臺州廣播電視大學 丁一琦

一、MCMO-Boost算法

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

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

For t=1 to T。以下是計算過程：

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

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

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

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

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

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

最終得到的分類器：

H(Xnew)=sign()

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

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

因為單級的分類器很難滿足分類的覆蓋率與準確率，因此在這里使用了分級結(jié)構(gòu)思想。

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

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

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

三、M-AdaBoost級聯(lián)決策樹

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

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

(2)訓練集SET中初始化記錄的分布D1,Bi=true時，D1(i)=1/(x)，Bi=false時，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)建若干單特征分類器并選擇最適合的一個樣本，用弱分類器驗證集合P中的樣本x，若判斷失誤，則裝入“通過集合”M。

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

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

四、實驗及分析

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

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

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

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

五、結(jié)束語

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

[1]韓慧，王文淵，毛炳浣.不均衡數(shù)據(jù)集中基于Adaboost的過抽樣算法[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]王勇，陶曉玲.分級結(jié)構(gòu)的AdaBoost入侵檢測方法研究[J].西安電子科技大學學報：自然科學版，2008，55(2)：345-361.

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