数据流中的相关聚类

Dec, 2018

Correlation Clustering in Data Streams

Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, Anthony Wirth

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

Abstract

clustering is a fundamental tool for analyzing large data sets. A rich body of work has been devoted to designing data-stream algorithms for the relevant optimization problems such as $k$-center, $k$-median, and $k$-means. Such algorithms need to be both time and and space efficient. I

clustering dynamic data stream model correlation clustering approximation algorithms convex programming

发现论文，激发创造

亚线性时更新的动态相关聚类

在动态节点流中，我们研究了相关聚类的经典问题。我们提出了一种算法，通过维护 $O (1)$ 的逼近精度和 $O$(polylog $n$) 的摊销更新时间，不断寻找最小化穿越簇的正边和簇内负边之和的分区。最后，我们用实际数据实验证明了我们的理论分析。

Jun, 2024

数据流中的差分隐私聚类

论文提出了不同隐私性水平的 k-means 和 k-median 流式聚类算法，采用核心集算法作为黑盒子并使用多项式空间达到恒定乘性错误和多项式加性错误。

Jul, 2023

高效查询相关聚类

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

Feb, 2020

常数轮并行下的相关聚类

本文提出了一种基于大规模并行计算 (MPC) 的算法，用于解决相关聚类问题。该算法的主要目标是利用签名图对图进行分区以最小化争议数量。在实验中，该算法同时试图减少节点内存的使用率。我们的算法是第一个在亚线性存储器中运行且使用有限的 MPC 轮数可以证明近似计算聚类问题方法的一种。

Jun, 2021

用于相关聚类的单遍基准算法。保持简单！

本文介绍了 Correlation Clustering 中使用的 Pivot 算法的改进版本，并通过在单通道中使用 O (n/epsilon) 字的内存实现了 (3+epsilon) 近似，并与以前的结果进行了比较。

May, 2023

数据流聚类：一篇综述

该文综述了数据流聚类算法的基本概念和特点，对不同算法进行了对比分析，讨论了数据流聚类存在的问题和挑战。

Jul, 2020

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

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

Nov, 2014

一个用于图聚类的流算法

我们提出了一种新的算法，用于在单次遍历的边流设置中执行图聚类，并基于模块度函数提供了理论上的解释。我们对从一百万到十亿边的大规模现实生活图表进行实验，并展示了该算法比现有算法运行速度快十倍以上，并可在最大的图表上获得相似或更好的检测分数。

Dec, 2017

基于聚类的数据流分类框架

本文提出了一种基于聚类的数据流分类框架，通过采用基于密度的流聚类算法，结合动态阈值和有效的主动标签查询策略，处理非平稳数据流，解决了标注的初始集问题和重叠类别之间的分类挑战。同时对聚类中的子簇结构进行探索，有效的解决了类别之间的重叠问题。实验结果和定量比较研究表明，该方法提供了比现有方法更好或可比较的性能。

Jun, 2021

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

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

Nov, 2021