Improved Ordinal Decisions Trees Algorithms Based on Rank Entropy
CHEN Jian-Kai, WANG Xi-Zhao, GAO Xiang-Hui
Key Laboratory on Machine Learning and Computational Intelligence of Hebei Province, College of Mathematics and Computer Science, Hebei University, Baoding 071002
Abstract：When the expanded attributes are selected for decision tree learning based on rank entropy, computing the rank mutual information of every single cut for each of the continuous-valued attributes is required to get the expanded attribute by comparing the values of rank mutual information. Therefore, the computational complexity is high. Aiming at this problem, cut-points are divided into stable and unstable cut-points and a mathematical model is established in this paper. The proposed model theoretically proves that the rank mutual information function achieves its maximum not at stable cut-points, but at unstable cut-points. The result means that in the algorithm only traversing the unstable cut-points is required instead of computing the values of the stable cut-points. Thus, the computational efficiency of building decision trees is greatly improved, which is confirmed by the numerical experimental results.
[1] Mitchell T M. Machine Learning. New York, USA: McGraw-Hill, 1997 [2] Wang X Z, Hong J R. Learning Algorithm of Decision Tree Generation for Interval-Valued Attributes. Journal of Software, 1998, 9(8): 637-640(in Chinese) (王熙照,洪家荣.区间值属性决策树学习算法.软件学报,1998, 9(8): 637-640) [3] Quinlan J R. Induction of Decision Tree. Machine Learning, 1986, 1(1): 81-106 [4] Wu X D, Kumar V, Quinlan J R, et al. Top 10 Algorithms in Data Mining. Knowledge and Information Systems, 2008, 14(1): 1-37 [5] Breiman L, Friedman J H, Olshen R A, et al. Classification and Regression Tree. Belmont, USA: Wadsworth International Group, 1984 [6] Wang X Z, Chen B, Qian G L, et al. On the Optimization of Fuzzy Decision Trees. Fuzzy Sets and Systems, 2000, 112(1): 117-125 [7] Wang X Z, Yeung D S. Tsang E C C. A Comparative Study on Heuristic Algorithms for Generating Fuzzy Decision Trees. IEEE Trans on Systems, Man and Cybernetics, 2001, 31(2): 215-226 [8] Wang X Z, Hong J R. On the Handling of Fuzziness for Continuous-Valued Attributes in Decision Tree Generation. Fuzzy Sets and Systems, 1998, 99(3): 283-290 [9] Tsang E C C, Wang X Z, Yeung D S. Improving Learning Accuracy of Fuzzy Decision Trees by Hybrid Neural Networks. IEEE Trans on Fuzzy Systems, 2000, 8(5): 601-614 [10] Shiu S C K, Sun C H, Wang X Z, et al. Maintaining Case-Based Reasoning Systems Using Fuzzy Decision Trees // Blanzieri E, Portinale L, eds. Lecture Notes in Artificial Intelligence. Berlin, Germany: Springer-Verlag. 2000, 1898: 285-296 [11] Wang X Z, Yang C X. Merging-Branches Impact on Decision Tree Induction. Chinese Journal of Computers, 2007, 30(8): 1251-1258 (in Chinese) (王熙照,杨晨晓.分支合并对决策树归纳学习的影响.计算机学报, 2007, 30(8): 1251-1258) [12] Yang C X, Wang X Z, Zhu R X. A Strategy of Merging Branches Based on Margin Enlargement of SVM in Decision Tree Induction // Proc of the IEEE International Conference on Systems, Man and Cybernetics. Taipei, China, 2006, I: 824-828 [13] Wang X Z, Zhao M H, Wang D H. Selection of Parameters in Building Fuzzy Decision Trees // Gedeon T D, Fung L C C, eds. Lecture Notes in Artificial Intelligence. Berlin, Germany: Springer-Verlag, 2003, 2903: 282-292 [14] Lee J W T, Wang X Z, Wang J F. Reduction of Attributes in Ordinal Decision Systems // Yeung D S, ed. Lecture Notes in Artificial Intelligence. Berlin, Germany: Springer-Verlag, 2006, 3930: 578-587 [15] Zopounidis C, Doumpos M. Multicriteria Classification and Sorting Methods: A Literature Review. European Journal of Operational Research, 2002, 138(2): 229-246 [16] Ben-David A, Sterling L, Pao Y H. Learning and Classification of Monotonic Ordinal Concepts. Computational Intelligence, 1989, 5(1): 45-49 [17] Potharst R, Bioch J C. Decision Trees for Ordinal Classification. Intelligent Data Analysis, 2000, 4(2): 97-111 [18] Potharst R. Feelders A J. Classification Trees for Problems with Monotonicity Constrains. SIGKDD Explorations, 2002, 4(1): 1-10 [19] Cao-Van K, Baets B D. Growing Decision Trees in an Ordinal Se-tting. International Journal of Intelligent Systems, 2003, 18(7): 733-750 [20] Barile N, Feelders A J. Nonparametric Monotone Classification with MOCA // Proc of the 8th IEEE International Conference on Data Mining. Pisa, Italy, 2008: 731-736 [21] Kotlowski W, Slowinski R. Rule Learning with Monotonicity Constrains // Proc of the 26th Annual International Conference on Machine Learning. Montreal, Canada, 2009: 537-544 [22] Hu Q H, Guo M Z, Yu D R, et al. Information Entropy for Ordinal Classification. Science China: Information Sciences, 2010, 53(6): 1188-1200 [23] Hu Q H, Che X J, Zhang L, et al. Rank Entropy-Based Decision Trees for Monotonic Classification. IEEE Trans on Knowledge and Data Engineering, 2012, 24(11): 2052-2064
2014, Vol. 27 
