о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999ꡡ3611ڡVol.36No.111999



Ŵ㷨Ԫ
⡡ơ
ժҪķһŻḶ́Ŵ㷨ģȻͨȫ㷨нŴ㷨ӦõŻ˲Ŵ㷨ԪķҶȨֵʸԪķ.Ŵ㷨ۺͱ뷽ص˵ζŴ㷨иĽ㷨ЧʣȻӰԪʵأʵ֤÷ĶԪкܸߵıʶ.
ؼʣŴ㷨ԪȨֵʸ
ͼţTP301TP18
CONSTRUCTING BINARY DECISION TREES BY
USING GENETIC ALGORITHM
WU Fei and HUANG Ti-Yun
(Management School of Harbin Institute of Technology, Harbin 150001)
AbstractDecision tree is an optimization method. By simulating the nature evolution, genetic algorithm becomes a kind of general-purpose global search algorithm. An approach to construct and optimize decision tree based on genetic algorithm is discussed in the paper here. A genetic algorithm is employed at each nonterminal node of the binary tree to search for weight vector. To achieve high performance, its fitness function and encoding method are discussed in detail, and in particular, much emphasis is put on its operator evolution. The effects of the misclassification rate of the binary tree are discussed and the experiment results show that the binary decision tree constructed based on genetic algorithmcan classify sample-set accurately.
Key wordsgenetic algorithm, binary decision tree, eight vector
1
Ŵ㷨һֻѧԭ㷨1ݣģĵŴѡȻ̭ļģͣͨʹȺ岻ŻҵŽ׼Ž.ΪһЧȫֲŻߣŴ㷨м򵥡ͨá³ǿڲдص㣬ڹũҵΡѧXȷȡ˹㷺Ӧ.
ϵͳŴ㷨Xһ֧һֽṹ򵥡Чʸߵķ2.Ŀǰ˲Ŵ㷨Ծṹ㣬ֱӹķ3ݣû漰ľߺѧϰ.Ŵ㷨ѵԾߺԪķ.
2ڶԪŴ㷨
Ԫս㣨Ҷӽ㣩ͷս㣬սʾԣսߺ.ھķսֵıȽϲֵĽжϴӸýµķ֧սӦֵԣ4.
Ŵ㷨ھУҪȷĿۺͱıƣԼŴ㷨Ļѡ񡢽ͱʵַ.ص۶ԪۺƼ桢ĸĽ.
2.1Ŵ㷨ۺ
ۺŴ㷨ӦΨһӿڣȺиӵһӳĹֱӰЧ.
ԪĴ۾Ҫ׼.xt={x1,x2,,xNt}Ϊнtѵxt=x1tx2txct,cĿxitxti.
1.xtĴΪС#ĿĴС.
xtͬһʱi(xt)=0.tȨֵʸΪw佫xtΪxtL(w)xtR(w):
xtL(w)={x|xxtwTx<0}
xtR(w)={x|xxtwTx>0}.
ȡָĴi(xt,w)ΪxtL(w)xtR(w)ʵļȨƽֵ.
2.ָĴ.
i(xt,w)=p(xtL(w)|xt)i(xtL(w))+p(xtR(w)|xt)i(xtR(w))
У

ʵļi(xt,w)=i(xt)-i(xt,w)ʾtָǰĴʼѡi(xt,w)Ϊۺѡõľߺʹʵļ󣬼f(y)=ixt,w).
2.2ŴӵĸĽ
2.2.1ӵĸĽ
ָĲֽṹ滻¸ĲGAȡҪֶ.һĸPcʣԿѡȡе.λҲȷ.Pcֵһȡúܴ0.60.9֮.
򵥵Ľǵ㽻棬õĲλϳõ㽻棬λĽṹıСϢ룬Чʽ.Ϊ㽻棬Ⱦɫѡȡ㣬Ȼ󽻻еһλһ˵ڵ㽻.ָĽʹýЧÿλϣַӽͬʱ˲λƻ󡢻λıСĲĳ.ʵĽĽʹЧʵõ.
2.2.2ӵĸĽ
ǰһıPmλĳһλĳλ1Ϊ00Ϊ1.Ŵ㷨ЧԣǷֹ㷨Ĵʩ.
ʵŴ㷨ܽϿֲŽ⣬ӾֲŽȫŽ軨ѽϳʱ.ΪЧʣ߽ľȣŴ㷨ֲŽʱؿʹλĩλҪļλ5ݣ൱ڸֵӻһСĲӶпԽСĴҵŽ.
ȺĸΪnжԱĶΪࣺһӦֵϸߵm壬mʱĶ̬Ʊλõķn-mʱȻѡȡλõķ.Ӧֵߵĸ壬ö̬Ʊλõķ㷨ŽӦֵ͵ĸ壬ѡȡλõķ֤㷨ȫ֤㷨Ч.̬Ʊλõķʵ£
gеķܴg*ʾŽһβʱķܴ,GbitLengthΪƱʾĸı볤.
bitint(((g-g*)/G)bitLength/2)+1;
bit1int(rand()(bit-1)+1).
g-g*ʱbitbitLength/2仯1λbit1ȡֵڣbit1֮.
2.2.3̬ʡ
ڼŴ㷨УPcPmȡΪ㶨ֵڸӵĶŻʱЧʲߣҴڡ족Ŀ.ΪЧʺͿٻŽ⣬иݸӦֵ̬ظıPcPm.ȺֲŽʱӦPcPmȺڽռ䷢ɢʱͽPcPm.ңӦֵߵĸ壬Ӧڽϵ͵PcPmʹýԱһӦֵϵ͵ĸ壬ӦڽϸߵPcPmʹýⱻ̭.ȺĶԣֱ֤Ŵ㷨ԣЧŴ㷨Ż.
̬PcĹʽΪ

УfmaxΪǰȺӦֵfavgΪȺƽӦֵfΪнϴӦֵk1k2Ϊ01֮.
̬PmĹʽͬ.
2.3Ŵ㷨ı뷽
뷽Ŵ㷨Ĺؼ⣬ϵܷкЧ.Ŵ㷨ı뷽Ҫ֣һǶƱ룬һǸ.ƱŴ㷨гı뼼ŵǣײͲ״κⶼöƱ룬ǶƱҲһЩȱ㣺Ǳʾ㷨Ч֮ìܣΣƱŴ㷨ڲУҪϵض봮룬㷨ļ㷨Ч.ıʾڼֻɼֳƣзǳߵıʾ.⣬ʾܹʾǳ򣬲㷨вҪת㷨Ч.ǣҲȱ.
ƱʮƱڸԵ.вõǶƱķΪƱĻҶȨֵʸw=(w1,w2,wn)еÿϵwii=(1,2,n),Ӧһ20λĶƴAiwiıʾȴﵽ10-6Ҫ.AiһγɶӦwĶƴA,A=A1A2An.TȨʸwӦĶƴAA=T(w),w=T1(A).
3Ȩֵʸ
Ŵ㷨ԪȨֵʸǰ᣺
1һʼȺʼȺһΪɻȱ.ΪʹĳʼȺȵطֲڽռУгʼĲ涨£
x1x2ΪtԲͬxi=(xi1,xi2,xin,1)Ti=1,2Ȩֵʸw=(x21-wԱ׼ʹȨֵʸÿϵwiֵ01֮䣬㷨ܹҵȺڵ򣬼ӿٶȣ㷨Ч.
2ֹж.й涨ΪһĺȨֵʸŽⲻ仯ֹͣ.
Ŵ㷨Ȩֵʸ㷨£
1.һʼȺp={A1,A2,An},A*ΪǰȺеŽ⣬f*=f(A*)g*=g=0gеķܴg*ʾŽһβʱķܴnﵱǰ.
2.ԵǰȺpеÿһӦֵf(A)=i(p,T1(A)).
3.ʼ⽻MͺO
M?
O?
g=g+1
4.
for i=1 to n do
ӵǰȺpöѡķѡһA
M=MA.
5.
fori=1ton/2do
شӽMѡAA壬ݸӦֵ㶯̬PcսPcн棬
M=M-{A,A}
O=O{A,A尴ոPcĺ}.
6.
O={Ao1,Ao2,Aon}mΪСnĳһ
ڵǰȺpѡmӦֵߵĸ壬Ƹĩλб죻
n-mAoiݸӦֵ㶯̬PmAoiеÿһλPm.
7.滻
ApbAowֱһȺpеŽ²ӴOе⣺
P=(O-{Aow}){Apb}.
8.AbΪһpеŽ
iff(Ab)>f*
then Ab*=f(Ab),g*=ת2
else if g-g*<G,GΪԤȸһƳ
thenת2
elseŽA*b.
4Ԫ
в϶µķԪӶԪĸ㿪ʼŴ㷨ȨֵʸʹýľߠbָĴʼﵽȨֵʸָΪӼ˽Ķӽ㣬ظ˷ֱָֹ˽Ϊս.Ϊ㣬.
3.N0ΪԤ.
4.I1ΪԤСֵ.
5.I2ΪԤָĴʼСֵ.
6.ֹΪi(xt)СI1#xtСN0i(xt,)СI2.
ֹĽΪս㣬Ԧi¹ʽ㣺

ԪĽݽṹC++ʾ£
classTreeNode:publicCObject{
public
classTreeNode*m_left;//ָ
classTreeNode*m_right;//ҽָ
CVectorm_weight;//Ȩֵʸ
CObArraym_sampleSet;//Ŀ
intm_classType;//Ԧi
}
Ԫ㷨£
1.⣻
2.Ա׼
3.ɸ㣻
4.ݹ齨Ԫ
#xt<N0tΪҶ㣬.
i(xt)<I1tΪҶ㣬.
Ŵ㷨tȨֵʸw.
ܰȨֵʸwָxtΪxtLxtR
xtL(w)={x|xxt,wTx<0}
xtR(w)={x|xxt,wTx>0}
ָĦi(xt,w)ֵ.
i(xt,w)СI2tΪҶ㣬ýΪգɽtӽӽ㣬ֱΪxtLxtR.
ԽtӽݹýԪ
ԽtӽݹýԪ.
5.ÿҶ㣬.ؾT.
5ʵ
ԹƱΪ˵Ԫķ.ѡ159ֹƱΪ.ѡƱʲתʡʡʡʲʡʲģʲʡ۾ʡʲʡɶȨΪ۱׼.۽Ϊֱ࣬ʾšֲͨͬĹƱ.
ѡСI1СָʼI2ΪαŴ㷨ĽʡʡGСΪ̶ֱֵΪ0.90.31002.˶ʵ飬ƽ1ʾ.
1Ԫ

СI1СָʼI2
0.050.038.725.48
0.050.022.841.78
0.050.010.690.43
0.040.034.102.57
0.040.022.141.34
0.040.010.520.33
0.030.021.981.25
0.030.010.450.28
0.020.021.350.85
0.020.010.360.23

СI1СָʼI2ֱӾԪĴʣӱ1пԿıСI1СָʼI2ԿƶԪĴʣʹϵͳΪܿϵͳ. 
6
Ŵ㷨ԪķŴ㷨˸ĽԵ㷨ٶ.÷˱ʶ׼ȷʺٶȣΪṩһּ򵥡ͨáЧķ.ص㣺Ŵ㷨ĸĽŴ㷨Ȩֵʸ۸ĴָĴʼԪܶԪĴʿΪ.
*õȻѧ(Ŀ79670023).
߼飺ƣŮ19735ʿоҪоΪŴ㷨Ȼ⡢ܾ֧ϵͳ.
ƣУڣʿʦҪоΪ֧ϵͳϢϵͳ.
ߵλҵѧѧԺ150001
ο
1Goldberg D. Genetic Algorithm in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley, 1989
2¶죬㣬. ھѧϰеĲɼԵɢ. о뷢չ1998, 35(5)403407
(Chen Enhong, Wang Qingyi, Cai Qingsheng. Test generation and discretization of continuously-valued attributes in decision-tree-based learning. Journal of Computer Research & Development (in Chinese), 1998, 35(5):403407)
3Ф£. Ŵ㷨.о뷢չ1998, 35(1):4952 
(XiaoYong, Chen Yiyun. Constructing decision trees by using genetic algorithm. Journal of Computer Research & Development (in Chinese), 1998, 35(1): 4952)
4Chai B B, Huang T, Zhuang X H, Sklansy J. Piecewise linear classifiers using binary tree structure and genetic algorithm. Pattern Recognition, 1996, 29(11): 19051917
5ΰ. Ŵ㷨еӦ.պѧѧ1998, 24(4)434437
(Jia Wei et al. Genetic algorithms and their application in softwaretest data generation. Journal of Beijing University of Aeronautics and Astronautics (in Chinese),1998, 24(4): 434437)
ԭյڣ1999-01-13޸ĸյڣ1999-08-08.
