TFS-2018《On the convergence of the sparse possibilistic c-means algorithm》

核心思想

论文的核心思想是为 Sparse Possibilistic C-Means (SPCM) 算法建立严格的数学收敛性保证。SPCM 是对经典 Possibilistic C-Means (PCM2) 算法的扩展，其核心创新在于引入了 $l_p$-范数 ($0<p<1$) 稀疏性约束。

• Possibilistic Clustering (PCM) 的动机：与 Fuzzy C-Means (FCM) 不同，PCM 允许一个数据点可以不属于任何簇，或者仅属于与其高度兼容的少数几个簇。这使得 PCM 对噪声和离群点更具鲁棒性，但经典 PCM 容易产生“重合簇”（coincident clusters），即多个簇中心收敛到同一高密度区域。
• SPCM 的动机：为了解决 PCM 的“重合簇”问题并进一步增强对噪声的鲁棒性，SPCM 强制要求每个数据点 $x_i$ 的隶属度向量 $u_i=[u_{i1},...,u_{im}]$ 是稀疏的。这意味着一个数据点只会对距离其最近的少数几个（甚至零个）簇中心的更新做出贡献，从而迫使算法发现数据中真正稀疏分布的、分离的簇结构。

论文的主要理论贡献是证明了 SPCM 算法的迭代序列会收敛到其代价函数的一个局部最小值，而非仅仅是驻点或鞍点。此外，通过将 PCM2 视为 SPCM 在稀疏参数 $\lambda =0$ 时的特例，论文也得出了比以往工作更强的关于 PCM2 收敛性的结论。

目标函数

SPCM 的目标函数 $J_{SPCM}$ 是在 PCM2 的目标函数基础上，增加了一个 $l_p$-范数稀疏性惩罚项：

$$J_{SPCM}(U,\Theta )=\sum _{i=1}^N\sum _{j=1}^m{u}_{ij}\Vert x_i-{\theta }_j{\Vert }^2+\sum _{j=1}^m{\gamma }_j\sum _{i=1}^N(u_{ij}\ln u_{ij}-u_{ij})+\lambda \sum _{i=1}^N\Vert u_i{\Vert }_p^p$$

其中：

• $x_i\in {\mathbb{R}}^l$ 是第 $i$ 个数据点，共 $N$ 个点。
• ${\theta }_j\in {\mathbb{R}}^l$ 是第 $j$ 个簇的中心（代表），共 $m$ 个簇。
• $u_{ij}\in [0,1]$ 是数据点 $x_i$ 对簇中心 ${\theta }_j$ 的可能性隶属度（possibilistic membership），表示其兼容程度。$U=[u_{ij}]$ 是 $N\times m$ 的隶属度矩阵。
• ${\gamma }_j>0$ 是与第 $j$ 个簇相关的参数，控制着该簇的影响范围。${\gamma }_j$ 越小，簇的影响范围越小。
• $\lambda \ge 0$ 是稀疏性正则化参数，控制着施加稀疏性的强度。
• $\Vert u_i{\Vert }_p^p={\sum }_{j=1}^m{u}_{ij}^p$ 是向量 $u_i$ 的 $l_p$-范数的 $p$ 次方。当 $0<p<1$ 时，该项能有效诱导稀疏性。
• 项 $u_{ij}\ln u_{ij}$ 在 $u_{ij}=0$ 时定义为 ${\lim }_{u_{ij}\to 0^{+}}{u}_{ij}\ln u_{ij}=0$。

各项含义：

1. 第一项 ${\sum }_{i,j}{u}_{ij}\Vert x_i-{\theta }_j{\Vert }^2$：是数据点到其所属簇中心的加权平方误差，旨在拉近高隶属度点与其簇中心的距离。
2. 第二项 ${\sum }_j{\gamma }_j{\sum }_i(u_{ij}\ln u_{ij}-u_{ij})$：是 PCM2 的正则项，它鼓励隶属度 $u_{ij}$ 取 0 或 1 的极端值，从而避免 FCM 中的“概率归一化”约束，使每个簇可以独立存在。
3. 第三项 $\lambda {\sum }_i\Vert u_i{\Vert }_p^p$：是本文引入的稀疏性诱导项。由于 $0<p<1$，该函数在 $u_{ij}=0$ 处不可微且具有“凹”性，能有效迫使许多 $u_{ij}$ 精确为 0，实现行稀疏（row-sparsity）。

当 $\lambda =0$ 时，$J_{SPCM}$ 退化为经典的 PCM2 目标函数 $J_{PCM2}$。

目标函数详细的优化过程

SPCM 采用交替优化（Alternating Optimization, AO）策略，轮流更新隶属度矩阵 $U$ 和簇中心 $\Theta$。

1. 更新簇中心 ${\theta }_j$

固定 $U$，对 $J_{SPCM}$ 关于 ${\theta }_j$ 求偏导并令其为零：

$$\frac{\partial J_{SPCM}}{\partial {\theta }_j}=2\sum _{i=1}^N{u}_{ij}({\theta }_j-x_i)=0$$

解得：

$${\theta }_j=\frac{{\sum }_{i=1}^N{u}_{ij}{x}_i}{{\sum }_{i=1}^N{u}_{ij}}$$

这个更新公式与 FCM 和 PCM 中的公式形式相同，是数据点的加权平均，权重即为隶属度 $u_{ij}$。

2. 更新隶属度 $u_{ij}$

固定 $\Theta$，更新 $u_{ij}$ 是 SPCM 最具挑战性和创新性的部分。目标函数中与 $u_{ij}$ 相关的部分为：

$$h(u_{ij};{\theta }_j)=u_{ij}\Vert x_i-{\theta }_j{\Vert }^2+{\gamma }_j(u_{ij}\ln u_{ij}-u_{ij})+\lambda u_{ij}^p$$

令 $d_{ij}=\Vert x_i-{\theta }_j{\Vert }^2$，则对 $u_{ij}$ 求导：

$$f(u_{ij})=\frac{\partial h}{\partial u_{ij}}=d_{ij}+{\gamma }_j\ln u_{ij}+\lambda p{u}_{ij}^{p-1}$$

论文[16]中已证明 $f(u_{ij})$ 在 $(0,1)$ 区间内有唯一最小值点 ${\hat{u}}_{ij}={\left[\frac{\lambda p(1-p)}{{\gamma }_j}\right]}^{\frac{1}{1-p}}$，且方程 $f(u_{ij})=0$ 最多有两个解。

SPCM 的关键在于，$u_{ij}$ 的最优解 $u_{ij}^{\ast }$ 并非直接由 $f(u_{ij})=0$ 的解给出，而是需要比较目标函数值。论文推导出一个几何解释：存在一个以数据点 $x_i$ 为中心、半径为 $R_j$ 的超球体 $C_{ij}$：

$$R_j^2=\frac{{\gamma }_j}{1-p}\left(-\ln \frac{\lambda (1-p)}{{\gamma }_j}-p\right)$$

• 如果簇中心 ${\theta }_j$ 位于 $C_{ij}$ 的内部或边界（即 $\Vert x_i-{\theta }_j{\Vert }^2\le R_j^2$），则 $u_{ij}^{\ast }$ 取 $f(u_{ij})=0$ 的较大的那个正解 uij{2}u_{ij}^{\{2\}}uij{2}​。
• 如果簇中心 ${\theta }_j$ 位于 $C_{ij}$ 的外部（即 $\Vert x_i-{\theta }_j{\Vert }^2>R_j^2$），则最优解为 $u_{ij}^{\ast }=0$。

因此，更新公式可简洁地表示为：

uij∗={uij{2},if ∥xi−θj∥2≤Rj20,otherwise u_{ij}^* = \begin{cases} u_{ij}^{\{2\}}, & \text{if } \|x_i - \theta_j\|^2 \leq R_j^2 \\ 0, & \text{otherwise} \end{cases} uij∗​={uij{2}​,0,​if ∥xi​−θj​∥2≤Rj2​otherwise​

其中，uij{2}u_{ij}^{\{2\}}uij{2}​ 是通过在区间 $({\hat{u}}_{ij},1]$ 上使用二分法（Bisection Method）求解 $f(u_{ij})=0$ 得到的较大根。

收敛性证明的核心难点：由于 $u_{ij}$ 的更新规则是一个分段函数（且在 $\Vert x_i-{\theta }_j{\Vert }^2=R_j^2$ 处不连续），整个优化算子 $T$ 在全局上不是连续的。论文的精妙之处在于，它没有试图证明全局连续性，而是将整个参数空间划分为多个“有效活动集”（valid active set）对应的区域。在每个这样的局部区域（即簇中心 ${\theta }_j$ 位于一组特定数据点对应的超球体交集内），算子 $T$ 是连续的，并且目标函数 $J$ 是严格单调递减的。通过应用 Meyer 定理（Theorem 1），论文最终证明了算法在每个局部区域内都会收敛到一个严格的局部最小值。

主要的贡献点

1. 首次为 SPCM 提供收敛性证明：这是本文最核心的贡献。它严格证明了 SPCM 算法的迭代序列会收敛到其代价函数 $J_{SPCM}$ 的一个局部最小值，这为算法的可靠性和理论基础提供了坚实保障。
2. 改进了 PCM2 的收敛性结论：通过将 PCM2 视为 SPCM 在 $\lambda =0$ 时的特例，论文证明了 PCM2 也会收敛到其代价函数 $J_{PCM2}$ 的一个局部最小值。这比 Zhou 等人在 [11] 中利用 Zangwill 定理得出的“收敛到局部最小值或鞍点”的结论要强得多。
3. 深入的理论分析：论文对算法行为进行了深刻的理论剖析，特别是通过引入“活动集”（active set）和“超球体”（hypersphere）的概念，清晰地解释了稀疏性约束如何在几何上影响隶属度的更新和簇中心的移动。
4. 参数选择指导：论文在附录和 III-A 小节中，对关键参数 $K$（用于计算 $\lambda$）的取值范围给出了理论指导（如 $K<p{e}^{2(1-p)}$），以确保算法在初始化和迭代过程中满足基本假设（如每个簇至少有一个活动点）。

算法的实现过程

SPCM 算法的实现过程如下（以单个簇 $j$ 为例，实际需对所有 $m$ 个簇并行操作）：

算法：SPCM($X,m$)

输入：数据集 X={x1,...,xN}X = \{x_1, ..., x_N\}X={x1​,...,xN​}，簇数 $m$。
输出：簇中心 Θ={θ1,...,θm}\Theta = \{\theta_1, ..., \theta_m\}Θ={θ1​,...,θm​}，参数 Γ={γ1,...,γm}\Gamma = \{\gamma_1, ..., \gamma_m\}Γ={γ1​,...,γm​}，隶属度矩阵 $U$。

1. 初始化 ($t=0$)：

   • 初始化 ${\theta }_j$：运行标准的 FCM 算法，得到 $m$ 个初始簇中心 ${\theta }_j^{(0)}$。
   • 初始化 ${\gamma }_j$：利用 FCM 的最终结果计算：
     $${\gamma }_j=\frac{{\sum }_{i=1}^N{u}_{ij}^{FCM}\Vert x_i-{\theta }_j^{(0)}{\Vert }^2}{{\sum }_{i=1}^N{u}_{ij}^{FCM}}$$
   • 计算 $\lambda$：
     $$\lambda =K\frac{\bar{\gamma }}{p(1-p)e^{2-p}},\text{其中}\bar{\gamma }=\underset{j=1,...,m}{\min }{\gamma }_j$$
     通常取 $K=0.9$ (当 $p=0.5$ 时)。

2. 重复以下步骤直到收敛：

   • 更新隶属度 $U^{(t)}$：
     对每个数据点 $i$ 和每个簇 $j$：
     1. 计算距离 $d_{ij}=\Vert x_i-{\theta }_j^{(t)}{\Vert }^2$。
     2. 计算临界半径 $R_j^2$ (公式见上文)。
     3. 如果 $d_{ij}>R_j^2$，则设 $u_{ij}^{(t)}=0$。
     4. 如果 $d_{ij}\le R_j^2$：
        • 计算 $f(u_{ij})$ 的最小值点 ${\hat{u}}_{ij}$。
        • 使用二分法在区间 $({\hat{u}}_{ij},1]$ 内求解方程 $f(u_{ij})=0$，得到较大的根 uij{2}u_{ij}^{\{2\}}uij{2}​。
        • 设 uij(t)=uij{2}u_{ij}^{(t)} = u_{ij}^{\{2\}}uij(t)​=uij{2}​。
   • 更新簇中心 ${\Theta }^{(t+1)}$：
     对每个簇 $j$：
     $${\theta }_j^{(t+1)}=\frac{{\sum }_{i=1}^N{u}_{ij}^{(t)}{x}_i}{{\sum }_{i=1}^N{u}_{ij}^{(t)}}$$
   • 迭代计数：$t=t+1$。
   • 检查收敛：如果所有 ${\theta }_j$ 在连续两次迭代中的变化小于预设阈值，则停止。

3. 后处理：算法终止后，通常需要一个额外的步骤来识别并移除可能产生的重复簇（即位置非常接近的簇中心）。

计算复杂度：算法的主要计算开销在于更新隶属度 $U$，特别是当需要使用二分法求解 uij{2}u_{ij}^{\{2\}}uij{2}​ 时。然而，在实践中，由于稀疏性约束，大部分 $u_{ij}$ 会被直接设为 0，只有少数点需要进行二分法计算，因此实际复杂度仅比 PCM 略高。