Heuristic Mining 알고리즘은 dependency graph를 기반으로 하여 이에 다양한 threshold들을 적용시켜 프로세스 모델을 도출하는 process discovery 알고리즘이다. Heuristic Mining은 알파 알고리즘과는 다르게 이벤트와 시퀀스의 빈도 (frequency)를 고려하기 때문에 몇 번 일어나지 않은 이벤트 등의 아웃라이어나 노이즈들을 필터링할 수 있다는 장점을 가진다. 그렇기 때문에 알파 알고리즘에 비해 실생활의 이벤트 로그를 프로세스 모델로 만들 때 더 유용하게 사용될 수 있다. 이번 포스팅에서는 Heuristic Mining이 무엇인지에 대해 설명하겠다.
Heuristic Mining Algorithm
휴리스틱 마이닝은 이벤트 로그로부터 C-net을 만들어내는 것을 목표로 하는 알고리즘이다. 그러므로 C-net을 어떻게 만드는지가 결국에 휴리스틱 마이닝 알고리즘과 같다고 할 수 있다. 그렇기 때문에 이에 대한 설명은, 아래 C-net에 대한 포스팅으로 대신하도록 하겠다.
2019/07/28 - [Theory/Process Model] - C-net (Causal net)이란?
C-net (Causal net)이란?
C-net(Causal net)이란, 액티비티 사이의 causal dependency를 표현한 그래프이다. C-net은 BPMN, EPCs, YAWL 등의 다양한 mainstream language에 아주 잘 맞게 이벤트 로그를 표현할 수 있고, 대부분의 프로세스..
process-mining.tistory.com
Heuristic Net
ProM, RapidMiner, pm4py 등의 다양한 프로세스 마이닝 툴들은 모두 휴리스틱 마이닝을 제공한다. 하지만 이들의 결과물은 대부분 C-net이 아닌 Heuristic Net의 형태로 나타난다. Heuristic Net은 간단히 말하면 dependency graph에 threshold를 적용시킨 형태이다.
2019/07/25 - [Theory/Process Model] - Dependency Graph란?
Dependency Graph란?
Dependency Graph란, 말 그대로 activity 사이의 dependency를 표현한 그래프이다. Dependency Graph는 또 다른 프로세스 모델인 C-net이나 process discovery의 한 방법인 heuristic mining의 기본이 되는 프로세..
process-mining.tistory.com
이 threshold의 종류는 다음과 같다. (물론, C-net에도 당연히 이 threshold들을 적용시킬 수 있다.)
Dependency Threshold
Dependency가 설정한 threshold보다 높은 것만을 표시한다. 예를 들어, dependency threshold가 0.7이면 dependency가 0.7 이상인 시퀀스만을 표시한다.
Positive Observations Threshold
두 이벤트 사이의 directly follows 수가 설정한 threshold보다 많은 것만을 표시한다. 즉, dependency threshold는 dependency를 필터링했다면, 이는 frequency를 필터링한다.
Relative-to-best Threshold
전체 엣지 중 Maximum dependency 값과 dependency 값 사이의 차이가 설정한 threshold보다 작은 경로만 표시한다. 예를 들어, threshold가 0.5이고 maximum dependency가 0.98일 때, dependency가 0.2라면 이는 표시되지 않고 (차이 = 0.78 > 0.5), dependency가 0.7이라면 이는 표시된다. (차이 = 0.28 < 0.5)
Length-one Loop Threshold
이 threshold는 length가 1인 loop(자신으로 돌아오는 loop)에 대한 필터링을 위한 threshold이다. 설정한 threshold보다 높은 위 값을 가지는 시퀀스만 표시한다.
Length-two Loop Threshold
이 threshold는 length가 2인 loop ( a > b > a 형태의 loop)에 대한 필터링을 위한 threshold이다. length-one loop threshold와 마찬가지로, 설정한 threshold보다 높은 위 값을 가지는 시퀀스만 표시한다.
Long Distance Threshold
이 threshold는 길이에 상관 없이 한 액티비티 뒤에 다른 액티비티가 일어난 경우에대한 필터링을 위한 threshold이다. 설정한 threshold보다 높은 위 값을 가지는 시퀀스만 표현한다.
And Threshold
이 threshold는 a 다음에 오는 b와 c 액티비티가 서로 XOR 관계 (a 이후에 b와 c 중 하나를 선택해서 일어남)인지 AND 관계인지 (a 이후에 b와 c가 모두 일어남)인지를 판단하기 위한 threshold이다. 설정한 threshold보다 값이 높으면 AND, 낮으면 XOR로 취급한다.
이 모든 threshold들을 원하는 대로 적용시키면, 예쁜 heuristic net 혹은 C-net이 도출된다.
이번 포스팅에서는 휴리스틱 마이닝에 대해 알아 보았다. 앞서 말했듯이 휴리스틱 마이닝은 알파 알고리즘이 가지고 있는 한계점인 frequency를 고려하지 못한다는 점, loop를 찾아낼 수 없다는 점을 모두 극복할 수 있다는 장점을 가진다. 또한 이 때문에 노이즈를 필터링할 수 있기 때문에 real data를 이용하여 프로세스 모델을 도출할 때에 더 유용하게 사용될 수 있다. 다양한 process discovery 알고리즘들 중에 자신의 데이터에 맞는 알고리즘을 적절하게 선택하여 사용하는 것이 중요하다!
최근댓글