今天和大家分享一下機器學(xué)習(xí)中常見的六種分類算法：K近鄰、決策樹、樸素貝葉斯、邏輯回歸、支持向量機、隨機森林、AdaBoost、GBDT、XGBoost。

下面，介紹了各個算法的概念及特點。

• KNN
• 決策樹
• 樸素貝葉斯
• 邏輯回歸
• 支持向量機
• 隨機森林
• AdaBoost
• GBDT
• XGBoost

一、K 近鄰（KNN）

k-近鄰算法（K-Nearest neighbors，KNN），它采用測量不同特征值之間的距離方法進行分類，即是給定一個訓(xùn)練數(shù)據(jù)集，對新的輸入實例，在訓(xùn)練數(shù)據(jù)集中找到與該實例最鄰近的K個實例（也就是上面所說的K個鄰居）， 這K個實例的多數(shù)屬于某個類，就把該輸入實例分類到這個類中。

KNN 是一種基本分類與回歸方法，其基本做法是：給定測試實例，基于某種距離度量找出訓(xùn)練集中與其最靠近的k個實例點，然后基于這k個最近鄰的信息來進行預(yù)測。

通常，在分類任務(wù)中可使用“投票法”，即選擇這k個實例中出現(xiàn)最多的標(biāo)記類別作為預(yù)測結(jié)果；在回歸任務(wù)中可使用“平均法”，即將這k個實例的實值輸出標(biāo)記的平均值作為預(yù)測結(jié)果；還可基于距離遠(yuǎn)近進行加權(quán)平均或加權(quán)投票，距離越近的實例權(quán)重越大。

k近鄰法不具有顯式的學(xué)習(xí)過程，事實上，它是懶惰學(xué)習(xí)（lazy learning）的著名代表，此類學(xué)習(xí)技術(shù)在訓(xùn)練階段僅僅是把樣本保存起來，訓(xùn)練時間開銷為零，待收到測試樣本后再進行處理。

k近鄰法的三要素：距離度量、k值的選擇及分類決策規(guī)則是k近鄰法的三個基本要素。

kNN 算法特點：

優(yōu)點：精度高、對異常值不敏感、無數(shù)據(jù)輸入假定

缺點：計算復(fù)雜度高、空間復(fù)雜度高

適用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型

二、決策樹

決策樹(Decision Trees)是一種非參監(jiān)督學(xué)習(xí)方法，即沒有固定的參數(shù)，對數(shù)據(jù)進行分類或回歸學(xué)習(xí)。決策樹的目標(biāo)是從已知數(shù)據(jù)中學(xué)習(xí)得到一套規(guī)則，能夠通過簡單的規(guī)則判斷，對未知數(shù)據(jù)進行預(yù)測。

決策樹是一種基本的分類與回歸方法。在分類問題中，表示基于特征對實例進行分類的過程，可以認(rèn)為是 if-then 的集合，也可以認(rèn)為是定義在特征空間與類空間上的條件概率分布。

決策樹通常有三個步驟：特征選擇、決策樹的生成、決策樹的修剪。

用決策樹分類：從根節(jié)點開始，對實例的某一特征進行測試，根據(jù)測試結(jié)果將實例分配到其子節(jié)點，此時每個子節(jié)點對應(yīng)著該特征的一個取值，如此遞歸的對實例進行測試并分配，直到到達葉節(jié)點，最后將實例分到葉節(jié)點的類中。

決策樹模型

決策樹學(xué)習(xí)的目標(biāo)：根據(jù)給定的訓(xùn)練數(shù)據(jù)集構(gòu)建一個決策樹模型，使它能夠?qū)嵗M行正確的分類。

決策樹學(xué)習(xí)的本質(zhì)：從訓(xùn)練集中歸納出一組分類規(guī)則，或者說是由訓(xùn)練數(shù)據(jù)集估計條件概率模型。

決策樹學(xué)習(xí)的損失函數(shù)：正則化的極大似然函數(shù)。

決策樹學(xué)習(xí)的測試：最小化損失函數(shù)。

決策樹原理和問答猜測結(jié)果游戲相似，根據(jù)一系列數(shù)據(jù)，然后給出游戲的答案。

決策樹算法特點：

優(yōu)點：計算復(fù)雜度不高，輸出結(jié)果易于理解，對中間值的缺失不敏感，可以處理不相關(guān)特征數(shù)據(jù)。

缺點：可能會產(chǎn)生過度匹配問題。

適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型

三、樸素貝葉斯

樸素貝葉斯（Naive Bayesian）是基于貝葉斯定理和特征條件獨立假設(shè)的分類方法，它通過特征計算分類的概率，選取概率大的情況進行分類。

樸素貝葉斯是經(jīng)典的機器學(xué)習(xí)算法之一，也是為數(shù)不多的基于概率論的分類算法。對于大多數(shù)的分類算法，在所有的機器學(xué)習(xí)分類算法中，樸素貝葉斯和其他絕大多數(shù)的分類算法都不同。比如決策樹，KNN，邏輯回歸，支持向量機等，他們都是判別方法，也就是直接學(xué)習(xí)出特征輸出Y和特征X之間的關(guān)系，要么是決策函數(shù)，要么是條件分布。但是樸素貝葉斯卻是生成方法，該算法原理簡單，也易于實現(xiàn)。

樸素貝葉斯

在scikit-learn中，一共有3個樸素貝葉斯的分類算法類。分別是GaussianNB，MultinomialNB和BernoulliNB。其中GaussianNB就是先驗為高斯分布的樸素貝葉斯，MultinomialNB就是先驗為多項式分布的樸素貝葉斯，而BernoulliNB就是先驗為伯努利分布的樸素貝葉斯。

樸素貝葉斯算法特點：

優(yōu)點：在數(shù)據(jù)較少的情況下依然有效，可以處理多類別問題。

缺點：對于輸入數(shù)據(jù)的準(zhǔn)備方式較為敏感。

適用數(shù)據(jù)類型：標(biāo)稱型數(shù)據(jù)

四、邏輯回歸

邏輯（Logistic） 回歸是一種統(tǒng)計方法，用于根據(jù)先前的觀察結(jié)果預(yù)測因變量的結(jié)果。它是一種回歸分析，是解決二分類問題的常用算法。

邏輯回歸算法特點：

優(yōu)點：計算代價不高，易于理解和實現(xiàn)

缺點：容易欠擬合，分類精度可能不高（這里是使用構(gòu)造數(shù)據(jù)，效果較佳，并且運行多次，結(jié)果可能不一樣）

五、支持向量機（SVM）

支持向量機（簡稱SVM）英文為Support Vector Machine。它是一 種監(jiān)督式學(xué)習(xí)的方法，它廣泛的應(yīng)用于統(tǒng)計分類以及回歸分析中。支持向量機（Support Vector Machine）是一種十分常見的分類器，核心思路是通過構(gòu)造分割面將數(shù)據(jù)進行分離。

SVM 是一類按監(jiān)督學(xué)習(xí)方式對數(shù)據(jù)進行二元分類的廣義線性分類器，其決策邊界是對學(xué)習(xí)樣本求解的最大邊距超平面，可以將問題化為一個求解凸二次規(guī)劃的問題。與邏輯回歸和神經(jīng)網(wǎng)絡(luò)相比，支持向量機，在學(xué)習(xí)復(fù)雜的非線性方程時提供了一種更為清晰，更加強大的方式。

具體來說就是在線性可分時，在原空間尋找兩類樣本的最優(yōu)分類超平面。在線性不可分時，加入松弛變量并通過使用非線性映射將低維度輸入空間的樣本映射到高維度空間使其變?yōu)榫€性可分，這樣就可以在該特征空間中尋找最優(yōu)分類超平面。

SVM使用準(zhǔn)則：n 為特征數(shù)， m 為訓(xùn)練樣本數(shù)。

• 如果相較于m而言，n要大許多，即訓(xùn)練集數(shù)據(jù)量不夠支持我們訓(xùn)練一個復(fù)雜的非線性模型，我們選用邏輯回歸模型或者不帶核函數(shù)的支持向量機。
• 如果n較小，而且m大小中等，例如n在 1-1000 之間，而m在10-10000之間，使用高斯核函數(shù)的支持向量機。
• 如果n較小，而m較大，例如n在1-1000之間，而??大于50000，則使用支持向量機會非常慢，解決方案是創(chuàng)造、增加更多的特征，然后使用邏輯回歸或不帶核函數(shù)的支持向量機。

SVM 算法特點：

優(yōu)點：計算代價不高，易于理解和實現(xiàn)

缺點：容易欠擬合，分類精度可能不高

適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型數(shù)據(jù)

六、隨機森林

隨機森林是一個包含多個決策樹的分類器， 并且其輸出的類別是由個別樹輸出的類別的眾數(shù)而定。隨機森林解決決策樹泛化能力弱的特點。

隨機森林算法的具體流程

隨機森林算法特點：

優(yōu)點：

• 對于很多種資料，可以產(chǎn)生高準(zhǔn)確度的分類器
• 可以處理大量的輸入變量
• 可以在決定類別時，評估變量的重要性
• 在建造森林時，可以在內(nèi)部對于一般化后的誤差產(chǎn)生不偏差的估計
• 包含一個好方法可以估計丟失的資料，并且如果有很大一部分的資料丟失，仍可以維持準(zhǔn)確度
• 對于不平衡的分類資料集來說，可以平衡誤差
• 可被延伸應(yīng)用在未標(biāo)記的資料上，這類資料通常是使用非監(jiān)督式聚類，也可偵測偏離者和觀看資料
• 學(xué)習(xí)過程很快速

缺點：

• 犧牲了決策樹的可解釋性
• 在某些噪音較大的分類或回歸問題上會過擬合
• 在多個分類變量的問題中，隨機森林可能無法提高基學(xué)習(xí)器的準(zhǔn)確性

七、AdaBoost算法

提升方法是從弱學(xué)習(xí)算法出發(fā)，反復(fù)學(xué)習(xí)，得到一系列的弱分類器（即基本分類器），然后組合這些弱分類器，構(gòu)成一個強分類器，大多數(shù)的提升方法都是改變訓(xùn)練數(shù)據(jù)集的概率分布（訓(xùn)練數(shù)據(jù)的權(quán)值分布），針對不同的訓(xùn)練數(shù)據(jù)分布調(diào)用弱學(xué)習(xí)算法學(xué)習(xí)一系列的弱分類器。

AdaBoost算法特點：

優(yōu)點：

1. 分類精度高；

2. 可以使用各種方法構(gòu)建子分類器，Adaboost算法提供的是框架；

3. 簡單，且不用做特征篩選；

4. 不會造成overfitting。

缺點：

1. 對分類錯誤的樣本多次被分錯而多次加權(quán)后，導(dǎo)致權(quán)重過大，影響分類器的選擇，造成退化問題；（需改進權(quán)值更新方式）

2. 數(shù)據(jù)不平衡問題導(dǎo)致分類精度的急劇下降；

3. 算法訓(xùn)練耗時，拓展困難；

4. 存在過擬合，穩(wěn)健性不強等問題。

八、GBDT

GBDT的基本結(jié)構(gòu)是決策樹組成的森林，學(xué)習(xí)方式是梯度提升。
具體講，GBDT作為集成模型，預(yù)測的方式是把所有子樹的結(jié)果加起來。GBDT通過逐一生成決策子樹的方式生成整個森林，生成新子樹的過程是利用樣本標(biāo)簽值與當(dāng)前樹林預(yù)測值之間的殘差，構(gòu)建新的子樹。

GBDT 算法特點：

優(yōu)點：

1) 可以靈活處理各種類型的數(shù)據(jù)，包括連續(xù)值和離散值。

2) 在相對少的調(diào)參時間情況下，預(yù)測的準(zhǔn)確率也可以比較高。這個是相對SVM來說的。

3）使用一些健壯的損失函數(shù)，對異常值的穩(wěn)健性非常強。比如 Huber損失函數(shù)和Quantile損失函數(shù)。

缺點：

1) 由于弱學(xué)習(xí)器之間存在依賴關(guān)系，難以并行訓(xùn)練數(shù)據(jù)。不過可以通過自采樣的SGBT來達到部分并行。

九、XGBoost算法

極端梯度提升（eXtreme Gradient Boosting，XGBoost）。XGBoost是陳天奇等人開發(fā)的一個開源機器學(xué)習(xí)項目，高效地實現(xiàn)了GBDT算法并進行了算法和工程上的許多改進，被廣泛應(yīng)用在Kaggle競賽及其他許多機器學(xué)習(xí)競賽中并取得了不錯的成績。

它是大規(guī)模并行boosted tree的工具，它是目前最快最好的開源boosted tree工具包。XGBoost 所應(yīng)用的算法就是 GBDT（gradient boosting decision tree）的改進，既可以用于分類也可以用于回歸問題中。與GBDT最大的區(qū)別是xgboost通過對目標(biāo)函數(shù)做二階泰勒展開，從而求出下一步要擬合的樹的葉子節(jié)點權(quán)重（需要先確定樹的結(jié)構(gòu)），從而根據(jù)損失函數(shù)求出每一次分裂節(jié)點的損失減小的大小，從而根據(jù)分裂損失選擇合適的屬性進行分裂。

1.XGBoost與GBDT相比，其優(yōu)勢：

將樹模型的復(fù)雜度加入到正則項中，來避免過擬合，因此泛化性能會優(yōu)于GBDT。

損失函數(shù)用泰勒展開式展開，同時用到了一階和二階導(dǎo)數(shù)，可以加快優(yōu)化速度。

GBDT只支持CART作為基學(xué)習(xí)器，XGBoost還支持線性分類器作為基學(xué)習(xí)器。

引進了特征子采樣，像隨機森林那樣，既能避免過擬合，又能減少計算。

在尋找最優(yōu)分割點時，考慮到傳統(tǒng)的貪心算法效率較低，實現(xiàn)了一種近似貪心算法，用來加速和減少內(nèi)存小號，除此之外，還考慮了稀疏數(shù)據(jù)集合缺失值的處理。

XGBoost支持并行處理。XGBoost的并行不是模型生成的并行，而是在特征上的并行，將特征排序后以block的形式存儲在內(nèi)存中，在后面迭代重復(fù)使用這個結(jié)構(gòu)。這個block也使得并行化成為了可能，其次在節(jié)點分裂時，計算每個特征的增益，最終選擇增益最大的那個特征去做分割，那么各個特征的增益計算就可以開多線程進行。

2.與lightGBM相比的不足點：

XGBoosting采用預(yù)排序，在迭代之前，對結(jié)點的特征做預(yù)排序，遍歷選擇最優(yōu)分割點，數(shù)據(jù)量大時，貪心法耗時，LightGBM方法采用histogram算法，占用的內(nèi)存低，數(shù)據(jù)分割的復(fù)雜度更低。

XGBoosting采用level-wise生成決策樹，同時分裂同一層的葉子，從而進行多線程優(yōu)化，不容易過擬合，但很多葉子節(jié)點的分裂增益較低，沒必要進行更進一步的分裂，這就帶來了不必要的開銷；LightGBM采用深度優(yōu)化，leaf-wise生長策略，每次從當(dāng)前葉子中選擇增益最大的結(jié)點進行分裂，循環(huán)迭代，但會生長出更深的決策樹，產(chǎn)生過擬合，因此引入了一個閾值進行限制，防止過擬合。

如何決定選擇哪種分類算法

下面有一個列表，可以幫助您了解應(yīng)該使用哪些分類算法來解決業(yè)務(wù)問題。

1. 問題識別：首先要做的是徹底了解手頭的任務(wù)。如果是有監(jiān)督的分類案例，可以使用邏輯回歸、隨機森林、決策樹等算法。
2. 數(shù)據(jù)集的大?。簲?shù)據(jù)集的大小也是您在選擇算法時應(yīng)該考慮的一個參數(shù)。由于很少有算法相對較快，因此最好切換到那些算法。如果數(shù)據(jù)集的大小很小，您可以堅持使用像樸素貝葉斯這樣的低偏差/高方差算法。相反，如果數(shù)據(jù)集很大，特征數(shù)量很多，那么你應(yīng)該使用高偏差/低方差算法，如 KNN、決策樹和 SVM。
3. 預(yù)測準(zhǔn)確度：模型的準(zhǔn)確度是測試分類器好壞的參數(shù)。它反映了預(yù)測輸出值與正確輸出值的匹配程度。當(dāng)然，更高的精度是可取的，但還應(yīng)檢查模型是否過擬合。
4. 訓(xùn)練時間：有時，像 SVM 和隨機森林這樣的復(fù)雜算法可能會占用大量計算時間。此外，更高的準(zhǔn)確性和大數(shù)據(jù)集無論如何需要更多時間來學(xué)習(xí)模式。像邏輯回歸這樣的簡單算法更容易實現(xiàn)并節(jié)省時間。
5. 數(shù)據(jù)集的線性：輸入變量和目標(biāo)變量之間并不總是存在線性關(guān)系。因此，必須分析這種關(guān)系并仔細(xì)選擇算法，因為其中一些僅限于線性數(shù)據(jù)集。檢查線性的最佳方法是擬合線性線或運行邏輯回歸或 SVM 并查找殘差。較高的誤差表明數(shù)據(jù)是非線性的，需要實施復(fù)雜的算法。
6. 特征數(shù)量：有時，數(shù)據(jù)集可能包含不必要的許多特征，并且并非所有特征都相關(guān)。然后可以使用最適合這種情況的 SVM 等算法，或者使用主成分分析來確定哪些特征是重要的。