대표적인 의사결정나무 알고리즘의 해석력 비교
Interpretability Comparison of Popular Decision Tree Algorithms
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Most of the open-source decision tree algorithms are based on three splitting criteria (Entropy, Gini Index, and Gain Ratio). Therefore, the advantages and disadvantages of these three popular algorithms need to be studied more thoroughly. Comparisons of the three algorithms were mainly performed with respect to the predictive performance. In this work, we conducted a comparative experiment on the splitting criteria of three decision trees, focusing on their interpretability. Depth, homogeneity, coverage, lift, and stability were used as indicators for measuring interpretability. To measure the stability of decision trees, we present a measure of the stability of the root node and the stability of the dominating rules based on a measure of the similarity of trees. Based on 10 data collected from UCI and Kaggle, we compare the interpretability of DT (Decision Tree) algorithms based on three splitting criteria. The results show that the GR (Gain Ratio) branch-based DT algorithm performs well in terms of lift and homogeneity, while the GINI (Gini Index) and ENT (Entropy) branch-based DT algorithms performs well in terms of coverage. With respect to stability, considering both the similarity of the dominating rule or the similarity of the root node, the DT algorithm according to the ENT splitting criterion shows the best results.
Abstract
Most of the open-source decision tree algorithms are based on three splitting criteria (Entropy, Gini Index, and Gain Ratio). Therefore, the advantages and disadvantages of these three popular algorithms need to be studied more thoroughly. Comparisons of the three algorithms were mainly performed with respect to the predictive performance. In this work, we conducted a comparative experiment on the splitting criteria of three decision trees, focusing on their interpretability. Depth, homogeneity, coverage, lift, and stability were used as indicators for measuring interpretability. To measure the stability of decision trees, we present a measure of the stability of the root node and the stability of the dominating rules based on a measure of the similarity of trees. Based on 10 data collected from UCI and Kaggle, we compare the interpretability of DT (Decision Tree) algorithms based on three splitting criteria. The results show that the GR (Gain Ratio) branch-based DT algorithm performs well in terms of lift and homogeneity, while the GINI (Gini Index) and ENT (Entropy) branch-based DT algorithms performs well in terms of coverage. With respect to stability, considering both the similarity of the dominating rule or the similarity of the root node, the DT algorithm according to the ENT splitting criterion shows the best results.
참고문헌 (30)
- An, A., "Rule Quality Measures for Rule Induction Systems", Computational Intelligence, 17(3), pp.409~424 (2001)
- Baesens, B, "Enterprise Information Systems V", pp.131~137 (2004)
- Belle, V., "Principles and Practice of Explainable Machine Learning", arXiv preprint arXiv:2009.11698, ~ (2020)
- Breiman, L, "Classification and Regression Trees" (1984), Wadsworth and Brooks
- Breiman, L., "Heuristics of Instability and Stabilization in Model Selection", The Annals of Statistics, 24(6), pp.2350~2383 (1996)
- Briand, B., "A Similarity Measureto Assess the Stability of Classification Trees", Computational Statistics and Data Analysis, 53(4), pp.1208~1217 (2009)
- Buntine, W., "A Further Comparison of Splitting Rules for Decision-Tree Induction", Machine Learning, 8(1), pp.75~85 (1992)
- Cano, A., "An Interpretable Classification Rule Mining Algorithm", Information Sciences, 240, pp.1~20 (2013)
- Chandra, B., "A New Node Splitting Measure for Decision Tree Construction", Pattern Recognition, 43(8), pp.2725~2731 (2010)
- Dannegger, F., "Tree Stability Diagnotics and Some Remedies for Instability", Statistics in Medicine, 19(4), pp.475~491 (2000)
- Freitas, A. A., "Comprehensible Classification Models :A Position Paper", ACM SIGKDD Explorations Newsletter, 15(1), pp.1~10 (2014)
- Garcia, S., "Enhancing the Effectiveness and Interpretability of Decision Tree and Rule Induction Classifiers with Evolutionary Training Set Selection over Imbalanced Problems", Applied Soft Computing, 9(4), pp.1304~1314 (2009)
- Goldstein, A., "Penalized Split Criteria for Interpretable Trees", arXiv preprint arXiv:1310.5677, ~ (2013)
- Harris, E., "Information Gain Versus Gain Ratio : A Study of Split Method Biases" (2001), The MITRE Corp.
- Jaworski, M., "New Splitting Criteria for Decision Trees in Stationary Data Streams", IEEE Trans. Neural Netw. Learn. Syst., 29(6), pp.2516~2529 (2018)
- Kotsiantis, S. B., "Supervised Machine Learning : A Review of Classification Techniques", Informatica, 31(3), pp.249~268 (2007)
- Leiva, R. G., "A Novel Hyperparameter-Free Approach to Decision Tree Construction that Avoids Overfitting by Design", IEEE Access, 7, pp.99978~99987 (2019)
- Li, R.-H., "Instability of Decision Tree Classification Algorithms", Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.570~575 (2002)
- Lustrek, M., "What Makes Classification Trees Comprehensible?", Expert Syst. Appl., 62, pp.333~346 (2016)
- Martens, D., "Performance of Classification Models from a User Perspective", Decision Support Systems, 51(4), pp.782~793 (2011)
- Murdoch, W. J., "Interpretable Machine Learning : Definitions, Methods, and Applications", arXiv e-prints, p. arXiv:1901.04592, ~ (2019)
- Norouzi, M, "Efficient Non-Greedy Optimization of Decision Trees", Proceedings of the 28th International Conference on Neural Informsation Processing, pp.1729~1737 (2015)
- Pazzani, M. J., "Acceptance of Rules Generated by Machine Learning Among Medical Experts", Methods of Information in Medicine, 40(5), pp.380~385 (2001)
- Quinlan, J. R, "C4.5 : Programs for Machine Learning" (1993), Morgan Kaufmann
- Quinlan, J. R., "Induction of Decision Trees", Machine Learning, 1(1), pp.81~106 (1986)
- Verbeke, W., "Building Comprehensible Customer Churn Prediction Models with Advanced Rule Induction Techniques", Expert Systems with Applications, 38(3), pp.2354~2364 (2011)
- Wang, Y., "Unifying Attribute Splitting Criteria of Decision Trees by Tsallis Entropy", Proc. IEEE Int. Conf. Acoust., Speech Signal Process(ICASSP), pp.2507~2511 (2017)
- Wang, Y., "A Less-Greedy Two-Term Tsallis Entropy Information Metric Approach for Decision Tree Classification", Knowledge-Based Systems, 120, pp.34~42 (2017)
- Zhao, Y., "Comparison of Decision Tree Methods for Finding Active Objects", Advances in Space Research, 41(12), pp.1955~1959 (2008)