决策树

青旅半醒 2022-01-30 06:49 496阅读 0赞

# 决策树 #

## 声明 ##

本文是来自网络文档和书本(周老师)的结合。

## 概述 ##

决策树(Decision Tree）是在已知各种情况发生概率的[基础][Link 1]上，通过构成决策树来求取净现值的[期望][Link 2]值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 信息熵(系统的凌乱程度)，使用算法[ID3][], [C4.5][]和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

决策树是一种树(二叉树或多叉树)形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

分类树（决策树）是一种十分常用的分类方法，他是一种监管学习。所谓监管学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。\[以上来自百度词条\]

## 简图 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 1][]

上图出自北风培训的课件，决策树的图有很多，随便找了两个。

## 种类 ##

分类树--对离散变量做决策树，分类树用于分类，如晴天/阴天/雨天，用户性别、邮件是否垃圾邮件。

回归树--对连续变量做决策树，回归树用于预测实数值，如明天的温度，用户的年龄。

## 算法原理 ##

有监督的学习、非参数学习算法、自顶向下递归方式构造决策树、在每一步选择中都采取在当前状态下最好/优的选择。

决策树（Decision Tree）是一种简单但是广泛使用的分类器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。决策数有两大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。

## 构造过程 ##

构建决策树重要步骤是选择最佳属性，使得基于该属性分裂后，每个分支的记录类别尽可能纯。

构建的决策树是否是严格的二叉树由属性选择度量确定，某些属性选择度量，如基尼系数强制结果树是二叉树，其他度量，如信息增益、信息增益比率并非如此，它允许多路划分。

## ##

### 构建步骤 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 2][]  
上表根据历史数据，记录已有的用户是否可以偿还债务，以及相关的信息。通过该数据，构建的决策树如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 3][]  
比如新来一个用户：无房产，单身，年收入55K，那么根据上面的决策树，可以预测他无法偿还债务（蓝色虚线路径）。从上面的决策树，还可以知道是否拥有房产可以很大的决定用户是否可以偿还债务，对借贷业务具有指导意义。

大概解释一下：

决策树算法构建的基本步骤如下：

1. 开始，所有记录看作一个节点

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

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

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

决策树算法的构建是基于递归建立的，其中有三种情况导致递归返回：

（1）当前节点包含的样本全属于用一类别，无需划分

（2）当前属性集为空，或是所有样本在所有属性上取值（类别）相同

（3）当前节点包含的样本集合为空，不能划分

（4）当前节点中记录数小于某个阈值，同时迭代次数达到给定值时，停止构建过程，此时使用 max(p(i))作为节点的对应类型

前三种可能会使树的节点过多，导致过拟合(Overfiting)等问题;比较常用的方式是使用 方式(4)作为停止条件。

### 信息量 ###

指的是一个样本/事件所蕴含的信息，如果一个事件的概率越大，那么就 可以认为该事件所蕴含的信息越少。极端情况下，比如:“太阳从东方升起”， 因为是确定事件，所以不携带任何信息量。

下面是我看过的，个人认为比较好的，贴出来：

若一事假有k种结果, 对应概率为![P\_i][P_i], 则此事件发生后所得到的信息量I为---出自简书

![20190518160727428.png][]

### **信息熵** ###

决策树学习的关键在于如何选择最优的划分属性，所谓的最优划分属性，对于二元分类而言，就是尽量使划分的样本属于同一类别，即“纯度”最高的属性。那么如何来度量特征（features）的纯度，这时候就要用到“信息熵（information entropy）”。1948年，香农引入信息熵;一个系统越是有序， 信息熵就越低，一个系统越是混乱，信息熵就越高，所以 信息熵被认为是一个系统有序程度的度量。公式如下：

![2019051815544779.png][]

下面是出自简书的定义，其实跟上面定义的Ent(D)是一样的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 4][]

### 条件熵 ###

假设随机变量(X,Y), 其联合分布概率为P(X=xi,Y=yi)=Pij, i=1,2,...,n;j=1,2,..,m  
则条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性, 其定义为X在给定条件下Y的条件概率分布的熵对X的数学期望.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 7][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 8][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 9][]

### 信息增益 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 10][]

**下面来举个例子说明具体是怎样操作的，只贴公式没多大意义，还是有不利于大家理解。举例子用的数据集为：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 11][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 12][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 13][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 14][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 15][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 16][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 17][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 18][]

注：上图红色框起来的部分，是西瓜书印刷错误，上图已改正。周老师在他的勘误网站也有说明，详见[勘误网站][Link 3]

说了这么多，下面就来看看用决策树算法跑出来的效果，本人主要用weka的ID3算法（使用的信息增益），以供大家参看，后面还会放出自己实现的版本，后面再说。（之所以不要sklearn库里的决策树，是因为sklearn库里的决策树提供的是使用Gini指数优化后的CART，并不提供ID3和C4.5算法）。  
由于新版本weka里已经不再提供ID3算法了，只能下载另外的安装包，把下载方法也贴出来吧，打开weka的Tools->package manager在里面找到包simpleEducationalLearningSchemes安装即可。安装好后就可以把西瓜数据集2.0来测试了，不过要想在weka中构建模型，还要先把.txt格式转换为.arff格式，转换的代码以及转换好的数据集，详见github。另外simpleEducationalLearningSchemes提供的ID3并不像J48那样支持可视化，因此参考链接基于以前weka老版本写的可视化，但该代码在新版本中无法使用，我修改了下整合到ID3上了，现在可以支持可视化了，测试西瓜数据集，生成的可视化树如下，具体代码也放到了github上，有兴趣的可以看看。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 19][]

但信息增益有个缺点就是对可取数值多的属性有偏好，举个例子讲，还是考虑西瓜数据集，如果我们把“编号”这一列当做属性也考虑在内，那么可以计算出它的信息增益为0.998，远远大于其他的候选属性，因为“编号”有17个可取的数值，产生17个分支，每个分支结点仅包含一个样本，显然这些分支结点的纯度最大。但是，这样的决策树不具有任何泛化能力。还是拿西瓜数据集2.0来测试下，如果考虑编号这一属性，看看ID3算法会生成一颗什么样的决策树：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 20][]

显然是生成了一颗含有17个结点的树，这棵树没有任何的泛化能力，这也是ID3算法的一个缺点。另外补充一下ID3算法的详细情况：  
Class for constructing anunpruned decision tree based on the ID3 algorithm.   
Can only deal with nominal attributes. No missing values allowed.   
Empty leaves may result in unclassified instances. For more information see: R. Quinlan (1986). Induction of decision trees. Machine Learning. 1(1):81-106.  
由于ID3算法的缺点，Quinlan后来又提出了对ID3算法的改进C4.5算法（在weka中为J48），C4.5使用了信息增益率来构造决策树，此外C4.5为了避免过拟合，还提供了剪枝的功能。C4.5还能够处理连续值与缺失值。剪枝与连续值和缺失值的处理在下一篇博客中再介绍。先来看看信息增益率：  
信息增益率  
信息增益比的定义为：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 21][]

### 混淆矩阵 ###

见本期[混淆矩阵][Link 4]

### [基尼系数][Link 5] ###

CART决策树使用  [基尼系数][Link 5] 来选择划分属性，同信息熵一样，反映了数据纯度问题，从数据集D中随机抽取两个样本，

其类别标记不一致的概率。Gini(D)越小，则数据集D的纯度越高。

## 决策树生成算法 ##

### ID3 ###

//todo

### C4.5 ###

### //todo ###

###    CART(Classification And Regression Tree) ###

//todo

## 优缺点 ##

决策树存在的限制是他比较容易过拟合，特别是当数据中包含大量特征时。决策树过于复杂，很容易就发生过拟合现象。选择决策树参数时要小心，尽量防止这种现象发生。决策树的优点是可以通过集成的方法，从决策树中构建更大的分类器。

## 实例 ##

数据集直接截图吧：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 22][]

源码

import pandas as pd
    import numpy as np
    from sklearn.model_selection import train_test_split
    from sklearn.preprocessing import LabelEncoder
    from collections import defaultdict
    from sklearn import tree
    
    df=pd.read_csv('/Users/****/Downloads/raw_data.csv')
    df.head(5)
    
    x = df.drop(['RID','Class:buys_computer'],axis=1)
    # y = df.Class:buys_computer
    print("x=",x)
    y = df['Class:buys_computer']
    print("y=",y)
    
    # 标签转换---必须转为浮点型,不然报错:could not convert string to float: 'youth'
    d = defaultdict(LabelEncoder)
    X_trans = x.apply(lambda x: d[x.name].fit_transform(x))
    X_trans.head()
    
    
    X_train, X_test, y_train, y_test = train_test_split(X_trans, y, random_state=1)   #将数据拆分为测试集与训练集
    clf = tree.DecisionTreeClassifier(max_depth=3)
    clf = clf.fit(X_train,y_train)#调用机器学习包-决策树模型
    test_rec = X_test.iloc[1,:]
    print("1323123123test_rec=",test_rec)
    z=clf.predict([test_rec])#使用测试集数据验证模型，输入预测结果
    print("z=",z)

[Link 1]: https://baike.baidu.com/item/%E5%9F%BA%E7%A1%80/32794
[Link 2]: https://baike.baidu.com/item/%E6%9C%9F%E6%9C%9B/35704
[ID3]: https://baike.baidu.com/item/ID3
[C4.5]: https://baike.baidu.com/item/C4.5
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70]: /images/20220130/0102eff98836475a9ae5383ec1c398fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 1]: /images/20220130/4fcb9f5498a847c4b23849cdd87162ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 2]: /images/20220130/4dc5c6dbf46247b09b3ce7d45e18d1f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 3]: /images/20220130/6fa25b3f127144b88caf52f131094f7e.png
[P_i]: https://math.jianshu.com/math?formula=P_i
[20190518160727428.png]: /images/20220130/4bf88fda3f924c41a4531567bd56ca78.png
[2019051815544779.png]: /images/20220130/01495d25f9a34ec4baf354daaa9fb534.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 4]: /images/20220130/19d3db434248439c99d57ae5716e4893.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 5]: /images/20220130/2ff579007fe44bc59b3a9ed7357e0053.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 6]: /images/20220130/85330c3909794d58b5aa58270c01ce45.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 7]: /images/20220130/73b3befa55074c4c8f2e5c28b3e5ec86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 8]: /images/20220130/57a2b34aa8074a7c870e90d7b4b40c56.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 9]: /images/20220130/0d9c12501ffd4053b2fd2c8817b13b87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 10]: /images/20220130/8a2542201d6d44269c0a3044214d268d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 11]: /images/20220130/e343904940d741e0b9eda01a1327b451.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 12]: /images/20220130/67061ac4027b44e39aa8e3bd1ba46fc0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 13]: /images/20220130/a0b4cdefa3d94efebe7344a731270ca0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 14]: /images/20220130/6adf689bc80d4845aea8726be9156685.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 15]: /images/20220130/ec16ccc75b4245788cf2349f6f18bcaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 16]: /images/20220130/2caf1d0e31224805a886a8e495bd64dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 17]: /images/20220130/6ca8739907324ab7b416ff89a8fe50c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 18]: /images/20220130/2698898323aa44ec9233440bd4dd050d.png
[Link 3]: https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/MLbook2016.htm
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 19]: /images/20220130/69767d50992942fc91e3cf62bafeb3ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 20]: /images/20220130/bba1beb73ad443f9acb993023c766172.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 21]: /images/20220130/ca8b15a4d069493fac46a56cc7233ab2.png
[Link 4]: https://blog.csdn.net/waeceo/article/details/90436827
[Link 5]: https://blog.csdn.net/waeceo/article/details/90473448
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhZWNlbw_size_16_color_FFFFFF_t_70 22]: /images/20220130/ba6d8ad6ff074f958cee0be4d8e2c167.png