KDDSep, 2011

利用 MapReduce 进行快速聚类

PDF
TL;DR本文考虑在 MapReduce 环境下设计用于处理大数据集的聚类算法，重点研究实用和流行的聚类问题，如 k-center 和 k-median，并开发具有常数因子近似保证的快速聚类算法。
发现论文，激发创造
  • 分布式部分聚类

    提出了一种在分布式环境下运行的算法来解决部分聚类问题，包括 k 中心，k 中位数和 k 均值等，旨在提高通信效率和解决噪音和数据不确定性带来的影响。

    Mar, 2017

  • 在一般拓扑上进行分布式 k-Means 和 k-Median 聚类

    本文提出一种新的分布式 k-median 和 k-means 聚类算法，通过 coresets 的方法，构建全局 coreset，降低了通信复杂度，实验结果表明该算法优于其他 coreset-based 分布式聚类算法。

    Jun, 2013

  • 可扩展核聚类：近似核 k-means

    本文提出了一种基于随机化的近似核 K-means 簇算法，其利用采样点与数据集中所有点之间的核相似性来近似聚类中心，实现了与传统低秩核近似聚类方案相比更好的聚类性能、更短的运行时间和更小的内存需求，最后利用集成聚类技术进一步提高算法性能。

    Feb, 2014

  • 在 MapReduce 框架中的排序、搜索和模拟

    本文探讨了 MapReduce 框架的算法方面，并通过设计和分析处理基本的排序、搜索和仿真问题的 MapReduce 算法展示了我们的方法的有效性。

    Jan, 2011

  • 分布式聚类与异常检测的实用算法

    本文提出了一种基于简要构建的数据摘要的分布式无监督学习算法，对异常点的全局识别有很好的近似保证，并在真实和人工数据上超过了所有基线算法。

    May, 2018

  • 有序 k - 中位数的常系数近似

    提供了一种基于 LP-rounding 的近似算法来解决有序 k-Median 问题，并探讨了包括权重和距离分配方法在内的多种算法来处理该问题。

    Nov, 2017

  • 使用 MapReduce 高效处理 k 近邻连接

    本研究探讨使用 MapReduce 框架在集群上执行 KNN join 操作的机制，并提出采用聚类将对象分组的映射机制、两种算法来降低成本，旨在减少洗牌和计算成本，并进行了有效性、鲁棒性和可伸缩性的实验验证。

    Jun, 2012

  • 近似聚类的最优时间界限

    本文研究了基于 k-median 目标函数的聚类问题，提出了一种称为连续采样的简单但有效的采样技术，并使用该技术开发了一个可在 O（nk）时间内运行的算法来解决 k-median 问题。

    Dec, 2012

  • 可扩展的公平聚类

    本研究提出了一种实用的近似公平分解算法，几乎在线性时间内运行，可对结果聚类的平衡性进行更精细的控制。

    Feb, 2019

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

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

    Jun, 2022