机器学习系列——决策树(一)

决策树

1. 定义

  顾名思义，决策树是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。例如，我们看到一个人穿着剪裁得体的西装，修身干练的衬衫，那么我们最起码认为这个人仪表大方，干干净净，然后这个人谈吐得体，态度温和，那么我们说这个人很有气质。最终我们得出一个简单的决策：这个人值得交朋友。

  上述的评价过程其实就是决策树的一种生活实例。那么，下面我们从数学的角度来定义决策树算法。

  决策树是一种非参数的有监督学习方法。他能够从一系列有特征和标签的数据中总结出决策规则，并用树状图的结构来呈现这些规则,以解决分类和回归问题。 上述中，“西装衬衫”可以视为一种特征，那么“干净”就可以视为标签。

2. 划分选择

  现在我们已经大致明白什么是决策树，那么，下一个问题就是如何划分这些特征？例如，我们评价一个人，更多是从能直观反映出这个人的一些特征入手。比如谈吐，比如气质，不能因为这个人出门没有系鞋带而认为这个人邋遢。所以我们要选择最有用，最直观的特征来作为决策的关键。也就是说，我们应该如何选择最优属性来进行划分？

  为了将特征和标签转化为一棵树，决策树需要找出最佳节点和最佳的分枝方法。对分类树来说，衡量这个最佳的指标叫做不纯度。也就是说，我们希望随着划分过程的不断进行，决策树的分支节点所包含的样本尽可能属于同一类别，即节点的不纯度越来越低。

  通常来说。不纯度越低，决策树对训练集的拟合越好。现在使用的决策树算法在分枝方法上的核心大多是围绕在对某个不纯度相关指标的最优化上。

2.1 信息增益

  划分数据的大原则就是：将无序的数据变得更加有序。在划分数据集之前之后，信息发成的变化成为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益。

  那么，如何定义信息呢？如果待分类的数据可能划分为多个分类，则符号xi的信息定义为：
$l(x_i) = -log_2(p(x_i))$l(xi​)=−log2​(p(xi​))
其中p(xi)是选择该分类的概率，也就是该分类在原待分数据集中的比例。

  因为待分的数据集中有很多类，我们需要计算所有类别中每一类特征划分数据集之后获得信息增益。具体来说，如果原数据集*100个数据，包含10类，选择其中一个分类之后获得的数据集为50个，只包含两类。那么数据明显区分的更清晰。

  假如有变量X，其可能的取值有n种，每一种取到的概率为Pi，那么X的熵就定义为

  所谓信息量，就是熵(物理学中定位为混乱度)。信息增益也就可以理解为父节点的熵减去子节点的熵（具体计算公式再次不做过多解释，感兴趣的可以自行百度）。信息增益越大，新节点较父节点来说，混乱度更低，纯度提升更大。

2.2 基尼指数

  CART决策树使用基尼系数来划分属性，在CART算法中,基尼指数表示一个随机选中的样本在子集中被分错的可能性。基尼指数为这个样本被选中的概率乘以它被分错的概率。直观来说，基尼指数反映了从数据集D中随机抽取两个样本，其类别不一致的概率。因此，基尼指数越小，则数据集D的纯度越高。

数据集D的纯度可以使用基尼值来度量：
$Gini（D） = 1-\sum_{k=1}^K(p_k)^2$Gini（D）=1−k=1∑K​(pk​)2

3. 决策树分类

• 分类树：对离散变量做决策树
• 回归树：对连续变量做决策树

3.模型参数

  sklearn中的决策树模型,此处选择较重要的参数稍作讲解。如需要每个参数更详细的注解，参考sklearn官网。

class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort='deprecated', ccp_alpha=0.0)[source]

3.1 criterion

字符型，可不填，默认基尼系数(‘gini’).
用来衡量分支质量的指标，即衡量不纯度的指标，输入"gini"使用基尼系数，输入“entropy”使用信息增益。

3.2 splitter

字符型，可不填，默认最佳分枝(‘best’)
确定每个节点的分支策略。输入‘best’使用最佳分枝，输入‘random’使用最佳随机分枝

3.3 max_depth

整数或者None，可不填，默认None
树的最大深度。如果是None，树会持续生长直到所有叶子节点的不纯度为0，或者输入一个数字，则树的最大高度为该数字

3.4 min_samples_split

整形或浮点数，可不填，默认为2。一个中间节点要继续分枝所需要的最小样本量。如果一个节点中的样本量小于min_samples_split中填写的数字，这个节点就不会继续向下分枝。

• 如果输入为整数，则认为输入的数字是分枝所需的最小样本量。
• 如果输入浮点数，则认为输入的浮点数是比例，乘以输入模型的样本量是分枝所需的最小样本量。

3.5 min_samples_leaf

整型或浮点数，可不填，默认为1
一个叶节点要存在所需要的的最小样本量。一个节点在分枝后的每个子节点中，必须要包含至少min_samples_leaf个训练样本，否则不会分枝。

• 如果输入为整数，则认为输入的数字是分枝后的节点存在所需的最小样本量。
• 如果输入浮点数，则认为输入的浮点数是比例，乘以输入模型的样本量是分枝后的节点存在所需的最小样本量

3.6 max_features

整形，浮点数，字符型或None，可不填，默认None。
在做最佳分枝的时候，考虑的特征个数

• 输入整数，则每次分枝只考虑max_features个特征
• 输入浮点数，则认为输入的浮点数为比例，每次分枝考虑的特征个数为max_features * 总特征个数
• 输入‘auto’，sklearn自动选择最适合分枝的特征数目
• 输入‘sqrt’，,使用总特征个数的平方根作为分枝时考虑的特征数目
• • 输入‘log2’，使用log2(总特征个数)作为分枝时考虑的特征数目
• 输入None，考虑所有特征进行分枝

3.7 random_state

整数，sklearn中设定好的random_state实数或None。可不填，默认None。

3.8 min_impurity_decrease

浮点数，可以不填，默认为0
当一个节点的分枝后，不纯度的降低大于等于min_impurity_decrease中输入的数值，则不会继续分枝。

4. 代码实现

决策树算法的基本流程：

1. 收集数据：可以使用任何方法
2. 准备数据：分类树数据必须离散化
3. 分析数据：树构造完成后，我们应该检车图形是否符合预期
4. 训练算法
5. 测试算法：计算准确率
6. 使用算法

  下面的代码使用sklearn中自带的红酒数据集进行决策树算法的实现。

引包

[1]:from sklearn import tree
    import numpy as np
    import pandas as pd
    import matplotlib.pyplot as plt
    from sklearn.datasets import load_wine
    from sklearn.model_selection import train_test_split

加载数据集

[2]:wine = load_wine()
[3]:wine.data  #特征
array([[1.423e+01, 1.710e+00, 2.430e+00, ..., 1.040e+00, 3.920e+00,
        1.065e+03],
       [1.320e+01, 1.780e+00, 2.140e+00, ..., 1.050e+00, 3.400e+00,
        1.050e+03],
       [1.316e+01, 2.360e+00, 2.670e+00, ..., 1.030e+00, 3.170e+00,
        1.185e+03],
       ...,
       [1.327e+01, 4.280e+00, 2.260e+00, ..., 5.900e-01, 1.560e+00,
        8.350e+02],
       [1.317e+01, 2.590e+00, 2.370e+00, ..., 6.000e-01, 1.620e+00,
        8.400e+02],
       [1.413e+01, 4.100e+00, 2.740e+00, ..., 6.100e-01, 1.600e+00,
        5.600e+02]])
[4]:wine.target  # 标签
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2,
       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
       2, 2])
[5]:wine.feature_names  # 特征名称
['alcohol',
 'malic_acid',
 'ash',
 'alcalinity_of_ash',
 'magnesium',
 'total_phenols',
 'flavanoids',
 'nonflavanoid_phenols',
 'proanthocyanins',
 'color_intensity',
 'hue',
 'od280/od315_of_diluted_wines',
 'proline']

切分数据集

[6]:Xtrain,Xtest,Ytrain,Ytest = train_test_split(wine.data,wine.target,test_size = 0.3)

[7]:Xtrain.shape
(124, 13)

[8]:Xtest.shape
(54, 13)

建立模型

[9]:clf = tree.DecisionTreeClassifier(criterion="entropy") # 模型实例化
[10]:clf = clf.fit(Xtrain,Ytrain) # 训练模型
[11]:score = clf.score(Xtest,Ytest) # 给模型打分
     score
0.9629629629629629

绘画树状图

import graphviz
dot_data = tree.export_graphviz(clf,out_file=None,feature_names=feature_name,filled=True,rounded=True)
graph = graphviz.Source(dot_data)
graph

5. 优缺点

优点：计算复杂度不高，输出结果易于理解，对中间值的确实不敏感，可以处理不相关特征数据
缺点：容易过拟合，必须使用诸如修剪（当前不支持），设置叶节点处所需的最小样本数或设置树的最大深度之类的机制。

6 .实战项目

近期马上更新，可以关注一下新人博主！！！

参考资料：

• 周志华《机器学习》
• 《机器学习实战》
• 菊安酱 决策树