Oct, 2017

单连接聚类在 l_p 距离下的大规模并行算法和难度

PDF
TL;DR介绍了用 Apache Spark 实现的高效的大规模并行算法来计算单链接聚类问题，该算法在 Hamming 距离，L1，L2 和 L∞ 距离下均能实现单轮 MPC，和（除了 Hamming 距离的精确算法外）都能实现（1+ε）- 近似，同时证明了在标准 MPC 难度假设下，o（log n）轮算法的常数近似难度结果。
massively parallel algorithmssingle-linkage clusteringhardness of approximationmpcapache spark
发现论文，激发创造
  • 并行匹配算法的圆形压缩

    该篇论文探讨了在大规模计算框架中对于最大匹配问题的解决方法，最终在机器拥有稍微低于线性内存的条件下，实现了近乎指数级的算法复杂度优化。

    Jul, 2017

  • 常数轮并行下的相关聚类

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

    Jun, 2021

  • 个体公平聚类的改进近似算法

    此论文介绍了一种可行的算法，用于从簇成员与簇中心之间的距离范数角度出发解决公平聚类问题，并对相应指标（如 bicriteria）进行了优化；同时，提供了一种基于模类约束的距离范数成本设施位置 16^p - 近似算法，并将借鉴此算法，将个体公平聚类转化为更一般如群体公平聚类的解法。

    Jun, 2021

  • 社会公正聚类的近似算法

    本文提出了一种在社会公正聚类中的近似算法，这个问题包括了在一个度量空间中，给定一组点，每个点属于一个或多个组，为了同时满足所有组，需要找到一个 k - 中位数、k - 均值或者更一般意义上，l_p - 聚类，同时给出了强化的 LP 松弛，将其应用于近似算法和双标准近似算法，并取得了理论上的改进。

    Mar, 2021

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

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

    Jul, 2023

  • 局部收缩算法实现大规模连通性分量

    该研究设计了一个分布式算法用于计算连接组件问题，并在 MapReduce 中提供了可扩展的实现。该算法在所有图形上显示 O (log n) 收敛，并对某些随机图形类具有高概率 O (log log n) 并行运行时间。在实践方面，该算法优于现有的 MapReduce 算法，并且在拥有数万亿边缘的图形上具有可扩展性。

    Jul, 2018

  • 社会公平的常积分因子 $k$- 聚类近似算法

    本研究对含 m 个群体的社会公平 (l_p, k)- 聚类问题的近似算法进行研究，其中特殊情况包括社会公平 k - 中心 (p=1) 和社会公平 k - 均值 (p=2) 问题。研究分别给出了多项式时间和两种不同的 (n^{2^{O (p)} m^2} 和 k^m poly (n)) 的近似算法，并探讨了这些算法与现有算法的比较。

    Jun, 2022

  • 一维投影聚类的简单、可扩展和有效方法

    非监督学习中的聚类是一个基础问题，本研究介绍了一种简单的随机聚类算法，它在任意 k 下的期望运行时间为 O (nnz (X) + nlogn)，并在 K-means 目标函数上实现了近似比例约为 O (k^4) 的算法，通过实验证明与现有方法相比，我们的聚类算法在运行时间和聚类质量之间有一个新的权衡。

    Oct, 2023

  • 近线性时间的分层聚合图聚类

    本文提出了一种层次凝聚图聚类算法框架并给出了完整的精确算法和近似算法，可以用于加权图的聚类问题，并通过用 $k$-NN 方法将点集转化为加权图，实现对点集的快速聚类。

    Jun, 2021

  • 基于随机化的降维在设施定位和单链接聚类中的应用

    本文研究将输入点集 $X$ 投影到随机 $d=O (d_X)$ 维子空间（其中 $d_X$ 是 $X$ 的双倍维数）的随机降维应用到聚类问题中，主要探讨了设施选址问题和单链接层次聚类问题。研究表明，这种方法在维度映射到一定程度时，可以达到在原始空间中找到的最优的设施选址近似值，同时这种方法还可以用于解决最小生成树等问题。

    Jul, 2021