Unterstützung des Ressourcen-basierten Lernens in Online Communities - Automatische Erstellung von Großtaxonomien in verschiedenen Sprachen

UNTERSTÜTZUNG DES RESSOURCEN-BASIERTEN LERNENS IN ONLINE COMMUNITIES– AUTOMATISCHE ERSTELLUNG VON GROSSTAXONOMIEN IN VERSCHIEDENEN SPRACHEN Vom Fachbereich Elektrotechnik und Informationstechnik der Technischen Universität Darmstadt zur Erlangung des akademischen Grades eines Doktor-Ingenieurs (Dr.-Ing.) genehmigte Dissertation von dipl.-inform.renato domínguez garcía Geboren am 17. September 1982 in San José, Costa Rica Referent: Prof. Dr.-Ing. Ralf Steinmetz Korreferent: Prof. Dr.-Ing Ulrik Schroeder Tag der Einreichung: 07. Dezember 2012 Tag der Disputation: 04. Februar 2013 Hochschulkennziffer D17 Darmstadt 2013 KURZFASSUNG Die sich stetig verändernden beruflichen Rahmenbedingungen und die immer kürzer werdende Gültigkeit einmal erworbenen Wissens verlangen flexible Formen des Wissensund Kompetenzerwerbs. Das in Bildungseinrichtungen angeeignete Wissen reicht nicht mehr ein Leben lang. Vielmehr besteht insbesondere im Arbeitsprozess zunehmend die Notwendigkeit, sich abhängig von der konkreten Problemstellung situativ Wissen anzueignen. Man spricht von selbstgesteuertem Lernen, da Lernende für ihre Lernbzw. Wissenserwerbsprozesse selbst verantwortlich sind. Gleichzeitig hat sich das World Wide Web zu einer der wichtigsten Quellen beim Wissenserwerb entwickelt. Das selbstgesteuerte Lernen mit Hilfe von Ressourcen aus dem Internet wird auch Ressourcen-basiertes Lernen bezeichnet. Eine der größten Herausforderung im Ressourcen-basierten Lernen ist es, relevante Web-Ressourcen im Web zu finden. Suchmaschinen werden sehr häufig verwendet, liefern aber praktisch keine Hilfestellung bei der Auswahl und Beurteilung gefundener Ressourcen. Empfehlungssysteme (engl. Recommender Systems) können grundsätzlich hilfreich sein, um für die jeweilige Situation und den jeweiligen Lernenden relevanten Ressourcen zu finden. Lernende können davon profitieren, dass sie auf Wissensressourcen hingewiesen werden, die andere Lernende, die einen ähnlichen Wissensbedarf besitzen, verwendet haben. In größeren Gruppen oder in einer Community sind für die eigene Lernaufgabe relevante Ressourcen mit hoher Wahrscheinlichkeit bereits von anderen Personen gefunden worden. Ziel dieser Arbeit war es, das Ressourcen-basierte Lernen innerhalb einer Community von Lernenden zu unterstützen, indem Lernende situationsbezogen auf Wissensressourcen hingewiesen werden, die andere Community-Mitglieder bereits verwendet haben. Zur Erreichung dieses Ziels wurde das Anwendungsszenario am Beispiel der CROKODIL-Plattform, eine Plattform zur Unterstützung des Ressourcen-basierten Lernens, untersucht. Die Untersuchung ergab, dass Benutzer oftmals nicht auf interessante Ressourcen hingewiesen werden können, wenn sie unterschiedliche Terminologien bei der Verschlagwortung von beim Lernen genutzten Ressourcen verwenden. Basierend auf dieser Feststellung wurde ein Konzept entwickelt, welches die Lücken in den von den Benutzern verwendeten Terminologien mittels der Verwendung einer Taxonomie schließt. Die Analyse ergab weiterhin, dass das Anwendungsszenario dadurch gekennzeichnet ist, dass die Benutzer aktuelle Begriffe in mehreren Sprachen als Schlagworte verwenden. Taxonomien, die diese Schlagworte in Beziehung zueinander setzen wollen, müssen daher dadurch charakterisiert sein, dass sie sehr aktuell sind und im mehreren Sprachen vorliegen. Diese Anforderungen können von existierenden manuell erzeugten Taxonomien nicht erfüllt werden. Daher wurden in der Arbeit mit TaxWikiHeur.KOM und TaxWikiML.KOM zwei Verfahren konzipiert und implementiert, die weitestgehend sprachunabhängig aus der Online Enzyklopädie Wikipedia Taxonomien generieren, indem sie Kategorienpaare aus der Wikipedia in Hyponymieund Nicht-Hyponymiebeziehungen klassifizieren. Diese Verfahren zeichnen sich dadurch aus, dass sie keine externen, manuell erzeug- ten Wissensbasen verwenden. Damit besteht keine Notwendigkeit einer manuellen Pflege von Taxonomien für neue Wissensbereiche. Das Verfahren TaxWikiML.KOM erweitert das Verfahren TaxWikiHeur.KOM und behebt einige der bei der Evaluation von TaxWikiHeur.KOM erkannten Mängel. Die Evaluation der Verfahren hat insgesamt gezeigt, dass trotz des Verzichtes auf eine externe Wissensbasis die Güte der Taxonomien sehr gut ist. Die Verwendung der Verfahren erfolgte in fünf Sprachen, so dass der Nachweis der sprachunabhängigen Nutzbarkeit ebenfalls erfolgte. Das Verfahren TaxWikiML.KOM wurde in der Arbeit weiterhin verwendet, um innerhalb der CROKODIL-Lernumgebung automatisch Beziehungen zwischen von den Benutzern verwendeten Schlagworten zur Beschreibung der im Lernprozess genutzten Ressourcen zu ergänzen. Es konnte zum einen anhand dreier Korpora aus dem Anwendungsfeld der Ressourcen-basierten Lernens nachgewiesen werden, dass die Dichte des semantischen Netzes, die zur Speicherung der Daten (Ressourcen, Tags und Benutzer) benutzt wird, durch das implementierte Konzept größer wird, womit Empfehlungssysteme umfangreichere Informationen zur Generierung von Empfehlungen zur Verfügung stehen, die auch solche Ressourcen anderer Lernender empfehlen können, die mit einer unterschiedlichen Terminologie beschrieben sind. Der positive Einfluss von mittels TaxWikiML.KOM ergänzten Hyponymiebeziehungen zwischen Schlagworten auf die Güte von Empfehlungssystemen wurde in einer weiteren Evaluation anhand des State-of-the-Art Verfahrens FolkRank zusätzlich nachgewiesen. Schließlich wurde das FReSET-Tool zur Evaluation von Empfehlungssystemen entwickelt. Das Tool wurde bereits in verschiedenen Arbeiten zur Evaluation verwendet, da es einen standardisierten Vergleich von Empfehlungssystemen ermöglicht. ABSTRACT Due to constantly changing professional environments and the decrease in the half-life of acquired knowledge, flexible forms of knowledge and skills acquisition are required. Nowadays, the knowledge acquired in educational institutions no longer last a lifetime. Rather, there is an increasing need (especially in work processes) for the personal acquisition of knowledge depending on specific tasks. This is called self-directed learning, as learners are responsible for their learning processes. At the same time, the World Wide Web has become one of the most important sources for knowledge acquisition. Self-directed learning using resources from the Internet is also called resource-based learning. One of the biggest challenges in resource-based learning is finding relevant web resources on the Web. Search engines are very often used for this purpose, but they do not provide assistance in the selection of found resources. Recommender systems can be helpful to find relevant resources. Learners can benefit from resources that other learners with similar knowledge requirements have already found. In larger groups or in a community, there is a high probability that relevant resources have already been found by other people. The goal of this thesis is to support resource-based learning within a community of learners by recommending knowledge resources that other community members have already found. To achieve this objective, the application scenario and an example implementation, CROKODIL, were investigated. The investigation revealed that the recommendation of interesting resources is often impossible, if the users use different terminologies for the tagging of resources. Based on this observation, a concept was developed that fills the gaps in the terminology used by the users through the use of a taxonomy. The analysis also reveals that the application scenario is characterized by current terms in multiple languages which are used as tags. A taxonomy used for the purpose of finding relationships between tags must, therefore, be characterized by the fact that it is up-to-date and available in multiple languages. These characteristics make manually created taxonomies unsuitable. Therefore, two approaches, TaxWikiHeur.KOM and TaxWikiML.KOM, were designed and implemented in order to generate large-scale taxonomies from the online encyclopedia Wikipedia in multiple languages. This is done by classifying pairs of categories from the Wikipedia in hyponymy and non-hyponymy relationships. These methods are characterized by the fact that they do not use external, manually created knowledge bases. Thus there is no need for the manual maintenance of taxonomies for new knowledge fields. TaxWikiML.KOM extends TaxWikiHeur.KOM and fixes some of the recognized shortcomings in the evaluation of TaxWikiHeur.KOM. The evaluation of the whole process has shown that even if no external knowledge base was used, the quality of the taxonomies was still very good. The approaches were evaluated in five different languages, in order to show the language-independency of the approaches. TaxWikiML.KOM was also used within CROKODIL to complement automatically generated relations between tags used by the users to describe the resources in their learning processes. Based on three corpora obtained from the application scenario, the evaluation could show that the density of the network grew using the implemented concept. Therefore, recommender systems have more information available to generate recommendations and this can be used for recommendations to learners using different terminologies. Additionally, the positive effect on the quality of recommender systems due to hyponymy relations between tags found by TaxWikiML.KOM was demonstrated in a further evaluation based on a state-of-the-Art algorithm. Finally, the FReSET tool for the evaluation of recommender systems was developed. FReSET can be used for the evaluation of recommender systems as it allows a standardized and thus comparable evaluation of recommender systems. INHALTSVERZEICHNIS 1 einführung 1 1.1Motivation................................... 1 1.2Ziel, Ansatz und Beiträge der Arbeit . . . . . . . . . . . . . . . . . . . . 2 1.3GliederungderArbeit ............................ 3 2 grundlagen 5 2.1Ressourcen-basiertes Lernen und Lernressourcen . . . . . . . . . . . . 5 2.2Information Retrieval und Maschinelles Lernen . . . . . . . . . . . . . 8 2.2.1InformationRetrieval ........................ 8 2.2.2MaschinellesLernen......................... 10 2.2.3Evaluationsmaße........................... 10 2.2.4Evaluationsverfahren......................... 12 2.3Wissensrepräsentation ............................ 13 2.3.1Begriffe................................. 13 2.3.2Konzepte................................ 13 2.3.3Relationen zwischen Konzepten . . . . . . . . . . . . . . . . . . 14 2.3.4Taxonomien.............................. 14 2.3.5Thesauri................................ 16 2.3.6Ontologien............................... 17 2.3.7SemantischeNetze.......................... 18 2.3.8Folksonomien............................. 19 2.4Wikipedia ................................... 19 2.4.1DasProjektWikipedia........................ 20 2.4.2StrukturderWikipedia ....................... 20 3 verwandte arbeiten 27 3.1Verwandte Arbeiten im Bereich Empfehlungssysteme . . . . . . . . . . 27 3.1.1Grundlagen zu Empfehlungssystemen . . . . . . . . . . . . . . 27 3.1.2Empfehlungssysteme im E-Learning . . . . . . . . . . . . . . . . 30 3.2Verwandte Arbeiten im Bereich Wissensextraktion . . . . . . . . . . . . 33 3.2.1Manuell erstellte Wissensbasen . . . . . . . . . . . . . . . . . . . 33 3.2.2Automatische Extraktion von Wissensbasen . . . . . . . . . . . 34 3.2.3Automatische Extraktion von Wissensbasen aus Wikipedia . . 37 3.2.4Diskussion und Einordnung dieser Arbeit . . . . . . . . . . . . 40 4 unterstützung des kollaborativen ressourcen - basierten lernens in online communities 43 4.1Analyse des Anwendungsszenarios und die CROKODIL-Plattform . . 43 4.1.1Ziele der Entwicklung der CROKDODIL-Lernumgebung . . . 43 4.1.2Funktionalitäten der CROKODIL-Plattform . . . . . . . . . . . 44 4.1.3Das CROKODIL-Datenmodell . . . . . . . . . . . . . . . . . . . 47 4.1.4 Analyse der Eigenschaften des Ressourcen-basierten Lernens in OnlineCommunities......................... 48 vii viii inhaltsverzeichnis 4.1.5 Herausforderungen bei der Nutzung von Ressourcen der Community................................. 49 4.2 Konzept zur Steigerung der Zugreifbarkeit auf Ressourcen im Ressourcenbasierten Lernen in Online Communities durch die Verwendung von Taxonomien .................................. 52 4.2.1 Empfehlung von Ressourcen auf Basis hyponymischer Beziehungen................................. 52 4.2.2 Anforderungen an eine Taxonomie zur Ergänzung hyponymischerBeziehungen .......................... 53 4.3Zusammenfassung .............................. 54 5 erkennung von hyponymien in verschiedenen sprachen 55 5.1Erkennung von Hyponymien auf Basis von Heuristiken . . . . . . . . 55 5.1.1Workflow ............................... 55 5.1.2Einzelne Schritte des Algorithmus im Detail . . . . . . . . . . . 56 5.1.3Sprachunabhängigkeit des Verfahrens . . . . . . . . . . . . . . . 65 5.1.4Evaluation des Verfahrens . . . . . . . . . . . . . . . . . . . . . . 66 5.1.5Zusammenfassung.......................... 71 5.2Erkennung von Hyponymien auf Basis von Entscheidungsbäumen . . 71 5.2.1Features ................................ 71 5.2.2Sprachunabhängigkeit des Verfahrens . . . . . . . . . . . . . . . 79 5.2.3Evaluation des Verfahrens . . . . . . . . . . . . . . . . . . . . . . 79 5.3Zusammenfassung .............................. 86 6 implementierung und proof-of-concept 89 6.1CROKODIL-Komponenten und erweiterte Architektur . . . . . . . . . 89 6.1.1CROKODIL-Komponenten . . . . . . . . . . . . . . . . . . . . . 90 6.1.2Die Taxonomiedatenbank . . . . . . . . . . . . . . . . . . . . . . 92 6.2Erweiterung des Datenmodells und Realisierung von Empfehlungen . 93 6.2.1Erweiterung des Datenmodells . . . . . . . . . . . . . . . . . . . 93 6.2.2Generierung von Empfehlungen . . . . . . . . . . . . . . . . . . 94 6.3CrokTaxTools ................................. 97 6.3.1Architektur von CrokTaxTools . . . . . . . . . . . . . . . . . . . 97 6.3.2Funktionsweise............................ 98 6.4Zusammenfassung .............................. 100 7 evaluation der nutzung der taxonomie im anwendungsszenario 101 7.1Grundlagen der Evaluation von Empfehlungssystemen . . . . . . . . . 101 7.1.1Evaluation mit historischen Daten . . . . . . . . . . . . . . . . . 101 7.1.2Benutzerevaluationen ........................ 102 7.1.3Fazit .................................. 103 7.2Ziele und Evaluationsmethodik . . . . . . . . . . . . . . . . . . . . . . . 103 7.2.1Auswahl und Erzeugung der Korpora . . . . . . . . . . . . . . . 105 7.2.2Verwendete Algorithmen und Tools . . . . . . . . . . . . . . . . 106 7.3Ergebnisse ................................... 108 7.3.1Evaluation bzgl. der Dichte des semantischen Netzes . . . . . . 109 7.3.2Empfehlungen anhand eines Empfehlungssystems . . . . . . . 110 inhaltsverzeichnis ix 7.4FazitundDiskussion............................. 113 8 zusammenfassung und ausblick 115 8.1Zusammenfassung und Beiträge der Arbeit . . . . . . . . . . . . . . . . 115 8.2Ausblick .................................... 116 literaturverzeichnis 119 abbildungsverzeichnis 133 tabellenverzeichnis 135 abkürzungsverzeichnis 138 a anhang 139 a.1Details zu TaxWikiHeur.KOM . . . . . . . . . . . . . . . . . . . . . . . . 139 a.1.1Parametrisierung der Heuristiken für die deutsche Sprache . . 139 a.1.2Ergebnisse von TaxWikiHeur.KOM in anderen Sprachen . . . . 140 a.2DetailszuTaxWikiML.KOM......................... 144 a.2.1 Klassifizierungsergebnisse basierend auf der englischen Wikipedia 144 a.2.2 Klassifizierungsergebnisse basierend auf der deutschen Wikipedia 145 a.3 Details zur Evaluation der Nutzung der Taxonomie im Anwendungsszenario..................................... 147 a.3.1Weitere Details zu den in der Evaluation verwendeten Korpora 147 a.3.2 Weitere Details zu Ausführung von FolkRank auf die verwendetenKorpora............................. 150 b wissenschaftliche arbeiten des autors 159 b.1Veröffentlichungen als Erstautor . . . . . . . . . . . . . . . . . . . . . . 159 b.2Mitautorenschaft und sonstige Veröffentlichungen . . . . . . . . . . . . 160 c curriculum vitæ 163 d betreute studentische abschlussarbeiten 165 e erklärung laut §9 der promotionsordnung 167 6 grundlagen allem auf Hypertextumgebung und Internetressourcen und erwartete von Lernenden die selbstständige Suche nach Lernressourcen im Web. Heutige Schätzungen 4 gehen davon aus, dass das Web mehr als 7,9Billionen Webseiten umfasst, und diese Anzahl wächst täglich. Auch wenn nur ein geringer Teil dieser Webseiten relevante und wertvolle Informationen, die für das Lernen verwendet werden können, enthalten, ist es immer noch eine unüberschaubare Anzahl von Ressourcen. Damit ergeben sich für das Lernen mit diesen Ressourcen Herausforderungen: Viele Ressourcen sind nicht für das Lernen aufbereitet. Relevante Informationen sind zum Beispiel oft über verschiedene Ressourcen verteilt. Die Unerfahrenheit von Lernenden ist ein weiteres Problem, denn sie können zumindest am Anfang einer Recherche nicht über die Vertrauenswürdigkeit und Relevanz von Ressourcen urteilen. Weitere Probleme werden von Tergan in [ 157 ] und Naumann in [ 107 ] angesprochen. Tergan spricht von struktureller und konzeptueller Desorientierung, die auftreten, wenn ein Lernender seine Recherche nicht strukturieren kann (z.B. wenn er nicht weiß, wie er am besten die Suche startet oder wenn er Schwierigkeiten hat beim Auffinden bereits besuchter Webseiten) bzw. wenn er neue Informationen nicht aufnehmen kann (z.B. weil Vorwissen fehlt). Naumann wiederum spricht von der kognitiven Mehrbelastung, wenn Lernende ihre Konzentration nicht nur für das Lernen, sondern für andere Aufgaben wie das Finden, Bewerten oder Speichern von Ressourcen verwenden müssen. Ressourcen-basiertes Lernen mit Ressourcen aus dem Internet findet in sehr vielen Szenarien statt: Wenn Studenten einen Vortrag im Rahmen einer Gruppenarbeit erstellen möchten und Informationen im Netz suchen, wenn ein Schüler ein BiologieReferat vorbereiten soll, wenn Mitarbeiter einer Firma eine Geschäftsreise nach Indien planen und sich über Land und die Kultur informieren wollen oder wenn Wissenschaftler an einem Beitrag arbeiten und nach verwandten Arbeiten recherchieren. An diesen Beispielen werden zwei Aspekte deutlich: erstens, dass das Vorwissen der Personen nicht ausreicht, um einen aktuellen Informationsbedarf zu decken, sodass sie selbstständig nach digitalen Ressourcen suchen müssen und zweitens, dass Lernende zwar die Aufgabe alleine bearbeiten, aber oft einer größeren Gruppe angehören. Beispielsweise gehört ein Schüler zu einer Klasse, ein Studenten besucht eine Vorlesung zusammen mit anderen Studenten, ein Mitarbeiter ist einer von vielen in einer Firma und ein Forscher einer von vielen in einer Forschergruppe. Aus diesem Grund stellte Tergan fest, dass Lehrende Lernenden Werkzeugen zur Unterstützung des Ressourcenbasierten Lernens anbieten sollten. In [ 19 ] diskutiert Böhnstedt weitere Definitionen des Ressourcen-basierten Lernens im Web und definiert Ressourcen-basiertes Lernen als „Form des Lernens, bei welcher der aktuelle Informationsbedarf durch die selbständige Interaktion mit einer Vielzahl verschiedener digitaler Lernressourcen gedeckt wird“. Diese Definition beschreibt sehr genau das Ressourcen-basierte Lernen, wie es im Rahmen dieser Arbeit benutzt wird, betrachtet allerdings nicht die oben erwähnte zweite Tatsache: Da Lernende in vielen Szenarien Mitglieder einer größeren Gruppe sind, gibt es eine hohe Wahrscheinlichkeit, dass andere Mitglieder relevante oder ähnliche Ressourcen bereits gefunden haben. Daher wird in dieser Arbeit Ressourcen-basiertes Lernen wie folgt definiert: 4http://www.worldwidewebsize.com/ - Zugriff am 14.11.2012 2.1 ressourcen-basiertes lernen und lernressourcen 7 Definition 1(Ressourcen-basiertes Lernen (RBL) in Online-Communities) RBL in Online Communities wird definiert als Form des Lernens, bei welcher Lernende ihren aktuellen Informationsbedarf durch selbständige Interaktion mit einer Vielzahl verschiedener digitaler Lernressourcen decken. Lernende gehören dabei einer Community an, deren andere Mitglieder ebenfalls durch selbständige Interaktion mit Lernressourcen lernen. Die gesammelten Lernressourcen stehen allen Mitgliedern der Community zur Verfügung. Diese Definition schließt weder die Anleitung durch einen Experten oder Lehrer noch die Kollaboration zwischen den Mitgliedern der Community aus, fokussiert aber auf das selbstgesteuerte Suchen und Lernen eines Lernenden. In dieser Definition kommt das Konzept „Lernressource“ vor. Bevor die Herausforderungen im Ressourcen-basierten Lernen in Communities analysiert werden, soll dieser Begriff an dieser Stelle nochmals erklärt werden. In der Literatur sind die Begriffe „Lernressourcen“ und „Lernobjekte“ eng miteinander verknüpft, oft werden sie sogar synonym benutzt. Die Tatsache, dass sich sehr viele Forscher mit Lernressourcen beschäftigt haben, hat dazu geführt, dass sich keine klare Definition des Begriffs „Lernobjekt“ gebildet hat. Die existierenden Definitionen hängen in der Regel vom Anwendungsszenario ab. Scholl hat in [ 145 ] verschiedene Definitionen diskutiert und folgerte, dass Forscher in der Vergangenheit folgende Merkmale in den Vordergrund der Definition von Lernobjekten stellen: •Granularität , also die Feinkörnigkeit der Lernobjekte, je nachdem, ob ein Lernobjekt aus vielen anderen kleinen besteht. Hier haben sich Autoren wie Wiley [ 165 ], Polsani [ 116 ], Boyle [ 22 ] oder Meyer [ 100 ] mit der Frage beschäftigt, ob Fragmente von Lernobjekten auch Lernobjekte sind und wie sich aus diesen Fragmenten neue Lernobjekte erstellen lassen. •Wiederverwendbarkeit , die lange Zeit im Fokus der Forschung war, definiert, inwieweit sich Lernobjekte für verschiedene Zwecke adaptieren lassen. Autoren wie Polsani [ 116 ], Hörmann [ 59 ], Meyer [ 100 ] und Zimmermann [ 174 ] legten einen großen Fokus auf die Wiederverwendbarkeit von Lernobjekten. •Lernabsicht , d.h. inwieweit die Absicht mit dem ein Objekt erstellt wurde, seine Eigenschaften als Lernobjekt betrifft. Beispielsweise definierte L’Allier [ 80 ] verschiedene Kriterien, die Ressourcen erfüllen müssen, um als Lernobjekte zu gelten. Eines dieser Kriterien war u.a. die Tatsache, dass ein Lernziel definiert ist. Darüber hinaus muss dieses Ziel durch Deckung eines Informationsbedarfs erreichbar sein und es muss bewertbar sein, ob und ab wann das Ziel erreicht wurde. Polsani [ 116 ] und Littlejohn [ 84 ] definierten Lernobjekte allerdings weniger strikt, da eine zu große Fixierung auf Lernziele die Wiederverwendbarkeit beeinträchtigen könnte. •das Beinhalten von Metadaten , um die Suche, Katalogisierung und den Nutzen von Lernobjekten zu unterstützen. Hodgins klassifizierte in [ 58 ] Lernobjekte je nach der Art der Metadaten, mit der sie versehen sind. •ihr Inhaltsmodell , je nachdem, wie der Inhalt des Lernobjekts eingebunden ist. Bekannte Inhaltsmodelle sind das Cisco-Inhaltsmodell [ 14 ] und das Inhaltsmodell von Hodgins [58]. 8 grundlagen •im Lebenszyklus , unterteilt in Erstellung, Wiederverwendung, Benutzung und Bereitstellung. Die Unterstützung des Lebenszyklus von Lernobjekten haben sich Autoren wie Downnes [ 38 ], Rensing et al. [ 126 ] und Lehmann [ 82 ] vorgenommen. Allerdings stellt Polsani in [ 116 ] fest, dass diese vielen Definitionen von Lernobjekten nicht konsistent sind und sich zum Teil widersprechen. Darüber hinaus existieren Formate wie das Learning Object Metadata ( LOM ) 5 (LOM) oder das Shareable Content Object Reference Model ( SCORM ) 6 (SCROM), um Lernobjekte zu beschreiben oder auszutauschen. Im Ressourcen-basierten Lernen, wie es in dieser Arbeit betrachtet wird, spielen Web-Ressourcen eine große Rolle, insofern schränken die Definitionen von Lernobjekten aus der Literatur das Ressourcen-basierte Lernen zu sehr ein. Aus diesem Grund werden im Rahmen dieser Arbeit Lernressourcen wie folgt definiert: Definition 2(Lernressourcen) Lernressourcen sind digitale (Web-)Ressourcen, die vom Lernenden im Ressourcen-basierten Lernen genutzt werden können. Lernressourcen können z.B. Webseiten, Videos, Bilder oder Blog-Einträge sein. Darüber hinaus deckt diese Definition die Definitionen aus vorherigen Arbeiten ab, wenn die Lernobjekte digital vorliegen und über das Web verfügbar sind. Laut Definition 2müssen Lernressourcen weder explizit für das Lernen aufbereitet noch durch Metadaten beschrieben sein oder andere Eigenschaften besitzen. 2.2 information retrieval und maschinelles lernen Information Retrieval ( IR ) (auf Deutsch Informationsrückgewinnung) wird von Manning et al. in [ 91 ] wie folgt definiert: „Information Retrieval is finding material (usually documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually stored on computers)“. Danach ist Information Retrieval als das Finden von unstrukturierten Dokumenten in einer großen Menge von Dokumenten, um einen Informationsbedarf zu decken, definiert. Im Folgenden werden verschiedene Konzepte aus diesem Gebiet eingeführt und insbesondere auf die Evaluation von Systemen für Information Retrieval eingegangen. 2.2.1Information Retrieval 2.2.1.1Informationsbedarf Der Informationsbedarf eines Benutzers bezeichnet den Wunsch nach Informationen zu einem gegebenen Thema, um z.B. eine gegebene Aufgabe zu lösen [ 91 ]. Man unterscheidet zwischen Informationsbedarf und Anfrage. Eine Anfrage beschreibt den Versuch eines Benutzers, seinen Informationsbedarf mitzuteilen [ 91 ]. Dies kann in textueller Form (z.B. SQL-Anfrage 7 ), implizit (z.B. mittels Analyse des Benutzer5http://www.adlnet.gov/Technologies/scorm/SCORMSDocuments/20044thEdition/ - Zugriff am 14.11.2012 6http://ltsc.ieee.org/wg12/files/LOM_1484_12_1_v1_Final_Draft.pdf - Zugriff am 14.11.2012 7Standard Query Language (SQL) 2.2 information retrieval und maschinelles lernen 9 verhaltens oder seiner gespeicherten Dateien) oder auf andere Weisen geschehen(z.B. mit „Like“-Knöpfen in Facebook8) 2.2.1.2Relevanz Eine Ressource oder ein Dokument ist relevant für einen Benutzer, wenn die Ressource wertvolle Informationen bzgl. des Informationsbedarfs eines Benutzers [ 91 ] enthält. Allerdings muss man an dieser Stelle anmerken, dass die Relevanz immer eine Portion Subjektivität hat und dass die Qualität des Retrieval von der Anfrage des Benutzers abhängt. 2.2.1.3Ranking Informell kann ein Ranking als eine Liste von Entitäten gemäß einem RankingKriterium bezeichnet werden. Beispielsweise kann ein Ranking von Ressourcen eine Liste von Ressourcen sein, in dem die Ressourcen in absteigender Reihenfolge gemäß Relevanz den Informationsbedarf eines Benutzers decken. Formell ist ein Ranking ein Tupel von Entitäten in geordneter Reihenfolge. Entitäten sind eine Menge von Dingen, die gerankt werden und die miteinander vergleichbar sein können auf der Basis eines Ranking-Kriteriums, das durch die binäre Relation / ausgedrückt wird. R={(e0,...,en)|(e0,...,en)∈P(E)∧∀k={0,...,n−1}⇒ek+1/ek} Estellt eine Menge von Entitäten dar, die gerankt werden sollen. P(E)Menge von Permutationen von E /Totale, reflexive und transitive binäre Relation basierend auf Ranking-Kriterien 2.2.1.4Empfehlung Eine Empfehlung von Entitäten sind Vorschläge. Üblicherweise werden diese Vorschläge von einem Empfehlungssystem generiert. Entitäten können alle möglichen Ressourcen, Benutzer oder Dinge sein. Beispielsweise beschreibt Koren in [ 77 ] ein Film-Empfehlungssystem. In [ 3 ] stellen Adomavicious et al. verschiedene traditionelle Empfehlungssysteme dar. Das Ziel von traditionellen Empfehlungssystemen ist die Bestimmung einer Ratingfunktion R mit folgender Signatur: R:Benutzer ×Entit ¨at →Rating Die Ratingfunktion ist partiell, da kein Benutzer alle Entitäten gespeichert hat. Ein Empfehlungssystem muss die Ratingfunktion total machen, also unbekannte Ratings raten. In Folksonomie-Anwendungen 2.3.8ist Rating ∈{0 , 1} , je nachdem, ob ein Benutzer eine Ressource getaggt hat oder nicht. Die Abschätzung von unbekannten Ratings stellt ein Ranking dar. Aus diesem Grund lassen sich Empfehlungssysteme als Rankingsysteme ansehen. Ein Empfehlungssystem prognostiziert Entitäten basierend auf Informationen über sie und auf dem Profil des Benutzers [ 64 ]. In Abschnitt 3.1 wird auf die verschiedenen Empfehlungssysteme näher eingegangen. 8http://www.facebook.com - Zugriff am 14.11.2012 10 grundlagen 2.2.2Maschinelles Lernen Der Einsatz von Methoden des maschinellen Lernens für die Klassifizierung von Relationen zwischen den Konzepten stellt einen Schwerpunkt dieser Arbeit dar. Im folgenden Kapitel sollen die Prinzipien erklärt werden, wie solche Verfahren evaluiert werden. Mitchell hat in [ 103 ] maschinelles Lernen wie folgt definiert: „A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with Experiences E“. Es geht also darum, dass ein Computer-Programm von Erfahrungen E lernt, wie eine Aufgabe (oder Menge von Aufgaben) T gelöst wird, sodass sie bzgl. einer gegebenen Metrik bzw. Maß besser abschneidet. Beispielsweise kann ein Schachspieler-Computer-Programm seine Gewinnquote (P) beim Schachspielen (T) durch Erfahrungen verbessern, wenn es immer wieder gegen sich selbst spielt (E). In dieser Arbeit wird maschinelles Lernen im Rahmen von binären Klassifikationsaufgaben angewendet. Eine Klassifikationsaufgabe bezeichnet die Aufgabe der Klassifizierung von Instanzen in einer gegebenen diskreten Menge von möglichen Kategorien [ 103 ]. Bei binären Klassifikationsaufgaben geht es darum, zwischen genau zwei Kategorien zu unterscheiden. Die Klassifizierungsaufgabe übernimmt ein Klassifikator. Der Klassifikator entscheidet anhand einer gegebenen Beispielmenge, wie eine neue Instanz klassifiziert wird. Angewendet auf die Definition von maschinellem Lernen stellt man fest, dass die Aufgabe (T) darin besteht, zwischen zwei Kategorien c1 und c2 zu unterscheiden, die Erfahrungen (E) kommen aus einer gegebenen Beispielmenge, genannt Trainingskorpus, und die Performanz (P) wird anhand der im nächsten Abschnitt (2.2.3) vorgestellten Metriken gemessen. Konkret entscheidet der Klassifikator basierend auf sogenannten Features, ob eine Instanz zu c1 oder c2 gehört. Ein Feature wird auf eine Instanz angewendet und liefert als Ergebnis jedes Features einen Zahlenwert zurück. Anschließend, wenn alle Features zu einer Instanz berechnet wurden, werden die Werte in einen sogenannten Featurevektor eingetragen. Der Featurevektor wird dabei als Repräsentation der Instanz angesehen und kann benutzt werden, um ähnliche Instanzen oder wiederkehrende Muster zwischen den Instanzen zu berechnen. Die Erstellung eines Featurevektors wird in Abbildung 1dargestellt. KOM – Multimedia Communications Lab 5 Our Approach Feature f1Feature f2… Feature fn Link (c1,c2) … Featurevektor = ( v1 v2… vn) 2 Abbildung 1: Erstellung des Featurevektors 2.2.3Evaluationsmaße Die im Rahmen dieser Arbeit entwickelten Verfahren werden mit Hilfe von Maßen aus dem Information Retrieval evaluiert: Precision, Recall und F-Maß. Diese Maße helfen dabei, die Güte der Verfahren aus mehreren Blickwinkeln zu beurteilen. 2.2 information retrieval und maschinelles lernen 11 Gegeben sei ein Klassifikator k , der eine (z.B. binäre) Klassifikation c1 oder c2 vornimmt. Der Klassifikator klassifiziert Entitäten e={e1 , e2 ,..., en} in den beiden Klassen c1 oder c2 ein. Bei diesem Prozess kann der Klassifikator allgemeine Fehler begehen, d.h. er sortiert eine Entität ei in die falsche Klasse ein. Abhängig vom Ergebnis der Klassifikation sowie von der tatsächlichen Klasse der Entität können vier Fälle unterschieden werden: 1. Richtig-positiver Fall (engl. true positive, tp ): Eine Entität ei der Klasse c1 wird korrekt als c1markiert. 2. Richtig-negativer Fall (engl. true negative, tn ): Eine Entität ei der Klasse c2 wird korrekt als c2markiert. 3. Falsch-positiver Fall (engl. false positive, fp ): Eine Entität ei der Klasse c1 wird fälschlicherweise als c2markiert. 4. Falsch-negativer Fall (engl. false negative, fn ): Eine Entität ei der Klasse c2 wird fälschlicherweise als c1markiert. Oft benutzt man eine sogenannte Konfusionsmatrix, um die Ergebnisse der Klassifikation darzustellen. Ein Beispiel wird in Tabelle 1dargestellt. Tabelle 1: Beispiel einer Konfusionsmatrix Der Link gehört zur Klasse c1Der Link gehört zur Klasse c2 Als c1klassifiziert Richtig-positiv (tp) Falsch-positiv (fp) Als c2klassifiziert Falsch-negativ (fn) Richtig-negativ (tn) Aus den Werten der Konfusionsmatrix lassen sich zwei zentrale Kennzahlen zur Evaluation eines Klassifikators errechnen [90]: Recall (auch Sensitivität oder Trefferquote genannt) , die als Anteil der korrekt als c1 klassifizierten Entitäten an der Gesamtheit der tatsächlich existierenden c1 Entitäten definiert werden. Recall entspricht der bedingten Wahrscheinlichkeit: P(richtig als c1erkannt|alle tatsächlichen existierenden c1-Entitäten) = tp tp+fn Precision (auch Relevanz, positiver Vorhersagewert, Genauigkeit genannt) , der Anteil der korrekt als c1 klassifizierten Entitäten an der Gesamtheit der als c1 erkannten Entitäten. Precision entspricht der bedingten Wahrscheinlichkeit: P(richtig als c1erkannt|alle als c1-erkannten Entitäten) = tp tp+fp Recall und Precision stehen oft in Konflikt zueinander: Ein höherer Recall eines Klassifikators bedeutet, dass der Großteil der tatsächlichen c1 -Entitäten vom Klassifikator als c1 korrekt klassifiziert wurde. Darunter kann aber die Precision leiden, da der Klassifikator für diesen Zweck viele c2 -Entitäten u.U. klassifizieren müsste. Umgekehrt kann eine hohe Precision zu einem schlechten Recall führen. Ein Klassifikator, der „auf Nummer sicher“ geht und nur Entitäten als c1 klassifiziert, wenn er sich sehr sicher ist, produziert hohe Precision-Werte. Dies führt aber auch dazu, 12 grundlagen dass viele „unsichere“ c1 -Entitäten übersprungen werden, was wiederum zu einer niedrigeren Precision führt. Je nach Anwendungsszenario können abhängig vom Schwerpunkt der Suche Suchergebnisse mit höherem Recall oder mit höherer Precision bevorzugt werden, indem dem Recall oder der Precision höhere Gewichtung zugeordnet wird [ 133 ]. Aus dem Precision und dem Recall kann ein sogenanntes F-Maß berechnet werden, das ein kombiniert gewichtetes harmonisches Maß für Recall und Precision darstellt. Im Rahmen dieser Arbeit wird die sogenannte F1 -Maß (Precision und Recall werden jeweils mit dem Wert 1gewichtet) wie folgt berechnet: F1=2∗Precision∗Recall Precision+Recall In allgemeinerer Form lautet die Formel für Fα(mit α⩾0) [133]: Fα=(1+α)∗Precision∗Recall α∗Precision+Recall F2 gewichtet z.B. den Recall doppelt so stark wie die Precision, bei F0,5 hingegen nimmt die Precision eine doppelt höhere Gewichtung im Vergleich zum Recall ein. Van Rijsbergen postuliert in [ 133 ], dass F-Maß ein Maß für die Effektivität der Informationsgewinnung aus Sicht eines Benutzers ist. Ein wichtiger Unterschied zwischen Recall und Precision ist der Fakt, dass das Recall nicht vom Verhältnis zwischen den positiven und negativen Fällen in der Testmenge abhängt. Der Recall beschränkt sich nur auf die positiven Fälle ( c1 ) und es spielt keine Rolle, ob die positiven Fälle in der Testmenge unteroder überrepräsentiert sind. Die Berechnung der Precision dagegen bezieht sowohl die positiven als auch die negativen Fälle in die Berechnung mit ein, was dazu führt, dass die Precision durch das Verhältnis zwischen positiven und negativen in der Testmenge beeinflusst wird. 2.2.4Evaluationsverfahren Für die Evaluation von Verfahren im Information Retrieval werden oft Varianten der sogenannten Kreuzvalidierung (engl. cross-validation) genutzt [ 103 ]. Mittlerweile hat sich die sogenannte k-fache stratifizierte Kreuzvalidierung (engl. K-Fold CrossValidation) als aus statischer Sicht beste Wahl herauskristallisiert [ 16 ]. Im Rahmen dieser Arbeit werden die Ergebnisse des Verfahrens des maschinellen Lernens mittels einer zehnfachen stratifizierten Kreuzvalidierung überprüft. Die Vorgehensweise wird in Abbildung 2gezeigt: Der gesamte Korpus wird in zehn Stichproben zerlegt. Davon werden neun Proben (90 % der Proben, hier in Grün dargestellt) als Trainingsdaten benutzt und die zehnte Probe (10% der Proben, hier in Rot dargestellt) als Testdaten. Der Evaluationsvorgang wird 10 Mal durchlaufen, wobei jede Stichprobe genau einmal als Testprobe eingesetzt wird. Abschließend werden die erhaltenen Ergebnisse über eine Mittelwertbildung bzw. über eine andere Kombinierungsmethode zusammengeführt, um ein einheitliches gesamtes Ergebnis zu erreichen. Der Vorteil dieser Methode liegt darin, dass alle Stichproben sowohl für das Training als auch für die Validierung des Verfahrens benutzt werden und jede Stichprobe genau einmal als eine Testprobe auftritt. Durch den Einsatz der zehnfachen stratifizierten Kreuzvalidierung wird der Einfluss von zufälligen Ausreißern vermindert sowie eine klare Trennung zwischen Trainingund Test-Daten erreicht [76]. 2.3 wissensrepräsentation 13 . . . . 1 2 10 3 Abbildung 2:10-fache stratifizierte Kreuzvalidierung 2.3 wissensrepräsentation In dieser Arbeit werden Fachbegriffe aus dem Gebiet der Wissensrepräsentation und der Computerlinguistik verwendet. In diesem Kapitel sollen daher die zum Verständnis der Arbeit notwendigen Fachbegriffe definiert und erklärt werden. 2.3.1Begriffe Im Rahmen dieser Arbeit sind Begriffe Wörter oder zusammengesetzte Wörter, die eine syntaktische und semantische Einheit bilden. Beispiele von Begriffen sind „Maschine“, „Informationstechnologie“, „Trauer“, „Telefon“ und „Löwe“. 2.3.2Konzepte Es existieren sehr viele Definitionen eines Konzepts. An dieser Stelle sollen drei Definitionen vorgestellt und diskutiert werden. Definition von Grabrilovitch and Markovitch [46]: „Concepts are the basic units of meaning that serve humans to organize and share their knowledge.“ Konzepte sind also demnach die „Grundeinheiten“ der Bedeutung, die von Menschen benutzt werden, um ihr Wissen zu organisieren und zu teilen. Bei dieser Definition liegt der Fokus in der Bedeutung eines Wortes. Diese Definition erlaubt durch die Benutzung des Begriffes „Grundeinheit des Wissens“ einen großen Raum an Interpretationen. Es ist hier sehr schwer zu sagen, ob ein gegebener Begriff eine „Grundeinheit des Wissens“ darstellt. Das liegt daran, dass das Wissen von Menschen nicht objektiv messbar ist. Definition aus Wikipedia.org9: „Ein Konzept ist ein Ergebnis des Instruments des Prozesses kognitiver Konzeption von Begriffen mit Sprache, der gleichzeitig eine Aussage zum Begriff enthält.“ Diese Definition enthält Begriffe wie „kognitive Konzeption“, die aus der Psychologie kommen. Bei dieser Definition wird ein Konzept als ein Ergebnis der Konzeption deklariert, allerdings ist es mit ihrer Hilfe sehr schwierig zu beurteilen, ob ein bestimmter Begriff ein Konzept darstellt. 9http://de.wikipedia.org/wiki/Konzeption - Zugriff am 14.11.2012 14 grundlagen Definition aus WordNet10: „A concept is an abstract or general idea inferred or derived from specific instances“ Diese Definition ist abstrakter als die zwei vorherigen Definitionen. Sie stellt weder erklärende Beschreibungen vor noch geht sie im Detail auf die spezifischen Instanzen ein. Zwar werden hier die Eigenschaften eines Konzepts definiert, sie erlaubt aber z.B. im Rahmen dieser Arbeit Kategorien in Wikipedia als Konzepte zu sehen und die darin enthaltenen Artikel als Instanzen zu sehen. Zum Schluss bleibt zu erwähnen, dass Konzepte eindeutig sind. Beispielsweise stellt jede Bedeutung des Begriffes „Bank“, das Finanzinstitut und die Sitzgelegenheit, ein einzigartiges und unabhängiges Konzept dar. 2.3.3Relationen zwischen Konzepten Semantische Relationen: Bevor die verschiedenen Modelle zur Wissensrepräsentation vorgestellt werden, sollen hier einige der in solchen Modellen vorkommenden semantischen Beziehungen zwischen Konzepten vorgestellt werden. Synonymie: Synonymie bezeichnet die inhaltliche Überstimmung zwischen zwei oder mehreren Begriffen. Synonyme Begriffe beschreiben dasselbe Konzept. Beispiele für Synonyme sind die Begriffe „Wagen“ und „Auto“. Beide beschreiben ein Fahrzeug mit vier Rädern. Antonymie: Antonymie besteht zwischen zwei Begriffen, wenn einer der beiden Begriffe das Gegenteil des anderen ist. Beispielsweise sind „Kälte“ und „Wärme“, „weiß“ und „schwarz“ Antonymien. Meronymie: Meronymie stellt eine Teil-Ganzes-Relation zwischen Begriffen dar. Meronymie-Relationen gibt es zwischen „Finger“ und „Hand“ oder ’“Tür“ und „Haus“. Hypernymie und Hyponymie: Als Hyponymie wird in der Linguistik eine Relation zwischen zwei Begriffen bezeichnet, bei der ein Begriff in einen anderen Begriff eingeschlossen ist. Nach Cruse [ 33 ] wird ein Konzept c1 als Hyponym von c2 bezeichnet (und umgekehrt wird c2 als Hyperonym von c1 bezeichnet), wenn jedes Individuum von c1 auch ein Individuum von c2 ist, aber nicht umgekehrt. Beispielsweise ist jede Katze ein Wirbeltier, aber nicht jedes Wirbeltier eine Katze. Aus diesem Grund werden Hyponymie-Beziehungen auch „ist-ein“-Beziehungen genannt. 2.3.4Taxonomien Taxonomien entstehen, wenn Hyperonyme und Hyponyme hierarchisch strukturiert sind. Der Begriff „Taxonomie“ setzt sich aus den altgriechischen Begriffen „taxis“ (Ordnung) und „nómos“ (Gesetz) zusammen. In [ 78 ] wird eine Taxonomie als „ein einheitliches Verfahren oder Modell definiert, um Objekte eines gewissen Bereichs [...] nach bestimmten Kriterien zu klassifizieren, d.h. sie in bestimmte Kategorien oder Klassen (auch Taxa genannt) einzuordnen“. In der Biologie wird eine Taxonomie als Klassenhierarchie verstanden, wie das Beispiel der Unterteilung von Lebewesen in Reiche, Stämme, Klassen Ordnungen, Familien, Gattungen und Arten (siehe Abbildung 3). 10 http://wordnetweb.princeton.edu/perl/webwn/ - Zugriff am 14.11.2012 2.3 wissensrepräsentation 15 Abbildung 3: Eine Taxonomie in der Biologie [10] In dieser Arbeit wird die Definition einer Taxonomie an die Definition der Linguistik angelehnt: Eine Taxonomie zeichnet sich durch zwei Eigenschaften aus: Die Hyponymie und die Inkompatibilität (vgl. [ 33 ]). Während die Hyponymie sicherstellt, dass es eine Hyponymie-Relation zwischen Oberund Unterknoten gibt, besagt die Inkompatibilität, dass Begriffe auf der gleichen hierarchischen Ebene nicht austauschbar sein sollen. Weiter wird in der Linguistik zwischen Klasse-Instanz-Beziehungen, wie z.B. zwischen „Frucht“ und „Apfel“, und reine Hyponymie-Beziehungen, wie z.B. zwischen „Frucht“ und „Pflanze“, unterschieden. Im Rahmen dieser Arbeit werden diese Beziehungstypen unter dem Relationstyp „ist-ein“ zusammengefasst, da diese feinere Unterscheidung für die Anwendungszwecke dieser Arbeit und viele anderer NLP-Anwendungen keine wesentliche Bedeutung hat [ 152 ]. Abbildung 4zeigt ein Beispiel für eine Taxonomie, die verschiedene Fahrzeuge darstellt. 22 grundlagen 2.4.2.3Glosse Die Glosse eines Wikipedia-Artikels wird oft als „Wörterbuch-ähnliche Definition“ charakterisiert [ 71 ], die jeder Wikipedia-Artikel besitzen sollte. Laut WikipediaGuidelines 27 sollte der erste Paragraph das Konzept definieren. Als Beispiel betrachten wir die Glosse des Wikipedia-Artikel für „Automobile“: „Ein Automobil, kurz Auto (auch Kraftwagen, früher Motorwagen), ist ein traditionell mehrspuriges Kraftfahrzeug, das von einem Motor angetrieben wird und zur Beförderung von Personen und Frachtgütern dient. Motorisierte Wagen lösten in nahezu allen Bereichen die von Zugtieren gezogenen Fahrwerke ab, da sie deutlich schneller und weiter fahren und eine höhere Leistung erbringen können. Dieser Vorteil entwickelte sich schließlich zu mehr Transporten, einem massiv gestiegenen Raumbedarf und markanten Umweltproblemen. Dies, obwohl der Verbrennungsmotor mitnichten der Antrieb der ersten Stunde war: 1900 verkehrten in den USA 40 Prozent der Automobile mit Dampf, 38 Prozent elektrisch und nur 22 Prozent fuhren mit Benzin. Der weltweite Fahrzeugbestand steigt kontinuierlich an und lag im Jahr 2007 bei rund 918 Millionen Fahrzeugen.“ Abhängig vom Interesse des Lesers kann er sich mit dieser Definition zufrieden geben oder den Artikel weiterlesen, um weitere Details zu erfahren. 2.4.2.4Infoboxen Infoboxen sind kleine Tabellen, die die Eckpunkte von bestimmten Wikipedia-Artikeln zusammenfassen. Infoboxen gibt es für geographische Einheiten (Kontinente, Länder, Städte, Gemeinden etc), Lebewesen (Pflanzen, Tiere etc) und andere Artikeltypen (Berge, Bands, chemische Elemente etc). Die Infobox des Wikipedia-Artikels „Entenvögel“ wird in Abb. 10 gezeigt. Infoboxen lassen sich aufgrund ihrer maschinenlesbaren Form gut für NLP-Applikationen nutzen, wie das Beispiel DBPedia [ 11 ] (siehe 3.2.3) zeigt. Abbildung 10: Infobox des Wikipedia-Artikels: „Entenvögel“ 27 http://en.wikipedia.org/wiki/Wikipedia:Lead_section - Zugriff am 14.11.2012 2.4 wikipedia 23 2.4.2.5Kategorien In Wikipedia gehört jeder Artikel mindestens einer Kategorie an. Die Zugehörigkeit zu einer oder mehreren Kategorien wird mit Hilfe eines Kategorie-Abschnitts am Ende eines Artikels dargestellt, siehe Abbildung 11. Kategorien stellen eine Gruppe von Artikeln zu einem bestimmten Thema dar. Beispielsweise entwählt die Kategorie „Darmstadt“ 28 sowohl mit Darmstadt verwandte Artikel wie „Kommunalpolizei Darmstadt“ 29 , „Luisencenter“ 30 oder das „Darmstädter Zentrum für IT-Sicherheit“ 31 . Darüber hinaus enthalten sie auch mit Darmstadt verwandte Unterkategorien wie „Bauwerk in Darmstadt“ 32 , „Stadtteil von Darmstadt“ 33 oder „Unternehmen (Darmstadt)“ 34 . Unterkategorien dürfen wiederum weitere Artikel oder Kategorien beinhalten. Abbildung 11: Kategorien-Abschnitt des Wikipedia-Artikels „Darmstadt“ Der Unterschied zwischen Artikeln und Kategorien in Wikipedia kann anhand des Artikels und der Kategorie „Darmstadt“ dargestellt werden. Während der Artikel Darmstadt die Stadt Darmstadt selbst darstellt, ist die Kategorie Darmstadt eine Ansammlung von Artikeln und Unterkategorien, die mit der Stadt Darmstadt verwandt sind. Kategorien und ihre Oberund Unterkategorien lassen sich als gerichteter Graph (ähnlich wie in Abschnitt 2.4.2.2) darstellen. Der resultierende Graph wird Kategoriengraph genannt. Die Kanten im Graph werden durch Kategorienpaare dargestellt, die Links genannt werden. Verfeinerungslinks (engl. Refinement Links) werden in Wikipedia verwendet, um andere Kategorien zu organisieren [ 118 ]. Verfeinerungslinks haben normalerweise die Form „X nach Y“ oder „X als Y“, wobei „X“ und „Y“ beliebige Begriffe darstellen können. Ein Beispiel wäre der Verfeinerungslink „Geographie nach Epoche“. Dieser Link fasst alle Kategorien zusammen, die mit Geographie zu tun haben und strukturiert die hier sich befindenden Kategorien und Artikel nach der Epoche, in der sie stattgefunden haben. Als Beispiel sieht man in Abb. 12 einen Ausschnitt des Kategoriengraphs. Der Kategoriengraph ist keine reine Taxonomie, da nicht nur Hyponymie-Beziehungen enthalten sind, sondern weitere semantische Relationen. Voess [ 158 ] bezeichnet den Kategoriengraph als Thesaurus aufgrund der Tatsache, dass Kategorien zu mehreren Kategorien gehören können. Andere Autoren wie Hammwöhner [ 52 ] sehen den Kategoriengraph als strukturiertes Vokabular, mit dem Wikipedia-Artikel verschlagwortet werden können. 28 http://de.wikipedia.org/wiki/Kategorie:Darmstadt - Zugriff am 14.11.2012 29 http://de.wikipedia.org/wiki/Kommunalpolizei_Darmstadt - Zugriff am 14.11.2012 30 http://de.wikipedia.org/wiki/Luisencenter - Zugriff am 14.11.2012 31 http://de.wikipedia.org/wiki/Darmst%C3%A4dter_Zentrum_f%C3%BCr_IT-Sicherheit - Zugriff am 14.11.2012 32 http://de.wikipedia.org/wiki/Kategorie:Bauwerk_in_Darmstadt - Zugriff am 14.11.2012 33 http://de.wikipedia.org/wiki/Kategorie:Stadtteil_von_Darmstadt - Zugriff am 14.11.2012 34 http://de.wikipedia.org/wiki/Kategorie:Unternehmen_%28Darmstadt%29 - Zugriff am 14.11.2012 24 grundlagen Abbildung 12: Kategoriengraph von der Hauptkategorie zur Kategorie „Darmstadt“ 2.4 wikipedia 25 2.4.2.6Begriffsklärungsseiten Begriffsklärungsseiten (Disambiguierung) werden dazu benutzt, mehrdeutige Begriffe voneinander zu unterscheiden. Wenn ein Benutzer nach einem Wort mit mehreren Bedeutungen sucht, wird er zu einer Begriffsklärungsseite weitergeleitet. Von dieser Seite aus kann der Benutzer weiter zum gewünschten Artikel navigieren. Beispielsweise leitet die Suche nach „Ente“ zu der Begriffsklärungsseite „Ente“35 (siehe Abb. 13) weiter. Bei Begriffen mit mehreren Bedeutungen wird ein Hinweis auf die Mehrdeutigkeit am oberen Rande des Artikels platziert. Abbildung 13: Begriffsklärungsseite: Ente 2.4.2.7Weiterleitungsseiten Weiterleitungsseiten, wie der Name es schon andeutet, leiten von einem WikipediaArtikel zu einem anderen. Der Weiterleitungsartikel selbst hat keinen Inhalt, sondern besteht aus einem Wikilink, der zum Ziel-Artikel führt. Beispielsweise gibt es die Weiterleitungsseite „Enten“ (siehe Abb. 14), die zum Artikel „Entenvögel“ 36 führt. Weiterleitungsseiten gibt es nicht nur für Pluralseiten, sondern auch für technische Fachbegriffe, Falschschreibungen sowie alternative Schreibweisen. 35 http://de.wikipedia.org/wiki/Ente - Zugriff am 14.11.2012 36 http://de.wikipedia.org/wiki/Entenv%C3%B6gel - Zugriff am 14.11.2012 26 grundlagen Abbildung 14: Weiterleitungsseite: Ente 2.4.2.8Andere Elemente der Wikipedia In Wikipedia gibt es außerdem folgende Seiten: • Hilfeseiten, die Informationen zur Benutzung und Bedienung der Wikipedia enthalten. • Benutzerseiten 37 , auf denen sich registrierte Autoren vorstellen dürfen. Auf Benutzerseiten wird außerdem angegeben, ob ein Benutzer auch Administratorrechte hat. • Spezialseiten 38 , die einen Überblick über den aktuellen Zustand der Wikipedia geben. Beispielsweise definieren diese Seiten, was auf Benutzerseiten stehen darf. • Vorlageseiten, die vorgefertigte Seiten und Beispiele zur schnellen und einheitlichen Erstellung von Artikeln und Seiten enthalten. 37 http://de.wikipedia.org/wiki/Spezial:Benutzer - Zugriff am 14.11.2012 38 http://de.wikipedia.org/wiki/Hilfe:Spezialseiten - Zugriff am 14.11.2012 3 VERWANDTE ARBEITEN »Wir sind gleichsam Zwerge, die auf den Schultern von Riesen sitzen, um mehr und Entfernteres als diese sehen zu können - freilich nicht dank eigener scharfer Sehkraft oder Körpergröße, sondern weil die Größe der Riesen uns zu Hilfe kommt und uns emporhebt.« — Bernhard von Chartres Bevor in Kapitel 4eine Analyse des Anwendungsszenarios des Ressourcenbasierten Lernens in Online Communities erfolgt, die offenen Herausforderungen bestimmt und ein Konzept vorgestellt werden, soll an dieser Stelle ein Überblick über verwandte Arbeiten gegeben werden. Zuerst soll auf Empfehlungssysteme und auf ihren Einsatz im E-Learning eingegangen werden. Danach werden im zweiten Teil verschiedene Ansätze zur automatischen Wissensextraktion behandelt. Dabei liegt der Schwerpunkt auf Verfahren, die Wikipedia als Korpus benutzen, da Wikipedia auch im Rahmen dieser Arbeit für die Wissensextraktion benutzt wird. 3.1 verwandte arbeiten im bereich empfehlungssysteme Empfehlungssysteme sind Werkzeuge und Techniken, die dem Benutzer eines Softwaresystems Objekte oder Items vorschlagen [ 131 ]. Sie werden benutzt, um Benutzer bei ihren Entscheidungen zu unterstützen wie z.B. beim Kauf von Büchern, bei der Musikauswahl oder der Suche von relevanten Nachrichten im Netz. In diesem Kapitel werden die grundlegenden Ideen und Verfahren von Empfehlungssystemen behandelt. 3.1.1Grundlagen zu Empfehlungssystemen Seit Mitte der neunziger Jahre [ 130 ], als die ersten Beiträge zu Empfehlungssystemen publiziert wurden, gibt es ein wachsendes Interesse an solchen Systemen, das bis heute ungebrochen ist [ 28 ]. Insbesondere werden sie in solchen Anwendungen eingesetzt, in denen sehr viele Items zur Verfügung stehen. Das gilt beispielsweise für soziale Netzwerke oder Communities. Empfehlungssysteme zielen darauf ab, Benutzern zu helfen, relevante Items aus einer großen Menge von Items zu finden [ 27 ]. Items können Ressourcen aller Art sein: Filme, Lieder, Bücher, Webseiten, Nachrichten, Restaurants, Hotels oder Mode. Heutzutage gibt es aber auch Empfehlungssysteme, die Benutzer [ 72 , 125 ] oder andere anwendungsspezifische Items wie Tags [ 69 ] oder Gruppen [ 110 ] empfehlen. Um relevante Empfehlungen für einen gegebenen Benutzer zu berechnen, greifen Empfehlungssysteme zumeist auf die historischen Daten von Benutzern zurück. Typischerweise wird bei Empfehlungssystemen zwischen den folgenden vier Typen von Ansätzen unterschieden: • Kollaboratives Filtern 27 28 verwandte arbeiten • Inhaltbasiertes Filtern • Wissensbasiertes Filtern • Hybrides Filtern An dieser Stelle soll ein Überblick über die Stärken und die Schwächen der verschiedenen Typen gegeben werden. Anschließend wird ein Blick auf offene Herausforderungen im Zusammenhang mit Empfehlungssystemen geworfen und analysiert, wie sich die verschiedenen Typen für eine Verwendung im E-Learning eignen. 3.1.1.1Kollaboratives Filtern Diese Art von Empfehlungssystemen stützt sich grundsätzlich auf die Vorlieben der Nutzer, um Listen von Empfehlungen zu generieren. Kollaboratives Filtern [ 48 , 57 , 140 ] erfolgt grob in drei Schritten: Im ersten Schritt werden die Vorlieben und die Präferenzen der verschiedenen Benutzer aus ihrem bisherigen Verhalten identifiziert und anschließend werden sogenannte Nachbarschaften gebildet. Eine Nachbarschaft besteht aus ähnlichen Benutzern (bei Benutzer-basierten Ansätzen) oder ähnlichen Items (bei Item-basierten Ansätzen) [ 27 ]. Der letzte Schritt besteht darin, Benutzern Items von anderen Benutzern aus seiner Nachbarschaft anzubieten, die er noch nicht kennt bzw. Items aus der Nachbarschaft der Items des Benutzers. Aufgrund ihrer Einfachheit und Effizienz ist sie eine der verbreitetsten Empfehlungstechniken. Darüber hinaus braucht kollaboratives Filtern keine Informationen über den Inhalt bzw. Bedeutung des Items. Es sind nur die Beziehungen zwischen den Nutzern und Ressourcen von Bedeutung. Nachteile des kollaborativen Filterns sind die Tatsachen, dass eine große Benutzer-Community nötig ist, das cold-start Problem [ 142 ] für neue Benutzer und Elemente besteht und das Data-Sparsity Problem [ 141 ]. Das cold-start Problem bezeichnet die Situation, wenn ein neuer Nutzer oder eine neue Ressource in die Anwendung hinzukommen. Es lassen sich nicht sofort Empfehlungen generieren, da keine oder wenige Daten über ihn/sie bekannt sind. Auf kollaborativem Filtern basierende Empfehlungssysteme neigen dazu, die beliebtesten Items zu empfehlen, was dazu führt, dass Empfehlungen Richtung Mainstream verfälscht werden. Das Data-Sparsity Problem tritt auf, wenn die vorhandenen Informationen nicht ausreichen, um eine geeignete Nachbarschaft eines Benutzers zu bilden. 3.1.1.2Inhaltbasiertes Filtern Inhaltbasierte Empfehlungssysteme [ 113 ] berücksichtigen für die Empfehlungen nur Informationen über die Benutzer und den Inhalt der Ressourcen. Meistens liegen diese Informationen in textueller Form, wie z.B. als Stichworte oder Beschreibungen der Items, vor. Empfehlungssysteme, die auf inhaltbasiertem Filtern aufbauen, suchen automatisch nach Items mit ähnlichen Beschreibungen und empfehlen diese. Diese Art von Empfehlungen hat den Vorteil, dass sie weder auf eine große Benutzer-Community noch auf eine große Profilgeschichte angewiesen ist. Darüber hinaus gibt es das cold-start Problem für neue Items nicht. Das cold-start Problem für Benutzer besteht dagegen immer noch. Nachteilig ist, dass es zusätzliche Informationen über den Benutzer braucht (i.d.R. die Interessen des Benutzers) und einen Zugriff auf den Inhalt bzw. die Beschreibung der Items (Metadaten). Bei großen Datenmengen erhöht sich die Zeitkomplexität von Empfehlungssystemen aufgrund 3.1 verwandte arbeiten im bereich empfehlungssysteme 29 der notwendigen Vorverarbeitung und Bearbeitung der textuellen Informationen entsprechend. Beispielsweise müssen u.a. die Wörter im textuellen Inhalt der Items auf ihre Wortstämme zurückgeführt werden, bevor sie mit anderen Wörtern verglichen werden. 3.1.1.3Wissensbasiertes Filtern Wissensbasiertes Filtern [ 25 , 101 ] bezeichnet den Prozess der Generierung von Empfehlungen auf Basis einer externen Wissensbasis. Diese Wissensbasen umfassen oft Benutzeranforderungen, Item-Eigenschaften und zusätzliches domänenspezifisches Wissen (z.B. in Form von Taxonomien und Ontologien). Dieses externe Wissen kann vom Empfehlungssystem ausgenutzt werden, um Zusammenhänge zwischen Benutzer oder Items zu erkennen und auf dieser Basis Benutzer oder Items zu empfehlen. Ein Beispiel für diese Art von Empfehlungssystemen ist das sogenannte Ontological Filtering [ 65 ]. Damit werden Techniken genannt, die Taxonomien und Ontologien benutzen, um Ähnlichkeiten [ 89 ] oder semantische Relationen [ 104 ] zwischen Items zu finden. In diesem Zusammenhang spricht man auch über constraint-based wissensbasiertes Filtern, worin vordefinierte Empfehlungsregeln bestimmt werden und case-based wissensbasiertes Filtern, wo mit Hilfe von Taxonomien und Ontologien und einer Distanzfunktion Ähnlichkeiten zwischen Items berechnet werden. Constraintbased wissensbasierte Empfehlungssysteme bestehen aus einem eindeutig definierten Satz von Empfehlungsregeln, die nacheinander angewendet werden [ 47 ] und casebased wissensbasierte Empfehlungssysteme beinhalten, wie der Name es schon sagt, fallbezogene Regeln, die aus dem vergangenen Verhalten und aus den Wissensbasen abgeleitet werden [86]. Empfehlungssysteme, die auf wissensbasierten Filtern beruhen, eignen sich besonders für die Empfehlung von komplexen Items mit vielen Eigenschaften (z.B. Video-Kameras oder Autos). Vorteile dieser Empfehlungssysteme sind das externe Wissen, das in die Empfehlungen einfließt, die Behebung des cold-start Problems und dass Änderungen der Präferenzen eines Nutzers sofort berücksichtigt werden können. Die Nachteile haben meistens mit der benutzten Wissensbasis zu tun: Wie gut passt die Wissensbasis zum Szenario? Was passiert, wenn kein Wissen zu einem Produkt vorhanden ist? Was passiert, wenn Item-Eigenschaften in verschiedenen Sprachen vorliegen? 3.1.1.4Hybrides Filtern Hybrides Filtern bezeichnet die Kombination verschiedener Datenquellen und Empfehlungssystemansätzen. Dabei unterscheidet man zwischen parallelisiertem hybridem Filtern (Empfehlungssysteme werden parallel ausgeführt und anschließend werden die Ergebnisse zusammengeführt), pipelined hybridem Filtern (Empfehlungssysteme werden nacheinander ausgeführt, wobei nachfolgende Empfehlungssysteme die Empfehlungsliste der vorherigen Empfehlungssysteme kennen) und monolithischem hybridem Filtern (das monolithische hybride Empfehlungssystem entsteht durch Kombination von Ansätzen und Eigenschaften von verschiedenen Empfehlungssystemen). 30 verwandte arbeiten 3.1.2Empfehlungssysteme im E-Learning Die ersten Empfehlungssysteme für E-Learning wurden ca. 2003 entwickelt. Es besteht in der Forschung die Übereinkunft, dass sich kommerzielle Empfehlungssysteme nicht einfach auf E-Learning-Systeme transferieren lassen. Tang und McCalla [ 95 , 155 , 156 ] zeigten, dass Empfehlungen, die nur auf Vorlieben der Benutzer beruhen (wie es bei kommerziellen Empfehlungssystemen der Fall ist), oft nicht die pädagogisch wertvollsten sind und dass sich das Ziel, die Rolle und der Kontext eines Benutzers während des Lernens ändern können. Drachsler zählt in [ 39 ] verschiedene Kriterien auf, die Empfehlungssysteme in E-Learning berücksichtigen sollten: • Das Lernziel der Lernenden • Das Vorwissen der Lernenden (z.B. Anfänger, Fortgeschrittene, Experten) • Die Eigenschaften der Benutzer • Erfahrungen von anderen Benutzern • Lernstrategien von Lernenden In den letzten Jahren sind aus diesem Grund verschiedene Empfehlungssysteme [ 39 , 93 ] entwickelt worden, die diesen Anforderungen oder Teilen dieser Anforderungen genügen. Leider sind viele dieser Ansätze nicht über die Entwicklung von Prototypen hinausgekommen und nicht in umfassend genutzte Anwendungen integriert worden. Im Folgenden soll ein Überblick über existierende Systeme gegeben werden. 3.1.2.1Auf kollaborativen Filtern basierende Verfahren Eines der ersten personalisierten Empfehlungssysteme für E-Learning-Systeme wurde von Recker und Walker [124,161] entwickelt. Sie verwendeten kollaboratives Filtern und haben untersucht, wie eine Lerncommunity vom Feedback von Lernenden profitieren kann. Tang und McCalla [ 95 , 155 , 156 ] entwickelten ein E-Learning-System, das auf kollaborativen Filtern basierend in der Lage ist, Ressourcen aus dem Web und von spezifischen Anwendungen zu empfehlen. Die Autoren zielten darauf ab, sowohl das Vorwissen als auch die Eigenschaften des Lernenden auszunutzen. Rafaeli et al. [ 121 , 122 ] haben sich mit der Frage beschäftigt, wie die Zusammenarbeit und die Bildung von Lerngruppen mit Hilfe von kollaborativem Filtern zu fördern ist. Dabei können Lernende entscheiden, ob sie automatisch generierte Empfehlungen oder Empfehlungen von Freunden haben wollen. In [ 40 ] hat Dron ein Empfehlungsverfahren entwickelt, das auf kollaborativem Filtern in mehreren Dimensionen besteht. Beispielsweise wird nicht nur berücksichtigt, ob ein Lernender eine Ressource gut gefunden hat, sondern auch andere Eigenschaften wie die Verständlichkeit, die Eignung für Anfänger oder die Art, wie sie geschrieben wurde. Verfahren, die auf kollaborativem Filtern basieren, eignen sich häufig nicht für E-Learning-Systeme, da sie auf die Verfügbarkeit von großen Datensätzen angewiesen sind. Dies ist im E-Learning meistens nicht der Fall. Einer der Gründe ist die Tatsache, dass viele Systeme für Schulklassen, Lernkurse oder Lehrveranstaltungen mit begrenzten Teilnehmerzahlen konzipiert sind. Darüber hinaus muss ein Lernender viele eigene Ressourcen gefunden haben, bevor Empfehlungen gebildet werden können. 3.1 verwandte arbeiten im bereich empfehlungssysteme 31 Für das Lernen bedeutet dies, dass gerade beim Beginn einer Recherche bzw. eines Lernprozesses keine Empfehlungen gemacht werden können. 3.1.2.2Auf inhaltbasiertem Filtern basierende Verfahren Die meisten auf inhaltbasierten Filtern basierende Empfehlungssysteme werden mit anderen Verfahren kombiniert (siehe 3.1.2.4). Dieser Umstand hat mehrere Gründe: Inhaltbasierte Verfahren arbeiten in der Regel daraufhin, ähnliche Ressourcen (vgl. [ 12 , 96 , 168 ]) zu empfehlen. In Anwendungsbereiche, wo die Ähnlichkeit von Objekten eine Rolle spielt, wie z.B. Biotechnologie [ 114 ], Geoinformatik [ 66 ] oder Linguistik [ 112 ], ist dies sehr nützlich. Im E-Learning aber hat dieser Anwendungsfall nur Sinn, wenn Lernende sich für ein spezifisches Thema interessieren, unabhängig von anderen Interessen und Präferenzen. Wenn es aber z.B. darauf ankommt, sich in ein Thema zu vertiefen, reicht die reine Suche nach ähnlichen Ressourcen nicht aus. Schließlich leidet inhaltbasiertes Filtern, genau wie beim kollaborativen Filtern, unter dem cold-start Problem. 3.1.2.3Auf wissensbasierten Filtern basierende Verfahren Auf wissensbasierten Filtern basierende Verfahren lassen sich in drei Kategorien einordnen: Die erste Kategorie von Verfahren setzt darauf, Kompetenzen von Lernenden und Lernkursen als Ontologie zu modellieren, um auf diese Weise Empfehlungen machen zu können. Zu diesem Verfahrenstyp gehören die Ansätze von Shen et al. [ 149 ], Manouselis et al. [ 92 ] und Aehnelt [ 4 ]. Shen et al. haben basierend auf einer Ontologie und auf Ablaufregeln (engl. senquencing rules) ein Verfahren zur Empfehlung von Lernobjekten entwickelt. Das System berechnet die Kompetenz von Lernenden und schlägt Lernobjekte vor, sodass Lernende ihre Kompetenz erhöhen können. Dieses Verfahren setzt eine Modellierung von Kompetenzen voraus, was im Ressourcenbasierten Lernen aufgrund der vielen möglichen Themen und Kompetenzen nicht machbar ist. Manouselis et al. versuchen einen ähnlichen Ansatz. Sie benutzen Ontologien von Lernkursen zu einem Thema, um Lernende durch verwandte Konzepte zu führen. Zusätzlich werden die Präferenzen der Lernenden und die Erfahrungen von ähnlichen Benutzern verwendet. Aehnelt schlägt Empfehlungssysteme für Benutzer vor, die auf eine Modellierung von Lernenden und ihren Kompetenzen beruhen. Dieses Empfehlungssystem berechnet den Bedarf an Wissen von Lernenden auf der Basis von historischen Daten von anderen Lernenden. Die zweite Kategorie umfasst Ansätze, die darauf abzielen, mögliche Lernpfade zu empfehlen. Dazu gehören die Ansätze von Janssen [ 68 ] und Huang et al. [ 63 ]. Janssen präsentierte ein Verfahren, das auf der individuellen Lernhistorie beruhend zukünftige Schritte im Lernprozess empfiehlt und Huang et al. versuchen Gruppenlernpfade mit Hilfe von Markov-Ketten zu erkennen. Diese stellen die Wahrscheinlichkeit des Übergangs von einem Lernobjekt zu einem anderen dar. Darüber hinaus wird ein weiteres statistisches Modell benutzt, um neue (unbekannte Pfade) zu erkennen. Schließlich gibt es die dritte Kategorie von Verfahren, die auf die Modellierung von Lernenden setzt. Khribi et al. [ 74 ] greifen auf die Bildung von Benutzerprofilen zurück. Zusätzlich berechnen Sie Ähnlichkeiten zwischen Präferenzen von Lernenden und ihrem Kontext, um hybride Empfehlungslisten (basierend auf kollaborativem Filtern und inhaltbasierten Verfahren) zu erstellen. Jie [ 70 ] hat ein personalisiertes 38 verwandte arbeiten [ 55 ] erstellten eine Ontologie basierend auf einem Biologie-Korpus, der aus Wikipedia extrahiert wurde. Chernov et al. [ 30 ] konzentrieren sich auf die Unterscheidung zwischen „starken“ und „schwachen“ Relationen bei Wikipedia-Kategorien. Diese Unterscheidung wird aufgrund der Anzahl der Links zwischen Artikeln in den Kategorien durchgeführt: Je mehr Links es gibt, desto stärker ist die Relation. Ein weiterer Ansatz ist WikiTaxonomy [ 118 ]. Es basiert auf Heuristiken und benutzt Wikipedia-Kategorien, um aus Wikipedia und dem Tipster-Sprachkorpus 9 Hyponymierelationen zu extrahieren. Der Tipster-Sprachkorpus ist eine Textkollektion aus Nachrichten, Patenten und wissenschaftlichen Beiträgen und wird benutzt, um die Kategorisierung von Hyponymie-Beziehungen zu verbessern. Der WikiTaxonomyAnsatz wurde auf die deutsche [ 73 ] und die japanische [ 172 ] Sprache übertragen. Die Ergebnisse waren aber in beiden Sprachen schlechter, da die Artikel im Deutschen und Japanischen einen geringeren Abdeckungsgrad als im Englischen aufweisen [ 73 , 172 ]. Sumida et al. [ 153 , 154 ] extrahieren Hyponymie-Beziehungen aus der QuellcodeStruktur von Wikipedia-Artikeln. Das Ziel von Sumida et al. war die Extraktion einer großen Menge an Hyponymie-Beziehungen aus der japanischen Wikipedia. Yamada et al. [ 172 ] erweiterten den Ansatz von Sumida, indem WikiTaxonomy benutzt wurde, um weitere Konzepte zur Menge der Hyponymie-Beziehungen hinzuzufügen. Ansätze, die die Erstellung multilingualer Wissensbasen mit Hilfe von Wikipedia zum Ziel haben, sind relativ neu und werden erst seit 2011 publiziert. WikiNet nutzt sehr viele Facetten von Wikipedia: Artikel, Wikilinks, Interwikilinks, das Glossar, Infoboxen, Kategorien und den Kategoriengraph. Wikipedia-Artikel und Kategorien stellen die Konzepte dar. WikiNet [ 106 ] extrahiert zuerst aus der englischen Wikipedia ein monolinguales semantisches Netz aus Konzepten. Anschließend wird mit Hilfe von Interwikilinks (vgl. 2.4.2.2) ein multilinguales semantisches Netz erstellt, indem die Namen der Wikipedia-Artikel als Konzepte in anderen Sprachen hinzugefügt werden (siehe Abb. 17). Fehlende Interwikilinks können zum Teil ergänzt werden, indem überlappende Interwikilinks benutzt werden [ 163 ]. Beispielsweise wenn es keinen direkten Interwikilink zwischen a1 und a3 gibt, kann trotzdem ein Interwikilink inferiert werden, wenn es einen Artikel a2 gibt, der Interwikilinks zu a1 und a3 hat. Die Relationen zwischen den Konzepten werden aus dem Kategoriensystem, den Infoboxen sowie dem Artikeltext extrahiert. Die Relationen werden mit Hilfe lexikalischer Methoden ermittelt. WikiNet zeichnet sich durch die hohe Portabilität aus, da als Basis (für den ersten Schritt nicht nur die englische, sondern) eine beliebige Wikipedia-Version gewählt werden kann. 12 “gd”:“Ain-Riaghailteachd” “en”:“Anarchism” “fr”:“Anarchisme” “it”:“Anarchismo” ... 25 “en”:“Autism” “et”:“Autism” “ca”:“Autisme” “fi”:“Autismi” “es”:“Autismo” ... 39 “lt”:“Albedas” “en”:“Albedo” “ast”:“Albedu” “hu”:“Albed” “et”:“Albeedo” ... 290 “lb”:“A (Buschtaf)” “uz”:“A (harf)” “ku”:“A (herf)” “fr”:“A (lettre)” ... 303 “lb”:“Alabama (Bundesstaat)” “br”:“Alabama (stad)” “ro”:“Alabama (stat SUA)” ... 305 “lt”:“Achilas” “fr”:“Achille” “en”:“Achilles” “scn”:“Achilli” “sl”:“Ahil” ... 307 “en”:“Abraham Lincoln” “lv”:“Abrahams Linkolns” “la”:“Abrahamus Lincoln” ... 308 “ga”:“Arastotail” “uz”:“Arastu” “kab”:“Aristot” “fr”:“Aristote” ... 309 “pl”:“Amerykanin w Paryu (Gershwin)” “nl”:“An American in Paris (Gershwin)” ... 316 “en”:“Academy Award for Best Art Direction” “es”:“Anexo:scar a la mejor direccin de arte” ... 324 “en”:“Academy Award” “id”:“Academy Awards” “tr”:“Akademi dlleri” ... ... Figure 3: The reversed index file contains an ordered listing of numeric IDs and their various lexicalizations. A line starts with a numeric concept ID, and its possible lexicalizations, including variants in other languages, as found in the cross-language links for articles and categories. 12 -FIELD OF STUDY 1072099 1324482 148725 153803 1749719 ... 25 CATEGORY 1267652 15335930 2687547 RELATED TO 640668 ... 39 CATEGORY 1487579 5233412 IS A 716907 7427968 RELATED TO ... 290 -ARTIST 11487620 6309589 ALPHABET 17730 CATEGORY 1476950 ... 303 -EXECUTED BY 16971198 1832115 1936741 2063265 2191317 ... 305 ASSOCIATED WITH 691877 ASSOCIATION 33158 CATEGORY 11262809 ... 307 ASSOCIATED WITH 691877 ASSOCIATION 33158 CATEGORY 1044730 ... 308 ASSOCIATION 24526 CAPITAL 1216 CATEGORY 1013656 10557882 ... 309 AUTHOR 13066 CATEGORY 15590942 1901286 COMPOSER 13066 COUNTRY ... 316 BASED IN 1732034 692361 CATEGORY 6001393 773951 COUNTRY 3173217 ... 324 BASED IN 1732034 692361 CATEGORY 14390148 14952319 773951 ... 330 CATEGORY 1052809 13583794 17176975 22912361 6014666 742885 CITY ... 332 AUTHOR 2511084 CATEGORY 13726390 14001347 4250978 7025604 GENRE ... ... Figure 4: The data file contains a list of relations for each concept (ID), ordered by the ID. Relations are directed. The file contains the relations induced by processing the category structure, categories and infoboxes. The structure of each line is: ID Rel1ID11 ID12 ... ID1nRel2ID21 .... ID is a concept’s ID, Reliare relations from or towards (if the relation is prefixed by “-”) this concept, and IDij are the concepts connected to ID through relation Reli. 12 10001591 100052 10030 1003654 10060195 10072892 1007418 100758 1008 ... 25 10001591 10008586 10013 10037201 1004186 1004482 10048 10055 1005705 ... 39 1000165 10086584 10112744 10180397 1019817 1028264 1028265 103050 ... 290 100935 10306453 103358 10436364 10437467 10576525 1109441 11388236 ... 303 10001591 10003335 10003629 10003649 10006052 1000637 10006781 ... 305 100254 10069798 1009303 10095749 10140510 10141 101411 10150963 ... 308 1000660 100090 1000978 10010856 1001664 100224 10023307 10024702 ... 330 10145549 13169236 14851243 16765178 169568 18948337 1942277 21148681 ... 332 1176603 1210571 12833051 13393902 13591897 14149608 15092767 15550841 ... 333 1046699 2477285 4104030 334 1137594 11807783 1181 1209 1234 12993 1317 1327 1328262 13909226 ... ... Figure 5: The cooccurrence relations file contains an ordered listing of numeric IDs and the concepts they co-occur with within a sentence (in some article). This file contains cooccurrence relations mined from article texts. Each line in the file has the structure: ID ID1... IDnwhere (ID, IDi) appear together in a sentence in an article. 1022 Abbildung 17: Beispiel: Ausschnitt aus WikiNet [106] 9http://www.ldc.upenn.edu/Catalog/CatalogEntry.jsp?catalogId=LDC93T3A - Zugriff am 14.11.2012 3.2 verwandte arbeiten im bereich wissensextraktion 39 Navigli und Ponzetto entwickelten mit BabelNet [108] ein multilinguales semantisches Netz durch eine Aggregation von WordNet, Wikipedia und SemCor 10 . SemCor ist ein Text-Korpus, der per Hand mit WordNet-Synsets indiziert wurde. Zusätzlich zu diesen Quellen wurde die Google Übersetzungschnittstelle 11 (Google Translation Application Programming Interface ( API )) benutzt, um Wikipedia-Artikelnamen zu übersetzen, für die keine Interwikilinks in anderen Sprachen existieren. In Abbildung 18 wird der Erstellungprozess von BabelNet dargestellt: Aus WordNet extrahiert BabelNet Konzepte sowie alle Relationenstypen, die zwischen ihnen existieren. Im nächsten Schritt werden weitere Konzepte aus Wikipedia-Artikel-Seiten sowie weitere semantische (nicht-spezifizierte) Relationen extrahiert. Interwikilinks werden dann benutzt, um Konzepte in verschiedenen Sprachen zu erkennen. Für fehlende Interwikilinks wird, wie oben erwähnt, der Übersetzungsdienst von Google benutzt. Um die Qualität der Übersetzung zu erhöhen, werden Sätze aus SemCor extrahiert, in denen das gesuchte Konzept vorkommt, übersetzt und die in den übersetzten Sätzen am meisten vorkommende Übersetzung wird dann als richtige Übersetzung des Konzepts angenommen. high wind blow gas gasbag wind hot-air balloon gas cluster ballooning Montgolfier brothers Fermi gas is-a has-part is-a is-a Wikipedia WordNet balloon BABEL SYNSET balloonEN, BallonDE, aerostatoES, globusCA, pallone aerostaticoIT, ballonFR, montgolfi` ereFR WIKIPEDIA SENTENCES ...world’s first hydrogen balloon flight. ...an interim balloon altitude record... ...from a British balloon near B´ ecourt... + SEMCOR SENTENCES ...look at the balloon and the... ...suspended like a huge balloon, in... ...the balloon would go up... Machine Translation system Figure 1: An illustrative overview of BabelNet. poor languages with the aid of Machine Translation. The result is an “encyclopedic dictionary”, that provides concepts and named entities lexicalized in many languages and connected with large amounts of semantic relations. 2 BabelNet We encode knowledge as a labeled directed graph G= (V, E)where Vis the set of vertices – i.e. concepts2such as balloon – and E⊆V×R×Vis the set of edges connecting pairs of concepts. Each edge is labeled with a semantic relation from R, e.g. {is-a,part-of ,...,}, where denotes an unspecified semantic relation. Importantly, each vertex v∈Vcontains a set of lexicalizations of the concept for different languages, e.g. {balloonEN, BallonDE,aerostatoES,...,montgolfi` ereFR }. Concepts and relations in BabelNet are harvested from the largest available semantic lexicon of English, WordNet, and a wide-coverage collaboratively edited encyclopedia, the English Wikipedia (Section 3.1). We collect (a) from WordNet, all available word senses (as concepts) and all the semantic pointers between synsets (as relations); (b) from Wikipedia, all encyclopedic entries (i.e. pages, as concepts) and semantically unspecified relations from hyperlinked text. In order to provide a unified resource, we merge the intersection of these two knowledge sources (i.e. their concepts in common) by establishing a mapping between Wikipedia pages and WordNet senses (Section 3.2). This avoids duplicate concepts and allows their inventories of concepts to complement each other. Finally, to enable multilinguality, we collect the lexical realizations of the available concepts in different languages by 2Throughout the paper, unless otherwise stated, we use the general term concept to denote either a concept or a named entity. using (a) the human-generated translations provided in Wikipedia (the so-called inter-language links), as well as (b) a machine translation system to translate occurrences of the concepts within sense-tagged corpora, namely SemCor (Miller et al., 1993) – a corpus annotated with WordNet senses – and Wikipedia itself (Section 3.3). We call the resulting set of multilingual lexicalizations of a given concept a babel synset. An overview of BabelNet is given in Figure 1 (we label vertices with English lexicalizations): unlabeled edges are obtained from links in the Wikipedia pages (e.g. BALLOON (AIRCRAFT) links to WIND), whereas labeled ones from WordNet3(e.g. balloon1 nhaspart gasbag1 n). In this paper we restrict ourselves to concepts lexicalized as nouns. Nonetheless, our methodology can be applied to all parts of speech, but in that case Wikipedia cannot be exploited, since it mainly contains nominal entities. 3 Methodology 3.1 Knowledge Resources WordNet. The most popular lexical knowledge resource in the field of NLP is certainly WordNet, a computational lexicon of the English language. A concept in WordNet is represented as a synonym set (called synset), i.e. the set of words that share the same meaning. For instance, the concept wind is expressed by the following synset: {wind1 n,air current1 n,current of air1 n}, where each word’s subscripts and superscripts indicate their parts of speech (e.g. nstands for noun) 3We use in the following WordNet version 3.0. We denote with wi pthe i-th sense of a word wwith part of speech p. We use word senses to unambiguously denote the corresponding synsets (e.g. plane1 nfor {airplane1 n,aeroplane1 n, plane1 n}). Hereafter, we use word sense and synset interchangeably. 217 Abbildung 18: BabelNet: Überblick über den Erstellungsprozesses bei BabelNet [ 108 ] Multilingual Entity Taxonomy ( MENTA ) [ 98 ] hat als Ziel die Erstellung einer vollständigen multilingualen Taxonomie, bestehend aus Konzepten und Eigennamen. MENTA versucht dieselben Konzepte in verschiedenen Wikipedia-Sprachversionen nicht nur anhand von Interwikilinks, sondern mit Hilfe von weiteren Heuristiken und syntaktischen Regeln, die manuell spezifiziert werden müssen, zu extrahieren. Im Gegensatz zu WikiNet und BabelNet werden nicht Informationen aus der englischen Wikipedia als Basis für die Erstellung der Wissensbasis verwendet, sondern es werden die Informationen aus allen Wikipedia-Sprachversionen genutzt. Informationen, die in mehreren Wikipedia Sprachversionen vorkommen, werden höher gewichtet als Informationen, die nur in einer Sprache vorkommen. Dieser Prozess wird in Abb. 19 gezeigt: Blau gefärbte Konzepte kommen aus WordNet, gelb gefärbte Konzepte sind Wikipedia-Kategorien und orange gefärbte Konzepte stellen Wikipedia-Artikel dar. Rechts sieht man das Ergebnis des Matchings und der Restrukturierung der Konzepte und Relationen. Für die Bestimmung von Hyponymierelationen zwischen den Konzepten werden syntaktische und strukturelle Eigenschaften von Wikipedia und WordNet in Betracht gezogen. MENTA unterscheidet zwischen zwei Typen von Hyponymierelationen: „Subklasse von“ für die Hyponymie-Relation zwischen zwei Konzepten (bspw. „Hund“ und „Tier“) und „Instanz von“ für die Relation zwischen 10 http://www.cse.unt.edu/~rada/downloads.html#semcor - Zugriff am 14.11.2012 11 https://developers.google.com/translate/ - Zugriff am 14.11.2012 40 verwandte arbeiten einem Konzept und einer Instanz (bpsw. „Lassie“ und “Hund“). Interwikilinks werden in Abb. 19 rot dargestellt, während die Kanten aus dem Kategoriengraph blau gezeigt werden. Figure 1: Simplified sample of noisy input from link heuristics Figure 2: Relevant sample of the desired output 3.1.2 Category-Article Linking This function returns 1when x,yare a category and an article, respectively, known to be about the same concept, e.g. the category Abugida writing systems and the article Abugida. This is detected by checking for specific templates on the category page. 3.1.3 Supervised WordNet Disambiguation To see if a Wikipedia article, category, or infobox matches a WordNet synset, we use a linker that assesses their similarity and is trained on a small set of manually labelled training examples to disambiguate possible meanings (see Section 5.2). The linker relies on Ridge Regression [6] to obtain a statistical model from the training examples. As input, it uses three major signals as features. Term Overlap. The term overlap quantifies the degree of overlap between the respective natural language labels. The set of labels for a Wikipedia entity is given by its title (after capitalization detection) and titles of its redirection articles. A set of labels for a WordNet entity is retrieved from the English, Arabic, Catalan, Estonian, Hebrew, and Spanish wordnets (see globalwordnet.org), as well as from MLSN [10]. For a Wikipedia entity xand a WordNet entity y, the term overlap feature is then computed as: X lx∈labels(x) max ly∈labels(y)wx(lx, x)wy(ly, y)sim(lx, ly)(1) Here, sim(lx, ly)is a a simple similarity measure between labels that returns 1if the languages match and the strings match after lemmatizing and removing additional qualifications in parentheses, and 0otherwise. For Wikipedia, the additional label weighting wx generally yields 1, while for WordNet 1/n is returned by wywhen ndifferent meanings of lyare listed. It turns out that determining the right capitalization of terms aids in filtering out incorrect links. WordNet synsets for ‘house’ will then only match articles about houses but not articles about movies or music singles called ‘House’. Cosine Similarity. The cosine vT xvy(||vx|| ||vy||)−1between vectors vx,vyderived for the short description gloss extracted from the English Wikipedia and the gloss/labels provided by WordNet, respectively. The vectors are created using TF-IDF scores after stemming using Porter’s method. Primary Sense Heuristic. The number of unqualified English Wikipedia labels where the WordNet synset is listed as the first (most frequent) noun sense in WordNet. A Wikipedia title like ‘House’ is considered unqualified if it does not include an additional qualification in parentheses, unlike ‘House (novel)’. The most frequent sense of ‘house’ listed in WordNet is much more likely to correspond to Wikipedia’s ‘House’ article than to pages with additional qualifications like ‘House (1977 film)’ or ‘House (novel)’. The former reflects the most important meaning of a word as chosen by Wikipedia editors, and thus is more likely to correspond to the first sense listed in WordNet. Together, these three signals allow us to learn whether a Wikipedia article and a WordNet synset describe the same thing. 3.1.4 Redirect Matching Many projects treat redirects in Wikipedia as simple aliases for an entity. However, many redirects do not share the same referent with the page they redirect to. For instance, there are redirects from Physisist (i.e. human beings) to Physics (a branch of science) and from God does not play dice to Albert Einstein. There are large numbers of redirects from song names to album names or artist names, and so on. We decided to conservatively equate redirects with their targets only in the following two cases. •the titles of redirect and redirect target match after parenthesized substring removal, Unicode NFKD normalization, diacritics and punctuation removal, and lower-case conversion •the redirect uses certain templates or categories that explicitly indicate co-reference with the target (alternative names, abbreviations, etc.) 3.1.5 Infobox Matching This function returns a constant w > 0when an infobox template like Infobox actor is matched with an article or category having a corresponding title, in this case Actor, and 0.0 otherwise. We chose w= 0.5because these links are not as reliable as interwiki links or redirect links. The function does not consider article titles with additional qualifications as matching, so Actor (UML) would not be considered. 3.2 Subclass Link Heuristics Subclass linking functions use simple heuristics to link a class x to its potential parent classes y. 3.2.1 Parent Categories This linker checks if categories are subclasses of their own parent categories as listed in Wikipedia. It first ensures that both x and yare likely to be categories denoting genuine classes. A genuine class like Biologists can have instances as its class members (individual biologists, ontologically speaking, are regarded as instances of Biologists). In contrast, other categories like Abbildung 19: MENTA: Vor und nach dem Matching-Prozess von Konzepten aus verschiedenen Sprachen und Quellen [98] 3.2.4Diskussion und Einordnung dieser Arbeit In den vorherigen Abschnitten wurden verschiedene Verfahren vorgestellt, mit deren Hilfe Wissensbasen aus verschiedenen Quellen gewonnen werden können. Zuerst wurden manuelle Verfahren vorgestellt. Diese Verfahren zeichnen sich durch eine sehr hohe Datenqualität aus, da sie oft durch Experten erstellt werden. Leider bringt die Erstellung durch Experten auch Nachteile mit sich. Zuerst ist die Erstellung durch wenige Personen sowohl zeitals auch kostenintensiv. Meistens begrenzt sich das Wissen von manuell erstellten Wissensbasen auf domainunabhängiges Wissen, so dass möglichst viele Leute von der Wissensbasis profitieren können. Zudem werden neue Begriffe (z.B. iPad) erst langsam der Wissensbasis hinzugefügt. Seit 2005 wurden z.B. in WordNet nur 3000 neue Konzepte hinzugefügt12. Nach den manuellen Verfahren wurden verschiedene automatische (und semiautomatische) Verfahren vorgestellt, um Wissensbasen zu extrahieren oder zu erstellen. Automatische Verfahren, die semantische Relationen aus textuellen Korpora extrahieren, haben sich als nützlich erwiesen, um eine große Menge an Relationen in einer Domain zu erkennen. Die größte Schwäche dieser Verfahren ist die Tatsache, dass sie auf einen „guten“ Korpus angewiesen sind. Um eine allgemeingültige Wissensbasis zu erstellen, müsste man einen Korpus finden, der alle Domains umfasst und realistisch abbildet. In der Realität existiert so ein Korpus nicht, sodass für jede Applikation ein neuer Korpus gebraucht wird. In den letzten Jahren haben Forscher das Potential von Wikipedia als zu verwendendem Korpus erkannt. Mit Hilfe der im Rahmen dieser Arbeit vorgestellten Ansätze zur Generierung von Wissensbasen unter Nutzung der Wikipedia wurden bereits gute Ergebnisse bzgl. der Genauigkeit und der Abdeckung in anderen Arbeiten erreicht [ 118 , 152 , 171 ]. Allerdings erweisen sich diese Ansätze unflexibel in Bezug auf die Portabilität in andere Sprachen [45,55,118,152–154,162,172]. Ansätze, die zusätzlich zu Wikipedia auf andere Wissensbasen wie WordNet oder weitere Sprachkorpora zugreifen, haben den Nachteil, dass sie nicht in andere Sprachen übertragen werden können, da diese Korpora oder Tools oft in anderen Sprachen 12 http://wordnet.princeton.edu/wordnet/man/wnstats.7WN.html - Zugriff am 24.11.2012 3.2 verwandte arbeiten im bereich wissensextraktion 41 nicht verfügbar sind. Darüber hinaus haben die meisten Verfahren die englische Wikipedia-Sprachversion zur Basis. Der Grund dafür ist die Tatsache, dass die englische Wikipedia mit Abstand die größte Wikipedia-Sprachversion ist, sowohl was die Anzahl der Artikel angeht als auch die Anzahl der Autoren. Beispiele dafür sind die multilingualen Ansätze WikiNet und BabelNet. Da aber Wikipedia keine kulturellneutrale Enzyklopedia ist [ 115 ], führt dies dazu, dass sozio-kulturell spezifisches Wissen, das in vielen Wikipedia-Sprachversionen enthalten ist, verloren geht. Sozio-kulturell spezifisches Wissen bezeichnet Wissen, das für ein Land, eine Region, für ein Volk oder eine Kultur relevant ist. Diese Art Wissen existiert nicht immer in der englischen Wikipedia. Beispielsweise gibt es in der englischen Wikipedia keinen Artikel vom Widerstand der Anti-Atom-Bewegung in Deutschland zum „Castor-Transport“, also dem Transport von radioaktiven Abfällen. In E-Learning-Szenarien, so wie sie im Rahmen dieser Arbeit betrachtet werden, ist dieses Wissen sehr wichtig. Mehrsprachige Ansätze, die auf Interwikilinks basieren, haben zusätzlich mit dem Problem zu kämpfen, dass Interwikilinks für viele Artikel nicht existieren. Beispielsweise enthalten nur 51,7% aller deutschen Wikipedia-Artikel einen Interwikilink zum jeweiligen englischen Artikel, umgekehrt sind es aber nur 16,6% [ 143 ]. Aus diesem Grund arbeitet MENTA mit zusätzlichen Heuristiken zur Erkennung von gleichen Konzepten in verschiedenen Sprachen. MENTA ist ein sehr umfassender und vielversprechender Ansatz, allerdings enthält er viele für die meisten Anwendungsszenarien irrelevante Informationen und ist sehr umfangreich (fast 100 GB). MENTA beinhaltet z.B. eine große Menge an Informationen in der aktuellen Sprache des Benutzers für die keine Übersetzungen vorliegen. Außerdem berichten die Autoren von MENTA, dass für die Erstellung von MENTA oft manuelle Ausnahmen formuliert werden, um die Genauigkeit des Verfahrens zu verbessern [98]. Die Methoden zur Bestimmung von Hyponymierelationen aus den verwandten Arbeiten lassen sich in zwei Gruppen einteilen: Verfahren, die nur auf Wikipedia basieren, und Verfahren, die auch externe Quellen heranziehen. Diese Unterscheidung lässt sich sehr gut am Beispiel des WikiTaxonomy-Ansatzes sehen: Auf der einen Seite gibt es Vorverarbeitungsheuristiken, Heuristiken, die auf Namenskonventionen der Wikipedia basieren und Nachverarbeitungsheuristiken und auf der anderen Seite Syntaxund lexiko-syntaktisch-basierte Methoden, die zusätzlich den Tipster-Corpus benutzen. Aus der Analyse dieser Heuristiken lässt sich schließen, dass externe Quellen herangezogen werden, um das „Verständnis“ des Verfahrens zu erhöhen: Während Syntaktische Methoden (vgl. 3.2.3) als sehr akkurat gelten [ 118 , 170 ], werden lexikalisch-syntaktische Methoden benutzt, um zusätzliche Informationen über Namen, Phrasen und Konzepte zu erhalten. Darüber hinaus sind viele dieser Heuristiken sprachabhängig, da sie die Eigenschaften der englischen Sprache und der Namenskonventionen benutzen, die nicht in jeder Sprache gleich sind. Aufgrund der dargestellten Schwäche bestehender Verfahren wurden im Rahmen dieser Arbeit zwei Verfahren entwickelt, die die Anforderungen des Szenarios Ressourcen-basierten Lernens erfüllen. Die Anforderungen werden im folgenden Kapitel analysiert und es wird dargestellt, dass die Eigenschaften der Wikipedia (aktuell, mit großer Themenabdeckung, sozio-kulturell spezifisches Wissen und multilingual) gut geeignet sind, die Anforderungen zu erfüllen. 4 UNTERSTÜTZUNG DES KOLLABORATIVEN RESSOURCEN-BASIERTEN LERNENS IN ONLINE COMMUNITIES »Es ist nicht gut, dass der Mensch alleine sei, und besonders nicht, dass er alleine arbeite; vielmehr bedarf er der Teilnahme und Anregung, wenn etwas gelingen soll.« — Johann Wolfgang von Goethe Diese Arbeit hat das Ziel im Ressourcen-basierten Lernen dem Lernenden die Ressourcen, die innerhalb einer Community bereits verwendet wurden, situationsabhängig zugänglich zu machen. In diesem Kapitel soll nun das Anwendungsszenario des Ressourcen-basierten Lernens in Online-Communities konkret vorgestellt werden und auf seine Eigenschaften analysiert werden. Dazu werden unter anderem die CROKODIL-Lernumgebung, eine Plattform zur durchgängigen Unterstützung der mit dem Ressourcen-basierten Lernen verbundenen Aufgaben des Lernenden, und ihr Einsatz betrachtet. Die Analyse zeigt die Schwächen des bisherigen CROKODIL-Ansatzes zur Empfehlung von Ressourcen auf und stellt ein neues auf der Verfügbarkeit einer Taxonomie basierendes Konzept zur Behebung der Schwächen auf. Abschließend werden die Anforderungen an eine zur Realisierung des Konzeptes zu verwendende Taxonomie selbst dargestellt. 4.1 analyse des anwendungsszenarios und die crokodil-plattform Das Anwendungsszenario dieser Arbeit ist das selbstgesteuerte Ressourcen-basierte Lernen. Zur Unterstützung des Ressourcen-basierten Lernens (siehe Kapitel 2.1) wurde die Communities, Web-Ressourcen und Kompetenzentwicklungsdienste integrierende Lernumgebung ( CROKODIL )-Plattform [ 7 , 8 ] entwickelt, die in diesem Kapitel detailliert vorgestellt wird. Eine Betrachtung der Verwendung der CROKODILLernumgebung erlaubt es, Charakteristika des Ressourcen-basierten Lernens zu bestimmen und Schwächen zu identifizieren. 4.1.1Ziele der Entwicklung der CROKDODIL-Lernumgebung Die CROKODIL -Plattform hat das Ziel, das kollaborative Ressourcen-basierte Lernen mit Web-Ressourcen, wie es in Kapitel 2.1vorgestellt wurde, zu unterstützen. Die CROKODIL -Plattform will den Herausforderungen, die aus dieser Form des selbstgesteuerten Lernens entstehen, begegnen. Rensing et al. [ 129 ] weisen z.B. auf die verschiedenen im Ressourcen-basierten Lernen zu erbringenden Aufgaben hin: Wie in Abbildung 20 gezeigt wird, müssen Lernende nicht nur den aktuellen Informationsbedarf decken, sondern auch andere Aufgaben wie die Planung des Lernprozesses, die Suche nach und die Persistierung von Lernressourcen erfüllen. 43 44 unterstützung des kollaborativen ressourcen-basierten Abbildung 20: Ein Modell zum Ressourcen-basierten Lernen Für alle diese verschiedenen Aufgaben stehen den Lernenden verschiedene Tools und Programme zur Verfügung: • Für die Suche werden Web-Browser und Suchmaschinen verwendet. • Falls die Web-Ressource nicht in HTML-Format vorliegt, braucht der Lernende zusätzliche Programme, um die Datei zu lesen. Bei PDF-Dateien wäre es z.B. ein PDF-Viewer. • Die Annotation und Organisation von Ressourcen kann z.B. erfolgen mit Hilfe von „Social Bookmarking“-Applikationen wie delicious 1 oder Literaturverwaltungsprogrammen wie JabRef 2. • Die Weitergabe an Freunde oder Lernpartner könnte u. a. per Mail oder Wikis [147] geschehen. Es gab bisher keine Applikationen, die den gesamten Prozess des Ressourcenbasierten Lernens bzw. der im Modell genannten Aufgaben unterstützen. Das Ziel der Entwicklung der CROKODIL -Plattform ist es gerade gewesen, alle Schritte des Ressourcen-basierten Lernens zu unterstützen. Da keine andere so umfassende Lernumgebung für Ressourcen-basiertes Lernen bekannt ist, eignet sich CROKODIL im Rahmen dieser Arbeit auch die Anforderungen des Ressourcen-basierten Lernens und die Eigenschaften des Szenarios zu analysieren. 4.1.2Funktionalitäten der CROKODIL-Plattform Die CROKODIL -Plattform ist eine Web-Applikation, die aus einem Web-Portal und einem Firefox-Plugin besteht. Die CROKODIL -Plattform bietet Funktionalitäten typischer „Social Bookmarking“-Systeme wie delicious, angereichert um CommunityFunktionen wie ein Chatund Nachrichtensystem und Funktionen zur Verwal1http://delicious.com/ - Zugriff am 14.11.2012 2http://jabref.sourceforge.net - Zugriff am 14.11.2012 4.1 analyse des anwendungsszenarios und die crokodil-plattform 45 tung von Gruppen und Freundschaften. Darüber hinaus ist in der CROKODIL - Plattform das pädagogische Konzept der Aufgabenprototypen (vgl. [ 127 ]) implementiert, dass die Selbststeuerung der Lernenden unterstützen soll. Die Realisierung der CROKODIL -Plattform basiert auf semantischen Netzen [ 94 , 150 ] zur Datenhaltung. Semantische Netze haben sich in den letzten Jahren als ein guter Ansatz zur Unterstützung des Ressourcen-basierten Lernens etabliert, wie Böhnstedt et al. in [ 17 ] gezeigt haben. In diesem Abschnitt soll kurz auf die verschiedenen Funktionen der CROKODIL-Plattform eingegangen werden. Abbildung 21 zeigt sie im Überblick. Abbildung 21: Die CROKODIL-Plattform 4.1.2.1Planung und Reflektion Lernende in der CROKODIL -Plattform können Aktivitäten erstellen (2), die z.B. die Lernziele des Benutzers darstellen [ 8 ]. Die Aktivitäten erlauben es dem Benutzer seine Recherchen nach Wissensressourcen vorab zu planen. Eine Aktivität kann außerdem Unteraktivitäten haben (3), die Teilaufgaben in der Bearbeitung einer Aktivität darstellen können. Die Reflektion wird dadurch unterstützt, dass sowohl Aktivitäten als auch Wissensressourcen kommentiert werden können (nicht auf dem Screenshot dargestellt). 4.1.2.2Annotierung und Organisation von Ressourcen Im Web gefundene Ressourcen, die von den Lernenden im Ressourcen-basierten Lernen genutzt werden, lassen sich in der CROKODIL -Plattform speichern, beschreiben und mit Hilfe von typisierten Tags annotieren, d.h. . es können ihnen Schlagworte zugeordnet werden. Dadurch erhalten Lernende die Möglichkeit, Ressourcen mit semantischer Information anzureichern [ 18 ]. Darüber hinaus lassen sich Wissensressourcen zu Aktivitäten zuordnen. Die Zuordnung einer Ressource zu einer Aktivität gibt an, dass die Ressource bei der Bearbeitung zu einer Aktivität verwendet wird. 46 unterstützung des kollaborativen ressourcen-basierten 4.1.2.3Suche Die CROKODIL -Plattform bietet eine interne Suche (1), die es den Benutzern erlaubt, nach Ressourcen, Aktivitäten, Benutzern, Gruppen oder Tags zu suchen. Darüber hinaus kann sich der Benutzer alle seine Freunde (7), Gruppen (8), Aktivitäten (9), Ressourcen (10) und Tags (11) anzeigen lassen. Tags lassen sich zur Suche und Navigation benutzen. 4.1.2.4Community-Funktionalitäten Da die CROKODIL -Plattform das Ziel verfolgt, das kollaborative Ressourcen-basierte Lernen, d.h. das Lernen in einer Gruppe, zu unterstützen, bietet es verschiedene Community-Funktionen an: • Lernende können ein eigenes Profil pflegen (6). • Es gibt die Möglichkeit, andere Lernende als Kontakte zu speichern (7). • Lernende können Gruppen bilden (8) und Aktivitäten gemeinsam bearbeiten. • Lernende können miteinander chatten (4) und sich gegenseitig Nachrichten schicken (12) • Die Kommentar-Funktion auf der Gruppenseite kann zur Kommunikation zwischen verschiedenen Gruppenmitgliedern benutzt werden. • Die CROKODIL -Plattform bietet einen Newsfeed mit für den Benutzer potentiell relevanten Informationen über die Aktionen von Lernpartnern oder Kontakten innerhalb der Plattform. 4.1.2.5Zugriff auf Informationen und Empfehlungen Ressourcen, Aktivitäten und Tags werden in der CROKODIL-Plattform mit anderen Benutzern geteilt. Dazu sind entsprechende Zugriffsrechte an Aktivitäten und Ressourcen festzulegen. Ist dies der Fall, können z.B. alle an einer Aktivität beteiligten Benutzer auf die vom Lernenden zugeordneten Ressourcen zugreifen. Ressourcen, die von Benutzern öffentlich verfügbar gemacht wurden, stehen allen anderen Benutzern zur Verfügung. Sie werden mittels der Suchfunktion gefunden oder können über die zugeordneten Tags gelistet werden. Damit kann ein aktiver Zugriff auf Ressourcen und Informationen anderer Lernender realisiert werden. Ergänzend werden in CROKODIL Empfehlungen realisiert, mittels derer Lernende aktiv und in Abhängigkeit von ihrer aktuellen Lernaufgabe auf Ressourcen anderer Lernender hingewiesen werden. CROKODIL verwendet strukturbasierte Empfehlungen auf Basis der Informationen, die im semantischen Netz vorliegen. Bei strukturellen Empfehlungen werden die Kanten zwischen den Knoten traversiert, um zwischenpotenziell interessante, d.h. im Netz in der Nähe befindliche Ressourcen zu finden und den Lernenden vorzuschlagen. Abb. 22 zeigt dafür ein Beispiel. Einem Benutzer, der die Ressource „Semantic Web und E-Learning“ verwendet, könnte die Ressource „Lernen mit Web 2.0“ vorgeschlagen werden, weil beide den gemeinsamen Tag „E-Learning“ verwenden. 4.1 analyse des anwendungsszenarios und die crokodil-plattform 47 KOM – Multimedia Communications Lab 13 Goal: Content-Based Recommendations of Snippets in Knowledge Networks Content-based recommendation Some measure of similarity / relatedness between snippets is needed for recommendation E-Learning Lernen mit Web 2.0 Web 2.0 für E-LearningWeb 2.0 Lebenlanges Lernen Blog entry: e-learning in Web 2.0 Paper excerpt: Web 2.0 for learning Web 2.0 Life long learning TEL E-learning ? Abbildung 22: Zusammenhängendes semantisches Netz 4.1.3Das CROKODIL-Datenmodell Das Datenmodell der CROKODIL -Plattform besteht aus verschiedenen Komponenten. In Abbildung 23 wird das Basismodell der CROKODIL -Plattform als Klassendiagramm vorgestellt. Auf die Darstellung der einzelnen Attribute wird an dieser Stelle verzichtet. Das Basismodell deckt sich in weiten Teilen mit dem in [ 19 ] ausgearbeiteten Modell. In diesem Kapitel wird auf die für diese Arbeit relevanten Elemente (Ressourcen, Tags und Benutzer) eingegangen und auf die Beschreibung der restlichen Elemente (Gruppen, Aktivitäten, etc) verzichtet. Aktor Benutzer Gruppe Tag Objekt Ressource Ort Thema Person Ereignis Typ Aktivität 0..n 0..1 hat Teilaktivität 0..1 0..n ist Teilaktivität von 0..n 0..1 ist freigegegen für / gehört zu Benutzer 0..1 0..n0..n ist Freund von 0..n 0..n ist Mitglied in 0..n 0..n gehört zu Aktivität 0..n 0..n taggt 0..n0..ngetaggt mit 0..n 0..n verwendet 1 1 gehört zu Abbildung 23: Basismodell der CROKODIL-Plattform Im Modell der CROKODIL -Plattform können Ressourcen gespeichert und ihnen typisierte Tags[ 18 ] zugeordnet werden. Typisiertes Tagging verwendet im Gegensatz zu traditionellem Tagging eine anwendungsspezifische Basisontologie von Tagtypen. Mit Hilfe des typisierten Taggings können Benutzer Ressourcen nicht nur mit freien Schlagwörtern taggen, sondern Tags mit eindeutigen Typen wie Personen, Ereignissen, Themen oder Orten verwenden. Im Modell wird weiterhin gespeichert, welcher Aktor ein Objekt (Ressource, Tag oder Aktivität) angelegt hat und ob er Ressourcen mit Tags verschlagwortet hat. Das CROKODIL -Datenmodell kann als Graph dargestellt werden, wobei Benutzer, Tags und Ressourcen als Knoten repräsentiert werden. Die Kanten stellen die Relationen zwischen den Objekten dar und geben beispielsweise an, dass ein Benutzer eine Ressource gespeichert hat, dass ein Benutzer einen Tag benutzt hat bzw. dass eine Ressource mit einem Tag verschlagwortet wurde. Dies soll anhand folgender Abbildung vereinfacht dargestellt werden: 54 unterstützung des kollaborativen ressourcen-basierten 4.3 zusammenfassung In diesem Kapitel wurde die CROKODIL-Plattform als Beispiel für ein System zur Unterstützung des Ressourcen-basierte Lernens in Online-Communities, wie es im Rahmen dieser Arbeit definiert wurde, vorgestellt. Die Analyse der Plattform und ihrer Nutzung ergab, dass Lernende bei der Verschlagwortung von Ressourcen unterschiedliche Begrifflichkeiten verwenden. Diese Tatsache führt dazu, dass Lernende innerhalb einer Community nur eingeschränkt von den Ressourcen anderer Lernender profitieren können. Aus diesem Grund wurde ein Konzept vorgestellt, das die Lücken im semantischen Netz, die aus der Verwendung unterschiedlicher Begriffe resultiert, mittels der Ergänzung hyponymischer Beziehungen schließen soll. Mit Hilfe dieser ergänzten Relationen soll Abhilfe geschaffen werden, um dem Lernenden einen besseren Zugriff auf Ressourcen anderer Lernender zu ermöglichen. Das Konzept verlangt die Verfügbarkeit einer Taxonomie deren Eigenschaften aus den Charakteristika des Anwendungsszenarios Ressourcen-basiertes Lernen abgeleitet wurden. Wie in Abschnitt 3.2.3angemerkt wurde, erfüllt Wikipedia diese Eigenschaften. Die englische Wikipedia deckt mehr als 3Millionen Konzepte ab, jeden Tag kommen 1000 neue Artikel hinzu und es existieren Wikipedia-Versionen in 281 Sprachen. In den verschiedenen Sprachversionen ist sozio-kulturell spezifisches Wissen enthalten. In Abschnitt 3.2.4wurde angesprochen, dass bestehende Ansätze mit Ausnahmen sozio-kulturell spezifisches Wissen nicht oder nicht genügend unterstützen. Ebenso wurde dort MENTA als umfassendster Ansatz analysiert. Die Analyse ergab, dass MENTA für das in Rahmen dieser Arbeit betrachtete Szenario zu „überladen“ ist und auf manuelle Arbeit zurückgreift. Um mit diesen Problemen umzugehen, werden in Rahmen dieser Arbeit zwei Methoden entwickelt und im nachfolgenden Kapitel vorgestellt, die auf einzelne Wikipedia-Versionen unabhängig voneinander angewendet werden können. Da jede Sprache ihre eigene Syntax und Grammatik hat, war das Ziel die Entwicklung eines Ansatzes, der in verschiedenen Sprachen ohne große Änderungen ausgeführt werden kann. Im Gegensatz zu den monolingualen Ansätzen, die in Abschnitt 3.2.3erwähnt wurden, benutzen die in dieser Arbeit entwickelten Verfahren nur Wikipedia als Referenzkorpus und basieren nicht auf externen Korpora oder Werkzeugen. Dies erhöht die Sprachportabilität und macht die Verfahren unabhängig von anderen Parteien. 5 ERKENNUNG VON HYPONYMIEN IN VERSCHIEDENEN SPRACHEN »Taxonomy is described sometimes as a science and sometimes as an art, but really it’s a battleground.« — Bill Bryson In den vorherigen Kapiteln wurde zum einen ein Überblick über die verschiedenen Methoden und Ansätze gegeben, um Wissensbasen zu erstellen und zum anderen wurde das Konzept zur Unterstützung des Ressourcen-basierten Lernens von OnlineCommunities auf Basis von Taxonomien vorgestellt. Basierend auf den Anforderungen des Anwendungsszenarios wurden Wikipedia-basierte Ansätze als geeignet für die Umsetzung des Konzepts identifiziert. In diesem Kapitel werden zwei Verfahren vorgestellt, die ausgehend vom Kategoriengraph der Wikipedia in der Lage sind, Hyponymierelationen im Kategoriengraph zu identifizieren. Als Eingabe wurden für beide Verfahren Kategorienpaare, auch Links (vgl. 2.4.2.5) genannt, verwendet. Die Verfahren entscheiden, ob zwischen den im Kategoriengraphen verlinkten Begriffen eine Hyponymierelation existiert oder ob dies nicht der Fall ist. Mit anderen Worten handelt es sich um die Unterscheidung zwischen is-aund not-is-a-Relationen. 5.1 erkennung von hyponymien auf basis von heuristiken In Abschnitt 3.2.4wurde analysiert, dass externe Quellen zur Erkennung von Hyponymierelationen sehr gute Ergebnisse liefern, aber auch Nachteile wurden beschrieben, bspw. in Bezug auf Portabilität in verschiedene Sprachen. TaxWikiHeur.KOM setzt auf die Substitution von sprachabhängigen und auf externen Quellen basierenden Methoden durch andere Heuristiken, die sprachunabhängig sind und allein auf Nutzung der Wikipedia basieren [36]. 5.1.1Workflow Der Ansatz TaxWikiHeur.KOM besteht aus drei Schritten: Ein Vorverarbeitungsschritt, der irrelevante Kategorien und Links eliminiert, ein Hauptschritt bestehend aus vier Heuristiken und ein Nachverarbeitungsschritt, der weitere is-a-Relationen (transitiv) propagiert. Der gesamte Workflow wird in Abb. 29 dargestellt. Die verschiedenen Schritte werden in den nächsten Abschnitten genauer erläutert. Algorithmus 5.1.1zeigt den TaxWikiHeur.KOM-Algorithmus im Überblick. Die Eingabe des Algorithmus ist eine beliebig große Menge an Links aus dem Kategoriengraph der Wikipedia. Die Ausgabe des Verfahrens ist eine neue Menge von Links, die zusätzlich markiert sind und zeigen, ob zwischen den Kategorien eine Hyponymie-Beziehung existiert. Die Vorverarbeitungsschritte (Zeilen 2-3) verändern 55 56 erkennung von hyponymien in verschiedenen sprachen Filtern von Metakategorien Filtern von Verfeinerungslinks Matching von Lexikalischen Köpfen an richtiger Stelle Matching von Lexikalischen Köpfen an falscher Stelle Matching des ersten Satzes eines Artikels Matching von Kookkurrenzen im Graph Propagierungvon gefundenen Links Vorverarbeitung Nachverarbeitung Abbildung 29: Der gesamte Workflow die Eingabemenge, indem Kategorien und Links eliminiert werden. Die Hauptschritte (Zeilen 4-8) bestehen aus vier Heuristiken und tragen die entsprechenden Markierungen an den Links an. Nachverarbeitungsschritte (Zeilen 9-10) beenden die Prozedur durch Hinzufügen von transitiven Links. Algorithmus 5.1.1TaxWikiHeur.KOM Eingabe: Eine Menge von Links L={(c1,1,c1,2),(c2,1,c2,2), ... , (cn,1,cn,2)} 1:Prozedur TaxWikiHeur.KOM(L) .Vorverarbeitungsschritte 2:Remove_AdminMetacategories(L) 3:Filter_Out_Refinement_Links(L) .Hauptschritte 4:Q=Prepare_Set_For_Labelling(L).Transformiert alle Paare (ci,1,cj,2)in markierte Tripel (ci,1,cj,2,∅) 5:Lexical_Head_Matching(Q) 6:Modifier_Matching(Q) 7:First_Sentence_Matching(Q) 8:Cooccurrence_Matching(Q) .Nachverarbeitungsschritte 9:Link_Propagation_Rule(Q) Ausgabe: Menge von gelabelten Links Q={(c1,1 , c1,2 , k1) , (c2,1 , c2,2 , k2) , ... , (cn,1 , cn,2 , kn)} , wobei ki={0 , 1} angibt, ob zwischen beiden Kategorien eine Hyponymie-Beziehung existiert (1) oder nicht (0). 5.1.2Einzelne Schritte des Algorithmus im Detail In diesem Abschnitt werden die verschiedenen Heuristiken sowie die Vorund Nachverarbeitungsschritte anhand des Beispiels in Abb. 30 erklärt. Dieses Beispiel zeigt einen kleinen Kategoriengraphen, der einen Ausschnitt aus dem tatsächlichen Kategoriengraph der Wikipedia darstellt, aber aus Gründen der besseren Übersichtlichkeit stark verkürzt wurde. Rechtecke stellen in diesem Graph Wikipedia-Artikel dar, während Wikipedia Kategorien durch Ovale repräsentiert werden. 5.1 erkennung von hyponymien auf basis von heuristiken 57 Sachsystematik !Hauptkategorie Kunst Musiker US-Amerikanischer Musiker Michael Jackson Michael Jackson Musik Person als Thema Musiker Abbildung 30: Beispiel-Kategoriengraph Die Menge der Links, also die Eingabe des Verfahrens, lautet wie folgt: L={ ( !Hauptkategorie , Sachsystematik ), ( Sachsytematik , Kunst ),( Kunst , Musik ), ( Musik , Musiker ), ( Musiker , US-Amerikanischer Musiker ), ( Michael Jackson , US-Amerikanischer Musiker), (Michael Jackson,Person als Thema)} 5.1.2.1Vorverarbeitungsschritte Vorverarbeitungsschritt 1(Filtern von administrativen Metakategorien) Der erste Vorverarbeitungsschritt verfolgt das Ziel, den Kategoriengraphen zu säubern, indem Metakategorien, die für administrative Aufgaben benutzt werden, gelöscht werden. Abb. 31 zeigt den exemplarischen Kategoriengraph nach Entfernung der administrativen Metakategorien !Hauptkategorie und Sachsystematik . In der deutschen Wikipedia kennzeichnen die folgenden Präfixe Metakategorien: Wikipedia: , Wikiprojekte: , Artikel: , Listen: , Kategorien: , MediaWiki: , Portal: , Vorlagen: , Hilfe: , Sachsystematik , Räumliche Sachsystematik , Zeitliche Systematik oder ! [ 118 ]. Dieser Vorverarbeitungsschritt ist vergleichsweise einfach und kann in andere Wikipedia-Versionen transferiert werden. Beispielsweise existiert der Präfix Kategorien auch auf Englisch (Categories) und Spanisch (Categorías). Algorithmus 5.1.2Filtern von administrativen Metakategorien in Pseudocode Eingabe: Eine Menge von Links L={(c1,1 , c1,2) , (c2,1 , c2,2) , ... , (cn,1 , cm,2)} , eine Liste P={p1,p2, ... , pk}von Präfixen, die Metakategorien im Wikipedia enthalten 1:Prozedur Remove_AdminMetacategories(L,P) 2:for all (ci,1,cj,2)∈Ldo 3:if lemma(ci,1)oder lemma(cj,1)beginnt mit pa∈Pthen 4:L0=L/{(ci,1,cj,2)} Ausgabe: Menge von Links L0={(c1,1,c1,2),(c2,1,c2,2), ... ,(cn,1,cn,2)} 58 erkennung von hyponymien in verschiedenen sprachen Kunst Musiker US-Amerikanischer Musiker Michael Jackson Michael Jackson Musik Person als Thema Musiker Abbildung 31: Beispiel-Kategoriengraph nach Filterung von administrativen Metakategorien Vorverarbeitungsschritt 2(Filtern von Verfeinerungslinks) Der zweite Vorverarbeitungsschritt hat das Entfernen von Verfeinerungslinks zum Ziel (vgl. Abschnitt 2.4.2.5). Die Heuristik in Pseudocode wird in Algorithmus 5.1.3 angegeben. Der exemplarische Kategoriengraph würde sich auf folgenden Graph reduzieren, denn die Kategorie Person als Thema wird entfernt: Kunst Musiker US-Amerikanischer Musiker Michael Jackson Michael Jackson Musik Musiker Abbildung 32: Beispiel-Kategoriengraph nach Filtern von Verfeinerungslinks Die Sprachunabhängigkeit dieser Heuristik wird dadurch gewährleistet, dass in anderen Wikipedia-Sprachversionen auch Verfeinerungslinks existieren. Es muss nur die in dem Verfeinerungslink auftretende Präposition übersetzt werden. 5.1 erkennung von hyponymien auf basis von heuristiken 59 Algorithmus 5.1.3Filtern von Verfeinerungslinks in Pseudocode Eingabe: Eine Menge von Links L={(c1,1 , c1,2) , (c2,1 , c2,2) , ... , (cn,1 , cn,2)} , die Präposition p , die in einer gegebenen Sprache zur Angabe von Verfeinerungslinks benutzt wird 1:Prozedur Filter_Out_Refinement_Links(L,p) 2:for all (ci,1,cj,2)∈Ldo 3:if lemma(ci,1)or lemma(cj,1)enthält String ” p”then 4:L0=L/{(ci,1,cj,2)} Ausgabe: Menge von Links L0={(c1,1,c1,2),(c2,1,c2,2), ... ,(cn,1,cn,2)} 5.1.2.2Heuristiken Heuristik 1(Matching von lexikalischen Köpfen an richtiger Stelle) Die erste Heuristik basiert auf der in Abschnitt 3.2.2.1vorgestellten Methode des Vergleichs der lexikalischen Köpfe. Wie bereits erwähnt, kann der lexikalische Kopf eine sehr effektive Methode zur Erkennung von is-a-Links [ 118 ] sein. Beispielsweise haben „Französische Revolution“ und „Revolution“ den gleichen lexikalischen Kopf „Revolution“. Algorithmus 5.1.4zeigt den Pseudocode dieser Heuristik. Diese Heuristik muss für die verschiedenen Sprachen adaptiert werden (Zeile 11 in Algorithmus 5.1.4): Bei Kategorien in der englischen Wikipedia ist der lexikalische Kopf in der Regel das letzte Wort, wie bei „Sailboats“, „Water sports“ oder „Historical reenactment groups“. Algorithmus 5.1.4 Matching von lexikalischen Köpfen an richtiger Stelle in Pseudocode Eingabe: Eine Menge von ungelabelten Links L={(c1,1 , c1,2 , ∅) , (c2,1 , c2,2 , ∅) , ... , (cn,1 , cm,2 , ∅)} , eine Liste P={p1) , p2 , ... , pk} von Präpositionen in einer gegebenen Sprache 1:Prozedur Lexical_Head_Matching(L,P) 2:for all (ci,1,cj,2,∅)∈Ldo 3:if lemma(ci,1)enthält pa∈Pthen 4:ci,1=Truncate_Prepositions(ci,1,pa) 5:if lemma(cj,1)enthält pa∈Pthen 6:cj,1=Truncate_Prepositions(cj,1,pa) 7:if lemma(ci,1)enthält Klammern then 8:ci,1=Truncate_Bracketts(ci,1) 9:if lemma(cj,1)0enthält Klammern then 10:cj,1=Truncate_Bracketts(cj,1) 11:if lemma(ci,1) enthält lemma(cj,1) an der Position des lexikalischen Kopfes then . für Deutsch wird getestet, ob lemma(ci,1) = w◦lemma(cj,1) gilt. ◦ stellt die Konkatenation von zwei Zeichen dar und weine beliebige Zeichenkette 12:(ci,1,cj,2,∅)←(ci,1,cj,2,1).Link wird als Hyponymie markiert Ausgabe: Menge von gelabelten Links L0={(c1,1 , c1,2 , 1) , (c2,1 , c2,2 , 1) , ... ,(cn,1,cn,2,1)} 60 erkennung von hyponymien in verschiedenen sprachen Allerdings gibt es einige Ausnahmen zu dieser Regel, zum Beispiel für Kategorien, die Präpositionen enthalten, wie beispielsweise „Sport in Irland“ und „Campaign for Nuclear Disarmament“ oder jene Kategorien, die eine Kategorie mit Hilfe eines Begriffs in Klammern verfeinern wie beispielsweise „Sport (Irland)“. Dieses Problem kann für die meisten Fällen dadurch gelöst werden, dass diese Ausnahmen explizit definiert werden und die restliche Phrase nach der Präposition ignoriert wird oder Begriffe in der Klammer nicht betrachtet werden (Zeilen 3-10 in Algorithmus 5.1.4). Die Wikipedia-Nomenklatur für die Verfeinerung von Kategorien mit Präpositionen und Begriffen in Klammern existieren in anderen Sprachen auch und können dementsprechend genauso in anderen Sprachen behandelt werden. Im exemplarischen Kategoriengraph bedeutet dies, dass der Link ( Musiker , US-amerikanischer Musiker ) als Hyponymie erkannt wird. Die Markierung dieses Links wird in Abb. 33 dargestellt. Kunst Musiker US-Amerikanischer Musiker Michael Jackson Michael Jackson Musik Musiker <<is-a>> Abbildung 33: Beispiel-Kategoriengraph nach Matching von lexikalischen Köpfen an der richtigen Stelle Diese Heuristik funktioniert grundsätzlich auch für andere Sprachen. Die Position des lexikalischen Kopfes muss angepasst werden: In Arabisch steht der lexikalische Kopf am Beginn eines Lemmas einer Kategorie. Bei Sprachen mit zusammengesetzten Wörtern wie der deutschen Sprache muss beachtet werden, dass der lexikalische Kopf sich innerhalb dieses zusammengesetzten Wortes befinden kann. Beispielsweise ist das Wort „Baumhaus“ ein solches zusammengesetztes Wort. Diese Heuristik wird für die deutsche Sprache mit Hilfe eines Matching-Fensters der Länge c1 simuliert. Mit anderen Worten: Ein Kategorienpaar (ci,1 , cj,1) wird als Hyponymie markiert, wenn die letzten c1 -Zeichen der Lemmata identisch sind. Der optimale Wert kann je nach Sprache variieren. Die Experimente für die Parametrisierung auf Deutsch (vgl. Anhang A.1.1) zeigten, dass c=4die besten Ergebnisse produzierte. 5.1 erkennung von hyponymien auf basis von heuristiken 61 Heuristik 2(Matching von lexikalischen Köpfen an falscher Stelle) Die zweite Heuristik basiert auf dem gleichen Ansatz. Lexikalische Köpfe werden aber hier für die Erkennung von Nicht-Hyponymien benutzt. Diese Heuristik überprüft, ob der lexikalische Kopf sich an einer anderen Stelle der Kategorie befindet. Beispielsweise lässt sich mit Hilfe dieser Heuristik erkennen, dass beim Kategorienpaar „Baumhaus“ und „Baum“ keine Hyponymie vorliegt, weil „Baum“ nicht am Ende des Wortes, sondern am Anfang auftritt. Der Algorithmus im Pseudocode wird in Algorithmus 5.1.5) dargestellt. Algorithmus 5.1.5 Matching von lexikalischen Köpfen an falscher Stelle in Pseudocode Eingabe: Eine Menge von ungelabelten Links L={(c1,1 , c1,2 , ∅) , (c2,1 , c2,2 , ∅) , ... , (cn,1 , cn,2 , ∅)} , eine Liste P={p1) , p2 , ... , pk} von Präpositionen in einer gegebenen Sprache 1:Prozedur Modifier_Matching(L,P) 2:for all (ci,1,cj,2,∅)∈Ldo 3:if lemma(ci,1)enthält pa∈Pthen 4:ci,1=Truncate_Prepositions(ci,1,pa) 5:if lemma(cj,1)enthält pa∈Pthen 6:cj,1=Truncate_Prepositions(cj,1,pa) 7:if lemma(ci,1)enthält Klammern then 8:ci,1=Truncate_Bracketts(ci,1) 9:if lemma(cj,1)enthält Klammern then 10:cj,1=Truncate_Bracketts(cj,1) 11:if lemma(ci,1) enthält lemma(cj,1) nicht an der Position des lexikalischen Kopfes then . für Deutsch wird getestet, ob lemma(ci,1) = lemma(cj,1)◦w gilt. ◦ stellt die Konkatenation von zwei Zeichen dar und weine beliebige Zeichenkette 12:(ci,1,cj,2,∅)←(ci,1,cj,2,0).Link wird als Nicht-Hyponymie markiert Ausgabe: Menge von gelabelten Links L0={(c1,1 , c1,2 , 0) , (c2,1 , c2,2 , 0) , ... ,(cn,1,cn,2,0)} Auch diese Heuristik eignet sich für verschiedene Sprachen, wenn man ähnlich wie oben beschrieben ein weiteres Matching-Fenster c2 definiert. Für Deutsch hat beispielsweise c2=6 die besten Ergebnisse geliefert (vgl. Anhang A.1.1). Für andere Sprachen lassen sich einfach Wörter oder Teilwörter benutzen. Im exemplarischen Beispiel (siehe Abb. 34) führt diese Heuristik dazu, dass der Link ( Musik , Musiker ) als Nicht-Hyponymie erkannt wird. 62 erkennung von hyponymien in verschiedenen sprachen Kunst Musiker US-Amerikanischer Musiker Michael Jackson Michael Jackson Musik Musiker <<is-a>> <<not-is-a>> Abbildung 34: Beispiel-Kategoriengraph nach Matching von lexikalischen Köpfen an anderen Stellen Heuristik 3(Matching des ersten Satzes eines Artikels) Die dritte Heuristik basiert auf der Tatsache, dass die Glosse eines WikipediaArtikels (vgl. Abschnitt 2.4.2.1) eine besondere Bedeutung für Hyponymie-Beziehungen hat. Anstatt sprachabhängige Patterns (vgl. Abschnitt 3.2.2.2) für jede Sprache zu definieren, versucht diese Heuristik im ersten Satzes des Artikels [ 109 ] eine HyponymieBeziehung zwischen Kategorien zu finden. Im exemplarischen Kategoriengraph lässt sich mittels der Heuristik bestimmen, dass ( Michael Jackson , US-amerikanischer Musiker , 1 ) gilt, da der erste Satz des Wikipedia-Artikels „Michael Jackson“ wie folgt lautet: „Michael Joseph Jackson (geboren am 29. August 1958 in Gary, Indiana; Gestorben am 25. Juni 2009 in Los Angeles, Kalifornien) war ein US-amerikanischer Musiker, Komponist, Tänzer und Entertainer.“1 Algorithmus 5.1.6Matching des ersten Satzes eines Artikels Eingabe: Eine Menge von ungelabelten Links L={(c1,1 , c1,2 , ∅) , (c2,1 , c2,2 , ∅) , ... , (cn,1 , cn,2 , ∅)} , die einen gleichnamigen Wikipedia-Artikel a(lemma(ci,1)) haben 1:Prozedur First_Sentence_Matching(L,a(lemma(ci,1))) 2:for all (ci,1,cj,2,∅)∈Ldo 3:first_sentence =Get_First_Sentence(a(ci,1)) 4:if first_sentence enthält Teilstring lemma(cj,2)then 5:(ci,1,cj,2,∅)←(ci,1,cj,2,1).Link wird als Hyponymie markiert Ausgabe: Menge von gelabelten Links L0={(c1,1 , c1,2 , 1) , (c2,1 , c2,2 , 1) , ... ,(cn,1,cn,2,1)} Der große Vorteil dieser Heuristik ist die Tatsache, dass eine sprachabhängige Suche nach Pattern nicht benötigt wird, da die Wikipedia-Guidelines in allen Sprachen definieren, dass der erste Satz den Artikel definieren soll. 1http://de.wikipedia.org/wiki/Michael_Jackson - Zugriff am 14.11.2012 5.1 erkennung von hyponymien auf basis von heuristiken 63 Kunst Musiker US-Amerikanischer Musiker Michael Jackson Michael Jackson Musik Musiker <<is-a>> <<not-is-a>> <<is-a>> Abbildung 35: Beispiel-Kategoriengraph nach Matching des ersten Satzes Heuristik 4(Matching von Kookkurrenzen im Graph) Diese vierte Heuristik basiert auf der Ausnutzung der Struktur des Kategoriengraphen. Ponzetto et al. [118] wiesen darauf hin, dass Kookkurrenzen im Graph auf is-a-Relationen zwischen Kategorien hindeuten können. Dies gilt insbesondere, wenn ein Artikel sowohl in einer Kategorie als auch in einer Unterkategorie enthalten ist. Im Beispiel führt diese Heuristik dazu, dass ( Musik , Kunst , 1 ) gilt, da beide Kategorien den gemeinsamen Artikel „Musiker“ haben. Algorithmus 5.1.7Matching von Kookkurrenzen im Graph Eingabe: Eine Menge von ungelabelten Links L={(c1,1 , c1,2 , ∅) , (c2,1 , c2,2 , ∅) , ... , (cn,1,cn,2,∅)},A(ci,j)für ci,j∈L 1:Prozedur Co-occurrences_Matching(L,) 2:for all (ci,1,cj,2)∈Ldo 3:if A(ci,1)∩A(cj,2)6=∅then 4:(ci,1,cj,2,∅)←(ci,1,cj,2,1).Link wird als Hyponymie markiert Ausgabe: Menge von gelabelten Links L0={(c1,1 , c1,2 , 1) , (c2,1 , c2,2 , 1) , ... ,(cn,1,cn,2,1)} Diese Heuristik kann unabhängig von der Sprache angewendet werden. Das Ergebnis dieser Heuristik wird in der folgenden Abbildung dargestellt. 70 erkennung von hyponymien in verschiedenen sprachen WikipediaLinks GermaNet Überprüfte Links Abbildung 39: Links, die sowohl im Kategorien-Graph als auch in GermaNet vorkommen Tabelle 6zeigt einen Überblick der Ergebnisse. Sie zeigt korrekt und inkorrekt klassifizierte Links. Für die Deutsche Wikipedia wurden 90,2% der gelabelten Links korrekt und 9,8% falsch klassifiziert. Allerdings konnte nur der Teil der Wikipedia evaluiert werden, der eine Überlappung mit GermaNet (bzw. WordNet für Englisch) hat (siehe Abb. 39). Ein Link (c1 , c2) wurde genau dann evaluiert, wenn sowohl c1 als auch c2 als Kategorie (Wikipedia) und Konzept (GermaNet und WordNet) existieren. Aus diesem Grund konnten 80.551 (42,8%) der Instanzen nicht überprüft werden. Links, die in einer der Wissensbasen nicht oder nur teilweise vorkommen, wurden als „unbekannte Links“ markiert. Tabelle 6: Vergleich der Ergebnisse mit GermaNet und WordNet Deutsch Englisch Korrekt klassifizierte Links 72731 (90,2%) 439280 (86,8%) Falsch klassifizierte Links 7820 (9,8%) 58550 (13,2%) Unbekannte Links 87802 (52,2%) 613975 (58,1%) Gesamtanzahl Links 168353 1111805 In Tabelle 7wird ein näherer Blick auf die Precision, Recall und F1 -Maß der Links geworfen, die mit WordNet und GermaNet evaluiert werden konnten. Für die deutsche Sprache lag bei is-a-Relationen die Precision bei 93,6% und Recall bei 84,2%. Tabelle 7: Precision, Recall und F1 -Maß beim Vergleich der Ergebnisse mit GermaNet und WordNet Precision Recall F1-Maß Klasse Englisch 52,9%88,2%73,4% is-a 98,9%40,7%69,8% not-is-a Deutsch 93,6%84,2%88,6% is-a 87,9%95,2%91,4% not-is-a Bei der Analyse der Ergebnisse muss man beachten, dass obwohl die Ergebnisse sehr gut sind, sie sich nur auf den Teil der Wikipedia-Links beziehen, die mit GermaNet evaluiert werden konnten. Insgesamt wurden 80.551 Links in der deutschen Sprache überprüft, aber 87.802 Link blieben unüberprüft, da keine vollständige In- 5.2 erkennung von hyponymien auf basis von entscheidungsbäumen 71 formationen über den Link in GermaNet zu finden waren. Das hat zwei Ursachen: Erstens hat Wikipedia eine viel größere Abdeckung als manuell erstellte Wissensbasen und zweitens konnten einige Begriffe nicht gefunden werden, weil sie in einer anderen Schreibweise in GermaNet/WordNet vorliegen. Beispielsweise finden sich die Plural-Formen von manchen Begriffen aus der Wikipedia in GermaNet/WordNet nicht, weil sie nur in der Singular-Form vorliegen. Schließlich überrascht die Tatsache, dass die Precision für Deutsch und Englisch so unterschiedlich ist. Dies war auch beim Vergleich mit dem manuell erstellten Korpus beobachtet worden. Hier fiel auf, dass die parametrisierten Heuristiken verhältnismäßig mehr Links in Deutsch als im Englisch erfassen konnten und die erfassten Links wurden mit einer hohen Qualität klassifiziert. Für die anderen Sprachen gab es keine Möglichkeit (abgesehen von der Position des lexikalischen Kopfes) der Parametrisierung einzelner Heuristiken. Weitere Anpassungen von TaxWikiHeur.KOM an eine bestimmte Sprache können dazu führen, dass die Ergebnisse für diese Sprache verbessert werden. 5.1.5Zusammenfassung In diesem Abschnitt wurde ein multilinguales Verfahren zur Klassifikation von Links im Wikipedia-Kategoriengraph in is-aund not-is-a-Relationen vorgestellt und evaluiert. Es wurde gezeigt, dass Hyponymie-Beziehungen zwischen Wikipedia-Kategorien automatisch mit wenigen Informationen über eine Sprache erkannt werden können. Die Ergebnisse des Verfahren wurden mit Hilfe der manuell erstellen Korpora überprüft. Als Erstes wurde zu diesem Zweck ein zufällig erstellter manuell gelabelter Korpus verwendet und anschließend die von Experten erstellten Wissensbasen GermaNet und WordNet. Die Ergebnisse auf dem manuell erstellten Korpus sind relativ gut, allerdings war der Recall immer kleiner als die Precision, was sich dadurch erklären lässt, dass viele Links nicht durch eine Heuristik erfasst werden konnten. 5.2 erkennung von hyponymien auf basis von entscheidungsbäumen Im vorigen Abschnitt wurde gezeigt, dass die automatische multilinguale Erkennung von Hyponymierelationen im Kategoriengraph grundsätzlich möglich ist. Basierend auf den im vorigen Kapitel gewonnenen Erkenntnissen, wird in den folgenden Abschnitten eine robustere Methode vorgestellt. Zum einen soll das Verfahren auf maschinellem Lernen beruhen und auf diese Weise sicherstellen, dass alle Links durch jedes Feature erfasst werden. Zum anderen werden die Klassifikatoren mit verschiedenen Korpora trainiert, so dass der Klassifikator für jede Sprache anders aussehen wird. Somit erreicht man eine Art „Parametrisierung“ des Verfahrens. Das in diesem Abschnitt vorgestellte Verfahren trägt den Namen TaxWikiML.KOM und verwendet 20 Features, um Hyponymierelationen im Kategoriengraph der Wikipedia zu erkennen [37]. 5.2.1Features Die Eingabe von TaxWikiML.KOM ist, genau wie bei TaxWikiHeur.KOM, eine Menge von Links l= (c1 , c2) aus dem Kategoriengraph der Wikipedia. Diese Links werden 72 erkennung von hyponymien in verschiedenen sprachen in die zwei Klassen is-a oder not-is-a klassifiziert (siehe Abschnitt 2.2.2). Für jeden Link wird ein Featurevektor aus Werten der 20 Features gebildet. In Tabelle 8sind die entwickelten Features im Überblick dargestellt. Nachfolgend werden die einzelnen Features im Detail erklärt. Tabelle 8: Überblick der entwickelten Features ID Name Wertebereich Feature-Typ 1adminCatFeature {0,1}Vorverarbeitung 2refinementLinkFeature {0,1}Vorverarbeitung 3positionOfHeadFeature {2,1,0,-1}Syntaktisch 4coocurrenceOfWordsFeature NSyntaktisch 5coocurrenceArticleFeature {0,1}Strukturell 6commonArticleFeature {1,0,-1}Strukturell 7c1c2IncomingLinksFeature {1,0,-1}Strukturell 8c1c2OutgoingLinksLinksFeature {1,0,-1}Strukturell 9c1distanceCommonAncestorFeature NStrukturell 10 c2distanceToCommonAncestorFeature NStrukturell 11 c1NumberOfSubcategoriesFeature NStrukturell 12 c1NumberOfSuperCategoriesFeature NStrukturell 13 c2NumberOfSubcategoriesFeature NStrukturell 14 c2NumberOfSuperCategoriesFeature NStrukturell 15 CommonWikilinksFeature NStrukturell 16 firstSentenceFeature {0,1}Artikelbasiert 17 RedirectFeature {1,0,-1}Artikelbasiert 18 c2Inc1Feature NArtikelbasiert 19 c1ArticleFeature {0,1}Artikelbasiert 20 c2ArticleFeature {0,1}Artikelbasiert 5.2.1.1Vorverarbeitungsfeatures Es existieren zwei Vorverarbeitungsfeatures, die grundsätzlich den Vorverarbeitungsheuristiken in Abschnitt 5.1.2.1entsprechen. Beide Features liefern den Wert 1 für Links, die administrative Kategorien ( adminCatFeature ) oder Verfeinerungslinks ( refinementLinkFeature ) enthalten, zurück. Die Berechnung der Features erfolgt nach den in Algorithmen 5.2.1und 5.2.2beschriebenen Prozeduren. Diese Features können, wie in Abschnitt 5.1.2.1erklärt, in verschiedenen Sprachen berechnet werden. 5.2 erkennung von hyponymien auf basis von entscheidungsbäumen 73 Algorithmus 5.2.1Berechnung von adminCatFeature Eingabe: Link l={(c1 , c2)} , eine Liste P={p1 , p2 , ... , pk} von Präfixen, die Metakategorien darstellen 1:function adminCatFeature(l,P) 2:if lemma(c1)or lemma(c2)begins with pa∈Pthen 3:return 1 4:else 5:return 0 Ausgabe: Ein Wert w∈{0,1} Algorithmus 5.2.2Berechnung von refinementLinkFeature Eingabe: Link l={(c1 , c2)} , die Präposition p , die in einer gegebenen Sprache zur Angabe von Verfeinerungslinks benutzt wird 1:function refinementLinkFeature(L,p) 2:if lemma(c1)or lemma(c2)enthält String ” p”then 3:return 1 4:else 5:return 0 Ausgabe: Ein Wert w∈{0,1} 5.2.1.2Syntaktische Features Syntaktische Features nutzen die syntaktischen Komponenten der Kategorien, um zwischen is-aund not-is-a-Relationen zu unterscheiden (siehe Abschnitt 3.2.2.1). In diesem Abschnitt werden zwei syntaktische Features vorgestellt: positionOfHeadFeature und coocurrenceOfWordsFeature . Das positionOfHeadFeature nutzt die Tatsache, dass der lexikalische Kopf der Lemmata sehr effektiv zur Erkennung von Hyponymien [ 118 ] verwendet werden kann. Dieses Feature liefert einen Wert zwischen {2 , 1 , 0 , −1} für einen Link l={(c1 , c2)} zurück, der die Position des lexikalischen Kopfes von c2repräsentiert. Wir unterscheiden folgende Fälle: f3(c1,c2) =                2Wenn der lexikalische Kopf von c2am Ende von c1steht 1Wenn der lexikalische Kopf von c2irgendwo in der Mitte von c1steht 0Wenn der lexikalische Kopf von c2am Anfang von c1steht −1sonst, d.h. der lexikalische Kopf kommt gar nicht vor Dieses Feature wird mit Hilfe von Algorithmus 5.2.3berechnet: Beispielsweise berechnet dieser Algorithmus für den Link l={(Franz¨osische Revolution , Revolution)} den Wert 2. In Abschnitt 5.1.2.2wurde angegeben, dass Kategorien Präpositionen oder Klammern enthalten können. Diese Fälle werden entsprechend gesondert behandelt. Es wird, genau wie bei TaxWikiHeur.KOM, angenommen, dass, wenn die Position des lexikalischen Kopfes nicht mit der Position des lexikalischen Kopfes in einer gegebenen Sprache übereinstimmt, es sich bei diesem Link um eine not-is-a-Relation handelt. 74 erkennung von hyponymien in verschiedenen sprachen Algorithmus 5.2.3Berechnung von positionOfHeadFeature Eingabe: Link l={(c1 , c2)} , eine Liste P={p1) , p2 , ... , pk} von Präpositionen in einer gegebenen Sprache 1:function positionOfHeadFeature(L,P) 2:if lemma(c1)enthält pa∈Pthen 3:c1=Truncate_Prespositions(c1,pa) 4:if lemma(c2)enthält pa∈Pthen 5:c2=Truncate_Prespositions(c2,pa) 6:if lemma(c1)enthält Klammern then 7:c1=Truncate_Bracketts(c1) 8:if lemma(c2)0enthält Klammern then 9:c2=Truncate_Bracketts(c2) . Die Funktionen Truncate_Prepositions und Truncate_Bracketts sind wie in Abschnitt 5.1.2.2beschrieben 10:if lemma(c1)endet mit lemma(c2)then 11:return 2 12:else if lemma(c1)beginnt mit lemma(c2)then 13:return 0 14:else if lemma(c1)enthält lemma(c2)then 15:return 1 16:else 17:return −1 . z.B. lemma(c1) = w◦lemma(c2) auf Deutsch/Englisch oder lemma(c1) = lemma(c2)◦w auf Spanisch/Arabisch, wobei w eine beliebige Zeichenkette darstellt Ausgabe: Ein Wert w∈{2,1,0,−1} 5.2 erkennung von hyponymien auf basis von entscheidungsbäumen 75 cooccurrenceOfWords bestimmt Kookkurrenzen von Wörtern in beiden Kategorienamen. Dieses Feature soll Fälle behandeln, in denen die Lemmata zweier verlinkter Kategorien mehrere Wörter gemeinsam haben. Die Funktion zur Berechnung von cooccurrenceOfWords wird in Algorithmus 5.2.4dargestellt. Algorithmus 5.2.4Berechnung von cooccurrenceOfWords Eingabe: Link l={(c1 , c2)} , eine Liste P={p1 , p2 , ... , pk} von Präpositionen in einer gegebenen Sprache 1:function cooccurrenceOfWordsFeature(L,P) 2:if lemma(c1)enthält pa∈Pthen 3:c1=Truncate_Prepositions(c1,pa) 4:if lemma(c2)enthält pa∈Pthen 5:c2=Truncate_Prepositions(c2,pa) 6:if lemma(c0 1)enthält Klammern then 7:c1=Truncate_Bracketts(c1) 8:if lemma(c2)0enthält Klammern then 9:c2=Truncate_Bracketts(c2) 10:occ =0 11:for all w∈lemma(c1)do 12:if w∈lemma(c2)then 13:occ =occ +1 14:if occ ⩾2then 15:return 1 16:else 17:return 0 Ausgabe: Ein Wert w∈{0,1} 5.2.1.3Strukturelle Features Diese Features nutzen die Struktur des Kategoriengraphs zusammen mit dem Wikilinkgraph 6 . coocurrenceFeature liefert den Wert 1 für Links, dessen Kategorien mindestens einen Artikel gemeinsam haben, ansonsten liefert das Feature den Wert 0 zurück. Die Berechnung von coocurrenceFeature wird im Algorithmus 5.2.5dargestellt. 6 Die Struktur der Wikipedia lässt sich als Graph darstellen, wenn Artikel als Knoten und Wikilinks als Kanten angesehen werden. 76 erkennung von hyponymien in verschiedenen sprachen Algorithmus 5.2.5Berechnung von coocurrenceFeature Eingabe: Link l={(c1,c2)} 1:function coocurrenceFeature(L) 2:A1=a(c1).a(c)berechnet alle Artikel zu einer Kategorie. 3:A2=a(c2) 4:if A1∩A26=∅then 5:return 1 6:else 7:return 0 Ausgabe: Eine natürliche Zahl Darüber hinaus wird die Anzahl der gemeinsamen Artikel durch ein eigenes Feature (commonArticleFeature) berechnet (vgl. Algorithmus 5.2.6). Algorithmus 5.2.6Berechnung von commonArticleFeature Eingabe: Link l={(c1,c2)} 1:function commonArticleFeature(L) 2:A1=a(c1).a(c)berechnet alle Artikel zu einer Kategorie. 3:A2=a(c2) 4:occ =|{A1∩A2}| 5:return occ Ausgabe: Eine natürliche Zahl c1c2IncomingLinksFeature und c1c2OutgoingLinksFeature messen die Stärke der Relation zwischen beiden Kategorien. Zu diesem Zweck wird die Anzahl der Artikel in c1 gezählt, die mindestens einen einoder ausgehenden Wikilink zu einem Artikel in c2 haben [ 30 ]. Die Funktionen zur Berechnung dieser Features werden in Algorithmen 5.2.7und 5.2.8vorgestellt. Algorithmus 5.2.7Berechnung von ausgehenden Links Eingabe: Link l={(c1,c2)} 1:function c1c2OutcomingLinksFeature(L) 2:occ =0 3:for all ai∈c1do 4:if aihat ein Wikilink zu einem Artikel aj∈c2then 5:occ =occ +1 6:return occ Ausgabe: Eine natürliche Zahl 5.2 erkennung von hyponymien auf basis von entscheidungsbäumen 77 Algorithmus 5.2.8Berechnung von eingehenden Links Eingabe: Link l={(c1,c2)} 1:function c1c2IncomingLinksFeature(L) 2:occ =0 3:for all ai∈c2do 4:if cihat ein Wikilink zu einem Artikel aj∈c1then 5:occ =occ +1 6:return occ Ausgabe: Eine natürliche Zahl Die Features c1distanceCommonAncestorFeature und c2distanceCommonAncestorFeature berechnen den Abstand zwischen den gegebenen Kategorien c1 und c2 zum ersten gemeinsamen Vorfahren cA beider Kategorien. Die Entfernungen werden einzeln berechnet, d.h. c1distanceCommonAncestorFeature berechnet den Abstand von c1 zu cA und c2distanceCommonAncestorFeature den Abstand c2 zu cA . Ein Beispiel wird in Abbildung 40 gezeigt. Die Berechnung der Distanz findet durch einen adaptierten Breitensuche-Algorithmus [ 32 ] statt. Es werden zwei Breitensuchen im Kategoriengraph ausgehend von c1 und c2 gestartet und besuchte Knoten gespeichert. Die Suche erfolgt solange, bis sich die Wege an einem einzigen Knoten kreuzen. Der Algorithmus wird in 5.2.9angegeben. c1 c2 cA 2 1 Abbildung 40: Entfernung von zwei Knoten zum ersten gemeinsamen Vorfahren Die Features c1NumberOfSubcategories , c1NumberOfSupercategories , c2NumberOfSubcategories und c2NumberOfSupercategories zählen die Anzahl der Unterund Oberkategorien von c1 und c2 . Kategorien mit einer Vielzahl von Unterkategorien repräsentieren in der Regel abstraktere Konzepte, die von vielen anderen Artikeln referenziert werden, wie z.B. „Wissenschaft“. Schließlich zählt das Feature CommonWikilinksFeature die Anzahl der gemeinsamen Wikilinks zwischen c1 und c2. 78 erkennung von hyponymien in verschiedenen sprachen Algorithmus 5.2.9Berechnung des letzten gemeinsamen Vorfahren Eingabe: Link l={(c1,c2)} 1:Prozedur distanceToCommonAncestor(L) .Initialisierung 2:paths1={} 3:paths2={} 4:visitednodes1={} 5:visitednodes2={} .Aktuelle Kategorie hinzufügen 6:path1=Add_Category_To_Path(c1,paths1) 7:path2=Add_Category_To_Path(c2,paths2) 8:visitednodes1=visitednodes1∪c1 9:visitednodes2=visitednodes2∪c2 10:repeat 11:tmp1=Get_Parents(c1,paths1) 12:tmp2=Get_Parents(c2,paths2) 13:for all c1,i∈tmp1do 14:path1=Add_Category_To_Path(c1,i,paths1) 15:visitednodes1=visitednodes1∪c1,i 16:for all c2,i∈tmp2do 17:path2=Add_Category_To_Path(c2,i,paths2) 18:visitednodes2=visitednodes2∪c2,i 19:until ∃cA∈visitednodes1∩visitednodes2 20:distance1=Calculate_Distance_To_Node(cA,paths1) 21:distance2=Calculate_Distance_To_Node(cA,paths2) Ausgabe: Zwei Werte distance1 und distance2 , die den Werten der Features entsprechen 5.2 erkennung von hyponymien auf basis von entscheidungsbäumen 79 5.2.1.4Artikelbasierte Features Diese Menge von Features bestimmt sich aus dem Inhalt der Wikipedia-Artikel. Das erste Feature macht sich die Tatsache wieder zunutze, dass der erste Satz eines Artikels eine Definition des Konzeptes enthält. definitionSentenceFeature gibt an, ob im ersten Satz des Artikels a1 aus Kategorie c1 der lexikalische Kopf von Kategorie c2 vorkommt. Beispielsweise liefert dieses Feature für den Link L= (M¨auseartige , Nagetiere) den Wert 0 zurück, weil „Nagetiere“ im ersten Satz des Artikels zu „Mäuseartige“ vorkommt. Auch hier gilt, dass keine sprachabhängige Suche von Mustern benötigt wird, und das Feature somit in verschiedenen Sprachen angewendet werden kann. Das Feature c2Inc1Feature zählt die Anzahl von Vorkommen der lexikalischen Köpfe von c2 im Rest des Artikels von c1 . Weiterhin geben c1ArticleFeature und c2ArticleFeature an, ob es überhaupt einen Artikel mit den Namen von c1 bzw. c2 gibt. Dass ein Artikel zu einer Kategorie gibt, ist ein Hinweis darauf, dass es sich bei dieser Kategorie um ein Konzept handelt. Sie liefern den Wert 1 zurück, falls ein Artikel zu einer Kategorie existiert, ansonsten den Wert 0 . Zum Schluss gibt RedirectFeature an, ob der Artikel a1 , der die Kategorie c1 beschreibt, zum entsprechenden Artikel a2 weiterleitet, der die Kategorie c2 beschreibt. Dies kann ein Hinweis darauf sein, dass eine Synonymie-Relation zwischen c1und c2besteht. 5.2.2Sprachunabhängigkeit des Verfahrens Der hier vorgestellte Ansatz (TaxWikiML.KOM) ist genauso wie TaxWikiHeur.KOM sprachunabhängig, da der Ansatz auf verschiedene Sprachen ohne Modifizierung der Features angewendet werden kann. Der Ansatz kann benutzt werden, um eine große Menge an taxonomischen Relationen aus der Menge der Links im WikipediaKategoriengraph zu extrahieren. Dazu werden nur folgende wenige Informationen benötigt: 1. Eine Liste von Präfixen, die Wikipedia benutzt, um Metakategorien zu erkennen, wie z.B. „Wikipedia“ oder „Benutzer“(siehe Abschnitt 5.2.1.1). 2. Die Präposition, die in der Sprache S benutzt wird, um Verfeinerungslinks zu definieren. Beispielsweise „by“ für Englisch oder „nach“ für Deutsch (siehe Abschnitt 5.2.1.1). 3. Die Liste aller Präpositionen in Sprache S , um lexikalische Köpfe in komplexen Kategorien heuristisch zu bestimmen (siehe Abschnitt 5.2.1.2). Im Vergleich zum ersten Ansatz braucht TaxWikiML.KOM keine Angabe darüber, wo der lexikalische Kopf in der jeweiligen Sprache zu finden ist. Mit Hilfe von diesen Informationen ist es möglich, Hyponymie-Beziehungen zu erkennen. Die Güte des Verfahrens in verschiedenen Sprachen wird im nächsten Abschnitt dargestellt. 5.2.3Evaluation des Verfahrens TaxWikiML.KOM wurde in fünf verschiedenen Sprachen evaluiert: drei europäische Sprachen (Englisch, Deutsch und Spanisch) und zwei Sprachen mit nicht-lateinischen Schriften (Arabisch, Russisch). Die Evaluation bestand aus drei Schritten: 86 erkennung von hyponymien in verschiedenen sprachen Tabelle 16: Vergleich der Ergebnisse zwischen TaxWikiML.KOM und WikiNet TaxWikiML.KOM WikiNet Korrekt klass. Links 13307 (85,95%) 12113 (78,23%) Inkorrekt klass. Links 2176 (14,05%) 3370 (21,77%) Gesamtanzahl der Links 15483 15483 Tabelle 17 zeigt detaillierte Ergebnisse beider Ansätze für den Evaluationskorpus. Für F1 -Maß lagen die Werte für is-a-Beziehungen bei 80,48% und bei 89,02% für not-isa Beziehungen. Für die englische Sprache lässt sich also sagen, dass TaxWikiML.KOM auf dem Evaluationskorpus besser als WikiNet arbeitete. Leider konnten nur 15.483 von 85.938 Links evaluiert werden. Dafür gibt es hauptsächlich zwei Gründe: Zum einen hat Wikipedia eine viel größere Konzept-Abdeckung als WordNet und zum anderen können viele Wikipedia-Kategorien (z.B. „Das große Buch der deutschen Fußballvereine“) nicht einem WordNet-Synset zugeordnet werden. Tabelle 17: Detaillierte Ergebnisse von TaxWikiML und WikiNet im Vergleich zu WordNet Precision Recall F1-Maß Klasse TaxWikiML.KOM 86,12 %73,54 %80,48 % is-a 85,86 %92,42 %89,02 % not-is-a WikiNet 69,14 %78,29 %73,37 % is-a 85,20 %78,29 %81,60 % not-is-a 5.3 zusammenfassung In diesem Kapitel wurden zwei Verfahren vorgestellt, mit deren Hilfe Hyponymierelationen zwischen Kategorien in Wikipedia erkannt werden können. Im Gegensatz zu anderen Verfahren beruht die Erstellung der Taxonomie weder auf sprachabhängigen Methoden noch auf bereits existierenden (manuell erstellten) Wissensbasen. Beim ersten Verfahren handelt es sich um ein regelbasiertes Verfahren: TaxWikiHeur.KOM, das in der Lage ist, zwischen is-aund not-is-a-Relationen zu unterscheiden. Mit diesem Verfahren wurde gezeigt, dass die multilinguale automatische Erkennung von is-a-Relationen möglich ist. TaxWikiHeur.KOM wurde evaluiert und die Ergebnisse wurden mit einem manuell erstellten Korpus sowie mit zwei von Experten erstellten Wissensbasen verglichen. Darüber hinaus wurden die Grenzen des Ansatzes gezeigt und analysiert. Auf der Basis der bei TaxWikiHeur.KOM gewonnenen Erkenntnisse wurde ein weiterer Ansatz, TaxWikiML.KOM, entwickelt. TaxWikiML.KOM besteht aus einem trainierten binären Klassifikator, der mit Hilfe einer Reihe von Features automatisch taxonomische Beziehungen zwischen Paaren aus dem Wikipedia-Kategoriengraph erkennen kann. Das Verfahren zeichnet sich dadurch aus, dass man mit wenigen Informationen über eine Zielsprache und ohne externe Quellen eine Klassifikation 5.3 zusammenfassung 87 von Links vornehmen kann. Wie im ersten Fall wurde die Evaluation mit Hilfe von manuell und automatisch erstellten Korpora durchgeführt. Beide Verfahren ermöglichen die Ableitung von Taxonomien aus Wikipedia für verschiedene Sprachen durch Benutzung von syntaktischen und strukturellen Regeln. Im Rahmen dieser Arbeit wurden diese Verfahren für die Erstellung von Taxonomien zum Einsatz im Ressourcen-basierten Lernen in Online Communities benutzt. Allerdings sind auch andere Szenarien denkbar: Sie kann z.B. benutzt werden, um weitere automatisch erstellte Wissensbasen zu evaluieren. Insbesondere für Sprachen, wo keine manuell erstellten Wissensbasen zum Vergleich existieren oder nicht verfügbar sind. Im nächsten Kapitel wird detailliert erklärt, wie die erstellte Taxonomie in der CROKODIL-Plattform eingesetzt wird. 6 IMPLEMENTIERUNG UND PROOF-OF-CONCEPT »The classification of facts and the formation of absolute judgments upon the basis of this classification [...] essentially sum up the aim and method of modern science.« — Karl Pearson InKapitel 4wurden bereits die Funktionen der CROKODILPlattform und das im Rahmen dieser Arbeit entwickelte Konzept zur Steigerung der Zugreifbarkeit auf Ressourcen im Ressourcen-basierten Lernen in online Communities durch die Verwendung von Taxonomien beschreiben. In diesem Kapitel wird zunächst in Abschnitt 6.1die bestehende Architektur der CROKODIL-Plattform sowie die in dieser Arbeit vorgenommene Erweiterung der Architektur vorgestellt. Abschnitt 6.2beschreibt die im Rahmen dieser Arbeit implementierte Erweiterung des CROKODIL-Datenmodells sowie die zusätzliche Realisierung von Ressourcenempfehlungen. Die verschiedenen implementierten Erweiterungen zum Export der von den Benutzern in CROKODIL verwendeten Tags, die Prüfung auf Hyponomiebeziehungen zwischen diesen, die mittels einer mit Hilfe des im vorhergehenden Kapitel beschriebenen Verfahrens bestimmten Taxonomie-Datenbank erfolgt, sowie die Integration der gefundenen Relationen in das CROKODIL-Modell erläutert Abschnitt 6.3. 6.1 crokodil-komponenten und erweiterte architektur Die Architektur der CROKODIL -Plattform, inkl. der Empfehlungssysteme, besteht aus verschiedenen Komponenten, die in Abbildung 42 dargestellt sind. In einer semantischen Datenbank werden die der CROKODIL -Plattform zu Grunde liegenden semantischen Informationen gespeichert. Das Web-Portal und der Net-Navigator erlauben dem Benutzer die Manipulation der Plattformindividuen und die Navigation im semantischen Netz innerhalb seines Browsers. Web-Services dienen zur Kommunikation mit dem Backend und damit zur Anbindung weiterer Dienste. Im Rahmen dieser Arbeit wurden ergänzend eine Taxonomiedatenbank realisiert, welche die mit Hilfe des in Kapitel 5vorgestellten Verfahrens TaxWikiML.KOM klassifizierten Beziehungen zwischen den Wikipedia-Kategorien enthält, und verschiedene Tools, CrokoTaxTools genannt, die zur Manipulation der Datenbank und Anbindung an CROKODIL dienen. Sie werden detailliert in Abschnitt 6.3dargestellt. 89 90 implementierung und proof-of-concept KOM – Multimedia Communications Lab 5 Eure Aufgabe: Unterstützung der kollaborativen Recherche im Web Semantische Datenbank Knowledge Builder Knowledge Portal REST API Net Navigator Web-Services Browser Taxonomie-- Datenbank CrokoTaxTools K-Infinity Abbildung 42: Gesamtarchitektur der CROKODIL-Plattform 6.1.1CROKODIL-Komponenten CROKODIL basiert auf K-Infinity, was eine Technologieplattform der Firma intelligent views 1 zur Vernetzung und Verwaltung von Wissen in Wissensnetzen ist. K-Infinity und damit auch die CROKODIL-Plattform setzt sich aus den folgenden Komponenten zusammen: • einer semantischen Datenbank, die das Wissensnetz speichert, • Werkzeugen zur Modellierung des Wissensnetzes und zur Definition von sogenannten Expertensuchen • Schnittstellen für den Zugriff auf das Wissensnetz durch externe Anwendungen, • einem Web-Portal als Frontend für die Visualisierung und die Bearbeitung von Entitäten des Wissensnetzes durch die Nutzer, • einer graphischen Visualisierung und Navigationsschnittstelle für das semantische Netz (Net-Navigator). K-Infinity ist plattformunabhängig, da die Komponenten in Java und Smalltalk implementiert wurden. Während das Web-Portal das Web-Interface der CROKODIL - Plattform ist, wird eine Knowledge Builder genannte Applikation zur Modellierung von Wissensnetzen genutzt. Mit dem Knowledge Builder können Wissensnetzknoten (im Fall von CROKODIL sind das Ressourcen, Tags, Aktivitäten usw.) und Relationen erzeugt, bearbeitet und gelöscht werden. Wissensnetzknoten werden in K-Infinity u.a. in Begriffe und Individuen unterteilt. Für jeden Wissensnetzknoten (Begriffe und Individuen) können Attribute und Relationen definiert werden. Während die Begriffe ähnlich wie Klassen gemeinsame Attribute von Individuen zusammenfassen, bilden die Individuen den tatsächlichen Inhalt des Wissensnetzes. 1http://www.intelligent-views.com - Zugriff am 14.11.2012 6.1 crokodil-komponenten und erweiterte architektur 91 Mittels des Knowledge Builders lassen sich außerdem die sogenannten Expertensuchen definieren. Eine Expertensuche erlaubt die Zusammenstellung von Begriffen, Individuen, Relationen und Attributen zu geschachtelten, feststehenden Suchanfragen, deren Ergebnisse sich dynamisch ändern, wenn neue Individuen oder Relationen angelegt oder gelöscht werden. Die Ergebnisse der Expertensuchen können im Portal in eigenen Bereichen angezeigt werden. Abbildung 43 zeigt die Definition einer Expertensuche in der CROKODIL -Plattform. Die dargstellte Expertensuche in Abb. 43 liefert alle Themen von Ressourcen, die ein gemeinsames Thema mit einer gegebenen Ressource teilen. Abbildung 43: Eine einfache Expertensuche im Knowledge Builder Ein wichtiger Vorteil von Expertensuchen ist die Tatsache, dass die Ergebnisse Mengen sind und K-Infinity Mengenoperatoren anbietet, mit denen sich Expertensuchen beliebig kombinieren lassen. Beispielsweise lassen sich die Vereinigung und die Schnittmenge von Expertensuchen bilden. Das graphische Anzeigen der Wissensnetze übernimmt der Net-Navigator. Wie der Name schon andeutet, kann der Net-Navigator die Wissensnetze nicht nur anzeigen, sondern erlaubt das Navigieren durch ein Wissensnetz. Die Objekte eines Wissensnetzes und ihre Verbindungen miteinander werden als Graph dargestellt. Abbildung 44 zeigt einen Ausschnitt aus einem Wissensnetz im Net-Navigator. Ein Benutzer „renato“ besitzt eine Ressource über Web-Didaktik. Darüber hinaus teilen sich „renato“ und „Christoph R.“ einen Tag „Ressourcen-basiertes Lernen“ vom Typ Thema. Benutzer „Christoph R.“ hat eine Ressource „PERKAM“ mit dem Thema „context-based learning“ getaggt. K-Infinity bietet die Möglichkeit, Web-Services zu definieren, die mittels einer RESTAPI 2 den Zugriff auf die Backend-Datenbank erlauben. REST-Services können über URLs 3 adressiert angesprochen werden. Eine direkte Manipulation von Objekten ist nicht vorgesehen. Jeder Zugriff muss indirekt über die dem Objekt zugeordnete URL erfolgen. Eine zentrale Bedeutung bei REST haben die HTTP-Methoden GET, POST und DELETE. Sie stellen die Funktionen dar, die auf die Objekte angewendet werden können. GET steht für den Aufruf von Informationen, POST für das Einfügen von Informationen und DELETE für das Löschen von Informationen. Für eine komplette Beschreibung von REST wird an dieser Stelle auf [132] verwiesen. Mit Hilfe der REST-API lassen sich also die Informationen, d.h. Objekte und Relationen, abrufen. In Abschnitt 6.3wird die Nutzung der Web-Services zur Realisierung der auf Taxonomie-basierenden Empfehlungen erläutert. 2REpresentational State Transfer Architektur (REST) 3Uniform Resource Locator (URL) 92 implementierung und proof-of-concept Abbildung 44: Ausschnitt eines Wissensnetzes im Net-Navigator 6.1.2Die Taxonomiedatenbank Die Taxonomiedatenbank ist eine SQL-Datenbank, die alle aus der Wikipedia relevanten Informatioonen enthält, die für TaxWikiML.KOM notwendig sind sowie die von TaxWikiML.KOM klassifizierten Links zwischen den Wikipedia Kategorien enthält. Der Wikipedia-Korpus wurde als XML-Dump von der Wikipedia-Dump-Seite 4 heruntergeladen. Die notwendigen Informationen wurden in einem Vorbereitungsschritt in eine MySQL-Datenbank überführt. Die relevanten Tabellen für die deutsche Sprache werden in Abbildung 45 dargestellt. PS steht dabei für Primärschlüssel und FS für Fremdschlüssel. Jede der Tabellen enthält spezifische Informationen: de_lemma enthält alle Kategorien und Artikel mit ihren jeweiligen IDs, de_article enthält zusätzlich den Inhalt der Artikel, de_wikilink stellt die Wikilinks dar, also Verweise von einem Artikel zu einem anderen, de_redirect enthält die Weiterleitungen von einem Artikel zu einem anderen und schließlich de_category , die den Kategoriengraph darstellt. Die Tabelle de_category enthält eine zusätzlichen Spalte, die mittels WikiTaxML.KOM berechnet wurde und die angibt, ob es zwischen zwei Kategorien eine Hyponymie gibt oder nicht. de_wikilink PS id FS1 FS2 artid targetid linktext de_lemma PS artid name de_category PS id FS1 FS2 artid catid isHyponomy de_redirect PS id FS1 FS2 artid targetid lemma de_article PS,FS artid name content Abbildung 45: Struktur der Datenbanktabellen 4http://dumps.wikimedia.org/ - Zugriff am 14.11.2012 6.2 erweiterung des datenmodells und realisierung von empfehlungen 93 6.2 erweiterung des datenmodells und realisierung von empfehlungen In Kapitel 4wurde das Grundkonzept dieser Arbeit beschrieben, das darin besteht erkannte Hyponomiebeziehungen zwischen Tags dem CROKODIL-Wissensnetz hinzuzufügen und auf Basis dieser hinzugefügten Relationen dem Lernenden Ressourcenempfehlungen anzubieten. Diese beiden Implementierungsaspekte werden nachfolgend dargestellt. 6.2.1Erweiterung des Datenmodells Die mittels eines Vergleichs mit der Taxonomiedatenbank bestimmten taxonomischen Beziehungen zwischen Tags werden unmittelbar im Datenmodell gespeichert. Ergänzend werden sie dazu benutzt, eine Ähnlichkeit zwischen Ressourcen zu berechnen. Die Ähnlichkeit wird durch die existierende Entfernung in der Taxonomie der die Ressourcen beschreibenden Tags bestimmt. Diese Relation wird später von Expertensuchen benutzt, um neue Empfehlungen zu generieren.5 Das bestehende CROKODIL Datenmodell muss daher an zwei Stellen erweitert werden: Die erweiterten und die neuen Klassen sind in Abbildung 46 dargestellt. Es ist eine Assoziationsklasse is-a mit einem Attribut Distanz neu hinzugekommen. Die Distanz gibt die Entfernung zwischen zwei Tags in der Taxonomie an und wird mit Hilfe einer Breitensuche berechnet (siehe Abschnitt 6.3.2.1). Die Ähnlichkeit zwischen Ressourcen oder allgemeiner Objekten wird mit Hilfe zweier Relationen quellObjekt und aehnlicheObjekte modelliert. Tag + tagInTaxonomie Objekt Ressource + ressourceInTaxonomy 0..1 0..1 ist-ein + distanz Ähnlichkeit TaxonomieÄhnlichkeit 1..n1 1 quellObjekt 0..n ähnlich zu + stärke Abbildung 46: Erweiterung des Basismodells der CROKODIL-Plattform Ähnlich wie bei den is-a-Relationen wird auf für die Ähnlichkeitsrelation ein numerisches Attribut, dass die Stärke oder die Ähnlichkeit zwischen den Objekten angibt, benötigt. Die Erstellung der Ähnlichskeitsrelation wird in Detail in Abschnitt 6.3.2.2 erklärt. Zusätzlich ist mittels eines weiteren Attributs checkTaxonomy zu speichern, ob die Ähnlichkeit zwischen zwei Objekten, d.h. zwei aus der CROKODIL-Plattform exportierten Tags bereits berechnet wurde. Bei der Erstellung Ähnlichkeitsrelationen zwischen Ressourcen kann es im schlimmsten Fall passieren, dass Relationen zwischen alle Paare von Ressourcen gezogen werden müssen. In diesem wären die Expertensuchen nicht mehr performant ausführbar. Um dieses Problem umzugehen, wurde die Entscheidung getroffen, die Ähnlichkeits5 94 implementierung und proof-of-concept relation nicht direkt zwischen zwei Objekten zu speichern, sondern Hilfsobjekte zu definieren, die zum einen mit einem Quellobjekt verbunden sind und zum anderen mit allen zu diesem Quellobjekt ähnlichen Ressourcen. Diese Hilfobjekte besitzen zudem einen spezifischen Typ entsprechend des Verfahrens, mittels dessen die Ähnlichkeit berechnet wurde. Konkret wurde eine Taxonomieähnlichkeitsklasse definiert, deren Instanzen sowohl mit einem sogenannten Quellobjekt (Quellobjekt-Relation) als auch mit einem oder mehreren Objekten, die ähnlich zum Quellobjekt sind, über Relationen verbunden sind. An dieser Stelle soll das mit Hilfe eines Beispiels gezeigt werden: KOM – Multimedia Communications Lab 2 Next Steps 5 http://www.google.com http://www.bing.com http://www.yahoo.com TaxonomieÄhnlichkeit quellobjekt Abbildung 47: Beispiel der Benutzung des Ähnlichkeitsobjekts Die Ressource „http://www.google.com“ ist das Quellobjekt einer Taxonomieähnlichkeit, die zu zwei ähnlichen Objekten führt. Darüber hinaus lässt sich die Stärke als Attribut der „ähnliches zu“-Relation speichern, sodass die Ähnlichkeit zwischen verschiedenen ähnlichen Objekten verglichen werden kann. 6.2.2Generierung von Empfehlungen Empfehlungen werden in der CROKODIL-Plattform grundsätzlich mit Hilfe von Expertensuchen generiert. Das gilt bereits für die in Abschnitt 4.1.2.5beschriebenen Empfehlungen. An dieser Stelle wird erläutert, wie die Ähnlichkeitsrelation zwischen Objekten verwendet wird, um weitere Empfehlungen zu generieren. Eine Expertensuche (siehe Abb. 48) wird benutzt, um alle Ähnlichkeitsobjekte zu einem gegebenen Objekt zurückzuliefern. Das Objekt beschreibt den „Kontext“ der aktuellen Suche. Abbildung 48: Expertensuche nach Objekten der Taxonomieähnlichkeit 6.2 erweiterung des datenmodells und realisierung von empfehlungen 95 Da in der CROKODIL -Plattform verschiedene Algorithmen zur Berechnung von Ähnlichkeiten realisiert sind, können diese Ergebnisse vereinigt, anhand ihrer Stärke (z.B. ist dies abhängig von der Distanz in der Taxonomiedatenbank) gerankt und dem Benutzer angezeigt werden. Allerdings muss sichergestellt werden, dass Ressourcen in der gleichen Aktivität oder in Oberund Unteraktivitäten nicht empfohlen werden, da diese keinen Mehrwert für den Benutzer bringen. Zu diesem Zweck wird eine zweite Expertensuche gebildet (siehe Abb. 49) und anschließend die Differenz zwischen der ersten und der zweiten Ergebnismenge gebildet. Das Ergebnis wird dem Benutzer als Empfehlung angezeigt. Abbildung 49: Expertensuche nach Ressourcen in der gleichen Aktivität Die Empfehlungen erscheinen in der CROKODIL -Plattform als sogenannte Kontextboxen. Abbildung 50 zeigt einen CROKODIL -Screenshot zur Ressource „Bing“. Auf der rechten Seite sieht man eine Kontextbox „Empfehlungen“. In Abbildung 51 wird diese Kontextbox größer dargestellt. Sie zeigt eine Empfehlung auf die ähnliche Wissensressource „Google“. Diese Empfehlung wird angezeigt, weil die Ressourcen „Bing“ und „Google“ mit den Tags „Suchmaschine“ bzw. „Google“ getaggt. Aus der Taxonomie ließ sich zudem ableiten, dass „Google“ eine „Suchmaschine“ ist. Aus diesen Informationen erzeugt das hier vorgestellte Verfahren ein Ähnlichkeitsobjekt zwischen den Ressourcen „Bing“ und „Google“. Abbildung 52 zeigt den Ausschnitt des semantischen Netzes im Knowledge Builder der Relationen zwischen „Bing“ und „Google“. 102 evaluation der nutzung der taxonomie im anwendungsszenario 2004 -2007 im renommierten Journal ACM Transactions on Information Systems 1 (ACM TOIS) publizierten Forschungsartikel über Empfehlungssysteme analysiert. Drei Viertel aller Artikel wurden mit Hilfe von historischen Daten evaluiert. Die Evaluation anhand historischer Daten gilt als vergleichsweise einfach durchführbar und beliebig wiederholbar. Ein Algorithmus kann mit beliebig vielen Parametrisierungen getestet werden. Darüber hinaus lässt sich auf diese Weise die Qualität von zwei Empfehlungssystemen unter den genau gleichen Bedingungen vergleichen. Bei der Evaluation mit historischen Daten werden die Evaluationsmetriken und -maße aus dem Information Retrieval (vgl. Abschnitte 2.2.3) benutzt, um sicherzustellen, dass die Messungen verlässlich sind und nicht durch Ausreißer verfälscht werden. Dafür baut die Evaluation von Empfehlungssystemen grundsätzlich auf die im Abschnitt 2.2.4vorgestellte k-fache stratifizierte Kreuzvalidierung oder Varianten dieser [ 134 ] auf. Robuste und stabile Aussagen werden durch die zufällige Aufteilung der Proben und die Tatsache, dass die Experimente k-mal durchgeführt werden, erreicht. In diesem Vorgehen liegt auch der Nachteil von Evaluationen mit historischen Daten: Die zur Evaluation verwendeten Daten stammen aus Anwendungen, die ohne Empfehlungssystem oder mit Hilfe anderer Empfehlungssysteme erhoben wurden. Das bedeutet, dass ein neues Empfehlungssystem hohe Precisionund Recall-Werte liefert, wenn es dieselben Items wie die alten (bzw. keine) Empfehlungssysteme empfehlen kann. Dies führt aber dazu, dass Empfehlungssysteme, die neue (unbekannte) Items empfehlen, nicht mit Hilfe historischer Daten evaluiert werden können. Empfehlungssysteme, die auf die Interaktion mit den Benutzern basieren (wie z.B. [ 23 , 26 , 44 ]), lassen sich ebenfalls nicht mit historischen Daten evaluieren. Diese Empfehlungssysteme erwarten Angaben von Benutzer (oft in Form von Fragen), um Empfehlungen generieren zu können. 7.1.2Benutzerevaluationen Benutzerevaluationen lassen sich in Online-Evaluationen und Benutzerstudien einteilen [ 131 ]. Beide haben gemeinsam, dass die Qualität der Empfehlungen durch die Benutzer explizit oder implizit angegeben oder bestimmt wird. Online-Evaluationen bezeichnen Studien, die im laufenden Betrieb einer Anwendung gemacht werden. Das Ziel ist es, aus dem Verhalten des Benutzers Aussagen abzuleiten. Zum Beispiel, wenn die Benutzer eines Systems einen bestimmten Typ von Empfehlungen mehr anklicken als einen anderen, dann lässt sich schlussfolgern, dass dieses Empfehlungssystem den anderen überlegen ist. Online-Evaluationen mit realen Benutzern gelten als der strengste Beweis der Qualität eines Empfehlungssystems [ 131 ]. Allerdings sind die Ergebnisse einer Online-Evaluation nur aussagekräftig, wenn sich viele Benutzer daran beteiligen. Darüber hinaus hängen die Ergebnisse von vielen Faktoren, wie dem Benutzerverhalten, dem Benutzer-Kontext, dem Interface und der Usability der Plattform, ab. Zusammenfassend lässt sich sagen, dass Online-Evaluationen eher benutzt werden, wenn die Wirksamkeit von Empfehlungssystemen im Langzeiteinsatz evaluiert werden soll [131]. Eine Benutzerstudie wird typischerweise durchgeführt, indem eine Menge von Probanden gebeten wird, bestimmte Aufgaben mit Hilfe eines Empfehlungssystems zu erledigen. Während die Probanden die verschiedenen Aufgaben erledigen, wird 1http://tois.acm.org/ - Zugriff am 14.11.2012 7.2 ziele und evaluationsmethodik 103 ihr Verhalten beobachtet und dokumentiert. Die Aufgaben hängen vom Typ der zu empfehlenden Items ab: Es kann sich z.B. um die Auswahl eines Internetproviders anhand von Empfehlungen [ 43 ] oder die Suche nach Produkten in einem OnlineKatalog [ 119 ], handeln. Die Ergebnisse (z.B. die Anzahl der korrekt bearbeiteten Aufgaben oder wie schnell eine Aufgabe gelöst werden konnte) werden dann numerisch ausgewertet und ggf. mit den Ergebnissen mit einer Baseline oder einem anderen Empfehlungssystem verglichen. Benutzerstudien haben den Vorteil, dass sich das Verhalten der Benutzer gut auswerten und vergleichen lässt, haben aber auch einige Nachteile. Benutzerstudien sind oft sehr kostspielig, da die Probanden zuerst angeworben und häufig bezahlt werden müssen. Aus diesem Grund können die Szenarien nur wenige Male durchgespielt werden, was die Verlässlichkeit der Ergebnisse vermindert [ 131 ]. Darüber hinaus ist die Auswahl der Probanden von höchster Wichtigkeit, da sie die Benutzer des realen Systems repräsentieren sollen. Ansonsten wären die Ergebnisse nicht vertrauenswürdig. 7.1.3Fazit In diesem Abschnitt wurden die beiden grundsätzlichen Methoden zur Evaluation von Empfehlungssystemen vorgestellt und deren Vorund Nachteile diskutiert. Die Evaluation mit Hilfe von historischen Daten überprüft, ob bereits gefundene Items in einem Datensatz gefunden werden. Das im Rahmen dieser Arbeit entwickelte Konzept hat zum Ziel, generelle und spezifische Ressourcen zu empfehlen. Aufgrund der Tatsache, dass nur eine kleinere Menge an Ressourcen zu empfehlen ist, werden die Precisionund Recallwerte eher niedrig sein. Dieses Ergebnis ist unkritisch, weil ein strukturbasiertes Verfahren nicht alleine das Ressourcen-basierte Lernen unterstützen kann. Es sind ergänzend weitere Empfehlungssysteme nötig, wie z.B. Empfehlungen auf Basis der Ähnlichkeit von Ressourcen [ 146 ] oder aktivitätsbasierte Empfehlungen [ 9 ]. Eine Benutzerevaluation würde unter demselben Problem leiden: Entweder würden die Benutzer nicht optimal in ihrem Lernprozess unterstützt, wenn nur das strukturbasierte Verfahren benutzt wird, oder wenn mehrere Empfehlungssystem im Einsatz sind, dann ist die Messung der Wirkung von einzelnen Empfehlungssystemen in Benutzerstudien grundsätzlich schwer nachweisbar [131]. Aus diesem Grund konzentriert sich die in diesem Kapitel beschriebene Evaluation darauf nachzuweisen, dass Hyponymien benutzt werden können, um semantische Netze anzureichen, so dass Empfehlungssysteme von der umfangreichreicheren Struktur profitieren können. Die genutzte Evaluationsmethodik wird im nächsten Abschnitt vorgestellt. 7.2 ziele und evaluationsmethodik Die im Rahmen dieser Arbeit adressierten Forschungsfragen wurden in Kapitel 4wie folgt formuliert: • Wie können alle Lernenden trotz der Verwendung unterschiedliche Begriffe von den in der Community gespeicherten Informationen profitieren, indem sie auf Ressourcen von anderen Lernenden aufmerksam gemacht werden. 104 evaluation der nutzung der taxonomie im anwendungsszenario • Wie kann die Menge der potentiell relevanten Lernressourcen in den Suchergebnissen erweitert werden, wenn eine Suche keine oder wenige Treffer liefert, indem dem Lernenden zum Beispiel nicht nur Treffer angezeigt werden, die seinen Suchstring enthalten. • Wie lassen sich hierarchische Strukturen zwischen Themen erkennen, um generelle von spezifischen Ressourcen zu unterscheiden und diese Information den Lernenden zu geben Zum Nachweis der Nützlichkeit der Taxonomie zur Erweiterung des Wissensnetzes und der darauf basierenden Empfehlungen wurde in der vorliegenden Arbeit eine mehrstufige Evaluationsmethodik angewendet. Im ersten Schritt werden die zuvor genannten Ziele in messbare Evaluationsziele übersetzt, so dass eine Verbesserung tatsächlich festegestellt werden kann. Lernende können von den in der Community gespeicherten Ressourcen profitieren, wenn sie strukturbasierte Empfehlungen bekommen. In der vorgestellten Implementierung werden Empfehlungen mit Hilfe von strukturbasierten Expertensuchen (siehe Abschnitt 6.2.2) bestimmt. Strukturbasierte Verfahren beruhen auf einer möglichst dichten Struktur des benutzten Graphen [ 69 ]. Daher wurden folgende Evaluationsziele definiert: 1. Die Evaluation soll zeigen, dass is-a-Relationen tatsächlich die Struktur des vorliegenden Wissensnetzes verdichten (durch mehr Kanten) und auf diese Weise mehr strukturbasierte Empfehlungen bestimmt werden können. Dazu wird die Dichte des Netzes gemessen. 2. Die Evaluation soll zudem zeigen, dass strukturbasierte Empfehlungssysteme von den zusätzlichen is-a-Relationen im semantischen Netz profitieren können. Die Dichte von Graphen ist ein in der Forschung zu strukturbasierten Empfehlungssystemen in verwandten Arbeiten [ 9 , 60 , 135 ] anerkanntes Maß. Wenn strukturbasierte Empfehlungssysteme evaluiert werden, erfasst die Evaluation nicht den gesamten Anwendungsdaten, sondern nur einem sogenannten p-Core von Level k ([ 15 ]). Ein p-Core von Level k stellt einen Untergraphen dar, bei dem jeder Knoten mit mindesten k anderen in Verbindung steht. Somit wird eine hohe Dichte im Evaluationskorpus garantiert und es ist sichergestellt, dass falsche Empfehlungen nicht aus der Struktur des Graphen resultieren. In einer realen Anwendung, wie z.B. der CROKODIL-Plattform, ist eine hohe Dichte sehr unwahrscheinlich (siehe 7.2.1). Die Evaluation erfolgt mittels verschiedener CROKODIL-Korpora: Ein Korpus aus der öffentlichen CROKODIL-Plattform und jeweils zwei weiteren Korpora aus den CROKODIL-Anwendungsszenarien [ 8 ]. Auf diese Weise soll sichergestellt werden, dass verschiedene inhaltliche Themenbereiche abgedeckt werden. So ist sichergestellt, dass die Ergebnisse unabhängig von der Inhaltsdomäne und von den angewendeten Szenarien sind. Für jeden Korpus wird gemessen, inwieweit sich der Zusammenhang des semantischen Netzes nach dem Hinzufügen von is-a-Relationen verändert. Zum Nachweis des zweiten Evaluationsziels wird gezeigt, dass ein State-of-the-Art strukturbasiertes Empfehlungssystem mittels der ergänzten is-a-Relationen verbessert werden kann. Zur Bewertung werden Evaluationsmaße aus dem Information Retrieval und Verfahren der Evaluation mit historischen Daten benutzt (vgl. Abschnitte 2.2und 7.1.1). Mittels dieses Vorgehens lassen sich anhand der größeren Anzahl von Experimenten 7.2 ziele und evaluationsmethodik 105 validere Aussagen zur Nützlichkeit des Ansatzes machen. In den folgenden Unterabschnitten werden die Extraktion der Korpora und weitere im Rahmen der Evaluation benutzte Hilfsverfahren beschrieben. 7.2.1Auswahl und Erzeugung der Korpora Die CROKODIL-Plattform bildet, wie in Kapitel 4erläutert, das Szenario „Ressourcenbasiertes Lernen in Online-Communities“ ab. Aus diesem Grund wurde das Konzept in der CROKODIL-Plattform integriert und evaluiert. 7.2.1.1CROKODIL-Korpora Insgesamt wurden drei verschiedene Korpora aus der CROKODIL-Plattform extrahiert und zum Zwecke der Evaluation aufbereitet: •CROKp steht für den aus der öffentlichen CROKODIL-Instanz extrahierten Korpus. In dieser Instanz können registrierte Benutzer beliebige Ressourcen speichern und verwalten. •CROK1 entspricht dem in den Szenarien 3und 4in [ 8 ] ermittelten Korpus. Bei den Nutzern handelt es sich um Lernende, die in duale Studiengänge im Bereich der „Business Administration“ und der „Elektround Informationstechnik“ eingeschrieben sind. •CROK2 bezeichnet den Korpus, der in den Szenarien 1und 2aus dem gleichen Paper entstanden ist. In den Szenarien handelt es sich um Umschulungen im Bereich Informationstechnologie mit Lernphasen von maximal einem Tag. In der CROKODIL-Plattform sind die Daten in einem semantischen Netz gespeichert. Um zur Erreichung des Evaluationsziels 2die CROKODIL-Korpora auf bestehende Empfehlungssystem anzuwenden, wird das semantische Netz in eine Folksonomie überführt. Die Überführung des semantischen Netzes der CROKODIL-Plattform in eine Folksonomie erfolgte bereits in anderen Arbeiten [ 9 , 134 ]. In Abschnitt 2.3.8 wurde eine Folksonomie formell als ein 4-Tupel definiert: F={U , T , R , Y} , wobei U die endliche Menge der Benutzer, T die endliche Menge der Tags, R die endliche Menge der Ressourcen in der Folksonomie darstellt. Y ist eine ternäre Relation Y∈U×R×T , die die Tag-Zuweisungen von Benutzern an Ressourcen repräsentiert. Die Menge P ist dabei die Menge der Posts. Um Empfehlungssalgorithmen, die auf Basis von Folksonomien arbeiten, bei der Evaluation im Rahmen dieser Arbeit verwenden zu können, ergibt sich die Einschränkung, dass Kanten die Form (u , t , r)∈Y (für einen Benutzer u , ein Tag t und eine Ressource r ) haben müssen und somit Kanten zwischen Tags nicht erlaubt sind. Daher wird die folgende Prozedur 7.2.1benutzt, um in CROKODIL existierende Kanten zwischen Tags als ternäre Relation innerhalb der Korpora der CROKODIL-Plattform abzubilden. 106 evaluation der nutzung der taxonomie im anwendungsszenario Algorithmus 7.2.1 Prozedur zur Abbildung von Hyponymien als ternäre Relationen Eingabe: Liste von Paaren aus Tags, die durch eine Hyponymierelation verbunden sind L={(t1,t2),...,(tn,tm)} 1:Prozedur Convertion_To_Folksonomy_Relation(L) 2:O={} .Ausgabeliste 3:for all (ti,tj)∈Ldo 4:usersi=Get_Users_Using_Tag(ti) 5:resourcesi=Get_Users_Using_Tag(ti) 6:for all users ui∈usersido 7:for all resources ri∈resourcesido 8:e=Create_Folksonomy_Relation(ui,t2,ri) 9:L=L∪e 10:usersj=Get_Users_Using_Tag(tj) 11:resourcesj=Get_Users_Using_Tag(tj) 12:for all users uj∈usersjdo 13:for all resources rj∈resourcesjdo 14:e=Create_Folksonomy_Relation(uj,t2,rj) 15:L=L∪e Ausgabe: Eine Liste mit ternäre Relationen O Somit wird sichergestellt, dass eine Hyponymie-Relation zwischen den Tags t1 und t2als ternäre Relationen abgebildet wird: •(uj , t1 , rj) , wobei uj und rj alle Ressourcen bzw. Benutzer, die mit t2 verbunden sind •(ui , t2 , ri) , wobei ui und ri alle Ressourcen bzw. Benutzer, die mit t1 verbunden sind Auf diese Weise wird das Gewicht einer Hyponymie auf alle Ressourcen und Benutzer übertragen, die mit diesen Tags verbunden sind. Tabelle 18 zeigt den Umfang der zur Evaluation verwendeten Korpora. |S| (engl. subgraphs) gibt an, aus wieviel nicht verbundenen Teilgraphen die Korpora bestehen. Tabelle 18: Eigenschaften der benutzten Korpora Datensatz |U| |T| |R| |Y| |P|Datum |S| CROKp22 300 203 2877 986 01.10.2012 3 CROK124 93 113 1701 722 01.10.2012 1 CROK229 78 53 439 238 01.10.2012 2 7.2.2Verwendete Algorithmen und Tools Das zweite zuvor genannte Evaluationsziel besteht darin, den Einfluss von zusätzlichen Hyponymierelationen auf strukturbasierte Empfehlungssysteme zu bestimmen. Dazu soll ein State-of-the-Art für strukturbasierte Empfehlungen Verfahren benötigt. 7.2 ziele und evaluationsmethodik 107 In [ 134 ] gibt Rodenhausen einen Überblick über existierende Ansätze. Rodenhausen kommt zu dem Schluss, dass FolkRank sich am besten für die Aufgabe der Ressourcenempfehlung in CROKODIL eignet. FolkRank zeichnet sich u.a. durch Flexibilität bzgl. der Eingaben des Empfehlungssystems und durch stabile Ergebnisse in verschiedenen Szenarien aus. Aus diesen Gründen wird es auch im Rahmen dieser Arbeit zur Evaluation verwendet. 7.2.2.1FolkRank FolkRank ist ein graphbasiertes Verfahren, das von Hotho et al. in [ 60 ] vorgestellt wurde. Es basiert auf dem PageRank-Algorithmus [ 111 ], der für das Ranking von Webseiten entwickelt wurde. Dabei wird das Web als ein ungerichteter Graph, bei dem die Webseiten durch Links (Kanten) verbunden sind, betrachtet. Die zugrundeliegende Idee dahinter ist, dass ein Hyperlink von einer Webseite a zu einer Internetseite b auch die Übertragung von Autorität oder Vertrauen von a nach b darstellt. Auf diese Weise werden Webseiten, die viel referenziert werden, höher gerankt als Webseiten, die wenig referenziert werden. Die Kernidee des FolkRank-Algorithmus ist die Transformation der graphischen Struktur der Folksonomie (siehe Definition2.3.8) zu einem ungerichteten, gewichteten, tripartiten Graphen G= (V , E) . Dabei stellen die Ressourcen, Tags und Benutzer der Folksonomie die Knoten des Graphen dar ( v=U∪T∪R ). Die Menge der Kanten wird durch E={{u , t} , {t , r} , {u , r}|(u , t , r)∈Y} gegeben. Das Gewicht w für jede Kante wird durch die Häufigkeiten in der Menge der Kanten vorgegeben. Das Gewicht für eine Kante zwischen einem Benutzer u und einem Tag t wird durch die Anzahl der Ressourcen bestimmt, die u mit t getaggt hat ( w(u , t) = |{r∈R|(u , t , r)∈Y}| ). Entsprechend berechnet man w(t , r) und w(u , r) als die Anzahl der Benutzer, die Ressource r mit t getaggt haben bzw. als die Anzahl der Benutzer u , die die Ressource rgetaggt haben. Für die Berechnung von FolkRank wird der Graph als normalisierte Adjazenzmatrix A dargestellt, sodass jede Spalte 1ergibt. Der Algorithmus startet mit einem beliebigen Vektor waus nicht-negativen Zahlen. FolkRank iteriert wie folgt: w←dAw + (1−d)p, wobei pein Präferenzvektor mit ||w||1=||p||1ist und d∈[0,1]ein Parameter, durch den der Einfluss von pbegrenzt werden kann. Auf dieser Basis kann FolkRank ein Knoten-spezifischer Ranking (Benutzer-, Ressourcen, oder Tags-spezifisch) in Folksonomien wie folgt berechnen: 1.pspezifiziert einen Präferenzknoten des Benutzers. 2.w0ist das Ergebnis von FolkRank für d=1. 3.w1ist das Ergebnis von FolkRank für d < 1. 4.w=w1−w0ist der finale Gewichtungsvektor und somit der FolkRank. Für Zwecke der Evaluation wird im Rahmen dieser Arbeit der Standard-FolkRankAlgorithmus mit einer Standard-Parametrisierung 2 verwendet. Als Präferenz-Vektor 2http://dev.nepomuk.semanticdesktop.org/wiki/CommunityManager - Zugriff am 14.11.2012 108 evaluation der nutzung der taxonomie im anwendungsszenario wird immer der Benutzer, für den die Empfehlungen berechnet werden, mit einem doppelten Gewicht (als alle anderen Knoten) ausgewählt. 7.2.2.2FReSET FReSET 3 ist ein Evaluationsframework zur Bewertung Folksonomie-basierte Empfehlungssysteme, das im Rahmen dieser Arbeit entwickelt wurden [ 34 ]. FReSET standardisiert die Evaluation mit historischen Daten und erlaubt die Vergleichbarkeit verschiedener Empfehlungssysteme. Darüber hinaus können Vorverarbeitungsalgorithmen, sogenannte Filter, die die Anpassung von Datensätzen erlauben, definiert werden. Beispielsweise kann das p-Core einer Folksonomie berechnet werden, sodass nur Knoten betrachtet werden, die mit mindestens k anderen in der Folksonomie verbunden sind. Des Weiteren können beliebige Empfehlungssysteme in das Framework als Plugin integriert werden. FReSET berechnet die Standardmaße des Information Retrieval als Evaluationsmaße für die verwendeten Korpora und Verfahren. Eine graphische Ausgabe (vgl. Abb. 57) der Ergebnisse steht zur Verfügung, um die Ergebnisse für den Benutzer verständlicher zu machen. Abbildung 57: FReSET Screenshot des F1-Graphs FReSET wurde im Rahmen dieser Evaluation verwendet, um die Qualität von FolkRank bei Verwendung der verschiedenen Korpora zu berechnen, wobei die Korpora mit und ohne ergänzte Hyponymierelationen genutzt werden. 7.3 ergebnisse In diesem Abschnitt werden die Ergebnisse der Evaluation vorgestellt. Als Erstes wird gezeigt, dass die Folksonomien in den Evaluationskorpora nach Erkennung von is-a-Relationen zwischen Tags tatsächlich dichter werden. Anschließend wird auf die Verbesserungen der strukturbasierten Empfehlungen eingegangen. 3Folsonomy-based REcommender System Evaluation Tool 7.3 ergebnisse 109 7.3.1Evaluation bzgl. der Dichte des semantischen Netzes Zunächst wurde die Dichte der einzelnen Folksonomien gemessen. Die Dichte dn(G) eines Graphen G gibt das Verhältnis der Kantenzahl von G zur Kantenzahl eines vollständigen Graphen 4 [ 21 ]. dmin und dmax stellen den Knoten mit dem jeweils kleinsten bzw. größten Grad dar. Darüber hinaus bezeichnen davg und dmed den Durchschnitt der Grade aus allen Knoten im Graph bzw. den Median der Grade allen Knoten im Graph. Ein Überblick wird in Tabelle 19 gezeigt. Tabelle 19: Struktur der benutzten Korpora Datensatz dmin dmax davg dmed dn CROKp1 296 16,44 3 12,45 CROK11 232 22,19 14 5,51 CROK21 45 8,23 3 1,08 Es lässt sich erkennen, dass obwohl der maximale Grad eines Knotens ( dmax ) relativ hoch ist, der Durchschnitt ( davg ) und insbesondere der Median ( dmed ) weit davon entfernt liegen. Wie Jäschke et al. in [ 69 ] angemerkt haben, leiden viele strukturbasierte Empfehlungssysteme darunter, dass die Graphen nicht dicht sind. Aus diesem Grund betrachten sie nur Korpora, die einen p-Core von mindestens Level 5 haben, um „die Chancen auf gute Empfehlungen zu erhöhen“. Diese Eigenschaft erfüllt keiner der Korpora. Als Folge davon ist es möglich, dass zu manchen Objekten nur entfernte (und somit weniger relevante) Objekte empfohlen werden könnten. Tabelle 20 zeigt die Eigenschaften der Korpora, nachdem Hyponymierelationen, mittels des in Abschnitt 6.3vorgestellten Frameworks, erkannt und in der Graphenstruktur eingefügt wurden. In allen Korpora ließen sich Hyponymien finden. Bei den kleineren Korpora wurden weniger Hyponymierelationen gefunden. Durch die Hyponymierelationen wuchsen in allen Korpora sowohl die Anzahl der Kanten als auch die Anzahl der Posts. In den in der Evaluation benutzten Korpora konnte die Anzahl der Untergraphen nicht reduziert werden, da die gefundenen Hyponymierelationen alle im gleichen Untergraphen lagen. Sollten die Tags einer Hyponymie-Relation in verschiedenen Untergraphen liegen, kann auch die Anzahl der Untergraphen reduziert werden. Tabelle 20: Eigenschaften der benutzten Korpora nach der Erkennung von Hyponymierelationen Datensatz |Y| |Yalt| |P| |Palt| |U| |Ualt|Hyponymien CROKp2951 2877 1042 986 3 3 2 CROK11813 1701 786 722 1 1 1 CROK2443 439 240 238 2 2 1 In CROKp und CROK1 war der Knoten mit den meisten Kanten Element der erkannten Hyponymierelationen. Dies lässt sich in Tabelle 21 durch die Vergrößerung von dmax erkennen. Dies erklärt auch, warum in beiden die Anzahl der Relationen so 4In vollständigen Graphen ist jeder Knoten mit alle anderen Knoten im Graph direkt verbunden. 110 evaluation der nutzung der taxonomie im anwendungsszenario gewachsen sind. Bei CROK2 war der Knoten mit den meisten Kanten nicht Element einer Hyponymierelation und somit wuchs die Anzahl der Kanten nur um vier. Während dmed für alle Korpora gleich blieb wuchs, erhöhte sich davg in jedem Fall. Tabelle 21: Dichte der benutzten Korpora nach der Erkennung von Hyponymierelationen Datensatz dmax dmax,alt davg davg,alt dmed dmed,alt dn dnalt CROKp301 296 16,86 16,44 3 3 12,77 12,45 CROK1237 232 23,65 22,19 14 14 6,56 5,51 CROK245 45 8,30 8,23 3 3 1,09 1,08 Zusammengefasst lässt sich sagen, dass Hyponymierelationen tatsächlich in der Lage sind, die Struktur der Netze im Anwendungsszenario „Ressourcen-basiertes Lernen in Online Communities“ zu verdichten und somit weitere Empfehlungen zu ermöglichen. In den nächsten Abschnitten soll untersucht werden, ob die Verdichtung der Struktur auch zu besseren Empfehlungen von Ressourcen und Tags in strukturbasierten Empfehlungssystemen führt. 7.3.2Empfehlungen anhand eines Empfehlungssystems Die Auswirkungen der Ergänzung von Hyponymierelationen in der Folksonomie wurden mit Hilfe von FolkRank bewertet. Dazu wurden zuerst die Gütemaße von FolkRank bei der Verwendung der Korpora ohne Hyponymierelationen berechnet und anschließend für die Korpora mit den erkannten Hyponymierelationen berechnet. Die Ergebnisse wurden wiederum einer zehnfache stratifizierten Kreuzvalidierung unterzogen, in der für jeden Benutzer die Ressourcen bzw. die Tags in 10 Folds aufgeteilt werden und, wie in Abschnitt 2.2.4erläutert nacheinander, mehrfach berechnet. In den Tabellen 28,30,32 sind die durchschnittlichen Werte der berechneten Maße Precision, Recall, F1 -Maß bei Anwendung von FolkRank auf die Korpora ohne Hyponymien dargestellt. Die Tabellen 22,24 und 26 zeigen die entsprechenden Ergebnisse für die k-ersten-Empfehlungen. Precision, Recall, F1 -Maß und bei k= 1 sind die Gütemaße wenn nur den ersten Treffer einer Empfehlungsliste in die Evaluation einbezogen wird. k=10 bedeutet entsprechend, dass die ersten 10 Treffer für die Evaluation relevant sind. In Evaluation wurde also angenommen, dass höchsten die ersten 10 Empfehlungen für einen Benutzer relevant sind. Höhere Werte von k wären zwar möglich und würden zu besseren Ergebnissen führen, aber laut einer Studie [ 67 ] ist es so, dass knapp 70% der Nutzer nur an den ersten 10 Treffern einer Trefferliste interessiert sind. 7.3 ergebnisse 111 Tabelle 22: Ergebnisse für CROKp ohne Hyponymien k Precision Recall F1-Maß 1 0,1285 0,0425 0,0556 2 0,1017 0,0414 0,0468 3 0,1224 0,0705 0,067 4 0,1412 0,1274 0,0943 5 0,1548 0,1615 0,1137 6 0,161 0,1881 0,1266 7 0,1679 0,2124 0,1386 8 0,1688 0,2268 0,1454 9 0,1705 0,2386 0,153 10 0,1699 0,2403 0,1574 Tabelle 23: Ergebnisse für CROKp mit Hyponymien k Precision Recall F1-Maß 1 0,1404 0,0449 0,0591 2 0,0938 0,0426 0,0475 3 0,1155 0,0739 0,0691 4 0,142 0,1378 0,102 5 0,1534 0,1621 0,1144 6 0,161 0,1897 0,1277 7 0,1656 0,2083 0,137 8 0,1655 0,2214 0,1426 9 0,16 0,225 0,143 10 0,1651 0,2299 0,1517 Tabelle 24: Ergebnisse für CROK1 ohne Hyponymien k Precision Recall F1-Maß 1 0,3234 0,0662 0,1031 2 0,2711 0,1123 0,145 3 0,2604 0,1603 0,1768 4 0,2264 0,1908 0,1793 5 0,199 0,2149 0,1771 6 0,1963 0,2947 0,1963 7 0,1665 0,2113 0,1535 8 0,1694 0,237 0,1645 9 0,1749 0,278 0,1792 10 0,1734 0,2978 0,1836 Tabelle 25: Ergebnisse für CROK1 mit Hyponymie k Precision Recall F1-Maß 1 0,3333 0,0561 0,0907 2 0,2917 0,1125 0,1462 3 0,2934 0,1656 0,1871 4 0,2591 0,1887 0,1915 5 0,2354 0,2098 0,1922 6 0,2287 0,2785 0,2083 7 0,2143 0,2498 0,1969 8 0,2138 0,2887 0,2093 9 0,2109 0,3112 0,2151 10 0,2031 0,279 0,2033 LITERATURVERZEICHNIS [1] Adafre, S. F. ; Rijke, M. de: Finding Similar Sentences across Multiple Languages in Wikipedia. In: Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics,2006, S. 62–69 [2] Adar, E. ; Skinner, M. ; Weld, D. S.: Information Arbitrage across Multi-lingual Wikipedia. In: Proceedings of the Second ACM International Conference on Web Search and Data Mining ACM, 2009, S. 94–103 [3] Adomavicius, G. ; Tuzhilin, A.: Context-Aware Recommender Systems. In: Proceedings of the 2008 ACM conference on Recommender systems, Springer, 2011, S. 217–253 [4] Aehnelt, M. ; Ebert, M. ; Beham, G. ; Lindstaedt, S. ; Paschen, A.: A SocioTechnical Approach towards Supporting Intra-Organizational Collaboration. In: Times of Convergence. Technologies Across Learning Contexts 5192 (2008), S. 33–38 [5] Anderson, M. ; Ball, M. ; Boley, H. ; Greene, S. ; Howse, N. ; Lemire, D.: RACOFI: A Rule-Applying Collaborative Filtering System. In: Proceedings of the International Workshop on Collaboration Agents: Autonomous Agents for Collaborative Environments,2003, S. 13 [6] Andreevskaia,A.;Bergler, S.: Mining WordNet for Fuzzy Sentiment: Sentiment Tag Extraction from WordNet Glosses. In: Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics Bd. 6,2006, S. 209–216 [7] Anjorin, M. ; Domínguez García, R. ; Rensing, C.: CROKODIL: a Platform Supporting the Collaborative Management of Web Resources for Learning Purposes. In: Proceedings of the 16th annual joint conference on Innovation and technology in computer science education. New York, NY, USA : ACM, Jun 2011. – ISBN 978–1–4503–0697–3, S. 361. – Poster [8] Anjorin, M. ; Rensing, C. ; Bischoff, K. ; Bogner, C. ; Lehmann, L. ; Reger, A. L. ; Faltin, N. ; Steinacker, A. ; Lüdemann, A. ; Domínguez García, R.: CROKODIL - a Platform for Collaborative Resource-Based Learning. In: Towards Ubiquitious Learning, Proceedings of the 6th European Conference on Technology Enhanced Learning. Heidelberg : Springer, Sep 2011 ( LNCS 6964). – ISBN 9783642239847, S. 29–42 [9] Anjorin, M. ; Rodenhausen, T. ; Domínguez García, R. ; Rensing, C.: Exploiting Semantic Information for Graph-Based Recommendations of Learning Resources. In: Proceedings of the 7th European Conference on Technology Enhanced Learning. Heidelberg : Springer, Sep 2012 [10] Arborea, V.: Wissensportal: Taxonomie. Webseite, 2012. – Online verfügbar unter http://www.verein-arborea.de/wissen/taxonomie; Zugriff am 14.11.2012. 119 120 literaturverzeichnis [11] Auer, S. ; Bizer, C. ; Kobilarov, G. ; Lehmann, J. ; Cyganiak, R. ; Ives, Z.: Dbpedia: A nucleus for a web of open data. In: Proceedings of the 6th International Semantic Web Conference, Springer, 2007, S. 722–735 [12] Auer, S. ; Lehmann, J.: What have Innsbruck and Leipzig in Common? Extracting Semantics from Wiki Content. In: Proceedings of the 4th European Semantic Web Conference, Springer, 2007, S. 503–517 [13] Augustin, A. G.: Erfassung Semantischer Informationen aus Enzyklopädischen Daten, Technische Universität Graz, Diplomarbeit, 2012 [14] Barritt, C. ; Lewis, D. ; Wieseler, W.: Cisco Systems Reusable Information Object Strategy. Webseite, Oktober 1999. – Zugriff am 28.11.2012 [15] Batagelj,V.;Zaveršnik, M.: Generalized Cores.2002 [16] Bengio, Y. ; Grandvalet, Y.: No Unbiased Estimator of the Variance of KFold Cross-Validation. In: The Journal of Machine Learning Research 5(2004), S. 1089–1105 [17] Böhnstedt, D. ; Scholl, P. ; Benz, B. ; Rensing, C. ; Steinmetz, R. ; Schmitz, B.: Einsatz persönlicher Wissensnetze im Ressourcen-basierten Lernen. In: DeLFI 2008:6. e-Learning Fachtagung Informatik. Köllen, Bonn : Lecture Notes in Informatics (LNI), Sep 2008 ( P-132). – ISBN 978–3–88579–226–0, S. 113–124 [18] Böhnstedt, D. ; Scholl, P. ; Rensing, C. ; Steinmetz, R.: Collaborative Semantic Tagging of Web Resources on the Basis of Individual Knowledge Networks. In: Proceedings of First and Seventeenth International Conference on User Modeling, Adaptation, and Personalization Bd. Lecture Notes in Computer Science, Springer-Verlag Berlin Heidelberg 2009, Jun 2009. – ISBN 978–3–642–02246–3, S. 379–384 [19] Böhnsteedt, D.: Semantisches Tagging zur Verwaltung von webbasierten Lernresourcen, TU Darmstadt, Diss., Juni 2011 [20] Bollacker, K. ; Evans, C. ; Paritosh, P. ; Sturge, T. ; Taylor, J.: Freebase: a Collaboratively Created Graph Database for Structuring Human Knowledge. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data ACM, 2008, S. 1247–1250 [21] Borgatti, S. P.: Graph theory. Reading List CAMOS, School of Computer Science, Carnegie Mellon University, [22] Boyle, T.: Design Principles for Authoring Dynamic, Reusable Learning Objects. In: Australian Journal of Educational Technology 19 (2003), S. 46–58 [23] Bridge, D. ; Ricci, F.: Supporting Product Selection with Query Editing Recommendations. In: Proceedings of the First ACM Conference on Recommender systems ACM, 2007, S. 65–72 [24] Budanitsky, A. ; Hirst, G.: Semantic Distance in WordNet: An Experimental, Application-Oriented Evaluation of Five Measures. In: Workshop on WordNet and Other Lexical Resources Bd. 2,2001 literaturverzeichnis 121 [25] Burke, R.: Knowledge-Based Recommender Systems. In: Encyclopedia of Library and Information Systems 69 (2000), Nr. Supplement 32, S. 175–186 [26] Burke, R. ; Hammond, K. J. ; Yound, B. C.: The FindMe Approach to Assisted Browsing. In: IEEE Expert 12 (1997), Nr. 4, S. 32–40 [27] Kapitel 1. In:Candillier, L. ; Jack, K. ; Fessant, F. ; Meyer, F.: State-of-the-Art Recommender Systems. IGI Global, 2009, S. 1–22 [28] Chatti, M.A. ; Dyckhoff, A.L. ; Schroeder, U. ; Thüs, H.: Forschungsfeld Learning Analytics. In: i-com – Zeitschrift für interaktive und kooperative Medien 11 (2012), Nr. 1, S. 22–25 [29] Chen, C.M. ; Lee, H. M. ; Chen, Y. H.: Personalized E-Learning System using Item Response Theory. In: Computers & Education 44 (2005), Nr. 3, S. 237–255 [30] Chernov, S. ; Iofciu, T. ; Nejdl, W. ; Zhou, X.: Extracting Semantic Relationships between Wikipedia Categories. In: Proceedings of the First International Workshop on Semantic Wikis Citeseer, 2006 [31] Cimiano, P. ; Pivk, A. ; Schmidt-Thieme, L. ; Staab, S.: Learning Taxonomic Relations from Heterogeneous Sources of Evidence. In: Ontology Learning from Text: Methods, Evaluation and Applications 123 (2005), S. 59–73 [32] Cormen, T.H. ; Leiserson, C. E. ; Rivest, R. ; Stein, C.: Algorithmen-Eine Einführung. Oldenbourg Wissenschaftsverlag, 2010 [33] Cruse, D. A.: Lexical Semantics. Cambridge University Press, 1986 [34] Domínguez García, R. ; Bender, M. ; Anjorin, M. ; Rensing, C. ; Steinmetz, R.: FReSET - An Evaluation Framework for Folksonomy-Based Recommender Systems. In: Proceedings of the 4th ACM Workshop on Recommender Systems and the Social Web,2012 [35] Domínguez García, R. ; P., Scholl ; Rensing, C.: Supporting Resource-based Learning on the Web using Automatically Extracted Large-scale Taxonomies from Multiple Wikipedia Versions. In: Proceedings of 10th International Conference on Web-Based Learning Springer, Lecture Notes in Computer Science, Dec 2011. – ISBN 978–3642258121, S. 309–314 [36] Domínguez García, R. ; Rensing, C. ; Steinmetz, R.: Automatic Acquisition of Taxonomies in Different Languages from Multiple Wikipedia Versions. In: Proceedings of the 11th International Conference on Knowledge Management and Knowledge Technologies ACM International Conference Proceedings Series ACM Inc., ACM International Conference Proceedings Series ACM Inc., Sep 2011. – ISBN 978–1–4503–0732–1 [37] Domínguez García, R. ; Schmidt, S. ; Rensing, C. ; Steinmetz, R.: Automatic Taxonomy Extraction in Different Languages using Wikipedia and minimal language-specific Information. In: Computational Linguistics and Intelligent Text Processing, Springer, Mar 2012 ( LNCS 7181). – ISBN 978–3642286032, S. 42 –53 122 literaturverzeichnis [38] Downes, S.: Learning Objects: Resources for Distance Education Worldwide. In: The International Review of Research in Open and Distance Learning 2(2001), Nr. 1, S. Article–2 [39] Drachsler, H. ; Hummel, H. G. K. ; Koper, R.: Personal Recommender Systems for Learners in Lifelong Learning Networks: the Requirements, Techniques and Model. In: International Journal of Learning Technology 3(2008), Nr. 4, S. 404–423 [40] Dron, J. ; Mitchell, R. ; Siviter, P. ; Boyne, C.: CoFIND – an Experiment in N-dimensional Collaborative Filtering. In: Journal of Network and Computer Applications 23 (2000), Nr. 2, S. 131–142 [41] Drummer, J. ; Hambach, S. ; Kienle, A. ; Lucke, U. ; Martens, A. ; Müller, W. ; Rensing, C. ; Schroeder, U. ; Schwill, A. ; Spannagel, C. ; Trahasch, S.: Forschungsherausforderungen des E-Learning. In: Die 9. E-Learning Fachtagung Informatik 9(2011), S. 197–208 [42] Faatz, A.: Ein Verfahren zur Anreicherung Fachgebietsspezifischer Ontologien durch Begriffsvorschläge, TU Darmstadt, Diss., Dezember 2004 [43] Felfernig, A. ; Gula, B.: An Empirical Study on Consumer Behavior in the Interaction with Knowledge-Based Recommender Applications. In: Proceedings of the 8th IEEE International Conference on and Enterprise Computing, E-Commerce, and E-Services IEEE, 2006, S. 37 [44] Felfernig, A. ; Kiener, A.: Knowledge-Based Interactive Selling of Financial Services with FSAdvisor. In: Proceedings of the National Conference on Artificial Intelligence Bd. 20 AAAI Press; MIT Press; 1999,2005, S. 1475 [45] Finin, T. ; Syed, Z.: Creating and Exploiting a Web of Semantic Data. In: Proceedings of the 2nd International Conference on Agents and Artificial Intelligence, 2010, S. 7–18 [46] Gabrilovich, E. ; Markovitch, S.: Computing Semantic Relatedness using Wikipedia-Based Explicit Semantic Analysis. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence Bd. 6Morgan Kaufmann Publishers Inc., 2007, S. 12 [47] Gärtner, K.: Analyse von Recommendersystemen in Deutschland. Bd. 38. BIT Verlag, 2012 [48] Goldberg, D. ; Nichols, D. ; Oki, B. M. ; Terry, D.: Using Collaborative Filtering to Weave an Information Tapestry. In: Communications of the ACM 35 (1992), Nr. 12, S. 61–70 [49] Granitzer, M. ; Augustin, A. ; Kienreich, W. ; Sabol, V.: Taxonomy Extraction from German Encyclopedic Texts. In: Proceedings of the Malaysian Joint Conference on Artificial Intelligence,2009 [50] Gruber, T.R.: Toward Principles for the Design of Ontologies Used for Knowledge Sharing. In: International Journal of Human-Computer Studies 43 (1993), Nr. 5, S. 907–928 literaturverzeichnis 123 [51] Hall, M. ; Frank, E. ; Holmes, G. ; Pfahringer, B. ; Reutemann, P. ; Witten, I. H.: The WEKA Data Mining Software: an Update. In: ACM SIGKDD Explorations Newsletter 11 (2009), Nr. 1, S. 10–18 [52] Hammwöhner, R.: Qualitätsaspekte der Wikipedia. In: kommunikation@gesellschaft 8(2007), S. 77–90 [53] Hamp, B. ; Feldweg, H.: Germanet – a Lexical-Semantic Net for German. In: Proceedings of the Workshop Automatic Information Extraction and Building of Lexical Semantic Resources for NLP Applications Citeseer, 1997, S. 9–15 [54] Hearst, M. A.: Automatic Acquisition of Hyponyms from Large Text Corpora. In: Proceedings of the 14th Conference on Computational Linguistics Bd. 2Association for Computational Linguistics, 1992, S. 539–545 [55] Herbelot, A. ; Copestake, A.: Acquiring Ontological Relationships from Wikipedia using RMRS. In: Proceedings of the International Workshop on Web Content Mining with Human Language Technologies Citeseer, 2006 [56] Herding, D. ; Schroeder, U. ; Stalljohann, P. ; Chatti, M.A.: Formatives Assessment in Offenen, Informellen Vernetzten Lernszenarien. In: i-com – Zeitschrift für interaktive und kooperative Medien 11 (2012), Nr. 1, S. 19–21 [57] Herlocker, J. L. ; Konstan, J. A. ; Borchers, A. ; Riedl, J.: An Algorithmic Framework for Performing Collaborative Filtering. In: Proceedings of the 22nd annual international ACM SIGIR Conference on Research and Development in Information Retrieval ACM, 1999, S. 230–237 [58] Hodgins, H.W.: The Future of Learning Objects. In: Proceedings of the 2002 eTEE Conference, bepress, 2004, S. 11 [59] Hörmann, S.: Wiederverwendung von digitalen Lernobjekten in einem auf Aggregation basierenden Autorenprozess, TU Darmstadt, Diss., Februar 2006 [60] Hotho, A. ; Jäschke, R. ; Schmitz, C. ; Stumme, G.: Folkrank: A Ranking Algorithm for Folksonomies. In: Proceedings of the International Workshop on Information Retrieval (FGIR) Bd. 2006, Citeseer, 2006 [61] Hotho, A. ; Jäschke, R. ; Schmitz, C.h ; Stumme, G.: BibSonomy: A Social Bookmark and Publication Sharing System. In: Proceedings of the Conceptual Structures Tool Interoperability Workshop,2006 [62] Hsu, M.H.: A Personalized English Learning Recommender System for ESL Students. In: Expert Systems with Applications 34 (2008), Nr. 1, S. 683–688 [63] Huang, Y. M. ; Huang, T. C. ; Wang, K. T. ; Hwang, W. Y.: A Markov-Based Recommendation Model for Exploring the Transfer of Learning on the Web. In: Educational Technology & Society 12 (2009), Nr. 2, S. 144–162 [64] Jakob, N.: Extracting Opinion Targets from User-Generated Discourse with an Application to Recommendation Systems, Technische Universität Darmstadt, Diss., 2011 124 literaturverzeichnis [65] Jannach, D. ; Zanker, M. ; Felfernig, A. ; Friedrich, G.: Recommender Systems: An Introduction. Cambridge University Press, 2010 [66] Janowicz, K. ; Raubal, M. ; Kuhn, W.: The Semantics of Similarity in Geographic Information Retrieval. In: Journal of Spatial Information Science 2(2012), Nr. 2, S. 29–57 [67] Jansen, B. J. ; Spink, A. ; Saracevic, T.: Real Life, Real Users, and Real Needs: a Study and Analysis of User Queries on the Web. In: Information Processing & Management 36 (2000), Nr. 2, S. 207–227 [68] Janssen, J. ; Tattersall, C. ; Waterink, W. ; Berg, B. Van d. ; Van Es, R. ; Bolman, C. ; Koper, R.: Self-organising Navigational Support in Lifelong Learning: How Predecessors Can Lead The Way. In: Computers & Education 49 (2007), Nr. 3, S. 781–793 [69] Jäschke, R. ; Marinho, L. ; Hotho, A. ; Schmidt-Thieme, L. ; Stumme, G.: Tag Recommendations in Folksonomies. In: Knowledge Discovery in Databases: PKDD 2007 4702 (2007), S. 506–514 [70] Jie, L.: A Personalized E-Learning Material Recommender System. In: Proceedings of the Second International Conference on Information Technology and Applications,2004 [71] Jurafsky, D. ; Martin, J. H. ; Kehler, A. ; Vander Linden, K. ; Ward, N.: Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Bd. 2. Prentice Hall New Jersey, 2000 [72] Karkada, U.H.: Friend Recommender System for Social Networks. Seminararbeit, 2009 [73] Kassner, L. ; Nastase, V. ; Strube, M.: Acquiring a Taxonomy from the German Wikipedia. In: Proceedings of the 6th International Conference on Language Resources and Evaluation,2008 [74] Khribi, M. K. ; Jemni, M. ; Nasraoui, O.: Automatic Recommendations for E-Learning Personalization Based on Web Usage Mining Techniques and Information Retrieval. In: Proceedings of the 8th IEEE International Conference on Advanced Learning Technologies IEEE, 2008, S. 241–245 [75] Klein, D. ; Manning, C. D.: Fast Exact Inference with a Factored Model for Natural Language Parsing. In: Advances in Neural Information Processing Systems 15 (2002), Nr. 2002, S. 3–10 [76] Kohavi, R.: A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection. In: International Joint Conference on Artificial Intelligence Bd. 14 Lawrence Erlbaum Associates Ltd, 1995, S. 1137–1145 [77] Koren, Y.: The Bellkor Solution to the Netflix Grand Prize. http://www. netflixprize.com/assets/GrandPrize2009_BPC_BellKor.pdf . Version:2009. – Zugriff am 20.11.2012 literaturverzeichnis 125 [78] Koschnick, W. J.: Standardwörterbuch für die Sozialwissenschaften. KG Saur Verlag, 1992 [79] Koutrika, G. ; Ikeda, R. ; Bercovitz, B. ; Garcia-Molina, H.: Flexible recommendations over rich data. In: Proceedings of the 2nd ACM conference on Recommender systems ACM, 2008, S. 203–210 [80] L’Allier, J. J.: Frame of Reference: NETg’s Map to Its Products, Their Structures and Core Beliefs. Whitepaper, April 1997 [81] Leacock, C. ; Chodorow, M.: Combining Local Context and WordNet Similarity for Word Sense Identification. In: WordNet: An Electronic Lexical Database 49 (1998), Nr. 2, S. 265–283 [82] Lehmann, L.: Lebenszyklusinformationen von Wissensdokumenten - Erfassung, Verwaltung und Validierung, TU Darmstadt – Multimedia Kommunikation, Diss., April 2010 [83] Lenat, D.B.: CYC: A Large-scale Investment in Knowledge Infrastructure. In: Communications of the ACM 38 (1995), Nr. 11, S. 33–38 [84] Littlejohn, A.: Reusing Online Resources: a Sustainable Approach to E-Learning. Routledge, 2003 [85] Liu, B.: Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data. Springer Verlag, 2007 [86] Lorenzi, F. ; Ricci, F.: Case-Based Recommender Systems: A Unifying View. In: Intelligent Techniques for Web Personalization 3169 (2005), S. 89–113 [87] MacKay, D. J. C.: Information Theory, Inference, and Learning Algorithms. Cambridge Univ Press, 2003 [88] Maedche, A. ; Staab, S.: Ontology Learning for the Semantic Web. In: IEEE Intelligent Systems 16 (2001), Nr. 2, S. 72–79 [89] Maidel, V. ; Shoval, P. ; Shapira, B. ; Taieb-Maimon, M.: Evaluation of an Ontology-Content Based Filtering Method for a Personalized Newspaper. In: Proceedings of the 2nd ACM conference on Recommender systems ACM, 2008, S. 91–98 [90] Makhoul, J. ; Kubala, F. ; Schwartz, R. ; Weischedel, R.: Performance Measures for Information Extraction. In: Proceedings of DARPA Broadcast News Workshop,1999, S. 249–252 [91] Manning, C. D. ; Raghavan, P. ; Schutze, H.: Introduction to Information Retrieval. Bd. 1. Cambridge University Press Cambridge, 2008 [92] Manouselis, N. ; Costopoulou, C.: Experimental Analysis of Multiattribute Utility Collaborative Filtering on a Synthetic Data Set. In: Personalization Techniques and Recommender Systems, Series in Machine Perception and Artificial Intelligence 70 (2008), S. 111–134 126 literaturverzeichnis [93] Manouselis, N. ; Drachsler, H. ; Vuorikari, R. ; Hummel, H. ; Koper, R.: Recommender Systems in Technology Enhanced Learning. In: Recommender Systems Handbook. Springer, 2011, S. 387–415 [94] Martin, P. A.: Semantic Networks to Support Learning. In: Supplementary Proceedings of International Conference on Computational Science, Springer, 2008 [95] McCalla, G.: The Ecological Approach to the Design of E-Learning Environments: Purpose-Based Capture and Use of Information about Learners. In: Journal of Interactive Media in Education 7(2004), Nr. 1, S. 18–32 [96] Medelyan, O. ; Milne, D. ; Legg, C. ; Witten, I.H.: Mining Meaning from Wikipedia. In: International Journal of Human-Computer Studies 67 (2009), Nr. 9, S. 716–754 [97] Meder, Nobert ; Frick, Andre ; Bettels, Mirko ; Klapschuweit, Christoph: Web-Didaktik: Eine neue Didaktik webbasierten, vernetzten Lernens. W. Bertelsmann Verlag, 2002 [98] Melo, G. de ; Weikum, G.: MENTA: Inducing Multilingual Taxonomies from Wikipedia. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management ACM, 2010, S. 1099–1108 [99] Metke-Jimenez, A. ; Raymond, K. ; MacColl, I.: Ontologies Derived from Wikipedia: a Framework for Comparison. In: Proceedings of the International Conference on Knowledge Engineering and Ontology Development SciTe Press, 2010, S. 382–387 [100] Meyer, M.: Modularization and Multi-Granularity Reuse of Learning Resources, TU Darmstadt, Diss., Oktober 2008 [101] Middleton, S.E. ; Shadbolt, N.R. ; DeRoure, D.C.: Ontological User Profiling in Recommender Systems. In: ACM Transactions on Information Systems 22 (2004), Nr. 1, S. 54–88 [102] Miller, G.A.: WordNet: a Lexical Database for English. In: Communications of the ACM 38 (1995), Nr. 11, S. 39–41 [103] Mitchell, T.: Machine Learning. McGraw Hill Higher Education, 1997 [104] Mobasher, B. ; Jin, X. ; Zhou, Y.: Semantically Enhanced Collaborative Filtering on the Web. In: Web Mining: From Web to Semantic Web 3209 (2004), S. 57–76 [105] Nakayama, K. ; Hara, T. ; Nishio, S.: Wikipedia Mining for an Association Web Thesaurus Construction. In: Web Information Systems Engineering 4831 (2007), S. 322–334 [106] Nastase, V. ; Strube, M. ; Boerschinger, B. ; Zirn, C. ; Elghafari, A.: WikiNet: A Very Large Scale Multi-Lingual Concept Network. In: Proceedings of the International Conference on Language Resources and Evaluation, European Language Resources Association, 2010. – ISBN 2–9517408–6–7 literaturverzeichnis 127 [107] Naumann, A.: Wissenserwerb und Informationssuche mit Hypertexten : die Bedeutung von Strukturierung, Navigationshilfen und Arbeitsgedächtnisbelastung, TU Chemnitz, Diss., 2004 [108] Navigli, R. ; Ponzetto, S. P.: BabelNet: Building a very large multilingual semantic network. In: Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics Association for Computational Linguistics, 2010, S. 216–225 [109] Nguyen, D. ; Matsuo, Y. ; Ishizuka, M.: Subtree Mining for Relation Extraction from Wikipedia. In: Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Companion Volume, Short Papers Association for Computational Linguistics, 2007, S. 125–128 [110] O´ connor, M. ; Cosley, D. ; Konstan, J. A. ; Riedl, J.: PolyLens: A Recommender System for Groups of Users. In: Proceedings of the 2001 Seventh European Conference on Computer Supported Cooperative Work Springer, 2002, S. 199–218 [111] Page, L. ; Brin, S. ; Motwani, R. ; Winograd, T.: The PageRank Citation Ranking: Bringing Order to the Web. (1999) [112] Patwardhan, S. ; Banerjee, S. ; Pedersen, T.: Using Measures of Semantic Relatedness for Word Sense Disambiguation. In: Proceedings of the International Conference on Intelligent Text Processing and Computational Linguistics, Springer, 2003, S. 241–257 [113] Pazzani, M. ; Billsus, D.: Content-Based Recommendation Systems. In: The Adaptive Web 4321 (2007), S. 325–341 [114] Pesquita, C. ; Faria, D. ; Falcão, A. O. ; Lord, P. ; Couto, F. M.: Semantic Similarity in Biomedical Ontologies. In: PLoS computational biology 5(2009), Nr. 7, S. e1000443 [115] Pfeil, U. ; Zaphiris, P. ; Ang, C. S.: Cultural Differences in Collaborative Authoring of Wikipedia. In: Journal of Computer-Mediated Communication 12 (2006), Nr. 1, S. 88–113 [116] Polsani, P.R.: Use and Abuse of Reusable Learning Objects. In: Journal of Digital Information 3(2003), Nr. 4, S. 170–179 [117] Ponzetto, S. P. ; Navigli, R.: Large-Scale Taxonomy Mapping for Restructuring and Integrating Wikipedia. In: Proceedings of the 21st International Joint Conference on Artifical Intelligence Morgan Kaufmann, 2009, S. 2083–2088 [118] Ponzetto, S. P. ; Strube, M.: Deriving a Large-Scale Taxonomy from Wikipedia. In: Proceedings of the National Conference on Artificial Intelligence Bd. 22 AAAI Press; MIT Press, 2007, S. 1440 [119] Pu, P. ; Chen, L. ; Kumar, P.: Evaluating product search and recommender systems for E-commerce environments. In: Electronic Commerce Research 8(2008), Nr. 1, S. 1–27 134 abbildungsverzeichnis Abbildung 37 Beispiel-Kategoriengraph ohne not-is-a-Relationen und Artikel 64 Abbildung 38 Beispiel-Kategoriengraph nach Propagierung von HyponymieBeziehungen............................. 65 Abbildung 39 Links, die sowohl im Kategorien-Graph als auch in GermaNet vorkommen ............................. 70 Abbildung 40 Entfernung von zwei Knoten zum ersten gemeinsamen Vorfahren 77 Abbildung 41 Links, die sowohl im Kategorien-Graph als auch in WordNet und WikiNet vorkommen . . . . . . . . . . . . . . . . . . . . . 85 Abbildung 42 Gesamtarchitektur der CROKODIL-Plattform . . . . . . . . . . 90 Abbildung 43 Eine einfache Expertensuche im Knowledge Builder . . . . . . 91 Abbildung 44 Ausschnitt eines Wissensnetzes im Net-Navigator . . . . . . . 92 Abbildung 45 Struktur der Datenbanktabellen . . . . . . . . . . . . . . . . . . 92 Abbildung 46 Erweiterung des Basismodells der CROKODIL-Plattform . . . 93 Abbildung 47 Beispiel der Benutzung des Ähnlichkeitsobjekts . . . . . . . . 94 Abbildung 48 Expertensuche nach Objekten der Taxonomieähnlichkeit . . . 94 Abbildung 49 Expertensuche nach Ressourcen in der gleichen Aktivität . . . 95 Abbildung 50 Screenshot einer Ressource mit einer Taxonomie-basierten Empfehlung ............................. 96 Abbildung 51 Screenshot einer Kontextbox für Empfehlungen . . . . . . . . 96 Abbildung 52 Ausschnitt des semantischen Netzes von CROKODIL . . . . . 96 Abbildung 53 Innere Architektur von CrokTaxTools . . . . . . . . . . . . . . 98 Abbildung 54 Drei Ressourcen mit jeweils einem Tag . . . . . . . . . . . . . . 98 Abbildung 55 Gefundene is-a-Relationen..................... 99 Abbildung 56 Berechnete Ähnlichskeitsrelationen und -objekte . . . . . . . . 100 Abbildung 57 FReSET Screenshot des F1-Graphs ................ 108 TABELLENVERZEICHNIS Tabelle 1Beispiel einer Konfusionsmatrix . . . . . . . . . . . . . . . . . . 11 Tabelle 2 Überblick über die manuell extrahierten und gelabelten Korpora 67 Tabelle 3 Klassifikationsergebnisse der einzelnen Heuristiken für Deutsch 68 Tabelle 4Zusammenfassung der Ergebnisse von TaxWikiHeur.KOM . . 69 Tabelle 5Precision, Recall und F1-Maß für jede Klasse und Sprache . . 69 Tabelle 6Vergleich der Ergebnisse mit GermaNet und WordNet . . . . 70 Tabelle 7 Precision, Recall und F1 -Maß beim Vergleich der Ergebnisse mit GermaNet und WordNet . . . . . . . . . . . . . . . . . . . 70 Tabelle 8Überblick der entwickelten Features . . . . . . . . . . . . . . . 72 Tabelle 9Überblick über die extrahierten Korpora . . . . . . . . . . . . . 81 Tabelle 10 Zusammenfassung der Ergebnisse nach Sprachen . . . . . . . 82 Tabelle 11 Precision, Recall und F1-Maß für jede Klasse und Sprache . . 82 Tabelle 12 Konfusionsmatrix für die englische Sprache . . . . . . . . . . . 83 Tabelle 13 Performanz der Features pro Sprache . . . . . . . . . . . . . . 83 Tabelle 14 Ranking der benutzten Features für jede Sprache (IDs der Features stehen in Tabelle 8).................... 84 Tabelle 15 Zusammenfassung der Ergebnisse ohne Optimierung . . . . . 84 Tabelle 16 Vergleich der Ergebnisse zwischen TaxWikiML.KOM und WikiNet ................................. 86 Tabelle 17 Detaillierte Ergebnisse von TaxWikiML und WikiNet im VergleichzuWordNet ......................... 86 Tabelle 18 Eigenschaften der benutzten Korpora . . . . . . . . . . . . . . 106 Tabelle 19 Struktur der benutzten Korpora . . . . . . . . . . . . . . . . . . 109 Tabelle 20 Eigenschaften der benutzten Korpora nach der Erkennung von Hyponymierelationen........................ 109 Tabelle 21 Dichte der benutzten Korpora nach der Erkennung von Hyponymierelationen........................... 110 Tabelle 22 Ergebnisse für CROKpohne Hyponymien . . . . . . . . . . . . 111 Tabelle 23 Ergebnisse für CROKpmit Hyponymien . . . . . . . . . . . . 111 Tabelle 24 Ergebnisse für CROK1ohne Hyponymien . . . . . . . . . . . . 111 Tabelle 25 Ergebnisse für CROK1mit Hyponymie . . . . . . . . . . . . . 111 Tabelle 26 Ergebnisse für CROK2ohne Hyponymien . . . . . . . . . . . . 112 Tabelle 27 Ergebnisse für CROK2mit Hyponymien . . . . . . . . . . . . . 112 Tabelle 28 CROKp: Gesamtergebnisse ohne Hyponymie . . . . . . . . . . 112 Tabelle 29 CROKp: Gesamtergebnisse mit Hyponymie . . . . . . . . . . . 112 Tabelle 30 CROK1: Gesamtergebnisse ohne Hyponymien . . . . . . . . . 113 Tabelle 31 CROK1: Gesamtergebnisse mit Hyponymien . . . . . . . . . . 113 Tabelle 32 CROK2: Gesamtergebnisse ohne Hyponymien . . . . . . . . . 113 Tabelle 33 CROK2: Gesamtergebnisse mit Hyponymien . . . . . . . . . . 113 Tabelle 34 Überblick der Ergebnisse bei verändertem Matching-Fenster . 139 Tabelle 35 Überblick der Ergebnisse bei verändertem Matching-Fenster . 140 Tabelle 36 Klassifikationsergebnisse der einzelnen Heuristiken für Englisch 141 135 136 tabellenverzeichnis Tabelle 37 Klassifikationsergebnisse der einzelnen Heuristiken Spanisch 142 Tabelle 38 Klassifikationsergebnisse der einzelnen Heuristiken für Arabisch 143 Tabelle 39 Zusammenfassung der Ergebnisse ohne Optimierung . . . . . 144 Tabelle 40 Precision, Recall und F-Maß (Englisch) . . . . . . . . . . . . . . 145 Tabelle 41 Konfusionsmatrix (Englisch) . . . . . . . . . . . . . . . . . . . . 145 Tabelle 42 Zusammenfassung der Ergebnisse ohne Optimierung . . . . . 145 Tabelle 43 Precision, Recall und F-Maß (Deutsch) . . . . . . . . . . . . . . 146 Tabelle 44 Konfusionsmatrix (Deutsch) . . . . . . . . . . . . . . . . . . . . 146 Tabelle 45 Vergleich der Ergebnisse zwischen TaxWikiML.KOM und WikiNet ................................. 146 Tabelle 46 Detaillierte Ergebnisse von TaxWikiML.KOM und WikiNet im VergleichzuGermaNet....................... 147 Tabelle 47 Dichte der Ressource-Knoten in den benutzten Korpora . . . 148 Tabelle 48 Dichte der Tags-Knoten in den benutzten Korpora . . . . . . . 148 Tabelle 49 Dichte der Benutzer-Knoten in den benutzten Korpora . . . . 148 Tabelle 50 Dichte der Ressource-Knoten in den benutzten Korpora . . . 149 Tabelle 51 Dichte der Tags-Knoten in den benutzten Korpora . . . . . . . 149 Tabelle 52 Dichte der Benutzer-Knoten in den benutzten Korpora . . . . 149 Tabelle 53 Ergebnisse für CROKpmit einfacher Benutzergewichtung . . 150 Tabelle 54 Gesamtergebnisse.......................... 150 Tabelle 55 Ergebnisse für CROKpmit fünffacher Benutzergewichtung . . 150 Tabelle 56 Gesamtergebnisse.......................... 150 Tabelle 57 Ergebnisse für CROKpmit zehnfacher Benutzergewichtung . 151 Tabelle 58 Gesamtergebnisse.......................... 151 Tabelle 59 Ergebnisse für CROK1mit einfacher Benutzergewichtung . . 151 Tabelle 60 Gesamtergebnisse.......................... 151 Tabelle 61 Ergebnisse für CROK1mit fünffacher Benutzergewichtung . . 152 Tabelle 62 Gesamtergebnisse.......................... 152 Tabelle 63 Ergebnisse für CROK1mit zehnfacher Benutzergewichtung . 152 Tabelle 64 Gesamtergebnisse.......................... 152 Tabelle 65 Ergebnisse für CROK2mit einfacher Benutzergewichtung . . 153 Tabelle 66 Gesamtergebnisse.......................... 153 Tabelle 67 Ergebnisse für CROK2mit fünffacher Benutzergewichtung . . 153 Tabelle 68 Gesamtergebnisse.......................... 153 Tabelle 69 Ergebnisse für CROK2mit zehnfacher Benutzergewichtung . 154 Tabelle 70 Gesamtergebnisse.......................... 154 Tabelle 71 Ergebnisse für CROKpmit einfacher Benutzergewichtung . . 154 Tabelle 72 Gesamtergebnisse.......................... 154 Tabelle 73 Ergebnisse für CROKpmit fünffacher Benutzergewichtung . . 155 Tabelle 74 Gesamtergebnisse.......................... 155 Tabelle 75 Ergebnisse für CROKpmit zehnfacher Benutzergewichtung . 155 Tabelle 76 Gesamtergebnisse.......................... 155 Tabelle 77 Ergebnisse für CROK1mit einfacher Benutzergewichtung . . 156 Tabelle 78 Gesamtergebnisse.......................... 156 Tabelle 79 Ergebnisse für CROK1mit fünffacher Benutzergewichtung . . 156 Tabelle 80 Gesamtergebnisse.......................... 156 Tabelle 81 Ergebnisse für CROK1mit zehnfacher Benutzergewichtung . 157 Tabelle 82 Gesamtergebnisse.......................... 157 tabellenverzeichnis 137 Tabelle 83 Ergebnisse für CROK2mit einfacher Benutzergewichtung . . 157 Tabelle 84 Gesamtergebnisse.......................... 157 Tabelle 85 Ergebnisse für CROK2mit fünffacher Benutzergewichtung . . 158 Tabelle 86 Gesamtergebnisse.......................... 158 Tabelle 87 Ergebnisse für CROK2mit zehnfacher Benutzergewichtung . 158 Tabelle 88 Gesamtergebnisse.......................... 158 ABKÜRZUNGSVERZEICHNIS ACM Association for Computing Machinery. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 API Application Programming Interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39 CROKODIL Communities, Web-Ressourcen und Kompetenzentwicklungsdienste integrierendeLernumgebung.......................................43 CSV Comma-separatedvalues...........................................66 IR InformationRetrieval................................................8 LOM LearningObjectMetadata...........................................8 MENTA MultilingualEntityTaxonomy......................................39 RBL Ressourcen-basiertesLernen.........................................1 REST REpresentational State Transfer Architektur. . . . . . . . . . . . . . . . . . . . . . . . .91 SCORM Shareable Content Object Reference Model. . . . . . . . . . . . . . . . . . . . . . . . . . .8 SQL StandardQueryLanguage...........................................8 URL UniformResourceLocator..........................................91 WWW WorldWideWeb.....................................................1 YAGO YetAnotherGreatOntology........................................37 138 A ANHANG »Alles nimmt ein gutes Ende für den, der warten kann.« — Leo Tolstoi a.1 details zu taxwikiheur.kom a.1.1Parametrisierung der Heuristiken für die deutsche Sprache Für die Parametrisierung der Heuristiken wurde ein anderer Korpus gewählt als in Abschnitt 5.1.4.1, um eine maximale heterogene Linksmenge zu haben. Der Korpus bestand aus 329 zufällig gewählten Kategorien. Der Kategoriengraph selbst bestand aus 635 Links, die manuell gelabelt wurden. Insgesamt bestand der Korpus aus 196 isa-Links und 439 not-is-a-Links. Zuerst wird auf die Parametrisierung für das Matching von lexikalischen Köpfen an richtiger Stelle und anschließend auf das Matching von lexikalischen Köpfen an falscher Stelle eingegangen. a.1.1.1Matching von lexikalischen Köpfen an richtiger Stelle Um die optimale Konfiguration für die Heuristik zu finden, wurden verschiedene Matching-Fenster in Betracht gezogen. Diese Heuristik wurde auf den Korpus wiederholt angewendet, bis eine optimale Länge des Matching-Fensters bestimmt wurde. Die besten Ergebnisse ergaben sich bei einem Matching-Fenster von 4.71 von 83 Links wurden dabei korrekt klassifiziert. Die restlichen Ergebnisse sind in folgender Tabelle aufgeführt: Tabelle 34: Überblick der Ergebnisse bei verändertem Matching-Fenster Länge des Matching-Fensters Korrekt kl. Links Inkorrekt kl. Links 3 73 15 4 71 12 5 59 12 6 46 11 Wie man an den Ergebnissen sieht, wächst die Anzahl der inkorrekt klassifizierten Links, wenn das Matching-Fenster zu klein ist. Für die Matching-Fenster 4,5und 6gibt es einen relativ großen Unterschied in Bezug auf die Anzahl der korrekt klassifizierten Links. Die Anzahl der korrekt klassifizierten Links wächst für kleine Matching-Fenster, aber die Verbesserung von Matching-Fenster 4zu Matching-Fenster 3ist nicht signifikant, da zwar 2Links mehr korrekt klassifiziert wurden, gleichzeitig aber existieren 3weitere falsch klassifizierte Links. 139 140 appendix a.1.1.2Matching von lexikalischen Köpfen an falscher Stelle Dasselbe Verfahren wurde angewendet, um ein Matching-Fenster für diese Heuristik zu bestimmen. Die besten Ergebnisse wurden mit einem Matching-Fenster von 6 erreicht. 15 von 21 Links wurden korrekt klassifiziert. In Tabelle 35 werden die weiteren Ergebnisse gezeigt. Tabelle 35: Überblick der Ergebnisse bei verändertem Matching-Fenster Länge des Matching-Fensters Korrekt kl. Links Inkorrekt kl. Links 3 18 9 4 15 8 5 15 8 6 15 6 7 11 5 8 11 5 9 9 5 10 5 1 a.1.2Ergebnisse von TaxWikiHeur.KOM in anderen Sprachen appendix 141 Tabelle 36: Klassifikationsergebnisse der einzelnen Heuristiken für Englisch Ungelabelte Links Korrekt klassifiziert Inkorrekt klassifiziert Noch zu klassifizieren Heuristik: Admin. Metakategorien 1561 228 0 1333 Heuristik: Verfeinerungslinks 1333 233 0 1100 Heuristik: Lex. Köpfe an richtiger Stelle 1100 94 1 1005 Heuristik: Lex. Köpfe an falscher Stelle 1005 46 0 959 Heuristik: Erster Satz eines Artikels 959 15 4 940 Matching von Kookkurrenzen im Graph 940 75 47 818 Heuristik: Transitive Links 117 89 142 appendix Tabelle 37: Klassifikationsergebnisse der einzelnen Heuristiken Spanisch Ungelabelte Links Korrekt klassifiziert Inkorrekt klassifiziert Noch zu klassifizieren Heuristik: Admin. Metakategorien 860 34 0 826 Heuristik: Verfeinerungslinks 826 117 0 709 Heuristik: Lex. Köpfe an richtiger Stelle 709 88 1 620 Heuristik: Lex. Köpfe an falscher Stelle 620 15 4 601 Heuristik: Erster Satz eines Artikels 601 12 0 589 Matching von Kookkurrenzen im Graph 589 32 15 548 Heuristik: Transitive Links 96 28 appendix 143 Tabelle 38: Klassifikationsergebnisse der einzelnen Heuristiken für Arabisch Ungelabelte Links Korrekt klassifiziert Inkorrekt klassifiziert Noch zu klassifizieren Heuristik: Admin. Metakategorien 1204 256 0 948 Heuristik: Verfeinerungslinks 948 281 0 667 Heuristik: Lex. Köpfe an richtiger Stelle 667 34 5 628 Heuristik: Lex. Köpfe an falscher Stelle 628 72 0 556 Heuristik: Erster Satz eines Artikels 556 51 0 505 Matching von Kookkurrenzen im Graph 505 106 22 377 Heuristik: Transitive Links 28 18