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

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

news 2025/5/14 5:38:02

摘要

近年来，聚类与深度学习的结合受到了广泛关注。无监督神经网络，如自编码器，能够自主学习数据集中的关键结构。这一思想可以与聚类目标结合，实现对相关特征的自动学习。然而，这类方法通常基于 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：