Daten gesammelt, Daten vorbereitet und nun? Wie können wir aufbereitete Daten analysieren um Wissen zu gewinnen? Hier ist der k-Means-Algorithmus ein beliebtes Hilfsmittel, der mitunter auch die Analyse im Big-Data-Umfeld zu einen Kinderspiel macht. In den folgenden Artikel wird gezeigt wie Unternehmen durch dieses einfachen Verfahren Kosten senken können ohne Einbußen hinzunehmen.
Eine grundlegende Analytics Methode Daten aufzuarbeiten ist es die Gesamtheit der Daten zu clustern. Das Ziel einer Clusteranalyse ist es Ähnlichkeitsstrukturen in großen Datenbeständen aufzuzeigen und diese in Gruppen zu unterteilen. Bei dem k-Means-Algorithmus handelt es sich um eine Reihe von Befehlen, welche diese Gruppierung von Objekten übernimmt. Da es sich hierbei um ein sehr effektives Verfahren handelt, ist es für die Analyse großer Mengen von Daten, wie sie im Big-Data-Bereich anzutreffen sind, geeignet.
Jeder Gruppe, sogenannte Cluster, werden durch einen geeigneten zentralen Datenpunkt repräsentiert, dadurch verringert sich die Anzahl der zu untersuchenden Elemente erheblich. Wie verlieren dadurch offenbar Informationen, den die exakte Position alle Datenpunkte sind uns nicht mehr bekannt, jedoch bleiben durch gutes Clustering die wichtigen Informationen erhalten.
Der k-Means-Algorithmus stammt aus einer Zeit in welcher das heutige Internet nur als futuristische Idee in Büchern erdacht wurde. Dieser geht auf eine Idee von Hugo Steinhaus aus dem Jahre 1957 zurück. Dadurch, dass dieser Algorithmus mehrere Befehle in Schleife abarbeitet, diese also beliebig wiederholt werden, ist dieser für jede Größe von Daten anwendbar.
Ablauf des k-Means-Algorithmus
Um eine endliche Anzahl von Daten in eine beliebige Anzahl von ähnlichen Gruppen einzuteilen und für jede Gruppe einen repräsentativen Datenpunkt zuzuordnen muss der Algorithmus mehrere Male durchlaufen werden. Im Allgemeinen gilt, je größer die Anzahl der zu betrachtenden Daten, um so öfters werden die Befehle wiederholt. Dies führt dazu den möglichst besten Repräsentanten für die Gruppen herauszufinden und den Informationsverlust denkbar klein zu halten.
Die Ausgangslage um den k-Means-Algorithmus durchzuführen ist eine Datenbank mit n-Datenpunkte und eine Festlegung der Aufteilung in k-Gruppen, also die Anzahl in wie vielen Gruppen geclustert werden soll. Nun folgt der eigentliche Algorithmus:
- Auswahl der k-Clusterpunkte – diese werden entweder durch Zufall oder durch eine Schätzung ausgewählt.
- Clustering – Zuordnung jedes Datenpunkt zum nächstgelegenen Clusterpunkt.
- Neuberechnung der Clusterzentren – Erschaffung neuer Clusterpunkte durch berechnen des gewichteten Mittel des vorläufigen Cluster.
Mit den neu errechneten Clusterpunkten geht es nun wieder zurück zum zweiten Schritt. Dieses Verfahren wird beendet, sobald eine zu Beginn festgelegte Anzahl an Wiederholungen erreicht ist, oder wenn durch eine Neuberechnung die Zuordnung der Datenpunkte zum jeweiligen Cluster nicht mehr verändert wird.
Stellen Sie sich k-Körbe vor, welchen wir jeweils einen Clusterpunkt zuordnen. Nun legen wir die Datenpunkte in den Korb zu dem er am wenigsten Abstand hat. Wurden alle Punkte in einen der Körbe gelegt berechnen wir nun einen neuen Clusterpunkt und damit neue Körbe und wiederholen die Zuordnung. Sobald sich der Inhalt des neuen Korbes zum vorherigen nicht mehr geändert hat beenden wir den Vorgang.
Probleme bei der Anwendung des k-Means-Algorithmus
Der k-Means-Algorithmus kann mit n-dimensionalen Datenpunkten arbeiten. Das heißt die Datenpunkte können n-beliebige Eigenschaften besitzen, jedoch muss bei jeden Datenpunkt jeder dieser Eigenschaften betrachtet werden und darf nicht ausgelassen werden. Wichtig ist das die Eigenschaften durch Zahlen ausgedrückt werden.
Wenn wir zum Beispiel ein Tier durch Eigenschaften wie Größe, Gewicht, Geschlecht, Alter, Lebensraum usw. beschreiben wollen müssen alle Tiere, welche betrachtet werden sollen diese Eigenschaften aufweisen. Eigenschaften, welche normalerweise nicht mit Zahlen gekennzeichnet werden, müssen durch eine codiert werden. Bei dem Geschlecht wäre eine mögliche Übersetzung 0 für männliche und 1 für weibliche Tiere, bei der Eigenschaft des Lebensraum können verschiedene Gebiete unterschiedlichen Zahlen, wie bei den Postleitzahlensystem, zugeordnet werden. Ein Datenpunkt, eines männlichen Schäferhundes, innerhalb einer Hundedatenbank könnte beispielweise wie folgt aussehen {5; 62; 35; 0; 4} in der Reihenfolge {Rasse; Größe in cm; Gewicht in kg; Geschlecht; Alter in Jahren}, welche bei jeden Datenpunkt eingehalten werden muss.
Der der Algorithmus alle Datenpunkte einen Clusterpunkt zuordnet können Ausreißer die Bildung der Cluster stark verfälschen. Aus diesem Grund ist vor der Auswertung eine Bereinigung der Daten nötig.
Die Ausgangslage der Startpunkte ist von wichtiger Bedeutung, da nicht jede Wahl der Anfangsclusterpunkt zur gleichen Einteilung führt, wie im kommenden Beispiel erkennbar ist. Dort ist zu erkennen wie zwei unterschiedliche Cluster aus identischen Datenpunkten entsteht, indem der Anfangsclusterpunkt anders gewählt wurde. Wie k-Means die Gruppen ausarbeitet ist abhängig von der Wahl der ersten Clusterpunkte. Jedoch gibt es zwei einfache Möglichkeiten diesen Effekt entgegenzuwirken. Wenn die Anfangspunkte zufällig ausgewählt werden, führen sie das Experiment mehrmals durch, bis das Ergebnis zufriedenstellend ist. Kenne deine Daten und „schätze“ eine gute Ausgangslage.
Anwendungsmöglichkeiten des k-Means-Algorithmus
Der k-Means-Algorithmus kann durch seiner effizienten Nutzung des Speicher- und Rechenbedarfs für sehr große Datenmengen im Big-Data-Umfeld genutzt werden. Wichtige Anwendungsbereiche sind Marketing und die Analyse des Kundenverhaltens, aber auch in der Bildverarbeitung wird dieses Verfahren häufig angewandt.
Was hat Bildverarbeitung mit n-dimensionalen Datenpunkten zu tun? Jeder Pixel eines Bildes kann eine Farbe annehmen. Jede Farbe besteht aus den drei Farbkanälen, diese sind die Grundfarben rot, grün und blau und bilden den RGB-Farbraum. Innerhalb eines Farbkanals stehen 256 Werte, wobei 0 = dunkel und 255 = hell bedeutet. Dadurch kann jede mögliche Farbe mit drei Zahlen in der Reihenfolge des Rot-, Grün- und Blauanteils beschrieben werden, z.B. (247;80;2) ist der Orangeton unseres Logos. Ein Bild ist also nur eine Ansammlung von Datenpunkten mit jeweils drei Eigenschaften, welche wir mit Hilfe des Verfahren Clustern können.
Der Nutzen den ein Unternehmen daraus ziehen kann, ist die Einsparungen von Speicherplatz, welcher durch die Komprimierung der Bilddateien geschaffen wird. Hierbei werden durch den k-Means-Algorithmus die geeignetsten k-Farben herausgefunden, ohne dass der Inhalt des Bildes nicht mehr zu erkennen ist.
Wie im obigen Beispiel zu sehen, verringert sich der Speicherbedarf des Bilds nicht linear zur Farbanzahl, sondern steigt anfangs stark an und flacht ab. Der Kern des Bildes ist bei jedem gut zu erkennen, wobei zwischen den Originalbild und die Begrenzung auf 15 Farben, kaum ein Unterschied zu erkennen ist, obwohl der Speicherbedarf sich auf 60% reduziert hat. Anhand dieses Beispiels ist wieder zu erkennen, wie wichtig die Auswahl der richtigen Anfangsclusterpunkte ist.
Der k-Means-Algorithmus sieht nicht nur in der Theorie logisch aus, sondern lässt sich auch im Unternehmen effektiv einsetzen. Mit Hilfe des Algorithmus können Produktionsstandards festgelegt werden um Qualitätsstandards einzuhalten. Dadurch können die Produkte automatisch in unterschiedlichen Qualitätsstufen mit verschiedenen Preisen eingeteilt werden. So kann Qualität und Sicherheit für Produkte gewährleistet werden und Fehlproduktionen werden leicht erkannt und aussortiert.
Nicht nur bei der Produktion kann das Verfahren einen durschlagenden Erfolg bringen, sondern auch bei der Segmentierung der Kunden. Durch die Einteilung von Kunden in Kundengruppen, können zugeschnittene Werbekampagnen durchgeführt werden. Durch bestehende Kundendaten, wie demografische und ökonomische Kriterien, können Kunden unterteilt werden. Im Bereich Sport wäre beispielsweise eine Unterteilung in Ballsportarten, Kraftsport und Radsport möglich. Diese Einteilungen erlauben gezielte Werbemaßnahmen.
Der k-Means-Algorithmus kommt in vielen weiteren Anwendungsbereich zum Einsatz. Bei der Fehleranalyse im Unternehmen, Analyse des Kaufverhalten von Kunden, die Suchmaschinenoptimierung, Spamidentifikation, aber auch in Gebieten der Archäologie, Botanik, Medizin, …. Clustering begegnet uns im alltäglichen Leben, es ist nicht nur die zweckmäßige Unterteilung von Daten, sondern das auffinden von Strukturen in diesen Daten und die Verdeutlichung in Statistiken sodass aus den Strukturen Wissen gewonnen und effektiv eingesetzt werden kann.
