Mineração de Dados: Associação - Aula...

Mineração de Dados: Associação - Aula 18

Profa Janniele Aparecida Soares Araujo

CSI462 – Sistemas de Apoio à Decisão

2

Mineração de dados: associação

● Introdução● É a tarefa de descobrir relacionamentos interessantes entre registros

em grandes bases de dados● Transações de cestas de compras● Identificar relações entre convicções e o voto de eleitores

3

Mineração de dados: associação

● Regras de Associação● Um algoritmo de associação procura por regras de associação● Atendem a um suporte e confiança mínimos preestabelecidos● Uma regra de associação é expressa na seguinte forma:

X → Y● Seja σ(X)X)) a quantidade de vezes em que um conjunto X aparece e

σ(X)X) ∪ Y) ) a quantidade de vezes em que os conjuntos X e Y aparecem em união:● Suporte: sup(X)X)) = σ(X)X))/NN● Suporte: sup(X)X) ∪ Y) ) = σ(X)X) ∪ Y) )/NN● Confiança: conf (X)X) → Y) ) = σ(X)X) ∪ Y) )/Nσ(X)X))

4

Mineração de dados: associação

● Exemplos● Regras(X → Y): {Leite, Fraldas} → {Cerveja}

● σ(X Y) = 2 ∪Y) = 2 ● σ(X) = 3

● sup(X Y) = 2/5 = 0,4∪Y) = 2 ● sup(X) = 3/5 = 0,6

● conf (X → Y) = 2/3 = 0,67

TID Itens

1 {Pão, Leite}

2 {Pão, Fraldas, Cerveja, Ovos}

3 {Leite, Fraldas, Cerveja, Cola}

4 {Pão, Leite, Fraldas, Cerveja}

5 {Pão, Leite, Fraldas, Cola}

5

Mineração de dados: associação

● Definições● Associação é um processo de duas etapas:

1)Gerar o conjunto de itemsets frequentes (que atendem ao suporte mínimo)

2)Gerar as regras a partir dos itemsets frequentes (que atendem à confiança mínima)

6

Mineração de dados: associação● Geração do conjunto de itens

frequentes por força bruta● Listar todos os conjuntos de itens

possíveis e calcular seu suporte● A primeira tabela representa uma

base de dados de compras efetuadas

TID Itens

1 {Pão, Leite}

2 {Pão, Fraldas, Cerveja, Ovos}

3 {Leite, Fraldas, Cerveja, Cola}

4 {Pão, Leite, Fraldas, Cerveja}

5 {Pão, Leite, Fraldas, Cola}

Candidatos Suporte

{Pão} 4/5 = 0.9

{Leite} 4/5 = 0.9

{Fraldas} 4/5 = 0.9

{Cerveja} 3/5 = 0.8

{Ovos} 1/5 = 0.2

{Cola} 2/5 = 0.4

{Pão,Leite} 3/5 = 0.8

{Pão,Fraldas} 3/5 = 0.9

{Pão, Cerveja} 2/5 = 0.4

... ...

7

Mineração de dados: associação

● Extremamente ineficiente!● O(N x M x W)● N = número de transações● M = número de conjuntos de itens candidatos (2k - 1, k = itens)● W = Tamanho da maior transação● Nosso pequeno exemplo levaria a (5 * 63 * 4) = 1260 comparações

8

Mineração de dados: associação

● Princípio do Apriori● Se um conjunto de itens é

frequente, então todos os seus subconjuntos também o são

9

Mineração de dados: associação

● Princípio do Apriori● Se um conjunto de itens é

infrequente, então todos os seus superconjuntos também o são

10

Mineração de dados: associação

● Algoritmo Apriori● Inicialmente cada item é considerado um conjunto candidato de 1

item● Os que não atendem o suporte mínimo são descartados● Posteriormente, procura-se conjuntos candidatos de 2 itens usando

apenas os conjuntos de 1 item● O processo é repetido até não restarem mais conjuntos de candidatos

a serem testados

11

Mineração de dados: associação

apriori(minSup, conjunto de transações T, conjunto de itens I)

1.K = 1;

2. F = Fk = {i | i ∈ I ∧ σ(i) ≥ minSup x |T|}; //Gera o conjunto de 1-itemsets frequentes

3. faça

1. ++k;

2. Ck = genCandidatos(Fk-1); //Gera o conjunto itens candidatos

3. para cada t ∈ T

1. Ct = subset(Ck, t); //Separa os candidatos que estão contidos na transação 2. para cada candidato c ∈ C

1. ++σ(c); //Incrementa seu valor de suporte3. Fim-para

4. Fim-para

5. Fk = {c | c ∈ Ck ∧ σ(c) ≥ minSup x |T |}; //Adiciona os candidatos que atendem ao suporte mínimo

6. F = F ∪Y) = 2 Fk;

4.ate que Fk = ∅;

5. retorne F;

fimAssociador

12

Mineração de dados: associação

● Algoritmo Apriori● A função genCandidatos(Fk-1)

● Funde pares de conjuntos frequentes de tamanho k-1, gerando conjuntos frequentes de tamanho k● Usa ordenação lexicográfica para evitar candidatos duplicados

Conjunto de 2 itens

{Cerveja, Fraldas}

{Fraldas, Leite}

{Fraldas, Pão}

{Leite, Pão}

Conjunto de 2 itens

{Cerveja, Fraldas}

{Fraldas, Leite}

{Fraldas, Pão}

{Leite, Pão}

Conjunto de 3 itens

{Fraldas, Leite, Pão}

13

Mineração de dados: associação

● Algoritmo Apriori● Calcular o suporte de todos os conjuntos de tamanho 1 e, em seguida,

eliminar aqueles que não possuem o suporte mínimo.● Minsup = 0.5

TID Itens

1 {Pão, Leite}

2 {Pão, Fraldas, Cerveja, Ovos}

3 {Leite, Fraldas, Cerveja, Cola}

4 {Pão, Leite, Fraldas, Cerveja}

5 {Pão, Leite, Fraldas, Cola}

Conjunto de 1 item frequente

{Cerveja} σ = 3 sup = 0.6

{Fraldas} σ = 4 sup = 0.8

{Leite} σ = 4 sup = 0.8

{Pão} σ = 4 sup = 0.8

14

Mineração de dados: associação

● Algoritmo Apriori● Formar todos os possíveis conjuntos de tamanho 2 a partir daqueles

de tamanho 1 resultantes do passo anterior.

Conjunto de 1 item frequente

{Cerveja}

{Fraldas}

{Leite}

{Pão}

Conjunto de 1 item frequente

{Cerveja}

{Fraldas}

{Leite}

{Pão}

Candidatos de 2 itens

{Cerveja, Fraldas} σ = 3 sup = 0.6

{Cerveja, Leite} σ = 2 sup = 0.4

{Cerveja, Pão} σ = 2 sup = 0.4

{Fraldas, Leite} σ = 3 sup = 0.6

{Fraldas, Pão} σ = 3 sup = 0.6

{Leite, Pão} σ = 3 sup = 0.6

15

Mineração de dados: associação

● Algoritmo Apriori● Criar um subset Ct a partir

dos novos candidatos e da base de compras

16

Mineração de dados: associação

● Algoritmo Apriori● Eliminar os novos conjuntos que não possuem o suporte mínimo

Candidatos de 2 itens

{Cerveja, Fraldas} σ = 3 sup = 0.6

{Cerveja, Leite} σ = 2 sup = 0.4

{Cerveja, Pão} σ = 2 sup = 0.4

{Fraldas, Leite} σ = 3 sup = 0.6

{Fraldas, Pão} σ = 3 sup = 0.6

{Leite, Pão} σ = 3 sup = 0.6

Candidatos de 2 itens

{Cerveja, Fraldas} σ = 3 sup = 0.6

{Fraldas, Leite} σ = 3 sup = 0.6

{Fraldas, Pão} σ = 3 sup = 0.6

{Leite, Pão} σ = 3 sup = 0.6

17

Mineração de dados: associação

● Algoritmo Apriori● Formar todos os possíveis conjuntos de tamanho 3 a partir daqueles

de tamanho 2 resultantes do passo anterior

Candidatos de 2 itens

{Cerveja, Fraldas}

{Fraldas, Leite}

{Fraldas, Pão}

{Leite, Pão}

Candidatos de 2 itens

{Cerveja, Fraldas}

{Fraldas, Leite}

{Fraldas, Pão}

{Leite, Pão}

Candidatos de 3 itens

{Fraldas, Leite, Pão}

18

Mineração de dados: associação

● Algoritmo Apriori● Criar um subset Ct a partir dos novos candidatos e da base de

compras.● Eliminar os novos conjuntos que não possuem o suporte mínimo

19

Mineração de dados: associação

● Algoritmo Apriori● Repetir o procedimento anterior até que, no k-ésimo passo, nenhum

novo conjunto de tamanho conjuntos de tamanho k, obtido a partir dos conjuntos de tamanho k-1, tenha suporte mínimo.

Candidatos de 3 itens

{Fraldas, Leite, Pão}

Candidatos de 3 itens frequentes

∅

20

Mineração de dados: associação

● E para gerar as regras!?● Para cada conjunto frequente f F, gere todas as possibilidades de ∈

regras e avalie sua confiança● Valores de suporte, previamente armazenados são utilizados para tal,

assim não é necessário ler a base de dados novamente● Conjuntos frequentes de tamanho 1 são descartados

21

Mineração de dados: associação

● E para gerar as regras!?● Seguindo o exemplo, suponha minConf = 0.9

Conjunto de itens frequentes (X)F)

{Cerveja, Fraldas} α = 3

{Fraldas, Leite} α = 3

{Fraldas, Pão} α = 3

{Leite, Pão} α = 3

{Cerveja}α = 3

{Fraldas} α = 4

{Leite} α = 4

{Pão} α = 4

Regras

{Cerveja} → {Fraldas} conf = 1.00

{Fraldas} → {Cerveja} conf = 0.75

{Fraldas} → {Leite} conf = 0.75

{Leite} → {Fraldas} conf = 0.75

{Fraldas} → {Pão} conf = 0.75

{Pão} → {Fraldas} conf = 1.00

{Leite} → {Pão} conf = 0.75

{Pão} → {Leite} conf = 0.75

22

Exercícios

1) Execute o manualmente algoritmo Apriori para a seguinte base de dados considerando. minSup = 0.5 e minConf = 0.6

23

Bibliografia

● Introdução ao Data Mining. Steinbach, Michael; Kumar, Vipin; Tan, Pang-ning, Rio de Janeiro: Ed. Ciencia Moderna, 2009.

● Notas de Data Mining. Fonseca, G.H.G, Universidade Federal de Ouro Preto, 2013