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.