ICMLNov, 2021

通过强三元闭包标记的相关聚类：快速近似算法和实用下界

PDF
TL;DR本研究提出了更快的近似算法，避免了其最佳逼近算法所依赖的不切实际的线性规划放宽，为两个经过充分研究的特殊情况 —— 聚簇编辑和聚簇删除提供了更快、更实用、更高效的线性规划算法及极具可扩展性的组合技术，包括聚簇删除的第一个组合逼近算法，实际应用中，我们的算法产生了近乎与质量最佳算法相匹配的近似解，同时适用于数量级更大的问题。
correlation clusteringapproximation algorithmslinear programmingcluster editingcluster deletion
发现论文，激发创造
  • 参数化图聚类和边标记的更快逼近算法

    本文提供的是一种关于网络分析的图聚类框架 LambdaCC 的更快更可靠的逼近算法，其依赖于可调节参数的分辨率参数和一种新的参数化边标记问题。

    Jun, 2023

  • 高效查询相关聚类

    本文主要研究了查询效率，使用类似于计算距离的相似度度量，通过提出新的算法实现了更加高效的相关聚类，能够在给定预算内使用不同的查询方式获得与最优解相差不大的结果，并且针对算法进行了实验研究。

    Feb, 2020

  • 多项式对数轮次内求解相关聚类问题的三因素近似算法失效

    本文研究了用于相关聚类问题的并行算法，其中每个不同实体的每对实体都标记为相似或不相似，旨在将实体分成簇以最小化与标签的不一致性，提出了首个多项式对数深度并行算法，并使用比 3 更好的逼近比计算 (2.4 +ϵ) 逼近解，可以将其转换为 (m1.5) 时间顺序算法和带有 (m1.5) 总内存的多项式对数轮次亚线性内存计算算法。

    Jul, 2023

  • 使用同簇查询的近似相关聚类

    该研究介绍了一种半监督聚类框架及其在相关性聚类问题中的应用，提出了一种有效的近似算法，并给出了同类查询数量的上下界。

    Dec, 2017

  • 强三元闭合与簇删除的关系

    该论文研究了基于无向图的两个相关问题的参数化复杂性和经典复杂性，包括强三元闭包、集群删除等问题，并研究了关于这两个问题的复杂性和多项式内核等相关问题。

    Mar, 2018

  • 相关聚类推广

    LambdaCC 和 MotifCC 是两种变体的相关聚类问题，应用于网络分析和社区检测，我们提出了两种非平凡的逼近算法来解决该问题，其中我们提出了两个算法来改善先前的逼近结果，同时还研究了在构造两个簇的限制下的逼近结果，其中 MotifCC 应用于超图设置。

    Sep, 2018

  • 最小最大相关聚类的 4 近似算法

    我们介绍了一种用于最小最大相关聚类问题的下界技术，并基于此技术提出了一种完全图的组合 4 近似算法。我们通过贪婪连接启发式算法扩展了这个算法，并在几个基准数据集上实证表明它提高了解决方案的质量和运行时间，改进了现有的技术水平。

    Oct, 2023

  • 大规模相关聚类优化

    本文聚焦于 Correlation Clustering functional，它结合了数据点之间的正面和负面亲和性。文章的贡献包括两个方面，一是提供了该函数的理论分析；二是提出了新的优化算法，能够处理无法使用现有方法解决的大规模问题（>100K 变量）。通过对该函数的理论分析，发现该函数具备概率生成解释的能力，并且合理地解释了其内在的 “模型选择” 能力。此外，文章还探索了该函数和 well-known Potts 能量最小化之间的类比，这为我们提出了几种新的优化算法，这些算法利用函数的内在 “模型选择” 能力，可以自动恢复基础聚类数。与此同时，文章还介绍了两种新的应用领域：无监督人脸识别和通过粗略边界描绘实现的交互式多对象分割。

    Dec, 2011

  • 具有不对称分类误差的相关聚类

    本文研究了相关聚类问题在每个相似边和不相似边权重符合一定假设下的近似算法，并给出了此问题渐近匹配的线性规划完整性间隙。

    Aug, 2021

  • 定数个簇的相关聚类

    研究聚类分析中的一种新方法 —— 相关聚类或定性信息聚类，探讨了最大化协议的问题和最小化分歧的问题，重点研究了聚类数为常数 k 的情况，发现该问题具有多项式时间近似解，为解决最小化分歧问题做了大量的技术工作。

    Apr, 2005