一種不均衡數據集的決策樹改進算法

臺州廣播電視大學 丁一琦

一、MCMO-Boost算法

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

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

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

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

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

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

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

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

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

最終得到的分類器：

H(Xnew)=sign()

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

二、分級結構分類器

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

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

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

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

三、M-AdaBoost級聯決策樹

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

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

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

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

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

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

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

四、實驗及分析

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

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

級聯分類器相應于單層次分類結構，在判決非離網數據樣本時的準確度變化較小，但離網判斷虛警率f明顯降低，提升了數據策略的可讀性。

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

五、結束語

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

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

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