Submitted by Lucienne Costa (lucienneferreira@ufcg.edu.br) on 2018-05-03T21:26:06Z No. of bitstreams: 1 FRANCISCO DANTAS NOBRE NETO – TESE (PPGCC) 2017.pdf: 3110801 bytes, checksum: e2803429a1a01abf91502c50bc0ea1df (MD5) / Made available in DSpace on 2018-05-03T21:26:06Z (GMT). No. of bitstreams: 1 FRANCISCO DANTAS NOBRE NETO – TESE (PPGCC) 2017.pdf: 3110801 bytes, checksum: e2803429a1a01abf91502c50bc0ea1df (MD5) Previous issue date: 2017-05 / Com a ampla difusão de smartphones equipados com dispositivos GPS (Global Positioning System), rastrear a localização de objetos (como pessoas e veículos) tem sido uma tarefa mais factível, resultando em novas oportunidades de pesquisas em variadas áreas do conhecimento. Dentre estas oportunidades, esta pesquisa lida com o desafio da área de previsão de rotas e destinos. Saber antecipadamente o destino de um usuário assim que ele inicia um deslocamento tem muitas utilidades práticas, tais como: indicar rotas menos congestionadas ou vias mais seguras, e sugerir a visita a algum ponto de interesse (POI) antes do destino almejado. Sistemas que fornecem previsão de rota e destino estão disponíveis comercialmente, no entanto, estes podem requerer interações constantes do usuário. Para deslocamentos diários, porém, a necessidade de uma interação frequente do usuário com um aplicativo pode tornar seu uso pouco prático e pouco ubíquo. Além disso, muitos trabalhos que apresentam modelos de previsão de rotas e destinos, disponíveis na literatura, não contemplam uma importante informação contextual, que é o papel que os lugares visitados representam para um usuário (por exemplo, se é sua casa ou seu local de trabalho). Não obstante, a maioria dos preditores disponíveis não possuem a funcionalidade de prever lugares nunca visitados. Esta tese de doutorado propõe uma família de métodos de predição baseada no algoritmo de compressão de dados Prediction by Partial Matching (PPM). Ainda com relação a esta pesquisa, é proposto um mecanismo capaz de identificar que uma rota em curso está sendo realizada pela primeira vez e, portanto, ter a possibilidade de prever um destino ainda não visitado. Neste estudo, também foram implementados outros preditores consolidados na literatura, que são as Cadeias de Markov e as Cadeias Ocultas de Markov, utilizados para comparação. É importante observar que ambos os preditores são capazes de prever apenas o destino de um trajeto, ao invés da rota restante. Nos experimentos realizados, foram utilizadas as métricas de Precisão, Recall e Medida-F (F1 Score), com validação cruzada (contendo 10 partições mutuamente exclusivas), para avaliação dos modelos de previsão implementados. A base de dados utilizada nesta pesquisa é composta por mais de 1.500 rotas, coletadas por aproximadamente três meses, referentes a 21 usuários. Os preditores baseados em PPM apresentaram resultados competitivos (ou superiores) comparados aos da literatura. / Thanks to the widely diffusion of smartphones with GPS devices natively embedded, the task of tracking object locations, such as people or vehicles, is more feasible nowadays, fostering new research opportunities. Among these new opportunities, this work addresses the challenge of route and destination prediction. Knowing in advance the destination where a user might reach as soon as he or she starts to move can be useful in various situations. For instance, to suggest to users less jammed or safer routes, as well to warn about points of interest located along their route. There are commercial systems capable of predicting destination and routes, however, these systems usually require frequent user interaction. Nonetheless, such a requirement could make the application unusable for daily routines. Moreover, most existing works do not consider an important contextual information: the information about the places that the users visit, i.e., the role that the places play to the user (for instance, if the place is home or work). In addition, most predictors described in the literature are not able to predict places that users have never visited. This thesis proposes a family of algorithms based on Prediction by Partial Matching (PPM). Furthermore, this work proposes a mechanism for identifying whether a route is being performed for the first time, resulting in the feasibility for predicting a never visited place. This research also provides a comparison between our proposed predictors, and the predictors based on Markov Models and Hidden Markov Models (HMM), which have been used in related works. It is important to mention that both Markov and HMM predictors that we implemented are able to predict just the destination, instead the remaining route. For the statistical assessment of the predictors, the metrics Precision, Recall and F1 Score are used, together with the process of 10-fold cross- validation. The database contains about 1,500 routes extracted from 21 users, gathered for three months. The predictors based on PPM performed similarly (or better) than others reported in the literature.