- 决策树的关键是选择最优划分属性,希望在划分以后分支结点"纯度"越来越高
- 纯度的计算方法不同,就会导致学习方法不同
-
信息熵:随机变量的不确定性
-
条件熵:随机变量在某些条件下的不确定性
-
信息增益:信息熵-条件熵
-
ID3使用信息增益作为纯度的计算,每次选择信息增益最大的特征进行分裂
-
初始化特征集合和数据集合
-
计算数据集合的信息熵和所有特征的条件熵,选择信息增益最大的进行分裂
-
重复上述步骤,子集只有单一特征则是叶子结点
- 集合D中第k类样本所占的比例为$P_{k}$,那么D的信息熵定义
$$
Entroy(D) = -\sum_{k=1}^{K}P_{k}log_{2}P_{k}
$$
- 条件熵
-
$D_{i}$表示D中特征A取第i个值的样本子集
$$
H(D|a) = \sum_{i=1}^n\frac{|D_{i}|}{D}Entroy(D)
$$
$$
Entroy(D) = -\sum_{k=1}^{K}P_{k}log_{2}P_{k}=-(\frac{8}{17}log_{2}\frac{8}{17}+\frac{9}{17}log_{2}\frac{9}{17})=0.998
$$
- 计算在条件色泽下的信息熵
-
$D_{1}$(青绿) 正例$\frac{3}{6}$ 负例$\frac{3}{6}$
-
$D_{2}$(乌黑) 正例$\frac{4}{6}$ 负例$\frac{2}{6}$
-
$D_{3}$(浅白) 正例$\frac{1}{5}$ 负例$\frac{4}{5}$
- 信息熵计算
$$
Entroy(D_{1}) = -\sum_{k=1}^{K}P_{k}log_{2}P_{k}=-(\frac{3}{6}log_{2}\frac{3}{6}+\frac{3}{6}log_{2}\frac{3}{6})=1
$$
$$
Entroy(D_{2}) = -\sum_{k=1}^{K}P_{k}log_{2}P_{k}=-(\frac{4}{6}log_{2}\frac{4}{6}+\frac{2}{6}log_{2}\frac{2}{6})=0.918
$$
$$
Entroy(D_{3}) = -\sum_{k=1}^{K}P_{k}log_{2}P_{k}=-(\frac{1}{5}log_{2}\frac{1}{5}+\frac{4}{5}log_{2}\frac{4}{5})=0.722
$$
$$
\begin{align}
Gain(D,色泽) = Entroy(D)- \sum_{i=1}^n\frac{|D_{i}|}{D}Entroy(D)
\ = 0.988-(\frac{6}{17}*1.000+\frac{6}{17}*0.918+\frac{5}{17}*0.722)
\=0.109
\end{align}
$$
-
选择增益最大的一个进行分裂
-
然后递归进行下去
-
-
最后得到如图这样的形式
- 遇到独特的特征的时候/条件熵可能0也可能很小/那么信息熵就很大/十分容易过拟合/不具有泛化能力/针对这一点我们C4.5将引入信息增益率
- 没有进行剪枝
- 只能处理离散的数据
- 没有考虑到缺失值
$$
Gain_ ratio(D,a) = \frac{Gain(D,a)}{IV(a)}
$$
$$
IV(a) = -\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}log_{2}\frac{|D^{v}|}{|D|}
$$
$$
IV(触感)=0.874(V=2)\\
IV(色泽)=1.580(V=3)\\
IV(编号)=4.088(V=17)
$$
- 可以看出分母的属性固有值/当属性越特殊那么他的值越大/能够一定限度的解决在使用信息增益的时候/泛化能力不足的特点
- C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。
- C4.5 只能用于分类
