ASDL:Recommendersysteme

From Wiki

Aufgaben von Recommender-Systemen / Motivation

Recommender-Systeme sind Empfehlungssysteme, die den Nutzer bei der Entscheidungsfindung unterstützen sollen. Die Empfehlungen werden automatisch generiert. Die Schlußfolgerung findet auf Basis von vorhandenen Daten statt.

Man möchte eine bessere und effizientere Nutzung der immer weiter wachsenden Informationsmenge des WWW, da die eigene Recherche ohne fremde Hilfe immer schwieriger wird. Aber Suchmaschinen sind (noch) nicht personalisiert genug bei Darstellung und Suche.

Recommender-Systeme werden zum Beispiel im E-Commerce, E-Learning oder in Informations- und Nachrichtenportalen eingesetzt. Auch das von uns entwickelte ASDL-Tool kann man als Recommender-System bezeichnen.

Bild 1: Der grundlegende Aufbau eines Recommender-Systems. Auf Basis der gespeicherten Hintergrunddaten und des User-Inputs werden die Empfehlungen berechnet.¹

Arten von Recommender-Systemen

Inhaltsbasiert (content-based filtering):

Ähnlichkeit von Objekten wird über deren Eigenschaften bestimmt. Das System sucht also Objekte heraus, deren Attribute identisch oder ähnlich zu den bisher positiv bewerteten sind. Das content-based filtering hat seinen Ursprung im Information Retrieval. Es wird meistens für Textdokumente angewendet, Objekte sind dann Dokumente mit Textinhalten. Diese Technik findet in der Praxis Anwendung bei Bibliotheken, Webseiten, Informationsportalen oder Newsgroups. Algorithmen zur Berechnung sind z.B. das Boolean Matching und das Vektorraummodell.

Beim Boolean Matching ist die Relevanz abhängig von der Existenz bestimmter Eigenschaften des Objekts, das binär bewertet wird. Die Schlüsselwörter können mit AND, OR oder NOT verknüpft werden. Allerdings ist die Rangfolge bezüglich der Relevanz nicht ohne weiteres möglich.

Das Vektorraummodell ist ein Verfahren, bei dem Dokumente und Anfragen als Punkte in einem Vektorraum repräsentiert werden. Zum Retrieval wird die Distanz zwischen dem Anfragevektor und dem Dokumentvektor genutzt.

Empfehlungsbasiert (collaborative filtering):

Die Grundlage beim collaborative filtering ist die Beziehung zwischen Objekten und Benutzern. Objekte sind genau dann ähnlich, wenn sie auch ähnlich bewertet wurden. Man unterscheidet zwei Arten von Algorithmen, speicherbasierte und modellbasierte. Die speicherbasierte Berechnung der Ähnlichkeit zwischen dem aktiven Benutzer und den in der Datenmatrix gespeicherten erfolgt mittels kosinusbasiertem oder korrelationsbasiertem Ähnlichkeitsmaß.

Bild 2: Das Kosinusmaß liefert Werte zwischen 0 und 1, das korrelationsbasierte Ähnlichkeitsmaß Werte zwischen -1 und 1.

Zur Ermittlung der ähnlichen Benutzer (Mentoren) muß das Ähnlicheitsmaß berechenbar sein, d.h. Benutzer b muß mindestens ein noch nicht von Benutzer a bewertetes Objekt bewertet haben. Das modellbasierte Verfahren basiert auf einem Modell, das auf Basis der Bewertungen der Datenmatrix erlernt wurde. Da das Modell wird in der Offline-Phase erstellt wird, kann die Prognose kann schnell erstellt werden. Beispiele hierfür sind Clustermodelle und Bayessche Netze.

Im Clustermodell werden Benutzer mit ähnlichen Präferenzen in Clustern zusammengefaßt. In der Phase der Clusteranalyse werden die Nutzer eingeteilt mit dem Ziel, daß Nutzer eines Clusters möglichst ähnlich und Nutzer verschiedener Cluster möglichst unähnlich zueinander sind. Während der Laufzeitphase wird der aktive Benutzer probabilistisch den Clustern zugeordnet. Die Objekte, die empfohlen werden, sind diejenigen, die von den anderen Nutzern des Clusters positiv bewertet wurden.

Bild 3: Clustermodell²

Bild 4: Wahrscheinlichkeiten für jede Person/Film-Cluster - Kombination²

Bild 5: Bayessches Netz²

Hybride Systeme

Hybride Systeme bieten eine Kombination aus zwei oder mehreren Verfahren. Dabei wird meistens collaborative filtering mit einem anderen Verfahren kombiniert. Ein Beispiel ist das item-based collaborative filtering von Amazon, das den Kunden Produkte vorschlägt, die von Kunden gekauft wurden, die auch das aktuell betrachtete Produkt gekauft haben.

Die Vorgehensweise: Offline werden Ähnlichkeiten zwischen Items mithilfe der User/Item-Matrix berechnet. Eine Ähnlichkeitstabelle für alle bewerteten Items wird erstellt. Online erfolgt dann die Suche nach ähnlichen Items. Die Offline-Berechnung ist zeitaufwendig, die Online-Berechnung hingegen schnell. Die Offline-Berechnung ist möglich, weil die Beziehungen zwischen den Produkten statisch sind. Das Verfahren liefert Empfehlungen somit in Echtzeit.

Kombinationsmöglichkeiten

Schwächen von Recommender-Systemen

Collaborative filtering:

• Sparsity-Problem (geringe Ausgangs- bzw. Grunddaten in der User-Item-Rating-Matrix)
• Coldstart-Problem (keine oder zu wenig Daten beim Start des Systems)
• New-Item-Problem (keine oder zu wenig Daten bei einem neuen Item)
• New-User-Problem (keine oder zu wenig Daten bei einem neuen User)
• Blackbox-Problem (Schlußfolgerungsmechanismus nicht von außen sichtbar)
• Datenschutz

Content-based filtering:

• Ständiges Pflegen des Datenbestandes notwendig
• Überspezialisierung des Systems möglich

Beispiele

Recommender-Systeme kann man z. B. finden auf folgenden Seiten:

• http://movielens.umn.edu/ Bewerten von Spielfilmen
• http://www.ratingzone.com/ Bewerten von verschiedensten Produkten, z.B. Wein
• http://shadow.ieor.berkeley.edu/humor/ Witze-Empfehlungssystem

Recommender-Systeme und Daffodil

In Daffodil werden DLOs (Digital Library Objects) an User oder Gruppen empfohlen. Die Empfehlungen basieren nicht auf Bewertungen der User, sondern auf der Organisation der DLOs in den Ordnern. Es erfolgt also ein Vergleich zwischen User/Gruppen und ihren gespeicherten DLOs. Bei ausreichender Überlappung, können Objekte empfohlen werden.

Unterschiede zu anderen Recommender-Systemen: Normalerweise geht ein Recommender-Sytem nur von einem Objekttyp aus. Die Datenmenge, auf der die Empfehlungen basieren, besteht aber aus verschiedenen Objekttypen (-> Gewichtungsfaktoren für DLOs). Außerdem existieren verschiedene Arten von Beziehungen zwischen DLOs (-> Ähnlichkeit des Inhaltes, Strukturelle Beziehungen zwischen verschiedenen Objekttypen, Beziehungen zwischen Objekten desselben Typs). Die Daten eines Users formen eine einzige Menge. In Daffodil organisieren die User ihre Daten in verschieden Ordnern, die verschiedene Kontexte beschreiben, selbst. (-> nur Objekte im selben Ordner wird bei der Empfehlung berücksichtigt).

Fazit

Recommender-Systeme haben sich z. B. im E-Commerce auf breiter Front durchgesetzt. Die Zukunft liegt in hybriden Systemen, die die Qualität der Recommender-Systeme verbessern sollen. Probleme, die noch zu lösen sind, umfassen den Datenschutz und das noch fehlende Vertrauen der User in solche Systeme.

Quellen

• [1] A. Lehmann: Recommender Systems, TU Dresden, Hauptseminar Multimediatechnik, 2004

• [2] A. Glogowski: Recommender Systems, Seminararbeit, Universität Duisburg-Essen, 2006

• M. Funk: Recommender Systems in Theorie und Praxis, Seminararbeit, JWvG-Universität Frankfurt a. M.

• N. Fuhr et al: Recommendation in a Collaborative Digital Library Enviroment, Universität Dortmund, 2001

• R. Burke: Integrating Knowledge-based and Collaborative-filtering Recommender Systems, University of California, 1999

• Wikipedia: Artikel „Collaborative filtering“, Stand 17.4.2006

• L. Diestelhorst: Recommendation Engines, TU Hamburg-Harburg, 2001

• R. Burke: Hybrid Recommender Systems: Survey and Experiments, California State University, 2002

• F. Xu: Einführung in Recommender-Systeme, Universität des Saarlandes

• B. M. Sawar et al: Recommender Systems for Large-scale E-Commerce: Scalable Neighborhood Formation Using Clustering, University of Minnesota, 2003