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

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 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.

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) <math>f: X → Y<math> inicialmente desconhecida (Mitchel 2006). Isto é feito a partir de um conjunto de dados de exemplo <math>{x_{i},y_{i}}<math>, em que <math>x_{i}<math} representa os atributos de um dado e <math>y_{i}<math> a variável resposta referente a classe a que pertence. Tais dados são utilizados para “mostrar” ao algoritmo o mapeamento das entradas <math>x_{i}<math> para as saídas desejadas <math>y_{i} = f(x_{i})<math>.

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 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 ti é feita extraindo regras de associação que contém apenas os atributos de ti usando o conjunto de treinamento. As regras extraídas são do tipo <math>X → 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.

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>

[[|miniaturadaimagem|Teste]]