Abstract

In der vorliegenden Bachelor Thesis werden die Geschichte, die verwendeten Technologien und die Einsatzgebiete von Empfehlungssystemen dargestellt. Basierend auf diesen Erkenntnissen wird die mögliche Implementierung eines solchen Systems für zwei Beispielanwendungen überprüft. Hierbei handelt es sich um den Büchermarktplatz im InfWeb der Fakultät Informatik der Hochschule Reutlingen und das PaSIS System des Universitätsklinikums Tübingen. Im Hinblick auf Faktoren wie Datenbasis oder Nutzeraufkommen wird eine Entscheidung für einen der beiden Anwendungsfälle getroffen und im Anschluss ein Konzept zur Implementierung entwickelt.

This bachelor thesis concerns with the history, the used technologies and the field of application for recommender systems. Based on this knowledge the possible implementation of such a system is evaluated for two concrete examples. These are the Büchermarktplatz included in the InfWeb of the faculty for computer science at Reutlingen University and the PaSIS system at the University Hospital Tübingen. With regard to factors such as database or amount of users a decision for one of the two applications is made. Afterwords a concept for the implementation will be developed.

Inhaltsverzeichnis 3

Inhaltsverzeichnis   

1.  Einleitung  5

1.1.  Einführung  5

1.2.  Motivation  7

1.3.  Ziele der Arbeit  8

2.  Empfehlungssysteme  9

2.1.  Überblick  9

2.1.1.  Gesamteinordnung  9

2.1.2.  Entwicklungsgeschichte  11

2.1.3.  Anwendungsgebiete  15

2.2.  Methoden von Empfehlungssystemen  16

2.2.1.  Regelbasierte Filterung  16

2.2.2.  Inhaltsbasierte Filterung  17

2.2.3.  Kollaborative Filterung  18

2.2.4.  Hybride Verfahren  21

2.2.5.  Unterscheidung Memory-Based Model-Based  21

2.2.6.  Messbarkeit von Eigenschaften  23

2.3.  Fallbeispiele  27

2.3.1.  Amazon  27

2.3.2.  Last.fm  29

2.3.3.  MovieLens  30

3.  Mögliche Anwendungsfälle  32

3.1.  Büchermarktplatz  32

3.2.  PaSIS/PaSOS  34

3.3.  Anwendungsfallanalyse  35

3.4.  Entscheidung  38

4.  Konzeption eines Empfehlungssystems für PaSIS/PaSOS  39

4.1.  Zielsetzung des Systems  39

4.2.  Anforderungen an das System  39

Inhaltsverzeichnis 4

4.2.1.  Funktionale Anforderungen  39

4.2.2.  Nichtfunktionale Anforderungen  40

4.3.  Auswahl des Verfahrens  40

4.3.1.  Gegenüberstellung der Verfahren  40

4.3.2.  Schlussfolgerung  41

4.4.  Nähere Eingrenzung  42

4.4.1.  Grobkonzept des Systems  42

4.4.2.  Bestimmung der Fallähnlichkeit  42

4.4.3.  Bewertung durch Benutzer  45

4.4.4.  Sortierung Fallähnlichkeit  46

4.4.5.  Zusammenfassung  46

4.5.  Automatisierte Verschlagwortung  48

4.5.1.  TF-IDF  48

5.  Fazit  50

Abbildungsverzeichnis   51

Tabellenverzeichnis 52   

Listings   53

Literaturverzeichnis   55

A.  Quellcode  59

A.1.  TF-IDF Implementierung  59

A  2 Testskript  61

1. Einleitung

1.1. Einführung

Empfehlungssysteme begegnen einem bei der täglichen Nutzung des Internets heutzutage geradezu selbstverständlich. Im täglichen Leben stellen persönliche Empfehlungen durch andere Personen das hauptsächliche Hilfsmittel zum Finden und Auswählen passender Dinge dar. Recommender Systeme bilden diese menschlichen Empfehlungen in technischen Systemen ab [Färber et al., 2003, S.5]. Obwohl auf den ersten Blick nicht immer ersichtlich, ist diese Technik in vielen Bereichen präsent. Dazu zählen unter anderem jegliche Form von Inhalten (Text, Bild, Ton oder Produkte), Prozesse (geobasierte oder interaktive) sowie Personen (Experten, Interessengruppen). Die Einsatzgebiete dieser Systeme werden in Kapitel 2.1.3 detailliert aufgelistet.

Sie werden vor allem eingesetzt, um den mit dem World Wide Web verbundenen Information Overload ¹ Herr zu werden. Der Benutzer sieht sich einer nicht zu bewältigenden Menge an Informationen gegenüber. Genau dieses Problem soll ein gut arbeitendes Empfehlungssystem ganz oder teilweise lösen. Dies lässt sich auch in eine Definition fassen: Ein Empfehlungssystem ist ein System, das einem Benutzer in einem gegebenen Kontext aus einer gegebenen Entitätsmenge aktiv eine Teilmenge nützlicher Elemente empfiehlt [Klahold, 2009, S.1]. Weniger abstrakt ausgedrückt, ist der Sinn eines solchen Systems, Informationen zu filtern, aufzubereiten und sinnvolle Empfehlungen für den Benutzer zu geben [Mürzl, Riemenschneider, 2008, S.2]. In der Regel interagiert der Benutzer wissentlich mit dem System mit der Motivation, eine Empfehlung zu erhalten [Runte, 2000, S.9]. Die Funktionsweise eines Empfehlungssystems ist in Abbildung 1.1 illustriert.

Der Einsatz eines solchen Systems ist vor allem dann von großem Nutzen, wenn die Nutzeranzahl und die zur Verfügung stehende Informationsmenge sehr hoch sind, wie bei Informations- und Nachrichtenportalen oder E-Commerce Anwendungen. Als

¹ Information Overload bezeichnet per Definition den Zustand, mit einer Datenmenge konfrontiert

zu sein, die nicht mehr sinnvoll zu verarbeiten ist. Eine Entscheidungsfindung wird dadurch schwierig bis unmöglich.

1.1. Einführung 6

Abbildung 1.1.: Funktion eines Empfehlungssystems [Klahold, 2009, S.2]

Benutzer kommt man daher am häufigsten mit der Empfehlung von Inhalten in Kontakt. Produktempfehlungen stellen hier wiederum den am stärksten vertretenen Einsatzbereich dar [Klahold, 2009, S.5]. Die Entwicklung der Systeme ist vor allem in diesem Bereich weit fortgeschritten. Dies bedingt sich durch die simple marktwirtschaftliche Tatsache, dass gute Produktempfehlungen den Kunden eher zum Kauf anregen und dementsprechend bares Geld zu verdienen ist. Prominentester Vertreter auf diesem Gebiet ist sicherlich die Firma Amazon.com Incorporated. Ein prägnantes Zitat ihres CEO ² lautet:

„If I have one million customers on the web, I should have one million stores on the web.“

Jeff Bezos, CEO Amazon.com Inc.

² Chief executive officer. Bezeichnet im angelsächsischen Raum den Leiter eines Unternehmens, der

für Firmenpolitik und Geschäftsführung zuständig ist. www.businessdictionary.com

1.2. Motivation 7

Dies verdeutlicht sehr gut die im Onlineauftritt von Amazon umgesetzte Strategie, auf die im Abschnitt Fallbeispiele näher eingegangen wird.

1.2. Motivation

Die zahlreichen wissenschaftlichen Veröffentlichungen zu diesem Thema verdeutlichen die Relevanz des Themas in der Informatik. Trotz allem sind Personalisierungssysteme ein relativ junges Forschungsgebiet. Da die möglichen Einsatzzwecke praktisch unbegrenzt sind, ist ein Ende der Entwicklung noch nicht abzusehen. Der Autor dieser Arbeit kam mit dem Thema zum ersten Mal während seiner Tätigkeit als Praktikant und Werksstudent der Firma dmc ³ in Kontakt. Dort allerdings mit dem Fokus auf den Einsatz in E-Commerce ⁴ Anwendungen. Es wurde versucht, sinnvolle Anwendungsfälle für ein solches System im Umfeld der Hochschule Reutlingen zu finden. In Anlehnung an die Buchempfehlungen bei Amazon war zunächst der Katalog der Hochschulbibliothek als Zielanwendung angedacht. Diese Idee wurde jedoch aufgrund des problematischen (bzw. nicht möglichen) Zugriffs und Einblicks in den Datenbestand verworfen. Im späteren Verlauf der Recherche stellte sich zudem heraus, dass diese Funktionalität bereits durch das von der Universität Karlsruhe entwickelte BibTip ⁵ System umgesetzt wird. Die Suche nach einer ähnlichen Anwendung führte dann zum Büchermarktplatz im InfWeb der Fakultät Informatik. Durch eine Anregung von Prof. Dr. Schmollinger rückte dann das PaSIS ⁶ System am Universitätsklinikum Tübingen in den Blickpunkt. Das System an sich stellt schon eine Innovation dar. Seine mögliche Verknüpfung mit einem Empfehlungsmechanismus ist bisher einmalig.

³ digital media center www.dmc.de

⁴ Electronic Commerce bezeichnet in diesem Zusammenhang das Kaufen und Verkaufen von Gütern

und Dienstleistungen über das Internet.

⁵ http://www.bibtip.org Nähere Informationen siehe Kapitel 3.1

⁶ Patienten Sicherheits Informations System. Nähere Informationen siehe Kapitel 3.2

1.3. Ziele der Arbeit 8

1.3. Ziele der Arbeit

Ziel der Arbeit ist es zunächst einen grundlegenden Überblick über die verschiedenen Technologien, ihre Ursprünge und Einsatzgebiete schaffen. Aufgrund dieser Erkenntnisse soll dann die Möglichkeit eines Einsatzes innerhalb von zwei Beispielanwendungen geprüft werden. Hierbei handelt es sich um den Büchermarktplatz im InfWeb der Fakultät Informatik der Hochschule Reutlingen und das PaSIS/PaSOS System am Universitätsklinikum Tübingen. Für eine der zwei Anwendungen wird im Anschluss ein Konzept zur Implementierung eines Empfehlungssystems erstellt. Der Titel der Thesis wurde erst nach der Entscheidung gewählt. Dies war nötig, da er sonst nicht klar und prägnant genug hätte formuliert werden können.

• Vor- und Gegenüberstellung der existierenden Technologien

• Prüfung der Möglichkeit eines Einsatzes für die zwei Beispielanwendungen

• Entscheidung für welchen Anwendungsfall die Konzeption erfolgt

• Konzeption für die Einführung des Systems

2. Empfehlungssysteme

2.1. Überblick

2.1.1. Gesamteinordnung

Empfehlungssysteme lassen sich zunächst in zwei Obergruppen einteilen. (siehe Abbildung 2.1) Man unterscheidet grundsätzlich zwischen individualisierten und nicht individualisierten Systemen.

Abbildung 2.1.: Empfehlungssystemkategorien (Eigendarstellung)

Erfolgt keine Individualisierung, erhält jeder Benutzer dieselben Ergebnisse. Beispielhaft sei hier ein System genannt, das die Kinofilm-Präferenzen einer breiten Masse von Benutzern speichert und Präferenz-Mittelwerte für jeden Kinofilm be- rechnet. Im Anschluss werden die Filme nach ihrer Präferenz absteigend geordnet

2.1. Überblick

und die 100 Filme mit der höchsten mittleren Präferenz ausgegeben. Eine über ein solches System erstellte Empfehlung ist für jeden Benutzer identisch [Runte, 2000, S.9].

Im Gegensatz dazu stehen die individualisierten Systeme. Wie der Name schon sagt, erfolgt hier eine Personalisierung auf den Benutzer. Hierzu können verschiedene Verfahren eingesetzt werden. Man unterscheidet grundsätzlich zwischen inhaltsbasierten und kollaborativen Verfahren. Diese unterscheiden sich in der Methodik zur Empfehlungsgenerierung.

Bei inhaltsbasierten Systemen werden die Eigenschaften der zu empfehlenden Objekte ausgewertet. Entsprechend der Präferenzen und Bewertungen eines Nutzers für diese Eigenschaften werden Empfehlungen ausgesprochen. Dem Benutzer werden dementsprechend Objekte empfohlen, die seinen bisher präferierten ähnlich sind. Beim kollaborativen Filtern werden die Präferenzen anderer Benutzer des Systems ausgewertet. Das Augenmerk liegt hier darauf, Benutzerprofile zu finden, die dem Profil des aktiven Benutzers ähneln. Aufgrund dieser Auswertung werden dann Empfehlungen für andere Benutzer generiert.

Zusätzlich existieren zahlreiche Mischformen aus beiden Varianten, die sogenannten hybriden Systeme.

Nähere Informationen zu den einzelnen Varianten finden sich in Kapitel 3.

2.1. Überblick

2.1.2. Entwicklungsgeschichte

Die Problematik des Informationsüberflusses ist nicht erst seit Zeiten des Internets existent. Die Aufgabe, kontextuell nützliche Informationen zu finden, stellt sich schon sehr lange. Sie tritt Im Grunde bereits auf, seit Informationen sich archivieren lassen. In der wissenschaftlichen Literatur wird darauf schon seit Beginn des 20. Jahrhunderts eingegangen. Beispielhaft sei hier ein Zitat von Claus Oppenheimer aus seinem Aufsatz „Die papierne Sintflut“ genannt:

„Wenn man gar nicht mehr übersehen kann, was geschaffen wird, so wird ([...]) Literatur zu einem Zahlenfriedhof.“

Claus Oppenheimer 1

Darin thematisiert er das Problem eines Forschers, der sein Spezialgebiet beherrschen will. Um dies zu erreichen, muss er jedoch eine stetig wachsende Menge an Wissen aufnehmen. Wenn er allerdings versucht, alle auf seinem Fachgebiet erscheinenden Veröffentlichungen zu lesen, bleibt ihm kaum noch Zeit für die eigentliche Forschung. Gleichzeitig besteht jedoch die Gefahr, bereits behandelte Themen zu bearbeiten, wenn er sich nicht oder nur unzureichend informiert [Marx, Gramm, 2005, S.16]. Ein weiteres prägnantes Zitat aus dem Jahr 1982 lautet:

„Wir ertrinken in Informationen, aber hungern nach Wissen“

John Naisbitt 2

In einer akademischen Arbeit wird das Fachgebiet Empfehlungssysteme zum ersten Mal im Jahr 1958 behandelt. „A Business Intelligence System“ beschreibt ein Verfahren zur automatisierten Analyse von Dokumenten. Diese werden dann als Empfehlung weitergeleitet. Hier ist allerdings noch nicht von Empfehlungen, sondern von „Selektiver Verbreitung neuer Information“ die Rede [Luhn, 1958, S.314-319]. Zeitlich gesehen wurden zunächst eigenschaftsbasierte Filterverfahren entwickelt. Darauf folgten die kollaborativen Verfahren und im Anschluss daran die hybriden Varianten. Die ersten Vertreter jeder Gattung werden auf den kommenden Seiten behandelt.

¹ [Oppenheimer, 1927, S.229]

² Amerikanischer Trendforscher, Zitat aus seinem Buch Megatrends: Ten New Directions

Transforming Our Lives, Grand Central Publishing, 1988

2.1. Überblick

Als erster Vertreter der eigenschaftsbasierten Filterung kann das System „The In-formation Lens“ gesehen werden, das im Jahr 1986 vorgestellt wurde. Es erweitert die klassische E-Mail um eine Art Tagging ³ Funktion. Jeder Mail werden vom Sender Metadaten hinzugefügt. Durch die Adressierung an ein spezielles Mail-Konto („lens“) wird sie im Anschluss an alle möglicherweise interessierten Empfänger weitergeleitet. Dafür wurden im Vorfeld vom Empfänger Regeln festgelegt, die an ihn weiterzuleitende Mails definieren [Malone et al., 1986, S.2] (siehe auch Abbildung 2.2).

Abbildung 2.2.: Architektur des Information Lens Systems [Klahold, 2009, S.102]

³ Hinzufügen von Schlagworten

2.1. Überblick

Das im Jahr 1992 vorgestellte Tapestry System wird in der Literatur als erste Implementierung einer kollaborativen Filterung beschrieben. Es wurde im Xerox Palo Alto Research Center entwickelt. Genau wie Information Lens dient es zur Empfehlung von E-Mails. Grundidee ist die Einbeziehung der Benutzer in den Filterprozess. Diese können dann einzelne Mails z. B. als relevant oder nicht relevant kennzeichnen. Im Anschluss können von jedem Benutzer Filter definiert werden, die die Präferenzen der anderen Nutzer berücksichtigen. Dies geschieht durch Regeln der Form „Zeige Mails, die von Benutzer X als relevant gekennzeichnet wurden “oder „Zeige keine Mails, die von Benutzer Y und Z als nicht relevant gekennzeichnet wurden“. Beispielsweise möchte man nur interessante Beiträge einer bestimmten Newsgroup erhalten, hat jedoch keine Zeit alle zu lesen, um die Wichtigen herauszufiltern. Es ist einem jedoch bekannt, dass Benutzer X, Y und Z sämtliches Material der Newsgroup lesen und auf interessante Beiträge antworten. Tapestry erlaubt nun die Filterung nach „Beiträge, die von X, Y und Z beantwortet wurden “. Dies setzt allerdings voraus, dass sich die Benutzer des Systems kennen, um sich ihre persönlichen Filter erstellen zu können [Goldberg et al., 1992, S.61 ff.].

Abbildung 2.3.: Architektur des Tapestry Systems [Klahold, 2009, S.89]