Aproximação de Conformance Checking utilizando Directly-follows Graph Estendidos

Resumo

Conformance Checking é um campo em Mineração de Processos relevante para auditoria e alinhamento em processos de negócio (AALST, 2016). Neste campo, o modelo de processo é comparado com seu respectivo log de eventos com o objetivo de verificar similaridades e discrepâncias (AALST, 2016). Essa verificação ocorre através de dimensões de qualidade como fitness e precisão. Nesse contexto, alignments (AALST, 2012) é uma das técnicas mais utilizadas para mensurar o fitness com vasto respaldo na literatura (BUIJS, 2014). A maioria das técnicas que calculam alignments oferecem soluções exatas (BUIJS, 2014). Entretanto, em diversas aplicações é suficiente obter um valor aproximado. Além disso, em se tratando  de logs de big data, o tempo necessário para cálculo dos alignments é considerado longo e inaplicável em aplicações reais (AALST, 2012). Devido a essa limitação, propostas na literatura aproximam o valor do alignment com redução no tempo computacional necessário para a tarefa. Sani et al. (2020) propõem a utilização de subconjuntos do log para cálculo aproximado do alignment.  Entretanto, essa abordagem realiza alignments da forma tradicional estando sujeito a limitações semelhantes e com performance dependente do número de variantes no log de eventos. Outra abordagem, presente  na biblioteca PM4py (BERTI, 2019), permite a realização de alignments em estruturas mais simples chamadas Directly-follows graphs (DFG) que podem ser obtidas a partir do sistema de transição de uma Petri-net. Uma das limitações de tal abordagem é a perda do paralelismo do sistema de transição ao convertê-lo em um DFG (AALST, 2016), o que implicará em alignments realizados incorretamente. Neste trabalho, propõe-se um método que incorpora no DFG múltiplas instâncias de uma mesma atividade presente no sistema de transição como forma de conservar o paralelismo da Petri-net. Neste método, sufixos são adicionados às atividades repetidas de forma que elas possuam valor único ao compor o DFG. Durante a realização do alignment, os sufixos são ignorados. Para avaliar a técnica proposta, foram utilizados 50 logs reais e 3 diferentes algoritmos de descoberta de processos para obtenção das Petri-nets e realização dos alignments real e aproximados. Em seguida, foram comparadas as técnicas de subconjunto, DFG tradicional e a proposta apresentada no quesito qualidade da aproximação do alignment e custo computacional envolvido. Os resultados sugerem que a proposta melhora substancialmente os resultados de alignments em DFGs tradicionais e mantém o seu baixo custo computacional. Dessa forma, os resultados se igualam aos obtidos com subconjuntos, porém com tempo computacional menor em torno de uma ordem de grandeza.