查找对象之间相似性的算法

Question

我有一些巨大的数据集(介于10-20之间),我需要找出这些数据集之间的关系.数据集非常庞大,计算可能不适合单台计算机.这些数据集中的字段是文本而不是数字.增加复杂性,一些字段也可能有不正确的单词,例如'huose'为'house',我正在使用模糊算法.

为了解决这个问题,我正在考虑使用余弦相似性但不确定这么大的数据集的性能.我的问题是,这种算法是否足以应对这种问题(性能和准确性).如果没有,是否还有其他一些我应该研究的算法？

编辑:更多信息

我将使用的数据集可能是文本文件和数据库表的混合.列中的值通常为10-50 char,并且它不是一个巨大的文档.我寻找的关系是数据集的一列与另一列的相似程度.我有点想根据列之间的相似性得出分数.例如

Col1     Col2     Col3
A        B        X
C        S        B
E        C        A
T        V        C
X        E

因此,在上面的例子中,人们可以说Col1并且Col3彼此之间有很强的关系Col1而且Col2关系很弱.

Answer 1

不,使用余弦相似性不是一个好的选择,因为:

1. 它没有考虑单词的顺序(假设词袋模型).
2. 它需要计算每对对象的成对距离,这对于大型集合来说在计算上是不可能的.

您可能正在寻找更类似于信息检索中的近重复检测的内容.我已经在一个不同的线程(虽然不是一个确切的欺骗)中解释过一次,但是这里是如何做到的:

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

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

通常在面临重复时 - 但是单词的顺序有一些重要性.为了对付它-生成集时s1和s2-你真正产生套K-shinglings,而不是套的唯一的一句话.
例如

Text 1:"I'm writing a crawler to"
Text 2:"I'm writing a some text crawler to get"

随着k=2,集合将是:

s1 = { I'm write, write a, a crawler, crawler to }
s2 = { I'm write, write a, a some, some text, text crawler, crawler to, to get }
s1 [union] s2 = { I'm write, write a, a crawler, crawler to, a some, some text, text crawler, to get } 
s1 [intersection] s2 = { I'm write, write a, crawler to }

在上面,jaccard相似性将是3/8.如果你使用相同方法的单个单词,(k = 1个shinglings)你将得到你想要的5/8- 但这是我(以及大多数IR专家)意见的更糟糕的解决方案.

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