title: 机器学习笔记(五)决策树与RF

机器学习笔记(五)决策树

date: 2015-08-09 10:18:55

MachineLearning

1. 基本概念

• 熵(entropy)：熵是信息学中的概念，主要用来衡量随机变量不确定程度。设X是一个取有限个值的离散随机变量，其概率分布为$P(X = x_i) = p_i,i = 1,2,...,n$，那么随机变量X的信息熵则定义为：$H(X) = -\sum_{i = 1}^n{p_ilogp_i}$

• 条件熵：设有随机变量（X，），其联合分布概率为$P(X = x_i,Y = y_j) = p_{ij}, i = 1,2,...,n; j = 1,2,...,m$
  条件熵H(X|Y)表示在已知随机变量X的条件下，随机变量Y的不确定程度。条件熵H(X|Y)定义为X给定条件下，随机变量Y的条件概率分布的熵对X的数学期望：$H(Y|X) = \sum_{i = 1}^n{p_iH(Y|X = x_i)}$，这里$p_i = p(X = x_i),i = 1,2,..,n$

• 信息增益：(我们先计算训练集的熵，然后计算选定一个特征之后的条件熵，用两者的差值表示熵的减少程度，减少的越多，选的特征越好)

  信息增益表示已知特征X的信息而使得类Y的不确定减少的程度。信息增益为：特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵与给定特征X条件下的经验条件熵H(D|A)的之差，即g(D,A = H(D) - H(D|A)。

  • 信息增益比:信息增益偏好于那些取值较多的特征。信息增益比可以对这一问题进行校正，信息增益比的定义为：$g_R(D,A) = \frac{g(D,A)}{H_A(D)}$，其中，$H_A(D) = -\sum_{i = 1}^n\frac{|D_i|}{|D|}log_2{\frac{|D_i|}{|D|}}$，这里需要注意条件熵`$H(D|A)$和熵$H_A(D) = -\sum_{i = 1}^n\frac{|D_i|}{|D|}log_2{\frac{|D_i|}{|D|}}$的区别。

2. 决策树生成

• ID3算法:分类算法、信息增益
• C4.5算法：分类算法、信息增益比

3. 决策树剪枝

剪枝是决策树学习算法对付过拟合问题的主要手段（决策树很容易产生过拟合问题）。分为“预剪枝”和“后剪枝”两种方法。

预剪枝：预剪枝指的是在决策树生成过程中，对每个结点在进行划分前先进行估计，若当前结点的划分不能带来泛化性能的提升，那么停止划分并将当前结点标记为叶结点。这里可以使用交叉验证的方式，用测试集来计算泛化性能。

后剪枝：后剪枝指的是决策树完全生长，然后自底而上的考察非叶子结点，若将该结点对应的子树替换成叶子结点能带来泛化性能的提升，则将该结点对应的子树替换成叶子结点。

4. CART算法

4.1 回归树的生成

回归树的属性选择采用的是均方误差。
回归树的切分属性选择的方法是：对特征和特征的属性的取值进行遍历，对切分变量和相应的切分点，数据集被切分成两个区域，计算此次划分的均方误差，选取其中最小均方误差所对应的属性和相应的取值作为当前切分点。

4.2 分类树的生成

分类树采用基尼指数，选取基尼指数最小的属性及属性的取值作为划分，基尼指数的定义为：
分类问题中，假设有K个类，样本点属于第K个类的概率为$p_k$，则概率分布的基尼指数定义为
$Gini(p) = \sum_{k = 1}^{k = K}{p_k(1 - p_k)} = 1 - \sum_{k = 1}^K{p_k^2}$，基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此，基尼指数越小，数据集的纯度越高。

分类树算法的属性选择：
对某个特征A的某个取值a，将数据集合D划分成$D1$和$D2$两个集合，计算该特征，该取值下的基尼指数，计算公式为：
$gini(D,A = a) = \dfrac{D1}{D}gini(D1) + \dfrac{D2}{D}gini(D2)$。选取gini指数最小的划分属性和划分点，作为当前的划分点。

5. 随机森林

1. 首先在样本的集合上进行有放回的抽样，假设有T棵树，那么采样得到T个样本的集合；
2. 对于每个树，每个结点，在属性集合上进行无放回的抽样，从抽样集合中选择最优属性进行划分；
3. 每棵树进行完全分裂，不剪枝；
4. 预测：通常情况下，分类任务时采用投票法、回归任务时采用简单平均法；