A Bird’s Eye View: How Machine Learning Can Help You Charge Your E-Scooters

Bird scooters in Columbus, Ohio

Bird scooters in Columbus, Ohio

Ever since I started using bike-sharing to get around in Seattle, I have become fascinated with geolocation data and the transportation sharing economy. When I saw this project leveraging the mobility data RESTful API from the Los Angeles Department of Transportation, I was eager to dive in and get my hands dirty building a data product utilizing a company’s mobility data API.

Unfortunately, the major bike and scooter providers (Bird, JUMP, Lime) don’t have publicly accessible APIs. However, some folks have seemingly been able to reverse-engineer the Bird API used to populate the maps in their Android and iOS applications.

One interesting feature of this data is the nest_id, which indicates if the Bird scooter is in a “nest” — a centralized drop-off spot for charged Birds to be released back into circulation.

I set out to ask the following questions:

  1. Can real-time predictions be made to determine if a scooter is currently in a nest?
  2. For non-nest scooters, can new nest location recommendations be generated from geospatial clustering?

To answer these questions, I built a full-stack machine learning web application, NestGenerator, which provides an automated recommendation engine for new nest locations. This application can help power Bird’s internal nest location generation that runs within their Android and iOS applications. NestGenerator also provides real-time strategic insight for Bird chargers who are enticed to optimize their scooter collection and drop-off route based on proximity to scooters and nest locations in their area.

Bird

The electric scooter market has seen substantial growth with Bird’s recent billion dollar valuation  and their $300 million Series C round in the summer of 2018. Bird offers electric scooters that top out at 15 mph, cost $1 to unlock and 15 cents per minute of use. Bird scooters are in over 100 cities globally and they announced in late 2018 that they eclipsed 10 million scooter rides since their launch in 2017.

Bird scooters in Tel Aviv, Israel

Bird scooters in Tel Aviv, Israel

With all of these scooters populating cities, there’s much-needed demand for people to charge them. Since they are electric, someone needs to charge them! A charger can earn additional income for charging the scooters at their home and releasing them back into circulation at nest locations. The base price for charging each Bird is $5.00. It goes up from there when the Birds are harder to capture.

Data Collection and Machine Learning Pipeline

The full data pipeline for building “NestGenerator”

Data

From the details here, I was able to write a Python script that returned a list of Bird scooters within a specified area, their geolocation, unique ID, battery level and a nest ID.

I collected scooter data from four cities (Atlanta, Austin, Santa Monica, and Washington D.C.) across varying times of day over the course of four weeks. Collecting data from different cities was critical to the goal of training a machine learning model that would generalize well across cities.

Once equipped with the scooter’s latitude and longitude coordinates, I was able to leverage additional APIs and municipal data sources to get granular geolocation data to create an original scooter attribute and city feature dataset.

Data Sources:

  • Walk Score API: returns a walk score, transit score and bike score for any location.
  • Google Elevation API: returns elevation data for all locations on the surface of the earth.
  • Google Places API: returns information about places. Places are defined within this API as establishments, geographic locations, or prominent points of interest.
  • Google Reverse Geocoding API: reverse geocoding is the process of converting geographic coordinates into a human-readable address.
  • Weather Company Data: returns the current weather conditions for a geolocation.
  • LocationIQ: Nearby Points of Interest (PoI) API returns specified PoIs or places around a given coordinate.
  • OSMnx: Python package that lets you download spatial geometries and model, project, visualize, and analyze street networks from OpenStreetMap’s APIs.

Feature Engineering

After extensive API wrangling, which included a four-week prolonged data collection phase, I was finally able to put together a diverse feature set to train machine learning models. I engineered 38 features to classify if a scooter is currently in a nest.

Full Feature Set

Full Feature Set

The features boiled down into four categories:

  • Amenity-based: parks within a given radius, gas stations within a given radius, walk score, bike score
  • City Network Structure: intersection count, average circuity, street length average, average streets per node, elevation level
  • Distance-based: proximity to closest highway, primary road, secondary road, residential road
  • Scooter-specific attributes: battery level, proximity to closest scooter, high battery level (> 90%) scooters within a given radius, total scooters within a given radius

 

Log-Scale Transformation

For each feature, I plotted the distribution to explore the data for feature engineering opportunities. For features with a right-skewed distribution, where the mean is typically greater than the median, I applied these log transformations to normalize the distribution and reduce the variability of outlier observations. This approach was used to generate a log feature for proximity to closest scooter, closest highway, primary road, secondary road, and residential road.

An example of a log transformation

Statistical Analysis: A Systematic Approach

Next, I wanted to ensure that the features I included in my model displayed significant differences when broken up by nest classification. My thinking was that any features that did not significantly differ when stratified by nest classification would not have a meaningful predictive impact on whether a scooter was in a nest or not.

Distributions of a feature stratified by their nest classification can be tested for statistically significant differences. I used an unpaired samples t-test with a 0.01% significance level to compute a p-value and confidence interval to determine if there was a statistically significant difference in means for a feature stratified by nest classification. I rejected the null hypothesis if a p-value was smaller than the 0.01% threshold and if the 99.9% confidence interval did not straddle zero. By rejecting the null-hypothesis in favor of the alternative hypothesis, it’s deemed there is a significant difference in means of a feature by nest classification.

Battery Level Distribution Stratified by Nest Classification to run a t-test

Battery Level Distribution Stratified by Nest Classification to run a t-test

Log of Closest Scooter Distribution Stratified by Nest Classification to run a t-test

Throwing Away Features

Using the approach above, I removed ten features that did not display statistically significant results.

Statistically Insignificant Features Removed Before Model Development

Model Development

I trained two models, a random forest classifier and an extreme gradient boosting classifier since tree-based models can handle skewed data, capture important feature interactions, and provide a feature importance calculation. I trained the models on 70% of the data collected for all four cities and reserved the remaining 30% for testing.

After hyper-parameter tuning the models for performance on cross-validation data it was time to run the models on the 30% of test data set aside from the initial data collection.

I also collected additional test data from other cities (Columbus, Fort Lauderdale, San Diego) not involved in training the models. I took this step to ensure the selection of a machine learning model that would generalize well across cities. The performance of each model on the additional test data determined which model would be integrated into the application development.

Performance on Additional Cities Test Data

The Random Forest Classifier displayed superior performance across the board

The Random Forest Classifier displayed superior performance across the board

I opted to move forward with the random forest model because of its superior performance on AUC score and accuracy metrics on the additional cities test data. AUC is the Area under the ROC Curve, and it provides an aggregate measure of model performance across all possible classification thresholds.

AUC Score on Test Data for each Model

AUC Score on Test Data for each Model

Feature Importance

Battery level dominated as the most important feature. Additional important model features were proximity to high level battery scooters, proximity to closest scooter, and average distance to high level battery scooters.

Feature Importance for the Random Forest Classifier

Feature Importance for the Random Forest Classifier

The Trade-off Space

Once I had a working machine learning model for nest classification, I started to build out the application using the Flask web framework written in Python. After spending a few days of writing code for the application and incorporating the trained random forest model, I had enough to test out the basic functionality. I could finally run the application locally to call the Bird API and classify scooter’s into nests in real-time! There was one huge problem, though. It took more than seven minutes to generate the predictions and populate in the application. That just wasn’t going to cut it.

The question remained: will this model deliver in a production grade environment with the goal of making real-time classifications? This is a key trade-off in production grade machine learning applications where on one end of the spectrum we’re optimizing for model performance and on the other end we’re optimizing for low latency application performance.

As I continued to test out the application’s performance, I still faced the challenge of relying on so many APIs for real-time feature generation. Due to rate-limiting constraints and daily request limits across so many external APIs, the current machine learning classifier was not feasible to incorporate into the final application.

Run-Time Compliant Application Model

After going back to the drawing board, I trained a random forest model that relied primarily on scooter-specific features which were generated directly from the Bird API.

Through a process called vectorization, I was able to transform the geolocation distance calculations utilizing NumPy arrays which enabled batch operations on the data without writing any “for” loops. The distance calculations were applied simultaneously on the entire array of geolocations instead of looping through each individual element. The vectorization implementation optimized real-time feature engineering for distance related calculations which improved the application response time by a factor of ten.

Feature Importance for the Run-time Compliant Random Forest Classifier

Feature Importance for the Run-time Compliant Random Forest Classifier

This random forest model generalized well on test-data with an AUC score of 0.95 and an accuracy rate of 91%. The model retained its prediction accuracy compared to the former feature-rich model, but it gained 60x in application performance. This was a necessary trade-off for building a functional application with real-time prediction capabilities.

Geospatial Clustering

Now that I finally had a working machine learning model for classifying nests in a production grade environment, I could generate new nest locations for the non-nest scooters. The goal was to generate geospatial clusters based on the number of non-nest scooters in a given location.

The k-means algorithm is likely the most common clustering algorithm. However, k-means is not an optimal solution for widespread geolocation data because it minimizes variance, not geodetic distance. This can create suboptimal clustering from distortion in distance calculations at latitudes far from the equator. With this in mind, I initially set out to use the DBSCAN algorithm which clusters spatial data based on two parameters: a minimum cluster size and a physical distance from each point. There were a few issues that prevented me from moving forward with the DBSCAN algorithm.

  1. The DBSCAN algorithm does not allow for specifying the number of clusters, which was problematic as the goal was to generate a number of clusters as a function of non-nest scooters.
  2. I was unable to hone in on an optimal physical distance parameter that would dynamically change based on the Bird API data. This led to suboptimal nest locations due to a distortion in how the physical distance point was used in clustering. For example, Santa Monica, where there are ~15,000 scooters, has a higher concentration of scooters in a given area whereas Brookline, MA has a sparser set of scooter locations.

An example of how sparse scooter locations vs. highly concentrated scooter locations for a given Bird API call can create cluster distortion based on a static physical distance parameter in the DBSCAN algorithm. Left:Bird scooters in Brookline, MA. Right:Bird scooters in Santa Monica, CA.

An example of how sparse scooter locations vs. highly concentrated scooter locations for a given Bird API call can create cluster distortion based on a static physical distance parameter in the DBSCAN algorithm. Left:Bird scooters in Brookline, MA. Right:Bird scooters in Santa Monica, CA.

Given the granularity of geolocation scooter data I was working with, geospatial distortion was not an issue and the k-means algorithm would work well for generating clusters. Additionally, the k-means algorithm parameters allowed for dynamically customizing the number of clusters based on the number of non-nest scooters in a given location.

Once clusters were formed with the k-means algorithm, I derived a centroid from all of the observations within a given cluster. In this case, the centroids are the mean latitude and mean longitude for the scooters within a given cluster. The centroids coordinates are then projected as the new nest recommendations.

NestGenerator showcasing non-nest scooters and new nest recommendations utilizing the K-Means algorithm

NestGenerator showcasing non-nest scooters and new nest recommendations utilizing the K-Means algorithm.

NestGenerator Application

After wrapping up the machine learning components, I shifted to building out the remaining functionality of the application. The final iteration of the application is deployed to Heroku’s cloud platform.

In the NestGenerator app, a user specifies a location of their choosing. This will then call the Bird API for scooters within that given location and generate all of the model features for predicting nest classification using the trained random forest model. This forms the foundation for map filtering based on nest classification. In the app, a user has the ability to filter the map based on nest classification.

Drop-Down Map View filtering based on Nest Classification

Drop-Down Map View filtering based on Nest Classification

Nearest Generated Nest

To see the generated nest recommendations, a user selects the “Current Non-Nest Scooters & Predicted Nest Locations” filter which will then populate the application with these nest locations. Based on the user’s specified search location, a table is provided with the proximity of the five closest nests and an address of the Nest location to help inform a Bird charger in their decision-making.

NestGenerator web-layout with nest addresses and proximity to nearest generated nests

NestGenerator web-layout with nest addresses and proximity to nearest generated nests

Conclusion

By accurately predicting nest classification and clustering non-nest scooters, NestGenerator provides an automated recommendation engine for new nest locations. For Bird, this application can help power their nest location generation that runs within their Android and iOS applications. NestGenerator also provides real-time strategic insight for Bird chargers who are enticed to optimize their scooter collection and drop-off route based on scooters and nest locations in their area.

Code

The code for this project can be found on my GitHub

Comments or Questions? Please email me an E-Mail!

 

Allgemeines über Geodaten

Dieser Artikel ist der Auftakt in einer Artikelserie zum Thema “Geodatenanalyse”.

Von den vielen Arten an Datensätzen, die öffentlich im Internet verfügbar sind, bin ich in letzter Zeit vermehrt über eine besonders interessante Gruppe gestolpert, die sich gleich für mehrere Zwecke nutzen lassen: Geodaten.

Gerade in wirtschaftlicher Hinsicht bieten sich eine ganze Reihe von Anwendungsfällen, bei denen Geodaten helfen können, Einblicke in Tatsachen zu erlangen, die ohne nicht möglich wären. Der wohl bekannteste Fall hierfür ist vermutlich die einfache Navigation zwischen zwei Punkten, die jeder kennt, der bereits ein Navigationssystem genutzt oder sich eine Route von Google Maps berechnen lassen hat.
Hiermit können nicht nur Fragen nach dem schnellsten oder Energie einsparensten (und damit gleichermaßen auch witschaftlichsten) Weg z. B. von Berlin nach Hamburg beantwortet werden, sondern auch die bestmögliche Lösung für Ausnahmesituationen wie Stau oder Vollsperrungen berechnet werden (ja, Stau ist, zumindest in der Theorie immer noch eine “Ausnahmesituation” ;-)).
Neben dieser beliebten Art Geodaten zu nutzen, gibt es eine ganze Reihe weiterer Situationen in denen deren Nutzung hilfreich bis essentiell sein kann. Als Beispiel sei hier der Einzugsbereich von in Konkurrenz stehenden Einheiten, wie z. B. Supermärkten genannt. Ohne an dieser Stelle statistische Nachweise vorlegen zu können, kaufen (zumindest meiner persönlichen Beobachtung nach) die meisten Menschen fast immer bei dem Supermarkt ein, der am bequemsten zu erreichen ist und dies ist in der Regel der am nächsten gelegene. Besitzt man nun eine Datenbank mit der Information, wo welcher Supermarkt bzw. welche Supermarktkette liegt, kann man mit so genannten Voronidiagrammen recht einfach den jeweiligen Einzugsbereich der jeweiligen Supermärkte berechnen.
Entsprechende Karten können auch von beliebigen anderen Entitäten mit fester geographischer Position gezeichnet werden: Geldautomaten, Funkmasten, öffentlicher Nahverkehr, …

Ein anderes Beispiel, das für die Datenauswertung interessant ist, ist die kartographische Auswertung von Postleitzahlen. Diese sind in fast jedem Datensatz zu Kunden, Lieferanten, ect. vorhanden, bilden jedoch weder eine ordinale, noch eine sinnvolle kategorische Größe, da es viele tausend verschiedene gibt. Zudem ist auch eine einfache Gruppierung in gröbere Kategorien wie beispielsweise Postleitzahlen des Schemas 1xxxx oft kaum sinnvoll, da diese in aller Regel kein sinnvolles Mapping auf z. B. politische Gebiete – wie beispielsweise Bundesländer – zulassen. Ein Ausweg aus diesem Dilemma ist eine einfache kartographische Übersicht, welche die einzelnen Postleitzahlengebiete in einer Farbskala zeigt.

Im gezeigten Beispiel ist die Bevölkerungsdichte Deutschlands als Karte zu sehen. Hiermit wird schnell und übersichtlich deutlich, wo in Deutschland die Bevölkerung lokalisiert ist. Ähnliche Karten können beispielsweise erstellt werden, um Fragen wie “Wie ist meine Kundschaft verteilt?” oder “Wo hat die Werbekampange XYZ besonders gut funktioniert?” zu beantworten. Bezieht man weitere Daten wie die absolute Bevölkerung oder die Bevölkerungsdichte mit ein, können auch Antworten auf Fragen wie “Welchen Anteil der Bevölkerung habe ich bereits erreicht und wo ist noch nicht genutztes Potential?” oder “Ist mein Produkt eher in städtischen oder ländlichen Gebieten gefragt?” einfach und schnell gefunden werden.
Ohne die entsprechende geographische Zusatzinformation bleiben insbesondere Postleitzahlen leider oft als “nicht sinnvoll auswertbar” bei der Datenauswertung links liegen.
Eine ganz andere Art von Vorteil der Geodaten ist der educational point of view:
  • Wer erst anfängt, sich mit Datenbanken zu beschäftigen, findet mit Straßen, Postleitzahlen und Ländern einen deutlich einfacheren und vor allem besser verständlichen Zugang zu SQL als mit abstrakten Größen und Nummern wie ProductID, CustomerID und AdressID. Zudem lassen sich Geodaten nebenbei bemerkt mittels so genannter GeoInformationSystems (*gis-Programme), erstaunlich einfach und ansprechend plotten.
  • Wer sich mit SQL bereits ein wenig auskennt, kann mit den (beispielsweise von Spatialite oder PostGIS) bereitgestellten SQL-Funktionen eine ganze Menge über Datenbanken sowie deren Möglichkeiten – aber auch über deren Grenzen – erfahren.
  • Für wen relationale Datenbanken sowie deren Funktionen schon lange nichts Neues mehr darstellen, kann sich hier (selbst mit dem eigenen Notebook) erstaunlich einfach in das Thema “Bug Data” einarbeiten, da die Menge an öffentlich vorhandenen Geodaten z.B. des OpenStreetMaps-Projektes selbst in optimal gepackten Format vielen Dutzend GB entsprechen. Gerade die Möglichkeit, die viele *gis-Programme wie beispielsweise QGIS bieten, nämlich Straßen-, Schienen- und Stromnetze “on-the-fly” zu plotten, macht die Bedeutung von richtig oder falsch gesetzten Indices in verschiedenen Datenbanken allein anhand der Geschwindigkeit mit der sich die Plots aufbauen sehr eindrucksvoll deutlich.
Um an Datensätze zu kommen, reicht es in der Regel Google mit den entsprechenden Schlagworten zu versorgen.
Neben – um einen Vergleich zu nutzen – dem Brockhaus der Karten GoogleMaps gibt es beispielsweise mit dem OpenStreetMaps-Projekt einen freien Geodatensatz, welcher in diesem Kontext etwa als das Wikipedia der Karten zu verstehen ist.
Hier findet man zum Beispiel Daten wie Straßen-, Schienen- oder dem Stromnetz, aber auch die im obigen Voronidiagramm eingezeichneten Gebäude und Supermärkte stammen aus diesem Datensatz. Hiermit lassen sich recht einfach just for fun interessante Dinge herausfinden, wie z. B., dass es in Deutschland ca. 28 Mio Gebäude gibt (ein SQL-Einzeiler), dass der Berliner Osten auch ca. 30 Jahre nach der Wende noch immer vorwiegend von der Tram versorgt wird, während im Westen hauptsächlich die U-Bahn fährt. Oder über welche Trassen der in der Nordsee von Windkraftanlagen erzeugte Strom auf das Festland kommt und von da aus weiter verteilt wird.
Eher grundlegende aber deswegen nicht weniger nützliche Datensätze lassen sich unter dem Stichwort “natural earth” finden. Hier sind Daten wie globale Küstenlinien, mittels Echolot ausgemessene Meerestiefen, aber auch von Menschen geschaffene Dinge wie Landesgrenzen und Städte sehr übersichtlich zu finden.
Im Grunde sind der Vorstellung aber keinerlei Grenzen gesetzt und fast alle denkbaren geographischen Fakten können, manchmal sogar live via Sattelit, mitverfolgt werden. So kann man sich beispielsweise neben aktueller Wolkenbedekung, Regenradar und globaler Oberflächentemperatur des Planeten auch das Abschmelzen der Polkappen seit 1970 ansehen (NSIDC) oder sich live die Blitzeinschläge auf dem gesamten Planeten anschauen – mit Vorhersage darüber, wann und wo der Donner zu hören ist (das funktioniert wirklich! Beispielsweise auf lightningmaps).
Kurzum Geodaten sind neben ihrer wirtschaftlichen Relevanz – vor allem für die Logistik – auch für angehende Data Scientists sehr aufschlussreich und ein wunderbares Spielzeug, mit dem man sich lange beschäftigen und eine Menge interessanter Dinge herausfinden kann.

Kiano – visuelle Exploration mit Deep Learning

Kiano – eine iOS-App zur visuellen Exploration und Suche der eigenen Fotos.

Menschen haben kein Problem, komplexe Bilder zu verstehen, es fällt ihnen aber schwer, gezielt Bilder in großen Bildersammlungen (wieder) zu finden. Da die Anzahl von Bildern, insbesondere auch auf Smartphones zusehends zunimmt – mehrere tausend Bilder pro Gerät sind keine Seltenheit, wird die Suche nach bestimmten Bildern immer schwieriger. Ist bei einem gesuchten Foto dessen Aufnahmedatum unbekannt, so kann es sehr lange dauern, bis es gefunden ist. Werden dem Nutzer zu viele Bilder auf einmal präsentiert, so geht der Überblick schnell verloren. Aus diesem Grund besteht eine typische Bildsuche heutzutage meist im endlosen Scrollen über viele Bildschirmseiten mit langen Bilderlisten.

Dieser Artikel stellt das Prinzip und die Funktionsweise der neuen iOS-App “Kiano” vor, die es Nutzern ermöglicht, alle ihre Bilder explorativ mittels visuellem Browsen zu erkunden. Der Name “Kiano” steht hierbei für “Keep Images Arranged & Neatly Organized”. Mit der App ist es außerdem möglich, zu einem Beispielbild gezielt nach ähnlichen Fotos auf dem Gerät zu suchen.

Um Bilder visuell durchsuch- und sortierbar zu machen, werden sogenannte Merkmalsvektoren bzw. Featurevektoren verwendet, die Aussehen und Inhalt von Bildern kompakt repräsentieren können. Zu einem Bild lassen sich ähnliche Bilder finden, indem die Bilder bestimmt werden, deren Featurevektoren eine geringe Distanz zum Featurevektor des Suchbildes haben.

Werden Bilder zweidimensional so angeordnet, dass die Featurevektoren benachbarter Bilder sehr ähnlich sind, so erhält man eine visuell sortierte Bilderlandkarte. Bei einer visuell sortierten Anordnung der Bilder fällt es Menschen deutlich leichter, mehr Bilder gleichzeitig zu erfassen, als dies im unsortierten Fall möglich wäre. Durch die graduelle Veränderung der Bildinhalte wird es möglich, über diese Karte visuell zu navigieren.

Generierung von Featurevektoren zur Bildbeschreibung

Convolutional Neural Networks (CNNs) sind nicht nur in der Lage, Bilder mit hoher Genauigkeit zu klassifizieren, d.h. zu erkennen, welches Objekt – entsprechend einer Menge von gelernten Objektkategorien auf einem Bild zu sehen ist, die Aktivierungen der Netzwerkschichten lassen sich auch als universelle Featurevektoren zur Bildbeschreibung nutzen. Während die vorderen Netzwerkschichten von CNNs einfache visuelle Bildmerkmale wie Farben und einfache Muster detektieren, repräsentieren die Ausgangsschichten des Netzwerks die semantischen Informationen bezüglich der gelernten Objektkategorien. Die Zwischenschichten des Netzwerks sind weniger von den Objektkategorien abhängig und können somit als generelle abstrakte Repräsentationen des Inhalts der Bilder angesehen werden. Hierbei ist es möglich, bereits fertig trainierte Klassifikationsnetzwerke für die Featureextraktion wiederzuverwenden. In der Visual Computing Gruppe der HTW Berlin wurden umfangreiche Evaluierungen durchgeführt, um zu bestimmen, welche Netzwerkschichten von welchen CNNs mit welchen zusätzlichen Transformationen zu verwenden sind, um aus Netzwerkaktivierungen Feature-Vektoren zu erzeugen, die sehr gut für die Suche nach beliebigen Bildern geeignet sind.

Beste Ergebnisse hinsichtlich der Suchgenauigkeit (der Mean Average Precision) wurden mit einem Deep Residual Learning Network (ResNet-200) erzielt. Die 2048 Aktivierungen vor dem vollvernetzten letzten Layer werden als initiale Featurevektoren verwendet, wobei sich die Suchgenauigkeit durch eine L1-Normierung, gefolgt von einer PCA-Transformation (Principal Component Analysis) sogar noch verbessern lässt. Hierdurch ist es möglich, die Featurevektoren auf eine Größe von nur 64 Bytes zu reduzieren. Leider ist die rechnerische Komplexität der Bestimmung dieser hochwertigen Featurevektoren zu groß, um sie auf mobilen Geräten verwenden zu können. Eine gute Alternative stellen die Mobilenets dar, die sich durch eine erheblich reduzierte Komplexität auszeichnen. Als Kompromiss zwischen Klassifikationsgenauigkeit und Komplexität wurde für die Kiano-App das Mobilenet_v2_0.5_128 verwendet. Die mit diesem Netzwerk bestimmten Featurevektoren wurden ebenfalls auf eine Größe von 64 Bytes reduziert.

Die aus CNNs erzeugten Featurevektoren sind gut für die Suche nach Bildern mit ähnlichem Inhalt geeignet. Für die Suche nach Bilder, mit ähnlichen visuellen Eigenschaften (z.B. die auftretenden Farben oder deren örtlichen Verteilung) sind diese Featurevektoren nur bedingt geeignet. Hierfür eignen sich klassische sogenannte “Low-Level”-Featurevektoren besser. Da für eine ansprechende und leicht erfassbare Bildsortierung auch eine Übereinstimmung dieser visuellen Bildattribute wichtig ist, kommt bei Kiano ein weiterer Featurevektor zum Einsatz, mit dem sich diese “primitiven” visuellen Bildattribute beschreiben lassen. Dieser Featurevektor hat eine Größe von 50 Bytes. Bei Kiano kann der Nutzer in den Einstellungen wählen, ob bei der visuellen Sortierung und Bildsuche größerer Wert auf den Bildinhalt oder die visuelle Erscheinung eines Bildes gelegt werden soll.

Visuelle Bildsortierung

Werden Bilder entsprechend ihrer Ähnlichkeiten sortiert angeordnet, so können mehrere hundert Bilder gleichzeitig wahrgenommen bzw. erfasst werden. Dies hilft, Regionen interessanter Bildern leichter zu erkennen und gesuchte Bilder schneller zu entdecken. Die Möglichkeit, viele Bilder gleichzeitig präsentieren zu können, ist neben Bildverwaltungssystemen besonders auch für E-Commerce-Anwendungen interessant.

Herkömmliche Dimensionsreduktionsverfahren, die hochdimensionale Featurevektoren auf zwei Dimensionen projizieren, sind für die Bildsortierung ungeeignet, da sie die Bilder so anordnen, dass Lücken und Bildüberlappungen entstehen. Sollen Bilder sortiert auf einem dichten regelmäßigen 2D-Raster angeordnet werden, kommen als Verfahren nur selbstorganisierende Karten oder selbstsortierende Karten in Frage.

Eine selbstorganisierende Karte (Self Organizing Map / SOM) ist ein künstliches neuronales Netzwerk, das durch unbeaufsichtigtes Lernen trainiert wird, um eine niedrigdimensionale, diskrete Darstellung der Daten des Eingangsraums als sogenannte Karte (Map) zu erzeugen. Im Gegensatz zu anderen künstlichen neuronalen Netzen, werden SOMs nicht durch Fehlerkorrektur, sondern durch ein Wettbewerbsverfahren trainiert, wobei eine Nachbarschaftsfunktion verwendet wird, um die lokalen Ähnlichkeiten der Eingangsdaten zu bewahren.

Eine selbstorganisierende Karte besteht aus Knoten, denen einerseits ein Gewichtsvektor der gleichen Dimensionalität wie die Eingangsdaten und anderseits eine Position auf der 2D-Karte zugeordnet sind. Die SOM-Knoten sind als zweidimensionales Rechteckgitter angeordnet. Das vom der SOM erzeugte Mapping ist diskret, da jeder Eingangsvektor einem bestimmten Knoten zugeordnet wird. Zu Beginn werden die Gewichtsvektoren aller Knoten mit Zufallswerten initialisiert. Wird ein hochdimensionaler Eingangsvektor in das Netz eingespeist, so wird dessen euklidischer Abstand zu allen Gewichtsvektoren berechnet. Der Knoten, dessen Gewichtsvektor dem Eingangsvektor am ähnlichsten ist, wird als Best Matching Unit (BMU) bezeichnet. Die Gewichte des BMU und seiner auf der Karte örtlich benachbarten Knoten werden an den Eingangsvektor angepasst. Dieser Vorgang wird iterativ wiederholt. Das Ausmaß dieser Anpassung nimmt im Laufe der Iterationen und der örtlichen Entfernung zum BMU-Knoten ab.

Um SOMs an die Bildsortierung anzupassen, sind zwei Modifikationen notwendig. Jeder Knoten darf nicht von mehr als einem Featurevektor (der ein Bild repräsentiert) ausgewählt werden. Eine Mehrfachauswahl würde zu einer Überlappung der Bilder führen. Aus diesem Grund muss die Anzahl der SOM-Knoten mindestens so groß wie die Anzahl der Bilder sein. Eine sinnvolle Erweiterung einer SOM verwendet ein Gitter, bei dem gegenüberliegende Kanten verbunden sind. Werden diese Torus-förmigen Karten für große SOMs verwendet, kann der Eindruck einer endlosen Karte erzeugt werden, wie es in Kiano umgesetzt ist. Ein Problem der SOMs ist ihre hohe rechnerische Komplexität, die quadratisch mit der Anzahl der zu sortierenden Bilder wächst, wodurch die maximale Anzahl an zu sortierenden Bildern beschränkt wird. Eine Lösung stellt eine selbstsortierende Karte (Self Sorting Map / SSM) dar, deren Komplexität nur n log(n) beträgt.

Selbstsortierende Karten beginnen mit einer zufälligen Positionierung der Bilder auf der Karte. Diese Karte wird dann in 4×4-Blöcke aufgeteilt und für jeden Block wird der Mittelwert der zugehörigen Featurevektoren bestimmt. Als nächstes werden aus 2×2 benachbarten Blöcken jeweils vier korrespondierende Bild-Featurevektoren untersucht und ihre zugehörigen Bilder gegebenenfalls getauscht. Aus den 4! = 24 Anordnungsmöglichkeiten wird diejenige gewählt, die die Summe der quadrierten Differenzen zwischen den jeweiligen Featurevektoren und den Featuremittelwerten der Blöcke minimiert. Nach mehreren Iterationen wird jeder Block in vier kleinere Blöcke halber Breite und Höhe aufgeteilt und wiederum in der beschriebenen Weise überprüft, wie die Bildpositionen dieser kleineren Blöcke getauscht werden sollten. Dieser Vorgang wird solange wiederholt, bis die Blockgröße auf 1×1 Bild reduziert ist.

In der Visual-Computing Gruppe der HTW Berlin wurde untersucht, wie die Sortierqualität des SSM-Algorithmus verbessert werden kann. Anstatt die Mittelwerte der Featurevektoren als konstanten Durchschnittsvektor für den gesamten Block zu berechnen, verwenden wir gleitende Tiefpassfilter, die sich effizient mittels Integralbildern berechnen lassen. Hierdurch entstehen weichere Übergänge auf der sortierten Bilderkarte. Weiterhin wird die Blockgröße nicht für mehrere Iterationen konstant gehalten, sondern kontinuierlich zusammen mit dem Radius des Filterkernels reduziert. Durch die Verwendung von optimierten Algorithmen von “Linear Assignment” Algorithmen wird es weiterhin möglich, den optimalen Positionstausch nicht nur für jeweils vier Featurevektoren bzw. Bildern sondern für eine deutlich größere Anzahl zu überprüfen. All diese Maßnahmen führen zu einer deutlich verbesserten Sortierungsqualität bei gleicher Komplexität.

Effiziente Umsetzung für iOS

Wie so oft, liegen die softwaretechnischen Herausforderungen an ganz anderen Stellen, als man zunächst vermutet. Für eine effiziente Implementierung der zuvor beschriebenen Algorithmen, insbesondere der SSM, stellte es sich heraus, dass die Programmiersprache Swift, in der iOS Apps normaler Weise entwickelt werden, erheblich mehr Rechenzeit benötigt, als eine Umsetzung in der Sprache C. Im Zuge der stetigen Weiterentwicklung von Swift und dessen Compiler mag sich die Lücke zu C zwar immer weiter schließen, zum Zeitpunkt der Umsetzung war die Implementierung in C aber um einen Faktor vier schneller als in Swift. Hierbei liegt die Vermutung nahe, dass der Zugriff auf und das Umsortieren von Featurevektoren als native C-Arrays deutlich effektiver passiert, als bei der Verwendung von Swift-Arrays. Da Swift-Arrays Value-Type sind, kommt es in Swift vermutlich zu unnötigen Kopieroperationen der Fließkommazahlen in den einzelnen Featurevektoren.

Die Berechnung des Mobilenet-Anteils der Featurevektoren konnte sehr komfortabel mit Apples CoreML Machine Learning Framework umgesetzt werden. Hierbei ist zu beachten, dass es sich wie oben beschrieben, nicht um eine Klassifikation handelt, sondern um das Abgreifen der Aktivierungen einer tieferen Schicht. Für Klassifikationen findet man praktisch sofort nutzbare Beispiele, für den Zugriff auf die Aktivierungen waren jedoch Anpassungen notwendig, die bei der Portierung eines vortrainierten Mobilenet nach CoreML vorgenommen wurden. Das stellte sich als erheblich einfacher heraus, als der Versuch, auf die tieferen Schichten eines Klassifizierungsnetzes in CoreML zuzugreifen.

Für die Verwaltung der Bilder, ihrer Featurevektoren und ihrer Position in der sortieren Karte wird in Kiano eine eigene Datenstruktur verwendet, die es zu persistieren gilt. Es ist dem Nutzer ja nicht zuzumuten, bei jedem Start der App auf die Berechnung aller Featurevektoren zu warten. Die Strategie ist es hierbei, bereits bekannte Bilder zu identifizieren und deren Features nur dann neu zu berechnen, falls sich das Bild verändert hat. Die über Appels Photos Framework zur Verfügung gestellten local Identifier identifizieren dabei die Bilder. Veränderungen werden über das Modifikationsdatum eines Bildes detektiert. Die größte Herausforderung ist hierbei das Zeichnen der Karte. Die Benutzerinteraktion soll schnell und flüssig erscheinen, auf Animationen wie das Nachlaufen der Karte beim Verschieben möchte man nicht verzichten. Die Umsetzung geschieht hierbei nicht in OpenGL ES, welches ab iOS 12 ohnehin als deprecated bezeichnet wird. Auf der anderen Seite wird aber auch nicht der „Standardweg“ des Überschreibens der draw-Methode einer Ableitung von UIView gewählt. Letztes führt bekanntlich zu Performanceeinbußen. Insbesondere deshalb, weil das System sehr oft Backing-Images der Ansichten erstellt. Um die Kontrolle über das Neuzeichnen zu behalten, wird in Kiano ein eigenes Backing-Image implementiert, das auf Ebene des Core Animation Frameworks dem View als Layer zugweisen wird. Diesem Layer kann dann sehr komfortabel eine 3D-Transformation zugewiesen werden und man profitiert von der GPU-Beschleunigung, ohne OpenGL ES direkt verwenden zu müssen.

 

Trotz der Verwendung eines Core Animation Layers ist das Zeichnen der Karte immer noch sehr zeitaufwendig. Das liegt an der Tatsache, dass je nach Zoomstufe tausende von Bildern darzustellen sind, die alle über das Photos Framework angefordert werden müssen. Das Nadelöhr ist dann weniger das Zeichnen, als die Zeit, die vergeht, bis einem das Bild zur Verfügung gestellt wird. Diese Vorgänge sind praktisch alle nebenläufig. Zur Erinnerung: Ein Foto kann in der iCloud liegen und zum Zeitpunkt der Anfrage noch gar nicht (oder noch nicht in geeigneter Auflösung) heruntergeladen sein. Netzwerkbedingt gibt es keine Vorhersage, wann oder ob überhaupt das Bild zur Verfügung gestellt wird. In Kiano werden zum einen Bilder in sehr kleiner Auflösung gecached, zum anderen wird beim Navigieren auf der Karte im Hintergrund ein neues Kartenteil als Backing-Image vorbereitet, das dem Nutzer nach Fertigstellung angezeigt wird. Die vorberechneten Kartenteile sind dabei drei Mal so breit und drei Mal so hoch wie das Display, so dass man diese „Hintergrundaktivität“ beim Verschieben der Karte in der Regel nicht bemerkt. Nur wenn die Bewegung zu schnell wird oder die Bilder zu langsam „geliefert“ werden, erkennt man schwarze Flächen, die sich dann verzögert mit Bildern füllen.

Vergleichbares passiert beim Hineinzoomen in die Karte. Der Nutzer sieht zunächst eine vergrößerte und damit unscharfe Version des aktuellen Kartenteils, während im Hintergrund ein Kartenteil in höherer Auflösung und mit weniger Bildern vorbereitet wird. In der Summe geht Kiano hier einen Kompromiss ein. Die Pixeldichte der Geräte würde eine schärfere Darstellung der Bilder auf der Karte erlauben. Allerdings müssten dann die Bilder in so höher Auflösung angefordert werden, dass eine flüssige Kartennavigation nicht mehr möglich wäre. So sieht der Nutzer in der Regel eine Karte mit Bildern in halber Auflösung gemessen an den physikalischen Pixeln seines Displays.

Ein anfangs unterschätzter Arbeitsaufwand bei der Umsetzung von Kiano liegt darin begründet, dass sich die Photo Library des Nutzers jederzeit während der Benutzung der App verändern kann. Bilder können durch Synchronisationen mit der iCloud oder mit iTunes verschwinden, sich in andere Alben bewegen, oder neue können auftauchen. Der Nutzer kann Bildschirmfotos machen. Das Photos Framework stellt komfortable Benachrichtigungen für solche Events zur Verfügung. Der Implementierung obliegt es dabei aber herauszubekommen, ob die Karte neu zu sortieren ist oder nicht, ob das gerade anzeigte Bild überhaupt noch existiert und was zu tun ist, wenn es verschwunden ist.

Zusammenfassend kann man feststellen, dass natürlich die Umsetzung der Algorithmen und die Darstellung dessen auf einer Karte zu den spannendsten Teilen der Arbeiten an Kiano zählen, dass aber der Umgang mit einer sich dynamisch ändernden Datenbasis nicht unterschätzt werden sollte.

Autoren

Prof. Dr. Klaus JungProf. Dr. Klaus Jung studierte Physik an der TU Berlin, wo er im Bereich der Mathematischen Physik promovierte. Bis 2008 arbeitete er als Leiter F&E bei der Firma LuraTech im Bereich der Dokumentenverarbeitung und Langzeitarchivierung. In der JPEG-Gruppe leitete er die deutsche Delegation bei der Standardisierung von JPEG2000. Seit 2008 ist er Professor für Medieninformatik an der HTW Berlin mit dem Schwerpunkt „Visual Computing“.

Prof. Dr. Kai Uwe Barthel

Prof. Dr. Kai Uwe Barthel studierte Elektrotechnik an der TU Berlin, bevor er Assistent am Institut für Nachrichtentechnik wurde und im Bereich Bildkompression promovierte. Seit 2001 ist er Professor der HTW Berlin. Hauptforschungsbereiche sind visuelle Bildsuche und automatisches Bildverstehen. 2009 gründete er die pixolution GmbH www.pixolution.de, ein Unternehmen, das Technologien für die visuelle Bildsuche anbietet.

Applying Data Science Techniques in Python to Evaluate Ionospheric Perturbations from Earthquakes

Multi-GNSS (Galileo, GPS, and GLONASS) Vertical Total Electron Content Estimates: Applying Data Science techniques in Python to Evaluate Ionospheric Perturbations from Earthquakes

1 Introduction

Today, Global Navigation Satellite System (GNSS) observations are routinely used to study the physical processes that occur within the Earth’s upper atmosphere. Due to the experienced satellite signal propagation effects the total electron content (TEC) in the ionosphere can be estimated and the derived Global Ionosphere Maps (GIMs) provide an important contribution to monitoring space weather. While large TEC variations are mainly associated with solar activity, small ionospheric perturbations can also be induced by physical processes such as acoustic, gravity and Rayleigh waves, often generated by large earthquakes.

In this study Ionospheric perturbations caused by four earthquake events have been observed and are subsequently used as case studies in order to validate an in-house software developed using the Python programming language. The Python libraries primarily utlised are Pandas, Scikit-Learn, Matplotlib, SciPy, NumPy, Basemap, and ObsPy. A combination of Machine Learning and Data Analysis techniques have been applied. This in-house software can parse both receiver independent exchange format (RINEX) versions 2 and 3 raw data, with particular emphasis on multi-GNSS observables from GPS, GLONASS and Galileo. BDS (BeiDou) compatibility is to be added in the near future.

Several case studies focus on four recent earthquakes measuring above a moment magnitude (MW) of 7.0 and include: the 11 March 2011 MW 9.1 Tohoku, Japan, earthquake that also generated a tsunami; the 17 November 2013 MW 7.8 South Scotia Ridge Transform (SSRT), Scotia Sea earthquake; the 19 August 2016 MW 7.4 North Scotia Ridge Transform (NSRT) earthquake; and the 13 November 2016 MW 7.8 Kaikoura, New Zealand, earthquake.

Ionospheric disturbances generated by all four earthquakes have been observed by looking at the estimated vertical TEC (VTEC) and residual VTEC values. The results generated from these case studies are similar to those of published studies and validate the integrity of the in-house software.

2 Data Cleaning and Data Processing Methodology

Determining the absolute VTEC values are useful in order to understand the background ionospheric conditions when looking at the TEC perturbations, however small-scale variations in electron density are of primary interest. Quality checking processed GNSS data, applying carrier phase leveling to the measurements, and comparing the TEC perturbations with a polynomial fit creating residual plots are discussed in this section.

Time delay and phase advance observables can be measured from dual-frequency GNSS receivers to produce TEC data. Using data retrieved from the Center of Orbit Determination in Europe (CODE) site (ftp://ftp.unibe.ch/aiub/CODE), the differential code biases are subtracted from the ionospheric observables.

2.1 Determining VTEC: Thin Shell Mapping Function

The ionospheric shell height, H, used in ionosphere modeling has been open to debate for many years and typically ranges from 300 – 400 km, which corresponds to the maximum electron density within the ionosphere. The mapping function compensates for the increased path length traversed by the signal within the ionosphere. Figure 1 demonstrates the impact of varying the IPP height on the TEC values.

Figure 1 Impact on TEC values from varying IPP heights. The height of the thin shell, H, is increased in 50km increments from 300 to 500 km.

2.2 Phase Smoothing

For dual-frequency GNSS users TEC values can be retrieved with the use of dual-frequency measurements by applying calculations. Calculation of TEC for pseudorange measurements in practice produces a noisy outcome and so the relative phase delay between two carrier frequencies – which produces a more precise representation of TEC fluctuations – is preferred. To circumvent the effect of pseudorange noise on TEC data, GNSS pseudorange measurements can be smoothed by carrier phase measurements, with the use of the carrier phase smoothing technique, which is often referred to as carrier phase leveling.

Figure 2 Phase smoothed code differential delay

2.3 Residual Determination

For the purpose of this study the monitoring of small-scale variations in ionospheric electron density from the ionospheric observables are of particular interest. Longer period variations can be associated with diurnal alterations, and changes in the receiver- satellite elevation angles. In order to remove these longer period variations in the TEC time series as well as to monitor more closely the small-scale variations in ionospheric electron density, a higher-order polynomial is fitted to the TEC time series. This higher-order polynomial fit is then subtracted from the observed TEC values resulting in the residuals. The variation of TEC due to the TID perturbation are thus represented by the residuals. For this report the polynomial order applied was typically greater than 4, and was chosen to emulate the nature of the arc for that particular time series. The order number selected is dependent on the nature of arcs displayed upon calculating the VTEC values after an initial inspection of the VTEC plots.

3 Results

3.1 Tohoku Earthquake

For this particular report, the sampled data focused on what was retrieved from the IGS station, MIZU, located at Mizusawa, Japan. The MIZU site is 39N 08′ 06.61″ and 141E 07′ 58.18″. The location of the data collection site, MIZU, and the earthquake epicenter can be seen in Figure 3.

Figure 3 MIZU IGS station and Tohoku earthquake epicenter [generated using the Python library, Basemap]

Figure 4 displays the ionospheric delay in terms of vertical TEC (VTEC), in units of TECU (1 TECU = 1016 el m-2). The plot is split into two smaller subplots, the upper section displaying the ionospheric delay (VTEC) in units of TECU, the lower displaying the residuals. The vertical grey-dashed lined corresponds to the epoch of the earthquake at 05:46:23 UT (2:46:23 PM local time) on March 11 2011. In the upper section of the plot, the blue line corresponds to the absolute VTEC value calculated from the observations, in this case L1 and L2 on GPS, whereby the carrier phase leveling technique was applied to the data set. The VTEC values are mapped from the STEC values which are calculated from the LOS between MIZU and the GPS satellite PRN18 (on Figure 4 denoted G18). For this particular data set as seen in Figure 4, a polynomial fit of  five degrees was applied, which corresponds to the red-dashed line. As an alternative to polynomial fitting, band-pass filtering can be employed when TEC perturbations are desired. However for the scope of this report polynomial fitting to the time series of TEC data was the only method used. In the lower section of Figure 4 the residuals are plotted. The residuals are simply the phase smoothed delay values (the blue line) minus the polynomial fit line (the red-dashed line). All ionosphere delay plots follow the same layout pattern and all time data is represented in UT (UT = GPS – 15 leap seconds, whereby 15 leap seconds correspond to the amount of leap seconds at the time of the seismic event). The time series shown for the ionosphere delay plots are given in terms of decimal of the hour, so that the format follows hh.hh.

Figure 4 VTEC and residual plot for G18 at MIZU on March 11 2011

3.2 South Georgia Earthquake

In the South Georgia Island region located in the North Scotia Ridge Transform (NSRT) plate boundary between the South American and Scotia plates on 19 August 2016, a magnitude of 7.4 MW earthquake struck at 7:32:22 UT. This subsection analyses the data retrieved from KEPA and KRSA. As well as computing the GPS and GLONASS TEC values, four Galileo satellites (E08, E14, E26, E28) are also analysed. Figure 5 demonstrates the TEC perturbations as computed for the Galileo L1 and L5 carrier frequencies.

Figure 5 VTEC and residual plots at KRSA on 19 August 2016. The plots are from the perspective of the GNSS receiver at KRSA, for four Galileo satellites (a) E08; (b) E14; (c) E24; (d) E26. The y-axes and x-axes in all plots do not conform with one another but are adjusted to fit the data. The y-axes for the residual section of each plot is consistent with one another.

Figure 6 Geometry of the Galileo (E08, E14, E24 and E26) satellites’ projected ground track whereby the IPP is set to 300km altitude. The orange lines correspond to tectonic plate boundaries.

4 Conclusion

The proximity of the MIZU site and magnitude of the Tohoku event has provided a remarkable – albeit a poignant – opportunity to analyse the ocean-ionospheric coupling aftermath of a deep submarine seismic event. The Tohoku event has also enabled the observation of the origin and nature of the TIDs generated by both a major earthquake and tsunami in close proximity to the epicenter. Further, the Python software developed is more than capable of providing this functionality, by drawing on its mathematical packages, such as NumPy, Pandas, SciPy, and Matplotlib, as well as employing the cartographic toolkit provided from the Basemap package, and finally by utilizing the focal mechanism generation library, Obspy.

Pre-seismic cursors have been investigated in the past and strongly advocated in particular by Kosuke Heki. The topic of pre-seismic ionospheric disturbances remains somewhat controversial. A potential future study area could be the utilization of the Python program – along with algorithmic amendments – to verify the existence of this phenomenon. Such work would heavily involve the use of Scikit-Learn in order to ascertain the existence of any pre-cursors.

Finally, the code developed is still retained privately and as of yet not launched to any particular platform, such as GitHub. More detailed information on this report can be obtained here:

Download as PDF

ID3-Algorithmus: Ein Rechenbeispiel

Dieser Artikel ist Teil 3 von 4 der Artikelserie Maschinelles Lernen mit Entscheidungsbaumverfahren und nun wollen wir einen Entscheidungsbaum aus Daten herleiten, jedoch ohne Programmierung, sondern direkt auf Papier (bzw. HTML :-).

Folgender Datensatz sei gegeben:

Zeile Kundenart Zahlungsgeschwindigkeit Kauffrequenz Herkunft Zahlungsmittel: Rechnung?
 1  Neukunde  niedrig  niedrig  Inland  false
 2  Neukunde  niedrig  niedrig  Ausland  false
 3  Stammkunde  niedrig  niedrig  Inland  true
 4  Normalkunde  mittel  niedrig  Inland  true
 5  Normalkunde  hoch  hoch  Inland  true
 6  Normalkunde  hoch  hoch  Ausland  false
 7  Stammkunde  hoch  hoch  Ausland  true
 8  Neukunde  mittel  niedrig  Inland  false
 9  Neukunde  hoch  hoch  Inland  true
 10  Normalkunde  mittel  hoch  Inland  true
 11  Neukunde  mittel  hoch  Ausland  true
 12  Stammkunde  mittel  niedrig  Ausland  true
 13  Stammkunde  niedrig  hoch  Inland  true
 14  Normalkunde  mittel  niedrig  Ausland  false

Gleich vorweg ein Disclaimer: Der Datensatz ist natürlich überaus klein, ja gerade zu winzig. Dafür würden wir in der Praxis niemals einen Machine Learning Algorithmus einsetzen. Dennoch bleiben wir besser übersichtlich und nachvollziehbar mit diesen 14 Zeilen. Das Lernziel dieser Übung ist es, ein Gefühl für die Erstellung von Entscheidungsbäumen zu erhalten.
Zu beachten ist ferner, dass dieser Datensatz bereits aggregiert ist, denn eigentlich nummerisch abbildbare Daten wurden in Klassen zusammengefasst.

Das Ziel:

Der Datensatz spielt wieder, welchem Kunden (ID) bisher die Zahlung per Rechnung erlaubt und nicht widerrufen wurde. Das Ziel soll sein, eine Vorhersage darüber zu machen zu können, wann ein Kunde per Rechnung zahlen darf und wann nicht (dann per Vorkasse).

Der Algorithmus:

Wir verwenden den ID3-Algorithmus in seiner Reinform. Der ID3-Algorithmus ist der gängigste Algorithmus zum Aufbau datengetriebener Entscheidungsbäume und es gibt mehrere Abwandlungen. Die Vorgehensweise des Algorithmus wird in dem Teil 2 der Artikelserie Entscheidungsbaum-Algorithmus ID3 erläutert.

1. Schritt: Auswählen des Attributes mit dem höchsten Informationsgewinn

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) = H(S) - \sum_{i=1}^n \frac{\bigl|S_i\bigl|}{\bigl|S\bigl|} \cdot H(S_i)

1.1 Gesamt-Entropie des Datensatzes berechnen

Erstmal schauen wir uns die Entropie des gesamten Datensatzes an. Die Entropie bezieht sich dabei auf das gewünschte Klassifikationsergebnis, also ist die Zahlung via Rechnung erlaubt oder nicht? Diese Frage wird entweder mit true oder false beantwortet.

H(S) = - \frac{9}{14} \cdot \log_2(\frac{9}{14}) - \frac{5}{14} \cdot \log_2(\frac{5}{14})  = 0.94

1.2 Berechnung der Informationsgewinne aller Attribute

Berechnen wir nun also die Informationsgewinne über alle Spalten.

Attribut Subset Count(true) Count(false)
Kundenart “Neukunde” 2 3
“Stammkunde” 4 0
“Normalkunde” 3 2

Wir zerlegen den gesamten Datensatz gedanklich in drei Kategorien der Kundenart und berechnen die Entropie bezogen auf das Klassifikationsziel:

H(S_{Neukunde}) = - \frac{2}{5} \cdot \log_2(\frac{2}{5}) - \frac{3}{5} \cdot \log_2(\frac{3}{5})  = 0.97

H(S_{Stammkunde}) = - \frac{4}{4} \cdot \log_2(\frac{4}{4}) - \frac{0}{4} \cdot \log_2(\frac{0}{4})  = 0.00

H(S_{Normalkunde}) = - \frac{3}{5} \cdot \log_2(\frac{3}{5}) - \frac{2}{5} \cdot \log_2(\frac{2}{5})  = 0.97

Zur Erinnerung, der Informationsgewinn (Information Gain) wird wie folgt berechnet:

    \[ IG(S, A_{Kundenart}) =  - \sum_{i=1}^n \frac{\bigl|S_i\bigl|}{\bigl|S\bigl|} \cdot H(S_i) \]

Angewendet auf das Attribut “Kundenart”…

    \[ IG(S, A_{Kundenart}) =  H(S) - \frac{\bigl|S_{Neukunde}\bigl|}{\bigl|S\bigl|} \cdot H(S_{Neukunde}) - \frac{\bigl|S_{Stammkunde}\bigl|}{\bigl|S\bigl|} \cdot H(S_{Stammkunde}) - \frac{\bigl|S_{Normalkunde}\bigl|}{\bigl|S\bigl|} \cdot H(S_{Normalkunde}) \]

… erhalten wir der Formal nach folgenden Informationsgewinn:

    \[ IG(S, A_{Kundenart}) =  0.94 - \frac{5}{14} \cdot 0.97 - \frac{4}{14} \cdot 0.00 - \frac{5}{14} \cdot 0.97 = 0.247 \]

Nun für die weiteren Spalten:

Attribut Subset Count(true) Count(false)
Zahlungsgeschwindigkeit “niedrig” 2 2
“mittel” 4 2
“schnell” 3 1

Entropien für die “Zahlungsgeschwindigkeit”:

H(S_{niedrig}) = - \frac{2}{4} \cdot \log_2(\frac{2}{4}) - \frac{2}{4} \cdot \log_2(\frac{2}{4})  = 1.00

H(S_{mittel}) = - \frac{4}{6} \cdot \log_2(\frac{4}{6}) - \frac{2}{6} \cdot \log_2(\frac{2}{6})  = 0.92

H(S_{schnell}) = - \frac{3}{4} \cdot \log_2(\frac{3}{4}) - \frac{1}{4} \cdot \log_2(\frac{1}{4})  = 0.81

So berechnen wir wieder den Informationsgewinn:

    \[ IG(S, A_{Zahlungsgeschwindigkeit}) =  H(S) - \frac{\bigl|S_{niedrig}\bigl|}{\bigl|S\bigl|} \cdot H(S_{niedrig}) - \frac{\bigl|S_{mittel}\bigl|}{\bigl|S\bigl|} \cdot H(S_{mittel}) - \frac{\bigl|S_{schnell}\bigl|}{\bigl|S\bigl|} \cdot H(S_{schnell}) \]

Einsatzen und ausrechnen:

    \[ IG(S, A_{Zahlungsgeschwindigkeit}) =  0.94 - \frac{4}{14} \cdot 1.00 - \frac{6}{14} \cdot 0.92 - \frac{4}{14} \cdot 0.81 = 0.029 \]

Und nun für die Spalte “Kauffrequenz”:

Attribut Subset Count(true) Count(false)
Kauffrequenz “niedrig” 3 4
“hoch” 6 1

Entropien:

H(S_{niedrig}) = - \frac{3}{7} \cdot \log_2(\frac{3}{7}) - \frac{4}{7} \cdot \log_2(\frac{4}{7})  = 0.99

H(S_{hoch}) = - \frac{6}{7} \cdot \log_2(\frac{6}{7}) - \frac{1}{7} \cdot \log_2(\frac{1}{7})  = 0.59

Informationsgewinn:

    \[ IG(S, A_{Kauffrequenz}) =  H(S) - \frac{\bigl|S_{niedrig}\bigl|}{\bigl|S\bigl|} \cdot H(S_{niedrig}) - \frac{\bigl|S_{hoch}\bigl|}{\bigl|S\bigl|} \cdot H(S_{hoch}) \]

Einsetzen und Ausrechnen:

    \[ IG(S, A_{Kauffrequenz}) =  0.94 - \frac{7}{14} \cdot 1.00 - \frac{7}{14} \cdot 0.59 = 0.150 \]

Und last but not least die Spalte “Herkunft”:

Attribut Subset Count(true) Count(false)
Herkunft “Inland” 6 2
“Ausland” 3 3

Entropien:

H(S_{Inland}) = - \frac{6}{8} \cdot \log_2(\frac{6}{8}) - \frac{2}{8} \cdot \log_2(\frac{2}{8})  = 0.81

H(S_{Ausland}) = - \frac{3}{6} \cdot \log_2(\frac{3}{6}) - \frac{3}{6} \cdot \log_2(\frac{3}{6})  = 1.00

Informationsgewinn:

    \[ IG(S, A_{Herkunft}) =  H(S) - \frac{\bigl|S_{Inland}\bigl|}{\bigl|S\bigl|} \cdot H(S_{Inland}) - \frac{\bigl|S_{Ausland}\bigl|}{\bigl|S\bigl|} \cdot H(S_{Ausland}) \]

Einsetzen und Ausrechnen:

    \[ IG(S, A_{Herkunft}) =  0.94 - \frac{8}{14} \cdot 0.81 - \frac{6}{14} \cdot 1.00 = 0.05 \]

2. Schritt: Anlegen des Wurzel-Knotens

Der Informationsgewinn ist für das Attribut “Kundenart” am größten, daher entscheiden wir uns im Sinne des ID3-Algorithmus für dieses Attribut als Wurzel-Knoten.

3. Schritt: Rekursive Wiederholung (!!!)

Nun stellt sich natürlich die Frage: Wie geht es weiter?

Der Algorithmus kann eigentlich nur eines: Einen Wurzelknoten finden. Diesen Vorgang müssen wir nun nur noch rekursiv wiederholen, und das tun wir wie folgt.

Der Datensatz wurde bereits aufgeteilt in die drei Kundenarten. Für jede Kundenart ergibt sich jeweils ein Subset mit den verbleibenden Attributen. Für alle drei Subsets erstellen wir dann wieder einen Wurzelknoten, so dass ein neuer Ast entsteht.

3.1 Erster Rekursionsschritt

Machen wir also weiter und bestimmen wir das nächste Attribut nach der Kundenart, für die Fälle Kundenart = “Neukunde”:

Zeile Kundenart Zahlungsgeschwindigkeit Kauffrequenz Herkunft Zahlungsmittel: Rechnung?
 1  Neukunde  niedrig  niedrig  Inland  false
 2  Neukunde  niedrig  niedrig  Ausland  false
 8  Neukunde  mittel  niedrig  Inland  false
 9  Neukunde  hoch  hoch  Inland  true
 11  Neukunde  mittel  hoch  Ausland  true

Die Entropie des Gesamtdatensatzes (ja, es ist für diesen Schritt betrachtet der gesamte Datensatz!) ist wie folgt:

H(S_{Neukunde}) = - \frac{2}{5} \cdot \log_2(\frac{2}{5}) - \frac{3}{5} \cdot \log_2(\frac{3}{5})  = 0.97

Die Entropie ist weit weg von einer bestimmten Wahrscheinlichkeit (nahe der Gleichverteilung). Daher müssen wir hier nochmal ansetzen und losrechnen:

Entropien für “Zahlungsgeschwindigkeit” bei Neukunden:

H(S_{niedrig}) = 0.00

H(S_{mittel}) = 1.00

H(S_{hoch}) = 0.00

Informationsgewinn des Attributes “Zahlungsgeschwindigkeit” bei Neukunden:

    \[ IG(S_{Neukunde},A_{Zahlungsgeschwindigkeit}) = 0.97 - \frac{3}{5} \cdot 0.00 - \frac{2}{5} \cdot 1.00 -  \frac{1}{5} \cdot 0.00 = 0.57 \]

Betrachtung der Spalte “Kauffrequenz” bei Neukunden:

Entropien für “Kauffrequenz” bei Neukunden:

H(S_{niedrig}) = 0.00

H(S_{hoch}) = 0.00

Informationsgewinn des Attributes “Kauffrequenz” bei Neukunden:

    \[ IG(S_{Neukunde},A_{Kauffrequenz}) = 0.97 - \frac{3}{5} \cdot 0.00 - \frac{2}{5} \cdot 0.00 = 0.97 \]

Betrachtung der Spalte “Herkunft” bei Neukunden:

Entropien für “Herkunft” bei Neukunden:

H(S_{Inland}) = 0.92

H(S_{hoch}) = 1.00

Informationsgewinn des Attributes “Herkunft” bei Neukunden:

    \[ IG(S_{Neukunde},A_{Herkunft}) = 0.97 - \frac{3}{5} \cdot 0.92 - \frac{2}{5} \cdot 1.00 = 0.018 \]

Wir entscheiden uns also für das Attribut “Kauffrequenz” als Ast nach der Entscheidung “Neukunde”, denn dieses Attribut bring uns den größten Informationsgewinn und trennt uns die Unterscheidung für oder gegen das Zahlungsmittel “Rechnung” eindeutig auf.

3.1 Zweiter Rekursionsschritt

Was passiert mit der Kundenart “Stammkunde”?

Zeile Kundenart Zahlungsgeschwindigkeit Kauffrequenz Herkunft Zahlungsmittel: Rechnung?
 3  Stammkunde  niedrig  niedrig  Inland  true
 7  Stammkunde  hoch  hoch  Ausland  true
 12  Stammkunde  mittel  niedrig  Ausland  true
 13  Stammkunde  niedrig  hoch  Inland  true

Die Antwort ist einfach: Nichts!
Wer ein Stammkunde ist, dem wurde stets die Zahlung per Rechnung erlaubt.

H(S_{Stammkunde}) = 0.0

3.1 Dritter Rekursionsschritt

Fehlt nun nur noch die Frage nach der Unterscheidung von Normalkunden.

Zeile Kundenart Zahlungsgeschwindigkeit Kauffrequenz Herkunft Zahlungsmittel: Rechnung?
 4  Normalkunde  mittel  niedrig  Inland  true
 5  Normalkunde  hoch  hoch  Inland  true
 6  Normalkunde  hoch  hoch  Ausland  false
 14  Normalkunde  mittel  niedrig  Ausland  false

Zwar ist die Entropie des Subsets der Normalkunden…

H(S_{Normalkunde}) = 1.0

… denkbar schlecht, da maximal. Aber wir können genauso vorgehen, wie wir es bei dem Subset der Neukunden getan haben. Ich nehme es nun aber vorweg: Wenn wir uns den Datensatz näher ansehen, erkennen wir, dass wir diese Gesamtentropie von 1.0 für das Subset “Normalkunde” nicht mit den Attributen “Kauffrequenz” oder “Herkunft” reduzieren können, da dieses auch für sich betrachtet in Entropien der Größe 1.0 erhalten werden. Das Attribut “Herkunft” hingegen teilt den Datensatz sauber in true und false auf:

Somit ist der Informationsgewinn für das Attribut “Herkunft” am größten und wir haben unseren Baum komplett und – glücklicherweise – eindeutig bestimmen können!

Ergebnis: Der Entscheidungsbaum

Somit haben wir den Entscheidungsbaum über den ID3-Algorithmus erstellt, der eine Auskunft darüber macht, ob einem Kunden die Zahlung über Rechnung (statt Vorkasse) erlaubt wird:

true = Rechnung als Zahlungsmittel erlaubt
false = Rechnung als Zahlungsmittel nicht erlaubt

Shiny Web Applikationen

Jede Person, die irgendwie mit Daten arbeitet, kommt nicht herum, aus Analysen oder Modellen gezogene Erkenntnisse mit anderen zu teilen. Meist haben diese Personen keinen statistischen oder mathematischen Hintergrund. Für diese sollten die Ergebnisse nicht nur verständlich, sondern im besten Fall auch visuell ansprechend aufbereitet sein. Neben recht teuren Softwarelösungen wie Tableau oder QlikView gibt es von R-Studio auch eine (zumindest im kleinen Rahmen) kostenfreie Lösung – R-Shiny.

Shiny ist ein R Paket, mit dessen Hilfe man interaktive Webapplikationen oder Dashboards erstellen kann, bei dem man auf den vollen Funktionsumfang aller R-Pakete zugreifen kann.

Bei der Erstellung für einfache Shiny-Apps sind keine HTML, CSS oder Javascript Kenntnisse nötig. Shiny teilt sich im Prinzip in zwei Programme: Das Front-End wird in der Datei ui.r festgelegt. Alles was im Back-End passiert, wird in der Datei server.r beschrieben. R-Studio übernimmt danach das Rendern des Front- Ends und man erhält eine übliche HTML-Datei, in dessen Backend R läuft.

Die Vorteile der Einfachheit, nur mit R eine funktionale Web-App erstellen können, hat natürlich auch seine Nachteile. Shiny ist, was das Design betrifft, eher limitiert und auch die Platzierung von Inputs wie Slidern, Drop-Downs oder auch Outputs wie Grafiken oder Tabellen ist stark beschränkt.

Eine kaum bekannte und dokumentierte Funktion von R-Shiny ist die Funktion „htmlTemplate“. Mit dieser lassen sich komplett in HTML, CSS und gegebenenfalls Javascript geschriebene Websites mit der vollen Funktionalität von R im Back-End integrieren – und sehen um Längen besser aus als rein in R geschriebene Web-Apps.

Wie man auf diese Art Shiny Apps programmiert zeige ich nun anhand des Folgenden Beispiels. Die folgenden Erklärungen sind mit Absicht kurz gehalten und stellen kein Tutorial dar, sondern sollen vielmehr die Möglichkeiten der Funktion „htmlTemplate“ zeigen.

Zunächst zur ui.R:

Der Code in der ui.R Datei ist recht einfach gehalten. Es werden nur die Bibliotheken geladen, auf die R zugreifen muss. Danach wird das html Template mit dem entsprechenden Namen geladen. Ansonsten werden in dieser Datei nur Input und Output als Variablen festgelegt.

 

In der Server.R Datei wird in diesem Beispiel der bekannte und oft verwendete Datensatz Mtcars verwendet. Zunächst wird mit dem Paket dplyr und der Funktion filter ein neuer Datensatz berechnet, der auf Nutzereingaben reagiert (sliderInput, siehe ui.R). Wenn in R-Shiny in DataFrames Berechnungen durchgeführt werden, müssen diese immer in einem sog. reactive Statement stehen. Danach werden mittels ggplot2 insgesamt drei Plots zu dem Datensatz erstellt.

Plot 1 stellt einen Zusammenhang zwischen Gewicht und Benzinverbrauch mittels linearer Regression dar. Plot 2 zeigt an, wie viele Zylinder die Fahrzeuge aus dem gefilterten Datensatz haben und Plot 3 zeigt die Korrelationen zwischen den Variablen an. Diese drei Plots sollen dem Endnutzer interaktiv zur Verfügung stehen.

 

In dieser HTML Datei wird die Struktur der Web App festgelegt. Diese enthält neben reichlich HTML auch ein paar Zeilen Internal Javascript, mit dem sich die die Diagramme ein- und ausblenden lassen. Das wichtigste in dieser Datei ist jedoch die Funktionsweise, mit der die in der ui.R Datei die Variablen an das Template übergeben werden. Jede template.html muss im Kopf (<head> … /<head>) die Funktion {{ headContent() }} enthalten. Damit werden die für Shiny benötigte Depedencies beim Rendern geladen. Diese übrigen, in der ui.R Datei deklarierten Variablen, werden ebenfalls mittels zwei geschweiften Klammern an das Template übergeben.

 

Nun muss für das Styling der App nur doch eine CSS-Datei geladen werden. Wichtig ist zu beachten, dass externe CSS Dateien bei Shiny immer in einem gesonderten Ordner mit dem Namen „www“ abgespeichert werden müssen. Auf diesen Ordner wird in der HTML Datei nicht gesondert verwiesen. Es reicht der Verweis <link rel=’stylesheet’ href=’style.css’/>.

Für den Upload der Datei müssen server.R, ui.R und template.html auf einer Ebene liegen, während wie bereits erwähnt die CSS Datei in einem gesonderten Ordner namens „www“ abliegen muss.

Die Web App liegt unter folgendem Link ab: https://markuslang1987.shinyapps.io/CustomShiny/

Einiges an der App ist sicherlich Spielerei, der Artikel soll in erster Linie aber die Möglichkeiten zeigen, die man mit einem selbst erstellten HTML Template im Gegensatz zu den recht eingeschränkten Möglichkeiten der normalen Shiny Programmierung zur Verfügung hat. Außerdem möchte ich mit diesem Artikel zeigen, dass Webentwicklung und Data Science/Analytics nicht zwangsläufig komplett voneinander unabhängige Welten sind.

Lineare Regression in Python mit Scitkit-Learn

Die lineare Regressionsanalyse ist ein häufiger Einstieg ins maschinelle Lernen um stetige Werte vorherzusagen (Prediction bzw. Prädiktion). Hinter der Regression steht oftmals die Methode der kleinsten Fehlerquadrate und die hat mehr als eine mathematische Methode zur Lösungsfindung (Gradientenverfahren und Normalengleichung). Alternativ kann auch die Maximum Likelihood-Methode zur Regression verwendet werden. Wir wollen uns in diesem Artikel nicht auf die Mathematik konzentrieren, sondern uns direkt an die Anwendung mit Python Scikit-Learn machen:

Haupt-Lernziele:

  • Einführung in Machine Learning mit Scikit-Learn
  • Lineare Regression mit Scikit-Learn

Neben-Lernziele:

  • Datenvorbereitung (Data Preparation) mit Pandas und Scikit-Learn
  • Datenvisualisierung mit der Matplotlib direkt und indirekt (über Pandas)

Was wir inhaltlich tun:

Der Versuch einer Vorhersage eines Fahrzeugpreises auf Basis einer quantitativ-messbaren Eigenschaft eines Fahrzeuges.


Die Daten als Download

Für dieses Beispiel verwende ich die Datei “Automobil_data.txt” von Kaggle.com. Die Daten lassen sich über folgenden Link downloaden, nur leider wird ein (kostenloser) Account benötigt:
https://www.kaggle.com/toramky/automobile-dataset/downloads/automobile-dataset.zip
Sollte der Download-Link unerwartet mal nicht mehr funktionieren, freue ich mich über einen Hinweis als Kommentar 🙂

Die Entwicklungsumgebung

Ich verwende hier die Python-Distribution Anaconda 3 und als Entwicklungs-Umgebung Spyder (in Anaconda enthalten). Genauso gut funktionieren jedoch auch Jupyter Notebook, Eclipse mit PyDev oder direkt die IPython QT-Console.


Zuerst einmal müssen wir die Daten in unsere Python-Session laden und werden einige Transformationen durchführen müssen. Wir starten zunächst mit dem Importieren von drei Bibliotheken NumPy und Pandas, deren Bedeutung ich nicht weiter erläutern werde, somit voraussetze.

Wir nutzen die Pandas-Bibliothek, um die “Automobile_data.txt” in ein pd.DataFrame zu laden.

Schauen wir uns dann die ersten fünf Zeilen in IPython via dataSet.head().

Hinweis: Der Datensatz hat viele Spalten, so dass diese in der Darstellung mit einem Backslash \ umgebrochen werden.

Gleich noch eine weitere Ausgabe dataSet.info(), die uns etwas über die Beschaffenheit der importierten Daten verrät:

Einige Spalten entsprechen hinsichtlich des Datentypes nicht der Erwartung. Für die Spalten ‘horsepower’ und ‘peak-rpm’ würde ich eine Ganzzahl (Integer) erwarten, für ‘price’ hingegen eine Fließkommazahl (Float), allerdings sind die drei Spalten als Object deklariert. Mit Trick 17 im Data Science, der Anzeige der Minimum- und Maximum-Werte einer zu untersuchenden Datenreihe, kommen wir dem Übeltäter schnell auf die Schliche:

Datenbereinigung

Für eine Regressionsanalyse benötigen wir nummerische Werte (intervall- oder ratioskaliert), diese möchten wir auch durch richtige Datentypen-Deklaration herstellen. Nun wird eine Konvertierung in den gewünschten Datentyp jedoch an den (mit ‘?’ aufgefüllten) Datenlücken scheitern.

Schauen wir uns doch einmal die Datenreihen an, in denen in der Spalte ‘peak-rpm’ Fragezeichen stehen:

Zwei Datenreihen sind vorhanden, bei denen ‘peak-rpm’ mit einem ‘?’ aufgefüllt wurde. Nun könnten wir diese Datenreihen einfach rauslöschen. Oder mit sinnvollen (im Sinne von wahrscheinlichen) Werten auffüllen. Vermutlichen haben beide Einträge – beide sind OHC-Motoren mit 4 Zylindern – eine ähnliche Drehzahl-Angabe wie vergleichbare Motoren. Mit folgendem Quellcode, gruppieren wir die Spalten ‘engine-type’ und ‘num-of-cylinders’ und bilden für diese Klassen den arithmetischen Mittelwert (.mean()) für die ‘peak-rpm’.

Und schauen wir uns das Ergebnis an:

Ein Vier-Zylinder-OHC-Motor hat demnach durchschnittlich einen Drehzahl-Peak von 5155 Umdrehungen pro Minute. Ohne nun (fahrlässigerweise) auf die Verteilung in dieser Klasse zu achten, nehmen wir einfach diesen Schätzwert, um die zwei fehlende Datenpunkte zu ersetzen.

Wir möchten jedoch die Original-Daten erhalten und legen ein neues DataSet (dataSet_c) an, in welches wir die Korrekturen vornehmen:

Nun können wir die fehlenden Peak-RPM-Einträge mit unserem Schätzwert ersetzen:

Was bei einer Drehzahl-Angabe noch funktionieren mag, ist für anderen Spalten bereits etwas schwieriger: Die beiden Spalten ‘price’ und ‘horsepower’ sind ebenfalls vom Typ Object, da sie ‘?’ enthalten. Verzichten wir einfach auf die betroffenen Zeilen:

Datenvisualisierung mit Pandas

Wir wollen uns nicht lange vom eigentlichen Ziel ablenken, dennoch nutzen wir die Visualisierungsfähigkeiten der Pandas-Library (welche die Matplotlib inkludiert), um uns dann die Anzahlen an Einträgen nach Hersteller der Fahrzeuge (Spalte ‘make’) anzeigen zu lassen:

Oder die durchschnittliche PS-Zahl nach Hersteller:

Vorbereitung der Regressionsanalyse

Nun kommen wir endlich zur Regressionsanalyse, die wir mit Scikit-Learn umsetzen möchten. Die Regressionsanalyse können wir nur mit intervall- oder ratioskalierten Datenspalten betreiben, daher beschränken wir uns auf diese. Die “price”-Spalte nehmen wir jedoch heraus und setzen sie als unsere Zielgröße fest.

Interessant ist zudem die Betrachtung vorab, wie die einzelnen nummerischen Attribute untereinander korrelieren. Dafür nehmen wir auch die ‘price’-Spalte wieder in die Betrachtung hinein und hinterlegen auch eine Farbskala mit dem Preis (höhere Preise, hellere Farben).

Die lineare Korrelation ist hier sehr interessant, da wir auch nur eine lineare Regression beabsichtigen.

Wie man in dieser Scatter-Matrix recht gut erkennen kann, scheinen einige Größen-Paare nahezu perfekt zu korrelieren, andere nicht.

Korrelation…

  • …nahezu perfekt linear: highway-mpg vs city-mpg (mpg = Miles per Gallon)
  • … eher nicht gegeben: highway-mpg vs height
  • … nicht linear, dafür aber nicht-linear: highway-mpg vs price

Nun, wir wollen den Preis eines Fahrzeuges vorhersagen, wenn wir eine andere quantitative Größe gegeben haben. Auf den Preis bezogen, erscheint mir die Motorleistung (Horsepower) einigermaßen linear zu korrelieren. Versuchen wir hier die lineare Regression und setzen somit die Spalte ‘horsepower’ als X und ‘price’ als y fest.

Die gängige Konvention ist übrigens, X groß zu schreiben, weil hier auch mehrere x-Dimensionen enthalten sein dürfen (multivariate Regression). y hingegen, ist stets nur eine Zielgröße (eine Dimension).

Die lineare Regression ist ein überwachtes Verfahren des maschinellen Lernens, somit müssen wir unsere Prädiktionsergebnisse mit Test-Daten testen, die nicht für das Training verwendet werden dürfen. Scitkit-Learn (oder kurz: sklearn) bietet hierfür eine Funktion an, die uns das Aufteilen der Daten abnimmt:

Zu beachten ist dabei, dass die Daten vor dem Aufteilen in Trainings- und Testdaten gut zu durchmischen sind. Auch dies übernimmt die train_test_split-Funktion für uns, nur sollte man im Hinterkopf behalten, dass die Ergebnisse (auf Grund der Zufallsauswahl) nach jedem Durchlauf immer wieder etwas anders aussehen.

Lineare Regression mit Scikit-Learn

Nun kommen wir zur Durchführung der linearen Regression mit Scitkit-Learn, die sich in drei Zeilen trainieren lässt:

Aber Vorsicht! Bevor wir eine Prädiktion durchführen, wollen wir festlegen, wie wir die Güte der Prädiktion bewerten wollen. Die gängigsten Messungen für eine lineare Regression sind der MSE und R².

MSE = \frac{\sum_{i=1}^n (y_i - \hat{y_i})^2}{n}

Ein großer MSE ist schlecht, ein kleiner gut.

R^2 = 1 - \frac{MSE}{Var(y)}= \frac{\frac{1}{n} \cdot \sum_{i=1}^n (y_i - \hat{y_i})^2}{\frac{1}{n} \cdot \sum_{i=1}^n (y_i - \hat{\mu_y})^2}

Ein kleines R² ist schlecht, ein großes R² gut. Ein R² = 1.0 wäre theoretisch perfekt (da der Fehler = 0.00 wäre), jedoch in der Praxis unmöglich, da dieser nur bei absolut perfekter Korrelation auftreten würde. Die Klasse LinearRegression hat eine R²-Messmethode implementiert (score(x, y)).

Die Ausgabe (ein Beispiel!):

Nach jedem Durchlauf ändert sich mit der Datenaufteilung (train_test_split()) das Modell etwas und auch R² schwankt um eine gewisse Bandbreite. Berauschend sind die Ergebnisse dabei nicht, und wenn wir uns die Regressionsgerade einmal ansehen, wird auch klar, warum:

Bei kleineren Leistungsbereichen, etwa bis 100 PS, ist die Preis-Varianz noch annehmbar gering, doch bei höheren Leistungsbereichen ist die Spannweite deutlich größer. (Nachträgliche Anmerkung vom 06.05.2018: relativ betrachtet, bleibt der Fehler über alle Wertebereiche ungefähr gleich [relativer Fehler]. Die absoluten Fehlerwerte haben jedoch bei größeren x-Werten so eine Varianz der möglichen y-Werte, dass keine befriedigenden Prädiktionen zu erwarten sind.)

Egal wie wir eine Gerade in diese Punktwolke legen, wir werden keine befriedigende Fehlergröße erhalten.

Nehmen wir einmal eine andere Spalte für X, bei der wir vor allem eine nicht-lineare Korrelation erkannt haben: “highway-mpg”

Wenn wir dann das Training wiederholen:

Die R²-Werte sind nicht gerade berauschend, und das erklärt sich auch leicht, wenn wir die Trainings- und Testdaten sowie die gelernte Funktionsgerade visualisieren:

Die Gerade lässt sich nicht wirklich gut durch diese Punktwolke legen, da letztere eher eine Kurve als eine Gerade bildet. Im Grunde könnte eine Gerade noch einigermaßen gut in den Bereich von 22 bis 43 mpg passen und vermutlich annehmbare Ergebnisse liefern. Die Wertebereiche darunter und darüber jedoch verzerren zu sehr und sorgen zudem dafür, dass die Gerade auch innerhalb des mittleren Bereiches zu weit nach oben verschoben ist (ggf. könnte hier eine Ridge-/Lasso-Regression helfen).

Richtig gute Vorhersagen über nicht-lineare Verhältnisse können jedoch nur mit einer nicht-linearen Regression erreicht werden.

Nicht-lineare Regression mit Scikit-Learn

Nicht-lineare Regressionsanalysen erlauben es uns, nicht-lineare korrelierende Werte-Paare als Funktion zu erlernen. Im folgenden Scatter-Plot sehen wir zum einen die gewohnte lineare Regressionsgerade (y = a * x + b) in rot, eine polinominale Regressionskurve dritten Grades (y = a * x³ + b * x² + c * x + d) in violet sowie einen Entscheidungsweg einer Entscheidungsbaum-Regression in gelb.

Nicht-lineare Regressionsanalysen passen sich dem Verlauf der Punktwolke sehr viel besser an und können somit in der Regel auch sehr gute Vorhersageergebnisse liefern. Ich ziehe hier nun jedoch einen Gedankenstrich, liefere aber den Quellcode für die lineare Regression als auch für die beiden nicht-linearen Regressionen mit:

Python Script Regression via Scikit-Learn

Weitere Anmerkungen

  • Bibliotheken wie Scitkit-Learn erlauben es, machinelle Lernverfahren schnell und unkompliziert anwenden zu können. Allerdings sollte man auch verstehen, wei diese Verfahren im Hintergrund mathematisch arbeiten. Diese Bibliotheken befreien uns also nicht gänzlich von der grauen Theorie.
  • Statt der “reinen” lineare Regression (LinearRegression()) können auch eine Ridge-Regression (Ridge()), Lasso-Regression (Lasso()) oder eine Kombination aus beiden als sogenannte ElasticNet-Regression (ElasticNet()). Bei diesen kann über Parametern gesteuert werden, wie stark Ausreißer in den Daten berücksichtigt werden sollen.
  • Vor einer Regression sollten die Werte skaliert werden, idealerweise durch Standardisierung der Werte (sklearn.preprocessing.StandardScaler()) oder durch Normierung (sklearn.preprocessing.Normalizer()).
  • Wir haben hier nur zwei-dimensional betrachtet. In der Praxis ist das jedoch selten ausreichend, auch der Fahrzeug-Preis ist weder von der Motor-Leistung, noch von dem Kraftstoffverbrauch alleine abhängig – Es nehmen viele Größen auf den Preis Einfluss, somit benötigen wir multivariate Regressionsanalysen.

Privacy, Security and Ethics in Process Mining – Article Series

When I moved to the Netherlands 12 years ago and started grocery shopping at one of the local supermarket chains, Albert Heijn, I initially resisted getting their Bonus card (a loyalty card for discounts), because I did not want the company to track my purchases. I felt that using this information would help them to manipulate me by arranging or advertising products in a way that would make me buy more than I wanted to. It simply felt wrong.

Read this article in German:
Datenschutz, Sicherheit und Ethik beim Process Mining – Artikelserie

The truth is that no data analysis technique is intrinsically good or bad. It is always in the hands of the people using the technology to make it productive and constructive. For example, while supermarkets could use the information tracked through the loyalty cards of their customers to make sure that we have to take the longest route through the store to get our typical items (passing by as many other products as possible), they can also use this information to make the shopping experience more pleasant, and to offer more products that we like.

Most companies have started to use data analysis techniques to analyze their data in one way or the other. These data analyses can bring enormous opportunities for the companies and for their customers, but with the increased use of data science the question of ethics and responsible use also grows more dominant. Initiatives like the Responsible Data Science seminar series [1] take on this topic by raising awareness and encouraging researchers to develop algorithms that have concepts like fairness, accuracy, confidentiality, and transparency built in (see Wil van der Aalst’s presentation on Responsible Data Science at Process Mining Camp 2016).

Process Mining can provide you with amazing insights about your processes, and fuel your improvement initiatives with inspiration and enthusiasm, if you approach it in the right way. But how can you ensure that you use process mining responsibly? What should you pay attention to when you introduce process mining in your own organization?

In this article series, we provide you four guidelines that you can follow to prepare your process mining analysis in a responsible way:

Part 1 of 4: Clarify the Goal of the Analysis

Part 2 of 4: Responsible Handling of Data

Part 3 of 4: Consider Anonymization

Part 4 of 4: Establish a collaborative Culture

Acknowledgements

We would like to thank Frank van Geffen and Léonard Studer, who initiated the first discussions in the workgroup around responsible process mining in 2015. Furthermore, we would like to thank Moe Wynn, Felix Mannhardt and Wil van der Aalst for their feedback on earlier versions of this article.

Die Rastrigin-Funktion

Jeder Data Scientist kommt hin und wieder mal in die Situation, einen Algorithmus trainieren bzw. optimieren zu wollen oder zu müssen, ohne jedoch, dass passende Trainingsdaten unmittelbar verfügbar wären. Zum einen kann man in solchen Fällen auf Beispieldaten zugreifen, die mit vielen Analysetools mitgeliefert werden, oder aber man generiert sich seine Daten via mathematischer Modelle selbst, die für bestimmte Eigenschaften bekannt sind, die gute Bedingungen für das Optimierungstraining liefern. 

Ein solches Modell, das man als Machine Learning Entwickler kennen sollte, ist die Rastrigin-Funktion, die laut Wikipedia von Leonard A. Rastrigin erstmalig beschrieben wurde. Dabei handelt es sich um eine Häufigkeites-/Wahrscheinlichkeitsverteilung, deren Dichte mehrere lokale Modi (Gipfel) aufweist. Ein Modus (oder Modalwert) ist in einer Häufigkeitsverteilung der häufigste Wert (“Bergspitze”) bzw. der Wert mit der höchsten Wahrscheinlichkeit.

Anmerkung des Autors: Dieser Artikel stellt zum einen die Rastrigin-Funktion und ihre Bedeutung für die Optimierungsrechnung vor, ist zum anderen aber auch eine Einführung in den Umgang mit NumPy-Matrizen (die eine Menge For-Schleifen ersparen können).

Die Rastrigin-Funktion

Mathematisch beschrieben wird die Rastrigin-Funktion wie folgt:

f(x_1 \cdots x_n) = An + \sum_{i=1}^n (x_i^2 -10cos(2\pi x_i))

-5.12 \leq x_i \leq 5.12

Wobei für das globale Minimum gilt: f(0) = 0
Außerdem ist zu beachten, dass A=10 eine Konstante ist.

Die Rastrigin-Funktion im Standard-Python umsetzen und visualisieren

Die Formel lässt sich in Python (wie natürlich in jeder anderen Programmiersprache auch) einfach umsetzen:

Nun können wir über den klassischen Weg der Programmierung einfach eine For-Schleife verwenden, um die Rastrigin-Funktionswerte in eine Liste zu packen und mit einem Plot zu visualsieren, dabei bin ich leider doch nicht ganz um die Verwendung des NumPy-Pakets nicht herumgekommen:

rastrigin-line-chart

Die grafische Darstellung zeigt, dass es sich tatsächlich um eine symmetrische multimodalen Verteilung handelt.

Die Rastrigin-Funktion mehrdimensional umsetzen, mit NumPy-Matrizen-Funktionen

Die obige Umsetzung der Rastrigin-Funktion ist eindimensional (eine Variable), braucht für die Darstellung allerdings zwei Dimensionen (f(x) und die Durchlaufanzahl bzw. Zeitachse). Nun könnten wir die Zahl der Variablen von 1 (x) auf 2 (x und y) erhöhen und eine dreidimensionale Darstellung erzeugen. Eine ähnliche dreidimensionale Darstellung gab es bereits in meiner Vorstellung des k-nearest-Neighbour-Algorithmus nachzuvollziehen. Dabei müssten wir die Konstante A=10 auf A=20 verdoppeln:

rastrigin-funktion-python-3d-plot

Die Rastrigin-Funktion wird gerne für Optimierungsalgorithmen eingesetzt, wofür sie wegen des großen Suchraums und der hohen Anzahl lokaler Modi ein herausforderndes Umfeld bietet. Beispielsweise wird – meines Erachtens nach – das wohl beliebteste Optimierungsverfahren im maschinellen Lernen, das Gradientenverfahren, hier keine guten Ergebnisse liefern, denn es gibt einfach zu viele lokale Minima.

 

 

Einführung in WEKA

Waikato Environment for Knowledge Analysis, kurz WEKA, ist ein quelloffenes, umfangreiches, plattformunabhängiges Data Mining Softwarepaket. WEKA ist in Java geschrieben und wurde an der WAIKATO Iniversität entwickelt. In WEKA sind viele wichtige Data Mining/Machine Learning Algorithmen implementiert und es gibt extra Pakete, wie z. B. LibSVM für Support Vector Machines, welches nicht in WEKA direkt implementiert wurde. Alle Einzelheiten zum Installieren und entsprechende Download-Links findet man unter auf der Webseite der Waikato Universität. Zusammen mit der Software wird ein Manual und ein Ordner mit Beispiel-Datensätzen ausgeliefert. WEKA arbeitet mit Datensätzen im sogenannten attribute-relation file format, abgekürzt arff. Das CSV-Format wird aber ebenfalls unterstützt. Eine Datei im arff-Format ist eine ASCI-Textdatei, welche aus einem Header- und einem Datateil besteht. Im Header muss der Name der Relation und der Attribute zusammen mit dem Typ stehen, der Datenteil beginnt mit einem @data-Schlüsselwort. Als Beispiel sei hier ein Datensatz mit zwei Attributen und nur zwei Instanzen gegeben.

WEKA unterstützt auch direktes Einlesen von Daten aus einer Datenbank (mit JDBC) oder URL. Sobald das Tool installiert und gestartet ist, landet man im Hauptmenü von WEKA – WEKA GUI Chooser 1.

Abbildung 1: WEKA GUI Chooser

Abbildung 1: WEKA GUI Chooser

Der GUI Chooser bietet den Einstieg in WEKA Interfaces Explorer, Experimenter, KnowledgeFlow und simple CLI an. Der Explorer ist ein graphisches Interface zum Bearbeiten von Datensätzen, Ausführen von Algorithmen und Visualisieren von den Resultaten. Es ist ratsam, dieses Interface als Erstes zu betrachten, wenn man in WEKA einsteigen möchte. Beispielhaft führen wir jetzt ein paar Algorithmen im Explorer durch.

Der Explorer bietet mehrere Tabs an: Preprocess, Classify, Cluster, Associate, Select attributes und Visualize. Im Preprocess Tab hat man die Möglichkeit Datensätze vorzubereiten. Hier sind zahlreiche Filter zum Präprozessieren von Datensätzen enthalten. Alle Filter sind in supervised und unsupervised unterteilt, je nachdem, ob das Klassenattribut mitbetrachtet werden soll oder nicht. Außerdem kann man entweder Attribute oder Instanzen betrachten, mit Attributen lässt man Filter spaltenweise arbeiten und bei Instanzen reihenweise. Die Auswahl der Filter ist groß, man kann den ausgewählten Datensatz diskretisieren, normalisieren, Rauschen hinzufügen etc. Unter Visualize können z. B. die geladenen Datensätze visualisert werden. Mit Select attributes kann man mithilfe von Attribut Evaluator und Search Method ein genaueres Ergebnis erzielen. Wenn man im Preprocess den Datensatz lädt, erhält man einen Überblick über den Datensatz und dessen Visualisierung. Als Beispiel wird hier der Datensatz diabetes.arff genommen, welcher mit WEKA zusammen ausgeliefert wird. Dieser Datensatz enthält 768 Instanzen mit je 9 Attributen, wobei ein Attribut das Klassenattribut ist. Die Attribute enthalten z. B. Informationen über die Anzahl der Schwangerschaften, diastolischer Blutdruck, BMI usw. Alle Attribute, außer dem Klassenattribut, sind numerisch. Es gibt zwei Klassen tested negativ und tested positiv, welche das Resultat des Testens auf diabetes mellitus darstellen. über Preprocess -> Open File lädt man den Datensatz in WEKA und sieht alle relevanten Informationen wie z. B. Anzahl und Name der Attribute. Nach dem Laden kann der Datensatz klassifiziert werden.

Abbildung 2: Diabetes.arff Datensatz geladen in WEKA

Abbildung 2: Diabetes.arff Datensatz geladen in WEKA

Hierzu einfach auf Classify klicken und unter Choose den gewünschten Algorithmus auswählen. Für diesen Datensatz wählen wir jetzt den Algorithmus kNN (k-Nearest Neighbour). Der Algorithmus klassifiziert das Testobjekt anhand der Klassenzugehörigkeit von den k Nachbarobjekten, die am nähsten zu dem Testobjekt liegen. Die Distanz zwischen den Objekten und dem Testobjekt wird mit einer Ähnlichkeitsmetrik bestimmt, meistens als euklidische oder Manhattan-Distanz. In WEKA ist der Algorithmus unter lazy iBk zu finden. Wenn man auf das Feld neben dem Algorithmusnamen in WEKA mit rechter Maustaste klickt, kann man unter show properties die Werte für den ausgewählten Algorithmus ändern, bei iBk kann man u.A. den Wert für k ändern. Für den ausgewählten Datensatz diabetes.arff stellen wir beispielsweise k = 3 ein und führen die 10-fache Kreuzvalidierung durch, indem wir unter Test Options die Cross Validation auswählen. Nach der Klassifikation werden die Ergebnisse in einer Warhheitsmatrix präsentiert. In unserem Fall sieht diese wie folgt aus:

Die Anzahl der richtig klassifizierten Instanzen beträgt 72.6563 %. Wenn man in der Result list auf den entsprechenden Algorithmus einen Rechtsklick macht, kann man z. B. noch den Fehler der Klassifizierung visualisieren. Entsprechend lassen sich im Explorer unter Cluster Clustering-Algorithmen und unter Associate Assoziationsalgorithmen auf einen ausgewählten Datensatz anwenden. Die restlichen Interfaces von WEKA bieten z. T. die gleiche Funktionalität oder erweitern die Möglichkeiten des Experimentierens, fordern aber mehr Erfahrung und Wissen von dem User. Das Experimenter Interface dient dazu, mehrere Datensätze mit mehreren Algorithmen zu analysieren. Mit diesem Interface kann man groß-skalierte Experimente durchführen. Simple CLI bietet dem User eine Kommandozeile, statt einem graphischen Interface, an.