机器学习之决策树

无监督学习、判别模型、多分类/回归

特点：

适用于小数据集，在进行逐步应答过程中，典型的决策树分析会使用分层变量或决策节点。

场景举例：基于规则的信用评估、赛马结果预测

优点：

计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征；

擅长对人、地点、事物的一系列不同特征、品质、特性进行评估

缺点：

容易过拟合（后续出现了随机森林，减小了过拟合现象）,使用剪枝来避免过拟合

适用数据类型：

数值型和标称型

1. 概念

• 信息

  ​ 这个是熵和信息增益的基础概念，我觉得对于这个概念的理解更应该把他认为是一用名称，就比如‘鸡‘(加引号意思是说这个是名称)是用来修饰鸡(没加引号是说存在的动物即鸡)，‘狗’是用来修饰狗的，但是假如在鸡还未被命名为’鸡’的时候，鸡被命名为‘狗’，狗未被命名为‘狗’的时候，狗被命名为’鸡’，那么现在我们看到狗就会称其为‘鸡’，见到鸡的话会称其为‘鸡’，同理，信息应该是对一个抽象事物的命名，无论用不用‘信息’来命名这种抽象事物，或者用其他名称来命名这种抽象事物，这种抽象事物是客观存在的。

  ​ 引用香农的话，信息是用来消除随机不确定性的东西，当然这句话虽然经典，但是还是很难去搞明白这种东西到底是个什么样，可能在不同的地方来说，指的东西又不一样，从数学的角度来说可能更加清楚一些，数学本来就是建造在悬崖之上的一种理论，一种抽象的理论，利用抽象来解释抽象可能更加恰当，同时也是在机器学习决策树中用的定义，如果带分类的事物集合可以划分为多个类别当中，则某个类（xi）的信息定义如下:

​ 　　　　　　　　　　　　　　　　　　　　　　

​ I(x)用来表示随机变量的信息，p(xi)指是当xi发生时的概率，这里说一下随机变量的概念，随机变量时概率论 中的概念，是从样本空间到实数集的一个映射，样本空间是指所有随机事件发生的结果的并集，比如当你抛硬币的时候，会发生两个结果，正面或反面，而随机事件在这里可以是，硬币是正面；硬币是反面；两个随机事件，而{正面，反面}这个集合便是样本空间，但是在数学中不会说用‘正面’、‘反面’这样的词语来作为数学运算的介质，而是用0表示反面，用1表示正面，而“正面->1”,”反面->0”这样的映射便为随机变量，即类似一个数学函数。

• 熵

  既然信息已经说完，熵说起来就不会那么的抽象，更多的可能是概率论的定义，熵是约翰.冯.诺依曼建议使用的命名（当然是英文），最初原因是因为大家都不知道它是什么意思，在信息论和概率论中熵是对随机变量不确定性的度量,与上边联系起来，熵便是信息的期望值，可以记作：

  　　　　　　　　　　　　　　　　　　　　　　　　　 　

  ​熵只依赖X的分布，和X的取值没有关系，熵是用来度量不确定性，当熵越大，概率说X=xi的不确定性越大，反之越小，在机器学期中分类中说，熵越大即这个类别的不确定性更大，反之越小，当随机变量的取值为两个时，熵随概率的变化曲线如下图：

　　　　　　　　　　　　　　　　　　　　

当p=0或p=1时，H(p)=0,随机变量完全没有不确定性，当p=0.5时，H(p)=1,此时随机变量的不确定性最大

条件熵

​ 条件熵是用来解释信息增益而引入的概念，概率定义：随机变量X在给定条件下随机变量Y的条件熵，对定义描述为：X给定条件下Y的条件干率分布的熵对X的数学期望，在机器学习中为选定某个特征后的熵，公式如下：

　　　　　　　　　　　　　　　　

这里可能会有疑惑，这个公式是对条件概率熵求期望，但是上边说是选定某个特征的熵，没错，是选定某个特征的熵，因为一个特征可以将待分类的事物集合分为多类，即一个特征对应着多个类别，因此在此的多个分类即为X的取值。

• 信息增益

  信息增益在决策树算法中是用来选择特征的指标，信息增益越大，则这个特征的选择性越好，在概率中定义为：待分类的集合的熵和选定某个特征的条件熵之差（这里只的是经验熵或经验条件熵，由于真正的熵并不知道，是根据样本计算出来的），公式如下：

　　　　　　　　　　　　　　　　

​ 注意：这里不要理解偏差，因为上边说了熵是类别的，但是在这里又说是集合的熵，没区别，因为在计算熵 的时候是根据各个类别对应的值求期望来等到熵

​ 信息增益算法（举例，摘自统计学习算法）

​ 训练数据集合D，|D|为样本容量，即样本的个数（D中元素个数），设有K个类Ck来表示，|Ck|为Ci的样本个数，|Ck|之和为|D|，k=1，2…..，根据特征A将D划分为n个子集D1，D2…..Dn，|Di|为Di的样本个数，|Di|之和为|D|,i=1,2,….,记Di中属于Ck的样本集合为Dik,即交集，|Dik|为Dik的样本个数，算法如下：

​ 输入：D，A

​ 输出：信息增益g(D,A)

(1)D的经验熵H(D)

　　　　　　　　

​ 此处的概率计算是根据古典概率计算，由于训练数据集总个数为|D|，某个分类的个数为|Ck|，在某个分类的概率，或说随机变量取某值的概率为：|Ck|/|D|

(2)选定A的经验条件熵H(D|A)

　　　　　　　　

此处的概率计算同上，由于|Di|是选定特征的某个分类的样本个数，则|Di|/|D|,可以说为在选定特征某个分类的概率，后边的求和可以理解为在选定特征的某个类别下的条件概率的熵，即训练集为Di，交集Dik可以理解在Di条件下某个分类的样本个数，即k为某个分类，就是缩小训练集为Di的熵

(3)信息增益

　　　　　　　　

2.基本思路

2.1 伪代码

检测数据集中的所有数据的分类标签是否相同:
​ If so return 类标签
​ Else:
​ 寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
​ 划分数据集
​ 创建分支节点
​ for 每个划分的子集
​ 调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
​ return 分支节点

2.2 算法特点

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。
适用数据类型：数值型和标称型。

​ 分类回归树（CART）是决策树的一种应用形式，其它形式还有 ID3 和 C4.5 等。

​ CART 的非终端节点为根节点和内节点。终端节点为叶节点。每个非终端节点代表一个单个输入变量 (X) 和该变量的分割点；而叶节点代表输出变量 (y)。该模型以如下形式用于预测：沿着决策树的分叉点，到达叶节点，输出在该叶节点上表示的值。

​ 图 3 中的决策树分类了某人根据自己的年龄和婚姻状况决定买跑车还是旅行车。如果此人超过 30 岁且未婚，我们这样沿着决策树：“超过 30 岁吗？” -> 是 ->“已婚？” -> 否。因此，模型的输出结果为跑车。

​ 决策树的生成是一个递归过程

三种情况下导致导致递归返回：

• 当前节点包含的样本全属于一个类别，无需划分
• 当前属性集为空，或是所有属性上取值相同，无法划分
• 当前节点包含的样本集合为空，不能划分

如何建立决策树(Hunt算法)

Hunt算法的递归定义：

1. 如果与节点t相关联的训练记录集中，所有记录都属于同一个类，则t是叶节点
2. 如果与节点t相关联的训练记录集中包含属于多个类的记录，则选择一个属性测试条件，将记录划分为较小长度子集。对于测试条件的而每个输出，创建一个子节点，并根据测试结果将Dt中的记录分布到子节点中，然后对每个子节点递归调用此方法。

• ID3（Iterative Dichotomiser 3）

  由 Ross Quinlan 在1986年提出。该算法创建一个多路树，找到每个节点（即以贪心的方式）分类特征，这将产生分类目标的最大信息增益。决策树发展到其最大尺寸，然后通常利用剪枝来提高树对未知数据的泛华能力。

• C4.5

  是 ID3 的后继者，并且通过动态定义将连续属性值分割成一组离散间隔的离散属性（基于数字变量），消除了特征必须被明确分类的限制。C4.5 将训练的树（即，ID3算法的输出）转换成 if-then 规则的集合。然后评估每个规则的这些准确性，以确定应用它们的顺序。如果规则的准确性没有改变，则需要决策树的树枝来解决。

• C5.0

  Quinlan 根据专有许可证发布的最新版本。它使用更少的内存，并建立比 C4.5 更小的规则集，同时更准确。

• CART（Classification and Regression Trees （分类和回归树））

  与 C4.5 非常相似，但它不同之处在于它支持数值目标变量（回归），并且不计算规则集。CART 使用在每个节点产生最大信息增益的特征和阈值来构造二叉树。

scikit-learn 源代码中使用 CART 算法的优化版本。

3. 使用

3.1 一般流程

收集数据：可以使用任何方法。
准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
训练算法：构造树的数据结构。
测试算法：使用经验树计算错误率。（经验树没有搜索到较好的资料，有兴趣的同学可以来补充）
使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

3.2 调参

4. 代码实现

4.1 核心算法

def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    # 如果数据集的最后一列的第一个值出现的次数=整个集合的数量，也就说只有一个类别，就只直接返回结果就行
    # 第一个停止条件：所有的类标签完全相同，则直接返回该类标签。
    # count() 函数是统计括号中的值在list中出现的次数
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果
    # 第二个停止条件：使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)

    # 选择最优的列，得到最优列对应的label含义
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 获取label的名称
    bestFeatLabel = labels[bestFeat]
    # 初始化myTree
    myTree = {bestFeatLabel: {}}
    # 注：labels列表是可变对象，在PYTHON函数中作为参数时传址引用，能够被全局修改
    # 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in list
    del(labels[bestFeat])
    # 取出最优列，然后它的branch做分类
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        # 求出剩余的标签label
        subLabels = labels[:]
        # 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
        # print 'myTree', value, myTree
    return myTree

4.2 sklearn实现

• 决策树分类器

import numpy as np
import matplotlib.pyplot as plt

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

# 参数
n_classes = 3
plot_colors = "bry"
plot_step = 0.02

# 加载数据
iris = load_iris()

for pairidx, pair in enumerate([[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]):
    # 我们只用两个相应的features
    X = iris.data[:, pair]
    y = iris.target

    # 训练
    clf = DecisionTreeClassifier().fit(X, y)

    # 绘制决策边界
    plt.subplot(2, 3, pairidx + 1)

    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step),
                         np.arange(y_min, y_max, plot_step))

    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    cs = plt.contourf(xx, yy, Z, cmap=plt.cm.Paired)

    plt.xlabel(iris.feature_names[pair[0]])
    plt.ylabel(iris.feature_names[pair[1]])
    plt.axis("tight")

    # 绘制训练点
    for i, color in zip(range(n_classes), plot_colors):
        idx = np.where(y == i)
        plt.scatter(X[idx, 0], X[idx, 1], c=color, label=iris.target_names[i],
                    cmap=plt.cm.Paired)

    plt.axis("tight")

plt.suptitle("Decision surface of a decision tree using paired features")
plt.legend()
plt.show()

• 决策树回归器

# 引入必要的模型和库
import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt

# 创建一个随机的数据集
# 参考 https://docs.scipy.org/doc/numpy-1.6.0/reference/generated/numpy.random.mtrand.RandomState.html
rng = np.random.RandomState(1)
# print 'lalalalala===', rng
# rand() 是给定形状的随机值，rng.rand(80, 1)即矩阵的形状是 80行，1列
# sort() 
X = np.sort(5 * rng.rand(80, 1), axis=0)
# print 'X=', X
y = np.sin(X).ravel()
# print 'y=', y
y[::5] += 3 * (0.5 - rng.rand(16))
# print 'yyy=', y

# 拟合回归模型
# regr_1 = DecisionTreeRegressor(max_depth=2)
# 保持 max_depth=5 不变，增加 min_samples_leaf=6 的参数，效果进一步提升了
regr_2 = DecisionTreeRegressor(max_depth=5)
regr_2 = DecisionTreeRegressor(min_samples_leaf=6)
# regr_3 = DecisionTreeRegressor(max_depth=4)
# regr_1.fit(X, y)
regr_2.fit(X, y)
# regr_3.fit(X, y)

# 预测
X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
# y_1 = regr_1.predict(X_test)
y_2 = regr_2.predict(X_test)
# y_3 = regr_3.predict(X_test)

# 绘制结果
plt.figure()
plt.scatter(X, y, c="darkorange", label="data")
# plt.plot(X_test, y_1, color="cornflowerblue", label="max_depth=2", linewidth=2)
plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=5", linewidth=2)
# plt.plot(X_test, y_3, color="red", label="max_depth=3", linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()

4.3 《机器学习实战》（python3.x）

​ 第三章 决策树

5. 补充

• 优化点
• 证明
• 参考：
  • 李航 《统计学习方法》
  • 周志华《机器学习》
  • ApacheCN