0

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

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

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

4

3 回答 3

1

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

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

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

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

于 2013-07-25T21:17:05.627 回答
0

鉴于您希望您的标准适用于组的所有成员，您需要一个允许重叠组的聚类算法。这是一个相当复杂的主题，所以我能做的最好的就是指导您阅读有关聚类算法的文献，特别是为重叠组设计的C-Means Clustering 。

于 2013-07-22T10:59:21.623 回答
0

我理解的问题是：

“ AG ”代表单词。“ # ”代表两个词之间的距离。你需要找出距离 <= 2 的对。

  A B C D E F G
A * # # # # # #
B   * # # # # #
C     * # # # #
D       * # # #
E         * # #
F           * #
G             *

基本上它需要2级循环，我们可以做的是减少比较次数，只比较上面矩阵中的“#”部分。这是PHP中的代码：

$result = array();
while ( ($word = array_shift($arrWordList)) !== NULL ) {
    foreach ($arrWordList as $otherWord ) {
        if ( calc_dist($word, $otherWord) <= 2 ) {
            $result[] = array($word, $otherWord);
        }
    }
}

你可以使用 $result 继续做某事。

于 2013-07-22T10:51:50.460 回答