3

余弦相似度：通常在比较两个文档时使用。它测量两个向量之间的角度。如果该值为零，则两个向量之间的角度为 90 度，并且它们不共享任何项。如果值为 1，则两个向量除了幅度之外是相同的。当数据稀疏、不对称并且缺乏特征的相似性时，使用余弦。

当我将余弦用于两个向量（文档）时，我将根据下表获得结果

id        Doc1(TF)  Doc2 (TF)
London        5        3
Is            2        2
Nice         10        3
City          0        1

然后将其标准化到最后。然后，我将得到余弦 Cos(v1,v2)= 90%

但是，如果我有 10 份文件，这意味着我得到了

Cos(v1,v2)= ? 
Cos(v1,v3)= ?
Cos(v1,v5)= ?
Cos(v1,v6)= ?
Cos(v1,v7)= ?
Cos(v1,v8)= ?
Cos(v1,v9)= ?
Cos(v2,v3)= ? 
Cos(v2,v4)= ?
Cos(v2,v5)= ?

And so o n 

Until 

Cos(v9,v10)= ?

然后我必须比较结果。

有什么快速的方法吗？我怎样才能得到 10 个或更多文件的 cos。

我知道我怎样才能得到两个文件的余弦但是我怎样才能得到更多的文件呢？我想要数学方法。

4

2 回答 2

1

有一个非常棘手的优化很容易被忽视。

大多数时候，您的向量将是sparse。如果您查看余弦相似度的公式，请注意向量长度不会改变。所以你可以预先计算它们。

对于点积，请注意，如果您的向量在 10% 的维度中为非零，则两者都将在仅 1% 的维度中为非零。所以你只想计算非零维度的产品！例如，在您的示例中，您想跳过单词City。

如果您随后将数据转置为基于列的布局并将零放在那里，您可以以分布式方式非常快速地计算它。例如，列v1中将缺少City文档。然后计算每列中的成对乘积，并将它们输出到相应的文档对。最后，您使用总向量长度对这些总和进行归一化。Mahout应该已经这样做了，因此您应该在一本关于 Mahout 的好书中找到有关此方法的详细信息（抱歉，我没有好的指示）。

处理大量文本的关键思想是利用稀疏性。尽量避免任何值为 0 的计算。

于 2013-01-01T12:23:58.870 回答
0

这里有一些优化。由于成对距离矩阵关于诊断对称，因此只计算矩阵的上三角形。此外，要进行实际的聚类，假设您有成对距离矩阵，您可以在 n-1 次迭代中执行此操作。计算成对距离矩阵的一种快速方法是使用并行编程（比如 GPU）。结果表明，在 GPU 上计算成对距离比 CPU 快 64 倍。然而，对于像单链路层次聚类这样的聚类算法，实际的聚类必须在 CPU 上完成

于 2012-12-25T17:25:57.143 回答