论文状态:已完成

K*-Means: A Parameter-free Clustering Algorithm

发表:2025/05/17
原文链接PDF 下载
价格:0.100000
价格:0.100000
已有 2 人读过
本分析由 AI 生成,可能不完全准确,请以原文为准。

TL;DR 精炼摘要

本文提出了一种新颖的聚类算法k*-means,完全无须用户设置聚类数量或任何其他参数。该算法利用最小描述长度原理,自动确定最优聚类数量k*,并通过聚类的分裂与合并过程优化k-means目标函数。实验表明,k*-means在k未知的情况下优于现有方法,同时具备较强的准确性与良好的扩展性。

摘要

Clustering is a widely used and powerful machine learning technique, but its effectiveness is often limited by the need to specify the number of clusters, k, or by relying on thresholds that implicitly determine k. We introduce k*-means, a novel clustering algorithm that eliminates the need to set k or any other parameters. Instead, it uses the minimum description length principle to automatically determine the optimal number of clusters, k*, by splitting and merging clusters while also optimising the standard k-means objective. We prove that k*-means is guaranteed to converge and demonstrate experimentally that it significantly outperforms existing methods in scenarios where k is unknown. We also show that it is accurate in estimating k, and that empirically its runtime is competitive with existing methods, and scales well with dataset size.

思维导图

论文精读

中文精读

1. 论文基本信息

1.1. 标题

K*-Means: A Parameter-free Clustering Algorithm

1.2. 作者

  • Louis Mahon (University of Edinburgh)
  • Mirella Lapata (University of Edinburgh)

1.3. 发表期刊/会议

论文目前作为预印本 (preprint) 发布在 arXiv 上,尚未经过同行评审或正式发表于特定期刊/会议。

1.4. 发表年份

2025年

1.5. 摘要

聚类 (Clustering) 是一种广泛使用且强大的机器学习技术,但其有效性通常受限于需要指定聚类数量 kk,或者依赖隐式决定 kk 的阈值。本文介绍了 k*-means,这是一种新颖的聚类算法,它无需设置 kk 或任何其他参数。相反,它利用 最小描述长度原理 (Minimum Description Length, MDL) 自动确定最优聚类数量 kk*,通过分裂 (splitting) 和合并 (merging) 聚类,同时优化标准 k-means 目标函数。作者证明了 k*-means 保证收敛,并通过实验表明,在 kk 未知的情况下,它显著优于现有方法。论文还展示了 k*-means 在估计 kk 方面的准确性,并且其实验运行时间与现有方法具有竞争力,并能很好地扩展到大型数据集。

1.6. 原文链接

2. 整体概括

2.1. 研究背景与动机

聚类是机器学习中的一项基础任务,广泛应用于数据可视化、表示学习 (representation learning)、联邦学习 (federated learning)、强化学习 (reinforcement learning) 中的探索、异常检测 (anomaly detection) 以及自然科学等多个领域。它甚至与深度学习的特征提取相结合,形成了深度聚类 (deep clustering) 和深度图聚类 (deep graph clustering) 等方法。聚类能够在缺乏标记数据的情况下,提供有意义且可解释的数据划分。

然而,几乎所有现有的聚类算法都存在一个普遍的局限性:它们需要用户设置参数。对于 基于质心 (centroid-based) 的算法(如 k-means),用户必须指定聚类的数量 kk。对于 基于密度 (density-based) 的算法(如 DBSCAN),则需要设置阈值(如 epsmin-pts)来定义高密度区域和分离区域,这些阈值隐式地决定了聚类的数量。在实际应用中,用户往往对数据的内在聚类结构知之甚少,难以选择合适的参数值,这大大限制了这些算法的适用性和有效性。

这篇论文的动机在于解决这一核心挑战:设计一个完全参数无关 (parameter-free) 的聚类算法,能够自动发现数据的最优聚类数量 kk*,而无需任何用户输入

2.2. 核心贡献/主要发现

k*-means 算法旨在继承 k-means 的优点(速度快、保证收敛、参数易解释、准确度高),同时克服其需要预设 kk 的缺点。论文的核心贡献和主要发现如下:

  • 提出了 k*-means 算法: 引入了一种新颖的聚类算法,该算法是完全参数无关的,即无需设置聚类数量 kk 或任何其他阈值。它通过将 最小描述长度原理 (MDL principle) 整合到 k-means 的框架中,实现了 kk 的自动确定。
  • 基于 MDL 的优化目标: k*-means 优化了一个信息论目标,即最小化数据在模型下的描述长度。这个描述长度被量化为表示聚类质心、每个数据点的聚类标签(索引成本,index cost)以及每个点与其质心之间位移(残差成本,residual cost)所需的比特数。通过平衡这两部分成本,算法能够自动找到一个合理的 kk 值。
  • 收敛性证明: 作者提供了 k*-means 算法在有限时间内保证收敛的正式证明。这继承了标准 k-means 算法的收敛性优势。
  • 实验验证 kk 估计的准确性: 在合成数据上进行实验,证明 k*-means 比现有方法能更准确地推断出真实的聚类数量 kk,在聚类分离度高的情况下,准确性接近完美。
  • 在标准聚类指标上的卓越性能: 在六个跨模态的真实世界标注数据集(图像、文本、音频、视频)上,k*-means 在标准聚类指标(如 ACC、ARI、NMI)上显著优于所有不需要设置 kk 的现有方法,并且在某些数据集上甚至能与已知 kk 值的 k-meansGMM 竞争。
  • 运行时竞争力: k*-means 的经验运行时间与现有方法相比具有竞争力,并且随着数据集规模的增加能很好地扩展,在大型数据集上比一些竞争方法(如 HDBSCAN)更快。

3. 预备知识与相关工作

3.1. 基础概念

3.1.1. 聚类 (Clustering)

聚类是一种无监督学习 (unsupervised learning) 任务,其目标是将数据集中的对象分成若干组(即聚类),使得同一组内的对象之间具有较高的相似度,而不同组之间的对象则具有较低的相似度。聚类算法不需要预先知道数据的类别标签。

3.1.2. k-Means 算法

k-means 算法是最常用和最经典的基于质心 (centroid-based) 的聚类算法之一。

  • 核心思想: 将数据点划分到 kk 个预设的聚类中,使得每个数据点都属于离它最近的聚类中心(质心,centroid),并最小化聚类内部的平方和 (Sum of Squared Errors, SSE)。
  • 算法步骤 (Lloyd's algorithm):
    1. 初始化: 随机选择 kk 个数据点作为初始质心。
    2. 分配 (Assignment): 将每个数据点分配到与其最近的质心所属的聚类。
    3. 更新 (Update): 重新计算每个聚类的质心,即该聚类中所有数据点的平均值。
    4. 迭代: 重复步骤 2 和 3,直到聚类分配不再变化,或者达到最大迭代次数。
  • 局限性: 必须预先指定聚类数量 kk

3.1.3. 最小描述长度原理 (Minimum Description Length, MDL)

最小描述长度原理 (MDL principle) 是信息论 (information theory) 中的一个概念,由 Jorma Rissanen 提出。它是一种模型选择 (model selection) 的原则,旨在从一组候选模型中选择最能描述数据的模型。

  • 核心思想: 最优的数据表示是使用最少比特 (bits) 就能精确指定数据的那种表示。这可以理解为,一个好的模型不仅应该能很好地拟合数据,还应该足够简洁。
  • 描述长度 (Description Length): 通常分为两部分:
    1. 模型描述长度 (Length of the Model): 描述模型本身所需的比特数(模型越复杂,描述长度越长)。
    2. 数据在模型下的描述长度 (Length of the Data given the Model): 使用模型来描述数据所需的比特数(模型对数据的拟合度越好,残差越小,这部分的描述长度越短)。
  • 目标: 最小化总描述长度 = 模型描述长度 + 数据在模型下的描述长度。这有助于避免过拟合 (overfitting)(模型描述长度过长)和欠拟合 (underfitting)(数据在模型下的描述长度过长)。

3.1.4. UMAP

UMAP (Uniform Manifold Approximation and Projection) 是一种非线性降维技术,常用于数据可视化和特征提取。

  • 特点: 能够有效地保留高维数据中的局部和全局结构,并且通常比 t-SNE 等方法计算更快。
  • 应用: 在这篇论文中,UMAP 被用于将高维数据(如图像特征、文本特征)降维到较低维度,以便于聚类分析。

3.1.5. CLIP 和 Llama-3.1

这是两种先进的预训练模型 (pre-trained models),用于从不同模态的数据中提取特征。

  • CLIP (Contrastive Language-Image Pre-training): 由 OpenAI 开发,能够学习图像和文本之间的对应关系,生成跨模态的特征表示。在论文中,它用于从图像和视频中提取特征。
  • Llama-3.1: 由 Meta 开发的大型语言模型 (Large Language Model, LLM)。在论文中,它用于从文本数据(20 NewsGroups)中提取特征。

3.2. 前人工作与技术演进

本节总结了论文中提及的与 k*-means 相关的现有聚类算法,并分析了它们在参数设置方面的挑战。

3.2.1. 基于质心的算法 (Centroid-based Algorithms)

  • k-Means [20, 18]: 如上所述,是最基础的基于质心算法,要求指定 kk
  • 高斯混合模型 (Gaussian Mixture Models, GMMs) [6]: 通过期望最大化 (Expectation-Maximization, EM) 算法拟合多元正态分布,将数据点视为来自不同高斯分布的混合。同样需要指定 kk 和协方差类型 (covariance type) 等参数。

3.2.2. 其他复杂聚类算法

  • 谱聚类 (Spectral Clustering) [34]: 首先将数据转换到低维空间,通常使用相似性矩阵的特征向量,然后在此低维空间中应用 k-means 等聚类算法。它也需要指定聚类数量 kk 和亲和度类型 (affinity type)。
  • 均值漂移 (Mean Shift) [5]: 通过迭代地将数据点向密度更高的区域移动来发现聚类。它不需要指定 kk,但需要一个带宽参数 (bandwidth parameter) 来定义邻域,这实际上是一个重要的调优参数。
  • AP (Affinity Propagation) [9]: 通过数据点之间传递消息来识别“代表点 (exemplars)”并形成聚类。它不需要指定 kk,但需要一个偏好参数 (preference parameter) 和阻尼因子 (damping factor)。Mean ShiftAffinity Propagation 的共同缺点是其二次空间复杂度,限制了可扩展性。

3.2.3. 基于密度的算法 (Density-based Algorithms)

  • DBSCAN (Density-Based Spatial Clustering of Applications with Noise) [7]: 通过将具有足够多邻居的点归为一类来识别密集区域作为聚类,并将稀疏点标记为噪声。它不需要指定 kk,但需要两个关键参数:邻域半径 eps 和最小点数 min-pts。这些参数的设置对结果(包括聚类数量)有很大影响。

  • OPTICS (Ordering Points to Identify the Clustering Structure) [1]: 扩展了 DBSCAN,通过基于可达距离 (reachability distance) 对点进行排序,可以识别不同密度的聚类。它避免了设置 eps,但引入了一个陡峭度参数 (steepness parameter) 来定义聚类边界。

  • HDBSCAN (Hierarchical DBSCAN) [3]:DBSCAN 的基础上引入了分层聚类框架,根据稳定性提取扁平聚类。它也需要最小聚类大小 (minimum cluster size) 和最小样本数 (minimum samples) 等参数。

    论文的附录 A (Figure 4) 展示了 DBSCANepsmin-pts 参数对最终 kk 值的影响巨大,从 6 到 4000 多个,强调了参数调优的困难性。

3.2.4. 自动确定 kk 的方法

  • X-Means [36]:k-means 的扩展,通过使用 贝叶斯信息准则 (Bayesian Information Criterion, BIC) [39] 自动确定最优的聚类数量 kkX-Means 的工作方式是,首先尝试对每个现有的聚类进行二分 (bifurcate),然后使用局部 BIC 来决定是否接受分裂。它通常需要预设一个最大聚类数量 maxKmax_K
  • Ishioka [13] 的方法:X-Means 类似,通过维护一个聚类栈 (stack of clusters) 并顺序地在每个聚类上运行 k-means (k=2) 来进行分裂。

3.3. 差异化分析

k*-means 与上述现有方法,特别是 X-Means,在理念上有一些相似之处,但也存在显著区别:

  • 参数无关性: k*-means 的核心优势在于它完全参数无关。而 X-Means 虽然能自动选择 kk,但仍需要一个 maxKmax_K 参数。其他方法如 Mean Shift, Affinity Propagation, DBSCAN 及其变体也需要其他形式的参数(带宽、偏好、eps/min-pts等)。

  • 模型选择准则: k*-means 使用 最小描述长度原理 (MDL) 作为其模型选择准则。而 X-Means 则使用 贝叶斯信息准则 (BIC)。虽然两者都是信息论或概率论范畴内的准则,但 MDL 更直接地量化了编码数据的比特数。

  • 优化过程:

    • X-Means 通常分两阶段操作:先通过局部 BIC 决定是否分裂,然后用全局 BIC 从一系列可能的模型中选择最佳模型。这意味着它需要多次运行 k-means 到收敛。
    • k*-means 则在一个统一的过程中完成。它在 k-means 的迭代中引入了 maybe-splitmaybe-merge 步骤,并通过跟踪每个聚类内部的子聚类 (subclusters) 和子质心 (subcentroids) 来评估分裂和合并的成本效益。这使得 k*-means 只需要一次运行 k-means 达到收敛,效率更高。
  • 效率: 论文指出,X-Means 或通过遍历 kk 值并使用 BIC 选择的方法 (sweeping k) 通常效率较低,因为它们需要训练多个模型到收敛。k*-means 通过其单阶段优化和对子聚类的管理,显著提高了效率。

    以下是原文 Table 1 的结果,总结了常见聚类算法及其所需的参数: 以下是原文 Table 1 的结果:

AlgorithmRequired Parameters
K-meansNumber of clusters (k)
Gaussian Mixture Models (GMM)Number of components (k); Covariance type
Spectral ClusteringNumber of clusters (k); Affinity type
Mean ShiftBandwidth parameter (kernel width)
Affinity PropagationPreference parameter; Damping factor
DBSCANNeighborhood radius (eps); Minimum points (minpts)
HDBSCANMinimum cluster size; Minimum samples; Cluster selection eps
OPTICSCut threshold for eps (ξ); Minimum neighborhood points (MinPts)
X-MeansMaximum number of clusters; Minimum number of clusters
k*means

4. 方法论

k*-means 算法的核心思想是利用 最小描述长度原理 (Minimum Description Length, MDL) 来自动确定最优的聚类数量 kk*。它通过同时优化 k-means 目标函数和 MDL 目标函数,在 k-means 的迭代过程中引入了聚类的分裂 (splitting) 和合并 (merging) 操作。

4.1. 方法原理:量化描述长度 (Quantifying Description Length)

k*-means 将聚类模型的描述长度量化为比特成本 (bit cost),并在训练过程中最小化这个总成本。一个数据点 xx 在聚类模型下的比特成本由两部分组成:

  1. 索引成本 (index cost): 指定数据点 xx 所属聚类的成本。如果当前有 KK 个聚类,那么选择 KK 个聚类中的一个需要 log2K\log_2 K 比特。对于 NN 个数据点,总索引成本为 Nlog2KN \log_2 K 比特。

  2. 残差成本 (residual cost): 指定数据点 xx 相对于其分配到的聚类质心 (centroid) 的位移 (displacement) 的成本。这可以近似为负对数概率 (negative log-probability),即 logp(xc)-\log p(x|c),其中 ccxx 所属聚类的质心。

    论文将每个聚类内的数据分布建模为单位方差的多元正态分布 (multivariate normal distribution with unit variance)。对于一个数据点 xx 及其所属聚类的质心 cc,其概率密度函数 (probability density function) p(xc)p(x|c) 为: p(xc)=1(2π)d/2exp(12(xc)T(xc)) p(x|c) = \frac{1}{(2\pi)^{d/2}} \exp\left(-\frac{1}{2} (x-c)^T (x-c)\right) 其中 dd 是数据的维度。

那么,对应的负对数概率为: logp(xc)=dlog2π+xc22 -\log p(x|c) = \frac{d \log 2\pi + ||x-c||^2}{2} 这表明残差成本与数据点到其质心的平方距离 (squared distance) 成正比。

总描述长度目标函数: 整个聚类模型的数据总成本由所有数据点的索引成本和残差成本之和,再加上模型本身的成本构成。对于 k*-means,模型本身的成本是表示 kk 个聚类质心所需的比特数。如果每个质心有 dd 维,并且每个浮点数需要 mm 比特精度来精确表示,那么模型成本为 KdmK \cdot d \cdot m 比特。

形式上,设 XX 为要聚类的数据,Π(X)\Pi(X)XX 的所有划分 (partitions) 的集合,P|P| 为划分 PP 中的子集数量(即聚类数量)。最优划分 PP^* 的目标函数为: P=argminPΠ(X)Pdm+XlogP+12SPQ(S) P^* = \operatorname*{argmin}_{P \in \Pi(X)} |P|dm + |X|\log|P| + \frac{1}{2}\sum_{S \in P} Q(S) 其中 Q(S) 计算聚类 SS 内部所有点到其质心的平方和 (total sum of squares)。Q(X)=XVsbXQ(X) = |X| \mathrm{Vsb} X (此处原文 Q(X)=XVsbXQ(X) = |X| \mathrm{Vsb} X 似乎有误,根据附录 B 推导 Q(S)=xSxc(P,x)2Q(S) = \sum_{x \in S} ||x - c(P,x)||^2,表示聚类 SS 中所有点到其质心的平方距离之和)。最终,最优聚类数量 k=Pk^* = |P^*|

MDL 目标函数的推导 (来自附录 B): 目标是最小化以下表达式: argminPΠ(X)Pdm+XlogP+xXdlog2π+xc(P,x)22 \operatorname*{argmin}_{P \in \Pi(X)} |P|dm + |X|\log|P| + \sum_{x \in X} \frac{d \log 2\pi + ||x - c(P,x)||^2}{2} 其中 c(P,x) 是数据点 xx 在划分 PP 下所属聚类的质心。 由于 dlog2πd \log 2\pi 是一个常数项,在最小化过程中可以忽略。因此,上式等价于: argminPΠ(X)Pdm+XlogP+12xXxc(P,x)2 \operatorname*{argmin}_{P \in \Pi(X)} |P|dm + |X|\log|P| + \frac{1}{2}\sum_{x \in X} ||x - c(P,x)||^2 将对所有数据点的平方距离求和,转换为对每个聚类内数据点的平方距离求和: argminPΠ(X)Pdm+XlogP+12SPxSxc(P,x)2 \operatorname*{argmin}_{P \in \Pi(X)} |P|dm + |X|\log|P| + \frac{1}{2}\sum_{S \in P} \sum_{x \in S} ||x - c(P,x)||^2 定义 Q(S)=xSxc(P,x)2Q(S) = \sum_{x \in S} ||x - c(P,x)||^2,即聚类 SS 内所有点到其质心的平方距离之和。最终得到: P=argminPΠ(X)Pdm+XlogP+12SPQ(S) P^* = \operatorname*{argmin}_{P \in \Pi(X)} |P|dm + |X|\log|P| + \frac{1}{2}\sum_{S \in P} Q(S) 其中:

  • P|P|:当前聚类模型的聚类数量 KK
  • dd: 数据的维度。
  • mm: 表示一个浮点数所需的比特精度 (float precision),通过数据中任意两个值之间的最小距离的负对数来确定。具体计算为 floatcost=(max(X)min(X))/floatprecisionfloatcost = (max(X) - min(X)) / floatprecision (在 MDLCOST 过程中定义)。
  • Pdm|P|dm: 模型成本 (model cost),即编码所有聚类质心所需的比特数。
  • XlogP|X|\log|P|: 索引成本 (index cost),即编码每个数据点所属聚类标签所需的比特数。
  • 12SPQ(S)\frac{1}{2}\sum_{S \in P} Q(S): 残差成本 (residual cost),即编码每个数据点与其质心位移所需的比特数。

4.2. 核心方法详解:最小化描述长度 (Minimizing Description Length)

k*-means 算法 (Algorithm 1) 通过在标准的 k-means 迭代中加入 maybe-splitmaybe-merge 步骤来有效优化上述 MDL 目标函数。

4.2.1. 算法流程 (Algorithm 1: K*-MEANS)

k*-means 的主循环在每次迭代中执行标准的 k-means 步骤,并交替执行 maybe-splitmaybe-merge 步骤,以动态调整聚类数量 KK

1: procedure K*-MEANS(X)
2:   best_cost ← ∞
3:   unimproved_count ← 0
4:   μ ← [∑_{i=1}^n x_i / n]  # 初始化一个包含所有数据点平均值的质心
5:   C ← [X]                 # 初始化一个包含所有数据点的聚类
6:   μs ← [INITSUBCENTROIDS(X)] # 为初始聚类初始化两个子质心
7:   Cs ← [{x ∈ X : ||x - μs1|| < ||x - μs2||}, {x ∈ X : ||x - μs2|| < ||x - μs1||}] # 根据子质心划分初始子聚类
8:   while true do
9:     μ, C, μs, Cs ← KMEANSSTEP(X, μ, C, μs, Cs) # 执行 k-means 步骤,更新质心和聚类
10:    μ, C, μs, Cs, did_split ← MAYBESPLIT(X, μ, C, μs, Cs) # 尝试分裂聚类
11:    if ¬did_split then # 如果没有发生分裂
12:      μ, C, μs, Cs ← KMEANSSTEP(X, μ, C, μs, Cs) # 再次执行 k-means 步骤
13:      μ, C, μs, Cs ← MAYBEMERGE(X, μ, C, μs, Cs) # 尝试合并聚类
14:    end if
15:    cost ← MDLCOST(X, μ, C) # 计算当前 MDL 成本
16:    if cost < best_cost then
17:      best_cost ← cost
18:      unimproved_count ← 0
19:    else
20:      unimproved_count ← unimproved_count + 1
21:    end if
22:    if unimproved_count = patience then # 如果成本在一定次数的迭代中没有改善,则停止
23:      break
24:    end if
25:  end while
26:  return μ, C # 返回最终的质心和聚类
27: end procedure

初始化 (Lines 4-7): 算法以单个聚类开始,包含所有数据点 XX

  • μμ: 初始质心是所有数据点的平均值。
  • CC: 初始聚类包含所有数据点 XX
  • μsμs: INITSUBCENTROIDS(X) 函数为这个唯一的初始聚类生成两个子质心 (subcentroids)。这通常通过 k++-means 初始化方法 [2] 或类似的策略实现,以确保子质心之间有良好的分离。
  • Cs: 根据这两个子质心将初始聚类 XX 划分为两个子聚类。

主循环 (Lines 8-25): 循环直到 MDL 成本在连续 patience 次迭代中没有改善为止。

  • KMEANSSTEP (Line 9 & 12): 这是一个扩展的标准 k-means 步骤。它不仅更新主聚类 CC 和主质心 μμ,还以同样的方式更新每个主聚类内部的子聚类 Cs 和子质心 μsμs。本质上,每个主聚类内部都在进行一个“迷你” k-means 过程。这个步骤包括:
    • 分配 (Assign): 将每个数据点分配给最近的主质心。同时,将每个主聚类中的数据点分配给其内部最近的子质心。
    • 更新 (Update): 重新计算每个主聚类的质心为其中所有点的平均值。同样,重新计算每个子聚类的子质心为其内部所有点的平均值。
  • MAYBESPLIT (Line 10): 检查是否有聚类应该被分裂。
  • MAYBEMERGE (Line 13): 如果没有发生分裂,则检查是否有聚类应该被合并。
  • MDLCOST (Line 15): 计算当前的 MDL 成本,用于评估算法的进展和收敛。

4.2.2. MDLCOST 过程 (Algorithm 2: MDLCOST)

这个过程计算给定当前聚类模型下的总描述长度。

28: procedure MDLCOST(X, μ, C)
29:   d ← the dimensionality of X # 数据的维度
30:   floatprecision ← -log of the minimum distance between any values in X # 浮点精度
31:   floatcost ← (max(X) - min(X)) / floatprecision # (原文此处有误,应为 floatprecision = -log(min_dist_val),然后 modelcost 使用 floatprecision。但这里是按原文直接转录,后续根据上下文理解)
32:   modelcost ← |C| * d * floatcost # 模型成本:聚类数量 * 维度 * 浮点精度成本
33:   idxcost ← |X| * log(|C|) # 索引成本:数据点数量 * log(聚类数量)
34:   c ← the sum of the squared distances of every point in X from its assigned centroid # 所有点到其质心的平方距离之和
35:   residualcost ← |X| * d * log(2π) + c # 残差成本 (根据推导,常数项可忽略,但此处是完整形式)
36:   return modelcost + idxcost + residualcost
37: end procedure

MDLCOST 符号解释:

  • dd: 数据 XX 的维度。
  • floatprecision: 浮点精度。原文描述为“min(X)max(X) 之间最小距离的负对数”,但通常浮点精度 mm 是一个定值,或通过数据范围和精度需求计算得出。这里 floatcost 的计算 (max(X) - min(X)) / floatprecision 在原文中略显模糊,但其目的是估计表示一个浮点值所需的比特成本。在实际实现中,这通常是一个预设的常量,如 32 或 64。
  • modelcost: 模型成本。C|C| 是当前聚类的数量 (即 KK)。此项表示编码所有 KKdd 维质心所需的总比特数。
  • idxcost: 索引成本。X|X| 是数据点的总数 (即 NN)。log(C)log(|C|) 是编码每个数据点所属聚类所需的比特数。
  • cc: 所有数据点到其各自所属聚心的平方距离之和 (SSE)。
  • residualcost: 残差成本。Xdlog(2π)|X| * d * log(2π) 是一个常数项,ccSSE。根据 MDL 推导,这两项共同组成了残差成本。

4.2.3. MAYBESPLIT 过程 (Algorithm 2: MAYBESPLIT)

maybe-split 过程检查是否应该将某个聚类分裂成两个子聚类。

1: procedure MAYBESPLIT(X, μ, C, μs, Cs)
2:   best_costchange ← MDLCOST(X, μ, C) # 初始最佳成本变化设定为当前总 MDL 成本
3:   split_at ← -1 # 标记要分裂的聚类索引
4:   for i ∈ {0, ..., |μ|} do # 遍历所有当前聚类
5:     subc1, subc2 ← Cs[i] # 获取第 i 个聚类的两个子聚类
6:     submu1, submu2 ← μs[i] # 获取第 i 个聚类的两个子质心
7:     costchange = (Σ_{x ∈ submu1} (x - subc1)^2 + Σ_{x ∈ submu2} (x - subc2)^2) - Σ_{x ∈ C[i]} (x - μ[i])^2 + |X| / (|μ| + 1)
       # costchange 的含义:分裂后残差成本的减少量 - 索引成本的增加量 (近似)
       # 详细: (分裂后两个子聚类内部的 SSE) - (原聚类内部的 SSE) + 索引成本增加的近似值
8:     if costchange < best_costchange then # 如果这个分裂操作能减少总成本
9:       best_costchange ← costchange
10:      split_at ← i # 记录要分裂的聚类索引
11:    end if
12:  end for
13:  if best_costchange < 0 then # 如果存在一个分裂能使总成本减少
14:    μ, C ← SPLIT(μ, C, μs, Cs, split_at) # 执行分裂操作,更新主质心和主聚类
15:    new_μs ← INITSUBCENTROIDS(μs[split_at]) # 为新分裂出的两个聚类分别初始化子质心 (原文此处有误,应为两个新的子质心列表,但直接转录)
16:    μs ← μs[:split_at] + new_μs + μs[split_at:] # 更新子质心列表
17:  end if
18:  return μ, C, μs, Cs, split_at ≥ 0 # 返回更新后的模型和是否发生分裂的标志
19: end procedure

MAYBESPLIT 详解:

  • 成本变化评估 (Line 7): 对于每个聚类 SiS_i 及其内部的两个子聚类 Si1,Si2S_{i1}, S_{i2},算法评估将其分裂的成本变化。
    • 残差成本变化:Q(Si)Q(S_i) 变为 Q(Si1)+Q(Si2)Q(S_{i1}) + Q(S_{i2})。分裂通常会减少残差成本(因为每个点离更小的子聚类质心更近)。
    • 索引成本变化: 聚类数量从 KK 变为 K+1K+1。每个数据点的索引成本从 logK\log K 增加到 log(K+1)\log (K+1),总索引成本增加 X(log(K+1)logK)X/(K+1)|X|(\log(K+1) - \log K) \approx |X|/(K+1)
    • 模型成本变化: 聚类数量从 KK 变为 K+1K+1。模型成本增加 dmd \cdot m 比特。
  • 原文第 7 行的 costchange 计算是一个简化的、用于快速判断分裂是否有利的启发式方法。它实际上是计算了分裂后残差成本的减少量与索引成本增加量的平衡:
    • Σxsubmu1(xsubc1)2+Σxsubmu2(xsubc2)2Σ_{x ∈ submu1} (x - subc1)^2 + Σ_{x ∈ submu2} (x - subc2)^2:分裂后两个子聚类内部的 SSE
    • ΣxC[i](xμ[i])2Σ_{x ∈ C[i]} (x - μ[i])^2:原聚类内部的 SSE
    • X/(μ+1)|X| / (|μ| + 1):这是索引成本增加的近似值,μ|μ| 是当前聚类数量 KK
    • 所以 costchange = (新 SSE) - (旧 SSE) + (索引成本增加)。如果这个 costchange<0costchange < 0,说明分裂有利。
  • 分裂操作 (Lines 13-17): 如果某个分裂能使 MDL 成本降低(即 best_costchange < 0),则执行该分裂。被选中的聚类分裂成其两个子聚类,这两个子聚类升格为新的主聚类。然后为这些新聚类重新初始化内部的子聚类和子质心。

4.2.4. MAYBEMERGE 过程 (Algorithm 3: MAYBEMERGE)

maybe-merge 过程检查是否应该将两个聚类合并。为了提高效率,它只考虑最近的两个聚类进行合并。

1: procedure MAYBEMERGE(X, μ, C, μs, Cs)
2:   i1, i2 ← the indices of the closest pair of centroids # 找到最近的两个质心的索引
3:   Z ← C[i1] ∪ C[i2] # 合并这两个聚类的数据点
4:   m_merged ← (1 / |Z|) * Σ_{x ∈ Z} x # 计算合并后新聚类的质心
5:   mainQ ← Σ_{z ∈ Z} (z - m_merged)^2 # 计算合并后新聚类内部的 SSE
6:   subcQ ← Σ_{x ∈ C[i1]} (x - μ[i1])^2 + Σ_{x ∈ C[i2]} (x - μ[i2])^2 # 合并前两个聚类内部的 SSE 之和
7:   costchange ← mainQ - subcQ - |X| / |μ| # 合并后残差成本的增加量 - 索引成本的减少量 (近似)
8:   if costchange < 0 then # 如果合并能减少总成本
9:     C ← C with C[i1] replaced with Z and C[i2] removed # 执行合并操作,更新主聚类列表
10:    μ ← μ with μ[i1] replaced with m_merged and μ[i2] removed # 执行合并操作,更新主质心列表
11:  end if
12:  return μ, C # 返回更新后的模型
13: end procedure

MAYBEMERGE 详解:

  • 选择合并对象 (Line 2): 仅考虑距离最近的两个质心对应的聚类进行合并,以减少计算量。
  • 成本变化评估 (Line 7): 类似 maybe-split,算法评估合并这两个聚类的成本变化。
    • 残差成本变化:Q(Si1)+Q(Si2)Q(S_{i1}) + Q(S_{i2}) 变为 Q(Si1Si2)Q(S_{i1} \cup S_{i2})。合并通常会增加残差成本(因为点离合并后的更大聚类质心可能更远)。
    • 索引成本变化: 聚类数量从 KK 变为 K-1。每个数据点的索引成本从 logK\log K 减少到 log(K1)\log (K-1),总索引成本减少 X(logKlog(K1))X/K|X|(\log K - \log (K-1)) \approx |X|/K
    • 模型成本变化: 聚类数量从 KK 变为 K-1。模型成本减少 dmd \cdot m 比特。
  • 原文第 7 行的 costchange 计算是一个简化的、用于快速判断合并是否有利的启发式方法:
    • mainQ:合并后新聚类内部的 SSE
    • subcQ:合并前两个聚类内部的 SSE 之和。
    • X/μ|X| / |μ|:这是索引成本减少的近似值,μ|μ| 是当前聚类数量 KK
    • 所以 costchange = (新 SSE) - (旧 SSE) - (索引成本减少)。如果这个 costchange<0costchange < 0,说明合并有利。
  • 合并操作 (Lines 8-10): 如果合并能使 MDL 成本降低,则执行合并。两个聚类被移除,它们的并集形成一个新的聚类。

4.2.5. 收敛性证明 (Proof of Convergence)

论文在附录 C 中提供了 k*-means 算法的收敛性证明。

  • 引理 1 (Lemma 1): 在每次分配 (assign) 步骤中,MDL 成本要么减少要么保持不变。只有当没有数据点被重新分配时,成本才保持不变。
    • 证明: 分配步骤不改变聚类数量 KK 或数据点数量 NN,因此不影响模型成本和索引成本。它只影响残差成本。通过重新分配点到最近的质心,每个点的平方距离会最小化。如果一个点被重新分配,则它到新质心的距离小于到旧质心的距离,从而严格减少残差成本。
  • 引理 2 (Lemma 2): 在每次更新 (update) 步骤中,MDL 成本要么减少要么保持不变。只有当没有质心被更新时,成本才保持不变。
    • 证明: 更新步骤不改变聚类数量 KK 或数据点数量 NN,因此不影响模型成本和索引成本。质心被更新为其所属聚类中所有点的平均值,而平均值是最小化该聚类内部所有点到其中心点平方距离之和的唯一解。因此,更新质心会最小化残差成本。
  • 定理 3 (Theorem 3): k*-means 算法保证在有限时间内收敛。
    • 证明: 根据引理 1 和引理 2,assignupdate 步骤在发生变化时会严格降低 MDL 成本。maybe-splitmaybe-merge 步骤也明确地设定了只有当 MDL 成本减少时才执行操作。这意味着 k*-means 在训练过程中永远不会回到之前的聚类分配状态。由于数据点的划分是有限的(由贝尔数 BN+1B_{N+1} 给出 [10]),因此算法在有限步内必然收敛。

      这个收敛性证明是标准 k-means 收敛性证明的扩展,虽然理论上的最坏情况运行时间是指数级的,但在实践中算法通常能快速收敛。

5. 实验设置

论文通过三组实验评估了 k*-means 算法:合成数据上的 kk 估计准确性、真实标注数据集上的聚类性能,以及不同数据集规模下的运行时间。

5.1. 数据集

5.1.1. 合成数据 (Synthetic Data)

  • 生成方式: 对于一系列 kk 值,使用 Bridson 采样 (Bridson sampling) 在二维空间 R2\mathbb{R}^2 中生成 kk 个质心,并限制它们之间的最小距离 dd。然后,从每个质心生成 1000/k1000/k 个数据点,这些点服从单位方差的多元正态分布 (multivariate normal distribution with unit variance)。

  • 目的: 用于测试算法在已知真实 kk 值的情况下,能否准确估计出 kk

  • 参数: kk 从 1 到 50,最小质心间距 dd 分别为 2, 3, 4, 5。每种 (k, d) 组合重复 10 次。

  • 示例: 原文 Figure 1 展示了 dd 值为 2, 3, 5 时的合成数据示例,反映了不同的聚类分离度。

    Figure 1: Synthetic data of standard, multivariate Normal clusters, with varying degrees of separation. Left: weak separation, inter-centroid distance constrained to \(\\geq 2\) , \(\\mathtt { k } ^ { * } \\mathtt { m e a n s }\) is \(9 \\%\) accurate in inferring \(k\) and baselines are \({ \\leq } 4 . 4 \\%\) . Middle: inter-centroid distance constrained to \(\\geq 3\) \(\\mathtt { k } ^ { * }\) means is \(2 5 \\%\) accurate in inferring \(k\) and baselines are \(\\leq 1 6 \\%\) .Right: strong separation, inter-centroid distance constrained to \(\\geq 5\) , \(\\mathtt { k } ^ { * }\) means is \(9 9 \\%\) accurate in inferring \(k\) and baselines are \(leq 5 7 \\%\) . 该图像是三幅展示合成数据的散点图,均表示具有20个聚类。左图显示了弱分离度的聚类,中图为中等分离度的聚类,而右图展示强分离度的聚类。不同颜色对应不同的聚类,从而强调了聚类算法在不同条件下的表现。

图 (原文 Figure 1) 展示了合成数据在不同聚类分离度下的情况。左图是弱分离(质心间距 2\ge 2),中图是中等分离(质心间距 3\ge 3),右图是强分离(质心间距 5\ge 5)。

5.1.2. 真实世界标注数据集 (Labelled Datasets)

  • MNIST: 手写数字数据集 (0-9),共 10 个类别。
  • USPS: 手写数字数据集 (0-9),共 10 个类别。
  • Imagenette [12]: ImageNet 的一个子集,包含 10 个图像类别。
  • Speech Commands: 短语音命令识别数据集,包含 36 个类别。
  • 20 NewsGroups: 文本数据集,包含 20 个主题类别。
  • MSRVTT: 视频剪辑数据集,配有自然语言描述,包含 20 个类别。

5.1.3. 数据预处理 (Preprocessing)

为了处理高维或复杂的数据模态,论文采用了特征提取和降维技术:

  • UMAP [30]: (min-dist=0, n-neighbours=10) 用于所有数据集的降维。
  • CLIP [37]: 应用于 Imagenette 数据集和 MSRVTT 数据集(视频和文本模态)以提取特征。
  • Llama-3.1 [40]: 应用于 20 NewsGroups 数据集以提取特征(对所有词元取平均)。

5.2. 评估指标

论文使用了多种评估指标来衡量聚类算法的性能,包括预测 kk 的准确性以及聚类划分与真实标签的一致性。

5.2.1. 预测 kk 的均方误差和准确率

  • 均方误差 (Mean Squared Error, MSE):
    1. 概念定义: 衡量预测值与真实值之间差异的平方的平均值。在本文中,用于量化预测的聚类数量 kpredk_{pred} 与真实聚类数量 ktruek_{true} 之间的平均差异程度。值越小表示预测越准确。
    2. 数学公式: MSE=1Nsamplesi=1Nsamples(kpred,iktrue,i)2 \mathrm{MSE} = \frac{1}{N_{samples}} \sum_{i=1}^{N_{samples}} (k_{pred,i} - k_{true,i})^2
    3. 符号解释:
      • NsamplesN_{samples}: 总样本数(这里指合成数据实验中不同的 (k, d) 组合重复次数)。
      • kpred,ik_{pred,i}: 第 ii 个样本的预测聚类数量。
      • ktrue,ik_{true,i}: 第 ii 个样本的真实聚类数量。
  • 准确率 (Accuracy):
    1. 概念定义: 衡量预测的聚类数量与真实聚类数量完全一致的样本所占的比例。
    2. 数学公式: Accuracy=NcorrectNsamples \mathrm{Accuracy} = \frac{N_{correct}}{N_{samples}}
    3. 符号解释:
      • NcorrectN_{correct}: 预测聚类数量 kpredk_{pred} 与真实聚类数量 ktruek_{true} 完全一致的样本数。
      • NsamplesN_{samples}: 总样本数。

5.2.2. 聚类质量评估指标 (与真实标签比较)

这些指标用于评估聚类算法生成的划分与数据的真实类别标签 (Ground Truth) 划分之间的匹配程度。

  • 聚类准确率 (Clustering Accuracy, ACC) [27]:

    1. 概念定义: 衡量聚类结果与真实标签匹配的程度。由于聚类算法本身不关心标签的顺序,通常需要找到一个最优的映射 (mapping) 将聚类标签映射到真实标签,然后计算匹配度。它反映了有多少数据点被正确地分配到其对应的真实类别。
    2. 数学公式: ACC=maxmapi=1N1(yi=map(ci))N \mathrm{ACC} = \max_{map} \frac{\sum_{i=1}^N \mathbf{1}(y_i = map(c_i))}{N}
    3. 符号解释:
      • NN: 数据点的总数。
      • yiy_i: 第 ii 个数据点的真实类别标签。
      • cic_i: 第 ii 个数据点被分配到的聚类标签。
      • map: 从聚类标签到真实标签的所有可能映射中的一个。
      • maxmap\max_{map}: 选择能够最大化准确率的映射。
      • 1()\mathbf{1}(\cdot): 指示函数,如果条件为真则为 1,否则为 0。
  • 调整兰德指数 (Adjusted Rand Index, ARI) [27]:

    1. 概念定义: 衡量两个数据划分之间相似度的指标,通过修正兰德指数 (Rand Index) 来消除随机机会造成的影响。ARI 的值范围在 -1 到 1 之间,1 表示两个划分完全一致,0 表示与随机分配的结果一致,负值表示比随机分配更差。它对聚类数量差异较大的情况具有较好的鲁棒性。
    2. 数学公式: ARI=RIE[RI]max(RI)E[RI] \mathrm{ARI} = \frac{\mathrm{RI} - E[\mathrm{RI}]}{\max(\mathrm{RI}) - E[\mathrm{RI}]} 其中,兰德指数 (RI) 为: RI=a+b(N2) \mathrm{RI} = \frac{a+b}{\binom{N}{2}}
    3. 符号解释:
      • NN: 数据点的总数。
      • (N2)\binom{N}{2}: 从 NN 个数据点中选择两个点的所有可能对数。
      • aa: 在两个划分中都属于同一聚类/类别的点对数。
      • bb: 在两个划分中都属于不同聚类/类别的点对数。
      • E[RI]E[\mathrm{RI}]: 随机分配下兰德指数的期望值。
      • max(RI)\max(\mathrm{RI}): 兰德指数的最大可能值。
  • 归一化互信息 (Normalized Mutual Information, NMI) [27]:

    1. 概念定义: 衡量两个变量(这里是聚类划分和真实标签)之间相互依赖性的指标,并进行归一化。NMI 的值范围在 0 到 1 之间,1 表示两个划分完全一致,0 表示完全独立。它基于信息熵 (entropy) 的概念,量化了通过知道其中一个划分可以获得多少关于另一个划分的信息。
    2. 数学公式: NMI(Y,C)=MI(Y,C)H(Y)H(C) \mathrm{NMI}(Y, C) = \frac{\mathrm{MI}(Y, C)}{\sqrt{\mathrm{H}(Y) \mathrm{H}(C)}} 其中,互信息 (MI) 为: MI(Y,C)=yYcCP(y,c)log(P(y,c)P(y)P(c)) \mathrm{MI}(Y, C) = \sum_{y \in Y} \sum_{c \in C} P(y,c) \log\left(\frac{P(y,c)}{P(y)P(c)}\right) 信息熵 (H) 为: H(Y)=yYP(y)logP(y) \mathrm{H}(Y) = - \sum_{y \in Y} P(y) \log P(y)
    3. 符号解释:
      • YY: 真实类别标签的集合。
      • CC: 聚类标签的集合。
      • P(y,c): 一个数据点同时属于真实类别 yy 和聚类 cc 的联合概率。
      • P(y): 一个数据点属于真实类别 yy 的边缘概率。
      • P(c): 一个数据点属于聚类 cc 的边缘概率。
      • H(Y)\mathrm{H}(Y): 真实类别标签的熵。
      • H(C)\mathrm{H}(C): 聚类标签的熵。
      • MI(Y,C)\mathrm{MI}(Y, C): 真实标签和聚类标签之间的互信息。

5.3. 对比基线 (Baselines)

论文将 k*-means 与一系列现有聚类算法进行了比较,特别是那些不需要预设 kk 的方法。为了提供性能上限,也包括了已知真实 kk 值的 k-meansGMM

5.3.1. 无需预设 kk 的基线方法

  • AP (Affinity Propagation): (阻尼因子 damping factor = 0.5)
  • Mean Shift: (带宽 bandwidth = 成对距离的中位数 median of pairwise distances)
  • DBSCAN: (eps = 0.5, min-samples = 5)
  • HDBSCAN: (min-cluster-size, min-samples 等参数设置为 sci-kit learn 默认值,通常会导致大量离群点)
  • OPTICS: (ξξ = 0.05, min-samples = 5)
  • X-Means: (kmax = dataset size\sqrt{\text{dataset size}})。论文解释选择此 kmax 值是因为此时索引成本和残差成本的信息量大致相等。所有其他参数均为 sci-kit learn 默认值。

5.3.2. 需要预设 kk 的上限方法

  • k-Means: 知道真实的聚类数量 kk
  • GMM (Gaussian Mixture Models): 知道真实的聚类数量 kk

5.3.3. 扫描 kk 的基线方法 (Sweeping kk)

这是一种常见的处理未知 kk 的策略,即训练多个 k-means 模型,kk 值从 1 开始逐步增加(以数据集大小的 10% 为增量),然后使用贝叶斯信息准则 (BIC) 选择最佳的 kk 值。

6. 实验结果与分析

6.1. 核心结果分析

6.1.1. 合成数据上的 kk 预测准确性

论文首先在合成数据集上评估了 k*-means 及其基线算法在预测真实聚类数量 kk 方面的性能。

以下是原文 Table 2 的结果:

Performance on predicting the true number of clusters in synthetic data for varying degrees of cluster separation. k*means performs consistently the best, and reaches near perfect accuracy when d=5d = 5.
mseacc
k*meansdbscanhdbscanxmeansk*meansdbscanhdbscanxmeans
synthetic d=2306.35126.10414.73721.549.004.404.003.80
synthetic d=381.70252.41116.35681.9725.405.407.8016.00
synthetic d=41.94244.2828.3460.1368.007.6021.4022.20
synthetic d=50.00238.1812.8323.9999.806.6057.6025.40

分析:

  • k*-means 的卓越性能: 无论聚类分离度 dd 如何,k*-meanskk 的预测方面始终表现最佳。
    • 在弱分离 (synthetic d=2) 情况下,k*-meansMSEAcc 仍远优于所有基线。
    • 随着分离度增加,k*-means 的性能显著提升。当 d=5d=5 (强分离) 时,k*-meansMSE 接近 0 (0.00),Acc 达到 99.80%,几乎完美地预测了真实的 kk 值。
  • 基线方法表现:
    • DBSCANX-MeansMSE 普遍较高,Acc 较低,表明它们在准确估计 kk 方面存在困难。DBSCANMSE 相对较低但准确率不高,可能因为它倾向于产生非常少的聚类或大量离群点。
    • HDBSCANd=4d=4d=5d=5MSE 有所下降,Acc 有所提升,但仍远低于 k*-means
  • 分离度的影响: 结果清楚地表明,随着聚类之间分离度的增加,所有算法的性能都有所改善,但 k*-means 的改进最为显著,并且与基线方法之间的性能差距也随之扩大。这验证了 k*-means 在聚类结构清晰时能够非常准确地识别 kk

6.1.2. 标注数据集上的聚类性能

论文在六个不同模态的标注数据集上评估了 k*-means 与基线方法的聚类质量,使用 ACC、ARI 和 NMI 指标,并报告了预测的 kk 值、离群点数量和运行时间。

以下是原文 Table 3 的结果:

ACC ARI NMI k Num Outliers Runtime (s)
MNIST domain = images n classes = 10 affinity -1.00 -1.00 -1.00 -1.00 0 36000+
meanshift 77.23 63.42 80.28 7.00 0 463.39
DBSCAN 68.75 54.84 77.66 6.00 1 2.95
HDBSCAN 79.73 0.06 36.95 20696.00 11122 225.34
OPTICS 0.32 0.00 34.77 1214.00 11190 46.24
xmeans 40.89 (4.75) 34.77 (4.70) 64.74 (2.25) 118.80 (23.59) 0 16.40 (6.41)
k*means 91.26 (3.56) 84.99 (2.97) 87.44 (1.14) 10.90 (0.32) 0 3.38 (0.39)
kmeans 84.12 (8.13) 79.64 (6.92) 85.31 (2.73) 10.00 0 0.09 (0.05)
GMM 86.29 (7.05) 82.61 (6.89) 87.41 (2.74) 10.00 0 0.78 (0.26)
USPS domain = images n classes = 10 affinity 61.29 49.37 75.94 25.00 0 148.15
meanshift 74.55 63.88 78.03 6.00 0 27.93
DBSCAN 80.46 71.00 83.51 7.00 0 0.13
HDBSCAN 77.49 82.16 79.09 108.00 829 0.80 (0.01)
OPTICS 1.88 0.46 43.95 2681.00 1617 11.68
xmeans 55.12 (5.03) 46.09 (4.23) 73.27 (1.71) 41.00 (8.12) 0 1.00 (0.43)
k*means 88.68 (0.00) 81.57 (0.00) 87.14 (0.00) 8.00 (0.00) 0 0.26 (0.03)
kmeans 79.72 (8.15) 78.68 (6.66) 86.4 (2.12) 10.00 0 0.03 (0.03)
GMM 81.72 (6.76) 80.27 (5.68) 86.84 (1.82) 10.00 0 0.11 (0.01)
Imagenet (subset) domain = images n classes = 10 affinity -1.00 -1.00 -1.00 -1.00 0 36000+
meanshift 55.98 36.05 58.67 6.00 0 103.31
DBSCAN 26.09 3.70 22.00 3.00 1 0.22
HDBSCAN 51.62 46.01 55.52 402.00 4193 1.09 (0.02)
OPTICS 1.35 0.28 40.22 3916.00 2262 18.11
xmeans 39.21 (3.19) 25.53 (3.03) 55.92 (0.88) 70.00 (8.54) 0 2.76 (0.68)
k*means 66.18 (1.55) 46.42 (1.45) 60.20 (0.86) 6.40 (0.70) 0 0.94 (0.34)
kmeans 69.79 (5.18) 55.08 (4.65) 64.16 (2.81) 10.00 0 0.05 (0.04)
GMM 66.85 (6.11) 53.97 (5.44) 64.01 (2.76) 10.00 0 0.30 (0.09)
Speech Commands domain = audio n classes = 36 affinity -1.00 -1.00 -1.00 -1.00 0 36000+
meanshift 52.08 17.89 59.53 16.00 0 1205.21
DBSCAN 50.60 10.52 61.59 20.00 0 2.22
HDBSCAN 65.35 67.68 67.12 2453.00 24170 53.98 (7.86)
OPTICS 0.74 0.13 47.76 28932.00 17163 325.78
xmeans 26.32 (7.78) 14.33 (8.22) 47.70 (18.56) 190.10 (161.25) 0 16.00 (13.01)
k*means 68.73 (1.57) 48.43 (2.49) 70.22 (0.67) 26.50 (0.97) 0 20.98 (5.22)
kmeans 71.08 (1.72) 57.78 (1.67) 72.67 (0.47) 36.00 0 0.30 (0.06)
GMM 71.04 (1.27) 56.12 (1.63) 72.90 (0.42) 36.00 0 6.46 (0.89)
20 NG domain = text n classes = 20 affinity 40.36 23.94 48.27 75.00 0 597.33
meanshift 21.50 9.19 30.45 9.00 0 275.23
DBSCAN 16.40 1.98 18.59 12.00 0 0.40
HDBSCAN 30.08 24.05 47.72 664.00 6153 3.27 (0.03)
OPTICS 1.60 0.27 43.73 5529.00 3211 28.84
xmeans 30.01 (10.66) 15.48 (8.18) 37.78 (19.83) 107.60 (56.16) 0 4.78 (2.51)
k*means 42.33 (1.14) 26.08 (0.44) 46.61 (0.67) 11.20 (0.42) 0 2.46 (0.96)
kmeans 46.73 (1.47) 33.68 (0.53) 50.42 (0.48) 20.00 0 0.07 (0.06)
GMM 47.03 (1.22) 33.71 (0.78) 50.68 (0.50) 20.00 0 0.86 (0.19)
MSRVTT domain = video & text n classes = 20 affinity 37.65 12.82 35.96 46.00 0 31.09
meanshift 11.51 3.24 18.40 15.00 0 25.09
DBSCAN 45.39 39.23 46.86 27.00 0 0.05
HDBSCAN 4.30 0.70 24.36 1763.00 1275 0.26 (0.73)
OPTICS 31.78 (580.54) 11.64 (965.93) 38.16 (1441.93) 32.40 (3924.62) 1091 5.02
xmeans 44.10 (136.25) 25.75 (65.28) 38.43 (33.06) 18.10 (87.56) 0 0.39 (40.48)
k*means 40.07 (108.95) 25.35 (128.11) 38.43 (62.75) 18.10 (87.56) 0 2.57 (40.59)
kmeans 44.10 (136.25) 25.75 (65.28) 38.16 (33.06) 20.00 0 0.07 (0.06)
GMM 40.07 (108.95) 25.35 (128.11) 38.43 (62.75) 20.00 0 0.26 (0.73)

分析:

  • k*-means 的总体优势: k*-means 在所有六个数据集上,无论是在 ACC、ARI 还是 NMI 指标上,都显著优于所有不需要设置 kk 的基线方法。
    • 预测 kk 的准确性: k*-means 在所有数据集上预测的 kk 值都更接近真实类别数量。例如,在 MNIST 和 USPS (真实 kk=10) 上,k*-means 预测 kk 分别为 10.90 和 8.00,非常接近。相比之下,其他方法如 XMeans 经常过高估计 kk (如 MNIST 上的 118.80),而 MeanShiftDBSCAN 倾向于低估 kkHDBSCANOPTICS 则在许多情况下预测了极其庞大的 kk 值,并产生了大量离群点,这在实际应用中通常是不可接受的。
    • 聚类质量: k*-means 在 MNIST 和 USPS 等数据集上,其聚类质量甚至能与已知真实 kk 值的 k-meansGMM 相媲美。这强调了其在完全参数无关的情况下达到了接近最优的性能。
  • 基线方法的局限性:
    • 过高/过低估计 kk: 大多数基线方法存在严重过高或过低估计 kk 的问题。例如,HDBSCANOPTICS 在多个数据集上预测的 kk 值高达数千,并产生大量离群点,这使得它们的聚类结果在许多情况下难以解释和使用。
    • 指标的误导性: 论文指出,在某些情况下(如 20-NG, MSRVTT 上某些基线的 NMI 较高),尽管 NMI 值看起来不错,但这些方法同时预测了极高的 kk 值。这种情况下,由于预测划分的熵 (entropy) 过高,NMI 可能会给出不可靠的结果。
    • 参数敏感性: 论文重申,虽然手动调优基线参数可能获得更好的结果,但这违背了在 kk 未知且无真实标签可用于调优的实际应用场景。

6.1.3. 与扫描 kk 策略的比较

论文还比较了 k*-means 与一种常见实践,即通过扫描一系列 kk 值并使用 BIC 准则选择最优 kkk-means 策略 (sweepkm)。

以下是原文 Table 4 的结果:

ACC ARI NMI NC Runtime (s)
MNIST sweepkm 12.86 8.17 56.01 25.00 148.15
k*means 91.26 (3.56) 84.99 (2.97) 87.44 (1.14) 10.90 (0.32) 3.38 (0.39)
USPS sweepkm 32.36 (0.81) 21.77 (0.77) 65.20 (0.40) 68.40 (3.10) 11.21 (0.73)
k*means 88.68 (0.00) 81.57 (0.00) 87.14 (0.00) 8.00 (0.00) 0.80 (0.26)
ImageNet (subset) sweepkm 8.16 (0.26) 1.18 (0.05) 7.62 (0.05) 83.20 (4.13) 19.54 (0.23)
k*means 66.18 (1.55) 46.42 (1.45) 60.20 (0.86) 6.40 (0.70) 0.94 (0.34)
Speech Commands sweepkm 32.19 (1.27) 20.10 (0.90) 62.29 (0.30) 239.50 (12.12) 951.58 (11.31)
k*means 68.73 (1.57) 48.43 (2.49) 70.22 (0.67) 26.50 (0.97) 20.98 (5.22)
20 NG sweepkm 32.75 (0.54) 17.44 (0.54) 46.84 (0.17) 107.30 (5.83) 36.61 (1.28)
k*means 42.33 (1.14) 26.08 (0.44) 46.61 (0.67) 11.20 (0.42) 2.46 (0.96)
MSRVTT sweepkm 27.50 (89.64) 12.24 (53.57) 41.36 (18.64) 91.60 (464.76) 7.33 (20.57)
k*means 44.10 (136.25) 25.75 (65.28) 38.16 (33.06) 18.10 (87.56) 2.57 (40.59)

分析:

  • 性能差距: k*-means 在所有数据集上都显著优于 sweepkm 方法,无论是在 ACC、ARI、NMI 等聚类质量指标上,还是在预测的聚类数量 kkNC 列)上。
    • sweepkm 策略倾向于选择非常高的 kk 值,通常是真实类别数的 4-5 倍。这导致其在聚类质量指标上表现不佳。
  • 运行时效率: k*-means 的运行时间也远快于 sweepkm,通常快 10 到 50 倍。这是因为 sweepkm 需要对多个 kk 值独立训练 k-means 模型到收敛,而 k*-means 采用单阶段优化。

6.1.4. 可视化示例

Figure 2: Clusters predicted by \(\\mathtt { k } ^ { * }\) means for the UMAP representations on the Speech Commands dataset, by \(\\mathtt { k } ^ { * }\) means (left) and XMeans (right). \(\\mathtt { k } ^ { * }\) means predicts 33 classes and XMeans predicts 315, vs. 36 in the annotations. 该图像是图表,展示了在Speech Commands数据集上,通过extttk exttt{k}^* means(左)和XMeans(右)预测的聚类结果。extttk exttt{k}^* means预测了33个类别,而XMeans预测了315个类别,与注释中的36个类别相比,显示了不同的聚类效果。

图 (原文 Figure 2) 展示了 k*-meansXMeans 在 Speech Commands 数据集 UMAP 降维表示上的聚类结果。k*-means 预测了 33 个类别,XMeans 预测了 315 个类别,而真实标注有 36 个类别。

分析: 这张图直观地展示了 k*-means 预测的聚类数量 (33) 更接近真实值 (36),而 XMeans 严重高估了聚类数量 (315),导致过度碎片化的聚类,使得结果难以解释和利用。

6.2. 运行时分析

论文进一步分析了 k*-means 算法在不同数据集规模下的运行时间,并与速度最快的基线方法进行比较。

Figure 3: Runtime as a function of dataset size. Each point represents the mean runtime of 10 randomly sampled subsets from the Speech Commands dataset of the given size. The line tracks windowed averages. \(\\mathtt { k } ^ { * }\) means has a similar speed to xmeans, faster than HDBSCAN, especially for larger input sizes, and slower than kmeans, DBSCAN and GMM. 该图像是图表,显示了不同聚类算法在不同数据集大小下的运行时间。每个点代表从Speech Commands数据集中随机抽样的10个子集的平均运行时间,曲线表示窗口平均值。kk^*与xmeans速度相似,比HDBSCAN快,尤其在较大输入数据时,且比kmeans、DBSCAN和GMM慢。

图 (原文 Figure 3) 展示了不同算法在 Speech Commands 数据集不同子集大小下的运行时间。每个点代表 10 个随机采样子集的平均运行时间,线条表示窗口平均值。k*-means 的速度与 XMeans 相似,比 HDBSCAN 快(尤其对于大输入),但比 k-meansDBSCANGMM 慢。

分析:

  • k-means 的速度优势: k-means 在所有数据集大小下都最快,即使对于 99,000 个样本也远低于 1 秒。这是因为它只进行固定的迭代次数,并且不需要额外的分裂/合并操作。
  • k*-means 的竞争力:
    • k*-means 的运行时间与 XMeans 相似。
    • 对于小样本量,HDBSCAN 相对高效,但其运行时间随样本量增长更快。当样本量达到 99,000 时,HDBSCAN 的运行时间是 k*-means 的 6 倍。
    • k*-meansDBSCANGMM 慢,但考虑到 k*-means 提供了参数无关性和更准确的 kk 估计,这种速度上的权衡是合理的。
  • 其他基线: Mean ShiftAffinity PropagationOPTICS 的运行时间明显更长,以至于未包含在图 3 中,这进一步凸显了 k*-means 在效率上的优势。

6.3. 消融实验/参数分析 (DBSCAN 参数敏感性)

虽然论文没有进行 k*-means 内部组件的消融实验,但其附录 A 提供了 DBSCAN 参数敏感性的分析,以此来强调参数无关算法的必要性。

Figure 4: Values of \(k\) (number of clusters) found on MNIST for different values of the DBSCAN parameters, min-pts \(\\mathbf { \\dot { X } }\) -axis) and eps (y-axis). We sweep min-pts from 140, and eps from 0.03 to 1.5 in \(5 \\%\) increments. 该图像是一个热图,展示了在 MNIST 数据集上不同 DBSCAN 参数下(min-pts 和 eps)找到的聚类数量 kk。横轴为 min-pts,范围从 1 到 36,纵轴为 eps,范围从 0.03 到 1.416。图中展示了不同参数组合对应的 kk 值。

图 (原文 Figure 4) 展示了 DBSCAN 在 MNIST 数据集上,min-pts (x轴) 和 eps (y轴) 不同取值下找到的聚类数量 kkmin-pts 范围从 1 到 40,eps 范围从 0.03 到 1.5。图中颜色深浅代表了不同的 kk 值。

分析:

  • DBSCAN 的参数敏感性: 该图直观地展示了 DBSCAN 的两个关键参数 epsmin-pts 对最终聚类数量 kk 的巨大影响。在 MNIST 数据集上,仅通过调整这两个参数,预测的 kk 值可以在 6 到超过 4000 之间大幅变化。
  • 参数调优的挑战: 真实类别数量为 10,但 DBSCAN 在不同参数组合下产生了如此大的 kk 值范围。这突出了在 kk 未知且无真实标签来指导参数调优时,依赖参数敏感算法的巨大挑战。这也正是 k*-means 试图解决的核心问题。

7. 总结与思考

7.1. 结论总结

本文提出了 k*-means,一种创新的、完全参数无关的聚类算法,旨在解决传统聚类方法需要预设聚类数量 kk 或调优其他参数的根本性限制。通过将最小描述长度原理 (MDL) 整合到 k-means 框架中,k*-means 能够通过动态的聚类分裂和合并操作,自动确定最优的聚类数量 kk*,同时优化标准的 k-means 目标。

论文提供了 k*-means 保证在有限时间内收敛的正式证明。实验结果表明,在合成数据上,k*-means 在估计真实的 kk 值方面远超现有方法,尤其是在聚类分离度高的情况下几乎能达到完美准确率。在多个真实世界的标注数据集上,k*-means 在标准的聚类质量指标(ACC、ARI、NMI)上显著优于所有不需要设置 kk 的竞争方法,并且在某些情况下甚至能与已知真实 kk 值的 k-meansGMM 竞争。此外,k*-means 的运行时间具有竞争力,并且能很好地扩展到大型数据集。

k*-means 对于那些用户对数据潜在聚类结构或合适的 kk 值存在高度不确定性的应用场景,提供了一个强有力且实用的解决方案。

7.2. 局限性与未来工作

论文作者指出了 k*-means 的以下局限性:

  • 理论最坏情况运行时间: k*-means 缺乏关于最坏情况运行时间的理论保证。虽然在实践中表现良好,但这仍然是一个理论上的限制。

  • 聚类形状假设: k*-means 假设聚类大致呈球形 (roughly spherical clusters)。这与原始 k-means 的局限性类似,而现实世界中的聚类可能具有任意形状。

    尽管存在这些局限性,作者也指出,这些批评同样适用于最广泛使用的 k-means 算法,并未阻止其普及。这暗示了 k*-means 即使存在这些局限,其在无需参数设置方面的优势仍使其具有巨大的应用潜力。论文中并未明确提出未来的工作方向,但从上述局限性可以推断:

  • 研究和开发具有非球形聚类形状适应能力的 k*-means 变体。

  • 进一步优化算法以改善其理论最坏情况运行时间,或提供更强的近似保证。

  • 探索将 MDL 原理应用于其他类型的聚类算法(如基于密度或层次聚类),以实现更广泛的参数无关性。

7.3. 个人启发与批判

7.3.1. 个人启发

  1. MDL 的强大应用: 这篇论文再次展示了最小描述长度原理 (MDL) 在模型选择和解决过拟合/欠拟合问题上的优雅和强大。将 MDL 从理论工具转化为一个具体的、可操作的聚类算法中的优化目标,是一种非常巧妙且富有成效的思路。对于需要自动选择模型复杂度的场景,MDL 提供了一个清晰且理论基础坚实的框架。
  2. 参数无关算法的价值: 论文强调了参数无关 (parameter-free) 算法在实际应用中的巨大价值。在许多真实世界的场景中,领域专家往往难以提供合适的参数,甚至没有真实标签来辅助参数调优。k*-means 这种“开箱即用”的特性,大大降低了聚类算法的使用门槛,拓宽了其应用范围。
  3. 对经典算法的创新性扩展: k*-means 并没有抛弃 k-means 这个经典算法,而是在其基础上进行了创新性扩展。通过引入“子聚类 (subclusters)”、maybe-splitmaybe-merge 等机制,它在保持 k-means 核心优势(如速度、收敛性)的同时,解决了其最大的局限性。这种对现有成熟技术的“微创新”而非“颠覆”,往往能带来更强的实用性。

7.3.2. 批判

  1. MDL 成本函数中的参数敏感性: 尽管 k*-means 号称“参数无关”,但 MDL 成本函数本身涉及浮点精度 mm (在 MDLCOST 过程中的 floatprecisionfloatcost)。论文中对 floatprecision 的描述 (-log of the minimum distance between any values in X) 似乎是一种数据驱动的自适应方法,但具体如何计算 floatcost=(max(X)min(X))/floatprecisionfloatcost = (max(X) - min(X)) / floatprecision 仍有些模糊。如果 mm 的选择对结果敏感,那么这可能是一个隐式参数,需要更深入的分析和默认值选择策略。
  2. “大致球形”聚类的限制: 论文明确指出,k*-means 假设聚类大致呈球形,这继承了 k-means 的局限性。虽然这对于许多数据集来说是一个合理的假设,但对于发现任意形状的聚类(例如 DBSCAN 擅长的),k*-means 可能表现不佳。未来的工作可以考虑如何将 MDL 原理与能够处理非球形聚类的底层机制结合起来。
  3. 计算效率的进一步优化: 尽管 k*-means 在运行时表现出色,但相比于原始 k-means 仍然慢一个数量级。对于超大规模数据集,这仍然可能是一个瓶颈。探索更高效的 maybe-splitmaybe-merge 策略,或者更快的子聚类更新方法,将是重要的研究方向。例如,是否可以采用近似最近邻搜索来加速质心分配和合并判断?
  4. 初始子质心的影响: 算法初始化时,INITSUBCENTROIDS 函数为唯一的初始聚类生成两个子质心。虽然论文提到使用 k++-means 方式,但这个初始步骤的随机性或具体策略是否会影响最终的收敛结果和效率,值得进一步探讨。
  5. 离群点的处理:DBSCAN 及其变体可以识别离群点 (outliers)。k*-means 作为一个基于质心的算法,默认情况下会将所有点分配到某个聚类中,而不明确识别离群点。在某些应用中,离群点的识别与聚类同样重要。未来的扩展可以考虑如何将离群点检测机制整合到 k*-means 中,同时保持其参数无关性。

相似论文推荐

基于向量语义检索推荐的相关论文。

暂时没有找到相似论文。