Empfehlungssysteme: Recommender Systems - Grundlagen, Konzepte und Lösungen - Klahold A.

Author: Klahold A.

Tags: software computertechnik programmierung informatik

ISBN: 978-3-8348-0568-3

Year: 2009

Similar

Linux: Konzepte, Kommandos, Oberflächen

Grundlagen und Konzepte der Informatik: Eine Einführung in die Informatik ausgehend von den fundamentalen Grundlagen

Bremsenhandbuch: Grundlagen, Komponenten, Systeme, Fahrdynamik

Handbuch Verbrennungsmotor: Grundlagen, Komponenten, Systeme, Perspektiven

Text

André Klahold
Empfehlungssysteme

sUppLex

Aus dem Programm

T Management
ITund -Anwendungen

Web 2.0 – Eine empirische Bestandsaufnahme
herausgegeben von Paul Alpar und Steffen Blaschke
Benutzerfreundliche Online-Hilfen
von Petra Thiemann
Methoden wissensbasierter Systeme
von Christoph Beierle und Gabriele Kern-Isberner
Marketingkampagnen effizient managen
von Thomas Dold, Bernd Hoffmann und Jörg Neumann
Controlling mit SAP®
von Gunther Friedl, Christian Hilz und Burkhard Pedell
Marketing-Kommunikation im Internet
herausgegeben von Dirk Frosch-Wilke und Christian Raith
Grundkurs ITT Proj
o ektcontrolling
von Andreas Gadatsch
Daten- und Informationsqualität
herausgegeben von Knut Hildebrand, Marcus Gebauer,
r Holger Hinrichs
und Michael Mielke
Business Intelligence – Grundlagen und praktische Anwendungen
von Hans-Georg Kemper,
r Walid Mehanna und Carsten Unger
Business Intelligence – Arbeits- und Übungsbuch
von Hans-Georg Kemper und Henning Baars
Website Marketing
von Sven Roddewig
Handbuch E-Procurement
von Patrick P. Stoll

www.viewegteubner.de

sUppLex

André Klahold

Empfehlungssysteme
Recommender Systems –
Grundlagen, Konzepte und Lösungen
Mit 82 Abbildungen
STUDIUM

sUppLex

Bibliografische Information der Deutschen Nationalbibliothek
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der
Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über
<http://dnb.d-nb.de> abrufbar.

Das in diesem Werk enthaltene Programm-Material ist mit keiner Verpflichtung oder Garantie irgendeiner Art verbunden. Der Autor übernimmt infolgedessen keine Verantwortung und wird keine daraus
folgende oder sonstige Haftung übernehmen, die auf irgendeine Art aus der Benutzung dieses
Programm-Materials oder Teilen davon entsteht.
Höchste inhaltliche und technische Qualität unserer Produkte ist unser Ziel. Bei der Produktion und
Auslieferung unserer Bücher wollen wir die Umwelt schonen: Dieses Buch ist auf säurefreiem und
chlorfrei gebleichtem Papier gedruckt. Die Einschweißfolie besteht aus Polyäthylen und damit aus
organischen Grundstoffen, die weder bei der Herstellung noch bei der Verbrennung Schadstoffe
freisetzen.

1. Auflage 2009
Alle Rechte vorbehalten
© Vieweg+Teubner | GWV Fachverlage GmbH, Wiesbaden 2009
Lektorat: Sybille Thelen | Andrea Broßler
Vieweg+Teubner ist Teil der Fachverlagsgruppe Springer Science+Business Media.
www.viewegteubner.de
Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede
Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne
Zustimmung des Verlags unzulässig und strafbar. Das gilt insbesondere für
Vervielfältigungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung
und Verarbeitung in elektronischen Systemen.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk
berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im
Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher
von jedermann benutzt werden dürften.
Umschlaggestaltung: KünkelLopka Medienentwicklung, Heidelberg
Druck und buchbinderische Verarbeitung: Krips b.v., Meppel
Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier.
Printed in the Netherlands
ISBN 978-3-8348-0568-3

sUppLex

Für Danie

sUppLex

Vorwort
I not only use all the brains that I have, but all that I can borrow.
(Thomas Woodrow Wilson (1856-1924), 28. Präsident der USA)
In einer immer komplexer werdenden Welt mit überbordenden Informationsquellen sind Entscheidungshilfen von unschätzbarem
Wert.
Die Prominenz des Themas wird seit vielen Jahren durch die zahlreichen akademischen Veröffentlichungen unterstrichen.
Das vorliegende Buch ist im Rahmen der Vorlesungsreihe zu Empfehlungssystemen am Institut für Knowledge Management der Universität Siegen entstanden. Es ist der Versuch, einen umfassenden
Überblick des Themas zu geben.
Neben einer Einführung in die grundlegenden Konzepte werden
zahlreiche konkrete Verfahren in kompakter Form vorgestellt. Dadurch wird gleichzeitig die Entwicklungsgeschichte dieses noch relativ jungen Forschungsgebietes illustriert.
André Klahold,
Siegen, Januar MMIX

VII

sUppLex

Inhaltsverzeichnis

1 Überblick ..................................................................................................1
1.1 Grundbegriffe ...................................................................................1
1.1.1 Empfehlungssystem...................................................................1
1.1.2 Personalisierung .........................................................................3
1.1.3 Suchverfahren .............................................................................3
1.2 Anwendungsgebiete .........................................................................4
1.2.1 Inhalte ..........................................................................................5
1.3 Entwicklungsgeschichte .................................................................16
2 Grundlagen ............................................................................................21
2.1 Fachtermini.......................................................................................21
2.1.1 Allgemein ..................................................................................21
2.1.2 Eigenschaftsanalyse..................................................................23
2.1.3 Metadaten ..................................................................................28
2.1.4 Linguistik...................................................................................32
3 Methoden von Empfehlungssystemen...............................................37
3.1 Die Qualität von Empfehlungen ...................................................37
3.1.1 Nützlichkeit als Maßstab .........................................................38
3.1.2 Ähnlichkeit als Maßstab ..........................................................39
3.1.3 Expertenempfehlungen und Referenz-Daten.......................39
3.1.4 Precision und Recall .................................................................40
3.2 Content Based Filtering ..................................................................42
3.2.1 Eigenschaftsanalyse..................................................................42
3.2.2 Eigenschaftsanalyse am Beispiel von Textdokumenten......42
3.2.3 Repräsentation der Eigenschaften..........................................56
3.2.4 Ähnliche Elemente als Empfehlungen ..................................58
3.2.5 Alternative Verfahren ..............................................................59
3.3 Collaborative Filtering ....................................................................62

sUppLex

Inhaltsverzeichnis
3.3.1 Der benutzerbezogene Algorithmus......................................63
3.3.2 Der elementbasierte Algorithmus ..........................................64
3.3.3 Modell- und speicherbasiertes Verfahren .............................65
3.3.4 Nachteile des Collaborative Filtering ....................................66
3.4 Hybride Verfahren ..........................................................................68
3.5 Ähnlichkeit als Selektionskriterium..............................................68
3.5.1 Distanz und Ähnlichkeit..........................................................71
3.5.2 Cosinus.......................................................................................71
3.5.3 Pearson Korrelationskoeffizient .............................................72
3.5.4 Overlap Koeffizient ..................................................................73
3.5.5 Dice Koeffizient.........................................................................73
3.5.6 Jaccard Koeffizient....................................................................74
3.5.7 Euklidscher Abstand ................................................................75
3.5.8 Mutual Information..................................................................75
3.5.9 Nearest Neighbours .................................................................76
3.6 Klassifikationsverfahren .................................................................77
3.6.1 Minimum Description Length (MDL) ...................................77
3.6.2 Naiver Bayes-Klassifikator ......................................................79
3.6.3 Bayes´sches Netz.......................................................................80
3.6.4 ID3...............................................................................................82
3.6.5 K-Means-Clustering .................................................................86
4 Anwendungen .......................................................................................87
4.1 Collaborative Filtering-Systeme ....................................................89
4.1.1 Tapestry .....................................................................................89
4.1.2 Ringo ..........................................................................................90
4.1.3 GroupLens .................................................................................92
4.1.4 Siteseer .......................................................................................93
4.1.5 Jester (Eigentaste) .....................................................................94
4.1.6 Amazon......................................................................................95
4.1.7 SurfLen.......................................................................................96
4.1.8 PocketLens.................................................................................98
4.1.9 PACT ........................................................................................100

sUppLex

Inhaltsverzeichnis
4.2 Content Based Filtering-Systeme ................................................102
4.2.1 The Information lens ..............................................................102
4.2.2 Infoscope..................................................................................103
4.2.3 Newsweeder............................................................................104
4.2.4 Letizia.......................................................................................105
4.2.5 WebWatcher ............................................................................107
4.2.6 Syskill & Webert .....................................................................109
4.2.7 Remembrance Agent..............................................................110
4.2.8 InfoFinder ................................................................................111
4.2.9 Amalthaea................................................................................113
4.2.10 AgentDLS ..............................................................................114
4.2.11 Webmate ................................................................................116
4.2.12 SLIDER...................................................................................117
4.2.13 LexicalChainer ......................................................................119
4.2.14 NewsDude.............................................................................121
4.2.15 SIFT.........................................................................................122
4.2.16 Watson ...................................................................................124
4.2.17 LIBRA.....................................................................................126
4.2.18 Margin Notes ........................................................................127
4.2.19 Jimminy..................................................................................128
4.2.20 SUITOR ..................................................................................129
4.2.21 PRES .......................................................................................130
4.2.22 WebSail ..................................................................................132
4.2.23 WAIR......................................................................................133
4.2.24 Powerscout ............................................................................135
4.2.25 CALVIN .................................................................................136
4.2.26 WordSieve .............................................................................138
4.2.27 MetaMarker...........................................................................140
4.2.28 WebTop..................................................................................141
4.2.29 INFOS.....................................................................................142
4.3 Hybride Systeme ...........................................................................144
4.3.1 Fab ............................................................................................144

sUppLex

Inhaltsverzeichnis
4.3.2 PHOAKS ..................................................................................145
4.3.3 Let´s Browse ............................................................................146
4.3.4 CASMIR ...................................................................................148
4.3.5 LaboUr .....................................................................................149
4.3.6 Tango........................................................................................150
4.3.7 Nakif .........................................................................................152
4.3.8 MovieLens ...............................................................................153
Literaturverzeichnis ................................................................................155
Abbildungsverzeichnis ...........................................................................167
Stichwortverzeichnis...............................................................................171

XII

sUppLex

1 Überblick
1.1 Grundbegriffe
1.1.1 Empfehlungssystem
Ein Empfehlungssystem (oft auch „Recommender System“ genannt) ist ein
System, das einem Benutzer in einem gegebenen Kontext aus einer gegebenen Entitätsmenge aktiv eine Teilmenge „nützlicher“ Elemente empfiehlt.

Definition
des Begriffes
Empfehlungssystem

Der Kontext konstituiert sich dabei aus dem Benutzerprofil P, der Entitätsmenge M und der Situation S.
Dabei kann das Profil P aus expliziten (Geschlecht, Alter, Interessensgebiete etc.), und impliziten Informationen (Besuchshäufigkeit einer Website,
gelesene Texte, gekaufte Produkte etc.) bestehen.
Die Entitätsmenge M zählt zum Kontext, da sich auch alleine aus Ihrer Änderung (Neuzugang von Entitäten) und ohne Änderung des Profils eine
Empfehlung ergeben kann.
Die Situation S konstituiert sich aus Rahmenparametern der realen Welt
(Datum, Uhrzeit, Geoinformation, verwendetes Endgerät des Benutzers,
gerade angezeigter Text im Browser des Benutzers etc.).
Die empfohlenen Elemente T (Teilmenge von M) sollten den Nutzen des
Benutzers B im gegebenen Kontext K maximieren. Formal besteht die Aufgabe eines Empfehlungssystems daher in folgender Optimierung:

max Nutzwert B, K , T

mit

P, M , S

Dabei kommt der Definition der Nutzwertfunktion offensichtlich
große Bedeutung zu. Der Aspekt der „Nützlichkeit“ von Empfehlungen wird daher später noch genauer betrachtet.
Bei den Elementen der Entitätsmenge M kann es sich um so unterschiedliche Dinge wie Bücher, Musikstücke, Konzerte, Reisen, Nachrichten, Fachartikel, E-Mails, Fachleute etc. handeln.
Im Folgenden wird für diese Elemente der Begriff Empfehlungselemente verwendet.
Die Qualität eines Empfehlungssystems ist primär vom Verfahren
zur Selektion der Empfehlungen abhängig. Es sollte alle verfügbaren

sUppLex

1 Überblick
Informationen (Elemente der Entitätsmenge M) berücksichtigen und
aus diesen nur die „nützlichsten“ (für den Benutzer im gegebenen
Kontext) als Empfehlung anbieten.

Bild 1: Ein
Empfehlungssystem
selektiert aus
der Menge
möglicher
Entitäten eine
Teilmenge,
die es dem
Benutzer
empfiehlt

Die angewendeten Verfahren zur Selektion „nützlicher“ Empfehlungen werden traditionell in drei wesentliche Gruppen gegliedert. Solche, die auf Basis von ähnlichen Benutzerprofilen arbeiten, bezeichnet man als Collaborative Filtering-Verfahren. Solche, die sich die Eigenschaften der Entitäten der Menge M zunutze machen, bezeichnet
man als Content Based Filtering-Verfahren. Und Systeme mit einer
Mischung beider Ansätze bilden die dritte Gruppe der sogenannten
Hybrid-Verfahren.

sUppLex

1.1 Grundbegriffe

1.1.2 Personalisierung
Der Begriff Personalisierung wird oftmals als synonym zur Bezeichnung Empfehlungssystem verwendet, ist aber eigentlich umfassender:

Personalisierung ist die Anpassung von Informationen, Diensten oder Produkten an die definierten oder vermuteten Bedürfnisse einer Person. Die
Anpassung kann aufgrund des Personenprofils, der aktuellen Situation der
Person, aber auch durch aktive „Personalisierung“ durch den Anwender
erfolgen. Letzteres erfolgt meist interaktiv durch eine Auswahl von n aus m
Optionen. Auf Basis des Profils kann die Anpassung automatisiert durch
Software oder manuell durch einen Menschen erfolgen.

Personalisierung ist ein
recht weit
gefasster
Begriff

Beispiele für Personalisierung reichen von der Anpassung einer
Software an die eigenen Bedürfnisse über die individuelle Konfektionierung von Schuhen bis zum personalisierten Werbebrief.
Alternativ zum Begriff Personalisierung wird in der englischsprachigen Literatur auch der Begriff Customization verwendet.

1.1.3 Suchverfahren
Suchverfahren (Information Retrieval) werden beispielsweise von
Suchmaschinen oder Desktop-Suchen eingesetzt. Sie liefern dem Benutzer auf Basis einer aktiven Anfrage Suchergebnisse (meist in Listenform).
Der wesentliche Unterschied zu Empfehlungssystemen besteht also
darin, dass der Benutzer die Empfehlungen nicht automatisch erhält,
sondern diese aktiv durch Formulierung und Absenden einer Suchanfrage anfordern muss.

Suchverfahren
erfordern das
aktive
Formulieren
einer Anfrage

Der Übergang zwischen Suchverfahren und Empfehlungssystem ist
in der Praxis allerdings fließend. Wird neben der expliziten Suchanfrage auch der aktuelle Kontext oder das Profil des Benutzers einbezogen, so liegt ein Mischverfahren vor. Und bei der sogenannten
Interactive Query Expansion wird beispielsweise die Suchanfrage
durch Empfehlung weiterer Suchworte (M wird hier aus der Perspektive des Empfehlungssystems durch die Worte, nicht die Texte gebildet) ergänzt.

sUppLex

1 Überblick

1.2 Anwendungsgebiete
Die Anwendungsgebiete für Empfehlungssysteme sind so vielfältig,
dass im Folgenden nur ein grober Überblick und insbesondere ein
Gefühl für die Bandbreite der Einsatzmöglichkeiten gegeben werden
soll. Zunächst einmal kann man eine sehr grobe Einteilung von Empfehlungssystemen auf Basis einer Typisierung der ausgesprochenen
Empfehlungen vornehmen. Dies sind im Wesentlichen:

Bild 2:
Differenzierung von
Empfehlungssystemen
anhand der
Typisierung
der ausgesprochenen
Empfehlungen

Im Folgenden finden sich aktuelle Beispiele im Kontext dieser Typisierung.

sUppLex

1.2 Anwendungsgebiete

1.2.1 Inhalte
Die Empfehlung von Inhalten (engl. Content) dürfte das populärste
Einsatzgebiet von Empfehlungssystemen sein. Und innerhalb dieser
Domäne stellen wiederum Produktempfehlungen den am stärksten
vertretenen Einsatzbereich dar.
1.2.1.1 Produkt-Empfehlungen
Der Webshop Amazon (www.amazon.de) zeigt dem Benutzer in Abhängigkeit vom aktuell betrachteten oder gekauften Buch weitere
Bücher als Empfehlungen.
Der Film-Verleih Amango (www.amango.de) empfiehlt dem Benutzer
in Abhängigkeit von bewerteten Film-DVD andere DVD. Als Basis
dient dabei die Bewertung von DVD durch Benutzer mit ähnlichem
Profil.
Der Internet-Shop Baby-Walz (www.baby-walz.com) empfiehlt zum
aktuell gezeigten Produkt passende Produkte. Dies erfolgt auf Basis
der Produktbeziehungen sowie des Kaufverhaltens anderer Kunden,
die auch das angezeigte Produkt gekauft haben.
Bild 3:
Kaufempfehlungen auf
Basis von
Produktverbindungen
und Kaufverhalten
anderer
Benutzer

sUppLex

1 Überblick
Auf der Website CHIP (www.chip.de) werden dem Benutzer in Abhängigkeit von getesteten Produkten günstige Kaufoptionen empfohlen. Als Basis dient dabei die Verbindung von redaktionellen Artikeln
und Produkten.
Bild 4: ShopEmpfehlungen auf Basis
von Verbindung redaktioneller
Artikel zu
Produkten

sUppLex

1.2 Anwendungsgebiete
1.2.1.2 Text-Empfehlungen
Die Website der Handwerkszeitung (www.handwerksszeitung.de)
empfiehlt dem Benutzer in Abhängigkeit vom aktuell betrachteten
Artikeltext inhaltlich verwandte Artikel auf Basis der Analyse unstrukturierter Texte.

Bild 5: TextEmpfehlungen auf Basis
von inhaltlicher Ähnlichkeit zum
angezeigten
Artikeltext

Auf der Website Individual.com (www.individual.com) werden dem
Benutzer in Abhängigkeit vom eigenen Profil, das manuell durch
Selektion aus umfangreichen Listen definiert wird, aktuell passende
Texte empfohlen.

sUppLex

1 Überblick
1.2.1.3 Bild-Empfehlungen
Bei photoree.com werden dem Benutzer nach der Bewertung von 100
Bildern Empfehlungen für Bilder geliefert, die auf der Bewertung
anderer Benutzer, die dem eigenen Bewertungsprofil ähnlich sind,
geliefert.
Bild 6: BildEmpfehlungen auf Basis
der eigenen
Bewertung
und der
Ähnlichkeit
zur
Bewertung
anderer
Benutzer

Pixsta.com empfiehlt dem Benutzer nach der Auswahl eines Bildes
(konkret handelt es sich um Produktfotos) weitere Bilder, die von
Form oder Farbe ähnlich sind.

sUppLex

1.2 Anwendungsgebiete
1.2.1.4 Audio-Empfehlungen
Bei Last.fm (www.lastfm.de) werden dem Benutzer Musikstücke
empfohlen, deren Interpreten zu einem gewählten Interpreten ähnlich sind. Dabei werden die Profile anderer Benutzer ausgewertet, um
ähnliche Interpreten zu finden.
Bild 7: MusikEmpfehlungen auf Basis
der eigenen
Bewertung
und der
Ähnlichkeit
zur Bewertung anderer
Benutzer

Auf der Website Audiobaba (www.audiobaba.com) werden dem Benutzer Musikstücke empfohlen, die zu dem vom Benutzer gewählten
Musikstück (das wie bei einer Suchmaschine gesucht wird) ähnlich
sind. Dabei werden die Audiostreams analysiert und unterschiedliche Eigenschaften der Musikstücke berücksichtigt.
Empfehlungen auf Basis der Eigenschaften manuell gewählter Musikstücke werden dem Benutzer auf ZuKool (http://zukool.com) empfohlen. Der Benutzer kann die Empfehlungen zusätzlich durch Bewertungen beeinflussen.

sUppLex

1 Überblick
1.2.1.5 Video-Empfehlungen
MyStrands.tv (www.mystrands.tv) empfiehlt dem Benutzer Videos
von YouTube, deren Interpreten zu einem gewählten Interpreten
ähnlich sind. Dabei werden die Profile anderer Benutzer ausgewertet,
um ähnliche Interpreten zu finden.
Bild 8: VideoEmpfehlungen auf Basis
der Ähnlichkeit zu einem
gewählten
Video

sUppLex

1.2 Anwendungsgebiete
Bei AmazNode (http://amaznode.fladdict.net/about_en.html) erhält
der Benutzer Film-Empfehlungen. Dabei werden ausgehend von
einem Film auf Basis des Kaufverhaltens anderer Benutzer ähnliche
Filme empfohlen. AmazNode nutzt die Daten von Amazon.com und
ist ein schönes Beispiel dafür, dass auch die Visualisierung der Empfehlungen eine bedeutende Rolle spielt.

Bild 9: FilmEmpfehlungen auf Basis
des Kaufverhaltens anderer Benutzer

sUppLex

1 Überblick
Movielens (ttp://movielens.umn.edu) empfiehlt dem Benutzer Filme,
die den besten der eigenen Filmbewertungen entsprechen. Dabei
werden die Profile anderer Benutzer ausgewertet, um Filme zu finden.

Bild 10: FilmEmpfehlungen auf
Basis der
eigenen
Bewertung
und der
Ähnlichkeit
zur
Bewertung
anderer
Benutzer

sUppLex

1.2 Anwendungsgebiete
1.2.1.6 Prozess-Empfehlungen
Bei Map24 (www.map24.de) werden dem Benutzer nach Eingabe
vom Ausgangspunkt und Endpunkt einer geplanten Reise neben der
Fahrempfehlung auch Tankstellen aufgrund ihrer Nähe zur Reiseroute empfohlen.
Scirus (www.scirus.com) zeigt dem Benutzer nach Eingabe einer
Suchanfrage neben den Ergebnissen auch Vorschläge zur Eingrenzung des Suchfeldes.
Bild 11:
Empfehlungen zur
Einschränkung des
Suchfeldes

sUppLex

1 Überblick
Newsisfree (www.newsisfree.com) präsentiert dem Benutzer nach
Eingabe einer Suchanfrage in verschiedenen Dimensionen (Aktualität,
Popularität etc.) die Ergebnisse in grafischer Form. Es ist ein schönes
Beispiel für den fließenden Übergang von Such- zu Empfehlungssystemen.
Bei Foodio54 (http://foodio54.com) werden dem Benutzer nach Eingabe einer Suchanfrage für Restaurants die zum Suchbegriff und der
Lokation passenden Restaurants in Abhängigkeit von der Bewertung
durch andere Benutzer empfohlen.
Bild 12:
Empfehlungen auf
Basis
inhaltlicher
und
geografischer
Vorgaben auf
Basis von
Benutzerbewertungen

sUppLex

1.2 Anwendungsgebiete
1.2.1.7 Personenempfehlungen
Biomedexperts (www.biomedexperts.com) liefert dem Benutzer nach
Angabe eines medizinischen Sachgebietes Experten auf Basis der
Häufigkeit von wissenschaftlichen Abhandlungen. Dabei kann auch
eine geobasierte Visualisierung abgerufen werden, um Experten zum
Thema zu selektieren.
Bild 13:
Empfehlungen von
Experten auf
Basis der
Autoren in
wissenschaftlichen
Abhandlungen in
geographischer
Visualisierung

Bei Google Scholar (http://scholar.google.com) werden dem Benutzer
nach Angabe eines Suchbegriffes wissenschaftliche Abhandlungen
mit Angabe des Autors (Experten) und der Zitierhäufigkeit gegeben.
Zudem werden die vermeintlich wichtigsten Autoren auf Basis dieser
Angaben ermittelt und angezeigt.

sUppLex

1 Überblick

1.3 Entwicklungsgeschichte
Vor der Aufgabe, kontextuell nützliche Informationen zu finden,
stehen wir Menschen vermutlich bereits so lange, wie wir die Fähigkeit besitzen, Informationen zu archivieren.
Das unscheinbare Wort "nützlich" spielt im Umfeld von Empfehlungssystemen eine sehr bedeutende Rolle. Es soll daher später in
gebührendem Umfang darauf eingegangen werden.
Dem Alter der Problemstellung entsprechend vielfältig sind die vorhandenen Lösungsansätze. Von den ersten thematisch gegliederten
Bibliotheken über umfangreiche Bibliographien bis zu dem von Vannevar Bush erdachten Hyperlink-Konzept [1] hat sich auch die Technik des Empfehlens weiter entwickelt.
Mit wachsender Informationsmenge wird die Problemlösung deutlich erschwert, da es nicht mehr nur gilt, "nützliche" Informationen
zu finden, sondern diejenige mit der höchsten Relevanz – also die mit
dem höchsten Grad an „Nützlichkeit“ zu selektieren. Wir wollen
"Relevanz" im Folgenden im Sinne von "Nutzwert für den Kontext"
verstehen. Es ist daher offensichtlich keine objektiv messbare, sondern aufgrund der subjektiven Komponente eine nur empirisch fassbare Größe.
Das Überangebot an
Information
macht die
Selektion der
„nützlichen“
Elemente
immer
wichtiger.

Das mit einfacherer Archivierung und Verbreitung entstehende
Überangebot an Information wird akademisch bereits seit Beginn des
20. Jahrhunderts thematisiert. Exemplarisch sei auf C. Oppenheimers
„Die papierne Sintflut“ [2] aus dem Jahr 1927 verwiesen. Über fünfzig Jahre später hat sich die Situation aufgrund exponentiellen
Wachstums des Datenvolumens weiter verschärft. So prägte 1982 der
amerikanische Trendforscher John Naisbitt den Satz "Wir ertrinken in
Informationen, aber hungern nach Wissen" [3]. Die Informationsmenge
wächst mittlerweile nicht mehr exponentiell. Dies ist allerdings nur
dem bereits erreichten extrem hohen Maß an Informationsausstoß zu
verdanken [4].

Im Jahr 1958
beschreibt
Hans Peter
Luhn die
Funktionsweise eines
Empfehlungssystems.

Die erste akademische Arbeit mit Bedeutung auf dem Feld der Empfehlungssysteme dürfte „A Business Intelligence System“ [5] von
Hans-Peter Luhn aus dem Jahr 1958 sein. Darin beschreibt er ein System, das automatisiert Dokumente analysiert und als Empfehlung an
definierte Stellen in einer Organisation leitet. Er spricht allerdings
nicht von Recommendations (Empfehlungen), sondern von Selective
dissemination of new information (Selektiver Verbreitung neuer Information). Als Basis für die Empfehlungen dienen dabei explizite Profi-

sUppLex

1.3 Entwicklungsgeschichte
le, die auf Basis von Dokumenten erzeugt werden, welche die gewünschten Themen beschreiben. Beim Eingang neuer Dokumente
werden diese dann mit den Profilen in einem „Comparison Device“ verglichen. Der Vergleich bewertet den Grad der Übereinstimmung zwischen Dokument und Profil. Dass die Arbeit im Jahr 1958
erschien, ist kein Zufall. Ein Jahr zuvor, am 4. Oktober 1957, wurde
mit dem Sputnik der erste Satellit vom Boden der Sowjetunion gestartet. Dadurch wurde der sogenannte „Sputnikschock“ ausgelöst.
Die USA – vom technologisch unterschätzten Rivalen überholt – startete damals eine der größten Bildungsinitiativen.
Bild 14: Der
Sputnik
markierte
nicht nur den
Beginn der
Raumfahrt,
sondern legte
indirekt auch
das
Fundament
für das
Information
Retrieval und
damit für die
Empfehlungssysteme.

Zeitlich betrachtet wurden die Collaborative Filtering-Verfahren gefolgt von den hybriden Ansätzen erst einige Zeit nach den Content
Based Filtering-Ansätzen entwickelt. Im Folgenden findet sich eine auf
der Zeitachse aufbereitete Übersicht relevanter Vertreter der drei
Gruppen.

sUppLex

1 Überblick
Bild 15:
Content
Based
Filteringbasierte
Empfehlungssysteme –
Übersicht der
zeitlichen
Entwicklung

sUppLex

1.3 Entwicklungsgeschichte
Bild 16:
Collaborative
Filteringbasierte
Empfehlungssysteme –
Übersicht der
zeitlichen
Entwicklung

sUppLex

1 Überblick
Bild 17:
Hybride
Empfehlungssysteme –
Übersicht der
zeitlichen
Entwicklung

sUppLex

2 Grundlagen
Im vorangegangenen Überblick ist unter anderem auch die Vielfalt
der unterschiedlichen Blickwinkel auf das Thema Empfehlungssysteme deutlich geworden. Um die wesentlichen Eigenschaften der
beiden Grundprinzipien Collaborative Filtering und Content Based Filtering vorzustellen, werden in diesem Kapitel zunächst wichtige Begriffe und Algorithmen eingeführt.

2.1 Fachtermini
Die wichtigsten Fachbegriffe aus dem Umfeld der Empfehlungssysteme werden im Folgenden eingeführt. Gegliedert sind diese nach
den Bereichen „Allgemein“, „Eigenschaftsanalyse“, „Metadaten“ und
„Linguistik“.

2.1.1 Allgemein
Eine Session ist definiert als die Sequenz von aufeinander folgenden, mit
Datentransfer verbundenen Aktionen, die ein Benutzer während des
Besuches einer Website ausführt.

Ein Cookie ist eine lokal im Browser des Benutzers gespeicherte Datei, in
der unter anderem Informationen zum Benutzer und zur aktuellen Session
abgelegt werden können.

Ein Hyperlink ist ein Verweis von einer bestimmten Stelle einer Webseite
auf eine andere Webseite oder eine bestimmte Stelle in einer anderen
Webseite.

Session

Hyperlink

Die Hyperlinks sind das wesentliche Merkmal des Hypertextes. Im
Vergleich zu klassischen Querverweisen, kann man durch Anklicken
des Hyperlinks das verlinkte Ziel aufrufen.

sUppLex

2 Grundlagen
Suchmaschine

Eine klassische Suchmaschine ist eine Software zur Recherche von
Textdokumenten, die in unterschiedlichen Formaten und an
unterschiedlichen Orten vorliegen.

Nach Eingabe einer Suchanfrage liefert eine Suchmaschine eine Liste
mit Verweisen auf potenziell relevante Dokumente. Diese werden
dabei in der Regel durch eine automatisch aus dem Text gewonnene
Kurzbeschreibung ergänzt.
Suchanfrage

Eine Suchanfrage (kurz Anfrage; engl. Query) ist ein aus einem oder
mehreren Worten bestehender Text, der von einer Suchmaschine als
Ausgangswert für eine Recherche verwendet wird.

Potenziell kann eine Suchanfrage auch logische Operatoren enthalten
(UND, NICHT etc.), mit denen komplexere Anfragen erzeugt werden
können.
Profil

Ein Benutzerprofil (kurz Profil) besteht aus einer Menge von
Empfehlungselementen, die potenziell mit einer Benutzerbewertung und
dem Zeitpunkt der Aufnahme ins Profil versehen sind.

Alternativ kann ein Benutzerprofil auch aus Eigenschaftswerten von
Empfehlungselementen bestehen, die das Interessensgebiet des Benutzers widerspiegeln.
Ein flüchtiges Profil ist nur während einer begrenzten Zeitspanne existent. In der Regel handelt es sich dabei um die Dauer einer Session.
Ein persistentes Profil bleibt für längere Dauer und insbesondere über
verschiedene Sessions hinweg erhalten. Dazu muss der Benutzer
erkannt werden, was in der Regel eine Anmeldung erforderlich
macht.
Kontext

Unter Kontext soll im Folgenden die Kombination von Benutzerprofil, der
Menge der Empfehlungselemente und der aktuellen Situation verstanden
werden.

sUppLex

2.1 Fachtermini
Eine Situation konstituiert sich aus Rahmenparametern der realen Welt wie
dem Datum, der Uhrzeit, der Geoinformation, dem verwendeten Endgerät
des Benutzers, dem gerade angezeigten Text im Browser des Benutzers etc.

Im Umfeld von Empfehlungssystemen stellen Trainingsdaten (auch Lernmenge) eine möglichst repräsentative Teilmenge der Menge aller Empfehlungselemente dar.

Situation

Trainingsdaten

Auf Basis der Trainingsdaten und manuell vorgenommener Klassifikation leiten beispielsweise verschiedene Klassifikationsverfahren
automatisch (maschinelles Lernen) Klassifikationsregeln ab.

Eine Benutzerbewertung für ein Empfehlungselement ist im einfachsten Fall
ein binärer Wert ("interessant", "nicht interessant").

Benutzerbewertung

Alternativ erfolgt die Bewertung auf einer Skala (beispielsweise
"nicht interessant", "etwas interessant", "interessant", "sehr interessant").

2.1.2 Eigenschaftsanalyse
Die Eigenschaftsanalyse (auch als Feature Selection bezeichnet) spielt
bei Content Based Filtering-Verfahren eine wichtige Rolle. Eine genaue
Definition findet sich in 3.2.1 Eigenschaftsanalyse. Aufgrund des Fokus
auf Textdokumente als Empfehlungselemente werden im Folgenden
auch nur die wichtigsten Begriffe aus diesem Umfeld aufgeführt.

Ein Korpus oder Textkorpus oder auch Corpus besteht aus einer Menge von
Texten, die im Rahmen einer Analyse als Grundlage dienen.

Korpus

Ein Korpus wird im Umfeld von Empfehlungssystemen sowohl zur
Gewinnung statistischer Informationen (Worthäufigkeiten, Kollokationen etc.), als auch zur Durchführung von Testreihen, sowie der
Gewinnung von Trainingsdaten verwendet.
Bedeutende Standard-Korpora sind der Brown Korpus für Texte in
amerikanischem Englisch, der erstmals 1964 veröffentlicht wurde.
Der LOB Korpus ist eine Abwandlung des Brown Korpus für britisches Englisch. Mit WordNet pflegt die Princeton University seit 1985

sUppLex

2 Grundlagen
einen Wortschatz der englischen Sprache, der auch weitergehende
Beziehungen (Synonyme, Hyponyme etc.) abbildet, also eigentlich einen Thesaurus darstellt.
Für die deutsche Sprache relevante Korpora sind der Deutsche Referenzkorpus des Institut für Deutsche Sprache, das WordNet Pendant
GermaNet der Universität Tübingen, sowie das Wortschatz-Projekt der
Universität Leipzig.
Mit dem Schweizer Text Korpus stellt die Universität Basel einen spezifischen Korpus für Schweizer Deutsch im Testbetrieb bereit. Ein analoges Projekt für Österreich befindet sich mit dem Austrian Academy
Corpus im Aufbau.
Wortvektor

Der Volltext eines Empfehlungselementes (hier ein Textdokument) oder ein
aus Worten bestehendes Benutzerprofil kann durch einen Wortvektor
dargestellt werden. Dabei stellt jede Komponente des Vektors ein
bestimmtes Wort – potenziell mit dessen Gewichtung (siehe dazu 3.2.2.2
TF-IDF) - dar.

Durch diese Vereinheitlichung werden Texte in Form der Wortvektoren im Vektorraum mathematisch vergleichbar. Als Sonderfall geben
binäre Wortvektoren nur an, ob ein Wort in einem Text vorhanden ist.
Analog zu den Empfehlungselementen können auch Benutzerprofile
als Wortvektoren dargestellt werden.
Viele Worte wie beispielsweise "schreiben" kommen in der Sprachanwendung in zahlreichen Flexionen vor. So findet sich neben
„schreiben“ auch "geschrieben" (Tempus-Flexion), "schreibt" (Numerus-Flexion). Das Wort „Haus“ kommt als „Hauses“ (Kasus-Flexion),
„Häuser“ (Numerus-Flexion) vor.
Stemming

Unter Stemming versteht man die algorithmische Reduktion von Worten
auf deren Wortstämme.

Zwei bekannte Stemming-Verfahren sind die von Lovins [6] und Porter [7]. Einen guten Überblick und einen Vergleich von drei Verfahren gibt die Arbeit von Paice [8]. Durch Stemming wird versucht,
Wortformen automatisiert auf Lexeme zurückzuführen, um begrifflich zusammengehörige Wortformen durch dieselbe Zeichenkette
(das Lexem) darzustellen. In der Regel wird dies durch Heuristiken

sUppLex

2.1 Fachtermini
wie der Vereinheitlichung von Umlauten und "ß/ss" oder dem Abtrennen von Suffixen (beispielsweise "schreib-en") erreicht.
Damit werden "Pseudo-Lexeme" erzeugt, die aber gerade in der
deutschen Sprache mit ihren stark unterschiedlichen Flexionen
("schreibt", "geschrieben") problematisch sind. Zusätzlich gehen beim
Stemming Informationen verloren, die durch die Wortform codiert
werden. Beispielsweise die zeitliche Information (Vergangenheit) in
"geschrieben". Verschiedene Untersuchungen belegen, dass einfaches
Stemming im Mittel keinen positiven Einfluss auf Empfehlungen hat
[9].

Ein Inverser Index (engl. reverse index) ist eine Datenstruktur, die für jedes
Wort, das in mindestens einem Text eines Korpus vorkommt, alle Texte
aufführt, in denen dieses Wort vertreten ist.

Inverser
Index

Invertiert ist ein solcher Index, da er nicht die in einem Text enthaltenen Worte, sondern die Texte, in denen ein Wort enthalten ist, liefert.
Für einen Korpus mit den Texten T1=“Das ist ein Text“ und T2=“Und
das ist noch ein Text“ würde der Inverse Index wie folgt aussehen
(wenn man die Klein-/Großschreibung nicht beachtet):
„das“

: {T1,T2}

„ist“

: {T1,T2}

„ein“

: {T1,T2}

„text“

: {T1,T2}

„und“

: {T2}

„noch“

: {T2}

Ein Stoppwort ist ein Wort, das für die Eigenschaftsanalyse eines Textes
keine Bedeutung haben soll.

Stoppwort

Stoppworte sind in der Regel die am häufigsten vorkommenden
Worte einer Sprache (feste Stoppwortliste) oder einer Menge von
Dokumenten (berechnete Stoppwortliste). Eine Stoppwortliste reduziert den Umfang eines Inversen Index signifikant.

sUppLex

2 Grundlagen
Zipf´sches
Gesetz

Nach dem Zipf´schen Gesetz [10] können schon weniger als 50
Stoppworte mit dem höchsten Rang, die nicht in den Inversen Index
aufgenommen werden, das Volumen des Inversen Index halbieren.
Der Rang eines Wortes ist seine Position in der Reihenfolge, der nach
ihren Häufigkeiten des Vorkommens in Texten absteigend sortierten,
Worte.
Die Häufigkeit NC(W) eines Wortes W ist dessen Anzahl über alle
Texte in einem Korpus C.
Das Zipf´sche Gesetz besagt, dass die Häufigkeit eines Wortes umgekehrt proportional zu seinem Rang ist. Mit k als korpusabhängiger
Konstante folgt daraus:

N C W * Rang (W )

Daraus lässt sich ableiten, dass relativ wenige Worte einen großen
Anteil aller Texte ausmachen:
Bild 18:
Zipf´sches
Gesetz –
Schematisierter
Zusammenhang von
Häufigkeit
und Rang

Das idealisierte Verhältnis zwischen Rang und Häufigkeit approximiert die Realität besonders dann gut, wenn der Korpus C sehr groß
ist oder gar die Verwendung eine natürliche Sprache in großem Um-

sUppLex

2.1 Fachtermini
fang repräsentiert. Auf Basis der Analyse des Projektes "Deutscher
Wortschatz" der Universität Leipzig [12] ergibt sich folgender Vergleich des Zipf´schen Gesetzes zur Realität der deutschen Sprache.
Dabei wurden über 18 Millionen Wortinstanzen berücksichtigt:
Bild 19:
Korrelation
von Rang und
Häufigkeit
nach
Zipf´schem
Gesetz und in
der deutschen
Sprache
(logarithmische
Achsenskalierung)
aus [12]

Man sieht, dass Zipf´sches Gesetzt und reale Korrelation zwischen
Frequenz und Rang eines Wortes im Bereich mittlerer Frequenzen
sehr gut ist.
Allerdings existieren im unteren und oberen Bereiche deutliche Abweichungen. Diese Abweichungen können bei weniger großen und
thematisch fragmentierten Korpora noch stärker ausfallen.
Das Zerlegen eines Textes in zusammengehörige Zeichenketten
(Worte, Zahlen etc.) bezeichnet man als Token-Bildung (engl. Tokenization). Dies ist meist die Basis zur weitergehenden Textanalyse.

Ein Idiom ist eine feste (idiomatische) Kombination von Worten.

TokenBildung

Idiom

Die Bedeutung eines Idioms entspricht dabei nicht der Bedeutung
der kombinierten Worte.

sUppLex

2 Grundlagen
Beispiele für Idiome sind
– „gegen den Strom schwimmen“
– „etwas im Schilde führen“
– „den Löffel abgeben“
In allen Fällen ergibt sich der Sinn des Idioms nur in der konkreten
Kombination der Worte.
Kookkurrenz

Kookkurrenz ist die Wahrscheinlichkeit (korpus-abhängig, empirisch
ermittelt in Form der Häufigkeiten) mit der zwei Worte W1 und W2 in
einem Textfenster Fn von n Worten gemeinsam auftreten:

Kook n W1 ,W2

Kollokation

P W1 , W2 , Fn

Eine Kollokation liegt vor, wenn die Kookkurrenz Kookn(W1,W2) zweier
Worte W1 und W2 signifikant über dem Durchschnittswert Kn(Wi,Wj) aller
Wortpaare Wi, Wj liegt.

In der Linguistik werden oft weitere Kriterien für das Vorliegen einer
Kollokation gefordert, die jedoch im Rahmen der nachfolgenden Betrachtungen keine Rolle spielen.

2.1.3 Metadaten
Metadaten

Metadaten sind Empfehlungselementen manuell hinzugefügte strukturierte
Informationen zu deren Eigenschaften.

Es muss zwischen relationalen und autonomen Metadaten unterschieden werden. Erstere setzen Empfehlungselemente in eine bestimmte Relation zu anderen Empfehlungselementen in verschiedenen Ordnungsstrukturen. Wohingegen Letztere autonom am Emp-

sUppLex

2.1 Fachtermini
fehlungselemente mitgeführt und genutzt werden können. Nachfolgend werden einige Arten von Metadaten aufgeführt.
Eine Taxonomie ist ein Klassifikationsverfahren, das Gruppen von
Empfehlungselementen durch eine Einordnung in eine Hierarchie bildet.

Taxonomie

Bild 20:
Beispielhafte
Struktur einer
Taxonomie

Ein Thesaurus besteht aus einer Sammlung von Begriffen, die in einer
definierten Beziehung zueinander stehen.

Thesaurus

Neben der Hierarchie der Taxonomie in Form von Ober- und Unterbegriffen bestimmt ein Thesaurus vorrangig Synonyme.

Bild 21:
Beispielhafte
Struktur eines
Thesaurus

sUppLex

2 Grundlagen
Topic Map

Der durch ISO/IEC 13250 definierte Topic Map Standard bietet eine
standardisierte und implementationsunabhängige Notation, um "Topics" (Themen) und deren Beziehung zueinander und zu Texten zu
definieren.

Topic Maps fassen Texte durch Adressierung ("occurence") zu einer Gruppe
zusammen, die einem bestimmten Thema ("topic") zugeordnet ist.
Zwischen den Themen ("topics") selbst bestehen wiederum Beziehungen
("associations"). Durch Typisierung werden Themen ("topics") zu
gleichartigen Gruppen zusammengefasst (beispielsweise "Städte",
"Menschen" etc.).

Man kann eine Topic Map als einen mehrdimensionalen Themenraum betrachten, in dem die Orte durch Themen repräsentiert werden und die semantischen Abstände zwischen zwei Themen (auf
dem "association" Pfad) durch die Zahl der dazwischen liegenden
anderen Themen bestimmt werden.
Bild 22:
Beispielhafte
Struktur einer
Topic Map

sUppLex

2.1 Fachtermini
Eine Ontologie definiert Objekte und deren Relationen zueinander
(zum Beispiel mittels RDF). Sie definiert ein Datenmodell mit Entitätstypen und Entitäten (zum Beispiel mittels XML; unterstützt
Mehrsprachigkeit) und kann Semantik und einfache Abhängigkeiten
mit Hilfe des Ontologie-Vokabulars beschreiben (zum Beispiel mittels
OWL). Logische Zusammenhänge können mittels Regeln ausgedrückt werden (zum Beispiel mittels F-Logic).

Ontologie

Bild 23:
Beispielhafte
Struktur einer
Ontologie

Ein Schlagwort wird in der Regel zugeordnet, um eine eindeutige
Suche nach den Empfehlungselementen zu ermöglichen.

Schlagwort

Unter einem Schlagwort
wird ein natürlichsprachlicher Ausdruck
verstanden, der den Inhalt eines Textes möglichst kurz und präzise
wiedergibt.

Komplexe Inhalte werden in der Regel durch mehrere Schlagworte
beschrieben.
Grundlage für eine systematische Schlagwortvergabe ist in der Praxis
oft ein Verzeichnis der zu verwendenden Schlagwörter. Neben individuellen gibt es auch genormte Verzeichnisse wie beispielsweise die
Schlagwortnormdatei [13]. Siehe dazu auch 3.2.2.1 Schlagworte und
Schlüsselworte.

sUppLex

2 Grundlagen

2.1.4 Linguistik
Linguistik

Ein wesentliches Forschungsgebiet der Linguistik (Sprachwissenschaft)
ist das der Semantik.

Semantik

Die Semantik in unserem Sinne beschäftigt sich mit der Bedeutung
von sprachlichen Schriftzeichen – also dem geschriebenen Wort.

Synonym

Ein Synonym ist ein Wort, das zumindest teilweise die gleiche Bedeutung
wie ein Wort mit unterschiedlicher Schreibweise hat.

Beispiele für Synonyme sind:
– Bildschirm - Monitor - TFT
– Bank - Geldinstitut
– Computer - PC- Laptop
Homonym

Ein Homonym ist ein Wort, das bei identischer Schreib- und Sprechweise
eine unterschiedliche Bedeutung hat.

Noch genauer unterscheidet man:
– Homograph (auch Homogramm) = in gleicher Schreibweise
– Homophon = in gleicher Sprechweise
Das Wort „Spielende“ im Sinne von „Ende eines Spiels“ oder „die Spieler“ ist ein Beispiel für ein Homograph. Ebenso „aufnehmen“ im Sinne
von einen „Film aufnehmen“ oder „die Zügel aufnehmen“.
Bild 24: Zwei
Bedeutungen
des Homographs „Aufnehmen“.

sUppLex

2.1 Fachtermini
Ein Beispiel für Homophone sind die Worte „Lehre“ und „Leere“.

Ein Polysem ist ein Wort, das mehrere Bedeutungen hat. Im Gegensatz zum
Homonym müssen diese Bedeutungen aber inhaltlich verwandt sein.

Polysem

Ein Beispiel für ein Polysem ist das Wort „Pferd“ im Sinne des Reittieres und der Schachfigur.
Unter Assoziation versteht man die Verknüpfung zweier oder mehrerer gedanklicher Inhalte durch einen Menschen. Auf Worte bezogen
stellt die Wort-Assoziation Beziehungen zwischen unterschiedlichen
Worten auf Basis deren Bedeutung her.

Assoziation

Eine der problematischsten Begriffsdefinitionen ist die der Bedeutung
(engl. Meaning). Die Fragestellung lautet: was ist die Bedeutung von
Bedeutung? Es gibt nicht nur aufgrund der gegebenen sprachlichen
Rekursion keine einfache Antwort, sondern auch aufgrund der
Mehrdeutigkeit des Wortes „Bedeutung“.

Bedeutung

So kann „Bedeutung“ im Sinne einer Definition wie
„’Leere Flasche’ bedeutet, dass im Gefäß kein Inhalt ist“
verwendet werden oder im Sinn einer Implikation wie
„Die leere Flasche bedeutete, dass er weiter Durst leiden musste.“
oder um Wichtigkeit auszudrücken wie in
„Die leere Flasche war von großer Bedeutung für ihn.“.
Hier nun der Versuch, eine Definition für das Umfeld von Empfehlungssystemen zu geben:

Die Bedeutung eines Wortes (oder eines Begriffes, wie ein Wort in diesem
Zusammenhang oft bezeichnet wird) ist die inhaltliche Vorstellung, die ein
Mensch mit der Form des Wortes (der Zeichenkette bzw. dem
gesprochenen Wort) verbindet.

Daraus folgt unmittelbar, dass Worte mehrdeutig sind. Denn die
Bedeutung eines Wortes ist offensichtlich von mehreren Faktoren
abhängig. Jeder Mensch verbindet mit einem Wort unterschiedliche

sUppLex

2 Grundlagen
Assoziationen. Und auch für einen Menschen verändert sich die inhaltlichen Interpretation mit den Rahmenbedingungen wie Ort, Zeit
etc.
Polysemie

Diese Mehrdeutigkeit von Worten bezeichnet man in der Linguistik als
Polysemie.

Das Wort „Flasche“ hat nach einem mehrstündigen Marsch bei sengender Sonne durch eine heiße Wüste eine andere Bedeutung, als an
einem lauen Sommerabend in einem italienischen Restaurant an der
Küste des Mittelmeers. Die meisten Menschen werden im ersten Fall
an eine Wasserflasche und im zweiten Fall eher an eine Flasche guten
Weines denken.
Disambiguierung /
Monosemierung

Wie dieses Beispiel zeigt, können auch die umgebenden Worte die
Rahmenbedingungen bilden, welche die Bedeutung eines Wortes
maßgeblich beeinflussen.
Das ist eine wesentliche Eigenschaft, die sich die meisten Empfehlungssysteme für Textdokumente als Empfehlungselemente zunutze
machen. Insbesondere um die Mehrdeutigkeit (Polysemie) von Worten aufzulösen.
Diesen Vorgang bezeichnet man als Disambiguierung oder Monosemierung. Letzteres ist die Zurückführung auf eine Bedeutung oder ein
Semem.

sUppLex

2.1 Fachtermini

Bild 25:
Polysemie
kann durch
Monosemierung
aufgelöst
werden;
einem Lexem
(Wort) wird
ein
eindeutiges
Semem
(Bedeutung)
zugeordnet

Die Disambiguierung durch Worte im Umfeld eines Wortes hat eine
breite linguistische und philosophische Basis. Als Beispiele seien Zitate von Firth und Wittgenstein angeführt:
„You shall know a word by the company it keeps'' (Firth, [14])
„Man kann für eine große Klasse von Fällen der Benützung des Wortes
›Bedeutung‹ - wenn auch nicht für alle Fälle seiner Benützung - dieses Wort
so erklären: Die Bedeutung eines Wortes ist sein Gebrauch in der Sprache.“ (Wittgenstein, [15])

sUppLex

2 Grundlagen
Diese Aussagen werden durch verschiedene Untersuchungen gestützt [16], [17].
Hyponym

Hyperonym

Ein Hyponym ist ein Wort, das einem anderen Wort untergeordnet ist und
damit eine spezifischere Bedeutung besitzt als das übergeordnete Word,
das als Hyperonym bezeichnet wird.

Das Hyperonym enthält einen Teil der Bedeutungsbestandteile des
Hyponyms. Das Hyponym enthält alle Bedeutungsbestandteile des
Hyperonyms
und
dazu
noch
ein
oder
mehr
weitere
Bedeutungsbestandteile.

Das Wort „Ball“ ist beispielsweise Hyperonym der Hyponyme „Wasserball“ und „Fußball“.
Antagonym

Ein Antagonym ist ein Homonym dessen unterschiedliche Bedeutungen
sich widersprechen.

Ein Beispiel für ein solches Wort ist der „Quantensprung“, der im
physikalischen Sinne eine sehr kleine Änderung beschreibt, im übertragenen Sinne aber für große Veränderung verwendet wird.
Antonym

Zwei Worte sind Antonyme, wenn Sie Gegensätzliches bezeichnen.

Beispiele für solche Wortpaare sind „hell“ und „dunkel“ oder
„alt“ und „jung“.

sUppLex

3 Methoden von Empfehlungssystemen
Die Konzepte des Collaborative Filtering sind weitgehend unabhängig
von den betrachteten Empfehlungselementen. Die beim Content Based
Filtering angewendeten Verfahren hängen hingegen sehr stark von
den Eigenschaften der Empfehlungselemente ab, auf die sie angewendet werden sollen.
Um Redundanzen zu vermeiden, wird das Content Based Filtering im
Detail am Beispiel von Textdokumenten als Empfehlungselemente
vorgestellt.
Content Based Filtering für Bilder, Musik, Audio, Video etc. verwendet zwar andere Methoden zur Eigenschaftsanalyse, die grundlegenden Prinzipien der Verfahren zur Ermittlung von Empfehlungen sind
sich jedoch meist sehr ähnlich.

3.1 Die Qualität von Empfehlungen
Wie kann man die Güte von Empfehlungen bewerten? Gibt es ein
objektives Maß dafür?
Offensichtlich kann eine objektive Bewertung nur dann erfolgen,
wenn es eindeutige und allgemein anerkannte Entscheidungskriterien gibt. Daraus folgt, dass eine Funktion f bekannt sein muss, die
einem gegebenen Kontext K die besten Empfehlungen E1, E2, …, En
zuordnet:

f K

^E1 , E2 ,..., En `

Werden diese Empfehlungen von einem Empfehlungssystem im
Kontext K gegeben, so arbeitet das Verfahren optimal.
Ein Beispiel für eine objektiv bewertbare Empfehlung ist die
Fahrtstrecke von einem Ort A zu einem Ort B. Zur weiteren Vereinfachung sei angenommen, dass A und B nur durch zwei Gabelungen
voneinander getrennt seien:

sUppLex

3 Methoden von Empfehlungssystemen

Bild 26: Ein
Beispiel für
objektiv
bewertbare
Empfehlungen

Nur die Empfehlung zunächst „rechts“ und dann „links“ zu fahren
ist eine gute Empfehlung:

f A, B

^" rechts links"`

Die meisten Umgebungen, in denen Empfehlungssysteme zum Einsatz kommen sind deutlich komplexer als die oben beschriebene. Nur
selten lässt sich daher ein objektiver Bewertungsmaßstab anlegen.

3.1.1 Nützlichkeit als Maßstab
Wenn man kein objektives Bewertungsmaß hat, kann man sich noch
auf die Bewertung der Nützlichkeit durch den Benutzer stützen. Allerdings erfordert die Evaluation eines Empfehlungssystems dann
eine große Grundgesamtheit an Benutzern, die das System über einen
möglichst langen Zeitraum nutzen und die ausgesprochenen Empfehlungen bewerten, um belastbare Aussagen auf dieser empirischen
Basis abzuleiten.

sUppLex

3.1 Die Qualität von Empfehlungen

3.1.2 Ähnlichkeit als Maßstab
Oft besteht die Aufgabe des Empfehlungssystems darin, Empfehlungselemente mit der größten Ähnlichkeit zum Kontext K zu finden.
Konkret muss es dann Empfehlungselemente finden, die denen ähnlich sind, die durch das Profil P oder der Situation S gegeben sind. Im
Abschnitt 3.2 Content Based Filtering wird dies am Beispiel von Textdokumenten als Empfehlungselementen detailliert beschrieben. In 3.5
Ähnlichkeit als Selektionskriterium wird beschrieben, wie man „Ähnlichkeit“ berechnen kann.

3.1.3 Expertenempfehlungen und Referenz-Daten
Auch der Einsatz von Referenz-Daten ist ein Versuch, Objektivität in
die Beurteilung von Empfehlungssystemen zu bringen. Dabei werden auf Basis der Referenz-Daten meist von menschlichen Experten
Empfehlungen ausgesprochen. Diese Empfehlungen werden dann
mit denen der Empfehlungssysteme verglichen.
Besonders ausgeprägt ist dieses Vorgehen im Bereich von Textdokumenten als Empfehlungselemente. Mit den Cranfield Experimenten
[18] sollte eine Testumgebung zum objektiven Vergleich verschiedener Textklassifikationsverfahren geschaffen werden. Dazu wurde ein
fester Korpus (aus dem Themenfeld Luft- und Raumfahrt) von Experten manuell durchgängig klassifiziert.
Der Vergleich zu bereits vorgegebenen Referenz-Daten in Form von
Test-Korpora (TREC-Daten, TDT-Korpora etc.) ermöglicht zwar einen
objektiven Vergleich mit ebenfalls darauf getesteten anderen Verfahren, birgt aber die Gefahr, dass die Bewertung der Relevanz von Texten in den Test-Korpora nur für eben diese Test-Korpora gelten. Und
selbst auf den Test-Korpora kann das nicht als gegeben betrachtet
werden, da die menschlichen Bewertungen keine sichere Basis bieten.
So hat die Relevanzbewertung unter verschiedenen Experten meist
kein einstimmiges Ergebnis. Vergleiche verschiedener Verfahren auf
Basis von Test-Korpora sind demnach zwar ein Indikator, aber nicht
hinreichend für die allgemeine Qualität eines Verfahrens (siehe dazu
auch [19]).
Voorhees [20] weißt darauf hin, dass selbst die Test-Korpora nicht
mit ausreichender Güte klassifiziert werden können, da es bei angenommenen 30 Sekunden pro Dokument und rund 800.000 Dokumenten im TREC-Test-Korpus rund neun Monate dauern würde, eine
einzige Klasse (Thema) von Dokumenten zu bestimmen.

sUppLex

3 Methoden von Empfehlungssystemen
Und schließlich haben Turpin und Hersh in Feldstudien gezeigt, dass
die Bewertungen auf Basis der TREC Test-Korpora nicht mit einem
Vergleich mit menschlichen Testpersonen übereinstimmten [21].
Damit soll die Sinnhaftigkeit des Einsatzes von Referenzdaten nicht
in Frage gestellt werden. Die auf Basis von Referenzdaten ermittelten
Ergebnisse können aber nicht ohne Weiteres als allgemeingültig betrachtet werden.

3.1.4 Precision und Recall
Auch wenn oft keine Möglichkeit zur objektiven Beurteilung der
ausgesprochenen Empfehlungen besteht, so gibt es ein theoretisches
Maß für die qualitative Güte der Empfehlungen eines Empfehlungssystems. Dieses wird in der Regel mit den Werten Precision und Recall
angegeben.
Precision und
Recall

Werden aus einer Menge M von Empfehlungselementen n empfohlen, so
gibt die Precision an, welchen Prozentsatz die relevanten Empfehlungselemente in der Empfehlung ausmachen. Als Recall bezeichnet man
hingegen den Prozentsatz der relevanten Empfehlungselemente M, die
empfohlen wurden.

Daher ist Precision ein Maß für die Güte von Empfehlungen und
Recall eines für die Berücksichtigung potenziell relevanter Empfehlungselemente:
Bild 27: Die
"Precision" ist
das Verhältnis von
relevanten zu
insgesamt
empfohlenen
Texten und
"Recall" ist
das Verhältnis von
empfohlenen
relevanten
Texten zu
insgesamt
relevanten
Texten.

sUppLex

3.1 Die Qualität von Empfehlungen
Gibt es beispielsweise 10 relevante Empfehlungselemente und sind
unter 15 empfohlenen Elementen 5 relevante, so hat Precision einen
Wert von 33% und Recall einen Wert von 50%.
Eine konkrete Ermittlung von Precision und Recall ist allerdings
problematisch, da das Kriterium "relevant" wie oben ausgeführt in
der Regel subjektiv ist.

sUppLex

3 Methoden von Empfehlungssystemen

3.2 Content Based Filtering
Die Verfahren auf Basis des Content Based Filtering basieren im Wesentlichen auf den Eigenschaften der Empfehlungselemente. Insbesondere spielt das Verhalten anderer Benutzer keine Rolle. Im Rahmen der Eigenschaftsanalyse werden die Eigenschaften bestimmt, die
dann zur Selektion „nützlicher“ Elemente für eine Empfehlung verwendet werden. Die Nützlichkeit wird dabei oft mit der Ähnlichkeit
zu Elementen im aktuellen Kontext, der Situation oder im Profil des
Anwenders gleichgesetzt (siehe dazu auch oben 3.1.2 Ähnlichkeit als
Maßstab).

3.2.1 Eigenschaftsanalyse
Bevor jedoch beispielsweise eine Auswertung der Ähnlichkeit zur
Anwendung kommen kann, muss erst eine Eigenschaftsanalyse der
Empfehlungselemente erfolgen.
Definition
des Begriffes
Eigenschaftsanalyse (auch
Feature
Selection)

Die Eigenschaftsanalyse (auch als Feature Selection bezeichnet) bestimmt die
charakteristischen Eigenschaften von Empfehlungselementen. Und zwar in
einer Weise, die einen algorithmischen Vergleich zwischen Empfehlungselementen ermöglicht. Um die Laufzeitkomplexität zu reduzieren muss die
Eigenschaftsanalyse ein möglichst gutes Verhältnis zwischen der Menge
der Eigenschaften und der dadurch gegebenen diskriminierenden Wirkung
bezüglich der Empfehlungselemente erzielen.

3.2.2 Eigenschaftsanalyse am Beispiel von Textdokumenten
Im Folgenden sollen die wichtigsten Verfahren zur Eigenschaftsanalyse von Textdokumenten vorgestellt werden. Im Wesentlichen geht
es dabei um die Problemstellung, aus einem unstrukturierten Text
die wesentlichen Eigenschaften zu extrahieren.
Was bei einem Text in diesem Falle die Worte sind, sind bei Bildbeziehungsweise Musik-Empfehlungssystemen beispielsweise Farben und Formen beziehungsweise Rhythmus und Tempo.
3.2.2.1 Schlagworte und Schlüsselworte
Als charakteristische Attribute eines Textes gelten sicherlich dessen
Schlüsselworte. Dabei sind Schlüsselworte nicht mit Schlagworten zu
verwechseln.

sUppLex

3.2 Content Based Filtering
Schlüsselworte (oder Stichwörter) sind Worte, die einem Dokument zur
Beschreibung entnommen werden.

Schlüsselworte

Schlagworte hingegen sind Worte, die dem Dokument zur Inhaltsbeschreibung zugeordnet werden. Schlagworte müssen nicht unbedingt
im Dokument selbst enthalten sein.
Zur manuellen Definition von Schlagworten (manuelle Indexierung)
gibt es standardisierte Vorschriften [22], [23]. Allerdings sucht man in
diesen vergebens nach einem algorithmisch verwertbaren Verfahren
zur Bestimmung von Schlüsselworten oder Schlagworten.
So geben die Regeln für den Schlagwortkatalog [22] unter §4 (Inhaltsanalyse) vor:
Feststellen des Inhalts bzw. der inhaltlichen Schwerpunkte eines vorliegenden Dokuments, also der darin behandelten Gegenstände. Maßgebend für die
Wahl der Schlagwörter ist der Inhalt, nicht die jeweilige Titelfassung mit
den sich daraus ergebenden Stichwörtern.
Gewichtung und Auswahl der zu erschließenden inhaltlichen Aspekte unter
Berücksichtigung der Aufnahmeprinzipien für den Schlagwortkatalog (vgl.
§ 3) und der Grundprinzipien der Schlagwortkatalogisierung (vgl. § 6).
Ermittlung eines oder mehrerer Begriffe, die den wesentlichen Inhaltskomponenten eines Dokuments entsprechen.
Umsetzung der ausgewählten Begriffe in prägnante Bezeichnungen zum
Zweck der möglichen Ansetzung einzelner Schlagwörter (vgl. § 9).
Damit wird zwar die Zielsetzung, nicht aber der Prozess, definiert.
3.2.2.2 TF-IDF
Das bekannteste Verfahren zur Ermittlung der wichtigsten Worte
eines Textes ist das sogenannte TF-IDF-Verfahren [24], [25], [26]. Das
Akronym steht für Term Frequency – Inverse Document Frequency. Das
Verfahren verwendet statistische Informationen aus dem Korpus
(IDF) und dem betrachteten Text (TF), um die bedeutsamen Worte
des Textes zu ermitteln.

TF-IDF

sUppLex

3 Methoden von Empfehlungssystemen
Das dem Verfahren zugrunde liegende Konzept beruht auf zwei Annahmen zu Texten. Zum einen sind Worte für einen Text vermeintlich umso bedeutsamer, je häufiger sie in diesem vorkommen (Term
Frequency, TF). Zum anderen sind Worte, die in sehr vielen Texten
vorkommen, für den einzelnen Text und insbesondere dessen Charakterisierung weniger bedeutsam (Inverse Document Frequency, IDF).
Das Verfahren „belohnt“ also das häufige Auftreten eines Wortes im
konkreten Text und „bestraft“ ein häufiges Vorkommen über alle
Texte.
Bild 28: Das
TF-IDFVerfahren
bestimmt die
wichtigsten
Worte eines
Textes auf
Basis
statistischer
Informationen

Das TF-IDF-Verfahren ordnet jedem Wort Wn des betrachteten Textes
ein Gewicht G(Wn) zu. Die bedeutendsten Worte sind die mit den
höchsten Gewichten.

sUppLex

3.2 Content Based Filtering
Formal gilt für ein Wort Wn:

G Wn
mit TF

TF * IDF
NT W

und IDF= IDF

log

C
I C (W )

sowie

NT W = Anzahl der Instanzen ("Frequenz") von W in Text T

I C W = Anzahl der Texte im Korpus C={T1,…,Tn} mit mindestens einer Instanz von W

C = Anzahl der Texte im Korpus C
Das TF-IDF-Verfahren kommt in unterschiedlichen Derivaten zum
Einsatz, die alle unter diesem Merkmal zusammengefasst werden
sollen. Von über 50 untersuchten Empfehlungssystemen für Textdokumente als Empfehlungselemente setzen für die Eigenschaftsanalyse ein TF-IDF-Derivat ein.
3.2.2.3 Mutual Information
Beim Mutual Information-Ansatz wird die Beziehung zwischen zwei
Worten aus dem Grad des gemeinsamen Vorkommens (wechselseitige Information) abgeleitet [27].
Wenn zwei Worte wi und wj die Wahrscheinlichkeiten P(wi) und P(wj)
haben und PF(wi,wj) die Wahrscheinlichkeit für deren gemeinsames
Auftreten in einem Textfenster F ist, ist MI(wi,wj) wie folgt definiert:

Mutual
Information –
Ähnlichkeits
maß

sUppLex

3 Methoden von Empfehlungssystemen

MI wi , w j

p F wi , w j

für ( wi z w j )
°log 2
p wi * p w j
®
°1, sonst
¯

Es wird also die Wahrscheinlichkeit des gemeinsamen Auftretens mit
der des unabhängigen Auftretens verglichen. Bei einer signifikanten
Beziehung von wi und wj wird MI(wi,wj) deutlich größer als Null.
Umgekehrt haben bei MI(wi,wj)0 die Worte wenig gemein.
Zur Berechnung von PF(wi,wj) wird F konkret festgelegt. In [27] wird
es beispielsweise auf fünf Worte (Token) gesetzt. Sei außerdem W die
Menge aller Worte aller Dokumente im Korpus C und |W| die Anzahl der Worte in C sowie |wi| die Anzahl des Vorkommens (Instanzen) von wi in C.
Dann gilt:

p wi

wi
W

und mit F(wi,wj) als der Anzahl des gemeinsamen Vorkommens
(Kookkurrenz) von wi und wj in einem Textfenster von F Worten gilt:

p wi , w j

F ( wi , w j )

Dieses F für alle Worte zu bestimmen ist aufgrund der Permutationsmöglichkeiten offensichtlich ein aufwändiges Unterfangen. Daher
wird oft auf Werte zurückgegriffen, die auf Basis verhältnismäßig
großer Korpora ermittelt wurden [28], [29].

OWS

3.2.2.4 Beispiel einer Heuristik zur Wortselektion
Das Okapi Weighting Scheme (OWS) ist ein Beispiel für ein heuristisches Verfahren zur Extraktion von Eigenschaften. Im konkreten Fall
werden damit Worte eines Textes gewichtet, um dann die mit dem
höchsten Gewicht zu selektieren. Die OWS-Wortgewichtung gestaltet
sich wie folgt:

sUppLex

3.2 Content Based Filtering

¦w *
i

T Q

( k1 1) * tf ( k 3 1) * qtf
*
K tf
k 3 qtf

mit Q als Anfrage, welche die Worte T enthält und

§
dl ·
k1 * ¨¨ 1 b b *
¸
avgdl ¸¹
©

mit
k1 = 1,2
k3 = zwischen 0 und 1000 wählbar
b = 0,75
tf = Anzahl der Instanzen des Wortes im Dokument
qtf = Anzahl der Instanzen des Wortes in allen Texten
dl = Dokumentlänge
avgdl = Durchschnittliche Dokumentlänge
wi = Robertson-Sparck-Jones (RSJ)-Gewicht mit

§ ri 0,5 ·
¸¸
¨¨

0
,
5
R
r
i
©
¹
log
·
§
ni ri 0,5
¸¸
¨¨

N
n
R
r
0
,
5
i
i
©
¹

mit
N = Größe der Textbasis C
ni = Anzahl der Texte in C, die das Wort Ti enthalten
R = bekannte Dokumente, die zu einem Topic relevant sind
ri = Anzahl der relevanten Texte, die das Wort enthalten

sUppLex

3 Methoden von Empfehlungssystemen

Thesauri und
Wörterbücher
sollen das
Problem der
Synonyme
verkleinern.

3.2.2.5 Bedeutung, Thesauri und Wörterbücher
Rein statistische Verfahren wie TF-IDF interpretieren Worte nur als
Zeichenfolgen, die eventuell durch Stemming oder andere Verfahren
normiert wurden, um Übereinstimmungen zwischen inhaltlich ähnlichen Worten beim „Zählen“ der Worte zu berücksichtigen.
Nicht erfasst wird dabei aber die Bedeutung (siehe dazu 2.1.4 Linguistik) der Worte. Durch den Einsatz von Thesauri, Wörterbüchern oder
Synonym-Lexika versucht man dieses Defizit zu reduzieren.
Besonders bedeutsam ist es, Polysemie aufzulösen und Assoziationen
nachahmen zu können. Das folgende Schaubild verdeutlicht das
Problem der Polysemie und die Notwendigkeit für Assoziationen:

Bild 29:
Polysemie,
Homonyme
und Assoziationen durch
Synonyme

sUppLex

3.2 Content Based Filtering
Das Wort „Bank“ aus Text T1 wird durch die Worte „Rast“, „Vögel“ und „Natur“ disambiguiert. Damit wird die Beziehung zu Text
T3 größer und die Verbindung zu Text T2 geringer.
Durch das Synonym „Geldinstitut“ des Wortes „Bank“ kann der Text
T4 dem Text T5 zugeordnet werden.
Durch den Einsatz eines Thesaurus oder eines Wörterbuches ist ein
Algorithmus in der Lage, Funktionen des menschlichen Sprachvermögens wie Assoziationen und Disambiguierung zumindest in Ansätzen nachzuahmen.
In der Informatik verwendet man für die Disambiguierung von Worten meist das Akronym WSD für Word Sense Disambiguation.

WSD

Dass WSD auch Menschen Probleme bereitet, zeigen verschiedene
Untersuchungen. So hat Jorgeson beispielsweise gezeigt, dass Testpersonen in nur 68% aller Fälle bei der Bestimmung der Bedeutung
eines Wortes überein stimmen [30]. Berücksichtigt man, dass nicht
alle Worte mehrdeutig sind – laut Veronis Studie [31] werden 73%
aller Worte von Menschen als eindeutig eingestuft – ist der Grad der
Unbestimmtheit eines einzelnen Wortes sehr hoch.
Das Problem wurde bereits in den 50er Jahren im Rahmen der ersten
Schritte maschineller Übersetzungsverfahren erkannt [32]:
First, let us think of a way in which the problem of multiple meaning can, in
principle at least, be solved. If one examines the words in a book, one at a
time as through an opaque mask with a hole in it one word wide, then it is
obviously impossible to determine, one at a time, the meaning of the words.
"Fast" may mean "rapid"; or it may mean "motionless"; and there is no
way of telling which.
But, if one lengthens the slit in the opaque mask, until one can see not only
the central word in question but also say N words on either side, then, if N is
large enough one can unambiguously decide the meaning of the central word.
The formal truth of this statement becomes clear when one mentions that the
middle word of a whole article or a whole book is unambiguous if one has
read the whole article or book, providing of course that the article or book is
sufficiently well written to communicate at all.
Den Einsatz eines Thesaurus schlägt bereits Luhn im Rahmen seines
A Business Intelligence Systems im Jahr 1958 vor [5], [33].
Ein Thesaurus (siehe auch 2.1.3 Metadaten) setzt Worte in Beziehung
zueinander. Diese Relationen sind in der DIN-Norm 1463-1 beziehungsweise der ISO-Norm 2788 geregelt. Hier einige Beispiele:

Thesaurus

sUppLex

3 Methoden von Empfehlungssystemen
Synonyme:

„Benutze Synonym“ bzw. “Use synonym”

Hyponyme:

„Oberbegriff“ bzw. „Broader term“

Hyperonyme:

„Unterbegriff“ bzw. „Narrower term“

Assoziation:

„Verwandter Begriff“ bzw. „Related term“

Am Beispiel des Wortes „Ball“ soll der Einsatz eines Thesaurus veranschaulicht werden.
Für Ball liefere ein fiktiver Thesaurus folgende Beziehungen:
Ball ist Unterbegriff von Veranstaltung
Ball ist Unterbegriff von Sportgerät
Ball hat Synonym Tanzveranstaltung
Ball hat verwandten Begriff Fußball
Etc.
Auf Basis dieser Informationen kann ein Algorithmus nun beispielsweise im Rahmen der Eigenschaftsanalyse einen Menschen befragen,
welcher Wortsinn gemeint ist. Dieses überwachte Verfahren hat natürlich den Nachteil, dass es nicht automatisch ablaufen kann.
Alternativ kann ein Verfahren prüfen, ob Begriffe aus dem Umfeld
des Wortes laut Thesaurus ebenfalls im eigentlichen Text Vorkommen und daraus auf die Bedeutung des Wortes schließen. Das Potenzial dieses Ansatzes belegen verschiedene Studien.
So hat Yarowski [16] gezeigt, dass bereits ein weiteres Wort im direkten Umfeld des Wortes genügt, um den Wortsinn mit mindestens
90% Wahrscheinlichkeit zu bestimmen (zu disambiguieren). Das gilt
allerdings nur für Worte mit zwei verschiedenen Wortbedeutungen
und in einem engen Mikro-Kontext von wenigen Worten um das
betrachtete Wort.
Und Gale, Church und Yarowski [17] haben in einer anderen Untersuchung gezeigt, dass man die Qualität der Disambiguierung durch
eine Erweiterung des Mikro-Kontexts um das betrachtete Wort von 6
Worten auf 50 Worte um 4% verbessern kann.
Assoziation

Ein ähnliches Vorgehen erfolgt beim Einsatz von Wörterbüchern.
Hier macht man sich die Definition eines Wortes zunutze, um Mehrdeutigkeit aufzulösen oder Assoziationen herzustellen. Letztere wer-

sUppLex

3.2 Content Based Filtering
den dadurch imitiert, dass man auch Begriffe der Definition aus dem
Wörterbuch mit in die selektierten Eigenschaften aufnimmt.
Das Wort „Bildschirm“ wird beispielsweise durch ein fiktives Wörterbuch mit „Elektronisches Sichtgerät zur Darstellung von Computerinhalten oder Filmen. Auch als Monitor bezeichnet.“ definiert. Dadurch kann das Wort „Monitor“ als Eigenschaft verwendet werden,
auch wenn es im eigentlichen Text nicht vorkommt.

Wörterbuch

An diesem Beispiel wird aber auch die Gefahr des Einsatzes von
Wörterbüchern für die Nachahmung von Assoziation deutlich. Auch
das Wort „Film“ würde so in die Eigenschaften des Textes aufgenommen. Wenn der Text den Einsatz eines Bildschirms als Ausgabegerät für einen Computer beschreibt, wäre das eine negative Erweiterung der Texteigenschaften, da das zusätzliche Wort dann sehr wahrscheinlich nicht zur Bedeutung des Textes passt.

Polysemie
durch
Erweiterung
der
Eigenschaften

Einen guten Überblick zum Thema WSD geben Agiree und Edmonds
[34].

3.2.2.6 Kollokationen

Eine Kollokation (engl. Collocation) ist ein Wortpaar, dessen Vorkommen
im Korpus signifikant über dem Mittelwert des Vorkommens aller
Wortpaare liegt.

Kollokationen

Oder anders ausgedrückt, kommen die Worte eines solchen Wortpaares sooft miteinander vor, dass eine inhaltliche Verbindung abgeleitet werden kann.
Im Rahmen der Linguistik wird Kollokation oftmals nicht über die
reine Häufigkeit des gemeinsamen Vorkommens von Worten definiert, sondern als das erwartete gemeinsame Vorkommen von Worten aufgrund verschiedener Bedingungen.
Erstmals verwendet haben dürfte den Begriff Kollokation der englische Sprachwissenschaftler Firth:
Meaning by collocation is an abstraction at the syntagmatic level and is not
directly concerned with the conceptual or ideal approach to the meaning of
words. One of the meanings of night is its collocability with dark, and of
dark, of course, collocation with night. [35]

sUppLex

3 Methoden von Empfehlungssystemen
Benson unterscheidet grammatikalische und lexikalische Kollokationen, wobei erstere ein dominierendes Wort besitzen und letztere aus
gleichwertigen Worten bestehen:
By collocation we mean a group of words that occurs repeatedly, i. e. recurs,
in a language. These “recurrent phrases” can be divided into grammatical
collocations and lexical collocations. [36]
Hausmann geht ebenfalls von einer hierarchischen Beziehung zwischen den Worten einer Kollokation aus [37] und führt verschiedene
Typen von Kollokationen ein [38].
Einsatzmöglichkeiten
von Kollokationsinformationen im
Umfeld von
Empfehlungssystemen

Was kann man nun aber im Umfeld von Empfehlungssystemen mit
Kollokationsinformationen als Eigenschaften von Texten tun? Ähnlich wie beim Einsatz von Thesauri und Wörterbüchern kann man
Assoziationen zwischen Worten herstellen und Polysemie von Worten auflösen.
Die Übereinstimmung von Kollokationen und menschlichen Assoziationen wurde von Denhière et al. ausführlich untersucht [39].
Ein Beispiel für den Einsatz von Kollokationen zur Disambiguierung
von Worten liefern beispielsweise Hoste et al. [40].

3.2.2.7 Named Entity Recognition (NER)
Named Entity
Recognition
(NER)

Named Entity Recognition (kurz auch NER genannt)
steht für die
automatische Erkennung von Entitäten bestimmter Entitätstypen aus
unstrukturierten Textdokumenten. Entitätstypen können Beispielsweise
„Personen“, Firmen“ oder „Orte“ sein. Entitäten sind konkrete
Ausprägungen dieser Typen. Also beispielsweise „Bill Gates“,
„Microsoft“ oder „Redmond“.

Es sind zwei grundsätzliche Ansätze der NER zu unterscheiden.
Die regelbasierte Variante leitet auf Basis grammatikalischer, statistischer oder anderer Informationen regelbasiert ab, ob es sich bei einem Wort oder Wort-Tupel um ein „Named Entity“ handelt.
Der listenbasierte Ansatz arbeitet mit Verzeichnissen von Named
Entities und vergleicht Worte und Wort-Tupel damit, um Named
Entities zu erkennen. Auch Mischformen beider Ansätze sind anzutreffen.

sUppLex

3.2 Content Based Filtering
Die Named Entity Recognition versucht im Rahmen der Eigenschaftsanalyse auf Textbasis Worte spezieller Bedeutungskategorien (Entitätstypen) zu erkennen. Beispiele für solche Kategorien sind
- Eigennamen (Organisationsnamen, Personennamen etc.)
- Zeitliche Angaben (Jahreszahlen, Wochentage etc.)
- Ortsangaben (Städte, Gebäude etc.)
Am Beispiel der Eigennamen soll im Folgenden das prinzipielle Vorgehen beim NER veranschaulicht werden. Eine in diesem Umfeld oft
zitierte Arbeit ist die von Rau [41], die auf Heuristiken und Regeln
aufsetzt.
Fast immer machen sich NER-Verfahren die Charakteristik der betreffenden Bedeutungskategorie zu Nutze. So kann man Personennamen
beispielsweise daran erkennen, dass sie mit bestimmten, ihnen direkt
vorausgehenden Worten wie „Frau“, „Herr“, „Dr.“ etc. einhergehen.
Oder Firmen beispielsweise oft spezielle Folgeworte wie „GmbH“,
„AG“ etc. nach dem eigentlichen Firmennamen besitzen.
Ein oft angewendetes Konzept im Rahmen des NER ist das des
überwachten Lernens (Supervised Learning). Dabei kommen unter
anderen Techniken wie Hidden Markov Modelle (kurz HMM) [42], Entscheidungsbäume [43] und Support Vector Machines [44] (kurz SVM)
zum Einsatz.
Beim Supervised Learning wird in der Regel auf Basis einer Trainingsmenge vorgegeben, was Named Entities sind. Die Systeme leiten dann aus den Trainingsmengen ihre Entscheidungen ab, welche
Worte in größeren Korpora Named Entities darstellen.
Im Rahmen des NER sind die Behandlung von Anaphern und Akronymen relevante Aspekte. Letztere spielen insbesondere bei Organisationen eine wichtige Rolle.
Die Akronyme MIT, IBM, CIA etc. müssen mit den ausgeschriebenen
Bezeichnern der Organisationen assoziiert werden.

sUppLex

3 Methoden von Empfehlungssystemen
Bei Anaphern handelt es sich um Referenzen auf Named Entities aus
vorangegangenen Sätzen. So bezieht sich in den beiden folgenden
Beispielsätzen das erste Wort des Zweiten Satzes („Er“) auf die im
ersten Satz eingeführte Person:
„Der neue Minister Herbert Maier soll morgen vereidigt werden.
Er gehört der Partei bereits seit 22 Jahren an.“

NLP

3.2.2.8 Natural Language Processing (NLP)
Das Natural Language Processing (NLP, Verarbeitung Natürlicher
Sprache) beschäftigt sich mit Sprachanalyse und Sprachsynthese, mit
dem Ziel, eine dem Menschen zumindest ähnliche Sprachverarbeitung zu erzielen.
Im Umfeld von Empfehlungssystemen ist nur die Sprachanalyse von
Interesse. Im Laufe der Zeit haben sich im Bereich der Sprachanalyse
zwei wesentliche Forschungsrichtungen entwickelt. Die der theoretischen Linguistik wurde von Noam Chomsky begründet [45]. Die der
statistischen Informationstheorie (auch als Korpus-Linguistik bezeichnet)
umfasst unter anderem die im Vorfeld beschriebenen Methoden.
Sollen Eigenschaften eines unstrukturierten Textdokumentes ermittelt werden, kann der Ansatz der theoretischen Linguistik wertvolle
Informationen liefern.
Durch die grammatikalische und morphologische Analyse können im
Text enthaltene Informationen, die sich nicht aus den einzelnen Worten ableiten lassen, gewonnen werden.

POS-Tagging

Die grammatikalische Analyse (Part-Of-Speech-Tagging, POSTagging) eines Textes ordnet jedem Wort des Textes eine grammatikalische Kategorie zu. Die Analyse kann sich auf Wortklassen konzentrieren (Substantiv, Adjektiv etc.) oder die Syntax der Worte im
Satz bestimmen (Subjekt, Objekt etc.).
Damit lässt sich beispielsweise die Bedeutung „A wendet B auf C
an“ ableiten: „Der Mann öffnete die Flasche“ (A=“Mann“, B=“öffnet“,
C=“Flasche“).

Morphologische
Analyse

Die morphologische Analyse liefert Merkmale wie „Numerus“, „Tempus“ etc.
Damit lässt sich beispielsweise die Vergangenheitsform erkennen:
„Der Mann öffnete die Flasche“ („öffnete“ = Vergangenheitsform).

sUppLex

3.2 Content Based Filtering
3.2.2.9 Alternative Eigenschaften
Neben den Worten kommen noch weitere Eigenschaften eines Textes
für die Eigenschaftsanalyse in Frage. Eine prominente Alternative für
die Worte eines Textes als Grundeinheiten der Eigenschaften sind die
sogenannten N-Gramme.

N-Gramme

Ein N-Gramm ist eine Folge von „N“ Zeichen.

Statt 1-Gramm schreibt man bei konkretem „N“ aber Monogramm
(für N=1), Bigramm (für N=2), Trigramm (für N=3) etc.
Das Wort „Empfehlungssystem“ würde in Trigrammen wie folgt
aufgelöst:
Emp
mpf
pfe
feh
ehl
hlu
lun
ngs
gss
ssy
yst
ste
tem
Wie man sieht, haben die Buchstaben am Wortanfang und Ende ein
geringeres Vorkommen. Um das zu ändern, werden Wortanfang und
-ende mit Leerzeichen aufgefüllt.

sUppLex

3 Methoden von Empfehlungssystemen
Im angeführten Beispiel würden dadurch folgende Trigramme(mit
„[]“ als Leerzeichen) hinzukommen:
[][]E
[]Em
m[][]
em[]
Durch N-Gramme ist die Anzahl der zu speichernden „Worte“ (NGramme) definiert. Bei 37 alphanumerischen Zeichen („0-9“ und „az“ und Leerzeichen) ergeben sich potenziell 373 = 50.653 Trigramme.
Davon sind aber in konkreten Korpora nicht alle Trigramme vertreten.
Besonders bei Sprachen wie Japanisch mit kaum oder gar keiner
Worttrennung durch Leerzeichen bieten N-Gramme Vorteile. Aber
auch bei Sprachen mit getrennten Worten können N-Gramme sinnvoll eingesetzt werden. Insbesondere bei geringfügig falsch geschriebenen Worten ist der N-Gramm-Ansatz weniger anfällig als die
wortbasierte Eigenschaftsanalyse.
Der Einsatz von N-Grammen hat aber auch Nachteile. Je stärker die
Flexionen einer Sprache sind, desto weniger erfolgversprechend sind
N-Gramme [46].

3.2.3 Repräsentation der Eigenschaften
Die mit großem Abstand häufigste Form der Speicherung von Eigenschaften von Empfehlungselementen ist die in Form von Vektoren.
Historisch ist ein Vektor eine Größe, die neben einem Wert auch eine
Richtung benötigt, um vollständig definiert zu sein. Beispiele für
solche Größen sind die Geschwindigkeit oder die Beschleunigung.

sUppLex

3.2 Content Based Filtering
Mathematisch ist ein Vektor v ein Element des Vektorraumes V über dem
Körper K. Dabei ist V eine nicht-leere Menge, die zusammen mit der
Addition eine abelsche Gruppe bildet und folgenden Axiomen mit

D , E K und v, w V

Vektor

gerecht wird:

D E v Dv E v
D vw

Dv Dw

DE v D Ev
1v

Man kann sich einen Vektorraum mit mehr als drei Dimensionen nur
schwer vorstellen. In einer solchen Situation hilft es, wenn man die
Komponenten eines Vektors isoliert betrachtet. Eine Komponente des
Vektors v kann man sich als einen Vektor k vorstellen, der selbst eine
Komponente mit dem identischen Wert wie v besetzt hat und sonst
nur „0“-Werte besitzt:
v=(1,1,0)
Dann ist der die zweite Komponente von v repräsentierende Vektor:
k=(0,1,0)
Der Vektor v=(1,0,0) ist noch leicht vorzustellen. Die Vektoren
w=(1,1,0,0,1,0) und x=(1,0,0,0,1,0) hingegen kaum noch. Wenn man
aber nur die bezüglich des Wertes abweichende zweite Komponente
betrachtet, ist der „Unterschied“ der Vektoren w und x wieder einfacher zu verstehen.
Dieses Verständnis ist für die im Kontext von Empfehlungssystemen
in der Regel sehr große Anzahl an Dimensionen erforderlich.
Handelt es sich bei den Empfehlungselementen um Textdokumente,
so kann man diese durch Vektoren in einem Vektorraum darstellen,
dessen Dimensionen durch alle im Korpus vorkommenden Worte
aufgespannt wird.
Das heißt, dass jeder Text durch einen Vektor mit so vielen Komponenten repräsentiert wird, wie der Korpus Worte besitzt. Wenn für

sUppLex

3 Methoden von Empfehlungssystemen
die weitere Verarbeitung neben dem Vorkommen des Wortes auch
seine Häufigkeit oder das Gewicht (siehe dazu 3.2.2.2 TF-IDF) von
Bedeutung ist, tragen die Komponenten nicht nur den binären Wert
für „vorhanden“ (Wert „1“) oder „nicht vorhanden“ (Wert „0“), sondern die Anzahl des Vorkommens oder eben das Gewicht.
Besonders bei kurzen Texten bleibt aber offensichtlich der überwiegende Teil der Komponenten leer, da ein kurzer Text nur eine sehr
kleine Teilmenge der Worte eines Korpus enthält. Dass eine Darstellung in Vektorform dennoch sinnvoll ist, liegt an dem ausgefeilten
mathematischen Rüstzeug, das für Vektoren zur Verfügung steht.
Alternative
Darstellungsformen

Neben der Darstellung der Eigenschaften eines Textes in Form eines
Vektors gibt es in Form von Sätzen, der unsortierten Wortmenge
(auch als „Bag of Words“ bezeichnet) etc. weitere Optionen.

3.2.4 Ähnliche Elemente als Empfehlungen
Die Aufgabe eines Empfehlungssystems besteht wie bereits in der
grundlegenden Definition festgehalten darin, dem Benutzer „nützliche“ Elemente zu empfehlen.
Der „Nutzen“ für einen Anwender kann dabei stark durch den Kontext beeinflusst werden. Sucht ein Benutzer ein „Vegetarisches Restaurant“, weil er am Abend ein solches aufsuchen möchte, so ist die
Empfehlung des besten Elementes nicht sinnvoll, wenn sich dieses in
zu weiter Entfernung befindet. Auch eine automatisch angewendete
Berücksichtigung der Geoposition löst das Problem nicht immer.
Beispielsweise dann nicht, wenn der Benutzer Restaurants für den
geplanten Urlaub in einem fernen Land sucht.
In solchen Fällen beeinflusst der Kontext die rein auf Ähnlichkeit zur
Anforderung abgestützten Empfehlungen negativ.
Ein weiteres Beispiel ist die Empfehlung von Büchern. Auch hier
wird meist mit einem Ähnlichkeitsansatz gearbeitet um Empfehlungselemente zu selektieren.
Wenn der Benutzer zu einem gerade gewählten Buch auf Basis der
Ähnlichkeit sehr gute Empfehlungen von Büchern erhält, die er bereits besitzt, so wird die Nützlichkeit in Frage gestellt.
Diese Beispiele sollten zeigen, dass eine rein auf Ähnlichkeit abgestellte Auswahl von Empfehlungselementen oft nicht dem Anspruch
gerecht wird, Elemente mit dem größten Nutzen zu selektieren.
Dass Ähnlichkeit im Umfeld von Empfehlungssystemen dennoch
eine wichtige Rolle spielt, steht außer Frage. Wie Ähnlichkeit berech-

sUppLex

3.2 Content Based Filtering
net werden kann, beschreibt „3.5 Ähnlichkeit als Selektionskriterium“.

3.2.5 Alternative Verfahren
Statt die Eigenschaften von Empfehlungselementen zu ermitteln und
dann zu verwenden, gibt es alternative Verfahren, die die Eigenschaften verwenden, um darüber auf Empfehlungselemente zuzugreifen.
Ein solcher Ansatz, der die Beziehung von den Eigenschaften zu den
Empfehlungselementen betrachtet und nicht umgekehrt, ist beispielsweise das Latent Semantic Indexing.
3.2.5.1 Latent Semantic Indexing (LSA)
Beim Latent Semantic Indexing (LSA) [47] wird zunächst eine Matrix
von Eigenschaften (Worten) und Empfehlungselementen (Textdokumenten) gebildet. Diese Matrix repräsentiert den Korpus und ist
entsprechend groß. Die Anzahl der Empfehlungsobjekte bestimmt
die Spaltenzahl und die Anzahl der Worte die Zeilenzahl. Die resultierende Matrix ist ebenso groß wie spärlich besetzt.
Folgendes Beispiel zeigt einen sehr kleinen Korpus mit lediglich fünf
Empfehlungselementen (Textdokumenten):
Text1

Die Sonne ist der Stern im Planetensystem

Text2

Unser Planetensystem hat unsere Sonne als Stern

Text3

Die Planeten kreisen um die Sonne

Text4

Planeten kreisen um Sterne

Text5

Er lief in Kreisen und sah Sterne

Text6

Der Planet lief in Kreisen um die Sonne

LSA

Ein Beispiel

sUppLex

3 Methoden von Empfehlungssystemen
Sowie die zugehörige Matrix:
Eine WortDokumentMatrix als
Basis des LSI
Verfahrens

Text 1
als

Text 2

Text 3

Text 4

die

1
2

hat

1
1

in
ist

kreisen

lief
planet

planeten
planetensystem

Text 6

der

Text 5

1
1

sah

sonne

stern

sterne

1
1

und

1
1

unser

unsere

Durch Single Value Decomposition (SVD) wird die Größe der Matrix
drastisch reduziert. Dabei werden veranschaulicht ähnliche Zeilen
zusammengefasst. In der obigen Tabelle beispielsweise die Zeilen für
„Planet“ und „Stern“. Es werden also Eigenschaften (Worte), die in
vielen Empfehlungselementen (Textdokumenten) gemeinsam vorkommen, zu einer „virtuellen“ Eigenschaft zusammengefasst. Davon
verspricht man sich im Umfeld von Textdokumenten beispielsweise
die Zusammenfassung von semantisch sehr ähnlichen Worten wie

sUppLex

3.2 Content Based Filtering
Synonymen. Oder anders ausgedrückt werden Empfehlungsobjekte
(die Spalten der Matrix) sehr ähnlich, wenn sie viele Eigenschaften
haben, die sich ähnlich sind (in vielen Empfehlungsobjekten gleichzeitig vorkommen). Die Verwandtschaft zu Kollokationen (siehe
3.2.2.6 Kollokationen) ist offensichtlich, wird hier aber direkt mit den
Vorkommen der Worte in den Textdokumenten verbunden.

sUppLex

3 Methoden von Empfehlungssystemen

3.3 Collaborative Filtering
Das Verfahren des Collaborative Filtering fußt im Wesentlichen auf
dem Verhalten von Benutzern.
Das Collaborative Filtering nutzt anstelle der Verwandtschaft von
Empfehlungselementen meist die Ähnlichkeit von Benutzerprofilen.
Die Profile repräsentieren das Benutzerverhalten in Form der Nutzung von Empfehlungselementen (Texte, Produkte, Bilder etc.). Daraus resultiert eine Benutzer-Empfehlungselement-Matrix:
Bild 30: Die
CF-Matrix der
BenutzerEmpfehlungselementBeziehungen.

Mit U1, …, Un als Benutzer und I1,…,Im als Empfehlungselemente.
Eine Zelle [Ux,Iy] der Matrix stellt die implizite oder explizite Bewertung des Empfehlungselementes Iy durch den Benutzer Ux dar. Die
Bewertung kann boolesch („angesehen“ / „nicht angesehen“ beziehungsweise „gut“ / „schlecht“) oder auf einer diskreten Skala erfolgen.
Beispiele für Collaborative Filtering-Verfahren sind Ringo [48], Siteseer [49] und GroupLens [50]. Empfehlungen für einen Benutzer
werden in der Regel aus dem Verhalten anderer Benutzer mit ähnlichem Profil gewonnen. Das zugrunde liegende Konzept des Collaborative Filtering (siehe auch [51]) soll nun kurz vorgestellt werden.

sUppLex

3.3 Collaborative Filtering

3.3.1 Der benutzerbezogene Algorithmus
Um für einen Benutzer "vorherzusagen", welche Empfehlungselemente ihn interessieren könnten und ihm diese anzubieten, arbeiten
benutzerbezogene Collaborative Filtering-Verfahren im Wesentlichen
wie folgt:
Auf der Basis von n Benutzern und m Empfehlungselementen wird
die Matrix R=(rij) mit i=1..n und j=1..m erzeugt. Der Wert rij repräsentiert die "Bewertung" des Elementes j durch den Benutzer i. Diese
Bewertung kann explizit durch den Benutzer erfolgen (beispielsweise
"sehr gut, "gut" etc.) oder aber implizit aus seinem Verhalten (beispielsweise dem Kauf eines Produktes oder dem Lesen eines Textes)
abgeleitet werden.
Die Aufgabe besteht darin, für ein Empfehlungselement I und den
Benutzer U (der das Empfehlungselement noch nicht gesehen hat) zu
bewerten, wie hoch die Relevanz R für ihn ist: R(I,U).
Dazu wird beim benutzerbezogenen Collaborative Filtering für alle
Empfehlungselemente auf Basis des Verhaltens von Benutzern, die
dem Benutzer Ux am ähnlichsten sind, berechnet wie groß die Relevanz (das erwartete Interesse) R(Ux,Iy) dieser Empfehlungselemente
für Ux sein wird. Die Ähnlichkeit wird auf Basis von Distanz- oder
Ähnlichkeitsmaßen ermittelt (siehe 3.5 ). Im zweiten Schritt werden
dann die Empfehlungselemente mit dem höchsten Relevanz-Wert zur
Auswahl gestellt.
Bild 31:
Benutzerbezogenes
Collaborative
FilteringKonzept

Aufgrund der Bewertungen des Benutzers (1=U3) werden ähnliche
Benutzer (2=U1,U2) gesucht. Die von den meisten ähnlichen Benut-

sUppLex

3 Methoden von Empfehlungssystemen
zern als "gut" bewerteten Empfehlungselemente (3) werden dem
Benutzer empfohlen (4).

3.3.2 Der elementbasierte Algorithmus
Um für einen Benutzer "vorherzusagen" ob ein Empfehlungselement
ihn interessieren könnte und ihm dieses anzubieten, arbeiten elementbasierte Collaborative Filtering-Verfahren im Wesentlichen wie
folgt:
Auf der Basis von n Benutzern und m Empfehlungselementen wird
wiederum die Matrix R=(rij) mit i=1..n und j=1..m erzeugt.
Auch hier besteht die Aufgabe darin, für ein Empfehlungselement Iy
und den Benutzer Ux (der das Objekt noch nicht gesehen hat) zu bewerten, wie hoch die Relevanz R für ihn ist: R(Iy,Ux).
Dazu werden zunächst auf Basis der vom Benutzer bereits bewerteten Objekte I1,…,Iu die Ähnlichkeiten S zu Iy berechnet. Die Ähnlichkeit wird dadurch bestimmt, dass aus allen Paaren von Empfehlungselementen (Iy,I1), …, (Iy,Iu) [kurz (Iy,I1..u)] aufgrund der Bewertungen von anderen Benutzern, die jeweils beide Empfehlungselemente bewertet haben, ein Vektor gebildet wird, der dann für die
Ähnlichkeitsbestimmung verwendet wird. Haben alle Benutzer Iy
und ein anderes Empfehlungselement jeweils identisch bewertet, ist
die Ähnlichkeit am größten.
Bild 32:
Elementbasiertes
Collaborative
FilteringKonzept

Beim elementbasierten Collaborative Filtering-Konzept werden aufgrund der gut bewerteten Empfehlungselemente des Benutzers
(1=U3) in der Bewertungsmatrix R alle Paare von Empfehlungselementen, in denen eines dieser Empfehlungselemente vorkommt, se-

sUppLex

3.3 Collaborative Filtering
lektiert (2). Die am besten bewerteten anderen Empfehlungselemente
in diesen Paaren (3=I2) werden dem Benutzer dann empfohlen (4).
Die Relevanz R(Iy,Ux) wird dann beispielsweise in Form des gewichteten Durchschnitts der Bewertungen des Benutzers für die Iy ähnlichsten Empfehlungselemente ermittelt. Je ähnlicher ein Empfehlungselement Ij dem Empfehlungselement Iy ist (je größer also S(Iy,Ij)) ,
desto stärker fließt die Bewertung durch den Benutzer für dieses
Objekt ein:

R I y ,U x

j 1... n

S I y , I j * R I j ,U x

j 1... n

S Iy,I j

Dabei sind Ij=1..u die durch den Benutzer bewerteten Empfehlungselemente.

3.3.3 Modell- und speicherbasiertes Verfahren
Bei speicherbasierten Verfahren wird die komplette Basis der Benutzerprofile mit deren Verhalten zur Berechnung der Empfehlungen
verwendet. Es werden in der Regel statistische Verfahren zur Bestimmung der Nachbarn verwendet [52].
Beim modellbasierten Verfahren tritt anstelle der vollständigen Collaborative Filtering Matrix ein vereinfachtes Modell wie zum Beispiel
eine "Benutzer-Cluster" Matrix.
Die bekanntesten modellbasierten Ansätze sind Bayes´sche Netze
und Clusterbildung, aber auch Regelsysteme und neuronale Netze
gehören dazu.
Bei der Clusterbildung werden Benutzergruppen mit ähnlichen Präferenzen gebildet. Auf Basis der Cluster werden dann Empfehlungen
für den aktiven Benutzer erstellt. Dabei werden die Präferenzwerte
der Benutzer aus dem Cluster des aktiven Benutzers in einem Durchschnittswert verdichtet. Dieser Durchschnittswert kann potenziell
auch übergreifend auf Basis von Präferenzwerten der Benutzer anderer Cluster, in denen sich der aktive Benutzer ebenfalls befindet, ermittelt werden. Wobei die Präferenzwerte in diesem Falle mit dem
Grad der Cluster-Zugehörigkeit gewichtet werden.
Der auf den ersten Blick überlegene modellbasierte Ansatz hat allerdings den Nachteil, dass neue Daten aufwändiger hinzugefügt wer-

sUppLex

3 Methoden von Empfehlungssystemen
den müssen und dass durch die Vereinfachung auch Informationen
für die Entscheidungsfindung verloren gehen können.

3.3.4 Nachteile des Collaborative Filtering
Die wesentlichen Nachteile des Collaborative Filtering sind das Kaltstart-Problem, das Problem der Spärlichkeit (sparsity) und der Lemming-Effekt. Diese sollen im Folgenden kurz beschrieben werden.

KaltstartProblem

Spärlichkeit

LemmingEffekt

3.3.4.1 Kaltstart-Problem
Da Empfehlungen offensichtlich nur auf dem Verhalten anderer Benutzer ausgesprochen werden können, muss ein Collaborative Filtering-Verfahren zunächst eine "kritische Menge" an Benutzeraktionen
erfasst haben, bevor es Empfehlungen aussprechen kann. Das gilt
nicht nur für die Collaborative Filtering-Matrix an sich (und damit
für neue Empfehlungselemente), sondern insbesondere auch für jeden neuen Benutzer. Ohne dass dieser ausreichend viele eigene Aktionen (implizite oder explizite Bewertung von Empfehlungselementen) durchgeführt hat, kann ein Collaborative Filtering-System ihm
keine Empfehlungen geben. Dieser Umstand wird als KaltstartProblem bezeichnet.
3.3.4.2 Spärlichkeit (sparsity)
Aufgrund der in Collaborative Filtering-Umgebungen häufig sehr
großen Anzahl von Empfehlungselementen sind oftmals 98% bis 99%
der Empfehlungselemente nicht mit einer Bewertung durch den Benutzer versehen [53]. Betrifft dies im Mittel über alle Benutzer mehr
als 99,5% der Objekte, so fällt die Empfehlungsgüte eines Collaborative Filtering-Verfahrens drastisch ab [54]. Anschaulich sinkt mit
zunehmender Spärlichkeit der Bewertungen die Wahrscheinlichkeit,
Benutzer zu finden, die gleiche Empfehlungselemente gleich oder
ähnlich bewertet haben.
3.3.4.3 Lemming-Effekt
Eines der wohl bekanntesten Portale mit angewendetem Collaborative Filtering-Verfahren dürfte der Internet-Buchshop von "Amazon"
sein. Hier funktioniert das Collaborative Filtering offenbar – vorausgesetzt man hat bereits ein paar Bücher angesehen oder gekauft und
daher das Kaltstart-Problem beseitigt – recht gut. Die Spärlichkeit
wird durch die enorme Anzahl von Benutzern zumindest außerhalb
der thematischen Nischen beseitigt.
Wie bei allen Anwendungsfällen, die eine Bewertung eines Empfehlungselementes mit einem Kaufakt verbinden, besteht auch hier eine

sUppLex

3.3 Collaborative Filtering
natürliche Hürde, die empfohlenen Objekte anzunehmen (zu erwerben) und damit selbst positiv zu bewerten.
Allerdings kann man bei sehr populären Produkten, wie beispielsweise im Jahr 2006 bei den Büchern von Dan Brown, selbst hier den
sogenannten Lemming-Effekt beobachten. Die Bücher von Dan Brown
wurden zu sehr vielen anderen Büchern empfohlen, obwohl thematisch kaum Zusammenhänge erkennbar waren. Der Grund waren
extrem viele Benutzer, die Dan Browns Bücher gekauft haben.
Entfällt die "Kaufhürde" auch noch, rufen Benutzer die Ihnen empfohlenen Empfehlungselemente ungleich öfter auf, so dass diese –
besonders bei impliziter Bewertung durch den Aufruf – wiederum
anderen Benutzern empfohlen werden und so fort. Dadurch werden
einmal empfohlene Objekte immer weiter gestärkt. Neue Objekte
haben kaum eine Chance in die Liste der empfohlenen Empfehlungselemente aufzusteigen. Diesen Vorgang bezeichnet man als LemmingEffekt.

sUppLex

3 Methoden von Empfehlungssystemen

3.4 Hybride Verfahren
Hybride Verfahren, die Content Based-Filterung und Collaborative Filtering verbinden, versuchen die Vorteile beider Ansätze zu kombinieren. Die Varianz der Mischformen ist dabei sehr groß, was später bei
der Vorstellung verschiedener Empfehlungssysteme deutlich wird.

3.5 Ähnlichkeit als Selektionskriterium
Um die Eigenschaften zweier Empfehlungselemente zu vergleichen,
wird wie bereits erwähnt meist deren Ähnlichkeit als Maßstab herangezogen.
Aber auch beim Collaborative Filtering kommt Ähnlichkeit als Selektionskriterium zum Einsatz.
Distanzmaße sind dabei der klassische Weg, die Dimension der
„Ähnlichkeit“ mathematisch berechenbar zu machen. Zunächst werden dazu die Eigenschaften von Empfehlungselementen oder Benutzerprofilen in Vektoren transformiert und dann über ein Distanzmaß
verglichen. Bei den Vektoren handelt es sich entweder um binäre
Vektoren, bei denen jede Komponente das Vorhandensein oder
Nichtvorhandensein einer Eigenschaft angibt. Oder es handelt sich
um Vektoren mit reellen Zahlen als Komponenten. Diese können in
den Komponenten Ausprägungen von Eigenschaften wiedergeben.
Diese Ausprägungen können Alternativen wie beispielsweise in einem Benutzerprofil die Bewertung von Empfehlungselementen auf
einer Skale von eins bis sechs sein. Oder „Gewichte“ wie beispielsweise die Häufigkeit eines Wortes in einem Text.
Am Beispiel von Texten als Empfehlungselemente mit den Worten
als Eigenschaft soll dies illustriert werden.
Seien die Texte T1, T2 und T3 wie folgt gegeben:
T1 = „Gehirne der Serie 9000 sind die besten Computer, die jemals
gebaut worden sind. Kein Computer der Serie 9000 hat jemals einen Fehler gemacht oder eine unklare Information gegeben.“
T2 = „Gehirne aus der 9000 Serie sind Computer, die keine Fehler
machen und die auch keine unklare Information geben.“
T3 = „Die 9000 Serie sind Computer, die keine Fehler machen.
Dennoch kann man mit diesen Geräten keinen Rasen mähen und
auch keinen Hausputz machen.“

sUppLex

3.5 Ähnlichkeit als Selektionskriterium
Weiter sei angenommen, dass die folgenden Worte Stoppworte sind,
die keine Berücksichtigung beim Ähnlichkeitsvergleich spielen sollen:
-

auch

aus

dennoch

der

die

diesen

eine

einen

hat

kann

kein

keine

keinen

machen

man

mit

oder

sind

und

worden

Damit bleiben bei den drei Beispieltexten folgende relevanten Worte
übrig:
T1 = „Gehirne Serie 9000 besten Computer jemals gebaut Computer
Serie 9000 jemals Fehler gemacht unklare Information gegeben“
T2 = „Gehirne 9000 Serie Computer Fehler unklare Information geben.“
T3 = „9000 Serie Computer Fehler Geräten Rasen mähen Hausputz“

sUppLex

3 Methoden von Empfehlungssystemen
Seien die Komponenten der Wortvektoren alphanumerisch sortiert,
so ergeben sich die folgenden Komponenten (benannt nach dem jeweiligen Wort) für den Vektoraufbau, wenn nur die in den drei Beispieltexten vorkommenden Worte berücksichtigt werden:
-

9000
Besten
Computer
Fehler
gebaut
geben
gegeben
Gehirne
gemacht
Geräten
Hausputz
Information
jemals
mähen
Rasen
Serie
unklare

Verwendet man binäre Vektoren, bei denen nur das Vorkommen
beziehungsweise das Fehlen eines Wortes angezeigt werden, erhält
man für die drei Beispieltexte folgende Vektoren:
V1=(1,1,1,1,1,0,1,1,1,0,0,1,1,0,0,1,1)
V2=(1,0,1,1,0,1,1,1,0,0,0,1,0,0,0,1,1)
V3=(1,0,1,1,0,0,0,0,0,1,1,0,0,1,1,1,0)
Bei Vektoren mit reellen Komponenten erhält man folgende Vektoren:
V1=(2,1,2,1,1,0,1,1,1,0,0,1,2,0,0,2,1)
V2=(1,0,1,1,0,1,1,1,0,0,0,1,0,0,0,1,1)
V3=(1,0,1,1,0,0,0,0,0,1,1,0,0,1,1,1,0)

sUppLex

3.5 Ähnlichkeit als Selektionskriterium

Diese binären Vektoren der Beispieltexte werden im Folgenden zur
Veranschaulichung der unterschiedlichen Ähnlichkeits- und Distanzmaße verwendet.

3.5.1 Distanz und Ähnlichkeit
Es gibt einen formalen Unterschied zwischen einem Distanzmaß und
einem Ähnlichkeitsmaß.

Ein Distanzmaß auf einer Menge C von Empfehlungselementen ist eine
reelle Funktion dist(T1,T2) mit dist(T1,T2)=0 falls T1=T2.

Ein Ähnlichkeitsmaß ist eine reelle Funktion sim(T1,T2) mit sim(T1,T2)=1 falls
T1=T2. Neben der Reflexivität gilt auch die starke Reflexivität: dist(T1,T2)=0
=> T1=T2 und sim(T1,T2)=1 => T1=T2. Im Rahmen von Empfehlungssystemen
wird keine metrische Distanz gefordert. Damit sind zusätzliche
Bedingungen metrischer Distanzen (Symmetrie etc.) nicht zwingend
gegeben.

Distanz

Ähnlichkeit

Im Folgenden werden die wichtigsten Distanzmaße am Beispiel der
Eigenschaften von Textdokumenten in Form von Wortvektoren vorgestellt.

3.5.2 Cosinus
Das Cosinus-Ähnlichkeitsmaß (Cosine Similarity) bestimmt die Ähnlichkeit Sim zweier n-dimensionaler Vektoren v=(v1,…,vn) und
w=(w1,…,Wn) wie folgt durch deren Cosinus:

SimcosT(v,w) =

CosinusÄhnlichkeits
maß

vxw
v*w

v * wi

i 1 i

v *

i 1 i

i 1

sUppLex

3 Methoden von Empfehlungssystemen
wobei v•w das Skalarprodukt und |v|*|w| das Produkt der Beträge
(Längen) der Vektoren ist. Je ähnlicher Vektoren sind, desto geringer
ist der Winkel zwischen Ihnen und desto größer der Wert der Ähnlichkeitsfunktion.
Für die Vektoren der Beispieltexte ergeben sich folgende gerundeten
Werte:
SimcosT(V1,V2) = 0,77
SimcosT(V1,V3) = 0,41
SimcosT(V2,V3 ) = 0,47
Interpretiert man die Vektoren v und w als Mengen von Worten, so
gilt:
SimcosT(v,w) =

vw
(v * w)

3.5.3 Pearson Korrelationskoeffizient
Pearson
Korrelationskoeffizient

Der Pearson Korrelationskoeffizient (PC; Pearson Correlation [55]) ist
eine Ähnlichkeitsfunktion Sim. Für zwei Vektoren v und w mit
v=(v1,v2,…,vn) und w=(w1,w2,…,wm) gilt:

Simpc(v,w) =

vi v * wi w

i 1...n

¦v

i 1... n

v *

¦w

i 1... n

Dabei steht v beziehungsweise w für den Durchschnitt der Komponenten von v beziehungsweise w.
Für die Vektoren der Beispieltexte ergeben sich folgende gerundeten
Werte:
Simpc(V1,V2) = 0,43
Simpc(V1,V3) = - 0,42
Simpc(V2,V3 ) = - 0,1

sUppLex

3.5 Ähnlichkeit als Selektionskriterium

3.5.4 Overlap-Koeffizient
Der Overlap-Koeffizient ist ein Ähnlichkeitsmaß Sim. Für zwei Vektoren v und w mit v=(v1,v2,…,vn) und w=(w1,w2,…,wm) gilt:

OverlapKoeffizient –
Ähnlichkeitsmaß

¦ min(v , w )
Sim (v,w) =
min(¦ x , ¦ y )
n

i 1

Für die Vektoren der Beispieltexte ergeben sich folgende gerundeten
Werte:
Simok(V1,V2) = 0,89
Simok(V1,V3) = 0,5
Simok(V2,V3 )= 0,5
Interpretiert man die Vektoren v und w als Mengen von Worten, so
gilt:

Simok(v,w) =

vw
min( v , w )

Anschaulich wird also die Größe der gemeinsamen Wortmenge beider Vektoren durch die kleinere von beiden normiert, so dass große
Wortmengen nur normalen Einfluss haben. Man kann den Overlap
Koeffizienten als Maß für die wechselseitige Inklusion interpretieren.

3.5.5 Dice-Koeffizient
Beim Dice-Koeffizienten wird die Beziehung zwischen zwei Wortvektoren aus dem Grad des gemeinsamen Vorkommens der einzelnen
Worte abgeleitet:

DiceKoeffizient –
Ähnlichkeitsmaß

sUppLex

3 Methoden von Empfehlungssystemen

2 * ¦i 1 ( xi * y i )
n

Simdk(v,w) =

n
i 1

x i ¦i 1 y i
n

Der Dice-Koeffizient ist ein Ähnlichkeitsmaß Sim. Für zwei Vektoren
v und w mit v=(v1,v2,…,vn) und w=(w1,w2,…,wm) gilt:

2 * ¦i 1 ( g ( xi ) * g ( y i ))
n

Sim dk (v,w) =

min(¦i 1 g ( xi ), ¦i 1 g ( y i ))
n

Für die Vektoren der Beispieltexte ergeben sich folgende gerundeten
Werte:
Simdk(V1,V2) = 0,76
Simdk(V1,V3) = 0,40
Simdk(V2,V3 ) = 0,47
Interpretiert man die Vektoren v und w als Mengen von Worten, so
gilt:
Simdk(v,w) =

2* v w
vw

3.5.6 Jaccard-Koeffizient
JaccardKoeffizient –
Ähnlichkeitsmaß

Der Jaccard-Koeffizient ist ein Ähnlichkeitsmaß Sim. Für zwei Vektoren
v und w mit v=(v1,v2,…,vn) und w=(w1,w2,…,wm) gilt:

Sim jk

¦
(v,w) =
¦ x¦

i 1
n

i 1

( xi * y i )
y i ¦i 1 ( xi * y i )
n

sUppLex

3.5 Ähnlichkeit als Selektionskriterium
Für die Vektoren der Beispieltexte ergeben sich folgende gerundete
Werte:
Simjk(V1,V2) = 0,62
Simjk(V1,V3) = 0,25
Simjk(V2,V3 ) = 0,31
Interpretiert man die Vektoren v und w als Mengen von Worten, so
gilt:
Simjk(v,w) =

vw
vw

3.5.7 Euklidscher Abstand
Das gebräuchlichste Distanzmaß dürfte der Euklidische Abstand sein.
Für zwei Vektoren v und w mit v=(v1,v2,…,vn) und w=(w1,w2,…,wm)
gilt:

dist ea (v,w) =

i 1

(vi wi ) 2

Für die Vektoren der Beispieltexte ergeben sich folgende gerundeten
Werte:
distea(V1,V2) = 2,23
distea (V1,V3) = 3,46
distea (V2,V3 ) = 3,00

3.5.8 Mutual Information
Für zwei Wortvektoren v und w kann die Ähnlichkeit der den Vektoren zugrunde liegenden Texte wie folgt mit der Mutual Information
(siehe dazu 3.2.2.3 Mutual Information) über alle Permutationen der
Worte aus v und w berechnet werden:

sUppLex

3 Methoden von Empfehlungssystemen
Sim mi (v,w) =

¦ ¦
n

i 1

j 1

MI vi , w j

Je größer der resultierende Wert, desto ähnlicher sind sich vermeintlich die beiden Texte.

3.5.9 Nearest Neighbours
Nearest
Neighbours

Beim Nearest Neighbours-Verfahren handelt es sich um ein Verfahren
zur Ermittlung der k nächsten Nachbarn eines Elementes. Meist beruht es auf der Optimierung eines anderen Distanzmaßes. Statt in
O(n) Laufzeit aus n Elementen die k nächsten Nachbarn zu selektieren, wird beispielsweise durch Klassifikation ein optimiertes iteratives Verfahren angewendet. Formal sind die k nächsten Nachbarn
eines Elementes a wie folgt definiert.
Sei X eine endliche Teilmenge eines metrischen Raumes mit der Distanzfunktion d(x,y). Die Punkte biX mit i=1,…,k sind die k nächsten
Nachbarn von a, falls gilt:
0 <= d(a,bi) <= d(a,bi+1) für i=1,…,k
und

d(a,bk) <= d(a,c)

für alle cX\{b1,...,bk).
Bei Empfehlungssystemen sind die k nächsten Nachbarn die Empfehlungselemente oder Benutzer mit dem geringsten Abstand zu einem
konkreten Empfehlungselement beziehungsweise Benutzer.

sUppLex

3.6 Klassifikationsverfahren

3.6 Klassifikationsverfahren
Klassifikationsverfahren vergleichen Empfehlungselemente nicht,
sondern verfolgen den Ansatz, diese zu gruppieren. Im Folgenden
werden Klassifikationsverfahren am Beispiel der Eigenschaften von
Textdokumenten vorgestellt.

3.6.1 Minimum Description Length (MDL)
Beim MDL-Verfahren (Minimum Description Length [56]) wird ein
Dokument D der Klasse K1 eher zugeordnet als der Klasse K2, wenn
die binärcodierte Darstellung der Klasse K1 erweitert um D weniger
Speicherplatz benötigt als die binärcodierte Darstellung der Klasse K2
erweitert um D.
MDL basiert auf der Annahme, dass das kompakteste Modell auch
das optimale ist. Es folgt somit dem Prinzip Pluralitas non est ponenda
sine necessitate [57] von "Ockhams Razor" (William of Ockham, 12851349), das besagt, dass große Mengen („Vielheiten“) nicht ohne
Grund angenommen werden sollten.
Formal kann der MDL-Ansatz über das Bayes´sche Theorem hergeleitet werden. Gesucht ist die Klasse Ki, welche die Wahrscheinlichkeit
p(Ki|D) für Ki bei gegebenem D maximiert. Mit dem Bayes´schen
Theorem kann das in

max
Ki

p D Ki * p Ki
pD

umgeformt werden.

sUppLex

3 Methoden von Empfehlungssystemen
Da P(D) unabhängig von Ki ist, ist es für die Maximierung des Terms
über Ki irrelevant. Gesucht ist also

max p D K i * p K i
Ki

Das ist wegen p(x)<=1 äquivalent zu

min log p D K i * p K i
Ki

min log p D K i log p K i
Ki

Nun ist aber -log2(p(X)) nach Shannon [58] gleich der Bitzahl eines
optimalen Binärcodes für X. Daher sucht man bei MDL die wahrscheinlichste Klasse Ki bei gegebenem Dokument D, indem man die
Klasse Ki mit der kürzesten Bitcodierung sucht. Die Bitcodierung
umfasst dabei zum einen die Klasse selbst, zum anderen die Klasse
zuzüglich des Dokumentes.
Um MDL konkret anwenden zu können, muss die Bitcodierung konkretisiert werden. Exemplarisch sei hier die Verfahrensweise von
NewsWeeder (siehe 4.2.3 Newsweeder) vorgestellt:
x

D = das zu klassifizierende Dokument

WD = binärer Wortvektor des Dokumentes D

LD = die Anzahl der Nicht-Null-Komponenten in WD
= Anzahl unterschiedlicher Worte in D

T = die Trainingsdaten mit denen die Klassen aufgebaut wurden; dies ist ein Wortvektor der für jedes
Wort die Anzahl der Dokumente speichert, die dieses
Wort enthalten

Ki = die Klasse besteht aus "gelernten" Dokumenten
der Trainingsdaten; dies ist analog zu T ein Wortvektor – allerdings beschränkt auf die Dokumente aus Ki.

sUppLex

3.6 Klassifikationsverfahren
Gesucht ist dann die Klasse Ki, welche die Binärcodierung der Klasse
und des Dokumentes minimiert [59]:

min^ log p WD K i , LD , T log p K i LD , T
Ki

3.6.2 Naiver Bayes-Klassifikator
Der Naive Bayes-Klassifikator (NBK) ordnet ein Dokument D einer
Klasse zu. Es wird für den Wortvektor WD=(w1,…,wn) des Dokumentes die Klasse Ki mit der größten bedingten Wahrscheinlichkeit für
WD gesucht:
maxi P(Ki|WD)
Mit dem Bayes´schen Theorem wird dies zu:

max
Ki

p WD K i * p K i
p WD

Da p(WD) für alle Klassen Ki identisch ist und damit für die Maximierung über die Klassen irrelevant, folgt:

max p WD K i * p K i
Ki

Die Naive Bayes-Klassifikation trifft die Annahme, dass die Attribute
von WD (Worte) unabhängig voneinander auftreten. Dies ist in der
Praxis natürlich nicht der Fall, da beispielsweise die Worte "Doktor"
und "Krankenschwester" signifikant häufiger gemeinsam auftreten
als die Worte "Pinguin" und "Wüste". Dennoch wird diese Annahme
getroffen, was mit wj als der j-ten Komponente (Wort) des Wortvektors WD zu folgender Umformung führt:

max p w1 K i * ... * p wn K i * p K i
Ki

sUppLex

3 Methoden von Empfehlungssystemen
Die Wahrscheinlichkeiten p(wj|Ki) und p(Ki) werden auf Basis statistischer Daten der Lernmengen wie folgt abgeleitet (geschätzt). Die
Wahrscheinlichkeit p(Ki) wird aus der Anzahl der Dokumente einer
Klasse in Relation zur Summe der Dokumente aller Klassen berechnet:

p( K i )

^D D K `
¦ ^D D K `
i

Neben dieser a-priori Wahrscheinlichkeit für die Klassen gilt für die
Wahrscheinlichkeit der Zugehörigkeit des Wortes wj zur Klasse Ki mit
WD[wj] als j-ter Komponente des Wortvektors WD des Dokumentes D:

p w j Ki

^D D K

WD >w j @ ! 0

^D D K `
i

Die bedingte Wahrscheinlichkeit wird also aus der Anzahl der Dokumente einer Klasse, die das Wort enthalten, in Relation zu der Anzahl der Dokumente der Klasse insgesamt berechnet.

3.6.3 Bayes´sches Netz
Ein Bayes´sches Netz ist eine Weiterentwicklung des NBK-Ansatzes.
Ein Bayes´sches Netz B=<V,E,p> ist ein gerichteter azyklischer Graph
(DAG) mit V als Menge der Knoten und E als Menge der Kanten sowie einer bedingten Wahrscheinlichkeit für jeden Knoten N. Jeder
Knoten N stellt eine Zufallsvariable dar. Die Verbindung von Knoten
N1 zu Knoten N2 steht für die bedingte Wahrscheinlichkeit P(N2|N1).
Bei einer Klassifikation mittels eines Bayes´schen Netzes stellen die
inneren Knoten des Graphen die Worte und die Knoten mit ausschließlich einlaufenden Kanten die Klassen dar.
Der Aufbau des Bayes´schen Netzes muss aus den Trainingsdaten
abgeleitet werden. Er erfolgt in zwei Schritten. Zunächst wird die
Struktur aufgebaut, dann werden die Parameter gesetzt [60][61].
Der Strukturaufbau besteht aus drei Teilschritten. In der Draft-Phase
wird die Mutual Information (siehe unten) aller inneren Knoten
(Worte) berechnet und aufgrund der so ermittelten Ähnlichkeiten der
Worte ein Graph erzeugt.

sUppLex

3.6 Klassifikationsverfahren
In der zweiten Phase (Thickening) werden Kanten zwischen nicht dseparierbaren Knoten eingezogen. Zwei Knoten N1 und N2 sind dseparierbar, wenn auf allen Pfaden zwischen N1 und N2 ein Knoten Z
existiert, so dass die Wahrscheinlichkeit von Z bekannt ist und die
Verbindung von Z zu N1 und N2 seriell oder divergierend, oder so
dass Z und dessen Nachfolger unbekannt sind und Z von N1 und N2
zu Z konvergierend ist.
Bild 33:
Kriterien für
d-separierte
Knoten

Im folgenden Graphen sind beispielsweise die Knotenpaare (1,2) und
(5,6) d-separiert, wenn die Wahrscheinlichkeit für die Knoten "2" und
"5" gegeben ist.

sUppLex

3 Methoden von Empfehlungssystemen
Bild 34: Ein
Bayes´sches
Netz im
Aufbau

In der dritten Phase (Thinning) werden schließlich alle Kanten entfernt, deren Knoten d-separierbar sind. Die Parameter ergeben sich
bei der Textklassifikation aus den Testdaten. Hier sind sowohl die apriori als auch die bedingten Wahrscheinlichkeiten der Worte in
Form der relativen Häufigkeiten beziehungsweise der Kookkurrenzen vorhanden. Deren Berechnung ist aber ein recht aufwändiges
Unterfangen.

3.6.4 ID3
Beim ID3 [62] Verfahren wird ein Entscheidungsbaum anhand einer
Trainingsmenge aufgebaut. Im Entscheidungsbaum stehen die Blätter
für die Klassen, die inneren Knoten stellen Attribute dar und die
Kanten tragen einen Attributwert ihres Ausgangsknotens:

sUppLex

3.6 Klassifikationsverfahren
Bild 35: Ein
ID3 Entscheidungsbaum
besteht aus
Klassen
(Blättern),
Attributen
(inneren
Knoten) und
Attributwerten
(Kanten). Aus
dem Entscheidungsbaum
lassen sich
Regeln für die
Klassenzugehörigkeit
der Empfehlungselemente ableiten.

Die Attribute sind im Kontext von Entscheidungssystemen die Eigenschaften der Empfehlungselemente, die entweder (wie in der oben
stehenden Abbildung am Beispiel von Worten als Eigenschaften von
Textdokumenten als Empfehlungselementen) binär oder gewichtet
sind. Wichtig ist allerdings, dass die Anzahl der Werte für ein Attribut klein bleiben muss, wenn ID3 sinnvoll eingesetzt werden soll, da
die maximale Ausprägung eines Attributes mit dem Grad des Baumes übereinstimmt. Aufgrund des Entscheidungsbaumes werden
neue Empfehlungselemente (Texte) dann einer Klasse zugeordnet.
Der Aufbau eines Entscheidungsbaumes erfolgt mit folgendem Algorithmus auf Basis von Traningsdaten T (im Beispiel sind dies Texte)
die manuell den Klassen Ki zugeordnet wurden:

sUppLex

3 Methoden von Empfehlungssystemen
Der ID3
Algorithmus

ID3 (T,Ki)
wenn T=Ki für eine Klasse Ki,
dann erzeuge ein Blatt "Ki"
sonst wenn T=
dann erzeuge ein Blatt ""
sonst
wähle attribut(T,Aj)
erzeuge Knoten "Aj"
für alle Werte WAjk von Aj (k=1…q)
erzeuge Kante "WAjk"
setze T:= T{t|tT
t hat Wert WAJk}
rufe ID3(T,Ki) auf
füge B an Kante "WAJk" ein
gebe den erzeugten Baum "B" zurück

Die Funktion "wähle attribut(T,Aj)" wählt das Attribut mit dem maximalen Informationsgewinn und ist wie folgt definiert; sind keine
Attribute mehr vorhanden, gilt: "wähle die häufigste Klasse".
Der Informationsgewinn G(A) eines Attributes A wird aus der Differenz des Informationsgehaltes (oder der Entropie) I(T) ohne das Attribut A und dem Informationsgehalt I(T|A) unter Berücksichtigung
des Attributes A (bedingte Entropie) bestimmt. Der Informationsgewinn steht also dafür, wie gut man eine Klassifikation eines Empfehlungselementes (hier eines Textdokumentes) mit und ohne dem Attribut vornehmen kann:
G(A)=I(T)-I(T|A)
Der Informationsgehalt einer Menge T von Empfehlungselementen
wird durch die Entropie

I (T )

¦ p( K i ) * log 2 p( K i )
i 1... n

sUppLex

3.6 Klassifikationsverfahren
bestimmt [63], [58]. Konkret steht P(Ki) hier für die Wahrscheinlichkeit von Klasse Ki der Trainingsdaten T beziehungsweise einer Teilmenge davon.
Der Informationsgehalt der Menge T mit Attribut A als Wurzel ist
durch die bedingte Entropie [63; 138 ff.]

I (T A)

¦ p( A

WAJ i ) * I (^t t T A WAJ i `)

i 1... s

definiert. Mit P(A=WAJi) als Wahrscheinlichkeit, dass A den Wert
WAJi annimmt und {t|tTA=WAJi} ist die Teilmenge der Trainingsdaten T, die Attribut A mit dem Wert WAJi (dem Wort) besitzt.
Insgesamt ergibt sich

max I (T ) I (T A j )
Aj

·
§
max ¨ ¦ p( K i ) * log 2 p( K i ) ¦ p( A WAJ i ) * I (^t t T A WAJ i `) ¸
Aj
i 1... s
© i 1...n
¹

Die Wahrscheinlichkeiten werden algorithmisch durch Häufigkeiten
ersetzt:

p Ki

^t t K `
^t t T `
i

und

p A WAJ i

^t t T WAJ
^t t T `

mit |M| als der Anzahl der Elemente der Menge M und "WAJit" als
Bedingung, dass ein Empfehlungselement (hier ein Textdokument) t
den Attributwert WAJi (hier das Wort) enthält.

sUppLex

3 Methoden von Empfehlungssystemen

3.6.5 K-Means-Clustering
K-MeansClustering

Das K-Means-Clustering (KMC) teilt Elemente in Gruppen auf, unterscheidet sich aber von den bisher beschriebenen Klassifikationsverfahren dadurch, dass die Gruppen beim Clustering zunächst unbekannt sind und automatisch gebildet werden. Man unterscheidet
hierarchisches und nicht-hierarchisches Clustering. Ersteres startet
mit einem großen Cluster und spaltet dann in jedem Lauf neue
Cluster ab. Letzteres startet mit meist willkürlich gewählten Clustern
und bildet diese in jedem Lauf mehr und mehr aus. Weitere Spielarten sind das harte und das weiche Clustering. Während Ersteres jedes
Element genau einer Gruppe zuordnet, erlaubt Letzteres die Zuordnung eines Elementes zu mehreren Gruppen.
Übertragen auf Vektoren stellt das Clustering anschaulich ein geometrisches Verfahren im n-dimensionalen Raum dar. Ein bekannter
(harter) Algorithmus zur Clusterbildung ist K-Means der nach willkürlicher Wahl repräsentativer "Punkte" im Vektorraum die Vektoren
den nächsten „Punkten“ zuordnet und dann eine iterative Verbesserung der Punkte durchführt.
Sei X eine endliche Teilmenge eines metrischen Raumes mit der Distanzfunktion d(x,y). Sei f eine Funktion zur Ermittlung des "Schwerpunktes" von n Vektoren v1,…,vn. Im einfachsten Fall ist das der Mittelwertvektor der Vektoren v1,…,vn.

Der K-MeansClusteringAlgorithmus

Wähle k initiale Punkte p1,…,pk
setze pkorrektur = Toleranz
(Abbruch bei Erreichen der Toleranz in Summe für alle Cluster)
solange pkorrektur >= Toleranz
setze pkorrektur=0 (Initialisierung)
für Cluster ci mit i=1,…,k
ci = {vj|pl=1…k:d(vj,pi)<=d(vj,pl)}
palt = pi
pi=f(ci)
pkorrektur=pkorrektur+(pi-palt)
(Korrekturfaktor akkumulieren)

sUppLex

4 Anwendungen
Die folgende Übersicht einer Auswahl bedeutsamer Empfehlungssysteme wird in die drei Hauptgruppen Collaborative Filtering, Content
Based Filtering und Hybride Systeme unterteilt. Empfehlungssysteme
aber nur durch die Einteilung in diese drei Hauptgruppen zu klassifizieren, ist aufgrund der großen Bandbreite der verwendeten Verfahren innerhalb der jeweiligen Gruppe zu grob.
Die im Folgenden beschriebenen Merkmale von Empfehlungssystemen werden in logisch zusammenhängenden Gruppen aufgeführt.
Die dienen einer detaillierten Differenzierung der untersuchten Empfehlungssysteme.
-

Empfehlungselement

: Text, Film etc.

Eigenschaftsanalyse

: TF-IDF, NLP etc.

Profilbildung

: Benutzerverhalten etc.

Distanzmaß

: Vektorbasiert, etc.

Symmetrie2

: ja/nein

Vorberechnung3

: ja/nein

Regelbasiert

: ja/nein

Heuristik5

: ja/nein

Die in den Grafiken verwendeten Akronyme entsprechen denen im vorangegangenen Teil des Buches eingeführten Kürzeln.

Ein „ja“ bedeutet, dass Empfehlungselement E1 das Empfehlungselement
E2 zugeordnet bekommt, wenn umgekehrt E1 auch E2 zugeordnet ist. Bei
Verfahren, die Empfehlungen aus Klassifikation ableiten, liegt Symmetrie
vor, wenn Empfehlungselemente nur einer Klasse zugeordnet werden
können.

Ein „ja“ bedeutet, dass die Empfehlungen nicht im Moment der Nutzung
des Empfehlungssystems durch den Anwender ermittelt, sondern auf
vorberechneten Daten geliefert werden.

Ein regelbasiertes Verfahren leitet aus einer gegebenen Variable X eine
Variable Y ab. Dabei sind X und Y meist Datentupel. Wenn X beispielsweise die bisher durch einen Benutzer aufgerufenen Empfehlungselemente darstellt, könnte Y ein zu empfehlendes Empfehlungselement sein,
das durch die Regel X > Y aus X abgeleitet wird.

Merkmale
von
Empfehlungssystemen

sUppLex

4 Anwendungen
Alle im Folgenden vorgestellten Empfehlungssysteme werden neben
einer kurzen Beschreibung der Grundkonzepte anhand einer einheitlichen Grafik schematisiert.
Bild 36:
Schematische
Darstellung
der Merkmale
eines
Empfehlungssystems

Eine Heuristik ist eine Annäherung oder eine "Daumenregel" für die
Lösung eines Problems.

sUppLex

4.1 Collaborative Filtering-Systeme

4.1 Collaborative Filtering-Systeme
4.1.1 Tapestry

Bild 37:
Tapestry

Das Tapestry [64]-Verfahren arbeitet auf unstrukturierten Daten (EMails). Diese werden von Benutzern explizit bewertet. Benutzer können Filter definieren (explizites Strukturprofil; modellbasiertes CF).
Es kann beispielsweise alle E-Mails anzeigen, die von den Benutzern
B1 und B2 als relevant eingestuft werden (regelbasierte Distanzermittlung). Oder beispielsweise keine E-Mails, die von Benutzer B3 als
irrelevant eingestuft wurden. Wichtig ist also, dass die Benutzer sich
untereinander kennen, um eine Auswahl von Benutzern mit ähnlichen Interessen treffen zu können.

sUppLex

4 Anwendungen

4.1.2 Ringo

Bild 38:
Ringo

Das Ringo [48]-Verfahren empfiehlt dem Benutzer Musik in Form von
Interpreten und Alben. Dazu muss der Benutzer zunächst eine Vorschlagsliste von Interpreten auf einer Skala von 1 bis 7 bewerten.
Diese Vorschlagsliste wird aus den am meisten bewerteten (erhöht
Wahrscheinlichkeit verwandter Benutzer) und aus zufällig gewählten
(garantiert Berücksichtigung aller Interpreten) Interpreten zusammengestellt.
Nach der Bewertung kann der Benutzer folgende Funktionen nutzen:
-

Anzeige von Interpreten/Alben, die dem Benutzer empfohlen werden

Anzeige von Interpreten/Alben, die dem Benutzer nicht empfohlen
werden

Anzeige der Empfehlung (Bewertung von 1 bis 7) zu einem Interpreten oder Album

Hinter den Empfehlungen steht ein Collaborative Filtering-Ansatz.
Im Rahmen von Ringo wurden vier Verfahren zur Ermittlung verwandter Benutzer getestet, indem aus den Benutzerprofilen jeweils

sUppLex

4.1 Collaborative Filtering-Systeme
20% der Empfehlungen entfernt und dann mit den Empfehlungen
auf Basis dieser Verfahren verglichen wurden.
Die Verfahren waren:
-

Durchschnitt der quadrierten Differenzen

Benutzerbezogener Korrelationskoeffizient (PC)

Angepasster benutzerbezogener Korrelationskoeffizient

Elementbasierter Korrelationskoeffizient

Der angepasste benutzerbezogene Korrelationskoeffizient erzielte die
besten Ergebnisse und wird daher in Ringo verwendet. Dabei werden
die skalaren Wertungen der Benutzer in positiv und negativ transformiert, indem unabhängig von den Benutzerbewertungen ein fester
Mittelwert in der Skalenmitte (4) zum Einsatz kommt. Formal wird
für zwei Benutzerprofile v und w statt

Distanz(v,w) =

vi v * wi w

i 1... n

¦v

v *

i 1... n

¦w

i 1... n

die folgende Variante verwendet:

Distanz(v,w) =

vi 4 * wi 4
2

i 1... n

¦v

i 1... n

4 *
2

¦w

i 1... n

sUppLex

4 Anwendungen

4.1.3 GroupLens
Bild 39:
GroupLens

Das GroupLens [59], [65]-Verfahren gibt über einen Collaborative Filtering-Algorithmus Empfehlungen für Usenet-Nachrichten aus. Die
Benutzer geben anonym in einem proprietären Client explizite Bewertungen von Newsgroup-Artikeln auf der Skala von 1 bis 5 ab.
Diese Bewertungen werden an einen zentralen GroupLens-Server
geschickt. Dieser speichert die Bewertungen innerhalb von 60 Sekunden in der Ratings Datenbank und berechnet im 24 Stunden Rhythmus auf Basis dieser Ratings die Korrelationen zwischen allen Benutzern und speichert diese in der „Correlations“-Datenbank. Auf Basis
dieser Datenbank gibt der Server dann individuelle Empfehlungen
für einzelne Benutzer aus. Die empfohlenen Nachrichten werden
durch die betreffenden Newsgroup-Reader angezeigt.

sUppLex

4.1 Collaborative Filtering-Systeme

4.1.4 Siteseer
Bild 40:
Siteseer

Siteseer [49] basiert auf Browser-Bookmarks. Die Bookmarks eines
Benutzers werden zentral gespeichert (boolesche Bewertung von
Objekten). Auf diese Bookmarks, die insbesondere in Kategorien
aufgeteilt werden können (manuelle Metadaten), hat der Benutzer
jederzeit Zugriff, um Webseiten aufzurufen. Die Bookmarks eines
Benutzers werden mit den Bookmarks anderer Benutzer auf gleiche
Einträge hin verglichen. Je mehr identische Einträge bei zwei Benutzern vorliegen, umso ähnlicher werden diese Benutzer eingestuft.
Das System liefert dem Benutzer dann die Bookmarks seiner nächsten Nachbarn (NN Distanzmaß).

sUppLex

4 Anwendungen

4.1.5 Jester (Eigentaste)
Bild 41: Jester

Das Jester [66]-Verfahren empfiehlt dem Benutzer Texte (Witze) auf
Basis eines Collaborative Filtering-Ansatzes. Das Besondere ist, dass
die Benutzer im Rahmen der Profilbildung dieselben Texte bewerten
müssen. Dadurch wird das Problem der "Spärlichkeit" eliminiert.
Dass der Benutzer auch ihm potenziell unbekannte Texte bewerten
muss, versucht das Verfahren durch einen Gewichtungsfaktor in
Form des Bekanntheitsgrades zu korrigieren.
Die Bewertung selbst erfolgt auf einer fein granularen Skala in Form
eines Schiebereglers mit 200 nicht einzeln markierten Bewertungsstufen. Jede Bewertung wird normalisiert, indem der Durchschnitt aller
Bewertungen subtrahiert und dann durch die Standardabweichung
dividiert wird.
Durch Hauptkomponentenanalyse (Principal Component Analysis
(PCA), [67]) wird die Dimension des zu betrachtenden Vektorraums
auf einen weniger dimensionalen Unterraum reduziert, in dem der
Hauptteil der Datenvarianz liegt. Mit PCA wird, vereinfacht ausgedrückt, das Maximum an Datenvarianz in einem Minimum an Dimensionen abgebildet.
Abschließend werden mit rekursiver geometrischer Klassifikation
(KMC) die Benutzergruppen aufgeteilt, indem Cluster (konkret 40)

sUppLex

4.1 Collaborative Filtering-Systeme
gebildet werden. Ein neuer Benutzer erhält dann wie folgt seine Empfehlungen:
-

Bewertungen für die ausgewählten Texte einholen

Wertungsvektor (=Profil) mittels PCA in den Unterraum abbilden

zugehörigen Cluster wählen

Empfehlungen aus diesem Cluster anbieten und bewerten lassen

Ein wesentlicher Vorteil des Eigentaste-Verfahrens besteht in der
konstanten Laufzeitkomplexität, die Skalierungsprobleme eliminiert.

4.1.6 Amazon
Bild 42:
Amazon

Das Amazon [68], [69] Collaborative Filtering-Verfahren empfiehlt
dem Benutzer Bücher aufgrund der aktuell oder vor kurzem (in der
gleichen Session mit flüchtigem Profil) in seinem Warenkorb befindlichen Bücher. Basis der Empfehlungen ist eine "offline item-to-item"
Distanz-Tabelle, die aufgrund des Benutzerverhaltens (Kauf) vorberechnet wird.
Die Vorberechnung findet zu Büchern "ähnliche" Bücher, indem sie
analysiert, welche Bücher von gleichen Benutzern gekauft werden.
Dazu wird zu jedem Buch ein Vektor aufgebaut. Es handelt sich um
ein elementbasiertes Collaborative Filtering-Verfahren, bei dem das
Cosinus-Ähnlichkeitsmaß für die Distanzermittlung zwischen zwei

sUppLex

4 Anwendungen
Buch-Vektoren verwendet wird. Eine Besonderheit ist die Vorberechnung dieser Distanzen. Nur dadurch kann gewährleistet werden,
dass die Performanz auch bei den großen Benutzer- (29 Millionen)
und Buchzahlen (mehrere Millionen) ausreichend ist. Ist die DistanzTabelle einmal berechnet, so ist die Laufzeit lediglich von der Anzahl
der Bücher, die der Benutzer in seinem Warenkorb hat (oder kürzlich
hatte), abhängig. Für jedes dieser Bücher werden dann durch einfache Punktselektion auf der Distanz-Tabelle die ähnlichsten Bücher
ermittelt und anschließend zu einer Empfehlungsliste zusammengeführt.

4.1.7 SurfLen
Bild 43:
SurfLen

Das SurfLen [70]-Verfahren basiert auf elementbasiertem Collaborative Filtering. Auf Basis des Benutzerverhaltens, ermittelt durch die in
einer Session aufgerufenen Webseiten, werden automatisiert Regeln
(so genannte Assoziationsregeln) abgeleitet, die ein Modell für die
Benutzer-Element-Matrix darstellen. Dem Benutzer werden zur aktuell betrachteten Webseite Empfehlungen eingeblendet. Technisch
erfolgt dies durch ein Browser-Plug-In.
Eine neue Regel wird immer iterativ erzeugt. Dabei kommt die im
Folgenden beschriebene Heuristik zum Einsatz. Zunächst werden die
Empfehlungselemente selektiert, deren Vorkommen über alle Sessions einen bestimmten Schwellwert (Prozentwert minsup) übertrifft.

sUppLex

4.1 Collaborative Filtering-Systeme
Dann werden die daraus bildbaren 2-Tupel (i1,i2) von Empfehlungselementen gebildet, deren gemeinsames Vorkommen in allen Sessions wiederum den Schwellwert minsup überschreitet. Gleiches wird
dann für 3-Tupel, 4-Tupel etc. durchgeführt. Durch minsup wird die
Zahl der zu betrachtenden Tupel klein gehalten.
Die so gefundenen Tupel werden zum Erzeugen der Regeln verwendet. Dazu wird aus einem Tupel (i1,i2,…,ik) die Regel XoY mit
X=(i1,i2,…,ik-1) und Y=(ik) erzeugt. Daraus folgt, dass die Empfehlungen potenziell asymmetrisch sind.
Die Tupelerzeugung ist der im Rahmen der Regelerzeugung aufwändige Vorgang. Die Berechnung durch die SRE (SurfLen Recommendation Engine) ist ein dauerhaft laufender Prozess, da die Regeln
ständig an die Daten neuer Sessions (Benutzerverhalten) angepasst
werden müssen.
Damit dem Benutzer auch dann eine Empfehlung gegeben werden
kann, wenn keine Regel auf sein aktuelles Verhalten zutrifft, wird in
diesem Falle die Schnittmenge der Empfehlungselemente aus der
Benutzersession und der Empfehlungselemente aus den Sessions in
der SurfLen-Datenbasis gebildet (in diesem Falle erfolgt das Collaborative Filtering speicherbasiert und elementbasiert).
Die Empfehlungen bestehen in diesem Fall aus den Empfehlungselementen der Session Sj mit der größten Schnittmenge zu B, wobei
die in der Benutzersession B vorkommenden Elemente ausgeblendet
werden:
B=(i1,i2,…,ik), S=(s1,s2,…,sm)
Empfehlung:=Sj-B mit

max B S j
i

sUppLex

4 Anwendungen

4.1.8 PocketLens
Bild 44:
PocketLens

PocketLens [71] liegen als einem Vertreter des Collaborative Filtering
vier Zielsetzungen zugrunde: portability, palmtop compatibility, user
control und accuracy. Die portability meint die Nutzungsmöglichkeit
an beliebigem Standort und insbesondere auch im Offline-Betrieb.
Dies und die palmtop compatibility werden durch einen modellbasierten Collaborative Filtering-Ansatz erreicht. Das Modell wird erstellt
und lokal gespeichert, während der Benutzer online ist. Die Collaborative Filtering Matrix wird in eine Element-Element-Matrix transformiert und auf die Elemente reduziert, die durch den Benutzer
bewertet wurden. Das vektorbasierte Benutzerprofil besteht aus Bewertungen von Empfehlungselementen. Der Benutzer kann selbst
bestimmen (user control), welche Teile seines Profils für andere Benutzer verfügbar sind. Die accurracy wird durch ein modifiziertes
elementbasiertes Collaborative Filtering-Verfahren erreicht.
Dazu wird zunächst aus der Collaborative Filtering-Matrix eine Element-Element-Matrix gebildet. Letztere beinhaltet die Relevanz, mit
der auf Basis von Empfehlungselement I1 das Empfehlungselement I2
empfohlen wird. Ein trivialer Weg diese Matrix zu konstruieren ist
die Summation einer identischen Bewertung zweier Objekte durch
einen Benutzer. Das PocketLens-Verfahren verwendet ein weiterentwickeltes inkrementelles Verfahren:

sUppLex

4.1 Collaborative Filtering-Systeme
Seien O1,…,On die Zeilen und N1,…Nn die Spalten der nichtreduzierten Element-Element-Matrix, die bei n Elementen n Zeilen
und n Spalten umfasst. Wenn die Elemente Oi (durch den Benutzer
selbst bewertete Empfehlungselemente) und Nj die Bewertungen wk
und uk durch einen anderen Benutzer Bk erhalten, wird die Zelle
(Oi,Nj) der Matrix wie folgt angepasst:
Cooccur(Oi,Ni)= Cooccur(Oi,Ni)+1
PtLenW(Oi,Nj)= PtLenW(Oi,Nj)+wk*wk
PtLenU(Oi,Nj)= PtLenW(Oi,Nj)+uk*uk
PDot(Oi,Nj)= PDot(Oi,Nj)+ wk*uk

Die Distanz zweier Objekte Oi und Nj wird durch eine CosinusÄhnlichkeitsfunktion auf Basis der Zellwerte berechnet:

sim(Oi , N j )

Fk *

PDot (Oi , N j )
PtLenU (Oi , N j ) * PtLenW (Oi , N j )

mit Fk=1 falls Cooccur(Oi,Nj)>=50 und Fk=Cooccur(Oi,Nj) sonst. Sie wertet Benutzer Bk ab, die hohe Übereinstimmung, aber nur wenige gemeinsame Objekte besitzen.

sUppLex

4 Anwendungen

4.1.9 PACT
Bild 45:
PACT

Bei PACT [72] wird auf Basis des Benutzerverhaltens auf einer Website ein flüchtiges Profil in Form eines gewichteten Transaktionsvektors
gebildet. Die Gewichtung einer Seite resultiert dabei aus der gemessenen Lesedauer. Außerdem erzeugt PACT auf Basis der Transaktionen aller Benutzer Kategorien, indem das Mittel aller zu einer Kategorie gehörigen Transaktionsvektoren durch Addition der Komponenten und Division durch die Anzahl der Vektoren ermittelt wird
(modellbasiertes Collaborative Filtering). Welcher Klasse ein Transaktionsvektor zugeordnet wird, entscheidet das Verfahren mit dem
Klassifikationsverfahren K-Means Clustering (KMC).
Empfehlungen in Form von anderen Webseiten werden dem Benutzer in der aktuell angezeigten Webseite gegeben (diese wird dazu vor
der Auslieferung an den Benutzer modifiziert).

100

sUppLex

Dabei wird eine Webseite umso mehr empfohlen, je höher die Summe ihrer Gewichtungen über alle gemittelten Klassenvektoren ist.
Zusätzlich fließt die Übereinstimmung von Transaktionsvektor (der
auf "n" Schritte limitiert wird, um die Wahrscheinlichkeit inhaltlich
zusammenhängender Webseiten zu erhöhen) und den einzelnen
Klassenvektoren als Korrekturfaktor ein, wobei als Distanzfunktion
das Cosinus-Ähnlichkeitsmaß (COS) zum Einsatz kommt.
Webseiten, die in der aktuellen Transaktion enthalten sind, werden
ausgefiltert:
Empfehlung

= Pi mit pi (p1,…,pn)
= Webseiten in einem Klassenvektor C

und

Gewichtung pi , c j * cos Transaktion, c j t Schwellwert
mit
Cj = Klassenvektoren (j=1…m) , i=1…n

101

sUppLex

4 Anwendungen

4.2 Content Based Filtering-Systeme
4.2.1 The Information lens
Bild 46:
Information
Lens

Das System The Information Lens [73] setzt auf einem E-Mail-Dienst
auf und arbeitet auf semi-strukturierten Daten, indem es semistrukturierte E-Mail-Templates anbietet. Das heißt, neben Volltext
werden noch Meta-Daten (beispielsweise "Ort", "Produkt" etc.) mitgeführt, die vom Sender einer E-Mail ausgefüllt werden. Der Sender
kann ferner durch einen Adressaten "lens" (spezielles E-Mail-Konto)
die Verteilung der E-Mail an alle potenziell interessierten Empfänger
einleiten. Ein Empfänger wiederum erhält solche E-Mails, wenn diese
durch eines seiner E-Mail-Templates "erkannt" wird (regelbasierte
Distanzermittlung). Die Erkennung beschränkt sich hier auf eine

102

sUppLex

4.2 Content Based Filtering-Systeme
einfache Übereinstimmung der strukturierten Daten einer E-Mail mit
einem E-Mail-Template (beispielsweise der passende "Ort").

4.2.2 Infoscope
Bild 47:
Infoscope

Infoscope [74] verwendet Filterregeln (Distanzermittlung auf Basis
einer Regel), um Usenet-Nachrichten zu empfehlen. Dabei protokollieren Agenten das Benutzerverhalten und erzeugen daraus automatisch Filter-Regeln auf Basis der Präferenzen des Benutzers. Diese
Filter-Regeln werden dem Benutzer dann als "virtuelle Newsgroups"
angeboten. Die Benutzer können Regeln annehmen, verändern oder
ablehnen. Diese Aktionen werden wiederum von den Agenten aus-

103

sUppLex

4 Anwendungen
gewertet, um zukünftige Empfehlungen zu verbessern. Filter-Regeln
müssen also nicht aktiv erstellt, sondern nur bewertet werden. Durch
das aktive Angebot wird der Benutzer auf eine potenziell veränderte
Interessenslage aufmerksam gemacht.

4.2.3 Newsweeder
Bild 48:
Newsweeder

Bei Newsweeder [59] wird ein Benutzerprofil auf Basis expliziter Bewertungen von Newsgroup-Beiträgen auf einer Skala von 1 bis 5
gebildet.

104

sUppLex

4.2 Content Based Filtering-Systeme
Texte werden dabei in der ersten Variante von Newsweeder durch
Wortvektoren mit binären Werten (0,1 für Wort nicht vorhanden oder
vorhanden) repräsentiert.
Um die Komplexität des Verfahrens zu reduzieren, werden in einer
weiteren Variante die Worte durch ein TF-IDF-Derivat gewichtet, die
Abstände der Vektoren mit dem Cosinus-Ähnlichkeitsmaß ermittelt
und dann mit einem NN-Verfahren (Nearest Neighbours) zu Kategorien zusammengefasst.
Die finale Newsweeder-Variante arbeitet mit einem MDL Verfahren
(Minimum Description Length). Ein Wortvektor v wird bei Newsweeder der Kategorie K zugeordnet, deren Codierung zusammen mit v
am wenigsten Speicherplatz benötigt.

4.2.4 Letizia
Beim Letizia [75]-Verfahren wird das Benutzerverhalten im Webbrowser in folgender Form ausgewertet: Zur aktuell angezeigten
Seite werden mit einem TF-IDF-Derivat die wichtigsten Schlüsselworte ermittelt und dem Benutzerprofil, das ein gewichteter Wortvektor ist, hinzugefügt. Außerdem werden die von der aktuell angezeigten Seite verlinkten Webseiten analysiert. Und zwar wie bei einer
Patrouille (daher der Begriff "reconnaissance agent" bei Letizia) in
immer tieferen Link-Hierarchie-Stufen, solange der Benutzer die aktuelle Seite betrachtet. Die analysierten Seiten werden mit einem TFIDF-Derivat in Wortvektoren transformiert und mittels des CosinusÄhnlichkeitsmaß mit dem Benutzerprofil verglichen. Von allen möglichen Links der verschiedenen Stufen, die von der aktuell betrachteten Seite ausgehen, werden dem Benutzer die am besten zu seinem
Profil passenden angeboten. Dabei wird das bestimmende Schlüsselwort, aufgrund dessen die Empfehlung ausgesprochen wurde, mit
angegeben.

105

sUppLex

4 Anwendungen
Bild 49:
Letizia

106

sUppLex

4.2 Content Based Filtering-Systeme

4.2.5 WebWatcher
Bild 50:
WebWatcher

107

sUppLex

4 Anwendungen
WebWatcher [76],[77],[78] unterstützt den Benutzer bezüglich Webseiten auf Basis seines Benutzerprofils durch zwei wesentliche Arten
von Empfehlungen:
-

Bestehende Hyperlinks: werden in einer Webseite hervorgehoben,
wenn als empfehlenswert betrachtet

Neue Webseiten: die zur aktuellen Webseite Passenden werden
empfohlen

Das Benutzerprofil besteht aus expliziten strukturierten Angaben
(Interessensspezifikation). Wesentlich sind dabei die Suchworte, die
der Benutzer angibt. Diese werden verwendet, um Hyperlinks im
angezeigten Text hervorzuheben. Zur Bewertung der Hyperlinks
wird das Cosinus-Ähnlichkeitsmaß zwischen Benutzerprofil in Form
eines Wortvektors der Suchworte und den Hyperlinks in Form der
binären Wortvektoren hi=1…n berechnet, wobei hi aus den Worten
-

im Titel des Textes, in dem der Link vorkommt

im Satz, in dem der Link vorkommt

im Linktext

gebildet wird.
Bei der Empfehlung "ähnlicher" Webseiten zur gerade angezeigten
Webseite kommt Content Based-Filterung zum Einsatz, bei dem die
Eigenschaften von Webseiten durch die eingehenden Hyperlinks
beschrieben werden. Zwei Webseiten, die durch Hyperlink-Vektoren
(Matrixspalten) repräsentiert sind, werden mit dem Ähnlichkeitsmaß
der Transinformation (Mutual Information, MI) verglichen.

108

sUppLex

4.2 Content Based Filtering-Systeme

4.2.6 Syskill & Webert
Bild 51:
Syskill &
Webert

Bei Syskill & Webert [79] werden auf Basis der Bewertung von Webseiten Benutzerprofile generiert und dann neue Webseiten, die diesen
ähnlich sind, empfohlen. Die Texte der Webseiten werden mit einem
TF-IDF-Derivat in einen booleschen Wortvektor transformiert. In das
Benutzerprofil, das ebenfalls einen booleschen Wortvektor darstellt,
werden vereinfacht ausgedrückt die Worte aufgenommen, die in gut
bewerteten Texten häufig vorkommen, also vermeintlich "bedeutend"
für den Benutzer sind. Nachdem sechs verschiedene Verfahren Distanz-Ermittlung vorgestellt und evaluiert werden, wird der Naive
Bayes-Klassifikator als Mittel der Wahl definiert.

109

sUppLex

4 Anwendungen

4.2.7 Remembrance Agent
Bild 52:
Remembrance
Agent

Der Remembrance Agent [80], [81] ermittelt aufgrund eines vom Benutzer gerade bearbeiteten Textes ähnliche Texte. Dabei kann der
Benutzer einstellen, in welchem Radius (konkret wie viele Zeichen)
um die aktuelle Cursorposition der Text für Empfehlungen berücksichtigt werden soll. Dabei können für die n Empfehlungen, die im
proprietären Client zeilenweise angezeigt werden, unterschiedliche
Text-Umfänge eingestellt werden. Die empfohlenen Texte werden
dem Benutzer in einem speziellen Frontend, in dem er auch den aktuellen Text bearbeitet, angeboten. Dabei wird die SMART Suchmaschine ("Salton's Magical Automatic Retriever of Text", später auch
als "System for the Manipulation and Retrieval of Text" bezeichnet)

110

sUppLex

4.2 Content Based Filtering-Systeme
[82], [83] eingesetzt. Diese nutzt in der eingesetzten Variante den von
Rocchio und Salton entwickelten Rocchio-Ansatz [83]. Dabei werden
die Texte zunächst mit einem TF-IDF-Derivat in gewichtete Wortvektoren transformiert. Dies wird beim Remembrance Agent einmal pro
Nacht für neue Texte durchgeführt (vorberechnet). Die Ähnlichkeit
von Texten wird mit dem Cosinus-Ähnlichkeitsmaß der Wortvektoren ermittelt.

4.2.8 InfoFinder
Bild 53:
InfoFinder

Infofinder [84] beobachtet den Benutzer beim Aufrufen von Webseiten.
Das Verfahren extrahiert aus den durch Anklicken eines "Smiley"
explizit positiv bewerteten Webseiten mit einer Heuristik die be-

111

sUppLex

4 Anwendungen
stimmenden Worte. Diese Worte werden in einen Entscheidungsbaum integriert, der das Benutzerprofil repräsentiert. Welchem Profil
eine Webseite beziehungsweise deren bestimmende Worte hinzugefügt werden, bestimmt der Benutzer explizit durch Zuordnung zu
einem bestehenden oder Anlegen eines neuen Profils. Der Entscheidungsbaum eines Profils wird dann in eine boolesche Anfrage gewandelt und an eine Standard-Suchmaschine gesendet. Diese Anfragen werden offline (nachts) durchgeführt, und dem Benutzer werden
interessante neue Webseiten am nächsten Tag zur Verfügung gestellt.
Die bestimmenden Worte einer Webseite werden mit folgender Heuristik ermittelt:
-

Worte, die in einer Stoppwortliste stehen, sind grundsätzlich unwichtig

komplett großgeschriebene Worte sind wichtig (Vermutung: es
handelt sich um ein Akronym)

Worte vor einem in Klammern oder Anführungszeichen stehenden
komplett großgeschriebenen Wort sind wichtig (Vermutung: Definition eines Akronyms)

In Klammern oder Anführungszeichen stehende Worte nach einem
komplett großgeschriebenen Wort sind wichtig (Vermutung: Definition eines Akronyms)

Anders formatierte Wortfolgen von zwei bis drei Worten, die kein
eigenständiger Satz sind, sind wichtig (Vermutung: erstmalige
Verwendung eines wichtigen Wortes)

Worte in Aufzählungen sind wichtig

Worte in Überschriften sind wichtig

Worte in Bildunterschriften sind wichtig

Worte in Tabellenspalten und -zeilen sind wichtig

Oftmals wiederholte Wortfolgen sind wichtig

Substantive in direkter Folge sind wichtig (Vermutung: Fachbegriff)

Worte, die Sonderzeichen (beispielsweise Bindestrich) oder Ziffern
enthalten, sind wichtig

Worte mit Großbuchstaben im Wort sind wichtig

Es kommt ein Thesaurus zum Einsatz, um Synonyme zu erkennen
und als "identisch" bewerten zu können.

112

sUppLex

4.2 Content Based Filtering-Systeme
Der Entscheidungsbaum eines Profils wird – solange noch nicht zehn
Webseiten zugeordnet sind – mit jeder neu zugeordneten Webseite
nach dem ID3 Algorithmus [62] komplett neu initialisiert. Ab der elften Webseite wird eine neue Webseite nur noch eingefügt, ohne den
Baum neu aufzubauen.

4.2.9 Amalthaea
Bild 54:
Amalthaea

In Amalthaea [85] werden die Profile der Benutzer durch gewichtete
Wortvektoren repräsentiert. Jeder Benutzer besitzt automatische und
explizite Profile. Ein neues automatisches Profil wird durch die Beobachtung des Benutzerverhaltens in einer Session erzeugt (flüchtiges
Profil). Die am stärksten frequentierten Webseiten werden dann mit

113

sUppLex

4 Anwendungen
einem TF-IDF-Derivat in Wortvektoren transformiert und zu einem
Benutzerprofil zusammengefügt. Der Benutzer kann bestehende Profile (auch automatische) anpassen, indem er Webseiten entfernt, neue
hinzufügt oder Worte des Wortvektors als besonders wichtig einstuft.
Neue, auf Basis eines Profils empfohlene Webseiten kann der Benutzer auf einer Skala von 1-5 bewerten und das Profil so beeinflussen.
Die Empfehlungen werden mit dem Cosinus-Ähnlichkeitsmaß ermittelt.

4.2.10 AgentDLS
Bild 55:
AgentDLS

Das Content Based Filtering-Verfahren AgentDLS [86] ermittelt Empfehlungen für Webseiten auf Basis folgender Heuristik:

114

sUppLex

4.2 Content Based Filtering-Systeme
(i)

Schlüsselworte

Enthält ein Text explizite Schlüsselworte im Fließtext (erkannt aufgrund von Wort-Indikatoren wie "keyword" etc.), so werden diese
dem Text zugeordnet und für die Distanzermittlung mit dem gerade
angezeigten Text verwendet. Eine Stoppwortliste sorgt dafür, dass zu
allgemeine Schlüsselworte nicht verwendet werden.
(ii)

Personen

Durch Pattern-Matching werden Namensnennungen ermittelt, die
mit einem Personenverzeichnis (manuell aufgebaut) übereinstimmen.
Als Empfehlung wird die Webseite der erkannten Person empfohlen.
(iii)

Zitate

Analog zu "Personen" – allerdings für Veröffentlichungen.
(iv)

Concept

Die Distanz zwischen dem angezeigten Text und anderen Texten –
beziehungsweise deren Wortvektoren – wird mittels dem Naive Bayes-Klassifikator (NBK) ermittelt. Dazu kommt das Rainbow Package
von McCullam [87] zum Einsatz, das mit binären Wortvektoren arbeitet.
Die Empfehlungen werden dem Benutzer bei der Anzeige des aktuellen Textdokumentes angezeigt. Die Ermittlung und Anzeige der
Empfehlungen erfolgt allerdings asynchron, um die Anzeige des
Dokumentes nicht zu verlangsamen.

115

sUppLex

4 Anwendungen

4.2.11 Webmate
Bild 56:
Webmate

Webmate [88] verwendet Benutzerprofile, die aus gewichteten Wortvektoren bestehen. Diese Vektoren werden auf Basis eines TF-IDFDerivates aus Texten mit positiven Benutzerbewertungen gewonnen.
Die Zahl der Wortvektoren, die für "Interessen" eines Benutzers stehen, wird durch kontinuierliche Zusammenfassung von Vektoren mit
großer Ähnlichkeit gering gehalten. Die Ähnlichkeit wird mit dem
Cosinus-Ähnlichkeitsmaß bestimmt. Die Wortvektoren des Benutzerprofils werden dann mit den ebenfalls gewichteten Wortvektoren
neuer Webseiten auf Basis des Cosinus-Ähnlichkeitsmaßes verglichen.
Übersteigt die Ähnlichkeit der Vektoren einen Schwellwert, so wer-

116

sUppLex

4.2 Content Based Filtering-Systeme
den die Webseiten dem Benutzer in Form einer "virtuellen Zeitung"
mit absteigend nach Relevanz (Ähnlichkeit) sortierten Links empfohlen. Die Berechnung der Empfehlungen erfolgt "offline" (vorberechnet), wenn genügend Rechenleistung verfügbar ist.

4.2.12 SLIDER
Bild 57:
SLIDER

Bei SLIDER [89] werden Webseiten und Benutzerprofile durch gewichtete Wortvektoren repräsentiert. Jeder Benutzer besitzt mehrere
Profile. Der Benutzer kann Webseiten explizit Profilen zuordnen,
innerhalb der Profile verschieben und auch wieder komplett entfernen. Ferner kann der Benutzer die vorgeschlagenen Webseiten be-

117

sUppLex

4 Anwendungen
werten (binäre Wertung durch "Star"-Auszeichnung). Das Lesen einer
Webseite wird implizit bewertet. Auf Basis dieser Aktionen werden
die Wortvektoren der Profile durch die Wortvektoren der Webseiten
verändert. Gelöschte Webseiten werden als Ausschlusskriterien für
die Empfehlungen verwendet, bleiben in SLIDER also als Information
erhalten. Die Gewichtung (E) gestaltet sich dabei wie folgt:
-

zuordnen: 3

löschen: 3

lesen: 0,5

bewerten: 3

keine Aktion: 0,25

Zu jedem Profil (topic) werden dem Benutzer die sechs relevantesten,
noch nicht vom Benutzer gesehenen Webseiten angezeigt. Außerdem
gibt es ein topic "other news", in dem der Benutzer bisher ungesehene
Webseiten sieht, die mit keinem seiner Profile übereinstimmen. Dadurch soll ein "Tunnelblick" (overspecialization) vermieden werden.
Der Wortvektor eines Textes wird durch ein TF-IDF-Derivat gebildet.
Die Relevanz eines Textes für einen bestimmten Benutzer wird durch
sim, ein Derivat des Cosinus-Ähnlichkeitsmaßes zwischen Text- und
Profil-Vektor bestimmt. Ein neuer Text wird in Form seines Wortvektors wie folgt in das Profil übernommen:
P'=P + ED

Wobei P' das neue und P das alte Profil sowie D den Wortvektor des
neuen Textes repräsentieren. Dabei steht E für die Gewichtung der
Webseite.

118

sUppLex

4.2 Content Based Filtering-Systeme

4.2.13 LexicalChainer
Bild 58:
Lexical
Chainer

Das LexicalChainer [90]-Verfahren erzeugt Links zwischen Dokumenten, empfiehlt also Text zueinander. Es verwendet dazu Lexical Chaining, wobei eine Lexical Chain (LC) eine Folge semantisch verbundener Worte ist.
Die Intention ist es, Textfragmente zu ermitteln, die das gleiche Thema haben. Dadurch soll die Ambiguität, die bei Verwendung einzelner Worte entsteht, reduziert werden. Als Basis für die Lexical ChainBildung kann jedes Verzeichnis verwendet werden, das Worte mit
ihren Bedeutungen verbindet (NLP). Beim LexicalChainer kommt
WordNet [91] zum Einsatz. Unter anderem gruppiert WordNet Worte
nach Synonymgruppen (als "Synsets" bezeichnet), die noch mit Hyperonym/Hyponym-Beziehungen verknüpft sind. Worte, die über die
Beziehungen in WordNet verbunden sind, bilden eine Lexical Chain.

119

sUppLex

4 Anwendungen
Jeder Text T wird durch zwei Vektoren v1,v2 repräsentiert:
v1=(g11,…,g1n)
mit g1i= Gewicht des Synsets i im Text = Anzahl des Vorkommens des
Synsets in den Lexical Chains des Textes
v2=(g21,…,g2n)
mit g2i= Gewicht des Synsets i im Text = Anzahl des Vorkommens des
Synsets in WordNet-Relation (Hyperonym, Hyponym etc.) zu einem
Synset das in v1 ein Gewicht größer "0" hat.
Die Distanz zweier Texte A und B wird durch das CosinusÄhnlichkeitsmaß zwischen den Vektoren vA1, vA2 von Text A und vB1, vB2
von Text B mit folgender Heuristik ermittelt:
(i)

D1=COS(vA1,vB1)

(ii)

D2=COS(vA1,vB2)

(iii)

D3=COS(vA2,vB1)

Erreicht die Summe
D=¦i=1…3Di

dieser Distanzen einen bestimmten Schwellwert, so wird der Text
dem Benutzer empfohlen.

120

sUppLex

4.2 Content Based Filtering-Systeme

4.2.14 NewsDude
Bild 59:
NewsDude

NewsDude [92] empfiehlt dem Benutzer auf Basis seines Profils neue
Texte. Dabei werden ein aktuelles und ein langfristiges Profil unterschieden. Um Empfehlungen auszusprechen, werden Texte zunächst
mit dem kurzfristigen Profil verglichen; erst wenn dies keine ausreichende Ähnlichkeit ergibt, kommt das langfristige Profil mit der Aufteilung in "interessant" oder "nicht interessant" zum Einsatz.
Das aktuelle Profil besteht aus den vom Benutzer bewerteten Texten.
Die Texte werden als Wortvektoren im Profil abgelegt. Die Empfehlung neuer Texte erfolgt dann durch Transformation derselben in

121

sUppLex

4 Anwendungen
Wortvektoren und Bestimmung der Ähnlichkeit zum Profil auf Basis
des Cosinus-Ähnlichkeitsmaßes.
Das langfristige Profil beruht auf der Naiven Bayes-Klassifikation
(NBK) der booleschen Wortvektoren der Texte und besteht aus den
Klassen "interessant" und "nicht interessant". Texte werden bei
NewsDude nur dann klassifiziert, wenn diese mindestens n (konkret
3) Worte der betreffenden Klasse enthalten.
Eine Besonderheit von NewsDude ist, dass dem Benutzer ausgesprochene Empfehlungen erklärt werden. Wird ein Text auf Basis des
aktuellen Profils empfohlen, so wird die Anmerkung ausgegeben,
dass der Text empfohlen wurde, weil zuvor einmal der Text t positiv
bewertet wurde. Dabei steht t für den Text aus dem aktuellen Profil
mit dem größten Cosinus-Ähnlichkeitsmaß. Wurde die Textempfehlung
auf Basis des langfristigen Profils ermittelt, so gib NewsDude die Worte des Textes an, die maßgeblich zur Zuordnung des Textes zur Klasse der "interessanten" Texte geführt haben.

4.2.15 SIFT
In SIFT [93] ("Stanford Information Filtering Tool") kann der Benutzer
beliebig viele explizite Profile in Form von Anfragen (Queries) samt
deren Parametern (Benachrichtigungsfrequenz, Anzahl der gewünschten Ergebnisse etc.) anlegen. Mit booleschen Anfragen (gewünschte und nicht gewünschte Worte) und Vektorraum-Anfragen
(VSM; Vector Space Model; es wird eine Wordmenge als Anfrage
verwendet) bestehen zwei verschiedene Anfragetypen. Bei Vektorraum-Anfragen kommt das TF-IDF-Verfahren zur Erzeugung der gewichteten Wortvektoren zum Einsatz. Die Ähnlichkeiten werden
dann mittels Cosinus-Ähnlichkeitsmaß ermittelt.

122

sUppLex

4.2 Content Based Filtering-Systeme

Bild 60: SIFT

Bei der Anfrageverarbeitung werden drei Ansätze zur Bearbeitung
vorgestellt. Beim BF-Ansatz (Brute Force) wird für jedes neue Dokument jede Anfrage erneut ausgeführt, um zu entscheiden, ob dem
Benutzer das Objekt empfohlen werden soll. Der QI-Ansatz (Query
Indexing) reduziert die Anzahl der auszuführenden Anfragen, indem
nur solche ausgeführt werden, die mindestens ein Wort des neuen
Dokumentes enthalten. Dazu wird ein inverser Index mit den Worten
der Anfragen verwaltet, in dem von jedem Wort die Anfragen, in
denen es verwendet wird, erreichbar sind. Der SQI-Ansatz (Selective

123

sUppLex

4 Anwendungen
Query Indexing) reduziert zusätzlich noch die im inversen Index geführten Worte einer Anfrage, indem nur die signifikanten Worte der
Anfrage verwendet werden. Die Selektion der signifikanten Worte
erfolgt auf Basis eines IDF-Derivates.

4.2.16 Watson
Bild 61:
Watson

WATSON [94], [95], [96] liefert dem Benutzer zu seinem in einer Applikation (Textverarbeitung, Browser etc.) angezeigten Text inhaltlich
verwandte Texte. Dazu verwendet WATSON Plug-Ins (Application
Adapters), um Zugriff auf den in einer Applikation angezeigten Text
zu haben.
Aufgrund des Textes wird dann, wie im Folgenden beschrieben, eine
Suchanfrage erzeugt. Da WATSON die Texte, gegen die die Suchanfragen laufen sollen, nicht in der eigenen Datenbasis vorhält und auf

124

sUppLex

4.2 Content Based Filtering-Systeme
diese in der Regel nur in Form eines unstrukturierten Textes Zugriff
hat, kann kein vektorbasiertes Verfahren zum Einsatz kommen.
Stattdessen verwendet WATSON ein Bündel von Heuristiken, um aus
einem Text T die für die Suchanfrage relevanten Worte in Form einer
sortierten Liste zu selektieren.
Diese Heuristiken sind:
-

Entfernung der Stoppworte; dabei verlässt sich WATSON allerdings auch auf die Quellsysteme (siehe unten); das heißt, WATSON entfernt nur die Stoppworte aus der Suchanfrage, die in einer
statischen Stoppwortliste definiert wurden

Je häufiger ein Wort vorkommt, desto wichtiger ist es (TF-IDFDerivat)

Hervorgehobene Worte (fett etc.) sind wichtiger

Worte am Anfang eines Textes sind wichtiger, als jene am Ende des
Textes (Textverlauf)

Worte, die in kleinerer Schrift gehalten sind, sind weniger wichtig

Die Textposition (siehe oben) für Worte in Auflistungen wird ignoriert

Diese Suchanfrage wird dann in einer standardisierten internen, formalen Form an die Schnittstellen (Information Adapters) der verschiedenen Quellsysteme gesendet. Diese Schnittstellen transformieren
das interne Format in das proprietäre Anfrageformat des jeweiligen
Quellsystems. Bei WATSON werden alle Anfragen "online" (keine
Vorberechnung) durchgeführt. WATSON hält selbst keine Informationen und ist damit auf die Verfügbarkeit der Quellsysteme angewiesen.
Die Anfragen liefern die Ergebnisse, die dann von WATSON auf Redundanz geprüft werden. Dazu vergleicht WATSON den Titel und
die URL der Ergebnisse und betrachtet zwei Texte als identisch,
wenn die Ähnlichkeit von Titel und URL einen bestimmten Schwellwert überschreitet.

125

sUppLex

4 Anwendungen

4.2.17 LIBRA
Bild 62:
LIBRA

Beim LIBRA [97]-Verfahren fußen die Empfehlungen auf Metadaten,
die von Amazon.com durch einen automatischen Extraktor (zu
LIBRA-Zeiten waren die Amazon-Webservices noch nicht verfügbar)
gewonnen werden. Die Metadaten, zu denen auch die CollaborativeDaten (ähnliche Bücher) von Amazon.com zählen, die aber in LIBRA
als "normaler" Content verwendet werden, werden komplett (kein
TF-IDF) als gewichteter Wortvektor implementiert.
Die Benutzer müssen zunächst eine Reihe von Büchern auf einer Skala von 1 bis 10 bewerten, um ein Profil zu bilden. Das Profil besteht

126

sUppLex

4.2 Content Based Filtering-Systeme
aus einem gewichteten Wortvektor. Zur Klassifikation kommt ein
leicht modifizierter Naiver Bayes-Klassifikator (NBK) zum Einsatz.

4.2.18 Margin Notes
Bild 63:
Margin Notes

In Margin Notes [98] werden zunächst Webseiten mittels Savant, einem TF-IDF-Derivat, in Wortvektoren transformiert. Dies erfolgt "offline" (vorberechnet), sobald die Webseiten verfügbar sind. Ruft der
Benutzer im Browser eine Webseite auf, so werden "online" (beim
angezeigten Text wird also nicht auf die Vorberechnung zurückgegriffen) mit Savant – einer von Rhodes und Jan Nelson entwickelten
Suchmaschine, die mit dem Okapi-Verfahren [99], [100] arbeitet – die
ähnlichsten Texte bestimmt. Dabei wird den Worten im ersten Absatz
des Textes mehr Relevanz zugesprochen (Textverlauf). Diese werden
dann in Form der 5 "relevantesten" Texte am rechten Rand (daher
"margin notes") in der Webseite eingebettet angezeigt (durch Um-

127

sUppLex

4 Anwendungen
schreiben des HTML-Codes auf einem Proxy-Server). Zu Evaluationszwecken wird außerdem eine Bewertung auf einer Skala von 1-5
ermöglicht, die aber nicht in die zukünftigen Empfehlungen einfließt.
Das Okapi Verfahren (in der Fassung von TREC-6, wie es von Margin
Notes verwendet wird) basiert auf einem TF-IDF-Derivat, das statt
der IDF die durchschnittliche Worthäufigkeit im Text selbst zur
Normalisierung heranzieht. Kürzere Dokumente werden bei Empfehlungen längeren Dokumenten vorgezogen.

4.2.19 Jimminy
Bild 64:
Jimminy

128

sUppLex

4.2 Content Based Filtering-Systeme
Mit Jimminy [101] dem Kürzel für Just-in-time information retrieval
agents hat Rhodes neben Margin Notes und dem Remembrance Agent
ein weiteres Content Based Filterung-Verfahren vorgestellt. Jimminy
ist allerdings bezüglich des zugrunde liegenden Content Based Filterung-Konzeptes identisch zum Remembrance Agent. Lediglich die
Benutzerschnittstelle (tragbare Sichtbrille und Tastatur) unterscheidet
sich. Das Verfahren ist dennoch interessant, da es einen Ausblick auf
die potenziellen Möglichkeiten kontextbasierter Empfehlungen im
„echten Leben“ gibt. Mehr Details zum Jimminy-Ansatz findet man
in Rhodes Patentschrift dazu [102].

4.2.20 SUITOR
Bild 65:
SUITOR

129

sUppLex

4 Anwendungen
Die Besonderheit des Content Based Filterung-Verfahrens SUITOR
[103] besteht darin, dass es einen sehr umfassenden Zugang zum
aktuellen Kontext des Benutzers sucht. So protokolliert es nicht nur
klassisch sein Verhalten im Web-Browser, sondern überwacht auch
seine Tastatureingaben und seinen Blickfokus durch eine entsprechende Hardware. Alle Analysemethoden liefern Text. Dieser wird
kontinuierlich in das Benutzerprofil übernommen. Und zwar in Form
eines TF-IDF-Derivates, das bedeutende Worte durch deren Häufigkeit selektiert. Verändert sich das Interesse eines Benutzers, wird
langsam – indem mehr und mehr Worte mit dem neuen Thema des
Interesses aufgenommen werden – auch das Profil verändert. Damit
Interessensänderungen schneller berücksichtigt werden können, partitioniert SUITOR das Benutzerprofil auf der Zeitachse in zwei Teile:
kurzfristiges Profil und langfristiges Profil. Über die Implementation
der Profile berichtet Maglio leider nicht. Aus dem Zusammenhang
lässt sich aber auf eine vektorbasierte Darstellung schließen.
SUITOR verwendet verschiedene Agenten. Die potenziell zu empfehlenden Texte werden durch Investigator Agents gesammelt. So genannte Reflector Agents bewerten dann die Texte im Hinblick auf die
Benutzerprofile. Ab einer bestimmten Überdeckung (vermutlich TFIDF-Derivat mit Cosinus-Ähnlichkeitsmaß; siehe "vektorbasiert" oben)
von Text und kurzfristigem oder langfristigem Profil wird eine Empfehlung ausgesprochen.

4.2.21 PRES
In PRES [104] werden Webseiten und Benutzerprofile durch gewichtete Wortvektoren repräsentiert. Jeder Benutzer besitzt ein Profil, das
implizit durch das Betrachten von Webseiten (mit einer Mindestlesedauer) gebildet wird. Der Wortvektor eines Textes wird durch ein TFIDF-Derivat gebildet. Die Relevanz eines Textes für einen bestimmten
Benutzer wird durch das Cosinus-Ähnlichkeitsmaß zwischen Text- und
Profil-Vektor bestimmt. Ein neuer Text wird in Form seines Wortvektors wie folgt in das Profil übernommen:
P'=P + D
Wobei P' das neue und P das alte Profil sowie D den Wortvektor des
neuen Textes repräsentieren. Durch D (ein Wert zwischen 0 und 1)
werden die Gewichte der bestehenden Worte im bestehenden Profil

130

sUppLex

4.2 Content Based Filtering-Systeme
mit jedem neuen Text verringert. Dadurch "verblassen" nicht mehr
frequentierte Worte nach und nach.

Bild 66: PRES

131

sUppLex

4 Anwendungen

4.2.22 WebSail
Bild 67:
WebSail

Das WebSail [105] Verfahren basiert auf Profilen, die aus einem gewichteten Wortvektor bestehen. Vom Benutzer bewertete Webseiten
verändern das Profil in Form binärer Wortvektoren, die durch ein TFIDF-Derivat gebildet werden. Die Bewertung der Webseiten durch
den Benutzer erfolgt zweiwertig in Form von "relevant (ja/nein)".
Angezeigt werden die zu bewertenden Webseiten bei WebSail allerdings nicht im Kontext anderer Webseiten, sondern in Form eines
Suchergebnisses, das dann mit WebSail iterativ durch Bewertungen
verfeinert wird. Die Profile sind daher flüchtig und nur während
einer Such-Iterationsschleife präsent. Auf Basis des TW2 [105], [106]

132

sUppLex

4.2 Content Based Filtering-Systeme
Algorithmus wird ein Wort pv im Wortvektor des Profils durch ein
Wort wV im Wortvektor einer positiv bewerteten Webseite (deren
Wortvektor mit einem TF-IDF-Derivat ermittelt wird) wie folgt beeinflusst (wobei für den Motivations- beziehungsweise Demotivationsfaktor mit >1 steht):
-

pv = wv, falls wv=0

pv =

, falls wv=1 und pv=0

pv =

*pv, falls wv=1 und pv>0

Bei einer negativ bewerteten Webseite gilt:
-

pv = pv/

Es wird also im Falle einer negativ bewerteten Webseite eine Abwertung des kompletten Profils vorgenommen. Die Empfehlung neuer
Webseiten basiert auf dem ebenfalls im Rahmen von TW2 (siehe
oben) vorgestellten Distanzmaß. Es handelt sich um das Skalarprodukt des Profil- und Webseiten-Wortvektors und damit um eine Abwandlung des Cosinus-Ähnlichkeitsmaßes.

4.2.23 WAIR
WAIR [107],[108] nutzt ein Benutzerprofil in Form eines gewichteten
Wortvektors. Zu Beginn gibt der Benutzer n Worte in Form einer
Suchanfrage ein und schafft somit ein implizites Basisprofil. Aufgrund der Worte im Benutzerprofil werden Anfragen an Standardsuchmaschinen gestellt. Die zurück gelieferten Webseiten transformiert das Verfahren dann mit einem TF-IDF-Derivat (ohne IDFKomponente, da WAIR keinen eigenen Index aufbaut) in binäre
Wortvektoren.
Die Relevanz einer Webseite wird wie folgt berechnet:
RT=6k=1…n tfk*wpk, falls kT
wobei k=1…n die Worte im Profilvektor, p=1…m die Profile des Benutzer und T der Text der Webseite sind. Die n relevantesten Webseiten (Maximalwerte Rt der in Frage kommenden Webseiten) werden
dem Benutzer dann vorgeschlagen.
Aufgrund des Verhaltens des Benutzers in Bezug auf die empfohlenen Webseiten wird das Benutzerprofil adaptiert. Dabei werden pro
Webseite protokolliert:
-

Lesedauer

133

sUppLex

4 Anwendungen
-

Setzen eines Bookmarks

Scrollen

Benutzen von Hyperlinks (in der Webseite)

Diese vier Parameter werden mit einem mehrstufigen neuronalen
Netz gewichtet. Ein Profil wird in Abhängigkeit vom Wert dieser vier
gewichteten Parameter angepasst. Dabei wird jedes Wort des Profilvektors erhöht, wenn die empfohlene Webseite es enthält, und erniedrigt, wenn es nicht enthalten ist. Der so angepasste gewichtete
Profilvektor wird verwendet, um m neue Worte für eine Suchanfrage
zu selektieren. Dabei sind - *m Worte solche mit den größten Gewichten und *m Worte zufällige aus dem Profil. Letzteres soll die
Flexibilität (Exploration) der Profile für Neues gewährleisten
Bild 68:
WAIR

134

sUppLex

4.2 Content Based Filtering-Systeme

4.2.24 Powerscout
Bild 69:
Powerscout

Das Powerscout [109]-Verfahren ist eine Weiterentwicklung von Letizia (siehe Seite 105). Statt einem Profil werden nun beliebig viele Profile angeboten. Ein Profil besteht weiterhin aus einem Wortvektor, in
dem allerdings zu jedem Wort zusätzlich hinterlegt ist, weshalb es
sich im Profil befindet.

135

sUppLex

4 Anwendungen
Gründe dafür können sein:
-

Die betrachtete Webseite, aus der das Wort ins Profil übernommen
wurde

Die Suchanfrage, die das Wort enthielt

Für die Selektion der Schlüsselworte eines Textes wird neben einem
TF-IDF-Derivat auch die Typographie und die Textposition ausgewertet. Der Benutzer entscheidet dann manuell, ob und zu welchem
Profil die Schlüsselworte des gerade betrachteten Texts hinzugefügt
werden sollen (Bewertung).
Powerscout analysiert nicht mehr die von der aktuellen Webseite aus
verlinkten Webseiten, sondern nutzt die Worte eines Profils als Anfrage an eine herkömmliche Suchmaschine. Die eingehenden Webseiten werden in Wortvektoren transformiert. Wenn diese zum zugehörigen Profil (aufgrund dessen die Anfrage gestellt wurde) nach dem
Cosinus-Ähnlichkeitsmaß eine bestimmte Nähe aufweisen, werden sie –
jeweils unter "ihrem" Profil – empfohlen.

4.2.25 CALVIN
CALVIN arbeitet [110], [111], [112] mit fallbasiertem Schließen (CaseBased Reasoning; CBR), indem es die Verwendung von Webseiten in
Kontexten protokolliert und auf Basis dieser Fälle diese Webseiten
später in ähnlichen Kontexten empfiehlt. Der Kontext besteht bei
CALVIN aus drei Bestandteilen: dem Task (eine vom Benutzer manuell angegebene Aufgabe in Form von Worten), mehreren Topics (ebenfalls vom Benutzer manuell in Form von Worten angegeben) und
schließlich den Webseiten (in Form automatisch auf Basis der Texte
ermittelter Schlüsselworte), die im Rahmen von Task und Topics betrachtet wurden. Die Webseiten werden dabei durch ein TF-IDFDerivat in einen Wortvektor mit maximaler Wortanzahl (einmal definiert) transformiert.
Die Fälle (Kontexte) werden zentral gespeichert und benutzerübergreifend verfügbar gemacht.
Eine CALVIN Sitzung muss nicht zwingend mit der manuellen Angabe von Task und Topic beginnen, da auch alleine durch Webseiten
ein Kontext aufgebaut wird, der mit der Fall-Basis verglichen werden
kann.

136

sUppLex

4.2 Content Based Filtering-Systeme
Erkennt CALVIN einen ähnlichen Kontext, so empfiehlt es nicht nur
die Webseiten, die im gespeicherten Fall (Kontext) zusätzlich betrachtet wurden, sondern zeigt auch den Weg (Clickstream; Folge von
Webseiten) zu dieser empfohlenen Webseite.
Ähnliche Kontexte werden mit dem Contrast Model of categorization
[113] ermittelt. Die Profile der Benutzer sind flüchtig, die Fälle werden ohne Benutzerbezug verwaltet.

Bild 70:
CALVIN

137

sUppLex

4 Anwendungen

4.2.26 WordSieve
Bild 71:
WordSieve

Das Grundprinzip von Wordsieve [114] besteht aus einem dreistufigen
"Sieb" (daher „WordSieve“), durch das die Worte aller Texte, die der
Nutzer betrachtet, geschickt werden.
Die erste Stufe bildet die prominentesten Worte im aktuellen Benutzerkontext ab. Dazu wird eine überschaubare Zahl an Knoten (konkret 150) mit den Werten "Wort" und Prominenz (sinngemäß Excitement) belegt. Mit jeweils 100 neu geprüften Worten verblasst (sinngemäß Decay) die Prominenz aller Knoten um den Wert b. Neue Worte
belegen solange die Knoten, bis alle belegt sind. Danach wird bei
Worten, die bereits einen Knoten belegen, deren Prominenz um einen

138

sUppLex

4.2 Content Based Filtering-Systeme
konstanten Wert erhöht (b/g). Einem neuen Wort, das noch keinen
Knoten besitzt, wird dann zufällig ein Knoten zugeordnet. Es übernimmt diesen dauerhaft mit der Zufallswahrscheinlichkeit von
0,0001*(Prominenz-100)2. Dabei steht Prominenz für die des Wortes,
das den Knoten derzeit belegt. Worte mit großer Prominenz werden
daher mit sehr geringer Wahrscheinlichkeit ersetzt. Da die Einstellung des Parameters g für die erste Stufe des Siebs essentiell ist, wird
es mit jedem neuen Wort, neu im Verhältnis zu den Knoten mit kumulierter Prominenz kalibriert.
Die zweite Stufe des Siebs besteht aus mehr Knoten (konkret 500), die
neben dem Wort und der Prominenz auch noch eine Aktivierungsstärke (sinngemäß Priming) besitzen. In diese zweite Stufe gelangen nur
Worte, die bereits Knoten in Stufe 1 belegen. Mit jedem neuen Wort
auf Stufe 1 wird ein kompletter "Lauf" für die Worte der Stufe 2
durchgeführt. Mit jedem "Lauf" werden die Prominenz und Aktivierungsstärke aller Knoten um einen festen Wert abgesenkt. Die Prominenz der Knoten auf Stufe 2 wächst mit jedem Lauf in dem das Wort
einen Knoten auf Stufe 1 besetzt hält. Das Wachstum ist dabei abhängig von der Aktivierungsstärke. Letztere wird dabei ebenfalls angehoben. Neue Worte ersetzen bestehende in Stufe 2 analog zum Verfahren auf Stufe 1. Die Stufe zwei bildet im Gegensatz zum "Kurzzeitgedächtnis" der Stufe 1 quasi ein "Langzeitgedächtnis".
Die dritte Stufe ist analog zur zweiten aufgebaut. Allerdings erhöht
sich hier die Prominenz erst dann, wenn ein Wort lange Zeit nicht
mehr in Stufe 1 existiert. Da klassische Stoppworte quasi immer existent sind, erreichen diese auf dieser Stufe keine hohe Prominenz.
Der gewichtete Wortvektor eines Textes wird mit WordSieve ermittelt,
indem das Dokument durch ein leeres Sieb der Stufe 1 läuft und die
Prominenz der Stufe 1 dann mit den korrespondieren Werten der
Knoten in Stufe 2 und 3 multipliziert wird (Heuristik). Der aktuelle
Kontext des Benutzers wird als gewichteter Wortvektor ebenfalls
durch Multiplikation der Prominenz der Stufe 1 mit den korrespondierenden Werten der Stufen 2 und 3 ermittelt. Die Ähnlichkeit eines
Textes zu einem Profil wird dann mittels des CosinusÄhnlichkeitsmaßes bestimmt.

139

sUppLex

4 Anwendungen

4.2.27 MetaMarker
Bild 72:
MetaMarker

Das MetaMarker [115]-Verfahren arbeitet auf E-Mails. Es erzeugt mittels NLP automatisiert Metadaten.
Dabei kommt folgende Heuristik zum Einsatz, die den Text wie angegeben "tagged":
–
–
–
–
–
–
–

Satz-Ermittlung (<s> … </s>)
Satzteil-Ermittlung ("laufen"|Verb)
Morphologie-Analyse ("laufen"|Verb|Wortwurzel="lauf")
Mehrwort-Begriffe (<pn>Müller,GmbH</pn>="Müller GmbH")
Begriffskategorisierung (<pn cat=Firma> Müller,GmbH</pn>)
Implizite Metadaten (beispielsweise "<urgency>" aus E-Mail-Status)
Benutzerpräferenz (<like>,<dislike>,<interested>,<not interested>)

140

sUppLex

4.2 Content Based Filtering-Systeme
Die Benutzerpräferenz wird anhand von Schlüsselworten in die vier
Werte like, dislike, interested beziehungsweise not interested transformiert und dann ins Benutzerprofil übernommen. Dem Benutzer werden dann Texte empfohlen, die Begriffe enthalten, die ihn interessieren oder die er gerne hat („like“), und die keine (oder verhältnismäßig wenig) Worte enthalten, die ihn nicht interessieren oder die er
nicht mag ("dislike"). Die Einschätzung erfolgt durch Klassifikation
des Wortvektors eines Textes in Bezug auf den Klassenvektor (Benutzerprofil).

4.2.28 WebTop
Bild 73:
WebTop

141

sUppLex

4 Anwendungen
WebTop [116], [117] empfiehlt dem Benutzer ähnliche Webseiten auf
Basis der gerade angezeigten Webseite. Dabei werden die bedeutenden Worte der aktuell angezeigten Webseite durch ein TF-IDFDerivat ermittelt. Diese Wortmenge wird dann als Anfrage für bestehende Suchmaschinen verwendet. Die zurück gelieferten Texte werden in Form von (Titel, Link)-Tupel angeboten (heuristisches Verfahren zur Bestimmung der Content-Distanz). Der Benutzer kann Empfehlungen als Edge Links markieren (explizite Profilbildung), die dann
dauerhaft – aber entfernbar – mit der angezeigten Webseite in seinem
Profil verbunden bleiben. Neben den Edge Links und den verwandten
Webseiten einer Webseite werden dem Benutzer noch die eingehenden und ausgehenden Hyperlinks der Webseite angezeigt.

4.2.29 INFOS
INFOS [118] arbeitet auf Newsgroup-Beiträgen. Der Benutzer kann
Beiträge als interessant, uninteressant und indifferent bewerten. Auf
Basis dieser Bewertungen kommen zwei Verfahren zum Einsatz. Das
Global Hill Climbing (GHC)-Modell greift die Naive Bayes-Klassifikation
(NBK) und TF-IDF auf und entwickelt daraus ein eigenes Verfahren.
Es speichert zu jedem Wort die Anzahl der seitens des Benutzers als
interessant (I(w)) und als uninteressant (U(w)) bewerteten Texte. Für
einen neuen Text T wird dann die Summe der Bewertungen der anschließend darin enthaltenen Worte gebildet und dann entschieden,
ob eine Empfehlung ausgesprochen wird:

¦ I (w )

¦ O( w )
i

i 1... T

¦U ( w )
i

i 1... T

¦ O(w )

! A empfehlen

i 1... T

mit O(w) als der Gesamtzahl der Instanzen von w in allen Texten und
A als Pufferzone (auf 0,15 gesetzt) zwischen empfehlen und nicht
empfehlen.
Wenn das Global Hill Climbing einen Beitrag nicht klassifizieren kann,
wird das Verfahren der Case Based Abstraction Hierarchy (eine Art des
Case Based Reasoning; CBR) verwendet. Es ist ein Modell, das die "Bedeutung" der Worte von Beiträgen für die Klassifikation verwendet.
Dazu werden die "bedeutenden" Worte der Texte als Schlüsselworte
extrahiert. Dafür kommen einige Heuristiken zum Einsatz. So werden
beispielsweise die ersten beiden und der letzte Satz eines Absatzes

142

sUppLex

4.2 Content Based Filtering-Systeme
sowie die Überschriften höher bewertet (Textstruktur). Und vorangegangene Signalworte wie "wichtig(es)" erhöhen die Relevanz eines
Wortes. Mittels WordNet werden auch die Synonyme eines Wortes
ermittelt. Auf Basis dieser Heuristiken werden dann die bedeutenden
Worte eines Textes selektiert und anschließend mit den bedeutenden
Worten der bereits abgelegten "Cases" (bereits bewertete Beiträge)
verglichen. Dabei wird auch auf die Hyperonym-Struktur von WordNet zurückgegriffen, um die Worte begrifflich einzuordnen. Schließlich werden die neuen Beiträge empfohlen, wenn sie eine hohe Übereinstimmung mit positiv bewerteten Beiträgen besitzen. Es werden
dem Benutzer auch die bestimmenden Eigenschaften (Worte) angezeigt, die zur Empfehlung geführt haben.
Bild 74: Infos

143

sUppLex

4 Anwendungen

4.3 Hybride Systeme
4.3.1 Fab
Bild 75: Fab

Das hybride Fab [119]-Verfahren nutzt Profile (Selection Agent genannt) in Form von Wortvektoren, die auf Basis der Bewertung von
Texten auf einer Skala von eins bis sieben mittels TF-IDF-Derivat generiert werden. Eine sehr gut bewertete Seite wird direkt ähnlichen
Benutzern empfohlen (Collaborative Filtering).
Ferner kommen sogenannte Collection Agents zum Einsatz, die auf
Basis der Profile vieler Benutzer generiert werden und dann neue
Texte sammeln und den Benutzern vorschlagen, deren Profile den
Texten über einen bestimmten Schwellwert ähneln (Content Based
Filterung; Cosinus-Ähnlichkeitsmaß). Es werden Benutzern auch Texte
vorgeschlagen, die zum Profil ähnlicher Benutzern (ermittelt durch
Nearest Neighbours Verfahren) passen. Collection Agents, deren Empfehlungen nicht ausreichend Resonanz finden, werden entfernt.

144

sUppLex

4.3 Hybride Systeme

4.3.2 PHOAKS
Bild 76:
PHOAKS

Beim PHOAKS [120] ("People Help One Another Know Stuff")-Verfahren
werden manuelle Links (URLs) in Einträgen aus Newsgroups als
positive Bewertung der verlinkten Webseite interpretiert. PHOAKS
verfolgt auf den ersten Blick einen Collaborative Filtering-Ansatz, da
Benutzer die News schreiben (Provider), die Empfehlungen für lesende Benutzer (Recipients) erzeugen.
Je mehr schreibende Benutzer den gleichen Link verwenden, desto
höher wird die verlinkte Webseite gewertet. Folglich gilt sie als relevanter für Benutzer, die die betreffende Newsgroup besuchen. Dass
die Links manuell gesetzt wurden, spricht sicher für die Einordnung
als Collaborative Filtering-Verfahren.
Bei PHOAKS erhält der Benutzer also nach Newsgroups gruppierte
Empfehlungen relevanter Webseiten. Welche Newsgroup den Benutzer interessiert, wählt er manuell, was quasi ein flüchtiges Profil darstellt.
Die Empfehlungen werden allerdings nach einem klassischen Content Based Filterung-Verfahren (Kategorie bestimmt Empfehlungen)
ermittelt. Daher wird PHOAKS als hybrides Verfahren eingeordnet.

145

sUppLex

4 Anwendungen
Ein Link wird nur dann "gewertet" (Heuristik zur Ermittlung der Eigenschaften eines Empfehlungselementes), wenn er folgende vier
Tests besteht:
-

die Nachricht, die den Link enthält, wurde nicht in verschiedene
Newsgroups gestellt (Annahme: sonst thematisch zu unpräzise)

der Link ist nicht Bestandteil der Benutzersignatur

der Link befindet sich nicht in einem zitierten Textbereich

die Worte im Umfeld des Links
o

deuten auf Empfehlung hin

deuten nicht auf Werbung oder Ankündigung hin

Da der Link die Bedeutung der Seite in Bezug auf die Kategorie
(flüchtiges Profil) bestimmt, liegt ein Distanzmaß mit heuristischem
Verfahren vor.

4.3.3 Let´s Browse
Bild 77: Let´s
Browse

Das Let´s Browse [121]-Verfahren ist eine Weiterentwicklung des Content Based Filterung-Verfahrens Letizia (siehe S. 105) um einen Collaborative Filtering-Ansatz. Anders als bei den meisten Collaborative
Filtering-Verfahren wird hier eine "physische" Benutzergruppe, die

146

sUppLex

4.3 Hybride Systeme
das gleiche Endgerät benutzt, betrachtet („Kiosk-System“). Die Benutzer werden dabei ohne Login – anhand eines persönlichen elektronischen Ausweises, der als Meme Tag bezeichnet wird – erkannt.
Die Benutzerprofile werden zunächst initialisiert, um das KaltstartProblem zu vermeiden. Die Initialisierung erfolgt durch die Analyse
einer "Start-Webseite" (einfaches explizites Strukturprofil) und durch
die Verfolgung der Links zu damit verbundenen Webseiten. Für
Letzteres wird ein Zeitlimit verwendet, so dass pro Benutzer zwischen zehn bis fünfzig Webseiten analysiert werden. Die Startseite ist
dabei die persönliche Webseite des Benutzers oder seines Unternehmens.
Die Analyse erfolgt mit einem TF-IDF-Derivat, um die bestimmenden
Worte der Webseiten zu ermitteln. Das Benutzerprofil wird als gewichteter Wortvektor verwaltet. Im Gegensatz zum reinen Content
Based Filterung-Verfahren Letizia werden beim Let´s BrowseVerfahren bis zu fünfzig Worte, statt zehn Worten pro Profil, verwaltet. Tests haben diese Zahl als erforderlich erscheinen lassen, um
verwandte Benutzer auch anhand weniger wichtiger Worte identifizieren zu können.
Die Empfehlungen werden auf Basis der Profile der derzeit im Einzugsbereich des Endgerätes befindlichen Benutzer ermittelt. Dazu
wird ein "gemeinsames Profil" (daher als benutzerbezogenes, speicherbasiertes Collaborative Filtering eingestuft) in Form einer einfachen Linearkombination der Wortvektoren ermittelt:
(g1,g2,g3,…,g50)
= (bI1+bII1+…+bN1, …, bIn+bIIn+…+bNn)
mit I,II,…,N als Benutzer.
Dann werden alle mit der aktuell angezeigten Seite verlinkten (und
bei genügend Analysezeit auch weitere Link-Ebenen) Webseiten in
Wortvektoren transformiert und mit dem Wortvektor des gemeinsamen Profils verglichen. Der Vergleich erfolgt durch das CosinusÄhnlichkeitsmaß der Vektoren. Es werden also die verlinkten Seiten
angezeigt, die dem gemeinsamen Profil der Benutzer am ähnlichsten
sind.

147

sUppLex

4 Anwendungen

4.3.4 CASMIR
Bild 78:
CASMIR

CASMIR [122] verwendet verschiedene Agenten, um Empfehlungen
zu ermitteln. Die Document Agents ermitteln aufgrund einer Anfrage
eines Search Agent die relevanten Texte ihres Textpools. Sie arbeiten
also ähnlich einer Suchmaschine. Dabei werden Anfrage und Text
mit einem TF-IDF-Derivat zu Wortvektoren transformiert. Die relevanten Texte werden dann mit dem Cosinus-Ähnlichkeitsmaß bestimmt.
Der Search Agent nimmt die Anfragen des Benutzers entgegen, selektiert die relevanten Dokumente durch Weitergabe der Anfrage an die
Document Agents und sortiert die gefundenen Dokumente dann nach
ihrer Relevanz.
Außerdem bestimmt er die wichtigsten Worte einer Anfrage und gibt
diese an den User Assistent weiter. Welche Worte das sind, bestimmt
der Search Agent auf Basis des Verhaltens des Anwenders. Worte, die
in mehr als einem Text, den der Benutzer im Suchergebnis wählt
(implizites positives Feedback), vorhanden sind, werden gewählt
und im Benutzerprofil aufgewertet. Worte, die in nicht selektierten
Texten vorkommen, werden abhängig von der Anzahl der Texte abgewertet (implizites negatives Feedback).
Der User Assistent verwaltet das Benutzerprofil in Form von gewichteten Wortvektoren. Er bestimmt welchem Wortvektor ("Interesse")

148

sUppLex

4.3 Hybride Systeme
die vom Search Agent ausgewählten Worte hinzugefügt werden.
Wenn der Benutzer nicht aktiv ist, führt der User Assistent automatisch Abfragen mit den am stärksten gewichteten Worten im Benutzerprofil durch.
Der User Agent arbeitet mit anderen User Agents zusammen. Wenn er
nach Ausführung einer Anfrage keinen passenden Wortvektor ("Interesse") findet, gibt er die Anfrage an andere User Agents weiter und
übernimmt einen, der von diesen angebotenen Wortvektoren ("Interesse"), als "Starthilfe". Wenn der Benutzer das System nicht benutzt,
sucht der User Agent verwandte Wortvektoren in anderen Benutzerprofilen und reichert seine Wortvektoren mit deren Worten an (Collaborative Filtering).

4.3.5 LaboUr
Bild 79:
LaboUr

Das LaboUr (Learning About the User) [123], [124], [125]-Verfahren
generiert aus dem impliziten Benutzerverhalten ein Benutzerprofil.
Wenn ein Benutzer aufeinander folgend Webseiten wählt, die das
gleiche Thema in Form eines Wortes behandeln, so wird dieses als
bedeutsam eingestuft. Formal erfolgt dies durch einen Naiven Bayes
Klassifikator (NBK), der den Text einem Profil zuordnet. Die Texte

149

sUppLex

4 Anwendungen
werden mit einem TF-IDF-Derivat (Wort vorhanden: ja/nein) analysiert und in Wortvektoren gewandelt. Immer wieder aufgerufene
Webseiten werden zusätzlich in absteigender Reihenfolge im Profil
verwaltet und dem Benutzer in einem Baum (erste Ebene: häufig
aufgerufen, zweite Ebene: weniger häufig aufgerufen) zur Verfügung
gestellt. Auf Basis des Benutzerprofils werden verwandte Benutzer
mit dem Korrelationskoeffizient (PC) gesucht.

4.3.6 Tango
Bild 80:
Tango

Das Tango-Verfahren [53] kombiniert Collaborative Filtering und
Content Based Filterung, um die Probleme "Kaltstart" und "Spärlichkeit" sowie sogenannte "Graue Schafe" (grey sheep) zu beseitigen.
Letzteres liegt vor, wenn ein Benutzer bezüglich seiner Bewertungen
zwar Profil-Überdeckungen mit anderen Benutzern hat, diese aber in
Sachen Bewertung so stark variieren, dass keine "verwandten" Benutzer selektiert werden können.
Tango wird von seinen Autoren als nicht hybrides Empfehlungssystem bezeichnet, da es die Verfahren des Collaborative Filtering und
Content Based Filterung autonom nutzt und deren Empfehlungen –
in Abhängigkeit von deren "Stärke" – dann in einem gewichteten

150

sUppLex

4.3 Hybride Systeme
Mittel zusammenführt. Durch den Einsatz beider Basiskonzepte wird
es dennoch in die Kategorie "Hybrid-Systeme" aufgenommen.
Der Benutzer meldet sich bei Tango an, um dann in einem Browser
Zeitungsartikel aufzurufen, zu lesen und zu bewerten. Außerdem
kann der Benutzer sein Profil bearbeiten.
Das Profil besteht aus einer Reihe fester Kategorien (News, Business
etc.), die der Benutzer explizit aus- und abwählen kann, sowie impliziten und expliziten Schlüsselworten. Beide sind einer Kategorie zugeordnet und Letztere als Freitext durch den Benutzer veränderbar.
Erstere werden aus den am besten bewerteten Artikeln (die besten
25%) gewonnen, wobei die Kategorie-Zuordnung implizit durch die
des Artikels erfolgt. Es sind manuelle Metadaten in Form der Kategorie am Artikel erforderlich. Die Auswahl der Kategorien kann der
Benutzer jederzeit treffen (explizites Strukturprofil).
Die Bewertung eines Artikels (Webseite) erfolgt auf einer Skala von
eins bis zehn mit einem "Schieberegler" und gibt an, mit welchem
Grad (10 = am höchsten) der Benutzer ähnliche Artikel wie diesen
lesen möchte.
Die Anzeige der empfohlenen Artikel erfolgt dann durch "Auszeichnung" der Artikel auf den durch normales Navigieren erreichten
Übersichtsseiten. Die Auszeichnung kann dabei wahlweise durch
Hervorhebung der empfehlenswerten Artikel mit "blauem Hintergrund" oder durch "Sterne" von 1 bis 5 (in Abhängigkeit von der
Stärke der Empfehlung) erfolgen. Zusätzlich zeigt Tango die 10 empfehlenswertesten, vom Benutzer noch nicht gelesenen Artikel an.
Der Collaborative Filtering-Teil von Tango arbeitet mit einem benutzerbezogenen Ansatz und bestimmt verwandte Benutzer mittels Korrelationskoeffizienten (PC).
Der Content Based Filterung Teil von Tango extrahiert die "relevanten"
Worte eines Artikels mit einem TF-IDF-Derivat (inklusive StoppwortEntfernung und Stemming). Deren Übereinstimmung zum Benutzerprofil (gleiche Kategorie wie der Artikel) wird dann mittels Overlap
Koeffizient (OK) bestimmt. Und zwar zum impliziten und expliziten
Wort-Profil. Anschließend werden die Übereinstimmungen dieser
beiden Profilarten und die Kategorie zu je einem Drittel in eine
durchschnittliche Gesamtbewertung eingebracht.
Aus dem Ergebnis des Collaborative Filtering und Content Based
Filterung wird dann eine Empfehlung in Form des gewichteten Mittels berechnet. Die Gewichtung wird dabei mit der vermeintlichen
Höhe der Genauigkeit des Ergebnisses korreliert. So wird das Collaborative Filtering abgewertet, wenn die Anzahl und/oder der Grad

151

sUppLex

4 Anwendungen
der Benutzerübereinstimmung gering ist. Das Content Based Filterung hingegen verliert an Bedeutung, wenn der Benutzer keine expliziten Schlüsselworte angegeben oder zu wenige Artikel gut bewertet
hat und daher keine impliziten Schlüsselworte genutzt werden können.

4.3.7 Nakif
Bild 81: Nakif

Beim hybriden Nakif [126]-Verfahren besitzen neben den Benutzern
auch die Empfehlungselemente (konkret Filme) eigene "Profile". Bei
näherer Betrachtung erweisen sich diese "Profile" aber als Kombination von "Wertungsspalten" (wobei evalhj die Wertung des Objektes h
durch Benutzer j ist) der Benutzer-Element-Matrix und einem einfachem Wortvektor (wobei ovechk für Wort k in Objekt h steht), der mit
einem TF-IDF-Derivat (aus dem Text der Filmbeschreibung) gebildet
wird. Die fünf ganzzahligen Wertungsoptionen liegen im Intervall [2,2].
Das Benutzerprofil wird durch eine Matrix repräsentiert. Diese besteht aus n Wortvektoren – für jeden Benutzer einen. Sei vij ein solcher Wortvektor für Benutzer j im Profil des Benutzers i. Dann gibt

152

sUppLex

4.3 Hybride Systeme
vij(w) an, wie genau Benutzer i und j bei der Bewertung von Texten
mit dem Wort w übereinstimmen.
Wie stark nun der Text des Empfehlungselementes h mit einem Benutzerprofil des Benutzers i übereinstimmt, wird dann wie folgt berechnet:
Match(i,h)= 6j=1…u 6k=1…s vij(wk) * evalhj * ovechk

mit u = Anzahl der Benutzer und s = Anzahl der Worte insgesamt.
Eine Ähnlichkeit zum Korrelationskoeffizienten (PC) ist zwar vorhanden, allerdings weicht der Ansatz aufgrund der "Wortwertungen"
statt der "Objektwertungen" doch erheblich ab. Daher wird das Vorgehen als Heuristik eingeordnet.

4.3.8 MovieLens
Bild 82:
MovieLens

Das MovieLens [127]-Verfahren empfiehlt Benutzern Filme und arbeitet als Hybridsystem mit mehreren Verfahren.

153

sUppLex

4 Anwendungen
Zum einen kommen mehrere so genannte IF Agents (Content Based
Filterung) zum Einsatz:
-

DoppelgaengerBots

RipperBot

GenreBots

Zum anderen werden diese Bots in das benutzerbezogene Collaborative Filtering wie Benutzer einbezogen. Letzteres basiert auf der
DBLens Recommendation Engine, die verwandte Benutzer mit dem
Pearson Korrelationskoeffizienten (PC) ermittelt.
Die DoppelgaengerBots basieren auf einem TF-IDF-Derivat und analysieren die Filmbeschreibung. Zunächst wird die IDF als log(N/O) gebildet, wobei N die Gesamtzahl der Filme und O die Zahl der Filme,
in denen ein Wort vorkommt, darstellen. Der TF-Anteil wird als binärer Vektor für das Vorkommen oder Nicht-Vorkommen eines Wortes
gebildet. Auf Basis der Filmbewertungen eines Benutzers wird dann
mit den TF-IDF-Werten ein Profil in Form eines Wortvektors gebildet.
Auf Basis des Skalarproduktes des Profilvektors und der TFVektoren der Filme werden dann Empfehlungen ausgesprochen. Es
handelt sich also um ein Derivat des Cosinus-Ähnlichkeitsmaßes.
Der RipperBots setzt den Regelgenerator Ripper [128] ein. Dieser basiert auf einer iterativen Regelerzeugung, die ineffiziente Regeln auf
Basis der Fehlerrate verwirft. Es wurden verschiedene RipperBots
durch unterschiedliche Trainingssets erzeugt.
Die GenreBots bewerten Filme in Abhängigkeit Ihres Genres, so dass
„Toy Story“ vom Kinderfilm-GenreBot beispielsweise "5" Punkte erhält. Wohingegen dieser GenreBot dem Film „The Shining“ keinen
Punkt gibt. Die GenreBots arbeiten auf manuellen Metadaten.
Dadurch, dass die Bots wie normale Benutzer in das benutzerbezogene
Collaborative Filtering-Verfahren einbezogen werden, werden klassische Probleme reiner Collaborative Filtering-Verfahren wie "Spärlichkeit" verhindert.

154

sUppLex

Literaturverzeichnis
[1]

Bush, V. (1945): As We May Think. - The Atlantic monthly, Juli
1945.

[2]

Oppenheimer, C. (1927): Die papierne Sintflut. - ChemikerZeitung 51 (24), S. 229-230, 1927.

[3]

Naisbitt, J. (1982): Megatrends: Ten New Directions Transforming Our Lives. - Warner Books, 1982, 290 S., New York,
United States, ISBN 0446512516, 1982.

[4]

Marx, W.; Gramm, G. (2002): Literaturflut - Informationslawine – Wissensexplosion. Wächst der Wissenschaft das Wissen
über den Kopf? - Arbeitspapier des Max-Planck-Institut für Festkörperforschung Stuttgart
(http://www.fkf.mpg.de/ivs/literaturflut.html), 2002

[5]

Luhn, H.P. (1958): A Business Intelligence System. – IBMJounal, Volume 2, Number 4, S. 314-319, October 1958

[6]

Lovins, J.B (1968): Development of a stemming algorithm. Mechanical Translation and Computational Linguistics, vol. 11, S.
22-31, 1968

[7]

Porter, M.F. (1980): An algorithm for suffix stripping. - New
models in probabilistic information retrieval, British Library Research and Development Report, no. 5587, chapter 6, 1980

[8]

Paice, C.D. (1994): An evaluation method for stemming algorithms. - Proceedings of the 17th annual international ACM SIGIR
conference on Research and development in information retrieval
table of contents, Dublin, Ireland, S.42-50, ISBN 038719889X,
1994

[9]

Hull, D.A (1996): Stemming Algorithms A Case Study for
Detailed Evaluation. - Journal of the American Society of Information Science, vol.47, no.1, S.70-84, 1996

[11]

Zipf, G.K. (1949): Human Bevavior and the Principle of Least
Effort. - Cambridge, MA, Adisson-Wesley, 1949

[12]

Heyer, G. (2005): Folien zur Vorlesung "Computerlinguistik".
" http://www.asv.informatik.uni-leipzig.de/opencms/export/sites/default/asv/downloads/Lehrmaterial/2008/
LI06_Zipf.pdf ", Stand August 2008

155

sUppLex

Literaturverzeichnis
[13]

Die Deutsche Bibliothek (2005): Normdaten-CD-ROM
(Sprachwortnormdatei „SWD“). - Die Deutsche Bibliothek, CDROM, 2005.

[14]

Firth, J.R. (1957): A synopsis of linguistic theory, 1930-1955. Palmer, F.R. (Herausgeber), Selected papers of J.R. Firth 19521959, Harlow: Longman, 1957

[15]

Wittgenstein, L., Schult, J. (1968): Philosophische Untersuchungen. - Suhrkamp, ISBN: 3518223720, 1968

[16]

Yarowsky, D. (1993): One sense per collocation.- In the Proceedings of ARPA Human Language Technology Workshop, 1993

[17]

Gale, W.A.; Church, K.W.; Yarowsky, D. (1993): A method for
disambiguating word senses in a large corpus. - Computers
and the Humanities, Vol.26, S. 415-439, 1993

[18]

Cleverdon, C.W. (1967): The Cranfield tests on index language devices. - Aslib Proceedings, 19, 6, S. 173-194

[19]

Hand, T.F. (1997): A proposal for task-based evaluation of text
summarization systems. - ACL/EACL-97 Workshop on Intelligent Scalable Text Summarization, Madrid, Spanien, S. 31-36,
1997

[20]

Voorhees, E. (2002): The Philosophy of Information Retrieval
Evaluation. - Proceedings of the 2nd Workshop of the CrossLanguage Evaluation Forum, CLEF 2001, Darmstadt, Germany,
2002

[21]

Turpin, A.H.; Hersh, W. (2001): Why batch and user evaluations do not give the same results. - Proceedings of the 24th
annual international ACM SIGIR conference on Research and development in information retrieval, S. 225-231, New Orleans, Louisiana, United States, 2001

[22]

Umlauf, K. (1998): Regeln für den Schlagwortkatalog (RSWK)
und Einführung in die Regeln für den Schlagwortkatalog
RSWK. - Berliner Handreichungen zur Bibliotheks- und Informationswissenschaft, ISSN 1438-7662, Heft 66, 1998

[23]

National Information Standards Organization (1997): Guidelines for Abstracts. – ANSI/NISO Z39.14-1997, Revision of ANSI
Z39.14-1979 (R1987), ISSN: 1041-5653, Approved November
27,1996 by the American National Standards Institute, 1997

[24]

Luhn, H.P. (1958): The Automatic Creation of Literature Abstracts. - IBM Journal, pages S. 159-165, 1958

[25]

Spärck-Jones, Karen (1972): A statistical interpretation of term

156

sUppLex

Literaturverzeichnis
specificity and its application in retrieval. - Journal of Documentaion, Vol. 28, S. 11-21, 1972
[26]

Wu, H.; Salton, G. (1981): A comparison of search term
weighting: term relevance vs. inverse document frequency. Proceedings of the 4th annual international ACM SIGIR conference
on Information storage and retrieval, S. 30-39, 1981

[27]

Church, K.W.; Hanks, P. (1989): Word Association Norms,
Mutual Information, and Lexicography. - Proceedings of the
27th. Annual Meeting of the Association for Computational Linguistics, Vancouver, B.C., Canada, S. 76-83, 1989

[28]

Meier, H. (1978): Deutsche Sprachstatistik. - Georg Olms Verlag, Hildesheim, Deutschland, ISBN 3487017695, 1978

[29]

- (2006): Wortschatz Lexikon der Universität Leipzig. http://wortschatz.uni-leipzig.de/index_js.html

[30]

Jorgensen, J. (1990): The Psychological Reality of Word
Senses. - Journal of Psychalinguistic Research, Vol.19, S.167-190,
1990

[31]

Veronis, J. (2001): Sense tagging: Does it make sense? - Corpus
Linguistics
2001,
Lancaster,
http://www.up.univmrs.fr/~veroni

[32]

Weaver, W. (1949): Translation. - Published in: Machine translation of languages: fourteen essays, Locke, W. N. et al.
(Herausgeber), Technology Press of the Massachusetts Institute
of Technology, Cambridge, Mass., and John Wiley & Sons,
Inc., New York, S.15 – 23, 1949

[33]

Luhn, H. P. (1957): A Statistical Approach to Mechanized
Encoding and Searching of Literary Information. - ZBM Journal of Research und Development, 1, No. 4, 309, 1957

[34]

Agirre, E.; Edmonds, P. (2007): Word Sense Disambiguation –
Algorithms and Applications. – Text, Speech and Language
Technoloy – Volume 33, Springer Science and Business Media,
ISBN: 978-1-4020-6870-6, 2007

[35]

Firth, J.R. (1957): Modes of Meaning. - Papers in Linguistics
1934-1951, Oxford University Press, S. 190-215, 1957

[36]

Benson, M. (1985): Collocations and idioms. - Ilson, R.
(Herausgeber), Dictionaries, lexicography and language learning,
Pergamon Press, S. 61-68, 1985

[37]

Hausmann, F.J. (1984): Wortschatzlernen ist Kollokationslernen. - Zum Lehren und Lernen französischer Wortverbindungen,

157

sUppLex

Literaturverzeichnis
Praxis des neusprachlichen Unterrichts, 31, , p. 395 – 406, 1984
[38]

Hausmann, F.J. (1989): Le dictionnaire de collocations. Hausmann, F. J. et al. (Herausgeber), Wörterbücher, Dictionaries,
Dictionnaires, erster Teilband. Berlin: de Gruyter 1989, S. 10101019.

[39]

Denhière, G.; Lemaire, B.; Bellissens, C.; Jhean, S. (2007): A
semantic space for modeling children's semantic memory. The handbook of Latent Semantic Analysis, Lawrence Erlbaum
Associates (Herausgeber), S. 143-165, 2007

[40]

Hoste, V.; Daelemans, W.; Hendrickx, I.; van den Bosch, A.
(2002): Dutch word sense disambiguation: optimizing the
localness of context. - Proceedings of the ACL-02 workshop on
Word sense disambiguation: recent successes and future directions Volume 8, S. 61-66, 2002

[41]

Bikel, Daniel M.; Miller, S.; Schwartz, R.; Weischedel, R.
(1997): Nymble: a High-Performance Learning Name-finder. Proceedings of the Conference on Applied Natural Language Processin, 1997

[42]

Asahara, Masayuki; Matsumoto, Y. (2003): Japanese Named
Entity Extraction with Redundant Morphological Analysis. Proceedings of the Human Language Technology conference - North
American chapter of the Association for Computational Linguistics,
2003

[43]

Sekine, Satoshi (1998): Nyu: Description of The Japanese NE
System Used For Met-2. - Proceedings of the Message Understanding Conference, 1998

[44]

Rau, Lisa F. (1991): Extracting Company Names from Text. Proceedings of the Conference on Artificial Intelligence Applications
of IEEE, 1991

[45]

Chomsky, N (1957): Syntactic Structures. - Mouton, Den Haag
1957, de Gruyter, Berlin/New York. ISBN 90-279-3385-5, 1957

[46]

Mustafa, S.H.; Al-Radaideh, Q.A. (2004): Using N-grams for
Arabic text searching. - Journal of the American Society for Information Science and Technology archive, Vol. 55 , Issue 11 (September 2004), S. 1002 – 1007, 2004

[47]

Deerwester, S.; Dumais, S. T.; Furnas, G. W.; Landauer, T. K.
(1990): Indexing by latent semantic analysis. - Journal of the
American Society for Information Science 41, 6, S. 391 – 407, 1990

[48]

Shardanand, U.; Maes, P. (1995): Social Information Filtering:

158

sUppLex

Literaturverzeichnis
Algorithms for Automating "Word of Mouth". - Proceedings of
ACM CHI'95 Conference on Human Factors in Computing Systems, S. 210-217, Denver, Colorado, UNITED STATES, 1995
[49]

Rucker, J.; Polanco, M.J. (1997): Siteseer: Personalized Navigation for the Web. - Communications of the ACM, vol. 40, no. 3, S.
73-75, 1997

[50]

Konstan, J.A.; Miller, B.N.; Maltz, D.; Herlocker, J.L.; Gordon,
L.R.; Riedl, J. (1997): Grouplens: Applying collaborative filtering to Usenet news. - Communications of the ACM, vol. 40, no. 3,
S. 77-87, 1997

[51]

Sarwar, B.; Karypis, G.; Konstan, J.; Riedl, J. (2001): Itembased collaborative filtering recommendation algorithms. Proceedings of the 10th international conference on World Wide
Web, Hong Kong, S. 285-295, ISBN 1581133480, 2001

[52]

Cover, T.M.; Hart, P.E. (1967): Nearest Neighbor Pattern Classification. - IEEE Transactions on Information Theory, vol. IT-IS,
no. 1, 1967

[53]

Claypool, M.; Gokhale, A.; Miranda, T.; Murnikov, P.; Netes,
D.; Sartin, M. (1999): Combining Content-Based and Collaborative Filters in an Online Newspaper. - Proceedings of ACM
SIGIR Workshop on Recommender Systems, Berkeley, UNITED
STATES, 1999

[54]

Melville, P.; Mooney, R.J.; Nagarajan, R. (2002): ContentBoosted Collaborative Filtering for Improved Recommendations. - Eighteenth national conference on Artificial intelligence,
Edmonton, Alberta, Canada, S. 187-192, ISBN 0262511290, 2002

[55]

Basilico, J.; Hofmann, T. (2004): Unifying collaborative and
content-based filtering. - Proceedings of the twenty-first international conference on Machine learning, Banff, Alberta, Canada, S. 9,
ISBN 1581138285, 2004

[56]

Rissanen, J. (1978): Modeling by shortest data description. Automatica, vol. 14, S. 465-471, 1978

[57]

(2005): Ockham's razor. - Encyclopaedia Britannica

[58]

Shannon, C.E. (1948): A Mathematical Theory of Communication. - Reprinted with corrections from The Bell System Technical
Journal, vol. 27, S. 379–423, 623–656, United States, 1948

[59]

Lang, K. (1995): News{W}eeder: learning to filter netnews. Proceedings of the 12th International Conference on Machine
Learning. Lake Tahoe, CA, UNITED STATES, 1995

159

sUppLex

Literaturverzeichnis
[60]

Cheng, J.; Greiner, R. (1999): Comparing Bayesian Network
Classifiers. - Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI-99), S. 101-108, Sweden, 1999

[61]

Cheng, J. (1997): Learning Belief Networks from Data: An
Information Theory Based Approach. - Proceedings of the Sixth
ACM International Conference on Information and Knowledge
Management, CIKM'97, 1997

[62]

Quinlan, J. R. (1986): Induction of Decision Trees. - Machine
Learning, vol. 1, no. 1, Kluwer Academic Publishers, 1986

[63]

MacKay, D.J.C. (2005): Information Theory, Inference, and
Learning Algorithms. - 640 Seiten, Cambridge University Press
2005

[64]

Goldberg, D.; Nichols, D.; Oki, B. M.; Terry, D. (1992): Using
collaborative filtering to weave an information tapestry. Communications of the ACM, vol. 35, no. 12, S. 61-70, 1992

[65]

Resnick, P.; Iacovou, N.; Suchak, M.; Bergstrom, P.; Riedl, J.
(1994): GroupLens: An Open Architecture for Collaborative
Filtering of Netnews. - Proceedings of ACM, Conference on Computer Supported Cooperative Work, S. 175-186, Chapel Hill, NC,
UNITED STATES, 1994

[66]

Goldberg, K.; Roeder, T.; Gupta, D.; Perkins, C. (2000): Eigentaste: A Constant Time Collaborative Filtering Algorithm. Information Retrieval, vol. 4, no. 2, Kluwer Academic Publishers, S.
133-151, 2001

[67]

Pearson, K. (1901): On lines and planes of closest fit to systems of points in space. - The London, Edinburgh and Dublin
Philosophical Magazine and Journal of Science, 6 (2), S. 559-572,
1901

[68]

Linden, G.D.; Smith, B.; York, J. (2003): Amazon.com Recommendations - Item-to-Item Collaborative Filtering. - IEEE
Internet Computing, vol. 7, no. 1, S. 76-80, 2003

[69]

Linden, G.D.; Jacobi, J.A.; Benson, E.A. (2001): Collaborative
recommendations using item-to-item similarity mappings. United States Patent 6.266.649, 2001

[70]

Fu, W.; Budzik, J.; Hammond, K.J. (2000): Mining Navigation
History for Recommendation. - In Proceedings of the international conference for intelligent user interfaces, S. 106-112, New
Orleans, Louisiana, United States, 2000

[71]

Miller, B.N.; Konstan, J.A.; Riedl, J. (2004): PocketLens: To-

160

sUppLex

Literaturverzeichnis
ward a personal recommender system. - ACM Transactions on
Information Systems (TOIS) archive, vol. 22, no. 3 (July 2004), S.
437-476, ISSN:1046-8188, 2004
[72]

Mobasher, A.; Dai, H.; Luo, T.; Nakagawa, M.; Witshire, J.
(2000): Discovery of Aggregate Usage Profiles for Web Personalization. - Proceedings of the WebKDD Workshop, 2000

[73]

Malone, T.W.; Grant, K.R.; Turbak, F.A. (1986): The information lens: an intelligent system for information sharing in
organizations. - Conference on Human Factors in Computing
Systems; Proceedings of the SIGCHI conference on Human factors
in computing systems table of contents, Boston, Massachusetts,
United States, 1986

[74]

Fischer, G.; Stevens, C. (1991): INFOSCOPE - Information
access in complex poorly structured information spaces. Conference on Human Factors in Computing Systems , Proceedings
of the SIGCHI conference on Human factors in computing systems:
Reaching through technology; New Orleans, Louisiana, United
States , S. 63–70, 1991

[75]

Lieberman, H. (1995): Letizia: An Agent That Assists Web
Browsing. - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), Morgan Kaufmann
publishers Inc, San Mateo, CA, United States, ISBN 1558603638,
S. 924-929, 1995

[76]

Armstrong, R.; Freitag,D.; Joachims,T; Mitchell,T (1995):
Webwatcher: A learning apprentice for the world wide web. AAAI Spring Symposium on Information Gathering from Heterogeneous, Distributed Environments, Stanford, United States, 1995

[77]

Joachims, T.; Mitchell, T.; Freitag, D.; Armstrong, R. (1995):
WebWatcher: Machine Learning and Hypertext. - AAAI
Spring Symposium on Information Gathering, 1995

[78]

Joachims, T.; Freitag, D.; Mitchell, T. (1997): WebWatcher: A
Tour Guide for the World Wide Web. - Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), Morgan
Kaufmann, 1997

[79]

Pazzani, M.; Muramatsu, J.; Billsus, D. (1996): Syskill & Webert: Identifying interesting web sites. - Proceedings of the
AAAI Spring Symposium on Machine Learning in Information
Access, Irvine, CA, United States, 1996

[80]

Rhodes, B.J.; Starner, T. (1996): The Remembrance Agent: A
Continuously Running Information Retrieval System. - Pro-

161

sUppLex

Literaturverzeichnis
ceedings of the First International Conference on Practical Applications of Intelligent Agents and Multi-Agent Technology, S. 486495, 1996
[81]

Rhodes, B.J.; Starner, T. (1999): Everyday-use Wearable Computers. - MIT Technical Report, 1999

[82]

Salton, G.; Lesk, M.E. (1965): The SMART automatic document retrieval systems—an illustration. - Communications of
the ACM, vol. 8, no. 6 (June 1965), S. 391-398, ISSN:0001-0782,
1965

[83]

Salton, G. (1971): The SMART Retrieval System - Experiments
in Automatic Document Processing. - Prentice-Hall, Inc. Upper
Saddle River, NJ, United States, 1971

[84]

Krulwosh, B.; Burkey, C. (1997): The InfoFinder Agent: Learning User Interests through Heuristic Phrase Extraction. - IEEE
Expert/Intelligent Systems & Their Applications, vol. 12, no. 5, S.
22-27, September/October, 1997

[85]

Moukas, A. (1997): Amalthaea: Information Discovery and
Filtering using a Multiagent Evolving Ecosystem. - Proceedings
of the Conference on Practical Applications of Agents and Multiagent Technology, 1996

[86]

Carr, L.A.; Hall, W.; Hitchcock, S. (1998): Link services or link
agents? - Proceedings of the ninth ACM conference on Hypertext
and hypermedia, Pittsburgh, Pennsylvania, United States, S. 113122, ISBN:0897919726, 1998

[87]

McCallum, A.; Nigam, K. (1998): Naive Bayes algorithm for
learning to classify text. - AAAI-98 Workshop on "Learning for
Text Categorization, Madison, Wisconsin, United States, 1998

[88]

Chen, L.; Sycara, K. (1998): WebMate: a personal agent for
browsing and searching. - Proceedings of the second international
conference on Autonomous agents table of contents, Minneapolis,
Minnesota, United States, S. 132-139, 1998

[89]

Balabanovic, M. (1998): Learning to Surf: Multiagent Systems
for Adaptive Web Page Recommendation. - PhD Thesis, Stanford University Department of Computer Science, completed March
1998

[90]

Green, S.J. (1998): Automated link generation: can we do better than term repetition? - Proceedings of the seventh international conference on World Wide Web 7, Brisbane, Australia, S. 7584, ISSN 01697552, 1998

162

sUppLex

Literaturverzeichnis
[91]

Fellbaum, C. (1998): WordNet. An electronic lexical database.
- Cambridge, MA: MIT Press; 422 Seiten, 1998

[92]

Billsus, D.; Pazzani, M.J. (1999): A Personal News Agent that
Talks, Learns and Explains. - Proceedings of the Third International Conference on Autonomous Agents, Seattle, Washington,
UNITED STATES, 1999

[93]

Yan, T.W.; Garcia-Molina, H. (1999): The SIFT Information
Dissemination System. - ACM Transactions on Database Systems, vol. 24, no. 4, S. 529-565, 1999

[94]

Budzik, J.; Hammond, K. (1999): Watson: Anticipating and
Contextualizing Information Needs. - Proceedings of the 62nd
Annual Meeting of the American Society for Information Science,
1999

[95]

Budzik, J.; Hammond, K.J. (2000): User Interactions with Everyday Applications as Context for Just-in-time Information
Access. - Proceedings of the International Conference on Intelligent
User Interfaces, New Orleans, Louisiana, United States, 2000

[96]

Budzik, J.;Hammond, K.J. (2003): Information access in context: experiences with the watson system. - Northwestern University Evanston, Illinois, USA, 2003

[97]

Mooney, R.J; Roy, L. (2000): Content-Based Book Recommending Using Learning for Text Categorization. - Proceedings of the fifth ACM conference on Digital libraries, S. 195-204,
San Antonio, Texas, United States, 2000

[98]

Rhodes, B.J. (2000): Margin Notes: Building a Contextually
Aware Associative Memory. - Proceedings of the International
Conference on Intelligent User Interfaces, S. 219-224, 2000

[99]

Robertson, S.E.; Walker, S.; Hancock-Beaulieu, M.; Gull, A.;
Lau, M. (1992): Okapi at TREC. - Proceedings of the first Text
REtrieval Conference (TREC-1), S. 21-30, Gaithersburg, Maryland,
United States, 1992

[100]

Walker, S.; Robertson, S.E.; Boughanem, M.; Jones, G.J.F.;
Sparck Jones, K. (1998): Okapi at TREC-6. - Proceedings of the
sixth Text Retrieval Conference (TREC-6), S. Gaithersburg, Maryland, United States, 1997

[101]

Rhodes, B.J.; Maes, P. (2000): Just-in-time information retrieval agents. - IBM Systems Journal archive, vol. 39, no. 3-4 , S.
685-704, ISSN:0018-8670, 2000

[102]

Rhodes, B.J. (2001): Method and apparatus for automated,

163

sUppLex

Literaturverzeichnis
context-dependent retrieval of information. - United States
Patent 6.236.768, 2001
[103]

Maglio, P.P.; Barrett, R.; Campbell, C.S.; Selker, T. (2000):
SUITOR: an attentive information system. - Proceedings of the
5th international conference on Intelligent user interfaces, New
Orleans, Louisiana, United States, S. 169-176, ISBN:1581131348,
2000

[104]

van Meteren, R.; van Someren, M. (2000): Using ContentBased Filtering for Recommendation. - University of Amsterdam, Netherlands, 2000

[105]

Chen, Z.; Meng, X. (2000): WebSail: From On-line Learning to
Web Search. - Web Information Systems Engineering, S. 206-213,
2000

[106]

Littlestone, N. (1987): Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm. - Machine Learning 2, S. 285-318, Kluwer Academic Publisher, Boston,
United States, 1988

[107]

Seo, Y.-W.; Zhang, B.-T. (2000): Personalized web-document
filtering using reinforcement learning. - Applied Artificial Intelligence, vol. 15, no. 7, S. 665-685, August 2001

[108]

Zhang, B.-T.; Seo, Y.-W. (2001): Personalized Web-Document
Filtering Using Reinforcement Learning. - Applied Artificial
Intelligence, vol. 15, no. 7, S. 665-68, 2001

[109]

Lieberman, H.; Fry, C.; Weitzman, L. (2001): Exploring the
Web with reconnaissance agents. - Communications of the ACM
archive, vol. 44 , no. 8 (August 2001), S. 69-75, ISSN:0001-0782,
2001

[110]

Bauer, T.; Leake, D.B. (2001): A Research Agent Architecture
for Real Time Data. - Fifth International Conference on Intelligent
Agents, Montreal, Canada, S. 61-66, 2001

[111]

Bauer, T.; Leake, D.B. (2002): Exploiting information access
patterns for context-based retrieval. - Proceedings of the 7th
international conference on Intelligent user interfaces, San Francisco, California, United States, Session: Short Papers, S. 176-177,
ISBN 1581134592, 2002

[112]

Leake, D.B.; Bauer, T.; Maguitman, A.; Wilson, D.C. (2000):
Capture, Storage and Reuse of Lessons about Information
Resources: Supporting Task-Based Information Search. - Proceedings of the AAAI-00 Workshop on Intelligent Lessons Learned

164

sUppLex

Literaturverzeichnis
Systems. AAAI Press, Menlo Park, 2000
[113]

Tversky, A. (1977): Features of Similarity. - Psychological Review, vol. 84, no. 4, S. 327-352, 1977

[114]

Bauer, T.; Leake, D.B. (2001): WordSieve: A Method for RealTime Context Extraction Collection and Analysis. - Lecture
Notes in Computer Science, vol. 2116, S. 30-43, 2001

[115]

Paik, W.; Yilmazel, S.; Brown, E.; Poulin, M.; Dubon, S.;
Amice, C. (2001): Applying natural language processing
(NLP) based metadata extraction to automatically acquire
user preferences. - Proceedings of the 1st international conference
on Knowledge capture, Victoria, British Columbia, Canada, S. 116122, ISBN 1581133804, 2001

[116]

Wolber, D.; Kepe, M.; Ranitovic, I. (2002): Exposing document
context in the personal web. - Proceedings of the 7th international conference on Intelligent user interfaces, San Francisco, California, United States, Session: Full Papers, S. 151-158, ISBN
1581134592, 2002

[117]

Wolber, D.; Brooks, C.H. (2004): Associative sources and
agents for zero-input publishing. - Proceedings of the 13th international World Wide Web conference on Alternate track papers
& posters, New York, NY, United States, Session: Posters, S. 494495, ISBN 1581139128, 2004

[118]

Mock, K.J. (1996): Intelligent Information Filtering via Hybrid
Techniques: Hill Climbing, Case-Based Reasoning, Index Patterns, and Genetic Algorithms. - Ph.D. thesis, University of
California Davis, United States, 1996

[119]

(1997): Fab - Content-Based, Collaborative Recommendation. Communications of the ACM, vol. 40, no. 3, S. 66-72, 1997

[120]

Terveen, L.; Hill, W.; Amento, B.; McDonald, D.; Creter, J.
(1997): PHOAKS – a system for sharing recommendations. Communications of the ACM, vol. 40, no. 3, S. 66-72, 1997

[121]

Lieberman, H.; van Dyke, N.W.; Vivacqua, A.S. (1998): Let's
browse: a collaborative Web browsing agent. - Proceedings of
the 4th international conference on Intelligent user interfaces, Los
Angeles, California, United States, S. 65-68, 1998

[122]

Berney, B.; Ferneley, E. (1999): CASMIR - a community of
software agents collaborating in order to retrieve multimedia
data. - Proceedings of the third annual conference on Autonomous
Agents, Seattle, Washington, United States, S. 428-429, 1999

165

sUppLex

Literaturverzeichnis
[123]

Pohl, W.; Nick, A. (1999): Machine learning and knowledge
representation in the LaboUr approach to user modelling. Proceedings of the seventh international conference on User modelling, Banff, Canada, S. 179-188, 1999

[124]

Pohl, W. (1997): LaboUr - Machine Learning for User Modeling. - Human-Computer Interaction, 1997

[125]

Pohl, W. (1996): Learning About the User – User Modeling
and Machine Learning. - In Proceedings of the ICML'96 Workshop Machine Learning meets Human-Computer Interaction, S. 2940,1996

[126]

Funakoshi, K.; Ohguro, T. (2001): Evaluation of integrated
content-based collaborative filtering. - ACM SIGIR Workshop
on Recommender Systems, New Orleans, UNITED STATES

[127]

Good, N.; Schafer, J.B.; Konstan, J.; Borchers, A.; Sarwar, B.;
Herlocker, J.; Riedl, J. (1999): Combining Collaborative Filtering with Personal Agents for Better Recommendations. - Proceedings of the 1999 Conference of the American Association of
Artificial Intelligence (AAAI-99), S. 439-446

[128]

Cohen, W.W. (1995): Fast Effective Rule Induction. - Proceedings of the 12th International Conference on Machine Learning, S.
115-123, Tahoe City, CA, United States, ISBN 1558603778, 1995

166

sUppLex

Abbildungsverzeichnis
Bild 1: Ein Empfehlungssystem selektiert aus der Menge möglicher
Entitäten eine Teilmenge, die es dem Benutzer empfiehlt ....................2
Bild 2: Differenzierung von Empfehlungssystemen anhand der
Typisierung der ausgesprochenen Empfehlungen.................................4
Bild 3: Kaufempfehlungen auf Basis von Produktverbindungen und
Kaufverhalten anderer Benutzer ...............................................................5
Bild 4: Shop-Empfehlungen auf Basis von Verbindung
redaktioneller Artikel zu Produkten.........................................................6
Bild 5: Text-Empfehlungen auf Basis von inhaltlicher Ähnlichkeit
zum angezeigten Artikeltext......................................................................7
Bild 6: Bild-Empfehlungen auf Basis der eigenen Bewertung und
der Ähnlichkeit zur Bewertung anderer Benutzer .................................8
Bild 7: Musik-Empfehlungen auf Basis der eigenen Bewertung und
der Ähnlichkeit zur Bewertung anderer Benutzer .................................9
Bild 8: Video-Empfehlungen auf Basis der Ähnlichkeit zu einem
gewählten Video........................................................................................10
Bild 9: Film-Empfehlungen auf Basis des Kaufverhaltens anderer
Benutzer......................................................................................................11
Bild 10: Film-Empfehlungen auf Basis der eigenen Bewertung und
der Ähnlichkeit zur Bewertung anderer Benutzer ...............................12
Bild 11: Empfehlungen zur Einschränkung des Suchfeldes................13
Bild 12: Empfehlungen auf Basis inhaltlicher und geografischer
Vorgaben auf Basis von Benutzerbewertungen ....................................14
Bild 13: Empfehlungen von Experten auf Basis der Autoren in
wissenschaftlichen Abhandlungen in geographischer
Visualisierung ............................................................................................15
Bild 14: Der Sputnik markierte nicht nur den Beginn der Raumfahrt,
sondern legte indirekt auch das Fundament für das Information
Retrieval und damit für die Empfehlungssysteme...............................17
Bild 15: Content Based Filtering-basierte Empfehlungssysteme –
Übersicht der zeitlichen Entwicklung ....................................................18
Bild 16: Collaborative Filtering-basierte Empfehlungssysteme –
Übersicht der zeitlichen Entwicklung ....................................................19

167

sUppLex

Abbildungsverzeichnis
Bild 17: Hybride Empfehlungssysteme - Übersicht der zeitlichen
Entwicklung ...............................................................................................20
Bild 18: Zipf´sches Gesetz – Schematisierter Zusammenhang von
Häufigkeit und Rang.................................................................................26
Bild 19: Korrelation von Rang und Häufigkeit nach Zipf´schem
Gesetz und in der deutschen Sprache (logarithmische
Achsenskalierung) aus [12] ......................................................................27
Bild 20: Beispielhafte Struktur einer Taxonomie..................................29
Bild 21: Beispielhafte Struktur eines Thesaurus ...................................29
Bild 22: Beispielhafte Struktur einer Topic Map ..................................30
Bild 23: Beispielhafte Struktur einer Ontologie ....................................31
Bild 24: Zwei Bedeutungen des Homographs „Aufnehmen“. ...........32
Bild 25: Polysemie kann durch Monosemierung aufgelöst werden;
einem Lexem (Wort) wird ein eindeutiges Semem (Bedeutung)
zugeordnet..................................................................................................35
Bild 26: Ein Beispiel für objektiv bewertbare Empfehlungen.............38
Bild 27: Die "Precision" ist das Verhältnis von relevanten zu
insgesamt empfohlenen Texten und "Recall" ist das Verhältnis von
empfohlenen relevanten Texten zu insgesamt relevanten Texten......40
Bild 28: Das TF-IDF-Verfahren bestimmt die wichtigsten Worte
eines Textes auf Basis statistischer Informationen................................44
Bild 29: Polysemie, Homonyme und Assoziationen durch
Synonyme ...................................................................................................48
Bild 30: Die CF-Matrix der Benutzer-EmpfehlungselementBeziehungen. ..............................................................................................62
Bild 31: Benutzerbezogenes Collaborative Filtering-Konzept............63
Bild 32: Elementbasiertes Collaborative Filtering-Konzept................64
Bild 33: Kriterien für d-separierte Knoten.............................................81
Bild 34: Ein Bayes´sches Netz im Aufbau .............................................82
Bild 35: Ein ID3 Entscheidungsbaum besteht aus Klassen (Blättern),
Attributen (inneren Knoten) und Attributwerten (Kanten). Aus dem
Entscheidungsbaum lassen sich Regeln für die Klassenzugehörigkeit
der Empfehlungselemente ableiten.........................................................83
Bild 36: Schematische Darstellung der Merkmale eines
Empfehlungssystems ................................................................................88
Bild 37: Tapestry .......................................................................................89

168

sUppLex

Abbildungsverzeichnis
Bild 38: Ringo ............................................................................................90
Bild 39: GroupLens...................................................................................92
Bild 40: Siteseer .........................................................................................93
Bild 41: Jester.............................................................................................94
Bild 42: Amazon........................................................................................95
Bild 43: SurfLen.........................................................................................96
Bild 44: PocketLens...................................................................................98
Bild 45: PACT..........................................................................................100
Bild 46: Information Lens ......................................................................102
Bild 47: Infoscope....................................................................................103
Bild 48: Newsweeder .............................................................................104
Bild 49: Letizia.........................................................................................106
Bild 50: WebWatcher..............................................................................107
Bild 51: Syskill & Webert .......................................................................109
Bild 52: Remembrance Agent................................................................110
Bild 53: InfoFinder..................................................................................111
Bild 54: Amalthaea .................................................................................113
Bild 55: AgentDLS ..................................................................................114
Bild 56: Webmate....................................................................................116
Bild 57: SLIDER.......................................................................................117
Bild 58: Lexical Chainer .........................................................................119
Bild 59: NewsDude.................................................................................121
Bild 60: SIFT ............................................................................................123
Bild 61: Watson .......................................................................................124
Bild 62: LIBRA.........................................................................................126
Bild 63: Margin Notes ............................................................................127
Bild 64: Jimminy .....................................................................................128
Bild 65: SUITOR......................................................................................129
Bild 66: PRES ...........................................................................................131
Bild 67: WebSail ......................................................................................132
Bild 68: WAIR..........................................................................................134
Bild 69: Powerscout................................................................................135

169

sUppLex

Abbildungsverzeichnis
Bild 70: CALVIN.....................................................................................137
Bild 71: WordSieve .................................................................................138
Bild 72: MetaMarker...............................................................................140
Bild 73: WebTop......................................................................................141
Bild 74: Infos............................................................................................143
Bild 75: Fab ..............................................................................................144
Bild 76: PHOAKS....................................................................................145
Bild 77: Let´s Browse ..............................................................................146
Bild 78: CASMIR .....................................................................................148
Bild 79: LaboUr .......................................................................................149
Bild 80: Tango..........................................................................................150
Bild 81: Nakif...........................................................................................152
Bild 82: MovieLens .................................................................................153

170

sUppLex

Stichwortverzeichnis
A
AgentDLS....................................114
Ähnlichkeit ........................39, 58, 68
Ähnlichkeitsmaß ............................71
Cosinus......................................71
Dice Koeffizient ........................73
Jaccard Koeffizient....................74
Overlap Koeffizient ...................73
Pearson Korrelationskoeffizient 72
Amalthaea....................................113
Amazon..........................................95
Antagonym ....................................36
Antonym ........................................36
Anwendungen ................................87
Anwendungsgebiete.........................4
Assoziation ..............................33, 50
Austrian Academy Corpus.............24

B
Bayes´sches Netz ...........................80
Bedeutung................................33, 48
eines Wortes ..............................33
Benutzerbewertung ........................23
Benutzerprofil ................................22
Brown Korpus................................23

C
CALVIN ......................................136
CASMIR......................................148
Clustering.......................................86
Collaborative Filtering...................62
benutzerbezogener Algorithmus 63
elementbasierter Algorithmus....64
modellbasiertes Verfahren.........65

Nachteile................................... 66
speicherbasiertes Verfahren ...... 65
Collaborative Filtering-Systeme.... 89
Content Based Filtering................. 42
Content Based Filtering-Systeme 102
Cookie ........................................... 21
Corpus ........................................... 23
Cosinus Ähnlichkeitsmaß.............. 71
Cranfield Experimente .................. 39

D
Dice Koeffizient ............................ 73
Disambiguierung ........................... 34
Distanzmaß.............................. 71, 75

E
Eigenschaftsanalyse ................ 23, 42
Empfehlungen
Qualitätsmaßstab....................... 37
Empfehlungselement....................... 1
Empfehlungssystem
Anwendungsgebiete
Audio...................................... 9
Bilder...................................... 8
Personen ............................... 15
Produkte ................................. 5
Prozesse................................ 13
Texte....................................... 7
Video .................................... 10
Entwicklungsgeschichte............ 16
Meilensteine.............................. 18
Euklidischer Abstand .................... 75

171

sUppLex

Stichwortverzeichnis

F
Fab............................................... 144
Feature Selection ..................... 23, 42
Flexionen....................................... 24

G
GermaNet ...................................... 24
GroupLens..................................... 92

H
Homograph.................................... 32
Homonym...................................... 32
Homophon..................................... 32
Hybride Systeme ......................... 144
Hybrid-Verfahren .......................... 68
Hyperlink ...................................... 21
Hyperonym.................................... 36
Hyponym....................................... 36

I
ID3 ................................................ 82
IDF (inverse document frequency) 44
Idiom ............................................. 27
Index
inverser ..................................... 25
InfoFinder.................................... 111
Information Retrieval ...................... 3
Informationsmenge........................ 16
INFOS ......................................... 142
Infoscope..................................... 103
Inverse Document Frequency........ 44

Jimminy ....................................... 128

K
Kaltstart-Problem .......................... 66
Kasus ............................................. 24
Klassifikationsverfahren ................ 77
Kollokation.............................. 28, 51
Kontext ...................................... 1, 22
Kookkurrenz .................................. 28
Korpus ........................................... 23
Test............................................ 39

L
LaboUr......................................... 149
Latent Semantic Indexing .............. 59
Lemming-Effekt ............................ 66
Lernmenge..................................... 23
Let´s Browse................................ 146
Letizia.......................................... 105
Lexeme .......................................... 24
LexicalChainer ............................ 119
LIBRA ......................................... 126
Linguistik....................................... 32
LOB Korpus .................................. 23
LSA ............................................... 59
Luhn, Hans-Peter ........................... 16

M
Margin Notes ............................... 127
Metadaten ...................................... 28
MetaMarker ................................. 140
Minimum Description Length ....... 77
Monosemierung............................. 34
MovieLens................................... 153
Mutual Information.................. 45, 75

Jaccard Koeffizient........................ 74
Jester ............................................. 94

172

sUppLex

Stichwortverzeichnis

Query Expansion............................. 3

Naiver Bayes-Klassifikator ............79
Nakif ............................................152
Named Entity Recognition.............52
Natural Language Processing.........54
Nearest Neighbours........................76
NER ...............................................52
NewsDude ...................................121
Newsweeder.................................104
N-Gramme .....................................55
NLP................................................54
Numerus.........................................24
Nützlichkeit....................................38
Nutzwertfunktion .............................1

Schlagwort .................................... 31
Schlagworte................................... 43
Schlagwortkatalog......................... 43
Schlüsselworte .............................. 42
Schweizer Text Korpus ................. 24
Selektionskriterium
Ähnlichkeit ............................... 68
Semantik ....................................... 32
Semem........................................... 34
Session .......................................... 21
SIFT ............................................ 122
Single Value Decomposition......... 60
Siteseer.......................................... 93
Situation ........................................ 23
SLIDER....................................... 117
Spärlichkeit ................................... 66
Sparsity ......................................... 66
Sputnikschock ............................... 17
Stemming ...................................... 24
Stichwörter.................................... 43
Stoppwort ...................................... 25
Suchanfrage................................... 22
Suchmaschine............................ 3, 22
Suchverfahren ................................. 3
SUITOR ...................................... 129
SurfLen ......................................... 96
SVD .............................................. 60

Ontologie .......................................31
Overlap Koeffizient .......................73
OWL ..............................................31

P
PACT ...........................................100
Part-Of-Speech-Tagging ................54
Pearson Korrelationskoeffizient.....72
Personalisierung...............................3
PHOAKS .....................................145
PocketLens.....................................98
Polysem .........................................33
Polysemie...........................34, 48, 51
POS-Tagging .................................54
Powerscout...................................135
Precision ........................................40
PRES............................................130
Profil ..............................................22

Q
Query .............................................22

Rang .............................................. 26
RDF............................................... 31
Recall ............................................ 40
Recommender System..................... 1
Referenzkorpus
Deutscher .................................. 24
Remembrance Agent ................... 110
Ringo............................................. 90

173

sUppLex

Stichwortverzeichnis
Synonym ....................................... 32
Syskill & Webert......................... 109

T
Tango .......................................... 150
Tapestry......................................... 89
Taxonomie .................................... 29
Tempus.......................................... 24
Term Frequency ............................ 44
Test-Korpora ................................. 39
TF (term frequency) ...................... 44
TF-IDF-Verfahren......................... 43
The Information Lens.................. 102
Thesaurus .......................... 29, 48, 49
Token ............................................ 27
Topic Map ..................................... 30
Trainingsdaten............................... 23

W
WAIR .......................................... 133
Watson......................................... 124
Webmate...................................... 116
WebSail ....................................... 132
WebTop ....................................... 141
WebWatcher ................................ 107
Word Sense Disambiguation ......... 49
WordNet ........................................ 23
WordSieve ................................... 138
Wörterbuch.............................. 48, 51
Wortschatz-Projekt ........................ 24
Wortvektor..................................... 24
WSD .............................................. 49

Z
Zipf
Gesetz........................................ 26

Vektor ........................................... 57

174

sUppLex