о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.7P.788-793



һֻϢۺѡ׼
Ƕï桡Ǯ
ժҪѡǻѧϰģʽʶеһҪ.ȻʵӦУûнѡȡͳһǣֻעķܣûпȡķ⣬ʶϵͳЧʽϵ.дʵӦýǶȣһµѡ׼򣬽ķȡͳһǣϢȡۺۺΪѡ׼򣬲ʽ㷨ECFS.㷨ӦʵѧϰⲢ㷨ID3BP˱Ƚ.ʵECFSڱ֤ʶ𾫶ȵͬʱȡʱģʶٶ.
ؼʣϢ棬ãѡ񣬾
ţTP18
A FEATURE SELECTION CRITERION BASED ON INFORMATION 
GAIN AND COST EVALUATION FUNCTION
WANG Ya-Dong
(Department of Computer Science and Engineering, Harbin Institute of Technology, Harbin 150001)
GUO Mao-Zu
(Department of Computer Science and Engineering, Harbin Institute of Technology, Harbin 150001)
QIAN Guo-Liang
(Department of Computer Science and Engineering, Harbin Institute of Technology, Harbin 150001)
AbstractFeature selection is an important problem in the fields of machine learning and pattern recognition. However, in real-world domains, the fact that feature selection and feature extraction are not considered together in existing heuristic algorithms leads to the lower efficiency of application system. In this paper, a new feature selection criterion is presented which considers feature selection and feature extraction together. A heuristic algorithm based on information gain and cost of feature extraction evaluation function, ECFS is also given. It is applied to the learning problem in real-world domain and is compared with ID3 and BP algorithms. The experimental results show that under the condition of ensuring the recognition rate, ECFS can reduce a lot of cost of feature extraction and improve recognition speed greatly.
Key wordsinformation gain, cost, feature selection, decision tree
1
ѡǻѧϰģʽʶٵһҪ1.ѡָ֪һаĳһ׼ѡкܺõԵӼĳһ׼ķܽڷŻƣ2.Ŀǰѡ񷽷ҪǴͳģʽʶ𷽷ڡ2ݣ34ԼһЩѧϰȣ56.Щѡ׼ҪĿ⣬ĳһ׼ѡܽϺõз࣬ûпǵȡķ.ȻʵӦУһӽǲģȡķҲһǳҪĿ.ΪһȡøߵõϢͨҪڷõ͵.ǣʱõ͵ļõϢܺͿܶһøߵõϢÿ֮Сڷøߵ.ˣȷѡ׼ʱÿȡķʮֱҪ.
ĴʵӦýǶȣһֻϢȡۺۺѡ׼.ķȡͳһǣʶѡȡͬʱеķʽ㷨ECFS.㷨Ӧдʶϵͳѡ⣬ѧϰ㷨ID3BP㷨˱Ƚ.ʵECFSڱ֤ʶ𾫶ȵͬʱȡʱģʶٶ.
2ͳѡ׼
2.1׼
һF={f1, f2,, fn}ѡзϺõӼķƶȾСƶȾ.ݾ׼2ݣӦʹֵ֮֮ͬľ󣬶ͬһڵֵ֮ķС.֮ͳƶģѵFеnطҳmõΪ.磬ѵWiWjֱֵΪmimjkΪmikmjkӦľֵΪ.ѡ׼Ϊ.ȻGk ֵԽ󣬱ʾkWiWjԽ.f1, f2, , fnGkĴСѡܹȫֳѵӼ{fi, fj, , fm}1imn.
2.2׼
ǽѡһЧֶ.ף3иһ̼֡ήѧϰ㷨дʶѡ.ģͺ㷨£


ͼ1ģ
1 ڵڵȨصPerceptron㷨
2 ɶѵԿɷԲɷԶġע⡱ƣ
3 ڵڵ䲻Ҫġ̼ά.
(ȡд)пܰ˺ܶʶ̲޺ܴӰЩȴռ˴Դ.ѧϰ㷨ܹʹԪҵڵ˷ܶߡĿٵһЩڵ.ЩڵӦӦΪʶҪҪӶﵽѡĿ.
2.3׼
ѧϰ㷨÷βԣڵݹ鹹УĽʽѡ.ΪQuinlanϢΪľѧϰ㷨ID35ݣ㷺Ӧģʽʶרϵͳ.
ھĵTiϣеѵͷֱΪT+iT-i,ýеϢض£

XkΪǰķ֦ԣXkmֵ{V1, V2,, Vm}TiΪmӽ㣬Ti+1={T(i+1)1T(i+1)2T(i+1)m}.T(i+1)kϺи͸ӽT(i+1)kеϢI(T(i+1)k)ôXkΪ֦Եõӽ㼯Ti+1еϢǣ.ˣڵTiXkΪ֦ԵϢǣGain(Xk)=I(Ti)-I(Ti+1).ID3ѡʹGain(Xk)XkΪ֦ԣϢԭ.ͨݹʽ㷨ѡͬΪĽԽ.
ѡ׼򷽷ҪĿ⣬ĳһ׼ѡܽϺõз࣬ûпǵȡķ.ȻʵӦУһӽǲģȡķҲһǳҪĿ.ҽһɿȷϲ鷽ȻҲǷǳģЩȫּͨ򵥵;ȷ.רϵͳϺһЩģʽʶʵӦҪ7.ˣѡʱÿȡķʮֱҪ.
3Ϣۺѡ׼
3.1ȡ
ȡǻȡڷһֶλ㷨2.κȡķڲͬѧϰʵǲͬ.һF={F1,F2,F3,, Fn}ȡFiķñʾΪCost(Fi).ʵĲͬCost(Fi)ʱ䡢ǮȲͬ߶.ڴģʽʶ⣬ʶ𡢺ʶ8ݵȣCost(Fi)ĶΪȡʱʱ临Ӷ.רϵͳϵУ7ݣؿԽǮΪCost(Fi)Ķλ.
Ϊ˽һȡ֮ĹϵȶԳȡͶȡ㷨бţF1, F2,, FnA1, A2,, Am(Уmn).㷨һΪĸԿһҲһֲ.ÿһ㷨ӦķúӶõúC={C1, C2,, Cm}.Ȼһȡͼ2ڽȡȡ㷨ĶӦϵ.ÿһĳȡӦ㷨һúй.ȡԭݸĲͬڲӦ㷨ȡӦķúȷ.ÿһFiȡӦ㷨AjãȡķCjC(Fi)=Cj.


ͼ2ȡ
3.2Ϣۺѡʽ㷨ECFS
һַǳЧĹѧϰߣѵѧϰٶȡʶٶȿŵ㣬رʺڴģݷ.ھĽγɹУõѡ׼ͬγɲͬľ.ΪQuinlanID35ݼĽ㷨6.Ȼľѧϰ㷨ѡ׼Уûнѡȡͳһǣֻעķܣûпǵȡķ.ˣʵӦдЧʽϵ͵.ΪȡķҲϵͳеһҪ.ԣѡʱÿȡķʮֱҪ.
ԾΪߣѡȡͳһǣϢۺѡ׼
1 ϢȼϢСȼ.
2 ȡСѡȼȡô.
У(1)׼ɵľƽ߶ȼСŻ׼ʹÿһҶвʱܻùڱϢ.Ӷ֤÷Ҷ㵽Ҷƽ·.ʹɵľƽȽСӶнϿķٶ.(2)׼ͨѡЩȡСϵͳķãӶﵽϵͳЧʵĿ.
׼ѡ׼ʽۺF(A,E) = Gain(A)/(1+C(A)).Gain(A) ʾѡAϢ棬ʵ뱾ĵڶ־׼еĸͬC(A)ǳȡAķãݲͬʱǮȶλʾΪӣʵȷȡֵԵϢȡ֮ƽϵֵΪ(0,1)ϵʵ.
F(A,E)ĶԿF(A,E)ʾѵӼEλڻõϢȡֵԽ󣬱ѡԽ.ȡķʱC(A)=0ǳСʱF(A,E)൱ڴͳϢҲID3Ϣ׼Ǳѡ׼һ.Ǹ׼ϵѡʽ㷨ECFS㷨£
㷨1. ѵӼEӵA={A1, A2,, An}F(Ai,E)涨ۺ
PROCEDURE ECFS(E)
BEGIN
IFEֻ򷵻Ҷ㣬
ELSE 
ѡһAkAkAʹF(Ak,E)
ForAkÿȡֵVjݹ鹹ECFS(Ej)EjֻAkȡֵΪVjӣ
طҶ㼰ӦAk
ENDIF
END
3.3ȡECFS
Ϊ˽һѡȡ̽ܽѡѵнѡECFSȻʶȡȡӶﵽϵͳЧʵĿ.巽£
(1)ѵ.ѡѵΪѵӼϣȻȡ㷨ȡÿһnάռ䣨ѵ.Ȼʽ㷨ECFSѡľھÿҶӽϣһµĽϢýҪѡţ
(2)ʶ.þʶʱ򣬸һµĴʶϢͨȡӦ㷨ȡ֮Ӧ.ͨȡECFS߷߽ѡͳȡҪĳзʱٽиĳȡ.سȡȫӶȡϵͳЧʣΪϵͳôȡϣ.
3.4һѡ
ǹһ򵥵ѡ˵ECFSƣ1.
1һѡ

x1x2
e110P
e201N
e310P


x15
x28


ڱ1У4ӣΪ.x1,x2з࣬x1x2ȡ÷ֱΪ58.þ㷨ID35ݣx1x2ԽѵӼȫֿ.ϢΪ2.Ϊ{x1=1eP; x1=0eN;}{x2=0eP; x2=1eN;}.Ҳ˵ID3ֻķܣ޷x1x2ʵӦЧ.ECFSֻѡx1Ϊ.ΪȡֵΪ0.5F(x1,E)=0.57 F(x2,E)=0.4ȻF(x1,E) F(x2,E)ECFSֻѡx1ΪΪ{x1=1eP; x1=0eN;}.ʶһµʱֻҪȡx1ȡֵͿͨECFSб𣬴Ӷʡ˷.ͨ򵥵ӿԿѡȡͳһECFS㷨ŵ.
ѡ׼ʽ㷨ECFSȡķȡķͳһǣ໥ƽ⣬໥ϵʹϵͳγһл. 
4ʵ
ĽECFS㷨ӦʵӦдʶϵͳ봫ͳľѧϰ㷨ID3BP㷨бȽ.ѡ1000ú֣40ѧṩд.ÿְ20ͬÿֵǰ12Ϊѵ12000ӣ8Ϊʶ𼯣8000ӣ.ȡ˺ʻܱṹΪ.ȡһ12άռ䣺A={A1, A2, A3,, A12} (2).
2ȡд

A1ʻ (1-z)A7ܱ(0-f)
A2λ(0-2)A8ṹ(0-2)
A3λ (0-2)A9(0-4)
A4ܱ(0-f)A10(0-4)
A5ܱ(0-f)A11(0-4)
A6ܱ(0-f)A12(0-4)


Ĳʱȡ㷨ķ.ֽF(A,E)дʶеӦ˵£F(A,E)=Gain(A)/(1+C(A))Gain(A) ѡAϢ棬C(A)ʾȡAʵʱģΪӣڱȡֵΪ0.45F(A,E)ʾѵӼEλʱڻõϢ.486΢ʵȽ3ʾ. 
3ECFSID3BP㷨ıȽϽ

BP㷨ID3ECFS
ѵʱ260 h2 h2 h
ʶٶ14 /s12 /s21 /s
ʶ𾫶77.85%76.32%75.24%


ӱ3Է֣ECFS㷨ѡʶȡʶеķֻȡʶҪǷǳЧ.ECFS̳ID3㷨ѧϰʶٶȿŵ㣬ʶID3ͬʱʶٶкܴߣϵͳЧ.
⣬ǻ֣ECFSѵľƽֻ8߶Ϊ12.Ҳ˵ʶĹУÿҪʶĺ֣ƽֻ8,ȡ,ʶٶ.ͬʱECFSڲͬĺ֣ʹõнϴͬ.Уڸӵĺ֣ܱʹõƵʺܸߣ87%һ֣ṹͷʹƵʽϸߣ82%ڼ򵥺ֵʶϣʻʹҪһЩ78%.ԿECFSʶͬӶȵĺʱܹЧѡͬ. 
5
ĴʵӦýǶȣķȡͳһǣһֻϢȡۺۺѡ׼ʶѡȡͬʱеķʽ㷨ECFS.㷨Ӧдʶϵͳѡ.ʵECFSڱ֤ʶ𾫶ȵͬʱȡʱģʶٶ.
ĿõȻѧ𡢹ʺĿɫƥ䡢Уܻ.
߼飺ǶУ1964ڣҪоΪרϵͳɫƥ.
ï棬У1966ڣʿҪоΪѧϰɫƥ䡢ǡֵ㷨.
ǮУ1971ʿҪоΪѧϰɫƥ䡢ģʽʶ.
ߵλǶ(ҵѧѧ빤ϵ150001)
ï(ҵѧѧ빤ϵ150001)
Ǯ(ҵѧѧ빤ϵ150001)
οף
1ݳ±򣬺٣Ƕ.Ӽѡ⣬ѧ1997, 20(2): 133138
(Chen Bin, Hong Jiarong, Wang Yadong. The problem of finding optimal subset of features. Chinese Journal of Computers(in Chinese), 1997, 20(2): 133138)
2ݲԪ. ģʽʶ. : ӿƼѧ磬1992, 104120
(Cai Yuanlong. Pattern Recognition(in Chinese). Xi'an: Xi'an University of Electronic Science and Technology Press. 1992, 104120)
3ӭΪ.дѡģʽʶ˹ܣ1992, 5(1): 3743
(Liu Yingjian, Dai Ruwei, Zhang Liqing. Feature selection of handwritten Chinese character based on neural network. Pattern Recognition and Artificial Intelligence(in Chinese). 1992, 5(1): 3743)
4Ȩգųͣ.Hopfield-Tankģ͵ı緽ѧ 1996, 24(8): 7881
(Quan Guangri, Cui Minggen, Zhang Zhaohui, Hong Jiarong. A variant parameter network method based on Hopfield-Tank model. Acta Electronica Sinica. 1996, 24(8): 7881)
5Quinlan J R. Induction of decision trees. Machine Learning, 1986, 1(1): 81106
6ݺ٣壬ԭޱ.һµľѧϰ㷨ѧ1995, 18(6): 1821
(Hong Jiarong, Ding Mingfeng, Li Xingyuan, Wang Liwei. A new algorithm of decision tree induction. Chinese Journal of Computers(in Chinese), 1995, 18(6): 1821)
7Pazzani M, Merz C, Murphy P et al. Reducing misclassification costs. In: Proceedings of the 11th International Conference of Machine Learning, New Brunswick: Morgan Kaufmann, 1994, 217225
8Ǯ.ڻѧϰдʶоʵ֣˶ʿģݣҵѧ1995
(Qian Guoliang. Research and implementation of handwritten Chinese character recognition based on machine learningmaster dissertation(in Chinese). Harbin Institute of Technology, Harbin 1995)
ոڣ1998-10-06
޸ڣ1999-04-06
