Export this record: EndNote BibTex

Please use this identifier to cite or link to this item: http://tede2.pucrs.br/tede2/handle/tede/6254
Document type: Tese
Title: Descoberta de conjuntos de itens frequentes com o modelo de programação MapReduce sobre contextos de incerteza
Author: Carvalho, Juliano Varella de 
Advisor: Ruiz, Duncan Dubugras Alcoba
Abstract (native): Frequent Itemsets Mining (FIM) é uma tarefa de mineração de dados utilizada para encontrar relações entre os itens de um dataset. O Apriori é um tradicional algoritmo da classe Generateand- Test para descobrir tais relações. Estudos recentes mostram que este e outros algoritmos desta tarefa não estão aptos para executar em contextos onde haja incerteza associada, pois eles não estão preparados para lidar com as probabilidades existentes nos itens do dataset. A incerteza nos dados ocorre em diversas aplicações como, por exemplo, dados coletados de sensores, informações sobre a presença de objetos em imagens de satélite e dados provenientes da aplicação de métodos estatísticos. Dada a grande quantidade de dados com incertezas associadas, novos algoritmos têm sido desenvolvidos para trabalharem neste contexto: UApriori, UF-Growth e UH-Mine. O UApriori, em especial, é um algoritmo baseado em suporte esperado, abordado frequentemente pela comunidade acadêmica. Quando este algoritmo é aplicado sobre grandes datasets, em um contexto com probabilidades associadas aos itens do dataset, ele não apresenta boa escalabilidade. Por outro lado, alguns trabalhos têm adaptado o algoritmo Apriori para trabalhar com o modelo de programação MapReduce, a fim de prover uma melhor escalabilidade. Utilizando este modelo, é possível descobrir itens frequentes de modo paralelo e distribuído. No entanto, tais trabalhos focam seus esforços na descoberta de itens frequentes sobre datasets determinísticos. Esta tese apresenta o desenvolvimento, implementação e os experimentos realizados, a partir da aplicação e discussão de três algoritmos: UAprioriMR, UAprioriMRByT e UAprioriMRJoin. Os três algoritmos citados evoluem o algoritmo tradicional Apriori para que possam executar com o modelo de programação MapReduce sobre contextos com incerteza associada. O algoritmo UAprioriMRJoin é um algoritmo híbrido com base nos algoritmos UAprioriMR e UAprioriMRByT. Os experimentos revelam o bom desempenho do algoritmo UAprioriMRJoin quando aplicado sobre grandes datasets, com muitos atributos e um número médio pequeno de itens por transação, em um cluster de nodos.
Abstract (english): Frequent Itemsets Mining (FIM) is a data mining task used to find relations between dataset items. Apriori is the traditional algorithm of the Generate-and-Test class to discover these relations. Recent studies show that this algorithm and others of this task are not adapted to execute in contexts with uncertainty because these algorithms are not prepared to handle with the probabilities associated to items of the dataset. Nowadays, data with uncertainty occur in many applications, for example, data collected from sensors, information about the presence of objects in satellite images and data from application of statistical methods. Due to big datasets with associated uncertainty, new algorithms have been developed to work in this context: UApriori, UF-Growth and UH-Mine. UApriori, specially, is an algorithm based in expected support, often addressed by scientific community. On the one hand, when this algorithm is applied to big datasets, in a context with associated probabilities to dataset items, it does not present good scalability. On the other hand, some works have evolved the Apriori algorithm joining with the model of programming MapReduce, in order to get a better scalability. With this model, it is possible to discover frequent itemsets using parallel and distributed computation. However, these works focus their efforts on discovering frequent itemsets on deterministic datasets. This thesis present the development, implementation and experiments applied to three algorithms: UAprioriMR, UAprioriMRByT and UAprioriMRJoin. The three cited algorithms evolve the traditional algorithm Apriori, integrating the model of programming MapReduce, on contexts with uncertainty. The algorithm UAprioriMRJoin is a hybrid algorithm based on the UAprioriMR and UAprioriMRByT algorithms. The experiments expose the good performance of the UAprioriMRJoin algorithm, when applied on big datasets, with many distinct items and a small average number of items per transaction in a cluster of nodes.
Keywords: INFORMÁTICA
MINERAÇÃO DE DADOS (INFORMÁTICA)
CNPQ Knowledge Areas: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language: por
Country: Brasil
Publisher: Pontifícia Universidade Católica do Rio Grande do Sul
Institution Acronym: PUCRS
Department: Faculdade de Informática
Program: Programa de Pós-Graduação em Ciência da Computação
Access type: Acesso Aberto
URI: http://tede2.pucrs.br/tede2/handle/tede/6254
Issue Date: 20-Mar-2015
Appears in Collections:Programa de Pós-Graduação em Ciência da Computação

Files in This Item:
File Description SizeFormat 
473651 - Texto Completo.pdfTexto Completo14.77 MBAdobe PDFThumbnail

Download/Open Preview


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.