이전에 우리는 알파 알고리즘에 대해 살펴 보았다. 알파 알고리즘은 이벤트 로그로부터 프로세스 모델을 가장 단순한 방법으로 도출해낼 수 있다는 장점을 가지지만, 알파 알고리즘은 몇 가지 치명적인 문제점들을 가진다.
2019/05/31 - [Theory/Process Discovery] - 알파 알고리즘 (Alpha Algorithm)이란?
알파 알고리즘 (Alpha Algorithm)이란?
알파 알고리즘(Alpha Algorithm)은 이벤트 로그로부터 프로세스 모델을 찾는, Process Discovery의 가장 기본이 되는 가장 단순한 알고리즘이다. 여태까지 Process Discovery가 무엇인지를 직관적으로 이해하지 못..
process-mining.tistory.com
Implicit Places
첫 번째 문제는 Implicit place가 만들어질 수 있다는 것이다. Implicit place란, 없어도 behavior에 아무 영향을 미치지 않는 불필요한 place를 의미한다. 예시를 통해 살펴보겠다.
위 L과 같은 이벤트 로그가 있다. 이 L에 대해서 알파 알고리즘을 적용해 보면 다음과 같은 형태의 페트리 넷이 도출된다. (과정은 생략한다.)
위 그림에서 초록색으로 표시된 place들이 바로 implicit place이다. 트랜지션 d가 fire되었을 때, p1과 그 위의 place에 모두 토큰이 생성되고, 트랜지션 g가 fire되면 이들이 모두 사라지는데, 이는 p1이 없어도 같은 behavior를 보일 것이다. 이는 p2에도 똑같이 적용된다. 이와 같이 알파 알고리즘을 적용하면, 불필요한 implicit place들이 만들어진다는 문제점이 있다.
하지만 이 문제점은 데이터 전처리를 하거나, implicit place가 도출되면 이를 삭제하는 방식으로 해결할 수 있다. 또한 implicit place를 포함한다고 해서 틀린 모델은 아니기 때문에 그렇게 큰 문제가 되지는 않는다.
length 1 loop를 다룰 수 없음
알파 알고리즘은 길이가 1인 loop를 제대로 표현할 수 없다. 길이가 1인 loop란, 자기 자신으로 화살표가 들어가고 나가서 해당 트랜지션만 반복되는 loop를 뜻한다. 이 또한 예시를 통해 살펴보겠다.
위 L과 같은 이벤트 로그가 있으면, 다음과 같이 생긴 모델이 도출되기를 바랄 것이다.
하지만 L에 대해서 알파 알고리즘을 적용해 보면, 다음과 같이 b가 unconnected인 모델이 도출된다.
이와 같이 알파 알고리즘으로는 길이가 1인 loop를 제대로 표현할 수 없다. 하지만 이 문제점은 알고리즘을 loop에 대해서만 약간 수정하거나 loop가 필요한 경우에 모델에 이를 추가하는 후처리를 하는 등의 방법으로 해결할 수 있다.
length 2 loop를 다룰 수 없음
위와 비슷하게, length가 2인 loop 또한 다룰 수 없다. 길이가 2인 loop란, b, c, b, c, b, c 와 같이 두 트랜지션이 계속 반복될 수 있는 형태를 의미한다. 이 또한 간단한 예시를 통해 살펴보겠다.
위 L과 같은 이벤트 로그가 있으면, 다음과 같이 생긴 모델이 도출되기를 바랄 것이다.
하지만 L에 대해서 알파 알고리즘을 적용해 보면, 다음과 같이 b c가 unconnected인 페트리 넷이 도출된다.
이와 같이 알파 알고리즘으로는 길이가 2인 loop도 제대로 표현할 수 없다. 이 문제점 또한 length 1 loop의 경우와 동일한 방법으로 해결할 수 있으므로 큰 문제점은 아니다.
Non-local dependencies
non-local dependency란, 직접적으로 연결되지는 않지만 특정 이벤트가 일어나야 일어나는 이벤트를 의미한다. 이 또한 예시를 통해 설명하는 것이 이해가 쉽다.
위와 같은 이벤트 로그 L이 있다고 하자. 이 때, d 액티비티는 반드시 a 액티비티가 일어나야 일어나고, e 액티비티는 반드시 b 액티비티가 일어나야 일어난다고 하자. 그렇다면 우리는 다음과 같은 페트리 넷을 원할 것이다.
하지만 이벤트 로그 L을 알파 알고리즘으로 표현하면 다음과 같은 페트리 넷이 도출된다.
위와 같이 우리는 알파 알고리즘으로는 non-local dependency를 고려할 수 없음을 알 수 있다. 하지만 이 문제점은 다른 process discovery 알고리즘에서도 발견되는 foundational problem이다.
도출된 모델이 항상 sound하지 못함
알파 알고리즘으로 도출된 프로세스 모델은 soundness를 보장하지 못한다. 몇몇 process discovery 알고리즘은 soundness를 보장하기도 한다.
Noise, Incompleteness
Noise란, 이벤트 로그가 포함하는 아웃라이어를 의미한다. 즉, 주류로 일어나는 trace가 아닌, 정말 낮은 빈도로 일어나는 trace들을 의미한다. 알파 알고리즘은 trace의 빈도를 고려하지 않고 모든 direct follow를 다 고려하기 때문에 아주 적은 빈도로 일어난 trace와 아주 많이 일어난 trace 모두 동등하게 페트리 넷에 나타난다는 문제점이 있다.
Incompleteness란, 이벤트 로그가 너무 적은 데이터를 포함하는 경우를 말한다. 이벤트 로그가 너무 적은 이벤트들만을 포함한다면 이를 통해 프로세스 모델을 도출하는 것은 신뢰도 문제를 가질 수 있다.
Noise와 Incompleteness는 알파 알고리즘만이 가지는 문제가 아닌, 다른 process discovery 방법들도 해결해야 하는 foundational problem이다.
알파 알고리즘이 가장 쉽고 직관적인 process discovery 알고리즘임은 분명하다. 하지만 위와 같은 문제점들을 가질 수도 있다는 것을 알고, 알파 알고리즘이 만능이 아닌 것에 유의하여 알고리즘을 적용해야 할 것이다.
References
1. Course: Business Process Intelligence. RWTH. Prof. Wil van der Aalst.
최근댓글