機器學習算法原理及效率分析

中國人民大學附屬中學 葛恭豪

一、引言

上個世紀五十年代，人工智能的概念首先在Dartmouth學會上被提出，之后卻由于眾多技術的限制而未能得到很好的發展。自進入21世紀，人工智能進展飛速。Siri、AlphaGo等眾多新事物進入了人們的生活，人工智能也逐漸成為普通人生活的一部分。

二、常用算法及原理簡介

1.樸素貝葉斯（Naive Bayes classifier，NB）

NB分類器是線性分類器，它以貝葉斯定理為依據，時間效率高，常用于大規模數據處理。貝葉斯定理即根據先驗概率求后驗概率，表達式為：

可預測未知樣本x所屬類別的可能性，選擇其中可能性大的作為x的類。

2.k-近鄰(k-Nearest Neighbors，KNN)

KNN是線性分類方法，簡單高效。它找出未知樣本x周圍最近的k個樣本作為近鄰，針對這k個樣本，將x歸類為多于k/2數量樣本的類。

3.邏輯回歸（Logistic Regression）

LR是一種十分強大的線性分類算法，它根據LR模型對數據進行處理，它可以處理有多個解釋變量的數據。LR處理數據時先建立二項式模型，再進行概率估計。

4.決策樹（Decision Tree，DT）

DT可用于回歸預測，處理數據時,它會構建一種非常直觀的樹狀結構對樣本進行分類，依特征對樣本分類，目標是構建最優的決策樹。DT算法系統化、結構化，可找出屬性和類別之間的關系，并預測出未知類別。

5.隨機森林（Random Forest，RF）

RF處理數據時，會通過矩陣創建多棵決策樹，將數據投入決策樹中。決策樹分類后，依據被預測最多的類屬決定最終分類結果。

6.梯度提升決策樹（Gradient Boosting Decision Tree，GBDT）

GBDT是基于決策樹的線性回歸算法，與隨機森林類似，由多棵決策樹組成，處理結果為多棵決策樹結果。GBDT中的決策樹是回歸樹，因此常被用于回歸預測方面。

7.支持向量機（Support Vector Machine，SVM）

SVM是一種非線性的機器學習算法，它旨在尋找一個超平面，將訓練數據分開。根據結構風險最小化準則計算，使兩類數據邊緣部分垂直于超平面的距離最大時，成為最優超平面。通過構造最優超平面，SVM能夠高精度地處理數據。

8.人工神經網絡（Artificial Neural Networks，ANN）

ANN是近年的研究熱點，它是一種類似于生物神經網絡的非線性算法，由多個類似于神經元的單元組成。ANN基于風險最小化原則，所以有些缺陷，比如易陷入局部極小等。

三、機器學習評價指標

1.分類算法的指標

（1）精確率與召回率

（3）ROC曲線和AUC

ROC曲線適用于二分類問題，它描述了分類器分類正確的正樣本個數占總正樣本個數的比例。ROC曲線下的面積越大則分類器效果越好。AUC指的是ROC曲線下的面積，AUC的值就是ROC曲線下部分的面積大小。

（4）支持度和置信度

四、實驗

1.數據集

數據集選用MNIST手寫數字數據集，數據集分訓練集和測試集，用于訓練模型和檢測結果。其中訓練集有60000樣本，測試集為10000樣本，維度為784。

MNIST訓練集由SD-3的30,000個模式和來自SD-1的30,000個模式組成。這60,000個模式訓練集包含大約250位作家的手寫用例。

2.實驗目的及方案

常用的機器學習分類算法中，屬于線性的有NB、LR，非線性的有DT、RF。實驗的目的是對比它們的時間效率、準確率的情況，得出相應的結論。

基于MNIST數據集，選用pycarm和anaconda平臺，調用python的sklearn包里的機器學習算法作測試，然后對比分析。

3.實驗結果

kNN、LR、RF、SVM、GBDT準確率都相對較高，從時間效率看，SVM、GBDT時間成本大，這樣就顯示出kNN、LR和RF的輕便。而NB時間效率最高，但準確率83.69%較低。

表1 時間和準確率對比

RF的時間效率高，準確率也高；DT結構簡單，但處理數據的準確率和時間效率都不高；SVM和GBDT準確率都高，說明非線性算法擬合數據后處理效果好，處理時間分別是3682.412秒和7036.34秒。

原理上，NB算法簡單，基于貝葉斯定理對樣本的類別進行預測，時間效率高，快過其它，但準確度不高。kNN是尋找未知樣本周圍的樣本，并依據周圍樣本的分類對未知樣本進行分類。因而它比NB計算量大，時間效率低。kNN相比它非線性算法較快，準確率高。

LR算法的準確率為91.98%，比NB、DT高，但比其它算法低。它運行時間為80.523秒，因為計算量較大，比其它線性分類算法慢，但比SVM和GBDT快。綜合分析，線性分類算法優勢在于時間效率高，非線性的結果更好，能更好地擬合數據。究其原因，在于線性分類算法對特征的依賴較多，它要求數據的特征線性可分，線性分類算法時間效率高。

線性分類算法需要更多的數據預處理工作，預先選擇特征、變換特征或者組合特征，使得特征可區分。而非線性分類算法相當于集成了數據的預處理工作，通過自身的建模，對非線性數據也能展示良好的處理性能。

五、總結與展望

本文介紹了8種常用的機器學習算法和11種效果評估指標。不同算法在相同的環境內的效果也都不一樣。用來評價算法效果的方法有很多種，各種方法反映出各種算法的優缺點也各不相同。

通過實驗對比不同的算法在基于MNIST數據集的情況下的準確度和時間效率。如果繼續研究，可以選取更多的算法，并使其基于更多的數據集，例如Car Evaluation、Wine、Adult等。如果想要獲得更全面的實驗結果，可以用更多的機器學習評價指標對實驗進行評估。

[1]張曉芳,張磊.論機器學習及其在教育中的應用[J].信息與電腦:理論版,2015(24):165-166.