★ FEATURED ARTICLE 决策树这个算法我最早接触是在做一个用户流失预测的小项目上。当时手头有一批用户行为数据领导要求给出一个能解释清楚为什么判断这个用户会流失的模型。试过逻辑回归系数解释起来太绕试过KNN根本说不清哪些特征在起作用。最后选了决策树原因很简单——它把判断逻辑直接摊开给你看像一棵倒着长的树每个分叉点都在回答这个特征重不重要、重要到什么程度。这就是决策树最核心的价值可解释性。而ID3、C4.5、CART这三个经典算法恰好代表了决策树从能跑到跑得好再到什么都能跑的三个阶段。这篇文章我会把这三个算法的构建原理拆开讲透包括它们各自用什么指标选特征、为什么这么选、实际写代码时哪里容易踩坑以及我这些年用下来的一些经验判断。1. 决策树到底在解决一个什么问题1.1 从二十问游戏理解决策树的本质决策树的思路其实特别朴素你小时候可能玩过一个游戏我心里想一个东西你问我问题我只能回答是或不是看你能不能在二十个问题内猜出来。聪明的问法不是它是苹果吗而是它是水果吗——因为后者能把可能性空间砍掉一大半。决策树干的就是这件事。它把特征空间一层层切分每次切分都试图让切出来的子集纯度更高。所谓纯度就是子集里的样本尽可能属于同一个类别。切到某个节点时如果里面的样本已经全是同一类了就不用再切了这个节点变成叶子节点它的类别就是预测结果。这个过程的数学化表达就是给定训练集D特征集A递归地选择一个最优划分特征把D分成若干子集对每个子集重复这个过程直到满足停止条件。听起来简单但最优划分特征怎么定义就是ID3、C4.5、CART三个算法的分水岭。1.2 为什么不用准确率直接选特征有人可能会想那我直接试每个特征看哪个划分后子集准确率最高不就行了这个想法有两个致命问题。第一准确率对多路划分有偏好。假设有个特征叫用户ID每个ID对应一个样本按它划分后每个子集只有一个样本纯度100%准确率满分。但这棵树毫无泛化能力纯粹是记住了训练数据。这就是过拟合的典型表现。第二准确率不是凸函数优化起来不友好。我们需要一个能衡量不确定性的指标不确定性越小说明纯度越高。信息熵和基尼指数就是干这个的。信息熵来自信息论基尼指数来自概率论两者本质都在度量随机抽两个样本类别不一致的概率。这里有个常见误解很多人以为决策树选特征就是选最重要的特征。实际上它选的是当前节点上最能降低不确定性的特征这个特征在树的全局重要性排名里可能并不靠前因为它的作用可能被上层节点抢走了。1.3 三个算法的核心差异一览在深入细节之前先用一张表把ID3、C4.5、CART的核心区别摆出来后面再逐个拆解。维度ID3C4.5CART特征选择指标信息增益信息增益率基尼指数特征类型离散离散连续离散连续树的形态多叉树多叉树二叉树缺失值处理不支持支持支持剪枝策略无易过拟合悲观剪枝代价复杂度剪枝任务类型分类分类分类回归这张表建议先记住后面每个算法我会展开讲为什么会有这些差异以及这些差异在实际使用中意味着什么。2. ID3用信息增益选特征的开山之作2.1 信息熵不确定性的度量尺ID3的核心是信息增益而信息增益建立在信息熵之上。信息熵的公式是$$H(D) -\sum_{k1}^{K} p_k \log_2 p_k$$其中$p_k$是第k类样本在数据集D中的比例。这个公式在干什么它在算把D中样本的类别当作随机变量它的不确定性有多大。举个具体例子。假设D有10个样本5个正类5个负类那么$p_正0.5$$p_负0.5$$H(D) -(0.5 \times \log_2 0.5 0.5 \times \log_2 0.5) 1$比特。如果10个样本全是正类$p_正1$$H(D) -(1 \times \log_2 1) 0$比特。熵为0意味着完全确定熵为1意味着最不确定二分类情况下。我习惯用一个类比来解释熵就像一锅汤的混乱程度。所有料都均匀混在一起混乱度最高如果料分层了每层都是同一种混乱度就低。决策树要做的就是不断分层让每个子集尽量纯。2.2 信息增益的计算过程与偏好陷阱信息增益的定义是划分前的熵减去划分后的条件熵。$$Gain(D, a) H(D) - \sum_{v1}^{V} \frac{|D^v|}{|D|} H(D^v)$$其中$a$是特征$V$是$a$的取值个数$D^v$是$a$取第v个值的样本子集。我拿一个具体数据走一遍。假设有6个样本特征天气取值为晴、阴、雨标签是是否出门。样本天气是否出门1晴是2晴是3阴否4雨否5雨否6阴是划分前3个是3个否$H(D) 1$。按天气划分晴2个样本全是是$H 0$阴2个样本1是1否$H 1$雨2个样本全是否$H 0$条件熵 $\frac{2}{6} \times 0 \frac{2}{6} \times 1 \frac{2}{6} \times 0 \frac{1}{3}$信息增益 $1 - \frac{1}{3} \frac{2}{3} \approx 0.667$现在问题来了。如果还有一个特征叫样本编号取值1到6每个值对应一个样本。按它划分每个子集只有一个样本熵全是0条件熵为0信息增益 1。比天气的0.667大ID3会选样本编号。但这显然是个垃圾特征。这就是信息增益的偏好陷阱它偏好取值多的特征。因为取值越多划分越细每个子集越纯条件熵越低增益越大。C4.5就是为了解决这个问题而生的。2.3 ID3的代码实现与实操注意用Python手写一个简化版ID3核心逻辑如下import numpy as np from collections import Counter def entropy(y): counts Counter(y) probs [c / len(y) for c in counts.values()] return -sum(p * np.log2(p) for p in probs if p 0) def information_gain(X, y, feature_idx): base_entropy entropy(y) values np.unique(X[:, feature_idx]) cond_entropy 0 for v in values: mask X[:, feature_idx] v subset_y y[mask] cond_entropy (len(subset_y) / len(y)) * entropy(subset_y) return base_entropy - cond_entropy def id3(X, y, features): # 停止条件1全同一类 if len(set(y)) 1: return y[0] # 停止条件2特征用完 if len(features) 0: return Counter(y).most_common(1)[0][0] gains [information_gain(X, y, f) for f in features] best_f features[np.argmax(gains)] tree {best_f: {}} remaining [f for f in features if f ! best_f] for v in np.unique(X[:, best_f]): mask X[:, best_f] v tree[best_f][v] id3(X[mask], y[mask], remaining) return tree这段代码有几个实操中容易忽略的点。第一entropy函数里加了if p 0的判断因为$0 \times \log 0$在数学上定义为0但代码里会报错。第二停止条件2返回多数类这是处理特征用完但样本还没分纯的情况实际工程中还会加一个节点样本数小于阈值的停止条件。第三递归时remaining去掉了已用特征这隐含了一个假设每个特征在一条路径上只用一次。这个假设在ID3里成立但在某些变体中会被打破。实操心得ID3对连续特征无能为力如果你的数据里有年龄、收入这类连续值必须先手动分箱。分箱的粒度很讲究太粗丢失信息太细又容易过拟合。我一般先用等频分箱切成5到10箱再根据业务含义微调。3. C4.5用信息增益率修正ID3的偏好3.1 信息增益率怎么算为什么能修正偏好C4.5引入了一个叫分裂信息的量也叫固有值$$SplitInfo(D, a) -\sum_{v1}^{V} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}$$这个量衡量的是特征$a$本身的取值分布有多分散。取值越多、越均匀分裂信息越大。然后信息增益率就是$$GainRatio(D, a) \frac{Gain(D, a)}{SplitInfo(D, a)}$$回到刚才样本编号的例子。样本编号有6个取值每个取值1个样本分裂信息 $-\sum_{v1}^{6} \frac{1}{6} \log_2 \frac{1}{6} \log_2 6 \approx 2.585$。信息增益是1增益率 $1 / 2.585 \approx 0.387$。天气的分裂信息晴2个、阴2个、雨2个$-\left(\frac{2}{6}\log_2\frac{2}{6} \times 3\right) \log_2 3 \approx 1.585$。增益率 $0.667 / 1.585 \approx 0.421$。现在天气的增益率反而比样本编号高了偏好被修正了。3.2 增益率也有坑偏好取值少的特征但增益率不是完美的。如果某个特征只有一个取值分裂信息为0增益率会变成无穷大或者未定义。所以C4.5的实际做法是先从候选特征中选出信息增益高于平均值的特征再从中选增益率最高的。这是一个两阶段筛选避免了增益率对取值少特征的极端偏好。这个细节很多教程一笔带过但实际写代码时如果漏掉会出现除零错误或者选出无意义的单值特征。我在早期实现时就踩过这个坑当时数据里有个特征所有样本取值都一样结果程序直接崩了。3.3 C4.5对连续特征和缺失值的处理C4.5相比ID3最大的工程改进是支持连续特征和缺失值。连续特征处理用的是二分法。假设特征$a$在D上有m个不同取值排序后得到${a^1, a^2, ..., a^m}$。取相邻值的中点$\frac{a^i a^{i1}}{2}$作为划分点把D分成$\leq t$和$ t$两部分。对每个候选划分点算信息增益率选最好的。这里有个优化如果相邻两个样本类别相同它们之间的划分点可以跳过因为不会带来纯度提升。缺失值处理分两个层面。一是在选划分特征时只用在特征$a$上没有缺失的样本子集$\tilde{D}$来计算增益最后乘以一个系数$\frac{|\tilde{D}|}{|D|}$来惩罚缺失多的特征。二是划分样本时如果样本在特征$a$上缺失就把它同时分配到所有子节点但带一个权重权重等于各子节点样本比例。def gain_ratio_with_missing(X, y, feature_idx, missing_mask): # 只用非缺失样本计算增益 valid ~missing_mask[:, feature_idx] X_valid, y_valid X[valid], y[valid] if len(y_valid) 0: return 0 gain information_gain(X_valid, y_valid, feature_idx) # 惩罚系数 penalty len(y_valid) / len(y) # 分裂信息 values, counts np.unique(X_valid[:, feature_idx], return_countsTrue) probs counts / len(y_valid) split_info -sum(p * np.log2(p) for p in probs if p 0) if split_info 0: return 0 return (gain / split_info) * penalty注意缺失值处理会让样本在树中分裂成多份训练完后每个样本可能落在多个叶子节点上。预测时如果遇到缺失值也是按权重加权各叶子的输出。这个机制在sklearn的决策树里没有完全复现sklearn要求先自己填充缺失值。3.4 悲观剪枝C4.5的过拟合对策决策树不剪枝几乎必然过拟合。C4.5用的是悲观剪枝Pessimistic Error Pruning, PEP。它的思路是对每个子树比较剪枝前后在训练集上的错误率如果剪枝后错误率没有显著上升就剪掉。具体做法是给每个叶子节点的错误数加0.5的惩罚连续修正然后计算子树的错误率上界。如果子树根节点的错误率上界小于等于子树的加权错误率就剪枝。这个悲观体现在它假设训练集上的错误率会比真实错误率低所以加了惩罚项。PEP的优点是只需要训练集不需要单独的验证集在数据量少的时候很实用。缺点是偏向于剪掉那些叶子节点多的子树可能剪过头。我个人的经验是如果数据量够还是用验证集做剪枝更稳。4. CART基尼指数与二叉树的组合拳4.1 基尼指数为什么比熵计算更快CART用基尼指数替代信息熵$$Gini(D) 1 - \sum_{k1}^{K} p_k^2$$基尼指数可以理解为从D中随机抽两个样本类别不一致的概率。它的计算比熵简单因为不需要算对数。在特征选择时CART算的是划分后的加权基尼指数$$Gini_index(D, a) \sum_{v1}^{V} \frac{|D^v|}{|D|} Gini(D^v)$$选使这个值最小的特征。为什么基尼指数比熵快熵要算$\log_2$基尼只要算平方。在大规模数据上这个差异会累积。有研究表明基尼指数和熵在大多数情况下选出的特征是一致的只在少数边界情况下有差异。所以sklearn默认用基尼指数不是没有道理的。4.2 CART为什么坚持二叉树ID3和C4.5生成的是多叉树一个特征有几个取值就分几叉。CART不管特征有几个取值只做二分。对离散特征它会把取值分成两组穷举所有二分组合选最优的。对连续特征它选一个切分点$t$分成$\leq t$和$ t$。二叉树的好处有三个。第一避免多叉树带来的碎片化。多叉树在取值多的特征上会把数据切得很碎每个子节点样本少统计不可靠。第二二叉树等价于递归地做二分类结构更规整剪枝和后续处理更方便。第三对离散特征的有序性不敏感。多叉树把离散取值当作无序的但CART的二分可以捕捉到取值A和B一组C和D一组这种组合信息。代价是计算量。对V个取值的离散特征CART要穷举$2^{V-1} - 1$种二分组合。V大了会爆炸。所以实际实现里对离散特征通常限制取值数或者用启发式搜索代替穷举。4.3 CART回归树用方差代替基尼CART不仅能分类还能回归。回归树的叶子输出不是类别而是该节点样本的均值。特征选择的指标从基尼指数变成均方误差MSE$$MSE(D, a) \sum_{v1}^{2} \frac{|D^v|}{|D|} \text{Var}(D^v)$$选使MSE最小的划分。预测时新样本落到哪个叶子就输出那个叶子的均值。这里有个实操细节回归树对异常值敏感因为均值会被极端值拉偏。如果数据里有异常值可以考虑用中位数代替均值或者先做异常值处理。我在一个房价预测项目里就遇到过几套豪宅把整个区域的预测值拉高了后来把目标变量做了对数变换才缓解。def cart_regression_split(X, y): best_mse float(inf) best_feature, best_threshold None, None for f in range(X.shape[1]): thresholds np.unique(X[:, f]) for t in thresholds: left y[X[:, f] t] right y[X[:, f] t] if len(left) 0 or len(right) 0: continue mse (len(left) * np.var(left) len(right) * np.var(right)) / len(y) if mse best_mse: best_mse mse best_feature, best_threshold f, t return best_feature, best_threshold4.4 代价复杂度剪枝CART的剪枝逻辑CART用的是代价复杂度剪枝Cost Complexity Pruning, CCP也叫 weakest link pruning。它的目标函数是$$R_\alpha(T) R(T) \alpha |T|$$其中$R(T)$是树T的训练误差$|T|$是叶子节点数$\alpha$是惩罚系数。$\alpha$越大对树的大小惩罚越重树越简单。算法分两步。第一步从完整的树开始自下而上计算每个内部节点的剪枝收益。对每个内部节点算它被剪掉后$R_\alpha$的变化找到使$R_\alpha$最小的那个节点剪掉得到一个子树序列。第二步用交叉验证在子树序列里选最优的$\alpha$。sklearn里的ccp_alpha参数就是控制这个的。默认是0不剪枝。实际用的时候我一般先用cost_complexity_pruning_path拿到一系列$\alpha$值然后对每个$\alpha$训练一棵树用验证集选最好的。实操心得ccp_alpha的调参不要凭感觉。先用path clf.cost_complexity_pruning_path(X_train, y_train)拿到path.ccp_alphas然后对每个alpha训练模型看验证集准确率画一条曲线选拐点。这个流程比手动试快得多而且有据可循。5. 三个算法在实际项目中的选型与踩坑记录5.1 什么场景选哪个算法虽然现在sklearn的DecisionTreeClassifier默认就是CART的变体但理解三个算法的差异对选型和调参仍然重要。场景推荐算法理由纯离散特征数据量小ID3实现简单信息增益直观混合特征有缺失值C4.5原生支持连续值和缺失值需要回归任务CART唯一支持回归的需要特征重要性排序CART基尼重要性稳定sklearn原生支持需要概率输出CART叶子节点类别比例即概率我个人的经验是实际项目里90%的情况直接用CART。ID3和C4.5更多是理解原理的阶梯工程上CART的二叉树结构、剪枝机制、回归能力都更完善。但如果你在面试或者教学场景能把三个算法的演进逻辑讲清楚是很加分的。5.2 特征重要性怎么算才靠谱sklearn的feature_importances_用的是基尼重要性一个特征在所有节点上带来的基尼指数下降的加权和。但这个指标有两个坑。第一它偏向于高基数特征取值多的特征和ID3的信息增益偏好类似。第二它是在训练集上算的如果过拟合了重要性排序可能不可信。更稳的做法是用排列重要性Permutation Importance把某个特征的值随机打乱看模型性能下降多少。下降越多说明该特征越重要。这个方法是模型无关的而且可以在验证集上算。from sklearn.inspection import permutation_importance result permutation_importance(clf, X_val, y_val, n_repeats10, random_state42) for i in result.importances_mean.argsort()[::-1]: print(fFeature {i}: {result.importances_mean[i]:.4f} /- {result.importances_std[i]:.4f})5.3 决策树过拟合的几种表现和应对决策树过拟合的表现很直观训练集准确率接近100%验证集准确率差一大截。我总结了几种典型情况和应对手段。情况一树太深叶子节点样本太少。应对限制max_depth或者设min_samples_leaf。我一般先设min_samples_leaf5起步根据数据量调整。情况二特征太多噪声特征被选中。应对先做特征筛选或者用max_features限制每次分裂考虑的特征数。后者会让树更随机类似随机森林的思路。情况三连续特征切分点太细。应对对连续特征先分箱或者设min_samples_split防止在样本少的节点上继续切。情况四类别不平衡树偏向多数类。应对设class_weightbalanced或者对少数类过采样。from sklearn.tree import DecisionTreeClassifier clf DecisionTreeClassifier( criteriongini, max_depth8, min_samples_leaf5, min_samples_split10, class_weightbalanced, ccp_alpha0.01, random_state42 )5.4 一个完整的调参流程我把实际项目里的调参流程整理成步骤可以直接抄。先不剪枝训练一棵完整的树看训练集和验证集的准确率差距。差距大说明过拟合严重需要强剪枝。用cost_complexity_pruning_path拿到alpha序列对每个alpha训练模型画验证集准确率曲线选拐点附近的alpha。固定alpha调max_depth和min_samples_leaf。这两个参数控制树的复杂度先用网格搜索粗调再细调。如果还有提升空间试max_features。设成sqrt(n_features)或log2(n_features)引入随机性。最后用排列重要性检查特征把重要性接近0的特征删掉重新训练。这个流程走下来一般能比默认参数提升5到15个百分点。具体提升多少取决于数据质量如果特征本身噪声大提升有限。5.5 决策树的几个隐藏坑坑一random_state不设结果不可复现。决策树在特征重要性相同时会随机选一个不设随机种子每次跑的结果可能不一样。这个坑我在复现实验时踩过找了半天原因。坑二类别标签必须是数值。sklearn不接受字符串标签要先LabelEncoder。但注意LabelEncoder会把标签映射成0,1,2...如果标签本身有序比如低中高这个映射是合理的如果无序比如红绿蓝映射后的数值大小没有意义但决策树不会受影响因为它只关心相等与否。坑三连续特征的量纲不影响决策树。决策树不需要归一化因为它只关心大小关系不关心绝对距离。这点和SVM、KNN不同。但如果你用排列重要性量纲会影响打乱后的效果不过影响不大。坑四决策树对训练集的小扰动敏感。数据里改几个样本树的结构可能大变。这是决策树方差大的表现也是随机森林、GBDT这些集成方法存在的原因。如果单棵树效果不稳定考虑上集成。6. 从单棵树到集成决策树的延伸价值6.1 为什么决策树是集成学习的基石决策树虽然单棵效果一般但它是随机森林、GBDT、XGBoost、LightGBM这些强算法的基学习器。原因有三个。第一决策树是弱学习器的典型代表容易过拟合但偏差低。集成方法通过组合多棵低偏差、高方差的树降低方差提升泛化能力。第二决策树的训练可以并行随机森林里每棵树独立训练天然适合分布式。第三决策树对特征缩放不敏感预处理简单适合作为集成的组件。理解了单棵树的构建原理再看随机森林的随机选特征、GBDT的拟合残差就很容易明白它们在解决什么问题。随机森林是在降低方差GBDT是在降低偏差。6.2 决策树的可解释性在业务中的价值我做过一个信贷风控的项目业务方最关心的不是AUC多高而是为什么拒绝这个客户。决策树能直接给出一条规则路径收入低于X且负债率高于Y且近半年逾期次数大于Z拒绝。这条规则业务方能看懂能拿去和客户解释也能拿去和监管沟通。这是神经网络做不到的。神经网络可能效果更好但它是黑盒。在需要解释性的场景决策树和它的集成变体尤其是GBDT配合SHAP值是首选。6.3 决策树规则提取的实操方法从训练好的树里提取规则sklearn提供了tree_.threshold和tree_.children_left/right可以遍历。但更简单的方法是用export_textfrom sklearn.tree import export_text rules export_text(clf, feature_namesfeature_names) print(rules)输出是缩进的文本每个if-else分支就是一条规则。如果要转成业务规则表可以自己写个递归函数遍历树结构把路径上的条件收集起来。注意提取出来的规则在训练集上100%准确但不代表在真实数据上有效。规则要配合覆盖率一起看覆盖率太低的规则比如只覆盖几个样本不要用那是过拟合的产物。6.4 决策树在特征工程中的反向应用决策树不仅能做预测还能用来做特征工程。具体做法是用决策树对特征做离散化把连续特征切成若干区间每个区间作为一个新特征。这个方法叫基于树的离散化在逻辑回归等线性模型前处理中很有用。另一个用法是用决策树的叶子节点编号作为新特征喂给其他模型。这就是GBDTLR的经典套路GBDT负责特征组合和离散化LR负责最终分类。这个方案在点击率预测里用了很多年效果稳定。# 用决策树叶子编号做特征 leaf_ids clf.apply(X_train) # 返回每个样本落在哪个叶子 # leaf_ids 可以作为新特征喂给其他模型这个套路的原理是决策树的每条路径代表一种特征组合叶子编号就是组合的编码。相比手动做交叉特征树自动找到了有区分度的组合。7. 手写实现与sklearn对照几个关键差异7.1 分裂标准的实现差异手写ID3时我用的是信息增益。sklearn的criterionentropy也是信息增益但它的实现做了优化用直方图加速连续特征的阈值搜索而不是穷举所有唯一值。这个优化在大数据上差异明显手写版在10万样本上可能跑几分钟sklearn几秒就完了。CART的基尼指数在sklearn里也是直方图实现。如果你要自己实现建议先对特征排序然后用累积和算左右子集的基尼避免每次重新遍历。7.2 停止条件的差异手写版的停止条件通常只有全同一类和特征用完。sklearn多了几个max_depth、min_samples_split、min_samples_leaf、min_impurity_decrease。其中min_impurity_decrease最容易被忽略它要求分裂带来的不纯度下降至少达到这个值否则不分裂。这个参数在噪声大的数据上很有用能防止树在无意义的特征上浪费深度。7.3 缺失值处理的差异前面说过C4.5原生支持缺失值但sklearn的决策树不支持。sklearn要求输入没有NaN。如果你有缺失值要么填充要么用支持缺失值的梯度提升库比如某些版本的XGBoost和LightGBM。这是个实际使用中必须注意的差异别以为C4.5支持就以为sklearn也支持。7.4 多输出任务的差异sklearn的决策树支持多输出一个样本可以同时预测多个标签。比如预测一个人的多个属性性别、年龄段、收入档。实现上它把多输出当作多个单输出任务在每个节点上算所有输出的平均不纯度下降。这个功能在手写版里通常不实现因为用得少但知道有这回事遇到多标签任务时能想到。8. 写在最后我这些年用决策树的几点体会决策树是我工具箱里最常用的算法之一不是因为它效果最好而是因为它最透明。每次模型效果不好我第一件事就是打印一棵决策树看看往往能发现数据里的问题某个特征的分裂点很奇怪说明数据有异常值某个分支特别深说明这类样本特别难分某个特征从来没被用到说明它可能是冗余的。ID3、C4.5、CART这三个算法我建议每个学机器学习的人都亲手实现一遍。不是为了造轮子而是为了理解特征选择这件事的本质。信息增益、增益率、基尼指数这三个指标背后的思想——用不确定性度量纯度——会贯穿你后续学随机森林、GBDT、甚至神经网络的很多设计。最后分享一个我常用的调试技巧训练完一棵树后用export_text打印出来然后拿几条验证集样本手动沿着树走一遍看预测路径是否符合直觉。如果不符合要么是数据有问题要么是树过拟合了。这个手动验证的过程比看准确率数字更能发现问题。
阅读完成 · 觉得有帮助？
