A caminhada do turista como ferramenta na identificação de padrões

Autor: Campiteli, Mônica Guimarães
Jazyk: portugalština
Rok vydání: 2007
Předmět:
Druh dokumentu: Tese de Doutorado
Popis: A caminhada do turista pode ser enunciada num meio desordenado formado por N pontos espalhados aleatoriamente num hipercubo de d dimensoes. Um caminhante, partindo de um ponto qualquer desse meio, se desloca seguindo a regra determinista de dirigir-se sempre ao ponto mais proximo que nao tenha sido visitado nos ultimos µ pas- sos. Esta dinamica de movimentacao leva a trajetorias formadas por uma parte inicial transiente de t pontos, e uma parte final c?clica de p pontos. As trajetorias obtidas sao altamente dependentes da configuracao do meio. Este cenario sugere que este modelo possa ser usado como uma ferramenta de reconhecimento de padroes em conjuntos de dados. O objetivo desta tese e mostrar que as propriedades da caminhada do turista permitem a sua utilizacao na caracterizacao e exploracao de diversos tipos de sistemas. Aplicamos o modelo descrito em dois tipos distintos de sistemas, sistemas cont´?nuos e redes regulares, estudando suas ropriedades em funcao de parametros como tamanho do sistema, valor de memoria (µ), condicoes de contorno e regras de movimentacao. Finalmente, propomos e exploramos duas novas metodologias de reconhecimento de padroes baseadas nesta caminhada. A primeira consiste de um algoritmo de an´alise de imagens para caracterizar texturas que utiliza os resultados da matriz conjunta S(t, p) que carrega as informacoes sobre todas as trajetorias obtidas, reduzindo sua dimensionalidade e permitindo a classificacao eficiente de diferentes classes de imagens por um algoritmo de analise discriminante. O diferencial desta metodologia esta em sua capacidade de extrair da imagem as informacoes presentes em diversas escalas simultaneamente. A segunda metodologia e um algoritmo de agrupamento de dados n~ao supervisionado que considera cada atrator formado num dado valor de µ como um agrupamento natural e tem como resultado final uma arvore hierarquica geral, onde os grupos se conectam conforme se aumenta o valor de µ. Os resultados desta metodologia comparam-se em eficiencia aos resultados obtidos pela metodologia adicional para os dados testados e, entre as vanta- gens obtidas, podemos citar (i) independencia de uma metrica relacionando os elementos do conjunto, ja que trabalha apenas com uma matriz de vizinhancas, (ii) respeito a estrutura natural embutida no conjunto de dados, gerando uma arvore geral ao inves de uma arvore binaria e (iii) a representacao de maneira identica de conjuntos que sofreram transformacao de escala devido a independencia de uma metrica.
The tourist walk is defined in a disordered environment characterized by N points randomly distributed in a d-dimensional hypercube. Leaving from a given point, a wal- ker moves according to the deterministic rule of going to next point not visited in the last µ time steps. This dynamics leads to trajectories consisting in a transient part of t points e a final cyclic part of p points. The obtained trajectories are strongly dependent on the configuration of points. This described scenario suggests that the model can be treated as a tool for pattern recognition. The aim of this thesis is to demonstrate that the tourist walk\'s properties allow for its use in the characterization and exploration of various kinds of systems. We have applied the model in two distinct kinds of systems - continuous systems and regular networks and studied its properties as a function of the following parameters: system size, memory (µ), boundary conditions and movimentation rule. Eventually we have proposed and explored two new pattern recognition methodolo- gies based on this deterministic walk. The first one consists of an image analysis algorithm to characterize textures that makes use of the joint matrix S(t, p) which carries the data about all trajectories obtained, reducing its dimensionality and allowing an efficient clas- sification of different classes of images by a discriminant analysis algorithm. Its distinctive feature is its ability to extract informations in all scales from an image simultaneously. The second methodology proposed is a non-supervised clustering algorithm that considers each attractor in a given µ as a natural cluster. Its final result is a general hierarchical tree where groups coalesce as µ is increased. The results obtained with this methodology are comparable in efficiency with the results obtained with the tradicional method for the datasets tested. Among the advantages presented we can cite (i) independence from a metrics relating the elements since it works only with a neighborhood ranking table, (ii) respect for the natural structure hidden in the dataset, generating a general tree instead of a binary one and (iii) the representation of two sets transformed by scale in an identic manner due to the independence from a metrics.
Databáze: Networked Digital Library of Theses & Dissertations
Externí odkaz: