基于传播度量的分层聚类
本文研究了关于层次聚类的成本函数及其 NP 难度,提出了基于逐层递归分割的启发式方法以及基于凸松弛的近似算法,并分析了两者的逼近误差和时间复杂度,讨论了在假设条件下问题的难度。
Sep, 2016
本文介绍了一种适用于一组点之间的层次结构的简单代价函数,该函数基于这些点之间的相似性,克服了现有算法由于缺乏精确客观函数而退化的问题。作者进一步证实该方法在经典实例中表现出良好的性能,并提出了一种上行建设程序,其近似比可以证明是好的。
Oct, 2015
本文提出两种高效的分层聚类算法,针对 Dasgupta 成本函数。对于任何有明确集群结构的输入图 G,我们设计的算法在 G 的输入大小几乎为线性的时间内运行,并返回一个相对于 Dasgupta 成本函数的 O (1) 近似 HC 树。我们将我们的算法的性能与先前的最新技术在合成和真实世界的数据集上进行比较,并表明我们设计的算法在更短的运行时间内产生了相当或更好的 HC 树。
Jun, 2023
提出了一种新的代价函数,基于 Dasgupta 的代价函数,解决了旧代价函数无法度量原始相似图与分层结构一致性的问题,并提出了一个多项式时间算法进行计算。
Dec, 2018
本研究考虑采用收益目标函数的双重问题,并证明了存在一种双重算法(经过半切)的近似解,得到了广义收益问题的 0.585 近似算法,从而改进了此前由一系列早期研究导致的 0.4246 近似保证。
Jun, 2020
公平机器学习领域的关键问题是公平聚类算法的研究,特别是在现代智能系统引发了许多伦理争议的情况下。Ahmadian 等人提出了针对分层聚类的公平性研究,但他们的算法是高度理论化的。Knittel 等人提出了第一个实际的成本公平近似算法,但未能突破他们提出的多项式逼近的障碍。我们通过提出第一个真正的对数多项式逼近低成本公平分层聚类算法,极大地弥合了最好的公平聚类和普通聚类逼近之间的差距。
Nov, 2023
该论文提出了一种基于超 bolic 空间的新方法(HyperAid),用于将 tree-metrics 适应到噪声数据,并通过引入边权重来提高适应性,该方法在边缘增强树和最短距离计量表示的合成数据,以及 Zoo,Iris,Glass,分割和 SpamBase 等实际数据集上效果显著优于现有方法。
May, 2022
该研究提出了一个基于层次聚类和谱聚类算法的框架,来解决大型数据集处理的问题,该算法在小型数据子集上运行,具有较高的性能、测量复杂度和运行时复杂度。经过广泛的实验验证,该框架实际上非常具有吸引力。
Jun, 2012
本文提出了一种可扩展的聚合层次聚类方法,可以在不降低质量的前提下对数十亿个数据点进行聚类,并在公开的聚类基准测试集上实现了最先进的结果,同时还将层次聚类引入作为非参数聚类目标的近似算法。
Oct, 2020