Heuristics Miner

Hi, and welcome back. In this lecture, I’ll explain you how the Heuristics miner works, which is actually an improvement upon the Alpha miner. So we’re still bridging the gap with a different algorithm between the event log and the discovery of a process model from this data. So as I said, the Heuristics miner is actually an improvement of the Alpha miner, and it improves in three ways. It takes frequencies into account, and therefore it can filter out a noisy behavior or infrequent behavior, and it’s able to detect short loops, and it allows skipping of single activities. However, it still does not guarantee sound process models. So how does it work? It also builds the directly-follows matrix but now using the frequencies.

So same relation holds, and let’s see what we could build from this example event log but now with frequencies. So the first trace occurs six times, et cetera, et cetera. We can build the following directly-follows matrix using frequencies. So for instance, a is directly followed by b 56 times, as you can see in the event log on the left. And so you fill in the rest of the cells. And for clarity, I left the cells with zero empty. Next to this, we build also a dependency matrix, and we use the formula above, which I’ll explain in a bit more detail later. When you take the directly-follows matrix on the right, you get the dependency matrix as shown here.

And using the formula above, you can calculate each cell. And I’ll show you an example of one, and I hope you can repeat it for the others. So the dependency between a and b, on the left matrix, is calculated by taking the directly-follows relation a and b in the right matrix, which is 56, and subtract the inverse relation. So b directly followed by a, which has occurred zero times. So we do 56 minus 0. We divide it by the times that a was directly followed by b plus the times that b was directly followed by a plus 1. So we get 56 plus 0 plus 1. So we divide 56 by 57, and we get to the value of 0.98.

I hope you can see that we can do this for all cells in the dependency matrix. Now we get values between minus 1 and plus 1. A negative value means actually that there’s a negative relation. A high value in the plus side means that there’s a strong relation. So for instance, the cell that we just calculated, 0.98, that’s really close to 1. That means that we observed it rather frequent, but also that the inverse relation, so b being followed by a, does not or very infrequently hold. And using these two matrices, we can filter certain relations, since we have both the frequency and the significance. And then using particular patterns, we can build a Petri net.

And if we apply the Heuristics miner on these two matrices that are built in the meantime, we get the Petri net shown above. I hope you see that this Petri net has some issues. So let’s get the source event log and our process model checklist, and let’s check, for instance, is this process model sound? So please pause this video for a minute, think about it, is the model shown above, is it sound?

I hope you saw that this model is not sound, and I’ll explain why. So if we fire a and then b and d, as well as the middle of the three, silent transitions, we get in the following state. There are three tokens, and both f and c are now enabled. So let’s fire f and g and follow the path further, and now we have a final token in the final place, hence indicating the final state of the Petri net, but there’s still a token enabling c. So this breaks the soundness rule of proper completion, and therefore, this whole process model is not sound. So the Heuristics miner does not guarantee sound process models. Point 2, replay fitness.

If we take the original data, can we replay this on the Petri net? Well, the Petri net limits, for instance, activity c to only be executed after b. And at the same time, after c, you can only fire e and not f.

However, in these three traces, we see this behavior. B is executed after c, and f is executed after c. And we cannot replay all behavior that we saw, so the replay fitness can be considered as bad or at least not perfect. But many of the traces cannot be replayed. When we evaluate precision, you could say that precision is OK. It does not allow for too much behavior that we didn’t see. Actually, it allows less behavior than we saw. However, it’s also not really generalizing since it’s restricting the behavior too much, and it is not really capturing the intent of the data that we saw in a nice way.

So the data shows parallelism, in particular, orderings, and this process model does not. Furthermore, you could classify this model as medium on the simplicity scale, since, mainly because of the unsoundness, it has some strange structures. But at the same time, it’s not very big and does not really have crossing arcs, so it’s not very complex. So I hope that you see that although the Heuristics miner, even on real data, can be an improvement over the Alpha miner, in practice, it has still some issues. In the next lectures, I will show you the Heuristics miner on real data, in the process mining tool ProM to show you that it can discover reasonable process models.

But I will also show you even better process mining algorithms that also on real data can discover good quality process models. I hope to see you again in the next lecture.