Collaborative Filtering

In Form von Empfehlungen auf Amazon kennt jeder Collaborative Filtering Techniken. Hier finden Sie mehr zum Thema und den Anwendungsmöglichkeiten in Unternehmens-Software.

Einleitung

Als zu Beginn der 90er Jahre das Email-Aufkommen zu steigen begann, kamen die Entwickler damaliger Mail-Systeme rasch zu der Erkenntnis, dass für die Verwaltung der Datenmengen, die durch den Verkehr elektronischer Post generiert würden, nur neuartige Filter-Techniken Abhilfe schaffen könnten. So wurde im Zusammenhang mit der Entwicklung des Mail-Systems Tapestry unter dem Begriff Collaborative Filtering (CF) ein neuartiges Filter-Verfahren eingeführt (4). Collaborative Filtering hat sich in den letzten 15 Jahren zu einem Schlagwort sowohl in der Industrie als auch in der Forschung entwickelt. Insbesondere das Web 2.0 und das Aufkommen sozialer Netzwerke haben in den letzten Jahren für einen weiteren Schub gesorgt.

Zunächst findet man den Einsatz von Methoden des CFs insbesondere in Systemen, die dem Benutzer eine Entscheidungshilfe für die nächste Aktion bieten sollen. So stellt sich zum Beispiel für einen Buchhändler die Frage, welche Bücher er dem Kunden vorschlagen soll, um die Kaufentscheidung des Benutzers zu vereinfachen oder zu beeinflussen. Eins der besten Beispiele ist hier sicherlich das Online-Versandhaus Amazon. Aber auch Multimedia-Software wie iTunes oder das Auktionshaus eBay nutzen CF in ihren Systemen.

Wer heutzutage im Internet Waren bestellt, ist es gewohnt, eine personalisierte Empfehlungsliste des Anbieters gezeigt zu bekommen. Die Erstellung einer solchen Liste kann auf diversen Wegen geschehen. Die Voraussetzung ist, dass das System eine Liste vorheriger Transaktionen aller Benutzer zur Verfügung hat. Noch besser ist es allerdings, wenn die Transaktionen zusätzlich mit Bewertungen der Benutzer versehen sind. Die Empfehlungsliste stellt eine Vorhersage dar, welche weiteren Objekte oder Informationseinheiten für den Benutzer von Interesse sind. Kernpunkt ist folgende Idee: Benutzer die in der Vergangenheit ähnliche Entscheidungen getroffen haben, werden dies wahrscheinlich auch in der Zukunft tun. Je ähnlicher Benutzer sind, desto wahrscheinlicher ist es, dass sie die gleichen Entscheidungen treffen. Die hier vorgestellt Technik wird auch Nearest Neighbor genannt, da aus der Gesamtmenge aller Benutzer die ähnlichsten Benutzer gesucht werden. Um ein besseres Verständnis für CF zu bekommen und den entstandenen Hype nachvollziehen zu können, veranschaulicht man sich den Einsatz am besten an einem Beispiel.

Beispiel 1.1 Wenn die Benutzer A, B und C in der Vergangenheit Bücher ähnlich bewertet, bzw. diese gekauft haben, und das System nun vorhersagen will, ob ein bestimmtes Buch für Benutzer C geeignet ist, wird sich das System an den Bewertungen der Benutzer A und B orientieren, sofern die beiden Benutzer das Buch bereits kennen. Je ähnlicher C den Benutzern A und B ist, desto stärker kann deren Bewertung in die Beurteilung einfließen.

Verschiedene Aspekte des CF

Ein CF-System kann verschiedenen Funktionen dienen, wobei häufig zwei besonders hervorgehoben werden (siehe dazu z.B. 7). Zum einen wird häufig eine Liste generiert, die Objekte vorschlägt, die für den Benutzer interessant sind. Die zweite Funktionalität ist die Vorhersage einer Bewertung für ein bestimmtes Objekt durch einen Benutzer.

Ein typischer Flaschenhals in CF-Systemen ist die Suche nach ähnlichen Benutzern. Viele Anwendungen stellen die Anforderungen, dass die Ergebnisse in Bruchteilen von Sekunden berechnet werden. Daraus folgte die Suche nach Verfahren, die es ermöglichen diese rechenintensive Arbeit aufzuteilen, so dass ein Teil vorab berechnet werden kann und so wenig wie möglich online berechnet werden muss. Die Arbeit an solchen Algorithmen führte zu einem weiteren Zweig von Systemen, die nicht mehr die Ähnlichkeit von Benutzern, sondern von Objekten berechnen. In solchen Item-Based-CF-Systemen kann viel der Rechenarbeit vorab geleistet werden (7), was insbesondere in large-scale Anwendungen von großer Bedeutung ist (5). In Fällen wie bei Amazon kommen schnell mehrere Millionen Kunden und um die eine Million Waren zustande. Daher haben sich auch diese Systeme zahlreich in den letzten Jahren etabliert. Allerdings soll hier der Fokus auf dem User-Based-CF liegen, da dies der Ursprung des CF ist. Überschreiten im Falle eines User-Based-CF die Datensätze die Kapazität des Systems, so können in vielen Fällen unwichtige Datensätze (z.B. Benutzer mit sehr wenigen Transaktionen) ausgelassen werden ohne die Genauigkeit der Vorhersage negativ zu beeinflussen. In anderen Fällen müssen Approximationen benutzt werden, die dazu führen, dass die sich die Genauigkeit des Systems verschlechtert.

Alternativ zum CF wird häufig inhaltsbasiertes Filtern verwendet. Dabei werden meistens Benutzer oder Objekte gesucht, die sich aufgrund ihrer spezifischen Eigenschaften und Meta-Daten ähneln. Dabei können natürlich nur die Merkmale berücksichtigt werden, die sich einfach Erfassen oder Abfragen lassen. Die ist insbesondere dann schwierig, wenn die Objekte schwer zugänglich sind, z.B. bei Medien wie Musik oder Filmen. Da sich kollaboratives und inhaltsbasiertes Filtern nicht gegenseitig ausschließen, gibt es diverse Ansätze, die Hybrid-Systeme vorstellen. Diese hybriden Systeme ermöglichen es, die Suche zu verfeinern und einzugrenzen. Verschiedene hybride Ansätze werden zum Beispiel in (1) vorgestellt.

Wie bereits erwähnt, ist eine Voraussetzung für das CF, dass vorherige Transaktionen oder Bewertungen des Benutzers gespeichert worden sind. Aber diese Voraussetzung stellt häufig eine große Hürde dar, da die Benutzer häufig nicht gewillt sind, diese Entscheidungen explizit preiszugeben. Insbesondere im Falle von Bewertungen, müssen häufig zusätzliche Anreize gesetzt werden oder die Bewertung eines Benutzers für ein Objekt implizit erfasst werde.

CF in Unternehmenssoftware

Es gibt unzählige Möglichkeiten CF in Unternehmenssoftware einzusetzen. Hier soll kurz auf zwei Bereiche eingegangen werden und diese nur kurz skizziert werden. Zum einem gibt es in Unternehmen das klassische Problem, die eingehenden Informationen und Nachrichten zu sortieren und zu priorisieren. Systeme wie Tapestry (4) und GroupLens (6) haben bereits vor Jahren gezeigt, dass CF im Bereich der Kommunikation und Informationsverteilung eine bedeutende Rolle spielt. Dies wirft die Frage auf, ob CF nicht auch in Unternehmenssoftware sinnvoll eingesetzt werden kann.

Beispiel 3.1 Jeder Benutzer ist mit einer Füller von eingehenden Nachrichten und verfügbaren Informationen konfrontiert und es stellt sich die Frage, welche Dokumente mit welcher Priorität und Sorgfalt zu lesen. Diese Informationsflut setzt sich unter anderem aus externem und internem Email-Verkehr, Internet und Intranet zusammen. Ein CF-System kann die Verwaltung dieser Informationen übernehmen und dem Benutzer mit einer personalisierten Ansicht Hilfe leisten. Die Bewertung der Ansicht kann hier implizit erfolgen, denn wenn der Benutzer weiterhin zunächst Dokumente aus dem unteren Bereich der Liste auswählt, ist die Ansicht noch nicht optimal auf den Benutzer zugeschnitten.

Ähnliche Ansätze werden zum Beispiel von Google genutzt um Nachrichteninhalte zu personalisieren (2). Zum anderen kann CF auch genutzt werden, um die Bedienung von Software zu vereinfachen. So wird unter dem Begriff Social Navigation zum Beispiel die kollaborative Navigation durch Informationsysteme genannt (siehe z.B. 3).

Beispiel 3.2 In großen Unternehmen, die komplexe Software verwenden, müssen unterschiedliche Benutzergruppen möglichst schnell Worfklows durchlaufen. In solcher Software stellt sich also die Frage, nach der nächsten Aktion, die ein Benutzer ausführen will. Die Komplexität solcher Software verhindert häufig eine optimale Bedienbarkeit und die Navigation zum nächsten Arbeitsschritt braucht Erfahrung. Die verschiedenen Benutzergruppen der Software lassen sich häufig nicht objektiv Klassifizieren, so dass es nicht möglich ist, Bedienungsanleitungen für jede Gruppe zu erstellen. Es wird sich aber dennoch zeigen, dass bestimmte Benutzer immer wieder bestimmte Workflows in der Software durchführen. Diese immer wieder kehrenden Abläufe könnten durch CF schneller zugänglich gemacht werden, indem das System die nächste Aktion vorschlägt. Des weiteren könnten sich durch den Einsatz eines CF-Systems die Benutzer schneller zurecht finden, wenn sich Aufgabenbereiche ändern. Die Voraussetzung, explizite Bewertungen für vorgeschlagene Workflows anzugeben, stellt kein Problem dar, da Mitarbeiter hierzu angewiesen werden können.

Zusammenfassung

CF kommt ursprünglich aus dem Bereich der Kommunikation und hat sein Einsatzgebiet in den letzten Jahren durchgehend erweitert. Die Verfügbarkeit diverser open-source Softwarepakete in verschiedenen Sprachen ermöglicht einen einfachen Einstieg. Hierbei sollte allerdings beachtet werden, dass eine Vielzahl an Design-Entscheidungen großen Einfluss auf die Qualität der Vorhersagen haben und die Beschaffenheit der verfügbaren Daten berücksichtigt werden muss. Für eine ausführliche Einführung in die Thematik ist die Arbeit (8) als lesenswert hervorzuheben.

[1] Robin Burke, Hybrid web recommender systems, The Adaptive Web (2007), 377–408.

[2] Abhinandan S. Das, Mayur Datar, Ashutosh Garg, and Shyam Rajaram, Google news personalization: scalable online collaborative filtering, WWW ’07: Proceedings of the 16th international conference on World Wide Web, ACM, 2007, pp. 271–280.

[3] P. Dourish and M. Chalmers, Running out of space: Models of information navigation, HCI, Glasgow, 1994.

[4] David Goldberg, David Nichols, Brian M. Oki, and Douglas Terry, Using collaborative filtering to weave an information tapestry, Commun. ACM 35 (1992), no. 12, 61–70.

[5] Greg Linden, Brent Smith, and Jeremy York, Amazon.com recommendations: Item-to-item collaborative filtering, IEEE Internet Computing 7 (2003), no. 1, 76–80.

[6] Paul Resnick, Neophytos Iacovou, Mitesh Suchak, Peter Bergstrom, and John Riedl, Grouplens: An open architecture for collaborative filtering of netnews, CSCW ’94: Proceedings of the 1994 ACM conference on Computer supported cooperative work, ACM Press, 1994, pp. 175–186.

[7] Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl, Item-based collaborative filtering recommendation algorithms, WWW ’01: Proceedings of the 10th international conference on World Wide Web, 2001, pp. 285–295.

[8] J. Schafer, Dan Frankowski, Jon Herlocker, and Shilad Sen, Collaborative filtering recommender systems, The Adaptive Web (2007), 291–324.