Regras de Associação - Mineração de Dados

1 /Nunes & Guimarães 38

Regras de Associação

Profª. Rosângela Nunes

Prof. Norton Guimarães


Agenda

Motivação

Definição

Conceitos básicos

Minerando Regras de Associação

Algoritmo Apriori

Geração de regras de Associação

Avaliação das regras


Motivação


Aplicações

Market Basket

43% das pessoas que compram computadores também compram software de gestão financeira

Web Mining45% dos visitantes que acessam páginas sobre Voleibol também acessam páginas sobre Handebol


Agenda

Motivação

Definição

Conceitos básicos


Algoritmo Apriori




Definição

Padrões que aparecem frequentemente num conjunto de dados


Agenda

Motivação

Definição

Conceitos básicos


Algoritmo Apriori




Representação dos dados

• Dados de transação

• Atributos assimétricos• Apenas a presença(um valor diferente de

zero) é importante


Conceitos básicos

• Conjunto de itens• I = {i1, i2, …., in}• Exemplo:• I = {Bread, Milk, Beer, Eggs, Diaper, Coke}

• Conjunto de transações• D = {T1, T2, …., Tn}


Conceitos básicos

• Seja A um conjunto de itens:• Uma transação T contém A se, somente se,

• Exemplo• T = {Bread, Diaper, Beer, Eggs}• A = {Bread, Diaper}

IA

TA


Conceitos básicos

• Regra de associação

Implicação significa co-ocorrência e não causalidade

BAIBIABA e e onde ,


Conceitos básicos

• Exemplo• A = {Milk, Beer}• B = {Diaper}• {Milk, Beer} → {Diaper}


Conjunto de itens (Itemsets)

• Seja um conjunto de itens• I = {i1, i2, …., in}

• Um conjunto é um itemset• |S| = k, então S é um k-itemset

IS


Conjunto de itens

• I = {Bread, Milk, Beer, Eggs, Diaper, Coke}

• A = {Bread} é um 1-itemset

• B = {Milk, Coke} é um 2-itemset

• C = {Beer, Bread, Coke} é um 3-itemset


Contador de suporte

• Número de transações que contém um itemset

• Exemplo

X= {Bread, Milk}• σ(X) = 3

|},|{|)( DTTXTX


Suporte de uma regra de associação

• Seja a regra de associação A → B• Suporte s é a porcentagem de transações em

D que contém A U B

• S = P(A U B) = σ(A U B)/N, onde N é o número de transações


Suporte de uma regra de associação

• Exemplos• {Bread} → {Beer}• σ({Bread} U {Beer}) = 2• s = 2/5 = 0.4


Confiança de uma regra de associação

• Seja a regra de associação A → B

• Confiança c é a porcentagem de transações em D que contém A e também contém B

• c = P(B | A) = σ(A U B)/ σ(A)


Confiança de uma regra de associação

• Exemplos• {Bread} → {Beer}• σ({Bread} → {Beer} = 2 • σ({Bread} = 4• c = 2/4 = 0.5


Formulação do problema

• Dado um conjunto de transações D, encontre todas as regras que tenham suporte ≥ minsup e confiança ≥ minconf onde minsup e minconf são os limites de suporte e confiança correspondentes

• Frequente itemset: Satisfaz minsup

• Regras fortes: Satisfazem minsup e minconf


Agenda

Motivação

Definição

Conceitos básicos


Algoritmo Apriori




Minerando regras de associação

• Exemplo de regras• {Milk, Diaper} → {Beer} (s=0.4, c=0.67)• {Milk, Beer} → {Diaper} (s=0.4, c=1.0)• {Diaper, Beer} → {Milk} (s=0.4, c=0.67)• {Beer} → {Milk, Diaper} (s=0.4, c=0.67)• {Diaper} → {Milk., Beer} (s=0.4, c=0.5)• {Milk} → {Diaper, Beer} (s=0.4, c=0.5)



Todas as regras são partições binárias do mesmo itemset: {Milk, Diaper, Beer}

• Regras originadas do mesmo itemset possuem o mesmo suporte mas a confiança podem ser diferentes

• Então, podemos desacoplar os requisitos de confiança e suporte



• Passo 1 – Gerar todos os frequente itemset• Encontrar todos os itemsets que satisfazem

minsup

• Passo 2 – Gerar regras de associação fortes• Extrair todas as regras dos itemsets gerados no

passo 1 que satisfazem minconf

Obs. A performance é determinada pelo passo 1


Complexidade computacional

• Complexidade ~O(NMw)

• Abordagem custosa• M = 2d – 1, onde d = |I|


Estratégias para geração dos frequente itemsets

• Reduzir o número de candidatos (M)• Busca Completa: M = 2d

• Usar técnicas de poda para reduzir M

• Reduzir o número de comparações (NM)• Evitar corresponder cada conjunto de itens

candidatos com cada transação• Uso de estruturas de dados eficientes para

armazenar os candidatos e transações


Agenda

Motivação

Definição

Conceitos básicos


Algoritmo Apriori




Princípio Apriori

“ Se um itemset é frequente, então todos os seus subconjuntos também devem ser

frequentes”


Princípio Apriori

• X = {Bread, Milk, Diaper} (s = 0.4)• X1 = {Bread, Milk} (s = 0.6)• X2 = {Bread, Diaper} (s = 0.6)• X3 = {Milk, Diaper} (s = 0.6)• X4 = {Bread} (s = 0.8)• X5 = {Milk} (s = 0.8)• X6 = {Diaper} (s = 0.8)


Poda baseada em suporte

• Se um itemset for infrequente, então todos os seus superconjuntos devem ser infrequentes também.

• Propriedade anti-monotônica da medida de suporte:


Poda baseada em suporte


Ilustração do Princípio Apriori


O Algoritmo Apriori


Características do Apriori

• Algoritmo de níveis• Percorre um nível por vez• Conjuntos de 1 item ao tamanho máximo de

itens frequentes

• Estratégia de geração-e-teste• A cada iteração novos conjuntos de itens

candidatos são gerados a partir dos conjuntos de itens frequentes encontrados na iteração anterior


Geração de Candidatos - requisitos• Evitar geração excessiva de candidatos

• Excluir candidatos se pelo um item é infrequentes

• Assegurar que o conjunto candidato seja completo• Incluir o conjunto de todos os conjuntos de

itens frequentes

• Não gerar o mesmo conjunto de itens candidatos mais de uma vez


Métodos para geração de candidatos – Fk-1 x Fk-1


Apriori-gen

• Geração de candidatos• Passo de união (join)• Ck é gerado, unindo Lk-1 com ele mesmo

• Poda de candidatos• Passo de poda (prune)• Qualquer (k-1)-itemset que não seja

frequente, não pode ser um subconjunto de um k-itemset frequente


Apriori-gen – passo de join


Apriori gen – passo de poda


O Algoritmo Apriori


Agenda

Motivação

Definição

Conceitos básicos


Algoritmo Apriori





• Passo 1 – Gerar todos os frequente itemset• Encontrar todos os itemsets que satisfazem

minsup

• Passo 2 – Gerar regras de associação fortes• Extrair todas as regras dos itemsets gerados no

passo 1 que satisfazem minconf

Obs. A performance é determinada pelo passo 1


Geração de regras

• K-itemset pode produzir até 2k – 2 regras de associação

E: 3-itemset: {1, 2, 3}

{1,2} → {3} {1,3} → {2}

{2,3} → {1} {1} → {2,3}

{2} → {1,3} {3} → {1,2}


Cálculo da Confiança

• Não há necessidade de percorrer o banco de dados. Por quê?

• Ex:

• Itemset= {1,2,3}

• Regra: {1,2} → {3}

• Confiança = σ({1,2,3}) / σ({1,2})


Poda baseada em confiança

• Se uma regra X → Y – X não satisfazer o limite de confiança, então qualquer regra X' → Y – X', onde X' X, não deve satisfazer o limite de confiança também

• Como σ(X') ≥ σ(X) então• σ(Y) / σ(X') ≤ σ(Y) / σ(X)


Poda baseada em confiança


Geração de regras


Geração de regras


Procedimento ap-genrules


Exemplo

• minconf = 60%

• Dado o 3-itemset {b,d,e} σ({b,d,e}) = 4• H1 : {{e} , {d}, {b}}

• {b,d} → {e} c = 4/7 = 0,57• {b,e} → {d} c = 4/4 = 1• {d,e} → {b} c = 4/6 = 0,66


Exemplo

• minconf = 60%

• Dado o 3-itemset {b,d,e} σ({b,d,e}) = 4

• H2 : { {b,d}}

• e → {b,d} c = 4/7 = 0,57


Agenda

Motivação

Definição

Conceitos básicos


Algoritmo Apriori




Avaliação de 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} → {D} 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


Tabela de Contingê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


Computando a tabela de contingência

• {Milk, Beer} → {Diaper}


Limitações da Confiança

• Avaliando {Chá} → {Café}• 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


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 medida?


Dúvidas??Sugestões??

Críticas??

Documents

Regras de Associação - Mineração de Dados