机器学习基础

监督学习

给定一组输入（特征）和对应的输出（标签），训练一个模型来学习输入和输出之间的映射关系。

代价函数

代价函数是机器学习和优化问题中用来衡量模型预测结果与真实结果之间差异的函数。它反映了模型的“错误”程度——即预测数据相对于真实数据的“损失”，通常通过调整模型参数来最小化代价函数值，从而得到更好预测效果。

1. 定义

假设有训练数据集：

$$
{(x^{(i)}, y^{(i)})}_{i=1}^m
$$

其中：

• $m$ 表示样本数量
• $x^{(i)} \in \mathbb{R}^n$ 是第 $i$ 个样本的输入特征向量，包含 $n$ 个特征
• $y^{(i)}$ 是第 $i$ 个样本的真实标签（可为标量或向量，视具体任务而定）

模型的预测函数为：

$$
h_\theta(x^{(i)}) = \theta^T x^{(i)} = \sum_{j=0}^{n} \theta_j x_j^{(i)}
$$

• $\theta$ 表示模型的参数（权重）

代价函数（损失函数） $J(\theta)$ 用于衡量模型预测值与真实值之间的差异，通常定义为所有样本的平均误差：

$$
J(\theta) = \frac{1}{m} \sum_{i=1}^m \mathcal{L}\big(h_\theta(x^{(i)}), y^{(i)}\big)
$$

$\mathcal{L}(\hat{y}, y)$ 是单个样本的损失函数（loss function），衡量预测值 $\hat{y} = h_\theta(x)$ 与真实值 $y$ 的差距。

常见代价函数

均方误差（Mean Squared Error，MSE）

适用于回归问题，定义为预测值与真实值误差的平方的平均值：

$$
J(\theta) = \frac{1}{2m} \sum_{i=1}^m \left(h_\theta(x^{(i)}) - y^{(i)}\right)^2
$$

$1/2$ 是为了求导时简化表达式。

交叉熵损失（Cross-Entropy Loss）

适用于分类问题，尤其是二分类：

$$
J(\theta) = -\frac{1}{m} \sum_{i=1}^m \left[ y^{(i)} \log h_\theta(x^{(i)}) + (1 - y^{(i)}) \log (1 - h_\theta(x^{(i)})) \right]
$$

度量预测概率分布与真实标签的差异。

• 损失函数（Loss Function） 针对单个样本的误差度量，用来衡量某一个预测值和真实值之间的差距。
• 代价函数（Cost Function） 针对整个训练集的平均损失，把所有样本的损失函数求平均或求和。

---

梯度下降

梯度下降是通过不断调整模型参数使代价函数最小化，找到模型的最优参数。核心思想是沿着代价函数在参数空间中的负梯度方向更新参数，因为梯度指向函数上升最快的方向，沿负梯度方向移动可以最快减小函数值。

公式表示

假设代价函数为 $J(\theta)$，参数为向量 $\theta$，梯度为 $\nabla_\theta J(\theta)$，则参数更新规则为：

$$
\theta := \theta - \alpha \nabla_\theta J(\theta)
$$

• $\alpha$ 是学习率（learning rate），控制每次更新的步长大小。
• $\nabla_\theta J(\theta)$ 是代价函数对参数 $\theta$ 的梯度（偏导数组成的向量）。

过程

1. 初始化参数 $\theta$（随机或零初始化，神经网络不能为零）。
2. 计算代价函数 $J(\theta)$ 及其梯度 $\nabla_\theta J(\theta)$.
3. 根据梯度下降公式更新参数。
4. 重复步骤 2 和 3，直到代价函数收敛或达到最大迭代次数。

学习率

• 过大：可能导致参数更新过度（步长过大），甚至发散，无法收敛。
• 过小：收敛速度慢，训练时间长。

参数迭代状态

1. 收敛 (Convergence)
   参数逐渐靠近某个固定点（极小点），跳动幅度逐渐减小，最终稳定
2. 振荡收敛 (Oscillatory Convergence)
   参数在目标附近反复跳动，但跳动幅度逐渐减小，最终依然收敛到极小点，常见于学习率较大但未超过临界值的梯度下降。
3. 非收敛振荡 (Non-convergent Oscillation)
   参数在有限区间内无规则跳动，没有收敛到某个固定点，但不发散，属于稳定的但无收敛的状态，类似“电子云”是概率问题。
4. 发散 (Divergence)
   参数值幅度不断扩大，远离极小点，通常因学习率过大导致训练失败。

额外说明（可不看）

• 梯度下降的收敛条件（以一维二次函数为例）：

$$
\theta_{t+1} = (1 - \alpha a) \theta_t
$$

• 若 $|1 - \alpha a| < 1$，收敛
• 若 $1 < \alpha a < 2$，震荡收敛
• 若 $|1 - \alpha a| > 1$，发散

---

正规方程

线性回归中可以通过正规方程（Normal Equation）直接计算最优参数 $\theta$，无需使用梯度下降。

假设训练数据集为 $X \in \mathbb{R}^{m \times n}$，目标向量为 $y \in \mathbb{R}^{m}$，其中 $m$ 是样本数量，$n$ 是特征数量。

1. 损失函数（向量形式）：

   $$
   J(\theta) = \frac{1}{2m}(X\theta - y)^T (X\theta - y)
   $$

2. 对 $\theta$ 求导：

   $$
   \frac{\partial J(\theta)}{\partial \theta} = \frac{1}{m} X^T (X\theta - y)
   $$

3. 令导数为 0，得到最优解条件：

   $$
   X^T (X\theta - y) = 0
   $$

4. 解得正规方程（拆开移项即可）：

   $$
   \theta = (X^T X)^{-1} X^T y
   $$

• $X^T X$可逆
• $\theta$ 是最终预测结果

优点

• 不需要选择学习率
• 无需迭代直接求解

缺点

• $(X^T X)^{-1}$ 的时间复杂度为 $O(n^3)$，特征数量较多时效率低下
• $X^T X$ 不可逆时无法使用正规方程（可以正则化）

为避免不可逆，添加一个微小的正则项 $\lambda I$，形成岭回归：

$$
\theta = (X^T X + \lambda I)^{-1} X^T y
$$

其中 $\lambda$ 是正则化强度，$I$ 是单位矩阵。

为什么添加正则项 ( \lambda I ) 可以保证矩阵可逆

在正规方程中，原始需要求逆的矩阵是：

$$
X^T X
$$

它是一个对称且正半定的矩阵，（$x^\top A x \geq 0$则称 $A$ 是一个正半定矩阵）意味着它的特征值都是非负的，但可能存在零特征值导致不可逆（部分特征值为零也可能导致矩阵不可逆）。

通过添加正则项，矩阵变为：

$$
X^T X + \lambda I
$$

• 正则化参数$\lambda > 0$（通常小于1接近0，引入$\lambda$便于调节）
• $I$ 是单位矩阵且所有特征值都是 1，加法操作将矩阵的特征值整体“向右平移” $\lambda$ 个单位

如果 $X^T X$ 的特征值为 $\sigma_1, \sigma_2, \dots, \sigma_n$，那么$X^T X + \lambda I$的特征值为

$$
\sigma_1 + \lambda, \sigma_2 + \lambda, \dots, \sigma_n + \lambda
$$

因为 $\lambda > 0$，所以所有特征值都严格大于 0，这意味着 $X^T X + \lambda I$ 是正定矩阵，正定矩阵一定是可逆的。最终正规方程的解存在且唯一。

---

逻辑回归

逻辑回归是一种用于二分类问题的线性分类模型。与线性回归不同，它的输出是一个概率值，表示某个样本属于正类（label = 1）的概率。

逻辑回归的假设函数使用了 sigmoid 函数将线性回归的输出映射到 $(0, 1)$ 区间：

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

• $x$ 为特征向量
• $\theta$ 为模型参数
• $h_\theta(x)$ 是预测为正类的概率

损失函数（对数损失）

逻辑回归使用的是对数损失函数（Log Loss）：
$$
J(\theta) = -\frac{1}{m} \sum_{i=1}^m \left[ y^{(i)} \log h_\theta(x^{(i)}) + (1 - y^{(i)}) \log (1 - h_\theta(x^{(i)})) \right]
$$

• $m$ 是样本数
• $y^{(i)}$ 是第 $i$ 个样本的真实标签
• $h_\theta(x^{(i)})$ 是第 $i$ 个样本的预测概率

当真实标签 $y^{(i)} = 1$ 时，损失为

$$
-\log h_\theta(x^{(i)})
$$

即预测概率越接近 1，损失越小。

当真实标签 $y^{(i)} = 0$ 时，损失为

$$
-\log \big(1 - h_\theta(x^{(i)}) \big)
$$

即预测概率越接近 0，损失越小。

通常使用梯度下降来最小化该损失函数，更新参数 $\theta$。

优点

• 训练速度快

缺点

• 只能解决线性可分的问题（需要扩展如多项式特征或核方法）
• 异常值敏感

---

正则化

在机器学习中，正则化（Regularization）是一种防止模型过拟合（Overfitting）的技术。通过在损失函数中加入正则项，限制模型参数的复杂度，从而提升模型的泛化能力。

常见的正则化方法

L2 正则化（岭回归）

L2 正则化通过惩罚参数的平方和来约束模型：

$$
J(\theta) = J_0(\theta) + \frac{\lambda}{2m} \sum_{j=1}^n \theta_j^2
$$

• $J_0(\theta)$ 是原始损失函数
• $\lambda$ 是正则化强度（超参数）
• $m$ 是样本数
• $\theta_j$ 是第 $j$ 个参数（通常不对 $\theta_0$ 进行正则）

L2 正则化使参数趋向于较小的数值，保持模型稳定。

L1 正则化（Lasso）

L1 正则化通过惩罚参数的绝对值和，具有稀疏性，能实现特征选择：

$$
J(\theta) = J_0(\theta) + \frac{\lambda}{m} \sum_{j=1}^n |\theta_j|
$$

L1 正则化会使部分参数变为零，从而简化模型。

正则化在梯度下降中的更新公式

以 L2 正则化为例，参数更新为：

$$
\theta_j := \theta_j - \alpha \left( \frac{1}{m} \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)}) x_j^{(i)} + \frac{\lambda}{m} \theta_j \right)
$$

• 正则化能够有效缓解过拟合问题
• L2 正则化偏向参数缩小，但不一定为零
• L1 正则化有特征选择功能，使部分参数变为零

---

神经网络

神经网络（Neural Network）是一种模拟生物神经系统的机器学习模型，由多层神经元（节点）组成，用于拟合复杂的非线性函数。

基本结构

• 输入层：接收输入特征
• 隐藏层：一个或多个隐藏层，每层包含若干神经元
• 输出层：输出预测结果

每个神经元通过加权和加偏置，经过激活函数产生输出。

前向传播

对于第 $l$ 层的神经元，假设输入为 $\mathbf{a}^{(l-1)}$，权重矩阵为 $W^{(l)}$，偏置向量为 $\mathbf{b}^{(l)}$，则该层输出为：

$$
\mathbf{z}^{(l)} = W^{(l)} \mathbf{a}^{(l-1)} + \mathbf{b}^{(l)}
$$

激活函数 $g(\cdot)$ 作用后得到激活值：

$$
\mathbf{a}^{(l)} = g(\mathbf{z}^{(l)})
$$

输入层的激活值为输入特征：$\mathbf{a}^{(0)} = \mathbf{x}$。

激活函数Sigmoid

$$
\sigma(z) = \frac{1}{1 + e^{-z}}
$$

损失函数和训练

通过定义损失函数（如均方误差或交叉熵），利用反向传播算法和梯度下降优化网络参数。

反向传播

从输出层开始，计算每层误差对损失的贡献，逐层传递梯度。

反向传播的数学推导

假设网络有 $L$ 层，第 $l$ 层输入为 $a^{(l-1)}$，权重矩阵为 $W^{(l)}$，偏置向量为 $b^{(l)}$，激活函数为 $g$，则：

前向计算

• 线性变换：

  $$
  z^{(l)} = W^{(l)} a^{(l-1)} + b^{(l)}
  $$

• 激活输出：

  $$
  a^{(l)} = g(z^{(l)})
  $$

误差项定义

• 定义第 $l$ 层误差项：

$$
\delta^{(l)} = \frac{\partial J}{\partial z^{(l)}}
$$

输出层误差计算

最后一层为输出层 $L$，误差为：

$$
\delta^{(L)} = \nabla_{a^{(L)}} J \odot g’(z^{(L)})
$$

• $\nabla_{a^{(L)}} J$ 是损失对输出的偏导数
• $g’(z^{(L)})$ 是激活函数导数
• $\odot$ 是元素逐项相乘（Hadamard 积）

反向传播误差递推

• 从输出层往前传播，层 $l$ 的误差：
  $$
  \delta^{(l)} = (W^{(l+1)})^T \delta^{(l+1)} \odot g’(z^{(l)})
  $$

梯度计算

参数梯度计算：

• 权重梯度：

  $$
  \frac{\partial J}{\partial W^{(l)}} = \delta^{(l)} (a^{(l-1)})^T
  $$

• 偏置梯度：

  $$
  \frac{\partial J}{\partial b^{(l)}} = \delta^{(l)}
  $$

代码实现

import numpy as np

def sigmoid(z):
    return 1 / (1 + np.exp(-z))

def sigmoid_derivative(z):
    s = sigmoid(z)
    return s * (1 - s)

# 前向传播
def forward(X, W1, b1, W2, b2):
    z1 = W1 @ X + b1
    a1 = sigmoid(z1)
    z2 = W2 @ a1 + b2
    a2 = sigmoid(z2)
    return z1, a1, z2, a2

# 反向传播
def backward(X, Y, z1, a1, z2, a2, W2):
    m = X.shape[1]  # 样本数
    dz2 = a2 - Y
    dW2 = (1/m) * dz2 @ a1.T
    db2 = (1/m) * np.sum(dz2, axis=1, keepdims=True)

    dz1 = W2.T @ dz2 * sigmoid_derivative(z1)
    dW1 = (1/m) * dz1 @ X.T
    db1 = (1/m) * np.sum(dz1, axis=1, keepdims=True)

    return dW1, db1, dW2, db2

不对称性分类的误差评估

F1 分数是分类问题中常用的性能指标，综合了精确率（Precision）和召回率（Recall），计算公式如下：

$$
\text{Precision} = \frac{TP}{TP + FP}
$$

$$
\text{Recall} = \frac{TP}{TP + FN}
$$

其中定义：

$$
\begin{cases}
TP \text{：真正例（True Positive）} \
FP \text{：假正例（False Positive）} \
FN \text{：假负例（False Negative）}
\end{cases}
$$

F1 分数定义为精确率和召回率的调和平均数：

$$
F_1 = 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}}
$$

这里的乘以 2 来自调和平均数的标准定义，其本质是为了计算两个数的调和平均值。

$$
H = \frac{2}{\frac{1}{a} + \frac{1}{b}} = \frac{2ab}{a + b}
$$

调和平均比算术平均略低，更能体现两者不平衡的情况，因此 F1 分数更适合衡量精确率和召回率的平衡。

---

支持向量机（SVM）

支持向量机是一种强大的监督学习算法，广泛用于分类任务。其核心目标是找到一个最优的决策超平面，将不同类别的样本分开，并且使两类之间的间隔（Margin）最大化。

最大化间隔

在二分类问题中，找到一个超平面将两类样本分开，并且这个超平面距离训练集中最近的样本点尽可能远，那么模型具有更强的泛化能力。换句话说，最大间隔超平面在训练数据之外更稳健，更不容易被噪声或数据变化影响。

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

训练样本线性可分：硬间隔（Hard Margin）最大化

即所有正负样本能用一条直线（或高维里的超平面）完全分开，互不混淆，采用硬间隔最大化。该方法要求完全正确地分开样本，不允许任何分类错误。

训练样本近似线性可分：软间隔（Soft Margin）最大化

即大部分样本可以被一条线分开，但少量样本因噪声或偏移无法正确分类时，采用软间隔最大化。
该方法在最大化间隔的基础上引入惩罚系数 $C$，以平衡分错样本的损失（惩罚项）和间隔的大小。
允许部分样本落在间隔区域内甚至被误分类，以提升模型对新数据的泛化能力。

训练样本线性不可分

即样本在原始空间中无法被任何超平面线性分开时，使用核技巧将其映射到高维特征空间，在该空间中可能变得线性可分。
结合核函数与软间隔最大化训练一个非线性支持向量

决策边界和间隔

决策边界是分类的分界线（或超平面），表示模型将样本分类为不同类别的标准。
间隔是指决策边界与最近样本点之间的距离。

支持向量

并不是所有训练样本都决定决策边界，只有距离决策边界最近的那些样本点（称为支持向量）真正影响边界的位置和方向。
支持向量使得模型只依赖于少数关键样本，增强了模型的计算效率和泛化能力。

数学表达

给定训练数据集：
$$
{(x^{(i)}, y^{(i)})}_{i=1}^m, \quad x^{(i)} \in \mathbb{R}^n, \quad y^{(i)} \in {-1, +1}
$$
寻找一个超平面：
$$
w^T x + b = 0
$$
使得对所有样本满足：
$$
y^{(i)} (w^T x^{(i)} + b) \geq 1
$$
其中，等式成立的样本点是支持向量。

最大化间隔的优化目标

最大化间隔等价于最小化 $|w|$，可转化为凸二次规划问题：

这里通过约束保证样本分类正确且距离边界不小于1。

为什么只关注支持向量

• 决策边界仅由支持向量唯一确定
  其他离边界更远的样本点，对边界的影响为零，不会改变优化结果。

• 减少模型复杂度
  只用少数支持向量参与模型决策，提升计算效率和存储效率。

• 增强泛化能力
  最大间隔原则避免了对所有训练样本的过度拟合，更具鲁棒性。

支持向量机通过最大化间隔，选择最关键的支持向量确定分类边界，实现了一个既简单又强大的分类模型，兼具良好的泛化能力和计算效率。

---

核函数

• 很多数据在原始空间线性不可分,映射到一个更高维的空间可能线性可分，但高维空间计算复杂，难以直接实现。核函数能够直接计算两个点在高维映射后对应向量的内积，代替高维映射计算，减少计算量。
• 核函数计算样本之间的相似度（支持向量机并不需要知道 $\phi(x)$，只需要核函数值）：

$$
K(x, x’) = \phi(x)^T \phi(x’)
$$

• (x, x’)：原始空间中的两个样本点
• (\phi(x), \phi(x’))：将样本映射到高维特征空间后的向量（通常无法显式得到映射函数，代码也不写，不用多考虑）
• (K(x, x’))：核函数的值，即映射后向量的内积，表示样本间的相似度

高斯核函数的两种常见形式

高斯核函数常用来衡量两个样本点 $x$ 和 $x’$ 的相似度：

形式一

$$
K(x, x’) = \exp\big(-\gamma |x - x’|^2\big)
$$

• $\gamma$ 是核函数的参数，控制“衰减速度”。

形式二

$$
K(x, x’) = \exp\left(-\frac{|x - x’|^2}{2\sigma^2}\right)
$$

• $\sigma$ 是核函数的带宽参数，控制核函数的宽度，决定了核函数对样本间距离的敏感度，$\sigma$ 越大，核函数的响应越“宽”，远距离样本之间的相似度也越高。
• 两者关系：

$$
\gamma = \frac{1}{2\sigma^2}
$$

对偶目标函数

$$
\max_{\alpha} \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 K(x_i, x_j)
$$

$$
\sum_{i=1}^m \alpha_i y_i = 0, \quad \alpha_i \geq 0, \quad i=1,2,\dots,m
$$

• $m$：训练样本总数
• $\alpha_i$：拉格朗日乘子，代表样本点的重要程度，值越大说明对应样本对分类边界贡献越大
• $y_i \in {+1, -1}$：第 $i$ 个样本的类别标签
• $x_i$：第 $i$ 个样本的输入特征向量

通过核矩阵，算法决定哪些点重要（即支持向量）

重要的点对应的权重$a_i $ 非零，不重要的权重为零，虽然计算了所有点对，但最终模型只使用支持向量做决策

---

无监督学习

K 均值算法（K-Means Clustering）

K 均值是一种无监督学习算法，通过将数据划分成 (K) 个簇（群集），使得同一簇内的数据点相似度高，不同簇间差异大。

核心

随机初始化：一开始随机选取 𝐾 个点作为初始质心（中心点）。

划分阶段：根据距离，把每个点归到最近的质心的簇。（点离哪个质心最近归谁）

更新阶段：计算每个簇所拥有点的均值，把质心移动到这个均值位置。

重复步骤 2 和 3：用新的质心重新划分数据点，再更新质心，直到质心位置基本不变（收敛）或者达到最大迭代次数。

特征缩放

特征缩放（Feature Scaling）是常用的数据预处理方法，目的是将不同尺度的特征转换到相似的尺度范围内，提升机器学习模型的收敛速度和数值稳定性。

由于标准的 K 均值算法默认所有特征权重相同，不会自动区分哪些特征更重要，每个特征在计算欧氏距离时的“重要性”是一样的。所以在用 K 均值算法前，需要对各特征进行缩放让它们的尺度相似。

Z-score 标准化（标准差标准化）

$$
z = \frac{x - \mu}{\sigma}
$$

• (x) 是原始特征值
• (\mu) 是该特征均值
• (\sigma) 是该特征标准差（消除不同特征的波动差异，除样本量没意义）

Min-Max 归一化

$$
x’ = \frac{x - x_{\min}}{x_{\max} - x_{\min}}
$$

• $x$ 是原始特征值
• $x_{\min}$ 是该特征的最小值
• $x_{\max}$ 是该特征的最大值
• $x’$ 是归一化后的特征值，范围在 $[0, 1]$

均值归一化（Mean Normalization）

$$
x’ = \frac{x - \bar{x}}{x_{\max} - x_{\min}}
$$

• 参数同上
• $x’$ 范围变为 $[-1, 1]$ 附近（可能超出，总体趋势在范围内，和极值有关）

目标函数

将数据集分成 (K) 个簇，最小化簇内点到簇中心的距离平方和：

$$
J = \sum_{k=1}^K \sum_{x_i \in C_k} | x_i - \mu_k |^2
$$

• $C_k$：第 $k$ 个簇的所有点集合
• $\mu_k$：第 $k$ 个簇的质心（均值）

算法步骤

1. 初始化：随机选择 $K$ 个点作为初始簇中心 $\mu_k$。

2. 分配步骤：将每个点分配给距离最近的簇中心：

$$
c_i = \arg\min_{k} | x_i - \mu_k |^2
$$

3. 更新步骤：重新计算每个簇的质心：

$$
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i
$$

• arg min 表示函数取得最小值时对应的变量取值

4. 重复步骤 2 和 3，直到簇分配不再变化或达到最大迭代次数。

代码实现

from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
import numpy as np

# 示例数据
X = np.array([[1, 2], [1, 4], [1, 0],
              [4, 2], [4, 4], [4, 0]])

# 数据标准化
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# 创建模型，指定簇数，random_state =0固定随机结果，产生相同的随机数序列
kmeans = KMeans(n_clusters=2, random_state=0)

# 训练模型(标准化后)
kmeans.fit(X_scaled)

# 簇中心
print("簇中心：", kmeans.cluster_centers_)

# 预测每个点所属簇
print("簇标签：", kmeans.labels_)

import torch

def kmeans(X, num_clusters=2, num_iters=100, device='cpu'):
    X = X.to(device)

    # 随机初始化质心
    indices = torch.randperm(X.size(0))[:num_clusters]
    centroids = X[indices]

    for _ in range(num_iters):
        # 计算每个点到每个质心的距离
        distances = torch.cdist(X, centroids)  # [num_points, num_clusters]

        # 分配标签为最近质心索引
        labels = torch.argmin(distances, dim=1)

        new_centroids = []
        for k in range(num_clusters):
            assigned = X[labels == k]
            if assigned.size(0) == 0:
                # 如果该簇没有点，随机重新初始化质心
                new_centroids.append(X[torch.randint(0, X.size(0), (1,))].squeeze(0))
            else:
                new_centroids.append(assigned.mean(dim=0))
        new_centroids = torch.stack(new_centroids)

        # 判断质心是否收敛
        if torch.allclose(centroids, new_centroids, atol=1e-4):
            break

        centroids = new_centroids

    return centroids, labels

# 示例用法
if __name__ == "__main__":
    X = torch.tensor([[1., 2.], [1., 4.], [1., 0.],
                      [4., 2.], [4., 4.], [4., 0.]])
    centroids, labels = kmeans(X, num_clusters=2)
    print("簇中心：", centroids)
    print("簇标签：", labels)

肘部算法（Elbow Method）

肘部算法是用于确定 KMeans 聚类中最佳簇数 $K$ 的一种经典算法。

每个簇的质心

对于第 $k$ 个簇 $C_k$，其质心 $\mu_k$ 定义为：

$$
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i
$$

• $C_k$：第 $k$ 个簇的样本集合
• $|C_k|$：第 $k$ 个簇的样本个数（是集合的基数，不是绝对值！！）
• $x_i$：属于第 $k$ 个簇中的样本点

根据可视图视觉判断拐点

---

主成分分析（PCA）

PCA 的目标是找到一个低维子空间，使数据投影到这个子空间后具有最大方差，尽可能保留原始数据的信息量。

它通过寻找一组新的正交基（主成分）来重新表达数据。这些主成分按照方差大小排序。
（第一主成分是方差最大的方向，第二主成分与第一主成分正交，方差次大，依此类推）

简单来说，PCA 在做一组新的特征加权和，这个加权通过线性代数自动计算得出，目的是让数据在新坐标轴上的分布尽可能分散，从而尽可能保留原始数据的结构和信息。

数据中心化（Data Centering）

数据中心化的目的是将数据的参考线（基准线）从原点移动到样本均值，处理后能更清晰地反映数据的波动和差异。

对于第 $j$ 个维度，所有样本的均值计算公式为：

$$
\bar{x}j = \frac{1}{n} \sum{i=1}^{n} x_{ij}
$$

• $n$：样本总数
• $x_{ij}$：第 $i$ 个样本第 $j$ 个维度的取值

将每个样本的该维度值减去均值，得到中心化后的数据：

$$
x_{ij}^{centered} = x_{ij} - \bar{x}_j
$$

处理后，该维度所有样本的均值变为 0（就是平均值为 0）。

异常检测算法

异常检测的目标：不是为了学会“异常长什么样”，而是学会“什么是正常”。所以遇到异常样本不是判断样本异常，而是非正常。因此异常检测算法允许甚至默认异常样本极少甚至没有。

轴对轴独立误判问题

异常点在整体空间异常，但在每个轴上的投影看起来“正常”，如果算法只考虑单变量的概率（如高斯分布），会误判为正常点。

多变量高斯分布

多变量高斯分布是 一组变量的联合概率分布，它不仅考虑每个变量的单独分布，还考虑它们之间的相关性。
有几个特征（feature），就需要几维的协方差矩阵。

---

协同过滤算法

协同过滤（Collaborative Filtering，CF）是一种基于历史行为数据来进行推荐的算法，广泛应用于推荐系统中。其核心思想是通过用户之间或物品之间的相似度，来预测用户可能感兴趣的物品。

1. 表示交互数据，构建稀疏矩阵 $R \in \mathbb{R}^{|U| \times |I|}$
2. 计算相似度
3. 邻域选择，选取最相似的 $k$ 个邻域。
4. 偏好预测，聚合邻域信息，估计预期评分。

缺点

• 稀疏性问题：用户-物品矩阵通常非常稀疏，影响相似度计算准确性。
• 冷启动问题：对新用户或新物品缺乏足够数据难以推荐。
• 计算成本高：数据过大时相似度计算和搜索开销大。

公式（非重点）

• 余弦相似度（User-Based）

  $$
  \text{sim}(u,v) = \frac{\sum_{i \in I_{uv}} r_{u,i} \times r_{v,i}}{\sqrt{\sum_{i \in I_u} r_{u,i}^2} \times \sqrt{\sum_{i \in I_v} r_{v,i}^2}}
  $$

  其中，$r_{u,i}$ 是用户 $u$ 对物品 $i$ 的评分，$I_u$ 是用户 $u$ 评分过的物品集合，$I_{uv} = I_u \cap I_v$。

• 预测评分
  $$
  \hat{r}{u,j} = \frac{\sum{v \in N(u)} \text{sim}(u,v) \times r_{v,j}}{\sum_{v \in N(u)} |\text{sim}(u,v)|}
  $$
  其中，$N(u)$ 是用户 $u$ 的邻居集合，$r_{v,j}$ 是邻居 $v$ 对物品 $j$ 的评分。

---

大数据集处理

随机梯度下降（Stochastic Gradient Descent，SGD）

随机梯度下降是一种优化算法，用于通过迭代方式最小化目标函数（如损失函数），尤其适合大规模数据训练。

基本思想

• 与批量梯度下降（Batch Gradient Descent）每次使用全部训练样本计算梯度不同，随机梯度下降每次只用一个样本来计算梯度并更新参数。

算法步骤

假设模型参数为 $\theta$，学习率为 $\alpha$，训练集共有 $m$ 个样本：

1. 初始化参数 $\theta$
2. 对于每个训练样本 $(x^{(i)}, y^{(i)})$：
   • 计算梯度：
     $$
     g_i = \nabla_\theta L(h_\theta(x^{(i)}), y^{(i)})
     $$
   • 更新参数：
     $$
     \theta := \theta - \alpha g_i
     $$
3. 重复多轮迭代，直到收敛

优点

• 计算速度快，每次更新只需用一个样本
• 能跳出局部极小值，适合非凸优化
• 适合在线学习，能处理动态数据

缺点

• 更新过程带噪声，收敛不如批量梯度下降稳定
• 收敛路径可能震荡，需采用学习率衰减或优化技巧

Mini-Batch 梯度下降

Mini-Batch 梯度下降是批量梯度下降和随机梯度下降之间的一种折中方法。

基本思想

• 将训练数据划分成若干个小批次（mini-batch），每个小批次包含一定数量的样本。
• 每次使用一个 mini-batch 计算梯度并更新参数。

算法步骤

假设参数为 $\theta$，学习率为 $\alpha$，数据集共有 $m$ 个样本，mini-batch 大小为 $b$：

1. 将训练集划分为 $\lceil m / b \rceil$ 个 mini-batch。
2. 对每个 mini-batch：
   • 计算该批次的平均梯度：
     $$
     g = \frac{1}{b} \sum_{i=1}^b \nabla_\theta L(h_\theta(x^{(i)}), y^{(i)})
     $$
   • 更新参数：
     $$
     \theta := \theta - \alpha g
     $$

优点

计算效率高，梯度估计更准确，训练更稳定，可优化批量计算

缺点

• 需要选择合适的 mini-batch 大小，大小不合适会影响性能
• 仍有一定的噪声，可能导致收敛震荡

随机梯度下降收敛

随机梯度下降（SGD）由于每次只用一个样本计算梯度，参数更新带有噪声，因此其收敛性质与批量梯度下降不同。

特点

• 噪声性质：SGD 更新方向是梯度的无偏估计，但含有随机噪声，导致参数在最优值附近振荡。
• 收敛速度：初期收敛较快，但后期由于噪声，难以完全收敛到精确的最优点。
• 学习率衰减：通过逐渐减小学习率，可以减小振荡幅度，使参数更接近最优值，从而保证收敛。

理论

• 在凸函数和合适的学习率条件下，SGD 几乎必然收敛到全局最优解。
• 在非凸问题（如深度神经网络）中，SGD 有能力跳出局部极小值，找到较好解。

虽然 SGD 本质带噪声，但通过合理设计学习率和优化技巧，可以实现稳定且高效的模型训练收敛。

Map-Reduce 中的“减少映射”与“数据并行”

在使用 Map-Reduce 模型处理大规模数据时，有两个核心思想帮助提高效率和扩展性：

减少映射（Reducing Mapping）

在分布式数据处理中，每个节点独立处理一部分数据，生成大量中间结果。为减轻后续合并和计算的压力，可以在本地尽量合并相同的结果或者过滤无关数据，减少传输的数据量。

这种减少是对中间结果进行本地的预聚合或筛选，保证传递给下一阶段的数据包含所有必要的信息，不会影响最终计算结果的正确性。

数据并行（Data Parallelism）

将大数据集划分成多个子块，在不同的计算节点或线程上独立执行相同的 Map 或 Reduce 操作，从而实现并行处理。

同一函数并行处理不同数据子集，计算过程中节点彼此独立无需通信（完成后要汇总），易扩展计算资源（简而言之方便加入增加计算节点而不影响已有系统的运行和架构）。