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

1、 數(shù)據(jù)倉庫與數(shù)據(jù)挖掘數(shù)據(jù)倉庫與數(shù)據(jù)挖掘 2 目前，數(shù)據(jù)挖掘的研究工作大都集中在算法的探討 而忽視對數(shù)據(jù)處理的研究。事實(shí)上，數(shù)據(jù)預(yù)處理對數(shù)據(jù) 挖掘十分重要，一些成熟的算法都對其處理的數(shù)據(jù)集合 有一定的要求：比如數(shù)據(jù)的完整性好，冗余性小，屬性 的相關(guān)性小等。 高質(zhì)量的決策來自高質(zhì)量的數(shù)據(jù)，因此數(shù)據(jù)預(yù)處理 是整個數(shù)據(jù)挖掘與知識發(fā)現(xiàn)過程中的一個重要步驟。 數(shù)據(jù)挖掘數(shù)據(jù)挖掘: : 數(shù)據(jù)庫中的知識挖掘數(shù)據(jù)庫中的知識挖掘(KDD)(KDD) 數(shù)據(jù)挖掘數(shù)據(jù)挖掘知識挖知識挖 掘的核心掘的核心 數(shù)據(jù)清洗數(shù)據(jù)清洗 數(shù)據(jù)集成數(shù)據(jù)集成 數(shù)據(jù)庫數(shù)據(jù)庫 數(shù)據(jù)倉庫數(shù)據(jù)倉庫 任務(wù)相關(guān)數(shù)據(jù)任務(wù)相關(guān)數(shù)據(jù) 選擇選擇 數(shù)據(jù)挖掘數(shù)據(jù)挖掘

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

3、戶，郵件列表中0.1%的記錄是 重復(fù)的，主要是因?yàn)橥粋€客戶的名字可能有不同的寫法， 如：Jon Doe和John Doe。 因此，每周需要印刷和郵寄100份額外的刊物，假設(shè)每份 刊物每周的郵寄和印刷費(fèi)用是兩美元，公司每年將至少浪費(fèi) 1萬美元以上。 3）不完整性：）不完整性：由于實(shí)際系統(tǒng)設(shè)計(jì)時存在的缺陷以及使用過程由于實(shí)際系統(tǒng)設(shè)計(jì)時存在的缺陷以及使用過程 中的一些人為因素，數(shù)據(jù)記錄可能會出現(xiàn)數(shù)據(jù)值的丟失或不中的一些人為因素，數(shù)據(jù)記錄可能會出現(xiàn)數(shù)據(jù)值的丟失或不 確定。確定。 原因可能有： （1）有些屬性的內(nèi)容有時沒有 （家庭收入，參與銷售事務(wù)數(shù)據(jù)中的顧客信息） （2）有些數(shù)據(jù)當(dāng)時被認(rèn)為是不必要的

4、 （3）由于誤解或檢測設(shè)備失靈導(dǎo)致相關(guān)數(shù)據(jù)沒有記錄下來 （4）與其它記錄內(nèi)容不一致而被刪除 （5）忽略了歷史數(shù)據(jù)或?qū)?shù)據(jù)的修改 4）噪聲數(shù)據(jù)：）噪聲數(shù)據(jù)：數(shù)據(jù)中存在著錯誤或異常（偏離期望值）數(shù)據(jù)中存在著錯誤或異常（偏離期望值） v如：血壓和身高為如：血壓和身高為0就是明顯的錯誤就是明顯的錯誤 v噪聲數(shù)據(jù)的產(chǎn)生原因：噪聲數(shù)據(jù)的產(chǎn)生原因： 數(shù)據(jù)采集設(shè)備有問題；數(shù)據(jù)采集設(shè)備有問題； 在數(shù)據(jù)錄入過程發(fā)生人為或計(jì)算機(jī)錯誤；在數(shù)據(jù)錄入過程發(fā)生人為或計(jì)算機(jī)錯誤； 數(shù)據(jù)傳輸過程中出現(xiàn)錯誤；數(shù)據(jù)傳輸過程中出現(xiàn)錯誤； 由于命名規(guī)則或數(shù)據(jù)代碼不同而引起的不一致。由于命名規(guī)則或數(shù)據(jù)代碼不同而引起的不一致。 q 數(shù)據(jù)清

5、理（清洗）數(shù)據(jù)清理（清洗） -去掉數(shù)據(jù)中的噪聲，糾正不一致 q 數(shù)據(jù)集成數(shù)據(jù)集成 -將多個數(shù)據(jù)源合并成一致的數(shù)據(jù)存儲，構(gòu)成一個完整 的數(shù)據(jù)集，如數(shù)據(jù)倉庫。 q 數(shù)據(jù)變換（轉(zhuǎn)換）數(shù)據(jù)變換（轉(zhuǎn)換） -將一種格式的數(shù)據(jù)轉(zhuǎn)換為另一格式的數(shù)據(jù)(如規(guī)范化) q 數(shù)據(jù)歸約（消減）數(shù)據(jù)歸約（消減） -通過聚集、刪除冗余屬性或聚類等方法來壓縮數(shù)據(jù)。 11 注意：注意： 上述的各種數(shù)據(jù)預(yù)處理方法，并不是相互獨(dú)立上述的各種數(shù)據(jù)預(yù)處理方法，并不是相互獨(dú)立 的，而是相互關(guān)聯(lián)的，如消除數(shù)據(jù)冗余既可以看成的，而是相互關(guān)聯(lián)的，如消除數(shù)據(jù)冗余既可以看成 是一種形式的數(shù)據(jù)清洗，也可以看成是一種數(shù)據(jù)歸是一種形式的數(shù)據(jù)清洗，也可以看

6、成是一種數(shù)據(jù)歸 約（消減）。約（消減）。 4.1 數(shù)據(jù)清洗數(shù)據(jù)清洗 4.2 數(shù)據(jù)集成和變換數(shù)據(jù)集成和變換 4.3 數(shù)據(jù)歸約數(shù)據(jù)歸約 4.4 數(shù)據(jù)離散化和概念分層數(shù)據(jù)離散化和概念分層* 14 u 掌握數(shù)據(jù)清洗的處理方法（空缺、噪聲、 不一致）； u 掌握各種數(shù)據(jù)歸約的方法； u 理解數(shù)據(jù)離散化的方法。 4.1 數(shù)據(jù)清洗數(shù)據(jù)清洗 現(xiàn)實(shí)世界的數(shù)據(jù)一般是臟的、不完整的和不一致的。而數(shù) 據(jù)清洗試圖填充空缺的值、識別孤立點(diǎn)、消除噪聲，并糾正數(shù) 據(jù)中的不一致性。因此，從如下幾個方面介紹： （1 1）空缺值；）空缺值； （2 2）噪聲數(shù)據(jù)；）噪聲數(shù)據(jù)； （3 3）不一致數(shù)據(jù)。）不一致數(shù)據(jù)。 1. 1. 空缺值

7、的處理？空缺值的處理？ 17 空缺值空缺值 u數(shù)據(jù)并不總是完整的 數(shù)據(jù)庫表中，很多條記錄的對應(yīng)字段可能沒有相應(yīng)值，比如銷 售表中的顧客收入 u引起空缺值的原因 設(shè)備異常 與其他已有數(shù)據(jù)不一致而被刪除 因?yàn)檎`解而沒有被輸入的數(shù)據(jù) 在輸入時，有些數(shù)據(jù)因?yàn)榈貌坏街匾暥鴽]有被輸入 對數(shù)據(jù)的改變沒有進(jìn)行日志記載 u空缺值要經(jīng)過推斷而補(bǔ)上。 如何處理空缺值如何處理空缺值 1）忽略該元組：）忽略該元組： v 若一條記錄中有屬性值被遺漏了，則將該記錄排除在 數(shù)據(jù)挖掘之外； v 尤其當(dāng)類標(biāo)號缺少時通常這樣做（假定挖掘任務(wù)涉及分 類或描述)； v 但是，當(dāng)某類屬性的空缺值所占百分比很大時，直接忽 略元組會使挖掘性

8、能變得非常差。 如何處理空缺值如何處理空缺值 2）人工填寫空缺值：）人工填寫空缺值： v工作量大，可行性低 3）使用屬性的平均值填充空缺值：）使用屬性的平均值填充空缺值： v如所有顧客的平均收入為$1000，則使用該值替換 income中的空缺值。 如何處理空缺值如何處理空缺值 4）使用一個全局變量填充空缺值：）使用一個全局變量填充空缺值： v如：將空缺的屬性值用同一個常數(shù)(如“Unknown”)替 換。 v如果空缺值都用“Unknown”替換，當(dāng)空缺值較多時 ，挖掘程序可能誤以為它們形成了一個有趣的概念， 因?yàn)樗鼈兌季哂邢嗤闹怠癠nknown”。 v因此，盡管該方法簡單，我們并不推薦它。

9、如何處理空缺值如何處理空缺值 5）使用與給定元組屬同一類的所有樣本的平均值：）使用與給定元組屬同一類的所有樣本的平均值： l 適用于分類數(shù)據(jù)挖掘； l 如將顧客按信用度分類，則用具有相同信用度的顧客的平均 收入替換income中的空缺值。 6）使用最可能的值填充空缺值（最常用）：）使用最可能的值填充空缺值（最常用）： l 可以利用回歸、貝葉斯計(jì)算公式或判定樹歸納確定，推斷出 該條記錄特定屬性最大可能的取值； l 如，利用數(shù)據(jù)集中其他顧客的屬性，構(gòu)造一棵判定樹，預(yù)測 income的空缺值。 2. 2. 噪聲數(shù)據(jù)的處理？噪聲數(shù)據(jù)的處理？ 噪聲數(shù)據(jù)噪聲數(shù)據(jù) u噪聲噪聲(noise) ：是一個測量變量

10、中的隨機(jī)錯誤或偏是一個測量變量中的隨機(jī)錯誤或偏 差差 u引起噪聲數(shù)據(jù)的原因引起噪聲數(shù)據(jù)的原因 數(shù)據(jù)收集工具的問題 數(shù)據(jù)輸入錯誤 數(shù)據(jù)傳輸錯誤 技術(shù)限制 命名規(guī)則的不一致 如何處理噪聲數(shù)據(jù)如何處理噪聲數(shù)據(jù) 1）分箱）分箱 (binning): u分分箱方法通過考察箱方法通過考察“鄰居鄰居”(即周圍的值即周圍的值)來平滑存儲數(shù)來平滑存儲數(shù) 據(jù)的值據(jù)的值。 u存存儲的值被分布到一些儲的值被分布到一些“桶桶”或箱中。由于分箱方法或箱中。由于分箱方法 參考相鄰的值，因此它進(jìn)行局部平參考相鄰的值，因此它進(jìn)行局部平滑?；?如何處理噪聲數(shù)據(jù)如何處理噪聲數(shù)據(jù) 分箱的步驟：分箱的步驟： v首先排序數(shù)據(jù)，并將它們

11、分到等深（等寬）的箱中；首先排序數(shù)據(jù)，并將它們分到等深（等寬）的箱中； v然后可以按箱的然后可以按箱的平均值平均值、按箱、按箱中值中值或者按箱的或者按箱的邊界邊界等等 進(jìn)行平滑。進(jìn)行平滑。 按箱的按箱的平均值平均值平滑：箱中每一個值被箱中的平均值替換平滑：箱中每一個值被箱中的平均值替換 按箱的按箱的中值中值平滑：箱中的每一個值被箱中的中值替換平滑：箱中的每一個值被箱中的中值替換 按箱的按箱的邊界邊界平滑：箱中的最大和最小值被視為箱邊界，箱中平滑：箱中的最大和最小值被視為箱邊界，箱中 的每一個值被最近的邊界值替換。的每一個值被最近的邊界值替換。 如何處理噪聲數(shù)據(jù)如何處理噪聲數(shù)據(jù) 等深分箱等深分箱

12、 (binning): 按記錄數(shù)進(jìn)行分箱，每箱具有相同的記錄數(shù)，每箱按記錄數(shù)進(jìn)行分箱，每箱具有相同的記錄數(shù)，每箱 的記錄數(shù)稱為箱的權(quán)重，也稱箱子的深度。的記錄數(shù)稱為箱的權(quán)重，也稱箱子的深度。 示例：示例： 已知一組價格數(shù)據(jù)：已知一組價格數(shù)據(jù)：15,21,24,21,25,4,8,34,28 現(xiàn)用等深（深度為現(xiàn)用等深（深度為3）分箱方法對其進(jìn)行平滑，以對數(shù)據(jù)中的噪聲進(jìn)行）分箱方法對其進(jìn)行平滑，以對數(shù)據(jù)中的噪聲進(jìn)行 處理。處理。 思考：思考：根據(jù)根據(jù)bin中值進(jìn)行中值進(jìn)行 平滑的結(jié)果？平滑的結(jié)果？ 結(jié)果：結(jié)果： Bin1：8、8、8； Bin2：21、21、21； Bin3：28、28、28 在該

13、例中，在該例中，price數(shù)據(jù)首先被劃分并存人等深的箱中數(shù)據(jù)首先被劃分并存人等深的箱中(深度深度 3)。 v 對于按對于按箱平均值箱平均值平滑，箱中每一個值被箱中的平均值替換。平滑，箱中每一個值被箱中的平均值替換。 例如，箱例如，箱1中的值中的值4，8和和15的平均值是的平均值是9；這樣，該箱中的每；這樣，該箱中的每 一個值被替換為一個值被替換為9。 v 對于按對于按箱邊界箱邊界平滑，箱中的平滑，箱中的最大和最小值被視為箱邊界最大和最小值被視為箱邊界。箱。箱 中的每一個值被最近的邊界值替換。中的每一個值被最近的邊界值替換。 v 類似地，可以使用按類似地，可以使用按箱中值箱中值平滑。此時，箱中的

14、每一個值被平滑。此時，箱中的每一個值被 箱中的中值替換。箱中的中值替換。 如何處理噪聲數(shù)據(jù)如何處理噪聲數(shù)據(jù) 等寬分箱等寬分箱 (binning): 在整個屬性值的區(qū)間上平均分布，即每個箱的區(qū)間在整個屬性值的區(qū)間上平均分布，即每個箱的區(qū)間 范圍設(shè)定為一個常量，稱為箱子的寬度。范圍設(shè)定為一個常量，稱為箱子的寬度。 示例：示例： 已知一組價格數(shù)據(jù)：已知一組價格數(shù)據(jù)：15,21,24,21,25,4,8,34,28 現(xiàn)用等寬（寬度為現(xiàn)用等寬（寬度為10）分箱方法對其進(jìn)行平滑，以對數(shù)據(jù)中的噪聲進(jìn)）分箱方法對其進(jìn)行平滑，以對數(shù)據(jù)中的噪聲進(jìn) 行處理。行處理。 結(jié)果：結(jié)果： 先排序：先排序：4，8，15，21

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

16、（人民幣元）：排序后的值（人民幣元）： 800，1000，1200，1500，1500，1800，2000， 2300，2500，2800，3000，3500，4000，4500， 4800，5000 要求：分別用等深分箱方法要求：分別用等深分箱方法(箱深為箱深為4）、等寬分箱方法）、等寬分箱方法 （寬度為（寬度為1000）對其進(jìn)行平滑，以對數(shù)據(jù)中的噪聲進(jìn)行）對其進(jìn)行平滑，以對數(shù)據(jù)中的噪聲進(jìn)行 處理。處理。 （1）等深分箱結(jié)果：）等深分箱結(jié)果： （1）首先，劃分為等深的箱：）首先，劃分為等深的箱： 箱箱1（800，1000，1200，1500）；）； 箱箱2（1500，1800，2000，23

17、00）；）； 箱箱3（2500，2800，3000，3500）；）； 箱箱4（4000，4500，4800，5000） （2）按箱的平均值平滑，結(jié)果為：）按箱的平均值平滑，結(jié)果為： 箱箱1（1125，1125 ，1125 ，1125 ）；）； 箱箱2（1900，1900，1900，1900）；）； 箱箱3（2950，2950，2950，2950）；）； 箱箱4（4575，4575 ，4575 ，4575 ） （1）等深分箱結(jié)果：）等深分箱結(jié)果： （2）按箱的中值平滑，結(jié)果為：）按箱的中值平滑，結(jié)果為： 箱箱1（1100，1100 ，1100 ，1100 ）；）； 箱箱2（1900，1900，1

18、900，1900）；）； 箱箱3（2900，2900，2900，2900）；）； 箱箱4（4650，4650 ，4650 ，4650 ） （2）按箱的邊界值平滑，結(jié)果為：）按箱的邊界值平滑，結(jié)果為： 箱箱1（800，800，1500，1500）；）； 箱箱2（1500，1500，2300，2300）；）； 箱箱3（2500，2500，3500，3500）；）； 箱箱4（4000，4000，5000，5000） （2）等寬分箱結(jié)果：）等寬分箱結(jié)果： （1）首先，劃分為等寬的箱：）首先，劃分為等寬的箱： 箱箱1（800，1000，1200，1500，1500，1800）；）； 箱箱2（2000，2

19、300，2500，2800，3000）；）； 箱箱3（3500， 4000，4500 ）；）； 箱箱4（4800，5000） （2）按箱的平均值平滑，結(jié)果為：）按箱的平均值平滑，結(jié)果為： 箱箱1（1300，1300 ，1300 ，1300 ，1300 ，1300 ）；）； 箱箱2（2520，2520 ，2520 ，2520 ，2520 ）；）； 箱箱3（4000，4000 ，4000 ）；）； 箱箱4（4900，4900 ） （2）等寬分箱結(jié)果：）等寬分箱結(jié)果： （1）按箱的中值平滑，結(jié)果為：）按箱的中值平滑，結(jié)果為： 箱箱1（1350，1350 ，1350 ，1350 ，1350 ，1350

20、 ）；）； 箱箱2（2500，2500 ，2500 ，2500 ，2500 ）；）； 箱箱3（4000，4000 ，4000 ）；）； 箱箱4（4900，4900 ） （2）按箱的邊界值平滑，結(jié)果為：）按箱的邊界值平滑，結(jié)果為： 箱箱1（800，800 ，800 ，1800 ，1800 ，1800 ）；）； 箱箱2（2000，2000 ，3000 ，3000 ，3000 ）；）； 箱箱3（3500，3500 ，4000 ）；）； 箱箱4（4800，5000） 如何處理噪聲數(shù)據(jù)如何處理噪聲數(shù)據(jù) u2）聚類（）聚類（Clustering）：）： 相似或相鄰近的數(shù)據(jù)聚合在一起形成各個聚類集合，而那些

21、 位于聚類集合之外的數(shù)據(jù)對象，被視為孤立點(diǎn)。 特點(diǎn)：直接形成簇并對簇進(jìn)行描述，不需要任何先驗(yàn)知識。 通過聚類分通過聚類分 析查找孤立析查找孤立 點(diǎn)，消除噪點(diǎn)，消除噪 聲聲 如何處理噪聲數(shù)據(jù)如何處理噪聲數(shù)據(jù) u3）計(jì)算機(jī)和人工檢查結(jié)合）計(jì)算機(jī)和人工檢查結(jié)合 計(jì)算機(jī)檢測可疑數(shù)據(jù)，然后對它們進(jìn)行人工判斷 u4）回歸）回歸 發(fā)現(xiàn)兩個相關(guān)的變量之間的變化模式，利用回歸分析方 法所獲得的擬合函數(shù)，幫助平滑數(shù)據(jù)及除去噪聲。 x y y = x + 1 X1 Y1 Y1 許多數(shù)據(jù)平滑的方法也是涉及離散化的數(shù)據(jù)歸約方法許多數(shù)據(jù)平滑的方法也是涉及離散化的數(shù)據(jù)歸約方法 。例如，上面介紹的分箱技術(shù)減少了每個屬性的不同

22、值。例如，上面介紹的分箱技術(shù)減少了每個屬性的不同值 的數(shù)量。的數(shù)量。 另外，概念分層是一種數(shù)據(jù)離散化形式，也可以用于另外，概念分層是一種數(shù)據(jù)離散化形式，也可以用于 數(shù)據(jù)平滑。例如，數(shù)據(jù)平滑。例如，price的概念分層可以把的概念分層可以把price的值映射的值映射 到到inexpensive，moderately_priced和和expensive，從而減，從而減 少了挖掘過程所處理的值的數(shù)量。少了挖掘過程所處理的值的數(shù)量。 注意：注意： 3. 3. 不一致數(shù)據(jù)的處理？不一致數(shù)據(jù)的處理？ 40 不一致數(shù)據(jù)不一致數(shù)據(jù) 處理不一致數(shù)據(jù)的方式： l人工更正 l利用知識工程工具：如，如果知道屬性間的函

23、數(shù)依賴 關(guān)系，可以據(jù)此查找違反函數(shù)依賴的值。 l 數(shù)據(jù)字典：在將不同操作性數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行集成 時，也會帶來數(shù)據(jù)的不一致。如：一個給定的屬性在不 同的數(shù)據(jù)庫中可能具有不同的名字，如姓名在一個數(shù)據(jù) 庫中為Bill，在另一個數(shù)據(jù)庫中可能為B。對此，可根據(jù) 數(shù)據(jù)字典中提供的信息，消除不一致。 4.2 數(shù)據(jù)集成和變換數(shù)據(jù)集成和變換 q 數(shù)據(jù)挖掘所需要的海量數(shù)據(jù)集往往涉及多個數(shù)據(jù)源， 因此，在信息處理之前需要合并這些數(shù)據(jù)源存儲的數(shù) 據(jù)。 q 如果原始數(shù)據(jù)的形式不適合信息處理算法的需要，就 要進(jìn)行數(shù)據(jù)變換。 1）數(shù)據(jù)集成）數(shù)據(jù)集成：將來自多個數(shù)據(jù)源的數(shù)據(jù)合并到一起： 2）數(shù)據(jù)變換）數(shù)據(jù)變換：對數(shù)據(jù)進(jìn)行規(guī)

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

25、實(shí)世界的實(shí)體 如：如何確信一個數(shù)據(jù)庫中的customer_id和另一個數(shù) 據(jù)庫中的cust_number是同一實(shí)體。 通常，數(shù)據(jù)庫的數(shù)據(jù)字典數(shù)據(jù)字典和數(shù)據(jù)倉庫的元數(shù)據(jù)元數(shù)據(jù)，可幫 助避免模式集成中的錯誤。 46 （2 2）數(shù)據(jù)冗余問題）數(shù)據(jù)冗余問題 數(shù)據(jù)冗余問題： v同一屬性值不同的數(shù)據(jù)庫中會有不同的字段名； v一個屬性可以由另外一個表導(dǎo)出，如：一個顧客數(shù)據(jù) 表中的平均月收入屬性，可以根據(jù)月收入屬性計(jì)算出 來。 47 （2 2）數(shù)據(jù)冗余問題）數(shù)據(jù)冗余問題 數(shù)據(jù)冗余問題： 有些冗余可以被相關(guān)分析檢測到： BA BA n BBAA r ) 1( )( , 如果變量如果變量A、B間具有較高的相關(guān)系數(shù)

26、，表明間具有較高的相關(guān)系數(shù)，表明A或或B可以可以 作為冗余而去掉。作為冗余而去掉。 除了檢查屬性是否冗余外，還要檢查記錄行的冗余。 48 (3)(3)數(shù)據(jù)值沖突問題數(shù)據(jù)值沖突問題 數(shù)據(jù)值沖突 對現(xiàn)實(shí)世界的同一實(shí)體，來自不同數(shù)據(jù)源的屬性值可 能不同。 產(chǎn)生的原因：表示、比例或編碼不同。 如：重量屬性在一個系統(tǒng)中可能以公制單位存放，而 在另一系統(tǒng)中可能以英制單位存放；同一商品的價格屬 性值不同地域采用不同價格單位；不同學(xué)校的成績單可 能以百分制、五分制及其他等級制來存放等等。 2. 2. 數(shù)據(jù)變換？數(shù)據(jù)變換？ 50 數(shù)據(jù)變換數(shù)據(jù)變換 數(shù)據(jù)變換：將數(shù)據(jù)轉(zhuǎn)換成適合數(shù)據(jù)挖掘的形式。涉及內(nèi)容： （1）平滑

27、）平滑：去掉數(shù)據(jù)中的噪聲，將連續(xù)的數(shù)據(jù)離散化： 分箱 聚類 回歸。 （2）聚集）聚集：對數(shù)據(jù)進(jìn)行匯總和聚集 Avg(), count(), sum(), min(), max(), 如，每天銷售額（數(shù)據(jù)）可以進(jìn)行聚集操作以獲得每 月或每年的總額。 可用來構(gòu)造數(shù)據(jù)立方體。 51 數(shù)據(jù)變換數(shù)據(jù)變換 數(shù)據(jù)變換：將數(shù)據(jù)轉(zhuǎn)換成適合數(shù)據(jù)挖掘的形式。涉及內(nèi)容： （3）數(shù)據(jù)概化）數(shù)據(jù)概化：使用概念分層，用更抽象（更高層次）的概 念來取代低層次或數(shù)據(jù)層的數(shù)據(jù)對象 如，街道屬性，可以泛化到更高層次的概念，如城市、 國家； 同樣，對于數(shù)值型的屬性，如年齡屬性，可以映射到 更高層次的概念，如年輕、中年和老年。 52

28、數(shù)據(jù)變換數(shù)據(jù)變換 數(shù)據(jù)變換：將數(shù)據(jù)轉(zhuǎn)換成適合數(shù)據(jù)挖掘的形式。涉及內(nèi)容： （4）規(guī)范化）規(guī)范化：將數(shù)據(jù)按比例進(jìn)行縮放，使之落入一個特定的 區(qū)域，以消除數(shù)值型屬性因大小不一而造成的挖掘結(jié)果的偏差。 如將工資收入屬性值映射到-1.0, 1.0的范圍內(nèi)。 常用的方法： 最小最小-最大規(guī)范化；最大規(guī)范化； 零零-均值規(guī)范化（均值規(guī)范化（z-score規(guī)范化）；規(guī)范化）； 小數(shù)定標(biāo)規(guī)范化小數(shù)定標(biāo)規(guī)范化。 規(guī)格化的目的：規(guī)格化的目的： 是將一個屬性取值范圍影射到一個特定范圍之內(nèi)，以是將一個屬性取值范圍影射到一個特定范圍之內(nèi)，以 消除數(shù)值性屬性因大小不一而造成挖掘結(jié)果的偏差。消除數(shù)值性屬性因大小不一而造成挖掘

29、結(jié)果的偏差。 數(shù)據(jù)變換數(shù)據(jù)變換規(guī)范化規(guī)范化 在正式進(jìn)行數(shù)據(jù)挖掘之前，尤其是使用基在正式進(jìn)行數(shù)據(jù)挖掘之前，尤其是使用基于對象距離于對象距離 的挖掘算法時，必須進(jìn)行數(shù)據(jù)的規(guī)格化。的挖掘算法時，必須進(jìn)行數(shù)據(jù)的規(guī)格化。 如對于一個顧客信息數(shù)據(jù)庫中如對于一個顧客信息數(shù)據(jù)庫中年齡年齡屬性或?qū)傩曰蚬べY工資屬性，屬性， 由于工資屬性的取值比年齡屬性的取值要大得多，若不進(jìn)由于工資屬性的取值比年齡屬性的取值要大得多，若不進(jìn) 行規(guī)格化處理，基于工資屬性的距離計(jì)算值將遠(yuǎn)遠(yuǎn)超過基行規(guī)格化處理，基于工資屬性的距離計(jì)算值將遠(yuǎn)遠(yuǎn)超過基 于年齡屬性的計(jì)算值，這就意味著工資屬性的作用在整個于年齡屬性的計(jì)算值，這就意味著工資屬性的

30、作用在整個 數(shù)據(jù)對象的距離計(jì)算中被錯誤放大了。數(shù)據(jù)對象的距離計(jì)算中被錯誤放大了。 數(shù)據(jù)變換數(shù)據(jù)變換規(guī)范化規(guī)范化 55 數(shù)據(jù)變換數(shù)據(jù)變換規(guī)范化規(guī)范化 數(shù)據(jù)規(guī)范化：將數(shù)據(jù)按比例縮放至一個小的特定區(qū)間： 1）最小最小最大規(guī)范化最大規(guī)范化：假定minA和maxA分別為屬性A的最 小和最大值，則通過下面公式將A的值映射到區(qū)間new_min, new_max中的v： AAA AA A minnewminnewmaxnew minmax minv v_)_( 例：例：假定屬性income的最小與最大值分別為$12000和$98000， 可根據(jù)最小最大規(guī)范化方法將其范圍映射到0,1： 如：屬性值$73600將

31、變換為： (73600-12000)/(98000-12000)*(1-0)+0=0.716 56 數(shù)據(jù)變換數(shù)據(jù)變換規(guī)范化規(guī)范化 2）z-scorez-score規(guī)范化規(guī)范化（零均值規(guī)范化）： 將屬性A的值根據(jù)其平均值和標(biāo)準(zhǔn)差進(jìn)行規(guī)范化； 常用于屬性最大值與最小值未知，或使用最小最大規(guī)范 化方法會出現(xiàn)異常數(shù)據(jù)的情況。 A A devstandard meanv v 其中，meanA、standard-devA分別為屬性A取值的均值和標(biāo) 準(zhǔn)差。 例：例：假定屬性income的平均值與標(biāo)準(zhǔn)差分別為$54000和 $16000，使用z-score規(guī)范化，則屬性值$73600將變換為： (73600-

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

33、留規(guī)范化參數(shù)（如平均值和標(biāo)準(zhǔn)差，如果 使用使用z-score規(guī)范化），以便將來的數(shù)據(jù)可以用一致規(guī)范化），以便將來的數(shù)據(jù)可以用一致 的方式規(guī)范化。的方式規(guī)范化。 注意：注意： 59 數(shù)據(jù)變換數(shù)據(jù)變換 數(shù)據(jù)變換：將數(shù)據(jù)轉(zhuǎn)換成適合數(shù)據(jù)挖掘的形式。涉及內(nèi)容： （5）屬性構(gòu)造）屬性構(gòu)造： 利用已有屬性集構(gòu)造出新的屬性，并加入到現(xiàn)有屬性 集中以幫助挖掘更深層次的模式知識，提高挖掘結(jié)果 的準(zhǔn)確性； 如，根據(jù)寬、高屬性，可以構(gòu)造一個新屬性：面積。 4.3 4.3 數(shù)據(jù)歸約數(shù)據(jù)歸約 u對大規(guī)模數(shù)據(jù)庫內(nèi)容進(jìn)行復(fù)雜的數(shù)據(jù)分析常需要消耗 大量的時間，使得這樣的分析變得不現(xiàn)實(shí)和不可行； u數(shù)據(jù)歸約（data reduc

34、tion）：數(shù)據(jù)消減或約簡，是在 不影響最終挖掘結(jié)果的前提下，縮小所挖掘數(shù)據(jù)的規(guī)模。 u數(shù)據(jù)歸約技術(shù)可以用來得到數(shù)據(jù)集的歸約表示，它小 得多，但仍接近保持原數(shù)據(jù)的完整性。 u對歸約后的數(shù)據(jù)集進(jìn)行挖掘可提高挖掘的效率，并產(chǎn) 生相同（或幾乎相同）的結(jié)果。 4.3 4.3 數(shù)據(jù)歸約數(shù)據(jù)歸約 數(shù)據(jù)歸約的標(biāo)準(zhǔn)：數(shù)據(jù)歸約的標(biāo)準(zhǔn)： u用于數(shù)據(jù)歸約的時間不應(yīng)當(dāng)超過或“抵消”在歸約后 的數(shù)據(jù)集上挖掘節(jié)省的時間。 u歸約得到的數(shù)據(jù)比原數(shù)據(jù)小得多，但可以產(chǎn)生相同或 幾乎相同的分析結(jié)果。 4.3 4.3 數(shù)據(jù)歸約數(shù)據(jù)歸約 數(shù)據(jù)歸約的策略如下： u數(shù)據(jù)立方體聚集； u維歸約； u數(shù)據(jù)壓縮； u數(shù)值歸約； u離散化和概念

35、分層生成。 1. 1. 數(shù)據(jù)立方體聚集？數(shù)據(jù)立方體聚集？ 64 數(shù)據(jù)立方體聚集數(shù)據(jù)立方體聚集 2. 2. 維歸約？維歸約？ 66 維歸約維歸約 u維歸約：主要用于檢測并刪除不相關(guān)、弱相關(guān)或冗余的屬主要用于檢測并刪除不相關(guān)、弱相關(guān)或冗余的屬 性維性維 用于數(shù)據(jù)分析的數(shù)據(jù)可能包含數(shù)以百計(jì)的屬性，其中大部分 可能與挖掘任務(wù)不相關(guān)，是冗余的。如，分析顧客是否會在商 場購買mp3播放器，諸如顧客的電話號碼等屬性多半是不相關(guān)的。 維歸約通過刪除不相關(guān)的屬性（或維），而有效減少數(shù)據(jù)庫 的規(guī)模。 u最常用的方法：屬性子集選擇。 67 維歸約維歸約屬性子集選擇屬性子集選擇 q 目標(biāo)： 找出最小屬性集，確保新數(shù)據(jù)

36、集的概率分布盡可能 接近原數(shù)據(jù)集的概率分布。 q 如何找出原屬性的一個好的子集 d個屬性有2d個可能的子集。窮舉搜索找出屬性的 最佳子集可能是不現(xiàn)實(shí)的，特別是當(dāng)d的數(shù)目很大 時。 68 維歸約維歸約屬性子集選擇屬性子集選擇 q 啟發(fā)式算法： 對于屬性子集選擇，通常使用壓縮搜索空間的啟發(fā) 式算法。 它們的策略是做局部最優(yōu)選擇，期望由此導(dǎo)致全局 最優(yōu)解。 69 維歸約維歸約屬性子集選擇屬性子集選擇 常用的啟發(fā)式方法： 1 1）逐步向前選擇）逐步向前選擇： u該過程由空屬性集開始，選擇原屬性集中最好的屬性，并將 它添加到該集合中。 u在其后的每一次迭代，將原屬性集剩下的屬性中的最好的屬 性添加到該集

37、合中。 u 如：遺傳算法是遺傳算法是一種基于生物進(jìn)化論和分子遺傳學(xué)的全局隨 機(jī)搜索算法。 70 維歸約維歸約屬性子集選擇屬性子集選擇 常用的啟發(fā)式方法： 2）逐步向后刪除：）逐步向后刪除： 由整個屬性集開始，每一步都刪除尚在屬性集中的最壞屬性。 直到無法選擇出最壞屬性或滿足一定的閾值為止。 如：粗糙集理論粗糙集理論， 利用定義的數(shù)據(jù)集合U上的等價關(guān)系對U 進(jìn)行劃分，對于數(shù)據(jù)表來說，這種等價關(guān)系可以是某個屬性， 或者是幾個屬性的集合。因此，按照不同屬性的組合就把數(shù) 據(jù)表劃分成不同的基本類，在這些基本類的基礎(chǔ)上進(jìn)一步求 得最小約簡集。 71 維歸約維歸約屬性子集選擇屬性子集選擇 常用的啟發(fā)式方法：

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

39、壓縮算法分為兩類： v 無損壓縮（loseless）：可以不丟失任何信息地還 原壓縮數(shù)據(jù)；如：字符串壓縮 v 有損壓縮（lossy）：只能重新構(gòu)造原數(shù)據(jù)的近似 表示；如：音頻/視頻壓縮。 76 77 數(shù)據(jù)壓縮數(shù)據(jù)壓縮 兩類： 1）無損壓縮：指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原， 解壓縮)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同。 u即：數(shù)據(jù)經(jīng)過壓縮后，信息不受損失，還能完全恢復(fù)到壓縮 前的原樣。 u壓縮軟件：Zip或RAR。 78 數(shù)據(jù)壓縮數(shù)據(jù)壓縮 兩類： 2）有損壓縮：又稱破壞型壓縮，即將次要的信息數(shù)據(jù)壓縮掉， 犧牲一些質(zhì)量來減少數(shù)據(jù)量，使壓縮比提高。 u常用于壓縮聲音、圖像以及視頻。音頻能夠

40、在沒有察覺的質(zhì) 量下降情況下實(shí)現(xiàn) 10:1 的壓縮比，視頻能夠在稍微觀察質(zhì)量 下降的情況下實(shí)現(xiàn)如 300:1 這樣非常大的壓縮比。 常見算法：JPEG、MPEG、MP3等。 算法機(jī)理：小波變換小波變換或主成份分析主成份分析 4. 4. 數(shù)值歸約？數(shù)值歸約？ 80 數(shù)值歸約數(shù)值歸約 數(shù)值歸約：通過選擇替代的、較小的數(shù)據(jù)表示形式來減少通過選擇替代的、較小的數(shù)據(jù)表示形式來減少 數(shù)據(jù)量數(shù)據(jù)量。 （1）有參方法）有參方法： 通常使用一個參數(shù)模型來評估數(shù)據(jù)，該方法只需要存儲參數(shù)， 而不是實(shí)際數(shù)據(jù)，能大大減少數(shù)據(jù)量，但只對數(shù)值型數(shù)據(jù)有效。 如：線性回歸方法（最小二乘法）：Y=+X 81 數(shù)值歸約數(shù)值歸約 數(shù)

41、值歸約：通過選擇替代的、較小的數(shù)據(jù)表示形式來減少通過選擇替代的、較小的數(shù)據(jù)表示形式來減少 數(shù)據(jù)量數(shù)據(jù)量。 （2）無參方法）無參方法： 常見的有： v 直方圖；直方圖； v 聚類；聚類； v 取樣取樣。 82 1 1）直方圖）直方圖 直方圖：根據(jù)屬性的數(shù)據(jù)分布將其分成若干不相交的區(qū)間， 每個區(qū)間的高度與其出現(xiàn)的頻率成正比。 例：下面的數(shù)據(jù)是AllElectronics通常銷售的商品的單價表（已 排序）： 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,

42、20, 20,20,20,21,21, 21,21,25,25, 25,25,25,28,28,30,30,30。 試用直方圖表示，以壓縮數(shù)據(jù)。 83 1 1）直方圖）直方圖 頻率頻率-值對應(yīng)關(guān)系圖值對應(yīng)關(guān)系圖 84 2 2）聚類）聚類 聚類：將原數(shù)據(jù)集劃分成多個群或聚類。 u原則原則：同類中的數(shù)據(jù)彼此相似；不同類中的數(shù)據(jù)彼此不相似。 u相似相似：通常用空間距離度量 u 聚類的有效性有效性依賴于實(shí)際數(shù)據(jù)的內(nèi)在規(guī)律。 85 3 3）取樣）取樣 取樣（抽樣）：允許用數(shù)據(jù)的較小隨機(jī)樣本（子集）表示 大的數(shù)據(jù)集。 取樣方法： u 不放回簡單隨機(jī)取樣 （Simple Random Sampling Wi

43、thout Replacement, SRSWOR） u放回簡單隨機(jī)取樣（Simple Random Sampling With Replacement, SRSWR） u 聚類取樣：先聚類，后取樣 u 分層取樣：先分層，后取樣。 取樣取樣SRSSRS SRSWOR (簡單隨機(jī)選簡單隨機(jī)選 樣，不回放樣，不回放) SRSWR (簡單隨機(jī)選簡單隨機(jī)選 樣，回放樣，回放) 原始數(shù)據(jù)原始數(shù)據(jù) 87 取樣取樣 聚類采樣：聚類采樣： 首先將大數(shù)據(jù)集D劃分為M個互不相交的聚類， 然后再從M個類中的數(shù)據(jù)對象分別進(jìn)行隨機(jī)抽取，可最終獲得 聚類采樣的數(shù)據(jù)子集。 聚類采樣方法示意圖聚類采樣方法示意圖 88 聚類取

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

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

46、層概念分層 離散化方法離散化方法 常用的離散化方法： 1）分箱：）分箱：屬性的值可以通過將其分配到各分箱中而將其離散化。 v 利用每個分箱的均值或中數(shù)替換每個分箱中的值（利用均值或 中數(shù)進(jìn)行平滑）。 v 循環(huán)應(yīng)用這些操作處理每次操作結(jié)果，就可以獲得一個概念層 次樹。 離散化方法離散化方法 常用的離散化方法： 2）直方圖：）直方圖： l等寬直方圖中，將數(shù)據(jù)劃分成相等的部分或區(qū)間，如(0,100$)、 (100$,200$、(200$,300$. l等深直方圖：值被劃分使得每一部分包括相同個數(shù)的樣本。 離散化方法離散化方法 常用的離散化方法： 3）聚類分析聚類分析： v 聚類算法可以將數(shù)據(jù)集劃分為

47、若干類或組。 v 每個類構(gòu)成了概念分層樹的一個節(jié)點(diǎn)； v 每個類還可以進(jìn)一步分解為若干子類，從而構(gòu)造更低水平的層 次。 v 當(dāng)然類也可以合并起來構(gòu)成更高層次的概念水平。 4）基于熵的離散化基于熵的離散化：熵是一種信息度量的方法 5）通過自然劃分分段通過自然劃分分段 基于熵的離散化基于熵的離散化 思想：思想： u 考慮類別信息，遞歸計(jì)算信息熵，產(chǎn)生分層的離散化。 I(S)=初始不確初始不確 定性：定性： 基于熵的離散化基于熵的離散化 思想：思想： u 考慮類別信息，遞歸計(jì)算信息熵，產(chǎn)生分層的離散化。 給定一個數(shù)據(jù)元組的集合給定一個數(shù)據(jù)元組的集合S，基于熵對，基于熵對S離散化的方法如下：離散化的方

48、法如下： 1）屬性A中的每個取值可被認(rèn)為是一個潛在的區(qū)間邊界或閾值T。 例如，A的取值v可以將樣本S劃分為分別滿足Av和Av兩個子 集，這樣就創(chuàng)建了一個二元離散化。 2）對于數(shù)據(jù)集S，根據(jù)所劃分子集而獲得的最大熵增益來選擇閾 值，劃分后數(shù)據(jù)集S提供的信息如下： E(A)= 學(xué)習(xí)屬性學(xué)習(xí)屬性A之之 后的不確定性：后的不確定性： 基于熵的離散化基于熵的離散化 其中S1和S2分別對應(yīng)于S中滿足條件：AT與AT，的樣本。 對給定的集合，熵函數(shù)Ent根據(jù)集合中樣本的類分布來計(jì)算。例 如，給定m個不同類別，S1的熵就是： 其中pi為類i在S1中出現(xiàn)的概率，等于S1中類i的樣本除以S1中樣 本的總行數(shù)。同理

49、，計(jì)算Ent(S2)。 3）確定閾值的過程遞歸的用于所得到的每個劃分，直到滿足某 個終止條件，如： Ent(S)-I(S,T) 信息增益不能低于信息增益不能低于： 基于熵的離散化基于熵的離散化 與迄今為止提到的其他方法不同，基于熵的離散化使用 了類別信息。這使得它更有可能將區(qū)間邊界定義在準(zhǔn)確位 置，有助于提高分類的準(zhǔn)確性。 此處用到的信息增益和信息熵也用于決策樹歸納。 自然劃分分段自然劃分分段 思想：思想： u 將數(shù)值區(qū)域劃分為相對一致的、易于閱讀的、看上去更 直觀或自然的區(qū)間。 聚類分析產(chǎn)生的概念分層可能會將一個工資區(qū)間劃分為： 51263.98, 60872.34 而通常數(shù)據(jù)分析人員希望看

50、到劃分的形式為50000，60000 u自然劃分的3-4-5規(guī)則規(guī)則?？梢詫?shù)值數(shù)據(jù)劃分為相對一致 和“自然”的區(qū)間。一般的，根據(jù)最重要的數(shù)字上的值區(qū) 域，遞歸的和逐層的將給定的數(shù)據(jù)區(qū)域劃分為3、4或5個等 寬區(qū)間。 自然劃分的自然劃分的3-4-5規(guī)則規(guī)則 規(guī)則的劃分步驟：規(guī)則的劃分步驟： 如果一個區(qū)間最高有效位最高有效位上跨越3，6，7或9個不同的值， 就將該區(qū)間劃分為3個等寬子區(qū)間；(72,3,2) 如果一個區(qū)間最高有效位最高有效位上跨越2，4，或8個不同的值， 就將該區(qū)間劃分為4個等寬子區(qū)間； 如果一個區(qū)間最高有效位最高有效位上跨越1，5，或10個不同的值， 就將該區(qū)間劃分為5個等寬子區(qū)

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

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

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

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

55、000$：劃分為5個子區(qū)間(0$,200$, (200$,400$, 400$,600$, (600$,800$, (800$,1000$. 第三個區(qū)間(1000$,2000$：劃分為5個子區(qū)間(1000$,1200$, (1200$,1400$, 1400$,1600$, (1600$,1800$, (1800$,2000$. 第四個區(qū)間(2000$,5000$：劃分為3個子區(qū)間(2000$,3000$, (3000$,4000$, (4000$,5000$。 類似的，如有必要，3-4-5規(guī)則可繼續(xù)在較低的層次上迭代。 3-4-5規(guī)則規(guī)則例子例子 (-$4000 -$5,000) (-$40

56、0 - 0) (-$400 - -$300) (-$300 - -$200) (-$200 - -$100) (-$100 - 0) (0 - $1,000) (0 - $200) ($200 - $400) ($400 - $600) ($600 - $800)($800 - $1,000) ($2,000 - $5, 000) ($2,000 - $3,000) ($3,000 - $4,000) ($4,000 - $5,000) ($1,000 - $2, 000) ($1,000 - $1,200) ($1,200 - $1,400) ($1,400 - $1,600) ($1,600 - $1,800) ($1,800 - $