In Kapitel 2 werden die grundlegenden Begriffe und formalen Definitionen der Clusteranalyse diskutiert. Es wird auf die NP-H¨ arte des Clustereinteilungsproblems eingegangen. Die in der Literatur bestehenden Clusterverfahren werden anhand ihrer immanenten Eigenschaften klassifiziert und Prinzipien zur Bildung von Clustern thematisiert. Ein weiterer Abschnitt des Kapitels 2 befasst sich mit Abstands- bzw. Ähnlichkeitsfunktionen, die einen wesentlichen Bestandteil von Clusterverfahren bilden.
Existierende, klassische Algorithmen zur Clusterbildung aus dem Bereich des Data Mining werden in Kapitel 3 erläutert. Nachdem die Clusterverfahren in Kapitel 2 klassifiziert wurden, werden in Kapitel 3 vier Klassen von Clusterverfahren näher beleuchtet: Hierarchische und partitionierende Verfahren, Fuzzy-Clustering und wahrscheinlichkeitsbasiertes Clustern.
In Kapitel 4 wird ein Algorithmus zur Berechnung von Benutzerprofilen vorgestellt.
Kapitel 5 gibt eine Beschreibung der Clusterbildung als Disziplin des Web Usage Mining. Der erste Abschnitt führt grundlegende Begriffe ein und motiviert
die Anwendung der Clusteranalyse im Web Mining. Des Weiteren werden in Kapitel 5 die Parameter zum Clustern von Benutzern auf der Grundlage von non-obvious-user-profiles diskutiert. Die Aufgabe des zweiten Abschnittes dieses Kapitels ist die Beantwortung der Frage: ” Was kann alles geclustered
werden?“ Im dritten und letzten Abschnitt des Kapitels 5 wird zun¨ achst allgemein und anschließend anhand eines Beispiels die Anwendung eines in der Praxis häufig eingesetzten, klassischen Clusterverfahrens auf non-obvious-userprofiles erläutert.
Das Kapitel 6 ist der Vorstellung verwandter Arbeiten im Web Mining Umfeld gewidmet. Es werden sowohl zahlreiche, in der Literatur diskutierte Clusterverfahren als auch Ähnlichkeitsmaße präsentiert, erläutert, miteinander verglichen und kritisiert.
In Kapitel 7 werden einige mögliche Anwendungen der Clusteranalyse im Bereich des Web Usage Mining diskutiert. Im Einzelnen handelt es sich um Recommender Systeme, Adaptive Websites, Prefetching Systeme und die selektive Kontaktierung von Kundengruppen.
Kapitel 8 gibt eine Zusammenfassung der vorliegenden Arbeit.
Inhaltsverzeichnis
1. Einleitung
1.1 Einführung in Information Retrieval und Data Mining
1.2 Einführung in die Clusteranalyse
1.3 Überblick über die Arbeit
2. Grundlagen der Clusteranalyse
2.1 Begriffe und formale Definitionen
2.2 Optimales Clustern ist NP-hart
2.2.1 Objekte in unterscheidbaren Clustern
2.2.2 Objekte in ununterscheidbaren Clustern
2.2.3 Beweis nach Garey und Johnson
2.3 Klassifikation der Clusterverfahren
2.3.1 Hierarchische Clusterverfahren
2.3.2 Partitionierende Clusterverfahren
2.3.3 Disjunkte vs. nicht-disjunkte Verfahren
2.3.4 Deterministische vs. probabilistische Verfahren
2.3.5 Monothetische vs. polythetische Verfahren
2.3.6 Scharfe vs. Fuzzy-Verfahren
2.3.7 Inkrementelle vs. nicht-inkrementelle Verfahren
2.3.8 Überwachte vs. unüberwachte Verfahren
2.3.9 Unvollständige vs. vollständige Verfahren
2.4 Prinzipien zur Bildung der Cluster
2.5 Abstandsfunktionen
2.5.1 Begriffe, Definitionen
2.5.2 Wichtige Distanzmaße für metrische Variablen
2.5.2.1 Distanzmaße auf Basis der verallgemeinerten Minkowski-Metrik
2.5.2.2 Ein Beispiel zur verallgemeinerten Minkowski-Metrik
2.5.2.3 Probleme der diskutierten Distanzmaße
2.5.2.4 Transformation auf eine einheitliche Skala
2.5.2.5 Gewichtung der Merkmale
2.5.2.6 Die Mahalanobis-Distanz
2.5.2.7 Das Kosinusmaß
2.5.3 Distanzmaße für Merkmale mit binärem Wertebereich
2.5.4 Aufstellen der Ähnlichkeitsmatrix
2.6 Kategorienützlichkeit
2.7 Darstellung von Clustern
3. Klassische Clusteralgorithmen
3.1 Hierarchische Verfahren
3.1.1 Hierarchisch agglomerierender Algorithmus
3.1.2 Single Pass Clustering
3.1.3 Ein graphentheoretischer Algorithmus
3.2 Partitionierende Verfahren
3.2.1 Squared Error Methode
3.2.2 K-means Algorithmus
3.3 Fuzzy-Clustering
3.3.1 Unscharfe Mengen, Zugehörigkeitsfunktion
3.3.2 Fuzzy-c-means Algorithmus
3.4 Wahrscheinlichkeitsbasiertes Clustering
3.4.1 EM-Algorithmus
4. Non-obvious user profiles (NOPs)
4.1 Motivation
4.2 Algorithmus zur Erstellung von NOPs
4.3 Messen der Ergebnisse
4.3.1 Einbinden eines Feedback-Mechanismus
4.3.2 Nutzen der Feedback-Informationen
5. Clusterbildung als Disziplin des Web Usage Mining
5.1 Motivation, Grundlagen
5.2 Parameter zum Clustern von Benutzern auf Basis von NOPs
5.2.1 Auf der Website angebotene Themen
5.2.2 Zeitliche Interessensänderungen der Benutzer
5.2.3 Vertrauenswürdigkeit der Benutzer
5.2.4 Navigationspfade der Benutzer
5.2.5 Durchschnittliche Sessiondauer
5.2.6 Anzahl Sessions
5.2.7 Persönliche Daten der Benutzer
5.3 Anwendung klassischer Clusteralgorithmen auf Benutzerprofile
5.3.1 Anwendung des K-means-Algorithmus auf die Clusterbildung von NOPs in Bezug auf Themen
5.3.2 Beispiel zur Anwendung des K-means-Algorithmus
6. Verwandte Arbeiten im Web Mining Umfeld
6.1 Zugriffsmuster, generalisierte Sessions und Attribute-oriented induction
6.1.1 Clusterverfahren BIRCH
6.2 Clusteranalyse von Sessions mittels Sequence Alignment
6.3 Ähnlichkeitsbasiertes Clustern von Web Transaktionen
6.4 Entdeckung von Wissen durch Navigationspfade von Benutzern
6.4.1 Path Feature Space
6.5 Sequence Alignment Methode
6.6 Charakterisieren von Benutzergruppen einer E-Commerce Website
6.6.1 Hybrider Clusteralgorithmus
6.7 Ähnlichkeitsbestimmung zwischen Interessen zur Clusteranalyse
6.7.1 Ähnlichkeitsmaße
6.7.2 Matrixbasierter Clusteralgorithmus
6.8 Clusteranalyse anhand von längsten, gemeinsamen Teilpfaden
6.8.1 Ähnlichkeit zwischen Pfaden
6.8.2 Graphbasierter Clusteralgorithmus
6.8.3 Beispiel zur Ähnlichkeit zweier Pfade
6.9 Erstellung von aggregierten Benutzungsprofilen
6.9.1 Profile Aggregations based on Clustering Transactions (PACT)
6.9.2 Association Rule Hypergraph Partitioning (ARHP)
7. Anwendungsgebiete der Clusteranalyse
7.1 Recommender Systeme
7.2 Adaptive Websites
7.3 Prefetching Systeme
7.4 Kontaktierung von Kundengruppen
8. Zusammenfassung
Zielsetzung und thematische Schwerpunkte
Die vorliegende Arbeit untersucht das Verfahren der Clusteranalyse im Kontext des Web Usage Mining, um Benutzer anhand ihres Verhaltens auf Web-Portalen in homogene Gruppen zu segmentieren. Dabei steht die Entwicklung und Evaluierung von Benutzerprofilen – insbesondere sogenannter "non-obvious user profiles" (NOPs) – im Mittelpunkt, um eine personalisierte Ansprache und Web-Optimierung zu ermöglichen.
- Grundlegende Definitionen und Klassifikation von Clusterverfahren
- Algorithmen zur Erstellung und Berechnung von NOPs
- Anwendung klassischer Clusteralgorithmen im Web-Mining-Kontext
- Diskussion verwandter Arbeiten zur Clusterbildung von Sessions und Pfaden
- Anwendungsfelder wie Recommender Systeme, Adaptive Websites und Prefetching
Auszug aus dem Buch
2.3.2 Partitionierende Clusterverfahren
Die Aufgabe partitionierender Clusterverfahren besteht darin, eine Datensammlung, ausgehend von einer initialen Partitionierung, in k disjunkte Mengen derart zu partitionieren, dass sich die Objekte innerhalb einer Gruppe so ähnlich wie möglich sind. Jedes Objekt wird einem eindeutigen Cluster zugewiesen. Es entsteht keine hierarchische Clusterstruktur [20]. Der Vorteil partitionierender Clusterverfahren liegt in der Untersuchung sehr großer Datensammlungen, wo die Erstellung eines Dendrogramms nur schwer durchzuführen ist.
Bei partitionierenden Clusterverfahren ist es notwendig, aber auch problematisch, vor dem Start des Algorithmus anzugeben, auf wie viele (unbekannte) Partitionen k der Algorithmus die Datensammlung untersuchen soll. Damit bleibt die Anzahl der Cluster konstant. Sicherlich lässt sich der Algorithmus mehrere Male mit verschiedenen Werten für k starten, jedoch muss man in der Lage sein, sich zwischen verschiedenen k-Werten zu entscheiden [20]. Welches k zur optimalen Clustereinteilung führt, kann nur anhand einer Ähnlichkeitsfunktion (score function) bestimmt werden. Insbesondere kann durch die Berechnung der Kategorienützlichkeit (siehe Abschnitt 2.6) die Gesamtqualität einer Aufteilung von Objekten in Cluster gemessen werden. [50]
Zusammenfassung der Kapitel
1. Einleitung: Einführung in die Themengebiete Information Retrieval, Data Mining und Clusteranalyse sowie eine Vorstellung der Arbeitsstruktur.
2. Grundlagen der Clusteranalyse: Diskussion der theoretischen Definitionen, Komplexitätsprobleme (NP-Härte) und eine detaillierte Klassifikation verschiedener Clusterverfahren sowie Abstandsfunktionen.
3. Klassische Clusteralgorithmen: Erläuterung verbreiteter Algorithmen aus dem Data Mining, unterteilt in hierarchische, partitionierende, Fuzzy- und wahrscheinlichkeitsbasierte Verfahren.
4. Non-obvious user profiles (NOPs): Beschreibung eines spezifischen Algorithmus zur Erstellung und Messung von Benutzerprofilen, die über offensichtliche Registrierungsdaten hinausgehen.
5. Clusterbildung als Disziplin des Web Usage Mining: Motivation zur Clusterbildung von Benutzern und Anwendung klassischer Verfahren auf Basis der in Kapitel 4 definierten Benutzerprofile.
6. Verwandte Arbeiten im Web Mining Umfeld: Kritische Analyse und Vergleich verschiedener wissenschaftlicher Ansätze zur Clusterbildung von Sessions, Clickstreams und Navigationspfaden.
7. Anwendungsgebiete der Clusteranalyse: Untersuchung praktischer Einsatzszenarien wie Recommender Systeme, adaptive Webseiten, Prefetching und die gezielte Kontaktierung von Kundensegmenten.
8. Zusammenfassung: Abschließendes Resümee über die Ergebnisse der Diplomarbeit und Ausblick auf zukünftige Forschungsnotwendigkeiten.
Schlüsselwörter
Clusteranalyse, Data Mining, Web Usage Mining, Benutzerprofile, K-means, Partitionierung, Hierarchische Verfahren, Web Mining, Recommender Systeme, Adaptive Websites, Prefetching, Navigationspfade, Ähnlichkeitsmaße, Clickstream, Kategorienützlichkeit.
Häufig gestellte Fragen
Worum geht es in dieser Diplomarbeit im Kern?
Die Arbeit beschäftigt sich mit der Clusteranalyse von Benutzerdaten auf Web-Portalen, um diese in homogene Gruppen zu unterteilen und personalisierte Dienste zu ermöglichen.
Welche zentralen Themenfelder werden bearbeitet?
Zu den Schwerpunkten zählen die theoretischen Grundlagen der Clusterbildung, klassische Algorithmen (z.B. K-means), die Erstellung von komplexen Benutzerprofilen und deren Anwendung im Web Mining.
Was ist das primäre Forschungsziel?
Das Ziel ist es, einen Überblick über existierende wissenschaftliche Arbeiten im Bereich des Web Mining zu geben und die Eignung klassischer Clusterverfahren für die Segmentierung von Benutzerprofilen zu untersuchen.
Welche wissenschaftlichen Methoden kommen zum Einsatz?
Die Arbeit nutzt methodische Ansätze aus der Clusteranalyse, wie hierarchische und partitionierende Verfahren sowie Fuzzy- und wahrscheinlichkeitsbasierte Modelle, und bewertet diese hinsichtlich ihrer Anwendbarkeit.
Was deckt der Hauptteil der Arbeit inhaltlich ab?
Der Hauptteil behandelt neben den Grundlagen und Algorithmen detailliert die Erstellung von "Non-obvious user profiles" (NOPs) und analysiert verwandte Forschungsansätze im Web-Mining-Umfeld.
Welche Begriffe charakterisieren die Arbeit am besten?
Begriffe wie Web Usage Mining, Benutzercluster, K-means-Algorithmus, Distanzmaße und Navigationsanalyse fassen die Arbeit prägnant zusammen.
Was zeichnet die "Non-obvious user profiles" aus?
Im Gegensatz zu expliziten Benutzerdaten spiegeln NOPs das implizite Verhalten der Nutzer (z.B. Navigationspfade, Verweildauer) über mehrere Sessions wider, um Interessen präziser zu erfassen.
Warum ist die Wahl des Distanzmaßes für die Clusterbildung entscheidend?
Distanzmaße bestimmen, wie Ähnlichkeit zwischen Objekten gemessen wird; eine falsche Wahl kann die Clusterbildung verfälschen, insbesondere wenn Merkmale unterschiedliche Einheiten oder Relevanzen haben.
Welche Rolle spielen Webportale für die Clusterbildung?
Webportale generieren große Mengen an Logfile-Daten, die eine wertvolle Basis für die Analyse des Benutzerverhaltens durch Clustering bieten, um beispielsweise personalisierte Inhalte auszuspielen.
- Quote paper
- Björn Brandt (Author), 2006, Clustering und Evaluierung von Benutzerprofilen bei Web-Portalen, Munich, GRIN Verlag, https://www.grin.com/document/56106
