2. 决策树算法原理：信息增益与 ID3

说到决策树，我第一个想到的场景就是日志里那个“未知错误码”的分类。你手头可能有一堆半结构化日志，光靠人工看，累得不行。
决策树呢，说白了就是用一层层“如果…就…”的规则把数据分开。它训练完之后，你拿一段新日志来，按规则一走，就知道是网络超时、内存溢出还是权限失败。

今天这一章，咱们就把决策树怎么“分”的底牌翻出来。重点是两个东西：信息增益和ID3 算法。这两个是决策树最经典的基础，用来做日志模式识别再合适不过。

信息熵：混乱程度的度量

要理解信息增益，得先搞明白 信息熵。我刚开始学的时候也觉得这概念玄乎，后来发现其实就是衡量一组数据有多“乱”。

举个例子：日志里有 100 条错误记录，全部都是“连接超时”。那基本上不用猜，肯定超时。这种确定性越高，熵就越低。
反过来，50 条超时、30 条拒绝、20 条权限错误——这时候不确定性就大了，熵值就高。

熵的公式长这样（习惯用代码写出来，直观）：

import math

def entropy(labels):
    total = len(labels)
    # 统计每个类别出现的次数
    counts = {}
    for l in labels:
        counts[l] = counts.get(l, 0) + 1
    # 计算熵
    ent = 0.0
    for cnt in counts.values():
        p = cnt / total
        if p > 0:
            ent -= p * math.log2(p)
    return ent

嗯，说白了就是对概率取对数再求和，取个负号。你可以暂时记住一个结论：所有样本属于同一类别时，熵 = 0；分布越均匀，熵越大。

信息增益：用什么特征来分

决策树选特征时，要选一个能让分裂后整体熵值降低最多的。降低的这部分就叫 信息增益。公式也不复杂：

信息增益 = 分裂前的熵 - 分裂后各子节点熵的加权平均

权重就是子节点样本数占总样本数的比例。你想想看，如果选了某个特征做划分，信息增益越大，说明它越能帮我们把混乱的日志分成更纯净的几堆。

具体计算我给你列个表格，拿一个简单的日志错误类型数据集来说：

先算总体熵：超时55、权限15、拒绝30，总数100。P(超时)=0.55，P(权限)=0.15，P(拒绝)=0.3。熵 = -0.55×log20.55 - 0.15×log20.15 - 0.3×log20.3 ≈ 1.43。

然后按“来源”这个特征分裂：
API模块：熵 = -20/30×log2(20/30) - 10/30×log2(10/30) ≈ 0.918
数据库模块：熵 = -5/30×log2(5/30) - 25/30×log2(25/30) ≈ 0.65
缓存模块：熵 = -30/40×log2(30/40) - 5/40×log2(5/40) - 5/40×log2(5/40) ≈ 1.13

加权平均熵 = (30/100)×0.918 + (30/100)×0.65 + (40/100)×1.13 ≈ 0.912

信息增益 = 1.43 - 0.912 = 0.518。这个值越大，越应该先用“来源”这个特征。

ID3 算法：递归构建决策树

ID3 就是利用信息增益反复分裂的贪心算法。步骤其实很简单：

1. 用当前数据集计算所有特征的信息增益
2. 选取信息增益最大的特征作为当前节点
3. 根据该特征的每个取值划分出子数据集
4. 对每个子数据集递归执行 1~3，直到满足停止条件（比如子集样本全属于一个类，或者没有特征可用了）

伪代码放下面，你跑一遍就知道逻辑了：

def id3(data, features):
    # 如果所有样本属于同一类，返回叶子节点
    if all_same_class(data):
        return leaf(class)
    # 如果没有剩余特征，返回多数类
    if not features:
        return leaf(majority_class(data))
    # 选择信息增益最大的特征
    best_feat = argmax(info_gain(data, f) for f in features)
    tree = {best_feat: {}}
    # 对每个取值递归
    for value in unique_values(data, best_feat):
        subset = data[data[best_feat] == value]
        tree[best_feat][value] = id3(subset, features - {best_feat})
    return tree

ID3 只支持离散特征，连续特征得先做离散化。我一般用等频分桶，但对于日志里的数值类字段（比如响应时间毫秒数），有时直接按是否超过阈值划分反而更有效。嗯，这点后面讲 C4.5 时会细说。

用 SVG 画一张 ID3 构建流程

下面这张图我帮你把 ID3 递归构建决策树的流程串起来了，你看完马上就有整体感：

图上可以看出，ID3 就是个“先选特征、再分裂、再递归”的重复过程。每一步都挑当下最能让样本变纯的那个特征。
我们做日志分类时，特征经常是“错误码前缀”、“模块名”、“请求方法”、“出现时段”这些离散字段。ID3 处理起来很顺。

ID3 的局限与我的避坑经验

• 只处理离散特征。连续值得自己做分箱，但分箱的粒度直接影响结果。我建议用领域知识——比如日志里的“处理时长”，一般分成“<100ms”、“100~500ms”、“>500ms”三段就够了，别太细。
• 容易过拟合。不剪枝的话，树可能记住很罕见的噪声模式。我在审计日志分析中遇到过，一个样本量只有 3 条的类别，树硬生生给画了 3 条路径出来。解决方法是预剪枝：设置叶子最少样本数 10，最大深度 8。
• 不支持缺失值。日志里常有空字段，ID3 直接报错。我的做法是：对缺失值用该特征的最常见值填充，或者单独当做一个“未知”类别来处理。

我个人认为，ID3 作为教学模型是完美的，让你一眼看穿决策树的内核。但真要拿它做线上日志分类，最好加点改造——要么加剪枝，要么直接上C4.5。不过那是后话了，我们先把这个地基打牢。