A Greedy Algorithm for Construction of Decision Trees for Tables with Many-Valued Decisions : A Comparative Study

• Autorzy: Azad M. , Chikalov I. , Moshkov M. , Zielosko B.
• Języki publikacji: EN

Abstrakty

EN

In the paper, we study a greedy algorithm for construction of decision trees. This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision from the set attached to this row. Experimental results for data sets from UCI Machine Learning Repository and randomly generated tables are presented. We make a comparative study of the depth and average depth of the constructed decision trees for proposed approach and approach based on generalized decision. The obtained results show that the proposed approach can be useful from the point of view of knowledge representation and algorithm construction.

Słowa kluczowe

EN

decision table with many-valued decisions; decision tree; greedy algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 128, nr 1-2
• Strony: 1--15
• Opis fizyczny: Bibliogr. 29 poz., rys., tab.

Twórcy

autor

Azad M.

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

autor

Chikalov I.

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

autor

Moshkov M.

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

autor

Zielosko B.

• Institute of Computer Science, University of Silesia, 39, Będzińska St., Sosnowiec 41-200, Poland

Bibliografia

• [1] Asuncion, A., Newman, D. J.: UCI Machine Learning Repository, http: //www. ics. uci. edu/~mlearn/, 2007.
• [2] Azad, M., Chikalov, I., Moshkov, M., 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 (L. Popova-Zeugmann, Ed.), CEUR-WS.org, 2012, 13-24.
• [3] Azad, M., Chikalov, I., Moshkov, M., Zielosko, B.: Greedy Algorithms for Construction of Approximate Tests, Fundam. Inform., 120(3-4), 2012, 231-242.
• [4] Azad, M., Chikalov, I., Moshkov, M., Zielosko, B.: Tests for Decision Tables with Many-valued Decisions - Comparative Study, in: Federated Conference on Computer Science and Information Systems - FedCSIS 2012, Wrocław, Poland, 9-12 September 2012, Proceedings, CEUR-WS.org, 2012, 271-277.
• [5] Blockeel, H., Schietgat, L., Struyf, J., Dzeroski, S., Clare, A.: Decision Trees for Hierarchical Multilabel Classification: A Case Study in Functional Genomics, in: Knowledge Discovery in Databases: PKDD 2006, 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, Berlin, Germany, September 18-22, 2006, Proceedings (J. Fiirnkranz, T. Scheffer, M. Spiliopoulou, Eds.), vol. 4213 of LNCS, Springer, 2006,18-29.
• [6] Boutell, M. R., Luo, J., Shen, X., Brown, C. M.: Learning Multi-label Scene Classification, Pattern Recognition, 37(9), 2004, 1757-1771.
• [7] Chikalov, I., Zielosko, B.: Decision Rules for Decision Tables with Many-valued Decisions, in: Rough Sets and Knowledge Technology - 6th International Conference, RSKT 2011, Banff, Canada, October 9-12, 2011, Proceedings (J. Yao, S. Ramanna, G. Wang, Z. Suraj, Eds.), vol. 6954 of LNCS, Springer, 2011, 763-768.
• [8] Clare, A., King, R. D.: Knowledge Discovery in Multi-label Phenotype Data, in: Principles of Data Mining and Knowledge Discovery, 5th European Conference, PKDD 2001, Freiburg, Germany, September 3-5, 2001, Proceedings (L. D. Raedt, A. Siebes, Eds.), vol. 2168 of LNCS, Springer, 2001, 42-53.
• [9] Cohen, W. W.: Learning Trees and Rules with Set-valued Features, in: Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, AAAI 96, IAAI96, Portland, Oregon, August 4-8, 1996, Volume 1, AAAI Press / The MIT Press, 1996, 709716.
• [10] Comite, F. D., Gilleron, R., Tommasi, M.: Learning Multi-label Alternating Decision Trees from Texts and Data, in: Machine Learning and Data Mining in Pattern Recognition, Third International Conference, MLDM 2003, Leipzig, Germany, July 5-7, 2003, Proceedings (P. Perner, A. Rosenfeld, Eds.), vol. 2734 of LNCS, Springer, 2003, 35-49.
• [11] Mencia, E. L., Fiirnkranz, J.: Pairwise Learning of Multilabel Classifications with Perceptrons, in: Proceedings of the International Joint Conference on Neural Networks, IJCNN 2008, part of the IEEE World Congress on Computational Intelligence, WCCI 2008, Hong Kong, China, June 1-6, 2008, IEEE, 2008, 2899-2906.
• [12] Moshkov, M., Zielosko, B.: Combinatorial Machine Learning - A Rough Set Approach, Springer, Heidelberg, 2011.
• [13] Moshkov, M., Zielosko, B.: Construction of a-Decision Trees for Tables with Many-valued Decisions, in: Rough Sets and Knowledge Technology - 6th International Conference, RSKT 2011, Banff, Canada, October 9-12, 2011, Proceedings (J. Yao, S. Ramanna, G. Wang, Z. Suraj, Eds.), vol. 6954 of LNCS, Springer, 2011, 486-494.
• [14] Moshkov, M., Zielosko, B.: Construction of Tests for Tables with Many-valued Decisions, in: 20th International Workshop Concurrency, Specification and Programming CS&P 2011, September 28-30, Pułtusk, Poland, Białystok University of Technology, 2011, 376-384.
• [15] Moshkov, M. J.: Greedy Algorithm for Decision Tree Construction in Context of Knowledge Discovery Problems, in: Rough Sets and Current Trends in Computing, 4th International Conference, RSCTC 2004, Uppsala, Sweden, June 1-5, 2004, Proceedings (S. Tsumoto, R. Słowinski, H. J. Komorowski, J. W. Grzymała-Busse, Eds.), vol. 3066 of LNCS, Springer, 2004, 192-197.
• [16] Orłowska, E., Pawlak, Z.: Representation of Nondeterministic Information, Theor. Comput. Sci., 29, 1984, 27-39.
• [17] Pawlak, Z.: Information Systems - Theoretical Foundations, Inform. Systems, 6(3), 1981, 205-218.
• [18] Pawlak, Z.: Rough Sets - Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, 1991.
• [19] Pawlak, Z., Skowron, A.: Rough Sets and Boolean Reasoning, Inf. Sci., 177(1), 2007, 41-73.
• [20] Pawlak, Z., Skowron, A.: Rudiments of Rough Sets, Inf. Sci., 177(1), 2007, 3-27.
• [21] Quinlan, J. R.: Induction of Decision Trees, Mach. Learn., 1986, 81-106.
• [22] Rissanen, J.: Modeling by Shortest Data Description, Automatica, 14(5), 1978, 465-471.
• [23] Skowron, A., Rauszer, C.: The Discernibility Matrices and Functions in Information Systems, in: Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory, Kluwer Academic Publishers, Dordrecht, 1992, 331-362.
• [24] Tsoumakas, G., Katakis, I.: Multi-label Classification: An Overview, IJDWM, 3(3), 2007, 1-13.
• [25] Tsoumakas, G., Katakis, I., Vlahavas, I. P.: Mining Multi-label Data, in: Data Mining and Knowledge Discovery Handbook, 2nd ed., Springer, 2010, 667-685.
• [26] Wieczorkowska, A., Synak, P., Lewis, R. A., Raś, Z. W.: Extracting Emotions from Music Data, in: Foundations of Intelligent Systems, 15th International Symposium, ISMIS 2005, Saratoga Springs, NY, USA, May 25-28, 2005, Proceedings (M.-S. Hacid, N. V Murray, Z. W. Raś, S. Tsumoto, Eds.), vol. 3488 of LNCS, Springer, 2005, 456-465.
• [27] Yang, H., Xu, Z., Zhang, J., Cai, J.: A Constructing Method of Decision Tree and Classification Rule Extraction for Incomplete Information System, International Conference on Computational Aspects of Social Networks, CASoN 2010, Taiyuan, China, 26-28 September 2010, IEEE Computer Society, 2010.
• [28] Zhou, Z.-H., Jiang, K., Li, M.: Multi-instance Learning Based Web Mining, Appl. Intell., 22(2), 2005, 135-147.
• [29] Zhou, Z.-H., Zhang, M.-L., Huang, S.-J., Li, Y.-F.: Multi-instance Multi-label Learning, Artif. Intell., 176(1), 2012, 2291-2320.