决策树ID3算法的一种改进.doc

文档介绍：决策树ID3算法的一种改进
赵静 摘要 决策树是一种使用信息增益度选择测试属性的分类方法。本文通过对ID3算法的分析,利用凸函数的相关知识化简信息增益度的计算复杂度,从而提高决策树的构造效率。
关键词 决策树;ID3算法;决策树ID3算法的一种改进
赵静 摘要 决策树是一种使用信息增益度选择测试属性的分类方法。本文通过对ID3算法的分析,利用凸函数的相关知识化简信息增益度的计算复杂度,从而提高决策树的构造效率。
关键词 决策树;ID3算法;教学测评
中图分类号TP3 文献标识码A 文章编号 1674-6708(2012)79-0227-01
1 ID3算法简介
ID3算法由Quinlan于1979年提出。其基本思想是:在对训练集进行分类时,以信息熵为度量,用于决策树节点的属性选择,每次优先选取信息量最多的属性对数据进行划分,以构造一颗熵值下降最快的决策树,每个叶子节点对应的实例集中的实例属于同一类。
设样本数据集T有s个样本,每个样本都有u个评估属性,m个类别。评估属性划分T成v个子集,其中中包含样本,属于第类的样本数为(i=1,2,...m)。则有:子集的信息熵:I()==
属性的信息熵为:E()=信息增益为: Gain()=I(T)- E()
2 ID3算法的优点和不足
优点:运用信息论知识选择属性,理论清晰;容易生成IF-THEN语句;对于离散型样本数据处理功能强;ID3自顶向下搜索,节省系统资源,计算时间与样本大小。
不足:ID3算法在选择分类属性时往往选择了取值较多的属性;ID3算法只能处理离散型数据,若分析必须先进行离散化;用ID3算法创建决策树时必须知道所有内部节点。83788689