数据算法笔记
关于数学建模的笔记。
一、数据预处理与清洗的数学本质
在机器学习中，数据归一化、标准化以及清洗虽然可以通过 Pandas 或 scikit-learn 一键调用，但其底层完全依赖于统计学与代数变换。真正重要的不是会不会调包，而是理解每一步为什么成立、在什么条件下失效。
1. 缺失值处理：插值法的底层逻辑
- 线性插值：
- 底层原理：假设两个已知数据点之间呈线性变化，利用直线斜率估算缺失值。这本质上可以视为局部一阶近似。
- 计算公式：已知点 $(x_{0}, y_{0})$ 和 $(x_{1}, y_{1})$，要估计 $x$ 处的 $y$ 值： $$y = y_{0} + (x - x_{0})\frac{y_{1} - y_{0}}{x_{1} - x_{0}}$$
- 风险提示：如果数据本身具有强非线性或高频波动，例如复杂金融时间序列，线性插值会抹平局部结构，导致特征失真。
- 进一步方法：三次样条插值通过分段三次多项式逼近，并保证一阶导数与二阶导数连续，因此曲线更平滑，也更适合连续变化问题。
2. 异常值检测的统计学边界
- 3$\sigma$ 原则 (Z-score 方法)：
- 底层原理：基于正态分布概率密度函数。在标准正态分布中，数据落在 $\mu \pm 3\sigma$ 范围内的概率约为 99.73%。
- 判定逻辑：若下式成立，则可视为小概率事件，通常判定为异常值： $$|x_{i} - \mu| > 3\sigma$$
- 局限性：该方法强依赖数据近似服从正态分布。若数据本身偏态明显或存在厚尾分布，则此方法可能完全失效。
- 箱线图检测 (IQR 方法)：
- 底层原理：基于分位数构造统计边界，不需要分布假设，因此具有更强鲁棒性。
- 判定公式：设第一四分位数为 $Q_{1}$，第三四分位数为 $Q_{3}$，则四分位距为： $$IQR = Q_{3} - Q_{1}$$
- 边界区间：正常数据一般位于以下区间，超出该范围可判定为离群点： $$[Q_{1} - 1.5 \times IQR,\ Q_{3} + 1.5 \times IQR]$$
3. 数据缩放：归一化与标准化
- 线性归一化：
- 底层原理：通过线性变换将数据按比例缩放到固定区间，一般是 $[0,1]$。它保留原始大小规律，但会受极端值影响。
- 计算公式： $$x_{\text{norm}} = \frac{x - \min(x)}{\max(x) - \min(x)}$$
- 泛化映射到任意区间 $[a,b]$：先求 $Max$ 和 $Min$，再计算缩放系数与结果： $$k = \frac{b-a}{Max-Min}, \quad Y_{nor} = a + k(Y-Min)$$
- 标准化：
- 底层原理：将数据转化为均值为 0、标准差为 1 的尺度，更适合保留样本间相对离散程度。
- 计算公式： $$x_{\text{std}} = \frac{x - \mu}{\sigma}$$
- 实现逻辑：先遍历样本求均值 $\mu$，再计算方差与标准差 $\sigma$，最后逐项做平移与缩放。
- 学习监督：KNN、K-Means 这类基于欧几里得距离的算法必须特别关注标准化。若一个特征量纲远大于其他特征，例如收入和身高同时建模，则大尺度特征会在距离计算中形成支配效应，直接掩盖小尺度特征的实际贡献。
二、图论核心算法的底层机制与原生实现过程
图论算法是不能依靠简单“调包”完成的核心计算机科学内容。资料中给出了原生的数据结构和算法流程。
1. 图的底层存储结构
- 邻接矩阵：使用二维数组 arcs[i][j] 存储。对于无权图，存在边设为 1，不存在设为 0；对于带权图，设为权值 $w_{ij}$，无边则设为无穷大 $\infty$。这种结构查询边极快，但对于稀疏图极其浪费空间。
- 邻接表：为每个顶点建立一个链表。定义顶点表（存顶点信息和头指针）与边表（存相邻顶点的下标和边权值 weight）。适合边数较少的图，在拓扑排序和关键路径求解时效率极高。
2. 最小生成树底层算法
- Prim算法（加点法）：
- 原理：利用 MST 权值性质，将图分为已加入树的集合 $U$ 和未加入的集合 $V-U$。每次在这两个集合之间的桥接边中找权值最小的一条，将其对应顶点划入 $U$。
- 底层实现：维护一个 mst[n-1] 数组，记录 $U$ 中点到 $V-U$ 中点的已知最短边。外层循环 $n-1$ 次，每次遍历 mst 找到权重 weight 最小的边将其顶点加入 $U$；然后最关键的一步：更新 mst 数组，如果新加入顶点的发出边比原先 mst 中记录的连接更短，则覆写 mst 记录。复杂度为 $O(|V|^2)$。
- Kruskal算法（加边法）：
- 原理：初始状态下所有顶点各自为政（无边的森林）。将所有边按权重递增排序，从小到大挑边，只要这条边不会和已挑选的边“形成环路”，就将其加入生成树。
- 底层实现（并查集思想）：使用一个 status 数组记录每个顶点所属的“连通分支代表”。挑到边 $(u,v)$ 时，如果 status[u] != status[v]，说明不构成环路，采纳该边。随后遍历全局，把所有归属 status[v] 的点全部改成 status[u]（合并连通分支）。
3. 最短路径底层算法
- Dijkstra算法（单源最短路径）：
- 原理：也是贪心策略，维护集合 $U$（已知最短距离点）和 $V-U$（未知点）。
- 松弛操作：对于所有剩余的 $v_{i}$，若以下不等式成立，说明借道 $v_{\min}$ 更近，就更新 $dist[i].len$ 并把前驱修改为 $v_{\min}$： $$dist[i].len > dist[min].len + arcs[min][i]$$
- Floyd算法（多源最短路径）：
- 原理：动态规划。对于顶点 $i$ 到 $j$，尝试把每一个顶点 $k$ 当作中间节点。如果 $i \to k \to j$ 比 $i \to j$ 短，就更新距离。
- 核心递推式： $$A[i][j] = \min(A[i][j],\ A[i][k] + A[k][j])$$ 最外层循环必须是中间点 $k$（0 到 $n-1$），内层是起始点 $i$ 和终点 $j$。
4. 拓扑排序与关键路径
- 拓扑排序原理：依靠“入度”信息。手工准备一个一维数组 indegree 统计所有顶点的入度，并维护一个栈或队列（存放入度为0的点）。每次弹出一个点 $i$ 加入输出序列，然后遍历它的所有出边，将其邻接点 $k$ 的入度减 1 (--indegree[k])，若减为 0 则入栈。如果最终输出的点少于总数，说明有环（死锁）。
- 关键路径推导：
- 前向推导：计算事件的最早发生时间（按拓扑顺序递推）： $$ee(j) = \max{ee(i) + w(i, j)}$$
- 后向推导：计算事件的最迟发生时间（按逆拓扑顺序递推）： $$le(i) = \min{le(j) - w(i, j)}$$
- 比较活动：活动最早开始时间 $e(k) = ee(i)$，最迟开始时间： $$l(k) = le(j) - w(i, j)$$ 若 $e(k) = l(k)$，即为关键活动，这些活动构成了关键路径。
三、数学模型与时间序列预测的推导
这部分无需机器学习黑盒模型，可纯依靠统计学与微积分手撸计算过程。
1. ARIMA 预测模型的数学机理
- 平稳性与差分：ARIMA 假设序列的均值和方差不随时间改变，因此非平稳序列通常需要先做差分： $$\Delta y_{t} = y_{t} - y_{t-1}$$
- 自回归 (AR, Auto-Regressive)：认为当前值由过去若干期历史值线性组合而成： $$y_{t} = u + \sum \gamma_{i} y_{t-i} + e_{t}$$
- 移动平均 (MA)：认为当前值与过去若干期预测误差相关，本质上是在拟合噪声结构。
- 定阶原理 (AIC/BIC准则)：在手工实现中，$p$ 和 $q$ 的选择可以用信息准则完成。以 BIC 为例： $$BIC = \ln(n) \cdot k - 2\ln(L)$$ 其中 $k$ 为参数个数，$L$ 为极大似然值，$n$ 为样本量。其核心思想是用惩罚项抑制复杂模型，防止过拟合。
2. 常微分方程建模：传染病 SIR 模型
如果想手写疾病传播的模拟算法，只需依据下面的非线性微分方程组，使用 Euler 方法在离散时间步上逐步迭代求解：
- 人群划分：健康者 $S(t)$，感染者 $I(t)$，移出免疫者 $R(t)$，总人数满足 $S(t) + I(t) + R(t) = 1$。
- 系统方程：
$$\frac{dS}{dt} = -\beta S I, \quad \frac{dI}{dt} = \beta S I - \mu I, \quad \frac{dR}{dt} = \mu I$$ - 阈值分析：定义基本再生数阈值： $$\frac{1}{\sigma} = \frac{\mu}{\beta}$$ 当初始健康者比例 $S_{0}$ 小于该阈值时，$dI/dt < 0$，疫情趋于自然衰减；反之则可能先增长后回落。
- 数值实现：完全可以手写差分迭代（Euler 法），例如： $$I \leftarrow I + dt \cdot (\beta S I - \mu I)$$ 从而用最基础的循环完成动力学模拟。
3. 灰色预测 GM(1,1)：数据稀少时的预测利器
灰色预测适合数据量极少（通常 4~10 个点）且无法假定分布的情况，是建模竞赛中预测题的常用工具。
建模步骤（原始序列 $X^{(0)} = {x^{(0)}(1), x^{(0)}(2), \ldots, x^{(0)}(n)}$）：
累加生成（AGO）：构造单调递增的新序列，以弱化随机性： $$x^{(1)}(k) = \sum_{i=1}^{k} x^{(0)}(i)$$
构造均值序列： $$z^{(1)}(k) = \frac{x^{(1)}(k) + x^{(1)}(k-1)}{2}, \quad k = 2, 3, \ldots, n$$
建立灰色微分方程： $$x^{(0)}(k) + a \cdot z^{(1)}(k) = b$$
最小二乘估计参数 $[a, b]^T$：构造矩阵并求解：
$$B = \bigl[,-z^{(1)}(2),\ 1;\ -z^{(1)}(3),\ 1;\ \cdots;\ -z^{(1)}(n),\ 1,\bigr], \quad Y = \bigl[x^{(0)}(2),\ x^{(0)}(3),\ \ldots,\ x^{(0)}(n)\bigr]^{T}$$
$$\hat{a} = (B^T B)^{-1} B^T Y$$
还原预测值：先求累加序列预测值，再累减还原： $$\hat{x}^{(1)}(k+1) = \left(x^{(0)}(1) - \frac{b}{a}\right) e^{-ak} + \frac{b}{a}$$ $$\hat{x}^{(0)}(k+1) = \hat{x}^{(1)}(k+1) - \hat{x}^{(1)}(k)$$
精度检验：计算后验差比 $C = S_{2} / S_{1}$（残差标准差与原始序列标准差之比），$C < 0.35$ 为优，$C < 0.50$ 为合格。
1 | import numpy as np |
四、常用数据可视化代码模板与数学含义
画图不仅是为了好看，更重要的是通过视觉方式验证数学假设，例如线性关系、聚类趋势、极值点位置等。
1. 散点图：寻找变量间的映射关系
1 | import matplotlib.pyplot as plt |
散点图最适合观察两个变量之间是否存在近似线性关系、分段关系或者明显聚类结构。若点云大致落在一条直线附近，往往意味着可以进一步尝试线性回归建模。
2. 相关性热力图：降维与特征选择的雷达
底层数学是皮尔逊相关系数，它用于衡量两个变量的线性相关程度，范围在 $[-1,1]$ 之间： $$\rho_{X,Y} = \frac{Cov(X,Y)}{\sigma_{X} \sigma_{Y}}$$
1 | import seaborn as sns |
热力图本质上是在可视化协方差结构。若两个特征高度相关，则它们可能存在信息冗余，在降维、特征筛选和多重共线性分析中都非常关键。
3. 三维曲面图：观察目标函数的极值点
1 | from mpl_toolkits.mplot3d import Axes3D |
三维曲面图常用于观察目标函数形状。若图像呈单峰凸碗形，则优化问题通常更容易求解；若存在多个局部极小值，则意味着优化过程可能需要更复杂的全局搜索策略。
五、运筹学与数学规划
在数学建模中，寻找最优解是核心任务之一。与其手写不稳定的梯度下降，不如理解成熟求解器背后的约束表达方式与优化思想。
1. 线性规划：最基础的最优化模型
线性规划要求目标函数和所有约束均为线性，是运筹学的骨架，也是整数规划、网络流等高级模型的基础。
标准形式：
$$\min \mathbf{c}^T \mathbf{x}$$ $$\text{s.t.} \quad A^{(\mathrm{ub})}\mathbf{x} \leq \mathbf{b}^{(\mathrm{ub})},\quad A^{(\mathrm{eq})}\mathbf{x} = \mathbf{b}^{(\mathrm{eq})},\quad \mathbf{l} \leq \mathbf{x} \leq \mathbf{u}$$
- 单纯形法原理：在可行域（凸多面体）的顶点之间跳转，每次移动都保证目标函数值不增。最优解一定在顶点处取到。
- 对偶理论：每个线性规划（原问题）对应一个对偶问题。原问题最优值 = 对偶问题最优值（强对偶定理），可用于灵敏度分析和影子价格解释。
1 | from scipy.optimize import linprog |
2. 规划问题代码模板：以非线性规划 SLSQP 算法为例
数学模型定义：
$$\min f(x) = x_{1}^{2} + x_{2}^{2}$$
$$\text{s.t.} \quad x_{1} + x_{2} \geq 1, \quad x_{1}, x_{2} \in [0, +\infty)$$
1 | from scipy.optimize import minimize |
这里的关键不是记住 API，而是理解优化问题由三部分组成：目标函数、约束条件和定义域。SLSQP 的优势在于能同时处理边界约束与一般非线性约束，因此在工程优化和竞赛建模中都很常见。
六、现代机器学习：基于树的集成算法原理
不能把 sklearn 当作盲目调参的黑盒。树模型尤其如此，因为它们背后对应的是非常完整的统计学习思想。
1. 随机森林：Bagging 的方差削减思想
- 数学与算法底层：随机森林由多棵决策树组成。每棵树都对训练样本做 Bootstrap 有放回抽样，同时在每次分裂节点时只随机考虑部分特征。这样做的核心效果是降低模型方差，从而抑制过拟合。
- 决策机制：分类任务通常采用投票法，回归任务通常采用多棵树预测结果的平均值。
- 可解释性输出：模型还能够输出特征重要性，通常基于节点纯度下降量的平均贡献计算。
1 | from sklearn.ensemble import RandomForestRegressor |
2. XGBoost：二阶近似下的 Boosting
- 数学与算法底层：与随机森林的并行建树不同，XGBoost 采用串行 boosting 机制，每一棵新树都在拟合上一轮模型的残差。
- 硬核差异：传统 GBDT 多基于损失函数的一阶梯度信息，而 XGBoost 进一步引入二阶导数信息，对目标函数做二阶泰勒展开，并显式加入模型复杂度正则项。
- 风险评估：XGBoost 精度高，但对学习率、树深度、正则化系数等超参数非常敏感，实战中若缺少交叉验证，很容易过拟合。
1 | # 需要先 pip install xgboost |
XGBoost 的真正价值不在于“调个参数就拿高分”，而在于它把梯度提升、二阶优化和正则化思想融合到了统一框架中，因此既高效又强大，但也要求使用者具备更强的验证意识。
七、综合评价方法：AHP、熵权法与 TOPSIS
综合评价问题的核心是：如何将多个指标的信息合并成一个可以比较的得分。以下三种方法分别从主观判断、客观信息量和几何距离三个角度解决这一问题。
1. 层次分析法（AHP）：主观权重的量化
AHP 将决策者的经验与偏好转化为数学权重，适合指标体系清晰、权重主要依赖专家判断的情境。
构造判断矩阵：对 $n$ 个指标两两比较重要性，填入 $n \times n$ 矩阵 $A$，其中元素 $a_{ij}$ 表示指标 $i$ 相对指标 $j$ 的重要程度，采用 1~9 标度。矩阵满足 $a_{ij} = 1/a_{ji}$，对角线为 1。
求权重向量：对矩阵 $A$ 求最大特征值 $\lambda_{max}$ 及其对应的特征向量 $\mathbf{w}$，归一化后即为各指标权重。近似算法为对每列归一化后逐行取平均：
$$w_{i} = \frac{1}{n} \sum_{j=1}^{n} \frac{a_{ij}}{\sum_{k=1}^{n} a_{kj}}$$
- 一致性检验（CR）：判断矩阵填写可能存在逻辑矛盾，需计算一致性比率：
$$CI = \frac{\lambda_{max} - n}{n - 1}, \quad CR = \frac{CI}{RI}$$
其中 $RI$ 为随机一致性指标（查表得到，$n=3$ 时 $RI=0.58$，$n=4$ 时 $RI=0.90$）。若 $CR < 0.10$，则通过一致性检验，否则需重新修正判断矩阵。
1 | import numpy as np |
2. 熵权法：基于信息量的客观赋权
熵权法完全由数据本身驱动，核心思想来自信息论：某指标的各方案取值差异越大，携带的信息量越多，权重越大；若所有方案在该指标上的值几乎相同，则该指标对区分方案几乎没有贡献，权重趋近于 0。
计算流程（$m$ 个方案，$n$ 个指标，数据矩阵为 $X$）：
- 归一化：对每列指标做正向归一化（正向指标越大越好，负向指标取倒数或做变换后再归一化）：
$$r_{ij} = \frac{x_{ij} - \min_{j} x_{ij}}{\max_{j} x_{ij} - \min_{j} x_{ij}}$$
- 计算比重（第 $i$ 行第 $j$ 列的相对占比）：
$$p_{ij} = \frac{r_{ij}}{\sum_{i=1}^{m} r_{ij}}$$
- 计算信息熵：
$$e_{j} = -\frac{1}{\ln m} \sum_{i=1}^{m} p_{ij} \ln p_{ij}$$
其中 $\frac{1}{\ln m}$ 是归一化系数，使得 $e_{j} \in [0, 1]$。当 $p_{ij} = 0$ 时约定 $p_{ij} \ln p_{ij} = 0$。
- 计算权重：差异系数 $d_{j} = 1 - e_{j}$，熵权为：
$$w_{j} = \frac{d_{j}}{\sum_{j=1}^{n} d_{j}}$$
1 | import numpy as np |
3. TOPSIS：基于理想解的排名方法
TOPSIS（逼近理想解排序法）不独立计算权重，而是在已知权重的前提下，通过计算每个方案与"最优理想解"和"最劣理想解"的距离来排名。它可以直接接收 AHP 或熵权法输出的权重向量。
计算流程：
- 加权归一化矩阵：对原始矩阵先做向量归一化，再乘以权重：
$$v_{ij} = w_{j} \cdot \frac{x_{ij}}{\sqrt{\sum_{i=1}^{m} x_{ij}^{2}}}$$
- 确定正负理想解：
$$A^{+} = {\max_{i} v_{ij}}, \quad A^{-} = {\min_{i} v_{ij}} \quad (\text{正向指标})$$
- 计算距离：每个方案到正负理想解的欧氏距离：
$$D_{i}^{+} = \sqrt{\sum_{j=1}^{n}(v_{ij} - A_{j}^{+})^{2}}, \quad D_{i}^{-} = \sqrt{\sum_{j=1}^{n}(v_{ij} - A_{j}^{-})^{2}}$$
- 计算贴近度并排名：
$$C_{i} = \frac{D_{i}^{-}}{D_{i}^{+} + D_{i}^{-}}, \quad C_{i} \in [0, 1]$$
$C_{i}$ 越大表示方案越接近理想解，排名越靠前。
1 | import numpy as np |
三种方法的对比与联用建议：
| 方法 | 权重来源 | 适用场景 | 核心依据 |
|---|---|---|---|
| AHP | 主观（专家判断） | 指标难以量化，依赖经验 | 特征值与一致性 |
| 熵权法 | 客观（数据驱动） | 数据充足，减少主观偏差 | 信息熵 |
| TOPSIS | 需外部提供权重 | 方案排名与综合评分 | 理想解距离 |
在实际竞赛中，常见的组合做法是：熵权法（或 AHP）求权重 → TOPSIS 排名，也可将两种权重加权融合后再输入 TOPSIS，以平衡主客观信息。
八、回归分析：从线性到正则化
回归分析是建立变量之间定量关系的核心工具，从最简单的一元线性回归到带正则化的多元回归，背后是一套完整的优化与参数估计体系。
1. 一元线性回归：最小二乘的本质
给定 $n$ 个样本点 $(x_{i}, y_{i})$，拟合直线 $\hat{y} = \beta_{0} + \beta_{1} x$，使残差平方和最小：
$$\min_{\beta_{0}, \beta_{1}} \sum_{i=1}^{n} (y_{i} - \beta_{0} - \beta_{1} x_{i})^2$$
对 $\beta_{0}, \beta_{1}$ 分别求偏导并令其为零，解析解为：
$$\beta_{1} = \frac{\sum_{i=1}^{n}(x_{i} - \bar{x})(y_{i} - \bar{y})}{\sum_{i=1}^{n}(x_{i} - \bar{x})^2}, \quad \beta_{0} = \bar{y} - \beta_{1} \bar{x}$$
拟合优度 $R^2$：衡量模型对数据方差的解释比例：
$$R^2 = 1 - \frac{\sum\bigl(y(i) - \hat{y}(i)\bigr)^2}{\sum\bigl(y(i) - \bar{y}\bigr)^2}$$
$R^2 \in [0,1]$，越接近 1 说明拟合越好。但注意：$R^2$ 随特征数增加单调不减，多元回归应改用调整后的 $\bar{R}^2$。
1 | import numpy as np |
2. 多元线性回归：矩阵形式的最小二乘
当有 $p$ 个特征时，模型写为向量形式：
$$\hat{\mathbf{y}} = X\boldsymbol{\beta}, \quad \boldsymbol{\beta} = (\beta_{0}, \beta_{1}, \ldots, \beta_{p})^{T}$$
其中 $X$ 为设计矩阵（首列全为 1，对应截距项）。最小二乘的解析解为正规方程：
$$\hat{\boldsymbol{\beta}} = (X^T X)^{-1} X^T \mathbf{y}$$
多重共线性风险：若特征之间高度相关，$X^T X$ 接近奇异，参数估计不稳定，此时需要正则化（见下）。
1 | from sklearn.linear_model import LinearRegression |
3. 多项式回归：非线性关系的线性化
多项式回归本质上仍是线性回归，只需在特征矩阵中加入原始特征的高次项，所有参数仍可用最小二乘求解：
$$\hat{y} = \beta_{0} + \beta_{1} x + \beta_{2} x^{2} + \cdots + \beta_{d} x^{d}$$
过拟合风险：次数 $d$ 越高，训练集拟合越好，但泛化能力可能急剧下降。需要结合交叉验证选择合适的阶数。
1 | from sklearn.preprocessing import PolynomialFeatures |
4. Ridge 回归与 Lasso 回归：正则化防止过拟合
当特征数多、存在多重共线性或训练数据少时，标准最小二乘容易过拟合。正则化在损失函数中加入惩罚项，主动压缩系数。
Ridge（L2 正则化）：惩罚系数的平方和，使所有系数均匀缩小，不会置零：
$$\min_{\boldsymbol{\beta}} \sum_{i=1}^{n}\bigl(y(i) - \hat{y}(i)\bigr)^2 + \lambda \sum_{j=1}^{p}\beta(j)^2$$
解析解为（相比普通最小二乘，在 $X^T X$ 对角线上加了 $\lambda I$，避免奇异）：
$$\hat{\boldsymbol{\beta}}_{ridge} = (X^T X + \lambda I)^{-1} X^T \mathbf{y}$$
Lasso（L1 正则化）：惩罚系数的绝对值之和，会将不重要特征的系数精确置零，天然具备特征选择功能：
$$\min_{\boldsymbol{\beta}} \sum_{i=1}^{n}\bigl(y(i) - \hat{y}(i)\bigr)^2 + \lambda \sum_{j=1}^{p}|\beta(j)|$$
| 方法 | 惩罚项 | 系数是否置零 | 适用场景 |
|---|---|---|---|
| Ridge | $\lambda |\boldsymbol{\beta}|_{2}^{2}$ | 否，均匀缩小 | 多重共线性，特征都有用 |
| Lasso | $\lambda |\boldsymbol{\beta}|_{1}$ | 是，自动选特征 | 高维稀疏，特征筛选 |
超参数 $\lambda$ 通过交叉验证选取，sklearn 提供 RidgeCV / LassoCV 自动搜索。
1 | from sklearn.linear_model import RidgeCV, LassoCV |
九、聚类算法：无监督的结构发现
聚类不依赖标签，目标是自动发现数据中的内在分组结构。不同算法对"簇"的形状假设完全不同，选错方法会导致结果毫无意义。
1. K-means：基于质心的划分聚类
数学目标：将 $n$ 个样本划分为 $k$ 个簇 ${C_{1}, \ldots, C_{k}}$，使簇内样本到各自质心 $\mu_{j}$ 的总距离（惯性）最小：
$$\min \sum_{j=1}^{k} \sum_{\mathbf{x} \in C_{j}} |\mathbf{x} - \mu_{j}|^{2}$$
EM 迭代流程（Lloyd 算法）：
- E 步（分配）：将每个样本分配给距离最近的质心： $$c(i) = \arg\min_{j} |\mathbf{x}^{(i)} - \mu^{(j)}|^{2}$$
- M 步（更新）：重新计算每个簇的质心： $$\mu_{j} = \frac{1}{|C_{j}|} \sum_{\mathbf{x} \in C_{j}} \mathbf{x}$$
- 重复直到质心不再变化。
关键注意事项：
- K-means 对初始值敏感，常用 K-means++ 初始化（按距离概率选择初始质心）避免陷入局部最优；
- 需要预先指定 $k$，可用肘部法则（画出不同 $k$ 下的惯性曲线，找拐点）辅助选择；
- 假设簇是凸形且大小相近，对非球形或密度差异大的簇效果差。
1 | from sklearn.cluster import KMeans |
2. DBSCAN：基于密度的异形簇检测
DBSCAN 不需要预先指定簇数，能发现任意形状的簇，并自动将稀疏区域的点标记为噪声，非常适合探索性分析。
核心概念：
- ε-邻域：以点 $p$ 为中心、半径 $\varepsilon$ 内的所有点的集合；
- 核心点：ε-邻域内样本数 $\geq MinPts$ 的点；
- 边界点：自身不是核心点，但落在某核心点的 ε-邻域内；
- 噪声点：既不是核心点也不是边界点，标记为 $-1$。
扩张逻辑：从任一未访问核心点出发，通过"密度可达"关系不断向外扩张，将互相密度可达的点归为同一簇。
参数选择建议：
- $MinPts$ 一般取特征维度的 2 倍；
- $\varepsilon$ 通过 k-距离图（对每个点计算到其第 $k$ 近邻的距离，排序后找拐点）辅助确定。
1 | from sklearn.cluster import DBSCAN |
K-means vs DBSCAN 对比：
| 维度 | K-means | DBSCAN |
|---|---|---|
| 是否需要指定 $k$ | 是 | 否 |
| 簇形状假设 | 凸形、大小相近 | 任意形状 |
| 噪声处理 | 无，噪声点会被强制分配 | 有，自动标记 |
| 计算复杂度 | $O(nkd)$ | $O(n \log n)$（用树索引） |
| 适用场景 | 大规模、球形簇 | 噪声数据、异形簇 |
十、降维：主成分分析（PCA）
PCA 是最经典的线性降维方法，目标是找到一组互相正交的方向（主成分），使投影后方差最大（信息保留最多），从而用更少的维度表示高维数据。
1. 数学推导
给定标准化后的数据矩阵 $X \in \mathbb{R}^{n \times p}$，PCA 的步骤如下：
计算协方差矩阵： $$\Sigma = \frac{1}{n-1} X^T X$$
特征值分解：求 $\Sigma$ 的特征值 $\lambda_{1} \geq \lambda_{2} \geq \cdots \geq \lambda_{p}$ 及对应的特征向量 $\mathbf{v}{1}, \mathbf{v}{2}, \ldots, \mathbf{v}_{p}$（即主成分方向）。
选取前 $d$ 个主成分：方差贡献率记为 $R_{d}$，其定义为： $$R_{d} = \frac{\sum_{i=1}^{d} \lambda_{i}}{\sum_{i=1}^{p} \lambda_{i}}$$ 通常选取累计解释率超过 85%-95% 时对应的 $d$。
投影：将原始数据投影到前 $d$ 个主成分方向： $$Z = X V^{(d)}, \quad V^{(d)} = [\mathbf{v}^{(1)}, \ldots, \mathbf{v}^{(d)}]$$
2. 几何直觉
PCA 本质上是寻找数据分布的主轴方向：方差最大的方向是第一主成分，与之正交且方差次大的方向是第二主成分，依此类推。它是一种旋转变换，不会丢失样本间的欧氏几何关系（在投影子空间内）。
3. 注意事项
- 必须先标准化：若各特征量纲或方差差异悬殊，方差大的特征会主导主成分，导致结果失真；
- 主成分无物理含义：降维后的轴是原始特征的线性组合，难以直接解释；
- 仅捕捉线性结构：若数据本身呈非线性流形分布，应考虑 Kernel PCA 或 t-SNE。
1 | from sklearn.decomposition import PCA |