3

我的问题是我需要比较 URL 路径并推断它们是否相似。下面我提供要处理的示例数据：

# GROUP 1
/robots.txt

# GROUP 2
/bot.html

# GROUP 3
/phpMyAdmin-2.5.6-rc1/scripts/setup.php
/phpMyAdmin-2.5.6-rc2/scripts/setup.php
/phpMyAdmin-2.5.6/scripts/setup.php
/phpMyAdmin-2.5.7-pl1/scripts/setup.php
/phpMyAdmin-2.5.7/scripts/setup.php
/phpMyAdmin-2.6.0-alpha/scripts/setup.php
/phpMyAdmin-2.6.0-alpha2/scripts/setup.php

# GROUP 4
//phpMyAdmin/

我试过 Levenshtein 距离来比较，但对我来说不够准确。我不需要 100% 准确的算法，但我认为 90% 及以上是必须的。

我认为我需要某种分类器，但问题是新数据的每个部分都可以包含应该分类到新未知类的路径。

你能把我引到右边吗？

谢谢

4

3 回答 3

1

在检查@jakub.gieryluk 的建议时，我意外地找到了令我满意的解决方案——“Hobohm 聚类算法，最初旨在减少生物序列数据集的冗余。”

Bruno Vecchi实现的 PERL 库测试给了我非常好的结果。唯一的问题是我需要 Python 实现，但我相信我可以在 Internet 上找到一个或自己重新实现代码。

接下来是我还没有检查过这个算法的主动学习能力；）

于 2011-10-20T13:12:05.973 回答
1

Levenshtein 距离是最好的选择，但要调整距离。您必须在标记上使用加权编辑距离和可能的分割路径 - 单词和数字。因此，例如像“2.5.6-rc2 和 2.5.6”这样的版本可以被视为 0 权重差异，但像 phpMyAdmin 和 javaMyAdmin 这样的名称标记给出 1 权重差异。

于 2011-10-19T09:21:15.203 回答
0

我知道这不是您问题的确切答案，但是您熟悉k-means算法吗？

我想即使 Levenshtein 也可以在这里工作，但困难在于如何用这种方法计算质心。

也许您可以将输入集划分为不相交的子集，然后为每个子集中的每个 URL 计算与同一子集中所有其他 URL 的距离，并且距离总和最小的 URL 应该是质心（当然，这取决于关于输入集有多大；对于大型集，这样做可能不是一个好主意）。

k-means 的好处是你可以从绝对随机的划分开始，然后迭代地让它变得更好。

k-means 的坏处是你必须k在开始之前精确。但是，在运行期间（可能在前几次迭代后情况稳定），您可以测量每个集合的内部相似性，如果它很低，您可以将集合分成两个子集并继续使用相同的算法。

于 2011-10-18T22:01:26.057 回答