Active Trace Clustering이란?

 Trace Clustering이란, 프로세스 마이닝에서 비슷한 속성을 가진 trace들을 클러스터링하는 것을 말한다. 이러한 Trace Clustering은 프로세스 분석이나 비교적 이해하기 쉬운 프로세스 모델을 도출하는 데에 도움을 준다. Trace Clustering에는 각 trace의 속성을 이용하여 clustering을 하는 기본적인 방법부터 액티비티의 앞뒤 맥락을 파악하여 clustering을 하는 Context Aware Trace Clustering 등 다양한 방법이 존재한다. 이번 포스팅에서는 Trace Clustering의 방법 중 하나인 Active Trace Clustering에 대해 알아보겠다. 

 

Motivation

 Active Trace Clustering은 기존 Trace Clustering 방법이 가지고 있던 한계인 Clustering의 성능을 높이는 것과 프로세스 모델 자체의 성능을 높이는 것 사이의 간극을 줄이기 위해 등장했다. 기존 Trace Clustering 방법은 비슷한 특성을(feature)을 가지고 있는 trace들을 clustering하는 것을 목적으로 했다. 즉, Clustering의 성능을 높이기 위해 기존의 데이터 마이닝에서의 clustering처럼 클러스터 내의 similarity를 높이고, 클러스터끼리의 similarity를 낮추는 것을 목적으로 한 것이다. 하지만 이러한 방법은 각 클러스터로부터 도출된 프로세스 모델의 성능은 보장하지 못한다는 단점을 가진다.  Active Trace Clustering은, 이러한 한계점을 해결하기 위해 특성이 비슷한 trace들을 clustering하기보다는, 특정 프로세스 모델에 잘 맞는 trace들끼리 clustering을 하는 것을 해결책으로 제시한다. 

 

Algorithm

 Active Trace Clustering의 알고리즘은 selection, look ahead, residual trace resolution의 세 단계로 이루어진다. 그 알고리즘은 다음과 같다. (알고리즘 내에서 dpi는 Distinct Process Instance, 즉 하나의 trace를 말한다.) 알고리즘을 시작하기 전에 우리는, 원하는 클러스터의 개수(nb_cluster), 목표 fitenss (tf), 최소 클러스터 크기 기준 (mcs), window size (w)를 미리 정한다.

Active Trace Clustering의 알고리즘

 이제 이 알고리즘의 세 단계를 하나씩 설명해보겠다.

Selection

 Selection은 초기 클러스터를 형성하는 단계이다. 즉, 클러스터 내의 trace들을 바탕으로 프로세스 모델을 만들고, 이 프로세스 모델의 성능을 좋게 유지하면서 trace를 추가해나가는 단계이다. Selection 단계에서는 Frequency-based selective sampling과 Distance-based selective sampling의 두 가지 sampling 방법을 사용해 trace를 선택한다.

 

Frequency-based selective samping

 Frequency-based selecive sampling은 말 그대로 가장 frequency가 높은 trace를 가장 중요한 trace로 생각하고, 이를 선택하는 것을 말한다. 맨 처음 초기 클러스터를 만들 때 사용되는 방법으로, 클러스터에 아무 trace도 포함되어 있지 않거나 빈도가 상위 w%에 속하는 trace의 개수가 하나일 때, 현재 cluster에 더할 trace를 가장 빈도가 높은 trace로 지정한다.

 

Distance-based selective sampling

 Distance-based selective sampling은 기존 cluster와 가장 비슷한 특성을 가지는 trace를 선택하는 것을 말한다. 이는 위의 frequency-based selective sampling이 사용되지 않아야 하는 경우 (클러스터에 trace가 이미 포함되어 있거나 빈도가 상위 w%에 속하는 trace의 개수가 여러 개일 때)에 사용되고, 현재 cluster에 더할 trace를 기존 cluster와 가장 비슷한 특성을 가지는 trace로 지정한다.

 

 위 sampling 방법을 이용하여 trace를 지정했다면, 이 trace와 기존 cluster 내의 traece들을 바탕으로 휴리스틱 마이닝을 통해 프로세스 모델을 만든다. 이 프로세스 모델의 fitness가 목표 fitness 값(tf)보다 높다면 cluster에 해당 trace를 포함하고, 그렇지 않은 경우, 현재 cluster의 사이즈를 측정한다. 그리고 현재 cluster의 크기, 즉 현재 cluster에 포함된 trace의 개수가 (아직 클러스터에 포함되지 않고 남은 trace 개수 * mcs) 값보다 작으면 현재 trace를 무시하고, 그렇지 않다면 Look ahead 단계를 진행한다.

Look Ahead

 Look Ahead는 앞 단계에서 도출한 클러스터가 도출한 프로세스 모델에 맞는 나머지 trace들을 클러스터에 포함시킴으로써 클러스터의 크기를 키우는 단계이다. 즉, 아직 cluster에 포함되지 않은 trace들에 대해서 이들이 클러스터로부터 도출되는 프로세스 모델에 fitting한다면, 이를 클러스터에 포함시킴으로써 클러스터의 크기를 키워나간다.

 

이렇게 Selection 단계와 Look Ahead 단계를 클러스터의 개수가 원하는 클러스터의 개수(nb)가 될 때까지 반복한다.

 

Residual Trace Resolution

 Residual Trace Resolution 단계는  이 단계까지 cluster에 포함되지 못한 trace를 처리하는 단계이다. 이에는 두 가지 옵션이 있는데, 남은 각 trace를 fitness가 가장 높은 cluster에 분배하거나 남은 trace들을 묶어서 하나의 cluster를 만드는 것이다.

 

이렇게 Residual Trace Resolution 단계까지 거치면 알고리즘이 종료된다.

 

Limitation

 Active Trace Clustering 알고리즘의 한계점은, 각 trace 간의 빈도가 고르지 않게 분포해 있다고 가정했다는 점이다. 만약 각 trace의 빈도가 고르게 분포해(uniform) 있다면, 이 알고리즘은 Selection과 Look Ahead 단계에서 충분히 크기가 큰 클러스터를 만들 수 없다. 또한 process discovery 알고리즘으로 휴리스틱 마이닝을 특정했고, 프로세스 모델을 평가하는 기준을 fitness로 한정했다는 것도 한계점이 될 수 있다. 

 

 이번 포스팅에서는 trace clustering의 또 다른 방법인 Active Trace Clustering에 대해 알아보았다. 각자의 목적에 맞는 적절한 trace clustering 알고리즘을 사용하는 것이 중요할 것이다. 

 

글을 오랜만에 썼더니 잘 안 써진다.......... ㅠㅠ

References

Weerdt, Jochen & vanden Broucke, Seppe & Vanthienen, Jan & Baesens, Bart. (2013). Active Trace Clustering for Improved Process Discovery. IEEE Trans. Knowl. Data Eng.. 25. 2708-2720. 10.1109/TKDE.2013.64.