Classification and Optimization of Decision Trees for Inconsistent Decision Tables Represented as MVD tables

• Autorzy: Mohammad Azad , Mikhail Moshkov
• Języki publikacji: EN

Abstrakty

EN

Decision tree is a widely used technique to discover patterns from consistent data set. But if the data set is inconsistent, where there are groups of examples (objects) with equal values of conditional attributes but different decisions (values of the decision attribute), then to discover the essential patterns or knowledge from the data set is challenging. We consider three approaches (generalized, most common and many-valued decision) to handle such inconsistency. We created different greedy algorithms using various types of impurity and uncertainty measures to construct decision trees. We compared the three approaches based on the decision tree properties of the depth, average depth and number of nodes. Based on the result of the comparison, we choose to work with the many-valued decision approach. Now to determine which greedy algorithms are efficient, we compared them based on the optimization and classification results. It was found that some greedy algorithms (Mult_ws_entSort, and Mult_ws_entML) are good for both optimization and classification.(original abstract)

Słowa kluczowe

EN

Objectives trees; Classification trees; Optimal decisions; Algorithms; Optimalization; Classification; Decision tree

PL

Drzewa celów; Drzewa klasyfikacyjne; Decyzje optymalne; Algorytmy; Optymalizacja; Klasyfikacja; Drzewo decyzyjne

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2015
• Tom: 5
• Strony: 31--38

Twórcy

autor

Mohammad Azad

• Computer, Electrical & Mathematical Sciences & Engineering Division King Abdullah University of Science and Technology Thuwal , Saudi Arabia

autor

Mikhail Moshkov

• Computer, Electrical & Mathematical Sciences & Engineering Division King Abdullah University of Science and Technology Thuwal , Saudi Arabia

Bibliografia

• K. DembczyÅDski, S. Greco, W. KotÅ ˇ Cowski, and R. SÅ ´ CowiÅ ´ Dski, ˇ "Optimized generalized decision in dominance-based rough set approach," in Rough Sets and Knowledge Technology, ser. Lecture Notes in Computer Science, 2007, vol. 4481, pp. 118-125.
• J. Mingers, "An empirical comparison of selection measures for decision-tree induction," Machine Learning, vol. 3, no. 4, pp. 319-342, 1989. doi: 10.1007/BF00116837. [Online]. Available: http://dx.doi.org/10.1007/BF00116837
• M. Moshkov and B. Zielosko, Combinatorial Machine Learning - A Rough Set Approach, ser. Studies in Computational Intelligence. Springer, 2011, vol. 360. ISBN 978-3-642-20994-9
• M. Azad, I. Chikalov, M. Moshkov, and B. Zielosko, "Greedy algorithm for construction of decision trees for tables with many-valued decisions," in Proceedings of the 21th International Workshop on Concurrency, Specification and Programming, Berlin, Germany, September 26-28, 2012. CEUR-WS.org, 2012, vol. 928.
• M. Azad, I. Chikalov, and M. Moshkov, "Three approaches to deal with inconsistent decision tables - comparison of decision tree complexity," in RSFDGrC, 2013. doi: 10.1007/978-3-642-41218-9 pp. 46-54.
• M. Azad and M. Moshkov, "Minimization of decision tree average depth for decision tables with many-valued decisions," Procedia Computer Science, vol. 35, no. 0, pp. 368 - 377, 2014. doi: http://dx.doi.org/10.1016/j.procs.2014.08.117
• "Minimization of decision tree depth for multi-label decision tables," in Granular Computing (GrC), 2014 IEEE International Conference on, vol. 0. IEEE, 2014. doi: 10.1109/GRC.2014.6982798
• "Minimizing size of decision trees for multi-label decision tables," in Computer Science and Information Systems (FedCSIS), 2014 Federated Conference on, vol. 0. IEEE, 2014. doi: 10.15439/2014F256
• J. Demsar, "Statistical comparisons of classifiers over multiple data sets," Journal of Machine Learning Research, vol. 7, pp. 1-30, 2006.
• A. Asuncion and D. J. Newman, "UCI Machine Learning Repository," http://www.ics.uci.edu/ mlearn/, 2007.
• J. Alcalá-Fdez, A. Fernández, J. Luengo, J. Derrac, and S. García, "KEEL data-mining software tool: Data set repository, integration of algorithms and experimental analysis framework," Multiple-Valued Logic and Soft Computing, vol. 17, no. 2-3, pp. 255-287, 2011.
• G. Tsoumakas and I. Katakis, "Multi-label classification: An overview," IJDWM, vol. 3, no. 3, pp. 1-13, 2007.
• T. Cour, B. Sapp, C. Jordan, and B. Taskar, "Learning from ambiguously labeled images," in CVPR, 2009. doi: 10.1109/CVPRW.2009.5206667 pp. 919-926.
• E. Hüllermeier and J. Beringer, "Learning from ambiguously labeled examples," Intell. Data Anal., vol. 10, no. 5, pp. 419-439, 2006.
• R. Jin and Z. Ghahramani, "Learning with multiple labels," in NIPS, 2002, pp. 897-904.
• A. Clare and R. D. King, "Knowledge discovery in multi-label phenotype data," in PKDD, 2001. doi: 10.1007/3-540-44794-6 pp. 42-53.
• M. Azad and M. Moshkov, "'misclassification error' greedy heuristic to construct decision trees for inconsistent decision tables," in International Conference on Knowledge Discovery and Information Retrieval. SCITEPRESS, 2014, pp. 184-191.

Identyfikatory

DOI

10.15439/2015F231