Dissertação
{pt_PT=Automatically Geo-referencing Tabular Descriptions of Historic Routes} {} EVALUATED
{pt=Itinerários históricos, frequentemente acessíveis como tabelas que listam sítios visitados em sequência, são recursos abundantes e importantes objetos de estudo para investigadores humanistas. Este trabalho avança métodos novos para automaticamente geocodificar itinerários tabulares. Combinando correspondência aproximada de strings com algoritmos de optimização de custo, especificamente a procura A* para encontrar caminhos de menor custo, entre pares de locais, sobre um raster que codifica inclinação de terreno, juntamente com um método de programação dinâmica baseado no algoritmo de Viterbi para encontrar sequências de locais que minimizem o custo total. Correspondência de strings foi testada tanto com medidas de similaridade de strings bem estabelecidas como com algoritmos que são estado da arte usando aprendizagem automática. Experiências com dados de itinerários históricos, geocodificados por especialistas com coordenadas verdadeiras, e também com o gazetteer GeoNames, usado para correspondência de topónimos e para treino de algoritmos supervisionados, atestam a eficácia deste método. Os resultados obtidos demonstram que, enquanto que a correspondência de strings consegue medianas de erro baixas, com muitos topónimos a corresponderem exatamente com entradas do GeoNames, a combinação com algoritmos de optimização melhora significativamente os resultados em termos da distância de erro média. Além disso, usar caminhos de menor custo para reconstruir rotas prováveis entre pares de locais permite inquirir e inferir novas hipóteses sobre rotas históricas. Este estudo demonstra que métodos alavancando a intuição que os viajantes escolhem caminhos óptimos, em combinação com correspondência aproximada de strings para encontrar topónimos correspondentes ao itinerário, são de facto eficazes para geocodificar automaticamente estes recursos., en=Historical itineraries, often accessible as tables describing places visited in sequence, are abundant resources and also important objects of study for humanities scholars. This work advances a novel method for automatically geocoding tabular itineraries, combining approximate string matching with cost optimization algorithms, specifically A* search for finding least-cost paths between pairs of locations over a raster encoding terrain slope, together with a dynamic programming method based on the Viterbi algorithm for finding sequences of locations that minimize the overall cost. Approximate string matching was tested with both well established string similarity measures and state-of-the-art supervised machine learning algorithms. Experiments with a dataset of historical itineraries, with ground-truth geocoding annotations provided by domain experts, and with also the GeoNames gazetteer used for toponym matching and for the training of the supervised algorithms, attest to the effectiveness of the proposed method. The obtained results show that, while approximate string matching alone can already achieve very low median errors, with many toponyms matching exactly against GeoNames entries, the combination with cost optimization can significantly improve results in terms of the average distance towards the correct disambiguations. Moreover, the usage of least-cost paths for reconstruting the most likely routes between pairs of locations can enable new inquiries and inferences about historical routes. This study shows that methods leveraging the intuition that travelers choose optimal routes, in combination with approximate string matching for finding gazetteer entries matching the toponyms in the itineraries, are indeed effective for automatically geocoding these resources.}
outubro 31, 2017, 13:0
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
Bruno Emanuel Da Graça Martins
Departamento de Engenharia Informática (DEI)
Professor Auxiliar