Devido aos avanços tecnológicos ocorridos nos últimos anos, houve um aumento na quantidade e complexidade de dados gerados. Assim, aprofundou-se a necessidade do desenvolvimento de estratégias eficientes que permitam o armazenamento, a recuperação e a representação resumida desses tipos de dados complexos. Dentre as estratégias exploradas pelos pesquisadores da área para atender a esses propósitos estão os Métodos de Acesso. Esses métodos têm como objetivo indexar os dados de maneira eficaz para reduzir o tempo de consulta. Além disso, eles têm sido aplicados para apoiar o processamento de técnicas de Mineração de Dados, como a Detecção de Agrupamentos. Dentre os métodos de acesso, as estruturas de indexação métrica são construídas usando apenas o critério baseado na distância entre os elementos do conjunto de dados em questão, i.e. operações de similaridade sobre as características intrínsecas dos dados. Desse modo, nem sempre os resultados correspondem ao contexto desejado pelo usuário. Este trabalho explorou o desenvolvimento de algoritmos que permitam aos métodos de acesso métrico processarem detecção de agrupamento de dados para auxiliar o processamento de consultas com maior carga semântica; visando contribuir no tratamento da questão da eficiência de abordagens que envolvam operações por similaridade (por exemplo, técnicas de mineração de dados e consultas por similaridade). Diante deste contexto, foram desenvolvidas três abordagens, a primeira apresenta o método clusMAM (Unsupervised Clustering using Metric Access Methods), o qual tem como objetivo apresentar um agrupamento dos dados com a aplicação de um Método de Acesso Métrico a partir de um conjunto resumido dos dados. A segunda abordagem apresenta a abordagem CCkNN (Class-Constraint k-NN) para lidar com o problema de restrições de múltiplas classes sobre o espaço de busca. Por fim, a terceira abordagem apresenta o método CfQ (Clustering for Querying) realizando a integração das técnicas clusMAM com CCkNN, empregando os pontos positivos de cada estratégia adotada pelos algoritmos. No geral, os experimentos realizados mostram que os métodos propostos contribuem de maneira efetiva na redução de medidas de similaridade requiridas durante um processamento de técnicas que são baseadas em computações de distância. / Due to the technological advances over the last years, both the amount and variety of data available have been increased at a fast pace. Thus, this scenario has influenced the development of effective strategies for the processing, summarizing, as well as to provide fast and automatic understanding of such data. The Access Methods are strategies that have been explored by researchers in the area to aid these purposes. These methods aim to effectively index data to reduce the time required for processing similarity querying. In addition, they have been applied to aid the processing of Data Mining techniques, such as Clustering Detection. Among the access methods, the metric structures are constructed applying only the criterion based on the distance computation between the elements of the dataset, i.e. similarity operations on the intrinsic characteristics of the dataset. Thus, the results do not always correspond to the context desired by users. This work explored the development of algorithms that allow metric access methods to process queries with a higher semantic load, aimed at contributing to the treatment of the quality question on the results of approaches that involve similarity operation (for example, data mining techniques and similarity queries). In this context, three approaches have been developed: the first approach presents the method clusMAM (Unsupervised Clustering using Metric Access Methods), which aims to display a clustering from a dataset with the application of a Metric Access Method from a summarized set. The second approach presents the CCkNN approach to dealing with the problem of multi-class constraints on the search space. Finally, the third proposal presents the method CfQ (Clustering for Querying) by integrating the techniques clusMAM with CCkNN, using the positive points of each strategy applied by the algorithms. In general, the experiments carried out showed that the proposed methods can contribute to an effective way of reducing similarity computations, which is required during a processing of techniques that are based on distance computations.

Devido aos avanços tecnológicos ocorridos nos últimos anos, houve um aumento na quantidade e complexidade de dados gerados. Assim, aprofundou-se a necessidade do desenvolvimento de estratégias eficientes que permitam o armazenamento, a recuperação e a representação resumida desses tipos de dados complexos. Dentre as estratégias exploradas pelos pesquisadores da área para atender a esses propósitos estão os Métodos de Acesso. Esses métodos têm como objetivo indexar os dados de maneira eficaz para reduzir o tempo de consulta. Além disso, eles têm sido aplicados para apoiar o processamento de técnicas de Mineração de Dados, como a Detecção de Agrupamentos. Dentre os métodos de acesso, as estruturas de indexação métrica são construídas usando apenas o critério baseado na distância entre os elementos do conjunto de dados em questão, i.e. operações de similaridade sobre as características intrínsecas dos dados. Desse modo, nem sempre os resultados correspondem ao contexto desejado pelo usuário. Este trabalho explorou o desenvolvimento de algoritmos que permitam aos métodos de acesso métrico processarem detecção de agrupamento de dados para auxiliar o processamento de consultas com maior carga semântica; visando contribuir no tratamento da questão da eficiência de abordagens que envolvam operações por similaridade (por exemplo, técnicas de mineração de dados e consultas por similaridade). Diante deste contexto, foram desenvolvidas três abordagens, a primeira apresenta o método clusMAM (Unsupervised Clustering using Metric Access Methods), o qual tem como objetivo apresentar um agrupamento dos dados com a aplicação de um Método de Acesso Métrico a partir de um conjunto resumido dos dados. A segunda abordagem apresenta a abordagem CCkNN (Class-Constraint k-NN) para lidar com o problema de restrições de múltiplas classes sobre o espaço de busca. Por fim, a terceira abordagem apresenta o método CfQ (Clustering for Querying) realizando a integração das técnicas clusMAM com CCkNN, empregando os pontos positivos de cada estratégia adotada pelos algoritmos. No geral, os experimentos realizados mostram que os métodos propostos contribuem de maneira efetiva na redução de medidas de similaridade requiridas durante um processamento de técnicas que são baseadas em computações de distância. / Due to the technological advances over the last years, both the amount and variety of data available have been increased at a fast pace. Thus, this scenario has influenced the development of effective strategies for the processing, summarizing, as well as to provide fast and automatic understanding of such data. The Access Methods are strategies that have been explored by researchers in the area to aid these purposes. These methods aim to effectively index data to reduce the time required for processing similarity querying. In addition, they have been applied to aid the processing of Data Mining techniques, such as Clustering Detection. Among the access methods, the metric structures are constructed applying only the criterion based on the distance computation between the elements of the dataset, i.e. similarity operations on the intrinsic characteristics of the dataset. Thus, the results do not always correspond to the context desired by users. This work explored the development of algorithms that allow metric access methods to process queries with a higher semantic load, aimed at contributing to the treatment of the quality question on the results of approaches that involve similarity operation (for example, data mining techniques and similarity queries). In this context, three approaches have been developed: the first approach presents the method clusMAM (Unsupervised Clustering using Metric Access Methods), which aims to display a clustering from a dataset with the application of a Metric Access Method from a summarized set. The second approach presents the CCkNN approach to dealing with the problem of multi-class constraints on the search space. Finally, the third proposal presents the method CfQ (Clustering for Querying) by integrating the techniques clusMAM with CCkNN, using the positive points of each strategy applied by the algorithms. In general, the experiments carried out showed that the proposed methods can contribute to an effective way of reducing similarity computations, which is required during a processing of techniques that are based on distance computations.

Made available in DSpace on 2016-06-02T19:05:21Z (GMT). No. of bitstreams: 1 DissAG.pdf: 1368372 bytes, checksum: a38fba0c17555bf840c80e653af2d007 (MD5) Previous issue date: 2005-05-20 / In this work, the MIGFIR (Metric Indexing and Geometric Features-based Image Retrieval) system is presented. This system was developed mainly to make possible to index and retrieve certain image classes (like human face images, for example) with efficiency and accuracy using geometric measures, two new similarity functions and the metric access method called Slim-tree. This system also allows configuring important parameters during the definition of queries and makes possible to apply fuzzy sets and related concepts so that the language used in search expressions of one of the query classes that are supported be considerably close of the language usually applied by human beings. Efficiency and accuracy of the system at the execution of queries on several real and synthetic human face image sets are also presented. About efficiency, the obtained results show that MIGFIR can promote a quite considerable reduction of the execution time of queries in comparison with a similar approach that applies sequential scanning of the data. About accuracy, the results show that performance is satisfactory during the retrieval of human faces similar to certain example-images. / Neste trabalho apresenta-se o sistema denominado MIGFIR (Metric Indexing and Geometric Features-based Image Retrieval), que foi desenvolvido principalmente para permitir que determinados tipos de imagens (como de faces humanas, por exemplo) sejam indexados e recuperados com eficiência e precisão usando suas medidas geométricas, duas novas funções de similaridade e o método de acesso métrico Slim-tree. Esse sistema também permite que os usuários configurem parâmetros relevantes durante a definição de consultas, e possibilita ainda aplicar conjuntos nebulosos e conceitos relacionados para que a linguagem empregada nas expressões de busca de uma das classes de consulta suportadas se aproxime consideravelmente da linguagem normalmente utilizada por seres humanos. A eficiência e a precisão do sistema na execução de consultas sobre vários conjuntos reais e sintéticos de imagens de faces humanas também são apresentadas. Com relação à eficiência, os resultados obtidos mostram que o uso de MIGFIR pode promover uma redução bastante considerável do tempo de execução de consultas em comparação com uma abordagem similar que aplica varredura seqüencial dos dados. Já em termos de precisão, os resultados mostram que o desempenho é satisfatório na recuperação de faces humanas similares a determinados tipos de imagens-exemplo.

It is well-known that the existing theoretical models for outlier detection make assumptions that may not reflect the true nature of outliers in every real application. This dissertation describes an empirical study performed on unsupervised outlier detection using 8 algorithms from the state-of-the-art and 8 datasets that refer to a variety of real-world tasks of practical relevance, such as spotting cyberattacks, clinical pathologies and abnormalities occurring in nature. We present our lowdown on the results obtained, pointing out to the strengths and weaknesses of each technique from the application specialists point of view, which is a shift from the designer-based point of view that is commonly adopted. Many of the techniques had unfeasibly high runtime requirements or failed to spot what the specialists consider as outliers in their own data. To tackle this issue, we propose MetricABOD: a novel ABOD-based algorithm that makes the analysis up to thousands of times faster, still being in average 26% more accurate than the most accurate related work. This improvement is tantamount to practical outlier detection in many real-world applications for which the existing methods present unstable accuracy or unfeasible runtime requirements. Finally, we studied two collections of text data to show that our MetricABOD works also for adimensional, purely metric data. / É conhecido e notável que os modelos teóricos existentes empregados na detecção de outliers realizam assunções que podem não refletir a verdadeira natureza dos outliers em cada aplicação. Esta dissertação descreve um estudo empírico sobre detecção de outliers não-supervisionada usando 8 algoritmos do estado-da-arte e 8 conjuntos de dados que foram extraídos de uma variedade de tarefas do mundo real de relevância prática, tais como a detecção de ataques cibernéticos, patologias clínicas e anormalidades naturais. Apresentam-se considerações sobre os resultados obtidos, apontando os pontos positivos e negativos de cada técnica do ponto de vista do especialista da aplicação, o que representa uma mudança do embasamento rotineiro no ponto de vista do desenvolvedor da técnica. A maioria das técnicas estudadas apresentou requerimentos de tempo impraticáveis ou falhou em encontrar o que os especialistas consideram como outliers nos conjuntos de dados confeccionados por eles próprios. Para lidar-se com esta questão, foi desenvolvido o método MetricABOD: um novo algoritmo baseado no ABOD que torna a análise milhares de vezes mais veloz, sendo ainda em média 26% mais acurada do que o trabalho relacionado mais acurado. Esta melhoria equivale a tornar a busca por outliers uma tarefa factível em muitas aplicações do mundo real para as quais os métodos existentes apresentam resultados instáveis ou requerimentos de tempo impassíveis de realização. Finalmente, foram também estudadas duas coleções de dados adimensionais para mostrar que o novo MetricABOD funciona também para dados puramente métricos.