Regras de Associação
Paulo J Azevedo
DI - Universidade do Minho
2007-2008
Detecção de associações nos dados
1
MAP-i 2007/2008
Sumário
•
•
•
Motivação
Introdução às regras de associação
Algoritmos para cálculo de termos frequentes
–
•
Representações Verticais
–
•
•
•
•
•
•
•
Apriori e outras variantes Breath-first
Algoritmos Depth-first com representações verticais
Representações condensadas de termos frequentes
Medidas de interesse
Filtragem de termos não correlacionados
Selecção e pruning de regras
Atributos contínuos em regras de associação
Estudo de propriedades numéricas com regras de
associação
Modelos de previsão com regras de associação
MAP-i 2007/2008
2
Problema
• Base de Dados de
Ticket Data
• Ex:
1 1901,1881,199,901
2 901,1661
3 676,199,177,100
…..
…
120099 78,1881,199,8
ite
m
•
O marketing da cadeia de Hipermercados
pretende fazer um estudo de
comportamento de compras.
•
Tem acesso aos dados representativos dos
“cestos de compras” (basket data)
•
•
Exemplo de perguntas a responder:
Que produtos estão associadas ao consumo
de cerveja X ?
Como podemos descrever a população
consumidora de amendoins?
Onde devem estar localizadas os produtos
de limpeza doméstica ?
Como se relacionam os produtos 1661 e
199 ?
•
•
•
Número da
transacção
3
MAP-i 2007/2008
Como expressar a informação extraída ?
• Regras que relacionam produtos (items),
Qualidade das regras
expressa por medidas
estatísticas.
901 & 1661  67
Há um número explosivo de
potenciais regras que podem ser
derivadas!
Todas as regras ?
Qual o procedimento
eficiente a aplicar?
Como obter ?
Como seleccionar ?
Como discriminar
regras “boas” de “más”
?
Como organizar ?
MAP-i 2007/2008
4
Podemos ver o problema pela perspectiva do
espaço de pesquisa a explorar
ABCD
Set indica
inclusão
matemática
Itemset
ABC
AB
ABD
AC
A
ACD
AD
B
BCD
BC
C
BD
CD
D
Item
5
MAP-i 2007/2008
Medidas de Interesse
•
•
•
•
•
Tipicamente recorre-se a uma métrica de incidência para definir quais as
associações significantes.
A mais popular é o suporte (contagem) dos itemsets.
As regras são qualificadas por uma métrica de interesse (previsibilidade,
solidez ou força da regra).
Normalmente é usada a confiança (probabilidade condicional)
Assim, a regra de associação:
901 & 707  1088 (sup=0.3,conf=0.9)
•
Deve ser lida como: a compra conjunta dos produtos 901, 707 e 1088 ocorre em
30% das transacções. Por outro lado, verifica-se que 90% das transacções que
contêm 901 e 707 também contêm o produto 1088.
•
Outra leitura: 90% da sub-população definida pelos produtos 901 e 707 consomem
1088.
•
Ou ainda: a contagem do consumo de 901 e 707, quando se adiciona 1088, desce
para 90% da inicial.
6
MAP-i 2007/2008
Aplicações
• Sistemas de recomendação,
• Web Adaptativo
– Amazon: o site recomenda novos interesses usando
os items visitados/comprados pelo utilizador.
– Challange Netflix: http://www.netflixprize.com
• Descriptive Data Mining (Clusters de residuos
em Proteinas),
• Spam Filtering,
• Classificação,
• etc,
7
MAP-i 2007/2008
Application: Recommendations using AR
click stream
C
D
A
B
index.html
Obs.: A
E
Recommendations (top 2):
D
Rules:
F
 D (conf: 0,8)
A
B
A
E  D
(conf: 0,7)
A
D  F
(conf: 0,6)
A  D
(conf: 0,5)
D  X
(conf: 0,4)
MAP-i 2007/2008
F
(0,6)
X
(0,4)
8
TTR Hydrophobic Clusters detection
Sup = 0.34821 Conf = 1.00000
LEU_12=[00.00 : 25.00[ <--
Leu 12
% SASA
100
75
PHE_64=[00.00 : 25.00[ &
50
MET_13=[00.00 : 25.00[ &
25
ALA_97=[00.00 : 25.00[
A
0
0
2
4
6
8
Met 13
L12 - M13
25
Distance (Å)
% SASA
100
75
50
25
0
0
2
4
6
20
15
10
5
0
8
0
Phe 64
2
4
6
8
L12 - F64
25
Distance (Å)
% SASA
100
75
50
25
0
0
2
4
6
20
15
10
5
0
8
0
Ala 97
2
4
6
8
L12 - A97
25
Distance (Å)
% SASA
100
75
50
25
0
0
2
4
6
8
20
15
10
5
0
0
Time (ns)
2
4
6
8
Time (ns)
Sup=0.34821 conf=1.0000
LEU_12=[00.00 : 25.00[ 
PHE_64=[00.00 : 25.00[ & MET_13=[00.00 : 25.00[ & ALA_97=[00.00 : 25.00[
9
MAP-i 2007/2008
Geração de Regras
• Cálculo da confiança: conf(AC) = s(A C) / s(A).
• Noção de thresholds de conf e sup (minsup e minconf)
• Algoritmo “trivial”:
Tendo ABC,
testar, sabendo s(AB) e s(ABC),
se s(ABC) / s(AB) ≥ minconf
Fazer este procedimento para todos os
s∈{ABC} em que #s > 1.
10
MAP-i 2007/2008
Cálculo de Termos Frequentes
(frequent itemsets)
• Algoritmo naif:
Seja K = { items em DB},
Derivar o P(K) (power_set),
Percorrer DB para contar as ocorrências de P(K)
Filtrar os itemset em P(K) que não verificam minsup.
• Intractável!!!!!!!!
• Melhor: fazer uso da propriedade downward closure
do suporte
Se X ⊆ Y então s(X) ≥ s(Y)
11
MAP-i 2007/2008
Algoritmo Apriori [Agrawal & Srikant 94]
• L_1 = { 1-items frequentes}
• For(k=2;L_k-1 ≠ {}; k++) do
C_{k} = apriori_gen(L_{k-1});
forall transacções t ∈ D do
• C_{t} = subsets(C_{k},t)
• Forall candidatos c ∈ C_{t} do
– C.count++;
End
L_{k} = {c ∈ C_{k} | c.count ≥ minsup}
End
Answer=
∪ L_{k};
Algoritmo Bottom-up e breath-first. Em apriori_gen é gerado os
candidatos a contar. Só são considerados candidatos que
obedecem à propriedade anti-monótona
(é candidato se todos os seus subconjuntos são frequentes!)
MAP-i 2007/2008
12
Aplicação da Propriedade Anti-monótona
ABCD
ABC
AB
ABD
AC
A
ACD
AD
B
BCD
BC
C
BD
CD
D
Infrequente
13
MAP-i 2007/2008
Apriori “in action…”
14
MAP-i 2007/2008
Tipos de Algoritmos para Cálculo
de termos frequentes (FIM)
• Breath-First
• Depth-First
Apriori
FP-growth
Partition
Inverted Matrix
Dic
Eclat
Sampling
Depth-first expansion (CAREN)
15
MAP-i 2007/2008
Algoritmo Partition
•
•
Versão paralela do Apriori. Definir várias partições no dataset onde
aplicamos localmente o Apriori.
A soma dos itemsets frequentes ocorridos em cada partição é um
superconjunto dos termos frequentes no dataset. Segunda passagem no
dataset para contar os candidatos encontrados nas partições.
16
MAP-i 2007/2008
Algoritmo Partition(2)
• Filtragem de candidatos globais
17
MAP-i 2007/2008
Algoritmo Dynamic Itemset
Counting (DIC)
Diminuir o número de passagems pelo dataset usando a ideia de iniciar a contagem
do N-itemset quando todos os seus subconjuntos (N-1)-itemsets já são frequentes.
18
MAP-i 2007/2008
DIC(2)
•Large definitvo: frequente e contado
•Large candidato:frequente mas em contagem
•Small definitivo: já contado não frequente
•Small candidato: em contagem, ainda não
frequente
19
MAP-i 2007/2008
Algoritmos: Representações
• Horizontais
– Transacções são listas de items. Ex:
t12: 1,4,6,7,12,129,929
t15: 2,4,5,6,14,189,901
• Verticais
– Representar a cobertura de cada item nas
transacções. Ex:
Tidlist(6) = [t12,t15,t24,t123,t300,…]
Tidlist(14)= [t15,t120,t541,…]
Tidlist(129)=[t12,t18,t45,…]
20
MAP-i 2007/2008
Representações Verticais
•
Cover Lists
–
–
–
–
•
Ideal para “sparse” data
Tidlist(I) = [t4,t9,t12,t45,t312,…]
sup(I) = #coverlist(I)
Tidlist(A U B) = tidlist(A) ∩ tidlist(B)
BitMaps
–
–
–
–
Melhores resultados com “dense” data
bitmap(I)= “0010011100011000”
Contar bits ligados
sup(I) = bitcount(bitmap(I))
bitmap(A U B) = bitmap(A) & bitmap(B)
Bitwise logical and
MAP-i 2007/2008
21
Representações Verticais (2)
• DiffSets (altamente escalável)
– Em vez de representar todo o tidlist, usar só as
“alterações” ao tidlist para calcular suporte.
– Diffset(A U B) = tidlist(A) – tidlist(B) (elementos de A que não
ocorrem em B)
•Inicialmente temos
– s(AB) = s(A) - #ds(AB)
diffsets < tidlists
•Ficam mais pequenos
– ds(ABC) = ds(AC) – ds(AB)
conforme os itemsets se
tornam mais longos
– s(ABC) = s(AB) - #ds(ABC)
• Exemplo:
– t(A) = [1,3,4,5], t(B)=[1,2,3,4,5,6], t(C)=[2,4,5,6].
– ds(AB)=[ ],ds(AC)=[1,3], ds(ABC)=[1,3],
– S(ABC)= 4 – 0 – 2 = 2.
MAP-i 2007/2008
22
Depth-first Expansion (Caren)
• 1º scan na BD para contar 1-items frequentes.
(items são ordenados por ordem crescente de suporte.
• 2ª scan montar bitmaps (cover lists) dos 1-items e contar 2-itemsets
frequentes.
• Depth-first expansion: Estender itemsets juntando items
(respeitando a ordem de items imposta). Fazer bitwise-and para
obter cover list do novo itemset. Usar testes para evitar operações
bitcounting redundantes (verificar se os 2-itemsets contidos no novo
itemset em expansão são frequentes, etc e outros “truques”).
Contagem de suport ↔ bitcounting.
transacção
1
Itemset ABCE
1
2
3
4
5
200 201
0
0
1
0
1
Ocorrência nessa transacção
MAP-i 2007/2008
0
23
Representações condensadas de
termos frequentes
•
•
•
•
All itemsets frequentes (FIS)
Itemsets máximos (MIS)
Closed itemsets (CIS)
Free-sets (FS)
Maximal Patterns
Closed Patterns
All Patterns
Em certas aplicações é viável calcular
versões condensadas dos itemsets.
Simplifica-se o cálculo e evita-se alguma
redundância.
24
MAP-i 2007/2008
Formatos Condensados
• Maximal itemsets
I é máximo se:
a  I : sup(a)  ms
• Closed itemsets
I é um closed itemset se:
s  I : sup(s)  ms & sup(s)  sup(I )
ou se
I 
J
Jcover(I)
O suporte dos itemsets frequentes que não são “closed”
25
são determinados pelos closed patterns.
MAP-i 2007/2008
Formatos Condensados (cont)
• Seja X não closed, então sup(X)=sup(I) onde I é
o mais pequeno closed pattern que contém X
(closure de X)
– Notar que em datasets esparsos #FIM ≈ #CIS !
• δ-Free-patterns
X é δ-free pattern sse não existe uma regra
de associação entre dois subconjunto de X com
δ excepções.
• Melhor: X é um δ-free pattern iff
X 1  X , sup( X )    sup( X 1)
26
MAP-i 2007/2008
Regras de Inferência de contagem
• Alguns algoritmos usam regras de inferência de
contagem (evitando algum esforço), derivando a
contagem de um itemset à custa das contagem
dos seus subconjuntos.
• Exemplos:
– (support lower bound)
Sejam X,Y,Z itemsets,
sup( XYZ)  sup( XY )  sup( XZ )  sup( X )
– (support inference)
Sejam X,Y,Z itemsets,
sup( XY )  sup( X )  sup( XYZ)  sup( XZ )
27
MAP-i 2007/2008
Exemplos de regras
Association Rules ...
Sup = 0.01500
Sup = 0.03900
Sup = 0.01000
Sup = 0.01000
Conf = 0.37500
Conf = 0.30000
Conf = 0.28571
Conf = 0.28571
oranges
oranges
oranges
oranges




bananas & peaches
peaches
bananas & potatoes
peaches & potatoes
• Que informação é possível tirar deste tipo de estrutura ?
• Leitura das regras…
• Capacidade de previsão?
• Interpretação das métricas
• Característica da população descrita...
• Redundância
28
MAP-i 2007/2008
Medidas de Interesse
•
•
•
•
•
•
Lift
Conviction
Leverage
Χ2
Reliability
etc
conf ( A  C )
Lift ( A  C ) 
s(C )
1  s(C )
conv( A  C ) 
1  conf ( A  C )
leve( A  C )  s( A  C )  s( A) * s(C )
R( A  C)  conf ( A  C)  s(C)
Teste de Χ2 entre
antecedente e
consequente
29
MAP-i 2007/2008
Medidas de Interesse (2)
Confiança:
• mede probabilidade condicional
conf ( A  C ) 
P(C) dado A
•Tende a dar ênfase a regras não
correlacionadas (spurious rules).
Laplace:
• estimador da confiança que tem
lapl( A  C ) 
em conta o suporte
• torna-se mais pessimista com o
valores de s(A) mais pequenos
• sofre dos mesmos problemas da
confiança
Lift:
• Mede a distância para a independência
entre A e C
• varia entre [0, +oo[
• Valor 1  independência,
• Valores longe de 1  indicam que a evidencia
de A fornece informação sobre C.
• mede co-ocorrência (não implicação)
• é simétrica!
MAP-i 2007/2008
Lift ( A  C ) 
s( A  C )
s( A)
s( A  C )  1
s ( A)  2
conf ( A  C )
s(C )
30
Medidas de Interesse (3)
Conviction:
• motivada pelas fraquezas de conf e lift
• varia entre [0.5, +oo[
• tenta capturar o grau de implicação entre A e C
• é directional i.e. conv(A C) ≠ conv(C  A)
• valor 1 indica independência
• motivação (implicação lógica): A  C  ~A υ C  ~(A ∩ ~C)
• medir quanto (A ∩ ~C) se desvia da independência.
• inverto o rácio entre s(A υ ~C) e s(A) x s(~C) para lidar com negação
• excelente medida para classificação.
1  s(C )
conv( A  C ) 
1  conf ( A  C )
Leverage:
• varia entre ]-0.25,0.25[
• mede o número de casos extra obtidos
em relação ao esperado (à independência)
leve( A  C )  s( A  C )  s( A)  s(C )
Teste do χ2:
•Mede independência estatística entre antecedente
e consequente
• não captura a força da correlação entre A e C
• Apenas suporta a decisão de independência
MAP-i 2007/2008
2 
n

riR
(O(r )  E[r ]) 2
E[r ]
31
Medidas de Interesse (4)
Jaccard:
•. mede grau de “overlap” (sobreposição) entre
os casos de A e os casos de C
• varia entre [0,1]
• mede a distância entre A e C pela fracção
entre os casos cobertos pelos dois e
os caso cobertos por um só (A ou C).
• valores altos indicam sobreposição de casos
cobertos.
Cosine:
• também mede grau de “overlap” entre A e C
• ver A e C como dois vectores
• valor 1, os vectores coincidem
• valor 0, vectores não têm sobreposição (varia entre [0,1])
Mutual Info:
• mede a redução de incerteza no consequente
quando o se toma conhecimento do antecedente.
• é simétrica
• baseada na noção de entropia (de Shanahan)
MAP-i 2007/2008
32
Problemas da métrica Confiança
A confiança pode não detectar independência. A
regra ovos  leite pode ter conf=80% mas
podemos saber que o consumo de ovos é
independente de leite.
Independência entre A e C:
s( A  C )  s( A)  s(C )
Noutros casos podemos ter dependência positiva/negativa.
Podemos usar uma medida de X^2 para medir correlação
Entre antecedente e consequente.
2 
n

riR
(O(r )  E[r ]) 2
E[r ]
Aplicar teste de X^2 com um valor de conf=95% e 1 grau de liberdade,
Se X^2 >= 3.84 rejeita-se a hipótese de independência.
MAP-i 2007/2008
33
Pruning nos itemsets
• Aplicar teste de X^2 durante a contagem de termos
frequentes.
• Problema: X^2 não satisfaz a propriedade downward
closure. Isto é, AB e BC podem não satisfazer o teste de
X2 mas ABC pode. Upward closure property:
– Se X2(AC) ≥ 3.84 então necessáriamente X2(ABC) ≥ 3.84
• Caren. Define sempre um consequente. Em itemsets
onde este ocorre aplica X2.
• Corre-se o risco de não gerar todas as regras possíveis.
Potencialmente incompleto!
34
MAP-i 2007/2008
Fraquezas do framework
suport-confiança
• Pode ser difícil definir um suporte mínimo ideal
• Certos problemas podem exigir suporte mínimos
extremamente baixos e.g. caviar  champagne
• Solução: procurar as k-optimal rules (sendo
óptimas em relação a uma medida específica)
• Suporte e confiança mínimas altas podem
perder regras interessantes
• Confiança pode atribuir alto interesse a regras
não correlacionadas (como vimos!)
• Outras medidas sofrem de problemas similares
35
MAP-i 2007/2008
Selecção e Pruning de Regras
• Um algoritmo de FIM (mesmo com filtragem de suporte
confiança mínima) pode gerar milhões de regras.
Podemos ter #{regras} >> #{transacções} !!!
• Maioria das regras são geradas fruto do acaso (no
sentido estatístico). Noção de false discoveries
• Regras não correlacionadas (em que o antecedente e o
consequente são independentes)
• Aparecimento de regras redundantes. Regras contêm
items no antecedente que são explicados por outros
items também no antecedente. Ex (grávida => mulher):
• Grávida & mulher  retenção_de_liquidos
– Descartar regra redundante x  y se:
– Existe z ∈ x : s(x  y) = s(x - z  y)
36
MAP-i 2007/2008
Pruning de Regras
Problema de improvement nas regras
Conf = 0.300
Conf = 0.315
oranges
oranges


bananas & peaches
peaches
Noção de improvement:
uma regra mais especifica tem de produzir uma mais valia em
termos de valor de medida de interesse.
imp( A  C )  min(A'  A : met ( A  C )  met ( A'  C ))
met pode ser ={conf,lift,conv,X^2,etc}
Se o improvement > 0 dizemos que são regras productivas.
37
MAP-i 2007/2008
Significância Estatística
• Em vez de definir um minimal improvement,
aplicar um teste de significância estatística:
eliminar regras não significativas (Webb,
Magnum Opus)
• Uma regra x  y é insignificante se
– Existir outra regra x – z  y em que valor
met(x  y) – met(x – z  y)
não é significativamente alto (sendo met(x  y) >met(x-z  y))
• Usa-se um teste da distribuição Binomial
para determinar significância
38
MAP-i 2007/2008
Regras Significativas
• Exemplo para um valor de significância α=1%
• Processo: eliminar a regra mais especifica se a probabilidade de se
obter, ao acaso, o conjunto de transacções que cobrem essa regra é
maior do que α, assumindo que os dados são obtidos de uma amostra
aleatória e que o verdadeiro valor da métrica (hipótese nula) é o da regra
mais geral.
• Regras (ntrans=1000, H0=0.907):
A & B  C
A
 C
sucesso
#casos
(antsup=272,sup=255,conf=0.938)
(antsup=333,sup=302,conf=0.907)
H.nula
H.alternativa
1-α
• Binom.test(255,272,0.907,>H0,conf=0.99), obtém-se p-value=0.04608
• A primeira regra é insignificante (para α=1%) em relação à segunda,
porque adicionando B ao antecedente não aumente significativamente o
valor de conf.
39
MAP-i 2007/2008
False Discoveries
• Seja ρ uma regra que satisfaz um conjunto de restrições
φ em relação a uma distribuição Θ, encontrada num
dataset D.
• Há o risco de se ter encontrado ρ que satisfaz φ em
relação a D mas não a Θ. (todos os métodos de pruning
vistos anteriormente sofrem deste problema!)
• Testes de Hipótese Estatísticos:
– H0: ¬ρ é verdadeiro
– Se ρ é encontrado temos uma false discovery - Erro tipo I
(unsoundness)
– Qualquer ρ que não satisfaz H0 e não for derivado Erro tipo II (incompleteness)
40
MAP-i 2007/2008
Significant Patterns (Webb’07)
• Dividir os dados para análise em exploratory
data e holdout data.
• Derivar regras no exploratory data
• Aplicar teste de hipóteses a cada regra (obter
um p-value para cada uma).
– Rejeito H0 se p-value < α.
• Usa-se a holdout data para efectuar os testes.
• Alternativa (within search):
– Calcular o tamanho do espaço de pesquisa
– Aplicar testes estatístico com correcção de Bonferroni
41
MAP-i 2007/2008
Significant Patterns (2)
• Usa o Exact Fisher Test,
– p-value(x  y, x–z  y):
p
min(b ,c )

i 0
(a  b)!(c  d )!(a  c)!(b  d )!
(a  b  c  d )!(a  i)!(b  i)!(c  i)!(d  i)!
– Aceitar x  y se p-value ≤ α
a = s(x υ y)
b = s(x υ ¬y)
c = s(x-z υ ¬z υ y)
d = s(x-z υ ¬z υ ¬y)
Calcula a probabilidade de
observar os números obtidos de
ocorrência de x&y (ou valores
maiores) dado o número de
ocorrências de x-z&y se
P(y|x)==P(y|x-z).
• Webb aplica este teste somente entre cada regra
x  y e as suas imediatas generalizações. Isto é
regras
– {}y e
– x–z  y tal que |x-z| = n - 1, sendo |x| = n.
– Notar que x  y tem 2|x| - 1 generalizações!!
MAP-i 2007/2008
42
Significant Patterns (3)
• Problema das Multiplas Comparações!
Probabilidade de ocorrer um erro de tipo I
aumenta com o número de testes.
• Usar Ajustamento de Bonferroni (corrigir α para n
testes como sendo κ= α/n) – crivo demasiado
fino!
• Usar Ajustamento de Holm (k em vez de α).
– Risco de erro tipo I é não mais do que α. Requer
ordenação dos p-values e ter disponíveis todos estes
valores antes de determinar valor de ajustamento (k).

– Para (n testes) pi,
k  max(1 j i p j 
)
n  j 1
43
MAP-i 2007/2008
Dados não Categóricos
(tratamento durante a geração dos itemsets)
• Em formato atributo/valor os atributos numéricos (ou de uma
grandeza não categórica, como ex: hierarquias) podem dar origem
a inúmeros items.
• Tende a gerar muitas regras e demasiado especificas, muitas vezes
sem valor de interesse. Em vez de:
class=1  colesterol = high & age=29
class=1  colesterol = high & age=32
class=1  colesterol = high & age=41
Deviamos ter:
class=1  colesterol = high & age ∈ [29,41]
• Catch 22 situation: items de intervalos pequenos implica suportes
baixos o que leva à não geração de certas regras.
• Por outro lado, intervalos grandes implica regras de confiança
baixa. Juntar valores de um atributo num intervalo leva à perda de
informação!
44
MAP-i 2007/2008
Tratamento de valores numéricos
• Em Pré processamento:
– Discretização em intervalos de valores. Ex: criar
intervalos onde é preservado o valor de classe.
– Binarização; cada atributo é convertido em dois
valores. Há a selecção de um valor de corte.
• Durante o processamento (árvores de decisão):
– Binarização: Seleccionar um valor de corte entre os
valores do conjunto associado à sub-árvore. O valor
escolhido é aquele que maximiza ganho! (e é sempre
um que está na transição entre valores de classe).
– Aplicação recursiva deste princípio.
45
MAP-i 2007/2008
Dados Numéricos
Age
Colest
Blood
Class
23
High
2.33
A
24
Low
2.39
B
27
High
2.21
A
27
Low
1.09
A
29
Low
2.02
A
30
Low
2.98
C
31
Low
3.01
C
31
High
1.98
B
33
low
2.09
B
Discretização Supervisionada: Atributo especial comando o processo.
Ex: Age: [23-23],[24-24],[27-29],[30-31],[33-33]
Ou Age < 29, Age ≥ 29.
Não supervisionada: O processo é independente dos outros atributos.
Ex: Age:[23-27],[29-31],[33-33]
MAP-i 2007/2008
46
Discretização
• Supervisionada:
– Fayyad & Irani: Entropy oriented
– Class intervals (caren)
– Chi-Merge
• Não supervisionada:
–
–
–
–
Equi-depth (intervalos de igual nº de elementos)
Equi-width (intervalos de igual largura)
Srikant (caren)
K-means
47
MAP-i 2007/2008
Discretização Fayyad & Irani
(em Pré-processamento)
• Ordenar os valores do atributo a discretizar,
• Definir os cut points – ponto onde há alternância
de classe,
• Calcular Ganho Informativo para cada ponto:
• Escolher ponto com maior valor de Ganho,
• Verificar se condição MDL é satisfeita
Se sim o processo pára,
Senão aplicar recursivamente o processo
à esquerda e direita do ponto escolhido.
48
MAP-i 2007/2008
Fayyad & Irani
• Condição Minimal Description Length:
N = #S, k = #classes, ki = #classes em Si
• Processo pára se a condição é satisfeita.
0.0
2.3
2.3
12.4
18.9
19.3
24.4
49
MAP-i 2007/2008
Discretização ChiMerge
• Juntar intervalos adjacentes que demonstram
independência sobre o atributo classe.
• Medir independência através de um teste de Χ2.
Escolher o par com menor valor da estatística.
• Parar quando, para o par escolhido, Χ2 > δ,
sendo δ dado pelo utilizador.
• Inicialmente ordena-se os valores do atributo a
discretizar. Cada valor dá origem a um intervalo
unitário.
50
MAP-i 2007/2008
ChiMerge
• Cálculo do Χ2
( Aij  Eij )
  i 1  j 1
Eij
2
2
k
2
• Sendo:
– k é número de classes
– Aij é número de exemplos no intervalo i da classe j
– Eij = #(intervalo i) x #(classe j) / N, ou seja frequência esperada.
• Graus de liberdade = (#intervalos -1) x (#classes -1)
• Se o teste indica dependência então a diferença na distribuição de
classes entre os intervalos é estatisticamente significativa. Ou seja,
os intervalos devem permanecer separados.
51
MAP-i 2007/2008
Discretização Srikant & Agrawal
• Ocorre durante a execução do algoritmo de FIM.
• Inicia com um número pré-definido de intervalos. Este
número é calculado usando uma medida de perda de
informação (Partial Completeness).
• Fusão de intervalos adjacentes controlada pelo valor de
suporte do intervalo obtido.
• Gera-se assim novos items que convivem com os
intervalos iniciais.
• Ficamos com vários níveis de informação sobre o
atributo numérico (com menor ou maior granularidade).
52
MAP-i 2007/2008
Fusão de Intervalos
Dom(X) = {1,2,3,4}
Intervalos base:
X=[1,1],
X=[2,2],
X=[3,3],
X=[4,4],
sup=0.1
sup=0.2
sup=0.2
sup=0.5
Então podemos ter:
X=[1,2], sup=0.3
X=[3,4], sup=0.7
Mas também:
X=[1,3], sup=0.5
X=[2,4], sup=0.9
e até
X=[1,4], sup=1
Não esquecer que estes intervalos só são
gerados se não ultrapassarem o suporte
máximo imposto pelo utilizar.
Há o problema da geração de demasiados
items. Para n valores (ou intervalos) de um
atributo temos potencialmente O(n^2) items
que contêm um valor ou intervalo do atributo.
O mesmo pode acontecer com as regras em
relação à confiança.
53
MAP-i 2007/2008
Partial Completeness
Pretende-se avaliar o grau de perda de informação que surge com a definição
de intervalos. Este medida permite definir o número ideal de intervalos em
relação à perda admitida.
Seja C um conjunto de itemsets de um dataset D. Para um K > 1, dizemos
que P é K-completo em relação a C se:
•
•
•
P ⊆ C,
X ∈ P e X’ ⊆ X → X’ ∈ P,
X ∈ C,
Z tal que:
– Z é uma generalização de X e s(Z) ≤ K x s(X),
–
Y⊆X
Y’ tal que:
Y’ é uma generalização de Y e
s(Y’) ≤ K x s(Y).




54
MAP-i 2007/2008
Exemplo
num
itemset
sup
1
X=[20,30]
10
2
X=[20,40]
12
3
X=[20,50]
15
4
Y=[1,5]
10
5
Y=[1,7]
12
6
X=[20,30],Y=[1,5]
8
7
X=[20,40],Y=[1,7]
10
Os itemsets 2,3,5,7 formam um conjunto
P 1.5-completo.
Qualquer itemset de X tem uma
generalização neste conjunto em que o
suporte dessa generalização é superior no
máximo 1.5 vezes o suporte de X
Intervalos equi-depth (com o mesmo número de valores contínuos)
minimizam o número de intervalos necessário para minimizar um dado
nível K de partial completeness.
55
MAP-i 2007/2008
Número de Intervalos
2*n
num 
ms * ( k  1)
n é o número de atributos contínuos. ms é suporte mínimo
Quanto mais baixo o valor de completude K menor a perda de informação
e maior o número de intervalos.
Notar que, para controlar a fusão de intervalos usa-se um valor de suporte
máximo que tipicamente, por omissão, é igual a ms.
56
MAP-i 2007/2008
Exemplo
X
Y
CLASS
1
11
A
1
11
B
2
13
B
2
13
A
3
15
C
3
15
A
7
18
B
7
18
B
9
23
B
9
23
A
ms = 0.2
K=8
2*2
num 
3
(0.2 * 7)
Intervalos base:
X=[1,2], X=[3,7], X=[9,9]
Y=[11,13], Y=[15,18], Y=[23,23]
Se suporte máximo for 0.6 podemos
obter por fusão:
X=[3,9] e Y=[15,23]
57
MAP-i 2007/2008
Geração de Regras de Associação para
propriedades de interesse numéricas
Ideia geral: Ter regras em que o consequente é a
representação de uma propriedade numérica.
Exemplos:
Sex=female  Wage: mean=$7.9 (overall mean=$9.02)
non-smoker & wine-drinker  life-expectancy=85 (overall=80)
58
MAP-i 2007/2008
Regras de Associação com propriedades
numéricas (cont)
• Várias propostas
– Quantitative Association Rules (Aumann &
Lindell99)
– Impact Rules (Webb 2001)
– Distribution Rules (Jorge & Azevedo 2006)
• Ideia comum a todas as propostas:
Gerar regras que representam o comportamento de uma
propriedade numérica num sub população interessante.
Diferentes propostas de noção de regra interessante.
59
MAP-i 2007/2008
Regras de Associação com propriedades
numéricas (cont)
•
Noção de sub população interessante.
–
QAR, usa um z-test para confirmar interesse (validade) da
regra. z-test entre meanJ(Tx) e mean(D-Tx) com α=0.05.
Complemento
de Tx
Regras do tipo: subset(X)  MeanJ(Tx)
onde
MeanJ(Tx) ≠ Mean(D-Tx)
z.test(μ0,observ,σ): Usado para encontrar diferenças
significativas entre as médias μ0 e média da amostra.
Calcula a probabilidade de a média de uma amostra obtida assumindo a média e desvio
padrão da população (μ0 e σ) seja maior do que a média observada - assume
distribuição Normal!
Permite concluir se a amostra pertence à população em
estudo.
60
MAP-i 2007/2008
Regras de Associação com propriedades
numéricas (cont)
Impact Rules (Webb)
• Interesse refere-se à noção de impacto. Optimização
pesquisando-se impact rules que maximizam a definição
de impacto.
• Uso de t-test para avaliar significância: tende para o z-test
com o aumento do número de graus de liberdade. Mais adaptado
para amostra pequenas. Procedimento de comparação de médias.
Média da prop.
de interesse
• Noção de Impacto:
Impact(IR)  (Mean(IR)  poi) x cover(ant(IR))
61
MAP-i 2007/2008
Distribution Rules
• O consequente é uma distribuição,
• Uso do teste Kolmogorov-Smirnov, para avaliar se regra
é interessante.
• Noção de interesse: Regra é interessante se o pi-value
do
Distribuição geral
Distribuição do
da população
subgrupo da regra
ks-test(apriori,rules-dist) < α
for menor que o valor α dado pelo utilizador.
62
MAP-i 2007/2008
Ideia Geral
• Gerar regras de associação em que o consequente é a
distribuição da propriedade numérica a estudar e o
antecedente a descrição da sub população.
• Comparar distribuição apriori (da população geral) com
a distribuição do sub grupo (via ks-test()).
• Ex:
Ant-Sup = 0.14482
IDADE={46/1,48/1,51/2,52/2,54/1,55/1,57/2,58/1,59/3,60/2,61/2,62/2,63/3,64/4,65
/4,66/4,67/3,68/4,69/2,70/6,72/6,73/4,75/3,76/7,77/5,78/3,79/1,80/2,81/1,82/4,83/2,
84/3,86/3,90/1 }  TAVC=1 & DIAB=0
Descreve a distribuição da IDADE para a sub população (que
representa 14,4% dos indivíduos estudados) que teve o tipo de AVC
63
1 e não é diabética.
MAP-i 2007/2008
Distribution Rule presentation
• property of
interest
• each DR is a plot
• distribution plot
– frequency
polygon
– static binning
• distribution
statistics
• comparison with
default
distribution
64
MAP-i 2007/2008
Medir o interesse de uma DR
• KS-interest:
– Given a rule Ay=Dy|A, its
KS-interest is 1-p,
– p is the p-value of the KS test
comparing Dy|A and Dy|
•KS-improvement
• value added by the refinements of a rule
• imp(AB) is
min({KS-interest(AB) - KS-interest(AsB) | AsA})
65
MAP-i 2007/2008
Aplicações de Regras de Distribuição
• Descripitive data mining
– dataset: Determinants of Wages from the 1985 Current Population
Survey in the United States, a.k.a. Wages
– property of interest: WAGE
• Rule discovery
–
–
–
–
–
min-sup=0.1, KS-int=0.95
minimal KS-improvement of 0.01
numerical attributes in the antecedent were pre-discretized
compact internal representation of rules
rules can be output as text or graphically
66
MAP-i 2007/2008
Using Distribution Rules
• antecedent
– people with 13 to 15
years of education
– not from the south
• consequent
– wage distribution is
better than the
whole population
but still
concentrated on the
same interval
MAP-i 2007/2008
67
Using Distribution Rules
• antecedent
– refinement of previous
– race is white
• consequent
– wage distribution is
even better than before
– KS-improvement is
higher than 0.01
– the wages still are
concentrated on the
same interval as before
68
MAP-i 2007/2008
Using Distribution Rules
• antecedent
– married males
• consequent
– less interesting
– still signif. different
69
MAP-i 2007/2008
Using Distribution Rules
• antecedent
– Occupation=Clerical
• consequent
– concentrated on
lower income
70
MAP-i 2007/2008
Using Distribution Rules
• antecedent
– Occupation=Management
• consequent
– clearly better wage
distribution
– we also observe a
slightly lifted right
tail
71
MAP-i 2007/2008
Using Distribution Rules
• antecedent
– young people
• consequent
– lower wages, very
concentrated
– some secondary
modes are
suggested
72
MAP-i 2007/2008
Análise de Sub Grupos
• Por vezes é interessante analisar a
distribuição dos valores de um atributo
numérico.
• Queremos identificar sub populações que
se distinguem em relação à população
geral pela distribuição particular do
atributo numérico.
• Aplicações naturais em dados médicos.
73
MAP-i 2007/2008
Análise de Distribuições
Ant sup = 0.18593 KS = 0.000000005119
Kurt = 10.990787557293 Skew = 2.475421605300
NCY=6 & ORIGIN=1 
MPG={ 15.0/4,16.0/5,17.0/2,18.0/18,19.0/13,20.0/7,
21.0/11,22.0/6,23.0/2,24.0/2,25.0/1,27.0/1,
29.0/1,38.0/1 }
Aplicar testes de “Goodness of Fit”. (e.g. Kolmogorov-Smirnov).
Compara distribuições segundo parâmetros tipo Skewness
(grau de assimetria) e Kurtosis (grau de afunilamento)
MAP-i 2007/2008
74
Modelos de Previsão
com Regras de Associação
• Ver um conjunto de regras seleccionadas
como um modelo de previsão.
• Para fazer previsão sobre um caso, usar
as previsões derivadas das regras que
cobrem esse caso.
• Usados em:
– Sistemas de recomendação
– Classificação
– Previsão numérica
75
MAP-i 2007/2008
Classificação com Regras de
Associação
• Os modelos são um conjunto
seleccionado de regras de associação.
• Regras com um só consequente = classe
(CAR rules).
• Várias propostas: CMAR, CBA, Apriori-C.
• Vários métodos: BestRule, Votação,
Distribuição de classes,
• Uso de diferentes métricas.
• Implementação no CAREN
76
MAP-i 2007/2008
BestRule Prediction
• Para um novo caso:
– Produzir um rank com as regras que cobrem caso,
– Escolher a regra do topo do rank,
– A previsão é o consequente desta regra,
bestrule x  arg min rank (r )
rF ( x )
– Rank é produzido pela seguinte ordenação:
R1  R2 if
m eas( R1 )  m eas( R2 ) or
m eas( R1 )  m eas( R2 )  sup( R1 )  sup( R2 ) or
m eas( R1 )  m eas( R2 )  sup( R1 )  sup( R2 )  ant( R1 )  ant( R2 )
MAP-i 2007/2008
77
Voting
• Para um novo caso:
– Seleccionar as regras que cobrem o caso,
– Cada regra vote na classe que representa
(consequente).
– A votação é ponderada pelo valor da medida
de interesse
– Alternativamente, a votação é uniforme
78
MAP-i 2007/2008
Class Distribution
• Só aplicável em medidas de interesse com
valores [0,1] (conf, laplace, etc)
• Votação idêntica aos métodos de voting.
• Noção de resíduo:
– Residuo(r) = 1 – vote(r),
– Os resíduos de um regra são uniformemente
distribuídos pelas classes não votadas pela regra,
– Regras com o mesmo corpo são tratadas em bloco.
79
MAP-i 2007/2008
Selecção de Regras CAR
•
Noção de cobertura do conjunto de treino
1)
2)
3)
Ordenar regras por ordem descendente de confiança
Para cada exemplo e ∈ Treino, e.count=0;
Enquanto conjunto Treino ≠ Ø e Regras ≠ Ø fazer
1)
Para cada r ∈ Regras
1)
2)
3)
4)
•
Encontrar todos os e que cobrem r
Se r classifica bem pelo menos um e
Então fazer e.count++ para todos e
Seleccionar r e retirar de Regras
Vários propostas: CBA os exemplos de treino
são retirados assim que usados. CMAR tem a
noção de cobertura δ. Os exemplos são
retirados quando e.count > δ.
80
MAP-i 2007/2008
Selecção de regras
• São seleccionadas as primeiras N regras que cobrem o
conjunto de treino (e com mais alta confiança)
• CBA usa pessimistic error rate based pruning
• CMAR aplica voting (selecção de várias regras que
cobrem o exemplo): Divide regras por grupos de classes
que estas representam. Faz votação por Χ2 pesado (de
cada grupo).
• Apriori-C usa subset feature selection – remoção de
items, e N best rules in each class – escolha por classe.
• CBA faz BestRule - Escolhe regra do topo da ordem.
Ordena regras por:
– R1 > R2 sse conf(R1) > conf(R2)
– Ou
conf(R1) == conf(R2) && sup(R1) > sup(R2)
– Ou
conf(R1) == conf(R2) && sup(R1) == sup(R2)
mas R1 gerada primeiro que R2
MAP-i 2007/2008
81
Composição de Modelos
• A escolha de um só modelo levanta problemas
estatísticos (decisão sem suporte), computacionais
(máximos locais) e de representação (a hipótese não
está no espaço).
• Uso de múltiplos modelos tende a minimizar todos estes
problemas.
• Combinação de predições:
– Voting (ponderada)
– Voting (uniforme)
– Class distribuition (CAREN)
• Geração de Modelos Homogéneos
– Bagging
– Boosting
• Geração de Modelos Heterogéneos
– Stacking
82
MAP-i 2007/2008
Bagging
• Boostrapp AGGregation,
• boostrapping dos vários conjuntos de treino,
• Cada conjunto de treino (de tamanho igual ao
dataset inicial) dá origem a um modelo,
• (amostragem com substituição)
• Previsão feita por votação uniforme.
• Funciona porque reduz a variabilidade dos modelos
individuais escolhendo o voto maioritário de muitos modelos.
• Em árvores de decisão acontece:
• na escolha do um atributo de teste para um nó
• na escolha dos cut-points nos atributos numéricos.
83
MAP-i 2007/2008
Bagging
Post Bagging
S1
D
sampling
M1
pred1
SR2
M2
pred2
Sn
Mn
predn
voting
final
prediction
84
MAP-i 2007/2008
Post-Bagging (CAREN)
•
•
•
•
Jorge & Azevedo (Discovery Science 05)
Amostragem de regras em vez de casos,
Não há necessidade de “relearning”,
Conjunto de variantes sobre tipo de votos,
e possibilidade de “don’t knows”,
• Baixa a componente de variância do erro.
• Implementado no CAREN.
85
MAP-i 2007/2008
Boosting
• Algoritmo iterativo
• Associa um peso a cada exemplo
• Inicializar os peso de uma forma uniforme
• Iterativamente:
• gera um modelo para a actual distribuição
dos exemplos (distribuição dada pelos pesos)
• os pesos dos exemplos mal classificados
são incrementados para a próxima iteração.
• Os modelos gerados são agregados por votação
pesada.
• Há redução do bias e da variância.
86
MAP-i 2007/2008
Boosting (2)
• Weak learner que gera um hiper-plano paralelo a um dos eixos
1ºIteração
+
+
+
+
-
+
+
+
-
Treino
+
+
+
+
Decisão
+
2ºIteração
+
Treino
+
+
+
-
-
+
+
+
+
-
-
Composição dos
Dois modelos
-
Decisão
No limite, boosting consegue “cobrir” todos os casos,
i.e. accuracy de treino = 1.0 MAP-i 2007/2008
87
Iterative Reordering
• Increase the accuracy of a CAR set
– Run the rule set on the training set
– Re-evaluate the interest and support of each
rule
• Interest according to rule’s accuracy
• Support according to rule’s usage
– This yields a new ordering on the original set
of rules
88
MAP-i 2007/2008
Iterative Reordering
D
Rule
generation
T1
r1
r2
r3
r4
pred1
T2
Tn
T3
Re-evaluate
Re-order
filter
r1
r3
r2
r4
Re-evaluate
Re-order
filter
+
pred2
+
r2
r3
r1
...
pred3
+
MAP-i 2007/2008
r2
r3
predn
final
prediction
89
Ensemble generation
• Updating interest
• support(Triali) = usage(Triali-1)
90
MAP-i 2007/2008
IRE Algorithm
91
MAP-i 2007/2008
Prediction
• Given a new case
– For each trial
• Use BestRule
• Overall prediction
– Weighted trial voting (two variants)
• Weight = global accuracy of the trial
– IRE.V.Acc.int
• Weight = interest measure of the best rule within
the trial
– IRE.BR.int
92
MAP-i 2007/2008
Method behavior
• Bias variance analysis (Kohavi’s methodology)
– 10 out of 12 datasets reduce bias visibly
– Variance tends to increase
– Error reduction seems to be mainly due to bias reduction
93
MAP-i 2007/2008
Conclusões
• Algoritmos para calcular associações entre
elementos atómicos nos dados (items),
• Geração de Regras que descrevem associação
entre elementos atómicos dos dados.
• Selecção de regras interessantes e
significativas,
• Tratamento de dados não categóricos
• Análise de propriedades de interesse
numéricas.
• Previsão com regras de associação
94
MAP-i 2007/2008