Clustering und Evaluierung von Benutzerprofilen bei Web-Portalen

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

1 Einleitung
1.1 Einf ührung in Information Retrieval und Data Mining
1.2 Einf ührung in die Clusteranalyse
1.3 ÜberblicküberdieArbeit

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 Überwachtevs.unüberwachteVerfahren
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 MinkowskiMetrik
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 Cluster- bildung 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 ÄhnlichkeitsbasiertesClusternvonWebTransaktionen
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 Web- site
6.6.1 Hybrider Clusteralgorithmus
6.7 ÄhnlichkeitsbestimmungzwischenInteressenzurClusteranalyse
6.7.1 Ähnlichkeitsmaße
6.7.2 Matrixbasierter Clusteralgorithmus
6.8 Clusteranalyse anhand von längsten, gemeinsamen Teilpfaden .
6.8.1 ÄhnlichkeitzwischenPfaden
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 Assoc_iation 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

Literaturverzeichnis

Abbildungsverzeichnis

1.1 Data Mining als ein Schritt im Prozess des KDD. Quelle:[10]. .

1.2 Visualisierung von Clustern f ür zwei Merkmale F und G

2.1 Visualisierung von drei sich überlappenden Clustern f ür zwei Merkmale S und T bei einer vollständigen Clustereinteilung . .

2.2 Dendrogramm eines hierarchischen Clusterings

2.3 Unterschied zwischen überwachten und un überwachten Clu- sterverfahren. Quelle:[8]

2.4 Prinzip der Nächste-Nachbarn-Verfahren. Quelle:[2]

2.5 Problematik der Skalierung. Quelle:[22]

2.6 Cluster-Repräsentation durch einen Klassifikationsbaum oder konjunktivische logische Ausdr ücke. Quelle:[23]

3.1 Ein minimaler Spannbaum. Quelle:[23]

3.2 3-means Clustering (k = 3). Quelle:[26]

3.3 Wahrscheinlichkeitsdichtefunktion f ür zwei Cluster A und B Quelle:[50]

3.4 Konvergenz des EM-Algorithmus. Quelle:[20]

5.1 Visualisierung der NOPs im Koordinatensystem

6.1 Beispiel eines CF-Baumes. Quelle:[53]

6.2 Baumstruktur einer Website. Quelle:[43]

6.3 Evaluierung der erstellten Clustereinteilung. Quelle:[43]

6.4 Wahl des Schwellwertes ϑ. Quelle:[51]

6.5 Systemarchitektur. Quelle:[29]

7.1 Systemarchitektur inkl. Proxy-Server

7.2 Vergleich der Präzision zwischen PPM und vob-PPM. Quelle:[51]

Tabellenverzeichnis

2.1 Bedeutung der Parameter der verallgemeinerten Minkowski- Metrik. Quelle:[2]

2.2 Merkmale mit binärem Wertebereich. Quelle:[20]

3.1 Beispiel der Zugeh örigkeitsgrade von 4 Objekten zu 3 Clustern

4.1 NOPs von f ünf Benutzern der Website bei vier vorgegebenen Themen. Quelle:[32]

Danksagung

An dieser Stelle m öchte ich all jenen danken, die durch ihre fachliche und pers önliche Unterst ützung zum Gelingen dieser Diplomarbeit und des gesamten Studiums beigetragen haben.

Ich bedanke mich bei Herrn Prof. Dott.-Ing. Roberto Zicari f ür das Bereitstellen des Themas dieser Diplomarbeit und die freundliche Hilfsbereitschaft, die er mir entgegenbrachte. Ihm und insbesondere Frau Dipl.-Inf. (FH) Natascha Hoebel danke ich f ür die sehr gute Betreuung meiner Diplomarbeit. Die zahlreichen wissenschaftlichen Ratschläge und fachlichen Diskussionen haben stets zur Verbesserung der Arbeit beigetragen.

Ein ganz besonderer Dank geb ührt meinem Studienkollegen Frank Stolarc- zyk. Die fachlichen Diskussionen, die gemeinsam gel östen Übungsaufgaben, die zusammen durchgef ührten Praktika und die gemeinsamen Vorbereitun- gen auf die Pr üfungen während des gesamten Studiums haben entscheidend zu unserem erfolgreichen und schnellen Informatik-Studium beigetragen. Ich danke ihm f ür seine Unterst ützung, Motivation, Kritik und Bereitschaft rund um die Uhr. Während der gemeinsamen Jahre hat sich auch im privaten Um- feld eine gefestigte Freundschaft entwickelt, die sich ebenfalls zu einer beruf- lichen Partnerschaft entwickeln soll.

Aufrichtiger Dank geb ührt meinen Eltern, die mir dieses Studium durch ihre Unterst ützung in allen Lebensbereichen erm öglicht und die materiellen Grundlagen gelegt haben. Einen großen Ansporn f ür mein z ügiges Studium habe ich meinem Vater, Dr. Winfried Brandt, zu verdanken. Er stellt mir eine erfolgversprechende berufliche Zukunft in Aussicht.

Meiner Frau Jenny m öchte ich meinen herzlichsten Dank aussprechen. Sie hat mir die Sorgen des Alltags abgenommen und mich tatkräftig unterst ützt, so dass ich 100% meiner Zeit dem Studium widmen konnte. Ich danke ihr f ür die Geduld, die sie während meiner Zeit an der Universität und der Entstehung dieser Arbeit aufbrachte.

Kapitel 1 Einleitung

1.1 Einführung in Information Retrieval und Data Mining

Zum einen lässt in den letzten Jahren die zunehmende Verbreitung von elek- tronischen Medien die Menge der Daten, die digital zur Verf ügung stehen, im- mer weiter anwachsen. Umfassende digitalisierte Datensammlungen werden von Wirtschaftsunternehmen, aber auch wissenschaftlichen und staatlichen Einrichtungen aufgebaut. Durch die ebenfalls ansteigende weltweite Vernet- zung von Rechnern werden diese Informationen f ür immer mehr Menschen zugänglich.[11]

Zum anderen hat die Konvergenz von Informatik und Telekommunikation ei- ne Gesellschaft geschaffen, die von Informationen lebt. Allerdings ist ein Groß- teil der vorhandenen Informationen nur in Rohform als Datensammlung vor- handen.[50]

Eine anspruchsvolle Aufgabe besteht unter anderem darin, diese Datensammlungen auszuwerten und zu analysieren, d.h. in wenig koordinierten und kontrollierten Datensammlungen die relevanten Informationen zu finden. Diese inhaltliche Suche ist in der Literatur als Information Retrieval bekannt. Die Gewinnung impliziter, bislang unbekannter und potenziell n ützlicher Informationen aus Daten wird nach[50] als Data Mining ¹ bezeichnet. Zu diesem Zweck werden Algorithmen entwickelt, die Datenbanken automatisch durchforsten und dabei nach Regelmäßigkeiten oder Mustern suchen.

F ür die Wissensgewinnung aus Datensammlungen (Knowledge Discovery in Da- tabases (KDD)) gibt Reginald Ferber in seinem Buch folgende Definition: ”Know- ledge Discovery in Databases (KDD) beschreibt automatisierte Verfahren, mit denen Regelmäßigkeiten in Mengen von Datensätzen gefunden und in eine f ür Nutzende verständliche Form gebracht werden.“ [11]

In der Literatur finden sich zwei verschiedene Definitionen des Data Mining Begriffes:

1. Data Mining ist ein Synonym fur den Begriff des KDD. Ein Vertreter dieser Ansicht ist Reginald Ferber [11].

2. Data Mining wird angesehen als ein notwendiger Schritt im mehrstu- figen Prozess des KDD (siehe Abbildung 1.1). Dieser Schritt besteht aus Algorithmen, die in einer Datensammlung Strukturen ausfindig machen. Vertreter dieser Ansicht sind u.a. Jiawei Han und Micheline Kamber[19].

Auch Usama Fayyad[10] vertritt diese Ansicht: ”In our view,KDD refers to the overall process of discovering useful knowledge from data, and data mining refers to a particular step in this process. Data mining is the application of spec_ific algorithms for extracting patterns from data.“

Der KDD-Prozess besteht nach [[19]] aus der Datensäuberung (data clea- ning), der Datenintegration (data integration), der Datenselektion (da- ta selection), der Datentransformation (data transformation), dem Data Mining, der Musterauswertung (pattern evaluation) und der Wissensre- präsentation (knowledge presentation). In [[19]] wird detailliert auf den KDD-Prozess eingegangen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Abbildung1.1: Data Mining als ein Schritt im Prozess des KDD. Quelle: [[10]]

1.2 Einführung in die Clusteranalyse

Die Clusteranalyse ist ein Analyseverfahren im Data Mining, das Strukturen in einer Sammlung von Daten erkennt. Sie ist ein Werkzeug zur explorativen Da- tenanalyse. Sie ist besonders in den betriebswirtschaftlichen Bereichen Mar- keting und Vertrieb von Bedeutung, um die Identifikation und Analyse ho- mogener Kundengruppen zu unterst ützen. Diese Gruppen k önnen dann ge- zielt durch das Unternehmen kontaktiert werden. Gerade bei großen Einzel- handelsunternehmen ist nicht mehr jeder einzelne Kunde pers önlich, sondern dem Unternehmen nur durch die Aufzeichnung der Geschäftsprozesse be- kannt, die durch die Kunden generiert wurden. Basierend auf diesen Geschäfts- prozessinformationen, die in unserem Sinne eine Datensammlung repräsen- tieren, werden die Kundendaten durch Clusteringverfahren segmentiert. Die Kunden innerhalb einer Gruppe sind hinsichtlich der betrachteten Informatio- nen homogen, d.h. sie haben beispielsweise dieselben Produkte gekauft und stellen daher eine einheitliche Kundengruppe dar.[41]

Das Ziel der Clusteranalyse besteht darin, eine Menge von Objekten (automatisiert) in Gruppen bzw. Cluster einzuteilen. Dabei versteht man unter der Einteilung in Cluster, dass[22]

- die Objekte einer Gruppe untereinander m öglichst ähnlich sind (Homogenit ä t innerhalb eines Clusters);
die Objekte je zwei verschiedener Cluster m öglichst unterschiedlich sind (Heterogenit ä t zwischen den Clustern).

Anschaulich kann man ein Cluster als eine Sammlung nahe beieinanderliegender Objekte interpretieren. Im dreidimensionalen Raum, bei Betrachtung von drei Merkmalen, erkennt man ein Cluster in Gestalt einer Punktwolke. Je mehr Merkmale einer Datensammlung in eine Clustereinteilung einfließen, desto h öherdimensional wird die Betrachtung. Eine Visualisierung f ür mehr als drei Merkmale ist nicht m öglich. Die in Abbildung 1.2 untersuchten Objekte bilden in den beiden Merkmale F und G vier Cluster.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.2: Visualisierung von Clustern f ür zwei Merkmale F und G

Es gibt eine große Anzahl an Clusteranalyseverfahren. Es w ürde allerdings den Rahmen sprengen, auf jedes in der Literatur bekannte Clusteranalyseverfahren im Detail in dieser Arbeit einzugehen.

Im Rahmen dieser Diplomarbeit wird auf die Clusteranalyse von Benutzer- profilen, die u.a. an der Professur f ür Datenbanken und Informationssysteme der Johann Wolfgang Goethe-Universität Frankfurt entwickelt wurden, ein- gegangen[32]. Benutzerprofile k önnen in vielerlei Hinsicht geclustered wer- den. Man denke beispielsweise an eine Gruppierung von Web-Usern anhand von Themen. Interessante Fragestellungen in diesem Zusammenhang sind si- cherlich, welche und wie viele Web-User sich f ür die gleichen Themen einer Website interessieren oder welche Interessensänderungen im Laufe der Zeit auftreten. Diese und andere Fragen lassen sich mit Unterst ützung der Cluster- analyse beantworten.

1.3 Überblick über die Arbeit

Die Arbeit ist wie folgt organisiert.

In Kapitel 2 werden die grundlegenden Begriffe und formalen Definitionen der Clusteranalyse diskutiert. Es wird auf die NP-Härte 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 vor- gestellt.

Kapitel 5 gibt eine Beschreibung der Clusterbildung als Disziplin des Web Usa- ge 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: ”Waskannallesgeclustered werden?“ Im dritten und letzten Abschnitt des Kapitels[5] wird zunächst all- gemein und anschließend anhand eines Beispiels die Anwendung eines in der Praxis häufig eingesetzten, klassischen Clusterverfahrens auf non-obvious-user- profiles 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.

Kapitel 2 Grundlagen der Clusteranalyse

2.1 Begriffe und formale Definitionen

Nach Pullwitt[35] ist eine Clustereinteilung eine Zerlegung einer Menge von Objekten in Teilmengen derart, dass die Objekte desselben Clusters zusammengeh örig sind, wohingegen die Objekte verschiedener Cluster eine geringere Zusammengeh örigkeit aufweisen. Formal k önnen wir die Clustereinteilung C folgendermaßen beschreiben:

Abbildung in dieser Leseprobe nicht enthalten

Die Zusammengeh ö rigkeit von Objekten wird gemäß[35] durch ein Maß f ür die Ä hnlichkeit s E (., .) bzw. den Abstand d E (., .) zwischen Objekten im Objek- traum E definiert. MaximaleÄhnlichkeit bzw. minimaler Abstand zwischen je zwei Objekten determinieren eine maximale Zusammengeh örigkeit innerhalb eines Clusters. Im Folgenden betrachten wir der Einfachheit halber nur das Abstandsmaß.

Eine Clustereinteilung C = { c 1, . . . , c k } einer Objektmenge E heißt nach[35] vollst ä ndig, wenn jedes Objekt e ∈ E einem Cluster zugeordnet ist. Andernfalls heißt die Einteilung partiell. F ür eine vollständige Clustereinteilung kann man infolgedessen schreiben:

Abbildung in dieser Leseprobe nicht enthalten

In Abbildung 1.2 ist eine vollständige Clustereinteilung gezeigt, da es kein Objekt gibt, das keinem der vier Cluster zugeordnet ist.

Eine Clustereinteilung C = { c 1, . . . , c k } heißt gemäß[35] nichtüberlappend, wenn kein Objekt mehr als einem Cluster zugeordnet ist. Andernfalls heißt die Einteilung ü berlappend. Man spricht also von einer nicht überlappenden Clustereinteilung, falls

Abbildung in dieser Leseprobe nicht enthalten

gilt. In Abbildung 1.2 ist eine nicht überlappende Clustereinteilung gezeigt, da jedes Objekt zu genau einem Cluster zugeordnet ist. In Abbildung 2.1 wird eine überlappende Clustereinteilung visualisiert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Visualisierung von drei sich überlappenden Clustern f ür zwei Merkmale S und T bei einer vollständigen Clustereinteilung

Ein Clusterverfahren ist nach[35] eine Methode, die eine Clustereinteilung be- stimmt. Man geht von der Objektmenge aus und verwendet ein geeignetes Maß f ür die Ähnlichkeit s E (., .) bzw. den Abstand d E (., .) zweier Objekte.

Cluster c k önnen durch Repräsentanten c identifiziert werden, wenn ein metrischer Raum E mit der Metrik¹ d E (., .) verwendet wird. Der Repräsentant des Clusters c ist der Schwerpunkt bzw. Zentroid von c, der sich nach[35] durch Mittelwertbildung über alle Objekte des Clusters ergibt:

Abbildung in dieser Leseprobe nicht enthalten

In den Abbildungen[1].[2] und[2].[1] sind die Zentroide der Cluster als schwarze Quadrate gezeichnet.

Eine Partitionierung P eines Objektraumes E ist dessen disjunkte Zerlegung in Klassen P = { p 1, . . . , p l }, d.h. es gelten

Abbildung in dieser Leseprobe nicht enthalten

Die Partitionierung ist damit eine vollständige Clustereinteilung mit nicht ü- berlappenden Clustern. Man spricht in diesem Zusammenhang auch von Seg- mentierung.

Die Begriffe der Abstandsfunktion und der Distanz d (x, y) zwischen je zwei Objekten x und y werden in Abschnitt 2.5.1 definiert. Die Distanz d C (c i, c j) gibt den Abstand zwischen je zwei Clustern c i und c j an. Näheres zu d C (c i, c j) und dessen Bestimmung siehe Abschnitt 2.4.

2.2 Optimales Clustern ist NP-hart

Grundsätzlich ist bei Aussagen der Kombinatorik zu differenzieren, ob es sich um unterscheidbare oder ununterscheidbare Objekte und Klassen handelt. Es werden im Folgenden endlich viele unterscheidbare Objekte einer Datensammlung betrachtet. Da deshalb auch die Menge m öglicher Cluster endlich ist, k önnte man versucht sein, das Problem der Clustereinteilung von n Objekten in k Cluster mit naiver Herangehensweise dadurch zu l ösen, alle m öglichen Clustereinteilungen zu untersuchen.

2.2.1 Objekte in unterscheidbaren Clustern

Wenn erlaubt wird, dass Cluster leer sein d ürfen, ist es relativ einfach, eine Aussage dar über zu treffen, wie viele Kombinationsm öglichkeiten es gibt, n Objekte in k Cluster einzuteilen. Es gibt f ür jedes der n Objekte k M öglichkeiten, es einem Cluster zuzuordnen. Damit ergeben sich

Abbildung in dieser Leseprobe nicht enthalten

verschiedene Clustereinteilungsm öglichkeiten. Die Anzahl der verschiedenen Clustereinteilungen wächst exponenziell in n.

Wenn kein Cluster leer bleiben darf, wird es komplizierter, die Anzahl der m öglichen Clustereinteilungen zu bestimmen. Es wird angenommen, dass die Reihenfolge innerhalb der Cluster nicht relevant ist. Die Anzahl m öglicher Clustereinteilungen von n Objekten in k Cluster wird nach[27] bestimmt durch

Abbildung in dieser Leseprobe nicht enthalten

Dabei ist S(n, k) definiert als[Abbildung in dieser Leseprobe nicht enthalten]und ist in der Literatur als die Stirling-Zahl zweiter Art bekannt. Die Stirling-Zahl zweiter Art bestimmt also die Anzahl der k-Partitionen einer n-elementigen Menge von Objekten.[27]

2.2.2 Objekte in ununterscheidbaren Clustern

Die Anzahl der M öglichkeiten, n Objekte in k ununterscheidbare Cluster einzuteilen ist nach[27] gleich S (n, k).[4]

Sollen beispielsweise n Objekte 2 ununterscheidbaren Clustern zugeordnet werden, gibt es

Abbildung in dieser Leseprobe nicht enthalten

Möglichkeiten. Man sieht, dass es schon f ür den ”einfachen“Fallvonnurzwei vorgegebenen Clustern exponenziell in n viele m ögliche Clustereinteilungen gibt, weshalb die naive Herangehensweise abzulehnen und nur von theoretischem Interesse ist.

2.2.3 Beweis nach Garey und Johnson

Garey und Johnson[16] beschreiben in ihrem Buch die NP -Härte des Clusterings wie folgt:

Gegeben eine endliche Menge X, eine ganzzahlige Distanz d (x, y) zwischen je zwei Objekten x und y und zwei positive Zahlen K und B. Frage: Gibt es eine Partition von X in disjunkte Mengen X 1, X 2, . . . , X k, so dass f ür alle Paare[Abbildung in dieser Leseprobe nicht enthalten] ?

Brucker[6] f ührt eine Reduktion dieses Clusteringproblems auf das NP -voll- ständige Problem der Dreifärbbarkeit von Graphen (3-COLORING) zur ück. Er hat damit die NP -Härte des Clusterings bewiesen. Garey und Johnson sind der Meinung, dass das Problem sogar f ür K = 3 und alle Distanzen d (x, y) ∈ [0, 1] NP -vollständig bleibt. F ür K = 2 wird das Clustereinteilungsproblem allerdings in polynomieller Zeit l ösbar.

Cluster-Algorithmen k önnen eine gute, suboptimale L ösung in polynomieller Zeit f ür ein fest vorgegebenes k bestimmen. Ist k variabel, d.h. nicht mehr fix, gibt es, falls [Abbildung in dieser Leseprobe nicht enthalten] angenommen wird, keine Algorithmen, die in polynomi- eller Zeit eine optimale Clustereinteilung der vorgegebenen Objekte berechnen. Alle diese Cluster-Algorithmen liegen in der Komplexitätsklasse NP.

2.3 Klassifikation der Clusterverfahren

In der Literatur werden auf oberster Stufe hierarchische von partitionierenden Clusterverfahren unterschieden.

Hierarchische Verfahren erzeugen eine hierarchische Clusterstruktur m öglicher Einteilungen, so dass die Objekte auf oberster Ebene in nur wenige Cluster unterteilt werden, die sich wiederum in eigene Cluster unterteilen etc.

Partitionierende Verfahren erstellen eine ”flache“PartitionderDatensamm- lung in k disjunkte Partitionen, ohne eine mehrstufige Clusterstruktur zu er- mitteln, nachdem die Anzahl k der gew ünschten Cluster vorgegeben wurde. [50] [23]

2.3.1 Hierarchische Clusterverfahren

Grundsätzlich werden agglomerierende (bottom-up Vorgehensweise) von divi- siven (top-down Vorgehensweise) Clusteringverfahren unterschieden[20].

Bei den agglomerierenden (anhäufenden) Verfahren wird initial jedes Objekt der Datensammlung als eigenes Cluster interpretiert. Es werden sukzessive ein- zelne, zueinander ähnliche Objekte zu Clustern und bereits erkannte Cluster zu gr ößeren Clustern verschmolzen bis der Abstand zwischen je zwei Clustern einen bestimmten Schwellwert übersteigt oder wenn nur noch ein großes Clu- ster übrig ist.[20]

Divisive (unterteilende) Verfahren beginnen anfänglich mit einem einzigen Cluster. Jedes Objekt der Datensammlung ist diesem Cluster zugeordnet. Anschließend werden immer neue (Teil-)Cluster erstellt, d.h. das urspr üngliche Cluster immer feiner unterteilt. Dieser Prozess dauert so lange an, bis nur noch Cluster bestehend aus Einzelobjekten übrig bleiben.[20]

Beiden Verfahrenstypen, agglomerierend wie divisiv, ist gemeinsam, dass eine Baumstruktur entsteht, die meist als Dendrogramm bezeichnet wird (siehe Abbildung 2.2). Die Tiefe eines Querbalkens in Abbildung 2.2 zeigt an, auf welcher Hierarchieebene Cluster verschmolzen werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Dendrogramm eines hierarchischen Clusterings

Es ist sowohl bei agglomerierenden als auch bei divisiven Clusterverfahren m öglich, den Algorithmus vorzeitig abzubrechen, wenn man eine bestimmte Hierarchieebene des Dendrogramms clustern m öchte. Im Falle eines agglomerierenden Verfahrens terminiert der Algorithmus also bevor nur noch ein Cluster übrig ist. Handelt es sich um ein divisives Verfahren so endet der Algorithmus bevor nur noch Cluster bestehend aus Einzelobjekten übrig bleiben. Dadurch wird meist eine Laufzeitverbesserung erreicht.

2.3.2 Partitionierende Clusterverfahren

Die Aufgabe partitionierender Clusterverfahren besteht darin, eine Datensamm- lung, ausgehend von einer initialen Partitionierung, in k disjunkte Mengen derart zu partitionieren, dass sich die Objekte innerhalb einer Gruppe so ähn- lich wie m öglich sind. Jedes Objekt wird einem eindeutigen Cluster zuge- wiesen. Es entsteht keine hierarchische Clusterstruktur[20]. Der Vorteil par- titionierender Clusterverfahren liegt in der Untersuchung sehr großer Daten- sammlungen, wo die Erstellung eines Dendrogramms nur schwer durchzu- f ühren ist.

Bei partitionierenden Clusterverfahren ist es notwendig, aber auch problema- tisch, 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Ä hnlichkeits- funktion (score function) bestimmt werden. Insbesondere kann durch die Be- rechnung der Kategorienützlichkeit (siehe Abschnitt 2.6) die Gesamtqualität ei- ner Aufteilung von Objekten in Cluster gemessen werden.[50]

Weiterhin werden die Clusterverfahren anhand folgender Kriterien differen- ziert.[23]

2.3.3 Disjunkte vs. nicht-disjunkte Verfahren

Die Clusteranalyseverfahren k önnen unterschieden werden in disjunkte (nicht-überlappende) und nicht-disjunkte (überlappende) Verfahren. Wird jedes Objekt genau einem Cluster zugeordnet, handelt es sich um ein disjunktes Verfahren. Kann ein Objekt zwei oder mehr Clustern zugeordnet werden, spricht man von einem nicht-disjunkten Clusteranalyseverfahren[5]. Einerseits nimmt mit dem Anteil derÜberlappungen die Heterogenität zwischen den Clustern ab. Wenn es zwischen zwei Clustern viele Objekte gibt, die zu beiden Clustern zu- geordnet werden k önnen, sind die Cluster nicht deutlich voneinander trenn- bar. Andererseits kann ein überlappendes Verfahren zu einer geringeren An- zahl von Clustern f ühren.[2]

2.3.4 Deterministische vs. probabilistische Verfahren

In der Literatur wird die Art und Weise, wie die Objekte Clustern zugeordnet werden, deterministisch oder probabilistisch, differenziert. Bei den deterministischen Verfahren werden die Objekte mit einer Wahrscheinlichkeit p = 0 oder p = 1 einem oder mehreren Clustern zugeordnet. Bei probabilistischen Clusteranalyseverfahren werden die Objekte mit einer Wahrscheinlichkeit p ∈ [0, 1] den Clustern zugeordnet.[2]

2.3.5 Monothetische vs. polythetische Verfahren

Das Unterscheidungskriterium zwischen monothetischen und polythetischen Ver- fahren ist die Anzahl der Merkmale, die parallel in die Berechnung der Clu- stereinteilung eingehen. Polythetische Algorithmen beziehen alle Merkmale simultan in die Berechnung der Abstände zwischen Clustern ein. Ein mono- thetischer Algorithmus betrachtet jeweils einzelne Merkmale sequenziell, d.h. nacheinander und nicht parallel, um die Datensammlung zu unterteilen. Die meisten Algorithmen zur Clustereinteilung sind polythetisch.

2.3.6 Scharfe vs. Fuzzy-Verfahren

Die Verfahren der Fuzzy-Clusteranalyse (possibilistische Verfahren) werden der Kategorie der probabilistischen Clusteringverfahren zugerechnet. Die Objekte werden den Clustern mit einem Zugeh örigkeitsgrad m X (d) ∈ [0, 1] zugewie- sen. m X (d) ist jedoch nicht als eine Wahrscheinlichkeitsgr öße zu deuten, wes- halb sich die Zugeh örigkeitsgrade auch nicht zu 1 aufsummieren brauchen. Ein Zugeh örigkeitsgrad von 0,95 bedeutet nicht, dass das Objekt dem betref- fenden Cluster mit einer Wahrscheinlichkeit von 95% zugeordnet wird. Statt- dessen sind die Zugeh örigkeitsgrade im Sinne der unscharfen Mengen (Fuzzy Sets) zu interpretieren, auf die in Abschnitt 3.3.1 noch näher eingegangen wird. [41]

Bei scharfen Verfahren kann der Zugeh örigkeitsgrad eines Objektes zu einem Cluster entweder 0 oder 1 sein. Es wird kein Wert zwischen 0 und 1 angenom- men.

Ein Fuzzy-Verfahren kann nach[23] in ein scharfes Verfahren konvertiert werden, indem das Objekt demjenigen Cluster zugeordnet wird, das den maximalen Zugeh örigkeitsgrad hat.

2.3.7 Inkrementelle vs. nicht-inkrementelle Verfahren

Es muss der Einsatz eines inkrementellen gegen über eines nicht-inkrementellen Clusteranalyseverfahrens abgewogen werden, wenn die zu clusternde Daten- sammlung sehr groß ist und es Zeit- und/oder Speicherplatzbeschränkungen gibt, die gefährden, dass der Algorithmus eingesetzt werden kann. Ein guter Algorithmus sollte sowohl die Anzahl der Durchläufe, die zum Clustern der Datensammlung n ötig ist, als auch die Anzahl der in einem Durchlauf un- tersuchten Objekte und weiterhin die Gr öße der benutzten Datenstrukturen minimieren.[23]

Beim inkrementellen Clustering werden die Objekte der Datensammlung ein- zeln und nacheinander betrachtet, wohingegen beim nicht-inkrementellen Clu- stering parallel alle Objekte in die Berechnung der Clustereinteilung einfließen. Beim inkrementellen Clustern entsteht ein Baum, dessen Blätter die Objekte sind. Die Wurzel repräsentiert die gesamte Datensammlung. Gestartet wird mit dem Baum, der nur aus der Wurzel besteht. Sukzessive werden die Objek- te der Baumstruktur hinzugef ügt. An welcher Stelle ein Objekt im Baum ein- gef ügt wird, entscheidet das Maß der Kategorien ützlichkeit (siehe Abschnitt 2.6). Der Nachteil von inkrementellen Verfahren ist, dass das entstehende Clu- stering von der Reihenfolge abhängt, in der die Objekte herangezogen werden.

2.3.8 Überwachte vs. unüberwachte Verfahren

Die Algorithmen zur Clustereinteilung werden dem Lernparadigma zugerechnet. Grundsätzlich werden in der Literatur zwei Arten des induktiven Lernens² voneinander unterschieden. F ür diese Unterscheidung sind die Begriffe Trainingsmenge und Testmenge fundamental.

Die Trainingsmenge ist eine endliche Menge von Objekten, auf der der Algorithmus die Erkennung von Clustern durchf ührt. Um die vom Algorithmus ermittelten Ergebnisse verifizieren zu k önnen, verwendet man eine weitere Menge endlich vieler Objekte, die so genannte Testmenge. Die Trainings- und Testmenge sind disjunkt.[11]

Man spricht vom ü berwachten Lernen (supervised learning), wenn eine Trainingsmenge gegeben ist, die den Algorithmus bei der Berechnung von Clustern unterst ützt. Der Algorithmus nutzt aus, dass es bereits eine Menge von Objekten gibt, die als Repräsentanten f ür ein Cluster angesehen werden k önnen. Das sind die Objekte der Trainingsmenge. Der Algorithmus bestimmt Cluster, indem er die Objekte der Testmenge demjenigen Repräsentanten der Trainingsmenge zuordnet, dem das Objekt am ähnlichsten ist. Die Trainingsmenge gibt eine grobe Strukturierung der Objekte vor.

Beim unüberwachten Lernen (unsupervised learning) geht es darum, Strukturen in einer noch unstrukturierten Datensammlung zu entdecken, ohne dass eine Trainingsmenge vorhanden ist[26]. Es sind daher keine vorklassifizierten Objekte vorhanden, die helfen, Cluster zu finden und der Algorithmus muss eine Einteilung in Cluster selbst finden.

In Abbildung 2.3 ist der Unterschied zwischen überwachtem und un über- wachtem Clustering visualisiert. Die weißen und schwarzen Kreise repräsen- tieren zwei verschiedene Objekttypen einer Datensammlung. Ein un überwach- tes Clusterverfahren w ürde (sehr wahrscheinlich) die Cluster in Abbildung 2.3 (a) identifizieren, wohingegen ein überwachtes Clusterverfahren die in Abbil- dung 2.3 (b) eingezeichneten Cluster berechnet. Das liegt offensichtlich dar- an, dass das überwachte Clusterverfahren anhand der Trainingsmenge gelernt hat, dass es zwei verschiedene Objekttypen gibt und diese separat gruppiert. Das un überwachte Clusterverfahren kennt keine Trainingsmenge und grup- piert lediglich Objekte, die räumlich sehr nahe beieinander liegen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Unterschied zwischen überwachten und un überwachten Clu- sterverfahren. Quelle:[8]

2.3.9 Unvollständige vs. vollständige Verfahren

Bei unvollst ä ndigen Clusterverfahren handelt es sich um geometrische Metho- den, die zu einer niedrigdimensionalen, räumlichen Darstellung der Objek- te f ühren. F ür mehrdimensionale Daten wird eine Reduktion der Dimensio- nen durchgef ührt, beispielsweise durch eine Hauptkomponentenanalyse ³, um sie zwei- oder dreidimensional graphisch darstellen zu k önnen. Die Clusterbil- dung erfolgt dann manuell durch augenscheinliche Betrachtung der Daten, d.h. der Anwender selbst, nicht das Clusterverfahren, f ührt die Zuordnung der Objekte zu Clustern durch eine Interpretation der räumlichen Darstellung durch. Der Vorteil unvollständiger Verfahren liegt in der Anschaulichkeit der Daten.[2],[22]

Vollst ä ndige Clusterverfahren f ühren die Zuordnung von Objekten zu Clustern ohne zusätzlichen Eingriff des Anwenders durch, meist ohne Anwendung graphischer Methodik.[2]

2.4 Prinzipien zur Bildung der Cluster

Es gibt im Wesentlichen nur vier Prinzipien zur Bildung von Clustern, auf denen alle in der Literatur diskutierten Clusterverfahren basieren[2]. Diese werden nun vorgestellt.

1. N ä chste-Nachbarn-Verfahren: Die Cluster werden derart gebildet, dass

a) jedes Objekt der Datensammlung eine bestimmte Anzahl nächster Nachbarn in demjenigen Cluster hat, dem es zugeordnet ist oder
b) jedes Objekt der Datensammlung in dem Cluster zumindest einen B -ten nächsten (z.B. einen drittnächsten) Nachbarn hat.

Im Fall a) gilt ein Objekt x als ein nächster Nachbar zu einem Objekt y, falls x eineÄhnlichkeit zu y hat, die betragsmäßig gr ößer oder gleich einem bestimmten, vorher festgelegten Schwellwert (threshold) ist. Diese Vorstellung ist in Abbildung 2.4 graphisch dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: Prinzip der Nächste-Nachbarn-Verfahren. Quelle:[2]

In Abbildung 2.4 a-1) ist dargestellt, dass alle Objekte, die ein- und demselben Cluster angeh ören, nächste Nachbarn zueinander sein m üssen. Dies entspricht dem Complete-Linkage (= Methode des weitest entfernten Nachbarn, Maximum-Methode). Die Distanz d C (c i, c j) zweier Cluster c i und c j wird im Complete-Linkage definiert als der maximale Abstand über allen Objektpaaren aus den Clustern:

Abbildung in dieser Leseprobe nicht enthalten

Dadurch, dass das Maximum über die Abstände der Objekte gebildet wird, ergeben sich kleine, stark abgegrenzte Cluster, d.h. alle Objekte desselben Clusters weisen einen geringen paarweisen Abstand zueinan- der auf, weswegen eine sehr starke Homogenität innerhalb des Clusters die Folge ist[35]. Graphentheoretisch bezeichnet man ein solches Clu- ster, das einen vollständigen Graphen beschreibt, als Clique [2].

Abbildung 2.4 a-3) repräsentiert die Basis des Single-Linkage (= Methode des n ä chsten Nachbarn, Minimum-Methode). Jedes Objekt des Clusters hat mindestens einen nächsten Nachbarn. Der Abstand d C (c i, c j) zweier Cluster c i und c j wird im Single-Linkage als minimaler Abstand über allen Objekten aus den Clustern bestimmt:

Abbildung in dieser Leseprobe nicht enthalten

Inhomogene Cluster sind die Folge. So kann über ein einzelnes Objekt eine Kette von weiteren Objekten zugeordnet werden, die zu den rest- lichen Clusterobjekten einen hohen Abstand aufweisen. Die resultieren- den Cluster haben eine starke Streuung und langgezogene Strukturen. [35]

Abbildung 2.4 a-2) zeigt einen Ansatz, bei dem jedes Objekt des Clu- sters mindestens zwei nächste Nachbarn besitzen soll. Allgemein spricht man hier nicht von zwei sondern von B nächsten Nachbarn. Bekanntlich kann ein Objekt einer Datensammlung mit n Objekten maximal n − 1 Nachbarn besitzen, so dass f ür B angefangen beim erstnächsten Nach- barn bis zum (n − 1)-nächsten Nachbarn alle Werte zulässig sind. Die Berechnung der Distanz d C (c i, c j) zwischen je zwei Clustern c i und c j sollte sich in diesem Fall zwischen den beiden Extremen des Single- und des Complete-Linkage bewegen.

2. Mittelwertmodelle: Die Cluster werden durch Mittelwertbildung über den Abstand je zweier Objekte innerhalb der Cluster und/oder je zweier Cluster beschrieben. Formal ergibt sich der Abstand d C (c i, c j) zweier Cluster c i und c j als durchschnittlicher Abstand (Average Linkage) über allen Objektpaaren der Cluster:

Abbildung in dieser Leseprobe nicht enthalten

Die Clusterstrukturen, die durch die Mittelwertmodelle erzeugt werden, ordnen sich zwischen den langgezogenen Ketten des Single Linkage und den stark abgegrenzten Clustern des Complete Linkage ein.[35]

3. Objekte als Repr ä sentanten der Cluster (Repr ä sentanten-Verfahren): Jedes Clu- ster wird durch ein f ür dieses Cluster typisches Objekt beschrieben. Die- ses Objekt nennt man Repr ä sentant. Die Aufgabe des Clusterverfahrens besteht in diesem Fall also darin, Repräsentanten in der Datensammlung zu finden. Sind die Repräsentanten gefunden, bleibt es, die verbleiben- den, nicht typischen Objekte demjenigen Cluster zuzuordnen, dessen Repräsentanten sie am ähnlichsten sind. Alternativ werden diese Ob- jekte keinem Cluster zugewiesen, wenn die Ähnlichkeitzumnächsten Repräsentanten zu klein, d.h. der Abstand zu groß ist.

Anwendung finden die Repräsentanten-Verfahren vor allem in Bereichen, in denen kein metrischer Raum⁴ vorliegt, d.h. eine Distanzberechnung zwischen je zwei Objekten nicht m öglich ist. Ein Beispiel hierf ür ist die Clusteranalyse von DNA-Strukturen.

4. Clusterzentren als Repr ä sentanten (Verfahren zur Konstruktion von Cluster- zentren): Im Unterschied zum Repräsentanten-Verfahren, wo ein einzel- nes Objekt Repräsentant eines Clusters ist, wird hier angenommen, dass ein Cluster durch seinen Zentroid (siehe Definition auf S. 6) charakteri- siert werden kann. In diesem Fall dr ückt man den Abstand der Cluster c_i und c_j uber den Abstand ihrer Zentroide c_i und c_j aus:

Abbildung in dieser Leseprobe nicht enthalten

Wie man sieht, fällt die Distanzberechnung bei diesen Clusterverfahren weniger komplex aus, als bei den anderen, zuvor aufgef ührten Verfahren. Vielmehr kann die Distanz d C (c_i, c_i) in konstanter Zeit O (1) berechnet werden. Bei den Mittelwertmodellen ist im Gegensatz dazu eine Zeit O (# ci · # cj) nötig. Auch der Speicherplatzbedarf ist bei diesen Verfahren geringer, da ein Cluster durch seinen Zentroid repräsentiert wird und nicht, wie bei den anderen Verfahren, durch die Vereinigung aller Objekte, die diesem Cluster zugeordnet sind.[35]

Die Cluster werden so bestimmt, dass

a) die Zentroide je zweier Cluster maximalen Abstand voneinander haben oder
b) die Streuung zwischen den Zentroiden maximiert wird.

Sowohl das Complete Linkage-Verfahren als auch das Single Linkage-Verfahren wie auch das Average Linkage-Verfahren sind hierarchische, agglomerieren- de und deterministische Clusterverfahren. Konkrete Clusteralgorithmen, wie beispielsweise das k -means-Verfahren, die diesen Prinzipien zugeordnet wer- den k önnen, werden in Kapitel 3 diskutiert. Zunächst f ühren wir die wichti- gen Konzepte der Abstandsfunktion und des Distanzmaßes ein, die f ür das Verständnis der anschließend erläuterten Clusteralgorithmen essenziell sind.

2.5 Abstandsfunktionen

2.5.1 Begriffe, Definitionen

Fast alle Clusterverfahren basieren auf Abstands- oderÄhnlichkeitsmaßen zwi- schen Objekten der Datensammlung und fordern, dass der Abstand zwischen je zwei verschiedenen Objekten berechnet werden kann, um zu entscheiden, ob zwei Objekte zueinander ähnlich sind. Damit sowohl Distanzen als auch Ähnlichkeitenformalberechnetwerdenkönnen,wirdimFolgendenderBe- griff der Abstandsfunktion definiert und anschließend die am häufigsten verwendeten Abstandsmaße aufgef ührt.[37]

Es sei M die Menge aller Objekte der Datensammlung. Eine Abbildung d: M × M → R, die jedem Paar von Objekten eine reelle Zahl zuweist, heißt Abstandsfunktion, wenn für beliebige[Abbildung in dieser Leseprobe nicht enthalten]

Abbildung in dieser Leseprobe nicht enthalten

mit [Abbildung in dieser Leseprobe nicht enthalten]ist minimal, falls x = y. Bedingung (2.4) beschreibt die Symme- trieeigenschaft der Abstandsfunktion. d heißt eine metrische Abstandsfunktion, falls zusätzlich

Abbildung in dieser Leseprobe nicht enthalten

gilt. Bedingung (2.6) beschreibt die Dreiecksungleichung. Den mathematischen Begriff der Metrik erhält man, indem man d 0 = 0 fordert[37].

2.5.2 Wichtige Distanzmaße für metrische Variablen

2.5.2.1 Distanzmaße auf Basis der verallgemeinerten Minkowski-Metrik

Die im Folgenden vorgestellten Distanzmaße haben sich in der Literatur als wichtig herausgestellt und lassen sich aus der verallgemeinerten Minkowski-

Abbildung in dieser Leseprobe nicht enthalten

ableiten[2]. Dabei bezeichnet d (q, r) s, t den Abstand zwischen den Objekten s und t mit Parameter q und [Abbildung in dieser Leseprobe nicht enthalten]bezeichnet die i -te Koordinate des Objektes s, d.h. die Koordinate der Dimension i.

Der Summationsindex i iteriert über alle Dimensionen; in jeder Dimension wird die Differenz der Koordinatenwerte berechnet. Diese Differenzen werden mit einem konstanten Faktor r potenziert und anschließend mit dem Faktor[Abbildung in dieser Leseprobe nicht enthalten] potenziert, was äquivalent zu einer q -ten Wurzel ist.

Indem man f ür die Parameter q und r der Minkowski-Metrik bestimmte Werte einsetzt, erhält man f ür

Abbildung in dieser Leseprobe nicht enthalten

Der Parameter r bewirkt, dass die Differenzen zwischen den Variablen einer Dimension gewichtet werden. Je gr ößer der Metrikparameter r desto stärker werden gr ößere Differenzen in weniger Variablen gewichtet als kleine Differenzen in vielen Variablen.[2]

2.5.2.2 Ein Beispiel zur verallgemeinerten Minkowski-Metrik

Ein Beispiel aus[2] soll die Anwendung der Minkowski-Metrik verdeutli- chen. Es wird die Unähnlichkeit des Profils⁵ s = (2, 1, 1, 2) zu den Profilen t = (1,2,2,2) und u = (2,1,1,5) berechnet. Die Profile s und t differieren we- nig in den einzelnen Komponenten, während bei s und u nur eine große Ab- weichung in der letzten Komponente des Profils vorliegt. In Tabelle 2.1 sind die Werte der Minkowski-Metrik f ür dieses Beispiel dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.1: Bedeutung der Parameter der verallgemeinerten Minkowski- Metrik. Quelle:[2]

Betrachten wir den Fall r = q. Die Unähnlichkeit zwischen s und t nimmt mit dem Parameter r ab, da den vielen kleinen Abweichungen in der Berechnung ein immer kleineres Gewicht beigemessen wird. Die Ähnlichkeitnimmtzu. Die Unähnlichkeit zwischen s und u bleibt konstant. s und u werden im Ver- gleich zu s und t mit zunehmendem Metrikparameter unähnlicher. Der Me- trikparameter q hat die Funktion einer R ücknormierung auf die urspr üngliche Skaleneinheit. Zur Verdeutlichung des Effektes der R ücknormierung wurde in der Tabelle auch mit q = 1 gerechnet. Man sieht, dass der Effekt der Gewich- tung mit dem Parameter r mit konstantem q immer stärker ausfällt. Während f ür r = q = 10 die Distanz zwischen s und u ca. 2,7 mal so groß ist wie zwi- schen s und t, ist sie f ür r = 10 und q = 1 bereits 19.683 mal so groß. Mit Aus- nahme der quadrierten euklidischen Distanz wird in der Regel r = q gewählt.

2.5.2.3 Probleme der diskutierten Distanzmaße

Die oben genannten, auf der verallgemeinerten Minkowski-Metrik basieren- den Distanzmaße gehen von der Annahme aus, dass die Objekte, zwischen denen eine Distanz gemessen werden soll, vergleichbar sind. Mit ihr k önnen nur Distanzen zwischen solchen Objekten berechnet werden, die die gleiche Einheit aufweisen, d.h. zuvor geeignet skaliert wurden. Beispielsweise k önnte das eine Objekt das Merkmal mal ”Gewicht“und das andere Objekt das Merk- ”Länge“haben. Die Distanz dieser beiden Objekte könnte mit der Eu- klidischen Distanz nicht berechnet werden, da ”Gewicht“und ”Länge“nicht vergleichbar sind[20].

Es ist bei der Verwendung eines Distanzmaßes vielmehr darauf zu achten, dass [[22]]

- die einzelnen Merkmale der Objekte, nach denen geclustered werden soll, oft unterschiedlich wichtig/relevant f ür das Clustering sind und
- die Merkmalsausprägungen verschiedene Maßstäbe/Einheiten aufweisen und damit a priori nicht vergleichbar sind.

In Abbildung 2.5 ist die Problematik der Skalierung graphisch dargestellt. In der linken Grafik sind vier Objekte A, B, C, D eingezeichnet, die zur Bildung der Cluster { A, B } und { C, D } f ühren. In der rechten Grafik wurde die Skalierung der x - und der y -Achse modifiziert, so dass dieselben Objekte auf der x -Achse enger beieinander, auf der y -Achse weiter auseinander liegen. Infolgedessen werden die Cluster { A, C } und { B, D } erstellt.[22]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.5: Problematik der Skalierung. Quelle:[22]

Diesen Beschränkungen wird im Folgenden Rechnung getragen, indem die Merkmale auf eine einheitliche Skala transformiert und anschließend gewichtet werden[20].

2.5.2.4 Transformation auf eine einheitliche Skala

Eine übliche Strategie ist, die Werte der Merkmale (= Merkmalsausprägungen) der Objekte zu standardisieren, indem jede Merkmalsausprägung durch die Standardabweichung des Merkmals dividiert wird[20]. Die Standardabweichung f ür das k -te Merkmal X k eines Objektes berechnet sich als

Abbildung in dieser Leseprobe nicht enthalten

Um den angestrebten Effekt der einheitlichen Skala und damit der Vergleichbarkeit von Objekten zu erhalten, werden neue Merkmalsausprägungen

Abbildung in dieser Leseprobe nicht enthalten

berechnet.[20]

2.5.2.5 Gewichtung der Merkmale

Sind die Merkmale, nach denen geclustered werden soll, unterschiedlich relevant f ür das Clustering, so k önnen sie (im Anschluss an die eben beschriebene Standardisierung) mit dem Faktor w i gewichtet werden. Es wird die gewichtete Euklidische Distanz bestimmt:[20]

Abbildung in dieser Leseprobe nicht enthalten

Sowohl die Euklidische- als auch die gewichtete Euklidische Distanz sind insofern additiv, als die Merkmale unabh ä ngig voneinander einen Beitrag zum Distanzmaß leisten. Dieser Effekt ist nicht immer gew ünscht. Das im Folgenden beschriebene Extrembeispiel verdeutlicht diesen Sachverhalt.[20]

2.5.2.6 Die Mahalanobis-Distanz

Angenommen, es werden die H öhe und der Durchmesser einer bestimmten Anzahl von Tassen gemessen. Wenn die Einheiten beider Merkmale vergleich- bar sind, kann, basierend auf diesen Maßen, dieÄhnlichkeit zwischen je zwei verschiedenen Tassen bestimmt werden. Das Problem besteht darin, dass die Höhe einer Tasse 100 Mal, der Durchmesser hingegen nur ein einziges Mal ge- messen wird. Pro Objekt ”Tasse“existierenalso[101] Merkmale,[100] vonihnen haben bis auf Messfehler identische Werte.[20]

Wurde man die Euklidische Distanz zur Berechnung der Ähnlichkeitzwi- schen den Tassen benutzen, so w ürde die H öhe der Tasse dasÄhnlichkeitsmaß dominieren, jedoch tragen 99 Werte der H öhenmessungen überhaupt nichts zu dem Maß bei, das bestimmt werden soll. Die 99 Messungen sind perfekt korreliert zu der ersten H öhenmessung. Diese Redundanz soll durch die Ver- wendung der Kovarianzen zwischen den Merkmalen vermieden werden.[20]

Betrachtet werden n Objekte. Die Kovarianz zweier Merkmale X und Y mit Werten x(1),...,x(n)bzw.y(1)...y(n)ist definiert als

Abbildung in dieser Leseprobe nicht enthalten

mit x als Mittelwert der Werte von X, y analog. Die Kovarianz zweier Objekte X und Y gibt an, wie stark die beiden Objekte zueinander geh ören/variieren. [20]

Man spricht von der Kovarianzmatrix, wenn die Kovarianzen von p vielen Merk- malen in einer (p × p)-Matrix dargestellt werden. Die Werte der Kovarianz und damit die Einträge der Kovarianzmatrix k önnen ebenfalls standardisiert werden. Dieser standardisierte Wert wird als Korrelationskoeffizient ρ bezeich- net und ist f ür zwei Objekte X und Y durch die Berechnungsvorschrift

Abbildung in dieser Leseprobe nicht enthalten

gegeben. Es ist m öglich, auch die Korrelationskoeffizienten in eine (p × p)Matrix einzutragen.[20]

Zur ück zum Beispiel der Tassen. Anhand der eben allgemein eingef ührten Begriffe kann der Effekt, der durch die 100 zueinander korrelierten H öhenmessungen entstand, durch die Einbeziehung der Kovarianzmatrix in dieÄhnlichkeitsberechnung beseitigt werden. Dieser Ansatz f ührt zur Mahalanobis-Distanz zwischen zwei Objekten s und t:[20]

Abbildung in dieser Leseprobe nicht enthalten

wobei [Abbildung in dieser Leseprobe nicht enthalten] die transponierte Variante des Vektors (x (s) − x (t)) ist, Σ die Kovarianzmatrix bezeichnet und Σ − [1] als Inverse der Kovarianzmatrix die Werte relativ zu Σ standardisiert. Es ist leicht nachzupr üfen, dass Formel 2.7 eine skalare Gr öße beschreibt.

2.5.2.7 Das Kosinusmaß

Um dieÄhnlichkeit zwischen zwei Vektoren q und d n mit eingeschlossenem Winkel α zu berechnen, kann unter anderem das Kosinusma ß herangezogen werden. Es ist wie folgt definiert:

Abbildung in dieser Leseprobe nicht enthalten

Das Kosinusmaß entspricht dem Skalarprodukt zweier Einheitsvektoren. Die berechnete Ähnlichkeit sim (q, d n) hängt nicht vom Betrag der Vektoren ab, sondern lediglich von deren Richtung. Die gr ößte Ähnlichkeit sim (q, d n) = cos(0 ◦) = 1 weisen beide Vektoren auf, wenn sie in dieselbe Richtung zeigen. Der Wertebereich von sim (q, d n) liegt zwischen -1 und 1.

2.5.3 Distanzmaße für Merkmale mit binärem Wertebereich

In diesem Abschnitt werden einige wichtige Distanzmaße f ür Objekte ein- gef ührt, deren Merkmale einen binären Wertebereich haben. Eine M öglichkeit besteht darin, die Anzahl n i, j der Merkmale zweier Objekte i und j zu bestim- men, an denen sich zwei Objekte gleichen oder voneinander unterscheiden. [20]

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.2: Merkmale mit binärem Wertebereich. Quelle:[20]

In Tabelle 2.2 nehmen alle Merkmale der Objekte i und j Werte aus { 0, 1 } an. Der Eintrag n 1,1 f ür i = 1 und j = 1 gibt an, dass es n 1,1 viele Merkmale gibt, in denen die Objekte i und j beide den Wert 1 annehmen. Ein offensichtliches Maß f ür dieÄhnlichkeit zweier Objekte, deren Merkmale einen binären Wertebereich haben, ist der matching-Koeffizient

Abbildung in dieser Leseprobe nicht enthalten

der den prozentualen Anteil der ubereinstimmenden Merkmale unter allen[Abbildung in dieser Leseprobe nicht enthalten] Merkmalen angibt.[20]

Manchmal ist es ungeeignet, die Zellen (0, 0) (oder (1, 1)) in dieÄhnlichkeits- berechnung mit einzubeziehen. Wenn beispielsweise die Merkmalsausprägung- en Werte über das Vorhandensein (1) oder die Abwesenheit (0) von bestimm- ten Eigenschaften sind, sollte man nicht die irrelevanten Eigenschaften be- trachten, die kein Objekt hat. Es ist nicht interessant zu wissen, welche Merkmalsausprägungen ein Merkmal nicht hat sondern welche es tatsächlich hat. Diese Betrachtung f ührt zu einer Modifikation des matching-Koeffizienten, die in der Literatur als Jaccard-Koeffizient bekannt ist:[20]

Abbildung in dieser Leseprobe nicht enthalten

Wenn tatsächlich alle (0, 0)-Zellen f ür dieÄhnlichkeitsberechnung irrelevant sind, ist es konsequent, anzunehmen, dass (0, 1)- und (1, 0)-Zellen bez üglich der Relevanz f ür die Ähnlichkeit zwischen (0, 0)- und (1, 1)-Zellen liegen soll- ten. Aus diesem Grund wird sowohl die Anzahl der (0, 1)-Zellen als auch der (1, 0)-Zellen mit 1/2 multipliziert. Man erhält den Dice-Koeffizienten [20]

Abbildung in dieser Leseprobe nicht enthalten

2.5.4 Aufstellen der Ähnlichkeitsmatrix

Die zwischen je zwei Objekten der Datensammlung berechnete Ähnlichkeit wird in einer Ä hnlichkeitsmatrix bzw. Distanzmatrix gespeichert.Wenn n die Anzahl der Objekte in der Datensammlung beschreibt, dann besteht die Matrix aus n Zeilen und n Spalten.

Abbildung in dieser Leseprobe nicht enthalten

Der Eintrag a i, j ist der ÄhnlichkeitswertzwischendenObjekten i und j.Wie man sieht, weist die Matrix eine quadratische Struktur auf. Es ist allerdings nicht n ötig, alle n [2] vielen Einträge der Matrix tatsächlich zu berechnen. Da die Ähnlichkeit zweier Objekte i und j symmetrisch und die Ähnlichkeit eines Objektes zu sich selbst gleich 1 ist, gen ügt es, die untere Dreieicksmatrix zu berechnen. DieÄhnlichkeitsmatrix ist bez üglich der Hauptdiagonalen symmetrisch. In der folgenden Matrix sind diejenigen Einträge, die nicht explizit berechnet werden m üssen, mit ⊗ markiert.

Abbildung in dieser Leseprobe nicht enthalten

2.6 Kategorienützlichkeit

Die Kategorienützlichkeit (category utility) CU misst die Gesamtqualität einer Aufteilung von Objekten in Cluster und ist damit ein Gütema ß f ür Clustereinteilungen. Besondere Wichtigkeit wird ihr bei inkrementellen, hierarchischen Clusteranalyseverfahren (siehe Abschnitt 2.3.7) beigemessen. Die Kategorien ützlichkeit basiert auf einer quadratischen Verlustfunktion, die auf bedingten Wahrscheinlichkeiten definiert ist:[50]

Abbildung in dieser Leseprobe nicht enthalten

C 1, . . . , C k bezeichnen die k Cluster. Der Summationsindex l läuft über die Clu- ster, die mit ihrer Wahrscheinlichkeit Pr[ C l ] gewichtet sind. Die mittlere Sum- mierung iteriert über die Merkmale der Objekte. a i ist das i -te Merkmal und nimmt die Werte [Abbildung in dieser Leseprobe nicht enthalten]an.Über diese Werte wird in der letzten Summe mit dem Summationsindex j iteriert. Zu beachten ist, dass sich die Wahrschein- lichkeiten Pr durch Summierung über alle Objekte ergeben. Damit gibt es eine weitere implizite Summationsebene, die in Formel 2.8 nicht gezeigt ist. Die Differenzen zwischen den quadrierten Wahrscheinlichkeiten werden in der inneren doppelten Summierung über alle Merkmale und alle ihre m öglichen Werte summiert.[50]

Da sich Merkmalsausprägungen in einem Cluster naturgemäß sehr ähnlich sind, ist ein wesentlicher Vorteil eines Clusters, dass die Vorhersage der Merk- malsausprägungen von Objekten in diesem Cluster erleichtert wird. Das heißt: Pr [Abbildung in dieser Leseprobe nicht enthalten] ist eine bessere Abschätzung der Wahrscheinlichkeit, dass Merk- mal a i den Wert v ij f ür ein Objekt im Cluster C l hat, als Pr [Abbildung in dieser Leseprobe nicht enthalten], weil ber ücksichtigt wird, in welchem Cluster sich das Objekt befindet.[50]

Die Kategorien ützlichkeit 2.8 gibt also an, inwieweit die Information, dass das Objekt einem bestimmten Cluster zugeordnet ist, tatsächlich n ützt. Die Division durch k wirkt einerÜberanpassung entgegen.[50]

Ein weiteres G ütemaß einer Clustereinteilung ist die squared error Methode, auf die in Abschnitt 3.2.1 näher eingegangen wird.

2.7 Darstellung von Clustern

Das Ergebnis der Clusteranalyse ist eine Partitionierung der Datensammlung, eine Einteilung von Objekten in Cluster. Die Cluster sowie deren zugeordnete Objekte sollen in einer kompakten Form beschrieben werden. Die folgenden Repräsentationsformen sind in der Literatur bekannt:[23]

1. Ein Cluster wird durch seinen Zentroid oder eine Menge distanzierter Objekte repräsentiert.

[...]

---

¹ webopedia.com gibt folgende Definition f ür data mining: ”A class of database applications that look for hidden patterns in a group of data that can be used to predict future behavior. Data Mining actually discovers previously unknown relationships among the data.“[1]

¹ zur Begrifflichkeit siehe Kapitel 5

¹ zur Begrifflichkeit siehe Kapitel 4

¹ zum Begriff der Metrik siehe auch Abschnitt 2.5.1

¹ Induktives Lernen bezeichnet die Entdeckung neuer Zusammenhänge, die vorher nicht bekannt waren

¹ Die Hauptkomponentenanalyse (HKA) ist ein Verfahren der multivariaten Statistik[1]. ”Bei der HKA geht es darum, die Information, die in einer Menge von unabhängigen Variablen enthalten ist, zu komprimieren. [. . .] “[1]

¹ zur Definition siehe Abschnitt 2.5.1

¹ zur Begrifflichkeit siehe Kapitel 4