基于信息熵的特征子集选择启发式算法的研究  

Research on a Heuristic Algorithm of Feature Subset Selection Based on Entropy

作　　者：钱国良[1] 舒文豪[1] 陈彬[1] 权光日[1] 

机构地区：[1]哈尔滨工业大学计算机科学与工程系

出　　处：《软件学报》1998年第12期911-916,共6页Journal of Software

基　　金：国家自然科学基金;国际合作项目彩色匹配基金;哈尔滨工业大学科技基金

摘　　要：特征子集选择问题是机器学习和模式识别中的一个重要问题．最优特征子集选择问题已被证明是ＮＰ难题．然而，目前的特征子集选择的启发式算法是基于正反例一致的，没有考虑到实际应用中的噪音数据影响，使得选择一个较好的特征子集非常困难．首先从统计学的角度分析了噪音对特征子集选择的影响，给出含有错误率的一致特征子集概念，然后利用信息熵和拉普拉斯错误估计函数构造了特征子集选择启发式算法ＥＦＳ（ｅｎｔｒｏｐｙｂａｓｅｄｆｅａｔｕｒｅｓｕｂｓｅｔｓｅｌｅｃｔｉｏｎ）．将该算法应用于两个实际领域的学习问题，并与ＧＦＳ（ｇｒｅｅｄｙｆｅａｔｕｒｅｓｕｂｓｅｔｓｅｌｅｃｔｉｏｎ）算法进行了比较．实验结果表明，ＥＦＳ选择的特征子集更具有代表性。FSS(feature subset selection) is an important problem in the fields of machine learning and pattern recognition. Minimum FSS problem has been proved NP hard. However, existing heuristic algorithms are based on the consistency of positive and negative examples set, and a more optimal feature subset is hard to be produced under the noisy data in application to real world domains. In this paper, from the degree of statistics, the effects of noisy data on FSS is analyzed firstly, and a concept of consistent feature subset which contains error rate is given. Then a heuristic algorithm——EFS (entropy based feature subset selection) based on information theoretic entropy measure and Laplace error rate is presented. It is also applied to two real world domains and is compared with GFS (greedy feature subset selection). The experimental results show that EFS can produce more representative feature subset, and can solve the noisy problem in the practical application effectively.

关 键 词：特征子集选择 信息熵 启发式算法 NP问题 

分 类 号：O22[理学—运筹学与控制论]