Soft k-means

在 k-means 聚类中，每一个数据点隶属于一个类，这是一种 hard 的模式。与之相对的，soft clustering 不把一个数据点硬分给一类，而是给出它属于各个类的“置信度”，表示它属于各个类的程度。在有些场景下，我们也许更希望使用 soft 模式。本文试从两种角度推导 soft 版本的 k-means 算法。

角度 1：Hard k-means → Soft k-means

在之前的文章 K-means及其推广中，我们知道 k-means 是用迭代的方式优化下述目标： \[ \quad\sum_{l=1}^k\sum_{C(i)=l}\|x_i-m_l\|^2 \]

其中 \(C\) 表示划分，\(C(i)=l\) 表示样本 \(x_i\) 被划分到类 \(l\) 中。定义指示变量： \[ \gamma_{il}=\begin{cases}1,&\text{if }C(i)=l\\0,&\text{otherwise}\end{cases} \] 那么优化目标可以改写为： \[ \quad\sum_{l=1}^k\sum_{i=1}^n\gamma_{il}\|x_i-m_l\|^2\tag{1}\label{target} \] k-means 硬就硬在 \(\gamma_{il}\) 是一个 0/1 变量。\(\gamma_{il}=1\) 表示样本 \(x_i\) 被划分给了类 \(l\)，这意味着在 \(x_i\) 到所有聚类中心的距离里面，它到 \(m_l\) 最近，写作数学语言即： \[ l=\arg\min_{j}\|x_i-m_j\|^2 \] 进而 \(\gamma_{il}\) 可以写作： \[ \gamma_{il}=\text{onehot}(\arg\min_j \|x_i-m_j\|^2)_l=\text{onehot}(\arg\max_j (-\|x_i-m_j\|^2))_l \] 根据各种函数的hard与soft形式一文，\(\text{onehot}(\arg\max)\) 的平滑近似是 \(\text{softmax}\)，所以： \[ \gamma_{il}\approx\hat\gamma_{il}=\text{softmax}\left(-\|x_i-m_j\|^2;\tau\right)_l=\frac{e^{-\|x_i-m_l\|^2/\tau}}{\sum_{j=1}^ke^{-\|x_i-m_j\|^2/\tau}} \] 并且 \(\hat\gamma_{il}\) 可以解释为 \(x_i\) 属于第 \(l\) 类的概率。将其代回 \(\eqref{target}\) 式就得到 soft 版本的优化目标： \[ \quad\sum_{l=1}^k\sum_{i=1}^n\hat\gamma_{il}\|x_i-m_l\|^2\tag{2}\label{target-soft} \] 和 hard k-means 一样，我们用迭代的方式来优化 \(\eqref{target-soft}\) 式：

1. 随机选择 \(k\) 个样本作为中心 \((m_1,\ldots,m_k)\).

2. 对给定的中心，计算样本属于各类的概率 \(\hat\gamma_{il}\)： \[ \hat\gamma_{il}=\frac{e^{-\|x_i-m_l\|^2/\tau}}{\sum_{j=1}^ke^{-\|x_i-m_j\|^2/\tau}}\tag{3}\label{estep} \]

3. 固定 \(\hat\gamma_{il}\)，求各类最优中心，即： \[ \min_{m_1,\ldots,m_k}\quad\sum_{l=1}^k\sum_{i=1}^n\hat\gamma_{il}\|x_i-m_l\|^2 \] 求偏导并令为零，容易解得： \[ m_l=\frac{\sum_{i=1}^n\hat\gamma_{il}x_i}{\sum_{j=1}^n\hat\gamma_{jl}}\tag{4}\label{mstep} \] 即对 \(x_i\) 计算加权平均（weighted means）。

4. 迭代执行 2、3 步直至收敛。

角度 2：GMM → soft k-means

熟悉 GMM 的朋友可能已经发现了，soft k-means 和 GMM 的形式非常相似。我们先回顾一下 GMM 的优化步骤（详见EM 算法）：

1. 随机初始化模型参数 \(\alpha_k,\mu_k,\Sigma_k,\,k=1,\ldots,K\)

2. E-step：计算隐变量的概率分布： \[ p_{ik}=\frac{\alpha_k^{(t)}\phi(x_i;\mu_k^{(t)},\Sigma_k^{(t)})}{\sum_{j=1}^K\alpha_j^{(t)}\phi(x_i;\mu_j^{(t)},\Sigma_j^{(t)})} \] 其中 \(\phi(x;\mu,\Sigma)\) 是高斯分布的 pdf： \[ \phi(x;\mu,\Sigma)=\frac{1}{ {(\sqrt{2\pi})}^d|\Sigma|^{1/2} }\exp\left(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)\right) \]

3. M-step：计算新参数： \[ \begin{align} &\alpha_k^{(t+1)}=\frac{\sum_{i=1}^np_{ik}}{n}&& k=1,\ldots,K\\ &\mu_k^{(t+1)}=\frac{\sum_{i=1}^np_{ik}x_i}{\sum_{i=1}^n p_{ik}}&& k=1,\ldots,K\\ &\Sigma_k^{(t+1)}=\frac{\sum_{i=1}^np_{ik}(x_i-\mu_k)^T(x_i-\mu_k)}{\sum_{i=1}^np_{ik}}&& k=1,\ldots,K \end{align} \]

4. 迭代执行第 2、3 步。

如果我们取： \[ \begin{align} &\alpha_k=1/K,&k=1,\ldots,K\\ &\Sigma_k=I,&k=1,\ldots,K \end{align} \] 那么 E-step 将简化为： \[ p_{ik}=\frac{e^{-(x_i-\mu_k)^T(x_i-\mu_k)/2}}{\sum_{j=1}^Ke^{-(x_i-\mu_j)^T(x_i-\mu_j)/2}} \] 这不就是 \(\tau=2\) 的 \(\eqref{estep}\) 式嘛！如果 \(\tau\) 是其他数也没关系，给协方差矩阵乘一个倍数即可。

M-step 中只需要更新 \(\mu\)： \[ \mu_k^{(t+1)}=\frac{\sum_{i=1}^np_{ik}x_i}{\sum_{i=1}^np_{ik}} \] 与 \(\eqref{mstep}\) 式完全一致！所以，soft k-means 是 GMM 在各高斯分布选择概率相同且协方差矩阵为单位矩阵（或单位矩阵的倍数）下的特殊情况。

现在，让我们回头看看 hard k-means。要从 soft 变回 hard，只需要让 \(\text{softmax}\) 里的温度系数 \(\tau\) 趋近于 \(0\)。对应到 GMM 中，相当于让协方差矩阵 \(\Sigma\) 趋近于 \(0\)，即高斯分布趋近 Dirac delta 函数（分布）。因此，k-means 是 GMM 在各高斯分布趋近 Dirac delta 函数且选择概率相同下的特殊情况。

References

1. Bauckhage, Christian. Lecture notes on data science: Soft k-means clustering. Technical Report, Univ. Bonn, DOI: https://doi.org/10.13140/RG. 2.1. 3582.6643, 2015. ↩︎
2. Hart, Peter E., David G. Stork, and Richard O. Duda. Pattern classification. Hoboken: Wiley, 2000. ↩︎
3. Bishop, Christopher M., and Nasser M. Nasrabadi. Pattern recognition and machine learning. Vol. 4, no. 4. New York: springer, 2006. ↩︎