曹婷婷，張忠林

(蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070)

1 引言

不均衡數(shù)據(jù)大規(guī)模存在現(xiàn)實生活中且在許多領(lǐng)域有著重要應(yīng)用，如醫(yī)療健康診斷、信用欺詐和 入侵檢測[1 - 3]等。通常人們更加關(guān)注的是診斷異常或者錯誤的數(shù)據(jù)，對于不均衡數(shù)據(jù)分類問題，少數(shù)類的錯分代價相對較大，傳統(tǒng)的分類方法旨在最大化整體分類準確率，給研究帶來了一定的挑戰(zhàn)。

國內(nèi)外學(xué)者對不均衡數(shù)據(jù)分類問題的研究主要從數(shù)據(jù)層面和算法層面2個大的方面展開。數(shù)據(jù)層面主要以欠采樣、過采樣、人工合成采樣、混合采樣以及相應(yīng)的改進算法作為研究點，其主要思想是對數(shù)據(jù)分布進行重構(gòu)，使數(shù)據(jù)達到基本均衡狀態(tài)，如SMOTE(Synthetic Minority Oversampling TEchnique)[4]、Borderline-SMOTE[5]等。算法層面一般集中在集成學(xué)習(xí)、代價敏感學(xué)習(xí)CSL(Cost Sensitive Learning)[6]和元學(xué)習(xí)方面。集成學(xué)習(xí)主要包括Bagging、Boosting和Stacking算法。代價敏感學(xué)習(xí)CSL的基本思想是在非均衡數(shù)據(jù)分類中正確識別出少數(shù)類樣本的價值比正確識別出多數(shù)類樣本的價值要高，因此在分類中應(yīng)賦予樣本不同的損失代價。文獻[7]基于貝葉斯風(fēng)險最小化原理提出了一種可以將任意分類器算法轉(zhuǎn)化為代價敏感算法的 MetaCost算法，根據(jù)樣本屬于每個類的概率及誤分類代價之積選取分類代價最小的類別作為樣本分類結(jié)果，從而達到誤分代價最小。目前，學(xué)者們對一些傳統(tǒng)的分類算法，如支持向量機SVM(Support Vector Machine)、決策樹、神經(jīng)網(wǎng)絡(luò)和 AdaBoost 等提出了對應(yīng)的代價敏感算法[8 - 11]。王莉等人[12]在代價敏感的理論基礎(chǔ)上提出了NIBoost(New Imbalanced Boost) 算法，該算法結(jié)合NKSMOTE(New Kernel Synthetic Minority Over-sampling TEchnique)技術(shù)，根據(jù)分類錯誤率和預(yù)測的類標計算權(quán)重系數(shù)及各樣本新權(quán)重，使分類器在訓(xùn)練過程中更加關(guān)注被錯分的樣本。楊浩等人[13]提出了CSD-KNN(Cost Sensitive based on average Distance of K-Nearest Neighbor)算法，在降低決策邊界樣本密度的重采樣方法的基礎(chǔ)上，以每類樣本的平均距離作為分類結(jié)果的標準，使其符合貝葉斯決策理論從而具有代價敏感性，最后按不同的K值以整體誤分代價最小為原則進行Boosting集成，相較于傳統(tǒng)的KNN(K-Nearest Neighbor)算法，CSD-KNN算法平均誤分代價下降且代價敏感性能更好。Kotsiantis[14]提出了一種代價敏感的Stacking集成模型，用C4.5、KNN、樸素貝葉斯NB(Naive Bayes)作為分類器并將其用于不均衡數(shù)據(jù)分類。Cao 等人[15]將代價敏感的Logistic回歸作為元分類器，提出了IMCStacking(Inverse Mapping based Cost-sensitive Stacking learning)算法，并將快速有效的特征逆映射技術(shù)應(yīng)用于算法中，最大限度利用Stacking集成期間的交叉驗證過程。

綜上，不均衡數(shù)據(jù)分類中存在以下問題:(1)傳統(tǒng)的分類算法在實際應(yīng)用中賦予正類和負類相同的錯分代價；(2)集成算法的研究主要集中在Bagging與Boosting模型上，對Stacking集成算法的研究相對較少；(3)數(shù)據(jù)往往呈現(xiàn)非線性。針對以上問題，本文從代價敏感與Stacking集成的角度出發(fā)，提出了一種代價敏感的KPCA-Stacking(Kernel Principal Component Analysis-Stacking)算法，結(jié)合自適應(yīng)綜合采樣ADASYN(ADAptive SYNthetic sampling)方法，按照貝葉斯風(fēng)險最小化原理使Stacking集成中的初級分類器具有代價敏感性，同時KPCA能在高維度特征空間對核函數(shù)映射數(shù)據(jù)進行主成分分析，對數(shù)據(jù)進行降維，在特定條件下彌補了PCA算法線性不可分的不足。在KEEL公共數(shù)據(jù)集上進行了相關(guān)的實驗驗證，結(jié)果表明代價敏感的KPCA-Stacking算法取得了較好的分類效果，尤其是對少數(shù)類的識別。

2 ADASYN采樣

在SMOTE算法之后，He等人[16]提出了ADASYN自適應(yīng)綜合采樣方法。SMOTE算法作為一種插值法，對每個少數(shù)類樣本合成同數(shù)量的樣本，對插值區(qū)域未進行限定，可能會導(dǎo)致類別重疊和邊界混淆的問題。ADASYN方法可根據(jù)數(shù)據(jù)分布情況為不同的少數(shù)類樣本自適應(yīng)地生成不同數(shù)量的新樣本。按照一定的規(guī)則和機制，在比較難分類的區(qū)域合成更多的樣本，ADASYN具體步驟如算法1所示。

算法1ADASYN采樣

輸入:訓(xùn)練樣本集D={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi表示樣本,X={xi|xi∈Rn},yi∈Y={1,0}是標簽類，yi=1表示少數(shù)類，yi=0表示多數(shù)類，用ms和ml分別表示少數(shù)類和多數(shù)類樣本的數(shù)目，滿足ms≤ml且ms+ml=m。

輸出：采樣后新的訓(xùn)練集Dnew={(x′1,y1),(x′2,y2),…,(x′n,yn)}。

(1) 定義并計算類不平衡度d=ms/ml,d∈(0,1]。

(2) 生成的少數(shù)類樣本總量G為:

G=(ml-ms)×α

其中,α∈[0,1]表示加入新樣本后的不平衡度。當α=1時,G表示少數(shù)類與多數(shù)類的差值，即合成樣本后數(shù)據(jù)完全均衡。

(3) 對每個少數(shù)類樣本xi，利用歐氏距離找出其K近鄰并計算其比率Ri=Δ/K,i=1,2,…,m,Ri∈(0，1]，其中Δ是xi的K近鄰中屬于多數(shù)類的樣本數(shù)目。

(6) 根據(jù)以下步驟為每個少類樣本xi合成gi個樣本：

forj= 1:gi

從xi的K近鄰中隨機選擇一個少數(shù)類樣本xzi；

根據(jù)線性插值法合成樣本sj=xi+(xzi-xi)×λ，其中λ為隨機數(shù)，λ∈[0,1]；

end

3 代價敏感的KPCA-Stacking算法

3.1 Stacking算法思想

集成學(xué)習(xí)主要包括Bagging、Boosting和Stacking算法，Bagging和Boosting中基學(xué)習(xí)器一般為同種類型，而Stacking集成是異質(zhì)的，許多機器學(xué)習(xí)競賽比如Kaggle中較優(yōu)秀的解決方案建立在Stacking集成基礎(chǔ)上。Stacking集成算法框架如圖1所示，第1層個體基學(xué)習(xí)器稱為初級學(xué)習(xí)器，第2層用于結(jié)合的學(xué)習(xí)器稱為元學(xué)習(xí)器。Stacking先從初始訓(xùn)練集中基于各種不同的算法學(xué)習(xí)出初級學(xué)習(xí)器，每個初級學(xué)習(xí)器對原始樣本的預(yù)測標記組成新的數(shù)據(jù)集，將其作為元學(xué)習(xí)器的輸入特征來訓(xùn)練一個次級模型。為防止過擬合，使用K折交叉驗證，在構(gòu)建元學(xué)習(xí)器訓(xùn)練集的過程中，可得到測試集數(shù)據(jù)。

Figure 1 Framework of Stacking integrated algorithm

3.2 代價敏感Stacking算法

基于Staking算法的思想，本文針對現(xiàn)實生活中數(shù)據(jù)分布存在不均衡性提出了代價敏感的Stacking集成學(xué)習(xí)算法。選取K近鄰KNN、線性判別分析LDA(Linear Discriminant Analysis)、支持向量機SVM和隨機森林RF(Random Forest)分類器分別按照貝葉斯最小風(fēng)險化原理改進為代價敏感算法，使用一般最小化分類損失最小化分類錯誤率，代價敏感則以最小化分類代價為目標。最小風(fēng)險貝葉斯決策理論的主要策略是各種錯誤分類所造成的平均風(fēng)險最小,通過最小化后驗概率來進行分類決策，一般使用代價矩陣表示分類器的誤分類代價，以二分類為例，首先計算風(fēng)險，然后再進行決策。

計算風(fēng)險：

R(yi|x)=∑P(yi|x)Cost(yi,yj)

(1)

決策：

y= argminR(yi|x)

(2)

其中,R(yi|x)為樣本x分類到y(tǒng)i中的風(fēng)險構(gòu)造函數(shù)，P(yi|x) 為樣本x屬于類別yi的后驗概率，Cost(yi,yj)為類別yi誤分到類別yj的代價。

集成學(xué)習(xí)效果的好壞主要取決于基分類器的預(yù)測精度和基分類器之間的差異性，只有基分類器自身的分類準確率越高并且呈現(xiàn)多樣的趨勢，每個基學(xué)習(xí)器之間不出現(xiàn)強相關(guān)性，集成學(xué)習(xí)的效果才會越好。如果所有基學(xué)習(xí)器都產(chǎn)生了相同的預(yù)測結(jié)果，反而會增加建模的復(fù)雜性，所以我們希望不同的基學(xué)習(xí)器能夠“好而不同”[17]。

考慮到基分類器自身的預(yù)測能力，本文Stacking集成的初級學(xué)習(xí)器選擇自身精度較高且具有差異性的分類器。其中KNN通過測量不同特征值之間的距離進行分類，思想簡單，理論成熟。隨機森林作為Bagging集成框架的代表算法，精度高、抗過擬合能力強，在實際問題中應(yīng)用廣泛。SVM在高維非線性問題中表現(xiàn)突出。LDA雖常用作降維，但也可作為分類算法。對KNN、LDA、SVM、RF基分類器的性能與相關(guān)度分析將在4.3節(jié)展開。為了減輕過擬合，第2層分類器最好選擇較為簡單的模型，Stacking框架中邏輯回歸LR(Logistic Regression)或多響應(yīng)線性回歸MLR(Multi-response Linear Regression)被證明是比較好的方法[18]。本文以傳統(tǒng)統(tǒng)計學(xué)方法廣義線性模型GLM(Generalized Linear Model)中應(yīng)用最廣泛的LR作為Stacking集成的元學(xué)習(xí)器，LR模型基于概率學(xué)理論，模型清晰，簡單易操作且穩(wěn)定。因此，本文分別將KNN、NB、SVM、RF轉(zhuǎn)化成代價敏感的算法作為Stacking集成框架的初級學(xué)習(xí)器，選擇LR作為元學(xué)習(xí)器，以適用于解決不均衡數(shù)據(jù)分類問題。

3.3 代價敏感KPCA-Stacking算法

核主成分分析KPCA是非線性降維常用的方法之一，其基本思想是通過核技巧(非線性函數(shù)Φ)將m維線性不可分的原始輸入向量空間映射到線性可分的高維空間F，然后在F上進行PCA分析，將維度降到m′，且滿足m>m′，并利用核技巧簡化計算，因此具有很強的非線性處理能力。

Figure 2 Overall flow chart of cost-sensitive KPCA-Stacking algorithm

將KPCA加入到代價敏感的Stacking學(xué)習(xí)CSL-Stacking(Cost Sensitive Learning-Stacking)算法框架中，在數(shù)據(jù)輸入初級學(xué)習(xí)器之前，對數(shù)據(jù)特征進行KPCA分析并提取出有效非線性特征，進而提升學(xué)習(xí)器效果。本文KPCA中的核函數(shù)選取徑向基函數(shù)RBF(Radial Basis Function)，如式(3)所示：

k(x,xc)=exp(-γ‖x-xc‖2)

(3)

其中,γ=1/(2σ2),σ為徑向基函數(shù)的擴展常數(shù)。在使用KPCA提取特征之前對數(shù)據(jù)進行ADASYN采樣。代價敏感的KPCA-Stacking算法的具體步驟如算法2所示，算法整體框架如圖2所示。

算法2代價敏感的KPCA-Stacking算法

輸入：訓(xùn)練集D={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi∈X,yi∈Y={1,0}，迭代次數(shù)T。

輸出：代價敏感的Stacking集成分類器H(x)。

1.采用算法1進行ADASYN采樣;

2.用KPCA進行非線性特征映射，提取有效特征，更新訓(xùn)練集D′;

3.學(xué)習(xí)初級分類器;

4.fort=1 toTdo//迭代次數(shù)

5. 根據(jù)貝葉斯風(fēng)險最小化原理，將基分類器轉(zhuǎn)化為代價敏感分類器;

argminR(yi|x) = ∑P(yi|x)Cost(yi,yj)

6.在訓(xùn)練集D′上學(xué)習(xí)代價敏感的初級基分類器ht(xi);

7.endfor

8.構(gòu)建新的數(shù)據(jù)集;

9.fori=1 tomdo

10.D={(x′1,y1),(x′2,y2),…,(x′m,ym)}/*其中，x′i={h1(xi),h2(xi),…,hT(xi)}*/

11.endfor

12.學(xué)習(xí)元分類器;

13.在新的數(shù)據(jù)集Dnew上，學(xué)習(xí)元分類器Logistic Regression，訓(xùn)練的模型整體記為H(x)。

14.returnH(x);//組合分類器

4 實驗結(jié)果與分析

4.1 數(shù)據(jù)集

本文選擇類別不均衡的二分類KEEL公共數(shù)據(jù)集對提出的算法進行分析驗證，若數(shù)據(jù)集為多類別，則選取其中一種類別作為少數(shù)類，合并其他類別作為多數(shù)類，數(shù)據(jù)集的不平衡度IR(Maj/Min)為1.86～8.60，其中，Min和Maj分別為少數(shù)類樣本數(shù)目和多數(shù)類樣本數(shù)目。具體信息描述如表1所示。

4.2 評價指標

對于不均衡數(shù)據(jù)分類而言，準確率并不能提供有用的信息，意義并不大，因此選擇有效的評價指標是非常有必要的。不均衡數(shù)據(jù)分類模型的評價指標基于混淆矩陣，表2給出了二分類的混淆矩陣。

Table 1 Two-class unbalanced data sets

Table 2 Two-class confusion matrix

由于準確率已經(jīng)不再適用于不均衡數(shù)據(jù)集，本文選取F-measure、G-mean和AUC作為評價指標，其定義分別如式(4)～式(6)所示。

(4)

其中，查準率Precision=TP/(TP+FP)，召回率Recall=TP/(TP+FN),β一般取值為1，表示Precision和Recall所占比重相同。

(5)

其中，TPR=Recall=TP/(TP+FN),TNR=TN/(TN+FP)。

(6)

其中，F(xiàn)PR=FP/(FP+TN)。

G-mean指標可同時關(guān)注2個類上的性能，ROC曲線[19]將FPR作為x軸，TPR作為y軸，因此可以通過ROC曲線評價一個分類器好壞，ROC曲線越靠近左上角，面積越大，AUC值越大，則分類器的性能越好。

4.3 實驗結(jié)果及分析

在模型訓(xùn)練之前，對原始數(shù)據(jù)進行ADASYN過采樣，采樣前后數(shù)據(jù)分布如表3所示。

在數(shù)據(jù)集make_circles上進行PCA與KPCA分析對比，從圖3可以看出，在一個非線性可分的數(shù)據(jù)集上，經(jīng)過主成分分析之后，無論如何找到的最大方差的方向數(shù)據(jù)仍舊是線性不可分的。用基于徑向基函數(shù)(RBF)的主成分分析法，將數(shù)據(jù)集投影到經(jīng)變換后的特征PC1上可以實現(xiàn)線性劃分，此時只需要PC1一個特征，從而保證了樣本的最佳可分離性。

Table 3 Data distribution before and after ADASYN sampling

Figure 3 Comparison of the effects of PCA and KPCA on make_circles dataset

為了驗證KPCA能有效提取數(shù)據(jù)非線性特征，對KPCA-Stacking與Stacking集成框架的初級學(xué)習(xí)器進行實驗對比。圖4為KPCA-Stacking與Stacking集成框架在數(shù)據(jù)集Ecoli3上的ROC曲線。ROC曲線下的面積為AUC值，KPCA-Stacking與Stacking的AUC值分別為0.970和0.931。

Figure 4 Comparison of ROC curves between KPCA-Stacking and Stacking integrated algorithms

集成學(xué)習(xí)預(yù)測結(jié)果優(yōu)劣的2個決定性因素為基分類器的預(yù)測準確率與基分類器的多樣性，在3.2節(jié)已經(jīng)闡述。對于二分類問題，常見的分類器多樣性度量有不和度量(Disagreement Measure)、相關(guān)系數(shù)(Correlation Coefficient)、Q-統(tǒng)計量(Kappa-Statistic)和K-統(tǒng)計量(Kappa-Statistic)。本文選取相關(guān)系數(shù)作為度量標準。a和d為分類器Hi和Hj都正確和錯誤分類的樣本數(shù)目，c/d分別為分類器Hj/Hi正確分類而分類器Hi/Hj錯誤分類的樣本數(shù)目，可得到分類器Hi與Hj的預(yù)測結(jié)果聯(lián)立表，則相關(guān)系數(shù)ρij定義如式(7)所示。

(7)

相關(guān)系數(shù)越大，則個體學(xué)習(xí)器多樣性程度越小?，F(xiàn)在KEEL公共數(shù)據(jù)集上對用于組合學(xué)習(xí)的初級分類器的性能和相關(guān)性進行分析，以確保Stacking集成算法整體性能較優(yōu)，本文選取數(shù)據(jù)集wisconsin。

圖5使用點圖可視化了平均估計準確率和95%的置信區(qū)間，觀察可知均值以平均準確率降序排序，5個分類器均性能良好，可通過圖5觀察算法的重疊延展性。

Figure 5 Performance analysis of base classifier

表4給出了各算法之間相關(guān)性分析，可看到GBDT(Gradient Boosting Decision Tree)與RF呈現(xiàn)79.9%的較強相關(guān)性，且與LDA與KNN相關(guān)性也較強，分別為75.2%和76.9%。觀察圖5可知，GBDT與RF與SVM有一定重疊且GBDT比RF分類準確率稍低，因此將KNN、LDA、SVM和RF作為Stacking 集成的較佳組合，保證各算法之間未出現(xiàn)強相關(guān)性的同時降低整體算法時間復(fù)雜度，為模型集成提供可靠依據(jù)。

Table 4 Analysis of correlation between different algorithms

首先將代價敏感的Stacking學(xué)習(xí)算法CSL-Stacking與Stacking集成算法在未經(jīng)ADASYN過采樣的原始數(shù)據(jù)集上進行實驗，少數(shù)類樣本和多數(shù)類樣本在5個數(shù)據(jù)集上的召回率(Recall)與F-measure分別如表5和圖6所示，相較于Stacking集成學(xué)習(xí)算法，代價敏感的Stacking學(xué)習(xí)算法在少數(shù)類的識別準確率上有一定提升，證明其解決不均衡數(shù)據(jù)二分類問題時是有效的。

Table 5 Comparison of Recall values between CSL-Stacking and Stacking integration algorithms

Figure 6 Comparison of F-measure values between CSL-Stacking and Stacking integration algorithms

為了驗證代價敏感的KPCA-Stacking算法在不均衡數(shù)據(jù)分類上的有效性，將本文算法與其他10種算法進行對比，10種算法包括KNN、LDA、SVM、集成算法RF、C4.5、Bagging、Adaboost、梯度提升樹GBDT和文獻[12]所提出的具有代價敏感性的NIboost算法。其中，NIboost算法采用基于C4.5實現(xiàn)的決策樹(J48)和樸素貝葉斯NB作為Boosting集成的基分類器，分別記為NIboost1和NIboost2。實驗基于Jupyter Notebook和Weka平臺，所有實驗均采用5折交叉驗證，其他參數(shù)與文獻[12]均保持一致。分別選取F-measure、G-mean、AUC3個指標進行評價，實驗結(jié)果如表6～表8所示，其中AVG列表示該算法的結(jié)果在5個數(shù)據(jù)集上的均值。

分析表6～表8可知，當以G-mean作為評價指標時，文獻[12]的2種算法中基分類器為NB的NIBoost2取得的結(jié)果較好，在數(shù)據(jù)集wisconsin和pima上分別為0.977和0.735，本文代價敏感的KPCA-Stacking算法在數(shù)據(jù)集Ecoli1、Ecoli3和Yeast3上取得了最好結(jié)果，分別為0.912,0.937和0.967。以F-measure作為評價指標時，除了在wisconsin數(shù)據(jù)集上沒有取得最佳結(jié)果，在其他4個數(shù)據(jù)集上代價敏感的KPCA-Stacking算法均比NIBoost2效果佳。當以AUC作為評價指標時，代價敏感的KPCA-Stacking算法在數(shù)據(jù)集Ecoli1、Ecoli3和Yeast3上效果最好，相較于整體取得較好結(jié)果的NIBoost2算法，分別提升了9.8%，8.0%和12.5%，均值提升了6.72%。在wisconsin和pima數(shù)據(jù)集上KPCA-Stacking算法效果略微差于LDA。在3個評價指標上代價敏感的KPCA-Stacking算法均取得了最高均值，整體表現(xiàn)良好。

Table 6 Comparison of G-mean of different algorithms on five datasets

Table 7 Comparison of F-measure of different algorithms on five datasets

Table 8 Comparison of AUC of different algorithms on five datasets

綜合整體實驗分析可知，單分類器LDA、集成算法RF和GBDT取得了較好的結(jié)果，以NB為基分類器的NIBoost2算法效果優(yōu)于以J48為基分類器的NIBoost1算法，而代價敏感的KPCA- Stacking算法效果優(yōu)于大部分單個算法和部分集成算法的。因此在不均衡數(shù)據(jù)分類問題中，基于代價敏感的KPCA-Stacking算法是一種行之有效的方法，在后期研究中可作為一種參考。

5 結(jié)束語

本文基于代價敏感思想與KPCA提出了代價敏感的KPCA-Stacking集成算法，使其適用于不均衡數(shù)據(jù)分類問題。從算法層面入手，將代價敏感的KNN、LDA、SVM和RF作為初級學(xué)習(xí)器，進一步擴展了初級學(xué)習(xí)器的范圍，LR作為元學(xué)習(xí)器，2層架構(gòu)，KPCA能有效提取數(shù)據(jù)非線性特征，對數(shù)據(jù)進行降維。在公共數(shù)據(jù)集上與J48決策樹等10種算法進行了對比實驗，結(jié)果表明，代價敏感的KPCA-Stacking算法在少數(shù)類識別準確率上有一定提升，比單個模型的整體分類性能更優(yōu)，且Stacking模型使用多次交叉驗證算法較穩(wěn)健，為數(shù)據(jù)特征非線性與不均衡數(shù)據(jù)二分類問題提供了新的研究方向。

需要注意的是，本文通過KPCA非線性的方法提取主成分，所提取到的新特征物理意義是不明確的，若要單獨分析某一個或者某幾個因素或特征對分類結(jié)果的影響程度，代價敏感的KPCA- Stacking算法則不適用。在適用范圍內(nèi)進一步提升算法的性能并將其擴展到多分類；Stacking集成策略中尋找弱相關(guān)的初級學(xué)習(xí)器的組合方案；嘗試3層或者更深層的Stacking集成可作為下一步研究的方向。