Empfehlungssysteme: Grundlagen, Konzepte und Systeme

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 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

IX

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

X

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

XI

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

K

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

1

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.

2

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.

3

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.

4

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

5

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

6

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.

7

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.

8

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.

9

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

10

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

11

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

12

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

13

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

14

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.

15

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-

16

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.

17

sUppLex

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

18

sUppLex

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

19

sUppLex

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

20

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

Cookie

Hyperlink

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

21

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.

22

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

23

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

24

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.

25

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 )

k

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-

26

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.

27

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 PW1 , W2 , Fn

Kollokation

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-

28

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

29

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

30

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.

31

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“.

32

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

33

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.

34

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])

35

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“.

36

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:

37

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.

38

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.

39

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.

40

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.

41

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.

42

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

43

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.

44

sUppLex

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

G Wn TF * IDF mit TF

N T 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ß

45

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:

pwi

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:

46

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

K

§ 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

wi

§ 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

47

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

48

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

49

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-

50

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]

51

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.

52

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.

53

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).

54

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.

55

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.

56

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  Ev D v  w Dv  Dw DE v D Ev 1v

v

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

57

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-

58

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

59

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

1

die

1

1 2

1

er

1

hat

1 1

in ist

1

1

1

1

1

1

1

kreisen

1

1

lief planet

1

planeten planetensystem

Text 6

1

der

im

Text 5

1 1

1

1

sah

1

sonne

1

1

stern

1

1

1

sterne

1 1

um

1

und

1

1

1 1

unser

1

unsere

1

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

60

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.

61

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.

62

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-

63

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-

64

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 I y , 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-

65

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

66

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.

67

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.“

68

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“

69

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)

70

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) =

=

¦

n

CosinusÄhnlichkeits maß

vxw v*w

v * wi

i 1 i

¦

n

2

v *

i 1 i

¦

n

i 1

wi

2

71

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) =

vˆw (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:

¦ v

Simpc(v,w) =

i 1...n

¦ v

i 1... n

i



 v * wi  w

¦ w  w 2

i

2

v *

i

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

72

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

i 1

ok

n

i 1

i

n

i

i 1

i

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) =

vˆw 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ß

73

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

2

2

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

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¦

n

n

i 1 n

i 1

i 1

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

74

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) =

vˆw v‰w

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) =

¦

n

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:

75

sUppLex

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

¦ ¦ n

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 biX 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 cX\{b1,...,bk). Bei Empfehlungssystemen sind die k nächsten Nachbarn die Empfehlungselemente oder Benutzer mit dem geringsten Abstand zu einem konkreten Empfehlungselement beziehungsweise Benutzer.

76

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 K i * p K i p D

umgeformt werden.

77

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 * pK i Ki

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

min  log p D K i * pK i Ki

œ min  log p D K i   log pK i Ki

œ min log pD K i  log pK 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

x

WD = binärer Wortvektor des Dokumentes D

x

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

x

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

x

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

78

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 * pK 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 * pK 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

79

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

k

k

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 K i

^D D  K

i

`

š 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= 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.

80

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.

81

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:

82

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:

83

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|tT š 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

84

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|tTšA=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 K i

^t t  K ` ^t t  T ` i

und

p A WAJ i

^t t  T š WAJ ^t t  T `

i

 t`

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

85

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)

86

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

1

4

1

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

2

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.

3

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

4

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

87

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

5

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

88

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.

89

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

90

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) =

¦v

i 1... n

¦ v

 2

i

 v * wi  w

2

¦ w  w 2

i

i 1... n

2

v *

i

i 1... n

die folgende Variante verwendet:

Distanz(v,w) =

¦ v

 4 * wi  4 2

i

2

i 1... n

¦ v

i 1... n

 4 * 2

i

¦ w

i



 4

2

i 1... n

91

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.

92

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ß).

93

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)

94

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

95

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.

96

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

97

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:

98

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.

99

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  p , c * cosTransaktion, c t Schwellwert i

j

j

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 kT 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> … ) Satzteil-Ermittlung ("laufen"|Verb) Morphologie-Analyse ("laufen"|Verb|Wortwurzel="lauf") Mehrwort-Begriffe (Müller,GmbH="Müller GmbH") Begriffskategorisierung ( Müller,GmbH) Implizite Metadaten (beispielsweise "" aus E-Mail-Status) Benutzerpräferenz (,,,<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

i 1... T



i 1... T

¦ O(w )

! A Ÿ empfehlen

i

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

o

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

J

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

N

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

R

O

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

S

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

V

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