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 11: Linha 11:
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.
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 é 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 - Cache Optimization é 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.
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 ==

Revisão das 03h30min 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

Distributed LAC - Otimização de Cache

Implementação em Hadoop

Decisões de Implementação

Avaliação Experimental

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.