Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Classificação associativa incremental (LAC): diferenças entre revisões

Origem: Wikilivros, livros abertos por um mundo aberto.
[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
Linha 124: Linha 124:
Por padrão o Hadoop divide cada arquivo de entrada em vários chunks que são processador por diferentes mappers, este processo é feito para aumentar o grau de paralelismo.
Por padrão o Hadoop divide cada arquivo de entrada em vários chunks que são processador por diferentes mappers, este processo é feito para aumentar o grau de paralelismo.


[[Ficheiro:Hadoop-chunking1.png|commoldura|centro|Divisão de um arquivo de Entrada em Chunks]
[[Ficheiro:Hadoop-chunking1.png|commoldura|centro|Divisão de um arquivo de Entrada em Chunks]]

Contudo, este processo não é o adequado para nossa aplicação, visto que queremos processar cada arquivo em um único mapper desta forma a cache do LAC será aproveitada adequadamente. Para garantir que cada arquivo seja processado por apenas um mapper foi extendida a classe de input desejada, no nosso caso '''KeyValueTextInputFormat''', e sobrecarregamos o método '''isSplitable()''' de forma que retornase '''false'''.


Contudo, este processo não é o adequado para nossa aplicação, visto que queremos processar cada arquivo em um único mapper desta forma a cache do LAC será aproveitada adequadamente. Para garantir que cada arquivo seja processado por apenas um mapper foi extendida a classe de input desejada, no nosso caso '''KeyValueTextInputFormat''', e sobrecarregamos o método '''isSplitable()''' de forma que retornase '''false'''.


==== Distribuindo o Classificador ====
==== Distribuindo o Classificador ====

Revisão das 17h54min de 14 de fevereiro de 2013

Introdução

Classificação é uma técnica constantemente aplicada em Knowledge Discovery in Databases (KDD) no processo de mineração de dados. O KDD é um processo de extração de conhecimento de bancos de dados, em geral, bancos de dados históricos. Um dos exemplos mais conhecidos a respeito de KDD é sobre a descoberta de que aos finais de semana a venda de fraldas estava relacionadas a venda de cervejas em uma grande rede de supermercados dos Estados Unidos.

Porém, quando fala-se de Big Data considera-se os dados em curtos espaços de tempo e em grande quantidade, ou seja, não são minerados bancos de dados históricos, em relação a vários meses, e sim bancos de dado semanais, diários. Assim, é necessário que as técnicas de mineração de dados e aprendizado de máquina aplicadas em Big Data sejam escaláveis para trabalhar com grandes volumes de dados e em tempo próximo de real.

Sendo assim, aplicar classificação no contexto de big data necessita de adaptação dos algoritmos quanto a dependência de dados, overhead de comunicação de rede, etc. Realiza essas adaptações classificação torna-se uma importante ferramenta da extração de conhecimento em big data.

Diante este desafio, a adaptação de algoritmos de classificação para big data, este trabalho direciona a adaptação do algoritmo Lazy Associative Classification (LAC) para um ambiente distribuído. O LAC é um algoritmo que cria modelos de classificação sob demanda para cada dado a ser classificado. Esta característica cria uma possibilidade de paralelismo, uma vez que pode-se distribuir os dados a serem classificados para diversos nós de computação para que sejam instanciados diversos classificadores LAC com um mesmo conjunto de exemplos.

Além disso o LAC possui algumas características que permitem a otimização para a realização da classificação de dados que reduzem a quantidade de acessos aos conjunto de exemplos, fornecendo a mesma taxa de acerto.

Portanto, este trabalho tem como objetivo o aproveitamento de tais características para o desenvolvimento de um algoritmo distribuído, chamado Distributed Lazy Associative Classification. O restrante deste trabalho está organizado da seguinte maneira: A Seção #REDIRECIONAMENTO Classificação Automática apresenta a técnica de Classificação Automática; Na Seção Lazy Associative Classification (LAC) o algoritmo LAC é detalhado; Na Seção Extração de Regras de Associação e o LAC é apresentado o problema de extração de regras de associação, sua complexidade e como o LAC lida com isto; Na Seção Distributed LAC - Otimização de Cache é apresentado o algoritmo proposto neste trabalho o Distributed LAC, em que são detalhadas as características que permitem a otimizaçaõ do LAC; Na Seção Implementação em Hadoop mostramos o projeto de impementação do Distributed LAC no Hadoop e as decisões de implementação; Na Seção Avaliação Experimental detalhamos a avaliação experimental, configuração de experimentos e resultados obtidos; Por fim, na Seção Conclusão apresentamos nossas conclusões, trabalhos futuros e considerações finais.

Classificação Automática

Classificação automática é uma técnica desenvolvida em aprendizado de máquina e mineração de dados. Em se tratando da área de aprendizado de máquina, classificação automática se encaixa em aprendizado supervisionado que trata-se de um processo que induz uma função (modelo) inicialmente desconhecida (Mitchel 2006). Isto é feito a partir de um conjunto de dados de exemplo , em que xirepresenta os atributos de um dado e a variável resposta referente a classe a que pertence. Tais dados são utilizados para "mostrar" ao algoritmo o mapeamento das entradas para as saídas desejadas .

Para realizar a indução desta função os algoritmos de classificação utilizam técnicas inspiradas em estatística até em computação natural (algoritmos genéticos, colônias de formigas, etc). Vários destes algrotimos possuem duas fazes: treino e classificação. A fase de treino é responsável pela indução da função que irá classificar dados ainda desconhecidos. A fase de teste é a aplicação de tal função a cada dado do conjunto de teste os quais são classificados.

Outros algoritmos não possuem a fase de treino separada da fase de classficificação. Este algoritmos são conhecidos como Lazy ou Sob Demanda. O processo de classificação realizado por estes algoritmos é tal que para cada dado do conjunto de teste é construída um modelo de classificação, ou seja, o modelo de classificação é construído sob demanda para cada dado do teste.

Lazy Associative Classification (LAC)

Lazy Associative Classification (LAC) é um algoritmo de classificação associativo proposto por Veloso et al. (2006). LAC é um algoritmo não paramétrico baseado em exemplos (conjunto de treinamento), ou seja, o processo de aprendizado se dá pela indução de um modelo de classificação durante a etapa de treino.

De acordo com Veloso et al. (2006) LAC não usa nenhuma estratégia para minimização de erros ou suposições inválidas sobre a distribução dos dados. Assim, as regras estraídas são aplicadas para descrever os dados e estimar as probabilidades de uma determinada instância de teste pertencer a cada classe. O LAC gera, para cada instância de teste, um modelo sob demanda durante o processo de treinamento.

A Geração de modelo sob demanda para cada teste é feita extraindo regras de associação que contém apenas os atributos de usando o conjunto de treinamento. As regras extraídas são do tipo , em que é um subconjunto dos atributos de e é o rótulo da i-ésima classe. Este tipo de regra é conhecida como Regra de Associação de Classe (Class Assocication Rule) (CAR) devido ao fato de que os atributos estão sempre à esquerda e a classe à direita na regra. Extraídas as regras, a classe de cada tié computada através dos votos dados pelas regas. O LAC utiliza limiares mínimos de suporte e confiânça para evitar a extração de regras de associação inúteis.

No Algoritmo 1 apresentamos o pseudo-código do LAC que recebe como entrada o conjunto de treinamento e teste, limiares mínimos de suporte e confiância e um limite máximo para o tamanho das regras extraídas. Para cada instância tipertencer a cada classe. Na linha 7 atribui-se o rótulo da classe que obteve maior probabilidade à tido conjunto de teste é extraído um conjunto de regras de associação que respeite os limiares de suporte, confiânça e tamanho da regra (linha 2). Seguindo, entre as linhas 3 à 6 são computadas as probabilidades da instância pertencer a cada classe. Na linha 7 atribui-se o rótulo da classe que obteve maior probabilidade à .

Pseudo-código do Lazy Associative Classification

Extração de Regras de Associação e o LAC

A extração de regras de associação é uma tarefa de mineração de dados, também conhecida como Mineração de Item Sets Frequentes. Seu objetivo é encontrar conjuntos de itens que possuem correlação em um banco de dados de transações.

O conceito de regas fortes de Agrawal et al. (1993) deu origem a este tópico de pesquisa. O primeiro algoritmo para Mineração de Itens Sets Frequentes foi o Apriori proposto por Agrawal e Srikant (1994).

A extração de regras de associação tem um alto custo computacional, sendo que o algoritmo força bruta possui complexidade exponencial. Outros algoritmos foram propostos para este fim, que fazem uso de heurísticas de podas e limitações de tamanhos de regras, alguns exemplos são o Eclat e FP-growth.

O LAC pode utilizar no processo de indução de regras qualquer algoritmo de mineração de itens sets frequentes. Contudo para reduzir a dimensionalidade dos dados o LAC aplica antes do processo de extração de regras a projeção de dados.

O LAC realiza a projeção de dados do dado de teste sobre o conjunto de exemplos. Em suma, a projeção consiste em um conjunto de exemplos que é obtido depois de remover todos atributos não inclusos na instância de teste. Um exemplo é apresentado nas Tabelas 1 e 2. Na Tabela 1 é apresentado o conjunto de exemplos , composto por 10 exemplos, e a instância de teste , a ser classificada.

Conjunto de exemplos e instância de teste.

Após a projeção de sobre o conjunto de exemplos ao qual será utilizada para a extração de regras de associação é apresentado na Tabela 2. Percebe-se que de 10 exemplos, restaram apenas 5, reduzindo consideravelmente a quantidade de exemplos a serem inspecionados.

Conjunto de exemplos projetado em relação a instância de teste.

Após a projeção de dados o algoritmo de mineração de itens sets frequentes é executado. Porém várias regras são frequentemente extraídas e não é eficiente extraí-las toda vez que um dado de teste é analizado. Assim, o LAC também incorpora um cache de regras frequentes, em que quando uma regra frequente é extraída, esta é inserida neste repositório, reduzindo a quantidade de acesso ao conjunto de exemplos.

O cache do LAC é um importante recurso a ser utilizado em um contexto de big data, em que é possível armazenar modelos de classificação (conjunto de regras) e evitar o re-trabalho de extraí-los a cada instância

Distributed LAC - Otimização de Cache

O Distributed LAC direciona-se a duas frentes: possibilitar a classificação de dados de forma distribuída, tornando o processamento de grandes bases de dados plausível; e otimizar o uso do cache de regras implementado no LAC no trabalho de Veloso et al. (2006).

Para otimizar o uso da cache parte-se do princípio de que para instâncias semelhantes, ou seja, aquelas que possuem vários atributos com o mesmo valor, são geradas várias regras em comum. Sendo assim, se for possível gerar grupos baseados em similaridade, ao processar esses grupos o princípio anterior é satisfeito.

Agrupar dados em grupos é uma outra técnica de aprendizado de maquina e mineração de dados, também chamada de clustering. Outra forma de se gerar grupos similares pode ser escolhendo-se uma instância aleatóriamente e ordenar o restante por similaridade a esta escolhida. Assim separa-se o conjunto de dados em quantos grupos forem desejados.

Portanto o Distributed LAC necessita antes de classificar os dados agrupá-los. Um esquema, simplificado, pode ser visto na Figura 1, em que os itens de cores parecidas são agrupados e processados pela mesma CPU. Este é o primeiro passo do algoritmo.


Primeira fase do Distributed LAC.

Quando a CPU é acionada para realizar a classificação ocorre processo de treinamento, que no caso do LAC trata-se de carregar o conjunto de exemplos e criar índices para facilitar a extração de regras. A Figura 2 mostra um esquema de como isso é feito.

Segunda fase do Distributed LAC.

O processo mostrado na Figura 2 se repete para cada grupo e o processamento do Distributed LAC é finalizado.

Implementação em Hadoop

Map

Cada mapper recebe como entrada um arquivo de texto que contem as instancias de teste a serem processadas. O formato do arquivo de entrada é:

<key>\t<instance>
<key>\t<instance>
.
.
.
<key>\t<instance>

Sendo que dentro de um mesmo arquivo todas as instancias possuem a mesma chave, para cada linha a função de map realiza o processo de classificação e extrai os dados pertinentes, no nosso caso o número de hits e misses da cache, e os escreve na saída da função onde serão processados pelas funções de reduce. A seguir apresentamos a função de Map:


public void map(Text key, Text value, Context context) throws IOException, InterruptedException {
    String line = value.toString();
    try {
        Result result = this.classifier.distributionForInstance(line.split(" "));
        context.write(missesText, new IntWritable(result.getMisses()));
        context.write(hitsText, new IntWritable(result.getHits()));
    } catch (Exception e) {
        e.printStackTrace();
    }
}

Reduce

O processo de reduce neste caso consiste apenas em somar os números de hits e misses e retornar a soma de cada um, a seguir apresentamos o implementação utilizada:

 
public void reduce(Text key, Iterable<IntWritable> results, Context context) 
    throws IOException, InterruptedException {
    int value = 0;

    for (IntWritable result : results) {
        value +=  result.get();
    }
    context.write(key, new IntWritable(value));
}

Decisões de Implementação

Evitando a divisão dos arquivos de entrada

Por padrão o Hadoop divide cada arquivo de entrada em vários chunks que são processador por diferentes mappers, este processo é feito para aumentar o grau de paralelismo.

Ficheiro:Hadoop-chunking1.png
Divisão de um arquivo de Entrada em Chunks

Contudo, este processo não é o adequado para nossa aplicação, visto que queremos processar cada arquivo em um único mapper desta forma a cache do LAC será aproveitada adequadamente. Para garantir que cada arquivo seja processado por apenas um mapper foi extendida a classe de input desejada, no nosso caso KeyValueTextInputFormat, e sobrecarregamos o método isSplitable() de forma que retornase false.

Distribuindo o Classificador

Para que cada mapper possa processar o arquivo com as instâncias de teste é necessário que cada mapper possua um classificador treinado, uma solução seria antes de realizar o processamento em cada mapper obter o classificador previamente serializado por meio do HDFS, porém isto pode acarretar em um overhead considerável. Uma alternativa para este problema é copiar o classificador serilizado para cada maquina e assim o mapper acessa o arquivo localmente. O Hadoop fornece a classe DistributedCache para este tipo de situação, contudo durante nossos experimentos tivemos vários problemas com esta funcionalidade, desta forma replicamos a funcionalidade desta classe por meio de scripts em bash.


Avaliação Experimental

Métodos de Particionamento

Particionamento Aleatório

Particionamento por Clustering

Particionamento por Clustering com cortes

Conclusão

Referências Bibliográficas

Agrawal, R. and Srikant, R (1994). Fast algorithms for mining association rules in large databases. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.

Agrawal, R.; Imieliński, T.; Swami, A. (1993). Mining association rules between sets of items in large databases. Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93. pp. 207

Mitchell, T. M. (2006). The discipline of machine learning. Machine Learning, Carnegie Mellon University, School of Computer Science, Machine Learning Dept., n. July, p. 1–7, 2006.

Veloso, A., Meira Jr., W., and Zaki, M. J. (2006). Lazy associative classification. In Proceedings of the Sixth International Conference on Data Mining, ICDM ’06, pages 645--654, Washington, DC, USA. IEEE Computer Society.