數(shù)據(jù)挖掘-CHAPTER2-數(shù)據(jù)預(yù)處理

1、1第第2章章: 數(shù)據(jù)預(yù)處理數(shù)據(jù)預(yù)處理n為什么預(yù)處理數(shù)據(jù)為什么預(yù)處理數(shù)據(jù)?n數(shù)據(jù)清理數(shù)據(jù)清理 n數(shù)據(jù)集成數(shù)據(jù)集成n數(shù)據(jù)歸約數(shù)據(jù)歸約n離散化和概念分層產(chǎn)生離散化和概念分層產(chǎn)生n小結(jié)小結(jié)2為什么數(shù)據(jù)預(yù)處理為什么數(shù)據(jù)預(yù)處理?n現(xiàn)實(shí)世界中的數(shù)據(jù)是臟的現(xiàn)實(shí)世界中的數(shù)據(jù)是臟的n不完全不完全: 缺少屬性值缺少屬性值, 缺少某些有趣的屬性缺少某些有趣的屬性, 或僅包含聚集數(shù)據(jù)或僅包含聚集數(shù)據(jù)n例例, occupation=“”n噪音噪音: 包含錯(cuò)誤或孤立點(diǎn)包含錯(cuò)誤或孤立點(diǎn)n例例, Salary=“-10”n不一致不一致: 編碼或名字存在差異編碼或名字存在差異n例例, Age=“42” Birthday=“03/

2、07/2010”n例例, 以前的等級(jí)以前的等級(jí) “1,2,3”, 現(xiàn)在的等級(jí)現(xiàn)在的等級(jí) “A, B, C”n例例, 重復(fù)記錄間的差異重復(fù)記錄間的差異3數(shù)據(jù)為什么臟數(shù)據(jù)為什么臟?n不完全數(shù)據(jù)源于不完全數(shù)據(jù)源于n數(shù)據(jù)收集時(shí)未包含數(shù)據(jù)收集時(shí)未包含n數(shù)據(jù)收集和數(shù)據(jù)分析時(shí)的不同考慮數(shù)據(jù)收集和數(shù)據(jù)分析時(shí)的不同考慮.n人人/硬件硬件/軟件問(wèn)題軟件問(wèn)題n噪音數(shù)據(jù)源于噪音數(shù)據(jù)源于n收集收集n錄入錄入n傳輸傳輸n不一致數(shù)據(jù)源于不一致數(shù)據(jù)源于n不同的數(shù)據(jù)源不同的數(shù)據(jù)源n違反函數(shù)依賴違反函數(shù)依賴4為什么數(shù)據(jù)預(yù)處理是重要的為什么數(shù)據(jù)預(yù)處理是重要的?n沒(méi)有高質(zhì)量的數(shù)據(jù)沒(méi)有高質(zhì)量的數(shù)據(jù), 就沒(méi)有高質(zhì)量的數(shù)據(jù)挖掘結(jié)果就沒(méi)有高

3、質(zhì)量的數(shù)據(jù)挖掘結(jié)果!n高質(zhì)量的決策必然依賴高質(zhì)量的數(shù)據(jù)高質(zhì)量的決策必然依賴高質(zhì)量的數(shù)據(jù)n例如例如, 重復(fù)或遺漏的數(shù)據(jù)可能導(dǎo)致不正確或誤重復(fù)或遺漏的數(shù)據(jù)可能導(dǎo)致不正確或誤導(dǎo)的統(tǒng)計(jì)導(dǎo)的統(tǒng)計(jì).n數(shù)據(jù)倉(cāng)庫(kù)需要高質(zhì)量數(shù)據(jù)的一致集成數(shù)據(jù)倉(cāng)庫(kù)需要高質(zhì)量數(shù)據(jù)的一致集成5數(shù)據(jù)質(zhì)量：一個(gè)多維視角數(shù)據(jù)質(zhì)量：一個(gè)多維視角n一種廣泛接受的多角度一種廣泛接受的多角度:n正確性正確性(Accuracy)n完全性完全性(Completeness)n一致性一致性(Consistency)n合時(shí)合時(shí)(Timeliness)：timely update? n可信性可信性(Believability)n可解釋性可解釋性(Interp

4、retability)n可存取性可存取性(Accessibility)6數(shù)據(jù)預(yù)處理的主要任務(wù)數(shù)據(jù)預(yù)處理的主要任務(wù)n數(shù)據(jù)清理數(shù)據(jù)清理n填充缺失值填充缺失值, 識(shí)別識(shí)別/去除離群點(diǎn)去除離群點(diǎn), 光滑噪音光滑噪音, 并糾正數(shù)據(jù)中的不并糾正數(shù)據(jù)中的不一致一致n數(shù)據(jù)集成數(shù)據(jù)集成n多個(gè)數(shù)據(jù)庫(kù)多個(gè)數(shù)據(jù)庫(kù), 數(shù)據(jù)立方體數(shù)據(jù)立方體, 或文件的集成或文件的集成n數(shù)據(jù)變換數(shù)據(jù)變換n規(guī)范化和聚集規(guī)范化和聚集n數(shù)據(jù)歸約數(shù)據(jù)歸約n得到數(shù)據(jù)的歸約表示得到數(shù)據(jù)的歸約表示, 它小得多它小得多, 但產(chǎn)生相同或類似的分析結(jié)但產(chǎn)生相同或類似的分析結(jié)果：維度規(guī)約、數(shù)值規(guī)約、數(shù)據(jù)壓縮果：維度規(guī)約、數(shù)值規(guī)約、數(shù)據(jù)壓縮n數(shù)據(jù)離散化和概念分層

5、數(shù)據(jù)離散化和概念分層7數(shù)據(jù)預(yù)處理的形式數(shù)據(jù)預(yù)處理的形式 8第第2章章: 數(shù)據(jù)預(yù)處理數(shù)據(jù)預(yù)處理n為什么預(yù)處理數(shù)據(jù)為什么預(yù)處理數(shù)據(jù)?n數(shù)據(jù)清理數(shù)據(jù)清理 n數(shù)據(jù)集成數(shù)據(jù)集成n數(shù)據(jù)歸約數(shù)據(jù)歸約n離散化和概念分層產(chǎn)生離散化和概念分層產(chǎn)生n小結(jié)小結(jié)9數(shù)據(jù)清理數(shù)據(jù)清理 Data Cleaningn現(xiàn)實(shí)世界的數(shù)據(jù)是現(xiàn)實(shí)世界的數(shù)據(jù)是臟臟的：很多潛在的不正確的數(shù)據(jù)，比如，的：很多潛在的不正確的數(shù)據(jù)，比如，儀器故障，人為或計(jì)算機(jī)錯(cuò)誤，許多傳輸錯(cuò)誤儀器故障，人為或計(jì)算機(jī)錯(cuò)誤，許多傳輸錯(cuò)誤nincomplete:缺少屬性值缺少屬性值, 缺少某些有趣的屬性缺少某些有趣的屬性, 或僅包含聚集數(shù)據(jù)或僅包含聚集數(shù)據(jù)ne.g.,

6、 職業(yè)職業(yè)=“ ” (missing data)nnoisy:包含錯(cuò)誤或孤立點(diǎn)包含錯(cuò)誤或孤立點(diǎn)ne.g., Salary=“10” (an error)ninconsistent:編碼或名字存在差異編碼或名字存在差異, e.g.,nAge=“42”, Birthday=“03/07/2010”n以前的等級(jí)以前的等級(jí) “1, 2, 3”, 現(xiàn)在等級(jí)現(xiàn)在等級(jí) “A, B, C”n重復(fù)記錄間的差異重復(fù)記錄間的差異n有意的有意的(e.g.,變相丟失的數(shù)據(jù)變相丟失的數(shù)據(jù))nJan. 1 as everyones birthday?10如何處理缺失數(shù)據(jù)如何處理缺失數(shù)據(jù)?n忽略元組忽略元組: 缺少類別標(biāo)簽時(shí)

7、常用缺少類別標(biāo)簽時(shí)常用(假定涉及分類假定涉及分類不是很有不是很有效，當(dāng)每個(gè)屬性的缺失百分比變化大時(shí)效，當(dāng)每個(gè)屬性的缺失百分比變化大時(shí)n手工填寫(xiě)缺失數(shù)據(jù)手工填寫(xiě)缺失數(shù)據(jù): 乏味乏味+費(fèi)時(shí)費(fèi)時(shí)+不可行不可行 ?n自動(dòng)填充自動(dòng)填充n一個(gè)全局常量一個(gè)全局常量 : e.g., “unknown”, a new class?! n使用屬性均值使用屬性均值n與目標(biāo)元組同一類的所有樣本的屬性均值與目標(biāo)元組同一類的所有樣本的屬性均值: 更巧妙更巧妙n最可能的值最可能的值: 基于推理的方法，如基于推理的方法，如貝葉斯公式或決策樹(shù)貝葉斯公式或決策樹(shù)11噪音數(shù)據(jù)噪音數(shù)據(jù)Noisy DatanNoise: 被測(cè)量的變量

8、的隨機(jī)誤差或方差被測(cè)量的變量的隨機(jī)誤差或方差n不正確的屬性值可能由于不正確的屬性值可能由于n錯(cuò)誤的數(shù)據(jù)收集工具錯(cuò)誤的數(shù)據(jù)收集工具n數(shù)據(jù)錄入問(wèn)題數(shù)據(jù)錄入問(wèn)題 data entry problemsn數(shù)據(jù)傳輸問(wèn)題數(shù)據(jù)傳輸問(wèn)題data transmission problemsn技術(shù)限制技術(shù)限制 technology limitationn不一致的命名慣例不一致的命名慣例 inconsistency in naming convention n其他需要數(shù)據(jù)清理的問(wèn)題其他需要數(shù)據(jù)清理的問(wèn)題n重復(fù)記錄重復(fù)記錄 duplicate recordsn數(shù)據(jù)不完整數(shù)據(jù)不完整 incomplete datan不一

9、致的數(shù)據(jù)不一致的數(shù)據(jù) inconsistent data12如何處理噪音數(shù)據(jù)如何處理噪音數(shù)據(jù)?n分箱分箱Binning method:n排序數(shù)據(jù)，分布到等頻排序數(shù)據(jù)，分布到等頻/等寬的箱等寬的箱/桶中桶中n箱均值光滑、箱中位數(shù)光滑、箱邊界光滑箱均值光滑、箱中位數(shù)光滑、箱邊界光滑, etc.n聚類聚類Clusteringn檢測(cè)和去除檢測(cè)和去除 離群點(diǎn)離群點(diǎn)/孤立點(diǎn)孤立點(diǎn) outliersn計(jì)算機(jī)和人工檢查相結(jié)合計(jì)算機(jī)和人工檢查相結(jié)合n人工檢查可疑值人工檢查可疑值 (e.g., deal with possible outliers)n回歸回歸 Regressionn回歸函數(shù)擬合數(shù)據(jù)回歸函數(shù)擬合數(shù)

10、據(jù)13分箱：簡(jiǎn)單的離散化方法分箱：簡(jiǎn)單的離散化方法n等寬度等寬度Equal-width (distance) 剖分剖分:n分成大小相等的分成大小相等的n個(gè)區(qū)間個(gè)區(qū)間: 均勻網(wǎng)格均勻網(wǎng)格 uniform gridn若若A和和B是是 屬性的最低和最高取值屬性的最低和最高取值, 區(qū)間寬度為區(qū)間寬度為: W = (B A)/N.n孤立點(diǎn)可能占據(jù)重要影響孤立點(diǎn)可能占據(jù)重要影響 may dominate presentationn傾斜的數(shù)據(jù)處理不好傾斜的數(shù)據(jù)處理不好.n等頻剖分等頻剖分 (frequency) /等深等深equi-depth :n分成分成n個(gè)區(qū)間個(gè)區(qū)間, 每一個(gè)含近似相同數(shù)目的樣本每一個(gè)含

11、近似相同數(shù)目的樣本nGood data scalingn類別屬性可能會(huì)非常棘手類別屬性可能會(huì)非常棘手.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: -

12、Bin 1: 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, 3415聚類分析聚類分析16Regressionxyy = x + 1X1Y1Y117數(shù)據(jù)清理作為一個(gè)過(guò)程數(shù)據(jù)清理作為一個(gè)過(guò)程n數(shù)據(jù)偏差檢測(cè)數(shù)據(jù)偏差檢測(cè) Data discrepancy detectionn使用元數(shù)據(jù)使用元數(shù)據(jù)(數(shù)據(jù)性質(zhì)的知識(shí)數(shù)據(jù)性質(zhì)的知識(shí))(e.g.,領(lǐng)域

13、領(lǐng)域, 長(zhǎng)度范圍長(zhǎng)度范圍,從屬?gòu)膶? 分布分布)n檢查字段過(guò)載檢查字段過(guò)載 field overloading n檢查唯一性規(guī)則檢查唯一性規(guī)則, 連續(xù)性規(guī)則連續(xù)性規(guī)則,空值規(guī)則空值規(guī)則n使用商業(yè)工具使用商業(yè)工具n數(shù)據(jù)清洗數(shù)據(jù)清洗Data scrubbing: 使用簡(jiǎn)單的領(lǐng)域知識(shí)使用簡(jiǎn)單的領(lǐng)域知識(shí)(e.g., 郵編郵編, 拼寫(xiě)檢拼寫(xiě)檢查查) 檢查并糾正錯(cuò)誤檢查并糾正錯(cuò)誤n數(shù)據(jù)審計(jì)數(shù)據(jù)審計(jì) Data auditing: 通過(guò)分析數(shù)據(jù)發(fā)現(xiàn)規(guī)則和聯(lián)系發(fā)現(xiàn)違規(guī)通過(guò)分析數(shù)據(jù)發(fā)現(xiàn)規(guī)則和聯(lián)系發(fā)現(xiàn)違規(guī)者者(孤立點(diǎn)孤立點(diǎn))n數(shù)據(jù)遷移和集成數(shù)據(jù)遷移和集成n數(shù)據(jù)遷移工具數(shù)據(jù)遷移工具Data migration too

14、ls:允許指定轉(zhuǎn)換允許指定轉(zhuǎn)換n提取提取/變換變換/裝入工具裝入工具ETL (Extraction/Transformation/Loading) tools: 允許用戶通過(guò)圖形用戶界面指定變換允許用戶通過(guò)圖形用戶界面指定變換n整合兩個(gè)過(guò)程整合兩個(gè)過(guò)程n兩個(gè)過(guò)程迭代和交互執(zhí)行兩個(gè)過(guò)程迭代和交互執(zhí)行(e.g., Potters Wheels)18第第2章章: 數(shù)據(jù)預(yù)處理數(shù)據(jù)預(yù)處理n為什么預(yù)處理數(shù)據(jù)為什么預(yù)處理數(shù)據(jù)?n數(shù)據(jù)清理數(shù)據(jù)清理 n數(shù)據(jù)集成數(shù)據(jù)集成n數(shù)據(jù)歸約數(shù)據(jù)歸約n離散化和概念分層產(chǎn)生離散化和概念分層產(chǎn)生n小結(jié)小結(jié)19數(shù)據(jù)集成數(shù)據(jù)集成n數(shù)據(jù)集成數(shù)據(jù)集成 Data integration:

15、n合并多個(gè)數(shù)據(jù)源中的數(shù)據(jù)，存在一個(gè)一致的數(shù)據(jù)存儲(chǔ)中合并多個(gè)數(shù)據(jù)源中的數(shù)據(jù)，存在一個(gè)一致的數(shù)據(jù)存儲(chǔ)中n涉及涉及3個(gè)主要問(wèn)題：模式集成、冗余數(shù)據(jù)、沖突數(shù)據(jù)值個(gè)主要問(wèn)題：模式集成、冗余數(shù)據(jù)、沖突數(shù)據(jù)值n模式集成模式集成 Schema integration n例如例如., A.cust-id ？ B.cust-#n實(shí)體識(shí)別問(wèn)題實(shí)體識(shí)別問(wèn)題 Entity identification problem: n多個(gè)數(shù)據(jù)源的真實(shí)世界的實(shí)體的識(shí)別多個(gè)數(shù)據(jù)源的真實(shí)世界的實(shí)體的識(shí)別, e.g., Bill Clinton = William Clintonn集成不同來(lái)源的元數(shù)據(jù)集成不同來(lái)源的元數(shù)據(jù)n沖突數(shù)據(jù)值的檢測(cè)

16、和解決沖突數(shù)據(jù)值的檢測(cè)和解決n對(duì)真實(shí)世界的實(shí)體，其不同來(lái)源的屬性值可能不同對(duì)真實(shí)世界的實(shí)體，其不同來(lái)源的屬性值可能不同n原因原因:不同的表示不同的表示,不同尺度不同尺度,公制公制 vs. 英制英制20數(shù)據(jù)集成中冗余數(shù)據(jù)處理數(shù)據(jù)集成中冗余數(shù)據(jù)處理n冗余數(shù)據(jù)冗余數(shù)據(jù)Redundant data （集成多個(gè)數(shù)據(jù)庫(kù)時(shí)出（集成多個(gè)數(shù)據(jù)庫(kù)時(shí)出現(xiàn)）現(xiàn)）n目標(biāo)識(shí)別：同一個(gè)屬性在不同的數(shù)據(jù)庫(kù)中有不同的名稱目標(biāo)識(shí)別：同一個(gè)屬性在不同的數(shù)據(jù)庫(kù)中有不同的名稱n衍生數(shù)據(jù)：一個(gè)屬性值可由其他表的屬性推導(dǎo)出衍生數(shù)據(jù)：一個(gè)屬性值可由其他表的屬性推導(dǎo)出, e.g.,年收入年收入n相關(guān)分析相關(guān)分析 correlation ana

17、lysis /協(xié)方差分析協(xié)方差分析covariance analysisn可用于檢測(cè)冗余數(shù)據(jù)可用于檢測(cè)冗余數(shù)據(jù)n小心的集成多個(gè)來(lái)源的數(shù)據(jù)可以幫助降低和避免結(jié)果數(shù)據(jù)小心的集成多個(gè)來(lái)源的數(shù)據(jù)可以幫助降低和避免結(jié)果數(shù)據(jù)集中的冗余和不一致，提高數(shù)據(jù)挖掘的速度和質(zhì)量集中的冗余和不一致，提高數(shù)據(jù)挖掘的速度和質(zhì)量21相關(guān)分析相關(guān)分析 (數(shù)值數(shù)據(jù)數(shù)值數(shù)據(jù))nCorrelation coefficient (also called Pearsons product moment coefficient)n相關(guān)系數(shù)（皮爾遜相關(guān)系數(shù)）相關(guān)系數(shù)（皮爾遜相關(guān)系數(shù)）n元組個(gè)數(shù)元組個(gè)數(shù), 和和 屬性屬性A和和B上的平均值上

18、的平均值, A and B分別為各自標(biāo)準(zhǔn)差，分別為各自標(biāo)準(zhǔn)差， (aibi) is the AB叉積叉積 cross-product之和之和.nIf rA,B 0, A and B 正相關(guān)正相關(guān) (As values increase as Bs). 值越大相關(guān)程度值越大相關(guān)程度越高越高.nrA,B = 0: 不相關(guān)不相關(guān); rAB 0, 則則A 和和B 同時(shí)傾向于大于期望值同時(shí)傾向于大于期望值.n負(fù)covariance: If CovA,B 0.26相關(guān)分析相關(guān)分析 (名義數(shù)據(jù)名義數(shù)據(jù)Nominal Data)n2 (chi-square) test 開(kāi)方檢驗(yàn)開(kāi)方檢驗(yàn)nij是是(ai,bj)

19、的觀測(cè)頻度（實(shí)際計(jì)數(shù)）的觀測(cè)頻度（實(shí)際計(jì)數(shù)）neij是是(ai,bj)的期望頻度的期望頻度nN數(shù)據(jù)元組的個(gè)數(shù)數(shù)據(jù)元組的個(gè)數(shù)屬屬A性性a1a2i acb1Bb2j br(A=ai,B=bj)rjijijijciee1212)(NbBcountaAcountejiij)(*)(n2 值越大值越大,相關(guān)的可能越大相關(guān)的可能越大n對(duì)對(duì) 2 值貢獻(xiàn)最大的項(xiàng)，其值貢獻(xiàn)最大的項(xiàng)，其實(shí)際值與期望值相差最大的實(shí)際值與期望值相差最大的相相n相關(guān)不意味著因果關(guān)系相關(guān)不意味著因果關(guān)系27Chi-Square 卡方值計(jì)算卡方值計(jì)算: 例子例子n2 (chi-square) 計(jì)算計(jì)算(括號(hào)中的值為期望計(jì)值，由兩個(gè)類別的分

20、布數(shù)據(jù)計(jì)括號(hào)中的值為期望計(jì)值，由兩個(gè)類別的分布數(shù)據(jù)計(jì)算得到算得到)n結(jié)果表明結(jié)果表明like_fiction 和和play_chess 關(guān)聯(lián)關(guān)聯(lián)93.507840)8401000(360)360200(210)21050(90)90250(22222Play chessNot play chessSum (row)看小說(shuō)看小說(shuō)250(90)200(360)450不看小說(shuō)不看小說(shuō)50(210)1000(840)1050Sum(col.)30012001500901500300*450)(*)(11Ncountcounte下棋看小說(shuō)28數(shù)據(jù)變換數(shù)據(jù)變換Data Transformationn光滑光

21、滑: 去掉噪音，技術(shù)：分箱、回歸、聚類去掉噪音，技術(shù)：分箱、回歸、聚類n聚集聚集Aggregation:匯總匯總, 數(shù)據(jù)立方體構(gòu)造數(shù)據(jù)立方體構(gòu)造n數(shù)據(jù)泛化數(shù)據(jù)泛化Generalization:概念分層概念分層n規(guī)范化規(guī)范化Normalization:按比例縮放到一個(gè)具體區(qū)間按比例縮放到一個(gè)具體區(qū)間n最小最小-最大規(guī)范化最大規(guī)范化nz-score 規(guī)范化規(guī)范化n小數(shù)定標(biāo)規(guī)范化小數(shù)定標(biāo)規(guī)范化n屬性屬性Attribute/特征特征feature 構(gòu)造構(gòu)造n從給定的屬性構(gòu)造新屬性從給定的屬性構(gòu)造新屬性n機(jī)器學(xué)習(xí)中稱為：特征構(gòu)造機(jī)器學(xué)習(xí)中稱為：特征構(gòu)造數(shù)據(jù)規(guī)約29規(guī)范化數(shù)據(jù)的方法規(guī)范化數(shù)據(jù)的方法n最小最

22、小-最大規(guī)范化最大規(guī)范化 min-max normalizationn新數(shù)據(jù)可能新數(shù)據(jù)可能“越界越界”nz-score normalizationnnormalization by decimal scalingn移動(dòng)屬性移動(dòng)屬性A的小數(shù)點(diǎn)位置的小數(shù)點(diǎn)位置(移動(dòng)位數(shù)依賴于屬性移動(dòng)位數(shù)依賴于屬性A的最大值的最大值)AAAAAAminnewminnewmaxnewminmaxminvv_)_(A標(biāo)準(zhǔn)差均值A(chǔ)vvjvv10J為使得 Max(| |)最后的集合: A1, A4, A6維度規(guī)約維度規(guī)約-決策樹(shù)規(guī)約決策樹(shù)規(guī)約3939維度規(guī)約維度規(guī)約-屬性屬性/特征產(chǎn)生特征產(chǎn)生nFeature Genera

23、tion 產(chǎn)生新的屬性，其可以比產(chǎn)生新的屬性，其可以比原始原始屬性屬性更有效地更有效地表示數(shù)據(jù)的重要信息。表示數(shù)據(jù)的重要信息。n三個(gè)一般方法三個(gè)一般方法:n屬性提取屬性提取 Attribute extractionn特定領(lǐng)域的特定領(lǐng)域的n映射數(shù)據(jù)到新空間映射數(shù)據(jù)到新空間nE.g., 傅立葉變換傅立葉變換, wavelet transformation, 流形方法流形方法( manifold approaches)n屬性構(gòu)造屬性構(gòu)造n組合特征組合特征n數(shù)據(jù)離散化數(shù)據(jù)離散化 Data discretization4040 x2x1e主成分分析主成分分析 (PCA)nprincipal compon

24、ent analysis，K-L變換變換n找到一個(gè)投影，其能表示數(shù)據(jù)的最大變化找到一個(gè)投影，其能表示數(shù)據(jù)的最大變化n原始數(shù)據(jù)投影到一個(gè)更小的空間中，導(dǎo)致維度減少原始數(shù)據(jù)投影到一個(gè)更小的空間中，導(dǎo)致維度減少. n發(fā)現(xiàn)的協(xié)方差矩陣的特征向量，用這些特征向量定義新發(fā)現(xiàn)的協(xié)方差矩陣的特征向量，用這些特征向量定義新的空間的空間4141n給定給定 p維維空間中的空間中的N個(gè)點(diǎn)個(gè)點(diǎn), 找到找到 k p 個(gè)正交向量個(gè)正交向量 (principal components) 可以很好表示原始數(shù)據(jù)的可以很好表示原始數(shù)據(jù)的 n歸范化輸入數(shù)據(jù)歸范化輸入數(shù)據(jù): 每個(gè)屬性值位于相同的區(qū)間內(nèi)每個(gè)屬性值位于相同的區(qū)間內(nèi)n計(jì)算計(jì)

25、算 k 個(gè)標(biāo)準(zhǔn)正交向量個(gè)標(biāo)準(zhǔn)正交向量, i.e., principal componentsn每個(gè)輸入的點(diǎn)是這每個(gè)輸入的點(diǎn)是這k 個(gè)主成分的線性組合個(gè)主成分的線性組合nThe principal components are sorted in order of decreasing “significance” or strengthnSince the components are sorted, the size of the data can be reduced by eliminating the weak components(i.e., using the strongest

26、principal components, it is possible to reconstruct a good approximation of the original data)nWorks for numeric data only主成分分析主成分分析 (Steps)42X1X2Y1Y2Principal Component Analysis43數(shù)值規(guī)約數(shù)值規(guī)約n選擇替代的、選擇替代的、“較小的較小的”數(shù)據(jù)表示形式數(shù)據(jù)表示形式n參數(shù)方法參數(shù)方法n假設(shè)數(shù)據(jù)適合某個(gè)模型，估計(jì)模型參數(shù)，僅存儲(chǔ)的參假設(shè)數(shù)據(jù)適合某個(gè)模型，估計(jì)模型參數(shù)，僅存儲(chǔ)的參數(shù)，并丟棄數(shù)據(jù)（孤立點(diǎn)除外）數(shù)，并丟棄數(shù)據(jù)（孤

27、立點(diǎn)除外）n對(duì)數(shù)線性模型對(duì)數(shù)線性模型:n基于一個(gè)較小的維組合的子集來(lái)估計(jì)基于一個(gè)較小的維組合的子集來(lái)估計(jì) 離散屬性的離散屬性的多維空間中每個(gè)點(diǎn)的概率多維空間中每個(gè)點(diǎn)的概率n非參數(shù)方法非參數(shù)方法n不假定模型不假定模型nhistograms, clustering, sampling 44回歸和對(duì)數(shù)線性模型回歸和對(duì)數(shù)線性模型n線性回歸線性回歸: 數(shù)據(jù)擬合到一條直線上數(shù)據(jù)擬合到一條直線上n通常使用最小二乘法擬合通常使用最小二乘法擬合n多元線性回歸多元線性回歸n允許響應(yīng)變量允許響應(yīng)變量Y表示為多個(gè)預(yù)測(cè)變量的函數(shù)表示為多個(gè)預(yù)測(cè)變量的函數(shù)n對(duì)數(shù)線性模型對(duì)數(shù)線性模型: n近似離散的多維概率分布近似離散的多維

28、概率分布4545回歸分析回歸分析n研究因變量因變量/響應(yīng)變量響應(yīng)變量Y(dependent variable/response variable) 對(duì)個(gè)或多個(gè)自變量自變量/解釋變量解釋變量(independent variable / explanatory variable)的相依關(guān)系的方法的統(tǒng)稱n參數(shù)需要估計(jì)以最好的擬合給定參數(shù)需要估計(jì)以最好的擬合給定的數(shù)據(jù)的數(shù)據(jù)n絕大多數(shù)情況絕大多數(shù)情況“最好的擬合最好的擬合”是由是由最小二乘法最小二乘法(least squares method)實(shí)實(shí)現(xiàn)現(xiàn), 其他的方法也有其他的方法也有n用于預(yù)測(cè)（包括時(shí)用于預(yù)測(cè)（包括時(shí)間序列數(shù)據(jù)的預(yù)間序列數(shù)據(jù)的預(yù)測(cè)），

29、推斷，假設(shè)測(cè)），推斷，假設(shè)檢驗(yàn)和因果關(guān)系的檢驗(yàn)和因果關(guān)系的建模建模yxy = x + 1X1Y1Y146線性回歸線性回歸-用于預(yù)測(cè)用于預(yù)測(cè)Y: -diameter at breast height(DBH) X: - Age0123456789101112Y?1.01.01.56.09.010.5 1116.5 9.58.012.5 12.5X3411121528455257758188939747線性回歸線性回歸(cont.)nGiven x, construct the linear regression model for y against x as:nLeast squares es

30、timation of y given variable x is:48多元線性回歸多元線性回歸n響應(yīng)變量響應(yīng)變量: w，自變量，自變量: A1,A2,Ak.n“5” 樣本數(shù)目樣本數(shù)目) 1 (21kAAAw49直方圖直方圖Histogramsn把數(shù)據(jù)劃分成不相交的子把數(shù)據(jù)劃分成不相交的子集或桶集或桶n一維時(shí)可用動(dòng)態(tài)規(guī)劃優(yōu)化一維時(shí)可用動(dòng)態(tài)規(guī)劃優(yōu)化構(gòu)建構(gòu)建n涉及量化問(wèn)題涉及量化問(wèn)題051015202530354010000200003000040000500006000070000800009000010000050聚類聚類Clusteringn將對(duì)象劃分成集將對(duì)象劃分成集/簇簇, 用簇的表示替

31、換實(shí)際數(shù)據(jù)用簇的表示替換實(shí)際數(shù)據(jù)n技術(shù)的有效性依賴于數(shù)據(jù)的質(zhì)量技術(shù)的有效性依賴于數(shù)據(jù)的質(zhì)量n使用層次聚類，并多維索引樹(shù)結(jié)構(gòu)存放使用層次聚類，并多維索引樹(shù)結(jié)構(gòu)存放n非常多的聚類算法和定義非常多的聚類算法和定義51抽樣抽樣Samplingn抽樣抽樣: 獲得一個(gè)小的樣本集獲得一個(gè)小的樣本集s來(lái)表示整個(gè)數(shù)據(jù)集來(lái)表示整個(gè)數(shù)據(jù)集 Nn允許一個(gè)挖掘算法運(yùn)行復(fù)雜度子線性于樣本大小允許一個(gè)挖掘算法運(yùn)行復(fù)雜度子線性于樣本大小n關(guān)鍵原則關(guān)鍵原則:選擇一個(gè)有代表性的數(shù)據(jù)子集選擇一個(gè)有代表性的數(shù)據(jù)子集n數(shù)據(jù)偏斜時(shí)簡(jiǎn)單隨機(jī)抽樣的性能很差數(shù)據(jù)偏斜時(shí)簡(jiǎn)單隨機(jī)抽樣的性能很差n發(fā)展適應(yīng)抽樣方法：分層抽樣發(fā)展適應(yīng)抽樣方法：分層抽樣

32、 nNote: Sampling may not reduce database I/Os (page at a time)52抽樣類型抽樣類型 Types of Samplingn簡(jiǎn)單隨機(jī)抽樣 Simple random samplingn相同的概率選擇任何特定項(xiàng)目相同的概率選擇任何特定項(xiàng)目n無(wú)放回抽樣 Sampling without replacementnOnce an object is selected, it is removed from the populationn放回抽樣Sampling with replacementn一個(gè)被抽中的目標(biāo)不從總體中去除一個(gè)被抽中的目標(biāo)不從

33、總體中去除n分層抽樣 Stratified sampling: n把數(shù)據(jù)分成不相交部分把數(shù)據(jù)分成不相交部分(層層), 然后從每個(gè)層抽樣然后從每個(gè)層抽樣(按比例按比例/大大約相同比例的數(shù)據(jù)約相同比例的數(shù)據(jù)) n偏斜數(shù)據(jù)偏斜數(shù)據(jù)53Sampling: With or without ReplacementSRSWOR(simple random sample without replacement)SRSWRRaw Data54Sampling: Cluster or Stratified SamplingRaw Data Cluster/Stratified Sample55第第2章章: 數(shù)據(jù)預(yù)

34、處理數(shù)據(jù)預(yù)處理n為什么預(yù)處理數(shù)據(jù)為什么預(yù)處理數(shù)據(jù)?n數(shù)據(jù)清理數(shù)據(jù)清理 n數(shù)據(jù)集成數(shù)據(jù)集成n數(shù)據(jù)歸約數(shù)據(jù)歸約n離散化和概念分層產(chǎn)生離散化和概念分層產(chǎn)生n小結(jié)小結(jié)56離散化離散化 Discretization和概念分成和概念分成n三種類型屬性三種類型屬性:n名義名義 values from an unordered set， color, professionn順序數(shù)順序數(shù) values from an ordered set , e.g., military or academic rank n連續(xù)連續(xù) real numbersn離散化離散化 Discretization: 把連續(xù)屬性的區(qū)域分成

35、區(qū)間把連續(xù)屬性的區(qū)域分成區(qū)間n區(qū)間標(biāo)號(hào)可以代替實(shí)際數(shù)據(jù)值區(qū)間標(biāo)號(hào)可以代替實(shí)際數(shù)據(jù)值 n利用離散化減少數(shù)據(jù)量利用離散化減少數(shù)據(jù)量n有監(jiān)督有監(jiān)督 vs. 無(wú)監(jiān)督：是否使用類的信息無(wú)監(jiān)督：是否使用類的信息n某個(gè)屬性上可以遞歸離散化某個(gè)屬性上可以遞歸離散化n分裂分裂 Split (top-down) vs. 合并合并merge (bottom-up)n自頂向下：由一個(gè)自頂向下：由一個(gè)/幾個(gè)點(diǎn)開(kāi)始遞歸劃分整個(gè)屬性區(qū)間幾個(gè)點(diǎn)開(kāi)始遞歸劃分整個(gè)屬性區(qū)間n遞歸離散化屬性，產(chǎn)生屬性值分層遞歸離散化屬性，產(chǎn)生屬性值分層/多分辨率劃分：多分辨率劃分：概念分層概念分層57數(shù)值數(shù)據(jù)離散化數(shù)值數(shù)據(jù)離散化/概念分層概念分層n

36、分箱分箱 Binning(Top-down split, unsupervised)n直方圖（直方圖（Top-down split, unsupervised）n聚類聚類 (unsupervised, top-down split or bottom-up merge)n基于基于 2 分析的區(qū)間合并分析的區(qū)間合并(unsupervised, bottom-up merge)n基于熵基于熵 Entropy-based discretizationn根據(jù)自然劃分根據(jù)自然劃分58不用類別不用類別(Binning vs. Clustering) DataEqual interval width (bi

37、nning)Equal frequency (binning)K-means clustering leads to better results59基于熵基于熵Entropy的離散化的離散化60 Chi-merge離散化離散化nChi-merge: 2-based discretizationn有監(jiān)督有監(jiān)督: use class informationn自低向上自低向上: find the best neighboring intervals (具有相似的類具有相似的類別分布別分布, i.e., low 2 values) to mergen遞歸地合并遞歸地合并, until a prede

38、fined stopping condition61由自然劃分離散化由自然劃分離散化n3-4-5 規(guī)則規(guī)則n如果最高有效位包含如果最高有效位包含 3, 6, 7 or 9 個(gè)不同的值個(gè)不同的值, partition the range into 3 個(gè)等寬區(qū)間（個(gè)等寬區(qū)間（7：2-3-2分成分成3個(gè)區(qū)間）個(gè)區(qū)間）n2, 4, or 8 不同的值不同的值, 區(qū)域分成區(qū)域分成 4 個(gè)等寬區(qū)間個(gè)等寬區(qū)間n1, 5, or 10 不同的值不同的值, 區(qū)域分成區(qū)域分成5 個(gè)等寬區(qū)間個(gè)等寬區(qū)間n類似地，逐層使用此規(guī)則類似地，逐層使用此規(guī)則62分類數(shù)據(jù)的概念分層分類數(shù)據(jù)的概念分層 Categorical D

39、atan用戶用戶/專家在模式級(jí)顯式地指定屬性的偏序?qū)＜以谀Ｊ郊?jí)顯式地指定屬性的偏序nstreetcitystatecountryn通過(guò)顯式數(shù)據(jù)分組說(shuō)明分層通過(guò)顯式數(shù)據(jù)分組說(shuō)明分層n厄本，香檳，芝加哥厄本，香檳，芝加哥Illinoisn只說(shuō)明屬性集只說(shuō)明屬性集 n系統(tǒng)自動(dòng)產(chǎn)生屬性偏序，根據(jù)系統(tǒng)自動(dòng)產(chǎn)生屬性偏序，根據(jù) 每個(gè)屬性下不同值的數(shù)據(jù)每個(gè)屬性下不同值的數(shù)據(jù)n啟發(fā)式規(guī)則：相比低層，高層概念的屬性通常有較少取值啟發(fā)式規(guī)則：相比低層，高層概念的屬性通常有較少取值nE.g., street city state countryn只說(shuō)明部分屬性值只說(shuō)明部分屬性值63自動(dòng)產(chǎn)生概念分層自動(dòng)產(chǎn)生概念分層nS

40、ome concept hierarchies can be automatically generated based on the analysis of the number of distinct values per attribute in the given data set n含不同值最多的屬性放在層次的最低層含不同值最多的屬性放在層次的最低層nNote: Exceptionweekday, month, quarter, yearcountryprovince_or_ statecitystreet15 distinct values65 distinct values356

41、7 distinct values674,339 distinct values64SummarynData preparation is a big issue for both warehousing and miningnData preparation includesnData cleaning and data integrationnData reduction and feature selectionnDiscretizationnA lot a methods have been developed but still an active area of researchD

42、ata Reduction, Transformation, IntegrationnData QualitynMajor Tasks in Data PreprocessingnData Cleaning and Data IntegrationnData Cleaningni. Missing Data and Misguided Missing Datanii. Noisy Dataniii. Data Cleaning as a ProcessnData Integration MethodsnData ReductionnData Reduction StrategiesnDimen

43、sionality Reductionni. Principal Component analysisnii. Feature Subset Selectionniii. Feature CreationnNumerosity Reductionni. Parametric Data Reduction: Regression and Log-Linear Modelsnii. Mapping Data to a New Space: Wavelet Transformationniii. Data Cube aggregationniv. Data Compressionnv. Histogram analysisnvi. Clusteringnvii. Sampling: Sampling without Replacement, Stratified SamplingnData Transformation and Data DiscretizationnData Transformation: NormalizationnData Discretization Methodsni. Binningnii. Cluster Analysisniii. Discretization Using Class Labels: Entropy-Based Di