BazEkon - The Main Library of the Cracow University of Economics

BazEkon home page

Main menu

Azad Mohammad (King Abdullah University of Science and Technology, Saudi Arabia), Moshkov Mikhail (King Abdullah University of Science and Technology, Saudi Arabia)
Minimizing Size of Decision Trees for Multi-label Decision Tables
Annals of Computer Science and Information Systems, 2014, vol. 2, s. 67-74, rys., tab., bibliogr. 20 poz.
Drzewo decyzyjne, Proces decyzyjny, Algorytmy, Wiedza
Decision tree, Decision proces, Algorithms, Knowledge
We used decision tree as a model to discover the knowledge from multi-label decision tables where each row has a set of decisions attached to it and our goal is to find out one arbitrary decision from the set of decisions attached to a row. The size of the decision tree can be small as well as very large. We study here different greedy algorithms as well as dynamic programming algorithms to minimize the size of the decision trees. Some of the considered algorithms are good enough for the minimization of number of nodes (at most 18.92% difference), number of nonterminal nodes (at most 20.76% difference), and number of terminal nodes (at most 18.71% difference) relative to the optimal result obtained by dynamic programming algorithm.(original abstract)
Full text
  1. Asuncion A. and Newman D. J., "UCI Machine Learning Repository," mlearn/, 2007.
  2. Azad M., Chikalov I., Moshkov M., "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.
  3. Azad M., Chikalov I., Moshkov M., and Zielosko B., "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, ser. CEUR Workshop Proceedings, L. Popova-Zeugmann, Ed., 2012, vol. 928.
  4. Blockeel H., Schietgat L., Struyf J., Dzeroski S., and Clare A., "Decision trees for hierarchical multilabel classification: A case study in functional genomics," in PKDD 2006, Berlin, Germany, Proceedings, ser. LNCS, J. Fürnkranz, T. Scheffer, and M. Spiliopoulou, Eds. Springer, 2006, vol. 4213, pp. 18-29.
  5. Boutell M. R., Luo J., Shen X., and Brown C. M., "Learning multi-label scene classification," Pattern Recognition, vol. 37, no. 9, pp. 1757-1771, 2004. doi: 10.1016/j.patcog.2004.03.009
  6. Clare A. and King R. D., "Knowledge discovery in multi-label phenotype data," in PKDD, 2001. doi: 10.1007/3-540-44794-6 pp. 42-53.
  7. Comité F. D., Gilleron R., and Tommasi M., "Learning multi-label alternating decision trees from texts and data," in MLDM, 2003. doi: 10.1007/3-540-45065-3 pp. 35-49.
  8. Cour T., Sapp B., Jordan C., and Taskar B., "Learning from ambiguously labeled images," in CVPR, 2009. doi: 10.1109/CVPRW.2009.5206667 pp. 919-926.
  9. Demsar J., "Statistical comparisons of classifiers over multiple data sets," Journal of Machine Learning Research, vol. 7, pp. 1-30, 2006.
  10. Hüllermeier E. and Beringer J., "Learning from ambiguously labeled examples," Intell. Data Anal., vol. 10, no. 5, pp. 419-439, 2006.
  11. Jin R. and Ghahramani Z., "Learning with multiple labels," in NIPS, 2002, pp. 897-904.
  12. Loza Mencía E.and Fürnkranz J., "Pairwise learning of multilabel classifications with perceptrons," in IJCNN, 2008. doi: 10.1109/IJCNN.2008.4634206 pp. 2899-2906.
  13. Moshkov M. and Chikalov I., "On algorithm for constructing of decision trees with minimal depth," Fundam. Inform., vol. 41, no. 3, pp. 295-299, 2000. doi: 10.3233/FI-2000-41302
  14. Moshkov M.and Zielosko B., Combinatorial Machine Learning - A Rough Set Approach, ser. Studies in Computational Intelligence. Springer, 2011, vol. 360. ISBN 978-3-642-20994-9
  15. Tsoumakas G. and Katakis I., "Multi-label classification: An overview," IJDWM, vol. 3, no. 3, pp. 1-13, 2007.
  16. Tsoumakas G., Katakis I., and Vlahavas I. P., "Mining multi-label data," in Data Mining and Knowledge Discovery Handbook, 2010, pp. 667-685.
  17. Wieczorkowska A., Synak P., Lewis R. A., and Ras Z. W., "Extracting emotions from music data," in ISMIS, 2005. doi: 10.1007/11425274 pp. 456-465.
  18. Zhou Z.-H., Jiang K., and Li M., "Multi-instance learning based web mining," Appl. Intell., vol. 22, no. 2, pp. 135-147, 2005. doi: 10.1007/s10489-005-5602-z
  19. Zhou Z.-H., Zhang M.-L., Huang S.-J., and Li Y.-F., "Multi-instance multi-label learning," Artif. Intell., vol. 176, no. 1, pp. 2291-2320, 2012. doi: 10.1016/j.artint.2011.10.002
  20. Zhu X. and Goldberg A. B., Introduction to Semi-Supervised Learning, ser. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2009
Cited by
Share on Facebook Share on Twitter Share on Google+ Share on Pinterest Share on LinkedIn Wyślij znajomemu