Danksagung

An dieser Stelle m ¨ ochte ich all jenen danken, die durch ihre fachliche und pers ¨ onliche Unterst ¨ utzung zum Gelingen dieser Diplomarbeit und des gesamten Studiums beigetragen haben.

Ich bedanke mich bei Herrn Prof. Dott.-Ing. Roberto Zicari f ¨ ur 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 ¨ ur die sehr gute Betreuung meiner Diplomarbeit. Die zahlreichen wissenschaftlichen Ratschl¨ age und fachlichen Diskussionen haben stets zur Verbesserung der Arbeit beigetragen.

Ein ganz besonderer Dank geb ¨

zyk. Die fachlichen Diskussionen, die gemeinsam gel ¨ die zusammen durchgef ¨ gen auf die Pr ¨ ufungen w¨ ahrend des gesamten Studiums haben entscheidend zu unserem erfolgreichen und schnellen Informatik-Studium beigetragen. Ich danke ihm f ¨ ur seine Unterst ¨ utzung, Motivation, Kritik und Bereitschaft rund um die Uhr. W¨ ahrend der gemeinsamen Jahre hat sich auch im privaten Umfeld eine gefestigte Freundschaft entwickelt, die sich ebenfalls zu einer beruflichen Partnerschaft entwickeln soll.

Aufrichtiger Dank geb ¨ uhrt meinen Eltern, die mir dieses Studium durch ihre Unterst ¨ utzung in allen Lebensbereichen erm ¨ lagen gelegt haben. Einen großen Ansporn f ¨

meinem Vater, Dr. Winfried Brandt, zu verdanken. Er stellt mir eine erfolgversprechende berufliche Zukunft in Aussicht.

Meiner Frau Jenny m ¨ ochte ich meinen herzlichsten Dank aussprechen. Sie hat mir die Sorgen des Alltags abgenommen und mich tatkr¨ aftig unterst ¨ dass ich 100% meiner Zeit dem Studium widmen konnte. Ich danke ihr f ¨ Geduld, die sie w¨ ahrend meiner Zeit an der Universit¨ at und der Entstehung dieser Arbeit aufbrachte.

Inhaltsverzeichnis

Abbildungsverzeichnis   IV

Tabellenverzeichnis V   

1  Einleitung  1

1.1  Einf uhrung in Information Retrieval und Data Mining  1

1.2  Einf uhrung in die Clusteranalyse  2

1.3   

Uberblick  uber die Arbeit  4

2  Grundlagen der Clusteranalyse  5

2.1  Begriffe und formale Definitionen  5

2.2  Optimales Clustern ist NP-hart  7

2.2.1  Objekte in unterscheidbaren Clustern  7

2.2.2  Objekte in ununterscheidbaren Clustern  7

2.2.3  Beweis nach Garey und Johnson  8

2.3  Klassifikation der Clusterverfahren  8

2.3.1  Hierarchische Clusterverfahren  9

2.3.2  Partitionierende Clusterverfahren  10

2.3.3  Disjunkte vs. nicht-disjunkte Verfahren  10

2.3.4  Deterministische vs. probabilistische Verfahren  10

2.3.5  Monothetische vs. polythetische Verfahren  11

2.3.6  Scharfe vs. Fuzzy-Verfahren  11

2.3.7  Inkrementelle vs. nicht-inkrementelle Verfahren  11

2.3.8   

Uberwachte  vs. un uberwachte Verfahren  12

2.3.9  Unvollst andige vs. vollst andige Verfahren  13

2.4  Prinzipien zur Bildung der Cluster  13

2.5  Abstandsfunktionen  16

2.5.1  Begriffe, Definitionen  16

2.5.2  Wichtige Distanzmaße f ur metrische Variablen  17

2.5.2.1  Distanzmaße auf Basis der verallgemeinerten  

Minkowski  -Metrik  17

2.5.2.2  Ein Beispiel zur verallgemeinerten Minkowski-  

Metrik   18

2.5.2.3  Probleme der diskutierten Distanzmaße  19

2.5.2.4  Transformation auf eine einheitliche Skala  19

2.5.2.5  Gewichtung der Merkmale  20

2.5.2.6  Die Mahalanobis-Distanz  20

2.5.2.7  Das Kosinusmaß  22

I

II Inhaltsverzeichnis

2.5.3 Distanzmaße f ¨ ur Merkmale mit bin¨ arem Wertebereich . 22 2.5.4 Aufstellen der ¨ Ahnlichkeitsmatrix . . . . . . . . . . . . . 23 2.6 Kategorien ¨ utzlichkeit . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.7 Darstellung von Clustern . . . . . . . . . . . . . . . . . . . . . . 24

3 Klassische Clusteralgorithmen 27

3.1 Hierarchische Verfahren . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.1 Hierarchisch agglomerierender Algorithmus . . . . . . . 27 3.1.2 Single Pass Clustering . . . . . . . . . . . . . . . . . . . . 28 3.1.3 Ein graphentheoretischer Algorithmus . . . . . . . . . . 29 3.2 Partitionierende Verfahren . . . . . . . . . . . . . . . . . . . . . . 30 3.2.1 Squared Error Methode . . . . . . . . . . . . . . . . . . . 31 3.2.2 K-means Algorithmus . . . . . . . . . . . . . . . . . . . . 31 3.3 Fuzzy-Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3.1 Unscharfe Mengen, Zugeh ¨ origkeitsfunktion . . . . . . . 34

3.3.2 Fuzzy-c-means Algorithmus . . . . . . . . . . . . . . . . 34 3.4 Wahrscheinlichkeitsbasiertes Clustering . . . . . . . . . . . . . . 36 3.4.1 EM-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . 37

4 Non-obvious user profiles (NOPs) 41

4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2 Algorithmus zur Erstellung von NOPs . . . . . . . . . . . . . . . 41 4.3 Messen der Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3.1 Einbinden eines Feedback-Mechanismus . . . . . . . . . 43 4.3.2 Nutzen der Feedback-Informationen . . . . . . . . . . . . 44

5 Clusterbildung als Disziplin des Web Usage Mining 45

5.1 Motivation, Grundlagen . . . . . . . . . . . . . . . . . . . . . . . 45 5.2 Parameter zum Clustern von Benutzern auf Basis von NOPs . . 46 5.2.1 Auf der Website angebotene Themen . . . . . . . . . . . 46 5.2.2 Zeitliche Interessens¨ anderungen der Benutzer . . . . . . 47 5.2.3 Vertrauensw ¨ urdigkeit der Benutzer . . . . . . . . . . . . 47 5.2.4 Navigationspfade der Benutzer . . . . . . . . . . . . . . . 48 5.2.5 Durchschnittliche Sessiondauer . . . . . . . . . . . . . . . 48 5.2.6 Anzahl Sessions . . . . . . . . . . . . . . . . . . . . . . . . 49 5.2.7 Pers ¨ onliche Daten der Benutzer . . . . . . . . . . . . . . . 49 5.3 Anwendung klassischer Clusteralgorithmen auf Benutzerprofile 50 5.3.1 Anwendung des K-means-Algorithmus auf die Clusterbildung von NOPs in Bezug auf Themen . . . . . . . . . 50 5.3.2 Beispiel zur Anwendung des K-means-Algorithmus . . 51

6 Verwandte Arbeiten im Web Mining Umfeld 55

6.1 Zugriffsmuster, generalisierte Sessions und Attribute-oriented induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.1.1 Clusterverfahren BIRCH . . . . . . . . . . . . . . . . . . . 56 6.2 Clusteranalyse von Sessions mittels Sequence Alignment . . . . 57 6.3 ¨ Ahnlichkeitsbasiertes Clustern von Web Transaktionen . . . . . 61

Inhaltsverzeichnis III

6.4  Entdeckung von Wissen durch Navigationspfade von Benutzern  65

6.4.1  Path Feature Space  66

6.5  Sequence Alignment Methode  69

6.6  Charakterisieren von Benutzergruppen einer E-Commerce Web-  

site   71

6.6.1  Hybrider Clusteralgorithmus  72

6.7   

Ahnlichkeitsbestimmung  zwischen Interessen zur Clusteranalyse  74

6.7.1   

Ahnlichkeitsma  ße  75

6.7.2  Matrixbasierter Clusteralgorithmus  76

6.8  Clusteranalyse anhand von l angsten, gemeinsamen Teilpfaden  80

6.8.1   

Ahnlichkeit  zwischen Pfaden  81

6.8.2  Graphbasierter Clusteralgorithmus  82

6.8.3  Beispiel zur  

Ahnlichkeit  zweier Pfade  85

6.9  Erstellung von aggregierten Benutzungsprofilen  85

6.9.1  Profile Aggregations based on Clustering Transactions  

  (PACT)  87

6.9.2  Association Rule Hypergraph Partitioning (ARHP)  88

7  Anwendungsgebiete der Clusteranalyse  91

7.1  Recommender Systeme  91

7.2  Adaptive Websites  92

7.3  Prefetching Systeme  93

7.4  Kontaktierung von Kundengruppen  96

8  Zusammenfassung  97

Literaturverzeichnis   101

Abbildungsverzeichnis

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

1.2 Visualisierung von Clustern f ¨ ur zwei Merkmale F und G . . . . 3

2.1 Visualisierung von drei sich ¨ uberlappenden Clustern f ¨

Merkmale S und T bei einer vollst¨ andigen Clustereinteilung . . 2.2 Dendrogramm eines hierarchischen Clusterings . . . . . . . . . 2.3 Unterschied zwischen ¨ uberwachten und un ¨ uberwachten Clusterverfahren. Quelle: [8] . . . . . . . . . . . . . . . . . . . . . . . 13 2.4 Prinzip der N¨ achste-Nachbarn-Verfahren. Quelle: [2] . . . . . . 14 2.5 Problematik der Skalierung. Quelle: [22] . . . . . . . . . . . . . . 19 2.6 Cluster-Repr¨ asentation durch einen Klassifikationsbaum oder konjunktivische logische Ausdr ¨ ucke. Quelle: [23] . . . . . . . . . 25

3.1 Ein minimaler Spannbaum. Quelle: [23] . . . . . . . . . . . . . . 30 3.2 3-means Clustering (k = 3). Quelle: [26] . . . . . . . . . . . . . . 33 3.3 Wahrscheinlichkeitsdichtefunktion f ¨ ur zwei Cluster A und B.

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

5.1 Visualisierung der NOPs im Koordinatensystem . . . . . . . . . 52

6.1 Beispiel eines CF-Baumes. Quelle: [53] . . . . . . . . . . . . . . . 56 6.2 Baumstruktur einer Website. Quelle: [43] . . . . . . . . . . . . . 59 6.3 Evaluierung der erstellten Clustereinteilung. Quelle: [43] . . . . 60 6.4 Wahl des Schwellwertes ϑ. Quelle: [51] . . . . . . . . . . . . . . . 80 6.5 Systemarchitektur. Quelle: [29] . . . . . . . . . . . . . . . . . . . 86

7.1 Systemarchitektur inkl. Proxy-Server . . . . . . . . . . . . . . . . 94 7.2 Vergleich der Pr¨ azision zwischen PPM und vob-PPM. Quelle: [51] 96

IV

Tabellenverzeichnis

2.1 Bedeutung der Parameter der verallgemeinerten Minkowski-Metrik. Quelle: [2] . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Merkmale mit bin¨ arem Wertebereich. Quelle: [20] . . . . . . . . 22

3.1 Beispiel der Zugeh ¨ origkeitsgrade von 4 Objekten zu 3 Clustern 34

4.1 NOPs von f ¨ unf Benutzern der Website bei vier vorgegebenen

Themen. Quelle: [32] . . . . . . . . . . . . . . . . . . . . . . . . . 42

V

Kapitel 1

Einleitung

1.1 Einf¨ uhrung in Information Retrieval und Data Mining

Zum einen l¨ asst in den letzten Jahren die zunehmende Verbreitung von elektronischen Medien die Menge der Daten, die digital zur Verf ¨ ugung stehen, immer weiter anwachsen. Umfassende digitalisierte Datensammlungen werden von Wirtschaftsunternehmen, aber auch wissenschaftlichen und staatlichen Einrichtungen aufgebaut. Durch die ebenfalls ansteigende weltweite Vernetzung von Rechnern werden diese Informationen f ¨ ur immer mehr Menschen zug¨ anglich. [11]

Zum anderen hat die Konvergenz von Informatik und Telekommunikation eine 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 ¨ utzlicher Informa-

tionen aus Daten wird nach [50] als Data Mining ¹ bezeichnet. Zu diesem Zweck werden Algorithmen entwickelt, die Datenbanken automatisch durchforsten und dabei nach Regelm¨ aßigkeiten oder Mustern suchen.

F ¨ ur die Wissensgewinnung aus Datensammlungen (Knowledge Discovery in Databases (KDD)) gibt Reginald Ferber in seinem Buch folgende Definition: ” Knowledge Discovery in Databases (KDD) beschreibt automatisierte Verfahren, mit denen Regelm¨ aßigkeiten in Mengen von Datens¨ atzen gefunden und in eine f ¨ ur Nutzende verst¨ andliche Form gebracht werden.“ [11]

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

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

¹ webopedia.com gibt folgende Definition f ¨ ur 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.“[46]

1

2 Kapitel 1 Einleitung

2. Data Mining wird angesehen als ein notwendiger Schritt im mehrstufigen 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 specific algorithms for extracting patterns from data.“

Der KDD-Prozess besteht nach [19] aus der Datens¨ auberung (data cleaning), der Datenintegration (data integration), der Datenselektion (data selection), der Datentransformation (data transformation), dem Data Mining, der Musterauswertung (pattern evaluation) und der Wissensrepr¨ asentation (knowledge presentation). In [19] wird detailliert auf den KDD-Prozess eingegangen.

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

1.2 Einf¨ uhrung 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 Datenanalyse. Sie ist besonders in den betriebswirtschaftlichen Bereichen Marketing und Vertrieb von Bedeutung, um die Identifikation und Analyse homogener Kundengruppen zu unterst ¨ utzen. Diese Gruppen k ¨ onnen dann gezielt durch das Unternehmen kontaktiert werden. Gerade bei großen Einzel-handelsunternehmen ist nicht mehr jeder einzelne Kunde pers ¨ onlich, sondern

dem Unternehmen nur durch die Aufzeichnung der Gesch¨ aftsprozesse bekannt, die durch die Kunden generiert wurden. Basierend auf diesen Gesch¨ afts-prozessinformationen, die in unserem Sinne eine Datensammlung repr¨ asentieren, werden die Kundendaten durch Clusteringverfahren segmentiert. Die Kunden innerhalb einer Gruppe sind hinsichtlich der betrachteten Informationen 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 ¨ oglichst ¨ ahnlich sind

(Homogenit¨ at innerhalb eines Clusters);

• die Objekte je zwei verschiedener Cluster m ¨ oglichst unterschiedlich sind (Heterogenit¨ at 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 ¨ oherdimensional wird die Betrachtung. Eine Visualisierung f ¨ ur mehr als drei Merkmale ist nicht m ¨ oglich. Die in Abbildung 1.2 untersuchten Objekte bilden in den beiden Merkmale F und G vier Cluster.

Abbildung 1.2: Visualisierung von Clustern f ¨ ur zwei Merkmale F und G

Es gibt eine große Anzahl an Clusteranalyseverfahren. Es w ¨ urde 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 Benutzerprofilen, die u.a. an der Professur f ¨ ur Datenbanken und Informationssysteme

der Johann Wolfgang Goethe-Universit¨ at Frankfurt entwickelt wurden, eingegangen [32]. Benutzerprofile k ¨ onnen in vielerlei Hinsicht geclustered werden. Man denke beispielsweise an eine Gruppierung von Web-Usern anhand von Themen. Interessante Fragestellungen in diesem Zusammenhang sind sicherlich, welche und wie viele Web-User sich f ¨ ur die gleichen Themen einer

Website interessieren oder welche Interessens¨ anderungen im Laufe der Zeit auftreten. Diese und andere Fragen lassen sich mit Unterst ¨ utzung der Cluster- analyse beantworten.

4 Kapitel 1 Einleitung

1.3 ¨ Uberblick ¨ uber 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¨ 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. ¨ Ahnlichkeitsfunktionen, die einen wesentlichen Bestandteil von Clusterverfahren bilden.

Existierende, klassische Algorithmen zur Clusterbildung aus dem Bereich des Data Mining werden in Kapitel 3 erl¨ autert. Nachdem die Clusterverfahren in Kapitel 2 klassifiziert wurden, werden in Kapitel 3 vier Klassen von Clusterverfahren n¨ aher 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 ¨ uhrt 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¨ aufig eingesetzten, klassischen Clusterverfahrens auf non-obvious-userprofiles erl¨ autert.

Das Kapitel 6 ist der Vorstellung verwandter Arbeiten im Web Mining Umfeld gewidmet. Es werden sowohl zahlreiche, in der Literatur diskutierte Clusterverfahren als auch ¨ Ahnlichkeitsmaße pr¨ asentiert, erl¨ autert, miteinander verglichen und kritisiert.

In Kapitel 7 werden einige m ¨ ogliche 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.

² zur Begrifflichkeit siehe Kapitel 5

³ zur Begrifflichkeit siehe Kapitel 4

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 ¨ orig sind, wohingegen die Objekte verschiedener Cluster eine geringere Zusammengeh ¨ origkeit aufweisen. Formal k ¨ onnen wir die Clustereinteilung C folgendermaßen beschreiben:

C = {c j ⊆ E | j = 1, . . . , k},

wobei c j ein einzelnes Cluster, E die Menge der Objekte und k die Anzahl der Cluster ist.

Die Zusammengeh¨ origkeit von Objekten wird gem¨ aß [35] durch ein Maß f ¨ ur

Ahnlichkeit s E (., .) bzw. den Abstand d E (., .) zwischen Objekten im Objekdie ¨ traum E definiert. Maximale ¨ Ahnlichkeit bzw. minimaler Abstand zwischen je zwei Objekten determinieren eine maximale Zusammengeh ¨ origkeit 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¨ andig, wenn jedes Objekt e ∈ E einem Cluster zugeordnet ist. Andernfalls heißt die Einteilung partiell. F ¨ ur eine vollst¨ andige Clustereinteilung kann man infolgedessen schreiben:

In Abbildung 1.2 ist eine vollst¨ andige Clustereinteilung gezeigt, da es kein Objekt gibt, das keinem der vier Cluster zugeordnet ist. Eine Clustereinteilung C = {c 1 , . . . , c k } heißt gem¨ aß [35] nicht ¨ uberlappend,

wenn kein Objekt mehr als einem Cluster zugeordnet ist. Andernfalls heißt die Einteilung ¨ uberlappend. Man spricht also von einer nicht ¨ uberlappenden Clustereinteilung, falls

∀c u , c v ∈ C : c u ∩ c v = ∅

gilt. In Abbildung 1.2 ist eine nicht ¨ uberlappende Clustereinteilung gezeigt,

5

6 Kapitel 2 Grundlagen der Clusteranalyse

da jedes Objekt zu genau einem Cluster zugeordnet ist. In Abbildung 2.1 wird eine ¨ uberlappende Clustereinteilung visualisiert.

Abbildung 2.1: Visualisierung von drei sich ¨

Ein Clusterverfahren ist nach [35] eine Methode, die eine Clustereinteilung bestimmt. Man geht von der Objektmenge aus und verwendet ein geeignetes Ahnlichkeit s E (., .) bzw. den Abstand d E (., .) zweier Objekte. ur die ¨ Maß f ¨

Cluster c k¨ onnen durch Repr¨ asentanten c identifiziert werden, wenn ein metrischer Raum E mit der Metrik ¹ d E (., .) verwendet wird. Der Repr¨ asentant des Clusters c ist der Schwerpunkt bzw. Zentroid von c, der sich nach [35] durch Mittelwertbildung ¨ uber alle Objekte des Clusters ergibt:

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

p u ∩ p v = ∅ ⇔ u = v

und

Die Partitionierung ist damit eine vollst¨ andige Clustereinteilung mit nicht ¨ uberlappenden Clustern. Man spricht in diesem Zusammenhang auch von Segmentierung.

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¨ aheres zu d C (c i , c j ) und dessen Bestimmung siehe Abschnitt 2.4.

¹ zum Begriff der Metrik siehe auch Abschnitt 2.5.1

2.2 Optimales Clustern ist NP-hart

Grunds¨ atzlich 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 ¨ oglicher Cluster endlich ist,

k¨ onnte man versucht sein, das Problem der Clustereinteilung von n Objekten in k Cluster mit naiver Herangehensweise dadurch zu l ¨ osen, alle m ¨ oglichen

Clustereinteilungen zu untersuchen.

2.2.1 Objekte in unterscheidbaren Clustern

Wenn erlaubt wird, dass Cluster leer sein d ¨

sage dar ¨ uber zu treffen, wie viele Kombinationsm ¨ jekte in k Cluster einzuteilen. Es gibt f ¨ ur jedes der n Objekte k M¨ oglichkeiten, es einem Cluster zuzuordnen. Damit ergeben sich

verschiedene Clustereinteilungsm ¨ oglichkeiten. Die Anzahl der verschiedenen Clustereinteilungen w¨ achst exponenziell in n.

Wenn kein Cluster leer bleiben darf, wird es komplizierter, die Anzahl der m¨ oglichen Clustereinteilungen zu bestimmen. Es wird angenommen, dass die Reihenfolge innerhalb der Cluster nicht relevant ist. Die Anzahl m ¨ oglicher

Clustereinteilungen von n Objekten in k Cluster wird nach [27] bestimmt durch

i=0 (−1) i ( k i )(k − i) n und ist in der Literatur als k! ∑ k Dabei ist S(n, k) definiert als 1

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 ¨ oglichkeiten, 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

8 Kapitel 2 Grundlagen der Clusteranalyse

S(n, 2) =

M¨ oglichkeiten. Man sieht, dass es schon f ¨ ur den ”

vorgegebenen Clustern exponenziell in n viele m ¨ 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¨ arte 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 ¨ ur alle Paare

x, y ∈ X i und 1 ≤ i ≤ k gilt: d(x, y) ≤ B?

Brucker [6] f ¨ uhrt eine Reduktion dieses Clusteringproblems auf das NP-voll- st¨andige Problem der Dreif¨ arbbarkeit von Graphen (3-COLORING) zur ¨ Er hat damit die NP-H¨ arte des Clusterings bewiesen. Garey und Johnson sind

der Meinung, dass das Problem sogar f ¨ [0, 1] NP-vollst¨ andig bleibt. F ¨ ur K = 2 wird das Clustereinteilungsproblem allerdings in polynomieller Zeit l ¨

Cluster-Algorithmen k ¨ onnen eine gute, suboptimale L ¨ osung in polynomieller Zeit f ¨ ur ein fest vorgegebenes k bestimmen. Ist k variabel, d.h. nicht mehr fix, gibt es, falls P = NP angenommen wird, keine Algorithmen, die in polynomieller Zeit eine optimale Clustereinteilung der vorgegebenen Objekte berechnen. Alle diese Cluster-Algorithmen liegen in der Komplexit¨ atsklasse 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 ¨ oglicher

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“ Partition der Datensammlung in k disjunkte Partitionen, ohne eine mehrstufige Clusterstruktur zu ermitteln, nachdem die Anzahl k der gew ¨ unschten Cluster vorgegeben wurde. [50] [23]

2.3.1 Hierarchische Clusterverfahren

Grunds¨ atzlich werden agglomerierende (bottom-up Vorgehensweise) von divisiven (top-down Vorgehensweise) Clusteringverfahren unterschieden [20].

Bei den agglomerierenden (anh¨ aufenden) Verfahren wird initial jedes Objekt der Datensammlung als eigenes Cluster interpretiert. Es werden sukzessive einzelne, zueinander ¨ ahnliche Objekte zu Clustern und bereits erkannte Cluster zu gr ¨ oßeren Clustern verschmolzen bis der Abstand zwischen je zwei Clustern einen bestimmten Schwellwert ¨ ubersteigt oder wenn nur noch ein großes Cluster ¨ ubrig ist. [20]

Divisive (unterteilende) Verfahren beginnen anf¨ anglich mit einem einzigen Cluster. Jedes Objekt der Datensammlung ist diesem Cluster zugeordnet. Anschließend werden immer neue (Teil-)Cluster erstellt, d.h. das urspr ¨ ungliche

Cluster immer feiner unterteilt. Dieser Prozess dauert so lange an, bis nur noch Cluster bestehend aus Einzelobjekten ¨ ubrig 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.

agglomerierend

Abbildung 2.2: Dendrogramm eines hierarchischen Clusterings

Es ist sowohl bei agglomerierenden als auch bei divisiven Clusterverfahren m¨ oglich, den Algorithmus vorzeitig abzubrechen, wenn man eine bestimmte Hierarchieebene des Dendrogramms clustern m ¨ ochte. Im Falle eines agglomerierenden Verfahrens terminiert der Algorithmus also bevor nur noch ein Cluster ¨ ubrig ist. Handelt es sich um ein divisives Verfahren so endet der Al-gorithmus bevor nur noch Cluster bestehend aus Einzelobjekten ¨ ubrig bleiben.

Dadurch wird meist eine Laufzeitverbesserung erreicht.

10 Kapitel 2 Grundlagen der Clusteranalyse

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 ¨ ahnlich wie m ¨ oglich 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 ¨ uhren 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¨ asst sich der Algorithmus mehrere Male mit verschiedenen Werten f ¨ ur k starten, jedoch muss man in der

Lage sein, sich zwischen verschiedenen k-Werten zu entscheiden [20]. Welches uhrt, kann nur anhand einer ¨ k zur optimalen Clustereinteilung f ¨ Ahnlichkeitsfunktion (score function) bestimmt werden. Insbesondere kann durch die Berechnung der Kategorien ¨ utzlichkeit (siehe Abschnitt 2.6) die Gesamtqualit¨ at einer Aufteilung von Objekten in Cluster gemessen werden. [50]

Weiterhin werden die Clusterverfahren anhand folgender Kriterien differenziert. [23]

2.3.3 Disjunkte vs. nicht-disjunkte Verfahren

Die Clusteranalyseverfahren k ¨ onnen unterschieden werden in disjunkte (nicht¨ uberlappende) und nicht-disjunkte ( ¨

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 ¨ Uberlappungen die Heterogenit¨ at zwischen den Clustern ab. Wenn es zwischen zwei Clustern viele Objekte gibt, die zu beiden Clustern zu-

geordnet werden k ¨ onnen, sind die Cluster nicht deutlich voneinander trennbar. Andererseits kann ein ¨ zahl von Clustern f ¨ uhren. [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 Verfahren ist die Anzahl der Merkmale, die parallel in die Berechnung der Clustereinteilung eingehen. Polythetische Algorithmen beziehen alle Merkmale simultan in die Berechnung der Abst¨ ande zwischen Clustern ein. Ein monothetischer 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 ¨ sen. m X (d) ist jedoch nicht als eine Wahrscheinlichkeitsgr ¨ halb sich die Zugeh ¨ origkeitsgrade auch nicht zu 1 aufsummieren brauchen. Ein Zugeh ¨ origkeitsgrad von 0,95 bedeutet nicht, dass das Objekt dem betreffenden Cluster mit einer Wahrscheinlichkeit von 95% zugeordnet wird. Stattdessen sind die Zugeh ¨ origkeitsgrade im Sinne der unscharfen Mengen (Fuzzy

Sets) zu interpretieren, auf die in Abschnitt 3.3.1 noch n¨ aher eingegangen wird. [41]

Bei scharfen Verfahren kann der Zugeh ¨ origkeitsgrad eines Objektes zu einem

Cluster entweder 0 oder 1 sein. Es wird kein Wert zwischen 0 und 1 angenommen.

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

2.3.7 Inkrementelle vs. nicht-inkrementelle Verfahren

Es muss der Einsatz eines inkrementellen gegen ¨ uber eines nicht-inkrementellen

Clusteranalyseverfahrens abgewogen werden, wenn die zu clusternde Datensammlung sehr groß ist und es Zeit- und/oder Speicherplatzbeschr¨ ankungen gibt, die gef¨ ahrden, dass der Algorithmus eingesetzt werden kann. Ein guter Algorithmus sollte sowohl die Anzahl der Durchl¨ aufe, die zum Clustern der

Datensammlung n ¨ otig ist, als auch die Anzahl der in einem Durchlauf untersuchten Objekte und weiterhin die Gr ¨ minimieren. [23]

Beim inkrementellen Clustering werden die Objekte der Datensammlung einzeln und nacheinander betrachtet, wohingegen beim nicht-inkrementellen Clustering parallel alle Objekte in die Berechnung der Clustereinteilung einfließen. Beim inkrementellen Clustern entsteht ein Baum, dessen Bl¨ atter die Objekte sind. Die Wurzel repr¨ asentiert die gesamte Datensammlung. Gestartet wird

12 Kapitel 2 Grundlagen der Clusteranalyse

mit dem Baum, der nur aus der Wurzel besteht. Sukzessive werden die Objek-

te der Baumstruktur hinzugef ¨ ugt. An welcher Stelle ein Objekt im Baum eingef ¨ ugt wird, entscheidet das Maß der Kategorien ¨ 2.6). Der Nachteil von inkrementellen Verfahren ist, dass das entstehende Clustering von der Reihenfolge abh¨ angt, in der die Objekte herangezogen werden.

2.3.8 ¨ Uberwachte vs. un¨ uberwachte Verfahren

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

Die Trainingsmenge ist eine endliche Menge von Objekten, auf der der Algo-

rithmus die Erkennung von Clustern durchf ¨ ermittelten Ergebnisse verifizieren zu k ¨ onnen, verwendet man eine weitere Menge endlich vieler Objekte, die so genannte Testmenge. Die Trainings- und Testmenge sind disjunkt. [11]

Man spricht vom ¨ uberwachten Lernen (supervised learning), wenn eine Trainingsmenge gegeben ist, die den Algorithmus bei der Berechnung von Clustern unterst ¨ utzt. Der Algorithmus nutzt aus, dass es bereits eine Menge von Objekten gibt, die als Repr¨ asentanten f ¨ ur ein Cluster angesehen werden k ¨ onnen. Das

sind die Objekte der Trainingsmenge. Der Algorithmus bestimmt Cluster, indem er die Objekte der Testmenge demjenigen Repr¨ asentanten der Trainingsmenge zuordnet, dem das Objekt am ¨ ahnlichsten ist. Die Trainingsmenge gibt eine grobe Strukturierung der Objekte vor.

Beim un ¨ uberwachten 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 ¨ uberwachtem und un ¨ uberwachtem Clustering visualisiert. Die weißen und schwarzen Kreise repr¨ asen-

tieren zwei verschiedene Objekttypen einer Datensammlung. Ein un ¨ tes Clusterverfahren w ¨ urde (sehr wahrscheinlich) die Cluster in Abbildung 2.3 (a) identifizieren, wohingegen ein ¨

dung 2.3 (b) eingezeichneten Cluster berechnet. Das liegt offensichtlich daran, dass das ¨ uberwachte Clusterverfahren anhand der Trainingsmenge gelernt hat, dass es zwei verschiedene Objekttypen gibt und diese separat gruppiert. Das un ¨ uberwachte Clusterverfahren kennt keine Trainingsmenge und gruppiert lediglich Objekte, die r¨ aumlich sehr nahe beieinander liegen.

² Induktives Lernen bezeichnet die Entdeckung neuer Zusammenh¨ ange, die vorher nicht be- kannt waren

Merkmal 1

Abbildung 2.3: Unterschied zwischen ¨ uberwachten und un ¨ uberwachten Clusterverfahren. Quelle: [8]

2.3.9 Unvollst¨ andige vs. vollst¨ andige Verfahren

Bei unvollst¨ andigen Clusterverfahren handelt es sich um geometrische Methoden, die zu einer niedrigdimensionalen, r¨ aumlichen Darstellung der Objekte f ¨ uhren. F ¨ ur mehrdimensionale Daten wird eine Reduktion der Dimensiouhrt, beispielsweise durch eine Hauptkomponentenanalyse ³ , um sie nen durchgef ¨

zwei- oder dreidimensional graphisch darstellen zu k ¨ onnen. Die Clusterbildung erfolgt dann manuell durch augenscheinliche Betrachtung der Daten, d.h. der Anwender selbst, nicht das Clusterverfahren, f ¨ uhrt die Zuordnung

der Objekte zu Clustern durch eine Interpretation der r¨ aumlichen Darstellung durch. Der Vorteil unvollst¨ andiger Verfahren liegt in der Anschaulichkeit der Daten. [2], [22]

Vollst¨ andige Clusterverfahren f ¨ uhren die Zuordnung von Objekten zu Clustern

ohne zus¨ atzlichen 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¨ achste-Nachbarn-Verfahren: Die Cluster werden derart gebildet, dass

a) jedes Objekt der Datensammlung eine bestimmte Anzahl n¨ achster Nachbarn in demjenigen Cluster hat, dem es zugeordnet ist oder

b) jedes Objekt der Datensammlung in dem Cluster zumindest einen B-ten n¨ achsten (z.B. einen drittn¨ achsten) Nachbarn hat.

³ Die Hauptkomponentenanalyse (HKA) ist ein Verfahren der multivariaten Statistik [48]. ” Bei

der HKA geht es darum, die Information, die in einer Menge von unabh¨ angigen Variablen enthalten ist, zu komprimieren. [. . .] “ [49]

14 Kapitel 2 Grundlagen der Clusteranalyse

Im Fall a) gilt ein Objekt x als ein n¨ achster Nachbar zu einem Objekt y, falls x eine ¨ Ahnlichkeit zu y hat, die betragsm¨ aßig gr ¨ oßer oder gleich ei-

nem bestimmten, vorher festgelegten Schwellwert (threshold) ist. Diese Vorstellung ist in Abbildung 2.4 graphisch dargestellt.

Abbildung 2.4: Prinzip der N¨ achste-Nachbarn-Verfahren. Quelle: [2]

In Abbildung 2.4 a-1) ist dargestellt, dass alle Objekte, die ein- und demselben Cluster angeh ¨ oren, n¨ achste Nachbarn zueinander sein m ¨ ussen.

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 ¨ uber

allen Objektpaaren aus den Clustern:

Dadurch, dass das Maximum ¨ uber die Abst¨ ande der Objekte gebildet

wird, ergeben sich kleine, stark abgegrenzte Cluster, d.h. alle Objekte desselben Clusters weisen einen geringen paarweisen Abstand zueinander auf, weswegen eine sehr starke Homogenit¨ at innerhalb des Clusters die Folge ist [35]. Graphentheoretisch bezeichnet man ein solches Cluster, das einen vollst¨ andigen Graphen beschreibt, als Clique [2].

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

Inhomogene Cluster sind die Folge. So kann ¨ uber 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 Clusters mindestens zwei n¨ achste Nachbarn besitzen soll. Allgemein spricht man hier nicht von zwei sondern von B n¨ achsten Nachbarn. Bekanntlich kann ein Objekt einer Datensammlung mit n Objekten maximal n − 1 Nachbarn besitzen, so dass f ¨ ur B angefangen beim erstn¨ achsten Nachbarn bis zum (n − 1)-n¨ achsten Nachbarn alle Werte zul¨ assig 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 ¨ uber 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) ¨ uber allen Objektpaaren der Cluster:

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¨ asentanten der Cluster (Repr¨ asentanten-Verfahren): Jedes Cluster wird durch ein f ¨ ur dieses Cluster typisches Objekt beschrieben. Dieses Objekt nennt man Repr¨ asentant. Die Aufgabe des Clusterverfahrens besteht in diesem Fall also darin, Repr¨ asentanten in der Datensammlung zu finden. Sind die Repr¨ asentanten gefunden, bleibt es, die verbleibenden, nicht typischen Objekte demjenigen Cluster zuzuordnen, dessen

Repr¨ asentanten sie am ¨ ahnlichsten sind. Alternativ werden diese Objekte keinem Cluster zugewiesen, wenn die ¨ Repr¨ asentanten zu klein, d.h. der Abstand zu groß ist.

Anwendung finden die Repr¨ asentanten-Verfahren vor allem in Bereichen, in denen kein metrischer Raum ⁴ vorliegt, d.h. eine Distanzberechnung zwischen je zwei Objekten nicht m ¨ oglich ist. Ein Beispiel hierf ¨ ur ist

die Clusteranalyse von DNA-Strukturen.

4. Clusterzentren als Repr¨ asentanten (Verfahren zur Konstruktion von Clusterzentren): Im Unterschied zum Repr¨ asentanten-Verfahren, wo ein einzelnes Objekt Repr¨ asentant eines Clusters ist, wird hier angenommen, dass ein Cluster durch seinen Zentroid (siehe Definition auf S. 6) charakterisiert werden kann. In diesem Fall dr ¨ uckt man den Abstand der Cluster

16 Kapitel 2 Grundlagen der Clusteranalyse

c i und c j ¨ uber den Abstand ihrer Zentroide c i und c j aus:

d C (c i , c j ) = d E (c i , c j ).

Wie man sieht, f¨ allt die Distanzberechnung bei diesen Clusterverfahren weniger komplex aus, als bei den anderen, zuvor aufgef ¨ uhrten Verfahren. Vielmehr kann die Distanz d C (c i , c j ) in konstanter Zeit O(1) berechnet werden. Bei den Mittelwertmodellen ist im Gegensatz dazu eine Zeit O(#c i · #c j ) n¨ otig. Auch der Speicherplatzbedarf ist bei diesen Verfahren geringer, da ein Cluster durch seinen Zentroid repr¨ asentiert 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, agglomerierende und deterministische Clusterverfahren. Konkrete Clusteralgorithmen, wie beispielsweise das k-means-Verfahren, die diesen Prinzipien zugeordnet werden k ¨ onnen, werden in Kapitel 3 diskutiert. Zun¨ achst f ¨ uhren wir die wichtigen Konzepte der Abstandsfunktion und des Distanzmaßes ein, die f ¨ ur das

Verst¨ andnis der anschließend erl¨ auterten Clusteralgorithmen essenziell sind.

2.5 Abstandsfunktionen

2.5.1 Begriffe, Definitionen

Fast alle Clusterverfahren basieren auf Abstands- oder ¨ Ahnlichkeitsmaßen zwischen Objekten der Datensammlung und fordern, dass der Abstand zwischen je zwei verschiedenen Objekten berechnet werden kann, um zu entscheiden, ob zwei Objekte zueinander ¨ ahnlich sind. Damit sowohl Distanzen als auch ¨ Ahnlichkeiten formal berechnet werden k ¨ onnen, wird im Folgenden der Begriff der Abstandsfunktion definiert und anschließend die am h¨ aufigsten verwendeten Abstandsmaße aufgef ¨ uhrt. [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 ur beliebige x, y ∈ M gilt: Abstandsfunktion, wenn f ¨