机器学习

决策树

熵、信息增益(ID3)、信息增益率(C4.5)、基尼指数(CART)

Posted by 新宇 on February 21, 2020

一、算法简介

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

二、熵

1. 概念

  • 物理学上
    • 熵 Entropy 是“混乱”程度的量度
    • 系统越有序，熵值越低;系统越混乱或者分散，熵值越高。
  • 信息理论
    • 当系统的有序状态一致时，数据越集中的地方熵值越小，数据越分散的地方熵值越大。
    • “信息熵” (information entropy)是度量样本集合纯度最常用的一种指标

2. 信息熵公式

三、决策树划分依据

1. 信息增益 —— ID3

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

1.1 信息增益案例

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

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

可得到三个熵:

  • 整体熵

  • 性别的信息增益

  • 活跃度的信息增益

活跃度的信息增益比性别的信息增益大，也就是说，活跃度对用户流失的影响比性别大。

在做特征选择或者数据分析的时候，我们应该重点 考察活跃度这个指标。

1.2 存在的缺点

  • ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息.
  • ID3算法只能对描述属性为离散型属性的数据集构造决策树。

2. 信息增益率 —— C4.5

2.1 解决了什么问题

  • 信息增益准则对可取值数目较多的属性有所偏好
  • 为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法 [Quinlan， 1993J 不直接使用信息增益，而是使用”增益率” (gain ratio) 来选择最优划分属性.

2.2 定义

增益率是用前面的信息增益Gain(D, a)和属性a对应的”固有值”(intrinsic value) [Quinlan,1993J的比值来共同定义的。

2.3 案例

继续对上述案例进行信息增益率计算

  • 计算属性分类信息度量

  • 计算信息增益率

活跃度的信息增益率更高一些，所以在构建决策树的时候，优先选择；

通过这种方式，在选取节点的过程中，我们可以降低取值较多的属性的选取偏好。

2.4 C4.5的优势

  • 1.用信息增益率来选择属性
    • 克服了用信息增益来选择属性时偏向选择值多的属性的不足
  • 2.采用了一种后剪枝方法
    • 避免树的高度无节制的增长，避免过度拟合数据
  • 3.对于缺失值的处理
    • 处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值
    • 另外一种更复杂的策略是为A的每个可能值赋予一个概率。
  • 4.可以处理连续数值型属性

2.5 C4.5的缺点

  • 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。
  • 此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

3. 基尼值和基尼指数 —— CART

3.1 CART

CART决策树(Classification and Regression Tree) [Breiman et al., 1984] 使用”基尼指数” (Gini index)来选择划分属性, 这是一种著名的决策树学习算法,分类和回归任务都可用;

3.2 基尼值Gini和基尼指数Gini_index

3.3 案例分析

  • 第一次大循环：

    • 根节点的Gini值为:

    • 当根据是否有房来进行划分时，Gini指数计算过程为

    • 若按婚姻状况属性来划分，属性婚姻状况有三个可能的取值{married，single，divorced}，分别计算划分后的Gini系数增益

    • 同理可得年收入Gini

  • 第二次大循环
    • 接下来，采用同样的方法，分别计算剩下属性，其中根节点的Gini系数为(此时是否拖欠贷款的各有3个records)

  • 经过如上流程，构建的决策树，如下图

4. 多变量决策树 —— OC1

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

5. 决策树变量的两种类型

  • 数字型
    • 变量类型是整数或浮点数，如前面例子中的“年收入”。用“>=”，“>”,“<”或“<=”作为分割条件(排序后，利用已有的分 割情况，可以优化分割算法的时间复杂度)
  • 名称型
    • 类似编程语言中的枚举类型，变量只能从有限的选项中选取，比如前面例子中的“婚姻情况”，只能是“单身”，“已 婚”或“离婚”，使用“=”来分割。

6. 如何评估分割点的好坏?

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

四、剪枝

1. 剪枝的意义

  • 剪枝 (pruning)是决策树学习算法对付”过拟合”的主要手段。

2. 常用的减枝方法

  • 决策树剪枝的基本策略有”预剪枝”(pre-pruning)和”后剪枝”(post- pruning) 。
    • 预剪枝
      • 指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将 当前结点标记为叶结点;
    • 后剪枝
      • 则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树 泛化性能提升，则将该子树替换为叶结点。

3. 预剪枝

4. 后剪枝

5. 两种剪枝方法对比

  • 后剪枝决策树通常比预剪枝决策树保留了更多的分支。
  • 一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。
  • 但后剪枝过程是在生成完全决策树之后进行的。并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决 策树和预剪枝决策树都要大得多.

五、API介绍

  • class sklearn.tree.DecisionTreeClassifier(criterion=’gini’, max_depth=None,random_state=None)
    • criterion
      • 特征选择标准
      • “gini”或者”entropy”，前者代表基尼系数，后者代表信息增益。一默认”gini”，即CART算法。
    • min_samples_split
      • 内部节点再划分所需最小样本数
      • 这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。默认是2.如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。我之前的一个项目例子，有大概10 万样本，建立决策树时，我选择了min_samples_split=10。可以作为参考。
    • min_samples_leaf
      • 叶子节点最少样本数
      • 这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。 默认是1,可以输入最少的 样本数的整数，或者最少样本数占样本总数的百分比。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增 大这个值。之前的10万样本项目使用min_samples_leaf的值为5，仅供参考。
    • max_depth
      • 决策树最大深度
      • 决策树的最大深度，默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者 特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分 布。常用的可以取值10-100之间
    • random_state
      • 随机数种子

六、案例——泰坦尼克号乘客生存预测

1. 案例背景

泰坦尼克号沉没是历史上最臭名昭着的沉船之一。1912年4月15日，在她的处女航中，泰坦尼克号在与冰山相撞后沉没，在2224名乘客和机组 人员中造成1502人死亡。这场耸人听闻的悲剧震惊了国际社会，并为船舶制定了更好的安全规定。 造成海难失事的原因之一是乘客和机组人员 没有足够的救生艇。尽管幸存下沉有一些运气因素，但有些人比其他人更容易生存，例如妇女，儿童和上流社会。 在这个案例中，我们要求您 完成对哪些人可能存活的分析。特别是，我们要求您运用机器学习工具来预测哪些乘客幸免于悲剧。 (案例:https://www.kaggle.com/c/titanic/overview) 我们提取到的数据集中的特征包括票的类别，是否存活，乘坐班次，年龄，登陆home.dest，房间，船和性别等。 数据:http://biostat.mc.vanderbilt.edu/wiki/pub/Main/DataSets/titanic.txt

2. 步骤分析

  • 1.获取数据
  • 2.数据基本处理
    • 2.1 确定特征值,目标值
    • 2.2 缺失值处理
    • 2.3 数据集划分
  • 3.特征工程(字典特征抽取)
  • 4.机器学习(决策树)
  • 5.模型评估
    1. 决策树可视化

3. 代码实现

import pandas as pd
import numpy as np
from sklearn.feature_extraction import DictVectorizer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_graphviz
# 1.获取数据

titan = pd.read_csv('./data/titanic.txt')
titan.head()

# 2.数据基本处理

# 2.1 确定特征值,目标值 

x = titan[["pclass","age", "sex"]]
y = titan["survived"]

# 2.2 缺失值处理

x["age"].fillna(x["age"].mean(),inplace=True)

# 2.3 数据集划分

x_train, x_test, y_train, y_test = train_test_split(x , y)

# 3.特征工程(字典特征抽取)

transfer = DictVectorizer(sparse=False)
x_train = transfer.fit_transform(x_train.to_dict(orient="records"))
x_test = transfer.fit_transform(x_test.to_dict(orient="records"))

# 4.机器学习(决策树) 
estimator = DecisionTreeClassifier(criterion="entropy", max_depth=5)
estimator.fit(x_train, y_train)

# 5.模型评估
y_pre = estimator.predict(x_test)
print('预测值为:\n', y_pre)
score = estimator.score(x_test, y_test)
print('模型得分为:\n', score)

# 6.决策树可视化
transfer.get_feature_names()
export_graphviz(estimator, out_file="./data/tree.dot", feature_names=['age', 'pclass=1st', 'pclass=2nd', 'pclass=3rd', '女性', '男性'])

4. 决策树可视化

4.1 保存树的结构到dot文件

  • sklearn.tree.export_graphviz() 该函数能够导出DOT格式
    • tree.export_graphviz(estimator,out_file=’tree.dot’,feature_names=[’’,’’])

4.2 图形化显示

  • 方式1
    • 将生成的.dot文件内容拷贝到 http://webgraphviz.com/
  • 方式2
    • 安装graghviz插件, 将.dot文件转成png图片
      • ubuntu系统: sudo apt-get install graghviz
      • Mac系统: brew install graghviz
    • 使用命令生成图片: dot -Tpng -o tree.png tree.dot

七、回归决策树

1. 概念

  • 关于数据类型，我们主要可以把其分为两类，连续型数据和离散型数据。
  • 在面对不同数据时，决策树也可以分为两大类型：
    • 分类决策树
      • 处理离散型数据
    • 回归决策树
      • 主要用于处理连续型数据

2. 原理描述

  • 如何选择划分点?
    • 假如我们有n个特征，每个特征有si(i∈(1,n))个取值，那我们遍历所有特征，尝试该特征所有取值，对空间进行划分，直到取到特征j的取值s，使得损失函数最小，这样就得到了一个划分点
  • 如何决定叶节点的输出值?
    • 使用平方损失函数计算Loss

3. 算法

4. 案例

5. 回归决策树和线性回归对比

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor 
from sklearn import linear_model

# 生成数据

x = np.array(list(range(1, 11))).reshape(-1, 1)
y = np.array([5.56, 5.70, 5.91, 6.40, 6.80, 7.05, 8.90, 8.70, 9.00, 9.05])

# 训练模型

model1 = DecisionTreeRegressor(max_depth=1) 
model2 = DecisionTreeRegressor(max_depth=3) 
model3 = linear_model.LinearRegression() model1.fit(x, y)
model2.fit(x, y)
model3.fit(x, y)

# 模型预测

# 生成1000个数,用于预测模型 X_test.shape

X_test = np.arange(0.0, 10.0, 0.01).reshape(-1, 1) 



y_1 = model1.predict(X_test)
y_2 = model2.predict(X_test)
y_3 = model3.predict(X_test)

# 结果可视化

plt.figure(figsize=(10, 6), dpi=100) 
plt.scatter(x, y, label="data") 
plt.plot(X_test, y_1,label="max_depth=1") 
plt.plot(X_test, y_2, label="max_depth=3") 
plt.plot(X_test, y_3, label='liner regression')
plt.xlabel("data") 
plt.ylabel("target") 
plt.title("Decision Tree Regression") 
plt.legend()
plt.show()

CATALOG
    FEATURED TAGS
    Python 数据结构&算法 数据库 机器学习 特征工程 数据预处理 读书心得 OpenCV CV NLP
    FRIENDS