【机器学习笔记】决策树

下图来自互联网

决策树（decision tree）是一类常见的机器学习算法。

记录ID	年龄	收入层次	学生	信用等级	是否购买电脑
1	青少年	高	否	一般	否
2	青少年	高	否	良好	否
3	中年	高	否	一般	是
4	老年	中	否	一般	是
5	老年	低	是	一般	是
6	老年	低	是	良好	否
7	中年	低	是	良好	是
8	青少年	中	否	一般	否
9	青少年	低	是	一般	是
10	老年	中	是	一般	是
11	青少年	中	是	良好	是
12	中年	中	否	良好	是
13	中年	高	是	一般	是
14	老年	中	否	良好	否

—————————————————————–

根据已知数据预测再来的人会不会买电脑
决策树把所有的特征按照一定层级来排，变成树状。


按照什么属性分类？
决策树学习的关键是如何选择最优划分属性，一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本可能属于同一类别，既结点的“纯度”（purity）越来越高。

Information entropy（信息熵）

信息熵是度量样本集合纯度最常用的一种指标。
假定当前样本集合 D $D$ 中第 k $k$ 类样本所占比例为 pk $p_k$ ，则 D $D$的信息熵定义为

Ent(D)=−∑k=1|y|pklog2pk $$Ent(D)=-\underset{k=1}{\overset{|y|}{\sum }}{p}_{k}lo{g}_2{p}_k$$

Ent(D) $Ent(D)$ 的值越小，则 D $D$ 的纯度越高。

例子

比如我们将一个立方体A抛向空中，记落地时着地的面为f1，f1的取值为{1,2,3,4,5,6}，f1的熵

entropy(f1)=−(1/6∗log2(1/6)+…+1/6∗log2(1/6))=−1∗log2(1/6)=2.58 $$entropy(f1)=-(1/6\ast lo{g}_2(1/6)+\dots +1/6\ast lo{g}_2(1/6))=-1\ast lo{g}_2(1/6)=2.58$$

现在我们把立方体A换为正四面体B，记落地时着地的面为f2，f2的取值为{1,2,3,4}，f2的熵

entropy(1)=−（1/4∗log2(1/4)+...+1/4∗log2(1/4))=−log2(1/4)=2 $$entropy(1)=-（1/4\ast lo{g}_2(1/4)+...+1/4\ast lo{g}_2(1/4))=-lo{g}_2(1/4)=2$$

如果我们再换成一个球C，记落地时着地的面为f3，显然不管怎么扔着地都是同一个面，即f3的取值为{1}，故其熵

entropy(f3)=−1∗log2(1)=0 $$entropy(f3)=-1\ast lo{g}_2(1)=0$$

可以看到面数越多，熵值也越大，而当只有一个面的球时，熵值为0，此时表示不确定程度为0，也就是着地时向下的面是确定的。

Ent（D） $Ent（D）$值越小，不确定性低，纯度越高。

信息增益（information gain）

用信息熵分类，先算整个数据集的熵，再算给定的conditional 的熵，相减就能知道选定哪个特征能获得最多的纯度增加。
选定属性a的信息增益

Gain(D,a)=Ent(D)−∑v=1V|Dv||D|Ent(Dv) $$Gain(D,a)=Ent(D)-\underset{v=1}{\overset{V}{\sum }}\frac{|D^v|}{|D|}Ent(D^v)$$

增益率（gain ratio）

当取记录ID为特征时，可以算出增益时最大的，信息熵直接变成0.
信息增益准则对可取值数目较多的属性有所偏好，所以决策树不直接使用信息增益，而使用增益率

GainRatio(D,a)=Gain(D,a)IVa, $$GainRatio(D,a)=\frac{Gain(D,a)}{IVa},$$

其中

IV(a)=−∑v=1V|Dv||D|log2|Dv||D| $$IV(a)=-\underset{v=1}{\overset{V}{\sum }}\frac{|D^v|}{|D|}lo{g}_2\frac{|D^v|}{|D|}$$

增益率的方法偏好可取值数目少的属性，所以决策树算法用的是先找信息增益高于平均水平的属性，再从中挑选增益最高的。

基尼指数

CART决策树使用基尼指数来选择划分属性。

Gini(D)=∑k=1|y|∑k′≠kpkpk′=1−∑k=1|y|p2k $$\begin{gathered} Gini(D)=\underset{k=1}{\overset{|y|}{\sum }}\underset{k^{\prime }\ne k}{\sum }{p}_k{p}_{k^{\prime }} \\ =1-\underset{k=1}{\overset{|y|}{\sum }}{p}_k^2 \end{gathered}$$

基尼指数代表随机从数据集 D $D$ 中抽出两个样本，其类别标记不一致的概率。越小纯度越高。

剪枝处理

在决策树学习中，为了尽可能争取分类，节点划分过程不断重复，有时会造成分支过多，过拟合。可以主动去掉一些分支。

预剪支

决策树生成过程中，对每个结点划分前进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分，并将该结点标记为叶结点。
把数据集划分成训练集和验证集，通过验证集评估。

对于一个结点，先算如果是个叶结点，在验证集中的正确率，再算他划分一次后在验证集中的正确率，如果前者高于后者，停止划分标记成叶结点，否则说明划分正确。
优点：降低过拟合风险，显著减少了训练时间和测试时间
缺点：没有展开的一些分支，可能会导致欠拟合

后剪支

数据集分为训练集和验证集。
根据训练集生成完整的决策树后，从下往上考察，计算每个结点去掉与不去掉对于验证集的精度，决定是否剪除该结点。
优点：比预剪支保留了更多的分支，泛化性能好，欠拟合风险小
缺点：训练时间比未剪支和预剪支要大得多

---