機器學習算法選擇

本文主要回顧下幾個常用算法的適應場景和優缺點！

對于你的分類問題，你知道應該如何選擇哪一個機器學習算法么？當然，如果你真的在乎精度（accuracy），最好的方法就是通過交叉驗證（cross-validation）對各個算法一個個地進行測試，進行比較，然后調整參數確保每個算法達到最優解，最后選擇最好的一個。但是如果你只是在尋找一個“good enough”的算法來解決你的問題，或者這里有些技巧可以參考，因為其中會有一些基本準則。

數據集大小

首先來普及一下偏差和方差

• 偏差：描述的是預測值（估計值）的期望E’與真實值T之間的差距。偏差越大，越偏離真實數據。

• 方差：描述的是預測值P的變化范圍，離散程度，也就是離其期望值E的距離。方差越大，數據的分布越分散。

如果是小訓練集，高偏差/低方差的分類器（例如，樸素貝葉斯NB）要比低偏差/高方差大分類的優勢（例如，KNN），因為后者會過度擬合。但是，隨著你訓練集的增長，低偏差/高方差分類器就會漸漸的表現其優勢（因為它們有較低的漸近誤差），因為高偏差分類器此時已經不足以提供準確的模型。

當然，你也可以認為這是生成模型與判別模型的一個區別。

為什么說樸素貝葉斯是高偏差低方差?

以下內容引自知乎：

一些常見算法的優勢

1.樸素貝葉斯

屬于生成式模型，非常簡單，你只是做了一堆計數。如果注有條件獨立性假設，樸素貝葉斯分類器的收斂速度將快于判別模型，如邏輯回歸，所以你只需要較少的訓練數據即可。即使NB條件獨立假設不成立，NB分類器在實踐中仍然表現的很出色。它的主要缺點是它不能學習特征件的相互作用（例如，它不能學習出雖然你喜歡Brad Pitt和Tom Cruise的電影，但是你不喜歡他們在一起演的電影）。

2.Logistic Regression（邏輯回歸）

屬于判別式模型，有很多正則化模型的方法（L0， L1， L2, etc），而且你不必像在用樸素貝葉斯那樣擔心你的特征是否相關。與決策樹與SVM機相比，你還會得到一個不錯的概率解釋，你甚至可以輕松地利用新數據來更新模型（使用在線梯度下降算法）。如果你需要一個概率架構（比如，簡單地調節分類閾值，指明不確定性，或者是要獲得置信區間），或者你希望以后將更多的訓練數據快速整合到模型中去，那么使用它吧。

Sigmoid函數：

$$f(x) = \frac{1}{1+e^{-x}}$$

優點：

• 實現簡單，廣泛的應用于工業問題上；
• 分類時計算量非常小，速度很快，存儲資源低；
• 便利的觀測樣本概率分數；
• 對邏輯回歸而言，多重共線性并不是問題，它可以結合L2正則化來解決該問題；

缺點：

• 當特征空間很大時，邏輯回歸的性能不是很好；
• 容易 欠擬合 ，一般準確度不太高
• 不能很好地處理大量多類特征或變量；
• 只能處理兩分類問題（在此基礎上衍生出來的softmax可以用于多分類），且必須 線性可分 ；
• 對于非線性特征，需要進行轉換；

3.線性回歸

線性回歸是用于回歸的，而不像Logistic回歸是用于分類，其基本思想是用 梯度下降法 對最小二乘法形式的誤差函數進行優化，當然也可以用normal equation直接求得參數的解，結果為：

$$ \hat{w}=(X^{T}X)^{-1}X^Ty$$

而在LWLR（局部加權線性回歸）中，參數的計算表達式為:

$$ \hat{w}=(X^{T}WX)^{-1}X^TWy$$

由此可見LWLR與LR不同，LWLR是一個非參數模型，因為每次進行回歸計算都要遍歷訓練樣本至少一次。

4.最近領算法——KNN

KNN即最近鄰算法，其主要過程為：

1. 計算訓練樣本和測試樣本中每個樣本點的距離（常見的距離度量有歐式距離，馬氏距離等）；
2. 對上面所有的距離值進行排序；
3. 選前k個最小距離的樣本；
4. 根據這k個樣本的標簽進行投票，得到最后的分類類別；

如何選擇一個最佳的K值，這取決于數據。一般情況下，在分類時較大的K值能夠減小噪聲的影響。但會使類別之間的界限變得模糊。一個較好的K值可通過各種啟發式技術來獲取，比如，交叉驗證。另外噪聲和非相關性特征向量的存在會使K近鄰算法的準確性減小。

近鄰算法具有較強的一致性結果。隨著數據趨于無限，算法保證錯誤率不會超過貝葉斯算法錯誤率的兩倍。對于一些好的K值，K近鄰保證錯誤率不會超過貝葉斯理論誤差率。

KNN算法的優點

• 思想簡單，理論成熟，既可以用來做分類也可以用來做回歸；
• 可用于非線性分類；
• 訓練時間復雜度為O(n)；
• 準確度高，對數據沒有假設，對outlier不敏感；

缺點

• 計算量大；
• 樣本不平衡問題（即有些類別的樣本數量很多，而其它樣本的數量很少）；
• 需要大量的內存；

5.決策樹

易于解釋。它可以毫無壓力地處理特征間的交互關系并且是非參數化的，因此你不必擔心異常值或者數據是否線性可分（舉個例子，決策樹能輕松處理好類別A在某個特征維度x的末端，類別B在中間，然后類別A又出現在特征維度x前端的情況）。它的缺點之一就是不支持在線學習，于是在新樣本到來后，決策樹需要全部重建。另一個缺點就是容易出現過擬合，但這也就是諸如隨機森林RF（或提升樹boosted tree）之類的集成方法的切入點。另外，隨機森林經常是很多分類問題的贏家（通常比支持向量機好上那么一丁點），它訓練快速并且可調，同時你無須擔心要像支持向量機那樣調一大堆參數，所以在以前都一直很受歡迎。

決策樹中很重要的一點就是選擇一個屬性進行分枝，因此要注意一下信息增益的計算公式，并深入理解它。

信息熵的計算公式如下:

$$H=-\sum^{n}_{i=1}p(x_i)log_2p(x_i)$$

其中的n代表有n個分類類別（比如假設是2類問題，那么n=2）。分別計算這2類樣本在總樣本中出現的概率p1和p2，這樣就可以計算出未選中屬性分枝前的信息熵。

現在選中一個屬性$x_i$用來進行分枝，此時分枝規則是：如果$x_i=v$的話，將樣本分到樹的一個分支；如果不相等則進入另一個分支。很顯然，分支中的樣本很有可能包括2個類別，分別計算這2個分支的熵H1和H2,計算出分枝后的總信息熵H’ =p1 H1+p2 H2,則此時的信息增益ΔH = H - H’。以信息增益為原則，把所有的屬性都測試一邊，選擇一個使增益最大的屬性作為本次分枝屬性。

決策樹自身的優點

• 計算簡單，易于理解，可解釋性強；
• 比較適合處理有缺失屬性的樣本；
• 能夠處理不相關的特征。

缺點

• 容易發生過擬合（隨機森林可以很大程度上減少過擬合）。

6.支持向量機

高準確率，為避免過擬合提供了很好的理論保證，而且就算數據在原特征空間線性不可分，只要給個合適的核函數，它就能運行得很好。在動輒超高維的文本分類問題中特別受歡迎。可惜內存消耗大，難以解釋，運行和調參也有些煩人，而隨機森林卻剛好避開了這些缺點，比較實用。

優點

• 能夠處理大型特征空間
• 能夠處理非線性特征的相互作用
• 無需依賴整個數據

缺點

• 當觀測樣本很多時，效率并不是很高
• 有時候很難找到一個合適的核函數

算法選擇參考

1. 首當其沖應該選擇的就是邏輯回歸，如果它的效果不怎么樣，那么可以將它的結果作為基準來參考；
2. 然后試試決策樹（隨機森林）是否可以大幅度提升模型性能。即使你并沒有把它當做最終模型，你也可以使用隨機森林來移除噪聲變量；
3. 如果特征的數量和觀測樣本特別多，那么當資源和時間充足時，使用SVM不失為一種選擇。

盡管如此，回想一下， 好的數據卻要優于好的算法 ，設計優良特征是大有裨益的。假如你有一個超大數據集，那么無論你使用哪種算法可能對分類性能都沒太大影響（此時就可以根據速度和易用性來進行抉擇）。

參考文獻

[1] http://blog.echen.me/2011/04/27/choosing-a-machine-learning-classifier/