k-means与LSH算法

Question

我对数据挖掘和ML很新颖。我想了解LSH的k-means有什么不同。在阅读少量论文和其他网上资料后，似乎两种算法都试图实现类似文件的分组/聚类。对于垃圾邮件检测等用户来说，其中的任何一种都已被用于许多论文。但我不是很清楚他们有什么不同，如果我们将这个用于垃圾邮件检测这样的用例，结果会如何呢？

Answer 1

LSH不对您的数据进行群集。

它适用于接近重复（！）检测。

1. 通过设计LSH可能会产生“误报”（散列collisions），根本不相似。
2. LSH有一个阈值t，它只会尝试产生低于此阈值的对象的哈希链接。为了获得良好的性能，您需要选择尽可能小的阈值。对于群集，你需要能够在桶外找到对象（远离t） - 你无法可靠地用LSH做到这一点。
3. LSH将随机放置桶边界;你没有注意到这一点的唯一原因是你多次这样做，并希望不是所有人都被严重挑选。所以你只能得到差不多所有近邻。甚至可能只有90％，这取决于你的参数。由于每个对象都在多个存储桶中，它的集群是什么？您会得到大量重叠的“群集”，每个群集只包含数据的某些部分。这一切都很清楚，如何从中有效地找到好的集群。

LSH是真的关于“几乎相同的”对象，不是在你的数据中寻找更大的结构。

我不认为垃圾邮件检测是一个很好的用例 - 你知道任何垃圾邮件过滤器实际上会这样做吗？ 近乎重复的新闻检测例如然而，Google新闻与某种LSH有关;据说他们正在使用minhashing。