1、數(shù)據(jù)挖掘系列講座三,7-8,王 燦,數(shù)據(jù)挖掘,0703004,數(shù)據(jù)預(yù)處理,為什么要預(yù)處理數(shù)據(jù)？,現(xiàn)實(shí)世界的數(shù)據(jù)是“骯臟的”數(shù)據(jù)多了，什么問題都會出現(xiàn) 不完整的：有些感興趣的屬性缺少屬性值，或僅包含聚集數(shù)據(jù) 含噪聲的：包含錯誤或者“孤立點(diǎn)” 不一致的：在編碼或者命名上存在差異 沒有高質(zhì)量的數(shù)據(jù)，就沒有高質(zhì)量的挖掘結(jié)果 高質(zhì)量的決策必須依賴高質(zhì)量的數(shù)據(jù) 數(shù)據(jù)倉庫需要對高質(zhì)量的數(shù)據(jù)進(jìn)行一致地集成,數(shù)據(jù)質(zhì)量的多維度量,一個廣為認(rèn)可的多維度量觀點(diǎn)： 精確度 完整度 一致性 合乎時機(jī) 可信度 附加價值 可訪問性 跟數(shù)據(jù)本身的含義相關(guān)的 內(nèi)在的、上下文的、表象的,數(shù)據(jù)預(yù)處理的主要任務(wù),數(shù)據(jù)清理 填寫空缺的值

2、，平滑噪聲數(shù)據(jù)，識別、刪除孤立點(diǎn)，解決不一致性 數(shù)據(jù)集成 集成多個數(shù)據(jù)庫、數(shù)據(jù)立方體或文件 數(shù)據(jù)變換 規(guī)范化和聚集 數(shù)據(jù)歸約 得到數(shù)據(jù)集的壓縮表示，它小得多，但可以得到相同或相近的結(jié)果 數(shù)據(jù)離散化 數(shù)據(jù)歸約的一部分，通過概念分層和數(shù)據(jù)的離散化來規(guī)約數(shù)據(jù)，對數(shù)字型數(shù)據(jù)特別重要,空缺值,數(shù)據(jù)并不總是完整的 例如：數(shù)據(jù)庫表中，很多條記錄的對應(yīng)字段沒有相應(yīng)值，比如銷售表中的顧客收入 引起空缺值的原因 設(shè)備異常 與其他已有數(shù)據(jù)不一致而被刪除 因?yàn)檎`解而沒有被輸入的數(shù)據(jù) 在輸入時，有些數(shù)據(jù)應(yīng)為得不到重視而沒有被輸入 對數(shù)據(jù)的改變沒有進(jìn)行日志記載 空缺值要經(jīng)過推斷而補(bǔ)上,如何處理空缺值,忽略元組：當(dāng)類標(biāo)號缺

3、少時通常這么做（假定挖掘任務(wù)涉及分類或描述），當(dāng)每個屬性缺少值的百分比變化很大時，它的效果非常差。 人工填寫空缺值：工作量大，可行性低 使用一個全局變量填充空缺值：比如使用unknown或- 使用屬性的平均值填充空缺值 使用與給定元組屬同一類的所有樣本的平均值 使用最可能的值填充空缺值：使用像Bayesian公式或判定樹這樣的基于推斷的方法,噪聲數(shù)據(jù),噪聲：一個測量變量中的隨機(jī)錯誤或偏差 引起噪聲數(shù)據(jù)的原因 數(shù)據(jù)收集工具的問題 數(shù)據(jù)輸入錯誤 數(shù)據(jù)傳輸錯誤 技術(shù)限制 命名規(guī)則的不一致,如何處理噪聲數(shù)據(jù),分箱(binning): 首先排序數(shù)據(jù)，并將他們分到等深的箱中 然后可以按箱的平均值平滑、按箱

4、中值平滑、按箱的邊界平滑等等 聚類： 監(jiān)測并且去除孤立點(diǎn) 計算機(jī)和人工檢查結(jié)合 計算機(jī)檢測可疑數(shù)據(jù)，然后對它們進(jìn)行人工判斷 回歸 通過讓數(shù)據(jù)適應(yīng)回歸函數(shù)來平滑數(shù)據(jù),數(shù)據(jù)平滑的分箱方法,price的排序后數(shù)據(jù)（單位：美元）：4，8，15，21，21，24，25，28，34 劃分為（等深的）箱： 箱1：4，8，15 箱2：21，21，24 箱3：25，28，34 用箱平均值平滑： 箱1：9，9，9 箱2：22，22，22 箱3：29，29，29 用箱邊界平滑： 箱1：4，4，15 箱2：21，21，24 箱3：25，25，34,聚類,通過聚類分析查找孤立點(diǎn)，消除噪聲,回歸,x,y,y = x +

5、1,X1,Y1,Y1,數(shù)據(jù)集成,數(shù)據(jù)集成： 將多個數(shù)據(jù)源中的數(shù)據(jù)整合到一個一致的存儲中 模式集成： 整合不同數(shù)據(jù)源中的元數(shù)據(jù) 實(shí)體識別問題：匹配來自不同數(shù)據(jù)源的現(xiàn)實(shí)世界的實(shí)體，比如：A.cust-id=B.customer_no 檢測并解決數(shù)據(jù)值的沖突 對現(xiàn)實(shí)世界中的同一實(shí)體，來自不同數(shù)據(jù)源的屬性值可能是不同的 可能的原因：不同的數(shù)據(jù)表示，不同的度量等等,處理數(shù)據(jù)集成中的冗余數(shù)據(jù),集成多個數(shù)據(jù)庫時，經(jīng)常會出現(xiàn)冗余數(shù)據(jù) 同一屬性在不同的數(shù)據(jù)庫中會有不同的字段名 一個屬性可以由另外一個表導(dǎo)出，如“年薪” 有些冗余可以被相關(guān)分析檢測到 仔細(xì)將多個數(shù)據(jù)源中的數(shù)據(jù)集成起來，能夠減少或避免結(jié)果數(shù)據(jù)中的冗余

6、與不一致性，從而可以提高挖掘的速度和質(zhì)量。,數(shù)據(jù)變換,平滑：去除數(shù)據(jù)中的噪聲 （分箱、聚類、回歸） 聚集：匯總，數(shù)據(jù)立方體的構(gòu)建 數(shù)據(jù)概化：沿概念分層向上概化 規(guī)范化：將數(shù)據(jù)按比例縮放，使之落入一個小的特定區(qū)間 最小最大規(guī)范化 z-score規(guī)范化 小數(shù)定標(biāo)規(guī)范化 屬性構(gòu)造 通過現(xiàn)有屬性構(gòu)造新的屬性，并添加到屬性集中；以增加對高維數(shù)據(jù)的結(jié)構(gòu)的理解和精確度,數(shù)據(jù)變換規(guī)范化,最小最大規(guī)范化 z-score規(guī)范化 小數(shù)定標(biāo)規(guī)范化,其中，j是使 Max(| |)1的最小整數(shù),數(shù)據(jù)歸約策略,數(shù)據(jù)倉庫中往往存有海量數(shù)據(jù)，在其上進(jìn)行復(fù)雜的數(shù)據(jù)分析與挖掘需要很長的時間 數(shù)據(jù)歸約 數(shù)據(jù)歸約可以用來得到數(shù)據(jù)集的歸

7、約表示，它小得多，但可以產(chǎn)生相同的（或幾乎相同的）分析結(jié)果 數(shù)據(jù)歸約策略 數(shù)據(jù)立方體聚集 維歸約 數(shù)據(jù)壓縮 數(shù)值歸約 離散化和概念分層產(chǎn)生 用于數(shù)據(jù)歸約的時間不應(yīng)當(dāng)超過或“抵消”在歸約后的數(shù)據(jù)上挖掘節(jié)省的時間。,數(shù)據(jù)立方體聚集,最底層的方體對應(yīng)于基本方體 基本方體對應(yīng)于感興趣的實(shí)體 在數(shù)據(jù)立方體中存在著不同級別的匯總 數(shù)據(jù)立方體可以看成方體的格 每個較高層次的抽象將進(jìn)一步減少結(jié)果數(shù)據(jù) 數(shù)據(jù)立方體提供了對預(yù)計算的匯總數(shù)據(jù)的快速訪問 使用與給定任務(wù)相關(guān)的最小方體 在可能的情況下，對于匯總數(shù)據(jù)的查詢應(yīng)當(dāng)使用數(shù)據(jù)立方體,維歸約,通過刪除不相干的屬性或維減少數(shù)據(jù)量 屬性子集選擇 找出最小屬性集，使得數(shù)據(jù)

8、類的概率分布盡可能的接近使用所有屬性的原分布 減少出現(xiàn)在發(fā)現(xiàn)模式上的屬性的數(shù)目，使得模式更易于理解 啟發(fā)式的（探索性的）方法 逐步向前選擇 逐步向后刪除 向前選擇和向后刪除相結(jié)合 判定歸納樹,數(shù)據(jù)壓縮,有損壓縮 VS. 無損壓縮 字符串壓縮 有廣泛的理論基礎(chǔ)和精妙的算法 通常是無損壓縮 在解壓縮前對字符串的操作非常有限 音頻/視頻壓縮 通常是有損壓縮，壓縮精度可以遞進(jìn)選擇 有時可以在不解壓整體數(shù)據(jù)的情況下，重構(gòu)某個片斷 兩種有損數(shù)據(jù)壓縮的方法：小波變換和主要成分分析,數(shù)值歸約,通過選擇替代的、較小的數(shù)據(jù)表示形式來減少數(shù)據(jù)量 有參方法：使用一個參數(shù)模型估計數(shù)據(jù)，最后只要存儲參數(shù)即可。 線性回歸方

9、法：Y=+X 多元回歸：線性回歸的擴(kuò)充 對數(shù)線性模型：近似離散的多維數(shù)據(jù)概率分布 無參方法： 直方圖 聚類 選樣,直方圖,一種流行的數(shù)據(jù)歸約技術(shù) 將某屬性的數(shù)據(jù)劃分為不相交的子集，或桶，桶中放置該值的出現(xiàn)頻率 桶和屬性值的劃分規(guī)則 等寬 等深 V-最優(yōu) MaxDiff,聚類,將數(shù)據(jù)集劃分為聚類，然后通過聚類來表示數(shù)據(jù)集 如果數(shù)據(jù)可以組成各種不同的聚類，則該技術(shù)非常有效，反之如果數(shù)據(jù)界線模糊，則方法無效 數(shù)據(jù)可以分層聚類，并被存儲在多層索引樹中 聚類的定義和算法都有很多選擇,選樣,允許用數(shù)據(jù)的較小隨機(jī)樣本（子集）表示大的數(shù)據(jù)集 對數(shù)據(jù)集D的樣本選擇： 簡單隨機(jī)選擇n個樣本，不回放：由D的N個元組

10、中抽取n個樣本 簡單隨機(jī)選擇n個樣本，回放：過程同上，只是元組被抽取后，將被回放，可能再次被抽取 聚類選樣：D中元組被分入M個互不相交的聚類中，可在其中的m個聚類上進(jìn)行簡單隨機(jī)選擇（mM） 分層選樣：D被劃分為互不相交的“層”，則可通過對每一層的簡單隨機(jī)選樣得到D的分層選樣,選樣SRS,SRSWOR (簡單隨機(jī)選 樣，不回放),SRSWR (簡單隨機(jī)選 樣，回放),選樣聚類/分層選樣,原始數(shù)據(jù),聚類/分層選樣,離散化,三種類型的屬性值： 名稱型e.g. 無序集合中的值 序數(shù)e.g. 有序集合中的值 連續(xù)值e.g. 實(shí)數(shù) 離散化 將連續(xù)屬性的范圍劃分為區(qū)間 有效的規(guī)約數(shù)據(jù) 基于判定樹的分類挖掘

11、離散化的數(shù)值用于進(jìn)一步分析,離散化和概念分層,離散化 通過將屬性域劃分為區(qū)間，減少給定連續(xù)屬性值的個數(shù)。區(qū)間的標(biāo)號可以代替實(shí)際的數(shù)據(jù)值。 概念分層 通過使用高層的概念（比如：青年、中年、老年）來替代底層的屬性值（比如：實(shí)際的年齡數(shù)據(jù)值）來規(guī)約數(shù)據(jù),數(shù)據(jù)數(shù)值的離散化和概念分層生成,分箱（binning） 分箱技術(shù)遞歸的用于結(jié)果劃分，可以產(chǎn)生概念分層。 直方圖分析（histogram） 直方圖分析方法遞歸的應(yīng)用于每一部分，可以自動產(chǎn)生多級概念分層。 聚類分析 將數(shù)據(jù)劃分成簇，每個簇形成同一個概念層上的一個節(jié)點(diǎn)，每個簇可再分成多個子簇，形成子節(jié)點(diǎn)。 基于熵的離散化 通過自然劃分分段,通過自然劃分分段

12、,將數(shù)值區(qū)域劃分為相對一致的、易于閱讀的、看上去更直觀或自然的區(qū)間。 聚類分析產(chǎn)生概念分層可能會將一個工資區(qū)間劃分為：51263.98, 60872.34 通常數(shù)據(jù)分析人員希望看到劃分的形式為50000，60000 自然劃分的3-4-5規(guī)則常被用來將數(shù)值數(shù)據(jù)劃分為相對一致，“更自然”的區(qū)間,自然劃分的3-4-5規(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ū)間； 將該規(guī)則遞歸的應(yīng)用于每個子區(qū)間，產(chǎn)生給定數(shù)值屬性的概念分層； 對于數(shù)據(jù)集中出現(xiàn)的最大值和最小值的極端分布，為了避免上述方法出現(xiàn)的結(jié)果扭曲，可以在頂層分段時，選用一個大部分的概率空間。e.g. 5%-95%,3-4-5規(guī)則例子,(-$4000 -$5,000),第四步,分類數(shù)據(jù)的概念分層生成,分類數(shù)據(jù)是指無序的離散數(shù)據(jù)，它有有限個值（可能很多個）。 分類數(shù)據(jù)的概念分層生成方法： 由用戶或?qū)＜以谀Ｊ郊夛@式的說明屬性的部分序。 通過顯示數(shù)據(jù)分組說明分層結(jié)構(gòu)的一部分。 說明屬性集，但不說明它們的偏序，然后系統(tǒng)根據(jù)算法自