Open Source im professionellen Einsatz
Linux-Magazin 11/2012
© Dmitriy Shironosov, 123RF.com

© Dmitriy Shironosov, 123RF.com

Mit KI-Methoden Cluster berechnen

Sehen lernen

Ein menschlicher Beobachter sieht vieles intuitiv, erfasst zum Beispiel auf einer Karte die Ballungszentren einer zweidimensionalen Punktemenge auf einen Blick. Künstliche Intelligenz tut sich dabei normalerweise schwerer. Das relativ simple K-means-Verfahren jedoch liefert überraschend brauchbare Ergebnisse.

894

Der Naturfreund, der sich mit Hilfe des vorigen Perl-Snapshots eine Landkarte mit den amerikanischen Nationalparks generieren ließ [2], mag sich in einem zweiten Schritt fragen, wie er die verschiedenen Attraktionen möglichst Ressourcen-schonend abklappert. Abbildung 1 offenbart, dass sich die Parks in einigen Gegenden häufen. Ein Tourist erfährt und erwandert sich so vielleicht ein Dutzend Naturschauspiele auf einmal, mit nur einer Flugreise in die USA.

Abbildung 1: Amerikanische Nationalparks häufen sich in bestimmten Gegenden. Mit welcher Route klappern Reisende die meisten ab?

Unschlagbares Gehirn

Das menschliche Gehirn erfasst die sich ballenden Reißnägel auf der Landkarte ohne Anstrengung. In Sekundenbruchteilen steht fest, dass sich die meisten Nationalparks im Westen der kontinentalen Vereinigten Staaten häufen. Ein Computer hat nicht solch einen Überblick. Die Häufungen, so genannte Cluster, errechnet er sich mühevoll. Das Buch "Data Analysis With Open Source Tools" [3] erläutert die Implementierung einer Reihe von mehr oder weniger Erfolg versprechenden Verfahren. Allerdings sind auch sie allesamt dem menschlichen Gehirn unterlegen.

Wer dennoch nach automatischen Lösungen sucht, kommt nicht umhin einen halbwegs funktionierenden Algorithmus zu programmieren. Die Clustering Library [4] implementiert die gängigsten. 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. Dafür geht die unter [4] genannte PDF-Datei zur Clustering Library ab Seite 47 ausführlich auf die Benutzung des Algorithm::Cluster und der darin verwendeten Algorithmen ein.

Ausgangspunkt für die Berechnungen ist die XML-Datei mit den Geodaten amerikanischer Nationalparks aus dem vorigen Snapshot [2]. Die Datei entstand auf zwei Arten: Einmal mit Hilfe des Webservice auf http://microform.at und einmal mit dem handgeschriebenen Skript »Scraper« . In beiden Fällen fußt das Ergebnis auf frei erhältlichen Wikipedia-Daten. Abbildung 2 zeigt die aus dem Mikroformat extrahierten Daten der Wiki-Seite.

Abbildung 2: Die von Microform.at generierte XML-Datei enthält die Daten der Mikroformate aus der Wiki-Seite zu den amerikanischen Nationalparks.

Ziel des heutigen Snapshots ist es, diese XML-Daten einzulesen, damit sie ein Clusteralgorithmus in eine gruppierte Ausgabe mit geografisch zusammenliegenden Nationalparks umwandelt.

Cluster und Zentroide

Das gängigste Verfahren zum Finden von dichten Stellen in Punkthaufen nennt sich K-means. Es setzt voraus, dass man 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 abzüglich der drei verstreuten Inselgruppen sowie Alaskas, bleiben acht Zonen auf dem US-Festland übrig. Das sollte eine brauchbare Gruppierung ermöglichen, ohne dass die Parks eines Clusters zu weit auseinander liegen.

Der K-means-Algorithmus setzt zunächst willkürlich für jeden gesuchten Cluster so genannte Zentroide fest. Diese Punkte liegen am Anfang noch zufällig im Raum. Später avancieren sie zu Mittelpunkten der Cluster. Es zahlt sich aus, sie mit Bedacht zu platzieren, denn das Verfahren ist nicht stabil: Unterschiedliche Anfangsbedingungen führen zu verschiedenen Resultaten, manche Startpunkte verursachen gar einen Kollaps. Für den Anfang reicht dennoch eine zufällige Verteilung (Abbildung 3).

Abbildung 3: Am Anfang gibt es nur Punkte und die blau dargestellten Zentroiden. Der K-Means-Algorithmus startet mit n zufälligen Zentroiden …

Im Anschluss berechnet ein Programm für jeden der n Nationalparks die Distanz zu jedem der k Zentroide. Es ordnet jeden Park dem am nächsten gelegenen Zentroiden zu, baut also einen Cluster aus diesen Parks (Abbildung 4). Aus den geografischen Daten der Parks eines Clusters lässt sich nun deren Gravitationsmittelpunkt berechnen. Der Algorithmus verschiebt den Zentroiden in diesen Mittelpunkt (Abbildung 5).

Abbildung 4: … und weist die Punkte dem jeweils nächstgelegenen Zentroiden zu. So entstehen Cluster mit je einem eigenen Zentroiden.

Abbildung 5: Das Skript berechnet aus den geografischen Daten den Gravitationsmittelpunkt der Cluster und schiebt die Zentroiden dorthin.

Dieses Verfahren wiederholt der Algorithmus so lange, bis ein stabiler Zustand erreicht ist. Es kommt vor, dass er vorläufig gebildete Cluster nach einigen Durchgängen wieder auflöst, oder umgekehrt, dass er getrennte Cluster zu einem einzigen verschmilzt. Abbildung 6 zeigt die Gruppierung der Nationalparks als Ausgabe des Skripts in Listing 1.

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 }

Abbildung 6: Der K-means-Cluster-Algorithmus gruppiert die Parks nach Gegenden.

Wenig überraschend enthält der erste Cluster die beiden auf den hawaiianischen Inseln Big Island und Kauai liegenden Vulkan-Parks. Im nächsten Cluster liegen drei Parks im Bundesstaat Washington. Der dritte Cluster listet die acht Parks im kalten Alaska, der vierte die Insel Samoa und der fünfte schließlich drei in Nordkalifornien.

Diesen Artikel als PDF kaufen

Express-Kauf als PDF

Umfang: 3 Heftseiten

Preis € 0,99
(inkl. 19% MwSt.)

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Perl-Snapshot

    Mikroformate zeichnen HTML-Seiten mit allgemein anerkannten Tags aus, zum Beispiel Verbindungen zu sozialen Netzwerken oder Geokoordinaten. Das erlaubt automatischen Auswertern, sie zu sammeln und grafisch aufzubereiten. Nützlich ist das zum Beispiel bei Geodaten zur Routenplanung.

  • Lastverteiler

    Eine clevere IPtables-Funktion und Linux-HA verwandeln gewöhnliche Server in einen starken Cluster. Dessen Knoten teilen die Last untereinander und springen im Fehlerfall gegenseitig ein - ganz ohne zentrale Steuerung. Hardwarefehler oder Wartungsfenster verlieren ihren Schrecken.

  • Murchison Widefield Array: Australisches Teleskop bekommt Linux-Cluster

    Das Murchison Widefield Array Teleskop im westlichen Australien wird in Zukunft auf Linux setzen, um die täglich anfallenden 50 TByte Daten zu analysieren. Helfen soll dabei ein Cluster von IBM.

  • Balance-Akt

    Turbolinux Cluster Server ist eine Softwarelösung fürs Load Balancing, also zum transparenten Verteilen gleichartiger Dienste wie Webserver, Proxy- oder Mailserver an unterschiedliche Rechner in einem IP-Netz. Wir stellen das Produkt kurz vor.

  • Gemeinsam stark

    Wichtige Applikationen müssen trotz hängender Hardware und abstürzender Software verfügbar bleiben. Mit redundanten Servern gelingt dies: IPtables lässt sie im Cluster antreten und verteilt die Arbeit. Beim Ausfall eines Knotens schultert ein anderer dessen Last.

comments powered by Disqus

Stellenmarkt

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.