随机森林与决策树

决策树

决策树学习采用的是自顶向下的递归方法, 其基本思想是以信息熵为度量构造一棵熵值 下降最快的树,到叶子节点处的熵值为零, 此时每个叶节点中的实例都属于同一类。

• 最大优点: 可以自学习。在学习的过程中,不需要使用者了解过多背景知识,只需要对训练实例进行较好的标注,就能够进行学习。
• 显然,属于有监督学习。

三种生成算法

1. ID3 --- 信息增益 最大的准则
2. C4.5 --- 信息增益比 最大的准则
3. CART
   • 回归树: 平方误差 最小 的准则
   • 分类树: 基尼系数 最小的准则

1. 信息增益 $g(D,A)$

定义: 特征A对训练数据集D的信息增益 g(D,A), 定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即: $g(D,A)=H(D) – H(D|A)$

• 显然,这即为训练数据集D和特征A的互信息。

基本记号

• 设训练数据集为D, $\vert D \vert$ 表示样本个数。
• 设有K个类 $C_k, k=1,2,...,K$ , 有: $\sum_k C_k = \vert D \vert$
• 设特征A有n个不同的取值 $\{a_1,a_2,...,a_n\}$, 根据特征A的取值将D划分为n个子集 $D_1, D_2,..., D_n$ ,有: $\sum_i \vert D_i \vert =\vert D \vert$
• 记子集 $D_i$ 中属于类 $C_k$ 的样本的集合为 $D_{ik}$

经验熵 $H(D)$

计算数据集D的经验熵:
$H(D)=-\sum_{k=1}^K {\vert C_k \vert \over\vert D \vert}{\rm{log}}{\vert C_k \vert \over\vert D \vert}$

其中, $H(X)=-\sum p(x){\rm{ln}}p(x)$

经验条件熵 $H(D|A)$

$H(D|A)=\sum_{i=1}^n{\vert D_i \vert \over\vert D \vert}H(D_i)=-\sum_{i=1}^n{\vert D_i \vert \over\vert D \vert}\sum_{k=1}^K {\vert D_{ik} \vert \over\vert D_i \vert}{\rm{log}}{\vert D_{ik} \vert \over\vert D_i \vert}$

遍历所有特征,对于特征A:

• 计算特征A对数据集D的经验条件熵H(D|A)
• 计算特征A的信息增益:g(D,A)=H(D) – H(D|A)
• 选择信息增益最大的特征作为当前的分裂特征

2. 信息增益比

$g_R(D,A)={g(D,A)\over H_A(D)}$

3. 基尼系数

${\rm{Gini}}(p)=\sum_{k=1}^K p_k(1-p_k)=1-\sum_{k=1}^K p_k^2=1-\sum_{k=1}^K \big( {\vert C_k \vert \over\vert D \vert}\big)^2$

对于二分类问题:

${\rm{Gini}}(p)=2p(1-p)$

对于二分类问题, 在特征 A 的条件下,

${\rm{Gini}}(D|A)={\vert D_1 \vert \over\vert D \vert}{\rm{Gini}}(D_1)+{\vert D_2 \vert \over\vert D \vert}{\rm{Gini}}(D_2)$

Bagging

bagging: bootstrap aggregation

bootstrap

Bootstraping的名称来自成语“pull up by your own bootstraps”,意思是依靠你自己的资源,称为自助法,它是一种有放回的抽样方法.

"拔靴法": 从手上有限的资料, 产生不同的副本, 来模拟不一样的资料.

1. 从已知大小为 $N$ 的数据集 ${\scr{D}}$ 中, 进行 $t=1,2,...,T$ 的过程:
   • 进行有放回的采样, 得到 $N'$ 大小的数据集 ${\scr{D}_t}$ ,
   • 从 ${\scr{A\{D\}}}$ 中建立分类器 $g_t$ (ID3、C4.5、CART、SVM、Logistic回归等)
2. 重复上述步骤, 得到 $m$ 个分类器, $G={\rm{Uniform}}(g_t)$

作用: 通过投票/平均, 降低变化variance 与决策树恰好相反, 决策树的作用, 是使variance变大, 对数据敏感.

决策树的优缺点

• 优点: 决策树对训练属于有很好的分类能力,
• 缺点: 但对未知的测试数据未必有好的分类能力,泛化 能力弱,即可能发生过拟合现象。
  • 剪枝
  • 随机森林

随机森林

随机森林能够解决, 决策树的过拟合问题. 随机森林用训练集生成多个(非常深的)决策树.在预测时, 每个树的都会预测一个结果, 每个结果加权表决, 来避免过拟合. 例如, 如果你训练了3个树, 其中有2个树的结果是A, 1个数的结果是B, 那么最终结果会是A.

Random Forest classifiers work around that limitation by creating a whole bunch of decision trees (hence "forest") — each trained on random subsets of training samples (drawn with replacement) and features (drawn without replacement) — and have the decision trees work together to make a more accurate classification.

1. 加入随机性: 训练集的子空间(有放回采样)

• Bagging: 不太稳定, 变化较大, g(t) 通过投票/平均, 来 reduce variance
• CART: 对不同资料相对敏感, variance large, especially fully-grown tree

2. 加入随机性: 采样特征子空间(无放回采样)

从100维选10维, 即做了低维度的投影. P是投影矩阵, 每行row是natural basis代表平常单位的各自的方向.

3. 加入随机性: 加入新特征(合并, 低维的投影)

反馈与建议

• 微博：@Girl_AI

参考文献

• 统计学习方法
• 机器学习技法