machine-learning - k 均值与 LSH 算法

Question

我对数据挖掘和机器学习还很陌生。我想了解 k-means 与 LSH 有什么不同。在阅读了一些在线可用的论文和其他 Material 后，似乎这两种算法都试图实现相似文档的分组/聚类。对于垃圾邮件检测等用例，它们中的任何一个都已在许多论文中使用。但我不太清楚它们有何不同，如果我们将其用于垃圾邮件检测等用例，结果会有什么不同？

Answer 1

LSH 不会对您的数据进行聚类。

它适用于接近重复(!)的检测。

1. LSH 的设计可能会产生根本不相似的“误报”(哈希冲突)。
2. LSH 有一个阈值 t，它只尝试对低于该阈值的对象产生哈希冲突。为了获得良好的性能，您需要选择尽可能小的该阈值。对于集群，您确实需要能够找到存储桶之外的对象(比 t 更远) - 您无法使用 LSH 可靠地做到这一点。
3. LSH 会随机放置桶边界；您没有注意到这一点的唯一原因是您多次执行此操作，并希望并非所有这些都被错误地选择。所以你只能得到几乎所有的近邻。甚至可能只有 90%，具体取决于您的参数。由于每个对象都位于多个存储桶中，那么它的簇是什么？您会得到大量重叠的“集群”，每个集群仅包含数据的某些部分。如何从中高效地找到好的集群就已经很清楚了。

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

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