发现相似urls序列的算法是什么？

Question

假设一个域有一个urls列表，这些urls具有不同级别的路径深度和相似性

url1/some/where/here
url1/some/where-2/here
url1/some-3/where/here
...
...
url1/some/where/here/right/now/1
url1/some/where/here/right/now/2
url1/some/where/here/right/now/3
url1/some/where/here/right-1/now/1
url1/some/where/here/right-1/now/2
url1/some/where/here/right-1/now/3
url1/some/where/here/right-2/now/1
url1/some/where/here/right-2/now/2
url1/some/where/here/right-2/now/3
url1/some/where/here/right-2/now/4
...

我可以使用什么算法来根据URL字符串的密度(斜杠的数量)和相似性(文本距离，Levenshtein)对其进行聚类？

因此，输出将被聚集到组中：

url1/some/where/here

url1/some/where-2/here

url1/some-3/where/here

url1/some/where/here/right/now/1
url1/some/where/here/right/now/2
url1/some/where/here/right/now/3

url1/some/where/here/right-1/now/1
url1/some/where/here/right-1/now/2
url1/some/where/here/right-1/now/3

url1/some/where/here/right-2/now/1
url1/some/where/here/right-2/now/2
url1/some/where/here/right-2/now/3
url1/some/where/here/right-2/now/4

url1/some-3/where/here/133

一些特征：- url串越密集(或越深)，它就越相关，并且可能在序列中重复。-相似的urls块一个接一个地重复。不同的urls似乎离相似的urls更远。

DBSCAN适合这里吗？

(密度，LV距离)

我想删除最后一个字符，直到斜杠，然后在后续字符串中搜索匹配。如果匹配的url是列表中的下一个url，则它们很可能是一个块。如果在列表的更下方找到匹配，它可能不是任何块的一部分。

​

    url1/some/where

这几乎随处可见，因此不是任何块的一部分。

​

    url1/some/where/here/right/now/ 

查找两个后续匹配项，紧跟在候选人之后。

​

    url1/some/where/here/right-2/now/

找到3个随后出现的匹配项。所以它们被分成块。

​

    url1/some-3/where

在路径底部找到另一个匹配项，由于距离的原因，它们都不是任何块的一部分。这种方法有没有一个名字或者类似的东西？

​

Answer 1

是，尝试DBSCAN

我们没有你的数据，所以我们不知道它是否适用于你。

但是DBSCAN (特别是Generalized DBSCAN)非常灵活且易于适应。在你的案例中，你需要将你讨论的大部分问题的相似性正式化……考虑在斜杠上断开URL，然后将每个组件视为一个标记。这可能是最简单的方法。

总之:定义您想要的相似性，然后尝试DBSCAN和OPTICS。也许可以在某个地方分享你的经验，这样下一个学生就可以在此基础上继续学习。尝试生成一些可共享的代码，并将其回馈给社区；输入您的名字以获得信任。