王 軒，顧 峰，閔 帆，孫遠(yuǎn)秋

(1.西南石油大學(xué) 網(wǎng)絡(luò)與信息化中心，成都 610500；2.西南石油大學(xué) 計算機科學(xué)學(xué)院，成都 610500；3.西南石油大學(xué) 人工智能研究院，成都 610500)

0 引 言

分類是機器學(xué)習(xí)的重要研究課題之一。近年來，分類技術(shù)在眾多領(lǐng)域得到廣泛應(yīng)用。Zhang等[1]在2015年提出了基于代表的鄰域粗糙集覆蓋分類算法(representative-based classification through covering-based neighborhood rough sets, RCCNRS)，自算法提出以來，劉福倫[2]結(jié)合6種相似度計算方式，研究了相似度對算法的分類影響；結(jié)合代價敏感[3]和主動學(xué)習(xí)[4]的研究，使算法分類性能得到提升，更貼近實際應(yīng)用。本文的前期工作對算法的5種標(biāo)簽預(yù)測策略進(jìn)行了對比。

在分類問題上，RCCNRS算法能取得較高的分類精度。然而，在監(jiān)督式學(xué)習(xí)中，訓(xùn)練樣本的不同，或直接影響分類結(jié)果，或通過構(gòu)建過擬合/欠擬合的分類模型間接影響分類結(jié)果。比如，對于RCCNRS算法而言，訓(xùn)練集分割時導(dǎo)致的數(shù)據(jù)類別不平衡可能會導(dǎo)致數(shù)據(jù)集的觀測幾率發(fā)生變化，進(jìn)而影響對未分類樣本的分類，影響算法最終的分類精度。

單個分類通常存在分類偏好，對此，集成學(xué)習(xí)[5-6]的概念被提出。集成學(xué)習(xí)通過結(jié)合多個分類器，組成多分類器系統(tǒng)來完成學(xué)習(xí)任務(wù)，通過均衡各分類器的分類偏好，往往能取得較滿意的性能。集成學(xué)習(xí)有同質(zhì)集成和異質(zhì)集成2種策略。同質(zhì)集成策略，指參與集成的“基分類器”是同種類型但擁有不同參數(shù)的個體分類器；異質(zhì)集成策略，指參與集成的“組件分類器”由不同的算法生成。

針對上述情況，結(jié)合集成學(xué)習(xí)，本文提出基于k-fold交叉驗證[7]的3種策略。提出3種集成策略以期限制數(shù)據(jù)類別不平衡對RCCNRS分類精度的影響，提高分類器的性能。實驗在UCI[8]的Chess, Kr-vs-kp, Mushroom, Voting 4個標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行。

1 理論基礎(chǔ)

本文的研究在于提升基于代表的粗糙集覆蓋分類算法的分類性能。

1.1 基礎(chǔ)概念

定義1(決策信息系統(tǒng)) 決策信息系統(tǒng)S為一個三元組，定義為

S=(U,C,d)

(1)

(1)式中：U是整個論域；C表示條件屬性集合；d表示決策屬性。

定義2(鄰域) 任意x∈U，設(shè)置相似度閾值θ，θ∈(0,1]，那么定義樣本的鄰域為

n(x,θ)={y∈U|sim(x,y)≥θ}

(2)

(2)式中，sim(x,y)表示樣本x，y之間的相似度。

(3)

定義4(距離) 設(shè)x是待分類樣本，它與代表r之間的距離定義為

(4)

定義5(有效代表集合) 待分類樣本與距其最近的代表保持決策一致。與待分類樣本擁有最小距離的所有代表所組成的集合稱為有效代表集合。設(shè)選出的代表集合為R，有效代表集合記為

E={r∈R|distance(x,r)=mindis(x,R)}

(5)

(5)式中，

mindis(x,R)=min{distance(x,r)|r∈R}

(6)

1.2 RCCNRS算法

本文的研究基于RCCNRS算法。RCCNRS算法主要分為2個階段，分別對應(yīng)代表選舉和預(yù)測標(biāo)簽2個子算法。

代表選舉算法的目的是選出具有代表性的樣本。被選出的樣本將作為代表，對接下來所有的待分類樣本進(jìn)行分類。算法的偽代碼如下。

代表選舉算法

輸入:S={U,C,d}。

輸出: 代表集合R。

1)R=φ;

2) 計算sim(x,y);

3) for(eachx∈U)do

5) end for

6)U/tf553bt={X1,X2,…,Xk};

7) for(i=1 tok)do

8) whileX≠φdo

9) 選擇其鄰域?qū)Ξ?dāng)前論域覆蓋最多的x;

10)Ri=Ri∪{x};

11)X中去除r對應(yīng)的鄰域;

12) end while

13)R=R∪Ri;

14) end for

15) returnR;

標(biāo)簽預(yù)測算法根據(jù)代表選舉階段選出的代表進(jìn)行分類。最基本的原則是有效代表集合決定其類別標(biāo)簽。算法偽代碼如下。

預(yù)測標(biāo)簽算法

輸入:未分類樣本x, 代表集合R。

輸出: 預(yù)測出的類標(biāo)簽d′(x)。

1)E=φ;mindis=MAX_VALUE;

2) for(eachr∈R)do

3) Computedistance(x,r);

4) if(distance(x,r)

5)mindis=distance(x,r);

6)E={r};

7) else then

8)E=E∪{r};

9) end if

10) end for

11) 根據(jù)E得到d′(x)并輸出;

1.3 集成學(xué)習(xí)

集成學(xué)習(xí)通過均衡各分類器的分類偏好，以期獲得更好的分類模型。集成學(xué)習(xí)認(rèn)為，對于某一分類器的錯誤預(yù)測，其他分類器能夠?qū)ζ溥M(jìn)行糾正或者限制。常見的集成學(xué)習(xí)方法有Bagging[9]以及隨機森林法[10](random forest，RF)。

針對單一分類器存在分類偏好的特點，集成學(xué)習(xí)的概念被提出。集成學(xué)習(xí)有同質(zhì)集成和異質(zhì)集成2種策略。同質(zhì)集成策略，指參與集成的“基分類器”是同種類型但擁有不同參數(shù)的個體分類器；異質(zhì)集成策略，指參與集成的“組件分類器”由不同的算法生成。本文算法采用同質(zhì)集成策略。

1.4 主動學(xué)習(xí)

使用傳統(tǒng)監(jiān)督學(xué)習(xí)方法分類時，訓(xùn)練集樣本越多分布越均勻，分類效果往往越好。在許多實際應(yīng)用場景中，標(biāo)記樣本代價往往較高，且被標(biāo)記的樣本較少。主動學(xué)習(xí)提供了使用較少的訓(xùn)練樣本，獲得性能較好的分類器的方法。

主動學(xué)習(xí)使用已標(biāo)記樣本，以不確定性和差異性為準(zhǔn)則，輔以定制化的策略，甄別當(dāng)前最有價值的未標(biāo)記樣本。交由專家標(biāo)記后，補充進(jìn)訓(xùn)練集，然后重新構(gòu)建分類器。如此迭代，通過交互式學(xué)習(xí)不斷提高分類器的健壯性，直至觸發(fā)終止條件。

2 策略描述

k-fold交叉驗證的基本思想是將原始訓(xùn)練集分成k份，輪流將其中的1份作為測試集,其余作為訓(xùn)練集。以此類推，可以得到k個子分類器。以此進(jìn)行交叉驗證，達(dá)到減少隨機誤差的效果。

本節(jié)將詳細(xì)介紹本文提出的3種交叉驗證策略。集成策略1旨在依靠交叉驗證提高RCCNRS算法分類精度，簡稱ERC1；集成策略2去除分類精度低的基分類器再進(jìn)行集成，簡稱ERC2；集成策略3借鑒主動學(xué)習(xí)的思想以擴充訓(xùn)練集規(guī)模，來提高分類模型性能，簡稱ERC3。

2.1 集成策略1

ERC1的集成思想是采用委員會投票(query by committee, QBC)決定待分類樣本標(biāo)簽。采用k-fold得到的k個子分類器作為同質(zhì)QBC成員。ERC1是利用交叉驗證的方法，限制類別不平衡對RCCNRS算法分類精度的影響。

ERC1的基本框架如圖1。原始訓(xùn)練集Tr被分成k份，對應(yīng)訓(xùn)練成k個子分類器。k個子分類器一起組成委員會，委員會通過投票對原始測試集Te進(jìn)行標(biāo)簽預(yù)測。樣本全部獲得預(yù)測標(biāo)簽后，驗證得出算法最終精度。

圖1 ERC1框架

2.2 集成策略2

ERC2在ERC1的基礎(chǔ)上對QBC成員進(jìn)行了篩選。區(qū)別在于，對每一個子分類器，判斷其分類精度是否大于原始的RCCNRS算法。如果大于原始算法分類精度，則子分類器成為QBC成員，否則無權(quán)成為QBC成員。最終由QBC成員對所有待分類樣本進(jìn)行分類，結(jié)果由其投票決定。

ERC2的基本框架如圖2。采用k-fold訓(xùn)練子分類器的部分同ERC1，圖2未重復(fù)展現(xiàn)。委員會中包含分類精度大于RCCNRS分類器的子分類器以及原始RCCNRS分類器。測試集中的待分類樣本標(biāo)簽，由委員會投票決定。特殊情況下，當(dāng)子分類器分類精度都小于原始RCCNRS分類器，則仍用原RCCNRS分類器進(jìn)行分類。

圖2 ERC2框架

2.3 集成策略3

在ERC1，ERC2的基礎(chǔ)上，受到主動學(xué)習(xí)的啟發(fā)提出ERC3對訓(xùn)練集擴容。ERC3認(rèn)為所有子分類器決策一致的樣本適合采用RCCNRS進(jìn)行標(biāo)簽預(yù)測。經(jīng)過委員會分類后，無條件相信其分類是正確的，用這種方式擴展訓(xùn)練集。具體方法是對原始測試集用QBC進(jìn)行預(yù)分類，將決策一致的樣本加入到原始訓(xùn)練集，組成新的訓(xùn)練集。利用新的訓(xùn)練集構(gòu)建RCCNRS分類器，再對原始測試集分類。相比RCCNRS算法，ERC3主動學(xué)習(xí)自身認(rèn)為分類正確的樣本。

圖3 ERC3框架

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

本小節(jié)將展示所用數(shù)據(jù)集上的實驗結(jié)果，并進(jìn)行分析。實驗先進(jìn)行了k-fold交叉驗證，對比不同k值下3種策略的效果，以期尋找出最優(yōu)的k取值。接著，取實驗效果好的k值，將本文提出的3種策略和RCCNRS算法作對比。本文僅研究了二分類問題，實驗所用數(shù)據(jù)集如表1。

表1 數(shù)據(jù)集描述

每個數(shù)據(jù)集上共進(jìn)行10組實驗，每組實驗重復(fù)100次，得出分類精度后取平均值，以減小實驗誤差。對于Chess，Kr-vs-kp，Mushroom這3個較大數(shù)據(jù)集，第1組實驗取數(shù)據(jù)集的0.01作為訓(xùn)練集，以后每組實驗訓(xùn)練集規(guī)模遞增數(shù)據(jù)集的0.01。對于較小數(shù)據(jù)集Voting，第1組實驗取數(shù)據(jù)集的0.05作為訓(xùn)練集，以后每組實驗訓(xùn)練集規(guī)模遞增數(shù)據(jù)集的0.05。

3.1 k-fold對比

對于k-fold交叉驗證，k取值不同時，對實驗結(jié)果影響不同。該部分對k-fold交叉驗證的k取值做了實驗對比，以期找到本文提出的3種策略的最佳交叉驗證k值。

當(dāng)k取1時沒有研究意義，因此，實驗中設(shè)置k∈{2,3,4,5,6,7,8,9,10}。每一個k值分別在4個數(shù)據(jù)集上進(jìn)行實驗。不同k值對比如圖4。其中，圖4a—圖4d分別表示在Chess，Kr-vs-kp，Mushroom，Voting等4個數(shù)據(jù)集上的實驗結(jié)果，橫軸表示k的取值，縱軸表示此時方法對RCCNRS精度提升的平均值。

圖4 不同k值對比

根據(jù)本文實驗結(jié)果，在所用的4個數(shù)據(jù)集上，3種改進(jìn)策略基本上都是在k=5時取得最好的提升效果。只有ERC3在Mushroom和Voting數(shù)據(jù)集上，是k值取10時獲得最好的改進(jìn)效果。當(dāng)k值取2時，對RCCNRS算法的性能提升是負(fù)值。ERC1和ERC2受k取值影響相對較大。當(dāng)k取5時，取得最好的改進(jìn)效果。ERC3受k取值影響較小，對于RCCNRS算法的分類性能提升基本穩(wěn)定。隨著k值增大，有少量提升。ERC3主要受原始算法分類精度影響。主動學(xué)習(xí)的過程中，被學(xué)習(xí)到的樣本標(biāo)簽的準(zhǔn)確程度取決于原始算法的分類精度。所以，如果原始算法分類精度高，ERC3對性能提升相對更有效。

4個數(shù)據(jù)集上的實驗結(jié)果顯示，當(dāng)k取2時，3種策略對RCCNRS算法的性能沒有提升，反而有下降。這是當(dāng)k取2時，交叉驗證的優(yōu)勢尚未體現(xiàn)。并且在交叉驗證時，子訓(xùn)練集是原始訓(xùn)練集的一半，即不僅沒有通過集成消除分類偏好還減少了訓(xùn)練樣本。此時子訓(xùn)練集對應(yīng)分類器的精度下降幅度大，大于交叉驗證3種策略對原始算法分類精度的提升幅度。

3.2 ERC與RCCNRS對比

各個數(shù)據(jù)集在不同數(shù)據(jù)切割比例下的實驗結(jié)果分別如表2和表3。表2和表3中，同一訓(xùn)練集規(guī)模下，分類精度最高的結(jié)果由下劃線標(biāo)出。

表2 實驗結(jié)果(Ⅰ)

表3 實驗結(jié)果(Ⅱ)

從實驗結(jié)果來看，由于訓(xùn)練集分割存在隨機性，每次實驗結(jié)果不一定完全相同，但3種改進(jìn)策略，對RCCNRS算法分類精度都有一定的提升。其中，ERC1相對表現(xiàn)更好，但是當(dāng)RCCNRS原本分類精度就比較高時，ERC3表現(xiàn)更好。比如ERC3在Mushroom和Voting數(shù)據(jù)集上，分類精度提升較另外2個數(shù)據(jù)集上效果更好。

在實驗所用數(shù)據(jù)集上，和RCCNRS相比ERC1在4個數(shù)據(jù)集上的平均提升為0.72%，其中，在Chess和Kr-vs-kp數(shù)據(jù)集上分類精度提升更明顯，分別是1.15%和1.20%；ERC2在4個數(shù)據(jù)集上平均提升為0.71%，在Chess和Kr-vs-kp數(shù)據(jù)集上的平均提升明顯，分別為1.44%和1.60%；ERC3平均提升0.30%，同樣，在Chess和Kr-vs-kp數(shù)據(jù)集上平均提升較明顯，分別為0.58%和0.69%。對于Mushroom和Voting這2個數(shù)據(jù)集，因為RCCNRS算法原本分類精度較高，所以提升幅度較小。其中，ERC1和ERC2在Mushroom上平均提升較少，都為0.25%。ERC3在Voting數(shù)據(jù)集上提升最少，平均提升為0.18%。

在實驗所用4個數(shù)據(jù)集上，ERC1對分類精度提升更明顯；其次是ERC2和ERC1的分類精度相差不大；ERC3在Mushroom數(shù)據(jù)集上表現(xiàn)良好，即使RCCNRS算法分類精度達(dá)到98%時，也能對原始算法精度提升約0.5個百分點。

總體來說，本文提出的3種改進(jìn)策略，對于RCCNRS算法分類精度較低的數(shù)據(jù)集，適宜采用ERC1和ERC2中的一種進(jìn)行改進(jìn)。對于RCCNRS原本分類精度就較高的數(shù)據(jù)集，宜采用ERC3對算法進(jìn)行改進(jìn)。根據(jù)本文實驗數(shù)據(jù)，分類精度較高的標(biāo)準(zhǔn)應(yīng)超過90%。ERC1和ERC2分類精度相差不大，優(yōu)先考慮選擇ERC1。對于大數(shù)據(jù)集，不過分要求精度的時候，建議ERC2。因為ERC2中，QBC中基分類器更少，算法復(fù)雜度更低。所以對于不同數(shù)據(jù)集，應(yīng)該選擇其相適應(yīng)的改進(jìn)策略。

3.3 小 結(jié)

針對RCCNRS算法分類精度受訓(xùn)練數(shù)據(jù)類別不平衡影響的問題，本文提出3種改進(jìn)策略?？傮w來說，通過實驗驗證和分析得出如下結(jié)論：①對于RCCNRS算法，本文提出的3種k-fold交叉驗證策略，當(dāng)k取5時往往取得較好的分類性能提升。另外，ERC1和ERC2受k取值影響較大；ERC3受其影響較小，且ERC3隨k值增加改進(jìn)效果有微弱的提升；②對于RCCNRS算法分類精度較高的數(shù)據(jù)集，應(yīng)選擇ERC3。根據(jù)本文實驗結(jié)果，分類精度應(yīng)高于90%。對于RCCNRS原本分類精度低的數(shù)據(jù)集，應(yīng)選擇ERC1和ERC2中的一種。

4 結(jié)論及進(jìn)一步工作

本文提出的3種交叉驗證策略，對RCCNRS的分類精度有一定的提升。3種交叉驗證策略，同樣可以用來研究其他的經(jīng)典分類算法。其中，ERC3也可以研究數(shù)據(jù)集中特殊樣本的選擇和刪除。在接下來的工作中，將結(jié)合屬性加權(quán)[11]、三支決策[12-13]等對ERC3做進(jìn)一步研究，研究ERC3如何有效篩選特殊樣本。