Im vorherigen Artikel “Das könnte Ihnen auch gefallen – So funktionieren moderne Empfehlungssysteme” wurde das Collaborative Filtering (CF) kurz erläutert. Dieser Artikel baut inhaltlich darauf auf und lässt die zu Grunde liegende Idee in wenigen Worten zusammen: Es gibt zwei verschiedene Vorgehensweisen: User- und Item basiertes CF. Beim User basierten CF werden Produkte empfohlen, die von ähnlichen Kunden erworben wurden. Beim Item basierten CF werden Produkte empfohlen, die den bereits erworbenen Produkten des Kunden ähneln. In beiden Fällen basiert die Berechnung der Ähnlichkeit darauf, welche Produkte von welchen Usern gekauft wurden. In diesem Artikel werde ich zunächst auf Schwächen vieler CF Verfahren eingehen. Im Anschluss werde ich Ideen entwickeln, wie mit diesen Schwächen umzugehen ist. Dies resultiert schlussendlich in einer weiteren Technik: dem Cross-Occurrence Empfehlungssystem.

Wo kommt das “normale” Collaborative Filtering an seine Grenzen?

Ein generelles Problem vieler Empfehlungssysteme tritt zu Beginn auf, wenn nur wenige Informationen über die Kunden vorhanden sind. Dieses “Kaltstartproblem” existiert in verschiedenen Formen. In der Startphase des Systems, wenn also noch gar keine Daten von Kunden vorhanden sind, wird es häufig durch ein alternatives Empfehlungssystem überbrückt. Dieses basiert nicht auf der Auswertung von Nutzerverhalten, sondern auf manuell erstellten Empfehlungen. Aber auch wenn das System schon lange Zeit läuft, kann es lückenhaft sein. Wenn ein unbekannter Nutzer die Seite besucht, liegen noch keinerlei Informationen über ihn vor. Demnach ist es unmöglich, ihm personalisierte Empfehlungen auszusprechen. Die bislang beschriebenen Verfahren können erst funktionieren, sobald der Nutzer ein Produkt gekauft hat. Dabei weiss man eigentlich schon viel früher, woran der potentielle Kunde interessiert ist, denn mit jedem Klick den er tätigt verrät er etwas über sich. Das können Suchanfragen sein, Likes, Dislikes oder andere Bewertungen, Kommentare, Rezessionen, oder je nach Kontext der Plattform noch sehr viel mehr. Am einfachsten zugänglich ist sicherlich die Information, welche Produktseiten sich der Nutzer angesehen hat, deswegen werde ich mich im folgenden darauf konzentrieren.

Nicht nur für neue Nutzer ist es sinnvoll mehr als nur die Einkäufe in die Analyse des Nutzerverhaltens mit einzubeziehen. Angenommen, ein treuer Kunde hat Interesse an einem neuen Kühlschrank. Es ist sehr unwahrscheinlich, dass ein System dieses Interesse alleine seinem bisherigen Kaufverhalten entnehmen kann. Doch sobald Produktseiten von Kühlschränken aufgerufen wurden, lässt sich das Interesse erahnen. Darüber hinaus kann es noch viele andere weniger offensichtliche, aber dennoch interessante Muster im Nutzerverhalten geben, welche sich für sinnvolle Empfehlungen eignen. Deswegen ist es, solange man dabei sorgfältig vorgeht, immer sinnvoll, möglichst viele relevante Daten für das Empfehlungssystem zu nutzen.

Anforderungen an ein dimensionsübergreifendes Empfehlungssystem

Wie lassen sich nun die bislang behandelten Verfahren so erweitern, dass man das Nutzerverhalten über verschiedene Dimensionen der Interaktion hinweg analysieren kann? Die einfachste Möglichkeit ist sicherlich, alle Dimensionen zusammenzuführen. Also das Betrachten eines Produkts genau gleich zu werten wie ein Kauf. Dies hätte aber den Nachteil, dass das Ergebnis verwässert wird, denn zwischen dem Betrachten und dem Kaufen besteht ein gewaltiger Unterschied. Es entgehen einem so interessante Nebeneffekte. Es kann zum Beispiel sein, dass viele Nutzer sich ein bestimmtes Produkt ansehen aber aufgrund von schlechten Rezessionen zu einem Konkurrenzprodukt greifen. Das System sollte in der Lage sein dies zu erkennen und Betrachtern des unbeliebten Produkts das beliebte Produkt vorschlagen.

Eine zufriedenstellende Lösung muss in der Lage sein, Zusammenhänge zwischen den Dimensionen der Interaktion zu finden. Keine der bislang von mir beschriebenen Verfahren ist dazu ohne weiteres in der Lage. Doch wenn man sich die zu Grunde liegende Idee des Item oder User basierten Collaborative Filterings ansieht, ist es überraschend einfach, die Verfahren dementsprechend zu erweitern. Diese basierten immer auf dem Vergleich von Items oder von Usern. Eine Erweiterung des User basierten CF besteht darin, die User nicht nur aufgrund ihres Einkaufverhaltens zu vergleichen, sondern die gesamte Interaktion in den Vergleich mit einzubeziehen. Auf die Item basierten Verfahren lässt sich dies nur übertragen, wenn sich jede Interaktion eindeutig auf ein bestimmtes Produkt zurückführen lässt. In beiden Fällen ist es nicht offensichtlich, welches Ähnlichkeitsmass für den Vergleich benutzt werden soll oder wie die unterschiedlichen Dimensionen der Interaktion für den Vergleich zu gewichten sind. Folgende Grafik zeigt, auf welchen Werten der Vergleich der User bzw. der Items basiert.

Links: User Similarity zwischen zwei Usern basierend auf verschiedenen Interaktionen (“View” und “Purchase”) mit verschiedenen Produkten. Rechts: Item Similarity zwischen zwei Produkten basierend auf den verschiedenen Interaktionen verschiedener User.

Die Item Similarity ist in diesem Fall leider überhaupt nicht zielführend. Dies wird in folgendem Szenario deutlich. Angenommen, ein neuer User hat sich ein bestimmtes Produkt angeschaut. Das Item Similarity Empfehlungssystem sucht daraufhin nach Produkten, die diesem Produkt ähneln. Eine Ähnlichkeit lässt in diesem Fall aber keine Rückschlüsse auf eine erhöhte Einkaufswahrscheinlichkeit zu, denn die Ähnlichkeit kann auch bedeuten, dass die Produkte oft gemeinsam betrachtet wurden. Ein solches Verfahren findet lediglich ähnliche Produkte im Bezug auf die Nutzerinteraktion über viele Dimensionen hinweg, kann aber keine dimensionsübergreifenden Empfehlungen aussprechen.

Mit dieser Erkenntnis muss das eigentliche Ziel nochmal durchdacht werden. Sollen tatsächlich Produkte empfohlen werden? Ja, aber nicht nur. Es sollen Produkte zum Kaufen empfohlen werden! Oder noch allgemeiner: Produkte zusammen mit einer Interaktion. Übertragen auf das Item basierte Collaborative Filtering bedeutet das, dass ein Item nun ein Tupel bestehend aus Produkt und Interaktion ist. Und anstelle der Ähnlichkeit zwischen zwei Produkten basierend auf den User Interaktionen wird die Ähnlichkeit zwischen zwei solcher Tupel berechnet, ebenfalls basierend auf den User Interaktionen. Folgende Grafik zeigt den dimensionsübergreifenden Vergleich.

Ähnlichkeit zwischen zwei Produkt/Interaktions Tupel. V 1 ist die Interaktion “View” auf Produkt 1, P 2 ist die Interaktion “Purchase” auf Produkt 2. Ein hoher Ähnlichkeitswert bedeutet in diesem Beispiel, dass viele User, die Produkt 1 betrachtet haben das Produkt 2 gekauft haben.

Damit lässt sich das Item basierte Collaborative Filtering ganz normal anwenden. Für das aussprechen einer Empfehlung für einen User werden alle seine Produktinteraktionen mit allen möglichen Produktinteraktionen verglichen. Die ähnlichsten Produktinteraktionen werden ihm dann empfohlen. Üblicherweise fokussiert man sich hier allerdings auf Kaufempfehlungen.

Cross-Occurrence Empfehlungssystem

Wie lässt sich das nun am besten in die Praxis umsetzen? Beim normalen Item basierten CF ist das Co-Occurrence Empfehlungssystem eine einfache aber effektive Lösung, die sich ausserdem sehr gut mit Hadoop/MapReduce parallelisieren lässt. Als Ähnlichkeitsmass wird dabei gezählt, wie oft zwei Produkte gemeinsam gekauft wurden. Die Mathematik dahinter lässt sich direkt auf dimensionsübergreifende Empfehlungen übertragen. Ein solches System ist ein Cross-Occurrence Empfehlungssystem. Das Ähnlichkeitsmass funktioniert identisch. Es wird gezählt, wie häufig Interaktion A auf Produkt X gemeinsam mit Interaktion B auf Produkt Y vorkommt. Die Machine Learning Library Mahout enthält eine fertig implementierte Co-Occurrence Recommendation Engine, die sich auch für die Berechnung von Cross-Occurrence Empfehlungen einsetzen lässt. Die Idee der Cross-Occurrence entstammt einem Vortrag von Ted Dunning.

Im folgenden Beispiel demonstriere ich die für das Cross-Occurrence Empfehlungssystem notwendigen Berechnungen.

Ausgangspunkt ist die User / Action-Item Matrix A. Sie gibt nicht nur an, welcher Nutzer welches Produkt gekauft hat (Purchase, kurz P), sondern auch, welche er sich angesehen hat (View, kurz V).

User / Action-Item Matrix: Diese gibt für jeden User an, welche Produkte gekauft und welche Produkte angeschaut wurden. Wenn ein User ein Produkt betrachtet aber nicht gekauft hat, ist dies farblich hervorgehoben

Genau wie bei der Co-Occurrence lässt sich durch eine einfache Matrizenmultiplikation die Cross-Occurrence Matrix bestimmen: S = A^T*A. Die untere Hälfte der quadratischen Matrix wird hier ignoriert, da nur umsatzbringende Interaktionen (P) von Interesse sind.

Die Cross-Occurrence Matrix gibt an, wie oft alle Interaktion/Produkt Kombinationen gemeinsam vorkommen. Die farblich hervorgehobenen Einträge zeigen, dass das Betrachten von Produkt 1 oder 2 die Wahrscheinlichkeit für eine Empfehlung von Produkt 3 oder 4 erhöhen.

Durch eine erneute Multiplikation mit der User / Action-Item Matrix erhält man die Empfehlungen R = S*A^T = A^T*A*A^T:

Ein hoher Wert in der Empfehlungsmatrix gibt an, dass dem User ein bestimmtes Produkt empfohlen werden sollte. Die Einträge für bereits gekaufte Produkte sind ausgegraut.

Aus dieser Empfehlungsmatrix lassen sich direkt Empfehlungen für die Nutzer ablesen. User 3 würde man aufgrund dieses Ergebnisses eher zum Kauf von Item 4 als zum Kauf von Item 3 raten.

Fazit

Vielseitigere Informationen über Nutzer erhöhen die Qualität eines personenbezogenen Empfehlungssystems in mehrerer Hinsicht. Vor allem bei neuen Kunden lassen sich viel früher aussagekräftige Empfehlungen aussprechen. Auch bei Bestandskunden steigt die Relevanz und die Aktualität der Empfehlungen. Mit dem Cross-Occurrence Empfehlungssystem habe ich eine einfache Technik vorgestellt, die dimensionsübergreifende Informationen auswerten kann. Das Ergebnis der Beispielrechnung bietet im Vergleich zu einem eindimensionalen Empfehlungssystem wenig Mehrwert. Dies liegt aber aber vor allem an der geringen Grösse des verwendeten Datensatzes und daran, dass die Informationen in beiden Dimensionen fast identisch sind. In einem realistischen Szenario mit vielen Produkten, vielen Usern, einer dünnen User / Action-Item Matrix und deutlich mehr “Views” als “Purchases” ist ein vielseitigeres System deutlich überlegen. Es lässt sich ein umfassendes Profil über die Nutzer erstellen was in sehr zielgerichteten Empfehlungen resultiert.

Über Fragen und Anregungen zu diesem Artikel freue ich mich sehr. Kontaktiert mich einfach per E-Mail oder schreibt einen Kommentar. Wenn Sie selber planen ein Empfehlungssystem einzuführen, kann die YMC AG Sie bei der Planung und bei der Umsetzung unterstützen.

0 Kommentare

Einen Kommentar abschicken

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *