Regras de associação

Em mineração de dados e aprendizado de máquina, regras de associação são usadas para descobrir elementos que ocorrem em comum dentro de um determinado conjunto de dados.^[1]

Algoritmos

Existem diversos algoritmos que realizam buscas de regras de associação em bases de dados. Abaixo seguem alguns exemplos:

• Apriori
• Partition
• Eclat
• FP-Growth

Definição

Exemplo de base de dados com 4 itens e 5 transações.

transação	leite	pão	manteiga	cerveja
1	1	1	0	0
2	0	1	1	0
3	0	0	0	1
4	1	1	1	0
5	0	1	0	0

As regras de Associação têm como premissa básica encontrar elementos que implicam na presença de outros elementos em uma mesma transação, ou seja, encontrar relacionamentos ou padrões frequentes entre conjuntos de dados. O termo transação indica quais itens foram consultados em uma determinada operação de consulta.

Conceitos úteis

Várias métricas podem ser utilizadas para avaliar as regras e identificar quais são interessantes. As restrições mais utilizadas são limiares mínimos de suporte e confiança.

• O suporte de um conjunto X é definido como a proporção de transações da base de dados que contém esse conjunto.
• A confiança de uma regra é definida ${\displaystyle \mathrm {conf} (X\Rightarrow Y)=\mathrm {sup} (X\cap Y)/\mathrm {sup} (X)}$. Por exemplo, a regra ${\displaystyle \{\mathrm {leite,pao} \}\Rightarrow \{\mathrm {manteiga} \}}$ tem uma confiança de ${\displaystyle 0,2/0,4=0,5}$ na base de dados, o que significa que para 50% das transações que contém leite e pão a regra está correta.
  • A confiança pode ser interpretada como uma estimativa de probabilidade ${\displaystyle P(Y|X)}$, a probabilidade de encontrar o RHS da regra nas transações sobre a condição que essas transações também contenham LHS.^[2]
• O lift de uma regra é definido como ${\displaystyle \mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {sup} (X\cap Y)}{\mathrm {sup} (Y)\times \mathrm {sup} (X)}}}$ ou a razão do suporte observado que são esperados se X e Y estão independente. A regra ${\displaystyle \{\mathrm {leite,pao} \}\Rightarrow \{\mathrm {manteiga} \}}$ possui um lift de ${\displaystyle {\frac {0,2}{0,4\times 0,4}}=1,25}$.
• A convicção (conviction) de uma regra é definido como ${\displaystyle \mathrm {conv} (X\Rightarrow Y)={\frac {1-\mathrm {sup} (Y)}{1-\mathrm {conf} (X\Rightarrow Y)}}}$. A regra ${\displaystyle \{\mathrm {leite,pao} \}\Rightarrow \{\mathrm {manteiga} \}}$ tem uma convicção de ${\displaystyle {\frac {1-0,4}{1-0,5}}=1,2}$, e pode ser interpretado como a razão da freqüência esperada que X ocorre sem Y (isto quer dizer, a frequência que a regra faz uma predição incorreta) se X e Y forem divididos pela frequência das predições incorretas. Nesse exemplo, a convicção de 1,2 mostra que a regra ${\displaystyle \{\mathrm {leite,pao} \}\Rightarrow \{\mathrm {manteiga} \}}$ seria incorreta com uma frequência de 20% (1,2 mais frequente) se a associação entre X e Y tivesse uma chance aleatória.

Exemplo em Python

import pandas as pd
from mlxtend.frequent_patterns import apriori
from mlxtend.frequent_patterns import association_rules

columns = ['Transação', 'Leite', 'Pão']
dataset = [[1,           1,       1 ],
           [2,           0,       0 ],
           [3,           0,       0 ],
           [4,           1,       1 ],
           [5,           0,       1 ]]

df = pd.DataFrame(data = dataset, columns = columns)
del df['Transação'] # Remover a coluna "Transação"

frequent_itemsets = apriori(df, min_support=0.01, use_colnames=True)
print(frequent_itemsets)

frequent_itemsets = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.0, support_only=False)
print(frequent_itemsets)

Referências

1. T. Menzies, Y. Hu. Data Mining For Busy People. IEEE Computer, Outubro de 2003, pgs. 18-25.
2. Jochen Hipp, Ulrich Güntzer, and Gholamreza Nakhaeizadeh. Algorithms for association rule mining - A general survey and comparison. SIGKDD Explorations, 2(2):1-58, 2000.