当前位置：首页 > news >正文

【论文阅读】Dip-based Deep Embedded Clustering with k-Estimation

news 来源：原创 2025/7/5 19:17:51

摘要

近年来，聚类与深度学习的结合受到了广泛关注。无监督神经网络，如自编码器，能够自主学习数据集中的关键结构。这一思想可以与聚类目标结合，实现对相关特征的自动学习。然而，这类方法通常基于 k-means 框架，因此继承了诸如聚类呈球形分布等各种假设。另一项常见假设（即使在非 k-means 方法中也存在）是需要预先知道聚类的数量。

本文提出了一种新颖的聚类算法 DipDECK，它能够在优化基于深度学习的聚类目标的同时估计聚类数。此外，方法无需假设聚类仅为球形结构，即可处理复杂的数据集。该算法的核心思路是：在自编码器的嵌入空间中大幅度高估聚类数，并基于 Hartigan 的 Dip 检验（一种用于判断单峰性的统计检验）分析生成的微聚类，从而确定哪些聚类应当合并。

通过大量实验证明了该方法的多种优势：
(1) 在同时学习有利于聚类的表示和聚类数量的情况下，能够取得具有竞争力的效果；
(2) 该方法对参数不敏感，具有稳定的性能表现，并支持更灵活的聚类形状；
(3) 在聚类数量估计方面，DipDECK方法优于相关的现有方法。

引言

在大量未标注数据中发现模式是数据挖掘研究的重要分支之一，其目标是将数据划分为若干组相似的数据点。然而在实际应用中，往往无法事先得知数据中有多少个聚类。

传统聚类算法中已有诸多方法尝试解决这一问题。其中许多方法基于 k-means 框架，例如 X-means [23] 和 Dip-means [16]。也有一些方法，如 PG-Means [8]，采用基于期望最大化（EM）的方法，从而在聚类形状上具有更高的灵活性。但这些方法通常会自动继承“高斯分布聚类”的假设。虽然这种假设对部分数据集有效，但对其他数据集则过于严格，从而导致聚类结果不理想。

当然，也存在一些可以自动确定聚类数且不依赖高斯假设的聚类方法。例如著名的基于密度的 DBSCAN [7] 方法，以及一些基于谱聚类的变种 [31]。这些方法不仅可以估计聚类数，还支持任意形状的聚类。但它们以更复杂的参数（如邻域范围、邻居数量）取代了“聚类数量”这一直观参数。最终，聚类数量主要由这些复杂参数所控制，因此实质上只是将一个参数替换为了另外一些参数。

然而，上述所有方法在处理现代高维大数据（如图像、视频和文本）时往往效果不佳。即使运行时间和内存问题可以通过高性能实现来缓解，这些方法依然受到“维度灾难”的制约，因其多数依赖欧几里得距离。面对这类数据集，近年来的趋势是采用深度学习方法进行聚类。

在这类方法中，通常使用自编码器学习有利于聚类的低维表示，以降低维度并提升聚类效率，从而缓解高维带来的问题。因此，理想的方法应能够与深度学习聚类算法集成，在兼容深度学习优势的基础上，自动估计聚类数量。

截至目前，据作者所知，还没有一种基于深度学习的方法能够在聚类的同时估计聚类数量。现有策略仍依赖于传统聚类方法，而这些方法在高维或大规模数据集上扩展性较差。

为了解决上述问题，本文提出了一种新算法：DipDECK（Dip-based Deep Embedded Clustering with k-estimation）。该方法能够同时优化聚类数量 𝑘、聚类分配和数据嵌入表示。本文的做法是在自编码器的嵌入空间中先大幅高估聚类数量（记作 𝑘init），再利用 Hartigan 的 Dip 检验（该检验用于一维样本的多峰性判断）来识别具有结构相似性的聚类进行合并。Dip 检验输出的 Dip 值可转换为一个 p 值，表示样本为单峰分布的概率。本文设计了一种聚类损失函数，促使自编码器将 Dip p 值较高的聚类向同一方向靠拢，形成更紧凑的聚类结构，从而支持将多个子聚类合并为一个完整聚类。本文引入的唯一假设是 𝑘 ≤ 𝑘init，这相比于预设固定聚类数的传统方法是一种显著的放宽。图 1 展示了 DipDECK 背后的基本思想：假设图中点为某高维数据集经过自编码器降维后的二维嵌入表示，可通过 Dip 检验识别哪些子聚类结构上相似并进行合并，同时也支持识别非凸形状的聚类。

本文的贡献如下：

提出了一种新颖的深度聚类方法，无需预先指定聚类数量 𝑘。即便在缺乏该信息的情况下，本文的方法在多个基准数据集上也能取得具有竞争力的聚类效果（如 NMI 指标）。
虽然本文的方法在某种程度上引入了 k-means 风格的中心损失项，但在聚类形状方面表现出更大的灵活性。
本文首次将 Dip 检验（用于判断一维样本单峰性）引入深度学习聚类方法，以量化数据集中的结构信息。
本文在多个数据集上聚类数估计表现优越，因此该方法也可作为独立工具用于估计聚类数，再与其他聚类方法配合使用。

方法

DipDECK（Dip-based Deep Embedded Clustering with 𝑘-estimation）方法利用自编码器（autoencoder）在嵌入空间中同时实现聚类数量的估计与聚类分配的优化。本文中所使用的所有符号已在表1中列出。

自编码器是一种由编码器（encoder）和解码器（decoder）组成的无监督神经网络结构。编码器负责将输入数据映射到一个潜在的、通常是低维的空间中；解码器则尝试将嵌入后的数据重构回原始输入。通过最小化重构损失 Lrec，自编码器可以学习嵌入空间的结构特征。该损失通常采用均方误差（Mean Squared Error）计算，对于一个小批量样本 B，其公式如下：

其中，enc(⋅)表示编码器的输出，dec(⋅) 表示解码器的输出，∥⋅∥表示平方欧氏距离。图2展示了该自编码器结构。

总体而言，该方法依赖于两个主要参数：

初始聚类数 kinit，其应远大于实际的预期聚类数量；
Dip-p值阈值 T，用于判断两个聚类是否应合并。

在本文的实验中，采用了一个简单的前馈神经网络架构，但在实际应用中也可替换为其他领域相关的网络结构。接下来，在嵌入空间中执行 k-means 聚类（使用 kinit作为聚类数），以获得初始的聚类中心和聚类分配。由于作者希望在嵌入空间中同时优化数据表示和聚类中心的位置，因此本文选取离 k-means 初始中心最近的样本点作为新的聚类中心，具体计算如下：

其中，μikm是 k-means 聚类得到的第 i个初始聚类中心。

随后，对嵌入空间中的每对聚类（i,j）应用 Dip 检验以获取它们之间的 Dip 值。由于 Dip 检验的输入必须是一维数据，通过点积将每个样本投影到连接对应两个聚类中心 μi和 μj的直线上，计算如下：

生成的这一维数据集 Ci,j1d可用于计算 Dip 值，进而得到相应的 Dip-p 值。图1形象地展示了这一思想的实现过程。

Dip 检验在某些情况下可能会将两个实际相距较远的聚类识别为单峰分布（unimodal），尤其当它们的样本数量差异较大时。 为了解决这个问题，作者额外计算了一个 第二 Dip 值：该值仅考虑大聚类中靠近小聚类中心的样本点与小聚类的全部样本点。最终，取两个 Dip 值中较大的一个（即 Dip-p 值较小的一个）作为最终判断依据。这样可以确保两个聚类之间的过渡也是单峰的。

此外，作者规定每个聚类与自身之间的 Dip 值设为 0，因此对应的 Dip-p 值为 1。由于 pi,j=pj,i，可以构造一个对称的 Dip-p 值矩阵 P：

然后，矩阵 P 进行行归一化：将第 i行的每个元素除以该行的总和，得到矩阵 P^。

接下来，开始以 mini-batch 方式优化自编码器。在每个批次 B中，首先对所有样本及聚类中心进行编码，然后使用 k-means 方式更新聚类分配：每个样本被分配到距离其最近的中心。

提出了一个新的聚类目标函数 Lclu：

其中，cx是样本 x所属的聚类标签，std(⋅)和 mean(⋅)分别表示标准差和均值。集合 DC表示所有聚类中心之间的欧氏距离：

对 P^ 的行归一化保证了式 (3) 内部求和是一个仿射和，即对于一个固定的样本 x，所有权重 P^cx,i的和为 1。

其背后的直觉是：神经网络应当最强烈地将样本 enc(x) 推向它所分配的聚类中心（因为 Dip-p 值最大为 1），但同时也应适度地将其推向其他与其当前聚类形成单峰分布的中心 μi。由于对应的 P^cx,i较大，网络会倾向于缩小它与这些中心之间的距离，以减少损失。

本文对 Lclu中的距离进行归一化，使用 mean(DC)防止自编码器简单通过缩小嵌入空间的尺度来减小损失。然而，如果网络将个别聚类推得很远，mean(DC)仍可能保持较大。为防止这一点，又引入了 std(DC)项。

最后，使用公式 (1) 计算重构损失 Lrec，并将其与聚类损失相加，定义最终的 DipDECK 损失函数：

每个训练周期结束后，将每个嵌入点重新分配到其最近的聚类中心，以适应自编码器最新的嵌入结构。同时更新聚类中心，此次更新不同于式 (2)，不再使用 k-means 中心，而是改用嵌入中心的平均值最近的点作为新的中心：

之后，更新 Dip-p 值矩阵 P 和 P^，并启动聚类合并过程。

聚类合并过程（Merging Process）

为合并两个聚类，首先检查 Dip-p 值矩阵 P 中的最大 Dip-p 值是否大于指定的阈值 T。如果是，则将聚类数量减少一个，并将产生该最大 Dip-p 值的两个聚类 i 和 j 合并。

具体而言，为这两个聚类中的所有样本分配相同的标签，并通过以下方式创建一个新的聚类中心：选择最接近旧两个中心加权平均位置的样本点作为新的中心：

有了新的聚类中心后，即可更新 Dip-p 值矩阵 P 和归一化矩阵 P^。然后，再次检查 P 中的最大 Dip-p 值是否仍大于阈值。如果满足条件，则重复合并过程；如果不再满足，则重置训练轮次（epoch）计数器，并重新开始自编码器的优化过程。

注意：在合并之后的第一个训练轮次中，不会更新批次的标签，以让自编码器有时间适应新的聚类结构，并压缩由于合并而占据较大空间的聚类。

算法 1 展示了整个 DipDECK 聚类流程。

图 3 展示了该流程在一个三维数据集上的应用示例。该数据集中包含四个真实聚类：两个方向任意的“月牙形”聚类，以及两个方向任意的拉长高斯聚类。尽管该数据集在无需自编码器的情况下（例如通过谱聚类）也可能被成功聚类，但它是一个很好的示例，可用于可视化二维嵌入空间中我们的聚类流程。

摘要

引言

方法

聚类合并过程（Merging Process）

实验

相关文章：