初學機器學習必備10大演算法

毫無疑問，過去幾年中，作為人工智慧的主要領域，越來越多的人投身於機器學習研究。《哈佛商業評論》甚至將機器學習科學家稱為「21 世紀最性感的工作」。為了幫助機器學習初學者快速入門，加拿大皇后大學機器學習專家 Reena Shaw 特意寫了一篇文章，總結了機器學習初學者需要知道的 10 大演算法。

ML 演算法是指無需人類介入，就能從數據中學習，從經驗中優化的演算法。學習任務包括學習將輸入映射到輸入的函數，學習未標記數據中的隱藏結構；或者「基於實例的學習」，即將新的實例和訓練數據中的實例進行比較，為一個新的實例生成一個類標籤。

機器學習初學者需要知道的 10 個 ML 演算法：

ML 演算法的類型

ML 演算法大體上分為三類：

1 監督式學習：

監督式學習可以這樣解釋：使用標記的訓練數據學習輸入變數(X )到輸出變數(Y)的映射函數。

Y = f (X)

監督式學習問題會有兩種類型：

1. 分類 ：預測一個給定樣本的結果，其輸出變數的形式為類別。樣本含有標籤，比如男性和女性、生病的和健康的等等。
2. 回歸 ：預測一個給定樣本的結果，其輸出變數的形式為真值。樣本含有實值標籤，比如降雨量、某人的身高等等。

本文介紹的前 5 個演算法：線性回歸、邏輯回歸、分類回歸樹、樸素貝葉斯、K最近鄰演算法，都是監督式學習中的演算法。

集成學習是監督式學習的一種特殊類型，它是指將多種不同的弱機器學習模型的預測結果進行組合，以預測出一個新的樣本。文章末尾介紹的第 9 和第 10 個演算法，即隨機森林-套袋法（Bagging）、XGBoos-提升法（Boosting）都是集成學習中的演算法。

非監督式學習：

非監督式學習問題只有輸入變數(X)，但沒有相應的輸出變數。它使用無標記的訓練數據為數據的隱含結構建模。

非監督式學習問題可以有以下三種類型：

1. 關聯（Association）：發現目錄中項目共現的概率。其廣泛應用於「購物籃分析」。例如，如果一個顧客購買了麵包，他會有80% 的概率也購買雞蛋。
2. 聚集（Clustering）：將樣本分組，這樣，同一聚類中的物體與來自另一聚類的物體相比，相互之間會更加類似。
3. 降維：正如其含義，降維指減少一個數據集的變數數量，同時保證還能傳達重要信息。降維可以通過特徵抽取方法和特徵選擇方法完成。特徵選擇方法會選擇初始變數的子集。特徵抽取方法執行從高維度空間到低維度空間的數據轉換。例如，PCA演算法就是一種特徵抽取方式。

文中提到的第6-8個演算法，即 Apriori 演算法、K 均值演算法、PCA 演算法都是非監督式學習的例子。

增強學習:

增強學習是一種機器學習演算法，能讓 agent 通過學習會讓性能最大化的行為，根據其當前狀態決定下一步最優動作。

增強學習演算法常常通過試錯學習最佳選擇。它們最典型的應用時用在機器人上，比如機器人可以通過碰撞障礙物後接收負面反饋來避免碰撞。

監督式學習演算法

線性回歸：

在機器學習中，我們有一套輸入變數(X)用於決定輸出變數(y)。輸入變數和輸出變數之間存在一種關係，而機器學習的目標就是量化這種關係。

在線性回歸中，輸入值 (X) 和輸出值 (y) 之間的關係可以用方程 y = a + bx 表示。這樣以來，線性回歸的目標就是找出係數 a 和 b 的值，a 為截距，b 為回歸線的斜率。

圖 1 展示了為某個數據集標繪的 x 和 y 的值，目的是匹配出一條最接近大部分點的線。這能夠減少數據點的 y 值和斜線之間的距離（即誤差）。

2 邏輯回歸：

線性回歸預測結果是連續值，而邏輯回歸預測結果在應用轉換函數後是離散值。

邏輯回歸最適合二元分類（數據集中 y=0 或 1，其中 1 指默認類別。例如，在預測某個事件是否會發生時，事件發生歸類為 1；預測某人是否生病時，生病的狀況會以1表示）。它以

應用在其中的轉換函數而命名，稱為邏輯函數 h(x)= 1/ (1 + e^x)，是一個 S 型曲線。

在邏輯回歸中，輸出值的形式為默認類的概率（不像線性回歸中，輸出值為直接產生）。因為是概率，所以輸出值會介乎 0 到 1 之間。通過使用邏輯函數 h(x)= 1/ (1 + e^ -x)，對 X 值進行對數轉換可得到輸出值。然後用闕值將得到的概率，即輸出值，應用到二元分類中。

在圖 2 示例中，要確定一個腫瘤是否為惡性，默認值為 y=1（腫瘤=惡性）；x 值可以是腫瘤的度量值，比如腫瘤的大小。如圖中所示，邏輯函數將數據集中多種例子下的 x 值轉換為 0 到 1 之間的概率值。如果概率超過了闕值 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）是決策樹的一種應用形式，其它形式還有 ID3 和 C4.5 等。

CART 的非終端節點為根節點和內節點。終端節點為葉節點。每個非終端節點代表一個單個輸入變數 (X) 和該變數的分割點；而葉節點代表輸出變數 (y)。該模型以如下形式用於預測：沿著決策樹的分叉點，到達葉節點，輸出在該葉節點上表示的值。

圖 3 中的決策樹分類了某人根據自己的年齡和婚姻狀況決定買跑車還是旅行車。如果此人超過 30 歲且未婚，我們這樣沿著決策樹：「超過 30 歲嗎？」 -> 是 ->「已婚？」 -> 否。因此，模型的輸出結果為跑車。

4 樸素貝葉斯：

在某個事件已經發生的情況下，為了計算出另一個相同事件發生的概率，我們使用貝葉斯定理。根據某些變數的給定值，要想計算某個結果的概率，也就是根據我們的已知知識（d）計算假設（h）為真的概率，我們這樣使用貝葉斯定理：

P(h|d)= (P(d|h) * P(h)) / P(d)

其中：

P(h|d) =後驗概率。假設h的概率為真，給定數據為d，那麼 P(h|d)= P(d1| h)* P(d2| h)*....*P(dn| h)* P(d)

P(d|h) =可能性。假設 h 為真時，數據 d 的概率。

P(h) = 類的先驗概率。假設 h 的概率為真（不管數據 d 的情況）。

P(d) = Predictor 的先驗概率。數據 d 的概率（不管假設 h 的情況）。

這種演算法之所以被稱為「樸素」，是因為它假定所有的變數之間相互獨立，而這種假設在實際應用往往不成立。

用圖 4 作為一個例子，如果 weather=「sunny」，結果是什麼？

如果變數 weather=「sunny」，要想確定結果 Play 為「Yes」或「No」，需計算圖中P(yes|sunny) 和 P(no|sunny)，以較高的概率值選擇結果。

->P(yes|sunny)= (P(sunny|yes) * P(yes)) / P(sunny)

= (3/9 * 9/14 ) / (5/14)

= 0.60

-> P(no|sunny)= (P(sunny|no) * P(no)) / P(sunny)

= (2/5 * 5/14 ) / (5/14)

= 0.40

這樣，如果weather=「sunny」，結果為play= 『yes』。

5 K最近鄰演算法（KNN）

K 最近鄰演算法使用整個數據集作為訓練集，而非將數據集分割為一個數據集和一個測試集。

當一個新的數據實例需要一個結果時，KNN演算法會遍歷整個數據集找到這個新數據實例的K個最近實例，或者和新記錄最相似的實例的K數量，然後輸出結果的平均值（針對回歸問題）或者分類問題中的模式。K的值為用戶指定。

可使用比如歐幾里得距離和漢明距離等方式計算實例之間的相似度。

非監督式學習

6 Apriori演算法：

Apriori 演算法常被用於事務資料庫中挖掘頻繁集，然後生成關聯規則。它常常用在市場分析中，檢查在數據中頻繁共現的產品的組合。總體上講，我們將「如果某人購買物品 X，那麼他也購買物品 Y」的關聯規則寫為 X -> Y。

例如，如果某人購買了牛奶和糖，那麼他會很可能也會購買咖啡粉。這種情況的關聯規則可以被寫為 {milk,sugar} -> coffee powder。關聯規則的強度可以用它的支持度（support）和置信度（confidence）來度量。

圖中，支持度幫助刪除生成頻繁集時要考慮的候選集的數目。該支持度受到 Apriori 原則的指導。Apriori 原則認為，如果某個集為頻繁集，那麼該集所有的子集也必須為頻繁集。

7 K均值演算法：

K 均值演算法是很典型的基於距離的聚類演算法，採用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大。

它是一種迭代演算法，將相似數據分組為聚類。它會計算出 K 個聚類的中心值，將一個數據點賦給一個聚類，該聚類的中心和賦給它的數據點之間的距離最近。

第 1 步：K 均值迭代：

1. 選擇一個K 值。這裡，我們取 K 值為 3.
2. 隨機將每個數據點賦給 3 個聚類中任意一個。
3. 計算出每個聚類的聚類中心。紅色、藍色和綠色星標表示 3 個聚類的聚類中心。

第 2 步：

將每個數據點重新賦給最近的聚類中心。這裡，最上面的 5 個點被賦給藍色聚類中心的那個聚類。按同樣的步驟，將數據點賦給有紅色和綠色聚類中心的聚類。

第 3 步：

計算新聚類的中心。用灰色星標表示原來的聚類中心，繼續用紅色、綠色和藍色星標表示新的聚類中心。

第 4 步：

重複步驟 2-3，直到各個聚類之間的數據點不再變換。在經過這兩個連續步驟沒有數據點的切換情況後，導出K均值演算法。

8 PCA：

主成分分析（PCA）通過減少變數數目用於更容易地探究和可視化數據。主要是通過獲取數據中的最大方差，轉換入一個坐標稱為「主成分」的坐標系中完成這個過程。每個成分都是一個原始變數的線性組合，相互之間是正交關係。成分之間的正交關係表明這些成分之間的相關性為 0.

第一個主成分獲取數據中最大方差的方向。第二個主成分獲取數據中的剩餘方差，但變數和第一個成分沒有相關性。同樣地，所有接下來的主成分（PC3，PC4 等等）獲取剩餘方差，且和之前的成分沒有相關性。

集成學習

「集成」意思是通過投票或求平均值，將多個分類器的結果組合在一起，以改進結果。投票用在分類問題中，求平均值則用在回歸問題中。其理念是，將學習模型集合在一起的效果要好於單個學習模型。

集成學習演算法有三種類型：套袋法（bagging）、提升法（Boosting）和堆疊法（stacking），但本文是面向初學者，暫時先只講套袋法和提升法。

9 隨機森林-Bagging演算法：

隨機森林（多個學習模型）是套袋式決策樹（bagged decision tree，即單個學習模型）的改進形式。

套袋法（bagging）：該方法的第一步就是用數據集（用抽樣法創建而成）創建多個模型。在抽樣法中，每個生成的訓練集由原始數據集的隨機次級樣本組成。每個訓練集都和原始數據集一樣大小，但有些記錄會重複幾次，有些記錄則完全不出現。然後，整個原始數據集會被用作測試集。這樣，如果原始數據集的大小為N，那麼每個生成的訓練集大小也為N，特殊記錄的數量大約為（2N/3），測試集的大小也是N。

第二步就是用和生成的不同數據集中一樣的演算法構建多個模型。在這一步中，我們討論一下隨機森林。不像決策樹中，每個節點在將錯誤最小化的最佳特徵處分裂，在隨機森林中，我們選擇各個特徵的一個隨機抽樣用以構建最佳節點。之所以是隨機，是因為：即便是用套袋法，當決策樹選擇一個最佳特徵之處分裂時，最終會是相同的結構和相互關聯的預測。但在各個特徵的隨機子集處分裂後再套袋（bagging）意味著根據子樹的預測之間的相關性較低。

在每個分叉點要搜索的特徵數量被指定為隨機森林演算法的一個參數。

這樣，在隨機森林 bagging 中，用記錄中的隨機樣本構造每個決策樹，用預測器的隨機樣本構造每個分裂。

10 AdaBoost-Boosting演算法：

A) 套袋法（bagging）是一種平行集成，因為每個模型都是獨立搭建。但提升法（Boosting）是一種順序集成，每個模型都是在矯正之前模型的錯誤分類基礎上搭建。

B）套袋法大多涉及「簡單投票」，每個分類器投票獲得一個最終結果，它是由平行模型中的大多數決定。提升法涉及「加權投票」，每個分類器投票獲得最終結果，它也是由大多數來決定，但它是通過將更大的權重賦給先前模型的錯誤分類示例來搭建順序模型。

Adaboost 演算法（自適應增強演算法）指自適應的提升法。

在圖 9，第 1,2,3 步涉及到了一種叫做「決策樁」（decision stump）的弱學習模型（一個1層決策樹根據僅僅 1 個輸入特徵做出預測；這是個根部節點和葉節點立刻相連的決策樹）。構造弱學習模型的過程會不斷持續直到構造完畢用戶定義數量的弱學習模型或者直到訓練再無改進之處。第 4 步將先前模型的 3 個決策樁進行組合（這樣該決策樹中就有了 3 個分裂規則）。

第 1 步：以 1 個決策樁開始根據 1 個輸入變數做出決策：

數據點的數量顯示我們已經應用了相等的權重將它們分類為圓形或三角形。該決策樁已經在上半部分生成了一條水平線將這些數據點進行分類。我們可以看到，有 2 個圓形被錯誤地預測為三角形。因此，我們會給這 2 個圓形賦給更高的權重，並應用另一個決策樁。

第 2 步：轉向另一個決策樁，根據另一個輸入變數做出決策：

我們發現上一步中這 2 個被錯誤分類的圓形要大於剩餘的數據點。現在，第 2 個決策樁會試著正確地預測這 2 個圓形。

賦給更高的權重後，這 2 個圓形被左側的垂直線正確地分類了。但是，現在又將頂部的 3 個圓形錯誤分類。因此，我們給頂部的這 3 個圓形賦給更高的權重，並應用另一個決策樁。

第 3 步：訓練另一個決策樁，根據另一個輸入變數做出決策：

上一步中被錯誤分類的這 3 個圓形要大於其餘的數據點。現在，在右側已生成了一條垂直線，對三角形和圓形進行分類。

第 4 步：將決策樁進行組合：

我們把前 3 個模型中的分離器組合在一起，觀察發現和之前每個弱學習模型相比，這個模型的複雜規則正確地分類了數據。

總結

簡單回顧一下，我們學習了：

5個監督式學習演算法：線性回歸、邏輯回歸、CART、樸素貝葉斯、KNN。

3個非監督式學習演算法：Apriori演算法、K均值演算法、PCA。

2個集成學習演算法：隨機森林 Bagging 演算法、Adaboost 提升法。

這麼乾貨的東西，不收藏一下？

參考資料：

https://www.kdnuggets.com/2017/10/top-10-machine-learning-algorithms-beginners.html

作者：Reena Shaw