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 21: Linha 21:


== Lazy Associative Classification (LAC) ==
== Lazy Associative Classification (LAC) ==
Lazy Associative Classification (LAC) é um algoritmo de classificação associativo proposto por Veloso et al. (2006) <ref name="lac">[http://dl.acm.org/citation.cfm?id=1193367 Veloso et al.], </ref> . 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.
Lazy Associative Classification (LAC) é um algoritmo de classificação associativo proposto por Veloso et al. (2006) <ref name="lac">[http://dl.acm.org/citation.cfm?id=1193367 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.], </ref> . 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.
De acordo com Veloso et al. (2006)<ref name="lac">[http://dl.acm.org/citation.cfm?id=1193367 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.], </ref> 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 <math>t_{i}</math> é feita extraindo regras de associação que contém apenas os atributos de <math>t_{i}</math> usando o conjunto de treinamento. As regras extraídas são do tipo <math>X \text{→} c_{j}</math>, em que <math>X</math> é um subconjunto dos atributos de <math>t_{i}</math> e <math>c_{j}</math> é 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.
A Geração de modelo sob demanda para cada teste <math>t_{i}</math> é feita extraindo regras de associação que contém apenas os atributos de <math>t_{i}</math> usando o conjunto de treinamento. As regras extraídas são do tipo <math>X \text{→} c_{j}</math>, em que <math>X</math> é um subconjunto dos atributos de <math>t_{i}</math> e <math>c_{j}</math> é 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.
Linha 29: Linha 29:
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 <math>t_{i}</math> pertencer a cada classe. Na linha 7 atribui-se o rótulo da classe que obteve maior probabilidade à <math>t_{i}</math>.
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 <math>t_{i}</math> pertencer a cada classe. Na linha 7 atribui-se o rótulo da classe que obteve maior probabilidade à <math>t_{i}</math>.


[[Ficheiro:Lac algorithm.png|commoldura|centro|Pseudo-código do Lazy Associative Classification]]
[[Ficheiro:Lac algorithm.png|commoldura|centro|Pseudo-código do Lazy Associative Classification. Adaptador de (Veloso et al. 2006)<ref name="lac">[http://dl.acm.org/citation.cfm?id=1193367 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.], </ref>]]


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

Revisão das 17h58min de 15 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. A principal característica do LAC utilizada é o cache de regras frequêntes que objetiva-se em armazenar as regras de associação mais frequentes evitando analisar o conjunto de exemplos para re-extraí-las. Desta forma o Distributed Lazy Associative Classification tem por objetivo maximizar o uso deste recurso por meio de agrupamento de dados por similaridade. A hipótese deste trabalho é que ao processar conjuntos de dados de teste aos quais cada conjunto possua instâncias com alta similaridade, a utilização do cache aumentará. Sumarizando, o que o Distributed LAC assume é que quanto maior a similaridade do conjunto de teste processado, maior a utilização do cache de regras.

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) [1] . 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)[1] 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. Adaptador de (Veloso et al. 2006)[1]

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

Nesta seção é detalhado o processo de experimentação e avaliação da solução apresentada.

Conjunto de dados

Nos experimentos realizados foi utilizada uma base de dados textuais de Tweets coletados enter Junho e Outubro de 2010 tendo como foco as eleições presidenciais do Brasil. A então candidata Dilma Rousseff lançou um perfil no Twitter durante um anúncio público e usou esta rede social como uma das principais fontes de informção para seus eleitores. A campanha atraiu mais de 500.000 seguidores e Dilma foi a segunda pessoa mais citada no Twitter em 2010. Houve segundo turno nas eleições e Dilma Rousseff foi eleita com 56% dos votos.

Foram coletadas 446.724 mensagens referindo Dilma Rousseff no Twitter durante sua campanha, sendo selecionadas aleatóriamente 66.643 destas mensagens para rotulação manual. As mensagens foram rotuladas de forma a traçar o sentimento de aprovação em relação a candidada neste perído. A aprovação varia consideravelmente devido a várias afirmações polemicas e ataques políticos. O conjunto de dados contém somente mensagens em Português com 62.089 termos distintos e cada mensagem foi rotulada em Positivo ou Negativo, resultado em 46.808 mensagens Positivas e 19.835 Negativas.

Método de Avaliação

O foco deste trabalho é maximizar a utilização do Cache de Regras de Associação utilizado pelo LAC. Sendo assim, os experimentos realizados visam extrair métricas que comprovem ou não a maximização do uso deste recurso. As métricas utilizadas para medir quanto o Cache é utilizado são a quantidade de Misses e Hits. A primeira mede quantas regras novas tiveram que ser extraídas, uma vez que o padrão requerido não foi encontrado. Por outro lado, a segunda métrica mede a quantidade de regras que foram utilizadas do Cache.

Com a finalidade de medir a quantidade de Misses e Hits submetemos o Distributed LAC a três senários diferentes baseados na primeira fase de execução do algoritmo, o Particionamento de Dados:

  1. Particionamento Aleatório: Este método consiste em particionar de forma aleatória o teste em N grupos de tamanho iguais. A principal vantagem deste método é que cada mapper processa uma quantidade de instancias iguais, desta forma distribuindo melhor a carga. Contudo este método não leva em conta a cache e pode acabar gerando um grande número de misses na cache;
  2. Particionamento por Similaridade: Este método consiste na separação do conjunto de testes por meio de algoritmos de clustering. A principal vantagem deste método é que instancias semelhantes gerar regras semelhantes e portanto maximizar o uso da cache. Porém este método pode gerar clusteres desbalanceados o que pode acabar se tornando um gargalo;
  3. Particionamento por Similaridade com Cortes: Este método consiste na separação do conjunto de testes por meio de duas etapas. Na primeira etapa separamos o conjunto de testes utilizando algoritmos de clustering. Na segunda etapa realizamos um processo de corte nos grupos grandes de forma a evitar overhead de rede para transmitir grupos muito grandes.

Através destes métodos de particionamento espera-se comprovar que a quantidade de Misses no Particionamento Aleatório (1) é maior do que nos Particionamentos por Similaridade (2) e (3), pois as instâncias processadas em (1) poderão necessitar de conjuntos de regras discrepantes, obrigando a extração frequente de regras.

O método de experimentação utilizado é o 10-folds-cross-validation que consistem de criar 10 conjuntos diferentes de treino e teste. Para o particionamento (1) o conjunto de teste é separado aleatóriamente na função Map. Os particionamentos (2) e (3) é feito o agrupamento no conjunto de teste e gerado um arquivo para cada grupo. No caso do particionamento (3) os grupos grandes são divididos em grupos menores. Cada um desses grupos é então carregado e processado em Maps diferentes.

Resultados

Conclusão

Referências Bibliográficas

  1. 1,0 1,1 1,2 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.,

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.