詳細(xì)解釋數(shù)據(jù)挖掘中的十大算法

在一份調(diào)查問卷中，三個(gè)獨(dú)立專家小組投票選出的十大最有影響力的數(shù)據(jù)挖掘算法，今天我打算用簡(jiǎn)單的語言來解釋一下。

一旦你知道了這些算法是什么、怎么工作、能做什么、在哪里能找到，我希望你能把這篇博文當(dāng)做一個(gè)跳板，學(xué)習(xí)更多的數(shù)據(jù)挖掘知識(shí)。

還等什么？這就開始吧！

1.C4.5算法

C4.5是做什么的？C4.5 以決策樹的形式構(gòu)建了一個(gè)分類器。為了做到這一點(diǎn)，需要給定 C4.5 表達(dá)內(nèi)容已分類的數(shù)據(jù)集合。

等下，什么是分類器呢？ 分類器是進(jìn)行數(shù)據(jù)挖掘的一個(gè)工具，它處理大量需要進(jìn)行分類的數(shù)據(jù)，并嘗試預(yù)測(cè)新數(shù)據(jù)所屬的類別。

舉個(gè)例子吧，假定一個(gè)包含很多病人信息的數(shù)據(jù)集。我們知道每個(gè)病人的各種信息，比如年齡、脈搏、血壓、最大攝氧量、家族病史等。這些叫做數(shù)據(jù)屬性。

現(xiàn)在：

給定這些屬性，我們想預(yù)測(cè)下病人是否會(huì)患癌癥。病人可能會(huì)進(jìn)入下面兩個(gè)分類：會(huì)患癌癥或者不會(huì)患癌癥。 C4.5 算法會(huì)告訴我們每個(gè)病人的分類。

做法是這樣的：

用一個(gè)病人的數(shù)據(jù)屬性集和對(duì)應(yīng)病人的反饋類型，C4.5 構(gòu)建了一個(gè)基于新病人屬性預(yù)測(cè)他們類型的決策樹。

這點(diǎn)很棒，那么什么是決策樹呢？決策樹學(xué)習(xí)是創(chuàng)建一種類似與流程圖的東西對(duì)新數(shù)據(jù)進(jìn)行分類。使用同樣的病人例子，一個(gè)特定的流程圖路徑可以是這樣的：

病人有癌癥的病史

病人有和癌癥病人高度相似的基因表達(dá)

病人有腫瘤

病人的腫瘤大小超過了5cm

基本原則是：

流程圖的每個(gè)環(huán)節(jié)都是一個(gè)關(guān)于屬性值的問題，并根據(jù)這些數(shù)值，病人就被分類了。你可以找到很多決策樹的例子。

算法是監(jiān)督學(xué)習(xí)還是無監(jiān)督學(xué)習(xí)呢？這是一個(gè)監(jiān)督學(xué)習(xí)算法，因?yàn)橛?xùn)練數(shù)據(jù)是已經(jīng)分好類的。使用分好類的病人數(shù)據(jù)，C4.5算法不需要自己學(xué)習(xí)病人是否會(huì)患癌癥。

那 C4.5 算法和決策樹系統(tǒng)有什么區(qū)別呢？

首先，C4.5 算法在生成信息樹的時(shí)候使用了信息增益。

其次，盡管其他系統(tǒng)也包含剪枝，C4.5使用了一個(gè)單向的剪枝過程來緩解過渡擬合。剪枝給結(jié)果帶來了很多改進(jìn)。

再次，C4.5算法既可以處理連續(xù)數(shù)據(jù)也可以處理離散數(shù)據(jù)。我的理解是，算法通過對(duì)連續(xù)的數(shù)據(jù)指定范圍或者閾值，從而把連續(xù)數(shù)據(jù)轉(zhuǎn)化為離散的數(shù)據(jù)。

最后，不完全的數(shù)據(jù)用算法自有的方式進(jìn)行了處理。

為什么使用 C4.5算法呢？可以這么說，決策樹最好的賣點(diǎn)是他們方便于翻譯和解釋。他們速度也很快，是種比較流行的算法。輸出的結(jié)果簡(jiǎn)單易懂。

哪里可以使用它呢？ 在 OpenTox 上可以找到一個(gè)很流行的開源 Java實(shí)現(xiàn)方法。Orange 是一個(gè)用于數(shù)據(jù)挖掘的開源數(shù)據(jù)可視化和分析工具，它的決策樹分類器是用 C4.5實(shí)現(xiàn)的。

分類器是很棒的東西，但也請(qǐng)看看下一個(gè)聚類算法….

2. k 均值聚類算法

它是做什么的呢？K-聚類算法從一個(gè)目標(biāo)集中創(chuàng)建多個(gè)組，每個(gè)組的成員都是比較相似的。這是個(gè)想要探索一個(gè)數(shù)據(jù)集時(shí)比較流行的聚類分析技術(shù)。

等下，什么是聚類分析呢？聚類分析屬于設(shè)計(jì)構(gòu)建組群的算法，這里的組成員相對(duì)于非組成員有更多的相似性。在聚類分析的世界里，類和組是相同的意思。

舉個(gè)例子，假設(shè)我們定義一個(gè)病人的數(shù)據(jù)集。在聚類分析里，這些病人可以叫做觀察對(duì)象。我們知道每個(gè)病人的各類信息，比如年齡、血壓、血型、最大含氧量和膽固醇含量等。這是一個(gè)表達(dá)病人特性的向量。

請(qǐng)看：

你可以基本認(rèn)為一個(gè)向量代表了我們所知道的病人情況的一列數(shù)據(jù)。這列數(shù)據(jù)也可以理解為多維空間的坐標(biāo)。脈搏是一維坐標(biāo)，血型是其他維度的坐標(biāo)等等。

你可能會(huì)有疑問：

給定這個(gè)向量集合，我們?cè)趺窗丫哂邢嗨颇挲g、脈搏和血壓等數(shù)據(jù)的病人聚類呢？

想知道最棒的部分是什么嗎？

你告訴 k-means 算法你想要多少種類。K-means 算法會(huì)處理后面的部分。

那它是怎么處理的呢？k-means 算法有很多優(yōu)化特定數(shù)據(jù)類型的變量。

Kmeans算法更深層次的這樣處理問題：

1. k-means 算法在多維空間中挑選一些點(diǎn)代表每一個(gè) k 類。他們叫做中心點(diǎn)。

2. 每個(gè)病人會(huì)在這 k 個(gè)中心點(diǎn)中找到離自己最近的一個(gè)。我們希望病人最靠近的點(diǎn)不要是同一個(gè)中心點(diǎn)，所以他們?cè)诳拷麄冏罱闹行狞c(diǎn)周圍形成一個(gè)類。

3. 我們現(xiàn)在有 k 個(gè)類，并且現(xiàn)在每個(gè)病人都是一個(gè)類中的一員。

4. 之后k-means 算法根據(jù)它的類成員找到每個(gè) k 聚類的中心（沒錯(cuò)，用的就是病人信息向量）

5. 這個(gè)中心成為類新的中心點(diǎn)。

6. 因?yàn)楝F(xiàn)在中心點(diǎn)在不同的位置上了，病人可能現(xiàn)在靠近了其他的中心點(diǎn)。換句話說，他們可能會(huì)修改自己的類成員身份。

7. 重復(fù)2-6步直到中心點(diǎn)不再改變，這樣類成員也就穩(wěn)定了。這也叫做收斂性。

這算法是監(jiān)督的還是非監(jiān)督的呢？這要看情況了，但是大多數(shù)情況下 k-means 會(huì)被劃分為非監(jiān)督學(xué)習(xí)的類型。并不是指定分類的個(gè)數(shù)，也沒有觀察對(duì)象該屬于那個(gè)類的任何信息，k-means算法自己“學(xué)習(xí)”如何聚類。k-means 可以是半監(jiān)督的。

為什么要使用 k-means 算法呢？我認(rèn)為大多數(shù)人都同意這一點(diǎn)：

k-means 關(guān)鍵賣點(diǎn)是它的簡(jiǎn)單。它的簡(jiǎn)易型意味著它通常要比其他的算法更快更有效，尤其是要大量數(shù)據(jù)集的情況下更是如此。

他可以這樣改進(jìn)：

k-means 可以對(duì)已經(jīng)大量數(shù)據(jù)集進(jìn)行預(yù)先聚類處理，然后在針對(duì)每個(gè)子類做成本更高點(diǎn)的聚類分析。k-means 也能用來快速的處理“K”和探索數(shù)據(jù)集中是否有被忽視的模式或關(guān)系。

但用k-means 算法也不是一帆風(fēng)順的：

k means算法的兩個(gè)關(guān)鍵弱點(diǎn)分別是它對(duì)異常值的敏感性和它對(duì)初始中心點(diǎn)選擇的敏感性。最后一個(gè)需要記住的是， K-means 算法是設(shè)計(jì)來處理連續(xù)數(shù)據(jù)的。對(duì)于離散數(shù)據(jù)你需要使用一些小技巧后才能讓 K-means 算法奏效。

Kmeans 在哪里使用過呢？ 網(wǎng)上有很多可獲得的 kmeans 聚類算法的語言實(shí)現(xiàn)：

 Apache Mahout

 Julia

 R

SciPy

 Weka

MATLAB

 SAS

（ http://blog.jobbole.com/90316/ 點(diǎn)擊“閱讀原文” ，可跳轉(zhuǎn)閱讀）

如果決策樹和聚類算法還沒有打動(dòng)你，那么你會(huì)喜歡下一個(gè)算法的。

3.支持向量機(jī)

它是做什么的呢？支持向量機(jī)（SVM）獲取一個(gè)超平面將數(shù)據(jù)分成兩類。以高水準(zhǔn)要求來看，除了不會(huì)使用決策樹以外，SVM與 C4.5算法是執(zhí)行相似的任務(wù)的。

咦？一個(gè)超..什么？ 超平面（hyperplane）是個(gè)函數(shù)，類似于解析一條線的方程。實(shí)際上，對(duì)于只有兩個(gè)屬性的簡(jiǎn)單分類任務(wù)來說，超平面可以是一條線的。

其實(shí)事實(shí)證明：

SVM 可以使用一個(gè)小技巧，把你的數(shù)據(jù)提升到更高的維度去處理。一旦提升到更高的維度中，SVM算法會(huì)計(jì)算出把你的數(shù)據(jù)分離成兩類的最好的超平面。

有例子么？當(dāng)然，舉個(gè)最簡(jiǎn)單的例子。我發(fā)現(xiàn)桌子上開始就有一堆紅球和藍(lán)球，如果這這些球沒有過分的混合在一起，不用移動(dòng)這些球，你可以拿一根棍子把它們分離開。

你看，當(dāng)在桌上加一個(gè)新球時(shí)，通過已經(jīng)知道的棍字的哪一邊是哪個(gè)顏色的球，你就可以預(yù)測(cè)這個(gè)新球的顏色了。

最酷的部分是什么呢？SVM 算法可以算出這個(gè)超平面的方程。

如果事情變得更復(fù)雜該怎么辦？當(dāng)然了，事情通常都很復(fù)雜。如果球是混合在一起的，一根直棍就不能解決問題了。

下面是解決方案：

快速提起桌子，把所有的球拋向空中，當(dāng)所有的球以正確的方式拋在空中是，你使用一張很大的紙?jiān)诳罩蟹珠_這些球。

你可能會(huì)想這是不是犯規(guī)了。不，提起桌子就等同于把你的數(shù)據(jù)映射到了高維空間中。這個(gè)例子中，我們從桌子表面的二維空間過度到了球在空中的三維空間。

那么 SVM該怎么做呢？通過使用核函數(shù)（kernel），我們?cè)诟呔S空間也有很棒的操作方法。這張大紙依然叫做超平面，但是現(xiàn)在它對(duì)應(yīng)的方程是描述一個(gè)平面而不是一條線了。根據(jù) Yuval 的說法，一旦我們?cè)谌S空間處理問題，超平面肯定是一個(gè)面而不是線了。

關(guān)于 SVM的解釋思路，Reddit 的 ELI5 和 ML 兩個(gè)子版塊上也有兩個(gè)很棒的討論帖。

那么在桌上或者空中的球怎么用現(xiàn)實(shí)的數(shù)據(jù)解釋呢？桌上的每個(gè)球都有自己的位置，我們可以用坐標(biāo)來表示。打個(gè)比方，一個(gè)球可能是距離桌子左邊緣20cm 距離底部邊緣 50 cm，另一種描述這個(gè)球的方式是使用坐標(biāo)(x,y)或者(20,50)表達(dá)。x和 y 是代表球的兩個(gè)維度。

可以這樣理解：如果我們有個(gè)病人的數(shù)據(jù)集，每個(gè)病人可以用很多指標(biāo)來描述，比如脈搏，膽固醇水平，血壓等。每個(gè)指標(biāo)都代表一個(gè)維度。

基本上，SVM 把數(shù)據(jù)映射到一個(gè)更高維的空間然后找到一個(gè)能分類的超平面。

類間間隔(margin)經(jīng)常會(huì)和 SVM 聯(lián)系起來，類間間隔是什么呢？它是超平面和各自類中離超平面最近的數(shù)據(jù)點(diǎn)間的距離。在球和桌面的例子中，棍子和最近的紅球和藍(lán)球間的距離就是類間間隔(margin)。

SVM 的關(guān)鍵在于，它試圖最大化這個(gè)類間間隔，使分類的超平面遠(yuǎn)離紅球和藍(lán)球。這樣就能降低誤分類的可能性。

那么支持向量機(jī)的名字是哪里來的？還是球和桌子的例子中，超平面到紅球和藍(lán)球的距離是相等的。這些球或者說數(shù)據(jù)點(diǎn)叫做支持向量，因?yàn)樗鼈兌际侵С诌@個(gè)超平面的。

那這是監(jiān)督算法還是非監(jiān)督的呢？SVM 屬于監(jiān)督學(xué)習(xí)。因?yàn)殚_始需要使用一個(gè)數(shù)據(jù)集讓 SVM學(xué)習(xí)這些數(shù)據(jù)中的類型。只有這樣之后 SVM 才有能力對(duì)新數(shù)據(jù)進(jìn)行分類。

為什么我們要用 SVM 呢？ SVM 和 C4.5大體上都是優(yōu)先嘗試的二類分類器。根據(jù)“沒有免費(fèi)午餐原理”，沒有哪一種分類器在所有情況下都是最好的。此外，核函數(shù)的選擇和可解釋性是算法的弱點(diǎn)所在。

在哪里使用 SVM？有什么 SVM 的實(shí)現(xiàn)方法，比較流行的是用scikit-learn, MATLAB 和 libsvm實(shí)現(xiàn)的這幾種。

下面要介紹的算法是我最喜歡的算法之一：

4. Apriori 關(guān)聯(lián)算法

它是做什么的？Apriori算法學(xué)習(xí)數(shù)據(jù)的關(guān)聯(lián)規(guī)則(association rules)，適用于包含大量事務(wù)（transcation）的數(shù)據(jù)庫。

什么是關(guān)聯(lián)規(guī)則？關(guān)聯(lián)規(guī)則學(xué)習(xí)是學(xué)習(xí)數(shù)據(jù)庫中不同變量中的相互關(guān)系的一種數(shù)據(jù)挖掘技術(shù)。

舉個(gè) Apriori 算法的例子：我們假設(shè)有一個(gè)充滿超市交易數(shù)據(jù)的數(shù)據(jù)庫，你可以把數(shù)據(jù)庫想象成一個(gè)巨大的電子數(shù)據(jù)表，表里每一行是一個(gè)顧客的交易情況，每一列代表不用的貨物項(xiàng)。

精彩的部分來了：通過使用 Apriori 算法，我們就知道了同時(shí)被購買的貨物項(xiàng)，這也叫做關(guān)聯(lián)規(guī)則。它的強(qiáng)大之處在于，你能發(fā)現(xiàn)相比較其他貨物來說，有一些貨物更頻繁的被同時(shí)購買—終極目的是讓購物者買更多的東西。這些常被一起購買的貨物項(xiàng)被稱為項(xiàng)集（itemset）。

舉個(gè)例子，你大概能很快看到“薯?xiàng)l+蘸醬”和“薯?xiàng)l+蘇打水”的組合頻繁的一起出現(xiàn)。這些組合被稱為2-itemsets。在一個(gè)足夠大的數(shù)據(jù)集中，就會(huì)很難“看到”這些關(guān)系了，尤其當(dāng)還要處理3-itemset 或者更多項(xiàng)集的時(shí)候。這正是 Apriori 可以幫忙的地方！

你可能會(huì)對(duì) Apriori 算法如何工作有疑問，在進(jìn)入算法本質(zhì)和細(xì)節(jié)之前，得先明確3件事情：

第一是你的項(xiàng)集的大小，你想看到的模式是2-itemset或3-itemset 還是其他的？

第二是你支持的項(xiàng)集，或者是從事務(wù)的總數(shù)劃分出的事務(wù)包含的項(xiàng)集。一個(gè)滿足支持度的項(xiàng)集叫做頻繁項(xiàng)集。

第三是根據(jù)你已經(jīng)統(tǒng)計(jì)的項(xiàng)集中某些數(shù)據(jù)項(xiàng)，計(jì)算其他某個(gè)數(shù)據(jù)項(xiàng)出現(xiàn)的信心水準(zhǔn)或是條件概率。例如項(xiàng)集中出現(xiàn)的薯片的話，有67%的信心水準(zhǔn)這個(gè)項(xiàng)集中也會(huì)出現(xiàn)蘇打水。

基本的 Apriori 算法有三步：

參與，掃描一遍整個(gè)數(shù)據(jù)庫，計(jì)算1-itemsets 出現(xiàn)的頻率。

剪枝，滿足支持度和可信度的這些1-itemsets移動(dòng)到下一輪流程，再尋找出現(xiàn)的2-itemsets。

重復(fù)，對(duì)于每種水平的項(xiàng)集 一直重復(fù)計(jì)算，知道我們之前定義的項(xiàng)集大小為止。

這個(gè)算法是監(jiān)督的還是非監(jiān)督的？Apriori 一般被認(rèn)為是一種非監(jiān)督的學(xué)習(xí)方法，因?yàn)樗?jīng)常用來挖掘和發(fā)現(xiàn)有趣的模式和關(guān)系。

但是，等下，還有呢…對(duì)Apriori 算法改造一下也能對(duì)已經(jīng)標(biāo)記好的數(shù)據(jù)進(jìn)行分類。

為什么使用Apriori 算法？它易于理解，應(yīng)用簡(jiǎn)單，還有很多的派生算法。

但另一方面…

當(dāng)生成項(xiàng)集的時(shí)候，算法是很耗費(fèi)內(nèi)存、空間和時(shí)間。

大量的 Apriori 算法的語言實(shí)現(xiàn)可供使用。比較流行的是 ARtool, Weka, and Orange。

下一個(gè)算法對(duì)我來說是最難的，一起來看下吧。

5.EM 最大期望算法

EM 算法是做什么的？在數(shù)據(jù)挖掘領(lǐng)域，最大期望算法（Expectation-Maximization,EM） 一般作為聚類算法（類似 kmeans 算法）用來知識(shí)挖掘。

在統(tǒng)計(jì)學(xué)上，當(dāng)估算帶有無法觀測(cè)隱藏變量的統(tǒng)計(jì)模型參數(shù)時(shí),EM 算法不斷迭代和優(yōu)化可以觀測(cè)數(shù)據(jù)的似然估計(jì)值。

好，稍等讓我解釋一下…

我不是一個(gè)統(tǒng)計(jì)學(xué)家，所以希望我的簡(jiǎn)潔表達(dá)能正確并能幫助理解。

下面是一些概念，能幫我們更好的理解問題。

什么事統(tǒng)計(jì)模型？我把模型看做是描述觀測(cè)數(shù)據(jù)是如何生成的。例如，一場(chǎng)考試的分?jǐn)?shù)可能符合一種鐘形曲線，因此這種分?jǐn)?shù)分布符合鐘形曲線（也稱正態(tài)分布）的假設(shè)就是模型。

等下，那什么是分布？分布代表了對(duì)所有可測(cè)量結(jié)果的可能性。例如，一場(chǎng)考試的分?jǐn)?shù)可能符合一個(gè)正態(tài)分布。這個(gè)正態(tài)分布代表了分?jǐn)?shù)的所有可能性。換句話說，給定一個(gè)分?jǐn)?shù)，你可以用這個(gè)分布來預(yù)計(jì)多少考試參與者可能會(huì)得到這個(gè)分?jǐn)?shù)。

這很不錯(cuò)，那模型的參數(shù)又是什么呢？作為模型的一部分，分布屬性正是由參數(shù)來描述的。例如，一個(gè)鐘形曲線可以用它的均值和方差來描述。

還是使用考試的例子，一場(chǎng)考試的分?jǐn)?shù)分布（可測(cè)量的結(jié)果）符合一個(gè)鐘形曲線（就是分布）。均值是85，方差是100.

那么，你描述正態(tài)分布需要的所有東西就是這兩個(gè)參數(shù)：

平均值

方差

那么，似然性呢？回到我們之前的鐘形曲線例子，假設(shè)我們已經(jīng)拿到很多的分?jǐn)?shù)數(shù)據(jù)，并被告知分?jǐn)?shù)符合一個(gè)鐘形曲線。然而，我們并沒有給到所有的分?jǐn)?shù)，只是拿到了一個(gè)樣本。

可以這樣做：

我們不知道所有分?jǐn)?shù)的平均值或者方差，但是我們可以使用樣本計(jì)算它們。似然性就是用估計(jì)的方差和平均值得到的鐘形曲線在算出很多分?jǐn)?shù)的概率。

換句話說，給定一系列可測(cè)定的結(jié)果，讓我們來估算參數(shù)。再使用這些估算出的參數(shù)，得到結(jié)果的這個(gè)假設(shè)概率就被稱為似然性。

記住，這是已存在分?jǐn)?shù)的假設(shè)概率，并不是未來分?jǐn)?shù)的概率。

你可能會(huì)疑問，那概率又是什么？

還用鐘形曲線的例子解釋，假設(shè)我們知道均值和方差。然我們被告知分?jǐn)?shù)符合鐘形曲線。我們觀察到的某些分?jǐn)?shù)的可能性和他們多久一次的被觀測(cè)到就是概率。

更通俗的講，給定參數(shù)，讓我們來計(jì)算可以觀察到什么結(jié)果。這就是概率為我們做的事情。

很好，現(xiàn)在，觀測(cè)到的數(shù)據(jù)和未觀測(cè)到的隱藏?cái)?shù)據(jù)區(qū)別在哪里？觀測(cè)到的數(shù)據(jù)就是你看到或者記錄的數(shù)據(jù)。未觀測(cè)的數(shù)據(jù)就是遺失的數(shù)據(jù)。數(shù)據(jù)丟失的原因有很多（沒有記錄，被忽視了，等等原因）。

算法的優(yōu)勢(shì)是：對(duì)于數(shù)據(jù)挖掘和聚類，觀察到遺失的數(shù)據(jù)的這類數(shù)據(jù)點(diǎn)對(duì)我們來說很重要。我們不知道具體的類，因此這樣處理丟失數(shù)據(jù)對(duì)使用 EM 算法做聚類的任務(wù)來說是很關(guān)鍵的。

再說一次，當(dāng)估算帶有無法觀測(cè)隱藏變量的統(tǒng)計(jì)模型參數(shù)時(shí),EM 算法不斷迭代和優(yōu)化可以觀測(cè)數(shù)據(jù)的似然估計(jì)值。 希望現(xiàn)在再說更容易理解了。

算法的精髓在于：

通過優(yōu)化似然性，EM 生成了一個(gè)很棒的模型，這個(gè)模型可以對(duì)數(shù)據(jù)點(diǎn)指定類型標(biāo)簽—聽起來像是聚類算法！

EM 算法是怎么幫助實(shí)現(xiàn)聚類的呢？EM 算法以對(duì)模型參數(shù)的猜測(cè)開始。然后接下來它會(huì)進(jìn)行一個(gè)循環(huán)的3步：

E 過程：基于模型參數(shù)，它會(huì)針對(duì)每個(gè)數(shù)據(jù)點(diǎn)計(jì)算對(duì)聚類的分配概率。

M 過程：基于 E 過程的聚類分配，更新模型參數(shù)。

重復(fù)知道模型參數(shù)和聚類分配工作穩(wěn)定（也可以稱為收斂）。

EM 是監(jiān)督算法還是非監(jiān)督算法呢？因?yàn)槲覀儾惶峁┮呀?jīng)標(biāo)好的分類信息，這是個(gè)非監(jiān)督學(xué)習(xí)算法。

為什么使用它？EM 算法的一個(gè)關(guān)鍵賣點(diǎn)就是它的實(shí)現(xiàn)簡(jiǎn)單直接。另外，它不但可以優(yōu)化模型參數(shù)，還可以反復(fù)的對(duì)丟失數(shù)據(jù)進(jìn)行猜測(cè)。

這使算法在聚類和產(chǎn)生帶參數(shù)的模型上都表現(xiàn)出色。在得知聚類情況和模型參數(shù)的情況下，我們有可能解釋清楚有相同屬性的分類情況和新數(shù)據(jù)屬于哪個(gè)類之中。

不過EM 算法也不是沒有弱點(diǎn)…

第一，EM 算法在早期迭代中都運(yùn)行速度很快，但是越后面的迭代速度越慢。

第二，EM 算法并不能總是尋到最優(yōu)參數(shù)，很容易陷入局部最優(yōu)而不是找到全局最優(yōu)解。

EM 算法實(shí)現(xiàn)可以在 Weka中找到，mclust package里面有 R 語言對(duì)算法的實(shí)現(xiàn)，scikit-learn的gmm module里也有對(duì)它的實(shí)現(xiàn)。

6.PageRank算法

算法是做什么的？PageRank是為了決定一些對(duì)象和同網(wǎng)絡(luò)中的其他對(duì)象之間的相對(duì)重要程度而設(shè)計(jì)的連接分析算法(link analysis algorithm)。

那么什么是連接分析算法呢？它是一類針對(duì)網(wǎng)絡(luò)的分析算法，探尋對(duì)象間的關(guān)系（也可成為連接）。

舉個(gè)例子：最流行的 PageRank 算法是 Google 的搜索引擎。盡管他們的搜索引擎不止是依靠它，但 PageRank依然是 Google 用來測(cè)算網(wǎng)頁重要度的手段之一。

解釋一下：

萬維網(wǎng)上的網(wǎng)頁都是互相鏈接的。如果 Rayli.net 鏈接到了 CNN 上的一個(gè)網(wǎng)頁，CNN 網(wǎng)頁就增加一個(gè)投票，表示 rayli.net 和 CNN 網(wǎng)頁是關(guān)聯(lián)的。

這還沒有結(jié)束：

反過來，來自rayli.net 網(wǎng)頁的投票重要性也要根據(jù) rayli.net 網(wǎng)的重要性和關(guān)聯(lián)性來權(quán)衡。換句話說，任何給 rayli.net 投票的網(wǎng)頁也能提升 rayli.net 網(wǎng)頁的關(guān)聯(lián)性。

基本概括一下：

投票和關(guān)聯(lián)性就是 PageRank 的概念。rayli.net 給CNN 投票增加了 CNN 的 Pagerank，rayli.net 的 PageRank級(jí)別同時(shí)也影響著它為 CNN 投票多大程度影響了CNN 的 PageRank。

那么 PageRank 的0，1，2，3級(jí)別是什么意思？ 盡管 Google 并沒有揭露PageRank 的精確含義，我們還是能了解它的大概意思。

我們能通過下面這些網(wǎng)站的PageRank得到些答案：

看到了么？

這排名有點(diǎn)像一個(gè)網(wǎng)頁流行度的競(jìng)爭(zhēng)。我們的頭腦中都有了一些這些網(wǎng)站的流行度和關(guān)聯(lián)度的信息。

PageRank只是一個(gè)特別講究的方式來定義了這些而已。

PageRank還有什么其他應(yīng)用呢？ PageRank是專門為了萬維網(wǎng)設(shè)計(jì)的。

可以考慮一下，以核心功能的角度看，PageRank算法真的只是一個(gè)處理鏈接分析極度有效率的方法。處理的被鏈接的對(duì)象不止只是針對(duì)網(wǎng)頁。

下面是 PageRank3個(gè)創(chuàng)新的應(yīng)用：

1. 芝加哥大學(xué)的Dr Stefano Allesina，將 PageRank應(yīng)用到了生態(tài)學(xué)中，測(cè)定哪個(gè)物種對(duì)可持續(xù)的生態(tài)系統(tǒng)至關(guān)重要。

2. Twitter 研究出了一種叫 WTF（Who-to-Follow）算法，這是一種個(gè)性化的 PageRank推薦關(guān)注人的引擎。

3. 香港理工大學(xué)的 Bin Jiang 使用一種變形的PageRank來預(yù)測(cè)基于倫敦地形指標(biāo)的行人移動(dòng)速率。

這算法是監(jiān)督的還是非監(jiān)督的？PageRank常用來發(fā)現(xiàn)一個(gè)網(wǎng)頁的重要度關(guān)聯(lián)度，通常被認(rèn)為是一種非監(jiān)督學(xué)習(xí)算法。

為什么使用PageRank？可以說，PageRank的主要賣點(diǎn)是：由于得到新相關(guān)鏈接具有難度，算法依然具有良好的魯棒性。

更簡(jiǎn)單一點(diǎn)說，如果你又一個(gè)圖或者網(wǎng)絡(luò)，并想理解其中元素的相對(duì)重要性，優(yōu)先性，排名或者相關(guān)性，可以用PageRank試一試。

哪里使用過它呢？Google 擁有PageRank 的商標(biāo)。但是斯坦福大學(xué)取得了PageRank 算法的專利權(quán)。如果使用 PageRank，你可能會(huì)有疑問： 我不是律師，所以最好和一個(gè)真正的律師確認(rèn)一下。但是只要和 Google 或斯坦福沒有涉及到商業(yè)競(jìng)爭(zhēng)，應(yīng)該都是可以使用這個(gè)算法的。

給出PageRank 的三個(gè)實(shí)現(xiàn)：

1 C++ OpenSource PageRank Implementation

2 Python PageRank Implementation

3 igraph – The network analysis package (R)

7.AdaBoost 迭代算法

AdaBoost 算法是做什么的？AdaBoost 是個(gè)構(gòu)建分類器的提升算法。

也許你還記得，分類器拿走大量數(shù)據(jù)，并試圖預(yù)測(cè)或者分類新數(shù)據(jù)元素的屬于的類別。

但是，提升(boost) 指的什么？提升是個(gè)處理多個(gè)學(xué)習(xí)算法（比如決策樹）并將他們合并聯(lián)合起來的綜合的學(xué)習(xí)算法。目的是將弱學(xué)習(xí)算法綜合或形成一個(gè)組，把他們聯(lián)合起來創(chuàng)造一個(gè)新的強(qiáng)學(xué)習(xí)器。

強(qiáng)弱學(xué)習(xí)器之間有什么區(qū)別呢？弱學(xué)習(xí)分類器的準(zhǔn)確性僅僅比猜測(cè)高一點(diǎn)。一個(gè)比較流行的弱分類器的例子就是只有一層的決策樹。

另一個(gè)，強(qiáng)學(xué)習(xí)分類器有更高的準(zhǔn)確率，一個(gè)通用的強(qiáng)學(xué)習(xí)器的例子就是 SVM。

舉個(gè) AdaBoost 算法的例子：我們開始有3個(gè)弱學(xué)習(xí)器，我們將在一個(gè)包含病人數(shù)據(jù)的數(shù)據(jù)訓(xùn)練集上對(duì)他們做10輪訓(xùn)練。數(shù)據(jù)集里包含了病人的醫(yī)療記錄各個(gè)細(xì)節(jié)。

問題來了，那我們?cè)趺搭A(yù)測(cè)某個(gè)病人是否會(huì)得癌癥呢？AdaBoost 是這樣給出答案的：

第一輪，AdaBoost 拿走一些訓(xùn)練數(shù)據(jù)，然后測(cè)試每個(gè)學(xué)習(xí)器的準(zhǔn)確率。最后的結(jié)果就是我們找到最好的那個(gè)學(xué)習(xí)器。另外，誤分類的樣本學(xué)習(xí)器給予一個(gè)比較高的權(quán)重，這樣他們?cè)谙螺喚陀泻芨叩母怕时贿x中了。

再補(bǔ)充一下，最好的那個(gè)學(xué)習(xí)器也要給根據(jù)它的準(zhǔn)確率賦予一個(gè)權(quán)重，并將它加入到聯(lián)合學(xué)習(xí)器中（這樣現(xiàn)在就只有一個(gè)分類器了）

第二輪， AdaBoost 再次試圖尋找最好的學(xué)習(xí)器。

關(guān)鍵部分來了，病人數(shù)據(jù)樣本的訓(xùn)練數(shù)據(jù)現(xiàn)在被有很高誤分配率的權(quán)重影響著。換句話說，之前誤分類的病人在這個(gè)樣本里有很高的出現(xiàn)概率。

為什么？

這就像是在電子游戲中已經(jīng)打到了第二級(jí)，但當(dāng)你的角色死亡后卻不必從頭開始。而是你從第二級(jí)開始然后集中注意，盡力升到第三級(jí)。

同樣地，第一個(gè)學(xué)習(xí)者有可能對(duì)一些病人的分類是正確的，與其再度試圖對(duì)他們分類，不如集中注意盡力處理被誤分類的病人。

最好的學(xué)習(xí)器也被再次賦予權(quán)重并加入到聯(lián)合分類器中，誤分類的病人也被賦予權(quán)重，這樣他們就有比較大的可能性再次被選中，我們會(huì)進(jìn)行過濾和重復(fù)。

在10輪結(jié)束的時(shí)候，我們剩下了一個(gè)帶著不同權(quán)重的已經(jīng)訓(xùn)練過的聯(lián)合學(xué)習(xí)分類器，之后重復(fù)訓(xùn)練之前回合中被誤分類的數(shù)據(jù)。

這是個(gè)監(jiān)督還是非監(jiān)督算法？因?yàn)槊恳惠営?xùn)練帶有已經(jīng)標(biāo)記好數(shù)據(jù)集的弱訓(xùn)練器，因此這是個(gè)監(jiān)督學(xué)習(xí)。

為什么使用 AdaBoost？AdaBoost算法簡(jiǎn)單， 編程相對(duì)來說簡(jiǎn)潔直白。

另外，它速度快！弱學(xué)習(xí)器 一般都比強(qiáng)學(xué)習(xí)器簡(jiǎn)單，簡(jiǎn)單意味著它們的運(yùn)行速度可能更快。

還有件事：

因?yàn)槊枯嗊B續(xù)的Adaboost回合都重新定義了每個(gè)最好學(xué)習(xí)器的權(quán)重，因此這是個(gè)自動(dòng)調(diào)整學(xué)習(xí)分類器的非常簡(jiǎn)潔的算法，你所要做的所有事就是指定運(yùn)行的回合數(shù)。

最后，算法靈活通用，AdaBoost 可以加入任何學(xué)習(xí)算法，并且它能處理多種數(shù)據(jù)。

AdaBoost 有很多程序?qū)崿F(xiàn)和變體。給出一些：

 scikit-learn

 ICSIBoost

 gbm: Generalized Boosted Regression Models

如果你喜歡Mr.Rogers,你會(huì)喜歡下面的算法的…

8.kNN：k最近鄰算法

它是做什么的？kNN，或 K 最近鄰(k-Nearest Neighbors), 詩歌分類算法。然而，它和我們之前描述的分類器不同，因?yàn)樗莻€(gè)懶散學(xué)習(xí)法。

什么是懶散學(xué)習(xí)法呢？和存儲(chǔ)訓(xùn)練數(shù)據(jù)的算法不同，懶散學(xué)習(xí)法在訓(xùn)練過程中不需要做許多處理。只有當(dāng)新的未被分類的數(shù)據(jù)輸入時(shí)，這類算法才會(huì)去做分類。

但在另一方面，積極學(xué)習(xí)法則會(huì)在訓(xùn)練中建立一個(gè)分類模型，當(dāng)新的未分類數(shù)據(jù)輸入時(shí)，這類學(xué)習(xí)器會(huì)把新數(shù)據(jù)也提供給這個(gè)分類模型。

那么 C4.5，SVM 和 AdaBoost 屬于哪類呢？不像 kNN算法，他們都是積極學(xué)習(xí)算法。

給出原因：

1 C4.5 在訓(xùn)練中建立了一個(gè)決策分類樹模型。

2 SVM在訓(xùn)練中建立了一個(gè)超平面的分類模型。

3 AdaBoost在訓(xùn)練中建立了一個(gè)聯(lián)合的分類模型。

那么 kNN 做了什么？ kNN 沒有建立這樣的分類模型，相反，它只是儲(chǔ)存了一些分類好的訓(xùn)練數(shù)據(jù)。那么新的訓(xùn)練數(shù)據(jù)進(jìn)入時(shí)，kNN 執(zhí)行兩個(gè)基本步驟：

1 首先，它觀察最近的已經(jīng)分類的訓(xùn)練數(shù)據(jù)點(diǎn)—也就是，k最臨近點(diǎn)（k-nearest neighbors）

2 第二部，kNN使用新數(shù)據(jù)最近的鄰近點(diǎn)的分類， 就對(duì)新數(shù)據(jù)分類得到了更好的結(jié)果了。

你可能會(huì)懷疑…kNN 是怎么計(jì)算出最近的是什么？ 對(duì)于連續(xù)數(shù)據(jù)來說，kNN 使用一個(gè)像歐氏距離的距離測(cè)度，距離測(cè)度的選擇大多取決于數(shù)據(jù)類型。有的甚至?xí)鶕?jù)訓(xùn)練數(shù)據(jù)學(xué)習(xí)出一種距離測(cè)度。關(guān)于 kNN 距離測(cè)度有更多的細(xì)節(jié)討論和論文描述。

對(duì)于離散數(shù)據(jù)，解決方法是可以把離散數(shù)據(jù)轉(zhuǎn)化為連續(xù)數(shù)據(jù)。給出兩個(gè)例子：

1 使用漢明距離（Hamming distance ）作為兩個(gè)字符串緊密程度的測(cè)度。

2 把離散數(shù)據(jù)轉(zhuǎn)化為二進(jìn)制表征。

這兩個(gè)來自Stack Overflow的思路也有一些關(guān)于處理離散數(shù)據(jù)的建議：

 KNN classification with categorical data

 Using k-NN in R with categorical values

當(dāng)臨近的點(diǎn)是不同的類，kNN 怎么給新數(shù)據(jù)分類呢？當(dāng)臨近點(diǎn)都是同一類的時(shí)候，kNN 也就不費(fèi)力氣了。我們用直覺考慮，如果附近點(diǎn)都一致，那么新數(shù)據(jù)點(diǎn)就很可能落入這同一個(gè)類中了。

我打賭你能猜到事情是從哪里開始變的麻煩的了…

當(dāng)臨近點(diǎn)不是同一類時(shí)，kNN 怎么決定分類情況的呢？

處理這種情況通常有兩種辦法：

1 通過這些臨近點(diǎn)做個(gè)簡(jiǎn)單的多數(shù)投票法。哪個(gè)類有更多的票，新數(shù)據(jù)就屬于那個(gè)類。

2 還是做個(gè)類似的投票，但是不同的是，要給那些離的更近的臨近點(diǎn)更多的投票權(quán)重。這樣做的一個(gè)簡(jiǎn)單方法是使用反距離(reciprocal distance). 比如，如果某個(gè)臨近點(diǎn)距離5個(gè)單位，那么它的投票權(quán)重就是1/5.當(dāng)臨近點(diǎn)越來越遠(yuǎn)是，倒數(shù)距離就越來越小…這正是我們想要的。

這是個(gè)監(jiān)督算法還是非監(jiān)督的呢？因?yàn)?kNN 算法提供了已經(jīng)被分類好的數(shù)據(jù)集，所以它是個(gè)監(jiān)督學(xué)習(xí)算法。

為什么我們會(huì)用 kNN？便于理解和實(shí)現(xiàn)是我們使用它的兩個(gè)關(guān)鍵原因。根據(jù)距離測(cè)度的方法，kNN 可能會(huì)非常精確。

但是這還只是故事的一部分，下面是我們需要注意的5點(diǎn)：

1、 當(dāng)試圖在一個(gè)大數(shù)據(jù)集上計(jì)算最臨近點(diǎn)時(shí)，kNN 算法可能會(huì)耗費(fèi)高昂的計(jì)算成本。

2、 噪聲數(shù)據(jù)(Noisy data)可能會(huì)影響到 kNN 的分類。

3、 選擇大范圍的屬性篩選(feature)會(huì)比小范圍的篩選占有很多優(yōu)勢(shì)，所以屬性篩選(feature)的規(guī)模非常重要。

4、 由于數(shù)據(jù)處理會(huì)出現(xiàn)延遲，kNN 相比積極分類器，一般需要更強(qiáng)大的存儲(chǔ)需求。

5、 選擇一個(gè)合適的距離測(cè)度對(duì) kNN 的準(zhǔn)確性來說至關(guān)重要。

哪里用過這個(gè)方法？有很多現(xiàn)存的 kNN 實(shí)現(xiàn)手段：

 MATLAB k-nearest neighbor classification

scikit-learn KNeighborsClassifier

k-Nearest Neighbour Classification in R