基于相似词序列的聚类串

Question

我正在寻找一种有效的方法,根据相似单词序列的外观将大约1000万个字符串聚类成簇.

考虑一个字符串列表,如:

the fruit hut number one
the ice cre  am shop number one
jim's taco
ice cream shop in the corner
the ice cream shop
the fruit hut
jim's taco outlet number one
jim's t  aco in the corner
the fruit hut in the corner

算法运行后,我希望它们聚集如下:

the ice cre  am shop number one
ice cream shop in the corner
the ice cream shop

jim's taco
jim's taco outlet number one
jim's t  aco in the corner

the fruit hut
fruit hut number one
the fruit hut in the corner

很明显,区分聚类的序列是:

ice cream shop, jim's taco and fruit hut

Answer 1

我认为您正在寻找近似重复检测,您将使用一些未知阈值来聚类"不太重复" - 而且还有类似的文档.

其中一个已知的解决方案是使用Jaccard-Similarity来获得两个文档之间的差异.

Jaccard相似性基本上是 - 从每个文档中获取单词集,让这些集合s1和s2- 以及jaccard相似性|s1 [intersection] s2|/|s1 [union] s2|.

通常在面临重复时 - 但是单词的顺序有一些重要性.为了对付它-生成集时s1和s2-你真正产生套K-shinglings(或K-克),而不是套的唯一的一句话.
在你的例子中,k=2套装将是:角落里的冰淇淋店

s2 = { the ice, ice cre, cre am, am shop, shop number, number one }
s4 = {ice cream, cream shop, shop in, in the, the corner }
s5 = { the ice, ice cream, cream shop }

s4 [union] s5 = { ice cream, cream shop, shop in, in the, the corner, the ice } 
s4 [intersection] s5 = { ice cream, cream shop }

在上面,jaccard相似性将是2/6.
在你的情况下,普通的k-shinglings可能比使用单个单词(1-shingling)表现更差,但你必须测试这些方法.

这个过程可以很好地扩展,以便非常有效地处理大型集合,而无需检查所有对并创建大量集合.更多细节可以在这些讲义中找到(我在2年前根据作者的笔记给出了这个讲座).

完成此过程后,您基本上有一个度量d(s1,s2)来衡量每两个句子之间的距离,您可以使用任何已知的聚类算法来聚类它们.

免责声明:在实现了近似重复之后,我使用了这个帖子的答案作为基础.