Lade Inhalt...

Markov-basiertes Process Mining

Seminararbeit 2011 37 Seiten

Informatik - Wirtschaftsinformatik

Leseprobe

Inhaltsverzeichnis

Abkürzungsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

1. Einleitung und Motivation

2. Process Mining
2.1 Begriffsklärung
2.2 Sichten des Process Mining
2.3 Einsatzmöglichkeiten
2.4 Grundkonzepte
2.4.1 Einführung
2.4.2 Annahmen
2.4.3 Log-basierte Ordnungsrelationen
2.4.4 Mining-Prozess
2.4.5 Herausforderungen
2.5 Methoden
2.7 Ordnungsrahmen

3. Markov Modelle
3.1 Einführung
3.2 Markov-Ketten
3.3 Markov Modelle

4. Markov-basiertes Process Mining
4.1 Einführung
4.2 Endlicher Zustandsautomat (FSM)
4.3 Parametrisierung
4.4 Beispiel
4.5 Processing
4.5.1 Erstellung von Wahrscheinlichkeitstabellen
4.5.2 Konstruktion eines gerichteten Graphen
4.5.3 Auflösung überladener Knoten
4.5.4 Konvertierung in einen endlichen Zustandsautomaten
4.5.5 Zusammenführung nichtdeterministischer Transitionen
4.6 Metriken zur Erkennung paralleler Abläufe
4.6.1 Vorbemerkung
4.6.2 Entropy
4.6.3 Event Type Counts
4.6.4 Periodicy
4.6.5 Deciding Causality
4.7 Evaluation
4.8 „Related Work“

5. Zusammenfassung und Fazit

Literaturverzeichnis

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Abbildungsverzeichnis

Abb. 1: Petri-Netz (Beispiel)

Abb. 2: Beispiel - Übergangsgraph

Abb. 3: Endlicher Automat - Beispiel

Abb. 4: Beispielstream

Abb. 5: Ereignisgraph nach Schritt 2 (Markov)

Abb. 6: Ereignisgraph nach Schritt 3 (Markov)

Abb. 7: Endlicher Zustandsautomat nach Schritt 4 (Markov)

Abb. 8: Endlicher Zustandsautomat nach Schritt 5 (Markov)

Tabellenverzeichnis

Tabelle 1: Event-Log (Beispiel)

Tabelle 2: Ordnungsrahmen Process Mining

Tabelle 3: Wahrscheinlichkeitsverteilung 1. Ordnung (Markov)

Tabelle 4: Wahrscheinlichkeitsverteilung 2. Ordnung (Markov)

1. Einleitung und Motivation

Seit Anfang der 1990er Jahre hält die modellbasierte Ausführung von Prozes- sen immer mehr Einzug in Unternehmen und deren Informationssysteme. Bei- spielsweise werden im Bereich der Software-Entwicklung vor der Implemen- tierung Modelle, der zu unterstützenden Prozesse, erstellt, sodass Missver- ständnisse im Vorfeld beseitigt werden und somit die Erfolgsaussichten eines Projektes gesteigert werden. Gleiches gilt im betrieblichen Kontext - idealer- weise werden hier Prozessmodelle entworfen, welche später in die Ausführung durch menschliche oder maschinelle Ressourcen überführt werden. Geschäfts- prozessmanagement- oder Workflowmanagementsysteme sind heute sogar in der Lage die grafisch visualisierten Modelle direkt und ohne Umwege auszu- führen.

Alle an einem solchen Prozess beteiligten Informationssysteme, beispielsweise ERP (Enterprise Ressource Planung), CRM (Customer-Relationship- Management) oder SCM (Supply Chain Management), stellen Informationen zu den einzelnen Prozessschritten bereit, wodurch das Monitoring und die Ana- lyse der Prozesse ermöglicht wird. Die Technologien dazu fallen unter die Schlagwörter BPA (Business Process Analysis) und BAM (Business Activity Monitoring). Die Existenz dieser und anderer Schlagwörter kennzeichnen die Notwendigkeit entsprechender Software, wobei Process Mining einen ent- scheidenden Beitrag liefert.

Das Ziel des Process Mining besteht in der Extraktion explizierter Prozessmodelle anhand der protokollierten Prozessinformationen, welche im Allgemeinen in Log-Dateien abgelegt werden. Dabei sollen nicht nur die Prozessabläufe analysiert, sondern auch kausale Zusammenhänge zwischen den einzelnen Aktivitäten hergestellt werden. Hier müssen allerdings bestimmte Annahmen getroffen und Hindernisse überwunden werden.

In Kapitel 2 der vorliegenden Arbeit wird deshalb zunächst auf das Process Mining im Allgemeinen eingegangen. Hier werden die Grundlagen vermittelt, die für das korrekte Verständnis der Problemstellung notwendig sind, sowie ein Ordnungsrahmen entworfen, um die verschiedenen Themenfacetten korrekt einordnen zu können. Kapitel 3 setzt sich mit Markov Modellen auseinander, um die Grundlagen für das Verständnis der nachfolgenden Kapitel zu vermit- teln. Kapitel 4 beschäftigt sich anschließend mit dem Process Mining im Spe- ziellen - genauer gesagt mit der Theorie und der Anwendung von Markov Ket- ten im Process Mining. Dieses Kapitel stellt somit den Schwerpunkt der Arbeit dar. Anschließend werden die gewonnenen Kenntnisse in Kapitel 5 zusam- mengefasst und im Fazit konkretisiert.

2. Process Mining

2.1 Begriffsklärung

Der Begriff des Process Mining, häufig in der Literatur auch als Workflow Mining oder Control Flow Mining bezeichnet, hat seinen Ursprung im Data Mining. Beim Data Mining wiederum handelt es sich um einen Begriff mit populärwissenschaftlichem Ursprung, welcher sowohl in den Natur- als auch in den Wirtschaftswissenschaften genutzt wird1. Aufgrund des engen Bezugs soll zunächst eine grundlegende Definition des Data Mining angeboten werden.

Data Mining beschreibt „die Extraktion implizit vorhandenen, nicht trivialen und nützlichen Wissens aus großen, dynamischen, relativ komplex strukturier- ten Datenbeständen. […]“. Es wird versucht „Muster zu identifizieren, daraus Regeln abzuleiten, Unterschiede zwischen Gruppen von Datensätzen zu erken- nen, diese Gruppen beschreibende Attribute zu bestimmen, die repräsentativs- ten Beispiele zu finden und Gleichungen zu konstruieren, die für numerische Variablen gelten“.2

Das Process Mining, als eine spezielle Form des Data Mining, zielt auf ein bestimmtes Wissen ab - das Prozesswissen3. Demnach wird versucht, aus vorhandenen Datenbeständen genau das Wissen zu extrahieren, welches für die Beschreibung eines Prozesses notwendig ist.

Ebenfalls beschreiben Bissantz und Hagedorn4, ebenso wie Peterson5 in Ihren Beiträgen allgemeine Charakteristiken, welche für Verfahren, die dem Data Mining zuzuordnen sind, typisch erscheinen:

„limately understandable“: Die gewonnen Informationen werden in verständlicher Form (z.B. Text oder Grafik) präsentiert oder von einer Software weiterverarbeitet.

„valid“: Die generierten Thesen sind mit einer statistischen Sicherheit versehen.

„novel“: Der Fokus liegt auf neuen Erkenntnissen.

„non-trivial“: Die ermittelten Informationen sind nicht trivial.

„potential useful“: Die gewonnenen Information sind nicht immer offensichtlich bewertbar, aber nützlich.

„runtime“: Die Laufzeit des Mining-Prozesses liegt in einem vertretba- ren Rahmen und sollte in Abhängigkeit der Anzahl der zu untersuchen- den Datensätze nicht stärker als ein Polynom niedrigen Grades steigen.

Der Bezug dieser Charakteristiken wird in den nachfolgenden Kapiteln ver- deutlicht.

2.2 Sichten des Process Mining

Beim Process Mining wird zwischen drei grundlegenden Sichten unterschieden: der Prozesssicht, der Organisationssicht und der Fallsicht6.

Bei der Prozesssicht liegt der Fokus auf dem Kontrollfluss, also beispielsweise der Reihenfolge von Aktivitäten. Das Ziel dieser Sichtweise ist die Erfassung eines Modells, welches alle möglichen Prozesspfade bestmöglich abbildet. Dies wird im Allgemeinen mit Petri-Netzen, Ereignisgesteuerte Prozessketten (EPK) oder endlichen Zustandsautomaten (FSM = Finite State Machine) reali- siert. Der Fokus der vorliegenden Arbeit liegt auf der Prozesssicht.

Die Organisationssicht beschäftigt sich mit den innerbetrieblichen Organisationsstrukturen. Es wird also beispielsweise untersucht, welche Akteure an einem Prozess beteiligt sind und in welcher Beziehung diese zueinander stehen. Es wird auf diese Weise eine Art soziales Netzwerk erstellt, welches Gruppen, Zugehörigkeiten und Beziehungen abbildet.

Die Fallsicht fokussiert sich auf die Eigenschaften einzelner Prozessinstanzen. Diese Fälle können nicht nur durch die Prozesspfade oder die zugehörigen Akteure charakterisiert werden, sondern vielmehr auch über fallspezifische Werte, wie beispielsweise die Anzahl an Produkten in einer Bestellung.

2.3 Einsatzmöglichkeiten

Die Grundidee des Process Mining besteht in der Identifizierung, dem Monito- ring und der Optimierung von realen Prozessen durch die Extrahierung von Wissen aus Ereignisprotokollen7. Auf diese unterschiedlichen Einsatzmöglichkeiten soll im Folgenden kurz eingegangen werden.

Der naheliegendste Gedanke ist die Identifikation der Ablaufstrukturen im Un- ternehmen. Bisher führte der Weg zu einem Prozessmodell beispielsweise über die Durchführung von Interviews, wobei Mitarbeiter zu Ihren „eigenen“ Pro- zessen befragt werden. Modelle, die mit Process Mining-Technologien gewon- nen werden, sind, anders als Modelle, die mit klassischen Techniken entwickelt werden, objektiv und reflektieren somit den tatsächlichen Prozessablauf. Man bezeichnet dieses Vorgehen zur reinen Prozessidentifikation als „Process Dis- covery“.

Sollte bereits ein Prozessmodell vorhanden sein, so können auch hier sinnvolle Einsatzmöglichkeiten identifiziert werden. Das ermittelte Prozessmodell kann dazu genutzt werden, es mit dem bereits a priori vorhanden Prozessmodell zu vergleichen. Somit werden Diskrepanzen zwischen dem Soll-Zustand und dem Ist-Zustand identifiziert und analysiert. Man spricht dabei von der Delta- Analyse8, die Einsatzmöglichkeit wird im Allgemeinen als „Conformance“ bezeichnet. Weiterhin kann die „Conformance“ auch durch Organisationsmo- delle, Business Rules, Qualitätsanforderungen (Quality of Service = QoS) und vielen mehr geprüft werden9.

Grobe und häufige Abweichung des Ist-Zustands vom Soll-Zustand stellen jedoch die Korrektheit sowie die Angemessenheit des a priori Modells in Fra- gen. Somit besteht ebenfalls die Möglichkeit, das a priori Modell durch die Erkenntnisse der Delta-Analyse zu adaptieren und somit an die realen Struktu- ren anzugleichen. Folglich kann Process Mining ebenfalls als eine Methode zur Verbesserung der Prozessqualität durch Ableitung von Prozesswissen verstan- den werden10.

Ferner können die gewonnenen Prozessinformationen genutzt werden, um das a priori Modell zu erweitern. Hierbei wird ohne die vorherige Überprüfung der „Conformance“ eine Anreicherung des vorhandenen Modells mit neuen Infor mationen (z.B. Performance-Daten) durchgeführt11. Dies bezeichnet man als „Extension“.

2.4 Grundkonzepte

2.4.1 Einführung

In diesem Teilkapitel soll das generelle Vorgehen beim Process Mining vermittelt werden. Es existiert bereits eine große Anzahl an methodischen Ansätzen, in der nachfolgenden Erläuterungen wird jedoch auf den -Algorithmus Bezug genommen, da dieser die Grundlage für diverse weitere Algorithmen, wie beispielsweise den + oder den -Algorithmus bildet.

2.4.2 Annahmen

Wie bereits angesprochen soll durch das Process Mining Prozesswissen über Ereignis-Protokolle (im Folgenden „Logs“ genannt) extrahiert werden. Bezüglich dieser Logs müssen einige Annahmen12 getroffen werden, welche für deren Interpretation obligatorisch sind:

1. Jedes Ereignis verweist auf eine Aktivität (Task)
2. Jedes Ereignis verweist auf eine Prozessinstanz (Case)
3. Jedes Ereignis hat einen Initiator auf welchen verwiesen wird
4. Jedes Ereignis hat einen Zeitstempel

Tabelle 1 stellt ein solches Event-Log exemplarisch dar.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Event-Log (Beispiel) 13

2.4.3 Log-basierte Ordnungsrelationen

Um den in Tabelle 1 vorgestellten Log auswerten und in ein Modell (in diesem Fall Petri-Netz) überführen zu können, bedarf es einiger Regeln. Im Falle des α-Algorithmus, ebenso wie in diverse anderen Algorithmen werden dazu Ordnungsrelationen eingesetzt, welche die notwendigen Regeln zur Interpretation des Logs zur Verfügung stellt:14

Sei T eine Menge von Tasks, W ein Workflow Log über T und ein Log Trace, sodass

1. Direkter Nachfolger:

D.h. in irgendeinem Log Trace tritt Task a vor Task b auf. Diese Re- lation bildet die Grundlage, auf welcher alle weiteren Relationen auf- bauen.

Abbildung in dieser Leseprobe nicht enthalten

2. Kausalität: [Abbildung in dieser Leseprobe nicht enthalten]

D.h. wenn Task a und Task b zusammen auftreten, folgt immer b auf a

3. Auswahl: [Abbildung in dieser Leseprobe nicht enthalten]

D.h. Task a und Task b können nicht zusammen in auftreten. Das bedeutet, dass immer nur einer der beiden Tasks aufgeführt werden kann, was wiederum einem OR-Konstrukt entspricht.

4. Parallelität: [Abbildung in dieser Leseprobe nicht enthalten]

D.h. es wird sowohl Task a als auch Task b ausgeführt, die Reihenfolge ist dabei beliebig. Dies entspricht einem AND-Konstrukt.

2.4.4 Mining-Prozess

2.4.4.1 Pre-Processing

Die erste von allgemein drei Phasen des Mining-Prozesses beschäftigt sich mit der Extraktion der relevanten Log-Traces aus den vorhandenen Logs. Da Log- Dateien zu einem bestimmten Zeitpunkt aus den Systemen exportiert werden ist absehbar, dass einige Prozessinstanzen nicht vollständig ausgeführt wurden. Ebenfalls existieren in manchen Fällen Prozessinstanzen, welche aufgrund von Fehlern abgebrochen wurden und somit ebenfalls nicht vollständig sind. Diese Log-Traces würden in der eigentlichen Processing-Phase unerwünschte Effekte verursachen, da Prozesse analysiert würden, welche so nicht existieren. Aus diesem Grund müssen die entsprechenden Log-Einträge entfernt werden.

Beim Process Mining handelt es sich prinzipiell um einen induktiven Lernpro- zess aus Beispielen15. Hierbei kann durchaus zwischen positiven und negativen Beispielen unterschieden werden, wobei es sich bei positiven Beispielen um korrekt ausgeführte Prozess-Instanzen und bei negativen Beispielen um fehler- haft Ausführung oder Abbrüche handelt. Die Analyse der negativen Beispiele kann dabei als das Lernen aus Fehlern verstanden werden. Es wäre an dieser Stelle also auch denkbar, statt der korrekten Instanzen, die fehlerhaften Instan- zen zu selektieren. Allerdings gestaltet sich die Unterscheidung zwischen posi- tiven und negativen Beispielen in der Praxis als zu kompliziert, da die notwen- digen Informationen in den Logs selten vorhanden sind. Deshalb, und aufgrund der Tatsache, dass aktuelle Ansätze ausschließlich mit positiven Beispielen arbeiten, wird hier versucht die fehlerhaften Log-Traces zu entfernen, bzw. die fehlerfreien Log-Traces zu selektieren. Im Beispiel sähe das wie folgt aus:

Literaturverzeichnis

Bissantz, N; Hagedorn, J.: Data Mining (Datenmustererkennung) , In: Wirt- schaftsinformatik Volume 35 (1993)

Cook, J.E.; Wolf, A.L.: Automating Process Discovery through Event-Data Analyses, In: 17th International Conference on Software Engineering 1995

Cook, J.E.; Wolf, A.L.: Discovering Models of Software Processes from Event-Based Data, In: ACM Transcations on Software Engineering and Methodology, Volume 7 Issue 3, Juli 1998

Cook, J.E., Wolf, A.L.: Event-based detection of concurrency, In: Proceedings of the Sixth International Symposium on the Foundations of Software Engi- neering 1998

Cook, J.E.; Wolf, A.L.; Votta, L.: Cost-effective analyses of in-place software processes, In: IEEE Transactions on Software Engineering Volume 24 Issue 8, August 1998

da Silva, G.A.; Ferreira, D.R.: Applying Hidden Markov Models to Process Mining, In Rocha, A.; Restivo, F.; Reis, L.P.; Torrã, S. (Hrsg.): Sistemas e Tecnologias de Informação: Actas da 4ª Conferência Ibérica de Sistemas e Tecnologias de Informação, AISTI/FEUP/UPF, 2009

Georgi, H.: Stochastik - Einführung in die Wahrscheinlichkeitstheorie und Statistik, 3. Auf-lage, de Gruyter 2007

Herbst, J: Ein induktiver Ansatz zur Akqusition und Adaption von Workflow- Modellen, Tenea Verlag für Media, Berlin 2004, S. 8ff Maruster, L; Weij- ters, A; van der Aalst, W: Workflow Mining - Discovering process models from event logs, In: IEEE Transactions on Knowledge and Data Enginee- ring Volume 16, 2004

Herbst, J.; Karagiannis, D: Integrating Machine Learning and Workflow Man- agement to Support Acqusition and Adaption of Workflow Models, In: 9th International Workshop on Database and Expert Systems Applications, 1998

Hütt, M.; Dehnert, M.: Methoden der Bioinformatik - Eine Einführung, Sprin- ger Jäger, G.: Vorlesung der Formalen Methoden, Uni Bielefeld, WS 2007/2008 vom 09.01.2008

Köhler, R.; Altmann, G.; Piotrowski, R.G.: Quantitative Linguistik - Ein Inter- nationales Handbuch, de Gruyter 2005

Ly, L.T.: Process Mining - Bestehende Ansätze und weiterführende Aspekte, http://dbis.eprints.uni-ulm.de/543/, Zugang erforderlich, Abrufdatum: 14.10.2010

Marinell, G.: Mathematik für Sozial- und Wirtschaftswissenschaftler, 7. Auflage, Oldenbourg Maruster, L; Weijters, A; van der Aalst, W: Workflow Mining - Discovering process models from event logs, In: IEEE Transactions on Knowledge and Data Engineering Volume 16, 2004

Petersohn, H.: Data Mining: Verfahren, Prozesse, Anwendungsarchitektur; Oldenbourg Wissenschaftsverlag 2005

Rabiner, L.R.: A Tutorial on Hidden Markov Models and Selected Applica- tions in Speech Recognition, In: Proceesings of the IEEE, Vol. 77, No. 2, February 1989

Rozinat, A.; de Medeiros, A., Günther, C.W., Weijters, A.J.M.M., van der Aalst, W.M.P.: Towards an Evaluation Framework for Process Mining Al- gorithms, In: Business Process Management Workshops, Vol. 4928/2008

Rozinat, A.; Veloso, M.; van der Aalst, W.M.P: Using Hidden Markov Models to Evaluate the Quality of Discovered Process Models, In: BPM Center Re- port, Eindhoven 2008

Sun, J; Wand, J; Wen, L, van der Aalst, W: Mining process models with non- free-choice constructs, In: Data Mining and Knowledge Discovery, Volume 15 (2007)

Van der Aalst, W.M.P: Business Alignment - Using Process mining as a Tool for Delta Analysis, In: Requirements Engineering, Volume 10, Springer 2005

Van der Aalst, W.M.P: Decision Support Based on Process Mining, In: Burstein, F; Holsapple C.W.: Handbook on Decision Support Systems 1 - Basic Themes, International Handbooks on Information Systems 2008

Van der Aalst, W.M.P: Process Mining, In: Liu, Ling; Özsu, M.T.: Encyclope- dia of Database Systems, Springer 2009

Yan, L.; Yu-qiang, F: An Automatic Business Process Modeling Method Based on Markov Transition Matrix in BPM, In: International Conference on Management Science and Engineering, 2006

[...]


1 H. Petersohn: Data Mining: Verfahren, Prozesse, Anwendungsarchitektur; Oldenbourg Wissenschaftsverlag 2005, S. 8

2 N. Bissantz; J. Hagedorn: Data Mining (Datenmustererkennung) , In: Wirtschaftsinformatik Volume 35 (1993), S. 481

3 Van der Aalst, W: Process Mining, In: Liu, Ling; Özsu, M.T.: Encyclopedia of Database Systems, Springer 2009, S. 2173

4 N. Bissantz; J. Hagedorn: Data Mining (Datenmustererkennung) , In: Wirtschaftsinformatik Volume 35 (1993), S. 481

5 H. Petersohn: Data Mining: Verfahren, Prozesse, Anwendungsarchitektur; Oldenbourg Wissenschaftsverlag 2005, S. 9

6 Van der Aalst, W.M.P.: Business Alignment - Using Process mining as a Tool for Delta Analysis, In: Requirements Engineering, Volume 10, Springer 2005, S. 201f

7 Van der Aalst, W.M.P.: Process Mining, In: Liu, Ling; Özsu, M.T.: Encyclopedia of Database Systems, Springer 2009, S. 2171

8 Van der Aalst, W.M.P: Business Alignment: Using Process Mining as a Tool for Delta Analysis, In. CAiSE Workshops (2), 2004, S. 144

9 Van der Aalst, W.M.P.: Process Mining, In: Liu, Ling; Özsu, M.T.: Encyclopedia of Database Systems, Springer 2009, S. 2172

10 Ly, L.T.: Process Mining - Bestehende Ansätze und weiterführende Aspekte, S. 7, http://dbis.eprints.uni-ulm.de/543/, Zugang erforderlich, Abrufdatum: 14.10.2010

11 Van der Aalst, W.M.P.: Process Mining, In: Liu, Ling; Özsu, M.T.: Encyclopedia of Database Systems, Springer 2009, S. 2172

12 Van der Aalst, W.M.P.: Decision Support Based on Process Mining, In: Burstein, F; Holsapple C.W.: Handbook on Decision Support Systems 1 - Basic Themes, International Handbooks on Information Systems 2008, S. 640

13 Eigene Erstellung in Anlehnung an: Van der Aalst, W.M.P.: Decision Support Based on Process Mining, In: Burstein, F; Holsapple C.W.: Handbook on Decision Support Systems 1 - Basic Themes, International Handbooks on Information Systems 2008, S. 641

14 Maruster, L; Weijters, A; van der Aalst, W: Workflow Mining - Discovering process models from event logs, In: IEEE Transactions on Knowledge and Data Engineering Volume 16, 2004, S. 1134

15 Herbst, J: Ein induktiver Ansatz zur Akqusition und Adaption von Workflow-Modellen, Tenea Verlag für Media, Berlin 2004, S. 8ff

Details

Seiten
37
Jahr
2011
ISBN (eBook)
9783640848829
ISBN (Buch)
9783640849215
Dateigröße
673 KB
Sprache
Deutsch
Katalognummer
v168019
Institution / Hochschule
Universität des Saarlandes – Institut für Wirtschaftsinformatik
Note
1,7
Schlagworte
Process Mining Workflow Mining Mining BPM Geschäftsprozessmanagement Business Process Management Markov Markov Modell Markov Kette Entropy Data Mining GPM PM

Autor

Teilen

Zurück

Titel: Markov-basiertes Process Mining