模式识别笔记汇总
本次笔记主要关于K-Means 及其变分问题、熵不等式、Softmax/Softmin 函数、数值稳定化、以及泛函与方向导数等内容。
K-Means 基本原理与能量函数
K-Means 能量函数的定义
K-Means 算法的能量函数（目标函数）定义如下：
$$
E(\vec{U}, \vec{C})
= \sum_{x \in \Omega} \sum_{k=1}^{K} \bigl(f(x) - C_k\bigr)^2 U_k(x)
$$
其中：
- $ f(x) $ 表示数据点 $ x $ 的特征值；
- $ C_k $ 表示第 $ k $ 个聚类中心；
- $ U_k(x) $ 为归属矩阵的元素，表示数据点 $ x $ 是否属于第 $ k $ 个簇（在硬分类中，取值为 0 或 1）。
然后定义
$$
\langle \overrightarrow{O}, \overrightarrow{u} \rangle = \sum_{x \in \Omega} \sum_{k=1}^{K} O_k(x) \cdot u_k(x)
$$
其中误差函数为：
$$
O_k(x) = \bigl(f(x) - C_k\bigr)^2
$$
该能量函数也可用内积的形式表示：
$$
E(\vec{U}, \vec{C}) = \langle \vec{O}, \vec{U} \rangle
$$
其中 $\vec{O}$ 为一个误差向量。
K-Means 算法的迭代更新规则
K-Means 算法通过两步交替迭代来最小化能量函数 $E(\vec{U}, \vec{C})$：
更新归属矩阵 $\vec{U}^{t+1}$：
$$
\vec{U}^{t+1} = \arg \min_{\vec{U}} E(\vec{U}, \vec{C}^t)
$$具体到每个样本点 $x$ 的更新规则为：
$$ U_k^{t+1}(x)= \begin{cases} 1, & \text{if} k = \arg \min_{k \in \{1, \dots, K\}} (f(x) - C_k^t)^2 \\ 0, & \text{otherwise} \end{cases} $$即将每个数据点分配给距离其最近的簇中心。
更新聚类中心 $\vec{C}^{t+1}$：
$$
\vec{C}^{t+1} = \arg \min_{\vec{C}} E\bigl(\vec{U}^{t+1}, \vec{C}\bigr)
$$即对每个簇的样本求均值，作为新的聚类中心。
误差函数与误差向量
定义误差函数：
$$
O_k(x) = \bigl(f(x) - C_k\bigr)^2
$$
令
$$
\vec{O}(x) = \bigl(O_1(x), O_2(x), \dots, O_K(x)\bigr)^\mathsf{T},
$$
则 $\vec{O}$ 是一个向量值函数，映射
$$
\vec{O}: \Omega \subseteq \mathbb{R}^2 \to \mathbb{R}^K.
$$
备注
- K-Means 采用硬聚类方式，每个数据点只能属于一个簇，$U_k(x) \in {0,1}$。
- 优化目标：在每次迭代中，先更新 $\vec{U}$，再更新 $\vec{C}$，直至收敛。
- 计算复杂度：主要与数据点数 $N$ 和簇数 $K$ 有关，通常为 $O(NKT)$（$T$ 为迭代次数）。
K-Means 的变分问题与熵的性质
K-Means 变分问题
我们希望最小化下述能量函数：
$$
\min_{\vec{U}, \vec{C}} E(\vec{U}, \vec{C})
$$
其中 $\vec{U}$ 为归属矩阵，$\vec{C}$ 为聚类中心。
除硬划分之外，还可使用许多优化或正则化技巧，例如引入软分类思想（softmax / softmin）的方法。
熵的性质
在分析 K-Means 变分问题时，引入熵的一条不等式，用于约束归属矩阵的对数项：
$$
-\ln K
\le \langle \vec{U}, \ln \vec{U} \rangle
\le 0
$$
其中：
- $U_k$ 表示数据点对第 $k$ 个簇的归属概率（软分类时可在 $[0,1]$ 之间）；
- $\langle \vec{U}, \ln \vec{U}\rangle = \sum_{k=1}^{K} U_k \ln U_k$ 是熵相关的项。
该不等式可以用 Jensen 不等式等方法证明。等号成立的两种情况为：
- 左边等号：所有 $U_k = \frac{1}{K}$，即均匀分布；
- 右边等号：某一个 $U_k=1$，其它为 0，即完全硬分类。
变分方法的直观解释
- 最优化角度：寻找最优的 $\vec{U}, \vec{C}$ 使得数据点与簇中心的总体误差最小；
- 信息论角度：考虑信息熵约束，避免过度偏向某一簇，从而获得更合理的簇划分。
备注
- 熵的约束：对归属矩阵 $ \vec{U} $ 提供了额外的正则约束。
- 与 EM（期望最大化）算法中的软聚类思想存在对应关系。
熵不等式的证明
这里给出熵不等式：
$$
-\ln K
\leq \langle \vec{U}, \ln \vec{U} \rangle
\leq 0
$$
的推导思路详述如下：
证明 $f(u)=-\ln u$ 是凸函数：
函数 $f(u) = -\ln u$ 的一阶导数和二阶导数分别为：
$$
f’(u) = -\frac{1}{u},
\quad
f’’(u) = \frac{1}{u^2} > 0 \quad (u>0)
$$
由于 $f’’(u) > 0$，可知 $f(u)$ 是凸函数。
计算极限 $\lim\limits_{u\to0^+} u \ln u$：
令 $g(u) = -u \ln u$，求其极限：
$$
\lim_{u\to0^+} u \ln u = \lim_{u\to0^+} \frac{\ln u}{1/u}
$$
利用洛必达法则，分子求导得$1/u$，分母求导得 $-1/u^2$，因此：
$$
\lim_{u\to0^+} \frac{\ln u}{1/u} = \lim_{u\to0^+} \frac{1/u}{-1/u^2} = \lim_{u\to0^+} -u = 0
$$
所以：
$$
\lim_{u\to0^+} u \ln u = 0.
$$
这表明当 $u \to 0$ 时，$u \ln u$ 趋于 0。
用 Jensen 不等式推导熵不等式：
由于 $f(x)=-\ln x$ 是凸函数，因此对于满足 $\sum_{k=1}^{K} \alpha_k = 1$ 且 $ 0 \leq \alpha_k \leq 1$ 的权重 $\alpha_{k} $ ，有：
$$
\left( \sum_{k=1}^{K} \alpha_k x_k \right) \leq \sum_{k=1}^{K} \alpha_k f(x_k)
$$
取 $\alpha_k = U_k$，$x_k = \frac{1}{U_k}$，则：
$$
-ln \left( \sum_{k=1}^{K} U_k \cdot \frac{1}{U_k} \right) \leq \sum_{k=1}^{K} U_k (-\ln \frac{1}{U_k})
$$
由于 $\sum_{k=1}^{K} U_k = 1$，所以：
$$
-ln K \leq \sum_{k=1}^{K} U_k \ln U_k \leq 0
$$
即
$$
ln K \geq -\langle \vec{U}, \ln \vec{U} \rangle
$$
等号成立的条件：
- 左边等号成立条件：当所有 $U_k$ 相等，即 $U_k = 1/K$ 时，左侧等号成立。
- 右边等号成立条件：当仅有一个 $U_k=1$，其余 $U_k=0$ 时，右侧等号成立。
熵不等式在 K-Means 变分问题中的作用：
该不等式用于限制聚类的过度集中，即防止所有数据点都归属于同一簇。同时，它也鼓励一定程度的分散度，使簇划分更加均匀，从而优化聚类效果。
K-Means 的变分问题扩展
在传统 K-Means 的能量函数 $E(\vec{U}, \vec{C})$ 基础上，引入一项基于熵的正则化：
$$
\min_{\vec{u}\in U}
\Bigl[
E(\vec{u}, \vec{C})
+\varepsilon \langle \vec{u}, \ln \vec{u}\rangle
\Bigr]
$$
其中 $\varepsilon > 0$ 为权衡系数（正则化参数）。当 $\varepsilon \to 0$ 时，该模型接近传统 K-Means 硬分类；当 $\varepsilon$ 较大时，模型更倾向于软聚类。
更新过程：
- $\vec{u}^{t+1} = \arg \min_{\vec{u}} \bigl[E(\vec{u}, \vec{C}^t) - \varepsilon H(\vec{u})\bigr]$ (变成了严格凸)
- $\vec{C}^{t+1} = \arg \min_{\vec{C}} \bigl[E(\vec{u}^{t+1}, \vec{C})\bigr]$ （与传统 K-Means 相同）
这里的熵项
$$
H(\vec{u})
= - \sum_{k=1}^{K} \sum_{x\in \Omega} u_k(x)\ln u_k(x)
$$
作为“软化”或正则化手段，避免完全的 0-1 硬分类。
偏导数计算
熵项 $H(\vec{u})$ 可重写为
$$
-H(\vec{u}) = \langle \vec{u}, \ln \vec{u} \rangle.
$$
对于目标函数 $E(\vec{u}, \vec{C}) - \varepsilon H(\vec{u})$，计算其关于 $u_k$ 的偏导数：
设 $E(\vec{u}, \vec{C})$ 关于 $u_k$ 的偏导数为：
$$
\frac{\delta E}{\delta u_k} = O_k
$$对于熵项：
$$
\frac{\delta (-H)}{\delta u_k} = \ln u_k + 1
$$结合上述结果，求解极值条件：
$$
O_k - \varepsilon (\ln u_k + 1) = 0
$$化简得：
$$
u_k = \exp\left(-\frac{O_k}{\varepsilon} - 1\right)
$$
这表明更新 $u_k$ 时，其值受 $\varepsilon$ 控制，较大的 $\varepsilon$ 使得 $u_k$ 更加平滑，有助于软聚类。
拉格朗日函数与 Softmax 分析
拉格朗日函数
定义拉格朗日函数：
$$
\mathcal{L}(\vec{u}, \lambda)
= E(\vec{u}, \vec{c})
-\varepsilon H(\vec{u})+\sum_{x \in \Omega} \lambda(x)
\Bigl(
\sum_{k=1}^{K} u_k(x)-1
\Bigr)
$$
其中：
- $H(\vec{u})$ 是熵项；
- $\lambda(x)$ 为拉格朗日乘子，用于保证 $\sum_{k=1}^{K} u_k(x)=1$。
软分类 (Softmin / Softmax) 的推导
对 $\mathcal{L}(\vec{u}, \lambda)$ 关于 $u_k$ 取偏导为 0，可得到：
$$
\ln u_k(x)= -\frac{O_k(x) +\lambda(x)}{\varepsilon}
$$
其中 $O_k$ 是某类损失（例如 $(f(x)-C_k)^2$ ）或能量。
结合约束 $\sum_{k=1}^K u_k(x)=1$，可得Softmin形式：
$$
u_k^{t+1}(x)= \frac{\exp\Bigl(\dfrac{-O_k(x)}{\varepsilon}\Bigr)}{\sum_{j=1}^{K} \exp\Bigl(\dfrac{-O_j(x)}{\varepsilon}\Bigr)}
$$
也可写成softmax形式：
$$ \text{Softmax}_{\varepsilon}(-\vec{O}) = \left[\text{Softmin}_{\varepsilon}(\vec{O})\right]_k $$极限问题与分母拆分
k-means 硬分类更新公式
当不考虑熵正则化时，k-means 的硬分类可写为：
$$
u_k^{t+1}(x) =
\begin{cases}
1, & \text{if } k = \arg \min_{k \in {1, \dots, K}} O_k, \
0, & \text{otherwise}.
\end{cases}
$$
Softmin 的极限
考虑
$$ \lim_{\varepsilon \to 0^+} \frac{\exp\bigl(-O_k(x)/\varepsilon\bigr)}{\sum_{j=1}^K \exp\bigl(-O_j(x)/\varepsilon\bigr)} =\lim_{\varepsilon \to 0^+}\frac{\exp\bigl(-O_k(x)+m(x)/\varepsilon\bigr)}{\sum_{j\in M} \exp\bigl(-O_j(x)+m(x)/\varepsilon\bigr)+\sum_{j\notin M} \exp\bigl(-O_j(x)+m(x)/\varepsilon\bigr)} $$令 $m = \min \bigl\{ O_1(x), O_2(x), \dots, O_K(x) \bigr\}, \quad M = \arg\min_{k \in \bigl\{ 1, \dots, K \bigr\}} O_k(x)$。
当 $\varepsilon \to 0^+$，对于属于最优集 $M$ 的索引 $k$，$\exp(-O_k/\varepsilon)$ 主导；而不是最优集的 $\exp(-O_k/\varepsilon)$ 迅速衰减为 0。因此极限结果为：
这与 k-means 硬分类（一次只属于距离最近的簇）相一致。
称 $\min_{\vec{u}\in U，\vec{C}}\Bigl[E(\vec{u}, \vec{C})-\varepsilon H(u)\Bigr]$ 为softmin/softmax的分类的变分优化问题
k-means 的光滑化与 Softmax 溢出问题
k-means 的光滑化
通过在 k-means 能量函数中加入熵项并令 $\varepsilon>0$，可以将硬分类变为软分类，使其输出变得连续可导。
- 当 $\varepsilon \to 0$，Softmin 退化为 k-means 硬分类；
- 当 $\varepsilon$ 较大时，软分类更加显著。
Softmax 的数值溢出问题
Softmax 标准形式：
$$ \text{Softmax}\bigl(\vec{O}\bigr)_k = \frac{e^{O_k}}{\sum_{j=1}^K e^{O_j}}. $$若 $O_k$ 值过大，$e^{O_k}$ 可能数值溢出。
解决方案：数值稳定化
取 $\displaystyle M = \max\{O_1, O_2, \dots, O_K\}$ ，将所有项减去 $M$：
这样可防止溢出，保持结果不变。
泛函分析与方向导数
泛函与方向导数基本概念
在更高层次，令
$$ J: \mathcal{F} \to \mathbb{R} $$是作用于函数空间 $\mathcal{F}$ 的一个泛函（functional）。对于 $u(x)$ 的变化，可以定义方向导数：
$$ \lim_{h \to 0} \frac{J\bigl(x + hv\bigr) - J(x)}{h} = \left. \frac{d}{dh} J\bigl(x + hv\bigr) \right|_{h=0} $$方向导数与梯度存在对应关系：若把 $\nabla J=(\tfrac{\delta J}{\delta x_1}，\tfrac{\delta J}{\delta x_2} \cdot \cdot \cdot \tfrac{\delta J}{\delta x_n})$ 类比于有限维中的梯度，则方向导数可理解为梯度在 $v$ 方向的投影。
方向导数与梯度的关系
对 $J(U_k)$ 做微分：
$$ \langle \tfrac{\delta J}{\delta U_k}, V_k \rangle = \left. \tfrac{d}{dh} J\bigl(U_k + hV_k\bigr) \right|_{h=0}. $$例如，若
$$ J(U_k) = \sum_{x\in \Omega} O_k(x)\ln U_k(x), $$则
$$ J(U_k + hV_k) = \sum_{x\in \Omega} O_k(x)\ln\bigl(U_k(x) + hV_k(x)\bigr) $$对其在 $h=0$ 处求导，可得到对应的偏导，从而确定梯度形式。
九、总结与要点
K-Means 算法
- 能量函数：数据点到簇中心的平方误差和；
- 经典迭代：硬分类与均值更新交替进行。
K-Means 的变分扩展
- 通过引入熵（软分类），可得到 Softmin / Softmax 形式；
- 当正则系数 $\varepsilon \to 0$ 时，又可退化到原始硬划分结果。
熵不等式与数值稳定
- 熵提供了在聚类中的分布约束；
- Softmax 需用数值移位避免溢出。
泛函与方向导数
- 在更高阶场景中，可将 K-Means 问题放到泛函分析框架下；
- 方向导数、梯度概念可帮助理解对函数空间的优化。