• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Doctoral Thesis
DOI
10.11606/T.55.2011.tde-22112011-083653
Document
Author
Full name
Robson Leonardo Ferreira Cordeiro
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2011
Supervisor
Committee
Traina Junior, Caetano (President)
Faloutsos, Christos
Ferreira, João Eduardo
Heuser, Carlos Alberto
Moro, Mirella Moura
Title in English
Data mining in large sets of complex data
Keywords in English
Correlation clustering
Labeling and summarization
MapReduce
Moderante-to-high dimensionality data
Terabyte-scale data mining
Abstract in English
Due to the increasing amount and complexity of the data stored in the enterprises' databases, the task of knowledge discovery is nowadays vital to support strategic decisions. However, the mining techniques used in the process usually have high computational costs that come from the need to explore several alternative solutions, in different combinations, to obtain the desired knowledge. The most common mining tasks include data classification, labeling and clustering, outlier detection and missing data prediction. Traditionally, the data are represented by numerical or categorical attributes in a table that describes one element in each tuple. Although the same tasks applied to traditional data are also necessary for more complex data, such as images, graphs, audio and long texts, the complexity and the computational costs associated to handling large amounts of these complex data increase considerably, making most of the existing techniques impractical. Therefore, especial data mining techniques for this kind of data need to be developed. This Ph.D. work focuses on the development of new data mining techniques for large sets of complex data, especially for the task of clustering, tightly associated to other data mining tasks that are performed together. Specifically, this Doctoral dissertation presents three novel, fast and scalable data mining algorithms well-suited to analyze large sets of complex data: the method Halite for correlation clustering; the method BoW for clustering Terabyte-scale datasets; and the method QMAS for labeling and summarization. Our algorithms were evaluated on real, very large datasets with up to billions of complex elements, and they always presented highly accurate results, being at least one order of magnitude faster than the fastest related works in almost all cases. The real data used come from the following applications: automatic breast cancer diagnosis, satellite imagery analysis, and graph mining on a large web graph crawled by Yahoo! and also on the graph with all users and their connections from the Twitter social network. Such results indicate that our algorithms allow the development of real time applications that, potentially, could not be developed without this Ph.D. work, like a software to aid on the fly the diagnosis process in a worldwide Healthcare Information System, or a system to look for deforestation within the Amazon Rainforest in real time
Title in Portuguese
Mineração de dados em grande conjuntos de dados complexos
Keywords in Portuguese
Agrupamento de correlação
Dados de média à alta dimensionalidade
MapReduce
Mineração de dados em escala de terabytes
Rotulação e sumarização
Abstract in Portuguese
O crescimento em quantidade e complexidade dos dados armazenados nas organizações torna a extração de conhecimento utilizando técnicas de mineração uma tarefa ao mesmo tempo fundamental para aproveitar bem esses dados na tomada de decisões estratégicas e de alto custo computacional. O custo vem da necessidade de se explorar uma grande quantidade de casos de estudo, em diferentes combinações, para se obter o conhecimento desejado. Tradicionalmente, os dados a explorar são representados como atributos numéricos ou categóricos em uma tabela, que descreve em cada tupla um caso de teste do conjunto sob análise. Embora as mesmas tarefas desenvolvidas para dados tradicionais sejam também necessárias para dados mais complexos, como imagens, grafos, áudio e textos longos, a complexidade das análises e o custo computacional envolvidos aumentam significativamente, inviabilizando a maioria das técnicas de análise atuais quando aplicadas a grandes quantidades desses dados complexos. Assim, técnicas de mineração especiais devem ser desenvolvidas. Este Trabalho de Doutorado visa a criação de novas técnicas de mineração para grandes bases de dados complexos. Especificamente, foram desenvolvidas duas novas técnicas de agrupamento e uma nova técnica de rotulação e sumarização que são rápidas, escaláveis e bem adequadas à análise de grandes bases de dados complexos. As técnicas propostas foram avaliadas para a análise de bases de dados reais, em escala de Terabytes de dados, contendo até bilhões de objetos complexos, e elas sempre apresentaram resultados de alta qualidade, sendo em quase todos os casos pelo menos uma ordem de magnitude mais rápidas do que os trabalhos relacionados mais eficientes. Os dados reais utilizados vêm das seguintes aplicações: diagnóstico automático de câncer de mama, análise de imagens de satélites, e mineração de grafos aplicada a um grande grafo da web coletado pelo Yahoo! e também a um grafo com todos os usuários da rede social Twitter e suas conexões. Tais resultados indicam que nossos algoritmos permitem a criação de aplicações em tempo real que, potencialmente, não poderiam ser desenvolvidas sem a existência deste Trabalho de Doutorado, como por exemplo, um sistema em escala global para o auxílio ao diagnóstico médico em tempo real, ou um sistema para a busca por áreas de desmatamento na Floresta Amazônica em tempo real
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Tese_Cordeiro.pdf (28.37 Mbytes)
thesis_revised.pdf (28.55 Mbytes)
Publishing Date
2011-11-22
 
WARNING: The material described below relates to works resulting from this thesis or dissertation. The contents of these works are the author's responsibility.
  • Cordeiro, R.L.F., et al. Halite: Fast and Scalable Multi-Resolution Local-Correlation Clustering [doi:10.1109/TKDE.2011.176]. IEEE Transactions on Knowledge and Data Engineering [online], 2013, vol. 25, p. 387-401.
  • NUNES, S. A., et al. Analysis of Large Scale Climate Data: How Well Climate Change Models and Data from Real Sensor Networks Agree?. In Large Scale Network Analysis (LSNA) Workshop of the WWW 2013 Conference, Rio de janeiro, 2013. WWW 2013 Companion Publication.New York : ACM, 2013. Dispon?vel em: http://www2013.org/companion/p517.pdf.
  • Pola, I. R. V., et al. Similarity Sets: A Conceptual Basis to Seamlessly Include Similarity Queries in Data Base Management Systems. In 6th International Conference on Similarity Search and Applications (SISAP 2013), A Coruña, 2013. Proceedings of the SISAP 2013 - LNCC.Berlin : Springer, 2013.
  • Cordeiro, R.L.F., Faloutsos, C., and TRAINA JR, C. Data Mining in Large Datasets of Complex Data. New York : Springer Verlav, 2013{Volume}.{Serie}
  • Melhor Tese do CSBC-CTD 2012 - XXV Concurso de Teses e Dissertações do XXXII Congresso da Sociedade Brasileira de Computação - Sociedade Brasileira de Computação
All rights of the thesis/dissertation are from the authors
Centro de Informática de São Carlos
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2020. All rights reserved.