Email this article Rough Set Approach to Multivariate Decision Trees Inducing
Abstract
Aimed at the problem of huge computation, large tree size and over-fitting of the testing data for multivariate decision tree (MDT) algorithms, we proposed a novel rough set-based multivariate decision trees (RSMDT) method. In this paper, the positive region degree of condition attributes with respect to decision attributes in rough set theory is used for selecting attributes in multivariate tests. And a new concept of extended generalization of one equivalence relation corresponding to another one is introduced and used for construction of multivariate tests. We experimentally test RSMDT algorithm in terms of classification accuracy, tree size and computing time, using the whole 36 UCI Machine Learning Repository data sets selected by Weka platform, and compare it with C4.5, classification and regression trees (CART), classification and regression trees with linear combinations (CART-LC), Oblique Classifier 1 (OC1), Quick Unbiased Efficient Statistical Trees (QUEST). The experimental results indicate that RSMDT algorithm significantly outperforms the comparison classification algorithms with improved classification accuracy, relatively small tree size, and shorter computing time.
Keywords
References
[1] E. Frank, Y. Wang, S. Inglis, G. Holmes, I. H. Witten, “Using model trees for classification,” Machine Learning, vol. 32, no. 1, pp. 63–76, 1998.
http://dx.doi.org/10.1023/A:1007421302149
[2] J. R. Quinlan, “Induction of decision trees,” Machine Learning, vol. 1, no. 1, pp. 81–106, 1986.
http://dx.doi.org/10.1007/BF00116251
[3] J. R. Quinlan, C4.5: Programs for Machine Learning Morgan Kaufmann Publishers, San Mateo, CA, USA, 1993.
[4] L. Hyafil, R. L. Rivest, “Constructing optimal binary decision trees is NP-complete,” Information Processing Letters, vol. 5, no. 1, pp. 15–17, 1976.
http://dx.doi.org/10.1016/0020-0190(76)90095-8
[5] S. R. Safavin, D. Landgrebe, “A survey of decision tree classifier methodology,” IEEE Transactions on Systems, Man and Cybernetics, vol. 21, no. 3, pp. 660–674, 1991.
http://dx.doi.org/10.1109/21.97458
[6] L. Breiman, J. H. Friedman, R. Olshen, C.J. Stone, Classification and Regression Trees, Wadsworth Int. Group, 1984.
[7] M. Mehta, R. Agrawal, and J. Rissanen, “SLIQ: A fast scalable classifier for data mining,” in Int. Conf. Extending Database Technology (EDBT’96), Avignon, France, pp. 18–32, 1996.
[8] J. Shafer, R. Agrawal, and M. Mehta, “SPRINT: A scalable parallel classifier for data mining,” in Int. Conf. Very Large Data Bases (VLDB’96), Bombay, India, pp. 544–555, 1996.
[9] J. Gehrke, R. Ramakrishnan, and V. Ganti, “Rainforest: A framework for fast decision tree construction of large datasets,” Data Mining and Knowledge Discovery, vol. 4, pp. 127–162, 2000.
http://dx.doi.org/10.1023/A:1009839829793
[10] C. E. Brodley, P. E. Utgo, “Multivariate versus univariate decision trees,” Tech. rep. COINS CR, Dept. of Computer Science, University of Massachusetts at Amherst, 1992.
[11] C. E. Brodley, P. E. Utgoff, “Multivariate Decision Trees, Machine Learning, vol 19, pp. 45–77, 1995.
http://dx.doi.org/10.1007/BF00994660
[12] K. Bennett, “Decision tree construction via linear programming,” in Proc. 4th Midwest Artificial Intelligence Cognitive Science Soc. Conf., Utica, IL, pp. 97–101, 1992.
[13] S.K. Murthy, S. Kasif, S. Salzberg, “A System for in duction of oblique decision trees,” Journal of Artificial Intelligence Research, vol. 2, no. 1, pp. 1–33, 1994.
[14] D. Heath, S. Kasif, and S. Salzberg, “Learning oblique decision trees,” in Proc. 13th Int. Joint Conf. Artificial Intelligence, R. Bajcsy, Ed., San Mateo, CA, pp. 1002–1007, 1993.
[15] X. B. Li, “Multivariate Decision Trees for Data Mining,” Ph.D. dissertation, Univ. South Carolina, Dept. Manage. Sci., Columbia, SC, 1999.
[16] R. Rivest, “Learning decision lists,” Machine Learning, vol. 2, pp. 229–246, 1987.
http://dx.doi.org/10.1007/BF00058680
[17] J. Demsar, “Statistical comparisons of classifiers over multiple data sets,” Journal of Machine Learning Research, vol. 7, pp. 1–30, 2006.
[18] Z. Pawlak, “Rough Sets,” International Journal of Computer and Information Sciences, vol. 11, pp. 341–356, 1982.
http://dx.doi.org/10.1007/BF01001956
[19] Z. Pawlak and A. Skowron, “Rough sets: Some extensions”, Inf. Sci., vol. 1, no. 77, pp. 28–40, 2007.
http://dx.doi.org/10.1016/j.ins.2006.06.006
[20] Z. Pawlak, Rough Sets, Theoretical Aspects of Reasoning about Data, Dordrecht, Kluwer, 1991.
[21] Z. Pawlak, “AI and intelligent industrial appliactions: the rough set perspective,” Cysbernetcis and Systems, vol. 31, pp. 227–252, 2000.
http://dx.doi.org/10.1080/019697200124801
[22] Z. H. Tang, “A novel extension data mining approach based on rough sets pair analysis,” Journal of software, vol. 5, no. 4, pp. 447–454, April 2010.
[23] J. Wei, D. Huang, S. Wang, Z. Ma, “Rough set based decision tree,” In Proceedings of the 4th World Congress on Intelligent Control and Automation, vol. 7, pp. 426–430, 2002.
[24] X. P. Li, M. Dong, An algorithm for constructing decision tree based on variable precision rough set model, in Fourth International Conference on Natural Computation, pp. 280–283, 2008.
http://dx.doi.org/10.1109/ICNC.2008.88
[25] L. J. Huang, M. H. Huang, and B. Guo, A new method for constructing decision tree based on rough set theory, In 2007 IEEE International Conference on Granular Computing, pp. 241–244, 2007.
[26] D. Q. Miao, “Rough sets based on approach for multivariate decision tree construction,” Journal of Software, pp. 425–431, 1997. (in Chinese)
[27] C. C. Chan, “A rough set approach to attribute generalization in data mining,” Information Sciences, vol. 107, pp. 169–176, 1998.
http://dx.doi.org/10.1016/S0020-0255(97)10047-0
[28] R. Slowinski and D. Vanderpooten, “A generalized definition of rough approximations based on similarity,” IEEE Trans. Knowl. Data Eng., vol. 12, no. 2, pp. 331–336, 2000.
http://dx.doi.org/10.1109/69.842271
[29] I. H. Witten and E. Frank, “Data mining: Practical Machine Learning Tools and Techniques, second ed., Morgan Kaufmann, http://prdownloads.sourceforge.net/weka/datasets-UCI.jar, 2005.
[30] C. Blake, C. Merz, UCI Repository of machine learning databases, available on-line: http://www.ics.uci.edu/mlearn/MLRepository.html, 1998.
[31] W. Y. Loh and Y. S. Shih, “Split selection methods for classification trees,” Statist. Sinica, vol. 7, pp. 815–840, 1997.
[32] W. Buntine and R. Caruana, Introduction to IND Version 2.1 and Recursive Partitioning, NASA Ames Research Center, Moffet Field, CA, 1992.
[33] W. Ziarko, “Variable precision rough set model,” J. Comput. Syst. Sci., vol. 46, no. 1, pp. 39–59, 1993.
http://dx.doi.org/10.1016/0022-0000(93)90048-2
Full Text: PDF