Dynamic Programming Approach for Partial Decision Rule Optimization

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

Abstrakty

EN

This paper is devoted to the study of an extension of dynamic programming approach which allows optimization of partial decision rules relative to the length or coverage. We introduce an uncertainty measure J(T) which is the difference between number of rows in a decision table T and number of rows with the most common decision for T. For a nonnegative real number , we consider γ-decision rules (partial decision rules) that localize rows in subtables of T with uncertainty at most γ. Presented algorithm constructs a directed acyclic graph Δ(T) which nodes are subtables of the decision table T given by systems of equations of the kind "attribute = value". This algorithm finishes the partitioning of a subtable when its uncertainty is at most . The graph Δ(T) allows us to describe the whole set of so-called irredundant γ-decision rules. We can optimize such set of rules according to length or coverage. This paper contains also results of experiments with decision tables from UCI Machine Learning Repository.

Słowa kluczowe

EN

partial decision rules; length; coverage; dynamic programming

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 119, nr 3/4
• Strony: 233--248
• Opis fizyczny: Bibliogr. 53 poz., tab., wykr.

Twórcy

autor

Amin T.

autor

Chikalov I.

autor

Moshkov M.

autor

Zielosko B.

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

Bibliografia

• [1] Agrawal, R., Srikant, R.: Fast algorithms for mining association rules in large databases, in: Proceedings of the 20th International Conference on Very Large Data Bases (J. B. Bocca, M. Jarke, C. Zaniolo, Eds.), VLDB '94, Morgan Kaufmann, 1994, 487-499.
• [2] Alkhalid, A., Chikalov, I., Husain, S., Moshkov, M.: Extensions of dynamic programming as a new tool for decision tree optimization, Emerging Paradigms in Machine Learning (S. Ramanna, R. J. Howlett, L. C. Jain, Eds.), Springer, 2012, (to appear).
• [3] Alkhalid, A., Chikalov, I., Moshkov, M.: On algorithm for building of optimal _-decision trees, in: RSCTC 2010 (M. S. Szczuka, M. Kryszkiewicz, S. Ramanna, R. Jensen, Q. Hu, Eds.), vol. 6086 of LNCS, Springer, Heidelberg, 2010, 438-445.
• [4] Amin, T., Chikalov, I., Moshkov, M., Zielosko, B.: Dynamic programming algorithm for optimization of _-decision rules, in: 20th International Workshop Concurrency, Specification and Programming CS&P 2011, September 28-30, Pułtusk, Poland (M. Szczuka, L. Czaja, A. Skowron, M. Kacprzak, Eds.), Białystok University of Technology, 2011, 10-16.
• [5] Amin, T., Chikalov, I., Moshkov, M., Zielosko, B.: Dynamic programming approach for exact decision rule optimization, in: Rough Sets and Intelligent Systems. To the Memory of Professor Zdzisław Pawlak (A. Skowron, Z. Suraj, Eds.), Springer, 2012, 209-224.
• [6] Amin, T., Chikalov, I., Moshkov, M., Zielosko, B.: Dynamic programming approach to optimization of approximate decision rules, Inf. Sci., 2012, (submitted).
• [7] An, A., Cercone, N.: ELEM2: a learning system for more accurate classifications, in: Proceedings of the 12th Biennial Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence, Springer-Verlag, London, UK, 1998, 426-441.
• [8] Asuncion, A., Newman, D. J.: UCI Machine Learning Repository, http://www.ics.uci.edu/~mlearn/, 2007.
• [9] Bazan, J. G., Nguyen, H. S., Nguyen, T. T., Skowron, A., Stepaniuk, J.: Synthesis of decision rules for object classification, in: Incomplete Information: Rough Set Analysis (E. Orłowska, Ed.), Physica-Verlag, Heidelberg, 1998, 23-57.
• [10] Błaszczyński, J., Słowiński, R., Susmaga, R.: Rule-based estimation of attribute relevance, in: RSKT 2011 (J. Yao, S. Ramanna, G. Wang, Z. Suraj, Eds.), vol. 6954 of LNCS, Springer, 2011, 36-44.
• [11] Błaszczyński, J., Słowiński, R., Szela¸g, M.: Sequential covering rule induction algorithm for variable consistency rough set approaches, Inf. Sci., 181(5), 2011, 987-1002.
• [12] Boryczka, U., Kozak, J.: New algorithms for generation decision trees-Ant-Miner and its modifications, in: Foundations of Computational Intelligence (6) (A. Abraham, A. E. Hassanien, A. C. P. de Leon Ferreira de Carvalho, V. Sn´asel, Eds.), vol. 206 of Studies in Computational Intelligence, Springer, 2009, 229-262.
• [13] Brzezińska, I., Greco, S., Słowiński, R.: Mining Pareto-optimal rules with respect to support and confirmation or support and anti-support, Eng. Appl. of AI, 20(5), 2007, 587-600.
• [14] Chikalov, I., Husain, S., Moshkov, M.: Relationships between depth and number of misclassifications for decision trees, in: RSFDGrC 2011 (S. O. Kuznetsov, D. Ślęzak, D. H. Hepting, B. Mirkin, Eds.), vol. 6743 of LNCS, Springer, Heidelberg, 2011, 286-292.
• [15] Chikalov, I., Moshkov, M., Zielosko, B.: Online learning algorithm for ensemble of decision rules, in: RSFDGrC 2011 (S. O. Kuznetsov, D. Ślęzak, D. H. Hepting, B. Mirkin, Eds.), vol. 6743 of LNCS, Springer, Heidelberg, 2011, 310-313.
• [16] Clark, P., Niblett, T.: The CN2 induction algorithm, Mach. Learn., 3(4), 1989, 261-283.
• [17] Cohen, W. W.: Fast effective rule induction, in: ICML 1995 (A. Prieditis, S. J. Russell, Eds.), Morgan Kaufmann, 1995, 115-123.
• [18] Dembczyński, K., Kotłowski,W., Słowiński, R.: ENDER: a statistical framework for boosting decision rules, Data Min. Knowl. Discov., 21(1), 2010, 52-90.
• [19] Frank, E., Witten, I. H.: Generating accurate rule sets without global optimization, in: Proceedings of the Fifteenth International Conference on Machine Learning, ICML '98, Morgan Kaufmann Publishers Inc., 1998, 144-151.
• [20] Fürnkranz, J.: Separate-and-conquer rule learning, Artif. Intell. Rev., 13(1), 1999, 3-54.
• [21] Fürnkranz, J., Flach, P.: An analysis of rule learning heuristics, Technical Report CSTR-03-002, Department of Computer Science, University of Bristol, 2003.
• [22] Fürnkranz, J., Flach, P. A.: An analysis of rule evaluation metrics, in: Proceedings of the 20th International Conference on Machine Learning, ICML '03, AAAI Press, 2003, 202-209.
• [23] Fürnkranz, J., Flach, P. A.: ROC 'n' rule learning-towards a better understanding of covering algorithms, Mach. Learn., 58(1), 2005, 39-77.
• [24] Fürnkranz, J., Knobbe, A. J.: From local patterns to global models: the LeGo approach to data mining, in: From Local Patterns to Global Models: Proceedings of the ECML/PKDD-08 Workshop (J. Fürnkranz, A. J. Knobbe, Eds.), Antwerp, Belgium, 2008, 1-16.
• [25] Grzymała-Busse, J. W.: LERS - a system for learning from examples based on rough sets, in: Intelligent Decision Support. Handbook of Applications and Advances of the Rough Sets Theory (R. Słowiński, Ed.), Kluwer Academic Publishers, 1992, 3-18.
• [26] Jensen, R., Shen, Q.: Semantics-preserving dimensionality reduction: rough and fuzzy-rough-based approaches, IEEE Trans. Knowl. Data Eng., 16(12), 2004, 1457-1471.
• [27] Michalski, R. S.: A theory and methodology of inductive learning, Artif. Intell., 20(2), 1983, 111-161.
• [28] Michalski, S., Pietrzykowski, J.: iAQ: A program that discovers rules, AAAI-07 AI Video Competition, http://videolectures.net/aaai07_michalski_iaq/, 2007.
• [29] Moshkov, M., Chikalov, I.: On algorithm for constructing of decision trees with minimal depth, Fundam. Inform., 41(3), 2000, 295-299.
• [30] Moshkov, M., Piliszczuk, M., Zielosko, B.: Partial Covers, Reducts and Decision Rules in Rough Sets - Theory and Applications, vol. 145 of Studies in Computational Intelligence, Springer, Heidelberg, 2008, ISBN 978-3-540-69027-6.
• [31] Moshkov, M., Zielosko, B.: Combinatorial Machine Learning - A Rough Set Approach, vol. 360 of Studies in Computational Intelligence, Springer, Heidelberg, 2011, ISBN 978-3-642-20994-9.
• [32] Nguyen, H. S.: Approximate boolean reasoning: foundations and applications in data mining, in: T. Rough Sets (J. F. Peters, A. Skowron, Eds.), vol. 4100 of LNCS, Springer, 2006, 334-506.
• [33] Nguyen, H. S., Ślęzak, D.: Approximate reducts and association rules - correspondence and complexity Results, in: RSFDGrC 1999, vol. 1711 of LNCS, Springer, 1999, 137-145.
• [34] Nguyen, S. H.: Discovery of generalized patterns, in: ISMIS 1999 (Z. W. Ra´s, A. Skowron, Eds.), vol. 1609 of LNCS, Springer, 1999, 574-582.
• [35] Nguyen, S. H., Skowron, A., Synak, P.: Discovery of data patterns with applications to decomposition and classification problems, in: Rough Sets in Knowledge Discovery 2: Applications, Case Studies and Software Systems (L. Polkowski, A. Skowron, Eds.), vol. 19 of Studies in Fuzziness and Soft Computing, Physica-Verlag, 1998, 55-97.
• [36] Pawlak, Z.: Rough Sets - Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, 1991.
• [37] Pawlak, Z.: Rough set elements, in: Rough Sets in Knowledge Discovery (L. Polkowski, A. Skowron, Eds.), Physica-Verlag, Heidelberg, 1998, 10-30.
• [38] Pawlak, Z., Skowron, A.: Rough sets and Boolean reasoning, Inf. Sci., 177(1), 2007, 41-73.
• [39] Pawlak, Z., Skowron, A.: Rudiments of rough sets, Inf. Sci., 177(1), 2007, 3-27.
• [40] Quinlan, J. R.: C4.5: Programs for Machine Learning, Morgan Kaufmann Publishers Inc., 1993, ISBN 1-55860-238-0.
• [41] Rissanen, J.: Modeling by shortest data description, Automatica, 14(5), 1978, 465-471.
• [42] Sikora, M.: Decision rule-based data models using TRS and NetTRS - methods and algorithms, T. Rough Sets, 11, 2010, 130-160.
• [43] Sikora, M., Wróbel, Ł.: Data-driven adaptive selection of rules quality measures for improving the rules induction algorithm, in: RSFDGrC 2011 (S. O. Kuznetsov, D. Ślęzak, D. H. Hepting, B. Mirkin, Eds.), vol. 6743 of LNCS, Springer, Heidelberg, 2011, 278-285.
• [44] Skowron, A.: Rough sets in KDD, in: 16th World Computer Congress, IFIP2000, Proc. Conf. Intelligent Information Processing, IIP2000 (Z. Shi, B. Faltings, M. Musem, Eds.), House of Electronic Industry, Beijing, 2000, 1-17.
• [45] 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 (R. Słowinski, Ed.), Kluwer Academic Publishers, Dordrecht, 1992, 331-362.
• [46] Skowron, A., Wang, H., Wojna, A., Bazan, J. G.: A hierarchical approach to multimodal classification, in: RSFDGrC 2005 (D. Ślęzak, J. Yao, J. F. Peters, W. Ziarko, X. Hu, Eds.), vol. 3642 of LNCS, Springer, 2005, 119-127.
• [47] Ślęzak, D.: Normalized decision functions and measures for inconsistent decision tables analysis, Fundam. Inform., 44(3), 2000, 291-319.
• [48] Ślęzak, D., Wróblewski, J.: Order based genetic algorithms for the search of approximate entropy reducts, in: RSFDGrC 2003 (G. Wang, Q. Liu, Y. Yao, A. Skowron, Eds.), vol. 2639 of LNCS, Springer, 2003, 308-311.
• [49] Stefanowski, J., Vanderpooten, D.: Induction of decision rules in classification and discovery-oriented perspectives, Int. J. Intell. Syst., 16(1), 2001, 13-27.
• [50] Wallace, C.: Statistical and Inductive Inference by Minimum Message Length (Information Science and Statistics), Springer-Verlag New York, Inc., 2005, ISBN 038723795X.
• [51] Wróblewski, J.: Finding minimal reducts using genetic algorithm, in: Proc. of the Second Annual Joint Conference on Information Sciences, Wrightsville Beach, NC, 1995, 186-189.
• [52] Wróblewski, J.: Ensembles of classifiers based on approximate reducts, Fundam. Inform., 47(3-4), 2001, 351-360.
• [53] Zielosko, B., Moshkov, M., Chikalov, I.: Optimization of decision rules based on methods of dynamic programming, Vestnik of Lobachevsky State University of Nizhny Novgorod, 6, 2010, 195-200, (in Russian).