Posts

Aika: Ein semantisches neuronales Netzwerk

Wenn es darum geht Informationen aus natürlichsprachigen Texten zu extrahieren, stehen einem verschiedene Möglichkeiten zur Verfügung. Eine der ältesten und wohl auch am häufigsten genutzten Möglichkeiten ist die der regulären Ausdrücke. Hier werden exakte Muster definiert und in einem Textstring gematcht. Probleme bereiten diese allerdings, wenn kompliziertere semantische Muster gefunden werden sollen oder wenn verschiedene Muster aufeinander aufbauen oder miteinander interagieren sollen. Gerade das ist aber der Normalfall bei der Verarbeitung von natürlichem Text. Muster hängen voneinander ab, verstärken oder unterdrücken sich gegenseitig.
Prädestiniert um solche Beziehungen abzubilden wären eigentlich künstliche neuronale Netze. Diese haben nur das große Manko, dass sie keine strukturierten Informationen verarbeiten können. Neuronale Netze bringen von sich aus keine Möglichkeit mit, die relationalen Beziehungen zwischen Worten oder Phrasen zu verarbeiten. Ein weiteres Problem neuronaler Netze ist die Verarbeitung von Feedback-Schleifen, bei denen einzelne Neuronen von sich selbst abhängig sind. Genau diese Probleme versucht der Aika Algorithmus (www.aika-software.org) zu lösen.

Der Aika Algorithmus ist als Open Source Java-Bibliothek implementiert und dient dazu semantische Informationen in Texten zu erkennen und zu verarbeiten. Da semantische Informationen sehr häufig mehrdeutig sind, erzeugt die Bibliothek für jede dieser Bedeutungen eine eigene Interpretation und wählt zum Schluss die am höchsten gewichtete aus. Aika kombiniert dazu aktuelle Ideen und Konzepte aus den Bereichen des maschinellen Lernens und der künstlichen Intelligenz, wie etwa künstliche neuronale Netze, Frequent Pattern Mining und die auf formaler Logik basierenden Expertensysteme. Aika basiert auf der heute gängigen Architektur eines künstlichen neuronalen Netzwerks (KNN) und nutzt diese, um sprachliche Regeln und semantische Beziehungen abzubilden.

Die Knackpunkte: relationale Struktur und zyklische Abhängigkeiten

Das erste Problem: Texte haben eine von Grund auf relationale Struktur. Die einzelnen Worte stehen über ihre Reihenfolge in einer ganz bestimmten Beziehung zueinander. Gängige Methoden, um Texte für die Eingabe in ein KNN auszuflachen, sind beispielsweise Bag-of-Words oder Sliding-Window. Mittlerweile haben sich auch rekurrente neuronale Netze etabliert, die das gesamte Netz in einer Schleife für jedes Wort des Textes mehrfach hintereinander schalten. Aika geht hier allerdings einen anderen Weg. Aika propagiert die relationalen Informationen, also den Textbereich und die Wortposition, gemeinsam mit den Aktivierungen durch das Netzwerk. Die gesamte relationale Struktur des Textes bleibt also erhalten und lässt sich jederzeit zur weiteren Verarbeitung nutzen.

Das zweite Problem ist, dass bei der Verarbeitung von Text häufig nicht klar ist, in welcher Reihenfolge einzelne Informationen verarbeitet werden müssen. Wenn wir beispielsweise den Namen „August Schneider“ betrachten, können sowohl der Vor- als auch der Nachname in einem anderen Zusammenhang eine völlig andere Bedeutung annehmen. August könnte sich auch auf den Monat beziehen. Und genauso könnte Schneider eben auch den Beruf des Schneiders meinen. Einfache Regeln, um hier dennoch den Vor- und den Nachnamen zu erkennen, wären: „Wenn das nachfolgende Wort ein Nachname ist, handelt es sich bei August um einen Vornamen“ und „Wenn das vorherige Wort ein Vorname ist, dann handelt es sich bei Schneider um einen Nachnamen“. Das Problem dabei ist nur, dass unsere Regeln nun eine zyklische Abhängigkeit beinhalten. Aber ist das wirklich so schlimm? Aika erlaubt es, genau solche Feedback-Schleifen abzubilden. Wobei die Schleifen sowohl positive, als auch negative Gewichte haben können. Negative rekurrente Synapsen führen dazu, dass zwei sich gegenseitig ausschließende Interpretationen entstehen. Der Trick ist nun zunächst nur Annahmen zu treffen, also etwa dass es sich bei dem Wort „Schneider“ um den Beruf handelt und zu schauen wie das Netzwerk auf diese Annahme reagiert. Es bedarf also einer Evaluationsfunktion und einer Suche, die die Annahmen immer weiter variiert, bis schließlich eine optimale Interpretation des Textes gefunden ist. Genau wie schon der Textbereich und die Wortposition werden nun auch die Annahmen gemeinsam mit den Aktivierungen durch das Netzwerk propagiert.

Die zwei Ebenen des Aika Algorithmus

Aber wie lassen sich diese Informationen mit den Aktivierungen durch das Netzwerk propagieren, wo doch der Aktivierungswert eines Neurons für gewöhnlich nur eine Fließkommazahl ist? Genau hier liegt der Grund, weshalb Aika unter der neuronalen Ebene mit ihren Neuronen und kontinuierlich gewichteten Synapsen noch eine diskrete Ebene besitzt, in der es eine Darstellung aller Neuronen in boolscher Logik gibt. Aika verwendet als Aktivierungsfunktion die obere Hälfte der Tanh-Funktion. Alle negativen Werte werden auf 0 gesetzt und führen zu keiner Aktivierung des Neurons. Es gibt also einen klaren Schwellenwert, der zwischen aktiven und inaktiven Neuronen unterscheidet. Anhand dieses Schwellenwertes lassen sich die Gewichte der einzelnen Synapsen in boolsche Logik übersetzen und entlang der Gatter dieser Logik kann nun ein Aktivierungsobjekt mit den Informationen durch das Netzwerk propagiert werden. So verbindet Aika seine diskrete bzw. symbolische Ebene mit seiner subsymbolischen Ebene aus kontinuierlichen Synapsen-Gewichten.

Die Logik Ebene in Aika erlaubt außerdem einen enormen Effizienzgewinn im Vergleich zu einem herkömmlichen KNN, da die gewichtete Summe von Neuronen nur noch für solche Neuronen berechnet werden muss, die vorher durch die Logikebene aktiviert wurden. Im Falle eines UND-verknüpfenden Neurons bedeutet das, dass das Aktivierungsobjekt zunächst mehrere Ebenen einer Lattice-Datenstruktur aus UND-Knoten durchlaufen muss, bevor das eigentliche Neuron berechnet und aktiviert werden kann. Diese Lattice-Datenstruktur stammt aus dem Bereich des Frequent Pattern Mining und enthält in einem gerichteten azyklischen Graphen alle Teilmuster eines beliebigen größeren Musters. Ein solches Frequent Pattern Lattice kann in zwei Richtungen betrieben werden. Zum Einen können damit bereits bekannte Muster gematcht werden, und zum Anderen können auch völlig neue Muster damit erzeugt werden.

Da es schwierig ist Netze mit Millionen von Neuronen im Speicher zu halten, nutzt Aika das Provider Architekturpattern um selten verwendete Neuronen oder Logikknoten in einen externen Datenspeicher (z.B. eine Mongo DB) auszulagern, und bei Bedarf nachzuladen.

Ein Beispielneuron

Hier soll nun noch beispielhaft gezeigt werden wie ein Neuron innerhalb des semantischen Netzes angelegt werden kann. Zu beachten ist, dass Neuronen sowohl UND- als auch ODER-Verknüpfungen abbilden können. Das Verhalten hängt dabei alleine vom gewählten Bias ab. Liegt der Bias bei 0.0 oder einem nur schwach negativen Wert reicht schon die Aktivierung eines positiven Inputs aus um auch das aktuelle Neuron zu aktivieren. Es handelt sich dann um eine ODER-Verknüpfung. Liegt der Bias hingegen tiefer im negativen Bereich dann müssen mitunter mehrere positive Inputs gleichzeitig aktiviert werden damit das aktuelle Neuron dann auch aktiv wird. Jetzt handelt es sich dann um eine UND-Verknüpfung. Der Bias Wert kann der initNeuron einfach als Parameter übergeben werden. Um jedoch die Berechnung des Bias zu erleichtern bietet Aika bei den Inputs noch den Parameter BiasDelta an. Der Parameter BiasDelta nimmt einen Wert zwischen 0.0 und 1.0 entgegen. Bei 0.0 wirkt sich der Parameter gar nicht aus. Bei einem höheren Wert hingegen wird er mit dem Betrag des Synapsengewichts multipliziert und von dem Bias abgezogen. Der Gesamtbias lautet in diesem Beispiel also -55.0. Die beiden positiven Eingabesynapsen müssen also aktiviert werden und die negative Eingabesynapse darf nicht aktiviert werden, damit dieses Neuron selber aktiv werden kann. Das Zusammenspiel von Bias und Synpasengewichten ist aber nicht nur für die Aktivierung eines Neurons wichtig, sondern auch für die spätere Auswahl der finalen Interpretation. Je stärker die Aktivierungen innerhalb einer Interpretation aktiv sind, desto höher wird diese Interpretation gewichtet.
Um eine beliebige Graphstruktur abbilden zu können, trennt Aika das Anlegen der Neuronen von der Verknüpfung mit anderen Neuronen. Mit createNeuron(“E-Schneider (Nachname)”) wird also zunächst einmal ein unverknüpftes Neuron erzeugt, das dann über die initNeuron Funktion mit den Eingabeneuronen wortSchneiderNeuron, kategorieVornameNeuron und unterdrueckendesNeuron verknüpft wird. Über den Parameter RelativeRid wird hier angegeben auf welche relative Wortposition sich die Eingabesynapse bezieht. Die Eingabesynpase zu der Kategorie Vorname bezieht sich also mit -1 auf die vorherige Wortposition. Der Parameter Recurrent gibt an ob es sich bei dieser Synpase um eine Feedback-Schleife handelt. Über den Parameter RangeMatch wird angegeben wie sich der Textbereich, also die Start- und die Endposition zwischen der Eingabe- und der Ausgabeaktivierung verhält. Bei EQUALS sollen die Bereiche also genau übereinstimmen, bei CONTAINED_IN reicht es hingegen wenn der Bereich der Eingabeaktivierung innerhalb des Bereichs der Ausgabeaktivierung liegt. Dann kann noch über den Parameter RangeOutput angegeben werden, dass der Bereich der Eingabeaktivierung an die Ausgabeaktivierung weiterpropagiert werden soll.

Fazit

Mit Aika können sehr flexibel umfangreiche semantische Modelle erzeugt und verarbeitet werden. Aus Begriffslisten verschiedener Kategorien, wie etwa: Vor- und Nachnamen, Orten, Berufen, Strassen, grammatikalischen Worttypen usw. können automatisch Neuronen generiert werden. Diese können dann dazu genutzt werden, Worte und Phrasen zu erkennen, einzelnen Begriffen eine Bedeutung zuzuordnen oder die Kategorie eines Begriffs zu bestimmen. Falls in dem zu verarbeitenden Text mehrdeutige Begriffe oder Phrasen auftauchen, kann Aika für diese jeweils eigene Interpretationen erzeugen und gewichten. Die sinnvollste Interpretation wird dann als Ergebnis zurück geliefert.

Toolkits & Services für Semantische Textanalysen

Named Entity Recognition ist ein Teilgebiet von Information Extraction. Ziel von Information Extraction ist die Gewinnung semantischer Informationen aus Texten (im Gegensatz zum verwandten Gebiet des Information Retrieval, bei dem es um das möglichst intelligente Finden von Informationen, die u.U. vorab mit Information Extraction gewonnen wurden, geht). Named Entity Recognition (kurz NER) bezeichnet die Erkennung von Entitäten wie z.B. Personen, Organisationen oder Orten in Texten.

[box]Beispiel:
Albert Einstein war ein theoretischer Physiker, der am 14. März 1879 in Ulm geboren wurde. Er erhielt 1921 den Nobelpreis für Physik. Isaac Newton, Einstein und Stephen Hawking werden oft als die größten Physiker seit der Antike bezeichnet.”[/box]

Die Disambiguierung von Entitäten ist ein weiterer wichtiger Schritt auf dem Weg zu einem semantischen Verständnis von Texten. Wenn man so in obigem Text erkennen kann, dass “Albert Einstein“, “Er” und “Einstein” die gleiche Person bezeichnen, so kann ein Analyseverfahren z.B. daraus schließen, dass in diesem Text Einstein eine wichtigere Rolle spielt, als Newton, der nur einmal erwähnt wurde. Die Hyperlinks hinter den jeweiligen Entitäten zeigen eine Möglichkeit der semantischen Anreicherung von Texten an – in diesem Fall wurden die Entitäten mit entsprechenden Einträgen bei DBpedia automatisch verlinkt.

Named Entity Recognition dient vorrangig zwei Zwecken:

  • Anreicherung von Texten mit Metadaten
  • Abstraktion von Texten zur besseren Erkennung von Mustern

Punkt 1 dient direkt dem Information Retrieval. Anwender können so z.B. gezielt nach bestimmten Personen suchen, ohne alle möglichen Schreibweisen oder Berufsbezeichnungen auflisten zu müssen.

Punkt 2 dient der Vorverarbeitung von Texten als Input für Machine Learning Verfahren. So ist es (je nach Anwendung!) oft nicht von Bedeutung, welche Person, welcher Ort oder auch welche Uhrzeit in einem Text steht sondern nur die Tatsache, dass Personen, Orte oder Zeiten erwähnt wurden.

Sirrus Shakeri veranschaulicht die zentrale Bedeutung semantischer Analyse in seinem Beitrag From Big Data to Intelligent Applications:

intelligent-applications-cirrus-shakeri

Abbildung 1: Von Big Data zu Intelligent Applications von Cirrus Shakeri

Sein “Semantic Graph” setzt voraus, dass Entitäten mittels “Natural Language Processing” erkannt und zueinander in Beziehung gesetzt wurden.

Es ist interessant zu vermerken, dass Natural Language Processing und Data Mining / Machine Learning über viele Jahre als Alternativen zueinander und nicht als Ergänzungen voneinander gesehen wurden. In der Tat springen die meisten Vorgehensmodelle heutzutage von “Data Preparation” zu “Machine Reasoning”. Wir argumentieren, dass sich in vielen Anwendungen, die auf unstrukturierten Daten basieren, signifikante Qualitätsverbesserungen erzielen lassen, wenn man zumindest NER (inklusive Disambiguierung) in die Pipeline mit einbezieht.

Toolkits und Services für NER

Es existiert eine Vielzahl von Toolkits für Natural Language Processing, die Sie mehr oder weniger direkt in Ihre Programme einbinden können. Exemplarisch seien drei Toolkits für Java, Python und R erwähnt:

Diese Toolkits enthalten Modelle, die auf Korpora für die jeweils unterstützten Sprachen trainiert wurden. Sie haben den Vorteil, dass sie auch vollkommen neue Entitäten erkennen können (wie z.B. neue Politiker oder Fernsehstars, die zur Trainingszeit noch unbekannt waren). Je nach Einstellung haben diese Systeme aber auch eine relativ hohe Falsch-Positiv-Rate.

Wer NER nur ausprobieren möchte oder lediglich gelegentlich kleinere Texte zu annotieren hat, sei auf die folgenden Web Services verwiesen, die auch jeweils eine REST-Schnittstelle anbieten.

DBpedia

Das DBpedia Projekt nutzt die strukturierten Informationen der verschieden-sprachigen Wikipedia Sites für den Spotlight Service. Im Unterschied zu den reinen Toolkits nutzen die nun genannten Werkzeuge zusätzlich zu den trainierten Modellen eine Wissensbasis zur Verringerung der Falsch-Positiv-Rate. Die mehrsprachige Version unter http://dbpedia-spotlight.github.io/demo zeigt die Möglichkeiten des Systems auf. Wählen Sie unter “Language” “German“) und dann über “SELECT TYPES…” die zu annotierenden Entitätstypen. Ein Beispieltext wird automatisch eingefügt. Sie können ihn natürlich durch beliebige andere Texte ersetzen. Im folgenden Beispiel wurden “Organisation”, “Person”, und “Place“ ausgewählt:

DBprediaSpotlight

Abbildung 2: DBpedia Demo (de.dbpedia.org)

Die erkannten Entitäten werden direkt mit ihren DBpedia Datenbankeinträgen verlinkt. Im Beispiel wurden die Orte Berlin, Brandenburg und Preußen sowie die Organisationen Deutsches Reich, Deutsche Demokratische Republik, Deutscher Bundestag und Bundesrat erkannt. Personen wurden in dem Beispieltext nicht erkannt. Die Frage, ob man “Sitz des Bundespräsidenten” als Ort (Sitz), Organisation (das Amt des Bundespräsidenten) und / oder Person (der Bundespräsident) bezeichnen sollte, hängt durchaus vom Anwendungsszenario ab.

OpeNER

Das OpeNER Projekt ist das Ergebnis eines europäischen Forschungsprojekts und erweitert die Funktionalität von DBpedia Spotlight mit weiteren semantischen Analysen. Die Demo unter http://demo2-opener.rhcloud.com/welcome.action (Tab “Live Analysis Demo“, “Named Entity Recognition and Classification” und “Named Entity Linking” auswählen und “Analyse” drücken, dann auf der rechten Seite das Tab “NERC” anwählen) ergibt für den gleichen Beispieltext:

opeNER-projekt

Abbildung 3: OpeNER Projekt (opener-project.eu)

Organisationen sind blau hinterlegt, während Orte orange markiert werden. Auch hier werden erkannte Entitäten mit ihren DBpedia Datenbankeinträgen verknüpft. Die Bedeutung dieser Verknüpfung erkennt man wenn man auf das Tab “Map” wechselt. Berlin wurde als Ort erkannt und über die Geo-Koordinaten (geo:long = 13.4083, geo.lat = 52.5186) im DBpedia Eintrag von Berlin konnte das Wort “Berlin” aus obigem Text automatisch auf der Weltkarte referenziert werden.

Es gibt eine Vielzahl weiterer Services für NLP wie z.B. OpenCalais. Einige dieser Services bieten bestimmte Funktionalitäten (wie z.B. Sentiment Analysis) oder andere Sprachen neben Englisch nur gegen eine Gebühr an.

Listen Tagger

Der Vollständigkeit halber sei noch erwähnt, dass in den meisten Anwendungsszenarien die oben genannten Werkzeuge durch sogenannte Listen-Tagger (englisch Dictionary Tagger) ergänzt werden. Diese Tagger verwenden Listen von Personen, Organisationen oder auch Marken, Bauteilen, Produktbezeichnern oder beliebigen anderen Gruppen von Entitäten. Listen-Tagger arbeiten entweder unabhängig von den oben genannten statistischen Taggern (wie z.B. dem Standford Tagger) oder nachgeschaltet. Im ersten Fall markieren diese Tagger alle Vorkommen bestimmter Worte im Text (z.B. „Zalando“ kann so direkt als Modemarke erkannt werden). Im zweiten Fall werden die Listen genutzt, um die statistisch erkannten Entitäten zu verifizieren. So könnte z.B. der Vorschlag des statistischen Taggers automatisch akzeptiert werden wenn die vorgeschlagene Person auch in der Liste gefunden wird. Ist die Person jedoch noch nicht in der Liste enthalten, dann könnte ein Mitarbeiter gebeten werden, diesen Vorschlag zu bestätigen oder zu verwerfen. Im Falle einer Bestätigung wird die neu erkannte Person dann in die Personenliste aufgenommen während sie im Falle einer Ablehnung in eine Negativliste übernommen werden könnte damit dieser Vorschlag in Zukunft automatisch unterdrückt wird.

Regular Expression Tagger

Manche Entitätstypen folgen klaren Mustern und können mit hoher Zuverlässigkeit durch reguläre Ausdrücke erkannt werden. Hierzu zählen z.B. Kreditkarten- oder Telefon- oder Versicherungsnummern aber auch in vielen Fällen Bauteilbezeichner oder andere firmeninterne Identifikatoren.

Fazit

Natural Language Processing und insbesondere Named Entity Recognition und Disambiguierung sollte Teil der Werkzeugkiste eines jeden Anwenders bei der Analyse von unstrukturierten Daten sein. Es existieren mehrere mächtige Toolkits und Services, die allerdings je nach Anwendungsgebiet kombiniert und verfeinert werden müssen. So erkennt DBpedia Spotlight nur Entitäten, die auch einen Wikipedia Eintrag haben, kann für diese aber reichhaltige Metadaten liefern. Der Stanford Tagger hingegen kann auch vollkommen unbekannte Personennamen aus dem textuellen Kontext erkennen, hat aber bei manchen Texten eine relativ hohe Falsch-Positiv-Rate. Eine Kombination der beiden Technologien und anwendungsspezifischen Listen von Entitäten kann daher zu qualitativ sehr hochwertigen Ergebnissen führen.

Text Mining mit R

R ist nicht nur ein mächtiges Werkzeug zur Analyse strukturierter Daten, sondern eignet sich durchaus auch für erste Analysen von Daten, die lediglich in textueller und somit unstrukturierter Form vorliegen. Im Folgenden zeige ich, welche typischen Vorverarbeitungs- und Analyseschritte auf Textdaten leicht durchzuführen sind. Um uns das Leben etwas leichter zu machen, verwenden wir dafür die eine oder andere zusätzliche R-Library.

Die gezeigten Schritte zeigen natürlich nur einen kleinen Ausschnitt dessen, was man mit Textdaten machen kann. Der Link zum kompletten R-Code (.RMD) findet sich am Ende des Artikels.

Sentimentanalyse

Wir verwenden das Anwendungsgebiet der Sentimentanalyse für diese Demonstration. Mittels der Sentimentanalyse versucht man, Stimmungen zu analysieren. Im Prinzip geht es darum, zu erkennen, ob ein Autor mit einer Aussage eine positive oder negative Stimmung oder Meinung ausdrückt. Je nach Anwendung werden auch neutrale Aussagen betrachtet.

Daten einlesen

Datenquelle: ‘From Group to Individual Labels using Deep Features’, Kotzias et. al,. KDD 2015

Die Daten liegen als cvs vor: Die erste Spalte enhält jeweils einen englischen Satz, gefolgt von einem Tab, gefolgt von einer 0 für negatives Sentiment und einer 1 für positives Sentiment. Nicht alle Sätze in den vorgegebenen Daten sind vorklassifiziert.

Wir lesen 3 Dateien ein, fügen eine Spalte mit der Angabe der Quelle hinzu und teilen die Daten dann in zwei Datensätze auf. Der Datensatz labelled enthält alle vorklassifizierten Sätze während alle anderen Sätze in unlabelled gespeichert werden.

Wir haben nun 3000 vorklassifizierte Sätze, die entweder ein positives oder ein negatives Sentiment ausdrücken:

Textkorpus anlegen

Zuerst konvertieren wir den Datensatz in einen Korpus der R-Package tm:

Wir können uns nun einen Eindruck über die Texte verschaffen, bevor wir erste Vorverarbeitungs- und Säuberungsschritte durchführen:

  • Fünf Dokumente mit negativem Sentiment, die das Wort “good” enthalten: Not a good bargain., Not a good item.. It worked for a while then started having problems in my auto reverse tape player., Not good when wearing a hat or sunglasses., If you are looking for a good quality Motorola Headset keep looking, this isn’t it., However, BT headsets are currently not good for real time games like first-person shooters since the audio delay messes me up.
  • Liste der meist verwendeten Worte im Text: all, and, are, but, film, for, from, good, great, had, have, it’s, just, like, movie, not, one, phone, that, the, this, very, was, were, with, you
  • Anzahl der Worte, die nur einmal verwendet werden: 4820, wie z.B.: ‘film’, ‘ive, ’must’, ‘so, ’stagey’, ’titta
  • Histogramm mit Wortfrequenzen:

Plotten wir, wie oft die häufigsten Worte verwendet werden:

Vorverarbeitung

Es ist leicht zu erkennen, dass sogenannte Stoppworte wie z.B. “the”, “that” und “you” die Statistiken dominieren. Der Informationsgehalt solcher Stopp- oder Füllworte ist oft gering und daher werden sie oft vom Korpus entfernt. Allerdings sollte man dabei Vorsicht walten lassen: not ist zwar ein Stoppwort, könnte aber z.B. bei der Sentimentanalyse durchaus von Bedeutung sein.

Ein paar rudimentäre Vorverarbeitungen:

Wir konvertieren den gesamten Text zu Kleinbuchstaben und entfernen die Stoppworte unter Verwendung der mitgelieferten R-Stoppwortliste für Englisch (stopwords(“english”)). Eine weitere Standardoperation ist Stemming, das wir heute auslassen. Zusätzlich entfernen wir alle Sonderzeichen und Zahlen und behalten nur die Buchstaben a bis z:

 

Schlagwortwolke bzw Tag Cloud

Schließlich erzeugen wir eine Tag-Cloud aller Worte, die mindestens 25 mal im Text verwendet werden. Tag-Clouds eignen sich hervorragend zur visuellen Inspektion von Texten, allerdings lassen sich daraus nur bedingt direkte Handlungsanweisungen ableiten:

schlagwortwolke

Word-Assoziationen

Wir können uns für bestimmte Worte anzeigen lassen, wie oft sie gemeinsam mit anderen Worten im gleichen Text verwendet werden:

  • Worte, die häufig gemeinsam mit movie verwendet werden:

  • Worte, die häufig gemeinsam mit product verwendet werden:


 

Text-Mining

Wir erzeugen einen Entscheidungsbaum zur Vorhersage des Sentiments. Entscheidungsbäume sind nicht unbedingt das Werkzeug der Wahl für Text-Mining aber für einen ersten Eindruck lassen sie sich bei kleinen Datensätzen durchaus gewinnbringend einsetzen:

 

Eine Fehlerrate von über 50% auf den Trainingsdaten für positive Sentiments ist natürlich nicht berauschend und daher testen wir zum Schluß noch Support Vector Machines:

Die Ergebnisse sehen deutlich besser aus, müssten aber natürlich noch auf unabhängigen Daten verifiziert werden, um z. B. ein Overfittung zu vermeiden.

Download-Link zum kompletten R-Code für dieses Text-Mining-Beispiel: https://www.data-science-blog.com/download/textMiningTeaser.rmd

Text-Mining mit dem Aika Algorithmus

In diesem Beitrag möchte ich das Open Source Projekt Aika vorstellen. Ziel des Projektes ist es einen Text-Mining Algorithmus zu entwickeln, der ein künstliches Neuronales Netz (kNN) mit einem Pattern Mining Algorithmus kombiniert. Dabei dient die Silbentrennung von Wörtern als initiale Aufgabe, anhand derer der Algorithmus weiterentwickelt wird. Für diese Aufgabe soll allerdings kein vordefiniertes Wörterbuch verwendet werden. Stattdessen sollen die Silben in ihrer Eigenschaft als häufig auftretende Muster in rohem Text erkannt werden. Hier reicht es allerdings nicht einen Mining Algorithmus nach häufig auftretenden Strings suchen zu lassen, da sich viele der Strings überlappen oder schlicht keinen Sinn ergeben würden. Es ist also wichtig, dass sich die erkannten Silben gegenseitig unterdrücken können und dass der Algorithmus in der Lage ist, die so entstehenden unterschiedlichen Interpretationen eines Wortes miteinander zu vergleichen und die am höchsten gewichtete auszuwählen. Beispielsweise taucht die Silbe ‘der’ zu Beginn des Wortes ‘de-re-gu-lie-ren’ auf. In diesem Fall muss der Algorithmus erkennen, dass die erste Silbe des Wortes nicht ‘der’ sondern nur ‘de’ ist.

Wenn nun nach häufig auftretenden Mustern in Text gesucht werden soll, warum verwenden wir nicht einen reinen Pattern Mining Algorithmus? Der Grund für die Kombination mit einem kNN liegt darin, dass die erkannten Muster innerhalb einer kNN Topologie aufeinander aufsetzen können. Wenn z. B. das Wort “hausboot” als Muster erkannt werden soll, dann entstünden in der Datenstruktur des Mining Algorithmus sehr viele Teilmuster, die alle evaluiert werden müssten. Viel leichter wäre es für den Algorithmus, wenn die Muster “haus” und “boot” bereits erkannt worden wären und nun als Eingaben für die Erkennung des Wortes “hausboot” dienen könnten. So ist der Algorithmus zum einen in der Lage komplexere Muster zu erkennen und muss gleichzeitig weniger Teilmuster untersuchen. Ausserdem erlaubt es ein kNN ‘weiche’ Muster zu erlernen, also Muster bei denen einzelne Eingänge optional sind, die aber trotzdem noch sicher erkannt werden. Dadurch kann eine höhere Toleranz gegenüber Fehlern erreicht werden.

Im Gegensatz zu einem klassischen kNN nutzt Aika einen eher mit Googles Pagerank vergleichbaren Ansatz um Gewichte zwischen den einzelnen Neuronen des Netzwerks zu propagieren. Der Grutext-pattern-knnndgedanke dabei ist es, dass Neuronen entsprechend höher gewichtet werden sollten, wenn sie mit anderen hoch gewichteten Neuronen in Beziehung stehen. Wenn also beispielsweise eine Silbe in vielen hoch gewichteten Worten auftaucht, wird sie selbst entsprechend höher gewichtet.

Neuronen eines kNN erlauben es aber nicht nur Konjunktionen wie etwa bei Mustern zu erlernen, sondern auch Disjunktionen. Disjunktionen sind insbesondere beim Erlernen von Grammatikregeln wichtig, wenn z. B. einzelne Worte als Nomen erkannt werden sollen. Wenn nun solche Disjunktionen erlernt werden sollen, können auch hier häufige Muster behilflich sein. Angenommen, es wurden durch den Mining Algorithmus bereits die folgenden häufigen Muster gefunden: “der Baum” (f=4), “der Hammer” (f=3) und “der Nagel” (f=6). Dann können diese Muster so umgeformt werden, dass ein neues, deutlich häufigeres Muster “der <NOMEN>” (f=13) und eine Disjunktion <NOMEN> = “Baum” oder “Hammer” oder “Nagel”, entsteht.

Top 10 der Python Bibliotheken für Data Science

Python gilt unter Data Scientists als Alternative zu R Statistics. Ich bevorzuge Python auf Grund seiner Syntax und Einfachheit gegenüber R, komme hinsichtlich der vielen Module jedoch häufig etwas durcheinander. Aus diesem Grund liste ich hier die – meiner Einschätzung nach – zehn nützlichsten Bibliotheken für Python, um einfache Datenanalysen, aber auch semantische Textanalysen, Predictive Analytics und Machine Learning in die Tat umzusetzen.

NumPy – Numerische Analyse

NumPy ist eine Open Source Erweiterung für Python. Das Modul stellt vorkompilierte Funktionen für die numerische Analyse zur Verfügung. Insbesondere ermöglicht es den einfachen Umgang mit sehr großen, multidimensionalen Arrays (Listen) und Matrizen, bietet jedoch auch viele weitere grundlegende Features (z. B. Funktionen der Zufallszahlenbildung, Fourier Transformation, linearen Algebra). Ferner stellt das NumPy sehr viele Funktionen mathematische Funktionen für das Arbeiten mit den Arrays und Matrizen bereit.

matplotlib – 2D/3D Datenvisualisierung

Die matplotlib erweitert NumPy um grafische Darstellungsmöglichkeiten in 2D und 3D. Das Modul ist in Kombination mit NumPy wohl die am häufigsten eingesetzte Visualisierungsbibliothek für Python.

Die matplotlib bietet eine objektorientierte API, um die dynamischen Grafiken in Pyhton GUI-Toolkits einbinden zu können (z. B. GTL+ oder wxPython).

NumPy und matplotlib werden auch mit den nachfolgenden Bibliotheken kombiniert.

Bokeh – Interaktive Datenvisualisierung

Während die Plot-Funktionen von matplotlib statisch angezeigt werden, kann in den Visualsierungsplots von Bokeh der Anwender interaktiv im Chart klicken und es verändern. Bokeh ist besonders dann geeignet, wenn die Datenvisualisierung als Dashboard im Webbrowser erfolgen soll.

Das Bild über diesen Artikel zeigt Visualiserungen mit dem Python Package Bokeh.

Pandas – Komplexe Datenanalyse

Pandas ist eine Bibliothek für die Datenverarbeitung und Datenanalyse mit Python. Es erweitert Python um Datenstrukturen und Funktionen zur Verarbeitung von Datentabellen. Eine besondere Stärke von Pandas ist die Zeitreihenanalyse. Pandas ist freie Software (BSD License).

Statsmodels – Statistische Datenanalyse

Statsmodels is a Python module that allows users to explore data, estimate statistical models, and perform statistical tests. An extensive list of descriptive statistics, statistical tests, plotting functions, and result statistics are available for different types of data and each estimator.

Die explorative Datenanalyse, statistische Modellierung und statistische Tests ermöglicht das Modul Statsmodels. Das Modul bringt neben vielen statistischen Funktionen auch eigene Plots (Visualisierungen) mit. Mit dem Modul wird Predictive Analytics möglich. Statsmodels wird häufig mit NumPy, matplotlib und Pandas kombiniert.

SciPy – Lineare Optimierung

SciPy ist ein sehr verbreitetes Mathematik-Modul für Python, welches den Schwerpunkt auf die mathematische Optimierung legt. Funktionen der linearen Algebra, Differenzialrechnung, Interpolation, Signal- und Bildverarbeitung sind in SciPy enthalten.

scikit-learn – Machine Learning

scikit-learn ist eine Framework für Python, das auf NumPy, matplotlob und SciPy aufsetzt, dieses jedoch um Funktionen für das maschinelle Lernen (Machine Learning) erweitert. Das Modul umfasst für das maschinelle Lernen notwendige Algorithmen für Klassifikationen, Regressionen, Clustering und Dimensionsreduktion.

Mlpy – Machine Learning

Alternativ zu scikit-learn, bietet auch Mlpy eine mächtige Bibliothek an Funktionen für Machine Learning. Mlpy setzt ebenfalls auf NumPy und SciPy, auf, erweitert den Funktionsumfang jedoch um Methoden des überwachten und unüberwachten maschinellen Lernens.

NLTK – Text Mining

NLTK steht für Natural Language Toolkit und ermöglicht den effektiven Einstieg ins Text Mining mit Python. Das Modul beinhaltet eigene (eher einfache) Visualisierungsmöglichkeiten zur Darstellung von Textmuster-Zusammenhängen, z. B. in Baumstrukturen. Für Text Mining und semantische Textanalysen mit Python gibt es wohl nichts besseres als NLTK.

Theano – Multidimensionale Berechnungen & GPU-Processing

Theano is a Python library that allows you to define, optimize, and evaluate mathematical expressions involving multi-dimensional arrays efficiently

Für multidimensionale Datenanalysen bzw. die Verarbeitung und Auswertung von multidimensionalen Arrays gibt es wohl nichts schnelleres als die Bibliothek Theano. Theano ist dabei eng mit NumPy verbunden.

Theano ermöglicht die Auslagerung der Berechnung auf die GPU (Grafikprozessor), was bis zu 140 mal schneller als auf der CPU sein soll. Getestet habe ich es zwar nicht, aber grundsätzlich ist es wahr, dass die GPU multidimensionale Arrays schneller verarbeiten kann, als die CPU. Zwar ist die CPU universeller (kann quasi alles berechnen), die GPU ist aber auf die Berechnung von 3D-Grafiken optimiert, die ebenfalls über multidimensionalen Vektoren verarbeitet werden.

Lieferantenkonsolidierung durch Analyse unstrukturierter Einkaufsdaten

Häufig ist in der Einkaufspraxis eine Beschaffung gleicher Artikel und Warengruppen bei den verschiedensten Lieferanten festzustellen. Eine schlechte Datenqualität sowie intransparente Prozesse sind ein ausschlaggebender Grund dafür, dass die Einkaufsleitung Möglichkeiten der Bündelung bei wenigen Lieferanten nicht vollständig erkennt und deren Einsparpotenziale nicht im vollen Umfang realisiert werden können. Schuld daran sind oft mehrere Faktoren, wie mangelhafte Soll-Prozesse, fehlende interne Richtlinien, inkonsistente Stammdaten und pauschale Buchungen über “Dummy”-Werte sowie falsch konfigurierte IT-Systeme. Data Quality Analytics, eine Sammlung von auf die Datenbasis anzuwendende analytische Testverfahren, können typische sowie untypische Datenfehler sowie Inkonsistenzen ausfindig gemacht und zudem bereinigt werden.

Sollten die Bestellungen über pauschale Dummy-Positionen (beispielsweise “Betriebsmittel” oder “Fremdleistungen”) verbucht werden, können Bündelungspotenziale vom strategischen Einkauf nicht so einfach erkannt werden. Hinzu kommt häufig eine mangelhafte Pflege von Matieralstammdaten. Sind in den Bewegungsdaten – hierzu zählen insbesondere Daten über Aufträge, Bestellungen, Wareneingänge, Lagerverbräuche, Rechnungen und Zahlungen – jedoch wenigstens vereinzelt Texte über die Position (z. B. Artikelname) vorhanden, können über Textalgorithmen besonders hervorstechende Wörter aus diesen semi-strukturierten Daten extrahiert, nach bestimmten Kontextmodellen gefiltert und aggregiert werden. Wenn beispielsweise in einzelnen Positionstexten Begriffe vorkommen, die bestimmte Voraussetzungen erfüllen – beispielsweise ein Matching der jeweiligen Begriffe untereinander oder mit Wortlisten (z. B. dem Duden) – kann über eine Netzwerkanalyse ermittelt werden, über welche Lieferanten und verantwortliche Stellen gleichartige Positionen bezogen werden. In der einfachsten Variante werden die Begriffe gefiltert, die über mehrere Positonstexte wiederholt vorkommen.  Aus dem gesamten Buchungsstoff können so automatisiert Bündelungspotenziale im vollen Umfang über ein Vorschlagssystem aufgedeckt werden. Dies funktioniert auch dann, wenn der Einkauf über mehrere Betriebe mit unterschiedlichen IT-Systemen betrachtet werden soll. Diese neuartigen Analyseformen ermöglichen für den Einkauf neue Kostensenkungspotenzialeoftmals im zweistelligen Prozentbereich – die vom strategischen Einkauf verhältnismäßig leicht zu realisieren sind.