LSH und Collaborative Filtering: Ein praktischer Leitfaden zu DSCI553 Assignment 3 mit Spark

Einführung in DSCI553 Assignment 3: LSH und Recommender Systems

Die Aufgabe 3 des Kurses DSCI553 „Foundations and Applications of Data Mining“ aus dem Herbst 2021 fordert Studierende heraus, zwei zentrale Verfahren des Data Minings zu implementieren: Locality Sensitive Hashing (LSH) auf Basis der Jaccard-Ähnlichkeit und verschiedene Collaborative-Filtering-Empfehlungssysteme. Dabei kommt ausschließlich Apache Spark mit RDDs zum Einsatz – externe Bibliotheken wie NumPy oder Pandas sind nicht erlaubt. Dies spiegelt reale Anforderungen wider, wie sie etwa bei der Entwicklung von Empfehlungsalgorithmen für Streaming-Dienste oder Social-Media-Plattformen auftreten.

Warum LSH und Collaborative Filtering heute relevanter sind denn je

In einer Welt, in der personalisierte Empfehlungen den Alltag bestimmen – von TikTok-Videos über Spotify-Playlists bis hin zu Netflix-Serien – sind Techniken wie LSH und Collaborative Filtering unverzichtbar. Statt exakte Ähnlichkeitsberechnungen durchzuführen, die bei Millionen von Nutzern und Items rechenintensiv wären, erlaubt LSH eine effiziente Annäherung. Aktuelle Beispiele: Wenn eine E-Commerce-Plattform Produkte vorschlägt, die „Kunden, die dies kauften, auch kauften“, steckt oft Collaborative Filtering dahinter. Oder wenn eine KI-gestützte Lern-App Übungen basierend auf dem Verhalten ähnlicher Schüler empfiehlt, nutzt sie ähnliche Prinzipien.

Aufgabe 1: Jaccard-basiertes LSH implementieren

In Task 1 geht es darum, mithilfe von LSH Geschäftspaare aus dem Yelp-Datensatz zu identifizieren, deren Jaccard-Ähnlichkeit mindestens 0,5 beträgt. Dabei wird die Bewertungsmatrix binär betrachtet: Hat ein Nutzer ein Geschäft bewertet, ist der Eintrag 1, sonst 0. Die Herausforderung besteht darin, geeignete Hash-Funktionen zu wählen, die eine zufällige Permutation der Zeilen simulieren. Typische Funktionen sind f(x) = (ax + b) % m oder f(x) = ((ax + b) % p) % m, wobei p eine Primzahl und m die Anzahl der Bins ist.

Schritt-für-Schritt-Ansatz für LSH

1. Charakteristische Matrix erstellen: Aus der Trainingsdatei yelp_train.csv wird eine binäre Matrix erstellt, in der Zeilen für Nutzer und Spalten für Geschäfte stehen.
2. Hash-Funktionen definieren: Wählen Sie n Hash-Funktionen (z. B. n = 100), die die Zeilenindizes permutieren. Achten Sie auf eine gute Streuung, um Kollisionen zu minimieren.
3. Signaturmatrix aufbauen: Für jedes Geschäft wird eine Signatur der Länge n berechnet, indem der minimale Hash-Wert über alle Zeilen mit einer 1 ermittelt wird.
4. Bandit-Technik anwenden: Teilen Sie die Signatur in b Bänder mit jeweils r Zeilen auf, sodass b × r = n. Wählen Sie b und r so, dass die Wahrscheinlichkeit für False Positives und False Negatives optimiert wird (z. B. b = 20, r = 5).
5. Kandidatenpaare identifizieren: Zwei Geschäfte sind ein Kandidatenpaar, wenn ihre Signaturen in mindestens einem Band identisch sind.
6. Jaccard-Ähnlichkeit der Kandidaten berechnen: Nur Paare mit einer Ähnlichkeit ≥ 0,5 werden in die Ausgabedatei geschrieben.

Die Ausgabe muss als CSV mit den Spalten business_id_1, business_id_2, similarity erfolgen, alphabetisch sortiert. Die Bewertung erfolgt über Precision und Recall, wobei Precision ≥ 0,99 und Recall ≥ 0,97 für volle Punktzahl erforderlich sind. Die Laufzeit darf 100 Sekunden nicht überschreiten.

Aufgabe 2: Collaborative-Filtering-Empfehlungssysteme

Task 2 verlangt die Implementierung mehrerer Recommender-Systeme, die Bewertungen (Stars) für Nutzer-Geschäft-Paare vorhersagen. Grundlage ist wieder yelp_train.csv. Erlaubt sind ausschließlich Spark RDDs; DataFrames sind nicht zulässig. Die Systeme sollen auf dem Validierungsdatensatz getestet werden, ohne diesen ins Training einzubeziehen.

Mögliche Ansätze für Collaborative Filtering

• Item-basiertes Collaborative Filtering: Berechnen Sie die Ähnlichkeit zwischen Geschäften basierend auf den Bewertungen gemeinsamer Nutzer. Verwenden Sie z. B. die Pearson-Korrelation oder die Cosine-Ähnlichkeit. Die Vorhersage für einen Nutzer u und ein Geschäft i ergibt sich aus den gewichteten Durchschnittsbewertungen ähnlicher Geschäfte, die u bewertet hat.
• User-basiertes Collaborative Filtering: Analog, aber mit Nutzerähnlichkeiten. Dies kann bei vielen Nutzern rechenintensiv sein, eignet sich aber für Szenarien mit stabilen Nutzerprofilen.
• Modellbasierte Ansätze (optional): Obwohl nicht explizit gefordert, könnten Sie mit Spark-basierten Alternativen wie Matrixfaktorisierung experimentieren, um die Genauigkeit zu verbessern. Achten Sie jedoch auf die Beschränkung auf RDDs.

Praktische Tipps zur Optimierung

Da die Laufzeit begrenzt ist, sollten Sie effiziente Datenstrukturen wie Broadcast-Variablen für Ähnlichkeitsmatrizen nutzen. Auch das Caching von RDDs, die mehrfach verwendet werden, beschleunigt die Verarbeitung. Ein aktuelles Beispiel: Ähnlich wie Spotify personalisierte Playlists erstellt, könnten Sie die Ähnlichkeit von Geschäften auf Basis von Nutzerbewertungen berechnen – je mehr gemeinsame Bewertungen, desto höher die Gewichtung.

Häufige Fehler und wie Sie sie vermeiden

• Falsche Hash-Funktionen: Testen Sie Ihre Hash-Funktionen auf Gleichverteilung. Ungleichmäßige Permutationen führen zu vielen False Positives oder Negatives.
• Band-Parameter falsch gewählt: Bei zu wenigen Bändern sinkt der Recall, bei zu vielen steigt die Anzahl der False Positives. Experimentieren Sie mit verschiedenen Kombinationen.
• Vergessen der Sortierung: Die Ausgabe muss sowohl innerhalb jedes Paares als auch global alphabetisch sortiert sein. Nutzen Sie sorted() und sortBy() in Spark.
• Nutzung von DataFrames: Die Aufgabenstellung verbietet DataFrames explizit. Verwenden Sie ausschließlich RDDs, sonst gibt es null Punkte.

Verbindung zu aktuellen Trends und KI-Entwicklungen

Die Techniken aus Assignment 3 sind die Grundlage vieler moderner KI-Anwendungen: Empfehlungssysteme in Social Media, E-Commerce und Streaming-Diensten. Beispielsweise nutzt die KI-gestützte Lernplattform „StudyAI“ ähnliche Algorithmen, um Lernenden personalisierte Übungen vorzuschlagen. Auch in der Finanzwelt kommen LSH-ähnliche Verfahren zum Einsatz, um betrügerische Transaktionen zu erkennen, indem ähnliche Muster in Echtzeit geclustert werden. Ein weiteres Beispiel: Die Spieleplattform Steam verwendet Collaborative Filtering, um Spielern neue Titel zu empfehlen – basierend auf den Bewertungen anderer Spieler mit ähnlichem Spielverhalten.

Fazit und nächste Schritte

DSCI553 Assignment 3 ist eine hervorragende Gelegenheit, tief in die Welt des Data Minings einzutauchen. Durch die Implementierung von LSH und Collaborative Filtering mit Spark RDDs gewinnen Sie praktische Erfahrungen, die direkt in der Industrie anwendbar sind. Nutzen Sie die bereitgestellten Validierungsdaten, um Ihre Modelle zu optimieren, und achten Sie auf die Einhaltung der Laufzeit- und Formatvorgaben. Mit einem systematischen Ansatz und dem Verständnis der zugrundeliegenden Mathematik sind die geforderten Precision- und Recall-Werte erreichbar.

Viel Erfolg bei der Implementierung – und denken Sie daran: Wie bei einem gut trainierten KI-Modell kommt es auf die richtige Balance zwischen Effizienz und Genauigkeit an!