所花时间：90min
今天主要学习内容主要是机器学习，上课没咋听
知识点总结
这个问题很关键，决策树是机器学习的基础算法，也是软件设计师考试中机器学习部分的高频考点！核心结论：决策树是一种基于 “分而治之” 思想的树形分类 / 回归模型，通过属性划分逐步缩小样本范围，最终输出预测结果，核心围绕 “属性选择、剪枝、终止条件” 展开。
一、核心定义与本质
决策树是一种树形结构，每个内部节点代表一个属性的划分判断，每个叶节点代表一个类别（分类任务）或预测值（回归任务）。其本质是 “贪心算法 + 分而治之”：从根节点开始，每次选择最优属性划分样本，将复杂问题拆解为多个简单子问题，直到满足终止条件，最终实现对新样本的快速预测。
二、核心组成部分
根节点：整个决策树的起点，包含全部训练样本，需选择第一个最优划分属性。
内部节点：代表一个属性的划分，每个分支对应该属性的一个取值（如 “色泽 = 红”“色泽 = 绿”）。
叶节点：决策树的终点，无后续分支，每个叶节点对应一个确定的类别（分类）或预测值（回归），类别通常取该节点样本中数量最多的类别。
分支：连接父节点与子节点的路径，对应属性的某个取值，代表划分后的样本子集。
三、关键步骤：属性选择准则
属性选择的目标是找到 “最能区分样本类别” 的属性，常用准则有 3 种：
信息增益（ID3 算法）：基于信息熵计算，公式为 IG (S,A)=H (S)-H (S|A)，H 为信息熵。优先选择信息增益大的属性，但倾向于选择取值多的属性（如 “身份证号”），易过拟合。
信息增益率（C4.5 算法）：通过分裂信息归一化信息增益，公式为 GR (S,A)=IG (S,A)/SplitInfo (S,A)，解决了信息增益的偏好问题，但可能过度偏好取值少的属性。
基尼系数（CART 算法）：衡量样本集合的纯度，基尼系数越小，样本纯度越高。优先选择基尼系数最小的属性划分，计算效率高，适用于分类和回归任务。
四、避免过拟合：剪枝策略
决策树易因 “分支过细” 导致过拟合（对训练集拟合好，泛化能力差），需通过剪枝优化：
预剪枝：在决策树构建过程中提前停止分支，常用停止条件包括 “节点样本数少于预设阈值”“信息增益低于阈值”“样本类别纯度达到阈值”。优点是计算成本低、防过拟合效果直接；缺点是可能欠拟合（剪掉有用分支），对阈值敏感。
后剪枝：先构建完整决策树，再修剪冗余分支，通过验证集评估剪枝效果（如错误率是否下降）。常用方法有错误率降低剪枝（REP）、悲观错误剪枝（PEP）。优点是泛化能力强、欠拟合风险低；缺点是计算成本高，需额外验证集。
五、算法终止条件
当满足以下任一条件时，停止分支并标记为叶节点：
当前节点所有样本属于同一类别，无需进一步划分。
无剩余属性可用于划分，或剩余属性无法降低样本不确定性（如信息增益为 0），类别取该节点样本数最多的类别。
当前节点样本数量少于预设阈值，避免过拟合。
所有样本的属性值完全相同，无法区分，类别取样本数最多的类别。
六、优缺点
优点：结构直观、易解释（可可视化），无需对数据做归一化 / 标准化预处理，能处理离散型和连续型属性，鲁棒性较强。
缺点：易过拟合（需剪枝优化），对噪声数据敏感，可能产生偏斜树（某一分支过深），分类边界呈轴平行状，对复杂数据拟合能力有限。
