第3章數(shù)據(jù)預(yù)處理2014-111PPT課件目錄3.1數(shù)據(jù)預(yù)處理：概覽3.2數(shù)據(jù)清洗3.3數(shù)據(jù)聚合3.4數(shù)據(jù)刪減3.5數(shù)據(jù)轉(zhuǎn)換和數(shù)據(jù)離散化3.6總結(jié)2PPT課件數(shù)據(jù)預(yù)處理

真實(shí)世界中的數(shù)據(jù)庫對噪聲、缺失、以及不一致的數(shù)據(jù)是高度敏感的，因為這些數(shù)據(jù)常常容量很大，并且很可能是多來源的異質(zhì)數(shù)據(jù)。

數(shù)據(jù)的低質(zhì)量會導(dǎo)致低質(zhì)量的數(shù)據(jù)挖掘結(jié)果?！叭绾翁幚頂?shù)據(jù)，以有助于提到數(shù)據(jù)的質(zhì)量和數(shù)據(jù)挖掘的效果呢？數(shù)據(jù)被如何處理能夠提高挖掘過程的高效性和簡易型呢？”

這里有幾種數(shù)據(jù)預(yù)處理的技術(shù)，包括：數(shù)據(jù)清洗，數(shù)據(jù)聚合，數(shù)據(jù)刪減，數(shù)據(jù)轉(zhuǎn)換。這些技術(shù)能提升挖掘算法的精確性和效率。它們并非相對獨(dú)立，是共同工作的。比如，數(shù)據(jù)清洗也包含數(shù)據(jù)轉(zhuǎn)化以去除錯誤數(shù)據(jù)。3PPT課件3.1數(shù)據(jù)預(yù)處理：概覽3.1.1數(shù)據(jù)質(zhì)量：為什么做數(shù)據(jù)預(yù)處理？

如果數(shù)據(jù)滿足了人們的預(yù)期用途的需求，則數(shù)據(jù)質(zhì)量好。數(shù)據(jù)質(zhì)量包含很多因素，如：精確性、完整性、一致性、時效性、可信性以及可解釋性。

數(shù)據(jù)的不精確、不完整以及不一致是大型真實(shí)世界數(shù)據(jù)庫以及數(shù)據(jù)倉庫的常見特點(diǎn)。

4PPT課件數(shù)據(jù)的不精確性不精確數(shù)據(jù)有很多可能的原因：數(shù)據(jù)收集工具可能錯誤，數(shù)據(jù)記錄中很多人為的或計算機(jī)導(dǎo)致的的錯誤。用戶也可能在值當(dāng)他們不愿意暴露個人資料的時候在一些強(qiáng)制必須填寫的欄目故意提交了錯誤的資料（如生日直接用默認(rèn)值1月1日）。這是一些偽裝缺失的數(shù)據(jù)。數(shù)據(jù)在傳輸時也可能出錯。一些技術(shù)上的限制，例如并行同步數(shù)據(jù)的傳輸和計算時緩沖區(qū)間的有限性。不正確的數(shù)據(jù)也可能因為命名習(xí)慣或者數(shù)據(jù)編碼的不一致性，或者輸入域的格式不一致。重復(fù)的元組也需要進(jìn)行數(shù)據(jù)清洗。5PPT課件數(shù)據(jù)的不完整性導(dǎo)致數(shù)據(jù)的不完整性的原因也有很多：感興趣的屬性并不能總是可獲得，比如銷售交易數(shù)據(jù)中的客戶資料信息。另外，很可能因為在當(dāng)時的條目中，該屬性被認(rèn)為是不重要的。相關(guān)聯(lián)的數(shù)據(jù)沒有被記錄可能因為誤解或者設(shè)備故障的原因。6PPT課件不一致的數(shù)據(jù)

和其他數(shù)據(jù)記錄不一致的數(shù)據(jù)應(yīng)該被被刪掉。另外，數(shù)據(jù)歷史和修改可能被忽視。缺失的數(shù)據(jù)，特別是缺失了某些屬性值的元組，值可能需要被推斷。

數(shù)據(jù)質(zhì)量依賴于人們對數(shù)據(jù)的預(yù)期使用。兩個不同的用戶可能對一個給定的數(shù)據(jù)庫的質(zhì)量有不同的評估。

比如，一個市場分析員獲得了一個由顧客地址列表的數(shù)據(jù)庫。一些地址是過期或錯誤的，總體上有80%是精確的。市場分析員認(rèn)為這是一個針對目標(biāo)市場的很大的客戶數(shù)據(jù)庫，對數(shù)據(jù)的精確性很滿意。但是，銷售經(jīng)理可能認(rèn)為數(shù)據(jù)是不精確的。7PPT課件數(shù)據(jù)的時效性

時效性也可能影響數(shù)據(jù)質(zhì)量：

比如你在瀏覽AllElectronics公式的每月銷售獎金的數(shù)據(jù)分布。一些銷售代表在月末的時候沒有及時的提交他們的銷售記錄。在月末之后可能有一些數(shù)據(jù)的更正和調(diào)整。從每個月的時間周期來看，數(shù)據(jù)庫中存放的數(shù)據(jù)是不完整的。因為月末的數(shù)據(jù)沒有被及時的更新導(dǎo)致了數(shù)據(jù)質(zhì)量的負(fù)面性影響。8PPT課件數(shù)據(jù)的可信性和可解釋性

另外的兩個影響數(shù)據(jù)質(zhì)量的因素是可信性和可解釋性。

可信性反映用戶有多相信這些數(shù)據(jù)，可解釋性反應(yīng)數(shù)據(jù)有多容易被理解。

例如一個數(shù)據(jù)庫在某一時刻有一些錯誤，然后都被更正了。過去的錯誤導(dǎo)致了銷售部門用戶的大量問題，因此他們不再相信這些數(shù)據(jù)。這些數(shù)據(jù)可能使用了很多會計代碼，銷售部門不懂如何解釋。即使這些數(shù)據(jù)是精確完整一致和有時效性的，但是仍然被銷售部門用戶認(rèn)為是低質(zhì)量的。9PPT課件3.1.2數(shù)據(jù)預(yù)處理的主要任務(wù)數(shù)據(jù)預(yù)處理的主要步驟是：數(shù)據(jù)清洗數(shù)據(jù)聚合數(shù)據(jù)刪減數(shù)據(jù)轉(zhuǎn)換10PPT課件數(shù)據(jù)清洗

數(shù)據(jù)清洗的工作是清洗數(shù)據(jù)，通過填寫缺失的數(shù)據(jù)，平滑噪音數(shù)據(jù)，識別需要去除的離群點(diǎn)，以及解決不一致性。

如果用戶相信數(shù)據(jù)是臟數(shù)據(jù)，便不可能信任數(shù)據(jù)挖掘的結(jié)果。另外，臟數(shù)據(jù)可能導(dǎo)致挖掘過程中的混亂，導(dǎo)致不可靠的輸出結(jié)果。

即使絕大多數(shù)的挖掘方法都有處理數(shù)據(jù)不完整和噪聲的步驟，但仍然不夠健壯。通常，這些算法集中避免建模的函數(shù)對數(shù)據(jù)的過度擬合。

因此，有用的預(yù)處理的步驟是把你的數(shù)據(jù)通過一些數(shù)據(jù)清洗的例程工作來完成。11PPT課件數(shù)據(jù)聚合

如果你的分析中數(shù)據(jù)是多來源的，則需要進(jìn)行數(shù)據(jù)聚合工作，即聚合多種數(shù)據(jù)庫，數(shù)據(jù)立方，以及文件。

一個給定概念的屬性在不同數(shù)據(jù)庫中可能有不同的命名，導(dǎo)致了不一致性和冗余。

例如，顧客的主鍵屬性在一個數(shù)據(jù)庫中是custom_id,在另外的數(shù)據(jù)庫卻是cust_id。命名的不一致性也可能發(fā)生在屬性值的上面。

例如，一個數(shù)據(jù)庫中人名的第一個名字是”Bill”，在另一個中是”William”,第三個中是”B”.12PPT課件

同時，你懷疑一些屬性值是由其他屬性值計算的（比如年收入）。有大量的冗余數(shù)據(jù)會讓知識發(fā)現(xiàn)過程速度降低以及產(chǎn)生混亂。

因此，除了數(shù)據(jù)清洗，必須采取步驟來避免在數(shù)據(jù)聚合中出現(xiàn)冗余。通常，數(shù)據(jù)清洗和數(shù)據(jù)聚合在為數(shù)據(jù)倉庫準(zhǔn)備數(shù)據(jù)時被整合成一個預(yù)處理步驟。在數(shù)據(jù)清洗之外，在鑒別和去除因聚合導(dǎo)致的冗余數(shù)據(jù)的步驟。13PPT課件數(shù)據(jù)刪減

“我被選做分析的數(shù)據(jù)集非常大，這確信無疑的會減慢挖掘過程。是否有一個方法能夠在不影響數(shù)據(jù)挖掘的效果的情況下減小數(shù)據(jù)集呢？”這就是數(shù)據(jù)刪減。數(shù)據(jù)刪減能得到一個數(shù)據(jù)集的刪減集，比原來的數(shù)據(jù)小很多，但是能產(chǎn)生相同的（或幾乎相同的）分析結(jié)果。

數(shù)據(jù)刪減包括維度刪減和數(shù)據(jù)塊刪減。14PPT課件維度刪減：維度刪減是一種獲得原有數(shù)據(jù)的刪減或者壓縮集的數(shù)據(jù)編碼方案。比如，數(shù)據(jù)壓縮技術(shù)（小波分析、主成分分析）屬性子集選擇（去除不相關(guān)屬性），以及屬性構(gòu)造（如從原有數(shù)據(jù)集中建立小的更有用的屬性）數(shù)據(jù)塊刪減：數(shù)據(jù)被可選的更小的數(shù)據(jù)替換，使用參數(shù)模型（如回歸和對數(shù)-線性模型）或者非參數(shù)模型（直方圖，聚類，抽樣和數(shù)據(jù)聚集）。15PPT課件數(shù)據(jù)轉(zhuǎn)換

在神經(jīng)網(wǎng)絡(luò)、最近鄰分類以及聚類分析中，你可能使用一個基于距離的挖掘算法。

如果將數(shù)據(jù)標(biāo)準(zhǔn)化，按比例縮小到一個更小的范圍，如[0.0，1.0]中，可能會得到更好的效果。

你的顧客數(shù)據(jù)中可能包含年齡屬性和年薪屬性。年薪屬性會使用一個比年齡大得多的值范圍。因此，如果屬性是左非規(guī)范的，距離測量會在年薪上產(chǎn)生更大的距離權(quán)重。16PPT課件

離散化和概念層次生成也很有效。用于將原始數(shù)據(jù)值替換成范圍區(qū)間或者高層概念層級。例如，原始的年齡值被高層級的概念：年輕人，成年人和老年人替換。

離散化和概念層次生成是數(shù)據(jù)挖掘的強(qiáng)大工具，因為他們允許數(shù)據(jù)挖掘在更多抽象級別上進(jìn)行。

標(biāo)準(zhǔn)化、離散化和概念層次生成是數(shù)據(jù)轉(zhuǎn)換的幾種形式。17PPT課件多種預(yù)處理的形式18PPT課件預(yù)處理的作用

總之，真實(shí)世界中的數(shù)據(jù)更可能是臟的、不完整和不一致的。數(shù)據(jù)預(yù)處理技術(shù)可以提升數(shù)據(jù)質(zhì)量，因而提升接下來的挖掘過程的精確性和有效性。

數(shù)據(jù)預(yù)處理是知識發(fā)現(xiàn)過程的一個重要步驟，因為好的質(zhì)量抉擇基于好的質(zhì)量的數(shù)據(jù)。發(fā)現(xiàn)數(shù)據(jù)的異常，在早期進(jìn)行修正，減少被分析的數(shù)據(jù)會給決策制定帶來巨大的回報。19PPT課件3.2數(shù)據(jù)清洗3.2.1缺失值假設(shè)你需要分析AllElectronics的銷售和顧客數(shù)據(jù)。你注意到許多元組在一些屬性例如顧客收入上沒有記錄值。如何能填寫這些屬性的缺失值呢？有如下方法：1.忽略元組。常常在類別標(biāo)簽（假定是分類任務(wù)）缺失時這樣做。這種方法不是非常有效，除非元組包含若干缺失值的屬性。當(dāng)每個屬性上缺失的值占的比例變化很大時，這種方法特別糟糕。通過忽略這些元組，也不會使用這些元組剩下的屬性值。本來這些數(shù)據(jù)可以很有用的。20PPT課件2手工填寫缺失值。通常，這種方法耗時，并且對一個有很多缺失值的大型數(shù)據(jù)集來說并非可行。3使用一個全局常數(shù)來填寫缺失值。可以將所有缺失的屬性值用同一個常數(shù)，例如標(biāo)簽“Unknown”或者”-∞”來表示。如果缺失值被“Unknown”替換，挖掘算法可能錯誤的認(rèn)為形成了一個有趣的概念，因為他們都有一個共同的值”Unknown”.因此，即使這種方法很簡單，卻也并非不會出錯。4使用一個屬性的中心性測量來填寫缺失值。對于標(biāo)準(zhǔn)（對稱的）數(shù)據(jù)分布，可以使用平均值，對偏斜數(shù)據(jù)分布可以使用中值。21PPT課件5.使用給定元組的類別相同的所有樣本的均值或者中值。例如，如果根據(jù)顧客的信用風(fēng)險來分類顧客，可以計算和該顧客的信用風(fēng)險類別相同的所有顧客的收入均值，來填寫給定元組的缺失的收入屬性。如果對于給定類別數(shù)據(jù)分布是偏斜的，則使用中值。6.使用缺失值的最可能的值來填寫。值可以由回歸、使用Bayes公式的基于推理的工具，或者決策樹推理。如，使用你的數(shù)據(jù)集中的其他顧客的屬性，可以建立一個預(yù)測顧客缺失的收入值的決策樹。方法3-6改變了數(shù)據(jù)，即填寫的值可能是不正確的。其中，方法6是一種流行的策略。22PPT課件

需要重點(diǎn)指出的是，在某些情形，一個缺失的值并非意味著數(shù)據(jù)的錯誤！例如，當(dāng)申請信用卡時，申請者被要求提供駕駛證號碼。沒有駕駛證的自然就會在這一項不填寫。表格應(yīng)當(dāng)允許回答者做詳細(xì)說明，例如“不適合”。

軟件例程可能被使用來發(fā)現(xiàn)其他的空值（例如，“不知道？”或者“空”）。理想情況是，每一個屬性有一個或者多個針對空值情形的規(guī)則。這些規(guī)則可以詳細(xì)指明空值是否被允許或者種類值如何被處理和轉(zhuǎn)換。屬性域可以被留作空白，如果在隨后的商業(yè)過程中能夠被提供。

因此，即使在數(shù)據(jù)被獲取之后，我們能夠盡力去清洗，好的數(shù)據(jù)庫和數(shù)據(jù)表過程設(shè)計能在第一時間最小化缺失值和錯誤的數(shù)目。23PPT課件3.2.2噪聲數(shù)據(jù)

“什么是噪聲？”噪聲是度量變量的隨機(jī)錯誤或者偏差。

第2章中介紹的基本統(tǒng)計描述技術(shù)（箱子圖、散點(diǎn)圖）、數(shù)據(jù)可視化的技術(shù)科用來識別離群點(diǎn)，這些可能代表噪聲。給定一個數(shù)值屬性，例如價格，如何來平滑數(shù)據(jù)以去除噪聲呢？有如下技術(shù)：1、裝箱

裝箱方法通過參考數(shù)據(jù)值的“鄰居”（即該值周圍的數(shù)據(jù)）來平滑排好序的數(shù)據(jù)。24PPT課件排好序的數(shù)據(jù)被分布到一系列的“桶”,或箱子中。因為裝箱方法參考值的鄰居，所以使用的是局部平滑。有若干種裝箱技術(shù)：1）等頻裝箱。例如，價格屬性先被排序，然后被分割到箱子的大小為3的等頻箱子中。2）箱子均值平滑。箱子中的每個值被箱子的均值替代。3）箱子中值平滑。每個箱子值被箱子中值取代。4）箱子邊界平滑。箱子值被最靠近的邊界值（最大值或最小值）取代。箱子的寬度也大，平滑效果也越顯著。另外，等寬度的箱子，即每個箱子間隔是個相同的常數(shù)也常被使用。箱子技術(shù)也是一種數(shù)據(jù)離散化的技術(shù)。25PPT課件2、回歸：數(shù)據(jù)平滑也可以使用回歸的方法，即將數(shù)據(jù)值通過一個函數(shù)來表達(dá)。線性回歸是尋找兩個屬性（或變量）的最好的直線來通過一個屬性預(yù)測另外一個。多元線性回歸是線性回歸的擴(kuò)展。超過兩個的屬性被包含在其中，數(shù)據(jù)被擬合成一個高維超平面。3、離群點(diǎn)分析：通過聚類的方法可以檢測離群點(diǎn)。例如，相似的值被分組，或“簇”。值落在簇之外的被認(rèn)為是離群點(diǎn)。26PPT課件4、其他方法：

很多數(shù)據(jù)平滑技術(shù)也適用于數(shù)據(jù)離散化和數(shù)據(jù)削減。例如，裝箱技術(shù)削減了每個屬性的不同值的個數(shù)。在基于邏輯的數(shù)據(jù)挖掘方法例如決策樹中，因為需要不斷重復(fù)的在排序數(shù)據(jù)上做值的比較，因此這相當(dāng)于是數(shù)據(jù)削減。

概念分層是數(shù)據(jù)離散化的一種，可以用來做數(shù)據(jù)平滑。一個概念分層例如價格，可以映射真實(shí)的價格值到便宜、中等、昂貴上。這樣削減了挖掘過程需要處理的數(shù)據(jù)值的個數(shù)。一些分類方法有內(nèi)置的數(shù)據(jù)平滑機(jī)制。27PPT課件3.2.3數(shù)據(jù)清洗作為一個過程

“數(shù)據(jù)清洗是一個巨大的工作。數(shù)據(jù)清洗作為一個過程怎么樣呢？在處理這個任務(wù)是人如何精確的進(jìn)行呢？有任何可用的工具嗎？”

數(shù)據(jù)清洗作為一個過程的第一步是不一致性檢測。不一致性可能由多種原因?qū)е拢涸O(shè)計很差的數(shù)據(jù)表人為的輸入錯誤故意的錯誤（不希望泄露個人信息的回答者），以及數(shù)據(jù)延遲（如過期的地址）還可能因為不一致的數(shù)據(jù)表達(dá)和編碼的不一致使用其他的來源例如測量設(shè)備的錯誤導(dǎo)致的記錄數(shù)據(jù)和系統(tǒng)錯誤錯誤也可能發(fā)生在被用于和預(yù)期不同的目的時還有一些不一致性是因為數(shù)據(jù)聚合導(dǎo)致的（一個給定的屬性在不同數(shù)據(jù)庫中使用不同的名稱）28PPT課件

“那么，如何進(jìn)行不一致檢測呢？”

使用任何你事先已經(jīng)知道的關(guān)于數(shù)據(jù)的相應(yīng)屬性的知識，這種知識被稱為“元數(shù)據(jù)”。

例如，數(shù)據(jù)的類型和每個屬性的域是什么？每個屬性的可接受的值是什么？基本的統(tǒng)計數(shù)據(jù)描述（Section2.2）對于獲取數(shù)據(jù)趨勢和鑒別異常很有用。例如，尋找均值，中值和眾數(shù)。

數(shù)據(jù)是對稱還是偏斜的？值的取值范圍是？所有的值都落在期望的區(qū)間嗎？每個屬性的標(biāo)準(zhǔn)差是多少？值在距離均值兩倍標(biāo)準(zhǔn)差的范圍外的屬性值可能是潛在離群值。屬性之間有已知的依賴關(guān)系嗎？

在這個步驟，你可能需要寫下你自己的腳本或者使用后面將要討論的一些工具。通過這樣的方式，你可以找到噪聲，離群點(diǎn)，需要察覺的異常值。29PPT課件

作為一個數(shù)據(jù)分析師，你需要尋找不一致的編碼以及任何不一致的數(shù)據(jù)表達(dá)（比如，2010/12/25和25/12/2010)。

字段過載是另一個錯誤源，常常是設(shè)計者將新屬性的定義擠進(jìn)一個已經(jīng)定義好的屬性未使用的位（bit)。（例如，一個屬性的值范圍是32位二進(jìn)制中的31位，剩1個位未使用）。

數(shù)據(jù)還需要使用唯一性規(guī)則，連續(xù)性規(guī)則和空值規(guī)則來檢查。唯一值規(guī)則是給定屬性的每一個值必須和該屬性的其他所有值不同。連續(xù)性規(guī)則是在屬性的最小值和最大值之間不能有缺失值（例如，檢查號碼）。空值規(guī)則指明了空白、提問標(biāo)記、特殊字符或其他的字符串可能指代空值條件（如一個給定屬性的值不可獲得），以及這樣的值如何被處理。30PPT課件

空值規(guī)則應(yīng)當(dāng)指明如何記錄空值條件，例如，存儲數(shù)值屬性的0值，字符屬性的空白，或者其他可能使用的習(xí)慣（如，像“不知道”或者“？”的輸入應(yīng)當(dāng)被轉(zhuǎn)換成空白）。

有一系列不同的商業(yè)工具可以用來做不一致性檢測。數(shù)據(jù)洗擦工具使用簡單的領(lǐng)域知識（如郵政地址和拼音檢查的知識）來檢測和修正數(shù)據(jù)中的錯誤。這些工具在清洗多種來源的數(shù)據(jù)時依賴于語法解析和模糊匹配技術(shù)。

數(shù)據(jù)審核工具通過分析數(shù)據(jù)發(fā)現(xiàn)規(guī)則和關(guān)系來尋找不一致性，以及檢查違反了條件的數(shù)據(jù)。

它們是數(shù)據(jù)挖掘工具的變體。它們可能使用統(tǒng)計分析來發(fā)現(xiàn)關(guān)聯(lián)，或者聚類發(fā)現(xiàn)離群點(diǎn)。也可能利用2.2節(jié)介紹的基本統(tǒng)計數(shù)據(jù)描述方法。31PPT課件

一些數(shù)據(jù)不一致性可以通過使用外部參考來人工改正。例如，數(shù)據(jù)輸入的錯誤可以通過紙上跟蹤的方式來改正。

絕大部分的輸錯，都需要進(jìn)行數(shù)據(jù)轉(zhuǎn)換。即一旦我們發(fā)現(xiàn)了不一致性，常常需要定義和應(yīng)用轉(zhuǎn)換來修正。

商業(yè)工具在數(shù)據(jù)轉(zhuǎn)換步驟可以起到作用。數(shù)據(jù)遷移工具允許做簡單的轉(zhuǎn)換例如將字符串“gender”變?yōu)椤眘ex”.

ETL(抽取/轉(zhuǎn)換/加載工具）允許用戶規(guī)定使用圖形用戶接口（GUI)來轉(zhuǎn)換。

這些工具常常只支持有限的轉(zhuǎn)換集，因此，我們還常常選擇編寫定制的腳本來做數(shù)據(jù)清洗的工作。32PPT課件不一致性的兩個步驟即不一致性檢測和數(shù)據(jù)轉(zhuǎn)換是迭代的過程。這個過程是修剪錯誤，很耗時。33PPT課件3.3數(shù)據(jù)聚合數(shù)據(jù)挖掘經(jīng)常需要數(shù)據(jù)聚合——合并多個數(shù)據(jù)庫中的數(shù)據(jù)。細(xì)致的聚合能幫助減少和避免結(jié)果數(shù)據(jù)集中的冗余和不一致性。并在隨后的數(shù)據(jù)挖掘過程中提高準(zhǔn)確率和速度。34PPT課件3.3.1實(shí)體識別問題

數(shù)據(jù)聚合是將多種數(shù)據(jù)來源結(jié)合到一個數(shù)據(jù)庫中，如數(shù)據(jù)倉庫。這些來源包含多種數(shù)據(jù)庫，數(shù)據(jù)立方以及文件。

模式聚合和對象匹配可能比較復(fù)雜。如何將真實(shí)世界中的實(shí)體等價地匹配到多個數(shù)據(jù)源中？這就是實(shí)體識別問題。

35PPT課件

例如，數(shù)據(jù)分析師或者計算機(jī)如何確信一個數(shù)據(jù)庫中的customer_id和另一個庫中的cust_number指的是同一個屬性？包含名稱，含義，數(shù)據(jù)類型，屬性的取值范圍，以及控制規(guī)則的元數(shù)據(jù)在3.2節(jié)被探討過。這種元數(shù)據(jù)能幫助避免模式聚合中的錯誤。

元素?fù)?jù)還可以用來幫助數(shù)據(jù)轉(zhuǎn)換（例如，數(shù)據(jù)編碼pay_type在一個數(shù)據(jù)庫中可能是”H”、“S”,在一個中可能是”1”和“2”).因此，這個步驟和數(shù)據(jù)清洗也互相關(guān)聯(lián)。36PPT課件

將一個數(shù)據(jù)庫中的屬性匹配到另一個數(shù)據(jù)庫時，需要特別注意數(shù)據(jù)的結(jié)構(gòu)。

必須保證源系統(tǒng)中的任何屬性的功能性依賴關(guān)系以及參考限制與目標(biāo)系統(tǒng)匹配。例如，在一個系統(tǒng)中，discount可能被按次序被應(yīng)用，在另一個系統(tǒng)中則按每一個單個的項目內(nèi)部的次序被應(yīng)用。如果在聚合之前沒有發(fā)現(xiàn)這個，目標(biāo)系統(tǒng)中的商品則會有錯誤的discount信息。37PPT課件3.3.2冗余和關(guān)聯(lián)性分析

冗余是數(shù)據(jù)聚合的另外一個重要的問題。一個屬性（例如年收入）是冗余的，如果它能從其他的屬性或?qū)傩约贤茖?dǎo)得到。屬性的不一致或者維度命名也會導(dǎo)致相應(yīng)數(shù)據(jù)集中的冗余。

這種冗余可以使用關(guān)聯(lián)性分析來檢測。給出兩個屬性，這種分析能基于可獲得的數(shù)據(jù)測量一個屬性在多強(qiáng)的程度上暗含了另一個。對于名詞數(shù)據(jù)，可以使用卡方檢驗。對數(shù)值型數(shù)據(jù)，使用關(guān)聯(lián)系數(shù)和協(xié)方差。38PPT課件名詞數(shù)據(jù)的卡方關(guān)聯(lián)檢驗

對名詞數(shù)據(jù)，兩個屬性A和B之間的關(guān)聯(lián)關(guān)系可以使用卡方檢驗來發(fā)現(xiàn)。

假設(shè)A有c個不同的值，a1,a2,….ac.

B有r個不同的值，b1,b2,…br.

則包含屬性A和屬性B的元組可以使用一個列聯(lián)表來表示，其中A屬性的c個不同值構(gòu)成表的列，B屬性的r個不同值構(gòu)成表的行。令(Ai,Bj)表示屬性A取ai而屬性B取bj的聯(lián)合事件，即（A=ai,B=bj).39PPT課件

在表中每一個可能的(Ai,Bj)聯(lián)合事件都有一個單元?？ǚ街档墓绞牵浩渲?，oij表示觀察到的（Ai,Bj)聯(lián)合事件的頻率（實(shí)際次數(shù)）。而eij表示(Ai,Bj)事件的期望頻率，計算公式是：其中，n是數(shù)據(jù)元組的個數(shù)。40PPT課件

公式3.1計算全部r*c個單元的值。那些實(shí)際的次數(shù)和期望值相差最大的是對卡方值貢獻(xiàn)最大的。

卡方統(tǒng)計檢驗假定屬性A和屬性B是互相獨(dú)立的，即這兩個屬性之間沒有關(guān)聯(lián)?；陲@著性水平，自由度是(r-1)*(c-1)。如果假設(shè)被拒絕，則A和B統(tǒng)計相關(guān)。41PPT課件卡方檢驗舉例——例3.1假設(shè)調(diào)查了1500個人，按性別分成男和女。每個人投票是否喜歡閱讀小說。這樣，就有了兩個屬性：gender和preferred_reading.觀察到的每個可能的聯(lián)合事件的次數(shù)在表3.1中。圓括號中的表示事件的期望次數(shù)，按照公式3.2計算出來的。42PPT課件可以注意到，每一行中，期望次數(shù)的總和必須和這一行的觀察次數(shù)的總和相等；每一列中，期望次數(shù)的和等于這一列的觀察次數(shù)的和。利用公式3.1，計算卡方值為：對于2*2的表，自由度為(2-1)*(2-1)=1.在自由度為1時，卡方值為10.828則可以在0.001的顯著性水平上拒絕值原假設(shè)。因為計算出的值大于這個值，所以能以更小的顯著性水平拒絕原假設(shè)，即性別和是否喜歡讀小說之間存在強(qiáng)相關(guān)關(guān)系。43PPT課件數(shù)值型數(shù)據(jù)的相關(guān)系數(shù)

44PPT課件

相關(guān)系數(shù)rAB的值在-1到+1之間。如果rAB>0，則稱A和B正相關(guān)。表示A的值隨著B的值的增大而增大。值越大，相關(guān)性越強(qiáng)。因此，一個很大的值意味著A（或B)需要被作為冗余刪除。

如果rAB=0,則A和B相互獨(dú)立，它們之間沒有任何關(guān)系。如果值<0,則A和B負(fù)相關(guān)，表示一個屬性的值隨著另一個值的降低而增大。散點(diǎn)圖可以用來可視化屬性之間的關(guān)聯(lián)關(guān)系。45PPT課件

注意：關(guān)聯(lián)并不表示因果。即如果A和B相關(guān)，但并不意味著A導(dǎo)致B或者B導(dǎo)致A。

例如，在分析一個人口統(tǒng)計數(shù)據(jù)庫時，我們發(fā)現(xiàn)表示醫(yī)院數(shù)目的屬性和盜車數(shù)目相關(guān)。但這并不表示一個屬性導(dǎo)致了另外一個。兩個屬性實(shí)際上都是因為人口數(shù)這第三個屬性導(dǎo)致的。46PPT課件數(shù)值型數(shù)據(jù)的協(xié)方差

在概率理論和統(tǒng)計學(xué)中，相關(guān)性和協(xié)方差是評價兩個屬性是否一起發(fā)生變化的兩種相似的測量?？紤]兩個數(shù)值型屬性A和B,n個觀察{(a1,b1),…(an,bn)}.屬性A和屬性B的均值，即期望值為：和47PPT課件則屬性A和B的協(xié)方差為：如果利用公式3.3來計算相關(guān)系數(shù)rA,B,則：其中分母是屬性A和B的標(biāo)準(zhǔn)差?？梢钥吹?，48PPT課件

49PPT課件協(xié)方差舉例——例3.2考慮下表，這是一個觀察到的5次AllElectronics和Hightech公式的股票價格。如果股票是被同一個公司的趨勢影響，那么它們的價格是否一起漲落呢？50PPT課件計算均值：則協(xié)方差為：協(xié)方差值為正，因此，我們可以說兩個公司的股票是一起漲的。51PPT課件方差是協(xié)方差的特例，是兩個屬性相等，即屬性自身的協(xié)方差。52PPT課件3.3.3元組復(fù)制

除了檢測屬性間的冗余，元組級別的冗余也需要被檢測。不規(guī)范表的使用（一般是為了避免連接提高性能）是另一種數(shù)據(jù)冗余的來源。在不同的復(fù)制之間常常產(chǎn)生不一致性。因為不精確的數(shù)據(jù)輸入或者更新了一部分而非全部的數(shù)據(jù)。

例如，一個購買訂單數(shù)據(jù)庫包含購買者的姓名和地址屬性，而非這個信息的主鍵信息。不一致性就可能產(chǎn)生，比如在購買訂單數(shù)據(jù)庫中同樣的購買者姓名卻是不同的地址。53PPT課件3.3.4數(shù)據(jù)值和檢測與解析的沖突

數(shù)據(jù)聚合還包含數(shù)據(jù)值沖突的檢測和解析。例如，對于同一個真實(shí)世界實(shí)體，不同來源的屬性值可能不同?？赡苁且驗楸磉_(dá)、刻度或者編碼的不同。

比如，體重屬性在一個系統(tǒng)中可能以公制單位存放而在另一個中以英帝單位存放。

學(xué)校之間交換信息的時候，每個學(xué)校有自己的課程設(shè)置和等級模式。一個大學(xué)可能采用一個季度系統(tǒng)，一個數(shù)據(jù)庫系統(tǒng)中3門課程，等級從A+到F。另一個可能采用學(xué)期值，數(shù)據(jù)庫中提供2門課程，等級從1到10.很難制定兩所大學(xué)精確的課程——等級轉(zhuǎn)換規(guī)則，交換信息很困難。54PPT課件

屬性的抽象級別也可能不同。在一個抽象級別更低的系統(tǒng)中，同一個屬性的級別比另一個系統(tǒng)中同樣的值更低。

比如，total_sales在一個數(shù)據(jù)庫中指AllElectronics的一個部門的總體銷售，而同樣名稱的屬性在另一個數(shù)據(jù)庫中指的是一個給定地區(qū)的總體銷售。55PPT課件3.4數(shù)據(jù)刪減3.4.1數(shù)據(jù)刪減策略概覽數(shù)據(jù)刪減策略包含減少維度，減少數(shù)據(jù)塊以及數(shù)據(jù)壓縮。維度刪減是減少考慮的隨機(jī)變量或?qū)傩缘膫€數(shù)。維度刪減方法包括小波轉(zhuǎn)換，主成分分析，即將原有數(shù)據(jù)轉(zhuǎn)換或者投影到一個更小的空間。屬性子集選擇是檢測和刪除不相關(guān)的、弱相關(guān)的、冗余的屬性和維度的減少維度的方法。56PPT課件刪減數(shù)據(jù)塊是將原有數(shù)據(jù)以可選的、更小的表格替換。分參數(shù)和非參數(shù)兩種技術(shù)。參數(shù)的方法是，使用一個模型來評估數(shù)據(jù)，常常只有數(shù)據(jù)參數(shù)被存儲，而非實(shí)際的數(shù)據(jù)?；貧w和對數(shù)——線性模型是兩個參數(shù)技術(shù)的例子。非參數(shù)技術(shù)存放以直方圖、聚類、抽樣以及數(shù)據(jù)立方的形式表示的刪減數(shù)據(jù)。57PPT課件數(shù)據(jù)壓縮中，應(yīng)用轉(zhuǎn)換來得到一個原有數(shù)據(jù)的刪減或壓縮的表達(dá)。如果原有數(shù)據(jù)能從壓縮數(shù)據(jù)中被重構(gòu)而沒有任何信息損失，則數(shù)據(jù)刪減是無損的。如果只能重構(gòu)原有數(shù)據(jù)的近似集，則數(shù)據(jù)刪減是有損的。有一些字符串壓縮的無丟失的算法，這些通常只允許有限制的數(shù)據(jù)處理。減少維度和減少數(shù)據(jù)塊也能被看成是數(shù)據(jù)壓縮的形式。還有許多其他數(shù)據(jù)刪減的方法?；ㄔ跀?shù)據(jù)刪減上的時間復(fù)雜度不應(yīng)當(dāng)超過或等于挖掘一個刪減的數(shù)據(jù)集節(jié)省的時間。58PPT課件3.4.2小波轉(zhuǎn)換

離散小波轉(zhuǎn)換（DWT)是一個線性信號處理技術(shù)。對一個數(shù)據(jù)向量X,使用小波系數(shù)，轉(zhuǎn)換成一個不同的數(shù)值向量X’。

這兩個向量的長度相同。當(dāng)應(yīng)用這種數(shù)據(jù)刪減的技術(shù)時，將每個元組看成一個n維的數(shù)據(jù)向量，X=(x1,x2,…,xn)，表示數(shù)據(jù)庫的n個屬性的n個測量。

“如果小波轉(zhuǎn)換的數(shù)據(jù)和原有數(shù)據(jù)的長度相同，這種數(shù)據(jù)刪減技術(shù)如何有效呢？”59PPT課件

有效性在于小波轉(zhuǎn)換的數(shù)據(jù)能夠被截短。數(shù)據(jù)的被壓縮的近似集被保留，只存放了小波系數(shù)最強(qiáng)的一小部分?jǐn)?shù)據(jù)。

例如，所有比一些用戶指定閥值更大的小波系數(shù)被保留。其他的系數(shù)被設(shè)置為0.得到的數(shù)據(jù)表達(dá)因此非常稀疏，操作就可以利用數(shù)據(jù)的稀疏性，在小波空間計算將非常快。

這個技術(shù)還能被用于去除噪聲，而不需要消除數(shù)據(jù)的主要特征，像數(shù)據(jù)清洗一樣有效。

給定一系列系數(shù)，原有數(shù)據(jù)的近似能應(yīng)用逆DWT被重構(gòu)。60PPT課件 DWT和離散傅里葉轉(zhuǎn)換（DFT)關(guān)聯(lián)性很強(qiáng)。DFT是一種包含正弦余弦的信號處理技術(shù)。一般情況下，DWT能得到更好的無損壓縮。即如果在給定數(shù)據(jù)向量上應(yīng)用DWT和DFT，DWT能得到原有數(shù)據(jù)更好的近似集。因此，得到一個相同的近似集，DWT需要更少的空間。

只有一種DFT，但DWT有不同的系列。流行的小波轉(zhuǎn)換包含Harr-2,Daubechies-4,以及Daubechies-6.應(yīng)用一個離散小波轉(zhuǎn)換的一般步驟是使用一個層次化的金字塔算法，每次迭代將數(shù)據(jù)減半，這是非?？斓挠嬎闼俣取?1PPT課件DWT的步驟：1、輸入數(shù)據(jù)向量的長度L必須是2的整數(shù)次冪。這個條件可以在必要時以0填充數(shù)據(jù)向量來滿足。2、每個轉(zhuǎn)換包含應(yīng)用兩個函數(shù)。第一個應(yīng)用一些數(shù)據(jù)平滑，例如求和或者加權(quán)平均。第二個使用一個加權(quán)差，為了表達(dá)數(shù)據(jù)的具體特征。3、這兩個函數(shù)被應(yīng)用到向量X的每一個對（x2i,x2i+1).這會得到兩個長度為L/2的數(shù)據(jù)集。一般情況下，它們一個表達(dá)的是平滑的或者低頻的輸入數(shù)據(jù)的版本，另一個是高頻的內(nèi)容。4、這兩個函數(shù)被遞歸的應(yīng)用到前一個循環(huán)得到的數(shù)據(jù)集上，直到數(shù)據(jù)集的長度變成2.5、從前一次迭代的數(shù)據(jù)集中選擇值，將其指明為轉(zhuǎn)換數(shù)據(jù)的小波系數(shù)。62PPT課件63PPT課件

一個矩陣被應(yīng)用在輸入數(shù)據(jù)上，以便于得到小波系數(shù)。矩陣依賴于給定的DWT。矩陣必須是正交的，即列是單位向量，相互正交的，因此矩陣的逆是它的轉(zhuǎn)置。

通過將矩陣分解為幾個稀疏矩陣，得到的快速DWT算法具有O(n)的時間復(fù)雜度。

小波轉(zhuǎn)換能被應(yīng)用于高維數(shù)據(jù)如數(shù)據(jù)立方上。方法是首先應(yīng)用轉(zhuǎn)換到第一個維度上，然后第二個，以此類推。計算復(fù)雜度視立方的單元數(shù)目而定。

小波轉(zhuǎn)換對于稀疏或偏斜的數(shù)據(jù)有很好的效果，以及次序?qū)傩缘臄?shù)據(jù)上。小波變換的有損壓縮據(jù)說比JPEG好。它有很多實(shí)際的應(yīng)用，包括指紋圖像、計算機(jī)視覺的壓縮，時間序列數(shù)據(jù)分析以及數(shù)據(jù)清洗。64PPT課件3.4.3主成分分析

假定要刪減的數(shù)據(jù)包含n個屬性或維度。主成分分析（PCA)尋找K個n維正交向量，這些向量能最好的表達(dá)數(shù)據(jù)，k<n.原有的數(shù)據(jù)因此被投影到一個更小的空間，得到刪減的維度。

不同于屬性子集選擇，PCA通過創(chuàng)建一個可選的更好的變量集，得到重要屬性的聯(lián)合。PCA常常揭示之前沒有察覺的關(guān)系，因此得到通常沒有的解釋。aproductofafewsparsematrices65PPT課件PCA的基本步驟：1、將輸入數(shù)據(jù)標(biāo)準(zhǔn)化，每個屬性落在相同的值區(qū)間。確保屬性在更大范圍的不會占有更大權(quán)重。2、計算K個正交向量，提供標(biāo)準(zhǔn)輸入數(shù)據(jù)的基礎(chǔ)。這是一些單位向量。每個點(diǎn)在方向上與其他的垂直。這些向量被稱為主要成分。輸入數(shù)據(jù)是主成分的線性組合。3、主成分按重要性或者長度遞減的次序存放。主成分作為數(shù)據(jù)的新的坐標(biāo)軸的集合，提供重要的方差信息。即，排序的坐標(biāo)軸中，第一個軸表示數(shù)據(jù)的最大方差，第二個表示次高的方差，以此類推。例如圖3.5表示了兩個主成分Y1和Y2。66PPT課件67PPT課件4、因為主成分按重要性的降序排列，數(shù)據(jù)尺寸可以通過去除次要成分來減少，即具有更小方差信息的。使用最強(qiáng)的主成分，得到原有數(shù)據(jù)的很好的近似集的重構(gòu)是可能的。PCA能被應(yīng)用于次序或者非次序?qū)傩?。能處理稀疏和偏斜的?shù)據(jù)。高維數(shù)據(jù)能被減少為2個。相比于小波轉(zhuǎn)換，PCA能更好的處理稀疏數(shù)據(jù)，而小波轉(zhuǎn)換更適合處理高維數(shù)據(jù)。68PPT課件3.4.4屬性子集選擇

用來做分析的數(shù)據(jù)集可能包含成百個屬性，許多屬性和挖掘任務(wù)并不相關(guān)或者是冗余的。

例如，挖掘任務(wù)是對顧客進(jìn)行分類，判斷他們是否會購買一個流行的新CD，像顧客的電話號碼很可能是不相關(guān)的，不像年齡和音樂類型這類屬性是相關(guān)的。領(lǐng)域?qū)＜姨暨x一些有用的屬性是可能的，但這是一個困難和耗時的工作，特別是在數(shù)據(jù)的行為并不已知的時候。去掉了相關(guān)的屬性，或者保留了不相關(guān)的屬性都是有害的。導(dǎo)致挖掘算法的困惑以及低質(zhì)量的模式發(fā)現(xiàn)。并且，增加的不相關(guān)和冗余屬性也會讓挖掘過程變慢。69PPT課件

屬性子集選擇通過減少不相關(guān)和冗余的屬性來減少數(shù)據(jù)集的大小。屬性子集選擇的目標(biāo)是尋找一個相應(yīng)的數(shù)據(jù)類別分布概率盡可能接近使用所有屬性的原始分布的最小屬性集合。在刪減的屬性集上挖掘具有特別的好處：使挖掘出的模式更容易被理解。

“如何尋找一個原有屬性的好的子集合呢？”

對于n個屬性，有2n個子集合，對優(yōu)化子集的窮舉搜索是代價很大的，特別是在n和數(shù)據(jù)類別增加的時候。因此，剪枝式的啟發(fā)式方法通常被用于屬性子集選擇。這些方法通常是貪心式的，策略是做一個局部最優(yōu)的選擇用以得到一個全局優(yōu)化的解。70PPT課件

“最好的”（以及“最差的”）屬性常常是使用統(tǒng)計顯著性檢驗來決定，假定屬性之間是互相獨(dú)立的。許多其他的屬性評估方法如決策樹分類中的信息增益。

基本的屬性子集選擇的啟發(fā)式技術(shù)如下：

1、逐步向前選擇。該方法從一個屬性的空集合開始作為刪減集合。然后確定一個原有屬性的最好屬性，加入到刪減集合中。每一次迭代，都把剩余屬性集中最好的屬性加入到該集合。

2、逐步向后刪除。該方法從全體屬性集開始，每一次從中去除剩余屬性集合中最差的屬性。

3、結(jié)合向前選擇和向后刪除的方法。71PPT課件屬性子集選擇的貪心式方法72PPT課件4、決策樹推導(dǎo)。決策樹算法（如ID3，C4.5，和CART)最初被用于分類。決策樹推導(dǎo)是創(chuàng)建一個流程圖結(jié)構(gòu)，每一個內(nèi)部節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）表示一個屬性的檢驗，每一個分支對應(yīng)于一個檢驗的結(jié)果，每一個外部節(jié)點(diǎn)（葉子節(jié)點(diǎn)）表示一個類別預(yù)測。在一個節(jié)點(diǎn)，算法選擇最好的屬性去將數(shù)據(jù)分割成單個的類別。當(dāng)決策樹用于屬性子集選擇時，給定數(shù)據(jù)的樹被創(chuàng)建。所有沒有出現(xiàn)在樹中的屬性被認(rèn)為是不相關(guān)的。出現(xiàn)在樹中的屬性構(gòu)成了刪減屬性子集。在某些情形下，可能需要基于一些屬性創(chuàng)建一些新的屬性。這類屬性構(gòu)造能幫助提高對高維數(shù)據(jù)的精確性和結(jié)構(gòu)的理解。比如，基于屬性height和width創(chuàng)建area屬性。通過結(jié)合屬性，屬性構(gòu)造能發(fā)現(xiàn)數(shù)據(jù)屬性之間的缺失信息，有利于知識發(fā)現(xiàn)。73PPT課件3.4.5回歸和對數(shù)——線性模型：參數(shù)數(shù)據(jù)刪減

線性回歸中，數(shù)據(jù)被擬合成一條直線。

例如，隨機(jī)變量y(也稱為響應(yīng)變量），被建模成另一個隨機(jī)變量x(稱為預(yù)測變量）的線性函數(shù)，公式為：y=wx+b

在數(shù)據(jù)挖掘環(huán)境中，x和y都是數(shù)值型的屬性，系數(shù)w和b稱為回歸系數(shù)，定義了直線的斜率和y-截距。系數(shù)的求解可以使用最小二乘法，最小化實(shí)際直線分割數(shù)據(jù)和估計值之間的錯誤。

多元線性回歸是線性回歸的擴(kuò)展，將相應(yīng)變量y建模成2個或更多的預(yù)測變量的線性函數(shù)。74PPT課件

對數(shù)——線性模型近似于離散高維概率分布。

給定一系列包含n維屬性的元組，將每一個元組當(dāng)成n維空間中的一個點(diǎn)。

對數(shù)——線性模型基于一個更小的維度聯(lián)合的子集，來估計每個點(diǎn)在高維空間的概率。這樣就能從低維空間構(gòu)建高維數(shù)據(jù)空間。因此，模型可以用于維度刪減（因為低維點(diǎn)常常比原有數(shù)據(jù)點(diǎn)占有更少的空間）以及數(shù)據(jù)平滑（因為低維空間的聚合估計比高維空間的估計對抽樣變化主觀度更?。?5PPT課件

回歸和對數(shù)——線性模型都能用在稀疏數(shù)據(jù)上，即使應(yīng)用比較有限。兩種方法都能處理偏斜數(shù)據(jù)，回歸做的更好。對高維數(shù)據(jù)，回歸的計算復(fù)雜度很高，而對數(shù)——線性模型對高于10維的數(shù)據(jù)有更好的可擴(kuò)展性。

一些軟件包中有回歸問題的解決方法。如SAS,SPSS,S-Plus.76PPT課件3.4.6直方圖

直方圖使用箱子來近似數(shù)據(jù)分布，是一種流行的數(shù)據(jù)刪減的形式。

直方圖是將一個屬性A劃分成不相交的子集，稱為桶或者箱子。

如果每個桶只表示一個單個的屬性值/頻率對，則桶稱為單例桶。如圖3.7.通常，桶表示給定屬性的連續(xù)范圍?！叭绾未_定桶和屬性值的劃分呢？”有如下劃分的技術(shù)：等寬度：每個桶的范圍都是相同的。如圖3.8.等頻率：每個桶的頻數(shù)相同（即裝了個數(shù)幾乎相同的數(shù)據(jù)樣本）77PPT課件單例桶舉例78PPT課件等寬度裝箱79PPT課件

直方圖對于稀疏和稠密數(shù)據(jù)都很高效，對高度偏斜或者均勻分布的數(shù)據(jù)也是一樣。

單個屬性的直方圖可以被擴(kuò)展到多個屬性。多維直方圖能捕獲屬性間的依賴關(guān)系，最多能對5維數(shù)據(jù)有效。進(jìn)一步的研究高維數(shù)據(jù)的有效直方圖是有必要的。80PPT課件3.4.7聚類

聚類技術(shù)將數(shù)據(jù)元組當(dāng)成對象。將對象劃分成分組，或簇，在同一個簇中對象是相似的，跟其他簇中的對象是不相似的。相似性一般是基于距離函數(shù)，以對象在空間上的距離有多接近來定義。

聚類的質(zhì)量可以用它的直徑來表示，即簇中兩個對象的最大距離。幾何中心距離是聚類質(zhì)量的一個可選的測量，定義為每個聚類對象到聚類中心的平均距離。

圖3.3展示了一個顧客數(shù)據(jù)的2-D散點(diǎn)圖，點(diǎn)的位置是在一個城市中的顧客位置?？梢钥匆?個數(shù)據(jù)簇。81PPT課件82PPT課件3.4.8抽樣

抽樣也可以作為一種數(shù)據(jù)刪減的技術(shù)，因為它允許從一個大數(shù)據(jù)集中抽取小得多的隨機(jī)數(shù)據(jù)（子集）來表示。假定一個大數(shù)據(jù)集D包含N個元組，最常用的數(shù)據(jù)刪減的抽樣技術(shù)包括：1、無置換的簡單隨機(jī)抽樣（SRSWOR)。方法是從N個元組中以概率1/N從D中抽樣s個數(shù)據(jù)，每個元組被抽樣的概率都相等。2、有置換的簡單隨機(jī)抽樣（SRSWR)。類似于SPSWOR,除了每次從D中抽樣一個元組之后，記錄它然后替換。即元組被抽樣之后，再放回D中下次還可以被繼續(xù)抽到。83PPT課件3、聚類樣本。如果D中的元組被分成M個互不相交的簇，然后就可以抽樣得到s個簡單隨機(jī)抽樣簇，s<M.例如，元組在一個數(shù)據(jù)庫中通常被一次檢索一頁，每一頁可以被看做一個簇。然后使用SRSWOR到頁面上，便可以得到刪減數(shù)據(jù)的代表，即元組的聚類抽樣。其他的一些包含豐富語義信息的聚類規(guī)則也可以使用。例如，在空間數(shù)據(jù)庫中，基于不同地區(qū)在地理位置上的接近程度來圖形化地定義簇。84PPT課件4、分層抽樣：如果D被分成互不相交的層，分層抽樣可以通過對每個層進(jìn)行簡單隨機(jī)抽樣來生成。這能在數(shù)據(jù)偏斜的時候，選出具有代表性的樣本。例如，從顧客數(shù)據(jù)中進(jìn)行分層抽樣。將每個顧客按年齡分組，然后對分組抽樣。在這種方式下，有最小個數(shù)的顧客年齡層也被保證會被抽取。85PPT課件

使用抽樣的方法進(jìn)行數(shù)據(jù)刪減的優(yōu)點(diǎn)在于，得到一個樣本的代價和樣本的大小成比例，即s與N的比例。因此，抽樣復(fù)雜度是亞線性比于數(shù)據(jù)尺寸。其他的數(shù)據(jù)刪減技術(shù)的復(fù)雜度至少是O(N)。

給定一個固定的樣本大小，抽樣復(fù)雜度隨著數(shù)據(jù)維度的個數(shù)增加而增加。如果用直方圖技術(shù)，復(fù)雜度則是n的指數(shù)級別。

抽樣是最常用的用來估計一個集合查詢的答案的方法。86PPT課件3.4.9數(shù)據(jù)立方聚合

假設(shè)你在為你的分析收集數(shù)據(jù)。這些數(shù)據(jù)包括AllElectronics公司每個季度的銷售，從2008年至2010年。你感興趣的是每年的銷售額，而不是每個季度的總體銷售額。因此，數(shù)據(jù)需要被聚合，得到每年的銷售總額而非季度銷售額。

圖3.10是聚合的情況。得到的數(shù)據(jù)集尺寸更小，對分析任務(wù)來說沒有必要的信息損失。87PPT課件舉例88PPT課件

數(shù)據(jù)立方存儲的是高維聚合信息。如圖3.11是一個銷售數(shù)據(jù)的高維分析的數(shù)據(jù)立方，包含AllElectronics公司所有分部的每年的每種商品類型的銷售額。每個單元是一個聚合的數(shù)據(jù)值，對應(yīng)于高維空間中的數(shù)據(jù)點(diǎn)。每個屬性有一個概念層級，允許對數(shù)據(jù)的多層抽象級別的分析。比如，對于子公司的層級允許將子公司基于位置分組為不同的地區(qū)。

數(shù)據(jù)立方提供對預(yù)先計算，數(shù)據(jù)摘要的快速訪問，因此有利用在線分析處理以及數(shù)據(jù)挖掘。89PPT課件3.5數(shù)據(jù)轉(zhuǎn)換和離散化3.5.1數(shù)據(jù)轉(zhuǎn)換策略概覽數(shù)據(jù)轉(zhuǎn)換把數(shù)據(jù)轉(zhuǎn)換或合并成適合數(shù)據(jù)挖掘的形式。數(shù)據(jù)轉(zhuǎn)換的策略包括：1、平滑。用于去除數(shù)據(jù)中的噪聲。技術(shù)包括裝箱，回歸和聚類。2、屬性構(gòu)造（或特征構(gòu)造）。從給定屬性中構(gòu)造或增加新屬性以便于挖掘過程。3、聚合。在數(shù)據(jù)上應(yīng)用聚合或者概括操作。例如，聚合每日銷售數(shù)據(jù)以計算每月和每年的總體數(shù)據(jù)。通常這個步驟用在構(gòu)造用于多層抽象級別數(shù)據(jù)分析的數(shù)據(jù)立方。90PPT課件4、規(guī)范化。屬性被按比例縮放到一個更小的范圍，如-1.0到1.0，或0.0到1.0之間。5、離散化。數(shù)值屬性的原始值被區(qū)間標(biāo)簽或概念標(biāo)簽置換。標(biāo)簽?zāi)鼙贿f歸的組織成高層概念。形成一個數(shù)值屬性的概念層級。圖3.12是一個價格屬性的概念層級的例子。超過一個的概念層級可以被用來滿足不同用戶的需求。6、名詞數(shù)據(jù)的概念層級生成。例如steet屬性可以擴(kuò)展成高層概念，如city和country.許多名詞屬性的層次是隱藏在數(shù)據(jù)庫模式中的，可以在模式定義級別自動定義。91PPT課件離散化

離散化技術(shù)可以基于離散化方法的不同來分類，例如是使用類別信息還是處理方向（自底向上和自頂向下）。

如果離散化過程使用類別信息，稱為有監(jiān)督的離散化；否則是無監(jiān)督的。

如果過程先尋找一個活若干點(diǎn)來分割整個屬性范圍，然后對每個區(qū)間遞歸重復(fù)這個步驟，則稱為自頂向下的離散化或分割。自底向上的離散化或合并先把所有的連續(xù)值作為潛在的分割點(diǎn)，通過合并相鄰的值移除某些點(diǎn)來形成區(qū)間，然后再遞歸的應(yīng)用這個過程到每一個區(qū)間。92PPT課件

數(shù)據(jù)離散化和概念層級生成也是數(shù)據(jù)刪減的形式。原始數(shù)據(jù)被一個數(shù)目更小的區(qū)間或者概念標(biāo)簽置換。這簡化了原有數(shù)據(jù)，使挖掘更高效。挖掘出的模式通常更易于被理解。概念層級在對多層抽象級別挖掘上也十分有效。93PPT課件3.5.2數(shù)據(jù)標(biāo)準(zhǔn)化

使用的度量單位會影響數(shù)據(jù)分析。例如，將身高的度量單位從米變成英寸，或體重從公斤變?yōu)榘?，會?dǎo)致非常不同的結(jié)果。

通常，用更小的單位表達(dá)的屬性會有一個更大的屬性取值范圍，傾向于給這類屬性更大的效應(yīng)或“權(quán)重”。為了避免對度量單位的依賴，數(shù)據(jù)需要被標(biāo)準(zhǔn)化。

這會將數(shù)據(jù)按比例縮放在一個更小或更常見的區(qū)間，如[-1,1]或[0,1]。94PPT課件

標(biāo)準(zhǔn)化數(shù)據(jù)會給所有屬性相同權(quán)重。在分類算法包括神經(jīng)網(wǎng)絡(luò)或最近令分類以及聚類中，標(biāo)準(zhǔn)化特別有效。如果在神經(jīng)網(wǎng)絡(luò)反向傳播算法中，對每個訓(xùn)練元組的每個屬性的輸入值進(jìn)行標(biāo)準(zhǔn)化，則會加速學(xué)習(xí)的速度。對于基于距離的方法，標(biāo)準(zhǔn)化可以避免屬性在初始時具有大的范圍？在沒有給定數(shù)據(jù)的先驗知識時也很有用。有許多數(shù)據(jù)標(biāo)準(zhǔn)化的方法，如：最小——最大值標(biāo)準(zhǔn)化Z-分?jǐn)?shù)標(biāo)準(zhǔn)化十進(jìn)制換算標(biāo)準(zhǔn)化95PPT課件令A(yù)是一個數(shù)值屬性，有n個觀察到的值v1,v2,…,vn.最小——最大值標(biāo)準(zhǔn)化：令minA和maxA表示屬性A的最小值和最大值，最小——最大值標(biāo)準(zhǔn)化將值vi映射為vi’(范圍是[new_minA,new_maxA]:最小——最大值標(biāo)準(zhǔn)化保留了原有數(shù)據(jù)值的關(guān)系。如果后來的輸入的標(biāo)準(zhǔn)化的數(shù)據(jù)落在了原有數(shù)據(jù)區(qū)間的外面，將會發(fā)生過界的錯誤。96PPT課件Min_max

normarlization舉例假定收入屬性的最小值和最大值分別是$12,000和$98,000.將收入屬性映射到范圍[0.0,1.0]上。則一個值為$73,600的收入標(biāo)準(zhǔn)化為：97PPT課件Z-分?jǐn)?shù)標(biāo)準(zhǔn)化

98PPT課件Z-scorenormarlization舉例假定income屬性的均值和標(biāo)準(zhǔn)差是$54,000和$16,000。使用z-分?jǐn)?shù)標(biāo)準(zhǔn)化，則$73,600被轉(zhuǎn)換為：99PPT課件Z-分?jǐn)?shù)標(biāo)準(zhǔn)化的變體是使用屬性A的平均絕對偏差來替換標(biāo)準(zhǔn)差。平均絕對偏差sA的計算公式為：用sA替換σA即可。平均絕對偏差比標(biāo)準(zhǔn)差對離群點(diǎn)更健壯，因為沒有平方。即離群點(diǎn)的效應(yīng)被減弱。100PPT課件十進(jìn)制換算標(biāo)準(zhǔn)化

十進(jìn)制換算標(biāo)準(zhǔn)化通過移動屬性A的值的十進(jìn)制小數(shù)點(diǎn)來標(biāo)準(zhǔn)化。移動的數(shù)目依賴于屬性A的絕對值的最大值。轉(zhuǎn)換公式為：其中，j是使max(|vi’|)<1的最小整數(shù)。101PPT課件Decimalscalingnormarlization舉例

假設(shè)屬性A的記錄值的范圍是-986到917.則A的絕對值的最大值為986.通過十進(jìn)制換算標(biāo)準(zhǔn)化，將每個值除以1000（因為j=3)，所以-986標(biāo)準(zhǔn)化為：-0.986.917標(biāo)準(zhǔn)化為0.917.102PPT課件

注意標(biāo)準(zhǔn)化會小部分的改變原有數(shù)據(jù)，特別是在用z-分?jǐn)?shù)標(biāo)準(zhǔn)化和十進(jìn)制換算標(biāo)準(zhǔn)化時。

將標(biāo)準(zhǔn)化參數(shù)存儲起來是有必要的，因為將來的數(shù)據(jù)可以使用同一方式進(jìn)行標(biāo)準(zhǔn)化。103PPT課件3.5.3裝箱離散化技術(shù)

裝箱技術(shù)在3.2.2節(jié)已被討論過。

裝箱技術(shù)沒有使用分類信息，因此是無監(jiān)督的離散化技術(shù)。它對人為指定的箱子個數(shù)以及離群點(diǎn)比較敏感。104PPT課件3.5.4直方圖分析的離散化技術(shù)

直方圖也是一種無監(jiān)督的離散化技術(shù)。在2.2.3節(jié)已被討論過。

最小的區(qū)間尺寸可以被用來控制遞歸分割的步驟。這可以指明分割的最小寬度，或者每個分割的最小值數(shù)目。直方圖還可以基于數(shù)據(jù)分布的聚類分析來分割。105PPT課件3.5.5聚類、決策樹以及關(guān)聯(lián)分析離散化技術(shù)

聚類分析是一種流行的數(shù)據(jù)離散化方法。一個聚類算法可以應(yīng)用到數(shù)值屬性上，將屬性A的值分割成簇或分組。聚類考慮屬性A的分布，和數(shù)據(jù)點(diǎn)的緊密度，因此會產(chǎn)生高質(zhì)量的離散化結(jié)果。

聚類可以被用來生成屬性A的概念層次，使用自頂向下的分割策略或者自底向上的合并策略。106PPT課件

決策樹分類技術(shù)也可以用來做數(shù)據(jù)的離散化。這種技術(shù)采用自頂向下的分割方法。不同于其他的前面提到的方法，這是一種有監(jiān)督的離散化方法，即使用分類標(biāo)簽的信息。

例如，我們有一個數(shù)據(jù)集，包括病人的癥狀（屬性）以及病人的相應(yīng)診斷類別標(biāo)簽。在計算和確定分割點(diǎn)時使用到分類分布信息。直觀地，主要思想是選擇分割點(diǎn)，使一個給定的分割包含同類別的盡可能多的元組。熵是在這種情況適用的最普遍的測量。離散化數(shù)值屬性A時，選擇有最小熵的屬性A作為分割點(diǎn)，然后遞歸的分割結(jié)果區(qū)間，以得到一個層次的離散化結(jié)果。最終形成一個屬性A的概念層次。

因為決策樹離散化適用分類信息，區(qū)間界限定義的地方更可能提高分類的精確性。107PPT課件

關(guān)聯(lián)分析也可以用于數(shù)據(jù)離散化。ChiMerge是一種基于卡方分布的離散化方法。之前的離散化方法中，都是采用一種自頂向下的分割策略。這種ChiMerge的方法是采用自底向上的方法，通過尋找最優(yōu)的鄰