机器学习 决策树

损失：1.分割过程中，错误分类的数量
不纯度：
1. 子分类中类别混杂的程度

R包rpart tree
让树停止生长：

1. 子分区太小或者叶子结点太小 minsplit minbucket控制
2. 如果不能显著的降低不纯度 停止分割，依靠复杂度参数cpksvi ,cp越大 树越复杂 树的生长

集成：使用一个模型集和得到最终的预测
装袋：对数据 进行bootsrap建立一个模型集和

超参数 运行前需要确定的参数：

1. nodesize
2. maxnodes

基础概念

ID3:信息增益，多叉树 会过拟合 无法处理NA值，无剪枝，片偏向较多的特征，只能处理离散值，分类
ID4.5:信息增益+信息增益比，多叉树，可剪枝，分类
CART:二叉树，Geni指数，分类回归，类别平衡影响不大

信息 增益：原始的熵-子类的熵
为什么又引出了信息增益比？
信息增益偏向于选择取值数目多的特征（高基数特征）。
举个例子：
假设你有一个“身份证号码”这种特征，它对每个样本都是唯一的。用这个特征划分数据集，每个子集只包含一个样本，那么熵就变成了 0，信息增益最大。但显然这不具有泛化能力，是过拟合的表现。
ID3 算法中从“信息增益”到“信息增益比”的本质动因。下面我逐步解释：

对于缺失值的处理可以分为两个子问题：
问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）
针对问题一，C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
针对问题二，C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

2. 信息增益（Information Gain）

信息增益度量的是某个特征 对熵的减少程度，即这个特征对分类的不确定性的减少能力。

$$Gain(S,A)=Entropy(S)-\sum _{v\in Values(A)}\frac{|S_v|}{|S|}Entropy(S_v)$$

Site Unreachable

问题: 1. 为什么需要加权

三、解决方法：信息增益比（Gain Ratio）

为了解决信息增益对取值多的特征的偏好问题，C4.5算法引入了“信息增益比”，它对信息增益进行了一种归一化处理：

$$GainRatio(S,A)=\frac{Gain(S,A)}{IV(A)}$$

其中，IV(A) 是“固有值”（Intrinsic Value）或“分裂信息”，度量了属性 A 的取值分布：

$$IV(A)=-\sum _{v\in Values(A)}\frac{|S_v|}{|S|}{\log }_2\left(\frac{|S_v|}{|S|}\right)$$

如果一个属性有很多不同取值，它的 IV 会很大，从而 降低 GainRatio 的值，防止偏好过拟合属性。

决策树中的GENI指数，有了熵 为什么还需要定义GENIm 意义是什么

**既然有“熵（Entropy）”了，为什么还要提出 Gini 指数（Gini Index）？**这是理解不同决策树算法设计哲学的关键。

一、Gini 指数是什么？

Gini 指数是 CART（Classification and Regression Tree）决策树中使用的划分标准。它度量的是 “集合的纯度”，公式如下：

$$Gini(S)=1-\sum _{i=1}^k{p}_i^2$$

其中：

• $p_i$ 是样本属于第 $i$ 类的概率。
• $k$ 是分类的类别数。

它的含义是：从集合中随机抽取两个样本，其类别不一致的概率。

---

🔍 二、Gini 与 熵（Entropy）对比

指标	含义	数学特性	倾向偏好
熵（Entropy）	信息的不确定性	使用对数，计算更复杂	倾向于选择样本分布较平衡的划分
Gini 指数	样本不一致的概率（纯度度量）	仅使用平方，计算简单	更偏好多数类样本的划分

✨ 相同点：

• 都是评估“划分好坏”的指标，值越小越纯。

🔧 不同点（重点）：

• Gini 指数计算更快，适合大数据场景。
• 熵更贴近信息论，理论更严谨，但计算开销大（因为有对数运算）。
• 两者在分类表现上通常相差不大，但 CART 使用 Gini，是出于计算效率和工程实践的考虑。

---

三、那为什么还要提出 Gini？

1. 工程效率高
2. 不同算法设计理念：

• ID3/C4.5：强调信息论基础（熵 → 信息增益/增益比）
• CART：强调分类纯度（Gini）和工程效率，同时支持 二叉树结构

Gini 指数是一种计算更快、工程上更高效的“纯度”衡量方法，虽然它不如熵有信息论的严密性，但在实践中依然非常有效，尤其在 CART 决策树和随机森林中非常常用。

总结：ID3 容易过拟合的原因
没有剪枝 树生长到完全拟合训练数据，泛化能力差

如何用决策树、朴素贝叶斯、KNN判断“要不要去见相亲对象”？

假设我们有一个相亲对象的样本，包含以下特征：

• 年龄（25, 30, 35）
• 收入（高、中、低）
• 教育程度（本科、硕士、博士）
• 兴趣爱好匹配度（高、中、低）
• 颜值（高、中、低）
• 是否抽烟（是、否）

目标：决定是否去见这个相亲对象（是/否）。

---

1. 决策树（Decision Tree）—— 最符合人类思维

如何界定问题？

决策树会像人一样，一步步做**“if-else”判断**，比如：

1. 颜值是否 ≥ 中？
   • 是 → 继续判断
   • 否 → 不去见
2. 收入是否 ≥ 中？
   • 是 → 继续判断
   • 否 → 不去见
3. 是否抽烟？
   • 是 → 不去见
   • 否 → 去见

决策树模型训练

• 输入：历史相亲数据（特征 + 是否去见）
• 输出：一棵树，自动选择最优分裂特征（如先按“颜值”分裂，再按“收入”等）
• 预测：新样本按树的分支走，最终决定“见”或“不见”

✅ 优点：

• 解释性强（可以画出树，知道为什么决定见或不见）。
• 不需要概率假设，直接基于规则判断。

❌ 缺点：

• 可能过拟合（如果树太深，会记住噪声数据）。

---

2. 朴素贝叶斯（Naive Bayes）—— 基于概率

如何界定问题？

朴素贝叶斯计算：
P(去见 | 年龄,收入,教育,兴趣,颜值,抽烟)
即：在已知这些特征的情况下，“去见”的概率是多少？

计算步骤

1. 计算先验概率（历史数据中“去见”和“不去见”的比例）：

   • P(去见) = 历史中去见的次数 / 总次数
   • P(不去见) = 1 - P(去见)

2. 计算条件概率（每个特征在“去见”和“不去见”情况下的分布）：

   • P(年龄=30 | 去见) = 历史中“去见”且年龄=30的比例
   • P(收入=高 | 去见) = 历史中“去见”且收入=高的比例
   • …（其他特征类似）

3. 预测新样本：

   • 计算 P(去见 | 特征) ∝ P(去见) × P(年龄|去见) × P(收入|去见) × …
   • 计算 P(不去见 | 特征) ∝ P(不去见) × P(年龄|不去见) × P(收入|不去见) × …
   • 比较两者，选概率大的作为预测结果。

✅ 优点：

• 适合小数据集（计算快）。
• 在文本分类（如垃圾邮件）等场景表现好。

❌ 缺点：

• 要求特征独立（现实中“收入”和“教育”可能相关，但模型假设它们无关）。
• 需要概率估计（如果某个特征在训练集没出现，概率=0，导致预测失效）。

---

3. KNN（K-最近邻）—— 基于相似度

如何界定问题？

KNN 的思路是：
“找到历史上最相似的K个相亲对象，看他们大多数是见还是不见，照搬结果”

计算步骤

1. 定义相似度（距离）：

   • 数值特征（如年龄）：用欧氏距离 |年龄1 - 年龄2|
   • 类别特征（如收入、教育）：如果相同=0，不同=1（汉明距离）

2. 计算新样本与所有历史样本的距离，找到最相似的K个（如K=5）。

3. 投票决定：

   • 如果5个邻居中，3个去见了，2个没见 → 预测“去见”

✅ 优点：

• 无需训练，直接比较数据。
• 适合特征间关系复杂的情况。

❌ 缺点：

• 计算慢（每次预测都要比较所有历史数据）。
• 需要定义合适的距离度量（如“颜值”和“收入”怎么加权？）。
• 对异常值敏感（如果邻居里有错误数据，预测会出错）。

方法	如何计算？	优点	缺点	适用场景
决策树	if-else 规则，按特征分裂	解释性强，计算快	可能过拟合	需要可解释性的决策（如相亲、贷款审批）
朴素贝叶斯	计算 P(去见|特征)	适合小数据，计算快	要求特征独立，概率估计不准	文本分类（如垃圾邮件）
KNN	找最相似的K个样本，投票	无需训练，适应复杂关系	计算慢，需要定义距离	推荐系统（如“相似用户喜欢什么”）

• 如果想快速做可解释的决策 → 决策树（最符合人类思维）
• 如果有大量统计数据（如相亲网站） → 朴素贝叶斯（但现实中很难准确估计概率）
• 如果想找相似案例参考 → KNN（但计算成本高，普通人难用）

因此，日常生活中，人们更倾向于用决策树式的思维（一步步做判断），而不是贝叶斯或KNN的复杂计算。

在构建决策树时，容易出现过拟合的问题，特别是在训练数据噪声较大或样本较少时。为了解决这一问题，引入了**剪枝（Pruning）**机制。

剪枝有两种主要策略：

---

🌱 一、预剪枝（Pre-Pruning）

在决策树生成过程中提前终止划分，即当某些条件满足时，就不再继续划分节点。

✅ 常见的停止条件：

• 划分后信息增益小于某个阈值。
• 当前节点样本数低于某个阈值。
• 当前节点纯度已经很高（如大多数样本属于同一类）。
• 达到预设的最大树深度或最大叶节点数。

优点：

• 减少模型复杂度，避免过拟合。
• 训练速度快。

❌ 缺点：

• 可能过早停止划分，导致欠拟合。
• 决策是局部的、贪婪的，不一定是全局最优。

---

🌲 二、后剪枝（Post-Pruning）

✅ 定义：

先构建一棵完全生长的决策树，然后再从底向上回溯地剪去一些子树，用更简单的子结构替代。

✅ 常见的策略：

• 使用独立的验证集评估剪枝后的准确率，如果剪枝后性能提升（或下降很少），就保留剪枝。

• 使用最小描述长度原则（MDL）或代价复杂度剪枝（如 CART 的 α 剪枝）。

• 评估剪枝影响时使用了全局信息，更可靠。

• 通常比预剪枝性能更好。

❌ 缺点：

• 需要训练完整的树，计算量更大。
• 需要额外的验证集或正则化参数。

特性	预剪枝（Pre-Pruning）	后剪枝（Post-Pruning）
执行时机	构建树的过程中	构建整棵树之后
是否构建完整树	否	是
优点	快速、简洁，防止过拟合	更稳健，效果通常更好
缺点	易欠拟合，贪婪	慢，需验证集或成本函数
是否全局最优	否（局部判断）	接近全局最优

---

🎯 举例说明：

假设你用决策树分类一个顾客是否会购买商品。

• 预剪枝：如果发现“客户年龄”这个特征划分后的信息增益太小，算法就放弃进一步划分该节点。
• 后剪枝：树先把“客户年龄 → 地区 → 是否有宠物”等都用来划分，生成完整树。然后回头发现，“是否有宠物”这层对分类没啥帮助，就砍掉这一层。

举个例子：

假设你有一个“年龄”特征，是连续型的：

离散化方式 A（粗粒度）：

• 0-30 → 青年
• 30-60 → 中年
• 60+ → 老年

离散化方式 B（细粒度）：

• 0-20、20-30、30-40、40-50、50-60、60+

你会发现：

• 方式 A 可能在某些特征上分不清楚购买与不购买；
• 方式 B 能捕捉更多模式，但也可能引入噪声或过度拟合。

---

⚠️ 离散化带来的潜在影响总结：

离散化粒度	优点	缺点
粗粒度（少区间）	模型简洁，泛化能力好	信息损失，容易欠拟合
细粒度（多区间）	能捕捉复杂关系，精度可能提高	容易过拟合，计算开销大

---

🛠 那该怎么做呢？有没有推荐方法？

✅ 1. 不用手动离散化，直接用连续特征

现代决策树算法（如 CART）可以直接处理连续值，自动找到最佳划分点（通过遍历所有可能的切分点）。这是推荐的做法。

✅ 2. 如果必须离散化，可以使用以下技巧：

• 等频划分：每个区间样本数差不多（抗不均衡）
• 等距划分：区间长度相同（适合均匀分布）
• 基于熵/信息增益的监督划分：选择能提升模型性能的切分点（更智能）

✅ 3. 交叉验证选择最优区间数

你可以尝试不同的离散化粒度，并通过交叉验证选出在验证集上表现最好的。

使用决策树时需要注意的关键点

1. 数据预处理

(1) 是否需要归一化（Normalization）？

• 决策树不需要归一化！
  • 决策树基于特征阈值（如 年龄 > 30）进行分裂，不受特征尺度影响。
  • 归一化（如 Min-Max、Z-Score）神经网络等距离敏感模型是必要的，但对树模型无影响。

(2) 缺失值处理

• 决策树可以直接处理缺失值（如 CART 算法），但不同库的实现不同：
  • sklearn.tree 不支持缺失值，需提前填充（如均值、中位数）。
  • XGBoost、LightGBM 等高级树模型可自动处理缺失值。

(3) 类别特征（Categorical Features）

• 需要编码（如 One-Hot、Label Encoding），因为决策树只能处理数值特征。
  • sklearn 的决策树不支持直接输入字符串类别，需先转换。
  • CatBoost 等算法可自动处理类别特征。

---

2. 防止过拟合（Overfitting）

决策树容易过拟合（生成过于复杂的树），需采用以下策略：

(1) 剪枝（Pruning）

• 预剪枝（Pre-Pruning）：限制树的生长

  • max_depth（最大深度，如 3-5 层）
  • min_samples_split（节点最小样本数，如 10）
  • min_samples_leaf（叶子节点最小样本数，如 5）
  • max_features（每节点考虑的最大特征数，如 sqrt(n_features)）

• 后剪枝（Post-Pruning）（如 CART 的 ccp_alpha）

  from sklearn.tree import DecisionTreeClassifier
  model = DecisionTreeClassifier(ccp_alpha=0.01)  # 剪枝强度

(2) 交叉验证调参

• 用 GridSearchCV 搜索最佳超参数：

  from sklearn.model_selection import GridSearchCV
  params = {"max_depth": [3, 5, 7], "min_samples_split": [5, 10, 20]}
  grid = GridSearchCV(DecisionTreeClassifier(), params, cv=5)
  grid.fit(X, y)
  print(grid.best_params_)

---

3. 特征选择

• 决策树会自动选择重要特征（通过信息增益/基尼指数），但仍需注意：
  • 高基数特征（如 用户ID）可能导致过拟合，需删除或分箱。
  • 相关性高的特征可能被重复选择，可先用 VIF 或 相关系数矩阵 去冗余。

---

4. 类别不平衡问题

• 如果目标变量类别不平衡（如 90% 负样本，10% 正样本）：
  • 使用 class_weight="balanced" 调整类别权重：

    model = DecisionTreeClassifier(class_weight="balanced")

  • 或采用过采样（SMOTE）/欠采样。

---

5. 决策树的局限性

问题	影响	解决方案
高方差（不稳定）	数据微小变化会导致完全不同的树	用集成方法（随机森林、GBDT）
无法外推	只能预测训练集覆盖的范围（如年龄>100的数据）	结合回归模型（如梯度提升树）
忽略特征间交互	可能错过重要组合（如“年龄+收入”）	手动构造交互特征

---

6. 模型解释性

• 可视化决策树（适用于小树）：

  from sklearn.tree import plot_tree
  import matplotlib.pyplot as plt
  plt.figure(figsize=(12, 8))
  plot_tree(model, feature_names=X.columns, filled=True)
  plt.show()

• 特征重要性：

  importance = model.feature_importances_
  print(pd.DataFrame({"Feature": X.columns, "Importance": importance}))

---

7. 选择适合的决策树算法

算法	特点	适用场景
ID3	使用信息增益，只能处理分类	教学用途（已过时）
C4.5	改进ID3，支持连续值和剪枝	小规模分类任务
CART	支持分类和回归，默认用基尼指数	最常用（sklearn默认）
Random Forest	多棵树的集成，抗过拟合	高精度需求
XGBoost/LightGBM	梯度提升树，高性能	大数据、竞赛

✅ 数据预处理

• 类别特征编码（One-Hot/Label Encoding）
• 处理缺失值（填充或删除）
• 无需归一化

✅ 防止过拟合

• 限制 max_depth、min_samples_split
• 使用剪枝（ccp_alpha）
• 交叉验证调参

✅ 模型优化

• 处理类别不平衡（class_weight="balanced"）
• 检查特征重要性，删除无关特征

✅ 替代方案

• 单棵树不稳定 → 改用随机森林/XGBoost
• 需要更高解释性 → 可视化决策路径

最终建议

• 默认用 sklearn.tree.DecisionTreeClassifier（CART），调整 max_depth 防止过拟合。
• 如果数据量大或需要更高精度，用集成方法（如随机森林、XGBoost）。
• 决策树适合可解释性强的场景（如风控、医疗诊断），但在复杂任务中可能不如深度学习。