Mittlerweile gibt es eine Menge Discovery-Algorithmen, mit deren Hilfe man aus einem Event-Log ein Petrinetz gewinnen kann. Der Grund dafür, dass es mehrere dieser Algorithmen gibt ist, dass die Ergebnisse dieser Verfahren sich in ihrer Qualität unterscheiden. Zu bestimmen, wie gut das Ergebnis eines Discovery-Algorithmuses ist, ist die Aufgabe des sogenannten Conformance Checking, mit dem ich mich in meiner Forschung beschäftige. Denn auch wenn es leicht ist natürlichsprachlich anzugeben, was man sich von dem gewonnenen Petrinetz erhofft, so sind diese Anforderungen manchmal gar nicht so leicht zu formalisieren und zu überprüfen.

Betrachten wir als Beispiel das folgende Paar von Event-Log und Prozessmodell:

Wir können uns nun fragen, wie gut das Prozessmodell denn zu dem Event-Log passt. Kennen wir uns ein klein wenig mit der Semantik von Petrinetzen aus, so erkennen wir schnell, dass die Wörter <a,b,c,e>, <a,c,b,e> und <a,d,b,e> Teil der Sprache des Petrinetzes sind. So weit so gut, aber wir stellen auch fest, dass das Wort <a,b,c,d> kein Teil der Sprache des Petrinetzes ist, weil wir uns immer entscheiden müssen, ob wir c oder d schalten möchten (aber nie beides schalten können). Eine der vier Sequenzen in unserem Event-Log können wir also mit dem Petrinetz nicht nachahmen. Heiß das, dass unser Petrinetz oben schlecht ist?

Das hängt maßgeblich davon ab, wie oft wir die Sequenzen jeweils in der Realität beobachtet haben. Kam <a,b,c,d> nur ein einziges Mal vor während alle anderen Sequenzen 10.000 Mal vorkamen, so können wir wohl davon ausgehen, dass es sich bei der Sequenz <a,b,c,d> um ein einmaliges Ereignis handelte, das wir nicht unbedingt in unserem Modell abbilden möchten. Kommt <a,b,c,d> aber 10.000 Mal vor und wurden die anderen drei Sequenzen nur ein einziges Mal beobachtet, dann wären wir mit unserem Prozessmodell nicht besonders zufrieden, weil es nur Randfälle abbildet und das Hauptverhalten des Prozesses überhaupt nicht berücksichtigt.

Was wir bis hierhin betrachtet haben, ist die sogenannte Fitness (manchmal auch Recall genannt) eines Prozessmodells zu einem Event-Log. Mit ihr wird gemessen, wie viele Sequenzen des Event-Logs in der Sprache des Prozessmodells liegen. Wann ein Modell N gute Fitness zu einem Event-Log L hat, können wir an dem folgenden Venn-Diagramm sehen, wobei L(N) die Sprache des Modells N bezeichnet.

Nun ist Fitness allein aber nicht alles, was man sich wünschen kann. Um das einzusehen, betrachten wir das folgende Prozessmodell:

Die Sprache dieses Petrinetzes enthält jede beliebige Folge von den Symbolen a,b,c,d, und e -- und damit logischerweise auch jede Folge, die in unserem Event-Log L enthalten ist. Dieses Prozessmodell hat also perfekte Fitness (denn es kann alles, was der Event-Log vorgibt), passt aber trotzdem furchtbar schlecht zu unserem Event-Log, weil es zu viel kann, was gar nicht im Event-Log steht (wir sagen in dem Fall, es ist underfitting). Wir möchten also nicht nur, dass alles, was im Event-Log steht, auch in der Sprache des Modells enthalten ist, sondern auch, dass alles, was in der Sprache des Modells enthalten ist, auch im Event-Log hinterlegt ist. Diese Eigenschaft nennen wir Precision und veranschaulichen sie ebenso wie die Fitness mit Hilfe eines Venn-Diagramms:

Je mehr Wörter der Sprache von N existieren, die nicht in L auftauchen, desto schlechter ist also die Precision. Netze mit Sprachen, die komplett in L enthalten sind, haben dagegen perfekte Precision. Prüfen wir also nun, wie es um die Precision unseres Beispiels von oben bestellt ist:

Wir haben schon gesehen, dass die Sequenz <a,b,c,d> aus L nicht in der Sprache des Petrinetzes vorkommt. Aber das stört für die Precision überhaupt nicht, da wir uns nur für die Wörter aus der Sprache des Modells interessieren, die nicht in L enthalten sind. Wir sehen also schon einmal, dass Fitness und Precision unterschiedliche Dinge berücksichtigen. Stellen wir die Sprache unseres Petrinetzes auf, so erhalten wir L(N) = {abce, acbe, abde, adbe}. Wir stellen fest, dass die Sequenz <a,b,d,e> gar nicht in L vorkommt, also hat unser Modell nicht perfekte Precision.

Die Precision allein zu betrachten ist ebenso gefährlich wie die Fitness allein zu betrachten, denn sie kann leicht ausgetrickst werden: Nehmen wir ein Prozessmodell, in dem überhaupt kein Event schalten kann, können wir auch nichts falsch machen und haben damit perfekte Precision. Fitness und Precision gehen also bei der Bewertung von Prozessmodellen Hand in Hand.

Nun mag sich in realen Prozessmodellen aber die Frage stellen, ob wir wirklich so streng sein wollen, wie Fitness und Precision es uns vorgeben. Denn auch wenn wir die Sequenz <a,b,d,e> nicht in unserem Event-Log L gesehen haben, so könnte sie ja trotzdem zu dem möglichen Verhalten des Prozesses zählen, das einfach nur noch nicht beobachtet wurde. Vielleicht wollen wir diese Sequenz also doch lieber nicht aus unserem Prozessmodell verbannen, weil sie doch nah genug an den anderen Sequenzen im Event-Log dran ist. Ob uns das mit einem Modell gelingt oder nicht wird mit Hilfe eines Maßes für die Generalization gemessen. Die Generalization verhindert also, dass wir unser Prozessmodell zu exakt werden lassen (ein solches, zu exaktes Modell nennen wir overfitting) und steht damit der Precision entgegen.

Nun kann man sich fragen, ob es denn auch ein Maß gibt, das der Fitness entgegen steht, und ein solches gibt es: Die Simplicity. Denn auch wenn wir möglichst viel von unserem Event-Log in der Sprache des Prozessmodells haben möchten, so wollen wir doch gleichzeitig sicherstellen, dass unser Prozessmodell möglichst einfach aussieht. Das geht manchmal nur, indem man ein paar der Sequenzen aus dem Event-Log aus der Sprache des Modells herauslässt: Das Prozessmodell wird dadurch wesentlich leichter zu verstehen, aber die Fitness leidet darunter.

Diese vier Qualitätskriterien sind im Bereich Process Mining schon lange etabliert, allerdings sind nur Fitness und Precision wirklich zufriedenstellend mathematisch definiert. Doch selbst bei Fitness und Precision gibt es noch Verbesserungspotenzial, da sie sich auf manchen Eingaben anders verhalten, als man es erwarten würde. Mein Interesse gilt derzeit aber besonders der Simplicity, die zwar nachweislich sehr wichtig in der Praxis, aber dafür erstaunlich wenig erforscht ist. Daneben erforsche ich im Moment auch, ob sich der Spieß nicht umdrehen lässt und mit Hilfe von Process-Discovery ein Modell entwickeln lässt, das nach Konstruktion besonders gut in den oben genannten Qualitätskriterien abschneidet.