简述一种基于C4.5的随机决策树集成分类算法设计

陈猛 洪伟

摘 要 决策树分类算法是数据挖掘的一种典型数据分析方法。本文提出一种基于C4.5的随机决策树分类器集成算法对数据集进行分类，该算法对属性选择进行随机化处理，并对集成过程进行控制，该分类器集成算法有较高的分类准确率。

关键词 集成;决策树;随机;C4.5

引言

分类是数据挖掘的一个重要分支，目前已有許多成熟的算法，如决策树、贝叶斯网络、神经网络、支持向量机等。集成分类法在同一问题上学习多个基分类器，再将其预测结果结合得出最终分类结果，它能够有效地提高预测性能，因此受到了广泛的关注[1]。

为保证模型分类效果，单个基分类器的精度要高，同时基分类器之间差异要大。本文提出了一种基于C4.5的随机决策树集成分类算法，在随机决策树的生成中对属性选择进行随机化处理，并对集成过程进行控制[2]。

本文的组织如下：第二部分介绍背景知识。第三部分介绍基于C4.5的随机决策树集成分类算法。

1知识背景

1.1 基于决策树的分类算法

在20世纪80年代初，机器学习研究者J.Ross Quinlan开发了ID3算法，算法的计算过程不需要任何领域知识和参数设置，适合于探索式知识发现。决策树归纳的学习和分类步骤简单快速，学习的模型用树形式表示，直观且易于理解，并且决策树分类一般情况下具有较好的准确率。后来Quinlan提出了C4.5[4]算法，它降低了计算复杂度，增强了计算的效率， 克服了ID3方法选择偏向取值多的属性。C4.5算法还针对连续值属性的数据进行了处理，弥补了ID3算法只能处理离散值属性数据的缺陷。

1.2 集成学习方法

与单个算法相比，集成分类可以提高分类准确率，而且不容易出现过适应现象。在每个基本分类器的学习过程之中引入随机，使得学习出来的每个基本分类器都不同，然后利用投票表决的方法进行集成，也是有效的系综学习方法。在集成学习中引入随机可以对改进学习的精度，取得更好的学习效果[3]。

2随机决策树集成分类算法

本文使用的决策树构造算法是C4.5。C4.5算法在构造每一层树结构时，选择信息增益最高的属性进行分裂，由于偏置的存在，C4.5在每一步分裂选择局部最优属性，但很难保证全局最优。随机决策树集成分类算法的基本思想是在属性选择时，在信息增益最高的若干属性中进行随机选择，生成的随机树与标准决策树构成集成分类器，投票表决分类测试数据。

由C4.5的算法特点可知，在决策树各级结点上选择属性进行分裂时，最上面的几层对树的结构影响较大，越往下往往影响越小，或者没有影响。在随机决策树集成分类算法中，我们引入了分裂深度。定义如下：

定义1：分裂深度（）

在生成随机分类树的过程中， 分类深度h <时，在属性随机选择序列中进行随机选择。

随机决策树集成分类算法在决策树的学习过程中引入随机，使得学习生成的每棵树都不相同，然后将多棵随机树与标准决策树集成在一起，利用投票表决的方法对数据进行分类。在随机树生成算法中，当分裂节点深度小于分裂深度（），算法在信息增益最高的NUM个属中随机选择一个属性作为分裂属性，下文实验中的N取值为3。当分裂节点深度大于分裂深度（）时，按标准树算法划分。

算法3.1随机树生成算法：

GRDT（D，deep）

输入：

D：训练元组和它们的对应类标号的集合;

deep; //生成随机树当前深度

输出：

一棵随机决策树

方法：创建结点 N;

if samples 都在同一个类C then

return N 作为叶结点，以类C标记;

if （（deep + 1） < ）

对属性列表的每个属性计算，选择信息增益最高的NUM个属性放入随机选择表中。

在随机选择表中，随机选择一个属性，作为分裂属性splitting_attribute

加一个由 GRDT （Dsplitting_attribute， deep+1）返回的节点到N ;

else  作标准树划分

return N;

生成随机决策树后，我们可以生成标准决策树，构造出集成分类器使用投票表决的方法分类测试数据[5]。算法如下：

输入：D，K

输出：集成模型M*

方法：

For（i=1;i

{ 使用D，导出随机决策树Ti，加入M*

}

将使用D导出的标准决策树T加入M*

Return M*

3结束语

决策树分类算法是预测式数据挖掘的一种典型数据分析方法，从类标记的训练元组归纳决策树。本文提出一种基于C4.5的随机决策树集成分类算法（标准树是其一个成员），对数据集进行分类，引入分裂深度的方法对随机树的产生进行控制，该分类器集成算法有较高的分类准确率。

参考文献

[1] Breiman L.Bagging Predictors[J].Machine Learning，1996，24（2）：

123-140.

[2] Ho T K.The Random Subspace Method for Constructing DecisionForests[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1998，20（8）：832-844.

[3] Breiman L.Random Forests[J]. Machine Learning，2001，45（1）：5-32.

[4] Quinlan J R.C4.5：Programs for Machine Learning[M].San Mateo，

CA：Morgan Kaufmann，1993：109.

[5] Dietterich T G. An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees： Bagging， Boosting， and Randomization[J]. Machine Learning，2000，40（2）：139-157.