O volume de informação manipulada em sistemas apoiados por computador tem crescido tanto no número de objetos que compõem os conjuntos de dados quanto na quantidade e na complexidade dos atributos. Em conjuntos de dados do mundo real, a uniformidade na distribuição de valores e a independência entre atributos são propriedades bastante incomuns. De fato, dados reais são em geral caracterizados pela ampla presença de correlações entre seus atributos. Além disso, num mesmo conjunto podem existir correlações de naturezas diversas, como correlações lineares, não-lineares e não-polinomiais. Todo esse cenário pode degradar a performance dos algoritmos que manipulam e, principalmente, dos que realizam análises dos dados. Além da grande quantidade de objetos a serem tratados e do número elevado de atributos, as correlações nem sempre são conhecidas, o que pode comprometer a eficácia de tais algoritmos. Nesse contexto, as técnicas de redução de dimensionalidade permitem diminuir o número de atributos de um conjunto de dados, minimizando assim os problemas decorrentes da alta dimensionalidade. Algumas delas são baseadas na análise de correlações e, com o objetivo de reduzir a perda de informação relevante causada pela remoção de atributos, procuram eliminar apenas aqueles que sejam correlacionados aos restantes. No entanto, essas técnicas geralmente analisam como cada atributo está correlacionado a todos os demais, tratando o conjunto de atributos como um todo e usando ferramentas de análise estatística. Esta tese propõe uma abordagem diferente, baseada na Teoria dos Fractais, para detectar a existência de correlações e identificar subconjuntos de atributos correlacionados. Para cada correlação encontrada é possível ainda identificar quais são os atributos que melhor a descrevem. Conseqüentemente, um subconjunto de atributos relevantes para representar as características fundamentais dos dados é determinado, não apenas com base em correlações globais entre todos os atributos, mas também levando em consideração especificidades de correlações que envolvem subconjuntos reduzidos. A técnica apresentada é uma ferramenta a ser utilizada em etapas de pré-processamento de atividades de descoberta de conhecimento, principalmente em operações de seleção de atributos para redução de dimensionalidade. A proposta para a identificação de correlações e os conceitos que a fundamentam são validados por meio de estudos experimentais usando tanto dados sintéticos quanto reais. Finalmente, os conceitos básicos da Teoria dos Fractais são aplicados na análise de comportamento de data streams, também constituindo uma contribuição relevante desta tese de doutorado. / The volume of information processed by computer-based systems has grown not only in the amount of data but also in number and complexity of attributes. In real world datasets, uniform value distribution and independence between attributes are rather uncommon properties. In fact, real data is usually characterized by vast existence of correlated attributes. Moreover, a dataset can present different types of correlations, such as linear, non-linear and non-polynomial. This entire scenario may degrade performance of data management and, particularly, data analysis algorithms, as they need to deal with large amount of data and high number of attributes. Furthermore, correlations are usually unknown, which may jeopardize the efficacy of these algorithms. In this context, dimensionality reduction techniques can reduce the number of attributes in datasets, thus minimizing the problems caused by high dimensionality. Some of these techniques are based on correlation analysis and try to eliminate only attributes that are correlated to those remaining, aiming at diminishing the loss of relevant information imposed by attribute removal. However, techniques proposed so far usually analyze how each attribute is correlated to all the others, considering the attribute set as a whole and applying statistical analysis tools. This thesis presents a different approach, based on the Theory of Fractals, to detect the existence of correlations and to identify subsets of correlated attributes. In addition, the proposed technique makes it possible to identify which attributes can better describe each correlation. Consequently, a subset of attributes relevant to represent the fundamental characteristics of the dataset is determined, not only based on global correlations but also considering particularities of correlations concerning smaller attribute subsets. The proposed technique works as a tool to be used in preprocessing steps of knowledge discovery activities, mainly in feature selection operations for dimensionality reduction. The technique of correlation detection and its main concepts are validated through experimental studies with synthetic and real data. Finally, as an additional relevant contribution of this thesis, the basic concepts of the Theory of Fractals are also applied to analyze data streams behavior.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-01092006-113751 |
| Date | 29 March 2006 |
| Creators | Elaine Parros Machado de Sousa |
| Contributors | Caetano Traina Junior, Carlos Alberto Heuser, Claudia Maria Bauzer Medeiros, Maria Carolina Monard, Altigran Soares da Silva |
| Publisher | Universidade de São Paulo, Ciências da Computação e Matemática Computacional, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0022 seconds