机器学习算法之决策树

"语言艺术是以善意为基础。变相的讽刺，拐弯抹角的谩骂，体现的不是机灵，而是素质问题，毕竟谁都不是傻瓜。

—— 小闫同学

1.决策树简介

科普中国：决策树(Decision Tree)是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。

决策树思想的来源非常朴素，最早的决策树就是利用程序设计中的条件分支结构(if-else)分割数据的一种分类学习方法。接下来使用简单的语言进行描述：

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

比如生活中和女朋友决策去哪旅行：

1.距离超过30公里的地方不去

2.没有美食的地方不去

3.没有拍照景点，打卡胜地的地方不去

4.没有购物的地方不去

先选择一个地点（拉萨）：距离超过30公里，不去！

再选择一个地点（衡水）：距离在30公里以内，往下进行判断；有美食（大饼卷肉、咸鸭蛋），再向下进行；没有打卡胜地，不去！

选择下一个地点（武汉）：距离在30公里以内，往下进行判断；有美食（热干面），再向下进行；有打卡胜地（武汉大学的樱花大道），再向下进行；有购物地方（光谷），那此次旅行的地方就它了！更多精彩文章请关注公众号『Pythonnote』或者『全栈技术精选』

1.1 知识点汇总

1.决策树构建的基本步骤如下：

1) 开始将所有记录看作一个节点

2) 遍历每个变量的每一种分割方式，找到最好的分割点

3) 分割成两个节点 N1 和 N2

4) 对 N1 和 N2 分别继续执行2-3步，直到每个节点足够「纯」为止。

2.决策树的变量可以有两种：

1) 数字型 (Numeric) ：变量类型是整数或浮点数。用「>=」，「>」,「<」或「<=」作为分割条件（排序后，利用已有的分割情况，可以优化分割算法的时间复杂度）。

2) 名称型 (Nominal) ：类似编程语言中的枚举类型，变量只能从有限的选项中选取，使用「=」来分割。

3.如何评估分割点的好坏？

如果一个分割点可以将当前的所有节点分为两类，使得每一类都很「纯」，也就是同一类的记录较多，那么就是一个好分割点。更多精彩文章请关注公众号『Pythonnote』或者『全栈技术精选』

构建决策树采用贪心算法，只考虑当前纯度差最大的情况作为分割点。

2.决策树分类原理

2.1 熵

物理学上，熵 Entropy 是「混乱」程度的量度。系统越有序，熵值越低；系统越混乱或者分散，熵值越高。

信息理论：

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

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

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

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

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

假如事件 A 的分类划分是（A1 ,A2,...,An），每部分发生的概率是(p1,p2,...,pn)，那信息熵定义为公式如下：（log是以2为底，lg是以10为底）

2.1.1 案例

案例1：如果一颗骰子的六个面都是1 ，投掷它不会给你带来任何新信息，因为你知道它的结果肯定是1，它的信息熵为？

代码语言：javascript复制

 - log(1) = 0

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

代码语言：javascript复制

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

如果有32个球队，准确的信息量应该是：
H = -（p1 * logp1   p2 * logp2   ...   p32 * logp32），
其中 p1, ..., p32 分别是这 32 支球队夺冠的概率。
当每支球队夺冠概率相等都是 1/32 的时：H = -（32 * 1/32 * log1/32） = 5
每个事件概率相同时，熵最大，这件事越不确定。

案例3：篮球比赛里，有4个球队 { A,B,C,D} ，获胜概率分别为{1/2, 1/4, 1/8, 1/8}，求H(X)

代码语言：javascript复制

H(X) = 12log(2) 14log(4) 18log(8) 18log(8)=(12 12 38 38)log(2)=74bits
tips:
    以2为底的对数，记做lb,单位bit
    以e为底的对数，记做ln,单位nat

2.2 决策树的划分依据

2.2.1 信息增益

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

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

特征 A 对训练数据集 D 的信息增益 g(D,A) ，定义为集合 D 的信息熵 H(D) 与特征 A 给定条件下 D 的信息条件熵 H(D|A) 之差，即公式为：

公式的详细解释：

注：信息增益表示得知特征 X 的信息而使得类 Y 的信息熵减少的程度更多精彩文章请关注公众号『Pythonnote』或者『全栈技术精选』

2.2.2 信息增益率

增益率：增益比率度量是用增益度量 Gain(S，A) 和所分离信息度量 SplitInformation的比值来共同定义的。

2.2.3 基尼值和基尼指数

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

基尼指数 Gini_index(D)：一般，选择使划分后基尼系数最小的属性作为最优化分属性。

2.3 常见决策树类型比较

2.3.1 ID3 算法

存在的缺点

(1) ID3 算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息.更多精彩文章请关注公众号『Pythonnote』或者『全栈技术精选』

(2) ID3算法只能对描述属性为离散型属性的数据集构造决策树。

2.3.2 C4.5算法

做出的改进(为什么使用 C4.5要好)

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

(2) 可以处理连续数值型属性

(3) 采用了一种后剪枝方法

(4) 对于缺失值的处理

C4.5算法的优缺点

优点：产生的分类规则易于理解，准确率较高。

缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

2.3.3 CART算法

CART 算法相比 C4.5 算法的分类方法，采用了简化的二叉树模型，同时特征选择采用了近似的基尼系数来简化计算。

C4.5 不一定是二叉树，但 CART 一定是二叉树。

同时，无论是 ID3 , C4.5 还是 CART ，在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树( multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是 OC1，这里不多介绍。

如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。更多精彩文章请关注公众号『Pythonnote』或者『全栈技术精选』