Ähnlichkeit zwischen Benutzern auf Wertungen Basierend

Question

kann sagen, ich habe eine Menge von Benutzern, eine Reihe von Songs, und eine Reihe von Stimmen auf jedem Song:

=========== =========== =======
User        Song        Vote
=========== =========== =======
user1       song1       [score]
user1       song2       [score]
user1       song3       [score]
user2       song1       [score]
user2       song2       [score]
user2       song3       [score]
user3       song1       [score]
user3       song2       [score]
user3       song3       [score]
user-n      song-n      [score]
=========== =========== =======

Was ist der effizienteste Weg, Benutzer Ähnlichkeit basierend auf Song-Stimmen zu berechnen? Gibt es einen besseren Weg, als jeden Benutzer und jede Stimme für jeden Song iterieren?

Answer 1

Es gibt zwei gängige Metriken, die verwendet werden können Ähnlichkeiten zwischen den Nutzern zu finden:

1. euklidische Entfernung , das ist genau das, was Sie denken: ein n-dimensionalen Graphen vorstellen, die für jede Achse eines Song hat, der von zwei beteiligten Benutzern ( u1 und * u2) und der Wert auf seiner Achse ist die Punktzahl. Sie können Ähnlichkeit mit der Formel leicht berechnen:

   für jeden Song rezensiert von u1 und u2, berechnen pow(u1.song.score - u2.song.score, 2) und fügen Sie alle zusammen in sum_of_powers. Ähnlichkeitskoeffizient wird dann durch 1 / 1 + (sqrt(sum_of_powers)) gegeben.

2. Pearson-Korrelation (oder Korrelationskoeffizient): es ist ein besserer Ansatz, wie viel zwei Datensätze im Zusammenhang mit mir findet. Dieser Ansatz verwendet komplexere Formeln und ein wenig von Statistiken Hintergrund, überprüfen Sie es hier: Wiki . Sie werden für jedes Paar von Benutzern eine grafische Darstellung haben, können Sie Punkte dann plotten Partituren nach .. zum Beispiel, wenn aSong 2 von u1 und 4 von u2 abgestimmt wurde es den Punkt (2,4) plotten (das benutzer1 unter der Annahme, x-Achse und u2 ist y-Achse).

Nur um zu klären, verwenden Sie lineare Regression finden zwei Koeffizienten A und B, dass die Linie beschreiben, die die Entfernung von allen Punkten des Graphen minimiert. Diese Linie hat diese Formel: y = Ax + B. Wenn zwei Sätze ähnliche Punkte sind in der Nähe der Hauptdiagonale sein sollten, so sollte A 1 neigt, während B auf 0 Verpassen Sie nicht diese explaination so vollständig übernehmen oder als Referenz, weil es Solidität und typischen mathematischen Formalismus fehlt, ist es einfach zu geben, eine Idee.

EDIT: wie von anderen geschrieben, um komplexere Algorithmen Daten existieren Cluster, wie k-means, aber ich schlage vor, Sie von einfach diejenigen zu starten (eigentlich soll man nur etwas schwieriger brauchen, wenn man bedenkt, dass die Ergebnisse nicht ausreicht).

Answer 2

Ich empfehle das Buch Programmierung Collective Intelligence von Toby Segaran. Kapitel 3 beschreibt verschiedene Clusterverfahren wie Hierarchical Clustering und K-Means-Clustering .

Der Quellcode für die Beispiele ist verfügbar hier

Answer 3

Wenn Sie die genauesten Ergebnisse wollen, dann nein, man müßte über alles wiederholen.

Wenn Ihre Datenbank groß genug ist, können Sie nur eine statistische Stichproben nehmen, sagen wir zwischen 1.000 -10.000 Benutzer und Abgleich mit, dass die Einnahme.

Sie würden auch besser dran, einige weitere Tabellen zur Datenbank hinzufügen möchten, speichern Sie die Ergebnisse, und es nur jeder so oft aktualisiert werden, anstatt diese im laufenden Betrieb zu berechnen.

Answer 4

Ilya Grigorik hat eine Reihe auf Empfehlung Algorithmen, obwohl er zum Ruby wurde konzentriert. Es scheint, das Lernen unter der Maschine zu sein in seinem Archiven , aber gibt es Link kein direkter Abschnitt.

Answer 5

Wenn Sie es in einer angenäherten Weise tun wollen, ohne alle Datensätze zu besuchen, können Sie das Jaccard-Koeffizient verwenden. Wahrscheinlich braucht eine gewisse Anpassung, wenn Sie die Noten zu betrachten. Aber ich denke, das ist die beste Lösung, wenn Ihr System zu groß ist, und Sie haben nicht die Zeit, um alle Aufzeichnungen zu überprüfen.

Answer 6

Ich denke, eine Menge Leute hier die Einfachheit der Frage fehlen. Er sagte nichts über ein Rating Vorhersagesystem zu schaffen. Er will nur die Ähnlichkeit berechnen zwischen dem einzelnen Songs Rating Verhalten des Benutzers und die jeweils anderen Song Bewertung Verhalten des Benutzers. Der Pearson Korrelationskoeffizient gibt genau das. Ja, Sie müssen jeden Benutzer / Benutzer Paar iterieren.

EDIT:

Nach einigem Nachdenken darüber ein wenig mehr:

Pearson ist groß, wenn Sie die Ähnlichkeit zwischen zwei Benutzern des Geschmack wollen, aber nicht ihr Niveau der ‚opinionatedness‘ ... ein Benutzer, der eine Reihe von Liedern 4 bewertet, 5 und 6 wird mit einem anderen Benutzer korreliert perfekt, die Preise die gleichen Lieder 3, 6 und 9. mit anderen Worten, sie haben den gleichen „Geschmack“ (sie würden die Songs in der gleichen Reihenfolge Rang), aber der zweite Benutzer ist viel mehr opinionated. In anderen anderen Worten, behandelt der Korrelationskoeffizient von zwei beliebigen Bewertung Vektoren mit einer linearen Beziehung als gleich.

Wenn Sie jedoch die Ähnlichkeit zwischen den aktuellen Bewertungen der Benutzer jeden Song gab wollen, sollten Sie die mittlere quadratische Fehler zwischen den beiden Rating-Vektoren verwendet werden. Dies ist ein rein distanzbasierte Metrik (lineare Beziehungen nicht in die Ähnlichkeitsbewertung spielen), so dass die 4,5,6 und 3,6,9-Nutzer würden keinen perfekten Ähnlichkeitswert haben.

Die Entscheidung kommt darauf an, was Sie unter „ähnlich“ ...

Das ist alles.

Answer 7

Es soll möglich sein, einen guten Algorithmus in diesem Buch zu finden: Der Algorithmus Design Manual von Steven Skiena .

Das Buch hat eine ganze Reihe von Algorithmen für verschiedene Zwecke. Sie wollen einen Graph Clustering-Algorithmus, glaube ich. Ich weiß nicht die Kopie des Buches zur Hand haben, so kann ich es nicht für Sie suchen.

Eine schnelle Google-Suche eine Wikipedia-Seite gefunden: http://en.wikipedia.org/wiki/ Cluster_analysis Vielleicht helfen, aber ich denke, das Buch Algorithmen deutlicher erklärt.