一.介绍

1.定义

决策树：

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

2.熵的相关介绍

熵

用于衡量一个对象的有序程序。系统越有序，熵值越低；系统越混乱或者分散，熵值越高。

信息熵

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

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

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

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

3.把信息转换成熵值

二.决策树的划分依据一：信息增益

信息增益

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

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

定义与公式

案例说明

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

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

可得到三个熵：

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

注意：

信息增益越大，我们优先选择这个属性进行计算，即信息增益优先选择 属性总类别比较多 的进行划分。

三.决策树的划分依据二：信息增益率

增益率：

增益比率度量是用前面的增益度量Gain(S，A)和所分离信息度量SplitInformation(如上例的性别，活跃度等)的比值来共同定义的。

四.决策树的划分依据三：基尼值和基尼指数

基尼值Gini（D）：

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

基尼指数Gini_index（D）：

一般，选择使划分后基尼系数最小的属性作为最优化分属性。

基尼增益

选择基尼增益最大的点，进行优化划分

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

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

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

• 分割成两个节点N1和N2

• 对N1和N2分别继续执行2-3步，直到每个节点足够“纯”为止。

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

数字型（Numeric）：

通过对数据取两个数字之间的中间值，进行划分。

变量类型是整数或浮点数，如“年收入”。用“>=”，“>”,“<”或“<=”作为分割条件（排序后，利用已有的分割情况，可以优化分割算法的时间复杂度）。

名称型（Nominal）：

通过对属性的类别进行划分。

类似编程语言中的枚举类型，变量只能从有限的选项中选取，比如“婚姻情况”，只能是“单身”，“已婚”或“离婚”，使用“=”来分割。

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

​ 如果一个分割点可以将当前的所有节点分为两类，使得每一类都很“纯”，也就是同一类的记录较多，那么就是一个好分割点。

​ 比如“拥有房产”，可以将记录分成了两类，“是”的节点全部都可以偿还债务，非常“纯”；“否”的节点，可以偿还贷款和无法偿还贷款的人都有，不是很“纯”，但是两个节点加起来的纯度之和与原始节点的纯度之差最大，所以按照这种方法分割。构建决策树采用贪心算法，只考虑当前纯度差最大的情况作为分割点。

八.常见决策树类型比较

九.三种算法（ID3、C4.5、CART）

1.ID3 算法

存在的缺点

​(1) ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息.

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

2. C4.5算法

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

  • 用信息增益率来选择属性
  • 可以处理连续数值型属性
  • 采用了一种后剪枝方法
  • 对于缺失值的处理

C4.5算法的优缺点

​ 优点：

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

​ 缺点：

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

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

3.CART算法

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

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

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

如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。