歡迎光臨
每天分享高質量文章

機器學習演算法優缺點對比及選擇(彙總篇)

(給演算法愛好者加星標,修煉編程內功

轉自:知乎/杜博亞

 

本文的目的,是務實、簡潔地盤點一番當前機器學習演算法。文中內容結合了個人在查閱資料過程中收集到的前人總結,同時添加了部分自身總結,在這裡,依據實際使用中的經驗,將對此類模型優缺點及選擇詳加討論

主要回顧下幾個常用演算法的適應場景及其優缺點!

機器學習演算法太多了,分類、回歸、聚類、推薦、圖像識別領域等等,要想找到一個合適演算法真的不容易,所以在實際應用中,我們一般都是採用啟髮式學習方式來實驗。通常最開始我們都會選擇大家普遍認同的演算法,諸如SVM,GBDT,Adaboost,現在深度學習很火熱,神經網絡也是一個不錯的選擇。

假如你在乎精度(accuracy)的話,最好的方法就是通過交叉驗證(cross-validation)對各個演算法一個個地進行測試,進行比較,然後調整引數確保每個演算法達到最優解,最後選擇最好的一個。但是如果你只是在尋找一個“足夠好”的演算法來解決你的問題,或者這裡有些技巧可以參考,下麵來分析下各個演算法的優缺點,基於演算法的優缺點,更易於我們去選擇它。

1.天下沒有免費的午餐

在機器學習領域,一個基本的定理就是“沒有免費的午餐”。換言之,就是沒有演算法能完美地解決所有問題,尤其是對監督學習而言(例如預測建模)。

舉例來說,你不能去說神經網絡任何情況下都能比決策樹更有優勢,反之亦然。它們要受很多因素的影響,比如你的資料集的規模或結構。

其結果是,在用給定的測試集來評估性能並挑選演算法時,你應當根據具體的問題來採用不同的演算法。

當然,所選的演算法必須要適用於你自己的問題,這就要求選擇正確的機器學習任務。作為類比,如果你需要打掃房子,你可能會用到吸塵器、掃帚或是拖把,但你絕對不該掏出鏟子來挖地。

2. 偏差&方差

在統計學中,一個模型好壞,是根據偏差和方差來衡量的,所以我們先來普及一下偏差(bias)和方差(variance):

1. 偏差:描述的是預測值(估計值)的期望E’與真實值Y之間的差距。偏差越大,越偏離真實資料。

2. 方差:描述的是預測值P的變化範圍,離散程度,是預測值的方差,也就是離其期望值E的距離。方差越大,資料的分佈越分散。

模型的真實誤差是兩者之和,如公式:

通常情況下,如果是小訓練集,高偏差/低方差的分類器(例如,朴素貝葉斯NB)要比低偏差/高方差大分類的優勢大(例如,KNN),因為後者會發生過擬合(overfiting)。然而,隨著你訓練集的增長,模型對於原資料的預測能力就越好,偏差就會降低,此時低偏差/高方差的分類器就會漸漸的表現其優勢(因為它們有較低的漸近誤差),而高偏差分類器這時已經不足以提供準確的模型了。

為什麼說朴素貝葉斯是高偏差低方差?

首先,假設你知道訓練集和測試集的關係。簡單來講是我們要在訓練集上學習一個模型,然後拿到測試集去用,效果好不好要根據測試集的錯誤率來衡量。但很多時候,我們只能假設測試集和訓練集的是符合同一個資料分佈的,但卻拿不到真正的測試資料。這時候怎麼在只看到訓練錯誤率的情況下,去衡量測試錯誤率呢?

由於訓練樣本很少(至少不足夠多),所以通過訓練集得到的模型,總不是真正正確的。(就算在訓練集上正確率100%,也不能說明它刻畫了真實的資料分佈,要知道刻畫真實的資料分佈才是我們的目的,而不是只刻畫訓練集的有限的資料點)。

而且,實際中,訓練樣本往往還有一定的噪音誤差,所以如果太追求在訓練集上的完美而採用一個很複雜的模型,會使得模型把訓練集裡面的誤差都當成了真實的資料分佈特征,從而得到錯誤的資料分佈估計。這樣的話,到了真正的測試集上就錯的一塌糊塗了(這種現象叫過擬合)。但是也不能用太簡單的模型,否則在資料分佈比較複雜的時候,模型就不足以刻畫資料分佈了(體現為連在訓練集上的錯誤率都很高,這種現象較欠擬合)。過擬合表明採用的模型比真實的資料分佈更複雜,而欠擬合表示採用的模型比真實的資料分佈要簡單。

在統計學習框架下,大家刻畫模型複雜度的時候,有這麼個觀點,認為Error = Bias + Variance。這裡的Error大概可以理解為模型的預測錯誤率,是有兩部分組成的,一部分是由於模型太簡單而帶來的估計不准確的部分(Bias),另一部分是由於模型太複雜而帶來的更大的變化空間和不確定性(Variance)。

所以,這樣就容易分析朴素貝葉斯了。它簡單的假設了各個資料之間是無關的,是一個被嚴重簡化了的模型。所以,對於這樣一個簡單模型,大部分場合都會Bias部分大於Variance部分,也就是說高偏差而低方差。

在實際中,為了讓Error儘量小,我們在選擇模型的時候需要平衡Bias和Variance所占的比例,也就是平衡over-fitting和under-fitting。

當模型複雜度上升的時候,偏差會逐漸變小,而方差會逐漸變大。

3. 常見演算法優缺點

 3.1 朴素貝葉斯 

朴素貝葉斯屬於生成式模型(關於生成模型和判別式模型,主要還是在於是否需要求聯合分佈),比較簡單,你只需做一堆計數即可。如果註有條件獨立性假設(一個比較嚴格的條件),朴素貝葉斯分類器的收斂速度將快於判別模型,比如邏輯回歸,所以你只需要較少的訓練資料即可。即使NB條件獨立假設不成立,NB分類器在實踐中仍然表現的很出色。它的主要缺點是它不能學習特征間的相互作用,用mRMR中R來講,就是特征冗餘。取用一個比較經典的例子,比如,雖然你喜歡Brad Pitt和Tom Cruise的電影,但是它不能學習出你不喜歡他們在一起演的電影。

優點:

1. 朴素貝葉斯模型發源於古典數學理論,有著堅實的數學基礎,以及穩定的分類效率;

2. 對大數量訓練和查詢時具有較高的速度。即使使用超大規模的訓練集,針對每個專案通常也只會有相對較少的特征數,並且對專案的訓練和分類也僅僅是特征概率的數學運算而已;

3. 對小規模的資料表現很好,能個處理多分類任務,適合增量式訓練(即可以實時的對新增的樣本進行訓練);

4. 對缺失資料不太敏感,演算法也比較簡單,常用於文本分類;

5. 朴素貝葉斯對結果解釋容易理解。

缺點:

1. 需要計算先驗概率;

2. 分類決策存在錯誤率;

3. 對輸入資料的表達形式很敏感;

4. 由於使用了樣本屬性獨立性的假設,所以如果樣本屬性有關聯時其效果不好。

朴素貝葉斯應用領域

1. 欺詐檢測中使用較多;

2. 一封電子郵件是否是垃圾郵件;

3. 一篇文章應該分到科技、政治,還是體育類;

4. 一段文字表達的是積極的情緒還是消極的情緒;

5. 人臉識別。

 3.2 Logistic Regression(邏輯回歸) 

邏輯回歸屬於判別式模型,同時伴有很多模型正則化的方法(L0, L1,L2,etc),而且你不必像在用朴素貝葉斯那樣擔心你的特征是否相關。與決策樹、SVM相比,你還會得到一個不錯的概率解釋,你甚至可以輕鬆地利用新資料來更新模型(使用在線梯度下降演算法-online gradient descent)。如果你需要一個概率架構(比如,簡單地調節分類閾值,指明不確定性,或者是要獲得置信區間),或者你希望以後將更多的訓練資料快速整合到模型中去,那麼使用它吧。

Sigmoid函式:運算式如下:

優點:

1. 實現簡單,廣泛的應用於工業問題上;

2. 分類時計算量非常小,速度很快,儲存資源低;

3. 便利的觀測樣本概率分數;

4. 對邏輯回歸而言,多重共線性並不是問題,它可以結合L2正則化來解決該問題;

5. 計算代價不高,易於理解和實現。

缺點:

1. 當特征空間很大時,邏輯回歸的性能不是很好;

2. 容易欠擬合,一般準確度不太高;

3. 不能很好地處理大量多類特征或變數;

4. 只能處理兩分類問題(在此基礎上衍生出來的softmax可以用於多分類),且必須線性可分;

5. 對於非線性特征,需要進行轉換。

logistic回歸應用領域:

1. 用於二分類領域,可以得出概率值,適用於根據分類概率排名的領域,如搜索排名等;

2. Logistic回歸的擴展softmax可以應用於多分類領域,如手寫字識別等;

3. 信用評估;

4. 測量市場營銷的成功度;

5. 預測某個產品的收益;

6. 特定的某天是否會發生地震。

 3.3 線性回歸 

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

而在LWLR(區域性加權線性回歸)中,引數的計算運算式為: 

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

優點: 實現簡單,計算簡單。

缺點: 不能擬合非線性資料。

 3.4 最近鄰演算法——KNN 

KNN即最近鄰演算法,其主要過程為:

1. 計算訓練樣本和測試樣本中每個樣本點的距離(常見的距離度量有歐式距離,馬氏距離等); 

2. 對上面所有的距離值進行排序(升序);

3. 選前k個最小距離的樣本;

4. 根據這k個樣本的標簽進行投票,得到最後的分類類別。

如何選擇一個最佳的K值,這取決於資料。一般情況下,在分類時較大的K值能夠減小噪聲的影響,但會使類別之間的界限變得模糊。一個較好的K值可通過各種啟髮式技術來獲取,比如,交叉驗證。另外噪聲和非相關性特征向量的存在會使K近鄰演算法的準確性減小。近鄰演算法具有較強的一致性結果,隨著資料趨於無限,演算法保證錯誤率不會超過貝葉斯演算法錯誤率的兩倍。對於一些好的K值,K近鄰保證錯誤率不會超過貝葉斯理論誤差率。

KNN演算法的優點

1. 理論成熟,思想簡單,既可以用來做分類也可以用來做回歸;

2. 可用於非線性分類;

3. 訓練時間複雜度為O(n);

4. 對資料沒有假設,準確度高,對outlier不敏感;

5. KNN是一種在線技術,新資料可以直接加入資料集而不必進行重新訓練;

6. KNN理論簡單,容易實現。

缺點

1. 樣本不平衡問題(即有些類別的樣本數量很多,而其它樣本的數量很少)效果差;

2. 需要大量記憶體;

3. 對於樣本容量大的資料集計算量比較大(體現在距離計算上);

4. 樣本不平衡時,預測偏差比較大。如:某一類的樣本比較少,而其它類樣本比較多;

5. KNN每一次分類都會重新進行一次全域性運算;

6. k值大小的選擇沒有理論選擇最優,往往是結合K-折交叉驗證得到最優k值選擇。

KNN演算法應用領域

文本分類、樣式識別、聚類分析,多分類領域

 3.5 決策樹 

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

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

信息熵的計算公式如下:

其中的n代表有n個分類類別(比如假設是二類問題,那麼n=2)。分別計算這2類樣本在總樣本中出現的概率

,這樣就可以計算出未選中屬性分枝前的信息熵。

現在選中一個屬性

用來進行分枝,此時分枝規則是:如果

的話,將樣本分到樹的一個分支;如果不相等則進入另一個分支。很顯然,分支中的樣本很有可能包括2個類別,分別計算這2個分支的熵

和 

,計算出分枝後的總信息熵

,則此時的信息增益

。以信息增益為原則,把所有的屬性都測試一邊,選擇一個使增益最大的屬性作為本次分枝屬性。

決策樹自身的優點

1. 決策樹易於理解和解釋,可以可視化分析,容易提取出規則;

2. 可以同時處理標稱型和數值型資料;

3. 比較適合處理有缺失屬性的樣本;

4. 能夠處理不相關的特征;

5. 測試資料集時,運行速度比較快;

6. 在相對短的時間內能夠對大型資料源做出可行且效果良好的結果。

缺點

1. 容易發生過擬合(隨機森林可以很大程度上減少過擬合);

2. 容易忽略資料集中屬性的相互關聯;

3. 對於那些各類別樣本數量不一致的資料,在決策樹中,進行屬性劃分時,不同的判定准則會帶來不同的屬性選擇傾向;信息增益準則對可取數目較多的屬性有所偏好(典型代表ID3演算法),而增益率準則(CART)則對可取數目較少的屬性有所偏好,但CART進行屬性劃分時候不再簡單地直接利用增益率盡心劃分,而是採用一種啟髮式規則)(只要是使用了信息增益,都有這個缺點,如RF)。

4. ID3演算法計算信息增益時結果偏向數值比較多的特征。

改進措施

1. 對決策樹進行剪枝。可以採用交叉驗證法和加入正則化的方法;

2. 使用基於決策樹的combination演算法,如bagging演算法,randomforest演算法,可以解決過擬合的問題。

應用領域

企業管理實踐,企業投資決策,由於決策樹很好的分析能力,在決策過程應用較多。

3.5.1 ID3、C4.5演算法

ID3演算法是以信息論為基礎,以信息熵和信息增益度為衡量標準,從而實現對資料的歸納分類。ID3演算法計算每個屬性的信息增益,並選取具有最高增益的屬性作為給定的測試屬性。C4.5演算法核心思想是ID3演算法,是ID3演算法的改進,改進方面有: – 用信息增益率來選擇屬性,剋服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足; – 在樹構造過程中進行剪枝; – 能處理非離散的資料; – 能處理不完整的資料。

優點

產生的分類規則易於理解,準確率較高。

缺點

1. 在構造樹的過程中,需要對資料集進行多次的順序掃描和排序,因而導致演算法的低效;

2. C4.5只適合於能夠駐留於記憶體的資料集,當訓練集大得無法在記憶體容納時程式無法運行。

3.5.2 CART分類與回歸樹

是一種決策樹分類方法,採用基於最小距離的基尼指數估計函式,用來決定由該子資料集生成的決策樹的拓展形。如果標的變數是標稱的,稱為分類樹;如果標的變數是連續的,稱為回歸樹。分類樹是使用樹結構演算法將資料分成離散類的方法。

優點

1. 非常靈活,可以允許有部分錯分成本,還可指定先驗概率分佈,可使用自動的成本複雜性剪枝來得到歸納性更強的樹;

2. 在面對諸如存在缺失值、變數數多等問題時CART 顯得非常穩健。

 3.6 Adaboosting 

Adaboost是一種加和模型,每個模型都是基於上一次模型的錯誤率來建立的,過分關註分錯的樣本,而對正確分類的樣本減少關註度,逐次迭代之後,可以得到一個相對較好的模型。該演算法是一種典型的boosting演算法,其加和理論的優勢可以使用Hoeffding不等式得以解釋。

優點

1. Adaboost是一種有很高精度的分類器;

2. 可以使用各種方法構建子分類器,Adaboost演算法提供的是框架;

3. 當使用簡單分類器時,計算出的結果是可以理解的,並且弱分類器的構造極其簡單;

4. 簡單,不用做特征篩選;

5. 不易發生overfitting。

缺點

對outlier比較敏感。

 3.7 SVM支持向量機 

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

優點

1. 可以解決高維問題,即大型特征空間;

2. 解決小樣本下機器學習問題;

3. 能夠處理非線性特征的相互作用;

4. 無區域性極小值問題;(相對於神經網絡等演算法)

5. 無需依賴整個資料;

6. 泛化能力比較強。

缺點

1. 當觀測樣本很多時,效率並不是很高;

2. 對非線性問題沒有通用解決方案,有時候很難找到一個合適的核函式;

3. 對於核函式的高維映射解釋力不強,尤其是徑向基函式;

4. 常規SVM只支持二分類;

5. 對缺失資料敏感。

對於核的選擇也是有技巧的(libsvm中自帶了四種核函式:線性核、多項式核、RBF以及sigmoid核):

第一,如果樣本數量小於特征數,那麼就沒必要選擇非線性核,簡單的使用線性核就可以了;

第二,如果樣本數量大於特征數目,這時可以使用非線性核,將樣本映射到更高維度,一般可以得到更好的結果;

第三,如果樣本數目和特征數目相等,該情況可以使用非線性核,原理和第二種一樣。

對於第一種情況,也可以先對資料進行降維,然後使用非線性核,這也是一種方法。

SVM應用領域

文本分類、圖像識別(主要二分類領域,畢竟常規SVM只能解決二分類問題)

 3.8 人工神經網絡的優缺點 

人工神經網絡的優點:

1. 分類的準確度高;

2. 並行分佈處理能力強,分佈儲存及學習能力強;

3. 對噪聲神經有較強的魯棒性和容錯能力;

4. 具備聯想記憶的功能,能充分逼近複雜的非線性關係。

人工神經網絡的缺點:

1. 神經網絡需要大量的引數,如網絡拓撲結構、權值和閾值的初始值;

2. 黑盒過程,不能觀察之間的學習過程,輸出結果難以解釋,會影響到結果的可信度和可接受程度;

3. 學習時間過長,有可能陷入區域性極小值,甚至可能達不到學習的目的。

人工神經網絡應用領域:

目前深度神經網絡已經應用與計算機視覺,自然語言處理,語音識別等領域並取得很好的效果。

 3.9 K-Means聚類 

是一個簡單的聚類演算法,把n的物件根據他們的屬性分為k個分割,k< n。 演算法的核心就是要優化失真函式J,使其收斂到區域性最小值但不是全域性最小值。

關於K-Means聚類的文章,參見機器學習演算法-K-means聚類。關於K-Means的推導,裡面可是有大學問的,蘊含著強大的EM思想。

優點

1. 演算法簡單,容易實現 ;

2. 演算法速度很快;

3. 對處理大資料集,該演算法是相對可伸縮的和高效率的,因為它的複雜度大約是O(nkt),其中n是所有物件的數目,k是簇的數目,t是迭代的次數。通常k<

4. 演算法嘗試找出使平方誤差函式值最小的k個劃分。當簇是密集的、球狀或團狀的,且簇與簇之間區別明顯時,聚類效果較好。

缺點

1. 對資料型別要求較高,適合數值型資料;

2. 可能收斂到區域性最小值,在大規模資料上收斂較慢;

3. 分組的數目k是一個輸入引數,不合適的k可能傳回較差的結果;

4. 對初值的簇心值敏感,對於不同的初始值,可能會導致不同的聚類結果;

5. 不適合於發現非凸面形狀的簇,或者大小差別很大的簇;

6. 對於”噪聲”和孤立點資料敏感,少量的該類資料能夠對平均值產生極大影響。

 3.10 EM最大期望演算法 

EM演算法是基於模型的聚類方法,是在概率模型中尋找引數最大似然估計的演算法,其中概率模型依賴於無法觀測的隱藏變數。E步估計隱含變數,M步估計其他引數,交替將極值推向最大。

EM演算法比K-means演算法計算複雜,收斂也較慢,不適於大規模資料集和高維資料,但比K-means演算法計算結果穩定、準確。EM經常用在機器學習和計算機視覺的資料集聚(Data Clustering)領域。

 3.11 集成演算法(AdaBoost演算法) 

AdaBoost演算法優點:

1. 很好的利用了弱分類器進行級聯;

2. 可以將不同的分類演算法作為弱分類器;

3. AdaBoost具有很高的精度;

4. 相對於bagging演算法和Random Forest演算法,AdaBoost充分考慮的每個分類器的權重。

Adaboost演算法缺點:

1. AdaBoost迭代次數也就是弱分類器數目不太好設定,可以使用交叉驗證來進行確定;

2. 資料不平衡導致分類精度下降;

3. 訓練比較耗時,每次重新選擇當前分類器最好切分點。

AdaBoost應用領域:

樣式識別、計算機視覺領域,用於二分類和多分類場景

 3.12 排序演算法(PageRank) 

PageRank是google的頁面排序演算法,是基於從許多優質的網頁鏈接過來的網頁,必定還是優質網頁的回歸關係,來判定所有網頁的重要性。(也就是說,一個人有著越多牛X朋友的人,他是牛X的概率就越大。)

PageRank優點

完全獨立於查詢,只依賴於網頁鏈接結構,可以離線計算。

PageRank缺點

1. PageRank演算法忽略了網頁搜索的時效性;

2. 舊網頁排序很高,存在時間長,積累了大量的in-links,擁有最新資訊的新網頁排名卻很低,因為它們幾乎沒有in-links。

 3.13 關聯規則演算法(Apriori演算法) 

Apriori演算法是一種挖掘關聯規則的演算法,用於挖掘其內含的、未知的卻又實際存在的資料關係,其核心是基於兩階段頻集思想的遞推演算法 。

Apriori演算法分為兩個階段:

1. 尋找頻繁項集;

2. 由頻繁項集找關聯規則。

演算法缺點:

1. 在每一步產生侯選專案集時迴圈產生的組合過多,沒有排除不應該參與組合的元素;

2. 每次計算項集的支持度時,都對資料庫中 的全部記錄進行了一遍掃描比較,需要很大的I/O負載。

4. 演算法選擇參考

之前筆者翻譯過一些國外的文章,其中有一篇文章中給出了一個簡單的演算法選擇技巧:

1. 首當其衝應該選擇的就是邏輯回歸,如果它的效果不怎麼樣,那麼可以將它的結果作為基準來參考,在基礎上與其他演算法進行比較;

2. 然後試試決策樹(隨機森林)看看是否可以大幅度提升你的模型性能。即便最後你並沒有把它當做為最終模型,你也可以使用隨機森林來移除噪聲變數,做特征選擇;

3. 如果特征的數量和觀測樣本特別多,那麼當資源和時間充足時(這個前提很重要),使用SVM不失為一種選擇。

通常情況下:【GBDT>=SVM>=RF>=Adaboost>=Other…】,現在深度學習很熱門,很多領域都用到,它是以神經網絡為基礎的,目前筆者自己也在學習,只是理論知識不扎實,理解的不夠深入,這裡就不做介紹了,希望以後可以寫一片拋磚引玉的文章。

演算法固然重要,但好的資料卻要優於好的演算法,設計優良特征是大有裨益的。假如你有一個超大資料集,那麼無論你使用哪種演算法可能對分類性能都沒太大影響(此時就可以根據速度和易用性來進行抉擇)。

推薦閱讀

(點擊標題可跳轉閱讀)

機器學習常見演算法分類彙總

機器學習中的邏輯回歸模型簡介

深入淺出,一篇超棒的機器學習入門文章

覺得本文有幫助?請分享給更多人

關註「演算法愛好者」加星標,修煉編程內功

喜歡就點一下「好看」唄~

    閱讀原文

    赞(0)

    分享創造快樂