入門數據科學，初學者需要掌握的10大機器學習演算法

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

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

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

ML演算法的類型可分為監督學習、無監督學習和強化學習三種。

1.監督學習

我們可以把監督學習簡單解釋為使用經標記的訓練數據來學習映射函數：將輸入變數（X）映射到輸出變數（Y）：

Y = f (X).

監督學習問題主要有兩類：

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

事實上，集成學習也可以算作監督學習演算法的一類。

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

2.無監督學習

無監督學習問題只有輸入變變數（X），而沒有輸出變數（Y），它使用沒有標籤的訓練數據來模擬數據的基本結構。

無監督學習問題也可被分為以下幾類：

本文中的Apriori、K-means和PCA都是無監督學習的典型演算法。

3.強化學習

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

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

1.線性回歸

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

線性回歸示意圖

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

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

2.logistic回歸

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

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

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

logistic回歸示意圖

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

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

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

3.CART

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

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

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

CART示意圖

如果這個人已經三十多歲了，還沒有結婚，那演算法的分類流程是「30多歲？——是——已婚？——否」，最後輸出「跑車」。

4.樸素貝葉斯

樸素貝葉斯是一種基於貝葉斯定理的演算法，為了計算事件發生的概率，它假設已經發生了另一個事件。

貝葉斯定理

其中：

這個演算法被稱為是「naive」的，中文可譯為「天真」「樸素」，因為它假設所有變數都是相互獨立的，事實上，這在現實中幾乎不可能存在。

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

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

步驟1：將數據集轉換成頻率表；

步驟2：計算不同天氣出去玩的概率，並創建似然表，如陰天的概率是0.29；

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

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

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

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

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

5.KNN

KNN演算法即K Nearest Neighbor演算法，它將整個數據集作為訓練集，而不是將數據集劃分為測試集和訓練集。

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

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

6.Apriori

Apriori是一種針對頻繁項集的演算法，能挖掘布爾關聯規則，正如上文中所提到的，它是一種非監督學習演算法，常被用於「市場籃子分析」。在這類分析中，Apriori會檢查資料庫中頻繁出現的產品組合。如果我們設一個人先購買了商品X，又購買了商品Y，那它們之間的關聯可被表示為X - > Y。

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

用Apriori進行「市場籃子分析」

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

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

7.K-means

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

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

K-means示意圖

步驟1：K-means初始化；

步驟2：將每個數據點與質心關聯；

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

步驟3：重新計算質心；

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

步驟4：重複步驟2、步驟3進行迭代，如果數據不再發生變化，演算法結束。

8.PCA

PCA（主成分分析）是前文提到的非監督學習演算法中的降維類演算法，它用儘可能少的變數去分析存在於這些變數中的信息，使數據更易於搜索和可視化。

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

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

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

9.Bagging和隨機森林

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

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

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

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

10.boosting和AdaBoost

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

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

AdaBoost分類示意圖

上圖是AdaBoost分類的圖解，從中我們可以發現：

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

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

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

如圖②所示，第二個分類器明顯發現了權重較重的兩個圓，並把它們歸位一類，但它卻沒能分清其他圓形和三角形的差別，因此，它在圖像左側數據分類上被圓形加權，在這一區域有更好的優勢。之後，我們對右側數據中被錯分的三個圓形做權重調整。

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

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

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

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

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

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

2. 3種非監督學習演算法：Apriori、K-means、PC；

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

推薦閱讀：