决策树ID3算法的优化*
2021-01-08王利军
菏泽学院学报 2020年5期
关键词:信息
王利军
(安徽经济管理学院信息工程系,安徽 合肥 230031)
Quinlan J R提出的ID3算法[1]是经典的决策树算法,该算法以信息增益作为属性划分的依据,选取信息增益最大的属性作为分裂节点,从而生成决策树.这样的决策树结构简单,易于理解.但这种选取方式倾向属性值较多的属性,而这个属性不一定是最优的,为了避免这种多值依赖现象,许多学者提出了各种方案,如文献[2]引入属性的相关子集进行分类;文献[3]引用权值来进行改进信息增益公式来解决多值依赖问题;文献[4]提出了属性优先值的概念进行修正;文献[5]引入属性协调度这一概念来度量属性的分类能力,该分类能力其实是属性与类标号属性之间的相关性的体现;文献[6]提出的GINI指数作为衡量阀值,平衡信息增益对属性值个数多的偏好问题.本文拟采用OneR算法计算出每个属性的准确率来修正ID3算法的多值依赖问题.
另外关于信息增益公式简化计算方面的问题,许多学者提出各种简化方法,如文献[7]利用等价无穷小的性质来加快信息增益的计算效率;文献[8]利用凸函数的性质来简化计算;文献[9]利用知识依赖理论对公式进行简化.本文拟采用幂级数展开式来简化计算.
1 相关理论和举例
1.1 决策树ID3算法
ID3算法是决策树中的常用算法,它是以信息论中的信息熵理论为依据的.
定义1 类标号属性的期望信息量:设包含s个数据的训练样本数据集DB,若DB中类标号属性可划分为n个分类,每个分类表……
登录APP查看全文
