Ϣ
Information and Control
1999ꡡ285ڡVol.28No.51999



ڶԪӦKNN
ꡡɽ

ժҪ һֻڶԪӦKNNϷ(MCA-KNN)дʶ ΪKNNͬһϵõĲͬϽз࣬ͨԪӦ ЩĽϣԵõյķʵַϷ ٷʣ
ؼʣKڷKNNԪӦ, ַʶ
ͼţTP13ױʶ룺B

COMBINATION OF KNN CLASSIFIERS BASED ON
MULTIPLE CORRESPONDENCE ANALYSIS
HAN Hong YANG Jing-yu HU Zhong-shan
(Department of Computer, Nanjing University of Science & Technolo gy, Nanjing 210094)
AbstractThis paper presents a KNN classifier combination me thod based on multiple correspondence analysis (MCA-KNN). This combination meth od is applied to written character recognition. Four kinds of features are extra cted from same sample set and four result sets are obtained from these feature s ets through KNN classifier. Through MCA-KNN, the four result sets are combined to get the final result. The experimental results in this paper demonstrate MCA -KNN's capability to reduce classifying error rate. 
Key wordsKNN Classifier, Multiple Correspondence Analysis, Cha racter Recognition

1
ģʽʶУΪõķ෽ΪKNNKڣKNNĻ˼ǻ¼裺ֵԣ裺һ࣬Ƚÿ洢ԭͣģбȽϻȡԲֵȻԴԲֵȡǰKͶƱԭ򣨻ȨøƱ÷֣ΪƱ÷֣ߵ
˷⣮صܻԷãԲռıعɵģKNNάϴ洢ԭͽ϶´ʵЩʵʱһϴѣȻͨԭѡõҪܴԤҪKNNϣ
2
Ӧԭ
(1) ԱľȷҪߣϳķľȷҲܸߣ
(2) ԱķӦжԣΪöͬͬĳԱ ϣϷľȷȲܴκߣ
(3) ϷЧҪߣʵӦõķҪ
ȻϵѾǺͬʱ㾫ȷԺͶԣ
ͨ濼Ƿϣ
(1) Ĳͬʵʶд壬ͬʱͳͽṹ յʶлã
(2) ͬϣþвͬԵķз࣮ΪĲͬռ Ƿȷǲͬģ˿ɸݲͬķЧϷ öвֱͬĲͬӼѵһ ѧϰЩӷķص㣬Ӷӷķջδ֪
3ڶԪӦKNNϷMCA-KNN 
N࣬Ci, i=1,2,,NʾMKNNз࣬ΪKNNi,i=1,2,,M. M=4ÿKNNK=5ĳTj , KNNiõĽΪrji1,rji2,,rjik,i=1,2, ,Mrjik(Cl), l=1,2,,N, k=1,2,,KΪKNNiεõ lԭ
ʵеAΪԭͼBΪԼ÷R1ʵ еBΪԭͼAΪԼ÷R2ABΪn
R1µX1=(xjl)j=1,2,,n, l=1,2,,(M+1)*N.ɹΪ
R1еĵjrj11,rj12,,rj1k,rj21,rj 22,,rj2K,,,rjM1,rjM2,,rjMK,rj 11,rj12,,rj1KKNN1ԲBjõĽ X1е(xjl), l=1,2,,N;
rj21,rj22,,rj2KKNN1ԲBj ĽX1е(xjl), l=N+1, N+2,,2*N;
rjM1,rjM2,,rjMK,KNNMԲBj ĽX1е(xjl), l=(M-1)*N+1, (M-1)*N+2,,M*N.
i=1,2,,M, k=1,2,,K, l=(i-1)*N+1,(i-1)*N+2,,i*N,
(1)
j=1,2,,n
l=M*N+1,M*N+2,,(M+1)*N,
(2)
j=1,2,,n
BjʵΪCһKNNΪKNN-BESTKNN- BESTBjķӦȫΪC(2)ʽʵKNN-BESTBjõĽ X1е(xjl), l=M*N+1,M)*N+2,,M*N+N.
R2,ͬX2=(xjl) j=1,2,,n, l=1,2,,(M+1)*N.
ʵһʾȡM=4K=5, N=10
ԲT,KNNi, i=1,2,,Mñ1еĽ
ʾӦΪ
(15 0 0 0 0 0 0 0 0 0, 7 0 0 0 0 0 0 0 8 0,
14 0 1 0 0 0 0 0 0 0, 12 0 0 3 0 0 0 0 0 0,
15 0 0 0 0 0 0 0 0 0)
KNNõķƶkֵݼ,ʶԽK ,K-1,,1Ƿ֣ɹʽ12εõĵ÷֣Ӧ
X=(X1 X2), XжԪӦȡKNNȨֵ 
1 ΪC1(Ϊ0)ĲTKNN

ԲT
KNNKNN1KNN2KNN3KNN4KNN-BEST
Kֵ1234512345123451234512345
0000080088000020030000000
÷5432154321543215432154321
ʵC1


ѵ㷨£
(1) ԸKNNķ,ͨʽ(1),(2)õӦ
X=(xij)np,nΪp=(M+1)*N,
ʽNΪMΪϵKNNĿ
(2) ԾXУ

(3)
ʽdiag(a)ʾaɵĶԽǾ


(3) ԾFֵֽ⣬õ
F=U**V䡡 

(4)
(4) ԻõͶӰP=(pij)PpȡPpǰqֵΪϺͶ ӰProjectProject=(pij)pq
ԣ3оZиľľ
C=(cij)Nn, cij=Zij, i=M*N+i,
ʽNΪMΪKNNĿnΪ
ȡCNǰqֵΪϺľľCluster
Cluster=(cij)Nq
MCA-KNN㷨ʵʣѵеһKNN KNN-BESTԲϵKNNKNN-BESTķͨԪӦRpеqάϣͶӰ

ʹ
(5)
ﵽͬڶԾFֵֽ⣮ΪϵKNNڸ ӦȨֵӳKNN-BEST֮Ĺϵѵ㷨УõͶӰ ProjectΪȨֵõľľClusterΪKNN-BESTͶӰڸ ֵ
ABΪԭͼKNN㷨TзõRTԵjT еjTjķ
rj=(rj11,rj12,,rj1K, rj21,rj22, ,rj2K, ,rjM1, rjM2,,rjMK)
ӦNĲ
(6)

l1=(j-1)*N+1,(j-1)*N+2,,j*N,
l2=M*N+1,M*N+2,,M*N+N,
j=1,2,,M,ʽNΪMΪϵKNN,K ΪKNNȡKֵ.
TjõNУ
Re sulti=Testi*Project,
di=Resulti-Clusteri,(7)
i=1,2,,N
dmin=min(di), min( )ñСֵյķClass =min
4MCA-KNNдʶеӦ 
4.1 
ʹõʵȡConcordia UniversityCENPARMIݿе뼯Լ17000ֵͼ񣨷01 9ʮࣩ뼯еǾȷֲģ697935951Ϊʹͬķпɱԣôݼ3׼ÿ׼2000ҹķֲǾȵģ׼еΪѵֱΪABԣΪT
ʵݽȡ
(1) Gabor8*8㣬4(0, 45, 90, 135)ȡǰͼϸɹǼͼÿһ256ά
(2) LegendreأXY㵽10ףͼԤͬ2ÿһ121ά
(3) Pseudo-Zernikeأ䱻㵽8ףͼԤͬ2ÿһ36ά 
(4) Zernikeأ䱻㵽9ףȡǰͼ󾭹򵥵ĹбʾֱʻֵĸΪ300ÿһ30ά
4.2 KNNKѡȡ
ԸKNN㷨ԲͬKֵõķ2ѵABΪԭʹ洢ٶԲԼTͶƱõδ֪ΪƱƱһΪǰ

2 K(1-10)KNN㷨õķ

KNN(%)K
12345678910
Gabor17.8517.8517.1016.7017.6518.0519.1018.9019.6519.75
Legendre8.758.758.58.88.758.98.88.959.49.5
Pseudo-Zernike23.6523.6522.0022.1521.2521.0020.5520.2020.8520.90
Zernike25.4525.4522.5021.4020.9021.1020.9021.0521.0521.55
ϼ18.92518.92517.52517.26317.13817.26317.33817.27517.73817.925


ʵɵõ½ۣ
(1) ڲͬKKNN㷨ʷһµݼ
(2) Kڵ3KNN㷨ʵݼ
ڵһۣΪK󣬵õӦԭ𽥼С֮ľ󣬸òӦԭ͵ĿŶ𽥼СܴԽԽͶƱKNN㷨Kһ̶ʱ7󣩣 ʼ𽥱󣮶ԵڶۣKϴ󣬾ִܳԭ͵ĸ󣬵ǰѴڵȷԭͣԭ͵ӰٶȽ
2ʾK=5ʱKNNЧã㷨УKȡֵΪ5KNN-FEATURE1KNN-FEATURE2KNN-FEATURE3KNN-FEATURE4 ֱGaborLegendrePseudo-ZernikeZernikeϵKNN㷨
4.3 
ϵĿܼͼ1

ͼ1Ͽ
ΪϢһϸṹԤʶ𣮲֤һ ȷԣкܸ߿ɿԣȻֲͬĸKNN ǽϣԱԤʶʶֽʶ
ͼ1нṹʶΪ53.95%ȫʶȻʶʺܸߣǿɿԴ 100%˽ṹʶһЩǳ򵥵֣統ͼһ򵥱պȦʱ һʶΪ0ԤʶķҪƣֻܽеһֽз ҿɿԸ߼ɣ
ڵڶϣԽṹʶĲ۵KNNʶĸõĽֱΪǰԭ͵
ǽڶĸKNNõķMCA-KNN㷨ϣ Ӷõյķ
3ΪMCA-KNN㷨άq仯ʱõĽqֵΪFʽ3ȣʵΪ45

3 άq仯ʱ㷨õĽ

q12345678910
ʣ%25.3018.9012.358.407.456.454.153.353.053.05
ֵʣ%6.9913.8920.3926.6332.7738.6844.3349.8755.3757.53

q11121315202530354045
ʣ%3.003.003.003.003.003.003.003.003.003.00
ֵʣ%59.5561.5463.4367.0274.6981.2187.1592.3896.73100.0


ֵ=ǰqֵĺͣ/ȫֵĺͣ*100
q111ʱ25.30%ݼ3.0%q11ʱʱ3.0%䣮q=11ʱϽѴﵽõķЧqֵ߷ľȣ
4гKNN򲻰ṹԤͬ£ͨӦ򵥵ļǷͶƱVOTINGõýVOTINGǽϵKNNԸĵ÷ֱַͣշΪ÷ߵ
4 ͬ£ӦVOTINGʱȽ 

޽ṹԤṹԤ
ʣ%KNN-FEATURE1
KNN-FEATURE3
KNN-FEATURE4KNN-FEATURE1
KNN-FEATURE2
KNN-FEATURE3
KNN-FEATURE4KNN-FEATURE1
KNN-FEATURE3
KNN-FEATURE4KNN-FEATURE1
KNN-FEATURE2
KNN-FEATURE3
KNN-FEATURE4
VOTING10.956.456.353.85
Ӧ8.504.755.203.00


4УӦȻڼ򵥼ǷͶƱṹԤС˷ʣṹַǽṹŻĹϵ
5
ڶԪӦKNNϷMCA-KNNͨзķƽһKNNʱӦȨֵ㷨ͷʣ籾ʵõʴӲЧõKNN-FEATURE2 8.75%3.00%ѡȡϵķдо
߼飺꣬Ů1973ʿооΪͼģʽʶ
У1941ڣʿʦоΪģʽʶ𡢼Ӿ
ɽУ1973ʿооΪͼģʽʶ
ߵλϾѧϵϾ210094
ο
1. Ԫͳݷۡʵ. 1997
2Oivind D T, Anil K J, Torfinn T. Feature Extraction Methods for Charac ter Recognition? A Survey. Pattern Recognition, 1996, 29(4):641662 
3٣. ڰϾѡ. ģʽʶ˹, 1996, 9(4):324329
4Ching Y Suen, Christine Nadal, Raymond Legault, Tuan A. Mai and Louisa Lam. Computer Recognition of Unconstrained Handwritten Numerals. Proceedings of IEEE, 1992, 80(7):11621179
ոڣ1999-04-27
