學(xué)習(xí)筆記5：數(shù)據(jù)預(yù)處理與數(shù)據(jù)挖掘十大經(jīng)典算法

1、學(xué)習(xí)筆記5：數(shù)據(jù)預(yù)處理與數(shù)據(jù)挖掘十大經(jīng)典算法前言在介紹了數(shù)據(jù)挖掘的一般流程、常用方法、應(yīng)用功能和數(shù)據(jù)可視化之后，在本篇博文中，筆者想要分享一些在數(shù)據(jù)挖掘開始之前要做的一些事數(shù)據(jù)預(yù)處理。在第二部分中，筆者整理了數(shù)據(jù)挖掘中的十大經(jīng)典算法，與讀者們共享。兩部分分別從數(shù)據(jù)挖掘中數(shù)據(jù)預(yù)處理的方法與技術(shù)一文與網(wǎng)絡(luò)中引用而來，作為自己和讀者朋友們的學(xué)習(xí)筆記。在第三部分階段小結(jié)中，筆者對近期的學(xué)習(xí)進(jìn)行了階段性的總結(jié)。一、數(shù)據(jù)預(yù)處理現(xiàn)實中數(shù)據(jù)大多數(shù)都是不完整、不一致的，無法直接進(jìn)行數(shù)據(jù)挖掘，或直接影響了挖掘結(jié)果。為了提高數(shù)據(jù)挖掘質(zhì)量和數(shù)據(jù)挖掘效率，產(chǎn)生了數(shù)據(jù)預(yù)處理技術(shù)。對數(shù)據(jù)進(jìn)行預(yù)處理，不但可以節(jié)約大量的空間和

2、時間而且得到的挖掘結(jié)果能更好地起到?jīng)Q策和預(yù)測作用。數(shù)據(jù)預(yù)處理一般包括：數(shù)據(jù)清理，數(shù)據(jù)集成，數(shù)據(jù)變換，數(shù)據(jù)歸約等方法。這些數(shù)據(jù)預(yù)處理技術(shù)根據(jù)數(shù)據(jù)挖掘項目的需要和原始數(shù)據(jù)的特點，在數(shù)據(jù)挖掘之前有選擇的單獨使用或綜合使用，可大大提高數(shù)據(jù)挖掘模式的質(zhì)量，降低實際挖掘所需要的時間。數(shù)據(jù)預(yù)處理技術(shù)整理如下：1、數(shù)據(jù)清理數(shù)據(jù)清理是數(shù)據(jù)預(yù)處理中最花費時間、最乏味的，但也是最重要的一步。該步驟可以有效地減少學(xué)習(xí)過程中可能出現(xiàn)相互矛盾的情況。數(shù)據(jù)清理主要處理缺失數(shù)據(jù)，噪聲數(shù)據(jù)，識別、刪除孤立點。數(shù)據(jù)清理的基本方法有：（1）缺失數(shù)據(jù)處理：目前最常用的方法是使用最可能的值填充缺失值，比如可以用回歸、貝葉斯形式化方法工

3、具或判定樹歸納等確定缺失值。這類方法依靠現(xiàn)有的數(shù)據(jù)信息來推測缺失值，使缺失值有更大的機(jī)會保持與其他屬性之間的聯(lián)系。還有其他一些方法來處理缺失值，如用一個全局常量替換缺失值、使用屬性的平均值填充缺失值或?qū)⑺性M按某些屬性分類，然后用同一類中屬性的平均值填充缺失值。如果缺失值很多，這些方法可能誤導(dǎo)挖掘結(jié)果。如果缺失值很少，可以忽略缺失數(shù)據(jù)。（2）噪聲數(shù)據(jù)處理：噪聲是一個測量變量中的隨機(jī)錯誤或偏差，包括錯誤的值或偏離期望的孤立點值。目前最廣泛的是應(yīng)用數(shù)據(jù)平滑技術(shù)處理，具體包括：分箱技術(shù)，將存儲的值分布到一些箱中，用箱中的數(shù)據(jù)值來局部平滑存儲數(shù)據(jù)的值。具體可以采用按箱平均值平滑、按箱中值平滑和按箱邊

4、界平滑；回歸方法，可以找到恰當(dāng)?shù)幕貧w函數(shù)來平滑數(shù)據(jù)。線性回歸要找出適合兩個變量的“最佳”直線，使得一個變量能預(yù)測另一個。多線性回歸涉及多個變量，數(shù)據(jù)要適合一個多維面；計算機(jī)檢查和人工檢查結(jié)合方法，可以通過計算機(jī)將被判定數(shù)據(jù)與已知的正常值比較，將差異程度大于某個閾值的模式輸出到一個表中，然后人工審核表中的模式，識別出孤立點；聚類技術(shù)，將類似的值組織成群或“聚類”，落在聚類集合之外的值被視為孤立點。孤立點可能是垃圾數(shù)據(jù)，也可能為我們提供重要信息。對于確認(rèn)的孤立點垃圾數(shù)據(jù)將從數(shù)據(jù)庫中予以清除。2、數(shù)據(jù)集成數(shù)據(jù)集成就是將多個數(shù)據(jù)源中的數(shù)據(jù)合并存放在一個同一的數(shù)據(jù)存儲（如數(shù)據(jù)倉庫、數(shù)據(jù)庫等）的一種技術(shù)和

5、過程，數(shù)據(jù)源可以是多個數(shù)據(jù)庫、數(shù)據(jù)立方體或一般的數(shù)據(jù)文件。數(shù)據(jù)集成涉及3個問題：模式集成。涉及實體識別，即如何將不同信息源中的實體匹配來進(jìn)行模式集成。通常借助于數(shù)據(jù)庫或數(shù)據(jù)倉庫的元數(shù)據(jù)進(jìn)行模式識別；冗余數(shù)據(jù)集成。在數(shù)據(jù)集成中往往導(dǎo)致數(shù)據(jù)冗余，如同一屬性多次出現(xiàn)、同一屬性命名不一致等。對于屬性間冗余，可以先采用相關(guān)性分析檢測，然后刪除；數(shù)據(jù)值沖突的檢測與處理。由于表示、比例、編碼等的不同，現(xiàn)實世界中的同一實體，在不同數(shù)據(jù)源的屬性值可能不同。這種數(shù)據(jù)語義上的歧義性是數(shù)據(jù)集成的最大難點，目前沒有很好的辦法解決。3、數(shù)據(jù)變換數(shù)據(jù)變換是采用線性或非線性的數(shù)學(xué)變換方法將多維數(shù)據(jù)壓縮成較少維數(shù)的數(shù)據(jù)，消除它

6、們在時間、空間、屬性及精度等特征表現(xiàn)方面的差異。這方法雖然對原始數(shù)據(jù)都有一定的損害，但其結(jié)果往往具有更大的實用性。常見數(shù)據(jù)變換方法如下：數(shù)據(jù)平滑：去除數(shù)據(jù)中的噪聲數(shù)據(jù)，將連續(xù)數(shù)據(jù)離散化，增加粒度。通常采用分箱、聚類和回歸技術(shù)。數(shù)據(jù)聚集：對數(shù)據(jù)進(jìn)行匯總和聚集。數(shù)據(jù)概化：減少數(shù)據(jù)復(fù)雜度，用高層概念替換。數(shù)據(jù)規(guī)范化：使屬性數(shù)據(jù)按比例縮放，使之落入一個小的特定區(qū)域；常用的規(guī)范化方法有最小-最大規(guī)范化、z一score規(guī)范化、按小數(shù)定標(biāo)規(guī)范化等。屬性構(gòu)造：構(gòu)造出新的屬性并添加到屬性集中，以幫助挖掘過程。應(yīng)用實例表明，通過數(shù)據(jù)變換可用相當(dāng)少的變量來捕獲原始數(shù)據(jù)的最大變化。具體采用哪種變換方法應(yīng)根據(jù)涉及的相關(guān)

7、數(shù)據(jù)的屬性特點而定，根據(jù)研究目的可把定性問題定量化，也可把定量問題定性化。4、數(shù)據(jù)歸約數(shù)據(jù)歸約技術(shù)可以用來得到數(shù)據(jù)集的歸約表示，它接近于保持原數(shù)據(jù)的完整性，但數(shù)據(jù)量比原數(shù)據(jù)小得多。與非歸約數(shù)據(jù)相比，在歸約的數(shù)據(jù)上進(jìn)行挖掘，所需的時間和內(nèi)存資源更少，挖掘?qū)⒏行Вa(chǎn)生相同或幾乎相同的分析結(jié)果。幾種數(shù)據(jù)歸約的方法：（1）維歸約：通過刪除不相關(guān)的屬性（或維）減少數(shù)據(jù)量。不僅壓縮了數(shù)據(jù)集，還減少了出現(xiàn)在發(fā)現(xiàn)模式上的屬性數(shù)目。通常采用屬性子集選擇方法找出最小屬性集，使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性的原分布。屬性子集選擇的啟發(fā)式方法技術(shù)有：逐步向前選擇，由空屬性集開始，將原屬性集中“最好的”

8、屬性逐步填加到該集合中；逐步向后刪除，由整個屬性集開始，每一步刪除當(dāng)前屬性集中的“最壞”屬性；向前選擇和向后刪除的結(jié)合，每一步選擇“最好的”屬性，刪除“最壞的”屬性；判定樹歸納，使用信息增益度量建立分類判定樹，樹中的屬性形成歸約后的屬性子集。（2）數(shù)據(jù)壓縮：應(yīng)用數(shù)據(jù)編碼或變換，得到原數(shù)據(jù)的歸約或壓縮表示。數(shù)據(jù)壓縮分為無損壓縮和有損壓縮。比較流行和有效的有損數(shù)據(jù)壓縮方法是小波變換和主要成分分析。小波變換對于稀疏或傾斜數(shù)據(jù)以及具有有序?qū)傩缘臄?shù)據(jù)有很好的壓縮結(jié)果。主要成分分析計算花費低，可以用于有序或無序的屬性，并且可以處理稀疏或傾斜數(shù)據(jù)。（3）數(shù)值歸約：通過選擇替代的、較小的數(shù)據(jù)表示形式來減少數(shù)據(jù)

9、量。數(shù)值歸約技術(shù)可以是有參的，也可以是無參的。有參方法是使用一個模型來評估數(shù)據(jù)，只需存放參數(shù)，而不需要存放實際數(shù)據(jù)。有參的數(shù)值歸約技術(shù)有以下2種：回歸：線性回歸和多元回歸；對數(shù)線性模型：近似離散屬性集中的多維概率分布。無參的數(shù)值歸約技術(shù)有3種：直方圖：采用分箱技術(shù)來近似數(shù)據(jù)分布,是一種流行的數(shù)值歸約形式。其中V-最優(yōu)和MaxDiff直方圖是最精確和最實用的；聚類：聚類是將數(shù)據(jù)元組視為對象，它將對象劃分為群或聚類，使得在一個聚類中的對象“類似”，而與其他聚類中的對象“不類似”，在數(shù)據(jù)歸約時用數(shù)據(jù)的聚類代替實際數(shù)據(jù)；選樣：用數(shù)據(jù)的較小隨機(jī)樣本表示大的數(shù)據(jù)集，如簡單選樣、聚類選樣和分層選樣等（4）概

10、念分層：通過收集并用較高層的概念替換較低層的概念來定義數(shù)值屬性的一個離散化。概念分層可以用來歸約數(shù)據(jù)，通過這種概化盡管細(xì)節(jié)丟失了，但概化后的數(shù)據(jù)更有意義、更容易理解，并且所需的空間比原數(shù)據(jù)少。對于數(shù)值屬性，由于數(shù)據(jù)的可能取值范圍的多樣性和數(shù)據(jù)值的更新頻繁，說明概念分層是困難的。數(shù)值屬性的概念分層可以根據(jù)數(shù)據(jù)的分布分析自動地構(gòu)造，如用分箱、直方圖分析、聚類分析、基于熵的離散化和自然劃分分段等技術(shù)生成數(shù)值概念分層。分類數(shù)據(jù)本身是離散數(shù)據(jù)，一個分類屬性具有有限個不同值，值之間無序。一種方法是由用戶專家在模式級顯示地說明屬性的部分序或全序，從而獲得概念的分層；另一種方法是只說明屬性集，但不說明它們的偏

11、序，由系統(tǒng)根據(jù)每個屬性不同值的個數(shù)產(chǎn)生屬性序，自動構(gòu)造有意義的概念分層。5、小結(jié)在數(shù)據(jù)實際挖掘過程中，針對不同的數(shù)據(jù)源和數(shù)據(jù)挖掘目標(biāo)，有選擇的使用數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)變換和數(shù)據(jù)歸約等數(shù)據(jù)預(yù)處理方法和技術(shù)。它們的使用沒有先后順序的約束，某一種預(yù)處理可能需要循環(huán)多次進(jìn)行，某一種預(yù)處理可能一次也不需要。盡管有多種數(shù)據(jù)預(yù)處理的方法和技術(shù)，但都不夠成熟。所以，對數(shù)據(jù)挖掘中的數(shù)據(jù)預(yù)處理還需要做更進(jìn)一步的深入研究。二、數(shù)據(jù)挖掘十大經(jīng)典算法國際權(quán)威的學(xué)術(shù)組織theIEEEInternationalConferenceonDataMining(ICDM)2006年12月評選出了數(shù)據(jù)挖掘領(lǐng)域的十大經(jīng)典算法：C

12、4.5,k-Means,SVM,Apriori,EM,PageRank,AdaBoost,kNN,NaiveBayes,andCART.C4.5算法：是ID3算法的擴(kuò)展，它能夠產(chǎn)生用決策樹表示的分類器，而且它還可以通過更加容易理解的規(guī)則集形式來表示分類器。K-means算法：是一種簡單的迭代算法，它能夠?qū)⒔o定的數(shù)據(jù)集劃分為用戶定義的聚簇數(shù)目。SVM支持向量機(jī)：在機(jī)器學(xué)習(xí)應(yīng)用中，支持向量機(jī)被考慮為很重要的一個嘗試在所有著名的算法中，它提供了一種穩(wěn)定準(zhǔn)確的方法。它擁有強(qiáng)大的理論基礎(chǔ)，只需要少數(shù)示例進(jìn)行訓(xùn)練，并且對數(shù)據(jù)集維度數(shù)量不敏感。另外，訓(xùn)練SVM的有效方法已經(jīng)得到快速地發(fā)展。Apriori算法

13、：最流行的數(shù)據(jù)挖掘方法之一就是從交易數(shù)據(jù)集中尋找頻繁項集，并且產(chǎn)生關(guān)聯(lián)規(guī)則。尋找頻繁項目集是非平凡的，因為它存在組合爆炸的問題。一旦獲得到頻繁項目集，就可以直接根據(jù)用戶定義的置信度產(chǎn)生關(guān)聯(lián)規(guī)則。Apriori算法是一種采用候選集方法尋找頻繁項目集。它是一種使用反單調(diào)性的完全層次搜索算法。如果一個項目集是非頻繁的，那么它的任何超集都是非頻繁的。EM算法：有限混合分布提供一種靈活的，基于數(shù)學(xué)的建模和聚類數(shù)據(jù)集方法。常見的混合模型可以用來聚類連續(xù)數(shù)據(jù)和預(yù)測潛在的密度函數(shù)。這些混合模型可以通過最大似然的期望最大化算法來進(jìn)行擬合。PageRank算法：是一種使用互聯(lián)網(wǎng)上的超鏈接的搜索排序算法。PageR

14、ank基本的方法是，越是重要的文件鏈接一個文件，則這個文件就越重要，但那些入站鏈接并不是被平等計算的。首先，如果其他高等級的文件連接到它，那么根據(jù)PageRank的規(guī)則，此文件的等級也高。AdaBoost：集成學(xué)習(xí)是應(yīng)用多個學(xué)習(xí)器來解決問題。一般來說，集成學(xué)習(xí)的能力較單個學(xué)習(xí)器的效果更優(yōu)。因此，集成學(xué)習(xí)方法具有很強(qiáng)的吸引能力。AdaBoost方法是最重要的集成學(xué)習(xí)算法之一，它擁有牢固的理論基礎(chǔ)，預(yù)測非常準(zhǔn)確，并且簡單和易于實現(xiàn)。KNN分類算法：是通過在數(shù)據(jù)集中尋找與測試對象最近的k個對象。并且，預(yù)先定義類別標(biāo)簽。KNN有三個主要的核心元素：標(biāo)記對象集合，對象之間的相似性度量或者距離度量，最近鄰

15、居個數(shù)K。為了區(qū)分沒有標(biāo)記的對象，計算對象與標(biāo)記對象之間的距離。從而，識別k個最近鄰居。這些最近鄰居的類別標(biāo)簽被用來決定對象的類別標(biāo)簽。樸素貝葉斯：發(fā)源于古典數(shù)學(xué)理論，有著堅實的數(shù)學(xué)基礎(chǔ)，以及穩(wěn)定的分類效率。同時，NBC模型所需估計的參數(shù)很少，對缺失數(shù)據(jù)不太敏感，算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。但是實際上并非總是如此，這是因為NBC模型假設(shè)屬性之間相互獨立，這個假設(shè)在實際應(yīng)用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。CART：包括分類樹和回歸樹兩部分：分類樹的結(jié)果變量是分類變量，回歸樹的結(jié)果變量是連續(xù)變量。CART是一種樹型結(jié)構(gòu)，由樹結(jié)和連

16、線組成，在末端的樹結(jié)又稱為終止結(jié)。CART可分析同質(zhì)性較差的數(shù)據(jù)，采用替代變量的方法解決缺失數(shù)據(jù)問題，不要求數(shù)據(jù)的分布，可同時利用各種類型的數(shù)據(jù)。三、階段小結(jié)經(jīng)歷了一個星期數(shù)據(jù)挖掘的學(xué)習(xí)，筆者從一名只知數(shù)據(jù)挖掘其名而不知其為何物的本科低年級學(xué)生，成為一名初識BI和數(shù)據(jù)挖掘初學(xué)者，在學(xué)習(xí)這門學(xué)科的過程中體會到了發(fā)現(xiàn)和探索的樂趣。坦白地說，一開始每天將自己的學(xué)習(xí)筆記發(fā)布博客分享給大家時，我的內(nèi)心十分忐忑，一來作為一名初學(xué)者，缺少整體的知識結(jié)構(gòu)，難免會出現(xiàn)邏輯混亂，整理不完全，甚至無法甄別網(wǎng)絡(luò)上數(shù)據(jù)的真?zhèn)蔚那闆r；二來五篇博客中的大部分內(nèi)容都是摘抄與筆記，原創(chuàng)的東西甚少，我害怕讓瀏覽博客的讀者重復(fù)閱讀

17、，耽誤大家的時間。然而，在過程中，我逐漸地發(fā)現(xiàn)分享學(xué)習(xí)筆記型的博客亦有其獨特的長處：整理筆記發(fā)布博客的過程既讓我反復(fù)核實自己的筆記中是否有差錯的存在（用所學(xué)的知識就是數(shù)據(jù)預(yù)處理），又獲得了一個結(jié)交志同道合伙伴的途徑。當(dāng)然，在五篇的學(xué)習(xí)筆記中仍然不免存在著個人能力暫時無法企及的差錯，我希望自己盡力完善，同時也懇請讀者們不吝指教與多多包涵。說回到BI與數(shù)據(jù)挖掘本身，BI從被提出至今只有二十年的時間，數(shù)據(jù)挖掘的歷史也并不漫長，但在大數(shù)據(jù)時代的今天，數(shù)據(jù)挖掘已經(jīng)成為發(fā)展的潮流與趨勢。馬云曾說過，“這是一個變化的年代，當(dāng)很多人還沒有搞懂PC互聯(lián)網(wǎng)的時候，移動互聯(lián)網(wǎng)來了，當(dāng)很多人還沒弄懂移動互聯(lián)網(wǎng)，大數(shù)據(jù)

18、來了?！睂W(xué)習(xí)數(shù)據(jù)挖掘，無論是成為一個從業(yè)者，還是僅僅作為了解，都將讓我們在如今的一個時代中不至于太過落后。在學(xué)習(xí)數(shù)據(jù)挖掘的過程中，逐漸了解了一些關(guān)于數(shù)據(jù)挖掘的歷史、概念、流程、技術(shù)方法和應(yīng)用實例，當(dāng)然，對于數(shù)據(jù)挖掘的本質(zhì)，此時尚不敢妄談，大約是數(shù)據(jù)不再因果關(guān)系而更多地是相關(guān)關(guān)系，有待以后繼續(xù)學(xué)習(xí)、驗證、體悟。學(xué)習(xí)的過程中SmartBi軟件公司的軟件給予了我巨大的幫助，無論是電子表格版還是SmartMining都在學(xué)習(xí)過程中讓我對數(shù)據(jù)挖掘有了更直觀的體驗。軟件的操作只簡便令我享受其中。在本文中雖然介紹了數(shù)據(jù)挖掘的十大算法，但在使用SmartMining的過程中我未曾寫過一行代碼（當(dāng)然這和我現(xiàn)在的水平較低也有一定關(guān)系），軟件將操作代碼的封裝和拖拽圖標(biāo)即可實現(xiàn)操作使得它變得極為簡潔和易上手，尤其數(shù)據(jù)可視化的操作，圖表的繪制之方便無疑讓我在學(xué)習(xí)的過