적합성 검사
Conformance checking
비즈니스 프로세스 적합성 검사(일명, 적합성 검사)는 프로세스 모델을 [1]동일한 프로세스의 이벤트 로그와 비교하는 프로세스 마이닝 기술의 집합입니다.이벤트 로그에 기록된 비즈니스 프로세스의 실제 실행이 모델에 부합하는지, 또는 그 반대인지를 확인하기 위해 사용됩니다.
예를 들어, 100만 유로 이상의 구매 주문에는 2개의 체크가 필요하다는 것을 나타내는 프로세스 모델이 있을 수 있습니다.이벤트 로그를 분석하면 이 규칙을 준수하는지 여부가 표시됩니다.
또 다른 예로는, 특정의 활동을 같은 사람이 실행해서는 안 된다고 하는 이른바 「4개의 눈」의 원칙을 체크하는 것이다.이러한 요건을 특정하는 모델을 사용해 이벤트 로그를 스캔 하는 것으로, 잠재적인 부정 행위를 검출할 수 있습니다.따라서 적합성 검사를 사용하여 편차를 검출, 발견 및 설명하고 이러한 [2]편차의 심각성을 측정할 수 있습니다.
개요
적합성 검사 기술은 프로세스 모델과 이벤트 로그를 입력으로 사용하여 프로세스 모델에 캡처된 동작과 이벤트 로그에 캡처된 동작 간의 차이 세트를 반환합니다.이러한 차이는 시각적으로(예: 프로세스 모델 위에 중첩됨) 또는 자연어 문장의 목록으로 텍스트로 표현될 수 있습니다(예: 활동 x는 로그에서 여러 번 실행되지만 모델에 따라 허용되지 않음).일부 기법은 공정 모형과 사건 로그가 서로 어느 정도 일치하는지 나타내는 정규화된 측도(0과 1)를 생성할 수도 있습니다.
부적합 해석은 모형의 목적에 따라 달라집니다.
- 모형이 서술적이어야 하는 경우 모형과 로그 간의 불일치는 현실을 더 잘 포착하기 위해 모형이 개선되어야 함을 나타냅니다.
- 모델이 규범적인 경우, 그러한 불일치는 두 가지 방법으로 해석될 수 있습니다. 즉, 바람직하지 않은 편차를 노출시킬 수 있습니다(즉, 적합성 검사는 프로세스의 더 나은 제어의 필요성을 나타냅니다).또는 바람직한 편차를 드러낼 수 있습니다(즉, 작업자는 고객에게 보다 나은 서비스를 제공하기 위해 또는 프로세스 모델에서 예측하지 못한 상황을 처리하기 위해 이탈할 수 있습니다).
기술
적합성 확인의 목적은 두 가지 유형의 불일치를 식별하는 것입니다.
- 로그 동작 불일치: 모델에서 허용하지 않는 동작이 로그에 관찰되었습니다.
- 추가 모델 동작: 모델에서는 허용되지만 로그에서는 관찰되지 않는 동작.
일치하지 않는 로그 동작을 검출하는 방법에는 크게 재생, 트레이스 정렬 및 동작 정렬의 세 가지 종류가 있습니다.
재생 [3]기술에서는 각 트레이스가 프로세스 모델에 대해 한 번에 한 이벤트씩 재생됩니다.재생 에러가 검출되면, 그 에러가 보고되고, 로컬 보정이 행해져 재생 순서를 재개합니다.예를 들어 프로세스 모델에서 작업을 건너뛰거나 무시하거나 로그에서 이벤트를 건너뛰거나 무시하는 것이 로컬 수정일 수 있습니다.
재생 방법의 일반적인 제한사항은 오류가 발생할 때마다 오류 복구가 로컬에서 수행된다는 것입니다.따라서 이러한 방법으로는 로그 동작 불량을 설명할 수 있는 최소 오류 수를 식별하지 못할 수 있습니다.이 제한은 트레이스 얼라인먼트 기술을 [4]통해 해결됩니다.후자의 기법은 로그 내의 각 트레이스에 대해 모델에 의해 해석할 수 있는 가장 가까운 대응하는 트레이스를 식별합니다.또한 트레이스 정렬 기법은 이들 두 트레이스 간의 분기점을 나타내는 정렬을 계산합니다.출력은 정렬된 트레이스 쌍의 세트입니다.각 쌍은 모델에 의해 생성된 대응하는 가장 가까운 트레이스와 함께 모델의 트레이스와 정확히 일치하지 않는 트레이스를 로그에 표시합니다.
트레이스 얼라인먼트테크놀로지는, 동시 태스크나 주기적인 동작(태스크의 반복)을 명시적으로 처리하지 않습니다.예를 들어 4개의 태스크가 프로세스 모델에서 고정된 순서(예: [A, B, C, D])로만 발생할 수 있지만 로그에서 동시에 발생할 수 있는 경우(즉, 임의의 순서로) 이러한 차이는 개별 트레이스 수준에서 관찰될 수 없기 때문에 트레이스 정렬로 직접 검출할 수 없습니다.
기타 동작을 식별하는 방법은 네거티브이벤트를 [5]기반으로 합니다.이러한 메서드는 로그의 모든 트레이스 또는 일부 트레이스에 가짜(부정) 이벤트를 삽입함으로써 로그의 트레이스를 확장합니다.이 이벤트가 로그 내의 임의의 프레픽스 앞에 나타나지 않으면 트레이스의 특정 프레픽스 뒤에 네거티브이벤트가 삽입됩니다.
예를 들어 프리픽스 AB 뒤에 이벤트C가 관찰되지 않으면 AB 뒤에 마이너스이벤트로 C를 삽입할 수 있습니다.그런 다음 음의 이벤트로 강화된 로그가 공정 모델에 대해 재생됩니다.프로세스 모델이 음의 이벤트를 재생할 수 있는 경우, 이는 프로세스 모델에서 캡처된 동작이 로그에 캡처되지 않았음을 의미합니다(음의 이벤트는 로그에서 관찰되지 않은 동작에 해당하기 때문입니다).
주목할 만한 알고리즘
풋프린트 행렬 비교
풋프린트 매트릭스는 이벤트 로그에 두 활동의 인과 관계를 표시한다. 예를 들어, 이벤트 로그에서 활동 a는 모든 추적에서 활동 b에 이어지지만 활동 b는 결코 [6]b에 이어지지 않는다.이러한 의존성에 대해 순서 관계 목록이 선언됩니다.
L을 모든 액티비티의 리스트A와 관련된 이벤트 로그로 합니다.a, b를 A의 두 가지 활동으로 합니다.
- 패턴(a, b)이 발생하는 L에 트레이스 「」가 존재하는 경우에만, 「bL」.
- a →L b if 및 b ᐳ a가 아닌 a ᐳLL b인 경우에만.
- a L# b는 a가L 아닌 경우에 한해, b는L a가 아닌 경우에 한해.
- aL b의L if 및 b의L if 및 b의 a에 한한다.
프로세스 모델의 경우 실행 시퀀스 위에 플레이아웃 기술을 사용하여 이러한 매트릭스를 도출할 수도 있다.따라서 풋프린트 행렬에 기초하여 사건 로그가 고려된 공정 모델을 준수할 경우 로그와 모델을 나타내는 두 풋프린트 행렬이 동일하다는 것을 알 수 있습니다. 즉, 모형에 기록된 행동(이 경우 인과 관계)이 사건 로그에 최소한 한 번 이상 나타납니다.
예: L을 {<a, b>, <a, c, d>} 및 L의 모델 M으로 합니다.이 두 행렬은 다음과 같습니다.
| a | b | c | d | |
|---|---|---|---|---|
| a | # | → | → | # |
| b | ← | # | # | # |
| c | ← | # | # | → |
| d | # | # | ← | # |
| a | b | c | d | |
|---|---|---|---|---|
| a | # | → | → | → |
| b | ← | # | # | # |
| c | ← | # | # | → |
| d | ← | # | ← | # |
모델 M의 풋프린트 매트릭스에서 패턴(a, d)이 발생할 수 있으므로 이벤트 로그와 비교하여 편차를 발생시키는 것을 알 수 있습니다.이벤트 로그와 모델 간의 적합성은 다음과 같이 계산됩니다.
이 예에서 적합성은 1- }}=입니다.
토큰 재생 기술
토큰 기반 재생은 4개의 카운터(생산된 토큰, 소비된 토큰, 누락된 토큰 및 나머지 토큰)를 사용하여 Petri-net [7]표기법으로 지정된 프로세스 모델을 기반으로 관찰 트레이스의 적합성을 계산하는 기술입니다.이들 4개의 카운터는 Petri net 상에서 트레이스가 재생되었을 때의 토큰 상태를 기록합니다.트랜지션에 의해 토큰이 생성되면 생성된 토큰은 1씩 증가합니다.트랜지션을 실행하기 위해 토큰을 소비하면 소비된 토큰은 1씩 증가합니다.트랜지션을 실행하기 위해 토큰이 누락되면 누락된 토큰은 1씩 증가합니다.나머지 토큰은 트레이스 완료 후 남은 토큰의 합계를 기록합니다.트레이스는 재생 중에 누락된 토큰이 없고 마지막에 남은 토큰이 없는 경우에만 프로세스 모델에 준거합니다.
이벤트 로그와 공정 모델 간의 적합성은 다음과 같이 계산됩니다.
2 ( - ) + ( - ){ \ {2} ( - \ { m } { } { \ } + { \ 2 ( } ) 。여기서 m의 토큰 번호는 없습니다.
얼라인먼트
토큰 재생 기법은 효율적이고 이해하기 쉽지만, 이 접근법은 Petri net 표기법에 맞게 설계되었으며 부적합한 경우에 대해 모델에 의해 생성된 적절한 경로를 고려하지 않습니다.얼라인먼트는 한계를 해결하기 위해 도입되었으며 매우 정확한 적합성 검사 기술로 간주되며 모든 프로세스 모델링 [8]표기법에 적용할 수 있습니다.알고리즘이 철저한 검색을 수행하여 관측된 추적과 공정 모델 간의 최적의 정렬을 찾는 것이 기본 개념입니다.따라서 트레이스와 비교하여 가장 관련성이 높은 모델을 찾을 수 있습니다.
레퍼런스
- ^ Wil van der Aalst (2013). Process Mining: Discovery, Conformance and Enhancement of Business Processes. Springer.
- ^ Carmona, Josep; Dongen, Boudewijn van; Solti, Andreas; Weidlich, Matthias (2018-11-11). Conformance Checking: Relating Processes and Models. Springer. ISBN 978-3-319-99414-7.
- ^ Rozinat, Anne; van der Aalst, Wil (2008). "Conformance Checking of Processes Based on Monitoring Real Behavior". Information Systems. 33 (1): 64–95. doi:10.1016/j.is.2007.07.001.
- ^ Adriansyah, Arya (2014). Aligning Observed and Modeled Behavior (PhD thesis). Eindhoven University of Technology.
- ^ vanden Broucke, Seppe K. L. M.; De Weerdt, Jochen; Vanthienen, Jan; Baesens, Bart (2014). "Determining Process Model Precision and Generalization with Weighted Artificial Negative Events". IEEE Transactions on Knowledge and Data Engineering. 26 (8): 1877–1889. doi:10.1109/TKDE.2013.130. S2CID 14365893.
- ^ van der Aalst, Wil (2016), van der Aalst, Wil (ed.), "Data Science in Action", Process Mining: Data Science in Action, Berlin, Heidelberg: Springer, pp. 3–23, doi:10.1007/978-3-662-49851-4_1, ISBN 978-3-662-49851-4, retrieved 2021-08-12
- ^ Rozinat, A.; van der Aalst, W.M.P. (March 2008). "Conformance checking of processes based on monitoring real behavior". Information Systems. 33 (1): 64–95. doi:10.1016/j.is.2007.07.001. ISSN 0306-4379.
- ^ van der Aalst, Wil; Adriansyah, Arya; van Dongen, Boudewijn (2012-01-30). "Replaying history on process models for conformance checking and performance analysis". WIREs Data Mining and Knowledge Discovery. 2 (2): 182–192. doi:10.1002/widm.1045. ISSN 1942-4787.
