统计学习方法（五）：决策树和随机森林

决策树：判别模型
问题描述：假设要对一批样本分K类。其中这些样本又有A个特征。如何生成一个树形结构，按照特征一层一层往下分。

统计学习方法（五）：决策树和随机森林

决策树生成思路：有A个特征可供分类，但是先选哪个特征作为分类标准呢？决策树为了解决这个问题，首先会判断该特征的对样本的区分能力，比如在男宿舍这样一个条件下判断谁有ipad，如果用性别作为一个特征来判断分类，收益很小；如果我们用生活费多少来判断，那么对这个分类就有很大的帮助。决策树这里用信息增益来判断特征Ai对分类的影响大小，先选择对分类区分度大的特征，在用其他特征依次往下分。
信息增益：
- 熵：混乱程度的度量
  一个随机变量的熵可以由其各种取值的概率定义为： $H(X)=-\sum_{i=1}^{n} p_{i} \log p_{i}$
- 信息增益：定义特征 A 对训练数据集 D 的信息增益 g (D,A)，定义为集合 D 的经验熵 H(D) 与特征 A 给定条件下 D 的经验条件嫡 $H(D \mid A)$ 之差，即
  $g(D, A)=H(D)-H(D \mid A)$
  根据特征 $A$ 的取值将 D 划分为 $n$ 个子集 $D_{1}, D_{2}, \cdots, D_{n}$ ，
  $H(D \mid A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)$
- 信息增益比： $g_{R}(D, A)=\frac{g(D, A)}{H_{A}(D)}$ ，分母表示以特征A代替类别在数据集上计算熵。
决策树生成算法：
- ID3算法：以信息增益为特征判断标准
- C4.5：以信息增益比为特征判断标准
决策树剪枝算法：
- 剪枝原因：分类分的太细，对训练数据拟合很好，但是对未知数据的分类效果不好，也就是过拟合。考虑了树的复杂度因素。
- 先剪枝（也就是在生成过程中剪枝）：
  - 设定决策树高度，到高度了停止继续分
  - 设定叶节点包含的最小样本数
  - 计算每增一个节点对系统带来的性能，设定阈值予以停止
- 后剪枝（先生成完整的树再剪枝）：
  - 计算剪枝前后的损失函数，比较观察是否剪枝。
  - 还有多种剪枝算法。
随机森林：训练集产生多个决策树，输入预测数据后，每个决策树上都产生一个分类。对分类问题多数表决，对回归问题，求平均值。
- 如何产生多个决策树，也就是随机的含义：
  - 训练时，也就是生成决策树时，使用数据的N%（每次都是N%，但是具体数据不一样，可重复取样单个样本。
  - 生成决策树时，可以多次选择不同的特征组作为生成树的条件。

统计学习方法（五）：决策树和随机森林

相关推荐