php - 聚类 : finding groups of close items within a large collection

Question

我有一个项目数组(约 5000 个项目，每个项目都是一个英文单词)和项目对之间的距离函数。我想在数组中找到一组项目，其中一组中的所有项目都满足距离标准(例如，每对项目的距离小于 2)。组通常应尽可能大，但对此没有正式定义或硬性要求。

我的实现语言是 PHP，但我正在寻找有关可以有效处理此问题的算法的一般建议。

更新:我想我可以通过构建一个图来解决这个问题，其中顶点是项目，并且项目之间有一条边满足距离约束。一旦我构建了图表，我就可以运行像 Bron–Kerbosch 这样的算法来列出所有最大派系。如果可行，我会进行更新，但同时请随时添加您的想法。

Answer 1

这个函数是怎么定义的？它是预先计算的吗？如果是这样，您可以迭代计算函数表示并根据您的标准检索词对。如果不是，您别无选择，只能计算所有词对之间的函数(这在您的图形方法中是必要的)。除了 Bron-Kerbosch 算法，我会采用随机化+近似策略，例如，

http://dimacs.rutgers.edu/Workshops/Challenge10/abstracts.html#ovelgonne

http://dl.acm.org/citation.cfm?id=1933306.1934471

它基于模块化最大化方法。模块化是集群中传出边的数量与集群内边的数量之间的比率。在您的情况下，您将寻找比率为 0 的集群，并选择其中最大的一个。该算法非常快，适用于我使用过的大多数数据集。虽然基于模块化的方法对于这个问题可能有点矫枉过正，但恕我直言，我觉得这是思考问题的好方法 + 该算法的实现可在线获得(本文作者的 C 实现)。