Dec, 2011

大规模相关聚类优化

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

    本文研究了相关聚类中使用主动学习来查询相似性的有效获取函数，并提出了三种基于不一致性、熵和信息增益的获取函数。

    Feb, 2024

  • 高效查询相关聚类

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

    Feb, 2020

  • 预测聚类与优化的普适性框架

    本文研究了一种以监督学习为基础的聚类分析方法，该方法结合了回归和分类，采用整数线性规划方法以及高度可扩展的贪心算法，支持不同类型的聚类定义，并能够展示数据中不同的可解释性的离散聚类结构。

    May, 2023

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

    本研究提出了更快的近似算法，避免了其最佳逼近算法所依赖的不切实际的线性规划放宽，为两个经过充分研究的特殊情况 —— 聚簇编辑和聚簇删除提供了更快、更实用、更高效的线性规划算法及极具可扩展性的组合技术，包括聚簇删除的第一个组合逼近算法，实际应用中，我们的算法产生了近乎与质量最佳算法相匹配的近似解，同时适用于数量级更大的问题。

    Nov, 2021

  • 多割最小最大相关聚类

    本文提供了第一个问题的非平凡近似算法，来解决最小化每个子群组的最大不一致数的最小化最大相关聚类问题，并对 multicut 问题得出了相应的结果。

    Jun, 2019

  • 定数个簇的相关聚类

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

    Apr, 2005

  • 多层关联聚类

    我们在这篇论文中建立了多层相关聚类，这是对相关聚类（Bansal 等人，FOCS'02）在多层设置中的一种新的概括。我们首先设计了一个基于知名区域生长技术的 O (Llogn) 逼近算法（其中 L 是层数），然后研究了带有概率约束的一个重要特殊情况。我们进一步设计了一个 4 逼近算法，该算法改进了一般概率约束情况下的逼近比例。使用真实数据集的计算实验证明了我们所提出算法的有效性。

    Apr, 2024

  • 数据流中的相关聚类

    本文研究动态数据流模型下相关聚类问题，结合线性草图和凸规划与抽样技术提出 O (n・polylog n)-space 近似算法，解决了自然问题。

    Dec, 2018

  • 具有限制聚类大小和扩展权重上限的相关聚类

    本文介绍了在具有聚类大小限制以及边权重正负约束的图上的相关聚类问题。该研究提出了在边权重值为常数近似保证的情况下，解决带有聚类大小限制的相关聚类问题的方法。

    Nov, 2014

  • 图像分割的快速平面互相关聚类

    本文提出了一种基于加权完美匹配的优化方案，用于在平面图中查找高质量的相关聚类，该方法提供了通常易于计算且实践中紧密的最优关联聚类的下限。作者在问题上演示了他们的算法，该方法在最小化目标方面优于现有的全局优化技术，并在产生高质量分割方面与现有技术具有竞争力。

    Aug, 2012