Conformance Checking-based Concept Drift Detection in Process Mining

ESCOLA DE DOUTORAMENTO INTERNACIONAL DA USC Víctor José Gallego Fontenla Tese de doutoramento Conformance Checking-based Concept Drift Detection in Process Mining Santiago de Compostela, 2023 Programa de Doutoramento en Investigación en Tecnoloxías da Información TESE DE DOUTORAMENTO CONFORMANCE CHECKING-BASED CONCEPT DRIFT DETECTION IN PROCESS MINING Víctor José Gallego Fontenla 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 Declaración do autor/a da tese D./Dna. Víctor José Gallego Fontenla Título da tese: Conformance Checking-based Concept Drift Detection in Process Mining Presento a miña tese, seguindo o procedemento axeitado ao Regulamento, e declaro que: 1. A tese abarca os resultados da elaboración do meu traballo. 2. De ser o caso, na tese faise referencia ás colaboracións que tivo este traballo. 3. Confirmo que a tese non incorre en ningún tipo de plaxio doutros autores nin de traballos presentados por min para a obtención doutros títulos. 4. A tese é a versión definitiva presentada para a súa defensa e coincide a versión impresa coa presentada en formato electrónico. E comprométome a presentar o Compromiso Documental de Supervisión no caso de que o orixinal non estea na Escola. En Santiago de Compostela, Maio de 2023 Asdo. Víctor José Gallego Fontenla Autorización do director/titor da tese Conformance Checking-based Concept Drift Detection in Process Mining Dr. Manuel Lama Penín Dr. Juan Carlos Vidal Aguiar INFORMAN: Que a presente tese correspóndese co traballo realizado por D/Dna. Víctor José Gallego Fontenla, baixo a nosa dirección/titorización, e autorizamos a súa presentación, considerando que reúne os requisitos esixidos no Regulamento de Estudos de Doutoramento da USC, e que como directores desta non incorre nas causas de abstención establecidas na Lei 40/2015. De acordo co indicado no Regulamento de Estudos de Doutoramento, declaramos tamén que a presente tese de doutoramento é idónea para ser defendida en base á modalidade de Monográfica con reproducción de publicacións, nos que a participación do/a doutorando/a foi decisiva para a súa elaboración e as publicacións se axustan ao Plan de Investigación. En Santiago de Compostela, Maio de 2023 Asdo. Manuel Lama Penín Director/a tese Asdo. Juan Carlos Vidal Aguiar Director/a tese Á miña familia Cos que comparto sangue, e cos que non Resumo Se tivera tido máis tempo, tería escrito unha carta máis curta — Blaise Pascal Todos os días empregamos procesos, moitas veces sen sequera decatarnos. Campos tan variados como os sistemas de xestión da información [ 1 ], o seguimento do rendemento de atletas de alto nivel [ 2 , 3 ], a saúde [ 4 , 5 , 6 , 7 ] ou as metodoloxías de enxeñaría [ 8 , 9 , 10 ] usan procesos para estruturar as súas actividades. Nun entorno cada vez máis globalizado, onde os mercados se abren a todo o mundo e onde tomar decisións no momento preciso é crucial, é fundamental ser consciente de que a natureza dos procesos é dinámica e, por tanto, deben evolucionar para adaptarse ao seu entorno e alcanzar os seus obxectivos satisfactoriamente. A ampla variedade de aplicacións e a gran cantidade de datos xerados pola execución dos procesos fai esencial que tal adaptación se faga de forma automática, para así poder dispor de información precisa, fiable e veraz en todo momento. En resposta á necesidade de analizar toda esta información, aparecen diferentes técnicas que permiten modelar, interpretar e mellorar o rendemento dos procesos. Todas estas técnicas reúnense baixo o paraugas da Xestión de Procesos de Negocio (Business Process Management, BPM, en inglés). O BPM consta de varias fases que se desenvolven de forma cíclica. Comeza coa identificación do proceso, da súa arquitectura e do seu rendemento, para continuar co descubrimento do proceso e a súa documentación, seguido dunha etapa de análise na que se extraen debilidades e problemas que poidan afectar ao rendemento do proceso en xeral. Tras esta etapa de análise, e tendo en conta a información obtida acerca do rendemento, procédese a un Víctor José Gallego Fontenla redeseño do proceso que tentará mellorar algunha perspectiva no seu rendemento. Este proceso redeseñado é posteriormente implementado nun entorno supervisado e as súas execucións son monitorizadas para extraer información acerca de como o proceso se está a desenvolver e poder melloralo ciclicamente, repetindo cada unha das etapas indicadas. Un dos principais desafíos á hora de aplicar as técnicas de BPM no mundo real é que a maioría das tarefas deben ser realizadas manualmente por un experto ou requiren un alto nivel de interacción do usuario. Para reducir esta intervención, xurde unha nova disciplina denominada Minaría de Procesos (Process Mining, PM, en inglés), situada a medio camiño entre a Xestión de Procesos de Negocio e a Intelixencia Empresarial, por unha banda, e a Minaría de Datos e a Aprendizaxe Automática, por outra banda, que tenta automatizar moitas desas tarefas co fin de reducir a intervención humana ao mínimo. A través da extracción automatizada de información dos rexistros de execución dos procesos, a PM permite interpretar o que está realmente a acontecer nun proceso, en lugar do que se pensa que está a acontecer, permitindo tomar decisións en consecuencia. A maioría das técnicas de PM basean o seu funcionamento na análise de rexistros de eventos: conxuntos de trazas de execución compostas de eventos que rexistran a realización de certas tarefas, cos seus tempos de inicio e fin, e outros atributos adicionais, como poden ser os recursos empregados ou o seu custo, entre outros. As técnicas de PM poden ser clasificadas en tres grandes grupos. Por unha banda, temos os métodos de descubrimento, nos que a partir dun destes rexistros de eventos buscan as relacións de precedencia entre as actividades que compoñen o proceso, para extraer algunha clase de modelo que defina a súa estrutura. Estes modelos de proceso poden ser clasificados en dúas grandes familias: os modelos imperativos, que recollen todas as restricións entre actividades para definir o fluxo do proceso, e os modelos declarativos, que se basean en definir regras declarativas que restrinxen a precedencia entre algunhas actividades. Algúns exemplos de algoritmos de descubrimento do estado da arte son Inductive Miner,Heuristics Miner,Split Miner ou ProDiGen. Por outra banda, temos as técnicas de comprobación da conformidade, que se encargan de comparar modelos de proceso fronte aos rexistros de eventos para avaliar canto do comportamento soporta o primeiro con respecto ao segundo. Deste xeito, cuantifican as discrepancias e desaliñamentos entre os modelos de proceso e as súas execucións, permitindo avaliar en certa medida a calidade dos modelos á hora de representar o comportamento real dos procesos. Estas técnicas divídense en tres grandes familias: as métricas de axuste ou fitness, que miden canto comportamento presente no rexistro de eventos está soportado polo modelo, avaliando canto se desvían as execucións reais do comportamento esperado; as métricas de xvi precisión/xeneralización, que avalían a cantidade de comportamento que o modelo soporta fronte ao observado nas execucións reais; e as métricas de complexidade/simplicidade, que avalían como de estruturalmente complexo é o modelo. En terceiro e último lugar temos as tarefas de mellora do proceso, que teñen como obxectivo realizar unha análise do funcionamento do proceso e a extensión do modelo ou o seu refinamento para mellorar algunha das perspectivas deste. Dentro desta familia de técnicas podemos atopar algoritmos orientados a reparar o modelo para que se adapte mellor ao comportamento observado nas execucións e algoritmos orientados a estender o coñecemento do proceso coa fin de optimizar tempos de execución, predicir camiños ou patróns críticos ou detectar e corrixir comportamentos anómalos. Alén diso, as técnicas de PM poden ser clasificadas segundo a perspectiva do proceso analizado. Así, existen técnicas que analizan o proceso desde o punto de vista do fluxo de control, centrándose na estrutura das actividades e nas restricións entre elas. Estas técnicas son utilizadas para descubrir modelos ou verificar que as actividades se realicen na orde correcta. Tamén temos técnicas centradas na perspectiva organizacional, que analizan a asignación de recursos e optimizan a súa utilización, para, por exemplo replanificar calendarios de traballo. Outras técnicas abordan a perspectiva dos casos, analizando os atributos específicos para extraer características comúns a un subconxunto de casos que cumpran certos requisitos como, por exemplo, aqueles que aporten maiores beneficios. Por último, temos técnicas centradas na perspectiva temporal, que analizan os tempos de execución e espera para buscar retrasos na execución de certas tarefas ou motivos para execucións de larga duración. Estas perspectivas non son exclusivas, senón que poden combinarse para proporcionar unha visión máis ampla do proceso. Como se mencionou anteriormente, os procesos están cada vez máis presentes na nosa vida cotiá. Isto, xunto cun mundo cada vez máis competitivo, fai necesario que os procesos se adapten á realidade dos usuarios de forma flexible e áxil, para o cal os procesos deben ser suficientemente flexibles como para permitir cambios no fluxo das actividades. Estes cambios poden ser levados a cabo de forma consciente polos xestores do proceso, pero tamén derivados de circunstancias externas sobre as que non se ten control. É importante que estes cambios non pasen desapercibidos para os xestores, posto que poden levar a aumentos de custos ou reducións no rendemento do proceso. Por isto, é fundamental contar con información actualizada en todo momento que permita adaptarse ao proceso en tempo e forma tomando decisións da maneira máis inmediata posible para minimizar o seu impacto. Recentemente, propuxéronse diversas técnicas que permiten, dun xeito máis ou menos automatizado, xestionar estes cambios nos xvii Víctor José Gallego Fontenla procesos analizando a evolución dos casos de execución. Esta necesidade de xestionar os cambios non é nova. Orixinalmente, as técnicas de xestión de cambios nacen nos campos da aprendizaxe máquina e da monitorización predictiva, co obxectivo de detectar cando as variables empregadas para realizar unha predición cambian, invalidando os resultados. Este tipo de técnicas non foron adoptadas pola minaría de procesos ata fai uns anos; pola contra, a maioría das aproximacións de minaría de procesos aínda hoxe en día consideran os procesos como entidades estáticas que non evolucionan. A xestión dos cambios componse de tres etapas ben diferenciadas: por unha banda, a detección, encargada de indicar se un cambio existe ou non; por outra banda, a localización ecaracterización, encargadas de analizar o cando, o onde e o como do cambio; e, por último, a análise, encargada de explicar o por que do cambio. Nesta tese limitarémonos a propostas que resolven a fase de detección e de localización temporal. Existen diversas formas de clasificar os algoritmos de xestión de cambios. Dependendo do uso que fagan dos datos, podemos atopar uns algoritmos que empregan un único dato en cada instante e outros que fan uso dunha mostra de valores, coñecida como ventá. Os primeiros teñen a desvantaxe de levar máis tempo para detectar un cambio, mentres que os segundos dependen en gran medida da selección dun tamaño de ventá adecuado para capturar todo o comportamento. Á súa vez, estas ventás poden ter un tamaño fixo ou variable que se axusta automaticamente ao problema en tempo de execución, reducindo así a complexidade do problema de seleccionar un tamaño óptimo. Doutra banda, en función do mecanismo empregado para ponderar o valor da información segundo a súa antigüidade, atoparemos algoritmos con mecanismos de esquecemento gradual ou abrupto. Os primeiros utilizan máis datos para a avaliación dos cambios, dando maior importancia aos máis recentes pero sen descartar os antigos, o que pode retrasar a detección dos cambios. Os segundos, en cambio, empregan só un subconxunto dos valores históricos para realizar a detección. Estes últimos poden dividirse, a súa vez, en algoritmos baseados en mostras probabilísticas e algoritmos baseados nunha ventá temporal , que soamente consideran os valores máis recentes, dun xeito similar ao dunha cola de tamaño limitado. Todos os algoritmos presentados nesta tese se basean no uso dunha ventá temporal de tamaño fixo ou adaptable. Finalmente, os cambios poden ser clasificados tamén segundo a súa distribución temporal. Teremos cambios instantáneos cando un modelo substitúa ao outro abruptamente, sen pasos intermedios. Por outra banda, teremos cambios graduais cando os dous modelos, o previo ao cambio e o posterior, conviven durante un período de tempo, podendo atopar execucións de xviii ambos durante dito período. Amais, os cambios son incrementábeis cando podemos identificar modelos intermedios ata que o novo proceso se estabiliza; e recorrentes cando se repiten con certa periodicidade. Esta clasificación non é excluinte máis que para os dous primeiros tipos: un cambio deberá ser sempre instantáneo ou gradual, pero pode, á súa vez, formar parte dun cambio incrementábel se se dá nun contexto no que o modelo final non se chega a estabilizar. Ademais, todos os cambios (instantáneos, graduais ou incrementábeis) poden constituír un cambio recorrente se o comportamento se vai alternando ciclicamente con certa periodicidade. Por último, pero non menos importante, debemos diferenciar un cambio dunha execución anómala, que se debe a unha alteración espuria do proceso que non pervive no tempo. Nos últimos tempos, diversos autores propuxeron métodos para a detección de cambios nos procesos, seguindo diferentes aproximacións, todas coas súas vantaxes e inconvenientes. Así, podemos atopar propostas que basean o seu funcionamento en aliñar un modelo de proceso coas execucións reais [ 11 , 12 , 13 ]. Doutra banda, temos propostas baseadas en grafos, como as presentadas en [ 14 , 15 ], que representan o proceso como un grafo e analizan a súa evolución ao longo do tempo. Tamén podemos atopar propostas baseadas no uso de técnicas de agrupamento e no estudo da evolución de ditos grupos ao longo do tempo, como as presentadas en [ 16 , 17 , 18 , 19 ]. Non obstante, ningunha destas propostas consegue detectar todos os posibles patróns de cambio cunha alta fiabilidade e mantendo uns retardos pequenos. Agora ben, se se analiza o que ocorre nas métricas de conformidade cando ten lugar un cambio no estrutura dun proceso, pódese comprobar que cando unha actividade desaparece do modelo, a cantidade de comportamento que soporta o modelo vese reducida; sen embargo, cando unha nova actividade ou relación entre actividades aparece no modelo, o comportamento soportado polo modelo é superior ao que se observa nas trazas. Do mesmo xeito, pode comprobarse que cando aparecen ou se eliminan actividades nas trazas, o comportamento que pode explicar o modelo tipicamente cambia. Con estas consideracións, podemos formular a hipótese sobre a que se desenvolve esta tese: avaliar a evolución das métricas de conformidade ao longo da vida dun proceso pode permitirnos detectar cambios instantáneos e graduais de maneira fiable e rápida. En base a esta hipótese, propoñemos tres métodos para a detección de cambios instantáneos, graduais e en contornas con ruído. En primeiro lugar, preséntase C2D2, un algoritmo centrado na detección de cambios instantáneos con alta fiabilidade e baixos retrasos. Para isto, o algoritmo define unha ventá temporal de referencia e descobre un modelo de proceso a partir dos eventos contidos nela, para, a continuación, pasar a vixiar a evolución dos valores das métricas de axuste e precisión xix Víctor José Gallego Fontenla das sucesivas ventás mediante unha regresión linear simple. A idea tras deste algoritmo é que, en caso de non presentarse cambios, os valores das métricas deberían manterse estables arredor dun valor, ou o que é o mesmo, a pendente da regresión calculada sobre os valores históricos das métricas deberá ser cero, sen importar realmente o valor concreto que adquiran ditas métricas. Para fortalecer esta idea, demostramos que a combinación de métricas de axuste e precisión habilita a detección de cambios na estrutura dos procesos. Tamén demostramos que, por contra, empregar unicamente un tipo de métrica limita os patróns de cambio detectables. Amais, propoñemos un método para calcular o tamaño óptimo da ventá de detección de forma automática que está baseado nun proceso iterativo no que se descobren tres modelos de proceso a partir de tres ventás consecutivas dun tamaño determinado e se comparan os comportamentos capturados por eles. No caso de que sexan iguais, increméntase o tamaño da ventá ata que alomenos un dos tres modelos presente un comportamento diferente aos outros dous. Un dos problemas do método ven dado pola elevada complexidade de cómputo das métricas de conformidade, que se deben calcular múltiples veces, unha para cada ventá procesada. Para remediar este problema, propoñemos dúas estimacións do cambio nas métricas que, se ben non deberan ser empregadas para medir valores absolutos per se, son útiles para avaliar como estas evolucionan co tempo. Estas estimacións do cambio presentan un custo de cómputo moi inferior ao das métricas propostas no estado do arte, proporcionando mellores resultados á hora de detectar os cambios. As estimacións propostas son: (i) para o axuste, a porcentaxe de trazas que se poden volver a executar satisfactoriamente de principio a fin no modelo; e (ii) para a precisión, unha métrica dos pares de actividades relacionadas entre si no modelo fronte aos pares de actividades sucesivas observadas nas trazas, o que nos da unha idea da porcentaxe de camiños presentes no modelo que se observan alomenos unha vez nas execucións reais. C2D2 foi validado empregando 204 rexistros de eventos sintéticos xerados a partir de 3 modelos de proceso reais extraídos da literatura. Os resultados da detección foron comparados cos obtidos polos tres mellores algoritmos do estado do arte, empregando métricas habituais para este tipo de problemas, especificamente a fiabilidade, que avalía o numero de deteccións correctas e incorrectas, e o retardo, que mide canto tarda o algoritmo en detectar o cambio unha vez que este acontece. O resultado desta validación amosa que C2D2 obtén mellores resultados en termos de fiabilidade, mentres que mantén uns valores de retardo na detección moi baixos. Estes resultados tamén foron avaliados empregando tests estatísticos, validando as conclusións anteriores en tódolos casos. En segundo lugar, presentamos CRIER, que parte das premisas empregadas como base na xx definición de C2D2, é dicir, o uso de métricas de axuste e precisión e a súa monitorización mediante regresións lineais para a detección de cambios, pero estende a aproximación para habilitar a detección de cambios graduais en lugar de limitarse aos cambios instantáneos. O principio fundamental do funcionamento de CRIER é que todo cambio gradual vai estar delimitado por dúas deteccións teñen como particularidade que o comportamento que entre eses dous puntos pode ser definido como unha combinación dos comportamentos amosados antes e despois de dito cambio. Para fundamentar o desenvolvemento do algoritmo probamos formalmente que esta idea é correcta e que, ademais, o primeiro dos cambios vai ser debido a unha caída no axuste do modelo, debido á inclusión de novo comportamento que non fora observado antes e que, polo tanto, non formaba parte do comportamento capturado polo modelo descuberto a partir da ventá de referencia, mentres que o segundo será debido a unha caída na precisión, ao desaparecer o comportamento orixinal do proceso a partir dun instante concreto. Así, para comprobar que este comportamento intermedio sexa unha combinación dos outros dous, propoñemos un método que comproba a existencia de comportamento provinte dos modelos previo e posterior ao cambio, e que todas as execucións durante o intervalo de cambio pertenzan a un deles. Esta aproximación fai que non sexa necesario realizar ningún axuste a unha serie de distribucións de probabilidade determinadas, o que aporta maior flexibilidade ao algoritmo ao non impoñer ningunha restrición ao tipo de combinación presente durante o cambio gradual. CRIER foi avaliado empregando 120 rexistros de eventos sintéticos xerados a partir dun proceso real extraído do estado do arte e 12 distribucións de probabilidade diferentes para os segmentos de cambio. Os resultados obtidos foron comparados cos das principais propostas do estado do arte empregando as mesmas métricas de fiabilidade e retardo que foron usadas para avaliar C2D2. Ademais, proponse unha nova métrica para avaliar este tipo de algoritmos, á que denominamos cobertura do cambio, que cuantifica a porcentaxe do segmento de cambio detectado como tal por parte do algoritmo. Novamente, os resultados foron avaliados empregando tests estatísticos, amosando claramente que CRIER obtén os mellores resultados nas tres métricas. Finalmente, tomamos tódalas leccións aprendidas no o desenvolvemento de C2D2 eCRIER e propoñemos un novo algoritmo, R-CRIER, que habilita a detección de cambios instantáneos e graduais en contornas que presenten execucións anómalas que poden dar lugar a falsos positivos (tamén denominadas ruído). A maior dificultade de detectar cambios en procesos susceptibles de amosar ruído dáse á hora de diferenciar entre un cambio real e unha execución anómala xxi Víctor José Gallego Fontenla cuxo comportamento non perdura no tempo. Para levar a cabo esta detección seguimos coas premisas recollidas previamente (a avaliación das métricas de axuste e precisión) pero, neste caso, modificamos a etapa de monitorización. Se ben seguimos a empregar regresións lineais simples, demostramos formalmente que, no caso das anomalías, a pendente unicamente caerá durante un número determinado de medicións consecutivas, mentres que no caso dun cambio real o incremento na caída da pendente prolóngase durante moito máis tempo. Unha vez probada esta afirmación, propoñemos unha implementación que habilita a detección robusta de cambios, tanto instantáneos como graduais, en contornas susceptibles de presentar ruído. Un dos principais retos á hora de detectar os cambios neste tipo de contornas pasa por identificar a cantidade de anomalías presentes nas execucións. Para resolver este problema habitualmente recórrese ao coñecemento dun experto no domino, que indica a probabilidade de anomalías de xeito manual tras realizar algún tipo de análise do proceso. Neste caso, propoñemos un método automático de aproximación á estimación da porcentaxe ruído que habilita a súa detección en contornas onde non sexa posible contar coa colaboración de expertos. Para esta estimación baseámonos en métodos ben coñecidos na aprendizaxe automática, que ponderan en certa medida o beneficio de engadir máis información a un modelo fronte ao custo que isto ten asociado; tendo en conta que o comportamento anómalo debera ser pouco frecuente, mentres que o comportamento esperado do proceso debera estar moito máis presente no rexistro. Especificamente, o método avalía a porcentaxe de comportamento observado no rexistro de execución que é capturado polo modelo a medida que este se vai estendendo, de forma que o que se busca é o punto óptimo a partir do cal engadir máis comportamento ao modelo non fai que se soporten moitas máis trazas. R-CRIER foi avaliado empregando un total de 528 rexistros sintéticos xerados a partir dun modelo de proceso real extraído da literatura, con porcentaxes de ruído entre 0% e 25% , e con cambios tanto instantáneos como graduais. Os resultados obtidos foron comparados cos das principais aproximacións do estado do arte empregando as mesmas métricas que para C2D2 e CRIER. Neste caso, R-CRIER presenta os mellores resultados en termos de fiabilidade, á vez que mantén uns valores de retardo bastante baixos. Pola contra, a aproximación que obtén mellores valores de retardo faino a costa de sacrificar en gran medida a fiabilidade, polo que se volve inoperante para contornas reais. Co desenvolvemento destas tres aproximacións podemos dar por satisfeitos os obxectivos da tese de doutoramento, proporcionado como resultado final tres aproximacións que melloran as propostas do estado do arte na detección de cambios instantáneos e graduais no fluxo de xxii control dos procesos, e alicerzados por demostracións formais que validan as hipóteses de partida. xxiii Víctor José Gallego Fontenla iterative process in which three process models are discovered from three consecutive windows of a given size, and the behavior captured by these models is compared. If the three models capture the same behaviour, the window size is increased, until at least one of the three models exhibits different behavior from the other two. One of the main issues with C2D2 is the high computational complexity derived from the conformance metrics, which need to be calculated multiple times for each processed window. To address this problem, we propose two estimations of the change in metrics. Although these estimations should not be used to measure absolute values per se, they are useful for evaluating how the metrics evolve over time. These change estimations have a much lower computational cost compared to the metrics proposed in the state of the art, resulting in better results when detecting changes. The proposed estimations are as follows: (i) For fitness, the percentage of traces that can be successfully replayed from start to finish in the model. (ii) For precision, a metric that compares the set of pairs of reachable activities from the model to pairs of successive activities observed in the traces. This gives us an idea of the percentage of paths present in the model that are observed at least once in the actual executions. C2D2 has been validated using 204 synthetic event logs generated from 3 real process models extracted from the literature. The detection results have been compared with the results obtained by the top 3 state of the art algorithms using common metrics for this type of problem. Specifically, accuracy, which evaluates the number of correct and incorrect detections, and delay, which measures how long the algorithm takes to detect the change once it occurs. The validation results show that C2D2 achieves better results in terms of reliability while maintaining very low detection delay values. These results were also evaluated using statistical tests, which validate the previous conclusions in all cases. In the second place, we present CRIER, which builds upon the premises used as the basis for defining C2D2, namely the use of fitness and precision metrics and their monitoring through linear regressions for change detection, but extends the approach to enable the detection of gradual changes instead of being limited to sudden drifts. The fundamental principle behind CRIER operation is that every gradual change will be delimited by two detections that have the particularity that the behavior between these two points can be defined as a combination of the behaviors exhibited before and after that change. To substantiate the development of the algorithm, we formally prove that this idea is correct and that, furthermore, the first of the changes will be due to a drop in model fitness, resulting from the inclusion of new behavior that has not been observed before and therefore was not part of the behavior captured by the xxx model discovered from the reference window, while the second change will be due to a drop in precision, as the original behavior of the process disappears from a specific moment onwards. Thus, to verify that this intermediate behavior is a combination of the other two, we propose a method that checks for the existence of behavior originating from the models before and after the change and ensures that all executions during the interval of change belong to one of them. This approach eliminates the need to perform any fitting to specific probability distributions, which provides greater flexibility to the algorithm by not imposing any restrictions on the type of combination present during the gradual change. In addition, CRIER has been evaluated using 120 synthetic event logs generated from a real process extracted from the state of the art, as well as 12 different probability distributions for the change segments. The obtained results were compared with those of the main state of the art approaches using the same accuracy and delay metrics that were used to evaluate C2D2. Furthermore, a new metric called change coverage is proposed to evaluate this type of algorithm, which quantifies the percentage of the change segment detected as such by the algorithm. Once again, the results were evaluated using statistical tests, clearly demonstrating that CRIER achieves the best results in all three metrics. The last algorithm we propose is called R-CRIER, and enables the detection of both sudden and gradual changes in environments that may contain anomalous executions leading to false positives (also known as noise). The main challenge in detecting changes in processes prone to noise is distinguishing between a real change and an anomalous execution or outlier whose behavior does not persist over time. To address this detection challenge, we build upon the premises established earlier (namely, the evaluation of fitness and precision metrics) but modify the monitoring stage. While we continue to employ simple linear regressions, we formally demonstrate that in the case of anomalies, the slope will only decline for a certain number of consecutive measurements, whereas in the case of a real change, the slope’s decline will persist for a much longer period. Having validated this claim, we propose an implementation that enables robust detection of both sudden and gradual changes in environments prone to noise. Indeed, one of the main challenges in detecting changes in such environments lies in identifying the level of anomalies present in the executions. Typically, this challenge is addressed by leveraging the knowledge of a domain expert who manually assesses the likelihood of anomalies after analyzing the process. However, in this case, we propose an automatic method for estimating the percentage of noise, enabling its detection in environments where expert collaboration is not possible. To estimate the noise percentage, we rely on well-known xxxi Víctor José Gallego Fontenla methods in machine learning that weigh the benefit of adding more information to a model against the associated cost Given that anomalous behavior should be infrequent while the expected behavior of the process should be prevalent in the execution log, the method evaluates the percentage of observed behavior captured by the model as it is extended. The goal is to find the optimal point at which adding more behavior to the model does not significantly increase the number of supported traces. R-CRIER was evaluated using a total of 528 synthetic records generated from a real process model extracted from the literature. The logs had noise percentages ranging from 0% to 25% and included both instant and gradual changes. The results were compared with those of leading state of the art approaches using the same evaluation metrics as C2D2 and CRIER. In this case, R-CRIER achieved the best results in terms of accuracy while maintaining relatively low delay values. On the other hand, the approach that achieved better delay values did so at the expense of significantly sacrificing reliability, rendering it ineffective for real-world environments. With the development of these three approaches, we can consider the objectives of the Ph.D. dissertation fulfilled, resulting in three approaches that improve the state of the art proposals in the detection of sudden and gradual changes in the process control flow. These approaches are supported by formal demonstrations that validate the initial hypotheses. xxxii Contents 1 Introduction 1 1.1 Motivation.................................... 1 1.2 Hypothesis and objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3 Research Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4 OtherContributions............................... 19 1.5 Methodology .................................. 20 1.6 Documentstructure............................... 21 2 Related work 23 2.1 Suddendriftdetection.............................. 24 2.2 Gradual drift detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3 Conclusions................................... 34 3 Sudden drift detection 35 3.1 Sudden drift detection using conformance metrics . . . . . . . . . . . . . . . 37 3.2 Algorithm.................................... 38 3.3 Experimentation................................. 45 3.4 Conclusions................................... 56 4 Gradual drift detection 57 4.1 Gradual drift detection using conformance metrics . . . . . . . . . . . . . . 58 4.2 Algorithm.................................... 61 4.3 Experimentation................................. 66 4.4 Conclusions................................... 75 Contents 5 Robust drift detection 77 5.1 Robust drift detection using conformance metrics . . . . . . . . . . . . . . . 78 5.2 Algorithm.................................... 80 5.3 Experimentation................................. 86 5.4 Conclusions................................... 94 6 Conclusions 95 Appendix A Sudden drift detection: supplementary experiments 101 A.1 Central venous catheter process . . . . . . . . . . . . . . . . . . . . . . . . . 101 A.2 Hospital emergency ward process . . . . . . . . . . . . . . . . . . . . . . . 104 Appendix B Gradual drift detection: supplementary experiments 109 B.1 Linearlogs ................................... 109 B.2 Gaussianlogs.................................. 111 B.3 Exponentiallogs ................................ 112 B.4 Constantlogs .................................. 114 Appendix C Robust drift detection: supplementary experiments 117 C.1 Suddenchanges................................. 117 C.2 Gradualchanges................................. 136 List of publications included in this Ph.D. dissertation 143 Bibliography 145 List of Figures 155 List of Tables 157 xxxv CHAPTER 1 INTRODUCTION He that climbs a ladder must begin at the first round — Walter Scott 1.1 Motivation Processes are present all around us. From IT service management [ 1 ] to performance in high-level athletes [ 2 , 3 ], healthcare [ 4 , 5 , 6 , 7 ] or software engineering [ 8 , 9 , 10 ], organizations all around the globe use processes to shape their operations. With such a broad array of scenarios, it has become critical to be aware that the nature of processes is dynamic, so they must evolve and adapt to the environment quickly to properly serve their intended purpose. The wide variety of applications for processes and the large amount of data generated by their execution makes it essential that such adaptation is automatically done as much as possible, so that any process owner has accurate, reliable and truthful information when making decisions about the way the organisation operates. In response to the need for analysing all this information, over the last decades, different tools, techniques and mechanisms have emerged to support organisations in modelling, interpreting, and improving their processes. All these techniques are brought together under the umbrella of Víctor José Gallego Fontenla BPM Lifecycle I d e n t i f i c a t i o n D i s c o v e r 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 t a t i o n M o n i t o r i n g Process architecture As-is process model Insights on weaknesses and their impact To-be process model Executable process model Conformance and performance insights Figure 1.1: Business Process Management framework lifecycle (adapted from [20]). the Business Process Management (BPM) paradigm, which seeks to consolidate and integrate all these proposals with the aim of being interoperable. To address the goal of providing hints on how to improve processes, BPM defines a framework, depicted in Figure 1.1, in which processes go through several phases: identification of the process, discovery of a model as close as possible to how it is executed, analysis of weaknesses and potential optimisations, redesign of the process, implementation and deployment on its production environment, and monitoring and verification of its conformance with the respect to the designed one [20]. The most challenging factor when applying BPM techniques in the real world is that the majority of the tasks have to be performed manually, or require a high level of user interaction — for example, when designing a process model or when identifying opportunities for improvement—, which makes it difficult to deal with processes involving a large number of executions. In an attempt to address these issues, a new research discipline —called Process Mining (PM) [ 21 ]— has emerged with the aim of automating and improving many of the above problems through the use of techniques that reduce the intervention required by the process owners. PM stands in between BPM and Business Intelligence, on the one hand, and Data Mining and Machine Learning, on the other one, acting as a bridge between these two worlds. The process mining framework, depicted in Figure 1.2, relies on the extraction of valuable information from event logs, recording the execution of the activities that are part of a process in the form of events and traces. From the analysis of these logs, PM techniques allow us to interpret what is actually happening in a process, rather than what we think is happening, enabling us to take decisions accordingly [21]. 2 Chapter 1. Introduction Bussiness Processes Information Systems Event Logs Process Models supports produce Process Mining discovery conformance enhancement models analyzes implements/configure analyzes/specifies Figure 1.2: Process mining framework (adapted from [21]). Definition 1: Event Given the set of activities A that conform a process, an event 𝜀 can be defined as the execution of an activity 𝛼∈A at a given instant 𝑡 in the context of a process instance 𝑐 . The activity name 𝜀.𝑎 , the timestamp 𝜀.𝑡 and the process instance identifier —often referred to as case— 𝜀.𝑐 are the only mandatory attributes of an event, which can also have other generic attributes, such as the resources that perform the activities, or domain-specific attributes, understood as variables whose values are modified in the activity execution. Definition 2: Trace Given the full set of events E recorded from the execution of a process, a trace 𝜏 can be defined as the ordered sequence of the events belonging to the same process instance 𝜏.𝑐 , where the order is defined by the events timestamp. 3 Víctor José Gallego Fontenla Data Management Multiple Examples (Windows) Fixed Size Variable Size Single Example Figure 1.4: Taxonomy of concept drift algorithms based on their memory management: data management-driven classification (adapted from [46]). Forgetting Mechanism Gradual Forgetting Abrupt Forgetting Temporal Sequence (window) Fixed Size Variable Size Sampling (selection) Figure 1.5: Taxonomy of concept drift algorithms based on their memory management: forgetting mechanism-driven classification (adapted from [46]). the time performance of change detection, but will worsen the performance in periods without changes; while a window size too large will take longer to detect changes but have better performance in periods without changes. To solve this problem, windows can have a fixed size or a variable size that is automatically adapted during the execution. 2. According to the forgetting mechanism employed (Figure 1.5), algorithms can be classified into gradual forgetting and abrupt forgetting. The former considers all of the examples and assigns to each one a weight, giving a greater weight to the most recent data and 10 Chapter 1. Introduction 𝜏0𝜏1𝜏2𝜏3𝜏4𝜏5𝜏6𝜏7 𝜔5 𝜔6 𝜔7 Figure 1.6: Example of the sliding window behaviour. reducing the weight as the data becomes older. The latter consider a window of a restricted size and, as newer observations are received, forgets the older examples. These approaches can also be classified into two subtypes: those based on a sampling approach, in which each time a new observation is received a probability of belonging to the sample is assigned to it; and those that follow a first-in-first-out (FIFO) strategy, forgetting the oldest observations each time a new observation is received. The later are called sliding windows, and their size can be defined on the basis of a constant number of observations or on the basis of a temporal duration, which will cause the window size to change according to the new observations rate. All the methods presented in this Ph.D. dissertation use a window with an abrupt forgetting mechanism (sliding window). Definition 7: Sliding window The sliding window of size 𝑛 over a log 𝐿 is defined as 𝜔𝑖(𝐿, 𝑛)=⟨𝜏𝑖−𝑛+1, . . . , 𝜏𝑖⟩ , where its content is conformed by the most recent 𝑛 traces present in the log at instant 𝑖 . When a new trace is read from the log, the window slides one position, so the oldest trace is forgotten and the new trace is incorporated. This way, the algorithm only takes into account the most recent information for detecting changes. Figure 1.6 shows an example log and the behaviour of a six-sized sliding window over it. At instant 𝑡5 , the sliding window 𝜔5 contains traces 𝜏0 to 𝜏5 . At instant 𝑡6 a new trace is read from the log, so the oldest trace in the window ( 𝜏0 ) is forgotten and the new trace ( 𝜏6 ) is added to the window. This behaviour continues until the full log has been read. In addition to this classification, concept drift algorithms can also be grouped according to how datasets are processed: (i) offline algorithms, which perform the analysis once all the data are available, allowing a post-mortem analysis of the evolution of the observations; and 11 Víctor José Gallego Fontenla 𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1 𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2 Time (a) Sudden drift 𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1𝑀1 𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2𝑀2 Time (b) Gradual drift 𝑀1𝑀1𝑀1𝑀1𝑀1𝑀2𝑀3𝑀4𝑀5𝑀6𝑀7𝑀8𝑀8𝑀8𝑀8𝑀8 Time (c) Incremental drift 𝑀1𝑀1𝑀1𝑀1 𝑀2𝑀2𝑀2𝑀2 𝑀1𝑀1𝑀1𝑀1 𝑀2𝑀2𝑀2𝑀2 Time (d) Recurrent drift Figure 1.7: Types of concept drift based on their occurrence over time. (ii) online algorithms, which perform the analysis on-the-fly, as new data are generated, and are usually oriented towards real-time decision making. In this Ph.D. dissertation we focus only on the development of offline algorithms. It should be mentioned that changes can occur in multiple forms, according to their temporal distribution [46], as depicted in Figure 1.7: 1. Sudden changes, in which the new data distribution replaces the previous one immediately, so that the change occurs at a specific instant of time. 2. Gradual changes, in which both distributions, the old and the new, coexist for a period of time, alternating their appearance and fading away/becoming more present as the change takes place. These changes are characterized by the fact that they do not occur at an instant in time, but in a change region. 3. Incremental changes, in which a series of small successive changes occur due to intermediate distributions in the data between the original and the final distribution. As in the case of gradual changes, these changes are characterized by a region during which the different models succeed each other. 4. Recurrent changes, which are repeated periodically over time with a certain frequency. These changes are characterized more by the frequency with which they are repeated than by the point or region in which they occur. It should be highlighted that the first two change types are mutually exclusive. Thus, a change will be either sudden or gradual, but can also be incremental and/or recurrent. In addition, note that in business process management both incremental and recurrent changes can 12 Chapter 1. Introduction be approached as a sucession of sudden or gradual changes in the corresponding process model: for incremental changes every model is different, while for recurrent changes, the different models are repeated over time. For this reason, this Ph.D. dissertation has focused on both sudden and gradual changes only. Definition 8: Gradual drift, Sudden drift A gradual drift is defined as a change where the behaviour before the change does not disappear suddenly, but coexists with the one after the change for a period of time, while vanishing until it is no longer observed. Given two time instants 𝑡1 and 𝑡2 that bound the change, two models can be discovered, 𝑁<𝑡1 and 𝑁>𝑡2 , that capture the behaviour before and after those instants. For a change to be considered as gradual, four conditions must be satisfied: 1. The behaviours captured by the models discovered before 𝑡1 and after 𝑡2 are different: 𝐵𝑁<𝑡1≠𝐵𝑁>𝑡2. 2. Some of the behaviour observed between 𝑡1 and 𝑡2 is captured by the model discovered before 𝑡1:𝐵𝐿[𝑡1,𝑡2]∩𝐵𝑁<𝑡1≠∅. 3. Some of the behaviour observed between 𝑡1 and 𝑡2 is captured by the model discovered after 𝑡2:𝐵𝐿[𝑡1,𝑡2]∩𝐵𝑁>𝑡2≠∅. 4. All of the behaviour observed between 𝑡1 and 𝑡2 is captured either by the model discovered before 𝑡1 , by the model discovered after 𝑡2 or by both: 𝐵𝐿[𝑡1,𝑡2]⊆ (𝐵𝑁<𝑡1∪𝐵𝑁>𝑡2). If any of these conditions are not met, the change is considered a sudden change, where the old behaviour is replaced instantly by a new one. One of the biggest challenges in detecting conceptual drifts is to distinguish between real drifts and outliers [ 47 ], i.e., anomalous observations that do not reflect a real change in the models, but rather spurious executions that are not common and do not imply changes in the structure of processes. To avoid confusing these two concepts, we introduce the term of a drift candidate, a point with the potential to represent a change in the model but which must be confirmed later to reject that it is an effect of the presence of noise in the data. 13 Víctor José Gallego Fontenla Definition 9: Drift candidate A drift candidate can be defined as a potential change in the structure of the process that has to be confirmed later. Given two consecutive windows 𝜔𝑖 and 𝜔𝑖+1 , and two process models 𝑁𝑖=(𝑃𝑁𝑖, 𝑇𝑁𝑖, 𝐹𝑁𝑖, 𝜆𝑁𝑖) and 𝑁𝑖+1=(𝑃𝑁𝑖+1, 𝑇𝑁𝑖+1, 𝐹𝑁𝑖+1, 𝜆𝑁𝑖+1) discovered from each of these windows using the same discovery algorithm, we say that the window 𝜔𝑖 is a drift candidate when 𝑇𝑁𝑖≠𝑇𝑁𝑖+1∨𝐹𝑁𝑖≠𝐹𝑁𝑖+1 . A drift is confirmed only after several successive windows are marked as drift candidates and, in that moment, the change is pinpointed to the specific trace that triggered the change —the first trace of the first candidate in the case of fitness, or the last trace of the first window in the case of precision—. 1.2 Hypothesis and objectives In process mining, a change in a model implies an immediate change in the conformance measures. When a path from the model stops appearing in traces, it leads to reduced precision. Conversely, if a new path that is not included in the model starts appearing in the traces, it causes a reduction in fitness. These two situations suggest that there might be a connection between process mining conformance metrics and concept drift detection. Therefore, the hypothesis of the Ph.D. thesis can be formulated as follows: Drift detection and classification can be addressed by analyzing how the fitness and precision evolve along de process. Considering this hypothesis, the main objective of this Ph.D. dissertation is to detect automatically sudden and gradual changes in the structure of processes, based on the evolution of the conformance metrics. The solution should reach a high accuracy, detecting all the possible change patterns; maintain a low delay, allowing organizations to localize precisely the instant when the change took place; and be robust to the presence of noise, to distinguish between anomalous or infrequent behavior and real process changes. This main objective can be split in three sub-objectives: O1. The detection and localization of sudden drifts. 14 Chapter 1. Introduction The first objective is to design and develop an algorithm that can detect sudden controlflow drifts in a process from an event log. As a reference, all the common change patterns identified in process mining [48] should be supported by the algorithm. O2. The detection and localization of gradual drifts. The second objective is to detect gradual changes but, also, to differentiate when the change is sudden and gradual. This is specially interesting because, in a real environment, different type of changes can coexist, so being able to classify them is a requirement. O3. The adaptation of the former solutions to noisy environments. Finally, as a third objective, all the previous algorithms should be adapted to deal with noisy and complex event logs, where the structure of the underlying processes can be more complex, which can hinder the computation of conformance measures. 1.3 Research Contributions The research developed in this Ph.D. dissertation led to the following contributions: 1. A formal, mathematical demonstration that conformance metrics can be used to detect both sudden and gradual changes in the control-flow of a process. We have proven, combining set theory and definitions of fitness and precision, that monitoring these compliance metrics over time allows us to detect both sudden and gradual drifts in the control-flow of a process. 2. C2D2: An algorithm for Conformance Checking-based Drift Detection. We have proposed and successfully developed an algorithm (C2D2) for the detection and localization of sudden changes in a process control-flow. C2D2 monitors the conformance metrics along time using a a sliding window and a simple linear regression, being able to detect all the change patterns with a high accuracy while maintaining a small delay. The main contributions of C2D2 are as follows: (i) A method for detecting and identifying the points where the control-flow of the process changes suddenly. (ii) A novel and efficient estimator of the change in the precision of a model with respect to a set of traces. (iii) The use of regression techniques to monitor sudden changes in the control-flow of a process. 15 Víctor José Gallego Fontenla 3. CRIER: An algorithm for Conformance-based Gradual drift detection. We have successfully developed an algorithm (CRIER) for the detection and localization of gradual changes in the control-flow of a process. CRIER builds up on the same idea that monitoring conformance metrics along time can serve to detect changes —as in the case of the sudden drifts—, and extends it to deal with gradual changes. The main contributions of CRIER are as follows: (i) A formal proof that a gradual control-flow change will always imply some new and observable behaviour. (ii) A method for detecting and determining the intervals where the control-flow of a process gradually changes. (iii) A method for the classification of changes in sudden and gradual drifts. 4. R-CRIER: An algorithm for Robust drift detection in noisy environments. We have designed and implemented a functional solution (R-CRIER) for robust drift detection on noisy environments. R-CRIER starts with the lessons learned in the development of both C2D2 and CRIER and, from there, adapts the monitoring of conformance metrics to deal with noisy environments where anomalous executions can lead to wrong detections. The main contributions of R-CRIER are as follows: (i) A formal demonstration that monitoring the slope of a regression computed over conformance metrics values during some time can allow drift detection in noisy environments reducing the number of false positive detections. (ii) A method for detecting an localizing sudden and gradual drifts with a high accuracy even on high-noise environments. 1.3.1 Publications All the contributions shown in this dissertation are included in the following publications: Journals • Víctor Gallego-Fontenla, Juan Vidal and Manuel Lama, A Conformance Checkingbased Approach for Sudden Drift Detection in Business Processes,IEEE Transactions on Services Computing, 16:13-26, 2023 (Available online: October 2021). ISSN: 1939- 1374. doi: 10.1109/TSC.2021.3120031. Journal Impact Factor (JCR 2021): 11.019 5/164 (Q1) COMPUTER SCIENCE, INFORMATION SYSTEMS 2/110 (Q1) COMPUTER SCIENCE, SOFTWARE ENGINEERING 16 Chapter 1. Introduction • Víctor Gallego-Fontenla, Juan Vidal and Manuel Lama, Gradual Drift Detection in Process Models Using Conformance Metrics,Business & Information Systems Engineering, Submitted. ISSN: 2363-7005. doi: 10.48550/arXiv.2207.11007. Journal Impact Factor (JCR 2021): 5.675 33/164 (Q1) COMPUTER SCIENCE, INFORMATION SYSTEMS National Conferences • Víctor Gallego-Fontenla, Juan Vidal and Manuel Lama, Detección de concept drift en minería de procesos basado en agrupamiento de trazas,Jornadas de Ciencia e Ingenieria de Servicios (JCIS), 2018. hdl: 11705/JCIS/2018/005. • Manuel Lama, Juan Vidal, Víctor Gallego-Fontenla and Álvaro Porto Ares, Recomendación de actividades gamificadas basada en minería de procesos,Jornadas de Ciencia e Ingenieria de Servicios (JCIS), 2019. hdl: 11705/JCIS/2019/018. • Víctor Gallego-Fontenla, Juan Vidal and Manuel Lama, A Conformance Checkingbased Approach for Sudden Drift Detection in Business Processes (Summary), Jornadas de Ciencia e Ingenieria de Servicios (JCIS), 2022. hdl: 11705/JCIS/2022/007. 1.3.2 Participation in R&D projects, contracts and networks Aside from the publications mentioned above, the development of this Ph.D. thesis has lead to collaborations in the following projects: • CAREBOT - Intelligent Robotic Units for Ambulatory Healthcare Activities. This project pursued the development of robotic assistants to help patients to fullfill their routines and prescriptions at their home. As a result of this project, two products have been developed. On the one side, an event capturing and preprocessing cloud system have been designed, developed and deployed. On the other side, a trace clustering algorithm has been developed and validated in a Big Data environment. Both developments will later be used for fullfilling the objective O3. The adaptation of the former solutions to noisy logs and real processes by providing real logs for complex, loosely structured processes and a method for splitting them in simpler subprocesses, respectively. 17 Víctor José Gallego Fontenla • BIGBISC - Fueling Intelligence to Business Processes with Soft Computing in Big Data Scenarios. In this project, the algorithms presented in this Ph.D. dissertation have been adapted to look for changes in frequent patterns executed by users, rather than on complete process models. In addition, trace clustering techniques have been applied to simplify the problem by applying a divide-and-conquer strategy whereby for each data cluster only a subset of traces that are similar to each other are processed, so that the complexity of the extracted patterns is greatly reduced. As a result of this project, the algorithms have been tested on real logs generated by the management process of patients with valvular heart diseases in the cardiology service of the University Hospital Complex of Santiago de Compostela (CHUS) over the course of a year. • RAI4P - Responsible AI for Process Mining 2.0. The objective of this project is the development of predictive monitoring techniques for process mining that allow to forecast different features of the executions, such as the next activities or the remaining time. Specifically, the algorithms presented in this dissertation have been integrated in several prediction algorithms, so that the prediction takes into account possible changes in the processes before producing an output. • INCEPTION - Intelligent Handling of Concept Drift in Process Mining Supported by Cloud Computing. This activity is a proof-of-concept project in which the concept drift detection algorithms developed in the context of the BIGBISC project are deployed to a distributed infraestructure in the cloud. The solution is accesible through a set of REST APIs, which makes it independent and easily integrated into any existing platform. As part of this project, the algorithms developed during this Ph.D. dissertation have been adapted to support large amounts of data from complex and weakly structured processes, and the implementations have been optimized in order to obtain results in these contexts in a reasonable time. Specifically, the algorithms have been modified in two perspectives: on the one hand, integrating clustering algorithms to split complex processes in smaller and simpler subprocesses; and, on the other hand, modifying the regression methods used to detect changes in order to make them robust to noisy executions in weakly structured processes. • INSIDE - Emotion-aware Process Mining for Improving the Adherence in Cardiac Rehabilitation. The objective of this research project is to provide insights about the 18 Chapter 1. Introduction adherence of patients to Cardiac Rehabilitation processes by combining process mining techniques with patients mood recognition based on the use of wearable devices. Specifically, the algorithms presented in this Ph.D. dissertation are used to evaluate how the changes in the structure of the cardiac rehabilitation process affect the the causality of patients dropouts. • RCIS - Service Science and Engineering Network. During the development of this Ph.D. dissertation I have actively participated in the Service Science and Engineering National Network (TIN2014-53986-REDT), which brings together the leading experts in servitization and process mining in Spain. As a result of this collaboration several algorithms developed in the framework of this Ph.D. dissertation were published through publically accesible REST APIs. 1.4 Other Contributions The development of this Ph.D. dissertation has also led to the following, more technical, contributions: 1. Sudden drift logs - A dataset for validating sudden drift detection algorithms. As a part of the development of C2D2, three datasets composed by multiple log files have been generated. Specifically, three models from the state of the art in process mining —a loan application process [ 20 ], a hospital emergency ward process [ 49 ] and a central venous catheter process [ 50 ]— have been used, generating, for each applicable change pattern [ 48 ], 4 logs with 4 different sizes — 2,500 , 5,000 , 7,500 and 10,000 traces—. Specifically, 204 log files have been generated. This dataset, available online 1 , has been designed to be used as a benchmark for testing control-flow sudden drift detection algorithms. 2. Gradual drift logs - A dataset for validating gradual drift detection algorithms. As a part of the development of CRIER, one dataset composed of multiple event logs has been generated, using the same loan application process and change patterns from the sudden drift logs. In total, 120 event logs have been generated, with 12 different probability distributions for transitioning between the models. This dataset, available 1https://gitlab.citius.usc.es/ProcessMining/logs/-/tree/master/drift/sudden 19 Víctor José Gallego Fontenla not perform well in processes with loops, which affects the accuracy results. Also, as in the previous approach, the delay results are very dependant on the size used for splitting the log. Finally, the graph features considered for comparing models do not take into account small differences in the graphs, so the method will perform poorly in noisy environments. Clustering-based approaches In [ 16 ], the authors propose an online approach based on the extraction of histograms from traces and then use a clustering algorithm to generate groups of similar traces. A change is triggered when a new cluster appears. An important drawback of this approach is that it does not take into account the order of events. Thus, it can only detect the addition or removal of new activities, but not the changes in the precedence relations between them, so accuracy results are poor for some change patterns. In [ 18 ], the authors cluster traces using the distance between pairs of activities. However, this approach does not support models with loops. Moreover, the distance can ignore certain change patterns depending on how many activities are affected by the change, having an impact on the accuracy values. In terms of delay, both approaches should perform well, as the cluster count is not specified a priori, so the log should be split right at the point where the drift happens. Also, both algorithms should be acceptably robust, as long as the clustering does not create a new group when anomalous executions appear. In [ 17 ], the authors extend a trace clustering algorithm [ 67 ] adding a time dimension to force clusters to include only consecutive traces, and thus be able to detect changes. The advantage of this approach is that the delay results should be good, as the log is ideally split just where the change happens. However, the approach highly depends on the number of clusters, fixed by the user, and only obtains good results when the number of clusters is equal to the number of changes, thus impacting both accuracy —if the number of clusters is different from the number of changes, false positives and negatives will appear— and robustness —high number of clusters can lead to noisy executions creating a wrong cluster—. In [ 19 ], the authors use a Markov clustering algorithm over different time windows to detect changes, but the approach does not focus on the control-flow perspective. Instead, multiple viewpoints of the process are taken into account simultaneously, mixing control-flow changes with behavioral and resource changes. Also, the accuracy for the detection is highly dependent on the features used to represent the traces, which can ignore certain change patterns. In terms of delay, results depends on the choosen window size used for computing traces features, getting acceptable results if the window size is small enough, but worsening if the window size is too 26 Chapter 2. Related work big. Finally, the approach should be quite robust as long as the clustering approach should not create new clusters if the noise is evenly distributed along the log. Windowing and statistical analysis-based approaches In [ 58 ], the authors propose a method for online concept drift detection using a polyhedron-based log representation. Then, they monitor the probability that a trace falls into that polyhedron using the ADWIN algorithm [ 68 ]. The main drawbacks of this approach is that it cannot detect all change patterns, penalizing accuracy. Also, the method is not robust as it does not consider the presence of noise in the executions, taking all behaviour as expected. Online detection is also addressed in [ 59 ], where the authors discover a probabilistic process model that, given an activity, assigns a probability to every possible successor, and checks how these probabilities evolve throughout the complete log using statistical hypothesis tests. Although the method identifies drifts in most cases, small changes in less likely activities generate changes in the probabilities that can still remain undetected, penalizing accuracy. However, this also makes the approach somewhat noise robust, as low frequency behaviour should not affect its performance. With respect to delay, both algorithms are expected to perform well, as they run online, so the drift can be detected just when it happens. In [ 45 ], the authors use a fixed-size window over some features extracted from the follows/precedes relations present in traces, and statistical hypothesis tests to evaluate whether these features have changed significantly. The weak point of this method is that it requires a lot of interaction from the user, including previous knowledge of the process model and the areas where the changes can be located. An extension of this work has been proposed in [ 60 ], where the authors implement a recursive bisectioning approach. Specifically, they take the traces that are involved in a drift detection and recursively split them into halves, intending to automatically localize the change. A drawback of this approach is that it still requires the user to know the possible changes to obtain good results. The accuracy of these two approaches is highly tied to the features choosen to evaluate changes, penalizing accuracy if the choosen feature is not able to capture some change patterns. In terms of delay, the first one is highly dependent on the choosen window size. The second one reduces the delay, as it adjusts the window size automatically to better localize the drift. A similar solution is presented in [ 61 ], where the authors propose the usage of event class correlation as a feature, and apply statistical hypothesis tests to detect changes. This approach fails in detecting some change patterns such as the changes in the execution order of activities, penalizing again the accuracy. Also, it inherits 27 Víctor José Gallego Fontenla the drawbacks from [ 45 ] related to the behavior of the delay. Among these three proposals, just [ 60 ] takes into account the concept drift detection in noisy environments, providing some support for detection in these contexts. Another interesting approach, called ProcessDrift, was proposed in [ 63 ], where the authors transform traces into partial-ordered-runs and then apply a statistical hypothesis test over two windows (one for reference and one for detection) to detect changes. The main drawback of this approach lies in its sensitivity to changes in the frequencies of certain relations present in the log, which may lead to false positives in the detection, which impacts accuracy. A related method is presented in [ 64 ], where the authors focus on detecting the change at the event level instead of at trace level. Specifically, they extract the 𝛼+ relations from two consecutive adaptive windows of events and, then, applying a statistical test, namely the G-test, compare the relations distribution of these two windows. This allows to detect changes even with unfinished executions, and reduce the detection delay. The drawback of this approach is that it requires high amounts of traces to be able to detect changes. Furthermore, changes that are close to each other may be ignored, which again has an impact on the accuracy. In terms of delay, both approaches should obtain good results, as they use overlapping sliding windows, so the change can be precisely pinpoint when it happens. Only the second one of the approaches consider the presence of noise in the log, improving the results of the first one, but it still restricts itself to linear combinations of behaviour, limiting its applicability to noisy environments. In [ 65 ], the authors present TPCDD, a method that transforms the event log into a relation matrix using direct succession and weak order relations, where each column represents a trace and each row a relation. Then, based on the trend of these relations, it generates candidate drift points. These points are clustered using DBSCAN, to group candidates that belong to the same drift point. This approach relies heavily on a correct radius for the DBSCAN algorithm, detecting all change patterns but potentially getting a high number of false positives when it is too low and a high number of false negatives when it is too high. Also, the algorithm shows good results in terms of delay, but it does not deal with noisy traces, leading it to poor results in noisy environments. In [ 66 ], the authors propose an algorithm for detecting sudden drifts in event streams using relation frequency maps and an adaptive window. They propose the use of an ADWIN with different distances between these frequency matrices, so a change would be detected if two consecutive frequency maps are different enough. The main drawback with this approach lies in choosing a good distance metric to detect all change patterns in any context, having an 28 Chapter 2. Related work Table 2.1: Approaches for sudden drift detection from the state of the art and their performance for accuracy, delay and robustness perspectives. Approach Accuracy Delay Robustness Stertz and Rinderle-Ma [11] Model-to-log alignment − ± ± Lakshmanan et al. [14] Graph analysis − − − Seeliger et al. [15] Graph analysis − − − Junior et al. [16] Clustering − + ± Accorsi and Stocker [18] Clustering − + ± Luengo and Sepúlveda [17] Clustering − + − Hompes et al. [19] Clustering − ± ± Carmona and Gavaldà [58] Windowing plus statistical analysis − + − Weber et al. [59] Windowing plus statistical analysis − + + Bose et al. [45] Windowing plus statistical analysis − − − Martjushev et al. [60] Windowing plus statistical analysis − + ± Kumar et al. [61] Windowing plus statistical analysis − − − Maaradji et al. [63] Windowing plus statistical analysis ± ± − Ostovar et al. [64] Windowing plus statistical analysis ± + ± Zheng et al. [65] Windowing plus statistical analysis ± + − Hassani [66] Windowing plus statistical analysis − − − impact on accuracy, delay and robustness. Table 2.1 provides a summary of the performance of the state of the art approaches. It is worth noting that only the approaches presented in [ 64 ] and [ 65 ] exhibit a good accuracy in detecting changes, regardless of the type of change patterns, while still maintaining a low delay. 2.2 Gradual drift detection The number of proposals present in the state of the art is fairly reduced for gradual drift detection. This may be due to the lack of base solutions that provide sufficiently good results that can be adapted to the detection of gradual changes in the process control-flow. 29 Víctor José Gallego Fontenla Model-to-log alignment-based approaches In [ 13 ], the log is transformed into a time series using a feature called r-measure that compares the relation matrices between two consecutive windows. Then, the algorithm looks for outliers in these time series, and determines that a change exists when one is detected. The main drawback of this approach is that it does not distinguish sudden and gradual drifts and it is prone to mix up changes with outliers, impacting accuracy and robustness. Moreover, it is also not extensively tested, being evaluated against 4 synthetic logs, where they obtain highly variable results for accuracy, with values between 0.6 and 0.95 depending on the used parameters. On the good side, the algorithm is expected to perform well in terms of delay, as nothing prevents it from detecting the drift just when it happens. In [ 11 ], the authors propose an algorithm that deals with a stream of events, allowing the detection of changes in incomplete traces. Using a window of a given size, different versions of the process model are discovered —the process history— and the fitness is computed against the last mined model. In this approach, a change is present when the fitness of a trace is below a threshold. Then, detected changes are classified in sudden, gradual, incremental or recurring based on the number of process histories available, their fitness values and the presence of unfinished traces in the moment the process changes. Thus, when a trace does not fit the last discovered model, a new one is mined using only the unfitting traces. To prevent false positives, each model also receives an score, and a model is considered to change only when that score is over a threshold, making the algorithm robust to noisy executions if the threshold is choosen correctly. As a disadvantage, increasing the threshold will penalize delay, as the algorithm has to wait more until confirming a drift. Finally, changes are classified in sudden, gradual, recurring and incremental using both two new thresholds and the process history. The main drawback of this approach is that it requires the user to have a deep knowledge of the problem in order to tune the hyperparameters used in the detection —the window size and 4 different thresholds—. Furthermore, the algorithm can not detect all structural change patterns, e.g., the transformation of an optional parallel structure into an exclusive choice where the order of some activities is enforced, having a negative impact in accuracy. Also, the approach has not been extensively tested and no quantitative measures are provided about the goodness of the results. In [ 12 ], the authors propose a method that is also based on the idea of using the process model for detecting changes. This approach splits the log in 𝑛 windows of size 𝑚 . Then, a set of declarative rules is extracted from the complete log and their confidence is computed 30 Chapter 2. Related work with respect to each window, obtaining a multivalued time series. Finally, a traditional concept drift detection algorithm —namely, the PELT algorithm— in combination with a hierarchical clustering technique is used to detect changes in the resulting time series. The main drawback with this approach is that the classification of changes in sudden or gradual is not automatic, but it must be performed visually by the user. Also, results are highly dependent on the size of the window, penalizing accuracy and delay if the window size is not choosen properly. As a positive thing, the extraction of rules over a large enough window gives the method some noise robustness. Regarding the validation, the algorithm shows promising results for the detection, but it is only tested with 4 synthetic and 2 real logs. Clustering-based approaches In [ 17 ], the authors propose the use of an agglomerative hierarchical clustering over the traces to detect changes. For the clustering, traces are transformed to feature vectors that abstract the trace behaviour. Specifically, the maximal repeat [ 67 ] and the starting timestamp of the trace are used as features. Once the clusters are generated, they define a change as the point in time where one cluster ends and a new one starts. However, this method is very dependent on the number of clusters, which should be fixed by the user and equal to the number of changes present in the log. Choosing the right number of clusters should lead to low delay values, since the log will be split just in the point where the change happens. On the other hand, choosing a wrong cluster count will higly impact on accuracy and robustness, with poor results due to false detections. Regarding the experimentation, the approach is only validated using 3 logs, with an accuracy —calculated as the sum of true positives and true negatives, and divided by the total number of traces— between 57% and 100%. In [ 69 ], authors propose an online approach where they use a clustering approach over graph distances. The approach takes as input an event stream, and updates the corresponding trace graph every time a new event is received. When they have enough traces, a process model is discovered by generating two weighted graphs: in one of them, the weight of the arcs represents the frequency of the transitions between activities; and in the other one, the average time between activities is the arc weight. Then, a distance between the trace graph and these two weighted graphs is computed, and these distances are grouped using a online density-based clustering algorithm —namely, DenStream—, which provides some robustness to noise. Due to this computation being performed per trace, the delay values are expected to be very low. Regarding the validation, the approach is tested using 18 synthetic logs, but the 31 Víctor José Gallego Fontenla only metric provided is the number of changes detected. The main drawback of this method is that it mixes control-flow and behavioral changes, penalizing its accuracy. Also, it requires a lot of hyperparameters to be tuned by the user in order to obtain good results. Finally, as many of the presented proposals, it supports the detection over logs with gradual changes, but does not distinguish between sudden and gradual changes. Windowing and statistical analysis-based approaches In [ 45 ], authors present an approach that computes features from follow/precede relations and use a statistical hypothesis test to check if there are changes in the features over time, specifically over two consecutive fixed size windows. Examples of these features are: for each activity of the log, the number of activities that always, sometimes and never follow/precede a given activity; for each pair of activities 𝛼1 and 𝛼2 of the log and for each trace, the number of sequences of size 𝑛 that start with 𝛼1 and contain 𝛼2 ; for each pair of activities 𝛼1 and 𝛼2 of the log and for each trace, the significance of 𝛼1 following/preceding 𝛼2 with a maximum distance of 𝑛 ; etc. The main drawback of this approach is that it does not distinguish between sudden and gradual changes and it deals only with linear distributions for gradual changes, which limits its accuracy and robustness to some types of drifts, and that it is very dependant on choosing the right window size, affecting delay. Additionally, it requires the user to have an advanced knowledge of the process, including which features to select, the activities that can change or the statistical test to be used in order to process the log. Furthermore, the approach is not extensively tested, being validated only with two synthetic logs and a real one, without providing any quantitative assessment of the results, although they seem to be promising. An extension to this approach is presented in [ 60 ], where the authors propose the use of non-consecutive windows, leaving a gap between them, in order to increase the difference between features in gradual environments in order to reduce the false negatives. In this extension, the restriction of gradual drifts distribution is removed, so the algorithm can detect also changes that are not linear, improving its robustness. Yet, the approach fails to provide a solution able to identify all drift patterns distinguishing if a change is sudden or gradual, requires even more knowledge from the user to set other parameters —as the size of the gap between the windows—, and still does not provide quantitative metrics in the validation, which is performed only over 2 logs. Another very interesting proposal, halfway between the extraction of features and the use of a process model, is the one presented in [ 62 , 63 ]. In this approach, the behavior of the traces is abstracted using partial-ordered-runs —i.e., a graph representation of the traces—. Once the 32 Chapter 2. Related work Table 2.2: Approaches for gradual drift detection from the state of the art and their performance for accuracy, delay and robustness perspectives. Approach Accuracy Delay Robustness Li et al. [13] Model-to-log alignment − + − Stertz and Rinderle-Ma [11] Model-to-log alignment − ± ± Yeshchenko et al. [12] Model-to-log alignment − − ± Luengo and Sepúlveda [17] Clustering − + − Tavares et al. [69] Clustering − + + Bose et al. [45] Windowing plus statistical analysis − − − Martjushev et al. [60] Windowing plus statistical analysis − + ± Maaradji et al. [63] Windowing plus statistical analysis ± ± − behavior is abstracted, two consecutive sliding windows are used and, by means of a statistical test, it is checked if the content of these windows is significantly different. The fact that it uses two consecutive sliding windows allows the algorithm to detect changes with a low delay. Once the changes are detected, a classification is performed to guess if they represent a sudden or a gradual drift. In this classification, a statistical test checks if the combination of traces between two consecutive changes represents a linear combination of the traces before and after the first and second changes, respectively. This is one of the most thoroughly validated proposals, tested with multiple logs. The main drawback of this approach is that it can be very sensitive to changes in the frequencies of the relations, which may lead to the detection of false positives, penalizing accuracy. Also, the algorithm can only detect gradual changes that are due to a linear distribution of the traces between two models, which may not be the case in real logs, affecting negatively its robustness. Table 2.2 provides a summary of the performance of the main state of the art approaches, showing that no approach provides good results in terms of accuracy, being [ 63 ] and [ 60 ] the best positioned ones. However, there are approaches that achieve good or acceptable results in terms of delay —[13, 17, 60, 69]— and robustness —[11, 12, 60, 63]—. 33 Víctor José Gallego Fontenla 2.3 Conclusions As a summary, there is no approach that provides a fully automated solution for detecting sudden and gradual changes, supporting all types of change patterns and trace distributions, and having an exhaustive validaton that detect changes with high accuracy and low delay. With C2D2 and CRIER we address the aforementioned issues, improving the results of the process drift detection. Proposed methods remove any user interaction in drift detection, requiring only a minimum window size to be specified. Moreover, both methods can detect all change patterns independently of the process structure. Finally, with R-CRIER we try to tackle the problem of applying this kind of methods to environments where the presence of noise can make it difficult do distinguish a real change from noisy anomalous executions. Furthermore, the three proposed methods are designed to identify drifts with low delay and a high accuracy, minimizing the detection of false negatives and positives. They have been deeply validated using a variety of synthetic logs from models from the state of the art, showing better results than the ones obtained by the main state of the art approaches. 34 CHAPTER 3 SUDDEN DRIFT DETECTION Change is the only thing that is immutable. — Arthur Schopenhauer In this chapter, we present C2D2 (Conformance Checking-based Drift Detection), an algorithm for offline sudden control-flow drift detection in process mining. C2D2 relies on the hypothesis that changes in the model structure (drifts) can be detected by changes in its fitness and/or precision. Therefore, by continuously monitoring the conformance metrics of a process, these drifts may be detected. To illustrate this idea, let’s take the example in Figure 3.1. Let us suppose the models 𝑁1 and 𝑁2 depicted in Figures 3.1a and 3.1b. The difference between both models is that activities 𝐵 and 𝐶 are in parallel in 𝑁1 , but in sequence in 𝑁2 . Let us also suppose that the process 𝑁1 changes to 𝑁2 at instant 𝑖=8 , which log is represented in Figure 3.1c, henceforth denoted as 𝐿1 . Traces 𝜏1 to 𝜏8 correspond to the execution of 𝑁1 and traces 𝜏9 to 𝜏16 correspond to 𝑁2 . In 𝐿1 , the concurrent execution of activities 𝐵 and 𝐶 becomes a sequence from 𝜏9 onwards. After this change, traces are still replayable, so the fitness remains unaltered. However, no trace in the window contains the path 𝐴→𝐶→𝐷 from 𝜏9 onwards, so the precision falls. This can be seen in Figure 3.1e, where precision falls because the model allows more behaviour than is present in the traces, but fitness remains unaltered. Víctor José Gallego Fontenla Algorithm 3.2 Automatic window size optimizer Inputs: an event log 𝐿and a minimum window size 𝑛 < |𝐿| Outputs: the optimal window size for processing 𝐿 1: function AdjustWindow(𝑛, 𝐿) 2: 𝑁1, 𝑁2, 𝑁3← ∅ 3: 𝑛′←𝑛 4: while 𝑁1=𝑁2=𝑁3do 5: 𝑁1←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (⟨𝜏0, . . . , 𝜏𝑛′⟩) 6: 𝑁2←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (⟨𝜏𝑛′, . . . , 𝜏2𝑛′⟩) 7: 𝑁3←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (⟨𝜏2𝑛′, . . . , 𝜏3𝑛′⟩) 8: if 𝑁1=𝑁2=𝑁3then 9: 𝑛′←𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡 (𝑛′) 10: end if 11: end while 12: return n’ 13: end function change every 250 traces. In the case of pl (Figure 3.2a), two fragments that are originally executed in a concurrent form are transformed into a sequential execution, which should imply a reduction in precision but not in fitness. In the case of cb (Figure 3.2b), a fragment is transformed from mandatory to skippable, which should imply a reduction in fitness but not in precision. 3.2.2 Adjusting the Window Size When some behaviour appears in some traces but not in the model, they can be initially considered as outliers. But when this behaviour persists for a long time, it can be flagged as a change, having the organization an opportunity to enhance its process. Something similar happens when some behaviour is no longer observed in the log. A path of the process that is not present during a short period of time can be seen as a temporary exception. But if this behaviour is absent for a long time, some optimizations can be made to improve the process performance. Hence, small windows will detect less durable changes, while larger window sizes will detect changes that persist. Adjusting the window size for processing the log is not a trivial task. A small window would led to multiple false detections, due to the window not containing enough information to describe the process executed at a given instant. On the other hand, a big window would not detect some changes, because the reference window will contain traces from before and after the change. Thus, a good balance between the two options is essential. To adjust the 42 Chapter 3. Sudden drift detection 𝜏1𝜏2𝜏3𝜏4𝜏5𝜏6𝜏7𝜏8𝜏9𝜏10 𝜏11 𝜏12 𝜏13 𝜏14 𝜏15 𝜏16 Change 𝜔6𝜔12 𝜔5𝜔10 𝜔15 Added Behaviour Removed Behaviour Added Behaviour Removed Behaviour 𝑁2≠𝑁1 𝑁1=𝑁1 𝑁2≠𝑁1=𝑁1 𝑁1=𝑁1≠𝑁2 Figure 3.3: Behaviour of the adaptive window in the example from Figure 3.1. Log correspond with the one in Figure 3.1c and Figure 3.1d for removing and adding behaviour, respectively. 𝑁1and 𝑁2refer respectively to the models in Figure 3.1a and Figure 3.1b. window size, C2D2 uses an approach based on the comparison of models from consecutive sublogs (Algorithm 3.2). We start with three empty models (line 2) and a window size 𝑛′ , that is initialized to the minimum window size 𝑛 (line 3). Then, three new models for three consecutive sublogs are discovered with the same discovery algorithm used for the detection (lines 5 to 7). If these three discovered models are equal, we increment the window size and try again (lines 8 to 10). Else, if any of the discovered models differ from the rest, the procedure finishes and the last 𝑛′ is used as the window size. By default, we use a minimum window size of 1% and an increment of 0.1% of the log size. Figure 3.3 shows why three consecutive models are required. Let us consider the log in Figure 3.1d, that presents a change between traces 𝜏8 and 𝜏9 . The change consist in some behaviour being added to the process (the execution of 𝐵 before 𝐶 is replaced by a concurrent execution of these two activities). In this case, using two windows, one that contains behaviour from before the change and one that contains behaviour from both before and after the change, is enough because the models will be different. Consider now the log in Figure 3.1c, that also contains a change between traces 𝜏8 and 𝜏9 . This time, the change consists in some behaviour being removed from the process (the execution of 𝐶 before 𝐵 disappears from the log). In this case, when using just two windows, the model discovered with traces from both pre- and post-drift traces reflects no changes, because the missing path is present in the pre-drift traces used for discovery. In this scenario three windows, with their respective models, are required: one to depict the behaviour of the process before the change, one to detect both pre- and post-drift behaviour, which will be the same as in the pre-drift case, and one to represent the behaviour after the change. 43 Víctor José Gallego Fontenla 3.2.3 Conformance metrics change estimators Traditional fitness and precision metrics are designed to assess the global quality of a model. These metrics use different approaches to compute fitness and precision in a reliable way, giving each trace a score in a continuous scale depending on how well they conform to the model, rather than following a discrete approach where traces can only get a binary rating for conformance. C2D2 use these metrics to detect structural changes during the execution of a process. Moreover, we propose two simpler fitness and precision metrics aside from the well-established metrics from the state of the art. These two approaches have much lower computational complexity and were designed to detect changes in simple and noise-free logs. In the case of fitness, we use the percentage of replayable traces. This approach is not particularly useful for measuring the quality of a model, since it equally penalizes traces that do not fit the model and those that deviate slightly from it. Despite this, it can be used to estimate changes in fitness, since a change in the percentage of traces that can be replayed in the model always leads to a change in the metric value. For precision, the following approach is used: PC =1−|OLP \DFR| |OLP|(3.1) where: • A set of one-length paths (OLP) is extracted from the model. An OLP is a pair of activities that are directly connected in the process model, without any other activity in between. • A set of directly-follows relations (DFR) is extracted from the log. A DFR is a pair os activities that appear one after the other in the log, without any activity in between. •Operator \is the difference between two sets. Equation (3.1) does not measure the precision per se, but the change in the precision. The moment a OLP stops appearing in the log is indicative that some path of the model has disappeared. The proposed approach returns 1 when all the supported behavior of the model appears at least once in the log, and 0 otherwise, i.e., when none of the behavior supported by the model appears in the log. The computation of this metric is illustrated with an example in Figure 3.4. 44 Chapter 3. Sudden drift detection 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 Figure 3.4: PC computation example. Colored in green are the arcs that appear in the log. Colored in grey those that do not appear. 3.3 Experimentation Concept drift algorithms are assessed based on two quality measures: On the one hand, 𝐹𝑠𝑐𝑜𝑟𝑒 (Equation (3.2a)), which is an accuracy metric computed as the harmonic mean between precision (Equation (3.2b)) and recall (Equation (3.2c)): 𝐹𝑠𝑐𝑜𝑟𝑒 =2×𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 ×𝑟𝑒𝑐𝑎𝑙𝑙 𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 +𝑟𝑒𝑐𝑎𝑙𝑙 (3.2a) 𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 =𝑇𝑃 𝑇𝑃 +𝐹𝑃 (3.2b) 𝑟𝑒𝑐𝑎𝑙𝑙 =𝑇𝑃 𝑇𝑃 +𝐹𝑁 (3.2c) On the other hand, delay (henceforth Δ ), which is the distance between the point when the change really happened and when it is detected: Δ(𝑑𝑅, 𝑑𝐷)=|𝑑𝑅−𝑑𝐷|(3.3) To classify the detected changes as true positives ( TP ), false positives ( FP ) or false negatives ( FN ), we use a threshold 𝜀 , that represents the error tolerance of the quality measures, and a neighborhood 𝛿𝜀 𝑖 , defined as the interval between 𝑖−𝜀 and 𝑖+𝜀 . Let a change happen at instant 𝑖 . This change is classified as a TP only when it is detected in 𝛿𝜀 𝑖 . When no change is detected in 𝛿𝜀 𝑖 it is classified as FN . Finally, all changes detected in 𝛿𝜀 𝑖 where a previous change has been already detected are classified as a FP , as well as the ones detected outside any 𝛿𝜀 . Figure 3.5 shows an example with two real changes ( 𝑑5 , at instant 5 , and 𝑑20 , at instant 20 ), 45 Víctor José Gallego Fontenla 0 5 10 15 20 25 𝛿5 5𝛿5 20 TP FP FP FN Figure 3.5: Change results classification in TP , FP and FN . A dot represents a real change. A cross represents a detection. Shadowed are the neighborhoods for 𝜀=5. and three detections, at instants 4 ( 𝑐4 ), 7 ( 𝑐7 ) and 12 ( 𝑐12 ), using a 𝜀=5 . In this example, 𝑐4 is classified as a TP , because it lies in the neighborhood of 𝑑5 ; 𝑐7 is classified as a FP , because, despite being in the neighborhood of 𝑑5 , another change has been detected previously; 𝑐12 is classified too as a FP , in this case for being detected outside any neighborhood 𝛿5 ; and finally, 𝑑20 is classified as a FN since no change is detected in its neighborhood. The algorithm implementation is published online and available as a REST API1. 3.3.1 Validation data Our proposal has been tested with three models extracted from the literature [ 20 , 49 , 50 ], which describe a loan application process, a hospital emergency ward process, and a central venous catheter process, respectively. These models are usually part of benchmarks for concept drift detection, process discovery and conformance ckecking. A set of sythetic logs for each one of the process models have been generated using the methodology and change patterns described in [ 63 ]. This is the most extended methodology [ 12 , 15 , 65 ] for generating datasets when validating sudden concept drift detection algorithms in process mining. For each process, we generated a dataset composed of 68 logs: 17 with 2,500 traces, 17 with 5,000 , 17 with 7,500 and 17 with 10,000 . The original dataset from [ 63 ] contains 4 more logs, one for each of the sizes, but they have been discarded because its drift pattern —changing the frequency of the branches in a choice construct— does not affect the control-flow of the process, but the behaviour of the users. Only the results of the experiments with one of the models —namelly the loan application process— are shown in this chapter. Detailed results for the other two models can be found in Appendix A. The Petri net corresponding to the loan application process is depicted in Figure 3.6. To generate the 17 modified models, 11 simple change patterns from [ 48 ] are applied to the original process. These patterns can be classified into three categories (Table 3.1): (i) changes involving the insertion of new behavior —marked with 𝐼 —; (ii) changes involving the optionalization 1https://tec.citius.usc.es/concept-drift-api/swagger-ui.html 46 Chapter 3. Sudden drift detection A B C D E F G H I J K L M N O P Q R S Figure 3.6: Petri net for the original loan application process model [ 63 ] used to generate logs. Activity names are shortened for better understandability. Table 3.1: Change patterns applied to the original model from Figure 3.6 and resulting models. (a) Change patterns. Code Change pattern Class cm Move fragment into/out of conditional branch I cp Duplicate fragment I pm Move fragment into/out of parallel branch I re Add/remove fragment I rp Substitute fragment I sw Swap two fragments I cb Make fragment skippable/non-skippable O lp Make fragments loopable/non-loopable O cd Synchronize two fragments R cf Make two fragments conditional/sequential R pl Make two fragments parallel/sequential R (b) Derived models. Model code Change patterns cm cm cp cp pm pm re re rp rp sw sw cb cb lp lp cd cd cf cf pl pl OIR lp + re + cd ORI lp + pl + re RIO cf + cp + cb ROI pl + lp + rp of a part of the model —marked with 𝑂 —; and (iii) changes involving the restructuring and rearrangement of some parts of the model —marked with 𝑅 —. In addition, another 6 models are generated by applying a combination of simple change patterns —one pattern from each of the previously named categories— to build a complex change pattern. Once all the models are available, the logs are generated simulating executions of those processes. The original log is then combined with the modified ones to generate logs with drifts. The final log is composed joining alternatively sublogs from both the original model and the modified ones. Each drifting log presents a change every 10% of its final size. A log generation example is represented in Figure 3.7. Two logs ( 𝐿1 and 𝐿2 ) with different models are split in 5 sublogs with equal sizes ( 𝐿1 1 to 𝐿5 1 and 𝐿1 2 to 𝐿5 2 ). This sublogs are combined alternatively into a log 𝐿, with size |𝐿1|+|𝐿2|. 47 Víctor José Gallego Fontenla 𝐿1generation 𝐿generation 𝐿2generation 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 Figure 3.7: Log generation example. 3.3.2 Conformance checking metrics and discovery algorithm impact In order to check the impact of the discovery algorithm and the conformance metrics in C2D2 performance, different configurations have been tested: 1. Discovery algorithms: Inductive Miner ( IM ) [ 23 ] and Heuristics Miner ( HM ) [ 71 ], which are two of the most used methods for discovering models from event logs. No algorithm based on evolutionary computation has been selected because it would increase the computational complexity significantly. 2. Fitness metrics: Alignment Based Fitness ( AF ) [ 72 ], Negative Event Recall ( NR ) [ 34 ] and the percentage of completely Replayable Traces (RT) from Section 3.2.3. 3. Precision metrics: Advanced Behavioural Appropriateness ( ABA ) [ 35 ], Negative Event Precision (NP) [34] and Precision Change assessment (PC) from Section 3.2.3. The key when choosing a discovery algorithm and a pair of fitness and precision metrics is to obtain a combination that allows the results of the regression to stabilize around a value, so the slope is zero while there are no changes. If we focus on fitness, reaching a constant value in absence of changes is easier if we use a discovery algorithm that ensures traces replayability, 48 Chapter 3. Sudden drift detection Table 3.2: Mean Δ and 𝐹𝑠𝑐𝑜𝑟𝑒 for every tested configuration over the 2,500 traces logs for the loan application process. Window size has been fixed to 100 traces. Best results are shadowed in a darker grey and runners-up in a lighter one. Error tolerance has been set to a 5% of the 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 Inductive Miner. However, if we use a discovery algorithm that does not ensure traces replayability, such as Heuristics Miner, the selected metric should take this into account, or the obtained values will not stabilize, so more false positives will be notified. This can be seen in the experiments in Table 3.2, where the results of Inductive Miner do not change significantly no matter which fitness metric is used. On the contrary, when we use Heuristics Miner, best results are obtained when a more robust fitness metric is used (e.g., alignments based one vs. percentage of replayable traces). On the other hand, if we focus on precision, the chosen discovery algorithm has less impact, as none of the discovery algorithms used in the experimentation ensures a perfect precision. When computing precision, situations in which a path from the model is only present in few traces (or even in none) are quite common, so the metric can oscilate a lot. With the use of the 𝑃𝐶 precision metric this is partially addressed, because this metric does not take into account how many times a path occurs but only its presence. This forces the metric to converge 49 Víctor José Gallego Fontenla 50 100 150 200 250 0 0.5 1 𝐹𝑠𝑐𝑜𝑟𝑒 𝐹𝑠𝑐𝑜𝑟𝑒 0 20 40 60 Δ Δ (a) Loan application. 50 100 150 200 250 0 0.5 1 𝐹𝑠𝑐𝑜𝑟𝑒 𝐹𝑠𝑐𝑜𝑟𝑒 0 20 40 60 Δ Δ (b) Hospital emergency ward. 50 100 150 200 250 0 0.5 1 𝐹𝑠𝑐𝑜𝑟𝑒 𝐹𝑠𝑐𝑜𝑟𝑒 0 20 40 60 Δ Δ (c) Central venous catheter. Figure 3.8: Mean 𝐹𝑠𝑐𝑜𝑟𝑒 (higger is better) and Δ (lower is better) evolution using the 2,500 traces logs and different window sizes. Shadowed in green is the optimal region. quickly, so the regression slopes are near to zero earlier, and change more abruptly when the path disappears competely from the executions. Taking into account the former results, the experiments in the following sections have been performed using IM algorithm, RT fitness and PC precision. 3.3.3 Window size impact In this section we present the results of the experiments on the influence of the window size on the results. Figure 3.8 show how the window size affects mean 𝐹𝑠𝑐𝑜𝑟𝑒 and mean Δ for logs for the loan application process with 2,500 traces, changes every 250 traces, and without automatic window size adjustment. In all cases, the optimal window size for both 𝐹𝑠𝑐𝑜𝑟𝑒 and Δ ranges between 25 and 100 (this area is boxed in green). Sizes below 25 produce good results in terms of Δ , but strongly penalize the 𝐹𝑠𝑐𝑜𝑟𝑒 values. In this case, C2D2 identifies many false positives because the reference window does not include sufficient behavior to discover a model with a high fitness. C2D2 also gets a low 𝐹𝑠𝑐𝑜𝑟𝑒 for windows with more than 100 traces because the discovered model has a low precision, allowing too much behavior that is not present in the log, thus causing false negatives as the window contains behavior of both before and after the change. 3.3.4 Results and benchmarking In this section, C2D2 algorithm is compared with Trace-Based ProDrift (PD-T) [ 63 ], Event- Based ProDrift (PD-E) [ 64 ] and TPCDD [ 65 ], the three sudden process drift detection algorithms with best results in the state of the art. Specifically, we used the following configurations: 1. PD-T with an adaptive window and an initial size of 50. 50 Chapter 3. Sudden drift detection 2. PD-E with an adaptive window and an initial size of 50 .Relation noise filter threshold was set to 0% and sensitivity to very high, as the authors recommend for analyzing synthetic logs without noise. 3. TPCDD minimum window size set to 100 and DBSCAN radius to 10. Table 3.3 shows the results for the loan application process logs —further detailed results for the central venous catheter and the hospital emergency ward processes are available in Appendix A—. C2D2 outperforms the rest of algorithms in terms of 𝐹𝑠𝑐𝑜𝑟𝑒 in all the cases, except in OIR log, getting always the best average value. Moreover, C2D2 is also the second best in terms of delay, very close to TPCDD, and being all the values in the same order of magnitude. Table 3.3: Mean 𝐹𝑠𝑐𝑜𝑟𝑒 and Δvalues for each algorithm using the loan application process 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 cf 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 𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ Continues on next page 51 Víctor José Gallego Fontenla 3. Detect gradual changes with a low delay, so a change can be precisely localized in time. 4. Have a high accuracy, detecting all the changes without false alarms nor skipping changes. CRIER can detect gradual and sudden changes in event logs based on the change of conformance checking metrics —fitness and precision— over a sliding window, computing these metrics for the successive sliding windows from the start until the end of the log. The evolution of these conformance metrics is evaluated using linear regressions and hypothesis testing, so that a potential change is detected when the metric values change significantly. In order to identify gradual drifts, detected change points are analyzed. If the behaviour contained between two consecutive points is a combination of the behaviour present before the first point —detected as a change in fitness— and the behaviour after the second one —detected as a change in precision—, then the change is classified as gradual. This strategy for detecting gradual changes will be formally proven in the next section. 4.1 Gradual drift detection using conformance metrics A gradual change is defined between two instants 𝑡1 and 𝑡2 , where the process has a behaviour 𝐵1 before 𝑡1 , a different behaviour 𝐵2 after 𝑡2 , while 𝐵1 and 𝐵2 coexist in [𝑡1, 𝑡2] (see Definition 8). Theorem 4.1: All gradual drifts are characterized by a fitness change in t 1 and by a precision change in t2. Proof: Consider a log 𝐿 , with a gradual change between instants 𝑡1 and 𝑡2 , in which the new behaviour is first observed at 𝑡1 and some old behaviour is less and less frequently observed, until it disappears completely at 𝑡2 . Let us consider three disjoint sets of behaviour: •𝐵𝑐 , which contains the behaviour that appears throughout the whole duration of the log 𝐿and which can be empty; •𝐵𝑝, which contains the previous behaviour of 𝐿that disappears between 𝑡1and 𝑡2 and which cannot be empty; and •𝐵𝑛 , which contains the new behaviour that starts to appear after 𝑡1 and replaces 𝐵𝑝 58 Chapter 4. Gradual drift detection after 𝑡2and which also cannot be empty. Using these two instants 𝑡1 and 𝑡2 , we can split the log 𝐿 in three sublogs. Let 𝐿<𝑡1 be the log containing all the traces before 𝑡1 , 𝐿[𝑡1,𝑡2] be the log containing the traces between 𝑡1 and 𝑡2 , and 𝐿>𝑡2 be the log with the remaining traces after 𝑡2 . Similarly, we can define the corresponding behaviors for these logs as 𝐵𝐿<𝑡1=𝐵𝑐∪𝐵𝑝 , 𝐵𝐿[𝑡1,𝑡2]=𝐵𝑐∪𝐵𝑝∪𝐵𝑛 , and 𝐵𝐿>𝑡2=𝐵𝑐∪𝐵𝑛 , respectively, and the reference models 𝑁<𝑡1 , 𝑁[𝑡1,𝑡2] and 𝑁>𝑡2 that can be discovered from the traces of these logs, respectively. The values for fitness and precision before the change, i.e., 𝐿<𝑡1, can be computed as follows: 𝛾(𝐿<𝑡1, 𝑁<𝑡1)= |𝐵𝐿<𝑡1∩𝐵𝑁<𝑡1| |𝐵𝐿<𝑡1|= |(𝐵𝑐∪𝐵𝑝) ∩ 𝐵𝑁<𝑡1| |𝐵𝑐∪𝐵𝑝|= |(𝐵𝑐∩𝐵𝑁<𝑡1) ∪ (𝐵𝑝∩𝐵𝑁<𝑡1)| |𝐵𝑐∪𝐵𝑝| 𝜌(𝐿<𝑡1, 𝑁<𝑡1)= |𝐵𝐿<𝑡1∩𝐵𝑁<𝑡1| |𝐵𝑁<𝑡1|= |(𝐵𝑐∪𝐵𝑝) ∩ 𝐵𝑁<𝑡1| |𝐵𝑁<𝑡1|= |(𝐵𝑐∩𝐵𝑁<𝑡1) ∪ (𝐵𝑝∩𝐵𝑁<𝑡1)| |𝐵𝑁<𝑡1| Which can be simplified since 𝐵𝑐and 𝐵𝑝are disjoint sets: 𝛾(𝐿<𝑡1, 𝑁<𝑡1)= |𝐵𝑐∩𝐵𝑁<𝑡1|+|𝐵𝑝∩𝐵𝑁<𝑡1| |𝐵𝑐| + |𝐵𝑝|= |𝐵𝑐∩𝐵𝑁<𝑡1| |𝐵𝑐| + |𝐵𝑝|+|𝐵𝑝∩𝐵𝑁<𝑡1| |𝐵𝑐| + |𝐵𝑝| 𝜌(𝐿<𝑡1, 𝑁<𝑡1)= |𝐵𝑐∩𝐵𝑁<𝑡1|+|𝐵𝑝∩𝐵𝑁<𝑡1| |𝐵𝑁<𝑡1|= |𝐵𝑐∩𝐵𝑁<𝑡1| |𝐵𝑁<𝑡1|+|𝐵𝑝∩𝐵𝑁<𝑡1| |𝐵𝑁<𝑡1| Similarly, fitness and precision values in the change interval [𝑡1, 𝑡2] with respect to this same model 𝑁<𝑡1can be computed as follows: 𝛾(𝐿[𝑡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íctor José Gallego Fontenla This equation can be simplified since 𝐵𝑛 only starts to appear after 𝑡1 , i.e., 𝐵𝑁<𝑡1∩𝐵𝑛=∅ : 𝛾(𝐿[𝑡1,𝑡2], 𝑁<𝑡1)= |𝐵𝑐∩𝐵𝑁<𝑡1| |𝐵𝑐|+|𝐵𝑝|+|𝐵𝑛|+|𝐵𝑝∩𝐵𝑁<𝑡1| |𝐵𝑐|+|𝐵𝑝|+|𝐵𝑛| 𝜌(𝐿[𝑡1,𝑡2], 𝑁<𝑡1)= |𝐵𝑐∩𝐵𝑁<𝑡1| |𝐵𝑁<𝑡1|+|𝐵𝑝∩𝐵𝑁<𝑡1| |𝐵𝑁<𝑡1| Moreover, since 𝐵𝑝≠∅ and 𝐵𝑛≠∅ , |𝐵𝑐|+|𝐵𝑝|+|𝐵𝑛|>|𝐵𝑐|+|𝐵𝑝| . Thus, 𝛾(𝐿<𝑡1, 𝑁<𝑡1)> 𝛾(𝐿[𝑡1,𝑡2], 𝑁<𝑡1) but 𝜌(𝐿<𝑡1, 𝑁<𝑡1)=𝜌(𝐿[𝑡1,𝑡2], 𝑁<𝑡1) , confirming our hypothesis that fitness decreases at the beginning of a gradual drift, but precision remaining unaltered. Once the beginning of the drift has been detected, a new model 𝑁[𝑡1,𝑡2] is discovered using the log 𝐿[𝑡1,𝑡2] . Then, the conformance metrics can be computed using Definitions 5 and 6 as follows: 𝛾(𝐿[𝑡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 then proceed to define the values after 𝑡2, where 𝐵𝑝has totally disappeared: 𝛾(𝐿>𝑡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]| Nothing canbe affirmed withrespectto fitness, butwecanconclude that 𝜌(𝐿[𝑡1,𝑡2], 𝑁[𝑡1,𝑡2])> 𝜌(𝐿>𝑡2, 𝑁[𝑡1,𝑡2]), i.e., precision will decrease at the end of the gradual drift. 60 Chapter 4. Gradual drift detection A situation in which a gradual change starts with a change in precision at 𝑡1 is impossible, since the change in precision necessarily implies a sudden change in the model structure. Since this proof is straightforward, we did not include it in this dissertation — 𝐵𝑛=∅ , since no new behavior is added after 𝑡1 , otherwise a change in fitness should be present, and 𝐵𝐿<𝑡1=𝐵𝐿[𝑡1,𝑡2], which contradicts the Definition 9—. □ 4.2 Algorithm The premise underlying the operation of CRIER is that, using fitness and precision metrics, gradual drifts can be detected with high accuracy. To better understand how the algorithm works, we illustrate the gradual drift detection with the example of Figure 4.1. The example is based on a sliding window of size 4 . First, traces are read until the window is full. Then, traces from the first full window 𝜔4 are mined with a discovery algorithm to obtain the model that describes its behavior. Then, the window is shifted trace by trace and for each shift the fitness and precision —which are initially 1— are checked to detect whether they change. In the window 𝜔9 the fitness decreases while the precision does not change, so 𝜏9 is labeled as a drift candidate. The fitness decrease lasts for three windows, which means that traces from 𝜏10 to 𝜏12 are also drift candidates, so trace 𝜏9 is finally labeled as a drift. As a consequence, a new model is discovered at 𝜔12 , starting a new cycle of the algorithm, until a change in fitness or precision is detected in the next windows. In this example, a precision decrease is detected for the windows 𝜔20 , 𝜔21 , 𝜔22 and 𝜔23 , confirming a drift in trace 𝜏17 and, therefore, a gradual drift between traces 𝜏9and 𝜏17. Algorithm 4.1 shows the pseudocode of the CRIER algorithm. The only mandatory inputs are the event log and a minimum window size. As part of the initialization phase, the algorithm creates two empty lists for the confirmed drifts, one for sudden and one for gradual drifts (line 2) and sets the initial window index 𝑖=1 (line 4). As the algorithm is based on a sliding window 𝜔𝑖 (Definition 7), in this initialization phase its optimal size 𝑛 is computed (line 3) using the function AdjustWindow (Algorithm 4.2, lines 1 to 15). The adjustment of the window size is based on the comparison of the behaviour observed in three consecutive windows. In this step, we start with a size 𝑛′ initialized as the minimum window size 𝑛 and discover three models from three consecutive windows of size 𝑛′ (Algorithm 4.2, lines 5 to 7). If the three models capture the same behaviour (Algorithm 4.2, line 8), the size of each window 𝑛′ is incremented by 𝑛′ (Algorithm 4.2, line 9) and the process starts again. The procedure finishes when one of 61 Víctor José Gallego Fontenla ID Trace Window Conformance metrics Actions Model 𝜏1𝐴𝐵𝐶𝐷 𝜔1=⟨𝜏1⟩— Window is not full. Read new trace 𝜏2𝐴𝐵𝐶𝐷 𝜔2=⟨𝜏1, 𝜏2⟩— Window is not full. Read new trace 𝜏3𝐴𝐵𝐶𝐷 𝜔3=⟨𝜏1, 𝜏2, 𝜏3⟩— Window is not full. Read new trace 𝜏4𝐴𝐵𝐶𝐷 𝜔4=⟨𝜏1, 𝜏2, 𝜏3, 𝜏4⟩𝛾(𝑁1, 𝜔4)=1.00 𝜌(𝑁1, 𝜔4)=1.00 Discover model for 𝜔4𝑁1A B CD 𝜏5𝐴𝐵𝐶𝐷 𝜔5=⟨𝜏2, 𝜏3, 𝜏4, 𝜏5⟩𝛾(𝑁1, 𝜔5)=1.00 𝜌(𝑁1, 𝜔5)=1.00 No drift candidate detected 𝜏6𝐴𝐵𝐶𝐷 𝜔6=⟨𝜏3, 𝜏4, 𝜏5, 𝜏6⟩𝛾(𝑁1, 𝜔6)=1.00 𝜌(𝑁1, 𝜔6)=1.00 No drift candidate detected 𝜏7𝐴𝐵𝐶𝐷 𝜔7=⟨𝜏4, 𝜏5, 𝜏6, 𝜏7⟩𝛾(𝑁1, 𝜔7)=1.00 𝜌(𝑁1, 𝜔7)=1.00 No drift candidate detected 𝜏8𝐴𝐵𝐶𝐷 𝜔8=⟨𝜏5, 𝜏6, 𝜏7, 𝜏8⟩𝛾(𝑁1, 𝜔8)=1.00 𝜌(𝑁1, 𝜔8)=1.00 No drift candidate detected 𝜏9𝐴𝐵𝐷𝐶 𝜔9=⟨𝜏6, 𝜏7, 𝜏8, 𝜏9⟩𝛾(𝑁1, 𝜔9)=0.75 𝜌(𝑁1, 𝜔9)=1.00 Drift candidate on 𝜔9(by fitness) 𝜏10 𝐴𝐵𝐶𝐷 𝜔10 =⟨𝜏7, 𝜏8, 𝜏9, 𝜏10⟩𝛾(𝑁1, 𝜔10)=0.75 𝜌(𝑁1, 𝜔10)=1.00 Drift candidate on 𝜔10 (by fitness) 𝜏11 𝐴𝐵𝐷𝐶 𝜔11 =⟨𝜏8, 𝜏9, 𝜏10, 𝜏11 ⟩𝛾(𝑁1, 𝜔11)=0.50 𝜌(𝑁1, 𝜔11)=1.00 Drift candidate on 𝜔11 (by fitness) 𝜏12 𝐴𝐵𝐶𝐷 𝜔12 =⟨𝜏9, 𝜏10, 𝜏11, 𝜏12⟩𝛾(𝑁1, 𝜔12)=0.50 𝜌(𝑁1, 𝜔12)=1.00 Drift candidate on 𝜔12 (by fitness) Confirm drift at 𝜏9(by fitness) Discover model for 𝜔12 𝑁2A B C D 𝜏13 𝐴𝐵𝐷𝐶 𝜔13 =⟨𝜏10, 𝜏11, 𝜏12, 𝜏13⟩𝛾(𝑁2, 𝜔13)=1.00 𝜌(𝑁2, 𝜔13)=1.00 No drift candidate detected 𝜏14 𝐴𝐵𝐶𝐷 𝜔14 =⟨𝜏11, 𝜏12, 𝜏13, 𝜏14⟩𝛾(𝑁2, 𝜔14 )=1.00 𝜌(𝑁2, 𝜔14)=1.00 No drift candidate detected 𝜏15 𝐴𝐵𝐷𝐶 𝜔15 =⟨𝜏12, 𝜏13, 𝜏14, 𝜏15⟩𝛾(𝑁2, 𝜔15)=1.00 𝜌(𝑁2, 𝜔15)=1.00 No drift candidate detected 𝜏16 𝐴𝐵𝐶𝐷 𝜔16 =⟨𝜏13, 𝜏14, 𝜏15, 𝜏16⟩𝛾(𝑁2, 𝜔16 )=1.00 𝜌(𝑁2, 𝜔16)=1.00 No drift candidate detected 𝜏17 𝐴𝐵𝐷𝐶 𝜔17 =⟨𝜏14, 𝜏15, 𝜏16, 𝜏17⟩𝛾(𝑁2, 𝜔17)=1.00 𝜌(𝑁2, 𝜔17)=1.00 No drift candidate detected 𝜏18 𝐴𝐵𝐷𝐶 𝜔18 =⟨𝜏15, 𝜏16, 𝜏17, 𝜏18⟩𝛾(𝑁2, 𝜔18)=1.00 𝜌(𝑁2, 𝜔18)=1.00 No drift candidate detected 𝜏19 𝐴𝐵𝐷𝐶 𝜔19 =⟨𝜏16, 𝜏17, 𝜏18, 𝜏19⟩𝛾(𝑁2, 𝜔19)=1.00 𝜌(𝑁2, 𝜔19)=1.00 No drift candidate detected 𝜏20 𝐴𝐵𝐷𝐶 𝜔20 =⟨𝜏17, 𝜏18, 𝜏19, 𝜏20⟩𝛾(𝑁2, 𝜔20)=1.00 𝜌(𝑁2, 𝜔20)=0.66 Drift candidate on 𝜔20 (by precision) 𝜏21 𝐴𝐵𝐷𝐶 𝜔21 =⟨𝜏18, 𝜏19, 𝜏20, 𝜏21⟩𝛾(𝑁2, 𝜔21)=1.00 𝜌(𝑁2, 𝜔21)=0.66 Drift candidate on 𝜔21 (by precision) 𝜏22 𝐴𝐵𝐷𝐶 𝜔22 =⟨𝜏19, 𝜏20, 𝜏21, 𝜏22⟩𝛾(𝑁2, 𝜔22)=1.00 𝜌(𝑁2, 𝜔22)=0.66 Drift candidate on 𝜔22 (by precision) 𝜏23 𝐴𝐵𝐷𝐶 𝜔23 =⟨𝜏20, 𝜏21, 𝜏22, 𝜏23⟩𝛾(𝑁2, 𝜔23)=1.00 𝜌(𝑁2, 𝜔23)=0.66 Drift candidate on 𝜔23 (by precision) Confirm drift at 𝜏17 (by precision) Discover model for 𝜔23 𝑁3A B D C 𝜏24 𝐴𝐵𝐷𝐶 𝜔24 =⟨𝜏21, 𝜏22, 𝜏23, 𝜏24⟩𝛾(𝑁3, 𝜔24)=1.00 𝜌(𝑁3, 𝜔24)=1.00 No drift candidate detected 𝜏25 𝐴𝐵𝐷𝐶 𝜔25 =⟨𝜏22, 𝜏23, 𝜏24, 𝜏25⟩𝛾(𝑁3, 𝜔25)=1.00 𝜌(𝑁3, 𝜔25)=1.00 No drift candidate detected 𝜏26 𝐴𝐵𝐷𝐶 𝜔26 =⟨𝜏23, 𝜏24, 𝜏25, 𝜏26⟩𝛾(𝑁3, 𝜔26)=1.00 𝜌(𝑁3, 𝜔26)=1.00 No drift candidate detected 𝜏27 𝐴𝐵𝐷𝐶 𝜔27 =⟨𝜏24, 𝜏25, 𝜏26, 𝜏27⟩𝛾(𝑁3, 𝜔27)=1.00 𝜌(𝑁3, 𝜔27)=1.00 No drift candidate detected Figure 4.1: Example of a gradual change where some previously unobserved behavior starts to replace the previous one at 𝜏9, which is no longer observed after trace 𝜏16. 62 Chapter 4. Gradual drift detection the three models has a different behavior or when the condition 3∗𝑛′<|𝐿| fails, meaning that it is not possible to discover three consecutive models, returning the last 𝑛′ as the adjusted optimal window size (Algorithm 4.2, line 14). Once the size is adjusted, the window is populated with the first 𝑛 remaining traces from the initial index. Then, the first process model is discovered (line 6) using the content from this 𝜔𝑖 window. This model is stored in a list 𝑁 which contains the set of models that will be discovered for each detected drift. After this initialization, the drift detection step is executed (lines 8 to 42). This step is composed of a loop that repeats until no traces remain unprocessed in the log. Thus, as part of the initialization performed after each change detection, two empty lists are created (line 9), Γ and 𝑃 , for storing the fitness and precision, respectively. Also, two more lists, 𝐷Γ and 𝐷𝑃 , are initialized (line 10). These lists will later be populated with booleans indicating if the successive windows are marked as drift candidates. Finally, a flag used for indicating if a change has been detected is initialized (line 11). Once this initialization is completed, the main detection loop begins (lines 12 to 41), where the detection is performed based on the trends in the values of the conformance metrics. This loop processes the remaining windows, starting at index 𝑖 , until a new change is detected or to the end of the log if no change is present (line 12). For each window 𝜔𝑖 the fitness and the precision of the last discovered model 𝑁|𝑁| are computed, and their values are appended to Γ and 𝑃 , respectively (lines 13 and 14). Then, using the function IdentifyDriftCandidate from Algorithm 4.2, the window 𝜔𝑖 is classified or not as a drift candidate (lines 15 to 16). To carry out this classification step, a simple linear regression —using the ordinary least squares method— is computed over the metric values (Algorithm 4.2, line 17). If there are enough data for computing the regression and the slope of the fitted line is different from 0 with enough statistical confidence — 𝑝-value <0.05 in the 𝑡-test , where 𝐻0 states that the slope of the regression is 0—, or the slope is 0 and the previous window has been marked as a drift candidate, the window 𝜔𝑖 will be marked as a drift candidate. To finalize this detection step the function ConfirmDrift from Algorithm 4.2 is executed (line 29). This function is in charge of checking whether a drift candidate persists over time, becoming a real change, or, on the contrary, only represents a noisy trace. A drift candidate is confirmed as a real change if the last 𝑛windows have been also marked as drift candidates (Algorithm 4.2, lines 23 to 26). Once the change is confirmed, it should be pinpointed in time to an specific trace. In case the drift comes from a change in fitness, the trace causing the drift is the last trace from the 63 Víctor José Gallego Fontenla Algorithm 4.1 CRIER (Conformance-based GRadual DrIft DetEction AlgoRithm) Inputs: an event log 𝐿, minimum size of the sliding window 𝑛′ Outputs: a set of traces/segments of the log causing drifts 1: procedure ConceptDriftDetection(𝐿, 𝑛′) 2: D𝑆,D𝐺← [ ] //confirmed sudden and gradual drifts 3: n←AdjustWindow(𝑛′,⟨𝜏1, . . . , 𝜏|𝐿|⟩) 4: 𝑖←𝑛 5: 𝜔𝑖← ⟨𝜏𝑖−𝑛, . . . , 𝜏𝑖⟩ 6: N← [𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (𝜔𝑖)] //save the model in the model history 7: 𝜏∗, 𝜏′←𝜏1 8: while 𝑖 < |𝐿|do 9: Γ,P← [ ] //fitness and precision measures (Definitions 5 and 6) 10: DΓ,DP← [ ] //drift candidates (fitness and precision) 11: 𝑓 𝑙𝑎𝑔 ←𝐹 𝐴𝐿𝑆𝐸 12: while (𝑖 < |𝐿|) ∧ ¬ 𝑓 𝑙𝑎𝑔 do 13: Γ←Γ:: 𝛾(𝜔𝑖, 𝑁|𝑁|)//append current fitness 14: P←P:: 𝜌(𝜔𝑖, 𝑁|𝑁|)//append current precision 15: DΓ←DΓ:: IdentifyDriftCandidate(n,Γ,DΓ) 16: DP←DP:: IdentifyDriftCandidate(n,P,DP) 17: if ConfirmDrift(n,DΓ)∨ConfirmDrift(n,DP)then//change confirmed 18: if ConfirmDrift(n,DΓ)then 19: 𝜏∗←𝜏𝑖−𝑛//confirmed drift in the last trace from the first candidate 20: else if ConfirmDrift(n,DP)then 21: 𝜏∗←𝜏𝑖−2𝑛//confirmed drift in the first trace from the first candidate 22: end if 23: 𝑓 𝑙𝑎𝑔 ←𝑇𝑅𝑈𝐸 24: 𝐿′← ⟨𝜏′, . . . , 𝜏∗⟩//store the sublog between confirmed drifts 25: n←AdjustWindow(𝑛′,⟨𝜏𝑖+1, . . . , 𝜏|𝐿|⟩) 26: 𝑖←𝑖+𝑛 27: 𝜔𝑖← ⟨𝜏𝑖−𝑛, . . . , 𝜏𝑖⟩ 28: N←N:: 𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (𝜔𝑖)//append current model to model history 29: if |𝑁|>2∧ (∃𝜏∈𝐿′:𝐵𝜏∈𝐵𝑁|𝑁|−2)∧ (∃𝜏∈𝐿′:𝐵𝜏∈𝐵𝑁|𝑁|) ∧ (∀𝜏∈𝐿′:𝐵𝜏∈𝐵𝑁|𝑁|−2∪𝐵𝑁|𝑁|)then 30: 𝜏′←𝐷𝑆|𝐷𝑆| 31: D𝑆← {𝑑∈D𝑆:𝑑≠𝜏′} 32: D𝐺←D𝐺:: [𝜏′, 𝜏∗)//a gradual change 33: else 34: D𝑆←D𝑆:: 𝜏∗//a sudden change 35: end if 36: 𝜏′←𝜏∗ 37: else 38: 𝑖←𝑖+1 39: 𝜔𝑖← ⟨𝜏𝑖−𝑛, . . . , 𝜏𝑖⟩ 40: end if 41: end while 42: end while 43: return D𝑆∪D𝐺 44: end procedure 64 Chapter 4. Gradual drift detection Algorithm 4.2 Auxiliary functions 1: function AdjustWindow(𝑛, 𝐿) 2: 𝑁1, 𝑁2, 𝑁3← ∅ 3: 𝑛′←𝑛 4: while 3𝑛 < |𝐿|do 5: 𝑁1←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (⟨𝜏0, . . . , 𝜏𝑛′⟩) 6: 𝑁2←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (⟨𝜏𝑛′, . . . , 𝜏2𝑛′⟩) 7: 𝑁3←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (⟨𝜏2𝑛′, . . . , 𝜏3𝑛′⟩) 8: if 𝐵𝑁1=𝐵𝑁2=𝐵𝑁3then 9: 𝑛′←𝑖𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡 (𝑛′) 10: else 11: return 𝑛′ 12: end if 13: end while 14: return 𝑛′ 15: end function 16: function IdentifyDriftCandidate(n, 𝑑𝑎𝑡𝑎, D) 17: Υ←𝑟𝑒𝑔𝑟𝑒𝑠𝑠 ({𝑑𝑎𝑡𝑎|𝑑𝑎𝑡𝑎|−n, . . . , 𝑑𝑎𝑡𝑎|𝑑𝑎𝑡𝑎|}) 18: 𝑚<←Υ.slope <0∧Υ.confidence <0.05 19: 𝑚>←Υ.slope >0∧Υ.confidence <0.05 20: 𝑚=← (¬ 𝑚<) ∧ (¬ 𝑚>) 21: return (|𝑑𝑎𝑡𝑎|>n) ∧ (𝑚<∨𝑚>∨ (𝑚=∧ (D|D|=𝑡𝑟𝑢𝑒))) 22: end function 23: function ConfirmDrift(n,D) 24: 𝑑′← ∀𝑑∈ {D|D|−n, . . . , D|D|}:𝑑=𝑡𝑟𝑢𝑒 25: return (|D|⩾n) ∧ 𝑑′ 26: end function first window identified as a candidate —i.e., the first trace causing a change in the metric—. In the case of a change in precision, the trace causing the drift is the first trace from the first window identified as candidate —i.e., the first trace from the first window causing a change in precision—. Then, the flag indicating a detection is updated (line 23) and the sublog 𝐿′ between confirmed drifts is stored for later. The drift must then be classified as sudden or gradual. Figure 4.2 illustrates this part of the algorithm. The first step is to update both the index at which the next window will start and its optimal size (lines 25 and 26). Then, the new window is populated with the traces and the model describing the behavior contained in this window is discovered (lines 27 and 28). This model is stored in the model list. Since gradual changes are delimited by two drifts, the last three models of this list — 𝑁|𝑁|−2 , 𝑁|𝑁|−1 , and 𝑁|𝑁| — are used to check the conditions that determine whether the drift is gradual or not. Note that the model 𝑁|𝑁|−1 corresponds with the sublog in which the confirmed drift has been detected. These conditions are the following (line 29): 65 Víctor José Gallego Fontenla 𝑡1𝑡2 𝜏′𝜏∗ 𝜏𝑖𝜏𝑖+𝑛 𝑁|𝑁|−2𝑁|𝑁|−1𝑁|𝑁| 𝐿′𝜔𝑖+𝑛 A B CDA B C D A B D C Figure 4.2: Drift classification phase in CRIER. 1. There are more than two models in the model list (|𝑁|>2). 2. At least, one trace from 𝐿′is supported by 𝑁|𝑁|. 3. At least, one trace from 𝐿′is supported by 𝑁|𝑁|−2. 4. The behaviour from every trace in 𝐿′is part of the behaviour of 𝑁|𝑁|−2or 𝑁|𝑁|. If 𝐿′ fulfills these four requirements, the change is classified as gradual, indicating that the drift starts at the trace where the last sudden drift 𝐷𝑆|𝐷𝑆| was detected and lasts until 𝜏∗ . Furthermore, 𝐷𝑆|𝐷𝑆| is removed from the sudden drift list (line 31), and appended to the list DΓ of classified drifts (line 32). On the other hand, if the candidate cannot be classified as gradual because it does not meet any of the requirements, the change at 𝜏∗ is classified as sudden (line 34). Finally, the index 𝑖 is incremented by 1 (line 38), the sliding window is updated to this index (line 39), and the cycle starts again. 4.3 Experimentation To evaluate the quality of the results obtained by CRIER against those of the state of the art approaches, we use the same metrics that we used in Chapter 3. On the one hand, 𝐹𝑠𝑐𝑜𝑟𝑒 , which is calculated as the harmonic mean between precision and recall, and evaluates how reliable the results are, based on the number of true/false positives and negatives (Equation (3.2a)). For gradual changes, a true positive ( 𝑇𝑃 ) is any change whose detection area overlaps with a real change not previously detected, while a false positive ( 𝐹𝑃 ) is any change that does not correspond to a region of real change, or that matches a region of change previously detected. In addition, a false negative ( 𝐹𝑁 ) is a region of change that does not overlap with anyone of the detected changes. On the other hand, Δ , which measures how late a drift is reported from the 66 Chapter 4. Gradual drift detection 𝜏0𝜏5𝜏10 𝜏15 𝜏20 𝜏25 𝜏30 𝜏35 𝜏40 𝜏45 𝜏50 FP TP FN Δ Υ Real drifts Detected drifts Figure 4.3: Example of classification of results over a log with two gradual changes. Upper timeline shows the real drift regions, marked in green. Lower timeline shows detected drift regions, marked in orange. actual occurrence until its detection. In the case of gradual changes, since we are dealing with areas of change instead of single points, we measure the delay in detecting the beginning of the region: Δ(𝑑𝑅, 𝑑𝐷)=|min(𝑑𝑅) − min(𝑑𝐷)| (4.1) where 𝑑𝑅and 𝑑𝐷are intervals indicating a real and a detected drift region, respectively. Additionally, and to better reflect the goodness of the results when dealing with gradual changes, these two metrics are complemented with a third one: the change region overlapping ( Υ ). This metric evaluates the percentage of the actual region of change that has been detected by the algorithm, reflecting how well the duration of the changes is captured: Υ(𝑑𝑅, 𝑑𝐷)=|𝑑𝑅∩𝑑𝐷| |𝑑𝑅|(4.2) where 𝑑𝑅and 𝑑𝐷are intervals indicating a real and a detected drift region, respectively. Figure 4.3 shows an example of how these metrics are applied in the evaluation of the results. This example presents a log with two gradual changes, one between traces 𝜏10 and 𝜏20 , and the other one between traces 𝜏35 and 𝜏45 . The algorithm detects two changes, one between traces 𝜏4 and 𝜏7 , classified as a false positive as no real change happened in this time interval, and one between traces 𝜏17 and 𝜏23 , classified as a true positive because it overlaps a real change. In this second detection, the delay would be 7 traces —from trace 𝜏10 to trace 𝜏17 —. On the other hand, the change region overlapping would be 30% , since only 3 traces out of the 10 that constitute the region of change are detected. Finally, the second change, between traces 𝜏35 and 𝜏45 , will be classified as a false negative, since the algorithm has not detected any change in that region. 4.3.1 Validation data Concept drift algorithms are validated with synthetic data generated from real processes, in which changes are introduced at a specific moment and with a specific duration, since there 67 Víctor José Gallego Fontenla are at the beginning or at the end of the change. Consequently, CRIER obtains high delays in detecting the start of the change, and premature detections at the end of the change, having a high number of false positives that lead to a decrease in accuracy. Particularly interesting are the logs with slowest changes — 0.1% slope, i.e., 1,000 -trace change regions—, where ProDrift obtains the best 𝐹𝑠𝑐𝑜𝑟𝑒 in 6 out of 10 logs. For these 6 logs, CRIER detects a lower change region overlapping, but obtains the best results in terms of Δ , which reinforces the idea that the detection errors are due to false positives in determining the end of the change. However, with respect to the average values of the metrics, CRIER is the best positioned since ProDrift is not able to detect any change in 3 of the logs, while Martjushev et al. obtains many false positives, detecting less than 18% of the traces as a region of change. In the remaining linear logs, the results of ProDrift suffer a significant degradation, detecting changes only in 2 of 20 logs with a greater slope than 0.1%, in which it obtains 𝐹𝑠𝑐𝑜𝑟𝑒 values of 0.5 or less, and Δof more than 400 traces. This degradation may be due to the fact that, as changes are much faster, the algorithm does not have enough information to correctly extract the distribution of partially-ordered-runs before and after the change, not being able to correctly detect the drifts. In logs with Gaussian distributions, the results obtained by CRIER are clearly better than those of Martjushev et al., with 𝐹𝑠𝑐𝑜𝑟𝑒 of 1.0 in 17 of 20 logs. These logs are characterized by relatively fast changes, but with both a slow start and termination. The results are consistent with what was previously established for the linear changes: as these are relatively fast changes —slightly more than 150 traces in the slowest case— the slope of the regression changes abruptly, facilitating the detection of changes. The values of Δ and Υ obtained by Martjushev et al. are particularly indicative. The slow start and termination of the new behavior lead to smaller changes in the distributions of the features, making the statistical test employed by this approach unable to detect the drifts and causing the beginning of the changes to be detected late —increasing Δ values— while their termination is detected prematurely —resulting in low Υvalues—. Something similar happens for logs with constant distribution. In this case, CRIER obtains the best results, with a perfect average 𝐹𝑠𝑐𝑜𝑟𝑒 and an average Υ of around 90% . This is because, as soon as the change starts, half of the observed behavior is part of the new model. Consequently, conformance metrics change very fast, which means that the slope of the regression is significantly modified and changes are detected almost instantly. For Martjushev et al., there are several logs in which no change is detected — rp and sw for all cumulative 74 Chapter 4. Gradual drift detection probability functions—. The poor performance of this algorithm for the same change patterns may be caused by the selected features since they are not able to capture such changes. Perhaps selecting other features that might be more sensitive to this type of changes would improve the results, however a more in-depth analysis should be performed to confirm this intuition. Finally, for logs with exponential changes, the results of CRIER are quite degraded when compared to the other distributions. These results are due to two distinct situations: on the one hand, in logs with 𝜆=0.5 , changes are so fast —only 14 traces— that CRIER is not able to detect them as gradual, leading to false negatives; and, on the other hand, in logs with 𝜆=0.05 , changes have such long tails that they are terminated prematurely, and consequently, a high number of false positives are detected in traces that belong to the actual change but have not been detected as part of the drift. This behavior of the algorithm is reflected by the values of Δ and Υ . As seen in the results, all changes are detected very close where they begin —with Δ below 10 traces in almost all cases—, but Υ values remain around 20% , indicating that only the initial part of the change region is detected. In addition, logs in which CRIER obtains the lowest Υcoincide with those with the worst 𝐹𝑠𝑐𝑜𝑟𝑒, confirming this hypothesis. 4.4 Conclusions In this chapter, we presented CRIER, an offline gradual-drift detection algorithm. CRIER is based on the hypothesis that change detection and classification can be addressed by analyzing how the fitness and precision of the process models —the old model and the new one after the change— vary from the beginning to the end of the gradual change. Specifically, the hypothesis is that at the beginning there is a modification of the fitness, keeping the precision; while at the end the precision changes. This hypothesis has been mathematically demonstrated. The approach has been validated using a synthetic dataset with 120 logs that present different change patterns and gradual change distributions, from linear to Gaussian, exponential and constant. The experiments show that CRIER outperforms the results of the main state of the art approaches in terms of accuracy ( 𝐹𝑠𝑐𝑜𝑟𝑒 ); delay ( Δ ), so drifts are detected faster; and change region overlapping ( Υ ), so the time interval during which two processes coexist is clearly identified. Furthermore, CRIER is more robust for all types of change distributions and particularly better for those in which the traces of the new model start to arise with a higher frequency at the beginning of the gradual drift, such as Gaussian, exponential, and constant distributions. 75 Víctor José Gallego Fontenla Nonetheless, our approach has proven to be more consistent even when the former conditions are not present such as when the drift follows a linear distribution with a low slope, being able to detect all the change patterns with less delay Δand better Υ. 76 CHAPTER 5 ROBUST DRIFT DETECTION I shall either find a way or make one. — Hannibal In the previous chapters, we presented two approaches —C2D2 and CRIER— for detecting sudden and gradual drifts with high reliability. These approaches monitor the behavior of fitness and precision metrics over the entire log to detect changes in the process control-flow. By detecting when the metrics deviate from their initial value, both C2D2 and CRIER can detect the presence of changes in non-noisy event logs. However, in real-world scenarios, anomalous executions can occur spontaneously without representing a change that persists over time. Therefore, it is necessary to adapt the developed algorithms to provide robust solutions to noisy environments, which are common in real scenarios. The robust version of these algorithms should be able to discriminate noise from real drifts that persist over time, reducing the number of false positives. In Figure 5.1, an example of fitness behavior is presented in both a noisy and non-noisy environment. When no noise is present, the metric value remains at a constant value —in this case, 1.0—, and decreases when a change occurs. This makes it possible to detect drifts by identifying decreases in the metric value. However, in presence of noise, the metric fluctuates around a certain value —approximately 0.75 in the example—, without showing significant drops until a change occurs. Víctor José Gallego Fontenla 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 environment 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 environment 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 environment 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 environment 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 environment 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 environment Figure 5.1: Fitness and precision behaviour in noisy and non-noisy environments. In the presence of noise, these fluctuations can result in false positive detections when anomalous executions occur, unless they are differentiated from the significant drops that occur in the case of real changes, thus invalidating the result. Furthermore, we cannot determine the magnitude of the drops a priori, as it depends on the change and the structure of the process being executed. Therefore, in order to detect changes in noisy environments, our intuition tells us that it is neccessary to detect multiple consecutive drops in the metric, with no intermediate increases in the value, are necessary. If the drop persists sufficiently over time, we can discriminate it from fluctuations caused by anomalous executions, enabling us to distinguish between a real change and noise. Based on this premise, this chapter introduces Robust CRIER (R-CRIER), the robust version of CRIER adapted for execution in both noisy and non-noisy environments. 5.1 Robust drift detection using conformance metrics In previous chapters, we showed that changes in the process control-flow can be detected by monitoring their conformance metrics. Also, we used simple linear regressions to monitor those conformance metrics, detecting a drift when the slope of the regression falls, meaning that the metric values are decreasing. However, in noisy environments, a drop in one of the metrics may be caused by transient anomalies that do not represent a real drift. In this section, we will demonstrate that successive drops in the regression slope can enable robust detection of changes, even in noisy environments, by separating falls derived from anomalous executions from those caused by real drifts. 78 Chapter 5. Robust drift detection Theorem 5.1: When detecting changes in noisy environments, waiting n/2 negative slopes for the simple linear regression allows to differenciate drops due to noisy executions from those due to real drifts. Proof: To demonstrate this, lets take the formula for calculating the slope of Υ using the least squares method [77]: Υ.slope =Í𝑛 𝑖=1(𝑥𝑖−𝑥)(𝑦𝑖−𝑦) Í𝑛 𝑖=1(𝑥𝑖−𝑥)2, being 𝑥 and 𝑦 the mean values for 𝑥 and 𝑦 , respectively. As 𝑥 is the index of the window for which the conformance metric has been measured, we can replace it by the arithmetic progression 1..𝑛, so we can replace in the equation: Υ.slope =Í𝑛 𝑖=1𝑖−1+𝑛 2(𝑦𝑖−𝑦) Í𝑛 𝑖=1𝑖−1+𝑛 22. On the other hand, 𝑦 contains the values of the conformance metrics for each window. Note that the following is valid for both fitness and precision. When a noisy execution enters the window 𝜔𝑖(𝐿, 𝑛) , the metric value will decrease, and stay at that value until the noisy execution disappears at window 𝜔𝑖+𝑛(𝐿, 𝑛) —we will have only a trace with the fitting/non-fitting behaviour, regardless of its position in the window lenght—. Thus, for a given window, there will be 𝑘 measurements with value 𝑐 at the beggining of the window and 𝑛−𝑘measurements with value 𝑐′at the end, being 𝑐 > 𝑐′, so we can rewrite 𝑦as: 𝑦=𝑘𝑐 + (𝑛−𝑘)𝑐′ 𝑛. Then, we can rewrite the slope as the following formula, where 𝑘 is the number of successive measurements without noise counted from the begginning of the window: 𝑓(𝑘)=Í𝑘 𝑖=1𝑖−1+𝑛 2𝑐−𝑘𝑐+(𝑛−𝑘)𝑐′ 𝑛+Í𝑛 𝑖=𝑘+1𝑖−1+𝑛 2𝑐′−𝑘𝑐+(𝑛−𝑘)𝑐′ 𝑛 Í𝑛 𝑖=1𝑖−1+𝑛 22. 79 Víctor José Gallego Fontenla 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 Figure 5.2: Example of the evolution of the slope in a noisy environment for 𝑛=20 , and multiple 𝑐 and 𝑐′values. Computing the first and second derivative over 𝑘to find the critical points, we get: 𝑓′(𝑘)=6(𝑐−𝑐′)(2𝑘−𝑛) 𝑛(𝑛2+2)𝑓′′ (𝑘)=12𝑐−12𝑐′ 𝑛3+2𝑛 We know that 𝑐 > 𝑐′⩾0; 𝑛, 𝑘 ∈N;𝑛 > 𝑘 , so 𝑓′(𝑘)=0=⇒𝑘=𝑛/2 and 𝑓′′ (𝑘)>0∀𝑘, i.e., 𝑓(𝑘)has a minimum on 𝑘=𝑛/2. On the contrary, it is straightforward to demonstrate that, when having a real drift, with the values from the metric decreasing steadily —as we have one more trace that does fit/not fit the model on each iteration—, the regression slope will decrease continually without presenting any critical point. □ This behavior is shown in the example from Figure 5.2. Here, 𝑛=20 , and we show the behaviour for some values of 𝑐 and 𝑐′ . When 𝑘 increases—i.e., when the occurrences of 𝑐′ increases at the cost of decreasing the number of occurrences of 𝑐 —, the regression slope also decreases, reaching a minumum in 𝑘=10 , no matter the specific values 𝑐 and 𝑐′ get. From here onwards, the slope is still negative, but its values increase with 𝑘until reaching 0.0 at 𝑘=20. 5.2 Algorithm Algorithm 5.1 shows the pseudocode of R-CRIER, the algorithm for robustly detecting process control-flow drifts, ensuring reliable results even in noisy environments. R-CRIER continuously monitors process conformance metrics over time, looking for variations that persist and that may indicate a change in the process. The algorithm utilizes a sliding window that moves over the entire log and calculates fitness and precision metrics for each window to examine their evolution over time. R-CRIER takes three inputs: an event log 𝐿 , a window size 𝑛 , and an 80 Chapter 5. Robust drift detection Algorithm 5.1 R-CRIER Inputs: an event log 𝐿, size of the sliding window 𝑛, estimation of the noise probability 𝑟 Outputs: a set of traces/segments of the log causing drifts 1: procedure ConceptDriftDetection(𝐿, 𝑛, 𝑟) 2: L,N← [ ] //list of sublogs between drifts and the respective models 3: 𝑖←𝑛 4: 𝑙𝑎𝑠𝑡 ←0 5: while 𝑖 < |𝐿|do 6: Γ,P← [ ] //list of fitness and precision measures (Definitions 5 and 6) 7: ΥΓ,ΥP← [ ] //list of regressions for fitness and precision 8: N←𝑑𝑖𝑠𝑐𝑜𝑣𝑒𝑟 (𝜔𝑖(𝐿, 𝑛)) 9: N←N:: 𝑁//save current model in the models list 10: 𝑏𝑟𝑒𝑎𝑘 ←FALSE 11: while 𝑖 < |𝐿| ∧ ¬𝑏𝑟𝑒𝑎𝑘 do 12: Γ←Γ:: 𝛾(𝜔𝑖(𝐿, 𝑛), 𝑁 )//append current fitness 13: P←P :: 𝜌(𝜔𝑖(𝐿, 𝑛), 𝑁 )//append current precision 14: if (|Γ|⩾𝑛) ∧ (|P|⩾𝑛)then //enough measurements 15: ΥΓ←ΥΓ:: 𝑟𝑒𝑔𝑟𝑒𝑠𝑠 (𝑡𝑎𝑖𝑙 (Γ, 𝑛)) //save regression over last n measurements 16: ΥP←ΥP:: 𝑟𝑒𝑔𝑟𝑒𝑠𝑠 (𝑡𝑎𝑖𝑙 (P, 𝑛)) //save regression over last n measurements 17: end if 18: if (|ΥΓ|⩾𝑛/2) ∧ HasDrift(𝑡𝑎𝑖𝑙(ΥΓ, 𝑛/2)) then //fitness drift confirmed 19: 𝑏𝑟𝑒𝑎𝑘 ←TRUE 20: L←L:: [𝜏𝑙𝑎𝑠𝑡 , . . . , 𝜏𝑖−(𝑛/2)]//save the sublog between drifts 21: 𝑙𝑎𝑠𝑡 ← (𝑖−𝑛/2) 22: else if (|ΥP|⩾𝑛/2) ∧ HasDrift(𝑡𝑎𝑖𝑙 (ΥP, 𝑛/2)) then //precision drift confirmed 23: 𝑏𝑟𝑒𝑎𝑘 ←TRUE 24: L←L:: [𝜏𝑙𝑎𝑠𝑡 , . . . , 𝜏𝑖−𝑛]//save the sublog between drifts 25: 𝑙𝑎𝑠𝑡 ← (𝑖−𝑛) 26: end if 27: 𝑖←𝑖+1 28: end while 29: end while 30: L←L:: [𝜏𝑙𝑎𝑠𝑡 , . . . , 𝜏𝑖]//save the last sublog 31: return ClassifyDrifts(L,N, 𝑟 )//classify the drifts 32: end procedure 33: function HasDrift(Υ) 34: return ∀Υ𝑖∈Υ→ (Υ𝑖.slope <0)∧(Υ𝑖.confidence <0.05) ∧ (|Υ𝑖.slope|⩽|Υ𝑖+1.slope|) 35: end function estimation of the amount of noise present in the log 𝑟 . It produces a list of traces or sublogs from the input log that cause sudden or gradual drifts, respectively. The algorithm begins by creating two lists, L and N , which will be used to store the sublogs between changes and the process models for each sublog, respectively (line 2). Next, it sets the index of the first window to be processed as the size of the window (line 3), which includes the first 𝑛 traces from the log. Additionally, it initializes a variable to keep track of the position of 81 Víctor José Gallego Fontenla the last detected drift to 0 (line 4). The main detection loop, which runs from lines 5 to 29, iterates over the log until all traces have been processed. At the start of the loop, two lists, Γ and P , are initialized to store historical fitness and precision measurements, respectively (line 6). Additionally, two lists, ΥΓ and ΥP , are initialized (line 7) to maintain a record of regressions over the fitness and precision measurements, respectively. These lists are essential for detecting and confirming drifts in the process control-flow. Next, the loop discovers a process model using a noise-robust discovery algorithm applied to the traces in the 𝜔𝑖(𝐿, 𝑛) window, where 𝐿 is the log, and 𝑛 is the size of the window for the i-th iteration (line 8). The algorithm used in this case is the Inductive Miner - infrequent algorithm ( 𝐼𝑀𝐹 ) [ 78 ]. 𝐼𝑀𝐹 is an adapted version of the original Inductive Miner [ 23 ] that includes additional filtering steps to remove deviating and infrequent behavior to produce more precise models. After discovering the process model, it is stored in the list of process models, N(line 9), and a flag is initialized to false (line 10) to break out of the next loop if necessary. Once the initial setup is complete, the algorithm enters an inner loop that iterates over the remaining traces until a change is detected or there are no more unprocessed traces (lines 11 to 28). Within this loop, the fitness and precision values for each remaining window are computed and added to the previously defined lists (lines 12 and 13). If at least 𝑛 measurements for the conformance metrics have been computed (lines 14 to 17), a simple linear regression is performed over the last 𝑛 elements of both fitness and precision measurements, and the results are stored in the designated lists (lines 15 and 16). Next, the algorithm checks for the presence of drifts in the computed regressions (lines 18 to 26). This involves first ensuring that enough regressions have been computed —at least 𝑛/2 regressions are required, as explained in section 5.1—. The algorithm then determines if the last 𝑛/2 regressions show a drift using the HasDrift function (lines 33 to 35). To confirm a drift in the metrics, the last 𝑛/2 regressions must exhibit a negative slope with a confidence of the slope being equal to 0.0 below 0.05 , and the magnitude of the slopes of the successive regressions should be steadily increasing (line 34). If a drift is detected, the algorithm sets the flag to break the inner loop (lines 19 and 23), adds a new sublog between changes to the list L (lines 20 and 24), and stores the location of the last detected drift in the variable 𝑙𝑎𝑠𝑡 (lines 21 and 25). It is important to differentiate between fitness-caused and precision-caused drifts to calculate the drift index. This is because of the different behavior of the two metrics when a change is present. In the case of fitness, when the 82 Chapter 5. Robust drift detection first drifting trace appears in the window, the metric value decreases, resulting in a negative slope for the regression. Therefore, when a drift is confirmed, the trace that caused the drift is the last one from the first window evaluated in the regression. Thus, the index of the change for fitness is 𝑖−𝑛+ (𝑛/2)=𝑖− (𝑛/2) . However, in the case of precision, the value will only decrease when the last trace before the drift disappears from the window, so the first drifting trace will be the first one from the first evaluated window. Hence, the index of the change for precision is 𝑖−𝑛. After checking for the occurrence of a drift, if there is none, we slide the window one position forward (line 27) and proceed to loop back to the beginning of the inner loop. Otherwise, if a change has been detected, we break out of the inner loop and restart the detection process. Once all traces have been processed, the sublog between the last detected change and the end of the log is added to L (line 30). The algorithm then uses the function ClassifyDrifts from Algorithm 5.2 to classify the changes as sudden or gradual before returning (line 31). 5.2.1 Drift classification Once the drift points have been detected from the log, the next step is to classify them as sudden or gradual drifts using the same criteria described in Chapter 4. However, this classification is performed as a final step instead of being done during the detection process, and it must also be adapted to account for noisy environments. Algorithm 5.2 outlines the code used for this classification. The algorithm takes in a list of sublogs delimited by drifts L , a corresponding list of models N , and an estimation of the percentage of noise present in the log 𝑟 . The first step is to initialize a list D (line 2), which will be used to store the classified drifts. If L contains only two sublogs, it can be assumed that the drift is sudden and that it occurs on the last trace from the first sublog (lines 3 to 5). Otherwise, we iterate over the list of sublogs until the antepenultimate sublog is reached (lines 5 to 20). Within this loop, we select three consecutive models N𝑖 , N𝑖+1 and N𝑖+2 , along with the corresponding sublogs L𝑖 , L𝑖+1 and L𝑖+2 . Then it is checked if L𝑖+1 represents a gradual change using the following four conditions (line 9): 1. The behaviour from N𝑖and N𝑖+2must differ from each other. 2. At least one trace in L𝑖+1must exhibit behavior that is supported by N𝑖. 3. At least one trace in L𝑖+1must exhibit behavior that is supported by N𝑖+2. 83 Víctor José Gallego Fontenla Table 5.1: Average 𝐹𝑠𝑐𝑜𝑟𝑒 and Δ values for the noisy logs with sudden changes. The colors highlight the best performing approach for each metric. size noise R-CRIER ProDrift 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 positives —sometimes more than 60 false positives for 9 true positives—. In contrast, for ProDrift, 𝐹𝑠𝑐𝑜𝑟𝑒 values decrease with increasing noise levels, but this time due to the number of false negatives, i.e., real changes that the algorithm fails to detect. Regarding Δ ,TPCDD obtains the best values, outperforming all other approaches, but at the cost of significantly compromising its 𝐹𝑠𝑐𝑜𝑟𝑒 values. ProDrift obtains the worst results with delay values between 70 and 100 traces for all logs, while R-CRIER lies in the middle, with Δ values lower than ProDrift but higher than TPCDD. Notably, for R-CRIER, Δ values increase with log size, indicating higher delays with longer logs, and lower values with smaller ones. On the other hand, Table 5.2 presents the average results for the logs containing gradual 90 Chapter 5. Robust drift detection Table 5.2: Average 𝐹𝑠𝑐𝑜𝑟𝑒 and Δ values for the noisy logs with gradual changes. The colors highlight the best performing approach for each metric. distribution noise R-CRIER ProDrift Martjushev et 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% Constant 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 continues to outperform other approaches in terms of 𝐹𝑠𝑐𝑜𝑟𝑒 , with consistently higher values overall. However, the differences between the approaches are less pronounced in this case. As with sudden drifts, the 𝐹𝑠𝑐𝑜𝑟𝑒 decreases with an increase in the noise level, leading to lower average values, mainly due to false negatives being detected. Martjushev et al. performed poorly, achieving F-score values below 0.5 in 8 out of 12 logs, and not exceeding 0.55 in any log. Δ shows the best results for Martjushev et al., whereas both R-CRIER and ProDrift exhibit worse but similar values. In terms of Υ , the three alternatives perform similarly, with the best results evenly distributed among them. Statistical tests To ensure the validity of the results, we have used statistical methods to compare the performance of R-CRIER with the state of the art algorithms. Specifically, we conducted a BAIN test to determine if R-CRIER performs better than the other approaches —details of this test are explained in Section 3.3.4—. The Bayes factor 𝐵𝐹𝐻𝑖𝐻𝑐 𝑖 was used as a measure of evidence for the hypothesis being tested against its complement. The results of this test are summarized in Table 5.3. For the sudden drift logs, the Bayes factor 𝐵𝐹𝐻1𝐻𝑐 1 —where 𝐻1 is the hypothesis that considers that R-CRIER has better results— clearly shows an extreme evidence supporting the hypothesis that R-CRIER performs better than the other approaches in terms of 𝐹𝑠𝑐𝑜𝑟𝑒 . However, when it comes to Δ ,TPCDD is statistically superior to R-CRIER. When it comes to 91 Víctor José Gallego Fontenla Table 5.3: BAIN test results for the validation logs, where 𝐵𝐹𝐻𝑖𝐻𝑐 𝑖 shows the Bayesian factor for 𝐻𝑖 against its complementary 𝐻𝑐 𝑖=¬𝐻𝑖 . The most likely hypothesis is shown shaded in blue. 𝐵𝐹𝐻𝑖𝐻𝑐 𝑖 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ sudden drifts 𝐻1:R-CRIER >ProDrift and R-CRIER >TPCDD 2.28 ×1013 7.06 ×10−25 — 𝐻2:R-CRIER <ProDrift 2.14 ×10−31 6.78 ×10−71 — 𝐻3:R-CRIER <TPCDD 4.58 ×10−91 2.29 ×1013 — 𝐻4:R-CRIER =ProDrift 1.55 ×10−28 7.08 ×10−68 — 𝐻5:R-CRIER =TPCDD 5.75 ×10−88 3.55 ×10−22 — gradual drifts 𝐻1:R-CRIER >ProDrift and R-CRIER >Martjushev et al. 3.19 4.23 ×10−10 9.75 ×10−1 𝐻2:R-CRIER <ProDrift 6.35 ×10−11.52 1.05 𝐻3:R-CRIER <Martjushev et al. 7.02 ×10−21 4.44 ×1099.49 ×10−1 𝐻4:R-CRIER =ProDrift 1.29 ×1011.30 ×1011.34 ×101 𝐻5:R-CRIER =Martjushev et al. 2.22 ×10−18 4.17 ×10−81.34 ×101 gradual drifts, 𝐵𝐹𝐻1𝐻𝑐 1 indicates that R-CRIER and ProDrift are similarly effective in terms of 𝐹𝑠𝑐𝑜𝑟𝑒 , with the highest evidence score. However, Martjushev et al. performs significantly better than the other two approaches in terms of Δ , according to the test results. In terms of Υ , the test shows that all three algorithms are evenly matched, with high evidence for their pairing. 5.3.3 Results discussion The previous section shows that R-CRIER outperforms the rest of the state of the art approaches in terms of 𝐹𝑠𝑐𝑜𝑟𝑒 when dealing with noisy environments. The results for sudden changes are promising, with R-CRIER achieving a mean 𝐹𝑠𝑐𝑜𝑟𝑒 value of 0.9 across all the logs. However, as the level of noise increases, 𝐹𝑠𝑐𝑜𝑟𝑒 values decrease due to an increase in false positives. This can be attributed to the challenge of differentiating between a real drift and anomalous executions, which can cause conformance metrics to decrease even when such presence is spurious. Nevertheless, the number of false positives remains within tolerable limits, with an average of less than 3 , and a maximum of 7 and 8 on the RIO and OIR logs with 10,000 traces and 25% and 20% of noise, respectively. In these experiments, we limited the noise presence to a maximum of 25% . However, our results suggest that R-CRIER may still perform well in environments with even higher levels of anomalous executions. In contrast to R-CRIER,TPCDD shows a rapid decrease in 𝐹𝑠𝑐𝑜𝑟𝑒 values even with small 92 Chapter 5. Robust drift detection noise levels, and its performance does not significantly change with varying levels of noise. Instead, the primary factor that affects TPCDD performance is the size of the log, which leads to a significant number of false positives between changes. This makes TPCDD impractical for use with the largest logs and higher levels of noise, where it detects over 60 false positives for all cases. Among the evaluated approaches, ProDrift falls between R-CRIER and TPCDD. Its 𝐹𝑠𝑐𝑜𝑟𝑒 values show a similar behavior to R-CRIER, decreasing with the noise level, but with lower magnitude. The maximum 𝐹𝑠𝑐𝑜𝑟𝑒 value achieved was 0.8440 for the 10,000 traces and 0% noise. However, the decrease in 𝐹𝑠𝑐𝑜𝑟𝑒 is mainly due to an increase in the false negative rates, with some drifts going unnoticed in an increasing number of logs. This might be caused by the algorithm building an underfitting reference model, which is too generalized due to the presence of noise to detect changes accurately. In terms of Δ ,TPCDD outperforms R-CRIER. However, as previously mentioned, TPCDD becomes impractical in the presence of noise, resulting in numerous false detections. The mean Δ values for R-CRIER increase with the log size and become closer to those of TPCDD for smaller logs. All three algorithms show an increase in Δ with the noise level, possibly because of the algorithms have to wait longer to distinguish a drift from anomalous behavior. Additionally, Δ values obtained by ProDrift are higher for smaller logs than those of R-CRIER, but the difference between smaller and larger logs is not as significant as with R-CRIER. In the case of gradual logs, R-CRIER outperforms the other approaches in terms of 𝐹𝑠𝑐𝑜𝑟𝑒 , achieving values above 0.75 in 78 out of 100 logs. However, as with sudden drifts, the 𝐹𝑠𝑐𝑜𝑟𝑒 values decrease with an increase in noise level. This decrease is mainly due to the inability of R-CRIER to detect the end of drift regions accurately, resulting in a high number of false positives at the end of the drift. The Υ values also reflect this, indicating that the algorithm often fails to detect the entire change region, leading to premature termination of the drift. ProDrift exhibits similar behavior to R-CRIER but with worse results. In contrast, Martjushev et al. performs poorly, exhibiting highly variable detection capability depending on the pattern of change present in the log. While the approach achieves perfect 𝐹𝑠𝑐𝑜𝑟𝑒 values for some patterns, it fails to detect any change in others, resulting in 𝐹𝑠𝑐𝑜𝑟𝑒 values of 0.0. 93 Víctor José Gallego Fontenla 5.4 Conclusions This chapter presents the R-CRIER algorithm, which builds upon previous works C2D2 and CRIER to enable drift detection in noisy environments. R-CRIER continuously monitors the fitness and precision metrics of the model using linear regression, allowing for reliable and robust detection of changes. The hypothesis that several successive regressions with a negative slope whose magnitude is always increasing confirms a drift has been mathematically proven. Experiments with 528 synthetic logs with multiple noise levels for sudden and gradual drifts demonstrate that R-CRIER outperforms other state of the art proposals with better overall accuracy values. Despite its effectiveness, R-CRIER has some limitations that need to be addressed in order to provide a complete solution for all scenarios. The primary challenge arises from the use of a fixed window size, which makes it difficult to handle logs with highly unbalanced intervals between changes. To overcome this limitation, it would be desirable to introduce a mechanism for automatically calculating the window size, which could be optimized during the execution, as suggested in Section 3.2.2. However, this presents a significant challenge, as the presence of anomalous executions in the log can make it difficult to perform such a search for the optimal size. Another important limitation arises with the automatic identification of the percentage of noise in logs from highly unstructured processes. The estimation methods proposed in Section 5.2.2 may yield suboptimal results in such cases, as there may not be a significant or easily identifiable knee in the graph. It is worth noting that this is a common issue affecting all concept drift approaches, as well as a large part of process mining tasks. Extracting valuable knowledge from such processes is challenging without prior preprocessing. However, exploring such preprocessing methods falls beyond the scope of this dissertation. 94 CHAPTER 6 CONCLUSIONS If we knew what it was we were doing, it would not be called research, would it? — Albert Einstein In this dissertation, our focus has been on addressing the challenge of identifying changes in process control-flow by closely monitoring the evolution of conformance metrics over time. Due to the widespread use of processes across various industries and organizations, coupled with increasing automation and digitization and the global interconnectivity that opens a global market for everyone, it is crucial to identify such changes in a timely manner to avoid underperformance or unexpected outcomes. This dissertation emphasizes the critical nature of being aware of subtle changes during Process Mining and Business Process Management tasks. Neglecting to address these changes can lead to adverse consequences in the analysis and insights derived from such activities. In recent times, a plethora of solutions have been proposed to address this problem. Some of these solutions aim to automatically update the process to adapt it to changes in the most optimal manner. Others seek to detect these changes and inform the relevant parties as quickly as possible, thereby enabling informed decision-making. Our emphasis has been on the latter group, so decisions are taken using the latest valid data. Regrettably, most of the approaches that address this task fall short in one way or another. Firstly, most approaches require substantial Víctor José Gallego Fontenla user intervention to confirm the existence of a change. This can be highly inappropriate in complex or highly automated environments that generate big amounts of data, rendering the process infeasible. Secondly, these approaches usually suffer from substantial delays in detecting changes, taking an excessive amount of time to verify their presence, leading to potential losses for the process owners. Thirdly, they usually are highly dependent on the patterns of change observed in the data, performing optimally for some patterns, but inadequately for others. This makes them unsuitable for environments in which potential patterns of change are unknown. Finally, the majority of these approaches are not robust, failing to detect changes in noisy environments where anomalous executions can occur, which is common in the real world. Taking into account the state of the art limitations previously discussed, we suggest utilizing conformance metrics as a means for reliable and early detection for changes, regardless of their patterns. To support our proposal, we put forward three hypotheses: 1. We assert that fitness can detect changes related to unsupported behavior but is unable to detect fitting behavior that is disappearing from the log, whereas precision can detect changes related to fitting behavior that is disappearing from the log but cannot identify new unsupported behavior that is being observed. 2. We suggest that all gradual drifts can be characterized by a fitness change at the outset and a precision change at the end. 3. We contend that monitoring successive drops in conformance metrics allows us to differentiate between genuine changes and spurious, unexpected executions. We have developed three algorithms based on the aforementioned hypotheses, which allow for the early detection of changes in the control-flow of a process. In Chapter 3, we focused on sudden changes —i.e., changes that occur immediately, with new behavior replacing the old behavior from a specific point in time—. In this chapter, we have demonstrated mathematically that conformance metrics can be used to detect such changes. We have also developed C2D2, an algorithm that evaluates fitness and precision metrics over a reference process model using a sliding window and a linear regression, enabling the detection of changes in the process structure. To enhance the algorithm accuracy, we have proposed two new, low complexity estimators for the conformance metrics with which the drift detection is facilitated. We tested C2D2 with two well-established metrics— 𝐹𝑠𝑐𝑜𝑟𝑒 and delay— and evaluated it using a collection of 204 synthetic logs generated from 3 different process models 96 Chapter 6. Conclusions from the state of the art and 17 change patterns. We compared the results with those from the best-performing algorithms from the state of the art, namely TPCDD and ProDrift, and found that C2D2 outperformed them in terms of 𝐹𝑠𝑐𝑜𝑟𝑒. Then, in Chapter 4 our focus shifts to gradual drifts. Unlike sudden drifts, gradual drifts occur when the old behavior is gradually replaced by the new one over time. We have established and formally proven that such drifts always commence with a change in fitness and culminate with a change in precision. Also, as part of this chapter, we have developed CRIER, an algorithm that builds on the premises of C2D2 but extends them to distinguish between sudden and gradual drifts. Our approach is not constrained by any particular behavior distribution during the drift, enabling it to handle any changes while maintaining high accuracy. We evaluated CRIER on 120 event logs, which had 12 different probability distributions. Additionally, we introduced a new evaluation metric that measures the accuracy of detecting the drifting interval. The performance of CRIER was compared to two of the best-performing algorithms from the state of the art, namely ProDrift and Martjushev et al., and it outperformed them considerably. Lastly, in Chapter 5, our attention is on developing a robust detection system that can operate effectively even in presence of noise. We have demonstrated that by monitoring successive drops in conformance metrics, it is possible to differentiate between genuine changes and noisy executions. To this end, we present the R-CRIER algorithm, which builds on the proposals outlined in the previous chapters and adapts them to handle noisy environments. Finally, we evaluate the performance of R-CRIER on a dataset consisting of 528 logs and compare it with the best-performing approaches from the state of the art, namely TPCDD,ProDrift and Martjushev et al., showing that our algorithm outperforms them again in terms of accuracy. With these three proposed algorithms, we have successfully achieved all the objectives stated in the introduction from Chapter 1. Specifically, we have addressed the problem of robustly detecting changes in the control-flow of a process, whether they occur suddenly or gradually, even in noisy environments. We have mathematically proved that conformance metrics can be used to detect changes, and we have proposed new metrics and algorithms that improve upon the state of the art approaches. Our algorithms have been extensively evaluated using synthetic event logs, demonstrating their high accuracy and robustness. By achieving these objectives, our work contributes to the field of process mining and can have practical implications in various application domains, such as healthcare, finance, and manufacturing. 97 Víctor José Gallego Fontenla Future work While the present research has made significant progress in detecting control-flow process changes in various scenarios, there are still several limitations that need to be addressed in future research. • Currently, our algorithms focus solely on the detection of control-flow drifts. However, there is potential to explore the use of other metrics that could evaluate other process perspectives, enabling the extension of drift detection to these perspectives. For instance, time-related metrics could be utilized to monitor changes in the temporal performance of the process. Alternatively, metrics based on the execution cost or that monitors complex behavioral patterns, bottlenecks, or frequent subprocesses could be explored. The addition of such metrics would enable the detection of changes in those perspectives, thereby broadening the scope of drift detection to cover more scenarios. • In addition to the limitations related to the control-flow drift detection, our research has been confined to single-process scenarios. However, as the complexity of the process environment increases, it is necessary to explore the detection of changes in more complex scenarios that involve multiple interdependent processes. To address this issue, future research could focus on exploring the use of clustering techniques to apply a divide-and-conquer strategy. This approach would involve grouping processes with similar characteristics into clusters, and then applying our proposed algorithms to each cluster. To do so, it is necessary to evaluate distance metrics for the clustering algorithm, which would enable us to measure the similarity between processes and group them accordingly. Therefore, by expanding our research to more complex process scenarios and developing appropriate clustering techniques, we can extend the applicability of our proposed algorithms to a wider range of real-world process environments. • Finally, the algorithms proposed in this research are solely designed for drift detection and do not address other stages of the drift management process. Future research could focus on developing methods for change description and drift cause analysis, which would provide process owners with more comprehensive information to facilitate decision-making. Such analysis could involve examining the context in which the drift occurred, identifying the factors that triggered it, and understanding the implications of 98 Chapter 6. Conclusions the change for the overall process performance. This would enable a more complete and effective management of process drifts. In summary, this research has opened several avenues for future work that can enhance the drift detection process in various ways. These include the exploration of new metrics to detect changes in different process perspectives, the extension of the algorithms to multiple interdependent processes, and the development of techniques for change description and drift cause analysis. By addressing these challenges, we can provide a broader approach to process drift management, and provide more valuable information to process owners for decision-making. The possibilities for further research in this area are promising and have the potential to make significant contributions to the field of process mining. 99 Víctor José Gallego Fontenla Table A.2: Mean 𝐹𝑠𝑐𝑜𝑟𝑒 and Δ values for each algorithm using the hospital emergency ward process logs. (Continued) 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 re 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 rp 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 𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ𝐹𝑠𝑐𝑜𝑟𝑒 Δ Continues on next page 106 Appendix A. Sudden drift detection: supplementary experiments Table A.2: Mean 𝐹𝑠𝑐𝑜𝑟𝑒 and Δ values for each algorithm using the hospital emergency ward process logs. (Continued) 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 Average 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 contains detailed results for the experiments of CRIER for the synthetic logs of the Loan Application process. B.1 Linear logs . Table B.1 shows the results for the linear gradual changes with slopes of 0.1% , 0.2% , 0.5% , and 1.0%. Table B.1: 𝐹𝑠𝑐𝑜𝑟𝑒 , Δ and Υ values for the logs with linear gradual changes. The colors highlight the best performing approach for each metric. cf 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 Martjushev et al. ProDrift 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ Continues on next page Víctor José Gallego Fontenla Table B.1: 𝐹𝑠𝑐𝑜𝑟𝑒 , Δ and Υ values for the logs with linear gradual changes. The colors highlight the best performing approach for each metric. (Continued) 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% re 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% rp 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 Martjushev et al. ProDrift 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ Continues on next page 110 Appendix B. Gradual drift detection: supplementary experiments Table B.1: 𝐹𝑠𝑐𝑜𝑟𝑒 , Δ and Υ values for the logs with linear gradual changes. The colors highlight the best performing approach for each metric. (Continued) 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% Average 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 Martjushev et al. ProDrift 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ B.2 Gaussian logs . Table B.2 shows the results for the detection of gradual changes in logs that follow two Gaussian distributions. 111 Víctor José Gallego Fontenla Table B.2: 𝐹𝑠𝑐𝑜𝑟𝑒 , Δ and Υ values for the logs with Gaussian gradual changes. The colors highlight the best performing approach for each metric. cf 𝜇=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% re 𝜇=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% rp 𝜇=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% Average 𝜇=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 Martjushev et al. 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ B.3 Exponential logs . Table B.3 shows the results for the detection of gradual changes in logs that follow three exponential distributions with 𝜆set to 0.05, 0.1, and 0.5. 112 Appendix B. Gradual drift detection: supplementary experiments Table B.3: 𝐹𝑠𝑐𝑜𝑟𝑒 , Δ and Υ values for the logs with exponential gradual changes. The colors highlight the best performing approach for each metric. cf 𝜆=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% re 𝜆=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% rp 𝜆=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 Martjushev et al. 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ Continues on next page 113 Víctor José Gallego Fontenla Table B.3: 𝐹𝑠𝑐𝑜𝑟𝑒 , Δ and Υ values for the logs with exponential gradual changes. The colors highlight the best performing approach for each metric. (Continued) 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% Average 𝜆=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 Martjushev et al. 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ B.4 Constant logs . Table B.4 shows the results for the detection of gradual changes in logs that follow three different constant distributions. Table B.4: 𝐹𝑠𝑐𝑜𝑟𝑒 , Δ and Υ values for the logs with constant gradual changes. The colors highlight the best performing approach for each metric. cf 𝑝=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 Martjushev et al. 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ Continues on next page 114 Appendix B. Gradual drift detection: supplementary experiments Table B.4: 𝐹𝑠𝑐𝑜𝑟𝑒 , Δ and Υ values for the logs with constant gradual changes. The colors highlight the best performing approach for each metric. (Continued) re 𝑝=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% rp 𝑝=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% Average 𝑝=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 Martjushev et al. 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 𝐹𝑠𝑐𝑜𝑟𝑒 Δ Υ 115