Recommendation Engine

[FabianLurz]

Hallo,
ich entwickle gerade eine Recommendation Engine. Diese hat die Aufgabe, Items (also bspw. Filme) in Vektoren zu wandeln (ein Vektor beschreibt dann einen Film) und diese Vektoren mit allen anderen Vektoren zu vergleichen. Dann werden Korrelationen berechnet und in die DB geschrieben. Man kann sich nun vorstellen, dass bei 817k Filmen eine Menge zusammen kommt und es müssen 817k * 817k -817k Korrelationen berechnet werden.
Das Problem das ich nun habe ist, dass ich keine andere Möglichkeit sehe, als erst alle Filme einzulesen, dann Vektoren zu bilden, dann Korrelationen zu berechnen. Dabei wird natürlich viel Speicher gebraucht und ein Stream wäre wohl schöner. Aber da ich ja alle Filme benötige um die Korrelationen zu berechnen, nützt mir ein Stream nichts ?! Seht ihr noch andere Möglichkeiten? Evtl. ist es noch etwas zu ungenau formuliert....wenn es unverständlich ist, bitte sagen
Gruß und Danke im voraus
Fabian

 

[Kevin94]

Also, wenn du jeden Film mit jedem vergleichen willst/musst, dann wirst du so vorgehen müssen.

Wenn du hier von Mathematischen Vektoren redest, dann dürfte das mit dem Arbeitsspeicher gerade noch hinhauen, ansonsten müsstest du das ganze in Blöcke auf teilen und erst jeden Block "in sich vergleichen" und dann immer 2 Blöcke laden und alle aus dem einen Block mit allen aus dem anderen Block vergleichen. Was du hier mit Streams willst (ausser zum Zwichenspeichern auf Platte) kann ich nicht nachvollziehen.

Was mir jetzt so nachträglich auffält wenn du für jede Korrelation einen Datensatz anlegst, bei 817_000 Filmen, dann hast du am ende grob 667.489.000.000 Datensätze, ginge man von (übertriebenen) 256Byte pro Datensatz aus, wären das 170 TB. Mal im ernst 170 T e r r a B y t e und selbst bei einem Byte pro Datensatz wäre es noch 670 GB, ich glaube da musst du dir was anderes einfallen lassen, das verträgt ja keine Datenbank, selbst wenn du einen Server auftreibst, der dir annährend genug Speicher zur Verfügung stellt.

 

[Guybrush Threepwood]

1. Eine Frage: Wie berechnest Du für einen Film einen Vektor? Bei semantischem Material könnte man ja LSA oder so nehmen. Oder machst Du das mit den Film-Beschreibungen?

2. Wenn Du für jeden Film bereits einen Vektor hast, ist es möglicherweise einfacher, bei einer Anfrage zu einem bestimmten Vektor einfach die Korrelationen zu den anderen 817k Filmen durchzurechnen. Das sollte bei modernen Rechner maximal wenige Sekunden dauern und beim Abruf der Datenmenge aus einer DB musst Du mit der gleichen Dauer rechnen. Die Vektoren müsstest Du natürlich im Speicher halten. Wieviele Dimensionen hat Dein Vektorraum? Wenn es nicht zu viele Dimensionen sind, dann könnte auch eine 32Bit-Maschine reichen. Ansonsten eben 64Bit um mehr als 4GB addressieren zu können.
Der Vorteil wäre, dass Du die Datenbasis leicht erweitern könntest. Du müsstest nur neue Vektoren hinzufügen. Die Berechnung würde ja dann einzeln durchlaufen. Ansonsten wäre es immer nötig, alle anderen 817k Filme "upzudaten" (ich liebe die deutsche Sprache).

P.S.: Man könnte über Clustering-Verfahren den Vektorraum auch in Sektoren einteilen und dann lediglich innerhalb eines Sektors rechnen. Das würde unheimlich viel Berechnungen sparen.

P.P.S: Du musst gar nicht alle Filme im Speicher präsent halten. Es reicht, der Reihe nach einen einzelnen Film einzulesen (wie auch immer Du vorgehst) und den Vektor zu berechnen. Den Vektor behälst Du, den Film dagegen nicht im Speicher. So solltest Du Stück für Stück eine sehr sparsame Repräsentation der Filmbasis aufbauen können. Die Berechnung passier dann ausschließlich mit den Vektoren.

 

[FabianLurz]

Hallo
super Danke für die Antworten. Der Ausmaße der DB bin ich mir bewusst. Du musst aber auch noch sehen, dass nur Filme mit überdurchschnittlicher Korrelation behalten werden (also werden es wohl etwas weniger als die Hälfte sein). Tatsächlich wird es auch so gemacht wie beim 2 Thread...d.h. Filme werden in Vektoren gespeichert (sind meine ich jetzt integer Vektoren) und dann verglichen.
Das mit den Sektoren finde ich spannend und werde mir da auf jeden Fall etwas durchlesen.
Für eine Recommendation Engine dieser Ausmaße (die ich also benötige) ist das aber wohl die beste Möglichkeit; offline Berechnung der Korrelationen unter den Items. Das das sehr viel Speicher benötigt...damit muss man dann leben Ich sage nochmal Bescheid, wenn ich alles eingelesen habe. Bin gerade dabei alles einzulesen. Schreiben wird noch etwas dauern. Bin mal gespant wie groß das wird.

 

[ssoul26]

Was mich wundert 817k Filme??? Wirklich??

 

[FabianLurz]

Ich werde jetzt erst mal nur die deutschen Filme nehmen. Das sind ca. 67k. Wenn man aber alle Filme nimmt sind es tatsächlich 817k....keine Serien inbegriffen.
Ja naja das ist nicht ganz einfach zu lösen....man benötigt wirklich vernünftige Hardware und man muss sich was einfallen lassen, diese Datenmengen zu bewältigen

 

[ssoul26]

Diese "Korrelationen" werden die nur einmalig berechnet und angelegt? Ich gehe mal davon aus, dass dies immer nur ein einmaliger Vorgang ist? Wird ja wohl nicht ständig neu gebildet, oder? Und was willst du zum Schluss erreichen? Das wäre mal interessant.

 

[FabianLurz]

Hey,
ja also das wird einmalig berechnet; es sei denn, es kommen neue Filme hinzu. Dann muss man natürlich alles neu berechnen.
Was ich damit vorhabe:
Recommendation Service (also Empfehlungsdienst). Genaueres darf ich leider nicht sagen Aber wenn man sich amazon anschaut, weiß man ja denke ich was gemeint ist
Gruß Fabian

 

[fastjack]

Ich würde das auch on demand berechnen (wenn die Berechnung nicht zu teuer ist). Für den Betrieb würde ich diese Berechnungen dann in einer Art mixed LRU/TTL Cache (also capped und mit expiring, vlt. expire Prüfung beim get() oder so, also ohne Threads) speichern. Dann hast Du z.B. immer ein Hotset von 1000 Vergleichen (halt alle Vergleiche, die sehr oft angefragt werden) im Speicher, was sich nach den Anfragen der User dann selbst zusammenstellt.

 

[FabianLurz]

Also on demand wird ausgeschlossen
Stell dir mal vor, du hast 1 mio. Produkte. Daraus willst du on demand Korrelationen berechnen. Man muss dann für jedes Produkt weitere Informationen auslesen (Genre,Actor etc.). Da wird die Datenmenge gleich x-fach erhöht.
Für diese on demand Berechnung bräuchte man gigantische Serverfarmen (und das ist wirklich nicht übertrieben) um eine vernünftige Responsetime zu erlangen.
Offline-Berechnung bedarf im Endeffekt nur eine hohen Festplattenkapazität....aber die ist wohl günstiger wie enorme Ramkapazität und enorme CPU-Power.
Da diese Engine hochskalierbar sein muss/soll und es amazon genauso gemacht hat halte ich das für den besseren Weg Natürlich ist es immer ein schlechtes Argument zu sagen "der hat es auch so gemacht". Aber da es sich um amazon handelt kann man dieses Argument denke ich gelten lassen

 

[andiv]

Hast du schonmal nach (wissenschaftlichen) Veröffentlichungen zum Thema Recommendation gesucht?

Ich hab jetzt mit den Stichworten "recommendation amazon" bei Google Scholar zum Beispiel
http://www.cs.umd.edu/~samir/498/Amazon-Recommendations.pdf gefunden. Ich hab das ganze jetzt nur überflogen, aber es sieht hilfreich aus, wenn man sich dafür interessiert wie Amazon das macht. Über die referenzierten Paper findet man bestimmt noch mehr.

Ich kann mir irgendwie nicht vorstellen, dass man wirklich alle Korrelationen speichert. Das muss doch riesige Datenmengen ergeben. Ich würde intuitiv versuchen die Filme in Kategorien zu ordnen bzw. zu taggen und dann die Korrelationen nur noch auf Kategorie-Ebene und innerhalb der Kategorien zu berechnen. Aber das ist jetzt nur eine spontane Idee...

 

[FabianLurz]

Hey,
also es fallen schon eine Menge Korrelationen weg
Ich habe mir auch schon sehr viele wissenschaftliche Texte zu diesem Thema durchgelesen....so genau war es meist nicht.
Ich finde auch, dass mir schon gut geholfen wurde. Natürlich ist es schwer zu helfen, bei einem derart komplexen Thema. Dafür benötigt man ja meist auch viel Vorwissen.
Ich werde jetzt "SparseMatrix" verwenden und die Korrelationen entweder zur Laufzeit berechnen oder eben wie schon erwähnt in byte speicher (bzw. shortint).
Mit den Kategorien hast du im Prinzip recht....es wird aber schon automatisch gemacht. Da eben nur Korrelationen gespeichert werden die überdurchschnittlich sind (und das sind sie eben bie bspw. gleichem Genre). 817k*817k-817k war nur eine grobe Schätzung, damit ich weiß, wieviel Arbeitsspeicher ca. benötigt wird (817k sind ja noch nicht wirklich viele Daten).
Gruß Fabian

 

[fastjack]

Schau mal auch nach Cassandra und Hadoop und Co, wir haben mit beiden Systemen sehr gute Erfahrungen in Bezug auf riesige Datenmengen gemacht.

 

[Ark]

@FabianLurz: Ich habe (schon vor über einer Woche) in diesem Thread ein paar Fragen gestellt, deren Beantwortung wohl sehr helfen könnte/sollte/dürfte/würde.

Ark

 

[DoofesPW]

Was genau meinst du denn mit "Korelationen"? Die Ähnlichkeit zweier Filme? Falls dem so ist, könntest du das Finden von ähnlichen Filmen auf das Nearest-Neighbor-Problem in einem k-d-Tree reduzieren.