數(shù)據(jù)倉庫與數(shù)據(jù)挖掘基礎(chǔ)第3章數(shù)據(jù)預(yù)處理(趙志升)資料

1、1、數(shù)據(jù)預(yù)處理的意義2、數(shù)據(jù)清理(qngl)3、數(shù)據(jù)集成與變換4、數(shù)據(jù)歸約第三章 數(shù)據(jù)(shj)預(yù)處理共五十一頁1、數(shù)據(jù)質(zhì)量問題： 噪聲(zoshng)數(shù)據(jù) 空缺數(shù)據(jù) 不一致數(shù)據(jù)第一節(jié) 數(shù)據(jù)(shj)預(yù)處理的意義預(yù)處理數(shù)據(jù)提高數(shù)據(jù)質(zhì)量提高挖掘結(jié)果共五十一頁2、數(shù)據(jù)預(yù)處理的基本方法： 數(shù)據(jù)清理：除去噪聲，糾正不一致性。 數(shù)據(jù)集成：將多種數(shù)據(jù)源合并成一致的數(shù)據(jù)存儲(chǔ)(cn ch)。 數(shù)據(jù)變換：即規(guī)范化，可以改進(jìn)距離度量的挖掘 算法的精度和有效性。 數(shù)據(jù)歸約：通過聚集、刪除冗余特性或聚類方法 來壓縮數(shù)據(jù)。第一節(jié) 數(shù)據(jù)(shj)預(yù)處理的意義共五十一頁第一節(jié) 數(shù)據(jù)(shj)預(yù)處理的意義3、數(shù)據(jù)預(yù)處理的意義

2、 改進(jìn)數(shù)據(jù)質(zhì)量，提高其后的挖掘過程的精度和 性能。 高質(zhì)量的決策依賴于高質(zhì)量的數(shù)據(jù)，數(shù)據(jù)預(yù)處 理是知識(shí)發(fā)現(xiàn)過程的重要步驟。 檢測數(shù)據(jù)異常、盡早調(diào)整數(shù)據(jù)，并歸約待分析(fnx) 數(shù)據(jù)，將得到較高決策回報(bào)。共五十一頁第二節(jié) 數(shù)據(jù)(shj)清理 現(xiàn)實(shí)世界的數(shù)據(jù)一般是含噪聲(zoshng)的、不完整的、不一致的。數(shù)據(jù)清理例程試圖填充空缺的值，識(shí)別孤立點(diǎn)、消除噪聲，并糾正數(shù)據(jù)中的不一致。共五十一頁第二節(jié) 數(shù)據(jù)(shj)清理1、空缺值 忽略元組 人工填寫空缺值 使用一個(gè)全局常量填充空缺值 使用屬性的平均值填充空缺值 使用與給定元組屬同一類的所有(suyu)樣本的平均值 使用最可能的值填充空缺值共五十一頁第

3、二節(jié) 數(shù)據(jù)(shj)清理2、噪聲數(shù)據(jù) 噪聲是一個(gè)測量變量中的隨機(jī)錯(cuò)誤或偏差。對于(duy)噪聲通常采用數(shù)據(jù)平滑技術(shù)去除噪聲。 分箱（binning） 聚類（clustering） 回歸（regression）共五十一頁第二節(jié) 數(shù)據(jù)(shj)清理2、噪聲數(shù)據(jù) 分箱：通過考察周圍的值來平滑存儲(chǔ)數(shù)據(jù)的值，存儲(chǔ)的值被分布到一些“桶”或箱中。 按箱平均值平滑 按箱中值(zhn zh)平滑 按箱邊界平滑共五十一頁第二節(jié) 數(shù)據(jù)(shj)清理2、噪聲(zoshng)數(shù)據(jù) 聚類：孤立點(diǎn)可以被聚類檢測。聚類將類似的值組織成群或“聚類”，聚類集合之外的值被視為孤立點(diǎn)。共五十一頁第二節(jié) 數(shù)據(jù)(shj)清理2、噪聲數(shù)據(jù)

4、(shj) 回歸：通過讓數(shù)據(jù)適合一個(gè)函數(shù)（回歸函數(shù)）來平滑數(shù)據(jù)。 線性回歸：找出適合兩個(gè)變量的“最佳”直線， 使得一個(gè)變量能夠預(yù)測另一個(gè)。 多線性回歸：是線性回歸的擴(kuò)展，它涉及多于 兩個(gè)變量，數(shù)據(jù)要適合一個(gè)多維面。共五十一頁第二節(jié) 數(shù)據(jù)(shj)清理3、不一致數(shù)據(jù) 對于有些事務(wù)，記錄數(shù)據(jù)的不一致 數(shù)據(jù)集成可能造成數(shù)據(jù)的不一致 可以采用人工干預(yù)更正，以及知識(shí)工程工具來檢測違反限制(xinzh)和規(guī)則的數(shù)據(jù)。共五十一頁第三節(jié) 數(shù)據(jù)集成(j chn)與變換 數(shù)據(jù)挖掘經(jīng)常需要： 數(shù)據(jù)(shj)集成：由多個(gè)數(shù)據(jù)(shj)存儲(chǔ)合并數(shù)據(jù)(shj) 數(shù)據(jù)轉(zhuǎn)換：將數(shù)據(jù)轉(zhuǎn)換成適于挖掘的形式共五十一頁第三節(jié) 數(shù)據(jù)(

5、shj)集成與變換1、數(shù)據(jù)集成 數(shù)據(jù)集成是將多個(gè)數(shù)據(jù)源中的數(shù)據(jù)結(jié)合起來存放在一個(gè)一致的數(shù)據(jù)存儲(chǔ)中。這些(zhxi)數(shù)據(jù)源可以包括多個(gè)數(shù)據(jù)庫、數(shù)據(jù)立方體或一般文件。共五十一頁第三節(jié) 數(shù)據(jù)集成(j chn)與變換1、數(shù)據(jù)集成 模式集成：可以通過元數(shù)據(jù)避免錯(cuò)誤(cuw)。 冗余：屬性的冗余以及元組重復(fù)。 數(shù)據(jù)值沖突的檢測與處理：不同數(shù)據(jù)源的屬 性值不同。共五十一頁第三節(jié) 數(shù)據(jù)(shj)集成與變換2、數(shù)據(jù)變換 數(shù)據(jù)變換將數(shù)據(jù)轉(zhuǎn)換成適合挖掘的形式，主要有： 平滑：除去數(shù)據(jù)中的噪聲，如分箱、聚類和回歸。 聚集：對數(shù)據(jù)進(jìn)行(jnxng)匯總和聚集。 數(shù)據(jù)概化：使用概念分層，用高層概念替換低層“原始” 數(shù)據(jù)。

6、 規(guī)范化：將屬性數(shù)據(jù)按比例縮放，使之落入一個(gè)小的特 定區(qū)間。 屬性構(gòu)造：構(gòu)造新的屬性并添加到屬性集中，以利挖掘。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約 數(shù)據(jù)歸約技術(shù)可以用來得到(d do)數(shù)據(jù)集的歸約表示，雖然它很小，但仍接近于保持原數(shù)據(jù)的完整性。這樣，在歸約后的數(shù)據(jù)集上挖掘?qū)⒏行?，并產(chǎn)生相同或幾乎相同的分析結(jié)果。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約數(shù)據(jù)(shj)歸約的策略有： 數(shù)據(jù)立方體聚集： 維歸約 數(shù)據(jù)壓縮 數(shù)值壓縮 離散化和概念分層生成共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約1、數(shù)據(jù)(shj)立方體聚集年=2002 年=2001 年=2000季度銷售額Q1Q2Q3Q436004430425

7、05700年銷售額200020012002179801623819650共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約1、數(shù)據(jù)立方體聚集 基本方體：創(chuàng)建在最低層的數(shù)據(jù)立方體。 頂點(diǎn)方體：最高層抽象的數(shù)據(jù)立方體。 方體：對不同層創(chuàng)建的數(shù)據(jù)立方體。 方體的格：數(shù)據(jù)立方體可以(ky)看作方體的格。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約2、維歸約 用于數(shù)據(jù)分析的數(shù)據(jù)可能包含數(shù)以百計(jì)的屬性，其中大部分屬性與挖掘任務(wù)不相關(guān)，是冗余的。 維歸約通過刪除不相關(guān)的屬性（或維）減少數(shù)據(jù)量?；静捎脤傩宰蛹x擇方法。屬性子集選擇的目標(biāo)是找出最小屬性集，使得數(shù)據(jù)類的概率分布盡可能地接近(jijn)使用所有屬性的原分布。共五十一頁

8、第四節(jié) 數(shù)據(jù)(shj)歸約2、維歸約 d個(gè)屬性有2d個(gè)可能的子集，通過窮舉搜索找出屬性的最佳子集可能是不現(xiàn)實(shí)(xinsh)的，通常使用壓縮搜索空間的啟發(fā)式算法，這些算法是貪心算法，在搜索屬性空間時(shí)，總是做看上去是最佳的選擇。其含義是由局部最優(yōu)選擇，期望由此導(dǎo)致全局最優(yōu)選擇。實(shí)際應(yīng)用中，貪心算法是有效的，并可以逼近最優(yōu)解。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約2、維歸約 屬性子集(z j)選擇的基本啟發(fā)式方法包括的技術(shù)有： 逐步向前選擇 逐步向后刪除 向前選擇和向后刪除的結(jié)合 判定樹歸納共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約2、維歸約 逐步(zhb)向前選擇：由空集開始，選擇屬性集中最好的屬性，并將

9、其添加到該集合中。隨后每次迭代，將原屬性集剩下的屬性中的最好的屬性添加到該集合中。 逐步向后刪除：由整個(gè)屬性集開始，每一步刪除掉尚在屬性集中的最壞的屬性。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約2、維歸約 向前選擇和向后刪除的結(jié)合：向前選擇和向后刪除方法的結(jié)合，每一步選擇一個(gè)最好的屬性，并在剩余屬性中刪除一個(gè)最壞的屬性。 說明：以上三種(sn zhn)方法可以使用一個(gè)閾值來確定是否停止屬性選擇。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約2、維歸約 判定樹歸納：判定樹算法，如ID3和C4.5。判定樹歸納構(gòu)造一個(gè)類似流程圖的結(jié)構(gòu)，其每個(gè)內(nèi)部節(jié)點(diǎn)表示一個(gè)屬性上的測試(csh)，每個(gè)分枝（非樹葉）對應(yīng)于測試(c

10、sh)的一個(gè)輸出；每個(gè)外部節(jié)點(diǎn)（樹葉）表示一個(gè)判定類。在每個(gè)節(jié)點(diǎn)，算法選擇“最好”的屬性，將數(shù)據(jù)劃分成類。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約2、維歸約 判定樹歸納：初始(ch sh)屬性集：A1，A2，A3，A4，A5，A6歸約后的屬性集：A2，A3，A5A3A2A5類1類2類1類2屬性子集選擇的貪心（啟發(fā)式）方法共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約3、數(shù)據(jù)壓縮 數(shù)據(jù)壓縮是指應(yīng)用數(shù)據(jù)編碼或變換，以便得到原數(shù)據(jù)的歸約或“壓縮”表示。 無損數(shù)據(jù)壓縮技術(shù)：原數(shù)據(jù)可以由壓縮數(shù)據(jù)重 新構(gòu)造而不丟失任何信息(xnx)，所采用的壓縮技術(shù)。 有損數(shù)據(jù)壓縮技術(shù)：只能重新構(gòu)造原數(shù)據(jù)的近 似表示，所采用的數(shù)據(jù)壓縮

11、技術(shù)。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約3、數(shù)據(jù)壓縮 兩種流行的有效的有損數(shù)據(jù)壓縮方法 小波變換(binhun) 主要成分分析共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約3、數(shù)據(jù)壓縮(sh j y su) 小波變換 離散小波變換DWT（Discret Wavelet Transform） 離散傅里葉變換DFT（ Discret Fourier Transform ）共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約3、數(shù)據(jù)壓縮 小波變換：離散小波變換DWT和離散傅里葉變換DFT均常用于信號處理技術(shù)。一般，DWT是一種較好的有損壓縮，若DWT和DFT保留相同數(shù)目的系數(shù)，DWT將提供原數(shù)據(jù)更精確的近似。比較流行(li

12、xng)的小波變換包括Haar、Daubechies變換，應(yīng)用離散小波變換的典型金字塔算法，在每次迭代將數(shù)據(jù)減半，導(dǎo)致很快的計(jì)算速度。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約3、數(shù)據(jù)壓縮(sh j y su) 小波變換可以用于多維數(shù)據(jù)，如數(shù)據(jù)立方體。其基本思路是：首先將變換用于第一維，然后第二維，如此下去。計(jì)算復(fù)雜性對于方體中的單元的個(gè)數(shù)是線性的。小波變換的有損壓縮比當(dāng)前的商業(yè)標(biāo)準(zhǔn)JPEG壓縮好。小波變換廣泛應(yīng)用于指紋圖象壓縮、計(jì)算機(jī)視覺、時(shí)間序列數(shù)據(jù)分析和數(shù)據(jù)清理。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約3、數(shù)據(jù)壓縮 主要成分分析PCA 假定待壓縮的數(shù)據(jù)由N個(gè)元組 或數(shù)據(jù)向量組成，取自k個(gè)維。PCA

13、搜索c個(gè)最能代表數(shù)據(jù)的k-維正交向量，這里ck。 意義：原來(yunli)的數(shù)據(jù)投影到一個(gè)較小的空間，導(dǎo)致數(shù)據(jù)壓縮。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約3、數(shù)據(jù)壓縮 主要成分分析PCA PCA可以作為一種維歸約形式使用。不象屬性子集選擇通過保留原屬性集的一個(gè)子集來減少屬性集的大小，PCA通過創(chuàng)建一個(gè)替換的、較小的變量集來“組合(zh)”屬性的精華，原數(shù)據(jù)可以投影到該較小的集合中。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約3、數(shù)據(jù)壓縮 主要成分分析PCA PCA計(jì)算花費(fèi)低，可以用于有序和無序(w x)的屬性，并且可以處理稀疏和傾斜數(shù)據(jù)。對于多于2維的數(shù)據(jù)可以通過將問題歸約為2維來處理。 與數(shù)據(jù)壓縮的小

14、波變換相比， PCA能較好地處理稀疏數(shù)據(jù)，而小波變換更適合高維數(shù)據(jù)。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約4、數(shù)值歸約 數(shù)值歸約技術(shù)就是通過選擇替代的、較小的數(shù)據(jù)表示形式來減少數(shù)據(jù)量，主要有有參和無參兩類： 有參方法：使用一個(gè)(y )模型來評估數(shù)據(jù)，使得只 需要存放參數(shù)，而不是實(shí)際數(shù)據(jù)。如，回歸 和對數(shù)線性模型。 無參方法：使用存放數(shù)據(jù)歸約表示。如，直方 圖、聚類、選樣。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約4、數(shù)值歸約 回歸和對數(shù)線性模型(mxng) 直方圖 聚類 選樣共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約4、數(shù)值歸約 回歸和對數(shù)線性模型 回歸和對數(shù)線性模型可以用來近似給定數(shù)據(jù)。在線性回歸中，對數(shù)

15、據(jù)建模，使之適合一條直線。對數(shù)線性模型近似離散(lsn)的多維概率分布。基于較小的方體形成數(shù)據(jù)立方體的格，該方法可以用于估計(jì)具有離散(lsn)屬性集的基本方體中每個(gè)單元的概率。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約4、數(shù)值歸約 回歸和對數(shù)線性模型 回歸和對數(shù)線性模型可以用于稀疏數(shù)據(jù)，但應(yīng)用可能是受限制的。在用于傾斜數(shù)據(jù)時(shí)，回歸效果更好。當(dāng)用于高維數(shù)據(jù)時(shí)，對數(shù)線性模型表現(xiàn)(bioxin)出很好的伸縮性，可以擴(kuò)展到10維左右。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約4、數(shù)值歸約 直方圖 直方圖使用分箱近似分布，是一種流行的數(shù)據(jù)歸約形式。屬性A的直方圖（histogram）將A的數(shù)據(jù)分布劃分為不相交的子集

16、，或桶。桶安放在水平(shupng)軸上，而桶的高度（和面積）是該桶所代表的值的平均頻率。如果每個(gè)桶只代表單個(gè)屬性值/頻率對，則該桶為單桶。通常，桶表示給定屬性的一個(gè)連續(xù)區(qū)間。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約4、數(shù)值(shz)歸約 直方圖 等寬 等深 V-最優(yōu) MaxDiff共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約4、數(shù)值歸約 聚類 聚類技術(shù)將數(shù)據(jù)元組視為對象。它將對象劃分為群或聚類，使得在一個(gè)聚類中的對象“類似”，但與其他聚類中的對象“不類似”。通常，類似性基于距離，用對象在空間中的“接近”程度定義。聚類的“質(zhì)量”可以用“直徑(zhjng)”表示，直徑(zhjng)是一個(gè)聚類中兩個(gè)任意對象的

17、最大距離。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約4、數(shù)值歸約 聚類 質(zhì)心距離是聚類質(zhì)量的另一種度量，它定義為聚類質(zhì)心到每個(gè)聚類對象的平均距離。 在數(shù)據(jù)歸約時(shí)，用數(shù)據(jù)的聚類表示替換實(shí)際數(shù)據(jù)。 在數(shù)據(jù)庫系統(tǒng)中，多維索引樹主要用于提供(tgng)對數(shù)據(jù)的快速訪問；也可用于分層數(shù)據(jù)歸約，提供(tgng)數(shù)據(jù)的多維聚類；也可用于提供(tgng)查詢的近似回答。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約4、數(shù)值歸約 選樣 選樣是用數(shù)據(jù)的較小隨機(jī)樣本（子集）表示大的數(shù)據(jù)集，它可以作為一種(y zhn)數(shù)據(jù)歸約技術(shù)使用。共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約4、數(shù)值歸約 選樣假定大的數(shù)據(jù)(shj)集D包含N個(gè)元組，則對

18、D的選樣有： 簡單選擇n個(gè)樣本，不回放 簡單選擇n個(gè)樣本，回放 聚類選樣 分層選樣共五十一頁第四節(jié) 數(shù)據(jù)(shj)歸約4、數(shù)值歸約 選樣 采用選樣進(jìn)行數(shù)據(jù)歸約的優(yōu)點(diǎn)：可以得到樣本的花費(fèi)正比例于樣本的大小n，而不是(b shi)數(shù)據(jù)的大小N。因此選樣的復(fù)雜性子線性于數(shù)據(jù)的大小。 用于數(shù)據(jù)歸約時(shí)，選樣最常用來回答聚集查詢。在指定的誤差范圍內(nèi)，可以用中心極限定理確定估計(jì)一個(gè)給定的函數(shù)的指定誤差范圍內(nèi)所需的樣本大小。共五十一頁第五節(jié) 離散(lsn)化和概念分層生成 通過將屬性域劃分為區(qū)間，離散化技術(shù)可以用來減少給定的連續(xù)屬性值的個(gè)數(shù)。區(qū)間的標(biāo)號可以替代實(shí)際的數(shù)據(jù)值。 許多離散化技術(shù)都可以遞歸使用，以便提供(tgng)屬性值的分層或多分解劃分，即概念分層。共五十一頁第五節(jié) 離散化和概念(ginin)分層生成1、數(shù)值數(shù)據(jù)的離散化和概念分層生成 對于數(shù)值屬性，由于數(shù)據(jù)的可能取值范圍的多樣性和數(shù)據(jù)值的更新頻繁，進(jìn)行概念分層比較困難。數(shù)值屬性的概念分層可以根據(jù)數(shù)據(jù)分布分析自動(dòng)(zdng)地構(gòu)造，基本方法主要有：共五十一頁第五節(jié) 離散(lsn)化和概念分層生成1、數(shù)值數(shù)據(jù)的離散(lsn)化和概念分層生成 分箱 直方圖分析 聚類分析 基于熵的離散化 通過自然劃分分段共五十一頁第五節(jié) 離散化和概念(ginin)分層生成2、分類數(shù)據(jù)的概念分層生成