李文斌,劉椿年,鐘 寧,3

(1.石家莊經(jīng)濟(jì)學(xué)院信息工程學(xué)院,石家莊 050031;2.北京工業(yè)大學(xué)電子信息與控制工程學(xué)院,北京 100124;3.日本前橋工業(yè)大學(xué)生命科學(xué)與信息學(xué)院,群馬 371-0816,日本;4.河北師范大學(xué) 軟件學(xué)院,石家莊 050016)

集成學(xué)習(xí)主要通過決策優(yōu)化或覆蓋優(yōu)化 2種手段將若干弱分類器的能力進(jìn)行綜合,以優(yōu)化分類系統(tǒng)的總體性能[1].近年來,多分類器集成已成為研究者們關(guān)注的一個(gè)熱點(diǎn)[2-8].集成學(xué)習(xí)的研究被認(rèn)為是當(dāng)前機(jī)器學(xué)習(xí)的四大研究方向之首[9].訓(xùn)練多個(gè)個(gè)體學(xué)習(xí)器是集成學(xué)習(xí)的第 1步,集成則是將這些個(gè)體學(xué)習(xí)器進(jìn)行組合.文獻(xiàn)[10]中,按照個(gè)體學(xué)習(xí)器生成方式的不同,將集成方法大致分為 2類:以 AdaBoost為代表的提升(Boosting)方法(統(tǒng)稱該類為 Boosting);另一類以裝袋(Bagging)為代表(統(tǒng)稱這一類為Bagging).

本文提出了 1種介于 Bagging和 Boosting之間的集成學(xué)習(xí)方法,稱為兩階段集成學(xué)習(xí)(two-phase ensemble learning,簡稱為 TPEL).TPEL包括 2個(gè)過程:直接學(xué)習(xí)和間接學(xué)習(xí).直接學(xué)習(xí)指從給定的訓(xùn)練例中學(xué)習(xí)出多個(gè)個(gè)體分類器的過程;間接學(xué)習(xí)則指從這些個(gè)體學(xué)習(xí)器擁有的“知識”中學(xué)習(xí)集成分類器的過程.結(jié)合電子郵件過濾這樣1個(gè) 2類文本分類問題[11],本文設(shè)計(jì)并實(shí)現(xiàn)了一系列實(shí)驗(yàn),實(shí)驗(yàn)中采用樸素貝葉斯方法(Na·l·ve Bayes,簡稱為 NB)為基線分類器(baseline classifier),其判別函數(shù)參見文獻(xiàn)[12].對郵件過濾而言,誤拒和誤收錯(cuò)誤的代價(jià)是不同的[2],本文僅將郵件過濾看作是普通的2類文本分類問題加以研究,未考慮郵件過濾的特殊性.

1 兩階段集成學(xué)習(xí)(TPEL)

Bagging[13]和 Boosting[14]是 2種有代表性的集成學(xué)習(xí)方法,TPEL的設(shè)計(jì)來自于對 Bagging和 Boosting的分析.

1.1 Bagging及 Boosting分析

對 2類分類問題而言,Bagging學(xué)習(xí)的預(yù)測函數(shù) H可以表示為

其中,x是新例;c0和 c1是類別標(biāo)識符;L是弱學(xué)習(xí)算法;T是訓(xùn)練輪數(shù);Li是第 i輪學(xué)習(xí)出來的分類器.當(dāng)Li認(rèn)為 x是 c1類別時(shí),Li(x)輸出 c1,否則輸出 c0.

Boosting算法最早可以追溯到 1990年,由 Schapire[14]提出.Freund[15]于 1995年提出了 AdaBoost算法.就 2類分類問題而言,K可以表示為

其中,x是新樣本,wi是第 i(i=1,…,T)個(gè)預(yù)測函數(shù) Li的權(quán)重(通常在訓(xùn)練例上分類效果越好的預(yù)測函數(shù),它的權(quán)重越大,相反則越小).

本文中 H和K為集成函數(shù),統(tǒng)一記為 E.從上面的描述可知,Bagging和 Boosting的集成函數(shù)都被事先設(shè)定了類型或形式.Bagging的集成函數(shù) H是 1個(gè)分段函數(shù),Boosting的集成函數(shù)K是 1個(gè)線性組合函數(shù).若令 y=〈L1(x),L2(x),…LT(x)〉,當(dāng) x變化時(shí),y在T維空間形成了一系列點(diǎn),一部分點(diǎn)的真實(shí)類別為c1,記為 Y1;另一部分點(diǎn)的真實(shí)類別為 c0,記為 Y0.Bagging和 Boosting則假定了 1個(gè)超平面,將這 2類點(diǎn)分開,圖 1以 Bagging為例進(jìn)行說明.圖 1中,立方體的每個(gè)頂點(diǎn)代表 1個(gè) y向量,圓形所示的頂點(diǎn)是Bagging標(biāo)注為 c1的點(diǎn).Bagging假定 A、B、C這 3個(gè)頂點(diǎn)決定的面是將 Y1和 Y0分開的分類超平面,該平面上及其法線方向的上方區(qū)域被 Bagging認(rèn)為是 Y1中的點(diǎn)所在的區(qū)域,該平面法線反方向所指的下方區(qū)域被認(rèn)為是 Y0中的點(diǎn)所在的區(qū)域.

顯然,事先設(shè)定將 Y1和 Y0分開的分類超平面的辦法將導(dǎo)致算法的性能不確定.事實(shí)上,正是這種對集成函數(shù)的預(yù)先設(shè)定,導(dǎo)致了 Bagging和 Boosting的一些缺點(diǎn)和現(xiàn)象:

1)Bagging能提高不穩(wěn)定學(xué)習(xí)算法的預(yù)測精度,而對穩(wěn)定學(xué)習(xí)算法效果不明顯,有時(shí)甚至使預(yù)測精度降低[13].

2)Boosting和 Bagging的輪數(shù)并非越多越好[16].

3)Boosting方法在有效時(shí)效果比 Bagging還好,但在無效時(shí)卻可能使學(xué)習(xí)系統(tǒng)的性能惡化[16].

為此,在 TPEL中采用學(xué)習(xí)算法學(xué)習(xí)將 Y1和 Y0分開的分類超平面,即 TPEL采用學(xué)習(xí)的辦法對集成函數(shù)進(jìn)行構(gòu)造.

1.2 TPEL算法

TPEL包括 2個(gè)階段:直接學(xué)習(xí)和間接學(xué)習(xí).TPEL直接學(xué)習(xí)的學(xué)習(xí)任務(wù)是利用 1個(gè)或多個(gè)同構(gòu)或異構(gòu)的學(xué)習(xí)算法從訓(xùn)練集中學(xué)習(xí)多個(gè)個(gè)體分類器,設(shè)為 fi(i=1,…,m).對 2類分類任務(wù)而言,個(gè)體分類器可表示為

式中,R為分類器輸出的類別概率;x是 1個(gè)文本向量;d是 x的維數(shù).間接學(xué)習(xí)則指從個(gè)體分類器擁有的知識中進(jìn)行學(xué)習(xí)的過程.

圖 1 Bagging假定集成函數(shù)形式的示意圖Fig.1 Illustrative figure of Bagging's predefined ensemble function

顯然,TPEL的關(guān)鍵問題是如何表示個(gè)體分類器的知識,下面給出本文采用的 1種知識的表示方法.設(shè) D是訓(xùn)練集,其中有 ｜D｜個(gè)樣本,它們的期望輸出為

式中 yi(i=1,…,｜D｜)表示第 i個(gè)樣本的期望輸出,yi∈ {c0,c1}.

設(shè) Yk(k=1,…,m)是個(gè)體分類器 fk在 D上的實(shí)際輸出,Yk=[yk1,…,yk｜D｜]T,ykj是 fk對第 j(j=1,…,｜D｜)個(gè)訓(xùn)練例的實(shí)際輸出.由于某些 fk輸出的是類別,此時(shí) ykj∈{c0,c1};某些 fk輸出的是函數(shù)值或概率值,此時(shí) ykj∈R.個(gè)體學(xué)習(xí)器擁有的知識被表示成矩陣K的第 i行 ki代表第i個(gè)訓(xùn)練例 xi(i=1,…,｜D｜),ki的第 j個(gè)單元 kij的值代表了 fj對 xi的分類知識(j=1,…,m),ki(m+1)則指示了 xi的期望類別.從而,對 2類分類問題而言,間接學(xué)習(xí)的任務(wù)是學(xué)習(xí)分類超平面(即集成函數(shù) E),將K中 c1類別和 c0類別的樣本在空間中分開.

前文中,Bagging和 Boosting的集成函數(shù)都被事先假定了類型或形式,而 TPEL中的集成函數(shù)則是通過間接學(xué)習(xí)中采用的學(xué)習(xí)算法而得.因此,TPEL具有更強(qiáng)的泛化能力及魯棒性,這一點(diǎn)在實(shí)驗(yàn)中得到了很好的驗(yàn)證.

算法 1和算法 2分別給出了為 2類文本分類設(shè)計(jì)的 TPEL的訓(xùn)練和分類算法.

算法 1TPEL-trainer(D,L[1..T],L0,T) ∥L[1],…,L[T]是學(xué)習(xí)算法

輸入:訓(xùn)練集 D;輪數(shù) T;T個(gè)學(xué)習(xí)算法 L[1],…,L[T];集成函數(shù)學(xué)習(xí)算法 L0

輸出:T個(gè)分類器:f1,…,fT;集成函數(shù) E

從算法 1可知,TPEL要進(jìn)行 2次分類器的訓(xùn)練,第 1次是訓(xùn)練 T個(gè)個(gè)體分類器(算法 1的#1行),第 2次是從 T個(gè)個(gè)體分類器的知識矩陣中訓(xùn)練得到集成函數(shù)(算法 1的#2～4行).這 2次訓(xùn)練似乎使 TPEL需要很長的訓(xùn)練時(shí)間,但實(shí)際情況并非如此.首先,f1,…,fT的訓(xùn)練過程是互不相干的,因此,各模型的訓(xùn)練可“并發(fā)”執(zhí)行,所需的時(shí)間僅比訓(xùn)練單分類器的時(shí)間稍長.在這點(diǎn)上,與 Bagging方法相同.Bagging類方法隨機(jī)選取訓(xùn)練子集訓(xùn)練個(gè)體學(xué)習(xí)器,由于各訓(xùn)練子集間相互獨(dú)立,使 Bagging的各個(gè)預(yù)測函數(shù)可并行或并發(fā)生成.其次,K的縱向維數(shù) T通常非常小,因此算法 1中#4行的學(xué)習(xí)過程所花費(fèi)的時(shí)間非常少,上述 2點(diǎn)在實(shí)驗(yàn)中都得到了驗(yàn)證.值得指出的是:算法 1的#3.2行對K中相應(yīng)單元賦值為類別值,在實(shí)際使用中,可以是弱分類器對當(dāng)前樣本輸出的類別概率或函數(shù)值.

算法 2TPEL-classifier(x,P,f1,…,fT,E)

輸入:新郵件 x;P的默認(rèn)值為 T;T個(gè)個(gè)體分類器為 f1,…,fT;集成函數(shù)為 E;

輸出:c0或 c1

IF(至少 P個(gè)分類器認(rèn)為 x是 ci)THEN RETURN ci∥i=0或 1,P由用戶設(shè)定

從算法 2可知,TPEL與 Bagging、Boosting類算法對新樣本的分類有明顯區(qū)別.當(dāng)新樣本到達(dá)時(shí),Bagging首先利用 T個(gè)個(gè)體學(xué)習(xí)器產(chǎn)生向量 X=〈m1,…,mT〉,其中 mj(j=1,…,T)是第 j個(gè)分類器對新樣本的標(biāo)注結(jié)果,然后根據(jù)X輸出多數(shù)分類器贊成的標(biāo)注結(jié)果.Boosting類的算法則根據(jù)各弱分類器的標(biāo)注決定新樣本的最終類別.TPEL則是將各分類器的實(shí)際輸出向量 X=〈m1,…,mT〉作為集成函數(shù)的輸入,由集成函數(shù)決定新樣本的類別.TPEL的集成函數(shù)是根據(jù)分類器在訓(xùn)練例上的分類歷史學(xué)習(xí)得到的,一方面,當(dāng)訓(xùn)練例發(fā)生變化時(shí),重新訓(xùn)練可使集成函數(shù)發(fā)生相應(yīng)改變;另一方面,改變間接學(xué)習(xí)過程中的學(xué)習(xí)算法也可使集成函數(shù)發(fā)生變化.這就意味著,TPEL的集成函數(shù)將會根據(jù)實(shí)際情況“動態(tài)”地決定 X的最終類別,這樣的做法將使結(jié)果更加可靠.

設(shè)有 3個(gè)弱分類器 M1、M2、M3,3個(gè)訓(xùn)練樣本 x1、x2、x3,它們的真實(shí)類別分別為 0、0、1.另設(shè)有新樣本x4,其期望類別是 0.這 3個(gè)弱分類器對 x1、x2、x3的輸出向量分別是 〈1,1,0〉、〈1,1,0〉、〈0,0,0〉,在 x4上的實(shí)際輸出向量為〈1,1,0〉.Bagging認(rèn)為,x4的類別是 1.然而,當(dāng)弱分類器的輸出向量為〈1,1,0〉時(shí),在訓(xùn)練例上的真實(shí)類別總是 0(如:x1、x2),而不是 1.因此,如果 Bagging能了解這一點(diǎn),就不會對 x4的類別判定犯錯(cuò)誤.然而,TPEL利用弱分類器在訓(xùn)練例上的分類“知識”能發(fā)現(xiàn)這一點(diǎn),從而輸出 0為 x4的真實(shí)類別.也就是說,Bagging類的方法并不根據(jù)弱分類器對訓(xùn)練例的分類情況輸出新樣本的類別.盡管Boosting算法考慮了弱分類器對訓(xùn)練例的分類情況,但最終的投票函數(shù)形式過于單一化.

2 實(shí)驗(yàn)

本文實(shí)驗(yàn)驗(yàn)證了以下問題:

1)弱學(xué)習(xí)器的個(gè)數(shù)對 TPEL預(yù)測效果的影響;

2)弱學(xué)習(xí)算法的類型(同構(gòu)或異構(gòu))對 TPEL預(yù)測效果的影響.從第 2節(jié)可知,Bagging、Boosting類方法通常只可以集成多個(gè)同構(gòu)的弱分類器(實(shí)際上,Bagging可集成異構(gòu)的);而 TPEL可集成多個(gè)同構(gòu)或異構(gòu)的分類器.

3)弱學(xué)習(xí)算法的穩(wěn)定性對 TPEL預(yù)測效果的影響.學(xué)習(xí)算法的穩(wěn)定性是指當(dāng)訓(xùn)練集發(fā)生較小變化時(shí),學(xué)習(xí)結(jié)果不會發(fā)生較大變化.文獻(xiàn)[12]指出,穩(wěn)定性是影響 Bagging預(yù)測效果的關(guān)鍵因素.對不穩(wěn)定學(xué)習(xí)算法(如:決策樹和神經(jīng)網(wǎng)絡(luò)),Bagging能提高它們的預(yù)測精度,而對穩(wěn)定的學(xué)習(xí)算法(如:k-NN、NB),Bagging的效果不明顯,有時(shí)甚至使預(yù)測精度降低.

4)TPEL的時(shí)間復(fù)雜度.

實(shí)驗(yàn)的硬件環(huán)境為:IBM T42筆記本(CPU:2.0 GHz;內(nèi)存:512 M);軟件環(huán)境為:JBuilder X+Weka[17]開發(fā)包.除特別說明,分類器參數(shù)都使用 Weka的默認(rèn)參數(shù).

2.1 實(shí)驗(yàn)數(shù)據(jù)集及評價(jià)指標(biāo)

本文采用了 4個(gè)公用的電子郵件測試集,分別是 PU1[18](下文用 D1表示),Lingspam[19](用 D2表示),Spam Assassin[20](用 D3表示),Spambase[21](用 D4表示).這 4個(gè)數(shù)據(jù)集中,2類(垃圾郵件和正常郵件)文本的數(shù)據(jù)分布情況見表 1.

表 1 實(shí)驗(yàn)數(shù)據(jù)分布情況Table 1 Experimental data distribution

對文本分類任務(wù)而言,常用的評價(jià)指標(biāo)為查準(zhǔn)率(precision,簡寫為 p)、查全率(recall,簡寫為 r)及F1值,計(jì)算公式見文獻(xiàn)[22].本文實(shí)驗(yàn)中采用的測試方法均為開放測試(數(shù)據(jù)集中 66%作訓(xùn)練,34%作測試);特征提取算法為信息增益(information gain,簡稱為 IG)[22],特征子集的大小為 150;文本表示的方法為二進(jìn)制詞頻.Spambase數(shù)據(jù)集中的每個(gè)郵件文本在發(fā)布時(shí)已經(jīng)被表示成了向量形式,所以對這一數(shù)據(jù)集未做特征子集提取,表示的方式上也未做額外的處理.

2.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn) 1基準(zhǔn)結(jié)果(baseline results).表 2給出了 NB、Bagging、AdaBoostM1這 3種方法在 4個(gè)數(shù)據(jù)集上的結(jié)果,其他實(shí)驗(yàn)將與此作參考進(jìn)行分析比較.表中,p(i)、r(i)、F1(i)(i=0,1)分別表示 p(ci),r(ci)和 F1(ci);P表示總的正確率(為正確分類的測試樣本數(shù)除以總測試樣本數(shù)).從表 2可以看出,若僅根據(jù)P判斷,Bagging在 D1、D2上的性能差于 NB;在 D 3、D4上要好于 NB,尤其是在 D4上.AdaBoostM1在 D1、D2、D3上要好于 NB,在 D4上與 NB的效果一致.

表 2 NB、Bagging和 AdaBoostM 1在 4個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Tab le 2 The experimental resu lts of NB,Bagging and AddBoostM 1 on four datasets %

實(shí)驗(yàn) 2弱分類器個(gè)數(shù)對 TPEL性能的影響實(shí)驗(yàn).本實(shí)驗(yàn)分為以下子實(shí)驗(yàn):

1)第 1階段分別采用 5、20、50、100個(gè) NB學(xué)習(xí)器,第 2階段采用 NB學(xué)習(xí)器;

2)第 1階段分別采用 5、20、50、100個(gè)徑向基網(wǎng)絡(luò)(RBFNetwork,簡稱為 RBF)學(xué)習(xí)器,第 2階段采用RBF學(xué)習(xí)器.

3)第 1階段分別采用 5、20、50、100個(gè) J48學(xué)習(xí)器,第 2階段采用 J48學(xué)習(xí)器.

4)第 1階段分別采用 5、20、50、100個(gè) PART學(xué)習(xí)器,第 2階段采用 PART學(xué)習(xí)器.

上述 4個(gè)子實(shí)驗(yàn)的結(jié)果如圖 2所示.

由圖 2(a)可知,當(dāng)弱學(xué)習(xí)器個(gè)數(shù) T發(fā)生變化時(shí),在前 3個(gè)數(shù)據(jù)集上,P基本不變;在第 4個(gè)數(shù)據(jù)集上,當(dāng) T取 100時(shí),P值微弱變小.從圖 2(b)來看,在 D1和 D2兩個(gè)數(shù)據(jù)集上,僅當(dāng) T取 50時(shí),發(fā)生了變化,T取 5、50、100時(shí),P基本不變.在 D3、D4上,當(dāng) T從 5變化到 50時(shí),P呈增加趨勢,當(dāng) T變化到 100時(shí),D3上的 P基本不變,而 D4上的 P值有所下降.圖 2(c)顯示的變化最為無序,但整體上來講,當(dāng) T改變時(shí),P的變化幅度都不大,在 D1上的變化區(qū)間為[94.61%,95.96%],D2上的變化區(qū)間為[97.87%,98.17%],D3上的變化區(qū)間為[97.56%,98.39%],D4上的變化區(qū)間為[94.25%,95.27%].圖 2(d)表明,當(dāng) T從5增加到 100時(shí),在 4個(gè)數(shù)據(jù)集上,P值都呈不斷增加的趨勢.

總體來看,該實(shí)驗(yàn)的結(jié)果表明,在4個(gè)數(shù)據(jù)集上,當(dāng)T變化時(shí),TPEL在P上的變化幅度都不大.從圖 2來看,T取 50時(shí),P在 4個(gè)數(shù)據(jù)集上都有較好的表現(xiàn),因此,在實(shí)踐中,建議 T的值不超過 50.

圖 2 弱分類器個(gè)數(shù)對TPEL性能的影響Fig.2 The performance of TPEL when the countof the weak classifiers is changed

實(shí)驗(yàn) 3異構(gòu)分類器集成實(shí)驗(yàn).“異構(gòu)”指在第 1階段學(xué)習(xí)每個(gè)個(gè)體分類器的學(xué)習(xí)算法彼此不同.表3給出了本實(shí)驗(yàn)的結(jié)果.首先比較該實(shí)驗(yàn)中的 TPEL與 AdaBoostM1的性能.從該表可看出,D1、D3、D4這3個(gè)數(shù)據(jù)集在多數(shù)指標(biāo)上都優(yōu)于 AdaBoostM 1.僅在數(shù)據(jù)集 D2上,TPEL略差于 AdaBoostM 1.在 D2上,AdaBoostM1的 P值為 98.68%,L2在這一數(shù)據(jù)集上取得了 98%的總正確率,與 AdaBoostM 1接近;L1、L3的 P值也與 AdaBoostM1比較接近.可見,此時(shí)的 TPEL比 AdaBoostM 1要優(yōu)秀許多.與 Bagging(見表 2)相比,本實(shí)驗(yàn)中的 TPEL在 4個(gè)數(shù)據(jù)集上的結(jié)果全面優(yōu)于 Bagging.因此,不難得出結(jié)論,TPEL在集成異構(gòu)分類器時(shí),效果非常理想.

表 3 異構(gòu)分類器集成的實(shí)驗(yàn)結(jié)果Table 3 The experimental results of combining multiple heterogeneous classifiers %

實(shí)驗(yàn) 4完全同構(gòu)分類器集成.完全同構(gòu)指第 1階段和第 2階段的學(xué)習(xí)算法相同.實(shí)驗(yàn)結(jié)果如表 4所示.從表 4可以看出,除 L2在 D1、D2兩個(gè)數(shù)據(jù)集上比 NB稍差外,其他值大部分都優(yōu)于 NB.僅從 P值分析,L1在 D1、D2上強(qiáng)于 Bagging,在 D3、D4上有所不及;L1僅在 D4上強(qiáng)于 AdaBoostM1.L2僅在 D1上強(qiáng)于 Bagging,其他數(shù)據(jù)集上與 Bagging接近;在 D3,尤其是在 D4上超過了 AdaBoostM1,在其他 2個(gè)數(shù)據(jù)集上接近.L3在 4個(gè)數(shù)據(jù)集上的都超過了 Bagging;在 D3、D4上超過了 AdaBoostM1,在 D1、D2上與AdaBoostM1的 P值有 1%左右的差距.L4在 D1、尤其是在 D4上,超過了 AdaBoostM1,在 D2、D3上也與AdaBoostM1的性能接近;在 D1、D2上超過了 Bagging.

表 4 完全同構(gòu)分類器集成結(jié)果Tab le 4 The experimental resu lts of com bining the sam e classifiers %

當(dāng)集成完全同構(gòu)的分類器時(shí),TPEL也取得了成功.尤其是當(dāng)采用適當(dāng)?shù)娜鯇W(xué)習(xí)分類器的學(xué)習(xí)算法時(shí)(如 L3),TPEL的性能超過 Bagging和 AdaBoostM 1的表現(xiàn).

實(shí)驗(yàn) 5部分同構(gòu)實(shí)驗(yàn).結(jié)果見表 5部分同構(gòu)指第 1階段的學(xué)習(xí)算法相同,但第 2階段采用與第 1階段不同的學(xué)習(xí)算法.從表 5可以看出,在各種實(shí)驗(yàn)中,TPEL的大部分指標(biāo)值比 NB的要好,尤其是 L3.結(jié)合實(shí)驗(yàn) 4可知,TPEL適用于部分同構(gòu)或完全同構(gòu)方式的集成.

表 5 部分同構(gòu)實(shí)驗(yàn)的結(jié)果Table 5 The experim enta l resu lts of combining part o f the homogeneous classifiers %

實(shí)驗(yàn) 6穩(wěn)定性實(shí)驗(yàn).包括 4個(gè)子實(shí)驗(yàn).

1)測試對穩(wěn)定性算法 NB的集成情況.在 TPEL中,第 1階段采用 10個(gè) NB,第 2階段采用 NB.

2)測試對穩(wěn)定性算法 k-NN(k=5)的集成情況.在 TPEL中,第 1階段采用 10個(gè)k-NN,第 2階段采用NB.

3)測試對不穩(wěn)定性算法 RBF的集成情況.在 TPEL中,第 1階段采用10個(gè) RBFNetwork,第 2階段采用RBFNetwork.

4)測試對不穩(wěn)定算法 J48的集成情況.在 TPEL中,第 1階段采用 10個(gè) J48,第 2階段采用 J48.

4個(gè)子實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果如圖 3所示.

圖 3 TPEL穩(wěn)定性實(shí)驗(yàn)Fig.3 Stability experiment

圖 3(a)、(b)表明,TPEL的結(jié)果與 NB的相當(dāng)或有提高.這說明,TPEL適用于集成穩(wěn)定算法,不像Bagging,對穩(wěn)定學(xué)習(xí)算法的集成往往會使性能極大地降低.圖 3(c)顯示 TPEL在 D1、D3數(shù)據(jù)集上比 RBF Network的性能稍差,在 D2上相當(dāng),在 D4上比單個(gè) RBFNetwork強(qiáng)許多.圖 3(d)顯示 TPEL在 4個(gè)數(shù)據(jù)集上都提高了 J48的性能.說明 TPEL適用于提升不穩(wěn)定性算法的性能.

可見,對穩(wěn)定或不穩(wěn)定算法,用 TPEL集成都能從一定程度上改善分類精度.

實(shí)驗(yàn) 7 時(shí)間復(fù)雜度實(shí)驗(yàn).表 6比較了 TPEL與其他算法的時(shí)間復(fù)雜度.TPEL的訓(xùn)練時(shí)間由 2部分組成,第 1部分來自于直接學(xué)習(xí),第 2部分來自于間接學(xué)習(xí).本實(shí)驗(yàn)中,TPEL第 1階段集成了 NB、PART、J48、RBF Network;第 2階段則采用 NB.由于第 1階段的訓(xùn)練可以采用多線程并發(fā)執(zhí)行方式,因此,第 1階段的訓(xùn)練時(shí)間約等于所集成的 4種算法中的最長訓(xùn)練時(shí)間.從表 6可以看出,TPEL的時(shí)間比 AdaBoostM1的要短許多.TPEL間接學(xué)習(xí)的時(shí)間非常短(見加號后面的數(shù)字),幾乎可以忽略不計(jì).

上述實(shí)驗(yàn)從各個(gè)側(cè)面分析了 TPEL的性能及特點(diǎn).實(shí)驗(yàn)結(jié)果表明,TPEL是一種有吸引力的集成學(xué)習(xí)方法.TPEL的優(yōu)勢為:

1)不需要過多地考慮輪數(shù) T的取值大小問題,因?yàn)?TPEL受 T的影響不大;

2)實(shí)現(xiàn)簡單,訓(xùn)練時(shí)間短;

3)效果明顯;

4)集成函數(shù)的形式并非一成不變,它隨數(shù)據(jù)集及直接和間接學(xué)習(xí)過程中的學(xué)習(xí)算法的變化而變化.

表 6 時(shí)間復(fù)雜度比較結(jié)果Tab le 6 Compared resu lts of time com plexity s

3 結(jié)束語

在集成學(xué)習(xí)中,集成函數(shù)的形式通常是被事先設(shè)定的,如在 Bagging類或 Boosting類方法中,這往往導(dǎo)致不確定的性能.本文提出了 1種 2階段集成學(xué)習(xí)的方法,其最大特點(diǎn)是利用學(xué)習(xí)算法學(xué)習(xí)集成的預(yù)測函數(shù).實(shí)驗(yàn)結(jié)果表明,TPEL受集成的個(gè)體分類器個(gè)數(shù)的影響甚微;利用 TPEL集成異構(gòu)的多個(gè)分類器時(shí)效果顯著;利用 TPEL集成同構(gòu)多個(gè)分類器時(shí),絕大部分情況下取得了優(yōu)于樸素貝葉斯等算法的結(jié)果;對穩(wěn)定及不穩(wěn)定學(xué)習(xí)器的集成效果都比較明顯;TPEL具有較低的時(shí)間復(fù)雜度.

盡管本文只是在 2類文本分類的情況下驗(yàn)證了算法的性能,但 2類分類是多類分類的基礎(chǔ),不難將TPEL推廣到多類的情況.

[1]蘇金樹,張博鋒,徐昕.基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J].軟件學(xué)報(bào),2006,17(9):1848-1859.SU Jin-shu,ZHANG Bo-feng,XU Xin.Advances in machine learning based text categorization[J].Journal of Software,2006,17(9):1848-1859.(in Chinese)

[2]李文斌,劉椿年,陳嶷瑛.基于混合高斯模型的電子郵件多過濾器融合方法[J].電子學(xué)報(bào),2006,34(2):247-251.LIWen-bin,LIU Chun-nian,CHEN Yi-ying.Combining multiple email filters of naive bayes based on GMM[J].Acta Electronica Sinica,2006,34(2):247-251.(in Chinese)

[3]刁力力,胡可云,陸玉昌,等.用 Boosting方法組合增強(qiáng)Stumps進(jìn)行文本分類[J].軟件學(xué)報(bào),2002,13(8):1361-1367.DIAO Li-li,HU Ke-yun,LU Yu-chang,et al.Improved stumps combined by boosting for text categorization[J].Journal of Software,2002,13(8):1361-1367.(in Chinese)

[4]魯湛,丁曉青.基于分類器判決可靠度估計(jì)的最優(yōu)線性集成方法[J].計(jì)算機(jī)學(xué)報(bào),2002,25(8):890-895.LU Zhan,DING Xiao-qing.An optimal linear combination method by evaluating the reliability of individual classifiers[J].Chinese Journal of Computers,2002,25(8):890-895.(in Chinese)

[5]李凱,黃厚寬.小規(guī)模數(shù)據(jù)集的神經(jīng)網(wǎng)絡(luò)集成算法研究[J].計(jì)算機(jī)研究與發(fā)展,2006,43(7):1161-1166.LIKai,HUANG Hou-kuan.Study of a neural network ensemble algorithm for small data sets[J].Journal of Computer Research and Development,2006,43(7):1161-1166.(in Chinese)

[6]姜遠(yuǎn),周志華.基于詞頻分類器集成的文本分類方法[J].計(jì)算機(jī)研究與發(fā)展,2006,43(10):1681-1687.JIANG Yuan,ZHOU Zhi-hua.A text classification method based on term frequency classifier ensemble[J].Journal of Computer Research and Development,2006,43(10):1681-1687.(in Chinese)

[7]周志華,陳世福.神經(jīng)網(wǎng)絡(luò)集成[J].計(jì)算機(jī)學(xué)報(bào),2002,25(1):1-8.ZHOU Zhi-hua,CHEN Shi-fu.Neural network ensemble[J].Chinese Journal of Computers,2002,25(1):1-8.(in Chinese)

[8]唐偉,周志華.基于Bagging的選擇性聚類集成[J].軟件學(xué)報(bào),2005,16(4):496-502.TANG Wei,ZHOU Zhi-hua.Bagging-based selective clusterensemble[J].Journal of Software,2005,16(4):496-502.(in Chinese)

[9]DIETTERICH T G.Machine learning research:four current directions[J].AIMagazine,1997,18(4):97-136.

[10]ZHOU Zhi-hua,TANGWei.Selective ensemb le of decision trees[C]∥Lecture Notes in Artificial Intelligence.Berlin:Springer,2003,26391:476-483.

[11]ZHONG N,MATSUNAGA T,LI U C N.A text mining agents based architecture for personal e-mail filtering and management[C]∥Lecture Notes in Computer Science.Berlin:Springer,2002:329-336.

[12]樊興華,孫茂松.一種高性能的兩類中文文本分類方法[J].計(jì)算機(jī)學(xué)報(bào),2006,29(1):124-131.FAN Xing-hua,SUN Mao-song.A high performance two-class Chinese text categorization method[J].Chinese Journal of Computers,2006,29(1):124-131.(in Chinese)

[13]BREIMAN L.Bagging predictors[J].Machine Learning,1996,24(2):123-140.

[14]SCHAPIRER E.The strength of weak learn ability[J].Machine Learning,1990,5:197-227.

[15]FREUND Y.Boosting a weak algorithm bymajority[J].Information and Computation,1995,121(2):256-285.

[16]OPITZ D,MACLIN R.Popular ensemble methods:an empirical study[J].Journal of Artificial Intelligence Research,1999,11:169-198.

[17]The University of Waikato.Weka開發(fā)包[DB/OL].(1998-01-02)[2009-11-02].http:∥www.cs.waikato.ac.nz/ml/weka/

[18]ANDROUTSOPOULOS I.PU 1數(shù)據(jù)集 [DB/OL].(2000-03-28)[2010-03-09].http:∥www.aueb.gr/users/ion/publications.html

[19]SAKKISG.Lingspam數(shù)據(jù)集[DB/OL].(2003-05-16)[2010-03-09].http:∥www.aueb.gr/users/ion/publications.html

[20]Apache Software Foundation.Spam Assassin數(shù)據(jù)集[DS/OL].(2002-02-08)[2010-03-09].http:∥spamassassin.apache.org/pub liccorpus/

[21]HEWLETT-PACKARD L.Spambase數(shù)據(jù)集[DB/OL].(1998-06-10)[2010-03-09].http:∥www.ics.uci.edu/～m learn/databases/spambase/

[22]YANG Y,PEDERSEN J O.A comparative study on feature selection in text categorization[C]∥Proc of the 14th International Conference on Machine Learning.[S.l.]:Morgan Kaufmann,1997:412-420.