09. reglas de asociacion (probabilidades)

Tópicos de Data MiningReglas de Asociación (2)

Reinaldo González [email protected]

Universidad de Santiago de ChileFacultad de Ciencias

Departamento de Matemática y Ciencia de la Computación

Primer Semestre 2008

Reinaldo González S. (USACH) Reglas de Asociación Primer Semestre 2008 1 / 28

Contenidos

1 Introducción

2 Teoría de Probabilidades

3 Simulaciones


Introducción

Introducción

• Las reglas de asociación son una manera muy popular deexpresar patrones de datos de una base de datos. Estos patronespueden servir para conocer el comportamiento general delproblema que genera la base de datos, y de esta manera, setenga más información que pueda asistir en la toma dedecisiones.

• Por ejemplo, en un supermercado podemos conocer queproductos suelen comprarse conjuntamente, y así mejorar ladistribución de los productos en las estanterías. En un servidorweb podemos conocer cuales son los itinerarios más seguidospor los visitantes a las páginas web, y entonces, utilizar estainformación para estructurar las páginas web en el servidor.


Teoría de Probabilidades

Probabilidades para datos Transaccionales

Una base de datos transaccionales consiste en una serie detransacciones donde cada una de estas contiene un subconjunto deitems.

Analizaremos las transacciones en un intervalo de tiempo fijo t.Asumiremos que las transacciones ocurren aleatoriamente siguiendoun proceso Poisson con parámetro θ.

El numero de transacciones m en el intervalo de tiempo tienedistribución Poisson con parámetro θt:

P(M = m) =e−θt(θt)m

m!




Denotaremos los items que aparecen en la base de datos por

L = {l1, l2, ..., ln}

donde n es el numero de items. Asumiremos que cada item ocurreindependientemente del otro y cada item li ∈ L existe con unaprobabilidad fija pi de estar contenido en una transacción.

Cada transacción es el resultado de n intentos Bernoulliindependientes, donde las probabilidades de éxito están dadas por elvector

p = (p1, p2, ..., pn)




La siguiente tabla contiene la típica representación de una base dedatos binaria, donde cada columna representa un item, por otro lado,cada fila contiene una transacción

i1 i2 i3 · · · inp p1 p2 p3 · · · pn

Tr1 0 1 0 · · · 1Tr2 0 1 0 · · · 1Tr3 0 1 0 · · · 0Tr4 0 0 0 · · · 0

......

......

. . ....

Trm−1 1 1 0 · · · 1Trm 0 0 1 · · · 1

c c1 c2 c3 · · · cn




El valor 1 indica presencia y 0 indica ausencia de los correspondientesitems en la transacción. Adicionalmente, la probabilidad de éxito paracada item esta dada por una fila adicional llamada p y la fila llamada crepresenta el número de transacciones que contienen un itemcualquiera (o sea, es la suma de unos por columna).

Entonces, el número ci puede ser interpretado como una realizaciónde la variable aleatoria Ci. Bajo la condición de un numero fijo detransacciones m, esta variable sigue una distribución Binomial.

P(Ci = ci|M = m) =

(

m

ci

)

pci

i (1 − pi)m−ci




Sin embargo, dado un intervalo de tiempo fijo, el numero detransacciones no es fijo, la distribución marginal es:

P(Ci = ci) =

∞∑

m=ci

P(Ci = ci|M = m)P(M = m)

=

∞∑

m=ci

(

m

ci

)

pci

i (1 − pi)m−ci

e−θt(θt)m

m!

=e−θt(piθt)ci

ci!

∞∑

m=ci

((1 − p)θt)m−ci

(m − ci)!

=e−piθt(piθt)ci

ci!




Con esto es fácil mostrar que la distribución de probabilidad de cadaCi tiene una distribución Poisson con parámetro piθt.

Para simplificar la notación usaremos λi = piθt y se introducirá elvector de parámetros

λ = (λ1, λ2, ..., λn)

de la distribución Poisson para todos los items. Este vector deparámetros puede ser calculado del vector de probabilidades p yviceversa por la relación lineal

λ = pθt

donde θ es la intensidad con la cual las transacciones ocurren y t es elintervalo de tiempo.




Para una base de datos dada, el valor del parámetro θ y el vector deéxitos p (o alternativamente λ) son desconocidos, pero pueden serestimados de la base de datos.

La mejor estimación de θ es m/t. Una estimación simple para λ sepuede obtener usando la cantidad observada de cada item. Sinembargo esta estimación se vuelve de poca confianza cuando setiene poca cantidad de Transacciones.

Existen estimaciones mas sofisticadas, por ejemplo, DuMouchel yPregibon (2001) usan el hecho de que los parámetros estándistribuidos de acuerdo a una función de densidad paramétrica. Es poreso, que usan la mezcla de dos distribuciones Gamma como ladistribución para los parámetros.


Simulaciones

Simulaciones

Por simplicidad, asumiremos para la siguiente simulación que losparámetros λ son elegidos de una distribución Gamma.

Simularemos las cantidades ci, para n = 200 items diferentes en unperiodo t = 30 dias con una intensidad de θ = 300 transacciones pordía. Para la distribución Gamma, usaremos los parámetros k = 0,75 ya = 250.

Primero, elegimos el numero de transacciones m en un intervalo detiempo t de una distribución Poisson con parámetro θt.

> m <- rpois(1, theta*t)> m[1] 8966


Simulaciones

Simulaciones

Ahora, generaremos el vector de parámetro p. Para esto se generaránn valores para λi provenientes de una distribución Gamma. Luego, setransformarán dividiéndolos por el valor m.

> p <- sort(rgamma(n, shape=k, scale=a)/m, decreasing=TRUE)

Dado lo anterior, se pueden simular las transacciones en la base dedatos por medio de intentos Bernoulli, para cada uno de los n items. Elresultado de esto es una matriz de m × n llamada Tr.

> Tr <- matrix(rbinom(m*n, 1, p), ncol=n, byrow=TRUE)

Utilizando la matriz que contiene las transacciones, calculamos los ci

como la suma de cada una de las columnas, estos numerosrepresentaran la cantidad de transacciones en las cuales el itemaparece.

> c <- (apply(Tr, 2, sum))


Simulaciones

Simulaciones

Se puede calcular directamente el soporte de cada item. Recordemosque el soporte para un itemset Z es definido como

supp(Z) =cZ

m

donde cZ es la cantidad de veces que fue comprado el item Z y m esel numero de transacciones en la base de datos.

> supp1 <- c/m> summary(supp1)

Min. 1st Qu. Median Mean 3rd Qu. Max.0.000000 0.003932 0.013770 0.021410 0.031060 0.159900


Simulaciones

Simulaciones

Se puede calcular directamente el soporte de cada item. Recordemosque el soporte para un itemset Z es definido como

supp(Z) =cZ

m

donde cZ es la cantidad de veces que fue comprado el item Z y m esel numero de transacciones en la base de datos.

> supp1 <- c/m> summary(supp1)

Min. 1st Qu. Median Mean 3rd Qu. Max.0.000000 0.003932 0.013770 0.021410 0.031060 0.159900

El resumen estadístico muestra que hay una diferencia significativaentre la media y la mediana. Esto indicaría que se trata de unadistribución asimétrica. Esta distribución es mostrada en la siguientefigura.


Simulaciones

Simulaciones

Como es típico en datos transaccionales, solo unos pocos itemstienen un soporte relativamente alto, mientras que la mayoría de lositems aparecen más bien raras veces.

0 50 100 150 200

0.00

0.05

0.10

0.15

items

supp

ort

0.00 0.05 0.10 0.15

050

100

150

support minimo

item

s m

as fr

ecue

ntes


Simulaciones

Simulaciones

Ahora, extenderemos el proceso para la ocurrencia de dos itemset, locual corresponde a la ocurrencia de dos items en la mismatransacción. Los totales para dos itemset pueden ser representadospor una matriz de n × n donde cada celda ci,j contiene laco-ocurrencia para los items i y j. Esta matriz es simétrica conci,j = cj,i y la diagonal contiene los totales para los items individuales.

Se puede calcular los valores ci,j desde la base de datos, al contar elnúmero de transacciones para cada combinación de los items en lamatriz de co-ocurrencia (denotada por c2 en el código).

Descartaremos los valores de la diagonal dado que por definición unatransacción no puede tener el mismo item mas de una vez. Usandoesos valores podemos calcular el soporte para dos itemsets.


Simulaciones

Simulaciones

> c2 <- sapply(1:n, function(i)+ {+ apply(Tr[,i] & Tr[,1:n], 2, sum)+ })

> diag(c2) <- NA> supp2 <- c2/m

> summary(as.vector(supp2))Min. 1st Qu. Median Mean 3rd Qu. Max. NA’s

0.000e+00 0.000e+00 1.115e-04 4.536e-04 4.461e-04 1.751e-02 2.000e+02

El resumen estadístico para los soportes muestra que para muchascombinaciones de items se obtienen soportes muy pequeños, lo cuales propio de base de datos transaccionales.

En la siguiente figura, los ejes x e y representan los items y en el eje zse presenta el respectivo soporte. Los items son ordenadosdependiendo de su ocurrencia individual, partiendo por el item másfrecuente.


Simulaciones

Simulaciones

items

item

s

support


Simulaciones

Simulaciones

La confianza es definida como

C(X ⇒ Y ) =T (X ⇒ Y )

T (X)

donde X e Y son itemset disjuntos. La confianza se puede entendercomo la siguiente probabilidad P(Y |X). Con nuestros pares de itemspodemos generar reglas del tipo li ⇒ lj, donde i, j = 1, 2, ..., n y i 6= j.

Calculemos la confianza para las n(n − 1) posibles reglas en la basede datos

> conf2 <- supp2/supp1> summary(as.vector(conf2))

Min. 1st Qu. Median Mean 3rd Qu. Max. NA’s0.000e+00 0.000e+00 7.937e-03 2.121e-02 2.991e-02 1.000e+00 1.394e+03

> persp(conf2, expand=0.5, ticketype="detailed", border=0, shade=1,zlab="confidence", xlab="items", ylab="items")


Simulaciones

Simulaciones

El resumen estadístico muestra que los valores para la confianza songeneralmente bajos, lo cual refleja el hecho de que no hay asociaciónen la base. Sin embargo, el máximo indica que algunas reglas tienenconfianza uno.

La siguiente figura muestra que la confianza aumenta a medida que elitem X se vuelve más frecuente y el item Y es menos frecuente. Peroel hecho de que la confianza favorece claramente algunas reglas haceque la medida no sea apropiada cuando se quieren clasificar reglaspor su interés.


Simulaciones

Simulaciones

items

item

s

confidence


Simulaciones

Simulaciones

Típicamente las reglas extraídas usando el soporte mínimo (y laconfianza) son filtradas u ordenadas usando el valor del lift. La medidalift es definida para reglas de la forma X ⇒ Y como

L(X ⇒ Y ) =P(Y ∪ X)

P(X)P(Y )=

P(Y |X)

P(Y )

donde X e Y son itemset disjuntos. P(Y ∪ X) es la probabilidad quetodos los items en X e Y aparezcan en la transacción. El producto delas probabilidades individuales P(X)P(Y ) representa la probabilidadesperada de encontrar los items en X e Y juntos en la transacción siellos ocurren independientemente dados sus probabilidadesindividuales. Para calcular el lift, normalmente se utilizan los valoresde la confianza y soporte.

L(X ⇒ Y ) =C(X ⇒ Y )

T (Y )


Simulaciones

Simulaciones

Un valor de lift igual a 1 indica que los artículos co-ocurren en la basede datos como era lo esperado bajo independencia. Valores mayoresque uno indica que los items estan asociados. Para usos de control decomercialización generalmente se argumenta que si lift > 1 indicaproductos complementarios y si lift < 1 indica substitutos.

Para las reglas generadas de 2−itemsets, el lift puede ser calculadodirectamente de la confianza ya calculada y los valores del soporte.

> lift <- conf2/matrix(supp1, ncol=n, nrow=n, byrow=TRUE)> summary(as.vector(lift))

Min. 1st Qu. Median Mean 3rd Qu. Max. NA’s0.000 0.000 0.730 1.012 1.208 427.000 2558.000


Simulaciones

Simulaciones

De modo interesante, aunque los datos no contengan asociaciones, seencontraron muchos ceros y algunos valores sumamente altos de lift.

> length(which(lift>2))[1] 3418

Por ejemplo, 3418 reglas son encontradas con un lift mayor que 2. Parael diagnóstico visualizamos los valores de lift en la siguiente figura.

La cual muestra en la mayoría muchos ceros y los valores de lift másaltos son alcanzados para artículos ubicados en la parte derechaesquina trasera. Estos valores de lift son producidos por items confrecuencias muy bajas. El producto de las probabilidades para talesartículos raros está cerca del cero y si tales artículos co-ocurren juntosuna vez por casualidad, producirá un valor sumamente alto para el lift.


Simulaciones

Simulaciones

items

item

s

lift


Simulaciones

Simulaciones

Para la mayoría de las aplicaciones, se utiliza un soporte mínimo parafiltrar todos los itemset y también las reglas que no aparezcanfrecuentemente en la base de datos.Como ejemplo, desecharemos todos los 2−itemsets que no satisfacenun soporte mínimo del 0,1%.

> min_supp <- 0.001> length(lift[supp2 >= min_supp])[1] 5926> summary(lift[supp2 >= min_supp])

Min. 1st Qu. Median Mean 3rd Qu. Max. NA’s0.3863 0.9195 1.0620 1.1230 1.2570 3.6730 200.0000

> lift[supp2 < min_supp] <- 1> length(which(lift>2))[1] 110


Simulaciones

Simulaciones

El soporte requerido deja 5926 reglas. El resumen estadístico muestraque las reglas más frecuentes tienen ahora un valor de lift alrededor 1,pero hay todavía 110 reglas con valores del lif t mayores que 2.

El siguiente gráfico, claramente muestra la tendencia del lift deproducir valores más altos para reglas que contienen uno o dosartículos menos frecuentes. Esto indica que la medida de lift funcionamal para filtrar el ruido aleatorio en datos transaccionalesespecialmente si estamos interesados en artículos relativamenteraros.

Además, si el lift es usado para clasificar reglas descubiertas, hay unatendencia sistemática hacia el favoritismo de reglas con artículosmenos frecuentes.


Simulaciones

Simulaciones

items

item

s

lift


09. reglas de asociacion (probabilidades)

Documents