數(shù)據(jù)挖掘CHAPTER數(shù)據(jù)預處理

1、1第2章: 數(shù)據(jù)(shj)預處理為什么預處理數(shù)據(jù)(shj)?數(shù)據(jù)清理 數(shù)據(jù)集成數(shù)據(jù)歸約離散化和概念分層產(chǎn)生小結(jié)共六十七頁2為什么數(shù)據(jù)(shj)預處理?現(xiàn)實世界中的數(shù)據(jù)是臟的不完全: 缺少屬性值, 缺少某些有趣的屬性, 或僅包含聚集數(shù)據(jù)例, occupation=“”噪音(zoyn): 包含錯誤或孤立點例, Salary=“-10”不一致: 編碼或名字存在差異例, Age=“42” Birthday=“03/07/2010”例, 以前的等級 “1,2,3”, 現(xiàn)在的等級 “A, B, C”例, 重復記錄間的差異共六十七頁3數(shù)據(jù)(shj)為什么臟?不完全數(shù)據(jù)源于數(shù)據(jù)收集時未包含數(shù)據(jù)收集和數(shù)據(jù)分析時

2、的不同考慮.人/硬件/軟件(run jin)問題噪音數(shù)據(jù)源于收集錄入傳輸不一致數(shù)據(jù)源于不同的數(shù)據(jù)源違反函數(shù)依賴共六十七頁4為什么數(shù)據(jù)(shj)預處理是重要的?沒有高質(zhì)量的數(shù)據(jù)(shj), 就沒有高質(zhì)量的數(shù)據(jù)(shj)挖掘結(jié)果!高質(zhì)量的決策必然依賴高質(zhì)量的數(shù)據(jù)例如, 重復或遺漏的數(shù)據(jù)可能導致不正確或誤導的統(tǒng)計.數(shù)據(jù)倉庫需要高質(zhì)量數(shù)據(jù)的一致集成共六十七頁5數(shù)據(jù)質(zhì)量：一個(y )多維視角一種(y zhn)廣泛接受的多角度:正確性(Accuracy)完全性(Completeness)一致性(Consistency)合時(Timeliness)：timely update? 可信性(Believabil

3、ity)可解釋性(Interpretability)可存取性(Accessibility)共六十七頁6數(shù)據(jù)預處理的主要(zhyo)任務數(shù)據(jù)清理填充缺失值, 識別/去除離群點, 光滑噪音, 并糾正數(shù)據(jù)中的不一致數(shù)據(jù)集成多個數(shù)據(jù)庫, 數(shù)據(jù)立方體, 或文件的集成數(shù)據(jù)變換規(guī)范化和聚集數(shù)據(jù)歸約得到數(shù)據(jù)的歸約表示, 它小得多, 但產(chǎn)生相同或類似(li s)的分析結(jié)果：維度規(guī)約、數(shù)值規(guī)約、數(shù)據(jù)壓縮數(shù)據(jù)離散化和概念分層共六十七頁7數(shù)據(jù)(shj)預處理的形式 共六十七頁8第2章: 數(shù)據(jù)(shj)預處理為什么預處理數(shù)據(jù)?數(shù)據(jù)清理(qngl) 數(shù)據(jù)集成數(shù)據(jù)歸約離散化和概念分層產(chǎn)生小結(jié)共六十七頁9數(shù)據(jù)(shj)清理

4、Data Cleaning現(xiàn)實世界的數(shù)據(jù)是臟的：很多潛在的不正確的數(shù)據(jù)，比如，儀器故障，人為或計算機錯誤，許多傳輸錯誤incomplete:缺少屬性(shxng)值, 缺少某些有趣的屬性, 或僅包含聚集數(shù)據(jù)e.g., 職業(yè)=“ ” (missing data)noisy:包含錯誤或孤立點e.g., Salary=“10” (an error)inconsistent:編碼或名字存在差異, e.g.,Age=“42”, Birthday=“03/07/2010”以前的等級 “1, 2, 3”, 現(xiàn)在等級 “A, B, C”重復記錄間的差異有意的(e.g.,變相丟失的數(shù)據(jù))Jan. 1 as ev

5、eryones birthday?共六十七頁10如何處理(chl)缺失數(shù)據(jù)?忽略元組: 缺少類別標簽時常用(假定涉及分類不是很有效，當每個屬性的缺失百分比變化大時手工填寫缺失數(shù)據(jù): 乏味+費時+不可行 ?自動填充一個全局常量 : e.g., “unknown”, a new class?! 使用屬性均值與目標元組同一類的所有(suyu)樣本的屬性均值: 更巧妙最可能的值: 基于推理的方法，如貝葉斯公式或決策樹共六十七頁11噪音(zoyn)數(shù)據(jù)Noisy DataNoise: 被測量的變量的隨機誤差或方差不正確的屬性值可能由于錯誤的數(shù)據(jù)收集工具(gngj)數(shù)據(jù)錄入問題 data entry pr

6、oblems數(shù)據(jù)傳輸問題data transmission problems技術限制 technology limitation不一致的命名慣例 inconsistency in naming convention 其他需要數(shù)據(jù)清理的問題重復記錄 duplicate records數(shù)據(jù)不完整 incomplete data不一致的數(shù)據(jù) inconsistent data共六十七頁12如何(rh)處理噪音數(shù)據(jù)?分箱Binning method:排序數(shù)據(jù)，分布到等頻/等寬的箱/桶中箱均值(jn zh)光滑、箱中位數(shù)光滑、箱邊界光滑, etc.聚類Clustering檢測和去除 離群點/孤立點 ou

7、tliers計算機和人工檢查相結(jié)合人工檢查可疑值 (e.g., deal with possible outliers)回歸 Regression回歸函數(shù)擬合數(shù)據(jù)共六十七頁13分箱：簡單的離散(lsn)化方法等寬度Equal-width (distance) 剖分:分成大小相等的n個區(qū)間: 均勻網(wǎng)格 uniform grid若A和B是 屬性的最低和最高取值, 區(qū)間寬度為: W = (B A)/N.孤立點可能占據(jù)重要影響 may dominate presentation傾斜的數(shù)據(jù)處理不好.等頻剖分 (frequency) /等深equi-depth :分成n個區(qū)間, 每一個含近似相同數(shù)目的樣本

8、Good data scaling類別(libi)屬性可能會非常棘手.共六十七頁14Binning Methods for Data Smoothing* Sorted data for price (in dollars): 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34* Partition into (equi-depth) bins: - Bin 1: 4, 8, 9, 15 - Bin 2: 21, 21, 24, 25 - Bin 3: 26, 28, 29, 34* Smoothing by bin means: - Bin 1: 9, 9

9、, 9, 9 - Bin 2: 23, 23, 23, 23 - Bin 3: 29, 29, 29, 29* Smoothing by bin boundaries: - Bin 1: 4, 4, 4, 15 - Bin 2: 21, 21, 25, 25 - Bin 3: 26, 26, 26, 34共六十七頁15聚類分析共六十七頁16Regressionxyy = x + 1X1Y1Y1共六十七頁17數(shù)據(jù)清理作為(zuwi)一個過程數(shù)據(jù)偏差檢測 Data discrepancy detection使用元數(shù)據(jù)(數(shù)據(jù)性質(zhì)的知識)(e.g.,領域, 長度范圍,從屬, 分布)檢查字段過載 fie

10、ld overloading 檢查唯一性規(guī)則, 連續(xù)性規(guī)則,空值規(guī)則使用商業(yè)工具數(shù)據(jù)清洗Data scrubbing: 使用簡單的領域知識(e.g., 郵編, 拼寫檢查) 檢查并糾正錯誤數(shù)據(jù)審計 Data auditing: 通過分析數(shù)據(jù)發(fā)現(xiàn)規(guī)則和聯(lián)系發(fā)現(xiàn)違規(guī)者(孤立點)數(shù)據(jù)遷移和集成數(shù)據(jù)遷移工具Data migration tools:允許指定轉(zhuǎn)換提取/變換/裝入工具ETL (Extraction/Transformation/Loading) tools: 允許用戶通過圖形用戶界面指定變換整合(zhn h)兩個過程兩個過程迭代和交互執(zhí)行(e.g., Potters Wheels)共六十七頁

11、18第2章: 數(shù)據(jù)(shj)預處理為什么預處理數(shù)據(jù)?數(shù)據(jù)清理 數(shù)據(jù)集成數(shù)據(jù)歸約離散(lsn)化和概念分層產(chǎn)生小結(jié)共六十七頁19數(shù)據(jù)(shj)集成數(shù)據(jù)集成 Data integration: 合并多個數(shù)據(jù)源中的數(shù)據(jù)，存在一個一致的數(shù)據(jù)存儲中涉及3個主要問題：模式集成、冗余數(shù)據(jù)、沖突數(shù)據(jù)值模式集成 Schema integration 例如., A.cust-id ？ B.cust-#實體識別(shbi)問題 Entity identification problem: 多個數(shù)據(jù)源的真實世界的實體的識別, e.g., Bill Clinton = William Clinton集成不同來源的元數(shù)據(jù)

12、沖突數(shù)據(jù)值的檢測和解決對真實世界的實體，其不同來源的屬性值可能不同原因:不同的表示,不同尺度,公制 vs. 英制共六十七頁20數(shù)據(jù)(shj)集成中冗余數(shù)據(jù)(shj)處理冗余數(shù)據(jù)Redundant data （集成多個數(shù)據(jù)庫時出現(xiàn)）目標識別：同一個屬性在不同的數(shù)據(jù)庫中有不同的名稱衍生數(shù)據(jù)：一個屬性值可由其他表的屬性推導出, e.g.,年收入相關分析 correlation analysis /協(xié)方差分析covariance analysis可用于檢測冗余數(shù)據(jù)小心的集成多個來源的數(shù)據(jù)可以幫助降低(jingd)和避免結(jié)果數(shù)據(jù)集中的冗余和不一致，提高數(shù)據(jù)挖掘的速度和質(zhì)量共六十七頁21相關(xinggu

13、n)分析 (數(shù)值數(shù)據(jù))Correlation coefficient (also called Pearsons product moment coefficient)相關系數(shù)（皮爾遜相關系數(shù)）n元組個數(shù), 和 屬性A和B上的平均值, A and B分別為各自(gz)標準差， (aibi) is the AB叉積 cross-product之和.If rA,B 0, A and B 正相關 (As values increase as Bs). 值越大相關程度越高.rA,B = 0: 不相關; rAB 0, 則A 和B 同時傾向于大于期望值.負covariance: If CovA,B 0.共

14、六十七頁26相關(xinggun)分析 (名義數(shù)據(jù)Nominal Data)2 (chi-square) test 開方檢驗ij是(ai,bj)的觀測頻度（實際計數(shù)）eij是(ai,bj)的期望(qwng)頻度N數(shù)據(jù)元組的個數(shù)屬A性a1a2iacb1Bb2jbr(A=ai,B=bj)2 值越大,相關的可能越大對 2 值貢獻最大的項，其實際值與期望值相差最大的相相關不意味著因果關系共六十七頁27Chi-Square 卡方值計算(j sun): 例子2 (chi-square) 計算(括號中的值為期望計值，由兩個類別的分布(fnb)數(shù)據(jù)計算得到)結(jié)果表明like_fiction 和play_che

15、ss 關聯(lián)Play chessNot play chessSum (row)看小說250(90)200(360)450不看小說50(210)1000(840)1050Sum(col.)30012001500共六十七頁28數(shù)據(jù)(shj)變換Data Transformation光滑: 去掉噪音，技術：分箱、回歸、聚類聚集Aggregation:匯總, 數(shù)據(jù)立方體構(gòu)造數(shù)據(jù)泛化Generalization:概念分層規(guī)范化Normalization:按比例縮放到一個具體區(qū)間最小-最大規(guī)范化z-score 規(guī)范化小數(shù)定標規(guī)范化屬性(shxng)Attribute/特征feature 構(gòu)造從給定的屬性構(gòu)造

16、新屬性機器學習中稱為：特征構(gòu)造數(shù)據(jù)規(guī)約共六十七頁29規(guī)范化數(shù)據(jù)(shj)的方法最小-最大規(guī)范化 min-max normalization新數(shù)據(jù)可能“越界”z-score normalizationnormalization by decimal scaling移動屬性(shxng)A的小數(shù)點位置(移動位數(shù)依賴于屬性A的最大值)J為使得 Max(| |)最后的集合: A1, A4, A6維度規(guī)約-決策樹規(guī)約共六十七頁3939維度規(guī)約-屬性/特征(tzhng)產(chǎn)生Feature Generation 產(chǎn)生新的屬性，其可以比原始屬性更有效地表示數(shù)據(jù)的重要信息。三個一般方法:屬性提取 Attribu

17、te extraction特定領域(ln y)的映射數(shù)據(jù)到新空間E.g., 傅立葉變換, wavelet transformation, 流形方法( manifold approaches)屬性構(gòu)造組合特征數(shù)據(jù)離散化 Data discretization共六十七頁4040 x2x1e主成分(chng fn)分析 (PCA)principal component analysis，K-L變換(binhun)找到一個投影，其能表示數(shù)據(jù)的最大變化原始數(shù)據(jù)投影到一個更小的空間中，導致維度減少. 發(fā)現(xiàn)的協(xié)方差矩陣的特征向量，用這些特征向量定義新的空間共六十七頁4141給定 p維空間中的N個點, 找到

18、k p 個正交向量 (principal components) 可以很好表示原始數(shù)據(jù)的 歸范化輸入數(shù)據(jù): 每個屬性值位于相同的區(qū)間內(nèi)計算(j sun) k 個標準正交向量, i.e., principal components每個輸入的點是這k 個主成分的線性組合The principal components are sorted in order of decreasing “significance” or strengthSince the components are sorted, the size of the data can be reduced by eliminatin

19、g the weak components(i.e., using the strongest principal components, it is possible to reconstruct a good approximation of the original data)Works for numeric data only主成分(chng fn)分析 (Steps)共六十七頁42X1X2Y1Y2Principal Component Analysis共六十七頁43數(shù)值(shz)規(guī)約選擇替代的、“較小的”數(shù)據(jù)表示形式參數(shù)方法假設數(shù)據(jù)適合某個模型(mxng)，估計模型(mxng)參數(shù)

20、，僅存儲的參數(shù)，并丟棄數(shù)據(jù)（孤立點除外）對數(shù)線性模型:基于一個較小的維組合的子集來估計 離散屬性的多維空間中每個點的概率非參數(shù)方法不假定模型histograms, clustering, sampling 共六十七頁44回歸(hugu)和對數(shù)線性模型線性回歸: 數(shù)據(jù)擬合到一條直線上通常(tngchng)使用最小二乘法擬合多元線性回歸允許響應變量Y表示為多個預測變量的函數(shù)對數(shù)線性模型: 近似離散的多維概率分布共六十七頁4545回歸(hugu)分析研究因變量/響應變量Y(dependent variable/response variable) 對個或多個自變量/解釋變量(independent

21、variable / explanatory variable)的相依關系的方法的統(tǒng)稱參數(shù)需要估計以最好的擬合給定(i dn)的數(shù)據(jù)絕大多數(shù)情況“最好的擬合”是由最小二乘法(least squares method)實現(xiàn), 其他的方法也有用于預測（包括時間序列數(shù)據(jù)的預測），推斷，假設檢驗和因果關系的建模yxy = x + 1X1Y1Y1共六十七頁46線性回歸(hugu)-用于預測Y: -diameter at breast height(DBH) X: - Age0123456789101112Y?1.01.01.56.09.010.51116.59.58.012.512.5X34111215

22、284552577581889397共六十七頁47線性回歸(hugu)(cont.)Given x, construct the linear regression model for y against x as:Least squares estimation of y given variable x is:共六十七頁48多元(du yun)線性回歸響應變量(binling): w，自變量: A1,A2,Ak.“5” 樣本數(shù)目共六十七頁49直方圖Histograms把數(shù)據(jù)劃分(hu fn)成不相交的子集或桶一維時可用動態(tài)規(guī)劃優(yōu)化構(gòu)建涉及量化問題共六十七頁50聚類Clustering將對象

23、劃分成集/簇, 用簇的表示替換實際數(shù)據(jù)技術的有效性依賴于數(shù)據(jù)的質(zhì)量使用(shyng)層次聚類，并多維索引樹結(jié)構(gòu)存放非常多的聚類算法和定義共六十七頁51抽樣(chu yn)Sampling抽樣: 獲得一個小的樣本(yngbn)集s來表示整個數(shù)據(jù)集 N允許一個挖掘算法運行復雜度子線性于樣本大小關鍵原則:選擇一個有代表性的數(shù)據(jù)子集數(shù)據(jù)偏斜時簡單隨機抽樣的性能很差發(fā)展適應抽樣方法：分層抽樣 Note: Sampling may not reduce database I/Os (page at a time)共六十七頁52抽樣(chu yn)類型 Types of Sampling簡單隨機抽樣 Sim

24、ple random sampling相同的概率選擇任何(rnh)特定項目無放回抽樣 Sampling without replacementOnce an object is selected, it is removed from the population放回抽樣Sampling with replacement一個被抽中的目標不從總體中去除分層抽樣 Stratified sampling: 把數(shù)據(jù)分成不相交部分(層), 然后從每個層抽樣(按比例/大約相同比例的數(shù)據(jù)) 偏斜數(shù)據(jù)共六十七頁53Sampling: With or without ReplacementSRSWOR(simp

25、le random sample without replacement)SRSWRRaw Data共六十七頁54Sampling: Cluster or Stratified SamplingRaw Data Cluster/Stratified Sample共六十七頁55第2章: 數(shù)據(jù)(shj)預處理為什么預處理數(shù)據(jù)?數(shù)據(jù)清理 數(shù)據(jù)集成數(shù)據(jù)歸約離散化和概念(ginin)分層產(chǎn)生小結(jié)共六十七頁56離散(lsn)化 Discretization和概念分成三種類型屬性:名義 values from an unordered set， color, profession順序數(shù) values fro

26、m an ordered set , e.g., military or academic rank 連續(xù) real numbers離散化 Discretization: 把連續(xù)屬性的區(qū)域分成區(qū)間(q jin)區(qū)間標號可以代替實際數(shù)據(jù)值 利用離散化減少數(shù)據(jù)量有監(jiān)督 vs. 無監(jiān)督：是否使用類的信息某個屬性上可以遞歸離散化分裂 Split (top-down) vs. 合并merge (bottom-up)自頂向下：由一個/幾個點開始遞歸劃分整個屬性區(qū)間遞歸離散化屬性，產(chǎn)生屬性值分層/多分辨率劃分：概念分層共六十七頁57數(shù)值數(shù)據(jù)離散(lsn)化/概念分層分箱 Binning(Top-down s

27、plit, unsupervised)直方圖（Top-down split, unsupervised）聚類 (unsupervised, top-down split or bottom-up merge)基于2 分析的區(qū)間合并(unsupervised, bottom-up merge)基于熵 Entropy-based discretization根據(jù)(gnj)自然劃分共六十七頁58不用(byng)類別(Binning vs. Clustering) DataEqual interval width (binning)Equal frequency (binning)K-means cl

28、ustering leads to better results共六十七頁59基于(jy)熵Entropy的離散化共六十七頁60 Chi-merge離散(lsn)化Chi-merge: 2-based discretization有監(jiān)督: use class information自低向上: find the best neighboring intervals (具有(jyu)相似的類別分布, i.e., low 2 values) to merge遞歸地合并, until a predefined stopping condition共六十七頁61由自然(zrn)劃分離散化3-4-5 規(guī)則

29、如果最高有效(yuxio)位包含 3, 6, 7 or 9 個不同的值, partition the range into 3 個等寬區(qū)間（7：2-3-2分成3個區(qū)間）2, 4, or 8 不同的值, 區(qū)域分成 4 個等寬區(qū)間1, 5, or 10 不同的值, 區(qū)域分成5 個等寬區(qū)間類似地，逐層使用此規(guī)則共六十七頁62分類(fn li)數(shù)據(jù)的概念分層 Categorical Data用戶/專家(zhunji)在模式級顯式地指定屬性的偏序streetcitystatecountry通過顯式數(shù)據(jù)分組說明分層厄本，香檳，芝加哥Illinois只說明屬性集 系統(tǒng)自動產(chǎn)生屬性偏序，根據(jù) 每個屬性下不同值

30、的數(shù)據(jù)啟發(fā)式規(guī)則：相比低層，高層概念的屬性通常有較少取值E.g., street city state country只說明部分屬性值共六十七頁63自動(zdng)產(chǎn)生概念分層Some concept hierarchies can be automatically generated based on the analysis of the number of distinct values per attribute in the given data set 含不同值最多的屬性(shxng)放在層次的最低層Note: Exceptionweekday, month, quarter, y

31、earcountryprovince_or_ statecitystreet15 distinct values65 distinct values3567 distinct values674,339 distinct values共六十七頁64SummaryData preparation is a big issue for both warehousing and miningData preparation includesData cleaning and data integrationData reduction and feature selectionDiscretizat

32、ionA lot a methods have been developed but still an active area of research共六十七頁Data Reduction, Transformation, IntegrationData QualityMajor Tasks in Data PreprocessingData Cleaning and Data IntegrationData Cleaningi. Missing Data and Misguided Missing Dataii. Noisy Dataiii. Data Cleaning as a Proce

33、ssData Integration MethodsData ReductionData Reduction StrategiesDimensionality Reductioni. Principal Component analysisii. Feature Subset Selectioniii. Feature CreationNumerosity Reductioni. Parametric Data Reduction: Regression and Log-Linear Modelsii. Mapping Data to a New Space: Wavelet Transfor

34、mationiii. Data Cube aggregationiv. Data Compressionv. Histogram analysisvi. Clusteringvii. Sampling: Sampling without Replacement, Stratified SamplingData Transformation and Data DiscretizationData Transformation: NormalizationData Discretization Methodsi. Binningii. Cluster Analysisiii. Discretiza

35、tion Using Class Labels: Entropy-Based Discretizationiv. Discretization Without Using Class Labels: Interval Merge by 2 AnalysisConcept Hierarchy and Its Formationi. Concept Hierarchy Generation for Numerical Dataii. Concept Hierarchy Generation for Categorical Dataiii. Automatic Concept Hierarchy Generation共六十七頁66ReferencesE. Rahm and H. H. Do. Data Cleaning: Problems and Current Approaches. IEEE Bulletin of the Technical Committee on Data Engineering. Vol.23, No.4D. P. Ballou and G. K. Tayi. Enhancing data quality in data warehou