k-meansとLSHのアルゴリズム

Question

私はデータマイニングとMLにはかなり新しいです。 LSHとk-meansがどのように違うのか理解したい。いくつかの論文やオンラインで入手可能な他の資料を読んで、両方のアルゴリズムが類似した文書のグループ化/クラスタリングを達成しようとしているようです。スパム検出などの用途では、どちらも多くの論文で使用されています。しかし、私はそれらがどのように異なっているかはあまり明確ではなく、スパム検出のような用途にこれを使用しても、その結果はどう違うでしょうか？

Answer 1

LSHはデータをクラスタ化しません。

近接重複（！）検出に適しています。

1. LSHは設計上、全く似ていない「偽陽性」（ハッシュコリジョン）を生成する可能性があります。
2. LSHにはしきい値tがあり、このしきい値以下のオブジェクトに対してのみハッシュコリジョンを生成しようとします。良好なパフォーマンスを得るには、このしきい値をできるだけ小さくする必要があります。クラスタリングの場合、は、バケット外のオブジェクトを（tよりも遠くに）見つけることができる必要があります。これをLSHで確実に行うことはできません。
3. LSHはバケット境界をランダムに配置します。あなたがこれを何度も気付かない唯一の理由は、あなたがこれを何度もやっていることです。そしてそれらのすべてがひどく選ばれていないことを願っています。だから、はほぼのすべての近くの隣人になります。あなたのパラメータによっては90％しかないかもしれません。すべてのオブジェクトはの複数のバケットにあるので、そのクラスタは何ですか？重複している「クラスタ」という膨大な量のデータがそれぞれに含まれています。これからどのようにして良いクラスタを効率的に見つけるかははっきりしています。

LSHは実際にはの "ほぼ同じ"オブジェクトで、データ内のより大きな構造を見つけることではありません。

私は、スパム検出はどちらの場合でも良いとは思わない - 実際にこれを行うスパムフィルタは分かっていますか？ ニュースのほぼ重複したニュース検出。しかし、Googleニュースはある種のLSHに関連しています。彼らはおそらくminhashingを使用しています。