Title :
NP-Hard Problems of Learning from Examples
Author :
Chen, Bin ; Quan, Guangri
Author_Institution :
Sch. of Software, Harbin Inst. of Technol., Weihai
Abstract :
As designing practical algorithms of learning from examples, one has to deal with some optimization problems. The major optimization problems are: the smallest feature subset selection, the smallest decision tree induction, and the smallest k-DNF induction. In this paper, we show that all these optimization problems listed as above are NP-hard, and we present new greedy algorithms for solving these problems.
Keywords :
decision trees; greedy algorithms; learning (artificial intelligence); optimisation; NP-hard problems; greedy algorithms; learning; optimization; smallest decision tree induction; smallest feature subset selection; smallest k-DNF induction; Algorithm design and analysis; Decision trees; Design optimization; Fuzzy systems; Greedy algorithms; Matrices; NP-hard problem; Software algorithms; Space technology; Training data; Learning from examples; NP-hard; decision trees; feature subset selection; greedy algorithms; optimization problems; rules;
Conference_Titel :
Fuzzy Systems and Knowledge Discovery, 2008. FSKD '08. Fifth International Conference on
Conference_Location :
Shandong
Print_ISBN :
978-0-7695-3305-6
DOI :
10.1109/FSKD.2008.406
