最优特征子集选择问题

被引：85

作者：

陈彬

洪家荣

王亚东

机构：

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

来源：

关键词：

机器学习; 模式识别; 特征子集选择; 集合覆盖; NP难题; 贪心算法;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

机器学习和模式识别面临的一个重要问题，就是特征子集的选择问题，即从一个大的已知特征集合，选择一个子集合来一致地描述已知例子（样本）．特别，最优特征子集选择问题，即最小的特征子集问题的计算复杂性至今还不清楚．在本文中，作者证明了最优特征子集问题是ＮＰ难题，并给出它的一个启发式算法．

引用

页码：133 / 138

页数：6

共 10 条

[1] ClassificationandRegressionTrees. BreimanL,FriedmanJ,OlshenR,StoneC. . 1984
[2] Inductionofdecisiontrees. QuinlanJR. Machine Learning . 1986
[3] Anewsimilarity-basedlearningalgorithmGSandacomparisionwithID3. HongJR,UhrikC. ProcIntComputerScienceConference’’88 . 1988
[4] irrelevantfeaturesandthesubsetselectionproblem. JohnGH,KohaviR,PflogerK. ProcML’’94 . 1994
[5] Learningwithmanyirrelevantfeatures. AlmuallimH,DietterichTG. ProcAAAI-91 . 1991
[6] Approximationalgorithmsforcombinationalproblems. JohnsonDS. JComputerandSystemsScience . 1973
[7] HCV:AHeuristicCoveringAlgorithmforExtensionMatrixApproach. WuX. .
[8] PatternRecognitionAStatisticalApproach. DevijverPA,KittlerJ. . 1982
[9] Greedyattributeselection. CaruanaR,FreitagD. ProcML’’94 . 1994
[10] AEI:anextensionmatrixapproximatemathodforthegeneralcoveringproblem. HongJR. IntJournalofComputerandInformationScience . 1985