Tag Archive for: Command Line

Christopher Kipp

Erstellen und benutzen einer Geodatenbank

/in , , , , , , , , , , , , /by

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.

Vishal Bhalla

Statistical Relational Learning – Part 2

/in , , , , , , , /by

In the first part of this series on “An Introduction to Statistical Relational Learning”, I touched upon the basic Machine Learning paradigms, some background and intuition of the concepts and concluded with how the MLN template looks like. In this blog, we will dive in to get an in depth knowledge on the MLN template; again with the help of sample examples. I would then conclude by highlighting the various toolkit available and some of its differentiating features.

MLN Template – explained

A Markov logic network can be thought of as a group of formulas incorporating first-order logic and also tied with a weight. But what exactly does this weight signify?

Weight Learning

According to the definition, it is the log odds between a world where F is true and a world where F is false,

and captures the marginal distribution of the corresponding predicate.

Each formula can be associated with some weight value, that is a positive or negative real number. The higher the value of weight, the stronger the constraint represented by the formula. In contrast to classical logic, all worlds (i.e., Herbrand Interpretations) are possible with a certain probability [1]. The main idea behind this is that the probability of a world increases as the number of formulas it violates decreases.

Markov logic networks with its probabilistic approach combined to logic posit that a world is less likely if it violates formulas unlike in pure logic where a world is false if it violates even a single formula. Consider the case when a formula with high weight i.e. more significance is violated implying that it is less likely in occurrence.

Another important concept during the first phase of Weight Learning while applying an MLN template is “Grounding”. Grounding means to replace each variable/function in predicate with constants from the domain.

Weight Learning – An Example

Note: All examples are highlighted in the Alchemy MLN format

Let us consider an example where we want to identify the relationship between 2 different types of verb-noun pairs i.e noun subject and direct object.

The input predicateFormula.mln file contains

  1. The predicates nsubj(verb, subject) and dobj(verb, object) and
  2. Formula of nsubj(+ver, +s) and dobj(+ver, +o)

These predicates or rules are to learn all possible SVO combinations i.e. what is the probability of a Subject-Verb-Object combination. The + sign ensures a cross product between the domains and learns all combinations. The training database consists of the nsubj and dobj tuples i.e. relations is the evidence used to learn the weights.

When we run the above command for this set of rules against the training evidence, we learn the weights as here:

Note that the formula is now grounded by all occurrences of nsubj and dobj tuples from the training database or evidence and the weights are attached to it at the start of each such combination.

But it should be noted that there is no network yet and this is just a set of weighted first-order logic formulas. The MLN template we created so far will generate Markov networks from all of our ground formulas. Internally, it is represented as a factor graph.where each ground formula is a factor and all the ground predicates found in the ground formula are linked to the factor.

Inference

The definition goes as follows:

Estimate probability distribution encoded by a graphical model, for a given data (or observation).

Out of the many Inference algorithms, the two major ones are MAP & Marginal Inference. For example, in a MAP Inference we find the most likely state of world given evidence, where y is the query and x is the evidence.

which is in turn equivalent to this formula.

Another is the Marginal Inference which computes the conditional probability of query predicates, given some evidence. Some advanced inference algorithms are Loopy Belief Propagation, Walk-SAT, MC-SAT, etc.

The probability of a world is given by the weighted sum of all true groundings of a formula i under an exponential function, divided by the partition function Z i.e. equivalent to the sum of the values of all possible assignments. The partition function acts a normalization constant to get the probability values between 0 and 1.

Inference – An Example

Let us draw inference on the the same example as earlier.

After learning the weights we run inference (with or without partial evidence) and query the relations of interest (nsubj here), to get inferred values.

Tool-kits

Let’s look at some of the MLN tool-kits at disposal to do learning and large scale inference. I have tried to make an assorted list of all tools here and tried to highlight some of its main features & problems.

For example, BUGS i.e. Bayesian Logic uses a Swift Compiler but is Not relational! ProbLog has a Python wrapper and is based on Horn clauses but has No Learning feature. These tools were invented in the initial days, much before the present day MLN looks like.

ProbCog developed at Technical University of Munich (TUM) & the AI Lab at Bremen covers not just MLN but also Bayesian Logic Networks (BLNs), Bayesian Networks & ProLog. In fact, it is now GUI based. Thebeast gives a shell to analyze & inspect model feature weights & missing features.

Alchemy from University of Washington (UoW) was the 1st First Order (FO) probabilistic logic toolkit. RockIt from University of Mannheim has an online & rest based interface and uses only Conjunctive Normal Forms (CNF) i.e. And-Or format in its formulas.

Tuffy scales this up by using a Relational Database Management System (RDBMS) whereas Felix allows Large Scale inference! Elementary makes use of secondary storage and Deep Dive is the current state of the art. All of these tools are part of the HAZY project group at Stanford University.

Lastly, LoMRF i.e. Logical Markov Random Field (MRF) is Scala based and has a feature to analyse different hypothesis by comparing the difference in .mln files!

 

Hope you enjoyed the read. The content starts from basic concepts and ends up highlighting key tools. In the final part of this 3 part blog series I would explain an application scenario and highlight the active research and industry players. Any feedback as a comment below or through a message is more than welcome!

Back to Part I – Statistical Relational Learning

Additional Links:

[1] Knowledge base files in Logical Markov Random Fields (LoMRF)

[2] (still) nothing clever Posts categorized “Machine Learning” – Markov Logic Networks

[3] A gentle introduction to statistical relational learning: maths, code, and examples

Benjamin Aunkofer

Auswertung von CSV- und Log-Dateien auf der Command Line mit awk

/in , , /by

Die Programmiersprache awk ist klein und unscheinbar, unter Data Science at the Command Line-Verfechtern allerdings ein häufiges Tool zur schnellen Analyse von CSV-Datein und vergleichbar strukturierten Daten (z. B. Logfiles) mit über Trennzeichen differenzierten Spalten. Auch in Shell-Skripten kommt awk meistens dann zum Einsatz, wenn es um den Zugriff, aber auch um die Manipulation von solchen Dateien geht.

Data Science at the Command Line: Facing the Future with Time-Tested Tools

awk wird als Skriptsprache mit nahezu jeder Linux-Distribution ausgeliefert und ist recht einfach eingehalten, kann jedoch auch schnell kryptisch werden. awk wird meistens ad-hoc auf der Kommandozeile ausgeführt, es können jedoch auch Skripte in awk-Dateien erstellt werden. Häufiger Grund für den Einsatz von awk ist die Anwendung von regulären Ausdrücken (Textmustersuche) auf Logdateien.

Nachfolgend ein kleines Tutorial für den Schnelleinstieg in diese interessante Analysetool auf Kommandozeile. Die CSV-Datei einfach hier downloaden: (einen Überblick über den Inhalt bietet auch eine Einführung in Python, die ebenfalls auf dieser CSV-Datei basiert)

CSV-Datei gedownloaded? Dann kann es losgehen im Terminal jeder beliebiger Linux-Distribution:

Anweisungen, so auch die obige, beginnen stets mit “awk”. Da diese CSV-Datei nicht mit dem Standardchar (Komma), sondern einem vertikalen Strich (Pipe) getrennt ist, muss dies via “-F’|'” angegeben werden. Wäre das Trennzeichen ein Semikolon, wäre der Parameter “-F’;'” korrekt. Der Befehl gibt jede Zeile des CSV in der Kommandozeile aus, so dass wie nachfolgend den gesamten Dateiinhalt sehen:

Viele CSV- und Logdateien haben keinen Header, diese hier hat jedoch die erste Zeile als Header, die daher bei der Analyse nicht als Werte-Zeile fehlinterpretiert werden darf, daher wird nachfolgend von nun an die Anweisung “NR>1” mitgegeben:

Spalten werden in awk über das Dollarzeichen angesprochen, folgende Anweisung zeigt uns alle Zeilen der zweiten Spalte:

Diese Skriptsprache beherrscht assoziative Arrays. Es können demnach auch nicht-numerische Schlüssel für den Zugriff auf Datenfelder verwendet werden. Dies machen wir uns für das Anzeigen aller Standorte mit Angabe der jeweiligen Mitarbeiterzahl an dem Standort zu nutze. Die Variable a speichert alle Mitarbeiterzahlen in Spalte 4 über den Schlüssel des Standortnamens in Spalte 2, dann endet der Anweisungsblock und es folgt eine For-Schleife, die alle Schlüsselwerte ausgibt und den dazugehörigen Speicherwert (Mitarbeiterzahl) ausgibt.

Auch If-Anweisungen sind einfach machbar. Folgendes Beispiel unterscheidet die Zeilennummern (Spalte1) nach geraden und ungeraden Zahlen und gibt den dazugehörigen Standortnamen (Spalte 2) aus.

Folgendes Beispiel klassifiziert alle Standorte mit weniger als 10 Mitarbeitern, allerdings nicht über “if…else…”, sondern über die Kurzabfrage nach dem Schema a>b?”True”:”False”.

Folgendes Code-Beispiel zeigt die Zählung der Vorkommnisse (Entsprechung: GROUP BY Spalte3, Count(*)).

Etwas umformuliert, können wir auch die Werte pro Gruppe aufsummieren, nachfolgend beispielhaft der Gewinn (Einnahmen aus Spalte 5 – Kosten aus Spalte 6) und die Mitarbeiterzahl über die jeweilige Gruppe.

Das Zusammenführen von Zeichenketten erfolgt simpel durch Aneinandereihung:

Ein letztes Beispiel möchte keine einzelnen Zeilen des Datensatzes auflisten und auch keine Gruppierung unterscheiden, sondern die Zusammenfassung über die Angabe der gesamten Mitarbeiteranzahl und der Gewinn-Summe über alle Standorte angeben.

Fazit

Als Programmiersprache ist awk sicherlich nur ein nice-to-have, aber wenn man das Prinzip dieser Sprache erstmal verstanden hat, kann sie ein interessantes Tool darstellen, um schon auf Kommandozeilenebene sich schnell einen Überblick über Datenbestände zu beschaffen und auch um Datenqualitätstests durchzuführen.