基于代表的交叉驗(yàn)證分類(lèi)

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

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

0 引 言

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

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

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

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

1 理論基礎(chǔ)

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

1.1 基礎(chǔ)概念

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

S=(U,C,d)

(1)

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

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

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

(2)

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

(3)

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

(4)

定義5(有效代表集合) 待分類(lèi)樣本與距其最近的代表保持決策一致。與待分類(lèi)樣本擁有最小距離的所有代表所組成的集合稱(chēng)為有效代表集合。設(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個(gè)階段，分別對(duì)應(yīng)代表選舉和預(yù)測(cè)標(biāo)簽2個(gè)子算法。

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

代表選舉算法

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

輸出: 代表集合R。

1)R=φ;

2) 計(jì)算sim(x,y);

3) for(eachx∈U)do

5) end for

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

7) for(i=1 tok)do

8) whileX≠φdo

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

10)Ri=Ri∪{x};

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

12) end while

13)R=R∪Ri;

14) end for

15) returnR;

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

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

輸入:未分類(lèi)樣本x, 代表集合R。

輸出: 預(yù)測(cè)出的類(lèi)標(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í)通過(guò)均衡各分類(lèi)器的分類(lèi)偏好，以期獲得更好的分類(lèi)模型。集成學(xué)習(xí)認(rèn)為，對(duì)于某一分類(lèi)器的錯(cuò)誤預(yù)測(cè)，其他分類(lèi)器能夠?qū)ζ溥M(jìn)行糾正或者限制。常見(jiàn)的集成學(xué)習(xí)方法有Bagging[9]以及隨機(jī)森林法[10](random forest，RF)。

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

1.4 主動(dòng)學(xué)習(xí)

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

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

2 策略描述

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

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

2.1 集成策略1

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

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

圖1 ERC1框架

2.2 集成策略2

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

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

圖2 ERC2框架

2.3 集成策略3

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

圖3 ERC3框架

3 實(shí)驗(yàn)及結(jié)果分析

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

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

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

3.1 k-fold對(duì)比

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

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

圖4 不同k值對(duì)比

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

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

3.2 ERC與RCCNRS對(duì)比

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

表2 實(shí)驗(yàn)結(jié)果(Ⅰ)

表3 實(shí)驗(yàn)結(jié)果(Ⅱ)

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

在實(shí)驗(yàn)所用數(shù)據(jù)集上，和RCCNRS相比ERC1在4個(gè)數(shù)據(jù)集上的平均提升為0.72%，其中，在Chess和Kr-vs-kp數(shù)據(jù)集上分類(lèi)精度提升更明顯，分別是1.15%和1.20%；ERC2在4個(gè)數(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%。對(duì)于Mushroom和Voting這2個(gè)數(shù)據(jù)集，因?yàn)镽CCNRS算法原本分類(lèi)精度較高，所以提升幅度較小。其中，ERC1和ERC2在Mushroom上平均提升較少，都為0.25%。ERC3在Voting數(shù)據(jù)集上提升最少，平均提升為0.18%。

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

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

3.3 小 結(jié)

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

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

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