最优特征子集选择问题

被引：86

作者：

陈彬，洪家荣，王亚东

机构：

[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