Spectrally Tuned Bandwidth Selection for Kernel Fuzzy Relational Clustering

技术摘要：用于核模糊关系聚类的谱调谐带宽选择

问题陈述
模糊关系聚类（Fuzzy Relational Clustering, FRC）旨在通过部分隶属度识别关系数据（成对差异性）中的重叠几何聚类结构。然而，经典的 FRC 方法面临两个关键局限性：

1. 变量重要性等同的假设： 传统方法通常将所有变量或维度视为同等重要，无法适应那些由特定特征定义聚类的特定数据结构。
2. 对模糊化参数 ($m$) 的敏感性： 模糊程度由参数 $m$ 控制。启发式选择 $m$（通常为 $1.5 \le m \le 3$）往往会导致“均匀解”问题，即算法发生坍缩，将所有对象的隶属概率均等分配给所有聚类（即 $1/c$）。这种被称为“均匀坍缩”（uniform collapse）的现象使得聚类结果失去信息量。虽然 Yu 等人的先前理论工作建立了避免对象类 FCM 中坍缩的 $m$ 的界限，但这些结果并未扩展到使用希尔伯特空间中核诱导距离的关系数据。

方法论
作者提出了核模糊关系聚类（Kernel Fuzzy Relational Clustering, KFRC），这是一个整合了核函数来定义差异性，并采用一种新型两阶段带宽选择算法的框架。

• 核模糊关系聚类 (KFRC)：
  该方法在再生核希尔伯特空间（RKHS）中使用核诱导的平方欧几里得距离来构建 FRC。通过使用对称正定（PSD）核，该关系目标在数学上等价于基于对象的目标，从而实现了对数据几何嵌入的显式控制。

• 稳定性分析与理论界限：
  论文对均匀解 $(U^*, V^*)$ 进行了形式化的稳定性分析。

  • 它证明了均匀解始终是 FRC 算法的一个不动点。
  • 它推导出了均匀解失去稳定性（变为鞍点）的充分必要条件。该条件取决于限制在全 1 向量正交补空间上的矩阵 $Q$ 的最小特征值，而 $Q$ 是模糊化函数 $t_m$ 和核格拉姆矩阵（Gram matrix）谱属性的函数。
  • 具体而言，当 $\kappa(t_m, c)\lambda_{\max}(F) > 1$ 时，均匀解变得不稳定，其中 $F$ 是归一化且双中心化的核矩阵，$\kappa$ 是关于模糊化函数导数的函数。

• 新型模糊化函数：
  基于稳定性分析，作者发现标准幂函数（$t_m(u)=u^m$）和指数型模糊化函数施加了一个严格的几何要求：主特征值必须解释至少 50% 的方差（对于 $c > 2$ 的情况）。为了解决这一问题，作者提出了互补根号模糊化函数：
  $$t_{cr}(u) = 1 - (1 - u)^{1/m}$$
  该函数满足标准的模糊化性质（边界保护、单调性和凸性）以及原点稀疏性，但至关重要的是，其稳定性阈值随着聚类数 $c$ 的增加而渐近趋于零。这防止了人工维度的主导地位，并允许在较大的 $m$ 值下进行有意义的聚类。

• 两阶段带宽选择算法：
  为了防止均匀坍缩并优化聚类结构，作者提出了一个两阶段梯度上升程序来选择核带宽 ($\theta$)：

  1. 第一阶段（可行性）： 在各向异性约束（$\max \theta_j / \min \theta_j \le \alpha$）下最大化归一化核矩阵的领先特征值 $\lambda_1(F)$。其目标是找到使 $\lambda_1(F)$ 超过理论稳定性阈值 $\tau = \lim_{m \to m_{max}} 1/\kappa(t_m, 1/c)$ 的带宽。这确保了均匀解是不稳定的。
  2. 第二阶段（精细化）： 从可行候选解出发，最大化多聚类准则 $Q$（例如，前 $c-1$ 个特征值的和、对数和或特征间隙/eigengap）。这一步旨在防止数据坍缩到单一维度（如果仅最大化 $\lambda_1$ 则会发生这种情况），并促进沿多个聚类相关方向的分离。

核心贡献

1. 理论扩展： 将模糊化参数的稳定性分析从基于对象的 FCM 推广到希尔伯特空间中的关系聚类，为避免均匀坍缩提供了精确的理论界限。
2. 新型模糊化函数： 引入了互补根号模糊化函数，与幂函数相比，它提供了更宽松的稳定性准则，对于 $c > 2$ 的数据集特别有利。
3. 谱带宽选择： 开发了一种两阶段算法，能够自动调节核带宽，以确保聚类解的稳定性，同时优化多聚类分离度。这隐含地执行了无监督核度量学习。
4. 实证验证： 证明了所提框架在合成数据和真实世界数据中能一致地恢复复杂结构，而在这些场景下传统方法往往会失效或坍缩为均匀解。

结果
实验在 192 个合成数据集（改变信噪比、聚类重叠度和聚类数量）和 6 个公开基准数据集上进行。

• 聚类恢复： KFRC（尤其是使用二次或互补根号模糊化函数时）在调整兰德指数（ARI）和调整互信息（AMI）方面优于竞争对手（FRC, FANNY, FCM-MK, MS-FCM, vFCM），尤其是在低信噪比（SNR）场景和 $c \ge 4$ 的情况下。
• 避免均匀坍缩： 竞争方法经常表现出较高的均匀度得分（接近 1.0），表明发生了向均匀解的坍缩。KFRC 保持了中间水平的均匀度得分（$U \in [0.1, 0.8]$），证实了其保留了纯粹的模糊解。
• 变量选择： 带宽选择程序成功识别了信息特征。“对数和”多聚类准则在处理高维且具有多聚类的数据时表现最佳，而“特征间隙（eigengap）”在聚类较少时最为理想。
• 各向异性： 结果表明，允许一定的各向异性（$\alpha > 1$）是有益的，特别是在聚类数量较多或 SNR 较低时，因为这允许算法平滑掉无信息特征。

意义与主张
本文声称 KFRC 提供了一个稳健的模糊关系聚类框架，克服了启发式参数选择的局限性。通过将算法的稳定性直接与核矩阵的谱属性联系起来，作者为避免均匀解提供了理论保证。所提出的带宽选择算法允许使用任意大的模糊化值而不必担心坍缩，从而能够发现传统方法无法解决的复杂重叠聚类结构。这项工作被认为是使模糊关系聚类更加可靠且具有理论依据的重要一步，特别是对于那些聚类结构存在于特征空间子空间中的数据。