Conformance Checking-based Concept Drift Detection in Process Mining

ESCOLA DE DOUTORAMENTO
INTERNACIONAL DA USC
Víc o José
Gallego Fon enla
Tese de dou o amen o
Con o mance Checking-based
Concep D i De ec ion in
P ocess Mining
San iago de Compos ela, 2023
P og ama de Dou o amen o en In es igación en Tecnoloxías da In o mación
TESE DE DOUTORAMENTO
CONFORMANCE CHECKING-BASED
CONCEPT DRIFT DETECTION IN PROCESS
MINING
Víc o José Gallego Fon enla
ESCOLA DE DOUTORAMENTO INTERNACIONAL DA UNIVERSIDADE DE SANTIAGO
DE COMPOSTELA
PROGRAMA DE DOUTORAMENTO EN INVESTIGACIÓN EN TECNOLOXÍAS DA
INFORMACIÓN
SANTIAGO DE COMPOSTELA
2023
Decla ación do au o /a da ese
D./Dna. Víc o José Gallego Fon enla
Tí ulo da ese: Con o mance Checking-based Concep D i De ec ion in P ocess Mining
P esen o a miña ese, seguindo o p ocedemen o axei ado ao Regulamen o, e decla o que:
1. A ese aba ca os esul ados da elabo ación do meu aballo.
2. De se o caso, na ese aise e e encia ás colabo acións que i o es e aballo.
3.
Con i mo que a ese non inco e en ningún ipo de plaxio dou os au o es nin de aballos
p esen ados po min pa a a ob ención dou os í ulos.
4.
A ese é a e sión de ini i a p esen ada pa a a súa de ensa e coincide a e sión imp esa
coa p esen ada en o ma o elec ónico.
E comp omé ome a p esen a o Comp omiso Documen al de Supe isión no caso de que o
o ixinal non es ea na Escola.
En San iago de Compos ela, Maio de 2023
Asdo. Víc o José Gallego Fon enla

Au o ización do di ec o / i o da ese
Con o mance Checking-based Concep D i De ec ion in P ocess Mining
D . Manuel Lama Penín
D . Juan Ca los Vidal Aguia
INFORMAN:
Que a p esen e ese co espóndese co aballo ealizado po D/Dna. Víc o José Gallego
Fon enla, baixo a nosa di ección/ i o ización, e au o izamos a súa p esen ación, conside ando
que eúne os equisi os esixidos no Regulamen o de Es udos de Dou o amen o da USC, e que
como di ec o es des a non inco e nas causas de abs ención es ablecidas na Lei 40/2015.
De aco do co indicado no Regulamen o de Es udos de Dou o amen o, decla amos amén
que a p esen e ese de dou o amen o é idónea pa a se de endida en base á modalidade de
Monog á ica con ep oducción de publicacións, nos que a pa icipación do/a dou o ando/a oi
decisi a pa a a súa elabo ación e as publicacións se axus an ao Plan de In es igación.
En San iago de Compos ela, Maio de 2023
Asdo. Manuel Lama Penín
Di ec o /a ese
Asdo. Juan Ca los Vidal Aguia
Di ec o /a ese
Á miña amilia
Cos que compa o sangue, e cos que non

Resumo
Se i e a ido máis empo, e ía esc i o unha
ca a máis cu a
— Blaise Pascal
Todos os días emp egamos p ocesos, moi as eces sen seque a deca a nos. Campos an
a iados como os sis emas de xes ión da in o mación [
1
], o seguimen o do endemen o de
a le as de al o ni el [
2
,
3
], a saúde [
4
,
5
,
6
,
7
] ou as me odoloxías de enxeña ía [
8
,
9
,
10
] usan
p ocesos pa a es u u a as súas ac i idades. Nun en o no cada ez máis globalizado, onde
os me cados se ab en a odo o mundo e onde oma decisións no momen o p eciso é c ucial,
é undamen al se conscien e de que a na u eza dos p ocesos é dinámica e, po an o, deben
e oluciona pa a adap a se ao seu en o no e alcanza os seus obxec i os sa is ac o iamen e.
A ampla a iedade de aplicacións e a g an can idade de da os xe ados pola execución dos
p ocesos ai esencial que al adap ación se aga de o ma au omá ica, pa a así pode dispo de
in o mación p ecisa, iable e e az en odo momen o.
En espos a á necesidade de analiza oda es a in o mación, apa ecen di e en es écnicas
que pe mi en modela , in e p e a e mello a o endemen o dos p ocesos. Todas es as écnicas
eúnense baixo o pa augas da Xes ión de P ocesos de Negocio (Business P ocess Managemen ,
BPM, en inglés). O BPM cons a de a ias ases que se desen ol en de o ma cíclica. Comeza
coa iden i icación do p oceso, da súa a qui ec u a e do seu endemen o, pa a con inua co
descub imen o do p oceso e a súa documen ación, seguido dunha e apa de análise na que se
ex aen debilidades e p oblemas que poidan a ec a ao endemen o do p oceso en xe al. T as es a
e apa de análise, e endo en con a a in o mación ob ida ace ca do endemen o, p océdese a un
Víc o José Gallego Fon enla
edeseño do p oceso que en a á mello a algunha pe spec i a no seu endemen o. Es e p oceso
edeseñado é pos e io men e implemen ado nun en o no supe isado e as súas execucións son
moni o izadas pa a ex ae in o mación ace ca de como o p oceso se es á a desen ol e e pode
mello alo ciclicamen e, epe indo cada unha das e apas indicadas.
Un dos p incipais desa íos á ho a de aplica as écnicas de BPM no mundo eal é que
a maio ía das a e as deben se ealizadas manualmen e po un expe o ou equi en un al o
ni el de in e acción do usua io. Pa a educi es a in e ención, xu de unha no a disciplina
denominada Mina ía de P ocesos (P ocess Mining, PM, en inglés), si uada a medio camiño
en e a Xes ión de P ocesos de Negocio e a In elixencia Emp esa ial, po unha banda, e a
Mina ía de Da os e a Ap endizaxe Au omá ica, po ou a banda, que en a au oma iza moi as
desas a e as co in de educi a in e ención humana ao mínimo. A a és da ex acción
au oma izada de in o mación dos exis os de execución dos p ocesos, a PM pe mi e in e p e a
o que es á ealmen e a acon ece nun p oceso, en luga do que se pensa que es á a acon ece ,
pe mi indo oma decisións en consecuencia. A maio ía das écnicas de PM basean o seu
uncionamen o na análise de exis os de e en os: conxun os de azas de execución compos as
de e en os que exis an a ealización de ce as a e as, cos seus empos de inicio e in, e ou os
a ibu os adicionais, como poden se os ecu sos emp egados ou o seu cus o, en e ou os.
As écnicas de PM poden se clasi icadas en es g andes g upos. Po unha banda, emos os
mé odos de descub imen o, nos que a pa i dun des es exis os de e en os buscan as elacións
de p ecedencia en e as ac i idades que compoñen o p oceso, pa a ex ae algunha clase de
modelo que de ina a súa es u u a. Es es modelos de p oceso poden se clasi icados en dúas
g andes amilias: os modelos impe a i os, que ecollen odas as es icións en e ac i idades
pa a de ini o luxo do p oceso, e os modelos decla a i os, que se basean en de ini eg as
decla a i as que es inxen a p ecedencia en e algunhas ac i idades. Algúns exemplos de
algo i mos de descub imen o do es ado da a e son Induc i e Mine ,Heu is ics Mine ,Spli
Mine ou P oDiGen. Po ou a banda, emos as écnicas de comp obación da con o midade,
que se enca gan de compa a modelos de p oceso on e aos exis os de e en os pa a a alia
can o do compo amen o sopo a o p imei o con espec o ao segundo. Des e xei o, cuan i ican
as disc epancias e desaliñamen os en e os modelos de p oceso e as súas execucións, pe mi indo
a alia en ce a medida a calidade dos modelos á ho a de ep esen a o compo amen o eal dos
p ocesos. Es as écnicas di ídense en es g andes amilias: as mé icas de axus e ou i ness,
que miden can o compo amen o p esen e no exis o de e en os es á sopo ado polo modelo,
a aliando can o se des ían as execucións eais do compo amen o espe ado; as mé icas de
x i
p ecisión/xene alización, que a alían a can idade de compo amen o que o modelo sopo a
on e ao obse ado nas execucións eais; e as mé icas de complexidade/simplicidade, que
a alían como de es u u almen e complexo é o modelo. En e cei o e úl imo luga emos as
a e as de mello a do p oceso, que eñen como obxec i o ealiza unha análise do uncionamen o
do p oceso e a ex ensión do modelo ou o seu e inamen o pa a mello a algunha das pe spec i as
des e. Den o des a amilia de écnicas podemos a opa algo i mos o ien ados a epa a o
modelo pa a que se adap e mello ao compo amen o obse ado nas execucións e algo i mos
o ien ados a es ende o coñecemen o do p oceso coa in de op imiza empos de execución,
p edici camiños ou pa óns c í icos ou de ec a e co ixi compo amen os anómalos.
Alén diso, as écnicas de PM poden se clasi icadas segundo a pe spec i a do p oceso
analizado. Así, exis en écnicas que analizan o p oceso desde o pun o de is a do luxo de
con ol, cen ándose na es u u a das ac i idades e nas es icións en e elas. Es as écnicas son
u ilizadas pa a descub i modelos ou e i ica que as ac i idades se ealicen na o de co ec a.
Tamén emos écnicas cen adas na pe spec i a o ganizacional, que analizan a asignación de
ecu sos e op imizan a súa u ilización, pa a, po exemplo eplani ica calenda ios de aballo.
Ou as écnicas abo dan a pe spec i a dos casos, analizando os a ibu os especí icos pa a
ex ae ca ac e ís icas comúns a un subconxun o de casos que cump an ce os equisi os como,
po exemplo, aqueles que apo en maio es bene icios. Po úl imo, emos écnicas cen adas na
pe spec i a empo al, que analizan os empos de execución e espe a pa a busca e asos na
execución de ce as a e as ou mo i os pa a execucións de la ga du ación. Es as pe spec i as
non son exclusi as, senón que poden combina se pa a p opo ciona unha isión máis ampla do
p oceso.
Como se mencionou an e io men e, os p ocesos es án cada ez máis p esen es na nosa
ida co iá. Is o, xun o cun mundo cada ez máis compe i i o, ai necesa io que os p ocesos
se adap en á ealidade dos usua ios de o ma lexible e áxil, pa a o cal os p ocesos deben se
su icien emen e lexibles como pa a pe mi i cambios no luxo das ac i idades. Es es cambios
poden se le ados a cabo de o ma conscien e polos xes o es do p oceso, pe o amén de i ados
de ci cuns ancias ex e nas sob e as que non se en con ol. É impo an e que es es cambios non
pasen desape cibidos pa a os xes o es, pos o que poden le a a aumen os de cus os ou educións
no endemen o do p oceso. Po is o, é undamen al con a con in o mación ac ualizada en odo
momen o que pe mi a adap a se ao p oceso en empo e o ma omando decisións da manei a
máis inmedia a posible pa a minimiza o seu impac o. Recen emen e, p opuxé onse di e sas
écnicas que pe mi en, dun xei o máis ou menos au oma izado, xes iona es es cambios nos
x ii
Víc o José Gallego Fon enla
p ocesos analizando a e olución dos casos de execución.
Es a necesidade de xes iona os cambios non é no a. O ixinalmen e, as écnicas de xes ión
de cambios nacen nos campos da ap endizaxe máquina e da moni o ización p edic i a, co
obxec i o de de ec a cando as a iables emp egadas pa a ealiza unha p edición cambian,
in alidando os esul ados. Es e ipo de écnicas non o on adop adas pola mina ía de p ocesos
a a ai uns anos; pola con a, a maio ía das ap oximacións de mina ía de p ocesos aínda hoxe
en día conside an os p ocesos como en idades es á icas que non e olucionan. A xes ión dos
cambios componse de es e apas ben di e enciadas: po unha banda, a de ección, enca gada
de indica se un cambio exis e ou non; po ou a banda, a localización eca ac e ización,
enca gadas de analiza o cando, o onde e o como do cambio; e, po úl imo, a análise, enca gada
de explica o po que do cambio. Nes a ese limi a émonos a p opos as que esol en a ase de
de ección e de localización empo al.
Exis en di e sas o mas de clasi ica os algo i mos de xes ión de cambios. Dependendo
do uso que agan dos da os, podemos a opa uns algo i mos que emp egan un único da o
en cada ins an e e ou os que an uso dunha mos a de alo es, coñecida como en á. Os
p imei os eñen a des an axe de le a máis empo pa a de ec a un cambio, men es que os
segundos dependen en g an medida da selección dun amaño de en á adecuado pa a cap u a
odo o compo amen o. Á súa ez, es as en ás poden e un amaño ixo ou a iable que se
axus a au oma icamen e ao p oblema en empo de execución, educindo así a complexidade
do p oblema de selecciona un amaño óp imo. Dou a banda, en unción do mecanismo
emp egado pa a ponde a o alo da in o mación segundo a súa an igüidade, a opa emos
algo i mos con mecanismos de esquecemen o g adual ou ab up o. Os p imei os u ilizan máis
da os pa a a a aliación dos cambios, dando maio impo ancia aos máis ecen es pe o sen
desca a os an igos, o que pode e asa a de ección dos cambios. Os segundos, en cambio,
emp egan só un subconxun o dos alo es his ó icos pa a ealiza a de ección. Es es úl imos
poden di idi se, a súa ez, en algo i mos baseados en mos as p obabilís icas e algo i mos
baseados nunha en á empo al , que soamen e conside an os alo es máis ecen es, dun xei o
simila ao dunha cola de amaño limi ado. Todos os algo i mos p esen ados nes a ese se basean
no uso dunha en á empo al de amaño ixo ou adap able.
Finalmen e, os cambios poden se clasi icados amén segundo a súa dis ibución empo al.
Te emos cambios ins an áneos cando un modelo subs i úa ao ou o ab up amen e, sen pasos
in e medios. Po ou a banda, e emos cambios g aduais cando os dous modelos, o p e io ao
cambio e o pos e io , con i en du an e un pe íodo de empo, podendo a opa execucións de
x iii
ambos du an e di o pe íodo. Amais, os cambios son inc emen ábeis cando podemos iden i ica
modelos in e medios a a que o no o p oceso se es abiliza; e eco en es cando se epi en con
ce a pe iodicidade. Es a clasi icación non é excluin e máis que pa a os dous p imei os ipos:
un cambio debe á se semp e ins an áneo ou g adual, pe o pode, á súa ez, o ma pa e dun
cambio inc emen ábel se se dá nun con ex o no que o modelo inal non se chega a es abiliza .
Ademais, odos os cambios (ins an áneos, g aduais ou inc emen ábeis) poden cons i uí un
cambio eco en e se o compo amen o se ai al e nando ciclicamen e con ce a pe iodicidade.
Po úl imo, pe o non menos impo an e, debemos di e encia un cambio dunha execución
anómala, que se debe a unha al e ación espu ia do p oceso que non pe i e no empo.
Nos úl imos empos, di e sos au o es p opuxe on mé odos pa a a de ección de cambios
nos p ocesos, seguindo di e en es ap oximacións, odas coas súas an axes e incon enien es.
Así, podemos a opa p opos as que basean o seu uncionamen o en aliña un modelo de
p oceso coas execucións eais [
11
,
12
,
13
]. Dou a banda, emos p opos as baseadas en g a os,
como as p esen adas en [
14
,
15
], que ep esen an o p oceso como un g a o e analizan a súa
e olución ao longo do empo. Tamén podemos a opa p opos as baseadas no uso de écnicas de
ag upamen o e no es udo da e olución de di os g upos ao longo do empo, como as p esen adas
en [
16
,
17
,
18
,
19
]. Non obs an e, ningunha des as p opos as consegue de ec a odos os
posibles pa óns de cambio cunha al a iabilidade e man endo uns e a dos pequenos.
Ago a ben, se se analiza o que oco e nas mé icas de con o midade cando en luga un
cambio no es u u a dun p oceso, pódese comp oba que cando unha ac i idade desapa ece
do modelo, a can idade de compo amen o que sopo a o modelo ese educida; sen emba go,
cando unha no a ac i idade ou elación en e ac i idades apa ece no modelo, o compo amen o
sopo ado polo modelo é supe io ao que se obse a nas azas. Do mesmo xei o, pode
comp oba se que cando apa ecen ou se eliminan ac i idades nas azas, o compo amen o que
pode explica o modelo ipicamen e cambia. Con es as conside acións, podemos o mula a
hipó ese sob e a que se desen ol e es a ese: a alia a e olución das mé icas de con o midade
ao longo da ida dun p oceso pode pe mi i nos de ec a cambios ins an áneos e g aduais
de manei a iable e ápida. En base a es a hipó ese, p opoñemos es mé odos pa a a de ección
de cambios ins an áneos, g aduais e en con o nas con uído.
En p imei o luga , p esén ase C2D2, un algo i mo cen ado na de ección de cambios
ins an áneos con al a iabilidade e baixos e asos. Pa a is o, o algo i mo de ine unha en á
empo al de e e encia e descob e un modelo de p oceso a pa i dos e en os con idos nela,
pa a, a con inuación, pasa a ixia a e olución dos alo es das mé icas de axus e e p ecisión
xix

Víc o José Gallego Fon enla
das sucesi as en ás median e unha eg esión linea simple. A idea as des e algo i mo é
que, en caso de non p esen a se cambios, os alo es das mé icas debe ían man e se es ables
a edo dun alo , ou o que é o mesmo, a penden e da eg esión calculada sob e os alo es
his ó icos das mé icas debe á se ce o, sen impo a ealmen e o alo conc e o que adqui an
di as mé icas. Pa a o alece es a idea, demos amos que a combinación de mé icas de axus e
e p ecisión habili a a de ección de cambios na es u u a dos p ocesos. Tamén demos amos que,
po con a, emp ega unicamen e un ipo de mé ica limi a os pa óns de cambio de ec ables.
Amais, p opoñemos un mé odo pa a calcula o amaño óp imo da en á de de ección de o ma
au omá ica que es á baseado nun p oceso i e a i o no que se descob en es modelos de p oceso
a pa i de es en ás consecu i as dun amaño de e minado e se compa an os compo amen os
cap u ados po eles. No caso de que sexan iguais, inc emén ase o amaño da en á a a que
alomenos un dos es modelos p esen e un compo amen o di e en e aos ou os dous.
Un dos p oblemas do mé odo en dado pola ele ada complexidade de cómpu o das mé icas
de con o midade, que se deben calcula múl iples eces, unha pa a cada en á p ocesada. Pa a
emedia es e p oblema, p opoñemos dúas es imacións do cambio nas mé icas que, se ben
non debe an se emp egadas pa a medi alo es absolu os pe se, son ú iles pa a a alia como
es as e olucionan co empo. Es as es imacións do cambio p esen an un cus o de cómpu o moi
in e io ao das mé icas p opos as no es ado do a e, p opo cionando mello es esul ados á ho a
de de ec a os cambios. As es imacións p opos as son: (i) pa a o axus e, a po cen axe de azas
que se poden ol e a execu a sa is ac o iamen e de p incipio a in no modelo; e (ii) pa a a
p ecisión, unha mé ica dos pa es de ac i idades elacionadas en e si no modelo on e aos
pa es de ac i idades sucesi as obse adas nas azas, o que nos da unha idea da po cen axe de
camiños p esen es no modelo que se obse an alomenos unha ez nas execucións eais.
C2D2 oi alidado emp egando
204
exis os de e en os sin é icos xe ados a pa i de
3
modelos de p oceso eais ex aídos da li e a u a. Os esul ados da de ección o on compa ados
cos ob idos polos es mello es algo i mos do es ado do a e, emp egando mé icas habi uais
pa a es e ipo de p oblemas, especi icamen e a iabilidade, que a alía o nume o de de eccións
co ec as e inco ec as, e o e a do, que mide can o a da o algo i mo en de ec a o cambio unha
ez que es e acon ece. O esul ado des a alidación amosa que C2D2 ob én mello es esul ados
en e mos de iabilidade, men es que man én uns alo es de e a do na de ección moi baixos.
Es es esul ados amén o on a aliados emp egando es s es a ís icos, alidando as conclusións
an e io es en ódolos casos.
En segundo luga , p esen amos CRIER, que pa e das p emisas emp egadas como base na
xx
de inición de C2D2, é dici , o uso de mé icas de axus e e p ecisión e a súa moni o ización
median e eg esións lineais pa a a de ección de cambios, pe o es ende a ap oximación pa a
habili a a de ección de cambios g aduais en luga de limi a se aos cambios ins an áneos.
O p incipio undamen al do uncionamen o de CRIER é que odo cambio g adual ai es a
delimi ado po dúas de eccións eñen como pa icula idade que o compo amen o que en e
eses dous pun os pode se de inido como unha combinación dos compo amen os amosados
an es e despois de di o cambio. Pa a undamen a o desen ol emen o do algo i mo p obamos
o malmen e que es a idea é co ec a e que, ademais, o p imei o dos cambios ai se debido
a unha caída no axus e do modelo, debido á inclusión de no o compo amen o que non o a
obse ado an es e que, polo an o, non o maba pa e do compo amen o cap u ado polo modelo
descube o a pa i da en á de e e encia, men es que o segundo se á debido a unha caída na
p ecisión, ao desapa ece o compo amen o o ixinal do p oceso a pa i dun ins an e conc e o.
Así, pa a comp oba que es e compo amen o in e medio sexa unha combinación dos ou os
dous, p opoñemos un mé odo que comp oba a exis encia de compo amen o p o in e dos
modelos p e io e pos e io ao cambio, e que odas as execucións du an e o in e alo de cambio
pe enzan a un deles. Es a ap oximación ai que non sexa necesa io ealiza ningún axus e a
unha se ie de dis ibucións de p obabilidade de e minadas, o que apo a maio lexibilidade
ao algo i mo ao non impoñe ningunha es ición ao ipo de combinación p esen e du an e o
cambio g adual.
CRIER oi a aliado emp egando
120
exis os de e en os sin é icos xe ados a pa i dun
p oceso eal ex aído do es ado do a e e 12 dis ibucións de p obabilidade di e en es pa a os
segmen os de cambio. Os esul ados ob idos o on compa ados cos das p incipais p opos as
do es ado do a e emp egando as mesmas mé icas de iabilidade e e a do que o on usadas
pa a a alia C2D2. Ademais, p oponse unha no a mé ica pa a a alia es e ipo de algo i mos,
á que denominamos cobe u a do cambio, que cuan i ica a po cen axe do segmen o de
cambio de ec ado como al po pa e do algo i mo. No amen e, os esul ados o on a aliados
emp egando es s es a ís icos, amosando cla amen e que CRIER ob én os mello es esul ados
nas es mé icas.
Finalmen e, omamos ódalas leccións ap endidas no o desen ol emen o de C2D2 eCRIER
e p opoñemos un no o algo i mo, R-CRIER, que habili a a de ección de cambios ins an áneos e
g aduais en con o nas que p esen en execucións anómalas que poden da luga a alsos posi i os
( amén denominadas uído). A maio di icul ade de de ec a cambios en p ocesos suscep ibles
de amosa uído dáse á ho a de di e encia en e un cambio eal e unha execución anómala
xxi
Víc o José Gallego Fon enla
cuxo compo amen o non pe du a no empo. Pa a le a a cabo es a de ección seguimos coas
p emisas ecollidas p e iamen e (a a aliación das mé icas de axus e e p ecisión) pe o, nes e
caso, modi icamos a e apa de moni o ización. Se ben seguimos a emp ega eg esións lineais
simples, demos amos o malmen e que, no caso das anomalías, a penden e unicamen e cae á
du an e un núme o de e minado de medicións consecu i as, men es que no caso dun cambio
eal o inc emen o na caída da penden e p olóngase du an e moi o máis empo. Unha ez
p obada es a a i mación, p opoñemos unha implemen ación que habili a a de ección obus a de
cambios, an o ins an áneos como g aduais, en con o nas suscep ibles de p esen a uído.
Un dos p incipais e os á ho a de de ec a os cambios nes e ipo de con o nas pasa po
iden i ica a can idade de anomalías p esen es nas execucións. Pa a esol e es e p oblema
habi ualmen e ecó ese ao coñecemen o dun expe o no domino, que indica a p obabilidade
de anomalías de xei o manual as ealiza algún ipo de análise do p oceso. Nes e caso,
p opoñemos un mé odo au omá ico de ap oximación á es imación da po cen axe uído que
habili a a súa de ección en con o nas onde non sexa posible con a coa colabo ación de expe os.
Pa a es a es imación baseámonos en mé odos ben coñecidos na ap endizaxe au omá ica, que
ponde an en ce a medida o bene icio de engadi máis in o mación a un modelo on e ao
cus o que is o en asociado; endo en con a que o compo amen o anómalo debe a se pouco
ecuen e, men es que o compo amen o espe ado do p oceso debe a es a moi o máis p esen e
no exis o. Especi icamen e, o mé odo a alía a po cen axe de compo amen o obse ado no
exis o de execución que é cap u ado polo modelo a medida que es e se ai es endendo, de
o ma que o que se busca é o pun o óp imo a pa i do cal engadi máis compo amen o ao
modelo non ai que se sopo en moi as máis azas.
R-CRIER oi a aliado emp egando un o al de
528
exis os sin é icos xe ados a pa i dun
modelo de p oceso eal ex aído da li e a u a, con po cen axes de uído en e
0%
e
25%
, e con
cambios an o ins an áneos como g aduais. Os esul ados ob idos o on compa ados cos das
p incipais ap oximacións do es ado do a e emp egando as mesmas mé icas que pa a C2D2 e
CRIER. Nes e caso, R-CRIER p esen a os mello es esul ados en e mos de iabilidade, á ez
que man én uns alo es de e a do bas an e baixos. Pola con a, a ap oximación que ob én
mello es alo es de e a do aino a cos a de sac i ica en g an medida a iabilidade, polo que se
ol e inope an e pa a con o nas eais.
Co desen ol emen o des as es ap oximacións podemos da po sa is ei os os obxec i os
da ese de dou o amen o, p opo cionado como esul ado inal es ap oximacións que mello an
as p opos as do es ado do a e na de ección de cambios ins an áneos e g aduais no luxo de
xxii
con ol dos p ocesos, e alice zados po demos acións o mais que alidan as hipó eses de
pa ida.
xxiii
Víc o José Gallego Fon enla
i e a i e p ocess in which h ee p ocess models a e disco e ed om h ee consecu i e windows
o a gi en size, and he beha io cap u ed by hese models is compa ed. I he h ee models
cap u e he same beha iou , he window size is inc eased, un il a leas one o he h ee models
exhibi s di e en beha io om he o he wo.
One o he main issues wi h C2D2 is he high compu a ional complexi y de i ed om he
con o mance me ics, which need o be calcula ed mul iple imes o each p ocessed window.
To add ess his p oblem, we p opose wo es ima ions o he change in me ics. Al hough
hese es ima ions should no be used o measu e absolu e alues pe se, hey a e use ul o
e alua ing how he me ics e ol e o e ime. These change es ima ions ha e a much lowe
compu a ional cos compa ed o he me ics p oposed in he s a e o he a , esul ing in be e
esul s when de ec ing changes. The p oposed es ima ions a e as ollows: (i) Fo i ness, he
pe cen age o aces ha can be success ully eplayed om s a o inish in he model. (ii) Fo
p ecision, a me ic ha compa es he se o pai s o eachable ac i i ies om he model o pai s
o successi e ac i i ies obse ed in he aces. This gi es us an idea o he pe cen age o pa hs
p esen in he model ha a e obse ed a leas once in he ac ual execu ions.
C2D2 has been alida ed using
204
syn he ic e en logs gene a ed om
3
eal p ocess
models ex ac ed om he li e a u e. The de ec ion esul s ha e been compa ed wi h he
esul s ob ained by he op
3
s a e o he a algo i hms using common me ics o his ype o
p oblem. Speci ically, accu acy, which e alua es he numbe o co ec and inco ec de ec ions,
and delay, which measu es how long he algo i hm akes o de ec he change once i occu s.
The alida ion esul s show ha C2D2 achie es be e esul s in e ms o eliabili y while
main aining e y low de ec ion delay alues. These esul s we e also e alua ed using s a is ical
es s, which alida e he p e ious conclusions in all cases.
In he second place, we p esen CRIER, which builds upon he p emises used as he basis
o de ining C2D2, namely he use o i ness and p ecision me ics and hei moni o ing h ough
linea eg essions o change de ec ion, bu ex ends he app oach o enable he de ec ion o
g adual changes ins ead o being limi ed o sudden d i s. The undamen al p inciple behind
CRIER ope a ion is ha e e y g adual change will be delimi ed by wo de ec ions ha ha e
he pa icula i y ha he beha io be ween hese wo poin s can be de ined as a combina ion
o he beha io s exhibi ed be o e and a e ha change. To subs an ia e he de elopmen o
he algo i hm, we o mally p o e ha his idea is co ec and ha , u he mo e, he i s o he
changes will be due o a d op in model i ness, esul ing om he inclusion o new beha io
ha has no been obse ed be o e and he e o e was no pa o he beha io cap u ed by he
xxx

model disco e ed om he e e ence window, while he second change will be due o a d op in
p ecision, as he o iginal beha io o he p ocess disappea s om a speci ic momen onwa ds.
Thus, o e i y ha his in e media e beha io is a combina ion o he o he wo, we p opose
a me hod ha checks o he exis ence o beha io o igina ing om he models be o e and a e
he change and ensu es ha all execu ions du ing he in e al o change belong o one o hem.
This app oach elimina es he need o pe o m any i ing o speci ic p obabili y dis ibu ions,
which p o ides g ea e lexibili y o he algo i hm by no imposing any es ic ions on he ype
o combina ion p esen du ing he g adual change.
In addi ion, CRIER has been e alua ed using
120
syn he ic e en logs gene a ed om a
eal p ocess ex ac ed om he s a e o he a , as well as
12
di e en p obabili y dis ibu ions
o he change segmen s. The ob ained esul s we e compa ed wi h hose o he main s a e
o he a app oaches using he same accu acy and delay me ics ha we e used o e alua e
C2D2. Fu he mo e, a new me ic called change co e age is p oposed o e alua e his ype
o algo i hm, which quan i ies he pe cen age o he change segmen de ec ed as such by he
algo i hm. Once again, he esul s we e e alua ed using s a is ical es s, clea ly demons a ing
ha CRIER achie es he bes esul s in all h ee me ics.
The las algo i hm we p opose is called R-CRIER, and enables he de ec ion o bo h sudden
and g adual changes in en i onmen s ha may con ain anomalous execu ions leading o alse
posi i es (also known as noise). The main challenge in de ec ing changes in p ocesses p one o
noise is dis inguishing be ween a eal change and an anomalous execu ion o ou lie whose
beha io does no pe sis o e ime. To add ess his de ec ion challenge, we build upon he
p emises es ablished ea lie (namely, he e alua ion o i ness and p ecision me ics) bu modi y
he moni o ing s age. While we con inue o employ simple linea eg essions, we o mally
demons a e ha in he case o anomalies, he slope will only decline o a ce ain numbe o
consecu i e measu emen s, whe eas in he case o a eal change, he slope’s decline will pe sis
o a much longe pe iod. Ha ing alida ed his claim, we p opose an implemen a ion ha
enables obus de ec ion o bo h sudden and g adual changes in en i onmen s p one o noise.
Indeed, one o he main challenges in de ec ing changes in such en i onmen s lies
in iden i ying he le el o anomalies p esen in he execu ions. Typically, his challenge is
add essed by le e aging he knowledge o a domain expe who manually assesses he likelihood
o anomalies a e analyzing he p ocess. Howe e , in his case, we p opose an au oma ic
me hod o es ima ing he pe cen age o noise, enabling i s de ec ion in en i onmen s whe e
expe collabo a ion is no possible. To es ima e he noise pe cen age, we ely on well-known
xxxi
Víc o José Gallego Fon enla
me hods in machine lea ning ha weigh he bene i o adding mo e in o ma ion o a model
agains he associa ed cos Gi en ha anomalous beha io should be in equen while he
expec ed beha io o he p ocess should be p e alen in he execu ion log, he me hod e alua es
he pe cen age o obse ed beha io cap u ed by he model as i is ex ended. The goal is o ind
he op imal poin a which adding mo e beha io o he model does no signi ican ly inc ease
he numbe o suppo ed aces.
R-CRIER was e alua ed using a o al o
528
syn he ic eco ds gene a ed om a eal p ocess
model ex ac ed om he li e a u e. The logs had noise pe cen ages anging om
0%
o
25%
and included bo h ins an and g adual changes. The esul s we e compa ed wi h hose o leading
s a e o he a app oaches using he same e alua ion me ics as C2D2 and CRIER. In his case,
R-CRIER achie ed he bes esul s in e ms o accu acy while main aining ela i ely low delay
alues. On he o he hand, he app oach ha achie ed be e delay alues did so a he expense
o signi ican ly sac i icing eliabili y, ende ing i ine ec i e o eal-wo ld en i onmen s.
Wi h he de elopmen o hese h ee app oaches, we can conside he objec i es o he Ph.D.
disse a ion ul illed, esul ing in h ee app oaches ha imp o e he s a e o he a p oposals in
he de ec ion o sudden and g adual changes in he p ocess con ol low. These app oaches a e
suppo ed by o mal demons a ions ha alida e he ini ial hypo heses.
xxxii
Con en s
1 In oduc ion 1
1.1 Mo i a ion.................................... 1
1.2 Hypo hesis and objec i es . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Resea ch Con ibu ions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4 O he Con ibu ions............................... 19
1.5 Me hodology .................................. 20
1.6 Documen s uc u e............................... 21
2 Rela ed wo k 23
2.1 Suddend i de ec ion.............................. 24
2.2 G adual d i de ec ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3 Conclusions................................... 34
3 Sudden d i de ec ion 35
3.1 Sudden d i de ec ion using con o mance me ics . . . . . . . . . . . . . . . 37
3.2 Algo i hm.................................... 38
3.3 Expe imen a ion................................. 45
3.4 Conclusions................................... 56
4 G adual d i de ec ion 57
4.1 G adual d i de ec ion using con o mance me ics . . . . . . . . . . . . . . 58
4.2 Algo i hm.................................... 61
4.3 Expe imen a ion................................. 66
4.4 Conclusions................................... 75
Con en s
5 Robus d i de ec ion 77
5.1 Robus d i de ec ion using con o mance me ics . . . . . . . . . . . . . . . 78
5.2 Algo i hm.................................... 80
5.3 Expe imen a ion................................. 86
5.4 Conclusions................................... 94
6 Conclusions 95
Appendix A Sudden d i de ec ion: supplemen a y expe imen s 101
A.1 Cen al enous ca he e p ocess . . . . . . . . . . . . . . . . . . . . . . . . . 101
A.2 Hospi al eme gency wa d p ocess . . . . . . . . . . . . . . . . . . . . . . . 104
Appendix B G adual d i de ec ion: supplemen a y expe imen s 109
B.1 Linea logs ................................... 109
B.2 Gaussianlogs.................................. 111
B.3 Exponen iallogs ................................ 112
B.4 Cons an logs .................................. 114
Appendix C Robus d i de ec ion: supplemen a y expe imen s 117
C.1 Suddenchanges................................. 117
C.2 G adualchanges................................. 136
Lis o publica ions included in his Ph.D. disse a ion 143
Bibliog aphy 145
Lis o Figu es 155
Lis o Tables 157
xxx

CHAPTER 1
INTRODUCTION
He ha climbs a ladde mus begin a he i s
ound
— Wal e Sco
1.1 Mo i a ion
P ocesses a e p esen all a ound us. F om IT se ice managemen [
1
] o pe o mance in
high-le el a hle es [
2
,
3
], heal hca e [
4
,
5
,
6
,
7
] o so wa e enginee ing [
8
,
9
,
10
], o ganiza ions
all a ound he globe use p ocesses o shape hei ope a ions. Wi h such a b oad a ay o
scena ios, i has become c i ical o be awa e ha he na u e o p ocesses is dynamic, so hey
mus e ol e and adap o he en i onmen quickly o p ope ly se e hei in ended pu pose.
The wide a ie y o applica ions o p ocesses and he la ge amoun o da a gene a ed by hei
execu ion makes i essen ial ha such adap a ion is au oma ically done as much as possible, so
ha any p ocess owne has accu a e, eliable and u h ul in o ma ion when making decisions
abou he way he o ganisa ion ope a es.
In esponse o he need o analysing all his in o ma ion, o e he las decades, di e en ools,
echniques and mechanisms ha e eme ged o suppo o ganisa ions in modelling, in e p e ing,
and imp o ing hei p ocesses. All hese echniques a e b ough oge he unde he umb ella o
Víc o José Gallego Fon enla
BPM
Li ecycle
I
d
e
n
i
i
c
a
i
o
n
D
i
s
c
o
e
y
A
n
a
l
y
s
i
s
R
e
d
e
s
i
g
n
I
m
p
l
e
m
e
n
a
i
o
n
M
o
n
i
o
i
n
g
P ocess a chi ec u e
As-is p ocess model
Insigh s on weaknesses and hei impac
To-be p ocess model
Execu able p ocess model
Con o mance and pe o mance insigh s
Figu e 1.1: Business P ocess Managemen amewo k li ecycle (adap ed om [20]).
he Business P ocess Managemen (BPM) pa adigm, which seeks o consolida e and in eg a e
all hese p oposals wi h he aim o being in e ope able. To add ess he goal o p o iding hin s
on how o imp o e p ocesses, BPM de ines a amewo k, depic ed in Figu e 1.1, in which
p ocesses go h ough se e al phases: iden i ica ion o he p ocess, disco e y o a model as
close as possible o how i is execu ed, analysis o weaknesses and po en ial op imisa ions,
edesign o he p ocess, implemen a ion and deploymen on i s p oduc ion en i onmen , and
moni o ing and e i ica ion o i s con o mance wi h he espec o he designed one [20].
The mos challenging ac o when applying BPM echniques in he eal wo ld is ha
he majo i y o he asks ha e o be pe o med manually, o equi e a high le el o use
in e ac ion — o example, when designing a p ocess model o when iden i ying oppo uni ies
o imp o emen —, which makes i di icul o deal wi h p ocesses in ol ing a la ge numbe o
execu ions. In an a emp o add ess hese issues, a new esea ch discipline —called P ocess
Mining (PM) [
21
]— has eme ged wi h he aim o au oma ing and imp o ing many o he abo e
p oblems h ough he use o echniques ha educe he in e en ion equi ed by he p ocess
owne s. PM s ands in be ween BPM and Business In elligence, on he one hand, and Da a
Mining and Machine Lea ning, on he o he one, ac ing as a b idge be ween hese wo wo lds.
The p ocess mining amewo k, depic ed in Figu e 1.2, elies on he ex ac ion o aluable
in o ma ion om e en logs, eco ding he execu ion o he ac i i ies ha a e pa o a p ocess
in he o m o e en s and aces. F om he analysis o hese logs, PM echniques allow us
o in e p e wha is ac ually happening in a p ocess, a he han wha we hink is happening,
enabling us o ake decisions acco dingly [21].
2
Chap e 1. In oduc ion
Bussiness P ocesses In o ma ion Sys ems
E en Logs
P ocess Models
suppo s
p oduce
P ocess Mining
disco e y
con o mance
enhancemen
models
analyzes
implemen s/con igu e
analyzes/speci ies
Figu e 1.2: P ocess mining amewo k (adap ed om [21]).
De ini ion 1: E en
Gi en he se o ac i i ies
A
ha con o m a p ocess, an e en
𝜀
can be de ined as he
execu ion o an ac i i y
𝛼∈A
a a gi en ins an
𝑡
in he con ex o a p ocess ins ance
𝑐
. The ac i i y name
𝜀.𝑎
, he imes amp
𝜀.𝑡
and he p ocess ins ance iden i ie —o en
e e ed o as case—
𝜀.𝑐
a e he only manda o y a ibu es o an e en , which can
also ha e o he gene ic a ibu es, such as he esou ces ha pe o m he ac i i ies, o
domain-speci ic a ibu es, unde s ood as a iables whose alues a e modi ied in he
ac i i y execu ion.
De ini ion 2: T ace
Gi en he ull se o e en s
E
eco ded om he execu ion o a p ocess, a ace
𝜏
can be
de ined as he o de ed sequence o he e en s belonging o he same p ocess ins ance
𝜏.𝑐
,
whe e he o de is de ined by he e en s imes amp.
3
Víc o José Gallego Fon enla
Da a
Managemen
Mul iple
Examples
(Windows)
Fixed
Size
Va iable
Size
Single
Example
Figu e 1.4:
Taxonomy o concep d i algo i hms based on hei memo y managemen : da a
managemen -d i en classi ica ion (adap ed om [46]).
Fo ge ing
Mechanism
G adual
Fo ge ing
Ab up
Fo ge ing
Tempo al
Sequence
(window)
Fixed
Size
Va iable
Size
Sampling
(selec ion)
Figu e 1.5:
Taxonomy o concep d i algo i hms based on hei memo y managemen : o ge ing
mechanism-d i en classi ica ion (adap ed om [46]).
he ime pe o mance o change de ec ion, bu will wo sen he pe o mance in pe iods
wi hou changes; while a window size oo la ge will ake longe o de ec changes bu
ha e be e pe o mance in pe iods wi hou changes. To sol e his p oblem, windows can
ha e a ixed size o a a iable size ha is au oma ically adap ed du ing he execu ion.
2.
Acco ding o he o ge ing mechanism employed (Figu e 1.5), algo i hms can be classi ied
in o g adual o ge ing and ab up o ge ing. The o me conside s all o he examples
and assigns o each one a weigh , gi ing a g ea e weigh o he mos ecen da a and
10

Chap e 1. In oduc ion
𝜏0𝜏1𝜏2𝜏3𝜏4𝜏5𝜏6𝜏7
𝜔5
𝜔6
𝜔7
Figu e 1.6: Example o he sliding window beha iou .
educing he weigh as he da a becomes olde . The la e conside a window o a
es ic ed size and, as newe obse a ions a e ecei ed, o ge s he olde examples. These
app oaches can also be classi ied in o wo sub ypes: hose based on a sampling app oach,
in which each ime a new obse a ion is ecei ed a p obabili y o belonging o he sample
is assigned o i ; and hose ha ollow a i s -in- i s -ou (FIFO) s a egy, o ge ing he
oldes obse a ions each ime a new obse a ion is ecei ed. The la e a e called sliding
windows, and hei size can be de ined on he basis o a cons an numbe o obse a ions
o on he basis o a empo al du a ion, which will cause he window size o change
acco ding o he new obse a ions a e.
All he me hods p esen ed in his Ph.D. disse a ion use a window wi h an ab up o ge ing
mechanism (sliding window).
De ini ion 7: Sliding window
The sliding window o size
𝑛
o e a log
𝐿
is de ined as
𝜔𝑖(𝐿, 𝑛)=⟨𝜏𝑖−𝑛+1, . . . , 𝜏𝑖⟩
, whe e
i s con en is con o med by he mos ecen
𝑛
aces p esen in he log a ins an
𝑖
. When
a new ace is ead om he log, he window slides one posi ion, so he oldes ace is
o go en and he new ace is inco po a ed. This way, he algo i hm only akes in o
accoun he mos ecen in o ma ion o de ec ing changes.
Figu e 1.6 shows an example log and he beha iou o a six-sized sliding window o e i . A
ins an
𝑡5
, he sliding window
𝜔5
con ains aces
𝜏0
o
𝜏5
. A ins an
𝑡6
a new ace is ead om
he log, so he oldes ace in he window (
𝜏0
) is o go en and he new ace (
𝜏6
) is added o he
window. This beha iou con inues un il he ull log has been ead.
In addi ion o his classi ica ion, concep d i algo i hms can also be g ouped acco ding
o how da ase s a e p ocessed: (i) o line algo i hms, which pe o m he analysis once all he
da a a e a ailable, allowing a pos -mo em analysis o he e olu ion o he obse a ions; and
11
Víc o José Gallego Fon enla
𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1
𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2
Time
(a) Sudden d i
𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1
𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2
Time
(b) G adual d i
𝑀1𝑀1𝑀1𝑀1𝑀1𝑀2𝑀3𝑀4𝑀5𝑀6𝑀7𝑀8𝑀8𝑀8𝑀8𝑀8
Time
(c) Inc emen al d i
𝑀1𝑀1𝑀1𝑀1
𝑀2𝑀2𝑀2𝑀2
𝑀1𝑀1𝑀1𝑀1
𝑀2𝑀2𝑀2𝑀2
Time
(d) Recu en d i
Figu e 1.7: Types o concep d i based on hei occu ence o e ime.
(ii) online algo i hms, which pe o m he analysis on- he- ly, as new da a a e gene a ed, and a e
usually o ien ed owa ds eal- ime decision making. In his Ph.D. disse a ion we ocus only on
he de elopmen o o line algo i hms.
I should be men ioned ha changes can occu in mul iple o ms, acco ding o hei empo al
dis ibu ion [46], as depic ed in Figu e 1.7:
1.
Sudden changes, in which he new da a dis ibu ion eplaces he p e ious one immedia ely,
so ha he change occu s a a speci ic ins an o ime.
2.
G adual changes, in which bo h dis ibu ions, he old and he new, coexis o a pe iod o
ime, al e na ing hei appea ance and ading away/becoming mo e p esen as he change
akes place. These changes a e cha ac e ized by he ac ha hey do no occu a an
ins an in ime, bu in a change egion.
3.
Inc emen al changes, in which a se ies o small successi e changes occu due o
in e media e dis ibu ions in he da a be ween he o iginal and he inal dis ibu ion. As
in he case o g adual changes, hese changes a e cha ac e ized by a egion du ing which
he di e en models succeed each o he .
4.
Recu en changes, which a e epea ed pe iodically o e ime wi h a ce ain equency.
These changes a e cha ac e ized mo e by he equency wi h which hey a e epea ed
han by he poin o egion in which hey occu .
I should be highligh ed ha he i s wo change ypes a e mu ually exclusi e. Thus, a
change will be ei he sudden o g adual, bu can also be inc emen al and/o ecu en . In
addi ion, no e ha in business p ocess managemen bo h inc emen al and ecu en changes can
12
Chap e 1. In oduc ion
be app oached as a sucession o sudden o g adual changes in he co esponding p ocess model:
o inc emen al changes e e y model is di e en , while o ecu en changes, he di e en
models a e epea ed o e ime. Fo his eason, his Ph.D. disse a ion has ocused on bo h
sudden and g adual changes only.
De ini ion 8: G adual d i , Sudden d i
A g adual d i is de ined as a change whe e he beha iou be o e he change does no
disappea suddenly, bu coexis s wi h he one a e he change o a pe iod o ime, while
anishing un il i is no longe obse ed. Gi en wo ime ins an s
𝑡1
and
𝑡2
ha bound he
change, wo models can be disco e ed,
𝑁<𝑡1
and
𝑁>𝑡2
, ha cap u e he beha iou be o e
and a e hose ins an s. Fo a change o be conside ed as g adual, ou condi ions mus
be sa is ied:
1.
The beha iou s cap u ed by he models disco e ed be o e
𝑡1
and a e
𝑡2
a e di e en :
𝐵𝑁<𝑡1≠𝐵𝑁>𝑡2.
2.
Some o he beha iou obse ed be ween
𝑡1
and
𝑡2
is cap u ed by he model
disco e ed be o e 𝑡1:𝐵𝐿[𝑡1,𝑡2]∩𝐵𝑁<𝑡1≠∅.
3.
Some o he beha iou obse ed be ween
𝑡1
and
𝑡2
is cap u ed by he model
disco e ed a e 𝑡2:𝐵𝐿[𝑡1,𝑡2]∩𝐵𝑁>𝑡2≠∅.
4.
All o he beha iou obse ed be ween
𝑡1
and
𝑡2
is cap u ed ei he by he model
disco e ed be o e
𝑡1
, by he model disco e ed a e
𝑡2
o by bo h:
𝐵𝐿[𝑡1,𝑡2]⊆
(𝐵𝑁<𝑡1∪𝐵𝑁>𝑡2).
I any o hese condi ions a e no me , he change is conside ed a sudden change, whe e
he old beha iou is eplaced ins an ly by a new one.
One o he bigges challenges in de ec ing concep ual d i s is o dis inguish be ween eal d i s
and ou lie s [
47
], i.e., anomalous obse a ions ha do no e lec a eal change in he models,
bu a he spu ious execu ions ha a e no common and do no imply changes in he s uc u e o
p ocesses. To a oid con using hese wo concep s, we in oduce he e m o a d i candida e, a
poin wi h he po en ial o ep esen a change in he model bu which mus be con i med la e
o ejec ha i is an e ec o he p esence o noise in he da a.
13
Víc o José Gallego Fon enla
De ini ion 9: D i candida e
A d i candida e can be de ined as a po en ial change in he s uc u e o he p ocess ha
has o be con i med la e . Gi en wo consecu i e windows
𝜔𝑖
and
𝜔𝑖+1
, and wo p ocess
models
𝑁𝑖=(𝑃𝑁𝑖, 𝑇𝑁𝑖, 𝐹𝑁𝑖, 𝜆𝑁𝑖)
and
𝑁𝑖+1=(𝑃𝑁𝑖+1, 𝑇𝑁𝑖+1, 𝐹𝑁𝑖+1, 𝜆𝑁𝑖+1)
disco e ed om
each o hese windows using he same disco e y algo i hm, we say ha he window
𝜔𝑖
is a d i candida e when
𝑇𝑁𝑖≠𝑇𝑁𝑖+1∨𝐹𝑁𝑖≠𝐹𝑁𝑖+1
. A d i is con i med only a e
se e al successi e windows a e ma ked as d i candida es and, in ha momen , he
change is pinpoin ed o he speci ic ace ha igge ed he change — he i s ace o he
i s candida e in he case o i ness, o he las ace o he i s window in he case o
p ecision—.
1.2 Hypo hesis and objec i es
In p ocess mining, a change in a model implies an immedia e change in he con o mance
measu es. When a pa h om he model s ops appea ing in aces, i leads o educed p ecision.
Con e sely, i a new pa h ha is no included in he model s a s appea ing in he aces, i
causes a educ ion in i ness. These wo si ua ions sugges ha he e migh be a connec ion
be ween p ocess mining con o mance me ics and concep d i de ec ion. The e o e, he
hypo hesis o he Ph.D. hesis can be o mula ed as ollows:
D i de ec ion and classi ica ion can be add essed by analyzing how he i ness and
p ecision e ol e along de p ocess.
Conside ing his hypo hesis, he main objec i e o his Ph.D. disse a ion is o de ec
au oma ically sudden and g adual changes in he s uc u e o p ocesses, based on he e olu ion
o he con o mance me ics. The solu ion should each a high accu acy, de ec ing all he
possible change pa e ns; main ain a low delay, allowing o ganiza ions o localize p ecisely
he ins an when he change ook place; and be obus o he p esence o noise, o dis inguish
be ween anomalous o in equen beha io and eal p ocess changes. This main objec i e can
be spli in h ee sub-objec i es:
O1. The de ec ion and localiza ion o sudden d i s.
14
Chap e 1. In oduc ion
The i s objec i e is o design and de elop an algo i hm ha can de ec sudden con ol-
low d i s in a p ocess om an e en log. As a e e ence, all he common change pa e ns
iden i ied in p ocess mining [48] should be suppo ed by he algo i hm.
O2. The de ec ion and localiza ion o g adual d i s.
The second objec i e is o de ec g adual changes bu , also, o di e en ia e when he
change is sudden and g adual. This is specially in e es ing because, in a eal en i onmen ,
di e en ype o changes can coexis , so being able o classi y hem is a equi emen .
O3. The adap a ion o he o me solu ions o noisy en i onmen s.
Finally, as a hi d objec i e, all he p e ious algo i hms should be adap ed o deal wi h
noisy and complex e en logs, whe e he s uc u e o he unde lying p ocesses can be
mo e complex, which can hinde he compu a ion o con o mance measu es.
1.3 Resea ch Con ibu ions
The esea ch de eloped in his Ph.D. disse a ion led o he ollowing con ibu ions:
1.
A o mal, ma hema ical demons a ion ha con o mance me ics can be used o
de ec bo h sudden and g adual changes in he con ol- low o a p ocess.
We ha e p o en, combining se heo y and de ini ions o i ness and p ecision, ha
moni o ing hese compliance me ics o e ime allows us o de ec bo h sudden and
g adual d i s in he con ol- low o a p ocess.
2. C2D2: An algo i hm o Con o mance Checking-based D i De ec ion.
We ha e p oposed and success ully de eloped an algo i hm (C2D2) o he de ec ion and
localiza ion o sudden changes in a p ocess con ol- low. C2D2 moni o s he con o mance
me ics along ime using a a sliding window and a simple linea eg ession, being able o
de ec all he change pa e ns wi h a high accu acy while main aining a small delay. The
main con ibu ions o C2D2 a e as ollows: (i) A me hod o de ec ing and iden i ying
he poin s whe e he con ol- low o he p ocess changes suddenly. (ii) A no el and
e icien es ima o o he change in he p ecision o a model wi h espec o a se o aces.
(iii) The use o eg ession echniques o moni o sudden changes in he con ol- low o a
p ocess.
15

Víc o José Gallego Fon enla
3. CRIER: An algo i hm o Con o mance-based G adual d i de ec ion.
We ha e success ully de eloped an algo i hm (CRIER) o he de ec ion and localiza ion
o g adual changes in he con ol- low o a p ocess. CRIER builds up on he same idea
ha moni o ing con o mance me ics along ime can se e o de ec changes —as in
he case o he sudden d i s—, and ex ends i o deal wi h g adual changes. The main
con ibu ions o CRIER a e as ollows: (i) A o mal p oo ha a g adual con ol- low
change will always imply some new and obse able beha iou . (ii) A me hod o de ec ing
and de e mining he in e als whe e he con ol- low o a p ocess g adually changes.
(iii) A me hod o he classi ica ion o changes in sudden and g adual d i s.
4. R-CRIER: An algo i hm o Robus d i de ec ion in noisy en i onmen s.
We ha e designed and implemen ed a unc ional solu ion (R-CRIER) o obus d i
de ec ion on noisy en i onmen s. R-CRIER s a s wi h he lessons lea ned in he
de elopmen o bo h C2D2 and CRIER and, om he e, adap s he moni o ing o
con o mance me ics o deal wi h noisy en i onmen s whe e anomalous execu ions can
lead o w ong de ec ions. The main con ibu ions o R-CRIER a e as ollows: (i) A o mal
demons a ion ha moni o ing he slope o a eg ession compu ed o e con o mance
me ics alues du ing some ime can allow d i de ec ion in noisy en i onmen s educing
he numbe o alse posi i e de ec ions. (ii) A me hod o de ec ing an localizing sudden
and g adual d i s wi h a high accu acy e en on high-noise en i onmen s.
1.3.1 Publica ions
All he con ibu ions shown in his disse a ion a e included in he ollowing publica ions:
Jou nals
•
Víc o Gallego-Fon enla, Juan Vidal and Manuel Lama, A Con o mance Checking-
based App oach o Sudden D i De ec ion in Business P ocesses,IEEE T ansac ions
on Se ices Compu ing, 16:13-26, 2023 (A ailable online: Oc obe 2021). ISSN: 1939-
1374. doi: 10.1109/TSC.2021.3120031.
Jou nal Impac Fac o (JCR 2021): 11.019
5/164 (Q1) COMPUTER SCIENCE, INFORMATION SYSTEMS
2/110 (Q1) COMPUTER SCIENCE, SOFTWARE ENGINEERING
16
Chap e 1. In oduc ion
•
Víc o Gallego-Fon enla, Juan Vidal and Manuel Lama, G adual D i De ec ion
in P ocess Models Using Con o mance Me ics,Business & In o ma ion Sys ems
Enginee ing, Submi ed. ISSN: 2363-7005. doi: 10.48550/a Xi .2207.11007.
Jou nal Impac Fac o (JCR 2021): 5.675
33/164 (Q1) COMPUTER SCIENCE, INFORMATION SYSTEMS
Na ional Con e ences
•
Víc o Gallego-Fon enla, Juan Vidal and Manuel Lama, De ección de concep d i
en mine ía de p ocesos basado en ag upamien o de azas,Jo nadas de Ciencia e
Ingenie ia de Se icios (JCIS), 2018. hdl: 11705/JCIS/2018/005.
•
Manuel Lama, Juan Vidal, Víc o Gallego-Fon enla and Ál a o Po o A es, Recomen-
dación de ac i idades gami icadas basada en mine ía de p ocesos,Jo nadas de
Ciencia e Ingenie ia de Se icios (JCIS), 2019. hdl: 11705/JCIS/2019/018.
•
Víc o Gallego-Fon enla, Juan Vidal and Manuel Lama, A Con o mance Checking-
based App oach o Sudden D i De ec ion in Business P ocesses (Summa y),
Jo nadas de Ciencia e Ingenie ia de Se icios (JCIS), 2022. hdl: 11705/JCIS/2022/007.
1.3.2 Pa icipa ion in R&D p ojec s, con ac s and ne wo ks
Aside om he publica ions men ioned abo e, he de elopmen o his Ph.D. hesis has lead o
collabo a ions in he ollowing p ojec s:
•
CAREBOT - In elligen Robo ic Uni s o Ambula o y Heal hca e Ac i i ies. This
p ojec pu sued he de elopmen o obo ic assis an s o help pa ien s o ull ill hei
ou ines and p esc ip ions a hei home.
As a esul o his p ojec , wo p oduc s ha e been de eloped. On he one side, an e en
cap u ing and p ep ocessing cloud sys em ha e been designed, de eloped and deployed.
On he o he side, a ace clus e ing algo i hm has been de eloped and alida ed in a Big
Da a en i onmen . Bo h de elopmen s will la e be used o ull illing he objec i e O3.
The adap a ion o he o me solu ions o noisy logs and eal p ocesses by p o iding eal
logs o complex, loosely s uc u ed p ocesses and a me hod o spli ing hem in simple
subp ocesses, espec i ely.
17
Víc o José Gallego Fon enla
•
BIGBISC - Fueling In elligence o Business P ocesses wi h So Compu ing in Big
Da a Scena ios. In his p ojec , he algo i hms p esen ed in his Ph.D. disse a ion ha e
been adap ed o look o changes in equen pa e ns execu ed by use s, a he han on
comple e p ocess models. In addi ion, ace clus e ing echniques ha e been applied o
simpli y he p oblem by applying a di ide-and-conque s a egy whe eby o each da a
clus e only a subse o aces ha a e simila o each o he a e p ocessed, so ha he
complexi y o he ex ac ed pa e ns is g ea ly educed.
As a esul o his p ojec , he algo i hms ha e been es ed on eal logs gene a ed by he
managemen p ocess o pa ien s wi h al ula hea diseases in he ca diology se ice o
he Uni e si y Hospi al Complex o San iago de Compos ela (CHUS) o e he cou se o
a yea .
•
RAI4P - Responsible AI o P ocess Mining 2.0. The objec i e o his p ojec is he
de elopmen o p edic i e moni o ing echniques o p ocess mining ha allow o o ecas
di e en ea u es o he execu ions, such as he nex ac i i ies o he emaining ime.
Speci ically, he algo i hms p esen ed in his disse a ion ha e been in eg a ed in se e al
p edic ion algo i hms, so ha he p edic ion akes in o accoun possible changes in he
p ocesses be o e p oducing an ou pu .
•
INCEPTION - In elligen Handling o Concep D i in P ocess Mining Suppo ed
by Cloud Compu ing. This ac i i y is a p oo -o -concep p ojec in which he concep
d i de ec ion algo i hms de eloped in he con ex o he BIGBISC p ojec a e deployed
o a dis ibu ed in aes uc u e in he cloud. The solu ion is accesible h ough a se o
REST APIs, which makes i independen and easily in eg a ed in o any exis ing pla o m.
As pa o his p ojec , he algo i hms de eloped du ing his Ph.D. disse a ion ha e been
adap ed o suppo la ge amoun s o da a om complex and weakly s uc u ed p ocesses,
and he implemen a ions ha e been op imized in o de o ob ain esul s in hese con ex s
in a easonable ime. Speci ically, he algo i hms ha e been modi ied in wo pe spec i es:
on he one hand, in eg a ing clus e ing algo i hms o spli complex p ocesses in smalle
and simple subp ocesses; and, on he o he hand, modi ying he eg ession me hods used
o de ec changes in o de o make hem obus o noisy execu ions in weakly s uc u ed
p ocesses.
•
INSIDE - Emo ion-awa e P ocess Mining o Imp o ing he Adhe ence in Ca diac
Rehabili a ion. The objec i e o his esea ch p ojec is o p o ide insigh s abou he
18
Chap e 1. In oduc ion
adhe ence o pa ien s o Ca diac Rehabili a ion p ocesses by combining p ocess mining
echniques wi h pa ien s mood ecogni ion based on he use o wea able de ices.
Speci ically, he algo i hms p esen ed in his Ph.D. disse a ion a e used o e alua e how
he changes in he s uc u e o he ca diac ehabili a ion p ocess a ec he he causali y
o pa ien s d opou s.
•
RCIS - Se ice Science and Enginee ing Ne wo k. Du ing he de elopmen o his
Ph.D. disse a ion I ha e ac i ely pa icipa ed in he Se ice Science and Enginee ing
Na ional Ne wo k (TIN2014-53986-REDT), which b ings oge he he leading expe s
in se i iza ion and p ocess mining in Spain. As a esul o his collabo a ion se e al
algo i hms de eloped in he amewo k o his Ph.D. disse a ion we e published h ough
publically accesible REST APIs.
1.4 O he Con ibu ions
The de elopmen o his Ph.D. disse a ion has also led o he ollowing, mo e echnical,
con ibu ions:
1. Sudden d i logs - A da ase o alida ing sudden d i de ec ion algo i hms.
As a pa o he de elopmen o C2D2, h ee da ase s composed by mul iple log iles ha e
been gene a ed. Speci ically, h ee models om he s a e o he a in p ocess mining
—a loan applica ion p ocess [
20
], a hospi al eme gency wa d p ocess [
49
] and a cen al
enous ca he e p ocess [
50
]— ha e been used, gene a ing, o each applicable change
pa e n [
48
],
4
logs wi h
4
di e en sizes —
2,500
,
5,000
,
7,500
and
10,000
aces—.
Speci ically,
204
log iles ha e been gene a ed. This da ase , a ailable online
1
, has
been designed o be used as a benchma k o es ing con ol- low sudden d i de ec ion
algo i hms.
2. G adual d i logs - A da ase o alida ing g adual d i de ec ion algo i hms.
As a pa o he de elopmen o CRIER, one da ase composed o mul iple e en logs
has been gene a ed, using he same loan applica ion p ocess and change pa e ns om
he sudden d i logs. In o al,
120
e en logs ha e been gene a ed, wi h
12
di e en
p obabili y dis ibu ions o ansi ioning be ween he models. This da ase , a ailable
1h ps://gi lab.ci ius.usc.es/P ocessMining/logs/-/ ee/mas e /d i /sudden
19
Víc o José Gallego Fon enla
no pe o m well in p ocesses wi h loops, which a ec s he accu acy esul s. Also, as in he
p e ious app oach, he delay esul s a e e y dependan on he size used o spli ing he log.
Finally, he g aph ea u es conside ed o compa ing models do no ake in o accoun small
di e ences in he g aphs, so he me hod will pe o m poo ly in noisy en i onmen s.
Clus e ing-based app oaches
In [
16
], he au ho s p opose an online app oach based on he ex ac ion o his og ams om
aces and hen use a clus e ing algo i hm o gene a e g oups o simila aces. A change is
igge ed when a new clus e appea s. An impo an d awback o his app oach is ha i does
no ake in o accoun he o de o e en s. Thus, i can only de ec he addi ion o emo al o new
ac i i ies, bu no he changes in he p ecedence ela ions be ween hem, so accu acy esul s a e
poo o some change pa e ns. In [
18
], he au ho s clus e aces using he dis ance be ween
pai s o ac i i ies. Howe e , his app oach does no suppo models wi h loops. Mo eo e , he
dis ance can igno e ce ain change pa e ns depending on how many ac i i ies a e a ec ed by
he change, ha ing an impac on he accu acy alues. In e ms o delay, bo h app oaches should
pe o m well, as he clus e coun is no speci ied a p io i, so he log should be spli igh a he
poin whe e he d i happens. Also, bo h algo i hms should be accep ably obus , as long as
he clus e ing does no c ea e a new g oup when anomalous execu ions appea .
In [
17
], he au ho s ex end a ace clus e ing algo i hm [
67
] adding a ime dimension o
o ce clus e s o include only consecu i e aces, and hus be able o de ec changes. The
ad an age o his app oach is ha he delay esul s should be good, as he log is ideally spli jus
whe e he change happens. Howe e , he app oach highly depends on he numbe o clus e s,
ixed by he use , and only ob ains good esul s when he numbe o clus e s is equal o he
numbe o changes, hus impac ing bo h accu acy —i he numbe o clus e s is di e en om
he numbe o changes, alse posi i es and nega i es will appea — and obus ness —high
numbe o clus e s can lead o noisy execu ions c ea ing a w ong clus e —.
In [
19
], he au ho s use a Ma ko clus e ing algo i hm o e di e en ime windows o de ec
changes, bu he app oach does no ocus on he con ol- low pe spec i e. Ins ead, mul iple
iewpoin s o he p ocess a e aken in o accoun simul aneously, mixing con ol- low changes
wi h beha io al and esou ce changes. Also, he accu acy o he de ec ion is highly dependen
on he ea u es used o ep esen he aces, which can igno e ce ain change pa e ns. In e ms
o delay, esul s depends on he choosen window size used o compu ing aces ea u es, ge ing
accep able esul s i he window size is small enough, bu wo sening i he window size is oo
26

Chap e 2. Rela ed wo k
big. Finally, he app oach should be qui e obus as long as he clus e ing app oach should no
c ea e new clus e s i he noise is e enly dis ibu ed along he log.
Windowing and s a is ical analysis-based app oaches
In [
58
], he au ho s p opose a me hod o online concep d i de ec ion using a polyhed on-based
log ep esen a ion. Then, hey moni o he p obabili y ha a ace alls in o ha polyhed on
using he ADWIN algo i hm [
68
]. The main d awbacks o his app oach is ha i canno de ec
all change pa e ns, penalizing accu acy. Also, he me hod is no obus as i does no conside
he p esence o noise in he execu ions, aking all beha iou as expec ed. Online de ec ion is
also add essed in [
59
], whe e he au ho s disco e a p obabilis ic p ocess model ha , gi en an
ac i i y, assigns a p obabili y o e e y possible successo , and checks how hese p obabili ies
e ol e h oughou he comple e log using s a is ical hypo hesis es s. Al hough he me hod
iden i ies d i s in mos cases, small changes in less likely ac i i ies gene a e changes in he
p obabili ies ha can s ill emain unde ec ed, penalizing accu acy. Howe e , his also makes he
app oach somewha noise obus , as low equency beha iou should no a ec i s pe o mance.
Wi h espec o delay, bo h algo i hms a e expec ed o pe o m well, as hey un online, so he
d i can be de ec ed jus when i happens.
In [
45
], he au ho s use a ixed-size window o e some ea u es ex ac ed om he
ollows/p ecedes ela ions p esen in aces, and s a is ical hypo hesis es s o e alua e whe he
hese ea u es ha e changed signi ican ly. The weak poin o his me hod is ha i equi es a
lo o in e ac ion om he use , including p e ious knowledge o he p ocess model and he
a eas whe e he changes can be loca ed. An ex ension o his wo k has been p oposed in [
60
],
whe e he au ho s implemen a ecu si e bisec ioning app oach. Speci ically, hey ake he
aces ha a e in ol ed in a d i de ec ion and ecu si ely spli hem in o hal es, in ending o
au oma ically localize he change. A d awback o his app oach is ha i s ill equi es he use
o know he possible changes o ob ain good esul s. The accu acy o hese wo app oaches
is highly ied o he ea u es choosen o e alua e changes, penalizing accu acy i he choosen
ea u e is no able o cap u e some change pa e ns. In e ms o delay, he i s one is highly
dependen on he choosen window size. The second one educes he delay, as i adjus s he
window size au oma ically o be e localize he d i . A simila solu ion is p esen ed in [
61
],
whe e he au ho s p opose he usage o e en class co ela ion as a ea u e, and apply s a is ical
hypo hesis es s o de ec changes. This app oach ails in de ec ing some change pa e ns such as
he changes in he execu ion o de o ac i i ies, penalizing again he accu acy. Also, i inhe i s
27
Víc o José Gallego Fon enla
he d awbacks om [
45
] ela ed o he beha io o he delay. Among hese h ee p oposals,
jus [
60
] akes in o accoun he concep d i de ec ion in noisy en i onmen s, p o iding some
suppo o de ec ion in hese con ex s.
Ano he in e es ing app oach, called P ocessD i , was p oposed in [
63
], whe e he au ho s
ans o m aces in o pa ial-o de ed- uns and hen apply a s a is ical hypo hesis es o e wo
windows (one o e e ence and one o de ec ion) o de ec changes. The main d awback o
his app oach lies in i s sensi i i y o changes in he equencies o ce ain ela ions p esen in
he log, which may lead o alse posi i es in he de ec ion, which impac s accu acy. A ela ed
me hod is p esen ed in [
64
], whe e he au ho s ocus on de ec ing he change a he e en
le el ins ead o a ace le el. Speci ically, hey ex ac he
𝛼+
ela ions om wo consecu i e
adap i e windows o e en s and, hen, applying a s a is ical es , namely he G- es , compa e he
ela ions dis ibu ion o hese wo windows. This allows o de ec changes e en wi h un inished
execu ions, and educe he de ec ion delay. The d awback o his app oach is ha i equi es
high amoun s o aces o be able o de ec changes. Fu he mo e, changes ha a e close o
each o he may be igno ed, which again has an impac on he accu acy. In e ms o delay, bo h
app oaches should ob ain good esul s, as hey use o e lapping sliding windows, so he change
can be p ecisely pinpoin when i happens. Only he second one o he app oaches conside he
p esence o noise in he log, imp o ing he esul s o he i s one, bu i s ill es ic s i sel o
linea combina ions o beha iou , limi ing i s applicabili y o noisy en i onmen s.
In [
65
], he au ho s p esen TPCDD, a me hod ha ans o ms he e en log in o a ela ion
ma ix using di ec succession and weak o de ela ions, whe e each column ep esen s a ace
and each ow a ela ion. Then, based on he end o hese ela ions, i gene a es candida e
d i poin s. These poin s a e clus e ed using DBSCAN, o g oup candida es ha belong o he
same d i poin . This app oach elies hea ily on a co ec adius o he DBSCAN algo i hm,
de ec ing all change pa e ns bu po en ially ge ing a high numbe o alse posi i es when i is
oo low and a high numbe o alse nega i es when i is oo high. Also, he algo i hm shows
good esul s in e ms o delay, bu i does no deal wi h noisy aces, leading i o poo esul s in
noisy en i onmen s.
In [
66
], he au ho s p opose an algo i hm o de ec ing sudden d i s in e en s eams using
ela ion equency maps and an adap i e window. They p opose he use o an ADWIN wi h
di e en dis ances be ween hese equency ma ices, so a change would be de ec ed i wo
consecu i e equency maps a e di e en enough. The main d awback wi h his app oach
lies in choosing a good dis ance me ic o de ec all change pa e ns in any con ex , ha ing an
28
Chap e 2. Rela ed wo k
Table 2.1:
App oaches o sudden d i de ec ion om he s a e o he a and hei pe o mance
o accu acy, delay and obus ness pe spec i es.
App oach Accu acy Delay Robus ness
S e z and Rinde le-Ma [11] Model- o-log alignmen − ± ±
Lakshmanan e al. [14] G aph analysis − − −
Seelige e al. [15] G aph analysis − − −
Junio e al. [16] Clus e ing − + ±
Acco si and S ocke [18] Clus e ing − + ±
Luengo and Sepúl eda [17] Clus e ing − + −
Hompes e al. [19] Clus e ing − ± ±
Ca mona and Ga aldà [58] Windowing plus s a is ical analysis − + −
Webe e al. [59] Windowing plus s a is ical analysis − + +
Bose e al. [45] Windowing plus s a is ical analysis − − −
Ma jushe e al. [60] Windowing plus s a is ical analysis − + ±
Kuma e al. [61] Windowing plus s a is ical analysis − − −
Maa adji e al. [63] Windowing plus s a is ical analysis ± ± −
Os o a e al. [64] Windowing plus s a is ical analysis ± + ±
Zheng e al. [65] Windowing plus s a is ical analysis ± + −
Hassani [66] Windowing plus s a is ical analysis − − −
impac on accu acy, delay and obus ness.
Table 2.1 p o ides a summa y o he pe o mance o he s a e o he a app oaches. I is
wo h no ing ha only he app oaches p esen ed in [
64
] and [
65
] exhibi a good accu acy in
de ec ing changes, ega dless o he ype o change pa e ns, while s ill main aining a low delay.
2.2 G adual d i de ec ion
The numbe o p oposals p esen in he s a e o he a is ai ly educed o g adual d i
de ec ion. This may be due o he lack o base solu ions ha p o ide su icien ly good esul s
ha can be adap ed o he de ec ion o g adual changes in he p ocess con ol- low.
29
Víc o José Gallego Fon enla
Model- o-log alignmen -based app oaches
In [
13
], he log is ans o med in o a ime se ies using a ea u e called -measu e ha compa es
he ela ion ma ices be ween wo consecu i e windows. Then, he algo i hm looks o ou lie s
in hese ime se ies, and de e mines ha a change exis s when one is de ec ed. The main
d awback o his app oach is ha i does no dis inguish sudden and g adual d i s and i is p one
o mix up changes wi h ou lie s, impac ing accu acy and obus ness. Mo eo e , i is also no
ex ensi ely es ed, being e alua ed agains 4 syn he ic logs, whe e hey ob ain highly a iable
esul s o accu acy, wi h alues be ween
0.6
and
0.95
depending on he used pa ame e s. On
he good side, he algo i hm is expec ed o pe o m well in e ms o delay, as no hing p e en s
i om de ec ing he d i jus when i happens.
In [
11
], he au ho s p opose an algo i hm ha deals wi h a s eam o e en s, allowing he
de ec ion o changes in incomple e aces. Using a window o a gi en size, di e en e sions o
he p ocess model a e disco e ed — he p ocess his o y— and he i ness is compu ed agains
he las mined model. In his app oach, a change is p esen when he i ness o a ace is below
a h eshold. Then, de ec ed changes a e classi ied in sudden, g adual, inc emen al o ecu ing
based on he numbe o p ocess his o ies a ailable, hei i ness alues and he p esence o
un inished aces in he momen he p ocess changes. Thus, when a ace does no i he las
disco e ed model, a new one is mined using only he un i ing aces. To p e en alse posi i es,
each model also ecei es an sco e, and a model is conside ed o change only when ha sco e is
o e a h eshold, making he algo i hm obus o noisy execu ions i he h eshold is choosen
co ec ly. As a disad an age, inc easing he h eshold will penalize delay, as he algo i hm
has o wai mo e un il con i ming a d i . Finally, changes a e classi ied in sudden, g adual,
ecu ing and inc emen al using bo h wo new h esholds and he p ocess his o y. The main
d awback o his app oach is ha i equi es he use o ha e a deep knowledge o he p oblem
in o de o une he hype pa ame e s used in he de ec ion — he window size and 4 di e en
h esholds—. Fu he mo e, he algo i hm can no de ec all s uc u al change pa e ns, e.g.,
he ans o ma ion o an op ional pa allel s uc u e in o an exclusi e choice whe e he o de o
some ac i i ies is en o ced, ha ing a nega i e impac in accu acy. Also, he app oach has no
been ex ensi ely es ed and no quan i a i e measu es a e p o ided abou he goodness o he
esul s.
In [
12
], he au ho s p opose a me hod ha is also based on he idea o using he p ocess
model o de ec ing changes. This app oach spli s he log in
𝑛
windows o size
𝑚
. Then, a
se o decla a i e ules is ex ac ed om he comple e log and hei con idence is compu ed
30
Chap e 2. Rela ed wo k
wi h espec o each window, ob aining a mul i alued ime se ies. Finally, a adi ional concep
d i de ec ion algo i hm —namely, he PELT algo i hm— in combina ion wi h a hie a chical
clus e ing echnique is used o de ec changes in he esul ing ime se ies. The main d awback
wi h his app oach is ha he classi ica ion o changes in sudden o g adual is no au oma ic,
bu i mus be pe o med isually by he use . Also, esul s a e highly dependen on he size o
he window, penalizing accu acy and delay i he window size is no choosen p ope ly. As a
posi i e hing, he ex ac ion o ules o e a la ge enough window gi es he me hod some noise
obus ness. Rega ding he alida ion, he algo i hm shows p omising esul s o he de ec ion,
bu i is only es ed wi h 4 syn he ic and 2 eal logs.
Clus e ing-based app oaches
In [
17
], he au ho s p opose he use o an agglome a i e hie a chical clus e ing o e he aces
o de ec changes. Fo he clus e ing, aces a e ans o med o ea u e ec o s ha abs ac
he ace beha iou . Speci ically, he maximal epea [
67
] and he s a ing imes amp o he
ace a e used as ea u es. Once he clus e s a e gene a ed, hey de ine a change as he poin in
ime whe e one clus e ends and a new one s a s. Howe e , his me hod is e y dependen on
he numbe o clus e s, which should be ixed by he use and equal o he numbe o changes
p esen in he log. Choosing he igh numbe o clus e s should lead o low delay alues, since
he log will be spli jus in he poin whe e he change happens. On he o he hand, choosing a
w ong clus e coun will higly impac on accu acy and obus ness, wi h poo esul s due o
alse de ec ions. Rega ding he expe imen a ion, he app oach is only alida ed using 3 logs,
wi h an accu acy —calcula ed as he sum o ue posi i es and ue nega i es, and di ided by
he o al numbe o aces— be ween 57% and 100%.
In [
69
], au ho s p opose an online app oach whe e hey use a clus e ing app oach o e
g aph dis ances. The app oach akes as inpu an e en s eam, and upda es he co esponding
ace g aph e e y ime a new e en is ecei ed. When hey ha e enough aces, a p ocess
model is disco e ed by gene a ing wo weigh ed g aphs: in one o hem, he weigh o he
a cs ep esen s he equency o he ansi ions be ween ac i i ies; and in he o he one, he
a e age ime be ween ac i i ies is he a c weigh . Then, a dis ance be ween he ace g aph
and hese wo weigh ed g aphs is compu ed, and hese dis ances a e g ouped using a online
densi y-based clus e ing algo i hm —namely, DenS eam—, which p o ides some obus ness
o noise. Due o his compu a ion being pe o med pe ace, he delay alues a e expec ed o
be e y low. Rega ding he alida ion, he app oach is es ed using 18 syn he ic logs, bu he
31

Víc o José Gallego Fon enla
only me ic p o ided is he numbe o changes de ec ed. The main d awback o his me hod is
ha i mixes con ol- low and beha io al changes, penalizing i s accu acy. Also, i equi es a
lo o hype pa ame e s o be uned by he use in o de o ob ain good esul s. Finally, as many
o he p esen ed p oposals, i suppo s he de ec ion o e logs wi h g adual changes, bu does
no dis inguish be ween sudden and g adual changes.
Windowing and s a is ical analysis-based app oaches
In [
45
], au ho s p esen an app oach ha compu es ea u es om ollow/p ecede ela ions
and use a s a is ical hypo hesis es o check i he e a e changes in he ea u es o e ime,
speci ically o e wo consecu i e ixed size windows. Examples o hese ea u es a e: o each
ac i i y o he log, he numbe o ac i i ies ha always, some imes and ne e ollow/p ecede a
gi en ac i i y; o each pai o ac i i ies
𝛼1
and
𝛼2
o he log and o each ace, he numbe o
sequences o size
𝑛
ha s a wi h
𝛼1
and con ain
𝛼2
; o each pai o ac i i ies
𝛼1
and
𝛼2
o he
log and o each ace, he signi icance o
𝛼1
ollowing/p eceding
𝛼2
wi h a maximum dis ance
o
𝑛
; e c. The main d awback o his app oach is ha i does no dis inguish be ween sudden
and g adual changes and i deals only wi h linea dis ibu ions o g adual changes, which limi s
i s accu acy and obus ness o some ypes o d i s, and ha i is e y dependan on choosing
he igh window size, a ec ing delay. Addi ionally, i equi es he use o ha e an ad anced
knowledge o he p ocess, including which ea u es o selec , he ac i i ies ha can change
o he s a is ical es o be used in o de o p ocess he log. Fu he mo e, he app oach is no
ex ensi ely es ed, being alida ed only wi h wo syn he ic logs and a eal one, wi hou p o iding
any quan i a i e assessmen o he esul s, al hough hey seem o be p omising. An ex ension
o his app oach is p esen ed in [
60
], whe e he au ho s p opose he use o non-consecu i e
windows, lea ing a gap be ween hem, in o de o inc ease he di e ence be ween ea u es in
g adual en i onmen s in o de o educe he alse nega i es. In his ex ension, he es ic ion o
g adual d i s dis ibu ion is emo ed, so he algo i hm can de ec also changes ha a e no
linea , imp o ing i s obus ness. Ye , he app oach ails o p o ide a solu ion able o iden i y all
d i pa e ns dis inguishing i a change is sudden o g adual, equi es e en mo e knowledge
om he use o se o he pa ame e s —as he size o he gap be ween he windows—, and s ill
does no p o ide quan i a i e me ics in he alida ion, which is pe o med only o e 2 logs.
Ano he e y in e es ing p oposal, hal way be ween he ex ac ion o ea u es and he use o
a p ocess model, is he one p esen ed in [
62
,
63
]. In his app oach, he beha io o he aces is
abs ac ed using pa ial-o de ed- uns —i.e., a g aph ep esen a ion o he aces—. Once he
32
Chap e 2. Rela ed wo k
Table 2.2:
App oaches o g adual d i de ec ion om he s a e o he a and hei pe o mance
o accu acy, delay and obus ness pe spec i es.
App oach Accu acy Delay Robus ness
Li e al. [13] Model- o-log alignmen − + −
S e z and Rinde le-Ma [11] Model- o-log alignmen − ± ±
Yeshchenko e al. [12] Model- o-log alignmen − − ±
Luengo and Sepúl eda [17] Clus e ing − + −
Ta a es e al. [69] Clus e ing − + +
Bose e al. [45] Windowing plus s a is ical analysis − − −
Ma jushe e al. [60] Windowing plus s a is ical analysis − + ±
Maa adji e al. [63] Windowing plus s a is ical analysis ± ± −
beha io is abs ac ed, wo consecu i e sliding windows a e used and, by means o a s a is ical
es , i is checked i he con en o hese windows is signi ican ly di e en . The ac ha i
uses wo consecu i e sliding windows allows he algo i hm o de ec changes wi h a low delay.
Once he changes a e de ec ed, a classi ica ion is pe o med o guess i hey ep esen a sudden
o a g adual d i . In his classi ica ion, a s a is ical es checks i he combina ion o aces
be ween wo consecu i e changes ep esen s a linea combina ion o he aces be o e and
a e he i s and second changes, espec i ely. This is one o he mos ho oughly alida ed
p oposals, es ed wi h mul iple logs. The main d awback o his app oach is ha i can be e y
sensi i e o changes in he equencies o he ela ions, which may lead o he de ec ion o alse
posi i es, penalizing accu acy. Also, he algo i hm can only de ec g adual changes ha a e
due o a linea dis ibu ion o he aces be ween wo models, which may no be he case in eal
logs, a ec ing nega i ely i s obus ness.
Table 2.2 p o ides a summa y o he pe o mance o he main s a e o he a app oaches,
showing ha no app oach p o ides good esul s in e ms o accu acy, being [
63
] and [
60
] he
bes posi ioned ones. Howe e , he e a e app oaches ha achie e good o accep able esul s in
e ms o delay —[13, 17, 60, 69]— and obus ness —[11, 12, 60, 63]—.
33
Víc o José Gallego Fon enla
2.3 Conclusions
As a summa y, he e is no app oach ha p o ides a ully au oma ed solu ion o de ec ing
sudden and g adual changes, suppo ing all ypes o change pa e ns and ace dis ibu ions,
and ha ing an exhaus i e alida on ha de ec changes wi h high accu acy and low delay.
Wi h C2D2 and CRIER we add ess he a o emen ioned issues, imp o ing he esul s o
he p ocess d i de ec ion. P oposed me hods emo e any use in e ac ion in d i de ec ion,
equi ing only a minimum window size o be speci ied. Mo eo e , bo h me hods can de ec all
change pa e ns independen ly o he p ocess s uc u e. Finally, wi h R-CRIER we y o ackle
he p oblem o applying his kind o me hods o en i onmen s whe e he p esence o noise can
make i di icul do dis inguish a eal change om noisy anomalous execu ions. Fu he mo e,
he h ee p oposed me hods a e designed o iden i y d i s wi h low delay and a high accu acy,
minimizing he de ec ion o alse nega i es and posi i es. They ha e been deeply alida ed
using a a ie y o syn he ic logs om models om he s a e o he a , showing be e esul s
han he ones ob ained by he main s a e o he a app oaches.
34
CHAPTER 3
SUDDEN DRIFT DETECTION
Change is he only hing ha is immu able.
— A hu Schopenhaue
In his chap e , we p esen C2D2 (Con o mance Checking-based D i De ec ion), an
algo i hm o o line sudden con ol- low d i de ec ion in p ocess mining. C2D2 elies on he
hypo hesis ha changes in he model s uc u e (d i s) can be de ec ed by changes in i s i ness
and/o p ecision. The e o e, by con inuously moni o ing he con o mance me ics o a p ocess,
hese d i s may be de ec ed.
To illus a e his idea, le ’s ake he example in Figu e 3.1. Le us suppose he models
𝑁1
and
𝑁2
depic ed in Figu es 3.1a and 3.1b. The di e ence be ween bo h models is ha ac i i ies
𝐵
and
𝐶
a e in pa allel in
𝑁1
, bu in sequence in
𝑁2
. Le us also suppose ha he p ocess
𝑁1
changes o
𝑁2
a ins an
𝑖=8
, which log is ep esen ed in Figu e 3.1c, hence o h deno ed as
𝐿1
. T aces
𝜏1
o
𝜏8
co espond o he execu ion o
𝑁1
and aces
𝜏9
o
𝜏16
co espond o
𝑁2
. In
𝐿1
, he concu en execu ion o ac i i ies
𝐵
and
𝐶
becomes a sequence om
𝜏9
onwa ds. A e
his change, aces a e s ill eplayable, so he i ness emains unal e ed. Howe e , no ace in
he window con ains he pa h
𝐴→𝐶→𝐷
om
𝜏9
onwa ds, so he p ecision alls. This can
be seen in Figu e 3.1e, whe e p ecision alls because he model allows mo e beha iou han is
p esen in he aces, bu i ness emains unal e ed.
Víc o José Gallego Fon enla
Algo i hm 3.2 Au oma ic window size op imize
Inpu s: an e en log 𝐿and a minimum window size 𝑛 < |𝐿|
Ou pu s: he op imal window size o p ocessing 𝐿
1: unc ion Adjus Window(𝑛, 𝐿)
2: 𝑁1, 𝑁2, 𝑁3← ∅
3: 𝑛′←𝑛
4: while 𝑁1=𝑁2=𝑁3do
5: 𝑁1←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (⟨𝜏0, . . . , 𝜏𝑛′⟩)
6: 𝑁2←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (⟨𝜏𝑛′, . . . , 𝜏2𝑛′⟩)
7: 𝑁3←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (⟨𝜏2𝑛′, . . . , 𝜏3𝑛′⟩)
8: i 𝑁1=𝑁2=𝑁3 hen
9: 𝑛′←𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡 (𝑛′)
10: end i
11: end while
12: e u n n’
13: end unc ion
change e e y 250 aces. In he case o
pl
(Figu e 3.2a), wo agmen s ha a e o iginally
execu ed in a concu en o m a e ans o med in o a sequen ial execu ion, which should imply
a educ ion in p ecision bu no in i ness. In he case o
cb
(Figu e 3.2b), a agmen is
ans o med om manda o y o skippable, which should imply a educ ion in i ness bu no in
p ecision.
3.2.2 Adjus ing he Window Size
When some beha iou appea s in some aces bu no in he model, hey can be ini ially
conside ed as ou lie s. Bu when his beha iou pe sis s o a long ime, i can be lagged as
a change, ha ing he o ganiza ion an oppo uni y o enhance i s p ocess. Some hing simila
happens when some beha iou is no longe obse ed in he log. A pa h o he p ocess ha
is no p esen du ing a sho pe iod o ime can be seen as a empo a y excep ion. Bu i his
beha iou is absen o a long ime, some op imiza ions can be made o imp o e he p ocess
pe o mance. Hence, small windows will de ec less du able changes, while la ge window
sizes will de ec changes ha pe sis .
Adjus ing he window size o p ocessing he log is no a i ial ask. A small window
would led o mul iple alse de ec ions, due o he window no con aining enough in o ma ion
o desc ibe he p ocess execu ed a a gi en ins an . On he o he hand, a big window would
no de ec some changes, because he e e ence window will con ain aces om be o e and
a e he change. Thus, a good balance be ween he wo op ions is essen ial. To adjus he
42

Chap e 3. Sudden d i de ec ion
𝜏1𝜏2𝜏3𝜏4𝜏5𝜏6𝜏7𝜏8𝜏9𝜏10 𝜏11 𝜏12 𝜏13 𝜏14 𝜏15 𝜏16
Change
𝜔6𝜔12
𝜔5𝜔10 𝜔15
Added Beha iou
Remo ed Beha iou
Added Beha iou
Remo ed Beha iou
𝑁2≠𝑁1
𝑁1=𝑁1
𝑁2≠𝑁1=𝑁1
𝑁1=𝑁1≠𝑁2
Figu e 3.3:
Beha iou o he adap i e window in he example om Figu e 3.1. Log co espond wi h
he one in Figu e 3.1c and Figu e 3.1d o emo ing and adding beha iou , espec i ely.
𝑁1and 𝑁2 e e espec i ely o he models in Figu e 3.1a and Figu e 3.1b.
window size, C2D2 uses an app oach based on he compa ison o models om consecu i e
sublogs (Algo i hm 3.2). We s a wi h h ee emp y models (line 2) and a window size
𝑛′
,
ha is ini ialized o he minimum window size
𝑛
(line 3). Then, h ee new models o h ee
consecu i e sublogs a e disco e ed wi h he same disco e y algo i hm used o he de ec ion
(lines 5 o 7). I hese h ee disco e ed models a e equal, we inc emen he window size and y
again (lines 8 o 10). Else, i any o he disco e ed models di e om he es , he p ocedu e
inishes and he las
𝑛′
is used as he window size. By de aul , we use a minimum window size
o 1% and an inc emen o 0.1% o he log size.
Figu e 3.3 shows why h ee consecu i e models a e equi ed. Le us conside he log in
Figu e 3.1d, ha p esen s a change be ween aces
𝜏8
and
𝜏9
. The change consis in some
beha iou being added o he p ocess ( he execu ion o
𝐵
be o e
𝐶
is eplaced by a concu en
execu ion o hese wo ac i i ies). In his case, using wo windows, one ha con ains beha iou
om be o e he change and one ha con ains beha iou om bo h be o e and a e he change,
is enough because he models will be di e en . Conside now he log in Figu e 3.1c, ha also
con ains a change be ween aces
𝜏8
and
𝜏9
. This ime, he change consis s in some beha iou
being emo ed om he p ocess ( he execu ion o
𝐶
be o e
𝐵
disappea s om he log). In
his case, when using jus wo windows, he model disco e ed wi h aces om bo h p e- and
pos -d i aces e lec s no changes, because he missing pa h is p esen in he p e-d i aces
used o disco e y. In his scena io h ee windows, wi h hei espec i e models, a e equi ed:
one o depic he beha iou o he p ocess be o e he change, one o de ec bo h p e- and
pos -d i beha iou , which will be he same as in he p e-d i case, and one o ep esen he
beha iou a e he change.
43
Víc o José Gallego Fon enla
3.2.3 Con o mance me ics change es ima o s
T adi ional i ness and p ecision me ics a e designed o assess he global quali y o a model.
These me ics use di e en app oaches o compu e i ness and p ecision in a eliable way,
gi ing each ace a sco e in a con inuous scale depending on how well hey con o m o he
model, a he han ollowing a disc e e app oach whe e aces can only ge a bina y a ing
o con o mance. C2D2 use hese me ics o de ec s uc u al changes du ing he execu ion
o a p ocess. Mo eo e , we p opose wo simple i ness and p ecision me ics aside om he
well-es ablished me ics om he s a e o he a . These wo app oaches ha e much lowe
compu a ional complexi y and we e designed o de ec changes in simple and noise- ee logs.
In he case o i ness, we use he pe cen age o eplayable aces. This app oach is no
pa icula ly use ul o measu ing he quali y o a model, since i equally penalizes aces ha do
no i he model and hose ha de ia e sligh ly om i . Despi e his, i can be used o es ima e
changes in i ness, since a change in he pe cen age o aces ha can be eplayed in he model
always leads o a change in he me ic alue. Fo p ecision, he ollowing app oach is used:
PC =1−|OLP DFR|
|OLP|(3.1)
whe e:
•
A se o one-leng h pa hs (OLP) is ex ac ed om he model. An OLP is a pai o
ac i i ies ha a e di ec ly connec ed in he p ocess model, wi hou any o he ac i i y in
be ween.
•
A se o di ec ly- ollows ela ions (DFR) is ex ac ed om he log. A DFR is a pai os
ac i i ies ha appea one a e he o he in he log, wi hou any ac i i y in be ween.
•Ope a o is he di e ence be ween wo se s.
Equa ion (3.1) does no measu e he p ecision pe se, bu he change in he p ecision.
The momen a OLP s ops appea ing in he log is indica i e ha some pa h o he model has
disappea ed. The p oposed app oach e u ns
1
when all he suppo ed beha io o he model
appea s a leas once in he log, and
0
o he wise, i.e., when none o he beha io suppo ed by
he model appea s in he log. The compu a ion o his me ic is illus a ed wi h an example in
Figu e 3.4.
44
Chap e 3. Sudden d i de ec ion
AB
CDE
FG
OLP =⟨(A→B)(A→C)(B→D)(C→D)(D→E)(D→F)(E→G)(F→G)⟩
DFR =⟨(A→B)(A→C)(B→C)(B→D)(C→B)(C→D)(D→E)(E→G)⟩
PC =1−|⟨(D→F)(F→G)⟩|
8=0.75
Log
AB C D E G
A C B D E G
A B C D E G
A C B D E G
A C B D E G
A B C D E G
A B C D E G
A C B D E G
A B C D E G
Figu e 3.4:
PC compu a ion example. Colo ed in g een a e he a cs ha appea in he log.
Colo ed in g ey hose ha do no appea .
3.3 Expe imen a ion
Concep d i algo i hms a e assessed based on wo quali y measu es: On he one hand,
𝐹𝑠𝑐𝑜𝑟𝑒
(Equa ion (3.2a)), which is an accu acy me ic compu ed as he ha monic mean be ween
p ecision (Equa ion (3.2b)) and ecall (Equa ion (3.2c)):
𝐹𝑠𝑐𝑜𝑟𝑒 =2×𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 ×𝑟𝑒𝑐𝑎𝑙𝑙
𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 +𝑟𝑒𝑐𝑎𝑙𝑙 (3.2a)
𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 =𝑇𝑃
𝑇𝑃 +𝐹𝑃 (3.2b)
𝑟𝑒𝑐𝑎𝑙𝑙 =𝑇𝑃
𝑇𝑃 +𝐹𝑁 (3.2c)
On he o he hand, delay (hence o h
Δ
), which is he dis ance be ween he poin when he
change eally happened and when i is de ec ed:
Δ(𝑑𝑅, 𝑑𝐷)=|𝑑𝑅−𝑑𝐷|(3.3)
To classi y he de ec ed changes as ue posi i es (
TP
), alse posi i es (
FP
) o alse nega i es
(
FN
), we use a h eshold
𝜀
, ha ep esen s he e o ole ance o he quali y measu es, and
a neighbo hood
𝛿𝜀
𝑖
, de ined as he in e al be ween
𝑖−𝜀
and
𝑖+𝜀
. Le a change happen a
ins an
𝑖
. This change is classi ied as a
TP
only when i is de ec ed in
𝛿𝜀
𝑖
. When no change
is de ec ed in
𝛿𝜀
𝑖
i is classi ied as
FN
. Finally, all changes de ec ed in
𝛿𝜀
𝑖
whe e a p e ious
change has been al eady de ec ed a e classi ied as a
FP
, as well as he ones de ec ed ou side any
𝛿𝜀
. Figu e 3.5 shows an example wi h wo eal changes (
𝑑5
, a ins an
5
, and
𝑑20
, a ins an
20
),
45
Víc o José Gallego Fon enla
0 5 10 15 20 25
𝛿5
5𝛿5
20
TP FP FP FN
Figu e 3.5:
Change esul s classi ica ion in
TP
,
FP
and
FN
. A do ep esen s a eal change. A c oss
ep esen s a de ec ion. Shadowed a e he neighbo hoods o 𝜀=5.
and h ee de ec ions, a ins an s
4
(
𝑐4
),
7
(
𝑐7
) and
12
(
𝑐12
), using a
𝜀=5
. In his example,
𝑐4
is
classi ied as a
TP
, because i lies in he neighbo hood o
𝑑5
;
𝑐7
is classi ied as a
FP
, because,
despi e being in he neighbo hood o
𝑑5
, ano he change has been de ec ed p e iously;
𝑐12
is
classi ied oo as a
FP
, in his case o being de ec ed ou side any neighbo hood
𝛿5
; and inally,
𝑑20 is classi ied as a FN since no change is de ec ed in i s neighbo hood.
The algo i hm implemen a ion is published online and a ailable as a REST API1.
3.3.1 Valida ion da a
Ou p oposal has been es ed wi h h ee models ex ac ed om he li e a u e [
20
,
49
,
50
], which
desc ibe a loan applica ion p ocess, a hospi al eme gency wa d p ocess, and a cen al enous
ca he e p ocess, espec i ely. These models a e usually pa o benchma ks o concep d i
de ec ion, p ocess disco e y and con o mance ckecking. A se o sy he ic logs o each one o
he p ocess models ha e been gene a ed using he me hodology and change pa e ns desc ibed
in [
63
]. This is he mos ex ended me hodology [
12
,
15
,
65
] o gene a ing da ase s when
alida ing sudden concep d i de ec ion algo i hms in p ocess mining. Fo each p ocess, we
gene a ed a da ase composed o
68
logs:
17
wi h
2,500
aces,
17
wi h
5,000
,
17
wi h
7,500
and
17
wi h
10,000
. The o iginal da ase om [
63
] con ains
4
mo e logs, one o each o
he sizes, bu hey ha e been disca ded because i s d i pa e n —changing he equency o
he b anches in a choice cons uc — does no a ec he con ol- low o he p ocess, bu he
beha iou o he use s. Only he esul s o he expe imen s wi h one o he models —namelly
he loan applica ion p ocess— a e shown in his chap e . De ailed esul s o he o he wo
models can be ound in Appendix A.
The Pe i ne co esponding o he loan applica ion p ocess is depic ed in Figu e 3.6. To
gene a e he
17
modi ied models,
11
simple change pa e ns om [
48
] a e applied o he o iginal
p ocess. These pa e ns can be classi ied in o h ee ca ego ies (Table 3.1): (i) changes in ol ing
he inse ion o new beha io —ma ked wi h
𝐼
—; (ii) changes in ol ing he op ionaliza ion
1h ps:// ec.ci ius.usc.es/concep -d i -api/swagge -ui.h ml
46
Chap e 3. Sudden d i de ec ion
A B
C
D
E F
G
H
I
J
K
L
M
N
O
P
Q
R
S
Figu e 3.6:
Pe i ne o he o iginal loan applica ion p ocess model [
63
] used o gene a e logs.
Ac i i y names a e sho ened o be e unde s andabili y.
Table 3.1: Change pa e ns applied o he o iginal model om Figu e 3.6 and esul ing models.
(a) Change pa e ns.
Code Change pa e n Class
cm Mo e agmen in o/ou o
condi ional b anch
I
cp Duplica e agmen I
pm Mo e agmen in o/ou o
pa allel b anch
I
e Add/ emo e agmen I
p Subs i u e agmen I
sw Swap wo agmen s I
cb Make agmen
skippable/non-skippable
O
lp Make agmen s
loopable/non-loopable
O
cd Synch onize wo agmen s R
c Make wo agmen s
condi ional/sequen ial
R
pl Make wo agmen s
pa allel/sequen ial
R
(b) De i ed models.
Model code Change pa e ns
cm cm
cp cp
pm pm
e e
p p
sw sw
cb cb
lp lp
cd cd
c c
pl pl
OIR lp + e + cd
ORI lp + pl + e
RIO c + cp + cb
ROI pl + lp + p
o a pa o he model —ma ked wi h
𝑂
—; and (iii) changes in ol ing he es uc u ing and
ea angemen o some pa s o he model —ma ked wi h
𝑅
—. In addi ion, ano he
6
models
a e gene a ed by applying a combina ion o simple change pa e ns —one pa e n om each o
he p e iously named ca ego ies— o build a complex change pa e n.
Once all he models a e a ailable, he logs a e gene a ed simula ing execu ions o hose
p ocesses. The o iginal log is hen combined wi h he modi ied ones o gene a e logs wi h
d i s. The inal log is composed joining al e na i ely sublogs om bo h he o iginal model
and he modi ied ones. Each d i ing log p esen s a change e e y
10%
o i s inal size. A log
gene a ion example is ep esen ed in Figu e 3.7. Two logs (
𝐿1
and
𝐿2
) wi h di e en models
a e spli in 5 sublogs wi h equal sizes (
𝐿1
1
o
𝐿5
1
and
𝐿1
2
o
𝐿5
2
). This sublogs a e combined
al e na i ely in o a log 𝐿, wi h size |𝐿1|+|𝐿2|.
47

Víc o José Gallego Fon enla
𝐿1gene a ion
𝐿gene a ion
𝐿2gene a ion
A B
C
D
E F
G
H
I
J
K
L
M
N
O
P
Q
R
S
𝐿1
1𝐿2
1𝐿3
1𝐿4
1𝐿5
1
𝐿1
2𝐿2
2𝐿3
2𝐿4
2𝐿5
2
𝐿1
1𝐿2
1
𝐿3
1𝐿4
1𝐿5
1
𝐿1
2𝐿2
2𝐿3
2𝐿4
2𝐿5
2
A B
C
D
E F
GH
I
J
K
L
M
N
O
P
Q
R
S
Figu e 3.7: Log gene a ion example.
3.3.2
Con o mance checking me ics and disco e y algo i hm impac
In o de o check he impac o he disco e y algo i hm and he con o mance me ics in
C2D2 pe o mance, di e en con igu a ions ha e been es ed:
1.
Disco e y algo i hms: Induc i e Mine (
IM
) [
23
] and Heu is ics Mine (
HM
) [
71
], which
a e wo o he mos used me hods o disco e ing models om e en logs. No algo i hm
based on e olu iona y compu a ion has been selec ed because i would inc ease he
compu a ional complexi y signi ican ly.
2.
Fi ness me ics: Alignmen Based Fi ness (
AF
) [
72
], Nega i e E en Recall (
NR
) [
34
]
and he pe cen age o comple ely Replayable T aces (RT) om Sec ion 3.2.3.
3.
P ecision me ics: Ad anced Beha iou al App op ia eness (
ABA
) [
35
], Nega i e E en
P ecision (NP) [34] and P ecision Change assessmen (PC) om Sec ion 3.2.3.
The key when choosing a disco e y algo i hm and a pai o i ness and p ecision me ics is
o ob ain a combina ion ha allows he esul s o he eg ession o s abilize a ound a alue, so
he slope is ze o while he e a e no changes. I we ocus on i ness, eaching a cons an alue in
absence o changes is easie i we use a disco e y algo i hm ha ensu es aces eplayabili y,
48
Chap e 3. Sudden d i de ec ion
Table 3.2:
Mean
Δ
and
𝐹𝑠𝑐𝑜𝑟𝑒
o e e y es ed con igu a ion o e he
2,500
aces logs o he
loan applica ion p ocess. Window size has been ixed o
100
aces. Bes esul s a e
shadowed in a da ke g ey and unne s-up in a ligh e one. E o ole ance has been se
o a 5% o he log size.
𝐹𝑠𝑐𝑜𝑟𝑒 Δ
IM
𝛾=AF
𝜌=ABA 0.9028 4.0915
𝜌=NP 0.7985 43.6243
𝜌=PC 0.9969 3.6471
𝛾=NR
𝜌=ABA 0.9028 4.0915
𝜌=NP 0.7864 41.5318
𝜌=PC 0.9969 3.5948
𝛾=RT
𝜌=ABA 0.9425 4.0663
𝜌=NP 0.7955 41.7028
𝜌=PC 0.9969 3.5948
HM
𝛾=AF
𝜌=ABA 0.9327 7.4608
𝜌=NP 0.7365 36.1014
𝜌=PC 0.9789 4.4412
𝛾=NR
𝜌=ABA 0.9402 10.3758
𝜌=NP 0.7427 36.8831
𝜌=PC 0.9750 5.3828
𝛾=RT
𝜌=ABA 0.4724 6.0812
𝜌=NP 0.7025 73.5175
𝜌=PC 0.7176 2.9829
such as Induc i e Mine . Howe e , i we use a disco e y algo i hm ha does no ensu e aces
eplayabili y, such as Heu is ics Mine , he selec ed me ic should ake his in o accoun , o he
ob ained alues will no s abilize, so mo e alse posi i es will be no i ied. This can be seen in
he expe imen s in Table 3.2, whe e he esul s o Induc i e Mine do no change signi ican ly
no ma e which i ness me ic is used. On he con a y, when we use Heu is ics Mine , bes
esul s a e ob ained when a mo e obus i ness me ic is used (e.g., alignmen s based one s.
pe cen age o eplayable aces).
On he o he hand, i we ocus on p ecision, he chosen disco e y algo i hm has less impac ,
as none o he disco e y algo i hms used in he expe imen a ion ensu es a pe ec p ecision.
When compu ing p ecision, si ua ions in which a pa h om he model is only p esen in ew
aces (o e en in none) a e qui e common, so he me ic can oscila e a lo . Wi h he use
o he
𝑃𝐶
p ecision me ic his is pa ially add essed, because his me ic does no ake in o
accoun how many imes a pa h occu s bu only i s p esence. This o ces he me ic o con e ge
49
Víc o José Gallego Fon enla
50 100 150 200 250
0
0.5
1
𝐹𝑠𝑐𝑜𝑟𝑒
𝐹𝑠𝑐𝑜𝑟𝑒
0
20
40
60
Δ
Δ
(a) Loan applica ion.
50 100 150 200 250
0
0.5
1
𝐹𝑠𝑐𝑜𝑟𝑒
𝐹𝑠𝑐𝑜𝑟𝑒
0
20
40
60
Δ
Δ
(b) Hospi al eme gency wa d.
50 100 150 200 250
0
0.5
1
𝐹𝑠𝑐𝑜𝑟𝑒
𝐹𝑠𝑐𝑜𝑟𝑒
0
20
40
60
Δ
Δ
(c) Cen al enous ca he e .
Figu e 3.8:
Mean
𝐹𝑠𝑐𝑜𝑟𝑒
(higge is be e ) and
Δ
(lowe is be e ) e olu ion using he
2,500
aces
logs and di e en window sizes. Shadowed in g een is he op imal egion.
quickly, so he eg ession slopes a e nea o ze o ea lie , and change mo e ab up ly when he
pa h disappea s compe ely om he execu ions.
Taking in o accoun he o me esul s, he expe imen s in he ollowing sec ions ha e been
pe o med using IM algo i hm, RT i ness and PC p ecision.
3.3.3 Window size impac
In his sec ion we p esen he esul s o he expe imen s on he in luence o he window size
on he esul s. Figu e 3.8 show how he window size a ec s mean
𝐹𝑠𝑐𝑜𝑟𝑒
and mean
Δ
o
logs o he loan applica ion p ocess wi h
2,500
aces, changes e e y
250
aces, and wi hou
au oma ic window size adjus men .
In all cases, he op imal window size o bo h
𝐹𝑠𝑐𝑜𝑟𝑒
and
Δ
anges be ween
25
and
100
( his a ea is boxed in g een). Sizes below
25
p oduce good esul s in e ms o
Δ
, bu s ongly
penalize he
𝐹𝑠𝑐𝑜𝑟𝑒
alues. In his case, C2D2 iden i ies many alse posi i es because he
e e ence window does no include su icien beha io o disco e a model wi h a high i ness.
C2D2 also ge s a low
𝐹𝑠𝑐𝑜𝑟𝑒
o windows wi h mo e han
100
aces because he disco e ed
model has a low p ecision, allowing oo much beha io ha is no p esen in he log, hus
causing alse nega i es as he window con ains beha io o bo h be o e and a e he change.
3.3.4 Resul s and benchma king
In his sec ion, C2D2 algo i hm is compa ed wi h T ace-Based P oD i (PD-T) [
63
], E en -
Based P oD i (PD-E) [
64
] and TPCDD [
65
], he h ee sudden p ocess d i de ec ion
algo i hms wi h bes esul s in he s a e o he a . Speci ically, we used he ollowing
con igu a ions:
1. PD-T wi h an adap i e window and an ini ial size o 50.
50
Chap e 3. Sudden d i de ec ion
2.
PD-E wi h an adap i e window and an ini ial size o
50
.Rela ion noise il e h eshold
was se o
0%
and sensi i i y o e y high, as he au ho s ecommend o analyzing
syn he ic logs wi hou noise.
3. TPCDD minimum window size se o 100 and DBSCAN adius o 10.
Table 3.3 shows he esul s o he loan applica ion p ocess logs — u he de ailed esul s
o he cen al enous ca he e and he hospi al eme gency wa d p ocesses a e a ailable in
Appendix A—. C2D2 ou pe o ms he es o algo i hms in e ms o
𝐹𝑠𝑐𝑜𝑟𝑒
in all he cases,
excep in
OIR
log, ge ing always he bes a e age alue. Mo eo e , C2D2 is also he second
bes in e ms o delay, e y close o TPCDD, and being all he alues in he same o de o
magni ude.
Table 3.3: Mean 𝐹𝑠𝑐𝑜𝑟𝑒 and Δ alues o each algo i hm using he loan applica ion p ocess logs.
cb
2500 1.0000 6.2222 1.0000 5.5556 0.2000 90.0000 1.0000 78.4444
5000 1.0000 6.7778 0.9000 6.5556 0.7143 57.4000 1.0000 99.6667
7500 1.0000 7.7778 0.9474 16.6667 1.0000 68.6667 0.9474 70.2222
10000 1.0000 9.0000 0.8571 18.2222 0.5000 41.6667 0.8571 84.4444
cd
2500 1.0000 1.7778 1.0000 0.7778 0.0000 — 1.0000 42.4444
5000 1.0000 1.2222 0.9474 0.7778 0.0000 — 0.9412 2.5555
7500 1.0000 2.1111 0.9474 1.0000 0.0000 — 0.9474 2.2222
10000 1.0000 1.5556 0.9474 1.0000 0.0000 — 0.9000 3.3333
c
2500 1.0000 3.8889 1.0000 1.4444 1.0000 40.0000 1.0000 49.7778
5000 1.0000 3.3333 0.9474 9.2222 1.0000 25.7777 1.0000 50.1111
7500 1.0000 2.7778 0.9474 1.5556 1.0000 22.3333 0.9474 37.5556
10000 1.0000 3.8889 0.9474 5.8889 1.0000 29.6667 0.9474 45.8889
cm
2500 1.0000 5.8889 1.0000 11.5556 0.7143 66.0000 0.9412 95.1250
5000 1.0000 7.7778 0.9474 6.1111 0.7143 51.8000 0.8750 17.5714
7500 1.0000 5.3333 0.9474 4.4444 0.9412 83.8750 0.8889 78.6250
10000 1.0000 8.5556 0.9000 7.6667 0.0000 — 0.9474 97.7778
Log size
C2D2 TPCDD PD-T PD-E
𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ
Con inues on nex page
51
Víc o José Gallego Fon enla
3.
De ec g adual changes wi h a low delay, so a change can be p ecisely localized in ime.
4.
Ha e a high accu acy, de ec ing all he changes wi hou alse ala ms no skipping
changes.
CRIER can de ec g adual and sudden changes in e en logs based on he change o
con o mance checking me ics — i ness and p ecision— o e a sliding window, compu ing
hese me ics o he successi e sliding windows om he s a un il he end o he log. The
e olu ion o hese con o mance me ics is e alua ed using linea eg essions and hypo hesis
es ing, so ha a po en ial change is de ec ed when he me ic alues change signi ican ly. In
o de o iden i y g adual d i s, de ec ed change poin s a e analyzed. I he beha iou con ained
be ween wo consecu i e poin s is a combina ion o he beha iou p esen be o e he i s poin
—de ec ed as a change in i ness— and he beha iou a e he second one —de ec ed as a
change in p ecision—, hen he change is classi ied as g adual. This s a egy o de ec ing
g adual changes will be o mally p o en in he nex sec ion.
4.1 G adual d i de ec ion using con o mance me ics
A g adual change is de ined be ween wo ins an s
𝑡1
and
𝑡2
, whe e he p ocess has a beha iou
𝐵1
be o e
𝑡1
, a di e en beha iou
𝐵2
a e
𝑡2
, while
𝐵1
and
𝐵2
coexis in
[𝑡1, 𝑡2]
(see De ini ion 8).
Theo em 4.1: All g adual d i s a e cha ac e ized by a i ness change in
1
and by
a p ecision change in 2.
P oo : Conside a log
𝐿
, wi h a g adual change be ween ins an s
𝑡1
and
𝑡2
, in which he
new beha iou is i s obse ed a
𝑡1
and some old beha iou is less and less equen ly
obse ed, un il i disappea s comple ely a
𝑡2
. Le us conside h ee disjoin se s o
beha iou :
•𝐵𝑐
, which con ains he beha iou ha appea s h oughou he whole du a ion o
he log 𝐿and which can be emp y;
•𝐵𝑝, which con ains he p e ious beha iou o 𝐿 ha disappea s be ween 𝑡1and 𝑡2
and which canno be emp y; and
•𝐵𝑛
, which con ains he new beha iou ha s a s o appea a e
𝑡1
and eplaces
𝐵𝑝
58

Chap e 4. G adual d i de ec ion
a e 𝑡2and which also canno be emp y.
Using hese wo ins an s
𝑡1
and
𝑡2
, we can spli he log
𝐿
in h ee sublogs. Le
𝐿<𝑡1
be he
log con aining all he aces be o e
𝑡1
,
𝐿[𝑡1,𝑡2]
be he log con aining he aces be ween
𝑡1
and
𝑡2
, and
𝐿>𝑡2
be he log wi h he emaining aces a e
𝑡2
. Simila ly, we can de ine
he co esponding beha io s o hese logs as
𝐵𝐿<𝑡1=𝐵𝑐∪𝐵𝑝
,
𝐵𝐿[𝑡1,𝑡2]=𝐵𝑐∪𝐵𝑝∪𝐵𝑛
,
and
𝐵𝐿>𝑡2=𝐵𝑐∪𝐵𝑛
, espec i ely, and he e e ence models
𝑁<𝑡1
,
𝑁[𝑡1,𝑡2]
and
𝑁>𝑡2
ha
can be disco e ed om he aces o hese logs, espec i ely. The alues o i ness and
p ecision be o e he change, i.e., 𝐿<𝑡1, can be compu ed as ollows:
𝛾(𝐿<𝑡1, 𝑁<𝑡1)=
|𝐵𝐿<𝑡1∩𝐵𝑁<𝑡1|
|𝐵𝐿<𝑡1|=
|(𝐵𝑐∪𝐵𝑝) ∩ 𝐵𝑁<𝑡1|
|𝐵𝑐∪𝐵𝑝|=
|(𝐵𝑐∩𝐵𝑁<𝑡1) ∪ (𝐵𝑝∩𝐵𝑁<𝑡1)|
|𝐵𝑐∪𝐵𝑝|
𝜌(𝐿<𝑡1, 𝑁<𝑡1)=
|𝐵𝐿<𝑡1∩𝐵𝑁<𝑡1|
|𝐵𝑁<𝑡1|=
|(𝐵𝑐∪𝐵𝑝) ∩ 𝐵𝑁<𝑡1|
|𝐵𝑁<𝑡1|=
|(𝐵𝑐∩𝐵𝑁<𝑡1) ∪ (𝐵𝑝∩𝐵𝑁<𝑡1)|
|𝐵𝑁<𝑡1|
Which can be simpli ied since 𝐵𝑐and 𝐵𝑝a e disjoin se s:
𝛾(𝐿<𝑡1, 𝑁<𝑡1)=
|𝐵𝑐∩𝐵𝑁<𝑡1|+|𝐵𝑝∩𝐵𝑁<𝑡1|
|𝐵𝑐| + |𝐵𝑝|=
|𝐵𝑐∩𝐵𝑁<𝑡1|
|𝐵𝑐| + |𝐵𝑝|+|𝐵𝑝∩𝐵𝑁<𝑡1|
|𝐵𝑐| + |𝐵𝑝|
𝜌(𝐿<𝑡1, 𝑁<𝑡1)=
|𝐵𝑐∩𝐵𝑁<𝑡1|+|𝐵𝑝∩𝐵𝑁<𝑡1|
|𝐵𝑁<𝑡1|=
|𝐵𝑐∩𝐵𝑁<𝑡1|
|𝐵𝑁<𝑡1|+|𝐵𝑝∩𝐵𝑁<𝑡1|
|𝐵𝑁<𝑡1|
Simila ly, i ness and p ecision alues in he change in e al
[𝑡1, 𝑡2]
wi h espec o his
same model 𝑁<𝑡1can be compu ed as ollows:
𝛾(𝐿[𝑡1,𝑡2], 𝑁<𝑡1)=
|𝐵𝐿[𝑡1,𝑡2]∩𝐵𝑁<𝑡1|
|𝐵𝐿[𝑡1,𝑡2]|=
|(𝐵𝑐∪𝐵𝑝∪𝐵𝑛) ∩ 𝐵𝑁<𝑡1|
|𝐵𝑐∪𝐵𝑝∪𝐵𝑛|
=
|𝐵𝑐∩𝐵𝑁<𝑡1|
|𝐵𝑐| + |𝐵𝑝|+|𝐵𝑛|+|𝐵𝑝∩𝐵𝑁<𝑡1|
|𝐵𝑐| + |𝐵𝑝|+|𝐵𝑛|+|𝐵𝑛∩𝐵𝑁<𝑡1|
|𝐵𝑐| + |𝐵𝑝|+|𝐵𝑛|
𝜌(𝐿[𝑡1,𝑡2], 𝑁<𝑡1)=
|𝐵𝐿[𝑡1,𝑡2]∩𝐵𝑁<𝑡1|
|𝐵𝑁<𝑡1|=
|(𝐵𝑐∪𝐵𝑝∪𝐵𝑛) ∩ 𝐵𝑁<𝑡1|
|𝐵𝑁<𝑡1|
=
|𝐵𝑐∩𝐵𝑁<𝑡1|
|𝐵𝑁<𝑡1|+|𝐵𝑝∩𝐵𝑁<𝑡1|
|𝐵𝑁<𝑡1|+|𝐵𝑛∩𝐵𝑁<𝑡1|
|𝐵𝑁<𝑡1|
59
Víc o José Gallego Fon enla
This equa ion can be simpli ied since
𝐵𝑛
only s a s o appea a e
𝑡1
, i.e.,
𝐵𝑁<𝑡1∩𝐵𝑛=∅
:
𝛾(𝐿[𝑡1,𝑡2], 𝑁<𝑡1)=
|𝐵𝑐∩𝐵𝑁<𝑡1|
|𝐵𝑐|+|𝐵𝑝|+|𝐵𝑛|+|𝐵𝑝∩𝐵𝑁<𝑡1|
|𝐵𝑐|+|𝐵𝑝|+|𝐵𝑛|
𝜌(𝐿[𝑡1,𝑡2], 𝑁<𝑡1)=
|𝐵𝑐∩𝐵𝑁<𝑡1|
|𝐵𝑁<𝑡1|+|𝐵𝑝∩𝐵𝑁<𝑡1|
|𝐵𝑁<𝑡1|
Mo eo e , since
𝐵𝑝≠∅
and
𝐵𝑛≠∅
,
|𝐵𝑐|+|𝐵𝑝|+|𝐵𝑛|>|𝐵𝑐|+|𝐵𝑝|
. Thus,
𝛾(𝐿<𝑡1, 𝑁<𝑡1)> 𝛾(𝐿[𝑡1,𝑡2], 𝑁<𝑡1)
bu
𝜌(𝐿<𝑡1, 𝑁<𝑡1)=𝜌(𝐿[𝑡1,𝑡2], 𝑁<𝑡1)
, con i ming ou
hypo hesis ha i ness dec eases a he beginning o a g adual d i , bu p ecision emaining
unal e ed.
Once he beginning o he d i has been de ec ed, a new model
𝑁[𝑡1,𝑡2]
is disco e ed
using he log
𝐿[𝑡1,𝑡2]
. Then, he con o mance me ics can be compu ed using De ini ions 5
and 6 as ollows:
𝛾(𝐿[𝑡1,𝑡2], 𝑁[𝑡1,𝑡2])=
|𝐵𝐿[𝑡1,𝑡2]∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝐿[𝑡1,𝑡2]|
=
|𝐵𝑐∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝑐|+|𝐵𝑝|+|𝐵𝑛|+|𝐵𝑝∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝑐|+|𝐵𝑝|+|𝐵𝑛|+|𝐵𝑛∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝑐|+|𝐵𝑝|+|𝐵𝑛|
𝜌(𝐿[𝑡1,𝑡2], 𝑁[𝑡1,𝑡2])=
|𝐵𝐿[𝑡1,𝑡2]∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝑁[𝑡1,𝑡2]|
=
|𝐵𝑐∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝑁[𝑡1,𝑡2]|+|𝐵𝑝∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝑁[𝑡1,𝑡2]|+|𝐵𝑛∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝑁[𝑡1,𝑡2]|
We can hen p oceed o de ine he alues a e 𝑡2, whe e 𝐵𝑝has o ally disappea ed:
𝛾(𝐿>𝑡2, 𝑁[𝑡1,𝑡2])=
|𝐵𝐿>𝑡2∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝐿>𝑡2|=
|𝐵𝑐∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝑐|+|𝐵𝑛|+|𝐵𝑛∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝑐|+|𝐵𝑛|
𝜌(𝐿>𝑡2, 𝑁[𝑡1,𝑡2])=
|𝐵𝐿>𝑡2∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝑁[𝑡1,𝑡2]|=
|(𝐵𝑐∩𝐵𝑁[𝑡1,𝑡2])|
|𝐵𝑁[𝑡1,𝑡2]|+|𝐵𝑛∩𝐵𝑁[𝑡1,𝑡2]|
|𝐵𝑁[𝑡1,𝑡2]|
No hing canbe a i med wi h espec o i ness, bu wecanconclude ha
𝜌(𝐿[𝑡1,𝑡2], 𝑁[𝑡1,𝑡2])>
𝜌(𝐿>𝑡2, 𝑁[𝑡1,𝑡2]), i.e., p ecision will dec ease a he end o he g adual d i .
60
Chap e 4. G adual d i de ec ion
A si ua ion in which a g adual change s a s wi h a change in p ecision a
𝑡1
is
impossible, since he change in p ecision necessa ily implies a sudden change in he model
s uc u e. Since his p oo is s aigh o wa d, we did no include i in his disse a ion
—
𝐵𝑛=∅
, since no new beha io is added a e
𝑡1
, o he wise a change in i ness should be
p esen , and 𝐵𝐿<𝑡1=𝐵𝐿[𝑡1,𝑡2], which con adic s he De ini ion 9—. □
4.2 Algo i hm
The p emise unde lying he ope a ion o CRIER is ha , using i ness and p ecision me ics,
g adual d i s can be de ec ed wi h high accu acy. To be e unde s and how he algo i hm
wo ks, we illus a e he g adual d i de ec ion wi h he example o Figu e 4.1. The example
is based on a sliding window o size
4
. Fi s , aces a e ead un il he window is ull. Then,
aces om he i s ull window
𝜔4
a e mined wi h a disco e y algo i hm o ob ain he model
ha desc ibes i s beha io . Then, he window is shi ed ace by ace and o each shi he
i ness and p ecision —which a e ini ially 1— a e checked o de ec whe he hey change. In
he window
𝜔9
he i ness dec eases while he p ecision does no change, so
𝜏9
is labeled as a
d i candida e. The i ness dec ease las s o h ee windows, which means ha aces om
𝜏10
o
𝜏12
a e also d i candida es, so ace
𝜏9
is inally labeled as a d i . As a consequence, a new
model is disco e ed a
𝜔12
, s a ing a new cycle o he algo i hm, un il a change in i ness o
p ecision is de ec ed in he nex windows. In his example, a p ecision dec ease is de ec ed o
he windows
𝜔20
,
𝜔21
,
𝜔22
and
𝜔23
, con i ming a d i in ace
𝜏17
and, he e o e, a g adual
d i be ween aces 𝜏9and 𝜏17.
Algo i hm 4.1 shows he pseudocode o he CRIER algo i hm. The only manda o y inpu s
a e he e en log and a minimum window size. As pa o he ini ializa ion phase, he algo i hm
c ea es wo emp y lis s o he con i med d i s, one o sudden and one o g adual d i s (line 2)
and se s he ini ial window index
𝑖=1
(line 4). As he algo i hm is based on a sliding window
𝜔𝑖
(De ini ion 7), in his ini ializa ion phase i s op imal size
𝑛
is compu ed (line 3) using he
unc ion Adjus Window (Algo i hm 4.2, lines 1 o 15). The adjus men o he window size is
based on he compa ison o he beha iou obse ed in h ee consecu i e windows. In his s ep,
we s a wi h a size
𝑛′
ini ialized as he minimum window size
𝑛
and disco e h ee models
om h ee consecu i e windows o size
𝑛′
(Algo i hm 4.2, lines 5 o 7). I he h ee models
cap u e he same beha iou (Algo i hm 4.2, line 8), he size o each window
𝑛′
is inc emen ed
by
𝑛′
(Algo i hm 4.2, line 9) and he p ocess s a s again. The p ocedu e inishes when one o
61
Víc o José Gallego Fon enla
ID T ace Window Con o mance me ics Ac ions Model
𝜏1𝐴𝐵𝐶𝐷 𝜔1=⟨𝜏1⟩— Window is no ull. Read new ace
𝜏2𝐴𝐵𝐶𝐷 𝜔2=⟨𝜏1, 𝜏2⟩— Window is no ull. Read new ace
𝜏3𝐴𝐵𝐶𝐷 𝜔3=⟨𝜏1, 𝜏2, 𝜏3⟩— Window is no ull. Read new ace
𝜏4𝐴𝐵𝐶𝐷 𝜔4=⟨𝜏1, 𝜏2, 𝜏3, 𝜏4⟩𝛾(𝑁1, 𝜔4)=1.00
𝜌(𝑁1, 𝜔4)=1.00 Disco e model o 𝜔4𝑁1A B CD
𝜏5𝐴𝐵𝐶𝐷 𝜔5=⟨𝜏2, 𝜏3, 𝜏4, 𝜏5⟩𝛾(𝑁1, 𝜔5)=1.00
𝜌(𝑁1, 𝜔5)=1.00 No d i candida e de ec ed
𝜏6𝐴𝐵𝐶𝐷 𝜔6=⟨𝜏3, 𝜏4, 𝜏5, 𝜏6⟩𝛾(𝑁1, 𝜔6)=1.00
𝜌(𝑁1, 𝜔6)=1.00 No d i candida e de ec ed
𝜏7𝐴𝐵𝐶𝐷 𝜔7=⟨𝜏4, 𝜏5, 𝜏6, 𝜏7⟩𝛾(𝑁1, 𝜔7)=1.00
𝜌(𝑁1, 𝜔7)=1.00 No d i candida e de ec ed
𝜏8𝐴𝐵𝐶𝐷 𝜔8=⟨𝜏5, 𝜏6, 𝜏7, 𝜏8⟩𝛾(𝑁1, 𝜔8)=1.00
𝜌(𝑁1, 𝜔8)=1.00 No d i candida e de ec ed
𝜏9𝐴𝐵𝐷𝐶 𝜔9=⟨𝜏6, 𝜏7, 𝜏8, 𝜏9⟩𝛾(𝑁1, 𝜔9)=0.75
𝜌(𝑁1, 𝜔9)=1.00 D i candida e on 𝜔9(by i ness)
𝜏10 𝐴𝐵𝐶𝐷 𝜔10 =⟨𝜏7, 𝜏8, 𝜏9, 𝜏10⟩𝛾(𝑁1, 𝜔10)=0.75
𝜌(𝑁1, 𝜔10)=1.00 D i candida e on 𝜔10 (by i ness)
𝜏11 𝐴𝐵𝐷𝐶 𝜔11 =⟨𝜏8, 𝜏9, 𝜏10, 𝜏11 ⟩𝛾(𝑁1, 𝜔11)=0.50
𝜌(𝑁1, 𝜔11)=1.00 D i candida e on 𝜔11 (by i ness)
𝜏12 𝐴𝐵𝐶𝐷 𝜔12 =⟨𝜏9, 𝜏10, 𝜏11, 𝜏12⟩𝛾(𝑁1, 𝜔12)=0.50
𝜌(𝑁1, 𝜔12)=1.00
D i candida e on 𝜔12 (by i ness)
Con i m d i a 𝜏9(by i ness)
Disco e model o 𝜔12
𝑁2A B
C
D
𝜏13 𝐴𝐵𝐷𝐶 𝜔13 =⟨𝜏10, 𝜏11, 𝜏12, 𝜏13⟩𝛾(𝑁2, 𝜔13)=1.00
𝜌(𝑁2, 𝜔13)=1.00 No d i candida e de ec ed
𝜏14 𝐴𝐵𝐶𝐷 𝜔14 =⟨𝜏11, 𝜏12, 𝜏13, 𝜏14⟩𝛾(𝑁2, 𝜔14 )=1.00
𝜌(𝑁2, 𝜔14)=1.00 No d i candida e de ec ed
𝜏15 𝐴𝐵𝐷𝐶 𝜔15 =⟨𝜏12, 𝜏13, 𝜏14, 𝜏15⟩𝛾(𝑁2, 𝜔15)=1.00
𝜌(𝑁2, 𝜔15)=1.00 No d i candida e de ec ed
𝜏16 𝐴𝐵𝐶𝐷 𝜔16 =⟨𝜏13, 𝜏14, 𝜏15, 𝜏16⟩𝛾(𝑁2, 𝜔16 )=1.00
𝜌(𝑁2, 𝜔16)=1.00 No d i candida e de ec ed
𝜏17 𝐴𝐵𝐷𝐶 𝜔17 =⟨𝜏14, 𝜏15, 𝜏16, 𝜏17⟩𝛾(𝑁2, 𝜔17)=1.00
𝜌(𝑁2, 𝜔17)=1.00 No d i candida e de ec ed
𝜏18 𝐴𝐵𝐷𝐶 𝜔18 =⟨𝜏15, 𝜏16, 𝜏17, 𝜏18⟩𝛾(𝑁2, 𝜔18)=1.00
𝜌(𝑁2, 𝜔18)=1.00 No d i candida e de ec ed
𝜏19 𝐴𝐵𝐷𝐶 𝜔19 =⟨𝜏16, 𝜏17, 𝜏18, 𝜏19⟩𝛾(𝑁2, 𝜔19)=1.00
𝜌(𝑁2, 𝜔19)=1.00 No d i candida e de ec ed
𝜏20 𝐴𝐵𝐷𝐶 𝜔20 =⟨𝜏17, 𝜏18, 𝜏19, 𝜏20⟩𝛾(𝑁2, 𝜔20)=1.00
𝜌(𝑁2, 𝜔20)=0.66 D i candida e on 𝜔20 (by p ecision)
𝜏21 𝐴𝐵𝐷𝐶 𝜔21 =⟨𝜏18, 𝜏19, 𝜏20, 𝜏21⟩𝛾(𝑁2, 𝜔21)=1.00
𝜌(𝑁2, 𝜔21)=0.66 D i candida e on 𝜔21 (by p ecision)
𝜏22 𝐴𝐵𝐷𝐶 𝜔22 =⟨𝜏19, 𝜏20, 𝜏21, 𝜏22⟩𝛾(𝑁2, 𝜔22)=1.00
𝜌(𝑁2, 𝜔22)=0.66 D i candida e on 𝜔22 (by p ecision)
𝜏23 𝐴𝐵𝐷𝐶 𝜔23 =⟨𝜏20, 𝜏21, 𝜏22, 𝜏23⟩𝛾(𝑁2, 𝜔23)=1.00
𝜌(𝑁2, 𝜔23)=0.66
D i candida e on 𝜔23 (by p ecision)
Con i m d i a 𝜏17 (by p ecision)
Disco e model o 𝜔23
𝑁3A B D C
𝜏24 𝐴𝐵𝐷𝐶 𝜔24 =⟨𝜏21, 𝜏22, 𝜏23, 𝜏24⟩𝛾(𝑁3, 𝜔24)=1.00
𝜌(𝑁3, 𝜔24)=1.00 No d i candida e de ec ed
𝜏25 𝐴𝐵𝐷𝐶 𝜔25 =⟨𝜏22, 𝜏23, 𝜏24, 𝜏25⟩𝛾(𝑁3, 𝜔25)=1.00
𝜌(𝑁3, 𝜔25)=1.00 No d i candida e de ec ed
𝜏26 𝐴𝐵𝐷𝐶 𝜔26 =⟨𝜏23, 𝜏24, 𝜏25, 𝜏26⟩𝛾(𝑁3, 𝜔26)=1.00
𝜌(𝑁3, 𝜔26)=1.00 No d i candida e de ec ed
𝜏27 𝐴𝐵𝐷𝐶 𝜔27 =⟨𝜏24, 𝜏25, 𝜏26, 𝜏27⟩𝛾(𝑁3, 𝜔27)=1.00
𝜌(𝑁3, 𝜔27)=1.00 No d i candida e de ec ed
Figu e 4.1:
Example o a g adual change whe e some p e iously unobse ed beha io s a s o
eplace he p e ious one a 𝜏9, which is no longe obse ed a e ace 𝜏16.
62
Chap e 4. G adual d i de ec ion
he h ee models has a di e en beha io o when he condi ion
3∗𝑛′<|𝐿|
ails, meaning
ha i is no possible o disco e h ee consecu i e models, e u ning he las
𝑛′
as he adjus ed
op imal window size (Algo i hm 4.2, line 14).
Once he size is adjus ed, he window is popula ed wi h he i s
𝑛
emaining aces om
he ini ial index. Then, he i s p ocess model is disco e ed (line 6) using he con en om
his
𝜔𝑖
window. This model is s o ed in a lis
𝑁
which con ains he se o models ha will be
disco e ed o each de ec ed d i .
A e his ini ializa ion, he d i de ec ion s ep is execu ed (lines 8 o 42). This s ep is
composed o a loop ha epea s un il no aces emain unp ocessed in he log. Thus, as pa o
he ini ializa ion pe o med a e each change de ec ion, wo emp y lis s a e c ea ed (line 9),
Γ
and
𝑃
, o s o ing he i ness and p ecision, espec i ely. Also, wo mo e lis s,
𝐷Γ
and
𝐷𝑃
,
a e ini ialized (line 10). These lis s will la e be popula ed wi h booleans indica ing i he
successi e windows a e ma ked as d i candida es. Finally, a lag used o indica ing i a
change has been de ec ed is ini ialized (line 11).
Once his ini ializa ion is comple ed, he main de ec ion loop begins (lines 12 o 41), whe e
he de ec ion is pe o med based on he ends in he alues o he con o mance me ics. This
loop p ocesses he emaining windows, s a ing a index
𝑖
, un il a new change is de ec ed o o
he end o he log i no change is p esen (line 12). Fo each window
𝜔𝑖
he i ness and he
p ecision o he las disco e ed model
𝑁|𝑁|
a e compu ed, and hei alues a e appended o
Γ
and
𝑃
, espec i ely (lines 13 and 14). Then, using he unc ion Iden i yD i Candida e
om Algo i hm 4.2, he window
𝜔𝑖
is classi ied o no as a d i candida e (lines 15 o 16). To
ca y ou his classi ica ion s ep, a simple linea eg ession —using he o dina y leas squa es
me hod— is compu ed o e he me ic alues (Algo i hm 4.2, line 17). I he e a e enough
da a o compu ing he eg ession and he slope o he i ed line is di e en om 0 wi h
enough s a is ical con idence —
𝑝- alue <0.05
in he
𝑡- es
, whe e
𝐻0
s a es ha he slope o
he eg ession is 0—, o he slope is 0 and he p e ious window has been ma ked as a d i
candida e, he window
𝜔𝑖
will be ma ked as a d i candida e. To inalize his de ec ion s ep he
unc ion Con i mD i om Algo i hm 4.2 is execu ed (line 29). This unc ion is in cha ge
o checking whe he a d i candida e pe sis s o e ime, becoming a eal change, o , on he
con a y, only ep esen s a noisy ace. A d i candida e is con i med as a eal change i he
las 𝑛windows ha e been also ma ked as d i candida es (Algo i hm 4.2, lines 23 o 26).
Once he change is con i med, i should be pinpoin ed in ime o an speci ic ace. In case
he d i comes om a change in i ness, he ace causing he d i is he las ace om he
63

Víc o José Gallego Fon enla
Algo i hm 4.1 CRIER (Con o mance-based GRadual D I De Ec ion AlgoRi hm)
Inpu s: an e en log 𝐿, minimum size o he sliding window 𝑛′
Ou pu s: a se o aces/segmen s o he log causing d i s
1: p ocedu e Concep D i De ec ion(𝐿, 𝑛′)
2: D𝑆,D𝐺← [ ] //con i med sudden and g adual d i s
3: n←Adjus Window(𝑛′,⟨𝜏1, . . . , 𝜏|𝐿|⟩)
4: 𝑖←𝑛
5: 𝜔𝑖← ⟨𝜏𝑖−𝑛, . . . , 𝜏𝑖⟩
6: N← [𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (𝜔𝑖)] //sa e he model in he model his o y
7: 𝜏∗, 𝜏′←𝜏1
8: while 𝑖 < |𝐿|do
9: Γ,P← [ ] // i ness and p ecision measu es (De ini ions 5 and 6)
10: DΓ,DP← [ ] //d i candida es ( i ness and p ecision)
11: 𝑓 𝑙𝑎𝑔 ←𝐹 𝐴𝐿𝑆𝐸
12: while (𝑖 < |𝐿|) ∧ ¬ 𝑓 𝑙𝑎𝑔 do
13: Γ←Γ:: 𝛾(𝜔𝑖, 𝑁|𝑁|)//append cu en i ness
14: P←P:: 𝜌(𝜔𝑖, 𝑁|𝑁|)//append cu en p ecision
15: DΓ←DΓ:: Iden i yD i Candida e(n,Γ,DΓ)
16: DP←DP:: Iden i yD i Candida e(n,P,DP)
17: i Con i mD i (n,DΓ)∨Con i mD i (n,DP) hen//change con i med
18: i Con i mD i (n,DΓ) hen
19: 𝜏∗←𝜏𝑖−𝑛//con i med d i in he las ace om he i s candida e
20: else i Con i mD i (n,DP) hen
21: 𝜏∗←𝜏𝑖−2𝑛//con i med d i in he i s ace om he i s candida e
22: end i
23: 𝑓 𝑙𝑎𝑔 ←𝑇𝑅𝑈𝐸
24: 𝐿′← ⟨𝜏′, . . . , 𝜏∗⟩//s o e he sublog be ween con i med d i s
25: n←Adjus Window(𝑛′,⟨𝜏𝑖+1, . . . , 𝜏|𝐿|⟩)
26: 𝑖←𝑖+𝑛
27: 𝜔𝑖← ⟨𝜏𝑖−𝑛, . . . , 𝜏𝑖⟩
28: N←N:: 𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (𝜔𝑖)//append cu en model o model his o y
29: i |𝑁|>2∧ (∃𝜏∈𝐿′:𝐵𝜏∈𝐵𝑁|𝑁|−2)∧
(∃𝜏∈𝐿′:𝐵𝜏∈𝐵𝑁|𝑁|) ∧ (∀𝜏∈𝐿′:𝐵𝜏∈𝐵𝑁|𝑁|−2∪𝐵𝑁|𝑁|) hen
30: 𝜏′←𝐷𝑆|𝐷𝑆|
31: D𝑆← {𝑑∈D𝑆:𝑑≠𝜏′}
32: D𝐺←D𝐺:: [𝜏′, 𝜏∗)//a g adual change
33: else
34: D𝑆←D𝑆:: 𝜏∗//a sudden change
35: end i
36: 𝜏′←𝜏∗
37: else
38: 𝑖←𝑖+1
39: 𝜔𝑖← ⟨𝜏𝑖−𝑛, . . . , 𝜏𝑖⟩
40: end i
41: end while
42: end while
43: e u n D𝑆∪D𝐺
44: end p ocedu e
64
Chap e 4. G adual d i de ec ion
Algo i hm 4.2 Auxilia y unc ions
1: unc ion Adjus Window(𝑛, 𝐿)
2: 𝑁1, 𝑁2, 𝑁3← ∅
3: 𝑛′←𝑛
4: while 3𝑛 < |𝐿|do
5: 𝑁1←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (⟨𝜏0, . . . , 𝜏𝑛′⟩)
6: 𝑁2←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (⟨𝜏𝑛′, . . . , 𝜏2𝑛′⟩)
7: 𝑁3←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (⟨𝜏2𝑛′, . . . , 𝜏3𝑛′⟩)
8: i 𝐵𝑁1=𝐵𝑁2=𝐵𝑁3 hen
9: 𝑛′←𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡 (𝑛′)
10: else
11: e u n 𝑛′
12: end i
13: end while
14: e u n 𝑛′
15: end unc ion
16: unc ion Iden i yD i Candida e(n, 𝑑𝑎𝑡𝑎, D)
17: Υ←𝑟𝑒𝑔𝑟𝑒𝑠𝑠 ({𝑑𝑎𝑡𝑎|𝑑𝑎𝑡𝑎|−n, . . . , 𝑑𝑎𝑡𝑎|𝑑𝑎𝑡𝑎|})
18: 𝑚<←Υ.slope <0∧Υ.con idence <0.05
19: 𝑚>←Υ.slope >0∧Υ.con idence <0.05
20: 𝑚=← (¬ 𝑚<) ∧ (¬ 𝑚>)
21: e u n (|𝑑𝑎𝑡𝑎|>n) ∧ (𝑚<∨𝑚>∨ (𝑚=∧ (D|D|=𝑡𝑟𝑢𝑒)))
22: end unc ion
23: unc ion Con i mD i (n,D)
24: 𝑑′← ∀𝑑∈ {D|D|−n, . . . , D|D|}:𝑑=𝑡𝑟𝑢𝑒
25: e u n (|D|⩾n) ∧ 𝑑′
26: end unc ion
i s window iden i ied as a candida e —i.e., he i s ace causing a change in he me ic—.
In he case o a change in p ecision, he ace causing he d i is he i s ace om he i s
window iden i ied as candida e —i.e., he i s ace om he i s window causing a change
in p ecision—. Then, he lag indica ing a de ec ion is upda ed (line 23) and he sublog
𝐿′
be ween con i med d i s is s o ed o la e . The d i mus hen be classi ied as sudden o
g adual. Figu e 4.2 illus a es his pa o he algo i hm. The i s s ep is o upda e bo h he
index a which he nex window will s a and i s op imal size (lines 25 and 26). Then, he
new window is popula ed wi h he aces and he model desc ibing he beha io con ained in
his window is disco e ed (lines 27 and 28). This model is s o ed in he model lis . Since
g adual changes a e delimi ed by wo d i s, he las h ee models o his lis —
𝑁|𝑁|−2
,
𝑁|𝑁|−1
,
and
𝑁|𝑁|
— a e used o check he condi ions ha de e mine whe he he d i is g adual o no .
No e ha he model
𝑁|𝑁|−1
co esponds wi h he sublog in which he con i med d i has been
de ec ed. These condi ions a e he ollowing (line 29):
65
Víc o José Gallego Fon enla
𝑡1𝑡2
𝜏′𝜏∗
𝜏𝑖𝜏𝑖+𝑛
𝑁|𝑁|−2𝑁|𝑁|−1𝑁|𝑁|
𝐿′𝜔𝑖+𝑛
A B CDA B
C
D
A B D C
Figu e 4.2: D i classi ica ion phase in CRIER.
1. The e a e mo e han wo models in he model lis (|𝑁|>2).
2. A leas , one ace om 𝐿′is suppo ed by 𝑁|𝑁|.
3. A leas , one ace om 𝐿′is suppo ed by 𝑁|𝑁|−2.
4. The beha iou om e e y ace in 𝐿′is pa o he beha iou o 𝑁|𝑁|−2o 𝑁|𝑁|.
I
𝐿′
ul ills hese ou equi emen s, he change is classi ied as g adual, indica ing ha he
d i s a s a he ace whe e he las sudden d i
𝐷𝑆|𝐷𝑆|
was de ec ed and las s un il
𝜏∗
.
Fu he mo e,
𝐷𝑆|𝐷𝑆|
is emo ed om he sudden d i lis (line 31), and appended o he lis
DΓ
o classi ied d i s (line 32). On he o he hand, i he candida e canno be classi ied as
g adual because i does no mee any o he equi emen s, he change a
𝜏∗
is classi ied as
sudden (line 34). Finally, he index
𝑖
is inc emen ed by 1 (line 38), he sliding window is
upda ed o his index (line 39), and he cycle s a s again.
4.3 Expe imen a ion
To e alua e he quali y o he esul s ob ained by CRIER agains hose o he s a e o he a
app oaches, we use he same me ics ha we used in Chap e 3. On he one hand,
𝐹𝑠𝑐𝑜𝑟𝑒
, which
is calcula ed as he ha monic mean be ween p ecision and ecall, and e alua es how eliable
he esul s a e, based on he numbe o ue/ alse posi i es and nega i es (Equa ion (3.2a)).
Fo g adual changes, a ue posi i e (
𝑇𝑃
) is any change whose de ec ion a ea o e laps wi h a
eal change no p e iously de ec ed, while a alse posi i e (
𝐹𝑃
) is any change ha does no
co espond o a egion o eal change, o ha ma ches a egion o change p e iously de ec ed.
In addi ion, a alse nega i e (
𝐹𝑁
) is a egion o change ha does no o e lap wi h anyone o he
de ec ed changes. On he o he hand,
Δ
, which measu es how la e a d i is epo ed om he
66
Chap e 4. G adual d i de ec ion
𝜏0𝜏5𝜏10 𝜏15 𝜏20 𝜏25 𝜏30 𝜏35 𝜏40 𝜏45 𝜏50
FP TP FN
Δ Υ
Real d i s
De ec ed d i s
Figu e 4.3:
Example o classi ica ion o esul s o e a log wi h wo g adual changes. Uppe imeline
shows he eal d i egions, ma ked in g een. Lowe imeline shows de ec ed d i
egions, ma ked in o ange.
ac ual occu ence un il i s de ec ion. In he case o g adual changes, since we a e dealing wi h
a eas o change ins ead o single poin s, we measu e he delay in de ec ing he beginning o he
egion:
Δ(𝑑𝑅, 𝑑𝐷)=|min(𝑑𝑅) − min(𝑑𝐷)| (4.1)
whe e 𝑑𝑅and 𝑑𝐷a e in e als indica ing a eal and a de ec ed d i egion, espec i ely.
Addi ionally, and o be e e lec he goodness o he esul s when dealing wi h g adual
changes, hese wo me ics a e complemen ed wi h a hi d one: he change egion o e lapping
(
Υ
). This me ic e alua es he pe cen age o he ac ual egion o change ha has been de ec ed
by he algo i hm, e lec ing how well he du a ion o he changes is cap u ed:
Υ(𝑑𝑅, 𝑑𝐷)=|𝑑𝑅∩𝑑𝐷|
|𝑑𝑅|(4.2)
whe e 𝑑𝑅and 𝑑𝐷a e in e als indica ing a eal and a de ec ed d i egion, espec i ely.
Figu e 4.3 shows an example o how hese me ics a e applied in he e alua ion o he
esul s. This example p esen s a log wi h wo g adual changes, one be ween aces
𝜏10
and
𝜏20
, and he o he one be ween aces
𝜏35
and
𝜏45
. The algo i hm de ec s wo changes, one
be ween aces
𝜏4
and
𝜏7
, classi ied as a alse posi i e as no eal change happened in his ime
in e al, and one be ween aces
𝜏17
and
𝜏23
, classi ied as a ue posi i e because i o e laps a
eal change. In his second de ec ion, he delay would be
7
aces — om ace
𝜏10
o ace
𝜏17
—. On he o he hand, he change egion o e lapping would be
30%
, since only
3
aces ou
o he
10
ha cons i u e he egion o change a e de ec ed. Finally, he second change, be ween
aces
𝜏35
and
𝜏45
, will be classi ied as a alse nega i e, since he algo i hm has no de ec ed
any change in ha egion.
4.3.1 Valida ion da a
Concep d i algo i hms a e alida ed wi h syn he ic da a gene a ed om eal p ocesses, in
which changes a e in oduced a a speci ic momen and wi h a speci ic du a ion, since he e
67
Víc o José Gallego Fon enla
a e a he beginning o a he end o he change. Consequen ly, CRIER ob ains high delays in
de ec ing he s a o he change, and p ema u e de ec ions a he end o he change, ha ing a
high numbe o alse posi i es ha lead o a dec ease in accu acy. Pa icula ly in e es ing a e
he logs wi h slowes changes —
0.1%
slope, i.e.,
1,000
- ace change egions—, whe e P oD i
ob ains he bes
𝐹𝑠𝑐𝑜𝑟𝑒
in
6
ou o
10
logs. Fo hese
6
logs, CRIER de ec s a lowe change
egion o e lapping, bu ob ains he bes esul s in e ms o
Δ
, which ein o ces he idea ha he
de ec ion e o s a e due o alse posi i es in de e mining he end o he change. Howe e , wi h
espec o he a e age alues o he me ics, CRIER is he bes posi ioned since P oD i is no
able o de ec any change in
3
o he logs, while Ma jushe e al. ob ains many alse posi i es,
de ec ing less han 18% o he aces as a egion o change.
In he emaining linea logs, he esul s o P oD i su e a signi ican deg ada ion, de ec ing
changes only in 2 o 20 logs wi h a g ea e slope han 0.1%, in which i ob ains 𝐹𝑠𝑐𝑜𝑟𝑒 alues
o 0.5 o less, and Δo mo e han 400 aces. This deg ada ion may be due o he ac ha , as
changes a e much as e , he algo i hm does no ha e enough in o ma ion o co ec ly ex ac he
dis ibu ion o pa ially-o de ed- uns be o e and a e he change, no being able o co ec ly
de ec he d i s.
In logs wi h Gaussian dis ibu ions, he esul s ob ained by CRIER a e clea ly be e han
hose o Ma jushe e al., wi h
𝐹𝑠𝑐𝑜𝑟𝑒
o
1.0
in
17
o
20
logs. These logs a e cha ac e ized by
ela i ely as changes, bu wi h bo h a slow s a and e mina ion. The esul s a e consis en
wi h wha was p e iously es ablished o he linea changes: as hese a e ela i ely as changes
—sligh ly mo e han 150 aces in he slowes case— he slope o he eg ession changes
ab up ly, acili a ing he de ec ion o changes. The alues o
Δ
and
Υ
ob ained by Ma jushe
e al. a e pa icula ly indica i e. The slow s a and e mina ion o he new beha io lead o
smalle changes in he dis ibu ions o he ea u es, making he s a is ical es employed by his
app oach unable o de ec he d i s and causing he beginning o he changes o be de ec ed
la e —inc easing
Δ
alues— while hei e mina ion is de ec ed p ema u ely — esul ing in low
Υ alues—.
Some hing simila happens o logs wi h cons an dis ibu ion. In his case, CRIER ob ains
he bes esul s, wi h a pe ec a e age
𝐹𝑠𝑐𝑜𝑟𝑒
and an a e age
Υ
o a ound
90%
. This is
because, as soon as he change s a s, hal o he obse ed beha io is pa o he new model.
Consequen ly, con o mance me ics change e y as , which means ha he slope o he
eg ession is signi ican ly modi ied and changes a e de ec ed almos ins an ly. Fo Ma jushe
e al., he e a e se e al logs in which no change is de ec ed —
p
and
sw
o all cumula i e
74

Chap e 4. G adual d i de ec ion
p obabili y unc ions—. The poo pe o mance o his algo i hm o he same change pa e ns
may be caused by he selec ed ea u es since hey a e no able o cap u e such changes. Pe haps
selec ing o he ea u es ha migh be mo e sensi i e o his ype o changes would imp o e he
esul s, howe e a mo e in-dep h analysis should be pe o med o con i m his in ui ion.
Finally, o logs wi h exponen ial changes, he esul s o CRIER a e qui e deg aded when
compa ed o he o he dis ibu ions. These esul s a e due o wo dis inc si ua ions: on he one
hand, in logs wi h
𝜆=0.5
, changes a e so as —only
14
aces— ha CRIER is no able o
de ec hem as g adual, leading o alse nega i es; and, on he o he hand, in logs wi h
𝜆=0.05
,
changes ha e such long ails ha hey a e e mina ed p ema u ely, and consequen ly, a high
numbe o alse posi i es a e de ec ed in aces ha belong o he ac ual change bu ha e no
been de ec ed as pa o he d i . This beha io o he algo i hm is e lec ed by he alues o
Δ
and
Υ
. As seen in he esul s, all changes a e de ec ed e y close whe e hey begin —wi h
Δ
below
10
aces in almos all cases—, bu
Υ
alues emain a ound
20%
, indica ing ha only
he ini ial pa o he change egion is de ec ed. In addi ion, logs in which CRIER ob ains he
lowes Υcoincide wi h hose wi h he wo s 𝐹𝑠𝑐𝑜𝑟𝑒, con i ming his hypo hesis.
4.4 Conclusions
In his chap e , we p esen ed CRIER, an o line g adual-d i de ec ion algo i hm. CRIER is
based on he hypo hesis ha change de ec ion and classi ica ion can be add essed by analyzing
how he i ness and p ecision o he p ocess models — he old model and he new one a e he
change— a y om he beginning o he end o he g adual change. Speci ically, he hypo hesis
is ha a he beginning he e is a modi ica ion o he i ness, keeping he p ecision; while a he
end he p ecision changes. This hypo hesis has been ma hema ically demons a ed.
The app oach has been alida ed using a syn he ic da ase wi h
120
logs ha p esen
di e en change pa e ns and g adual change dis ibu ions, om linea o Gaussian, exponen ial
and cons an . The expe imen s show ha CRIER ou pe o ms he esul s o he main s a e
o he a app oaches in e ms o accu acy (
𝐹𝑠𝑐𝑜𝑟𝑒
); delay (
Δ
), so d i s a e de ec ed as e ;
and change egion o e lapping (
Υ
), so he ime in e al du ing which wo p ocesses coexis is
clea ly iden i ied.
Fu he mo e, CRIER is mo e obus o all ypes o change dis ibu ions and pa icula ly
be e o hose in which he aces o he new model s a o a ise wi h a highe equency a
he beginning o he g adual d i , such as Gaussian, exponen ial, and cons an dis ibu ions.
75
Víc o José Gallego Fon enla
None heless, ou app oach has p o en o be mo e consis en e en when he o me condi ions
a e no p esen such as when he d i ollows a linea dis ibu ion wi h a low slope, being able
o de ec all he change pa e ns wi h less delay Δand be e Υ.
76
CHAPTER 5
ROBUST DRIFT DETECTION
I shall ei he ind a way o make one.
— Hannibal
In he p e ious chap e s, we p esen ed wo app oaches —C2D2 and CRIER— o de ec ing
sudden and g adual d i s wi h high eliabili y. These app oaches moni o he beha io o
i ness and p ecision me ics o e he en i e log o de ec changes in he p ocess con ol- low.
By de ec ing when he me ics de ia e om hei ini ial alue, bo h C2D2 and CRIER can
de ec he p esence o changes in non-noisy e en logs.
Howe e , in eal-wo ld scena ios, anomalous execu ions can occu spon aneously wi hou
ep esen ing a change ha pe sis s o e ime. The e o e, i is necessa y o adap he de eloped
algo i hms o p o ide obus solu ions o noisy en i onmen s, which a e common in eal
scena ios. The obus e sion o hese algo i hms should be able o disc imina e noise om
eal d i s ha pe sis o e ime, educing he numbe o alse posi i es.
In Figu e 5.1, an example o i ness beha io is p esen ed in bo h a noisy and non-noisy
en i onmen . When no noise is p esen , he me ic alue emains a a cons an alue —in his
case, 1.0—, and dec eases when a change occu s. This makes i possible o de ec d i s by
iden i ying dec eases in he me ic alue. Howe e , in p esence o noise, he me ic luc ua es
a ound a ce ain alue —app oxima ely 0.75 in he example—, wi hou showing signi ican
d ops un il a change occu s.
Víc o José Gallego Fon enla
0 200 400 600 800 1,000 1,200 1,400 1,600 1,800 2,000 2,200 2,400
0
0.5
1
Non-noisy en i onmen
0 200 400 600 800 1,000 1,200 1,400 1,600 1,800 2,000 2,200 2,400
0
0.5
1
Noisy en i onmen
0 200 400 600 800 1,000 1,200 1,400 1,600 1,800 2,000 2,200 2,400
0
0.5
1
Non-noisy en i onmen
0 200 400 600 800 1,000 1,200 1,400 1,600 1,800 2,000 2,200 2,400
0
0.5
1
Noisy en i onmen
0 200 400 600 800 1,000 1,200 1,400 1,600 1,800 2,000 2,200 2,400
0
0.5
1
Non-noisy en i onmen
0 200 400 600 800 1,000 1,200 1,400 1,600 1,800 2,000 2,200 2,400
0
0.5
1
Noisy en i onmen
Figu e 5.1: Fi ness and p ecision beha iou in noisy and non-noisy en i onmen s.
In he p esence o noise, hese luc ua ions can esul in alse posi i e de ec ions when
anomalous execu ions occu , unless hey a e di e en ia ed om he signi ican d ops ha occu
in he case o eal changes, hus in alida ing he esul . Fu he mo e, we canno de e mine
he magni ude o he d ops a p io i, as i depends on he change and he s uc u e o he
p ocess being execu ed. The e o e, in o de o de ec changes in noisy en i onmen s, ou
in ui ion ells us ha i is neccessa y o de ec mul iple consecu i e d ops in he me ic, wi h
no in e media e inc eases in he alue, a e necessa y. I he d op pe sis s su icien ly o e
ime, we can disc imina e i om luc ua ions caused by anomalous execu ions, enabling us o
dis inguish be ween a eal change and noise.
Based on his p emise, his chap e in oduces Robus CRIER (R-CRIER), he obus e sion
o CRIER adap ed o execu ion in bo h noisy and non-noisy en i onmen s.
5.1 Robus d i de ec ion using con o mance me ics
In p e ious chap e s, we showed ha changes in he p ocess con ol- low can be de ec ed by
moni o ing hei con o mance me ics. Also, we used simple linea eg essions o moni o
hose con o mance me ics, de ec ing a d i when he slope o he eg ession alls, meaning
ha he me ic alues a e dec easing. Howe e , in noisy en i onmen s, a d op in one o he
me ics may be caused by ansien anomalies ha do no ep esen a eal d i . In his sec ion,
we will demons a e ha successi e d ops in he eg ession slope can enable obus de ec ion
o changes, e en in noisy en i onmen s, by sepa a ing alls de i ed om anomalous execu ions
om hose caused by eal d i s.
78
Chap e 5. Robus d i de ec ion
Theo em 5.1: When de ec ing changes in noisy en i onmen s, wai ing n/2 nega i e
slopes o he simple linea eg ession allows o di e encia e d ops due o noisy
execu ions om hose due o eal d i s.
P oo : To demons a e his, le s ake he o mula o calcula ing he slope o
Υ
using he
leas squa es me hod [77]:
Υ.slope =Í𝑛
𝑖=1(𝑥𝑖−𝑥)(𝑦𝑖−𝑦)
Í𝑛
𝑖=1(𝑥𝑖−𝑥)2,
being
𝑥
and
𝑦
he mean alues o
𝑥
and
𝑦
, espec i ely. As
𝑥
is he index o he window
o which he con o mance me ic has been measu ed, we can eplace i by he a i hme ic
p og ession 1..𝑛, so we can eplace in he equa ion:
Υ.slope =Í𝑛
𝑖=1𝑖−1+𝑛
2(𝑦𝑖−𝑦)
Í𝑛
𝑖=1𝑖−1+𝑛
22.
On he o he hand,
𝑦
con ains he alues o he con o mance me ics o each window.
No e ha he ollowing is alid o bo h i ness and p ecision. When a noisy execu ion
en e s he window
𝜔𝑖(𝐿, 𝑛)
, he me ic alue will dec ease, and s ay a ha alue un il
he noisy execu ion disappea s a window
𝜔𝑖+𝑛(𝐿, 𝑛)
—we will ha e only a ace wi h he
i ing/non- i ing beha iou , ega dless o i s posi ion in he window lengh —. Thus, o a
gi en window, he e will be
𝑘
measu emen s wi h alue
𝑐
a he beggining o he window
and 𝑛−𝑘measu emen s wi h alue 𝑐′a he end, being 𝑐 > 𝑐′, so we can ew i e 𝑦as:
𝑦=𝑘𝑐 + (𝑛−𝑘)𝑐′
𝑛.
Then, we can ew i e he slope as he ollowing o mula, whe e
𝑘
is he numbe o
successi e measu emen s wi hou noise coun ed om he begginning o he window:
𝑓(𝑘)=Í𝑘
𝑖=1𝑖−1+𝑛
2𝑐−𝑘𝑐+(𝑛−𝑘)𝑐′
𝑛+Í𝑛
𝑖=𝑘+1𝑖−1+𝑛
2𝑐′−𝑘𝑐+(𝑛−𝑘)𝑐′
𝑛
Í𝑛
𝑖=1𝑖−1+𝑛
22.
79

Víc o José Gallego Fon enla
02468 10 12 14 16 18 20
−0.04
−0.02
0
𝑘
Slope
𝑐=1.00 𝑐′=0.95
𝑐=1.00 𝑐′=0.90
𝑐=0.90 𝑐′=0.70
𝑐=1.00 𝑐′=0.50
Figu e 5.2:
Example o he e olu ion o he slope in a noisy en i onmen o
𝑛=20
, and mul iple
𝑐
and 𝑐′ alues.
Compu ing he i s and second de i a i e o e 𝑘 o ind he c i ical poin s, we ge :
𝑓′(𝑘)=6(𝑐−𝑐′)(2𝑘−𝑛)
𝑛(𝑛2+2)𝑓′′ (𝑘)=12𝑐−12𝑐′
𝑛3+2𝑛
We know ha
𝑐 > 𝑐′⩾0; 𝑛, 𝑘 ∈N;𝑛 > 𝑘
, so
𝑓′(𝑘)=0=⇒𝑘=𝑛/2
and
𝑓′′ (𝑘)>0∀𝑘, i.e., 𝑓(𝑘)has a minimum on 𝑘=𝑛/2.
On he con a y, i is s aigh o wa d o demons a e ha , when ha ing a eal d i ,
wi h he alues om he me ic dec easing s eadily —as we ha e one mo e ace ha does
i /no i he model on each i e a ion—, he eg ession slope will dec ease con inually
wi hou p esen ing any c i ical poin . □
This beha io is shown in he example om Figu e 5.2. He e,
𝑛=20
, and we show he
beha iou o some alues o
𝑐
and
𝑐′
. When
𝑘
inc eases—i.e., when he occu ences o
𝑐′
inc eases a he cos o dec easing he numbe o occu ences o
𝑐
—, he eg ession slope also
dec eases, eaching a minumum in
𝑘=10
, no ma e he speci ic alues
𝑐
and
𝑐′
ge . F om he e
onwa ds, he slope is s ill nega i e, bu i s alues inc ease wi h 𝑘un il eaching 0.0 a 𝑘=20.
5.2 Algo i hm
Algo i hm 5.1 shows he pseudocode o R-CRIER, he algo i hm o obus ly de ec ing p ocess
con ol- low d i s, ensu ing eliable esul s e en in noisy en i onmen s. R-CRIER con inuously
moni o s p ocess con o mance me ics o e ime, looking o a ia ions ha pe sis and ha
may indica e a change in he p ocess. The algo i hm u ilizes a sliding window ha mo es o e
he en i e log and calcula es i ness and p ecision me ics o each window o examine hei
e olu ion o e ime. R-CRIER akes h ee inpu s: an e en log
𝐿
, a window size
𝑛
, and an
80
Chap e 5. Robus d i de ec ion
Algo i hm 5.1 R-CRIER
Inpu s: an e en log 𝐿, size o he sliding window 𝑛, es ima ion o he noise p obabili y 𝑟
Ou pu s: a se o aces/segmen s o he log causing d i s
1: p ocedu e Concep D i De ec ion(𝐿, 𝑛, 𝑟)
2: L,N← [ ] //lis o sublogs be ween d i s and he espec i e models
3: 𝑖←𝑛
4: 𝑙𝑎𝑠𝑡 ←0
5: while 𝑖 < |𝐿|do
6: Γ,P← [ ] //lis o i ness and p ecision measu es (De ini ions 5 and 6)
7: ΥΓ,ΥP← [ ] //lis o eg essions o i ness and p ecision
8: N←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (𝜔𝑖(𝐿, 𝑛))
9: N←N:: 𝑁//sa e cu en model in he models lis
10: 𝑏𝑟𝑒𝑎𝑘 ←FALSE
11: while 𝑖 < |𝐿| ∧ ¬𝑏𝑟𝑒𝑎𝑘 do
12: Γ←Γ:: 𝛾(𝜔𝑖(𝐿, 𝑛), 𝑁 )//append cu en i ness
13: P←P :: 𝜌(𝜔𝑖(𝐿, 𝑛), 𝑁 )//append cu en p ecision
14: i (|Γ|⩾𝑛) ∧ (|P|⩾𝑛) hen //enough measu emen s
15: ΥΓ←ΥΓ:: 𝑟𝑒𝑔𝑟𝑒𝑠𝑠 (𝑡𝑎𝑖𝑙 (Γ, 𝑛)) //sa e eg ession o e las n measu emen s
16: ΥP←ΥP:: 𝑟𝑒𝑔𝑟𝑒𝑠𝑠 (𝑡𝑎𝑖𝑙 (P, 𝑛)) //sa e eg ession o e las n measu emen s
17: end i
18: i (|ΥΓ|⩾𝑛/2) ∧ HasD i (𝑡𝑎𝑖𝑙(ΥΓ, 𝑛/2)) hen // i ness d i con i med
19: 𝑏𝑟𝑒𝑎𝑘 ←TRUE
20: L←L:: [𝜏𝑙𝑎𝑠𝑡 , . . . , 𝜏𝑖−(𝑛/2)]//sa e he sublog be ween d i s
21: 𝑙𝑎𝑠𝑡 ← (𝑖−𝑛/2)
22: else i (|ΥP|⩾𝑛/2) ∧ HasD i (𝑡𝑎𝑖𝑙 (ΥP, 𝑛/2)) hen //p ecision d i con i med
23: 𝑏𝑟𝑒𝑎𝑘 ←TRUE
24: L←L:: [𝜏𝑙𝑎𝑠𝑡 , . . . , 𝜏𝑖−𝑛]//sa e he sublog be ween d i s
25: 𝑙𝑎𝑠𝑡 ← (𝑖−𝑛)
26: end i
27: 𝑖←𝑖+1
28: end while
29: end while
30: L←L:: [𝜏𝑙𝑎𝑠𝑡 , . . . , 𝜏𝑖]//sa e he las sublog
31: e u n Classi yD i s(L,N, 𝑟 )//classi y he d i s
32: end p ocedu e
33: unc ion HasD i (Υ)
34: e u n ∀Υ𝑖∈Υ→ (Υ𝑖.slope <0)∧(Υ𝑖.con idence <0.05) ∧ (|Υ𝑖.slope|⩽|Υ𝑖+1.slope|)
35: end unc ion
es ima ion o he amoun o noise p esen in he log
𝑟
. I p oduces a lis o aces o sublogs
om he inpu log ha cause sudden o g adual d i s, espec i ely.
The algo i hm begins by c ea ing wo lis s,
L
and
N
, which will be used o s o e he sublogs
be ween changes and he p ocess models o each sublog, espec i ely (line 2). Nex , i se s he
index o he i s window o be p ocessed as he size o he window (line 3), which includes he
i s
𝑛
aces om he log. Addi ionally, i ini ializes a a iable o keep ack o he posi ion o
81
Víc o José Gallego Fon enla
he las de ec ed d i o 0 (line 4).
The main de ec ion loop, which uns om lines 5 o 29, i e a es o e he log un il all
aces ha e been p ocessed. A he s a o he loop, wo lis s,
Γ
and
P
, a e ini ialized o s o e
his o ical i ness and p ecision measu emen s, espec i ely (line 6). Addi ionally, wo lis s,
ΥΓ
and
ΥP
, a e ini ialized (line 7) o main ain a eco d o eg essions o e he i ness and p ecision
measu emen s, espec i ely. These lis s a e essen ial o de ec ing and con i ming d i s in he
p ocess con ol- low.
Nex , he loop disco e s a p ocess model using a noise- obus disco e y algo i hm applied
o he aces in he
𝜔𝑖(𝐿, 𝑛)
window, whe e
𝐿
is he log, and
𝑛
is he size o he window o
he i- h i e a ion (line 8). The algo i hm used in his case is he Induc i e Mine - in equen
algo i hm (
𝐼𝑀𝐹
) [
78
].
𝐼𝑀𝐹
is an adap ed e sion o he o iginal Induc i e Mine [
23
] ha
includes addi ional il e ing s eps o emo e de ia ing and in equen beha io o p oduce mo e
p ecise models. A e disco e ing he p ocess model, i is s o ed in he lis o p ocess models,
N(line 9), and a lag is ini ialized o alse (line 10) o b eak ou o he nex loop i necessa y.
Once he ini ial se up is comple e, he algo i hm en e s an inne loop ha i e a es o e he
emaining aces un il a change is de ec ed o he e a e no mo e unp ocessed aces (lines 11
o 28). Wi hin his loop, he i ness and p ecision alues o each emaining window a e
compu ed and added o he p e iously de ined lis s (lines 12 and 13). I a leas
𝑛
measu emen s
o he con o mance me ics ha e been compu ed (lines 14 o 17), a simple linea eg ession is
pe o med o e he las
𝑛
elemen s o bo h i ness and p ecision measu emen s, and he esul s
a e s o ed in he designa ed lis s (lines 15 and 16).
Nex , he algo i hm checks o he p esence o d i s in he compu ed eg essions (lines 18
o 26). This in ol es i s ensu ing ha enough eg essions ha e been compu ed —a leas
𝑛/2
eg essions a e equi ed, as explained in sec ion 5.1—. The algo i hm hen de e mines i he
las
𝑛/2
eg essions show a d i using he HasD i unc ion (lines 33 o 35). To con i m a
d i in he me ics, he las
𝑛/2
eg essions mus exhibi a nega i e slope wi h a con idence
o he slope being equal o
0.0
below
0.05
, and he magni ude o he slopes o he successi e
eg essions should be s eadily inc easing (line 34).
I a d i is de ec ed, he algo i hm se s he lag o b eak he inne loop (lines 19 and 23),
adds a new sublog be ween changes o he lis
L
(lines 20 and 24), and s o es he loca ion o he
las de ec ed d i in he a iable
𝑙𝑎𝑠𝑡
(lines 21 and 25). I is impo an o di e en ia e be ween
i ness-caused and p ecision-caused d i s o calcula e he d i index. This is because o he
di e en beha io o he wo me ics when a change is p esen . In he case o i ness, when he
82
Chap e 5. Robus d i de ec ion
i s d i ing ace appea s in he window, he me ic alue dec eases, esul ing in a nega i e
slope o he eg ession. The e o e, when a d i is con i med, he ace ha caused he d i is
he las one om he i s window e alua ed in he eg ession. Thus, he index o he change
o i ness is
𝑖−𝑛+ (𝑛/2)=𝑖− (𝑛/2)
. Howe e , in he case o p ecision, he alue will only
dec ease when he las ace be o e he d i disappea s om he window, so he i s d i ing
ace will be he i s one om he i s e alua ed window. Hence, he index o he change o
p ecision is 𝑖−𝑛.
A e checking o he occu ence o a d i , i he e is none, we slide he window one posi ion
o wa d (line 27) and p oceed o loop back o he beginning o he inne loop. O he wise, i
a change has been de ec ed, we b eak ou o he inne loop and es a he de ec ion p ocess.
Once all aces ha e been p ocessed, he sublog be ween he las de ec ed change and he end
o he log is added o
L
(line 30). The algo i hm hen uses he unc ion Classi yD i s om
Algo i hm 5.2 o classi y he changes as sudden o g adual be o e e u ning (line 31).
5.2.1 D i classi ica ion
Once he d i poin s ha e been de ec ed om he log, he nex s ep is o classi y hem as sudden
o g adual d i s using he same c i e ia desc ibed in Chap e 4. Howe e , his classi ica ion is
pe o med as a inal s ep ins ead o being done du ing he de ec ion p ocess, and i mus also
be adap ed o accoun o noisy en i onmen s. Algo i hm 5.2 ou lines he code used o his
classi ica ion.
The algo i hm akes in a lis o sublogs delimi ed by d i s
L
, a co esponding lis o models
N
, and an es ima ion o he pe cen age o noise p esen in he log
𝑟
. The i s s ep is o ini ialize
a lis
D
(line 2), which will be used o s o e he classi ied d i s. I
L
con ains only wo sublogs,
i can be assumed ha he d i is sudden and ha i occu s on he las ace om he i s sublog
(lines 3 o 5). O he wise, we i e a e o e he lis o sublogs un il he an epenul ima e sublog is
eached (lines 5 o 20). Wi hin his loop, we selec h ee consecu i e models
N𝑖
,
N𝑖+1
and
N𝑖+2
,
along wi h he co esponding sublogs
L𝑖
,
L𝑖+1
and
L𝑖+2
. Then i is checked i
L𝑖+1
ep esen s
a g adual change using he ollowing ou condi ions (line 9):
1. The beha iou om N𝑖and N𝑖+2mus di e om each o he .
2. A leas one ace in L𝑖+1mus exhibi beha io ha is suppo ed by N𝑖.
3. A leas one ace in L𝑖+1mus exhibi beha io ha is suppo ed by N𝑖+2.
83
Víc o José Gallego Fon enla
Table 5.1:
A e age
𝐹𝑠𝑐𝑜𝑟𝑒
and
Δ
alues o he noisy logs wi h sudden changes. The colo s highligh
he bes pe o ming app oach o each me ic.
size noise R-CRIER P oD i TPCDD
𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ
2500
0% 1.0000 4.6928 0.7082 71.1555 1.0000 2.6391
5% 0.9645 14.5923 0.6585 73.4256 0.6781 16.9935
10% 0.9447 15.5607 0.5723 78.0376 0.6707 16.3464
15% 0.9483 18.7591 0.4301 80.5009 0.6631 18.3007
20% 0.8873 23.7562 0.4407 81.3877 0.6717 21.3137
25% 0.8690 23.4037 0.5410 80.7318 0.6719 22.3660
5000
0% 1.0000 3.8366 0.8029 73.8648 0.9969 2.0458
5% 0.9173 30.6171 0.7017 83.4717 0.4134 11.8876
10% 0.8933 39.9600 0.7248 82.0148 0.4000 17.8529
15% 0.8713 36.7743 0.6952 94.1133 0.3973 17.6635
20% 0.8543 43.6831 0.6579 99.7240 0.3971 19.8169
25% 0.8475 46.6313 0.6149 101.6962 0.4006 21.7647
7500
0% 1.0000 4.6275 0.8235 95.2540 1.0000 2.5948
5% 0.9448 39.4678 0.7338 82.8303 0.2926 12.4727
10% 0.8656 50.3497 0.7253 91.9893 0.2849 13.7190
15% 0.8502 50.3693 0.7000 97.9897 0.2804 20.4118
20% 0.8514 66.1825 0.6225 118.2278 0.2803 19.8497
25% 0.8170 72.9812 0.5946 100.4500 0.2819 20.0719
10000
0% 0.9965 6.7369 0.8440 95.2569 1.0000 2.5882
5% 0.8973 62.3063 0.7806 84.8988 0.2274 12.9281
10% 0.8421 74.6499 0.6746 80.3740 0.2190 16.9739
15% 0.8438 83.6895 0.7190 102.5690 0.2191 16.6078
20% 0.8296 88.7595 0.6516 103.6556 0.2192 22.6797
25% 0.8663 93.2711 0.6058 109.8812 0.2179 19.4314
posi i es —some imes mo e han
60
alse posi i es o
9
ue posi i es—. In con as , o
P oD i ,
𝐹𝑠𝑐𝑜𝑟𝑒
alues dec ease wi h inc easing noise le els, bu his ime due o he numbe
o alse nega i es, i.e., eal changes ha he algo i hm ails o de ec . Rega ding
Δ
,TPCDD
ob ains he bes alues, ou pe o ming all o he app oaches, bu a he cos o signi ican ly
comp omising i s
𝐹𝑠𝑐𝑜𝑟𝑒
alues. P oD i ob ains he wo s esul s wi h delay alues be ween
70
and
100
aces o all logs, while R-CRIER lies in he middle, wi h
Δ
alues lowe han
P oD i bu highe han TPCDD. No ably, o R-CRIER,
Δ
alues inc ease wi h log size,
indica ing highe delays wi h longe logs, and lowe alues wi h smalle ones.
On he o he hand, Table 5.2 p esen s he a e age esul s o he logs con aining g adual
90

Chap e 5. Robus d i de ec ion
Table 5.2:
A e age
𝐹𝑠𝑐𝑜𝑟𝑒
and
Δ
alues o he noisy logs wi h g adual changes. The colo s highligh
he bes pe o ming app oach o each me ic.
dis ibu ion noise R-CRIER P oD i Ma jushe e al.
𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ
Lineal
0% 0.9471 76.1194 47.01% 0.8931 67.2216 46.12% 0.4937 65.3886 26.92%
5% 0.8692 88.0333 33.15% 0.8105 86.2990 34.11% 0.5336 60.1690 28.90%
10% 0.8737 93.3931 32.82% 0.8642 98.3175 33.78% 0.4037 69.5324 22.38%
15% 0.8228 96.6347 28.60% 0.8013 101.0552 29.43% 0.4682 52.4000 27.83%
20% 0.7681 103.2889 19.12% 0.7681 106.7514 19.64% 0.4516 56.0317 23.28%
25% 0.6712 91.5333 9.49% 0.6712 92.7708 9.15% 0.3402 47.7685 18.71%
Cons an
0% 0.8313 53.3969 53.92% 0.8260 52.9469 52.82% 0.5075 57.4841 28.75%
5% 0.7835 91.8861 34.40% 0.8098 82.4881 33.22% 0.5562 60.6037 32.14%
10% 0.8073 86.1333 32.36% 0.7891 78.5165 32.23% 0.5200 59.8333 29.17%
15% 0.8110 99.3597 34.86% 0.8110 101.5347 34.96% 0.3924 37.8968 22.04%
20% 0.6825 104.9520 17.71% 0.7018 103.0641 17.71% 0.4100 60.5648 24.19%
25% 0.6194 91.1194 3.99% 0.6194 90.6986 4.46% 0.4300 55.3667 29.44%
changes. R-CRIER con inues o ou pe o m o he app oaches in e ms o
𝐹𝑠𝑐𝑜𝑟𝑒
, wi h
consis en ly highe alues o e all. Howe e , he di e ences be ween he app oaches a e less
p onounced in his case. As wi h sudden d i s, he
𝐹𝑠𝑐𝑜𝑟𝑒
dec eases wi h an inc ease in he
noise le el, leading o lowe a e age alues, mainly due o alse nega i es being de ec ed.
Ma jushe e al. pe o med poo ly, achie ing F-sco e alues below
0.5
in
8
ou o
12
logs, and
no exceeding
0.55
in any log.
Δ
shows he bes esul s o Ma jushe e al., whe eas bo h
R-CRIER and P oD i exhibi wo se bu simila alues. In e ms o
Υ
, he h ee al e na i es
pe o m simila ly, wi h he bes esul s e enly dis ibu ed among hem.
S a is ical es s
To ensu e he alidi y o he esul s, we ha e used s a is ical me hods o compa e he pe o mance
o R-CRIER wi h he s a e o he a algo i hms. Speci ically, we conduc ed a BAIN es o
de e mine i R-CRIER pe o ms be e han he o he app oaches —de ails o his es a e
explained in Sec ion 3.3.4—. The Bayes ac o
𝐵𝐹𝐻𝑖𝐻𝑐
𝑖
was used as a measu e o e idence o
he hypo hesis being es ed agains i s complemen . The esul s o his es a e summa ized in
Table 5.3. Fo he sudden d i logs, he Bayes ac o
𝐵𝐹𝐻1𝐻𝑐
1
—whe e
𝐻1
is he hypo hesis
ha conside s ha R-CRIER has be e esul s— clea ly shows an ex eme e idence suppo ing
he hypo hesis ha R-CRIER pe o ms be e han he o he app oaches in e ms o
𝐹𝑠𝑐𝑜𝑟𝑒
.
Howe e , when i comes o
Δ
,TPCDD is s a is ically supe io o R-CRIER. When i comes o
91
Víc o José Gallego Fon enla
Table 5.3:
BAIN es esul s o he alida ion logs, whe e
𝐵𝐹𝐻𝑖𝐻𝑐
𝑖
shows he Bayesian ac o o
𝐻𝑖
agains i s complemen a y
𝐻𝑐
𝑖=¬𝐻𝑖
. The mos likely hypo hesis is shown shaded in blue.
𝐵𝐹𝐻𝑖𝐻𝑐
𝑖
𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ
sudden d i s
𝐻1:R-CRIER >P oD i
and R-CRIER >TPCDD 2.28 ×1013 7.06 ×10−25 —
𝐻2:R-CRIER <P oD i 2.14 ×10−31 6.78 ×10−71 —
𝐻3:R-CRIER <TPCDD 4.58 ×10−91 2.29 ×1013 —
𝐻4:R-CRIER =P oD i 1.55 ×10−28 7.08 ×10−68 —
𝐻5:R-CRIER =TPCDD 5.75 ×10−88 3.55 ×10−22 —
g adual d i s
𝐻1:R-CRIER >P oD i
and R-CRIER >Ma jushe e al. 3.19 4.23 ×10−10 9.75 ×10−1
𝐻2:R-CRIER <P oD i 6.35 ×10−11.52 1.05
𝐻3:R-CRIER <Ma jushe e al. 7.02 ×10−21 4.44 ×1099.49 ×10−1
𝐻4:R-CRIER =P oD i 1.29 ×1011.30 ×1011.34 ×101
𝐻5:R-CRIER =Ma jushe e al. 2.22 ×10−18 4.17 ×10−81.34 ×101
g adual d i s,
𝐵𝐹𝐻1𝐻𝑐
1
indica es ha R-CRIER and P oD i a e simila ly e ec i e in e ms o
𝐹𝑠𝑐𝑜𝑟𝑒
, wi h he highes e idence sco e. Howe e , Ma jushe e al. pe o ms signi ican ly
be e han he o he wo app oaches in e ms o
Δ
, acco ding o he es esul s. In e ms o
Υ
,
he es shows ha all h ee algo i hms a e e enly ma ched, wi h high e idence o hei pai ing.
5.3.3 Resul s discussion
The p e ious sec ion shows ha R-CRIER ou pe o ms he es o he s a e o he a app oaches
in e ms o 𝐹𝑠𝑐𝑜𝑟𝑒 when dealing wi h noisy en i onmen s.
The esul s o sudden changes a e p omising, wi h R-CRIER achie ing a mean
𝐹𝑠𝑐𝑜𝑟𝑒
alue
o
0.9
ac oss all he logs. Howe e , as he le el o noise inc eases,
𝐹𝑠𝑐𝑜𝑟𝑒
alues dec ease due o
an inc ease in alse posi i es. This can be a ibu ed o he challenge o di e en ia ing be ween
a eal d i and anomalous execu ions, which can cause con o mance me ics o dec ease e en
when such p esence is spu ious. Ne e heless, he numbe o alse posi i es emains wi hin
ole able limi s, wi h an a e age o less han
3
, and a maximum o
7
and
8
on he
RIO
and
OIR
logs wi h
10,000
aces and
25%
and
20%
o noise, espec i ely. In hese expe imen s, we
limi ed he noise p esence o a maximum o
25%
. Howe e , ou esul s sugges ha R-CRIER
may s ill pe o m well in en i onmen s wi h e en highe le els o anomalous execu ions.
In con as o R-CRIER,TPCDD shows a apid dec ease in
𝐹𝑠𝑐𝑜𝑟𝑒
alues e en wi h small
92
Chap e 5. Robus d i de ec ion
noise le els, and i s pe o mance does no signi ican ly change wi h a ying le els o noise.
Ins ead, he p ima y ac o ha a ec s TPCDD pe o mance is he size o he log, which leads
o a signi ican numbe o alse posi i es be ween changes. This makes TPCDD imp ac ical o
use wi h he la ges logs and highe le els o noise, whe e i de ec s o e
60
alse posi i es o
all cases.
Among he e alua ed app oaches, P oD i alls be ween R-CRIER and TPCDD. I s
𝐹𝑠𝑐𝑜𝑟𝑒
alues show a simila beha io o R-CRIER, dec easing wi h he noise le el, bu wi h lowe
magni ude. The maximum
𝐹𝑠𝑐𝑜𝑟𝑒
alue achie ed was
0.8440
o he
10,000
aces and
0%
noise. Howe e , he dec ease in
𝐹𝑠𝑐𝑜𝑟𝑒
is mainly due o an inc ease in he alse nega i e a es,
wi h some d i s going unno iced in an inc easing numbe o logs. This migh be caused by
he algo i hm building an unde i ing e e ence model, which is oo gene alized due o he
p esence o noise o de ec changes accu a ely.
In e ms o
Δ
,TPCDD ou pe o ms R-CRIER. Howe e , as p e iously men ioned, TPCDD
becomes imp ac ical in he p esence o noise, esul ing in nume ous alse de ec ions. The
mean
Δ
alues o R-CRIER inc ease wi h he log size and become close o hose o TPCDD
o smalle logs. All h ee algo i hms show an inc ease in
Δ
wi h he noise le el, possibly
because o he algo i hms ha e o wai longe o dis inguish a d i om anomalous beha io .
Addi ionally,
Δ
alues ob ained by P oD i a e highe o smalle logs han hose o R-CRIER,
bu he di e ence be ween smalle and la ge logs is no as signi ican as wi h R-CRIER.
In he case o g adual logs, R-CRIER ou pe o ms he o he app oaches in e ms o
𝐹𝑠𝑐𝑜𝑟𝑒
,
achie ing alues abo e
0.75
in
78
ou o
100
logs. Howe e , as wi h sudden d i s, he
𝐹𝑠𝑐𝑜𝑟𝑒
alues dec ease wi h an inc ease in noise le el. This dec ease is mainly due o he inabili y
o R-CRIER o de ec he end o d i egions accu a ely, esul ing in a high numbe o alse
posi i es a he end o he d i . The
Υ
alues also e lec his, indica ing ha he algo i hm
o en ails o de ec he en i e change egion, leading o p ema u e e mina ion o he d i .
P oD i exhibi s simila beha io o R-CRIER bu wi h wo se esul s. In con as , Ma jushe
e al. pe o ms poo ly, exhibi ing highly a iable de ec ion capabili y depending on he pa e n
o change p esen in he log. While he app oach achie es pe ec
𝐹𝑠𝑐𝑜𝑟𝑒
alues o some
pa e ns, i ails o de ec any change in o he s, esul ing in 𝐹𝑠𝑐𝑜𝑟𝑒 alues o 0.0.
93
Víc o José Gallego Fon enla
5.4 Conclusions
This chap e p esen s he R-CRIER algo i hm, which builds upon p e ious wo ks C2D2 and
CRIER o enable d i de ec ion in noisy en i onmen s. R-CRIER con inuously moni o s he
i ness and p ecision me ics o he model using linea eg ession, allowing o eliable and
obus de ec ion o changes. The hypo hesis ha se e al successi e eg essions wi h a nega i e
slope whose magni ude is always inc easing con i ms a d i has been ma hema ically p o en.
Expe imen s wi h
528
syn he ic logs wi h mul iple noise le els o sudden and g adual d i s
demons a e ha R-CRIER ou pe o ms o he s a e o he a p oposals wi h be e o e all
accu acy alues.
Despi e i s e ec i eness, R-CRIER has some limi a ions ha need o be add essed in o de
o p o ide a comple e solu ion o all scena ios. The p ima y challenge a ises om he use o a
ixed window size, which makes i di icul o handle logs wi h highly unbalanced in e als
be ween changes. To o e come his limi a ion, i would be desi able o in oduce a mechanism
o au oma ically calcula ing he window size, which could be op imized du ing he execu ion,
as sugges ed in Sec ion 3.2.2. Howe e , his p esen s a signi ican challenge, as he p esence o
anomalous execu ions in he log can make i di icul o pe o m such a sea ch o he op imal
size.
Ano he impo an limi a ion a ises wi h he au oma ic iden i ica ion o he pe cen age
o noise in logs om highly uns uc u ed p ocesses. The es ima ion me hods p oposed in
Sec ion 5.2.2 may yield subop imal esul s in such cases, as he e may no be a signi ican o
easily iden i iable knee in he g aph. I is wo h no ing ha his is a common issue a ec ing all
concep d i app oaches, as well as a la ge pa o p ocess mining asks. Ex ac ing aluable
knowledge om such p ocesses is challenging wi hou p io p ep ocessing. Howe e , explo ing
such p ep ocessing me hods alls beyond he scope o his disse a ion.
94
CHAPTER 6
CONCLUSIONS
I we knew wha i was we we e doing, i would
no be called esea ch, would i ?
— Albe Eins ein
In his disse a ion, ou ocus has been on add essing he challenge o iden i ying changes
in p ocess con ol- low by closely moni o ing he e olu ion o con o mance me ics o e ime.
Due o he widesp ead use o p ocesses ac oss a ious indus ies and o ganiza ions, coupled
wi h inc easing au oma ion and digi iza ion and he global in e connec i i y ha opens a
global ma ke o e e yone, i is c ucial o iden i y such changes in a imely manne o a oid
unde pe o mance o unexpec ed ou comes. This disse a ion emphasizes he c i ical na u e
o being awa e o sub le changes du ing P ocess Mining and Business P ocess Managemen
asks. Neglec ing o add ess hese changes can lead o ad e se consequences in he analysis
and insigh s de i ed om such ac i i ies.
In ecen imes, a ple ho a o solu ions ha e been p oposed o add ess his p oblem. Some
o hese solu ions aim o au oma ically upda e he p ocess o adap i o changes in he mos
op imal manne . O he s seek o de ec hese changes and in o m he ele an pa ies as quickly
as possible, he eby enabling in o med decision-making. Ou emphasis has been on he la e
g oup, so decisions a e aken using he la es alid da a. Reg e ably, mos o he app oaches ha
add ess his ask all sho in one way o ano he . Fi s ly, mos app oaches equi e subs an ial

Víc o José Gallego Fon enla
use in e en ion o con i m he exis ence o a change. This can be highly inapp op ia e in
complex o highly au oma ed en i onmen s ha gene a e big amoun s o da a, ende ing he
p ocess in easible. Secondly, hese app oaches usually su e om subs an ial delays in de ec ing
changes, aking an excessi e amoun o ime o e i y hei p esence, leading o po en ial losses
o he p ocess owne s. Thi dly, hey usually a e highly dependen on he pa e ns o change
obse ed in he da a, pe o ming op imally o some pa e ns, bu inadequa ely o o he s. This
makes hem unsui able o en i onmen s in which po en ial pa e ns o change a e unknown.
Finally, he majo i y o hese app oaches a e no obus , ailing o de ec changes in noisy
en i onmen s whe e anomalous execu ions can occu , which is common in he eal wo ld.
Taking in o accoun he s a e o he a limi a ions p e iously discussed, we sugges u ilizing
con o mance me ics as a means o eliable and ea ly de ec ion o changes, ega dless o hei
pa e ns. To suppo ou p oposal, we pu o wa d h ee hypo heses:
1.
We asse ha i ness can de ec changes ela ed o unsuppo ed beha io bu is
unable o de ec i ing beha io ha is disappea ing om he log, whe eas p ecision
can de ec changes ela ed o i ing beha io ha is disappea ing om he log bu
canno iden i y new unsuppo ed beha io ha is being obse ed.
2.
We sugges ha all g adual d i s can be cha ac e ized by a i ness change a he
ou se and a p ecision change a he end.
3.
We con end ha moni o ing successi e d ops in con o mance me ics allows us o
di e en ia e be ween genuine changes and spu ious, unexpec ed execu ions.
We ha e de eloped h ee algo i hms based on he a o emen ioned hypo heses, which allow
o he ea ly de ec ion o changes in he con ol- low o a p ocess.
In Chap e 3, we ocused on sudden changes —i.e., changes ha occu immedia ely, wi h
new beha io eplacing he old beha io om a speci ic poin in ime—. In his chap e , we
ha e demons a ed ma hema ically ha con o mance me ics can be used o de ec such changes.
We ha e also de eloped C2D2, an algo i hm ha e alua es i ness and p ecision me ics o e a
e e ence p ocess model using a sliding window and a linea eg ession, enabling he de ec ion
o changes in he p ocess s uc u e. To enhance he algo i hm accu acy, we ha e p oposed wo
new, low complexi y es ima o s o he con o mance me ics wi h which he d i de ec ion
is acili a ed. We es ed C2D2 wi h wo well-es ablished me ics—
𝐹𝑠𝑐𝑜𝑟𝑒
and delay— and
e alua ed i using a collec ion o
204
syn he ic logs gene a ed om
3
di e en p ocess models
96
Chap e 6. Conclusions
om he s a e o he a and
17
change pa e ns. We compa ed he esul s wi h hose om he
bes -pe o ming algo i hms om he s a e o he a , namely TPCDD and P oD i , and ound
ha C2D2 ou pe o med hem in e ms o 𝐹𝑠𝑐𝑜𝑟𝑒.
Then, in Chap e 4 ou ocus shi s o g adual d i s. Unlike sudden d i s, g adual d i s
occu when he old beha io is g adually eplaced by he new one o e ime. We ha e es ablished
and o mally p o en ha such d i s always commence wi h a change in i ness and culmina e
wi h a change in p ecision. Also, as pa o his chap e , we ha e de eloped CRIER, an algo i hm
ha builds on he p emises o C2D2 bu ex ends hem o dis inguish be ween sudden and
g adual d i s. Ou app oach is no cons ained by any pa icula beha io dis ibu ion du ing
he d i , enabling i o handle any changes while main aining high accu acy. We e alua ed
CRIER on
120
e en logs, which had
12
di e en p obabili y dis ibu ions. Addi ionally, we
in oduced a new e alua ion me ic ha measu es he accu acy o de ec ing he d i ing in e al.
The pe o mance o CRIER was compa ed o wo o he bes -pe o ming algo i hms om he
s a e o he a , namely P oD i and Ma jushe e al., and i ou pe o med hem conside ably.
Las ly, in Chap e 5, ou a en ion is on de eloping a obus de ec ion sys em ha can ope a e
e ec i ely e en in p esence o noise. We ha e demons a ed ha by moni o ing successi e
d ops in con o mance me ics, i is possible o di e en ia e be ween genuine changes and noisy
execu ions. To his end, we p esen he R-CRIER algo i hm, which builds on he p oposals
ou lined in he p e ious chap e s and adap s hem o handle noisy en i onmen s. Finally, we
e alua e he pe o mance o R-CRIER on a da ase consis ing o
528
logs and compa e i
wi h he bes -pe o ming app oaches om he s a e o he a , namely TPCDD,P oD i and
Ma jushe e al., showing ha ou algo i hm ou pe o ms hem again in e ms o accu acy.
Wi h hese h ee p oposed algo i hms, we ha e success ully achie ed all he objec i es
s a ed in he in oduc ion om Chap e 1. Speci ically, we ha e add essed he p oblem o
obus ly de ec ing changes in he con ol- low o a p ocess, whe he hey occu suddenly o
g adually, e en in noisy en i onmen s. We ha e ma hema ically p o ed ha con o mance
me ics can be used o de ec changes, and we ha e p oposed new me ics and algo i hms ha
imp o e upon he s a e o he a app oaches. Ou algo i hms ha e been ex ensi ely e alua ed
using syn he ic e en logs, demons a ing hei high accu acy and obus ness. By achie ing
hese objec i es, ou wo k con ibu es o he ield o p ocess mining and can ha e p ac ical
implica ions in a ious applica ion domains, such as heal hca e, inance, and manu ac u ing.
97
Víc o José Gallego Fon enla
Fu u e wo k
While he p esen esea ch has made signi ican p og ess in de ec ing con ol- low p ocess
changes in a ious scena ios, he e a e s ill se e al limi a ions ha need o be add essed in
u u e esea ch.
•
Cu en ly, ou algo i hms ocus solely on he de ec ion o con ol- low d i s. Howe e ,
he e is po en ial o explo e he use o o he me ics ha could e alua e o he p ocess
pe spec i es, enabling he ex ension o d i de ec ion o hese pe spec i es. Fo ins ance,
ime- ela ed me ics could be u ilized o moni o changes in he empo al pe o mance
o he p ocess. Al e na i ely, me ics based on he execu ion cos o ha moni o s
complex beha io al pa e ns, bo lenecks, o equen subp ocesses could be explo ed.
The addi ion o such me ics would enable he de ec ion o changes in hose pe spec i es,
he eby b oadening he scope o d i de ec ion o co e mo e scena ios.
•
In addi ion o he limi a ions ela ed o he con ol- low d i de ec ion, ou esea ch has
been con ined o single-p ocess scena ios. Howe e , as he complexi y o he p ocess
en i onmen inc eases, i is necessa y o explo e he de ec ion o changes in mo e
complex scena ios ha in ol e mul iple in e dependen p ocesses. To add ess his issue,
u u e esea ch could ocus on explo ing he use o clus e ing echniques o apply a
di ide-and-conque s a egy. This app oach would in ol e g ouping p ocesses wi h
simila cha ac e is ics in o clus e s, and hen applying ou p oposed algo i hms o each
clus e . To do so, i is necessa y o e alua e dis ance me ics o he clus e ing algo i hm,
which would enable us o measu e he simila i y be ween p ocesses and g oup hem
acco dingly. The e o e, by expanding ou esea ch o mo e complex p ocess scena ios
and de eloping app op ia e clus e ing echniques, we can ex end he applicabili y o ou
p oposed algo i hms o a wide ange o eal-wo ld p ocess en i onmen s.
•
Finally, he algo i hms p oposed in his esea ch a e solely designed o d i de ec ion
and do no add ess o he s ages o he d i managemen p ocess. Fu u e esea ch
could ocus on de eloping me hods o change desc ip ion and d i cause analysis,
which would p o ide p ocess owne s wi h mo e comp ehensi e in o ma ion o acili a e
decision-making. Such analysis could in ol e examining he con ex in which he d i
occu ed, iden i ying he ac o s ha igge ed i , and unde s anding he implica ions o
98
Chap e 6. Conclusions
he change o he o e all p ocess pe o mance. This would enable a mo e comple e and
e ec i e managemen o p ocess d i s.
In summa y, his esea ch has opened se e al a enues o u u e wo k ha can enhance
he d i de ec ion p ocess in a ious ways. These include he explo a ion o new me ics o
de ec changes in di e en p ocess pe spec i es, he ex ension o he algo i hms o mul iple
in e dependen p ocesses, and he de elopmen o echniques o change desc ip ion and
d i cause analysis. By add essing hese challenges, we can p o ide a b oade app oach
o p ocess d i managemen , and p o ide mo e aluable in o ma ion o p ocess owne s o
decision-making. The possibili ies o u he esea ch in his a ea a e p omising and ha e he
po en ial o make signi ican con ibu ions o he ield o p ocess mining.
99
Víc o José Gallego Fon enla
Table A.2:
Mean
𝐹𝑠𝑐𝑜𝑟𝑒
and
Δ
alues o each algo i hm using he hospi al eme gency wa d
p ocess logs. (Con inued)
sw
2500 1.0000 2.0000 1.0000 0.4444 0.0000 — 0.9474 3.3333
5000 1.0000 2.0000 1.0000 0.8889 0.0000 — 1.0000 3.2222
7500 1.0000 2.0000 1.0000 0.8889 0.0000 — 0.7826 3.6667
10000 1.0000 2.0000 1.0000 1.0000 0.2000 82.0000 1.0000 2.6667
pl
2500 1.0000 1.5556 1.0000 1.1111 0.3636 57.5000 0.9474 7.7778
5000 1.0000 2.2222 1.0000 1.1111 0.0000 — 1.0000 8.4444
7500 1.0000 2.2222 1.0000 1.0000 0.2000 136.0000 1.0000 9.3333
10000 1.0000 2.5556 1.0000 1.2222 0.3636 150.5000 0.8182 7.3333
pm
2500 1.0000 5.8889 1.0000 3.3333 0.0000 — 1.0000 11.3333
5000 1.0000 7.2222 1.0000 3.8889 0.0000 — 0.8182 9.6667
7500 1.0000 5.5556 1.0000 1.5556 0.0000 — 0.7826 14.0000
10000 1.0000 7.7778 1.0000 2.1111 0.0000 — 0.9000 12.0000
e
2500 1.0000 2.0000 1.0000 1.0000 1.0000 58.1111 1.0000 9.4444
5000 1.0000 2.0000 1.0000 0.5556 1.0000 62.4444 0.7826 11.0000
7500 1.0000 2.0000 1.0000 0.6667 1.0000 66.1111 0.8571 11.2222
10000 1.0000 2.0000 1.0000 0.6667 1.0000 65.4444 1.0000 11.8889
p
2500 1.0000 2.0000 1.0000 0.4444 1.0000 67.0000 0.8571 5.1111
5000 1.0000 2.0000 1.0000 0.3333 1.0000 62.2222 0.9000 6.2222
7500 1.0000 2.0000 1.0000 0.6667 1.0000 69.8889 0.8182 5.4444
10000 1.0000 2.0000 1.0000 0.7778 1.0000 60.7778 1.0000 5.7778
IOR
2500 1.0000 2.0000 1.0000 0.8889 0.3333 24.0000 0.9000 6.4444
5000 1.0000 2.0000 1.0000 0.7778 0.5000 76.3333 0.9474 5.5556
7500 1.0000 2.0000 1.0000 0.7778 0.5000 186.0000 1.0000 6.1111
10000 1.0000 2.0000 1.0000 0.8889 0.3636 144.5000 0.9000 6.1111
Log size
C2D2 TPCDD PD-T PD-E
𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ
Con inues on nex page
106

Appendix A. Sudden d i de ec ion: supplemen a y expe imen s
Table A.2:
Mean
𝐹𝑠𝑐𝑜𝑟𝑒
and
Δ
alues o each algo i hm using he hospi al eme gency wa d
p ocess logs. (Con inued)
IRO
2500 1.0000 6.1111 1.0000 2.8889 0.7143 105.8000 1.0000 19.8889
5000 1.0000 7.2222 1.0000 3.0000 0.6154 96.2500 0.8889 18.6250
7500 1.0000 4.6667 1.0000 2.3333 0.6154 104.0000 0.7500 18.5556
10000 1.0000 4.0000 1.0000 2.2222 0.3636 110.0000 0.8182 17.7778
OIR
2500 0.9474 2.0000 0.7826 1.2222 0.7143 82.2000 0.9000 7.5556
5000 0.9474 2.0000 0.6429 1.6667 0.7143 86.8000 0.8571 8.8889
7500 1.0000 2.0000 0.5143 2.1111 0.8750 89.8571 0.7826 3.7778
10000 1.0000 2.0000 0.4186 2.8889 1.0000 106.3333 0.6923 7.0000
ORI
2500 1.0000 2.0000 1.0000 0.6667 0.5000 36.3333 1.0000 6.0000
5000 1.0000 2.0000 1.0000 0.4444 0.5000 94.0000 1.0000 6.7778
7500 1.0000 2.0000 1.0000 0.3333 0.8750 123.4286 0.9474 6.2222
10000 1.0000 2.0000 1.0000 0.6667 0.9412 280.6250 0.9000 6.0000
RIO
2500 1.0000 2.0000 1.0000 0.7778 0.6154 58.7500 0.9000 5.8889
5000 1.0000 2.0000 1.0000 0.8889 0.5556 100.6000 0.7826 5.5556
7500 1.0000 2.0000 1.0000 0.7778 0.7143 105.8000 0.7200 5.5556
10000 1.0000 2.0000 1.0000 0.6667 0.7143 101.8000 0.6207 12.6667
ROI
2500 1.0000 2.0000 0.9474 6.6667 0.9412 100.6250 1.0000 11.2222
5000 1.0000 2.0000 0.8182 7.0000 1.0000 76.8889 1.0000 14.2222
7500 1.0000 2.0000 0.6667 5.6667 1.0000 78.1111 0.9474 15.1111
10000 1.0000 2.0000 0.6000 6.6667 1.0000 80.5556 1.0000 15.0000
A e age
2500 0.9938 2.5359 0.9841 1.9150 0.6204 62.1327 0.8955 10.5049
5000 0.9969 2.6209 0.9652 1.9412 0.6863 81.7667 0.8281 12.1762
7500 1.0000 2.3007 0.9518 1.6601 0.7184 98.7705 0.8255 17.5621
10000 1.0000 2.5098 0.9423 1.9869 0.7407 107.5507 0.8067 19.1275
Log size
C2D2 TPCDD PD-T PD-E
𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ
107
APPENDIX B
GRADUAL DRIFT DETECTION:
SUPPLEMENTARY EXPERIMENTS
This appendix con ains de ailed esul s o he expe imen s o CRIER o he syn he ic logs o
he Loan Applica ion p ocess.
B.1 Linea logs
. Table B.1 shows he esul s o he linea g adual changes wi h slopes o
0.1%
,
0.2%
,
0.5%
,
and 1.0%.
Table B.1: 𝐹𝑠𝑐𝑜𝑟𝑒
,
Δ
and
Υ
alues o he logs wi h linea g adual changes. The colo s highligh he
bes pe o ming app oach o each me ic.
c
slope =0.1% 0.8000 45.5000 79.86% 0.6207 477.1111 27.90% 0.8750 240.7143 66.28%
slope =0.2% 1.0000 14.4444 90.93% 0.7826 100.4444 47.42% 0.3636 240.0000 9.00%
slope =0.5% 1.0000 19.8889 78.67% 0.7273 219.1250 18.00% 0.0000 — 0.00%
slope =1.0% 1.0000 15.3333 66.22% 0.3810 182.2500 10.11% 0.0000 — 0.00%
CRIER Ma jushe e al. P oD i
𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ
Con inues on nex page
Víc o José Gallego Fon enla
Table B.1: 𝐹𝑠𝑐𝑜𝑟𝑒
,
Δ
and
Υ
alues o he logs wi h linea g adual changes. The colo s highligh he
bes pe o ming app oach o each me ic. (Con inued)
cp
slope =0.1% 0.7619 42.7500 79.23% 0.7200 364.5556 29.44% 0.8750 245.4286 64.96%
slope =0.2% 1.0000 24.7778 87.29% 0.8000 137.7500 41.80% 0.7143 235.7500 24.42%
slope =0.5% 1.0000 18.1111 77.94% 0.7368 243.2857 30.44% 0.0000 — 0.00%
slope =1.0% 1.0000 11.2222 70.33% 0.4444 280.7500 8.89% 0.0000 — 0.00%
pm
slope =0.1% 0.3448 105.6000 43.72% 0.5000 283.3333 15.09% 0.8750 216.2857 68.73%
slope =0.2% 0.8000 38.3750 74.80% 0.6154 139.7500 25.84% 0.8235 203.1667 42.67%
slope =0.5% 0.9474 27.6667 78.28% 0.5000 170.3333 29.78% 0.3333 406.5000 22.00%
slope =1.0% 0.7368 15.4286 54.00% 0.0000 — 0.00% 0.5000 433.6667 22.44%
e
slope =0.1% 0.8571 27.6667 82.39% 0.5806 337.7500 24.82% 0.4615 288.3333 20.26%
slope =0.2% 1.0000 16.7778 88.20% 0.7500 157.1111 34.47% 0.0000 — 0.00%
slope =0.5% 1.0000 10.3333 82.39% 0.4762 193.6000 16.78% 0.0000 — 0.00%
slope =1.0% 1.0000 8.1111 68.78% 0.1905 41.0000 12.00% 0.0000 — 0.00%
p
slope =0.1% 0.5385 60.5714 56.50% 0.2000 881.0000 1.32% 0.8750 236.1429 63.11%
slope =0.2% 0.9474 41.6667 81.89% 0.0000 — 0.00% 0.5000 243.3333 12.91%
slope =0.5% 0.9474 12.5556 71.94% 0.0000 — 0.00% 0.0000 — 0.00%
slope =1.0% 1.0000 12.0000 68.89% 0.0000 — 0.00% 0.0000 — 0.00%
sw
slope =0.1% 0.7273 54.0000 79.32% 0.0000 — 0.00% 0.0000 — 0.00%
slope =0.2% 1.0000 21.1111 86.33% 0.0000 — 0.00% 0.0000 — 0.00%
slope =0.5% 1.0000 13.3333 81.00% 0.0000 — 0.00% 0.0000 — 0.00%
slope =1.0% 1.0000 10.1111 66.44% 0.0000 — 0.00% 0.0000 — 0.00%
OIR
slope =0.1% 0.6087 45.4286 70.71% 0.5455 474.1111 26.09% 0.0000 — 0.00%
slope =0.2% 0.6364 14.7143 70.18% 0.6667 173.1250 37.71% 0.0000 — 0.00%
slope =0.5% 1.0000 8.2222 90.56% 0.6957 186.1250 13.44% 0.0000 — 0.00%
slope =1.0% 1.0000 11.6667 80.56% 0.5600 60.8571 27.00% 0.0000 — 0.00%
CRIER Ma jushe e al. P oD i
𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ
Con inues on nex page
110
Appendix B. G adual d i de ec ion: supplemen a y expe imen s
Table B.1: 𝐹𝑠𝑐𝑜𝑟𝑒
,
Δ
and
Υ
alues o he logs wi h linea g adual changes. The colo s highligh he
bes pe o ming app oach o each me ic. (Con inued)
ORI
slope =0.1% 0.4444 81.5000 56.19% 0.5000 435.8889 26.08% 0.8750 325.1429 54.56%
slope =0.2% 0.7619 27.6250 77.40% 0.5385 208.7143 22.62% 0.3636 341.5000 3.36%
slope =0.5% 0.9474 34.4444 73.94% 0.6087 209.1429 17.00% 0.0000 — 0.00%
slope =1.0% 1.0000 11.4444 68.67% 0.4348 31.4000 29.44% 0.0000 — 0.00%
RIO
slope =0.1% 0.6364 80.2857 67.39% 0.3636 209.5000 10.09% 0.8750 216.5714 69.41%
slope =0.2% 1.0000 36.7778 83.76% 0.2000 79.0000 7.58% 0.9412 196.8571 56.84%
slope =0.5% 1.0000 27.6667 78.22% 0.2000 32.0000 11.11% 0.0000 — 0.00%
slope =1.0% 1.0000 17.2222 70.78% 0.5000 145.0000 33.33% 0.0000 — 0.00%
ROI
slope =0.1% 0.7619 31.3750 81.29% 0.8421 287.0000 26.34% 0.0000 — 0.00%
slope =0.2% 1.0000 13.7778 92.36% 0.7368 194.7143 34.51% 0.0000 — 0.00%
slope =0.5% 0.9000 9.0000 82.28% 0.9412 247.3750 46.28% 0.0000 — 0.00%
slope =1.0% 1.0000 7.3333 81.00% 0.3333 223.6667 22.89% 0.0000 — 0.00%
A e age
slope =0.1% 0.6481 57.4677 69.66% 0.4873 416.6944 17.70% 0.5712 252.6599 37.89%
slope =0.2% 0.9146 25.0048 83.31% 0.5090 148.8261 22.73% 0.3706 243.4345 15.58%
slope =0.5% 0.9742 18.1222 79.52% 0.4886 187.6234 18.31% 0.0333 406.5000 2.22%
slope =1.0% 0.9737 11.9873 69.57% 0.2844 137.8463 14.84% 0.0500 433.6667 2.24%
CRIER Ma jushe e al. P oD i
𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ
B.2 Gaussian logs
. Table B.2 shows he esul s o he de ec ion o g adual changes in logs ha ollow wo
Gaussian dis ibu ions.
111

Víc o José Gallego Fon enla
Table B.2: 𝐹𝑠𝑐𝑜𝑟𝑒
,
Δ
and
Υ
alues o he logs wi h Gaussian g adual changes. The colo s highligh
he bes pe o ming app oach o each me ic.
c
𝜇=20 𝜎2=10 0.9412 10.8750 61.22% 0.2727 25.6667 20.92%
𝜇=50 𝜎2=30 1.0000 9.7778 70.78% 0.5000 255.6000 6.84%
cp
𝜇=20 𝜎2=10 1.0000 8.2222 67.97% 0.2105 170.0000 0.44%
𝜇=50 𝜎2=30 1.0000 8.6667 63.33% 0.7368 283.0000 18.80%
pm
𝜇=20 𝜎2=10 1.0000 10.6667 55.56% 0.3636 168.5000 22.22%
𝜇=50 𝜎2=30 1.0000 14.8889 66.36% 0.6154 94.2500 44.44%
e
𝜇=20 𝜎2=10 1.0000 6.4444 63.40% 0.2000 55.5000 12.42%
𝜇=50 𝜎2=30 1.0000 10.0000 62.94% 0.4000 176.0000 9.25%
p
𝜇=20 𝜎2=10 1.0000 7.1111 64.49% 0.0000 — 0.00%
𝜇=50 𝜎2=30 1.0000 9.8889 60.22% 0.0000 — 0.00%
sw
𝜇=20 𝜎2=10 1.0000 12.2222 63.83% 0.0000 — 0.00%
𝜇=50 𝜎2=30 0.9474 8.1111 59.75% 0.0000 — 0.00%
OIR
𝜇=20 𝜎2=10 1.0000 6.4444 64.05% 0.5000 5.3333 61.44%
𝜇=50 𝜎2=30 1.0000 25.6667 61.93% 0.5000 72.6667 26.34%
ORI
𝜇=20 𝜎2=10 1.0000 8.6667 62.31% 0.2727 11.6667 29.85%
𝜇=50 𝜎2=30 1.0000 6.1429 47.40% 0.6087 141.7143 20.44%
RIO
𝜇=20 𝜎2=10 0.9412 10.3750 60.57% 0.0000 — 0.00%
𝜇=50 𝜎2=30 1.0000 15.4444 64.34% 0.3636 13.0000 21.13%
ROI
𝜇=20 𝜎2=10 1.0000 6.7778 69.28% 0.4444 253.5000 17.86%
𝜇=50 𝜎2=30 0.9000 7.3333 68.07% 0.8421 254.5000 36.52%
A e age
𝜇=20 𝜎2=10 0.9882 8.7806 63.50% 0.2264 98.5952 16.03%
𝜇=50 𝜎2=30 0.9847 11.5921 61.59% 0.4567 161.3414 19.66%
CRIER Ma jushe e al.
𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ
B.3 Exponen ial logs
. Table B.3 shows he esul s o he de ec ion o g adual changes in logs ha ollow h ee
exponen ial dis ibu ions wi h 𝜆se o 0.05, 0.1, and 0.5.
112
Appendix B. G adual d i de ec ion: supplemen a y expe imen s
Table B.3: 𝐹𝑠𝑐𝑜𝑟𝑒
,
Δ
and
Υ
alues o he logs wi h exponen ial g adual changes. The colo s
highligh he bes pe o ming app oach o each me ic.
c
𝜆=0.05 0.5000 6.0000 23.02% 0.3333 205.2500 11.99%
𝜆=0.10 1.0000 5.2222 60.00% 0.2857 38.6667 11.43%
𝜆=0.50 0.3636 2.0000 19.05% 0.2857 9.0000 33.33%
cp
𝜆=0.05 0.4615 8.8333 12.39% 0.5000 297.8000 15.83%
𝜆=0.10 0.9412 6.3750 53.81% 0.2222 300.5000 6.51%
𝜆=0.50 0.3636 3.0000 17.46% 0.1111 285.0000 0.79%
pm
𝜆=0.05 0.4167 9.8000 25.82% 0.2000 166.0000 11.11%
𝜆=0.10 1.0000 8.7778 49.68% 0.2000 217.0000 11.11%
𝜆=0.50 0.2000 3.0000 8.73% 0.0000 — 0.00%
e
𝜆=0.05 0.6364 7.4286 34.69% 0.5000 92.6667 22.14%
𝜆=0.10 1.0000 3.7778 57.46% 0.4348 47.6000 17.14%
𝜆=0.50 0.7143 2.8000 44.44% 0.1905 7.5000 11.11%
p
𝜆=0.05 0.4800 8.3333 17.43% 0.0000 — 0.00%
𝜆=0.10 0.9412 4.2500 52.70% 0.0000 — 0.00%
𝜆=0.50 0.0000 — 0.00% 0.0000 — 0.00%
sw
𝜆=0.05 0.2963 11.5000 15.51% 0.0000 — 0.00%
𝜆=0.10 0.7000 5.7143 38.73% 0.0000 — 0.00%
𝜆=0.50 0.8000 3.3333 50.79% 0.0000 — 0.00%
OIR
𝜆=0.05 1.0000 5.2222 69.06% 0.6154 50.3750 41.25%
𝜆=0.10 1.0000 3.7778 60.48% 0.6667 20.8889 61.27%
𝜆=0.50 0.6154 2.5000 36.51% 0.6667 13.1111 99.21%
ORI
𝜆=0.05 0.5000 9.8333 29.42% 0.5600 52.0000 29.58%
𝜆=0.10 0.6000 6.5000 35.40% 0.5000 22.1429 53.02%
𝜆=0.50 0.3636 2.5000 18.25% 0.4167 11.2000 49.21%
RIO
𝜆=0.05 0.8000 12.1250 46.44% 0.2000 160.0000 11.11%
𝜆=0.10 0.9412 8.1250 56.67% 0.2000 233.0000 11.11%
𝜆=0.50 0.3636 3.5000 16.67% 0.2000 192.0000 11.11%
CRIER Ma jushe e al.
𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ
Con inues on nex page
113
Víc o José Gallego Fon enla
Table B.3: 𝐹𝑠𝑐𝑜𝑟𝑒
,
Δ
and
Υ
alues o he logs wi h exponen ial g adual changes. The colo s
highligh he bes pe o ming app oach o each me ic. (Con inued)
ROI
𝜆=0.05 0.5000 6.6667 29.26% 0.7368 247.1429 25.34%
𝜆=0.10 0.8750 4.4286 46.98% 0.5263 236.6000 38.10%
𝜆=0.50 0.8000 2.8333 53.17% 0.2222 251.5000 22.22%
A e age
𝜆=0.05 0.5591 8.5742 31.11% 0.3646 158.9043 17.37%
𝜆=0.10 0.8999 5.6948 50.21% 0.3036 139.5498 22.03%
𝜆=0.50 0.4584 2.8296 27.34% 0.2093 109.9016 21.52%
CRIER Ma jushe e al.
𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ
B.4 Cons an logs
. Table B.4 shows he esul s o he de ec ion o g adual changes in logs ha ollow h ee
di e en cons an dis ibu ions.
Table B.4: 𝐹𝑠𝑐𝑜𝑟𝑒
,
Δ
and
Υ
alues o he logs wi h cons an g adual changes. The colo s highligh
he bes pe o ming app oach o each me ic.
c
𝑝=0.5𝑛=100 1.0000 5.4444 84.33% 0.3158 230.0000 2.22%
𝑝=0.5𝑛=200 1.0000 6.2222 93.00% 0.7273 172.5000 26.06%
𝑝=0.5𝑛=500 1.0000 6.2222 97.36% 0.9474 127.2222 46.69%
cp
𝑝=0.5𝑛=100 1.0000 5.6667 84.33% 1.0000 263.5556 30.44%
𝑝=0.5𝑛=200 1.0000 5.1111 92.22% 0.8889 287.7500 28.72%
𝑝=0.5𝑛=500 1.0000 4.8889 96.56% 1.0000 125.7778 53.64%
pm
𝑝=0.5𝑛=100 1.0000 4.5556 86.44% 0.0000 — 0.00%
𝑝=0.5𝑛=200 1.0000 4.4444 94.72% 0.0000 — 0.00%
𝑝=0.5𝑛=500 1.0000 6.6667 97.67% 0.6154 81.7500 37.73%
CRIER Ma jushe e al.
𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ
Con inues on nex page
114
Appendix B. G adual d i de ec ion: supplemen a y expe imen s
Table B.4: 𝐹𝑠𝑐𝑜𝑟𝑒
,
Δ
and
Υ
alues o he logs wi h cons an g adual changes. The colo s highligh
he bes pe o ming app oach o each me ic. (Con inued)
e
𝑝=0.5𝑛=100 1.0000 3.2222 84.22% 0.1053 93.0000 0.78%
𝑝=0.5𝑛=200 1.0000 3.5556 93.39% 0.5714 230.1667 17.33%
𝑝=0.5𝑛=500 1.0000 3.0000 96.49% 0.7273 213.7500 37.71%
p
𝑝=0.5𝑛=100 1.0000 17.1111 63.11% 0.0000 — 0.00%
𝑝=0.5𝑛=200 1.0000 5.2222 90.94% 0.0000 — 0.00%
𝑝=0.5𝑛=500 1.0000 5.8889 96.89% 0.0000 — 0.00%
sw
𝑝=0.5𝑛=100 1.0000 4.6667 87.33% 0.0000 — 0.00%
𝑝=0.5𝑛=200 1.0000 4.2222 94.44% 0.0000 — 0.00%
𝑝=0.5𝑛=500 1.0000 6.8889 96.29% 0.0000 — 0.00%
OIR
𝑝=0.5𝑛=100 1.0000 2.7778 89.22% 0.6154 39.7500 49.44%
𝑝=0.5𝑛=200 1.0000 3.0000 95.06% 0.5455 191.8333 19.22%
𝑝=0.5𝑛=500 1.0000 3.1111 96.73% 0.8571 198.7778 38.87%
ORI
𝑝=0.5𝑛=100 1.0000 5.4444 86.56% 0.4545 88.6000 25.89%
𝑝=0.5𝑛=200 1.0000 3.5556 96.06% 0.8571 232.5556 19.61%
𝑝=0.5𝑛=500 1.0000 3.8889 97.24% 0.6667 256.4444 40.60%
RIO
𝑝=0.5𝑛=100 1.0000 12.1111 83.67% 0.0000 — 0.00%
𝑝=0.5𝑛=200 1.0000 10.0000 93.11% 0.5000 171.6667 33.06%
𝑝=0.5𝑛=500 1.0000 9.8889 97.40% 0.3636 21.0000 20.22%
ROI
𝑝=0.5𝑛=100 1.0000 3.3333 90.89% 0.8421 245.5714 42.22%
𝑝=0.5𝑛=200 1.0000 3.0000 96.33% 1.0000 254.4444 44.94%
𝑝=0.5𝑛=500 1.0000 3.3333 98.36% 0.9474 153.3333 54.98%
A e age
𝑝=0.5𝑛=100 1.0000 6.4333 83.98% 0.3333 160.0795 16.53%
𝑝=0.5𝑛=200 1.0000 4.8333 94.03% 0.5090 220.1310 18.10%
𝑝=0.5𝑛=500 1.0000 5.3778 97.07% 0.6125 147.2569 33.04%
CRIER Ma jushe e al.
𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ
115