Posts

Erstellen und benutzen einer Geodatenbank

In diesem Artikel soll es im Gegensatz zum vorherigen Artikel Alles über Geodaten weniger darum gehen, was man denn alles mit Geodaten machen kann, dafür aber mehr darum wie man dies anstellt. Es wird gezeigt, wie man aus dem öffentlich verfügbaren Datensatz des OpenStreetMap-Projekts eine Geodatenbank erstellt und einige Beispiele dafür gegeben, wie man diese abfragen und benutzen kann.

Wahl der Datenbank

Prinzipiell gibt es zwei große “geo-kompatible” OpenSource-Datenbanken bzw. “Datenbank-AddOn’s”: Spatialite, welches auf SQLite aufbaut, und PostGIS, das PostgreSQL verwendet.

PostGIS bietet zum Teil eine einfachere Syntax, welche manchmal weniger Tipparbeit verursacht. So kann man zum Beispiel um die Entfernung zwischen zwei Orten zu ermitteln einfach schreiben:

während dies in Spatialite “nur” mit einer normalen Funktion möglich ist:

Trotztdem wird in diesem Artikel Spatialite (also SQLite) verwendet, da dessen Einrichtung deutlich einfacher ist (schließlich sollen interessierte sich alle Ergebnisse des Artikels problemlos nachbauen können, ohne hierfür einen eigenen Datenbankserver aufsetzen zu müssen).

Der Hauptunterschied zwischen PostgreSQL und SQLite (eigentlich der Unterschied zwischen SQLite und den meissten anderen Datenbanken) ist, dass für PostgreSQL im Hintergrund ein Server laufen muss, an welchen die entsprechenden Queries gesendet werden, während SQLite ein “normales” Programm (also kein Client-Server-System) ist welches die Queries selber auswertet.

Hierdurch fällt beim Aufsetzen der Datenbank eine ganze Menge an Konfigurationsarbeit weg: Welche Benutzer gibt es bzw. akzeptiert der Server? Welcher Benutzer bekommt welche Rechte? Über welche Verbindung wird auf den Server zugegriffen? Wie wird die Sicherheit dieser Verbindung sichergestellt? …

Während all dies bei SQLite (und damit auch Spatialite) wegfällt und die Einrichtung der Datenbank eigentlich nur “installieren und fertig” ist, muss auf der anderen Seite aber auch gesagt werden dass SQLite nicht gut für Szenarien geeignet ist, in welchen viele Benutzer gleichzeitig (insbesondere schreibenden) Zugriff auf die Datenbank benötigen.

Benötigte Software und ein Beispieldatensatz

Was wird für diesen Artikel an Software benötigt?

SQLite3 als Datenbank

libspatialite als “Geoplugin” für SQLite

spatialite-tools zum erstellen der Datenbank aus dem OpenStreetMaps (*.osm.pbf) Format

python3, die beiden GeoModule spatialite, folium und cartopy, sowie die Module pandas und matplotlib (letztere gehören im Bereich der Datenauswertung mit Python sowieso zum Standart). Für pandas gibt es noch die Erweiterung geopandas sowie eine praktisch unüberschaubare Anzahl weiterer geographischer Module aber bereits mit den genannten lassen sich eine Menge interessanter Dinge herausfinden.

– und natürlich einen Geodatensatz: Zum Beispiel sind aus dem OpenStreetMap-Projekt extrahierte Datensätze hier zu finden.

Es ist ratsam, sich hier erst einmal einen kleinen Datensatz herunterzuladen (wie zum Beispiel einen der Stadtstaaten Bremen, Hamburg oder Berlin). Zum einen dauert die Konvertierung des .osm.pbf-Formats in eine Spatialite-Datenbank bei größeren Datensätzen unter Umständen sehr lange, zum anderen ist die fertige Datenbank um ein vielfaches größer als die stark gepackte Originaldatei (für “nur” Deutschland ist die fertige Datenbank bereits ca. 30 GB groß und man lässt die Konvertierung (zumindest am eigenen Laptop) am besten über Nacht laufen – willkommen im Bereich “BigData”).

Erstellen eine Geodatenbank aus OpenStreetMap-Daten

Nach dem Herunterladen eines Datensatzes der Wahl im *.osm.pbf-Format kann hieraus recht einfach mit folgendem Befehl aus dem Paket spatialite-tools die Datenbank erstellt werden:

Erkunden der erstellten Geodatenbank

Nach Ausführen des obigen Befehls sollte nun eine Datei mit dem gewählten Namen (im Beispiel bremen-latest.sqlite) im aktuellen Ordner vorhanden sein – dies ist bereits die fertige Datenbank. Zunächst sollte man mit dieser Datenbank erst einmal dasselbe machen, wie mit jeder anderen Datenbank auch: Sich erst einmal eine Weile hinsetzen und schauen was alles an Daten in der Datenbank vorhanden und vor allem wo diese Daten in der erstellten Tabellenstruktur zu finden sind. Auch wenn dieses Umschauen prinzipiell auch vollständig über die Shell oder in Python möglich ist, sind hier Programme mit graphischer Benutzeroberfläche (z. B. spatialite-gui oder QGIS) sehr hilfreich und sparen nicht nur eine Menge Zeit sondern vor allem auch Tipparbeit. Wer dies tut, wird feststellen, dass sich in der generierten Datenbank einige dutzend Tabellen mit Namen wie pt_addresses, ln_highway und pg_boundary befinden.

Die Benennung der Tabellen folgt dem Prinzip, dass pt_*-Tabellen Punkte im Geokoordinatensystem wie z. B. Adressen, Shops, Bäckereien und ähnliches enthalten. ln_*-Tabellen enthalten hingegen geographische Entitäten, welche sich als Linien darstellen lassen, wie beispielsweise Straßen, Hochspannungsleitungen, Schienen, ect. Zuletzt gibt es die pg_*-Tabellen welche Polygone – also Flächen einer bestimmten Form enthalten. Dazu zählen Landesgrenzen, Bundesländer, Inseln, Postleitzahlengebiete, Landnutzung, aber auch Gebäude, da auch diese jeweils eine Grundfläche besitzen. In dem genannten Datensatz sind die Grundflächen von Gebäuden – zumindest in Europa – nahezu vollständig. Aber auch der Rest der Welt ist für ein “Wikipedia der Kartographie” insbesondere in halbwegs besiedelten Gebieten bemerkenswert gut erfasst, auch wenn nicht unbedingt davon ausgegangen werden kann, dass abgelegenere Gegenden (z. B. irgendwo auf dem Land in Südamerika) jedes Gebäude eingezeichnet ist.

Verwenden der Erstellten Datenbank

Auf diese Datenbank kann nun entweder direkt aus der Shell über den Befehl

zugegriffen werden oder man nutzt das gleichnamige Python-Paket:

Nach Eingabe der obigen Befehle in eine Python-Konsole, ein Jupyter-Notebook oder ein anderes Programm, welches die Anbindung an den Python-Interpreter ermöglicht, können die von der Datenbank ausgegebenen Ergebnisse nun direkt in ein Pandas Data Frame hineingeladen und verwendet/ausgewertet/analysiert werden.

Im Grunde wird hierfür “normales SQL” verwendet, wie in anderen Datenbanken auch. Der folgende Beispiel gibt einfach die fünf ersten von der Datenbank gefundenen Adressen aus der Tabelle pt_addresses aus:

Link zur Ausgabe

Es wird dem Leser sicherlich aufgefallen sein, dass die Spalte “Geometry” (zumindest für das menschliche Auge) nicht besonders ansprechend sowie auch nicht informativ aussieht: Der Grund hierfür ist, dass diese Spalte die entsprechende Position im geographischen Koordinatensystem aus Gründen wie dem deutlich kleineren Speicherplatzbedarf sowie der damit einhergehenden Optimierung der Geschwindigkeit der Datenbank selber, in binärer Form gespeichert und ohne weitere Verarbeitung auch als solche ausgegeben wird.

Glücklicherweise stellt spatialite eine ganze Reihe von Funktionen zur Verarbeitung dieser geographischen Informationen bereit, von denen im folgenden einige beispielsweise vorgestellt werden:

Für einzelne Punkte im Koordinatensystem gibt es beispielsweise die Funktionen X(geometry) und Y(geometry), welche aus diesem “binären Wirrwarr” den Längen- bzw. Breitengrad des jeweiligen Punktes als lesbare Zahlen ausgibt.

Ändert man also das obige Query nun entsprechend ab, erhält man als Ausgabe folgendes Ergebnis in welchem die Geometry-Spalte der ausgegebenen Adressen in den zwei neuen Spalten Longitude und Latitude in lesbarer Form zu finden ist:

Link zur Tabelle

Eine weitere häufig verwendete Funktion von Spatialite ist die Distance-Funktion, welche die Distanz zwischen zwei Orten berechnet.

Das folgende Beispiel sucht in der Datenbank die 10 nächstgelegenen Bäckereien zu einer frei wählbaren Position aus der Datenbank und listet diese nach zunehmender Entfernung auf (Achtung – die frei wählbare Position im Beispiel liegt in München, wer die selbe Position z. B. mit dem Bremen-Datensatz verwendet, wird vermutlich etwas weiter laufen müssen…):

Link zur Ausgabe

Ein Anwendungsfall für eine solche Liste können zum Beispiel Programme/Apps wie maps.me oder Google-Maps sein, in denen User nach Bäckereien, Geldautomaten, Supermärkten oder Apotheken “in der Nähe” suchen können sollen.

Diese Liste enthält nun alle Informationen die grundsätzlich gebraucht werden, ist soweit auch informativ und wird in den meißten Fällen der Datenauswertung auch genau so gebraucht, jedoch ist diese für das Auge nicht besonders ansprechend.

Viel besser wäre es doch, die gefundenen Positionen auf einer interaktiven Karte einzuzeichnen:

Was kann man sonst interessantes mit der erstellten Datenbank und etwas Python machen? Wer in Deutschland ein wenig herumgekommen ist, dem ist eventuell aufgefallen, dass sich die Endungen von Ortsnamen stark unterscheiden: Um München gibt es Stadteile und Dörfer namens Garching, Freising, Aubing, ect., rund um Stuttgart enden alle möglichen Namen auf “ingen” (Plieningen, Vaihningen, Echterdingen …) und in Berlin gibt es Orte wie Pankow, Virchow sowie eine bunte Auswahl weiterer *ow’s.

Das folgende Query spuckt gibt alle “village’s”, “town’s” und “city’s” aus der Tabelle pt_place, also Dörfer und Städte, aus:

Link zur Ausgabe

Graphisch mit matplotlib und cartopy in ein Koordinatensystem eingetragen sieht diese Verteilung folgendermassen aus:

Die Grafik zeigt, dass stark unterschiedliche Vorkommen der verschiedenen Ortsendungen in Deutschland (Clustering). Über das genaue Zustandekommen dieser Verteilung kann ich hier nur spekulieren, jedoch wird diese vermutlich ähnlichen Prozessen unterliegen wie beispielsweise die Entwicklung von Dialekten.

Wer sich die Karte etwas genauer anschaut wird merken, dass die eingezeichneten Landesgrenzen und Küstenlinien nicht besonders genau sind. Hieran wird ein interessanter Effekt von häufig verwendeten geographischen Entitäten, nämlich Linien und Polygonen deutlich. Im Beispiel werden durch die beiden Zeilen

die bereits im Modul cartopy hinterlegten Daten verwendet. Genaue Verläufe von Küstenlinien und Landesgrenzen benötigen mit wachsender Genauigkeit hingegen sehr viel Speicherplatz, da mehr und mehr zu speichernde Punkte benötigt werden (genaueres siehe hier).

Schlussfolgerung

Man kann also bereits mit einigen Grundmodulen und öffentlich verfügbaren Datensätzen eine ganze Menge im Bereich der Geodaten erkunden und entdecken. Gleichzeitig steht, insbesondere für spezielle Probleme, eine große Bandbreite weiterer Software zur Verfügung, für welche dieser Artikel zwar einen Grundsätzlichen Einstieg geben kann, die jedoch den Rahmen dieses Artikels sprengen würden.

Einstieg in Natural Language Processing – Teil 2: Preprocessing von Rohtext mit Python

Dies ist der zweite Artikel der Artikelserie Einstieg in Natural Language Processing.

In diesem Artikel wird das so genannte Preprocessing von Texten behandelt, also Schritte die im Bereich des NLP in der Regel vor eigentlichen Textanalyse durchgeführt werden.

Tokenizing

Um eingelesenen Rohtext in ein Format zu überführen, welches in der späteren Analyse einfacher ausgewertet werden kann, sind eine ganze Reihe von Schritten notwendig. Ganz allgemein besteht der erste Schritt darin, den auszuwertenden Text in einzelne kurze Abschnitte – so genannte Tokens – zu zerlegen (außer man bastelt sich völlig eigene Analyseansätze, wie zum Beispiel eine Spracherkennung anhand von Buchstabenhäufigkeiten ect.).

Was genau ein Token ist, hängt vom verwendeten Tokenizer ab. So bringt NLTK bereits standardmäßig unter anderem BlankLine-, Line-, Sentence-, Word-, Wordpunkt- und SpaceTokenizer mit, welche Text entsprechend in Paragraphen, Zeilen, Sätze, Worte usw. aufsplitten. Weiterhin ist mit dem RegexTokenizer ein Tool vorhanden, mit welchem durch Wahl eines entsprechenden Regulären Ausdrucks beliebig komplexe eigene Tokenizer erstellt werden können.

Üblicherweise wird ein Text (evtl. nach vorherigem Aufsplitten in Paragraphen oder Sätze) schließlich in einzelne Worte und Interpunktionen (Satzzeichen) aufgeteilt. Hierfür kann, wie im folgenden Beispiel z. B. der WordTokenizer oder die diesem entsprechende Funktion word_tokenize() verwendet werden.

rawtext = 'This is a short example text that needs to be cleaned.'

tokens = nltk.word_tokenize(rawtext)

tokens
['This', 'is', 'a', 'short', 'example', 'text', 'that', 'needs', 'to',  'be',  'cleaned',  '.']

Stemming & Lemmatizing

Andere häufig durchgeführte Schritte sind Stemming sowie Lemmatizing. Hierbei werden die Suffixe der einzelnen Tokens des Textes mit Hilfe eines Stemmers in eine Form überführt, welche nur den Wortstamm zurücklässt. Dies hat den Zweck verschiedene grammatikalische Formen des selben Wortes (welche sich oft in ihrer Endung unterscheiden (ich gehe, du gehst, er geht, wir gehen, …) ununterscheidbar zu machen. Diese würden sonst als mehrere unabhängige Worte in die darauf folgende Analyse eingehen.

Neben bereits fertigen Stemmern bietet NLTK auch für diesen Schritt die Möglichkeit sich eigene Stemmer zu programmieren. Da verschiedene Stemmer Suffixe nach unterschiedlichen Regeln entfernen, sind nur die Wortstämme miteinander vergleichbar, welche mit dem selben Stemmer generiert wurden!

Im forlgenden Beispiel werden verschiedene vordefinierte Stemmer aus dem Paket NLTK auf den bereits oben verwendeten Beispielsatz angewendet und die Ergebnisse der gestemmten Tokens in einer Art einfachen Tabelle ausgegeben:

# Ready-to-use stemmers in nltk
porter = nltk.PorterStemmer()
lancaster = nltk.LancasterStemmer()
snowball = nltk.SnowballStemmer(language='english')

# Printing a table to compare the different stemmers
header = 'Token\tPorter\tLancas.\tSnowball'
print(header + '\n' + len(header) * '-')
for token in tokens:
    print('\t'.join([token, porter.stem(token), lancaster.stem(token), snowball.stem(token)]))


Token	Porter	Lancas.	Snowball
-----------------------------
This	thi 	thi 	this
is  	is  	is  	is
a    	a    	a    	a
short	short	short	short
example	exampl	exampl	exampl
text	text	text	text
that	that	that	that
needs	need	nee	need
to  	to  	to  	to
be  	be  	be  	be
cleaned	clean	cle 	clean
.   	.   	.   	.

Sehr ähnlich den Stemmern arbeiten Lemmatizer: Auch ihre Aufgabe ist es aus verschiedenen Formen eines Wortes die jeweilige Grundform zu bilden. Im Unterschied zu den Stemmern ist das Lemma eines Wortes jedoch klar als dessen Grundform definiert.

from nltk.stem import WordNetLemmatizer

lemmatizer = WordNetLemmatizer()

lemmas = [lemmatizer.lemmatize(t) for t in tokens()]

Vokabular

Auch das Vokabular, also die Menge aller verschiedenen Worte eines Textes, ist eine informative Kennzahl. Bezieht man die Größe des Vokabulars eines Textes auf seine gesamte Anzahl verwendeter Worte, so lassen sich hiermit Aussagen zu der Diversität des Textes machen.

Außerdem kann das auftreten bestimmter Worte später bei der automatischen Einordnung in Kategorien wichtig werden: Will man beispielsweise Nachrichtenmeldungen nach Themen kategorisieren und in einem Text tritt das Wort „DAX“ auf, so ist es deutlich wahrscheinlicher, dass es sich bei diesem Text um eine Meldung aus dem Finanzbereich handelt, als z. B. um das „Kochrezept des Tages“.

Dies mag auf den ersten Blick trivial erscheinen, allerdings können auch mit einfachen Modellen, wie dem so genannten „Bag-of-Words-Modell“, welches nur die Anzahl des Auftretens von Worten prüft, bereits eine Vielzahl von Informationen aus Texten gewonnen werden.

Das reine Vokabular eines Textes, welcher in der Variable “rawtext” gespeichert ist, kann wie folgt in der Variable “vocab” gespeichert werden. Auf die Ausgabe wurde in diesem Fall verzichtet, da diese im Falle des oben als Beispiel gewählten Satzes den einzelnen Tokens entspricht, da kein Wort öfter als ein Mal vorkommt.

from nltk import wordpunct_tokenizer
from nltk.stem import WordNetLemmatizer

lemma = WordNetLemmatizer()

vocab = set([WordNetLemmatizer().lemmatize(t) for t in wordpunct_tokenize(text.lower())])

Stopwords

Unter Stopwords werden Worte verstanden, welche zwar sehr häufig vorkommen, jedoch nur wenig Information zu einem Text beitragen. Beispiele in der beutschen Sprache sind: der, und, aber, mit, …

Sowohl NLTK als auch cpaCy bringen vorgefertigte Stopwordsets mit. 

from nltk.corpus import stopwords
stoplist = stopwords.words('english')
stopset = set(stopwords.words('english'))

[t for t in tokens if not t in stoplist]
['This', 'short', 'example', 'text', 'needs', 'cleaned', '.']

Vorsicht: NLTK besitzt eine Stopwordliste, welche erst in ein Set umgewandelt werden sollte um die lookup-Zeiten kurz zu halten – schließlich muss jedes einzelne Token des Textes auf das vorhanden sein in der Stopworditerable getestet werden!

%timeit [w for w in tokens if not w in stopset] # 1.11 ms
%timeit [w for w in tokens if not w in stoplist] # 26.6 ms

POS-Tagging

POS-Tagging steht für „Part of Speech Tagging“ und entspricht ungefähr den Aufgaben, die man noch aus dem Deutschunterricht kennt: „Unterstreiche alle Subjekte rot, alle Objekte blau…“. Wichtig ist diese Art von Tagging insbesondere, wenn man später tatsächlich strukturiert Informationen aus dem Text extrahieren möchte, da man hierfür wissen muss wer oder was als Subjekt mit wem oder was als Objekt interagiert.

Obwohl genau die selben Worte vorkommen, bedeutet der Satz „Die Katze frisst die Maus.“ etwas anderes als „Die Maus frisst die Katze.“, da hier Subjekt und Objekt aufgrund ihrer Reihenfolge vertauscht sind (Stichwort: Subjekt – Prädikat – Objekt ).

Weniger wichtig ist dieser Schritt bei der Kategorisierung von Dokumenten. Insbesondere bei dem bereits oben erwähnten Bag-of-Words-Modell, fließen POS-Tags überhaupt nicht mit ein.

Und weil es so schön einfach ist: Die obigen Schritte mit spaCy

Die obigen Methoden und Arbeitsschritte, welche Texte die in natürlicher Sprache geschrieben sind, allgemein computerzugänglicher und einfacher auswertbar machen, können beliebig genau den eigenen Wünschen angepasst, einzeln mit dem Paket NLTK durchgeführt werden. Dies zumindest einmal gemacht zu haben, erweitert das Verständnis für die funktionsweise einzelnen Schritte und insbesondere deren manchmal etwas versteckten Komplexität. (Wie muss beispielsweise ein Tokenizer funktionieren der den Satz “Schwierig ist z. B. dieser Satz.” korrekt in nur einen Satz aufspaltet, anstatt ihn an jedem Punkt welcher an einem Wortende auftritt in insgesamt vier Sätze aufzuspalten, von denen einer nur aus einem Leerzeichen besteht?) Hier soll nun aber, weil es so schön einfach ist, auch das analoge Vorgehen mit dem Paket spaCy beschrieben werden:

import spacy

nlp = spacy.load('en')
doc = nlp(rawtext)

Dieser kurze Codeabschnitt liest den an spaCy übergebenen Rohtext in ein spaCy Doc-Object ein und führt dabei automatisch bereits alle oben beschriebenen sowie noch eine Reihe weitere Operationen aus. So stehen neben dem immer noch vollständig gespeicherten Originaltext, die einzelnen Sätze, Worte, Lemmas, Noun-Chunks, Named Entities, Part-of-Speech-Tags, ect. direkt zur Verfügung und können.über die Methoden des Doc-Objektes erreicht werden. Des weiteren liegen auch verschiedene weitere Objekte wie beispielsweise Vektoren zur Bestimmung von Dokumentenähnlichkeiten bereits fertig vor.

Die Folgende Übersicht soll eine kurze (aber noch lange nicht vollständige) Übersicht über die automatisch von spaCy generierten Objekte und Methoden zur Textanalyse geben:

# Textabschnitte
doc.text                                 # Originaltext
sents = doc.sents                        # Sätze des Dokuments
tokens = [token for token in doc]        # Tokens/Worte des Dokuments
parags = doc.text_with_ws.split('\n\n')  # Absätze des Dokuments

# Eigenschaften einzelner Tokens
[t.lemma_ for t in doc]                  # Lemmata der einzelnen Tokens
[t.tag_ for t in doc]                    # POS-Tags der einzelnen Tokens

# Objekte zur Textanalyse
doc.vocab                                # Vokabular des Dokuments
doc.sentiment                            # Sentiment des Dokuments
doc.noun_chunks                          # NounChunks des Dokuments
entities = [ent for ent in doc.ents]     # Named Entities (Persons, Locations, Countrys)

# Objekte zur Dokumentenklassifikation
doc.vector                               # Vektor
doc.tensor                               # Tensor

Diese „Vollautomatisierung“ der Vorabschritte zur Textanalyse hat jedoch auch seinen Preis: spaCy geht nicht gerade sparsam mit Ressourcen wie Rechenleistung und Arbeitsspeicher um. Will man einen oder einige Texte untersuchen so ist spaCy oft die einfachste und schnellste Lösung für das Preprocessing. Anders sieht es aber beispielsweise aus, wenn eine bestimmte Analyse wie zum Beispiel die Einteilung in verschiedene Textkategorien auf eine sehr große Anzahl von Texten angewendet werden soll. In diesem Fall, sollte man in Erwägung ziehen auf ressourcenschonendere Alternativen wie zum Beispiel gensim auszuweichen.

Wer beim lesen genau aufgepasst hat, wird festgestellt haben, dass ich im Abschnitt POS-Tagging im Gegensatz zu den anderen Abschnitten auf ein kurzes Codebeispiel verzichtet habe. Dies möchte ich an dieser Stelle nachholen und dabei gleich eine Erweiterung des Pakets spaCy vorstellen: displaCy.

Displacy bietet die Möglichkeit, sich Zusammenhänge und Eigenschaften von Texten wie Named Entities oder eben POS-Tagging graphisch im Browser anzeigen zu lassen.

import spacy
from spacy import displacy

rawtext = 'This is a short example sentence that needs to be cleaned.'

nlp = spacy.load('en')
doc = nlp(rawtext)
displacy.serve(doc, style='dep')

Nach ausführen des obigen Codes erhält man eine Ausgabe die wie folgt aussieht:

Serving on port 5000...
Using the 'dep' visualizer

Nun öffnet man einen Browser und ruft die URL ‘http://127.0.0.1:5000’ auf (Achtung: localhost anstatt der IP funktioniert – warum auch immer – mit displacy nicht). Im Browser sollte nun eine Seite mit einem SVG-Bild geladen werden, welches wie folgt aussieht

Die Abbildung macht deutlich was POS-Tagging genau ist und warum es von Nutzen sein kann wenn man Informationen aus einem Text extrahieren will. Jedem Word (Token) ist eine Wortart zugeordnet und die Beziehung der einzelnen Worte durch Pfeile dargestellt. Dies ermöglicht es dem Computer zum Beispiel in dem Satzteil “der grüne Apfel”, das Adjektiv “grün” auf das Nomen “Apfel” zu beziehen und diesem somit als Eigenschaft zuzuordnen.

Nachdem dieser Artikel wichtige Schritte des Preprocessing von Texten beschrieben hat, geht es im nächsten Artikel darum was man an Texten eigentlich analysieren kann und welche Analysemöglichkeiten die verschiedenen für Python vorhandenen Module bieten.

Einstieg in Natural Language Processing – Teil 1: Natürliche vs. Formale Sprachen

Dies ist Artikel 1 von 4 der Artikelserie Einstieg in Natural Language Processing – Artikelserie.

Versuche und erste Ansätze, Maschinen beizubringen menschliche Sprache zu verstehen, gibt es bereits seit den 50er Jahren. Trotz der jahrzehntelangen Forschung und Entwicklung gelingt dies bis heute nicht umfassend. Woran liegt dies?

Um diese Frage zu beantworten, hilft es, sich die Unterschiede zwischen „natürlichen“, also sich selbstständig entwickelnden, typischerweise von Menschen gesprochenen Sprachen und den von Computern interpretieren formalen Sprachen klar zu machen. Formale Sprachen, wie zum Beispiel Python zum Ausführen der Codebeispiele in dieser Artikelserie, HTML (Hyper Text Markup Language) zur Darstellung von Webseiten und andere typische Programmier- und Skriptsprachen, sind üblicherweise sehr streng strukturiert.

Alle diese Sprachen weisen eine Reihe von Gemeinsamkeiten auf, welche es Computern einfach machen, sie korrekt zu interpretieren (also den Informationsinhalt zu “verstehen”). Das vermutlich auffälligste Merkmal formaler Sprachen ist eine relativ strikte Syntax, welche (wenn überhaupt) nur geringe Abweichungen von einem Standard erlaubt. Wie penibel die jeweilige Syntax oft einzuhalten ist, wird am ehesten deutlich, wenn diese verletzt wird:

>>> print('Correct Syntax')
Correct Syntax

>>> print{'Wrong Syntax'}
    print{'Wrong Syntax'}
         ^
SyntaxError: invalid syntax

Solche so genannten “Syntax Error”  gehören daher zu den häufigsten Fehlern beim Schreiben von Quellcode.

Ganz anders dagegen sieht es in der Kommunikation mit natürlichen Sprachen aus. Zwar fördert falsche Komma-Setzung in der Regel nicht die Leserlichkeit eines Textes, jedoch bleibt dieser in der Regel trotzdem verständlich. Auch macht es keinen Unterschied ob ich sage „Es ist heiß heute.“ oder „Heute ist es heiß.“. Genau wie in der deutschen Sprache funktioniert dieses Beispiel auch im Englischen sowie in anderen natürlichen Sprachen. Insbesondere Spanisch ist ein Beispiel für eine Sprache mit extrem variabler Satzstellung. Jedoch kann in anderen Fällen eine andere Reihenfolge der selben Worte deren Bedeutung auch verändern. So ist „Ist es heute heiß?“ ganz klar eine Frage, obwohl exakt die selben Worte wie in den Beispielsätzen oben vorkommen.

Ein weiterer wichtiger, hiermit verwandter Unterschied ist, dass es bei formalen Sprachen in der Regel einen Ausdruck gibt, welcher eine spezifische Bedeutung besitzt, während es in natürlichen Sprachen oft viele Synonyme gibt, die ein und dieselbe Sache (oder zumindest etwas sehr ähnliches) ausdrücken. Ein wahrer boolscher Wert wird in Python als

True

geschrieben. Es gibt keine andere Möglichkeit, diesen Wert auszudrücken (zumindest nicht ohne irgend eine Art von Operatoren wie das Doppelgleichheitszeichen zu benutzen und damit z. B. “0 == 0” zu schreiben).  Anders hingegen zum Beispiel in der Deutschen Sprache: Wahr, richtig, korrekt, stimmt, ja,

Um einen Vorstellung davon zu bekommen, wie verbreitet Synonyme in natürlichen Sprachen sind, lässt sich die Internetseite https://www.openthesaurus.de verwenden. Beispielshalber findet man dutzende Synonyme für das Wort „schnell“ hier: https://www.openthesaurus.de/synonyme/schnell

Eine weitere große Schwierigkeit, welche in den meisten natürlichen Sprachen und nahezu allen Arten von Texten zu finden ist, stellen verschiedene grammatikalische Formen eines Wortes dar. So sind die Worte bin, wäre, sind, waren, wirst, werden… alles Konjugationen desselben Verbs, nämlich sein. Eine durchaus beeindruckende Übersicht über die verwirrende Vielfalt von Konjugationen dieses kleinen Wörtchens, findet sich unter: https://www.verbformen.de/konjugation/sein.htm.

Dieses Problem wird um so schwerwiegender, da viele Verben, insbesondere die am häufigsten genutzten, sehr unregelmäßige Konjugationsformen besitzen und damit keiner generellen Regel folgen. Daher ist computerintern oft ein Mapping für jede mögliche Konjugationsform bei vielen Verben die einzige Möglichkeit, an die Grundform zu kommen (mehr dazu in Teil 3 dieser Artikelserie).

Die Liste der sprachlichen Schwierigkeiten beim computergestützten Auswerten natürlicher Sprache ließe sich an diesem Punkt noch beliebig weiter fortsetzen:

  • Rechtschreibfehler
  • falsche Grammatik
  • Smileys
  • der „Substantivverkettungswahn“ im Deutschen
  • mehrdeutige Worte und Abkürzungen
  • abwegige Redewendungen (z. B. “ins Gras beißen”)
  • Ironie
  • und, und, und …

Ob und welche Rolle jede dieser Schwierigkeiten im einzelnen spielt, hängt natürlich sehr stark von den jeweiligen Texten ab und kann nicht pauschalisiert werden – ein typischer Chatverlauf wird ganz andere Probleme bereithalten als ein Wikipedia-Artikel. Wie man einige dieser Probleme in der Praxis vereinfachen oder sogar lösen kann und welche Ansätze und Methoden zur Verfügung stehen und regelmäßig zur Anwendung kommen wird im nächsten Teil dieser Artikelserie an praktischen Codebeispielen genauer unter die Lupe genommen.

NLTK vs. Spacy – Eine kurze Übersicht

Möchte man einen (oder auch einige) Text(e) mit den Methoden des natural language processings untersuchen um die darin verwendete Sprache auswerten oder nach bestimmten Informationen suchen, so sind insbesondere die Pakete NLTK und spaCy zu empfehlen (bei sehr vielen Texten sieht das schon wieder anders aus und wird am Ende der Artikelserie mit dem Paket gensim vorgestellt); beide bieten eine unglaubliche Vielzahl von Analysemöglichkeiten, vorgefertigten Wortsets, vortrainierte Stemmer und Lemmatiser, POS Tagger und, und, und…

Ist man vor allem an den Ergebnissen der Analyse selbst interessiert, so bietet sich spaCy an, da hier bereits mit wenigen Zeilen Code viele interessante Informationen generiert werden können.

Wer dagegen gerne selber bastelt oder wissen möchte wie die einzelnen Tools und Teilschritte genau funktionieren oder sich seine eigenen Stemmer, Tagger ect. trainieren will, ist vermutlich mit NLTK besser beraten. Zwar ist hier oft mehr Quellcode für das gleiche Ergebnis notwendig, allerdings kann das Preprocessing der Texte hierbei relativ einfach exakt den eigenen Vorstellungen angepasst werden. Zudem bietet NLTK eine Vielzahl von Beispieltexten und bereits fertig getagte Daten, mit welchen eigene Tagger trainiert und getestet werden können.

Einstieg in Natural Language Processing – Artikelserie

Unter Natural Language Processing (NLP) versteht man ein Teilgebiet der Informatik bzw. der Datenwissenschaft, welches sich mit der Analyse und Auswertung , aber auch der Synthese natürlicher Sprache befasst. Mit natürlichen Sprachen werden Sprachen wie zum Beispiel Deutsch, Englisch oder Spanisch bezeichnet, welche nicht geplant entworfen wurden, sondern sich über lange Zeit allein durch ihre Benutzung entwickelt haben. Anders ausgedrückt geht es um die Schnittstelle zwischen unserer im Alltag verwendeten und für uns Menschen verständlichen Sprache auf der einen, und um deren computergestützte Auswertung auf der anderen Seite.

Diese Artikelserie soll eine Einführung in die Thematik des Natural Language Processing sein, dessen Methoden, Möglichkeiten, aber auch der Grenzen . Im einzelnen werden folgende Themen näher behandelt:

1. Artikel – Natürliche vs. Formale Sprachen
2. Artikel – Preprocessing von Rohtext mit Python (erscheint demnächst…)
3. Artikel – Möglichkeiten/Methoden der Textanalyse an Beispielen (erscheint demnächst…)
4. Artikel – NLP, was kann es? Und was nicht? (erscheint demnächst…)

Zur Verdeutlichung der beschriebenen Zusammenhänge und Methoden und um Interessierten einige Ideen für mögliche Startpunkte aufzuzeigen, werden im Verlauf der Artikelserie an verschiedenen Stellen Codebeispiele in der Programmiersprache Python vorgestellt.
Von den vielen im Internet zur Verfügung stehenden Python-Paketen zum Thema NLP, werden in diesem Artikel insbesondere die drei Pakete NLTK, Gensim und Spacy verwendet.

Analyse der Netzwerktopologie des Internets auf Basis des IPv4-Protokolls

Wie kommen Daten die man via Internet quer durch die Welt sendet eigentlich an ihr Ziel? Welchen Weg nehmen beispielsweise die Datenpakete, wenn ich von mir zu Hause eine Datei an meinen Nachbarn ein Haus weiter sende? Wie groß ist der “Umweg”, den die Daten nehmen? Und macht es eigentlich einen Unterschied, ob ich www.google.de, www.google.com oder www.google.nl aufrufe, oder gehen alle Suchanfragen sowieso an dasselbe Ziel?

Fragen wie diese lassen sich durch eine Kombination von Tools wie traceroute oder tracepath und geoiplookup beantworten und unter Verwendung des Python-Paketes geoplotlib sogar graphisch auf einer Weltkarte darstellen. Die so gewonnenen Ergebnisse zeigen Teile der Netzwerktopologie des Internets auf und führen zu interessanten, teils unerwarteten Erkenntnissen.

Ziel dieses Artikels soll sein, ein möglichst einfaches Tutorial zum selber mitbasteln bereit zu stellen. Die einzelnen Schritte die hierfür notwendig sind, werden möglichst einfach verständlich dargestellt und erklärt, trotzdem sind zum vollständigen Verständnis grundlegende Kenntnisse in Python sowie der Kommandozeile hilfreich. Er richtet sich aber auch an alle, die sich einfach einmal etwas in ihrer virtuellen Umgebung „umschauen“ möchten oder einfach nur an den Ergebnissen interessiert sind, ohne sich mit den Details und wie diese umgesetzt werden, auseinander setzen zu wollen.  Am Ende des Artikels werden die einzelnen Skripte des Projekts als zip-Datei bereitgestellt.

Hinweis: Diese Anleitung bezieht sich auf ein Linux-System und wurde unter Ubuntu getestet. Windows-User können beispielsweise mit dem Befehl tracert (als Ersatz für traceroute) ähnliche Ergebnisse erziehlen, jedoch muss dann das Parsing der IP-Adressen abgeändert werden.

1. Grundsätzliches Erkunden der Route, die ein Datenpaket nimmt

Hierfür wird ein Programm wie traceroute, tracepath oder nmap benötigt, welches durch Versenden von „abgelaufenen Datenpaketen“ die Hosts „auf dem Weg“ zum Ziel dazu bringt, ihre IPv4-Adresse zurück zu geben. In diesem Artikel wird beispielhaft traceroute verwendet, da dieses unter den meisten Linux-Versionen bereits zur „Grundausstattung“ gehört und somit für diesen Schritt keine weitere Software installiert werden muss. Die Verwendung von traceroute folgt der Syntax:

sudo traceroute ${ZIEL}

Als Ziel muss hier die IP-Adresse bzw. der Domainname des Zielrechners angegeben werden. Ein Beispiel soll dies vereinfachen:

$ sudo traceroute www.google.de
traceroute to www.google.de (172.217.22.99), 64 hops max
  1   192.168.0.1  167,148ms  3,200ms  11,636ms 
  2   83.169.183.11  21,389ms  19,380ms  88.134.203.107  16,746ms 
  3   88.134.203.107  27,431ms  24,063ms  * 
  4   88.134.237.6  1679,865ms  *  130,818ms 
  5   88.134.235.207  58,815ms  84,150ms  * 
  6   72.14.198.218 144,998ms  107,364ms  108.170.253.68  121,851ms 
  7   108.170.253.84  58,323ms  101,127ms  216.239.57.218  44,461ms 
  8   216.239.57.218  43,722ms  91,544ms  172.253.50.100  67,971ms 
  9   172.253.50.214  106,689ms  96,100ms  216.239.56.130  110,334ms 
 10   209.85.241.145  63,720ms  61,387ms  209.85.252.76  73,724ms 
 11   209.85.252.28  71,214ms  61,828ms  108.170.251.129  81,470ms 
 12   108.170.251.129  64,262ms  52,056ms  72.14.234.115  71,661ms 
 13   72.14.234.113  262,988ms  55,005ms  172.217.22.99  66,043ms 

Im Beispiel wird die Route zum Hostrechner mit der Domain www.google.de ermittelt. In der ersten Spalte der Ausgabe ist die Nummer des jeweiligen „Hops“ zu sehen. Wichtig ist insbesondere die zweite Spalte, welche die IPv4-Adresse des jeweiligen Rechners auf dem Weg zum Ziel darstellt. Die folgenden Spalten enthalten weitere Informationen wie Antwortzeiten der jeweiligen Server und die IP-Adressen der Folge-Server.

Um die Ausgabe in eine Form umzuwandeln, welche später einfacher von Python gelesen werden kann, muss diese noch ausgelesen werden (Parsing). zuerst soll die erste Zeile der Ausgabe herausgeschnitten werden, da diese zwar informativ, jedoch kein Teil der eigentlichen Route ist. Dies kann sehr einfach durchgeführt werden, indem die Ausgabe des traceroute-Befehls an einen Befehl wie beispielsweise sed „gepiped“ (also weitergeleitet) wird. Die dabei entstehende Pipe sieht dann wie folgt aus:

sudo traceroute ${ZIEL} | sed '1d'

Um bei unserem Beispiel mit der Route zu www.google.de zu bleiben, sieht der Befehl und die Entsprechende Ausgabe wie folgt aus:

$ sudo traceroute   | sed '1d'
  1   192.168.0.1  167,148ms  3,200ms  11,636ms 
  2   83.169.183.11  21,389ms  19,380ms  88.134.203.107  16,746ms 
  3   88.134.203.107  27,431ms  24,063ms  * 
  4   88.134.237.6  1679,865ms  *  130,818ms 
  5   88.134.235.207  58,815ms  84,150ms  * 
  6   72.14.198.218 144,998ms  107,364ms  108.170.253.68  121,851ms 
  7   108.170.253.84  58,323ms  101,127ms  216.239.57.218  44,461ms 
  8   216.239.57.218  43,722ms  91,544ms  172.253.50.100  67,971ms 
  9   172.253.50.214  106,689ms  96,100ms  216.239.56.130  110,334ms 
 10   209.85.241.145  63,720ms  61,387ms  209.85.252.76  73,724ms 
 11   209.85.252.28  71,214ms  61,828ms  108.170.251.129  81,470ms 
 12   108.170.251.129  64,262ms  52,056ms  72.14.234.115  71,661ms 
 13   72.14.234.113  262,988ms  55,005ms  172.217.22.99  66,043ms 

Anschließend soll die zweite Spalte der Ausgabe herausgeschnitten werden. Dies ist am einfachsten mit dem Befehl awk zu bewerkstelligen. Das Prinzip dahinter ist das gleiche wie im obigen Schritt: die Ausgabe des vorherigen Befehls wird dem Befehl awk als Eingabe weitergeleitet, womit der gesamte Befehl nun wie folgt aussieht:

sudo traceroute ${ZIEL} | sed '1d' | awk '{ print $2 }'

Bezogen auf das google-Beispiel sehen Ein- und Ausgabe nun so aus:

$ sudo traceroute | sed '1d' | awk '{ print $2 }'
192.168.0.1
83.169.183.11
88.134.203.107
88.134.237.6
88.134.235.207
72.14.198.218
108.170.253.84
216.239.57.218
172.253.50.214
209.85.241.145
209.85.252.28
108.170.251.129
72.14.234.113

Im letzten Schritt sollen die einzelnen IP-Adressen durch Leerzeichen getrennt in eine einzelne Zeile geschrieben werden. Sinn dieses Schrittes ist, dass später viele Zielrechner nacheinander aus einer Datei eingelesen werden können und jede Route zu einem Zielrechner als eine einzelne Zeile in eine Zieldatei geschrieben wird.
Auch dieser Schritt funktioniert ähnlich wie die obigen Schritte, indem die Ausgabe des letzten Schrittes an einen weiteren Befehl weitergeleitet wird, der diese Funktion erfüllt. Dieser Schritt könnte wieder mit dem Befehl sed durchgeführt werden, da aber nur ein einzelnes Zeichen (nämlich das Zeilenumbruch-Zeichen bzw. Newline) durch ein Leerzeichen ersetzt werden soll, wird hier aufgrund der einfacheren Syntax der Befehl tr verwendet.
Der fertige Befehl sieht nun wie folgt aus:

sudo traceroute ${ZIEL} | sed '1d' | awk '{ print $2 }' | tr '\n' ' '

Oder im fertigen Beispiel mit www.google.de:

$ sudo traceroute   | sed '1d' | awk '{ print $2 }' | tr '\n' ' '
192.168.0.1 83.169.183.11 88.134.203.107 88.134.237.6 88.134.235.207 72.14.198.218 108.170.253.84 216.239.57.218 172.253.50.214 209.85.241.145 209.85.252.28 108.170.251.129 72.14.234.113

Hiermit ist das Parsen abgeschlossen und die fertige Ausgabe kann nun in eine Ergebnisdatei geschrieben werden. Um automatisch viele Zielrechner aus einer Datei einzulesen und alle gefundenen Routen in eine Zieldatei zu schreiben, wird der obige Befehl in eine Schleife „verpackt“ welche die Zielrechner Zeile für Zeile aus der Datei zieladressen.txt ausliest und die gefundenen Routen ebenso Zeile für Zeile in die Datei routen.csv schreibt. Die Datei routen.csv kann später zur Ermittlung verschiedener Informationen zu den gefunden IP-Adressen einfach mit einem Python-Skript eingelesen und geparst werden.

In diesem Artikel wird das fertige Skript ohne weitere Erklärung in der beiliegenden zip-Datei bereitgestellt. Wen die genaue Funktionsweise der Schleife interessiert, sei angehalten sich generell über die Funktionsweise von Shellskripten einzulesen, da dies den Rahmen des Artikels sprengen würde.

#/bin/sh

cat zieladressen.txt | while read ZIEL; do
    printf 'Ermittle Route nach: %s\n' "${ZIEL}"
    traceroute ${ZIEL} | sed '1d' | awk '{ print $2 }' | tr '\n' ' ' >> routes.csv
    printf '\n' >> routes.csv
done

cat routes.csv | tr -d \* | tr -s ' ' > routes_corrected.csv
mv routes_corrected.csv routes.csv

Dieses Skript benötigt die Datei zieladressen.txt welche wie folgt aussehen muss (anstatt Domainnamen können auch direkt IPv4-Adressen verwendet werden):

www.google.de
www.github.com
www.google.nl
...

2. Sammeln von (Geo-)Informationen zu bestimmten IPv4-Adressen

Die gefundenen IPv4-Adressen können anschließend mit dem Befehl geoiplookup oder über die Internetseite http://geoiplookup.net/ relativ genau (meißtens auf Städteniveau) lokalisiert werden. Dies funktioniert, da einzelne Subnets in der Regel bestimmten Regionen und Internetprovidern zugeordnet sind.

Der Befehl geoiplookup greift hierbei auf eine vorher installierte und lokal gespeicherte Datenbank zu, welche je nach installierter Version als Country- oder City-Edition vorliegt. Da geoiplookup nicht zu den Standartbordmitteln unter Linux gehört und um die weiteren Schritte auch Benutzern anderer Betriebssysteme zu ermöglichen, wird hier nur ein kurzes Beispiel der Benutzung dieses Befehls und dessen Ausgabe gegeben und im weiteren die Online-Abfrage mittels eines Python-Skriptes beschrieben.

$ geoiplookup 172.217.22.99
GeoIP Country Edition: US, United States
GeoIP City Edition, Rev 1: US, CA, California, Mountain View, 94043, 37.419201, -122.057404, 807, 650
GeoIP ASNum Edition: AS15169 Google Inc.

Die Internetseite http://geoiplookup.net bietet einen Onlineservice welcher Geo- und weitere Informationen zu gegebenen IPv4-Adressen bereitstellt. Öffnet man die Seite ohne Angabe einer IP-Adresse in einem Browser, so erhält man die entsprechenden Informationen über die eigene IP-Adresse. (Achtung: die Verwendung eines Proxies oder gar Tor führt zwangsläufig zu falschen Ergebnissen.)

Da die Seite auch über eine API (also eine automatisierte Abfrageschnittstelle) unter der Adresse “http://api.geoiplookup.net/?query=${IPADRESSE}” verfügt, kann man die entsprechenden Informationen zu den IP-Adressen mittels eines Pythonskriptes abfragen und auswerten. Als Antwort erhält man eine XML‑Datei welche beispielsweise folgendermaßen aussieht:

<ip>
  <results>
    <result>
      <ip>77.20.253.87</ip>
      <host>77.20.253.87</host>
      <isp>Vodafone Kabel Deutschland</isp>
      <city>Hamburg</city>
      <countrycode>DE</countrycode>
      <countryname>Germany</countryname>
      <latitude>53.61530</latitude>
      <longitude>10.1162</longitude>
    </result>
  </results>
</ip>

Diese kann im Browser z. B. unter der Adresse http://api.geoiplookup.net/?query=77.20.253.87 aufgerufen werden (oder unter: http://api.geoiplookup.net/ für die eigene Adresse).

Um die hierin enthaltenen Informationen mit Hilfe von Python auszulesen lässt sich ElementTree aus aus dem Modul xml.etree, das in der Python-Standartbibliothek vorhanden ist, verwenden. Dies wird im beiliegenden Skript mit der Funktion get_hostinfo() bewerkstelligt:

def get_hostinfo(ipv4):
    ''' Returns geoiplookup information of agiven host adress as a dictionary.
    The adress can be given as a string representation 0f a DNS or IPv4 adress.

    get_hostinfo(str) -> dict

    Examples: get_hostinfo("www.github.com")
              get_hostinfo("151.101.12.133")
    '''

    apiurl = 'http://api.geoiplookup.net/?query='
    hostinfo = defaultdict(str, {})
    try:
        xml = urllib.request.urlopen(apiurl + dns2ipv4(ipv4)).read().decode()
        xml = xml.replace('&', '')
        tree = ETree.fromstring(xml)
        for element in tree.getiterator():
            hostinfo[element.tag] = element.text
    except:
        return hostinfo
    finally:
        return hostinfo

Diese parst die XML-Datei automatisch zu einem Python-DefaultDict das dann die entsprechenden Informationen enthält (das DefaultDict wird verwendet da normale Python Dictionaries zu Fehlern führen, wenn nicht gesetzte Werte abgefragt werden). Die Ausgabe der Funktion sieht dann wie folgt aus:

In [3]: get_hostinfo('www.google.com')
Out[3]:
defaultdict(str,
            {'city': 'Mountain View',
             'countrycode': 'US',
             'countryname': 'United States',
             'host': '172.217.22.99',
             'ip': '172.217.22.99',
             'isp': 'Google',
             'latitude': '37.4192',
             'longitude': '-122.0574',
             'result': None,
             'results': None})

3. Plotten der gefundenen Routen mit geoplotlib auf einer Weltkarte

Wichtig für das anschließende Plotten ist hierbei die Geolocation also ‘latitude’ und ‘longitude’. Mit den Werten kann man anschließend die mit traceroute gefundenen Pfade als Basemap plotten. Dies funktioniert mit der Funktion drawroutes2map():

def drawroutes2map(routesfile='routes.csv'):
    drawroutes = list()
    for route in open(routesfile).readlines():
        ips = [ip2location(ip) for ip in route.strip().split(',')]
        print(ips)
        locs = [loc for loc in ips if not loc == None]
        longs = [loc[0] for loc in locs]
        lats = [loc[1] for loc in locs]
        m = minimalmap()
        drawroutes.append(tuple(m(lats, longs)))
        for drawroute in drawroutes:
            m.plot(drawroute[0], drawroute[1], '-', markersize=0, linewidth=1, color=rand_color())
            pickleto(drawroutes, 'tracedlocs.plk')
    plt.savefig('world.svg', format='svg')
    plt.savefig('world.png', format='png')
    plt.show()

Der Plot einer Verbindungsanfrage an www.google.de aus Berlin sieht beispielsweise folgendermaßen aus:

Hier wird deutlich, dass Datenpakete durchaus nicht immer den kürzesten Weg nehmen, sondern teilweise rund um die Welt gesendet werden (Deutschland – USA – Sydney(!) – USA), bevor sie an ihrem Ziel ankommen und dass das Ziel einer Verbindung zu einer Domain mit der Endung „de“ nicht unbedingt in Deutschland liegen muss.

Mit Default-Einstellungen werden von der Funktion drawroutes2map() alle Routen in zufälligen Farben geplottet, welche in der Datei routen.csv gefunden werden.

Lässt man viele Routen plotten wird hierbei die Netzwerkstruktur deutlich, über die die Daten im Internet verteilt werden. Auf dem obigen Plot kann man recht gut erkennen, dass die meisten Internetseiten in Europa oder den USA gehostet werden, einige noch in China und Japan, dagegen beispielsweise Afrika praktisch unbedeutend ist.

Auf dem nächsten Plot wiederum ist zu erkennen, dass es tatsächlich eine Art “Hotspots” gibt über die fast alle Daten laufen, wie z. B. Frankfurt am Main, Zürich und Madrid.

4. Schematische Darstellung der Routen als directed Graph mit graphviz

Mit graphviz lassen sich schematische Graphen darstellen. Mit dem Paket pygraphviz existiert hiefür auch eine Python-Anbindung. Die schematische Darstellung als Graph ist in vielen Fällen deutlich übersichtlicher als die Darstellung auf einer Weltkarte und die Topologie des Netzwerkes wird besser sichtbar.

Die entsprechende Python-Funktion, die alle Routen aus der Datei routes.csv als geplotteten Graph ausgibt ist drawroutes2graph():

def drawroutes2graph(routesfile='routes.csv'):
    '''Draws all routes found in the routesfile with graphviz to a Graph

        drawroutes2graph(file)

    '''
    routes = open(routesfile).readlines()
    for i in range(len(routes)):
        routes[i] = routes[i].replace('*', '').split()
        G = pgv.AGraph(strict=False, directed=True)

    for l in routes:
        for i in range(len(l)-1):
            if not (l[i], l[i+1]) in set(G.edges()):
                G.add_edge(l[i], l[i+1])

    for n in G.nodes():
        if get_hostinfo(n)['countrycode'] == 'DE':
            n.attr['color'] = 'green'
        elif get_hostinfo(n)['countrycode'] == 'US':
            n.attr['color'] = 'red'
        elif get_hostinfo(n)['countrycode'] == 'ES':
            n.attr['color'] = 'yellow'
        elif get_hostinfo(n)['countrycode'] == 'CH':
            n.attr['color'] = 'blue'
        elif get_hostinfo(n)['countrycode'] == 'CN':
            n.attr['color'] = 'magenta'

        G.write('routes.dot')
        
        G.layout('dot')
        G.draw('dot.png')

        G.layout()
        G.draw('neato.png')

Die Funktion schreibt den erstellten Graph in der Dot-Language in die Datei routes.dot und erstellt zwei verschiedene visuelle Darstellungen als png-Dateien.

Da mit der Funktion get_hostinfo() auch weitere Informationen zu den jeweiligen IP-Adressen verfügbar sind  können diese auch visuell im Graph dargestellt werden. So sind in der folgenden Darstellung Hosts in verschiedenen Ländern in unterschiedlichen Farben dargestellt. (Deutschland in grün, USA in rot, Spanien in gelb, Schweiz in blau, China in magenta und alle übrigen Länder und Hosts ohne Länderinformation in schwarz).

Diese Art der Darstellung vereint damit die Vorteile der schematischen Darstellung mit der Geoinformation zu den jeweiligen Hosts. Aus der Grafik lässt sich beispielsweise sehr gut erkennen, dass, trotz oft vieler Zwischenstationen innerhalb eines Landes, Landesgrenzen überschreitende Verbindungen relativ selten sind.

Auch interessant ist, dass das Netzwerk durchaus Maschen aufweist – mit anderen Worten: Dass ein und dieselbe Station bei verschiedenen Verbindungsanfragen über verschiedene Zwischenstationen angesprochen wird und Daten, die von Punkt A nach Punkt B gesendet werden, nicht immer denselben Weg nehmen.

5. Schlussfolgerung

Was kann man hieraus denn nun letztendlich an Erkenntnissen ziehen? Zum einen natürlich, wie Daten via Internet über viele Zwischenstationen rund um die Welt gesendet und hierbei mit jeder Station neu sortiert werden. Vor allem aber auch, dass mit dem entsprechenden Know-How und etwas Kreativität mit bemerkenswert wenig Code bereits Unmengen an Daten gesammelt, geordnet und ausgewertet werden können. Alle möglichen Daten werden in unserer heutigen Welt gespeichert und sind zu einem nicht unbeträchtlichen Teil auch für jeden, der weiß, wer diese Daten hat oder wie man sie selber ermitteln kann, verfügbar und oft lassen sich hier interessante Einblicke in die Funktionsweise unserer Welt gewinnen.

Entscheidungsbaum-Algorithmus ID3

Dieser Artikel ist Teil 2 von 4 der Artikelserie Maschinelles Lernen mit Entscheidungsbaumverfahren.

Entscheidungsbäume sind den Ingenieuren bestens bekannt, um Produkte hierarchisch zu zerlegen und um Verfahrensanweisungen zu erstellen. Die Data Scientists möchten ebenfalls Verfahrensanweisungen erstellen, jedoch automatisiert aus den Daten heraus. Auf diese Weise angewendet, sind Entscheidungsbäume eine Form des maschinellen Lernens: Die Maschine soll selbst einen Weg finden, um ein Objekt einer Klasse zuzuordnen.

Der ID3-Algorithmus

Den ID3-Algorithmus zu verstehen lohnt sich, denn er ist die Grundlage für viele weitere, auf ihn aufbauende Algorithmen. Er ist mit seiner iterativen und rekursiven Vorgehensweise auch recht leicht zu verstehen, er darf nur wiederum nicht in seiner Wirkung unterschätzt werden. Die Vorgehensweise kann in drei wesentlichen Schritten zerlegt werden, wobei der erste Schritt die eigentliche Wirkung (mit allen Vor- und Nachteilen) entfaltet:

  1. Schritt: Auswählen des Attributes mit dem höchsten Informationsgewinn
    Betrachte alle Attribute (Merkmale) des Datensatzes und bestimme, welches Attribut die Daten am besten klassifiziert.
  2. Schritt: Anlegen eines Knotenpunktes mit dem Attribut
    Sollten die Ergebnisse unter diesem Knoten eindeutig sein (1 unique value), speichere es in diesem Knotenpunkt und springe zurück.
  3. Schritt: Rekursive Fortführung dieses Prozesses
    Andernfalls zerlege die Daten jedem Attribut entsprechend in n Untermengens (subsets), und wiederhole diese Schritte für jede der Teilmengen.

Der Informationsgewinn (Information Gain) – und wie man ihn berechnet


Der Informationsgewinn eines Attributes (A) im Sinne des ID3-Algorithmus ist die Differenz aus der Entropie (E(S)) (siehe Teil 1 der Artikelserie: Entropie, ein Maß für die Unreinheit in Daten) des gesamten Datensatzes (S) und der Summe aus den gewichteten Entropien des Attributes für jeden einzelnen Wert (Value i), der im Attribut vorkommt:
IG(S, A) = E(S) - \sum_{i=1}^n \frac{\bigl|S_i\bigl|}{\bigl|S\bigl|} \cdot E(S_i)

Wie die Berechnung des Informationsgewinnes funktioniert, wird Teil 3 dieser Artikel-Reihe (erscheint in Kürze) zeigen.

Die Vorzüge des ID3-Algorithmus – und die Nachteile

Der Algorithmus ist die Grundlage für viele weitere Algorithmen. In seiner Einfachheit bringt er gewisse Vorteile – die ihn vermutlich zum verbreitesten Entscheidungsbaum-Algorithmus machen – mit sich, aber hat auch eine Reihe von Nachteilen, die bedacht werden sollten.

Vorteile Nachteile
  • leicht verständlich und somit schnell implementiert
  • stellt eine gute Basis für Random Forests dar
  • alle Attribute spielen eine Rolle, der Baum wird aber tendenziell klein, da der Informationsgewinn die Reihenfolge vorgibt
  • funktioniert (mit Anpassungen) auch für Mehrfachklassifikation
  • aus der Reihenfolge durch den Informationsgewinn entsteht nicht unbedingt der beste bzw. kleinste Baum unter allen Möglichkeiten. Es ist ein Greedy-Algorithmus und somit “kurzsichtig”
  • die Suche nach Entscheidungsregeln ist daher auch nicht vollständig/umfassend
  • da der Baum via ID3 solange weiterwachsen soll, bis die Daten so eindeutig wie möglich erklärt sind, wird Overfitting geradezu provoziert

Overfitting (Überanpassung) beachten und vermeiden

Aus Daten heraus generierte Entscheidungsbäume neigen zur Überanpassung. Das bedeutet, dass sich die Bäume den Trainingsdaten soweit anpassen können, dass sie auf diese perfekt passen, jedoch keine oder nur noch einen unzureichende generalisierende Beschreibung mehr haben. Neue Daten, die eine höhere Vielfältigkeit als die Trainingsdaten haben können, werden dann nicht mehr unter einer angemessenen Fehlerquote korrekt klassifiziert.

Vorsicht vor Key-Spalten!

Einige Attribute erzwingen eine Überanpassung regelrecht: Wenn beispielsweise ein Attribut wie „Kunden-ID“ (eindeutige Nummer pro Kunde) einbezogen wird, haben wir – bezogen auf das Klassifikationsergebnis – für jeden einzelnen Wert in dem Attribut eine Entropie von 0 zu erwarten, denn jeder ID beschreibt einen eindeutigen Fall (Kunde, Kundengruppe etc.). Daraus folgt, dass der Informationsgewinn für dieses Attribut maximal wird. Hier würde der Baum eine enorme Breite erhalten, die nicht hilfreich wäre, denn jeder Wert (IDs) bekäme einen einzelnen Ast im Baum, der zu einem eindeutigen Ergebnis führt. Auf neue Daten (neue Kundennummern) ist der Baum nicht anwendbar, denn er stellt keine generalisierende Beschreibung mehr dar, sondern ist nur noch ein Abbild der Trainingsdaten.

Prunning – Den Baum nachträglich kürzen

Besonders große Bäume sind keine guten Bäume und ein Zeichen für Überanpassung. Eine Möglichkeit zur Verkleinerung ist das erneute Durchrechnen der Informationsgewinne und das kürzen von Verzweigungen (Verallgemeinerung), sollte der Informationsgewinn zu gering sein. Oftmals wird hierfür nicht die Entropie oder der Gini-Koeffizient, sondern der Klassifikationsfehler als Maß für die Unreinheit verwendet.

Random Forests als Overfitting-Allheilmittel

Bei Random Forests (eine Form des Ensemble Learning) handelt es sich um eine Gemeinschaftsentscheidung der Klassenzugehörigkeit über mehrere Entscheidungsbäume. Diese Art des “demokratischen” Machine Learnings wird auch Ensemble Learning genannt. Werden mehrere Entscheidungsbäume unterschiedlicher Strukturierung zur gemeinsamen Klassifikation verwendet, wird die Wirkung des Overfittings einzelner Bäume in der Regel reduziert.

Überwachtes vs unüberwachtes maschinelles Lernen

Dies ist Artikel 1 von 4 aus der Artikelserie – Was ist eigentlich Machine Learning?

Der Unterschied zwischen überwachten und unüberwachtem Lernen ist für Einsteiger in das Gebiet des maschinellen Lernens recht verwirrend. Ich halte die Bezeichnung “überwacht” und “unüberwacht” auch gar nicht für besonders gut, denn eigentlich wird jeder Algorithmus (zumindest anfangs) vom Menschen überwacht. Es sollte besser in trainierte und untrainierte Verfahren unterschieden werden, die nämlich völlig unterschiedliche Zwecke bedienen sollen:

Während nämlich überwachte maschinelle Lernverfahren über eine Trainingsphase regelrecht auf ein (!) Problem abgerichtet werden und dann produktiv als Assistenzsystem (bis hin zum Automated Decision Making) funktionieren sollen, sind demgegenüber unüberwachte maschinelle Lernverfahren eine Methodik, um unübersichtlich viele Zeilen und Spalten von folglich sehr großen Datenbeständen für den Menschen leichter interpretierbar machen zu können (was nicht immer funktioniert).

Trainiere dir deinen Algorithmus mit überwachtem maschinellen Lernen

Wenn ein Modell anhand von mit dem Ergebnis (z. B. Klassifikationsgruppe) gekennzeichneter Trainingsdaten erlernt werden soll, handelt es sich um überwachtes Lernen. Die richtige Antwort muss während der Trainingsphase also vorliegen und der Algorithmus muss die Lücke zwischen dem Input (Eingabewerte) und dem Output (das vorgeschriebene Ergebnis) füllen.

Die Überwachung bezieht sich dabei nur auf die Trainingsdaten! Im produktiven Lauf wird grundsätzlich nicht überwacht (und das Lernen könnte sich auf neue Daten in eine ganz andere Richtung entwickeln, als dies mit den Trainingsdaten der Fall war). Die Trainingsdaten

Eine besondere Form des überwachten Lernens ist die des bestärkenden Lernens. Bestärkendes Lernen kommt stets dann zum Einsatz, wenn ein Endergebnis noch gar nicht bestimmbar ist, jedoch der Trend hin zum Erfolg oder Misserfolg erkennbar wird (beispielsweise im Spielverlauf – AlphaGo von Google Deepmind soll bestärkend trainiert worden sein). In der Trainingsphase werden beim bestärkenden Lernen die korrekten Ergebnisse also nicht zur Verfügung gestellt, jedoch wird jedes Ergebnis bewertet, ob dieses (wahrscheinlich) in die richtige oder falsche Richtung geht (Annäherungslernen).

Zu den überwachten Lernverfahren zählen alle Verfahren zur Regression oder Klassifikation, beispielsweise mit Algorithmen wir k-nearest-Neighbour, Random Forest, künstliche neuronale Netze, Support Vector Machines oder auch Verfahren der Dimensionsreduktion wie die lineare Diskriminanzanalyse.

Mit unüberwachtem Lernen verborgene Strukturen identifizieren

Beim unüberwachten Lernen haben wir es mit nicht mit gekennzeichneten Daten zu tun, die möglichen Antworten/Ergebnisse sind uns gänzlich unbekannt. Folglich können wir den Algorithmus nicht trainieren, indem wir ihm die Ergebnisse, auf die er kommen soll, im Rahmen einer Trainingsphase vorgeben (überwachtes Lernen), sondern wir nutzen Algorithmen, die die Struktur der Daten erkunden und für uns Menschen sinnvolle Informationen aus Ihnen bilden (oder auch nicht – denn häufig bleibt es beim Versuch, denn der Erfolg ist nicht garantiert!).Unüberwachte Verfahren des maschinellen Lernens dienen dem Data Mining, also der Erkennung von Inhalten in Daten anhand von sichtbar werdenden Strukturen. Die Verfahren müssen nicht unbedingt mit Datenvisualisierung arbeiten, oft ist das aber der Fall, denn erst die visuellen Strukturen ermöglichen unseren menschlichen Gehirnen die Daten in einen Kontext zu bringen. Mir sind zwei Kategorien des unüberwachten Lernens bekannt, zum einem das Clustering, welches im Grunde ein unüberwachtes Klassifikationsverfahren darstellt, und zum anderen die Dimensionsreduktion PCA (Hauptkomponentenanalyse). Es gibt allerdings noch andere Verfahren, die mir weniger vertraut sind, beispielsweise unüberwacht lernende künstliche neuronale Netze, die Rauschen lernen, um Daten von eben diesem Rauschen zu befreien.

Was ist eigentlich Machine Learning? Artikelserie

Machine Learning ist Technik und Mythos zugleich. Nachfolgend der Versuch einer verständlichen Erklärung, mit folgenden Artikeln:

Machine Learning ist nicht neu, aber innovativ!

Machine Learning oder maschinelles Lernen ist eine Bezeichnung, die dank industrieller Trends wie der Industrie 4.0, Smart Grid oder dem autonomen Fahrzeug zur neuen Blüte verhilft. Machine Learning ist nichts Neues und die Algorithmen sind teilweise mehrere Jahrzehnte alt. Dennoch ist Machine Learning ein Innovationsinstrument, denn während früher nur abstrakte Anwendungen, mit vornehmlich wissenschaftlichen Hintergrund, auf maschinellem Lernen setzten, finden entsprechende Algorithmen Einzug in alltägliche industrielle bzw. geschäftliche, medizinische und gesellschaftsorientierte Anwendungen. Machine Learning erhöht demnach sowohl unseren Lebensstandard als auch unsere Lebenserwartung!

Maschinelles Lernen vs künstliche Intelligenz

Künstliche Intelligenz (Artificial Intelligence) ist eine Bezeichnung, die in der Wissenschaft immer noch viel diskutiert wird. Wo beginnt künstliche Intelligenz, wann entsteht natürliche Intelligenz und was ist Intelligenz überhaupt? Wenn diese Wortkombination künstliche Intelligenz fällt, denken die meisten Zuhörer an Filme wie Terminator von James Cameron oder AI von Steven Spielberg. Diese Filme wecken Erwartungen (und Ängste), denen wir mir unseren selbstlernenden Systemen noch lange nicht gerecht werden können. Von künstlicher Intelligenz sollte als mit Bedacht gesprochen werden.

Maschinelles Lernen ist Teilgebiet der künstlichen Intelligenz und eine Sammlung von mathematischen Verfahren zur Mustererkennung, die entweder über generelle Prinzipien (das Finden von Gemeinsamkeiten oder relativen Abgrenzungen) funktioniert [unüberwachtes Lernen] oder durch das Bilden eines Algorithmus als Bindeglied zwischen Input und gewünschten Output aus Trainingsdaten heraus.

Machine Learning vs Deep Learning

Deep Learning ist eine spezielle Form des maschinellen Lernens, die vermutlich in den kommenden Jahren zum Standard werden wird. Gemeint sind damit künstliche neuronale Netze, manchmal auch verschachtelte “herkömmliche” Verfahren, die zum einen mehrere Ebenen bilden (verborgene Schichten eines neuronalen Netzes) zum anderen viel komplexere Zusammenhänge erlernen können, was den Begriff Deep Learning rechtfertigt.

Machine Learning vs Data Mining

Data Mining bezeichnet die Erkenntnisgewinnung aus bisher nicht oder nicht hinreichend erforschter Daten. Unüberwachte Verfahren des maschinellen Lernens, dazu gehören einige Verfahren aus dem Clustering und der Dimensionsreduktion, dienen explizit dem Zweck des Data Minings. Es sind Verfahren, die uns Menschen dabei helfen, vielfältige und große Datenmengen leichter interpretieren zu können. Machine Learning ermöglicht jedoch noch weit mehr als Data Mining.

Scikit-Learn Machine Learning Roadmap

Darstellung der vier Gebiete des Machine Learning: Die scikit-learn-Roadmap. Die Darstellung ist nicht vollständig, sondern umfasst nur die in scikit-learn implementierten Verfahren. Das Original-Bild ist interaktiv und zu finden auf scikit-learn.org

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.

set.seed(123)
Alter <- c(24, 22, 28, 25, 41, 39, 35, 40, 62, 57, 60, 55)
Einkommen <- c(20000, 22000, 25000, 24000, 55000, 65000, 75000, 60000, 30000, 34000, 30000, 34000)
Daten <- as.data.frame(cbind(Alter, Einkommen))

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.

DatenAlter <- scale(DatenAlter)
DatenEinkommen <- scale(DatenEinkommen)

Das Ganze geplottet:

plot(DatenAlter, DatenEinkommen, col = "blue", pch = 19,
     xlab = "Alter (scaled)",
     ylab = "Einkommen (scaled)",
     main = "Alter vs. Einkommen (scaled)")

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:

KmeansObj <- kmeans(Daten, 3, nstart = 20)
KmeansObjwithinss # Within Cluster Sums of Squares (WSS) KmeansObjtotss # Between Cluster Sums of Suqares (BSS)

> KmeansObjwithinss # Within Cluster Sums of Squares (WSS) [1] 0.7056937 0.1281607 0.1792432 > KmeansObjtotss # Between Cluster Sums of Suqares (BSS)
[1] 22

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.

ratio <- vector()
for (k in 1:6) {
    KMeansObj <- kmeans(Daten, k, nstart = 20)
    ratio[k] <- KMeansObjtot.withinss / KMeansObjtotss
}
plot(ratio, type = "b",
     xlab = "Anzahl der Cluster",
     ylab = "Ratio WSS/BSS",
     main = "Screeplot für verschiedene Clusterlösungen",
col = "blue",  pch = 19)

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.

KmeansObj <- kmeans(Daten, centers = 3, nstart = 20)
plot(DatenAlter, DatenEinkommen, col = KmeansObjcluster, pch = 19, cex = 4,      xlab = "Alter (scaled)",      ylab = "Einkommen (scaled)",      main = "3-Cluster-Lösung") points(KmeansObjcenters, col = 1:3, pch = 3, cex = 5, lwd = 5)

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.

Der Blick für das Wesentliche: Die Merkmalsselektion

In vielen Wissensbasen werden Datensätze durch sehr große Merkmalsräume beschrieben. Während der Generierung einer Wissensbasis wird versucht jedes mögliche Merkmal zu erfassen, um einen Datensatz möglichst genau zu beschreiben. Dabei muss aber nicht jedes Merkmal einen nachhaltigen Wert für das Predictive Modelling darstellen. Ein Klassifikator arbeitet mit reduziertem Merkmalsraum nicht nur schneller, sondern in der Regel auch weitaus effizienter. Oftmals erweist sich ein automatischer Ansatz der Merkmalsselektion besser, als ein manueller, da durchaus Zusammenhänge existieren können, die wir selbst so nicht identifizieren können.

Die Theorie: Merkmalsselektion

Automatische Merkmalsselektionsverfahren unterscheiden 3 verschiedene Arten: Filter, Wrapper und Embedded Methods. Einen guten Überblick über Filter- und Wrapper-Verfahren bieten Kumari et al. in ihrer Arbeit “Filter versus wrapper feature subset selection in large dimensionality micro array: A review” (Download als PDF).

Der Filter-Ansatz bewertet die Merkmale unabhängig des Klassifikators. Dabei werden univariate und multivariate Methoden unterschieden. Univariate Methoden bewerten die Merkmale separat, während der multivariate Ansatz mehrere Merkmale kombiniert. Für jedes Merkmal bzw. jedes Merkmalspaar wird ein statistischer Wert berechnet, der die Eignung der Merkmale für die Klassifikation angibt. Mithilfe eines Schwellwertes werden dann geeignete Merkmale herausgefiltert. Der Filter-Ansatz bietet eine schnelle und, aufgrund der geringen Komplexität, leicht skalierbare Lösung für die Merkmalsselektion. Der Nachteil von Filter-Selektoren besteht in der Missachtung der Abhängigkeiten zwischen den Merkmalen. So werden redundante Merkmale ähnlich bewertet und verzerren später die Erfolgsrate des Klassifikators. Bekannte Beispiele für Filter-Selektoren sind unter anderem die Euklidische Distanz und der Chi-2-Test.

Der Wrapper-Ansatz verbindet die Merkmalsbewertung mit einem Klassifikator. Innerhalb des Merkmalsraumes werden verschiedene Teilmengen von Merkmalen generiert und mithilfe eines trainierten Klassifikators getestet. Um alle möglichen Teilmengen des Merkmalsraumes zu identifizieren, wird der Klassifikator mit einem Suchalgorithmus kombiniert. Da der Merkmalsraum mit Zunahme der Anzahl der Merkmale exponentiell steigt, werden heuristische Suchmethoden für die Suche nach optimalen Teilmengen genutzt. Im Gegensatz zu den Filtern können hier redundante Merkmale abgefangen werden. Die Nutzung eines Klassifikators zur Bewertung der Teilmengen ist zugleich Vor- und Nachteil. Da die generierte Teilmenge auf einen speziellen Klassifikator zugeschnitten wird, ist nicht gewährleistet, dass die Menge auch für andere Klassifikatoren optimal ist. Somit ist dieser Ansatz zumeist abhängig vom gewählten Klassifikator. Zudem benötigt der Wrapper-Ansatz eine viel höhere Rechenzeit. Wrapper-Selektoren werden beispielsweise durch Genetische Algorithmen und Sequentielle Forward/Backward-Selektoren vertreten.

Embedded-Ansätze stellen eine Sonderform der Wrapper-Methode da. Allerdings werden Merkmalssuche und Klassifikatoren-Training nicht getrennt. Die Suche der optimalen Teilmenge ist hier im Modelltraining eingebettet. Dadurch liefern Embedded-Ansätze die gleichen Vorteile wie die Wrapper-Methoden, während die Rechenzeit dabei erheblich gesenkt werden kann. Der reduzierte Merkmalsraum ist aber auch hier vom jeweiligen Klassifikator abhängig. Klassifikatoren, die den Embedded-Ansatz ermöglichen sind beispielsweise der Random-Forest oder die Support-Vector-Maschine.

Entwicklungsgrundlage

Analog zum letzten Tutorial wird hier Python(x,y) und die Datenbasis „Human Activity Recognition Using Smartphones“ genutzt. Die Datenbasis beruht auf erfassten Sensordaten eines Smartphones während speziellen menschlichen Aktivitäten: Laufen, Treppen hinaufsteigen, Treppen herabsteigen, Sitzen, Stehen und Liegen. Auf den Aufzeichnungen von Gyroskop und Accelerometer wurden mehrere Merkmale erhoben. Die Datenmenge, alle zugehörigen Daten und die Beschreibung der Daten sind frei verfügbar.

(https://archive.ics.uci.edu/ml/datasets/Human+Activity+Recognition+Using+Smartphones)

Alle Daten liegen im Textformat vor. Für ein effizienteres Arbeiten mit der Datenbasis wurden diese im Vorfeld in das csv-Dateiformat überführt.

Python-Bibliotheken

Alle für das Data Mining relevanten Bibliotheken sind in Python(x,y) bereits enthalten. Für die Umsetzung werden folgende Bibliotheken genutzt:

import numpy as np
import pandas as pd

from sklearn.cross_validation import StratifiedKFold
from sklearn.ensemble import RandomForestClassifier
from sklearn.feature_selection import f_classif, RFECV, SelectKBest
from sklearn.svm import SVC

Die Bibliotheken NumPy und Pandas unterstützen die Arbeit mit verschiedenen Datenstrukturen und scikit-learn umfasst alle Funktionen des maschinellen Lernens.

Daten vorbereiten

Vor der Anwendung der einzelnen Verfahren werden die Daten vorbereitet. Das Data Frame wird eingelesen, die Klassen in numerische Labels überführt und das Datenfeld in Merkmale (X) und Klassenspalte (y) separiert. Weiterhin wird die informationslose Spalte subject entfernt.

index = 0
selected_features = []

# reading database
data = pd.read_csv("data/measures.csv", sep = ';', decimal = ',')

# converting textual class labels to numeric classes like description
data = data.replace({'WALKING': 1, 'WALKING_UPSTAIRS': 2, 'WALKING_DOWNSTAIRS': 3,
              'SITTING': 4, 'STANDING': 5, 'LAYING': 6})

# drop subject column
data = data.drop('subject', 1)

# remove class column from data set
print "removing class column from training set.."
X = data.drop('activity', 1)
y = data['activity']

columns = X.columns.values.tolist()

1. Verfahren: RFECV

Der RFECV (Recursive Feature Elimination with Cross Validation) ist ein Vertreter des Wrapper-Ansatzes. In diesem Beispiel wird die Merkmalsselektion mit einem Support Vector Klassifikator kombiniert. Der RFECV berechnet ein Ranking über die einzelnen Merkmale. Dabei bestimmt der Selektor selbst die optimale Menge der Merkmale. Alle Merkmale mit Platz 1 im Ranking bilden den optimalen Merkmalsraum.

''' ########## METHOD 1: RFE with cross validation and SVC ########## '''
print "create classifier for feature selection.."
svc = SVC(kernel = 'linear')

# fit the feature selector
print "create the feature selector.."
rfecv = RFECV(estimator = svc, step = 1, cv = StratifiedKFold(y, 3), scoring = 'accuracy')
print "fit the selector for data set.."
rfecv.fit(X, y)

print "The estimated number of optimal features is: " + str(rfecv.n_features_)

# get the most importent features
feat_importence = zip(rfecv.ranking_, columns)

# prepare list of selected features for new DataFrame
for i in range(len(feat_importence)):
    if(feat_importence[i][0] == 1):#>= np.nanmean(rfecv.ranking_)):
        selected_features.append(feat_importence[i][1])
        print "added feature: " + str(feat_importence[i][1]) + ".."

2. Verfahren: Random Forest-Klassifikator

Der Random-Forest-Klassifikator gehört zu den Modellen, die einen Embedded-Ansatz ermöglichen. Während des Klassifikatoren-Trainings wird jedem Merkmal ein Wert zugeordnet. Je höher der Wert, desto bedeutsamer das Merkmal. Allerdings ist hier eine manuelle Filterung notwendig, da anders als beim RFECV kein internes Optimum ermittelt wird. Mithilfe eines geeigneten Schwellwertes können die zu wählenden Merkmale bestimmt werden. In diesem Beispiel werden alle Merkmale selektiert, die eine Wichtung größer dem Mittelwert erhalten.

''' ########## METHOD 2: Random Forrest Classifier Feat Importance ########## '''
print "create classifier for feature selection.."
rfc = RandomForestClassifier(n_estimators = 500, criterion = 'entropy', max_depth = 4)
rfc = rfc.fit(X, y)

# get the most importent features
feat_importence = zip(rfc.feature_importances_, columns)

# prepare list of selected features for new DataFrame
for i in range(len(feat_importence)):
    if(feat_importence[i][0] >= np.mean(rfc.feature_importances_)):
        selected_features.append(feat_importence[i][1])
        print "added feature: " + str(feat_importence[i][1]) + ".."

3. Verfahren: Select K Best

Das Select K Best-Verfahren gehört den Filter-Ansätzen an. Daher kommt hier anders als bei den anderen beiden Verfahren kein Klassifikator zum Einsatz. Auch in diesem Verfahren wird für jedes Merkmal ein Wert berechnet, der die Wichtigkeit des Merkmals beziffert. Für die Berechnung der Werte können verschiedene Methoden verwendet werden. In diesem Beispiel wird eine Varianzanalyse genutzt (Parameter f_classif). Auch hier wird mithilfe eines manuellen Schwellwertes der reduzierte Merkmalsraum bestimmt.

''' ########## METHOD 3: Select K Best Features ########## '''
print "create classifier for feature selection.."
skb = SelectKBest(f_classif)
skb = skb.fit(X, y)

# get the most importent features
feat_importence = zip(skb.scores_, columns)

# prepare list of selected features for new DataFrame
for i in range(len(feat_importence)):
    if(feat_importence[i][0] >= np.nanmean(skb.scores_)):
        selected_features.append(feat_importence[i][1])
        print "added feature: " + str(feat_importence[i][1]) + ".."

Ergebnisse

Für die Bewertung der einzelnen Selektionsverfahren werden die einzelnen Verfahren in den Data-Mining-Prozess (siehe vorheriges Tutorial: Einstieg in das maschinelle Lernen mit Python(x,y)) integriert. Die nachfolgende Tabelle veranschaulicht die Ergebnisse der Klassifikation der einzelnen Verfahren.

 

Selektionsverfahren

Anzahl der Merkmale

Erfolgsrate Klassifikation

Ohne

561

93,96%

RFECV

314

94,03%

Random Forest

118

90,43%

Select K Best

186

92,30%

 

Durch den RFECV konnte das Ergebnis der Klassifikation leicht verbessert werden. Die anderen Selektionsverfahren, die auch deutlich weniger Merkmale nutzen, verschlechtern das Ergebnis sogar. Dies liegt vor allem an der manuellen Regulierung des Schwellwertes.