一文深刻理解决策树(系列一)

1 初始决策树

决策树思想的来源非常朴素，程序设计中的条件分支结构就是if-else结构，最早的决策树就是利用这类结构分割数据的一种分类学习方法

决策树：是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果，本质是一颗由多个判断节点组成的树。

怎么理解这句话？通过一个对话例子

想一想这个女生为什么把年龄放在最上面判断！！！！！！！！！

上面案例是女生通过定性的主观意识，把年龄放到最上面，那么如果需要对这一过程进行量化，该如何处理呢？

此时需要用到信息论中的知识：信息熵，信息增益

2 熵

2.1 概念

物理学上，熵 Entropy 是“混乱”程度的量度。

系统越有序，熵值越低；系统越混乱或者分散，熵值越高。

1948年香农提出了信息熵（Entropy）的概念。

• 信息理论：

1、从信息的完整性上进行的描述:

当系统的有序状态一致时，数据越集中的地方熵值越小，数据越分散的地方熵值越大。

2、从信息的有序性上进行的描述:

当数据量一致时，系统越有序，熵值越低；系统越混乱或者分散，熵值越高。

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

假定当前样本集合 D 中第 k 类样本所占的比例为 $p_k$pk​ (k = 1, 2,. . . , |y|) ，

$p_k=\frac{C^k}{D}$pk​=DCk​, D为样本的所有数量，$C^k$Ck为第k类样本的数量。

则 D的信息熵定义为(（log是以2为底，lg是以10为底）:

其中：Ent(D) 的值越小，则 D 的纯度越高.

2.2 案例

课堂案例：
假设我们没有看世界杯的比赛，但是想知道哪支球队会是冠军，
我们只能猜测某支球队是或不是冠军，然后观众用对或不对来回答，
我们想要猜测次数尽可能少，你会用什么方法？

答案：
二分法：
假如有 16 支球队，分别编号，先问是否在 1-8 之间，如果是就继续问是否在 1-4 之间，
以此类推，直到最后判断出冠军球队是哪支。
如果球队数量是 16，我们需要问 4 次来得到最后的答案。那么世界冠军这条消息的信息熵就是 4。

那么信息熵等于4，是如何进行计算的呢？
Ent(D) = -（p1 * logp1 + p2 * logp2 + ... + p16 * logp16），
其中 p1, ..., p16 分别是这 16 支球队夺冠的概率。
当每支球队夺冠概率相等都是 1/16 的时：Ent(D) = -（16 * 1/16 * log1/16） = 4
每个事件概率相同时，熵最大，这件事越不确定。

随堂练习：
篮球比赛里，有4个球队 {A,B,C,D} ，获胜概率分别为{1/2, 1/4, 1/8, 1/8}
求Ent(D)

答案：

3 决策树的划分依据一----信息增益

3.1 概念

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

信息增益 = entroy(前) - entroy(后)

注：信息增益表示得知特征X的信息而使得类Y的信息熵减少的程度

• 定义与公式

假定离散属性a有 V 个可能的取值:

假设离散属性性别有2（男，女）个可能的取值

若使用a来对样本集 D 进行划分，则会产生 V 个分支结点,

其中第v个分支结点包含了 D 中所有在属性a上取值为$a^v$av的样本，记为$D^v$Dv. 我们可根据前面给出的信息熵公式计算出$D^v$Dv的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重$\frac{|D^v|}{|D|}$∣D∣∣Dv∣​

即样本数越多的分支结点的影响越大，于是可计算出用属性a对样本集 D 进行划分所获得的"信息增益" (information gain)

其中：

特征a对训练数据集D的信息增益Gain(D,a),定义为**集合D的信息熵Ent(D)与给定特征a条件下D的信息条件熵$Ent(D|a)$Ent(D∣a)**之差，即公式为：

公式的详细解释：

信息熵的计算：

条件熵的计算：

其中：

$D^v$Dv 表示a属性中第v个分支节点包含的样本数

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

一般而言，信息增益越大，则意味着使用属性 a 来进行划分所获得的"纯度提升"越大。因此，我们可用信息增益来进行决策树的划分属性选择，著名的 ID3 决策树学习算法 [Quinlan， 1986] 就是以信息增益为准则来选择划分属性。

其中，ID3 名字中的 ID 是 Iterative Dichotomiser (迭代二分器)的简称

3.2 案例：

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

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

通过计算信息增益可以解决这个问题，统计上右表信息

其中Positive为正样本（已流失），Negative为负样本（未流失），下面的数值为不同划分下对应的人数。

可得到三个熵：

a.计算类别信息熵

整体熵：

b.计算性别属性的信息熵(a=“性别”)

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

b.计算活跃度属性的信息熵(a=“活跃度”)

c.计算活跃度的信息增益(a=“活跃度”)

活跃度的信息增益比性别的信息增益大，也就是说，活跃度对用户流失的影响比性别大。在做特征选择或者数据分析的时候，我们应该重点考察活跃度这个指标。

4 小结

本节中主要介绍了什么是决策树,以及决策树划分过程中的一个重要依据:熵.还有划分决策树的第一个依据:信息增益.
下一节将会为大家介绍信息增益比,基尼值等内容.