數(shù)據(jù)挖掘領(lǐng)域經(jīng)典算法

偶見網(wǎng)頁數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法，心血來潮，在學(xué)習(xí)的同時(shí)也想驗(yàn)驗(yàn)有哪些知道哪些實(shí)現(xiàn)過。

2006年12月，國際權(quán)威的學(xué)術(shù)組織the IEEE International Conference on Data Mining (ICDM)閑著沒事或者為了提高點(diǎn)會(huì)議知名度評(píng)選了數(shù)據(jù)挖掘領(lǐng)域的十大經(jīng)典算法。首先來看看參加評(píng)選的18個(gè)候選算法。

1：C4.5

C4.5就是一個(gè)決策樹算法，它是決策樹(決策樹也就是做決策的節(jié)點(diǎn)間的組織方式像一棵樹，其實(shí)是一個(gè)倒樹)核心算法ID3的改進(jìn)算法，所以基本上了解了一半決策樹構(gòu)造方法就能構(gòu)造它。決策樹構(gòu)造方法其實(shí)就是每次選擇一個(gè)好的特征以及分裂點(diǎn)作為當(dāng)前節(jié)點(diǎn)的分類條件。C4.5比ID3改進(jìn)的地方時(shí)：

1)       ID3選擇屬性用的是子樹的信息增益(這里可以用很多方法來定義信息，ID3使用的是熵(entropy)(熵是一種不純度度量準(zhǔn)則)),也就是熵的變化值.而C4.5用的是信息增益率。也就是多了個(gè)率嘛。一般來說率就是用來取平衡用的，就像方差起的作用差不多，比如有兩個(gè)跑步的人，一個(gè)起點(diǎn)是10m/s的人、其1s后為20m/s；另一個(gè)人起速是1m/s、其1s后為2m/s。如果緊緊算差值那么兩個(gè)差距就很大了，如果使用速度增加率(加速度)來衡量，2個(gè)人就是一樣了。在這里，其克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足。

2)       在樹構(gòu)造過程中進(jìn)行剪枝，我在構(gòu)造決策樹的時(shí)候好討厭那些掛著幾個(gè)元素的節(jié)點(diǎn)。對(duì)于這種節(jié)點(diǎn)，干脆不考慮最好，不然很容易導(dǎo)致overfitting。

3)       對(duì)非離散數(shù)據(jù)都能處理，這個(gè)其實(shí)就是一個(gè)個(gè)式，看對(duì)于連續(xù)型的值在哪里分裂好。也就是把連續(xù)性的數(shù)據(jù)轉(zhuǎn)化為離散的值進(jìn)行處理。

4)       能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理，這個(gè)重要也重要，其實(shí)也沒那么重要，缺失數(shù)據(jù)采用一些方法補(bǔ)上去就是了。

2：CART

CART也是一種決策樹算法！相對(duì)于上著有條件實(shí)現(xiàn)一個(gè)節(jié)點(diǎn)下面有多個(gè)子樹的多元分類，CART只是分類兩個(gè)子樹，這樣實(shí)現(xiàn)起來稍稍簡便些。所以說CART算法生成的決策樹是結(jié)構(gòu)簡潔的二叉樹。

3：KNN(K Nearest Neighbours)

這個(gè)很簡單，就是看你周圍的K個(gè)人(樣本)那個(gè)類別的人占的多，那個(gè)多那我也是那個(gè)多的。實(shí)現(xiàn)起來就是對(duì)每個(gè)訓(xùn)練樣本都計(jì)算與其相似度，選擇相似度Top-K個(gè)訓(xùn)練樣本出來，看這K個(gè)樣本中那個(gè)類別的多些，誰多跟誰。

4：Na?ve Bayes(樸素貝葉斯NB)

NB認(rèn)為各個(gè)特征是獨(dú)立的，誰也不關(guān)誰的事。所以一個(gè)樣本(特征值的集合，比如”數(shù)據(jù)結(jié)構(gòu)”出現(xiàn)2詞，“文件”出現(xiàn)1詞)，可以通過對(duì)其所有出現(xiàn)特征在給定類別的概率相乘。比如“數(shù)據(jù)結(jié)構(gòu)”出現(xiàn)在類1的概率為0.5，“文件”出現(xiàn)在類1的概率為0.3，則可認(rèn)為其屬于類1的概率為0.5*0.5*0.3。

5：Support Vector Machine(支持向量機(jī)SVM)

SVM就是想找一個(gè)分類得最”好”的分類線/分類面(最近的一些兩類樣本到這個(gè)”線”的距離最遠(yuǎn))。這個(gè)沒具體實(shí)現(xiàn)過，上次聽課，那位老師自稱自己實(shí)現(xiàn)了SVM，敬佩其鉆研精神。常用的工具包是LibSVM,SVMLight,MySVM.

6：EM(期望最大化)

這個(gè)我認(rèn)為就是假設(shè)數(shù)據(jù)時(shí)由幾個(gè)高斯分布組成的，所以最后就是要求幾個(gè)高斯分布的參數(shù)。通過先假設(shè)幾個(gè)值，然后通過反復(fù)迭代，以期望得到最好的擬合。

7：Apriori

這個(gè)是做關(guān)聯(lián)規(guī)則用的。不知道為什么，一提高關(guān)聯(lián)規(guī)則我就想到購物籃數(shù)據(jù)。這個(gè)沒實(shí)現(xiàn)過，不過也還要理解，它就是通過支持度和置信度兩個(gè)量來工作，不過對(duì)于Apriori，它通過頻繁項(xiàng)集的一些規(guī)律(頻繁項(xiàng)集的子集必定是頻繁項(xiàng)集等等啦)來減少計(jì)算復(fù)雜度。

8：FP-Tree(Mining frequent patterns without candidate generation)

這個(gè)也不太清楚。FP-growth算法(Frequent Pattern-growth)使用了一種緊縮的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)查找頻繁項(xiàng)集所需要的全部信息。采用算法：將提供頻繁項(xiàng)集的數(shù)據(jù)庫壓縮到一棵FP-tree來保留項(xiàng)集關(guān)聯(lián)信息，然后將壓縮后的數(shù)據(jù)庫分成一組條件數(shù)據(jù)庫（一種特殊類型的投影數(shù)據(jù)庫），每個(gè)條件數(shù)據(jù)庫關(guān)聯(lián)一個(gè)頻繁項(xiàng)集。

9：PageRank

大名鼎鼎的PageRank大家應(yīng)該都知道(Google靠此專利發(fā)家，其實(shí)也不能說發(fā)家啦!)。對(duì)于這個(gè)算法我的理解就是：如果我指向你(網(wǎng)頁間的連接)則表示我承認(rèn)你，則在計(jì)算你的重要性的時(shí)候可以加上我的一部分重要性(到底多少，要看我自己有多少和我共承認(rèn)多少個(gè)人)。通過反復(fù)這樣來，可以求的一個(gè)穩(wěn)定的衡量各個(gè)人(網(wǎng)頁)重要性的值。不過這里必須要做些限制(一個(gè)人的開始默認(rèn)重要性都是1)，不然那些值會(huì)越來越大越來越大。

10：HITS

HITS也是一個(gè)連接分析算法，它是由IBM首先提出的。在HITS，每個(gè)節(jié)點(diǎn)(網(wǎng)頁)都有一個(gè)重要度和權(quán)威度(Hubs and authorities,我也忘了具體的翻譯是什么了)。通過反復(fù)通過權(quán)威度來求重要度，通過重要度來求權(quán)威度得到最后的權(quán)威度和重要度。

11：K-Means

K-Means是一種最經(jīng)典也是使用最廣泛的聚類方法，時(shí)至今日任然有很多基于其的改進(jìn)模型提出。K-Means的思想很簡單，對(duì)于一個(gè)聚類任務(wù)(你需要指明聚成幾個(gè)類，當(dāng)然按照自然想法來說不應(yīng)該需要指明類數(shù)，這個(gè)問題也是當(dāng)前聚類任務(wù)的一個(gè)值得研究的課題)，首先隨機(jī)選擇K個(gè)簇中心，然后反復(fù)計(jì)算下面的過程直到所有簇中心不改變(簇集合不改變)為止：步驟1：對(duì)于每個(gè)對(duì)象，計(jì)算其與每個(gè)簇中心的相似度，把其歸入與其最相似的那個(gè)簇中。

步驟2：更新簇中心，新的簇中心通過計(jì)算所有屬于該簇的對(duì)象的平均值得到。

k-means 算法的工作過程說明如下：首先從n個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類中心；而對(duì)于所剩下其它對(duì)象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然后再計(jì)算每個(gè)所獲新聚類的聚類中心（該聚類中所有對(duì)象的均值）；不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù). k個(gè)聚類具有以下特點(diǎn)：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。

12：BIRCH

BIRCH也是一種聚類算法，其全稱是Balanced Iterative Reducing and Clustering using Hierarchies。BIRCH也是只是看了理論沒具體實(shí)現(xiàn)過。是一個(gè)綜合的層次聚類特征(Clustering Feature, CF)和聚類特征樹(CF Tree)兩個(gè)概念，用于概括聚類描述。聚類特征樹概括了聚類的有用信息，并且占用空間較元數(shù)據(jù)集合小得多，可以存放在內(nèi)存中，從而可以提高算法在大型數(shù)據(jù)集合上的聚類速度及可伸縮性。

BIRCH算法包括以下兩個(gè)階段：

1）掃描數(shù)據(jù)庫，建立動(dòng)態(tài)的一棵存放在內(nèi)存的CF Tree。如果內(nèi)存不夠，則增大閾值，在原樹基礎(chǔ)上構(gòu)造一棵較小的樹。

2）對(duì)葉節(jié)點(diǎn)進(jìn)一步利用一個(gè)全局性的聚類算法，改進(jìn)聚類質(zhì)量。

由于CF Tree的葉節(jié)點(diǎn)代表的聚類可能不是自然的聚類結(jié)果，原因是給定的閾值限制了簇的大小，并且數(shù)據(jù)的輸入順序也會(huì)影響到聚類結(jié)果。因此需要對(duì)葉節(jié)點(diǎn)進(jìn)一步利用一個(gè)全局性的聚類算法，改進(jìn)聚類質(zhì)量。

13：AdaBoost

AdaBoost做分類的一般知道，它是一種boosting方法。這個(gè)不能說是一種算法，應(yīng)該是一種方法，因?yàn)樗梢越⒃谌魏我环N分類算法上，可以是決策樹，NB，SVM等。

Adaboost是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構(gòu)成一個(gè)更強(qiáng)的最終分類器(強(qiáng)分類器)。其算法本身是通過改變數(shù)據(jù)分布來實(shí)現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個(gè)樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率，來確定每個(gè)樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進(jìn)行訓(xùn)練，最后將每次訓(xùn)練得到的分類器最后融合起來，作為最后的決策分類器。使用adaboost分類器可以排除一些不必要的訓(xùn)練數(shù)據(jù)，并將關(guān)鍵放在關(guān)鍵的訓(xùn)練數(shù)據(jù)上面。

14：GSP

GSP，全稱為Generalized Sequential Pattern(廣義序貫?zāi)Ｊ?，是一種序列挖掘算法。對(duì)于序列挖掘沒有仔細(xì)看過，應(yīng)該是基于關(guān)聯(lián)規(guī)則的吧！網(wǎng)上是這樣說的：

GSP類似于Apriori算法，采用冗余候選模式的剪除策略和特殊的數(shù)據(jù)結(jié)構(gòu)-----哈希樹來實(shí)現(xiàn)候選模式的快速訪存。

GSP算法描述:

1）掃描序列數(shù)據(jù)庫，得到長度為1的序列模式L1，作為初始的種子集。

2）根據(jù)長度為i 的種子集Li ，通過連接操作和修剪操作生成長度為i+1的候選序列模式Ci+1；然后掃描序列數(shù)據(jù)庫，計(jì)算每個(gè)候選序列模式的支持度，產(chǎn)生長度為i+1的序列模式Li+1，并將Li+1作為新的種子集。

3）重復(fù)第二步，直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止。

產(chǎn)生候選序列模式主要分兩步：

連接階段：如果去掉序列模式s1的第一個(gè)項(xiàng)目與去掉序列模式s2的最后一個(gè)項(xiàng)目所得到的序列相同，則可以將s1與s2進(jìn)行連接，即將s2的最后一個(gè)項(xiàng)目添加到s1中。

修切階段：若某候選序列模式的某個(gè)子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除。

候選序列模式的支持度計(jì)算：對(duì)于給定的候選序列模式集合C，掃描序列數(shù)據(jù)庫，對(duì)于其中的每一條序列s,找出集合C中被s所包含的所有候選序列模式，并增加其支持度計(jì)數(shù)。

15：PrefixSpan

又是一個(gè)類似Apriori的序列挖掘算法。不了解。

16：CBA

暈，還以為是Chinese Basketball Association呢！原來CBA(classification based on association)是基于關(guān)聯(lián)規(guī)則發(fā)現(xiàn)方法的分類算法。該算法分兩個(gè)步驟構(gòu)造分類器。第一步：發(fā)現(xiàn)所有形如xi1∧x => Ci 的關(guān)聯(lián)規(guī)則，即右部為類別屬性值的類別關(guān)聯(lián)規(guī)則(classification association rules，CAR)。第二步：從已發(fā)現(xiàn)的CAR中選擇高優(yōu)先度的規(guī)則來覆蓋訓(xùn)練集，也就是說，如果有多條關(guān)聯(lián)規(guī)則的左部相同，而右部為不同的類，則選擇具有最高置信度的規(guī)則作為可能規(guī)則。

17：Finding reduct

18：gSpan

這兩位都不怎么了解。Finding reduct是粗糙集約減算法。gSpan是圖挖掘算法。

當(dāng)然最后奪得前十名頭銜的分別是：C4.5，K-Means，SVM，Apriori，EM，PageRank，AdaBoost，KNN，NB和CART。