Զѧ
ACTA AUTOMATICA SINICA
1998 24 5  Vol.24  No.5 1998



һѡĶ̬滮1)
»
ժҪͨѡĻһѡָͻڴָĶ̬滮ѡ񷽷.ʹӵĶϢѡȫѰ̣תһ򵥵Ľ׶Ż.һ£ɸ׶ž߹ɵԵȼԭȫ.ķϺõӦˮź.
ؼʡѡ񣬶̬滮ģʽʶϢں.
DYNAMIC PROGRAMMING METHOD
FOR FEATURE SELECTION
ZHANG XINHUA
(Dalian Naval Academy, Dalian 116018)
(Dept. of Underwater Acoustical Engineering, Harbin Engineering University, Harbin 150001)
AbstractThe selection of multiple classes of features plays an important role in the field of pattern recognition. By analyzing the mechanism of feature selection, a performance measure of feature selection is proposed in this paper. Based on it, a dynamic programming method for feature selection is presented, by which a complex process of obtaining globally satisfactory solution to feature selection can be converted into a simple piecewise optimization. It is theoretically proved that the optimum strategy consisting of optimized decisions in each phase corresponds to the globally satisfactory solution of feature selection. The proposed approach is applied to feature selection of underwater acoustical signals.
Key wordsFeature selection, dynamic programming, pattern recognition,information fusion.
1
ģʶϢ𻮷ֵĹ.Ϊʵ³࣬ʹõ뺬㹻Ϣ.ͨĳһģʽʶ⣬ɴӶͬĽǶ(ʱƵ)õ͵ϢЩͬϢۺãģʽʶʮҪ.Ϣۺϲļ򵥺ϲҲǳĺϲѹӦлں.о֣нϺ÷ЧļϣЧһڵ.ԭҪж1)Ϣ۵Ĺ۵㣬Ϣлԣìԣļ򵥺ϲĻϢ֮ܲìϢ2)ԭϢļ򵥺ϲʹռάӣʱѵĿ䣬ɴ˵õķɷԻ½ѵģʱ½ԣ1.
ѡһֱܵĹ㷺ע滮2ݽԷϾ뷨ֲһҪ3ݣڻϢ̰㷨4ݵõĲȫ⣬ѡάԤȹ̶ģŴ㷨5һŻ㷨õȫ⣬Ծнϴļ㸴.ĴϷѡĻһֽŵѡָͻڴ˵Ķ̬滮ѡ񷽷.
2ѡĻ
覸C=W,w,Pʿռ䣬W=1,,Cʾģʽ𼯺ϣCģʽwWӼɵһҴPǶڦwϵĸʲ.УֵΪP(i),i=1,,C.F=X,x,p(X)ʿռ䣬X=(x1,xF)TFάxXBorelp(X)ǶڦxϵܶȺ.ڸģʽ⣬ģʽĳʼȷ
(1)
ǹ̶.
(2)
ɸ֪ģʽϢFͨѡԸı.ı
(3)
Ϊģʽռռ֮ĻϢӳ֮.XjRFΪXĵjѡ.֮䲻ڹռĻϢʱʽ
(4)
ѡĿǴӲͬϢѡɷʹ(2)ʽʾĺشﵽС.ȼʹ(3)ʽʾʿռʿռĻϢﵽ.ͨѡʹģʽƽȷԴﵽС.Ϊ(3)ʽļFͱɢĿֱָΪѡָ꣬ʮָ.(4)ʽֻ(3)ʽʽһֲ.ʵϣ(4)ʽʾĻϢûп֮Ϣ࣬(3)ʽ¹ϵ
(5)
ɼIs(CF)ȥһܵõϢI(CF)ĽϺý.һ(ʵһͷ)ӦܽϺõرڸ֮ԣøĻϢʾ.ҵһּȼܽϺýƻϢI(CF)ѡָ.
ѡĻ˼ǰѸһȻѡʹܺ
(6)
ﵽm.УΪϵһȡ0.11.0.ȡֵʣ(6)ʽܽϺõؽ(3)ʽʾĻϢӶʹռռ֮нϺõ.
3ڶ̬滮ѡ
ԭʼΪO=x1,,xFFΪɹѡά.ȡ״̬sk0OΪk׶ѡɵļϣFkOΪk׶οɹѡĺѡϣdk(sk)Fkʾk׶εľ߱Ӻѡѡµ.k׶ε״̬ɱʾΪ
sk=Tk-1(sk-1,dk-1(sk-1)),
Tk-1ʾ״̬sk-1µ״̬תƱ任.Pk,n-1(sk)Ϊk׶εn-1׶Եļϣ(6)ʽΪߵܺ.ӳʼ״̬s0Բp0,n״̬sn+1ʱõָ꺯V0,n(s0,p0,n)ɱʾΪ
(7)

(8)
ʾn+1׶״̬sn²þdnõָ.NsΪѡϵԪظ.
ѡͱһ̬滮.ݶ̬滮ԭp*0,n-1=(d*0,d*1,,d*n-1)ŲԵĳҪǶ0<k<n-1,s0
(9)
spk=Tk-1(sk-1,dk-1)ʾɳʼ״̬s0Ӳp0,k-1ȷĵk׶ε״̬.˵p*0,n-1ѡnŲԣǰӲp*0,n-2Ӧѡn-1Ų.֮s*nǾŲp*0,n-1=(d*0,d*1,,d*n-1)õ״̬(n)Ų(p*0,n-1,d*n)õs*n+1=Tn(s*n,d*n)Ҳ״̬.
ѡ㷨
1)k=0,sk=s0=,Fk=O,p0,k-1=,V0,k-1(s0,p0,k-1)=0;
2)k>pro-numת8ת3
3)xFk,(7)ʽܺvk(sk,x)ȷ
4)vk(sk,dk)<0ת8ת5
5)V0,k(s0,p0,k)=V0,k-1(s0,p0,k-1)+vk(sk,dk);
6)sk+1dk,,FkFkdk,p0,k=p0,k-1,dk;
7)kk+1,ת2
8).
pro-numΪԤĿ.
㷨1)ԤĿ2)ܺм.2)ԣìԣĿԽԽ.㷨ͬʱĿ뱻ѡ.Ҫ󣬿pro-num=F㷨ԶȷӦѡĿ.
ѡNPѽŻ⣬ѡռάӻϱը.ڶ̬滮ѡ㷨-ģʽڲϢʵӦŻѡļ.
4Ӧʵ
ڻĿѡ.ͨĿزźŵʱƵȡ͵ʱƵ.ڴˣ͵ģʽһźŵĵ(ͼ1еǰ30ά)һǰźŷֲֲֵȵĲνṹ(ͼ1еĺ13ά).


ͼ1Ŀ
ĿĿķ⣬C=2.ѵȡ136Լȡ396.ͬһѵڣ30ά13άνṹԼǼ򵥺ϲ43άֱѵṹӦ6ݣõƷõķģ.ͬһԼȷʶ1ʾ.
Ĳɢ䷨ƻϢ.ֵĴСϢǵȼ۵ģȡɢĿͬȡ10.ںϴӲͬõϢ壬Ϊ֮ͬʵһԹһ.ͼ2ʾ43԰Ϣ.
ѡϵй.ĴСģʽֲв鷨.
1²ԽȽ

  ʶʡ(%)

30ά86.589.388.0
13ά87.183.985.4
43άϲ85.784.685.1


ͼ2ռĻϢ
һڲԤѡĿ£ԽСѡԽ֮࣬Խ.1ͬѵԼģͣѡòͬĦõĿں2.
2ںϺĲԽ

  ʶʡ(%)
ƽ
0.23591.892.191.9
0.253291.693.292.4
0.352589.790.189.9

5ᡡ
ϢۺѡģʽʶҪڣЧٵѡ㷨һֱΪע.ĴϷѡĻһѡָ.ָ꣬ѡö̬滮.һӵĶϢںϵȫѰ̣תһ򵥵Ľ׶ԾֲŻ⣬ɸ׶ž߹ɵԵȼԭȫ.ķصǼ򵥣ѡĿ㷨Զȷڱĵʵȡ˽Ч̶ϵ.Цͨȷ.õָһǰµĽţһ£õĲһ.
1)йʿѧĿ.
ߵλ(ͧѧԺ116018)(̴ѧˮϵ150001)
ο
1Elshaikl T S, Wacker A G. Effect of dimensionality and estimation on the performance of Gaussin classifiers. IEEE trans. PAMI, 1980, 2(12):115126
2Foroutan I, Sklansky J. Feature selection for automatic classification of non Gaussian data. IEEE trans. SMC, 1987, 17(2):187198
3٣.ڰϾѡģʽʶ˹ܣ19969(4)324329
4Battiti R. Using mutual information for selecting features in supervised neural net learning. IEEE trans. NN, 1994,5(4):537550
5».Ŵ㷨Ӧ.ָӿƣ199722(4)4953
6Zhang X H, Lin L, Wang J C. A neural network with self-organizing structure and its applications. In:Proc. of Inte. Conf. on Neural Information Processing, Beijing, 1995, 2:906909
ոڡ1997-06-20
