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

（鄭州大學(xué) 商學(xué)院，鄭州 450001）

0 引言

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

1 機(jī)器學(xué)習(xí)及分類問題概述

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

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

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

2 單一的分類算法

2.1 單一分類算法概述

2.1.1 ANN分類

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

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

2.1.2 樸素貝葉斯分類

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

2.1.3 K近鄰分類

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

2.1.4 決策樹分類

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

2.1.5 支持向量機(jī)分類

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

2.2 碼單一分類算法的比較及應(yīng)用

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

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

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

3 集成分類算法

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

3.1 Bagging系列算法

3.1.1 Bagging分類

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

圖2 Bagging算法流程

3.1.2 RF分類

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

表2 RF的推廣算法

3.2 Boosting系列算法

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

圖3 Adaboost算法流程

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

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

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

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

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

4 機(jī)器學(xué)習(xí)分類算法面臨的挑戰(zhàn)及展望

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

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

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

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

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

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

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