引言
Word2Vec Embedding 技术
Word2Vec 是一种用于将单词映射到向量空间的技术，通过训练语料库来学习单词的语义关系。核心思想是将单词转换为一个高维向量，使得语义相近的单词在向量空间中距离较近。
Word2Vec 过程
- 输入文本（例如：”我”、”是”、”中国”、”人民”）
- 嵌入层（Embedding）：将单词转换为向量表示
- 训练：使用 Skip-gram 或 CBOW 模型进行训练
- 输出向量：得到语义空间中的词向量表示
在黑板上的示例中，展示了单词如何通过 Word2Vec 进行向量化，并且最终映射到一个 n 维向量空间中。
K-Means 聚类算法
K-Means 是一种常见的无监督学习算法，主要用于数据聚类。其基本思想是：
- 给定样本集合 $S$，包含样本 $S_1, S_2, \dots, S_k$。
- 设定 $k$ 个聚类中心 $C_1, C_2, \dots, C_k$。
- 将样本 $f$ 分配给最近的聚类中心 $C_k$。
数学定义
定义样本 $f$ 归属于最接近的簇：
$$
U_k^* =
\begin{cases}
1, & f \in S_k \
0, & \text{otherwise}
\end{cases}
$$
其中，样本 $f$ 的归属取决于其与聚类中心 $C_k$ 的欧式距离：
$$
| f - C_k |^2
$$
因此，每个样本都会归属于离它最近的簇。
K-Means 迭代步骤
- 随机初始化 $k$ 个聚类中心 $C_1, C_2, \dots, C_k$。
- 计算每个样本到聚类中心的距离，并将其分配到最近的簇。
- 更新聚类中心，使其成为簇中所有样本的平均值。
- 重复步骤 2 和 3，直到聚类中心不再发生变化或达到迭代次数上限。
总结
- Word2Vec 将单词映射到向量空间，使语义相似的单词在向量空间中更接近。
- K-Means 通过反复迭代，将数据点划分到不同的簇中进行聚类分析。
这两者结合在自然语言处理 (NLP) 中可用于 文本分类、聚类分析 等任务。例如，先用 Word2Vec 将文本转换为向量，然后使用 K-Means 进行文本聚类。
kmeans算法的定义
独热编码（One-Hot Encoding）
在 K-Means 聚类算法中，我们使用独热编码（One-Hot Encoding）来表示样本所属的类别：
若样本 $f$ 属于第 $k$ 个簇，则其独热编码表示为
$$
\mathbf{U}^* = (0, 0, \dots, 1, \dots, 0)
$$其中只有第 $k$ 维的值为 1，其余维度为 0。
例如：
- 若 $f \in S_1$：
$$
\mathbf{U}^* = (1, 0, 0, \dots, 0)
$$ - 若 $f \in S_k$：
$$
\mathbf{U}^* = (0, 0, \dots, 1, \dots, 0)
$$
- 若 $f \in S_1$：
K-Means 目标函数
在 K-Means 算法中，我们的目标是最小化样本点到其分配的聚类中心的距离平方和：
$$
\mathbf{U}^* = \arg\min_{\mathbf{U} \in \mathcal{U}} \sum_{k=1}^{K}U_k (f - C_k)^2
$$
其中：
- $\mathcal{U}$ 是所有可能的独热编码集合：
表示每个样本点只能属于一个簇。
定理及其证明
定理（Thm）
对于任意样本 $f$ 和聚类中心 $C_1, C_2, \dots, C_K$，定义：
$$ U_k^* = \begin{cases} 1, & k = \arg\min\limits_{R=1,2,\dots,K} (f - C_R)^2 \\ 0, & \text{else} \end{cases} $$即，样本 $f$ 应该被分配到使得 $(f - C_k)^2$（最小值唯一） 最小的簇 $C_k$。
证明（Proof）
定义
$$
m = \min_{k \in {1,2,\dots,K}} {(f - C_k)^2}
$$由于 $U_k$ 是独热编码，所有可能的 $U_k$ 满足
$$
\sum_{k=1}^{K} U_k = 1
$$目标函数展开：
$$
\sum_{k=1}^{K} U_k (f - C_k)^2 \geq\ \sum_{k=1}^{K} U_k \cdot m
$$由于 $\sum_{k=1}^{K} U_k = 1,$ 代入可得：
$$
\sum_{k=1}^{K} U_k (f - C_k)^2 \geq m
$$取 $U_k^*$ 使得 $k$ 取最小距离的索引，则：
$$
\sum_{k=1}^{K} U_k^* (f - C_k)^2 = m.
$$这说明只有当 $U_k^$ 取最优独热编码时，目标函数才能取到最小值 $m$ ，从而证明了 $U_k^$ 具有唯一最优解。
结论
- 独热编码 用于表示样本所属的类别，每个样本只能属于一个簇。
- 目标函数 通过最小化样本到其最近聚类中心的距离平方和，确定最优分类。
- 定理证明 说明了最佳分配方案是将样本分配到使得 $(f - C_k)^2$ 最小的簇。
这一定理是 K-Means 算法的核心之一，保证了算法在每一步迭代中都能使目标函数收敛到一个局部最优解。
–
连续情况下的 K-Means 聚类定义
在离散情况下，我们用有限个样本点 $f$ 进行聚类，而在连续情况下，需要对整个定义域 $\Omega$ 进行考虑。
目标函数扩展到连续情况
设函数 $f: \Omega \to \mathbb{R}$，其中 $\Omega$ 是定义域，$f(x)$ 是定义在 $\Omega$ 上的连续函数。
目标是在整个 $\Omega$ 上最小化聚类误差：
$$
\min_{\mathbf{U}(x) \in \mathcal{U}} \sum_{x \in \Omega} \sum_{k=1}^{K} U_k(x) (f(x) - C_k)^2
$$其中：
- $C_1, C_2, \dots, C_K$ 为 $K$ 个聚类中心。
- $U_k(x)$ 表示位置 $x$ 归属于第 $k$ 个聚类中心的程度。
约束条件
为了保证每个点 $x$ 仅归属于一个聚类簇，引入约束：
$$ \mathcal{U} = \left\{ \mathbf{U}(x) = (U_1(x), U_2(x), \dots, U_K(x)) \,\middle|\, \sum_{k=1}^{K} U_k(x) = 1, \quad 0 \leq U_k(x) \leq 1, \quad \forall x \in \Omega \right\} $$这意味着：
- 每个 $x$ 只能属于一个簇（即某个 $U_k(x)$ 取 1，其余取 0）。
- $U_k(x)$ 的取值范围在 $[0,1]$ 之间。
直观解释
从黑板上的示意图可以看出：
- $x \in \Omega$ 表示数据点在连续空间中的分布。
- $f(x)$ 代表数据点的特征值。
- 目标是将这些数据点划分到不同的簇 $C_1, C_2, \dots, C_K$ 中，使得同一簇中的点具有较小的方差。
结论
- 在连续情况下，K-Means 的目标函数和约束条件从离散样本点扩展到了整个定义域 $\Omega$。
- 目标仍然是最小化数据点到聚类中心的平方误差。
- 约束条件确保每个点 $x$ 只能归属于一个簇。
- 这种扩展形式在实际应用中可用于处理连续空间中的数据，如图像分割或概率密度估计。
K-Means 迭代优化过程
K-Means 算法的目标是最小化聚类误差 $E(\mathbf{U}, \mathbf{C})$，即样本点到其聚类中心的平方误差和。它采用 迭代优化 的方式，在每次迭代中交替更新 簇分配 和 聚类中心，直到收敛。
定义
聚类中心向量：
$$
\mathbf{C} = (C_1, C_2, \dots, C_K)^T.
$$K-Means 的优化目标：
$$
\min_{\mathbf{U} \in \mathcal{U}, \mathbf{C}} E(\mathbf{U}, \mathbf{C}).
$$
Step 1：更新簇分配 $\mathbf{U}$
$$
\mathbf{U}^{t+1} = \arg\min_{\mathbf{U} \in \mathcal{U}} E(\mathbf{U}, \mathbf{C}^t).
$$
其中，$U_k^{t+1}(x)$ 按照最近邻准则更新：
$$ U_k^{t+1}(x) = \begin{cases} 1, & k = \arg\min\limits_{\,k' \in \{1,2,\dots,K\}} \bigl(f(x) - C_{k'}^t\bigr)^2 \\ 0, & \text{otherwise} \end{cases} $$即，将样本 $x$ 归到当前最近的聚类中心 $C_k^t$。
Step 2：更新聚类中心 $\mathbf{C}$
$$
\mathbf{C}^{t+1} = \arg\min_{\mathbf{C}} E(\mathbf{U}^{t+1}, \mathbf{C}).
$$
聚类中心的更新公式：
$$
C_k = \frac{\sum\limits_{x \in \Omega} U_k^{t+1}(x) , f(x)}{|\Omega_k|},
$$
其中：
- $\Omega_k$ 是当前属于第 $k$ 个簇的所有样本点集合。
- 上式表示：新的聚类中心是该簇内所有样本的加权平均值。
- 也可以把$\Omega_k$替换成$\sum_{x \in \Omega} U_k^{t+1} (x) := \Omega^{t+1}_{k}$
总结
- Step 1：更新簇分配，使得每个点归属于与其最近的聚类中心。
- Step 2：更新聚类中心，使其为簇内所有点的均值。
- 这两步交替进行，直到聚类中心不再变化，算法收敛。
目标函数关于聚类中心的推导
以下演示 Step 2（更新聚类中心）中，如何对目标函数关于聚类中心 $C_k$ 求导并得到更新公式。为简化，只对离散情形展示，连续情形可将求和替换为积分，思路相同。
目标函数拆分
K-Means 的目标函数（离散情形）：
$$
E(\mathbf{U}, \mathbf{C})
= \sum_{k=1}^{K} \sum_{x \in \Omega} U_k(x)\bigl(f(x) - C_k\bigr)^2
$$
我们先单独关注属于簇 $k$ 的部分：
$$
E_k(\mathbf{U}, C_k)
= \sum_{x \in \Omega} U_k(x)\bigl(f(x) - C_k\bigr)^2
$$
在更新 $C_k$ 时，$U_k(x)$ 固定，只需对 $C_k$ 进行最优化。
对 $C_k$ 求偏导
令
$$
E_k(\mathbf{U}, C_k)
= \sum_{x \in \Omega} U_k(x)\bigl(f(x) - C_k\bigr)^2
$$
对 $C_k$ 求导并令其为 0：
$$
\frac{\partial}{\partial C_k} E_k(\mathbf{U}, C_k)
= \sum_{x \in \Omega} 2 U_k(x) \bigl(C_k - f(x)\bigr).
$$
令其为 0，可得：
$$
\sum_{x \in \Omega} U_k(x)\bigl(C_k - f(x)\bigr) = 0
$$
解方程，得到更新公式
整理可得：
$$
C_k \sum_{x \in \Omega} U_k(x)
= \sum_{x \in \Omega} U_k(x)f(x)
$$
若分母不为 0（该簇有样本），则
$$
C_k = \frac{\sum\limits_{x \in \Omega} U_k(x) f(x)}{\sum\limits_{x \in \Omega} U_k(x)}
$$
这就是 K-Means 中聚类中心的更新公式。在常见的离散数据立场下，上式意味着“该簇内所有样本特征的加权平均值”，权值由 $U_k(x)$ 决定。
若 $U_k(x)$ 只取 0 或 1（硬划分），则退化为简单的算术平均。
注：
在连续情况下，将“求和”换为对 $\Omega$ 的积分即可：
$$C_k = \frac{\int_{\Omega} U_k(x)f(x)\mathrm{d}x}{\int_{\Omega} U_k(x)\mathrm{d}x}$$
当 $U_k(x)$ 只取 0 或 1，即标准 K-Means，公式变为簇内样本的算术平均。
K-Means 能量单调下降（不增）性
以下笔记基于课堂板书，展示 K-Means 迭代过程中目标函数（也称“能量”或“误差”）如何在每一步都单调下降（或不增），从而收敛到局部最优解。
引理 / 定理描述
定理：
由 K-Means 算法产生的迭代序列 $(\mathbf{u}^{(t)}, \mathbf{c}^{(t)})$ 满足$$
E\bigl(\mathbf{u}^{(t+1)}, \mathbf{c}^{(t+1)}\bigr)
\le
E\bigl(\mathbf{u}^{(t)}, \mathbf{c}^{(t)}\bigr),
$$即每次迭代更新后，目标函数 $E(\cdot)$ 不会增大，从而保证了算法的单调收敛性。
目标函数回顾
离散情形下的 K-Means 目标函数：
$$
E\bigl(\mathbf{u}, \mathbf{c}\bigr)
= \sum_{k=1}^{K} \sum_{x \in \Omega}
U_k(x)\bigl(f(x) - C_k\bigr)^2
$$
迭代过程（两步更新）
Step 1：更新 $\mathbf{u}^{(t+1)}$
固定 $\mathbf{c}^{(t)}$，令$$
\mathbf{u}^{(t+1)}
= \arg\min_{\mathbf{u} \in \mathcal{U}}
E\bigl(\mathbf{u}, \mathbf{c}^{(t)}\bigr)
$$由于独热编码的性质，每个样本 $x$ 归于距离最近的中心 $C_k^{(t)}$。
这样得到$$
E\bigl(\mathbf{u}^{(t+1)}, \mathbf{c}^{(t)}\bigr)
\le
E\bigl(\mathbf{u}^{(t)}, \mathbf{c}^{(t)}\bigr)
$$Step 2：更新 $\mathbf{c}^{(t+1)}$
固定 $\mathbf{u}^{(t+1)}$，令$$
\mathbf{c}^{(t+1)}
= \arg\min_{\mathbf{c}}
E\bigl(\mathbf{u}^{(t+1)}, \mathbf{c}\bigr).
$$对每个 $C_k$ 求导并令其为 0，得到聚类中心是该簇内样本的加权平均。于是
$$
E\bigl(\mathbf{u}^{(t+1)}, \mathbf{c}^{(t+1)}\bigr)
\le
E\bigl(\mathbf{u}^{(t+1)}, \mathbf{c}^{(t)}\bigr)
$$
能量严格下降的证明思路
上两步结合，可得：
$$
E\bigl(\mathbf{u}^{(t+1)}, \mathbf{c}^{(t+1)}\bigr)
\le
E\bigl(\mathbf{u}^{(t)}, \mathbf{c}^{(t)}\bigr)
$$
这说明每一轮迭代后，目标函数都会朝着不增的方向变化，从而收敛到某个局部最优或鞍点。
结论
- K-Means 通过交替最小化簇分配 $\mathbf{u}$ 和聚类中心 $\mathbf{c}$，使目标函数在每次迭代中不增。
- 因此，算法单调地收敛到一个局部最优解（或鞍点）。
这便是 K-Means 能量单调下降 的主要证明思路，也是该算法能保证在有限步内收敛的关键原因。