編者按：2016年知名數(shù)據(jù)科學(xué)專業(yè)平臺(tái)KDnuggets在網(wǎng)站上列出了10大開發(fā)者必備的機(jī)器學(xué)習(xí)算法排名，受到眾多讀者歡迎。近期，作者Reena Shaw又結(jié)合當(dāng)前發(fā)展重寫原文，再一次吸引了大量數(shù)據(jù)科學(xué)家的目光。文章中包含算法簡(jiǎn)析和數(shù)字、實(shí)例展示，十分適合ML初學(xué)者閱讀。為了方便國(guó)內(nèi)讀者，論智現(xiàn)將原文編譯如下：

一、導(dǎo)語(yǔ)

“數(shù)據(jù)科學(xué)家”是“21世紀(jì)最性感的工作。”不久前，“哈佛商業(yè)評(píng)論”在一篇報(bào)道中是這樣描述的。隨著機(jī)器學(xué)習(xí)（ML）算法研究工作的不斷推進(jìn)，數(shù)據(jù)科學(xué)家也正變得更具吸引力。那么對(duì)于那些剛開始學(xué)習(xí)ML的入門者來(lái)說(shuō)，哪些是他們必備的實(shí)用算法呢？為了方便這個(gè)群體，我們重寫了“10大開發(fā)者必備的機(jī)器學(xué)習(xí)算法”，并根據(jù)受眾理解水平對(duì)內(nèi)容進(jìn)行了調(diào)整。

ML算法是指那些無(wú)需人工干預(yù)，僅憑數(shù)據(jù)和經(jīng)驗(yàn)就能不斷學(xué)習(xí)、改進(jìn)的算法，它們的學(xué)習(xí)任務(wù)可能包括利用函數(shù)將輸入映射到輸出、在未經(jīng)標(biāo)記的數(shù)據(jù)中學(xué)習(xí)隱藏結(jié)構(gòu)；或者是“基于實(shí)例學(xué)習(xí)”，通過(guò)新實(shí)例訓(xùn)練結(jié)合儲(chǔ)存在存儲(chǔ)器中的訓(xùn)練數(shù)據(jù)對(duì)比生成類標(biāo)簽。

二、ML算法類型

ML算法的類型可分為監(jiān)督學(xué)習(xí)、無(wú)監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)三種。

1.監(jiān)督學(xué)習(xí)

我們可以把監(jiān)督學(xué)習(xí)簡(jiǎn)單解釋為使用經(jīng)標(biāo)記的訓(xùn)練數(shù)據(jù)來(lái)學(xué)習(xí)映射函數(shù)：將輸入變量（X）映射到輸出變量（Y）：

Y = f (X).

監(jiān)督學(xué)習(xí)問(wèn)題主要有兩類：

• 分類（Classification）：根據(jù)給定樣本預(yù)測(cè)輸出變量所屬的類別形式，如男性/女性、疾病/健康等。

• 回歸（Regression）：根據(jù)給定樣本預(yù)測(cè)輸出變量的實(shí)值，如降雨量、身高等。

本文介紹的前5種算法——線性回歸、logistic回歸、CART、樸素貝葉斯和KNN——都是監(jiān)督學(xué)習(xí)下的典型算法。

事實(shí)上，集成學(xué)習(xí)也可以算作監(jiān)督學(xué)習(xí)算法的一類。

集成學(xué)習(xí)即通過(guò)多個(gè)分類器對(duì)數(shù)據(jù)集進(jìn)行預(yù)測(cè)，從而提高整體分類器的泛化能力。當(dāng)面對(duì)一個(gè)任務(wù)時(shí)，算法會(huì)訓(xùn)練一些弱分類器，之后把它們組合起來(lái)，以獲得更好的預(yù)測(cè)性能。它的思路是集體平均決策的表現(xiàn)會(huì)被單個(gè)分類器效果好，一般有Boosting、Bagging、Stacking三種方式。

2.無(wú)監(jiān)督學(xué)習(xí)

無(wú)監(jiān)督學(xué)習(xí)問(wèn)題只有輸入變變量（X），而沒(méi)有輸出變量（Y），它使用沒(méi)有標(biāo)簽的訓(xùn)練數(shù)據(jù)來(lái)模擬數(shù)據(jù)的基本結(jié)構(gòu)。

無(wú)監(jiān)督學(xué)習(xí)問(wèn)題也可被分為以下幾類：

• 關(guān)聯(lián)（Association）：發(fā)現(xiàn)樣本集中數(shù)據(jù)共現(xiàn)的概率。這在“市場(chǎng)籃子分析”（market-basket analysis）中有很廣泛的應(yīng)用，比如當(dāng)一個(gè)顧客買了面包后，他會(huì)有80%的概率再買雞蛋；

• 聚類（Clustering）：即對(duì)樣本進(jìn)行分類，使同一類中的樣本更相似，彼此間的關(guān)系更緊密。

• 降維（Dimensionality Reduction）：正如它的名稱，降維意味著在確保重要信息傳遞的前提下減少數(shù)據(jù)集中的變量，它常用的方法是特征提?。▓?zhí)行從高維空間到低維空間的數(shù)據(jù)轉(zhuǎn)換）和特征選擇（選擇原始變量的一個(gè)子集）。PCA算法是一種特征提取方法。

本文中的Apriori、K-means和PCA都是無(wú)監(jiān)督學(xué)習(xí)的典型算法。

3.強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)是一種ML算法，它允許agent根據(jù)當(dāng)前狀態(tài)選擇下一步行動(dòng)（最佳），通過(guò)學(xué)習(xí)實(shí)現(xiàn)行為的獎(jiǎng)勵(lì)最大化。

強(qiáng)化學(xué)習(xí)算法通常利用反復(fù)試驗(yàn)來(lái)學(xué)習(xí)最佳行為，它在機(jī)器人上有很廣泛的應(yīng)用。如在訓(xùn)練機(jī)器人時(shí)，開發(fā)者可以設(shè)定“碰撞”行為將獲得負(fù)面獎(jiǎng)勵(lì)，那機(jī)器人會(huì)朝著規(guī)避障礙物的方向發(fā)展，這也是游戲AI常用的套路。

三、十大機(jī)器學(xué)習(xí)算法

1.線性回歸

在ML問(wèn)題中，如果我們有一組輸入變量（X），要用它們得出輸出變量（Y），而輸入變量和輸出變量之間存在某種聯(lián)系，那ML算法的作用就是量化這種聯(lián)系。

線性回歸示意圖

在線性回歸算法中，輸入變量（X）和輸出變量（Y）的關(guān)系可被表示為函數(shù)y=ax+b，因此我們的目標(biāo)是找出系數(shù)a和b的值。

如上圖所示，a為曲線在y軸上的截距，b是曲線的斜率，而這些點(diǎn)就是數(shù)據(jù)集中各個(gè)值，我們需要訓(xùn)練模型使它們盡可能地接近曲線，縮小數(shù)據(jù)點(diǎn)和y值的距離（誤差）。

2.logistic回歸

logistic回歸和線性回歸有很多相似之處，但也有不小的區(qū)別，其中最突出的一點(diǎn)是：線性回歸預(yù)測(cè)的值的連續(xù)的，而logistic回歸預(yù)測(cè)的值需要經(jīng)過(guò)其他函數(shù)變換，是不連續(xù)的。

logistic回歸適合二進(jìn)制分類（y=0或1的數(shù)據(jù)集，其中1表示默認(rèn)類），如當(dāng)預(yù)測(cè)某一件事是否發(fā)生時(shí)，發(fā)生的事件被表示為1，不發(fā)生則為0（例：判斷某人是否生病，那生病即是1）。它的名稱源于使用的變換函數(shù)，這是一個(gè)邏輯函數(shù)h(x)=1/(1+e^-x)，在圖中表示為一條S形曲線。

在logistic回歸算法中，輸出是以默認(rèn)類概率的形式出現(xiàn)的（不同于直接產(chǎn)生輸出的線性回歸）。因?yàn)檫@是一個(gè)概率，它的輸出在0—1之間，所以我們需要先對(duì)x做對(duì)數(shù)轉(zhuǎn)換，再由h(x)=1/(1+e^-x)生成輸出概率y，最后用一個(gè)閾值強(qiáng)制這個(gè)概率進(jìn)行二元分類。

logistic回歸示意圖

假設(shè)我們正在用logistic回歸預(yù)測(cè)腫瘤是否是惡性的，如果是惡性的，則y=1。如上圖所示，logistic回歸算法中的邏輯函數(shù)將數(shù)據(jù)集中樣本各個(gè)值的x轉(zhuǎn)換成范圍在0—1之間的數(shù)h(x)，如果概率大于0.5，那就是惡性腫瘤。

方程p(x) = e^(b0+b1×x)/(1+ e^(b0+b1×x))也可被表示為ln（p(x)/1-p(x) ）= b0+b1×x。

邏輯回歸的目標(biāo)是通過(guò)訓(xùn)練數(shù)據(jù)找到b0和b1的值，來(lái)縮小預(yù)測(cè)結(jié)果和實(shí)際結(jié)果的誤差。這些系數(shù)都是用最大似然估計(jì)得出的。

3.CART

分類和回歸樹（CART）是決策樹的一種，它由特征選擇、樹的生成和剪枝三部分組成。

其中，根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)是非終端節(jié)點(diǎn)，表示單個(gè)輸入變量（X）及其分裂，葉節(jié)點(diǎn)是終端節(jié)點(diǎn)，表示輸出變量（Y）。如果一個(gè)模型基于CART算法設(shè)計(jì)，那它的思路就是輸入值從整棵樹的根部進(jìn)入計(jì)算，經(jīng)分裂后它會(huì)最終到達(dá)一個(gè)葉節(jié)點(diǎn)，而這個(gè)存在于葉節(jié)點(diǎn)上的值就是輸出。

我們可以舉一個(gè)簡(jiǎn)單的例子：根據(jù)對(duì)象的年齡和婚姻情況判斷他是買跑車還是小型貨車。假設(shè)買跑車的是30歲以下人士和30歲以上未婚人士，而買小型火車的是30歲以上已婚人士，如下圖所示：

CART示意圖

如果這個(gè)人已經(jīng)三十多歲了，還沒(méi)有結(jié)婚，那算法的分類流程是“30多歲？——是——已婚？——否”，最后輸出“跑車”。

4.樸素貝葉斯

樸素貝葉斯是一種基于貝葉斯定理的算法，為了計(jì)算事件發(fā)生的概率，它假設(shè)已經(jīng)發(fā)生了另一個(gè)事件。

貝葉斯定理

其中：

• P(c|x)稱后驗(yàn)概率，是給定x后，c為真的概率。

• P(x|c)表示似然值，是給定c后，x為真的概率。

• P(c)是類別先驗(yàn)概率，計(jì)算的是c為真的概率（不考慮數(shù)據(jù)）。

• P(x)則是預(yù)測(cè)值的先驗(yàn)概率，表示x的可能性（與假設(shè)無(wú)關(guān)）。

這個(gè)算法被稱為是“naive”的，中文可譯為“天真”“樸素”，因?yàn)樗僭O(shè)所有變量都是相互獨(dú)立的，事實(shí)上，這在現(xiàn)實(shí)中幾乎不可能存在。

用樸素貝葉斯預(yù)測(cè)出去玩的概率

上圖是論智6步驟帶你了解樸素貝葉斯分類器（含Python和R語(yǔ)言代碼）中根據(jù)天氣條件進(jìn)行分類，判斷這個(gè)人能不能出去玩一個(gè)案例：

步驟1：將數(shù)據(jù)集轉(zhuǎn)換成頻率表；

步驟2：計(jì)算不同天氣出去玩的概率，并創(chuàng)建似然表，如陰天的概率是0.29；

步驟3：使用貝葉斯公式計(jì)算每一類的后驗(yàn)概率，數(shù)據(jù)最高那欄就是預(yù)測(cè)的結(jié)果。

問(wèn)題：如果是晴天，這個(gè)人就能出去玩。這個(gè)說(shuō)法是不是正確的？

P(是|晴朗)=P(晴朗|是)×P(是)/P(晴朗)

在這里，P(晴朗|是)= 3/9 = 0.33，P(晴朗)= 5/14 = 0.36，P(是)= 9/14 = 0.64

現(xiàn)在，P(是|晴朗)=0.33×0.64/0.36=0.60，具有較高的概率，所以輸出為“是”。

5.KNN

KNN算法即K Nearest Neighbor算法，它將整個(gè)數(shù)據(jù)集作為訓(xùn)練集，而不是將數(shù)據(jù)集劃分為測(cè)試集和訓(xùn)練集。

這是一種相對(duì)容易理解的算法，當(dāng)需要對(duì)一個(gè)新的數(shù)據(jù)樣本輸出結(jié)果時(shí)，KNN算法會(huì)從數(shù)據(jù)集中找出最接近輸入樣本的K個(gè)數(shù)據(jù)樣本，然后對(duì)它們的輸出做平均，這個(gè)平均值就是最終輸出的值。簡(jiǎn)單來(lái)說(shuō)，這種算法基于數(shù)據(jù)歸類處理，它的K值由開發(fā)者設(shè)定。

在判斷輸入樣本與數(shù)據(jù)樣本的相似度時(shí)，KNN算法依靠的是歐氏距離、漢明距離等機(jī)器學(xué)習(xí)常用距離公式。

6.Apriori

Apriori是一種針對(duì)頻繁項(xiàng)集的算法，能挖掘布爾關(guān)聯(lián)規(guī)則，正如上文中所提到的，它是一種非監(jiān)督學(xué)習(xí)算法，常被用于“市場(chǎng)籃子分析”。在這類分析中，Apriori會(huì)檢查數(shù)據(jù)庫(kù)中頻繁出現(xiàn)的產(chǎn)品組合。如果我們?cè)O(shè)一個(gè)人先購(gòu)買了商品X，又購(gòu)買了商品Y，那它們之間的關(guān)聯(lián)可被表示為X - > Y。

例如，如果一個(gè)人購(gòu)買了牛奶和糖，那么他很有可能會(huì)再買一些沖調(diào)咖啡，這時(shí)，他的行為可以被表示為一個(gè)關(guān)聯(lián)式：{牛奶，糖} - >沖調(diào)咖啡。這樣的關(guān)聯(lián)規(guī)則是建立在足夠的支持度和信任度基礎(chǔ)上的。

用Apriori進(jìn)行“市場(chǎng)籃子分析”

如上圖所示，Apriori可分為三個(gè)步驟：先是從數(shù)據(jù)集中搜索所有頻繁項(xiàng)集，開發(fā)者設(shè)定的支持度（support）作為頻繁項(xiàng)的閾值，可以在剪枝時(shí)篩去所有不符合要求的項(xiàng)目；其次是利用頻繁項(xiàng)集構(gòu)造出滿足用戶最小信任度（confidence）的規(guī)則；最后得出真正的頻繁項(xiàng)集。

在衡量支持度時(shí)，Apriori規(guī)定如果一個(gè)項(xiàng)集是頻繁的，那它的所有子集也必須是頻繁的。

7.K-means

K-means算法即K-均值聚類算法。它是一種迭代算法，當(dāng)接受輸入量k后，算法會(huì)將n個(gè)數(shù)據(jù)對(duì)象劃分為k個(gè)聚類，用以獲得相應(yīng)的聚類滿足：同一聚類中的對(duì)象相似度較高，而不同聚類中的對(duì)象相似度較小。簡(jiǎn)單來(lái)說(shuō)，就是K-means會(huì)計(jì)算數(shù)據(jù)點(diǎn)到聚類質(zhì)心的距離，距離越小，相似度越高，之后把距離相近的數(shù)據(jù)歸為一類。

下圖展示了K-means的聚類原理：

K-means示意圖

步驟1：K-means初始化；

• 設(shè)定k值，在上圖中，我們?nèi)=3；

• 將數(shù)據(jù)點(diǎn)隨機(jī)劃分成3個(gè)聚類；

• 為每個(gè)聚類計(jì)算質(zhì)心，用紅、黃、藍(lán)三顆星表示。

步驟2：將每個(gè)數(shù)據(jù)點(diǎn)與質(zhì)心關(guān)聯(lián)；

將每個(gè)數(shù)據(jù)點(diǎn)按照和質(zhì)心的距離重新分配到新的類別中，在上圖中，5個(gè)數(shù)據(jù)點(diǎn)和藍(lán)星歸為一類。

步驟3：重新計(jì)算質(zhì)心；

計(jì)算新聚類的質(zhì)心，紅、黃、藍(lán)表示新質(zhì)心，灰色星星則是原質(zhì)心。

步驟4：重復(fù)步驟2、步驟3進(jìn)行迭代，如果數(shù)據(jù)不再發(fā)生變化，算法結(jié)束。

8.PCA

PCA（主成分分析）是前文提到的非監(jiān)督學(xué)習(xí)算法中的降維類算法，它用盡可能少的變量去分析存在于這些變量中的信息，使數(shù)據(jù)更易于搜索和可視化。

PCA的思路是將一個(gè)高維向量x，通過(guò)一個(gè)特殊的特征向量矩陣U，投影到一個(gè)低維的向量空間中，表征為一個(gè)低維向量y，并且僅僅損失了一些次要信息。從計(jì)算角度說(shuō)，如果原數(shù)據(jù)是一個(gè)n維的樣本，我們需要利用均值建立一個(gè)k（k<>

簡(jiǎn)要來(lái)說(shuō)，就是通過(guò)計(jì)算最大方差獲得樣本在“principal components”這條軸上的新坐標(biāo)。每個(gè)成分（components）都和原樣本線性相關(guān)，切彼此正交。如果兩個(gè)成分出現(xiàn)了正交性，那就證明它們之間的相關(guān)性為0。

如上圖所示，PC1捕捉到了數(shù)據(jù)集中的最大變化方向，而PC2獲得了一些剩余變量，但這些變量與PC1不相關(guān)。

9.Bagging和隨機(jī)森林

Bagging和隨機(jī)森林都是對(duì)單棵決策樹效果的提升。

Bagging很難翻譯，雖然名字里帶了一個(gè)bag，但其實(shí)它和袋子完全沒(méi)有關(guān)系，而是Bootstrap aggregation的縮寫，因此可以簡(jiǎn)單理解為是一種抽樣方法。當(dāng)進(jìn)行Bagging時(shí)，它首先會(huì)從數(shù)據(jù)集中重復(fù)抽取大小為N的子樣本，這就導(dǎo)致有的數(shù)據(jù)會(huì)重復(fù)出現(xiàn)，而有的不會(huì)。之后，原始數(shù)據(jù)集會(huì)被作為測(cè)試集，而多個(gè)子樣本則為訓(xùn)練集。需要注意的是，原始數(shù)據(jù)集的大小是N，測(cè)試數(shù)據(jù)集的大小是N，訓(xùn)練集的大小也是N。

之后，Bagging會(huì)針對(duì)這些訓(xùn)練集建立分類器，根據(jù)之前的抽樣方法反復(fù)抽樣m次，得到m個(gè)分類器。當(dāng)做到這一步時(shí)，傳統(tǒng)的做法是把原始數(shù)據(jù)放進(jìn)這些分類器中，由它們?cè)u(píng)分輸出最終值。但我們可以引入一個(gè)進(jìn)化版本——隨機(jī)森林。

不同于單棵決策樹把每個(gè)節(jié)點(diǎn)都分割成最佳表征，隨機(jī)森林的一般做法是首先從樣本中隨機(jī)抽取n個(gè)樣本，然后結(jié)合隨機(jī)選擇的表征K，對(duì)它們進(jìn)行m次決策樹構(gòu)建，得到m棵樹。和Bagging相比，它多了一次針對(duì)表征的隨機(jī)選擇。

10.boosting和AdaBoost

如果說(shuō)Bagging是一個(gè)并行的集合，因?yàn)槊總€(gè)分類器都是彼此獨(dú)立的，那么AdaBoost就是一種連續(xù)的方法，因?yàn)樗總€(gè)模型的建立都基于糾正前一個(gè)模型的錯(cuò)誤分類。

正如之前提到的，Bagging采取的是一種多個(gè)分類器簡(jiǎn)單評(píng)分的方式。而boosting是和Bagging對(duì)應(yīng)的一種將弱分類器組合成為強(qiáng)分類器的算法框架，它其中的一種算法是AdaBoost，即在建立多個(gè)弱分類器的基礎(chǔ)上，為分類器進(jìn)行權(quán)重賦值，性能好的分類器能獲得更多權(quán)重，從而使評(píng)分結(jié)果更理想。

AdaBoost分類示意圖

上圖是AdaBoost分類的圖解，從中我們可以發(fā)現(xiàn)：

步驟1：首先訓(xùn)練一個(gè)分類器對(duì)輸入數(shù)據(jù)進(jìn)行分類；

如圖①所示，所有圓形和三角形此時(shí)權(quán)重一致，分類器把它們分成了兩類，但其中下方的兩個(gè)圓形被錯(cuò)誤地歸類為三角形，因此，該分類器在圖上上部數(shù)據(jù)的分類上有優(yōu)勢(shì)。之后，我們提高了這兩個(gè)圓的權(quán)重，并把它們放入下一個(gè)分類器。

步驟2：將重新分配權(quán)重的數(shù)據(jù)放入下一個(gè)分類器；

如圖②所示，第二個(gè)分類器明顯發(fā)現(xiàn)了權(quán)重較重的兩個(gè)圓，并把它們歸位一類，但它卻沒(méi)能分清其他圓形和三角形的差別，因此，它在圖像左側(cè)數(shù)據(jù)分類上被圓形加權(quán)，在這一區(qū)域有更好的優(yōu)勢(shì)。之后，我們對(duì)右側(cè)數(shù)據(jù)中被錯(cuò)分的三個(gè)圓形做權(quán)重調(diào)整。

步驟3：將重新分配權(quán)重的數(shù)據(jù)放入下一個(gè)分類器；

如圖③所示，這一次第三個(gè)分類器判斷出了圖像右側(cè)的兩個(gè)三角形，但沒(méi)能分辨左側(cè)數(shù)據(jù)，因此在右側(cè)有一定權(quán)重優(yōu)勢(shì)。

步驟4：結(jié)合三個(gè)分類器進(jìn)行決策。

如圖④所示，該強(qiáng)分類器展示了3個(gè)弱分類器的評(píng)分結(jié)果，每塊區(qū)域的分類情況由該區(qū)域權(quán)重高的分類器決定，所以即便是最簡(jiǎn)單的分類器，它們組合起來(lái)也會(huì)有不錯(cuò)的效果。

四、結(jié)語(yǔ)

回顧全文，我們可以掌握：

1. 5種監(jiān)督學(xué)習(xí)算法：線性回歸、Logistic回歸、CART、樸素貝葉斯和KNN；

2. 3種非監(jiān)督學(xué)習(xí)算法：Apriori、K-means、PC；

3. 兩種集成技巧：Bagging和隨機(jī)森林、boosting和AdaBoost。