决策树

发表于 2022-07-11 更新于 2023-01-28 分类于机器学习

使用C++和python实现ID3算法的决策树模型，另有使用Pythonsklearn.tree中的DecisionTreeClassifier调包与可视化实例。

决策树原理

决策树作为一种机器学习算法，将 “特征a值小于x，特征b值小于y……=>类别1 “的逻辑规则流纳入树状数据结构。这种算法的优点是可解释性强。银行可以向客户解释他们被拒绝贷款的原因：例如，客户没有房子、收入低于5000元。

我们可以确保在前面的例子中建立的树是最佳的。在其他分割条件下，产生的树会更深，即需要更多的 “问题 “来达到答案。
决策树构建的流行算法，如ID3或C4.5，其核心是信息增益的贪婪最大化原则：在每一步，算法选择在分裂时提供最大信息增益的变量。然后递归地重复这个过程，直到熵为零（或某个小值以考虑过拟合的情况）。不同的算法使用不同的启发式 “早期停止 “或 “截止”，以避免构建一个过度拟合的树。

def build(L):
    # 先创建节点
    create node t
    # 如果满足停止条件，则称`t`为所需的模型；否则寻找使熵最低的分割点`L`并对两侧建树
    if the stopping criterion is True:
        assign a predictive model to t
    else:
        Find the best binary split L = L_left + L_right
        t.left = build(L_left)
        t.right = build(L_right)
    return t

步骤如下：

自顶向下的贪婪搜索遍历可能的决策树空间构造决策树；
从“哪一个属性将在树的根节点被测试”开始；
使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性作为树的根结点测试。
然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是说，样例的该属性值对应的分支）之下。
重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。

熵

对于具有 N 个可能状态的系统，香农熵定义如下：

$$
\Large Entropy(S)= -\sum_{i=1}^{N}p_i \log_2{p_i},

其中 $p_i$ 是使系统处于第 $i$ 个状态的概率。这是物理学、信息论和其他领域中使用的一个非常重要的概念。熵可以描述为系统中的混沌程度：熵越高，系统的有序性越低，反之亦然。这将帮助我们进行有效的数据拆分。

当只有两种样例时，定义可写为：

$$
\Large Entropy(S)= -p_{pos} \log_2{p_{pos}} -p_{neg} \log_2{p_{neg}}

其C++实现如下：

//根据具体属性和值来计算熵  
double ComputeEntropy(vector <vector <string> > remain_state, string attribute, string value,bool ifparent){  
    vector<int> count (2,0);  
    unsigned int i,j;  
    bool done_flag = false;//哨兵值  
    for(j = 1; j < MAXLEN; j++){  
        if(done_flag) break;  
        if(!attribute_row[j].compare(attribute)){  
            for(i = 1; i < remain_state.size(); i++){  
                if((!ifparent&&!remain_state[i][j].compare(value)) || ifparent){//ifparent记录是否算父节点  
                    if(!remain_state[i][MAXLEN - 1].compare(yes)){  
                        count[0]++;  
                    }  
                    else count[1]++;  
                }  
            }  
            done_flag = true;  
        }  
    }  
    if(count[0] == 0 || count[1] == 0 ) return 0;//全部是正实例或者负实例  
    //具体计算熵 根据[+count[0],-count[1]],log2为底通过换底公式换成自然数底数  
    double sum = count[0] + count[1];  
    double entropy = -count[0]/sum*log(count[0]/sum)/log(2.0) - count[1]/sum*log(count[1]/sum)/log(2.0);  
    return entropy;  
}

信息增益

$$
\Large IG(Q) = S_O - \sum_{i=1}^{q}\frac{N_i}{N}S_i

分类问题中的评判标准

我们讨论了熵，但还有其他的评判标准：

基尼不确定性 Gini uncertainty（基尼杂质Gini impurity）： $G = 1 - \sum\limits_k (p_k)^2$. 最大化基尼不确定性可以最大化同一子树中同一类的对象对的数量。
Misclassification error (误判误差): $E = 1 - \max\limits_k p_k$

实践中几乎从不使用误判误差，基尼不确定性和信息增益效果类似。

对于二元分类，熵和基尼不确定性采用以下形式：

$ S = -p_+ \log_2{p_+} -p_- \log_2{p_-} = -p_+ \log_2{p_+} -(1 - p_{+}) \log_2{(1 - p_{+})};$

$ G = 1 - p_+^2 - p_-^2 = 1 - p_+^2 - (1 - p_+)^2 = 2p_+(1-p_+).$

其中$p_+$ 是对象具有标签 + 的概率。

如果我们根据 $p_+$ 绘制这两个函数，就能发现看到熵是基尼不确定性的两倍。因此实践中这两个标准几乎相同。

# 消除警告
import warnings
warnings.filterwarnings("ignore")

import numpy as np
import pandas as pd
import seaborn as sns

sns.set()
from matplotlib import pyplot as plt

%config InlineBackend.figure_format = 'retina'

plt.figure(figsize=(6, 4))
xx = np.linspace(0, 1, 50)
plt.plot(xx, [2 * x * (1 - x) for x in xx], label="gini")
plt.plot(xx, [4 * x * (1 - x) for x in xx], label="2*gini")
plt.plot(xx, [-x * np.log2(x) - (1 - x) * np.log2(1 - x) for x in xx], label="entropy")
plt.plot(xx, [1 - max(x, 1 - x) for x in xx], label="missclass")
plt.plot(xx, [2 - 2 * max(x, 1 - x) for x in xx], label="2*missclass")
plt.xlabel("p+")
plt.ylabel("criterion")
plt.title("Criteria of quality as a function of p+ (binary classification)")
plt.legend()

优缺点

优点：

可解释性强
能被可视化
训练和预测速度快
模型参数少
支持数字特征和分类特征都支持

缺点：

对数据中的噪声敏感；稍微修改训练集（如删除一个特征，添加一些对象），整个模型可能会发生变化
由决策树构建的分离边界有其局限性——它由垂直于坐标轴之一的超平面组成，在实践中，其质量不如其他一些方法。
会过拟合
不稳定。数据的微小变化能显著改变决策树。这个问题通过决策树集成来解决（下一次讨论）。
最优决策树搜索问题是 NP 完备的。在实践中使用了如贪婪搜索具有最大信息增益的特征，但并不能保证找到全局最优树。
难以应对数据中的缺失值。
模型只能内插不能外推（随机森林和树增强也如此）。决策树对特征空间外的对象预测结果相同。

实例

分类问题

为人造数据拟合决策树。先生成两类服从不同均值的正态分布样本。

数据生成

# 第一类
np.random.seed(17)
train_data = np.random.normal(size=(100, 2))
train_labels = np.zeros(100)

# 第二类
train_data = np.r_[train_data, np.random.normal(size=(100, 2), loc=2)]
train_labels = np.r_[train_labels, np.ones(100)]

数据可视化

此分类问题是建立边界来分隔两个类（红点和黄点）。一条直线太简单，为每个红点蜿蜒的复杂曲线太复杂，会导致我们在新样本上出错。直观地说，平滑的边界或一条直线或超平面可以很好地处理新数据。

plt.figure(figsize=(10, 8))
plt.scatter(
    train_data[:, 0],
    train_data[:, 1],
    c=train_labels,
    cmap="Set1",
    linewidth=1.5,
)
plt.plot(range(-2, 5), range(4, -3, -1));

模型搭建与训练

训练Sklearn决策树来区分这两个类，使用max_depth限制树的深度并可视化生成的分离边界。

from sklearn.tree import DecisionTreeClassifier

clf_tree = DecisionTreeClassifier(criterion="entropy", max_depth=3, random_state=17)

clf_tree.fit(train_data, train_labels)

# 画出边界
def get_grid(data):
    x_min, x_max = data[:, 0].min() - 1, data[:, 0].max() + 1
    y_min, y_max = data[:, 1].min() - 1, data[:, 1].max() + 1
    return np.meshgrid(np.arange(x_min, x_max, 0.01), np.arange(y_min, y_max, 0.01))

xx, yy = get_grid(train_data)
predicted = clf_tree.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.pcolormesh(xx, yy, predicted, cmap="Set1")
plt.scatter(train_data[:, 0], train_data[:, 1], c=train_labels,
    cmap="Set1", edgecolors="black", linewidth=1.5);

树模型可视化

这个代码很难在kaggle上跑通……直接放图

1	# !pip install pydotplus

import pydotplus
from sklearn.tree import export_graphviz


def tree_graph_to_png(tree, feature_names, png_file_to_save):
    """
    This requires GraphViz to be installed.  
    """
  
    tree_str = export_graphviz(
        tree, feature_names=feature_names, filled=True, out_file=None
    )
    graph = pydotplus.graph_from_dot_data(tree_str)
    graph.write_png(png_file_to_save)

  
tree_graph_to_png(
    tree=clf_tree,
    feature_names=["x1", "x2"],
    png_file_to_save="topic3_decision_tree1.png",
)

一开始有200个样本，每类100个。初始状态的熵最大，$S=1$。然后，通过将 $x_2$ 的值与 1.211 进行比较，将样本第一次分成 2 组，左右组的熵都随之减少。在上面这个可视化图片中，第一类的样本越多橙色越深，第二类的样本越多蓝色越深。一开始，两个类的样本数量相等，所以树的根节点是白色的。

理论上您可以构建一棵决策树直到每个叶子都只有一个实例，但这在构建单棵树时并不常见，因为它会过拟合或泛化能力降低，树底部将是一些不重要的特征。

以下两种情况可将树构建到最大深度：

随机森林。随机森林（一组树）平均单个树的输出。
修剪枝叶 (Pruning trees)。首先将树构造到最大深度,然后自下而上地通过比较具有和不具有该节点的树的质量来删除树的一些节点（使用交叉验证比较）。

下图是在过拟合树中构建的分割边界示例。

回归问题

预测数值型变量时，标准会发生变化：

Variance:

$$
\Large D = \frac{1}{\ell} \sum\limits_{i =1}^{\ell} (y_i - \frac{1}{\ell} \sum\limits_{j=1}^{\ell} y_j)^2,

we look for features that divide the training set in such a way that the values of the target feature in each leaf are roughly equal.其中$\ell$是一个叶子的样本数，$y_i$是目标变量的值。简单地说，我们通过最小化方差寻找的特征是以这样一种方式划分训练集，即目标特征在每个叶子中的值大致相等。

让我们生成一些服从 $f(x) = e^{-x ^ 2} + 1.5 * e^{-(x - 2) ^ 2}$ 的数据，并加上一些噪声。然后我们将使用这些数据和树所做的预测来训练一棵树。

n_train = 150
n_test = 1000
noise = 0.1


def f(x):
    x = x.ravel()
    return np.exp(-(x ** 2)) + 1.5 * np.exp(-((x - 2) ** 2))


def generate(n_samples, noise):
    X = np.random.rand(n_samples) * 10 - 5
    X = np.sort(X).ravel()
    y = (
        np.exp(-(X ** 2))
        + 1.5 * np.exp(-((X - 2) ** 2))
        + np.random.normal(0.0, noise, n_samples)
    )
    X = X.reshape((n_samples, 1))
    return X, y


X_train, y_train = generate(n_samples=n_train, noise=noise)
X_test, y_test = generate(n_samples=n_test, noise=noise)

from sklearn.tree import DecisionTreeRegressor

reg_tree = DecisionTreeRegressor(max_depth=5, random_state=17)

reg_tree.fit(X_train, y_train)
reg_tree_pred = reg_tree.predict(X_test)

plt.figure(figsize=(10, 6))
plt.plot(X_test, f(X_test), "b")
plt.scatter(X_train, y_train, c="b", s=20)
plt.plot(X_test, reg_tree_pred, "g", lw=2)
plt.xlim([-5, 5])
plt.title(
    "Decision tree regressor, MSE = %.2f"
    % (np.sum((y_test - reg_tree_pred) ** 2) / n_test)
)
plt.show()

不难发现，决策树用分段常数函数逼近数据集

使用决策树进行 MNIST 手写数字识别

加载数据

from sklearn.datasets import load_digits

data = load_digits()
X, y = data.data, data.target

X[0, :].reshape([8, 8])

MNIST 可视化

1
2
3

f, axes = plt.subplots(1, 4, sharey=True, figsize=(16, 6))
for i in range(4):
    axes[i].imshow(X[i, :].reshape([8, 8]), cmap="Greys");

数据集划分

1
2
3

X_train, X_holdout, y_train, y_holdout = train_test_split(
    X, y, test_size=0.3, random_state=17
)

模型建立与训练

1
2
3

tree = DecisionTreeClassifier(max_depth=5, random_state=17)

tree.fit(X_train, y_train)

模型预测与评定

1
2
3

tree_pred = tree.predict(X_holdout)

accuracy_score(y_holdout, tree_pred)

调参

tree_params = {
    "max_depth": [1, 2, 3, 5, 10, 20, 25, 30, 40, 50, 64],
    "max_features": [1, 2, 3, 5, 10, 20, 30, 50, 64],
}

tree_grid = GridSearchCV(tree, tree_params, cv=5, n_jobs=-1, verbose=True)

tree_grid.fit(X_train, y_train)

显示最优参数：

1	tree_grid.best_params_, tree_grid.best_score_ # ({'max_depth': 20, 'max_features': 64}, 0.844)

交叉验证

1
2
3

np.mean(
    cross_val_score(RandomForestClassifier(random_state=17), X_train, y_train, cv=5)
)  # 0.935

调库

sklearn.tree.DecisionTreeClassifier

sklearn.tree.DecisionTreeClassifier 类的主要参数有:

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, ccp_alpha=0.0)

max_depth – the maximum depth of the tree;
max_features - the maximum number of features with which to search for the best partition (this is necessary with a large number of features because it would be “expensive” to search for partitions for all features);
min_samples_leaf – the minimum number of samples in a leaf. This parameter prevents creating trees where any leaf would have only a few members.

Classifier可选参数

参数：

参数	说明
criterion	{“gini”, “entropy”}, default=”gini” 这个参数是用来选择使用何种方法度量树的切分质量的。当criterion取值为“gini”时采用基尼不纯度（Gini impurity）算法构造决策树，当criterion取值为 “entropy” 时采用信息增益（ information gain）算法构造决策树.
splitter	{“best”, “random”}, default=”best” 此参数决定了在每个节点上拆分策略的选择。支持的策略是“best” 选择“最佳拆分策略”， “random” 选择“最佳随机拆分策略”。
max_depth	int, default=None 树的最大深度。如果取值为None,则将所有节点展开，直到所有的叶子都是纯净的或者直到所有叶子都包含少于min_samples_split个样本。
min_samples_split	int or float, default=2 拆分内部节点所需的最少样本数： · 如果取值 int , 则将`min_samples_split`视为最小值。 · 如果为float，则`min_samples_split`是一个分数，而`ceil（min_samples_split * n_samples）`是每个拆分的最小样本数。 -注释在版本0.18中更改：增加了分数形式的浮点值。
min_samples_leaf	int or float, default=1 在叶节点处所需的最小样本数。仅在任何深度的分裂点在左分支和右分支中的每个分支上至少留有`min_samples_leaf`个训练样本时，才考虑。这可能具有平滑模型的效果，尤其是在回归中。 · 如果为int，则将`min_samples_leaf`视为最小值 · 如果为float，则`min_samples_leaf`是一个分数，而`ceil（min_samples_leaf * n_samples）`是每个节点的最小样本数。 - 注释：在版本0.18中发生了更改：添加了分数形式的浮点值。
min_weight_fraction_leaf	float, default=0.0 在所有叶节点处（所有输入样本）的权重总和中的最小加权分数。如果未提供`sample_weight`，则样本的权重相等。
max_features	int, float or {“auto”, “sqrt”, “log2”}, default=None 寻找最佳分割时要考虑的特征数量： - 如果为`int`，则在每次拆分时考虑`max_features`功能。 - 如果为`float`，则`max_features`是一个分数，而`int（max_features * n_features）`是每个分割处的特征数量。 - 如果为`“auto”`，则`max_features = sqrt（n_features）`。 - 如果为`“sqrt”`，则`max_features = sqrt（n_features）`。 - 如果为`“log2”`，则`max_features = log2（n_features）`。 - 如果为`None`，则`max_features = n_features`。注意：直到找到至少一个有效的节点样本分区，分割的搜索才会停止，即使它需要有效检查的特征数量多于`max_features`也是如此。
random_state	int, RandomState instance, default=None 此参数用来控制估计器的随机性。即使分割器设置为“最佳”，这些特征也总是在每个分割中随机排列。当`max_features <n_features`时，该算法将在每个拆分中随机选择`max_features`，然后再在其中找到最佳拆分。但是，即使`max_features = n_features`，找到的最佳分割也可能因不同的运行而有所不同。就是这种情况，如果标准的改进对于几个拆分而言是相同的，并且必须随机选择一个拆分。为了在拟合过程中获得确定性的行为，`random_state`必须固定为整数。有关详细信息，请参见词汇表。
max_leaf_nodes	int, default=None 优先以最佳方式生成带有`max_leaf_nodes`的树。最佳节点定义为不纯度的相对减少。如果为None，则叶节点数不受限制。
min_impurity_decrease	float, default=0.0 如果节点分裂会导致不纯度的减少大于或等于该值，则该节点将被分裂。加权不纯度减少方程如下： `N_t / N * (impurity - N_t_R / N_t * right_impurity` `- N_t_L / N_t * left_impurity)` 其中`N`是样本总数，`N_t`是当前节点上的样本数，`N_t_L`是左子节点中的样本数，`N_t_R`是右子节点中的样本数。如果给`sample_weight`传了值，则`N , N_t , N_t_R` 和 `N_t_L`均指加权总和。在 0.19 版新增。
min_impurity_split	float, default=0 树模型停止生长的阈值。如果节点的不纯度高于阈值，则该节点将分裂，否则为叶节点。警告：从版本0.19开始被弃用:`min_impurity_split`在0.19中被弃用，转而支持`min_impurity_decrease`。`min_impurity_split`的默认值在0.23中从`1e-7`更改为`0`，在0.25中将被删除。使用`min_impurity_decrease`代替。
class_weight	dict, list of dict or “balanced”, default=None 以`{class_label: weight}`的形式表示与类别关联的权重。如果取值None,所有分类的权重为1。对于多输出问题，可以按照y的列的顺序提供一个字典列表。注意多输出(包括多标签) ，应在其自己的字典中为每一列的每个类别定义权重。例如：对于四分类多标签问题，权重应为[{0：1、1：1：1]，{0：1、1：5}，{0：1、1：1：1}，{0：1、1： 1}]，而不是[{1：1}，{2：5}，{3：1}，{4：1}]。 “平衡”模式使用y的值自动将权重与输入数据中的类频率成反比地调整为`n_samples /（n_classes * np.bincount（y））`。对于多输出，y的每一列的权重将相乘。请注意，如果指定了`sample_weight`，则这些权重将与`sample_weight`（通过`fit`方法传递）相乘。
presort	deprecated, default=’deprecated’ 此参数已弃用，并将在v0.24中删除。注意：从0.22版开始已弃用。
ccp_alpha	non-negative float, default=0.0 用于最小化成本复杂性修剪的复杂性参数。将选择成本复杂度最大且小于ccp_alpha的子树。默认情况下，不执行修剪。有关详细信息，请参见最小成本复杂性修剪。

属性

属性	说明
classes_	ndarray of shape (n_classes,) or list of ndarray 类标签（单输出问题）或类标签数组的列表（多输出问题）。
feature_importances_	ndarray of shape (n_features,) 返回特征重要程度数据。
max_features_	int `max_features` 的推断值。
n_classes_	int or list of int 整数的类别数（单输出问题），或者一个包含所有类别数量的列表（多输出问题）。
n_features_	int 执行模型拟合训练时的特征数量。
n_outputs_	int 执行模型拟合训练时的输出数量。
tree_	Tree 基础的Tree对象。请通过 `help(sklearn.tree._tree.Tree)`查看Tree对象的属性，并了解决策树的结构以了解这些属性的基本用法。

Classifier使用示例

from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(random_state=0)
iris = load_iris()
cross_val_score(clf, iris.data, iris.target, cv=10)

sklearn.tree.DecisionTreeRegressor

class sklearn.tree.DecisionTreeRegressor(*, criterion='mse', 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, presort='deprecated', ccp_alpha=0.0)

criterion{“squared_error”, “friedman_mse”, “absolute_error”, “poisson”}, default=”squared_error”
The function to measure the quality of a split. Supported criteria are “squared_error” for the mean squared error, which is equal to variance reduction as feature selection criterion and minimizes the L2 loss using the mean of each terminal node, “friedman_mse”, which uses mean squared error with Friedman’s improvement score for potential splits, “absolute_error” for the mean absolute error, which minimizes the L1 loss using the median of each terminal node, and “poisson” which uses reduction in Poisson deviance to find splits.

Regressor可选参数

参数：

参数	说明
criterion	{“mse”, “friedman_mse”, “mae”}, default=”mse” 测量分割质量的函数。支持的标准是均方误差的“ mse”，等于方差减少作为特征选择标准，并使用每个终端节点的均值“ friedman_mse”来最小化L2损失，该方法使用均方误差和弗里德曼改进分数作为潜在值拆分，并使用“ mae”表示平均绝对误差，使用每个终端节点的中值将L1损失最小化。版本0.18 中的新功能：平均绝对误差（MAE）标准。
splitter	{“best”, “random”}, default=”best” 用于在每个节点上选择拆分的策略。支持的策略是“best”选择最佳拆分，“random”选择最佳随机拆分。
max_depth	int, default=None 树的最大深度。如果为None，则将节点展开，直到所有叶子都是纯净的，或者直到所有叶子都包含少于min_samples_split个样本。
min_samples_split	int or float, default=2 拆分内部节点所需的最少样本数： - 如果为int，则认为`min_samples_split`是最小值。 - 如果为float，`min_samples_split`则为分数， `ceil(min_samples_split * n_samples)`是每个拆分的最小样本数。在版本0.18中更改：添加了分数的浮点值。
min_samples_leaf	int or float, default=1 在叶节点处需要的最小样本数。任何深度的分割点只有在左、右分支中至少留下min_samples_leaf训练样本时才会被考虑。这可能具有平滑模型的效果，尤其是在回归中。
min_weight_fraction_leaf	float, default=0.0 在所有叶节点处（所有输入样本）的权重总和中的最小加权分数。如果未提供sample_weight，则样本的权重相等。
max_features	int, float or {“auto”, “sqrt”, “log2”}, default=None 寻找最佳分割时要考虑的特征数量： - 如果为int，则`max_features`在每个分割处考虑特征。 - 如果为float，`max_features`则为小数，并且`int(max_features * n_features)`是在每次拆分时考虑要素。 - 如果为“auto”，则为`max_features=n_features`。 - 如果是“ sqrt”，则`max_features=sqrt(n_features)`。 - 如果为“ log2”，则为`max_features=log2(n_features)`。 - 如果为”None“，则`max_features=n_features`。注：直到找到至少一个有效的节点样本分区，分割的搜索才会停止，即使它需要有效检查多个`max_features`要素也是如此。
random_state	int, RandomState instance, default=None 控制估算器的随机性。即使`splitter`设置为`"best"`，这些特性总是在每次拆分时随机排列。当`max_features < n_features`时,算法将在每个分割处随机选择`max_features`特征，然后在其中找到最佳分割。即使`max_features=n_features`，但最佳分割可能因不同的运行而有所不同，这种情况下，如果标准的改进对于多个分割是相同的，必须随机选择一个分割。为了在拟合过程中获得确定性行为，必须将其固定为整数。有关详细信息，请参见词汇表。
max_leaf_nodes	int, default=None 以最好的方式种植一棵树，树上有`max_l`节点。最佳节点定义为杂质相对减少。如果没有，则叶节点的数量不受限制。
min_impurity_decrease	float, default=0.0 如果节点分裂会导致杂质的减少大于或等于该值，则该节点将被分裂。加权杂质减少方程如下： `N_t / N * (impurity - N_t_R / N_t * right_impurity` `N_t_L / N_t * left_impurity)` 其中，`N`是样本总数，`N_t`是当前节点的样本数，`N_t_L`是左子节点中的样本数，`N_t_R`是右子节点中的样本数。 `N`，`N_t`，`N_t_R`和`N_t_L`都指的是加权和，如果`sample_weight`可以通过。版本0.19中的新功能。
min_impurity_split	float, (default=0) 尽早停止树的生长的阈值。如果节点的杂质高于阈值，则该节点将分裂，否则为叶。从版本0.19 `min_impurity_split`开始不推荐使用：在版本0.19中不再推荐使用 `min_impurity_decrease`。 `min_impurity_split`的默认值在0.23中从1e-7更改为0，将会在0.25中删除。使用`min_impurity_decrease`将其代替。
presort	deprecated, default=’deprecated’ 此参数已弃用，并将在v0.24中删除。 `从0.22版开始不推荐使用。`
ccp_alpha	non-negative float, default=0.0 用于最小代价复杂度修剪的复杂度参数。选择代价复杂度最大且小于`ccp_alpha`的子树。默认情况下，不执行修剪。有关详细信息，请参见最小成本复杂性修剪。 0.22版中的新功能。

属性：

属性	说明
feature_importances_	ndarray of shape (n_features,) 返特征的重要性。
max_features_	int max_features的推断值。
n_features_	int `fit`执行时的特征数量。
n_outputs_	int `fit`执行时的输出数量。
tree_	Tree 基础的Tree对象。有关树对象的属性请参阅`help(sklearn.tree._tree.Tree)`，有关这些属性的基本用法，请参阅决策树结构。

Regressor使用示例

from sklearn.datasets import load_diabetes
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeRegressor
X, y = load_diabetes(return_X_y=True)
regressor = DecisionTreeRegressor(random_state=0)
cross_val_score(regressor, X, y, cv=10)

实现

ID3 实现

//计算信息增益，DFS构建决策树  
//current_node为当前的节点  
//remain_state为剩余待分类的样例  
//remian_attribute为剩余还没有考虑的属性  
//返回根结点指针  
Node * BulidDecisionTreeDFS(Node * p, vector <vector <string> > remain_state, vector <string> remain_attribute){  
    //if(remain_state.size() > 0){  
        //printv(remain_state);  
    //}  
    if (p == NULL)  
        p = new Node();  
    //先看搜索到树叶的情况  
    if (AllTheSameLabel(remain_state, yes)){  
        p->attribute = yes;  
        return p;  
    }  
    if(remain_attribute.size() == 0){//所有的属性均已经考虑完了,还没有分尽  
        string label = MostCommonLabel(remain_state);  
        p->attribute = label;  
        return p;  
    }  
  
    double max_gain = 0, temp_gain;  
    vector <string>::iterator max_it;  
    vector <string>::iterator it1;  
    for(it1 = remain_attribute.begin(); it1 < remain_attribute.end(); it1++){  
        temp_gain = ComputeGain(remain_state, (*it1));  
        if(temp_gain > max_gain) {  
            max_gain = temp_gain;  
            max_it = it1;  
        }  
    }  
    //下面根据max_it指向的属性来划分当前样例，更新样例集和属性集  
    vector <string> new_attribute;  
    vector <vector <string> > new_state;  
    for(vector <string>::iterator it2 = remain_attribute.begin(); it2 < remain_attribute.end(); it2++){  
        if((*it2).compare(*max_it)) new_attribute.push_back(*it2);  
    }  
    //确定了最佳划分属性，注意保存  
    p->attribute = *max_it;  
    vector <string> values = map_attribute_values[*max_it];  
    int attribue_num = FindAttriNumByName(*max_it);  
    new_state.push_back(attribute_row);  
    for(vector <string>::iterator it3 = values.begin(); it3 < values.end(); it3++){  
        for(unsigned int i = 1; i < remain_state.size(); i++){  
            if(!remain_state[i][attribue_num].compare(*it3)){  
                new_state.push_back(remain_state[i]);  
            }  
        }  
        Node * new_node = new Node();  
        new_node->arrived_value = *it3;  
        if(new_state.size() == 0){//表示当前没有这个分支的样例，当前的new_node为叶子节点  
            new_node->attribute = MostCommonLabel(remain_state);  
        }  
        else   
            BulidDecisionTreeDFS(new_node, new_state, new_attribute);  
        //递归函数返回时即回溯时需要1 将新结点加入父节点孩子容器 2清除new_state容器  
        p->childs.push_back(new_node);  
        new_state.erase(new_state.begin()+1,new_state.end());//注意先清空new_state中的前一个取值的样例，准备遍历下一个取值样例  
    }  
    return p;  
}

#coding=utf-8
#Author:Dodo
#Date:2018-11-21
#Email:lvtengchao@pku.edu.cn

'''
数据集：Mnist
训练集数量：60000
测试集数量：10000
------------------------------
运行结果：ID3(未剪枝)
    正确率：85.9%
    运行时长：356s
'''

import time
import numpy as np

def loadData(fileName):
    '''
    加载文件
    :param fileName:要加载的文件路径
    :return: 数据集和标签集
    '''
    #存放数据及标记
    dataArr = []; labelArr = []
    #读取文件
    fr = open(fileName)
    #遍历文件中的每一行
    for line in fr.readlines():
        #获取当前行，并按“，”切割成字段放入列表中
        #strip：去掉每行字符串首尾指定的字符（默认空格或换行符）
        #split：按照指定的字符将字符串切割成每个字段，返回列表形式
        curLine = line.strip().split(',')
        #将每行中除标记外的数据放入数据集中（curLine[0]为标记信息）
        #在放入的同时将原先字符串形式的数据转换为整型
        #此外将数据进行了二值化处理，大于128的转换成1，小于的转换成0，方便后续计算
        dataArr.append([int(int(num) > 128) for num in curLine[1:]])
        #将标记信息放入标记集中
        #放入的同时将标记转换为整型
        labelArr.append(int(curLine[0]))
    #返回数据集和标记
    return dataArr, labelArr

def majorClass(labelArr):
    '''
    找到当前标签集中占数目最大的标签
    :param labelArr: 标签集
    :return: 最大的标签
    '''
    #建立字典，用于不同类别的标签技术
    classDict = {}
    #遍历所有标签
    for i in range(len(labelArr)):
        #当第一次遇到A标签时，字典内还没有A标签，这时候直接幅值加1是错误的，
        #所以需要判断字典中是否有该键，没有则创建，有就直接自增
        if labelArr[i] in classDict.keys():
            # 若在字典中存在该标签，则直接加1
            classDict[labelArr[i]] += 1
        else:
            #若无该标签，设初值为1，表示出现了1次了
            classDict[labelArr[i]] = 1
    #对字典依据值进行降序排序
    classSort = sorted(classDict.items(), key=lambda x: x[1], reverse=True)
    #返回最大一项的标签，即占数目最多的标签
    return classSort[0][0]

def calc_H_D(trainLabelArr):
    '''
    计算数据集D的经验熵，参考公式5.7 经验熵的计算
    :param trainLabelArr:当前数据集的标签集
    :return: 经验熵
    '''
    #初始化为0
    H_D = 0
    #将当前所有标签放入集合中，这样只要有的标签都会在集合中出现，且出现一次。
    #遍历该集合就可以遍历所有出现过的标记并计算其Ck
    #这么做有一个很重要的原因：首先假设一个背景，当前标签集中有一些标记已经没有了，比如说标签集中
    #没有0（这是很正常的，说明当前分支不存在这个标签）。 式5.7中有一项Ck，那按照式中的针对不同标签k
    #计算Cl和D并求和时，由于没有0，那么C0=0，此时C0/D0=0,log2(C0/D0) = log2(0)，事实上0并不在log的
    #定义区间内，出现了问题
    #所以使用集合的方式先知道当前标签中都出现了那些标签，随后对每个标签进行计算，如果没出现的标签那一项就
    #不在经验熵中出现（未参与，对经验熵无影响），保证log的计算能一直有定义
    trainLabelSet = set([label for label in trainLabelArr])
    #遍历每一个出现过的标签
    for i in trainLabelSet:
        #计算|Ck|/|D|
        #trainLabelArr == i：当前标签集中为该标签的的位置
        #例如a = [1, 0, 0, 1], c = (a == 1): c == [True, false, false, True]
        #trainLabelArr[trainLabelArr == i]：获得为指定标签的样本
        #trainLabelArr[trainLabelArr == i].size：获得为指定标签的样本的大小，即标签为i的样本
        #数量，就是|Ck|
        #trainLabelArr.size：整个标签集的数量（也就是样本集的数量），即|D|
        p = trainLabelArr[trainLabelArr == i].size / trainLabelArr.size
        #对经验熵的每一项累加求和
        H_D += -1 * p * np.log2(p)

    #返回经验熵
    return H_D

def calcH_D_A(trainDataArr_DevFeature, trainLabelArr):
    '''
    计算经验条件熵
    :param trainDataArr_DevFeature:切割后只有feature那列数据的数组
    :param trainLabelArr: 标签集数组
    :return: 经验条件熵
    '''
    #初始为0
    H_D_A = 0
    #在featue那列放入集合中，是为了根据集合中的数目知道该feature目前可取值数目是多少
    trainDataSet = set([label for label in trainDataArr_DevFeature])

    #对于每一个特征取值遍历计算条件经验熵的每一项
    for i in trainDataSet:
        #计算H(D|A)
        #trainDataArr_DevFeature[trainDataArr_DevFeature == i].size / trainDataArr_DevFeature.size:|Di| / |D|
        #calc_H_D(trainLabelArr[trainDataArr_DevFeature == i]):H(Di)
        H_D_A += trainDataArr_DevFeature[trainDataArr_DevFeature == i].size / trainDataArr_DevFeature.size \
                * calc_H_D(trainLabelArr[trainDataArr_DevFeature == i])
    #返回得出的条件经验熵
    return H_D_A

def calcBestFeature(trainDataList, trainLabelList):
    '''
    计算信息增益最大的特征
    :param trainDataList: 当前数据集
    :param trainLabelList: 当前标签集
    :return: 信息增益最大的特征及最大信息增益值
    '''
    #将数据集和标签集转换为数组形式
    trainDataArr = np.array(trainDataList)
    trainLabelArr = np.array(trainLabelList)

    #获取当前特征数目，也就是数据集的横轴大小
    featureNum = trainDataArr.shape[1]

    #初始化最大信息增益
    maxG_D_A = -1
    #初始化最大信息增益的特征
    maxFeature = -1
    
    #“5.2.2 信息增益”中“算法5.1（信息增益的算法）”第一步：
    #1.计算数据集D的经验熵H(D)
    H_D = calc_H_D(trainLabelArr)
    #对每一个特征进行遍历计算
    for feature in range(featureNum):
        #2.计算条件经验熵H(D|A)
        #由于条件经验熵的计算过程中只涉及到标签以及当前特征，为了提高运算速度（全部样本
        #做成的矩阵运算速度太慢，需要剔除不需要的部分），将数据集矩阵进行切割
        #数据集在初始时刻是一个Arr = 60000*784的矩阵，针对当前要计算的feature，在训练集中切割下
        #Arr[:, feature]这么一条来，因为后续计算中数据集中只用到这个（没明白的跟着算一遍例5.2）
        #trainDataArr[:, feature]:在数据集中切割下这么一条
        #trainDataArr[:, feature].flat：将这么一条转换成竖着的列表
        #np.array(trainDataArr[:, feature].flat)：再转换成一条竖着的矩阵，大小为60000*1（只是初始是
        #这么大，运行过程中是依据当前数据集大小动态变的）
        trainDataArr_DevideByFeature = np.array(trainDataArr[:, feature].flat)
        #3.计算信息增益G(D|A)    G(D|A) = H(D) - H(D | A)
        G_D_A = H_D - calcH_D_A(trainDataArr_DevideByFeature, trainLabelArr)
        #不断更新最大的信息增益以及对应的feature
        if G_D_A > maxG_D_A:
            maxG_D_A = G_D_A
            maxFeature = feature
    return maxFeature, maxG_D_A


def getSubDataArr(trainDataArr, trainLabelArr, A, a):
    '''
    更新数据集和标签集
    :param trainDataArr:要更新的数据集
    :param trainLabelArr: 要更新的标签集
    :param A: 要去除的特征索引
    :param a: 当data[A]== a时，说明该行样本时要保留的
    :return: 新的数据集和标签集
    '''
    #返回的数据集
    retDataArr = []
    #返回的标签集
    retLabelArr = []
    #对当前数据的每一个样本进行遍历
    for i in range(len(trainDataArr)):
        #如果当前样本的特征为指定特征值a
        if trainDataArr[i][A] == a:
            #那么将该样本的第A个特征切割掉，放入返回的数据集中
            retDataArr.append(trainDataArr[i][0:A] + trainDataArr[i][A+1:])
            #将该样本的标签放入返回标签集中
            retLabelArr.append(trainLabelArr[i])
    #返回新的数据集和标签集
    return retDataArr, retLabelArr

def createTree(*dataSet):
    '''
    递归创建决策树
    :param dataSet:(trainDataList， trainLabelList) <<-- 元祖形式
    :return:新的子节点或该叶子节点的值
    '''
    #设置Epsilon，“5.3.1 ID3算法”第4步提到需要将信息增益与阈值Epsilon比较，若小于则
    #直接处理后返回T
    #该值的大小在设置上并未考虑太多，观察到信息增益前期在运行中为0.3左右，所以设置了0.1
    Epsilon = 0.1
    #从参数中获取trainDataList和trainLabelList
    #之所以使用元祖作为参数，是由于后续递归调用时直数据集需要对某个特征进行切割，在函数递归
    #调用上直接将切割函数的返回值放入递归调用中，而函数的返回值形式是元祖的，等看到这个函数
    #的底部就会明白了，这样子的用处就是写程序的时候简洁一点，方便一点
    trainDataList = dataSet[0][0]
    trainLabelList = dataSet[0][1]
    #打印信息：开始一个子节点创建，打印当前特征向量数目及当前剩余样本数目
    print('start a node', len(trainDataList[0]), len(trainLabelList))

    #将标签放入一个字典中，当前样本有多少类，在字典中就会有多少项
    #也相当于去重，多次出现的标签就留一次。举个例子，假如处理结束后字典的长度为1，那说明所有的样本
    #都是同一个标签，那就可以直接返回该标签了，不需要再生成子节点了。
    classDict = {i for i in trainLabelList}
    #如果D中所有实例属于同一类Ck，则置T为单节点数，并将Ck作为该节点的类，返回T
    #即若所有样本的标签一致，也就不需要再分化，返回标记作为该节点的值，返回后这就是一个叶子节点
    if len(classDict) == 1:
        #因为所有样本都是一致的，在标签集中随便拿一个标签返回都行，这里用的第0个（因为你并不知道
        #当前标签集的长度是多少，但运行中所有标签只要有长度都会有第0位。
        return trainLabelList[0]

    #如果A为空集，则置T为单节点数，并将D中实例数最大的类Ck作为该节点的类，返回T
    #即如果已经没有特征可以用来再分化了，就返回占大多数的类别
    if len(trainDataList[0]) == 0:
        #返回当前标签集中占数目最大的标签
        return majorClass(trainLabelList)

    #否则，按式5.10计算A中个特征值的信息增益，选择信息增益最大的特征Ag
    Ag, EpsilonGet = calcBestFeature(trainDataList, trainLabelList)

    #如果Ag的信息增益比小于阈值Epsilon，则置T为单节点树，并将D中实例数最大的类Ck
    #作为该节点的类，返回T
    if EpsilonGet < Epsilon:
        return majorClass(trainLabelList)

    #否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的
    # 类作为标记，构建子节点，由节点及其子节点构成树T，返回T
    treeDict = {Ag:{}}
    #特征值为0时，进入0分支
    #getSubDataArr(trainDataList, trainLabelList, Ag, 0)：在当前数据集中切割当前feature，返回新的数据集和标签集
    treeDict[Ag][0] = createTree(getSubDataArr(trainDataList, trainLabelList, Ag, 0))
    treeDict[Ag][1] = createTree(getSubDataArr(trainDataList, trainLabelList, Ag, 1))

    return treeDict

def predict(testDataList, tree):
    '''
    预测标签
    :param testDataList:样本
    :param tree: 决策树
    :return: 预测结果
    '''
    # treeDict = copy.deepcopy(tree)

    #死循环，直到找到一个有效地分类
    while True:
        #因为有时候当前字典只有一个节点
        #例如{73: {0: {74:6}}}看起来节点很多，但是对于字典的最顶层来说，只有73一个key，其余都是value
        #若还是采用for来读取的话不太合适，所以使用下行这种方式读取key和value
        (key, value), = tree.items()
        #如果当前的value是字典，说明还需要遍历下去
        if type(tree[key]).__name__ == 'dict':
            #获取目前所在节点的feature值，需要在样本中删除该feature
            #因为在创建树的过程中，feature的索引值永远是对于当时剩余的feature来设置的
            #所以需要不断地删除已经用掉的特征，保证索引相对位置的一致性
            dataVal = testDataList[key]
            del testDataList[key]
            #将tree更新为其子节点的字典
            tree = value[dataVal]
            #如果当前节点的子节点的值是int，就直接返回该int值
            #例如{403: {0: 7, 1: {297:7}}，dataVal=0
            #此时上一行tree = value[dataVal]，将tree定位到了7，而7不再是一个字典了，
            #这里就可以直接返回7了，如果tree = value[1]，那就是一个新的子节点，需要继续遍历下去
            if type(tree).__name__ == 'int':
                #返回该节点值，也就是分类值
                return tree
        else:
            #如果当前value不是字典，那就返回分类值
            return value

def model_test(testDataList, testLabelList, tree):
    '''
    测试准确率
    :param testDataList:待测试数据集
    :param testLabelList: 待测试标签集
    :param tree: 训练集生成的树
    :return: 准确率
    '''
    #错误次数计数
    errorCnt = 0
    #遍历测试集中每一个测试样本
    for i in range(len(testDataList)):
        #判断预测与标签中结果是否一致
        if testLabelList[i] != predict(testDataList[i], tree):
            errorCnt += 1
    #返回准确率
    return 1 - errorCnt / len(testDataList)

if __name__ == '__main__':
    #开始时间
    start = time.time()

    # 获取训练集
    trainDataList, trainLabelList = loadData('../Mnist/mnist_train.csv')
    # 获取测试集
    testDataList, testLabelList = loadData('../Mnist/mnist_test.csv')

    #创建决策树
    print('start create tree')
    tree = createTree((trainDataList, trainLabelList))
    print('tree is:', tree)

    #测试准确率
    print('start test')
    accur = model_test(testDataList, testLabelList, tree)
    print('the accur is:', accur)

    #结束时间
    end = time.time()
    print('time span:', end - start)

C4.5

Function C4.5(R:包含连续属性的无类别属性集合,C:类别属性,S:训练集)
/*返回一棵决策树*/
Begin
   If S为空,返回一个值为Failure的单个节点;
   If S是由相同类别属性值的记录组成,
   If R为空,则返回一个单节点,其值为在S的记录中找出的频率最高的类别属性值;
   [注意未出现错误则意味着是不适合分类的记录]；
  For 所有的属性R(Ri) Do
        If 属性Ri为连续属性，则
     Begin
           将Ri的最小值赋给A1：
        将Rm的最大值赋给Am；/*m值手工设置*/
           For j From 2 To m-1 Do Aj=A1+j*(A1Am)/m;
           将Ri点的基于{< =Aj,>Aj}的最大信息增益属性(Ri,S)赋给A；
     End；
  将R中属性之间具有最大信息增益的属性(D,S)赋给D;
   将属性D的值赋给{dj/j=1,2...m}；
  将分别由对应于D的值为dj的记录组成的S的子集赋给{sj/j=1,2...m};
   返回一棵树，其根标记为D;树枝标记为d1,d2...dm;
   再分别构造以下树:
   C4.5(R-{D},C,S1),C4.5(R-{D},C,S2)...C4.5(R-{D},C,Sm);
End C4.5

资源

scikit-learn 决策树指南
Decision trees and k Nearest Neighbors are covered practically in every ML book. We recommend “Pattern Recognition and Machine Learning” (C. Bishop) and “Machine Learning: A Probabilistic Perspective” (K. Murphy).
The book “Machine Learning in Action” (P. Harrington) will walk you through implementations of classic ML algorithms in pure Python.
Scipy 2017 scikit-learn tutorial by Alex Gramfort and Andreas Mueller.
Implementations of many ML algorithms. Good to search for decision trees and k-NN.

参考

mlcourse.ai Author: Yury Kashnitsky. Translated and edited by Christina Butsko, Gleb Filatov, and Yuanyuan Pao.
CSDN上的博客
Scikit-learn 文档
中文文档和中文教程