Lade Inhalt...

Clustering. Die Clusteranalysen K-means und DBSCAN im Vergleich

Studienarbeit 2018 27 Seiten

Informatik - Wirtschaftsinformatik

Leseprobe

Inhalt

1 Einleitung
1.1 Was ist eine Clusteranalyse
1.2 Proximitätsmaße

2 Partitionierendes Clustering
2.1 K-Means Algorithmus
2.2 Initialisierung des K-Means
2.3 K-Means Umsetzung in R

3 Der Iris Datensatz

4 Dichtebasiertes Clustering DBSCAN
4.1 Dichteerreichbarkeit
4.2 DBSCAN Umsetzung in R

5 Fazit

Abbildungsverzeichnis

Quellenverzeichnis

1 Einleitung

Die Clusteranalyse wird als Segmentierungsverfahren definiert. In diesem Verfahren werden die zu untersuchenden Daten in verschiedene Gruppen aufgeteilt. Die Gruppeneinteilung wird von Backhaus et al (2003) so definiert:

Die Mitglieder einer Gruppe sollen dabei eine weitgehend verwandte Eigenschaftsstruktur aufweisen; d.h. sich möglichst ähnlich sein. Zwischen den Gruppen sollen demgegenüber (so gut wie) keine Ähnlichkeiten bestehen. Ein wesentliches Charakteristikum der Clusteranalyse ist die gleichzeitige Heranziehung aller vorliegenden Eigenschaften zur Gruppenbildung. […] Bei allen Problemstellungen, die mit Hilfe der Clusteranalyse gelöst werden können, geht es immer um die Analyse einer heterogenen Gesamtheit von Objekten (z.B. Personen, Unternehmen), mit dem Ziel, homogene Teilmengen von Objekten aus der Objektgesamtheit zu identifizieren.“[1]

1.1 Was ist eine Clusteranalyse

Um Clusteranalyse zu verstehen, sollte vorerst definiert werden, was unter einem „Cluster“ verstanden wird. Ein Cluster ist eine Sammlung von Datenobjekten, die ähnliche Eigenschaften besitzen. Das bedeutet, dass sich die Objekte innerhalb derselben Gruppe ähneln. Sie unterscheiden sich jedoch sehr mit den Objekten in anderen Clustern.

Ziel der Clusteranalyse, die auch Clustering oder Datensegmentierung genannt wird, die Objekte in eine homogene Gruppe zu teilen. Die Clusteranalyse besteht darin, Datenpunkte in eine Gruppe von Clustern oder Gruppen zu partitionieren. Um Objekte Clustern zu können, müssen diese über Proximitätsmaße (Euklidischer Abstand, Manhattan-Abstand) miteinander verglichen werden. Objekte mit geringer Distanz zueinander werden dabei in ein Cluster eingeteilt.

Mittels Clusteranalyse kann man klassifizieren ohne die Klassen vorher zu kennen, dies wird auch nichtüberwachtes Lernen (Unsupervised Learning) genannt. In dem Sinne gibt es beim Clustering auch keine Trainingsdaten. Dies ist sehr verschieden von der Klassifizierung, die überwachtes Lernen erfordert. Es ist nicht sinnvoll das Clusterverfahren bei allen Datensätzen anzuwenden, denn manche Datensätze weisen keine Struktur auf und sind nur zufällig angeordnete Punkte, wo kein Cluster erkennbar ist. Die Folge wäre, dass der Datensatz falsch geclustert wird und die natürliche Datenstruktur nicht wiedergegeben werden kann. Auf der linken Seite der Abbildung 1 sieht man Datenpunkte, die mittels Clusteranalyse in vier Clustern eingeteilt wurden. Diese vier Cluster ähneln sich in ihren Eigenschaften. Je nach Methode können diese Objekte zu einem oder mehreren Clustern gehören. In dieser Arbeit werden beide Methoden wie K-Means und DBSCAN untersucht, angewendet und anschließend verglichen.[2]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Clusteranalyse[3]

1.2 Proximitätsmaße

Bevor man Clustering durchführt, muss man im Voraus definieren, wie nah zwei Objekte zueinander sind. Ein Beispiel ist die Entfernung zwischen Baltimore und Washington DC zu ermitteln. Die Längenmaße für Washington DC und Baltimore wird in dem folgenden Beispiel als Y bezeichnet, die Breitenmaße werden mit X bezeichnet, siehe Abbildung 3. Wenn man die Differenz der Entfernung in Längenrichtung und den Abstand in der Breite nimmt, hat man zwei Messungen der Entfernung zwischen Baltimore und Washington DC. Um diese zu kombinieren, müsste man beide Messungen zusammenfassen. Doch dann kann es der Fall sein, dass diese Entfernung negativ ausfällt und dass sie sich gegenseitig auslöschen.

Die Lösung ist, diese zu quadrieren. Somit hat man immer positive Entfernungen, die jedoch nicht unbedingt im selben Maßstab sind. Daher nimmt man daraus die Quadratwurzel. Die Lösung nennt man auch euklidische Distanz. Um die Ähnlichkeit oder Verschiedenheiten von zwei und mehreren Objekten zu beurteilen, werden unterschiedliche Proximitätsmaße verwendet. Man kann die Manhattan-Distanz oder die euklidische Distanz verwenden, oft wird aber die euklidische Distanz verwendet.[4]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Euklidische Distanz[5]

2 Partitionierendes Clustering

Die Partitionierungsmethode besteht im Wesentlichen darin, eine Menge von Daten in eine vordefinierte Anzahl von Clustern einzuteilen, d.h. die Clusteranzahl k muss vor dem Start festgelegt werden. Wenn sich eine Gruppierung durch weiteres Verschieben von Objekten nicht mehr verbessern lässt und ein vorgegebenes Optimum erreicht ist, endet das Verfahren. Es ist von der Startpartition abhängig und sehr rechenintensiv. Bei dieser Methode weiß man jedoch nicht, welcher Wert von k optimal ist. Daher sollte man ein iteratives Verfahren verwenden, bei der die Objekte iterativ immer wieder neu zugeordnet werden, bis das Clustering und die Bewertungsfunktion optimal ist. K-Means, ein beliebter Clustering Algorithmus, der dieses Verfahren implementiert. Im nächsten Kapitel wird dieser Algorithmus beschrieben und untersucht.[6]

2.1 K-Means Algorithmus

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Zielfunktion[7]

K-Means ist ein bekanntes, nichtüberwachtes Verfahren zum partitionierenden Clustern. In dem folgenden Abschnitt wird die K-Means Clustering Methode vorgestellt und untersucht. Aus Anschauungsgründen wird auf den 2-dimensionalen Euklidischen Raum beschränkt.

Die Besonderheit des K-Means ist es, dass er schnell die Zentren der Cluster findet. Durch die Einfachheit des K-Means Algorithmus ist es mit Abstand der beliebteste und bei weitem am häufigsten verwendete Cluster-Algorithmus.[8]

Zu Beginn muss die Anzahl der Cluster (Parameter K) bekannt sein. Um die Datenpunkte, die sich in demselben Gebiet befinden, einem Cluster zuordnen zu können, sollte für jeden Cluster gute Zentroide (Clusterzentren) gefunden werden. Im Folgenden Beispiel werden die Daten in zwei Cluster (K=2) aufgeteilt, man hat also zwei Zentroide. Der Schwerpunkt spielt beim Finden von geeigneten Clusterzentren eine wichtige Rolle. K-Means ist ein iterativer Algorithmus. Das bedeutet, dass der Grundschritt wiederholt durchlaufen wird, bis sich die Zentren nicht mehr oder nur noch wenig verschieben. Erst dann hat man sein gewünschtes Ergebnis erreicht.

Durch die Zielfunktion wird das Ziel eines Clusterverfahrens ausgedrückt. Das Ziel ist es die Funktion in Abbildung 4 zu minimieren. Eine typische Zielfunktion ist die Summe der quadratischen Abstände zum Zentrum SSE (Sum of Squared Errors), die auch Fehlerquadratsumme genannt wird.[9]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Fehlerquadratsumme[10] wobei Ci das i-te Cluster ist und ci das Zentrum des i-ten Clusters ist der euklidische Abstand.[11]

Mit der Clusteranalyse soll die „beste Anpassung“ ermittelt werden. Dies geschieht durch wiederholte Berechnungen (Iterationen), um die Gruppen (Segmente) näher zu bringen. Wenn die Segmentwerte genau übereinstimmen, wäre die Summe des quadratischen Fehlers (SSE) gleich null. Das bedeutet, dass es keine Fehler gibt und es somit die perfekte Übereinstimmung ist. Doch mit realen Daten ist dies sehr unwahrscheinlich, daher muss nach einem Segmentierungsansatz gesucht werden, der eine niedrigere SSE aufweist. Je niedriger die SSE ist, desto ähnlicher sind die „Verbraucher“ in diesem Marktsegment (Cluster). Eine hohe SSE würde bedeuten, dass es kein brauchbares Cluster ist. Der niedrigste Wert des SSE wird erreicht, indem man die Zentren als arithmetisches Mittel der Clusterpunkte wählt.[12]

Der Algorithmus läuft folgendermaßen ab:

1. K = die Anzahl der Cluster wird festgelegt
2. Zufällige Auswahl von k Clusterzentren
3. Die Euklidischen Abstände werden von den Clusterzentren zu jedem einzelnen Datenobjekt berechnet. Somit wird jedes Datenobjekt zu einem Clusterzentrum zugeordnet, der am nächsten vorliegt
4. Für jeden Cluster werden neue Clusterzentren berechnet, dies geschieht durch die Mittelwertbildung aller Datenobjekte in einem Cluster
5. Schritt 3 wird solange wiederholt, bis sich die Zuordnung der Datenobjekte stabil bleibt, ansonsten bricht sie ab.[13]

Abbildung 6 zeigt die Arbeitsweise des K-Means Algorithmus. Bild (a) zeigt die Datenobjekte. In Bild (b) sieht man zu zufällig gewählten Clusterzentren, die als Kreuze dargestellt sind. In Bild (c-f) sieht man bereits, wie sich die Zentren sich jedes Mal verschieben und die Datenobjekte sich zuordnen. In Bild (f) befinden sich die Zentren gut in der Mitte der Datenobjekte. Somit ist auch eine stabile Situation erreicht.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Arbeitsweise des K-means Algorithmus[14]

Vorteile

- Einfach und intuitiv
- Ziemlich effizienter Algorithmus: In O(tKn) pro Iteration, n ist die Anzahl der Objekte, K die Anzahl der Cluster und t die Anzahl der Iterationen. K,t << n, die Anzahl der Cluster sowie die Anzahl der Iterationen ist viel kleiner wie die Anzahl der Objekte
- Der Algorithmus terminiert oft bei einem lokalen Optimum.[15]

Nachteile

- Ein Wesentlicher Nachteil ist, dass das Ergebnis der Clusterbildung von den Startpositionen abhängt. Daher sollte man immer einige Versuche mit unterschiedlichen Startpositionen machen.
- Die Anzahl der Cluster muss im Voraus definiert sein
- Ausreißer haben großen Einfluss auf SSE
- K-Means hat Probleme Cluster zu erkennen, keine kugelförmige Struktur haben[16]

2.2 Initialisierung des K-Means

Die Qualität des K-Means Clustering hängt stark davon ab, welche Anzahl der Cluster man im Voraus definiert. Für unterschiedliche Initialisierungen werden unterschiedliche Ergebnisse berechnet. Um die optimale Anzahl der Cluster in den Daten zu finden, muss der Benutzer den Algorithmus für einen Bereich von K-Werten ausführen und die Ergebnisse vergleichen. Eine der Metriken, die zum Vergleichen von Ergebnissen verwendet wird, ist der mittlere Abstand zwischen Datenpunkten und ihrem Clusterzentrum. Diese Metrik kann nicht als einziges Ziel verwendet werden, stattdessen wird der mittlere Abstand zum Clusterzentrum als Funktion von K aufgetragen. Somit wird der “elbow point”, an dem sich die Abnahmerate stark ändert, verwendet, um K grob zu bestimmen.[17]

[...]


[1] Backhaus (2003), S.453

[2] Sarsted (2014)

[3] Vgl: http://www.datamining4u.nl/data-mining-clusteranalyse.php

[4] Vgl: http://www.staedtestatistik.de/fileadmin/vdst/ag-methodik/Leitfaeden/2008_AGMethodik_LeitfadenClusteranalyse_Teil2.pdf

[5] Vgl: http://jtleek.com/genstats_site/lecture_notes/01_12_Clustering.pdf

[6] Vgl: http://campar.in.tum.de/twiki/pub/Far/MachineLearningWiSe2003/oender_ausarbeitung.pdf

[7] Vgl: https://de.wikipedia.org/wiki/K-Means-Algorithmus

[8] Vgl: http://www.statistics4u.com/fundstat_eng/ee_kmeans_clustering.html

[9] Vgl: https://hlab.stanford.edu/brian/error_sum_of_squares.html

[10] Vgl: https://hlab.stanford.edu/brian/error_sum_of_squares.html

[11] Vgl: https://www-m9.ma.tum.de/material/felix-klein/clustering/Methoden/K-Means.php

[12] Vgl: http://www.clusteranalysis4marketing.com/interpretation/sum-of-squared-error-sse/

[13] Vgl: http://www.statistics4u.com/fundstat_eng/ee_kmeans_clustering.html

[14] Vgl: http://stanford.edu/~cpiech/cs221/handouts/kmeans.html

[15] Vgl: https://de.slideshare.net/kasunrangawijeweera/k-means-clustering-algorithm

[16] Vgl: http://optiv.de/Methoden/ClustMet/index.htm?14

[17] Vgl: https://www.datascience.com/blog/k-means-clustering

Details

Seiten
27
Jahr
2018
ISBN (eBook)
9783668849570
ISBN (Buch)
9783668849587
Sprache
Deutsch
Katalognummer
v452144
Institution / Hochschule
Hochschule Reutlingen
Note
1,3
Schlagworte
clustering k-means dbscan

Autor

Teilen

Zurück

Titel: Clustering. Die Clusteranalysen K-means und DBSCAN im Vergleich