Mineração de Dados
2º Semestre - 2011
Aula 29: Regras de Associação
Profa. Ms. Rosângela da Silva Nunes
1 de 18
Mineração de Dados
2º Semestre - 2011
Avaliação dos padrões
Algoritmos de regras de associação tendem a
produzir muitas regras
Muitas delas são desinteressantes ou redundantes
Redudantes: se {A,B,C} → e {A,B} → {D} possuem o
mesmo suporte e confiança
Medidas podem ser usadas para
podar/classificar os padrões derivados
Na formulação original – suporte e confiança
são as únicas medidas usadas
2 de 18
Mineração de Dados
2º Semestre - 2011
Aplicação de medidas
Knowledge
Patterns
Postprocessing
Preprocessed
Data
Prod
Prod
uct
Prod
uct
Prod
uct
Prod
uct
Prod
uct
Prod
uct
Prod
uct
Prod
uct
Prod
uct
uct
Featur
Featur
e
Featur
e
Featur
e
Featur
e
Featur
e
Featur
e
Featur
e
Featur
e
Featur
e
e
Mining
Selected
Data
Data
Preprocessing
Selection
3 de 18
Mineração de Dados
2º Semestre - 2011
Computando a tabela de
contigência
Dada uma regra X → Y, a informação necessária
para computar regras de interesse podem ser
obtidas com a tabela de contingência
Tabela de contingência para X → Y
Y
Y
X
f11
f10
f1+
X
f01
f00
fo+
f+1
f+0
|T|
f11: contador de suporte de X e Y
f10:contador de suporte de X e Y
f01: contador de suporte de X e Y
f00: contador de suporte de X e Y
Usado para definir várias medidas

suporte, confiança, lift, Gini,
J-measure, etc.
4 de 18
Mineração de Dados
2º Semestre - 2011
Computando a tabela de
contingência
{Milk, Beer} → {Diaper}
{Diaper}
{Diaper}
{Milk, Beer}
f11 = 2
f10 = 0
f1+= 2
{Milk, Beer}
f01 = 2
f00 = 1
f0+= 3
f+1= 4
f+0= 1
|T| = 5
TID
Items
1
Bread, Milk
2
3
4
5
Bread, Diaper, Beer, Eggs
Milk, Diaper, Beer, Coke
Bread, Milk, Diaper, Beer
Bread, Milk, Diaper, Coke
5 de 18
Mineração de Dados
2º Semestre - 2011
Limitações da Confiança
Avaliando {Chá} → {Café}
{Café}
{Café}
{Chá}
f11 = 150
f10 = 50
f1+= 200
{Chá}
f01 = 650
f00 = 150
f0+= 800
f+1= 800
f+0= 200
|T| = 1000
Suporte({Chá, Café}) = 150/1000 = 0,15
Confiança ({Chá} → {Café}) = 150/200 = 0,75
Proporção de pessoas que bebem chá e café é na
verdade bem menor que a proporção geral das
pessoas que bebem café
Relacionamento inverso: {Café} → {Chá}
Confiança({Café} → {Chá}) = 150/800 = 0,20
6 de 18
Mineração de Dados
2º Semestre - 2011
Medida: Lift & Interesse
Para variáveis binárias - Lift é equivalente a Fator de Interesse
Interpretação
Variáveis independentes
P(A,B) = P(A).P(B)
I(A,B) = 1
s ( A, B )
P ( B | A) c( A → B )
s ( A, B )
Nf11
s ( A)
Lift =
=
=
=
=
P( B)
s( B)
s( B)
s ( A) s ( B ) f1+ f + 1
I ( A, B ) =
s ( A, B )
Nf11
=
s ( A) s( B ) f1+ f + 1
Relacionadas positivamente
P(A,B) > P(A).P(B)
I(A,B) > 1
Relacionadas negativamente
P(A,B) < P(A).P(B)
Exemplo do chá-café
I (Chá, Café) =
0,15
= 0,9375
0,2.0,8
I(A,B) < 1
7 de 18
Mineração de Dados
2º Semestre - 2011
Limitações do Fator de Interesse
I(p,q) = 0,88/0,93.0,93 = 1,02
I(r,s) = 0,02/0,07.0,07 = 4,08
q
q
p
880
50
930
p
50
20
70
930
70
1000
r
r
r
20
50
70
r
50
880
930
70
930
1000
Obs.:
I(p,q) próximo de 1
Variáveis independentes?
p e q aparecem juntos em 88%
I(r,s) > I(p,q)
r e s raramente aparecem juntos
C(p,q) = 0,88/0,93 = 94,6%
C(r,s) = 0,02/0,07 = 28,6%
8 de 18
Mineração de Dados
2º Semestre - 2011
Exemplos de medidas
Literatura propões
diversas medidas
Algumas medidas
são boas para
algumas aplicações
mas não para outras
Como determinar a
melhor medidas?
9 de 18
Mineração de Dados
2º Semestre - 2011
Consistência entre medidas
objetivas
10 exemplos de tabelas de
contingência
Classificação de tabelas de
contingência
Example
f11
E1
E2
E3
E4
E5
E6
E7
E8
E9
E10
8123
8330
9481
3954
2886
1500
4000
4000
1720
61
f10
f01
f00
83
424 1370
2
622 1046
94
127
298
3080
5
2961
1363 1320 4431
2000 500 6000
2000 1000 3000
2000 2000 2000
7121
5
1154
2483
4
7452
10 de 18
Mineração de Dados
2º Semestre - 2011
Propriedade de permutação da
variável
A
A
B
p
r
B
q
s
B
B
A
p
q
A
r
s
Simétricas
M(A → B) = M(B → A)
Ex: Interesse
Assimétricas
M(A → B) ≠ M(B → A)
Ex: Confiança
11 de 18
Mineração de Dados
2º Semestre - 2011
Propriedade de escala
Male
Female
High
2
3
5
Low
1
4
5
3
7
10
Male
Female
High
4
30
34
Low
2
40
42
6
70
76
2x
10x
Uma medida objetivo M é invariante sob a operação de escala na
linha/coluna se M(T) = M(T') onde
T = [f11;f10;f01;f11]
T’ = [k1k3f11; k2k3f10; k1k4f01; k2 k4f00] e k1, k2, k3 e k4 são cte positivas
Ex: Taxa de probabilidade = (f11. f00)/(f10.f01)
12 de 18
Mineração de Dados
2º Semestre - 2011
Propriedade de Inversão
.
.
.
.
.
Transaction 1
Transaction N
A
B
C
D
E
F
1
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
(a)
(b)
(c)
13 de 18
Mineração de Dados
2º Semestre - 2011
Propriedade de Inversão
A=1
A=0
B=1
0
1
1
B=0
2
7
9
2
8
10
C=1
C=0
D=1
7
2
9
D=0
1
0
1
8
2
10
Uma medida objetiva M é invariante sob a operação de
inversão se o seu valor permanecer o mesmo ao se trocar os
contadores de frequência f11 por f00 e f10 ou f01
Exemplo: Taxa de probabilidade
Piatetsky-Shapiro =f11/N -(f1+f+1)/N2
PS(A,B) = 0/10 – (1.2)/100 = -0,02
PS(C,D)=7/10 – (9.8)/100 = 0,7 – 0,72 = -0,02
14 de 18
Mineração de Dados
2º Semestre - 2011
Propriedade de Adição Nula
A
A
B
p
r
B
q
s
A
A
B
p
r
B
q
s+k
Uma medida objetiva M é invariante sob a operação nula
se não for afetada pelo aumento de f00 enquanto que
todas as outras frequências na tabela de contingência
permanecem iguais
Exemplo: Jaccard = f11 /(f1+ + f+1 - f11)
15 de 18
Mineração de Dados
2º Semestre - 2011
Paradoxo de Simpson
Comprar
HDTV
Comprar Aparelhos de
ginástica
Total
Sim
Não
Sim
99
81
180
Não
54
66
120
153
147
300
c({HDTV = Sim} → {Aparelho de ginástica = Sim}) = 99/180 = 55%
Essa regra sugere que os clientes que compram televisores de
alta definição têm mais probabilidade de comprar aparelhos de
ginástica do que os que não compram televisão
16 de 18
Mineração de Dados
2º Semestre - 2011
Paradoxo de Simpson
Grupos
consumidores
Alunos de
Faculdade
Adultos
Trabalhadores
Comprar
HDTV
Comprar Aparelhos de
Ginástica
Total
Sim
Não
Sim
1
9
10
Não
4
30
34
Sim
98
72
170
Não
50
36
86
Alunos de faculdade
c({HDTV = Sim} → {Aparelho de ginástica = Sim}) = 1/10 = 10%
c({HDTV = Não} → {Aparelho de ginástica = Sim}) = 4/34 = 11,8%
Adultos trabalhadores
c({HDTV = Sim} → {Aparelho de ginástica = Sim}) = 98/170 = 57,7%
c({HDTV = Não} → {Aparelho de ginástica = Sim}) = 1/10 = 58,1%
17 de 18
Mineração de Dados
2º Semestre - 2011
Paradoxo de Simpson
Inversão na direção da associação
Explicação
85% dos clientes são adultos brasileiros
Relacionamento mais forte nos dados combinados
do que nos dados estratificados
Exemplo
Dados de cestas de compras devem ser
estratificados de acordo com os locais de lojas
18 de 18