Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/04355E5F-CBEB-4FC0-A75C-59EF43C5C18F | - |
| Αναγνωριστικό | http://link.springer.com/article/10.1023%2FA%3A1022445500761 | - |
| Αναγνωριστικό | 10.1023/A:1022445500761 | - |
| Γλώσσα | en | - |
| Μέγεθος | 28 pages | en |
| Τίτλος | Building decision trees with constraints | en |
| Δημιουργός | Garofalakis Minos | en |
| Δημιουργός | Γαροφαλακης Μινως | el |
| Δημιουργός | Hyun Dongjoon | en |
| Δημιουργός | Rastogi Rajeev | en |
| Δημιουργός | Shim Kyuseok | en |
| Εκδότης | Kluwer | en |
| Περίληψη | Classification is an important problem in data mining. Given a database of records, each with a class label, a classifier generates a concise and meaningful description for each class that can be used to classify subsequent records. A number of popular classifiers construct decision trees to generate class models. Frequently, however, the constructed trees are complex with hundreds of nodes and thus difficult to comprehend, a fact that calls into question an often-cited benefit that decision trees are easy to interpret. In this paper, we address the problem of constructing “simple” decision trees with few nodes that are easy for humans to interpret. By permitting users to specify constraints on tree size or accuracy, and then building the “best” tree that satisfies the constraints, we ensure that the final tree is both easy to understand and has good accuracy. We develop novel branch-and-bound algorithms for pushing the constraints into the building phase of classifiers, and pruning early tree nodes that cannot possibly satisfy the constraints. Our experimental results with real-life and synthetic data sets demonstrate that significant performance speedups and reductions in the number of nodes expanded can be achieved as a result of incorporating knowledge of the constraints into the building step as opposed to applying the constraints after the entire tree is built. | en |
| Τύπος | Peer-Reviewed Journal Publication | en |
| Τύπος | Δημοσίευση σε Περιοδικό με Κριτές | el |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2015-10-29 | - |
| Ημερομηνία Δημοσίευσης | 2003 | - |
| Θεματική Κατηγορία | Algorithmic knowledge discovery | en |
| Θεματική Κατηγορία | Factual data analysis | en |
| Θεματική Κατηγορία | KDD (Information retrieval) | en |
| Θεματική Κατηγορία | Knowledge discovery in data | en |
| Θεματική Κατηγορία | Knowledge discovery in databases | en |
| Θεματική Κατηγορία | Mining, Data | en |
| Θεματική Κατηγορία | data mining | en |
| Θεματική Κατηγορία | algorithmic knowledge discovery | en |
| Θεματική Κατηγορία | factual data analysis | en |
| Θεματική Κατηγορία | kdd information retrieval | en |
| Θεματική Κατηγορία | knowledge discovery in data | en |
| Θεματική Κατηγορία | knowledge discovery in databases | en |
| Θεματική Κατηγορία | mining data | en |
| Θεματική Κατηγορία | Classification | en |
| Θεματική Κατηγορία | Decision tree | en |
| Θεματική Κατηγορία | Branch-and-bound algorithm | en |
| Θεματική Κατηγορία | Constraint | en |
| Βιβλιογραφική Αναφορά | M. Garofalakis, D. Hyun, R. Rastogi and K. Shim, "Building decision trees with constraints", Data Min. Knowl. Disc., vol 7, no. 2, pp. 187-214, Apr. 2003. doi:10.1023/A:1022445500761 | en |
Copyright © DIAS 2013
