# 决策树

核心思想: 分而治之 (Divide and Conquer)。通过一系列规则对数据进行划分。

• ID3 算法
  • 核心指标：信息增益 (Information Gain).
  • 原理：选择能使熵 (Entropy) 下降最快的属性进行分裂。
  • 缺点：偏向于选择取值较多 (Pure) 的属性 (如 ID 号)。
• C4.5 算法
  • 核心指标：增益率 (Gain Ratio)。
  • 原理：在信息增益基础上除以 "分裂信息"(SplitInfo)，惩罚多值属性。
  • 优点：克服了 ID3 的偏见，能处理连续属性。

CART 算法：使用 ++ 基尼指数 (Gini Index)++，构建二叉树。

# 熵 (Entropy)

熵衡量数据的不确定性 (纯度)。

$$Info(D) = - \sum_{i} p_i \log_2(p_i)$$

场景: 10 个球，6 个红，4 个蓝。
p (红)=0.6, p (蓝)=0.4
Info(D)=-(0.6 xlog20.6+ 0.4 xl0g20.4)
提示: $\log_{2}{0.6} \approx -0.737 , \log_{2}{0.4} \approx -1.322$
Info(D)=-(0.6x-0.737.+0.4x-1.322)=-(-0.442-0:529)=0.971

熵为 0 表示完全纯 (只有一类)，熵为 1 表示最混乱 (各占一半)

# 信息增益 (Information Gain)

衡量按属性 A 分裂后，熵减少了多少。

$$Gain(A)=Info(D)- Info_A(D)$$

计算步骤:

1. 计算分裂前的总熵 Info(D) 。
2. 计算按属性 A 分裂后的加权平均熵 Info_A(D) 。

公式: \sum ( \text{子集样本数} / \text{总样本数} ) \times \text

3. 相减得到 Gain 。
4. 选择 Gain 最大的属性作为节点。

# 过拟合与剪枝

过拟合 (Overfitting): 树生长得太深，完美匹配训练数据，但在测试数据上表现差 (泛化能力弱)。

# 预剪枝 (Pre-pruning)

策略：在树生长过程中提前停止。

• 如：节点样本数小于阈值、信息增益小于阈值、树深度达到限制。
• 优点：速度快。
• 缺点：可能导致 "欠拟合"，错过后续可能的优秀分裂。

# 后剪枝 (Post-pruning)

策略：先生成完全树，再自底向上修剪。

• 方法：如果将子树替换为叶节点能降低错误率 (或代价复杂度)，则剪掉。
• 优点：通常保留更优的树。
• 缺点：计算代价高。

# 朴素贝叶斯 Naive Bayes

核心：基于贝叶斯定理 + 属性条件独立假设。

$$P(C \mid X) = \frac{P(X \mid C) \cdot P(C)}{P(X)}$$

由于分母 P (X) 对所有类别相同，只需比较分子:

$$\max: P(C) \times\prod P(x_i \mid C)$$

$P(C)$: 先验概率 (类别在训练集中出现的频率)。
$P(x_i \mid C)$: 在类别 C 中，属性 xi 出现的概率。

"朴素": 假设各属性 x...n 互不干扰 (如 "高富帅" 三个特征独立)。

# 拉普拉斯平滑 (Laplace Smoothing)

问题：如果新样本有一个特征值在训练集某类中从未出现，则 $P(x|C)=0$。连乘后整体概率为 0，导致无法预测。
解决方案:

$$P(x|C)=\frac{N_{xc}+1}{N_c+V}$$

$N_{xc}$: 该特征在 C 类中的计数。
$N_{c}$: 类样本总数。
$1$: 分子加 1。
$V$: 分母加该属性可能的取值个数 (类别数)。

例子：某类有 5 个样本，"已婚" 出现 0 次。属性有 3 种取值 (单 / 婚 / 离)。
修正概率 =(0+1)/(5+3)=1/8。

# K - 最近邻 KNN

特点：懒惰学习 (LazyLearning)，不建立模型，预测时才计算。

算法步骤

1. 计算测试样本与所有训练样本的距离。
2. 选取距离最近的 K 个邻居。
3. 投票: K 个邻居中哪一类最多，就归为哪一类。

关键要素

• 距离度量：欧氏距离 (最常用)、曼哈顿距离。
• K 的选择:
  • K 太小 (如 1): 对噪声敏感，易过拟合。
  • K 太大：边界模糊，易欠拟合。
• 数据标准化：必须做！否则大尺度属性会主导距离计算。