Wie Sätze zu speichern, schnell ähnliche Muster zu finden?

StackOverflow https://stackoverflow.com/questions/462563

Frage

(Dies ist keine Hausaufgaben und keine Arbeit Problem. Es ist nur mein persönliches Interesse / Beruf und völlig frei erfunden. Aber ich bin an einem guten Algorithmus oder Datenstruktur).

Nehmen wir an, dass ich eine Dating-Site laufen würde. Und mein Besonderheit wäre, dass die Singles waren abgestimmt durch Film Geschmack . (Warum nicht?)

In diesem Fall würde ich einen Weg brauchen, um die Filmbewertungen für jeden Benutzer zu speichern. (Bisher kein Problem.) Und ich würde eine Datenstruktur benötigt die am besten passenden Benutzer zu finden. Der Abstand zwischen zwei Geschmacksmustern würde der durchschnittliche Abstand zwischen allen Bewertungen, die beiden Benutzern gemacht.

Beispiel: 

movies   A B C D E F G H I J K L M ...
user Xm  9 5   1   1   5
user Ym      4 6 1         8
user Zf  9   6 4           7

Entfernung (X, Z) = avg (abs (9-9) + abs (1-4)) = 1,5

Entfernung (Y, Z) = avg (abs (4-6) + abs (6-4) + abs (8-7)) = 1,666

So Mr. X passt etwas besser an Frau Z, als Herr Y tut.

Ich mag soulution, dass ...

  • ... braucht nicht viele Vorgänge in der Datenbank
  • ... brauchen nicht viele Daten
    • zu handhaben
  • ... laufen schnell
  • ... liefern die besten passende
  • Ok, vielleicht würde ich auch eine gute Näherung betrachten.

Versuchen Sie, im Auge zu behalten, dass dies auch mit Tausenden von möglichen Filmen, Benutzern dieser Rate nur etwa 20-50 Filme und Tausende von Benutzern.

funktionieren soll

(Da es sich um eine psychische Rätsel und kein wirkliches Problem, Work-arrounds sind nicht wirklich zu helfen.)

Was ist Ihr Suchalgorithmus oder Datenstruktur sein würde?

War es hilfreich?

Lösung

Klingt viel wie der Netflix Prize Herausforderung, insbesondere die erste Hälfte des beliebtestenen Ansatzes . Die möglichen Implementierungen von dem, was Sie versuchen, sind zahlreich und vielfältig zu tun. Keiner von ihnen sind besonders effizient, und die L1-Metrik ist keine besonders gute Wahl für zuverlässige Korrelationen.

Andere Tipps

Sieht aus wie Sie für die nächster Nachbar im Film Raum. Und Ihre Distanzfunktion ist die L1-Metrik . Sie können sich wahrscheinlich ein räumlichen Index irgendeine Art verwenden. Vielleicht können Sie Techniken von Collaborative Filtering . 

CREATE TABLE data (user INTEGER, movie INTEGER, rate INTEGER);

SELECT  other.user, AVG(ABS(d1.rate - d2.rate)) AS distance
FROM    data me, data other
WHERE   me.user = :user
    AND other.user <> me.user
    AND other.movie = me.movie
GROUP BY
    other.user
ORDER BY
    distance

Die Komplexität wird O (n 1.5 )) anstelle von O (n 2 ), wie es Vergleiche werden n zusammen gefüllt Filme (Durchschnitt von Filmen sqrt(n) durch jedes Paar).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top