基于图像分割的绘图数据聚类方法及其优势与性能

基于图像分割的绘图数据聚类Tarek Naous1，Srinjay Sarkar2，Abubakar Abid3，James Zou41贝鲁特美国大学，2VinAI研究，3拥抱脸，4斯坦福大学tnn11@aub.edu.lb，v. vinai.io，abubakar@hf.co，jamesz@stanford.edu摘要聚类是一种在未标记数据中检测模式的流行方法。现有的聚类方法通常将数据集中的样本视为度量空间中的点，并计算距离以将相似的点分组在一起。在本文中，我们提出了一种在二维空间中聚类点的不同方法，灵感来自人类如何聚类数据：通过训练神经网络对标绘数据执行实例分段。我们的方法，可视化聚类，有几个优势，传统的聚类算法：它比大多数现有的聚类算法快得多（使得它适合于非常大的数据集），它与人类对聚类的直觉非常一致，并且它是无超参数的（尽管可以引入具有超参数的附加步骤以用于对算法的更多控制）。我们描述了该方法，并将其与其他10种聚类方法的合成数据进行比较，以说明其优点和缺点。然后，我们展示了我们的方法可以扩展到更高维的数据，并说明其在现实世界中的数据的性能。我们的Visual Clustering实现作为Python包公开提供，可以在几行代码中安装和使用任何数据集1。提供了一个关于合成数据集的演示2.1. 介绍许多应用需要将数据集中未标记的样本分类为不相交的聚类，使得同一聚类内的样本相似，而不同聚类中的样本有意义地不同。已经开发了许多这样的聚类算法，以满足图像处理[10]、生物医学[13]和空间数据[3]等领域应用的不同需求。最常用的聚类算法，如K-means聚类[5]、高斯混合聚类[4]和DBSCAN [12]，将样本视为度量（通常为欧几里得）空间中的点，并基于以下条件将点分组在一起：1https://github.com/tareknaous/visual-clustering2https://huggingface.co/spaces/CVPR/visual-clustering网站与其他点或计算样本的距离。例如，K均值聚类算法识别度量空间中的最佳质心，数据集中所有样本的距离最小化。高斯混合算法假设数据是从高斯混合中采样的，并在数据中产生聚类以最大化可能性，这在数据点接近高斯分布的中心时发生。 DBSCAN是一种基于密度的聚类算法，它不假设给定数据集的聚类数量，而是考虑属于同一聚类的一组点，如果在选定点的邻域中有一定数量的点通过递归地考虑到所有其他点的距离来扩展聚类由于这些算法中的大多数涉及测量点之间的距离，因此它们对于具有数百万或数十亿样本的大型数据集的扩展性很差。在我们的工作中，我们介绍了一种完全不同的聚类算法，设计用于二维大数据集。 我们的方法，我们称之为可视化聚类，灵感来自人类如何聚类数据：我们不是计算距离，而是根据数据集中大区域的形状将数据点分割成簇。我们通过训练神经网络对绘制的数据进行实例分割来模拟这个过程我们的方法与传统的聚类算法相比有几个优点：（1）由于al-tax m的主要步骤是从一个神经网络运行预测，因此它比大多数现有的聚类算法快得多，并且可以轻松扩展到具有数百万或数十亿样本的数据集。（2）正如我们在许多类型的数据集上所展示的那样，它与人类对聚类的直觉非常一致（3）核心算法是超参数自由的，尽管我们建议可以引入超参数的附加步骤以用于对算法的更多控制聚类在文献中已被应用于解决深度学习和计算机视觉中的各种问题，例如无监督图像分割[14]，面部标志检测[9]和图像分组[1，2]。然而，没有先前的工作已经利用训练的神经网络模型的快速推理时间来执行聚类。发展中图像去噪维度减少最大过滤1密谋2二元分割U-Net2-D输入矩阵预测掩码3例如分离连接-分量分析+流域4簇指派标签图群集数据集×∈数据集图1.可视化聚类算法的图表视图。虚线表示可选步骤。该算法首先创建数据集的矩阵表示，该数据集用作二进制分割模型（U-Net）的输入连通分量分析和分水岭被应用到预测的二进制掩码中，以分离图像中的不同实例，从而产生最终执行聚类分配的标签图在文献中已经研究了可以取代经典算法的深度学习模型，用于各种问题，例如排序[15]，解决混合整数问题[8]，甚至取代数据管理系统中的索引结构[7]。此外，有几种基于深度学习的方法被提出用于聚类[6]。然而，这些方法依赖于通过梯度下降的两个损失的优化，需要聚类的任何数据集，这需要大量的计算时间。相比之下，我们的方法只需要一个推理运行（即，一次“for-ward通过”模型），这明显更快。此外，这些方法主要是针对图像聚类的虽然迁移学习可以应用于提取潜在特征并在这种方法中绕过初始优化和训练过程，但这只能在特征之间存在共同相关结构的数据上完成，例如图像或文本数据。对于一般的表格数据，特征之间的这种相关性结构是未知的，并且在数据集之间变化因此，如果将这些基于深度学习的方法应用于这样的禁忌数据集，它们仍然需要非常大的计算时间。另一方面，我们提出的方法是第一个提供基于深度学习的分割模型的可视化方法，该模型以监督的方式训练，以在数值数据集（可以是表格数据或文本或图像等数据的嵌入）上执行聚类，这具有计算时间优势，而无论数据类型2. 方法2.1. 核心算法我们提出的可视化聚类算法如图1所示，由四个主要步骤组成，我们将在本节中描述。考虑数据集X∈Rm×2，我们我喜欢集群。我们从绘图步骤开始，其中X以二维矩阵形式表示，由I（X）表示。这是通过首先将两个特征的值线性移位为[0，256]，然后根据数据集中的每个样本的坐标，用值1填充零初始化的256256矩阵来如果数据集是高维的，我们应用主成分分析（PCA），并使用前两个主成分作为特征。然后将可以被可视化为图像的矩阵作为输入馈送到二元分割的第二步骤，其中使用预先训练的二元分割模型。我们采用U-Net架构[11]进行二进制分割，并在绘制的数据集的图像上以监督的方式对其进行训练，这些数据集是合成生成的，以及它们的二进制掩码。 U-Net模型预测了一个pixel-l维二进制掩码M（I（X））。通过训练的U-Net模型预测的二进制掩码包含关于聚类区域所在位置的信息。然而，二进制掩码本身并不指示图像中存在多少簇因此，我们的方法的下一步是分离二进制掩码中存在的实例（或集群）要做到这一点，我们应用连接的成分分析预测的面具，然后是一个实例分离的Watershed变换。这导致标签映射L，其中属于相同聚类的像素被分配相同的标签值。我们方法的最后一步是聚类分配，我们根据数据集中每个样本在标签映射中的位置为其分配一个聚类标签。2.2. 训练二进制分割模型为了训练用于二进制分割的U-Net模型，我们生成了1,000个斑点状集群的合成数据集。每个数值数据集用于创建数据样本，以训练二进制分割模型，其中输入是标绘的∞∞ ∞∞∞ ∞ ∞∞∞ ∞∞∞ ∞ ∞ ∞∞∞ ∞ ∞ ∞∞数据集和标签是分割图，其中每个聚类都有其片段。为了自动生成每个数据集的标签（分割图），我们计算了数据集中每个聚类的凸包。然后使用凸包来形成二进制掩码标签。当两个集群的外壳如果交叉部分低于阈值，则减去外壳以分离二进制掩码中的聚类。U-Net模型实现了88.7%的测试集Intersection-Over-Union（IOU）虽然只有斑点形状的集群被认为是在虽然我们的算法中使用的分割模型只在斑点形状的簇上训练，但是它可以成功地分割簇，而与它们的形状无关。在具有更复杂模式的数据集上，例如圆形或月亮形聚类，与K均值，亲和传播或高斯混合的结果相比，我们的算法提供了更符合人类直觉的聚类结果。虽然DBSCAN或谱聚类等其他算法与人类直觉一致，但它们的计算时间很长，无法有效地用于对大型数据集进行聚类。训练过程中，学习的模型可以分割clus-如第3节的结果所示，它们与形状无关。2.3. 图像去噪中不可分簇的处理所开发的二进制分割模型分割的方式，识别断开的集群的图像。如果两个或多个聚类相交，则模型可能将这些聚类合并为一个。这一点尤其适用于真实世界的数据集，其中集群更有可能是不可分割的。为了避免这个问题，我们引入了一个可选的图像去噪预处理步骤，以过滤掉图像中的低密度区域，并强调高密度区域。这有助于区分似乎由稀疏数据点连接的聚类区域我们专门通过中值滤波器对图像进行去噪2.4. 使用最大过滤处理未指定的点当在算法的最后一步中为数据集中的每个点分配标签时，许多点将落在聚类区域外部但靠近聚类区域的区域中。这些可能是偏离聚类中的大多数点所处位置的点，因此将被二元分割模型忽略。未分配的点也可以是在图像去噪步骤中过滤掉的低密度区域（如果使用的话）为了解决这个问题，我们在标签地图上执行一个可选的最大过滤操作，以增加每个聚类的面积，帮助覆盖附近未分配的点。我们希望增加聚类区域的程度由最大过滤器的大小控制，其中较大的过滤器大小将导致较大的聚类区域。3. 结果3.1. 合成数据集上的聚类性能及计算时间比较我们的可视化聚类方法的性能与图2中各种聚类形状的合成数据集上的多个经典聚类算法进行了比较。Al-数量的样本算法10K 50K 100K 500K 1M 2M视觉聚类0.292 0.571 0.909 3.686 7.222 14.096K均值0.155 0.541 1.103 5.470 9.519 18.956亲和力传播175.35平均位移3.482 101.82光谱聚类0.0520.5090.7967.45553.559美元病房1.994 27.965 93.564集聚集群1.177 12.154 39.886DBSCAN0.0930.3570.8377.60420.00952.648光学16.515BIRCH 1.298 7.390 14.320高斯混合0.089 0.358 0.726 3.047 5.949 11.962表1.对于越来越多的样本，可视化聚类与经典聚类算法的端到端计算时间（以秒为单位）比较表示计算时间超过3分钟，因此未包括在内。可视化聚类算法与高斯混合算法一样快，在大数据集上比所有其他经典算法都要快。分割模型、实例分离算法和过滤技术的计算时间与数据集中的样本数量无关。由于我们的算法是一个完全基于视觉的方法，它提供了一个很大的计算时间优势。然而，在我们的算法中的绘图和聚类分配步骤的计算时间随着样本的数量线性增加。在表1中，我们显示了视觉聚类（包括绘图时间）和经典算法之间的端到端计算时间比较，样本数量不断增加。视觉聚类实现了非常快的计算时间，几乎与高斯混合算法相同，高斯混合算法是测试中最快的经典算法，并且比K-Means聚类更快。视觉聚类在计算时间方面也优于所有其他的经典算法。因此，视觉聚类实现了缓慢的经典算法之间的妥协，如亲和传播，可以以人类直观的方式聚类复杂的模式，同时具有非常快的计算时间，如高斯混合或K均值。3.2. 真实世界数据集我们评估了三个真实世界的数据集从UCI存储库，其中一个∞ ∞∞图2.在具有多种聚类形状的合成数据集上比较视觉聚类与经典聚类算法。右下角的数字表示地面实况标签和预测标签之间的调整后的互信息分数高于0.95的分数以粗体突出显示Visual Clustering和DBSCAN是仅有的两种在所有合成数据集上实现与地面真实标记近乎完美匹配的算法是二维的，另外两个是更高维度的。这些数据集上的聚类结果如图3所示。在现实世界的数据集中，聚类更有可能在视觉上不可分离。对于前两个数据集（a和b），图像去噪步骤显示出其在突出数据集中的高密度区域和消除低密度区域方面的有效性。这有助于二进制分割模型捕获更多的集群，因为它们变得视觉上可分离。属于低密度区域的大多数点然后通过在聚类分配之前对标签图执行最大过滤来重新捕获。在那些真实世界的数据集中还注意到存在离群值，离群值是距离主聚类非常远的一些稀疏点，并且通常期望不被认为属于任何聚类。虽然经典方法难以捕获这样的离群值，但是观察到可视化聚类在这方面表现良好，并且避免了为这样的点形成聚类，这在需要聚类同时试图避免离群值时提供了第三个数据集（数据集c）为可视化聚类提供了一个更有说服力的案例，其中图中的大多数点都通过相同的模式连接。虽然在视觉上，将去噪后更清楚地示出的三条主线识别为三个不同的线索是直观的，因此，算法将它们视为一个集群。这是因为可视化聚类依赖于二进制分割和连接组件分析，这使得很难识别连接模式上的几个聚类，这可能是或可能不是基于用户的领域专业知识的理想输出。在这方面，我们未来的工作将集中在改进视觉聚类算法，使分割的方式，提供了一种能力，在连接模式上放置多个集群的进一步灵活性4. 结论我们介绍了视觉聚类，一个快速聚类算法的基础上训练的图像分割Visual Clustering的灵感来自于人类如何对数据进行聚类：通过在2D中绘制数据集并识别相似点的组。我们在真实和合成数据集上的实验以及与十种经典聚类算法的比较表明，Visual Clustering实现了符合人类直觉的聚类结果，这是由非常高的调整后的互信息分数突出显示的aInput dataset去噪输入，其中x2= 10可视化聚类结果，其中，n= 1可视化聚类结果，其中x2= 70平均值聚类结果，其中k= 6b使用PCA去噪输入，其中Σ= 5可视化聚类结果，其中，n= 1Visual Clustering结果，其中x2= 60平均值聚类结果，其中k= 10使用PCA去噪输入，其中Σ= 10可视化聚类结果，其中，n= 1Visual Clustering结果，其中x2= 20**= 3时的均值聚类结果图3.可视化聚类算法在三个真实世界数据集上的结果与k均值聚类的比较。D代表中值滤波器的核大小。 M代表最大滤波器的内核大小。 数据集（a）由城市道路事故坐标组成。 它包含2个特征和360，177个样本。数据集（b）包括用于室内定位的地磁场数据。它包含13个特征和58，374个样本。数据集（c）由单个家庭电力消耗数据组成。它包含7个特征和2，075，259个样本。使用PCA将数据集（b）和（c）减少到二维。我们注意到，我们不能得出结论，哪个算法提供了最好的聚类，因为在这些数据集中没有可用的地面真值标签。引用[1] Mathilde Caron，Piotr Bojanowski，Armand Joulin，andMatthijs Douze.用于视觉特征的无监督学习的深度聚类。在欧洲计算机视觉会议论文集（ECCV）中，第132-149页，2018年。1[2] 常建龙，王凌峰，孟高峰，向世明，潘春红。深度自适应图像聚类。在IEEE计算机视觉国际会议论文集，第5879-5887页，2017年。1[3] 张文，张文，等.一种基于密度的聚类算法.北京：科学出版社，2000.在KDD，第96卷，第226-231页1[4] 辛金 和韩家 伟。期望 最大化 聚类 ，第 382-383页。Springer US，Boston，MA，2010. 1[5] 辛金和韩家伟。K-Means聚类，第695- 697页。SpringerUS，Boston，MA，2017. 1[6] Md Rezaul Karim，Oya Beyan ，Rezle Zappa，Ivan GCosta，Dietrich Rebholz-Schuhmann，Michael Cochez和Ste-我是戴克的粉丝基于深度学习的生物信息学聚类方法。生物信息学简报，22（1）：393-415，2021。2[7] Tim Kraska，Alex Beutel，Ed H Chi，Jeffrey Dean，andNeok- lis Polyzotis.学习索引结构的情况。在2018年数据管理国际会议的开幕式上，第489-504页，2018年。2[8] Vinod Nair，Sergey Bartunov，Felix Gimeno，Ingrid vonGlehn ， PawelLicenki ， IvanLobov ， BrendanO'Donoghue，NicolasSonnerat，ChristianTjandraatmadja，Pengming Wang，et al.用神经网络求解混 合 整 数 规 划 。 arXiv 预 印 本 arXiv ： 2012.13349 ，2020。2[9] Xuan-Bac Nguyen、Duc Toan Bui、Chi Nhan Duong、Tien D Bui 和 Khoa Luu 。 Closformer ： 一 种 基 于Transformer的聚类方法，用于无监督的大规模人脸和视觉地标识别。在IEEE/CVF计算机视觉和模式识别会议论文集，第10847-10856页1[10] Thrasyvoulos N Pappas和Niedes S Jayant。一种自适应聚类图像分割算法。国际C声学、语音和信号处理会议，第1667-1670页。IEEE，1989年。1[11] Olaf Ronneberger，Philipp Fischer，and Thomas Brox. U-net：用于生物医学图像分割的卷积网络。医学图像计算和计算机辅助干预国际会议，第234施普林格，2015年。2[12] ErichSchubert，Jo ？rgSander ，MartinEster ，HansPeterKriegel ， and Xiaowei Xu.Dbscan revisited ，revisited ： 为 什 么 以 及 如 何 使 用 dbscan 。 ACMTransactions on Database Systems（TODS），42（3）：1-21，2017。1[13] 徐瑞和唐纳德·温斯奇。生物医学研究中的聚类算法：审查. 生物医学工程，IEEE Reviews in，3：120- 154，02 2010. 1[14] 周磊和魏宇峰。DIC：用于无监督图像分割的深度图像聚类。IEEE Access，8：34481-34491，2020。1[15] Xiaoke Zhu，Taining Cheng，Qi Zhang，Ling Liu，JingHe，Shaowen Yao，and Wei Zhou. NN-排序：基于神经网 络 的 数 据 分 布 感 知 排 序 。 arXiv 预 印 本 arXiv ：1907.08817，2019。2