ѧ
JOURNAL OF SOFTWARE
1999ꡡ1011ڡVol.10No.111999



ԿռϵĹѧϰ㷨
Ȩ Զ Ҷ硡
ժҪоԿռϵĹѧϰ㷨ȼоԿռϵĹѧϰ㷨Ŀĺ壬ѧϰеһЩƹ㵽Կռ䡣ڴ˻ϣоԿռɢ⣬֤ԿռСɢNP⣬ϢغĸӦõɢ⣬˻ϢصԿռ伫С㷨ԿռϵĹѧϰ㷨,ֵʵ
ؼʡѧϰ㷨Կռ䣬ϢأNP⡣
ͼšTP181
A Rule Learning Algorithm on Continuous Attributes Space
QUAN Guang-ri1 LIU Wen-yuan2 YE Feng2 CHEN Xiao-peng1
1 (Weihai Campus Harbin Institute of Technology Weihai 264200)
2(Department of Computer Science and Engineering Harbin Institute of Technology Harbin 150001)
AbstractThe rule learning algorithm on continuous attributes space is studied in this paper. First,  thepurpose and the importance of studying rule learning algorithm on continuous attributes space are briefly introduced, and then some basic concepts in the theory of rule learning are extended to the continuous attributes space. On this basis, the authors study the problem to divide continuous attributes space, and prove that the problem of min dividing continuous attributes space is a NP hard problem. The concepts of information entropy and infinite normed apply to the problem of dividing continuous attribute space and a new algorithm of dividing continuous attribute space based on the function of information entropy are presented. At last, a rule learning algorithm on continuous attributes space is presented and the data results of the experiments are given.
Key wordsRule learning algorithm, continuous attribute space, information entropy, infinite normed, NP hard problem.
ռ仯˹еҪо.ʾѧϰ㷨ͨӵѵʶ.ʾѧϰϵͳѧϰٶ뾫ԼʶٶȲõѧϰ㷨,ѵϵĹģռ.ʵʲݽɸѡ͸ʵѧϰٶʶ𾫶Լʡ洢ռҪֶ.,ӵɸѡԿռŻʶϵͳ³.
1987,QuinlanоԿռϵľѧϰ㷨ʱ,˻ϢصԷָ㷨1,2.FayyadQuinlanĻܹӿɢٶȵĸĽ㷨24.ǰ˹Ļ,ϢغĸӦõɢ,˻ϢصԿռ伫С㷨.Ŀָзֹϸ,ԱѧϰϵͳľԼʶϵͳ³.ڴ˻,ԿռϵĹѧϰ㷨.
1 
,j=1,2,...,n,Ϊjxjֵ(ȡֵΧ),E=D1D2...Dnnάռ,EеԪe=(v1,v2,...,vn),vjDj.PENEEӼ,Ϊ,ֱΪͷ.
1. DjӼAjΪDj޸Ĳ,ҽAjΪ޸(䡢뿪)Ĳ,䲢.
Ȼ,Aj,BjΪDj䲢,AjBj,AjBjDj-AjDj䲢.
2. ѡΪ{xj=Aj}{xjBj}Ĺϵ,Aj,BjΪ䲢,ҹ涨{xjBj}={xj=Dj-Bj}.ʽ1ѡӻ򼸸ѡӵĺȡʽ,Ϊ,,N={1,2,...,n}.ע:(1) ڹʽLвֵ,涨ȡֵΪԵֵ,κjN,,ȼL߼ѡ{xj=Dj};(2) ӿԿǹʽͳһ,e=(v1,v2,...,vn)={xj={vj}}.ѡS={xj=Aj}һʽL={xj=Aj}ҽjJAjAj.֪ʽL={xj=Aj}L={xj=Aj},LL䵱ҽJJ䲢Ҷκj,jJ,AjAj.
3. һʽΪ(֪ӼPENE)һµ,ǷNEеκη.һΪһµ,ÿһʽһµ.һΪ걸,κһPEеӶ,ĳһʽ.һһµ걸,һ걸.
4. ֪NEһʽL={xj=Aj}.NEÿһjN,jJ,Ԫء*NEеjеԪ;jJ,á*NEеjAjԪ.õľʽLž,ΪEM(L).ž,ֱԲͬеķԪɵļϽEM(L)һ·.
׼,4еĹʽe+ʱ,͵õe+žEM(e+).
5. EM(L)һ¹ʽLž,EM(L)еĳһֻһԪ,ƸԪΪѡԪ.
EM(L)ıѡԪһиLĹʽеĶӦѡ,Ҫ.
6. ֪ʽL={xj=Aj}ʽF={xj=Bj},LFӦѡӵȡֵϲõһµĹʽ,ΪLFĺϲ,ΪLF.LF={xj=AjBj}={xj=AjBj}.ע,κj,jN,jJJ,{xj=AjBj}={xj=Dj}ʡԲд.
1. EM(L)һ¹ʽLž,һEM(L)е·ǹʽL֪ʽӳ.ʽLǹʽL,EM(L)еһ·ضҲEM(L)еһ·.
2. ʽLȸǹʽAָǹʽB,ҽAB.
ף59жž۽о,žҪ,.
ԿռϵѡɢԿռϵѡӵʽһµ,ʽ.,A1={x11,4}ʾɢռϵһѡ,B1={x1٣0,1)(2,3)ȣ6,8}ʾռϵһѡ.
7. EM(L)һ¹ʽC={xj=Aj}ž,path={xj=Pj}EM(L)еһ·,׼ɵĹʽL·pathڹʽCԼɵĹʽ,ΪL=L(path,C).Aj䲢,PjɢӼ.
(1) jJP,Dj-AjеҽѡPjԪصʱ,Ĳ,Bj.
(2) ɹʽL=L(path,C)={xj=Bj}.
2 Կռ仯ʽ㷨
2.1 ԿռСNP
E=D1D2...Dnnάռ,ixiֵ(ȡֵΧ)(i=1,2,...,n)ʵ,EеԪe=(v1,v2,...,vn),viDi.PENEEӼ,Ϊ,ֱΪͷ.
8. PE,NEֱʾ뷴,

d(PE,NE)Ϊ뷴µľ,뷴ľ.СNEΪⷴ.
Ȼ,d(PE,NE)=0,һ뷴,PENE.PE뷴NEd(PE,NE)=0ʱ,뷴ཻĻ򲻿ɷ.
Ϊ۷,ǹ涨ָС,ָ.
9. ĳ˻ռΪС˻ռ,ƼСռ.
10. һԿռлֺ,ÿһС˻ռ䶼ͬʱ뷴,ƴ˻ΪɷĻ;,ΪɷĻ(һС˻ռ,ͬʱ뷴).
11. XE=D1D2...DnϵӼ,LiDiһ,ֱʾLiұ߽,

ֱӼXLiϵȷȷ.
12. ÿһֵ(j=1,2,...,n),kj(j=1,2,...,n)ȷֱʾjԵĵi(=li-1,li),i=nʱ,=ln-1,ln),,õԿռ仮ֳΪȾ໮,K(k1,k2,...,kn)ΪK.
3. d(PE,NE)=d0,Ⱦ໮K(k1,k2,...,kn)ܹ뷴.kj=ۣDj/d+1(j=1,2,...,n).֤.
ӿռСָ:E=D1D2...Dnnάռ,(i=1,2,...,n)ʵ,PE,NEֱʾ뷴,ki(i=1,2,...,n)ʾָDiĸ,ܹ뷴PE,NE仮,ʹk1.k2.....knС仮.
ָСָ:E=D1D2...Dnnάռ,(i=1,2,...,n)ʵ,PE,NEֱʾ뷴,ki(i=1,2,...,n)ʾָDiķָĸ,ܹ뷴PE,NE仮,ʹk1+k2+...+knС仮.
4. ӿռСָͷָСָⶼNP.
Ϊ֤4,ȼ򵥵ؽף10,11еĽ(Ϊ˷,,ף10,11еĽʵĸı).
Ƕֵɢռ,={0,1}(i=1,2,...,n),PE,NEֱԵ뷴,PENE=.
13. ǲɵĳ˻ռ,ӡPEͷӡNE,PEͷNEڳ˻ռǲɷ,,PEͷNEڳ˻ռE*iǿɷ.
ѡ:ڲɵĳ˻ռE*i=D*i1D*i2...D*ik,ܹPEͷNEάСĲɵĳ˻ռE*i.
. ѡNP.֤οף10,11.
4֤:E=D1D2...DnԿռ,Di=0,1(i=1,2,...,n);PENEE뷴;(1) PENE=;(2) ӡPEͷӡNE.ѿ,ʽѡԿռԼµ뷴,ӿռСָͷָСָⶼȼѡ,Ƕ˽ѡ.,ѡNP.,ӿռСָͷָСָⶼNP.
2.2 ϢصԿռָ㷨
2.2.1 ָ㷨ʽ׼
(1) ѡϢĻֵзָ,ӿָ,ٷָĿ.
(2) һĳС뷴֮ľd(PE,NE),ٽиָ.һ׼ָֹܹϸ΢,ʹѧϰʶϵͳӾõ³.
2.2.2 Ϣصָ㷨
1. PE,NEֱʾ뷴,Li(i=1,2,...,n)ʾ,P(L),N(L)ֱʾL=L1L2...Ln뷴ӵļ,Si(i=1,2,...,n)DiΪԪصļ,ֱʾLiұ߽,ֱʾӼP(L)N(L)Liϵȷȷ;ʼP(L)=PE,N(L)=NE,Li=Di,Si=(i=1,2,...,n).
2. P(L)=N(L)=()d(PE,NE)(i=1,2,...,n),PE=PE-P(L),NE=NE-N(L),ת8;,ÿ()d(PE,NE)л,,jJ(ע:Jʾd(PE,NE)jļ;LjΪʱAjҲ);
3. ÿֵϢE(Lj),jJ.

pAj,nAjֱʾAjе뷴;pBj,nBjʾBjе뷴;PL,NLʾL=L1L2...Ln뷴.I()=0.
4. лѡϢĻ,ѡϢСĻ.СĻֶӦԼΪr.
5. I(Ar)=0I(Br)>0,P(L)=P(L)-P(Ar)(N(L)=N(L)-N(Ar)),PE=PE-P(Ar)(NE=NE-N(Ar)),Sr=Sr-{Lr}+{Ar}+{Br},Lr=Br;ص2(ע:I(Ar)=0,,ArֻLеӻֻLеķӻΪ;P(Ar),N(Ar)ֱʾLAr뷴ӵļ).
6. I(Ar)>0I(Br)=0,P(L)=P(L)-P(Br)(N(L)=N(L)-N(Br)),PE=PE-P(Br)(NE=NE-N(Br)),Sr=Sr-{Lr}+{Ar}+{Br},Lr=Ar;ص2.
7. I(Ar)>0I(Br)>0,P(L)=P(Ar),N(L)=N(Ar),Lr=Ar,Sr=Sr-{Lr}+{Ar}+{Br},ص2.
8. I(Ar)=0I(Br)=0,PE=PE-P(Ar),NE=NE-N(Ar),Sr=Sr-{Lr}+{Ar}+{Br},ת9.
9. PE,ѡe+PE,ѡe+С˻ռL=L1L2...Ln,LiSi,e+Li(i=1,2,...,n),P(L)N(L),ص2;(PE=),Si(i=1,2,...,n),ͣ.
6. ָͣ,ÿһ䱻ָɻཻ.֤.
7. d(PE,NE)=d>0,ָ㷨ڲεָܹ뷴.֤.
8. СռL=L1L2...LnһЩ,C=xj=Lj},J={1,2,...,n}һ¹ʽ,ʽCڷENµžһ·.֤.
14. XEӼ,Kʾĳһָ㷨,ʾָ㷨KõĵjԵĵi,XɣʾX,jֵڵĿ.

fj(t,X)ΪӼXڵjDjϵķֲ.Xĵjֲ.
15. Dj(j=1,2,...,n)ĻཻĲD=D1D2...Dn϶ĺ

F(t,X)ΪӼXDϵķֲ.Xķֲ.
16. XǸӼ,ʾָ㷨õĵjԵĵi,LjʾjԵٰһXӵĲ,,L(X)=L1L2...LnΪXСӿռ.
17. PENEǸͷ,PEʾPEӼ,L(PE)=L1L2...LnʾPEСӿռ.NEĵj(j=1,2,...,n)LjԪضá*,õľӼPEڷNEµž,EM(PE).
2.3 ɹʽ㷨
1. E=D1D2...DnԿռ,PENEǸͷ,Iijʾָ㷨õĵjԵĵi,PEʾPEӼ.SNʾֻӵɵļ,ֻžзԪصɵļ.

2. PEڷNEµžEM(PE).
3. S=,SN.
4. SNڵ,ϲһ,ֱûڵΪֹ.
5. žбѡԪ(žĳһֻһԪ),SNѡ÷ӵ,,SNѡĵ;NEɾȥڵķ,S=S+{Iij}.
6. ,򷵻ص5;,ת7.
7. ɹʽ;ͣ.
3 ԿռϵĹѧϰ㷨
3.1 ѧϰ㷨CRA
ԿռϵĹѧϰ㷨(ѧϰ㷨,CRA).
1. ԿռE=D1D2...Dn,֪PEͷNE,ָ㷨仮.
PE=PEʾ,NE=NEʾ,EMʾž,F(t,PE),F(t,NE)ֱʾͷķֲ,ʾָ㷨õĵjԵĵi,XɣʾX,jֵڵĿ;
2. ͷķֲF(t,PE)F(t,NE);
3. ѡʹ(PE-F(t,PE))F(t,NE)ij(t);
4. PENEɾjֵڵ,ɾ,ͷķֲF(t,PE)F(t,NE);
5. NE䲻,򷵻ص3;,ɹʽ㷨;
6. PE,ͣ;,PE=PE-PE,NE=NE,PE=PE,ص2.
9. 뷴ǿɷ,d(PE,NE)=d>0,ѧϰ㷨CRA޲ͣ,һ걸.֤.
3.2 ѧϰ㷨ʱ临Է
PNֱʾ뷴ĸ,Djʾj(j=1,2,...,n)Djĳ,d=d(PE,NE)뷴֮ľ.
ָ㷨ļʱ临ӶΪ


ɹʽ㷨CRA㷨õļʱ临ӶΪ 

ɴ˿ɼ,ʹPEΪֹ,CRA㷨ļʱ临ӶΪ

4 еӦ
1ף12иֻϷʵ.Ϊ˵ϢصԿռָ㷨ԿռнпռָĹ,˵ѧϰ㷨CRAԿռʶĹ(ѧϰ).
1 ֻʵ

SymptomFault
S1S2S3S4S5S6S7S8S9S10S11D
10.800.10.11010.10.9101
20.800.10.10.800.80.10.80.901
30.500.10.10.8010.10.70.901
40.800.20.21010.10.9101
50.500.10.10.800.90.10.70.900
60.50.900.800.80.10.90.50.10.80
70.50.900.800.80.10.50.50.20.90
80.60.700.900.50.10.80.40.10.70
90.40.700.700.50.10.70.30.10.61
100.30.900.90100.80.100.90
110.20.700.80100.8000.80
120.20.600.600.900.7000.60
130.40.40.30.6000.10.10.200.10
140.40.50.30.70.05000.10.100.10
150.40.60.40.900.800.30.100.90
160.30.80.310100.10010
170.30.40.310100.10010
180.60.30.90.30.3000000.60
190.70.30.90.30.2000000.80
200.70.60.90.6000.20.50.300.91
210.70.60.90.7000.30.60.400.81

Ѿ֤,ָ㷨ļС˻ռֻͬһ,ٰ1ӵļС˻ռɿһ,ĿڼٲμѧϰĿ,ѧϰٶѧϰ.
ͨͼ1Կ21ӵѧϰ,ָ㷨11ӵѧϰ.

S1S2S5S7S9Contained Examples
 
PE101211,4
011112
001213
000019
1001121,22
 
NE001115
010016,7
100018
0100010
0000011,12,13,14,15,16,17
1000018,19

ͼ1 ӵļС˻ռ
ͼ1Ĺѧϰ,ѧϰ㷨CRAõıʾӵĹ3ʽ.
x10ݡģx21ݡģx50ݡģx90,
x11ݡģx21ݡģx71ݡģx90,
x10ݡģx21ݡģx51ݡģx90.
ʽתʽĹʽ:
{S1=(0.5,1}{S2=0,0.8}{S5=(0.5,1}{S9=(0.25,1},
{S1=0,0.5}{S2=0,0.8}{S7=0,0.15ݡ(0.95,1}{S9=(0.25,1},
{S1=(0.5,1}{S2=0,0.8}ģS5=0,0.5}{S9=(0.25,1}.
ݵѧϰϵͳ³Է˱Ƚʵ.صĸ.
18. ָ,ŵѧϰСӡ֮ľ,ŵe*ȵMin{d(e*,e)eE},Eѧϰ.
19. e*ʾһŵ,eʾѧϰe*.e*eʶһµ,e*Ϊܹȷʶ,,e*Ϊܱȷʶ.
20. 㷨ʶָ,ʶϵͳܹȷʶ(ŵ)Ŀʶ(ŵ)֮ıֵ.
ڲúϵͳовɼΪѧϰ,ʶϵͳݵ³Էʵ,ʵ2.ѧϰĸΪ1 000;ԿռάΪ12,ֵȡֵΪ0,1;ԿռάΪ1,ֵֻȡ롰쳣ֵ.ʶӼǶѧϰʵؽΪõ5 000ɵļ.
2 ݵѧϰϵͳӰ

ŵķȡ0.030.040.050.060.070.080.090.1
㷨ʶ(%)9795949290898685
Quinlan㷨ʶ(%)9289858381797572

2,(һΧڵ)³Է,㷨Quinlan㷨бȽԵ.,ĻϢصָ㷨ԿռϵĹѧϰ㷨ǷǳЧ.
5 С 
оԿռϵĹѧϰ㷨,֤ԿռСNP,ȻϢصԿռ伫С㷨.ڴ˻,ԿռϵĹѧϰ㷨,˸㷨ļʱ临.ʵ,㷨֮Ч.
Ŀоõ863߿ƼĿú̿ѧ.
߼飺Ȩ,1962,ʿ,,ҪоΪ,ѧϰ.
Զ,1968,ʿ,ʦ,ҪоΪݿ,ѧϰ.
Ҷ,1960,ʦ,ҪоΪ˹߼,ѧϰ.
,1970,ʦ,ҪоΪݿ.
ߵλȨաҵѧУ  264200
ԶҶ硡ҵѧѧ빤ϵ  150001
ͨѶϵ:Ȩգ 264200,ɽʡйҵѧУ
ο
1 Quinlan J R. Inductive learning of decision trees. Machine Learning, 1986,1(1):81106
2 Quinlan J R. C4.5: Programs for Machine Learning. Ver.1. San Mateo, CA: Morgan Kauffmann Publisher, 1993. 170247
3 Fayyad U M, Irai K B. On the handling of continuous-valued attributes in decision tree generation. Machine Learning, 1992,20(8):88102
4 Utgoff P E, Berkman N C, Clouse J A. Decision tree induction based on efficient tree restructuring. Machine Learning, 1997,29(1):544
5 .ʾѧϰž.ѧ,1991,14(6):3742
(Hong Jia-rong. Theory of extension matrixes in learning from examples. Chinese Journal of Computers, 1991,14(6):3742)
6 ,ԭ,.ʾѧϰĹž㷨ʵ.ѧ,1994,17(9):8388
(Zhao Mei-de, Li Xing-yuan, Hong Jia-rong. An algorithm of generalized extension matrixes in learning from examples and implementation. Chinese Journal of Computers, 1994,17(9):8388)
7 Ȩ,,Ҷ.ϸ㷨.ѧ,1998,9(2):156160
(Quan Guang-ri, Hong Bing-rong, Ye Feng et al. A heuristic function algorithm for minimum set-covering problem. Journal of Software, 1998,9(2):156160)
8 Ȩ.ڹѧϰо۲ʿѧλģ.ҵѧ,1998
(Quan Guang-ri. Research on neural networks based on rule learning Ph.D. Thesis. Harbin Institute of Technology, 1998)
9 Wu X D. Optimization problems in extension matrixes. Science in China (series A). 1992,35(3):363373
10 Chen Bin, Hong Jia-rong, Wang Ya-dong. Minimum feature subset selection problem. Journal of Computer Science and Technology, 1997,12(2):123128
11 ±,.ʾѧϰ󸴺⼰㷨.ѧ,1997,20(2):128131
(Chen Bin, Hong Jia-rong. Maximum composition problem in learning from examples and the algorithm. Chinese Journal of Computers, 1997,20(2):128131)
12 ,,ʷֵ.֪ʶ.:廪ѧ,1993.120200
(Yang Shu-zi, Ding Hong, Shi Tie-lin et al. Diagnosic Inference Based on Knowledge. Beijing: Tsinghua University Press, 1993. 120200)
1998-05-04յԭ,1998-11-25յ޸ĸ
