周爾昊 高 尚

（江蘇科技大學(xué) 鎮(zhèn)江 212001）

1 引言

近年來，分類器集成思想成為機(jī)器學(xué)習(xí)領(lǐng)域研究的一大熱點(diǎn)。其中的Bagging［1］和AdaBoost［2］算法是該領(lǐng)域具有代表性的集成策略。文獻(xiàn)［3］指出提高集成分類器的分類效果的方法基本從兩方面展開：一是提高基分類器之間的差異性，二是提高各個基分類器的分類精度。如文獻(xiàn)［4］中的ROFCO算法通過向訓(xùn)練集中加入差異性數(shù)據(jù)來減少基分類之間的相關(guān)性；再如文獻(xiàn)［5］中以多層感知機(jī)作為Bagging的基分類器，提高了基分類器分類精度，以得到更好的分類結(jié)果。目前，以各種決策樹（ID3、C4.5、CART）等作為基分類器的集成算法因其在分類問題上的良好表現(xiàn)，越來越受到集成研究者的重視。Rodriguez［6］等于2006年提出的一種新的集成算法——旋轉(zhuǎn)森林（ROF）算法，該算法以決策樹作為基分類器，通過特征變換增大基分類器之間的差異性，以獲得更好的集成效果。

隨著研究的深入，集成學(xué)習(xí)越來越多的被應(yīng)用于解決不平衡問題。不平衡數(shù)據(jù)分類問題是機(jī)器學(xué)習(xí)領(lǐng)域一大難題，日常生活中會在很多行業(yè)面臨此問題，比較常見的如電通行業(yè)中的欠費(fèi)預(yù)測、醫(yī)療行業(yè)中的病情診斷等［7］。然而，目前大多數(shù)機(jī)器學(xué)習(xí)分類算法并不能很好解決不平衡數(shù)據(jù)分類問題。代價敏感集成學(xué)習(xí)是一種不平衡數(shù)據(jù)分類方法，主要有三種實(shí)現(xiàn)方式，分別是：1）從學(xué)習(xí)模型出發(fā)，針對算法本身的改進(jìn)；2）從貝葉斯風(fēng)險理論出發(fā)；3）從預(yù)處理角度出發(fā)，將代價用于權(quán)重的調(diào)整，如AdaCost算法。

本文提出了一種代價敏感的旋轉(zhuǎn)森林算法（CROF），首先通過旋轉(zhuǎn)森林算法實(shí)現(xiàn)數(shù)據(jù)的預(yù)處理，然后以CART分類樹作為基分類器，在訓(xùn)練基分類器過程中引入誤分類代價，改變CART分類樹屬性分裂原則，得到代價敏感的CART分類樹，最后采用置信度這一指標(biāo)來確定樣本的最終類別。該方法不僅通過旋轉(zhuǎn)森林算法減少了基分類器之間的相關(guān)性，還通過引入誤分類代價提升了基分類器對于不平衡數(shù)據(jù)的分類能力。通過實(shí)驗對比分析，該方法能夠有效處理不平衡數(shù)據(jù)分類問題。

2 相關(guān)技術(shù)

2.1 代價敏感學(xué)習(xí)

代價敏感學(xué)習(xí)（CSL）最初來源于醫(yī)療診斷問題［8］。在醫(yī)療診斷過程中，將一位患者診斷為健康所付出的代價遠(yuǎn)大于將一位健康的人診斷為患者。在機(jī)器學(xué)習(xí)中，CSL指為不同類別賦予不同的權(quán)重，在訓(xùn)練過程中使機(jī)器更加“重視”那些擁有更高權(quán)重的類別，從而獲得理想的模型。這一思想更多地被運(yùn)用來解決不平衡數(shù)據(jù)分類問題，因為類別的分布不平衡，分類算法往往過度訓(xùn)練多數(shù)類而犧牲了少數(shù)類的分類精度。由于CSL是以最小化分類代價為目標(biāo)的［9］，所以通過賦予少數(shù)類更高的分類錯誤代價，使機(jī)器在分類過程中大大提高了模型對于少數(shù)類的分類精度，從而有效解決了不平衡數(shù)據(jù)的分類問題?？梢杂么鷥r矩陣表示分類器錯分時付出的代價［10］，設(shè)CL為少數(shù)類，CM為多數(shù)類。代價矩陣如表1所示。

表1 代價矩陣

其中，C（i，j）表示將j錯分為i的代價。

代價矩陣確定后，用貝葉斯構(gòu)建風(fēng)險函數(shù)，類別x被劃分為類別i的最小期望代價：

其中：p(j|x)表示把樣本x劃分為j類的后驗概率。

2.2 旋轉(zhuǎn)森林

旋轉(zhuǎn)森林（Rotation Forest）［11～14］于2006年 提出。該算法的核心是特征變換思想。先將屬性劃分為大小相等的K個不重疊子集，然后通過PCA、旋轉(zhuǎn)矩陣等變換方法獲得新的樣本數(shù)據(jù)。由此得到的各子樣本數(shù)據(jù)相互有所區(qū)別，從而提高了各基分類器的差異性和準(zhǔn)確性。

現(xiàn)設(shè)定F表示屬性集，D1，D2，…DL表示L個基分類器，用N×n的矩陣X表示有N條數(shù)據(jù)記錄的訓(xùn)練樣本集，n表示樣本特征數(shù)。模型構(gòu)建步驟如下。

1）將F隨機(jī)劃分為大小相等的K個子集，則每個子集約有M=n/K個屬性。

2）用Fij表示訓(xùn)練第i個分類器Di所使用的訓(xùn)練集的第j個子屬性集，對訓(xùn)練集進(jìn)行75%重采樣，產(chǎn)生一個樣本子集X’ij，通過主成分分析（PCA）對Fij中的子屬性進(jìn)行特征變換，得到Mj個主成分：，。

3）重復(fù)步驟2），得到K個子屬性集，將其主成分系數(shù)存入系數(shù)矩陣Ri：

根據(jù)原始屬性集排列順序重新旋轉(zhuǎn)矩陣Ri得，然后通過XRi’操作得到分類器Ci的訓(xùn)練集，在此訓(xùn)練集上訓(xùn)練基分類器Di，重復(fù)以上步驟L次得到L個基分類器。這里基分類器采用決策樹類型算法，因為其對特征的旋轉(zhuǎn)較敏感，得到的各個分類器有更大的差異性。

4）最終分類結(jié)果以最大置信度來決定，對于一個樣本x，用di,j(xR'C)表示用分類器Di預(yù)測x屬于c類可能性，label表示所有可能的類別，則x屬于c類的置信度為

由此可以通過式（3）判定x的最終類別：

3 代價敏感旋轉(zhuǎn)森林算法

傳統(tǒng)隨機(jī)森林算法在特征子空間構(gòu)造決策樹，降低了數(shù)據(jù)維度，本身適合處理高維數(shù)據(jù)，若向其中引入代價因子，可以同時處理高維不平衡數(shù)據(jù)［15］。但其在有噪音或樹數(shù)量設(shè)定不當(dāng)?shù)那闆r下存在過擬合問題。相比于傳統(tǒng)隨機(jī)森林算法，旋轉(zhuǎn)森林算法通過特征變換得到的各基分類器的差異性和準(zhǔn)確性都變大，在降低數(shù)據(jù)維度的同時也可以較好地避開過擬合問題，在此基礎(chǔ)上向基分類器引入代價因子得到代價敏感旋轉(zhuǎn)森林，相比于傳統(tǒng)的代價敏感方法以及現(xiàn)有的與隨機(jī)森林相結(jié)合的代價敏感方法，代價敏感旋轉(zhuǎn)森林算法可以更好地處理高維不平衡數(shù)據(jù)。

3.1 代價構(gòu)造

本文采用的代價敏感學(xué)習(xí)方法從學(xué)習(xí)模型出發(fā)，主要對決策樹算法進(jìn)行改進(jìn)，從分裂標(biāo)準(zhǔn)的選擇方面引入代價矩陣，使之能在不平衡數(shù)據(jù)集上有良好表現(xiàn)。

代價敏感旋轉(zhuǎn)森林算法的基分類器采用CART決策樹算法。在旋轉(zhuǎn)森林算法得到的新的訓(xùn)練樣本上構(gòu)造不剪枝的CART分類樹。CART決策樹的每個節(jié)點(diǎn)可選的分裂屬性為一固定數(shù)量M，且M≤F，F(xiàn)為樣本所有的特征數(shù)目，每次分裂從F中有放回的取M個屬性計算最佳分裂屬性。CART分類樹采用Gini指數(shù)來選擇劃分屬性及劃分點(diǎn)。Gini指數(shù)是一種不等性度量，又叫做“不純度”指標(biāo)，表示一個隨機(jī)選中的樣本在子集中被分錯的可能性。也就是說，當(dāng)一個節(jié)點(diǎn)中所有樣本都是一個類時，指數(shù)不純度為零；而當(dāng)節(jié)點(diǎn)類別分布均與時，指數(shù)應(yīng)該很大。Gini指數(shù)的定義如下：

其中p（t）表示節(jié)點(diǎn)t處少數(shù)類個體比例，1-p（t）表示多數(shù)類個體比例。

在CATR分類樹屬性分裂過程中，算法選擇下一個分裂節(jié)點(diǎn)的原則是使不純度下降最快的屬性，即使Gini指數(shù)變化量最大的屬性，其計算公式如下：

其中：q代表左邊節(jié)點(diǎn)的實(shí)例比例，1-q代表右邊節(jié)點(diǎn)的實(shí)例比例。現(xiàn)在向Gini指數(shù)計算中引入誤分類代價因子：

其中：Cij代表誤分類代價，為一固定數(shù)值，根據(jù)研究樣本實(shí)際分布決定。中分子，Π(j)為類別j的先驗值。分母。此時，不純度下降落差更新為

同樣地，選擇能使不純度變化量最大的節(jié)點(diǎn)作為最佳分裂屬性。

通過以上操作，成功的將懲罰代價Cij引入到了CART算法中，經(jīng)過修改的CART算法在每一次選擇新的屬性進(jìn)行分裂時都考慮到了實(shí)際樣本的不平衡性，由此得到的CART分類樹能夠更好地處理不平衡數(shù)據(jù)集。

3.2 算法步驟

1）根據(jù)實(shí)際樣本多數(shù)類與少數(shù)類比例計算誤法類代價C（CL，CM），C（CM，CL）；

2）運(yùn)用旋轉(zhuǎn)森林算法處理原始訓(xùn)練樣本集，得到D1，D2，…，DL個用于訓(xùn)練基分類器的新的數(shù)據(jù)集；

3）在D1上建立不剪枝的CART決策樹，引入誤分類代價，修改CART決策樹的屬性分裂計算方法；

4）重復(fù)步驟3），直到得到L個構(gòu)造完成的基分類器；

5）以最大置信度為標(biāo)準(zhǔn)輸出樣本的最終類別。

4 實(shí)驗及分析

4.1 實(shí)驗數(shù)據(jù)集、評價標(biāo)準(zhǔn)與參數(shù)設(shè)置

為驗證算法有效性，從UCI中選擇了五組數(shù)據(jù)集，由于CROF算法著重解決二分類的不平衡數(shù)據(jù)問題，故通過調(diào)整類別數(shù)使這五組數(shù)據(jù)呈現(xiàn)出二分類上的不平衡性。修改過后的數(shù)據(jù)集如表2所示。

表2 修改后的數(shù)據(jù)集

通常通過混合矩陣來衡量分類算法的性能，如表3所示。

表3 二分類混淆矩陣

本次實(shí)驗中，選取AUC值、真正例率（TPR）、f-度量（f-measure）來衡量算法性能。AUC值是一個比精度好得多的指標(biāo)，它可以反映多數(shù)類及少數(shù)類的平均分類情況，對于不平衡類別的分類問題，使用AUC進(jìn)行模型評估通常比使用精度更有意義。TPR度量的是少數(shù)類樣本中有多少被預(yù)測為少數(shù)類；f-measure是準(zhǔn)確率（PPV）和真正例率（TPR）的調(diào)和平均，由于同時考慮了準(zhǔn)確率和真正例率，所以它對于不平衡的二分類數(shù)據(jù)集來說是一種較好的度量。

對于誤分類代價Cij設(shè)置則根據(jù)所選取數(shù)據(jù)集實(shí)際情況而定，如clients數(shù)據(jù)集中，多數(shù)類與少數(shù)類比例為3.5，設(shè)CL為少數(shù)類，CM為多數(shù)類，若C（CL，CM）設(shè)為1，則C（CM，CL）應(yīng)設(shè)為3.5，以此體現(xiàn)若誤分少數(shù)類將帶來更大的懲罰。

4.2 實(shí)驗結(jié)果與分析

將CROF算法分別于CART決策樹算法、RF（隨機(jī)森林算法）、ROF（旋轉(zhuǎn)森林算法）進(jìn)行比較。四種算法的AUC值如圖1所示。

圖1 CATR，RF，ROF，CROF的AUC值比較

從圖1中可以看出，以集成為基礎(chǔ)的RF算法相較于普通的CART決策樹算法可以一定程度上緩解過擬合問題，但其對于少數(shù)類的分類不敏感，AUC值表現(xiàn)一般。ROF算法通過特征變換，在避開過擬合的同時其分類器的準(zhǔn)確性有所提升，對比RF算法AUC值有了提升。而CROF算法在此之上通過引入代價因子，能夠處理高維不平衡數(shù)據(jù)，其AUC值比之ROF算法又有了進(jìn)一步提升。這說明CROF算法對多數(shù)類及少數(shù)類的分類均有良好表現(xiàn)。

由于算法著重于解決不平衡數(shù)據(jù)的分類問題，所以對于少數(shù)類的分類精度有著更高的要求。表4、表5分別是四種算法在各數(shù)據(jù)集上的TPR和f-measure的平均值，圖2、圖3則是對表格數(shù)據(jù)的直觀反映。

表4 四種算法下各數(shù)據(jù)集的TPR值

表5 四種算法下各數(shù)據(jù)集的f-measure值

圖2 各數(shù)據(jù)集下四種算法TPR比較

圖3 四種算法下各數(shù)據(jù)集f-measure比較

從圖表中可以看出，CROF算法對于數(shù)據(jù)集中少數(shù)類的分類精度優(yōu)于其他三種算法，在AUC值較其他方法略有提升的基礎(chǔ)上，CROF算法對于少數(shù)類的分類準(zhǔn)確率有較大提升。以上實(shí)驗說明CROF算法可以更好地處理不平衡數(shù)據(jù)。

5 結(jié)語

傳統(tǒng)算法處理不平衡問題時往往基于類別平衡的假設(shè)，當(dāng)應(yīng)用于不平衡數(shù)據(jù)時性能并不理想［16］。CROF算法利用集成思想，通過ROF模型實(shí)現(xiàn)了數(shù)據(jù)的預(yù)處理，向CART算法中引入誤分類代價，改變了CART屬性分裂計算規(guī)則，使得分類器不僅多樣性與準(zhǔn)確性均得到改進(jìn)，而且能有效處理不平衡數(shù)據(jù)問題，進(jìn)而提高集成后的分類器分類性能。提出的CROF算法與傳統(tǒng)算法相比有更好的AUC、TPR及f-measure值。說明該算法在不平衡問題上是有效的。