간만의 포스팅. 블로그 시작한 이후로 가장 긴 공백기였던 것 같다. 다른 것을 쓰고 있어서 집에서까지 글을 쓰고 싶지 않았다 ㅎㅎ
실제 이벤트 로그는 크고 복잡하다. 그래서 이 이벤트 로그로 프로세스 모델을 도출해보면, 한 눈에 알아볼 수 없는 복잡한 구조의 spaghetti model이 나오는 경우가 많다.
이러한 상황에서 이벤트 로그 안에 있는 각각의 trace들을 clustering하고, 이 cluster별로 프로세스 모델을 도출한다면 문제를 어느 정도 해결할 수 있을 것이다. 뿐만 아니라 비슷한 속성의 trace들을 clustering함으로써 이들 각각의 특성을 파악하는 데에도 도움이 될 것이다. 이번 포스팅에서는 프로세스 마이닝에서 trace clustering을 어떻게 할 수 있는지에 대해 개괄적으로 알아볼 것이다.
Profile
profile은 각 trace의 속성을 나타낸다. Trace는 액티비티의 종류, resource의 종류 등 다양한 속성들을 가질 수 있기 때문에 profile의 종류도 다양하다. 이 profile을 설명하기 전에, 다음과 같은 이벤트 로그가 있다고 하자. 이벤트 로그가 무엇인지 모른다면 다음 포스팅을 참고한다.
2019/05/31 - [Process Mining - Theory] - 이벤트 로그(event log)란?
이벤트 로그(event log)란?
이벤트 로그란, 프로세스 마이닝의 가장 기본이 되는 데이터 형태이다. 프로세스 마이닝을 하기 위해서는 이벤트 로그가 반드시 있어야 하기 때문에, 현재 있는 데이터를 프로세스 마이닝에 활용하고 싶다면 이를..
process-mining.tistory.com
| Case ID | Activity | Timestamp | Resource | place | case type |
| 1 | a | 2019-11-20 | jang | Aachen | G |
| 1 | b | 2019-11-21 | lee | Cologne | G |
| 1 | d | 2019-11-22 | jang | Aachen | G |
| 2 | a | 2015-09-13 | kim | Pohang | F |
| 2 | c | 2016-01-01 | jang | Seoul | F |
| 2 | d | 2017-11-11 | park | Pohang | F |
| 3 | a | 2017-11-15 | kim | Seoul | L |
| 3 | d | 2018-4-27 | jang | Pohang | L |
Activity profile
Activity profile은 하나의 trace 안에서 일어난 각 액티비티의 개수를 나타낸다. 우리의 예시 이벤트 로그에서 case 1은 <a, b, d>, case 2는 <a, c, d>, case3은 <a, d> 로 일어났기 때문에 각 case의 activity profile은 다음과 같이 표현할 수 있다.
| Case ID | Activity Profile | |||
| a | b | c | d | |
| 1 | 1 | 1 | 0 | 1 |
| 2 | 1 | 0 | 1 | 1 |
| 3 | 1 | 0 | 0 | 1 |
Originator profile
Originator profile은 하나의 trace 안에서 이벤트를 수행한 각 resource의 수를 나타낸다. 우리의 예시 이벤트 로그에서 case 1은 <jang, lee, jang>, case 2는 <kim, jang ,park>, case3은 <kim, jang> 으로 일어났기 때문에 각 case의 originator profile은 다음과 같이 표현할 수 있다.
| Case ID | Originator Profile | |||
| jang | lee | kim | park | |
| 1 | 2 | 1 | 0 | 0 |
| 2 | 1 | 0 | 1 | 1 |
| 3 | 1 | 0 | 1 | 0 |
이 두개의 기본적인 profile 외에도 다양한 profile들을 도출할 수 있다.
Transition profile
Transition profile은 trace 내의 directly follows relation을 표현한다. 예를 들어, 우리의 예시 이벤트 로그에서 case 1은 <a, b, d>, case 2는 <a, c, d>, case3은 <a, d> 로 일어났기 때문에 case 1의 directly follows relation은 a->b, b->d, case 2는 a->c, c->d, case 3은 a->d가 있을 것이다. 그러므로 이를 표현하면 다음과 같이 표현할 수 있다.
| Case ID | Transition profile | |||||||||||||||
| a->a | a->b | a->c | a->d | b->a | b->b | b->c | b->d | c->a | c->b | c->c | c->d | d->a | d->b | d->c | d->d | |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Case attribute profile
Case attribute profile은 각 trace의 case attribute를 표현한다. Case attribute는 각 case id에 종속적인 attribute를 말한다. 같은 case id를 가지는 이벤트는 같은 case attribute를 공유한다. 우리의 예시에서는 case attribute에 해당하는 컬럼이 case type이기 때문에 다음과 같이 표현할 수 있다.
| Case ID | Case attribute profile | ||
| F | G | L | |
| 1 | 0 | 1 | 0 |
| 2 | 1 | 0 | 0 |
| 3 | 0 | 0 | 1 |
Event attribute profile
Event attribute profile은 각 trace의 event attribute를 표현한다. Event attribute는 각 event에 종속적인 attribute로, 각 event의 특성을 나타내기 때문에 이를 따라 clustering을 하면 각 trace가 가지고 있는 event의 특성에 따라 clustering이 가능하다. 우리의 예시에서는 case attribute에 해당하는 컬럼이 place이기 때문에 다음과 같이 표현할 수 있다.
| Case ID | Event attribute profile | |||
| Aachen | Cologne | Pohang | Seoul | |
| 1 | 2 | 1 | 0 | 0 |
| 2 | 0 | 0 | 2 | 1 |
| 3 | 0 | 0 | 1 | 1 |
Performance profile
Performance profile은 각 trace의 performance 정보를 표현한다. 이에는 trace의 길이, case 수행시간, 이벤트 수행시간의 minimum, maximum, mean, median, 대기 시간의 mimimum, maximum, mean, median 등이 될 수 있다.
이렇게 제시된 profile들 외에도 domain knoledge를 이용한 다양한 feature들을 만들어서 새로운 profile로 활용할 수 있다.
Clustering
이제 위에서 얻은 각 trace의 profile 정보를 이용해 clustering을 하면 된다. 각 distance measure와 clustering 알고리즘에 대해 설명하는 것은 포스팅의 방향과 맞지 않기 때문에 논문에 제시된 것이 무엇인지 정도만 간략히 나열하고, 각각에 대한 포스팅은 미래의 나에게 맡기겠다.
Distance Measure
Distance measure 각각에 대한 설명은 Process mining의 Clustering Distance Measure (Euclidean distance, Hamming distance, Jaccard distance) 포스팅을 참고한다.
- Euclidean distance
- Hamming distnace
- Jaccard distance
Clustering Algorithm
- K-means clustering
- Quality Threshold clustering
- Agglomerative Hierarchical clustering
- Self-Organizing Map
이번 포스팅에서는 프로세스 마이닝에서 trace clustering을 어떻게 할 수 있는지에 대해 개괄적으로 알아보았다. 이를 기본으로 해서 다양한 방향으로 자신에게 맞는 trace clustering이 가능할 것이다. 더 많은 프로세스 마이닝의 클러스터링에 대해 알고 싶다면 다음 Context Aware Trace Clustering, Active Trace Clustering 포스팅을 참고한다.
Context Aware Trace Clustering이란?
Trace Clustering이란, 프로세스 마이닝에서 비슷한 속성을 가진 trace들을 clustering하는 것을 말한다. process discovery 전의 trace clustering은 비교적 보기 쉽고 간단한 모델을 도출하는 데에 큰 도움을 준..
process-mining.tistory.com
References
1. Song M., Günther C.W., van der Aalst W.M.P. (2009) Trace Clustering in Process Mining. In: Ardagna D., Mecella M., Yang J. (eds) Business Process Management Workshops. BPM 2008. Lecture Notes in Business Information Processing, vol 17. Springer, Berlin, Heidelberg
최근댓글