Process discovery(Heuristic Mining)

Process discovery

* 목표 : 각 이벤트를 잘 설명하는 프로세스 모델 만들기
noise -> 프로세스 모델을 그룹화함으로써 해결

# Representation Bias
ex) 알파알고리즘
- 병렬(XOR, AND)설명, OR 설명하지 못함, 루프 처리 못함
- !! 빈도수를 고려하지 않고 activity의 순서만 고려 !!

-> DFG 마이닝 등장 (알파보다 더 단순한)

DFG mining
- trace내 작업의 선후 관계를 바탕으로 도출하는 모델
- 가장 기초적인 모델, xor과 and등 control-flow의 도출이 어렵다.
- 복잡한 모델을 임계치를 활용하여 단순화하게 만든다.


* 휴리스틱 마이닝
- 모델 생성시 이벤트의 빈도와 순서 고려
- 빈버하지 않은 행동은 모델에 포함시키지 않는다는 뜻
1) 이벤트 로그로부터 직접적인 선후 관계 테이블 도출
2) 종속성 관계값 계산 (알파 마이닝에는 없음)
- 종속성 관계값이란 a 다음 b가 올 경우의 수보다 b 다음 a가 올 경우의 수가 더 많으면 b 다음에 a가 오는 구나 라고 판단!
3) 임계치를 활용하여 종속성 그래프 도출 
- 종속성 척도(빈도수), 종속성 관계값(순서) 모두 활용
4) 종속성 그래프에 control-flow 추가
- AND, OR, XOR 조건 추가하기 위해 control-flow 활용
- Time window를 통해 activity의 input, output 파악

* 유전자 프로세스 마이닝
- 계산 지능 분야의 기법을 사용하는 진화론적 접근법
- 랜덤한 이벤트 로그 사용 -> 모델 도출 -> 모델과 로그의 정확도를 파악 -> 좋으면 도출, 안 좋으면 모델에 삽입, 추가 -> 반복
1) initialization
- 무작위적인 프로세스 모델 생성
2) selection
- 모델 개체와 로그를 비교하여 적합도 계산
3) reproduction
- 선택된 부모 개체들은 새로운 자식 개체 모델을 만드는 데 사용
- 크로스오버와 뮤테이션 사용

# Region-based Mining
- Tranwsition systems 도출 후 페트리넷 도출 형태로 수행
이때, place에 대응될 수 있는 region 찾는 것이 중요
* entering, leaving, non-crossing*
=> 각각의 activity는 항상 같은 특성을 가져야 함
=> 동일한 activity는 같은 특성 즉 entering이면 entering, ㅣeaving이면 leaving
- transition systems 내 제일 적은 reigons을 찾아서 페트리넷 place로 변환

- state을 정의하는 함수가 중요!
- 매우 복잡한 형태 -> state based regions을 통해 high-level 프로세스 모델 도출 가능

# Inductive Mining
- directly-follows graph와 process tree를 활용하는 방법
- 로그를 cut 하면서 하나의 activity로 구성된 sublog가 될 때까지 반복