分层聚类:目标函数和算法
提出了一种新的代价函数,基于 Dasgupta 的代价函数,解决了旧代价函数无法度量原始相似图与分层结构一致性的问题,并提出了一个多项式时间算法进行计算。
Dec, 2018
本文介绍了一种适用于一组点之间的层次结构的简单代价函数,该函数基于这些点之间的相似性,克服了现有算法由于缺乏精确客观函数而退化的问题。作者进一步证实该方法在经典实例中表现出良好的性能,并提出了一种上行建设程序,其近似比可以证明是好的。
Oct, 2015
本文研究了关于层次聚类的成本函数及其 NP 难度,提出了基于逐层递归分割的启发式方法以及基于凸松弛的近似算法,并分析了两者的逼近误差和时间复杂度,讨论了在假设条件下问题的难度。
Sep, 2016
本文提出两种高效的分层聚类算法,针对 Dasgupta 成本函数。对于任何有明确集群结构的输入图 G,我们设计的算法在 G 的输入大小几乎为线性的时间内运行,并返回一个相对于 Dasgupta 成本函数的 O (1) 近似 HC 树。我们将我们的算法的性能与先前的最新技术在合成和真实世界的数据集上进行比较,并表明我们设计的算法在更短的运行时间内产生了相当或更好的 HC 树。
Jun, 2023
本文研究了带有结构约束条件的层次聚类问题,提出了两种基于优化视角的自顶向下算法,并且通过公式化约束性正则化的方法在存在冲突先验信息的情况下得出了良好的解,同时探讨了基于差异性信息变化的目标函数的变形并进一步优化了当前技术,最后将该方法应用于实际数据集的分类学应用
May, 2018
本研究考虑采用收益目标函数的双重问题,并证明了存在一种双重算法(经过半切)的近似解,得到了广义收益问题的 0.585 近似算法,从而改进了此前由一系列早期研究导致的 0.4246 近似保证。
Jun, 2020
本文研究在传统的分类中引入公正性准则,探索公平的分层聚类算法以解决机器学习系统中的过度表达问题。我们为多种自然目标提供了简单高效的算法,能够找到一个合理的公正的分层聚类,同时只会带来微不足道的目标损失。
Jun, 2020
该研究提出了一种名为 HypHC 的方法,将传统的基于启发式算法的相似性层次聚类问题转化为一个离散优化问题,并通过连续松弛技术获得全局最优解,该方法通过超蜂窝嵌入实现了离散树到连续表示的映射,并采用解码算法通过叶节点嵌入到树状图的映射,实现了连续优化用于搜索离散二进制树的空间。
Oct, 2020