决策树ID3算法及其改进

杨洋

摘 要：介绍了数据挖掘的相关概念，数据挖掘中决策树ID3算法的相关概念以及信息增益和信息熵概念。通过实例介绍了ID3算法的主要内容，指出了ID3算法的不足及改进之处。针对该实例提出ID3算法的一种改进算法——MIND算法，并通过MIND算法重新计算实例内容。最后通过实例分析将改进算法与ID3算法进行对比，证明了改进算法的有效性。

关键词关键词：数据挖掘；决策树；ID3算法；MIND算法

DOIDOI：10.11907/rjdk.161585

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2016）008-0046-03

0 引言

ID3算法属于决策树算法当中的一种，它是通过把实例从根结点排列到某个叶子结点来对实例进行分析，叶子结点即为实例所属的分类[1]。决策树上的每一个结点就是对该实例某一个属性的测试，并且该结点的每一个后继分支对应着该属性的一个可能值。分类从根节点开始，对所有的实例通过所选属性进行分割，属性的选择采用最高信息增益法。停止分割的条件是：没有属性可以再对实例进行分割，或者结点上的实例都属于同一目标属性类别。ID3算法主要针对属性选择问题，是决策树学习方法中最为典型的算法，该方法使用信息增益度选择测试属性。

MIND算法可以作为ID3算法的一种改进算法，其算法思想更方便考虑每一个概化数据元组。MIND算法是一种典型的决策树构造方法的构造分类器，是采用数据库中用户定义的函数UDF发现分类规则的算法，也就是在决策树的每一层，为每个属性建立一张维度表，用来存放各个属性的取值属于哪个类别及结点编号，其优点是通过采用UDF实现决策树的构造过程使得分类算法易于与数据库系统集成。……