基于样本结构向量相似度的ID3算法改进

陈全园 侯帅琳 李雅琪

摘 要：通过对ID3算法的深入研究，发现其存在多值偏向、计算复杂和效率不高等问题。为了解决这些问题，文章对ID3算法模型进行了优化，并提出了一种基于向量相似度的改进ID3算法。在计算信息增益时，首先使用二阶麦克劳林公式简化了原始公式，从而减少了ID3算法在log函数上的运算时间和复杂程度。然后通过构造样本结构相似矩阵，并引入向量相似度作为权重，极大程度上避免了多值偏向的问题。通过实例验证对比，文章证明了这种优化在不影响后续运算并保证结果可靠的前提下，能够简化计算过程，并使得生成的决策树的各个分支点更加合理。

关键词：ID3算法;样本结构相似矩阵;向量相似度

中图分类号：TP301.6 文献标识码：A 文章编号：2095-9699（2023）06-0009-07

20 世纪80 年代，Quinlan[1]提出了的ID3 算法，它是将信息增益作为非叶节点的标准，计算样本数据库的信息增益，选择信息增益属性值最大的作为分裂节点，进行构造决策树。由于ID3算法构建的决策树结构清晰直观、易于理解，可以有效地降低数据噪声，是一个很好的处理离散型数据的算法模型。但是ID3算法依旧存在着不可忽视的缺点：（a）多值偏向性。ID3算法计算信息增益时倾向于选择信息熵最大的属性值作为根节点，在数据量偏少或者噪点多的情况下，信息熵最大的并不是最优的。（b）计算量大。在数据量很大的情况下，其计算量太大，并且存在一定的繁余计算，影响数据生成时间，效率不高[2-3]。

针对ID3算法以上不足，一些学者对此进行了相关的改进。文献[4-5]将用户兴趣度引入信息熵的计算公式中来降低多值偏向的影响;文献[6]引用权值进行改进信息增益公式来解决多值依赖问题;文献[7]利用等价无穷小的性质来加快信息增益的计算效率;文献[8]运用泰勒公式和麦克劳林公式，对ID3算法公式进行了化简。

文献都在一定程度上解决了多值偏向的问题，但主观性较强，会影响到客观结果，文章通过构造样本结构相似矩阵，引入向量相似度为其加入权重，从而避免多值偏向的问题，这样有效地避免了人为主观对数据的影响，同时也对ID3算法的信息增益计算进行优化，提高计算效率。

1 ID3算法

ID3算法是一种以信息熵和增益作为构造决策树节点属性的学习算法。选择信息增益最大的属性作为分类属性，从而构造决策树[1，9]。

“收入”为“低”的记录有4条，之前已经计算“收入”为“低”的熵H （S低）=0.295，接下来，根据相似结构矩阵和优化信息增益的中的计算方式，得到“收入”为“低”的条件下各描述属性的优化信息增益Gain'（A）：

Gain'（喜欢的季节）=0;

Gain'（是否商务人）=0.75;

Gain'（驾车水平）=0.5。

对比以上优化信息增益值，描述属性“喜欢的季节”具有最小的数值，因此选择“喜欢的季节”作为“低”的叶子节点。以“喜欢的季节”的属性值“春”“夏”“秋”和“冬”为分支节点的分类属性，计算各描述属性的条件熵及优化信息增益，划分出以属性“收入”为“低”的决策树分支。对于属性“收入”为“中”的决策树分支，按照以上规则，用递归的方法对其计算熵值并进行分裂属性的选择，最终得到的基于样本结构向量相似度的ID3算法生成的决策树，如图2所示。

4.2.3 实例分析与总结

由图1可知，将ID3算法的信息增益的计算公式进行优化化简后，新生成的决策树和原公式生成的决策树完全一致。这表明化简之后的公式，在提高了计算效率，简化计算过程的基础上并没有对结果造成影响，保证了结果的可靠性。

根据图1得出，因为多值偏向的缺点使得“喜欢的季节”成为决策树的第一个根节点，但数据表明这个因素并不能成为购车的决定性因素。反而是优化过后的，如图2所示，“收入”这一属性更符合现实逻辑。由图2可知，基于样本结构向量相似度的ID3算法在一定程度上克服了多值偏向问题，使得分类结果更加符合实际认知。

5 结论

ID3算法是决策树算法中的一种具有代表性的算法，文章利用样本结构相似度矩阵的概念，提出了一种基于样本结构向量相似度的ID3算法。样本结构向量相似度的优点在于它不受属性个数多少的影响，也不需要人为经验判断，可以反映出描述属性和分类属性之间的相似程度，即由描述属性和分类属性构成的结构相似矩阵，其两个列向量在正空间中的夹角，反映了该描述属性对决策的重要程度，夹角越大，两向量越无关，也就是说该描述属性能够很好地对决策进行分类，大大降低数据总体的信息熵，将其引入信息增益的计算，使得决策树根节点的选择更加合理。基于样本结构向量相似度的ID3算法使用客观数据完成建模，得出向量相似度值，克服了ID3算法的多值偏向问题。而二阶麦克劳林对公式的简化，消除函数中复杂的对数运算，提高算法执行效率，没有降低原本的精度，对后续的运算结果并无影响，保证了结果的可靠性。

两种改进的结合，有效地解决了计算复杂，效率低的问题，也一定程度上克服了ID3算法的多值偏向问题。

参考文献：

[1]Quinlan J R.Induction of decision trees[J].Machinelearning，1986，1：81-106.

[2]王利軍.决策树ID3 算法的优化[J].菏泽学院学报，2020，42（5）：15-19，30.

[3]于海平，朱玉全，陈耿，等.一种基于粗糙集理论的决策树构造方法[J].计算机应用与软件，2011，28（2）：80-82.

[4]王永梅，胡学钢.基于用户兴趣度和MID3决策树改进方法[J].计算机工程与应用，2011，47（27）：155-157.

[5]王睿，钟守铭，杨景浩.关于用户兴趣度的判定树算法的优化[J].计算机与数字工程，2006，34（2）：24-25，35.

[6]韩松来，张辉，周华平.基于关联度函数的决策树分类算法[J].计算机应用，2005，25（11）：2655-2657.

[7]黄爱辉，陈湘涛.决策树ID3算法的改进[J].计算机工程与科学，2009，31（6）：109-111.

[8]王苗.决策树ID3算法的改进研究[D].辽宁：辽宁工程技术大学，2011.

[9]Hssina B， Merbouha A， Ezzikouri H， et al.A comparativestudy of decision tree ID3 and C4.5[J].International Journal ofAdvanced Computer Science and Applications，2014，4（2）：13-19.

[10]Cha S-H， Yoon S， Tappert C C. Enhancing binaryfeature vector similarity measures [J].CSIS TechnicalReports，2005（210）：1-18.

[11]张睿.ID3决策树算法分析与改进[D].兰州：兰州大学，2010.

[12]Xia P， Zhang L， Li F. Learning similarity with cosinesimilarity ensemble[J].Information sciences，2015，307：39-52.

[13]陈文，余本功.一种基于多向量相似度的聚类分析方法研究[J].陇东学院学报，2023，34（2）：38-43.

[14]王秀慧，许彩欣.决策树在贷款客户信用评估中的应用[J].现代计算机（专业版），2011（9）：20-22.

[15]董跃华，刘力.基于相关系数的决策树优化算法[J].计算机工程与科学，2015，37（9）：1783-1793.

[16]孟雅蕾，周千明，师红宇，等.基于改进ID3算法的数据分类方法[J].计算机仿真，2022，39（5）：329-332，417.

责任编辑：肖祖铭