Técnicas de projeção desempenham papel importante na análise e exploração de dados multidimensionais, já que permitem visualizar informações muitas vezes ocultas na alta dimensão. Esta tese explora o potencial destas técnicas para resolver problemas relacionados à: 1) identificação de agrupamentos e 2) busca por similaridade em dados multidimensionais. Para identificação de agrupamentos foi desenvolvida uma técnica de projeção local e interativa que, além de projetar dados com ótima preservação de distâncias, permite que o usuário modifique o layout da projeção, agrupando um número reduzido de amostras representativas no espaço visual, de acordo com suas características. Os mapeamentos produzidos tendem a seguir o layout das amostras organizadas pelo usuário, facilitando a organização dos dados e identificação de agrupamentos. Contudo, nem sempre é possível selecionar ou agrupar amostras com base em suas características visuais de forma confiável, principalmente quando os dados não são rotulados. Para estas situações, um novo método para identificação de agrupamentos baseado em projeção foi proposto, o qual opera no espaço visual, garantindo que os grupos obtidos não fiquem fragmentados durante a visualização. Além disso, é orientado por um mecanismo de amostragem determinístico, apto a identificar instâncias que representam bem o conjunto de dados como um todo e capaz de operar mesmo em conjuntos de dados desbalanceados. Para o segundo problema: busca por similaridade em dados multidimensionais, uma família de métricas baseada em classes foi construída para projetar os dados, com o objetivo de minimizar a dissimilaridade entre pares de objetos pertencentes à mesma classe e, ao mesmo tempo, maximizá-la para objetos pertencentes a classes distintas. As métricas classes-específicas são avaliadas no contexto de recuperação de imagens com base em conteúdo. Com o intuito de aumentar a precisão da família de métricas classes-específicas, outra técnica foi desenvolvida, a qual emprega a teoria dos conjuntos fuzzy para estimar um valor de incerteza que é transferido para a métrica, aumentando sua precisão. Os resultados confirmam a efetividade das técnicas desenvolvidas, as quais representam significativa contribuição na tarefa de identificação de grupos e busca por similaridade em dados multidimensionais. / Projection techniques play an important role in multidimensional data analysis and exploration, since they allow to visualize information frequently hidden in high-dimensional spaces. This thesis explores the potential of those techniques to solve problems related to: 1) clustering and 2) similarity search in multidimensional data. For clustering data, a local and interactive projection technique capable of projecting data with effective preservation of distances was developed. This one allows the user to manipulate a reduced number of representative samples in the visual space so as to better organize them. The final mappings tend to follow the layout of the samples organized by the user, therefore, the user can interactively steer the projection. This makes it easy to organize and group large data sets. However, it is not always possible to select or group samples visually, in a reliable manner, mainly when handling unlabeled data. For these cases, a new clustering method based on multidimensional projection was proposed, which operates in the visual space, ensuring that clusters are not fragmented during the visualization. Moreover, it is driven by a deterministic sampling mechanism, able to identify instances that are good representatives for the whole data set. The proposed method is versatile and robust when dealing with unbalanced data sets. For the second problem: similarity search in multidimensional data, we build a family of class-specific metrics to project data. Such metrics were tailored to minimize the dissimilarity measure among objects from the same class and, simultaneously to maximize the dissimilarity among objects in distinct classes. The class-specific metrics are assessed in the context of content-based image retrieval. With the aim of increasing the precision of the class-specific metrics, another technique was developed. This one, uses the fuzzy set theory to estimate a degree of uncertainty, which is embedded in the metric, increasing its precision. The results confirm the effectiveness of the developed techniques, which represent significant contributions for clustering and similarity search in multidimensional data.
Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-29032016-143247 |
Date | 14 October 2015 |
Creators | Joia Filho, Paulo |
Contributors | Nonato, Luis Gustavo |
Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
Source Sets | Universidade de São Paulo |
Language | Portuguese |
Detected Language | Portuguese |
Type | Tese de Doutorado |
Format | application/pdf |
Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0019 seconds