ѧ
JOURNAL OF SOFTWARE
1999ꡡ109ڡVol.10No.91999



صž㷨*
ʯĺ
ժҪʾѧϰǴĳһѸϺͷйɲųзĸøһ򣬶ž۽ѰڷĹʽȼΪڷҳһ·.Զص⣬Ľԭеž㷨˻ƽص̹ʽƽʽƺصĸܶȺӶб.½㷨ӦдʶͨȽϣ˸Ľ㷨Ч.
ؼʡʾѧϰžƽأƺдʶ.
ͼšTP181
An Extension Matrix Algorithm for Multi-class Problem with Overlay Area
SHI Da-ming,SHU Wen-hao,XU Rui-feng
(Department of Computer Science and Engineering Harbin Institute of Technology Harbin 150001)
SHI Da-ming,XU Rui-feng
(Department of Computing Hong Kong Polytechnic University Hong Kong)
AbstractLearning from examples is to obtain a general rule through induction from a given set of positive and negative examples of a concept, which may describe all the positive examples, and reject all the negative examples of that concept. According to the extension matrix theory, to discover the equations which satisfy all positive examples on the background of negative examples may be considered as to find a path within the matrix of negative examples. In order to deal with the multi-class problems with overlay, an improved extension matrix algorithm has been proposed in this paper. The heuristic search based on average entropy has been used to get the approximate solutions of the shortest equation. The potential function is used to estimate the probability density function of the overlay area between positive and negative examples, so that the non-linear interfaces of the interclass areas may be obtained. The improved algorithms have been applied to handwritten Chinese character recognition and its effectiveness has been proved through comparison study and analysis.
Key wordsLearning from examples, extension matrix, average entropy, potential function, handwritten Chinese character recognition.
ʾѧϰǻѧϰнΪķ֧ǴĳһѸϺͷйɲųзĸøһҲȡ.ʾѧϰ֪ʶʾɷΪࡪ߹ɣ1.ǰID32Ϊصѵٶȶܿ죬ڴģѧϰ⣻AE13ΪصǷྫȸߣ֪ʶǿʺרϵͳ֪ʶԶȡ.AE1žextension matrixΪ.
ʾѧϰžӦڶصʱԭ㷨ɴʱͿռ俪޷صĹ.һʵӦ˵صձؿ͹۴ڵģѧϰܲһб.ʵϣ80ڣйظʱʾоͿʼڻѧϰ.ֱʾ֮ĸμԲȷ̶ȵ4.
ĸƽصķ̹ʽƽʽ㷨ص򣬹һԵƺص()ĳģʽܶȺ.
ĵ1ڽʾѧϰž.2һʽɵʽ㷨.3ƺصʶ.4ھ˵ںʶеӦ.5ͨʵȽ㷨ĽǰЧ.
1ž
һeһnάΪe=x1,x2,...,xnxjDjDjNDjɢżxjΪԪ.EeļϣPENEEӼΪֱͷ.
ѡΪxjAjݵĹϵ䣬AjDjʽһѡӻ򼸸ѡӵĺȡʽǹʽȡʽ.
1. һ.e+ڷe-i㹫ʽL,ҽe+Le-iL.
걸.ʽȡʽCOVPENEµһ򣬵ҽPEеκһNECOVеһʽ.
Ӷ1һ걸ԿԵóһNE¸e+ĹʽӦe+κԪأ뺬ÿһԪ.µУǽгɾʽΪȼۣһӶӦӦеһ.
2. ֪e+=x1,x2,...,xnNEÿһjNáԪء*NEеjегóľڷNEµž󣬼ΪEM(e+)e+ΪEM(e+).
žEM(e+)УɷֱԲͬеmԪɵļϽһ·.ϵžУֵͬĶӦķԪؽǵĹԪأֻɹԪɵ·ǵĹ·.ž.
EM(e+)e+NEµžEM(e+)rijݣe+=x1,x2,...,xnNEx-ijݣ
(1) 
(2) žEM(e+)е·ͬe+NEĹʽһһӦ
(3) ֪e+k(x+kj) Լe+l(x+lj)NEеԪx-ijEM(e+k)EM(e+l)ĹԪأҽx-ijx+kjx-ijx+lj.
(2)ǰѰNE¸e+ĹʽӦžEM(e+)һ·ʵ.(1)(3)ֻһNEи(1)·Ԫػ(3)·ԪأȫûбҪһž.ѧϰ㷨൱򵥣ֽʡ˴洢ռ.
 ע⣬Ͻ۾ܵõϸ֤3ݣǵĳ䲻ص⣬һӵž󲻴УеԪΪԪ.
2̹ʽƽʽ
һžиǸĹʽǲһЩŻ.
(1) ̹ʽ(MCOMP)ڶʽʱڣҳһڷ¸һ̹ʽСĿѡӵĹʽ.
(2) Ÿ(MCV)ڶʽʱڣҳһPENEµŸǣСĿʽĹ.
MCOMPMCVⶼ֤ΪNP-hard3ݣӳʾѧϰԶ֪ʶȡѳ̶ȣʹǲòѰ㷨ĳԶתøʽѰǵĽƽ.
AE1ͨʽһ·NEӼһ۾ENEENEеԪNEӦȡֵͬĿeеԪNEгֵĿ򽫱.һ·ɺAE1ʼԪ.
AE1MCVĽƽⷨΪΪٵĹʽѡžġ󹫹·Ŀžгֵ·󹫹ԪءĿžгֵԪأп󹫹·.ˣžУɰԪڸžгֵƵѡ·Ľ.ʽɺAE1ʼɾ๫ʽһʽģǵȫ๫ʽļ.
κһeһnάe=x1,x2,...,xnž۽ӷֳΪžһ·.ÿǲͬ.AE1ȶԸžɸԵĹ·ȻɾԪصȷѰ󹫹·.һ⣬ìܽͻ.
ɳü֧ƽصķѡ֧.ĽӦõžУ¶.
3. E=D1D2...DnһCE=E1E2...Ec,Ei(i=1,...,C)ΪiDjɢżjN.ΪEEiDjϵƽأ
(1)
njָDjڷżȡضֵnlָžδnjkָkDjȡضֵ.
ƽСѰҷԪ.ڳʵаʽ(1)õȴžУֱд.ַÿһҲ̰ĵģAE1ͬǣMCOMPƽĹУMCV⣬ʹMCVʱҪAE1.
3صĹ
ʵⶼص.һһӴѵʵʵص⣬ΪӦȷ㷨Ļѧϰǲе.ǽѧϰĹȥʶһ֣򲿼һ飬Сʵ¼һǼܷģžȥɹĹУһǴ¼ĹʽӦΪһȥǷмС¼¼пPEֳӼPEPE1PE2.
4. PE1ΪӼePE1,eNE.
5. PE2ΪӼeNE,ePE2.
׼PE1ĹCOV1걸ԡһԣPE2ĹCOV2ֻ걸ԣ1ۣ5.
1. COV1κһӣžУôзӦɾģCOV2ӿžдУнԽ.
ЧѡȡPE1ܸõ˳ӿѧϰʶٶ.ֻҪоģ壨д飩ǲӵģڴ£ÿPE1.
3.1ںܶȵģʽ
ڣǴģʽʶǶӦžٵԲɷ.
ģʽʶĿҪȷĳһģʽһ࣬ѧϰĿǴģʽĹ۲ֵзĳЩϵ.ϵȷģôѧϰõĹȫȷбģʽ.Ƕ͹ͬĻ¿ܵõȷĹ۲ֻڴظ£ųֳĳֹ.嵽žγɺʶһ⣬PE2һȷ䡰䡱ӳ˲ͬɫɵĹֱӰЧӵ.PE2һ(x1,...,xn).PE2M.Ҷ˹ʽ
(2)
P(wi)ǺģΪҪͳwiֵĸʣʵϣͬʱ䡢ͬͬҵĳֵĸʲͬp(e|wi)ǲܵģҪ֪wi£ĳΪe.ȻĿǰ״˼ĺʶ˵ĺʶֻһϴϴ⣬ȱάeͬȡֵڲͬʱܲͬһ࣬ǲܲһȫȷֻܾڸĸ.ʵְģʽĹؼѵܶȺ{p(wi|e),i=1,2,...,M}.
p(wi|e)>p(wj|e),ji,ewi.
3.2ƺ㷨
ݶ5COV2.ͨƺĸȷбԼ6.
6. nάģʽռĵek=x1,x2,...,xnһԴôekռeϵĵλֲɿһƺK(e,ek).
ڵekϣλﵽֵõľ󣬵λֲѸټС.ѰģʽбתΪڸλֲ֮ѡʵĵλߣCOV2ķɺ.ѡ

e=x1,x2,...,xnnάek=xk1,...,xknѵӣ.ʽΪƺ3
(1) MaxK(e,ek)=K(e,ek)|e=ek=1 
(2) 
(3) e-ek12e-ek22K(e,ek1)>K(e,ek2).
ʶp(wi|e)fk(e)ƣkΪúֵ01֮.Ϊظ׸fk(e)ĵ㷨ɼ½ڵʵʾ.ڱCOV2ǵģʽֵģڻPE2ԣfk(e)ҲKʶp(PE2|e).֪COV1COV2ΪһЩȡʽȡĴ洢ǰȡȡʽе.ÿȡʽͿɿģʽһṹģ.صϣԽfk(e)Խʶp(PE2|e)ǵ洢ռޣֻڴ洢ʶʶ֮ȡ.Ǽ¼PE2ľֵһڵָfk(e)ΪߵĴ.
4ʶӦþ
ھžɹƺʶ.
ͼ1ǹѧϰֵ,ÿӵΪe=x0,x1,...,x17xii0,1,...,17ֱӦںֵ18Ԫxi=0ʾڣxi=1ʾ.

ͼ1ͷ
PE1={e+1,e+2},PE2={e+3,e+4}.e+1,e+2ڷµžEM(e+1),EM(e+2)ͼ2ʾ.

ͼ2
ΪɸPE1̹ʽƽ⣬PE1NE۾ͼ3ʾ.

ͼ3PE1NE۾
ʽ(1ֱH0,H1,...,H17H9С.

ȴ9άƣõ̹ʽx51ݣx90ݣx171ݣҲEM(e+1)EM(e+2)󹫹·ͼ2EM(e+1)ʾ.
ȷֱEM(e+1)EM(e+2)Ĺ·EM(e+2)ȵõx140ݣx171ݣͼ2EM(e+2)ʾ.ɾԪزܵõ󹫹·.
ͬҲɵõӼPE2걸ʽCOV2=x01ݣx90ݣͼ4EM(e+3)EM(e+4)ʾ.
ע⵽1e-5ɾEM(e+4)е3бԽ.
e+3e+4e-3бe+3e+4e-3COV2.
(1) ȡf0(e)=0,k=0.
(2) e+3=x1,0,...,x1,17=0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0.Ϊf0(e+3)=0,ȡ

(3) e+4=x2,0,...,x2,17=0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,.Ϊf1(e+4)=exp(-3)0,ȡ
f2(e)=f1(e).
(4) e-3=x3,0,...,x3,17=0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0.Ϊf2(e-3)=exp(-3)0,ȡ


f3(e)p(PE2|e).

ͼ4
5ʵ
Ͻھɵݼһʵѵϵͳһʵ.ʵԵΪһ3 755ÿ8ѵ5.ַ󹩹ѧϰΪÿ80120.Ϊǿʵû̶ȣռÿ100ѵ.ѧϰǴݼɳʶȽɵѡȡȡ洢Ӱ洢ռ䣩ѧϰʱɳʱƣʶùȥбΪˣѡȡݼĸ5ͳʶʣѡ.
1AE1㷨ɹҲPE2PE2ѵɾ.
2صʾѧϰž㷨صܶȺp(PE2|e)=1.
3صʾѧϰž㷨صܶȺ.
ȽϽ1.
1㷨ЧȽ

ѧϰʶ
ѡȡѧϰʱ (s)ʶ(%)
1 (PE1)53134635465
 2(PE1)537264
(PE2)28918942762
 3(PE1)537264
(PE2)28918942771

1
(1) ʶʵͳ൱ڴַһѡ֧󼶷ͳƽ.2ص򣬵صĹʽɹֻ걸ԶһԣĻʶʷȷ1.3صܶȺʶ.ַضضʱ佫ʾԽ.
(2) 1뷽23PE1ɵѡ൱ȡԶںַ˵˻ƽص̹ʽƽʽԼȡЧ.һǰȡ洢򼰷Բ뿼ǵ.
(3) ѧϰʱûרͳƣɿPE2ƺĻֵõģҷ3ж̬ѧϰŵ.
ף7ûڱҶ˹ƵĽѧϰ㷨ص.κҶ˹ʹƹൽܵԭѳһʵǽ̬෽ӦڷУ㷨ڹ̶.⣬ף7ݵķٶԶȱ㷨.Խֲ࣬Խ.䷽δӼ벻ӼԴ賢Թൽ𣬶ñ㷨ܸѧĹܶȺȷ. 
6 
ž۽ѰڷĹʽȼΪڷҳһ·.Ĳž۴صʱλƽؽ̹ʽƽʽƺصĸܶȺӶб.
*оõ863߿ƼĿ.
ͨѶϵˣĺ150001,ҵѧѧ빤ϵ341
߼飺ʯ1971ʿʦҪоΪַʶ𣬻ѧϰ.
ĺ1932ڣҪоΪģʽʶ˹.
壬1973̣ҪоΪļ.
ߵλʯĺ壨ҵѧѧ빤ϵ150001
ʯ壨ѧӼѧϵۣ
οף
1Quinlan J R. Knowledge acquisition from structured data. IEEE Expert, 1991,6(6):3237
2Quinlan J R. Induction of decision tree. Machine Learning, 1986,1(1):81106
3Hong Jia-rong. AE1: an extension matrix approximate method for the general covering problem. International Journal of Computer and Information Science, 1985,14(6):421437
4Pat L et al. Learning with probabilistic representations. Machine Learning, 1997,29:91101
5ʯĺ.ƺʾѧϰžеӦ.ģʽʶ˹,1996,9(2):149154
(Shi Da-ming, Shu Wen-hao. A potential function used in the extension matrix theory of machine learning from examples. Pattern Recognition and Artificial Intelligence, 1996,9(2):149154)
6ݲԪ.ģʽʶ.ӿƼѧ,1990
(Cai Yuan-long. Pattern Recognition. Xi'an: Xi'an University of Electronic Science and Technology Press, 1990)
7Anderson J R et al. Exploration of an incremental, bayesian algorithm for categorization. Machine Learning, 1992,9:275308
ոڣ1998-02-13޸ڣ1998-09-24
