The Minimum Feature Subset Selection Problem  

作　　者：陈彬 洪家荣 王亚东 

机构地区：[1]DepartmentofComputerScience,HarbinInstituteofTechnology,Harbin150001

出　　处：《Journal of Computer Science & Technology》1997年第2期145-153,共9页计算机科学技术学报（英文版）

摘　　要：In applications of learning from examples to real-world tasks, feature subset selection is important to speed up training and to improve generalization performance. ideally, an inductive algorithm should use subset of features as small as possible. In this paper however, the authors show that the problem of selecting the minimum subset of features is NP-hard. The paper then presents a greedy algorithm for feature subset selection. The result of running the greedy algorithm on hand-written numeral recognition problem is also given.In applications of learning from examples to real-world tasks, feature subset selection is important to speed up training and to improve generalization performance. ideally, an inductive algorithm should use subset of features as small as possible. In this paper however, the authors show that the problem of selecting the minimum subset of features is NP-hard. The paper then presents a greedy algorithm for feature subset selection. The result of running the greedy algorithm on hand-written numeral recognition problem is also given.

关 键 词：Learning from examples NP-HARD greedy algorithm 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]