Fuzzy Mining(Fuzzy Miner)이란?

 많은 process discovery 알고리즘들이 고질적으로 가지고 있는 문제점은, 정제되지 않은 실생활 데이터를 넣었을 때 굉장히 복잡하고 한 눈에 무엇이 중요하고 무엇이 중요하지 않은지 알아볼 수 없는 "spaghetti" 모델을 도출한다는 것이다. 

복잡한 spaghetti model. 거의 spaghetti 수준이 아니라 spaghettini

  이러한 문제점을 해결하기 위해 등장한 알고리즘이 fuzzy mining이다. 이번 포스팅에서는 이 fuzzy mining 알고리즘에 대해 알아보겠다.

Motivation & 기본 아이디어

 Fuzzy miner의 기본적인 아이디어는 지도의 원리와 비슷하다.

지금 살고 있는 곳을 다른 축적으로 표현한 지도. 건물이 표시되는 정도, 길이 표시되는 정도 등이 다르다.

지도는 실제로 있는 모든 건물과 길을 싹 다 표시하기보다는, 확대하거나 축소함에 따라 정보를 합하거나, 생략하거나, 더 중요한 정보에 대해서는 강조하거나, 용도에 따라 다른 것을 표시하고는 한다. Fuzzy miner도 이벤트 로그에 나타나는 모든 액티비티와 엣지를 표시하기보다는, 중요도(significance)나 correlation에 따라 액티비티와 엣지를 합하거내 생략함으로써 좀 더 간단하고 보기 쉬운 프로세스 모델을 도출하는 것을 목표로 한다. 그렇다면 여기서, 중요도(significance)와 correlation은 무엇을 말하는 것일까? 그들의 의미는 다음과 같다.

 

• significance: 액티비티와 엣지가 나타내는 behavior의 상대적인 중요도를 말한다. 그 예시로는 빈도(frequency)가 있을 수 있다. 많이 일어난 액티비티와 많이 일어난 엣지가 상대적으로 더 중요하다고 생각하는 것이다.
• correlation: 두 이벤트가 얼마나 관련이 있는지(closely related)를 말한다. 데이터 상으로 더 많은 공통점을 가지고 있거나 이름이 비슷한 것(예를 들어, check_customer_application과 approve_customer_application과 같이 이름이 비슷하면 서로 연관되어 있을 확률이 높다.)이 correlation이 높다고 할 수 있다.

 이 두가지 척도에 따라 우리는 프로세스 모델을 간략화할 때에 무엇을 표시하고 무엇을 표시하지 않을 것인지를 결정할 수 있다. 그것은 다음과 같은 기준을 따른다.

 

• 중요도가 높은 것 (high significance): 간략화된 모델에서도 유지된다.
• 중요도는 낮지만 correlation이 높은 것 (less significant but highly correlated): cluster 안에 숨겨진다.
• 중요도도 낮고, correlation도 낮은 것 (less significant and lowly correlated): 생략된다.

이러한 기본적인 아이디어를 바탕으로 Fuzzy Miner 알고리즘이 진행된다.

Significance와 Correlation Metrics

 우선, Fuzzy Miner를 진행하기 위해서는 significance와 correlation을 명확한 수치로 정의할 필요가 있을 것이다. 여기에는 크게 unary significance metrics, binary significance metrics, binary correlation metrics의 세 가지 metric들이 이용된다. 

Unary Significance Metrics

 Unary Significance Metrics는 쉽게 얘기하면 각 액티비티의 중요도를 나타내는 수치이다. 이를 기준으로 중요도가 낮은 액티비티는 생략되고, 중요도가 높은 액티비티는 남아 있을 것이다. 이에는 두 가지 종류가 있다.

• frequency significance: 빈도. 빈도가 높을수록 중요하고, 빈도가 낮을수록 덜 중요하다고 판단한다. 
• routing significance: 해당 지점에서 split나 join을 많이 할수록 해당 액티비티가 더 중요하다고 판단한다. 그렇기 때문에 incoming arc와 outgoing arc의 숫자 혹은 significance의 차이가 클수록 중요도가 높다고 판단한다.

Binary Significance Metrics

 Binary Significance Metrics는 각 edge의 중요도를 나타내는 수치이다. 이를 기준으로 중요도가 낮은 엣지는 생략되고, 중요도가 높은 엣지는 남아 있는다. 이에는 두 가지 종류가 있다. 

• frequency significance: 빈도. 빈도가 높을수록 중요하고, 빈도가 낮을수록 덜 중요하다고 판단한다.
• distance significance: 해당 엣지의 significance와 source, target node(액티비티)의 significance의 차이가 클수록 distance significance가 낮아진다. (전체 프로세스 모델에서 중요한 엣지라면 연관된 node들에게도 중요도가 높을 것이라는 가정 하에 정의되었다.)

Binary Correlation Metrics

 Binary Correlation Metrics는 서로 다른 두 액티비티의 연관성을 나타내는 수치이다. 이에는 네 종류가 있다.

• proximity correlation: 연속으로 나타나는 두 액티비티는 연관성이 높다고 판단한다. 
• originator correlation: 액티비티를 수행한 사람(resource)의 이름이 비슷할수록 연관성이 높다고 판단한다. (resource의 이름에 부서, 업무명 등이 표현될 가능성이 있기 때문)
• endpoint correlation: 액티비티의 이름이 비슷할수록 연관성이 높다고 판단한다. 
• data value correlation: 다른 attribute들을 이용하여 data 상으로 비슷하면 연관성이 높다고 판단한다. 

Fuzzy Miner

이제 본격적인 알고리즘이 어떻게 진행되는지에 대해 알아보겠다. 우선, 이벤트 로그에서 나타나는 모든 액티비티를 unary significance와 함께 표현하고, 모든 엣지를 binary significance와 binary correlation과 함께 표현하여 날 것의 프로세스 모델을 만든다. 그 이후에 엣지를 정리하는 Conflict Resolution과 Edge Filtering, 액티비티 노드를 정리하는 aggregation & abstraction 과정을 거쳐 모델을 간단하게 만든다.

Conflict Resolution

 Conflict Resolution은 두 액티비티가 양방향으로 모두 연결되어 있는 conflict 상태를 정리하는 과정이다. 

conflict

이 conflict를 정의하기 위해서는 relative significance 값을 계산해야 한다. 이는 다음 식에 따라서 계산할 수 있다.

relative significance의 계산식. N은 process model의 모든 node를 말한다.

 또한 다음과 같이 offset 값도 정의해 주어야 한다. 

offset의 계산식

Conflict가 나타나는 경우는 세 가지가 있다.

• Length-2-Loop: <A,B,A> 혹은 <B,A,B> 등의 형태로 length-2-loop가 발생할 때 conflict가 생긴다. 이는 rel(A,B) 값과 rel(B,A) 값이 모두 지정한 preserve threshold 이상인 경우를 말한다. 이 때는 A->B, B->A 모두 생략하지 않는다.
• Exception: A->B가 정상적인 behavior이지만 가끔 B->A가 예외적으로 발생하는 형태이다. 이는 rel(A,B) 값과 rel(B,A) 값 중 하나 이상이 preserve threshold 미만이고, ofs(A,B) 값이 지정한 ratio threshold 이상인 경우를 말한다. 이 때는 정상적인 behavior(relative significance가 큰 액티비티)만 남기고 예외는 생략한다.
• Concurrnecy: 두 액티비티가 parallel하게 순서에 상관없이 모두 발생한다. 이는 rel(A,B) 값과 rel(B,A) 값 중 하나 이상이 preserve threshold 미만이고, ofs(A,B) 값이 지정한 ratio threshold 미만인 경우를 말한다. 이 경우에는 A->B, B->A relation을 모두 생략한다.

 이 과정에서 모든 conflict 엣지들을 검토하고 필요한 부분은 필터링한다.

Edge Filtering

 전 단계에서 conflict edge를 정리함으로써 edge들을 어느 정도 정리했지만, 아직 많은 수의 edge들이 남아있다. 이 단계에서는 그 edge들을 binary significance 값과 binary correlation 값을 기준으로 하여 정리한다. 이의 기준이 되는 값이 utility 값이다. 이는 다음과 같이 계산할 수 있다.

utility 값의 계산식. ur은 0과 1 사이로 지정한 utility ratio 값이다. 

예를 들어, 다음과 같이 A에 연결된 P, Q, R, S 액티비티와 그 엣지들이 있다고 하자. 그리고 그들의 significance와 correlation 값은 다음과 같다.

주어진 P, Q, R, S 엣지

 이들의 utility 값을 ur=0.5라고 생각하고 계산하면 다음과 같다.

계산된 utility 값

utility 값을 모두 계산했으면, 이들을 normalize해준다. 그리고 그 normalize한 값을 지정된 edge cutoff parameter을 기준으로 그 이하의 값을 가지는 edge들을 필터링한다. 즉, edge cutoff parameter가 높을수록 더 많은 edge들이 필터링되는 것이다. 예를 들어, 우리의 edge cutoff parameter를 0.4라고 하자. 그러면 우리의 edge는 다음과 같이 filtering될 것이다.

normalized utility 값이 edge cutoff parameter인 0.4를 넘는 P, R 엣지만남는다.

  이 과정에서 conflict가 아닌 엣지들까지 significance와 correlation 값을 기준으로 필터링한다. 

Aggregation & Abstraction

 앞선 단계들에서 엣지를 필터링했다면, 이 단계에서는 unary significance과 correlation을 기준으로 노드를 필터링한다. 우선, node cutoff paramer를 기준으로 이보다 낮은 significance 값을 가지는 노드들을 모두 후보(victim)로 둔다. 이 후보들은 모두 다른 노드에 합쳐지거나(aggregation) 생략될(abstraction) 것이다. 모든 후보들에 대해서 다음과 같은 방법으로 initial cluster들을 만든다.

1. 각 후보들에 대해 이 후보에 직접적으로 연결된 node 중 가장 correlation이 높은 node를 찾는다.
2. 찾은 node가 cluster node이면 이 후보를 해당 cluster에 포함시킨다. 이 때, 후보의 incoming, outgoing edge들을 cluster에 합쳐준다.
3. 찾은 node가 cluster node가 아니면 후보를 새로운 cluster로 만든다.

위 방법으로 initial cluster를 만들었으면, 이제 다음 방법으로 이 cluster들을 merge한다. 

1. 각 cluster들에 대해 앞에 직접 연결된 (선행) 것들과 뒤에 직접 연결된 (후행) 것들이 cluster인지 확인한다.
2. 만약 모든 앞에 오는 것들이 cluster라면 가장 correlation이 높은 cluster와 merge한다.
3. 만약 모든 뒤에 오는 것들이 cluster라면 가장 correlation이 높은 cluster와 merge한다.
4. 2와 3이 둘 다 아니라면 (앞 뒤에 모두 cluster가 아닌 node가 연결되어 있다면) cluster를 그냥 두고 다음 cluster로 넘어간다.

위 방법으로 cluster merge가 끝나면 abstraction을 진행한다. 즉, 혼자 따로 떨어져 있는(isolated) cluster나 하나의 액티비티로 구성된(singular) cluster가 있다면 이들을 제거한다. 이 때, 가장 significance가 높은 선행 edge는 남겨둠으로써 behavior가 왜곡되지 않도록 한다.

 이 과정에서 node들을 필터링함으로써 프로세스 모델을 더 간단하게 만들어 준다. 이렇게 Fuzzy Miner 알고리즘은 끝이 난다.

 

 이번 포스팅에서는 Fuzzy Miner를 이용해서 스파게티 모델에서 벗어나 쉽고 빠르고 정확하게, 한 눈에 알아볼 수 있는 프로세스 모델을 도출하는 방법에 대해 알아보았다. 이를 통해 복잡한 대용량의 데이터가 있더라도 이로부터 직관적인 프로세스 모델을 도출하는 것이 가능하다. 

와 글 썼었는데 밑에가 왠지 모르게 날아가서 감기 걸린 몸을 이끌고 다시 썼다... 개발자 반성하세요.... 흑흑

References

1. Günther C.W., van der Aalst W.M.P. (2007) Fuzzy Mining – Adaptive Process Simplification Based on Multi-perspective Metrics. In: Alonso G., Dadam P., Rosemann M. (eds) Business Process Management. BPM 2007. Lecture Notes in Computer Science, vol 4714. Springer, Berlin, Heidelberg