A mineração de dados é um processo computacionalmente caro, que se apoia no pré-processamento dos dados para aumentar a sua eficiência. As técnicas de redução de elementos do conjunto de dados, principalmente a amostragem de dados se destacam no pré-processamento. Os dados reais são caracterizados pela não uniformidade da distribuição, grande quantidade de atributos e presença de elementos considerados ruídos. Para esse tipo de dado, a amostragem uniforme, na qual cada elemento tem a mesma probabilidade de ser escolhido, é inefiiente. Os dados nos últimos anos, vem passando por transformações. Assim, não só o seu volume tem aumentado significantemente, mas também a maneira de como eles são representados. Os dados usualmente são divididos apenas em dados tradicionais (número e pequenas cadeias de caracteres) e dados complexos (imagens, cadeias de DNA, vídeos, etc). Entretanto, uma representação mais rica, na qual não só os elementos do conjunto são representados mas também a suas ligações, vem sendo amplamente utilizada. Esse novo tipo de dado, chamado rede complexa, fez surgir uma nova área de pesquisa chamada mineração de redes complexas ou de grafos, já que estes são utilizados na representação das redes complexas. Para esta nova área é necessário o desenvolvimento de técnicas que permitam a mineração de grandes redes complexas, isto é, redes com centenas de milhares de elementos(nós) e ligações(arestas). Esta tese teve como objetivo explorar a redução de elementos em conjuntos de dados chamados desbalanceados, isto é, que possuem agrupamentos ou classes de tamanhos bastantes distintos, e que também possuam alta quantidade de atributos e presença de ruídos. Além disso, esta tese também explora a mineração de redes complexas com a extração de padrões e propriedades e o desenvolvimento de algoritmos eficientes para a classificação das redes em reais e sintéticas. Também é proposto a mineração de redes complexas utilizando gerenciadores de base de dados para a mineração de cliques de tamanho 4 e 5 e a apresentação da extensão do coeficiente de clusterização / Data mining is an expensive computational process speeded up by data preprocessing. Data reduction techniques, as data sampling are useful during the data preprocessing. Real data are known for presenting non-uniform data distribution, a large amount of attributes and noise. For this type of data, uniform sampling, which selects elements with the same probability, is inefficient. Over the past years, the data available to mining have been changed. Not only have their volume increased but also data format. Data are usually divided into traditional (number and small chains of character) and complex (images, DNA, videos, etc). However, a rich representation, in which not only elements but also the connections among the elements have been used, is necessary. This new data type, which is called complex network and is usually modeled as a graph, has created a new research area, called graph mining or complex network mining, which requires the development of new mining techniques to allow mining large networks, that is, networks with hundreds of thousands of nodes and edges. The present thesis aims to explore the data reduction in unbalanced data, that is, data that have clusters with very different sizes, a large amount of attributes and noise. It also explores complex network mining with two basic findings: useful new patterns, which allow distinguishing real from synthetic networks and mining cliques of sizes 4 and 5 using database systems, discovering interesting power laws and presenting a new cluster coefficient formula
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-13072010-101429 |
| Date | 27 May 2010 |
| Creators | Ana Paula Appel |
| Contributors | Caetano Traina Junior, Renato Fileto, Estevam Rafael Hruschka Junior, Javam de Castro Machado, Roseli Aparecida Francelin Romero |
| 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.0024 seconds