机器学习

# 机器学习

# 分类大纲

# 线性回归

核心任务：预测一个连续值（例如：房价、气温、电池剩余寿命）。 它试图找到一条直线（或高维超平面）来拟合数据点。

# 核心公式

模型假设输入特征 $x$ 和输出 $y$ 之间存在线性关系：

$$y = w^T x + b$$

# 损失函数 (Loss Function)

线性回归通常使用 均方误差 (Mean Squared Error, MSE)。目的是最小化预测值与真实值之间差值的平方和。

$$J(w, b) = \frac{1}{2m} \sum_{i=1}^{m} (y^{(i)} - \hat{y}^{(i)})^2$$

# 逻辑回归

核心任务：虽然叫 “回归”，但它实际上是解决 二分类 问题（例如：是否患病、是否点击广告）。 它预测的是事件发生的概率（0 到 1 之间的值）。

# 核心公式

它在线性回归的基础上，加了一个 激活函数 (Sigmoid Function)，把输出压缩到 $(0, 1)$ 之间。

$$h_\theta(x) = \text{sigmoid}(w^T x + b) = \frac{1}{1 + e^{-(w^T x + b)}}$$

# 损失函数 (Loss Function)

逻辑回归 不能 使用 MSE（均方误差），因为引入 Sigmoid 后，MSE 不再是凸函数，会导致梯度下降陷入局部最优解。

它使用对数损失 (Log Loss)，也叫 交叉熵损失 (Cross-Entropy Loss)：

$$J(w) = - \frac{1}{m} \sum_{i=1}^{m} [y^{(i)} \log(\hat{y}^{(i)}) + (1 - y^{(i)}) \log(1 - \hat{y}^{(i)})]$$

这个公式的物理意义是：极大似然估计 (Maximum Likelihood Estimation)。

# 支持向量机

在逻辑回归中，只要能把两类分开的线都可以。但在 SVM 中，我们追求 **“最宽的街道”**。

• 超平面 (Hyperplane)：就是那条分类的线（在高维是面）。
• 间隔 (Margin)：由于我们希望分类器不仅能分对训练数据，还能对未知数据有好的容错性，所以我们要找到一条线，让它离最近的样本点越远越好。这个 “最远距离” 的两倍就是间隔。
• 支持向量 (Support Vectors)：重点！ 并非所有的样本点都对确定这条线有贡献。只有离线最近的那几个点（即 “撑” 起街道宽度的点）决定了模型。这些点叫支持向量。

# 目标函数 (Objective Function)

我们想要最大化间隔。几何间隔的公式是 $\frac{1}{||w||}$。最大化 $\frac{1}{||w||}$ 等价于 最小化 $||w||^2$。

所以，硬间隔（Hard Margin）SVM 的原始优化目标是：

$$\min_{w,b} \frac{1}{2}||w||^2$$

$$\text{s.t.} \quad y_i(w^T x_i + b) \geq 1, \quad i=1, ..., m$$

(这里的约束条件是：所有样本点都必须被正确分类，且都在间隔之外)

# 对偶问题求解

求解过程可以分为三个阶段：构造拉格朗日函数 $\rightarrow$ 转化为对偶问题 $\rightarrow$ 利用 SMO 算法求解。

# 第一阶段：从 “原问题” 到 “拉格朗日函数”

# 1. 回顾原问题 (Primal Problem)

我们的目标是最小化 $w$ 的模长，同时保证分类正确：

$$\min_{w, b} \frac{1}{2} ||w||^2$$

$$\text{s.t.} \quad y_i(w^T x_i + b) \geq 1, \quad i=1, \dots, m$$

这是一个带约束的凸优化问题。为了消除约束，我们需要引入拉格朗日乘子 (Lagrange Multipliers) $\alpha_i$（其中 $\alpha_i \geq 0$）。

# 2. 构造拉格朗日函数

我们将约束条件融合到目标函数中：

$$\mathcal{L}(w, b, \alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^{m} \alpha_i [y_i(w^T x_i + b) - 1]$$

• 这个函数的物理意义是：如果约束被满足，第二项为负或 0，最小化 $\mathcal{L}$ 等同于原问题；如果约束被违背，第二项会变得非常大，迫使优化往满足约束的方向走。

# 第二阶段：推导对偶形式 (The Dual Form)

原问题是 “极小极大” 问题（$\min_{w,b} \max_{\alpha} \mathcal{L}$）。对偶问题是它的交换形式，即 “极大极小” 问题（$\max_{\alpha} \min_{w,b} \mathcal{L}$）。

我们需要先对 $w$ 和 $b$ 求偏导并令其为 0（求极小值），消掉这两个变量。

# 1. 求偏导

$$\frac{\partial \mathcal{L}}{\partial w} = w - \sum_{i=1}^{m} \alpha_i y_i x_i = 0 \quad \Rightarrow \quad w = \sum_{i=1}^{m} \alpha_i y_i x_i$$

$$\frac{\partial \mathcal{L}}{\partial b} = - \sum_{i=1}^{m} \alpha_i y_i = 0 \quad \Rightarrow \quad \sum_{i=1}^{m} \alpha_i y_i = 0$$

关键点：第一个公式 $w = \sum \alpha_i y_i x_i$ 告诉我们，权重向量 $w$ 只是数据点 $x_i$ 的线性组合。而且只有支持向量的 $\alpha_i > 0$，其他非支持向量的 $\alpha_i = 0$，这意味着 $w$ 只由少数支持向量决定。

# 2. 代回拉格朗日函数

将上面求出的 $w$ 代回 $\mathcal{L}(w, b, \alpha)$ 中，经过化简（推导过程略去繁琐的代数运算），我们得到了只包含 $\alpha$ 的对偶目标函数：

$$\max_{\alpha} \left( \sum_{i=1}^{m} \alpha_i - \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j (x_i^T x_j) \right)$$

# K - 近邻

KNN 没有显式的 “训练” 过程（它只是把数据存起来）。当来了一个新样本 $x_{new}$ 需要预测时，它执行以下三步：

1. 算距离：计算 $x_{new}$ 与训练集中所有样本点的距离。
2. 找邻居：按距离排序，选出最近的 $K$ 个点。
3. 做决策：
   • 分类任务：少数服从多数。看这 $K$ 个邻居里哪一类最多。
   • 回归任务：求平均值。计算这 $K$ 个邻居目标值的平均值作为预测结果。

三个关键要素:

1. 距离度量

   • 欧氏距离 (Euclidean Distance)：最常用。即两点间的直线距离。

     $$d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}$$

   • 曼哈顿距离 (Manhattan Distance)：城市街区距离（走直角）。

     $$d(x, y) = \sum_{i=1}^{n} |x_i - y_i|$$

   • 余弦相似度 (Cosine Similarity)：关注方向而非距离，常用于文本分类。

   特征缩放 (Feature Scaling) KNN 对数据的量纲极度敏感！

   • 例如：特征 A 是 “身高 (米)”(1.7-1.9)，特征 B 是 “工资 (元)”(5000-50000)。
   • 如果不归一化，工资的差值（几万）会完全掩盖身高的差值（零点几），导致 KNN 只看工资。
   • 结论：用 KNN 前必须进行归一化 (Normalization) 或标准化 (Standardization)。

2. $K$ 值的选择：

   • K 很小 (如 K=1) 模型极不稳定，容易受噪声点影响（如果最近的一个点是噪声，就预测错了）。决策边界非常曲折、破碎。低偏差，高方差 (Overfitting)
   • K 很大 (如 K=N) 模型过于简单。无论输入什么，都预测为训练集中数量最多的那一类。决策边界过于平滑。高偏差，低方差 (Underfitting)

3. 决策规则

   • 多数表决：默认规则。

   • 距离加权 (Weighted KNN)：离得近的邻居权重更大。比如权重为 $1/d$。这样可以缓解 $K$ 值较大时远距离点干扰决策的问题。

如何加速 KNN？

答案：不要暴力搜索，使用索引结构。

1. KD-Tree (k-Dimensional Tree)：
   • 一种对 $k$ 维空间进行划分的二叉树。
   • 核心思想：把数据像切蛋糕一样切成一块块的。查找时，先判断目标点在哪一块，通过剪枝（Pruning）排除掉大部分不可能包含最近邻的区域。
   • 缺点：当特征维度很高时（>20 维），KD-Tree 的效率会退化成线性扫描。
2. Ball Tree：
   • 使用超球面来划分空间，在高维数据上比 KD-Tree 表现稍好。

# 决策树

决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的 “纯度”(purity) 越来越高。

# 经典的属性划分方法：

# 1. 信息熵 & 信息增益 (ID3)

• 物理意义：熵越大，数据越混乱；熵越小，数据越纯。

• 公式：

$$H(D) = - \sum_{k=1}^{K} p_k \log_2 p_k$$

(其中 $p_k$ 是第 $k$ 类样本所占的比例)

• 决策逻辑：选择那个能让熵下降最快（即信息增益最大）的特征进行分裂。

$$\text{Gain}(D, A) = H(D) - \sum^{V}_{v=1}{\frac{|D^{v}|}{|D|}}H(D^{v})$$

import math

def Ent(a, b):

    if a == 0 or b == 0:

        return 0

    c = a + b

    a, b = a / c, b / c

    return -a * math.log2(a) - b * math.log2(b)

H_D = Ent(9, 5)

H_D_A1 = 5/14*Ent(2, 3) + 4/14*Ent(4, 0) + 5/14*Ent(2, 3)

Gain_A1 = H_D - H_D_A1

print(f'{Gain_A1=}')

• ID3 的致命缺点：它特别偏爱取值多的特征。
  • 例子：如果把 “身份证号” 作为一个特征，每个样本都不一样，纯度极高，但这对预测毫无意义。

# 2. 信息增益率 (Information Gain Ratio) —— C4.5 算法

• 为了修正 ID3 的偏见，C4.5 引入了惩罚项。它用 “信息增益” 除以该特征的 “固有熵”（Intrinsic Value）。

  $$\text{Gain\_Ratio}(D, A) = \frac{\text{Gain}(D, A)}{IV_A(A)}$$

• 特征取值越多，$IV_A(A)$ 越大，分母变大，增益率就被压低了。

import math

def Ent(a, b):

    if a == 0 or b == 0:

        return 0

    c = a + b

    a, b = a / c, b / c

    return -a * math.log2(a) - b * math.log2(b)

H_D = Ent(9, 5)

H_D_A1 = 5/14*Ent(2, 3) + 4/14*Ent(4, 0) + 5/14*Ent(2, 3)

Gain_A1 = H_D - H_D_A1

print(f'{Gain_A1=}')

IV_A1 = -5/14*math.log2(5/14) - 4/14*math.log2(4/14) - 5/14*math.log2(5/14)

Gain_Ratio_A1 = Gain_A1 / IV_A1

print(f'{Gain_Ratio_A1=}')

# 3. 基尼系数 (Gini Impurity) —— CART 算法 (最重要！)

现在的工业界主流算法（如 XGBoost, sklearn 的默认树）都使用 CART (Classification and Regression Tree)。

• 物理意义：从集合中随机抽取两个样本，它们类别不一致的概率。

• 公式：

  $$\text{Gini}(p) = 1 - \sum_{k=1}^{K} p_k^2$$

  $$\text{Gini}_{\text{index}}(D, a) = \sum^{V}_{v=1}{\frac{|D^v|}{|D|}\text{Gini}(D^v)}$$

• 决策逻辑：选择让分裂后基尼系数最小的特征。

💡 面试必问：为什么 CART 用 Gini 而不用熵？

1. 计算快：熵需要算 $\log$，计算机算对数很慢；Gini 只需要算乘法和减法。
2. 效果近似：在绝大多数情况下，Gini 和熵生成的树结构非常相似。

# 剪枝：防止过拟合

# A. 预剪枝 (Pre-Pruning)

在树生长过程中，提前停止。

• 策略：
  • 限制最大深度 ( max_depth )。
  • 限制叶子节点最少样本数 ( min_samples_leaf )。
  • 限制信息增益的阈值（如果增益太小就不分了）。
• 优缺点：速度快，但容易欠拟合（可能错失后续很好的分裂机会）。

# B. 后剪枝 (Post-Pruning)

先让树长到最大，然后自底向上地剪掉那些不重要的枝叶。

• 策略：如果剪掉某个子树，模型在验证集上的准确率没有下降（甚至上升），那就剪掉。
• 优缺点：泛化能力强，但计算代价大。

# 随机森林

随机森林属于 Bagging (Bootstrap Aggregating) 算法的代表。它的强大来自于两个 “随机”：

# A. 样本的随机性 (Bootstrap Sampling)

• 怎么做：每棵树训练时，不是用所有的训练数据，而是有放回地随机抽取 $N$ 个样本（和原始数据集大小一样）。
• 结果：因为是有放回抽取，原始数据中大约有 36.8% 的样本不会出现在某棵树的训练集中。这些没被选中的数据叫做 袋外数据 (Out-of-Bag, OOB)。
• 目的：让每棵树看到的训练数据都不太一样，增加树之间的差异性 (Diversity)。

# B. 特征的随机性 (Feature Randomness)

• 怎么做：在决策树的每一个节点需要分裂时，不是从所有 $M$ 个特征中找最好的，而是先随机选出 $k$ 个特征（通常 $k = \sqrt{M}$ 或 $\log_2 M$），然后只在这 $k$ 个特征里找最好的分裂点。
• 目的：这是随机森林的点睛之笔！它防止了某些 “超级特征” 主导所有树的生长，强迫模型去关注那些次要但有用的特征，进一步降低了树之间的相关性。

# 面试问题：

Q: 随机森林能处理缺失值吗？

• A: 能。
  • 方法 1：简单填充（中位数 / 众数）。
  • 方法 2（进阶）：利用相似度矩阵。先简单填充，然后跑一遍随机森林，计算样本间的相似度（看落在同一个叶子节点的频率），用相似样本的值加权填充，再迭代训练。

# Adaboost

Adaboost 通常使用最简单的 决策树桩 (Decision Stump) 作为基分类器（即只有一层深度的树，切一刀）。

# 算法流程

# Step 1: 初始化权重

最开始，所有 $N$ 个训练样本的权重是平等的，都是 $1/N$。

# Step 2: 迭代训练 (Repeat T rounds)

在每一轮 $t$ 中：

1. 训练：用当前权重的样本训练一个弱分类器 $h_t(x)$。
2. 算错误率 ($\epsilon_t$)：看它分错了多少权重的数据。
3. 算话语权 ($\alpha_t$)：计算这个分类器在最终投票时的权重。
   • 公式：$\alpha_t = \frac{1}{2} \ln\left(\frac{1-\epsilon_t}{\epsilon_t}\right)$
   • 直觉：如果错误率越低（$\epsilon_t$ 小），$\alpha_t$ 就越大（话语权越重）。如果错误率是 50%（瞎猜），$\alpha_t$ 就是 0（废话不论）。
4. 更新样本权重 ($w$)：关键步骤！
   • 分错的样本：权重变大 $\rightarrow$ w_{new} = w_{old} \cdot e^
   • 分对的样本：权重变小 $\rightarrow$ w_{new} = w_{old} \cdot e^
   • 最后做归一化，让权重和为 1。

# Step 3: 最终组合

把这 $T$ 个弱分类器线性组合起来，话语权大的说了算：

$$H(x) = \text{sign}\left(\sum_{t=1}^{T} \alpha_t h_t(x)\right)$$

# 图解核心差异：Adaboost vs 随机森林

# 面试问题：

Q: 对于无法接受带权样本的个体学习器，应该采样什么办法调整权重？

• A: 应该采用 “重采样法” 来处理，像决策树这种可以处理带权样本的学习器，可以直接应用到权重中去。

# XGBoost

参考：躺懂 XGBoost，学不会来打我（doge）_哔哩哔哩_bilibili

# 算法流程

# 前向分步算法

$$\hat{y}^{(t)}=\hat{y}^{(t-1)}+f_{t}(x)$$

# 正则化项

XGBoost 显式地定义了正则化：

$$\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2$$

• $\gamma T$：叶子节点数量的惩罚（相当于 L0 正则，防止树太深）。
• $\frac{1}{2} \lambda ||w||^2$：叶子权重的 L2 正则（防止分数太极端）。

# 目标函数：

$$\sum^{N}_{i=1}L(y_i, \hat{y}^{(t)}_i)+\sum^{t}_{j=1}\Omega(f_j)$$

前 $t-1$ 棵树已经确定，仅需要优化第 $t$ 棵树的值即可。

将 $\hat{y}_i^{(t)}$ 展开，并去掉前 $t-1$ 棵树的正则化项（因为它们已经是常数了），得到：

$$Obj^{(t)} = \sum_{i=1}^{n} l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2$$

换成以叶子节点的形式遍历，

$$Obj^{(t)} = [\sum_{j=1}^{T} [\sum_{i \in I_j}^{} l(y_i, \hat{y}_i^{(t-1)} + w_j)] + \frac{1}{2} \lambda w_j^2] + \gamma T$$

这里如果确定损失函数为均方损失，可以利用贪心可以求解每个叶子节点内的最优值。但是不同任务损失函数不同，需要确立一种跨损失函数的通用方法。

# 二阶泰勒展开 (The Magic Step)

这是 XGBoost 最核心的数学魔法。GBDT 只用到一阶导，而 XGBoost 对损失函数进行了二阶泰勒展开。

回顾泰勒公式：$f(x + \Delta x) \approx f(x) + f'(x)\Delta x + \frac{1}{2}f''(x)\Delta x^2$。

把 $w_j$ 看作 $\Delta x$，我们展开：

$l(y_i, \hat{y}_i^{(t-1)} + w_j)\approx l(y_i, \hat{y}_i^{(t-1)})+l^{'}(y_i,\hat{y}_i^{(t-1)})w_j+\frac{1}{2} l^{''}(y_i, \hat{y}_i^{(t-1)})w_j^2$

其中，第一项为常量，可删去，可表示为

$$l(y_i, \hat{y}_i^{(t-1)} + w_j)\approx g_iw_j+\frac{1}{2} h_iw_j^2$$

其中，

• $g_i$ (一阶导 / 梯度)：$l^{'}(y_i,\hat{y}_i^{(t-1)})$
• $h_i$ (二阶导 / 海森矩阵)：$l^{''}(y_i,\hat{y}_i^{(t-1)})$

因此，整体目标函数可写为：

$$Obj^{(t)} = \sum_{j=1}^{T} [\sum_{i \in I_j}^{} (g_iw_j+\frac{1}{2} h_iw_j^2) + \frac{1}{2} \lambda w_j^2] + \gamma T \\ =\sum_{j=1}^{T} [w_j\sum_{i \in I_j}^{} g_i+\frac{1}{2}w_j^2\sum_{i \in I_j} h_i + \frac{1}{2} \lambda w_j^2] + \gamma T \\ =\sum_{j=1}^{T} [w_j\sum_{i \in I_j}^{} g_i+\frac{1}{2}w_j^2(\sum_{i \in I_j} h_i + \lambda) ] + \gamma T$$

定义该叶子上所有样本的 梯度之和：

• $G_j = \sum_{i \in I_j} g_i$
• $H_j = \sum_{i \in I_j} h_i$

目标函数变形为：

$$Obj^{(t)} = \sum_{j=1}^{T} [ G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2 ] + \gamma T$$

# 求解最优叶子权重 (Structure Score)

现在，目标函数变成了关于 $w_j$ 的一元二次函数（抛物线）：

$$f(w_j) = A w_j^2 + B w_j + C$$

其中 $A = \frac{1}{2}(H_j + \lambda)$，$B = G_j$。

对于一元二次方程，极值点在 $w = -B / 2A$ 处取得。

所以，给定树结构的情况下，第 $j$ 个叶子节点最优的叶子权重 $w_j^*$ 为：

$$w_j^* = - \frac{G_j}{H_j + \lambda}$$

把 $w_j^*$ 代回目标函数，得到这棵树的最小损失值（打分）：

$$Obj^* = - \frac{1}{2} \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T$$

💡 物理意义：

• $G_j$ 代表这一堆样本的一阶梯度总和（想要移动的方向）。
• $H_j$ 代表二阶曲率（移动的阻力）。
• $\lambda$ 是正则化项，增加分母，让计算出的权重 $w_j^*$ 不要太大（缩减）。
• $Obj^*$ 越小，说明这个树结构越好。

# 分裂节点 (Split Finding)

我们要找一棵树，但不可能遍历所有可能的树结构。XGBoost 使用贪心算法，从根节点开始，尝试每一次分裂。

假设我们要把一个节点分裂成左子节点 (L) 和 右子节点 (R)。

# 1. 分裂增益 (Gain)

我们要判断 “这一刀切下去值不值”。

• 切分前的分数：Score_{Parent} =\gamma -\frac{1}{2} \frac{(G_L + G_R)^2}
• 切分后的分数：$Score_{Left} + Score_{Right} = 2\gamma -\frac{1}{2}(\frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda})$

注意：这里每个节点的 G 和 H 都是已知的

增益公式 (Gain) = (切分后分数) - (切分前分数) - (引入新叶子的代价)：

$$Gain = \frac{1}{2} \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} \right] - \gamma$$

# 2. 决策逻辑

1. 遍历所有特征。
2. 对于每个特征，遍历所有可能的切分点（或者使用近 似分位数算法）。
3. 计算 $Gain$。
4. 找到 $Gain$ 最大的特征和切分点进行分裂。
5. 如果 $Gain < 0$（或者小于某个阈值），则停止分裂（这其实就是预剪枝）。

如何优化特征值排序：

• 筛选特征：列采样：（1）按树随机：直接随机选择特征，不更改；（2）按层随机（灵活）：每层都重新随机选取特征。

• 筛选特征值：（1）分桶；（2）加权分位法：根据每个样本的$h_i$ 进行分桶。

# 面试介绍

XGBoost（Extreme Gradient Boosting）本质上是 GBDT（Gradient Boosting Decision Tree）的一种高效、并行的工程实现。

它的基本思想是 Boosting（提升） 策略，即通过串行地迭代训练多个弱学习器（通常是 CART 回归树），每棵树都在拟合上一轮模型的残差（或者更准确地说是负梯度），最后将所有树的预测值加权求和得到最终结果。

二阶泰勒展开（最核心的区别）

话术：

“传统的 GBDT 在优化目标函数时，通常只用到了一阶导数（梯度）。

而 XGBoost 对目标函数进行了 二阶泰勒展开。它同时利用了 一阶导数（$g_i$） 和 二阶导数（$h_i$, 海森矩阵） 来近似目标函数。

这样做的好处是：下降得更快，收敛更精确。这就好比牛顿法相比梯度下降法，收敛速度通常更快。”

正则化（防止过拟合）

话术：

“XGBoost 在目标函数中显式地加入了 正则化项（Regularization）。

它惩罚了叶子节点的个数（$\gamma T$） 和 叶子节点权重的 L2 模平方（$\frac{1}{2}\lambda ||w||^2$）。

这一项在传统的 GBDT 中通常没有，这使得 XGBoost 学习出来的树更加简单，抗过拟合能力更强。”

面试官可能会追问：“那它和 LightGBM 有什么区别？” 或者 “为什么现在不用它了？” 你可以主动在大结局提到。

话术： “总结一下，XGBoost 相比于传统 GBDT，引入了二阶导数、正则化项和特征并行化，在精度和速度上都达到了很好的平衡。不过，随着数据量达到亿级，后来的 LightGBM 通过 GOSS（单边梯度采样）和 EFB（互斥特征捆绑）进一步提升了训练速度和内存效率。 但在中小规模的表格数据上，XGBoost 依然是目前最稳健的选择之一。”

# 聚类

# K - 均值

假设数据簇是球状的。我们先随机插 $K$ 个旗子（质心），谁离旗子近就算谁的人；然后根据这些人的位置移动旗子，直到旗子不动为止。

# 算法流程 (EM 算法的特例)

1. 初始化：随机选择 $K$ 个点作为初始质心 (Centroids)。
2. E 步 (Assignment)：计算每个样本到 $K$ 个质心的距离，把它归到最近的那个质心所在的簇。
3. M 步 (Update)：重新计算每个簇的平均值，将质心移动到这个平均值位置。
4. 循环：重复 2 和 3，直到质心不再移动（收敛）。

# 目标函数 (Loss Function)

最小化 簇内平方误差和 (Within-Cluster Sum of Squares, WCSS)：

$$J = \sum_{j=1}^{K} \sum_{x \in C_j} ||x - \mu_j||^2$$

也就是让簇内尽可能紧凑。

# 面试问题

• Q：K 怎么选？

  肘部法则 (Elbow Method)：画出 K 值与 Loss 的曲线，找拐点（像手肘一样的位置）。

  轮廓系数 (Silhouette Coefficient)：结合了 “簇内紧密度” 和 “簇间分离度”。值在 $[-1, 1]$ 之间，越接近 1 越好。

• Q：初始点敏感吗？

  非常敏感。如果运气不好，初始点选在一堆，可能陷入局部最优。

  解法：使用 K-Means++。它的策略是 “让初始质心尽可能离得远”。

# DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 的算法流程其实非常像是在 “传染病毒” 或者 “发展下线”。

它的核心逻辑是：只要密度够大，就继续向外扩张，直到碰壁（密度不够）为止。

以下是详细的算法流程拆解：

# 1. 核心参数准备

在开始之前，必须定好两个参数（之前复习过的）：

• $\epsilon$ (Epsilon)：扫描半径（邻域大小）。
• MinPts：成为核心点所需的最小邻居数。

# 2. 算法详细步骤

DBSCAN 不需要预先指定 $K$ 个簇，它从数据集中任意一个未访问的点开始。

# 第一步：遍历所有点

我们有一个点集 $D$，开始遍历每一个点 $P$：

1. 如果 $P$ 已经被访问过（Visited），跳过，看下一个点。
2. 如果 $P$ 没被访问过，标记为 已访问。

# 第二步：判断是否为 “核心点” (Core Point)

计算 $P$ 在半径 $\epsilon$ 内的邻居数量（包括它自己）：

• 情况 A：邻居数 < MinPts
  • 说明这里很稀疏，$P$ 暂时是个噪声点 (Noise)。
  • 注意：这个 “噪声” 标记是暂时的，因为后面它可能会被其他核心点 “收编” 变成边界点。
  • 动作：结束对 $P$ 的处理，回到第一步循环。
• 情况 B：邻居数 $\ge$ MinPts
  • 说明 $P$ 是一个核心点。
  • 动作：创建一个新簇 (New Cluster)，把 $P$ 放进去，然后开始 **“扩张”**（进入第三步）。

# 第三步：扩张簇 (Expand Cluster) —— 核心逻辑

这是 DBSCAN 最关键的一步。一旦找到了一个核心点 $P$，我们就有了 “火种”，现在要让火烧起来。

1. 建立种子队列：把 $P$ 的所有邻居（除去 $P$ 自己）放到一个种子队列 (Seeds) 中。
2. 循环处理种子队列：
   • 从队列里取出一个点 $Q$。
   • 处理状态：
     • 如果 $Q$ 之前是 “噪声”，把它变成当前簇的成员（边界点）。
     • 如果 $Q$ 之前 “未访问”，标记为 “已访问”，并把 $Q$ 加入当前簇。
   • 检查 $Q$ 的潜力：
     • 计算 $Q$ 的邻居数量。
     • 如果 $Q$ 也是核心点（邻居数 $\ge$ MinPts）：说明 $Q$ 密度也很大，可以继续传染。把 $Q$ 的所有邻居都加到种子队列的末尾。
     • 如果 $Q$ 不是核心点：说明它是边界点，到此为止，不再向外拉人了。
3. 循环结束：当种子队列空了，说明这个簇能连通的地方都跑遍了。这个簇的生长结束。

# 第四步：继续遍历

回到第一步，继续找下一个未访问的点，直到所有点都被访问过。

# 层次聚类

# 算法详细流程

假设我们有 $N$ 个数据点。

• Step 1: 初始化
  • 把每个数据点看作一个独立的簇。
  • 此时我们有 $N$ 个簇：$C_1, C_2, \dots, C_N$。
  • 计算所有簇两两之间的距离矩阵 (Distance Matrix)（通常是 $N \times N$ 的矩阵）。
• Step 2: 寻找最近的两个簇
  • 在距离矩阵中找到距离最小的那两个簇（比如 $C_i$ 和 $C_j$）。
• Step 3: 合并
  • 把 $C_i$ 和 $C_j$ 合并成一个新的簇 $C_{new}$。
  • 现在的簇总数变成了 $N-1$ 个。
• Step 4: 更新距离矩阵
  • 这是最关键的一步。我们需要计算新簇 $C_{new}$ 与剩下的所有旧簇之间的距离。
  • 更新距离矩阵。
• Step 5: 循环
  • 重复 Step 2 到 Step 4。
  • 不断合并最近的簇，簇的数量从 $N \rightarrow N-1 \rightarrow \dots \rightarrow 1$。
  • 直到所有数据点都被合并到一个大簇中，算法结束。

# 优缺点

# 降维

# 主成分分析

# 核心步骤

假设我们有 $m$ 个样本，每个样本有 $n$ 个特征（数据矩阵 $X$ 为 $m \times n$）。

1. 去中心化 (Mean Centering)：【必做】
   • 把数据的中心移到坐标原点。即每一列特征减去该列的均值。
   • 原因：如果不减均值，计算的协方差矩阵会出错。
2. 计算协方差矩阵 (Covariance Matrix)：
   • 我们需要知道特征之间是怎么相关的。
   • $C = \frac{1}{m-1} X^T X$ （$C$ 是一个 $n \times n$ 的对称矩阵）。
   • 矩阵对角线上的值是方差，非对角线是协方差。
3. 特征值分解 (Eigendecomposition)：
   • 这是数学魔法发生的时刻。我们需要求出协方差矩阵 $C$ 的特征值 ($\lambda$) 和 特征向量 ($v$)。
   • $C v = \lambda v$
4. 排序与筛选：
   • 特征向量 ($v$)：代表了新的坐标轴方向（主成分方向）。
   • 特征值 ($\lambda$)：代表了在那个方向上数据的方差大小。
   • 我们将 $\lambda$ 从大到小排序，选取前 $k$ 个最大的 $\lambda$ 对应的特征向量。
5. 投影 (Projection)：
   • 将原始数据 $X$ 乘以这 $k$ 个特征向量构成的矩阵 $W$。
   • $X_{new} = X \cdot W$。
   • 现在，数据从 $n$ 维降到了 $k$ 维。

# T-SNE

一句话总结：PCA 保留的是 “整体轮廓”（方差），t-SNE 保留的是 “局部邻里关系”。

# 算法原理：三步走

t-SNE 的名字里有三个关键词：t - 分布、随机 (Stochastic)、邻域 (Neighbor)。

# 第一步：高维空间里的 “社交圈” (Gaussian)

在高维空间里，我们要衡量两个点 $x_i$ 和 $x_j$ 有多像。

t-SNE 假设数据符合高斯分布（正态分布）。

• 如果 $x_j$ 离 $x_i$ 很近，那么 $x_i$ 选中 $x_j$ 做邻居的概率 $p_{j|i}$ 就很大。
• 如果离得很远，概率就几乎为 0。
• 这一步把距离转化成了概率。

# 第二步：低维空间里的 “模仿秀” (t-Distribution)

我们在 2D 平面上随机撒一堆点 $y_i, y_j$。我们希望这些点之间的概率分布 $q_{j|i}$ 能完美复刻高维空间里的 $p_{j|i}$。

• 重点：这里不用高斯分布，而是用 t - 分布（自由度为 1）。
• 为什么要换分布？ 见下文 “拥挤问题”。

# 第三步：极小化差异 (KL Divergence)

现在我们有两套概率分布：$P$（真身）和 $Q$（替身）。

我们要让 $Q$ 尽可能像 $P$。

• 使用 KL 散度 (Kullback-Leibler Divergence) 来衡量两个分布的差异。
• 利用梯度下降，不断移动低维空间里的点 $y$，直到 KL 散度最小。
  • 直观理解：如果两个点在高维本来很近，在低维却很远，KL 散度会很大，算法就会产生一个 “引力” 把它们拉近；反之则产生 “斥力”。

# 面试问题

• Q: 为什么要用 “t - 分布”

这是 t-SNE 的灵魂所在。

拥挤问题 (The Crowding Problem)：

高维空间极其巨大，而低维空间（2D）非常拥挤。想象一下，一个球体在高维空间里，它的表面积是随着维度指数增长的，但在 2D 平面上只有一点点地方。

如果你强行把高维数据压到 2D，原本中等距离的点会被迫挤在一起，破坏聚类效果。

t - 分布的解决方案：t - 分布相比高斯分布，是一个 **“长尾巴” (Heavy Tailed)** 的分布。

• 这意味着：在低维空间里，为了表示同样的 “不相似度”，t-SNE 允许点与点之间隔得更远。
• 它给中等距离的点留出了 “缓冲空间”，避免了所有点都挤成一团。

# 问题

# 类别不平衡问题

1. 对少样本进行过采样

2. 对多样本进行降采样

3. 阈值移动