融合信息增益与基尼指数的决策树算法

doi:10.3778/j.issn.1002-8331.2011-0040

摘要/Abstract

摘要： 机器学习中的决策树算法具有重要的数据分类功能，但基于信息增益的ID3算法与基于基尼指数的CART算法的分类功效还值得提高。构造信息增益与基尼指数的自适应集成度量，设计有效的决策树算法，以提升ID3与CART两类基本算法的性能。分析信息增益信息表示与基尼指数代数表示的异质无关性，采用基于知识的加权线性组合来建立信息增益与基尼指数的融合度量，开发决策树启发构造算法IGGI。关于决策树，IGGI算法有效改进了ID3算法与CART算法，相关数据实验表明IGGI算法通常具有更优的分类准确度。

关键词: 决策树, 信息增益, 基尼指数, 不确定性度量, 自适应线性融合, 机器学习

Abstract: Decision tree algorithms in machine learning have significant functions for data classification, but both ID3 algorithm based on information gain and CART algorithm based on Gini index have improvement space for classification performances. An adaptive integrated measure of information gain and Gini index is proposed to establish a robust algorithm of decision trees, so as to promote the two classical algorithms. Heterogeneity and independence of information-expressive information gain and algebra-expressive Gini index are analyzed, a fused measure of information gain and Gini index is constructed by the knowledge-based weighted linear combination, and thus a heuristic algorithm（IGGI） inducing decision trees is designed. Regarding decision trees, IGGI algorithm effectively improves ID3 and CART algorithms, and it generally has better classification accuracy as verified by relevant data experiments.

Key words: decision tree, information gain, Gini index, uncertainty measurement, adaptive linear fusion, machine learning

谢鑫, 张贤勇, 杨霁琳. 融合信息增益与基尼指数的决策树算法[J]. 计算机工程与应用, 2022, 58(10): 139-144.

XIE Xin, ZHANG Xianyong, YANG Jilin. Decision Tree Algorithm Fusing Information Gain and Gini Index[J]. Computer Engineering and Applications, 2022, 58(10): 139-144.

参考文献

[1] HUMBIRD K D，PETERSON J L，MCCLARREN R G.Deep neural network initialization with decision trees[J].IEEE Transactions on Neural Networks and Learning Systems，2019，30（5）：1286-1295.
[2] HUANG Y，QUAN Y H，LIU T.Supervised sparse coding with decision forest[J].IEEE Signal Processing Letters，2019，26（2）：327-331.
[3] PAVY A，RIGLING B.SV-Means：a fast SVM-based level set estimator for phase-modulated radar waveform classification[J].IEEE Journal of Selected Topics in Signal Processing，2018，12（1）：191-201.
[4] QUINLAN J R.Induction of decision trees[J].Machine Learning，1986，1（1）：81-106.
[5] QUINLAN J R.C4.5：programming for machine learning[M].San Mateo：Morgan Kaufmann Publishers，1993.
[6] 唐耀先，余青松.消除属性间依赖的C4.5决策树改进算法[J].计算机应用与软件，2018，35（3）：262-265.
TANG Y X，YU Q S.Improved C4.5 decision trees algorithm that eliminates dependencies between attributes[J].Computer Applications and Software，2018，35（3）：262-265.
[7] 王伟，李磊，张志鸿.具有容噪特性的C4.5算法改进[J].计算机科学，2015，42（12）：268-271.
WANG W，LI L，ZHANG Z H.Improved C4.5 algorithm with noise tolerance[J].Computer Science，2015，42（12）：268-271.
[8] DENISON D G T，MALLICK B K，SMITH A F M.A Bayesian CART algorithm[J].Biometrika，1998，85：363-377.
[9] 骆盈盈，王柯玲，陈川，等.结合递增式学习的CART算法改进[J].计算机工程与设计，2007，28（7）：1520-1522.
LUO Y Y，WANG?K L，CHEN C，et al.Improvement of CART algorithm combined with incremental learning[J].Computer Engineering and Design，2007，28（7）：1520-1522.
[10] CAMPBELL P R J，FATHULLA H，AHMED F.FuzzyCART：a novel fuzzy logic based classification & regression trees algorithm[C]//International Conference on Innovations in Information Technology，2009：255-259.
[11] 张亮，宁芊.CART决策树的两种改进及应用[J].计算机工程与设计，2015，26（5）：1209-1213.
ZHANG L，NING Q.Two improvements and applications of CART decision tree[J].Computer Engineering and Design，2015，26（5）：1209-1213.
[12] 尹儒，门昌骞，王文剑，等.模型决策树：一种决策树加速算法[J].模式识别与人工智能，2018，31（7）：643-652.
YIN R，MEN C Q，WANG W J，et al.Model decision tree：an accelerated algorithm of decision tree[J].Pattern Recognition and Artificial Intelligence，2018，31（7）：643-652.
[13] WEI J M，WANG S Q，WANG M Y，et al.Rough set based approach for inducing decision trees[J].Knowledge-Based Systems，2007，20（8）：695-702.
[14] 姚岳松，张贤勇，陈帅，等.基于属性纯度的决策树归纳算法[J].计算机工程与设计，2021，42（1）：142-149.
YAO Y S，ZHANG X Y，CHEN S，et al.Decision tree induction algorithm based on attribute purity degree[J].Computer Engineering and Design，2021，42（1）：142-149.
[15] 罗计根，杜建强，聂斌，等.融合Gini指数的ID3改进算法[J].南昌大学学报（工科版），2019，41（1）：80-84.
LUO J G，DU J Q，NIE B，et al.Improved ID3 algorithm based on Gini index[J].Journal of Nanchang University（Engineering Edition），2019，41（1）：80-84.
[16] JAIN V，PHOPHALIA A，BHATT J S.Investigation of a joint splitting criteria for decision tree classifier use of information gain and Gini index[C]//2018 IEEE Region 10 Conference（TENCON），2018：2187-2192.
[17] ZHANG X Y，TANG X，YANG J L，et al.Quantitative three-way class-specific attribute reducts based on region preservations[J].International Journal of Approximate Reasoning，2020，117：96-121.
[18] DUA D，GRAFF C.UCI machine learning repository[EB/OL].（2017-05-10）[2020-10-08].http：//archive.ics.uci.edu/ml.