數(shù)據(jù)挖掘概念與技術(shù)第三章

1、第三章 數(shù)據(jù)預(yù)處理3.1 數(shù)據(jù)預(yù)處理3.2 數(shù)據(jù)清理3.3 數(shù)據(jù)集成3.4 數(shù)據(jù)規(guī)約3.5 數(shù)據(jù)變換與數(shù)據(jù)離散化3.6小結(jié)3.3.1 為什么要對數(shù)據(jù)預(yù)處理 低質(zhì)量的數(shù)據(jù)將導(dǎo)致低質(zhì)量的挖掘結(jié)果 準(zhǔn)確性 完整性 一致性 時(shí)效性 可信性 可解釋性高質(zhì)量數(shù)據(jù)3.1.2 數(shù)據(jù)處理的主要任務(wù) 數(shù)據(jù)清理 數(shù)據(jù)集成 數(shù)據(jù)歸約 數(shù)據(jù)變換現(xiàn)實(shí)世界的的數(shù)據(jù)一般是不完整的，有噪聲的和不一致性的。數(shù)據(jù)清現(xiàn)實(shí)世界的的數(shù)據(jù)一般是不完整的，有噪聲的和不一致性的。數(shù)據(jù)清理理試圖填充缺失值，光滑噪聲試圖填充缺失值，光滑噪聲、識別識別離離群群點(diǎn)、糾正數(shù)據(jù)中的不一致點(diǎn)、糾正數(shù)據(jù)中的不一致。3.2.1 缺失值1）忽略元組：缺少類標(biāo)號時(shí)

2、通常這么做。但是忽略的元組其他屬性也不能用，即便是有用的。2）人工填寫：該方法很費(fèi)事費(fèi)時(shí)，數(shù)據(jù)集很大、缺失值很多時(shí)可能行不通。3）使用一個(gè)全局常量填充缺失值：將缺失值的屬性用同一個(gè)常量替換。（方法簡單但不可靠）4）使用屬性的中心度量（均值、中位數(shù)）填寫缺失值：對于正常的（對稱的）數(shù)據(jù)分布，可以使用均值；對于傾斜數(shù)據(jù)（非對稱）應(yīng)該使用中位數(shù)。5）使用與給定元組同一類的所有樣本的屬性均值或中位數(shù)： 利用另外一個(gè)屬性分類數(shù)據(jù)，計(jì)算缺失值的屬性值該是多少（均值或中位數(shù)）。6）使用最可能的值填充：利用回歸、貝葉斯形式化方法的基于推理的工具或決策樹歸納確定。3.2.2 噪聲數(shù)據(jù) 噪聲：被測量的變量的隨機(jī)誤

3、差或方差。1）分箱：排序后的數(shù)據(jù)按等頻（每個(gè)箱幾個(gè)值）分箱， 然后： 用箱均值光滑：箱中每個(gè)值都被替換為箱中的均值。 用箱中位數(shù)光滑：箱中的每一個(gè)只都被替換為該箱的中位數(shù)。 用箱邊界光滑：給定箱中的最大和最小值同樣被視為箱邊界， 箱中每個(gè)值都被替換為最接近的邊界值。2）回歸：可以用一個(gè)函數(shù)擬合數(shù)據(jù)來光滑數(shù)據(jù)。3）離群點(diǎn)分析：通過如聚類來檢測利群點(diǎn)。3.2.3 數(shù)據(jù)清理作為一個(gè)過程數(shù)據(jù)清理的第一步是偏差檢測。導(dǎo)致偏差的因素很多，認(rèn)為輸入錯(cuò)誤、有意錯(cuò)誤、數(shù)據(jù)退化（過時(shí)數(shù)據(jù)）、編碼不一致、設(shè)備錯(cuò)誤、系統(tǒng)錯(cuò)誤。如何進(jìn)行偏差檢測？ 使用任何關(guān)于數(shù)據(jù)性質(zhì)的知識： 元數(shù)據(jù)（主要是描述數(shù)據(jù)屬性（propert

4、y）的信息）、數(shù)據(jù)的基本統(tǒng)計(jì)描述（均值、中位數(shù)、眾數(shù)、方差、標(biāo)準(zhǔn)差等）、唯一性規(guī)則、連續(xù)性規(guī)則、空值規(guī)則。 數(shù)據(jù)挖掘經(jīng)常需要數(shù)據(jù)集成合并來自多個(gè)數(shù)據(jù)存儲(chǔ)的數(shù)據(jù)。3.3.1 實(shí)體識別問題 模式集成和對象匹配可能需要技巧，例如如何讓計(jì)算機(jī)識別customer_id和另外一個(gè)數(shù)據(jù)庫的cust_number是同一屬性？ 利用元數(shù)據(jù)，每個(gè)屬性的元數(shù)據(jù)包括名字、含義、數(shù)據(jù)類型和屬性的值的允許范圍，以及處理空值的規(guī)則。這些元數(shù)據(jù)可以用來幫助避免模式集成的錯(cuò)誤，還有助于變化數(shù)據(jù)3.3.2 冗余和相關(guān)分析 一個(gè)屬性如果能由另一個(gè)或另一組屬性“導(dǎo)出”，則這個(gè)屬性可能是冗余的；屬性或維命名的不一致也可能導(dǎo)致結(jié)果數(shù)據(jù)

5、集的冗余。1.標(biāo)稱數(shù)據(jù)的卡方相關(guān)檢驗(yàn)2.數(shù)值數(shù)據(jù)的相關(guān)系數(shù)3.數(shù)值數(shù)據(jù)的協(xié)方差1.標(biāo)稱數(shù)據(jù)的卡方相關(guān)檢驗(yàn) 假設(shè)A有c個(gè)不同的值，a1, a2,.ac. B有r個(gè)不同的值，b1,b2,br. 則包含屬性A和屬性B的元組可以使用一個(gè)列聯(lián)表來表示，其中A屬性的c個(gè)不同值構(gòu)成表的列，B屬性的r個(gè)不同值構(gòu)成表的行。令(Ai, Bj)表示屬性A取ai而屬性B取bj的聯(lián)合事件，即（A=ai, B=bj).在表中每一個(gè)可能的(Ai, Bj)聯(lián)合事件都有一個(gè)單元?？ǚ街档墓绞牵浩渲校琽ij表示觀察到的（Ai, Bj)聯(lián)合事件的頻率（實(shí)際次數(shù)）。而eij表示(Ai,Bj)事件的期望頻率，計(jì)算公式是：其中，n是數(shù)

6、據(jù)元組的個(gè)數(shù)?？ǚ浇y(tǒng)計(jì)檢驗(yàn)假定屬性A和屬性B是互相獨(dú)立的，即這兩個(gè)屬性之間沒有關(guān)聯(lián)?；陲@著性水平，自由度是(r-1)*(c-1)。如果假設(shè)被拒絕，則A和B統(tǒng)計(jì)相關(guān)。3.13.2假設(shè)調(diào)查了1500個(gè)人，按性別分成男和女。每個(gè)人投票是否喜歡閱讀小說。這樣，就有了兩個(gè)屬性：gender和preferred_reading.觀察到的每個(gè)可能的聯(lián)合事件的次數(shù)在表3.1中。圓括號中的表示事件的期望次數(shù)，按照公式3.2計(jì)算出來的?？梢宰⒁獾剑恳恍兄?，期望次數(shù)的總和必須和這一行的觀察次數(shù)的總和相等；每一列中，期望次數(shù)的和等于這一列的觀察次數(shù)的和。利用公式3.1，計(jì)算卡方值為：對于2*2的表，自由度為(2-

7、1)*(2-1)=1. 在自由度為1時(shí)，卡方值為10.828則可以在0.001的顯著性水平上拒絕值原假設(shè)。因?yàn)橛?jì)算出的值大于這個(gè)值，所以能以更小的顯著性水平拒絕原假設(shè)，即性別和是否喜歡讀小說之間存在強(qiáng)相關(guān)關(guān)系。2 數(shù)值數(shù)據(jù)的相關(guān)系數(shù)3.3相關(guān)系數(shù)rAB的值在-1到+1之間。如果rAB 0，則稱A和B正相關(guān)正相關(guān)。表示A的值隨著B的值的增大而增大。值越大，相關(guān)性越強(qiáng)。因此，一個(gè)很大的值意味著A（或B)需要被作為冗余刪除。如果rAB =0,則A和B相互獨(dú)立相互獨(dú)立，它們之間沒有任何關(guān)系。如果值0,則A和B負(fù)相關(guān)負(fù)相關(guān)，表示一個(gè)屬性的值隨著另一個(gè)值的降低而增大。散點(diǎn)圖可以用來可視化屬性之間的關(guān)聯(lián)關(guān)系

8、。注意：關(guān)聯(lián)并不表示因果。即如果A和B相關(guān)，但并不意味著A導(dǎo)致B或者B導(dǎo)致A。例如，在分析一個(gè)人口統(tǒng)計(jì)數(shù)據(jù)庫時(shí)，我們發(fā)現(xiàn)表示醫(yī)院數(shù)目的屬性和盜車數(shù)目相關(guān)。但這并不表示一個(gè)屬性導(dǎo)致了另外一個(gè)。兩個(gè)屬性實(shí)際上都是因?yàn)槿丝跀?shù)這第三個(gè)屬性導(dǎo)致的。3. 數(shù)值數(shù)據(jù)的協(xié)方差在概率理論和統(tǒng)計(jì)學(xué)中，相關(guān)性相關(guān)性和協(xié)方差協(xié)方差是評價(jià)兩個(gè)屬性是否一起發(fā)生變化的兩種相似的測量。考慮兩個(gè)數(shù)值型屬性A和B, n個(gè)觀察(a1,b1),(an,bn). 屬性A和屬性B的均值，即期望值為：和則屬性A和B的協(xié)方差協(xié)方差為：如果利用公式3.3來計(jì)算相關(guān)系數(shù)相關(guān)系數(shù)rA,B,則：其中分母是屬性A和B的標(biāo)準(zhǔn)差?？梢钥吹剑紤]下表，這是

9、一個(gè)觀察到的5次AllElectronics和Hightech公式的股票價(jià)格。如果股票是被同一個(gè)公司的趨勢影響，那么它們的價(jià)格是否一起漲落呢？計(jì)算均值：則協(xié)方差為：協(xié)方差值為正，因此，我們可以說兩個(gè)公司的股票是一起漲的。3.3.3 元祖重復(fù)除了檢測屬性間的冗余，元組級別的冗余元組級別的冗余也需要被檢測。不規(guī)范表的使用（一般是為了避免連接提高性能）是另一種數(shù)據(jù)冗余的來源。在不同的復(fù)制之間常常產(chǎn)生不一致性。因?yàn)椴痪_的數(shù)據(jù)輸入或者更新了一部分而非全部的數(shù)據(jù)。例如，一個(gè)購買訂單數(shù)據(jù)庫包含購買者的姓名和地址屬性，而非這個(gè)信息的主鍵信息。不一致性就可能產(chǎn)生，比如在購買訂單數(shù)據(jù)庫中同樣的購買者姓名卻是不同

10、的地址。3.3.4 數(shù)據(jù)值沖突的檢測與處理數(shù)據(jù)集成數(shù)據(jù)集成還包含數(shù)據(jù)值沖突的檢測和解析。例如，對于同一個(gè)真實(shí)世界實(shí)體，不同來源的屬性值可能不同?？赡苁且?yàn)楸磉_(dá)、刻度或者編碼的不同。比如，體重屬性在一個(gè)系統(tǒng)中可能以公制單位存放而在另一個(gè)中以英制單位存放。學(xué)校之間交換信息的時(shí)候，每個(gè)學(xué)校有自己的課程設(shè)置和等級模式。一個(gè)大學(xué)可能采用一個(gè)季度系統(tǒng)，一個(gè)數(shù)據(jù)庫系統(tǒng)中3門課程，等級從A+到F。另一個(gè)可能采用學(xué)期值，數(shù)據(jù)庫中提供2門課程，等級從1到10. 很難制定兩所大學(xué)精確的課程等級轉(zhuǎn)換規(guī)則，交換信息很困難。3.4.1 數(shù)據(jù)規(guī)約策略的概述3.4.2 小波變換3.4.3 主成分分析3.4.4 屬性子集選擇3

11、.4.5 回歸和對數(shù)線性模型：參數(shù)化數(shù)據(jù)規(guī)約3.4.6 直方圖3.4.7 聚類3.4.8 抽樣3.4.9 數(shù)據(jù)立方體聚集3.4.1 數(shù)據(jù)規(guī)約策略的概述 數(shù)據(jù)規(guī)約策略包括維歸約，數(shù)量規(guī)約，數(shù)據(jù)壓縮 1）維歸約：減少所考慮的隨機(jī)變量或?qū)傩缘膫€(gè)數(shù)。方法有 小波變換和主成分分析，它們把原數(shù)據(jù)變換或投影到較小的空間。屬性子集選擇是一種維歸約方法，其中不相關(guān)、弱相關(guān)或冗余的屬性或維被檢測和刪除。 2）數(shù)量歸約：用替代的、較小的數(shù)據(jù)表示形式替換原數(shù)據(jù)。 3）數(shù)據(jù)壓縮：使用變換，以便得到原數(shù)據(jù)的歸約或“壓縮”表示。如果原數(shù)據(jù)能夠從壓縮后的數(shù)據(jù)重構(gòu)，而不損失信息，該數(shù)據(jù)歸約為 無損的，近似重構(gòu)原數(shù)據(jù)稱為有損的。

12、（1）離散小波變換（DWT）：一種線性信號處理技術(shù)，用于數(shù)據(jù)向量X時(shí)，將它變成不同的數(shù)值小波系數(shù)向量X。（2）主成分分析：（PCA）又稱K-L方法，搜索k個(gè)最能代表數(shù)據(jù)的n維正交向量，其中k=n。（3）屬性子集選擇：通過刪除不相關(guān)或冗余的屬性（維）減少數(shù)據(jù)量。目標(biāo)是找出最小屬性集，使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性得到的原分布。另外，在縮小后的屬性集上挖掘能夠減少出現(xiàn)在發(fā)現(xiàn)模式上的屬性數(shù)目，使得模式更易于理解。（4）回歸和對數(shù)線性模型：參數(shù)化數(shù)據(jù)歸約 回歸和對數(shù)線性模型可以用來近似給定的數(shù)據(jù)。 對數(shù)線性模型：近似離散的多維概率分布。給定n維元組的集合，我們把每個(gè)元組看做n維空間的點(diǎn)，

13、對于離散屬性集，可使用對數(shù)線性模型，基于維組合的一個(gè)較小子集，估計(jì)多維空間中每個(gè)點(diǎn)的概率。（5）直方圖 直方圖使用分箱來近似數(shù)據(jù)分布，是一種流行的數(shù)據(jù)歸約形式。（6）聚類 聚類技術(shù)把數(shù)據(jù)元組看做對象，將對象劃分為群或簇，使得在一個(gè)簇中的對象相互“相似”，而與其他簇中的對象“相異”。通常，相似性基于距離函數(shù)。（7）抽樣 抽樣可以作為一種數(shù)據(jù)歸約的技術(shù)使用，因?yàn)樗试S用數(shù)據(jù)小得多的隨機(jī)樣本表示數(shù)據(jù)集。例如：簇抽樣，分層抽樣（8）數(shù)據(jù)立方體聚集 對數(shù)據(jù)倉庫的多維數(shù)據(jù)結(jié)構(gòu)建模3.5.1 數(shù)據(jù)變換策略概述： 1）光滑：去掉數(shù)據(jù)中的噪聲。技術(shù)包括分箱、回歸、聚類。 2）屬性構(gòu)造（特征構(gòu)造）：由給定的屬性構(gòu)

14、造新的屬性并添加到屬性集中，以幫助數(shù)據(jù)挖掘。 3）聚集：對數(shù)據(jù)進(jìn)行匯總或聚集。 4）規(guī)范化：把屬性數(shù)據(jù)按比例縮放，使之落入一個(gè)特定的區(qū)間。 5）離散化：數(shù)值屬性（eg。年齡）的原始值用區(qū)間標(biāo)簽（eg. 0-10,11-20）或概念標(biāo)簽（youth，adult，senior）替換。 6）由標(biāo)稱數(shù)據(jù)產(chǎn)生概念分層：將某個(gè)屬性（eg. street）泛化到較高的概念層（city）。3.5.2 通過規(guī)范化變換數(shù)據(jù)1.最小-最大規(guī)范化：對原始數(shù)據(jù)進(jìn)行線性變換。令minA和maxA表示屬性A的最小值和最大值，最小最大值標(biāo)準(zhǔn)化將值vi映射為vi(范圍是new_minA, new_maxA:最小最大值標(biāo)準(zhǔn)化保留

15、了原有數(shù)據(jù)值的關(guān)系。如果后來的輸入的標(biāo)準(zhǔn)化的數(shù)據(jù)落在了原有數(shù)據(jù)區(qū)間的外面，將會(huì)發(fā)生過界的錯(cuò)誤。假定收入屬性的最小值和最大值分別是$12,000和$98,000. 將收入屬性映射到范圍0.0, 1.0上。則一個(gè)值為$73,600的收入標(biāo)準(zhǔn)化為：3.5.2 通過規(guī)范化變換數(shù)據(jù)2. Z-分?jǐn)?shù)標(biāo)準(zhǔn)化假定income屬性的均值和標(biāo)準(zhǔn)差是$54,000和$16,000。使用z-分?jǐn)?shù)標(biāo)準(zhǔn)化，則$73,600被轉(zhuǎn)換為：3.5.3 通過分箱離散化 分箱并不使用類信息，因此是一種非監(jiān)督的離散化技術(shù)，對用戶制定的箱個(gè)數(shù)很敏感，也容易受離群點(diǎn)的影響。3.5.4 通過直方圖分析離散化 直方圖分析也是一種非監(jiān)督離散化技術(shù)

16、，因?yàn)樗皇褂妙愋畔ⅰ?.5.5 通過聚類、決策樹和相關(guān)分析離散化 聚類將數(shù)學(xué)的值劃分成簇或；離散化的決策樹方法是監(jiān)督的，它們使用了類標(biāo)號（分類）。3.5.6 標(biāo)稱數(shù)據(jù)的概念分層產(chǎn)生標(biāo)稱屬性具有有窮多個(gè)不同值，值之間無序。如地理位置，商品類型。 四中標(biāo)稱數(shù)據(jù)概念分層產(chǎn)生的方法： 1）由用戶或?qū)＜以谀Ｊ郊夛@示地說明屬性的部分序。（標(biāo)稱屬性或維的概念分層涉及一組屬性，由用戶或?qū)＜艺f明屬性的偏序或全序，然后很容易定義概念分層。） 2）通過顯式數(shù)據(jù)分組說明分層結(jié)構(gòu)的一部分。對于小部分?jǐn)?shù)據(jù)，顯式說明分組。 3）說明屬性集但不說明它們的偏序：用戶可以說明一個(gè)屬性集形成概念分層，但并不顯式說明它們的偏序，系

17、統(tǒng)可以試圖自動(dòng)產(chǎn)生屬性的序，構(gòu)造有意義的概念分層。 4）只說明部分屬性集 數(shù)據(jù)質(zhì)量包括精確性、完整性、一致性、時(shí)效性、可信性和可解釋性。質(zhì)量的評估基于對數(shù)據(jù)的預(yù)期使用。 即使目前存在大量的數(shù)據(jù)預(yù)處理技術(shù)，這仍然是一個(gè)研究的活躍領(lǐng)域，因?yàn)榇罅康牟灰恢潞团K數(shù)據(jù)的存在以及問題的復(fù)雜度的原因。D. P. Ballou and G. K. Tayi. Enhancing data quality in data warehouse environments. Comm. of ACM, 42:73-78, 1999A. Bruce, D. Donoho, and H.-Y. Gao. Wavelet a

18、nalysis. IEEE Spectrum, Oct 1996T. Dasu and T. Johnson. Exploratory Data Mining and Data Cleaning. John Wiley, 2003J. Devore and R. Peck. Statistics: The Exploration and Analysis of Data. Duxbury Press, 1997.H. Galhardas, D. Florescu, D. Shasha, E. Simon, and C.-A. Saita. Declarative data cleaning: Language, model, and algorithms. VLDB01M. Hua and J. Pei. Cleaning disguised missing data: A heuristic approach. KDD07H. V. Jagadish, et al., Special Issue on Data Reduction Techniques. Bulletin of the Technical Committee on Da