Descoberta de conjuntos de itens frequentes com o modelo de programação MapReduce sobre contextos de incerteza

• Ano de defesa: 2015
• Autor(a) principal: Carvalho, Juliano Varella de
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Pontifícia Universidade Católica do Rio Grande do Sul; Faculdade de Informática; Brasil; PUCRS; Programa de Pós-Graduação em Ciência da Computação
• Palavras-chave em Português: INFORMÁTICA; MINERAÇÃO DE DADOS (INFORMÁTICA); CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://tede2.pucrs.br/tede2/handle/tede/6254

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.