彩笔运维勇闯机器学习--决策树

前言

决策树是一种常用的机器学习模型，用于分类和回归任务，它通过模拟“树”的结构来对数据进行决策。本节我们详细讨论的是决策树中的分类任务

开始探索

scikit-learn

假设以下运维场景

• CPU
  • 低：<40%
  • 中：40%~70%
  • 高：>70%
• 内存
  • 低：<60%
  • 中：60%~85%
  • 高：>85%
• 磁盘I/O
  • 低：<40%
  • 中：40%~70%
  • 高：>70%
• 日志报错数（条）
  • 少：<20
  • 中：20~50
  • 多：>50

将其转换成代码：

import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import classification_report


level_map = {'低': 0, '中': 1, '高': 2, '少': 0, '中': 1, '高': 2, '多':2, '稳定': 1, '不稳定': 0}
data = [
    ['低', '低', '低', '少', '稳定'],
    ['中', '中', '低', '少', '稳定'],
    ['低', '中', '高', '少', '稳定'],
    ['低', '低', '低', '多', '不稳定'],
    ['低', '低', '高', '多', '不稳定'],
    ['高', '高', '低', '少', '不稳定'],
    ['中', '高', '低', '中', '稳定'],
    ['高', '低', '低', '多', '不稳定'],
    ['中', '高', '高', '少', '不稳定'],
    ['中', '中', '中', '中', '不稳定'],
    ['高', '高', '低', '少', '稳定'],
]

data_mapped = [[level_map[v] for v in row] for row in data]

df = pd.DataFrame(data_mapped, columns=['CPU', '内存', '磁盘IO', '日志报错数', '系统是否稳定'])

X = df[['CPU', '内存', '磁盘IO', '日志报错数']]
y = df['系统是否稳定']

clf = DecisionTreeClassifier(criterion='entropy', random_state=0)
clf.fit(X, y)
y_pred = clf.predict(X)

print("分类报告：\n", classification_report(y, y_pred, target_names=['不稳定', '稳定']))

脚本！启动

绘图更能直接观察决策树

from sklearn import tree
import matplotlib.pyplot as plt

plt.figure(figsize=(14, 8))
tree.plot_tree(clf,
               feature_names=['CPU', 'memory', 'storage I/O', 'error count'],
               class_names=['not stable', 'stable'],
               filled=True)
plt.show()

分析绘图

• 每个矩形框代表一个决策节点（叶子节点），比如第一个框，error count<1.5表示用该特征来分类，1.5是基于输入的数据计算出来的，模型认为1.5是特征分割点
• entropy：当前节点的不确定性（越低越纯）
• samples：这个节点上的样本数
• value=[不稳定数, 稳定数]：类别分布
• class：当前节点最终被分类的类别

深入理解决策树

熵（entropy）

在图中有一个重要的指标，entropy。它是衡量数据纯度（不确定性）的指标，熵越低，表示类别越“纯”（不确定性越低）；熵越高，代表数据越混杂

$$Entropy(D)=-\sum _{i=1}^k{p}_i{\log }_2{p}_i$$

• 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}\cdot lo{g}_2\frac{1}{5}+\frac{4}{5}\cdot lo{g}_2\frac{4}{5})=0.7215$$

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

信息增益

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

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

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

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

$$加权熵=\frac{9}{11}\cdot 0.991+\frac{2}{11}\cdot 0=0.811$$

$$原始熵=0.994-0.811=0.183$$

通过特征error count <= 1.5划分所带来的信息增益为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<=1.5有9条，稳定与不稳定的比例为[5, 4]
• error count>1.5有2条，并且都是不稳定的

计算一下信息增益：

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

选择error count以0.5为划分点

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

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

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

  • 再计算error count<=0.5的熵：$Entrop{y}_1=-(\frac{4}{6}\cdot lo{g}_2\frac{4}{6}+\frac{2}{6}\cdot lo{g}_2\frac{2}{6})\approx 0.918$
  • 再计算error count>0.5的熵：$Entrop{y}_2=-(\frac{1}{5}\cdot lo{g}_2\frac{1}{5}+\frac{4}{5}\cdot lo{g}_2\frac{4}{5})\approx 0.722$

• 计算加权熵：$Entrop{y}_{weighted}=\frac{6}{11}\cdot 0.918+\frac{5}{11}\cdot 0.722\approx 0.829$

• 信息增益：0.994-0.829=0.165

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

小结

算法步骤：

• 计算当前数据集的熵
• 对每个特征求出信息增益
• 选择信息增益最大的特征进行节点分类
• 重复以上步骤，直至熵为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<=0.5作为划分特征，与熵不一样

基尼增益

选择error count<=0.5

• error count<=0.5有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<=0.5的基尼指数，$Gin{i}_1=1-((\frac{4}{6}{)}^2+(\frac{2}{6}{)}^2)\approx 0.4445$
  • 计算error count>0.5的基尼指数，$Gin{i}_2=1-((\frac{1}{5}{)}^2+(\frac{4}{5}{)}^2)=0.32$
• 计算加权平均基尼指数：$Gin{i}_{weighted}=\frac{6}{11}\cdot 0.4445+\frac{5}{11}\cdot 0.32\approx 0.3870$
• 基尼增益：0.4959 - 0.3870=0.1089

选择error count<=1.5

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

计算一下基尼增益：

• 原始基尼指数：上面已经计算过，0.0496
  • 计算error count<=1.5的基尼指数，$Gin{i}_1=1-((\frac{5}{9}{)}^2+(\frac{4}{9}{)}^2)\approx 0.4939$
  • 计算error count>1.5的基尼指数，由于全是不稳定，$Gin{i}_2=1-((\frac{0}{2}{)}^2+(\frac{2}{2}{)}^2)=0$
• 计算加权平均基尼指数：$Gin{i}_{weighted}=\frac{9}{11}\cdot 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<=1.5）是否应该被剪枝

• 父节点的基尼指数：$R(t)=0.444$
• 加权平均基尼指数：
  • 父节点的加权基尼指数：$\frac{3}{6}\cdot 0.444=0.222$
  • 左子树的加权基尼指数：$\frac{1}{6}\cdot 0$
  • 右子树的加权基尼指数：$\frac{2}{6}\cdot 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，那该节点就将剪枝

联系我

• 联系我，做深入的交流
  

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