决策树

基本流程

决策树是一种常见的机器学习方法，采取的是分而治之的策略。其中每个非叶节点对应于一个属性测试，而叶子节点则对应于决策结果，也就是类别。

在生成决策树的过程中，遇到以下三种情况时停止递归：

决定决策树学习的关键在于如何选择最优的划分属性，保证每个分支节点所包含的样本尽量属于同一个类别，即节点的纯度越高。

信息熵是度量样本集合纯度的常用指标。假定当前样本集合D中第x类样本所占比例为p(x)，那么D的信息熵就是：

信息熵的取值范围为[0, log|y|]，y为类别数目

那么如何去判断某个属性对于样本集信息熵的提升呢，这里就提到了信息增益：

利用总的熵减去某个分类标准对应的熵，往往我们也可以给某个分支节点赋予权重|Dv|/|D|，Dv就是该分类标准下第v个节点对应的样本

怎么去理解呢？这里表述的是：原来的总熵为info(S)，在某个划分条件下熵变为了infos(S)，又由于熵是不确定的意思，那么差值越大，就意味着这个划分选择越好。

因为在某些情况下，选择信息增益大的属性，可能会导致泛化能力减弱，比如“编号”属性可能产生n个分支，使得分支节点达到最大，但在这种情况无法进行进一步的划分。

所以著名的C4.5决策树算法不直接使用信息增益，还是使用增益率：

Gain_ration(D, a)= Gain(D, a)/IV(a)

其中IV(a)为：

因为这是属性a的固有值，往往属性a的可取值树木越多，那么改值越大。由于该算法可能会倾向于选择可取值树木少的属性，所以它是这样操作的：先根据信息增益选择出高于平均水平的属性，再从其中选出增益率最高的。

先来看看基尼指数的公式：

从公式可以看出，基尼指数反映了随机从样本中抽取两个样本，两个样本一致的概率，该概率越小意味着样本集的纯度越高。

则对于属性a的基尼指数则是：

剪枝处理的目的是提高决策树的泛化能力，以应对算法出现的过拟合。

那么如何去评判泛化能力呢？我们可以将样本集分为两类：样本集和检验集，通过计算检验集的准确率来决定决策树的泛化性能

剪枝分为两种：预剪枝和后剪枝

预剪枝是在决策树生成过程中，对每个节点的划分前进行估计，估计其划分是否可以可以带来决策树性能的提升。若不能，则停止划分，并将当前节点标记为叶节点。

后剪枝是生成完成的决策树之后，自底向上对节点进行考察，若替换为叶节点后泛化能力有所提升，则进行替换

对于连续属性而言，由于可取值数目是无限的，因此我们需要采用连续属性离散化的处理思路。最简单的方法就是采用二分法对属性进行处理。

给定了样本集D和连续属性a，假设a在D上出现了n个取值，对这些取值进行排序：{a1,a2,...,an}，我们可以得到一个划分点集合，里面有n个元素：

Ta = {a(i)+a(i+1)/2 | 1<=i<=n-1}

对这一系列划分点进行考察，计算各个划分点的信息增益，选择信息增益最大对应的划分点。

我们为每个样本取一个权重wx

将信息增益的计算式更新为以下：

若样本在属性的取值已知，则将该样本划入与其取值对应的子节点，并保持权重wx；若属性取值未知，则同时划入所有子节点，并更新权重为~r_v*w_x

如果单纯地使用上面提到的决策树方法，对于多维变量而言，分类边界的每一段都是和属性对应的坐标轴平行的。

但这样会带来一个问题就是：当学习任务的分类边界比较复杂时，划分的时间成本过高。因此我们考虑多变量决策树，而不是单一的属性，每个叶节点此时就是一个线性的分类器，例如对于西瓜数据集：

其中一个节点，可以变成：-0.365密度+-0.366含糖度<-0.158?