做风控的同学应该都有过这种体验业务方丢给你一张几十个字段的申请表说“看情况决定批不批”可真要落到代码上“情况”到底是什么、先看哪个字段、看到什么程度能拍板谁也说不清楚。我第一次动手实现ID3和C4.5算法来完成贷款决策树项目时最大的感受就是——原来“看情况决定”是可以被写成规则的而且这套规则能直接从历史数据里长出来。这篇文章记录的是一个完整可复现的实验用纯Python手写ID3决策树和C4.5决策树在贷款审批数据集上构建决策树分类器判断一笔贷款申请该批还是该拒。项目会覆盖信息熵、信息增益、信息增益率、连续属性离散化、剪枝以及决策树调参这些关键内容适合刚学完理论、想看看代码怎么落地的同学也适合在信贷、反欺诈场景里需要可解释模型的从业者。文章里的代码我尽量写得贴近生产习惯方便你直接改造到自己的业务数据上。1. 项目背景贷款审批为什么需要决策树1.1 风控场景里的“拍脑袋”困境贷款审批本质上是一个分类问题输入是申请人的年龄、收入、职业、负债、信用记录等特征输出是“批准”或“拒绝”。很多小型金融机构和信贷平台早期主要靠人工审核审核员根据经验判断但这里有个很现实的问题经验无法批量复制。同一个申请上午下午两个审核员可能给出不同结论更不用说规模化扩张时新人培训成本有多高。决策树模型在这里的价值在于两点。第一它是白盒模型每一条审批结论都可以回溯到“收入3万且信用良好”这样明确的规则监管审计时能说清楚第二它能从标注好的历史数据里自动学出规则不用人工去枚举“什么条件组合应该拒绝”。这个项目的标题之所以选ID3与C4.5来实现而不是直接调sklearn是因为手写一遍才能把特征选择的内部逻辑吃透后面用工具时你才知道那些参数到底在控制什么。1.2 为什么是ID3和C4.5ID3是决策树算法里的老祖宗由Quinlan在1986年提出核心思想是每次选特征时都挑信息增益最大的那个属性来分裂。它简单、直观但有两个明显的硬伤一是偏好取值较多的特征一个身份证号特征的增益可能碾压所有业务特征二是不能直接处理连续数值收入、年龄、负债率这些字段都得先人工分箱。C4.5是ID3作者自己在1993年做的升级版改用信息增益率来克服ID3的偏好问题同时补上了连续属性自动离散化、缺失值处理和剪枝机制。可以说ID3是理解决策树原理的最佳入门版本C4.5则是把ID3推向工程可用的关键一步。做这个贷款项目时把两个算法都实现一遍等于把决策树最重要的两个里程碑亲手走了一遍。2. 数据集设计把贷款审批抽象成一张表2.1 自造数据集的原则做算法实验最忌讳一上来就拿脏数据练手尤其是手写算法阶段你需要一个能随时验证对错的“标准答案”。所以我设计了一个15条样本的小型贷款数据集包含年龄、月收入、是否学生、信用记录四个特征。这个规模刚好能手工验算每一步熵和增益又足够让两棵树的差异体现出来。特征的选择参考了真实信贷审批中最常见的维度年龄代表人生阶段与还款稳定性月收入代表还款能力是否学生代表收入结构的特殊性信用记录则代表历史履约情况。其中月收入我特意保留为连续数值目的就是为了同时演示C4.5的连续属性处理能力以及ID3必须先做离散化处理的局限性。2.2 样本数据表下面就是手工整理的15条历史记录标签列“是否批准”表示最终审批结果序号年龄月收入(元)是否学生信用记录是否批准1青年12000否一般否2青年25000否良好否3青年38000是一般是4青年22000是良好是5青年60000是良好是6青年15000是一般是7中年50000否一般是8中年35000否良好是9中年18000是良好是10中年22000是一般否11中年70000否良好是12老年8000否一般否13老年45000否良好否14老年30000是一般是15老年20000否一般否这里藏了一个小设计老年群体样本里高收入且信用良好的人依然被拒绝了。这在真实业务里可能是因为年龄导致贷款期限受限但只从数据看它会让“老年”这个特征呈现一种非纯状态正好用于观察算法在特征不纯时如何继续往下分裂。2.3 数据集的代码化在实际代码里我建议用列表套列表的方式存储数据集每行数据去掉表头之后是一个完整的样本向量最后一列固定是标签。为了方便后面测试我还把一个新样本单独拿出来22岁、学生、月收入28000、信用良好这个样本的预期判断是批准。def create_dataset(): # 15条历史样本年龄、月收入、是否学生、信用记录、是否批准 data [ [青年, 12000, 否, 一般, 否], [青年, 25000, 否, 良好, 否], [青年, 38000, 是, 一般, 是], [青年, 22000, 是, 良好, 是], [青年, 60000, 是, 良好, 是], [青年, 15000, 是, 一般, 是], [中年, 50000, 否, 一般, 是], [中年, 35000, 否, 良好, 是], [中年, 18000, 是, 良好, 是], [中年, 22000, 是, 一般, 否], [中年, 70000, 否, 良好, 是], [老年, 8000, 否, 一般, 否], [老年, 45000, 否, 良好, 否], [老年, 30000, 是, 一般, 是], [老年, 20000, 否, 一般, 否], ] features [年龄, 月收入, 是否学生, 信用记录] continuous_flags [False, True, False, False] # 仅月收入是连续特征 return data, features, continuous_flags设计这段代码时有几个小细节需要注意。continuous_flags列表非常重要它告诉算法哪些特征应该走连续属性处理流程否则算法会把月收入的每个具体数值当成一个离散取值算出来的信息增益会非常离谱。另外数据里不能出现完全重复但标签不同的样本否则算法没法学习出确定规则真实业务中遇到这种冲突样本时也要先做清洗。3. 核心原理从信息熵到信息增益率3.1 信息熵数据混乱程度的度量信息熵是信息论里衡量不确定性的指标。一个集合里如果所有样本的标签都一样那它非常“确定”熵就是0如果标签一半是批准一半是拒绝那最混乱熵达到最大值。计算公式如下H(D) -Σ(pk * log2(pk))其中pk是第k类样本占集合D的比例。在贷款数据集上15条样本中“是”有9条“否”有6条那么整体熵大约是0.971。这个值代表着在没有任何特征信息的情况下判断一笔贷款是否批准的不确定性。这里用到了log2信息量的单位是比特。比如一个集合里两类样本各占一半H(D)1含义就是“还需要1个比特的信息才能确定分类结果”。后续算信息增益时所有计算都基于这个基准。3.2 ID3的特征选择信息增益信息增益的定义是用某个特征划分数据集之前和之后熵的差值。公式表达为Gain(D, A) H(D) - Σ(|Dv| / |D|) * H(Dv)其中Dv是根据特征A的第v个取值划分出来的子集。增益越大说明用这个特征划分之后数据变得更“纯”了不确定性下降得最多。ID3的做法很简单遍历所有特征算每个特征的增益选最大的那个作为当前节点。用收入这个连续特征举例ID3不能直接用需要先把收入分箱。比如把月收入分成三档小于等于15000是“低收入”15000到35000是“中收入”大于35000是“高收入”。分箱之后才能套用上面的公式计算信息增益。但这个分箱过程本身带有主观性箱体的边界不同结果就不同这正是ID3的局限之一。3.3 C4.5的改进信息增益率C4.5并不仅仅是将Gain除以一个分裂信息量它要解决的是ID3“偏心”的问题。信息增益天然更喜欢取值多的特征因为特征值越多划分出来的子集越小熵下降得越快。为了抵消这种偏好C4.5引入分裂信息项SplitInfo(D, A) -Σ(|Dv| / |D|) * log2(|Dv| / |D|)然后定义增益率GainRatio(D, A) Gain(D, A) / SplitInfo(D, A)一个取值非常多的特征它的SplitInfo会很大分母一大增益率就被压下来了从而避免算法总盯着那些“分得太碎”的特征。在实际使用C4.5时算法通常会在候选特征里先挑出增益高于平均水平的再从中选择增益率最高的防止出现增益率虚高但实际增益很小的边缘情况。3.4 连续属性怎么处理C4.5处理连续属性的方式是二分法。具体来说将特征取值从小到大排序然后遍历所有相邻取值的中点把这个中点当作候选阈值把数据一分为二小于等于阈值的进左子集大于阈值的进右子集。每个阈值都能算出一个信息增益选增益最大的作为该连续特征的“最优分裂点”。处理连续特征时有一个关键差异离散特征在某个节点被使用后子节点一般不再使用它但连续特征分裂后建议保留因为数据在不同区间内可能还需要继续按该特征分裂。为了简化我的实现中会保留连续特征的再次使用权限这也是C4.5的标准做法。4. 代码实现手写ID3决策树4.1 公共工具函数先把信息熵、划分数据集、多数投票这几个最基础的公共函数写出来。后面ID3和C4.5都会复用。写信息熵时务必要注意对数函数的定义域p为0时跳过即可否则math.log2(0)会直接抛异常。import math from collections import Counter def calc_entropy(labels): total len(labels) if total 0: return 0.0 entropy 0.0 counter Counter(labels) for count in counter.values(): p count / total entropy - p * math.log2(p) return entropy def split_by_discrete_value(dataset, feature_index, value): sub_dataset [] for row in dataset: if row[feature_index] value: reduced row[:feature_index] row[feature_index 1:] sub_dataset.append(reduced) return sub_dataset def majority_label(labels): counter Counter(labels) return counter.most_common(1)[0][0] def calc_info_gain(dataset, feature_index): labels [row[-1] for row in dataset] entropy_before calc_entropy(labels) values set(row[feature_index] for row in dataset) entropy_after 0.0 for value in values: sub_dataset split_by_discrete_value(dataset, feature_index, value) weight len(sub_dataset) / len(dataset) entropy_after weight * calc_entropy([row[-1] for row in sub_dataset]) return entropy_before - entropy_aftersplit_by_discrete_value里我用了一个小技巧把被选中的那一列从子数据集中删掉。这样递归传参时特征集合天然就减少了不用额外维护“还有哪些特征没被使用”的列表。当然这个做法只适合离散特征连续特征不能这么删。4.2 ID3建树主逻辑ID3建树用递归实现。递归的基本套路是先看是否该停然后选最优特征再根据特征取值逐个往下建子树。def choose_best_feature_id3(dataset): feature_count len(dataset[0]) - 1 best_gain -1.0 best_index -1 for index in range(feature_count): gain calc_info_gain(dataset, index) if gain best_gain: best_gain gain best_index index return best_index, best_gain def build_tree_id3(dataset, features): labels [row[-1] for row in dataset] if len(set(labels)) 1: return labels[0] if len(dataset[0]) 1: return majority_label(labels) best_index, best_gain choose_best_feature_id3(dataset) if best_gain 0: return majority_label(labels) best_feature features[best_index] if best_feature 月收入: raise ValueError(ID3不能直接处理连续特征请先对月收入离散化) tree {best_feature: {}} values set(row[best_index] for row in dataset) remaining_features features[:best_index] features[best_index 1:] for value in values: sub_dataset split_by_discrete_value(dataset, best_index, value) if not sub_dataset: tree[best_feature][value] majority_label(labels) else: tree[best_feature][value] build_tree_id3(sub_dataset, remaining_features) return tree这里有个容易被新手忽略的问题特征值集合需要用set去重但Python的set是无序的导致每次运行树结构里分支打印的顺序可能不同。这不会影响准确率但如果希望结果可复现可以改成sorted(set(...))自己规定一个顺序。运行前我先把原始数据里的月收入做一次离散化映射def discretize_income(dataset): new_dataset [] for row in dataset: income row[1] if income 15000: income_label 低收入 elif income 35000: income_label 中收入 else: income_label 高收入 row_copy row[:] row_copy[1] income_label new_dataset.append(row_copy) return new_dataset离散化之后用ID3训练出的树大概是这样的结构根节点选择了“是否学生”然后学生分支会根据收入继续分非学生分支会根据信用记录继续分。这个结果并不意外因为在给月收入分了箱之后学生特征的取值区分度确实更好。4.3 ID3的预测与决策可视化ID3训练完成之后需要写一个简单的预测函数从根节点开始根据样本各特征值一路向下走到叶子节点def predict_id3(tree, sample, features): if not isinstance(tree, dict): return tree feature next(iter(tree)) index features.index(feature) value sample[index] subtree tree[feature].get(value) if subtree is None: return None return predict_id3(subtree, sample, features)predict函数返回的None表示这个分支在训练集中没有见过真实业务中遇到这种情况应该走兜底策略比如默认拒绝或者走人工审核而不是直接抛异常。打印树结构时我习惯用递归写法配合缩进让树的分层关系一目了然。把打印和预测这两个函数配合起来就能清楚看到ID3在贷款数据上学到的规则“学生且中高收入的人是优质客户非学生则需要看信用记录和收入档位”。这就是白盒模型的好处模型结果可以直接交给业务人员评审而不是给一个不可解释的概率值。5. 代码实现升级到C4.5决策树5.1 连续属性的最优阈值搜索C4.5的代码比ID3多两个复杂点连续属性处理和增益率计算。先写连续属性的阈值搜索逻辑。def split_by_continuous(dataset, feature_index, threshold): left [] right [] for row in dataset: if row[feature_index] threshold: left.append(row) else: right.append(row) return left, right def best_threshold_for_continuous(dataset, feature_index): values sorted(set(row[feature_index] for row in dataset)) best_gain -1.0 best_threshold values[0] labels [row[-1] for row in dataset] entropy_before calc_entropy(labels) for i in range(len(values) - 1): threshold (values[i] values[i 1]) / 2 left, right split_by_continuous(dataset, feature_index, threshold) if not left or not right: continue entropy_after (len(left) / len(dataset)) * calc_entropy([row[-1] for row in left]) \ (len(right) / len(dataset)) * calc_entropy([row[-1] for row in right]) gain entropy_before - entropy_after if gain best_gain: best_gain gain best_threshold threshold return best_threshold, best_gain取相邻值中点作为阈值是C4.5的经典做法。比如收入8000和12000的中间值是10000算法会尝试“收入10000”这个条件看划分后信息增益有多大。遍历15条样本的14个收入数值之间所有中点量级非常小所以效率完全不用担心。5.2 信息增益率计算与建树先写分裂信息量和增益率计算然后写C4.5建树主逻辑。与ID3不同C4.5的树节点需要区分“离散分支”和“连续分支”两类所以我在代码中设计了统一的节点结构离散节点有branches字典连续节点有threshold、left、right三个字段。def calc_split_info(dataset, feature_index): values [row[feature_index] for row in dataset] total len(values) split_info 0.0 for count in Counter(values).values(): p count / total split_info - p * math.log2(p) return split_info def calc_split_info_for_threshold(dataset, feature_index, threshold): left, right split_by_continuous(dataset, feature_index, threshold) total len(dataset) p1 len(left) / total p2 len(right) / total if p1 0 or p2 0: return 0.0 return -(p1 * math.log2(p1) p2 * math.log2(p2)) def calc_gain_ratio(dataset, feature_index): gain calc_info_gain(dataset, feature_index) split_info calc_split_info(dataset, feature_index) if split_info 0: return 0.0 return gain / split_info建树函数相对于ID3多了连续特征处理、连续特征保留这两个关键区别。离散特征还是从特征列表里删除连续特征则保留供后续节点继续使用。下面是完整实现def choose_best_feature_c45(dataset, features, continuous_flags): best_score -1.0 best_index -1 best_threshold None for index in range(len(features)): if continuous_flags[index]: threshold, gain best_threshold_for_continuous(dataset, index) split_info calc_split_info_for_threshold(dataset, index, threshold) score gain / split_info if split_info 0 else 0.0 else: gain calc_info_gain(dataset, index) split_info calc_split_info(dataset, index) score gain / split_info if split_info 0 else 0.0 if score best_score: best_score score best_index index best_threshold threshold if continuous_flags[index] else None return best_index, best_threshold def build_tree_c45(dataset, features, continuous_flags, max_depthNone, depth0): labels [row[-1] for row in dataset] if len(set(labels)) 1: return labels[0] if max_depth is not None and depth max_depth: return majority_label(labels) if len(features) 0: return majority_label(labels) best_index, best_threshold choose_best_feature_c45(dataset, features, continuous_flags) if best_index -1: return majority_label(labels) best_feature features[best_index] if continuous_flags[best_index]: left, right split_by_continuous(dataset, best_index, best_threshold) if not left or not right: return majority_label(labels) left_labels [row[-1] for row in left] right_labels [row[-1] for row in right] tree { feature: best_feature, type: continuous, threshold: best_threshold, left: majority_label(left_labels) if len(set(left_labels)) 1 else build_tree_c45(left, features, continuous_flags, max_depth, depth 1), right: majority_label(right_labels) if len(set(right_labels)) 1 else build_tree_c45(right, features, continuous_flags, max_depth, depth 1) } else: tree { feature: best_feature, type: discrete, branches: {} } remaining_features features[:best_index] features[best_index 1:] remaining_flags continuous_flags[:best_index] continuous_flags[best_index 1:] values set(row[best_index] for row in dataset) for value in values: sub_dataset [row for row in dataset if row[best_index] value] if not sub_dataset: tree[branches][value] majority_label(labels) else: tree[branches][value] build_tree_c45( sub_dataset, remaining_features, remaining_flags, max_depth, depth 1 ) return tree这个实现有一个值得注意的地方连续特征分裂后左子树和右子树在子代内部还有可能继续按“月收入”这一列再分裂因为features列表没有删除这个特征。这正是C4.5与ID3的重要差异。比如第一次按月收入8000划分后右子集里75000和60000等收入值之间可能还需要继续按收入区分。5.3 剪枝策略的实现思路C4.5在原论文里引入了悲观剪枝但完整实现比较复杂。这个项目里我补充了预剪枝和后剪枝两种思路方便在校验集上控制树的大小。预剪枝最简单就是在建树过程中加限制条件max_depth控制最大深度min_samples_leaf控制叶子节点最小样本数。生产实践里预剪枝是性价比最高的防过拟合手段。我在build_tree_c45中已经加了max_depth参数min_samples_leaf可以这样补充添加一个判断如果某个子集样本数小于min_samples_leaf就停止分裂直接返回多数类。后剪枝的做法是先让树完整生长然后从下往上尝试把某个子树替换成叶子节点用验证集评估替换前后准确率变化如果替换后效果不下降就剪掉。后剪枝性能开销大但往往比预剪枝效果好。真实项目里通常两种一起用或者直接用交叉验证找最佳参数。6. 对比实验两棵树的差异分析6.1 树结构对比同样一份数据集ID3离散化后和C4.5训练出的树根节点不一定相同。实测下来ID3的根节点偏向于“是否学生”因为分箱后的收入信息增益低于学生特征而C4.5由于对收入进行最优点二分收入特征的增益率往往排名靠前根节点会优先选择“月收入”。这种差异本身就是两种算法特征选择策略的直观体现。C4.5的树通常更紧凑因为连续属性的二分可以让每个节点的分裂质量更高不需要像ID3那样依赖人工分箱。但紧凑并不等于绝对准确数据噪声多的时候增益率偏向平衡分裂反而可能错过一些很细但很有用的规则。6.2 预测结果比较用同一个新样本做验证ID3和C4.5大概率能保持一致结论但各自给出的决策路径不同。ID3的路径可能是“是否学生是 - 月收入中收入 - 批准”C4.5的路径可能是“月收入27500 - 是否学生是 - 批准”。两条路径都对只是视角不同。如果测试集足够大C4.5的泛化能力通常优于ID3原因在于连续属性自动离散化避免了人工分箱的主观性增益率又减少了特征偏好带来的过拟合。但差距没有想象中那么大当业务特征都是离散值时两者的差距可能非常微小。6.3 特征选择偏好对比把两种算法的特征选择结果放到一起会更直观算法根节点选择依据连续属性主要短板ID3是否学生信息增益需手动分箱偏向取值多的特征C4.5月收入信息增益率自动二分增益率可能虚高需配合平均增益过滤注意C4.5的“增益率可能虚高”是一个真实存在的坑所以论文原实现里会加一道保险先算所有特征的平均信息增益只从增益高于平均值的特征里再挑增益率最高的。我这个实现为了代码简洁没有加这层过滤生产环境建议补上。7. 常见问题与决策树调参经验7.1 算出来的信息增益为什么是0最常见的原因是特征在当前数据子集里只有一个取值特征对学生样本集没有区分能力增益自然为0。这时候算法应该停止分裂并返回多数类而不是继续选择这个特征。另一个常见原因是熵计算公式里没有处理p0的情况直接math.log2(0)抛异常。建议写一个安全版本的熵函数p≤0时直接贡献0。还有一类问题出在连续属性上。如果连续特征的所有值都相同或者候选阈值划分后某一侧为空增益也会很低。处理办法是阈值搜索时跳过left或right为空的候选点。7.2 连续属性离散化的三大坑第一ID3手动分箱的边界很敏感边界从15000改成18000树的形状可能完全不同。真实项目中我建议用分位数分箱而不是拍脑袋定整数比如取收入的33%和67%分位点作为边界。第二C4.5二分阈值只能区分“小于等于某个数”和“大于某个数”如果收入在50000和55000之间还有明显差异二分就捕捉不到可能需要把连续属性转成多值的有序离散特征。第三连续特征分裂阈值经常会选在噪声样本附近导致树过拟合。缓解办法是限制min_samples_leaf让每个叶子至少保留一定数量的样本不要为了一两个离群点反复分裂。7.3 决策树调参维度决策树分类器调参的核心是控制模型复杂度。max_depth控制树的深度默认很深的话每片叶子可能只覆盖很少样本模型几乎背下训练集。min_samples_leaf控制每个叶子最小样本数设置太小时模型容易放大噪声。min_samples_split控制分裂所需的最小样本数这个参数对防止过度分裂也很有用。真实实践里我一般先调min_samples_leaf再调max_depth最后看特征重要性确认哪些字段有真正区分度。还有一个经验当数据分布极度不平衡时比如99%的拒绝率光调树结构参数不够还要关注类别权重、下采样或上采样。决策树算法本身对不平衡数据非常敏感因为它基于信息熵计算少数类的贡献容易被淹没。7.4 从手写到框架的迁移建议手写ID3和C4.5的最大价值是理解原理但上了生产环境还是建议用成熟框架。拿sklearn举例它的DecisionTreeClassifier默认使用的是CART算法支持基尼系数和信息熵两种准则。想复现C4.5的思路可以把criterion设为entropy然后把splitter保持为best。但对于连续特征自动离散化、增益率这些C4.5特有的逻辑sklearn并没有直接暴露成参数需要自己在特征工程阶段处理。如果业务中确实需要C4.5的完整实现可以考虑用第三方库或自己封装。我个人更倾向的做法是把这篇手写代码当成一个可解释规则引擎的原型真正落地时再迁移到Spark或分布式框架上用相同的树结构逻辑处理更大规模的数据。7.5 我的几个实操心得做贷款决策树这类项目我学到了几个比调参更重要的经验。数据集一定要干净标签冲突的样本务必删除或做多数投票归并否则树会生成很多噪声分支。特征含义要可解释不要为了一点点准确率加入业务上解释不清楚的“黑箱特征”这会毁掉决策树在风控场景里的最大价值。最后决策树模型相当脆弱训练集和测试集只要分布稍微不一致树结构就会剧烈变化上线前一定要用验证集做稳定性评估。我自己踩过的一个坑是把连续特征收入直接当离散特征喂给ID3结果树的一整层都被各种收入数值占满根节点也变成了“月收入”看起来增益最高实际毫无泛化能力。后来在代码里强制要求所有连续特征先标记再根据标记走不同的分裂逻辑才把这个坑填上。这也是这个项目里我收获最大的一点算法实现不只是堆公式数据的类型和约束往往决定了代码的核心结构。