决策树是一类常见的机器学习算法,决策过程是基于树的结构进行的。叶子结点对应了树的决策结果,子节点对应了属性的测试(例如西瓜的颜色)。决策树的最终目的是产生一棵泛化能力强的树。

决策树基本知识

决策树子节点的生成

决策树的生成方式是一个递归的过程,有根结点开始,生成子节点的情况有下面三种:

  • 当前节点包含的样本全属于一个类别,无需划分
  • 当前节点上所有样本的属性为空(例如缺失了身高这个数据),因此设置节点时,将该节点设置成样本中类别比例最大的那个。
  • 当前节点所包含的样本集合为空时,采用样本的先验概率(例如身高为170的样本最多)来设置样本类

信息熵

熵: entropy,希腊语原意为 内向性即一个系统不受外部干扰时,往内部最稳定状态发展的特性。

熵同时可以作为一个系统的混乱程度的度量,即根据热力学第二定律,一个系统倾向于向增加混乱的程度发展,例如抛一枚硬币,最终的统计结果是正反面都是0.5的概率,对于预测来说,预测正面或者反面的不确定性都是最大的。

信息熵:

信息熵是指接受数据中包含的信息量的平均值,是一种不确定性的度量,越随机的信源,熵越大。熵定义为概率分布的对数的相反数。也即是说,当一个事件发生的可能性越小,当这个事件出现的时候,提供的信息就越多,不确定性越大,熵就越大。
$$
\mathrm{H}(X)=\mathrm{E}[\mathrm{I}(X)]=\mathrm{E}[-\ln (\mathrm{P}(X))]
$$
当数据取自有限样本是:
$$
\mathrm{H}(X)=\sum_{i} \mathrm{P}\left(x_{i}\right) \mathrm{I}\left(x_{i}\right)=-\sum_{i} \mathrm{P}\left(x_{i}\right) \log _{2} \mathrm{P}\left(x_{i}\right)
$$
信息增益:

信息增益指期望信息的有效减少量。例如决策树,在一个分支上,选择一个属性进行划分,得到的信息增益越大证明划分结果不确定性越小,纯度越高。
$$
\operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} E n t\left(D^{v}\right)
$$
然而信息增益趋向于选择分类更加细致的属性(分类越多,每一类的纯度也会越大),为了克服这个毛病,引入了信息增益率:
$$
g_{R}(D, A)=\frac{g(D, A)}{H_{A}(D)}
$$
其中:
$$
H_{A}(D)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \log _{2} \frac{\left|D_{i}\right|}{|D|}
$$
信息增益率趋向于选择分类少的属性。(分类多,分母大)

基尼指数:

基尼指数比较直观,他反映了连续抽取两个样本,他们不一样的概率。因此越小表明纯度越纯。
$$
\operatorname{Gini}(\mathrm{p})=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2}
$$
决策树缺失属性的处理情况:

  1. 当属性缺失的情况下,选择最优的属性划分:可以修改信息增益函数,加上无缺失样本所占比例,无缺失样本中第k类所占比例,以及无缺失样本中某个属性所占比例等修正,得到划分的标准
  2. 当选定划分属性时,该属性缺失:将这些样本按照不同的概率,加入到所有的分支中