Automatische Ontologie-Optimierung in Ontologie-basierten ... · Zusammenfassung Ontologie-basierte Systeme nutzen Ontologien hauptsächlich, um Wissen strukturiert zu repräsentieren

Automatische Ontologie-Optimierung inOntologie-basierten Systemen

Diplomarbeitam Fachgebiet Agententechnologien in betrieblichen Anwendungen und der

Telekommunikation (AOT)Prof. Dr.-Ing. habil. Sahin Albayrak

Fakultät IV Elektrotechnik und InformatikTechnische Universität Berlin

vorgelegt vonWinfried Umbrath

Gutachter: Dr.- Ing. Stefan Fricke,Prof. Dr. Torsten Schaub

Winfried UmbrathMatrikelnummer: 711087Herbststr. 2813409 Berlin

Erklärung der Urheberschaft

Ich erkläre hiermit an Eides statt, dass ich die vorliegende Arbeit ohne Hilfe Dritterund ohne Benutzung anderer als der angegebenen Hilfsmittel angefertigt habe; die ausfremden Quellen direkt oder indirekt übernommenen Gedanken sind als solche kenntlichgemacht. Die Arbeit wurde bisher in gleicher oder ähnlicher Form in keiner anderenPrüfungsbehörde vorgelegt und auch noch nicht veröffentlicht.

Ort, Datum Unterschrift

II

Zusammenfassung

Ontologie-basierte Systeme nutzen Ontologien hauptsächlich, um Wissen strukturiert zurepräsentieren. Ein Beispiel hierfür sind Expertensuchsysteme. Diese nutzen Ontologi-en, um Suchanfragen den dafür zuständigen Experten zuzuordnen. Dabei bestehen On-tologien aus Kategorien und Beziehungen zwischen diesen Kategorien. Das Matchingder Suchanfragen auf die Experten geschieht durch eine automatische Klassifizierungder Anfrage in die Kategorien der Ontologie. Das Problem bei solchen Systemen ist dieWahl der Ontologie. Grosse Ontologien decken zwar alle benötigten Kategorien ab, sieerlauben aber keine performante Klassifikation der Anfragen. Kleine Ontologien hin-gegen können die Kategorien nicht genau genug beschreiben, d.h. die Kategorien sindrecht allgemein gehalten. In dieser Arbeit soll dieses Problem gelöst werden, indemdie Kategoriestruktur der Verteilung der Experten und Anfragen innerhalb des Systemsangepasst wird. Dabei werden nur diejenigen Kategorien behalten, zu denen häufig An-fragen gestellt werden. Diese Themengebiete werden mit Hilfe einer Singulärwertzer-legung auf einer Anfrage-Kategorien Matrix ermittelt. Im Ergebnis zeigt sich, dass eineOntologie mit 1200 Kategorien durch eine mit weniger als 100 Themengebieten ersetztwerden kann, ohne dass dabei die Qualität beim Matching der Suchanfragen auf dieExperten abnimmt.

III

Danksagung

An erster Stelle gilt mein Dank Prof. Dr. Torsten Schaub und Dr. Peter-Uwe Zettiér,welche mir die Möglichkeit eröffneten, an einem für den Lehrstuhl Wissensverarbeitungund Informationssysteme eher ungewöhnlichen Thema zu arbeiten. Weiterhin dankeich meinem Betreuer am DAI-Labor, Dipl-Ing. Robert Wetzker, für die konstruktivenGespräche und die hilfreichen Hinweise, die zur Verbesserung dieser Arbeit beitrugen.Für die Betreuung seitens der Universität, bedanke ich mich bei Dr. Peter-Uwe Zettiér,der immer ein offenes Ohr für meine Fragen hatte.

Dank auch an die Korrekturleser Wai-Lung Lee und Robert Wetzker für die Zeit,die sie für mich opferten.

Der grösste Dank gilt natürlich meiner gesamten Familie, ohne die dieses Studi-um nie möglich gewesen wäre. Durch ihre moralische und finanzielle Unterstützungermöglichten sie mir 6 schöne Jahre in Berlin.

IV

Inhaltsverzeichnis

Erklärung der Urheberschaft II

Zusammenfassung III

Inhaltsverzeichnis V

1 Einleitung 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Ziel der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Aufbau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Grundlagen und verwandte Arbeiten 52.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.1 Ontologien . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1.2 Textrepräsentation . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.2.1 Vektorraummodell . . . . . . . . . . . . . . . . . . . 72.1.2.2 Ähnlichkeitsmaße . . . . . . . . . . . . . . . . . . . 9

2.1.3 Dimensionsreduktion . . . . . . . . . . . . . . . . . . . . . . . 92.1.3.1 Term-Preprocessing . . . . . . . . . . . . . . . . . . 92.1.3.2 Feature Selection . . . . . . . . . . . . . . . . . . . 112.1.3.3 Latent Semantic Analysis . . . . . . . . . . . . . . . 12

2.1.4 Textklassifikation . . . . . . . . . . . . . . . . . . . . . . . . . 152.1.4.1 Naive Bayes Klassifikator . . . . . . . . . . . . . . . 152.1.4.2 Evaluierung . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Verwandte Arbeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 SPREE - Ein Expertensuchsystem 213.1 Die Ontologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2 Abbildung auf die Ontologie . . . . . . . . . . . . . . . . . . . . . . . 22

V

INHALTSVERZEICHNIS VI

3.3 Ermittlung der Experten . . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Problemanalyse 25

5 Lösungskonzept 325.1 Aufbau der vollständigen Ontologie . . . . . . . . . . . . . . . . . . . 345.2 Extraktion der Arbeitsontologie . . . . . . . . . . . . . . . . . . . . . 36

5.2.1 Experten-basierte Knotenreduktion . . . . . . . . . . . . . . . 365.2.2 Feature Selection . . . . . . . . . . . . . . . . . . . . . . . . . 375.2.3 Anfrage-basierte Knotenreduktion . . . . . . . . . . . . . . . . 38

6 Umsetzung 416.1 Teilsysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426.2 Datenmodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446.3 Aufbau der vollständigen Ontologie . . . . . . . . . . . . . . . . . . . 456.4 Extraktion der Arbeitsontologie . . . . . . . . . . . . . . . . . . . . . 47

6.4.1 Experten-basierte Knotenreduktion . . . . . . . . . . . . . . . 486.4.2 Feature Selection . . . . . . . . . . . . . . . . . . . . . . . . . 496.4.3 Anfrage-basierte Knotenreduktion . . . . . . . . . . . . . . . . 50

7 Evaluierung 527.1 Test Aufbau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527.2 Testergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

8 Fazit und Ausblick 57

Literaturverzeichnis 59

Abbildungsverzeichnis 63

Abkürzungsverzeichnis 64

A Anhang 65A.1 Quelltexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

Kapitel 1

Einleitung

1.1 Motivation

Vor der eigentlichen Motivation soll zunächst eine kurze, informale Arbeitsdefinitionvon Ontologie gegeben werden um dem Leser das Verständnis der restlichen Einleitungzu erleichtern. Eine detailliertere Definition ist in Kapitel 2 gegeben.Der Begriff Ontologie wird, je nach Anwendungsgebiet, für verschiedene Formender „Wissensrepräsentation eines formal definierten Systems von Begriffen undRelationen“[1] benutzt. In der vorliegenden Arbeit sei damit ein Graph, genauer ge-sagt ein Baum, gemeint, dessen Knoten („die Begriffe“) Kategorien repräsentieren, wieman sie beispielsweise in einem Webseitenverzeichnis finden würde. Die Kanten desBaumes stellen Relationen zwischen den Kategorien dar. Im Grunde entspricht eine sodefinierte Ontologie einer Taxonomie.Ontologien werden hauptsächlich zur Wissensdarstellung, zum Wissensaustausch oderzur Wissensverarbeitung verwendet. Dabei dienen sie meist dem gleichen Zweck: Wis-sen in einer strukturierten und leicht interpretierbaren Form zu repräsentieren. Alseinfachstes Beispiel einer Ontologie-Anwendung sei die Nutzung von Ontologien fürWebseiten-Verzeichnisse genannt1. Solche Ontologien bestehen aus einer hierarchi-schen Kategoriestruktur, wobei den einzelnen Kategorien eine Menge von Webseitenzugeordnet sind. Ähnlich dazu liegen in den meisten Ontologie-basierten Systemen denOntologien eine Menge an Daten zugrunde, also das Wissen, das durch sie repräsen-tiert werden soll. Da sich die Verteilung der Daten innerhalb des Systems über die Zeitverändert, verändern sich damit auch die Anforderungen an die Ontologie. Fast immerist die Ontologie aber statisch oder kann nicht ohne manuelle Interaktion geändert wer-

1beispielsweise http://directory.google.com, http://search.yahoo.com/dir

1

1.1 Motivation 2

den. Ein typisches Beispiel einer solchen Anwendung sind Expertensuchsysteme bzw.Question-Answering Systeme. In solchen Systemen werden Ontologien verwendet, umvon Benutzern gestellte Fragen zu kategorisieren und den geeignetesten Experten zuzu-ordnen (matchen). Da nicht vorhergesehen werden kann, in welchen Bereichen Fragengestellt werden, muss die zugrundeliegende Ontologie recht allgemein gehalten sein,d.h. möglichst viele Themengebiete abdecken und die Untergliederung der Kategori-en (die Granularität) kann nicht allzu fein ausfallen, um eine performante Verarbeitungnicht zu gefährden. Bei Systemen, in denen der Baum nicht nur intern genutzt wird,sondern auch dem Benutzer präsentiert wird, beispielsweise um Fragen manuell zu ka-tegorisieren, wirken sich grosse Bäume negativ auf die Benutzerfreundlichkeit aus, dader Nutzer so durch umfangreiche Kategoriestrukturen navigieren muss, um sein Zielzu erreichen. Für Systeme, die unter Zuhilfenahme einer Ontologie eine automatischeKlassifikation der Fragen vornehmen, bzw. die passenden Experten automatisiert ermit-teln, steht insbesondere der Performanz-Aspekt im Vordergrund, da mit zunehmenderGrösse des Baumes auch der Aufwand für die Klassifikation steigt. Der Vorteil solcherautomatisch klassifizierender Systeme ist, dass beim Aufgeben neuer Suchanfragen dieNavigation durch die Kategoriebäume entfällt, was die Benutzerfreundlichkeit des Sys-tems verbessert. Ausserdem können die Fragen auf diese Weise automatisch den Exper-ten aus den ermittelten Themengebieten zugeordnet werden, sofern die Experten überein entsprechendes Profil verfügen, aus denen ihre bevorzugten Themengebiete hervor-gehen.Unter den bekanntesten Expertensuchsystemen gibt es nur wenige, die eine automati-sche Klassifikation vornehmen: Illumio2, Wondir3, Oyogi4 und Allexperts5. Ein neuesSystem, das als Grundlage für diese Arbeit dient, ist SPREE6, das in einer Kooperationzwischen der TU-Berlin und den Deutsche Telekom Laboratories entstand. SPREE be-nutzt die Ontologie von ODP, allerdings wurden aus Gründen der Performanz nur rund1000 der insgesamt über 500000 Kategorien verwendet. Diese von Hand ausgesuchteUntermenge der Knoten enthält nur die oberen 2-3 Ebenen der vollständigen Ontolo-gie, d.h. die enthaltenen Kategorien sind recht allgemein. Eine Expertenkonzentrationin den Blättern würde dazu führen, dass zwischen den Experten nicht mehr gut differen-ziert werden könnte, da die Tiefe des Baumes nicht mehr ausreichen würde um die Spe-zialisierung der Experten hinreichend genau zu beschreiben. Eine Suchanfrage, die auf

2www.illumio.com3http://www.wondir.com4http://www.oyogi.com5http://allexperts.com6http://www.askspree.de

1.2 Ziel der Arbeit 3

einen solchen Knoten gematcht wird, würde alle darin enthaltenen Experten zurücklie-fern, was die Qualität des Experten-Matchings (also des Findens passender Experten zueiner Suchanfrage) beeinträchtigen würde. Die Alternative wäre, einen grösseren, fein-gliedrigeren Baum zu benutzen, der allerdings mit zunehmender Grösse immer mehrredundante Knoten enthalten würde, in denen keine Experten registriert sind. Ausser-dem nimmt die Performanz des Experten-Matchings mit wachsender Grösse des Bau-mes ab, wie sich später noch zeigen wird.Die Funktionsweise von SPREE wird in Kapitel 3 näher beschrieben.

1.2 Ziel der Arbeit

Ziel der Arbeit ist es, die oben genannten Probleme in SPREE, einem Expertensuch-system mit automatischer, ontologiebasierter Anfrage-Klassifikation, zu lösen. D.h. dieGranularität der Kategorien sollte sich automatisch so den Anforderungen anpassen,dass die Anzahl der Knoten minimiert und die Qualität des Experten-Matchings dabeimöglichst hoch gehalten wird.Um diese Ziele zu erreichen, muss sich die Ontologie von SPREE automatisch an dasSystem anpassen, so dass die Knotenstruktur den sich über die Zeit verändernden Datenangleicht. Dazu soll ein Algorithmus entwickelt werden, der die latente Semantik desSystems untersucht. Dabei ist von Interesse, über welche Themengebiete vorwiegendFragen gestellt werden und in welchen Kategorien Experten registriert sind. Mit Hil-fe dieser Informationen müssen so Knoten aus der Ontologie entfernt oder hinzugefügtwerden, dass häufig angesprochene Themen feingliedriger sind als kaum angesproche-ne. Aufgrund der feineren Untergliederung von stark frequentierten Kategorien soll einebessere Differenzierung der Fragen und Experten erreicht werden und damit auch eineVerbesserung des Experten-Matchings. Durch das Entfernen von nicht oder nur kaumgenutzten Knoten sollen redundante Knoten vermieden und somit eine Steigerung derPerformanz erreicht werden, da die Grösse des Baums direkte Auswirkungen auf dieMatching-Geschwindigkeit hat.

1.3 Aufbau

Der Aufbau der Arbeit gliedert sich wie folgt: In Kapitel 2 werden im ersten Teil diefür das Verständnis der Arbeit nötigen Grundlagen beschrieben. Um den zugrundelie-genden Matching-Algorithmus zu verstehen, werden das aus dem Information Retrieval(IR) Bereich bekannte Vektorraummodell und die darin definierten Ähnlichkeitsmaße

1.3 Aufbau 4

erläutert. Zusätzlich dazu werden auch Vorgehensweisen zur Dimensionsreduktionerläutert, die in der Arbeit verwendet werden um die Anzahl der für das Matchingbenötigte Terme zu reduzieren (Feature Selection) und um die Anzahl der Knoten zureduzieren (Latent Semantic Analysis). Im zweiten Teil des Kapitels werden Arbeitenvorgestellt, die sich mit der gleichen oder ähnlichen Thematik auseinandersetzen.In Kapitel 3 wird das weiter oben erwähnte Expertensuchsystem SPREE vorgestellt undder zugrundeliegende Matching-Algorithmus beschrieben um ein Verständnis dafürzu schaffen, wie Fragen mit Hilfe der Ontologie automatisch den richtigen Expertenzugeordnet werden können.In Kapitel 4 werden die Ursachen der eingangs beschriebenen Probleme ermittelt,um so Lösungsmöglichkeiten dafür entwickeln zu können. Basierend auf diesenErkenntnissen wird dann in Kapitel 5 ein Lösungsansatz entwickelt, dem das Ersetzender statischen Ontologie durch eine dynamische zugrundeliegt.Nachdem ein Lösungsmodell erarbeitet und ein System implementiert wurde, dasdieses Modell umsetzt, erfolgt nun die Beschreibung der Implementation in Kapitel 6.Eine Analyse der durch dieses System erzielten Ergebnisse und ein Vergleich zwischendem statischen und dem dynamischen Ansatz, wird in Kapitel 7 durchgeführt.Abschliessend folgt eine Zusammenfassung der Arbeit und ein Ausblick auf möglicheVerbesserungen und Erweiterungen des entwickelten Systems in Kapitel 8.

Kapitel 2

Grundlagen und verwandte Arbeiten

2.1 Grundlagen

In diesem Abschnitt werden grundlegende Begriffe definiert und elementare Konzepteerklärt, die für das Verständnis der weiteren Arbeit nötig sind.

2.1.1 Ontologien

Im Kontext der Informatik finden sich in der Literatur viele Definitionen des BegriffesOntologie, meist variieren sie in Abhängigkeit von dem verwendeten Einsatzgebiet:

• „Eine Ontologie ist ein gemeinsames Verständnis einer bestimmten Domäne“ [2]

• „Eine Ontologie ist...ein gemeinsames Verständnis einer Domäne, das zwischenMenschen und heterogenen und verteilten Systemen kommuniziert werden kann“[3]

• „Eine Ontologie ist...ein Computer-Modell eines Teils der Welt“ [4]

Der bekannteste Definitionsversuch, der insbesondere im Wissensmanagement, häufigbenutzt wird, stammt von Gruber [5]:

„Eine Ontologie ist die formale, explizite Spezifikation einer gemeinsamen1 Kon-zeptualisierung.“

Nachfolgendes Bild 2.1 des sogenannten semiotischen Dreiecks soll den Begriff

1der Begriff „gemeinsam“ stammt nicht aus der ursprünglichen von Gruber verfassten Definition,sondern wurde später in [6] hinzugefügt

5

2.1 Grundlagen 6

Abbildung 2.1: Semiotisches Dreieck

Konzept im gegebenen Kontext erklären, um die vorhergehende Definition zu verste-hen: Mit Objekt sind reale Objekte der Welt gemeint, die durch Symbole beschriebenwerden. Jedoch geschieht diese Beschreibung nicht immer eindeutig, zum Beispielsteht das Symbol Jaguar sowohl für das Auto als auch für das Tier. Wenn nun jemandden Satz „Der Jaguar ist schneller als ein Zug“ kommuniziert bekommt, bildet er mitHilfe zusätzlichem Wissens (zum Beispiel Kontextwissen, Erfahrungshintergrund, etc.)ein Konzept, d.h. er versteht nun unter dem Symbol Jaguar entweder das Tier oder dasAuto. Da Menschen über unterschiedliches zusätzliches Wissen verfügen, kann dergegebene Satz unterschiedliche Konzeptbildungen hervorrufen. Ontologien, wie siehier definiert wurden, zielen darauf ab, diese unterschiedlichen Interpretationen vonSymbolen eindeutig zu machen, d.h. zu jedem gegebenen Symbol gibt es genau einreales Objekt und genau ein Konzept.

Fast alle vorangegangenen Definitionen bezeichnen eine Ontologie als eine ArtWissen zu repräsentieren, das zwischen verschiedenen Systemen ausgetauscht werdenkann, so dass die beteiligten Systeme dieses Wissen gleich interpretieren können. SolcheOntologien enthalten typischerweise viel Semantik, modelliert durch Konzeptattributeund viele unterschiedliche Relationen zwischen den Konzepten, und werden daher alsschwergewichtige Ontologien bezeichnet [7]. Da in der vorliegenden Arbeit Ontologiennicht zum Austausch zwischen verschiedenen Systemen sondern ausschliesslich zurWissensrepräsentation innerhalb eines Systems genutzt werden, beschreibt die etwasallgemeinere Definition „Eine Ontologie ist ... eine Wissensrepräsentation eines formaldefinierten Systems von Begriffen und Relationen“ [1] den in dieser Arbeit verwendetenBegriff am besten. Wie schon in der Einleitung erwähnt, sind dabei die „Begriffe“

2.1 Grundlagen 7

die Knoten eines Baumes, die die Kategorien(oder auch Topics genannt) auf die dieFragen mit Hilfe des Matching Algorithmus abgebildet werden, repräsentieren, unddie „Relationen“ sind die Kanten im Baum, die zu den Eltern- oder Kindknoten bzw.zu den Ober- oder Unterkategorien eines Topics führen. Eine so definierte Ontologieentspricht im Grunde einer Taxonomie. Dabei wird Wissen in Form einer Hierarchiestrukturiert, d.h. es gibt nur eine Relation, die Vererbungsrelation. Da sich mit nur einerRelation wesentlich weniger Semantik transportieren lässt, werden solche Ontologienals leichtgewichtige Ontologien bezeichnet [7].Formal sei die in dieser Arbeit verwendete Ontologie definiert als ein Wissens-baum O = (C, E , T ,F), bestehend aus einer Menge von Knoten bzw. KategorienC = {c1, ..., cN}, die durch eine Menge von Kanten E miteinander verbunden sind, sodass jede Kategorie ci ∈ C einen eindeutigen Elternknoten hat, der eine Oberkategorierepräsentiert. T entspricht einer Menge von Termen und die Funktion F : 2T 7→ Cordnet jeder Kategorie ci eine Menge von Termen Tci ⊂ T zu.

2.1.2 Textrepräsentation

2.1.2.1 Vektorraummodell

Das Vektorraummodell wurde zum ersten mal 1975 von Salton [8] vorgestellt und istheute das dominierende Textrepräsentationsmodell im Information Retrieval. Texte kön-nen Dokumente, Suchanfragen oder einfach nur eine beliebige Menge von Wörtern sein(wie sie zum Beispiel die oben genannten Topics enthalten). Nachfolgend wird der Be-griff „Dokument“ stellvertretend für beliebige Texte gebraucht. Das Vektorraummodellist ein algebraisches Modell, das Dokumente und Suchanfragen als Vektoren in einemVektorraum (sogenanntem Termraum) darstellt. Dabei wird jedem Term aus einem Do-kumentenkorpus eine Dimension zugeordnet. Da jeder Term eine Dimension repräsen-tiert, kann jedes beliebige Dokument in diesem Raum als Vektor dargestellt werden(Dokumentenvektor). Der Wert des Dokumentenvektors in einer bestimmten Dimensionist ungleich 0 genau dann, wenn der zugehörige Term in dem Dokument vorkommt.Dieser Wert wird als (Term-)Gewichtung bezeichnet, und kann beispielsweise der Häu-figkeit des Auftretens des Wortes im Dokument entsprechen.Eine wesentlich weiter verbreitete und auch in SPREE genutzte Art der Gewichtungist die sogenannte tfidf -Gewichtung. Sie setzt sich zusammen aus der Häufigkeit einesTerms ti ∈ T in einem Dokument dj , welche mit tfij bezeichnet wird, und der inversenDokumenten-Häufigkeit idfi = m

dfi, wobeim die Gesamtanzahl der Dokumente bezeich-

net und dfi die Dokumenten-Häufigkeit, also die Anzahl der Dokumente in denen der

2.1 Grundlagen 8

Abbildung 2.2: Veranschaulichung des Vektorraummodells in einem Raum mit nur 3Termen. Die blauen Pfeile stellen 3 unterschiedliche Dokumente und ihre Repräsentati-on im Vektorraum dar.

Term ti vorkommt. Zusammengesetzt ergibt sich das tfidf-Gewicht

wij = tfij · idfi (2.1)

Empirische Ergebnisse haben gezeigt, daß normalisierte tfij und logarithmisch ge-dämpfte dfi Werte zu besseren Ergebnissen führen. Somit sieht die Gewichtung wiefolgt aus:

wij =tfij

maxk(tfkj)· log(idfi) (2.2)

Um grössere Dokumente nicht stärker zu gewichten als kleinere Dokumente und um dieGewichte auf das Intervall [0,1] zu beschränken, werden die Werte oft im Nachhineinnoch durch Kosinus Normalisierung normalisiert ([9]):

tfidfij =wij√∑Ts=1w

2sj

(2.3)

Formal lässt sich das Vektorraummodell wie folgt beschreiben (s. [10, Kap.1.3.6.1]):

Sei T = {t1, ..., tn} eine endliche Menge von Termen und D = {d1, ..., dm} ei-ne Menge von Dokumenten. Für jedes Dokument di ∈ D sei zu jedem Term tk ∈ T

ein Gewicht wi,k ∈ R gegeben. Die Gewichte des Dokuments di lassen sich zu einemVektor wi = (wi,1, ..., wi,n) ∈ Rn zusammenfassen, der das Dokument im Vektorraumrepräsentiert (Dokumentenvektor). Analog dazu werden auch Suchanfragen durch

2.1 Grundlagen 9

eine Menge gewichteter Terme als Vektoren q ∈ Rn dargestellt (Anfragevektor,

Query-Vektor).

2.1.2.2 Ähnlichkeitsmaße

Um nun Suchanfragen einem Dokument oder, wie in unserem Fall, einer Kategoriezuordnen zu können muss es ein Maß dafür geben wie ähnlich sich diese sind. Dafürwird eine Ähnlichkeitsfunktion sim : Rn × Rn− > R definiert, die jedem Paar auszwei Vektoren x, y ∈ Rn einen reellen Ähnlichkeitswert sim(x, y) zuweist.

Beispiele für Ähnlichkeitsmaße sind das Dice-, Overlap- und Jaccard-Maß [10,Kap.1.3.6.5]. Am häufigsten, wie auch in SPREE, wird jedoch das Cosinusmaßverwendet:

sim(x, y) =x · y|x| · |y|

Wie der Name schon sagt, wird durch dieses Maß der Cosinus des Winkels zwischenzwei Vektoren im Rn berechnet. Je kleiner der Winkel zwischen den Vektoren ist, destoähnlicher sind die Dokumente und umso höher ist auch der Cosinus. Für zwei identischeDokumente ergibt sich demnach ein Ähnlichkeitswert von 1.

2.1.3 Dimensionsreduktion

Um ein Problem performanter oder effizienter lösen zu können, ist es oft nötig die Kom-plexität des Raumes, in dem das Problem definiert ist, zu reduzieren. Nachfolgend wer-den mehrere Verfahren aus verschiedenen Bereichen aufgezeigt, die diese Aufgabe lö-sen.

2.1.3.1 Term-Preprocessing

Term-Preprocessing ist ein Vorgang, der es zum Ziel hat, die Mannigfaltigkeit vonTermen in Dokumenten zu reduzieren, um so den Vergleich zwischen Dokumentenund damit auch Termen zu vereinfachen. Das Preprocessing besteht aus mehreren Teil-schritten, die, je nach Anwendungsgebiet, nicht alle notwendigerweise durchgeführtwerden müssen.

2.1 Grundlagen 10

Als erstes werden üblicherweise aussagelose Terme entfernt (sogenannte Stopp-

wörter). Als aussagelos werden diejenigen Terme betrachtet, die sehr häufig in einerSprache vorkommen und so eher ein Rauschen darstellen, als etwas über den Inhalteines Dokumentes auszusagen (zum Beispiel und,oder,der,...). Stoppwörter könnenanhand von Listen, die für die wichtigsten Sprachen verfügbar sind, gefiltert werdenoder über die Wahrscheinlichkeit ihres Auftretens in einer Sprache. Diese Wahrschein-lichkeiten sind wohlbekannt, für die deutsche Sprache sind solche Werte beispielsweiseüber das Wortschatz-Lexikon2 der Universität Leipzig abrufbar.

Als zweiter Schritt werden meist die Worte auf ihren Wortstamm zurückgeführt(Stemming). Beispielsweise werden die Terme bunter aus einem Dokoment d1 undbuntesten aus einem Dokument d2 durch bunt ersetzt, was dazu führt, dass bei einemVergleich zwischen d1 und d2 sich die Dokumentenähnlichkeit (richtigerweise) erhöhenwürde. Die zwei verbreitetsten Varianten, den Wortstamm eines Wortes zu ermitteln,sollen nachfolgend vorgestellt werden: Einerseits werden, ähnlich wie bei einem Duden,die Worte in ihren verschiedenen morphologischen Formen und dem dazugehörigenWortstamm in einer Datenbank gespeichert, so dass über eine Abfrage zu einembeliebigen Wort der zugehörige Wortstamm zurückgeliefert wird (Lexikon-basiertes

Stemming).Die zweite, aufgrund ihrer überlegenen Performanz weit häufiger eingesetzte Variante,ist ein Stemming auf Basis eines sprachspezifischen Algorithmus (Algorithmus-

basiertes Stemming). Ein solcher Algorithmus verkürzt ein Wort nach bestimmtenvordefinierten Regeln, bis keine Regel mehr anwendbar ist. Der bekannteste Stemmer,der ursprünglich für die englische Sprache entwickelt wurde, für den es aber mittler-weile auch eine Portierung in die deutsche Sprache gibt, ist der Porter-Stemmer [11].

Ein weiterer Preprocessing Schritt, der zwar in der vorliegenden Arbeit keineAnwendung findet, jedoch der Vollständigkeit halber genannt werden soll, ist dasErsetzen der Terme durch Synonyme, was genauso wie das Lexikon-basierte Stemmingrealisiert wird, nur das hier einer Gruppe von Wörtern mit der gleichen Bedeutung einWort aus dieser Gruppe als Stellvertreter zugeordnet wird. So könnten die 3 Termewieso, weshalb, warum auf den Term weshalb reduziert werden.In SPREE und in dieser Arbeit wird die Vielfalt der Terme und damit auch derenAnzahl und die Dimensionen des Termraums durch Listen-basiertes Entfernen vonStoppwörtern und durch den Porter-Stemmer reduziert.

2http://wortschatz.uni-leipzig.de/

2.1 Grundlagen 11

Eine weitere Form der Reduktion des Termraums, bei dem, ähnlich wie bei denStoppwörtern, versucht wird weniger aussagekräftige Terme zu eliminieren, wird imnächsten Abschnitt vorgestellt.

2.1.3.2 Feature Selection

Wie in [12] gezeigt, genügt zum Klassifizieren von Dokumenten (s. Abschnitt 2.1.4) nurein Bruchteil der in einem Textkorpus befindlichen Terme. Dieses wird darauf zurück-geführt, dass viele Terme eine geringe oder gar keine Aussagekraft über die zugehö-rige Kategorie innehaben und somit nur Rauschen darstellen. Unter Aussagekraft einesTerms soll im Folgenden verstanden werden, in welchem Maße der Term die zugehörigeKlasse charakterisiert.Unter Feature Selection versteht man im Bereich des Information Retrieval das Her-ausfiltern der aussagekräftigsten Terme T ′ aus einer Menge von Termen T , so dass|T ′| << |T |, wobei mit T ′ eine möglichst hohe Effektivität erzielt wird [9]. Die Auswahlder Terme geschieht mit Hilfe verschiedener, aus der Informationstheorie und Statistikstammender Heuristiken. Diese Heuristiken versuchen auf unterschiedliche Weise dieAussagekraft eines jeden Terms bezüglich der zugehörigen Klasse zu bestimmen. Da-zu wird untersucht, ob es eine statistische Abhängigkeit zwischen einem Term und denKlassen gibt, in denen der Term vorkommt. Tritt ein Term wesentlich häufiger in einerKlasse auf als in anderen, ist er von dieser Klasse statistisch abhängig und somit aus-sagekräftiger. Auf diese Weise wird jedem Term ein Koeffizient zugeordnet. DiejenigenTerme, die über eine geringe Aussagekraft verfügen, also deren Koeffizient einen empi-risch zu bestimmenden Schwellwert unterschreiten, werden verworfen.Eine Übersicht und Einstufung der verbreitetsten Heuristiken findet sich in [9], S.20.Da, nach [9], Odds Ratio (OR) zu den effektivsten gehört und mit dem in dieser Ar-beit genutzten Naive Bayes Klassifizierer (s. 2.1.4) die vergleichsweise besten Klassi-fikationsergebnisse erzielt werden ([13, 14]), soll diese Heuristik hier kurz vorgestelltwerden:

OR(t, ci) =

P (t|ci)1−P (t|ci)P (t|ci)

1−P (t|ci)

=P (t|ci) · (1− P (t|ci))(1− P (t|ci)) · P (t|ci)

(2.4)

P (t|ci) ist die Wahrscheinlichkeit, dass ein Term t aus einem Dokument aus der Klasseci stammt, während P (t|ci) die Wahrscheinlichkeit beschreibt, dass das Dokument nichtaus der Klasse ci stammt. Die erste Formel beschreibt am besten die Idee hinter OddsRatio: Es drückt die Chance3 des Vorkommens eines Wortes in einer Klasse normali-

3Chance im Sinne von Odds: http://de.wikipedia.org/wiki/Odds

2.1 Grundlagen 12

siert durch die Chance des Vorkommens in den restlichen Klassen aus. Dadurch erhal-ten Terme, die in einer Klasse häufig und in anderen kaum vorkommen, eine bessereBewertung, da so der Zähler einen hohen Wert erzielt und der Nenner gegen 0 tendiert.

2.1.3.3 Latent Semantic Analysis

Während bei Feature Selection versucht wird aus allen Termen diejenigen zu filtern,die eine gewisse Aussagekraft bezüglich einer Klasse haben, werden bei der Latent Se-mantic Analysis (LSA)4 Terme zu sogenannten Konzepten zusammengefasst und dieDokumente durch diese beschrieben. Dazu wird zunächst eine Dokument-Term MatrixA ∈ Rm×n erstellt in der die Spalten-Vektoren Dokumente und die Zeilen-VektorenTerme repräsentieren. Ein Eintrag ai,j in der Zeile i und Spalte j der Matrix A hält dasGewicht des Termes i in dem Dokument j. Als nächstes wird A durch ein Verfahrennamens Singulärwertzerlegung (engl. Singular Value Decomposition, im folgenden mitSVD abgekürzt) in das Produkt dreier Matrizen zerlegt:

A = U · S · V T , U ∈ Rm×r, S ∈ Rr×r, V T ∈ Rr×n (2.5)

Eine Veranschaulichung der Zerlegung erfolgt in Abbildung 2.3. Diese Zerlegung hatfolgende Eigenschaften[15, 16]:

• Eine solche Zerlegung ist für jede beliebige Matrix möglich

• Die Spalten in U und V sind orthonormal und werden als linke bzw. rechte singu-

läre Vektoren bezeichnet4Auch als Latent Semantic Indexing bezeichnet

Abbildung 2.3: Zerlegung einer Matrix durch SVD

2.1 Grundlagen 13

• S ist eine Diagonalmatrix und die enthaltenen Werte werden als Singulärwerte

bezeichnet und sind nach ihrer Grösse sortiert

• U und V enthalten die Eigenvektoren von ATA bzw AAT

• Die Singulärwerte sind die Wurzeln der Eigenwerte von ATA

• Wählt man nur die k grössten Singulärwerte und die entsprechenden rechten undlinken singulären Vektoren erhält man so eine Annäherung Ak = Uk · Sk · V T

k anA

• Es lässt sich zeigen, dass Ak die Annäherung vom Rang k mit minimalem Fehlerhinsichtlich der Frobeniusnorm ist

Eine solche Annäherung hat ausserdem den Vorteil, dass die Terme und Dokumentenun in einem Konzeptraum dargestellt werden: Die Zeilen von U repräsentieren genauwie in A die Terme. Die Spalten werden als Konzepte bezeichnet und bilden die Or-thonormalbasis des Konzeptraumes. Die Spaltenvektoren werden Konzepte genannt, dasie thematisch ähnliche Begriffe in sich zusammenfassen, d.h. Terme, die häufig zusam-men in mehreren Dokumenten vorkommen, also eine hohe Korrelation haben, liegeninnerhalb eines Konzeptes näher beieinander. Die Dokumente werden durch die Spal-tenvektoren in V T

k im Konzeptraum repräsentiert, d.h. die Zeilen aus V Tk entsprechen

den Konzeptraum-Dimensionen.Folgendes Beispiel soll diesen Vorgang veranschaulichen: Gegeben sei folgende Term-Dokument-Matrix A

Dokument d1 d2 d3 d4 d5 d6 d7

Term

DB 2 1 3 1 0 0 0

SQL 4 1 2 0 0 0 0

Abfrage 2 0 3 1 0 0 0

Agenten 0 0 0 0 1 3 1

Ontologie 0 0 0 0 2 1 4

Bei den Dokumenten d1 bis d4 handelt es sich offensichtlich um Datenbank relevanteTexte, während es bei den restlichen drei Dokumenten anscheinend um Ontologien imZusammenhang mit Agententechnologien geht. Eine Zerlegung mittels SVD und Re-

2.1 Grundlagen 14

duktion auf Rang 2 führt zu folgenden Matrizen:

Ak =

−0.56 0

−0.64 0

−0.53 0

0 0.51

0 0.86

·

(6.75 0

0 5.13

)·

(−0.70 −0.18 −0.67 −0.16 0 0 0

0 0 0 0 0.44 0.46 0.77

)

(2.6)

Uk Sk V Tk

In der linken Spalte von Uk kann man nun erkennen, dass die ersten drei Datenbank-relevanten Terme zu einem Konzept zusammengefasst wurden, während die letzten zweiTerme ein weiteres Konzept bilden. In Vk lässt sich ablesen, dass die ersten vier Doku-mente, also die ersten vier Spalten, in der ersten Zeile ähnliche Werte haben. Wie obenschon beschrieben entspricht die erste Zeile der ersten Dimension im Konzeptraum, alsodem ersten Konzept. Da die zweite Dimension für diese Dokumente nur Nullen enthält,wurden die Dokumente eindeutig dem ersten Konzept zugeordnet. Analog dazu wurdendie restlichen Dokumente dem zweiten Konzept zugeordnet.Wie in diesem Beispiel gut zu erkennen ist, werden die Dokumente nun in einem 2-dimensionalen Raum dargestellt und nicht mehr wie ursprünglich im 5-dimensionalenTermraum. LSA wird oft dazu benutzt eine Dokumentenbasis in einen niedriger dimen-sionierten Raum abzubilden, um dann in diesem Raum die zu einer Anfrage passendenDokumente zu finden oder um die Beziehungen zwischen den Termen und Dokumen-ten untereinander zu untersuchen. Multipliziert man allerdings die reduzierten Matrizenaus und berechnet so die Annäherung Ak, so lässt sich erkennen, dass sich die Term-Gewichtungen durch die Reduktion verändert haben:

Ak =

2.63 0.67 2.52 0.60 0 0 0

3.03 0.77 2.91 0.70 0 0. 0.

2.51 0.63 2.40 0.58 0 0 0

0 0 0 0 1.13 1.21 2.00

0 0 0 0 1.92 2.05 3.41

(2.7)

In der Ausgansmatrix hatten die Terme Abfrage und SQL keine Gewichtung in denDokumenten d2 bzw. d4, da sie in diesen Dokumenten nicht vorkamen. Aufgrund derKorrelation der Terme DB, SQL und Abfrage wurden durch die Approximation Ak dieGewichtungen so verändert, dass Abfrage und SQL in den Dokumenten d2 bzw. d4 anRelevanz gewonnen haben, obwohl die Terme nicht direkt in den Dokumenten vorkom-

2.1 Grundlagen 15

men. Diese Neu-Gewichtung der Terme, bedingt durch die Korrelationen untereinander,soll später genutzt werden, um die relevanten Knoten in der Ontologie zu identifizieren(s. Abschnitt 5.2.3).Es sei noch angemerkt, dass die Wahl von k von den zu analysierenden Daten und demjeweiligen Anwendungsgebiet abhängt. Ein optimaler Wert für k muss also empirischermittelt werden.

2.1.4 Textklassifikation

Textklassifikation (auch Textkategorisierung) kann formal durch eine Funktion f :

D × C → {0, 1} beschrieben werden, die einem Dokument d ∈ D und einer Ka-tegorie c ∈ C einen booleschen Wert zuordnet. Das Ziel der Textklassifikation ist,die Funktion f , welche als Klassifikator bezeichnet wird, so zu gestalten, dass einemDokument-Kategorie Paar (d, c) genau dann eine 1 zugeordnet wird, wenn ein mensch-licher Experte d in die Kategorie c einordnen würde. Ansonsten wird dem Paar eine 0zugeordnet.Grundsätzlich wird zwischen überwachter (supervised) und unüberwachter (unsupervi-

sed) Klassifikation unterschieden. Bei der überwachten Klassifikation, welche in die-ser Arbeit zur Anwendung kommt, wird versucht f aus einer gegebenen sogenanntenTrainingsmenge zu erlernen. Diese Trainingsmenge besteht aus mehreren, von Handklassifizierten Dokumenten DT , d.h. zu jedem Paar (d, c), d ∈ DT ist der zugeordneteboolesche Wert bekannt. Bei der unüberwachten Klassifikation existiert kein Vorwissenüber richtige Kategoriezuordnungen. Es wird versucht eine Kategoriestruktur innerhalbvon D mit Hilfe eines zwischen den Dokumenten definierten Ähnlichkeitsmaßes zu fin-den. Dazu werden ähnliche Dokumente zu Gruppen(cluster) zusammengefasst und alszu einer bestimmten Kategorie zugehörig betrachtet.

2.1.4.1 Naive Bayes Klassifikator

In Kapitel 3 wird der von SPREE benutzte Klassifikator beschrieben, der durch Aus-nutzen des hierarchischen Aufbaus der Ontologie eine Suchanfrage in die Kategoriender Ontologie einordnet. Naive Bayes ist ein weiterer Klassifikator, der später in dieserArbeit verwendet wird und soll deshalb an dieser Stelle vorgestellt werden.Naive Bayes versucht, wie alle probabilistischen Klassifikatoren, durch Abschätzungvon P (ci|dj), also der Wahrscheinlichkeit, dass ein Dokument, repräsentiert durch einenDokumentenvektor dj = {w1, ..., wn}, zu der Klasse ci gehört, die Funktion f anzunä-

2.1 Grundlagen 16

hern. Die Abschätzung von P (ci|dj) basiert auf Bayes’ Theorem:

P (ci|dj) =P (ci)P (dj|ci)

P (dj)(2.8)

Der zugrundeliegende Ereignisraum ist der Dokumentenraum, d.h. P (ci) ist die Wahr-scheinlichkeit, dass ein zufällig ermitteltes Dokument zu der Klasse ci gehört und P (dj)

die Wahrscheinlichkeit, dass ein zufällig gewähltes Dokument durch den Dokumenten-vektor dj repräsentiert wird. Die Berechnung von P (dj) ist schwierig, da die Anzahlder möglichen Dokumentenvektoren zu hoch ist. Da P (dj) aber unabhängig von ci ist,stellt es bei der Berechnung von P (ci|dj) für unterschiedliche i und ein festem dj le-diglich eine Konstante dar, was bedeutet, dass lediglich der Zähler ausschlaggebend ist.Die Umformung der Definition der bedingten Wahrscheinlichkeit P (A|B) = P (A,B)

P (B)zu

P (A,B) = P (B)P (A|B) zeigt, dass der Zähler der gemeinsamen WahrscheinlichkeitP (ci, dj) entspricht:

P (ci, dj) = P (ci)P (dj|ci) (2.9)

Das oben angesprochene Problem bei der Berechnung von P (dj) gilt auch für die Be-rechnung von P (dj|ci). Um dieses Problem zu umgehen, wird davon ausgegangen, dasszwei beliebige Terme eines Dokumentes statistisch unabhängig voneinander sind, waszu folgender Gleichung führt: 5

P (dj|ci) =n∏k=1

P (wkj|ci) (2.10)

P (wkj|ci) bezeichnet hierbei die Wahrscheinlichkeit mit der der k-te Term aus demDokument repräsentiert durch dj in der Klasse ci vorkommt. Die Annahme der Unab-hängigkeit zwischen den Termen zeichnet Naive Bayes aus. Die Bezeichnung „naive“rührt daher, dass die Annahme meist nicht zutrifft, dennoch erreicht Naive Bayes oftgute Ergebnisse.Wird diese Umformung in (2.9) eingesetzt, ergibt sich so

P (ci, dj) = P (ci)n∏k=1

P (wkj|ci) (2.11)

Um mit Hilfe dieser Gleichung die passendste Klasse zu einem unbekannten Doku-ment dj zu finden, muss P (ci, dj) für jede Klasse berechnet werden. Dazu werden P (ci)

und P (wkj|ci) über den Dokumenten der Trainingsmenge berechnet. Die höchste so aus

5Eine genaue Herleitung findet sich unter http://en.wikipedia.org/wiki/Naive_Bayes_classifier

2.1 Grundlagen 17

(2.11) errechnete Wahrscheinlichkeit zeichnet auch die passendste Klasse zu dem gege-benen Dokument aus.Bei der Berechnung von P (ci, dj) durch Gleichung 2.11 ergeben sich für mancheKlassen eine Wahrscheinlichkeit von 0, wenn ein Wort aus dj nicht in ci vorkommt(P (wkj|ci) = 0). Die übrigen Worte aus dj haben somit keinen Einfluss mehr auf dieWahrscheinlichkeit, selbst wenn sie mit einer hohen Gewichtung in ci vorkommen wür-den. Um ein solches Verhalten zu vermeiden, wird P (wkj|ci) im Allgemeinen durcheine Glättungsfunktion ersetzt [17]. In dieser Arbeit wird dafür die sogenannte Laplace

Glättung ([17]) genutzt. Dabei wird P (wkj|ci) abgeschätzt durch

P (wkj|ci) =ε+ tfwkji

ε · n+∑n

k′=1 tfwk′ji(2.12)

ε ist hierbei ein frei definierbarer Parameter und tfwkji bezeichnet die Häufigkeit mit derder k-te Term aus dj in ci auftritt.

2.1.4.2 Evaluierung

Um die Performanz eines IR-Systems evaluieren und somit auch verschiedene Verfah-ren miteinander vergleichen zu können, existieren verschiedene Maße, die eine Aussageüber die Effektivität eines Verfahrens machen. Die zwei bekanntesten und am häufigs-ten eingesetzten Maße sind Precision und Recall, wobei Precision die Genauigkeit einesVerfahrens beschreibt und Recall die Vollständigkeit. Beide Maße lassen sich in ver-schiedenen IR-Bereichen anwenden. Im klassischen Dokumenten-Retrieval beispiels-weise, bei dem zu einer gegebenen Suchanfrage aus einer Dokumentenmenge die rele-vantesten Dokumente gefunden werden sollen, gibt Precision den prozentualen Anteilder tatsächlich relevanten Dokumente, von den als relevant eingestuften an. Der Recallhingegen beschreibt die Vollständigkeit als den Anteil der gefundenen, relevanten Do-kumenten von allen tatsächlich relevanten Dokumenten. Analog dazu lassen sich beideMaße hinsichtlich eines Textklassifikations-Systems wie folgt berechnen: Sei G(di) dieMenge der durch den Klassifikator zu einem Dokument di zugeordneten Klassen undR(di) die Menge der tatsächlich zu di gehörenden Klassen. Dann ist Precision gegebendurch

precision =|G(di) ∩R(di)||G(di)|

(2.13)

2.2 Verwandte Arbeiten 18

also als der Anteil, der richtigen zu di gefundenen Klassen von allen gefundenen Klas-sen. Der Recall lässt sich berechnen aus

recall =|G(di) ∩R(di)|

R(di)(2.14)

Dies entspricht dem Anteil, der richtigen zu di gefundenen Klassen von allen zu di ge-hörenden Klassen.Um nun zwei Systeme mit Hilfe der vorgestellten Maße zu vergleichen, müssten stetsPaare der Werte miteinander verglichen werden. Dieses hat sich als unbefriedigend her-ausgestellt, da oft nicht klar ist, welches Werte-Paar nun besser ist, wenn zum Beispielein Paar einen höheren Precision-Wert hat, dafür aber einen schlechteren Recall. Einhäufig eingesetztes Maß, das beide Werte in sich vereint ist das sogenannte F-Maß:

Fα =(1 + α) · (precision · recall)

α · precision+ recall(2.15)

Über α lässt sich der Einfluss von Precision und Recall beliebig steuern, für α > 1

wird der Recall höher gewichtet und für 0 < α < 1 der Precision-Wert. Da die meistenSysteme versuchen beide Werte gleichermaßen zu maximieren, wird meist das gewich-tete harmonische Mittel zwischen Precision und Recall benutzt, welches man für α = 1

erhält:F1 =

2 · precision · recallprecision+ recall

(2.16)

Um ein (überwachtes) Textklassifikations-System evaluieren zu können, wird eine Test-menge benötigt, also eine Menge an Dokumenten, von denen, genau wie bei der Trai-ningsmenge, die Klassenzugehörigkeit bekannt ist. Die Evaluierung soll eine Aussageüber die Performanz eines Klassifikators hinsichtlich unbekannter Dokumente geben,daher müssen die Trainings- und Testmenge disjunkt sein, d.h. wären Trainingsdoku-mente in der Testmenge, würden diese das Ergebnis verfälschen, da der Klassifikatordiese Dokumente bereits kennt.

2.2 Verwandte Arbeiten

Wie schon in der Einleitung beschrieben, beschäftigt sich die vorliegende Arbeit imKern mit der Entwicklung eines Algorithmus, der eine von einem Expertensuchsystemgenutzte Ontologie dynamisch an die dem System zugrundeliegenden Daten anpasst.In [18] wird ebenfalls ein Ansatz beschrieben, Ontologien dynamisch aus einer


gegebenen Menge von Dokumenten zu generieren. Allerdings ist dieser Vorgang nichtvoll-automatisch, sondern benötigt die Überwachung von menschlichen Experten aufdem Gebiet aus dem die Ontologie stammt.

Da sich Ontologien gut dazu eignen, Wissen formal und eindeutig zu repräsentieren,wurden in den letzten Jahren eine unüberschaubare Menge an, meist domänenspezi-fischen, Ontologien erschaffen, die sich teilweise überlappen. Um dieses vorhandeneWissen wiederverwenden zu können, ist es oft nötig, diese überlappenden Ontologienmiteinander zu vereinigen oder einander anzugleichen [19, 20, 21, 22]. In diesemKontext wird oft von dynamischen Ontologien gesprochen, womit aber nicht das indieser dieser Arbeit behandelte Thema gemeint ist.

Das Problem, eine gegebene Ontologie wie gefordert durch Hinzufügen oder Entfernenvon Knoten an das System anzupassen, kann durch das Problem ersetzt werden, auseiner grossen (im Sinne der abgedeckten Kategorien) und zugleich sehr feingliedrigenOntologie eine auf das System zugeschnittene Subontologie zu extrahieren (näheresdazu s. 5). In dem Bereich der Ontologie Extraktion wurden Optimierungs-Schemataeingeführt, um „das subjektive Verständnis von Qualität zu objektivieren“ [23, 24]: DieOptimierungs-Schemata enthalten Regeln und Algorithmen, die definieren, welchenAnforderungen eine Subontologie genügen soll, z.B. Grad der Allgemeinheit oderVollständigkeit. Es können eigene Optimierungs-Schemata definiert werden und indas vorgestellte System eingebracht werden. Dabei enthält das System auch schonvorgefertigte Schemata, die zum Beispiel die Ontologie bis auf eine gegebene Menge anKnoten beschneiden. Dieser Vorgang ist recht trivial. Die eigentliche Herausforderungliegt in der Identifikation der Knoten, die in der Subontologie enthalten sein müssenund welche aus der Ausgangs-Ontologie entfernt werden können. Da diese Aufgabevom System nicht gelöst wird, ist es auch nicht dazu geeignet, das dieser Arbeitzugrundeliegende Problem zu lösen.

In [25] wird aus einer breitgefächerten, allgemeinen Ontologie mit über 50000Knoten eine domänenspezifische Subontologie mit einer überschaubaren Anzahl anKnoten extrahiert. Dazu wurden als erstes von Hand eine geringe Anzahl von Knotenausgesucht, die in die Ziel-Domäne passen. Ausgehend von diesen Knoten wurdenüber eine Reihe von strukturellen und probabilistischen Heuristiken weitere Knotenidentifiziert, die Teil der Subontologie sein sollten. Auf das genauere Verfahren sollhier nicht näher eingegangen werden, da sowohl die Auswahl der Ausgangsknoten als


auch manche der genutzten Heuristiken manuelle Interaktionen erfordern, was nichtden Anforderungen an das hier zu entwickelnde System genügt. Seidenberg und Rectorstellen in [26] einen Algorithmus vor, der aus einer in der Ontologiesprache OWLdefinierten domänenübergreifenden Ontologie eine auf eine vorher definierte Domänezugeschnittene Unterontologie extrahiert. Jedoch ist dieser Algorithmus nicht auf dashier behandelte Problem anwendbar, da es sich hierbei um eine schwergewichtigeOntologie handelt und der Algorithmus auf den zusätzlichen Relationen aufbaut, die inunserer leichtgewichtigen Ontologie nicht gegebenen sind.

Kapitel 3

SPREE - Ein Expertensuchsystem

SPREE stellt eine frei zugängliche online Gemeinschaft dar, in der Benutzer Fragenstellen können, die automatisch mit Hilfe einer Ontologie klassifiziert und zu anderenNutzern weitergeleitet werden, die in den Kategorien Experten sind, in denen die Frageklassifiziert wurde. Die Nutzer des Systems sind also gleichzeitig Experten, die ver-suchen die ihnen zugeleiteten Fragen zu beantworten. Die zwei Begriffe Nutzer undExperte sind demnach in der gesamten Arbeit auch miteinander austauschbar.Wie schon eingangs beschrieben, soll in dieser Arbeit ein Weg gefunden werden inSPREE die zugrundeliegende Ontologie so zu gestalten, dass ihre Knotenstruktur sichautomatisch an die dem System zugrundeliegenden Daten anpasst. Wie diese Daten aus-sehen und wie sie innerhalb von SPREE genutzt werden, um eine Frage automatischdem richtigen Experten zuzuordnen, soll in diesem Kapitel in Anlehnung an [27, 28]erläutert werden.

3.1 Die Ontologie

In SPREE wird eine streng hierarchische Ontologie O = (C, E , T ,F) , wie in Kapitel 2definiert, mit ca. 1000 Knoten benutzt. Um die in der Ontologie enthaltenen Kategorienzu charakterisieren wird jedem Knoten c ∈ C eine Menge von Schlüsselwörtern Tc ⊂ T

zugeordnet. Diese Schlüsselwörter wurden aus den 10 besten Suchergebnissen des WebServices der Suchmaschine Yahoo!1 ermittelt. Dabei wurde, wie in [29] beschrieben,nach dem Knotennamen und, falls vorhanden, dem übergeordneten Knotennamen ge-sucht. Um nun der Ober-/Unterkategorie-Beziehung zwischen den Knoten gerecht zuwerden, wurden die Schlüsselwörter einer jeden Kategorie c mit den Schlüsselwörtern

1http://developer.yahoo.com/search

21

3.2 Abbildung auf die Ontologie 22

aller Kindknoten von c vereinigt: Tc = Tc ∪ (∪i∈K(c)Ti) wobei K(c) die Kinder von crepräsentiert. Als zweiten Schritt wurden nun Tc durch Tc ersetzt für alle c ∈ C.

3.2 Abbildung auf die Ontologie

Um die Anfragen an das System den richtigen Experten zuzuordnen, werden in SPREEsowohl die Expertenprofile als auch die Fragen zunächst auf die Ontologie abgebildet.Das Ergebnis dieser Abbildung ist ein Unterbaum (Subontologie) der Ontologie, derdie Fragen bzw. Experten repräsentiert. Die Abbildung der Expertenprofile nehmen dieNutzer selbst vor, indem sie bei der Registrierung im System sowohl die Kategorien an-geben, in denen sie sich selbst als Experte sehen, als auch den Grad der Expertise aufdem jeweiligen Gebiet auf einer Skala von 1 bis 5. Diese so spezifizierten Kategorienkönnen als Unterbaum der Ontologie betrachtet werden und im Profil der Nutzer gespei-chert werden, um später mit einkommenden Fragen verglichen werden zu können. DieAbbildung der Suchanfragen auf die Ontologie geschieht über einen Algorithmus, derdie hierarchische Struktur der Ontologie ausnutzt. Diesem Algorithmus liegt ein direkterVergleich zwischen der Suchanfrage und den einzelnen Knoten der Ontologie zugrun-de. Dieser Vergleich wird dadurch ermöglicht, dass sowohl die Suchanfrage als auch dieKnoten durch eine Menge von Schlüsselwörtern repräsentiert werden und somit als Vek-toren in einem Vektorraum dargestellt werden können (s. Abschnitt 2.1.2.1). Dieser Vek-torraum S(T ) ⊂ RM , |T | = M wird über der Menge aller in den Knoten enthaltenenTerme definiert (Termraum). Die zu einem Term ti ∈ Tcj gehörige Dimension der Vek-torrepräsentation v(cj) ∈ S(T ) eines Knoten cj enthält das zugehörige tfidf-Gewichttfidfij . Als Ähnlichkeitsfunktion für den Vergleich zwischen einer Suchanfrage q undeinem Knoten cj wird das Cosinus-Maß verwendet:

cos(q, cj) :=v(q) · v(cj)|v(q)| · |v(cj)|

(3.1)

Formal ausgedrückt ist dieses die theoretische Grundlage für die Ähnlichkeitsberech-nung in SPREE. Da ein Vektor v(cj) üblicherweise überwiegend Nullen enthalten wür-de (wegen |T | >> |Tcj |), wurden bei der Implementation die Terme nicht indiziert umeinen Termraum S(D) zu erzeugen. Der Cosinus zwischen q und cj wird direkt überihre Termmengen Tq bzw. Tcj berechnet:

sim(q, cj) :=

∑ti∈Tq∩Tcj

tfidfiq · tfidfij√|Tq| ·

√|Tcj |

(3.2)

3.3 Ermittlung der Experten 23

Mit Hilfe dieses Ähnlichkeitsmaßes kann nun mit folgendem Algorithmus eine Suchan-frage q auf einen Unterbaum der Ontologie abgebildet werden:

1. Wähle alle Knoten {ch1 , ..., chH} der obersten Stufe aus, die als Elternknoten

den Wurzelknoten haben und berechne die Ähnlichkeitswerte sim(q, chi), i ∈

{1, ..., H}

2. Bestimme den Knoten cx ∈ {ch1 , ..., chH} mit dem höchsten Ähnlichkeitswert

3. Füge cx zu dem gesuchten Unterbaum hinzu

4. Bestimme alle Kindknoten {ck1 , ..., ckK} von cx und für jeden Kindknoten cki

berechne die Ähnlichkeiten sim(q, cki), i ∈ {1, ..., K}

5. Berechne den Erwartungswert µ und die Standardabweichung σ der in 4. berech-neten Ähnlichkeitswerten

6. Wähle alle Knoten {cx} ⊂ {ck1 , ..., ckK} aus für die gilt: sim(q, cx) > µ + ασ,

wpbei α ≥ 0 ein vorher festgelegter Parameter ist

7. Für jeden Knoten cx aus {cx} führe den Algorithmus ab Schritt 3 durch bis dieletzte Ebene des Baumes erreicht ist

3.3 Ermittlung der Experten

Durch den im letzten Abschnitt beschriebenen Algorithmus erhalten wir einen Unter-baum der Ontologie als Repräsentation einer Suchanfrage. Da, wie oben beschrieben,die Experten in der gleichen Form repräsentiert sind, muss nun ein Ähnlichkeitsmaßdefiniert werden, das den Vergleich zwischen zwei Subontologien erlaubt, um soden geeignetesten Experten zu einer bestimmten Frage zu finden. Dazu wird dieOntologie in eine Vektorrepräsentation, wie in Abbildung 3.1 gezeigt, umgewandelt.Die Länge des Vektors entspricht der Gesamtanzahl der Knoten der Ontologie. JedeKomponente des Vektors entspricht einem Knoten. Dabei wird die erste Komponentedem Wurzelknoten zugeordnet, und danach folgen die Knoten, wie in der Abbildung,in der Reihenfolge von oben nach unten und von links nach rechts. Die Werte der Kom-ponenten eines Vektors legen fest, ob der entsprechende Knoten in der darzustellenden(Sub-)Ontologie enthalten ist oder nicht. Ähnlich zu den Dokumentenvektoren bedeuteteine 1, dass der Knoten in dem darzustellenden Unterbaum enthalten ist, und eine 0,dass der Knoten nicht enthalten ist. Würde z.B. eine Suchanfrage q auf obige Ontologie

3.3 Ermittlung der Experten 24

Abbildung 3.1: Repräsentation einer Beispiel-Ontologie mit 10 Knoten als Vektor

abgebildet den Unterbaum mit den Knoten 1, 5 und 7 ergeben, würde das dem Vektorv(q) = [1, 0, 0, 0, 1, 0, 1, 0, 0, 0] entsprechen. Die Darstellung der Experten als Vektorenist ähnlich. Gibt zum Beispiel ein Experte e an, er wäre Experte in den Knoten 8und 9, so wird ihm zunächst der Unterbaum mit den Knoten 8 und 9 zugeordnet,was der Vektorrepräsentation v(e) = [0, 0, 0, 0, 0, 0, 0, l1, l2, 0] entspricht. Die Werteli ∈ {1, ..., 5} entsprechen dabei dem Grad der Expertise des Nutzers in der jeweiligenKategorie. Der durch diese Vektoren aufgespannte Vektorraum S(O) ⊂ RN wird imfolgenden als Ontologieraum bezeichnet.

Um nun zu einer Suchanfrage q aus einer gegebenen Menge von ExpertenX = {e1, ..., eE} die geeignetesten zur Beantwortung der Frage herauszufinden,wird zunächst q nach dem oben beschriebenen Algorithmus in einen Unterbaum derOntologie umgewandelt und danach als Vektor v(q) repräsentiert. Die Experten könnenaufgrund ihres im Profil gespeicherten Unterbaums direkt in die Vektorrepräsentationv(e1), ..., v(eE) überführt werden. Das Matching zwischen der Suchanfrage und denExperten wird über das Skalarprodukt in S(O) realisiert:

m(q, ei) = v(q) · v(ei), i ∈ {1, ..., E} (3.3)

Die Experten mit den höchsten Matching-Werten werden als die am geeignetesten Be-nutzer eingestuft, die gegebene Suchanfrage zu beantworten.

Kapitel 4

Problemanalyse

Die grundsätzliche Aufgabe eines Expertensuchsystems besteht darin, von Nutzerngestellte Fragen den „richtigen“ Experten zuzuordnen. Wobei „richtig“ bedeutet, dassdie ermittelten Experten eine gewisse Expertise auf dem Gebiet haben müssen, aus demdie Frage stammt, um so dem Hilfe suchenden Nutzer bei seinem Problem helfen zukönnen. Es wird also eine Abbildung einer Anfrage q auf eine Menge von Experten Egesucht. Der intuitivste Ansatz wäre, die Frage direkt auf die Experten abzubilden (zumatchen). Dazu müsste man die Experten durch eine Menge von Termen repräsentieren,die ihr Wissen wiederspiegeln, um so das Problem in ein Textklassifikations-Problemzu überführen: Die Experten wären dann die zu ermittelnden Klassen, während dieAnfrage den zu klassifizierenden Text repräsentieren würde. Der Vorteil dieses Ansatzeswäre, dass man auf viele bekannte und bewährte Klassifikationsalgorithmen zurück-greifen könnte. Ein Nachteil wäre, die Schwierigkeit die Menge von Termen, die einenExperten beschreiben, zu bilden. Die Experten müssten diese selber spezifizieren, d.h.sie geben entweder manuell Schlüsselwörter an, die sie selbst als aussagekräftig genugeinschätzen, oder sie geben eine Menge von Dokumenten oder Webseiten an, die ausihrer Wissensdomäne stammen. Beispielsweise könnte ein Nutzer, der sein Wissen überdie Programmiersprache JAVA zum Ausdruck bringen möchte, den entsprechendenEintrag aus der Online-Enzyklopädie Wikipedia1 angeben oder die JAVA Homepage2

an sich. In beiden Fällen müsste der Benutzer selbst einschätzen können, welche undwieviele Schlüsselworte oder Dokumente er angeben muss, damit eine Klassifikationerst möglich ist. Auch wenn man den Benutzer durch Richtlinien auf die richtige Mengean Schlüsselwörtern hinweisen könnte, wäre das aus Sicht der Benutzerfreundlichkeitkeine wünschenswerte Lösung.

1http://de.wikipedia.org/wiki/Java_(Programmiersprache)2http://java.sun.com/

25

26

Ein weiteres Problem wäre die Matching-Qualität: Es wurde eine Auswertung desAnsatzes durchgeführt, bei dem die Entwicklung der Matching-Qualität in Abhängig-keit von der Anzahl der Experten untersucht werden sollte. Dabei wurden mit Hilfeeines Naive Bayes Klassifizierers die Experten zu einer Suchanfrage ermittelt, derenÄhnlichkeitswert zwischen der Frage und ihrer eigenen Schlüsselwortmenge unter denbesten 5 lag. D.h. betrug der fünft beste Ähnlichkeitswert über allen Experten 0.6, sowurden alle Experten die mind. diesen Wert erreicht hatten als geeignet betrachtet.Man beachte, dass so mehr als 5 Experten in die Ergebnismenge aufgenommenwerden können, wenn zum Beispiel der sechst- und siebt-beste Experte den gleichenÄhnlichkeitswert aufweisen wie der fünft-beste. Durch den Vergleich zwischen dengematchten mit den von vornherein bekannten, tatsächlich zu der Suchanfrage passen-den Experten, wurden so Precision und Recall berechnet. Wie Abbildung 4.1 zeigt,werden gute Precision-Werte erreicht. Jedoch nimmt der Recall mit steigender Anzahlder Experten so stark ab, dass schon bei 500 Experten der Wert kleiner als 1% ist.Dieser starke Abfall ist darauf zurückzuführen, dass zwar die besten Experten nachden besten 5 Ähnlichkeitswerten ausgesucht werden, jedoch sind die Ähnlichkeitswertekontinuierlich, so dass die Wahrscheinlichkeit recht gering ist, dass 2 Experten dengleichen Ähnlichkeitswert aufweisen. Die Folge daraus ist, dass meist lediglich 5Experten (oder höchstens 2-3 mehr) in der Ergebnismenge enthalten sind.Das ausschlaggebendste Argument gegen diesen Ansatz ist aber, dass der Aufwand desAnfrage-Matchings mit der Anzahl der Experten skaliert, da die Suchanfrage mit jedemeinzelnen Experten abgeglichen werden müsste. Sei E die Menge der Experten undTE die Menge der Terme, die einen Experten charakterisieren. Ohne Beschränkung derAllgemeinheit wird angenommen, dass die Suchanfrage aus einem Term besteht und|TE| für alle Experten gleich gross ist. Dann ist der Aufwand für das direkte Matcheneiner Suchanfrage O(Dir) = |E| · |TE|. Der Aufwand wird anhand der Anzahl derbenötigten Vergleiche abgeschätzt.

Im Bereich der Textklassifikation werden in der Praxis [30, 31, 32, 33, 34, 35]häufig Ontologien genutzt, um Kategorien zu repräsentieren. Um die oben beschriebe-nen Probleme zu umgehen, wurde in SPREE, wie in Kapitel 3 beschrieben, ein Ansatzgewählt, bei dem die Suchanfragen und die Experten zunächst auf eine vorher definierteOntologie abgebildet wurden. Die geeignetsten Experten wurden daraufhin durch einenVergleich der so erhaltenen Repräsentationen ermittelt. Bei diesem Ansatz müssen dieNutzer des Systems keine Schlüsselwörter angeben, sondern lediglich aus der Ontolo-gie die für sie zutreffenden Kategorien aussuchen. Die Mengen von Termen, die die

27

einzelnen Kategorien repräsentieren und auf deren Grundlage die Klassifikation späterausgeführt wird, können offline gesammelt, vorbereitet (zum Beispiel s. Abschnitt2.1.3.2) und auf ihre Klassifikationsqualität hin im Vorfeld getestet werden.Hinsichtlich der Matching-Qualität hat der Ontologie-basierte Ansatz den Vorteil, dassdie durch Formel 3.3 berechneten Ähnlichkeitswerte zwischen den Unterbäumen derSuchanfragen und Experten natürliche Zahlen sind. Dies hat zur Folge, dass es in derErgebnismenge mit den 5 besten Ähnlichkeitswerten mehr Experten gibt als im erstenAnsatz. Abbildung 4.1 zeigt, dass sich dadurch die Vollständigkeit der Ergebnismenge(was dem Recall entspricht) deutlich verbessert: Durch das Ontologie-basierte Mat-ching wird zwar mit steigender Anzahl der Experten ein um ca. 10% schlechtererPrecision-Wert erreicht, jedoch stehen dem ein um ca. 75% besserer Recall-Wertgegenüber.

Abbildung 4.1: Vergleich zwischen direktem Matching und Ontologie-basiertem Mat-ching auf einer Testontologie mit 103 Knoten

Ein weiterer Vorteil dieses Ansatzes ist, dass die Anzahl der Experten nicht mehr soeinen starken Einfluss auf die Performanz des Matchings hat: Der Aufwand für das

28

Matching setzt sich aus zwei Teilen zusammen. Als erstes wird die Suchanfrage mitallen Knoten verglichen. Dieser Vorgang ist unabhängig von den Experten und bleibtsomit bei steigender Anzahl der Experten konstant, sofern die Menge der KategorienC konstant bleibt. Unter den Annahmen, die für die Berechnung von O(Dir) gemachtwurden, entspricht das dem Aufwand O(Ont)1 = |C| · |TC |, wobei TC die Anzahl derTerme in einem Knoten bezeichnet. Als zweites wird der so resultierende Unterbaummit den Profilen der Experten verglichen. Sei C ′ die Menge an Knoten des ausSchritt 1 resultierenden Unterbaumes und α die Anzahl der Kategorien, in denen einNutzer Experte ist. Somit ergibt sich dafür der Aufwand O(Ont)2 = |C ′| · α|E|. AlsGesamtaufwand für das Matching ergibt sich so

O(Ont) = O(Ont)1 +O(Ont)2 = |C| · |TC |+ |C ′| · α|E|

Im Folgenden soll nun gezeigt werden, dass der Aufwand für das Ontologie-basierteMatching mit steigender Anzahl der Experten geringer ist als das direkte Matching.Angenommen O(Dir) > O(Ont). Daraus folgt O(Dir)−O(Ont) > 0, also

|E| · |TE| − |C| · |TC | − |C ′| · α|E| > 0 (4.1)

TE ist die Menge an Termen, die nötig sind, um die Kategorien, in denen ein NutzerExperte ist, zu beschreiben. Da ein Nutzer in α Kategorien Experte ist und für die Cha-rakterisierung einer Kategorie |TC | Terme nötig sind, gilt TE = α|TC |. Eingesetzt in 4.1ergibt sich dadurch

α|E| · |TC | − |C| · |TC | − |C ′| · α|E| > 0 (4.2)

(α|E| − |C|) · |TC | > |C ′| · α|E| (4.3)

α|E| − |C| > |C′| · α|E||TC |

(4.4)

α− |C||E|

>α|C ′||TC |

(4.5)

Für |E| ≥ |C| gilt: (4.6)

α− 1 >α|C ′||TC |

(4.7)

1− 1

α>|C ′||TC |

(4.8)

(4.9)

29

1 >|C ′||TC |

(4.10)

|TC | > |C ′| (4.11)

Daraus folgt, dass die Annahme O(Dir) > O(Ont) unter zwei Bedingungen zutrifft:Es muss |TC | > |C ′| gelten, was für SPREE zutrifft, da hier |TC | > 1000 und C ′ < 100

ist. Weiterhin muss |E| ≥ |C| gelten, was für eine wachsende Anzahl an Expertenzutrifft. Abbildung 4.2 zeigt, dass sobald die Anzahl der Experten die Knotenanzahlübersteigt, der Ontologie-basierte Ansatz dem direkten Matching hinsichtlich derBerechnungszeit überlegen ist.

Abbildung 4.2: Vergleich der benötigten Berechnungszeit (in Sekunden) für das Mat-chen einer Suchanfrage mittels direktem Matching und Ontologie-basiertem Matchingauf einer Testontologie mit 103 Knoten

Offensichtlich ist der ontologiebasierte Ansatz dem direkten Matching vorzuzie-hen. Wird nun eine Ontologie für das Experten-Matching genutzt, stellt sich die Frage,wie solch eine Ontologie im Idealfall aussehen sollte, bzw. welche Anforderungensich an die Ontologie ergeben. Da SPREE ein offenes System ist und nicht auf einebestimmte Zielgruppe zugeschnitten ist, sollte die Ontologie ein möglichst breitesSpektrum an Themengebieten abdecken. Um aber eine möglichst exakte, nicht zuallgemeine Kategorisierung der Fragen zu ermöglichen, müsste der Baum auchhinreichend tief sein, d.h. die Kategorien müssten sehr feingliedrig sein. Würdenbeispielsweise zehn Nutzer in zehn unterschiedlichen Programmiersprachen Expertensein und zehn weitere Nutzer in zehn unterschiedlichen Programmierumgebungen,

30

würde eine Anfrage zum Thema C++, die auf den Knoten Programmierung matcht,alle 20 Experten zurückliefern, wenn keine Unterknoten vorhanden wären, die dieKategorie weiter untergliedern würden.Eine solche sehr breite und tiefe Ontologie enthält im Allgemeinen hunderttausendevon Knoten, die aber nicht vollständig durch Experten abgedeckt werden, d.h. es sindviele redundante Kategorien vorhanden. Würden lediglich die Kategorie-Namen in derDatenbank gespeichert werden, würde dieses kein allzu grosses Problem darstellen.Da aber in SPREE jede Kategorie über eine Menge von Schlüsselwörtern verfügtund diese Schlüsselwörter von den Blättern bis zu der ersten Ebene des Baumeshinaufpropagiert werden, um so die Ober-/Unterkategorie-Relation zu realisieren (s.Kapitel 3), wird deutlich mehr Speicher in Anspruch genommen. Zusätzlich dazumüssten die Schlüsselwörter für alle Knoten, auch diejenigen, die möglicherweise nieim System genutzt werden, im Vorfeld gesammelt und vorbereitet werden, was zu einerenormen Zeitverzögerung bei der Erstellung der Ontologie führen würde, da die für dieErmittlung der Terme genutzte Suchmaschine die Anzahl der Suchanfragen auf 5000pro Tag beschränkt.Ein weiterer Nachteil dieser redundanten Datenhaltung wäre ein starker Performanz-verlust beim Matching-Prozess: Aufgrund des Vorhandenseins der redundanten Knotennimmt nicht nur die Anzahl der Terme und damit auch die Anzahl der Dimensionendes Termraums zu, sondern auch die Anzahl der Vergleiche. Sind zum Beispiel inder Kategorie Biologie keine Experten registriert, dieser Knoten aber noch 10 Ebenentief verzweigt, würde der Matching-Algorithmus bei einer Suchanfrage, die in diesenBereich fällt evtl. alle Ebenen unnötigerweise durchlaufen.Um den Nutzern von SPREE eine akzeptable Antwortzeit bei der Expertensuche zugarantieren, wurde aus der vollständigen ODP-Ontologie3 mit über 500000 Knoteneine Subontologie mit ca. 1000 Knoten semi-automatisch extrahiert. Dabei wurden nurdie ersten 2-3 Ebenen der ursprünglichen Ontologie übernommen und die darunterlie-genden Knoten verworfen. Eine solche Lösung führt zwar zu einer guten Performanz,jedoch sind so die Kategorien nicht genau genug untergliedert, was dazu führt, dassbei einer Expertenkonzentration in einem Blatt alle Experten zurückgeliefert werden,obwohl nur ein Bruchteil davon für die Frage zuständig ist, wie obiges Beispiel mit den20 Experten verdeutlicht. Eine weitere Möglichkeit, eine performante Subontologie zugewinnen, wäre nur die oberste Ebene zu behalten und zusätzlich 1 oder 2 Kategorien zuidentifizieren, die wesentlich feingliedriger strukturiert werden. Eine solche sogenannteDomänenontologie ist aber nur in einer Umgebung einsatzfähig, in der die Interessen

3Open Directory Project - http://www.dmoz.org/

31

der Nutzer und deren gestellte Fragen, und damit auch die benötigten Kategorien,leicht vorhersehbar sind, zum Beispiel in einem Unternehmen, in dem das System zumbrancheninternen Wissensaustausch genutzt wird. Da SPREE aber eine frei zugänglicheonline Gemeinschaft darstellt, ist das keine geeignete Lösungsmöglichkeit.

Zusammengefasst kann man sagen, dass sowohl eine grosse Ontologie, die mög-lichst viele Kategorien abdeckt, als auch eine (in der Breite oder in der Tiefe) gekürzteOntologie zu viele Nachteile haben, als dass man sie in einem Expertensuchsystemproduktiv einsetzen könnte. Allgemeiner noch kann man sagen, dass eine statischeOntologie nicht für diese Aufgabe geeignet ist, da sich die Expertenverteilung unddie „Nutzung“ der Knoten durch die gestellten Fragen über die Zeit schnell ändernkann, was dazu führt, dass sich die Anforderungen an die Granularität der jeweiligenKategorien ändert.

Kapitel 5

Lösungskonzept

Die Diskussion in Kapitel 4 hat gezeigt, dass nicht nur eine grosse Themenabdeckungdurch die Ontologie erwünscht ist, sondern auch eine hinreichende Tiefe und Feinglie-derung der einzelnen Kategorien. Allerdings sind beide Eigenschaften nicht so in einerstatischen Ontologie vereinbar, als dass man sie in einem Produktivsystem einsetzenkönnte. In diesem Abschnitt soll dieses Problem durch eine dynamische Ontologiegelöst werden, die beide Eigenschaften innehat, eine akzeptable Grösse aufweist unddie Qualität des Expertenmatchings nicht spürbar verschlechtert. Zunächst wird dasgrundsätzliche Vorgehen zur Erstellung der dynamischen Ontologie beschrieben. Einedetailliertere Beschreibung der dazu notwendigen Teilschritte erfolgt danach.Als Basis dafür soll eine grosse Ontologie mit einer breiten Themenabdeckung undeiner tiefen, feingliedrigen Kategoriestruktur, im Folgenden als vollständige Ontologie

bezeichnet, im Hintergrund gehalten werden. Diese Ontologie wird von SPREEnicht direkt benutzt, sondern stellt lediglich die Kategoriestruktur zum Zwecke derExtraktion einer wesentlich kleineren Subontologie zur Verfügung. Diese Subontologiesoll nur Knoten enthalten, die aktuell vom System benötigt werden. Die so extrahierteArbeitsontologie wird dann in SPREE genutzt, um den von Nutzern gestellten FragenExperten zuzuordnen.Es stellt sich nun die Frage, welche Knoten tatsächlich extrahiert werden sollen,also welche Knoten von SPREE tatsächlich benötigt werden? Als erstes sind das dieKategorien, in denen Experten registriert sind. Kategorien, in denen kein BenutzerExperte ist, sind redundant, da eine Frage in einer solchen Kategorie von niemandembeantwortet werden kann. Da aber mit der Dauer des Einsatzes des Systems auchdie Nutzerzahlen und damit auch die Anzahl der „besetzten“ Knoten wachsen, sollenzusätzlich auch die in dem System behandelten Themengebiete untersucht werden. D.h.es soll analysiert werden welche Themengebiete durch die Fragen abgedeckt werden

32

33

und Knoten, die nicht oder kaum benutzt werden, sollen verworfen werden. Es wirdalso davon ausgegangen, dass die Nutzer im System sich, zumindest innerhalb einesgewissen, kurzen Zeitraums, schwerpunktmässig über eine gleichbleibende Mengean Themen unterhalten. Ausreisser, also Fragen, die zu Kategorien ausserhalb dieserMenge gehören, wirken sich natürlich negativ auf das Expertenmatching aus, da dieseKnoten nicht in der Arbeitsontologie sind und damit auch keine Information darüberwelche Experten dafür zuständig sind. Allerdings fällt dieses kaum ins Gewicht, da zuder überwiegenden Anzahl der Fragen weiterhin die richtigen Experten zurückgeliefertwerden. Da diese so gefundene Menge an Themen natürlich nicht über einen längerenZeitraum gleich bleiben wird, insbesondere nicht, wenn sich neue Benutzer anmelden,die an anderen Themen interessiert sind, wird dieser Prozess der Analyse der Experten-und Anfragenstruktur und der daraus resultierende Aufbau der Arbeitsontologie inperiodischen Abständen wiederholt werden. Auf diese Weise entsteht eine dynamischeOntologie, die stets an die dem System zugrundeliegende Daten angepasst ist. Werdendabei nur neuere Anfragen berücksichtigt, also beispielsweise nur solche, die innerhalbder vergangenen 1-2 Monaten gestellt wurden, wird so insbesondere eine Verschiebungder Themen, an denen die Nutzer interessiert sind, berücksichtigt. D.h. ältere Themen-gebiete, zu denen keine Fragen mehr gestellt werden, werden so auch gefiltert.Da dieser Prozess vollautomatisch geschieht, bietet es sich an die Arbeitsontologie überNacht zu aktualisieren, so wird auch ein Höchstmaß an Aktualität erreicht und eineMinimierung des Fehlers beim Expertenmatching durch Ausreisser.

Eine solche Reduktion ist erst dann richtig effektiv, wenn die Anfragen nichtgleichverteilt sind, sondern eine gewisse Konzentration auf manche Themengebieteaufweisen. Bei einer ungünstigen Verteilung der Anfragen auf die Kategorien kannes passieren, dass die meisten Knoten, in denen Experten registriert sind, in derArbeitsontologie enthalten sind. Im schlimmsten Falle sind dies genau die Knoten, indenen auch Experten registriert sind, d.h. es konnten keine Knoten entfernt werden.Um dennoch auch bei einer hohen Anzahl an Experten eine gewisse Performanz zugewährleisten, wird versucht durch Feature Selection die Menge an Termen, die dieKategorien repräsentieren, zu minimieren, so dass beim Matching weniger Termemiteinander verglichen werden müssen.

Der eben vorgestellte Lösungsansatz besteht also im wesentlichen aus drei Schritten:Aufbau der vollständigen Ontologie, Extraktion der Arbeitsontologie und FeatureSelection. Die Extraktion der Arbeitsontologie lässt sich noch in Experten- und

5.1 Aufbau der vollständigen Ontologie 34

Anfrage-basierte Knotenreduktion unterteilen. Anhand von Abbildung 5.1 soll diezeitliche Abfolge der einzelnen Schritte erläutert werden. In den weiteren Abschnittendieses Kapitels werden die Schritte dann im Detail beschrieben. Als erstes wirddie vollständige Ontologie aus einer gegebenen Taxonomie aufgebaut (s. Abschnitt5.1), aus der dann mit Hilfe der aus SPREE stammenden Expertenprofile eine ersteSubontologie erzeugt wird. Die Experten-basierte Knotenreduktion erfolgt vor derAnfrage-basierten, da, wie sich später noch zeigen wird, letztere wesentlich rechen-intensiver ist, insbesondere wenn die Anzahl der Ausgangsknoten sehr hoch ist. Fürdie Anfrage-basierte Reduktion müssen die Anfragen aus SPREE mit den Knotender Subontologie verglichen werden, um die Häufigkeit der Anfragen pro Kategoriezu ermitteln. Die Anfragen wurden zwar schon in SPREE klassifiziert, allerdingswurde dazu der in Kapitel 3 genutzte Algorithmus benutzt. Für die Evaluierung desErgebnisses der Knotenreduktion wird jedoch der Naive Bayes Klassifikator benutzt(eine Begründung dafür wird in Kapitel 7 geliefert). Um die Evaluierung nicht zuverfälschen, ist eine Re-Klassifikation der Anfragen mit Naive Bayes nötig, bevor siezur Anfrage-basierten Knotenreduktion genutzt werden. Bevor die Re-Klassifikationerfolgen kann, muss zunächst die Feature Selection durchgeführt werden, welche deneinzelnen Knoten die zugehörigen Schlüsselworte zuordnet. Mit diesen Informationenkann nun im letzten Schritt die Arbeitsontologie aus der vorhandenen Subontologieextrahiert werden, welche nach SPREE zur weiteren Nutzung exportiert werden kann.

5.1 Aufbau der vollständigen Ontologie

Als erstes muss die vollständige Ontologie aufgebaut werden, wobei „aufbauen“ bedeu-tet, dass die Ontologie aus einem proprietären Format in ein geeignetes Format umge-wandelt und in der Datenbank abgelegt werden muss, um eine effiziente Extraktion derArbeitsontologie zu ermöglichen. Es soll die ODP-Ontologie genutzt werden, welcheim XML Format auf http://dmoz.org frei verfügbar ist. Als Webseitenverzeichnis decktsie ein sehr breites Spektrum an Themen ab und bietet gleichzeitig eine genügende Tie-fe (bis zu 12 Ebenen) für jeden Bereich. Insgesamt enthält sie über 500000 Knoten,allerdings wird in SPREE nur die englische Sprache unterstützt, daher können, nebenanderen, nicht für SPREE geeigneten Knoten, die sprachspezifischen Kategorien vonvornherein ausgeschlossen werden, so dass gut 400000 Kategorien übrigbleiben.Ein weiterer Vorteil der Ontologie ist, dass neben der gegebenen Kategoriestruktur auchzu jeder Kategorie eine Menge von URLs enthalten ist. Diese URLs verweisen auf Web-seiten, die von Hand aufgrund ihres Inhaltes den entsprechenden Kategorien zugeordnet


Abbildung 5.1: System-Überblick: Die Ergebnisse der Schritte 2 bis 4 werden alle indie gleiche Datenbank geschrieben. Um den Informationsfluss zu verdeutlichen werdendafür in der Abbildung 3 verschiedene Datenbanken abgebildet.

5.2 Extraktion der Arbeitsontologie 36

wurden. Damit ist eine Menge von Dokumenten gegeben, die sich zum Testen des Klas-sifikators nutzen lässt (s. Abschnitt 2.1.4). Ein Extrahieren und Speichern der Inhalteaus den gegebenen Webseiten soll allerdings noch nicht in diesem Schritt durchgeführtwerden, da dieses für über 400000 Knoten durchgeführt werden müsste, was zu den inKapitel 4 angesprochenen Problemen führen würde. In der Datenbank soll demnach nurdie Struktur des Kategorie-Baumes und die Zuordnung der URLs der Testdokumente zuden einzelnen Kategorien festgehalten werden.

5.2 Extraktion der Arbeitsontologie

Als zweiter Schritt soll aus der vollständigen Ontologie eine Arbeitsontologie mit mög-lichst wenig Knoten extrahiert werden, die sich für das Experten-Matching nutzen lässt.Das Problem der Identifikation der zu extrahierenden Knoten soll in 5.2.1 und 5.2.3 be-sprochen werden. Im Abschnitt 5.2.2 wird aufgezeigt, wie die Anzahl der Terme inner-halb der Kategorien möglichst gering gehalten wird, ohne dabei die Matching-Qualitätzu verschlechtern. Obwohl die Feature Selection keine Form der Knoten-Extraktion dar-stellt, wird sie dennoch in diesem Abschnitt beschrieben, da für die Anfrage-basierteReduktion die extrahierten Terme benötigt werden.

5.2.1 Experten-basierte Knotenreduktion

Als erstes sollen zur Identifikation der relevanten Knoten die Verteilung der Experten aufdie Knoten herangezogen werden. Dabei sollen, wie bereits oben angesprochen, nur dieKnoten aus der vollständigen Ontologie extrahiert werden, in denen mindestens ein Ex-perte registriert ist. Die so extrahierten Knoten bilden aber nicht zwingend einen Baum,daher werden die Elternknoten bis hin zum Wurzelknoten mit übernommen, so dass dieresultierende Knotenmenge einen Unterbaum der vollständigen Ontologie darstellt. Die-ses Vorgehen wird durch die Tatsache ermöglicht, dass ein Experte in einer Kategoriestets auch Experte in der übergeordneten Kategorie ist. Ein Spezialist in Programmie-

rung ist beispielsweise auch zu einem gewissen Grad Spezialist in der OberkategorieComputer.Damit sich die Arbeitsontologie automatisch an die aktuelle Expertenverteilung anpasst,werden zunächst in dem extrahierten Unterbaum die Blätter identifiziert, in denen dieAnzahl der Experten einen gewissen Schwellwert kE überschreiten. Zu diesen Blätternwerden die Kindknoten ebenfalls hinzugefügt. Auf diese Weise wird verhindert, dass zuviele Experten in einem Knoten vorhanden sind, was zu einem ungenauen Expertenmat-


ching führen würde (s. Kapitel 4). Das Hinzufügen der Kindknoten sollte erst nach derAnfrage-basierten Reduktion (Abschnitt 5.2.3) erfolgen, da die Kindknoten möglicher-weise noch über keine Anfragen verfügen und somit entfernt werden würden.Der Schwellwert kE legt somit die maximale Anzahl an Experten in den Blättern desresultierenden Baumes fest (außer es gibt keine weiteren Kindknoten mehr in der voll-ständigen Ontologie, dann kann dieser Wert überschritten werden). SPREE liefert aufeine Anfrage die 5 besten Experten zurück. Wird kE > 5 gewählt, so führt dieses zu ei-nem zu allgemeinen Expertenmatching und es kann vorkommen, dass unter den zurück-gelieferten Experten auch solche sind, die nicht zu der Anfrage passen. Kleine Werte fürkE würden zu häufigem Hinzufügen von Kindknoten führen. Da bei jedem Hinzufügenvon Kindknoten die Experten ihr Profil überarbeiten müssen, um aus den Kindknotenden zu ihnen passenden zu bestimmen, soll als Kompromiss kE = 5 gewählt werden.Würden Kategorien der ersten Ebene entfernt werden, in denen keine Experten regis-triert sind, könnte dies zur Folge haben, dass Anfragen, die in diese Kategorien fallenwürden, falsch kategorisiert werden: Die Kategorien der ersten Ebene enthalten alle Ter-me der Unterknoten, d.h. die Wahrscheinlichkeit ist gross, dass sich ihre Termmengenüberschneiden. Fehlt nun ein Knoten der ersten Ebene, könnte, durch das Überschnei-den der Termmengen, bei einer Anfrage ein Nachbarknoten oder ein Kind eines Nach-barknotens durch den Klassifikator ausgewählt werden, obwohl die Anfrage zu demfehlenden Knoten gehört. Aus diesem Grunde werden die Kategorien der ersten Ebeneebenfalls hinzugefügt. Ein weiterer Grund für die Notwendigkeit dieser Knoten ist, dassnach der hier vorgestellten Heuristik nur Knoten hinzugefügt werden, die mindestenseinen Experten enthalten, oder in deren Elternknoten mindestens 5 Experten registriertsind. Die Knoten der ersten Ebene haben aber keine Elternknoten und sollten sie in derersten Version der Arbeitsontologie nicht enthalten sein, können auch keine Expertensich in diesen Gebieten auszeichnen, d.h. die Kriterien zur Aufnahme in die Arbeitson-tologie könnten nie erfüllt werden. Da auch diese Knoten durch die Anfrage-basierteReduktion entfernt werden könnten, sollten sie erst danach hinzugefügt werden.

5.2.2 Feature Selection

In diesem Schritt soll nicht nur die in Abschnitt 2.1.3.2 vorgestellte Feature Selectiondurchgeführt werden, sondern auch der gesamte Vorgang der Ermittlung der Termmen-gen, welche dann durch die Feature Selection analysiert werden. Nach dem im letztenAbschnitt vorgestellten Schritt, liegen die relevanten Knoten hinsichtlich der Experten-struktur und die zugehörigen URLs der Test-Dokumente vor. Um Anfragen klassifizie-


ren zu können, muss jede Kategorie mit einer Menge von thematisch zugehörigen Ter-men verknüpft werden (sogenannte Trainigsmenge). Zu diesem Zweck werden zunächstdie Dokumente, wie in Abschnitt 3.1 beschrieben, geladen und deren Inhalt sowohl indie Arbeitsontologie geschrieben, als auch in die vollständige Ontologie. Das Speichernder Dokumente in der vollständigen Ontologie hat den Vorteil, dass sie beim nächstenUpdate der Arbeitsontologie nicht mehr neu geladen werden müssen. Würden die Do-kumente bei jedem Update neu geladen werden müssen, hätte dieses den Vorteil, dassman jedesmal die aktuellsten Dokumente zu einer Kategorie erhalten würde. Es wirdaber angenommen, dass die geladenen Dokumente nicht so schnell an Aktualität verlie-ren (ein Update der Arbeitsontologie findet 1 mal am Tag statt). Nach einem längerenZeitraum könnten die Dokumente verworfen und durch aktuellere ersetzt werden, diesessoll aber nicht in dieser Implementation berücksichtigt werden.Die Terme der so extrahierten Dokumente werden zunächst durch den Porter-Stemmerauf ihren Stamm zurückgeführt und die Stoppwörter mit Hilfe einer Stoppwort-Listeentfernt. Untersuchungen haben gezeigt, dass Wörter mit einer geringen Termfrequenz,gemessen über die gesamte Dokumentenmenge, kaum oder gar keine diskriminerendeWirkung in der Textklassifikation haben ([12, 36]), d.h. sie tragen nicht dazu bei, Klas-sen voneinander abzugrenzen. Es wird angenommen, dass es sich bei solchen Termenum Rechtschreibfehler oder andere obskure Wortkonstruktionen handelt, die keinen In-halt transportieren. Aus diesem Grunde werden alle Terme mit einer Termfrequenz klei-ner als 4 entfernt.Als nächstes soll eine Feature Selection mittels der Odds Ratio-Heuristik durchge-führt werden. Dazu wird für jeden Term ti der Klasse ci die Odds Ratio OR(t, ci) =P (t|ci)·(1−P (t|ci))(1−P (t|ci))·P (t|ci) berechnet. Damit in manchen Kategorien nicht zu viele oder zu wenigeTerme entfernt werden, werden in jedem Knoten die kf besten Terme behalten, wobeidas die Terme mit den höchsten Odds Ratio Werten sind. Die Ermittlung eines geeigne-ten Wertes für kf findet in Kapitel 7 statt.

5.2.3 Anfrage-basierte Knotenreduktion

Wie schon zu Beginn des Kapitels erwähnt, soll nach der Experten-basierten Reduktioneine weitere Knotenreduktion erfolgen, die auf der Analyse der Verteilung der imSystem gespeicherten Anfragen über den Kategorien basiert. Dabei sollen Kategorien,in denen keine oder nur wenige Anfragen erfolgten, entfernt werden. Das Ziel ist soviele Knoten wie möglich zu entfernen, wobei die Qualität des Matchings möglichsthoch bleiben soll.


Um die häufig angefragten Kategorien zu bestimmen, sollen im folgenden zwei Ansätzevorgestellt werden, die später in dieser Arbeit, in Kapitel 7, miteinander verglichenwerden sollen. Ein intuitiver Ansatz wäre, die Wahrscheinlichkeit der Klassifizierungeiner Anfrage in einer Kategorie zu berücksichtigen, wobei von einer statistischenUnabhängigkeit zwischen den Kategorien ausgegangen wird1. Auch wenn die Annah-me der Unabhängigkeit zwischen den Kategorien in einer hierarchisch gegliedertenKategoriestruktur nicht zutreffend ist, wird dieser intuitive Ansatz dennoch umgesetzt,um eine Beurteilung des zweiten, fortgeschritteneren Ansatzes zu ermöglichen.Formal ausgedrückt funktioniert die Bestimmung der wichtigsten Knoten dabei folgen-dermaßen: Sei Ai das Ereignis, dass der Klassifikator eine Anfrage in einen Knotenci kategorisiert und P (Ai) die Wahrscheinlichkeit des Auftretens dieses Ereignisses.Nach der Berechnung von P (Ai) für alle Knoten ci, werden die kC wahrscheinlichstenKnoten behalten und die restlichen verworfen.

In Kapitel 2 wurde erläutert, wie in LSA mittels SVD die zugrundeliegenden Be-ziehungen zwischen Termen und Dokumenten aufgedeckt wurden. Dabei führte dieKorrelation der Termverteilungen zu einer veränderten Gewichtung in den Dokumen-ten. Dadurch erhöhte sich die Relevanz von manchen Termen für Dokumente, in denensie nicht direkt vorkamen. Analog dazu wird im zweiten Ansatz SVD benutzt, um dielatente semantische Struktur in der Beziehung zwischen der Verteilung der Fragenauf die Knoten und den Knoten selbst zu analysieren. Als Grundlage dazu dient eineMatrix A ∈ {0, 1}|Q|×|C|, in der die Zeilen Fragen repräsentieren und die Spalten dieKategorien. Q = {q1, ..., qm} bezeichnet die Menge aller zu untersuchenden Fragenund C = {c1, ..., cn} die Menge aller Knoten. Ein Eintrag aij = 1 in Zeile i und Spaltej von A bedeutet, dass die Anfrage qi in die Kategorie cj klassifiziert wurde, und einEintrag aij = 0, dass dies nicht der Fall ist. Die Matrix A wird nun durch SVD in dasProdukt dreier Matrizen zerlegt:

A = U · S · V T (5.1)

Ähnlich wie in LSA erfolgt nun eine Reduktion auf Rang r, was zu folgender Annähe-rung Ar an A führt:

Ar = Ur · Sr · V Tr (5.2)

Durch Berücksichtigung der Korrelation der Anfrageverteilungen auf die Knoten, wer-den diese Verteilungen durch die Rangreduktion neu gewichtet (s. Abschnitt 2.1.3.3).

1Dieser Ansatz wird in den folgenden Kapiteln als probabilistischer Ansatz bezeichnet


Um die relevantesten Knoten zu bestimmen, wird die durchschnittliche Neugewichtungφ(cj) einer Kategorie cj berechnet durch

φ(cj) =1

|Q|

|Q|∑i=1

aij (5.3)

wobei aij das Gewicht in der Zeile i und Spalte j aus der Matrix Ar bezeichnet. DiekC Knoten mit der höchsten durchschnittlichen Gewichtung sind die am häufigstenangefragten und werden behalten, die übrigen werden verworfen.

Geeignete Werte für kC und r sollen durch den Reduktionsprozess automatischgefunden werden. Dazu werden für verschiedene kC und r Tests ausgeführt, die inAbhängigkeit dieser Parameter die Qualität und Performanz des Expertenmatchingsmessen. Primäres Ziel ist die signifikante Steigerung der Performanz, ohne dabeian Qualität zu verlieren (im Vergleich zu der nicht-reduzierten Ontologie, also fürkC = |C|). Als Kriterium für die Auswahl der Parameter kann also nicht allein diePerformanz dienen, da die höchste Performanz mit minimaler Anzahl der Knotenerreicht wird, was aber eine Verschlechterung der Qualität zur Folge haben würde. AlsKriterium soll daher die Qualität herangezogen werden. Es sollen diejenigen Wertefür kc und r ausgewählt werden, mit denen die beste Qualität erreicht wird. Solltedie Qualität für alle kc < |C| schlechter sein als für kC = |C|, bedeutet dies, dassdie Ontologie nicht weiter reduziert werden kann. Als Kompromiss, um auch beischlechter werdender Qualität an Performanz zu gewinnen, könnte man eine geringeVerschlechterung der Qualität in Kauf nehmen. Der Reduktionsprozess wird jedoch 1mal pro Tag durchgeführt. Würde bei jeder Reduktion eine geringe Verschlechterungder Qualität in Kauf genommen werden, wäre die Folge ein zunehmender Abfall derMatching-Qualität über die Zeit.

Kapitel 6

Umsetzung

Die Implementation von SPREE erfolgte in der Programmiersprache Python1. Diesesbedingt jedoch nicht die Umsetzung des Lösungskonzeptes in der gleichen Sprache,da das Ergebnis des zu implementierenden Systems, die Arbeitsontologie, in einer Da-tenbank vorliegt, die in das SPREE eigene Format umgewandelt werden kann. Jedochwurden für SPREE schon Python-Skripte (im folgenden einfach Skripte) entwickelt,die wiederverwendet werden können, beispielsweise um die ODP-Ontologie, welche imXML-Format vorliegt, zu parsen. Ein weiterer Grund Python zu nutzen, ist, dass eine Er-weiterung Numeric Python (NumPy2) verfügbar ist, die den programmatischen Umgangmit Vektoren und Matrizen stark vereinfacht. NumPy bietet neben den einfachen Opera-tionen, wie Vektor-/Matrixmultiplikation und Berechnungen der Vektornorm, auch kom-plexe Funktionen an, wie zum Beispiel die Singulärwertzerlegung. Für die folgende Im-plementation wird Python in der Version 2.4.3 und NumPy in der Version 1.0.1 verwen-det. Eine weitere Erweiterung von Python, das Natural Language Toolkit3, findet in die-ser Implementation Verwendung, da sie eine Umsetzung des Porter Stemmers enthält.Zudem wird für die HTTP-Anfragen die Bibliothek httplib24 benötigt. Als Schnittstel-le zum Datenbanksystem wird SQLObject5 (Version 0.8.0b2) genutzt. SQLObject er-möglicht eine Abbildung der Datenbanktabellen auf Python-Objekte (Objekt-Relational

Mapper), so dass die wichtigsten Datenbankoperationen über Pythonkonstrukte ausge-führt werden können, was zu einer schnelleren Entwicklungszeit führt. Als Datenbank-system wurde MySQL6 5.0.27 genutzt.

1http://www.python.org2http://numpy.scipy.org3http://nltk.sourceforge.net/index.php/Main_Page4http://code.google.com/p/httplib2 - In der Implementation wurde Version 0.2.0 verwendet5http://www.sqlobject.org6http://www.mysql.de

41

6.1 Teilsysteme 42

Abbildung 6.1: Überblick über die Teilsysteme

6.1 Teilsysteme

An dieser Stelle soll ein grober Überblick über das System gegeben werden. Dabei wer-den die wichtigsten Teilsysteme und deren Funktion kurz beschrieben. Jedes Teilsystemwird durch ein Verzeichnis repräsentiert und definiert einen eigenen Namensraum. DieTeilsysteme fassen eine Menge von Python Skripten, sogenannten Modulen, logischzusammen. Die Module bilden selbst einen Namensraum und können beliebige Artenvon programmiersprachlichen Konstrukten enthalten, wie Klassen und Methoden oderauch nur Variablen. Der Wurzel-Namensraum, in dem alle Teilsysteme eingebettet sind,lautet nodereduction.

Das Teilsystem crawler

Die Module in diesem Teilsystem stellen Funktionalitäten zum Herunterladen vonWebseiten, sowie die Extraktion der Terme aus diesen, zur Verfügung. Zusätzlich ist indiesem Teilsystem auch die Logik für das Abfragen der passenden Dokumente zu einerKategorie über den Webdienst von Yahoo! implementiert.

Das Teilsystem db

Alle Module, deren vorwiegende Funktion das Auslesen bzw. das Schreiben in dieDatenbank ist, sind in diesem Teilsystem untergebracht. Insbesondere finden sich hierdie Module, die die Ontologien in dem in 6.2 beschriebenen Format in der Datenbank

6.1 Teilsysteme 43

speichern.

Das Teilsystem dynamictree

Hier werden alle Module zusammengefasst, die mit der dynamischen Ontologie imZusammenhang stehen. Dazu gehören eine Repräsentation der dynamischen Ontologieals Python-Klasse (dynOntologyTree), Module für den Aufbau der vollständigenOntologie (fulltree) und die Extraktion der Arbeitsontologie (shrinker).

Das Teilsystem extractor

In diesem Teilsystem befinden sich Skripte für die Extraktion der Terme aus Doku-menten und den zugehörigen Term-Preprocessing Schritten wie das Entfernen vonStoppwörtern und das Stemming.

Das Teilsystem ml

Der Naive Bayes Klassifikator und die Anfrage-basierte Knotenreduktion sind indiesem Teilsystem umgesetzt.

Das Teilsystem parser

Wie schon in Abschnitt 5.1 erwähnt, liegt die ODP-Ontologie im XML Format vor. DasParsen der Ontologie und die Umwandlung in eine Verzeichnisstruktur werden durchdie hier befindlichen Module realisiert. Die weitere Verarbeitung der Verzeichnisstruk-tur erfolgt über die db.loader-Module.

Das Teilsystem tests

Tests, die vorwiegend für die Evaluierung genutzt werden, befinden sich in diesemTeilsystem.

Das Teilsystem tree

Analog zu dynamictree.dyOntologyTree befindet sich hier eine Repräsentati-on einer statischen Ontologie als Python-Klasse.

Das Teilsystem utils

In diesem Teilsystem befinden sich Hilfsfunktionen, die sich in die oberen Teilsystemenicht einordnen lassen.

6.2 Datenmodell 44

6.2 Datenmodell

Das erste Problem, das sich bei dem Erstellen des Datenbankmodells ergibt, ist, dasssowohl die Arbeits- als auch die vollständige Ontologie (sowie weitere, zu Testzweckenbenötigte, Ontologien) die gleiche Tabellenstruktur aufweisen. Eine Möglichkeit wäreeine Tabellenstruktur für alle Ontologien zu erstellen und die einzelnen Ontologienüber eine eindeutigen Namen zu identifizieren. Dieses würde zu sehr grossen Tabellenführen, was langsamere Datenbankabfragen zur Folge hätte.Für den Modellentwurf wird daher für jede Ontologie eine eigene Tabelle erstellt, d.h.alle Tabellennamen werden um den zugehörigen Ontologienamen wie folgt erweitert:<Tabellenname>_<Ontologiename>. Dieses wird insbesondere durch SQLAlchemyerleichtert: Die benötigte Tabellenstruktur wird einmalig im Modul db.model

beschrieben. Für jede Ontologie werden durch die so gegebene Struktur zur Laufzeitdie Tabellen in der Datenbank erzeugt, falls sie nicht schon vorhanden sind.Eine Ontologie wird durch mehrere Tabellen repräsentiert, die für diese Arbeit relevan-ten sollen im folgenden beschrieben werden:

nodesIn dieser Tabelle wird die Struktur der Ontologie nach der Modified Preorder Tree

Traversal-Methode ([37]) festgehalten. Neben dem Knotennamen und der Positionim Baum, werden auch die zu dem Knoten gehörigen Terme mit den verschiedenenGewichtungen (Termfrequenz, tfidf) festgehalten.

termsFür die Berechnung der tfidf-Gewichte der Terme und für die Feature Selection müssenbestimmte statistische Werte über die Terme festgehalten werden. Dieses geschieht mitHilfe dieser Tabelle. Ausserdem wird die terms-Tabelle der Arbeitsontologie nachSPREE exportiert.

docsDie Trainingsdokumente und ihre Zuordnung zu den jeweiligen Knoten wird in derdocs-Tabelle festgehalten. Zu jedem Dokument wird die URL und die Termmenge mitden verschiedenen Gewichtungen gespeichert.

dmozAnalog zu den Trainingsdokumenten, werden in dieser Tabelle die Testdokumente mit


vergleichbaren Informationen festgehalten.

6.3 Aufbau der vollständigen Ontologie

Nachdem ein grober Überblick über das Gesamtsystem gegeben und das Datenmodellvorgestellt wurde, soll nun die Umsetzung der im Lösungsansatz identifizierten Einzel-schritte im Detail vorgestellt werden. Als erster Schritt muss die vollständige Ontologieaufgebaut werden, um später daraus die Arbeitsontologie extrahieren zu können. Dievollständige Ontologie ist, wie schon erwähnt, eine Subontologie der ODP-Ontologie,welche nur die für SPREE in Frage kommenden Kategorien enthält. Zum Zeitpunktder Implementation waren dieses gut 400000 Knoten. Die ODP-Ontologie kann unterhttp://rdf.dmoz.org/rdf/ heruntergeladen werden. Dabei werden nur die zwei Dateiencategories.txt und content.rdf.u8 gebraucht. categories.txt enthältlediglich die Kategorienamen und dient dazu, die für SPREE relevanten Kategorien zufiltern. content.rdf.u8.gz enthält die URLs der mit den einzelnen Kategorienassoziierten Webseiten.

Mit Hilfe dieser zwei Dateien kann der gesamte, in Abbildung 6.2 dargestellte Pro-zess durch das Aufrufen des Skriptes fulltree.py gestartet werden, welchessich in nodereduction.dynamictree befindet. Das Skript erwartet drei Kom-mandozeilenparameter, die für das Erstellen der Ontologie notwendig sind: Die ers-ten zwei Parameter entsprechen den Pfaden der Dateien categories.txt undcontent.rdf.u8 in der genannten Reihenfolge. Der dritte Parameter bestimmt denOntologienamen, welcher an die Datenbank-Tabellennamen angehängt wird.Beim Aufrufen des Skriptes wird die Funktion createOntology() auf-gerufen, welche die drei Parameter als Argument erwartet. Innerhalb voncreateOntology wird zunächst parseODPOntology() aufgerufen. Die Auf-gaben dieser Funktion sind das Filtern der für SPREE geeigneten Kategorien auscategories.txt (removeExcludedBranches()) und das Konvertieren derXML-Datei content.rdf.u8 in ein simples Textformat (removeXML()). Die Er-gebnisse dieser zwei Operationen können anschließend für das Erzeugen eines Verzeich-nisbaumes genutzt werden, der die gefilterten Kategorien als Verzeichnisse und die mitden Kategorien verknüpften URLs in einer Datei in dem zugehörigen Verzeichnis ent-


Abbildung 6.2: Aufbau der vollständigen Ontologie

hält (createDirectories()). Der so erzeugte Verzeichnisbaum enthält nun alleInformationen, die benötigt werden, um die Baumstruktur und die zugehörigen Daten(die URLs) in der Datenbank abzulegen. Dieses geschieht über die Funktion fillDB,welche den Pfad des Verzeichnisbaumes als Argument erwartet. Ein einfacherer Wegdie Struktur der Ontologie und die URLs an fillDB zu übergeben, wäre dies überein Python-Objekt zu tun. Allerdings sind die bisher erwähnten Funktionen schon beider Entwicklung von SPREE entstanden und wurden vom Autor der Einfachheit halberwiederverwendet, da die Art der Schnittstelle zwischen den zwei Funktionen eine unter-geordnete Rolle spielt. Der Grund für die Wahl eines Verzeichnisbaumes anstelle einesPython-Objektes als Schnittstelle ist für die weitere Arbeit nicht von Bedeutung und solldeshalb an dieser Stelle nicht weiter erläutert werden.Das Übertragen der Baumstruktur in die nodes-Tabelle erfolgt über die Funkti-on loadNodesFromDirSubWithoutDocs(), welche das Verzeichnis rekursiv


durchläuft. Bei den zu den Knoten gehörenden URLs handelt es sich, wie in Kapitel5 beschrieben, um die Testdokumente. Daher werden sie beim Traversieren des Ver-zeichnisbaumes in die dmoz-Tabelle geschrieben. Die Inhalte der Webseiten, auf diedie URLs verweisen, werden an dieser Stelle noch nicht geladen, sondern erst, wenndie zugehörigen Knoten tatsächlich in der Arbeitsontologie genutzt werden. Für eineBegründung hierfür sei ebenfalls auf Kapitel 5 verwiesen.

6.4 Extraktion der Arbeitsontologie

Liegt die vollständige Ontologie, wie im letzten Abschnitt beschrieben, in der Daten-bank vor, kann nun daraus die Arbeitsontologie extrahiert werden. Diese Funktionali-tät wird im Modul nodereduction.dynamictree.shrinker durch die KlasseShrinker umgesetzt. Die Konfiguration der Klasse geschieht zum Teil über das Mo-dul nodereduction.settings. In settings werden unter anderem die Namender Arbeits- und der vollständigen Ontologie festgehalten. Eine Auslagerung dieser Pa-rameter ist dadurch begründet, dass sie auch von anderen Skripten (Testskripten oderdem oben vorgestellten Modul fulltree) benötigt werden.Da während des gesamten Prozesses oft Informationen über die Knotenstruktur dervollständigen Ontologie benötigt werden, wird im Konstruktor eine Objektrepräsen-tation der Ontologie erzeugt (Methode formTreeWithoutData() der Klassedynamictree.OntologyTree) und in einer Instanzvariablen abgelegt. Auf dieseWeise werden häufige Datenbankanfragen vermieden. Die Objektrepräsentation enthältlediglich die Struktur des Baumes und ist daher nicht allzu speicherintensiv.Um eine einfache Schnittstelle nach außen anzubieten, erfolgt die gesamte Extraktiondurch den Aufruf einer einzigen Methode(Shrinker.shrink()). Diese erwartet alsParameter

• featureSelection: ein boolscher Wert, der angibt, ob eine Termreduktionmittels Odds Ratio durchgeführt werden soll

• experts: eine Liste von Experten-Profilen für die Experten-basierte Reduktion

• queries: eine Liste der Kategorien der Suchanfragen, die für die Anfrage-basierte Reduktion genutzt werden sollen

• queryReduction: die Art der Anfrage-basierten Knotenreduktion (probabili-sitscher Ansatz oder basierend auf SVD, s. Abschnitt 5.2.3).


Der Extraktionsprozess erfolgt durch die in Kapitel 5 identifizierten EinzelschritteExperten-basierte Reduktion, Feature Selection, Anfrage-basierte Reduktion.

6.4.1 Experten-basierte Knotenreduktion

Die Experten-basierte Reduktion wird durch die MethodeshrinkNodesByExperts() realisiert. Hierbei sollen alle Knoten, in denenExperten registriert sind, oder Knoten, deren Elternknoten über mehr als 5 Expertenverfügen, aus der vollständigen Ontologie extrahiert und in die Arbeitsontologieübertragen werden. Dazu wird zunächst berechnet wieviele Experten in jedem Knotenregistriert sind (countExpertsPerNode()). Nachdem mit diesen Informationen,wie in Abschnitt 5.2.1 beschrieben, eine Liste der zu extrahierenden Knoten erstelltwurde (getInclusionList()), kann der eigentliche Extraktionsprozess beginnen(shrinkDocsAndNodes()). Alle Knoten der so erhaltenen Liste werden dabeiaus der nodes Tabelle der vollständigen Ontologie in die nodes Tabelle der Ar-beitsontologie kopiert. Wie in den letzten Kapiteln bereits beschrieben, enthält dievollständige Ontologie lediglich die Baumstruktur und keine Informationen darüber,welche Termmengen mit den Knoten assoziiert werden. Um diese Terme zu ermitteln,werden zunächst mit Hilfe der Suchmaschine Yahoo! für jeden Knoten eine Men-ge an URLs ermittelt. Dabei dient der Knotenname und der Elternknotenname alsSuchanfrage. Der Inhalt der besten 50 so ermittelten Webseiten (Trainigsdokumente)wird daraufhin heruntergeladen und in der docs Tabelle der vollständigen Ontologiegespeichert. Auf diese Weise, stehen die URLs und der Inhalt der Webseiten bei demnächsten Extraktionsprozess bereits zur Verfügung und der beschriebene Prozess mussfür diese Knoten nicht noch einmal durchgeführt werden. Der Inhalt der Dokumentewird dabei nicht als einfache Zeichenkette abgespeichert. Aus den Dokumenten werdendie Stoppwörter entfernt und die verbleibenden Terme werden gestemmt in ein Pythondictionary geladen, welches als String serialisiert in der Datenbank gespeichertwird. Für das Abfragen von Yahoo! und das Herunterladen der Dokumente, wirdfür jeden Knoten ein einzelner Thread gestartet (die Anzahl der Threads ist dabeibeschränkt), um die Verzögerung des Prozesses durch die HTTP-Anfragen zu verrin-gern. Das Threading wird in dem Modul crawler.threadedcrawler umgesetzt.Nachdem die Dokumente in der vollständigen Ontologie gespeichert worden sind,werden sie nun in die docs Tabelle der Arbeitsontologie kopiert, damit im nächstenSchritt daraus die angesprochenen Termmengen erzeugt werden können.Bei der Entwicklung des Lösungskonzeptes in Kapitel 5 wurde der eben beschriebene


Vorgang dem Teilschritt Feature Selection zugeschrieben. Während des Extrahierensder Knoten aus der nodes Tabelle können Informationen über die Elternknoten einesjeden Knoten einfach ausgelesen werden. Da diese Informationen für das Zusammen-setzen der Suchanfrage für Yahoo! benötigt werden, wurde das Laden der Dokumentevorgezogen, was keinen Einfluss auf den restlichen Prozess zur Folge hat.Als letzter Schritt werden die in der vollständigen Ontologie enthaltenen Testdoku-mente der extrahierten Knoten in die dmoz Tabelle der Arbeitsontologie kopiert.Dabei wird analog zu den Trainingsdokumenten der Inhalt der Webseiten übercrawler.threadedcrawler heruntergeladen.

6.4.2 Feature Selection

In der Anfrage-basierten Reduktion müssen automatische Klassifikationstests durchge-führt werden, wofür die Knoten mit einer aus den Trainingsdokumenten stammendenTermmenge verknüpft werden müssen. Diesem Schritt muss daher die Feature Selecti-on vorausgehen, die genau diese Aufgabe übernimmt.Als erstes werden dabei alle Terme aus den Trainingsdokumenten in die terms

Tabelle geschrieben db.loader.TermLoader.loadTerms(). Dabei werdennicht nur die Terme selbst, sondern auch weitere statistische Werte, wie zumBeispiel die Termfrequenz, festgehalten, da diese für die Odds Ratio Heu-ristik oder auch die Berechnung der tfidf-Gewichtung benötigt werden. Alsnächstes werden die zu den Knoten gehörenden Seiten aus der docs Tabel-le geladen und deren Terme in die Datenspalten der nodes Tabelle über-tragen (db.loader.TaxonomyLoader.loadNodesFromSitesReduced()).Die Terme werden dabei als String serialisierte Schlüssel-Wert Paare (dictionary)gespeichert mit den Termen als Schlüssel und deren Gewichtung als zugehöriger Wert.Damit beide vorgestellten Klassifikatoren auf den Daten arbeiten können, werden zweiverschiedene Termgewichtungen benötigt: Termfrequenz (tf ) für Naive Bayes und tfidffür den SPREE Klassifikator. Es wird für jede Gewichtung eine eigene Spalte be-nutzt. Bevor die Daten in die nodes Tabelle übertragen werden, werden sie durchdie Odds Ratio Heuristik gefiltert (utils.dr.reduceByOddsRatio()). Die An-zahl der verbleibenden Terme wird dabei über die Variable dr_nbr_terms aus demnodereduction.settings Modul reguliert. Auf diese Weise werden Tests für dasErmitteln des besten Wertes für dr_nbr_terms erleichtert. Als letzter Schritt mussnoch die Ober-/Unterkategorie Relation umgesetzt werden. Dazu werden die Terme derKnoten, wie in Kapitel chap:loesung beschrieben, von unten beginnend zu ihren El-


ternknoten hinaufpropagiert, so dass jeder Knoten alle Terme der Kindknoten enthält(db.loader.TaxonomyLoader.forwardTerms()). Die so erhaltenen Term-mengen werden in einer eigenen Spalte in der nodes Tabelle abgelegt.

6.4.3 Anfrage-basierte Knotenreduktion

Durch die Feature Selection liegen nun alle Informationen vor, die benötigt werden,um die Anfrage-basierte Reduktion durchzuführen. Diese Reduktion wird durch dieMethode shrinkNodesByQueries() realisiert. Da hierbei zwei verschiedeneAnsätze miteinander verglichen werden sollen, kann über ein Argument bestimmtwerden, ob der probabilistische Ansatz oder der SVD-basierte Ansatz genutzt werdensoll. In beiden Fällen muss zur Laufzeit bestimmt werden, welche Knoten beibehaltenund welche verworfen werden können. Dazu soll zunächst durch den gewählten Ansatzeine Einstufung der Relevanz aller Knoten erfolgen. Diese Funktionalität kapselt dieKlasse NodeReducer aus dem Modul ml.nodereducer. Über den Konstruktorkann der Ansatz gewählt und für die Relevanzberechnung benötigte Daten übergebenwerden. Für den probabilistischen Ansatz sind dies die Knoten, deren Relevanzbestimmt werden soll, und die Suchanfragen, auf deren Basis die Relevanz bestimmtwerden soll. Für den SVD-basierten Ansatz wird zusätzlich noch ein prozentualerWert erwartet (redLevel), der bestimmt wie stark die Singulärwerte reduziertwerden. Nach der Instanziierung erfolgt die Relevanzbestimmung über die MethodegetSortedNodes(), die wie der Name schon sagt, die Knoten sortiert nach ihrerRelevanz zurückliefert. Während für den probabilistischen Ansatz an dieser Stellelediglich die Wahrscheinlichkeiten bestimmt werden, mit denen ein Knoten in denSuchanfragen auftaucht, wird für die Relevanzbestimmung durch den SVD-basiertenAnsatz, die Klasse LSI aus dem Modul ml.svd.lsi benötigt. In LSI wird überden Konstruktor die Anfrage-Knoten Matrix erzeugt. Danach kann über die Methoderun() eine Singulärwertzerlegung mit anschließender Rang-Reduktion durchgeführtwerden. Die Zerlegung geschieht mittels der Funktion svd() aus der numpy Er-weiterung. Nach der, durch den Parameter redLevel gesteuerten, Rang-Reduktion,wird die Annäherung der Anfrage-Knoten Matrix berechnet. Die Relevanz der Knotenwird nun durch den Mittelwert der Einträge der Spaltenvektoren (welche die Knotenrepräsentieren) bestimmt (s. Abschnitt 5.2.3).Da für den SVD-basierten Ansatz die beste Stufe der Rang-Reduktion ermittelt werdenmuss, wird für verschiedene redLevel Werte die Relevanz der Knoten bestimmt.Mit den so erhaltenen Listen der sortierten Knoten werden nun automatische Tests


durchgeführt, die die Untermenge der Knoten finden soll, die die beste Qualität beimExperten-Matching erreicht (dieses Kriterium wurde in Abschnitt 5.2.3 definiert).Als Klassifikator wird Naive Bayes benutzt, für eine Begründung hierfür siehe Ka-pitel 7. Die Tests werden über die Methode getBestNodes() aus dem Modultests.classificationByNode3D gestartet. Die Tests sind so aufgebaut, dassfür jede Liste mit sortierten Knoten, in jeder Iteration, eine bestimmte Anzahl deram wenigsten relevanten Knoten weggelassen werden und für die übriggebliebenenKnoten die Qualität des Experten-Matchings und die Performanz gemessen wird.Auf diese Weise kann aus den verschiedenen Untermengen der einzelnen Listen diebeste, hinsichtlich der Matching-Qualität, ausgewählt werden. Für eine detailliertereBeschreibung der Tests, siehe Kapitel 7.Die so gefundene Menge an Knoten wird nun um die Knoten der ersten Baumebeneund die Knoten, deren Elternknoten über eine hohe Expertenkonzentration verfügen,ergänzt, falls sie durch die Reduktion entfernt wurden (s. Abschnitt 5.2.1). Da die soerhaltene Knotenmenge nicht notwendigerweise einen Baum darstellt, werden allenKnoten all ihre Elternknoten, bis hin zu dem Wurzelknoten, ebenfalls hinzugefügt.Damit ist die Reduktion abgeschlossen und es werden alle Knoten aus der nodes,docs und dmoz Tabelle gelöscht, die nicht in dieser Knotenmenge enthalten sind.Durch das Löschen der Knoten fallen jedoch möglicherweise auch Terme weg undes verändern sich die Termgewichtungen. Aus diesem Grunde werden die, durch dieFeature Selection durchgeführten Schritte, nochmals durchgeführt, d.h. die terms

Tabelle wird neu erzeugt und die Datenspalten der nodes Tabelle neu gefüllt.

Der gesamte Reduktionsprozess ist an dieser Stelle abgeschlossen, aller-dings müssen noch die Terme der Testdokumente für den SPREE Klas-sifikator mit tfidf gewichtet werden, was über den Aufruf der Methodedb.loaderDmoz.DmozLoader.addTFIDF2Testdata() umgesetzt wird.Ausserdem erwartet SPREE in der terms Tabelle zu jedem Term die zu-gehörigen Knoten in einer eigenen Spalte. Dieses wird über die Methodedb.loader.TermLoader.addNodes2Terms() erreicht. Die beiden letzt-genannten Methoden werden nicht näher erläutert, da der Schwerpunkt der Arbeit aufdem Reduktionsprozess liegt, sollen der Vollständigkeit halber aber dennoch genanntwerden.

Kapitel 7

Evaluierung

In diesem Kapitel soll überprüft werden, ob die erarbeitete Lösung die erhofften Ergeb-nisse liefert. Insbesondere soll die dynamische Ontologie mit der statischen, hinsichtlichMatching-Qualität und Performanz, verglichen werden. Als statische Ontologie wird ei-ne Ontologie benutzt, die in der Grösse und Tiefe der SPREE Ontologie stark ähnelt.Zusätzlich dazu soll überprüft werden, ob die Anfrage-basierte Knotenreduktion mittelsSVD gegenüber dem probabilistischen Ansatz einen Mehrwert bringt. Als Maß für dieMatching-Qualität wird das F1-Maß gewählt, da dabei Precision und Recall in einemWert vereint sind, was den Vergleich der Ergebnisse erleichtert. Die Performanz wirddurch die benötigte Klassifikationszeit pro Suchanfrage in Sekunden gemessen.

7.1 Test Aufbau

Die Tests sind folgendermaßen aufgebaut: Aus den Testdokumenten werden zunächstkünstliche Suchanfragen durch zufällig ausgesuchte Terme erstellt. Da die Knotenzu-gehörigkeit der Testdokumente bekannt ist, ist damit auch ihre richtige Kategorisie-rung von vornherein bekannt. Mit dieser Information kann, nach dem Klassifizierender Suchanfrage durch den Klassifikator und dem Ermitteln der entsprechenden Exper-ten, der F1 Wert berechnet werden. Die Ermittlung der Experten erfolgt wie in Kapitel3 beschrieben. Die Experten werden ebenfalls per Zufall generiert, da die in SPREEregistrierten Nutzer nicht für die Durchführung der Tests ausreichen. Die Anzahl derKategorien der erzeugten Experten liegt zwischen 1 und 5.Eine einzige Suchanfrage hat keine zuverlässige Aussagekraft bezüglich der Qualität,da diese in Abhängigkeit der Anfrage unter anderem stark schwanken kann. Aus diesemGrunde werden 5000 Suchanfragen generiert und der F1 Wert darüber gemittelt.Als Klassifikator für die Tests wird Naive Bayes gewählt, da der SPREE Klassifikator in

52

7.2 Testergebnisse 53

naher Zukunft durch Naive Bayes ersetzt werden soll. Auf diese Weise kann eine Aussa-ge darüber getroffen werden, ob die dynamische Ontologie für die nächste Version vonSPREE geeignet ist. Ausserdem wird für Naive Bayes als Termgewichtung lediglich dieTermfrequenz benötigt, somit ist es nicht mehr erforderlich tfidf zu berechnen.Für den Vergleich zwischen der statischen und der dynamischen Ontologie wird alserstes die statische Ontologie mit, wie oben beschrieben, zufällig erzeugten Exper-ten und Suchanfragen getestet. Die dynamische Ontologie wird, basierend auf dieserExpertenmenge, aus der vollständigen ODP-Ontologie erzeugt. Die Grundidee bei derAnfrage-basierten Knotenreduktion ist, die Knotenstruktur der Verteilung der Suchan-fragen anzupassen. Da die Suchanfragen aus der Testmenge generiert werden, wird fürdie Anfrage-basierte Reduktion die vollständige Testmenge genutzt. Für das Testen derdynamischen Ontologie werden dann, um einen fairen Vergleich zu ermöglichen, diegleichen Experten und Suchanfragen wie beim Testen der statischen Ontologie verwen-det.Für die Anfrage-basierten Knotenreduktion wurden zwei Verfahren (SVD und probabi-listischer Ansatz) implementiert, die nachfolgend gegenübergestellt werden sollen. Da-zu werden zunächst die Knoten einer Ontologie mit ca. 1200 Knoten durch die beidenAnsätze nach ihrer Relevanz sortiert. Danach wird die Matching-Qualität für die bestenkC Knoten für verschiedene kC bestimmt. Mit den so emittelten Messwerten werden diebeiden Verfahren miteinander verglichen.Die Auswertung der Termreduktion mittels Odds Ratio wird ebenfalls auf einer Ontolo-gie mit ca. 1200 Knoten und durchschnittlich 2642 Termen pro Knoten durchgeführt.Dabei wird durch Odds Ratio die Relevanz der Terme bestimmt und die Matching-Qualität in Abhängigkeit dieser Terme ermittelt.In Kapitel 5 wird beschrieben, dass bei einer hohen Expertenkonzantration die Kind-knoten zur Arbeitsontologie hinzugefügt werden. Diese Knoten verfügen erst über Ex-perten, nachdem die Expertenprofile durch die Nutzer aktualisiert wurden. Da zu diesemZeitpunkt keine Experten enthalten sind und zusätzliche Knoten die Testzeit verzögernwürden, werden diese Knoten für die Tests nicht hinzugefügt.

7.2 Testergebnisse

Zunächst soll die Feature Selection mittels Odds Ratio ausgewertet werden. Wie Ab-bildung 7.1 zeigt, fällt mit der Anzahl der Terme auch die Matching-Qualität ab. Beieiner Reduktion von gut 600 Termen pro Knoten nimmt der F1 Wert schon um ca. 4%ab. Der Leistungsgewinn bei 600 weniger Termen ist recht gering und rechtfertigt nicht


Abbildung 7.1: Odds Ratio Evaluierung. Die Matching-Qualität als Funktion der Anzahlder Terme pro Knoten.

den Qualitätsverlust. Hinsichtlich der Leistung wäre eine Reduktion auf 200 bis 400Terme wünschenswert, allerdings beträgt hier der Qualitätsverlust schon 6%, was eben-falls nicht tragbar ist. Ein Grund für die schlechten Werte könnte eine zu kleine Trai-ningsmenge sein. Pro Knoten werden 20 Dokumente geladen. Diese Dokumentenmengereicht für eine exakte Bestimmung der für Odds Ratio benötigten Wahrscheinlichkeitenvermutlich nicht aus.

Ein besseres Bild zeichnet sich bei der Anfrage-basierten Knotenreduktion ab (Abbil-dungen 7.2,7.3). Es zeigt sich, dass mit weniger als 100 Knoten eine bessere Matching-Qualität erzielt wird, als mit allen 1246 Knoten. Der mit der Gesamtmenge der Kno-ten erzielte F1 Wert beträgt 0.42. Um die Unterschiede in den Kurvenverläufen bessererkennen zu können, wurden lediglich die Werte für die besten 150 Knoten dargestellt.Zunächst werden verschiedene Stufen der Singulärwertreduktion beim SVD Ansatz mit-einander verglichen (Abbildung 7.2). Die besten Werte werden erreicht, wenn 50% derSingulärwerte für die Rang-Reduktion der Anfrage-Knoten Matrix genutzt werden.

Im Vergleich des probabilistischen Ansatzes mit SVD zeigt sich, dass mit einer Sin-gulärwertreduktion auf 50% eine bessere Matching-Qualität erreicht wird als mit demprobabilistischen Ansatz (Abbildung 7.3). Im Bereich von 15 bis 30 Knoten erzielt der


Abbildung 7.2: Anfrage-basierte Knotenreduktion mit SVD. Abgebildet sind die erziel-ten F1 Werte für verschiedene Rang-Reduktionen bei der SVD Zerlegung. Der angege-bene Prozentsatz entspricht dabei dem verbleibenden Anteil der Singulärwerte.

probabilistische Ansatz zwar nur um ca. 2% schlechtere Werte als das SVD-basierteVerfahren, danach fällt die Qualität aber stark ab. Dies zeigt, dass die Berücksichtigungder Korrelationen in der Anfrage-Knoten Matrix zu einer verbesserten Relevanzbestim-mung der Knoten führt.

Da die Anfrage-basierte Knotenreduktion mit SVD zu besseren Ergebnissen führt, wirdfür den Vergleich zwischen der statischen Ontologie und der dynamisch erzeugten Ar-beitsontologie nur dieser Ansatz verwendet. Desweiteren wird, wegen der schlechtenPerformanz, keine Termreduktion mittels Odds Ratio verwendet. Die Ergebnisse desVergleichs werden in Tabelle 7.1 zusammengefasst. Generell lässt sich sagen, dass diedynamische Ontologie mit einem Bruchteil der Knoten der statischen Ontologie, ei-ne ungefähr gleich gute Matching-Qualität erzielt. Dabei lässt sich erkennen, dass mitwachsender Anzahl der Experten auch die Anzahl der Knoten in der dynamischen On-tologie steigt. Dies lässt sich dadurch erklären, dass für mehrere Experten auch mehrere


Abbildung 7.3: Vergleich zwischen der Anfrage-basierten Knotenreduktion mittels SVDund des probabilistischen Ansatzes

# Experten Statisch Dynamisch# Knoten F1 tclass # Knoten F1 tclass

50 1246 0.594 0.0817 36 0.583 0.0035100 1246 0.544 0.0828 41 0.549 0.0058250 1246 0.420 0.0980 51 0.417 0.0149500 1246 0.397 0.1123 71 0.464 0.0264

Tabelle 7.1: Vergleich zwischen statischer und dynamischer Ontologie in Abhängigkeitder Anzahl der Experten. tclass bezeichnet dabei die benötigte Klassifikationszeit in Se-kunden.

Knoten benötigt werden, um besser zwischen ihnen differenzieren zu können. Als Fol-ge der geringen Knotenanzahl in der dynamischen Ontologie wird, im Vergleich zu derstatischen Ontologie, für die Klassifikation nur ein Bruchteil der Zeit benötigt. Dieszeigt, dass die Anpassung der Ontologie an die dem System zugrundeliegende Daten,mit dem in dieser Arbeit entwickelten Verfahren, eine deutliche Performanzsteigerungbei ungefähr gleichbleibender Matching-Qualität zur Folge hat.

Kapitel 8

Fazit und Ausblick

Abschliessend lässt sich zusammenfassen, dass mit der entwickelten Lösung und derdarin verwendeten Verfahren die gesetzten Ziele erreicht wurden. Es wurde ein Systementwickelt, das die Knotenstruktur einer Ontologie auf eine gegebene Experten- undAnfrageverteilung anpasst. Angewendet auf eine Ontologie von ähnlichem Aufbau wieder der SPREE Ontologie wurde, durch die Reduktion der Kategorien, eine signifikantePerformanzsteigerung bei ungefähr gleichbleibender Matching-Qualität erreicht. DieseErgebnisse zeigen, dass ein Austausch der statischen SPREE Ontologie durch eineadaptive, dynamische Ontologie zu einer verbesserten Leistung führt.Neben der Knotenreduktion wurde auch eine Termreduktion mittels Feature Selectiondurch die Odds Ratio Heuristik implementiert. Jedoch konnten die erhofften Ergeb-nisse nicht erzielt werden. Die Reduktion der Terme hatte einen zu starken Verlustder Matching-Qualität zur Folge. Um dennoch eine effektive Feature Selection zuerreichen, könnte die Anzahl der Trainingsdokumente erhöht werden, oder andereHeuristiken herangezogen werden. Die Leistungsgewinne der Knotenreduktion sindjedoch so hoch, dass eine Termreduktion nicht mehr unbedingt benötigt wird.

In dieser Arbeit wurde ein System zur Erzeugung einer dynamischen Ontologieentwickelt, mit dem Ziel diese Ontologie in SPREE einzubinden. Da die Ergebnisse füreine solche Integration sprechen, müssen im nächsten Schritt die hierbei entstehendenProbleme angegangen werden. Das erste Problem, das sich dabei ergibt, ist, dassdie für SPREE verwendete vollständige ODP-Ontologie nicht mehr vorliegt. Diezur Zeit aktuelle ODP-Ontologie wurde in ihrer Struktur so verändert, dass mancheKnoten der SPREE Ontologie nicht mehr in der neuen Ontologie enthalten sind. Ausdiesem Grunde muss hierfür eine Abbildung dieser Knoten auf die neue Ontologieermöglicht werden. Als weiteres Problem ergibt sich, dass durch die dynamische

57

58

Ontologie viele Knoten wegfallen. Somit verlieren die Verweise auf diese Knoten, bei-spielsweise aus den Expertenprofilen oder den Suchanfragen, ihre Gültigkeit. Werdendiese Knoten jedoch nicht gelöscht, sondern lediglich als gelöscht markiert, behal-ten die Verweise ihre Gültigkeit und werden bei der Klassifikation nicht mit einbezogen.

Auch wenn für die Integration noch weitere Arbeitsschritte nötig sind, die Ergeb-nisse rechtfertigen diesen Aufwand: Momentan sind 163 Nutzer in SPREE registriert.Bei 250 Nutzern ergibt sich laut Tabelle 7.1 ein Performanzgewinn um den Faktor 6.6.

Literaturverzeichnis

[1] Ontologie. http://de.wikipedia.org/wiki/Ontologie_

(Informatik). 1, 6

[2] USCHOLD, MIKE und MICHAEL GRUNINGER: Ontologies: Principles, Methods,

Applications. Knowledge Engineering Review, 11(2), 1996. 5

[3] FENSEL, DIETER: Ontologies: Silver Bullet for Knowledge Management and

Electronic Commerce. Springer Verlag, Berlin Heidelberg, 138 p., 2001. 5

[4] HUHNS, MICHAEL N. und MUNINDAR P. SINGH: Agents on the Web: Ontologies

for Agents. IEEE Internet Computing, 1(6):81–83, 1997. 5

[5] GRUBER, THOMAS R.: A translation approach to portable ontology specificati-

ons. Knowl. Acquis., 5(2):199–220, 1993. 5

[6] BORST, WILLEM NICO: Construction of Engineering Ontologies for Knowledge

Sharing and Reuse. Doktorarbeit, 1997. 5

[7] FÜRST, FRÉDÉRIC und FRANCKY TRICHET: Heavyweight Ontology Enginee-

ring. In: MEERSMAN, ROBERT, ZAHIR TARI und PILAR HERRERO (Heraus-geber): OTM Workshops (1), Band 4277 der Reihe Lecture Notes in Computer

Science, Seiten 38–39. Springer, 2006. 6, 7

[8] SALTON, GERARD, A. WONG und C. S. YANG: A Vector Space Model for Auto-

matic Indexing. Commun. ACM, 18(11):613–620, 1975. 7

[9] SEBASTIANI, FABRIZIO: Machine learning in automated text categorization.ACM Computing Surveys, 34(1):1–47, 2002. 8, 11

[10] FERBER, REGINALD: Information Retrieval: Suchmodelle und Data-Mining-

Verfahren für Textsammlungen und das Web. dpunkt Verlag, Heidelberg, 2003.8, 9

59

http://de.wikipedia.org/wiki/Ontologie_(Informatik)

http://de.wikipedia.org/wiki/Ontologie_(Informatik)

LITERATURVERZEICHNIS 60

[11] PORTER, M. F.: An algorithm for suffix stripping. Seiten 313–316, 1997. 10

[12] YANG, YIMING und JAN O. PEDERSEN: A comparative study on feature selection

in text categorization. In: FISHER, DOUGLAS H. (Herausgeber): Proceedings of

ICML-97, 14th International Conference on Machine Learning, Seiten 412–420,Nashville, US, 1997. Morgan Kaufmann Publishers, San Francisco, US. 11, 38

[13] MLADENIC, D. und M. GROBELNIK: Feature selection for classification based

on text hierarchy. In: Conference on Automatic Learning and Discovery, 1998. 11

[14] MLADENIC, DUNJA und MARKO GROBELNIK: Feature Selection for Unbalanced

Class Distribution and Naive Bayes. In: ICML ’99: Proceedings of the Sixteenth

International Conference on Machine Learning, Seiten 258–267, San Francisco,CA, USA, 1999. Morgan Kaufmann Publishers Inc. 11

[15] DEERWESTER, SCOTT C., SUSAN T. DUMAIS, THOMAS K. LANDAUER, GE-ORGE W. FURNAS und RICHARD A. HARSHMAN: Indexing by Latent Semantic

Analysis. Journal of the American Society of Information Science, 41(6):391–407,1990. 12

[16] Latent Semantic Indexing. http://en.wikipedia.org/wiki/Latent_

semantic_indexing. 12

[17] ZHAI, CHENGXIANG und JOHN LAFFERTY: A study of smoothing methods for

language models applied to Ad Hoc information retrieval. In: SIGIR ’01: Procee-

dings of the 24th annual international ACM SIGIR conference on Research and

development in information retrieval, Seiten 334–342, New York, NY, USA, 2001.ACM. 17

[18] HWANG, CHUNG HEE: Incompletely and Imprecisely Speaking: Using Dynamic

Ontologies for Representing and Retrieving Information. In: Knowledge Repre-

sentation Meets Databases, Seiten 14–20, 1999. 18

[19] CHOI, NAMYOUN, IL-YEOL SONG und HYOIL HAN: A survey on ontology map-

ping. SIGMOD Rec., 35(3):34–41, 2006. 19

[20] NOY, NATALYA FRIDMAN und MARK A. MUSEN: PROMPT: Algorithm and Tool

for Automated Ontology Merging and Alignment. In: AAAI/IAAI, Seiten 450–455,2000. 19

http://en.wikipedia.org/wiki/Latent_semantic_indexing

http://en.wikipedia.org/wiki/Latent_semantic_indexing


[21] DOU, DEJING: Ontology translation by ontology merging and automated reaso-

ning. Doktorarbeit, New Haven, CT, USA, 2004. Director-Drew V. Mcdermott.19

[22] KONSTANTINOS KOTIS, GEORGE VOUROS: The HCONE Approach to Ontolo-

gy Merging. In: The Semantic Web: Research and Applications. First European

Semantic Web Symposium (ESWS 2004), Seiten 137–151, 2004. 19

[23] WOUTERS, CARLO, THARAM S. DILLON, J. WENNY RAHAYU und ELIZABETH

CHANG: A Practical Walkthrough of the Ontology Derivation Rules. In: DEXA

’02: Proceedings of the 13th International Conference on Database and Expert

Systems Applications, Seiten 259–268, London, UK, 2002. Springer-Verlag. 19

[24] WOUTERS, C., T. DILLON, W. RAHAYU, E. CHANG und R. MEERSMAN: A

Practical Approach to the Derivation of Materialized Ontology Views. Idea GroupPublishing, 2004. 19

[25] SWARTOUT, B., R. PATIL, K. KNIGHT und T. RUSS: Toward Distributed Use of

Large-Scale Ontologies. In: the 10th Workshop on Knowledge Acquisition, Banff,Canada, 1996. 19

[26] SEIDENBERG, JULIAN und ALAN RECTOR: Web ontology segmentation: analy-

sis, classification and use. In: WWW ’06: Proceedings of the 15th international

conference on World Wide Web, Seiten 13–22, New York, NY, USA, 2006. ACMPress. 20

[27] ALPCAN, TANSU, CHRISTIAN BAUCKHAGE und SACHIN AGARWAL: An Effi-

cient Ontology-Based Expert Peering System. In: GbRPR, Seiten 273–282, 2007.21

[28] BAUCKHAGE, CHRISTIAN, TANSU ALPCAN, SACHIN AGARWAL, FLORIAN

METZE, ROBERT WETZKER, MILENA ILIC und SAHIN ALBAYRAK: An Intel-

ligent Knowledge Sharing System for Web Communities. In: Proceedings of the

IEEE International Conference on Systems, Man and Cybernetics 2007. IEEEComputer Society Press, 2007. 21

[29] WETZKER, ROBERT, TANSU ALPCAN, CHRISTIAN BAUCKHAGE, WINFRIED

UMBRATH und SAHIN ALBAYRAK: An unsupervised hierarchical approach to

document categorization. In: Proceedings IEEE Intl. Conf. on Web Intelligence

(WI’07), 2007. 21


[30] EMBLEY, DAVID W., DOUGLAS M. CAMPBELL, RANDY D. SMITH und STE-PHEN W. LIDDLE: Ontology-Based Extraction and Structuring of Information

from Data-Rich Unstructured Documents. In: CIKM, Seiten 52–59, 1998. 26

[31] MAEDCHE, A., S. STAAB und R. STUDER: Ontology-based Information Extrac-

tion and Integration. 26

[32] HENNER GRAUBITZ, KARSTEN WINKLER und MYRA SPILIOPOULOU: Seman-

tic Tagging of Domain-Specific Text Documents with DIAsDEM. 26

[33] LIU, TIE-YAN, YIMING YANG, HAO WAN, QIAN ZHOU, BIN GAO, HUA-JUN ZENG, ZHENG CHEN und WEI-YING MA: An experimental study on

large-scale web categorization. In: WWW ’05: Special interest tracks and pos-

ters of the 14th international conference on World Wide Web, Seiten 1106–1107,New York, NY, USA, 2005. ACM Press. 26

[34] WU, SHIH-HUNG, TZONG-HAN TSAI und WEN-LIAN HSU: Text categorization

using automatically acquired domain ontology. In: Proceedings of the sixth inter-

national workshop on Information retrieval with Asian languages, Seiten 138–145,Morristown, NJ, USA, 2003. Association for Computational Linguistics. 26

[35] HE, QINMING, LING QIU, GUOTAO ZHAO und SHENKANG WANG: Text Catego-

rization Based on Domain Ontology. In: WISE, Seiten 319–324, 2004. 26

[36] WEEBER, MARC, R. HARALD BAAYEN und REIN VOS: Extracting the lowest-

frequency words: pitfalls and possibilities. Comput. Linguist., 26(3):301–317,2000. 38

[37] PARSIAN, MAHMOUD: JDBC Recipes, Kapitel Exploring the Statement, Seiten381–430. Apress, 2005. 44

Abbildungsverzeichnis

2.1 Semiotisches Dreieck . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Vektorraummodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3 Zerlegung einer Matrix durch SVD . . . . . . . . . . . . . . . . . . . . 12

3.1 Repräsentation einer Beispiel-Ontologie mit 10 Knoten als Vektor . . . 24

4.1 Direktes Matching vs. Ontologie-basiertes Matching . . . . . . . . . . 274.2 Performanz: Direktes Matching vs. Ontologie-basiertes Matching . . . 29

5.1 System-Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

6.1 Teilsystem-Diagramm . . . . . . . . . . . . . . . . . . . . . . . . . . . 426.2 Aufbau der vollständigen Ontologie . . . . . . . . . . . . . . . . . . . 46

7.1 Odds Ratio Evaluierung . . . . . . . . . . . . . . . . . . . . . . . . . . 547.2 Anfrage-basierte Reduktion mit SVD . . . . . . . . . . . . . . . . . . 557.3 Vergleich probabilistischer Ansatz und SVD . . . . . . . . . . . . . . . 56

63

Abkürzungsverzeichnis

idf Inverse document frquency, inverse DokumentenhäufigkeitIR Information RetrievalLSA Latent Semantic AnalysisODP Open Directory ProjectSVD Singular Value Decomposition, Singulärwertzerlegungtf Term frequency, TermhäufigkeitURL Uniform Resource LocatorXML Extensible Markup Language

64

Anhang A

Anhang

A.1 Quelltexte

In diesem Abschnitt sind die wichtigsten Module aufgelistet. Der vollständige Quellco-de befindet sich auf dem beiliegenden Datenträger.

dynamictree

shrinker.py

1 from __future__ import division

2 import sys, os

3

4 import turbogears

5 import cPickle

6 import time

7

8 from sqlalchemy import func, select, insert, update, delete

9

10 from nodereduction import settings

11

12 from nodereduction.crawler import docloader

13 from nodereduction.dynamictree.dynOntologyTree import *14 import nodereduction.dynamictree.dynOntologyTree as dot

15

16 from nodereduction.db import model, dataprovider

17 from nodereduction.db.loader import TaxonomyLoader, TermLoader, SiteLoader

18 from nodereduction.db.loaderDmoz import DmozLoader

19 from nodereduction.db.tfidfLoader import TFIDFLoader

20

21 from nodereduction.crawler import threadedcrawler

22 from nodereduction.ml import nodereducer

23 from nodereduction.tests import classificationByNode3D as testexperts

24

25 class Shrinker:

65

A.1 Quelltexte 66

26 ’’’

27 The Shrinker class provides methods for extracting a subontology (called the

28 shrinked ontology) out of another ontology (called the original ontology).

29 Extraction(or shrinking) is performed by considering a given expertstructure

30 (expert-based reduction) and by taking a query-distribution over the 'ontologynodes

31 into account (query-based reduction).

32 ’’’

33

34

35 ’’’

36 Defines the minimum depth of the shrinked tree, i.e. only nodes with a level '<= minLevel

37 are removed.

38 ’’’

39 minLevel = 1

40

41 ’’’

42 Defines the minimum number of experts a parent node must have to not delete 'its

43 children nodes, i.e. all nodes with at least minParentExperts experts will

44 have children in the shrinked tree.

45 ’’’

46 minParentExperts = 5

47

48 def __init__(self):

49 ’’’

50 Load needed data

51 ’’’

52

53 self.origTax = settings.origTax

54 self.shrinkTax = settings.shrinkTax

55

56 ’’’ List of nodes that will be added to the shrinked DB after reduction’’’

57 self.addedNodes = []

58

59 ’’’ List of nodes that will not appear in the shrinked DB ’’’

60 self.nodeExclusionList = []

61 ’’’ List of nodes that will be used for expert based reduction ’’’

62 self.nodeInclusionList = []

63

64 print "Loading full tree..."

65 start = time.time()

66 self.tree = OntologyTree(self.origTax)

67 self.tree.formTreeWithoutData()

68 end = time.time()

69 print ’Done in %f.’ % (end-start)

70

71

72 def shrink(self, featureSelection=True, experts=None, queries=None, 'queryReduction=nodereducer.NodeReducer.LSI):

73 ’’’

74 Transforms the given ontology tree to a smaller one taking into account

75 the information about the experts registered in the system and the

76 user generated queries.

A.1 Quelltexte 67

77

78 @param featureSelection Determines if featureSelection should be used

79 @param experts List of expert profiles used for expert-based reduction.

80 Each expert profile is a list of node IDs

81 @param queries List of queries used for query-based reduction. A query

82 is represented by the node ID it is categorized in.

83 @param queryReduction The method used to perform query-based reduction

84 ’’’

85

86 totalstart = time.time()

87

88 if experts:

89 self.tree.experts = experts

90

91 extractedNodes = self.shrinkNodesByExperts()

92

93 print ’Loading terms from docs...’


95 termLoader = TermLoader()

96 termLoader.loadTerms(self.shrinkTax)



99

100 if not queries:

101 tfidfLoad = TFIDFLoader()

102 tfidfLoad.addTFIDF2Docs(self.shrinkTax)

103

104 print ’Adding term data to nodes ...’

105 taxLoader = TaxonomyLoader()

106 if featureSelection:

107 taxLoader.loadNodesFromSitesReduced(self.shrinkTax)

108 else:

109 taxLoader.loadNodesFromSites(self.shrinkTax)

110 print ’Done.’

111

112 taxLoader.forwardTerms(self.shrinkTax)

113 if not queries:

114 taxLoader.forwardTermsTFIDF(self.shrinkTax)

115

116 if queries:

117 # if information about queries is given perform query-based node 'reduction

118 self.shrinkNodesByQueries(extractedNodes, queries, queryReduction, 'featureSelection)

119

120 dmozLoader = DmozLoader()

121 dmozLoader.addTFIDF2Testdata(self.shrinkTax)

122

123 termLoader.addNodes2Terms(self.shrinkTax, ’data_tfidf_merged’)

124

125 totalend = time.time()

126 print ’Finished shrinking in %f.’ % (totalend-totalstart)

127

128 termCountShr = select([func.count(model.term_tables[self.shrinkTax].c.id)]).'execute().fetchone()[0]

A.1 Quelltexte 68

129 termCountOrig = select([func.count(model.term_tables[self.origTax].c.id)]).'execute().fetchone()[0]

130 nodeCountShr = select([func.count(model.node_tables[self.shrinkTax].c.id)]).'execute().fetchone()[0]

131 nodeCountOrig = select([func.count(model.node_tables[self.origTax].c.id)]).'execute().fetchone()[0]

132

133 print ’Reduced Nodes to’, nodeCountShr, ’out of’, nodeCountOrig

134 print ’Reduced Terms to’, termCountShr, ’out of’, termCountOrig

135

136 def addNodesToExclusionList(self, nodelist):

137 ’’’

138 Extends the list of nodes to be excluded with the given one

139

140 @param nodelist A list of node ids to be excluded

141 ’’’

142

143 self.nodeExclusionList.extend(nodelist)

144

145 def addNodesToInclusionList(self, nodelist):

146 ’’’

147 Extends the list of nodes that will be preserved with the given one

148

149 @param nodelist A list of node ids to be included

150 ’’’

151

152 self.nodeInclusionList.extend(nodelist)

153

154 def countExpertsPerNode(self):

155 ’’’

156 Labels each tree node with the number of experts passing through them

157 ’’’

158 print ’Counting experts per node...’

159

160 for u in self.tree.experts:

161 exp = self.tree.experts[u]

162 for nid in exp:

163 self.tree.asDict[nid].noExperts += 1

164


166

167

168 def getExclusionList(self):

169 ’’’

170 Returns a list of node id’s that can be removed from the tree.

171 Criteria for building this list are the number of experts per node

172 and the node level.

173 ’’’

174 print ’Building node exclusion list...’

175

176 exList = []

177 for node in self.tree.root.children:

178 exList.extend(self.getExclSubList(node))

179


A.1 Quelltexte 69

181 return exList

182

183

184 def getExclSubList(self, node):

185 ’’’

186 Recursively adds nodes to the exclusionlist and returns it.

187

188 @param node Starting node for recursion

189 ’’’

190 exList = []

191 parentlow = node.parent.noExperts < self.minParentExperts

192

193 if node.noExperts < 1 and node.level > self.minLevel and parentlow:

194 ’’’ remove this node ’’’

195 exList.append(int(node.id))

196 exList.extend(self.tree.asDict[int(node.id)].getAllChildrenIds())

197 else:

198 for child in node.children:

199 exList.extend(self.getExclSubList(child))

200

201 return exList

202

203 def getInclusionList(self):

204 ’’’

205 Returns a list of node id’s that will be included in the shrinked tree.

206 Criteria for building this list are the number of experts per node

207 and the node level.

208 ’’’

209 print ’Building node inclusion list...’

210

211 inList = [int(self.tree.root.id)]

212 for node in self.tree.root.children:

213 inList.extend(self.getInclSubList(node))

214


216 return inList

217

218

219 def getInclSubList(self, node):

220 ’’’

221 Recursively traverses the tree and adds nodes to a list

222 which is supposed to extend the inclusion list and returns it.

223

224 @param node Starting node for recursion

225 ’’’

226 inList = []

227 parenthigh = node.parent.noExperts >= self.minParentExperts

228 if node.noExperts == 0 and parenthigh:

229 self.addedNodes.append(int(node.id))

230 if node.noExperts > 0 or node.level <= self.minLevel: #or parenthigh:

231 if node.noExperts == 1 and node.parent.noExperts == 1:

232 return inList#self.nodeExclusionList.append(int(node.parent.id))

233 ’’’ include this node ’’’

234 inList.append(int(node.id))


A.1 Quelltexte 70

236 inList.extend(self.getInclSubList(child))

237

238 return inList

239

240 def shrinkDocsAndNodes(self):

241 ’’’

242 Copies all rows having a node id listed in nodeInclusionList

243 from the docs and the nodes table from original DB to shrinked DB.

244 ’’’

245

246 # Remove nodes listed in exclusion list

247 nInclusionList = list(set(self.nodeInclusionList).difference(set(self.'nodeExclusionList)))

248

249 print ’Adding all nodes contained in inclusion list(%d nodes)...’ % len('nInclusionList)

250


252 if len(nInclusionList) == 0:

253 nInclusionList.append(-5)

254 nInclusionList.append(-4)

255

256

257 # create and fill node table

258 node_table = model.node_tables[self.origTax]

259

260 nodeRows = select([node_table.c.id,

261 node_table.c.node_id,

262 node_table.c.leftidx,

263 node_table.c.rightidx,

264 node_table.c.name,

265 node_table.c.name_full,

266 node_table.c.level], node_table.c.id.in_(*nInclusionList))'.execute()

267

268 node_table = model.node_tables[self.shrinkTax]

269 node_table.drop(checkfirst=True)

270 node_table.create()

271

272 print ’\tInserting nodes into shrinked nodes table...’

273

274 nodeids = []

275 nid2path = {}

276 inserts = []

277 i = node_table.insert()

278 for node in nodeRows:

279 nodeids.append(node.id)

280 nid2path[node.id] = node.name_full

281

282 inserts.append(dict(node))

283 if len(inserts) > 500:

284 i.execute(*inserts)

285 inserts = []

286


A.1 Quelltexte 71


289 inserts = []

290

291 del nInclusionList

292

293 print ’\tFind nodes with an insufficient amount of documents and crawl them'...’

294

295 site_table = model.doc_tables[self.origTax]

296 startIdx = 0

297 maxlength = 200

298 while startIdx < len(nodeids):

299 endIdx = min(len(nodeids), startIdx + maxlength)

300 partlist = nodeids[startIdx:endIdx]

301 # find nodes without docs

302 siteRows = select([site_table.c.node_id,site_table.c.id,site_table.c.data'],

303 site_table.c.node_id.in_(*partlist)).execute()

304

305 nodes_to_load = list(partlist)

306 sitecounter = {}

307 for row in siteRows:

308 if not row.node_id in sitecounter:

309 sitecounter[row.node_id] = 0

310

311 if row.data != None and cPickle.loads(row.data) != ’’:

312 sitecounter[row.node_id] += 1

313

314 for nid in sitecounter:

315 if sitecounter[nid] >= settings.nbr_sites[self.shrinkTax] and nid in 'nodes_to_load:

316 nodes_to_load.remove(nid)

317

318 # load docs for nodes without docs

319 threadedcrawler.crawl(nodes_to_load, nid2path, self.origTax)

320

321 startIdx = endIdx

322

323 print ’\tInserting documents into shrinked docs table...’

324

325 # create and fill shrinked site table

326 site_table = model.doc_tables[self.shrinkTax]

327 site_table.drop(checkfirst=True)

328 site_table.create()

329 i = site_table.insert()

330

331 site_table = model.doc_tables[self.origTax]

332

333 startIdx = 0

334 maxlength = 200

335 while startIdx < len(nodeids):

336 endIdx = min(len(nodeids), startIdx + maxlength)

337 partlist = nodeids[startIdx:endIdx]

338

339 siteRows = select([site_table.c.id,

A.1 Quelltexte 72

340 site_table.c.node_id,

341 site_table.c.url,

342 site_table.c.data],

343 site_table.c.node_id.in_(*partlist)).execute()

344

345 sitecounter = {}

346 inserts = []

347

348 for site in siteRows:

349 if not site.node_id in sitecounter:

350 sitecounter[site.node_id] = 0

351

352 # continue if node already has sufficient docs

353 if sitecounter[site.node_id] >= settings.nbr_sites[self.shrinkTax]:

354 continue

355 else:

356 sitecounter[site.node_id] += 1

357

358 if site.data == None:

359 site.data = docloader.updateData(site.url,

360 model.doc_tables[self.origTax],

361 ’data’,

362 docid=site.id)

363

364 if site.data == None:

365 sitecounter[site.node_id] -= 1

366 continue

367

368 site.data = cPickle.dumps(site.data)

369

370 inserts.append(dict(site))



373 inserts = []

374



377


379


381 print ’All done in %f.’ % (end-start)

382

383 return nodeids

384

385 def shrinkTestdata(self):

386 ’’’

387 Copies all rows having a node id listed in nodeInclusionList

388 from the dmoz table from original DB to shrinked DB.

389 ’’’

390 print ’Filtering testdata...’

391

392 # Remove nodes listed in exclusion list

393 nInclusionList = list(set(self.nodeInclusionList).difference(set(self.'nodeExclusionList)))

A.1 Quelltexte 73

394


396

397 dmoz_table = model.dmoz_tables[self.shrinkTax]

398 dmoz_table.drop(checkfirst=True)

399 dmoz_table.create()

400 i = dmoz_table.insert()

401

402 dmoz_table = model.dmoz_tables[self.origTax]

403

404 startIdx = 0

405 maxlength = 200

406 while startIdx < len(nInclusionList):

407 endIdx = min(len(nInclusionList), startIdx + maxlength)

408 partlist = nInclusionList[startIdx:endIdx]

409

410 dmozRows = select([dmoz_table],

411 and_(dmoz_table.c.node_id.in_(*partlist),

412 not_(dmoz_table.c.bow.endswith(’(d.’)))).execute()

413

414 threadedcrawler.handle_dmoz_docs(i, list(dmozRows), model.dmoz_tables['self.origTax], ’bow’)

415


417



420

421 def shrinkNodesByExperts(self):

422 ’’’

423 Performs expert-based nodereduction.

424

425 @return The list of node IDs contained in the shrinked ontology

426 ’’’

427 self.countExpertsPerNode()

428 print ’# nodes:’, len(self.tree.asDict)

429

430 # Identify nodes to extract from the full ontology by

431 # taking the expert structure into account

432 self.nodeInclusionList.extend(self.getInclusionList())

433

434 # extract nodes listed in nodeInclusionList from full ontology

435 # i.e. expert based node reduction

436 extractedNodes = self.shrinkDocsAndNodes()

437 self.shrinkTestdata()

438

439 return extractedNodes

440

441 def shrinkNodesByQueries(self, extractedNodes, queries, queryReduction, 'featureSelection):

442 ’’’

443 Performs query-based nodereduction in self.shrinkTax

444

445 @param extractedNodes A list of node IDs determining the node set to be 'reduced

A.1 Quelltexte 74

446 @param queries List of lists: Inner lists represent queries, 'containing the node ids

447 the queries belong to

448 @param queryReduction The approach used to reduce nodes(simple 'probability or SVD)

449 ’’’

450 print ’Determining most used nodes...’


452

453 red2sorted_nodes = {}

454 config = None

455

456 if queryReduction == nodereducer.NodeReducer.LSI:

457 config = nodereducer.LSIConfig(extractedNodes, queries, 0)

458 nr = nodereducer.NodeReducer(queryReduction,config)

459 for redLevel in [1,0.6,0.55,0.5]:

460 config.redLevel = redLevel

461 sorted_nodes = nr.getSortedNodes(config)

462 red2sorted_nodes[redLevel] = sorted_nodes

463

464 if queryReduction == nodereducer.NodeReducer.PROB:

465 config = nodereducer.PROBConfig(extractedNodes, queries)

466 nr = nodereducer.NodeReducer(queryReduction)

467 sorted_nodes = nr.getSortedNodes(config)

468 red2sorted_nodes[’PROB’] = sorted_nodes

469

470

471 bestnodes = testexperts.getBestNodes(self.shrinkTax, red2sorted_nodes, self.'tree.experts)

472



475

476 # add tags with level <= minLevel

477 for nid in self.tree.asDict:

478 if self.tree.asDict[nid].level <= self.minLevel:

479 bestnodes.append(nid)

480

481 bestnodes = list(set(bestnodes))

482 print ’#nodes after adding nodes <= minLevel’, bestnodes

483 # add tags which should be added to the ontology due to high expert

484 # concentration in its parents

485 #bestnodes.extend(self.addedNodes)

486 #bestnodes = list(set(bestnodes))

487

488 # form a subtree out of the node ids

489 self.tree.addParents(bestnodes)

490

491 print "Reducing nodes in DB to %i and recalculating term weights" % len('bestnodes)


493

494 #remove query-based reduced nodes from docs-, nodes- and dmoz-tables

495 node_table = model.node_tables[self.shrinkTax]

496 node_table.delete(not_(node_table.c.id.in_(*bestnodes))).execute()

A.1 Quelltexte 75

497 doc_table = model.doc_tables[self.shrinkTax]

498 doc_table.delete(not_(doc_table.c.node_id.in_(*bestnodes))).execute()

499 dmoz_table = model.dmoz_tables[self.shrinkTax]

500 dmoz_table.delete(not_(dmoz_table.c.node_id.in_(*bestnodes))).execute()

501

502 #load terms again, new tf, idf values...

503 termLoader = TermLoader()

504 termLoader.loadTerms(self.shrinkTax)

505

506 #with new tf, idf values we can compute tfidf

507 tfidfLoad = TFIDFLoader()

508 tfidfLoad.addTFIDF2Docs(self.shrinkTax)

509

510 #load terms to nodes and propagate them to parents


512 if featureSelection:

513 taxLoader.loadNodesFromSitesReduced(self.shrinkTax)

514 else:

515 taxLoader.loadNodesFromSites(self.shrinkTax)

516 taxLoader.forwardTerms(self.shrinkTax)

517 taxLoader.forwardTermsTFIDF(self.shrinkTax)

518



521

522 if __name__ == "__main__":

523 if ’1200’ in sys.argv[1:]:

524 nodestable = model.node_tables[settings.origTax]

525 noderows = select([nodestable.c.id],

526 or_(nodestable.c.level < 3,

527 and_(nodestable.c.name_full.startswith(’/'Computers/’),nodestable.c.level < 4),

528 and_(nodestable.c.name_full.startswith(’/'Science/’),nodestable.c.level < 4)

529 )).execute()

530 noderows = list(noderows)

531

532 nids = [n.id for n in noderows]

533

534 s = Shrinker()

535 s.shrinkTax = "dmoz_1200"

536 s.addNodesToInclusionList(nids)

537 s.shrink(False)

538 if ’8100’ in sys.argv[1:]:

539 nodestable = model.node_tables[settings.origTax]

540 noderows = select([nodestable.c.id],

541 or_( nodestable.c.name_full.startswith(’/Computers/'’),

542 and_(nodestable.c.name_full.startswith(’/'Science/’),nodestable.c.level < 5)

543 )).execute()

544 noderows = list(noderows)

545

546 nids = [n.id for n in noderows]

547

A.1 Quelltexte 76

548 s = Shrinker()

549 s.shrinkTax = "dmoz_8100"


551 s.shrink(featureSelection=False)

552

553 if ’20000’ in sys.argv[1:]:

554 s = Shrinker()

555 s.shrinkTax = "dmoz_20k"

556 s.tree.populateExperts(5000)

557 s.countExpertsPerNode()

558 nids = s.getInclusionList()

559 f = open(’20kexps.pkl’,’w’)

560 cPickle.dump(s.tree.experts,f)

561 f.close()

562 f = open(’20knids.pkl’,’w’)

563 cPickle.dump(nids,f)

564 f.close()

565 print len(nids)

566 s.tree.experts = []



569

570 if ’13000’ in sys.argv[1:]:

571 s = Shrinker()

572 s.shrinkTax = "dmoz_13k"

573 s.tree.populateExperts(3000)

574 s.countExpertsPerNode()

575 nids = s.getInclusionList()

576 f = open(’13kexps.pkl’,’w’)

577 cPickle.dump(s.tree.experts,f)

578 f.close()

579 f = open(’13knids.pkl’,’w’)

580 cPickle.dump(nids,f)

581 f.close()

582 print len(nids)

583 s.tree.experts = []



fulltree.py


2 import sys, os, shutil

3

4 from nodereduction.parser import dmoz2spreetree, txt2dir, xml2txt

5 from nodereduction.db.loader import TaxonomyLoader

6

7

8 def createOntology(dmoz_category_file, dmoz_xml_file, ontology_name):

9 ’’’

10 Loads the given dmoz ontology structure to the specified database table

11

12 @param dmoz_category_file The categories.txt file which is contained in the 'dmoz distribution

A.1 Quelltexte 77

13 @param dmoz_xml_file The ontology xml file which is contained in the dmoz 'distribution

14 @param ontology_name The name appended to the database table names

15 ’’’

16 target_dir = ’nodereduction/parser/tree’

17

18 parseODPOntology(dmoz_category_file, dmoz_xml_file, target_dir)

19 fillDB(ontology_name, os.path.abspath(target_dir + ’/Top’))

20

21 # delete created directory

22 recursiveDelete(target_dir)

23

24 def recursiveDelete(dir):

25 ’’’

26 Recursively deletes the given directory and all of its contents

27

28 @param dir The directory to remove

29 ’’’

30 try:

31 shutil.rmtree(dir)

32 except:

33 recursiveDelete(dir)

34

35 def parseODPOntology(dmoz_category_file, dmoz_xml_file, target_dir):

36 ’’’

37 Parses the given Dmoz ontology and writes its structure as

38 a directory into target_dir.

39

40 @param dmoz_category_file The categories.txt file which is contained in the 'dmoz distribution

41 @param dmoz_xml_file The ontology xml file which is contained in the dmoz 'distribution

42 @param target_dir The directory where the tree structure should be written to

43 ’’’

44 reduced_cats_file = ’nodereduction/parser/reduced_categories.txt’

45 excl_regex_file = ’nodereduction/parser/excludedtopics.txt’

46 dmoz2spreetree.removeExcludedBranches(dmoz_category_file, excl_regex_file, 'reduced_cats_file)

47

48 # convert the content.rdf.u8 - xml file to a txt file

49 dmoz_xml_stripped = ’nodereduction/parser/odpxmlstripped.txt’

50 xml2txt.removeXML(dmoz_xml_file, dmoz_xml_stripped)

51

52 # convert the tree from the resulting txt file to a directory tree

53 txt2dir.createDirectories(dmoz_xml_stripped, target_dir, reduced_cats_file)

54

55 # remove the files created

56 try:

57 pass

58 os.remove(reduced_cats_file)

59 os.remove(dmoz_xml_stripped)

60 except:

61 pass

62

63 def fillDB(type=’dmoz_full’, path=’/opt/spree/data/Top_full’):

A.1 Quelltexte 78

64 ’’’

65 Loads the directory tree structure into the DB

66

67 @param type Defines the table which will be used

68 ’’’


70 taxLoader.loadTaxonomyWithoutDocs(path,type)

71

72

73 if __name__ == "__main__":

74 print "Loads the given dmoz ontology structure to\

75 the specified database table."

76 print "Usage: fulltree.py <dmoz category file> <dmoz ontology as xml file> <'ontology name> "

77

78 if len(sys.argv) > 3:

79 createOntology(sys.argv[1], sys.argv[2],sys.argv[3])

80 sys.exit(0)

dynOntologyTree.py


2 import cPickle,random,math

3

4 from sqlalchemy import *5 import nodereduction.db.model as m

6 from nodereduction.utils import dictutils

7

8 class Node:

9 ’’’

10 Represents a node in an ontology

11 ’’’

12 def __init__(self, row = None):

13 ’’’

14 Constructor

15 Populates self with the information given by row

16 ’’’

17 self.parent=None

18 self.children=[]

19

20 if row:

21 self.id = row.id

22 self.node_id = row.node_id

23 self.name = row.name

24 self.leftIdx = row.leftidx

25 self.rightIdx = row.rightidx

26 self.level = row.level

27 try:

28 self.data=cPickle.loads(row.data)

29 except:

30 self.data = {}

31

32 self.noExperts = 0

33

34 def addChild(self,newChildNode):

A.1 Quelltexte 79

35 ’’’

36 Adds newChildNode as a child to self

37 ’’’

38 self.children.append(newChildNode)

39 newChildNode.parent = self

40

41 def getAllChildrenIds(self):

42 ’’’

43 Returns a list containing all children node IDs

44 ’’’

45 children = []

46 for child in self.children:

47 children.append(int(child.id))

48 if len(child.children)>0:

49 children.extend(child.getAllChildrenIds())

50 return children

51

52 def isLeaf(self):

53 ’’’

54 Returns true if self is a leaf, false otherwise

55 ’’’

56 if self.children==[]:

57 return True

58 else:

59 return False

60

61 def isRoot(self):

62 ’’’

63 Returns true if self is root node, false otherwise

64 ’’’

65 return self.name == ’ROOT’;

66

67 def deleteNode(self):

68 ’’’

69 Deletes self

70 ’’’

71 del self

72

73 def getParents(self):

74 ’’’

75 Returns a list of all parents of the node (root is excluded)

76 ’’’

77 node = self

78 nodes = []

79 while True:

80 nodes.append(node)

81 if node.parent == None or node.parent.isRoot():

82 break;

83 node = node.parent

84

85 return nodes

86

87 def getFullPath(self):

88 ’’’

89 Returns a string with all parent names formatted in

A.1 Quelltexte 80

90 a directory path like manner e.g. /Computers/Programming

91 ’’’

92 nodes = []

93 nodes.extend(self.getParents())

94 nodes.reverse()

95

96 path = ""

97 for node in nodes:

98 path += node.name + "/"

99

100 return path

101

102 class OntologyTree(object):

103 ’’’

104 Represents an ontology tree

105 ’’’

106 def __init__(self, type):

107 ’’’

108 Constructor

109 ’’’

110 self.root = Node()

111 self.root.name=’ROOT’

112 self.root.parent=[]

113 self.root.children=[]

114 self.root.data={}

115 self.root.test={}

116 self.current=self.root

117 self.asDict = {}

118 self.query=[]

119 self.experts = {}

120 self.type = type

121 self.path2id = {}

122

123 def __del__(self):

124 ’’’

125 Removes the tree and its nodes from memory

126 ’’’

127 self.current=self.root

128

129 while self.root.children!=[]:

130 if self.current.children!=[]:

131 self.current=self.current.children[0]

132 else:

133 self.current.parent.children.remove(self.current)

134 node=self.current

135 self.current=self.current.parent

136 node.parent=None

137 node.deleteNode()

138

139 self.root.deleteNode

140 del self.current

141 self.q_subtree=[]

142 del self.q_subtree

143 self.q_subtree_real=[]

144 del self.q_subtree_real

A.1 Quelltexte 81

145

146 def formTreeWithoutData(self):

147 ’’’

148 Builds the tree structure based on the ontology

149 located in the db table defined by self.type.

150 Does not read any data.

151 ’’’

152 ont = m.node_tables[self.type]

153

154 rows = select([

155 ont.c.id,

156 ont.c.node_id,

157 ont.c.name,

158 ont.c.name_full,

159 ont.c.level,

160 ont.c.leftidx,

161 ont.c.rightidx],

162 order_by=[ont.c.leftidx]

163 ).execute()

164

165 row = rows.fetchone()

166 node = Node(row)

167 node.name = ’ROOT’

168

169 self.root = node

170 if row.name_full:

171 self.path2id[row.name_full] = row.id

172 current=node

173

174 for row in rows:


176

177 if row.name_full:

178 self.path2id[row.name_full] = row.id

179

180 while current.rightIdx < node.rightIdx:

181 current = current.parent

182

183 current.addChild(node)

184 current = node

185

186 self.addTreeDict(self.root)

187

188 def formTreeWithData(self):

189 ’’’



192 Assigns each node a bag of words (tf data).

193 ’’’


195

196 rows = select([

197 ont.c.id,

198 ont.c.node_id,

199 ont.c.name,

A.1 Quelltexte 82

200 ont.c.level,

201 ont.c.leftidx,

202 ont.c.rightidx,

203 ont.c.data.label(’data’)],


205 ).execute()

206

207 node = Node(rows.fetchone())


209


211

212 current=node

213





218


220 current = node

221


223

224 def formTreeWithTFIDFData(self):

225 ’’’



228 Assigns each node a bag of words (tfidf data).

229 ’’’


231

232 rows = select([

233 ont.c.id,

234 ont.c.node_id,

235 ont.c.name,

236 ont.c.level,

237 ont.c.leftidx,

238 ont.c.rightidx,

239 ont.c.data_tfidf.label(’data’)],


241 ).execute()

242

243 node = Node(rows.fetchone())


245


247

248 current=node

249





254

A.1 Quelltexte 83


256 current = node

257


259

260 def makeUnion(self, node = None):

261 ’’’

262 Propagates each nodes’ bag of words to its parents and

263 writes them to the db(column data_tfidf_merged).

264 ’’’

265 if not node:

266 node = self.root

267

268 table = m.node_tables[self.type]

269

270 len_data = len(node.data)

271 union = node.data

272


274 childdata = self.makeUnion(child)

275 union = dictutils.addDict(union, childdata)

276

277 union = dictutils.normalizeGeom(union)

278

279 if node.isRoot():

280 union = {}

281

282 u=table.update(table.c.id==node.id)

283 u.execute(data_tfidf_merged=cPickle.dumps(union))

284

285 return union

286

287 def findInSubTree(self,nodeName,head=None):

288 ’’’

289 Find a node by its name in a subtree with head as root.

290 ’’’

291 if head==None:

292 head=self.root

293 if (head.name!=nodeName):

294 for eachChild in head.children:

295 childSearchResult = self.findInSubTree(nodeName,eachChild)

296 if (childSearchResult!= None):

297 return childSearchResult;

298

299 else:

300 return head;

301 return None;

302

303 def findInSubTreeByNodeId(self,node_id,head=None):

304 ’’’

305 Find a node by its node_id in a subtree with head as root.

306 ’’’

307 if head==None:

308 head=self.root

309 if (head.node_id!=node_id):

A.1 Quelltexte 84

310 for eachChild in head.children:

311 childSearchResult = self.findInSubTreeByNodeId(node_id,'eachChild)

312 if (childSearchResult!= None):

313 return childSearchResult

314

315 else:

316 return head

317 return None

318

319 def addTreeDict(self, node = None):

320 """

321 Form a dictionary reprezentation of the tree

322 """

323

324 if not node:

325 node = self.root

326

327 if node.isRoot():

328 self.asDict[node.id] = node

329


331 self.asDict[child.id] = child

332 self.addTreeDict(child)

333

334 def choosePathPreWeighted(self, node, weighted_nodes, alpha=1000):

335 ’’’

336 Traverses the tree starting from the given node and

337 selects on each level the best nodes according to the

338 weights given by weighted_nodes. Best nodes on each level

339 are the ones with weight > mean + alpha * standard deviation.

340

341 @returns a list of nodes representing a subtree

342 ’’’

343 if len(node.children) == 0:

344 return []

345

346 children = node.children

347

348 distances = [weighted_nodes[n.id-1] for n in children]

349

350 for child in children:

351 child.weight = weighted_nodes[child.id-1]

352

353 if False and node.isRoot():

354 dic = {2:0.35, 36:0.05, 62:0.5, 95: 0.1}

355

356 m = sum(map(lambda x: x.weight * dic[x.id], children))

357 s = math.sqrt(sum(map(lambda x: math.pow(x.weight - m,2) * dic[x.id], 'children)))

358

359 else:

360 m = mean(distances)

361 s = sigma(distances)

362

A.1 Quelltexte 85

363 if len(distances) == 0:

364 threshold = m + alpha * s

365 else:

366 threshold = min(m + alpha * s, max(distances))

367

368 parentWeight = 0

369 if not node.isRoot():

370 parentWeight = node.weight

371

372 threshold = max([threshold, parentWeight])

373

374 best_children = filter(lambda x: x.weight >= threshold, children)

375

376 result = []

377

378 for child in best_children:

379 result.append(child)

380 result.extend(self.choosePathPreWeighted(child,weighted_nodes,alpha))

381

382 return result

383

384 def produceExpert(self, no_topics=3):

385 """

386 An expert, having expertise in ’no_topics’ nodes, is generated

387

388 @param no_topics determines in how many topics the expert is registered

389 """

390

391 expert_subtree=[]

392 empty=0

393 nids = self.asDict.keys()

394

395 while len(expert_subtree) < no_topics:

396 l = len(self.asDict)

397 r = random.randint(0,l-1)

398 node=self.asDict[nids[r]]

399 if node!=None and node.isLeaf():

400 expert_subtree.append(node)

401

402 expert_nodeids = []

403 for n in expert_subtree:

404 expert_nodeids.append(n.id)

405 l=n.getParents()

406 for node in l:

407 expert_nodeids.append(node.id)

408

409 return list(set(expert_nodeids))

410

411 def populateExperts(self, exp_number=1):

412 """

413 Populates exp_number experts

414 """

415

416 #an expert can be the expert in 5 topics at most

417 #assigning an expert a knowledge in x topics is a random process

A.1 Quelltexte 86

418 count=[]

419 for i in range(0,5):

420 count.append(0)

421

422 expert_count=0

423

424 self.experts = {}

425

426 for i in range(exp_number):

427 e_subtree=[]

428 r=random.randint(1,5)

429 count[r-1]+=1

430 e_subtree=self.produceExpert(r)

431

432 self.experts[expert_count] = e_subtree

433 expert_count +=1

434

435 return count

436

437 def addParents(self, node_ids):

438 ’’’

439 Adds all missing parent nodes to a list of nodes

440

441 @return: node set which results in a tree like structure of the given 'nodes

442 and all their parents

443 ’’’

444 subgraph_tmp = []

445 for id in node_ids:

446 subgraph_tmp.extend([n.id for n in self.asDict[id].getParents()])

447

448 return set(subgraph_tmp)

449

450 def nodeids2path(self,nodeids):

451 ’’’

452 Converts a list of nodeids to a list of node pathes

453

454 @param nodeids The node ids to be converted as a list

455 ’’’

456

457 pathes = []

458 for id in nodeids:

459 pathes.append(’/’ + self.asDict[id].getFullPath().strip(’/’))

460

461 return pathes

462

463 def path2nodeids(self, pathes):

464 ’’’

465 Converts a list of node paths to a list of node ids

466

467 @param pathes The full node pathes as a list

468 ’’’

469

470 ids = []

471 for path in pathes:

A.1 Quelltexte 87

472 if path in self.path2id:

473 ids.append(self.path2id[path])

474 else:

475 print ’Path not in tree: ’, path

476

477 return ids

ml

nodereducer.py


2

3 from nodereduction.ml.svd import lsi

4

5 import logging, sys

6 from numpy import *7

8 logging.basicConfig()

9 log = logging.getLogger(’NodeReducer’)

10 log.setLevel(logging.ERROR)

11

12 class NoConfigError(Exception):

13 pass

14

15 class NodeReducer:

16 ’’’

17 Provides methods to retrieve nodes sorted by relevance according to

18 either SVD or probabilistic approach

19 ’’’

20 PCA = 1

21 ENTROPY = 2

22 LSI = 3

23 PROB = 4

24 ACC = 5 #F1 measure

25 ACC_ADDING = 6

26

27 def __init__(self, method, config=None):

28 self.method = method

29 self.sortedNodes = None

30 if self.method == NodeReducer.LSI:

31 self.lsi_instance = lsi.LSI(config.queryLabels,config.nodes)

32

33 def calculateSortedNodes(self, config):

34 ’’’

35 Calculate the node importances and sort nodes by importance (asc). Use 'getNodes to retrieve the sorted nodes

36

37 @param config: the configuration file

38 ’’’

39 if self.method == NodeReducer.PROB:

40 tag2Occurrence = {}

41

42 for s in config.queryLabels:

A.1 Quelltexte 88

43 for t in s:

44 tag2Occurrence[t] = tag2Occurrence.get(t,0) + 1

45

46 sum_ = sum(tag2Occurrence.values())

47

48 nodes = []

49

50 for t in config.tags:

51 nodes.append([t,tag2Occurrence.get(t,0)])

52

53 nodes.sort(lambda x,y: cmp(x[1],y[1]))

54

55 self.sortedNodes = [n[0] for n in nodes]

56

57 if self.method == NodeReducer.LSI:

58 self.sortedNodes = self.lsi_instance.run(redLevel=config.redLevel)

59

60 def getSortedNodes(self, config=None):

61 ’’’

62 Returns all nodes sorted by importance (asc)

63

64 @return: list of nodes ids sorted by node importance

65 ’’’

66 if not config:

67 raise NoConfigError

68 self.calculateSortedNodes(config)

69 return self.sortedNodes

70

71 class LSIConfig:

72

73 def __init__(self, nodes, queryLabels, redLevel):

74 ’’’

75 @param nodes A list with node IDs. This nodes are to be reduced

76 @param querylabels List of lists: Inner lists represent queries, 'containing the node ids


78 @param redLevel The level of singular value reduction 0<= redLevel <=1, 1'means no reduction

79 ’’’

80 self.nodes = nodes

81 self.queryLabels = queryLabels

82 self.redLevel = redLevel

83

84 class PROBConfig:

85

86 def __init__(self, tags, query_labels):

87 ’’’

88 @param tags A list with node IDs. This nodes are to be reduced



91 ’’’

92 self.queryLabels = query_labels

93 self.tags = tags

A.1 Quelltexte 89

ml.svd

lsi.py


2

3 import sys, time

4 import numpy

5 from numpy import *6 from numpy.linalg import norm, svd

7 import logging

8 import cPickle as pickle

9

10 logging.basicConfig()

11 log = logging.getLogger(’LSI’)

12 log.setLevel(logging.ERROR)

13

14 class LSI:

15 def __init__(self, querylabels, tags):

16 ’’’

17 Constructor - Builds the data matrix from the given labeled queries

18



21 @param tags List of node IDs. These are the tags to be reduced

22

23 ’’’

24

25 self.tags = tags

26

27 query2count = {}

28

29 for query in querylabels:

30 query.sort()

31 qid = pickle.dumps(query)

32 query2count[qid] = query2count.get(qid,0) + 1

33

34 queryCount = len(query2count)

35

36 print ’\tInitializing LSA with %i compressed queries in a node space of %i 'dimensions’ % (queryCount, len(tags))

37

38 data = zeros((queryCount,len(tags)))

39

40 log.info(’Building data matrix...’)


42

43 q2c_items = query2count.items()

44 for idx in range(queryCount):

45 #query = querylabels[idx]

46 query = pickle.loads(q2c_items[idx][0])

47 for label in query:

48 if label in tags:

A.1 Quelltexte 90

49 data[idx,tags.index(label)] = q2c_items[idx][1]

50

51 del q2c_items

52 del query2count

53

54 # data has nodes in columns and queries in rows

55 self.training_data = data

56


58 print ’\tDone in %f s.’ % (end-start)

59

60

61 def run(self, redLevel=0.2):

62 ’’’

63 Perform LSI

64

65 @param redLevel The level of singular value reduction 0<= redLevel <=1, 1'means no reduction

66 ’’’

67

68 redLevelWasList = True

69 if not isinstance(redLevel,list):

70 redLevel = [redLevel]

71 redLevelWasList = False

72

73 print "\tPerforming LSI with %s singular values ..." % (str(redLevel))


75

76

77

78 data = self.training_data

79

80 [u,s,v] = svd(data,full_matrices=0)

81

82 uOrig = array(u)

83 sOrig = array(s)

84 vOrig = array(v)

85

86 alltopnodes = []

87

88 for red in redLevel:

89 #reduction by cutting singular values

90 th = sum(s) * red

91 cum = 0

92 for i in range(len(s)):

93 if cum>=th:

94 cutIdx = i

95 break

96 cum += s[i]

97 s[cutIdx:] = 0

98 u = u.transpose()

99 u[cutIdx:] = 0

100 u = u.transpose()

101 v[cutIdx:] = 0

102

A.1 Quelltexte 91

103 h = dot(diag(s),v)

104

105 # Compute approximation matrix

106 Ak = dot(u,h)

107

108 # Find most important nodes by computing the norm of each category vector

109 c = zeros(Ak.shape[1])

110 Akt = Ak.transpose()

111 for i in range(Ak.shape[1]):

112 #c[i] = norm(Akt[i])

113 c[i] = sum(Akt[i])/len(Akt[i])

114

115 c = nan_to_num(c)

116 sortidx = argsort(c)

117

118 topnodes = array(self.tags)[sortidx]

119

120 byRelevance = sorted(c)

121 byRelevance.reverse()

122

123 totalRel = sum(c)

124 rel = 0

125 for i in range(Ak.shape[1]):

126 rel += byRelevance[i]

127 if rel > totalRel*0.9:

128 print ’%s%% of relevance with %d nodes’ %(str(rel*100/totalRel),i')

129 break

130

131 u = array(uOrig)

132 s = array(sOrig)

133 v = array(vOrig)

134

135 alltopnodes.append(list(topnodes))

136


138 print ’\tDone in %f s.’ % (end-start)

139

140 if redLevelWasList:

141 return alltopnodes

142 else:

143 return alltopnodes[0]

ml.classifier

NaiveBayesLG.py


2

3 import math

4

5 class BayesClassifierLG(object):

6 ’’’

7 An implementation of the Naive Bayes classifier using Laplace smoothing

A.1 Quelltexte 92

8 ’’’

9 eps = 0.2

10 isLog = True

11

12 def __init__(self, id, features, overall_features):

13 self.id = id

14 self.length = sum(features.values()) + self.eps * len(overall_features)

15

16 self.features = features

17

18 def __repr__(self):

19 return ’<BayesDict: %s, %s tokens>’ % (self.id, len(self.features))

20

21 def getAbsoluteProbability(self, observations):

22 ’’’

23 Returns absolute probability according to the given observations

24 ’’’

25 prob = 0

26 for word, count in observations.items():

27 f = self.features.get(word,0)

28 if self.length > 0:

29 prob += count * math.log((f+self.eps)/self.length)

30

31 if prob == 0:

32 return -100000

33 return prob

db

model.py

1 ’’’

2 Provides an object represenation of the database tables

3 Creates all needed tables for the ontologies listed in settings.taxtypes

4 ’’’


6 from sqlalchemy import *7 import sqlalchemy.databases.mysql as mysql

8


10

11 connect_string = settings.connect_string

12 print connect_string

13 engine = create_engine(connect_string, echo=False, pool_size=25 ,max_overflow=50)

14

15 metadata = BoundMetaData(engine)

16

17 dmoz_tables = {}

18

19 ’’’ create dmoz tables ’’’

20 for type in settings.taxtypes:

21 table = Table(’dmoz_’+type, metadata,

22 Column(’id’, Integer, primary_key=True),

23 Column(’node_id’, Integer),

A.1 Quelltexte 93

24 Column(’url’, String(2000)),

25 Column(’text’, String(10000)),

26 Column(’bow’,mysql.MSLongText),

27 Column(’isTraining’, Integer, default=0)

28 )

29

30 table.create(checkfirst=True)

31 dmoz_tables[type] = table

32

33 node_tables = {}

34

35 ’’’ create nodes tables ’’’


37 table = Table(’nodes_’+type, metadata,


39 Column(’node_id’, String(50)),

40 Column(’leftidx’, Integer, unique = True),

41 Column(’rightidx’, Integer, unique = True),

42 Column(’name’, String(100), nullable = False),

43 Column(’name_full’, String(400)),

44 Column(’level’,Integer(2)),

45 Column(’no_results’,Integer),

46 Column(’data’,mysql.MSLongText),

47 Column(’data_merged’,mysql.MSLongText),

48 Column(’data_tfidf’,mysql.MSLongText),

49 Column(’data_tfidf_merged’,mysql.MSLongText)

50 )


52 node_tables[type] = table

53

54 doc_tables = {}

55

56 ’’’ create docs tables ’’’


58 table = Table(’docs_’+type, metadata,


60 Column(’node_id’, Integer, ForeignKey("nodes_"+type+".id"), nullable = False)',

61 Column(’url’, String(2000)),

62 Column(’data’,mysql.MSLongText),

63 Column(’data_tfidf’,mysql.MSLongText)

64 )


66 doc_tables[type] = table

67

68 term_tables = {}

69 ’’’ create terms tables ’’’


71 table = Table(’terms_’+type, metadata,

72 Column(’id’,Integer, primary_key=True),

73 Column(’term’, String(20), unique=True, nullable = False),

74 Column(’count’,Integer, default=0),

75 Column(’count_nodes’, Integer, default=0),

76 Column(’count_docs’, Integer, default=0),

77 Column(’idf’, Float, default=1.0),

A.1 Quelltexte 94

78 Column(’type’, String(1), default = ’N’),

79 Column(’data_tfidf’,mysql.MSLongText),

80 Column(’data_tfidf_merged’,mysql.MSLongText)

81 )


83 term_tables[type] = table

84

85 nodes2news_tables={}

86 ’’’ create nodes2news tables ’’’


88 table = Table(’nodes2news_’+type, metadata,

89 Column(’node_id’, Integer, ForeignKey("nodes_"+type+".id"), 'nullable = False),

90 Column(’news_id’, Integer, nullable = False),

91 Column(’isReal’, Boolean, default=True)

92 )


94 nodes2news_tables[type] = table

95

96 result_tables={}

97 ’’’ create results tables ’’’


99 table = Table(’results_’+type, metadata,

100 Column(’news_id’, Integer, unique=True),

101 Column(’bow_tfidf’,mysql.MSLongText),

102 Column(’ranked_nodes’, mysql.MSLongText),

103 Column(’ranked_nodes_cleaned’, mysql.MSLongText),

104 Column(’result’, mysql.MSLongText)

105 )


107 result_tables[type] = table

loader.py

1 import os, cPickle

2 from sqlalchemy import *3


5

6 from nodereduction.db import model, dataprovider

7 from nodereduction.tree import ontologytree

8 from nodereduction.extractor import extractor

9 from nodereduction.utils import dictutils, featurevector, dr

10

11 dmozurl_file = "www.out"

12

13 yahoourl_file = "yahoo.url"

14 yahoocrawl_ext = ".y.txt"

15

16

17 class SiteLoader(object):

18

19 def loadSites(self, type, base_dir, urlfile = yahoourl_file, min_term_number = 3)':

20 """

A.1 Quelltexte 95

21 Returns a dictionary of bag of words read from all sites listed

22 in urlfile. All sites are expected to be already crawled and

23 saved as files

24 """

25 sites= {}

26

27 urls = self.loadUrls(base_dir, urlfile)

28

29 bows = []

30

31 for url in urls:

32 if len(bows) >= settings.nbr_sites[type] and not urlfile == dmozurl_file:

33 break

34

35 filename = self.convertUrlToFilename(url, yahoocrawl_ext)

36 if not self.isValidFile(base_dir, filename):

37 continue

38

39 bow = extractor.file2Bow(base_dir, filename)

40 if len(bow) < min_term_number:

41 continue

42 bows.append({’url’:url,’data’:bow})

43

44 return bows

45

46 def loadUrls(self, base_dir, urlfile):

47 """

48 Returns all URLs contained in file "urlfile" as a list

49 """

50 filepath = os.path.join(base_dir, urlfile)

51

52 if not os.path.isfile(filepath):

53 return []

54

55 urls = [url.replace("\n","").replace("\r","") for url in open(filepath, "r")]

56

57 return urls

58

59 def convertUrlToFilename(self, url, ext):

60 ’’’

61 Converts an URL to a valid filename

62 ’’’

63 filename = url[7:]

64 filename = filename.replace("/","___")

65 endIdx = filename.find("?")

66 if endIdx != -1:

67 filename = filename[:endIdx]

68 filename += ext

69 return filename

70

71 def isValidFile(self, base_dir, filename):

72 ’’’

73 Determines if the given filename is valid

74 ’’’

75 filepath = os.path.join(base_dir, filename)

A.1 Quelltexte 96

76 if os.path.isfile(filepath) and os.path.getsize(filepath) > settings.'min_filesize and os.path.getsize(filepath) < settings.max_filesize:

77 return True

78 else:

79 return False

80

81 class TaxonomyLoader(object):

82 def __init__(self):

83 self.siteLoader = SiteLoader()

84 self.id_counter = 0

85

86 def loadTaxonomy(self, base_dir, type):

87 """

88 Starting point for writing the taxonomy structure and the related

89 documents to the DB.

90 """


92

93 node_table = model.node_tables[type]

94 node_table.delete().execute()

95 insert_nodes = node_table.insert()

96

97 doc_table = model.doc_tables[type]

98 doc_table.delete().execute()

99 insert_docs = doc_table.insert()

100

101 if ’dmoz’ in type:

102 model.dmoz_tables[type].delete()

103

104 self.loadNodesFromDirSub(type, base_dir, insert_nodes, insert_docs)

105

106 def loadNodesFromDirSub(self, type, base_dir, insert_nodes, insert_docs, count = '0, level=0):

107 """

108 Called from loadNodesFromDir(baseDir, loadData) recursivly goes through

109 all directories and adds each new directory as a node to the database

110 """

111 self.id_counter += 1

112

113 node = {}

114 node[’id’] = self.id_counter

115 if count == 0:

116 node[’name’] = "Root"

117 node[’node_id’] = ""

118 node[’name_full’] = "Root"

119 self.root_dir = base_dir.rstrip(’/’)

120 else:

121 node[’name_full’] = ’’.join(base_dir.split(self.root_dir)[1:])

122 foldername = os.path.split(base_dir)[1].split(’#’)

123 node[’node_id’] = foldername[0]

124 if len(foldername) < 2:

125 node[’name’] = foldername[0]

126 else:


128 node[’level’] = level

A.1 Quelltexte 97

129 node[’leftidx’] = count

130

131 for file in os.listdir(base_dir):

132 path = os.path.join(base_dir, file)

133 if os.path.isdir(path) and file.find(".svn") == -1:

134 count = self.loadNodesFromDirSub(type, path, insert_nodes, 'insert_docs, count + 1, level +1)

135

136 node[’rightidx’] = count +1

137

138

139 insert_nodes.execute(node)

140 print "%d. %s %s loaded." % (node[’id’],node[’name’],node[’name_full’])

141

142 urls = []

143

144 docs = self.siteLoader.loadSites(type, base_dir)

145 for doc in docs:

146 urls.append(doc[’url’])

147 doc[’node_id’] = node[’id’]

148 doc[’data’] = cPickle.dumps(doc[’data’])

149

150 if len(docs) > 0:

151 insert_docs.execute(docs)

152


154 docs = self.siteLoader.loadSites(type, base_dir, dmozurl_file)


156 #filter sites that are part of the training set

157 if doc[’url’] in urls:

158 continue


160 doc[’bow’] = cPickle.dumps(doc[’data’])

161

162 model.dmoz_tables[type].insert().execute(doc)

163

164 return count + 1

165

166 def loadTaxonomyWithoutDocs(self, base_dir, type):

167 """

168 Starting point for writing the taxonomy structure to the DB.

169 """


171


173 node_table.delete().execute()

174 insert_nodes = node_table.insert()

175


177 model.dmoz_tables[type].delete()

178

179 self.loadNodesFromDirSubWithoutDocs(type, base_dir, insert_nodes )

180

181 def loadNodesFromDirSubWithoutDocs(self, type, base_dir, insert_nodes, count = 0,'level=0):

A.1 Quelltexte 98

182 """

183 Called from loadNodesFromDir(baseDir, loadData) recursively goes through

184 all directories and adds each new directory as a node to the database.

185 """

186 self.id_counter += 1

187

188 node = {}

189 node[’id’] = self.id_counter

190 if count == 0:

191 node[’name’] = "Root"

192 node[’node_id’] = ""

193 node[’name_full’] = "Root"

194 else:

195 node[’name_full’] = ’’.join(base_dir.split(’/Top’)[1:])

196 foldername = os.path.split(base_dir)[1].split(’#’)

197 node[’node_id’] = foldername[0]

198 if len(foldername) < 2:


200 else:


202 node[’level’] = level

203 node[’leftidx’] = count

204

205

206 for file in os.listdir(base_dir):

207 path = os.path.join(base_dir, file)

208 if os.path.isdir(path) and file.find(".svn") == -1:

209 count = self.loadNodesFromDirSubWithoutDocs(type, path, insert_nodes,'count + 1, level +1)

210

211 node[’rightidx’] = count +1

212

213 insert_nodes.execute(node)

214 if int(node[’id’]) % 100 == 0:

215 print "%d. %s loaded. Name full: %s" % (node[’id’],node[’name’],node[’'name_full’])

216


218 durls = self.siteLoader.loadUrls(base_dir, dmozurl_file)

219 for url in durls:

220 doc = {}


222 doc[’url’] = url

223

224 model.dmoz_tables[type].insert().execute(doc)

225

226 return count + 1

227

228 def loadNodesFromSites(self, type):

229 ’’’

230 Adds data and data_tfidf column to the nodes table.

231 ’’’


233 node_ids = select([node_table.c.id]).execute()

234

A.1 Quelltexte 99


236

237 update = node_table.update(node_table.c.id==bindparam(’id’))

238

239 for row in node_ids:

240 node_id = row.id

241 vec = {}

242 tfdata = {}

243 docs = select([doc_table.c.data_tfidf, doc_table.c.data],doc_table.c.'node_id == node_id ).execute()

244


246 if doc.data_tfidf != None:

247 dictutils.addDict(vec,cPickle.loads(doc.data_tfidf))

248 dictutils.addDict(tfdata,cPickle.loads(doc.data))

249

250 tfdata.pop(’_count_’,0)

251 tfdata.pop(’_countStopwords_’,0)

252 vec = dictutils.normalizeGeom(vec)

253

254 update.execute({’id’:node_id, ’data_tfidf’:cPickle.dumps(vec), ’data’:'cPickle.dumps(tfdata)})

255

256 def loadNodesFromSitesReduced(self, type):

257 ’’’

258 Adds data and data_tfidf column to the nodes table.

259 Performs Feature Selection.

260 ’’’


262 node_ids = select([node_table.c.id]).execute()

263

264 terms2df_global = dataprovider.getTerms2DF(type)

265


267

268 no_docs = len([id for id in select([doc_table.c.id]).execute()])

269

270 update = node_table.update(node_table.c.id==bindparam(’id’))

271

272 terms2idf = dataprovider.getTerms2IDF(type)

273

274 for row in node_ids:

275 node_id = row.id

276 vec = {}

277 tfdata = {}

278 terms2df_local = {}

279

280 docs = select([doc_table.c.data],doc_table.c.node_id == node_id ).execute'()

281

282 no_docs_local = 0


284 no_docs_local += 1

285 data = cPickle.loads(doc.data)

286 data.pop(’_count_’,0)

A.1 Quelltexte 100

287 data.pop(’_countStopwords_’,0)

288

289 for w, value in data.items():

290 if w in terms2df_local:

291 terms2df_local[w] +=1

292 else:

293 terms2df_local[w] = 1

294 if w in vec:

295 vec[w] += value

296 tfdata[w] += value

297 else:

298 vec[w] = value

299 tfdata[w] = value

300

301 # Perform feature selection

302 reduced_bow = settings.dr_function[type](vec, terms2df_local, 'no_docs_local, terms2df_global, no_docs, settings.dr_nbr_terms, type)

303 reduced_bow_tfdata = settings.dr_function[type](tfdata, terms2df_local, 'no_docs_local, terms2df_global, no_docs, settings.dr_nbr_terms, type)

304

305 reduced_bow = featurevector.normalizeVector(reduced_bow, terms2idf)

306

307 update.execute({’id’:node_id, ’data_tfidf’:cPickle.dumps(reduced_bow), ’'data’:cPickle.dumps(reduced_bow_tfdata)})

308

309 def forwardTerms(self, type):

310 ’’’

311 Propagates terms contained in the data column of the nodes table

312 to to its nodes’ parents (fills data_merged column)

313 ’’’

314 print "Forwarding tf terms to parents ..."

315 ont_tree=ontologytree.OntologyTree(type)

316 ont_tree.formTreeWithData()

317

318 ont_tree.makeTFDataUnion()

319

320 ont_tree.__del__()

321 print "Done."

322

323 def forwardTermsTFIDF(self, type):

324 ’’’

325 Propagates terms contained in the data_tfidf column of the nodes table

326 to to its nodes’ parents (fills data_tfidf_merged column)

327 ’’’

328 print "Forwarding tfidf terms to parents ..."

329 ont_tree=ontologytree.OntologyTree(type)

330 ont_tree.formTreeWithTFIDFData()

331

332 ont_tree.makeUnion()

333

334 ont_tree.__del__()

335 print "Done."

336

337 class TermLoader(object):

338

A.1 Quelltexte 101

339 def loadTerms(self,type):

340 ’’’

341 Extract all terms contained in the documents in the document table

342 and store them in terms table besides additional information

343 (TF, DF, IDF)

344 ’’’

345

346 print "Deleting old term entries ..."

347

348 term_table = model.term_tables[type]

349 term_table.delete().execute()

350

351 print "Filling terms table with extracted words ..."


353 docs = select([doc_table.c.node_id, doc_table.c.data]).execute()

354

355 terms = dict()

356 docsPerTerm = dict()

357

358 no_docs = 0

359

360 # get all terms


362 no_docs += 1

363 doc_terms = cPickle.loads(doc.data)

364 if len(doc_terms) == 0:

365 continue;

366 dictutils.addDict(terms, doc_terms)

367

368 for term in doc_terms:

369 if term in docsPerTerm:

370 docsPerTerm[term] += 1

371 else:

372 docsPerTerm[term] = 1

373

374 print "Loaded %d terms" % len(docsPerTerm)

375 keys = terms.keys()

376 keys.sort()

377

378 inserts = []

379

380 i = term_table.insert()

381

382 # store all terms and their counters

383 for key in keys:

384

385 # store only terms up to a certain length and remove terms

386 # only used for management

387 if len(key) > 20 or key in ["_count_","_countStopwords_"]:

388 continue

389

390 inserts.append({’term’:key, ’count’:terms[key], ’count_docs’:docsPerTerm['key], ’idf’:featurevector.getIdf(docsPerTerm[key], no_docs)})


392 i.execute(inserts)

A.1 Quelltexte 102

393 inserts = []

394


396 i.execute(inserts)

397

398 try:

399 Index(’idx_term_’+type+’_term’, term_table.c.term).create()

400 except:

401 pass

402

403 def addNodes2Terms(self, type, data_column):

404 ’’’

405 Adds the nodes belonging to specific terms to the terms table

406 ’’’

407 print "Adding nodes to terms .... (%s)" %type , data_column,

408


410 nodes = select([node_table.c.id, node_table.c[data_column]]).execute()

411

412 dic = {}

413

414 no_nodes = nodes.rowcount

415

416 for node in nodes:

417 node_terms = cPickle.loads(node[data_column])

418 for term in node_terms:

419 if term in dic:

420 dic[term][node.id] = node_terms[term]

421 else:

422 dic[term] = {node.id: node_terms[term]}

423

424 updates = []

425

426 term_table = model.term_tables[type]

427 terms = select([term_table.c.id,term_table.c.term]).execute()

428

429 u = term_table.update(term_table.c.id==bindparam(’id’))

430 for row in terms:

431 data = {}

432 if row.term in dic:

433 data = dic[row.term]

434 updates.append({’id’:row.id, data_column:cPickle.dumps(data)})

435 if len(updates) > 1000:

436 u.execute(updates)

437 updates = []

438 print ".",

439

440 if len(updates) > 0:

441 u.execute(updates)