Optimization and analysis of decision trees and rules: dynamic programming approach

References

• Agrawal, R., and R. Srikant, 1994. “Fast Algorithms for Mining Association Rules in Large Databases”, In Proceedings edited by J. B. Bocca, M. Jarke, and C. Zaniolo, 487–499. 20th international conference on very large data bases, Santiago de Chile, Chile, September 12–15. Morgan Kaufmann.
   Google Scholar
• Alkhalid, A., I. Chikalov, and M. Moshkov. 2010a. “On Algorithm for Building of Optimal -Decision Trees.” In Lecture Notes in Computer Science Vol. 6086, edited by M. S. Szczuka, M. Kryszkiewicz, S. Ramanna, R. Jensen, and Q. Hu, 438–445. 7th international conference rough sets and current trends in computing, Warsaw, Poland, June 28–30. Heidelberg: Springer.
   Google Scholar
• Alkhalid, A., I. Chikalov, and M. Moshkov, M. 2010. “A Tool for Study of Optimal Decision Trees.” In Lecture Notes in Computer Science Vol. 6401, edited by J. Yu, S. Greco, P. Lingras, G. Wang, and A. Skowron, 353–360. 5th international conference rough set and knowledge technology, Beijing, China, October 15–17. Heidelberg: Springer.
   Google Scholar
• Alkhalid, A., I. Chikalov, and M. Moshkov, 2011a. “Comparison of Greedy Algorithms for -Decision Tree Construction.” In Lecture Notes in Computer Science Vol. 6954, edited by J. T. Yao, S. Ramanna, G. Y. Wang, and Z. Suraj, 178–186. 6th international conference rough set and knowledge technology, Banff, Canada, October 9–12. Heidelberg: Springer.
   Google Scholar
• Alkhalid, A., I. Chikalov, and M. Moshkov, 2011b. “Decision Tree Construction Using Greedy Algorithms and Dynamic Programming – Comparative Study”, In Proceedings edited by M. Szczuka, L. Czaja, A. Skowron, and M. Kacprzak, 1–9. 20th international workshop concurrency, specification and programming, Pułtusk, Poland, September 28–30. Białystok University of Technology.
   Google Scholar
• Alkhalid, A., I. Chikalov, and M. Moshkov, 2011c. “Comparison of Greedy Algorithms for Decision Tree Construction”, In Proceedings edited by J. Filipe and A. L. N. Fred, 438–443. International conference on knowledge discovery and information retrieval, Paris, France, October 26–29. SciTePress.
   Google Scholar
• Alkhalid , A. , Amin , T. , Chikalov , I. , Hussain , S. , Moshkov , M. and Zielosko , B. 2011 . Dagger: A Tool for Analysis and Optimization of Decision Trees and Rules . Computational Informatics, Social Factors and New Information Technologies: Hypermedia Perspectives and Avant-Garde Experiences in the Era of Communicability Expansion, Blue Herons Editions, Bergamo, Italy , 2011 : 29 – 39 .
   Google Scholar
• Alkhalid, A., I. Chikalov, S. Hussain, and M. Moshkov, 2013. “Extensions of Dynamic Programming as a New Tool for Decision Tree Optimization.” In Emerging Paradigms in Machine Learning. Smart Innovation, Systems and Teechnologies Vol. 13, edited by S. Ramanna, R. J. Howlett, and L. C. Jain, 11–29. Springer (Electronic version available).
   Google Scholar
• Amin, T., I. Chikalov, M. Moshkov, and B. Zielosko, 2011. “Dynamic Programming Algorithm for Optimization of -Decision Rules”, In Proceedings edited by M. Szczuka, L. Czaja, A. Skowron and M. Kacprzak, 10–16. 20th international workshop concurrency, specification and programming, Pułtusk, Poland, September 28–30. Białystok University of Technology.
   Google Scholar
• Amin , T. , Chikalov , I. , Moshkov , M. and Zielosko , B. 2012 . Dynamic Programming Approach for Partial Decision Rule Optimization . Fundamenta Informaticae , 119 ( 3–4 ) : 233 – 248 .
   Web of Science ®Google Scholar
• Amin , T. , Chikalov , I. , Moshkov , M. and Zielosko , B. 2013a . Dynamic Programming Approach to Optimization of Approximate Decision Rules . Information Sciences , 221 : 403 – 418 .
   Web of Science ®Google Scholar
• Amin, T., I. Chikalov, M. Moshkov, and B. Zielosko, 2013b. “Dynamic Programming Approach for Exact Decision Rule Optimization.” In Rough Sets and Intelligent Systems – Professor Zdzisław Pawlak in Memoriam. Intelligent Systems Reference Library Vol. 42, edited by A. Skowron, and Z. Surajm, 211–228. Springer (Electronic version available).
   Google Scholar
• Boryczka , U. and Kozak , J. 2009 . New Algorithms for Generation Decision Trees – Ant-Miner and its Modifications . Foundations of Computational Intelligence , 6 : 229 – 262 .
   Google Scholar
• Boryczka, U., and J. Kozak. 2010. “Ant Colony Decision Trees – A New Method for Constructing Decision Trees Based on Ant Colony Optimization.” In Lecture Notes in Computer Science Vol. 6421, edited by J.-S. Pan, S.-M. Chen, and N. T. Nguyen, 373–382. 2nd international conference computational collective intelligence. Technologies and applications, Kaohsiung, Taiwan, November 10–12. Heidelberg: Springer.
   Google Scholar
• Breiman , L. , Friedman , J. H. , Olshen , R. A. and Stone , C. J. 1984 . Classification and Regression Trees , Monterey, CA : Wadsworth & Brooks .
   Google Scholar
• Breitbart , Y. and Reiter , A. 1975 . A Branch-and-bound Algorithm to obtain an Optimal Evaluation Tree for Monotonic Boolean Functions . Acta Informatica , 4 : 311 – 319 .
   Google Scholar
• Chai, B.-B., X. Zhuang, Y. Zhao, and J. Sklansky. 1996. “Binary Linear Decision Tree with Genetic Algorithm.” Vol. 7472, 530–534. 13th international conference on pattern recognition, Vienna, Austria, August 25–29. Los Alamitos, CA: IEEE Computer Society Press.
   Google Scholar
• Chikalov, I., 2001. “Algorithm for Constructing of Decision Trees with Minimal Number of Nodes,” In Lecture Notes in Computer Science Vol. 2005, edited by W. Ziarko, and Y. Y. Yao, 139–143. 2nd international conference rough sets and current trends in computing, Banff, Canada, October 16–19, Revised Papers. Heidelberg: Springer.
   Google Scholar
• Chikalov, I., M. Moshkov, and M. Zelentsova, 2005. “On Optimization of Decision Trees.” In Lecture Notes in Computer Science Vol. 3700, edited by J. F. Peters, and A. Skowron, 18–36. Transactions on Rough Sets IV. Heidelberg: Springer.
   Google Scholar
• Chikalov, I., S. Hussain, and M. Moshkov. 2011a. “Relationships Between Depth and Number of Misclassifications for Decision Trees.” In Lecture Notes in Computer Science Vol. 6743, edited by S. O. Kuznetsov, D. Slȩzak, D. H. Hepting, and B. G. Mirkin, 286–292. 13th international conference rough sets, fuzzy sets, data mining and granular computing, Moscow, Russia, June 25–27. Heidelberg: Springer.
   Google Scholar
• Chikalov, I., M. Moshkov, and B. Zielosko. 2011b. “Online Learning Algorithm for Ensemble of Decision Rules.” In Lecture Notes in Computer Science Vol. 6743, edited by S. O. Kuznetsov, D. Slȩzak, D. H. Hepting, and B. G. Mirkin, 310–313. 13th international conference rough sets, fuzzy sets, data mining and granular computing, Moscow, Russia, June 25–27. Heidelberg: Springer.
   Google Scholar
• Fayyad, U. M., and K. B. Irani. 1992. “The Attribute Specification Problem in Decision Tree Generation.” 10th national conference on artificial intelligence, San Jose, CA, July 12–16. 104–110.
   Google Scholar
• Frank, A., and A. Asuncion. 2010. UCI Machine Learning Repository [online]. Irvine, CA: School of Information and Computer Science, University of California. Accessed September 23, 2011. http://archive.ics.uci.edu/ml.
   Google Scholar
• Garey , M. R. 1972 . Optimal Binary Identification Procedures. . SIAM Journal on Applied Mathematics , 23 : 173 – 186 .
   Web of Science ®Google Scholar
• Heath, D., S. Kasif, and S. Salzberg. 1993. “Induction of Oblique Decision Trees”, In Proceedings edited by B. Ruzena, 1002–1007. 13th international joint conference on artificial intelligence, Chambéry, France, August 28–September 3. Morgan Kaufmann.
   Google Scholar
• Hyafil , L. and Rivest , R. 1976 . Constructing Optimal Binary Decision Trees is NP-complete . Information Processing Letters , 5 : 15 – 17 .
   Google Scholar
• Jensen , R. and Shen , Q. 2000 . Semantics-preserving Dimensionality Reduction: Rough and Fuzzy-rough-based Approaches . IEEE Transactions on Knowledge and Data Engineering , 16 : 1457 – 1471 .
   Google Scholar
• Kononenko, I. 1995. “On Biases in Estimating Multi-valued Attributes”, In Proceedings edited by C. Mellish, 1034–1040. 14th international joint conference on artificial intelligence, Vol. 2. Montréal, Québec, Canada, August 20–25. Morgan Kaufmann.
   Google Scholar
• Liu, B., H. A. Abbass, and B. McKay. 2003. “Classification Rule Discovery with Ant Colony Optimization.” IEEE/WIC international conference on intelligent agent technology, Halifax, Canada, October 13–17, Washington, DC: IEEE Computer Society. 83–88.
   Google Scholar
• Martelli , A. and Montanari , U. 1978 . Optimizing Decision Trees through Heuristically Guided Search . Communications of the ACM , 21 : 1025 – 1039 .
   Web of Science ®Google Scholar
• Martin , J. K. 1997 . An Exact Probability Metric for Decision Tree Splitting and Stopping . Machine Learning , 28 : 257 – 291 .
   Web of Science ®Google Scholar
• Michalski, S. R., and J. Pietrzykowski. 2007. “iAQ: A Program that Discovers Rules.” 22nd AAAI conference on artificial intelligence, AI video competition, Vancouver, British Columbia, Canada, July 22–26. AAAI Press.
   Google Scholar
• Mingers , J. 1987 . Expert Systems – Rule Induction with Statistical Data . Journal of the Operational Research Society , 38 : 39 – 47 .
   Web of Science ®Google Scholar
• Moret , B. E. , Thomason , R. C. and Gonzalez , M. 1980 . The Activity of a Variable and its Relation to Decision Trees . ACM Transactions on Programming Languages and Systems (TOPLAS) , 2 : 580 – 595 .
   Google Scholar
• Moshkov, M. 2005. “Time Complexity of Decision Trees.” In Transactions on Rough Sets III. Lecture Notes in Computer Science Vol. 3400, edited by J. F. Peters, and A. Skowron, 244–459. Heidelberg: Springer.
   Google Scholar
• Moshkov , M. and Chikalov , I. 2000 . On Algorithm for Constructing of Decision Trees with Minimal Depth . Fundamenta Informaticae , 41 : 295 – 299 .
   Google Scholar
• Moshkov , M. and Chikalov , I. 2003 . Consecutive Optimization of Decision Trees Concerning Various Complexity Measures . Fundamenta Informaticae , 61 : 87 – 96 .
   Web of Science ®Google Scholar
• Moshkov, M., M. Piliszczuk, and B. Zielosko. 2008. “Partial Covers, Reducts and Decision Rules in Rough Sets: Theory and Applications.” Studies in computational intelligence Vol. 145. Heidelberg: Springer.
   Google Scholar
• Moshkov, M., and B. Zielosko. 2011. “Combinatorial Machine Learning: A Rough Set Approach.” Studies in Computational Intelligence Vol. 360. Heidelberg: Springer.
   Google Scholar
• Nguyen, H. S. 2006. ”Approximate Boolean Reasoning: Foundations and Applications in Data Mining.” In Transactions on Rough Sets V. Lecture Notes in Computer Science Vol. 4100, edited by J. F. Peters, and A. Skowron, 334–506. Heidelberg: Springer.
   Google Scholar
• Pawlak , Z. 1991 . Rough Sets – Theoretical Aspects of Reasoning About Data , Dordrecht : Kluwer Academic Publishers .
   Google Scholar
• Pawlak , Z. and Skowron , A. 2007 . Rough Sets and Boolean Reasoning . Information Sciences , 177 : 41 – 73 .
   Web of Science ®Google Scholar
• Quinlan , J. R. 1986 . Induction of Decision Trees . Machine Learning , 1 : 81 – 106 .
   Google Scholar
• Quinlan , J. R. 1993 . C4.5: Programs for Machine Learning , San Mateo : Morgan Kaufmann Publishers .
   Google Scholar
• Riddle , P. , Segal , R. and Etzioni , O. 1994 . Representation Design and Brute-force Induction in a Boeing Manufacturing Domain . Applied Artificial Intelligence , 8 : 125 – 147 .
   Web of Science ®Google Scholar
• Skowron, A., and C. Rauszer. 1992. “The Discernibility Matrices and Functions in Information Systems.” In Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory, edited by R. Slowinski, 331–362. Dordrecht: Kluwer Academic Publishers.
   Google Scholar
• Slȩzak, D., and J. Wróblewski. 2003. “Order-based Genetic Algorithms for the Search of Approximate Entropy Reducts.” In Lecture Notes in Computer Science Vol. 2639, edited by G. Wang, Q. Liu, Y. Yao, and A. Skowron, 308–311. 9th international conference rough sets, fuzzy sets, data mining, and granular computing, Chongqing, China, May 26–29. Heidelberg: Springer.
   Google Scholar
• Schumacher , H. and Sevcik , K. C. 1976 . The Synthetic Approach to Decision Table Conversion . Communications of the ACM , 19 : 343 – 351 .
   Web of Science ®Google Scholar
• Wróblewski, J. 1995. “Finding Minimal Reducts using Genetic Algorithm.” 2nd annual join conference on information sciences, Wrightsville Beach, NC, 186–189.
   Google Scholar
• Zielosko , B. , Moshkov , M. and Chikalov , I. 2010 . Optimization of Decision Rules based on Methods of Dynamic Programming . Vestnik of Lobachevsky State University of Nizhni Novgorod , 6 : 195 – 200 .
   Google Scholar