基于相关系数的ID3优化算法

摘要/Abstract

摘要：

ID3算法是目前最具有影响力的一种决策树构造算法，但仍然有许多的缺点，例如在多值属性偏向方面

的问题、计算时间复杂度高、效率不高等问题。提出了一种基于斯皮尔曼等级相关系数的ID3决策树构造

优化算法，利用相关系数克服了ID3算法在多值属性偏向方面的问题，在一定程度上提高了算法的分类准

确率。利用相关数学知识对计算过程进行了化简，减少了ID3算法在log运算上的运行时间。最后通过实

验验证了优化后的算法是可行的，且在准确率和运行速度方面都有更好的表现。

关键词: 决策树, ID3算法, 信息熵, 斯皮尔曼等级, 相关系数

Abstract:

The ID3 algorithm is the most influential algorithm in decision tree construction. However,

it has some disadvantages, such as timeconsuming, low efficiency and multivalue

attribute bias problem. We propose an improved ID3 algorithm based on Spearman Rank, which

optimizes the inadequacy of the attribute selection criterion. We overcome the main

drawback of the ID3 algorithm, which is to select attributes of more value by using

correlation coefficients, thus the accuracy of classification is improved. Meanwhile, we

reduce the time spent on log calculation by using related mathematical theories. Finally,

we conduct several experiments to verify the feasibility of the improved algorithm. Its

accuracy and efficiency are proved better than the ID3 algorithm.

Key words: decision tree, ID3 algorithm, information entropy, Spearman Rank, correlation coefficients

吴思博，陈志刚，黄瑞. 基于相关系数的ID3优化算法[J]. 计算机工程与科学.

WU Sibo，CHEN Zhigang，HUANG Rui. An improved ID3 algorithm based on correlation coefficients[J]. Computer Engineering & Science.

参考文献

［1］Wang Yongmei, Hu Xuegang. Improved decision tree algorithm based on userinterest

and MID3［J］.Computer Engineering & Applications,2011,47(27):155157.(in Chinese)

［2］Han Songlai, Zhang Hui, Zhou Huaping.Association function algorithm for decision

tree［J］.Computer Applications,2005,25(11):26552657.(in Chinese)

［3］Ye Mingquan, Hu Xuegang. Inproved decision tree algorithm based on grey weighted

correlated degree［J］.Computer Engineering and Applications,2007,43(32):171173.(in

Chinese)

［4］Zhang Chunlai,Zhang Lei.A new ID3 algorithm based on revised information gain

［J］.Computer Engineering & Science,2008,30(11):4649.(in Chinese)

［5］Huang Aihui,Chen Xiangtao.An improved ID3 algorithm of decision trees

［J］.Computer Engineering & Science,2009,31(6):109111.(in Chinese)

［6］Dong Yuehua, Liu Li. An optimized algorithm of decision tree based on correlation

coefficients［J］.Computer Engineering & Science, 2015,37(9):17841793.(in Chinese)

［7］Han J,Kamber M,Pei Jian.Data mining:Concepts and techniques［M］.
San Francisco:Morgan Kaufmann Publishers,2011.

［8］Meng X, Ma Z, Zhang X, et al. A categorization approach based on adapted decision tree

algorithm for Web databases query results［J］.Journal of Computer Research &

Development,2012,49(12):26562670.(in Chinese)

［9］Salzberg S L. Book review:C4.5:Programs for machine learning［J］.Machine

Learning,1994,16(3):235240.

［10］Quinlan J R.Improved use of continuous attributes in C4.5［J］.Journal of Artificial

Intelligence Research,1996,4(1):7790.

［11］Yu Jinping,Huang Ximei,Li Kangshun.Improved ID3 algorithm based on new

attributes selection criterion［J］.Application Research of Computers,2012,29(8):2895

2898.(in Chinese)

［12］Wang Hairui, Li Wei. Decision tree algorithm based on association rules

［J］.Computer Engineering,2011,37(9):104106.(in Chinese)

［13］Capkun S, Hamdi M, Hubaux J P.GPSfree positioning in mobile Ad Hoc networks

［J］.Cluster Computing,2002,5(2):157167.

［14］Du Xishou,Chen Shuqiao,Zhang Jianhui.Research on unidirectional P2P traffic

identification methods based on C4.5 decision tree［J］.Journal of Chinese Computer

Systems,2013,34(2):247252.(in Chinese)

［15］Quinlan J R.Induction of decision trees［J］. Machine Learning,1986,1(1):257264.

［16］Hightower J,Borriello G.Location systems for ubiquitous computing

［J］.Computer,2001,34(8):5766.

［17］Spearman C.The proof and measurement of association between two things［J］.American

Journal of Psychology,1987,100(34):44171.

附中文参考文献：

［1］王永梅,胡学钢.基于用户兴趣度和MID3决策树改进方法.［J］.计算机工程与应用,2011,47

(27):155157.

［2］韩松来,张辉,周华平.基于关联度函数的决策树分类算法［J］.计算机应用,2005,25(11):2655

2657.

［3］叶明权,胡学钢.一种基于灰色关联度的决策树改进算法［J］.计算机工程与应用,2007,43(32):171

173.

［4］张春来，张磊.一种基于修正信息增益的ID3算法［J］.计算机工程与科学.2008.30(11):4649.

［5］黄爱辉,陈湘涛.决策树 ID3 算法的改进［J］.计算机工程与科学,2009,31(6):109111.

［6］董跃华,刘力.基于相关系数的决策树优化算法［J］.计算机工程与科学,2015,37(9):17831793.

［8］孟祥福,马宗民,张霄雁,等.基于改进决策树算法的Web数据库查询结果自动分类方法［J］.计算机

研究与发展,2012,49(12):26562670.

［11］喻金平,黄细妹,李康顺.基于一种新的属性选择标准的ID3改进算法［J］.计算机应用研

究,2012,29(8):28952898.

［12］汪海锐,李伟.基于关联规则的决策树算法［J］.计算机工程,

2011,37(9):104106.

［14］杜锡寿,陈庶樵,张建辉.基于C4.5决策树的单向P2P流量识别方法研究［J］.小型微型计算机系

统,2013,34(2):247252.

[1]	崔弘, 赵双, 张广胜, 苏金树. 基于机器学习的移动代理应用流量识别方法[J]. 计算机工程与科学, 2022, 44(04): 654-664.
[2]	贾俊杰, 段超强. 基于评分离散度的托攻击检测算法[J]. 计算机工程与科学, 2022, 44(03): 554-562.
[3]	王鑫, 陈建凯, 翟俊海, . 区间值属性单调决策树算法的扩展[J]. 计算机工程与科学, 2020, 42(03): 557-563.
[4]	陈丽芳,冯力静,刘保相. 神经网络规则优化建模与应用[J]. 计算机工程与科学, 2019, 41(12): 2247-2254.
[5]	肖雪,薛善良. 基于改进的OPTICS聚类和LOPW的离群数据检测算法[J]. 计算机工程与科学, 2019, 41(05): 885-892.
[6]	邵俊健，王士同. 高维数据的增量式聚类算法的距离度量选择研究[J]. 计算机工程与科学, 2019, 41(02): 214-223.
[7]	陈力1，费洪晓2，丁海伦2，成琳2，翟纪宇2. 基于双决策树的数据采样方法[J]. 计算机工程与科学, 2019, 41(01): 130-135.
[8]	刘国梁，钱晓东. 基于加权网络结构的冷门资源推荐算法[J]. 计算机工程与科学, 2018, 40(05): 916-923.
[9]	黄冬梅1，杜艳玲1,2，张律文1. 基于信息熵种子点选取的流线可视化[J]. 计算机工程与科学, 2018, 40(03): 411-417.
[10]	陈秀明1,2,钱丽1,3,胡贤德1,李敬明1,2,张怡文1. 直觉犹豫模糊集的相关系数在群推荐中的应用[J]. 计算机工程与科学, 2017, 39(11): 2139-2144.
[11]	高双，桑庆兵，严大卫. 基于非下采样轮廓波变换和多核学习的盲图像质量评价[J]. 计算机工程与科学, 2017, 39(06): 1171-1178.
[12]	张元鸣，陈苗，陆佳炜，徐俊，肖刚. 基于MapReduce的Bagging决策树优化算法[J]. 计算机工程与科学, 2017, 39(05): 841-848.
[13]	钟伟1，黄元亮2. 基于特征融合与决策树技术的表情识别方法[J]. 计算机工程与科学, 2017, 39(02): 393-398.
[14]	陈曦，成韵姿. 一种优化组合相似度的协同过滤推荐算法[J]. 计算机工程与科学, 2017, 39(01): 180-187.
[15]	孙刚1,2，张靖1,3. 面向高维微阵列数据的集成特征选择算法[J]. J4, 2016, 38(07): 1330-1337.