監督學習最常見的五種演算法，你知道幾個？

雷鋒網按：本文作者李東軒，原文載于作者

個人博客

，雷鋒網已獲授權。

在機器學習中，無監督學習（Unsupervised learning）就是聚類，事先不知道樣本的類別，通過某種辦法，把相似的樣本放在一起歸位元一類；而監督型學習（Supervised learning）就是有訓練樣本，帶有屬性標籤，也可以理解成樣本有輸入有輸出。

所有的回歸演算法和分類演算法都屬於監督學習。回歸（Regression）和分類（Classification）的演算法區別在於輸出變數的類型，定量輸出稱為回歸，或者說是連續變數預測；定性輸出稱為分類，或者說是離散變數預測。

以下是一些常用的監督型學習方法。

一. K-近鄰演算法（k-Nearest Neighbors，KNN）

K-近鄰是一種分類演算法，其思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。K通常是不大於20的整數。KNN演算法中，所選擇的鄰居都是已經正確分類的物件。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

如上圖，綠色圓要被決定賦予哪個類，是紅色三角形還是藍色四方形？如果K=3，由於紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由於藍色四方形比例為3/5，因此綠色圓被賦予藍色四方形類。

演算法的步驟為：

（1）計算測試資料與各個訓練資料之間的距離；

（2）按照距離的遞增關係進行排序；

（3）選取距離最小的K個點；

（4）確定前K個點所在類別的出現頻率；

（5）返回前K個點中出現頻率最高的類別作為測試資料的預測分類。

二. 決策樹（Decision Trees）

決策樹是一種常見的分類方法，其思想和“人類逐步分析比較然後作出結論”的過程十分相似。決策過程和下圖類似。

決策樹是一個樹結構（可以是二叉樹或非二叉樹）。其每個非葉節點表示一個特徵屬性上的測試，每個分支代表這個特徵屬性在某個值域上的輸出，而每個葉節點存放一個類別。使用決策樹進行決策的過程就是從根節點開始，測試待分類項中相應的特徵屬性，並按照其值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。

不同于貝葉斯演算法，決策樹的構造過程不依賴領域知識，它使用屬性選擇度量來選擇將元組最好地劃分成不同的類的屬性。所謂決策樹的構造就是進行屬性選擇度量確定各個特徵屬性之間的拓撲結構。

那麼如何劃分資料呢？各個特徵的優先順序是怎麼排的？常用的劃分資料集方法有ID3和C4.5

（1） ID3演算法

劃分資料集的最大原則就是將資料變得更加有序。熵（entropy）是描述資訊不確定性（雜亂程度）的一個值。設S是當前資料下的劃分，那麼S的資訊熵的定義如下：

這裡，n是類別的數目，p(xi)表示選擇xi類別的概率（可用類別數量除以總數量估計）。

現在我們假設將S按屬性A進行劃分，則S的條件資訊熵（A對S劃分的期望資訊）為：

這裡，在屬性A的條件下，資料被劃分成m個類別（例如，屬性A是體重，有輕、中、重三個選項，那麼m=3），p(tj)表示類別tj（屬性A中所有具有第j個特性的所有資料）的數量與S總數量的比值，H(tj)表示子類別tj的熵。

資訊增益（Information gain）是指在劃分資料集之前之後資訊發生的變化，其定義如下：

在ID3演算法裡，每一次反覆運算過程中會計算所有剩餘屬性的資訊增益，然後選擇具有最大增益的屬性對資料集進行劃分，如此反覆運算，直至結束。這裡有一個

ID3演算法的實例過程

。

(2) C4.5演算法

D3演算法存在一個問題，就是偏向於多值屬性，例如，如果存在唯一識別屬性ID，則ID3會選擇它作為分裂屬性，這樣雖然使得劃分充分純淨，但這種劃分對分類幾乎毫無用處。ID3的後繼演算法C4.5使用增益率（gain ratio）的資訊增益擴充，試圖克服這個偏倚。嚴格上說C4.5是ID3的一個改進演算法。

在按照ID3的中的方法得到了資訊增益後，再定義分裂資訊（Split Information）：

然後定義增益率（Gain Ratio）:

C4.5選擇增益率為分裂屬性（連續屬性要用增益率離散化）。C4.5演算法有如下優點：產生的分類規則易於理解，準確率較高。其缺點是：在構造樹的過程中，需要對資料集進行多次的順序掃描和排序，因而導致演算法的低效。此外，C4.5只適合於能夠駐留於記憶體的資料集，當訓練集大得無法在記憶體容納時程式無法運行。

如果所有屬性都作為分裂屬性用光了，但有的子集還不是純淨集，即集合內的元素不屬於同一類別。在這種情況下，由於沒有更多資訊可以使用了，一般對這些子集進行“多數表決”，即使用此子集中出現次數最多的類別作為此節點類別，然後將此節點作為葉子節點。

在實際構造決策樹時，通常要進行剪枝，這時為了處理由於資料中的雜訊和離群點導致的過分擬合問題。剪枝有兩種：先剪枝——在構造過程中，當某個節點滿足剪枝條件，則直接停止此分支的構造；後剪枝——先構造完成完整的決策樹，再通過某些條件遍歷樹進行剪枝。悲觀錯誤剪枝PEP演算法是一種常見的事後剪枝策略。

三. 樸素貝葉斯（Naive Bayesian）

貝葉斯分類是一系列分類演算法的總稱，這類演算法均以貝葉斯定理為基礎，故統稱為貝葉斯分類。樸素貝葉斯演算法（Naive Bayesian) 是其中應用最為廣泛的分類演算法之一。樸素貝葉斯分類器基於一個簡單的假定：給定目標值時屬性之間相互條件獨立。樸素貝葉斯的基本思想是對於給出的待分類項，求解在此項出現的條件下各個類別出現的概率，哪個最大，就認為此待分類項屬於哪個類別。

首先給出條件概率的定義，P(A∥B)表示事件A在B發生下的條件概率，其公式為：

貝葉斯定理用來描述兩個條件概率之間的關係，貝葉斯定理公式為：

樸素貝葉斯分類演算法的具體步驟如下：

（1）設x={a1,a2,...,am}為一個待分類項，a1,a2,...,am為x的m個特徵屬性;

（2）設有類別集合C={y1,y2,...,yn}，即共有n個類別；

（3）依次計算x屬於各項分類的條件概率，即計算P(y1∥x)，P(y2∥x)，… ，P(yn∥x)：

注意，演算法的下一步驟是對比這些結果的大小，由於各項分母都是P(x)，所以分母不用計算。分子部分中P(yn)和P(ai∥yn)都是通過樣本集統計而得，其中P(yn)的值為樣本集中屬於yn類的數量與樣本總數量之比，P(ai∥yn)的值為yn類中滿足屬性ai的數量與yn類下樣本總數量之比。

這樣的計算方式符合特徵屬性是離散值的情況，如果特徵屬性是連續值時，通常假定其值服從高斯分佈（也稱正態分佈），即：

那麼P(ai∥yn)的值為：

其中，ηyn和σyn分別為訓練樣本yn類別中ai特徵項劃分的均值和標準差。

對於P(a∥y)=0的情況，當某個類別下某個特徵項劃分沒有出現時，就是產生這種現象，這會令分類器品質大大降低。因此引入Laplace校準，對沒類別下所有劃分的計數加1，這樣如果訓練樣本集數量充分大時，並不會對結果產生影響，也避免了乘積為0的情況。

（4）比較（3）中所有條件概率的大小，最大的即為預測分類結果，即：

這裡有一個樸素貝葉斯分類實例：

檢測SNS社區中不真實帳號

。

四. 邏輯回歸（Logistic Regression）

我們知道，線性回歸就是根據已知資料集求一線性函數，使其盡可能擬合數據，讓損失函數最小，常用的線性回歸最優法有最小二乘法和梯度下降法。而邏輯回歸是一種非線性回歸模型，相比於線性回歸，它多了一個sigmoid函數（或稱為Logistic函數）。邏輯回歸是一種分類演算法，主要用於二分類問題。邏輯回歸的具體步驟如下：

（1）定義假設函數h（即hypothesis）

Sigmoid函數的圖像是一個S型，預測函數就是將sigmoid函數g(x)裡的引數x替換成了邊界函數θ(x)，如下：

這裡hθ(x)表示結果取1的概率，因此對於輸入x分類結果為類別1和類別0的概率分別為：

(2)定義邊界函數θ(x)

對於二維資料，如果是預設線性線性邊界，那麼邊界函數為：

如果是預設非線性線性邊界，那麼邊界函數為的形式就多了，例如：

假設我們現在要解決的是識別圖片中的0或1（樣本庫只有0和1的圖片），圖片大小是20*20，那麼這個時候有400個特徵向量，那麼邊界函數為：

(3)構造損失函數（cost function，loss function）

損失函數的大小可以體現出邊界函數的各項參數是否最優。對於線性回歸，損失函數是歐式距離指標，但這樣的Cost Function對於邏輯回歸是不可行的，因為在邏輯回歸中平方差損失函數是非凸，我們需要其他形式的Cost Function來保證邏輯回歸的成本函數是凸函數。

我們選擇對數似然損失函數:

那麼邏輯回歸的Cost Function可以表示為：

這裡m表示有m個樣本，y是二值型資料，只能0或1，代表兩種不同的類別。

(4)求最優θ

要想找到最合適的邊界函數參數，只要使J(θ)最小即可。最優化的運算式為：

與線性回歸相似，可以採用梯度下降法尋優，也可以採用其他方法，具體見下面列出的第5個參考網址。

參考資料：

機器學習（一）K-近鄰（KNN）演算法

位址：

http://t.cn/RLj0XIZ

演算法雜貨鋪——分類演算法之決策樹(Decision tree)

地址：

http://t.cn/zjqquUf

決策樹演算法總結

位址：

http://t.cn/zjCCJpC

演算法雜貨鋪——分類演算法之樸素貝葉斯分類(Naive Bayesian classification)

地址：

http://t.cn/hqMdur

Coursera公開課筆記: 斯坦福大學機器學習第六課“邏輯回歸(Logistic Regression)”

位址：

http://t.cn/zOuCqYb

TensorFlow & 神經網路演算法高級應用班” 要開課啦！

從初級到高級，理論 + 實戰，一站式深度瞭解 TensorFlow！

本課程面向深度學習開發者，講授如何利用 TensorFlow 解決圖像識別、文本分析等具體問題。課程跨度為 10 周，將從 TensorFlow 的原理與基礎實戰技巧開始，一步步教授學員如何在 TensorFlow 上搭建 CNN、自編碼、RNN、GAN 等模型，並最終掌握一整套基於 TensorFlow 做深度學習開發的專業技能。

兩名授課老師佟達、白髮川身為 ThoughtWorks 的資深技術專家，具有豐富的大資料平臺搭建、深度學習系統開發專案經驗。

時間：每週二、四晚 20：00-21：00

開課時長：總學時 20 小時，分 10 周完成，每週 2 次，每次 1 小時

線上授課地址：http://www.mooc.ai/

雷鋒網相關閱讀：

機器學習十大演算法都是何方神聖？看完你就懂了

最新出爐——資料科學家最常使用的十大演算法