基于C++实现的ID3算法

Renaissance

发布日期: 2019-03-20 08:54:18 浏览量: 440
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

1、算法描述

ID3算法是以信息熵下降速度作为选取测试属性的标准的,决策树生成算法。

信息熵的下降速度用信息增益度来衡量其定义是:

  • 定义1:若存在n个相同概率的消息,则每个消息的概率p是1/n,一个消息传递的信息量为Log2(1/n)

  • 定义2:若有n个消息,其给定概率分布为P=(p1,p2…pn),则由该分布传递的信息量称为P的熵,记为

    1.   I(p)=-(i=1 to n求和)piLog2(pi)。
  • 定义3:若一个记录集合T根据类别属性的值被分成互相独立的类C1C2..Ck,则识别T的一个元素所属哪个类所需要的信息量为Info(T)=I(p),其中P为C1C2…Ck的概率分布,即

    1. P=(|C1|/|T|,…..|Ck|/|T|)
  • 定义4:若我们先根据非类别属性X的值将T分成集合T1,T2…Tn,则确定T中一个元素类的信息量可通过确定Ti的加权平均值来得到,即Info(Ti)的加权平均值为:

    1. Info(X, T)=(i=1 to n 求和)((|Ti|/|T|)Info(Ti))
  • 定义5:信息增益度是两个信息量之间的差值,其中一个信息量是需确定T的一个元素的信息量,另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量,信息增益度公式为:

    1. Gain(X, T)=Info(T)-Info(X, T)

ID3算法的运行过程是:

  • 根据训练样例求出各属性的信息增益度,并选取信息增益度最大的属性作为当前测试属性

  • 根据当前测试属性的值将训练样例分组

  • 对各组重复以上过程,直到每一组中都只有同一个目标类别的训练样例时停止

2、算法分析

  • 相容与不相容数据,对决策树构造有什么影响?

    不相容数据是训练样本中条件属性相同而决策属性不同的数据,说白了也就是矛盾的数据,不相容数据过多会使得生成的决策树缺乏代表性,不相容数据可以通过少数服从多数的方式转化成相容数据,或者干脆将所有不相容的数据从样例数据中删除。

  • 不同数据规模,对决策树构造有什么影响?

    小规模的数据构造出的决策树结构过于简单,决策时误判的概率较高,而规模过大会导致决策树过于复杂,决策时时间和决策树的存储空间消耗过高,因此规模过小过大都不是理想状态,因此应选择适中规模的样例数据。

  • 分析产生过拟合的原因以及相应的解决对策?

    过拟合是指由于训练集不够准确,而决策树是按照训练集高度精确生成的,这就会导致部分情况的误判,这就是过拟合。

    产生过拟合主要是由于训练集中的噪声引起的,可以采取剪枝的方法,主要分为以下两种:前减枝和后剪枝。

    前剪枝法是在完全正确对训练样本进行分类之前较早的停止决策树的生长,可以通过定义一个高度,当决策树生长到该高度时停止决策树的生长。

    后剪枝法是首先构造完整的决策树,允许树过度拟合训练数据,然后对那些置信度不够的结点子树用叶子结点来替代,这个叶子结点的类别为子树中大多数实例所属的类别。

3、程序说明

本程序在VS2008下开发,使用语言C++。其中,.Net运行需有.Net FrameWork 3.5及以上版本的运行环境。

本程序需通过图形界面指定,属性说明文件和训练样例文件:

  • 属性说明文件格式

    • 第一行一个整数表明第几个属性是目标分类属性
    • 以下任意行每一行描述一个属性,第一个字段表示属性名称,后面各字段表示该属性的各可能取值,各字段间用空格分隔
  • 训练样例文件格式

    • 每行一条训练样例,属性顺序根据属性说明文件规定顺序,属性间用空格分隔

上传的附件 cloud_download 基于C++实现的ID3算法.7z ( 97.38kb, 2次下载 )
error_outline 下载需要6点积分

发送私信

聪明但不自以为是,有趣但不哗众取宠,黑暗但不深不见底

8
文章数
11
评论数
最近文章
eject