一种不均衡数据集的决策树改进算法

台州广播电视大学 丁一琦

一、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.