Webseiten-Personalisierung für anonyme Besucher

Inhaltsverzeichnis

1 Einleitung

I Theoretische Grundlagen
2 Web Log Mining
2.1 Data Mining
2.1.1 Klassi kation
2.1.2 Clustering
2.1.3 Assoziationsregeln
2.1.4 Sequentielle Muster
2.1.5 Anwendungsgebiete
2.2 Inhalt von Log les
2.3 Preprocessing von Web Logs
2.3.1 Säubern der Logdatei
2.3.2 Identi kation von Usern
2.3.3 Identi kation von Sessions
2.3.4 Alternative: Sammeln von Logdaten auf Clientseite
2.4 Repräsentation von Web Logs
2.4.1 n -dimensionaler binärer Attributvektor
2.4.2 n -dimensionaler Pageview-Referenz Vektor
2.4.3 Sequenz von Seitenaufrufen
2.4.4 Dateiformat One Session Per Line
2.4.5 Datenbankrepräsentation
2.5 Web Log Analyse
2.5.1 Assoziationsregeln und Frequent Itemsets .
2.5.2 Clustering und Klassi kation
2.5.3 Sequentielle Muster
2.5.4 Identi kation interessierter Benutzer
2.6 Web Log Mining Software
3 Personalisierung und Benutzermodellierung
3.1 Ursprung
3.2 Personalisierung im Internet
3.3 User Modelling für Personalisierung
3.3.1 Abgrenzung Benutzermodell - Benutzerpro l
3.3.2 Customer Pro le Life Cycle
3.3.3 Daten und Datenquellen
3.3.4 Repräsentation von User Modellen
3.4 Klassi kation von Personalisierungsansätzen
3.4.1 Verwendete Pro le
3.4.2 Art der Wissensakquisition
3.4.3 Art der verwendeten Informationen
3.4.4 Memory Based oder Model Based
3.4.5 Ort der Personalisierung
3.4.6 Gültigkeitsdauer eines Modells
3.4.7 Transparenz
3.5 Personalisierungstechniken
3.5.1 Content Based Filtering
3.5.2 Traditionelles Collaborative Filtering
3.5.3 Modellbasierte Techniken
3.5.4 Regelbasierte Personalisierung
3.5.5 Navigationsbasierte Techniken
3.5.6 Zielorientierte Benutzermodellierung
3.5.7 Hybride Ansätze
3.5.8 Personalisierte Websuche
3.6 Personalisierung für anonyme Besucher
4 Kategorisierung von Webseiten
4.1 Manuelle vs. Automatische Klassi kation . .
4.2 Regelbasierte Klassi kation
4.2.1 Vorgehensweise
4.2.2 Automatisches Lernen von Klassi kationsregeln
4.3 Collaborative Tagging
4.4 Resümee: Welcher Ansatz?

II Praktischer Teil
5 Konzept
5.1 Motivation
5.2 Datenquellen
5.3 Festlegen und Zuweisen von Dimensionen
5.4 Ermitteln von Interesse
5.5 Aufbau des Benutzerpro ls
5.6 Vorhersage von Seiten und Interessen
5.7 Einordnung des Ansatzes
6 Personalisierungssoftware w.w.w. Pro ler
6.1 Systemarchitektur - Übersicht
6.2 Import von Log les
6.2.1 Unterstützte Formate
6.2.2 Filterungsmechanismus
6.2.3 Identi kation von Usern und Sessions
6.2.4 Datenbank-Repräsentation des Web Logs
6.3 Die Classi er-Komponente
6.3.1 De nition von Interessens-Dimensionen
6.3.2 Identi kation relevanter Navigationspfade und Seiten
6.3.3 Taggen von Seiten / Pfaden
6.4 Analysekomponente
6.4.1 Seiten-Statistiken
6.4.2 Pfad-Statistiken und Assoziationsregeln
6.5 Export von Sessiondaten
6.5.1 Navigationsebene
6.5.2 Taskebene
6.6 De nition personalisierter Hinweise
6.7 Kon gurationsdatei
6.8 Online-Personalisierungskomponente
6.9 Erweiterungsmöglichkeiten
6.9.1 Schnittstelle zur CW Advisor Suite
6.9.2 Clustering
6.9.3 Automatische Kategorisierung von Webseiten
7 Anwendungsszenarien und Beispiele
7.1 Analyse von Benutzerverhalten
7.2 Empfehlung interessanter Seiten
7.3 Personalisierte Hinweise
7.4 Vorhersage von Interessen
7.5 Parametrisierung eines virtuellen Beraters
8 Zusammenfassung und Ausblick
A Datenbankmodell

Danksagung

Ich bedanke mich bei allen, die mich im Rahmen dieser Arbeit unterstützt ha- ben: Bei meinen KorrekturleserInnen Dagmar Schmid und Thomas Kruggel sowie bei Markus Unterleitner und Erich Teppan für die umfangreichen Tests der von mir entwickelten Software und ihre zahlreichen nützlichen Anregungen. Herzlichen Dank an Robin Burke für die Bereitstellung nicht frei zugänglicher Literatur. Mein besonderer Dank gilt dem Betreuer und Begutachter dieser Arbeit, Alexander Felfernig, für seine Hinweise in vielen Diskussionen, seine Hilfe bei der Literatur- recherche, das wertvolle Feedback und seine ständige Erreichbarkeit und O enheit für Fragen.

Zusammenfassung

Im Laufe der letzten Jahre hat sich das World Wide Web von einem statischen zu einem Web dynamischer Inhalte gewandelt. Unterschiedliche, zur gleichen Zeit surfende Besucher der selben Webseite sehen nicht zwangsläu g die gleichen Inhal- te. Der präsentierte Content ist in vielen Fällen adaptiv , das heiÿt er richtet sich danach, was die Webseite über den jeweiligen Besucher weiÿ . Als Basis für die so genannte Personalisierung von Webseiten dienen Benutzermodelle. Diese werden in der Regel langfristig aufgebaut und erfordern eine vorherige Registrierung des Besuchers. Der Besucher, dem personalisierte Inhalte präsentiert werden, ist dem System bekannt; für anonyme Besucher stehen personalisierte Inhalte gewöhnlich nicht zur Verfügung.

In dieser Diplomarbeit wird zunächst der aktuelle state of the art im Bereich Personalisierung und Benutzermodellierung zusammengefasst und ein Überblick über die Gebiete Web Log Mining und Webseiten-Kategorisierung gegeben. Der zweite Teil der Arbeit beschreibt einen neuen Personalisierungsansatz, der auf den bestehenden Konzepten basiert und diese erweitert. Konkret erstellt das entworfe- ne Konzept kurzfristige, implizite Benutzermodelle von unbekannten Besuchern auf Basis ihres Navigationsverhaltens und unter Einbeziehung von Webseiten- Metadaten ( Annotationen ). Damit ist es möglich, Inhalt und Präsentation ei- ner Webseite an die Interessen des Besuchers anzupassen - selbst wenn es sich bei ihm um einen anonymen, nicht registrierten Besucher handelt. Im Rahmen des Forschungsprojekts COHAVE¹ (Consumer Behavior & Decision Modeling for Recommender Systems) wurde ein Software-Tool implementiert, das den entwor- fenen Personalisierungsansatz umsetzt und zusätzlich über Analysefunktionalitä- ten für serverseitige Web Logs verfügt. Der Funktionsumfang des Tools und das entwickelte Personalisierungskonzept werden anhand konkreter und möglicher An- wendungsszenarien vorgestellt. Zusätzlich wird illustriert, wie die durch den neuen Ansatz implizit erstellten Benutzerpro le dafür genutzt werden können, die Be- nutzerfreundlichkeit wissensbasierter Recommendersysteme zu steigern.

Abstract

Over the past few years the World Wide Web has changed from a static web to a web with dynamic contents. Two visitors of the same web page do not necessarily see the same things. The contents presented to a visitor depend in many cases on what the web site knows about her/him. User models are build to enable this so called Personalization of web sites. These models are usually created in the long term and require a previous registration of the visitor on the system. That means that a user who sees personalized content is well-known by the system. Personalized content is generally not available for unknown users. This master thesis summarizes the state of the art in user modeling and website personalizati- on. Furthermore it delivers an insight to the areas of web log mining (web usage mining) and website categorization. The main achievement of this Master Thesis is the development of an approach which builds up short-term, implicit user models of anonymous visitors based on their navigational history and metadata related to the visited pages. The developed techniques enable the adaptation of websites for unknown, unregistered visitors according to their current interests. The ap- proach was implemented through the development of a software tool within the COHAVE[2] (Consumer Behavior & Decision Modeling for Recommender Systems) research project. The software tool is also described in this thesis together with the personalization concept, concrete applications and possible future extensions.

Einleitung

Um sich ihren Besuchern bestmöglich zu präsentieren, setzen Firmen bei Websei- ten im E-Commerce-Bereich längst nicht mehr auf statische Inhalte. Viel mehr sind die gezeigten Inhalte dynamisch und richten sich nach den Informationen, die Webseiten über ihre Besucher besitzen. Diese Informationen sind in so genannten Benutzerpro len (User Pro les) gespeichert. Benutzerpro le setzen in der Regel voraus, dass sich Benutzer am System registrieren. Im Zuge der Registrierung wer- den neben Stammdaten (z.B. Kontaktdaten und Bankverbindung) auch bestimmte Interessen und Merkmale, die den Benutzer charakterisieren, erhoben und im Be- nutzerpro l gespeichert. Aufgrund des (Kauf-)Verhaltens eines Benutzers kann die- ses Pro l verfeinert und für die personalisierte Darstellung von Inhalten verwendet werden. Diese Arbeit fasst bestehende Personalisierungsmechanismen zusammen und widmet sich des Weiteren der Fragestellung, wie Webseiten für nicht registrier- te, unbekannte Benutzer personalisiert werden können. Zu diesem Zweck wurde im Rahmen dieser Diplomarbeit ein neues Konzept entwickelt, das die Personalisie- rung von Webseiten für unbekannte Besucher vornimmt. Die dafür notwendigen Benutzermodelle werden aus dem Navigationsverhalten des jeweiligen Benutzers und aus Metainformationen über die von ihm besuchten Seiten abgeleitet.

Die Arbeit ist in einen theoretischen und praktischen Teil gegliedert und wie folgt organisiert: Der theoretische Teil gibt einen Überblick über den State of the Art in den Bereichen Web Log Mining, User Modelling und Webseitenkategorisier- ung. In Kapitel 2 werden verschiedene Web Log Mining Techniken und existierende Anwendungen vorgestellt. Kapitel 3 widmet sich unterschiedlichen Personalisie- rungsmöglichkeiten und dem Thema User Modelling. Um Pro le aufgrund der besuchten Webseiten erstellen zu können, ist es notwendig, die Webseiten vorher in Kategorien einzuteilen bzw. sie mit geeigneten Metadaten zu versehen. Kapitel 4 behandelt diesen Punkt und zeigt auf, wie Webseiten anhand von Metainfor- mationen, aber auch anhand anderer Gesichtspunkte verschiedenen Kategorien zugeordnet werden können. Im praktischen Teil wird schlieÿlich ein Konzept prä- sentiert, das im Rahmen dieser Arbeit entworfen wurde und die Grundlage für die Personalisierung von Webseiten für anonyme Besucher bildet (Kapitel 5). Ka- pitel 6 beschreibt ein Software-Tool, das dieses Konzept umsetzt und neben der Personalisierungsfunktionalität für anonyme Besucher auch verschiedene Analy- semöglichkeiten von aus Web Logs extrahierten Navigationspfaden bietet. Erwei- terungsmöglichkeiten des Tools bezüglich automatischer Klassi kation von Web- seiten und Clustering von Sessions werden skizziert; auÿerdem wird gezeigt, wie die entwickelte Software ein bestehendes wissensbasiertes Recommendersystem unter- stützen und verbessern kann. Kapitel 7 enthält einige Anwendungsszenarien und Beispiele für Anwendungsgebiete der Software. Am Ende folgt eine Zusammenfas- sung samt Ausblick.

Teil I Theoretische Grundlagen: Status Quo der Forschungsarbeiten in den Bereichen User Modelling, Personalisierung, Web Log Mining und Webseiten-Kategorisierung.

2 Web Log Mining

Web Server protokollieren, wenn sie entsprechend kon guriert sind, alle Anfragen, die an sie gestellt werden. Die protokollierten Informationen werden in der Regel in Log les geschrieben (man spricht auch von serverseitigen Logdateien oder Web Logs ). Die Analyse dieser Log les mit verschiedenen Data Mining Techniken wird Web Log Mining oder Web Usage Mining genannt. Der erste Abschnitt dieses Kapitels beinhaltet daher einen Überblick über relevante Data Mining Techniken; danach werden Inhalt, Auswertungsansätze und Repräsentationsmöglichkeiten für Web Logs beschrieben.

2.1 Data Mining

Unter Data Mining versteht man das Extrahieren von implizitem, zuvor unbekann- tem Wissen aus Datenmengen auf nicht triviale Art und Weise [13]. Eine andere De nition sieht Data Mining als das Erkennen von Mustern und Zusammenhängen in groÿen Datenmengen, aus denen ein - meistens wirtschaftlicher - Vorteil gezo- gen werden kann [77]. Data Mining läuft automatisch oder zumindest teilweise automatisch ab. Voraussetzung ist in jedem Fall, dass die zu analysierende Daten- menge in einer strukturierten und hochqualitativen Form vorliegt. Deshalb sind möglicherweise Verarbeitungsschritte notwendig, die vor jeglichem Data Mining Prozess durchgeführt werden müssen [60]. Als bedeutendste Data Mining Techni- ken gelten Klassi kation, Clustering, Assoziationsregeln und sequentielle Muster. Sie werden im folgenden erklärt.

2.1.1 Klassi kation

Unter Klassi kation versteht man jenen Prozess, der anhand bestimmter Kriterien (Klassi kationsmodell, [13] ) einzelne Instanzen einer Datenmenge zuvor de nier- ten Gruppen zuweist. Grundsätzlich unterscheidet man zwischen deduktiven und induktiven Ansätzen. Deduktive Ansätze haben ein vorgegebenes, in der Regel manuell erstelltes Klassi kationsmodell - z.B. Klassi kationsregeln oder Entschei- dungsbäume [18] - und führen die Klassi kation anhand dieses Modells durch. Abbildung 2.1 zeigt einen beispielhaften Entscheidungsbaum, der aus vorhande- nen Wetterdaten ableitet, ob eine bestimmte Aktivität durchgeführt werden kann (positiv, Klasse P) oder nicht (negativ, Klasse N)[59]. Ein Entscheidungsbaum ist

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Beispielhafter Entscheidungsbaum aus[59]

eine spezielle Repräsentationsform von Klassi kationsregeln und kann deshalb im- mer auch als Menge von Klassi kationsregeln dargestellt werden und umgekehrt.

Eine der fünf Regeln im dargestellten Baum ist folgende:

(Klasse, N) : − (outlook, sunny ) , (humidity, high ) .

Jeder Pfad im Entscheidungsbaum zwischen Wurzel (outlook ) und Blättern (P, N) entspricht einer Klassi kationsregel.

Induktive Ansätze lernen Klassi kationsregeln bzw. Entscheidungsbäume automatisch aus einem so genannten Training Set, das aus bereits klassi zierten positiven und negativen Beispielen besteht. Sind geeignete, in sich nicht widersprüchliche Trainingsdaten vorhanden, so ist es immer möglich, einen Entscheidungsbaum zu erzeugen, der alle Items des Training Sets korrekt klassi ziert. Gewöhnlich gibt es viele korrekte Entscheidungsbäume für ein Training Set. Die Herausforderung beim Induzieren von Entscheidungsbäumen liegt jedoch darin, auch möglichst viele unbekannte Items korrekt zu klassi zieren. Dazu sind im Allgemeinen einfache Bäume geeigneter als komplexe Bäume, die zwar das Training Set perfekt erklären , aber für unbekannte Items ungenauer sind.[59]

Für das Induzieren guter Entscheidungsbäume - also solcher, die sowohl bekann- te als auch unbekannte Items zu einem groÿen Teil korrekt klassi zieren, existieren einige Techniken. Denkbar ist z.B., alle möglichen Bäume für ein Training Set zu berechnen und den einfachsten auszuwählen. Die hohe Anzahl möglicher Bäume beschränkt die Anwendbarkeit dieses Ansatzes auf kleine Datenmengen. ID3 ist ein Algorithmus, der mit relativ geringer Berechnungszeit auch in einer groÿen Datenmenge einen guten (aber selten einen optimalen) Entscheidungsbaum er- zeugt. ID3 unterliegt einer iterativen Struktur: Eine Teilmenge des Training Sets (Fenster bzw. Window ) wird zufällig ausgewählt und daraus ein Baum abgeleitet, der alle Items innerhalb des Fensters korrekt klassi ziert. Danach werden alle Ob- jekte des Training Sets unter Verwendung dieses Baums klassi ziert. Wurden alle Objekte korrekt klassi ziert, so ist der Baum für das gesamte Training Set korrekt und der Algorithmus terminiert. Andernfalls wird dem Fenster eine Auswahl der falsch klassi zierten Objekte hinzugefügt und daraus ein neuer Baum abgeleitet. Theoretisch ist es zwar möglich, dass dadurch das gesamte Training Set nach und nach in das Fenster aufgenommen wird, die Praxis hat allerdings gezeigt, dass auch in groÿen Datenmengen (Training Sets mit bis zu 30.000 Objekten und bis zu 50 Attributen) bereits nach einigen wenigen Iterationen ein korrekter Baum gefunden wird.[59]

Ein bekanntes Beispiel für das Induzieren von Klassi kationsregeln ist der im weit verbreiteten Email-Clienten Mozilla Thunderbird integrierte Spam l- ter. Dieser nutzt unter anderem auch die Möglichkeit, Regeln für Spam-Emails und Nonspam-Emails zu lernen: Der Benutzer hat die Möglichkeit, eingehende Emails einer dieser beiden Klassen zuzuweisen. Anhand der manuellen Klassi kation ausgewählter Emails (= Training Set) leitet der Spam lter Regeln ab, aufgrund welcher er neu eingehende Emails klassi ziert.

2.1.2 Clustering

Clustering ist ebenfalls ein Verfahren zur Gruppierung von Datenmengen. Die In- stanzen einer Gruppe sollen sich dabei möglichst ähnlich sein (Homogenität) und die Gruppe selbst sich klar von anderen Gruppen unterscheiden (Heterogenität) [74]. Je nach Clustering-Verfahren kann eine Instanz mehreren Clustern zu einem bestimmten Grad (Fuzzy Clustering, [78] ) oder nur einem Cluster (Partitionie- rendes Clustering ) angehören [77]. Im Gegensatz zur Klassi kation werden die Gruppen nicht a priori festgelegt, sondern erst während des Clustering-Vorgangs de niert. Man bezeichnet Clustering auch als das Suchen nach natürlichen Gruppen oder als unbeaufsichtigte Klassi kation (unsupervised classi cation )[13]. Prinzipi- ell bestehen Clustering-Vorgänge aus zwei Schritten (vgl.[38] ):

1. Berechnung von Abständen zwischen den Objekten der zu analysierenden Datenmenge auf Basis eines Ähnlichkeitsmaÿes bzw. Abstandsmaÿes. Die am häu gsten verwendete Metrik ist der Euklidische Abstand : Seien die Objekte x und y bestimmt durch die Koordinaten x = (x 1 , ..., xn) und y = (y 1 , ..., yn).

Der Euklidische Abstand zwischen x und y wird dann wie folgt berechnet:

Abbildung in dieser Leseprobe nicht enthalten

Eine Übersicht über weitere Ähnlichkeitsmaÿe ndet sich in[78].

2. Zusammenfassung einzelner Objekte zu möglichst homogenen Teilgruppen. Dafür existieren verschiedene Ansätze, die sich im wesentlichen in die Kate- gorien partitionierendes und hierarchisches Clustering [27] einteilen lassen. Abhängig vom jeweiligen Verfahren kann nicht nur die maximale Ähnlichkeit innerhalb einer Gruppe, sondern auch die Maximierung der Heterogenität zwischen den einzelnen Gruppen im Mittelpunkt stehen[38].

Als Beispiel sei der k -means Clustering-Algorithmus genannt. Dabei handelt es sich um ein partitionierendes Verfahren, das wie folgt de niert ist[27]:

1. Bestimme k verschiedene Clusterzentren. Dabei handelt es sich um zufällig ausgewählte Datenpunkte oder Items in der Datenmenge.
2. Weise jedes Item dem Cluster mit dem nächstgelegenen Clusterzentrum zu.
3. Berechne die Clusterzentren aus den aktuellen Mitgliedern der Cluster neu.
4. Wird ein bestimmtes Konvergenz-Kriterium nicht erfüllt, gehe zu Schritt 2. Andernfalls stoppt der Algorithmus. Ein typisches Konvergenzkriterium ist z.B., dass es keine oder nur geringe Änderungen in den Clustern gibt.

Abbildung 2.2 zeigt die Funktionsweise des Algorithmus in einem einfachen Bei- spiel mit fünf Items, zwei Dimensionen und zwei Clustern. Die kreisrunden Punkte

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Funktionsweise des k -means Clustering Algorithmus

sind Items, die Clusterzentren werden durch Quadrate dargestellt. Detaillierte Beschreibungen anderer Ansätze sowie konkrete Implementierungen können in der Literatur [23, 27, 78] nachgelesen werden.

2.1.3 Assoziationsregeln

Assoziationsregeln[2] spüren Muster in Datenmengen in der Form von WENN- DANN-Regeln auf. Analysiert man groÿe Datenmengen, kann es aufschlussreich sein, Assoziationen zwischen der Präsenz eines Items und der Präsenz eines anderen Items in Transaktionen aufzuspüren. Assoziationsregeln haben die Form

Abbildung in dieser Leseprobe nicht enthalten

Im Kontext von Web Log Mining dienen Assoziationsregeln unter anderem dazu, vom Besuch einer bestimmten Webseite innerhalb einer Session auf den Besuch einer anderen Webseite zu schlieÿen. Um die Qualität einer Assoziationsregel zu messen, stehen zwei Werte zur Verfügung: Der Con dence-Wert und der SupportWert (vlg.[77] ). Conf idence steht für die Wahrscheinlichkeit, mit der die Regel zutri t und ist wie folgt de niert:

Abbildung in dieser Leseprobe nicht enthalten

Support sagt aus, wie viele Transaktionen alle in der Regel vorkommenden Elemente enthalten und ist wie folgt de niert:

support (A ⇒ B) = P (A ∪ B)

Ein einfaches Beispiel: 100 Besucher haben die Homepage der Organisation xy besucht. 50 von ihnen haben die Webseite A.htm, 30 die Webseiten A.htm und B.htm besucht. Daraus ergeben sich folgende Wahrscheinlichkeiten:

Abbildung in dieser Leseprobe nicht enthalten

Confidence wird nun berechnet mit

Abbildung in dieser Leseprobe nicht enthalten

Dieser Wert besagt, dass 60% der Besucher, die die Seite A.htm besucht haben, auch die Seite B.htm besucht haben. Der Support dieser Regel entspricht der Wahrscheinlichkeit P (A.htm ∪ B.htm), also 0,3. 30% aller Kunden haben in diesem Fall sowohl die Seite A.htm als auch die Seite B.htm besucht.

Zur Berechnung von Assoziationsregeln stehen mehrere Algorithmen zur Verfügung, die im Allgemeinen nur jene Regeln berechnen, die einen minimalen Support bzw. eine minimale Con dence haben. Diese beiden Parameter werden dem jeweiligen Algorithmus übergeben. Generell besteht das Au nden von Assoziationsregeln aus zwei Teilproblemen[3]:

1. Finden aller Mengen von Items (so genannte Itemsets ) mit minimalem Sup- port. Itemsets mit Mindestsupport werden als Large Itemsets bezeichnet.
2. Berechnung von Regeln mit minimaler Con dence aus den Large Itemsets.

Der wohl bekannteste Algorithmus für das Au nden von Large Itemsets (1. Teil- problem) ist der Apriori Algorithmus von Agrawal und Srikant [3]. In jedem Fall ist es notwendig, die Datenmenge mehrmals zu durchlaufen. Der Apriori Algorithmus reduziert die Anzahl der Durchläufe dadurch, dass er im ersten Schritt den Support für einzelne Items zählt und jene speichert, die über minimalen Support verfügen (als Large Itemset identi ziert wurden). In den darauf folgenden Schritten werden jeweils die im Schritt zuvor identi zierten Large Itemsets herangezogen, um neue

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Funktionsweise des Apriori Algorithmus

potentielle Large Itemsets zu berechnen - so genannte Candidate Itemsets. Dafür ist kein eigener Durchlauf durch die Datenmenge mehr notwendig - dieser wird nur mehr für die Berechnung der Support -Werte für diese Itemsets benötigt. Am Ende des Schritts wird festgestellt, welche der Itemsets tatsächlich Large Itemsets sind; diese werden wiederum für die Berechnung der Kandidatenmenge im nächsten Schritt herangezogen. Dieser Prozess läuft so lange, bis keine neuen Large Itemsets gefunden werden. Die Berechnung der jeweiligen Kandidatenmenge erfordert also keinen eigenen Durchlauf durch die Datenmenge. Candidate Itemsets mit jeweils k Items werden durch das Zusammenfügen (Joinen ) von Large Itemsets mit k - 1 Items erzeugt, wobei Kandidaten mit einer Teilmenge, die kein Large Itemset ist, gelöscht werden.

Abbildung 2.3 zeigt die Berechnung von Large Itemsets mit dem Apriori Algorith- mus anhand eines einfachen Beispiels. Die Datenmenge besteht aus sieben Transak- tionen t 1 ... t 7 mit sieben verschiedenen Items {A, B, C, D, E, F, G}. Der minimale Support beträgt 2. Für die Berechnung der Assoziationsregeln aus den ermittelten Large Itemsets (Teilproblem 2) wurden ebenfalls schnelle Algorithmen entwickelt (siehe [2] ), die im Rahmen dieser Arbeit nicht betrachtet werden. Für das prin- zipielle Verständnis der Vorgehensweise ist auch ein straightforward Ansatz [3] ausreichend: Für jedes Large Itemset l werden alle nicht-leeren Teilmengen von l gesucht. Für jede so gefundene Teilmenge a wird eine Regel der Form a ⇒ (l − a) er- zeugt, wenn [Abbildung in dieser Leseprobe nicht enthalten] gröÿer ist als die minimale Con dence. Im konkreten Beispiel aus Abbildung 2.3 sei dieser Vorgang am Large Itemset l = {A, B, D} gezeigt: Die nicht-leeren Teilmengen von l sind {A, B}, {A, D}, {B, D}, {A}, {B} und {D}.

Um eine konkrete Regel zu berechnen, nimmt man eine Teilmenge a von l sowie die Menge l − a:

Abbildung in dieser Leseprobe nicht enthalten

Die daraus abgeleitete Regel der Form a ⇒ (l − a) lautet {A, B} ⇒ {D}. Die Con dence dieser Regel ergibt sich aus [Abbildung in dieser Leseprobe nicht enthalten] Die Regel ist dann gültig, wenn vom Benutzer eine minimale Con dence von weniger als[0].[66] angegeben wurde. Auch für alle anderen Teilmengen wird geprüft, ob Regeln abgeleitet werden können, die diese Bedingung erfüllen.

2.1.4 Sequentielle Muster

Unter Sequentiellen Mustern (Sequential Patterns ) versteht man das Auftreten von Items in Transaktionsmengen (z.B. Einkäufe von Kunden) in einer bestimmten Reihenfolge. Das Problem ist wie folgt de niert [4]:

- Ein Itemset i ist eine nicht-leere Menge von Items ij (z.B. Produkte, die bei einem Einkauf gekauft wurden): i = {i 1 ...im}.
- Eine Sequence s ist eine geordnete Liste von Itemsets sj (z.B. mehrere Ein- käufe eines Kunden): s = 〈 s 1 ...sn 〉.
- Eine Sequence 〈[Abbildung in dieser Leseprobe nicht enthalten] 〉 ist in einer Sequence 〈 [Abbildung in dieser Leseprobe nicht enthalten]〉 enthalten, wenn Ganz- zahlen [Abbildung in dieser Leseprobe nicht enthalten] existieren, so dass [Abbildung in dieser Leseprobe nicht enthalten]. Die Sequence 〈 (3)(4 5)(8) 〉 ist z.B. in 〈 (7)(3 8)(9)(4 5 6)(8) 〉 enthalten, da (3) ⊆ (3 8) , (4 5) ⊆ (4 5 6) und (8) ⊆ (8). Hingegen ist die Sequence 〈 (3)(5) 〉 (3 und 5 in aufeinander folgenden Transaktionen) nicht in 〈 (3 5) 〉 (3 und 5 in der selben Transaktion) enthalten und umgekehrt.[4]

Ein konkretes Beispiel für ein solches Muster im Einkaufsverhalten wäre, dass Kunden zuerst einen Laptop kaufen (1.), dann eine USB-Maus (2.) und dann eine externe Festplatte (3.). Diese Aktionen müssen weder atomar sein noch unmittel- bar aufeinander folgen. Kunden, die dazwischen oder gleichzeitig andere Produkte

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: Berechnung sequentieller Muster, Beispiel aus[4]

(z.B. 1. Laptop und CD-Rohlinge, 2. USB-Stick, 3. Maus und Mauspad, 4. Festplatte) kaufen, unterstützen dieses Muster ebenfalls.

Zum Aufspüren von Sequential Patterns in Transaktionsdaten stellten Agrawal et al.[4] verschiedene Algorithmen vor. Die prinzipielle Vorgehensweise ist folgende:

1. Sort Phase: Sortieren der Datenmenge nach Sequences.
2. Litemset Phase: Au nden der Large Itemsets (auch: Litemsets ). Dieser Schritt erfolgt mit einer leicht modi zierten Version des im vorherigen Ab- schnitt vorgestellten Apriori Algorithmus.
3. Transformation Phase: Transformieren aller Sequences in eine Menge von Large Itemsets, die in der jeweiligen Sequenz enthalten sind.
4. Sequence Phase: Au nden von Large Sequences (jene mit Mindestsup- port) unter Verwendung der Large Itemsets.
5. Maximal Phase: Bestimmen so genannter maximaler Large Sequences. Be- gonnen wird mit den längsten Large Sequences. Alle Large Sequences, die bereits Teilmenge einer anderen Large Sequence sind, werden nicht in die Menge der maximalen Sequences aufgenommen. In manchen Algorithmen wird diese Phase mit dem Au nden von Large Sequences kombiniert, um Zeit zu sparen, die sonst für das Zählen nicht-maximaler Sequences ver- schwendet wird .

Abbildung 2.4 zeigt ein Beispiel für das Berechnen von sequentiellen Mustern mit dem Algorithmus AprioriAll (aus [4] ). Der Mindestsupport wurde als 2 (40%) de- niert; das heiÿt mindestens zwei Transaktionen müssen das Muster enthalten. Schritt 1 (Sortieren) ist trivial, Schritt 2 (Berechnen von Large Itemsets ) wurde bereits im vorherigen Kapitel anhand eines Beispiels gezeigt. Schritt 3 ist ebenfalls trivial; deshalb liegen die Transaktionen für dieses Beispiel bereits als Sequenz von Large Itemsets vor. Beim ersten Durchlauf durch die Datenmenge werden alle 1- Sequences mit Mindestsupport gesucht und der Menge L 1 hinzugefügt. Analog zur Berechnung von Large Itemsets (siehe vorheriger Abschnitt) erfolgt nun die Be- rechnung von Large Sequences der Länge k aus Large Sequences der Länge k − 1. Beim Durchlaufen der Datenmenge wird nur der Support berechnet. Das Ergebnis dieses Schritts im konkreten Beispiel sind die Mengen L 1 - L 4. In diesen Mengen werden nun beginnend in L 4 maximale Large Sequences gesucht. Die längste Se- quence - in diesem Fall 〈 1 2 3 4 〉 - ist automatisch maximal. Kürzere Sequences sind nur maximal, wenn sie nicht Teilmenge einer maximalen Sequence sind. Aus der Menge L 3 ist demnach nur 〈 1 3 5 〉, aus L 2 nur 〈 4 5 〉 maximal.

In einigen Anwendungsfällen, z.B. im E-Commerce, mag es interessant sein, das Verhältnis zwischen der Anzahl der Kunden, welche die ersten k + l Items einer Sequence kaufen und der Anzahl der Kunden, welche die ersten k Items einer Sequence kaufen, zu berechnen. Bei Anwendung des AprioriAll Algorithmus sind die Prä xe langer Sequenzen bereits vorhanden und die Berechnung von Sequenzregeln leicht möglich[4]. Im Beispiel aus Abbildung 2.4 ist die Large Sequence 〈 1 3 〉 mit Suppport 4 ein Prä x der Large Sequence 〈 1 3 4 〉 mit Support 3. Die Con - dence der Regel 〈 1 3 〉 ⇒ 〈 1 3 4 〉 wird wie die Con dence von Assoziationsregeln berechnet, im konkreten Beispiel also folgendermaÿen:

Abbildung in dieser Leseprobe nicht enthalten

2.1.5 Anwendungsgebiete

Von der Analyse von Log les abgesehen kommt Data Mining in den verschiedens- ten Anwendungsbereichen zum Einsatz. In der Medizin werden vorhandene Daten über Krebserkrankungen beispielsweise bereits dazu genutzt, um Klassi kations- regeln abzuleiten, die einen Tumor als gut- oder bösartig einstufen (vgl. [59] ). Data Mining hat groÿe Bedeutung im Marketingbereich, z.B. für Customer Pro - ling, Identi zieren von Kundensegmenten (Clustering), Entdecken von Cross Sel- ling Potentialen durch Warenkorbanalysen (Assoziationsregeln) sowie Vorhersagen von Kundenverhalten [18] - z.B. für Kündigungspräventionsmanagement. Auch im Bankenbereich ist eine Vielzahl von Anwendungsmöglichkeiten vorhanden: Kun- denbetreuer können sich bei der Einschätzung der Kreditwürdigkeit eines Kunden von Data Mining Techniken unterstützen lassen, auÿerdem nutzen viele Firmen Da- ta Mining für Investitionsentscheidungen [18]. In Fehlerdiagnosesystemen (z.B. für Flugzeuge) werden mit Clustering Fehlerklassen abgeleitet und mögliche Probleme vorhergesagt. In der Kriminalitätsbekämpfung greifen Ermittler auf Systeme mit Data Mining Funktionalitäten zurück, um Kreditkartenbetrug zu entdecken und Indizien für Geldwäscheaktivitäten zu nden[18]. In der Literatur werden zahlreiche weitere Anwendungsgebiete genannt, z.B. Telekommunikation, Daten lterung, Terrorismusbekämpfung, Biologie und viele mehr.

2.2 Inhalt von Log les

Serverseitige Logdateien enthalten je nach Format der jeweiligen Logdatei für je- den Aufruf unterschiedliche Informationen. Folgende Daten können grundsätzlich mitprotokolliert werden (diese Liste erhebt keinen Anspruch auf Vollständigkeit):

- Die IP-Adresse, von der der Aufruf stammt
- Die IP-Adresse des Servers
- Datum und Uhrzeit der Anfrage
- Username, falls der Request von einem authenti zierten Benutzer stammt
- Die verwendete HTTP-Methode (GET, HEAD, POST, PUT)
- Der Pfad der angeforderten Ressource (z.B. /inhalt/index.htm )
- Die Portnummer der Anfrage ( 80 bei HTTP-Requests)
- Das Protokoll (z.B. HTTP/1.1 )
- Der User Agent (verwendeter Browser, z.B. Mozilla/4.0+(compatible;) )
- Referrer (jene URL, die im Browser des Nutzers unmittelbar vor dem aktu- ellen Request aufgerufen wurde)
- Übermittelter Status-Code (z.B. 200 für OK, 404 für Datei nicht gefunden )
- Übertragene Bytes (=Gröÿe der angeforderten Ressource)
- Der Wert bestimmter Cookies (z.B. language=de )
- Die vom Server generierte Session-ID

Welche dieser Daten tatsächlich mitprotokolliert werden, hängt von der Kon guration des Webservers, konkret vom verwendeten Logformat ab. Die am häu gsten verwendeten Formate sind (siehe[44] ):

- NCSA Common Log Format [42]: Dieses Format enthält nur grundlegende Informationen: IP-Adresse des Aufrufers, Name des authent zierten Users (falls vorhanden), Datum und Uhrzeit sowie die Request-Zeile bestehend aus HTTP-Methode, URL und Protokoll.
- W3C Extended Log Format [22]: Dabei handelt es sich um ein exibles, benutzerde niertes Format. Die zu protokollierenden Felder werden mit Direktiven festgelegt.
- NCSA Combined Log Format: Das Combined Log Format ist eine Erwei- terung des Common Log Formats. Es enthält zusätzlich zu den Feldern des Common Log Formats noch die Felder Referrer, User Agent und optional Cookie-Informationen[44].
- NCSA Separate Log Format (3-log format) ist ein Format, bei dem die ge- wonnenen Informationen in drei verschiedenen Logs abgelegt werden: Allgemeine Zugri sinformationen in einem Access Log im Common Log Format, die zuletzt besuchte Seite in einem Referrer Log und Informationen über den Browser in einem Agent Log. Alle Einträge in den einzelnen Logs haben einen Zeitstempel (datestamp ), um miteinander in Verbindung gebracht werden zu können. Cookie-Informationen werden nicht gespeichert[44].

Die im Rahmen dieser Arbeit entwickelte, im 2. Teil vorgestellte Software unter- stützt das Combined Log Format und das W3C Extended Logformat. Weitere Formate werden bei Bedarf integriert. Zu beachten ist in jedem Fall, dass mit dem Aufruf einer Webseite ( Page View ) in der Regel mehrere Anfragen (Hits) an den Webserver verbunden sind und auch protokolliert werden, weil in einer HTML-Datei (oder JSP- bzw. PHP-Datei) im überwiegenden Teil der Fälle auch Graphiken, Skripts, Flashanimationen usw. eingebunden sind. Da das HTTP Pro- tokoll ein zustandsloses Protokoll ist und der Server die Verbindung zum Client nach jeder Anfrage wieder trennt, enthält das Log le keinen zusammenhängenden Nutzungsvorgang, sondern lediglich eine chronologische Au istung aller bearbei- teten Anfragen [66]. Diese Problematik ist historisch bedingt. Der ursprüngliche Zweck von Web Logs lag nicht in der Analyse des Benutzerverhaltens, sondern in der Überwachung der Server-Aktivität und im Aufzeichnen von Fehlern.

2.3 Preprocessing von Web Logs

Die Anwendung von Data Mining Techniken setzt die Existenz strukturierter, hochwertiger Daten voraus (vgl. Abschnitt 2.1.). Web Logs erfüllen diese Voraussetzung nicht und müssen deshalb entsprechend aufbereitet werden.

2.3.1 Säubern der Logdatei

Um eine Logdatei für Analysezwecke zu verwenden oder anderweitig weiterzuverarbeiten, ist es in erster Linie notwendig, sie von irrelevanten Einträgen zu säubern (siehe[15] und[79] ). Irrelevant sind jene Ressourcen, die vom Besucher nicht explizit angefordert, sondern aufgrund eines anderen Requests implizit geladen werden. Darunter fallen beispielsweise Graphiken, Skriptdateien oder Flash-Animationen, die in Webseiten eingebettet sind. Erkannt werden können diese Einträge an der Dateiendung der jeweiligen URL. Aufrufe von Dateien vom Typ JPG, GIF, SWF, JS usw. werden aus dem Log le gelöscht.

Auch Aufrufe von verschiedenen Robots (vollautomatische Agenten, die das World Wide Web durchwandern, z.B. Suchmaschinen-Crawler, Email-Sammler, Spam- Bots und Link-Checker) sollten möglichst erkannt werden, um die Analyse des Benutzerverhaltens nicht zu verzerren. In[73] werden folgende Möglichkeiten genannt, um Robots zu identi zieren:

1. Sauber programmierte Robots rufen die Datei robots.txt auf und geben sich damit quasi freiwillig zu erkennen. Naturgemäÿ ist diese Methode keine be- sonders zuverlässige.

2. Auch das User Agent Feld kann darüber Aufschluss geben, ob ein Aufruf von einem (bekannten) Robot stammt. Beachtet werden muss, dass dieses Feld manipulierbar ist und somit diese Methode kein sicheres Ergebnis liefert.

3. Hier gilt ähnliches wie für den zuvor genannten Punkt. Die IP-Adresse kann Aufschluss geben, da bekannte Robots meist mit der selben IP-Adresse bzw. mit einer Adresse aus einem bestimmten IP-Range agieren. Allerdings ist es durchaus möglich, dass auch menschliche Nutzer die selbe Adresse verwenden (z.B. wenn der Aufruf über einen Proxy-Server geschieht).

4. Link-Checker-Robots, die nur die Verfügbarkeit einer URL überprüfen, be- dienen sich gewöhnlich der HEAD-Methode, um möglichst wenig Tra c zu erzeugen, während Browser diese Methode im Allgemeinen nicht verwenden.

Im Zuge der Analyse von Log les im Rahmen dieser Arbeit wurden auÿerdem zwei weitere Indizien ermittelt, die auf die Präsenz eines Robots hindeuten:

5. Zyklische Aufrufe: Erfolgen die Aufrufe von einer bestimmten IP in einem bestimmten Rhythmus (alle n + ε Sekunden), ist das ein sehr starkes Indiz für einen Robot. Es ist sehr unwahrscheinlich, dass ein menschlicher User ein derart regelmäÿiges Verhalten an den Tag legt.

6. Der Aufruf vieler verschiedener URLs innerhalb kurzer Zeit bzw. eine sehr kurze durchschnittliche Aufenthaltsdauer (~ 1 Sekunde) auf den verschiede- nen Seiten sprechen ebenfalls klar dafür, dass die Aufrufe von einem Robot stammen.

Ein absolut zuverlässiges Erkennungsmerkmal für Robots gibt es nicht. Mit den genannten Methoden kann zumindest der überwiegende Teil der Robot-Anfragen erkannt und somit ge ltert werden. Es ist davon auszugehen, dass die wenigen Anfragen von Robots, die nicht erkannt werden, vernachlässigbare Auswirkungen auf eine anschlieÿende Analyse haben.

2.3.2 Identi kation von Usern

Die Identi kation von Usern innerhalb eines Web Logs ist problemlos möglich, wenn es sich um authenti zierte User handelt oder ein persistentes Cookie für die Identi kation der Besucher verwendet wird. Alternativ können dynamische URLs mit eingebetteter Session-ID verwendet werden. Wenn der Browser des Besuchers keine Cookies akzeptiert oder von Serverseite kein Cookie zur Identi kation gesetzt wird, erweist sich diese Aufgabe in der Regel als relativ schwierig. Anfragen an den Webserver von der gleichen IP-Adresse können aufgrund der verbreiteten Verwen- dung von Proxy-Servern nicht einem Besucher zugerechnet werden. Heuristische Unterscheidungen sind in Kombination mit dem User Agent und dem verwende- ten Betriebssystem möglich - Informationen, die bei entsprechender Kon guration des Servers dem Agent Log bzw. dem User Agent Feld entnommen werden kön- nen [15]. Eine weitere Heuristik für die Benutzeridenti kation ist das Einbinden der Topologie der Seite, um für jeden Benutzer Navigationsmuster zu generieren. Wird eine Seite angefordert, die von keiner bisher angeforderten Seite aus erreicht werden kann, liegt die Vermutung nahe, dass ein weiterer Benutzer mit der selben IP-Adresse und gleichem User Agent im Spiel ist [15]. Prinzipiell denkbar, aber unwahrscheinlich ist die Möglichkeit, dass ein Benutzer mehrere Browser zugleich verwendet oder URLs manuell eingibt, anstatt auf einen Hyperlink zu klicken. In diesem Fall könnte er mit den genannten Heuristiken nicht als ein Benutzer identi ziert werden. Wahrscheinlicher ist der umgekehrte Fall: Anfragen mehrerer Benutzer mit gleicher IP-Adresse, gleichem Browser und gleichem Betriebssystem werden einem einzigen Benutzer zugeschrieben.

2.3.3 Identi kation von Sessions

Unter dem Begri Session versteht man eine Folge von Seitenbesuchen eines Besu- chers innerhalb einer bestimmten Zeitspanne. Eine Session besteht aus Anfragen, die im Zuge eines Besuchs innerhalb einer bestimmten Zeit abgesetzt werden. Ge- nerell wird ein Session-Time-Out von 30 Minuten gewählt; Zugri e eines Besuchers, die mehr als 30 Minuten nach seinem letzten Zugri erfolgen, werden nicht mehr der selben Session zugeordnet. Die Verweildauer eines Besuchers auf einer einzel- nen Seite lässt sich ob der zustandslosen Natur des HTTP-Protokolls nicht direkt bestimmen, kann aber durch die Zeitdi erenz zwischen zwei Requests berechnet werden. Dieser Wert ist ein Indiz, aber kein Beweis für die tatsächliche Aufent- haltsdauer: Zum einen ist es durchaus möglich, dass der Besucher mit mehreren Browserfenstern zugleich arbeitet ( Tabbed Browsing ), wodurch die tatsächliche Aufenthaltsdauer auf einer Seite nicht mehr nachvollziehbar ist; zum anderen spei- chern Browser aus Performancegründen Dateien, die sie von einem Webserver an- fordern, auf der lokalen Festplatte ab (Cache). Bei einem erneuten Aufruf muss diese Datei nicht mehr vom Server geladen werden; der Server bekommt also von einem erneuten Besuch nichts mit und kann ihn deshalb nicht protokollieren.

Für letzteres Problem gibt es einige Lösungsansätze (vgl. [15] ): Caching kann im Quellcode der Webseite verboten werden; auÿerdem wurde in [15] die Möglich- keit der Pfadvervollständigung präsentiert, bei der anhand des Referrer-Logs oder der Seiten-Topologie fehlende Requests im Web Log rekonstruiert werden können. Die Genauigkeit und universelle Anwendbarkeit dieser Methode ist allerdings anzu- zweifeln, auf die tatsächliche Aufenthaltsdauer auf einer Seite kann damit ebenfalls nicht geschlossen werden.

2.3.4 Alternative: Sammeln von Logdaten auf Clientseite

Alternativ besteht auch die Möglichkeit, Interaktionsdaten clientseitig zu sam- meln; auf diese Weise umgeht man die Probleme von Benutzer- und Sessioniden- ti kation, da der Einsatz von Cache und Proxy-Servern keinen Ein uss auf das Sammeln der Daten hat. Implementiert werden kann clientseitige Datensammlung unter Verwendung eines Remote-Agenten (z.B. JavaScripts, Java Applets) oder durch Modi zieren des Browsers, um ihm Datensammlungsfähigkeiten anzueignen [71]. Lin et al.[40] schlagen beispielsweise ein Modul vor, das nach der Installation beim Client das Benutzerverhalten aufzeichnet und an einen Datensammelserver schickt. Die Interaktionsdaten werden somit bereits strukturiert aufgezeichnet und können ohne weitere Aufbereitung analysiert werden. Einen gravierenden Nachteil haben clientseitige Methoden: Sie erfordern die Kooperation des Benutzers, der sich das nötige Applet oder Browser-Plugin installieren muss. Applets haben über- dies beim ersten Start relativ lange Ladezeiten und sind deshalb aus Benutzersicht nicht optimal. JavaScripts weisen zwar eine bessere Performance auf, können aber nicht alle Klicks registrieren (z.B. Neu Laden oder Zurück ). Ein modi zier- ter Browser ist aus qualitativer Sicht die beste Lösung, da das Benutzerverhalten über mehrere Webseiten hinweg beobachtet werden kann. Es dürfte sich freilich als schwierig erweisen, genügend Benutzer davon zu überzeugen, einen modi zierten, spionierenden Browser für ALLE ihre Aktivitäten im Internet zu verwenden.

2.4 Repräsentation von Web Logs

Wurden alle irrelevanten Einträge aus der Logdatei entfernt sowie User und Sessions identi ziert, müssen die vorhandenen Informationen für etwaige Analyseschritte entsprechend formatiert werden. Einige mögliche Repräsentationsformen werden in der Folge vorgestellt.

2.4.1 n -dimensionaler binärer Attributvektor

Dieses kompakte, aber nur bedingt anwendbare Format wurde in[55] präsentiert. Dabei wird jeder URL eine eindeutige Nummer j ∈ { 1 , ..., n} zugewiesen, wobei n die Anzahl der gültigen URLs ist¹. Die i -te User-Session wird als n -dimensionaler binärer Attributvektor mit der Eigenschaft

Abbildung in dieser Leseprobe nicht enthalten

codiert. Für viele Data Mining Algorithmen ist diese Darstellung geeignet und somit eine Analyse möglich. Allerdings gehen wichtige Informationen wie die Reihenfolge der Aufrufe, Aufenthaltsdauer und die Häu gkeit der Besuche einzelner Seiten innerhalb einer Session verloren. Bei einer sehr groÿen Anzahl von URLs leidet auÿerdem die Performance der Analysealgorithmen sehr stark.

2.4.2 n-dimensionaler Pageview-Referenz Vektor

Im einem an der DePaul University in Chicago, Illinois, entwickelten, auf Web Usa- ge Mining basierendem serverseitigen Recommendersystem wird für die Darstel- lung von Transaktionen ebenfalls ein n -dimensionaler Vektor verwendet [50, 47]. Gegeben ist eine Menge von eindeutigen Seiten U = {url 1 , url 2 , ..., urln} und eine Menge von User Transaktionen T = {t 1 , t 2 , ..., tn}, wobei jedes ti eine nichtleere Teilmenge von U ist. Jede Transaktion wird als n -dimensionaler Vektor der Form

Abbildung in dieser Leseprobe nicht enthalten

dargestellt, wobei w (urli, t) für die Gewichtung steht, die mit dem durch urli repräsentierten Pageview assoziiert wird. Handelt es sich dabei um eine binäre [1] Die Autoren von [55] verwenden für den Index n die Bezeichnung N U Gewichtung (z.B. 1 für Besuch, 0 für Nichtbesuch von urli), entspricht dieses For- mat dem oben vorgestellten binären Attributvektor. Die Gewichtung kann aber auch anhand anderer Gesichtspunkte, z.B. Aufenthaltsdauer oder Aufrufhäu g- keit, auf di erenziertere Art und Weise erfolgen. Somit können die Session-Daten mit Standard Data Mining Techniken analysiert werden. Informationen über die Reihenfolge der Seitenbesuche PageViews gehen aber ebenfalls verloren.

Betrachtet man anstatt einer Session mehrere oder alle Sessions, ergibt sich folgende Repräsentationsform: Gegeben ist eine Menge von User-Sessions U = {u 1 , u 2 , ..., um} und eine Menge von Seiten P = {p 1 , p 2 , ..., pn}. Die Benutzer- sessions können nun dargestellt werden als m × n Session-URL-Matrix U P = [Abbildung in dieser Leseprobe nicht enthalten], wobei [Abbildung in dieser Leseprobe nicht enthalten] für die Gewichtung von Seite pj in der Benutzerses- sion ui steht [32, 30].

2.4.3 Sequenz von Seitenaufrufen

Das Ableiten sequentieller Muster erfordert die Repräsentation von Sessions als eine Menge S = {s 1 , ..., sn} von Seitenaufrufs-Sequenzen (vgl.[4]. Eine Session si wird dargestellt als Sequenz si = 〈 ui 1 ...uin 〉, wobei uij für die als j -tes aufgerufene Seite in Session si steht. Die Reihenfolge und Anzahl der Seitenbesuche bleibt zwar erhalten, für Clustering-Algorithmen oder Klassi kation ist diese Darstellung jedoch nur bedingt geeignet. Die Aufenthaltsdauer wird nicht berücksichtigt.

2.4.4 Dateiformat One Session Per Line

Dieses Darstellungsformat wurde im Rahmen dieser Arbeit entwickelt und erwei- tert die sequentielle Darstellung um zusätzliche Informationen. Jede Session wird innerhalb einer Textdatei durch eine Zeile mit folgender Form repräsentiert:

[Session-ID, Benutzer-ID, IP, Startzeit]: (P1, T1), ..., (P n, T n)

Im eckigen Klammerpaar werden allgemeine Informationen zur Session gespeichert (Session-ID, Benutzer-ID, IP-Adresse sowie Datum und Uhrzeit des Beginns der Session). Bei Bedarf kann das Format noch für zusätzliche Informationen erweitert werden (z.B. User Agent). In den folgenden i Klammerpaaren (P i, T i) sind sequentiell die angeforderten Seiten-IDs P i (alternativ kann auch die URL verwendet werden) sowie die jeweilige Aufenthaltsdauer T i enthalten. Die Aufenthaltsdauer für die letzte Seite in einer Session ist in der Regel unbekannt und wird mit -1 gespeichert. Dieses Format ist nicht direkt für Analysealgorithmen anwendbar. Es hat aber den Vorteil, für Menschen lesbar zu sein; bei Bedarf können alle relevanten Informationen durch Parsing leicht extrahiert werden.

2.4.5 Datenbankrepräsentation

Die Repräsentation von Sessions in einem Textformat birgt einige Nachteile. Um alle Informationen e zient und ohne Informationsverlust aufzubereiten, ist eine relationale Datenbank geeigneter. In [26] wird beispielsweise ein würfelförmiges Modell präsentiert, das auf relationalen Datenbanktabellen basiert. Die aus dem Web Log extrahierten Informationen werden dabei in drei Dimensionen darge- stellt: In der Session-Dimension werden alle identi zierten Sessions repräsentiert, die Komponenten-Dimension enthält Informationen über die Reihenfolge der Pa- geVisits und die Attribut-Dimension stellt zusätzliche Informationen über die be- suchten Seiten bereit. Der Nachteil dieses Modells liegt im unnötig hohem Spei- cheraufwand, da für eine würfelförmige Darstellung alle identi zierten Sessions die gleiche Länge haben müssen. Sessions, die kürzer sind als die längste Session, müs- sen mit Platzhaltern aufgefüllt werden.

Im Rahmen dieser Arbeit wurde ein relationales Datenbankmodell für die Reprä- sentation von Sessions entwickelt (siehe Anhang A). Ein Ausschnitt der relevanten Teile ist in Abbildung 2.5 zu sehen. Die Reihenfolge der Seitenbesuche ist indirekt

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.5: Datenbankrepräsentation von Sessions (Ausschnitt)

durch den Zeitpunkt des Aufrufs gegeben. Jede Seite kann auÿerdem mit Meta- informationen versehen werden, indem sie einer oder mehreren zuvor de nierten Dimensionen (Kategorien ) zugewiesen wird. Man spricht in diesem Fall auch da- von, dass eine Seite ein Indikator für eine bestimmte Dimension ist (z.B. kann der Aufruf einer Seite mit den AGB eines Online-Shops ein Indikator für ein sehr konkretes Kau nteresse sein). Diese Zuweisung erfolgt fuzzy ; das heiÿt eine Seite kann zu einem bestimmten Grad einer Dimension angehören bzw. Indikator für eine bestimmte Dimension sein, wobei dieser Wert zwischen 0.0 (keine Zugehö- rigkeit) und 1.0 (volle Zugehörigkeit) liegen kann. Diese Informationen sind dann notwendig, wenn Benutzersessions auf der Ebene von Interessen analysiert werden sollen (vgl. Abschnitt 3.5.6 und Kapitel 5). Für Metainformationen, die für eine Analyse nicht relevant sind (z.B. Autor der Seite, Erstelldatum, etc.) steht bei Bedarf ein String-Attribut zur Verfügung. Ausgehend von dieser Darstellung, die alle relevanten Informationen über Sessions enthält, kann jede beliebige Textre- präsentation abgeleitet werden.

2.5 Web Log Analyse

Nach der Säuberung des Web Logs von unnötigen Einträgen, der Identi kation von Usern und Sessions sowie der Aufbereitung/Formatierung der extrahierten Sessions erfolgt die eigentliche Auswertung der gewonnenen Daten. Die Berech- nung bestimmter Kenngröÿen (Anzahl der Besucher, Page Hits, durchschnittliche Aufenthaltsdauer für einzelne Seiten, verursachter Tra c) ist trivial. Mit Unter- stützung von Data Mining Techniken (vgl. Abschnitt 2.1.) lässt sich noch eine Reihe weiterer wertvoller, nicht o ensichtlicher Informationen aus den aufgezeich- neten Daten extrahieren.

2.5.1 Assoziationsregeln und Frequent Itemsets

Eine entsprechende Repräsentation (z.B. binärer Attributvektor, Datenbankrepräsentation) vorausgesetzt, können in Web Logs mit verschiedenen Algorithmen (z.B. Apriori Algorithmus, siehe Abschnitt 2.1. und [3] ) Seiten identi ziert werden, die in Sessions oft gemeinsam vorkommen (Frequent Itemsets bzw. Large Itemsets ) [50]. Die Berechnung von Assoziationsregeln der Form Besuch von Seite A ⇒ Besuch von Seite B aus Large Itemsets wurde in Abschnitt 2.1. illustriert und kann relativ einfach durchgeführt werden.

2.5.2 Clustering und Klassi kation

Auch für Clustering-Algorithmen ist die Repräsentation der Sessions durch einen (binären) Attributvektor am geeignetsten, da auf diese Art und Weise leicht ein ge- eignetes Ähnlichkeitsmaÿ (z.B. Euklidischer Abstand ) de niert werden kann. Um Sessions zu clustern (man spricht auch von Transaction Clusters ), muss die Di- stanz zwischen einzelnen Sessions berechnet werden. Ein Beispiel: Gegeben seien zwei Sessions, repräsentiert durch die binären Attributvektoren x = (1 , 0 , 0 , 1) und y = (1 , 1 , 0 , 1). Der Euklidische Abstand ist de niert als [Abbildung in dieser Leseprobe nicht enthalten] (vgl. Abschnitt 2.1.). Die Distanz zwischen Session x und Session y ist demnach [Abbildung in dieser Leseprobe nicht enthalten].

Alternativ ist die Zuweisung von einzelnen Seiten an verschiedene URL-Cluster (Usage Clusters ) möglich, basierend auf der Häu gkeit des gemeinsamen Auftre- tens in Sessions. Details und Berechnungsvorschriften werden in[50] angeführt. Für Klassi kation ist das vorherige De nieren von Klassen und Eigenschaften not- wendig, auf Basis derer die Klassi kation statt nden soll [71]. Hier ist es wün- schenswert, dass eine detailliertere Repräsentationsform als beispielsweise ein bi- närer Attributvektor zur Verfügung steht (Datenbankrepräsentation oder PageviewReferenz Vektor).

Clustering und Klassi kation werden von der im Rahmen dieser Arbeit entwickel- ten Softwarekomponente nur indirekt unterstützt: Es ist möglich, Sessiondaten in ein für Clustering und Klassi kation geeignetes Dateiformat zu transferieren und die Analyse anschlieÿend mit externen Data Mining Tools durchzuführen.

2.5.3 Sequentielle Muster

Sequentielle Muster berücksichtigen die Reihenfolge von Items innerhalb von Trans- aktionsmengen (siehe Abschnitt 2.1.).

[...]

---

¹ http://cohave.i t.uni-klu.ac.at

¹ http://cohave.i t.uni-klu.ac.at