基于代表的留一法集成學習分類

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

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

0 引言

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

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

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

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

1 相關工作

本文的基本數據模型為決策信息系統,涉及到覆蓋粗糙集和鄰域粗糙集等相關概念。

1.1 決策信息系統

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

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

(1)

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

表1 決策信息系統示例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算法計算對象之間相似度。根據定義2,由表1的決策信息系統可計算出sim(x1,x6)=5/6。同理可計算出各對象之間的相似度。

1.2 鄰域

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

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

(4)

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

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

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

(5)

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

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

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

(6)

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

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

2 問題描述及LOOELCA

本章首先介紹LOOELCA的基算法RBC-CBNRS算法,并對RBC-CBNRS算法進行時間復雜度分析;接著介紹集成學習策略的框架和過程,并對LOOELCA進行算法分析。

2.1 問題描述

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

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

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

2.2.1 代表生成算法

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

輸入 決策信息系統DS={U,C,g0gggggg,V,I}。

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

1)

R=?,T=?;

2)

根據式(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)

選擇當前覆蓋對象最多的代表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)行,根據式(2)計算每兩個對象之間的相似度。

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

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

第8)～16)行,選出當前覆蓋正域對象最多的對象x,也就是|n*(x)|最大的對象x。它就是本輪選出的代表,然后從當前正域X中刪除x的鄰域包含的所有對象，并將選出來的代表x及對應鄰域n*(x)保存。循環此步驟直至論域U被全部覆蓋。

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

2.2.2 標簽預測算法

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

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

(7)

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

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

(8)

其中:

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

(9)

根據有效代表可以對未分類對象的類標簽進行預測:只有一個有效代表時,未分類對象與有效代表的類標簽一致;有多個有效代表時,通過所有有效代表的類標簽投票來決定未分類對象類標簽。

下面給出標簽預測算法的偽代碼描述。

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

輸出 預測的類標簽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)行,根據式(7)計算未分類對象與代表之間的距離。

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

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

2.3 集成學習策略

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

2.3.1 留一法

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

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

2.3.2 集成策略

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

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

2.4 LOOELCA算法分析

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

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

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

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

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

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

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

圖2 集成學習策略示意圖Fig. 2 Schematic diagram of ensemble learning strategy

3 實驗與分析

3.1 數據集

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

3.2 與RBC-CBNRS算法對比

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

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

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

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

3.3 與經典算法對比

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

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

表2 數據集信息Tab. 2 Data set information

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

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

圖3 LOOELCA與經典算法對比Fig. 3 Comparison of LOOELCA and classical algorithms

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

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

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

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

3.4 結果分析

本文提出的LOOELCA分類精度較RBC-CBNRS算法有提升,且分類性能優于J48等經典分類算法。實驗結果可看出,離群對象、邊界對象對RBC-CBNRS算法分類效果造成顯著影響。本文提出的LOOELCA有效地減小了該影響,提升了分類精度。從大部分數據集來看,訓練集規模小時,LOOELCA對RBC-CBNRS算法的精度提升更明顯。這也說明當訓練集規模小時，抽樣不均勻對算法的影響更大。在數據集較大的mushroom、wdbc兩個數據集上,LOOELCA較RBC-CBNRS算法精度也有提升。這說明就算有足夠的訓練集數據,也存在離群對象或邊界對象對分類精度影響的問題。

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

4 結語

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