DK-GBMKKM: 动态核空间粒球多核$k$-均值聚类

# 动态核空间粒球多重核k-均值聚类
来源：https://arxiv.org/html/2609.00647
## DK‑GBMKKM：动态核空间粒球多重核k-均值聚类
致谢：X. Lian, Y. Zhang, S. Xia, S. Zhong & X. Xiang 隶属于重庆邮电大学计算智能重庆高校市级重点实验室、网络空间大数据智能安全教育部重点实验室、数字经济智能川渝共建重点实验室以及大数据智能计算重点实验室，邮编400065，中国重庆。

第一作者 连晓宇  
单位：重庆邮电大学 重庆，中国，电子邮箱：[email protected]  
第二作者 张宇超  
单位：重庆邮电大学/重庆开放大学 重庆，中国，电子邮箱：[email protected]  
第三作者 夏书银（通讯作者）  
单位：重庆邮电大学 重庆，中国，电子邮箱：[email protected]  
第四作者 钟思琪  
单位：重庆邮电大学 重庆，中国，电子邮箱：[email protected]  
第五作者 向兆旭  
单位：重庆邮电大学 重庆，中国，电子邮箱：[email protected]

###### 摘要

多重核k-均值通过学习基础核的线性组合来整合互补的非线性相似性。然而，其基于逐样本的优化方法对噪声和边界样本敏感，并需反复操作样本规模的核矩阵。粒球表示法将局部样本组组织为介观单元，但在输入空间中一次生成的粒球可能与多重核学习过程中演化的融合核几何结构不一致。本文提出了动态核空间粒球多重核k-均值（DK-GBMKKM）。该方法在当前融合核空间中生成粒球，并交替进行核权重学习与粒球隶属度更新，使表示能够适应融合核几何结构的变化。进一步构建了样本大小加权的粒球核，以保留不同大小粒球的贡献，并建立了其半正定性及相关等价性质。在12个公共数据集上的实验证明了DK-GBMKKM具有强大的整体聚类性能。代码已开源以供复现：https://github.com/lianxiaoyu724/DK-GBMKKM。

###### 关键词：

多重核聚类，多重核k-均值，粒球计算，核空间，粒球。

## I 引言

经典的k-均值聚类因其简单性、计算效率和易于实现而被广泛应用于图像分析、文本挖掘、生物信息学和多媒体处理[1 (https://arxiv.org/html/2609.00647#bib.bib1), 2 (https://arxiv.org/html/2609.00647#bib.bib3), 3 (https://arxiv.org/html/2609.00647#bib.bib2)]。为了克服欧几里得距离在输入空间中的局限性，谱聚类构建了样本相似图，将聚类问题重新表述为图划分问题，并从图拉普拉斯矩阵的特征向量中导出低维嵌入[4 (https://arxiv.org/html/2609.00647#bib.bib4), 5 (https://arxiv.org/html/2609.00647#bib.bib5), 6 (https://arxiv.org/html/2609.00647#bib.bib6)]。而核k-均值则将样本隐式地映射到再生核希尔伯特空间（RKHS）并在该空间中进行聚类，从而改善了对非线性结构的表示能力[7 (https://arxiv.org/html/2609.00647#bib.bib7), 8 (https://arxiv.org/html/2609.00647#bib.bib8)]。

尽管核聚类能够捕获非线性结构，但单个核的表达能力是有限的。多重核聚类通过结合多个基础核来学习适应特定任务的相似性度量[9 (https://arxiv.org/html/2609.00647#bib.bib10), 10 (https://arxiv.org/html/2609.00647#bib.bib11)]。多重核k-均值（MKKM）是一个代表性框架，它联合优化核权重和聚类分配[11 (https://arxiv.org/html/2609.00647#bib.bib9)]，后续的扩展工作改进了其鲁棒性、结构建模能力和可扩展性[12 (https://arxiv.org/html/2609.00647#bib.bib12), 13 (https://arxiv.org/html/2609.00647#bib.bib13)]。然而，大多数现有方法仍然是以样本为中心的，这使得它们对噪声、边界样本和离群样本敏感，并且在处理大型核矩阵时计算开销很大。因此，一种稳定且高效的介观表示方法是非常理想的。

粒球计算（GBC）最近作为一种自适应的多粒度表示方法而兴起。GBC并非直接从单个样本中学习，而是用具有中心、半径和样本覆盖范围的粒球来近似任意的数据分布。因此，它用更少且更稳定的介观单元替代了大量的样本[14 (https://arxiv.org/html/2609.00647#bib.bib14), 15 (https://arxiv.org/html/2609.00647#bib.bib15)]。GBC在效率、鲁棒性和可解释性方面具有固有优势，并且已经与分类器、粗糙集、模糊集和图学习相结合，以构建稳定的多粒度学习框架[16 (https://arxiv.org/html/2609.00647#bib.bib16), 17 (https://arxiv.org/html/2609.00647#bib.bib17), 18 (https://arxiv.org/html/2609.00647#bib.bib18), 19 (https://arxiv.org/html/2609.00647#bib.bib19), 20 (https://arxiv.org/html/2609.00647#bib.bib20)]。它也被用于聚类，以降低计算复杂度并提高对噪声的鲁棒性[21 (https://arxiv.org/html/2609.00647#bib.bib38), 22 (https://arxiv.org/html/2609.00647#bib.bib21), 23 (https://arxiv.org/html/2609.00647#bib.bib23), 24 (https://arxiv.org/html/2609.00647#bib.bib29), 25 (https://arxiv.org/html/2609.00647#bib.bib25), 26 (https://arxiv.org/html/2609.00647#bib.bib28), 27 (https://arxiv.org/html/2609.00647#bib.bib24), 28 (https://arxiv.org/html/2609.00647#bib.bib26), 29 (https://arxiv.org/html/2609.00647#bib.bib27)]。因此，将GBC引入多重核聚类是一个自然的发展方向。粒球诱导的多重核k-均值（GB-MKKM）[30 (https://arxiv.org/html/2609.00647#bib.bib22)]首次将粒球嵌入到MKKM中。通过在输入空间中构建粒球并压缩样本集，它提高了效率和鲁棒性，并证明了介观单元在多重核聚类中的可行性。

然而，GB-MKKM及相关方法在输入空间中构建粒球。这种设计隐式地假设在输入空间中接近的样本在核诱导的高维特征空间中仍然接近。这个假设仅对近似保序的映射（如线性核）是合理的。在常用的非线性核（包括高斯核和多项式核）下，邻域关系在映射后可能会发生显著变化。输入空间的粒球边界可能因此无法反映核空间中实际的局部密度和聚类结构。此外，固定的粒球划分无法随着核权重和融合核几何结构的变化而自适应调整。为解决这些局限性，我们提出了动态核空间粒球多重核k-均值（DK-GBMKKM），该方法将粒球的构建与多重核聚类优化的空间对齐。主要贡献如下：

- • 我们提出了一种融合核驱动的动态粒球生成机制，其中粒球在当前的融合核空间中直接构建和更新，同时保持粒球数量固定。
- • 我们开发了一个交替优化框架，在压缩的粒球空间中联合更新粒球结构、谱表示和核权重。
- • 在12个公共数据集上的大量实验表明，根据四个聚类指标的平均性能和总体排名，DK-GBMKKM优于七种代表性方法。

本文并非直接对样本级的核矩阵应用多重核聚类，而是构建了多个粒球核，并对编码了局部结构的介观单元进行聚类。

### II‑A 动机

现有的粒球多重核聚类方法通常在输入空间中构建粒球，然后构建球级核表示。这会导致空间不匹配，因为球结构遵循输入空间几何，而聚类是在融合核空间中优化的。此外，固定的粒球划分无法适应核权重的变化，并可能与演化的融合核几何结构不一致。DK-GBMKKM解决了这两个问题，如图1 (https://arxiv.org/html/2609.00647#S2.F1)所示。它首先根据当前的核权重构建融合核矩阵K_σ，并在诱导的核空间中生成粒球。然后，根据球内和球间核关系计算球级核矩阵，接着进行谱嵌入和球级核权重学习。权重更新后，重建融合核并调整粒球隶属度。因此，表示与多重核模型共同演化。

参考图片说明：图1：DK-GBMKKM框架。
### II‑B 问题描述与基础模型

设 \( \mathcal{X} = \{x_i\}_{i=1}^n \) 是一个包含 \( c \) 个目标簇的数据集。给定 \( P \) 个正定基础核矩阵 \( \{K^{(p)}\}_{p=1}^P \)，每个矩阵都经过对称化、中心化和对角归一化处理，令 \( K^{(p)} \in \mathbb{R}^{n \times n} \)。核权重向量 \( \sigma = [\sigma_1, \ldots, \sigma_P]^\top \) 满足

\[ \left\{ \sigma \mid \sigma_p \geq 0, \sum_{p=1}^P \sigma_p = 1 \right\}. \tag{1} \]
我们使用权重平方的核组合

\[ K_\sigma = \sum_{p=1}^P \sigma_p^2 K^{(p)}. \tag{2} \]

**核空间粒球：** 在当前融合核 \( K_\sigma \) 诱导的 RKHS \( \mathcal{H} \) 中，第 \( \ell \) 个粒球表示为 \( B_\ell = (\mathcal{I}_\ell, C_\ell, R_\ell, \text{CCM}_\ell) \)。这里 \( \mathcal{I}_\ell \) 是球覆盖的样本集合，\( n_\ell = |\mathcal{I}_\ell| \) 是其大小，\( C_\ell \) 和 \( R_\ell \) 是其在核空间中的中心和半径，\( \text{CCM}_\ell \) 是其核空间中心一致性度量。相关推导见附录 B (https://arxiv.org/html/2609.00647#A2)。

核空间中心是球内映射样本的均值：

\[ C_\ell = \frac{1}{n_\ell} \sum_{x_i \in \mathcal{I}_\ell} \phi(x_i), \tag{3} \]
其中 \( \phi(x_i) \) 是 \( x_i \) 到 \( K_\sigma \) 诱导的 RKHS 的隐式映射。对于任意样本 \( x \)，其到 \( C_\ell \) 的平方距离为

\[
d_{\mathcal{H}}^2(x, C_\ell) = \left\| \phi(x) - C_\ell \right\|_{\mathcal{H}}^2 \tag{4}
\]
\[
= K_\sigma(x,x) - \frac{2}{n_\ell} \sum_{x_i \in \mathcal{I}_\ell} K_\sigma(x,x_i) + \frac{1}{n_\ell^2} \sum_{x_i \in \mathcal{I}_\ell} \sum_{x_j \in \mathcal{I}_\ell} K_\sigma(x_i,x_j).
\]

因此，该距离完全由 \( K_\sigma \) 计算得出，无需显式构造中心向量。\( B_\ell \) 的最大半径和平均半径为

\[ R_\ell = \max_{x_i \in \mathcal{I}_\ell} d_{\mathcal{H}}(x_i, C_\ell), \qquad \bar{R}_\ell = \frac{1}{n_\ell} \sum_{x_i \in \mathcal{I}_\ell} d_{\mathcal{H}}(x_i, C_\ell). \tag{5} \]

由于无监督聚类中没有标签纯度信息，我们通过将所有样本距离替换为核空间距离来调整中心一致性度量[22 (https://arxiv.org/html/2609.00647#bib.bib21)]。令 \( \chi_\ell = \{x_i \in \mathcal{I}_\ell \mid d_{\mathcal{H}}(x_i, C_\ell) \leq \bar{R}_\ell\} \) 表示位于平均半径内的样本。核空间的维度通常无法显式获得，因此我们使用半径归一化的密度，从而避免了对维度的直接依赖。单例球或零半径球的一致性设为1。平均半径和最大半径内的密度分别为

\[ \rho_\ell^{\text{ave}} = \frac{|\chi_\ell|}{\bar{R}_\ell}, \qquad \rho_\ell^{\max} = \frac{n_\ell}{R_\ell}. \tag{6} \]
这些比率通过关联覆盖的样本数量与相应的半径来量化紧凑性。核空间中心一致性度量则为

\[ \text{CCM}_\ell = \frac{\min(\rho_\ell^{\text{ave}},\, \rho_\ell^{\max})}{\max(\rho_\ell^{\text{ave}},\, \rho_\ell^{\max})} \in (0,1]. \tag{7} \]
该值接近1表示均匀且稳定的核空间分布，而较小的值则表明该粒球应进行细化。粒球在当前的融合核空间中生成，并将此度量与GBC过程中的核2-均值相结合[22 (https://arxiv.org/html/2609.00647#bib.bib21)]。

**粒球核构建：** 当前的融合核 \( K_\sigma \) 诱导一个所有基础核共享的单一粒球划分。由于 \( K_\sigma \) 是基础核的加权组合，每个融合空间球中心在相应基础核空间中具有一致的分解；见附录 B (https://arxiv.org/html/2609.00647#A2)。因此，只生成一个划分，所有基础核使用相同的索引集 \( \{\mathcal{I}_b\}_{b=1}^M \)。

对于两个粒球 \( B_a \) 和 \( B_b \)，它们在第 \( p \) 个基础核空间中的相似度定义为其中心的内积：

\[
\overline{K}_B^{(p)}(a,b) = \left\langle C_a^{(p)}, C_b^{(p)} \right\rangle = \frac{1}{n_a n_b} \sum_{x_i \in \mathcal{I}_a} \sum_{x_j \in \mathcal{I}_b} K^{(p)}(x_i,x_j). \tag{8}
\]
此核空间内积完全通过样本级核矩阵计算；无需显式形成基础空间中心。

定义样本到粒球的指示矩阵 \( G \) 为

\[ G_{ib} = \begin{cases} 1, & x_i \in B_b, \\ 0, & \text{否则}, \end{cases} \qquad \sum_{b=1}^{M} G_{ib} = 1, \quad i=1,\ldots,n. \tag{9} \]
因此，\( G \in \{0,1\}^{n \times M} \)。定义粒球大小矩阵为

\[ D = G^\top G = \text{diag}(n_1, \ldots, n_M). \tag{10} \]
由式 (8) 可得，基础核 \( p \) 的平均粒球核为

\[ \overline{K}_B^{(p)} = D^{-1} G^\top K^{(p)} G D^{-1}, \tag{11} \]
其第 \( (a,b) \) 项为 \( \langle C_a^{(p)}, C_b^{(p)} \rangle \)。

式 (11) 度量了粒球中心之间的核空间相似性，但忽略了粒球大小，这可能会低估较大粒球的权重。因此，我们按比例缩放……