Clustering symbolic temporal sequences using Temporal Needleman-Wunsch algorithm

November 17, 2023

O constante desenvolvimento de novas tecnologias revolucionou a forma como as informações dos pacientes são coletadas, armazenadas e utilizadas, especialmente com a maior integração e capacidades dos Prontuários Eletrônicos de Saúde (PES). Embora as abordagens de medicina de precisão baseadas em DNA sejam frequentemente caras, a análise de dados de PES oferece uma alternativa mais acessível e rápida. Os dados médicos costumam ser disponibilizados na forma de sequências temporais, motivando pesquisas em áreas de máquinas como mineração de padrões longitudinais. Nesse contexto, o AliClu, uma solução de agrupamento para sequências temporais simbólicas, combina técnicas como o algoritmo Temporal Needleman-Wunsch, agrupamento hierárquico aglomerativo e validação por bootstrap. O objetivo deste estudo é otimizar o tempo de execução do AliClu para expandir sua aplicação a conjuntos de dados mais amplos e permitir pesquisas mais eficientes em termos de tempo. Além disso, esta pesquisa investiga os índices de validação de agrupamento usados pela solução para melhor entender a seleção automática do número ótimo de clusters por parte do AliClu. Através de experimentos com conjuntos de dados sintéticos criados usando Cadeias de Markov de Tempo Contínuo e dados reais derivados do banco de dados da Sociedade Portuguesa de Reumatologia, a tese demonstra melhorias significativas no desempenho após a otimização. No entanto, também revela limitações no modo automático do AliClu, sugerindo espaço para aprimoramentos adicionais do tempo de execução e dos parâmetros de alinhamento. The constant development of new technologies has revolutionized the way patient information is collected, stored and used, specially with greater integration and capabilities of Electronic Health Records (EHRs). While DNA-based precision medicine approaches are often costly, the analysis of EHR data offers a more accessible and faster alternative. Medical data is often available in the form of temporal sequences, motivating research on machine areas such as longitudinal pattern mining. In this context, AliClu, a clustering solution for symbolic temporal sequences, combines techniques like Temporal Needleman-Wunsch algorithm, hierarchical agglomerative clustering, and bootstrapping validation. The focus of this study is optimizing AliClu's time performance to expand its application to broader datasets and enable more time-effective research. Additionally, the research investigates the clustering validation indices used by the solution to better understand its automatic selection of the optimal number of clusters. Through experiments with synthetic datasets created using Continuous-Time Markov Chains (CTMC) and real-world data derived from the Portuguese Society of Rheumatology database, the thesis demonstrates significant performance improvements post-optimization. However, it also reveals limitations in AliClu's automatic mode, suggesting room for further enhancement of execution time and alignment parameters.

Authors in the community:

• 

  M

  Matheus de Almeida Orsi e Silva

  ist192238

Supervisors of this institution:

• 

  S

  Susana de Almeida Mendes Vinga Martins

  ist14109

• 

  A

  Alexandra Sofia Martins de Carvalho

  ist45173

Mestrado em Engenharia Informática e de Computadores

electrical-engineering-electronic-engineering-information-engineering - Electrical engineering, electronic engineering, information engineering

Keywords

• AliClu
• clustering
• clustering indices
• parallelization
• temporal sequence alignment
• agrupamento
• alinhamento de sequências temporais
• índices de agrupamento
• paralelização

eng - English

Instituto Superior Técnico