信息熵和决策树

熵

信息熵

H(X)就叫做随机变量X的信息熵

$$H(X) = - \displaystyle \sum_{i=1}^{m}{p_ilog_{2}{(p_i)}}$$

• 信息量: 指的是一个样本/事件所蕴含的信息, 如果一个事件的概率越大, 就认为该事件所蕴含的信息越少. 极端情况下, “太阳从东方升起”, 因为是确定事件, 所以不携带任何信息量
• 信息熵, 一个系统越有序, 信息熵就越低, 一个系统越混乱, 信息熵就越高, 所以信息熵被认为是一个系统有序程度的度量
• 信息熵就是用来描述系统信息量的不确定度
• High Entropy(高信息熵): 表示随机变量X是均匀分布的, 各种去追情况是等概率出现
• Low Entropy(低信息熵): 表示随机变量X各种取值不是等概率出现, 可能出现有的事件概率很大, 有的事件概率很小

条件熵

• 给定条件X的情况下, 随机变量Y的信息熵叫做条件熵

专业(X)	性别(Y)
数学	M
IT	M
英语	F
数学	F
数学	M
IT	M
英语	F
数学	F

$$P(X=数学) = 4/8 = 0.5$$ $$P(X=IT) = 2/8 = 0.25$$ $$P(X=英语) = 2/8 =0.25$$ $$P(Y=M) = 4/8 = 0.5$$ $$P(X=数学, Y=F) = 2/8 = 0.25$$ $$P(X=数学, Y=M) = 2/8 = 0.25$$ $$P(X=IT, Y=M) = 2/8 = 0.25$$ $$P(X=英语, Y=F) = 2/8 = 0.25$$ $$P(Y=M|X=英语) = 0/8 = 0$$ $$\begin{align}H(X) &= -[P(X=数学)log_2P(X=数学) + P(X=IT)log_2P(X=IT) + P(X=英语)log_2P(X=英语)]\\ &=-[0.5log_{2}0.5 + 0.25 log_{2}0.25 + 0.25 log_{2}0.25]\\ &=-[0.5 \cdot (-1) + 0.25 \cdot (-2) + 0.25 \cdot (-2)] = 1.5\\ \end{align}$$ $$\begin{align}H(Y) &= -[P(Y=F)log_2P(Y=F) + P(Y=M)log_2P(Y=M)]\\ &=-[0.5log_{2}0.5 + 0.5log_{2}0.5] = 1\\ \end{align}$$

• 当专业(X)为数学的时候, Y的信息熵的值为H(Y|X=数学)

专业(X)	性别(Y)
数学	M
数学	F
数学	M
数学	F

$$H(Y|X=数学) = H(Y=M|X=数学) + H(Y=F|X=数学) = -[0.5 log_{2}0.5 + 0.5 log_{2}0.5] = 1$$

同理

专业(X)	性别(Y)
IT	M
IT	M

$$H(Y|X=IT) = H(Y=M|X=IT) = -[1 log_{2}1] = 0$$

专业(X)	性别(Y)
英语	F
英语	F

$$H(Y|X=英语) = H(Y=F|X=英语) = -[1 log_{2}1 ] = 0$$

$v_j$	$P(X=v_j)$	$H(Y \mid X=v_j)$
数学	0.5	1
IT	0.25	0
英语	0.25	0

$$H(Y|X) = \displaystyle \sum_{j=1}{P(X=v_j)H(Y|X=v_j)} = 0.5*1 + 0.25*0 + 0.25*0 = 0.5$$ $$\begin{align}H(X,Y) &= -[P(X=数学,Y=F)log(P(X=数学,Y=F)) + P(X=数学,Y=M) log( P(X=数学,Y=M)) + P(X=IT,Y=M) log( P(X=IT,Y=M) ) + P(X=英语,Y=F) log( P(X=英语,Y=F) )]\\ &= -[ 0.25log_{2}0.25 + 0.25log_{2}0.25 + 0.25log_{2}0.25 + 0.25log_{2}0.25 ] \\ &= -[-0.5 - 0.5 - 0.5 - 0.5] = 2\\ \end{align}$$ $$\begin{align}H(X) &= -[P(X=数学)log( P(X=数学) ) + P(X=IT)log( P(X=IT) ) + P(X=英语) log( P(X=英语) )]\\ &=-[0.5log_{2}0.5 + 0.25log_{2}0.25 + 0.25log_{2}0.25] = -[-0.5 - 0.5 - 0.5] = 1.5\\ \end{align}$$ $$H(Y|X) = H(X,Y)−H(X) = 2 - 1.5 = 0.5$$

• 事件(X, Y)发生所包含的熵, 减去事件X单独发生的熵, 即为在事件X发生的前提下, Y发生”新”带来的熵 $$\begin{align} H(Y|X) &= \sum_{j=1}{P(X=v_j)H(Y|X=v_j) = \sum_xP(X)H(Y|X)}\\ &= \sum_xp(x)(- \sum_yp(y|x)log(p(y|x)) = -\sum_x \sum_y p(x)p(y|x)log(p(y|x))\\ &= - \sum_x \sum_y p(x, y)log(\frac {p(x, y)} {p(x)})\\ &= - \sum_x \sum_y p(x, y)log(p(x,y)) - [- \sum_x (\sum_y p(x,y))log(p(x))]\\ &= H(X,Y) - [- \sum_x p(x)log(p(x))] = H(X, Y) -H(X) \end{align}$$

决策树

• 决策树(Decision Tree)是在已知各种情况发生概率的基础上, 通过构建决策树来进行分析的一种方式, 是一种直观应用概率分析的一种图解法; 决策树是一种预测模型, 代表的是对象属性与对象值之间的映射关系; 决策树是一种树形结构, 其中每个内部节点表示一个属性的测试, 每个分支表示一个测试输出, 每个叶节点代表一种类别; 决策树是一种非常常用的有监督的分类算法
• 决策树的决策过程就是从根节点开始, 测试待分类项中对应的特征属性, 并按照其值选择输出分支, 直到叶子节点, 将叶子节点的存放类别作为决策结果
• 决策树分为两大类: 分类树和回归树, 前者用于分类标签值, 后者用于预测连续值, 常用的算法有ID3, C4.5, CART等

决策树构建过程

• 决策树算法的重点就是决策树的构造; 决策树的构造就是进行属性选择度量, 确定各个特征属性之间的拓扑结构(树结构); 构建决策树的关键步骤就是分裂属性, 分裂属性是指某个节点按照某一类特征属性的不同划分构建不同的分支, 其目标就是让各个分裂子集尽可能的纯(让一个分裂子类中待分类的项尽可能的属于同一个类别)
• 构建步骤如下:
  • 将所有的特征看成一个一个的节点;
  • 遍历每个特征的每一种分割方式, 找到最好的分割点; 将数据划分为不同的子节点, $N_1, N_2, \cdots N_m$, 计算划分后所有子节点的”纯度”信息;
  • 对第二步产生的分割, 选择出最优的特征以及最优的划分方式; 得出最终的子节点$N_1, N_2, \cdots N_m$
  • 对子节点$N_1, N_2, \cdots N_m$分别继续执行2-3步, 直到每个最终的子节点都足够”纯”

决策树特征属性类型

根据特征属性的类型不同, 在构建决策树的时候, 采用不同的方式, 具体如下:

• 属性是离散值, 而且不要求生成的是二叉决策树, 此时一个属性就是一个分支
• 属性是离散值, 而且要求生成的是二叉决策树, 此时使用属性划分的子集进行测试, 按照”属于此子集”和”不属于此子集”分成两个分支
• 属性是连续值, 可以确定一个值作为分裂点split_point, 按照> split_point和$\le$split_point生成两个分支

决策树分割属性选择

• 决策树算法是一种”贪心”算法策略, 只考虑在当前数据特征下的最好分割方式, 不能进行回溯操作
• 对于整体的数据集而言, 按照所有的特征属性进行划分操作, 对所有划分操作的结果集的”纯度”进行比较, 选择”纯度”越高的特征属性作为当前需要分割的数据集进行分割操作, 持续迭代, 直到得到最终结果. 决策树是通过”纯度”来进行分割特征属性点的

决策树量化纯度

• 决策树的构建是通过样本概率和纯度进行构建操作的, 那么进行判断数据集是否”纯”可以通过三个公式进行判断, 分别是Gini系数, 熵(Entropy), 错误率, 这三个公式值越大, 表示数据越”不纯”; 越小表示越”纯”, 这三个公式效果差不多, 一般使用熵公式 $$P(1)=7/10=0.7; 可以偿还概率$$ $$P(2)=3/10=0.3; 无法偿还概率$$

$$Gini = 1 - \sum_{i=1}^{n}{P(i)^2}, H(Entropy) = -\sum_{i=1}^{n}{P(i)log_2(P(i))}, Error = 1 - \max_{i=1}^{n}{P(i)}$$

• 当计算出各个特征属性的量化纯度值后使用信息增益度来选择出当前数据集的分割特征属性; 如果信息增益度的值越大, 表示在该特征属性上会损失的纯度越大, 那么该属性就越应该在决策树的上层, 计算公式为: $$Gain = \Delta = H(D) - H(D|A)$$
  • Gain为特征A对训练集D的信息增益, 它为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差

决策树算法的停止条件

一般情况下有两个停止条件:

• 当每个子节点只有一种类型的时候停止构建
• 当前节点中记录数小于某个阈值, 同时迭代次数达到给定值时, 停止构建过程, 此时使用$max(p(i))$作为节点的对应类型
  方式一可能会使树的节点过多, 导致过拟合等问题; 比较常用的方式是使用方式二作为停止条件

决策树算法效果评估

• 决策树的效果评估和一般的分类算法一样, 采用混淆举证来进行计算准确率, 召回率和精确率等指标
• 也可以采用叶子节点的纯度值总和来评估算法的效果, 值越小, 效果越好

决策树生成算法

建立决策树主要有三种算法

• ID3
• C4.5
• CART(Classification And Regression Tree)

ID3算法

ID3算法是决策树比较经典的一个构造算法, 内部使用信息熵以及信息增益来进行构造; 每次迭代选择信息增益最大的特征属性作为分割属性

$$H(D) = - \displaystyle \sum_{i=1}^{n}{P(i)log_2(P(i))}$$ $$Gain = \Delta = H(D) - H(D|A)$$

优点: 决策树构建速度快, 实现简单
缺点:

• 计算依赖于特征数目比较多的特征, 而属性值最多的属性不一定最优
• ID3算法不是递增算法
• ID3算法是单变量决策树, 对于特征属性之间的关系不会考虑
• 抗噪性差
• 只适合小规模数据集, 需要将数据放到内存中

C4.5算法

使用信息增益率来取代ID3算法中的信息增益, 在树的构造过程中会进行剪枝操作进行优化; 能够自动完成对连续属性的离散化处理; C4.5算法在选中分割属性的时候选择信息增益率最大的属性, 涉及到的公式为:

$$H(D) = - \displaystyle \sum_{i=1}^{n}{P(i)log_2(P(i))}$$ $$Gain = \Delta = H(D) - H(D|A)$$ $$Gain_ratio(A) = \frac{Gain(A)}{H(A)}$$

优点:

• 产生的规则容易理解
• 准确率较高
• 实现简单

缺点:

• 对数据集需要进行多次顺序扫描和排序, 效率较低
• 只适合小规模数据集, 需要将数据放到内存中

CART算法

使用基尼系数作为数据纯度的量化指标来构建决策树, 使用GINI增益作为分割属性选择的标准, 选择GINI增益最大的作为当前数据集的分割属性; 可用于分类和回归两类问题. CART构建是二叉树

$$Gini = 1 - \sum_{i=1}^{n}{P(i)^2}$$ $$Gain = \Delta = Gini(D) - Gini(D|A)$$

ID3, C4.5, CART分类算法总结

• ID3和C4.5算法均只适合在小规模数据集上使用
• ID3和C4.5算法都是单变量决策树
• 当属性值取值比较多的时候，最好考虑C4.5算法，ID3得出的效果会比较差
• 决策树分类一般情况只适合小数据量的情况(数据可以放内存)
• CART算法是三种算法中最常用的一种决策树构建算法
• 三种算法的区别仅仅只是对于当前树的评价标准不同而已，ID3使用信息增益, C4.5使用信息增益率、CART使用基尼系数
• CART算法构建的一定是二叉树，ID3和C4.5构建的不一定是二叉树

算法	支持模型	树结构	特征选择	连续值处理	缺失值处理	剪枝	特征属性多次使用
ID3	分类	多叉树	信息增益	不支持	不支持	不支持	不支持
C4.5	分类	多叉树	信息增益率	支持	支持	支持	不支持
CART	分类, 回归	二叉树	基尼系数, 均方差	支持	支持	支持	支持

决策树优化策略

• 剪枝优化, 决策树过拟合一般情况是由于节点太多导致的, 剪枝优化对决策树的正确率影响是比较大的, 也是最常用的一种优化方式
• Random Forest, 利用训练数据随机产生多个决策树, 形成一个森林, 然后使用这个森林对数据进行预测, 选取最多结果作为预测结果

决策树剪枝

• 前置剪枝: 在构建决策树过程中, 提前停止, 得到的决策树一般比较小, 实践证明这种策略无法得到比较好的结果
• 后置剪枝: 在决策树构建好之后, 然后再开始裁剪, 一般使用两种方法, 后置剪枝的主要问题是计算效率问题, 存在一定的浪费情况
  • 用单一叶子节点代替整个子树, 叶子节点的分类采用子树中最主要的分类
  • 将一个子树完全代替另外一颗子树
• 后剪枝总体思路(交叉验证):
  • 由完全树$T_0$开始, 剪枝部分节点得到$T_1$, 再次剪枝得到$T_2$……直到仅剩树根的树$T_k$
  • 在验证数据集上对这$k+1$个树进行评价, 选择最优树$T_a$(即损失函数最小的树)
• 对于给定的决策树$T_0$
  • 计算所有内部非叶子节点的剪枝系数
  • 查找最小剪枝系数的节点, 将其子节点进行删除操作, 进行剪枝得到决策树$T_k$; 如果存在多个最小剪枝系数节点, 选择包含数据项最多的节点进行了剪枝操作
  • 重复上述操作, 直到产生的剪枝决策树$T_k$只有1个节点
  • 得到决策树$T_0T_1 \cdots T_k$
  • 使用验证样本集选择最优子树$T_a$
• 使用验证集选择最优子树的标准, 可以使用原始损失函数来考虑: $$loss = \displaystyle \sum_{t=1}^{leaf}{ \frac{\vert D_t \vert}{\vert D \vert}H(t)}$$
• 叶节点越多, 决策树越复杂, 损失越大; 修正添加剪枝系数, 修改后的损失函数为: $$loss_{\alpha} = loss + \alpha * leaf$$
• 考虑根节点为r的子树, 剪枝前后的损失函数分别为loss(R)和loss(r), 当这两者相等的时候, 可以求的剪枝系数 $$loss_{\alpha}(r) = loss(r) + \alpha$$ $$loss_{\alpha}(R) = loss(R) + \alpha * R_{leaf}$$ $$\alpha = \displaystyle \frac{loss(r) - loss(R)}{R_{leaf} - 1}$$

GridSearchCV: 网格交叉验证, 主要用于模型开发阶段找出模型的最优参数的一种方式, 内部会利用交叉验证

现在对于A和B的每个参数组合都进行一次k折交叉验证, 将k折交叉验证得到的k个模型的score(model.score(x,y))均值作为当前这组参数在训练集上的模型整体效果, GridSearchCV最终认为模型整体效果最优的对应参数是最优参数

分类树和回归树的区别

• 分类树采用信息增益、信息增益率、基尼系数来评价树的效果，都是基于概率值进行判断的;而分类树的叶子节点的预测值一般为叶子节点中概率最大的类别作为当前叶子的预测值。
• 在回归树种，叶子节点的预测值一般为叶子节点中所有值的均值来作为当前叶子 节点的预测值。所以在回归树中一般采用MSE作为树的评价指标，即均方差。 $$MSE = \frac{1}{n} \sum_{i=1}^{n}{(y_i - \hat{y_i})^2}$$
• 一般情况下只使用CART算法构建回归树

使用特征树实现特征选择
因为决策树构建过程中, 每次选择的划分特征的目的/方向是让数据具有更加明显的区分能力; 也就是我们每次选择的特征其实是具有明显的区分能力的, 可以认为这些被选择的特征其实对于y的取值具有更大的影响, 所有我们可以使用决策树来实现特征选择的操作, 即选择clf.feature_importances_返回列表中, 权重比较大的特征

决策树

• 区别

  • 分类树中使用信息熵, gini系数, 错误率作为”纯度”的度量指标, 回归树中使用MSE/MAE作为树的”纯度”的度量指标
  • 分类树使用叶子节点中包含最多的那个类别作为当前叶子的预测值, 回归树中使用叶子节点中包含的所有样本的目标属性的均值作为叶子的预测值

• 决策树的构建

  • 让每次分裂数据集的时候, 让分裂之后的数据集更加的”纯”

• 决策树分裂属性选择方式

  • 基于最优划分的规则进行选择, 迭代计算特征属性上所有划分方式的”纯度”, 选择划分后更加”纯”的一种方式(信息增益, 信息增益率), 该方法只能说明在当前数据集上是最优的, 可能会存在一定的过拟合情况
  • 基于随机的划分规则: 每次划分的时候, 都是先选择一定数目的特征, 然后在这部分特征中选择出一个最优的划分特征. 因为每次选择的划分特征都是局部最优的, 相对来讲可以增加模型的鲁棒性

• 决策树的欠拟合和过拟合

  • 通过增加树的深度来缓解决策树的欠拟合问题
  • 通过限制树的复杂程度来缓解这个过拟合的问题

• 网格交叉验证(GridSearchCV)

• 决策树的效果评估