臺(tái)州廣播電視大學(xué) 丁一琦

一、MCMO-Boost算法

設(shè)定訓(xùn)練樣本Ai、類標(biāo)號(hào)Bi，訓(xùn)練集P={(Ai,Bi)|Bi∈{true,false}}，i=1,2,…,total。如Bi=true則為少數(shù)類，如Bi=false則為多數(shù)類，設(shè)x為少數(shù)類樣本的個(gè)數(shù)，y為多數(shù)類樣本的個(gè)數(shù)，且x

當(dāng)Bi=true，則初始化每條記錄分布D1(i)=1/x，當(dāng)Bi=false時(shí)，D1(i)=1/y，級(jí)聯(lián)次數(shù)為T。

For t=1 to T。以下是計(jì)算過(guò)程：

(1)根據(jù)Dt從P中選取若干抽樣，裝入集合SET。

(2)若T=1，則使用SET中的原始數(shù)據(jù)集進(jìn)行計(jì)算。

(3)若T≥2，鑒于SET中的任何樣本數(shù)據(jù)A’，若B’=true，而ht-1=false，則將A’裝入集合X——通過(guò)集合。

(4)對(duì)于X中的任何樣本A”，在P訓(xùn)練集中找到同類近鄰k，任選y個(gè)近鄰，在A”與y個(gè)緊鄰的級(jí)聯(lián)上形成新的合成數(shù)據(jù)：synth=A”+rj×difj,j=1 to n。其中，rj為0~1之間的隨機(jī)數(shù)；difj是x”與第j個(gè)近鄰的矢量差。因此少數(shù)類樣本擴(kuò)充了n倍。

(5)把擴(kuò)充的少數(shù)類樣本裝入SET集合，再用更新的數(shù)據(jù)集訓(xùn)練決策樹(shù)，得到假設(shè)ht。

(6)利用ht對(duì)P分類，按下式更新分布：，i=1 tototal

最終得到的分類器：

H(Xnew)=sign()

其中，前4步是對(duì)不均衡數(shù)據(jù)進(jìn)行抽樣處理的過(guò)程，基本思路是將少數(shù)類采用的抽樣種子方法來(lái)擴(kuò)張以達(dá)到平均的目的。

二、分級(jí)結(jié)構(gòu)分類器

因?yàn)閱渭?jí)的分類器很難滿足分類的覆蓋率與準(zhǔn)確率，因此在這里使用了分級(jí)結(jié)構(gòu)思想。

分級(jí)機(jī)構(gòu)分類器由多個(gè)不同層次子分類器構(gòu)成，分類過(guò)程呈一條食物鏈狀，只有上面一級(jí)分類器判斷為離網(wǎng)樣本，才進(jìn)到下面一級(jí)分類器繼續(xù)分類，不然被認(rèn)作非離網(wǎng)的樣本直接舍棄，最終的離網(wǎng)判斷結(jié)果是能夠通過(guò)每一層次分類器且被每一個(gè)子分類器判為離網(wǎng)樣本。

如果弱分類器分類完畢，依據(jù)它在訓(xùn)練集上的分類結(jié)果對(duì)所有的樣本權(quán)值進(jìn)行調(diào)整，使下一次分類的弱分類器得以更注意那些被判斷為錯(cuò)誤的樣本，最終降低整個(gè)體系離網(wǎng)樣本的錯(cuò)誤率FRR，每一層次的分類器都要求越低的FRR越好。在級(jí)聯(lián)結(jié)構(gòu)中，上一層次的分類器結(jié)構(gòu)比較簡(jiǎn)單，使用的特征數(shù)也比較少，且具有很高的檢測(cè)率，F(xiàn)RR值也很低，可以對(duì)和目標(biāo)差異較大的非離網(wǎng)樣本進(jìn)行過(guò)濾；但由于下一層次的分類器對(duì)正負(fù)樣本較難區(qū)分，而且使用更復(fù)雜的結(jié)構(gòu)，因此對(duì)FRR的要求也適當(dāng)降低。

級(jí)聯(lián)結(jié)構(gòu)分類器若使用原始數(shù)據(jù)集訓(xùn)練比較困難，由于原始數(shù)據(jù)總數(shù)據(jù)集中的流失樣本占較少比例(一般為7%以下)。如此比例的數(shù)據(jù)樣本無(wú)法形成較好的簡(jiǎn)單分類模型，使得算法剛開(kāi)始就有了比較高的FRR，最終離網(wǎng)趨勢(shì)模型也無(wú)法到達(dá)預(yù)定的目標(biāo)。

三、M-AdaBoost級(jí)聯(lián)決策樹(shù)

M-AdaBoost級(jí)聯(lián)決策樹(shù)——一種改進(jìn)的AdaBoost級(jí)聯(lián)決策樹(shù)，它使用不均衡數(shù)據(jù)集獲得比傳統(tǒng)級(jí)聯(lián)決策樹(shù)算法更好的效率，避免了單一決策樹(shù)在不均衡數(shù)據(jù)集上訓(xùn)練的同化能力低、傾向多類記錄、模型不確定等問(wèn)題。以下是MCMO級(jí)聯(lián)決策樹(shù)算法過(guò)程：

(1)給定訓(xùn)練集P={(Ai,Bi)|Bi∈{true,false}}，i=1 tototal。如Bi=true則為少數(shù)類，如Bi=false則為多數(shù)類，x為少數(shù)樣本的個(gè)數(shù)，y為多數(shù)類樣本個(gè)數(shù)，且x

(2)訓(xùn)練集SET中初始化記錄的分布D1,Bi=true時(shí)，D1(i)=1/(x)，Bi=false時(shí)，D1(i)=1/(y)。

(3)若r=x/(x+y)∈(rmin,rmax)，則繼續(xù)下一步驟，若rrmax，則轉(zhuǎn)到步驟(6)。

(4)根據(jù)Dt分布從P中抽樣的數(shù)據(jù)裝入集合SET，創(chuàng)建若干單特征分類器并選擇最適合的一個(gè)樣本，用弱分類器驗(yàn)證集合P中的樣本x，若判斷失誤，則裝入“通過(guò)集合”M。

(5)對(duì)于通過(guò)集合中的任一數(shù)據(jù)樣本x”，在S中找出同類近鄰k，并選擇任意y∈(1,k)個(gè)，依據(jù)synth=x”+rj×difj，j=1 to n對(duì)擴(kuò)充x”樣本記錄，其中，rj是0~1之間的隨機(jī)數(shù)；difj是x”與第j個(gè)近鄰的矢量差。因此少數(shù)類樣本擴(kuò)充了n倍并且合并裝入到SET中。

(6)征對(duì)SET中的數(shù)據(jù)，采用AdaBoost建立多層次級(jí)聯(lián)分類器。

四、實(shí)驗(yàn)及分析

在實(shí)際應(yīng)用中建立良好的客戶離網(wǎng)趨勢(shì)模型比較困難，離網(wǎng)趨勢(shì)的變化程度受到各種主、客觀因素的刺激。研究此類問(wèn)題采用的數(shù)據(jù)挖掘方式從傳統(tǒng)的單層次級(jí)別算法，發(fā)展到多層次多級(jí)別算法的組合，雖然多層次多級(jí)別算法設(shè)計(jì)了構(gòu)建挖掘策略模型、驗(yàn)證測(cè)試數(shù)據(jù)的準(zhǔn)確性，但在現(xiàn)實(shí)運(yùn)用中總是無(wú)法解決數(shù)據(jù)的不均衡難題、很難生產(chǎn)出方便客戶理解的策略模型。

以eclipse開(kāi)發(fā)工具為依據(jù)，應(yīng)用改進(jìn)后的AdaBoost算法，在樣本系統(tǒng)中進(jìn)行測(cè)試實(shí)驗(yàn)。應(yīng)用M-AdaBoost級(jí)聯(lián)決策樹(shù)算法，先使不均衡原始數(shù)據(jù)樣本集進(jìn)行均衡化處理，獲得提升少數(shù)類后的樣本，再將均衡后的數(shù)據(jù)樣本集以7:3拆分為測(cè)試集和訓(xùn)練集；確認(rèn)級(jí)聯(lián)分類器的總體虛警率F和每層次可接受的最大虛警率f，應(yīng)用第1級(jí)分類器對(duì)樣本集進(jìn)行分類；用第1級(jí)分類器對(duì)測(cè)試集進(jìn)行評(píng)估，運(yùn)算虛警率f并判決，將出錯(cuò)的非離網(wǎng)數(shù)據(jù)樣本和通過(guò)第1級(jí)分類器確認(rèn)的離網(wǎng)數(shù)據(jù)樣本作為第2級(jí)分類器的原始數(shù)據(jù)，第2級(jí)分類器再估算數(shù)據(jù)測(cè)試集，計(jì)算虛警率f并判決，同上，將出錯(cuò)的非離網(wǎng)樣本和通過(guò)第2級(jí)分類器確認(rèn)的離網(wǎng)樣本作為第3級(jí)分類器的原始數(shù)據(jù)。對(duì)第3級(jí)分類器進(jìn)行測(cè)試評(píng)估——類似2級(jí)分類器評(píng)估的形式，計(jì)算虛警率f并判決，再把本層級(jí)出錯(cuò)的非離網(wǎng)樣本和通過(guò)第3級(jí)分類器的離網(wǎng)樣本作為第4級(jí)分類器的樣本數(shù)據(jù)，獲得的模型達(dá)到了預(yù)定的性能指標(biāo)。

級(jí)聯(lián)分類器相應(yīng)于單層次分類結(jié)構(gòu)，在判決非離網(wǎng)數(shù)據(jù)樣本時(shí)的準(zhǔn)確度變化較小，但離網(wǎng)判斷虛警率f明顯降低，提升了數(shù)據(jù)策略的可讀性。

征對(duì)AdaBoost多層次級(jí)聯(lián)分類器、具備數(shù)據(jù)均衡處置的AdaBoost的多層次級(jí)聯(lián)分類器決策樹(shù)，在確認(rèn)多層次級(jí)聯(lián)分類器準(zhǔn)確度降低較少的前提下，加大了數(shù)據(jù)樣本的覆蓋面，可總體所用的計(jì)算時(shí)間延長(zhǎng)了。

五、結(jié)束語(yǔ)

對(duì)于多層次級(jí)聯(lián)模型策略的AdaBoost分類器是處理分類難題的最有效方法之一。但單層次的AdaBoost分類器是專門征對(duì)對(duì)稱的分層級(jí)難題，而升華后的性價(jià)還約束在單個(gè)級(jí)聯(lián)策略的判斷上，能一定程度上改變判斷覆蓋面。雖然其它多層級(jí)模型策略分類器最后的檢測(cè)結(jié)果能得到一定的提高，可需要的輸入在原始數(shù)據(jù)的基礎(chǔ)上進(jìn)行了較大的改變，使得最終的模型難以理解。本文提出的M-AdaBoost級(jí)聯(lián)決策樹(shù)，采用了較為合理的處理不平衡數(shù)據(jù)集的方式，避免了以往“人為抽樣”的粗暴策略，使得算法對(duì)于數(shù)據(jù)樣本的不平衡比例有了更好的適應(yīng)能力，對(duì)數(shù)據(jù)樣本的測(cè)試建立在決策鏈的多個(gè)分類器判決重合部分，保證了級(jí)聯(lián)分類器整體的準(zhǔn)確率，并且提高了判決的覆蓋率，實(shí)驗(yàn)結(jié)果表明此算法是有效的。但是關(guān)于平衡化處理的相關(guān)參數(shù)以及算法對(duì)于電信數(shù)據(jù)的適用能力還是后續(xù)需要研究的課題。

[1]韓慧，王文淵，毛炳浣.不均衡數(shù)據(jù)集中基于Adaboost的過(guò)抽樣算法[J].計(jì)算機(jī)工程，2007，23(10)：207-209.

[2]Viola P，Jones M.Fast and Robust Classification Using AsymmetricAdaBoost and a Detector Cascade[C].//Proc.of Advances in NeuralInformation Processing System.Cambridge，MA，USA：MIT Press，2002：1311-1318.

[3]王勇，陶曉玲.分級(jí)結(jié)構(gòu)的AdaBoost入侵檢測(cè)方法研究[J].西安電子科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，55(2)：345-361.

[4]李闖，丁曉青，吳佑壽.一種改進(jìn)的AdaBoost算法——ADAdaBoost[J].計(jì)算機(jī)學(xué)報(bào)，2007，30(1)：103-109.