第四章 數(shù)據(jù)預(yù)處理.ppt

1、 數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘,主講：王名揚(yáng) 信息與計(jì)算機(jī)工程學(xué)院,2,引 言,目前，數(shù)據(jù)挖掘的研究工作大都集中在算法的探討而忽視對(duì)數(shù)據(jù)處理的研究。事實(shí)上，數(shù)據(jù)預(yù)處理對(duì)數(shù)據(jù)挖掘十分重要，一些成熟的算法都對(duì)其處理的數(shù)據(jù)集合有一定的要求：比如數(shù)據(jù)的完整性好，冗余性小，屬性的相關(guān)性小等。 高質(zhì)量的決策來(lái)自高質(zhì)量的數(shù)據(jù)，因此數(shù)據(jù)預(yù)處理是整個(gè)數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)過(guò)程中的一個(gè)重要步驟。,數(shù)據(jù)挖掘: 數(shù)據(jù)庫(kù)中的知識(shí)挖掘(KDD),數(shù)據(jù)挖掘知識(shí)挖掘的核心,數(shù)據(jù)清洗,數(shù)據(jù)集成,數(shù)據(jù)庫(kù),數(shù)據(jù)倉(cāng)庫(kù),Knowledge,任務(wù)相關(guān)數(shù)據(jù),選擇,數(shù)據(jù)挖掘,模式評(píng)估,第 4 章,數(shù)據(jù)預(yù)處理,5,數(shù)據(jù)預(yù)處理的重要性,數(shù)據(jù)預(yù)處理是數(shù)據(jù)挖掘的

2、重要一環(huán)，而且必不可少。要使挖掘算法挖掘出有效的知識(shí)，必須為其提供干凈，準(zhǔn)確，簡(jiǎn)潔的數(shù)據(jù)。 然而，當(dāng)今現(xiàn)實(shí)世界中的數(shù)據(jù)庫(kù)極易受到噪聲數(shù)據(jù)、空缺數(shù)據(jù)和不一致性數(shù)據(jù)的侵?jǐn)_，多數(shù)為“臟”數(shù)據(jù)。,1）雜亂性：如命名規(guī)則的不同 如性別： A數(shù)據(jù)庫(kù) male=1 , female=2 B數(shù)據(jù)庫(kù) male=男 ，female=女 C數(shù)據(jù)庫(kù) male=M , female=F,數(shù)據(jù)預(yù)處理的重要性,2）重復(fù)性：同一客觀事物在數(shù)據(jù)庫(kù)中存在兩個(gè)以上相同的物理描述。 假設(shè)某周刊有100000個(gè)訂戶，郵件列表中0.1%的記錄是重復(fù)的，主要是因?yàn)橥粋€(gè)客戶的名字可能有不同的寫法，如：Jon Doe和John Doe。 因

3、此，每周需要印刷和郵寄100份額外的刊物，假設(shè)每份刊物每周的郵寄和印刷費(fèi)用是兩美元，公司每年將至少浪費(fèi)1萬(wàn)美元以上。,數(shù)據(jù)預(yù)處理的重要性,3）不完整性：由于實(shí)際系統(tǒng)設(shè)計(jì)時(shí)存在的缺陷以及使用過(guò)程中的一些人為因素，數(shù)據(jù)記錄可能會(huì)出現(xiàn)數(shù)據(jù)值的丟失或不確定。 原因可能有： （1）有些屬性的內(nèi)容有時(shí)沒(méi)有 （家庭收入，參與銷售事務(wù)數(shù)據(jù)中的顧客信息） （2）有些數(shù)據(jù)當(dāng)時(shí)被認(rèn)為是不必要的 （3）由于誤解或檢測(cè)設(shè)備失靈導(dǎo)致相關(guān)數(shù)據(jù)沒(méi)有記錄下來(lái) （4）與其它記錄內(nèi)容不一致而被刪除 （5）忽略了歷史數(shù)據(jù)或?qū)?shù)據(jù)的修改,數(shù)據(jù)預(yù)處理的重要性,4）噪聲數(shù)據(jù)：數(shù)據(jù)中存在著錯(cuò)誤或異常（偏離期望值） 如：血壓和身高為0就是明顯

4、的錯(cuò)誤 噪聲數(shù)據(jù)的產(chǎn)生原因： 數(shù)據(jù)采集設(shè)備有問(wèn)題； 在數(shù)據(jù)錄入過(guò)程發(fā)生人為或計(jì)算機(jī)錯(cuò)誤； 數(shù)據(jù)傳輸過(guò)程中出現(xiàn)錯(cuò)誤； 由于命名規(guī)則或數(shù)據(jù)代碼不同而引起的不一致。,數(shù)據(jù)預(yù)處理的重要性,數(shù)據(jù)清理（清洗） -去掉數(shù)據(jù)中的噪聲，糾正不一致 數(shù)據(jù)集成 -將多個(gè)數(shù)據(jù)源合并成一致的數(shù)據(jù)存儲(chǔ)，構(gòu)成一個(gè)完整的數(shù)據(jù)集，如數(shù)據(jù)倉(cāng)庫(kù)。 數(shù)據(jù)變換（轉(zhuǎn)換） -將一種格式的數(shù)據(jù)轉(zhuǎn)換為另一格式的數(shù)據(jù)(如規(guī)范化) 數(shù)據(jù)歸約（消減） -通過(guò)聚集、刪除冗余屬性或聚類等方法來(lái)壓縮數(shù)據(jù)。,數(shù)據(jù)預(yù)處理的常見方法,11,注意： 上述的各種數(shù)據(jù)預(yù)處理方法，并不是相互獨(dú)立的，而是相互關(guān)聯(lián)的，如消除數(shù)據(jù)冗余既可以看成是一種形式的數(shù)據(jù)清洗，也可以看

5、成是一種數(shù)據(jù)歸約（消減）。,4.1 數(shù)據(jù)清洗 4.2 數(shù)據(jù)集成和變換 4.3 數(shù)據(jù)歸約 4.4 數(shù)據(jù)離散化和概念分層*,第 4 章,14,學(xué)習(xí)目的,掌握數(shù)據(jù)清洗的處理方法（空缺、噪聲、不一致）； 掌握各種數(shù)據(jù)歸約的方法； 理解數(shù)據(jù)離散化的方法。,4.1 數(shù)據(jù)清洗,現(xiàn)實(shí)世界的數(shù)據(jù)一般是臟的、不完整的和不一致的。而數(shù)據(jù)清洗試圖填充空缺的值、識(shí)別孤立點(diǎn)、消除噪聲，并糾正數(shù)據(jù)中的不一致性。因此，從如下幾個(gè)方面介紹： （1）空缺值； （2）噪聲數(shù)據(jù)； （3）不一致數(shù)據(jù)。,1. 空缺值的處理？,17,空缺值,數(shù)據(jù)并不總是完整的 數(shù)據(jù)庫(kù)表中，很多條記錄的對(duì)應(yīng)字段可能沒(méi)有相應(yīng)值，比如銷售表中的顧客收入 引起空

6、缺值的原因 設(shè)備異常 與其他已有數(shù)據(jù)不一致而被刪除 因?yàn)檎`解而沒(méi)有被輸入的數(shù)據(jù) 在輸入時(shí)，有些數(shù)據(jù)因?yàn)榈貌坏街匾暥鴽](méi)有被輸入 對(duì)數(shù)據(jù)的改變沒(méi)有進(jìn)行日志記載 空缺值要經(jīng)過(guò)推斷而補(bǔ)上。,如何處理空缺值,1）忽略該元組： 若一條記錄中有屬性值被遺漏了，則將該記錄排除在數(shù)據(jù)挖掘之外； 尤其當(dāng)類標(biāo)號(hào)缺少時(shí)通常這樣做（假定挖掘任務(wù)涉及分類或描述)； 但是，當(dāng)某類屬性的空缺值所占百分比很大時(shí)，直接忽略元組會(huì)使挖掘性能變得非常差。,如何處理空缺值,2）人工填寫空缺值： 工作量大，可行性低 3）使用屬性的平均值填充空缺值： 如所有顧客的平均收入為$1000，則使用該值替換income中的空缺值。,如何處理空缺值

7、,4）使用一個(gè)全局變量填充空缺值： 如：將空缺的屬性值用同一個(gè)常數(shù)(如“Unknown”)替換。 如果空缺值都用“Unknown”替換，當(dāng)空缺值較多時(shí)，挖掘程序可能誤以為它們形成了一個(gè)有趣的概念，因?yàn)樗鼈兌季哂邢嗤闹怠癠nknown”。 因此，盡管該方法簡(jiǎn)單，我們并不推薦它。,如何處理空缺值,5）使用與給定元組屬同一類的所有樣本的平均值： 適用于分類數(shù)據(jù)挖掘； 如將顧客按信用度分類，則用具有相同信用度的顧客的平均收入替換income中的空缺值。 6）使用最可能的值填充空缺值（最常用）： 可以利用回歸、貝葉斯計(jì)算公式或判定樹歸納確定，推斷出該條記錄特定屬性最大可能的取值； 如，利用數(shù)據(jù)集中其他

8、顧客的屬性，構(gòu)造一棵判定樹，預(yù)測(cè)income的空缺值。,2. 噪聲數(shù)據(jù)的處理？,噪聲數(shù)據(jù),噪聲(noise) ：是一個(gè)測(cè)量變量中的隨機(jī)錯(cuò)誤或偏差 引起噪聲數(shù)據(jù)的原因 數(shù)據(jù)收集工具的問(wèn)題 數(shù)據(jù)輸入錯(cuò)誤 數(shù)據(jù)傳輸錯(cuò)誤 技術(shù)限制 命名規(guī)則的不一致,如何處理噪聲數(shù)據(jù),1）分箱 (binning): 分箱方法通過(guò)考察“鄰居”(即周圍的值)來(lái)平滑存儲(chǔ)數(shù)據(jù)的值。 存儲(chǔ)的值被分布到一些“桶”或箱中。由于分箱方法參考相鄰的值，因此它進(jìn)行局部平滑。,如何處理噪聲數(shù)據(jù),分箱的步驟： 首先排序數(shù)據(jù)，并將它們分到等深（等寬）的箱中； 然后可以按箱的平均值、按箱中值或者按箱的邊界等進(jìn)行平滑。 按箱的平均值平滑：箱中每一個(gè)

9、值被箱中的平均值替換 按箱的中值平滑：箱中的每一個(gè)值被箱中的中值替換 按箱的邊界平滑：箱中的最大和最小值被視為箱邊界，箱中的每一個(gè)值被最近的邊界值替換。,如何處理噪聲數(shù)據(jù), 等深分箱 (binning): 按記錄數(shù)進(jìn)行分箱，每箱具有相同的記錄數(shù)，每箱的記錄數(shù)稱為箱的權(quán)重，也稱箱子的深度。,示例： 已知一組價(jià)格數(shù)據(jù)：15,21,24,21,25,4,8,34,28 現(xiàn)用等深（深度為3）分箱方法對(duì)其進(jìn)行平滑，以對(duì)數(shù)據(jù)中的噪聲進(jìn)行處理。,思考：根據(jù)bin中值進(jìn)行平滑的結(jié)果？,結(jié)果： Bin1：8、8、8； Bin2：21、21、21； Bin3：28、28、28,在該例中，price數(shù)據(jù)首先被劃分并

10、存人等深的箱中(深度3)。 對(duì)于按箱平均值平滑，箱中每一個(gè)值被箱中的平均值替換。例如，箱1中的值4，8和15的平均值是9；這樣，該箱中的每一個(gè)值被替換為9。 對(duì)于按箱邊界平滑，箱中的最大和最小值被視為箱邊界。箱中的每一個(gè)值被最近的邊界值替換。 類似地，可以使用按箱中值平滑。此時(shí)，箱中的每一個(gè)值被箱中的中值替換。,如何處理噪聲數(shù)據(jù),等寬分箱 (binning): 在整個(gè)屬性值的區(qū)間上平均分布，即每個(gè)箱的區(qū)間范圍設(shè)定為一個(gè)常量，稱為箱子的寬度。,示例： 已知一組價(jià)格數(shù)據(jù)：15,21,24,21,25,4,8,34,28 現(xiàn)用等寬（寬度為10）分箱方法對(duì)其進(jìn)行平滑，以對(duì)數(shù)據(jù)中的噪聲進(jìn)行處理。,結(jié)果：

11、 先排序：4，8，15，21，21，24，25，28，34 1）劃分為等寬度箱子 Bin1：4、8； Bin2：15、21、21、24、25； Bin3：28、34 2）根據(jù)均值進(jìn)行平滑 Bin1：6、6； Bin2：21、21、21、21、21； Bin3：31、31,3）根據(jù)中值進(jìn)行平滑 Bin1：6、6； Bin2：21、21、21、21、21； Bin3：31、31 4）根據(jù)邊界進(jìn)行平滑： Bin1：4、8； Bin2：15、25、25、25、25； Bin3：28、34,練習(xí)： 已知客戶收入屬性income排序后的值（人民幣元）：800，1000，1200，1500，1500，180

12、0，2000，2300，2500，2800，3000，3500，4000，4500，4800，5000 要求：分別用等深分箱方法(箱深為4）、等寬分箱方法（寬度為1000）對(duì)其進(jìn)行平滑，以對(duì)數(shù)據(jù)中的噪聲進(jìn)行處理。,（1）等深分箱結(jié)果： （1）首先，劃分為等深的箱： 箱1（800，1000，1200，1500）； 箱2（1500，1800，2000，2300）； 箱3（2500，2800，3000，3500）； 箱4（4000，4500，4800，5000） （2）按箱的平均值平滑，結(jié)果為： 箱1（1125，1125 ，1125 ，1125 ）； 箱2（1900，1900，1900，1900）；

13、 箱3（2950，2950，2950，2950）； 箱4（4575，4575 ，4575 ，4575 ）,（1）等深分箱結(jié)果： （2）按箱的中值平滑，結(jié)果為： 箱1（1100，1100 ，1100 ，1100 ）； 箱2（1900，1900，1900，1900）； 箱3（2900，2900，2900，2900）； 箱4（4650，4650 ，4650 ，4650 ） （2）按箱的邊界值平滑，結(jié)果為： 箱1（800，800，1500，1500）； 箱2（1500，1500，2300，2300）； 箱3（2500，2500，3500，3500）； 箱4（4000，4000，5000，5000）,（

14、2）等寬分箱結(jié)果： （1）首先，劃分為等寬的箱： 箱1（800，1000，1200，1500，1500，1800）； 箱2（2000，2300，2500，2800，3000）； 箱3（3500， 4000，4500 ）； 箱4（4800，5000） （2）按箱的平均值平滑，結(jié)果為： 箱1（1300，1300 ，1300 ，1300 ，1300 ，1300 ）； 箱2（2520，2520 ，2520 ，2520 ，2520 ）； 箱3（4000，4000 ，4000 ）； 箱4（4900，4900 ）,（2）等寬分箱結(jié)果： （1）按箱的中值平滑，結(jié)果為： 箱1（1350，1350 ，1350 ，

15、1350 ，1350 ，1350 ）； 箱2（2500，2500 ，2500 ，2500 ，2500 ）； 箱3（4000，4000 ，4000 ）； 箱4（4900，4900 ） （2）按箱的邊界值平滑，結(jié)果為： 箱1（800，800 ，800 ，1800 ，1800 ，1800 ）； 箱2（2000，2000 ，3000 ，3000 ，3000 ）； 箱3（3500，3500 ，4000 ）； 箱4（4800，5000）,如何處理噪聲數(shù)據(jù),2）聚類（Clustering）： 相似或相鄰近的數(shù)據(jù)聚合在一起形成各個(gè)聚類集合，而那些位于聚類集合之外的數(shù)據(jù)對(duì)象，被視為孤立點(diǎn)。 特點(diǎn)：直接形成簇并對(duì)

16、簇進(jìn)行描述，不需要任何先驗(yàn)知識(shí)。,通過(guò)聚類分析查找孤立點(diǎn)，消除噪聲,如何處理噪聲數(shù)據(jù),3）計(jì)算機(jī)和人工檢查結(jié)合 計(jì)算機(jī)檢測(cè)可疑數(shù)據(jù)，然后對(duì)它們進(jìn)行人工判斷 4）回歸 發(fā)現(xiàn)兩個(gè)相關(guān)的變量之間的變化模式，利用回歸分析方法所獲得的擬合函數(shù)，幫助平滑數(shù)據(jù)及除去噪聲。,許多數(shù)據(jù)平滑的方法也是涉及離散化的數(shù)據(jù)歸約方法。例如，上面介紹的分箱技術(shù)減少了每個(gè)屬性的不同值的數(shù)量。 另外，概念分層是一種數(shù)據(jù)離散化形式，也可以用于數(shù)據(jù)平滑。例如，price的概念分層可以把price的值映射到inexpensive，moderately_priced和expensive，從而減少了挖掘過(guò)程所處理的值的數(shù)量。,注意：,3

17、. 不一致數(shù)據(jù)的處理？,40,不一致數(shù)據(jù),處理不一致數(shù)據(jù)的方式： 人工更正 利用知識(shí)工程工具：如，如果知道屬性間的函數(shù)依賴關(guān)系，可以據(jù)此查找違反函數(shù)依賴的值。 數(shù)據(jù)字典：在將不同操作性數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行集成時(shí)，也會(huì)帶來(lái)數(shù)據(jù)的不一致。如：一個(gè)給定的屬性在不同的數(shù)據(jù)庫(kù)中可能具有不同的名字，如姓名在一個(gè)數(shù)據(jù)庫(kù)中為Bill，在另一個(gè)數(shù)據(jù)庫(kù)中可能為B。對(duì)此，可根據(jù)數(shù)據(jù)字典中提供的信息，消除不一致。,4.2 數(shù)據(jù)集成和變換,數(shù)據(jù)挖掘所需要的海量數(shù)據(jù)集往往涉及多個(gè)數(shù)據(jù)源，因此，在信息處理之前需要合并這些數(shù)據(jù)源存儲(chǔ)的數(shù)據(jù)。 如果原始數(shù)據(jù)的形式不適合信息處理算法的需要，就要進(jìn)行數(shù)據(jù)變換。 1）數(shù)據(jù)集成：將來(lái)自多

18、個(gè)數(shù)據(jù)源的數(shù)據(jù)合并到一起： 2）數(shù)據(jù)變換：對(duì)數(shù)據(jù)進(jìn)行規(guī)范化操作，將其轉(zhuǎn)換成適合于數(shù)據(jù)挖掘的形式。,1. 數(shù)據(jù)集成？,43,數(shù)據(jù)集成,數(shù)據(jù)集成 將多個(gè)數(shù)據(jù)源中的數(shù)據(jù)整合到一個(gè)一致的存儲(chǔ)中。 這些源可以是關(guān)系型數(shù)據(jù)庫(kù)、數(shù)據(jù)立方體或一般文件。 它需要統(tǒng)一原始數(shù)據(jù)中的所有矛盾之處，如字段的: 同名異義； 異名同義； 單位不統(tǒng)一； 字長(zhǎng)不一致等。,44,數(shù)據(jù)集成,集成過(guò)程中需要注意的問(wèn)題 模式集成問(wèn)題； 冗余問(wèn)題； 數(shù)據(jù)值沖突檢測(cè)與消除。,45,（1）模式集成問(wèn)題,模式集成： 整合不同數(shù)據(jù)源中的元數(shù)據(jù)； 進(jìn)行實(shí)體識(shí)別：匹配來(lái)自不同數(shù)據(jù)源的現(xiàn)實(shí)世界的實(shí)體 如：如何確信一個(gè)數(shù)據(jù)庫(kù)中的customer_id和

19、另一個(gè)數(shù)據(jù)庫(kù)中的cust_number是同一實(shí)體。 通常，數(shù)據(jù)庫(kù)的數(shù)據(jù)字典和數(shù)據(jù)倉(cāng)庫(kù)的元數(shù)據(jù)，可幫助避免模式集成中的錯(cuò)誤。,46,（2）數(shù)據(jù)冗余問(wèn)題,數(shù)據(jù)冗余問(wèn)題： 同一屬性值不同的數(shù)據(jù)庫(kù)中會(huì)有不同的字段名； 一個(gè)屬性可以由另外一個(gè)表導(dǎo)出，如：一個(gè)顧客數(shù)據(jù)表中的平均月收入屬性，可以根據(jù)月收入屬性計(jì)算出來(lái)。,47,（2）數(shù)據(jù)冗余問(wèn)題,數(shù)據(jù)冗余問(wèn)題： 有些冗余可以被相關(guān)分析檢測(cè)到：,如果變量A、B間具有較高的相關(guān)系數(shù)，表明A或B可以作為冗余而去掉。,除了檢查屬性是否冗余外，還要檢查記錄行的冗余。,48,(3)數(shù)據(jù)值沖突問(wèn)題,數(shù)據(jù)值沖突 對(duì)現(xiàn)實(shí)世界的同一實(shí)體，來(lái)自不同數(shù)據(jù)源的屬性值可能不同。 產(chǎn)生的

20、原因：表示、比例或編碼不同。 如：重量屬性在一個(gè)系統(tǒng)中可能以公制單位存放，而在另一系統(tǒng)中可能以英制單位存放；同一商品的價(jià)格屬性值不同地域采用不同價(jià)格單位；不同學(xué)校的成績(jī)單可能以百分制、五分制及其他等級(jí)制來(lái)存放等等。,2. 數(shù)據(jù)變換？,50,數(shù)據(jù)變換,數(shù)據(jù)變換：將數(shù)據(jù)轉(zhuǎn)換成適合數(shù)據(jù)挖掘的形式。涉及內(nèi)容：（1）平滑：去掉數(shù)據(jù)中的噪聲，將連續(xù)的數(shù)據(jù)離散化： 分箱 聚類 回歸。 （2）聚集：對(duì)數(shù)據(jù)進(jìn)行匯總和聚集 Avg(), count(), sum(), min(), max(), 如，每天銷售額（數(shù)據(jù)）可以進(jìn)行聚集操作以獲得每月或每年的總額。 可用來(lái)構(gòu)造數(shù)據(jù)立方體。,51,數(shù)據(jù)變換,數(shù)據(jù)變換：將數(shù)

21、據(jù)轉(zhuǎn)換成適合數(shù)據(jù)挖掘的形式。涉及內(nèi)容：（3）數(shù)據(jù)概化：使用概念分層，用更抽象（更高層次）的概念來(lái)取代低層次或數(shù)據(jù)層的數(shù)據(jù)對(duì)象 如，街道屬性，可以泛化到更高層次的概念，如城市、國(guó)家； 同樣，對(duì)于數(shù)值型的屬性，如年齡屬性，可以映射到更高層次的概念，如年輕、中年和老年。,52,數(shù)據(jù)變換,數(shù)據(jù)變換：將數(shù)據(jù)轉(zhuǎn)換成適合數(shù)據(jù)挖掘的形式。涉及內(nèi)容：（4）規(guī)范化：將數(shù)據(jù)按比例進(jìn)行縮放，使之落入一個(gè)特定的區(qū)域，以消除數(shù)值型屬性因大小不一而造成的挖掘結(jié)果的偏差。如將工資收入屬性值映射到-1.0, 1.0的范圍內(nèi)。 常用的方法： 最小-最大規(guī)范化； 零-均值規(guī)范化（z-score規(guī)范化）； 小數(shù)定標(biāo)規(guī)范化。,規(guī)格化的

22、目的： 是將一個(gè)屬性取值范圍影射到一個(gè)特定范圍之內(nèi)，以消除數(shù)值性屬性因大小不一而造成挖掘結(jié)果的偏差。,數(shù)據(jù)變換規(guī)范化,在正式進(jìn)行數(shù)據(jù)挖掘之前，尤其是使用基于對(duì)象距離的挖掘算法時(shí)，必須進(jìn)行數(shù)據(jù)的規(guī)格化。 如對(duì)于一個(gè)顧客信息數(shù)據(jù)庫(kù)中年齡屬性或工資屬性，由于工資屬性的取值比年齡屬性的取值要大得多，若不進(jìn)行規(guī)格化處理，基于工資屬性的距離計(jì)算值將遠(yuǎn)遠(yuǎn)超過(guò)基于年齡屬性的計(jì)算值，這就意味著工資屬性的作用在整個(gè)數(shù)據(jù)對(duì)象的距離計(jì)算中被錯(cuò)誤放大了。,數(shù)據(jù)變換規(guī)范化,55,數(shù)據(jù)變換規(guī)范化,數(shù)據(jù)規(guī)范化：將數(shù)據(jù)按比例縮放至一個(gè)小的特定區(qū)間： 1）最小最大規(guī)范化：假定minA和maxA分別為屬性A的最小和最大值，則通過(guò)下

23、面公式將A的值映射到區(qū)間new_min, new_max中的v：,例：假定屬性income的最小與最大值分別為$12000和$98000，可根據(jù)最小最大規(guī)范化方法將其范圍映射到0,1： 如：屬性值$73600將變換為： (73600-12000)/(98000-12000)*(1-0)+0=0.716,56,數(shù)據(jù)變換規(guī)范化,2）z-score規(guī)范化（零均值規(guī)范化）： 將屬性A的值根據(jù)其平均值和標(biāo)準(zhǔn)差進(jìn)行規(guī)范化； 常用于屬性最大值與最小值未知，或使用最小最大規(guī)范化方法會(huì)出現(xiàn)異常數(shù)據(jù)的情況。,其中，meanA、standard-devA分別為屬性A取值的均值和標(biāo)準(zhǔn)差。 例：假定屬性income的平

24、均值與標(biāo)準(zhǔn)差分別為$54000和$16000，使用z-score規(guī)范化，則屬性值$73600將變換為： (73600-54000）/16000=1.225,57,數(shù)據(jù)變換規(guī)范化,3）小數(shù)定標(biāo)規(guī)范化：通過(guò)移動(dòng)屬性A的小數(shù)點(diǎn)位置進(jìn)行規(guī)范化，小數(shù)點(diǎn)的移動(dòng)依賴于A的最大絕對(duì)值：,例：假定A的取值范圍-986, 917，則A的最大絕對(duì)值為986，為使用小數(shù)定標(biāo)規(guī)范化，用1000（即j=3）除每個(gè)值，這樣-986被規(guī)范化為-0.986。,其中，j是使 Max(| v |)1的最小整數(shù),規(guī)范化將原來(lái)的數(shù)據(jù)改變很多，特別是上述的后兩種方法。 有必要保留規(guī)范化參數(shù)（如平均值和標(biāo)準(zhǔn)差，如果使用z-score規(guī)范化

25、），以便將來(lái)的數(shù)據(jù)可以用一致的方式規(guī)范化。,注意：,59,數(shù)據(jù)變換,數(shù)據(jù)變換：將數(shù)據(jù)轉(zhuǎn)換成適合數(shù)據(jù)挖掘的形式。涉及內(nèi)容：（5）屬性構(gòu)造： 利用已有屬性集構(gòu)造出新的屬性，并加入到現(xiàn)有屬性集中以幫助挖掘更深層次的模式知識(shí)，提高挖掘結(jié)果的準(zhǔn)確性； 如，根據(jù)寬、高屬性，可以構(gòu)造一個(gè)新屬性：面積。,4.3 數(shù)據(jù)歸約,對(duì)大規(guī)模數(shù)據(jù)庫(kù)內(nèi)容進(jìn)行復(fù)雜的數(shù)據(jù)分析常需要消耗大量的時(shí)間，使得這樣的分析變得不現(xiàn)實(shí)和不可行； 數(shù)據(jù)歸約（data reduction）：數(shù)據(jù)消減或約簡(jiǎn)，是在不影響最終挖掘結(jié)果的前提下，縮小所挖掘數(shù)據(jù)的規(guī)模。 數(shù)據(jù)歸約技術(shù)可以用來(lái)得到數(shù)據(jù)集的歸約表示，它小得多，但仍接近保持原數(shù)據(jù)的完整性。 對(duì)

26、歸約后的數(shù)據(jù)集進(jìn)行挖掘可提高挖掘的效率，并產(chǎn)生相同（或幾乎相同）的結(jié)果。,4.3 數(shù)據(jù)歸約,數(shù)據(jù)歸約的標(biāo)準(zhǔn)： 用于數(shù)據(jù)歸約的時(shí)間不應(yīng)當(dāng)超過(guò)或“抵消”在歸約后的數(shù)據(jù)集上挖掘節(jié)省的時(shí)間。 歸約得到的數(shù)據(jù)比原數(shù)據(jù)小得多，但可以產(chǎn)生相同或幾乎相同的分析結(jié)果。,4.3 數(shù)據(jù)歸約,數(shù)據(jù)歸約的策略如下： 數(shù)據(jù)立方體聚集； 維歸約； 數(shù)據(jù)壓縮； 數(shù)值歸約； 離散化和概念分層生成。,1. 數(shù)據(jù)立方體聚集？,64,數(shù)據(jù)立方體聚集,2. 維歸約？,66,維歸約,維歸約：主要用于檢測(cè)并刪除不相關(guān)、弱相關(guān)或冗余的屬性維 用于數(shù)據(jù)分析的數(shù)據(jù)可能包含數(shù)以百計(jì)的屬性，其中大部分可能與挖掘任務(wù)不相關(guān)，是冗余的。如，分析顧客是否

27、會(huì)在商場(chǎng)購(gòu)買mp3播放器，諸如顧客的電話號(hào)碼等屬性多半是不相關(guān)的。 維歸約通過(guò)刪除不相關(guān)的屬性（或維），而有效減少數(shù)據(jù)庫(kù)的規(guī)模。 最常用的方法：屬性子集選擇。,67,維歸約屬性子集選擇,目標(biāo)： 找出最小屬性集，確保新數(shù)據(jù)集的概率分布盡可能接近原數(shù)據(jù)集的概率分布。 如何找出原屬性的一個(gè)好的子集 d個(gè)屬性有2d個(gè)可能的子集。窮舉搜索找出屬性的最佳子集可能是不現(xiàn)實(shí)的，特別是當(dāng)d的數(shù)目很大時(shí)。,68,維歸約屬性子集選擇,啟發(fā)式算法： 對(duì)于屬性子集選擇，通常使用壓縮搜索空間的啟發(fā)式算法。 它們的策略是做局部最優(yōu)選擇，期望由此導(dǎo)致全局最優(yōu)解。,69,維歸約屬性子集選擇,常用的啟發(fā)式方法： 1）逐步向前選擇

28、： 該過(guò)程由空屬性集開始，選擇原屬性集中最好的屬性，并將它添加到該集合中。 在其后的每一次迭代，將原屬性集剩下的屬性中的最好的屬性添加到該集合中。 如：遺傳算法是一種基于生物進(jìn)化論和分子遺傳學(xué)的全局隨機(jī)搜索算法。,70,維歸約屬性子集選擇,常用的啟發(fā)式方法： 2）逐步向后刪除： 由整個(gè)屬性集開始，每一步都刪除尚在屬性集中的最壞屬性。 直到無(wú)法選擇出最壞屬性或滿足一定的閾值為止。 如：粗糙集理論， 利用定義的數(shù)據(jù)集合U上的等價(jià)關(guān)系對(duì)U進(jìn)行劃分，對(duì)于數(shù)據(jù)表來(lái)說(shuō)，這種等價(jià)關(guān)系可以是某個(gè)屬性，或者是幾個(gè)屬性的集合。因此，按照不同屬性的組合就把數(shù)據(jù)表劃分成不同的基本類，在這些基本類的基礎(chǔ)上進(jìn)一步求得最小

29、約簡(jiǎn)集。,71,維歸約屬性子集選擇,常用的啟發(fā)式方法： 3）向前選擇和向后刪除的結(jié)合： 將向前選擇和向后刪除方法結(jié)合在一起； 每一步選擇一個(gè)最好的屬性，并在剩余屬性中刪除一個(gè)最壞的屬性。,72,維歸約屬性子集選擇,常用的啟發(fā)式方法： 4）判定樹歸納： 在判定樹的每個(gè)節(jié)點(diǎn)，算法選擇“最好”的屬性，將數(shù)據(jù)劃分成類。 當(dāng)判定樹歸納用于屬性子集選擇時(shí)，不出現(xiàn)在樹中的所有屬性假定是不相關(guān)的； 出現(xiàn)在判定樹中的屬性形成歸約后的屬性子集。,3. 數(shù)據(jù)壓縮？,75,數(shù)據(jù)壓縮,數(shù)據(jù)壓縮就是利用數(shù)據(jù)編碼或數(shù)據(jù)轉(zhuǎn)換將原來(lái)的數(shù)據(jù)集合壓縮為一個(gè)較小規(guī)模的數(shù)據(jù)集合。 壓縮算法分為兩類： 無(wú)損壓縮（loseless）：可以

30、不丟失任何信息地還原壓縮數(shù)據(jù)；如：字符串壓縮 有損壓縮（lossy）：只能重新構(gòu)造原數(shù)據(jù)的近似表示；如：音頻/視頻壓縮。,76,77,數(shù)據(jù)壓縮,兩類： 1）無(wú)損壓縮：指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)完全相同。 即：數(shù)據(jù)經(jīng)過(guò)壓縮后，信息不受損失，還能完全恢復(fù)到壓縮前的原樣。 壓縮軟件：Zip或RAR。,78,數(shù)據(jù)壓縮,兩類： 2）有損壓縮：又稱破壞型壓縮，即將次要的信息數(shù)據(jù)壓縮掉，犧牲一些質(zhì)量來(lái)減少數(shù)據(jù)量，使壓縮比提高。 常用于壓縮聲音、圖像以及視頻。音頻能夠在沒(méi)有察覺(jué)的質(zhì)量下降情況下實(shí)現(xiàn) 10:1 的壓縮比，視頻能夠在稍微觀察質(zhì)量下降的情況下實(shí)現(xiàn)如

31、300:1 這樣非常大的壓縮比。 常見算法：JPEG、MPEG、MP3等。 算法機(jī)理：小波變換或主成份分析,4. 數(shù)值歸約？,80,數(shù)值歸約,數(shù)值歸約：通過(guò)選擇替代的、較小的數(shù)據(jù)表示形式來(lái)減少數(shù)據(jù)量。 （1）有參方法： 通常使用一個(gè)參數(shù)模型來(lái)評(píng)估數(shù)據(jù)，該方法只需要存儲(chǔ)參數(shù)，而不是實(shí)際數(shù)據(jù)，能大大減少數(shù)據(jù)量，但只對(duì)數(shù)值型數(shù)據(jù)有效。 如：線性回歸方法（最小二乘法）：Y=+X,81,數(shù)值歸約,數(shù)值歸約：通過(guò)選擇替代的、較小的數(shù)據(jù)表示形式來(lái)減少數(shù)據(jù)量。 （2）無(wú)參方法： 常見的有： 直方圖； 聚類； 取樣。,82,1）直方圖,直方圖：根據(jù)屬性的數(shù)據(jù)分布將其分成若干不相交的區(qū)間，每個(gè)區(qū)間的高度與其出現(xiàn)的

32、頻率成正比。 例：下面的數(shù)據(jù)是AllElectronics通常銷售的商品的單價(jià)表（已排序）：1,1,5,5,5,5,5,8,8,10,10,10,10,12,14,14,14,15,15,15,15,15,15,18,18, 18,18, 18,18, 18,18,20,20, 20,20, 20,20,20,21,21, 21,21,25,25, 25,25,25,28,28,30,30,30。 試用直方圖表示，以壓縮數(shù)據(jù)。,83,1）直方圖,頻率-值對(duì)應(yīng)關(guān)系圖,84,2）聚類,聚類：將原數(shù)據(jù)集劃分成多個(gè)群或聚類。 原則：同類中的數(shù)據(jù)彼此相似；不同類中的數(shù)據(jù)彼此不相似。 相似：通常用空間距離

33、度量 聚類的有效性依賴于實(shí)際數(shù)據(jù)的內(nèi)在規(guī)律。,85,3）取樣,取樣（抽樣）：允許用數(shù)據(jù)的較小隨機(jī)樣本（子集）表示大的數(shù)據(jù)集。 取樣方法： 不放回簡(jiǎn)單隨機(jī)取樣 （Simple Random Sampling Without Replacement, SRSWOR） 放回簡(jiǎn)單隨機(jī)取樣（Simple Random Sampling With Replacement, SRSWR） 聚類取樣：先聚類，后取樣 分層取樣：先分層，后取樣。,取樣SRS,SRSWOR (簡(jiǎn)單隨機(jī)選 樣，不回放),SRSWR (簡(jiǎn)單隨機(jī)選 樣，回放),87,取樣,聚類采樣： 首先將大數(shù)據(jù)集D劃分為M個(gè)互不相交的聚類，然后再?gòu)腗

34、個(gè)類中的數(shù)據(jù)對(duì)象分別進(jìn)行隨機(jī)抽取，可最終獲得聚類采樣的數(shù)據(jù)子集。,聚類采樣方法示意圖,88,聚類取樣,89,取樣,分層取樣： 首先將大數(shù)據(jù)集D劃分為互不相交的層，然后對(duì)每一層簡(jiǎn)單隨機(jī)選樣得到D的分層選樣。 如，根據(jù)顧客的年齡組進(jìn)行分層，然后再在每個(gè)年齡組中進(jìn)行隨機(jī)選樣，從而確保了最終獲得分層采樣數(shù)據(jù)子集中的年齡分布具有代表性。,90,分層取樣,分層采樣方法示意圖,4.4 數(shù)據(jù)離散化和概念分層*,三種類型的屬性值： 標(biāo)稱型（名稱型、名義型）：數(shù)值來(lái)自于無(wú)序集合，如性別、地名、人名等。 序數(shù)型：數(shù)值來(lái)自于有序集合，如獎(jiǎng)學(xué)金的等級(jí)；職稱分布等。 連續(xù)型：實(shí)數(shù)值，如溫度、體重等。 離散化技術(shù)： 通過(guò)將

35、屬性（連續(xù)取值）閾值范圍分為若干區(qū)間，來(lái)幫助消減一個(gè)連續(xù)（取值）屬性的取值個(gè)數(shù)。 如，將氣溫劃分為：冷、正常、熱。,4.4 數(shù)據(jù)離散化和概念分層*,概念分層： 概念分層定義了一組由低層概念到高層概念集的映射。允許在各種抽象級(jí)別上處理數(shù)據(jù)，從而在多個(gè)抽象層上發(fā)現(xiàn)知識(shí)。 用較高層概念替換低層次（如年齡的數(shù)值）的概念，以此來(lái)減少取值個(gè)數(shù)。 雖然一些細(xì)節(jié)數(shù)據(jù)在泛化過(guò)程中消失了，但這樣所獲得的泛化數(shù)據(jù)或許更易于理解、更有意義。 另外，在消減后的數(shù)據(jù)集上進(jìn)行信息處理顯然效率更高。 概念分層結(jié)構(gòu)可以用樹來(lái)表示，樹的每個(gè)節(jié)點(diǎn)代表一個(gè)概念。,93,概念分層,離散化方法,常用的離散化方法： 1）分箱：屬性的值可以

36、通過(guò)將其分配到各分箱中而將其離散化。 利用每個(gè)分箱的均值或中數(shù)替換每個(gè)分箱中的值（利用均值或中數(shù)進(jìn)行平滑）。 循環(huán)應(yīng)用這些操作處理每次操作結(jié)果，就可以獲得一個(gè)概念層次樹。,離散化方法,常用的離散化方法： 2）直方圖： 等寬直方圖中，將數(shù)據(jù)劃分成相等的部分或區(qū)間，如(0,100$)、(100$,200$、(200$,300$. 等深直方圖：值被劃分使得每一部分包括相同個(gè)數(shù)的樣本。,離散化方法,常用的離散化方法： 3）聚類分析： 聚類算法可以將數(shù)據(jù)集劃分為若干類或組。 每個(gè)類構(gòu)成了概念分層樹的一個(gè)節(jié)點(diǎn)； 每個(gè)類還可以進(jìn)一步分解為若干子類，從而構(gòu)造更低水平的層次。 當(dāng)然類也可以合并起來(lái)構(gòu)成更高層次的

37、概念水平。 4）基于熵的離散化：熵是一種信息度量的方法 5）通過(guò)自然劃分分段,基于熵的離散化,思想： 考慮類別信息，遞歸計(jì)算信息熵，產(chǎn)生分層的離散化。,I(S)=,初始不確定性：,基于熵的離散化,思想： 考慮類別信息，遞歸計(jì)算信息熵，產(chǎn)生分層的離散化。 給定一個(gè)數(shù)據(jù)元組的集合S，基于熵對(duì)S離散化的方法如下： 1）屬性A中的每個(gè)取值可被認(rèn)為是一個(gè)潛在的區(qū)間邊界或閾值T。例如，A的取值v可以將樣本S劃分為分別滿足Av和Av兩個(gè)子集，這樣就創(chuàng)建了一個(gè)二元離散化。 2）對(duì)于數(shù)據(jù)集S，根據(jù)所劃分子集而獲得的最大熵增益來(lái)選擇閾值，劃分后數(shù)據(jù)集S提供的信息如下：,E(A)=,學(xué)習(xí)屬性A之后的不確定性：,基于

38、熵的離散化,其中S1和S2分別對(duì)應(yīng)于S中滿足條件：AT與AT，的樣本。對(duì)給定的集合，熵函數(shù)Ent根據(jù)集合中樣本的類分布來(lái)計(jì)算。例如，給定m個(gè)不同類別，S1的熵就是：,其中pi為類i在S1中出現(xiàn)的概率，等于S1中類i的樣本除以S1中樣本的總行數(shù)。同理，計(jì)算Ent(S2)。 3）確定閾值的過(guò)程遞歸的用于所得到的每個(gè)劃分，直到滿足某個(gè)終止條件，如：,Ent(S)-I(S,T) ,信息增益不能低于：,基于熵的離散化,與迄今為止提到的其他方法不同，基于熵的離散化使用了類別信息。這使得它更有可能將區(qū)間邊界定義在準(zhǔn)確位置，有助于提高分類的準(zhǔn)確性。 此處用到的信息增益和信息熵也用于決策樹歸納。,自然劃分分段,

39、思想： 將數(shù)值區(qū)域劃分為相對(duì)一致的、易于閱讀的、看上去更直觀或自然的區(qū)間。 聚類分析產(chǎn)生的概念分層可能會(huì)將一個(gè)工資區(qū)間劃分為：51263.98, 60872.34 而通常數(shù)據(jù)分析人員希望看到劃分的形式為50000，60000 自然劃分的3-4-5規(guī)則常可以將數(shù)值數(shù)據(jù)劃分為相對(duì)一致和“自然”的區(qū)間。一般的，根據(jù)最重要的數(shù)字上的值區(qū)域，遞歸的和逐層的將給定的數(shù)據(jù)區(qū)域劃分為3、4或5個(gè)等寬區(qū)間。,自然劃分的3-4-5規(guī)則,規(guī)則的劃分步驟： 如果一個(gè)區(qū)間最高有效位上跨越3，6，7或9個(gè)不同的值，就將該區(qū)間劃分為3個(gè)等寬子區(qū)間；(72,3,2) 如果一個(gè)區(qū)間最高有效位上跨越2，4，或8個(gè)不同的值，就將該

40、區(qū)間劃分為4個(gè)等寬子區(qū)間； 如果一個(gè)區(qū)間最高有效位上跨越1，5，或10個(gè)不同的值，就將該區(qū)間劃分為5個(gè)等寬子區(qū)間； 將該規(guī)則遞歸的應(yīng)用于每個(gè)子區(qū)間，產(chǎn)生給定數(shù)值屬性的概念分層；,自然劃分的3-4-5規(guī)則,規(guī)則的劃分步驟： 對(duì)于數(shù)據(jù)集中出現(xiàn)的最大值和最小值的極端分布，為了避免上述方法出現(xiàn)的結(jié)果扭曲，可以在頂層分段時(shí)，選用一個(gè)大部分的概率空間。e.g. 5%-95% 例如，在資產(chǎn)數(shù)據(jù)集中，少數(shù)人的資產(chǎn)可能比其他人高幾個(gè)數(shù)量級(jí)。如果按照最高資產(chǎn)值進(jìn)行分段，可能導(dǎo)致高度傾斜的分層。此時(shí)，可以在頂層分段時(shí)，選用一個(gè)大部分的概率空間。e.g. 5%-95%。 越出頂層分段的特別高和特別低的部分采用類似的規(guī)

41、則劃分方法形成單獨(dú)的區(qū)間。,示例：3-4-5規(guī)則,假定AllElectronics所有分部1999年的利潤(rùn)覆蓋了一個(gè)很寬的區(qū)間，從-351.00$到4700$。要求利用3-4-5規(guī)則自動(dòng)構(gòu)造利潤(rùn)屬性的一個(gè)概念層次樹。,示例：3-4-5規(guī)則,思路： 設(shè)在上述范圍取值為5%至95%的區(qū)間為：-159$至1838$。應(yīng)用3-4-5規(guī)則的具體步驟如下： 1）根據(jù)以上信息，在利潤(rùn)數(shù)據(jù)集中最小和最大值分別為：MIN=-351$, MAX=4700$。而根據(jù)以上分析，對(duì)于分段的頂層或第一層，要考慮的最低（5%）和最高（95%）的值是：LOW=-159$, HIGH=1838$。 2）依據(jù)LOW和HIGH及其

42、取值范圍，確定最高有效位為1000$，LOW按1000$美元向下取整，得到LOW=-1000$；HIGH按1000$向上取整，得到：HIGH=2000$。,示例：3-4-5規(guī)則,3）由于該區(qū)間在最高有效位上跨越了3個(gè)值，即(2000-(-1000)/1000=3，根據(jù)3-4-5規(guī)則，該區(qū)間被劃分成3個(gè)等寬區(qū)間：(-1000$,0, (0, 1000$, (1000$,2000$。這代表分層結(jié)構(gòu)的最頂層。,示例：3-4-5規(guī)則,4）現(xiàn)在，考察原數(shù)據(jù)集中MIN和MAX值與最高層區(qū)間的聯(lián)系。由于MIN值落在區(qū)間(-1000$,0，因此調(diào)整左邊界，對(duì)MIN取整后的-400$，所以第一個(gè)區(qū)間調(diào)整為(-4

43、00$,0。 而由于MAX值不在最后一個(gè)區(qū)間 (1000$,2000$中，因此需新建一個(gè)區(qū)間（最右邊區(qū)間）。對(duì)MAX取整后得5000$，因此新區(qū)間為(2000$,5000。 因此最終，概念樹分層結(jié)構(gòu)的最頂層包含4個(gè)區(qū)間：(-400$,0, (0,1000$,(1000$,2000$, (2000$,5000$。,示例：3-4-5規(guī)則,5）對(duì)上述每個(gè)區(qū)間遞歸應(yīng)用3-4-5規(guī)則，形成分層結(jié)構(gòu)的下一個(gè)較低層： 第一個(gè)區(qū)間(-400$,0：劃分為4個(gè)子區(qū)間(-400$,-300$, (-300$,-200$, (-200$,-100$, (-100$,0$. 第二個(gè)區(qū)間(0$,1000$：劃分為5個(gè)子區(qū)間(0$,200$, (200$,400$, 400$,600$, (600$,800$, (800$,1000$. 第三個(gè)區(qū)間(1000$,2000$：劃分為5個(gè)子區(qū)間(1000$,120