ICMLJun, 2023

针对良好聚类图的近似最优层次聚类

PDF
TL;DR本文提出两种高效的分层聚类算法，针对 Dasgupta 成本函数。对于任何有明确集群结构的输入图 G，我们设计的算法在 G 的输入大小几乎为线性的时间内运行，并返回一个相对于 Dasgupta 成本函数的 O (1) 近似 HC 树。我们将我们的算法的性能与先前的最新技术在合成和真实世界的数据集上进行比较，并表明我们设计的算法在更短的运行时间内产生了相当或更好的 HC 树。
hierarchical clusteringdasgupta's cost functioninput graphapproximate hc treerunning time
发现论文，激发创造
  • 一种改进的层次聚类树代价函数

    提出了一种新的代价函数，基于 Dasgupta 的代价函数，解决了旧代价函数无法度量原始相似图与分层结构一致性的问题，并提出了一个多项式时间算法进行计算。

    Dec, 2018

  • 从树到连续嵌入再回归：双曲线分层聚类

    该研究提出了一种名为 HypHC 的方法，将传统的基于启发式算法的相似性层次聚类问题转化为一个离散优化问题，并通过连续松弛技术获得全局最优解，该方法通过超蜂窝嵌入实现了离散树到连续表示的映射，并采用解码算法通过叶节点嵌入到树状图的映射，实现了连续优化用于搜索离散二进制树的空间。

    Oct, 2020

  • 分层聚类：目标函数和算法

    本篇论文研究层次聚类的优化问题，通过提出一些可靠的任务目标函数并对实际算法进行分析，提供了更优的算法以及性能表现。

    Apr, 2017

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

    本文提出了一种层次凝聚图聚类算法框架并给出了完整的精确算法和近似算法，可以用于加权图的聚类问题，并通过用 $k$-NN 方法将点集转化为加权图，实现对点集的快速聚类。

    Jun, 2021

  • 分层聚类：0.585 收益近似

    本研究考虑采用收益目标函数的双重问题，并证明了存在一种双重算法（经过半切）的近似解，得到了广义收益问题的 0.585 近似算法，从而改进了此前由一系列早期研究导致的 0.4246 近似保证。

    Jun, 2020

  • 稀疏切割和扩散度量下的近似分层聚类

    本文研究了关于层次聚类的成本函数及其 NP 难度，提出了基于逐层递归分割的启发式方法以及基于凸松弛的近似算法，并分析了两者的逼近误差和时间复杂度，讨论了在假设条件下问题的难度。

    Sep, 2016

  • 公平的多项式对数逼近低成本层次聚类

    公平机器学习领域的关键问题是公平聚类算法的研究，特别是在现代智能系统引发了许多伦理争议的情况下。Ahmadian 等人提出了针对分层聚类的公平性研究，但他们的算法是高度理论化的。Knittel 等人提出了第一个实际的成本公平近似算法，但未能突破他们提出的多项式逼近的障碍。我们通过提出第一个真正的对数多项式逼近低成本公平分层聚类算法，极大地弥合了最好的公平聚类和普通聚类逼近之间的差距。

    Nov, 2023

  • 一种基于相似性层次聚类的代价函数

    本文介绍了一种适用于一组点之间的层次结构的简单代价函数，该函数基于这些点之间的相似性，克服了现有算法由于缺乏精确客观函数而退化的问题。作者进一步证实该方法在经典实例中表现出良好的性能，并提出了一种上行建设程序，其近似比可以证明是好的。

    Oct, 2015

  • 基于传播度量的分层聚类

    研究层次聚类的成本函数及其近似算法，提出了一种线性规划算法及其基于球增长的 LP 松弛算法，用于获得层次聚类。

    Oct, 2016

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

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

    Jun, 2012