Classificação associativa incremental (LAC)

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

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 distribuição dos dados. Assim, as regras extraí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 $t_{i}$ é feita extraindo regras de associação que contém apenas os atributos de $t_{i}$ usando o conjunto de treinamento. As regras extraídas são do tipo $X{\text{→}}c_{j}$ , em que $X$ é um subconjunto dos atributos de $t_{i}$ e $c_{j}$ é 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 confianç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 pertencer 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 $t_{i}$ pertencer a cada classe. Na linha 7 atribui-se o rótulo da classe que obteve maior probabilidade à $t_{i}$ .

Pseudo-código do Lazy Associative Classification. Adaptado de (Veloso et al. 2006)^[2]

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 $S$ , composto por 10 exemplos, e a instância de teste $T$ , a ser classificada.

Conjunto de exemplos e instância de teste. Adaptado de (Veloso et al. 2006)^[2]

Após a projeção de $T$ sobre $S$ 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. Adaptado de (Veloso et al. 2006)^[2]

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 estendida a classe de input desejada, no nosso caso KeyValueTextInputFormat, e sobrecarregamos o método isSplitable() de forma que retornasse 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.

Implementação do LAC

Neste trabalho foi utilizada a implementação do LAC para Weka ^[5] disponível em http://code.google.com/p/machine-learning-dcc-ufmg/^[6] e impemetada por Gessé Dafe.

Neste trabalho foram feitas as seguinte modificações na implementação do LAC:

Inserção de código para contagem de Misses e Hits no Cache de regras;
Criação de um método para treinar o classificador a partir de um Buffer de arquivo e classificar instâncias baseadas em vetores de String.

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 quatro 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;
Particionamento Temporal: A coleção de dados foi obtida através da API de Streams do Twitter. Desta forma os dados naturalmente estão agrupados temporalmente, ou seja, tweets de um mesmo intervalo de tempo possuem um vocabulário próximo. Assim, os dados de teste serão ordenados temporalmente e divididos em conjuntos de tamanhos iguais;

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. Assim como os particionamentos (2) e (3), ao processar o particionamento (4) espera-se conjuntos mais coesos.

Realizamos dois conjuntos de experimentos, em que o primeiro utilizamos o método de experimentação utilizado é o 10-folds-cross-validation, para comparar entre os particionamentos (1), (2), (3). 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.

No segundo conjunto de experimentos comparamos o particionamento (1) e (4) e optamos por criar conjuntos de treino com 60% da base e teste com 40%. Foram criados 5 conjuntos utilizando esta metodologia.

Algoritmos de Agrupamento

Foram avaliados os seguintes algoritmos de agrupamento:

Em testes preliminares o que apresentou melhores resultados, no nosso caso gerou grupos mais balanceados foi o K-means. Portanto este algoritmo foi utilizado em todos os experimentos subsequentes.

Resultados

Primeira Avaliação

Tempo de Execução

Este experimento visa medir o desempenho dos métodos proposto. Como podemos ver o método de agrupamento foi o pior, isto se deve ao fato dos grupos gerados serem desbalanceados, desta forma a distribuição de carga não é igual entre todas as maquinas do cluster. Enquanto isso o método de geração de partições aleatórias obteve um bom desempenho, principalmente quando geramos um arquivo para cada processador do cluster e piorando quando geramos mais arquivos. Finalmente, o método de agrupamento com cortes apresentou os melhores resultados quando geramos um grande número de arquivos, provavelmente porque apesar de menores os arquivos são mais "coesos" e tomam proveito da cache. Vale lembrar que o depois de gerar os grupos este método realiza um corte dividindo os arquivos grandes, desta forma gerando um número maior de arquivos a serem processados.

Estatísticas da Cache

Nesta seção medimos o aproveitamento da cache por cada método, como esperado os métodos que utilizam o K-means apresentam os melhores resultado enquanto que o método de particionamento aleatório tende a piorar seus resultados conforme o número de grupos aumenta.

Tamanhos dos grupos

A seguir apresentamos os dados referentes a distribuição das instancias nos grupos, analisando o tamanho máximo e mínimo dos grupos gerados pelos métodos propostos. No gráfico que mede tamanho máximo dos grupos gerados podemos notar que o método de agrupamento por similaridade não é boa alternativa, pois não distribui os dados de forma adequada. Enquanto isso o método de agrupamento com cortes acaba distribuindo melhor as instâncias o que aliado a boa utilização da cache explica seu bom desempenho nos nossos experimentos.

Segunda Avaliação: Particionamentos (1) e (4)

A avaliação experimental realizada consiste em tomar vantagem da relação temporal da coleção de dados utilizada como forma de obter particionamentos mais coesos. Realizamos dois tipos de experimentos:

LAC Parametrizado: Confiança = 0.01, Suporte = 0.01 e Tamanho Máximo das regras = 3;
LAC Não Parametrizado: Confiança = 0.00, Suporte = 0.00 e Tamanho Máximo das regras = 3.

O objetivo das duas configurações é verificar se as podas por suporte e confiança aumentam a utilização do cache de regras. Na figura a baixo está listado o resultado obtido dos experimentos com as duas configurações e os dois tipos de particionamentos (1) e (4).

Observa-se que ao processar os dados utilizando o particionamento (4) (Particionamento Temporal) a utilização do cache aumenta consideravelmente em relação ao particionamento (1). Outro resultado evidente é que ao utilizar o LAC Parametrizado o uso do cache também aumenta em relação ao LAC Não Parametrizado quando os dados são processados pelo particionamento (4).

Diante destes resultados pode-se concluir que:

Ao definir valores de confiança e suporte aumenta a utilização do cache de regras;
Para dados temporais o particionamento (4) aumenta a utilização do cache independentemente de configurar valores de Confiança e Suporte para o LAC.

Além de avaliar a utilização do cache, neste caso também é necessário avaliar o quão preciso é o LAC utilizando Confiança e Suporte. Veloso et al. 2006^[2] mencionam que não há valores genéricos para Confiança e Suporte, sendo dependente do domínio do dados e da modelagem. Os resutados desta comparação para este trabalho podem ser visualizados na figura a baixo.

Acurácia LAC Parametrizado vs LAC Não Parametrizado

Nota-se que tanto no LAC Parametrizado como no LAC Não Parametrizado a acurácia não é penalizada ao utilizar o Particionamento Temporal, desta forma esta estrategia nos oferece uma melhora de desempenho sem implicar em perda de qualidade dos resultados gerados pelo classificador. Além disso, como comentado acima os valores para Confiança e Suporte variam de aplicação para aplicação e resultam em performances diferentes, neste caso configurar Confiança e Suporte iguais a 0.0 resultou em melhor performance do que a outra configuração.

Conclusão

Em este projeto, apresentamos tres estrategias para tornar o LAC um classificador distribuido utilizando o Hadoop e analisamos diferentes formas de particionar o teste para tentar melhorar otimizar o acesso a cache de regras.

Como nossos experimentos demostram um fator de grande importância é a boa distribuição das instancias em vários grupos. Isto aliado a estrategias de agrupamento, por similaridade ou ordenação temporal, pode levar a um melhor desempenho. Desta forma teremos uma melhor distribuição de carga conjuntamente com um melhor aproveitamento da cache interna do LAC.

Implementação Utilizada

O código utilizado encontra-se disponivel no github.

Referências Bibliográficas

[1] 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,

[lac-2] 2,0 ^2,1 ^2,2 ^2,3 ^2,4 ^2,5 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.,

[3] 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,

[4] 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.,

[5] Mark Hall, Eibe Frank, Geoffrey Holmes, Bernhard Pfahringer, Peter Reutemann, Ian H. Witten (2009); The WEKA Data Mining Software: An Update; SIGKDD Explorations, Volume 11, Issue 1.,

[6] Machine Learning Group UFMG,

[1]

[2]

[3]

[4]

[5]

[6]