机器学习：原理简明教程05-决策树

内容纲要

参考：《统计学习方法》

一句话概括：决策树通过信息增益或者信息增益率或者Gini系数选择最佳特征，以此为根，分成左右两边，递归建立子树，然后通过一个损失函数，从叶子回溯比较剪枝前后函数值变化，决定是否剪枝，该损失函数两部分分别表示模型对训练数据的预测情况和模型自身的复杂程度，新来一个样本，即可通过从根到叶子的方法判断属于哪类。

决策树：

用于分类与回归
步骤：特征选择，决策树生成与决策树剪枝

Quinlan在 1986年提出的ID3算法1993年提出的C4.5算法
Breiman等人在1984年提出的CART算法

决策树模型与学习

决策树模型

ml_bayes_001

决策树与if-then规则

决策树的属性结构其实对应着一个规则集合：由决策树的根节点到叶节点的每条路径构成的规则组成；路径上的内部特征对应着if条件，叶节点对应着then结论。决策树和规则集合是等效的，都具有一个重要的性质：互斥且完备。也就是说任何实例都被且仅被一条路径或规则覆盖。

决策树与条件概率分布

决策树还是给定特征条件下类的条件概率分布的一种退化表示（非等效，个人理解）。该条件分布定义在特征空间的划分上，特征空间被花费为互不相交的单元，每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的每条路径对应于划分中的一个单元。给定实例的特征X，一定落入某个划分，决策树选取该划分里最大概率的类作为结果输出。如图：

ml_bayes_002

关于b图，我是这么理解的，将a图的基础上增加一个条件概率的维度P，代表在当前特征X的情况下，分类为+的后验概率。图中的方块有些地方完全没有，比如x2轴上[a2,1]这个区间，说明只要X落在这里，Y就一定是-的，同理对于[0,a1]和[0,a2]围起来的一定是+的。有些地方只有一半，比如x1轴上[a1,1]这个区间，说明决策树认为X落在这里，Y只有一半概率是+的，根据选择条件概率大的类别的原则，就认为Y是-的（因为不满足P(+)>0.5)。

决策树学习

实际上是一个递归创建树的过程：

1. 选择一个最佳分类点（信息增益、信息增益率）

2. 以最佳分类点为根，将数据分两类，然后递归建子树

最优决策树的生成是个NP问题，能实现的生成算法都是局部最优的，剪枝则是既定决策树下的全局最优。

特征选择

特征选择问题

ml_bayes_003