• D 是某个数据集（或某个节点上的样本）
• k 是类别数量（如“稳定”“不稳定”就是2类）
• (p_i) 是第i类在该数据集中的比例

比如某节点：

样本数samples=5，类别value=[1,4]

[p_1=frac{1}{5}，p_2=frac{4}{5} ]

[Entropy(D) = - (frac{1}{5}⋅log_2frac{1}{5}+frac{4}{5}⋅log_2frac{4}{5}) = 0.7215 ]

熵越小，那就代表了该节点不确定性越低，如果该节点的上为0，那就不会继续分裂下去产生子节点；而不确定性越高的节点，就会继续分裂产生叶子节点

信息增益

是决策树中用于选择划分特征的核心指标。它本质上衡量的是：“使用某个特征进行划分后，数据的不确定性减少了多少”

信息增益=原始熵−加权熵

比如以下节点，想要计算出信息增益

原始熵我们已经有了，那就是0.994，需要计算加权熵

[加权熵=frac{9}{11}⋅0.991+frac{2}{11}⋅0=0.811 ]

[原始熵=0.994−0.811= 0.183 ]

通过特征error count 划分所带来的信息增益为0.183，也就是减少了 18.3% 的“混乱”程度

• 那该特征就是信息增益最大的特征了？
• 特征选的0.5、1.5的值是怎么来的？

特征选取的0.5、1.5从何而来

特征从“低”、“中”、“高”等文字描述转换成，0 1 2等数字，比如CPU可能的取值是[0,1,2]，那就可以尝试划分出阈值中位点

(0+1)/2=0.5
(1+2)/2=1.5

所以在选取划分点的时候就会参考中位点进行划分

选取信息增益最大的特征

先选择error count以1.5为划分点

• error count有9条，稳定与不稳定的比例为[5, 4]
• error count>1.5有2条，并且都是不稳定的

计算一下信息增益：

• 首先计算原始熵：11个样本中，5个稳定，6个不稳定，(Entropy=-(frac{6}{11}⋅log_2frac{6}{11}+frac{5}{11}⋅log_2frac{5}{11}) approx 0.994)
  • 再计算error count>=1.5的熵：(Entropy_1=-(frac{4}{9}⋅log_2frac{4}{9}+frac{5}{9}⋅log_2frac{5}{9}) approx 0.991)
  • 再计算error count>1.5的熵，由于全是不稳定，所以熵是0
• 计算加权熵：(Entropy_{weighted}=frac{9}{11}⋅0.991+frac{2}{11}⋅0 approx 0.811)
• 信息增益：0.994-0.811=0.183

选择error count以0.5为划分点

• error count有6条，稳定与不稳定的比例为[4, 2]

• error count>0.5有5条，稳定与不稳定的比例为[1, 4]

• 首先计算原始熵：上面已经计算过了，0.994

  • 再计算error count的熵：(Entropy_1=-(frac{4}{6}⋅log_2frac{4}{6}+frac{2}{6}⋅log_2frac{2}{6}) approx 0.918)
  • 再计算error count>0.5的熵：(Entropy_2=-(frac{1}{5}⋅log_2frac{1}{5}+frac{4}{5}⋅log_2frac{4}{5}) approx 0.722)

• 计算加权熵：(Entropy_{weighted}=frac{6}{11}⋅0.918+frac{5}{11}⋅0.722 approx 0.829)

• 信息增益：0.994-0.829=0.165

综上所述，error count为特征，以1.5为划分点，是合适的选择。并且将每个特征的每个划分点遍历一遍，得出error count是熵下降最快的划分点

小结

算法步骤：

• 计算当前数据集的熵
• 对每个特征求出信息增益
• 选择信息增益最大的特征进行节点分类
• 重复以上步骤，直至熵为0，或者特征用完，或者数到达规定层数

有位彦祖说到，这不就是ID3算法嘛，基于信息熵作为划分标准。其实说对了一部分，文中使用的代码

clf = DecisionTreeClassifier(criterion='entropy', random_state=0)

criterion='entropy'使用的是的算法是整合了CART算法+ID3的信息熵分类等多种算法思想融合而来

基尼指数

之前讨论了通过熵的方式来划分节点，本节讨论基尼指数来划分节点

[Gini(S) = 1 - sum_{i=1}^{n} p_i^2 ]

• n：数据集中类别的数量
• (p_i)：数据集中第 (i) 类的概率

clf = DecisionTreeClassifier(criterion='gini', random_state=0)

使用基尼指数，选择了error count作为划分特征，与熵不一样

基尼增益

选择error count

• error count有6条，稳定与不稳定的比例为[4, 2]
• error count>0.5有5条，稳定与不稳定的比例为[1, 4]

计算一下基尼增益：

• 原始基尼指数：(Gini = 1 - sum_{i=1}^{n} p_i^2 = 1-((frac{5}{11})^2-(frac{6}{11})^2 approx 0.496))
  • 计算error count的基尼指数，(Gini_1=1-((frac{4}{6})^2+(frac{2}{6})^2) approx 0.4445)
  • 计算error count>0.5的基尼指数，(Gini_2=1-((frac{1}{5})^2+(frac{4}{5})^2) = 0.32)
• 计算加权平均基尼指数：(Gini_{weighted}=frac{6}{11}⋅0.4445 + frac{5}{11}⋅0.32 approx 0.3870)
• 基尼增益：0.4959 - 0.3870=0.1089

选择error count

• error count有9条，稳定与不稳定的比例为[5, 4]
• error count>1.5有2条，并且都是不稳定的

计算一下基尼增益：

• 原始基尼指数：上面已经计算过，0.0496
  • 计算error count的基尼指数，(Gini_1=1-((frac{5}{9})^2+(frac{4}{9})^2) approx 0.4939)
  • 计算error count>1.5的基尼指数，由于全是不稳定，(Gini_2=1-((frac{0}{2})^2+(frac{2}{2})^2) = 0)
• 计算加权平均基尼指数：(Gini_{weighted}=frac{9}{11}⋅0.4939 approx 0.4041)
• 基尼增益：0.4959 - 0.4041=0.0918

小结

综上所述，error count为特征，以0.5为划分点，是合适的选择

使用基尼指数，选择特征划分点的时候，与熵的行为完全不一样，下面列一下基尼指数与熵的对比

剪枝

所谓剪枝，是提高决策树泛化能力的一种策略，剪枝的核心思想是减少数的复杂度，决策树通过找到最大的信息增益，不断迭代的划分节点分类，不断的迭代划分，就会造成树的复杂度不断提高

预剪枝

预剪枝：在构建决策树的过程中就进行限制，提前停止树的生长

• 设置最大深度，max_depth
• 设置叶子节点最小样本数，min_samples_leaf
• 设置内部节点最小样本数，min_samples_split
• 设置信息增益阈值（如增益低于某一阈值就不分裂）

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_predict, StratifiedKFold
from sklearn.metrics import classification_report


X, y = load_iris(return_X_y=True)

cv = StratifiedKFold(n_splits=5, shuffle=True)

model = DecisionTreeClassifier(max_depth=3, min_samples_leaf=3, random_state=0)
y_pred = cross_val_predict(model, X, y, cv=cv)

print("预剪枝 分类报告：n")
print(classification_report(y, y_pred, zero_division=0))

后剪枝

后剪枝：先让树尽可能长大（完全生长），然后再自底向上地修剪枝叶。sklearn中默认采用：成本复杂度剪枝（Cost Complexity Pruning，也叫 α-剪枝）：用代价函数考虑准确率与模型复杂度的权衡

from sklearn.model_selection import cross_val_score
import numpy as np

model = DecisionTreeClassifier(random_state=0)
path = model.cost_complexity_pruning_path(X, y)
ccp_alphas = path.ccp_alphas[:-1]

mean_scores = []

for alpha in ccp_alphas:
    clf = DecisionTreeClassifier(random_state=0, ccp_alpha=alpha)
    scores = cross_val_score(clf, X, y, cv=5, scoring='accuracy')
    mean_scores.append(scores.mean())

best_alpha = ccp_alphas[np.argmax(mean_scores)]
print("最佳 ccp_alpha:", best_alpha)

best_model = DecisionTreeClassifier(random_state=0, ccp_alpha=best_alpha)
best_model.fit(X, y)
y_pred = best_model.predict(X)
print("后剪枝 分类报告:")
print(classification_report(y, y_pred))

• 首先训练处一颗完整树
• 从底部开始，找到最小的子树节点t，将其子树 (T_t) 剪成一个叶子节点

• 计算剪枝后误差的变化，得到(alpha_t)
  • 其中损失函数可以使用多种方式计算，由于sklearn默认使用的是基尼指数，那就用基尼指数来计算误差$$alpha = frac{R(t)-R(T_t)}{|T_t|-1}$$
    • (R(t))：父节点的基尼指数
    • (R(T_t))：剪枝前加权基尼指数
    • (|T_t|)：叶节点数
• 上一步拿到的(alpha)，与ccp_alpha超参数（提前设置）进行对比，如果ccp_alpha>(alpha)，则减掉该子树
• 重复以上过程

举一个例子，来看下该节点（CPU）是否应该被剪枝

• 父节点的基尼指数：(R(t)=0.444)
• 加权平均基尼指数：
  • 父节点的加权基尼指数：(frac{3}{6}⋅0.444=0.222)
  • 左子树的加权基尼指数：(frac{1}{6}⋅0)
  • 右子树的加权基尼指数：(frac{2}{6}⋅0.5 approx 0.166)
  • 子树的加权基尼指数：(0.222+0+0.166=0.388)
• (alpha = frac{0.444-0.166}{3-1}=0.028)

如果超参数ccp_alpha>0.028，那该节点就将剪枝

联系我

• 联系我，做深入的交流
  

至此，本文结束
在下才疏学浅，有撒汤漏水的，请各位不吝赐教...