확률적 프로세스 트리 도출을 위한 타부 서치-유전자 프로세스 마이닝 알고리즘
Tabu Search–Genetic Process Mining Algorithm for Discovering Stochastic Process Tree
- 주제(키워드) 프로세스 마이닝 , 확률적 프로세스 모델 , 유전자 프로세스 마이닝 알고리즘
- 발행기관 아주대학교
- 지도교수 최진영
- 발행년도 2017
- 학위수여년월 2017. 2
- 학위명 석사
- 학과 및 전공 일반대학원 산업공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000024558
- 본문언어 한국어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
프로세스 마이닝은 프로세스를 분석 대상으로 삼아 프로세스를 시각화한 프로세스 모델을 도출하고, 도출된 모델을 실제 프로세스 수행과정과 비교함으로써 모델을 평가하며, 모델을 개선하는 활동을 수행해 프로세스에 대한 유용한 정보를 획득하는 것을 목표로 하는 분석 기법이다. 이러한 프로세스 마이닝에서 현실 세계의 프로세스를 잘 반영한 프로세스 모델을 도출하는 것이 가장 중요하다. 하지만 기존의 프로세스 모델들은 액티비티가 수행될 확률이나 액티비티를 수행하는 데 걸리는 시간과 같은 확률적 요소를 반영하고 있지 않은 결정적 프로세스 모델로서 이용할 수 있는 정보가 한정되어 있어 프로세스를 분석하고 이해하는 데 한계가 있다. 또한, 프로세스 모델을 도출하는 것과 더불어 프로세스 모델을 도출하기 위한 효율적인 방법론을 개발하는 것이 중요하다. 프로세스 모델 도출 방법론 중 하나인 유전자 프로세스 마이닝 알고리즘은 진화 과정을 모사한 메타 휴리스틱 알고리즘으로써 노이즈가 있는 데이터를 다룰 수 있지만, 연산 시간이 오래 걸려 대용량 데이터에 적용하기 어렵다는 한계점을 가진다. 본 논문에서는 이러한 문제점들을 개선하기 위해 확률적 프로세스 트리를 정의하고, 타부 서치-유전자 프로세스 마이닝 알고리즘을 제안하였다. 확률적 프로세스 트리는 확률적 요소를 반영하지 않은 기존의 프로세스 트리의 액티비티 노드와 연산자 노드와는 별도로 특정 액티비티 조합이 생성될 확률을 기록한 시퀀스 확률 정보 노드, 하나의 액티비티를 시작해서 마칠 때까지의 시간을 확률 분포로 표현한 단일 액티비티 수행 시간 노드, 여러 액티비티가 연속해서 실행되는 사이에 시스템의 대기 상태에 있는 시간을 확률 분포로 표현하는 인접 액티비티 간 시간 간격 노드를 정의하고 표현함으로써 확률적 요소를 반영하였다. 타부 서치-유전자 프로세스 마이닝 알고리즘은 확률적 프로세스 트리를 효율적으로 도출하기 위해 유전자 알고리즘에 타부 서치를 접목한 프로세스 모델 도출 방법론이다. 먼저, 프로세스 트리를 표현하기 위한 염색체로 2차원 배열을 정의하고, 초기 염색체 집합을 랜덤으로 생성한 뒤, 프로세스 트리의 적합도를 평가하였다. 그다음 유전 연산을 반복해 적합도를 증가시키는 방향으로 새로운 염색체 집합을 생성하였다. 유전 연산을 반복하는 과정에서 적합도가 낮은 프로세스 트리가 생성할 수 있는 액티비티를 수행 순서대로 나열한 문자열인 model trace를 타부 목록에 저장하고, 유전 연산을 통해 도출된 프로세스 트리가 생성할 수 있는 model trace와 타부 목록에 저장된 trace 간의 유사도를 비교해 이를 기준으로 프로세스 적합도가 낮은 해에 대한 중복 탐색을 방지하였다. 제안된 알고리즘의 성능을 검증하기 위해 기존 연구에서 사용된 2종의 이벤트 로그 데이터를 이용해 확률적 프로세스 트리를 도출한 뒤 모델의 적합도와 연산 시간을 비교 평가하는 실험을 수행하였다. 실험 결과 제안된 타부 서치-유전자 프로세스 마이닝 알고리즘이 적합도와 연산 시간의 측면에서 모두 기존의 유전자 프로세스 마이닝 알고리즘보다 우수한 성능을 나타냈다.
more초록/요약
Process mining is an analytical technique aimed at obtaining useful information about a process by (i) extracting a process model visualizing real world process, (ii) comparing it with the actual process for evaluation, and (iii) performing activities to improve the quality of the model. In process mining, it is most important to discover a process model that reflects real-world processes very well. However, most existing process models are deterministic because they do not include stochastic elements such as the occurrence probabilities or execution times of activities. Therefore, available information is limited, resulting in the limitations on analyzing and understanding the process. Furthermore, it is also important to develop an efficient methodology to discover the process model. Although genetic process mining algorithm is one of the methods that can handle data with noises, it has a limitation of large computation time when it is applied to data with large capacity. In this paper, we define a stochastic process tree and propose a tabu search-genetic process mining algorithm to resolve these issues. The suggested stochastic process tree reflects stochastic characteristics by introducing two special types of nodes such as (i) the sequence probability information node representing the probability that a specific combination of activities is generated, (ii) the single activity execution time node representing the probability distribution of the activity execution time, and (iii) the time interval node between two adjacent activities expressing the probability distribution of the idle time between two possible consecutive activities. The tabu search-genetic process mining algorithm efficiently discovers the suggested stochastic process tree by combining the genetic process mining algorithm with tabu list. In the algorithm, we first define a two-dimensional array as a chromosome to represent the process tree, an initial chromosome set is randomly generated, and the fitness values of the process trees are evaluated. Then, a new chromosome set is generated in the direction of increasing the fitness value by applying genetic operations such as crossover and mutation operations. In this procedure, a model trace, a string of activities that can be generated from the process tree, with a low fitness value is stored in the tabu list. By comparing the similarities among the model traces generated as the result of genetic operations with the traces stored in the tabu list, we can prevent duplicated searches for process trees with low fitness value being performed. In order to verify the performance of the proposed algorithm, we performed a numerical experiment by using two kinds of event log data used in the previous research. The results show that the suggested tabu search-genetic process mining algorithm outperformed the simple genetic process mining algorithm in terms of fitness and computation time.
more목차
제1장 서 론 1
제1절 연구 배경 및 필요성 1
제2절 연구 목적 및 접근법 6
제3절 논문 구성 7
제2장 관련 연구 분석 9
제1절 프로세스 모델 9
제2절 프로세스 모델 도출 방법론 13
제3장 타부 서치-유전자 프로세스 마이닝 알고리즘 제안 16
제1절 확률적 프로세스 트리의 정의 16
제2절 타부 서치-유전자 프로세스 마이닝 알고리즘 설계 23
제3절 타부 서치-유전자 프로세스 마이닝 알고리즘 순서도 38
제4장 실험 설계 및 성능 분석 40
제1절 실험 설계 40
제2절 실험 결과 분석 46
제5장 결 론 57
참고 문헌 59
영문 요약(Abstract) 62
