软聚类

软聚类#

软聚类又称为模糊聚类（fuzzy clustering），是指每个实例赋予每个簇一个分数的聚类。而硬聚类会将每个实例分配给一个单独的簇。

1. 期望最大#

期望最大（Expectation-Maximization，EM）算法与 k-均值算法有很多相似之处：它随机初始化簇参数，首先将实例分配给簇（期望步骤），然后更新簇（最大化步骤），然后重复这两个步骤，直到收敛为止。在聚类的上下文中，您可将 EM 视为 k-均值的概括，它不仅可找到聚类中心（\(μ_i\)），还可找到它们的大小，形状和方向（\(Σ_i\)），以及它们的相对权重（\(ϕ_i\)）。

但，与 k-均值不同，EM 使用软聚类分配。对于每个实例，在期望步骤中，该算法（基于当前的簇参数）估计它属于每个簇的概率。然后，在最大化步骤中，将使用数据集中的所有实例更新每个簇，并通过每个实例属于该簇的估计概率对其进行加权。这些概率称为实例簇的干系（responsibilities）。在最大化步骤中，每个簇的更新将主要受到其最相干的实例的影响。在已经估算了每个簇的位置，大小，形状，方向和相对权重后，该模型可轻松地将每个实例分配给最可能的簇（硬聚类）或估算其属于特定簇的概率（软聚类）。

不幸的是，就像 k-均值一样，EM 最终可能会收敛于较差的解决方案，因此它需要运行几次，仅保留最佳解决方案。当存在多个维度，多个簇或很少实例时，EM 可能难以收敛于最佳解决方案。可能需要通过限制算法必须学习的参数数量来减少任务的难度。一种方法是限制簇可具有的形状和方向的范围。这可通过对协方差矩阵施加约束来实现。

2. GMM#

2.1. 模型推导#

高斯混合模型（Gaussian Mixture Model，GMM）假设实例是由多个参数未知的高斯分布的混合生成的。从单个高斯分布生成的所有实例均形成一个簇，该簇通常看起来像椭圆形。每个簇可具有不同的椭圆形状，大小，密度和方向。

GMM 有多种变体。在实现之前，必须知道高斯分布的数量 k。其简单变体的算法如下：

步骤

  1. 对每个实例，从 k 个簇中随机选择一个簇。选择第\(j\)个簇的概率由簇的权重\(φ(j)\)定义。为第\(i\)个实例选择的簇的索引记为\(z(i)\)。

  2. 若\(z(i) = j\)，意味着第\(i\)个实例已分配给第\(j\)个簇，则从具有均值\(μ(j)\)和协方差矩阵\(Σ(j)\)的高斯分布中随机抽取此实例的位置\(x(i)\)。即：

\[ x_i ∼ 𝒩({μ}_{j}, {Σ}_{j}) \]

  1. \(x(i)\)的值已知，称为观测变量；\(z(i)\)的值未知，称潜在变量；

对于给定数据集\(X\)，通常首先需要估计权重\(ϕ\)和所有分布参数\(μ_i\)和\(Σ_i\)。

GMM 还可在任何给定位置估计模型的密度。而对于给出的每个实例，此方法都会估算该位置处的概率密度函数（PDF）的对数。若计算这些分数的指数，则可在给定实例的位置获得 PDF 的值。这些不是概率，而是概率密度：它们可取任何正值，而不仅仅是 0 到 1 之间的值。要估算实例落入特定区域的概率，必须在该区域上积分 PDF。

2.2. 相关细节#

设 GMM 的参数分别为实例数\(m\)，维度\(n\)，簇数 k。

  • 簇为任意球形或任意椭圆形，运算复杂度为\(O(kmn)\)

  • 簇为统一椭圆形或任意形状，运算复杂度为\(O(kmn^2 + kn^3)\)，此时不能放缩至大规模

实际上，GMM 在具有椭圆形状的聚类上效果很好。

2.3. BGMM#

除了手动搜索最佳数目的簇，还可使用贝叶斯 - 高斯混合模型（Bayesian-Gaussian Mixure Model，BGMM），该算法能够为不必要的簇赋予等于（或接近）零的权重。将簇数量 n_components 设置为一个您有充分理由相信的值，该值大于最佳簇数量，该算法将自动消除不必要的簇。在此模型中，聚类参数（包括权重，均值和协方差矩阵）不再被视为固定模型参数，而是被视为潜在的随机变量。故，此处\(z\)同时包括聚类参数和聚类分配。

\[ p(z ∣ X) = \frac{p(X ∣ z) p(z)}{p(X)} \]
\[ \mathrm{posterior} = \frac{\mathrm{likelihood} × \mathrm{prior}}{\mathrm{evidence}} \]

在 GMM 以及许多其他问题中，分母\(p(x)\)是棘手的，因为它需要对\(z\)的所有可能值进行积分：

\[ p(x) = ∫p(x ∣ z) p(z) d z \]

这种难处理性是贝叶斯统计中的核心问题之一，有几种解决方法。其中之一是变分推断（variational inference），它选择具有其自身的变分参数\(λ\)的分布族\(q(z; λ)\)，然后通过找到使 KL 从\(q(z)\)到\(p(z ∣ X)\)的 KL 散度最小的\(λ\)值优化这些参数，以使\(q(z)\)成为\(p(z ∣ X)\)的良好近似值，记为\(D_{KL}(q ∣ p)\)。

KL 散度方程如下所示，可将其重写为证据的对数，\(\log p(X)\)减去证据下界（evidence lower bound，ELBO）。由于\(\log p(X)\)不依赖于\(q\)，因此它是一个常数项，从而使 KL 散度最小化只需要使 ELBO 最大化：

\[\begin{split} \begin{aligned} D_{K L}(q ∣ p) &= E_q \bigg[\log \frac{q(z)}{p(z | X)} \bigg] \\ &= E_q \bigg[\log q(z) - \log \frac{p(z, X)}{p(X)} \bigg] \\ &= E_q[\log q(z) - \log p(z, X) + \log p(X)] \\ &= E_q[\log p(X)] - E_q[\log p(z, X)] - E_q[\log q(z)] \\ &= \log p(X) - \mathrm{ELBO} \end{aligned} \end{split}\]

在实践中，存在多种使 ELBO 最大化的技术。一种简单方法称为黑盒随机变异性推断（black- box stochastic variational inference，BBSVI）：在每次迭代中，从\(q\)提取一些样本，并将它们用于估计变异性参数\(λ\)的 ELBO 梯度，然后将其用于梯度上升步骤。这种方法使得可将 Bayesian 推断与任何类型的模型（设它是可区分的）甚至是深度神经网络一起使用。