一、什么是决策树决策树通过对训练样本的学习并建立分类规则然后依据分类规则对新样本数据进行分类预测属于有效监督学习。核心所以数据从根节点一步一步落到叶子节点。决策树的结构非常类似生活中的判断过程例如天气怎么样├── 晴天 → 湿度高吗│ ├── 是 → 不打球│ └── 否 → 打球└── 阴天 → 打球其中根节点第一个节点非叶子节点中间节点叶子节点最终结果节点决策树的核心问题是如何选择最优特征进行数据划分不同算法采用了不同的方法ID3使用信息增益C4.5使用信息增益率CART使用基尼指数Gini Index二、ID3 算法基于信息增益选择特征1. 信息熵EntropyID3 算法的核心思想是选择能够最大程度降低数据不确定性的特征作为划分依据。衡量数据混乱程度的指标就是信息熵。公式\[ H(D) -\sum p_i \log_2(p_i) \]其中\( p_i \)某一类别出现的概率熵越小数据越纯净熵越大数据越混乱在决策树中希望划分之后的数据熵越来越小。文件中的案例使用是否外出打球作为分类任务14 天数据中打球9 天不打球5 天因此类别熵为\[ H(D) 0.940 \]2. 信息增益Information Gain信息增益表示一个特征能够减少多少信息的不确定性。公式\[ \text{Gain}(D, A) H(D) - H(D|A) \]如果某个特征带来的信息增益最大则说明该特征最具有分类能力会优先作为决策树节点。3. ID3 案例计算假设数据包含特征分类天气晴天、阴天、雨天温度热、温和、凉爽湿度高、正常风有风、无风分别计算不同特征的信息增益。1天气特征天气划分后晴天5 天阴天4 天雨天5 天计算得到\[ H(D|\text{天气}) 0.693 \]因此\[ \text{Gain}(\text{天气}) 0.940 - 0.693 0.247 \]2温度特征计算得到\[ \text{Gain}(\text{温度}) 0.940 - 0.911 0.029 \]3湿度特征计算得到\[ \text{Gain}(\text{湿度}) 0.151 \]4风特征计算得到\[ \text{Gain}(\text{风}) 0.048 \]最终结果特征信息增益天气0.247湿度0.151风0.048温度0.029因此\[ \text{天气} \text{湿度} \text{风} \text{温度} \]天气成为根节点。三、C4.5 算法解决 ID3 容易偏向取值多特征的问题1. 为什么需要 C4.5ID3 算法存在一个问题如果某个特征拥有大量不同取值例如编号用户 ID商品编号虽然信息增益很高但实际没有分类意义。因此 C4.5 提出使用信息增益率代替信息增益。2. 信息增益率计算过程计算类别熵计算每个属性的信息熵计算信息增益\[ \text{Gain} H(D) - H(D|A) \]计算信息增益率\[ \text{GainRatio} \frac{\text{Gain}}{H(A)} \]选择信息增益率最大的特征。3. C4.5 案例计算计算结果特征信息增益率天气0.1566湿度0.151风0.049温度0.0186排序\[ \text{天气} \text{湿度} \text{风} \text{温度} \]因此依旧选择天气作为首个划分节点。四、CART 算法基于基尼指数CARTClassification And Regression Tree是目前应用非常广泛的一种决策树算法。它与 ID3、C4.5 最大的区别ID3信息增益C4.5信息增益率CART基尼指数CART 选择使划分后的数据基尼指数最小的特征。1. 基尼指数Gini Index公式\[ \text{Gini}(D) 1 - \sum p_i^2 \]含义Gini 越小数据越纯最好的划分方式就是让划分后的 Gini 指数最低例如贷款预测案例根据年龄特征青年中年老年分别计算不同年龄节点的基尼指数。五、决策树剪枝解决过拟合问题1. 为什么需要剪枝在决策树学习过程中模型会不断地对数据进行划分。如果不限制树的生长例如有 1000 条训练数据构建出来的决策树可能生成 1000 条不同的路径。也就是说每一个样本都有自己对应的一条判断路线树会完全记住训练数据对训练数据预测效果很好但是面对新的未知数据时可能无法正确判断这种现象称为过拟合Overfitting即模型过度学习训练数据中的细节和噪声导致泛化能力下降。因此需要通过剪枝Pruning降低模型复杂度提高模型对新数据的预测能力。2. 决策树如何剪枝决策树剪枝主要分为两种1预剪枝Pre-Pruning预剪枝是在决策树生成过程中提前限制树的生长。也就是说在树还没有完全建立之前根据一定条件停止继续划分。例如限制树的最大深度限制叶子节点数量限制叶子节点最少样本数量优点训练速度快可以减少模型复杂度防止过拟合缺点可能提前停止导致模型没有充分学习数据规律2后剪枝Post-Pruning后剪枝是在决策树已经完全生成之后再删除不必要的分支。流程先构建完整决策树分析每个节点的重要程度删除贡献较小的节点得到更加简单的决策树优点保留更多数据规律通常泛化能力更强缺点计算成本较高3. 预剪枝策略在实际机器学习中预剪枝通常通过以下方式实现1限制树的深度参数max_depth表示决策树允许达到的最大层数。例如如果设置max_depth 3表示树最多只有 3 层。作用防止树无限增长降低模型复杂度减少过拟合在数据量较小的时候可以不限制深度如果样本数量多特征数量多则可以尝试限制树深度。2限制叶子节点数量参数max_leaf_nodes表示限制决策树最大的叶子节点数量。例如设置max_leaf_nodes 10那么当叶子节点达到 10 个模型不会继续产生新的分支作用控制树结构规模防止模型学习过多细节3限制叶子节点样本数量参数min_samples_leaf表示叶子节点中最少需要包含多少个样本。例如min_samples_leaf 5表示一个叶子节点至少需要 5 个样本。如果某个节点样本过少说明该节点可能只是在记忆训练数据容易造成过拟合因此可以进行剪枝。4. 基尼系数与剪枝CART 算法使用基尼指数Gini Index作为节点划分标准。公式\[ \text{Gini}(D) 1 - \sum p_i^2 \]其中\( p_i \)类别比例基尼指数越小说明数据越纯。在剪枝过程中如果某个节点继续划分后基尼指数下降不明显分类效果提升很小那么这个节点可能没有必要继续展开。因此基尼系数不仅用于选择划分节点也可以辅助判断树结构是否合理。CART 算法本身就是通过基尼指数最小化准则进行特征选择。5. 剪枝前后的决策树变化剪枝前根节点 | ---------------- | | 节点A 节点B / \ / \ C D E F /|\ /|\ ...大量分支...特点树结构复杂节点数量多容易过拟合剪枝后根节点 | ---------------- | | 节点A 节点B | 结果特点删除无意义分支模型更加简单泛化能力提高六、sklearn 中的决策树剪枝参数在 sklearn 中from sklearn.tree import DecisionTreeClassifier model DecisionTreeClassifier( criteriongini, max_depth5, min_samples_leaf10, max_leaf_nodes20 )其中参数
