Die Bedeutung von Empfehlungssystemen für moderne e-Commerce Plattformen ist in den letzten Jahren rasant gestiegen. Marktführer Amazonmacht seinen Kunden schon lange nutzerspezifische Vorschläge. Viele andere Shops, darunter unter anderem Ebay oder OTTO, sind inzwischen nachgezogen.

Nicht nur für Shops sind Empfehlungssysteme von Bedeutung. Beispielsweise bekommen die Nutzer von YouTube Videos vorgeschlagen und Online Radios wie Last.fm gehen noch einen Schritt weiter und empfehlen nicht nur Songs, sondern erstellen ganze Wiedergabelisten aufgrund der Hörgewohnheiten.

Die Techniken, die hinter den Empfehlungssystemen stehen, werden unter dem Begriff Collaborative Filtering (CF) zusammengefasst. Diese Verfahren haben alle gemein, dass den Empfehlungen keine expliziten Informationen wie Alter oder Geschlecht und auch keine manuell erzeugten Hervorhebungen einzelner Artikel zu Grunde liegen. Statt dessen basieren sie ausschließlich auf den Interaktionen der Nutzer. Dazu wird nicht nur das Verhalten des aktuellen Nutzers analysiert. Vielmehr geht die Interaktion aller Nutzer in die Erstellung der Empfehlungen mit ein.

Man unterscheidet zwischen zwei Arten des Collaborative Filtering, User basiert und Item basiert, auf die ich im Folgenden genauer eingehen möchte.

User basierte Verfahren machen Vorschläge aufgrund des Verhaltens ähnlicher User. Dazu muss zunächst die Ähnlichkeit zwischen allen Usern bestimmt werden. Dem User werden Produkte empfohlen, die von den zu ihm ähnlichsten Usern gekauft wurden. Für die Berechnung der Ähnlichkeit zweier User wird deren Kaufverhalten der Vergangenheit ausgewertet. Leider ist es nicht trivial zu entscheiden, welches Ähnlichkeitsmaß hierfür am besten geeignet ist und wieviele Nutzer für die Erstellung der Vorschläge berücksichtigt werden sollen. Da die Berechnung der Similarity Matrix sehr aufwändig sein kann, sollte sie im Vorraus erfolgen. Die Similarity zweier User ist leider sehr instabil, denn sie kann nur von wenigen Interaktionen abhängen. Dies hat zur Folge, dass die letzten Aktivitäten, welche eigentlich von besonderer Bedeutung sein sollten, nicht in die Empfehlungen mit einfließen. Mehr zu verschiedenen Ähnlichkeitsmaßen und unter welchen Einschränkungen sich ein solches System doch in Echtzeit realisieren lässt, werde ich in einem zukünftigen Artikel schreiben.

Die Idee des User basierten Collaborative Filterings angewandt auf User 2. Wegen der Ähnlichkeit zu User 1 wird ihm das linke Dokument empfohlen.

Item basierte Verfahren haben diesen Nachteil nicht. Diese empfehlen dem User Produkte, welche ähnlich zu bereits von ihm gekauften sind. Die Ähnlichkeit bezieht sich nicht auf Produkteigenschaften, sondern darauf, von welchen Nutzern sie gekauft wurden. Hier ist es sinnvoll, die Item Similarity Matrix im Vorraus zu berechnen. Diese ist wesentlich stabiler als die User Similarity Matrix, weswegen Item basierte Verfahren trotz Vorberechnung für aktuelle Empfehlungen geeignet sind.

Die Idee des Item basierten Collaborative Filterings angewandt auf User 2. Das linke Dokument hat große Ähnlichkeit zu 3 bereits bekannten Dokumenten. Deswegen wird es empfohlen

Co Occurrence Empfehlungssysteme sind den Item basierten Verfahren unterzuordnen. Anstelle für jeden Eintrag der Item Similarity Matrix mit einer mal mehr, mal weniger geeigneten Metrik die Ähnlichkeit zu bestimmen, wird einfach gezählt, wie oft die beiden Produkte gemeinsam gekauft wurden. Dies wird im folgenden erläutert:

Die User/Item Matrix A gibt für jeden User die gekauften Produkte an.

Daraus lässt sich recht einfach die Item Co Occurrence Matrix S ableiten. Diese gibt an, wie häufig zwei Produkte gemeinsam gekauft worden. Am einfachsten geht das mit einer Matrizenmultiplikation S = A^T * A

Um Empfehlungen zu erhalten, muss die Co Occurrence Matrix noch einmal mit der transponierten User/Item Matrix multipliziert werden: R = S*A^T = A^T*A*A^T

Bereits gekaufte Produkte wurden in der Empfehlungsmatrix ausgegraut. Die übrigen Empfehlungen sind zwar aufgrund der geringen Datenbasis wenig aussagekräftig, es lässt sich aber einfach ablesen, dass man User 3 eher zu Item 4 als zu Item 3 raten sollte.

An dieser Stelle möchte ich kurz einwerfen, dass die notwendigen Matrizenmultiplikationen je nach Anzahl der User und Items theoretisch eine sehr hohe Berechnungskomplexität und einen sehr hohen Speicherbedarf haben können. Diese Berechnungen lassen sich allerdings sehr gut parallelisieren, zum Beispiel mit Hadoop und MapReduce. Dabei kann zusätzlich davon profitiert werden, dass die verwendeten Matrizen in der Regel sehr dünn sind. Das Mahout Framework enthält eine fertig implementierte Co Occurrence Recommendation Engine basierend auf MapReduce. Mehr Details zu dieser Thematik sind sehr gut in dem Buch “Mahout in Action” beschrieben.

Wenn man einem bislang unbekannten User eine Produktempfehlung machen möchte, kommt dieses System an seine Grenzen. Über eine Session-ID oder Cookie-ID lässt sich zwar ein Profil über betrachtete Produkte erstellen, welches in Kombination mit der Co Occurrence Matrix Empfehlungen liefern kann. Allerdings weiß das System nicht, ob das betrachten eines Produkts häufig zum Kauf führt. Eventuell führt es sogar eher zum Kauf eines anderen. Das kann zum Beispiel der Fall sein, wenn das betrachtete Produkt sehr schlechte Rezessionen hat und deswegen alle potentiellen Kunden zu einem Konkurrenzprodukt gegriffen haben.

Auch für bereits registrierte Nutzer ist es sinnvoll, nicht nur ihre Einkäufe, sondern auch betrachtete Produkte in die Produktempfehlung mit einfließen zu lassen. Dieses Problem lässt sich noch weiter generalisieren. Es ist wünschenswert, jede Art der Interaktion der Nutzer daraufhin zu untersuchen, ob sie zu einer bestimmten anderen Interaktion führt. Insbesondere, wenn dadurch Umsatz generiert wird. Auf einer Videoplattform lassen sich beispielsweise nicht nur die betrachteten Videos auswerten, sondern auch Nutzerkommentare, Likes oder Dislikes.

Wie sich diese Anforderungen in ein Recommendation System einbauen lassen, werde ich in kürze anhand der Cross Occurrence in einem weiteren Artikel erläutern.

Über Fragen und Anregungen zu diesem Artikel freue ich mich sehr. Kontaktiert mich einfach per E-Mail oder schreibt einen Kommentar.

0 Kommentare

Einen Kommentar abschicken

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