决策树算法

决策树算法

决策树概述

决策树的发展史

决策树的概述

决策树是什么?

• 决策树是一种基本的分类与回归方法

• 决策树由节点和有向边组成

• 结点类型: 根节点,内部结点和叶结点

绿色的球代表x,橘色的球代表y

---

决策树: 可以把决策树看成一个if-then规则的集合

• 由决策树的根结点到叶结点的每一条路径构建一条规则
• 路径上内部结点的特征对应这规则的条件,而叶结点的类对应着规则的结论
• 规则集合性质: 互斥并且完备(每一个实例都被一条路径或一条规则所覆盖,而且只被一条路径或一条规则所覆盖)
• 决策树(decision tree)一般都是自上而下的来生成的。每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。
• 决策树是对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多级决策，则决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案。

---

决策树预测流程

1. 收集数据
2. 准备数据: 将收集的信息按照一定规则整理出来,方便后续处理
3. 分析数据
4. 训练算法: 构造决策树
5. 测试算法: 使用经验树计算错误率.当错误率达到了可接收范围,就可以用了
6. 使用算法: 决策树可以更好地理解数据的内在含义

---

---

决策树算法原理

• 决策树学习采用的是自顶向下的递归方法
• 其基本思想是以信息熵为度量构造一颗熵值下降最快的树,到叶子节点处的熵值为零.
• 此时每个叶节点中的实例都属于同一类
• 有监督学习

---

决策树的生成算法

根据不同的目标函数,建立决策树主要有三种算法:

1. ID3 → 信息增益
2. C4.5 → 信息增益率
3. CART → Gini指数

• ID3算法(Iterative Dichotomiser 3)：

  • ID3算法的核心是在决策树各个结点上对应信息增益最大准则选择特征，递归地构建决策树
  • 具体流程：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点；再对子结点递归地调用以上方法，构建决策树。ID3相当于用最大似然法进行概率模型的选择

• C4.5决策树的引入:

  • 通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足
  • 能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理
  • 能够处理具有缺失属性值的训练数据

• CART(Classification And Regression Trees)：

  • CART分类回归树是一种典型的二叉决策树，可以做分类或者回归。如果待预测结果是离散型数据，则CART生成分类决策树；如果待预测结果是连续型数据，则CART生成回归决策树
  • 作为分类决策树时，待预测样本落至某一叶子节点，则输出该叶子节点中所有样本所属类别最多的那一类；作为回归决策树时，待预测样本落至某一叶子节点，则输出该叶子节点中所有样本的均值
  • CART用作分类树时采用基尼系数最小化原则，用作回归树时用平方误差最小化作为选择特征的准则，递归地生成二叉树

---

熵

熵是对平均不确定性的度量,对信息量的度量

---

互信息

平均互信息I：得知特征Y的信息而使得对标 签X的信息的不确定性减少的程度

重点内容:

---

信息增益★

• 特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵:

​ H(D|A)之差，即 g(D,A)=H(D) – H(D|A)

• 遍历所有特征，选择信息增益最大的特征作为当前的分裂特征

---

信息增益–案例示范

---

信息增益率

gr(D,A) = g(D,A) / H(A)

---

Gine系数

基尼系数(基尼不纯度):

基尼系数越小越好

• 创建分类树递归过程中，CART每次都选择当前数据集中 具有最小Gini系数的特征作为结点划分决策树

• 分类问题中，假设有K个类，样本属于第k类的概率为Pk， 则概率分布的基尼系数定义为：

概率 = 1-概率的累和(概率的平方之和)

• 对于二分类问题，若样本点属于第1个类的概率是p，则 概率分布的基尼系数为：

基尼系数案例–资料

动物分类.xlsx 文档下载

---

三种决策树学习算法

ID3：

取值多的属性，更容易使数据更纯，其信息增益更大。

训练得到的是一棵庞大且深度浅的树：不合理。

【信息增益越大越好】

• C4.5

【信息增益率越大越好】

• CART

一个属性的信息增益(率)/gini指数越大，表明属性对样本的熵减少的能力更强，这个属性使得数据由不确

定性变成确定性的能力越强

【Gini系数越小越好】

---

决策树的过拟合

决策树对训练属于有很好的分类能力，但对未知的测试数据未必有好的分类能力，泛化能力弱，即可能发生过拟合现象

• 剪枝

  • 剪枝总体思路：
    • 由完全树T0开始，剪枝部分结点得到T1，再次剪枝部分结点得到T2… …直到仅剩树根的树Tk；
    • 在验证数据集上对这k个树分别评价，选择损失函数最小的树T
  • 三种剪枝算法
    • 信息增益
    • 信息增益率
    • 基尼系数

• 随机森林

---

决策数–总结

1. 决策树的构建
   • 特征选择
   • 决策树的生成
   • 决策树的修剪
2. 决策树面临的问题
   • 决策树算法比较适合处理离散数值的属性。实际应用中属性是连续的或者离散的情况都比较常见
   • 在应用连续属性值时，在一个树结点可以将属性Ai的值划分为几个区间。然后信息增益的计算就可以采用和离散值处理一样的方法
     • 原则上可以将Ai的属性划分为任意数目的空间。
     • C4.5中采用的是二元分割（Binary Split），需要找出一个合适的分割阈值

---

---

决策树的优缺点

优点:

• 不需要任何领域知识或参数假设

• 适合高维数据

• 简单易于理解

• 短时间内处理大量数据，得到可行且效果较好的结果

缺点:

• 对于各类别样本数量不一致数据，信息增益偏向于那些具有更多数值的特征

• 易于过拟合

• 忽略属性之间的相关性

---

---

决策树代码实现

导入模块

from sklearn.tree import DecisionTreeClassifier
1

tre = DecisionTreeClassifier()
tre.fit(x_train,y_train)
y_predict = dtc.predict(x_test)
1
2
3

---

决策树代码带参数

class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best', max_depth=None, 
min_samples_split=2, min_samples_leaf =1, 
in_weight_fraction_leaf=0.0, max_features=None, 
random_state=None, max_leaf_nodes=None, 
min_impurity_split=1e-07, 
class_weight=None, presort=False)
1
2
3
4
5
6

---

决策树参数解释

1)*criterion:string类型，可选（默认为"gini"）

衡量分类的质量。支持的标准有"gini"代表的是Gini impurity(不纯度)与"entropy"代表的是information gain（信息增益）。

s=None,
random_state=None, max_leaf_nodes=None,
min_impurity_split=1e-07,
class_weight=None, presort=False)

*****

#### 决策树参数解释

1)*criterion:string类型，可选（默认为"gini"）

衡量分类的质量。支持的标准有"gini"代表的是Gini impurity(不纯度)与"entropy"代表的是information gain（信息增益）。

特征选择的标准，有信息增益和基尼系数两种，使用信息增益的是ID3和C4.5算法（使用信息增益比），使用基尼系数的CART算法，默认是gini系数。
1
2
3
4
5
6
7
8
9
10