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]
Conteúdo apagado Conteúdo adicionado
Linha 32:
 
== 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 <math>S</math>, composto por 10 exemplos, e a instância de teste <math>T</math>, a ser classificada.
 
[[Ficheiro:Training_projection_1_lac.png|commoldura|Conjunto de exemplos e instância de teste.]]
 
Após a projeção de <math>T</math> sobre <math>S</math> 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.
 
[[Ficheiro:Training_projection_2_lac.png|commoldura|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 ==