决策树 ID3 算法
ID3 算法
ID3 算法
- ID3 算法最早是由罗斯昆 (J.Ross Quinlan) 于1975年提出的一种决策树构建算法,算法的核心是“信息熵”,期望信息越小,信息熵越大,样本纯度越低。。
- ID3 算法是以信息论为基础,以信息增益为衡量标准,从而实现对数据的归纳分类
- ID3 算法计算每个属性的信息增益,并选取具有最高增益的属性作为给定的测试属性。
ID3 算法步骤:
- 1.初始化特征集合和数据集合
- 2.计算数据集合信息和所有特征的条件熵,选择信息增益最大的特征作为当前决策节点
- 3.更新数据集合和特征集合(删除上一步使用的特征,并按照特征值来划分不同分支的数据集合)
- 4.重复 2,3 两步,若子集值包含单一特征,则为分支叶子节点。
信息熵
H ( D ) = ? ∑ k = 1 K ∣ C k ∣ ∣ D ∣ log ? 2 ∣ C k ∣ ∣ D ∣ H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|} H(D)=?k=1∑K?∣D∣∣Ck?∣?log2?∣D∣∣Ck?∣?
K是类别,D是数据集, C k C_{k} Ck?是类别K下的数据集
条件熵
H
(
D
∣
A
)
=
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
H
(
D
i
)
H(D | A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)
H(D∣A)=i=1∑n?∣D∣∣Di?∣?H(Di?)
A是特征,i是特征取值
信息增益(ID3)
g ( D , A ) = H ( D ) ? H ( D ∣ A ) g(D, A)=H(D)-H(D|A) g(D,A)=H(D)?H(D∣A)
特征选择的目的在于选取对训练数据能够分类的特征,关键是其准则
样本集合 D D D对特征 A A A的信息增益(ID3)
g ( D , A ) = H ( D ) ? H ( D ∣ A ) g(D, A)=H(D)-H(D|A) g(D,A)=H(D)?H(D∣A)
其中, H ( D ) H(D) H(D)是数据集 D D D的熵, H ( D i ) H(D_i) H(Di?)是数据集 D i D_i Di?的熵, H ( D ∣ A ) H(D|A) H(D∣A)是数据集 D D D对特征 A A A的条件熵。 D i D_i Di?是 D D D中特征 A A A取第 i i i个值的样本子集, C k C_k Ck?是 D D D中属于第 k k k类的样本子集。 n n n是特征 A A A取 值的个数, K K K是类的个数。
ID3 算法缺点
ID3 没有剪枝策略,容易过拟合
信息增益准则对可取值数目较多的特征有所偏好,类似“编号”的特征其信息增益接近于 1
只能用于处理离散分布的特征没有考虑缺失值
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!