K-Mittel gegen LSH-Algorithmus

Question

Ich bin ziemlich neu in Data Mining und ML. Ich möchte verstehen, wie unterschiedlich k-bedeutet von LSH ist. Nach dem Lesen einiger Arbeiten und anderer online verfügbarer Materialien scheint es, dass beide Algorithmen versuchen, eine Gruppierung/Gruppierung ähnlicher Dokumente zu erreichen. Für Anwendungsfälle wie die Spam-Erkennung wurden beide in vielen Papieren verwendet. Aber ich bin nicht sehr klar, wie sie anders sind und wenn wir das überhaupt für einen Anwendungsfall wie Spam-Erkennung verwenden, wie würde sich das Ergebnis überhaupt unterscheiden?

Answer 1

LSH clustert nicht Ihre Daten.

Es eignet sich für nahezu doppelte (!) Erkennung.

1. LSH by Design kann "falsche Positive" (Hash-Kollisionen) erzeugen, die überhaupt nicht ähnlich sind.
2. LSH hat einen Schwellenwert t und versucht nur Hash-Kollisionen für Objekte unterhalb dieses Schwellenwerts zu erzeugen. Für eine gute Leistung müssen Sie diesen Schwellenwert so klein wie möglich auswählen. Für das Clustering müssen Sie tun in der Lage sein, Objekte außerhalb Ihres Eimers (weiter weg als t) zu finden - Sie können dies nicht zuverlässig mit LSH tun.
3. LSH wird Eimer Grenzen nach dem Zufallsprinzip; Der einzige Grund, warum Sie das nicht so oft bemerken, ist, dass Sie dies mehrmals tun und hoffen, dass nicht alle von ihnen schlecht gewählt sind. So erhalten Sie nur fast alle nahen Nachbarn. Vielleicht sogar nur 90%, abhängig von Ihren Parametern. Wie jedes Objekt ist in mehrere Eimer, was wäre sein Cluster? Sie erhalten eine riesige Menge überlappender "Cluster", die jeweils nur Teile Ihrer Daten enthalten. Es ist alles andere als klar, wie man daraus gute Cluster effizient findet.

LSH ist wirklich über „fast die gleichen“ Objekte, nicht über größere Struktur in Ihre Daten zu finden.

Ich glaube nicht, dass Spam-Erkennung ein guter Anwendungsfall für beide ist - wissen Sie von Spam-Filter, die das tatsächlich tun würde? Die fast doppelte Nachrichtenerfassung von z.B. Google News bezieht sich jedoch auf eine Art von LSH; Angeblich benutzen sie Minhashing.