Richtig schlau (Linux-Magazin, November 2012)

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.

Unschlagbares Gehirn

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.

Der Algorithmus bei dem jeder mit muss

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.

Cluster und Zentroide

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.

Bibliothek mit Perl-Wrapper

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.

Listing 1: k-means-cluster

    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.

Hanebüchene Datenstrukturen

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.

Gut genug

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.

Kaufverhalten vorhersagen

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.

Infos

[1]

Listings zu diesem Artikel: ftp://www.linux-magazin.de/pub/listings/magazin/2012/11/Perl

[2]

"Ausgezeichnet zu Fuß", Michael Schilli, Linux-Magazin 10/2012, http://www.linux-magazin.de/Heft-Abo/Ausgaben/2012/10/Perl-Snapshot

[3]

"Data Analysis With Open Source Tools", Philipp K. Janert, O'Reilly 2012

[4]

"Clustering Library", http://bonsai.hgc.jp/~mdehoon/software/cluster/software.htm

[5]

"k-means clustering", Wikipedia, http://en.wikipedia.org/wiki/K-means_clustering

Michael Schilli

arbeitet 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.