о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 9 Vol.36 No.9 1999



Ĺȡо
ԴɡŸ
ժҪΪ硰⡱ЧֶεĹȡ˻ڽṹֽӳȡĸ㷨ǵĻ˼벢ǵӣȨֵĻCSW㷨ЧֵĹȡ.CSW㷨ӦIRISȡõЧ.
ؼʡ磬ȡṹֽⷨӳ䷨
ͼšTP18
AN APPROACH TO RULE EXTRACTION OF NEURAL NETWORKS
HUANG YuanXIAO Rong, and ZHANG Fu-Yan
(State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing210093)(Institute of Multimedia Computing Technology, Nanjing University, Nanjing210093)
AbstractIn this paper, the rule extraction of neural networks is discussed, which is an effective method to avoid the shortcoming of being black boxes. Techniques based on decompositional and input-output mapping approaches are studied and their fundamental concepts and evaluates their performances are generalized. Based on similar weight approach, the CSW approach is proposed to efficiently solve the rule extraction from continuous-input neural networks. CSW is applied in IRIS Flower Classification Problem,and experiment results show that rules extracted by our method are accurate and comprehensible.
Key wordsneural network, rule extraction, decompositional approach, input-output mapping approach
缼ڸõ㷺Ӧãͨѵķѧϰȡ֪ʶֱԡԡ³ԺͿԣݲܹģ.ͻڷŵĴͳAIȣ缼Ҫȱǻõ֪ʶһϵӺȨֵУ޷Ϊû⣬ģͶû˵һ.ȱ͸ԣھ;֧ԼڰȫҪܸߵĹؼӦ÷棬缼ΪǲɿģӦܵһ.ˣбҪһͻƣùȡȨֵΪ֧Ӧṩľ˵ΪؼӦṩĿŶȺֶΣΪڷźͻӵAIṩһЧļɷ.ͻƵһֽǽͬʱһ򵥵Ļڹϵͳľ߲ģʽ۸ڹϵͳ÷һϵַҪ󿪷Ϊͬһ⽨ֽܴҰѾ߹̺ͽ͹̷ѿ͵ڹĽṹȱԣѽٲ.һַǱ۵Ĺȡѵõ缰ѵʾʩһ򹤳ݵ͹򣬴ӶԴ׼ȷķ.ͼԹȡĸ㷨һЩͱȽϣڴ˻ֵһµĹȡ㷨CSW㷨IRISʵַ֤ǼЧ.
1еĹȡ
԰ȡΪ.һǻڽṹֽĹȡؽΪλֽΪɵļϣÿһȡЩ.򵥵һ㷨FuӼ1ݣ˼ѰӵӼʹȨֵͳԪֵ.ǰнֵʾΪoutput=f(net)=net=i.xi-ȣЦǽֵ.ȨֵĳϴԪֵĻԪ״̬Ǽģ״̬δ.Ӽÿ㶼ʵһŹӦĸǹýṩĳӼǰ.ȡ̾ΪÿѰʹ㹻.ȱǵϸʱӼĿռͻúܴ󣬲ϱը⣬㷨ӶΪO(2n).Ϊ˼Ϊһޣƹȣڵ¼Ϊk㷨ӶȿɽΪ,ַȱǿܽ͹ͨԣΪĳЩ˵㹻ȲܹҵʵĹ.ӼһȱǼʹģȽСҲȡĹұﲻΪTowellMOFN2ݣ÷йıʽǣif (NǰMȷ) then .˼Towellзֿ԰ѹǰ࣬ʹһǰÿǰᶼͬҪԣеԱ.򻹿Ըرʾif N morethan(PosSet,NegSet)thenPosSetNegSet͸ļϣȥN۳.ӼȣMOFNĹС13㷨СĹɶԺ.ȱԵǻ֪ʶѵиؽı䣬򽫽ϺĿ. MOFNҪȨֵǿɾģͨ磬ҪáԹȨ3ݷѵ磬ķڷ縴Ӷ֮һЧľ⣬粢ٽȨֵѵЧ.
ڽṹֽķֳɸҪ͹ϲڸ㷨ӶȴҹԺܲ.෽У֦pruneʮҪ.RX㷨4Ȩ˥weight-decayBP磨ȨĴСӳӵҪ̶ȣȻ޼Ԥ⾫ȲɾҪӣڶгּ򻯵£زļֵо࣬ݲͬز㼤ֵİ취ѰҴ㵽زʹز㵽Ĺ.ʵз㷨ڲĹȡЧ൱ߣڲİ취㷨Ҫ֦ǳ򻯣縴Ӷȵ㷨Ӷȳʼμ.
һ෽ǻӳĹȡ㷨෽ͻڽṹֽķ֮ͬزڲṹֱ֮ѰҶӦȡӦĹ.дԵ㷨SestitoȨֵ5ݣַڵӵȥڵбȽϣĽCSW㷨ʱнϸ.CravenShavlikѧϰķȡ6ݣȡΪһѧϰOracleEXAMPLES()һʾѵõԴʾз࣬жһʾǷѱ򼯸ǣûʾʼһδӹǰɾһOracleSUBSET()жϸùǷ籣һ£Ծܹеʾ˵ǿɱɾģ˵ǲɾģӵǰȥظֱǰﵽ򲢽˹뵽.ַȫǴӵϵģʵв޸Ĺù򼯺ıȽȷĹǷﵽҪ.Զ·ȣдӹЧֹԶµķйǰϱը⣬ڹнΪձĹļʱ.
2 ֵCSW㷨
һ͵BP磬mԪ(x1,x2,,xm),زhԪ(y1,y2,,yh)nԪ(z1,z2,,zn)jΪԪyjֵijԪxiԪyjȨֵjkԪyjԪzkȨֵԱʾΪ
F:mn;F(x1,xm)=(z1,zn)
zk=gk(yjjk)  yj=fj(xiij+j)
(1)
Ϊ˱ȽĹϵȨֵڵӵȥm+nڵ(x1,x2,,xm+n)ڴʱڵڵͬһϣԾͽ׵óĳһЩй.Ըı˽ṹѵԭڵ¼ڵȨֵƣͿΪһ֮ڹ.ʹƽSSEжϽڵ֮ȨֵƹϵԪaԪb(Ѽ㣩ԶԪƽΪ
SSEab=(bj-aj)2
SSEʾab֮ӽ̶ȣclosenessSSEֵԽС˵abĹԽ.ѵС֮ĹϵȽϷɢƾSSEȷһ֮ĹHebbȷ֮ȨͨѵĸԭѵģʽԸֵȡѵȷЩ֮䲻ܴڹ.ڸѵʱһʡȥز㣬ԪԪ֮ȨֵΪ޹ȨֵΪ޹ԣirrelevanceĶֵԽС˵ĳĹϵԽ.Ԫ޹Ȩֵƽ͵ĳ˻ж֮ƹϵ
Productab=WeightabSSEab
Productabֵӽ0˵a,bһ֮ڹ.ȨֵӦڶʶLEDź򶼲׶һǿĹ.ʹȡ㷨һȨֵֻӦڶֵ磬ʵӦУԲɱؾ֣ںܶжҪãڷѧϰƵһҪƾԺܺõش룬ӴԵгȡкǿʵ壬ֵ磬SestitoȨֵĸĽ7ݣõĹʽΪ
Ri:Ifvmini1ai1vmaxi1)ġģvmininiainivmaxini)thenbi
vminikvmaxikֱѵзϹRiǰṹͽ۵ʾaikСֵֵ.ԿͨѵȷǰΧķѵдɸ쳣ʾͻ󽵵ľ.
ԴCSW(continuous similar weight).CSWȶеֵɢȻֵתɶֵ磬ӦȨֵӦٽǰתΪ.ֵɢУǲæ2ͳжϷгͻ.һʾ˵AǴɢlAɢCʾķ࣬kǷAijAȡֵڵiɢʱjʾmʣ1,l-1ݣmm+1гͻRi=AijCj=AijֱΪǵi͵jʾAijķֲ.һɢҪþٵɢ䲻ͬCSWΪ˱֤ݵͲľȣҪ϶ɢ.ԾIRISֲʶΪϲһԤ趨ҪԶsigLevelʼʼAʾепȡֵΪһɢ䣬ϲЦ2СsigLevel䣬𽥼СsigLevelֱɢݵĲһʴָΪֹ.Ϊ˼پʧ֤ѧϰЧȡ=1%sigLevel=0.52=1.386.ĸķֱΪ75631ʾ.
1

Sepal length4.34.955.55.86.37.1
Sepal width22.52.933.4
Petal length134.54.855.2
Petal width0.111.8

ɢ乲21ӦȨֵڵӵ㣬ɵ24-3-3.Ըı˽ṹѵȨֵSSE2ʾԪ޹Ȩֵƽ͵ĳ˻Productabж֮ƹϵProductab=WeightabSSEab.CSWǻԭеȨֵһĽԭйǰȱnot Anot BǰᣬǶProductֵܴ㣨2Input node13,17,18ȡΪǰǰȻͬһԵɢнΪƽǰͬһȡֵΨһԣûбҪǰ.⣬ԭеȨֵǰֻǡ롱ϵĹȻྫȺܸߵǵʾ٣ǶƽΪǰзྫȷȳֵԡ򡱹ϵǰ.򻯲ĹΪ
2

SSEOutput node 1Output node 2Output node 3
Input node 11.97626815.57815718.978373
Input node 23.33840515.22951312.616628
Input node 35.6811308.45829220.103409
Input node 48.5378228.53367715.842235
Input node 57.39430610.51699813.258282
Input node 69.69203111.6273049.247134
Input node 79.46612315.7942696.303343
Input node 83.73595411.41208718.470940
Input node 99.70263013.0463168.251924
Input node 109.7606207.60184015.547240
Input node 117.35725010.49759013.332457
Input node 124.21775813.00580512.394973
Input node 131.25670932.43304118.851028
Input node 1413.0720807.55853114.857869
Input node 155.15187215.1902648.442115
Input node 168.24999510.45522513.144000
Input node 174.95439820.8318829.698025
Input node 186.33863925.1120537.191267
Input node 193.28326217.28154412.182094
Input node 207.5312403.24760918.344231
Input node 219.60605821.3672316.042622

1: If (1petal length<3 ) then iris=setosa
2: If (3petal length<5) AND (1petal width<1.8) then iris= versicolor;
3: If (sepal length7.1) OR (petal length5.2) OR (petal width1.8) then iris= virginica.
򼯵ķྫ㷨ıȽ3ʾCSWȡĹ򲻽⣬к㷨൱Ԥ⾫.ͼ1˴CSW㷨SestitoSWĸĽ㷨ID3㷨ķྫȵıȽϣԿCSW㷨нǿĿCSWɢ̵ݴԺ㷨ĿԾ.
3IRISԽȽ

㷨SetosaViginicaVersicolorƽԤ⾫
CSW10095.339496.44
GVS100949496
IVSM10093.3394.0095.78
NTgrowth10093.5091.1394.87
Dasarathy100988694.67
C410091.0790.6193.89


ͼ1IRISȽ
3
ġ⡱Ӱھ򡢾ֵ֧ȹؼĹ㷺Ӧãȡǽ⡱Чֶ.һ磬ṹֽⷨ㷨СһЩÿֻһ磬֮ĹϵǵģڹǰвؿǷ.ڻһ༶ϲ⣬㷨縴Ӷȵƣز϶ʱȡĿɶԽúܲ㷨ȡǰ֦ɾԤʮҪӳ䷨ģƣ㷨󣬱СĽռ䣬 CravenһʺѵС.ȨֵͬһϽбȽϣЧ෽ȱݣCSWȨֵչֵ.ʵ÷нϺõķྫȡԺͿ.ȡ滹кܶ๤Ҫ罵㷨ĸӶȣȡĿԼ㷨ԣоȡĹ򼯵׼ѵд綯̬ȡԼʱ粢ܵȶǽһо.
߼飺ԴУ19738ʿооΪھ.
ɣУ197212ʿооΪھ.
ŸףУ193911ʿʦҪоΪý弼ͼѧ.
ߵλϾѧ¼صʵҡϾ210093
ϾѧýоϾ210093
ο
1Fu L M. Rule generation from neural networks. IEEE Trans on Sys, Man and Cybernetics, 1994, 28(8): 11141124
2Towell G, Shavlik J. The extraction of refined rules from knowledge based neural networks. Machine Learning, 1993,13(1): 71101
3Nowlan S J, Hinton G E. Simplifying neural networks by soft weight-sharing. Neural Computation,1992,4(2):473493
4Rudy Setiono, Liu H. Understanding neural networks via rule extraction. In: Proc of the 14th International Joint Conference on Artificial Intelligence, Montreal, 1995. 480485
5Sestito S, Dillon T. Knowledge acquisition of conjunctive rules using multilayered neural networks. International Journal of Intell Sys, 1993, 8(7): 779805
6Craven M W, Shavlik J W. Using sampling and queries to extract rules from trained neural networks. In: Proc of the 7th Int'l Conf on Mathine Learning, New Brunswick, 1994. 3745
7Sestito S, Dillon T. Knowledge acquisition of conjunctive rules with continuously valued attributes. In: Proc of 12th Int'l Conf on Artificial Intelligence, Avignon, France, 1992. 645655
8ԴŸ.ھ򹤾ߵо. 廪ѧѧ1998, 38(S2): 6466
(Huang Yuan,Zhang Fuyan. Research of data mining tools based on neural network approach. Journal of Tsinghua University, 1998, 38(2): 6466)
ԭյڣ1998-12-07޸ĸյڣ1999-05-07.
