开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 机器学习：决策树之信息熵、信息增益、信息增益率、基尼指数分析 -> 正文阅读

[数据结构与算法]机器学习：决策树之信息熵、信息增益、信息增益率、基尼指数分析

1.信息熵

1.1 信息理论

从信息的完整性描述：当系统的有序状态一致时，数据越集中的地方熵值越小，数据越分散的地方熵值越大。
从信息的有序性描述：当数据量一致时，系统越有序，熵值越低；系统越混乱或者分散，熵值越高。

“信息熵” (information entropy)是度量样本集合纯度最常用的一种指标。

1.2 信息熵理解

信息熵是一个变量包含信息多少的度量方式
信息熵的值越大，则认为该变量包含的信息量就大
信息熵越大，表示包含的信息种类就越多，信息量就越大，信息越混乱分散，纯度就越低
信息熵只和包含的信息种类、出现的概率有关，与信息总数量无关

例如：

1、特征 α：ABCDEFGH
2、特征 β：AAAABBCD
特征 α 包含了 8 种信息，特征 β 包含了 4 种信息，虽然信息长度一样，但是包含的信息量则不同。我们可以说，特征 α 的信息熵大于特征 β 的信息熵。

1.3 信息熵的计算

1.3.1 变量信息熵通常用以下公式计算：
$Ent(x)=-\sum_{i=1}^nP(x_i)\log_2P(x_i)$

P(x_i) 表示某一个信息出现的概率
H(x) 表示信息的信息熵值

1.3.2 特征 α：ABCDEFGH的计算过程：A、B、C、D、E、F、G、H出现的概率是1/8
$Ent(\alpha)=-(\frac{1}{8}×\log_2\frac{1}{8})×8=3$
1.3.3 特征 β：AAAABBCD 的计算过程：
A出现的概率是：1/2
B出现的概率是：1/4
C、D出现的概率是：1/8

$Ent(\beta)=-[\frac{1}{2}×\log_2\frac{1}{2}+\frac{1}{4}×\log_2\frac{1}{4}+(\frac{1}{8}×\log_2\frac{1}{8})×2]=1.75$

2.信息增益

2.1 概念

信息增益：以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。
通俗的讲：

熵可以指的是某个信息的信息熵
条件熵指的是在某种条件下信息熵的大小
信息增益 = 信息熵 - 条件熵

2.2 信息增益计算

2.2.1 信息增益计算公式：

$\operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\operatorname{Ent}(D \mid a)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{D^{v}}{D} \operatorname{Ent}\left(D^{v}\right)$

2.2.2 信息熵计算公式：

$Ent(D^v)=-\sum_{k=1}^n\frac{C^k}{D}log\frac{C^k}{D}$

2.2.3 条件熵的计算公式为：

$Ent(D|a)=\sum_{v=1}^V\frac{D^v}{D}Ent(D^v)=-\sum_{v=1}^V\frac{D^v}{D}\sum_{k=1}^n\frac{C^{kv}}{D^v}log\frac{C^{kv}}{D^v}$
其中：

D^v表示a属性中第v个分支节点包含的样本数
D^kv表示a属性中第v个分支节点包含的样本数中，第k个类别下包含的样本数

2.2.4 案例分析：

	如下图，第一列为论坛号码，第二列为性别，第三列为活跃度，最后一列用户是否流失。

我们要解决一个问题：性别和活跃度两个特征，哪个对用户流失影响更大？

在这里插入图片描述

2.2.4.1 计算is_lost类别信息熵

a、0出现的概率是10/15
b、1出现的概率是5/15
$Ent(D)=-\frac{10}{15}\log_2\frac{10}{15}-\frac{5}{15}\log_2\frac{5}{15}=0.9182$

2.2.4.2 性别信息增益

在这里插入图片描述

2.2.4.3 计算性别属性的信息熵

$Ent(D^男)=-\frac{5}{8}×\log_2\frac{5}{8}-\frac{3}{8}×\log_2\frac{3}{8}=0.9543$
$Ent(D^女)=-\frac{5}{7}×\log_2\frac{5}{7}-\frac{2}{7}×\log_2\frac{2}{7}=0.8631$

2.2.4.4 计算性别的信息增益(a=“性别”)

$\operatorname{Gain}(D｜_{性别})=Ent(D)-Ent(D|a)$
$\operatorname{Gain}(D|_{性别})=Ent(D)-\frac{8}{15}Ent(D^男)-\frac{7}{15}Ent(D^女)$
$\operatorname{Gain}(D|_{性别})=0.9182-\frac{8}{15}×0.9543-\frac{7}{15}×0.8631=0.0064$

2.2.4.5 活跃度信息增益

在这里插入图片描述
is_lost类别信息熵上边已经计算出为：0.9182

2.2.4.6 计算活跃度属性信息熵

$Ent(D^高)=-1×\log_21=0$
$Ent(D^中)=-\frac{4}{5}×\log_2\frac{4}{5}-\frac{1}{5}×\log_2\frac{1}{5}=0.7219$
$Ent(D^低)=-1×\log_21=0$

2.2.4.7 计算活跃度信息增益

$\operatorname{Gain}(D｜_{活跃度})=Ent(D)-\frac{6}{15}Ent(D^高)-\frac{5}{15}Ent(D^中)-\frac{4}{15}Ent(D^低)$
$\operatorname{Gain}(D｜_{活跃度})=0.9182-\frac{5}{15}×0.7219=0.6776$
根据以上分析得出：活跃度的信息增益比性别的信息增益大，最直接就是活跃度对客户流失的影响比较大。在做特征选择或者用户数据分析的时候，应该重点关注活跃度这个指标。

3.信息增益率

3.1 定义

鉴于信息增益的不足，我们希望对信息增益的计算做出一些调整，即：当特征值种类较多时，大幅度降低其重要性。调整后的信息增益，我们叫做信息增益率。

增益率：增益率是用前面的信息增益Gain(D, a)和属性a对应的"固有值"(intrinsic value)的比值来共同定义的。
$Gain_Ratio ? ( D ∣ a ) = Gain ? ( D , a ) I V ( a ) \operatorname{Gain\_Ratio}(D| a)=\frac{\operatorname{Gain}(D, a)}{I V(a)}$
$V(a)=-\sum_{v=1}^{V} \frac{D^{v}}{D} \log \frac{D^{v}}{D}$

Gain_Ratio 表示信息增益率
IV 表示特征的信息熵
特征的信息增益 ? 特征的信息熵

a. 如果某个特征的特征值种类较多，则其信息熵值就越大。即：特征值种类越多，除以的系数就越大。
b. 如果某个特征的特征值种类较小，则其信息熵值就越小。即：特征值种类越小，除以的系数就越小。

依旧使用上面的案例进行分析：

3.1.2 计算属性信息熵

gender属性信息熵：
$-\frac{8}{15}×\log_2{\frac{8}{15}}-\frac{7}{15}×\log_2{\frac{7}{15}}=0.9968$
act_info属性信息熵：
$IV(act\_info)= -\frac{6}{15}×\log_2{\frac{6}{15}}-\frac{5}{15}×\log_2{\frac{5}{15}}-\frac{4}{15}×\log_2{\frac{4}{15}}=1.5656$

上边计算得出：

gender的信息增益为：
$\operatorname{Gain}(D｜_{gender})=0.0064$

act_info的信息增益为：
$\operatorname{Gain}(D｜_{act\_info})=0.6776$
因此：

gender的信息增益率为：
$Gain_Ratio ? ( D ∣ g e n d e r ) = 0.0064 / 0.9968 = 0.0064 \operatorname{Gain\_Ratio}(D|_{gender})=0.0064/0.9968=0.0064$
act_info的信息增益率为：
$Gain_Ratio ? ( D ∣ a c t _ i n f o ) = 0.6776 / 1.5656 = 0.4328 \operatorname{Gain\_Ratio}(D|_{act\_info})=0.6776/1.5656=0.4328$

根据以上计算结果：gender特征的信息增益率明显小于act_info的信息增益率，因此我们优先选用act_info做为特征分裂点。

为什么使用C4.5比较好

1.用信息增益率来选择属性

克服了用信息增益来选择属性时偏向选择值多的属性的不足。

2.采用了一种后剪枝方法
避免树的高度无节制的增长，避免过度拟合数据
3.对于缺失值的处理：
在某些情况下，可供使用的数据可能缺少某些属性的值。假如〈x，c(x)〉是样本集S中的一个训练实例，但是其属性A的值A(x)未知。处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值；另外一种更复杂的策略是为A的每个可能值赋予一个概率。例如，给定一个布尔属性A，如果结点n包含6个已知A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支。
C4.5就是使用这种方法处理缺少的属性值。

4.基尼值和基尼指数

4.1 概念

CART 决策树 [Breiman et al., 1984] 使用"基尼指数" (Gini index)来选择划分属性.

CART 是Classification and Regression Tree的简称，这是一种著名的决策树学习算法,分类和回归任务都可用

基尼值Gini（D）：从数据集D中随机抽取两个样本，其类别标记不一致的概率。故，Gini（D）值越小，数据集D的纯度越高。

数据集 D 的纯度可用基尼值来度量:
$\operatorname{Gini}(D)=\sum_{k=1}^{|y|} \sum_{k \neq k} p_{k} p_{k^{\prime}}=1-\sum_{k=1}^{|y|} p_{k}^{2}$

p_k=C^k/D，D为样本的所有数量，C^k为第k类样本的数量。

基尼指数Gini_index（D,a）：
$Gini_index ? ( D , a ) = ∑ v = 1 V D v D Gini ? ( D v ) \operatorname{Gini\_index}(D, a)=\sum_{v=1}^{V} \frac{D^{v}}{D} \operatorname{Gini}\left(D^{v}\right)$

4.2 案例

请根据下图列表，按照基尼指数的划分依据，做出决策树。

序号	是否有房	婚姻状况	年收入(K)	是否拖欠贷款
1	yes	single	125	no
2	no	married	100	no
3	no	single	70	no
4	yes	married	120	no
5	no	divorced	95	yes
6	no	married	60	no
7	yes	divorced	220	no
8	no	single	85	yes
9	no	married	75	no
10	no	Single	90	Yes

注意：三个特征中，是否有房包含2个值、婚姻状况包含3个值、年收入包含多个值。其计算方法略有不同，注意区分。

4.2.1 是否有房（二值特征）

计算过程如下：根据是否有房将目标值划分为两部分：

计算有房子的基尼值： 有房子有 1、4、7 共计三个样本，对应：3个no、0个yes
$i(\text {是否有房，yes })=1-\left(\frac{0}{3}\right)^{2}-\left(\frac{3}{3}\right)^{2}=0$
计算无房子的基尼值：无房子有 2、3、5、6、8、9、10 共七个样本，对应：4个no、3个yes
$\operatorname{Gini}(\text {是否有房，no })=1-\left(\frac{3}{7}\right)^{2}-\left(\frac{4}{7}\right)^{2}=0.4898$
计算基尼指数：第一部分样本数量占了总样本的 3/10、第二部分样本数量占了总样本的 7/10：
$\operatorname{Gini_{-}} i n \operatorname{dex}(D, \text { 是否有房 })=\frac{7}{10} * 0.4898+\frac{3}{10} * 0=0.343$

4.2.2 婚姻状况（三值特征）

计算 {married} 和 {single,divorced} 情况下的基尼指数：
- 结婚的基尼值，有 2、4、6、9 共 4 个样本，并且对应目标值全部为 no：
$Gini_index ? ( D , ?married? ) = 0 \operatorname{Gini\_index}(D, \text { {married} })=0$
- 不结婚的基尼值，有 1、3、5、7、8、10 共 6 个样本，并且对应 3 个 no，3 个 yes：
$Gini_index ? ( D , ?single,divorced? ) = 1 ? ( 3 6 ) 2 ? ( 3 6 ) 2 = 0.5 \operatorname{Gini\_index}(D, \text { {single,divorced} })=1-\left(\frac{3}{6}\right)^{2}-\left(\frac{3}{6}\right)^{2}=0.5$
- 以 married 作为分裂点的基尼指数：
$Gini_index ? ( D , ?married? ) = 4 10 ? 0 + 6 10 ? [ 1 ? ( 3 6 ) 2 ? ( 3 6 ) 2 ] = 0.3 \operatorname{Gini\_index}(D, \text { married })=\frac{4}{10} * 0+\frac{6}{10} *\left[1-\left(\frac{3}{6}\right)^{2}-\left(\frac{3}{6}\right)^{2}\right]=0.3$
计算 {single} | {married,divorced} 情况下的基尼指数
$Gini_index ? ( D , ?婚姻状况? ) = 4 10 ? 0.5 + 6 10 ? [ 1 ? ( 1 6 ) 2 ? ( 5 6 ) 2 ] = 0.367 \operatorname{Gini\_index}(D, \text { 婚姻状况 })=\frac{4}{10} * 0.5+\frac{6}{10} *\left[1-\left(\frac{1}{6}\right)^{2}-\left(\frac{5}{6}\right)^{2}\right]=0.367$
计算 {divorced} | {single,married} 情况下基尼指数
$Gini_index ? ( D , ?婚姻状况? ) = 2 10 ? 0.5 + 8 10 ? [ 1 ? ( 2 8 ) 2 ? ( 6 8 ) 2 ] = 0.4 \operatorname{Gini\_index}(D, \text { 婚姻状况 })=\frac{2}{10} * 0.5+\frac{8}{10} *\left[1-\left(\frac{2}{8}\right)^{2}-\left(\frac{6}{8}\right)^{2}\right]=0.4$
最终：该特征的基尼值为 0.3，并且预选分裂点为：{married} 和 {single,divorced}

4.2.3 年收入（多值特征）

先将数值型属性升序排列，以相邻中间值作为待确定分裂点：

待确定的分裂点为：65、72.5、80、87.7、92.5、97.5、110、122.5、172.5
以年收入 65 将样本分为两部分，计算基尼指数
$\text { 节点为 } 65 \text { 时 }:\{\text { 年收入 }\}=\frac{1}{10} * 0-\frac{9}{10} *\left[1-\left(\frac{6}{9}\right)^{2}-\left(\frac{3}{9}\right)^{2}\right]=0.4$
以此类推计算所有分割点的基尼指数，我们发现最小的基尼指数为 0.3。