[edição não verificada]

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 22h36min de 15 de fevereiro de 2013

Esta seção apresenta uma discussão sobre o problema de mineração de itemsets frequentes sob a ótica de ambientes big-data.

Descrição da aplicação

O presente trabalho apresenta uma discussão acerca do problema de mineração de itemsets frequentes no contexto de ambientes de dados massivos (big data).

Denominação

Mineração de Itemsets Frequentes (MIFs)

Contexto

Motivação

Algoritmo

Exemplo de funcionamento

Exemplo de funcionamento do algoritmo SON. Processa uma partição por vez. Objetivo caber na RAM.

Requisitos

Nessa seção, apresentam-se os requisitos de escalabilidade, armazenamento, latência e tolerância a falhas considerados no projeto.

Escalabilidade

Armazenamento

Latência

Consideramos nesse projeto que a identificação de itemsets frequentes seja um processo offline e portanto não assumimos nenhum requisito de latência. Deseja-se porém obter speed-up próximo ao linear.

Tolerância a falhas

Dado o grande volume de dados e o tempo necessário para processamento, é comum que aplicações de big-data possuam tolerancia a falhas. Embora na presente aplicação tal quesito também seja importante, não entraremos no mérito de propor estratégias de tolerancia a falhas nesse trabalho. Diversos frameworks implementam tolerancia a falhas, evitando que o programador tenha tais preocupaçoes. Portanto, deixaremos isso por conta do framework a ser utilizado. Além disso, a existencia ou não de tolerancia a falhas não está intrinsecamente relacionada ao algoritmo. Assim, para o contexto em questão assumimos que isso não é crítico.

Projeto

Oportunidade de paralelização

Conforme já mencionado em seções anteriores, é comum que aplicações de mineração de dados dependam da extração de itemsets frequentes em grandes volumes de dados. Muitas vezes esses volumes não podem ser armazenado em uma única máquina. Nesse sentido, uma abordagem natural é particionar a base de dados de forma que cada nó seja responsável por armazenar e processar um subconjunto da totalidade.

A oportunidade de paralelização explorada nesse trabalho é o particionamento da base de dados por transações. Dessa forma, cada nó é responsável por um subconjunto das transações. Vale observar que o particionamento por trasações é mais indicado em casos onde a quantidade de transações é muito maior que a quantidade de itens presentes em cada transação. Caso contrário, o particionamento por itens poderia ser mais mais indicado.

A estratégia adotada nesse trabalho é semelhante à oportunidade de paralelização explorada pelo algoritmo Parallel SON (PSON), um algoritmo paralelo para extração itemsets frequentes. Grosso modo, o PSON é uma versão paralela do algoritmo SON. Assim como no algoritmo SON, no PSON a dependência de dados proveniente do princípio Apriori também não é problema. Na infraestrutura de computação, a qual pode ser descrita como um grafo onde cada nó é uma máquina, a dependência maior é intra nó.

O algoritmo SON, e por consequência o PSON, se beneficia do seguinte princípio:

Um itemset frequente global, certamente é frequente local em pelo menos uma das partições.

A primeira fase do algoritmo PSON consiste divisão da base de dados por transações. Em seguida, extrai-se o conjunto de itemsets frequentes maximais (IFMs) em cada partição. Note que esse passo que pode ser feito paralelamente. A próxima etapa é a união dos conjuntos de IFMs gerados, tal união consiste então no conjunto de candidatos ao título de itemsets frequentes globais. O último passo é a contagem de cada elemento do conjunto potência de cada candidato em todas as partições e posterior soma do número de ocorrências e filtragem dos itemsets frequentes globais.

Padrões de acesso aos dados

Na abordagem aqui apresentada, os dados são particionados por transações. Cada nó de processamento atua em um subconjunto das transações existentes na base original. Especificamente, cada partição é gravada em um arquivo distinto.

Considerando que a base já esteja particionada, cada partição é acessada em dois momentos durante o processamento. Em cada acesso, as transações correspondentes à cada partição são lidas para a memória principal e é feito o processamento. Portanto, para que o processamento ocorra de forma eficiente o particionamento da base de dados deve considerar um parâmetro importante, o tamanho da memória principal. Assim, nenhuma partição deve ser maior que a memória principal, caso contrário o overhead de causado pelo gerenciamento da memória virtual (e consequentemente uso da memória secundária) poderia reduzir drasticamente a eficiência do processamento.

O primeiro acesso refere-se à geração dos itemsets frequentes em cada partição. O segundo, ocorre após a união dos itemsets frequentes maximais gerados na primeira etapa. Nesse momento, cada partição é novamente lida novamente do disco. A figura à direita dessa página apresenta um diagrama temporal que representa visualmente o padrão de acesso aos dados adotado nesse trabalho. Nessa figura, cubos representam processos e cada cilindro representa uma partições dos dados.

Vale observar que, conceitualmente, apenas uma leitura é necessária, visto que as mesmas partições são lidas duas vezes. Porém, do ponto de vista de projeto há beneficios em separar as leituras. Tais benefícios ficaram claros ao longo do texto. Grosso modo, a base apenas precisa estar na memória principal durante a montagem da estrutura de dados requisitada pelo algoritmo de extração de itemsets frequentes a ser usado em cada partição e durante a contagem dos itens na última fase; portanto, remover esses dados da memória principal libera espaço para a própria extração de itemsets frequentes locais e outros processamentos. Além disso, não há perdas significatívas de desempenho.

Outro ponto importante é, dependendo de como a presente estratégia é implementada, haverá mais ou menos acessos a disco. Caso a implementação seja feita em Hadoop, por exemplo, haveria mais acessos visto que grande parte da comunicação ocorre por meio de arquivos.

Padrões de comunicação

Para tornar mais clara a explicação do método faz-se necessária uma distinção clara entre o nó central e os nós de processamento de transações. O nó central é responsável por gerenciar a computação dos nós que processam transações (ou doravante, nós de processamento). A figura à direita dessa página apresenta um diagrama que representa os padrões de comunicação da abodagem proposta.

No contexto de trocas de mensagens, o processamento pode ser descrito como segue. O nó central envia uma mensagem para cada nó de processamento, o objetivo é enviar os parâmetros necessários e iniciar a identificação dos itemsets frequentes em cada partição. Tão logo cada nó de processamento termine esse passo, uma mensagem contendo o conjunto de itemsets frequentes maximais é enviada ao nó central, que faz a união dos conjuntos recebidos e envia uma nova mensagem a cada nó de processamento contendo os itemsets frequentes maximais gerados. Nesse momento, os nós de processamento fazem o desmembramento de cada conjunto maximal, por meio da geração do conjunto potência, e efetua a contagem de cada elemento em sua respectiva partição. Ao fim dessa contagem, cada nó de processamento envia uma mensagem ao nó central, que por sua vez efetua a totalização e faz a filtragem deixando como resultado apenas os itemsets frequentes maximais globais.

Em suma, o processamento envolve quatro momentos de troca de mensagem:

Nó central envia mensagem aos nós de processamento para iniciar a computação dos IFMs locais
Nós de processamento enviam mensagem ao nó central contendo os IFMs locais
Nó central envia mensagem aos nós de processamento contendo a união dos IFMs locais
Nós de processamento enviam ao nó central mensagens contendo as contagens parciais

Note que o nó central sempre envia mensagens idênticas aos nós de processamento (salvo o nome dos arquivos na mensagem de inicialização), que por sua vez enviam sempre mesagens (potencialmente) distintas ao nó central.

Linha do tempo integrada

A figura abaixo apresenta uma linha do tempo integrada que exemplifica o comportamento do método em termos de acesso aos dados, processamento executado e trocas de mensagens.

Implementação

Nesta seção, são discutidos os principais aspectos de implementação do algoritmo.

Estratégia de paralelização

Algumas ferramentas e abstrações podem auxiliar o projeto e desenvolvimento de aplicações no contexto de processamento massivo e big-data. Encontrar aquela que mais naturalmente se adequa ao problema em questão é uma etapa importante do projeto. Dentre as ferramentas e abstrações disponíveis, destacam-se:

Ferramentas para processamento de streams;
Processamento descrito em forma de fluxo em grafos;
Ferramentas para processamento de grafos grandes;
Abstração MapReduce.

A oportunidade de paralelização aqui descrita pode ser implementada por meio de duas chamadas MapReduce, conforme descrito a seguir.

Etapa	Objetivo
1^o mapeamento	Extração dos itemsets frequentes maximais (IFMs) locais de cada partição
1^a redução	União dos IFMs
2^o mapeamento	Contagens locais baseadas na união dos IFMs
2^a redução	Totalização e filtragem pelo suporte

Estratégia de armazenamento

Cada partição da base de dados é armazenada em um arquivo transações. Trata-se de um arquivo de caracteres (textual), porém nada impede o uso de arquivos binários de bloco ou mesmo gerenciadores de banco de dados.

Estratégia de comunicação

Na implementação baseada no framework MaPI, a comunicação é feita por trocas de mensagens.

Execução

Plataforma e ferramentas

MapReduce++

MapReduce++ é um projeto open-source que contem diferentes implementações em C++ do modelo de programação MapReduce. Esse projeto possui uma interface padrão para desenvolvimento de bibliotecas MapReduce, que é a base de suas implementações MapReduce.

Atualmente, MapReduce++ contém duas implementações de MapReduce:

MapMP - uma biblioteca MapReduce para multi-processadores (memória compartilhada) MaPI - um framework MapReduce para multi-computadores (memória distribuída)

Download

Baixe a versão mais atual no SourceForge http://sourceforge.net/projects/mapreducepp/

Instalação no Ubuntu Linux

Para desenvolver e executar programas MapReduce++, é necessário possuir compilador g++ e suport para desenvolvimento e execução de programas baseados em MPI.

Instale o g++ com o seguinte comando no terminal: $sudo apt-get install g++

Para suporte a MPI, pode-se usar a implementação OpenMPI (recomendada): $sudo apt-get install openmpi-bin libopenmpi-dev

ou MPICH2, se preferir: $sudo apt-get install mpich2

Configuração do cluster

Necessária a instalação do ssh client e server. $sudo apt-get install openssh-server openssh-client

Como iniciar e parar um servidor ssh: $sudo /etc/init.d/ssh start $sudo /etc/init.d/ssh stop

Detalhes de implementação

Avaliação

Carga de trabalho

Avaliação experimental

Dimensões de avaliação

Planejamento experimental

Análise dos resultados

Escalabilidade

Tendências

Identificação de gargalos

Análise de projeto e implementação

@@ Linha 2: / Linha 2: @@
 = Descrição da aplicação =
+O presente trabalho apresenta uma discussão acerca do problema de mineração de ''itemsets'' frequentes no contexto de ambientes de dados massivos (''big data'').
 === Denominação ===