Leseprobe
Inhaltsverzeichnis
1. Einleitung
1.1. Einfuhrung
1.2. Motivation
1.3. Ziele der Arbeit
2. Empfehlungssysteme
2.1. Uberblick
2.1.1. Gesamteinordnung
2.1.2. Entwicklungsgeschichte
2.1.3. Anwendungsgebiete
2.2. Methoden von Empfehlungssystemen
2.2.1. Regelbasierte Filterung
2.2.2. Inhaltsbasierte Filterung
2.2.3. Kollaborative Filterung
2.2.4. Hybride Verfahren
2.2.5. Unterscheidung Memory-Based & Model-Based
2.2.6. Messbarkeit von Eigenschaften
2.3. Fallbeispiele
2.3.1. Amazon
2.3.2. Last.fm
2.3.3. MovieLens
3. Mogliche Anwendungsfalle
3.1. Buchermarktplatz
3.2. PaSIS/PaSOS
3.3. Anwendungsfallanalyse
3.4. Entscheidung
4. Konzeption eines Empfehlungssystems fur PaSIS/PaSOS
4.1. Zielsetzung des Systems
4.2. Anforderungen an das System
4.2.1. Funktionale Anforderungen
4.2.2. Nichtfunktionale Anforderungen
4.3. Auswahl des Verfahrens
4.3.1. Gegenuberstellung der Verfahren
4.3.2. Schlussfolgerung
4.4. Nahere Eingrenzung
4.4.1. Grobkonzept des Systems
4.4.2. Bestimmung der Fallahnlichkeit
4.4.3. Bewertung durch Benutzer
4.4.4. Sortierung Fallahnlichkeit
4.4.5. Zusammenfassung
4.5. Automatisierte Verschlagwortung
4.5.1. TF-IDF
5. Fazit
Abbildungsverzeichnis
Tabellenverzeichnis
Listings
Literaturverzeichnis
A. Quellcode
A.1. TF-IDF Implementierung
A.2. Testskript
1. Einleitung
1.1. Einfuhrung
Empfehlungssysteme begegnen einem bei der taglichen Nutzung des Internets heut- zutage geradezu selbstverstandlich. Im taglichen Leben stellen personliche Emp- fehlungen durch andere Personen das hauptsachliche Hilfsmittel zum Finden und Auswahlen passender Dinge dar. Recommender Systeme bilden diese menschlichen Empfehlungen in technischen Systemen ab [Farber et al., 2003, S.5]. Obwohl auf den ersten Blick nicht immer ersichtlich, ist diese Technik in vielen Bereichen prasent. Dazu zahlen unter anderem jegliche Form von Inhalten (Text, Bild, Ton oder Pro- dukte), Prozesse (geobasierte oder interaktive) sowie Personen (Experten, Interes- sengruppen). 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[1] Herr zu werden. Der Benutzer sieht sich einer nicht zu be- waltigenden Menge an Informationen gegenuber. Genau dieses Problem soll ein gut arbeitendes Empfehlungssystem ganz oder teilweise losen. Dies lasst sich auch in ei- ne Definition fassen: Ein Empfehlungssystem ist ein System, das einem Benutzer in einem gegebenen Kontext aus einer gegebenen Entitatsmenge aktiv eine Teilmenge nutzlicher Elemente empfiehlt [Klahold, 2009, S.1]. Weniger abstrakt ausgedruckt, ist der Sinn eines solchen Systems, Informationen zu filtern, aufzubereiten und sinnvolle Empfehlungen fur den Benutzer zu geben [Murzl, 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 Empfeh- lungssystems ist in Abbildung 1.1 illustriert.
Der Einsatz eines solchen Systems ist vor allem dann von grofiem Nutzen, wenn die Nutzeranzahl und die zur Verfugung stehende Informationsmenge sehr hoch sind, wie bei Informations- und Nachrichtenportalen oder E-Commerce Anwendungen. Als
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1.1.: Funktion eines Empfehlungssystems [Klahold, 2009, S.2]
Benutzer kommt man daher am haufigsten mit der Empfehlung von Inhalten in Kon- takt. Produktempfehlungen stellen hier wiederum den am starksten vertretenen Ein- satzbereich dar [Klahold, 2009, S.5]. Die Entwicklung der Systeme ist vor allem in diesem Bereich weit fortgeschritten. Dies bedingt sich durch die simple marktwirt- schaftliche 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 pragnantes Zitat ihres CEO[2] 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.
Dies verdeutlicht sehr gut die im Onlineauftritt von Amazon umgesetzte Strategie, auf die im Abschnitt Fallbeispiele naher eingegangen wird.
1.2. Motivation
Die zahlreichen wissenschaftlichen Veroffentlichungen zu diesem Thema verdeutli- chen die Relevanz des Themas in der Informatik. Trotz allem sind Personalisie- rungssysteme ein relativ junges Forschungsgebiet. Da die moglichen Einsatzzwecke praktisch unbegrenzt sind, ist ein Ende der Entwicklung noch nicht abzusehen. Der Autor dieser Arbeit kam mit dem Thema zum ersten Mal wahrend seiner Tatigkeit als Praktikant und Werksstudent der Firma dmc[3] in Kontakt. Dort allerdings mit dem Fokus auf den Einsatz in E-Commerce[4] Anwendungen. Es wurde versucht, sinn- volle Anwendungsfalle fur ein solches System im Umfeld der Hochschule Reutlingen zu finden. In Anlehnung an die Buchempfehlungen bei Amazon war zunachst der Katalog der Hochschulbibliothek als Zielanwendung angedacht. Diese Idee wurde je- doch aufgrund des problematischen (bzw. nicht moglichen) Zugriffs und Einblicks in den Datenbestand verworfen. Im spateren Verlauf der Recherche stellte sich zudem heraus, dass diese Funktionalitat bereits durch das von der Universitat Karlsruhe entwickelte BibTip[5] System umgesetzt wird. Die Suche nach einer ahnlichen Anwen- dung fuhrte dann zum Buchermarktplatz im InfWeb der Fakultat Informatik.
Durch eine Anregung von Prof. Dr. Schmollinger ruckte dann das PaSIS[6] System am Universitatsklinikum Tubingen in den Blickpunkt. Das System an sich stellt schon eine Innovation dar. Seine mogliche Verknupfung mit einem Empfehlungsme- chanismus ist bisher einmalig.
1.3. Ziele der Arbeit
Ziel der Arbeit ist es zunachst einen grundlegenden Uberblick uber die verschiedenen Technologien, ihre Ursprunge und Einsatzgebiete schaffen. Aufgrund dieser Erkennt- nisse soll dann die Moglichkeit eines Einsatzes innerhalb von zwei Beispielanwendun- gen gepruft werden. Hierbei handelt es sich um den Buchermarktplatz im InfWeb der Fakultat Informatik der Hochschule Reutlingen und das PaSIS/PaSOS System am Universitatsklinikum Tubingen. Fur eine der zwei Anwendungen wird im Anschluss ein Konzept zur Implementierung eines Empfehlungssystems erstellt. Der Titel der Thesis wurde erst nach der Entscheidung gewahlt. Dies war notig, da er sonst nicht klar und pragnant genug hatte formuliert werden konnen.
- Vor- und Gegenuberstellung der existierenden Technologien
- Prufung der Moglichkeit eines Einsatzes fur die zwei Beispielanwendungen
- Entscheidung fur welchen Anwendungsfall die Konzeption erfolgt
- Konzeption fur die Einfuhrung des Systems
2. Empfehlungssysteme
2.1. Uberblick
2.1.1. Gesamteinordnung
Empfehlungssysteme lassen sich zunachst in zwei Obergruppen einteilen. (siehe Ab- bildung 2.1) Man unterscheidet grundsatzlich zwischen individualisierten und nicht individualisierten Systemen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.1.: Empfehlungssystemkategorien (Eigendarstellung)
Erfolgt keine Individualisierung, erhalt jeder Benutzer dieselben Ergebnisse. Bei- spielhaft sei hier ein System genannt, das die Kinofilm-Praferenzen einer breiten Masse von Benutzern speichert und Praferenz-Mittelwerte fur jeden Kinofilm be- rechnet. Im Anschluss werden die Filme nach ihrer Praferenz absteigend geordnet und die 100 Filme mit der hochsten mittleren Praferenz ausgegeben. Eine uber ein solches System erstellte Empfehlung ist fur 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 konnen verschiede- ne Verfahren eingesetzt werden. Man unterscheidet grundsatzlich zwischen inhalts- basierten und kollaborativen Verfahren. Diese unterscheiden sich in der Methodik zur Empfehlungsgenerierung.
Bei inhaltsbasierten Systemen werden die Eigenschaften der zu empfehlenden Ob- jekte ausgewertet. Entsprechend der Praferenzen und Bewertungen eines Nutzers fur diese Eigenschaften werden Empfehlungen ausgesprochen. Dem Benutzer werden dementsprechend Objekte empfohlen, die seinen bisher praferierten ahnlich sind.
Beim kollaborativen Filtern werden die Praferenzen anderer Benutzer des Systems ausgewertet. Das Augenmerk liegt hie]r darauf, Benutzerprofile zu finden, die dem Profil des aktiven Benutzers ahneln. Aufgrund dieser Auswertung werden dann Empfehlungen fur andere Benutzer generiert.
Zusatzlich existieren zahlreiche Mischformen aus beiden Varianten, die sogenann- ten hybriden Systeme.
Nahere Informationen zu den einzelnen Varianten finden sich in Kapitel 3.
2.1.2. Entwicklungsgeschichte
Die Problematik des Informationsuberflusses ist nicht erst seit Zeiten des Internets existent. Die Aufgabe, kontextuell nutzliche 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. Jahrhun- derts eingegangen. Beispielhaft sei hier ein Zitat von Claus Oppenheimer aus seinem Aufsatz „Die papierne Sintflut“ genannt:
„Wenn man gar nicht mehr ubersehen kann, was geschaffen wird, so wird ([...]) Literatur zu einem Zahlenfriedhof.“
Claus Oppenheimer[1]
Darin thematisiert er das Problem eines Forschers, der sein Spezialgebiet beherr- schen will. Um dies zu erreichen, muss er jedoch eine stetig wachsende Menge an Wissen aufnehmen. Wenn er allerdings versucht, alle auf seinem Fachgebiet erschei- nenden Veroffentlichungen zu lesen, bleibt ihm kaum noch Zeit fur die eigentliche Forschung. Gleichzeitig besteht jedoch die Gefahr, bereits behandelte Themen zu be- arbeiten, wenn er sich nicht oder nur unzureichend informiert [Marx, Gramm, 2005, S.16]. Ein weiteres pragnantes 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 Ver- fahren zur automatisierten Analyse von Dokumenten. Diese werden dann als Emp- fehlung weitergeleitet. Hier ist allerdings noch nicht von Empfehlungen, sondern von „Selektiver Verbreitung neuer Information" die Rede [Luhn, 1958, S.314-319].
Zeitlich gesehen wurden zunachst 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.
Als erster Vertreter der eigenschaftsbasierten Filterung kann das System „The Information Lens“ gesehen werden, das im Jahr 1986 vorgestellt wurde. Es erweitert die klassische E-Mail um eine Art Tagging[3] Funktion. Jeder Mail werden vom Sender Metadaten hinzugefugt. Durch die Adressierung an ein spezielles Mail-Konto („lens“) wird sie im Anschluss an alle moglicherweise interessierten Empfanger weitergeleitet. Dafur wurden im Vorfeld vom Empfanger Regeln festgelegt, die an ihn weiterzulei- tende Mails definieren [Malone et al., 1986, S.2] (siehe auch Abbildung 2.2).
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.2.: Architektur des Information Lens Systems [Klahold, 2009, S.102]
Das im Jahr 1992 vorgestellte Tapestry System wird in der Literatur als erste Im- plementierung einer kollaborativen Filterung beschrieben. Es wurde im Xerox Palo Alto Research Center entwickelt. Genau wie Information Lens dient es zur Empfeh- lung von E-Mails. Grundidee ist die Einbeziehung der Benutzer in den Filterprozess. Diese konnen dann einzelne Mails z. B. als relevant oder nicht relevant kennzeich- nen. Im Anschluss konnen von jedem Benutzer Filter definiert werden, die die Pra- ferenzen der anderen Nutzer berucksichtigen. 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 mochte man nur interessante Beitrage 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 samtliches Material der Newsgroup lesen und auf interessante Beitrage antworten. Tapestry erlaubt nun die Filterung nach „Beitrage, die von X, Y und Z beantwortet wurden “. Dies setzt allerdings vor- aus, dass sich die Benutzer des Systems kennen, um sich ihre personlichen Filter erstellen zu konnen [Goldberg et al., 1992, S.61 ff.].
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.3.: Architektur des Tapestry Systems [Klahold, 2009, S.89]
Die Entwicklung des hybriden Fab Systems fuhrte im Dezember 1994 zur ersten lauffahigen Version, die im Anschluss noch weiterentwickelt wurde. Es kombiniert inhaltsbasierte und kollaborative Filtertechniken, um die Vorteile beider Verfahren zu nutzen und die Schwachen zu umgehen. Empfehlungsgegenstand des Systems sind Internetseiten.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.4.: Architektur des Fab Systems [Balabanovic, Shoham, 1997b, S.68]
Das System verfugt uber drei Hauptkomponenten: collection agents (suchen nach Seiten eines bestimmten Themengebietes), selection agents (suchen nach Seiten fur einen bestimmten Benutzer) und einem zentralen Router. Jeder Agent verfugt uber ein Profil, welches auf Wortern basiert, die in den bewerteten Internetseiten enthalten sind. Das Profil eines collection agents steht also fur ein Themengebiet, wahrend das eines selection agents die Interessen eines bestimmten Benutzers reprasentiert. Die durch collection agents gefundenen Seiten werden an den zentralen Router gesendet, der sie an alle Benutzer weiterleitet, deren Profil mit dem des collection agents zu einem bestimmten Wert ubereinstimmt. Der selection agent jedes Nutzers ubernimmt zusatzliche Filterfunktionen. Seiten, die der Benutzer bereits gesehen hat, werden verworfen und nicht erneut empfohlen. Die erhaltenen Empfehlungen werden durch die Benutzer bewertet. Diese Bewertungen werden benutzt, um das Profil des person- lichen selection agents zu aktualisieren. Gleichzeitig erhalt der collection agent, der die Empfehlung ausgesprochen hat, diese Ruckmeldung und passt sein Profil ebenfalls an. Zusatzlich werden hoch bewertete Seiten direkt an die sogenannten nearest neighbours (Benutzer mit ahnlichen Profilen) weitergeleitet. Dort werden sie genau wie die vom zentralen Router stammenden Empfehlungen verarbeitet. Um eine moglichst hohe Empfehlungsgute zu gewahrleisten, werden unpopulare (deren Empfehlungen nur von wenigen Nutzern gesehen werden) und erfolglose (deren Empfehlungen nur niedrige Bewertungen erhalten) Agenten wochentlich aussortiert. Die besten Agenten werden dupliziert, um deren Platz einzunehmen [Balabanovic, Shoham, 1997b, S.66 ff.].
2.1.3. Anwendungsgebiete
Die grundsatzlichen Einsatzmoglichkeiten fur ein Empfehlungssystem sind praktisch unbegrenzt. Eine grobe Einteilung kann anhand der Art der ausgesprochenen Emp- fehlungen vorgenommen werden. Diese sind in Abbildung 2.5 noch einmal dargestellt.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2.5.: Bandbreite von Empfehlungssystemen [Klahold, 2009, S.4]
[...]
[1] 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 unmoglich.
[2] Chief executive officer. Bezeichnet im angelsachsischen Raum den Leiter eines Unternehmens, der fur Firmenpolitik und Geschaftsfuhrung zustandig ist. www.businessdictionary.com
[3] digital media center www.dmc.de
[4] Electronic Commerce bezeichnet in diesem Zusammenhang das Kaufen und Verkaufen von Gutern und Dienstleistungen uber das Internet.
[5] http://www.bibtip.org Nahere Informationen siehe Kapitel 3.1
[6] Patienten Sicherheits Informations System. Nahere Informationen siehe Kapitel 3.2
[1] [Oppenheimer, 1927, S.229]
[2] Amerikanischer Trendforscher, Zitat aus seinem Buch Megatrends: Ten New Directions Transforming Our Lives, Grand Central Publishing, 1988
[3] Hinzufugen von Schlagworten