宿 晨，徐 華，崔 鑫，王玲娣

(江南大學 物聯(lián)網(wǎng)工程學院，江蘇 無錫 214122)

分類問題是數(shù)據(jù)挖掘中的難點。絕大多數(shù)分類算法只是在平衡數(shù)據(jù)集分類效果顯著，而在不均衡數(shù)據(jù)集上分類效果欠佳。但現(xiàn)實生活中的分類問題往往是類別不均衡的，例如銀行欺詐的檢測、垃圾郵件的檢測、車輛識別、疾病診斷等。不均衡數(shù)據(jù)分類問題已經(jīng)成為機器學習、數(shù)據(jù)挖掘等領域的重要研究方向之一[1-2]。在實際的生活中，不均衡分類問題大多數(shù)是多分類問題，因此更具有研究意義。而多數(shù)類的不均衡分類問題與二分類的分類問題相比，多數(shù)類對于分類模型要求更高，獲取少數(shù)類的代價也更大，類間數(shù)據(jù)的分布也更多樣化，也更難被分類。針對不均衡數(shù)據(jù)分類的研究主要集中在數(shù)據(jù)層面與算法層面的改進研究。數(shù)據(jù)層面的改進主要集中在對數(shù)據(jù)集的改進，增加少數(shù)類數(shù)據(jù)或減少多數(shù)類數(shù)據(jù)，使得原本的數(shù)據(jù)集相對均衡，主要的改進方法是過采樣與欠采樣。早期，Chawla等[3-4]，提出了一種SMOTEBoost(synthetic minority over-sampling technique and boost)的方法，將SMOTE采樣算法與集成算法Boost相結合，加強了對小類樣本的關注度；武森等[5]將聚類算法運用到采樣中，先利用聚類欠采樣方法將數(shù)據(jù)集均衡化，然后利用AdaBoost算法對新生成的數(shù)據(jù)集進行分類操作；2013年，Krawczyk 等[6]使用 PUSBE(pruned under-sampling balanced ensemble)方法，該方法有效運用了特征選擇技術；2014 年，Krawczyk等[7]又提出了 CS-MCS(cost-sensitive multiple classifier systems)集成方法，運用隨機欠采樣結合遺傳算法相結合的方式。在低維數(shù)據(jù)集上效果明顯，但是高維數(shù)據(jù)集上效果欠佳。文獻[8]指出采樣方法雖然可以提升小類樣本的識別率，但是容易引入噪聲，丟失有用信息，分類器對小類樣本過分的關注也易使得算法陷入局部最優(yōu)。對此， TAO等[9]提出了一種新的過采樣技術，該技術使用實值否定選擇(RNS)過程來生成人工少數(shù)類數(shù)據(jù)，而無需實際的少數(shù)類數(shù)據(jù)。生成的少數(shù)類數(shù)據(jù)(如果有的話)會與實際的少數(shù)類數(shù)據(jù)一起使用，并與多數(shù)類數(shù)據(jù)相結合，作為二分類學習方法的輸入，并且在實驗中證明了其有效性。

從算法的角度來看，改變概率密度，單類學習分類，集成學習，代價敏感學習，核方法等五種主要方法來解決數(shù)據(jù)分類不平衡問題[10]。國際機器學習界的權威Dietterich已經(jīng)將集成學習列為機器學習4大研究之首[11]。TAO等[12]提出了一種新的基于自適應權重的支持向量機成本敏感集成方法，用于不平衡數(shù)據(jù)分類，還創(chuàng)新性的提出了一種自適應的順序錯誤分類權重確定方法。該方法可以基于在提升過程中先前獲得的分類器，在每次迭代時自適應地考慮少數(shù)實例對SVM分類器的不同貢獻，這可以使其產(chǎn)生不同的分類器，從而提高泛化性能。隨后，Tao等[13]又提出了一種新的基于親和度和類別概率的模糊支持向量機技術(ACFSVM)。多數(shù)類樣本的親和力是根據(jù)支持向量描述域(SVDD)模型計算的，該模型僅由給定的多數(shù)類訓練樣本在內(nèi)核空間中進行訓練，類似于FSVM學習所使用的模型。針對噪聲樣本的處理，Tao等[13]采用核k最臨近法來確定與以前相同的核空間中多數(shù)類別樣本的類別概率。具有較低分類概率的樣本更有可能是噪音，并且通過將相似度和分類概率結合起來構成的低隸屬度,減少了噪聲樣本的影響。張苗燕等[14]結合細菌覓食算法的思想，提出了一種新的算法AdAdaboost，并對加權系數(shù)進行了改進，全局優(yōu)化最佳弱分類器，改善了AdaBoost算法誤檢率的同時得到了較好的檢測性能； Guo 等[15]將AdaBoost.M1 算法與特征選擇結合起來，提出了一種新的集成方法BAK(BPSO-AdaBoost-KNN)，使用KNN作為基分類器，但KNN的缺點是不能直接處理帶權數(shù)據(jù)，需要借助re-samplingd的方法轉化數(shù)據(jù)集后使用，而且AdaBoost.M1針對于基分類器的要求過于嚴苛，錯誤率不能超過50%。對此，將胡旺[16]等提出的SPSO(simple particle swarm optimization)算法進行改進，并與Zhu等[17]提出的SAMME.R版本的AdaBoost算法相結合，提出了WSPSO-SAMME.R-DT 算法，用以解決不平衡多分類問題。與AdaBoost.M1 算法所不同的，SAMME.R使用決策樹作為基分類器，避免在訓練樣本上花費時間，降低對基分類器的要求。為了降低基分類器的相關性，引入了隨機化的方法。使用AUCarea作為性能度量指標，并將其作為適應度值，優(yōu)化特征選擇。提升了小類樣本的識別率。

1 算法介紹

1.1 SAMME.R AdaBoost算法

AdaBoost算法是一個迭代過程，弱分類器的生成是串行的。在AdaBoost的訓練過程中，分類器的重心將轉移到那些更難分類的樣本上，即多次錯誤分類的樣本。隨后的訓練也會偏重于這些樣本，這是通過在算法運行期間為訓練樣本分配權重來實現(xiàn)的。樣本權重最初都是一致的，后續(xù)過程中每輪都會對樣本權重進行更新，最終得到一組弱分類器，將所有弱分類器加權組合成一個強分類器。

AdaBoost 算法適用于二分類問題， AdaBoost.M1可用于解決多分類問題。但是AdaBoost.M1的前提條件是基分類器的錯誤率小于50%，這一要求過于嚴格，易導致訓練失敗。針對以上不足，筆者選擇 Zhu等[17]提出的SAMME.R 版本的 AdaBoost算法，降低了對基分類器過于嚴苛的要求，僅比隨機猜測略好即可。同時，使用分類器的類別估計概率值來對樣本權重進行更新。

在該算法中，獲得加權類概率估計的公式為：

p(t)k(x)=Probw(h=k|x),k=1,…,K,

(1)

其中：t為迭代次數(shù)，k為類標簽，Prob函數(shù)是返回區(qū)域中的數(shù)值落在指定區(qū)間內(nèi)的對應概率。獲得加權類概率估計后，利用拉格朗日定理對稱約束優(yōu)化得到h(t)k(x)

(2)

更新樣本權重wi:

(3)

其中:y=(y1,…，ym)T

1.2 性能度量指標AUCarea

對于不平衡二分類問題來說，經(jīng)常使用ROC曲線來度量分類中的不平衡性，ROC是接受者操作特性曲線(receiver operating characteristic)，利用ROC曲線下的面積(area under the curve)作為算法的評價標準，理想中分類器的AUC為1.0，隨機猜測的分類器AUC為0.5。

AUC評價標準無法直接應用與多分類問題，需要對其進行拓展。最常用的2種擴展方法分為[18]：1)一對一方法；2)一對多方法。為了更加清晰的對比這2種方法，令Y={y1,y2,…，yk} ，Y表示的是數(shù)據(jù)的類標簽的集合。在一對一的方法中，計算所有類的兩兩組合(yi,yj)(i≠j) 的AUC值。一對多的方法中，先定義成二分類問題，令yi∈Y，屬于yi的樣本定義為正類，剩余的樣本為負類，然后計算定義后的AUC值。由此將會得到一組AUC值{r1,r2，…，rn} ，最后取平均值，記作avgAUC，作為性能度量值使用。以上2種方法都可簡單的實現(xiàn)，但是無法做到可視化。因為當多個AUC都變化時，avgAUC的值可能沒有任何變化。例如，當ri變?yōu)閞i+σ，rj變?yōu)閞j-σ，(i，j)∈{1,2，…，n}), 最終其avgAUC的值沒有改變，也無法進行分類模型調(diào)整的評價。

采用Hand DJ[19]提出的一種具有可視化優(yōu)點的度量指標方法AUCarea。AUCarea會將所有的AUC的值在極坐標上繪制出來。如圖1所示，黃色虛線三角形代表的就一個是三分類的AUCarea極坐標圖示，黃色虛線所覆蓋的面積就是最終度量值。AUCarea的計算公式如下

(4)

其中：n為AUC的總數(shù);r為每對類組合(yi,yj)(i≠j)的AUC的值。

圖1 三分類的AUCarea極坐標圖示Fig.1 Three-category AUCare polar plot

當所有AUC的值為1時，就達到了理想中的最優(yōu)狀態(tài)，即AUCarea的最大值，如公式(5)所示

(5)

計算歸一化的為公式(6)

(6)

使用歸一化公式(6)所得值記為AUCarea，AUCarea除了可視化的優(yōu)點之外，也對單個差的AUC較為敏感。

2 基于WSPSO特征選擇方法

雖然AdaBoost算法可通過增加小樣本的權重來增強對小樣本的關注，但它仍然使用正確率作為優(yōu)化目標，并且容易引起過擬合。因此，將特征選擇方法與SAMME.R AdaBoost算法結合。SAMME.R算法中加入特征選擇是基于以下考慮：去除不相干特征，減少時間與空間的浪費，加強對特征和特征值之間的聯(lián)系，從而更好的進行分類[20]。特征選擇算法主要有三類：嵌入式(embedded)、過濾式(filter)和封裝式(wrapper)。嵌入式算法的思路是學習器自身自動進行選擇，雖然效果較好，但是對于參數(shù)的設置需要較高的知識背景；過濾式算法的思路是先對各特征的相關性或發(fā)散性進行評估排序，根據(jù)設置的閾值來選擇。但是對特征之間的相關性難以評估，會造成部分有用信息的遺失；封裝式算法的思路是利用學習算法來評估特征的優(yōu)劣，相對于嵌入式算法與過濾式算法，雖然需要巨大的搜索空間，執(zhí)行時間稍長，但不需要過多的背景知識，可直接面向算法優(yōu)化，并且特征間的組合效應也得到了充分的挖掘。綜上，選擇封裝式算法來進行特征選擇。

粒子群優(yōu)化(PSO, particle swarm optimization)[21]算法，具有易實現(xiàn)、結構簡單、沒有復雜變異交叉操作的優(yōu)點，可運用于特征選擇優(yōu)化問題在。文獻[16]在證明PSO進化過程與粒子速度無關后提出了簡化版粒子群優(yōu)化(SPSO, simple particle swarm optimization)算法，去掉了速度選項，SPSO的進化公式為

xt+1id=ωxtid+c1r1(pid-xtid)+c2r2(pgd-xtid)，

(7)

其中：xt+1id表示的是第t代第i個粒子的第d維分量；ω是慣性權重因子；c1和c2是學習因子常數(shù)；r1和r2是隨機數(shù)，服從U(0,1)；pid表示第i個粒子個體極值的第d維，而pgd表示全局最優(yōu)解的第d維分量。

在粒子群算法中，慣性權重是重要的參數(shù)之一。其主要功能是平衡整個粒子群的全局搜索能力和局部搜索能力，從而顯著的提高算法的整體收斂速度。而在標準SPSO算法中，ω是固定的數(shù)值，無法改變。當慣性權重較小時，如果最優(yōu)解在初始搜索空間中，則粒子群算法可以快速找到全局最優(yōu)解，反之則無法正確找到。而慣性權值較大時，粒子群算法更像是全局搜索算法，總會探索新的區(qū)域。這意味著需要更多的迭代來尋找全局最優(yōu)，并且更有可能在找不到最優(yōu)解同時算法的時間復雜度也會增加。因此，ω應該在算法的初期設置為較大值，在算法的后期設置為較小值。這樣設置的優(yōu)點在于：初始階段的全局尋優(yōu)能力會得到增強，有利于避免局部最優(yōu)；而在算法的后期，可增強算法在局部的搜索能力，同時提高算法收斂速度。因此，借鑒文獻[22]運用的一種線性遞減動態(tài)獲取慣性權重ω的方法，即

(8)

其中的參數(shù)取值為：ωini=0.9；ωend=0.4時效果較好。t=當前迭代次數(shù)，T=最大迭代次數(shù)。

特性選擇可看成0～1組合優(yōu)化問題，Kennedy[23]等最早提出了二進制粒子群優(yōu)化(BPSO, binary particle swarm optimization)算法將PSO算法擴展到了離散二進制空間，針對PSO在特征選擇應用很多都是建立在BPSO的基礎上的，但其缺點是離散的PSO喪失了一些連續(xù)PSO的特性。在此情況下，選擇在特征選擇過程中，將特征選擇問題轉換為一個向量，由(0,1)來表示。F=(fti1,fti2,…,ftid)，ftid等于1時，該維特征被選中，等于0時，則未被選中。設定一個閾值δ來判斷是否被選中，如公式(9)所示

(9)

δ是隨機數(shù)，取值范圍U(0.2,0.8)。根據(jù)公式(9)粒子的位置向量在連續(xù)空間域與離散問題域中完成特征向量轉換。

在標準的PSO算法中，假設初始種群中存在先驗近似最優(yōu)粒子，則可確定整體的搜索方向，這將大幅度地縮短WSPSO的進化時間。所以，需要對數(shù)據(jù)預處理，得到特征的重要性。Brieman[24]提出了一種確定特征重要性的方法，其主要思想是：每次選擇特征時，隨機替換特征的值，并記錄預測精度的變化，預測的準確性越高說明該特征的重要性越高。這里所提的特征重要性也就是對預測結果貢獻的百分比。因此可以得到占比最高的粒子，加入初始的種群。

2.1 WSPSO-SAMME.R-DT算法

給出基于封裝式特征選擇的WSPSO-SAMME.R-DT算法的具體步驟。其中DT代表基分類器決策樹。為了增加集成學習中基分類器間的多樣性，將隨機選擇決策樹中的最佳分割點。

算法2：WSPSO-SAMME.R-DT算法

輸入:訓練集{(xi,yi)|i=1,2,…,n}，最大迭代次數(shù)T，種群大小m。

1)初始化種群。依據(jù)特征重要性，選擇重要性最高的一個粒子作為初始粒子，剩余的m-1個粒子以隨機的方式生成。這m個粒子的各維分量都是U(0,1)的隨機數(shù)，將所有粒子進行組合，完成初始種群的構建;

2)判斷是否滿足條件t≤Tandpg的適應度小于1。若成立繼續(xù)下一步，不成立跳出循環(huán);

3)對于粒子i=1，2，…，m;

4)根據(jù)公式(9)將粒子xi轉化為特征向量，基于特征向量從訓練集中選取訓練子集。然后根據(jù)算法SAMME.R，訓練出一個強分類器H;

5)根據(jù)強分類器H得到的預測結果，計算每對類別組合的AUC，然后按照公式(6)計算AUCarea，作為xi粒子的適應度值;

6)根據(jù)得到的AUCarea的值來更新個體最優(yōu)pi和全局最優(yōu)pg;

7)根據(jù)公式(7)、(8)更新粒子位置;

8)根據(jù)公式(9)將pg轉化為特征向量;

輸出：最優(yōu)特征子集、強分類器H。

3 實驗仿真與分析

實驗機器配置為：Window7，內(nèi)存6 GB，CPU2.50 GHz，算法基于Python3.6.2實現(xiàn)。實驗所用的10組數(shù)據(jù)集來自KEEL官網(wǎng)與UCI數(shù)據(jù)集，數(shù)據(jù)都源于實際中的應用領域，表1給出具體信息。不均衡比IR(imbalance ratio)是最大多數(shù)類別的樣本數(shù)與最小少數(shù)類別的樣本數(shù)之比。學習因子c1=c2=2，經(jīng)實驗顯示，種群粒子數(shù)m=100時效果最佳，初始設置迭代次數(shù)T為300次，圖2給出了每代最優(yōu)個體適應度值的曲線，隨著迭代次數(shù)增加，可以看出迭代次數(shù)T=50時個體適應度值已趨于穩(wěn)定，所以最終選擇的迭代次數(shù)為T=50。

圖2 最優(yōu)個體適應度值的曲線Fig.2 Curve of optimal individual fitness value

實驗結果利用AUCarea以及另一個被廣泛應用的不平衡分類指標GM(G-Mean)[25]對算法進行評價。GM定義如下

(10)

其中TP,FP,FN,TN分別表示：小類正確分類的數(shù)量，預測為小類但是真實為大類，預測為大類但是真實為小類，大類正確分類的數(shù)量。

表1 數(shù)據(jù)集信息

文獻[6][7][15]各自提出了PUSBE、CS-MCS、BAK算法，與提出的WSPSO-SAMME.R-DT進行對比。采取一對一方法將PUSBE和CS-MCS擴充到多分類問題上，結果見表2、3。

表2 4種算法的AUCarea值對比

表3 四種算法的GM值對比

根據(jù)表2與表3可以得到如下結論：提出的算法WSPSO-SAMME.R-DT總體性能略優(yōu)于要其他3種算法，尤其是在New_thyroid、Wine與Zoo數(shù)據(jù)集上，AUCarea與GM的值都達到了100%。除了Contraceptive數(shù)據(jù)集外，在其他數(shù)據(jù)集上，WSPSO-SAMME.R-DT也略好于其他3種算法。其中CS-MCS在AUCarea上的平均值為0.832，比PUSBE的平均值低了2.1%；比BAK的平均值低了5.6%；比提出的WSPSO-SAMME.R-DT的平均值低了10.3%。而在GM值上CS-MCS的平均值為0.875，比PUSBE的平均值低了2.8%；比BAK的平均值低了2.4%；比提出的WSPSO-SAMME.R-DT的平均值低了5.3%。由此可看出算法總體性能相對較差，這是因為CS-MCS算法并沒有跟其他3種算法一樣采用特征選擇技術，這也證明了特征選擇可有效的應用于不均衡多分類的問題。

為了更直觀的對比4種算法的分類效果，圖3給出了4種算法AUCarea值的部分polar圖。根據(jù)圖3所示，圖中紅色虛線代表PUSBE；藍色虛線代表CS-MCS；黃色虛線代表BAK；青色虛線代表WSPSO-SAMME.R-DT。他們所圍成的面積就是其對應的AUCarea的值。從圖中可以看出WSPSO-SAMME.R-DT在Hayes-Roth與Balance數(shù)據(jù)集中面積最大，意味著在這兩種數(shù)據(jù)集下，WSPSO-SAMME.R-DT優(yōu)于其他3種算法，在Dermatology算法中排名第二，但是與該數(shù)據(jù)集下的最優(yōu)算法PUSBE所產(chǎn)生的面積相差不多。

圖3 4種算法的AUCarea極坐標圖示比較Fig.3 Comparison of AUCarea polar coordinates of four algorithms

4 結 語

結合特征選擇與集成學習方法提出了WSPSO-SAMME.R-DT算法，在10組不均衡數(shù)據(jù)集上對本算法進行實驗測試，實驗結果驗證了該算法的有效性。WSPSO-SAMME.R-DT使用了WSPSO算法并且以AUCarea作為適應度值，來優(yōu)化特征選擇。其中，AUCarea具可視化的優(yōu)點，并且對較差的AUC值更加敏感。筆者并沒有采用采樣技術對初始數(shù)據(jù)集進行數(shù)據(jù)層面的改進，避免了丟失重要信息、引入噪聲等情況。WSPSO-SAMME.R-DT可直接應用于多分類算法且并不需要進行拓展。