Tag Archive for: Data Mining

Benjamin Aunkofer

Überwachtes vs unüberwachtes maschinelles Lernen

/in , , , , , , , /by

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

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

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

Trainiere dir deinen Algorithmus mit überwachtem maschinellen Lernen

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

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

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

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

Mit unüberwachtem Lernen verborgene Strukturen identifizieren

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

Benjamin Aunkofer

Was ist eigentlich Machine Learning? Artikelserie

/in , , , , , , , /by

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

Machine Learning ist nicht neu, aber innovativ!

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

Maschinelles Lernen vs künstliche Intelligenz

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

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

Machine Learning vs Deep Learning

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

Machine Learning vs Data Mining

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

Scikit-Learn Machine Learning Roadmap

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

Markus Lang

Unsupervised Learning in R: K-Means Clustering

/in , , , , , /by

Die Clusteranalyse ist ein gruppenbildendes Verfahren, mit dem Objekte Gruppen – sogenannten Clustern zuordnet werden. Die dem Cluster zugeordneten Objekte sollen möglichst homogen sein, wohingegen die Objekte, die unterschiedlichen Clustern zugeordnet werden möglichst heterogen sein sollen. Dieses Verfahren wird z.B. im Marketing bei der Zielgruppensegmentierung, um Angebote entsprechend anzupassen oder im User Experience Bereich zur Identifikation sog. Personas.

Es gibt in der Praxis eine Vielzahl von Cluster-Verfahren, eine der bekanntesten und gebräuchlichsten Verfahren ist das K-Means Clustering, ein sog. Partitionierendes Clusterverfahren. Das Ziel dabei ist es, den Datensatz in K Cluster zu unterteilen. Dabei werden zunächst K beliebige Punkte als Anfangszentren (sog. Zentroiden) ausgewählt und jedem dieser Punkte der Punkt zugeordnet, zu dessen Zentrum er die geringste Distanz hat. K-Means ist ein „harter“ Clusteralgorithmus, d.h. jede Beobachtung wird genau einem Cluster zugeordnet. Zur Berechnung existieren verschiedene Distanzmaße. Das gebräuchlichste Distanzmaß ist die quadrierte euklidische Distanz:

D^2 = \sum_{i=1}^{v}(x_i - y_i)^2

Nachdem jede Beobachtung einem Cluster zugeordnet wurde, wird das Clusterzentrum neu berechnet und die Punkte werden den neuen Clusterzentren erneut zugeordnet. Dieser Vorgang wird so lange durchgeführt bis die Clusterzentren stabil sind oder eine vorher bestimmte Anzahl an Iterationen durchlaufen sind.
Das komplette Vorgehen wird im Folgenden anhand eines künstlich erzeugten Testdatensatzes erläutert.

Zunächst wird ein Testdatensatz mit den Variablen „Alter“ und „Einkommen“ erzeugt, der 12 Fälle enthält. Als Schritt des „Data preprocessing“ müssen zunächst beide Variablen standardisiert werden, da ansonsten die Variable „Alter“ die Clusterbildung zu stark beeinflusst.

Das Ganze geplottet:

Wie bereits eingangs erwähnt müssen Cluster innerhalb möglichst homogen und zu Objekten anderer Cluster möglichst heterogen sein. Ein Maß für die Homogenität die „Within Cluster Sums of Squares“ (WSS), ein Maß für die Heterogenität „Between Cluster Sums of Squares“ (BSS).

Diese sind beispielsweise für eine 3-Cluster-Lösung wie folgt:

Sollte man die Anzahl der Cluster nicht bereits kennen oder sind diese extern nicht vorgegeben, dann bietet es sich an, anhand des Verhältnisses von WSS und BSS die „optimale“ Clusteranzahl zu berechnen. Dafür wird zunächst ein leerer Vektor initialisiert, dessen Werte nachfolgend über die Schleife mit dem Verhältnis von WSS und WSS gefüllt werden. Dies lässt sich anschließend per „Screeplot“ visualisieren.

Die „optimale“ Anzahl der Cluster zählt sich am Knick der Linie ablesen (auch Ellbow-Kriterium genannt). Alternativ kann man sich an dem Richtwert von 0.2 orientieren. Unterschreitet das Verhältnis von WSS und BSS diesen Wert, so hat man die beste Lösung gefunden. In diesem Beispiel ist sehr deutlich, dass eine 3-Cluster-Lösung am besten ist.

Fazit: Mit K-Means Clustering lassen sich schnell und einfach Muster in Datensätzen erkennen, die, gerade wenn mehr als zwei Variablen geclustert werden, sonst verborgen blieben. K-Means ist allerdings anfällig gegenüber Ausreißern, da Ausreißer gerne als separate Cluster betrachtet werden. Ebenfalls problematisch sind Cluster, deren Struktur nicht kugelförmig ist. Dies ist vor der Durchführung der Clusteranalyse mittels explorativer Datenanalyse zu überprüfen.

Anne Rozinat & Christian W. Günther

Consider Anonymization – Process Mining Rule 3 of 4

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

This is article no. 3 of the four-part article series Privacy, Security and Ethics in Process Mining.

Read this article in German:
“Datenschutz, Sicherheit und Ethik beim Process Mining – Regel 3 von 4“

If you have sensitive information in your data set, instead of removing it you can also consider the use of anonymization. When you anonymize a set of values, then the actual values (for example, the employee names “Mary Jones”, “Fred Smith”, etc.) will be replaced by another value (for example, “Resource 1”, “Resource 2”, etc.).

If the same original value appears multiple times in the data set, then it will be replaced with the same replacement value (“Mary Jones” will always be replaced by “Resource 1”). This way, anonymization allows you to obfuscate the original data but it preserves the patterns in the data set for your analysis. For example, you will still be able to analyze the workload distribution across all employees without seeing the actual names.

Some process mining tools (Disco and ProM) include anonymization functionality. This means that you can import your data into the process mining tool and select which data fields should be anonymized. For example, you can choose to anonymize just the Case IDs, the resource name, attribute values, or the timestamps. Then you export the anonymized data set and you can distribute it among your team for further analysis.

Do:

  • Determine which data fields are sensitive and need to be anonymized (see also the list of common process mining attributes and how they are impacted if anonymized).
  • Keep in mind that despite the anonymization certain information may still be identifiable. For example, there may be just one patient having a very rare disease, or the birthday information of your customer combined with their place of birth may narrow down the set of possible people so much that the data is not anonymous anymore.

Don’t:

  • Anonymize the data before you have cleaned your data, because after the anonymization the data cleaning may not be possible anymore. For example, imagine that slightly different customer category names are used in different regions but they actually mean the same. You would like to merge these different names in a data cleaning step. However, after you have anonymized the names as “Category 1”, “Category 2”, etc. the data cleaning cannot be done anymore.
  • Anonymize fields that do not need to be anonymized. While anonymization can help to preserve patterns in your data, you can easily lose relevant information. For example, if you anonymize the Case ID in your incident management process, then you cannot look up the ticket number of the incident in the service desk system anymore. By establishing a collaborative culture around your process mining initiative (see guideline No. 4) and by working in a responsible, goal-oriented way, you can often work openly with the original data that you have within your team.
Christoph Gresch

Der Blick für das Wesentliche: Die Merkmalsselektion

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

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

Die Theorie: Merkmalsselektion

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

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

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

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

Entwicklungsgrundlage

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

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

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

Python-Bibliotheken

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

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

Daten vorbereiten

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

1. Verfahren: RFECV

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

2. Verfahren: Random Forest-Klassifikator

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

3. Verfahren: Select K Best

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

Ergebnisse

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

 

Selektionsverfahren

Anzahl der Merkmale

Erfolgsrate Klassifikation
Ohne

561

93,96%
RFECV

314

94,03%
Random Forest

118

90,43%
Select K Best

186

92,30%

 

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

Anne Rozinat & Christian W. Günther

Clarify Goal of the Analysis – Process Mining Rule 1 of 4

/in , , , , , , , /by

This is article no. 1 of the four-part article series Privacy, Security and Ethics in Process Mining.

Read this article in German:
“Datenschutz, Sicherheit und Ethik beim Process Mining – Regel 1 von 4“

Clarify Goal of the Analysis

The good news is that in most situations Process Mining does not need to evaluate personal information, because it usually focuses on the internal organizational processes rather than, for example, on customer profiles. Furthermore, you are investigating the overall process patterns. For example, a process miner is typically looking for ways to organize the process in a smarter way to avoid unnecessary idle times rather than trying to make people work faster.

However, as soon as you would like to better understand the performance of a particular process, you often need to know more about other case attributes that could explain variations in process behaviours or performance. And people might become worried about where this will lead them.

Therefore, already at the very beginning of the process mining project, you should think about the goal of the analysis. Be clear about how the results will be used. Think about what problem are you trying to solve and what data you need to solve this problem.

Do:

  • Check whether there are legal restrictions regarding the data. For example, in Germany employee-related data cannot be used and typically simply would not be extracted in the first place. If your project relates to analyzing customer data, make sure you understand the restrictions and consider anonymization options (see guideline No. 3).
  • Consider establishing an ethical charter that states the goal of the project, including what will and what will not be done based on the analysis. For example, you can clearly state that the goal is not to evaluate the performance of the employees. Communicate to the people who are responsible for extracting the data what these goals are and ask for their assistance to prepare the data accordingly.

Don’t:

  • Start out with a fuzzy idea and simply extract all the data you can get. Instead, think about what problem are you trying to solve? And what data do you actually need to solve this problem? Your project should focus on business goals that can get the support of the process managers you work with (see guideline No. 4).
  • Make your first project too big. Instead, focus on one process with a clear goal. If you make the scope of your project too big, people might block it or work against you while they do not yet even understand what process mining can do.
Erwin Enzenhofer

R als Tool im Process Mining

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

Die Open Source Sprache R ermöglicht eine Vielzahl von Analysemöglichkeiten, die von einer einfachen beschreibenden Darstellung eines Prozesses bis zur umfassenden statistischen Analyse reicht. Dabei können Daten aus einem Manufacturing Execution System, kurz MES, als Basis der Prozessanalyse herangezogen werden. R ist ein Open Source Programm, welches sich für die Lösung von statischen Aufgaben im Bereich der Prozessoptimierung sehr gut eignet, erfordert jedoch auf Grund des Bedienungskonzepts als Scriptsprache, grundlegende Kenntnisse der Programmierung. Aber auch eine interaktive Bedienung lässt sich mit einer Einbindung der Statistikfunktionen in ein Dashboard erreichen. Damit können entsprechend den Anforderungen, automatisierte Analysen ohne Programmierkenntnisse realisiert werden.

Der Prozess als Spagetti Diagramm

Um einen Überblick zu erhalten, wird der Prozess in einem „process value flowchart“, ähnlich einem Spagetti‐ Diagramm dargestellt und je nach Anforderung mit Angaben zu den Key Performance Indicators ergänzt. Im konkreten Fall werden die absolute Anzahl und der relative Anteil der bearbeiteten Teile angegeben. Werden Teile wie nachfolgend dargestellt, aufgrund von festgestellten Mängel bei der Qualitätskontrolle automatisiert ausgeschleust, können darüber Kennzahlen für den Ausschuss ermittelt werden.

Der Prozess in Tabellen und Diagrammen

Im folgenden Chart sind grundlegende Angaben zu den ausgeführten Prozessschritten, sowie deren Varianten dargestellt. Die Statistikansicht bietet eine Übersicht zu den Fällen, den sogenannte „Cases“, sowie zur Dauer und Taktzeit der einzelnen Aktivitäten. Dabei handelt es sich um eine Fertigungsline mit hohem Automatisierungsgrad, bei der jeder Fertigungsschritt im MES dokumentiert wird. Die Tabelle enthält statistische Angaben zur Zykluszeit, sowie der Prozessdauer zu den einzelnen Aktivitäten. In diesem Fall waren keine Timestamps für das Ende der Aktivität vorhanden, somit konnte die Prozessdauer nicht berechnet werden.

Die Anwendung von Six Sigma Tools

R verfügt über eine umfangreiche Sammlung von Bibliotheken zur Datendarstellung, sowie der Prozessanalyse. Darin sind auch Tools aus Six Sigma enthalten, die für die weitere Analyse der Prozesse eingesetzt werden können. In den folgenden Darstellungen wird die Möglichkeit aufgezeigt, zwei Produktionszeiträume, welche über eine einfache Datumseingabe im Dashboard abgegrenzt werden, gegenüber zu stellen. Dabei handelt es sich um die Ausbringung der Fertigung in Stundenwerten, die für jeden Prozessschritt errechnet wird. Das xbar und r Chart findet im Bereich der Qualitätssicherung häufig Anwendung zur ersten Beurteilung des Prozessoutputs.

Zwei weitere Six Sigma typische Kennzahlen zur Beurteilung der Prozessfähigkeit sind der Cp und Cpk Wert und deren Ermittlung ein Bestandteil der R Bibliotheken ist. Bei der Berechnung wird von einer Normalverteilung der Daten ausgegangen, wobei das Ergebnis aus der Überprüfung dieser Annahme im Chart durch Zahlen, als auch grafisch dargestellt wird.

Von Interesse ist auch die Antwort auf die Frage, welchem Trend folgt der Prozess? Bereits aus der Darstellung der beiden Produktionszeiträume im Box‐Whiskers‐Plot könnte man anhand der Mediane auf einen Trend zu einer Verschlechterung der Ausbringung schließen, den der Interquartilsabstand nicht widerspiegelt. Eine weitere Absicherung einer Aussage über den Trend, kann über einen statistischen Vergleichs der Mittelwerte erfolgen.

Der Modellvergleich

Besteht die Anforderung einer direkten Gegenüberstellung des geplanten, mit dem vorgefundenen, sogenannten „Discovered Model“, ist aufgrund der Komplexität beim Modellvergleich, dieser in R mit hohem Programmieraufwand verbunden. Besser geeignet sind dafür spezielle Process Miningtools. Diese ermöglichen den direkten Vergleich und unterstützen bei der Analyse der Ursachen zu den dargestellten Abweichungen. Bei Produktionsprozessen handelt es sich meist um sogenannte „Milestone Events“, die bei jedem Fertigungsschritt durch das MES dokumentiert werden und eine einfache Modellierung des Target Process ermöglichen. Weiterführende Analysen der Prozessdaten in R sind durch einen direkten Zugriff über ein API realisierbar oder es wurde vollständig integriert. Damit eröffnen sich wiederum die umfangreichen Möglichkeiten bei der statistischen Prozessanalyse, sowie der Einsatz von Six Sigma Tools aus dem Qualitätsmanagement. Die Analyse kann durch eine, den Kundenanforderungen entsprechende Darstellung in einem Dashboard vereinfacht werden, ermöglicht somit eine zeitnahe, weitgehend automatisierte Prozessanalyse auf Basis der Produktionsdaten.

Resümee

Process Mining in R ermöglicht zeitnahe Ergebnisse, die bis zur automatisierten Analyse in Echtzeit reicht. Der Einsatz beschleunigt erheblich das Process Controlling und hilft den Ressourceneinsatz bei der Datenerhebung, sowie deren Analyse zu reduzieren. Es kann als stand‐alone Lösung zur Untersuchung des „Discovered Process“ oder als Erweiterung für nachfolgende statistische Analysen eingesetzt werden. Als stand‐alone Lösung eignet es sich für Prozesse mit geringer Komplexität, wie in der automatisierten Fertigung. Besteht eine hohe Diversifikation oder sollen standortübergreifende Prozessanalysen durchgeführt werden, übersteigt der Ressourcenaufwand rasch die Kosten für den Einsatz einer Enterprise Software, von denen mittlerweile einige angeboten werden.

 

Anne Rozinat & Christian W. Günther

Datenschutz, Sicherheit und Ethik beim Process Mining – Regel 4 von 4:

/in , , , , /by

Dieser Artikel ist Teil 4 von 4 aus der Reihe Datenschutz, Sicherheit und Ethik beim Process Mining.

english-flagRead this article in English:
“Privacy, Security and Ethics in Process Mining – Rule 4 of 4“


Schaffung einer Kooperationskultur

Möglicherweise ist der wichtigste Bestandteil bei der Schaffung eines verantwortungsbewussten Process Mining-Umfeldes der Aufbau einer Kooperationskultur innerhalb Ihrer Organisation. Process Mining kann die Fehler Ihrer Prozesse viel eindeutiger aufzeigen, als das manchen Menschen lieb ist. Daher sollten Sie Change Management-Experten miteinbeziehen wie beispielsweise Lean-Coaches, die es verstehen, Menschen dazu zu bewegen, sich gegenseitig “die Wahrheit“ zu sagen (siehe auch: Erfolgskriterien beim Process Mining).

Darüber hinaus sollten Sie vorsichtig sein, wie Sie die Ziele Ihres Process Mining-Projektes vermitteln und relevante Stakeholder so einbeziehen, dass ihre Meinung gehört wird. Ziel ist es, eine Atmosphäre zu schaffen, in der die Menschen nicht für ihre Fehler verantwortlich gemacht werden (was nur dazu führt, dass sie verbergen, was sie tun und gegen Sie arbeiten), sondern ein Umfeld zu schaffen, in dem jeder mitgenommen wird und wo die Analyse und Prozessverbesserung ein gemeinsames Ziel darstellt, für das man sich engagiert.

Was man tun sollte:

  • Vergewissern Sie sich, dass Sie die Datenqualität überprüfen, bevor Sie mit der Datenanalyse beginnen, bestenfalls durch die Einbeziehung eines Fachexperten bereits in der Datenvalidierungsphase. Auf diese Weise können Sie das Vertrauen der Prozessmanager stärken, dass die Daten widerspiegeln, was tatsächlich passiert und sicherstellen, dass Sie verstanden haben, was die Daten darstellen.
  • Arbeiten Sie auf iterative Weise und präsentieren Sie Ihre Ergebnisse als Ausgangspunkt einer Diskussion bei jeder Iteration. Geben Sie allen Beteiligten die Möglichkeit zu erklären, warum bestimmte Dinge geschehen und seien Sie offen für zusätzliche Fragen (die in der nächsten Iteration aufgegriffen werden). Dies wird dazu beitragen, die Qualität und Relevanz Ihrer Analyse zu verbessern, als auch das Vertrauen der Prozessverantwortlichen in die endgültigen Projektergebnisse zu erhöhen.

Was man nicht tun sollte:

  • Voreilige Schlüsse ziehen. Sie können nie davon ausgehen, dass Sie alles über den Prozess wissen. Zum Beispiel können langsamere Teams die schwierigen Fälle behandeln, es kann gute Gründe geben, von dem Standardprozess abzuweichen und Sie sehen möglicherweise nicht alles in den Daten (beispielsweise Vorgänge, die außerhalb des Systems durchgeführt werden). Indem Sie konstant Ihre Beobachtungen als Ausgangspunkt für Diskussionen anbringen und den Menschen die Möglichkeit einräumen, Ihre Erfahrung und Interpretationen mitzugeben, beginnen Sie, Vertrauen und die Kooperationskultur aufzubauen, die Process Mining braucht.
  • Schlussfolgerungen erzwingen, die ihren Erwartungen entsprechen oder die sie haben möchten, indem Sie die Daten falsch darstellen (oder Dinge darstellen, die nicht wirklich durch die Daten unterstützt werden). Führen Sie stattdessen ganz genau Buch über die Schritte, die Sie bei der Datenaufbereitung und in Ihrer Process-Mining-Analyse ausgeführt haben. Wenn Zweifel an der Gültigkeit bestehen oder es Fragen zu Ihrer Analysebasis gibt, dann können Sie stets zurückkehren und beispielsweise zeigen, welche Filter bei den Daten angewendet wurden, um zu der bestimmten Prozesssicht zu gelangen, die Sie vorstellen.
Vishal Bhalla

Statistical Relational Learning – Part 2

/in , , , , , , , /by

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

MLN Template – explained

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

Weight Learning

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

and captures the marginal distribution of the corresponding predicate.

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

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

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

Weight Learning – An Example

Note: All examples are highlighted in the Alchemy MLN format

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

The input predicateFormula.mln file contains

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

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

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

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

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

Inference

The definition goes as follows:

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

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

which is in turn equivalent to this formula.

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

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

Inference – An Example

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

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

Tool-kits

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

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

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

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

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

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

 

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

Back to Part I – Statistical Relational Learning

Additional Links:

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

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

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

Dr. Dietrich Wettschereck

Toolkits & Services für Semantische Textanalysen

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

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.