Enhancing Approximate Conformance Checking Accuracy with Hierarchical Clustering Model Behaviour Sampling
Existing model sampling-based methods for approximate conformance checking lack sufficient accuracy. This study proposes new hierarchical clustering approaches to improve approximation, achieving results closer to exact values.
In recent years, alignment-based method has become the de facto standard for conformance checking in computing con- formance diagnostics, as it always returns the most accurate deviations, known as optimal-alignment. However, as the com- plexity of the log and model increases, the runtime complexity of optimal alignment computation grows exponentially, leading to extremely long computation times—sometimes even taking several weeks. This makes them impractical for real-world ap- plications. To tackle the problems, various approximation strategies have been proposed. Notably, model behaviour sampling method provides an angle for approximate conformance checking, that is, selecting partial model traces to substitute process model.
My research looks into an enhanced model behaviour sampling method to select more representative subsets and get more accuracy approximate values. We apply hierarchical clustering to the event log with a new proposed distance criterion. Then, we propose two in-cluster methods to select typical traces from each cluster. Finally, we extend existing cost lower bound algorithm to achieve more accurate approximation results.
Our framework for proposed methods, as illustrated below.
With this novel notion, our method lays the foundation of many exciting futures being researched — for example, can we use more advanced hierarchical algorithm to obtain results? Keep an eye on us if you find this method interesting and practical — the party has started 🥳!