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]

AlgoritmosEditar

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

DefiniçãoEditar

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 úteisEditar

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  . Por exemplo, a regra   tem uma confiança de   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  , 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   ou a razão do suporte observado que são esperados se X e Y estão independente. A regra   possui um lift de  .
  • A convicção (conviction) de uma regra é definido como  . A regra   tem uma convicção de  , 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 freqüência das predições incorretas. Neste exemplo, a convicção de 1.2 mostra que a regra   seria incorreta com uma frequência de 20% (1,2 mais freqüente) se a associação entre X e Y tivesse uma chance aleatória.

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.