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

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

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

0 引言

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

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

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

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

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

2 單一的分類算法

2.1 單一分類算法概述

2.1.1 ANN分類

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

圖1 分類的實現(xiàn)過程

2.1.2 樸素貝葉斯分類

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

2.1.3 K近鄰分類

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

2.1.4 決策樹分類

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

2.1.5 支持向量機分類

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

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

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

表1 五種單一分類方法優(yōu)缺點對比

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

3 集成分類算法

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

3.1 Bagging系列算法

3.1.1 Bagging分類

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

圖2 Bagging算法流程

3.1.2 RF分類

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

表2 RF的推廣算法

3.2 Boosting系列算法

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

圖3 Adaboost算法流程

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

3.3 Bagging系列算法和Boosting系列算法的區(qū)別

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

表3 Bagging與Boosting的區(qū)別

表4 三種集成分類算法優(yōu)缺點對比

4 機器學習分類算法面臨的挑戰(zhàn)及展望

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

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

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

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

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

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

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