Posts

Unsupervised Learning in R: K-Means Clustering

Die Clusteranalyse ist ein gruppenbildendes Verfahren, mit dem Objekte Gruppen – sogenannten Clustern zuordnet werden. Die dem Cluster zugeordneten Objekte sollen möglichst homogen sein, wohingegen die Objekte, die unterschiedlichen Clustern zugeordnet werden möglichst heterogen sein sollen. Dieses Verfahren wird z.B. im Marketing bei der Zielgruppensegmentierung, um Angebote entsprechend anzupassen oder im User Experience Bereich zur Identifikation sog. Personas.

Es gibt in der Praxis eine Vielzahl von Cluster-Verfahren, eine der bekanntesten und gebräuchlichsten Verfahren ist das K-Means Clustering, ein sog. Partitionierendes Clusterverfahren. Das Ziel dabei ist es, den Datensatz in K Cluster zu unterteilen. Dabei werden zunächst K beliebige Punkte als Anfangszentren (sog. Zentroiden) ausgewählt und jedem dieser Punkte der Punkt zugeordnet, zu dessen Zentrum er die geringste Distanz hat. K-Means ist ein „harter“ Clusteralgorithmus, d.h. jede Beobachtung wird genau einem Cluster zugeordnet. Zur Berechnung existieren verschiedene Distanzmaße. Das gebräuchlichste Distanzmaß ist die quadrierte euklidische Distanz:

D^2 = \sum_{i=1}^{v}(x_i - y_i)^2

Nachdem jede Beobachtung einem Cluster zugeordnet wurde, wird das Clusterzentrum neu berechnet und die Punkte werden den neuen Clusterzentren erneut zugeordnet. Dieser Vorgang wird so lange durchgeführt bis die Clusterzentren stabil sind oder eine vorher bestimmte Anzahl an Iterationen durchlaufen sind.
Das komplette Vorgehen wird im Folgenden anhand eines künstlich erzeugten Testdatensatzes erläutert.

Zunächst wird ein Testdatensatz mit den Variablen „Alter“ und „Einkommen“ erzeugt, der 12 Fälle enthält. Als Schritt des „Data preprocessing“ müssen zunächst beide Variablen standardisiert werden, da ansonsten die Variable „Alter“ die Clusterbildung zu stark beeinflusst.

Das Ganze geplottet:

Wie bereits eingangs erwähnt müssen Cluster innerhalb möglichst homogen und zu Objekten anderer Cluster möglichst heterogen sein. Ein Maß für die Homogenität die „Within Cluster Sums of Squares“ (WSS), ein Maß für die Heterogenität „Between Cluster Sums of Squares“ (BSS).

Diese sind beispielsweise für eine 3-Cluster-Lösung wie folgt:

Sollte man die Anzahl der Cluster nicht bereits kennen oder sind diese extern nicht vorgegeben, dann bietet es sich an, anhand des Verhältnisses von WSS und BSS die „optimale“ Clusteranzahl zu berechnen. Dafür wird zunächst ein leerer Vektor initialisiert, dessen Werte nachfolgend über die Schleife mit dem Verhältnis von WSS und WSS gefüllt werden. Dies lässt sich anschließend per „Screeplot“ visualisieren.

Die „optimale“ Anzahl der Cluster zählt sich am Knick der Linie ablesen (auch Ellbow-Kriterium genannt). Alternativ kann man sich an dem Richtwert von 0.2 orientieren. Unterschreitet das Verhältnis von WSS und BSS diesen Wert, so hat man die beste Lösung gefunden. In diesem Beispiel ist sehr deutlich, dass eine 3-Cluster-Lösung am besten ist.

Fazit: Mit K-Means Clustering lassen sich schnell und einfach Muster in Datensätzen erkennen, die, gerade wenn mehr als zwei Variablen geclustert werden, sonst verborgen blieben. K-Means ist allerdings anfällig gegenüber Ausreißern, da Ausreißer gerne als separate Cluster betrachtet werden. Ebenfalls problematisch sind Cluster, deren Struktur nicht kugelförmig ist. Dies ist vor der Durchführung der Clusteranalyse mittels explorativer Datenanalyse zu überprüfen.

R Data Frames meistern mit dplyr – Teil 1

Dieser Artikel ist Teil 1 von 2 aus der Artikelserie R Data Frames meistern mit dplyr.

Data Frames sind das Arbeitspferd von R, wenn Daten in eine Struktur gepackt werden sollen, um sie einzulesen, zu säubern, zu transformieren, zu analysieren und zu visualisieren. Abstrakt gesprochen sind Data Frames nichts anderes als Relationen, also Mengen von Tupels, gebildet aus Elementen von geeigneten Mengen.

Dieses Konzept hat sich auch außerhalb des R-Universums bestens bewährt, umzusammengesetzte Daten, Beobachtungen oder Geschäftsobjekte zu repräsentieren. Der beste Beleg für diese Aussage sind die allgegenwärtigen Relationalen Datenbanksysteme (RDBMS). Dort werden Relationen als Tabellen (Tables) oder Sichten (Views) bezeichnet, und darauf wirkt eine mächtige, imperative Abfrage- und Manipulationssprache namens Structured Query Language, kurz:
SQL.

SQL ist in meiner Wahrnehmung die Lingua Franca der Datenverarbeitung, da sie im Kern über sehr viele Softwareprodukte gleich ist und nach erstaunlich geringem Lernaufwand mächtige Auswerte- und Manipulationsoperationen an den Daten ermöglicht. Hier eine SQL-Anweisung, um eine fiktive Tabelle aller Verkäufe (SALES) nach den Top-10-Kunden in diesem Jahr zu untersuchen:

Dieser selbsterklärliche Code aus sieben Zeilen hat einen enormen Effekt: Er fast alle Verkäufe des Jahres 2016 auf Basis der Kundennummer zusammen, berechnet dabei die Summe aller Verkaufsbeträge, zählt die Anzahl der Transaktionen und der verschiedenen vom Kunden gekauften Produkte. Nach Sortierung gemäß absteigenden Umsatzes schneidet der Code nach dem 10. Kunden ab.

SQL kann aber mit der gleichen Eleganz noch viel mehr: Beispielsweise verbinden Joins die Daten mehrerer Tabellen über Fremschlüsselbeziehungen oder analytische Funktionen bestimmen Rankings und laufende Summen. Wäre es nicht toll, wenn R ähnlich effektiv mit Data Frames analoger Struktur umgehen könnte? Natürlich! Aber schon der Versuch, obige SQL-Query auf einem R Data Frame mit den althergebrachten Bordmitteln umzusetzen (subset, aggregate, merge, …), führt zu einem unleserlichen, uneleganten Stück Code.

Genau in diese Bresche springt der von vielen anderen Bibliotheken bekannte Entwickler Hadley Wickham mit seiner Bibliothek dplyr: Sie standardisiert Operationen auf Data Frames analog zu SQL-Operationen und führt zu einer wirklich selbsterklärlichen Syntax, die noch dazu sehr performant abgearbeitet wird. Ganz analog zu ggplot2, das sich an der Grammar of Graphics orientiert, spricht Wickham bei dplyr von einer Grammar of Data Manipulation. Die Funktionen zur Manipulation nennt er folgerichtig Verben.

Dabei treten naturgemäß eine Reihe von Analogien zwischen den Teilen eines SELECT-Statements und dplyr-Funktionen auf:

SELECT-Operation dplyr-Funktion
Bildung der Spaltenliste select()
Bildung eines Ausdrucks mutate()
WHERE-Klausel filter()
GROUP BY Spaltenliste group_by()
Bildung von Aggregaten wie sum() etc. summarise()
HAVING-Klausel filter()
ORDER BY Spaltenliste arrange()
LIMIT-Klausel slice()

Die ersten Schritte

Ich möchte die Anwendung von dplyr mithilfe des Standard-Datensatzes Cars93
aus dem Paket MASS demonstrieren:

Die erste Aufgabe soll darin bestehen, aus dem Data Frame alle Autos zu selektieren, die vom Hersteller “Audi” stammen und nur Model und Anzahl Passagiere auszugeben. Hier die Lösung in Standard-R und mit dplyr:

Man sieht, dass die neue Funktion filter() der Zeilenselektion, also der Funktion subset() entspricht. Und die Auswahl der Ergebnisspalten, die in Standard-R durch Angabe einer Spaltenliste zwischen [ und ] erfolgt, hat in dplyr das Pendant in der Funktion select().

select() ist sehr mächtig in seinen Möglichkeiten, die Spaltenliste anzugeben. Beispielsweise funktioniert dies über Positionslisten, Namensmuster und ggf. das auch noch negiert:

Die obige Abfrage projiziert aus dem Data Frame sämtliche Spalten, die nicht mit “L” beginnen. Das scheint zunächst ein unscheinbares Feature zu sein, zahlt sich aber aus, wenn analytische Data Frames Dutzende oder Hunderte von Spalten haben, deren Bezeichnung sich nach einem logischen Namensschema richtet.
Soweit ist das noch nicht spektakulär. dplyr hilft uns in obigem Beispiel, als erstes bestimmte Datensätze zu selektieren und als zweites die interessierenden Spalten zu projizieren. dplyr ist aber bezüglich der Verarbeitung von Data Frames sehr intuitiv und funktional, sodass wir früher oder später viele Operationen auf unserem Data Frame verketten werden. So erreichen wir die Mächtigkeit von SQL und mehr. Die funktionale Syntax aus dem letzten Beispiel wird dann ganz schnell unleserlich, da die Verabeitungsreihenfolge (zuerst filter(), dann select()) nur durch Lesen des Codes von innen nach außen und von rechts nach links ersichtlich wird.

Daher geht dplyr einen Schritt weiter, indem es den eleganten Verkettungsoperator %>% aus dem magrittr-Paket importiert und zur Verfügung stellt. Dadurch werden die verschachtelten Ausdrücke in Sequenzen von Operationen gewandelt und somit sehr viel lesbarer und wartbarer:

Diese in meinen Augen geniale Syntax durch den neuen Operator %>% erlaubt einen sequenziellen Aufbau der Operationen auf einem Data Frame. Benutzer der Unix-Kommandozeile werden hier leicht die Analogie zu Pipes erkennen. Ganz abstrakt kann man sagen, dass damit folgende Operationen äquivalent sind:

Traditioneller Funktionsaufruf Verkettung mit %>%
f(a,b) a %>% f(b)
f(a,b,c) a %>% f(b,c)
g(f(a,b),c) a %>% f(b) %>% g(c)

Weiteres erklärt die Dokumentation zum %>%-Operator im Paket magrittr mithilfe
des Befehls ?magrittr::‘%>%‘.

Neue Variablen

Durch die Funtionen select() und filter() können wir aus Data Frames Spalten projizieren und Zeilen selektieren. Ergebnisse neuer Ausdrücke entstehen hingegen mit dem Verb mutate():

Im obigen Beispiel wird zunächst auf den Hersteller Audi selektiert und danach auf einen Streich zwei neue Spalten eingeführt, l_100km und eur. Durch Zuweisen auf eine neue Variable wird das fertige Ergebnis dauerhaft gespeichert. Hierbei handelt es sich wieder um ein natives Data Frame-Objekt. Die Operation transmute() arbeitet analog zu mutate(), verwirft aber nach Bildung der Ausdrücke alle nicht genannten Spalten. Somit können wir obiges Beispiel auch wie folgt schreiben:

Aggregate

Neben der Selektion von Zeilen und Spalten sowie der Bildung abgeleiteter Ausdrücke ist bei Datenbanktabellen die Gruppierung und Aggregation mit GROUP BY eine sehr wichtige Operation. Dies gilt auch für Data Frames in R, wenngleich hier der Funktionsumfang über diverse Funktionen wie table() oder aggregate() verteilt ist und wenig intuitiv ist.

Hier bringt dplyr ebenfalls eine großartige Verbesserung mit. Das entsprechende Verb heißt group_by(). Diese Operation wird zusammen mit einer Spaltenliste auf ein Data Frame angewendet:

Das Ergebnis von group_by() ist ein Objekt, das “mehr” ist als ein Data Frame, sondern auch noch einige spezifische Strukturinformationen von dplyr enthält. In unserem Beispiel sind dies Indizes von Zeilen, die zum gleichen Hersteller gehören. Das ursprüngliche Data Frame wird hierbei nicht kopiert, sondern nur eingebettet.

Nach Anwenden einer group_by()-Operation ist das Data Frame optimal vorbereitet für die eigentliche Aggregation mit summarise():

Das Resultat von summarise() ist wieder ein Data Frame, das neben den ursprünglichen Gruppierungskriterien nur noch die Aggregate enthält.

Daten in Reih’ und Glied

Zwischen Relationalen Datenbanken und R-Data Frames besteht ein wesentlicher konzeptioneller Unterschied: Die Ergebnisse eines SELECT-Befehls haben keine definierte Reihenfolge, so lange die Zeilen nicht mit der Klausel ORDER BY festgelegt wird. Im Gegensatz dazu haben die Zeilen von Data Frames eine konstante Reihenfolge, die sich aus der Anordnung derWerte in den Spaltenvektoren ergibt.

Dennoch ist es manchmal wünschenswert, Data Frames umzusortieren, um eine fachliche Reihenfolge abzubilden. Hierzu dient in dplyr das Verb arrange(), das im Standard-R weitgehend der Indizierung eines Data Frames mit Ergebnissen der order()-Funktion entspricht, aber syntaktisch eleganter ist:

Dieses Beispiel hat zum Ziel, die fünf PS-stärksten Autos zu selektieren. Die arrange()-Funktion sortiert hier zunächst absteigend nach der PS-Stärke, dann aufsteigend nach Herstellername. Die Selektion der 5 ersten Zeilen erfolgt mit der hilfreichen Funktion slice(), die aus einem Data Frame Zeilen anhand ihrer Reihenfolge selektiert.

Fazit und Ausblick

Mit dplyr wird die Arbeit mit Data Frames stark verbessert: Im Vergleich zu “nacktem” R bringt das Paket eine klarere Syntax, abgerundete Funktionalität und bessere Performance. In der Kürze dieses Artikels konnte ich dies nur oberflächlich anreissen. Daher verweise ich auf die vielen Hilfe-Seiten, Vignetten und Internet-Videos zum Paket. Im zweiten Teil dieses Artikels werde ich auf einige fortgeschrittene Features von dplyr eingehen, z.B. die Verknüpfung von Data Frames mit Joins, die Window-Funktionen und die Verwendung von Datenbanken als Backend.

Weiter zu R Data Frames meistern mit dplyr – Teil 2.

Die Abschätzung von Pi mit Apache Spark

Auf den Berliner Data Science/Big Data/Data Analytics/…-Meetups auf denen ich in letzter Zeit des Öfteren zugegen war, tauchte immer wieder der Begriff Spark auf. Ich wollte wissen was es hiermit auf sich hat. Nachdem ich Spark 1.5.1 lokal auf meinem Mac installiert hatte, fing ich an Wörter in frei verfügbaren Texten zu zählen. Da es mir aber zu aufwändig schien, extrem lange Texte im Internet zu suchen und ich ein Gefühl für die Leistungsfähigkeit von Spark bekommen wollte, widmete ich mich einem skalierbaren Problem: der Abschätzung von Pi mit der Monte Carlo-Methode.

 1000 Zufallspunkte lokal auf Mac

spark-scala-interface-pi-example

Dies war wie zu erwarten keine Herausforderung für meine Hardware. Was passiert bei 10^6/ 10^7/ 10^8/ 10^9… Zufallspunkten?

dataset-spark-pi-example-1

An dieser Stelle stieß ich auf ein “Integer-Problem“. Weil 3*10^9 > 2^31 – 1, kann in diesem Fall nicht mehr der Datentyp Integer verwendet werden, sondern man müsste „long Integer“ (64 bit) nehmen. Was mich nun jedoch viel mehr interessierte als mit Zufallspunkten > 2^31 – 1  zu experimentieren, war eine Spark-Installation auf AWS und die entsprechenden Berechnungszeiten. Ich installierte Spark 1.5.0 (auf Hadoop 2.6.0 YARN) auf einem AWS-Cluster (2 Core/1 Master x m3.xlarge). Zu meiner Überraschung ergab sich Folgendes:

dataset-spark-pi-example-2

Warum war mein Mac schneller als ein AWS-Cluster? Eine m3.xlarge-Instanz hat 4 Kerne und 15 GB Arbeitsspeicher, mein Mac ziemlich genau die Hälfte… Gut, dann probieren wir das Ganze mal mit einem 4 Core/1 Master x m3.xlarge-Cluster.

dataset-spark-pi-example-3

Es ergibt sich kein signifikanter Unterschied. Erst die Verwendung von einem 3 Core/1 Master x r3.2xlarge-Cluster brachte eine Beschleunigung. Wo ist der Flaschenhals? Um Netzwerkeffekte zu prüfen, habe ich schließlich eine 0 Core/1 Master-AWS-Installation getestet.

dataset-spark-pi-example-4

Dieser letzte Test skalierte zu meinen vorherigen Tests auf dem AWS-System, und er wies darauf hin, dass der Flaschenhals kein Netzwerkeffekt war.

Bei heise Developer fand ich einen sehr interessanten Artikel, welcher sich dem Thema „optimale Konfiguration der virtualisierten Cloud-Hardware für den jeweiligen Anwendungsfall finden“ widmet: Benchmarking Spark: Wie sich unterschiedliche Hardware-Parameter auf Big-Data-Anwendungen auswirken

Für heute belasse ich es bei dem vorgestellten Experiment.

To be continued…,