学文网摘要:该文介绍了随机决策树分类模型及如何启发式选择随机决策树的深度及棵树,通过实验证明了该算法的有效性和高效性。
关键词:随机决策树;深度;棵树
中***分类号:TP181文献标识码:A文章编号:1009-3044(2009)25-7206-02
Discussion on Random Decision Tree
LIU Xue-jing1,2, JI Jun-zhong1
(1.School of Computer Science, Beijing University of Technology, Beijing 100022, China ; 2.School of Information Engineering, Shijiazhuang University of Economics, Shijiazhuang 050031, China)
Abstract: This paper introduces the classification model of random decision tree and how to heuristic selected the depth and the number, the experiment shows that the algorithm is effectiveness and efficiency.
Key words: random decision tree; depth; number
启发式学习算法被广泛的用于决策树分类模型中,其思想在于寻求一个最优化假设,该假设使得预先给定的误差函数的误差减至最小。近来,由于多种模型混合的成功,如bagging模型,boosting模型,meta-learning模型等等,大大提高了最简化假设的准确性。随机决策树的方法和一般算法不同,它不是构建最佳的单元树,而是通过条件属性集合构建多棵树,那么每棵树的深度如何确定,是不是把所有的条件属性都拿来测试,还是仅仅取部分属性进行测试就已经可以满足需求;另外,创建多少棵树才能达到可信度的要求。成为随机决策树构建过程中非常重要的两个问题。
1 树的深度的选择
使用多个随机树的主要特色是它的多样性。然而,当随机树太深的时候,多样性实际上是减弱了。多样性不是随深度的增长而线性增长的。恰恰相反,当随机树的深度等于属性个数的极端的情况下,产生的每一棵随机树都是完全相同的,可能一点多样性也没有。
这里采用组合数学的方法确定随机决策树的深度。假设条件属性集合中总共有k个属性,i是我们将要确定的测试属性的数目。Cik表示从k个属性中无次序的选择i个测试属性的组合数。即可以产生:Cik=(k)!/i!(k-i)!条***的决策路径
我们希望得到最大的组合数,从而使随机决策树最大程度的拥有多样性。对于Cik本身而言,无论k是奇数还是偶数,当i=k/2时都可以取得最大值。所以当我们限制随机树的深度为k/2时,也就是树的深度是条件属性数目的一半时,随机决策树有最强的多样性、最佳的效果。
2 树的个数的选择
因为每棵树被随机的构建,故对于给定深度的树,其数目是一个有效的随机样本,多棵树的平均将接近一个大的样本的真实平均数。当每个属性的取值都是二元时,树的规模将达到2k/2。平均概率是使用棵树的样本平均值。这存在一个问题是是否值得使用更大的样本,也就是说更多的随机决策树。统计上,非常惊奇的发现,当N=10时,对大多数的应用己经足够了。
我们分析了源自较低置信区间,最糟情况下算法的效果,已此证明多棵随机决策树模型是最佳的模型。数据集中的最坏情况是仅有一个相关的属性,其他的k-1个属性都是不相关的。在这是最坏的情况下,单元树将忽略所有的不相关属性并且选择单个相关属性,从而生成一个最佳模型。然而,随机树可能使用所有属性,不论它是相关属性的还是不相关的。我们得到随机树的数目N,能确保它在可信度为p的前提下是最佳模型。
后验概率将由接近于训练数据默认概率的不相关属性的数目来确定。如果其中有一棵随机树采用了最佳属性对事例进行分类,那么平均的概率要比缺省概率好。平均概率可以和最佳单元树输出的概率不相同,因为在树的构建过程中每个属性被选择的概率都是相同的,致使从树根到树叶的每一条绝对路径的出现具有相同的概率。由此,一个属性在绝对路径中出现的概率为p=1/k了,在N棵随机树中,相关属性至少在一条路径被测试到的概率为
最低限度可信度:p(k,N)=1-(1-1/k)N
即随机决策树是最佳模型的可信度至少为p(k,N)。事实上由于在相同的属性集中部分属性之间有相互的关系,导致实际的概率将比以上估计高。
3 算法描述
输入:训练数据集S={(x1,t1),…,(xn,tn)},属性集X={F1,…,Fk},N为随机决策树的棵数。
输出:N棵随机决策树{T1,…,TN}
算法:
RandomTree(S,X,N)
Begin
For i∈{1,…,N} do
BuildTree (Ti,X);
End
For (x,t) ∈S do
For i∈{1,…,N} do
Update (Ti, (x,t));
End
End
Return{ T1,…,TN }
End
BuildTree (T,X)
Begin
If X=φ then
生成叶节点;
End
Else
随机选择属性F,属性F有m个值{di};
For j∈{1,…,m} do
BuildTree (nj,,X-{F});
End
End
End
Update (T,(x,t))
Begin
n[t]存放类t的数量,n[t]
If the node is a not a leaf then
d=F(x),n 为属性值d对应的子节点;
Update (n,(x,t));
End
End
CLASSIFY({T1,…,TN},x)
Begin
for tree Ti,Pi(y|x)=where n[y] is the count at the leaf node that x finally reaches to;
returnfor all class labels y;
for tree Ti,where n[y] is the count at the leaf node that x finally reaches to;
return for all class labels y;
End
4 实验
实验结果与单元最佳未剪枝及剪枝的决策树比较,通过同时改变随机树的数量和每棵树的深度来研究在性能方面的变化,证明了随机树深度和棵树选择的正确。
我们从现实的应用中挑选出KDD CUP’98所取的捐款数据。实验运行4次,对每次测试,直到有50棵随机树被构造出来才停止,测试结果如表1所示。
观测结果有几点值得重视。第一,当随机树的数目超过10时,随机树算法取得平均总收益将比最好的方法多:第二在树从1棵生长到10棵的过程中,精确值将有大大的提升,并且在达到10棵的时候将达到平稳状态。该算法在生成了10棵树后将不断的波动,但其准确度大多数比单元最佳决策树方法高。
参考文献:
[1] 杨宁,赵连文,郭耀煌. 随机决策树[J].西南交通大学学报,2000,35(2):212-215.
[2] 赵晓峰,叶震.基于加权多随机决策树的入侵检测模型[J].计算机应用,2007,27(5):1041-1043.
[3] 李楠.基于改进随机决策树的入侵检测方法研究[D].合肥:合肥工业大学,2007.