决策树 ID3 算法

2023-12-06 15:25:32 浏览数 (1)

ID3 算法

ID3 算法

  • ID3 算法最早是由罗斯昆 (J.Ross Quinlan) 于1975年提出的一种决策树构建算法，算法的核心是“信息熵”，期望信息越小，信息熵越大，样本纯度越低。。
  • ID3 算法是以信息论为基础，以信息增益为衡量标准，从而实现对数据的归纳分类
  • ID3 算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定的测试属性。

ID3 算法步骤：

  • 1.初始化特征集合和数据集合
  • 2.计算数据集合信息和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点
  • 3.更新数据集合和特征集合(删除上一步使用的特征，并按照特征值来划分不同分支的数据集合)
  • 4.重复 2，3 两步，若子集值包含单一特征，则为分支叶子节点。
信息熵
H(D)=-sum_{k=1}^{K} frac{left|C_{k}right|}{|D|} log _{2} frac{left|C_{k}right|}{|D|}

K是类别，D是数据集，

C_{k}

是类别K下的数据集

条件熵
H(D | A)=sum_{i=1}^{n} frac{left|D_{i}right|}{|D|} Hleft(D_{i}right)

A是特征，i是特征取值

信息增益（ID3）
g(D, A)=H(D)-H(D|A)

特征选择的目的在于选取对训练数据能够分类的特征,关键是其准则

样本集合

D

对特征

A

的信息增益（ID3）

g(D, A)=H(D)-H(D|A)

其中，

H(D)

是数据集

D

的熵，

H(D_i)

是数据集

D_i

的熵，

H(D|A)

是数据集

D

对特征

A

的条件熵。

D_i

是

D

中特征

A

取第

i

个值的样本子集，

C_k

是

D

中属于第

k

类的样本子集。

n

是特征

A

取 值的个数，

K

是类的个数。

ID3 算法缺点

ID3 没有剪枝策略，容易过拟合 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1 只能用于处理离散分布的特征没有考虑缺失值

决策树 测试 集合 数据 算法

0 人点赞