Process Mining Flashcards

Question

Petrinetz Analyse von Systemen Verifikation

Answer 1

Verifikation: Beweis von Eigenschaften: * Statische Eigenschaften: Unabhängig von Markierungen, nur von Netztopologie abhängig. * z.B. Verklemmungen / Deadlocks * Dynamische Eigenschaften: Abhängig von der Menge erreichbarer Markierungen. * Standardhilfsmittel: Erreichbarkeitsgraphen

Answer 2

* K: S → ℕ ∩ {∞} erklärt eine (möglicherweise unbeschränkte) Kapazität für jede Stelle. * Markierungen M: S → ℕ\0 müssen Kapazitäten respektieren, d.h. für jede Stelle s ∈ S gilt: M(s) ≤ K(s). * Transitionen sind bei Verwendung von Kapazitäten nur dann aktiviert, wenn Folgemarkierung Kapazitäten respektiert.

Answer 3

* Sei P=(S,T,F,K,M0) Petrinetz. * Abbildung B: S → ℕ\0 ∪ {∞} ordnet jeder Stelle eine „kritische Markenzahl“ zu. * Petrinetz P heißt: * B-sicher (oder B-beschränkt), wenn für alle erreichbaren Markierungen Anzahl der Markierungen pro Stelle durch B begrenzt, d.h.: für alle M ∈ [M₀\> und s ∈S gilt: M(s) ≤ B(s). * 1-sicher, 2-sicher usw., wenn B=1, B=2 usw. * beschränkt, wenn es natürliche Zahl b gibt, für die P b-sicher. * Stelle s heisst b-sicher, wenn P B-sicher mit B(s)=b, und B(s‘)= ∞ für s'#s. * Unterschied zwischen Kapazität und Sicherheit: * Kapazität begrenzt Stellenmarkierung (a priori-Begrenzung). * Sicherheit beobachtet Stellenmarkierung (a posteriori-Begrenzung).

Answer 4

Transition t eines Petrinetz P=(N,M₀) heißt: * aktivierbar: In mindestens einer erreichbaren Markierung aktiviert: existiert M1 ∈ [M₀\> mit: M₁[t\> * lebendig: In allen erreichbaren Markierung aktivierbar: für alle M1 ∈ [M₀\> gilt: existiert M₂∈ [M₁\> mit: M₂[t\> * tot: In keiner erreichbaren Markierung aktiviert: für alle M ∈ [M₀\> gilt: ¬M[t\> * Tot ist nicht logische Negation von lebendig sondern von aktivierbar !

Answer 5

Petrinetz P=(S,T,F,K,W,M₀) heißt: * lebendig: In jeder erreichbaren Markierung ist jede Transition aktivierbar: für alle M₁ ∈ [M₀\> und t ∈ T gilt: existiert M₂ ∈ [M₁\> mit: M₂[t\> * deadlockfrei: In jeder erreichbaren Markierung ist mindestens eine Transition aktiviert: für alle M₁ ∈ [M₀\> gilt: existiert t ∈ T mit: M₁[t\> * tot: Keine Transition aktiviert: ∀t ∈ T: ¬M₀ [t\>

Answer 6

* genau eine Stelle ohne eingehenden Bogen (Start-Stelle) * genau eine Stelle ohne ausgehenden Bogen (End-Stelle) * jede Stelle und Transition auf Pfard von Start- zu End-Stelle * Initiale Markierung * Start-Stelle genau eine Marke * Rest: Keine Marke

Answer 7

* Positiv * Einfache und wenige Notationselemente. * Graphisch gut darstellbar. * Marken: übersichtliche Visualisierung des Systemzustands. * Syntax und Semantik formal definiert. * Werkzeuge zur Erstellung, Analyse, Simulation, Code-Generierung vorhanden (z.B. Process Mining). * Gut geeignet für kooperierende Prozesse. * Nachteil * Zunächst keine Datenmodellierung (kann aber dahin erweitern).

Answer 8

* Process Mining: Data Mining auf Prozess-Daten * Process-Mining: Ende zu Ende Prozesse * Data-Mining: Datenbasiert und nicht prozessbasiert * Qualitätsbewertung * Viele Ähnlichkeiten, aber auch Unterschiede * Process-Mining-Techniken können Vorteile aus Erfahrungen im Bereuch Data Mining ziehen.

Answer 9

* Datensatz besteht aus Instanzen (Individuen, Entitäten, Fälle, Objekte oder Aufzeichnungen). * Variablen: als Attribute, Features oder Datenelemente bezeichnet. Zwei Typen: * Kategorielle Variablen: * Ordinal (hoch – mittel – niedrig) * Nominal (true – false, rot – pink – grün) * Numerische Variablen (geordnet, können nicht einfach aufgezählt werden).

Answer 10

* Klassifizierte Daten (Labeled Data) * Jede Instanz durch Response-Variable gekennzeichnet. * Ziel: * Erkläre Response-Variable (abhängige Variable) in Form von Predictor-Variablen (unabhängige Variable). * Klassifikationstechniken (z.B.: Lernen mit Entscheidungsbäumen) * Setzen kategorielle Response-Variablen voraus. * Ziel: Instanzen anhand Predictor-Variablen klassifizieren. * Regressionstechniken: Benötigen numerische Response-Variablen. * Ziel: Zu Daten passende Funktion mit wenigsten Fehlern finden.

Answer 11

* Nicht überwachtes Lernen verwendet unlabeled data. Variablen nicht in Response- und Predictor-Variablen unterteilt. * Beispiele: * Clustering (z.B.: k-means clustering und agglomerative hierarchical clustering). * Pattern discovery (association rules).

Answer 12

* Teile Menge der Instanzen auf, sodass Variation in jeder Teilmenge kleiner wird * Variation messen (z.B. durch Entropie) * Minimiere durchschnittliche Entropie; maximiere Informationsgewinn pro Schritt

Answer 13

* Entropie **E** * informationstheoretisches Maß für Chaos in einer Multimenge * Element **v**_i in einer Multimenge **c_i**-mal enthalten * Multimenge hat **n** Elemente * Einzelentropie: -log₂(p_i), wobei p_i=c_i/n * Gesamtentropie: E=−∑(p_i log₂(p_i)) (i=1, k)

Answer 14

* Anwendung: * Bei großer Datenmenge viele verschiedene Attribute von Bedeutung. * Entscheidungsbaum ohne große Berechnungen generieren. * Algorithmus: * Iterativ * Benutzt Entropie zur Bestimmung von Baum-Knoten. * Abbruch, falls jedem Blattknoten eine Klassifikation zugeordnet. * Eingabe: * Menge zu klassifizierender Objekte, Wurzelknoten, Menge noch zu vergebener Merkmale * Ausgabe: * Struktur mit Tupeln (Entscheidungsbaum)

Answer 15

* Gegeben: X={x₁ ,...,x_n}⊂{1,...,v₁}×...×{1,...,v_p}, y={y₁,...,y_n}⊂{1,...,c} * Aufrufen: ID3({1,...,n}, Wurzel,{1,...,p}) * Prozedur ID3(I,N,K) 1. Wenn alle y(I) gleich dann abbrechen 2. Berechne Informationsgewinn g_j((X(I),y(I))) = E(X)−∑_j∈y((∣X_j∣)/(∣X∣) ) \* E(X _j)∀ j∈K * X: Datensatz, E(X): Entropie im Datensatz, c: Klassifikation X _j : Untermenge von X, ∣X∣: Mächtigkeit von X, ∣X_j∣: Mächtigkeit von X _j 3. Bestimme Gewinnermerkmal i = argmx{g_j((X(I), y(I)))} 4. Zerlege I in v_i disjunkte Teilmengen 5. für j mit I_j ≠ {} * Generiere neuen Knoten N_j und hänge ihn an N * Aufrufen ID3(I_j, N, I\{i})

Answer 16

## Footnote Maß über den Wert einer Zufallsvariable, welche verbleibt, nachdem das Ergebnis einer anderen Zufallsvariable bekannt wird.

Answer 17

* tp: Anzahl true positives; korrekterweise als positiv klassifiziert. * fn: Anzahl false negatives; als negativ klassifiziert, aber positiv. * fp: Anzahl false positives; als positiv klassifiziert, aber negativ. * tn: Anzahl true negatives; korrekterweise als negativ klassifiziert.

Answer 18

Error = (fp+fn)/N

Answer 19

accuracy = (tp+tn)/N

Answer 20

tp-Rate = tp/p p=tp+fn

Answer 21

fp-Rate = fp/n n = fp+tn

Answer 22

precision = tp/p' p' = tp+fp

Answer 23

* Anzahl K zu ermittelnder Cluster vorher festlegen. * Start (i=0): Positionen der Clusterschwerpunkte zufällig initialisieren. * Objekte nächstgelegenen Schwerpunkten zuordnen. (i=1) * Bei jeder Iteration i Schwerpunkt und nächstliegende Kandidaten neu berechnen. * Dies Wiederholen bis Summe quadratischer Distanz einzelner Objekte zu ihrem jeweiligen Clusterschwerpunkt über alle Cluster ein Minimum erreicht. * Bild * x_nDatensätze und μ_k Schwerpunkte der Cluster. * Entscheidungskriterium für Cluster-Zugehörigkeit der Testobjekte: Abstände der Testvektoren von Clusterschwerpunkten.

Answer 24

* Regeln der Form “IF X THEN Y” lernen: * X⇒Y

Answer 25

support(X⇒Y) = N_X∧Y/N ## Footnote (N_X: Anzahl Datensätze, die alle Eigenschaften in X erfüllen).

Answer 26

confidence(X⇒Y) = N_X∧Y/N_X ## Footnote (N_X: Anzahl Datensätze, die alle Eigenschaften in X erfüllen).

Answer 27

lift(X⇒Y) = (N_{X∧Y *}N) / (N_X \* N_Y) ## Footnote (N_X: Anzahl Datensätze, die alle Eigenschaften in X erfüllen).

Answer 28

* Definition: Für gegebenen support-Schwellwert **minsup**: * Menge Z heißt frequent item-set, wenn N_Z / N \>= minsup. * Assoziationsregeln wie folgt generierbar: 1. Generiere frequent item-sets: alle Mengen Z sodass N_Z / N größer als gegebener Schwellwert für support und |Z| \>=2. 2. Für jedes frequent item-set Z betrachte Partition in nicht-leere Teilmengen X, Y. * Behalte Regeln X =\> Y, für die confidence gegebenen Schwellwert überschreitet oder gleich ist.

Answer 29

* Beobachtung: Jede nicht-leere Teilmenge einer frequent item-set ist ebenfalls frequent: Durch Teilmengen-Bildung kann sich Menge der zu erfüllenden Eigenschaften allenfalls verringern (nicht vergrößern), daher kann sich der support allenfalls vergrößern (nicht verringern), da es einfacher wird, alle Eigenschaften zu erfüllen. * Maximale frequent item-sets ausgehend von 1-elementigen frequent item-sets generierbar.

Answer 30

1. Wahrscheinlichkeit der Sequenz berechnen (gegeben Beobachtungssequenz und Hidden-Markov-Modell) 2. Gegeben Beobachtungssequenz und Hidden-Markov-Modell, wahrscheinlichsten „hidden path“ im Modell berechnen (= interne Zustandsfolge; kann zur z.T. beobachtet werden). 3. Bei gegebener Beobachtungs- sequenz Hidden-Markov-Modell ableiten, welches mit max. Wahrscheinlichkeit Sequenzen erzeugt.

Answer 31

Mit hilfe gegebener Datan testen wie gut der Algo ist.

Answer 32

* Was geschah in der Vergangenheit ? * Warum ist es passiert ? * Was wird vermutlich in der Zukunft geschehen ? * Wann und warum weichen Unternehmen und Leute voneinander ab ? * Wie kann ein Prozess besser kontrolliert werden ? * Wie kann ein Prozess neu entworfen werden, sodass die Performanz gesteigert wird ?

Answer 33

* Prozess enthält Fälle (cases). * Fall besteht aus Events, jeden Event genau einem Fall zuordnen. * Events innerhalb eines Falles: geordnet. * Events können Attribute haben. * Beispiele typischer Attributnamen: activity, time, costs und resource.

Answer 34

* Korrelation: Events in Event-Log: nach Fällen gruppiert. * Nicht trivial: setzt Korrelation der Events untereinander voraus. * Zeitstempel: Events pro Fall ordnen. * Probleme: nur Datum, unterschiedliche Uhren, verzögertes Loggen. * Snapshots: Fälle ggf. über Dauer der Aufnahme hinweg aktiv. * Z.B.: Fall vor Beginn des Event-Logs gestartet. * Scoping: Welche Tabellen berücksichtigen ? * Granularität: Events in Event-Log: andere Granularität als für Endnutzer relevante Aktivitäten.

Answer 35

* Verschieden Datenquellen zusammenfassen * Haupttabelle festlegen und Attribut zur Zusammenführung bestimmen

Answer 36

* **Minimal**: Nummer der GP-Instanz („case“ / Fall), GP-Aktivität, zeitliche Ordnung * **Optional**: Genaue Zeit, Nutzer, assoziierte Daten etc. * „**Rauschfrei**“: GP-Instanznr. erlaubt irrelevante Daten wegzufiltern. * **Vollständig**: Relevante Daten für verschiedene GP-Instanzen vorhanden.

Answer 37

* **Angemessenheit** (Fitness) * Verhalten des Event-Logs zulassen. * **Genauigkeit** (Precision) * vermeide Unteranpassung (underfitting) * kein Verhalten ohne Bezug zu Inhalt des Event-Logs zulassen. * **Verallgemeinerung** (Generalization) * vermeide Überanpassung (overfitting) * Verallgemeinerung des Beispiel-Verhaltens im Event-Log sein. * **Einfachheit** (Simplicity) * so einfach wie möglich sein.

Answer 38

* α-Algorithmus: aus Menge von Folgen von Log-Daten GP-Modell als Petrinetz extrahieren. * Idee: * Informationen über Abfolge der Aktivitäten durch Verwendung geeigneter Ordnungs-Relationen sammeln. * Ob Aktivitäten in verschiedenen Folgen in Kausal-Beziehung stehen, oder parallel bzw. unabhängig voneinander sind. * Damit Petrinetz konstruieren.

Answer 39

* Annahmen an zu erzeugende Petrinetze: * Ausführung: jede Transition erzeugt jeweils ein Ereignis in Log- Datei mit zugehöriger Bezeichnung. * Verschiedene Transitionen haben verschiedene Bezeichnungen. * Keine Bogen-Vielfachheiten. * Annahmen an Folge von Log-Daten: * Log-Daten alle vom relevanten GP erzeugt. GP durch Petrinetz modellierbar. * Aufteilung der Log-Daten auf Folgen in gegebener Menge entsprechen verschiedenen GP-Instanzen. * Abstrahieren von mehrfachen GP-Instanzen mit demselben Verlauf (und von GP-Instanznummern).

Answer 40

* Direkte Nachfolge: x \>_W y * ∃ σ∈W worin y direkt auf x folgt * Kausalität x →_W y * x \>_W y und nicht y \>_W x * Parralelität x ||_W y * x\>_Wy und y\>_Wx * Unabhängigkeit x #_W y * nicht x\>_W y und nicht y\>_W x

Answer 41

* Gesucht: Workflow-Schema als Petrinetz α(W) = (Stellen P_W, Transitionen T_W, Verbindungen F_W) * Transitionen * 1. T_W ={ t ∈ T | ∃_σ∈W t ∈ σ } * 2. T_I={t∈T | ∃_σ∈W t=first(σ)} Start-Transitionen * 3. T_O={t∈T | ∃_σ∈Wt=last(σ)} End-Transitionen * Kandidaten für Stellen * 4. X_W = { (A,B) | A ⊆ T_W ∧ A ≠ ∅ ∧ B ⊆ T_W ∧ B ≠ ∅ ∧ ∀_{a ∈ A} ∀_{b ∈ B} a →_W b ∧ ∀_{a1,a2 ∈ A} a₁#_w a₂ ∧ ∀_{b1,b2 ∈ B}b₁#_W b₂ } * Stellen * 5. Y_W = {(A,B) ∈ X_W | ∀_{(A´,B´) ∈ Xw} A⊆A´ ∧ B⊆B´ ⇒ (A,B) = (A´,B´)} * 6. P_W={(p(A,B)) | (A,B)∈Y_W}∪{i_W,o_W} * Verbindungen und Resultat * 7. F_W={(a,p_(A,B) ) | (A,B)∈Y_W∧a∈A} ∪ {p_(A,B) ,b | ( A,B) ∈ Y_W∧ b∈B} ∪ {(i_W ,t)|t∈T_I} ∪ {(t,o_W )| t∈T_O} * 8. α(W )=(P_W, T_W, F_W)

Answer 42

* Rauschen * Event-Log enthält seltenes und unregelmäßiges Verhalten. * Nicht typisches Verhalten des Prozesses. * Lösung z.B. durch Betrachtung der Häufigkeit * Unvollständigkeit * Event-Log enthält zu wenig Events, um alle Kontrollflüsse zu erfassen.

Answer 43

## Footnote Paradebeispiel für unterangepasstes Modell: jedes Verhalten auf Basis der Ereignisse a, ..., h zulässig.

Answer 44

* Keine negativen Beispiele: * Logs zeigen, was geschah. Nicht: was nicht passieren kann. * Durch Nebenläufigkeit, Schleifen, Verzweigungen: * Suchraum hat komplexe Struktur. * Log enthält nur Teil des möglichen Verhaltens. * Kein Zusammenhang zwi. Größe des Modells und seinem Verhalten: * Kleines Modell kann mehr/weniger Verhalten generieren. * Klassische Analyse- und Evaluations-Methoden erwarten Monotonie-Eigenschaften.

Answer 45

* Auditierung: Evaluation von Unternehmen und ihren Prozessen. * Audits stellen Validität und Zuverlässigkeit von Informationen über Unternehmen und entsprechende Prozesse sicher. * Test von Ausführung der GP in bestimmten Grenzen (von Managern, der Politik und anderen Interessenvertretern gesetzt). * Process-Mining: bei Aufdecken von Betrug, Fehlverhalten, Risiken und Ineffizienzen hilfreich. * Alle Events eines GP evaluierbar, auch während Prozess noch läuft.

Answer 46

* In jedem Schritt gibt es Zähler: * p (produzierte Tokens) * c (konsumierte Tokens) * m (fehlende Tokens), * r (überbleibende Tokens). * Am Anfang: alle leer. * Umgebung produziert ein Token für Stelle Start →p=1. * Transition a konsumiert ein Token und produziert 2 Tokens → p = 3, c = 1. * Am Ende konsumiert die Umgebung ein Token → c inkrementieren. * Durchführen bei jeder Transition

Answer 47

* produced, consumed, missing, remaining * (1-m/c) berechnet Anteil fehlender Tokens. * (1- r/P) berechnet Anteil überbleibender Tokens. * σ: Log, N: Modell. * 0 ≤ fitness(σ, N) ≤ 1. * Falls fitness (σ, N) = 1: Keine fehlende oder überbleibende Token. * fittness(σ, N) = 1/2 \* (1 - m/c) + 1/2 \* (1 - r/p)

Answer 48

* Fehlerfreie Workflow-Ausführung ? Workflow-Ausführung mit geringem oder normalem * Ressourcenverbrauch ? * Identifikation kritischer Aktivitäten (hoher Ressourcenverbrauch). * Wie sehen häufige / typische Ausführungen aus?

Answer 49

* (Timed) Replay: Timing-Information mit Modellelementen verknüpfen. Ziele: * Visualisierung * Analyse * der Zeit-Informationen

Answer 50

* Entscheidungspunkte in extrahierten Petrinetzen zunächst „nicht-deterministisch“: * im Modell nicht determiniert, welcher Ausführungszweig in welcher Ausführung gewählt wird * Nützliche Information ! * Idee: Klassifikationstechniken (s. Abschnitt 2.2) anwenden, um Rationale hinter der in den Ausführungen gewählten Entscheidungen auf Basis der Logdaten zu erkennen. * =\> „Decision Mining“

Answer 51

Wenn eine Stelle die Wahl zwischen 2 Transitionen hat.

Answer 52

* Flaschenhälse entdecken. * Abweichungen / Probleme entdecken. * Performanz-Messungen. * Verbesserungen vorschlagen. * Entscheidungshilfe (z.B.: Empfehlung und Vorhersage). * Rückkopplung geben.

Answer 53

* “Post-mortem”-Eventdaten * Abgeschlossene Fälle. * Zur Verbesserung und Auditierung. Nicht, um gegebenen Fall zu beeinflussen. * “Pre-mortem”-Eventdaten: * Nicht abgeschlossene Fälle. * Wenn Fall läuft / „lebt“ (pre-mortem): * Informationen aus Event-Log über Fall (akt. Daten) verwertbar. *  Korrekte und effiziente Durchführung des Falls sicherstellen.

Answer 54

Stark strukturierte Prozesse Verhalten ist "vorhersehbar"

Answer 55

unstrukturierte Prozesse mit vielen möglichen Pfaden

Answer 56

1. Weise jedem Datenpunkt einen Cluster zu 2. Füge die beiden nächsten Cluster zusammen (merge) 3. Wiederhole 2 bis nur noch ein Cluster existiert.

Answer 57

* Discovery/Extraktion: * Es existiert kein Modell, das die Vorgänge in der Bank modelliert. Zuständigkeiten einzelner Mitarbeiter und erlaubte / mögliche Aktionen des Kunden können über Process Mining ermittelt werden. * Conformance/Konformanz: * Es existiert ein Modell, das die Bank modelliert. Das Modell wird mit den Logs verglichen, die bei der Ausführung der Systeme entstehen. So können zum Beispiel Indizien gesammelt werden, um festzustellen, ob Mitarbeiter ihre Kompetenzen überschreiten oder das Vier-Augen-Prinzip verletzt wird. Darüber hinaus können auch Lücken im Prozess festgestellt werden: wenn der Bankautomat nach einem Softwareupdate auch Kreditanträge bearbeiten kann und dies nicht im Prozessmodell nachgepflegt wurde, kann dies aufgedeckt werden. * Enhancement/Verbesserung: * Ein bereits vorhandener Prozess soll um Informationen angereichert werden. Hier können bspw. lange Laufzeiten einer Kontoeröffnung auf- gedeckt werden und zu einer Optimierung oder Erweiterung eines Prozesses führen.

Answer 58

* Extraktion: Play-in * Konformanz: Play-out * Verbesserung: Replay

Answer 59

Vielfach werden IT-Systeme und interne Prozesse überhaupt an zuvor modellierten Prozessen ausgerichtet. Hier kann also gar kein Mining-Ansatz benutzt werden, bevor nicht mit GP-Modellierung gearbeitet worden ist. ## Footnote

Answer 60

* Informationen, die Process Mining liefert, basieren grundsätzlich auf der Auswertung einer begrenzten Zeitspanne. Aktivitäten, die in dieser Zeit nicht im Log auftauchen, aber eigentlich benötigt werden, können so aber nicht beachtet werden. * Die Abstraktionsebene wird durch das Log bestimmt und nicht dadurch welche Abstraktion sinnvoll ist.

Answer 61

Beim überwachten Lernen ist das Ziel eine abhängige Variable (die Response-Variable) durch unabhänige Variablen (die Predictor-Variablen) zu erklären. Beim nicht überwachten Lernen gibt es keine Unterscheidung zwischen den Variablen und das Ziel ist es diese zu Clustern oder ihre Beziehung untereinander darzustellen. ## Footnote

Answer 62

* Fall-Nummer : * Wird zur Bildung der Sequenzen benötigt. Ohne Fallnummer ist das Extrahieren eines Netzes nur dann möglich wenn es keine parallelen Ausführungen des Prozesses gibt. * Task : * Werden in Transitionen überführt. Ohne eindeutigen Bezeichner für einzelne Tasks würden mehrere Transitionen pro Task erzeugt und ein verfälschtes Netz entstehen. * zeitliche Ordnung : * Wird zur Bildung der Relationen zwischen Transitionen benötigt. * Rauschfrei : * Der α Algorithmus ist nicht in der Lage fehlerhafte oder unvollständige Sequenzen zu filtern. * Vollständig : * Das Log File ist vollständig.