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

一、導語

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

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

二、ML算法類型

ML算法的類型可分為監(jiān)督學習、無監(jiān)督學習和強化學習三種。

1.監(jiān)督學習

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

Y = f (X).

監(jiān)督學習問題主要有兩類：

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

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

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

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

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

2.無監(jiān)督學習

無監(jiān)督學習問題只有輸入變變量（X），而沒有輸出變量（Y），它使用沒有標簽的訓練數(shù)據(jù)來模擬數(shù)據(jù)的基本結構。

無監(jiān)督學習問題也可被分為以下幾類：

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

• 聚類（Clustering）：即對樣本進行分類，使同一類中的樣本更相似，彼此間的關系更緊密。

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

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

3.強化學習

強化學習是一種ML算法，它允許agent根據(jù)當前狀態(tài)選擇下一步行動（最佳），通過學習實現(xiàn)行為的獎勵最大化。

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

三、十大機器學習算法

1.線性回歸

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

線性回歸示意圖

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

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

2.logistic回歸

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

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

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

logistic回歸示意圖

假設我們正在用logistic回歸預測腫瘤是否是惡性的，如果是惡性的，則y=1。如上圖所示，logistic回歸算法中的邏輯函數(shù)將數(shù)據(jù)集中樣本各個值的x轉換成范圍在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。

邏輯回歸的目標是通過訓練數(shù)據(jù)找到b0和b1的值，來縮小預測結果和實際結果的誤差。這些系數(shù)都是用最大似然估計得出的。

3.CART

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

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

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

CART示意圖

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

4.樸素貝葉斯

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

貝葉斯定理

其中：

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

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

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

• P(x)則是預測值的先驗概率，表示x的可能性（與假設無關）。

這個算法被稱為是“naive”的，中文可譯為“天真”“樸素”，因為它假設所有變量都是相互獨立的，事實上，這在現(xiàn)實中幾乎不可能存在。

用樸素貝葉斯預測出去玩的概率

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

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

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

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

問題：如果是晴天，這個人就能出去玩。這個說法是不是正確的？

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算法，它將整個數(shù)據(jù)集作為訓練集，而不是將數(shù)據(jù)集劃分為測試集和訓練集。

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

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

6.Apriori

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

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

用Apriori進行“市場籃子分析”

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

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

7.K-means

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

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

K-means示意圖

步驟1：K-means初始化；

• 設定k值，在上圖中，我們取k=3；

• 將數(shù)據(jù)點隨機劃分成3個聚類；

• 為每個聚類計算質心，用紅、黃、藍三顆星表示。

步驟2：將每個數(shù)據(jù)點與質心關聯(lián)；

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

步驟3：重新計算質心；

計算新聚類的質心，紅、黃、藍表示新質心，灰色星星則是原質心。

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

8.PCA

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

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

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

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

9.Bagging和隨機森林

Bagging和隨機森林都是對單棵決策樹效果的提升。

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

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

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

10.boosting和AdaBoost

如果說Bagging是一個并行的集合，因為每個分類器都是彼此獨立的，那么AdaBoost就是一種連續(xù)的方法，因為它每個模型的建立都基于糾正前一個模型的錯誤分類。

正如之前提到的，Bagging采取的是一種多個分類器簡單評分的方式。而boosting是和Bagging對應的一種將弱分類器組合成為強分類器的算法框架，它其中的一種算法是AdaBoost，即在建立多個弱分類器的基礎上，為分類器進行權重賦值，性能好的分類器能獲得更多權重，從而使評分結果更理想。

AdaBoost分類示意圖

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

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

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

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

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

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

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

步驟4：結合三個分類器進行決策。

如圖④所示，該強分類器展示了3個弱分類器的評分結果，每塊區(qū)域的分類情況由該區(qū)域權重高的分類器決定，所以即便是最簡單的分類器，它們組合起來也會有不錯的效果。

四、結語

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

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

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

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