机器学习_Part2

决策树

基础决策树

决策树采用在特征空间中直接构造一系列决策超平面将特征空间分解为多个局部区域

决策树的基本组成部分：决策节点、分支和叶子

决策树的学习框架

决策树学习的基本过程可以概括为：从根节点开始，选择当前最优划分属性，对训练集进行划分，并对每个子节点递归地重复这一过程，直到满足停止条件为止。

伪代码如下：

函数 GenerateTree(训练集 D, 属性集 A):
	创建结点 node

	如果 D 中样本全属于同一类别 C:
		将 node 标记为类别 C 的叶结点
		返回 node

	如果 A 为空，或者 D 中样本在 A 上取值完全相同:
		将 node 标记为叶结点
		将 node 的类别设为 D 中样本数最多的类别
		返回 node

	从 A 中选择最优划分属性 a_*
	将 node 标记为以 a_* 为测试属性的内部结点

	对于 a_* 的每一个可能取值 v:
		令 D_v 表示 D 中在属性 a_* 上取值为 v 的样本子集

		如果 D_v 为空:
			创建叶结点 child
			将 child 的类别设为 D 中样本数最多的类别
			将 child 连接到 node
		否则:
			child = GenerateTree(D_v, A \ {a_*})
			将 child 连接到 node

	返回 node

其中，“选择最优划分属性”这一步可以根据不同算法采用不同标准：

• ID3 使用信息增益；
• C4.5 使用信息增益率；
• CART 常使用基尼指数。

连续值与缺失的处理

• 在实际问题中，决策树不仅要处理离散属性，还经常要面对连续值属性与缺失值属性。

1. 连续值的处理

• 对于连续属性，不能像离散属性那样直接按每个取值进行分支，因此通常需要先确定一个划分阈值 $t$，再将样本划分为两部分：
• $ x \le t \quad \text{与} \quad x > t $
• 常见做法是：
  • 先将该属性在训练集上的取值从小到大排序；
  • 在相邻取值之间选取若干候选切分点；
  • 分别计算每个候选切分点对应的划分指标；
  • 选择使指标最优的切分点作为当前划分阈值。
• 例如：
  • ID3 / C4.5 可以比较不同切分点下的信息增益或信息增益率；
  • CART 常选择使基尼指数或平方误差最小的切分点。
• 因此，对连续值属性的处理，本质上就是把“选择属性”进一步扩展为“选择属性 + 选择最佳切分点”。

2. 缺失值的处理

• 当某些样本在某个属性上的取值缺失时，会影响该属性是否应被选作划分属性，以及样本该被分到哪个分支。
• 常见处理思路包括：

（1）忽略缺失样本

• 在计算某个属性的划分指标时，只使用该属性取值已知的样本。
• 这种方法简单，但会损失部分信息。

（2）填补缺失值

• 可以先对缺失值进行预处理，再训练决策树，例如：
  • 用均值、中位数填补连续属性；
  • 用众数填补离散属性；
  • 或使用更复杂的插补方法。

（3）按概率分配到各分支

• 这是决策树中较经典的处理方式之一。
• 当样本在当前划分属性上缺失时，可按照已知样本落入各分支的比例，将该样本以不同权重分配到多个子结点。
• 这样可以尽量保留样本信息，而不是直接丢弃。

3. C4.5 中的典型做法

• C4.5 对缺失值有较系统的处理方式：
  • 在选择划分属性时，只利用该属性取值已知的样本计算信息增益率；
  • 同时根据非缺失样本所占比例，对该属性的评价结果进行调整；
  • 对于属性值缺失的样本，在向下分裂时按各分支概率分配权重。

4. 小结

• 连续值处理的关键在于：寻找最优切分点；
• 缺失值处理的关键在于：尽量减少信息损失，并合理决定样本去向；
• 这两类问题的处理能力，也是 C4.5、CART 比早期简单决策树更实用的重要原因。

决策树CLS，ID3，C4.5，CART

这几类算法的核心区别主要体现在“如何选择最优划分属性”上。

1. CLS 决策树

• CLS 可看作较早期的决策树学习思想，其基本过程与通用决策树框架一致：
  • 从根节点开始选择某个属性进行测试；
  • 按属性取值将样本划分到不同子节点；
  • 再递归生成各子树。
• 它强调“不断划分训练样本，使不同类别尽可能被区分开”。
• 可以认为后续的 ID3、C4.5、CART 等算法，都是在这一基本框架上进一步细化“划分准则”而形成的。

2. ID3 算法

• ID3 的核心是使用信息增益（Information Gain） 选择划分属性。
• 在介绍信息增益前，先定义信息熵。设数据集 $D$ 中第 $k$ 类样本所占比例为 $p_k$，则经验熵为：
• $ \mathrm{Ent}(D) = -\sum_{k=1}^{K} p_k \log_2 p_k $
• 熵越大，表示数据集的不确定性越高；熵越小，表示样本越“纯”。
• 若按属性 $a$ 对数据集 $D$ 划分，得到若干子集 $D^1, D^2, \dots, D^V$，则划分后的条件熵为： $ \mathrm{Ent}(D\mid a) = \sum_{v=1}^{V} \frac{\lvert D^v \rvert}{\lvert D \rvert}\mathrm{Ent}(D^v) $
• 因而属性 $a$ 的信息增益为：
• $ \mathrm{Gain}(D,a) = \mathrm{Ent}(D) - \mathrm{Ent}(D\mid a) $
• ID3 选择信息增益最大的属性作为当前结点的划分属性。

ID3 的特点：

• 优点：思想简单、实现方便、对离散属性处理自然；
• 缺点：偏向于选择取值数目较多的属性，容易造成过拟合；
• 一般不直接处理连续值属性，需要额外离散化。

3. C4.5 算法

• C4.5 是对 ID3 的改进，其核心思想是使用信息增益率（Gain Ratio） 来代替单纯的信息增益。
• 先定义属性 $a$ 的固有值：
• $ \mathrm{IV}(a) = -\sum_{v=1}^{V} \frac{\lvert D^v \rvert}{\lvert D \rvert}\log_2\frac{\lvert D^v \rvert}{\lvert D \rvert} $
• 则信息增益率定义为：
• $ \mathrm{Gain_ratio}(D,a) = \frac{\mathrm{Gain}(D,a)}{\mathrm{IV}(a)} $
• C4.5 通过引入分母 $\mathrm{IV}(a)$，削弱了 ID3 对“取值数很多的属性”的偏好。

C4.5 的特点：

• 能处理离散属性，也能通过选取最优切分点处理连续属性；
• 可以处理部分缺失值；
• 通常会结合剪枝策略提高泛化能力；
• 相比 ID3 更实用，也更常作为经典教学算法。

其中，C4.5 常采用后剪枝（post-pruning）思想：先生成一棵较大的树，再自底向上判断某个内部结点的子树是否值得保留。

一个常见的数学刻画方式是比较“保留子树”与“剪成叶结点”后的经验误差估计。

设某个结点对应的样本数为 $N$，若把该结点直接剪成叶结点，并将其类别记为该结点中样本数最多的类别，则该叶结点上的训练误分类样本数记为 $e$，其经验错误率可写为：

• $ \hat{R}_{\text{leaf}} = \frac{e}{N} $

若保留以该结点为根的整棵子树，设该子树共有 $L$ 个叶结点，第 $l$ 个叶结点覆盖的样本数为 $N_l$，误分类样本数为 $e_l$，则子树的经验错误率可写为：

• $ \hat{R}{\text{subtree}} = \sum{l=1}^{L} \frac{N_l}{N} \cdot \frac{e_l}{N_l} = \frac{\sum_{l=1}^{L} e_l}{N} $

如果只比较训练误差，往往会倾向于保留更大的子树，因为更复杂的树通常训练误差更小。因此 C4.5 的剪枝思想不是只看训练集拟合效果，而是进一步估计其泛化误差。

在课程层面可以把它理解为：对每个结点，比较“把它当成一个叶结点时的误差上界”和“保留整棵子树时的误差上界”。若剪成叶结点后的误差估计不大于保留子树的误差估计，就执行剪枝。

一种常见的近似写法是给经验误差加一个复杂度/不确定性修正项，例如记

• $ \tilde{R}{\text{leaf}} = \hat{R}{\text{leaf}} + \Omega_{\text{leaf}}, \qquad \tilde{R}{\text{subtree}} = \hat{R}{\text{subtree}} + \Omega_{\text{subtree}} $

其中，$\Omega$ 表示由于样本有限、模型复杂度不同而引入的误差修正。若满足

• $ \tilde{R}{\text{leaf}} \le \tilde{R}{\text{subtree}} $

则说明继续保留这棵子树并不能带来更好的泛化能力，于是就把该子树剪掉，用单个叶结点代替。

直观上看：

• 若子树虽然把训练样本分得很细，但只是“记住了训练集中的细节”，那么 $\tilde{R}_{\text{subtree}}$ 往往不会更优；
• 若子树确实捕捉到了稳定的判别结构，则保留子树时的误差估计会更小。

因此，C4.5 的剪枝本质上是在做一个“误差下降是否足以抵消模型复杂度增加”的判断，这也是它能缓解过拟合的重要原因。

ID3 与 C4.5 的比较

• ID3：按信息增益选属性；
• C4.5：按信息增益率选属性；
• ID3 更简单，但偏向多值属性；
• C4.5 对这一问题有改进，适用范围更广。

4. CART 算法

• CART（Classification and Regression Tree，分类与回归树）既可用于分类，也可用于回归。
• 与 ID3、C4.5 不同，CART 通常构造的是二叉树，即每次划分后一个结点只分成两个子结点。

对于分类问题，CART 常使用基尼指数（Gini Index） 选择划分属性。

• 设数据集 $D$ 中第 $k$ 类样本所占比例为 $p_k$，则基尼值定义为：
  • $ \mathrm{Gini}(D) = 1 - \sum_{k=1}^{K} p_k^2 $
• 基尼值反映数据集的不纯度：
  • 基尼值越小，说明数据集纯度越高；
  • 基尼值越大，说明样本混杂程度越高。
• 若按属性 $a$ 的某种划分方式将数据集分为两个子集 $D_1, D_2$，则划分后的基尼指数为： $ \mathrm{Gini_index}(D,a) = \frac{\lvert D_1 \rvert}{\lvert D \rvert}\mathrm{Gini}(D_1) + \frac{\lvert D_2 \rvert}{\lvert D \rvert}\mathrm{Gini}(D_2) $
• CART 选择使划分后基尼指数最小的属性及切分点。

对于回归问题，CART 一般使用平方误差最小化作为划分标准，即希望划分后各子区域内样本输出尽可能接近。

更具体地说，设当前结点对应的样本集合为

• $ D = {(x_i,y_i)}_{i=1}^{N} $

若选择第 $j$ 个特征及切分点 $t$ 进行划分，则可把样本分成两个区域：

• $ R_1(j,t) = {x \mid x^{(j)} \le t} $
• $ R_2(j,t) = {x \mid x^{(j)} > t} $

对于回归树，CART 假设每个区域上的预测输出都是一个常数。因此，若左、右两个区域分别预测为常数 $c_1,c_2$，则该次划分的平方误差目标可写为：

• $ \min_{j,t,c_1,c_2} \left[ \sum_{x_i \in R_1(j,t)} (y_i-c_1)^2 + \sum_{x_i \in R_2(j,t)} (y_i-c_2)^2 \right] $

其中，对固定的划分 $(j,t)$，要使区域内平方误差最小，最优常数其实就是该区域内样本输出的均值，即：

• $ c_1^* = \frac{1}{

  R_1

  }\sum_{x_i \in R_1(j,t)} y_i $

• $ c_2^* = \frac{1}{

  R_2

  }\sum_{x_i \in R_2(j,t)} y_i $

因此，CART 在回归中的核心就是：

• 枚举候选特征 $j$ 和候选切分点 $t$；
• 计算该划分下左右两个区域的平方误差和；
• 选择使误差最小的 $(j,t)$ 作为当前结点的最优划分。

也就是说，最优划分可记为：

• $ (j^,t^) = \arg\min_{j,t} \left[ \sum_{x_i \in R_1(j,t)} (y_i-c_1^)^2 + \sum_{x_i \in R_2(j,t)} (y_i-c_2^)^2 \right] $

找到最优划分后，再对左右子区域递归重复这一过程，直到满足停止条件为止。最终，每个叶结点对应一个区域，每个区域输出一个常数预测值。

所以，CART 回归树本质上是在输入空间上不断做二分，并用分段常数函数去逼近真实的回归函数。

CART 的特点：

• 既可用于分类，也可用于回归；
• 每次都进行二分，树结构更规整；
• 对连续属性处理较自然；
• 工程应用广泛，也是许多集成学习方法（如随机森林、GBDT）的基础。

ID3、C4.5 与 CART 的比较

• ID3：使用信息增益，主要用于分类；
• C4.5：使用信息增益率，是 ID3 的改进；
• CART：分类时使用基尼指数，回归时使用平方误差，并且生成的是二叉树。

多变量决策树

• 前面讨论的普通决策树大多是单变量决策树，即每个内部结点只测试一个属性，例如：
• $ x_j \le t $ 或“属性 $a$ 是否取某个值”。
• 多变量决策树则允许一个结点同时使用多个属性进行联合判定，其测试形式可以写成：
• $ \sum_{j=1}^{d} w_j x_j \le t $ 即通过一个线性组合来划分样本。
• 因此，多变量决策树在每个结点上对应的不再是坐标轴平行的切分，而是一个更一般的超平面划分。

多变量决策树的特点：

• 优点：
  • 表达能力更强；
  • 对某些需要多个属性共同决定类别的问题，树的规模可能更小；
  • 能表示斜着切分特征空间的决策边界。
• 缺点：
  • 训练过程更复杂；
  • 结点上需要同时确定多个参数，优化难度更高；
  • 可解释性通常弱于单变量决策树。
• 因而在实际中，单变量决策树因结构清晰、易于解释而更常见；多变量决策树则更强调模型表达能力。

CART树的实际应用

• CART 树在实际中应用非常广泛，因为它既能处理分类问题，也能处理回归问题，并且结构清晰、易于实现。
• 常见应用包括：
  • 分类任务：如用户画像分类、信用审批、医学诊断、垃圾邮件识别等；
  • 回归任务：如房价预测、销量预测、风险评分、温度或流量预测等；
  • 作为集成学习的基学习器：随机森林、GBDT、XGBoost 等方法都大量使用 CART 树作为基础模型。
• 在工程中，单棵 CART 树虽然可解释性强，但泛化能力有时有限，因此经常作为更复杂集成模型的组成部分。

划分输入空间

• CART 的基本思想是通过递归二分，不断把输入空间划分成若干个简单区域。
• 设输入空间为 $\mathcal{X}$，每次在某个结点选择一个属性及其切分点，例如：
  • $ x_j \le t $ 这样就把当前区域划分为两个子区域： $ R_1 = {x \mid x_j \le t}, \qquad R_2 = {x \mid x_j > t} $
• 随着树不断生长，输入空间被划分为越来越多的互不重叠的子区域： $ \mathcal{X} = R_1 \cup R_2 \cup \cdots \cup R_M $
• 对于分类树，每个区域对应一个类别标签；
• 对于回归树，每个区域对应一个常数输出，通常取该区域训练样本输出的均值。
• 因此，CART 本质上是在做分段建模：
  • 分类时是分段常值分类；
  • 回归时是分段常值回归。

对于回归树，如果第 $m$ 个区域记为 $R_m$，其预测值记为 $c_m$，则模型可写为：

• $ f(x) = \sum_{m=1}^{M} c_m I(x \in R_m) $

其中 $I(\cdot)$ 为示性函数。

代价复杂度剪枝

• 如果让 CART 树无限制地生长，训练误差会不断减小，但模型很容易对训练样本学得过细，从而出现过拟合。
• 因此，CART 通常采用代价复杂度剪枝（Cost-Complexity Pruning） 来控制树的规模。

其核心思想是：在考虑经验误差的同时，对树的复杂度加入惩罚项。定义代价复杂度函数为：

• $ C_{\alpha}(T) = C(T) + \alpha \lvert T \rvert $

其中：

• $T$ 表示当前子树；
• $C(T)$ 表示树在训练数据上的误差；
• $\lvert T \rvert$ 表示树的叶结点个数；

• $\alpha \ge 0$ 为复杂度惩罚参数。

• 当 $\alpha$ 较小时，更重视拟合训练数据，得到的树通常更大；
• 当 $\alpha$ 较大时，更重视模型简单性，得到的树通常更小。

更具体地说，设 $T_t$ 表示以内部结点 $t$ 为根的子树，$\lvert T_t \rvert$ 表示该子树的叶结点数。若把整棵子树 $T_t$ 剪掉，并直接把结点 $t$ 变成一个叶结点，则可以比较：

• 保留子树时的代价复杂度：
  • $ C_{\alpha}(T_t) = C(T_t) + \alpha \lvert T_t \rvert $
• 剪成单叶结点时的代价复杂度：
  • $ C_{\alpha}(t) = C(t) + \alpha $

其中，$C(T_t)$ 表示该子树所有叶结点上的总误差，$C(t)$ 表示把它整体看作一个叶结点后的误差。

因此，若满足

• $ C_{\alpha}(t) \le C_{\alpha}(T_t) $

就说明从“误差 + 复杂度惩罚”的角度看，没有必要继续保留这棵子树，于是可以将其剪去。

进一步整理上式，可得：

• $ C(t) + \alpha \le C(T_t) + \alpha \lvert T_t \rvert $
• $ C(t) - C(T_t) \le \alpha (\lvert T_t \rvert - 1) $

于是可以定义该内部结点对应的临界参数：

• $ g(t) = \frac{C(t) - C(T_t)}{\lvert T_t \rvert - 1} $

$g(t)$ 的含义可以理解为：剪去这棵子树时，平均每减少一个叶结点所付出的误差代价。

• 若某个结点的 $g(t)$ 很小，说明删掉这棵子树几乎不会显著增大误差，但却能明显降低模型复杂度，因此它更适合优先被剪掉；
• 若 $g(t)$ 很大，说明这棵子树对降低误差作用明显，就不应轻易删除。

因此，CART 剪枝通常会：

• 先从完整树出发；
• 对每个内部结点计算对应的 $g(t)$；
• 优先剪去 $g(t)$ 最小的子树；
• 逐步得到一系列从“大树”到“小树”的候选子树；
• 最后再用验证集或交叉验证选择泛化效果最好的那一棵。

代价复杂度剪枝的一般过程是：

• 先生成一棵较大的完整树；
• 自底向上考察内部结点，比较“保留子树”和“将该子树剪成一个叶结点”后的代价复杂度；
• 每次剪去使代价复杂度下降最明显的子树；
• 由此得到一系列嵌套的候选子树；

• 再通过验证集或交叉验证，从这些候选子树中选出泛化能力最好的那一棵。

• 这种方法的优点是：既考虑了训练误差，又抑制了模型复杂度，因此能够有效降低过拟合风险。

T-SNE可视化（似乎不是很重要）

SNE算法

• SNE（Stochastic Neighbor Embedding，随机近邻嵌入）是一种用于高维数据降维与可视化的方法，目标是在低维空间中尽量保持样本之间的邻近关系。
• 它的核心思想是：
  • 在高维空间中，用概率来描述“样本 $x_i$ 把 $x_j$ 看作邻居的程度”；
  • 在低维空间中，也构造类似的邻近概率；
  • 然后让低维分布尽量逼近高维分布。

在高维空间中，定义条件概率：

$ p_{j\mid i} = \frac{\exp\left(-\lVert x_i-x_j \rVert^2 / 2\sigma_i^2\right)}{\sum_{k \ne i} \exp\left(-\lVert x_i-x_k \rVert^2 / 2\sigma_i^2\right)} $

其中：

• $p_{j\mid i}$ 表示在高维空间中，点 $x_i$ 选择点 $x_j$ 作为其邻居的概率；
• $\sigma_i$ 控制以 $x_i$ 为中心的邻域范围。

在低维空间中，设点 $x_i$ 的低维表示为 $y_i$，则类似地定义：

$ q_{j\mid i} = \frac{\exp\left(-\lVert y_i-y_j \rVert^2\right)}{\sum_{k \ne i} \exp\left(-\lVert y_i-y_k \rVert^2\right)} $

SNE 通过最小化高维分布与低维分布之间的 KL 散度来学习低维表示：

$ C = \sum_i KL(P_i\mathrel{\Vert}Q_i) = \sum_i \sum_j p_{j\mid i} \log \frac{p_{j\mid i}}{q_{j\mid i}} $

• 当某两个样本在高维空间中互为近邻时，SNE 希望它们在低维空间中也尽量靠近。

SNE 的优点是能较好保留局部邻域结构，但也存在一些问题：

• 代价函数不对称，优化较复杂；
• 容易出现 crowding problem（拥挤问题），即高维空间中的中等距离关系在低维空间中难以合理表达。

T-SNE算法

• t-SNE（t-distributed Stochastic Neighbor Embedding）是在 SNE 基础上的改进方法，也是最常用的可视化降维技术之一。
• 它主要针对 SNE 的拥挤问题进行了改进，因此在二维、三维可视化上通常效果更好。

1. 高维空间中的相似度

• t-SNE 先将 SNE 中的条件概率改写为对称联合概率：
• $ p_{ij} = \frac{p_{j\mid i} + p_{i\mid j}}{2n} $
• 这样做后，相似度定义更加对称，也更便于优化。

1. 低维空间中的相似度

• 与 SNE 最大的不同在于：t-SNE 在低维空间中不再使用高斯分布，而是使用自由度为 1 的 t 分布（也就是柯西分布）来定义相似度： $ q_{ij} = \frac{\left(1+\lVert y_i-y_j \rVert^2\right)^{-1}}{\sum_{k \ne l} \left(1+\lVert y_k-y_l \rVert^2\right)^{-1}} $
• t 分布尾部更重，因此可以让低维空间中的远距离点分得更开，从而缓解拥挤问题。

1. 优化目标

• t-SNE 最小化高维联合分布 $P$ 和低维联合分布 $Q$ 之间的 KL 散度： $ C = KL(P\mathrel{\Vert}Q) = \sum_i \sum_j p_{ij}\log \frac{p_{ij}}{q_{ij}} $
• 其优化通常采用梯度下降法完成。

1. t-SNE 的特点

• 优点：
  • 非常适合高维数据的二维或三维可视化；
  • 能较好保留局部邻域结构；
  • 往往能把不同簇清晰地分开。
• 缺点：
  • 计算开销较大；
  • 更偏向于保留局部结构，对全局距离关系刻画不一定准确；
  • 可视化结果受超参数（如 perplexity）和初始化影响较大。

1. SNE 与 t-SNE 的比较

• SNE：
  • 使用条件概率描述邻近关系；
  • 低维空间中使用高斯分布；
  • 存在拥挤问题。
• t-SNE：
  • 使用对称联合概率；
  • 低维空间中使用重尾 t 分布；
  • 更适合可视化，实际应用更广泛。
• 因此，在数据分析中，t-SNE 常被用于观察高维特征是否形成聚类结构、不同类别是否可分，以及模型提取的特征表示效果如何。

聚类

• 聚类（Clustering） 是一种典型的无监督学习方法，其目标是在没有类别标签的情况下，根据样本之间的相似性将数据划分为若干组。
• 一般希望满足：
  • 外部指标：与某个“参考模型”进行比较
  • 内部指标
    • 类内相似度高：同一簇中的样本彼此接近；
    • 类间相似度低：不同簇中的样本彼此差异较大。
• 聚类常用于：
  • 用户分群；
  • 图像分割；
  • 异常检测；
  • 文档主题发现；
  • 数据预处理与可视化分析。
• 常见聚类方法包括：
  • 划分式聚类，如 K-means；
  • 层次聚类；
  • 密度聚类，如 DBSCAN；
  • 模型聚类，如高斯混合模型（GMM）。

Kmeans算法

• K-means 是最经典的划分式聚类算法之一，其基本思想是：给定簇数 $K$，将样本划分为 $K$ 个簇，并使每个样本尽量靠近其所属簇的中心。

1. 优化目标

• 设第 $k$ 个簇的中心为 $\mu_k$，则 K-means 的目标是最小化簇内平方和：
• $ J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \lVert x_i-\mu_k \rVert^2 $
• 也就是说，希望同一簇内样本到簇中心的距离尽可能小。

2. 算法步骤

• K-means 的基本流程如下：
  1. 随机初始化 $K$ 个聚类中心；
  2. 对每个样本，计算其到各聚类中心的距离，并将其分配到最近的中心；
  3. 对每个簇，重新计算该簇所有样本的均值，作为新的聚类中心；
  4. 重复步骤 2 和步骤 3，直到聚类中心不再明显变化，或达到迭代次数上限。

3. 特点

• 优点：
  • 原理简单；
  • 计算效率较高；
  • 适合处理大规模数据。
• 缺点：
  • 需要事先给定簇数 $K$；
  • 对初始中心敏感，可能陷入局部最优；
  • 对异常值较敏感；
  • 更适合近似球形、大小相近的簇。

4. 常见改进

• K-means++：改进初始中心的选取方式，减少陷入差解的概率；
• 可结合肘部法则、轮廓系数等方法辅助选择合适的 $K$ 值。

主成分分析（PCA）

• PCA（Principal Component Analysis，主成分分析）是一种常用的线性降维方法，目标是在尽量保留数据主要信息的前提下，将高维数据映射到低维空间。
• 它的核心思想是：寻找若干个新的正交坐标轴，使得数据在这些方向上的方差最大。

1. 基本思想

• 数据在某个方向上的方差越大，说明该方向包含的信息越多；
• 因此，PCA 选择方差最大的方向作为第一主成分；
• 再在与第一主成分正交的方向中选择方差最大的方向作为第二主成分；
• 依此类推，得到一组互相正交的主成分。

2. 数学形式

• 设样本中心化后的数据矩阵为 $X$，则协方差矩阵为：
• $ \Sigma = \frac{1}{n}X^T X $
• 对协方差矩阵做特征值分解：
• $ \Sigma v = \lambda v $
• 取最大的前 $d$ 个特征值对应的特征向量，组成投影矩阵，即可将原始数据投影到低维空间。

3. PCA 的作用

• 降低数据维度；
• 去除冗余信息；
• 压缩数据表示；
• 便于可视化；
• 在某些情况下还能减弱噪声影响。

4. PCA 的特点

• 优点：
  • 计算方法成熟；
  • 能较好保留全局线性结构；
  • 常作为机器学习预处理步骤。
• 缺点：
  • 只适用于线性降维；
  • 主成分通常缺乏直观语义解释；
  • 对非线性结构刻画能力有限。

KNN

• KNN（K-Nearest Neighbors，K 近邻）是一种基于实例的学习方法，可用于分类和回归。
• 它的基本思想是：对于一个新样本，在训练集中找到与它距离最近的 $K$ 个邻居，再根据这些邻居的信息做出预测。

1. KNN 分类

• 对于分类任务，KNN 通常采用多数表决：
  • 找出距离测试样本最近的 $K$ 个训练样本；
  • 统计这 $K$ 个近邻中各类别出现的次数；
  • 将出现次数最多的类别作为预测结果。

2. KNN 回归

• 对于回归任务，可以取最近 $K$ 个邻居输出值的平均值，或按距离加权平均，作为预测结果。

3. 距离度量

• KNN 的效果很大程度上依赖距离度量方式，常见的有：
  • 欧氏距离：

  $d(x,z) = \sqrt{\sum_{j=1}^{d}(x_j-z_j)^2}$

  • 曼哈顿距离；
  • 闵可夫斯基距离；
  • 余弦距离等。

4. KNN 的特点

• 优点：
  • 思想简单，容易实现；
  • 无需显式训练过程；
  • 对非线性决策边界有一定适应能力。
• 缺点：
  • 预测时计算量较大；
  • 对特征缩放敏感，因此常需要标准化；
  • 对噪声点和不平衡数据较敏感；
  • $K$ 的取值会显著影响结果。

5. KNN 中 K 值的影响

• $K$ 较小时，模型更容易受到噪声影响，预测结果不稳定；
• $K$ 较大时，模型更平滑，但可能忽略局部结构；
• 因此，通常通过验证集或交叉验证选择合适的 $K$。

• Previous
  机器学习_Part1.26
• Next
  机器学习_Part3.26