Knowledge Discovery in Databases, Teil III: Konzept Hierarchien in WUMprep

    02. April 2004 von Gebhard Dettmar

    Mit der Einführung in die grundlegenden Anwendungsbereiche und Methoden im ersten und dem Fokus auf die Datenaufbereitungsphase im zweiten Teil der Serie "KDD - Knowledge Discovery in Databases" sind die Voraussetzungen für die praktische Anwendung - die Wissensgenerierung bezüglich Kunden-/Nutzerverhaltens - geklärt. Entsprechend zeigt dieser Teil, wie mittels einer Kombination aus Semantic Web und Web Usage Mining sowohl die Datenaggregation mit Hilfe von Taxonomien und Konzepthierarchien sowie die abfragespezifische Analyse eines Webserver-Logs unter Einsatz der Mining-Tools WUMprep und WUM zur anschließenden Wissensgenerierung vonstatten zu gehen hat. Die Einbeziehung von Struktur und Semantik einzelner URLs in der Datenmodellierung verspricht eine neue Qualität der Musterentdeckung und erweitert somit die Methoden der Navigationsanalyse in diesem hochexpansiven Bereich. Die zugrundeliegende Methodik wird im folgenden an den Verhältnissen der c-o-k vorgestellt, die beschriebenen Eigenarten sind aber mutatis mutandis auf jedes themenspezifische Portal anwendbar.

    Problemstellung

    Die c-o-k ist ein nichtkommerzielles, themenbezogenes Informationsportal mit dem erklärten Ziel, "praxisorientiertes und qualifiziertes Wissen zum Thema Knowledge Management in Unternehmen" bereitzustellen. Der Schwerpunkt liegt dabei auf der Darstellung von "Einsatzmöglichkeiten und Leistungsfähigkeit aktueller Methoden, Techniken und Tools." Das Angebot ist somit stark inhaltsorientiert und besteht im wesentlichen aus Fachaufsätzen und Überblicken. Dieser Content-Bezug offenbart sich schon auf der Startseite - neben den üblichen Navigationshilfen werden dem Nutzer - sieht man von dem Forum ab - ausschließlich Artikel zum Anklicken geboten.

    Auch die Navigationshilfen rücken Content in den Vordergrund: Die am linken Seitenrand befindliche Bar präsentiert als erstes einen Content Pool, der Artikel in die Subkategorien Kontext = inhaltliche Zuordnung, und Rollen = anvisierte Zielgruppe des jeweiligen Themas unterteilt.

    Damit liegt es auf der Hand, auch die Analyse auf eben diesen Content zu fokussieren, da er den eigentlichen Inhalt der Seite und somit ihre eigentliche Daseinsbestimmung ausmacht. Da sich die Qualität eines Artikels nicht über URL-Strings wie cp_artikel.htm?artikel_id= ausmachen lässt, müssen solche Kriterien über eine Analyse ihrer Nutzung gewonnen werden: spiegelt sich die Ausrichtung im Abruf von Content behafteten URLs im Log wieder, nutzen die User die Seite gemäß ihrer Intention, tut sie es nicht, muss man auf mangelnde Akzeptanz schließen. Für weitergehende qualitative Bestimmungen könnte man das Web Structure Mining hinzuziehen, also klären, wer auf unsere Inhalte verlinkt, wer zitiert, bibliographiert usw. Hier sollen jedoch nicht Web Structure, Usage und Content Mining miteinander verzahnt, sondern das Usage Mining um einen semantischen Aspekt erweitert werden, um durch die Analyse der Abrufe einen vertieften Einblick in das Nutzungsverhalten zu erlangen [1].

    Doch zunächst zu den Fragen: Interessant sind v. a.:

    • Nutzerpfade von allgemeinen Navigationshilfen (wie Volltextsuche, Schlagwortregister/Index) zu Artikeln
    • Nutzerpfade von c-o-k-spezifischer Navigationshilfe (Kontext, Rollen) zu Artikeln,
    • Die Wahrnehmung der Inhalte gegenüber anderen Serviceangeboten,
    • Nutzungskon- oder divergenz verschiedener inhaltlicher Kategorien (lesen IT-Leiter nur Artikel über Werkzeuge oder auch Fallstudien/Methoden)

    Keine dieser Fragen lässt sich aus URL-Strings ablesen, daher schlagen Spiliopoulou und Pohle in [SP2000] [2] die Verwendung von Konzept Hierarchien vor, die URLs mit Semantik anreichern und so verschiedene Ebenen der Abstraktion ermöglichen: von "Suche -> Artikel" bis zu "Organisationsentwickler -> ERP im Wissensmanagement".

    Konzept Hierarchien und Taxonomien mit WUMprep

    Ein themenspezifisches Portal wie die c-o-k verfügt über eine bestimmte Struktur: es weist  einen übergeordneten Schwerpunkt, hier "Knowledge Management", auf, der sich in diverse Subkategorien verzweigt. Dazu gibt es bestimmte Sektionen, wie Tools oder den Content Pool, die sich ebenso in ihre je eigene Subkategorien verzweigen.

    Diese mutatis mutandis überall anzutreffende Struktur ist den Einträgen eines Webserverlogs jedoch nur in stark eingeschränktem Ausmaß anzusehen. Strings wie: /cp_artikel.htm?artikel_id=151 oder /s_tools.htm?fall=-11 " verraten zwar noch die Herkunft "Artikel = Content" oder Tools = Überblick" doch sämtliche Subkategorien, i.e. Werkzeuge, Fallstudien bei Artikeln oder CMS, DMS bei den Tools sind nicht einmal latent vorhanden, bzw. aus den Strings ablesbar. Damit lassen sich oben formulierte Fragen wie: auf welche Inhalte greifen IT-Leiter (= Nutzer, die als Einsiegspunkt /cp_.htm?fall=6 wählen; ob das tatsächlich alle IT-Leiter sind, ist für den Analysten völlig irrelevant) nicht beantworten.

    Diesem Umstand trägt das Analysetool WUMprep Rechnung, indem es über die üblichen, im 2. Teil dieser Serie beschriebenen Preprocessing-Tools, sc. Sessionizing, Robot- und Logfilter hinausgehende Features anbietet, unter denen hier vor allen anderen mapReTaxonomies.pl von Interesse ist.

    Dieses Script nutzt vom Analysten zu erstellende reguläre Ausdrücke, um URLs in semantisch aussagekräftige und somit abstrahierbare Strings zu verwandeln. In WUMprep existiert dazu die Datei regepr.txt, in welcher der User die URLs, deren Abruf ihn besonders interessiert, mit Bedeutung anreichert. Es stellt sich nun die Frage, wie weit er vernünftigerweise aggregiert, denn unterschiedliche Fragestellungen verlangen nach jeweils unterschiedlichen Aggregationstiefen.

    Ontologien

    Dazu muss er zunächst eine Ontologie erstellen, die sowohl Navigation als auch Inhalt und vor allem deren Beziehung zueinander abbildet. Für die c-o-k sieht eine Ontologie mit dem Fokus auf den Content-Abruf (= dem Ziel der Seite) so aus:

    Abbildung 1: Ontologie Content-Abruf

    Das Bild zeigt: von der Startseite sind Kontexte und Rollen zu erreichen. Diese wiederum unterteilen sich in die Subkategorien:

    Kontext

    Rollen

    Werkzeuge

    Organisationsentwickler

    Fallstudien

    Qualtitätsmanager

    Methoden

    IT-Leiter

     

    Personalentwickler

     

    WM Koordinator

    Tabelle 1: Kontexte/Rollen

    Der Artikel id=137 ist also inhaltlich als Werkzeug und in seiner Rolle für die Zielgruppe Organisationsentwickler, Qualitätsmanager, IT-Leiter und WM-Koordinatoren bestimmt deklariert, dies sind die 5 "Knotenpunkte", von denen aus auf ihn zugegriffen werden kann. Dazu war er eine bestimmte Zeit auf der Startseite, was in der Ontologie als gepunktete Linie erscheint. Weiterhin könnte man ihn noch über die Seiten Index, Suche und Autoren erreichen, allerdings nur unter vorheriger Eingabe inhaltlich relevanter Suchwörter, des Autornamens etc. Diese Art des Abrufs würde also zielgerichtetes Suchen voraussetzen, während er über "Werkzeuge" oder "Organisationsentwickler" auch Nutzern erschiene, die etwas anderes oder überhaupt nichts bestimmtes suchen. Die letzte Zugriffsmöglichkeit wäre von außerhalb z.B. über Google.

    Daraus ergeben sich 2 Möglichkeiten des Abrufs, die sich beide möglicher- aber nicht notwendigerweise unterscheiden: die herkömmliche Navigation über Volltextsuche und die c-o-k-spezifische über seitens der Redaktion vordefinierte Rollen und Kontexte. Die erste verlangt zielgerichtetes Suchen, die zweite schließt es nicht aus.

    Damit haben wir zwei Arten von URLs vor uns: Navigation und Inhaltsseiten, die Navigationsseiten unterteilen sich noch einmal in c-o-k-spezifische (Kontexte/Rollen) und allseits übliche (Volltextsuche).

    Solcherart Unterschiede machen sich Spiliopoulou/Pohle zu Nutze, indem sie, ausgehend von der Zielsetzung des Portals, die URLs des Logs in Action- und Target-pages unterteilen, wobei mit Action die Ermöglichung zielgerichteten Handelns, um den Zweck des Besuchs zu erreichen, gemeint ist, der - aus Anbietersicht - mit dem Zweck des Portalangebotes übereinzustimmen hat, und in dem Abruf einer Target-Seite bestünde. Bei der c-o-k wäre das ein Artikel, d.h., die Sequenz "Sitemap à Suche à Veranstaltungstermine" würde von mir als reine Action-Sequenz ohne Target-Seite, d.h. als eine "inactive session" interpretiert werden.

    Natürlich verzweigen sich diese beiden "children of the root node" weiter, der Charakter einer Webseite als gerichteter Graph wird in dieser Abbildung anschaulich:

    Abbildung 2: Service-based concept hierarchy, aus [SP01]

    Zweck einer solchen Unterteilung ist es, mit Blick auf das Anbieter-Ziel solche Action-Pages zu identifizieren, die signifikant häufig - oder umgekehrt selten - Target-Pages nach sich ziehen. Wir suchen somit nach Sessions Sa = Pa --> Pt (= Action-Page --> Target-Page) und identifizieren in den Resultaten besser oder schlechter geeignete Pa , indem wir ihre Konversionseffizienz berechnen: aus einer Gruppe von Navigationspfaden, die die Seite P und das Ziel T enthalten müssen, werden die Pfade durch die Anzahl der sessions geteilt, die die Seite P enthalten. Es handelt sich also, ähnlich wie in der Konfidenz beim Apriori-Algorithmus, um die bedingte Wahrscheinlichkeit des Consequens T aus Antecedens A, die man gewinnt, indem man die gesamte Regel, also die Zahl der Sessions, die Pa und Pt enthalten, durch den Support des Antecedens, also die Zahl der Sessions, die Pa enthalten, teilt.

    Dieses Verfahren lässt sich auf die ersten beiden o.g. Fragestellungen anwenden. Beide verlangen ein nur grob hierarchisches Konzept - und damit eine besonders hohe Aggregationstiefe.

    Dies wird deutlich, wenn man sich die letzte Fragestellung anschaut. Hier spielt der Inhalt der Artikel eine entscheidende Rolle und muss in der Taxonomie auftauchen. Ich muss daher in regexpr.txt in WUMprep jedem URL-String einen aussagekräftigen Namen zuteilen, z.B.

    OPEN_EIS \\/cp_artikel\\.htm\\?artikel_id=122

    Da die artikel ID noch nicht einmal etwas über einen Kontext oder eine Rolle, geschweige denn genaues bzgl. Inhalt verrät, muss ich alle id= durchgehen und mir einen semantisch aussagekräftigen Begriff ausdenken - ansonsten aber lediglich Metazeichen (s.u.) ausschalten. Bei der Unterteilung in Action- und Target-Pages dagegen muss ich reguläre Ausdrücke schreiben, die alle artikel- und artikel_d (=Druckversion) sowie pdf-Strings "matcht" und ihnen die Metabezeichnung "ARTIKEL" zuweisen - gleiches für Action-Pages.

    Da diese Artikelserie Anwendungsorientierung verfolgt, i.e. dem Leser die Anwendung der beschriebenen Tools, die Open Source und frei downloadbar sind, ermöglichen soll,  kommen wir an diesem Punkt nicht um einen kleinen Exkurs zu regulären Ausdrücken herum. Sie sind zugegebenermaßen nicht ganz trivial, aber extrem nützlich. Haben Sie sich aber einmal eingearbeitet und an ihre Nutzung gewöhnt, werden Sie nicht mehr wissen, wie Sie vorher ohne sie leben konnten ;-)

    Reguläre Ausdrücke

    Wer mit einem Computer arbeitet, benutzt reguläre Ausdrücke, ob er sich dessen bewusst ist oder nicht. Dabei ist der Begriff zunächst nicht sehr aussagekräftig. Er entstammt der formalen Algebra [3] und läßt sich am leichtesten mit "Suchmusterübereinstimmung" paraphrasieren. Denn es sind immer bestimmte Muster von Zeichen, die gesucht oder ersetzt werden müssen.

    Im Unix-Urgestein ed gab es einen Befehl, der Zeilen auf Suchmusterübereinstimmung prüfte: g/Regular Expression/p = global/Regular Expression/ Print. Daraus schrieb jemand ein eigenes Programm, das zum Klassiker bei allen, die reguläre Ausdrücke zu ihrer Arbeit brauchen, avancierte: grep. Anfangs eher limitiert (insb. bei den Metazeichen), erfuhr es zahlreiche Erweiterungen, namentlich in Form von egrep seitens des awk -Schöpfers Alfred Aho.

    Natürlich kann ein so weites Feld wie RegExpes, wie die gängige Abkürzung lautet, im Rahmen dieses Artikels nicht in extenso abgehandelt werden. Der Fokus wird im folgenden auf die Anforderungen, die die Erstellung von regexpr.txt in WUMprep stellen, beschränkt. Zur weiteren Lektüre sei Jeffrey Friedls wirklich sehr schön lesbares Buch ausdrücklich empfohlen - auch Dale Dougherty"s Klassiker "sed & awk" [4] ist in diesem Zusammenhang von hohem Nutzwert. 

    Metazeichen

    Das breite Spektrum an Metazeichen sind das eigentliche Nützliche in sed, grep, awk, Perl und allen Programmen, die reguläre Ausdrücke kennen. Sie ermöglichen es, die Auswahl an Suchmustern ganz den jeweiligen Bedürfnissen anzupassen, zu erweitern oder einzuschränken.

    Z.B. will ich im via regexpr.txt aufzubereitenden c-o-k-Log nicht nur den URL /cp_.htm?fall=2 durch FALLSTUDIEN im WUMprep-Log ersetzen, sondern gleichfalls /cp_.htm?sortieren=&fall=2&pos=25, bzw. 50 oder 22. Ich brauche also ein Suchmuster, das genau beide Zeichenfolgen trifft: bis /cp_.htm? sind sie identisch, dann soll sortieren=& auftauchen können (aber nicht müssen), dann geht es übereinstimmend mit fall=2 weiter, dann ist der erste String zu Ende, im zweiten folgen aber noch die Literale (=Zeichen, die genau das ausdrücken, wofür sie stehen, also das Gegenstück zu Metazeichen) &pos = irgendeine ein- oder zweistellige Zahl.

    Hierfür gibt es mehrere Möglichkeiten. Im einfachsten Fall muss man hier nur nach dem gemeinsamen Merkmal fall=2 suchen. Das setzt voraus, dass nicht in irgendeinem anderen URL diese Kennung auch verwendet wird, etwa s_autoren.htm?fall=2 o.ä. Da man die möglichen Strings seines Logs kaum auch nur annähernd kennt, muss man dies testen, etwa mit:

    awk "{print $7}" mylog |grep "fall=2" >test

    Allerdings ist das Resultat bei sehr großen Logs meist kaum noch überschaubar. Grundsätzlich sollte man nach der Maßgabe: "lieber etwas zu umständlich als zu einfach" verfahren, da sich alle Fehler im Preprocessing fortpflanzen: Das gemappte Log wird in WUM importiert, vordefinierten Algorithmen wie Apriori und eigenen Abfragen ausgesetzt. Falsches Mapping kann hier nicht mehr erkannt und korrigiert werden, unsinnige Resultate sind die notwendige Folge.

    Deshalb nimmt man in die Regex so viele Einschränkungen auf, wie man braucht:

    awk "{print $7}" mylog |awk "/cp_\\.htm\\?fall=2|sortieren=&fall=2&pos=[0-9]*/{print "FALLSTUDIEN",$1}" >test

    zeigt uns, ob das Ergebnis korrekt aussieht: awk "{print $7}" mylog vermeidet die Fußangel, Treffer aus der Referrer-Spalte ($11) zu erhalten, was z.B. bei

    1.kpmgconsulting.de - - [03/Feb/2003:04:33:31 -0700] "GET /css/styles.css HTTP/1.1" 200 7867 www.community-of-knowledge.de/cp_.htm

    der Fall wäre. Davon bekämen wir in test nur $7 = /css/styles.css zu Gesicht und würden uns wundern, warum der Ausdruck solchen Unsinn matcht.

    Nach der Pipe erfolgt der reguläre Ausdruck, bei dem zwischen dem Regex-Begrenzer in awk, / ... /, die Metazeichen ("." und "?") escaped werden müssen:

    /cp_\\.htm\\?fall=2|sortieren=&fall=2&pos=[0-9]*

    Entsprechend schreiben wir in die WUMprep-regexpr.txt:

    /cp_\\.htm\\?fall=2|sortieren=&fall=2&pos=[0-9]*

    Schaut man sich die Tabelle der Metazeichen, die als Zeichenbezeichner, Quantifizierer, Positionsbezeichner etc. auftreten können, an, wird schnell klar, wie obenstehende RegEx unser Ziel, zwei Zeichenketten mit nur geringfügigen Gemeinsamkeiten unter dem gleichen Begriff zu vereinen, erreicht:

      Metazeichen            passt auf

    .

    [...]

    [^...]

    \\Zeichen

    Punkt

    Zeichenklasse

    negierte Zeichenklasse

    escape

    beliebiges Zeichen

    Ein Zeichen aus der Liste

    keins der folgenden Zeichen

    einem Metazeichen vorgestellt macht es dieses zu einem Literal

    - Quantifizierer -

    ?

    *

    +

    {n,m}

    Fragezeichen

    Asterisk

    Plus

    expliziter Bereich

    keinmal oder einmal

    beliebig oft (0-∞)

    1-∞

    von min bis max

    - Positionsbezeichner -

    ^

    $

    \\<

    \\>

    Zirkumflex

    Dollar

    Wortgrenze

    Wortgrenze

    Zeilenanfang

    Zeilenende

    Wortanfang

    Wortende

    - Anderes -

    |

    (...)

    \\1, \\2, ...

    Alternation

    Klammern

    Referenzen

    eine der Alternativen

    Gruppierungen

    zählt Gruppierungen und buffert sie

    Tabelle 2 entn. aus Friedl, 2003, S. 29

    Verwandt wurden hier "|", "[...]" und *, an dessen Stelle auch {n,m}, möglich wäre. Doch zeigt die Tabelle auch, wie wir oben genannte Anforderung noch etwas eleganter, i.e. anforderungsnäher formulieren könnten:

    \\/cp_\\.htm\\?(sortieren=&)?fall=2(&pos=[0-9]+)?

    Alle Unterschiede stehen hier in runden Klammern, gefolgt von dem Quantifizierer "?", der der Regex-Maschine sagt: dieser String kann, muss aber nicht auftauchen.

    Konzept Hierarchien mit regulären Ausdrücken

    Reguläre Ausdrücke versetzen uns nun in die Lage, Konzept Hierarchien mit je nach Fragestellung unterschiedlicher Tiefe zu erstellen. Das bedeutet in WUMprep, verschiedene regexpr.txt-Dateien zu erstellen. Man beginnt mit der genauesten und daher leider mühseligsten  Variante: Jeder einzelne Artikel soll mit aussagekräftigen Titeln benannt werden. Hier bleibt uns nichts anderes übrig als jede einzelne URL zu benutzen und die Metazeichen ".", "?" und "/" zu escapen. Die so aufbereitete regexpr.txt sehen Sie hier.

    Hat man das hinter sich gebracht, kann man sich mit RegExes das Leben leicht machen: Unsere Action-Pages, die c-o-k-spezifischen oder allgemein üblichen Navigationsseiten und die Target-pages, die Artikel, erhalten je eigene regexpr.txt, bzw. nach Interessenlage kombinierte Variationen. Für die Frage: welche Action-Pages ermöglichen zielgerichteten Artikel-Abruf besonders gut, bzw. schlecht, brauchen wir Action Pages mit genauen Bezeichnern, für die Target-Pages dagegen reicht "ARTIKEL" völlig. Diese regexpr.txt kreieren wir so:

    grep "s_index[1-2]|fall=[1-8]|glossar" regexpr.txt >regnavTarg

    Damit sind alle Action-Pages in einer Datei. Fehlen noch die Artikel, aber ohne ihre aussagekräftigen Titel, die für diese Fragestellung ja keine Rolle spielen, stattdessen z.B. als TARGETPAGE

    awk "/artikel(_d)?/{print "TARGETPAGE",$2}" regexpr.txt >>regnavTarg

    Jetzt muss man nur noch mapReTaxonomies.pl über seine jeweiligen regexpr.txt laufen lassen und erhält in WUM importierbare, gemappte Logs, die in WUM gemäß ihrer zu Grunde liegenden Konzept Hierarchie abfragbar ist.

    Dies wird konkret im nächsten und letzten Teil der Serie vorgeführt

    Endnoten

    [1] S. dazu Bettina Berendt, Andreas Hotho, Gerd Stumme, Towards Semantic Web Mining, in: International Semantic Web Conference (ISWC02), 2002., 264-278, 271f.

    [2] M. Spiliopoulou and C. Pohle. Data mining for measuring and improving the success of web sites. Data Mining and Knowledge Discovery, 5:85--14, 2001.

    [3] Näheres bei Jeffrey Friedl, Reguläre Ausdrücke, Köln 1998, S. 64ff.

    [4] Dale Dougherty, sed & awk, O"Reilly & Associates, USA 19972

    Literatur

    • Bettina Berendt, Andreas Hotho, Gerd Stumme, Towards Semantic Web Mining, in: International Semantic Web Conference (ISWC02), 2002., 264-278.
    • M. Spiliopoulou and C. Pohle. Data mining for measuring and improving the success of web sites. Data Mining and Knowledge Discovery, 5:85--14, 2001
    • Jeffrey Friedl, Reguläre Ausdrücke, Köln 1998.
    • Dale Dougherty, sed & awk, O"Reilly & Associates, USA 19972.

Kommentare

Das Kommentarsystem ist zurzeit deaktiviert.