저번 포스팅에서 우리는 프로세스 마이닝의 trace clustering을 어떻게 할 수 있는지에 대해 알아보았다. 이번 포스팅에서는 해당 논문에서 사용한 clustring distance meaure인 Euclidean distance, Hamming distance, Jaccard distance에 대해 알아보겠다.
Euclidean distance
Euclidean distance는 우리가 일반적으로 생각하는 거리의 개념과 가장 비슷하다. 점 (1, 2), (5, 7)이 있다면 우리는 이 두 점 사이의 거리를 다음과 같은 식으로 계산한다.
즉, 같은 dimension의 값을 뺀 것의 제곱의 합의 루트값이 Euclidean distance라고 할 수 있다. 이를 점 p = (p1, p2, ..., pn)와 점 q = (q1, q2, ..., qn) 사이의 거리를 표현한 일반적인 식으로 나타내면 다음과 같다.
이를 프로세스 마이닝의 trace clustering에서 사용하는 profile 개념과 연결하여 설명해보겠다. 다음과 같은 activity profile을 가지는 case 3개가 있다고 하자.
그렇다면, case 1의 activity profile과 case 2의 activity profile의 Euclidean distance는 다음과 같은 식으로 계산할 수 있다.
Hamming distance
Hamming distance는 binary 문자열에서의 서로 다른 문자의 개수이다. 예를 들어, 11001라는 문자열이 있고 10111이라는 문자열이 있으면, 이들의 Hamming distance는 처음의 1과 마지막의 1이 일치하기 때문에 5 - 2 = 3으로 계산할 수 있다. 이를 점 p = (p1, p2, ..., pn)와 점 q = (q1, q2, ..., qn) 사이의 거리를 표현한 일반적인 식으로 나타내면 다음과 같다.
이것 또한 프로세스 마이닝의 trace clustering의 profile 개념과 연결하여 설명해보겠다. 프로세스 마이닝의 trace clustering에서는 Hamming distance를 다음과 같은 형태로 약간 변형하여 사용한다.
즉, p_k와 q_k가 모두 0이거나 모두 0 초과의 값을 가지면 1, 이외의 경우는 0을 가지고 이들의 합을 전체 profile 길이로 나눈 값을 Hamming distance로 정의한다. 아까 전에 들었던 예시와 같은 activity profile을 가지는 case가 3개 있다고 하자.
case 1의 activity profile과 case 2의 activity profile은 a가 1과 2에서 둘다 0 초과이고 d가 1과 2에서 둘다 0 초과이므로 a와 d에서 1이고, 나머지인 b와 c에서 0이다. 그러므로 Hamming distance는 (1+1)/4=0.5가 된다.
Jaccard distance
Jaccard distance는 1에서 두 집합의 교집합 원소의 개수 / 두 집합의 합집합 원소의 개수를 뺀 값으로 정의한다. 예를 들어, 집합 1이 {빨강, 초록}이고, 집합 2가 {초록, 노랑, 파랑}이라면 이는 1 - n(초록) / n(빨강, 초록, 노랑, 파랑) = 1 - 1/4 = 0.75로 계산할 수 있다. 이를 일반적인 식으로 나타내면 다음과 같다.
이것 또한 프로세스 마이닝의 trace clustering의 profile 개념과 연결하여 설명해보겠다. 프로세스 마이닝의 trace clustering에서는 Hamming distance를 다음과 같은 형태로 약간 변형하여 사용한다.
아까 전에 들었던 예시와 같은 activity profile을 가지는 case가 3개 있다고 하자.
case 1의 activity profile과 case 2의 activity profile에 대해 Jaccard distance은 다음과 같은 계산식을 통해 구할 수 있다.
이번 포스팅에서는 프로세스 마이닝의 trace clustering에서 사용하는 distance measure 3가지에 대해 알아보았다.
최근댓글