Regras de associação

Em mineração de dados e aprendizado de tratamento, regras de associação são usadas para descobrir elementos que ocorrem em comum dentro de um determinado conjunto de dados.

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

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 sup(X) 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 $\mathrm{conf}(X\Rightarrow Y) = \mathrm{supp}(X \cup Y) / \mathrm{supp}(X)$. Por exemplo, a regra $\{\mathrm{leite, pao}\} \Rightarrow \{\mathrm{manteiga}\}$ tem uma confiança de 0.2 / 0.4 = 0.5 na base de dados, o que significa que para 50% das transações que contém leite e pao a regra está correta.
  • A confiança pode ser interpretada como uma estimativa de probabilidade 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.
• O lift de uma regra é definido como $\mathrm{lift}(X\Rightarrow Y) = \frac{ \mathrm{supp}(X \cup Y)}{ \mathrm{supp}(Y) \times \mathrm{supp}(X) }$ ou a razão do suporte observado que são esperados se X e Y estão independente. A regra $\{\mathrm{leite, pao}\} \Rightarrow \{\mathrm{manteiga}\}$ possui um lift de $\frac{0.2}{0.4 \times 0.4} = 1.25$.
• A convicção (conviction) de uma regra é definido como $\mathrm{conv}(X\Rightarrow Y) =\frac{ 1 - \mathrm{supp}(Y) }{ 1 - \mathrm{conf}(X\Rightarrow Y)}$. A regra $\{\mathrm{leite, pao}\} \Rightarrow \{\mathrm{manteiga}\}$ tem uma convicção de $\frac{1 - 0.4}{1 - .5} = 1.2$, e pode ser interpretado como a razão da freqüência esperada que X ocorre sem Y (isto quer dizer, a frequencia que a regra faz uma predição incorreta) se X e Y forem divididos pela freqüência das predições incorretas. neste exemplo, a convicção de 1.2 mostra que a regra $\{\mathrm{leite, pao}\} \Rightarrow \{\mathrm{manteiga}\}$ seria incorreta com uma frequencia de 20% (1.2 mais freqüente) se a ssociação entre X e Y tivesse uma chance aleatória.