1. 서 론

최근 기술의 발달에 따른 연산․저장 장치의 발전으 로 데이터를 수집하고 저장할 수 있는 정보시스템에서 다루어야 하는 데이터의 양 또한 급격히 증가하였다. 이 에 축적된 데이터를 처리하고 분석할 수 있는 기술에 대 한 필요성은 더욱 커져가고 있는 상황이다. 프로세스 마 이닝(process mining)은 이러한 정보시스템을 이용하는 과정에서 기록된 데이터 중 프로세스를 수행하는 과정에 서 기록되는 이벤트 로그 데이터에 초점을 맞추어 이를 바탕으로 프로세스에 대한 의미 있는 정보를 찾아내는 분석 기법이다[13]. 이때, 프로세스는 제품과 서비스를 전달함으로써 새로운 가치를 창출할 수 있는 활동들을 조직화한 구성체를 의미한다[10].

이러한 프로세스 마이닝 분석 기술은 3가지 형태로 구분할 수 있다. 먼저, 프로세스 모델 도출은 이벤트 로그 데이터를 입력 받아 프로세스 모델을 생성하는 것이다. 둘 째, 순응도 평가는 이벤트 로그와 프로세스 모델 간 비교 를 통해 실제 프로세스가 프로세스 모델에 따라 수행되는 지 확인함으로써 모델의 품질을 평가하는 것이다. 셋째, 프로세스 모델 개선은 이벤트 로그에서 획득할 수 있는 정보와 프로세스 모델을 이용해 프로세스 모델의 품질을 향상시키는 것이다. 이 중에서 실제로 일어난 일을 시각화 해서 정량적으로 분석할 수 있는 바탕이 된다는 점과 순응 도 평가나 프로세스 모델 개선과 같은 다른 방식의 프로세 스 마이닝 분석의 입력 데이터가 된다는 점에서 프로세스 모델 도출 기술이 제일 중요하다고 할 수 있다.

한편, 프로세스 모델은 크게 결정적 프로세스 모델과 확률적 프로세스 모델로 나눌 수 있다. 결정적 프로세스 모델은 액티비티의 순서가 정해져 있고, 프로세스를 수행 하는 과정에서 발생하는 액티비티 수행시간 등에 확률적 정보를 포함하고 있지 않다. 따라서 대상 시스템의 실행 흐름만을 파악할 수 있을 뿐 시스템의 성능 분석에는 활 용할 수 없다는 한계를 지니고 있다. 그러나 확률적 프로 세스 모델은 액티비티 순서가 확률적 분포에 의해 결정되 며, 이벤트 로그에 기록된 액티비티 수행시간에 대한 확 률 정보를 포함하고 있는 프로세스 모델로써 잔여작업시 간 추정과 같은 시스템 성능 분석에 활용되어 프로세스에 대한 이해를 증진시킬 수 있다는 장점을 갖는다.

지금까지 이벤트 로그 데이터를 이용한 프로세스 모델 생성 연구로써 유전자 프로세스 마이닝 알고리즘(Genetic Process Mining : GPM)[15, 16]과 시뮬레이티드 어닐링 (Simulated Annealing)-유전자 프로세스 마이닝 알고리즘 [3]이 제안되었다. 그러나 GPM 알고리즘은 노이즈가 있 는 데이터를 다룰 수 있다는 장점이 있지만, 프로세스 모 델을 도출하기 위한 연산 수행시간이 길어 대용량 데이 터인 경우가 많은 실제 프로세스를 분석하기에 어려움이 따른다. 또한 SA-GPM 알고리즘은 적합도가 낮아 이에 대한 개선이 필요한 실정이다.

따라서 본 논문은 두 가지 목적을 해결하고자 하였다. 첫째, 프로세스 마이닝 분석에서 가장 중요한 역할을 하 는 프로세스 모델의 표현력을 향상시켜 프로세스에 대한 추가적인 분석을 수행할 수 있도록 프로세스 트리에 확 률 요소를 표현할 수 있는 확률적 프로세스 트리를 제안 하는 것이다. 둘째, 확률적 프로세스 트리를 보다 효율적 인 방법으로 도출하기 위해 타부 서치를 유전자 알고리 즘에 접목시킨 타부 서치(Tabu Search)-유전자 프로세스 마이닝(TS-GPM) 알고리즘을 설계하는 것이다.

본 논문에서는 이를 위해 연속해서 수행되는 액티비 티를 나타낸 문자열인 트레이스(trace)가 이벤트 로그에 나타난 확률을 계산한 시퀀스 확률 정보와 이벤트 로그 로부터 획득한 액티비티를 완료하는데 걸리는 액티비티 수행시간, 한 액티비티가 종료된 뒤 다른 액티비티를 수 행하기 전 대기 시간인 액티비티 간 시간 간격에 대한 확률 분포를 확률적 프로세스 트리에 반영하였다. 따라 서 확률적 프로세스 트리는 기존의 결정적 프로세스 모 델이 갖고 있는 시스템 분석에 대한 제약을 해결해주고, 시스템의 성능을 분석함으로써 현실 세계의 프로세스에 대한 더 많은 정보를 제공할 수 있다.

또한, 유전 연산이 끝나고 난 뒤 품질이 낮은 프로세 스 트리로 생성할 수 있는 액티비티 수행 순서를 기록한 문자열 trace를 타부 목록에 저장하여 품질이 낮은 프로 세스 트리에 대한 중복 탐색을 방지함으로써 우수한 품 질을 갖는 프로세스 트리를 도출할 수 있도록 하였다. 결 과적으로, 제안된 TS-GPM 알고리즘은 연산 수행시간이 오래 걸려 복잡도가 높은 프로세스를 분석하기에 어렵다 는 GPM 알고리즘의 문제를 해결해 줄 수 있다.

2. 관련 연구 분석

2.1 프로세스 모델

프로세스 모델은 현실 세계의 복잡한 프로세스를 쉽게 이해하기 위해 액티비티 간의 연관관계를 추상화된 모델 로 시각화한 것이다[13]. 프로세스 모델 중 대표적인 것으 로는 페트리 넷 기반의 프로세스 모델이 있다. 페트리 넷 은 토큰, 플레이스, 트랜지션, 아크를 이용한 대표적인 프 로세스 모델 표현 방법으로 토큰이 한 플레이스에서 아크 로 연결된 다른 플레이스로 트랜지션되는 과정을 통해서 프로세스 내 자원의 흐름을 표현한다[8, 9, 11, 14]. 하지 만 페트리 넷을 이용한 프로세스 모델은 deadlock이나 livelock과 같은 비정상 행동이 발생할 가능성이 존재하는 불완전 모델이 될 수 있다는 위험성을 지닌다[9].

이러한 한계점을 보완하기 위해 프로세스 트리 기반 프로세스 모델이 제안되었다. 프로세스 트리는 계층 구 조를 갖는 cycle이 없는 유향 그래프로 정의된다. 프로세 스 트리는 이벤트 로그에 나타난 액티비티를 표현하기 위한 액티비티 노드와 액티비티 노드 간 연관관계를 표 현하기 위한 연산자 노드로 이루어져있다. 연산자 노드 는 sequence(→), parallel(∧), or(∨), exclusive or(×), loop (↻) 등의 5가지 종류가 있다[1, 3]. <Figure 1>은 5가지 연산자 노드에 대한 적용 예를 나타낸다. Sequence 연산 자는 연결되어 있는 하위 노드를 왼쪽부터 순서대로 실 행하고, parallel 연산자는 연결되어 있는 모든 하위 노드 를 반드시 실행하되 연결된 순서와 상관없이 실행한다. 또, or 연산자는 하위 노드 중 하나 이상을 선택해 연결 된 순서에 상관없이 실행하며, exclusive or 연산자는 하 위 트리 중 단 하나만을 선택해 실행한다. Loop 연산자 는 하위 트리를 임의의 횟수만큼 반복 실행한다.

이 모델은 연산자 노드와 액티비티 노드를 통해 실제 프로세스의 흐름을 비교적 직관적으로 표현할 수 있고, 페 트리 넷에서 발생할 수 있는 불완전 모델을 생성하지 않음 으로써 프로세스 모델을 탐색하는 과정에서 탐색 공간이 축소되어 근사 최적 프로세스 모델 도출을 위한 연산 시간 을 단축할 수 있다는 장점을 가지고 있다[1, 18]. 그러나 이러한 모델들은 모두 액티비티의 수행 순서가 정해져 있 는 결정적 프로세스 모델의 일종으로써 확률 요소를 반영 하고 있지 않아 프로세스의 분석에 있어 한계를 지닌다.

한편, 확률적 프로세스 모델은 결정적 프로세스 모델 과 달리 이벤트 로그로부터 추출한 액티비티 수행시간 분포나 액티비티 발생 확률을 표현함으로써 잔여작업시 간 추정이나 프로세스 모델을 이용한 시뮬레이션 등의 추가적인 분석을 가능하게 함으로써 프로세스에 대한 이 해도를 높일 수 있도록 해준다. 이러한 확률적 프로세스 모델의 대표적 예시로 확률적 페트리 넷이 있다[8, 9]. 이 넷은 트랜지션으로 표현되는 액티비티 간 시간 간격 분 포가 추가되며, time delay가 없는 여러 개의 트랜지션이 동시에 가능한 경우에는 모든 경우에 대한 트랜지션 확 률을 weight로 나타낸다. 하지만 확률적 페트리 넷은 결 정적 페트리 넷에서 발생하는 구조적 한계점(불완전 모 델)을 가지고 있다는 점에서 여전히 한계가 있다.

2.2 프로세스 모델 도출 방법론

지금까지 제안된 대표적인 프로세스 모델 도출 방법 으로 유전자 알고리즘 기반의 GPM 알고리즘이 있다[1, 3, 6, 15, 16, 18]. 이 방법은 자연 생물 진화 과정의 원리 로부터 착안한 메타 휴리스틱 알고리즘인 유전자 알고리 즘을 이용한 프로세스 모델 도출 방법론이다. 각 염색체 에 대한 적합도 평가에는 프로세스 모델의 순응도를 평 가하는 4가지 척도인 replay fitness, precision, simplicity, generalization)[2]를 이용한다. 새로운 염색체 집단의 생 성은 적합도 측정, 선택, 유전 연산의 과정을 반복해 적 합도를 증가시키는 방향으로 수행된다. 이러한 GPM 알 고리즘은 노이즈가 있는 데이터를 다룰 수 있다는 장점 이 있지만, 근사 최적 프로세스 트리 도출을 위한 연산 시간이 길기 때문에 일반적으로 데이터의 크기가 큰 실 제 데이터에 적용하기 어렵다는 한계를 가진다.

이러한 단점을 보완하기 위해 유전자 알고리즘에 다 른 메타 휴리스틱 알고리즘을 접목한 방법론을 하이브리 드 유전자 알고리즘이라 한다[3, 6]. 하이브리드 유전자 알고리즘 기반의 프로세스 모델 도출 연구로는 유전자 알고리즘에 시뮬레이티드 어닐링 알고리즘을 결합해 프 로세스 트리를 도출하는 SA-GPM 알고리즘이 있다[3]. 이 알고리즘은 초기 프로세스 트리 집단 생성 연산과 선 택 연산에서 적합도가 낮은 염색체들을 대체할 때 SA를 이용해 프로세스 트리를 생성한다는 점에서 기존 유전자 알고리즘과 차이를 보이지만 적합도 평가나 유전 연산 과정에서는 유전자 알고리즘과 동일한 방식의 연산을 수 행하게 된다. Khezerlou and Alizaheh[3]에서는 SA-GPM 알고리즘과 GPM 알고리즘을 비교하기 위해 같은 시간 동안 각 알고리즘을 통해 연산을 수행했을 때 SA-GPM 알고리즘을 통해 도출된 프로세스 트리가 기존의 GPM 알고리즘을 통해 도출된 프로세스 트리보다 더 높은 평 균 적합도 값을 갖는 것을 보였다[3].

3. TS-GPM 알고리즘 제안

3.1 확률적 프로세스 트리 정의 및 제안

본 논문에서 제안하는 확률적 프로세스 트리는 크게 2 가지의 확률적 요소를 포함하고 있다. 이는 프로세스 트 리의 연산자 노드에 연결된 액티비티들을 이용해 액티비 티 조합을 생성할 때, 특정 액티비티 조합이 생성될 확률 을 기록한 시퀀스 확률 정보와 시간 정보 노드이다.

시퀀스 확률 정보는 프로세스 트리의 5가지 연산자 노 드 중 여러 가지의 trace(액티비티 수행 순서에 따라 액티 비티를 나열한 문자열)를 도출할 수 있는 parallel 연산자, or 연산자, exclusive or 연산자에 추가된다. 시퀀스 확률정 보는 연산자 노드에 연결된 노드들을 통해 생성할 수 있는 sub-trace들이 이벤트 로그에서 나타난 확률을 계산해 추 정할 수 있다. 시간 정보 노드는 단일 액티비티를 수행하 는데 소요되는 시간을 나타내는 단일 액티비티 실행 시간 노드와 프로세스 수행과정에서 발생할 수 있는 인접 액티 비티 간의 유휴시간을 나타내는 노드로 구분된다.

<Figure 2>는 시퀀스 확률 정보와 시간 정보 노드가 반 영된 확률적 프로세스 트리의 예시를 나타낸다. 예를 들어 ‘1_XOR’(노드 번호가 1번인 exclusive or 연산자 노드)는 해당 연산자 노드에 연결된 액티비티 노드 ‘2_Restart repair’, ‘3_Archive repair’, ‘4_Inform user’에 대한 시퀀스 확 률 정보인 P₂, P₃, P₄가 기록되어 있다. 또한 사각형으로 표현된 시간 정보 노드는 하나의 액티비티를 수행하는 데 걸리는 시간이나 액티비티를 수행하는 사이에 발생하는 대기 시간을 표현하는 확률 분포의 매개변수가 기록되어 있다.

단일 액티비티 수행 시간 노드는 S_k (S₆)과 같이 영문 자 S(single activity)로 표현되며 아래 첨자 k는 액티비티 노드의 번호나 이름을 의미한다. 인접 액티비티 간 시간 간격 노드는 A_ij(A₁₅, A₅₅)와 같이 영문자 A(adjacency activity) 로 표현되며, 아래 첨자 i는 프로세스 트리에서 먼 저 실행되는 선행 연산자 노드의 번호나 이름을, j는 나 중에 실행되는 후속 연산자 노드의 번호나 이름을 의미 한다.

<Figure 3>은 이벤트 로그를 이용해 확률적 프로세스 트리의 연산자 노드에 포함되는 시퀀스 확률 정보를 계 산하는 방법을 나타낸다. (ⅰ)과 같이 연산자 노드에 연 결된 2개의 액티비티 노드 a, b로 이루어진 프로세스 트 리가 있다고 한다면 이 프로세스 트리의 연산자 노드가 parallel, or, exclusive or 연산자일 때 액티비티 노드 a, b 에 대한 시퀀스 확률 정보는 다음과 같이 추정된다. 먼저 (ⅱ)와 같이 전체 이벤트 로그 중 계산 대상이 되는 연산 자 노드에 연결된 액티비티 노드가 발생한 이벤트 로그 를 필터링해 확률 정보를 계산한다. (ⅲ)은 연결된 여러 액티비티 중 한 개만을 선택하는 xor일 때 시퀀스 확률 정보를 계산하는 방법을 나타낸 것이다. 시퀀스 확률은 해당 액티비티가 발생한 빈도수를 연산자 노드에 연결된 모든 액티비티의 빈도수의 합계로 나누어 계산한다. 예 를 들면, 시퀀스 확률 P_a와 P_b는 각 액티비티가 발생한 빈도수를 freq(a) + freq(b) 나누어 계산한다.

하지만 p개의 액티비티 노드와 연결된 or 연산자 노드 인 경우 추가적으로 sub-trace를 생성하기 위한 하위 액티 비티의 갯수 (q, 0 < q ≦ p)를 먼저 결정해야 한다. 이때, 하 위 액티비티 갯수를 결정하기 위한 확률은 P_one (p개 중 1 개의 액티비티만 이용하는 확률), P_two (p개 중 2개의 액티 비티 이용 확률), P_n (p개의 액티비티 모두 이용하는 확률) 과 같이 표현한다. 예를 들어 <Figure 3>의 (ⅳ)에서 P_one 은 or 연산자에 연결된 액티비티 a와 b 중 1개만 발생한 이벤트 로그의 갯수 4를 연산자에 연결된 액티비티 a 또는 b 중 하나 이상이 한번이라도 발생한 이벤트 로그의 총 갯수인 10으로 나누어 계산할 수 있으며, 그 결과 P_one값 은 0.4가 된다. 이와 같은 방법으로 or 연산자에 n개의 액 티비티가 연결되어있는 경우 P_one , P_two , …, P_n을 모두 계 산해 sub-trace를 생성할 액티비티의 갯수에 대한 확률을 결정한다.

Or 연산자의 sub-trace를 생성할 하위 액티비티 수(q) 를 확률 값에 따라 결정한 뒤 그 결과가 2개 이상인 경 우(q ≧ 2)는 q개의 시퀀스 확률을 비교해 sub-trace를 구 성하는 액티비티의 순서를 결정한다. 예를 들어 <Figure 3>의 (ⅳ)에서 n이 2인 경우, P_ab(P_a>b)는 a가 b보다 먼저 나타난 trace(9, 10, 11, 18번)의 갯수 4를 액티비티 a, b 를 모두 포함하고 있는 trace(9, 10, 11, 18, 19, 20번)의 갯수인 6으로 나누어 계산하고, P_ab(P_a<b) 는 동일한 방 법으로 b가 a보다 먼저 나타난 trace의 갯수를 액티비티 a, b를 모두 포함하고 있는 trace 갯수로 나누어 계산한 다. 이때, 이벤트 로그의 trace를 이용해 액티비티 a와 b 간의 선후 관계를 판단하고자 하는 경우에는 trace에 기 록된 액티비티 중 선후 관계를 파악하는 대상이 되는 액 티비티를 제외한 다른 액티비티는 고려하지 않는다. 즉, a와 b 사이의 선후관계를 고려하는 경우 ‘a-c-d-b’와 같은 trace에서 c, d 액티비티는 고려하지 않는다.

이렇게 생성된 확률적 프로세스 트리로부터 model trace 를 생성하는 방법은 <Figure 4>와 같이 가능한 모든 trace 연산을 수행하지 않고 시퀀스 확률 정보에 의해 가장 발생 확률이 높은 trace만을 도출한다. (ⅰ) Exclusive or(xor) 연 산자 노드는 2개의 시퀀스 확률 정보 P_a와 P_b의 값에 따라 액티비티 노드 a와 b 중 한 개를 선택해 trace를 생성한다. (ⅱ) or 연산자 노드는 2개의 액티비티 노드 중 몇 개의 액티비티를 선택할 것인지 P_one과 P_two의 값에 따라 갯수 를 결정한 뒤, 시퀀스 확률 정보에 의해 trace를 생성한다. 이 경우는 P_one값이 0.4, P_two값이 0.6이므로 확률값에 따 라 한 가지를 선택해 trace를 생성한다. 만일 2개의 액티비 티를 이용해 trace를 생성하는 경우, P_ab 값이 2/3, P_ba 값이 1/3이므로 trace는 2/3 확률로 a-b가, 1/3 확률로 b-a가 생성 된다. 마지막으로, (ⅲ) parallel 연산자 노드에서도 P_ab, P_ba 확률 값에 따라 trace로 a-b 혹은 b-a를 생성한다.

3.2 TS-GPM 알고리즘 설계

3.2.1 기본 아이디어

본 논문에서 제안된 TS-GPM 알고리즘의 기본 아이디 어는 다음과 같다. 먼저, 프로세스 트리를 하나의 염색체 로 정의하고 elitism, replace, crossover, mutation 등의 유 전 연산을 수행한다[1, 3]. 이때, 적합도가 낮은 프로세스 트리가 생성하는 model trace를 타부 목록에 저장한다. 그 뒤 다음 세대의 염색체 집합을 생성하는 과정에서 새 로 생성된 프로세스 트리의 trace와 타부 목록에 저장된 trace 간의 유사도를 비교하여 새로 생성된 프로세스 트 리 중 타부 목록과의 유사도가 높은 프로세스 트리는 다 음 세대로 전달하지 않는다. 이를 통해 적합도가 낮은 트 리를 재탐색하는 것을 방지할 수 있다.

3.2.2 염색체 정의

염색체는 하나의 프로세스 트리를 나타내며 크기가 n × m인 2차원 배열 형태로 정의된다. <Table 1>은 <Figure 2>의 프로세스 트리를 크기가 10 × 8인 2차원 배열 형태 의 염색체로 표현한 예시이다. 행의 수를 나타내는 n 값 은 각 프로세스 트리가 포함하고 있는 액티비티 노드 갯 수와 연산자 노드 갯수의 합과 같다.

2차원 배열로 표현된 프로세스 트리 염색체는 8가지의 속성값을 가진다. NodeNo 속성은 프로세스 트리를 구성 하는 노드를 구분하기 위한 노드 번호 값을 의미한다. NodeName 속성은 노드 이름과 노드 번호(NodeNo)를 ‘노 드 번호_이름’ 형태로 표현한 것이다. Parents 속성은 각 노드에 직접 연결된 부모 노드(상위 노드)의 NodeName 이며, Depth(깊이)는 0보다 큰 정수 값으로 프로세스 트리 에서 노드가 위치한 깊이를 의미한다. 루트 노드(최상단 노드)의 깊이는 항상 0이며 하위 노드로 내려갈수록 깊이 는 1씩 증가한다. NodeClass 속성값은 각 노드의 종류를 표현하기 위한 이진수로써 연산자 노드는 1, 액티비티 노 드는 0을 갖는다. Sequence probability information 속성값 은 parallel, or, exclusive or 연산자만 그 값을 가지며 해당 연산자 노드에 연결된 액티비티 노드에 대한 시퀀스 확률 값이 저장된다. Timing information 속성값은 액티비티 노 드일 때는 단일 액티비티 노드 수행 시간 분포가, 연산자 노드일 경우에는 인접 액티비티 간 시간 간격 분포 노드 의 매개 변수 값을 갖는다. Path는 프로세스 트리를 구성 하는 노드 간 계층 관계를 나타내며, 해당 노드에 연결된 상위노드의 이름을 루트 노드부터 차례로 기록하고 있다. 예를 들어 <Table 1>에서 2_Restart Repair의 Path 값인 SEQ(Root)/1_XOR/2_Restart Repair는 루트 노드(SEQ)부 터 해당 노드(2_Restart Repair)까지 계층 관계로 연결된 연산자 노드와 액티비티 노드를 / 기호로 구분해 기술한 것이다.

3.2.3 초기 염색체 집합 생성

초기 염색체 집합은 프로세스 트리를 개체집단의 크 기만큼 무작위 생성해 초기 염색체 집합을 생성한다. 본 논문에서는 이를 위해 난수 벡터를 이용하며, 초기 프로 세스 트리에는 이벤트 로그에 있는 액티비티가 한 번씩 만 포함된다고 가정한다. 따라서 초기 프로세스 트리에 있는 액티비티 노드 갯수는 이벤트 로그에 있는 액티비 티 수와 동일하다. <Figure 5>는 난수 벡터를 생성하고 그 값에 따라 랜덤 프로세스 트리를 생성하는 절차이다.

난수 벡터 기반의 프로세스 트리 무작위 생성은 두 단 계를 거쳐 이루어진다. 1단계에서는 먼저 벡터의 원소 합이 입력 이벤트 로그의 액티비티 갯수와 같은 난수 벡 터를 생성한다. 난수 벡터를 이용하여 벡터의 원소가 1 인 경우에는 그 자리에 액티비티 노드를 배치하고, 원소 가 1보다 큰 경우, 예를 들면 r인 경우 그 자리에 r개의 자녀 노드를 갖는 연산자 노드를 배치한다. <Figure 5>의 (ⅰ)에서 난수 벡터 성분의 합이 5인 벡터를 생성한 결과 가 {1, 4}이므로 (ⅰ)의 우측에 있는 구조와 같은 프로세 스 트리를 생성한다.

2단계에서는 다양한 깊이를 갖는 프로세스 트리를 생성 하기 위해 깊이 증가 규칙에 따라 깊이를 증가시킬 것인지 여부를 결정한다. 깊이 증가 규칙이란 각 깊이 마다 하나 의 난수 벡터 원소가 해당 깊이의 난수 벡터 원소 합의 50%보다 크거나 같은 경우만 해당 연산자 노드에서 깊이 를 증가시킨다는 것이다. 예를 들어 <Figure 5>의 (ⅰ)에서 깊이가 1일 때 난수 벡터 {1, 4}를 보면, 2번째 원소인 4가 난수 벡터 원소 합인 5의 50% 보다 크므로(4 > 2.5), 자녀 노드를 4개 갖는 해당 연산자 노드에서 깊이를 2로 증가시 키게 된다. 깊이가 증가하면 그 지점에서 해당 난수 벡터 원소를 나누는 새로운 난수 벡터를 생성하고 난수 벡터의 원소 값에 따라 앞의 과정을 반복 수행한다.

<Figure 5>의 (ⅱ)를 보면 깊이가 1에서 2로 증가한 지 점에서 난수 벡터의 원소 값인 4를 분배한 새로운 난수 벡터 {1, 2, 1}을 생성한 것을 볼 수 있으며, 깊이가 1일 때와 마찬가지로 2번째 원소 값인 2가 난수 벡터의 원소 합 4의 50%인 2와 같으므로 깊이를 2에서 3으로 증가시 킨다. (ⅲ)과 같이 난수 벡터의 모든 원소 값이 1이 되어 더 이상 깊이 증가 연산을 수행할 수 없을 때 난수 벡터 생성을 중지하게 된다. 난수 벡터 생성이 중단되면 해당 위치의 난수 값에 따라 액티비티 노드와 연산자 노드를 할당하는데, 앞에서 정의한 것과 같이 액티비티 노드는 하나의 프로세스 트리에서 한번만 나타나므로 이벤트 로 그의 액티비티 집합에서 비복원 랜덤 추출을 수행하며, 연산자 노드는 하나의 프로세스 트리에서 여러 번 나타 날 수 있으므로 복원 랜덤 추출을 수행한다. (ⅳ)는 난수 벡터의 원소 값에 따라 액티비티 노드와 연산자 노드를 배치한 예시를 나타낸다.

3.2.4 프로세스 트리기반 Model Trace 생성

<Figure 6>은 프로세스 트리로부터 이벤트 로그를 생 성할 때 액티비티를 실행 순서에 따라 나열한 문자열인 model trace를 생성하는 방법을 나타낸다. 먼저 (i) Sequence 연산자는 하위 액티비티 노드를 왼쪽부터 차례로 실행하므 로 A-B-C-D 문자열 하나만을 trace로 갖는다. (ii) Parallel 연산자는 하위 액티비티 노드를 순서에 상관없이 모두 실 행하므로 A, B, C, D 노드를 모두 실행하는 ₄P₄ = 4!개의 trace가 가능하다. (iii) Exclusive or(XOR) 연산자는 하위 액티비티 노드 중 한 개만을 선택하여 실행하므로 A, B, C, D 4개의 trace가 가능하다. (iv) Or 연산자의 경우 먼저 4개의 하위 노드 중 trace를 생성할 m(m ≦ 4)개의 액티 비티 노드를 선택한 뒤, m개의 액티비티 노드를 이용해 생성할 수 있는 가능한 모든 조합을 반영한 m!개의 trace 를 생성한다.

<Figure 7>은 <Figure 6>에서 정의한 trace 도출 규칙에 따라 프로세스 트리의 model trace를 도출하는 3단계 규 칙을 나타낸 것이다. 먼저 (ⅰ)단계에서 프로세스 트리를 구성하는 모든 노드에 대해 trace를 도출해 이를 allnode trace라 정의한다. allnode trace에서 액티비티 노드의 trace 는 자기 자신이 되며, 연산자 노드의 trace는 연산자 노드 의 종류와 하위 액티비티 노드에 따라 결정된다.

그 다음, (ⅱ)단계에서 가장 깊이 위치한 연산자 노드 부터 노드 trace를 갱신한다. 예를 들어, <Figure 7>의 프 로세스 트리에 따라 가장 깊은 곳에 위치한 노드인 OR 노드에서 OR 노드의 trace에 해당하는 ‘B, E, B-E, E-B’ 를 이용해 상위 노드인 PAR노드의 trace를 갱신하고, 상 위 노드의 trace를 갱신한 뒤 OR 노드의 trace를 지워준 다((ⅱ)단계 우측 테이블). (ⅲ)단계에서는 루트 노드를 제외한 연산자 노드의 trace 중 갱신할 노드가 없을 때까 지 (ⅱ)단계를 반복 실행한다. 마지막으로 allnode trace에 서 루트 노드의 노드 trace 값을 model trace로 반환한다. 이러한 과정을 통해 프로세스 트리를 이용해 표현할 수 있는 모든 trace를 도출할 수 있다.

3.2.5 적합도 평가

본 논문에서는 프로세스 트리의 적합도 평가 기준으로 프로세스 모델의 순응도 평가 척도인 replay fitness, precision, simplicity, generalization의 가중 평균값을 이용한다 [1, 3, 12]. 각각의 척도에 대한 설명은 다음과 같다. Replay fitness는 log trace 문자열과 model trace 문자열의 공통부 분인 intersection의 길이를 모든 model trace 문자열 길이 의 합으로 나누어 계산한다. Precision은 model trace 갯수 와 log trace 갯수 사이의 대소 관계에 따라 다른 식을 이용 한다. 먼저, model trace의 갯수가 log trace 갯수보다 많은 경우는 intersect 집합에 포함된 trace의 갯수를 model trace 갯수로 나누어 precision을 계산하고, log trace 갯수가 model trace의 갯수보다 같거나 많은 경우는 intersect 집합 에 포함된 trace 수를 log trace 로 나누어 계산한다.

Simplicity는 프로세스 트리에 중복된 액티비티 노드나 이벤트 로그에서 발생하지 않은 액티비티가 포함되어 있 는 경우, Or 연산자 혹은 Loop 연산자가 포함된 경우에 대해 이와 같은 요소들이 프로세스 트리의 복잡도를 높인 다고 간주해 벌점을 부과하여 계산한다. Generalization은 프로세스 트리에 나타난 노드의 실행 횟수의 제곱근에 역 수를 취해 더한 값을 프로세스 트리에 있는 노드 갯수로 나누어 계산할 수 있다.

3.2.6 유전 연산

본 논문에서는 새로운 염색체 집합을 생성하기 위한 elitism, crossover, mutation, replace 유전 연산을 <Figure 8>과 같이 설계하였다. 먼저, elitism 연산은 전체 염색체 집합 중 우수한 적합도를 갖는 상위 elite rate만큼의 개체 들을 선별하고, 이 우수 염색체 집합(elite set)을 다음 세 대 염색체 집합에 그대로 전달한다[4].

Replace 연산은 elitism 연산과 반대로 전체 염색체 집 합 중 하위 inferior rate만큼의 낮은 적합도를 갖는 개체 들을 뽑아 선택된 열등한 부분집합(inferior set)을 전체 염색체 집합에서 제거하고, 제거된 부분을 새로 랜덤 생 성된 프로세스 트리로 대체한다[4]. 본 논문에서는 염색 체 집합에서 elite set과 inferior set에 해당하지 않는 부분 집합을 genetic operation set이라 정의하고 이들 전체를 대상으로 crossover 연산을 수행한 뒤 일정확률에 따라 mutation 연산을 수행한다.

Crossover 연산은 서로 다른 두 parent tree의 일부분인 sub-tree를 맞바꾸어 새로운 child tree를 생성하는 연산을 수행하며, 프로세스 트리의 sub-tree는 연산자 노드와 그 에 연결된 하위 노드 혹은, 하나의 액티비티 노드가 모두 될 수 있다. Mutation 연산은 crossover 연산을 수행한 뒤 각 프로세스 트리의 일부분을 설정된 mutation rate의 확 률에 따라 변화시켜 새로운 특성을 갖는 프로세스 트리 를 생성한다. Mutation 연산에는 랜덤 선택된 연산자 노 드의 종류를 바꾸는 operator node mutation, 랜덤 선택된 sub-tree를 제거하는 sub-tree removal, 랜덤 선택된 연산 자 노드에 하나의 액티비티 노드를 추가하는 single activity node addition의 3가지 세부 연산을 적용한다.

3.2.7 타부 목록 생성

타부 목록에는 적합도가 낮은 프로세스 트리로부터 생성할 수 있는 model trace가 저장된다. <Figure 9>는 population_n을 이용해 타부 목록을 생성하고 새로운 염 색체 집합인 population_n+1을 생성하는 방법을 나타낸다.

타부 서치는 유전 연산 과정에서 crossover와 mutation 연산 수행 전후의 프로세스 트리 집합인 genetic operation set과 genetic operation set’을 합한 집합인 tabu search input set을 입력으로 받아 거기에 포함된 프로세스 트리로 부터 생성된 model trace와 tabu list에 저장된 trace 간의 유사도를 edit distance와 KL divergence를 기준으로 측정 하는 방식으로 수행된다[5, 7]. 측정된 유사도를 기준으로 유사도가 낮으면서 동시에 높은 적합도를 갖는 프로세스 트리를 필터링해 이들을 tabu search output set이라 하며, 다음 세대의 염색체 집합(population_n+1)을 생성할 때 elite set과 replace set, tabu search output set을 이용한다.

4. 수치 실험

4.1 실험 설계

제안된 타부 TS-GPM 알고리즘의 성능을 측정하기 위한 수치 실험을 설계하였다. <Table 2>는 감도 분석 실험을 통해 결정된 수치 실험을 위한 매개변수와 그 값을 나타낸 다. 이 중에서 sampling rate는 model trace 도출 과정에서 전체 model trace 중 추출할 trace의 비율을 나타낸다. 이는 model trace를 도출하는 과정에서 parallel 연산자나 or 연산 자의 경우 연결된 child node 수가 늘어남에 따라 트리로부 터 도출할 수 있는 trace의 개수와 trace 도출을 위한 연산 시간이 급격하게 증가하기 때문에 사용된 방법이다.

적합도 평가를 위한 가중 평균의 가중치는 프로세스 모델이 이벤트 로그에 기록된 행동을 얼마나 잘 반영하 고 있는지 평가하는 replay fitness에 가장 큰 가중치 20, simplicity에 17, generalization에 15, precision에 0.5를 부 여하였다. 식 (1)은 이를 반영한 적합도 함수를 나타낸다.

프로세스 마이닝 알고리즘의 성능을 측정하기 위한 이 벤트 로그 데이터로써 <Table 3>과 같은 속성 값을 갖는 Repair event log[13]와 teleclaim event log[10]를 사용하였 다. Repair event log는 휴대 전화 A/S 센터에서의 고장 수 리 프로세스를 수행하는 과정을 기록한 이벤트 로그 데이 터이다. 7,734개의 이벤트를 포함하고 있으며, 1,104가지 의 케이스(고장 수리 프로세스)로 구성되었다. 이 이벤트 로그는 수리 접수, 고장 점검, 단순 고장 수리, 복잡 고장 수리 등의 8가지의 액티비티로 구성되어 있으며 이들 액티 비티가 시작된 시각, 종료된 시각이 모두 기록되어 있다.

두 번째 이벤트 로그인 teleclaim event log는 보험회사 의 콜센터서 처리된 보험금 청구 및 심사 과정을 기록한 것으로써 9,701개의 이벤트를 포함하고 있으며, 1,382가 지의 케이스(보험금 청구 프로세스)로 구성되었다[17]. 이 이벤트 로그는 보험금 청구 접수, 증빙 자료 확인, 보 험금 청구 심사 등록, 보험금 지급 등의 11가지 액티비 티로 이루어져 있으며 repair event log와 마찬가지로 각 액티비티의 시작 시각과 종료 시각이 기록되어있다.

제안된 알고리즘과의 성능 비교를 위한 기준으로 기 존에 제안된 GPM 알고리즘을 적용하였다. 구체적인 실 험 절차는 감도 분석 실험을 통해 결정된 매개변수 값을 바탕으로 2종의 이벤트 로그(repair, teleclaim)를 입력받 아 두 알고리즘을 수행해 프로세스 트리를 도출하고, 트 리의 적합도 값을 평가하는 방식으로 수행하였다. 이때, 각 이벤트 로그에 대해 알고리즘을 100회 만큼 반복 실 행해 프로세스 트리를 도출하는 실험과 100회의 반복 연 산을 수행하는 시간의 약 10~20%에 해당하는 500초 동 안 알고리즘을 실행하는 2가지 방식의 실험을 설계하였 다. 모든 실험은 각 조건에 대해 30회씩 반복 수행되었 으며, RAM 16GB, CPU Intel(R) Core^TM i5-3570 3.40GHz 데스크톱 환경에서 R 프로그래밍 언어를 통해 구현되었다.

4.2 실험 결과 분석

<Table 4>는 repair event log 데이터를 GPM 알고리즘 과 TS-GPM 알고리즘에 적용해 프로세스 트리를 탐색하 는 실험을 30회 반복 수행한 뒤 각 알고리즘을 통해 도 출된 프로세스 트리의 적합도 값의 차이가 통계적으로 유의한지 확인하기 위해 실시된 t-test 결과를 나타낸다. 30회의 반복 실험을 수행한 뒤 각 알고리즘을 통해 도출 한 프로세스 트리의 적합도 값을 통계적으로 비교하기 위해 다음과 같은 귀무가설과 대립가설을 수립하고, 유 의 수준은 0.05로 설정해 t-test를 수행하였다.

<Table 4>에서 100세대의 연산을 수행한 결과, 적합도 값의 평균은 GPM 알고리즘은 0.823, TS-GPM 알고리즘 은 0.861로 TS-GPM 알고리즘이 평균 약 4.6% 적합도가 높은 해를 도출하였다. 이에 대한 t-test 결과를 보면 p값 이 0.016이므로 TS-GPM 알고리즘이 도출한 프로세스 트리 적합도가 높다는 대립가설을 채택한다.

<Table 4>에서 500초 동안 실험을 수행한 결과, 적합 도 값의 평균은 GPM 알고리즘의 경우 0.818, TS-GPM 알고리즘의 경우 0.861로 TS-GPM 알고리즘이 GPM 알 고리즘보다 평균적으로 약 5.05% 높은 적합도 값을 갖는 프로세스 트리를 도출하였다. 500초의 연산 시간동안 수 행된 실험 결과 도출된 적합도 값에 대한 t-test 결과를 살펴보면 p값이 0.013이므로 TS-GPM 알고리즘을 통해 도출된 프로세스 트리의 적합도가 높다는 대립가설을 채 택한다.

<Table 4>에서 두 가지 방식의 실험 결과 도출된 적합 도의 평균값을 보면, TS-GPM 알고리즘의 경우 100세대 반복 연산을 수행한 경우와 500초 간 연산을 수행한 경우 모두 0.861로 같은 평균 적합도 값이 나타냈지만, GPM 알고리즘의 경우 100세대와 500초 간 연산을 수행한 결과 최고 적합도의 평균값이 각각 0.823과 0.818로 차이가 나 타났다. 이는 TS-GPM 알고리즘의 경우 연산 초기에 매 우 빠른 속도로 높은 적합도 값을 갖는 프로세스 트리를 탐색한 뒤 적합도 값에 큰 변화가 일어나지 않지만, GPM 알고리즘은 시간을 두고 점진적으로 높은 적합도 값을 갖 는 프로세스 트리를 탐색해 나가기 때문인 것으로 해석될 수 있다.

<Table 5>는 <Table 4>의 500초 동안 GPM알고리즘과 TS-GPM 알고리즘을 이용해 프로세스 트리를 도출하는 실험에서 최고 적합도 값을 갖는 프로세스 트리가 도출된 시점의 세대 수와 연산 시간을 비교한 것이다. GPM 알고 리즘은 연산을 시작한지 평균 약 304초 지나서야 최고 적 합도를 갖는 트리를 도출한 반면, TS-GPM 알고리즘은 약 92.9초 뒤 최고 적합도를 갖는 트리를 도출했으며, 적 합도 값 또한 TS-GPM 알고리즘을 통해 도출한 프로세스 트리가 약 5.5% 높은 것을 볼 수 있다. 즉, 본 논문에서 제안하는 TS-GPM 알고리즘이 GPM 대비 약 30.6%의 시 간 내에 높은 적합도 값을 갖는 프로세스 트리를 탐색할 수 있다.

<Table 6>은 teleclaim event log 데이터를 GPM 알고리 즘과 TS-GPM 알고리즘에 적용해 프로세스 트리를 탐색 하는 실험을 30회 반복 수행한 뒤, 각 알고리즘을 통해 도 출된 프로세스 트리의 적합도 값의 평균 차이가 통계적으 로 유의한지 확인하기 위해 실시된 t-test 결과를 나타낸 다. 100세대의 연산을 수행한 결과를 보면 적합도 값의 평균은 GPM 알고리즘과 TS-GPM 알고리즘이 각각 0.812, 0.851로 TS-GPM 알고리즘이 평균 약 4.8% 적합도 가 높은 해를 도출한 것을 볼 수 있다. 또한, 적합도 값의 평균에 대한 t-test 결과를 살펴보면 p값이 0.0000000013 이므로 TS-GPM 알고리즘을 통해 도출된 프로세스 트리 의 적합도가 높다는 대립가설을 채택한다.

500초 동안 연산을 수행해 도출된 프로세스 트리의 적 합도 값과 주어진 시간 동안 가장 높은 적합도를 갖는 프 로세스 트리를 도출한 시각을 측정한 실험 결과를 보면, 적합도의 평균값은 GPM 알고리즘과 TS-GPM 알고리즘 이 각각 0.799, 0.851로 TS-GPM 알고리즘이 평균적으로 약 6.73% 높은 적합도 값을 갖는 프로세스 트리를 도출한 것을 볼 수 있다. 500초의 연산 시간동안 수행된 실험 결 과 도출된 적합도 값에 대한 t-test 결과를 살펴보면 p값이 0.00000004로 TS-GPM 알고리즘을 통해 도출된 프로세스 트리의 적합도가 더 높다는 대립가설을 채택한다.

마지막으로 <Table 7>은 <Table 6>의 500초 동안 GPM 알고리즘과 TS-GPM 알고리즘을 이용해 프로세스 트리 를 도출하는 실험에서 최고 적합도 값을 갖는 프로세스 트리가 도출된 시점에서의 세대 수와 연산 시간을 비교한 것이다. GPM 알고리즘의 경우 평균 연산 시작 약 424.79 초 후 최고 적합도를 갖는 트리를 도출한 반면, TS-GPM 알고리즘은 약 53.4초 후 최고 적합도를 갖는 트리를 도 출했다. 적합도 값 또한 TS-GPM 알고리즘을 통해 도출 한 프로세스 트리가 약 6.73% 높은 것을 볼 수 있다. 즉, 본 논문에서 제안하는 TS-GPM 알고리즘이 약 86% 적은 시간 내에 높은 적합도 값을 갖는 프로세스 트리를 탐색 할 수 있다.

5. 결 론

본 논문은 결정적 프로세스 트리가 가지고 있는 표현 상의 한계를 극복하기 위한 새로운 확률적 프로세스 모델 링 방법으로써 확률적 프로세스 트리와 이를 도출하기 위 한 TS-GPM 알고리즘을 제안하였다. 이 알고리즘은 GPM 알고리즘에 타부 서치를 적용한 방법으로써 적합도가 낮은 프로세스 트리로부터 도출된 model trace를 타부 목록에 저장하고, 유전 연산을 반복 수행하는 과정에서 새로 생 성된 프로세스 트리로부터 도출된 model trace와의 유사 도를 비교해 중복 탐색을 방지함으로써 적합도를 빠르게 증가시킬 수 있는 방법이다.

본 논문에서 제안한 TS-GPM 알고리즘과 기존의 GPM 알고리즘의 성능을 측정하기 위해 기존 연구에서 사용되 었던 2종류의 이벤트 로그를 이용해 프로세스 트리를 도 출하고, 프로세스 트리의 품질을 측정해 결과를 비교하는 실험을 수행하였다. 실험은 동일 횟수의 유전 연산을 반 복하는 것과, 고정된 시간 동안 연산을 수행하는 두 가지 방법으로 수행되었다. 실험 결과 모든 경우에 대해 본 논 문에서 제안한 TS-GPM 알고리즘이 기존의 GPM 알고리 즘에 비해 우수한 품질을 갖는 해를 매우 빠른 속도로 탐 색할 수 있음을 검증하였다.

연구 추후 방향으로는 제안된 알고리즘의 한계로 평 가될 수 있는 확장성의 개선을 위해 규모가 큰 이벤트 로그 데이터 분석에 대한 유효성을 검증할 예정이다. 또 한 도출된 확률적 프로세스 트리를 시스템 성능 분석에 이용할 수 있는 방법론을 연구하고자 한다.