CN4321258/TP ISSN10072130X 计算机工程与科学
COMPU TER EN GIN EERIN G&SCIENCE
2007年第29卷第10期
Vol129,No110,2007
文章编号:10072130X(2007)1020050204
基于单因素方差分析的决策树算法3
Decisio n Tree Algorit hms Based
o n a One2Way Analysis of Variance
丁顺利,洪允德,袁静波
DING Shun2li,H ONG Yun2de,YUAN Jing2bo
(东北大学秦皇岛分校计算机工程系,河北秦皇岛066004)
(Department of Computer E ngineering,Northeastern U niversity at Q inghu angd ao,Q inghu angd ao066004,China)
摘 要:测试属性的选择是决策树构建的关键。本文基于单因素方差分析原理,提出了决策树算法ANOVA1.0及ANOVA2.0。两种算法在测试属性的选择上分别采用最大组间平方和、最大组内平方和增益率,而且都在平台WEKA232 5上实现。与ID3、C415进行效率、精度等方面比较的大数据集实验结果表明,提出的两种算法是较好的分类算法。
Abstract:Two new decision tree algorithms,ANOVA110and ANOVA210,are presented in this paper.The algo2 rithms are based on one2way analysis of variance.ANOVA1.0selects tested attributes according to the biggest sum of squares between groups.ANOVA2.0selects the tested attributes according to the biggest inter2group gain ratio of sum of squares.ANOVA1.0and ANOVA2.0are implemented in the Weka2325software.The two given algorithms are compared to ID3and C4.5in performance,precision,and so on.The experiments with larger datasets are done and the experimental re2 sults show that ANOVA1.0and ANOVA2.0are better classification algorithms.
关键词:决策树;组间平方和;组内平方和增益率
K ey w ords:decision tree;inter2group sum of squares;intra2group gain ratio of sum of squares
中图分类号:TP311文献标识码:A
1 引言
决策树算法在分类算法的研究与应用中受到广泛关注。绝大多数决策树的构建是一种自上而下、分而治之的归纳过程。从根结点开始,对每个非叶结点,根据测试属性判断规则找出其对应样本集中的一个属性作为测试属性,然后由测试属性的不同取值将训练样本集划分成若干个子样本集。每个子样本集构成一个新叶节点,对新叶节点再重复上述划分过程,直至达到特定的终止条件。测试属性的选择和如何划分样本集是构建决策树的关键环节。
最常见的决策树属性分裂方法是信息增益分裂方法,例如ID3[1]和C415[2];在文献[3]中提出了基于最小描述长度理论的新的分裂方法,并介绍了相关度、G统计、χ2统计、G ini’2index、Relief、J2Measure、dN Distance等方法。另外还有R2Measure[4]、False2Positives Criterion[5]等方法。
本文提出了决策树算法ANOVA110和ANOVA210。两种算法与上面分裂方法的不同点主要是基于统计学中的单因素方差分析原理,同时类属性的各个值以数字标号并参与运算。ANOVA110与ID3算法相比较是以最大组间平方和作为在非叶节点上选择测试属性的标准,而不是最大信息增益,其它步骤相同。ANOVA210与C415相比较,是以最大组间平方和增益率作为在非叶节点上选择测试属性的标准,而不是最大信息增益率,其它步骤相同。
2 理论分析
211 单因素方差分析的原理[6]
设某个随机变量的取值与一个因素A有关,因素A取r个不同水平A1,A2,…,A r,在A i下试验得到的是一个随机变量,即X i～N(μi,σ2)(i=1,2,…,r)。又假定总体X1, X2,…,X r相互独立,都服从正态分布,方差相等。在水平
3收稿日期:2007203229;修订日期:2007207209
作者简介:丁顺利(1963),男,河北昌黎人,博士,副教授,研究方向为数据库和网格计算;洪允德,硕士,研究方向为数据挖掘;袁静波,博士,副教授,研究方向为分布式系统、计算机网络和数据库技术。
通讯地址:066004河北省秦皇岛市开发区泰山路143号东北大学秦皇岛分校计算机工程系;Tel:135********;E2mail:dingsl@ https://www.doczj.com/doc/899989914.html,
Address:Depart ment of Computer Engineering,Nort heastern University at Qinghuangdao,Qinghuangdao,Hebei066004,P.R.China
A i 下进行n i 次独立试验,获得n i 个样本X i 1,X i 2,…,X i n i (i =1,2,…,r )。对固定的i ,它们来自同一个总体,即:
X ij ～N (μi ,
σ2),i =1,2,…,r ,j =1,2,…,n i (1)
而且所有的X ij 相互独立。令μ1,μ2,…,μr 分别为r 个水
平下观测样本的均值,则求解因素A 的作用是否显著的问题就相当于检验这样的一个假设H 0:μ1=μ2=…=μr 。总平方和S T 、组内平方和S e 、组间平方和S A 之间满足:
S T =S A +S e (简称平方和分解公式)
(2)S A 越大,则因素A 各水平总体均值μi 差异也越大。其中:
S T =∑r
i =1∑n i
j =1
X ij 2-T 2/n ,S A =∑r
i =1
n i -1T i 2-T 2/n
T i =∑n i
j =1
X ij ,T =∑r
i =1∑n i
j =1
X ij ,n =∑r
i =1
n i
E (S A )=(r -1)σ2+∑r
i =1
n i αi
2
(3)
μi =T i /n i ,μ=T/n ,αi =μi -μ
另外还可证明,无论H 0是否成立,S e /(n -r )都是σ
2
的无偏估计,即:
σ2=S e /(n -r )
(4)212 决策树算法AN OVA110的理论
设S 是n 个数据样本的集合。假定类属性具有m 个
不同值,定义m 个不同类C j (j =0,…,m -1),n j 是类C j 中的样本数。设属性A 具有r 个不同值{A 0,A 2,…,A r -1},可以用属性将S 划分为r 个子集{S 0,S 1,…,S r -1};其中,S i 包含S 中这样一些样本,它们在A 上具有值A i 。如果A 选作测试属性(即最好的分裂属性),则这些子集对应由包含集合S 的节点生长出来的分枝。设n ij 是子集S i 中类C j 的样本数,n i 是子集S i 中总的样本数。
设属性A 的属性值相当于单因素方差分析中因素A 的水平,类属性的取值(用0,1,…,m -1表示)相当于式(1)中X ij 的具体取值。在属性值A i (i =0,1,…,r -1)下进行n i 次独立试验,获得n i 个样本为:
0,0,…,0n i 0
,1,1,…,1n i 1
,(m -1),(m -1),…,(m -1)
n i (m-1)
因此,属性值A i 的样本均值为:
μi =(
∑m-1
j =0
jn
ij
)/n i =T i /n i (5)
属性A 的组间平方和为:
S A =
∑r-1
i =0n
-1
i T 2i -T 2
/n (6)
其中,T i =∑m -1j =0
j n ij ,n i =∑m -1j =0
n ij ,n j =∑r -1i =0
n ij ,T =∑r -1i =0
T i =∑m -1j =0
j n j ,
n =∑r -1
i =0
n i =∑m -1
j =0
n j 。
如果属性A 被选作测试属性,则集合S 分裂后的r 个
子集{S 0,S 1,…,S r -1}差异度越大越好。因为r 个子集差异度越小,所对应的由包含集合S 的节点生长出来的分枝在一定程度上可以合并,所以不必分裂。
如果在属性A 的两个值A i 、A j 下的样本均值μi 、
μj 无显著差异,则它们对应的两个子集S i 、S j 也无显著差异。所以,r 个子集{S 0,S 1,…,S r -1}的差异度表现为属性A 的不同值下的样本均值μi (i =0,1,…,r -1)的差异度,即检验属性A 的作用显著程度。当属性A 的作用越显著时,r 个子集{S 0,S 1,…,S r -1}差异度越大。
S A 的大小反映了属性A 的不同值所对应的样本均值
μi (i =0,1,…,r -1)之间的差异程度。因素A 的作用显著,则各水平μi 差异大,S A 也越大;当因素A 的作用不显著时,S A 的值为零。因此,我们可以通过比较集合S 的不同属性的组间平方和得到最大组间平方和。
若最大组间平方和不为零,则最大组间平方和对应的属性作为测试属性将S 划分,否则S 对应的节点为叶节点。S A 的值可以通过式(6)计算。当n i =0时,对应的子集为空,对应的属性无法预测类。空子集越多,生成的决策树模型预测类的能力会更低。因此,令n i =0的情况对S A 贡献为零。
213 决策树算法AN OVA210的理论
由式(2)、
(3)和(4)得:E (S A )=(r -1)S e /(n -r )+∑r -1
i =0n i ?αi 2
=(r -1)(S T -S A )/(n -r )+∑r -1
i =0
n i ?αi
2
又Θ∑r -1i =1
n i αi 2=∑r -1i =1
n i (u -u i )
2
=∑r -1
i =1
n i (T/n -T i /n i )2=∑r -1i =1
n i (T/n )2+∑r -1i =1
n i (T i /n i )2-∑r -1
i =1
2T T i /n =
n (T/n )2+∑r -1i =1
T i 2/n i -(2T/n )T =
∑r -1i =1
T i 2/n i -T 2/N =S A
所以E (S A )=
r -1
n -r
(S T -S A )+S A
(7)S T =∑r -1i =0∑m -1j =0
j 2n ij -T 2/n =∑m -1j =0
j 2n j -T 2/n
(8)
因为对于一个给定的集合S ,n j 、n 、T 都是确定的,所以S T 是一个确定值,与属性A 无关。当r 的值越大,(r -1)/(n -r )的值就越大。再结合式(7),可得结论:在S A 值不变时,属性A 的属性值的数量越多,则它的组间的平方和的期望值就越大,即如果以最大组间平方和为测试属性选择标准,那么有倾向于取值较多的属性的缺陷。
为了解决上面提到的算法缺陷,我们构造新的统计量S A ratio =S A /E (S A )以有最大值S A ratio 的属性作为测试属性。当最大值S A ratio 为零时,以集合S 对应的节点为叶节点。S A ratio 可称为组间平方和增益率,简写为S A r 。S A r 的值可通
过式(6)、
(7)、(8)计算:E (S A )=
r -1
n -r
(S T -S A )+S A ≥S A S A r =S A /E (S A )∈[0,1](当n -r >0时)
S A r 的值越大,则说明对应的属性对集合S 划分越好。当S A r 值为零时,则对应的属性对集合S 划分无意义。另外,当分母E (S A )为零时,有r =1且S A =0或者S T =S A =0,这两种情况明显地显示S A 对应的属性对集合S 划分无意义,所以可直接令S A r =0;当n -r ≤0时,如果集合S 再划分,决策树中会出现非常多的空分枝,或大部分分枝只有一个样本,因此也可认为对集合S 这样划分无意义,所以同样可直接令S A r =0。为了对决策树进行树剪枝,得到更好的决策树,可以在[0,1]内任取一个值α作为S A r 的阈值(称
为剪枝置信因数)。当S A r ≤
α时,令S A r =0。这是一种先剪枝方法[7]。实验表明,α取017到019的值得到的决策树会更好些。
3 算法实现的部分代码
311 集合S分裂的方法:
集合S先按类属性的取值分裂成m个子集{S′0,S′1,…,S′m-1},然后对各子集S′i(i=0,1,…,m-1)再按属性A的属性值分裂成r个子集{S′0i,S′1i,…,S′(r-1)i}。m个子集{S′0,S′1,…,S′m-1}对不同的属性都可以重用。
312 修改w eka2325的Id3算法java源文件实现两种算法
(1)为Id3类定义的新成员变量。
//返回311节的r个子集{S′0i,S′1i,…,S′(r-1)i}的样本数目。
private int[]splitData1(Instances data,Attribute att,int r) {int[]splitData1=new int[r];
Enumeration inst Enum=data.enumerateInstances();
while(inst Enum.hasMoreElement s()){
Instance inst=(Instance)inst Enum.next Element();
splitData1[(int)inst.value(att)]++;}
return splitData1;}
(2)对Id3原来的成员变量修改部分。
private void make Tree(Instances data)t hrows Exception{…
int classnum=data.numClasses();
Instances[]splitDataadd=splitData(data,data.classAttribute ());
while(att Enum.hasMore Element s()){
Attribute att=(Attribute)att Enum.next Element();
info Gainsmy[att.index()]=
computeInfo Gain(splitDataadd,att,classnum);}
m_Attribute=data.attribute(Utils.maxIndex(info Gains my));
if(Utils.eq(info Gainsmy[Utils.maxIndex(info Gainsmy)],0)) //if(info Gainsmy[Utils.maxIndex(info Gainsmy)]<0.8)
…}
Private double computeInfo Gain(Instances[]splitDataadd,
Attribute att,int classnum)t hrows Exception{
double Info Gain=0,k=0,t=0,t1=0;
int n=0,r=att.numValues();
if(r==1)return Info Gain;
else{int a[]=new int[r];double c[]=new double[r];
for(int j=0;j {int[]splitDataaddmy=splitData1(splitDataadd[j],att,r); int k1=0; for(int i=0;i if(e>0) {a[i]+=e;k1+=e;c[i]+=e3j;}k+=k13j3j;}} for(int i=0;i if(a[i]>0) {t1+=(double)c[i]3c[i]/a[i];n+=a[i];}} double sa=t1-(double)t3t/n; //if(n-r>0&&sa!=0) {double esa=(double)(r-1)/(n-r)3(k-t1) //+sa;Info Gain=sa/esa;}Info Gain=sa;return Info Gain;}} (3)若把312节(2)注释符去掉,再删除if(Utils.eq (info Gainsmy[Utils.maxIndex(info G ainsmy)],0))与In2 fo G ain=sa;语句则为ANOVA210算法,当中018为S A r的阈值,可根据需要改变。对Id3类的toString()、toString (int level)两种方法,添加一些代码则可以统计叶子结点数目、树的大小。 4 两种算法分别与Id3、C415比较 411 实验过程与实验结果 数据集:census2income.data(在ftp://202.118.77. 199的UCI数据(新)中)。数据集预处理:数据集census2 income共有32561个样本、15个属性,每个属性原来的缺省值(用?表示)保留作为一个属性值,每个属性都是分类型(用平台Weka325对属性age、f nlwgt、education2num、capital2gain、capital2loss、hours2per2week离散化后的不同值个数分别为8、20、4、3、9、12)。利用Microsoft Excel改变属性的列顺序,依次用15个属性集中的每个属性为类属性,结合weka2325生成15个数据集,同时以类属性命名。下面只以部分数据集实验结果作讨论。 表1 类属性的数据集 属性属性值 age8 workclass9 fnlwgt20 relationship6 race5 sex2 capital2gain3 education16 education2num4 marital2stat us7 occupation15 capital2loss9 hour2per2week12 native2country42 class2 ANOVA110、ANOVA210分别与平台weka2325的Id3、J4.8(J418是C415修正版8的J A V A实现)算法作比较。比较时,除了ANOV A110、ANOV A210在312节(2)改变部分与J4.8剪枝置信因数取011外,每种算法的其余参数都为weka2325的缺省值。实验机器主要特征:PIII处理器,主频866M Hz,内存128M。实验结果如表2和表3所示。 表2 Id3AN OVA110实验结果比较 数据集分类的准确率(%)10 字交叉检验 预测准确率(%) 建立模型CPU耗时(分钟)空叶子节点数目非空叶子节点数目树的节点数目 Id3 ANOV A 110 变化率Id3ANOV A 110 变化率Id3ANOV A 110 变化率Id3ANOV A 110 变化率Id3ANOV A 110 变化率Id3ANOV A 110 变化率 S ex96142961420751575175013381522168-68155283862971241678786886501940530419653154 education2num1001000100100041211133-681410001616017170 race9618696184-01027411573192-013112115413-6416124413261487111117931187901734062142285411 w orkclass9217192162-0115918859131-0195111685174-501864750145581-4104145741476711326873066758-2187 hour2per2week8215582147-01137169371770121131147189-391957221759037-181251804117779-11459968885567-14117 fnlwgt8215574163-0139221322108-01991719210185-39145385593963621791846718405-013466536671210188 native2country98113981130791178165-0157121939162-25162072919872-411310181103031123480433972-2139平均---0109---0132---5111---3172--0122---1156 表3 J418、AN OVA210剪枝置信因数分别为011,018时实验结果比较 数据集训练数据分类的准确率(%)10字交叉检验预测准确率(%)建立模型CPU耗时(分钟)叶子节点数目树的节点数目 J418ANOV A210变化率J418ANOV A210变化率J418ANOV A210变化率J418 ANOV A210 (空叶子节点)J4 18ANOV A210 hour2per2week531635414211475316353182013571911181-771121203(30)1254 workclass761287518620155761275162201766116116427313873137(18)78169 fnlwgt341343414801413413434132201068144214271156527(0)635 sex8417684111201778315683126201364114115426218310214(36)350249 native2country901468918201738919189154201416192179259157228249(58)251296 race8716887177011871658715620115121217524712254277(77)57316 education2num1001000100100001941132401431616(0)1717 平均--201009--20119--25011798114160143108157190186标准偏差121192104135137102121185 412 实验结果分析 (1)由表2、表3可以看出,ANOVA110与Id3相比较,建立决策树模型时间平均减少51%,其它方面两者几乎一样。ANOVA210与J418相比较,建立决策树模型时间平均减少50%。由于决策树的叶子节点数目及树的节点数目与剪枝置信因数有关,所以我们不能简单地通过变化率比较。ANOVA210与J418的剪枝置信因数范围都为[0, 1],但ANOVA210的剪枝置信因数越大,决策树的叶子节点数目及树的节点数目则越少,而J418则相反。表3说明,ANOVA210算法的两方面的标准偏差都较少。因此,不同数据集用ANOVA210建立的决策树模型的叶子节点数目及树的节点数目相似性更大,即ANOVA210更可靠。 (2)类属性的取值如果不用0,1,…,m-1表示,不会对决策树模型结果有影响。可以通过同时改变312节语句if(e>0){a[i]+=e;b[j]+=e;c[i]+=e3j;}和k+=k1 3j3j中j的取值进行实验验证。例如,取j=01013j+ 100或者j=j+1000或者j=Math1pow(2,j)。实验表明,类标号属性如果取其它值,不会对决策树模型结果有影响。理论如何证明? (3)ANOVA210的剪枝置信因数与r、n有何关系? 312节给出的程序只能对分类型属性数据集进行分类。 5 结束语 结合数理统计中单因素方差分析原理,本文提出决策树算法ANOVA110和ANOVA210。两种算法的运算过程主要是整数的乘法和加法,运算非常快,再次证明了决策树算法有倾向于取值较多的属性的缺陷。大数据集的实验结果证明,ANOVA110、ANOVA210是分别比Id3、C415更好的分类算法,特别是在建立决策树效率方面。 参考文献: [1] Quinlan J R.Induction of Decision Tree[J].Machine Learn2 ing,1986,1(1):8l2106. [2] Quinlan J R.C4.5:Programs for Machine Learning[M].San Mateo:Morgan Kauf mann Publishers,1993. [3] K ononenko I.On Biases in Estimating Multi2Valued Attrib2 utes[A].Proc of t he14t h Int’l Joint Conf on Artificial Intel2 ligence[C].1995.103421040. [4] Ho T,Nguyen T.Evaluation of Attribute Selection Mea2 sures in Decision Tree Induction[A].Proc of t he9t h Int’l Conf on L EA/AL E[C].1996.4132418. [5] Bout sinas B,Tsekouronas I X.Splitting Data in Decision Trees Using t he New False2Positives Met hods and Applica2 tions of Artificial Intelligence[A].Proc of t he3rd Hellenic Conf on A I[C].2004.1742182. [6] 邰淑彩,孙韫玉,等.应用数理统计.第二版[M].武汉:武汉 大学出版社,2005. [7] Han Jiawei,Kamber M.数据挖掘:概念与技术[M].北京:机 械工业出版社,2001. [8] Witten H,Frank E.数据挖掘:实用机器学习技术.第二版 [M].董琳,等译.北京:机械工业出版社,2006. (上接第16页) 器的压力,同时也能减少异常节点所产生的负面影响。未来的工作可以应用此模型在不同的环境下进行仿真,以确定最优的门限值T和确认异常的探测次数n,使整个流媒体实时分发系统能够迅速地从异常中恢复。 参考文献: [1] Su Ao2J an,Choffnes D R,Kuzmanovic A,et al.Drafting Be2 hind A KAMA I(Travelocity2Based Detouring)[A].Proc of ACM SIGCOMM’06[C].2006. [2] Dilley J,Maggs B,Parikh J,et al.G lobally Distributed Con2 tent Delivery[J].IEEE Internet Computing,2002,6(5):502 58. [3] Xu D,Kulkarni S,Rosenberg C,et al.A CDN2P2P Hybrid Architecture for Cost2Effective Streaming Media Dist ribution [A].Proc of SPIE/ACM MMCN’03[C].2003.123. [4] Johnson K,Carr J,Day M,et al.The Measured Performance of Content Distribution Networks[A].Proc of WCW’00[C]. 2000. [5] Zhang Xinyan,Liu Jiangchuan,Li Bo,et al.CoolStreaming/ DONet:A Data2Driven Overlay Network for Efficient Live Media Streaming[A].Proc of IEEE IN FOCOM’05[C]. 2005.
相关主题
文本预览