FenixEdu™

Dissertação

{en_GB=Time series data imputation - Comparison of Dynamic Time Warping with Needleman-Wunsch algorithm} {} EVALUATED

Detalhes: {pt=Os algoritmos de aprendizagem automática estão a ser desenvolvidos e aplicados a dados que ajudam a população nas suas necessidades diárias. Estes algoritmos trazem muitos benefícios a diferentes áreas e possibilitam análises preditivas, formação de grupos de classes (clustering) e classiﬁcação dos dados. Podem ser usados, por exemplo, em bases de dados médicas para facilitar o diagnóstico e o tratamento de um paciente. Em relação à eﬁciência destes algoritmos, existe uma preocupação acrescida no que se refere a valores em falta nos dados. Os algoritmos que existem não estão preparados para lidar com a falta destes dados, pelo que existe a necessidade de se abordar este tema. Assim, neste trabalho, pretende-se comparar dois algoritmos de imputação de dados que poderão ser usados para completar os dados em falta. Os algoritmos usados são o Dynamic Time Warping e Needleman-Wunsch. Veriﬁcou-se que estes dois algoritmos são capazes de preencher os dados em falta, onde o Dynamic Time Warping se revelou mais preciso, enquanto que o Needleman-Wunsch se revelou mais rápido. Com este trabalho também se veriﬁcou que estes dois algoritmos podem ser testados em mais profundidade devido ao seu potencial para preencher os dados em falta. Também são feitas sugestões para melhorar alguns pontos menos positivos em relação à performance dos mesmos., en=Machine learning algorithms are now being designed and applied to data to help humans in their everyday needs. These algorithms can bring major beneﬁts to many areas and are capable of conducting predictions, clustering and classiﬁcation on data. They could be used, for example, on medical databases to help in treatments and diagnosis of patients. One major concern that threatens the efﬁciency of these algorithms are missing values. Many algorithms which are in place today are not prepared to handle these missing values, which means they have to be handled in other ways. In this paper it is aimed to compare two imputation algorithms that could be used in ﬁlling these missing values. Both methods use sequence alignment to ﬁnd matches with which the missing values could then be imputed. One of the algorithms uses dynamic time warping while the other uses Needleman-Wunsch. Both of these algorithms were suitable when it came to data imputation. Imputation done using dynamic time warping was accurate, although it lacked in speed, while the Needleman-Wunsch imputation was faster, but not quite as accurate as the dynamic time warping imputation. The results show that both of these algorithms should be further tested due to their potential in the imputation of values, as well as some suggestions to strengthen the weaknesses of both of these algorithms.}
Keywords: {pt=Aprendizagem automática, data mining, valores em falta, Dynamic Time Warping, Needleman-Wunsch, en=Machine learning, data mining, missing values, Dynamic Time Warping, Needleman-Wunsch}

Discussão: novembro 22, 2019, 17:30