机器学习算法整理(四)决策树集成学习和随机森林

算法之名

发布于 2021-09-26 11:05:12

4560

发布于 2021-09-26 11:05:12

文章被收录于专栏：算法之名

接机器学习算法整理(三)

决策树

什么是决策树

比方说我们在招聘一个机器学习算法工程师的时候，会依照这样的流程进行逐层的评选，从而达到一个树形结构的决策过程。而在这棵树中，它的深度为3.最多通过3次判断，就能将我们的数据进行一个相应的分类。我们在这里每一个节点都可以用yes或者no来回答的问题，实际上我们真实的数据很多内容都是一个具体的数值。对于这些具体的数值，决策树是怎么表征的呢？我们先使用scikit-learn封装的决策树算法进行一下具体的分类。然后通过分类的结果再深入的认识一下决策树。这里我依然先加载鸢尾花数据集。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鸢尾花数据集的后两个特征
    X = iris.data[:, 2:]
    y = iris.target
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.scatter(X[y == 2, 0], X[y == 2, 1])
    plt.show()

运行结果

现在我们使用scikit-learn中的决策树来进行分类

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鸢尾花数据集的后两个特征
    X = iris.data[:, 2:]
    y = iris.target
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier(max_depth=2, criterion='entropy')
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.scatter(X[y == 2, 0], X[y == 2, 1])
    plt.show()

运行结果

这就是决策树得到的决策边界。通过这个图，我们来画一个决策树，看看它是如何逐层决策的

这就是决策树在面对属性是一种数值特征的时候是怎样处理的。在这里我们可以看到，在每一个节点上，它选择某一个维度，以及和这个维度相应的阈值，比如说在根节点的时候选的是x这个维度和2.4这个阈值。看我们的数据是大于等于2.4还是小于2.4分成两支。在右分支的子节点，选择了y这个维度和1.8这个阈值，看数据点到了这个节点的话是小于1.8还是大于等于1.8来进行分类。

首先决策树是一个非参数学习算法。其次决策树可以解决分类问题，而且可以天然的解决多分类问题。不像逻辑回归和SVM需要使用OvR或者OvO才能解决多分类问题。同时决策树也可以解决回归问题，我们可以用最终落在这个叶子节点中的所有的样本数据的平均值来当作回归问题的预测值。决策树算法也是具有非常好的可解释性。比如说我们在给用户的信用进行评级，比如说他的信用卡超过3次拖延支付，并且他的驾照平均每年都会被扣去8分，满足这样的条件，他的信用评级就会评为C级。我们可以非常容易的描述出来把样本数据分成某一个类的依据。我们现在的问题就是每个节点到底在哪个维度做划分？我们的数据复杂起来的话可能有成百上千个维度。如果我们选好了一个维度，那么我们要在某个维度的哪个值上做划分？这些都是构建决策树的关键问题。

信息熵

对于处理上面提到的问题——节点到底在哪个维度做划分？某个维度的哪个值上做划分？我们有一种方式来进行处理，那就是信息熵。

信息熵是信息论的基础概念，熵在信息论中代表随机变量不确定度的度量。熵越大，数据的不确定性越高；熵越小，数据的不确定性越低。熵是从物理热力学中引申出来的概念，熵越大，在一个封闭的热力系统中，分子无规则运动越剧烈，即不确定性越高；熵越小，封闭的热力系统中，分子越倾向于静止状态，它们的状态就越确定，即不确定性越低。我们来看一下香农提出来的信息熵公式。

其中

表示一个系统中有k类的信息，每一类信息所占的比例就叫做

。比如说在我们的鸢尾花数据集中一共有3种鸢尾花，每一种鸢尾花占的比例可能为1/3，则p1,p2,p3就分别等于1/3.由于

一定是小于等于1的，log(

)是小于等于0的，那么H一定是大于等于0的。

对于鸢尾花的这种各占1/3的分类，它的信息熵就为

再比如有一种分类，其中一种分类占1/10，第二种占2/10，第三种占7/10，那么它的信息熵就为

这种分类的信息熵比鸢尾花分类的信息熵要小，意味着这种分类比鸢尾花的分类更确定。这是因为这种分类第三种分类占了70%，所以这种分类是更确定的。而鸢尾花数据每一个类别各占了1/3，所以这个数据整体它的不确定性就越高。我们再来看一组更极端的数据，依然是三类，其中一类占100%。

信息熵为0，说明它的不确定性是最低的，即最确定的。在代码上，我们以二分类为例来看一下这个公式的图像是什么样子的。对于二分类来说，该公式可以转化为

这里x和1-x表示一类和另一类。

import numpy as np
import matplotlib.pyplot as plt

if __name__ == "__main__":

    def entropy(p):
        # 计算二分类信息熵
        return - p * np.log(p) - (1 - p) * np.log(1 - p)

    x = np.linspace(0.01, 0.99, 200)
    plt.plot(x, entropy(x))
    plt.show()

运行结果

从这个图中，我们可以看出，当x=0.5的时候，我们的信息熵来说，如果我们的数据只有两个类别，当每个类别各占一半的时候，此时整个数据的信息熵就是最大的，此时我们整个数据是最不稳定的，确定性是最低的。在0.5两边，无论x值更小还是更大，整个信息熵都在降低，这里因为无论x变小还是变大，我们的数据都偏向于某一类，整体的确定性变高了，所以相应的信息熵就变低了。

明白了这个概念，那么这两个问题就好说了——节点到底在哪个维度做划分？某个维度的哪个值上做划分？我们要让我们的系统划分后使得信息熵降低，换句话说相应的让我们的系统变的更加确定。

比方说在极端情况下，在A、B、C这三个叶子节点的时候，每一个叶子数据都只属于A、B、C这三类的某一类的话，那么此时我们整个系统的信息熵就达到了0。所以我们就是要找在每一个节点上有一个维度，这个维度上有一个取值，根据这个维度和取值，对我们的数据进行划分，划分以后得到的信息熵是所有其他划分方式得到的信息熵的最小值，我们称这样的一个划分就是当前最好的划分。我们只需要对所有的划分可能性进行一次搜索就可以得到这个最好的划分。我们只需要将这方式递归下去就形成了决策树。

使用信息熵寻找最优划分

模拟使用信息熵进行划分

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap
from collections import Counter
from math import log

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鸢尾花数据集的后两个特征
    X = iris.data[:, 2:]
    y = iris.target
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier(max_depth=2, criterion='entropy')
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()

    def split(X, y, d, value):
        '''
        划分
        :param X: 特征
        :param y: 输出
        :param d: 维度
        :param value: 阈值
        :return:
        '''
        index_a = (X[:, d] <= value)
        index_b = (X[:, d] > value)
        return X[index_a], X[index_b], y[index_a], y[index_b]

    def entropy(y):
        '''
        计算信息熵
        :param y:
        :return:
        '''
        # 建立类别和数量的字典
        counter = Counter(y)
        res = 0
        for num in counter.values():
            p = num / len(y)
            res += - p * log(p)
        return res

    def try_split(X, y):
        '''
        搜索信息熵最小的维度和阈值
        :param X:
        :param y:
        :return:
        '''
        # 定义一个最好的信息熵，初始值为+∞
        best_entropy = float('inf')
        # 定义在哪个维度，哪个阈值上进行划分，初始值都为-1
        best_d, best_v = -1, -1
        # 遍历所有的特征
        for d in range(X.shape[1]):
            # 对d维度上的数据进行排序
            sorted_index = np.argsort(X[:, d])
            # 遍历所有的样本数(不包含第一个样本)
            for i in range(1, len(X)):
                # 拿取候选阈值，为d维的数据中每两个数的中间值，且这两个数不能相等
                if X[sorted_index[i - 1], d] != X[sorted_index[i], d]:
                    v = (X[sorted_index[i - 1], d] + X[sorted_index[i], d]) / 2
                    # 对候选维度和阈值尝试划分
                    X_l, X_r, y_l, y_r = split(X, y, d, v)
                    # 获取对候选维度和候选阈值进行划分后的信息熵
                    e = entropy(y_l) + entropy(y_r)
                    # 获取信息熵最小的维度和阈值
                    if e < best_entropy:
                        best_entropy, best_d, best_v = e, d, v
        return best_entropy, best_d, best_v

    best_entropy, best_d, best_v = try_split(X, y)
    print("best_entropy =", best_entropy)
    print("best_d =", best_d)
    print("best_v =", best_v)

运行结果

best_entropy = 0.6931471805599453
best_d = 0
best_v = 2.45

根据结果，我们可以看出，我们对原始的数据进行划分，是在第0个维度，阈值在2.45的位置进行划分。划分以后信息熵变成了0.693。对照这个结果，我们看一下在scikit-learn中的划分结果

我们可以看到这个决策树第一次划分就是在横轴上，也就是第0个维度，位置大概就是2.45的位置进行的划分。现在我们将划分后的数据进行存储

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap
from collections import Counter
from math import log

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鸢尾花数据集的后两个特征
    X = iris.data[:, 2:]
    y = iris.target
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier(max_depth=2, criterion='entropy')
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()

    def split(X, y, d, value):
        '''
        划分
        :param X: 特征
        :param y: 输出
        :param d: 维度
        :param value: 阈值
        :return:
        '''
        index_a = (X[:, d] <= value)
        index_b = (X[:, d] > value)
        return X[index_a], X[index_b], y[index_a], y[index_b]

    def entropy(y):
        '''
        计算信息熵
        :param y:
        :return:
        '''
        # 建立类别和数量的字典
        counter = Counter(y)
        res = 0
        for num in counter.values():
            p = num / len(y)
            res += - p * log(p)
        return res

    def try_split(X, y):
        '''
        搜索信息熵最小的维度和阈值
        :param X:
        :param y:
        :return:
        '''
        # 定义一个最好的信息熵，初始值为+∞
        best_entropy = float('inf')
        # 定义在哪个维度，哪个阈值上进行划分，初始值都为-1
        best_d, best_v = -1, -1
        # 遍历所有的特征
        for d in range(X.shape[1]):
            # 对d维度上的数据进行排序
            sorted_index = np.argsort(X[:, d])
            # 遍历所有的样本数(不包含第一个样本)
            for i in range(1, len(X)):
                # 拿取候选阈值，为d维的数据中每两个数的中间值，且这两个数不能相等
                if X[sorted_index[i - 1], d] != X[sorted_index[i], d]:
                    v = (X[sorted_index[i - 1], d] + X[sorted_index[i], d]) / 2
                    # 对候选维度和阈值尝试划分
                    X_l, X_r, y_l, y_r = split(X, y, d, v)
                    # 获取对候选维度和候选阈值进行划分后的信息熵
                    e = entropy(y_l) + entropy(y_r)
                    # 获取信息熵最小的维度和阈值
                    if e < best_entropy:
                        best_entropy, best_d, best_v = e, d, v
        return best_entropy, best_d, best_v

    best_entropy, best_d, best_v = try_split(X, y)
    print("best_entropy =", best_entropy)
    print("best_d =", best_d)
    print("best_v =", best_v)
    # 将第一次划分后的数据进行存储
    X1_l, X1_r, y1_l, y1_r = split(X, y, best_d, best_v)
    # 打印划分后左子树的信息熵
    print(entropy(y1_l))
    # 打印划分后的右子树的信息熵
    print(entropy(y1_r))

运行结果

best_entropy = 0.6931471805599453
best_d = 0
best_v = 2.45
0.0
0.6931471805599453

通过跟图形对比，我们知道第一次划分，我们把所有属于第一类的数据全部划分了进去，它没有不确定性，所以第一次划分的第一类的信息熵为0；而除第一类外的信息熵为0.693

对于第一类我们已经不需要划分了，它的信息熵为0。而对于第一类之外的数据的信息熵为0.693，我们可以继续对其进行划分。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap
from collections import Counter
from math import log

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鸢尾花数据集的后两个特征
    X = iris.data[:, 2:]
    y = iris.target
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier(max_depth=2, criterion='entropy')
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()

    def split(X, y, d, value):
        '''
        划分
        :param X: 特征
        :param y: 输出
        :param d: 维度
        :param value: 阈值
        :return:
        '''
        index_a = (X[:, d] <= value)
        index_b = (X[:, d] > value)
        return X[index_a], X[index_b], y[index_a], y[index_b]

    def entropy(y):
        '''
        计算信息熵
        :param y:
        :return:
        '''
        # 建立类别和数量的字典
        counter = Counter(y)
        res = 0
        for num in counter.values():
            p = num / len(y)
            res += - p * log(p)
        return res

    def try_split(X, y):
        '''
        搜索信息熵最小的维度和阈值
        :param X:
        :param y:
        :return:
        '''
        # 定义一个最好的信息熵，初始值为+∞
        best_entropy = float('inf')
        # 定义在哪个维度，哪个阈值上进行划分，初始值都为-1
        best_d, best_v = -1, -1
        # 遍历所有的特征
        for d in range(X.shape[1]):
            # 对d维度上的数据进行排序
            sorted_index = np.argsort(X[:, d])
            # 遍历所有的样本数(不包含第一个样本)
            for i in range(1, len(X)):
                # 拿取候选阈值，为d维的数据中每两个数的中间值，且这两个数不能相等
                if X[sorted_index[i - 1], d] != X[sorted_index[i], d]:
                    v = (X[sorted_index[i - 1], d] + X[sorted_index[i], d]) / 2
                    # 对候选维度和阈值尝试划分
                    X_l, X_r, y_l, y_r = split(X, y, d, v)
                    # 获取对候选维度和候选阈值进行划分后的信息熵
                    e = entropy(y_l) + entropy(y_r)
                    # 获取信息熵最小的维度和阈值
                    if e < best_entropy:
                        best_entropy, best_d, best_v = e, d, v
        return best_entropy, best_d, best_v

    best_entropy, best_d, best_v = try_split(X, y)
    print("best_entropy =", best_entropy)
    print("best_d =", best_d)
    print("best_v =", best_v)
    # 将第一次划分后的数据进行存储
    X1_l, X1_r, y1_l, y1_r = split(X, y, best_d, best_v)
    # 打印划分后左子树的信息熵
    print(entropy(y1_l))
    # 打印划分后的右子树的信息熵
    print(entropy(y1_r))
    # 对右子树继续划分
    best_entropy2, best_d2, best_v2 = try_split(X1_r, y1_r)
    print("best_entropy =", best_entropy2)
    print("best_d =", best_d2)
    print("best_v =", best_v2)
    X2_l, X2_r, y2_l, y2_r = split(X1_r, y1_r, best_d2, best_v2)
    # 打印第二次划分后左子树的信息熵
    print(entropy(y2_l))
    # 打印第二次划分后的右子树的信息熵
    print(entropy(y2_r))

运行结果

best_entropy = 0.6931471805599453
best_d = 0
best_v = 2.45
0.0
0.6931471805599453
best_entropy = 0.4132278899361904
best_d = 1
best_v = 1.75
0.30849545083110386
0.10473243910508653

对于第二次划分，我们可以看信息熵降到最低是0.413，是在第1个维度，阈值在1.75的位置进行划分。对比图形，我们可以看到第二次划分是在纵轴上，也就是第1个维度，位置大概就是在1.75的地方进行划分的。并且划分后，两边的信息熵都没降为0，我们可以向更深的方向继续划分。

我们之前在scikit-learn中，max_depth=2，也就是深度值设为了2，也是划分到此为止。当然我们已经知道了使用信息熵来构建决策树，可以使用二叉树的方式来建立这个决策树，并打印这颗二叉树，关于建立的方式可以参考数据结构整理中关于二分搜索树的内容来进行建立。

基尼系数

除了信息熵可以对决策树的指标进行划分，还有另外一个指标可以对决策树进行划分，这个指标就是基尼系数。基尼系数的公式如下

这个式子和信息熵对应的式子是有同样的性质的，跟信息熵一样，我们先使用几个例子来看一下基尼系数。

通过这三个例子，我们可以看出，基尼系数和信息熵一样可以用来作为数据不确定性的一个度量。我们同样来看一下基尼系数的曲线是什么样子的。对于二分类来说，基尼系数的式子就可以化为

import numpy as np
import matplotlib.pyplot as plt

if __name__ == "__main__":

    def gini(p):
        # 计算二分类基尼系数
        return - 2 * p**2 + 2 * p

    x = np.linspace(0, 1, 200)
    plt.plot(x, gini(x))
    plt.show()

运行结果

现在我们模拟一下使用基尼系数进行划分，看看结果是怎样的。我们依然先使用scikit-learn来绘制一下使用基尼系数的决策树的决策边界。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鸢尾花数据集的后两个特征
    X = iris.data[:, 2:]
    y = iris.target
    dt_clf = DecisionTreeClassifier(max_depth=2, criterion='gini', splitter='best')
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.scatter(X[y == 2, 0], X[y == 2, 1])
    plt.show()

运行结果

现在我们再使用基尼系数来进行最优划分

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap
from collections import Counter

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鸢尾花数据集的后两个特征
    X = iris.data[:, 2:]
    y = iris.target
    dt_clf = DecisionTreeClassifier(max_depth=2, criterion='gini', splitter='best')
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()

    def split(X, y, d, value):
        '''
        划分
        :param X: 特征
        :param y: 输出
        :param d: 维度
        :param value: 阈值
        :return:
        '''
        index_a = (X[:, d] <= value)
        index_b = (X[:, d] > value)
        return X[index_a], X[index_b], y[index_a], y[index_b]

    def gini(y):
        '''
        计算基尼系数
        :param y:
        :return:
        '''
        # 建立类别和数量的字典
        counter = Counter(y)
        res = 1
        for num in counter.values():
            p = num / len(y)
            res -= p**2
        return res

    def try_split(X, y):
        '''
        搜索基尼系数最小的维度和阈值
        :param X:
        :param y:
        :return:
        '''
        # 定义一个最好的基尼系数，初始值为+∞
        best_g = float('inf')
        # 定义在哪个维度，哪个阈值上进行划分，初始值都为-1
        best_d, best_v = -1, -1
        # 遍历所有的特征
        for d in range(X.shape[1]):
            # 对d维度上的数据进行排序
            sorted_index = np.argsort(X[:, d])
            # 遍历所有的样本数(不包含第一个样本)
            for i in range(1, len(X)):
                # 拿取候选阈值，为d维的数据中每两个数的中间值，且这两个数不能相等
                if X[sorted_index[i - 1], d] != X[sorted_index[i], d]:
                    v = (X[sorted_index[i - 1], d] + X[sorted_index[i], d]) / 2
                    # 对候选维度和阈值尝试划分
                    X_l, X_r, y_l, y_r = split(X, y, d, v)
                    # 获取对候选维度和候选阈值进行划分后的基尼系数
                    e = gini(y_l) + gini(y_r)
                    # 获取基尼系数最小的维度和阈值
                    if e < best_g:
                        best_g, best_d, best_v = e, d, v
        return best_g, best_d, best_v

    best_g, best_d, best_v = try_split(X, y)
    print("best_g =", best_g)
    print("best_d =", best_d)
    print("best_v =", best_v)
    # 将第一次划分后的数据进行存储
    X1_l, X1_r, y1_l, y1_r = split(X, y, best_d, best_v)
    # 打印划分后左子树的基尼系数
    print(gini(y1_l))
    # 打印划分后的右子树的基尼系数
    print(gini(y1_r))
    # 对右子树继续划分
    best_g2, best_d2, best_v2 = try_split(X1_r, y1_r)
    print("best_g =", best_g2)
    print("best_d =", best_d2)
    print("best_v =", best_v2)
    X2_l, X2_r, y2_l, y2_r = split(X1_r, y1_r, best_d2, best_v2)
    # 打印第二次划分后左子树的基尼系数
    print(gini(y2_l))
    # 打印第二次划分后的右子树的基尼系数
    print(gini(y2_r))

运行结果

best_g = 0.5
best_d = 0
best_v = 2.45
0.0
0.5
best_g = 0.2105714900645938
best_d = 1
best_v = 1.75
0.1680384087791495
0.04253308128544431

这里通过第一次划分，第一类的基尼系数为0，达到了一个最小值。除第一类的其他类的基尼系数为0.5。第一次划分的维度为0，划分的阈值为2.45。第二次划分的最小基尼系数为0.21，第二次划分的维度为1，划分的阈值为1.75。对于剩下的两个节点，它们的基尼系数依然没有到0，我们可以对这两个节点继续向下划分。

信息熵 vs 基尼系数

通过它们两个的式子，我们可以看出来，信息熵的计算比基尼系数稍慢。在sikit-learn中的决策树默认为基尼系数。在大多数时候，这二者没有特别的效果优劣。对于决策树有其更重要的参数，对比不必纠结这两个参数。

CART与决策树中的超参数

我们使用的这种决策树又叫做CART(Classification And Regression Tree)。它的特点就是在每一个节点上根据某一个维度d和某一个阈值v进行二分。scikit-learn中的决策树都是CART的实现。决策树并不仅仅只有CART这一种实现方式，还有一些如ID3、C4.5、C5.0都是一些其他方式来创建决策树的方法。

当我们建立好了一个决策树，它做预测的时间复杂度为O(logm)，m是样本个数。这棵决策树的高度为logm。一个新的样本就会根据这个决策树的高度一步一步做决策一直走到叶子节点。但是我们创建决策树，它的训练的时间复杂度为O(n*m*logm)，n就是特征数，这个时间复杂度其实是非常高的。首先这棵树是logm级别的，在每一层上，都要做n*m这么多次的尝试，我们在模拟决策树的划分的时候，要对每一个维度n，每一个样本m进行一个遍历，最终找到那个最佳的划分点，在哪个维度的哪个阈值上进行划分。

还有一个更大的问题就是决策树非常容易产生过拟合，这和KNN算法是一样的，事实上所有的非参数算法都容易产生过拟合。基于这些原因，我们实际在创建决策树的时候，必须对决策树进行剪枝：降低复杂度，解决过拟合。其实之前在鸢尾花数据集的例子中，我们一直在进行剪枝。创建这个决策树的时候，对最大的高度max_depth一直传的是2，就是限制了整棵树的高度，最多是2，这实际上就是一个剪枝手段。使用scikit-learn来创建决策树的时候，所谓的剪枝就是需要对一些参数进行平衡。我们来看看除了max_depth之外还有什么参数可以用于剪枝，它既降低了决策树训练的复杂度，同时大大减少了过拟合的现象。首先我们先画一个月亮的数据集。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets

if __name__ == "__main__":

    X, y = datasets.make_moons(noise=0.25, random_state=666)
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.show()

运行结果

现在我们使用决策树来看一下它的决策边界

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap

if __name__ == "__main__":

    X, y = datasets.make_moons(noise=0.25, random_state=666)
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier()
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    plot_decision_boundary(dt_clf, axis=[-1.5, 2.5, -1, 1.5])
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.show()

运行结果

这里需要说明的是，当我们的决策树不传入任何参数的时候，它是使用基尼系数来进行决策的，另外我们也没有传入层数，不做这个设定，决策树就将一直向下划分，直到划分到每一个节点的基尼系数都为0为止。对于上图中的形状显然是不规则的，产生了过拟合。现在我们在构建决策树的时候传入一些参数，看看这些参数是如何遏制过拟合的。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap

if __name__ == "__main__":

    X, y = datasets.make_moons(noise=0.25, random_state=666)
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier()
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(dt_clf, axis=[-1.5, 2.5, -1, 1.5])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()

    dt_clf2 = DecisionTreeClassifier(max_depth=2)
    dt_clf2.fit(X, y)
    plot_decision_boundary(dt_clf2, axis=[-1.5, 2.5, -1, 1.5])
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.show()

运行结果

很显然现在这个样子比之前规整了很多，不再有了过拟合。不会针对某几个特殊的样本点进行特殊的变化。不过此时又可能是欠拟合，我们继续调整参数。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap

if __name__ == "__main__":

    X, y = datasets.make_moons(noise=0.25, random_state=666)
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier()
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(dt_clf, axis=[-1.5, 2.5, -1, 1.5])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()

    dt_clf2 = DecisionTreeClassifier(max_depth=2)
    dt_clf2.fit(X, y)
    # plot_decision_boundary(dt_clf2, axis=[-1.5, 2.5, -1, 1.5])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()

    dt_clf3 = DecisionTreeClassifier(min_samples_split=10)
    dt_clf3.fit(X, y)
    plot_decision_boundary(dt_clf3, axis=[-1.5, 2.5, -1, 1.5])
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.show()

运行结果

这里的min_samples_split的意思就是对于一个节点来说，它至少要有多少个样本数据，我们才对这个节点继续进行拆分下去。上图这样一个决策边界，它显然过拟合的程度是非常低的。对于min_samples_split，我们给它的值调的越高，它就越不容易过拟合。但是把它的值调的太高，就会发生欠拟合的情况。在极端的情况下，如果min_samples_split的值超过样本数总量，那么我们的决策树根本就不需要划分了，此时肯定是一个欠拟合的。现在我们继续调整其他参数。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap

if __name__ == "__main__":

    X, y = datasets.make_moons(noise=0.25, random_state=666)
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier()
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(dt_clf, axis=[-1.5, 2.5, -1, 1.5])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()

    dt_clf2 = DecisionTreeClassifier(max_depth=2)
    dt_clf2.fit(X, y)
    # plot_decision_boundary(dt_clf2, axis=[-1.5, 2.5, -1, 1.5])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()

    dt_clf3 = DecisionTreeClassifier(min_samples_split=10)
    dt_clf3.fit(X, y)
    # plot_decision_boundary(dt_clf3, axis=[-1.5, 2.5, -1, 1.5])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()

    dt_clf4 = DecisionTreeClassifier(min_samples_leaf=6)
    dt_clf4.fit(X, y)
    plot_decision_boundary(dt_clf4, axis=[-1.5, 2.5, -1, 1.5])
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.show()

运行结果

这里的min_samples_leaf的意思就是对于叶子节点来说，它至少应该有几个样本。如果这个值为1就是说对于叶子节点来说至少应该有1个样本，在这种情况下容易过拟合。因为我们真正走这颗决策树走到了叶子节点才决定一个分类，但是其实我们决定的这个分类在这个叶子节点上只有1个样本，它只由这一个样本决定，显然会对某些特殊的样本点会非常的敏感。从上图的图像看，6这个数也有效的遏制了过拟合。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap

if __name__ == "__main__":

    X, y = datasets.make_moons(noise=0.25, random_state=666)
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier()
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(dt_clf, axis=[-1.5, 2.5, -1, 1.5])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()

    dt_clf2 = DecisionTreeClassifier(max_depth=2)
    dt_clf2.fit(X, y)
    # plot_decision_boundary(dt_clf2, axis=[-1.5, 2.5, -1, 1.5])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()

    dt_clf3 = DecisionTreeClassifier(min_samples_split=10)
    dt_clf3.fit(X, y)
    # plot_decision_boundary(dt_clf3, axis=[-1.5, 2.5, -1, 1.5])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()

    dt_clf4 = DecisionTreeClassifier(min_samples_leaf=6)
    dt_clf4.fit(X, y)
    # plot_decision_boundary(dt_clf4, axis=[-1.5, 2.5, -1, 1.5])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()

    dt_clf5 = DecisionTreeClassifier(max_leaf_nodes=4)
    dt_clf5.fit(X, y)
    plot_decision_boundary(dt_clf5, axis=[-1.5, 2.5, -1, 1.5])
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.show()

运行结果

这里的max_leaf_nodes的意思是最多有多少个叶子节点。对于决策树来说，叶子节点越多，决策树整体就越复杂，它就越有可能产生过拟合的情况。

我们在实际使用这些参数的时候也要注意，首先也要避免欠拟合的问题，其次这些参数之间可以互相组合，所以我们可以使用网格搜索的方式来看一看到底使用怎样的参数能得到比较好的结果。决策树本身我们用来分类也好，做回归也好，效果可能无论你调节这些参数，都不会特别的好。

决策树解决回归问题

当我们使用CART的方式将决策树建立出来之后，在每一个叶子节点都包含了若干个数据。如果这些数据它相应的输出值是类别的话，那么我们就可以在叶子节点中让数据进行投票，看哪个类别所包含的数据多，我们就把我们的样本进入到这个叶子节点相应的归为那个类别。如果它的输出是一个具体的数的话，那就是回归问题所解决的问题，那么相应的新的样本点来到这个决策树之后，经过决策树来到某一个叶子节点，就可以用在这个叶子节点中相应的这些数据输出值的平均值来作为一个预测的结果。我们使用波士顿房价数据来进行一个预测。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor

if __name__ == "__main__":

    boston = datasets.load_boston()
    X = boston.data
    y = boston.target
    X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=666)
    dt_reg = DecisionTreeRegressor()
    dt_reg.fit(X_train, y_train)
    print(dt_reg.score(X_test, y_test))
    print(dt_reg.score(X_train, y_train))

运行结果

0.5934966254524108
1.0

通过打印R方值，我们可以看到对于测试数据集的预测准确度不是一个很好的结果，只有59.3%。但是对于训练数据集的准确度却是100%。这显然是一种过拟合。这个例子也同时告诉我们，决策树是非常容易产生过拟合的。对于回归问题来说，决策树的参数和上一小节是完全一样的，我们可以通过调参来防止过拟合。之前在多项式回归中，我们有过这样的一个模型准确率和模型复杂度的关系图。

意思就是说模型越复杂，它对训练数据的模型准确率越高，拟合的越好。但是对于测试数据却是一个抛物线的形式，它会随着模型复杂度的升高，测试数据模型准确率达到一个峰值，再继续复杂下去就会开始下降。现在我们就用代码来绘制决策树的这两条曲线。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor
from sklearn.metrics import r2_score

if __name__ == "__main__":

    boston = datasets.load_boston()
    X = boston.data
    y = boston.target
    X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=666)
    dt_reg = DecisionTreeRegressor()
    dt_reg.fit(X_train, y_train)
    # print(dt_reg.score(X_test, y_test))
    # print(dt_reg.score(X_train, y_train))

    maxSampleLeaf = 506
    train_scores = []
    test_scores = []
    for i in range(1, maxSampleLeaf + 1):
        dt_reg = DecisionTreeRegressor(min_samples_leaf=i)
        dt_reg.fit(X_train, y_train)
        y_train_predict = dt_reg.predict(X_train)
        train_scores.append(r2_score(y_train, y_train_predict))
        test_scores.append(dt_reg.score(X_test, y_test))
    plt.plot([i for i in range(1, maxSampleLeaf + 1)], train_scores, label='train')
    plt.plot([i for i in range(1, maxSampleLeaf + 1)], test_scores, label='test')
    plt.xlim(maxSampleLeaf, 1)
    plt.legend()
    plt.show()

运行结果

min_samples_leaf的意思就是对于叶子节点来说，它至少应该有几个样本。我们知道该值越小越容易过拟合，模型复杂度越高，所以我们图形中的横轴是从大到小，最小到1来排序的。意思就是说我们的模型复杂度是从低到高的一个过程，其中训练数据集的模型准确率是不断上升的，而测试数据集也是在不断上升但是到了一个峰值就开始下降。这里这个下降可能看的不是特别明显，现在我们来调低min_samples_leaf的最大值。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor
from sklearn.metrics import r2_score

if __name__ == "__main__":

    boston = datasets.load_boston()
    X = boston.data
    y = boston.target
    X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=666)
    dt_reg = DecisionTreeRegressor()
    dt_reg.fit(X_train, y_train)
    # print(dt_reg.score(X_test, y_test))
    # print(dt_reg.score(X_train, y_train))

    maxSampleLeaf = 506
    train_scores = []
    test_scores = []
    for i in range(1, maxSampleLeaf + 1):
        dt_reg = DecisionTreeRegressor(min_samples_leaf=i)
        dt_reg.fit(X_train, y_train)
        y_train_predict = dt_reg.predict(X_train)
        train_scores.append(r2_score(y_train, y_train_predict))
        test_scores.append(dt_reg.score(X_test, y_test))
    # plt.plot([i for i in range(1, maxSampleLeaf + 1)], train_scores, label='train')
    # plt.plot([i for i in range(1, maxSampleLeaf + 1)], test_scores, label='test')
    # plt.xlim(maxSampleLeaf, 1)
    # plt.legend()
    # plt.show()

    maxSampleLeaf = 100
    train_scores = []
    test_scores = []
    for i in range(1, maxSampleLeaf + 1):
        dt_reg = DecisionTreeRegressor(min_samples_leaf=i)
        dt_reg.fit(X_train, y_train)
        y_train_predict = dt_reg.predict(X_train)
        train_scores.append(r2_score(y_train, y_train_predict))
        test_scores.append(dt_reg.score(X_test, y_test))
    plt.plot([i for i in range(1, maxSampleLeaf + 1)], train_scores, label='train')
    plt.plot([i for i in range(1, maxSampleLeaf + 1)], test_scores, label='test')
    plt.xlim(maxSampleLeaf, 1)
    plt.legend()
    plt.show()

运行结果

现在我们换一个参数来看这个图

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor
from sklearn.metrics import r2_score

if __name__ == "__main__":

    boston = datasets.load_boston()
    X = boston.data
    y = boston.target
    X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=666)
    dt_reg = DecisionTreeRegressor()
    dt_reg.fit(X_train, y_train)
    # print(dt_reg.score(X_test, y_test))
    # print(dt_reg.score(X_train, y_train))

    maxSampleLeaf = 506
    train_scores = []
    test_scores = []
    for i in range(1, maxSampleLeaf + 1):
        dt_reg = DecisionTreeRegressor(min_samples_leaf=i)
        dt_reg.fit(X_train, y_train)
        y_train_predict = dt_reg.predict(X_train)
        train_scores.append(r2_score(y_train, y_train_predict))
        test_scores.append(dt_reg.score(X_test, y_test))
    # plt.plot([i for i in range(1, maxSampleLeaf + 1)], train_scores, label='train')
    # plt.plot([i for i in range(1, maxSampleLeaf + 1)], test_scores, label='test')
    # plt.xlim(maxSampleLeaf, 1)
    # plt.legend()
    # plt.show()

    maxSampleLeaf = 100
    train_scores = []
    test_scores = []
    for i in range(1, maxSampleLeaf + 1):
        dt_reg = DecisionTreeRegressor(min_samples_leaf=i)
        dt_reg.fit(X_train, y_train)
        y_train_predict = dt_reg.predict(X_train)
        train_scores.append(r2_score(y_train, y_train_predict))
        test_scores.append(dt_reg.score(X_test, y_test))
    # plt.plot([i for i in range(1, maxSampleLeaf + 1)], train_scores, label='train')
    # plt.plot([i for i in range(1, maxSampleLeaf + 1)], test_scores, label='test')
    # plt.xlim(maxSampleLeaf, 1)
    # plt.legend()
    # plt.show()

    maxSamplesSplit = 300
    train_scores = []
    test_scores = []
    for i in range(2, maxSamplesSplit + 1):
        dt_reg = DecisionTreeRegressor(min_samples_split=i)
        dt_reg.fit(X_train, y_train)
        y_train_predict = dt_reg.predict(X_train)
        train_scores.append(r2_score(y_train, y_train_predict))
        test_scores.append(dt_reg.score(X_test, y_test))
    plt.plot([i for i in range(2, maxSamplesSplit + 1)], train_scores, label='train')
    plt.plot([i for i in range(2, maxSamplesSplit + 1)], test_scores, label='test')
    plt.xlim(maxSamplesSplit, 2)
    plt.legend()
    plt.show()

运行结果

min_samples_split的意思就是对于一个节点来说，它至少要有多少个样本数据，我们才对这个节点继续进行拆分下去。这个值越大，模型复杂度越简单；越小，模型复杂度越复杂，所以上图的模型复杂度也是从小到大。同样对于训练数据集的模型准确率也是不断上升的，但是对于测试数据集来说，也是不断上升，然后到达峰值然后开始下降。

决策树的局限性

从这个图中，我们会发现决策树的决策边界都是横平竖直的。反映在二维图像中，决策边界都一定是跟横轴或纵轴是平行的。这个道理也是很显然的，因为对于决策树来说，每一个都是在某一个维度上选择某一个阈值进行划分，小于这个阈值进入一棵子树，大于这个阈值，进入另外一棵子树。对于这样的决策边界显然是有局限性的。

对于这样的四个点，如果用决策树来进行分类的话，就是这个样子

首先决策树会将数据分成上下两部分，上半部分已经不可再分，它的信息熵或者基尼系数为0。对于下半部分又分成了两部分，最后就是上图的样子。然而对于这四个点来说，它合理的决策边界应该是一根斜线。

对于决策树来说，它是永远不会产生一根斜线这样的决策边界的。更严重的事情，假设我们的数据集是这个样子

这样的数据是非常容易区分的，使用决策树是这个样子

同样是这个分布，但是如果稍微有一些倾斜

此时当我们再使用决策树的话，那么划分结果很有可能就是这个样子

这个决策边界就是横平竖直的样子，这样一个决策边界很有可能是不对的，对比于在中间画一条斜线的决策边界，在两侧逼近无限远的时候，会进行大量的错误划分。另外决策树还有一个局限性就是对个别数据敏感。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap

if __name__ == "__main__":

    iris = datasets.load_iris()
    X = iris.data[:, 2:]
    y = iris.target
    tree_clf = DecisionTreeClassifier(max_depth=2, criterion='entropy', splitter='best')
    tree_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    plot_decision_boundary(tree_clf, axis=[0.5, 7.5, 0, 3])
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.scatter(X[y == 2, 0], X[y == 2, 1])
    plt.show()

运行结果

现在我们来找出一个点，把这个点给删除掉。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap

if __name__ == "__main__":

    iris = datasets.load_iris()
    X = iris.data[:, 2:]
    y = iris.target
    tree_clf = DecisionTreeClassifier(max_depth=2, criterion='entropy', splitter='best')
    tree_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 绘制不规则决策边界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(tree_clf, axis=[0.5, 7.5, 0, 3])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()

    X_new = np.delete(X, 138, axis=0)
    y_new = np.delete(y, 138)
    print(X_new.shape)
    print(y_new.shape)
    tree_clf2 = DecisionTreeClassifier(max_depth=2, criterion='entropy', splitter='best')
    tree_clf2.fit(X_new, y_new)
    plot_decision_boundary(tree_clf2, axis=[0.5, 7.5, 0, 3])
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.scatter(X[y == 2, 0], X[y == 2, 1])
    plt.show()

运行结果

在这里可以看到，我们只删除了其中的一个样本点，它的决策边界就变的跟之前完全不同了。这也再次应证了了对于决策树算法来说，对于个别的样本点它可能是很敏感的，其实这是所有的非参数学习的缺点，所以它高度依赖调参才能得到一个较好的模型。一般决策树更重要的应用是使用集成学习的方式来创建一种随机森林的算法，而随机森林算法可以得到非常好的学习结果。

集成学习和随机森林

什么是集成学习

我们之前已经学习了诸多的机器学习算法，对于每一种机器学习算法，它们考虑问题的方式都略微有所不同。所以对于同一个问题，不同的算法可能给出不同的结果。那么此时我们听哪种算法的结果呢？此时我们可以把多个算法集中起来，让不同的算法对同一个问题都进行一下运算，看看最终结果是怎样的，最终少数服从多数。这就是集成学习的思路。

scikit-learn为我们提供了一个方便的接口——Voting Classifier。它就是基于不同的算法进行投票的一种分类器。我们用代码来看一下这个集成学习的使用，先画出月亮的数据集

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets

if __name__ == "__main__":

    X, y = datasets.make_moons(n_samples=500, noise=0.3, random_state=42)
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.show()

运行结果

现在我们使用多种算法的分类决策，看看最终结果如何

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LogisticRegression
from sklearn.svm import SVC
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score

if __name__ == "__main__":

    X, y = datasets.make_moons(n_samples=500, noise=0.3, random_state=42)
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()
    X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)
    # 逻辑回归
    log_clf = LogisticRegression()
    log_clf.fit(X_train, y_train)
    print(log_clf.score(X_test, y_test))
    # 支撑向量机SVM
    svm_clf = SVC()
    svm_clf.fit(X_train, y_train)
    print(svm_clf.score(X_test, y_test))
    # 决策树
    dt_clf = DecisionTreeClassifier()
    dt_clf.fit(X_train, y_train)
    print(dt_clf.score(X_test, y_test))
    # 用三种模型进行预测
    y_predict1 = log_clf.predict(X_test)
    y_predict2 = svm_clf.predict(X_test)
    y_predict3 = dt_clf.predict(X_test)
    # 综合三个算法，少数服从多数得到分类预测值
    y_predict = np.array((y_predict1 + y_predict2 + y_predict3) >= 2, dtype='int')
    print(accuracy_score(y_test, y_predict))

运行结果

通过结果，我们可以看出通过三种模型计算出来的分类准确度经过投票，如果预测的结果至少两个一致，就确定该类型。最终结果达到了91.2%。现在我们来看看scikit-learn中为我们提供的集成学习接口

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LogisticRegression
from sklearn.svm import SVC
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
from sklearn.ensemble import VotingClassifier

if __name__ == "__main__":

    X, y = datasets.make_moons(n_samples=500, noise=0.3, random_state=42)
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()
    X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)
    # 逻辑回归
    log_clf = LogisticRegression()
    log_clf.fit(X_train, y_train)
    print(log_clf.score(X_test, y_test))
    # 支撑向量机SVM
    svm_clf = SVC()
    svm_clf.fit(X_train, y_train)
    print(svm_clf.score(X_test, y_test))
    # 决策树
    dt_clf = DecisionTreeClassifier()
    dt_clf.fit(X_train, y_train)
    print(dt_clf.score(X_test, y_test))
    # 用三种模型进行预测
    y_predict1 = log_clf.predict(X_test)
    y_predict2 = svm_clf.predict(X_test)
    y_predict3 = dt_clf.predict(X_test)
    # 综合三个算法，少数服从多数得到分类预测值
    y_predict = np.array((y_predict1 + y_predict2 + y_predict3) >= 2, dtype='int')
    print(accuracy_score(y_test, y_predict))
    # 使用scikit-learn提供的集成学习接口
    voting_clf = VotingClassifier(estimators=[
        ('log_clf', LogisticRegression()),
        ('svm_clf', SVC()),
        ('dt_clf', DecisionTreeClassifier())
    ], voting='hard')
    voting_clf.fit(X_train, y_train)
    print(voting_clf.score(X_test, y_test))

运行结果

通过代码，我们可以看到这个集成学习接口非常类似于之前的Pipeline，它把所有的学习算法放入其中，最终得到的就是投票后的分类准确度。

Soft Voting Classifier

在上一小节中，我们创建了一个VotingClassifier的时候，使用了一个参数——voting='hard'。这种少数服从多数的集成学习就被称为Hard Voting。但是还有一种更重要的方式，叫做Soft Voting。在很多情况下，少数服从多数并不是最合理的，更合理的投票，应该有权值。对于一个样本数据点，不同的模型可能会根据概率来分成不同的类别。

根据这五个模型，把一个数据分成了五个分类，根据概率的不同，模型1把这个数据肯定划分到了A类，模型2划分到了B类，模型3划分到了B类，模型4划分到了A类，模型5划分到了B类，根据Hard Voting，少数服从多数，有2个模型划分成了A类，有3个模型划分成了B类，我们的集成学习就应该把这个数据最终划分成B类。但是看数据，虽然只有两个模型把这个数据划分成了A类，但是这两个模型都是非常的确定的，概率都很高，99%和90%；相反看另外三个模型把这个数据划分成B类，但是概率都不够高，只有51%、60%、70%。而Soft Voting就是以概率作为权值来进行划分的。

通过加权平均的概率，我们能够看到，这个数据被分成A类的概率为61.6%，而被分成B类的概率只有38.4%。所以Soft Voting最终把结果划分为A类。

既然要以概率为权值，这就要求我们的机器学习算法都能得出分类的概率。对于逻辑回归自不必说，它本身就是以概率来进行划分的。

kNN算法，计算概率的方式就是看离新来的样本点最近的多数分类的样本点数量/离新来的样本最近的总样本数量，下面这个图的k=3,概率就是2/3=66.6%

决策树，计算概率的方式跟kNN是非常相似的，在一个叶子节点所包含的数据是含有多个数据的，此时该节点的基尼系数也好，信息熵也好，可能还不为0。换句话说在这个叶子节点中是包含有不同类的数据的，在这种情况下哪个类的数据量大，相应的我们就把样本点分类给哪一个类。概率就是叶子节点中占比例最大的分类数量/该叶子节点所有的数据点的数量。

支撑向量机SVM,它本身是没有考虑概率的，是计算一个margin的最大值。不过虽然如此，SVM算法依然可以使用一些方式来计算出概率。这样的方式的代价是更多的计算资源。具体略过计算方式，以后补充。在scikit-learn中，SVC类中有一个probability,它默认值是False，如果我们给它设为True的话，对于SVC类来说，它就可以估计出对于每一个样本分给某一个类的概率是多少，但是这样做的话会牺牲一定的计算时间。

这样对于这些算法，或者是直接或者是间接都可以计算出数据分给某一个类对应的概率是多少。有了这个概率，我们就可以相应的使用Soft Voting的方式。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LogisticRegression
from sklearn.svm import SVC
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
from sklearn.ensemble import VotingClassifier

if __name__ == "__main__":

    X, y = datasets.make_moons(n_samples=500, noise=0.3, random_state=42)
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.show()
    X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)
    # 逻辑回归
    log_clf = LogisticRegression()
    log_clf.fit(X_train, y_train)
    print(log_clf.score(X_test, y_test))
    # 支撑向量机SVM
    svm_clf = SVC()
    svm_clf.fit(X_train, y_train)
    print(svm_clf.score(X_test, y_test))
    # 决策树
    dt_clf = DecisionTreeClassifier()
    dt_clf.fit(X_train, y_train)
    print(dt_clf.score(X_test, y_test))
    # 用三种模型进行预测
    y_predict1 = log_clf.predict(X_test)
    y_predict2 = svm_clf.predict(X_test)
    y_predict3 = dt_clf.predict(X_test)
    # 综合三个算法，少数服从多数得到分类预测值
    y_predict = np.array((y_predict1 + y_predict2 + y_predict3) >= 2, dtype='int')
    print(accuracy_score(y_test, y_predict))
    # 使用scikit-learn提供的集成学习接口
    # 使用hard voting
    voting_clf = VotingClassifier(estimators=[
        ('log_clf', LogisticRegression()),
        ('svm_clf', SVC()),
        ('dt_clf', DecisionTreeClassifier())
    ], voting='hard')
    voting_clf.fit(X_train, y_train)
    print(voting_clf.score(X_test, y_test))
    # 使用soft voting
    voting_clf2 = VotingClassifier(estimators=[
        ('log_clf', LogisticRegression()),
        ('svm_clf', SVC(probability=True)),
        ('dt_clf', DecisionTreeClassifier(random_state=666))
    ], voting='soft')
    voting_clf2.fit(X_train, y_train)
    print(voting_clf2.score(X_test, y_test))

运行结果