Mineração de Dados
Algoritmo APRIORI
Felipe Carvalho – UFES 2009/2
Uma base de dados transacional
• Para melhor compreensão do funcionamento do algoritmo APRIORI,
considere D a base de dados transacionais apresentada abaixo:
Algoritmo APRIORI
• O primeiro passo é gerar a lista de candidatos de
conjuntos de itens de tamanho 1, denotada por
C1, e levantar a freqüência de cada um em D:
• Considerando um limite mínimo de freqüência
igual a 2, obtemos a lista de conjuntos de itens
freqüentes de tamanho 1, denotada por L1:
Algoritmo APRIORI
• O próximo passo é obter todos os conjuntos candidatos de tamanho 2, C2, a
partir de combinações de elementos de L1, e suas respectivas freqüências
em D:
Algoritmo APRIORI
• Filtrando novamente pelo limite mínimo de
freqüência (definido como 2), obtemos a lista de
conjuntos de itens freqüentes de tamanho 2,
denotada por L2:
• Procedendo da mesma forma, podemos combinar
os elementos de L2 para obtermos todos os
conjuntos candidatos possíveis de tamanho 3, C3:
Algoritmo APRIORI
• Para mostrarmos como a propriedade Apriori pode ajudar a reduzir o
esforço computacional do algoritmo, vamos usar os elementos C3. Segundo
esta propriedade, todo subconjunto não vazio de um conjunto de itens
freqüentes também dever ser freqüente;
• então, se decompormos todos os elementos de C3 em conjuntos de
tamanho 2, podemos verificar quais deles pertencem a L2, i.e., são
freqüentes. Claramente, se um dos elementos de C3 possuir um
subconjunto que não consta em L2, esse elemento não pode ser freqüente.
Aplicação dessa propriedade em C3 é apresentada no próximo slide.
Algoritmo APRIORI
• Como podemos ver, de
acordo com a propriedade
Apriori, os últimos quatro
elementos de C3 não
podem ser freqüentes, pois
possuem subconjuntos que
não pertencem a L2. Temos
agora que verificar quais
dos conjuntos candidatos
que restaram são
realmente freqüentes.
• Como para cada um deles é necessário verificar todas as transações em D
para descobrir sua freqüência, o uso da propriedade Apriori nos poupou de
quatro verificações, usando apenas conhecimento prévio.
Algoritmo APRIORI
• Apenas para termos certeza de que a propriedade
Apriori realmente não elimina conjuntos
freqüentes, podemos levantar a freqüência de
cada um dos elementos de C3:
• Obtemos assim os conjuntos freqüentes de
tamanho 3, L3:
Algoritmo APRIORI
• A combinação dos elementos de L3 resultaria apenas
no conjunto {i1, i2, i3, i5}, que possui subconjuntos
não freqüentes (e.g., {i1, i3, i5} e {i2, i3, i5}). Isto
significa que não existem conjuntos maiores
freqüentes. Chegamos, então, ao final da execução
do algoritmo, e descobrimos todos os conjuntos
freqüentes possíveis:
• Para gerar regras de associação a partir do resultado
do algoritmo APRIORI, basta analisar a implicação
entre os elementos dessa lista, conforme discutimos
na Seção 3.2. (Quadro Cognitivo:
http://mineracaodedados.pbworks.com). Usando
medidas de interesse como cobertura e precisão,
conseguimos separar as regras fortes.
Algoritmo – Formalmente Definido
•
•
•
•
•
•
APRIORI(D, freq_min) {
L1 = {todos os itens freqüentes em D de tamanho 1};
Para (k = 2 ; Lk-1 <> vazio; k++) {
– Ck = {candidatos gerados pela combinação dos elementos de Lk-1};
– Para cada elemento E de Ck {
• Para cada subconjunto S de E {
– Se S <> Lk-1 então Ck = Ck – E;
• };
– };
– Para cada transação T de D {
• Para cada elemento E de Ck {
– Se E está contido em T então freq(E) = freq(E) + 1;
• };
– };
– Para cada elemento E de Ck {
• Se freq(E) > freq_min então Lk = Lk + E;
– };
};
retornar UkLk;
};