LCM: na efficient algorithm for
enumerating frequent closed item sets
T. Uno, T. Asai, H. Arimura
Apresentação: Luiz Henrique Longhi Rossi
Definições






E é o universo de todos os itens;
X é um subconjunto de E.
R é o conjunto de transações sobre E
R(X) = {t  R | X  t} será o
conjunto de transações incluindo X;
α é uma constante, α > 0;
Um conjunto X é chamado de
freqüente se |R(X)| > α;
Definições





Se um conjunto freqüente está contido em
outro, este é dito maximal
Se um conjunto de transações S  R,
tomamos I(S) = ∩TS T.
Se X satisfaz I(R(X)) = X, então é um
conjunto fechado.
F será o conjunto de todos conjuntos
freqüentes
C será o conjunto de todos conjuntos
freqüentes fechados
Característica

Algoritmo híbrido
• Em um momento das iterações opta,
baseado em estimativas, por um ou por
outra técnica para utilizar algoritmos
para dados esparsos ou densos;
Enumerando Conjuntos Fechados
Freqüentes


É construída uma arvore TRIE
É feita uma busca em profundidade,
enumera-se assim todos os
conjuntos fechados freqüentes
Algoritmo LCM

Para todos conjuntos maiores que o
conjunto i (anterior)
• Se o conjunto for freqüente E igual a
intersecção de todas as transações
envolvendo ele se chama
recursivamente o LCM


For each i > i(X)
If X[i] is frequent and X[i] = I(T(X[i])
then
• Call LCM (X[i])

End for
Algorítmo LCM

X[i] são todos os conjuntos que
contém X e contém i, logo X não
necessariamente é um prefixo de
X[i].
Exemplo, sup = 3






A: 1,2,3,8,5
B: 1,2,4,5
C: 1,2,3,8,9
D: 1,2,3,8,10
E: 1,2,4,9
F: 1,2,5,8


1;
1,2 é freqüente?
• Sim



T({1,2}) = {A, B,
C, D, E, F}
I(T({1,2})) = 1,2
É igual?
• Sim, então chama
recursivamente
Exemplo, sup = 3






A: 1,2,3,8,5
B: 1,2,4,5
C: 1,2,3,8,9
D: 1,2,3,8,10
E: 1,2,4,9
F: 1,2,5,8


1,2;
1,2,3 é frequente?
• Sim



T({1,2,3}) = {A, C,
D}
I(T({1,2,3}) = 1,2,3,8
É igual?
• Não, então não chama
recursivamente
Exemplo

Então como que ele identificará que o
conjunto 1,2,3,8 será fechado freqüente?
• Por causa do iterador! A verificação é feita
como se os dados estivessem em uma trie,
logo, ele vai varrer aumentando o índice i, que
compreende todos os subconjuntos (percorre
em profundidade)

Percorre toda a árvore em tempo linear
• Para realizar a operação I(X) não teria que
percorrer as transações envolvendo X?
Vantagens


Outros algoritmos ao gerarem a
árvore adicionam todos os conjuntos
freqüentes, adicionando assim,
muitos que serão “podados”, como o
LCM só adiciona conjuntos fechados
na árvore, poupa processamento;
Afirma também que cada iteração
tem menos processamento.
Vantagens

Além do algoritmo base, apresenta
algumas otimizações
• Ocurrence Deliver:




Reduz o tempo para construir T(X[i])
Normalmente é obtido a partir de T(X)
percorrendo todas transações que não
envolvem i
Ao invés disso, em quanto se obtém T(X)
simultaneamente é feita a lista J[i] = T(X[i])
Além disso não precisam ser feitas
chamadas recursivas se J[i] for vazio
Vantagens

Ocurrence Deliver
• Otimiza em casos que T(X[i]) é bem menor
que T(X);
• Pode levar até 1/10 do tempo em alguns
casos.

Right-First Sweep
• Como cada chamada recursiva vai ter um
tamanho menor ou igual que a chamada
anterior pode-se alocar a memória no tamanho
total de J de uma vez só como variável global.
Vantagens

Diffsets
• No caso do |T(X[i])| ser parecido com
|T(X)| é usada essa técnica
• Está definida em uma artigo completo
nas referências
• Diz-se que reduz em até 1/100 em
algumas base de dados
Vantagens

Computação hibrida
• Usar Ocurrence Deliver em casos em
que |T(X[i])| é bem menor que |T(X)|;
• Usar Diffsets em casos em que |T(X[i])|
é bem próximo a |T(X)|
• Como decidir?

Estatística
Vantagens

A(X) = Σi |T (X ∪ {i})|
• Tamanho total dos filhos de X

B(X) = Σi:X∪{i}∈ F (|T (X)| − |T (X ∪ {i})|)
• Tamanho de X menos o tamanho dos filhos


Para uma constante c usa-se o Ocurrence
deliver se A(X) < c.B(X)
A decisão é feita apenas para os filhos
imediatos da raiz desde que não tome
muito tempo
Vantagens
• A computação hibrida, reduz o tempo em até
1/3

Verificação de “fechabilidade” (no
ocurrence deliver)
• Por definição um conjunto candidato não vai
ser fechado sse existir um valor que ocorre em
todas transações que outro valor
• Então, é testado durante o algoritmo se a
existe um j que pertence a todas as transações
• Não é feito no diffset porque o conjunto seria
muito grande
Resultados

Bases de dados
Dataset
BMS-Web-View1
BMS-Web-View2
BMS-POS
T10I4D100K
T40I10D100K
pumsb
pumsb star
mushroom
connect
chess
#items
497
3,340
1,657
1,000
1,000
7,117
7,117
120
130
76
#Trans Minsup
(%)
59,602
77,512
517,255
100,000
100,000
49,046
49,046
8,124
67,577
3196
0.1–0.01
0.1–0.01
0.1–0.01
0.15–0.025
2–0.5
95–60
50–10
20–0.1
95–40
90–30
Resultados

LCMfreq, LCM, LCMmax, FPgrowth,
eclat, apriori, mafia-mfi
• Em todas as 9 base de dados diferentes