理论

Hunt算法是许多决策树算法的基础，包括ID3、C4.5和CART
增益率（gain ratio）：如决策树算法C4.5，采用增益率的划分标准来评估划分
树剪枝tree-pruning：决策树过大容易过拟合overfitting，通过树剪枝（修剪初始决策树的分支），减小决策树的规模，提高决策树的泛化能力
分类模型的误差：训练误差（training error）、泛化误差（generalization error）。一个好的分类模型不仅要能够很好地拟合训练数据，还需对未知样本进行准确的分类。
注意：决策树很小时，训练和检验误差都很大——模型拟合不足（model underfitting），这是因为模型尚未学习到数据的真实结构。随着决策树中结点数增加，训练和检验误差都降低。然而，一旦树的规模太大，即使训练误差还在继续降低，但检验误差开始增大——模型过分拟合（model overfitting）。
奥卡姆剃刀：给定两个具有相同泛化误差的模型，较简单的模型比较复杂的模型更可取。
交叉验证：二折交叉验证：数据分为两个相同大小的子集，首先选择其一作为训练集，另一个作为检验集，然后交换两个集合的角色。k二折交叉验证：数据分为k个相同大小的子集，选择其一作为检验集，其余全作为训练集，重复k次，使得每份数据都用于检验恰好一次。
k二折交叉验证的特殊情况：留一leave out方法：k=N（数据集大小）

实践（决策树分类）

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from matplotlib.font_manager import FontProperties
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
plt.show()
plt.rcParams['font.sans-serif']=['SimHei']

############获取数据############
iris_data = datasets.load_iris()
X = iris_data.data[:, [2, 3]]
y = iris_data.target
label_list = ['山鸢尾', '杂色鸢尾', '维吉尼亚鸢尾']

############构建决策边界############
def plot_decision_regions(X, y, classifier=None):
    marker_list = ['o', 'x', 's']
    color_list = ['r', 'b', 'g']
    cmap = ListedColormap(color_list[:len(np.unique(y))]) # 背景色

    # 生成网格点坐标矩阵
    x1_min, x1_max = X[:, 0].min()-1, X[:, 0].max()+1
    x2_min, x2_max = X[:, 1].min()-1, X[:, 1].max()+1
    t1 = np.linspace(x1_min, x1_max, 666)
    t2 = np.linspace(x2_min, x2_max, 666)
    x1, x2 = np.meshgrid(t1, t2) # 生成网格点坐标矩阵
    y_hat = classifier.predict(np.array([x1.ravel(), x2.ravel()]).T)
    y_hat = y_hat.reshape(x1.shape)
    plt.contourf(x1, x2, y_hat, alpha=0.2, cmap=cmap)   # 绘制轮廓等高线  alpha参数设置透明度
    plt.xlim(x1_min, x1_max)
    plt.ylim(x2_min, x2_max)

    # plot class samples
    for ind, clas in enumerate(np.unique(y)):
        plt.scatter(X[y == clas, 0], X[y == clas, 1], alpha=0.8, s=50,
                    c=color_list[ind], marker=marker_list[ind], label=label_list[clas])


############训练模型############
tree = DecisionTreeClassifier(criterion='gini', max_depth=5, random_state=1)
tree.fit(X, y)

############可视化############
plot_decision_regions(X, y, classifier=tree)
plt.xlabel('花瓣长度（cm）')
plt.ylabel('花瓣宽度（cm）')
plt.legend()
plt.show()