機器學習分類問題及算法研究綜述

楊劍鋒，喬佩蕊，李永梅，王 寧

（鄭州大學 商學院，鄭州 450001）

0 引言

在人類的生產和生活中存在著各種分類問題，對分類方法的需求并不比回歸方法少。分類方法已經得到廣泛研究，如判別分析和Logistic回歸等[1]。但是，傳統分類方法的分類準確度有限，且應用范圍較窄。隨著互聯網和大數據的發展，數據的豐富度和覆蓋面遠超出了人工可以觀察和總結的范疇。結合了統計學、數據庫科學和計算機科學的機器學習已成為人工智能和數據科學發展的主流方向之一。分類問題作為機器學習的一部分，成為了研究的重點。近年來，我國的機器學習分類算法相關研究發展迅猛，并廣泛應用于實踐。因此，對國內機器學習分類算法相關研究進行整理和評述，對學術研究以及實際應用都具有較大的指導意義。

1 機器學習及分類問題概述

機器學習（Machine Learning）是研究計算機如何模仿人類的學習行為，獲取新的知識或經驗，并重新組織已有的知識結構，提高自身的表現[2]。機器學習可以通過計算機在海量數據中學習數據的規律和模式，從中挖掘出潛在信息，廣泛用于解決分類、回歸、聚類等問題。機器學習一般包括監督、半監督、無監督學習問題。在監督學習問題中，數據輸入對象會預先分配標簽，通過數據訓練出模型，然后利用模型進行預測。當輸出變量為連續時，被稱為回歸問題，當輸出變量為離散時，則稱為分類問題。無監督學習問題中，數據沒有標簽。其重點在于分析數據的隱藏結構，發現是否存在可區分的組或集群。半監督學習[3]也是機器學習的一個重要分支。與標記數據相比，未標記數據較容易獲得。半監督學習通過監督學習與無監督學習的結合，利用少量的標記數據和大量的未標記數據進行訓練和分類。

機器學習算法最初多用于解決回歸問題。近年來，分類問題的研究也越來越多。在機器學習中，分類通常被理解為監督學習，但無監督學習和半監督學習也可以獲得更好的分類器。無監督分類是一種用來獲取訓練分類器標簽或推導分類模型參數的方法[4]。半監督分類中的分類器構建既使用了標記樣本又使用了未標記樣本，逐漸成為了研究熱點。本文主要討論了監督分類問題中的算法。

從監督學習的觀點來看，分類是利用有標記的信息發現分類規則、構造分類模型，從而輸出未含標記信息的數據屬性特征的一種監督學習方法[3]，其最終的目標是使分類準確度達到最好[5]。分類的實現過程[6]主要分為兩個步驟（見下頁圖1）：一是“學習步”，即歸納、分析訓練集，找到合適的分類器，建立分類模型得到分類規則；二是“分類步”，即用已知的測試集來檢測分類規則的準確率，若準確度可以接受，則使用訓練好的模型對未知類標號的待測集進行預測。

2 單一的分類算法

2.1 單一分類算法概述

2.1.1 ANN分類

ANN是一種模擬生物神經網絡進行信息處理的數學模型，簡稱為神經網絡。ANN是經典的機器學習算法。McCulloch和Pitts最早提出MP模型證明了單個神經元能執行邏輯功能。ANN分類根據給定的訓練樣本，調整人工神經網絡參數，使網絡輸出接近于已知樣本類標記。用于分類的ANN算法有BP神經網絡、RBF徑向基神經網絡、FNN模糊神經網絡、ANFIS自適應神經網絡等，其中BP神經網絡由于其良好的非線性逼近能力和分類能力得到了最廣泛的應用[7]。

圖1 分類的實現過程

2.1.2 樸素貝葉斯分類

Maron和Kuhns（1960）以貝葉斯理論為基礎，提出了依據概率原則進行分類的NB算法[8]。對于待分類樣本，根據已知的先驗概率，利用貝葉斯公式求出樣本屬于某一類的后驗概率，然后選擇后驗概率最大的類作為該樣本所屬的類。NB改進算法主要有TAN算法、BAN算法、半樸素貝葉斯算法、貝葉斯信念網絡等。

2.1.3 K近鄰分類

Cover和Hart提出了基于距離度量的KNN分類算法[9]。KNN算法將整個數據集作為訓練集，確定待分類樣本與每個訓練樣本之間的距離，然后找出與待分類樣本距離最近的K個樣本作為待分類樣本的K個近鄰。待分類樣本類別是占比最大的類別。KNN算法采用曼哈頓、閔可夫斯基以及歐式距離，其中歐式距離最常用。針對KNN算法的缺點，近鄰規則濃縮法、產生或者修改原型法、多重分類器結合法等改進KNN算法被提出。

2.1.4 決策樹分類

Breiman等提出了早期的決策樹（DT）分類算法—CART算法，其使用樹結構算法將數據分成離散類[10]。Quinlan引入信息增益提出了ID3算法和C4.5算法[11]。目前已發展到C5.0算法，其運行效率等得到進一步完善[12]。DT的改進算法還有EC4.5、SLIQ算法、SPRINT算法、PUBLIC算法等。決策樹是一種倒置的樹形結構，由決策節點、分支和葉子節點組成。DT分類算法一般有兩個步驟：一是利用訓練集從DT最頂層的根節點開始，自頂向下依次判斷，形成一棵決策樹（即建立分類模型）；二是利用建好的DT對待分類樣本集進行分類[13]。

2.1.5 支持向量機分類

Cortes和Vapnik在1995年正式提出了支持向量機(SVM)。SVM是基于統計學的VC維理論與結構風險最小原理的有監督二分類器。根據給定訓練集尋找Rn上的一個實值函數，g(x)以便使用分類函數f(x)=sgn(g(x))推斷任意一個模式x相對應的y的值。當數據線性可分時，SVM通過在原始特征空間中構建一個最優分割超平面，并將其作為決策面，最大化正負樣本之間的邊緣距離，采用訓練集構建分類器對樣本數據進行分類。當數據線性不可分時，SVM使用核函數將樣本數據映射到一個高維空間，然后尋找一個最優分類超平面隔離不同類別樣本數據，從而進行分類。近年來，發展出多種改進SVM算法，如GSVM、FSVM、TWSVMs、RSVM等[14]。

2.2 碼單一分類算法的比較及應用

五種單一分類方法的比較，如表1所示：

表1 五種單一分類方法優缺點對比

ANN分類作為機器學習的重要方法被廣泛應用于模式識別、故障診斷、圖像處理、人臉識別和入侵檢測等領域。近年來，深度神經網絡由于其優異的算法性能逐漸成為了學術界的研究熱點，已經廣泛應用于圖像分析、語音識別、目標檢測、語義分割、人臉識別、自動駕駛等領域[15]。NB分類算法經常被用于文本分類，另外也被用于故障診斷、入侵檢測、垃圾郵件分類等。KNN及其改進分類算法被大量應用于文本分類和故障診斷等領域，如判別糧食作物隱蔽性蟲害[16]等。DT分類主要應用于遙感影像分類、遙感圖像處理以及客戶關系管理中的客戶分類等領域，如地表沙漠化信息提取[17]、機械故障診斷[18]、人體行為的分類識別[19]等。SVM則主要用于二分類領域，在故障診斷、文本分類、模式識別、入侵檢測、人臉識別等領域有廣泛的應用。也擴展到了財務預警、醫學以及機器人等領域。

3 集成分類算法

盡管單一分類方法取得了飛速發展，但實際中仍會遇到這些方法不能有效解決的問題。Hansen和Salamon提出了新的機器學習方法——集成學習（Ensemble Learning）[20]。隨著數據結構復雜、數據量大、數據質量參差不齊等問題愈加突出，集成學習成為了大數據分析的強有力工具。集成學習算法是通過某種方式或規則將若干個基分類器的預測結果進行綜合，進而有效克服過學習、提升分類效果。集成算法按照基分類器是否存在依賴關系分為兩類：基分類器之間沒有依賴關系的Bagging系列算法和有依賴關系的Boosting系列算法。Bagging系列算法中用于分類的主要有Bagging算法和隨機森林（Random Forest,RF）算法。對于復雜數據，集成分類算法通常優于單一分類方法，但預測速度明顯下降，隨著基分類器數目增加，所需存儲空間也急劇增加。因此，選擇性集成被提出，利用少量基本學習機進行集成提高性能[21]。鑒于篇幅限制，本文不討論選擇性集成分類算法。

3.1 Bagging系列算法

3.1.1 Bagging分類

Breiman最早提出Bagging方法[22]。其原理是，首先對原始訓練集使用自助法抽樣（Bootstrap Sampling）的方式得到多個采樣集，然后用這些采樣集分別對多個基分類器進行訓練，最后通過基分類器的組合策略得到最終的集成分類器（見圖2）。在分類問題中，Bagging通常使用投票法，按照少數服從多數或票要過半的原則來投票確定最終類別。

圖2 Bagging算法流程

3.1.2 RF分類

隨機森林（RF）算法是關注決策樹的集成學習，由Breiman于2001年提出[23]。RF算法將CART算法構建的沒有剪枝的分類決策樹作為基分類器，將Bagging和隨機特征選擇結合起來，增加決策樹模型的多樣性。其原理是，首先從原始樣本集中使用Bootstrap方法抽取訓練集，然后在每個訓練集上訓練一個決策樹模型，最后所有基分類器投出最多票數的類別或類別之一為最終類別。除此之外，還出現了一些RF的推廣算法，如表2所示。

表2 RF的推廣算法

3.2 Boosting系列算法

Schapire和Freundfenbi最早提出了兩種Boosting算法[27]。利用重賦權法迭代訓練基分類器，然后采用序列式線性加權方式對基分類器進行組合。由于Boosting算法都要求事先知道弱分類算法分類正確率的下限，但實際中難以確定。Freund等基于Boosting思想進一步提出了AdaBoost算法[28]。其原理是，先給訓練數據中每個樣本賦予權重，并把樣本權重初始化為相等值，訓練得到第一個基分類器；通過計算錯誤率確定第一基分類器權重后，重新調整每個樣本權重，增大被錯分樣本的權重，從而使被錯分樣本在下一次學習中能夠盡可能正確分類。重復上述步驟，直至獲得足夠好的分類器。

圖3 Adaboost算法流程

改進的Adaboost算法有實Adaboost算法、LogitBoost算法、BrownBoost算法等[29]。近年來，由于AdaBoost.M1、AdaBoost.M2和AdaBoost.MH算法可用于解決多分類問題而受到了極大關注。此外，Friedman提出了Gradient Boosting算法，提出在前次建模的損失函數梯度下降方向進行建模，從而不斷進行改進模型[30]。Adaboost算法和Gradient Boosting算法分別與決策樹結合形成了提升樹和梯度提升決策樹（Gradient Boosting Decision Tree,GBDT）[31]。由于GBDT具有較強的泛化能力，適于多種分類問題，被越來越多地關注。

3.3 Bagging系列算法和Boosting系列算法的區別

Boosting與Bagging都是提高弱分類算法準確度的方法，但存在著一定區別（見下頁表3）。Bagging、RF、Adaboost三種主要集成分類算法的優缺點也各不相同（見下頁表4）。其中，RF和Bagging作為Bagging系列算法的不同在于：一是RF的基分類器都是CART決策樹；二是RF在Bagging隨機采樣的基礎上，又加上了特征隨機采樣。Bagging算法主要被用于人臉識別和個人信用評估等領域，也被廣泛應用于不平衡數據分類問題，如針對不平衡數據分類問題的基于Bagging組合學習方法[32]。RF作為一種優秀的非線性機器學習建模工具，廣泛用于模式識別、圖像分類、故障診斷等領域。Adaboost算法主要用于人臉檢測、人臉識別、車倆檢測、行人檢測、目標檢測、人眼檢測、膚色分割等二分類或多分類問題。目前，決策樹和神經網絡是使用最廣泛的Adaboost基分類器。

表3 Bagging與Boosting的區別

表4 三種集成分類算法優缺點對比

4 機器學習分類算法面臨的挑戰及展望

盡管機器學習分類算法可以處理很多復雜的分類問題，但隨著數據變得更加復雜多樣，機器學習分類算法在學習目標和分類效率方面遇到了新的挑戰：

（1）高維小樣本。不同應用領域的數據都呈現出高維度的特點。數據中的冗余、無關信息的增多，使得機器學習分類算法的性能降低，計算復雜度增加。機器學習分類算法一般需要利用大樣本才能進行有效學習，大數據并不意味著訓練樣本數量充足。當樣本量較小且特征中含有大量無關特征或噪聲特征時，可能導致分類精度不高，出現過擬合。

（2）高維不平衡。機器學習分類算法一般假定用于訓練的數據集是平衡的，即各類所含的樣本數大致相等，但現實中數據往往是不平衡的。現有研究通常將不平衡問題和高維問題分開處理，但是實踐中經常存在具有不平衡和高維雙重特性的數據。

（3）高維多分類。除了常見的二分類問題，實際應用中存在著大量的多分類問題，尤其是高維數據的多分類問題，這給現有的機器學習分類算法帶來了挑戰。

（4）特征工程。目前的機器學習分類算法應用中的數據實例是由大量的特征來表示的。良好的分類模型依賴于相關度大的特征集合，剔除不相關和多余特征，不僅能提高模型精確度，而且能減少運行時間。因此，特征選擇的研究對機器學習分類算法的發展越來越重要。

（5）屬性值缺失。屬性值缺失容易降低分類模型的預測準確率，是分類過程中一類常見的數據質量問題。正確解決分類過程中出現的屬性值缺失是一個具有挑戰性的問題。

機器學習是人工智能的重要組成部分，分類是其最重要的任務之一。通過討論了不同機器學習分類算法的特點及應用，可以發現沒有一種算法可以解決所有問題。此外，數據降維、特征選擇將分類算法的發展產生更大的影響。因此，在實際應用中，必須結合實際情況比較和選擇適當的分類算法和數據預處理方法以便更加有效地實現分類目標。在傳統分類算法改進和發展的同時，集成學習將得到更廣泛的應用和發展。