Uma rede de supermercados (normalmente WallMart) usando mineração de dados descobre que há uma estranha correlação entre compra de cerveja e compra de fraldas. Em algumas versões a rede coloca um estande de cerveja ao lado das fraldas. http://www.theregister.co.uk/2006/08/15/beer_diapers/
As técnicas de mineração de regras de associação e de conjunto de itens (itemset) frequentes é que permitem tirar este tipo de conclusão.
neste tipo de problema há um conjunto de itens (itens num supermercado - dado categorico) e há transações que contem um subconjunto dos itens (uma compra).
os itens podem ser paginas num site. a transação são as paginas visitadas em diferentes interações com o site.
o conceito de transação pode não ser localizado no tempo. Pode ser uma pessoa, e os itens aplicativos que ela instalou no seu celular (não necessariamente ao mesmo tempo).
ou pode ser proteinas ativas em diferentes tecidos de diferentes individuos (uma transação é a combinação de tecido e individuo).
Itemsets frequentes são conjunto de itens que aparecem juntos em pelo menos s% das transações. O número s, que precisa ser fornecido para o algoritmo é chamado de suporte
Vamos assumir as seguintes transações
A B C
A C
C D
A B
B D
D
Se o suporte é 1/3, ou seja queremos conjuntos de itens que aparecem em pelo menos 2 das 6 transações, então (A B) é um dos itemsets frequentes.
(A B) aparece como parte da primeira transação (mas (A B) não é a transação completa) e aparece como “parte” da 4 transação (e neste caso é a transação completa).
Há vários itemsets frequentes:
Se (A B) é um itemset frequente, então tanto (A) quanto (B) são também!
se um itemset tem n itens, então todas as 2^n -2 combinações dos itens também são itemsets frequentes.
no caso das transações acima , (A C) é um itemset frequente (e portanto (C) também é) e (D).
Portanto é necessario algumas restrições nos itemsets que serão retornados pelos algoritmos
um itemset i é maximal se ele tem suporte maior que s e todos os itemsets que incluem i tem suporte menor que s.
ou seja, não da para incluir mais nenhum item num itemset maximal e ainda ter um itemset com suporte maior que s
No exemplo anterior (A B), (A C), e (D) são maximais.
Um itemset i é fechado (closed) se todos os itemsets que o incluem tem suporte menor que i
no exemplo anterior todos os itemsets são fechados.
Regras de associação A B => C D
onde A B C D são itens. A confiança da regra (c) é a proporção das transações que incluem A B e que também incluem C D. Assim se a confiança da regra acima é 60% a regra pode ser lida como
Regras de associação 60% das pessoas que compraram A e B também compraram C e D
A confiança de uma regra é formalmente
confianca( A B => C D) = \frac{\#(A B C D)}{\#(A B)}
onde \#(A B) é o numero de transações que incluem o itemset (A B).
portanto
confianca( A B => C D) = \frac{suporte(A B C D)}{suporte(A B)}
Como usar um regra de associação A B => C D?
automaticamente: quando o cliente comprar A e B sugerir C e D. Neste caso queremos regras com alta confiança e regras do tipo A B => C
KDD: como uma regra para entender o problema. Neste caso queremos tanto alta confiança como alto suporte (não gastar o seu tempo entendendo um fenomeno que só acontece com 1 em dez milhões das transações!)
para KDD há outras considerações: quão interessante é a regra?
uma enquete de 1000 pessoas sobre que bebida elas tomam (se uma pessoa bebe tanto cafe como cha é uma transação com as 2 bebidas).
| – | café | não café | total |
|---|---|---|---|
| chá | 150 | 50 | 200 |
| não chá | 650 | 150 | 800 |
| total | 800 | 200 | 1000 |
a regra Chá => Café tem suporte 150/1000 = 0.15 (alto)
a confiança da regra é 0.15/0.2 = 75% também alto.
mas é regra não é interessante e é enganadora.
a regra \{ \} => Café tem confiança de 80%, isto é 80% das pessoas já bebem café. O fato delas tomarem chá diminue a probabilidade delas tomarem café!.
o lift mede o quanto não independentes são os 2 lados da regra A B => C D.
lift( A B => C D) = \frac{P(A B C D)}{P(A B) P(C D)}
onde P(A B) é a probabilidade de A B que é \#(A B)/n. lift =1 indica que A B e C D são independentes (o que usualmente não é nada interessante)
lift > 1 indica uma correlação positiva entre A B e C D.
Voce quer regras com lift >> 1 (ou muito perto do 0).
qual um valor minimo de lift?
há outras medidas de “quão interessante” é uma regra (um artigo que lista e compara 21 diferentes medidas )
Normalmente, para aplicações não automáticas de regras de associação, exige-se um suporte mínimo (para o itemset), uma confiança minima e talvez um lift mínimo.
Normalmente usa-se um algoritmo para achar itemsets frequentes (portanto que tem suporte mínimo) e destes itemsets gera-se as regras que tem confiança minima e talvez lift minimo.
há vários algoritmos para minerar itens frequentes: a priori, eclat, fp-grow
Pacote arules
implementa o algoritmo apriori para encontrar regras e itemsets frequentes
e o algoritmo eclat apenas para itemsets
ja contem alguns bancos de dados de transações
Mineração de sequências frequentes
Cada transação, além dos itens possui informação do cliente e da data de compra.
Voce quer obter regras de associação do tipo 70% dos clientes (confiança) que compram A, acabam comprando B em 2 meses.
O não-mito do Target e da filha grávida http://www.forbes.com/sites/kashmirhill/2012/02/16/how-target-figured-out-a-teen-girl-was-pregnant-before-her-father-did/ Isso poderia ter descoberto de mineração de sequências frequentes (mas o artigo dá a entender que o Target usou outras técnicas).
o pacote aruleSequences http://www.rdocumentation.org/packages/arulesSequences implementa um algoritmo de mineração de sequencias
Itemsets minimalmente infrequentes: