ICMLJun, 2021

近线性时间的分层聚合图聚类

PDF
TL;DR本文提出了一种层次凝聚图聚类算法框架并给出了完整的精确算法和近似算法，可以用于加权图的聚类问题，并通过用 $k$-NN 方法将点集转化为加权图，实现对点集的快速聚类。
hierarchical agglomerative clusteringalgorithmlinkage measuresweighted graphpoint datasets
发现论文，激发创造
  • 针对良好聚类图的近似最优层次聚类

    本文提出两种高效的分层聚类算法，针对 Dasgupta 成本函数。对于任何有明确集群结构的输入图 G，我们设计的算法在 G 的输入大小几乎为线性的时间内运行，并返回一个相对于 Dasgupta 成本函数的 O (1) 近似 HC 树。我们将我们的算法的性能与先前的最新技术在合成和真实世界的数据集上进行比较，并表明我们设计的算法在更短的运行时间内产生了相当或更好的 HC 树。

    Jun, 2023

  • 分层聚类优于平均链接

    本文研究了层次聚类问题，尤其是针对与平均链接聚类相关的性能和基于相似性和相异性的目标提出了新的算法，可以获得更好的结果。

    Aug, 2018

  • 层次聚类的数据聚合

    使用 BETULA 数据聚合算法进行数据聚类，使得在资源受限的系统上使用层次凝聚聚类方法成为可能，仅在聚类质量上有轻微损失，并且允许对非常大的数据集进行探索性数据分析。

    Sep, 2023

  • Ward 方法分析

    本文研究了 Ward 方法在分层 k 均值问题中的应用，通过对完全链接的算法进行分析，发现当最优 k 聚类具有良好分离性时，Ward 方法可以计算出 k - 均值目标函数的 2 - 近似解，并证明了当最优聚类满足平衡条件时，Ward 方法完全恢复最优解，并且我们证明了一维数据集的 Ward 聚类可以实现 O (1) 的近似解。

    Jul, 2019

  • 基于层次凝聚聚类的公平算法

    本文提出一种对分层聚类算法 (HAC) 进行公平性约束的方法，适用于任何自然的聚类公平措施和多个受保护群体，并在多个真实世界 UCI 数据集上进行了广泛的实验。

    May, 2020

  • 可扩展的分层凝聚聚类

    本文提出了一种可扩展的聚合层次聚类方法，可以在不降低质量的前提下对数十亿个数据点进行聚类，并在公开的聚类基准测试集上实现了最先进的结果，同时还将层次聚类引入作为非参数聚类目标的近似算法。

    Oct, 2020

  • 有向图中的聚合聚类：图度链接

    本研究提出了一种基于图的汇聚算法用于高维数据聚类，该算法通过研究图论中的两个基本概念（入度和出度）在聚类中的不同作用，定义了聚类的亲和度，该算法在图像聚类和物体匹配两个计算机视觉问题上均表现出优于最先进技术的效果。

    Aug, 2012

  • 高效的层次聚类主动算法

    该研究提出了一个基于层次聚类和谱聚类算法的框架，来解决大型数据集处理的问题，该算法在小型数据子集上运行，具有较高的性能、测量复杂度和运行时复杂度。经过广泛的实验验证，该框架实际上非常具有吸引力。

    Jun, 2012

  • 用于非对称网络的层次化准聚类方法

    本文提出了分层准聚类方法，用于不对称网络，保留输入数据的不对称性，该输出结构等价于有限准超度量空间并用美国国内人口迁移为例说明准聚类分析的价值。

    Apr, 2014

  • 单连接聚类在 l_p 距离下的大规模并行算法和难度

    介绍了用 Apache Spark 实现的高效的大规模并行算法来计算单链接聚类问题，该算法在 Hamming 距离，L1，L2 和 L∞ 距离下均能实现单轮 MPC，和（除了 Hamming 距离的精确算法外）都能实现（1+ε）- 近似，同时证明了在标准 MPC 难度假设下，o（log n）轮算法的常数近似难度结果。

    Oct, 2017