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

计算机工程与科学

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

吴思博，陈志刚，黄瑞

(中南大学软件学院,湖南长沙 410075)

收稿日期:2016-07-16 修回日期:2016-09-01 出版日期:2016-11-25 发布日期:2016-11-25
基金资助:
国家自然科学基金（61379057）

An improved ID3 algorithm based on correlation coefficients

WU Sibo，CHEN Zhigang，HUANG Rui

（School of Software,Central South University,Changsha 410075,China）

Received:2016-07-16 Revised:2016-09-01 Online:2016-11-25 Published:2016-11-25

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