Ein menschlicher Beobachter erfasst die Ballungszentren in einer zweidimensionalen Punktemenge unmittelbar. Künstliche Intelligenz tut sich da noch etwas schwerer, doch das relativ simple k-means-Verfahren liefert schon ganz brauchbare Ergebnisse.
Bei der im letzten Perl-Snapshot generierten Landkarte mit amerikanischen Nationalparks ([2]) fragt sich der Naturfreund freilich, wie er die verschiedenen Attraktionen möglichst resourcenschonend abklappern kann. Ein Blick auf Abbildung 1 offenbart, dass sich die Parks in bestimmten Gegenden häufen und ein Tourist mit nur einer Flugreise in die USA vielleicht ein Dutzend Naturschauspiele auf einmal erfahren und erwandern kann.
| |
| Abbildung 1: Amerikanische Nationalparks häufen sich in bestimmten Gegenden. |
Das menschliche Gehirn erfasst die Ballungszentren der digitalen Reißnägel auf der Landkarte ohne nennenswerte Anstrengung. Schon in Sekundenbruchteilen steht fest, dass sich die meisten Nationalparks im Westen der kontinentalen Vereinigten Staaten bündeln, einige im Südosten, dann noch sechs Parks hoch oben in Alaska, und einige weiter entferntere auf den Inseln von Hawaii, Samoa und Puerto Rico.
Ein Computer hat nicht diesen "Überblick" und muss die sogenannten Cluster mühevoll errechnen. Das Buch "Data Analysis With Open Source Tools" ([3]) erläutert die Implementierung einer Reihe von mehr oder weniger erfolgversprechenden Verfahren, die allerdings allesamt dem menschlichen Gehirn unterlegen sind, wie sich an einfachen Gegenbeispielen, an denen sie jämmerlich versagen, zeigen lässt.
Wer dennoch nach automatischen Lösungen sucht, kommt nicht umhin, einen der halbwegs funktionierenden Algorithmen zu programmieren. Die "Clustering Library" ([4]) implementiert die gängisten, und das CPAN-Modul Algorithm::Cluster setzt ein Perl-Interface auf die Bibliothek. Die auf dem CPAN verfügbare und dem Modul beiliegende Dokumentation ist allerdings sehr dürftig, aber die auf [4] stehende PDF-Datei zur Clustering Library geht ab Seite 47 aber ausführlich auf die Benutzung von Algorithm::Cluster und den damit unterstützten Algorithmen ein.
Ausgangspunkt der Berechnungen ist die XML-Datei mit den Geodaten amerikanischer Nationalparks aus dem letzten im letzten Snapshot. Damals wurde sie auf zwei Arten generiert: Eimal mit Hilfe des Web-Services auf http://microform.at und einmal mit einem handgeschriebenen Scraper. Beidesmal basiert das Ergebnis auf frei erhältlichen Wikipedia-Daten. Abbildung 2 zeigt das Format, das die Namen der Parks mit deren Geodaten kombiniert. Ziel des aktuellen Snapshots ist das Einlesen dieser XML-Daten, die ein Cluster-Algorithmus dann in eine gruppierte Ausgabe mit geografisch zusammenliegenden Nationalparks umwandelt.
 |
| Abbildung 2: Von http://microform.at generierte XML-Datei mit den Mikroformaten aus der Wikipedia-Seite zu den amerikanischen Nationalparks. |
Das wohl gängigste Verfahren zum Finden von dichten Stellen in Punkthaufen
nennt sich k-means ([5]). Er setzt voraus, dass man vorab ungefähr weiß,
wie viele verschiedene Cluster der Algorithmus aufstöbern soll. Das ist
nicht immer gegeben, aber im vorliegenden Fall liegt es nahe, etwa ein
Dutzend Cluster
vorzugeben, denn wenn man die drei verstreuten Inselgruppen sowie
Alaska abzieht,
bleiben noch acht Zonen auf dem US-Festland. Das sollte eine brauchbare
Gruppierung ermöglichen, ohne dass die Parks eines Clusters zu weit
auseinander liegen.
 |
| Abbildung 3: Der K-Means-Algorithmus startet mit N zufälligen Zentroiden ... |
Der k-means-Algorithmus setzt zunächst willkürlich für jedes gesuchte
Cluster sogenannte Zentroide fest. Am Anfang liegen diese Punkte,
die später zu Mittelpunkten der gesuchten Cluster avancieren, zufällig im
Raum verteilt. Dabei zahlt es sich manchmal durchaus aus, die Zentroiden
intelligent zu platzieren, denn das Verfahren ist nicht stabil,
unterschiedliche Anfangsbedingungen führen zu unterschiedlichen Resultaten
und manche Startpunkte verursachen gar einen Kollaps. Für den Anfang
reicht aber eine zufällige Verteilung (Abbildung 3).
 |
| Abbildung 4: ... und weist alle Punkte dem jeweils nächstgelegenen Zentroiden zu. |
Dann berechnet ein Programm für jeden der N Nationalparks die Distanz zu jedem der K Zentroide und ordnet jeden Park dem nächstgelegenen Zentroiden zu, baut also einen Cluster aus diesen Parks. Aus den geografischen Daten der Parks eines Clusters lässt sich nun deren Gravitations-Mittelpunkt berechnen, in den der Algorithmus den Zentroiden dann verschiebt (Abbildung 5).
 |
| Abbildung 5: In den neu entstandenen Clustern wandern die Zentroiden in den Gravitationsmittelpunkt. |
Dieses Verfahren wiederholt der Algorithmus so lange, bis sich ein stabiler Zustand einstellt. Es kommt durchaus vor, dass vorläufig gebildete Cluster sich nach einigen Durchgängen wieder auflösen oder, umgekehrt, getrennte Cluster zu einem einzelnen verschmelzen. Abbildung 5 zeigt die Gruppierung der Nationalparks als Ausgabe des Skripts in Listing 1. Wenig überraschend beinhaltet der erste Cluster die beiden auf den hawaiianischen Inseln Big Island und Kauai liegenden Vulkan-Parks.
 |
| Abbildung 6: Der K-Cluster-Algorithmus gruppiert die Parks nach Gegend. |
Im nächsten Cluster liegen drei Parks im Nordwesten der USA im Bundesstaat Washington. Der dritte Cluster listet die acht Parks im kalten Alaska, der vierte die Insel Samoa und schließlich der fünfte drei Parks in Nordkalifornien.
Statt den Algorithmus von Hand zu programmieren, bietet es sich
an, das CPAN-Modul Algorithm::Cluster zu verwenden, das auf der
"Clustering Library" ([4]) aufbaut und neben k-means auch noch
weitere Verfahren anbietet. Einem Anwendungsskript
bleibt nur noch, die erforderliche Reihe von Datenstrukturen zur
Eingabe füllen und von einer Bibliotheksfunktion zurückkommende Daten
zu interpretieren.
01 #!/usr/local/bin/perl -w
02 use strict;
03 use XML::Simple qw( XMLin );
04 use Algorithm::Cluster qw/kcluster/;
05
06 my $file = "microformat.xml";
07
08 my $data = XMLin( $file );
09
10 binmode STDOUT, ":utf8";
11
12 my $placemarks =
13 $data->{ Folder }->{ Placemark };
14
15 my $coords = [];
16 my $mask = [];
17 my $weights = [ 1, 1 ];
18 my @names = ();
19
20 for my $name ( keys %$placemarks ) {
21
22 my $latlong = $placemarks->{ $name }->
23 { Point }->{ coordinates };
24
25 my( $lon, $lat ) = split ',', $latlong;
26
27 push @$coords, [ $lon, $lat ];
28 push @names, $name;
29 push @$mask, [ 1, 1 ];
30 }
31
32 my %params = (
33 nclusters => 12,
34 transpose => 0,
35 npass => 100,
36 method => 'a',
37 dist => 'e',
38 data => $coords,
39 mask => $mask,
40 weight => $weights,
41 );
42
43 my ($clusters, $error, $found) =
44 kcluster( %params );
45
46 my @by_cluster = ();
47
48 for( my $i = 0; $i < scalar @$clusters;
49 $i++ ) {
50
51 my $id = $clusters->[ $i ];
52 push @{ $by_cluster[ $id ] },
53 [ $names[ $i ],
54 @{ $coords->[ $i ] } ];
55 }
56
57 for my $cluster ( @by_cluster ) {
58 print "Cluster: \n";
59 for my $park ( @$cluster ) {
60 print " @$park\n";
61 }
62 }
Listing 1 zieht in den Zeilen 3 und 4 die beiden CPAN-Module XML::Simple
und Algorithm::Cluster herein, beide lassen sich mit einer CPAN-Shell
problemlos installieren. Die XML-Datei liegt als microformat.xml
vor und wird in Zeile 8 durch die aus XML::Simple exportierte Funktion
XMLin eingelesen. Ausgaben auf ein auf UTF-8 eingestelltes Terminal
erfordern die binmode-Anweisung aus Zeile 10, sonst meckert das
Skript beim HaleakalÄ-Nationalpark auf Hawaii mit seinem a mit Überstrich.
Die aus Algorithm::Cluster exportierte Funktion kcluster() führt die
k-means-Berechnung auf Punkten mit Koordinaten durch, die über den
Parameter data als Referenz auf einen Array mit Referenzen
auf Punkte-Arrays hereingereicht werden. Die Funktion gibt eine
Referenz auf einen Array zurück, der für jeden Punkt die zughörige
Cluster-ID angibt. Dabei kommt das Ergebnis in der gleichen Reihenfolge
zurück, wie die Punkte vorher hereingereicht wurden, enthielt data
also vorher 10 Punkte, ist das Ergebnis eine Referenz auf einen Array
mit 10 Elementen, die aus Integerwerten von 0 bis N-1 bestehen, wobei
N die Anzahl der vorher mit nclusters festgelegte Anzahl der
gewünschten Cluster ist. Damit das Skript später auch weiß, welches
Element im Ergebnis-Array zu welchem Nationalpark gehört, schiebt
Zeile 28 die Namen der Parks in der gleichen Reihenfolge auf einen
weiteren Array @names. Kommt das Ergebnis zurück, muss die for-Schleife
ab Zeile 48 nur noch über alle Index-Werte des Arrays, anfangend bei 0
bis N-1, laufen, und kann dann den zugehörigen Namen aus @names mit
dem gleichen Index abrufen.
Das Ergebnis-Array @by_cluster listet dann den für jeden Cluster
die zugehörigen Parks mit deren Namen und Geokoordinaten auf.
Der Wert für npass ist in Zeile 35 auf 100 gesetzt, also lässt
kcluster() das Verfahren 100 mal laufen und erhält so hoffentlich ein
stabiles Ergebnis. Die Funktion erwartet als Eingabe auch noch eine
Referenz auf einen Array mask, der wie die Punkte-Koordinaten
ebenfalls in Zweierreihen vorliegt und mit 1 angibt, dass der Wert
an dieser Stelle tatsächlich existiert. Wäre ein Wert auf 0 gesetzt,
gäbe dies ein Loch im Daten-Array an, über das der Algorithmus hinwegginge.
Der Parameter method gibt mit "a" vor, dass zur Zentroid-Bestimmung
das arithmetische Mittel der Koordinaten gewählt wird. Mit "m" könnte
man statt dessen den Median wählen. Die Gewichte der einzelnen Punkte
zur Abstandsbestimmung setzt der Parameter weights mit [1,1] auf
gleiche Werte.
Wie berechnet das Skript nun die Abstände zwischen den einzelnen
Punkten im zweidimensionalen Raum? Hier schummelt der Algorithmus etwas,
denn er interpretiert die aus der Wikipedia-Information stammenden
geografischen Längen- und Breitengrade einfach als X/Y-Koordinaten
in einem orthogonalen System. Der Parameter dist legt mit "e"
die euklidische Distanz fest, die Funktion
rechnet also einfach den Abstand zweier
Punkte in einem zweidimensionalen Koordinatensystem aus.
Das ist für die Clusterbestimmung gut genug, obwohl die geographische
Breite und Länge natürlich keine X/Y-Koordinaten sind.
Wer's ganz genau ausrechnen möchte,
kann mit dem CPAN-Modul Geo::Distance die genaue Distanz zweier
als Länge bzw. Breite vorliegenden Koordinatenpunkte auf der Erdoberfläche
ausrechnen und statt der Funktion kcluster() die ebenfalls
von Algorithm::Cluster bereitgestellte Funktion kmedoids() verwenden.
Letztere erwartet allerdings laut Anleitung eine Abstandsmatrix aller
Punkte untereinander und arbeitet nicht mit künstlichen Zentroiden-Punkten,
sondern wählt einen einzelnen Nationalpark in einem Cluster als
ungefähren Mittelpunkt des Clusters.
Daten in Clustern zusammenzufassen ist nicht nur eine Spielerei für geographische Daten, sondern findet in allerlei Systemen mit künstlicher Intelligenz Anwendung. Der Internethändler Amazon weiß zum Beispiel, welche weiteren Produkte ein Kunde vielleicht gerne kaufen würde, weil er Kunden mit ähnlichem Kaufverhalten in Clustern zusammenfasst. Statt mit Mengen von Punkten arbeitet ein solches System dann mit vieldimensionalen Vektoren (jedes Produkt belegt ein Element), die nur sehr spärlich gefüllt sind, da jeder Kunde nur eine kleine Auswahl aus der Gesamtpalette kauft. Ausgefuchste Verfahren können mit diesen großen Datenmengen effektiv jonglieren und erstaunlich präzise Vorhersagen treffen.
Listings zu diesem Artikel: ftp://www.linux-magazin.de/pub/listings/magazin/2012/11/Perl
"Ausgezeichnet zu Fuß", Michael Schilli, Linux-Magazin 10/2012, http://www.linux-magazin.de/Heft-Abo/Ausgaben/2012/10/Perl-Snapshot
"Data Analysis With Open Source Tools", Philipp K. Janert, O'Reilly 2012
"Clustering Library", http://bonsai.hgc.jp/~mdehoon/software/cluster/software.htm
"k-means clustering", Wikipedia, http://en.wikipedia.org/wiki/K-means_clustering
 |
Michael Schilliarbeitet als Software-Engineer bei Yahoo in Sunnyvale, Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen der Skriptsprache Perl. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen. |