Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Classificação associativa incremental (LAC): diferenças entre revisões
[edição não verificada] | [edição não verificada] |
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. Adaptado 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 18h12min 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)[1]. 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) [2] . 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)[2] 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 à .
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) [3] 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) [4].
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.
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.
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.
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.
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.
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:
- 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;
- 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;
- 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
- ↑ 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,
- ↑ 2,0 2,1 2,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.; 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,
- ↑ 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.,