Recommendation Engine

[Ocram7]

Ich möchte für eine Newsseite ein Empfehlungs-System (Recommendation Engine) aufbauen. Das Ganze soll so funktionieren:

1) Ein Nutzer bewertet einen Artikel entweder als gut oder als schlecht.

2) Wenn die Bewertung gut ist, dann wird die Verknüpfung zwischen den Themen des Artikels und dem Nutzer in der Datenbank verstärkt.

Wenn ein User dann personalisierte News abrufen möchte, soll das so funktionieren:

1) Das Script holt sich alle Themen mit den Bewertungen des Nutzers aus der DB.

2) ...

Wie würdet ihr das System in PHP mit MySQL realisieren? Ich würde diese DB-Struktur nehmen. Aber gibt es vielleicht noch eine bessere?

User | Thema | Bewertung

User+Thema = Unique

Wenn ein Nutzer einen Artikel als gut bewertet, werden alle Themen des Textes in der DB mit dem User verknüpft, z.B.

"INSERT INTO interessen (user, thema, bewertung) VALUES ('abc', 'US-Wahl', '1') ON DUPLICATE KEY UPDATE bewertung = bewertung+1"

Dann könnte ein Datensatz für einen User später so aussehen:

US-Wahl: 84

KfW: 33

Sport: 124

Dallas Mavericks: 7

Um die News zu personalisieren, würde ich dann alle Interessen auslesen. Wie würdet ihr die Daten aber auf die Nachrichten in der DB anwenden?

Meine Idee war: Die ersten 150 News aus der DB auslesen. Wenn US-Wahl als Thema vorhanden, dann Rank = Rank + 84, wenn KfW enthalten, dann Rank = Rank + 33 usw.

So hätte die Nachricht mit den meisten enthaltenen Themen, die interessant sind, den höchsten Rang. Man müsste aber immer sehr viele News und alle Interessen auslesen. Gibt es da nicht einen besseren Weg?

Gibt es vielleicht gute Algorithmen, die man für dieses Problem nutzen könnte?

Ich hoffe, ihr könnt mir helfen.

[flashpixx]

Du hast Dich schon einmal mit dem Bereich "Data Mining" und dort mit dem Bereich "Frequent Itemsets" beschäftigt?

Phil

[Ocram7]

Danke für deine Antwort!

Bisher hatte ich mich damit noch nicht beschäftigt. Jetzt habe ich aber etwas dazu gelesen.

So wie ich das verstanden habe, kann ich den "Apriori-Algorithmus" nutzen, richtig?

In einer MySQL-Abfrage könnte man den Algorithmus doch so nutzen, oder?

SELECT warenkorb1.eintrag, warenkorb2.eintrag, COUNT(*) FROM warenkorb1, warenkorb2 WHERE warenkorb1.id = warenkorb2.id AND warenkorb1.eintrag < warenkorb2.eintrag GROUP BY warenkorb1.eintrag, warenkorb2.eintrag HAVING COUNT(*) >= 5

Wie kann ich diesen Algorithmus denn auf mein Problem anwenden?

[AndiE]

Ich würde so vorgehen.

Es ist aber nur Pseudocode.

eine Klasse "Themen" enthält N numrische Felder, deren Namen die vorkommenden Themen sind.

Die Klasse "Artikel" enthält den Text und ein Objekt der Klasse "Themen", wobei die angesprochenen Themen ungleich 1 sind, die anderen 0.

Die Klasse Nutzer enthält die Persönlichen Daten und auch ein Objekt der Klasse "Themen".

Ruft der Nutzer einen Artikel auf, dann erhöhen sich:

1. die angesprochenen Themen in der Klasse "Themen" des "Artikels"

2. die angesprochen Themen in der Klasse "Themen" des "Nutzers"

1. Sortiere die Inhalte von "Themen" von "Nutzer" der Größe nach abwärts.

für die Anzahl der Themen, die größer als 0 sind:

Suche n Liste alle Artikel für die die Anzahl der Themen von Nutzer größer als Null

sind.

lösche das Thema mit der höchsten Zahl

nochmal

[Ocram7]

@flashpixx: Danke für den guten Tipp! Frequent Itemsets sind wirklich interessant. Mir ist aber jetzt aufgefallen, dass man Frequent Itemsets nur für "Ich schließe vom Verhalten eines Nutzers auf das eines anderen Nutzers" benutzen kann. Also z.B.: Wer Nachricht 1 gelesen hat, hat auch oft Nachricht 6 gelesen. Da der User Nachricht 1 gelesen hat, empfehle ich ihm also Nachricht 6.

Für Empfehlungen, die auf Themen basieren, kann man Frequent Itemsets nicht verwenden, oder?

@AndiE: Die Idee scheint ganz gut zu sein. Ich habe aber noch nicht alles genau verstanden. Deshalb hab ich noch ein paar Fragen:

1) Wieso erhöht man beim Aufruf eines Artikels die Themen in der Klasse "Artikel"? Bei der Klasse "Nutzer" ist es ja klar, weil man so das Interesse messen will.

2) "Sortiere die Inhalte von "Themen" von "Nutzer" der Größe nach abwärts" => Man erhält also eine Liste mit den Themen, die der Nutzer am interessantesten findet, richtig? Z.B.: "Sport(73), Politik(32), Kultur (29), Wirtschaft(12), Musik(0)"; Hab ich das richtig verstanden?

3) Deinen letzten Schritt verstehe ich überhaupt nicht. Man weiß ja, welche Themen der Nutzer interessant findet. Aber wie bekommt man dann die Artikel, die dazu passen?

[AndiE]

Hallo,

1. Auch der Webmaster will wissen, welche Artikel am meisten angeklickt wurden, welche Themen also die Nutzer insgesant am meisten interessieren.. Deshalb weiß jeder Artikel, wie oft er angeklickt wude, und die Themen, für die er steht.

2. Die Ausgabe soll Artikel ausgeben:

1. alle für den Nutzer interessanten Artikel(Themen sind größer null), die Element max enthalten

2. alle die Element max-1 enthalten, außer die unter 1. angezeigten

usw.

Dabei ist Element max, das meistangeklickte Element, Element max-1 das zweithäufigst angeklickte Element usw.

[Ocram7]

OK, ich hoffe, ich hab es jetzt endlich verstanden. Ich mache mal ein Beispiel, sag mir bitte, ob das so richtig ist:

Nutzer X interessiert sich für die folgenden Themen:

- "Politik": 823 Mal angeklickt

- "Sport": 233 Mal angeklickt

- "Technik": 229 Mal angeklickt

- "Kultur": 125 Mal angeklickt

Also ist max=Politik und max-1=Sport

Ich hole für den User alle Artikel aus der Datenbank, bei denen Politik > 0 ist (1. Schritt). Dann hole ich alle Artikel, bei denen Sport > 0 ist (2. Schritt).

Ist das so richtig? Dann berücksichtigst du ja nur die beiden interessantesten Themen, den Rest ignorierst du?!

[AndiE]

Ne, darum steht ja dadrunter usw- und so weiter:

Beispiel:

" Die Bundesregierung beschließt: Die deutsche Sportförderung erhält mehr Geld", dann werden die Themen "Sport" und "Politik" berührt.

Bei der Auswertung durchläuft du die schleife solange bis alle relevanten Themen abgearbeitet sind.

1. zuerst die das Top-Theam enthalten.

2. dann die die das 2. Thema enthalten, aber noch nicht genannt sind

3. die das 3. Thema enthalten, aber noch nicht genannt sind

4.

...

N. die das unwichtigste Thema enthalten, und noch nicht genannt sind.

[Ocram7]

Danke, jetzt hab ich es verstanden!

Die Lösung würde funktionieren, das stimmt. Aber das wäre doch von der Performance her nicht gut, oder? Das Script müsste dann - je nachdem wie viele Artikel zu den Themen passen - in jedem Durchlauf über 100 Datensätze aus der DB holen. Das dauert doch ewig ...

Vielleicht geht es auch nicht besser. Ich weiß es nicht. Dann müsste man eventuell Alles vorberechnen lassen (CronJobs).

[ait]

Hallo,

mehr Infos und Referenzen auf Fachliteratur zum Thema "Recommendation Engines" findest Du hier.

[Ocram7]

Danke für den Link! Ich werde mir die Fachliteratur mal ansehen. Aber ich denke mal, dass darin nur das Empfehlen selbst behandelt wird, nicht mein Problem, also die Umsetzung mit PHP und MySQL.

Ich hab noch eine Seite gefunden:

Salmon Run: Pandora - Music Classification and Personalization

Da findet man zwei kurze Code-Schnipsel. Meint ihr, dass man die für mein Problem verwenden könnte? Da wird der Euklidischer Abstand genutzt.