Decision tree classification with bounded number of errors
| Autor: | Felipe de A. Mello Pereira, Eduardo Sany Laber, Aline Medeiros Saettler |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Incremental decision tree
Decision tree learning Decision tree Approximation algorithm Context (language use) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science Applications Theoretical Computer Science Randomized algorithm Combinatorics 010201 computation theory & mathematics Signal Processing 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Tree (set theory) Randomized rounding Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 127:27-31 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2017.06.011 |
| Popis: | Oblivious decision trees are decision trees where every node in the same level is associated with the same attribute. These trees have been studied in the context of feature selection. In this paper, we study the problem of constructing an oblivious decision tree that incurs at most k classification errors, where k is a given integer. We present a randomized rounding algorithm that, given a parameter 0 ϵ 1 / 2 , builds an oblivious decision tree with cost at most ( 3 / ( 1 − 2 ϵ ) ) ln ( n ) O P T ( I ) and produces at most ( k / ϵ ) errors, where O P T ( I ) is the optimal cost and n is the number of objects. The probability of failure of this algorithm is at most ( n − 1 ) / 2 n 2 . The logarithmic factor in the cost of the tree is the best possible attainable, even for k = 0 , unless P = NP . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect