• 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
 
 
Tese de Doutorado
DOI
https://doi.org/10.11606/T.55.2011.tde-22112011-083653
Documento
Autor
Nome completo
Robson Leonardo Ferreira Cordeiro
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Carlos, 2011
Orientador
Banca examinadora
Traina Junior, Caetano (Presidente)
Faloutsos, Christos
Ferreira, João Eduardo
Heuser, Carlos Alberto
Moro, Mirella Moura
Título em inglês
Data mining in large sets of complex data
Palavras-chave em inglês
Correlation clustering
Labeling and summarization
MapReduce
Moderante-to-high dimensionality data
Terabyte-scale data mining
Resumo em inglês
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
Título em português
Mineração de dados em grande conjuntos de dados complexos
Palavras-chave em português
Agrupamento de correlação
Dados de média à alta dimensionalidade
MapReduce
Mineração de dados em escala de terabytes
Rotulação e sumarização
Resumo em português
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
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Tese_Cordeiro.pdf (28.37 Mbytes)
thesis_revised.pdf (28.55 Mbytes)
Data de Publicação
2011-11-22
 
AVISO: O material descrito abaixo refere-se a trabalhos decorrentes desta tese ou dissertação. O conteúdo desses trabalhos é de inteira responsabilidade do autor da tese ou dissertação.
  • 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
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2024. Todos os direitos reservados.