树形结构每个分支代表一个判断结果的输出每个叶子节点代表一种分类结果决策树建立过程特征选择选取有较强分类能力的特征决策树生成根据选择的特征生成决策树决策树容易过拟合采用剪枝的方法缓解算法分裂标准连续值缺失值剪枝树结构任务ID3信息增益最大不支持无处理无多叉树仅分类C4.5信息增益率最大二分离散概率分配PEP 后剪枝多叉树仅分类CART基尼系数最小二分无原生支持代价复杂度剪枝严格二叉树分类 回归1. ID3构建流程计算每个特征的信息增益使用信息增益最大的特征将数据集拆分为子集使用该特征作为决策树的节点如果特征信息增益结果相同根据奥卡姆剃刀原则选择简单的特征作为节点剩余特征重复上述步骤缺点天然偏向取值多的特征如身份证、日期极易过拟合。只能处理离散分类特征2. C4.5C4.5 是 Ross Quinlan 1993 年提出的经典分类决策树算法是 ID3 算法的全面升级版也是现代决策树的里程碑算法直接衍生出 C5.0、随机森林、XGBoost 等模型。ID3 只用信息增益选特征存在明显缺陷C4.5 改用信息增益率遍历所有特征选择增益率最大的特征作为分裂节点。同时支持连续值、缺失值、自动剪枝适配真实业务数据。缺点仅支持分类任务无法做回归预测熵计算包含大量对数运算连续值需要排序训练速度慢生成多叉树相比二叉 CART 树内存开销更大贪心局部最优无法全局搜索最优树结构。3. CartCart是一种决策树模型可以用于分类、回归问题。回归使用平方误差最小化策略分类使用基尼指数最小化策略。必须是二叉树3.1 分类树输出为离散值分类策略基尼系数最小化from sklearn.tree import DecisionTreeClassifier, plot_tree estimator DecisionTreeClassifier( criteriongini, # 特征选择标准默认gini可以选择信息增益 min_samples_split5, # 内部节点再划分所需样本数 min_samples_leaf5, # 叶子节点最少样本数 max_depthNone # 决策树最大深度 ) estimator.fit(x_train, y_train) # 模型预测 y_pre estimator.predict(x_test, y_pre) # 模型评估 print(classification_report(y_test, y_pre)) # sklearn.metrics.classification_report # 画图 plot_tree(estimator, filled True, max_depth5) # sklearn.tree.plot_tree3.2 回归树输出为连续值但一般不用决策树处理回归问题一般用线性回归。分类策略平方误差最小化※ 计算平方误差平方损失例数据集D如下计算最优分裂点。先将x排序取x相邻元素的平均值计算每个分裂点s对应的平方误差以s1.5为例x1.5x1.5以此类推计算每个分裂点的平方误差为当s6.5时平方误差最小为1.93。故特征x的切分点为6.5。第一个分支划分完成后继续重复上述步骤在剩余样本中算第二个切分点。以此类推直到树画完。假设在分裂两次生成3个区域后停止分裂最终回归树为如下每一个叶子节点输出为该节点上的所有样本均值。from sklearn.tree import DecisionTreeRegression # 模型训练 estimator DecisionTreeRegression(max_depth3) # 最大深度这里是3层 estimator.fit(x_train, y_train) # 模型预测 y_pre estimator.predict(x_test) # 模型评估 # sklearn.metrics.mean_absolute_error, mean_squared_error, root_mean_squared_error mae mean_absolute_error(y_test, y_pre) mse mean_squared_error(y_test, y_pre) rmse root_mean_squared_error(y_test, y_pre) # 画图 plt.plot(x_test, y_pre) # matplotlib.pyplot plt.show()4. 剪枝剪枝是一种防止决策树过拟合的正则化方法提高决策树的泛化能力。剪枝把子树的节点全部删掉以叶子节点替换。剪枝方法预剪枝、后剪枝维度预剪枝后剪枝优点很多分支不展开降低过拟合风险显著减少训练和测试的时间开销保留更多分支欠拟合风险很小泛化性能通常优于预剪枝缺点当前划分暂不能提升泛化性能、但后续可能显著提升的分支会被误删存在欠拟合风险先生成完整树再自底向上逐一考察所有非叶节点训练时间开销远大于未剪枝和预剪枝决策树如4.1 预剪枝决策树生成过程中对每个节点在划分前先进行估计若当前节点的划分不能带来决策树泛化性能的提升则停止划分并标记当前节点为叶子节点python实现建模时设定模型参数max_depth树最大深度min_samples_split节点至少多少样本才允许分裂min_samples_leaf叶子节点最少样本数max_leaf_nodes限制叶子总数# 带预剪枝的CART分类树 dt_pre DecisionTreeClassifier( max_depth4, # 限制深度 min_samples_split10, # 少于10个样本不再分裂 min_samples_leaf3, # 叶子至少3个样本 random_state42 ) dt_pre.fit(X_train, y_train) # 评估 y_pred_pre dt_pre.predict(X_test) print(预剪枝树准确率, accuracy_score(y_test, y_pred_pre)) # 可视化树 plt.figure(figsize(12,6)) plot_tree(dt_pre, filledTrue, feature_namesX.columns) plt.show()4.2 后剪枝是先从训练集生成一棵完整的决策树然后自底向上地对非叶节点进行考察若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升。则将该子树替换为叶节点。python实现# 1. 先训练完全生长的未剪枝大树 dt_full DecisionTreeClassifier(random_state42) dt_full.fit(X_train, y_train) # 2. 获取所有候选剪枝系数ccp_alphas ccp_alphas dt_full.cost_complexity_pruning_path(X_train, y_train).ccp_alphas # 去掉最后一个alpha空树 ccp_alphas ccp_alphas[:-1] # 3. 遍历每个alpha训练对应剪枝树保存模型与准确率 tree_list [] test_acc [] for alpha in ccp_alphas: dt_pruned DecisionTreeClassifier(ccp_alphaalpha, random_state42) dt_pruned.fit(X_train, y_train) tree_list.append(dt_pruned) acc accuracy_score(y_test, dt_pruned.predict(X_test)) test_acc.append(acc) # 4. 找到测试集准确率最高的最优alpha best_idx test_acc.index(max(test_acc)) best_alpha ccp_alphas[best_idx] print(最优剪枝系数alpha, best_alpha) # 5. 构建最终后剪枝最优树 dt_post DecisionTreeClassifier(ccp_alphabest_alpha, random_state42) dt_post.fit(X_train, y_train) y_pred_post dt_post.predict(X_test) print(后剪枝树准确率, accuracy_score(y_test, y_pred_post)) # 可视化最优剪枝树 plt.figure(figsize(12,6)) plot_tree(dt_post, filledTrue, feature_namesX.columns) plt.show()案例汇总泰坦尼克号乘客生存预测补充知识A 信息熵 Entropy信息论中代表随机随机变量不确定度的度量。衡量一组数据的混乱程度、不确定性熵越大数据类别杂乱、不确定性高熵越小数据纯度高、类别单一、容易判断熵 0数据全部是同一类完全没有不确定性。其中为第 i 类样本在整体中的占比。例一组数据x{A,A,A,B,B,C,B,D,C}4个类别共9个样本求信息熵。B 信息增益特征a对数据集D的信息增益定义为集合D的熵与特征a在给定条件下D的熵之差。(信息增益信息熵-条件熵条件熵其中对的每一种取值单独计算该分支下 D 的信息熵用该分支样本占比加权求和得到整体条件熵。条件熵Σ分类占比*特征熵例数据集D如下计算其信息增益。共1个特征2个分类6条样本1. 计算信息熵2. 计算条件熵1计算的条件熵2计算的条件熵3整体条件熵3. 计算信息增益C 信息增益率信息增益率 信息增益 / 特征熵其中本质特征的信息增益 / 特征内在的信息相当于对信息增益进行修正增加一个惩罚系数惩罚系数1/特征熵特征取值个数较多时惩罚系数较小特征取值个数较少时惩罚系数较大例数据集D如下问先选哪个特征作为分裂节点求信息增益率。1. 求特征a的信息增益率见【补充知识-信息增益】1特征a的信息增益2特征a的特征熵3特征a的信息增益率2. 求特征b的信息增益率1特征b的信息增益①特征b的条件熵②特征b的信息增益2特征b的特征熵3特征b的信息增益率3. 结论故首选特征a为分裂特征。D 基尼指数基尼系数基尼值从数据集D中随机抽取两个样本其类别标记不一致的概率。基尼值越小数据集D纯度越高。设节点内有 k 个类别为第 i 类样本占比基尼指数基尼指数越小代表用特征a拆分后整体数据集越纯净划分效果越好。设数据集 D特征 a 有 n 种取值划分出子集例已知是否拖欠贷款y数据1. 计算是否有房特征a的基尼指数1是否有房的基尼值有房yes的是否拖欠贷款集合{no,no,no}无房no的是否拖欠贷款集合{no,no,yes,no,yes,no,yes}2是否有房的基尼指数2. 计算婚姻状况特征b的基尼指数1婚姻状况的基尼值婚姻状况有三类值需要分类计算①single {married, divorced}单身single的是否拖欠贷款集合{no,no,yes,yes}已婚和离异married, divorced的是否拖欠贷款集合{no,no,no,no,yes,no}最终为②married {single, divorced}已婚married的是否拖欠贷款集合{no,no,no,no}单身和离异single, divorced的是否拖欠贷款集合{no,no,yes,yes,yes,no}最终为③divorced {single, married}离异divorced的是否拖欠贷款集合{yes,no}单身和已婚single, married的是否拖欠贷款集合{no,no,yes,yes,no,no,no,no}最终为2婚姻状况的基尼指数场景①场景②场景③其中最小的是场景②的基尼指数0.3.3. 计算年收入特征c的基尼指数1计算年收入的基尼值例以 65 为分裂点≤65652计算年收入的基尼指数以此类推计算每个分裂点的基尼指数选择最小的最小的为0.3分裂点为97.5.综合选择综合3个特征的基尼指数取最小值该案例基尼指数最小值为0.3特征为婚姻状态married, singeldivorced、年收入≤97.5, 97.5根据奥卡姆剃刀原则选取简单的特征婚姻状态作为根节点以married, singeldivorced分支。第一轮完成后开始选择第二轮的根节点。married下全部都是无贷终止singeldivorced下包含有贷和无贷需要从剩下的两个特征中选择根节点。此时需要重新计算不同的是该轮计算需要剔除含married的样本剩余样本作为新的数据集重新计算各特征的基尼指数然后选择基尼指数最小的特征和场景作为根节点和分支以此类推之后的每一轮都需要重新计算直至构建完整个决策树。