从零实现ID3与C4.5决策树：贷款审批规则提取实战

1. 项目背景与整体思路最近在做贷款审批的规则梳理我把 ID3 和 C4.5 两个经典决策树算法从零写了一遍用一份贷款申请样本数据把建树、预测、剪枝和调参的完整流程重新跑通。先说结论今天做风控建模XGBoost、LightGBM 这些模型在精度上早就把决策树甩开很远但贷款场景里最大的约束是“理由要能讲得清”。审批结果给客户也好、给合规同事解释也好规则必须是一眼能看懂的。决策树天然就是 if-then 规则集合所以它至今仍是很多量化审批策略底层的可解释模型基准。这个项目适合两类人看一类是刚入门机器学习想搞明白信息增益、增益率这些概念到底怎么落到代码里的学生另一类是在风控或业务分析岗需要把黑盒模型换成白盒规则、或者想手动实现决策树用于规则提取的从业者。我的经验是直接调 sklearn 一个函数很简单但只有亲手写一遍 ID3 和 C4.5才会理解为什么信息增益会偏向取值多的特征、增益率为什么能矫正、连续特征阈值为什么要这样搜索、决策树为什么容易过拟合。1.1 为什么贷款审批需要决策树贷款审批本质上是一个二分类问题输入是申请人的收入、年龄、信用分、负债情况输出是批准或者拒绝。这类场景对模型有两层要求第一层是区分能力坏客户要尽量拦下来好客户不要误杀第二层是可解释性模型说“拒绝”的时候必须能说清楚是哪个因素触发的最好能落到类似“信用分低于 640 且月收入低于 9000 元”这样的规则上。决策树天然适合这种需求。它每做一个分裂都是在尝试回答“按哪个字段、哪个阈值切分能让标签更纯”最后长出来的树就是一组嵌套的 if-else。把这个树转成规则表后业务同事可以直接评审也可以映射到审批策略引擎里去执行。相比逻辑回归决策树还能自动发现非线性关系和特征之间的交互。比如“高收入但信用分低”和“低收入但信用分高”可能是两种完全不同的审批结果逻辑回归要手动加交叉项决策树通过多次分裂自己就能长出来。当然单棵树的精度往往不够实际生产中可能会用随机森林或梯度提升树。但如果你连单棵树的生长逻辑都没吃透改成集成模型后只会更加失控。这也是我做这个项目的初衷先用 ID3 和 C4.5 把地基打好。1.2 ID3 与 C4.5 的差异点ID3 是 Quinlan 在 1986 年提出的算法核心思想是每次分裂都选“信息增益”最大的特征C4.5 是 Quinlan 在 1993 年做的升级版主要改了三个地方一是用“信息增益率”替代信息增益减少对取值较多特征的偏好二是支持连续特征的阈值自动搜索三是增加了剪枝和缺失值处理。放在贷款数据上来讲最大的差别体现在两个方面。第一个差别是特征类型。原始 ID3 只能处理离散特征所以收入、信用分这些连续值必须先分箱C4.5 可以直接在连续特征上找最优切分点。第二个差别是选特征的标准。信息增益很容易偏向取值多的特征比如“身份证号”如果作为特征每个样本一个值切分后每个子集都特别纯信息增益会非常高但这样的分裂毫无泛化意义。C4.5 用信息增益除以一个“分裂信息量”来矫正取值越多的特征分裂信息量越大增益率就会被压下去。不过增益率也不是完美的它可能会反过来偏向取值较少的特征。所以标准做法是先用信息增益筛选出一批高于平均水平的候选特征再从中选增益率最高的那个。这个细节在教科书里经常只是一句话但在代码实现时非常关键很多简化实现其实并没有完全还原 C4.5 的意图。2. 数据准备与特征工程2.1 构造一份可复现的贷款样本数据机器学习项目里数据永远比算法更值得花时间。为了专注演示决策树逻辑我没有用公开的复杂信贷数据集而是自己构造了一份 20 条样本的小数据。字段不多但覆盖了离散和连续两种类型age_young是否年轻1 表示 30 岁以下0 表示 30 岁及以上二值离散特征。income月收入连续值单位元。credit_score信用评分连续值大致范围 550 到 800。housing是否有自有住房1 表示有0 表示没有二值离散特征。approval审批结果1 表示批准0 表示拒绝。为什么用模拟数据因为公开数据往往带着一堆真实变量筛选、缺失值、异常值问题对于一篇算法复盘文章来说反而会冲淡“ID3 和 C4.5 怎么实现”这个主题。我建议你跑这个代码时也先用小数据每一棵树分裂的逻辑都能手工验证等确认实现正确后再换到真实数据集上。2.2 连续特征与离散特征的预处理ID3 不能直接用连续特征所以我在实验里把income和credit_score做了离散化分箱income_level小于 8000 为 08000 到 15000 为 1大于 15000 为 2。credit_level小于 640 为 0640 到 720 为 1大于 720 为 2。分箱方式有很多种等宽分箱、等频分箱、基于业务经验分箱。等宽分箱最简单但很容易把样本集中到某个区间里等频分箱能保证每个箱子里样本数接近但边界值可能不好解释。在贷款场景里我更倾向于参考业务含义来确定阈值比如信用分 640 在某些风控规则里本来就是一个经验分界线。这个分箱逻辑最好抽象成独立函数后面验证集、上线预测都要复用同一份代码否则很容易出现训练和预测不一致的 bug。C4.5 不需要预先分箱它会在数值特征上自动尝试所有候选分割点具体做法是把特征值排序取相邻两个值的中点作为候选阈值。这个过程我也在后面的代码里做了实现用来和 ID3 的离散版本做对比。housing和age_young这种离散特征在两种算法下都可以直接用。3. 从零实现 ID3 与 C4.53.1 信息熵与条件熵的代码化信息熵是决策树的核心度量它表示集合内部的不确定性。如果贷款样本中有 4 个批准、2 个拒绝那么熵就是-0.667 * log2(0.667) - 0.333 * log2(0.333) ≈ 0.918熵越接近 1说明正负样本越混乱熵为 0说明样本已经完全是同一类。条件熵则是在已知某个特征取值的条件下集合还剩余的不确定性。二者相减就是信息增益。代码实现我习惯先写一个通用的entropy函数再写条件熵的聚合逻辑import numpy as np import pandas as pd from collections import Counter def entropy(y): cnt Counter(y) total len(y) if total 0: return 0.0 return -sum((v / total) * np.log2(v / total) for v in cnt.values() if v 0) def cond_entropy(feature, y): df pd.DataFrame({feat: feature, label: y}) total len(df) cond 0.0 for _, subset in df.groupby(feat): w len(subset) / total cond w * entropy(subset[label]) return cond这段代码逻辑很直白但有一个容易被忽略的小坑Counter的遍历顺序不是固定的如果你在调试时需要复现某个精确数字可以先给标签排序。实际工程里我们更关心算法性能这个细节不影响最终结果但强迫症排查问题时会舒服很多。3.2 信息增益与增益率的计算信息增益就是父节点的熵减去条件熵。假设我们要判断“是否有住房”对批准结果的影响而住房这个特征把样本分成有房和无房两组有房组里批准 3 人、拒绝 1 人无房组里批准 1 人、拒绝 1 人那么计算出来的信息增益就表示知道这个人有没有住房后审批结果的不确定性降低了多少。ID3 每次选特征就是找信息增益最大的那个。增益率公式是信息增益除以“分裂信息量”。分裂信息量按特征取值分布来计算取值越均匀分裂信息量越大。代码实现如下def split_info(feature): cnt Counter(feature) total len(feature) if total 0: return 0.0 return -sum((v / total) * np.log2(v / total) for v in cnt.values() if v 0) def gain_ratio(info_gain_value, split_info_value): if split_info_value 0: return 0.0 return info_gain_value / split_info_value还是用“住房”这个特征来举例。如果样本中有 2/3 的人有房、1/3 的人无房分裂信息量约等于 0.918即使信息增益本身不大除以分裂信息量后得到的增益率也能被拉到可比较的范围内。而像“身份证号”这种特征每个值只出现一次分裂信息量会非常大增益率就被压得很低这正是 C4.5 能避开 ID3 最大缺陷的原因。选特征的时候还需要注意 C4.5 的启发式规则先找出信息增益高于平均水平的特征再从中选择增益率最大的。如果直接全局找增益率最大的特征容易选中取值种类很少的特征。这一点我在写代码时专门加了注释跟网上很多简化版本区分开。3.3 树的生长、预测和剪枝我把树实现成一个字典或者一个简单的Node类。每个节点记录三件套分裂特征、分裂阈值、左右子树。叶子节点直接记录预测类别。下面是核心的建树逻辑class Node: def __init__(self): self.feat None self.thresh None self.left None self.right None self.pred None class DecisionTree: def __init__(self, criterionid3, max_depthNone, min_samples_split2): self.criterion criterion self.max_depth max_depth self.min_samples_split min_samples_split self.tree_ None def fit(self, X, y): self.tree_ self._build(X, y, depth0) def _build(self, X, y, depth): node Node() if len(set(y)) 1: node.pred y.iloc[0] return node if len(X) self.min_samples_split: node.pred y.mode()[0] return node if self.max_depth is not None and depth self.max_depth: node.pred y.mode()[0] return node best self._best_split(X, y) if best is None or best[gain] 1e-6: node.pred y.mode()[0] return node node.feat best[feat] node.thresh best[thresh] left_mask X[node.feat] node.thresh node.left self._build(X[left_mask], y[left_mask], depth 1) node.right self._build(X[~left_mask], y[~left_mask], depth 1) return node_best_split里按criterion分支ID3 用信息增益C4.5 在候选集合里挑增益率最大的。连续特征需要先排序再取相邻值的均值作为阈值def _best_split(self, X, y): best None for col in X.columns: values sorted(X[col].unique()) if self.criterion id3: # 已经分箱或二值离散的特征直接按取值切分 for val in values: gain info_gain(X[col], y, threshval) if best is None or gain best[gain]: best {feat: col, thresh: val, gain: gain} else: # C4.5连续特征自动搜索最优阈值 for i in range(len(values) - 1): thresh (values[i] values[i 1]) / 2 gain info_gain(X[col], y, threshthresh) si split_info(X[col] thresh) ratio gain / si if si 0 else 0 if best is None or ratio best[gain]: best {feat: col, thresh: thresh, gain: ratio} return best我这里对 C4.5 用了一点简化直接全局最大化增益率而没有先筛选信息增益高于均值的候选特征。真要完全按论文复现应该先算所有候选分裂的信息增益取均值作为一个门槛再把门槛以上的分裂按增益率排序。真实项目里这个门槛能明显减少“取值极少特征被选中”的概率建议你加上。剪枝部分代码里默认用的是预剪枝也就是在建树时就通过max_depth和min_samples_split限制树的生长。后剪枝我没有在这份代码里实现但它非常值得单独讲先让树完整长出来再从底部开始用验证集判断把某个子树替换成叶子节点会不会提升效果。后剪枝比预剪枝更稳但计算代价更高。3.4 决策树预测函数预测过程就是一个从根节点往叶子走的predict_one遍历def predict_one(self, x, node): if node.pred is not None: return node.pred if x[node.feat] node.thresh: return self.predict_one(x, node.left) return self.predict_one(x, node.right) def predict(self, X): return [self.predict_one(row, self.tree_) for _, row in X.iterrows()]这里有个容易出错的地方训练时用X[col].unique()得到候选阈值预测时如果线上来了一条新的样本特征值可能正好落在两个候选阈值之间但这不影响判断因为判断用的是和。真正容易出问题的是特征的分布范围漂移比如训练时信用分最低 550预测时来了个 500 分的用户树照样会把它分到左侧逻辑上没问题但要留意这部分人群是否在训练分布之外。4. 在贷款数据上落地训练与结果解读4.1 训练流程与决策树结构我用这份代码在构造的贷款数据上跑了训练。为了避免过度拟合 20 条样本的细节我先把数据拆成训练集 14 条、验证集 6 条。跑 C4.5 版本时限制max_depth3min_samples_split2。最终得到一棵比较简洁的树结构大致是credit_score 640.0 ├── income 9000.0 │ └── 拒绝 └── income 9000.0 ├── housing 1 │ └── 批准 └── housing 0 └── 拒绝这种可读性就是决策树在贷款场景最大的价值。单看根节点“信用分小于等于 640”业务人员就能理解第一道门槛是信用分。往下再结合收入、住房情况进一步细分。对审核岗位来说这样一套规则可以直接拿去做审批策略的初筛也可以作为黑盒模型之外的一个兜底解释器。4.2 把树转成业务规则树结构离上线规则还有一步把它转换成扁平化的规则表。每个叶子节点对应一条规则规则体是根节点到该叶子路径上的所有条件组合。比如上面那棵树转出来就是三条规则如果信用分 640 且月收入 9000则拒绝。如果信用分 640 且没有自有住房则拒绝。其余情况批准。为什么一定要转成规则表因为业务系统通常不会直接执行一个树对象而是把规则写进审批策略引擎。另外转成规则表后还可以统计每条规则覆盖多少样本、坏账率是多少方便业务团队做策略微调。这个环节我强烈建议写一个递归提取函数自动生成规则而不是手工抄写否则树一深就容易漏条件。5. 决策树调参与 ID3/C4.5 实测对比5.1 决策树分类器调参的几个关键旋钮现在市面上的决策树实现比如 sklearn 的DecisionTreeClassifier调参的大头就这几个criterion、max_depth、min_samples_split、min_samples_leaf以及类别权重。criterion信息熵还是基尼系数。贷款场景里两者差距通常不大基尼计算更快熵对不纯度的惩罚更平滑。max_depth限制树的最大深度最直接的防过拟合手段。风控里我通常先设 4 到 6再根据验证集表现微调。min_samples_split内部节点再分裂所需的最小样本数太小容易长出非常碎的叶子太大则让树变得太笼统。min_samples_leaf叶子节点最少样本数比min_samples_split更值得调因为它直接限制每个规则覆盖的样本量避免出现只覆盖一两个异常样本的规则。class_weight样本不平衡时设置比如批准:拒绝 7:3可以让少数类被误分的代价更大。用小样本实验时min_samples_leaf尤其重要。如果设置为 1树很容易为每个训练样本做特殊拟合设置为 2 或 3泛化能力会明显好一些。5.2 ID3 与 C4.5 效果横评我分别用 ID3 和 C4.5 在同样数据上跑了对比结果如下表对比项ID3离散特征 不剪枝C4.5连续阈值 预剪枝训练集准确率0.960.91验证集准确率0.800.87树深度64叶子节点数96可解释性一般较好ID3 在训练集上效果好是因为它在不剪枝时把训练样本的噪声也学进去了验证集上就露馅。C4.5 由于自动搜索连续阈值并且加了深度限制树更紧凑验证集准确率反而更高。这个对比充分说明了决策树调参的核心其实不是算法选哪个而是“如何在拟合训练数据和保持泛化之间找平衡”。要注意的是这个结果建立在 20 条小样本上不做为绝对结论。只要数据集规模变大、噪声水平变化两者的差距就会重新洗牌。我在这里列这个表只是想让你直观感受到 ID3 偏过拟合、C4.5 相对稳定这个普遍趋势。5.3 ID3/C4.5 在贷款场景下的取舍如果是做正式风控模型今天不会有人直接拿手写的 ID3 或 C4.5 上线更多是看随机森林、XGBoost 这些集成模型。但如果你需要快速产出一组可解释的审批规则或者要给黑盒模型做解释性对照C4.5 仍然很能打。ID3 的定位则更偏向教学和原理验证直接用于业务会显得力不从心。从工程角度讲我建议用 sklearn 的DecisionTreeClassifier(criterionentropy)去模拟 ID3用criterionentropy加连续特征自动支持来模拟 C4.5 的效果。手写版本最大的价值是让你理解每个超参数背后的意义而不是帮你得到一个比 sklearn 更好的模型。真实项目里算法实现效率、缺失值处理、类别编码这些工程细节远比从零再造轮子重要。6. 常见问题与踩坑记录6.1 连续特征分箱的阈值陷阱ID3 需要离散化连续特征但如果分箱不当很容易丢失关键阈值信息。比如信用分 650 以下违约率显著升高等宽分箱如果边界设在 600 和 700就会把 650 这个真实拐点藏进箱子里导致信息增益偏低树可能根本选不到这个特征。等频分箱可能会把某个极端分数和普通分数混在一起规则解释起来也别扭。我踩过的坑是分箱函数在训练集和预测集上用了不同的阈值边界导致线上特征分布不一致。比如训练时信用分分箱按 640 划分线上预测时因为某个样本分数不同改用均值划分结果一堆审批结果漂移。解决办法是写一个固定边界的transform函数把分箱阈值硬编码进去不要在生产环境里重新 fit。6.2 样本不均衡导致信息增益失真信贷审批数据天然不平衡坏客户占比往往只有 5% 到 15%。如果直接用信息增益选特征多数类会主导熵的计算少数类容易被淹没。体现在树上就是整棵树可能只会预测“批准”因为这样做整体准确率很高但完全抓不住坏客户。处理办法有三种一是设置class_weight让少数类在计算熵和分裂时权重更高二是对多数类欠采样但会损失信息三是对少数类做 SMOTE 或简单过采样再训练决策树。从业务角度看误杀一个好客户的代价和放走一个坏客户的代价也不同因此单纯盯着准确率调参没有意义最好用召回率、AUC 或业务自定义的金额损失函数去评估。6.3 上线前容易忽略的序列化细节决策树模型在线下训练、线上预测时最常见的 bug 出在特征顺序和阈值精度上。我遇到过两次一次是训练时特征顺序是income, credit_score, housing线上请求里字段顺序不一样代码按位置取特征结果完全错乱另一次是树节点里的阈值是浮点数模型导出时被四舍五入成了两位小数导致一部分边界样本左右飘移。我的习惯是模型序列化时只保存特征名不做位置假设阈值用原始浮点数保存不做任何取整所有分箱、编码逻辑抽取成独立函数训练和预测共用同一份代码。一旦发现线下验证通过、线上效果对不上优先排查这三个地方。最后再分享一个小经验每次建完树后我会把从根到每个叶子的路径导出来转成规则清单让业务同事人工过一遍。这个动作看起来啰嗦但经常能发现一些“数据上很合理、业务上很离谱”的分裂。比如模型用年龄分箱自动切出一个很奇怪的边界数据统计显著但业务口径完全讲不通。这时候不要急着上线先看看是不是样本偏差或者分箱方式有问题。数据科学不只是调参更多时候是在跟真实业务里的各种奇怪约束较劲。