王 軒,張 林,高 磊,蔣昊坤

(西南石油大學(xué) 計算機(jī)科學(xué)學(xué)院, 成都 610500)(*通信作者電子郵箱linzhang8080@163.com)

0 引言

分類是機(jī)器學(xué)習(xí)[1]的一個基本問題。1982年P(guān)awlak提出了粗糙集理論[2],進(jìn)而衍生出了覆蓋粗糙集[3-4]和鄰域粗糙集[5]。在覆蓋粗糙集的理論基礎(chǔ)上,Zhang等[6]提出了基于代表的粗糙集覆蓋分類算法——RBC-CBNRS(Representative-Based Classification through Covering-Based Neighborhood Rough Set)。

RBC-CBNRS算法對于分類問題已經(jīng)能取得較高的分類精度,在某些分類問題上分類精度超過ID3[7]、J48[8]等經(jīng)典分類算法。然而,RBC-CBNRS算法在模型構(gòu)建過程中,受訓(xùn)練集抽樣不均勻影響,導(dǎo)致某些正常對象成為離群對象或邊界對象。而這些離群對象會影響代表的選舉過程,進(jìn)而影響最終分類結(jié)果;或者有可能成為代表,直接導(dǎo)致周圍對象都分類錯誤。

集成學(xué)習(xí)[9]通過結(jié)合多個學(xué)習(xí)器來完成學(xué)習(xí)任務(wù),通常能取得更優(yōu)越的性能。受集成學(xué)習(xí)思想的啟發(fā),為限制離群對象或邊界對象對RBC-CBNRS算法分類精度的影響,本文提出了一種留一法集成學(xué)習(xí)算法——LOOELCA (Leave-One-Out Ensemble Learning Classification Algorithm)。LOOELCA以RBC-CBNRS算法為基分類算法,采用留一法[10]構(gòu)造一系列同質(zhì)基分類器,對離群對象與對應(yīng)的基分類器進(jìn)行標(biāo)記。這些被標(biāo)記的基分類器和基于全集的RBC-CBNRS分類器共同構(gòu)成委員會,并對未分類對象進(jìn)行標(biāo)簽預(yù)測。如委員會表決一致,則直接給該未分類對象貼上類標(biāo)簽;否則,基于k最近鄰(k-Nearest Neighbor, kNN)算法并利用標(biāo)注對象對未分類對象分類。

實驗在UCI的dermatology、zoo、wdbc、ionosphere、wine、 penbased、tic-tac-toe、sonar、mushroom等9個數(shù)據(jù)集上進(jìn)行,測試了LOOELCA在不同訓(xùn)練集規(guī)模下的分類精度。實驗結(jié)果表明,LOOELCA較RBC-CBNRS算法分類精度有提升,且與ID3、J48、Na?ve Bayes[11]、OneR[12]等經(jīng)典的分類算法相比,通常能得到更高的分類精度。

1 相關(guān)工作

本文的基本數(shù)據(jù)模型為決策信息系統(tǒng),涉及到覆蓋粗糙集和鄰域粗糙集等相關(guān)概念。

1.1 決策信息系統(tǒng)

定義1 決策信息系統(tǒng)[13]。決策信息系統(tǒng)S為一個五元組,定義為:

S=(U,C,d,V,I)

(1)

其中:U是整個論域;C表示條件屬性集合;d表示決策屬性；V={Va|a∈C∪d}是屬性值域集合;I={Ia|a∈C∪d}表示U→Va的信息函數(shù)。表1是一個決策信息系統(tǒng)。本文只討論單決策的名詞型決策信息系統(tǒng)。

表1 決策信息系統(tǒng)示例Tab. 1 Examples of decision system

定義2 相似度。任意x,y∈U在A?C中的相似度記為:

sim(x,y,A)=sam(x,y,A)/|A|

(2)

其中:

sam(x,y,A)=|{a∈A|a(x)=a(y)}|

(3)

因為本文選擇對象的全部屬性,即A=C,因此可用sim(x,y)表示sim(x,y,A)。本文采用overlap算法計算對象之間相似度。根據(jù)定義2,由表1的決策信息系統(tǒng)可計算出sim(x1,x6)=5/6。同理可計算出各對象之間的相似度。

1.2 鄰域

定義3 鄰域。任意x∈S,設(shè)置相似度閾值θ(θ∈(0,1]),那么定義對象的鄰域為:

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

(4)

相似度閾值θ指的是作為對象的鄰居所要滿足的最小相似度值。根據(jù)定義2, 相似度閾值取值范圍為{1/|C|,2/|C|,…,1}。如設(shè)定的相似度閾值介于兩個有效相似度之間,相似度閾值向上取值。例如,根據(jù)表1給出的決策信息系統(tǒng)C=6,如設(shè)定相似度閾值為3/7,此時2/6<3/7<3/6,那么相似度閾值取3/6。相似度閾值設(shè)置得越小,對象的鄰域越大;反之,對象的鄰域越小。結(jié)合表1并根據(jù)式(2)、(4)可知,n(x1, 4/6)={x1,x2,x4,x6,x11},n(x1, 5/6)={x1,x6,x11}。

定義4 最小相似度閾值。給定決策信息系統(tǒng)S=(U,C,d,V,I),d={1,2,…,k},U/ zr55j5v={X1,X2, …,Xk},那么任意x∈Xi的最小相似度閾值θ+定義如下:

θx+=min{0<θ≤1|n(x,θ)?Xi}

(5)

θx+由對象x和決策信息系統(tǒng)S共同決定。具體示例如圖1所示。

定義5 最大鄰域。最小相似度閾值對應(yīng)的鄰域就是最大鄰域;對于任意x∈S的最大鄰域可記為:

n*(x)=n(x,θx+)

(6)

最大鄰域就是在決策一致的情況下,覆蓋對象最多的鄰域。

圖1 n*(x1)的定義示例Fig. 1 Example of n*(x1)

2 問題描述及LOOELCA

本章首先介紹LOOELCA的基算法RBC-CBNRS算法,并對RBC-CBNRS算法進(jìn)行時間復(fù)雜度分析;接著介紹集成學(xué)習(xí)策略的框架和過程,并對LOOELCA進(jìn)行算法分析。

2.1 問題描述

受抽樣不均勻的影響,部分正常對象可能會成為邊界對象或者離群對象,這些點會影響代表選擇的過程。例如,這類對象會影響其他點的鄰域圈定過程，還有可能成為有效代表，這樣會影響RBC-CBNRS算法的分類精度。因此,離群對象或邊界對象對應(yīng)的分類器具有研究價值。

2.2 基于代表選舉的分類算法

本文的LOOELCA的基算法是RBC-CBNRS算法。RBC-CBNRS算法分為兩個子算法,分別是代表生成算法和標(biāo)簽預(yù)測算法。

2.2.1 代表生成算法

這個階段主要選舉出能夠作為代表的對象,并將代表保存下來。下面給出代表選舉過程的偽代碼。

輸入 決策信息系統(tǒng)DS={U,C,r5lzpzh,V,I}。

輸出 代表集合R及相似度閾值集合T。

1)

R=?,T=?;

2)

根據(jù)式(2)計算sim(x,y), 其中(x,y)∈(U×U);

3)

for (eachx∈U) do

4)

計算θx+;

5)

計算n*(x);

6)

end for

7)

計算正域U/d={X1,X2, …,Xk};

8)

for (i=1 tok) do

9)

X=Xi;

10)

whileX≠? do

11)

選擇當(dāng)前覆蓋對象最多的代表x∈U∩Xi;

12)

Ri=Ri∪{x};

13)

X=X-n*(x);

14)

end while

15)

R=R∪Ri;

16)

end for

17)

T={nr+|r∈R};

18)

returnR和T;

其中：

第1)行,定義代表集合R和相似度閾值集合T。

第2)行,根據(jù)式(2)計算每兩個對象之間的相似度。

第3)～6)行,根據(jù)式(5)計算對象x的最小相似度閾值θx+。根據(jù)式(6)計算x最大鄰域n*(x)。

第7)行,U是論域,X是U的子集,共分成k個子集。

第8)～16)行,選出當(dāng)前覆蓋正域?qū)ο笞疃嗟膶ο髕,也就是|n*(x)|最大的對象x。它就是本輪選出的代表,然后從當(dāng)前正域X中刪除x的鄰域包含的所有對象，并將選出來的代表x及對應(yīng)鄰域n*(x)保存。循環(huán)此步驟直至論域U被全部覆蓋。

第17)～18)行,返回代表集合R及代表對應(yīng)鄰域的相似度閾值集合T。

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

定義6 距離。設(shè)x是未分類對象,它與代表r之間的距離定義為:

distance=1/sim(x,r) -1 /θr+;

(7)

顯然,未分類對象與代表對象之間的相似度和距離成反比。一般認(rèn)為未分類對象與距離最近的代表保持決策一致。與未分類對象擁有最小距離的代表組成的集合稱為有效代表集。有效代表集記為:

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

(8)

其中:

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

(9)

根據(jù)有效代表可以對未分類對象的類標(biāo)簽進(jìn)行預(yù)測:只有一個有效代表時,未分類對象與有效代表的類標(biāo)簽一致;有多個有效代表時,通過所有有效代表的類標(biāo)簽投票來決定未分類對象類標(biāo)簽。

下面給出標(biāo)簽預(yù)測算法的偽代碼描述。

輸入 未分類對象x, 代表集合R。

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

1)

E=?;

2)

mindis=MAX_VALUE;

3)

for (eachr∈Y) do

4)

計算sim(x,r);

5)

計算distance(x,r);

6)

if (distance(x,r)

7)

mindis=distance(x,r);

8)

E={r};

9)

else then

10)

E=E∪{r};

11)

end if

12)

end for

13)

Getd′(x);

14)

returnd′(x);

其中：

第1)～2)行,初始化有效代表集合E和最小距離。

第4)～5)行,根據(jù)式(7)計算未分類對象與代表之間的距離。

第6)～10)行,根據(jù)式(8)～(9)找出與未分類對象距離最小的有效代表集合E。

第13)～14)行,有效代表投票決定未預(yù)測對象類標(biāo)簽并返回。

2.3 集成學(xué)習(xí)策略

本文提出的LOOELCA主要分為以下5個步驟:1)把帶類標(biāo)簽的訓(xùn)練集隨機(jī)等分成n份;2)依照留一法的思想進(jìn)行重采樣,形成n組〈訓(xùn)練集-1,測試集〉;3)調(diào)用RBC-CBNRS算法構(gòu)建基分類器;4)根據(jù)第3)步構(gòu)建的分類器組成委員會;5)通過委員會對測試集中的對象進(jìn)行標(biāo)簽預(yù)測。

2.3.1 留一法

留一法把訓(xùn)練集TR分層采樣為n份容量為n-1但互斥的子集,每次將1個子集作為訓(xùn)練集,預(yù)留出來的1個對象作為測試。正如圖2的基分類器構(gòu)建階段、RBC-CBNRS分類階段描述:用第一個子訓(xùn)練集預(yù)測對象x1,第二個子訓(xùn)練集預(yù)測對象x2,依此類推直至預(yù)測出xn。其中對預(yù)留對象進(jìn)行預(yù)測時,采用的是RBC-CBNRS算法。

對于預(yù)測錯誤的預(yù)留對象進(jìn)行標(biāo)記,并將其放入離群池,如圖2中所示的對象x2、x3。在離群對象選擇階段,所有被標(biāo)記的對象放入離群池。離群池中的對象用于對委員會決策不一致對象分類。

2.3.2 集成策略

把留一法構(gòu)建出來的基分類器進(jìn)行集成。若留一法中RBC-CBNRS算法對預(yù)留出的對象分類錯誤,那么算法認(rèn)為預(yù)留對象是訓(xùn)練集隨機(jī)抽樣時產(chǎn)生的離群對象。對預(yù)留對象分類錯誤：一方面表明這個分類器有缺陷;另一方面說明這個預(yù)留對象有特點。因此這類對象對應(yīng)的子訓(xùn)練集比較有研究價值。如圖2所示,所有離群對象對應(yīng)的分類器和原始訓(xùn)練集對應(yīng)的分類器一起組成委員會。

LOOELCA根據(jù)基分類器構(gòu)成的委員會決定測試集中未分類對象的標(biāo)簽。會有兩種情況:委員會中成員決策一致,那么此時未分類對象和委員會保持決策一致;另一種情況,委員會中各成員決策不一致,利用outlier pool中的對象采用kNN算法對未分類對象分類。

2.4 LOOELCA算法分析

LOOELCA的基分類器是RBC-CBNRS算法,因此要分析算法復(fù)雜度就需先分析RBC-CBNRS算法的復(fù)雜度。下面對RBC-CBNRS算法的兩個階段進(jìn)行復(fù)雜度分析。

代表選舉子算法階段:計算相似度時每個對象有a個屬性,每個對象需要與其他n-1個對象計算相似度,此步的復(fù)雜度為an(n-1)，記為O(n2)。計算最小相似度閾值θx+時,每個對象需要與其余n-1個對象比較相似度,此步的復(fù)雜度為n(n-1)，記為O(n2)。采用貪心算法對已生成的鄰域進(jìn)行覆蓋時,需要比較選出代表后的其余對象。選出零個代表時需要計算n次,當(dāng)選出1個代表時需要計算n-1次,依此類推,當(dāng)選出p個代表時, 算法復(fù)雜度為n+(n-1)+…+(n-p+1)=p(2n-p+1)/2,記為O(np)。綜上所述該階段的復(fù)雜度為:

O(n2)+O(n2)+O(np)=O(n2)

標(biāo)簽預(yù)測子算法階段:同樣選出的有效代表為p個,測試集有m個對象。每個未預(yù)測對象需要與p個代表計算距離,因此需計算相似度。由上一步計算可知,計算相似度時的復(fù)雜度為O(n2)，所以該階段的復(fù)雜度為O(n2mp)。算出距離之后需要找出最小距離,即每個未預(yù)測對象需與每一個代表比較距離,所以復(fù)雜度為O(mp)。標(biāo)簽預(yù)測階段只需計算相似度和距離,而簡單的投票階段可以忽略。因此該階段的復(fù)雜度為:

O(n2mp)+O(mp)=O(mpn2)

綜上所述,RBC-CBNRS的算法復(fù)雜度為O(mpn2)。本文LOOELCA需要對基分類器進(jìn)行集成,假設(shè)集成的基分類器數(shù)目為t。最簡單的情況委員會中只有原始訓(xùn)練集構(gòu)成的一個分類器,此時算法的復(fù)雜度與RBC-CBNRS算法復(fù)雜度相同,可記為O(mpn2)。最復(fù)雜的情況是所有的基分類器都進(jìn)入委員會,此時共有(n+1)個分類器。這時LOOELCA的復(fù)雜度為mpn2(n+1),可記為O(mpn3)。綜上所述,LOOELCA的復(fù)雜度介于兩者之間為:

O(mpn2) ≤O(tmpn2) ≤O(mpn3)

圖2 集成學(xué)習(xí)策略示意圖Fig. 2 Schematic diagram of ensemble learning strategy

3 實驗與分析

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

實驗在UCI的9個數(shù)據(jù)集上與RBC-CBNRS算法作了內(nèi)部對比。另外,本文提出的LOOELCA也和J48、ID3、Na?ve Bayes、OneR等算法作了比較。實驗所用數(shù)據(jù)集詳細(xì)信息如表2所列。

3.2 與RBC-CBNRS算法對比

首先,實驗將LOOELCA與RBC-CBNRS算法進(jìn)行了對比,實驗結(jié)果如表3～4所示。整體上來看,在實驗所用的9個數(shù)據(jù)集上,LOOELCA比RBC-CBNRS算法分類精度有提升，精度平均提升0.35～2.76個百分點。其中精度平均提升是指對應(yīng)數(shù)據(jù)集上各組實驗精度提升值總和除以實驗組數(shù)。

由表3～4可以看出,在penbased、ionosphere、mushroom、wdbc、zoo、dermatology六個數(shù)據(jù)集上,當(dāng)訓(xùn)練集設(shè)定比例較小時,LOOELCA較RBC-CBNRS算法分類精度提升更高。這說明當(dāng)選定訓(xùn)練集較小時,更容易產(chǎn)生離群對象或邊界對象。在RBC-CBNRS算法中訓(xùn)練集較小時,離群對象對分類精確度的影響較大;隨著數(shù)據(jù)集的不斷變大,離群對象使RBC-CBNRS算法分類錯誤的影響被限制了。

在tic-tac-toe數(shù)據(jù)集上,LOOELCA對RBC-CBNRS算法精度提升不受訓(xùn)練集比例影響。說明這個數(shù)據(jù)集數(shù)據(jù)分布比較均勻,離群對象或邊界對象對分類精確度的影響相對穩(wěn)定。

有少數(shù)組實驗數(shù)據(jù)分類精度不升反降，其他的幾組實驗分類精度有提升。同樣，在sonar數(shù)據(jù)集上,第一組實驗數(shù)據(jù)分類精度提升不明顯。說明在對應(yīng)數(shù)據(jù)集上，訓(xùn)練集較小時,離群對象對分類精度的影響不大，此時訓(xùn)練集對象較少,有正常對象被LOOELCA當(dāng)成離群對象,反而影響了分類精度。隨著訓(xùn)練集的增大,離群對象對RBC-CBNRS算法分類精度的影響凸顯出來,因此LOOELCA對分類精度的提升也更明顯。

3.3 與經(jīng)典算法對比

實驗在UCI的9個數(shù)據(jù)集上和J48、Na?ve Bayes、ID3、OneR等經(jīng)典算法作了對比。圖3繪出了9個數(shù)據(jù)集上各分類算法精度的對比圖。

在mushroom數(shù)據(jù)集上Na?ve Bayes算法的分類精度約為92%；在penbased數(shù)據(jù)集上OneR算法的精度約為35%；在dermatology數(shù)據(jù)集上OneR算法的精度約為45%。為了繪圖清晰，圖3(a)、(c)、(i)只繪出了四種算法的精度對比。

表2 數(shù)據(jù)集信息Tab. 2 Data set information

表3 小數(shù)據(jù)集上LOOELCA相對于RBC-CBNRS的分類精度提升百分點Tab. 3 Classification accuracy’s percentage point increase of LOOELCA relative to RBC-CBNRS on small data sets

表4 較大數(shù)據(jù)集上LOOELCA相對于RBC-CBNRS的分類精度提升百分點Tab. 4 Classification accuracy’s percentage point increase of LOOELCA relative to RBC-CBNRS on larger data sets

圖3 LOOELCA與經(jīng)典算法對比Fig. 3 Comparison of LOOELCA and classical algorithms

從總體上看,在實驗所用數(shù)據(jù)集上,LOOELCA分類精度高于參與對比的經(jīng)典算法。部分?jǐn)?shù)據(jù)集上優(yōu)勢不明顯,例如mushroom、wdbc兩個數(shù)據(jù)集。由于數(shù)據(jù)集本身對象較多,屬性較多,所以大部分分類算法都能取得不錯的分類效果。

圖3(d)、(g)、(i)顯示,在對應(yīng)數(shù)據(jù)集上LOOELCA并不能優(yōu)于所有算法,但總體上看分類精度優(yōu)于大部分參與對比的算法。其他子圖顯示,對應(yīng)數(shù)據(jù)集上LOOELCA分類精度優(yōu)于其他參與對比的經(jīng)典算法。

如表5所示,列出了9個數(shù)據(jù)集上參與對比的五種算法的排名。便于對比,當(dāng)分類精度平均值相差小于0.5%時,排名相同。從平均排名看LOOELCA排名最靠前,排名第二的Na?ve Bayes算法平均排名與LOOELCA差值為1。

表5 每個數(shù)據(jù)集上的各算法排名Tab. 5 Ranking of each algorithm on each data set

3.4 結(jié)果分析

本文提出的LOOELCA分類精度較RBC-CBNRS算法有提升,且分類性能優(yōu)于J48等經(jīng)典分類算法。實驗結(jié)果可看出,離群對象、邊界對象對RBC-CBNRS算法分類效果造成顯著影響。本文提出的LOOELCA有效地減小了該影響,提升了分類精度。從大部分?jǐn)?shù)據(jù)集來看,訓(xùn)練集規(guī)模小時,LOOELCA對RBC-CBNRS算法的精度提升更明顯。這也說明當(dāng)訓(xùn)練集規(guī)模小時，抽樣不均勻?qū)λ惴ǖ挠绊懜?。在?shù)據(jù)集較大的mushroom、wdbc兩個數(shù)據(jù)集上,LOOELCA較RBC-CBNRS算法精度也有提升。這說明就算有足夠的訓(xùn)練集數(shù)據(jù),也存在離群對象或邊界對象對分類精度影響的問題。

與Na?ve Bayes等經(jīng)典算法的對比實驗可以看出:在實驗所用的大部分?jǐn)?shù)據(jù)集上,LOOELCA分類精度更高。結(jié)合實驗結(jié)果和表2可以看出，在數(shù)據(jù)集對象超過300時,LOOELCA總能獲得較好的分類效果。在實驗所用數(shù)據(jù)集上,LOOELCA分類精度變化平緩,分類性能穩(wěn)定。

4 結(jié)語

RBC-CBNRS算法中,受抽樣不均勻影響會出現(xiàn)離群對象或邊界對象。為了應(yīng)對離群對象或邊界對象對分類精度的影響,本文提出了一種基于RBC-CBNRS算法的留一法的集成學(xué)習(xí)策略。實驗結(jié)果表明,本文提出的集成策略對算法的分類精度有提升。在進(jìn)一步的工作中,將研究代價敏感[14-15]問題對RBC-CBNRS算法的影響,如考慮測試代價、誤分類代價等因素。