Download Motivación - DCC - Universidad de Chile

Universidad de Chile
Facultad de Ciencias Físicas y Matemáticas
Departamento de Ciencias de la Computación
Búsqueda de patrones frecuentes en un
conjunto de datos mediante el algoritmo
FPGrowth.
Autor:
Andrés Villavicencio.
Motivación.
En el mundo del retail, siempre se ha buscado ofrecer a los consumidores los productos
que necesiten. En la vida real, se encuentran cientos de productos que por sí solos, no son
necesarios, pero que adquieren importancia cuando están acompañados de otros
productos. Un ejemplo clásico sería la necesidad de llevar una bebida cola al comprar una
botella de pisco, productos a los que además se puede añadir maní o vasos plásticos. Las
empresas aprovechan estas relaciones al momento de realizar promociones y definir el
posicionamiento de los productos en sus estantes. Si bien es sabido que esta práctica no
atrae un mayor número de clientes a un local, logra que el valor de la compra sea mayor
en cada visita.
La dificultad de esta técnica es descubrir las relaciones que hay entre productos
complementarios. Para enfrentarse a este problema, las empresas de retail realizan
búsquedas en la historia de ventas de sus negocios, analizando qué patrones de compra
son los más frecuentes. Por ejemplo en Amazon.com le es indicado al visitante que
porcentaje de la gente que compró el producto A llevo además el producto B. El
problema de la búsqueda de patrones frecuentes está relacionado con el volumen de datos
a procesar. Esto pues una base de datos de venta fácilmente puede incluir 100 millones de
registros y decenas de miles de ítemes, comprados en millones de carros o transacciones
(transacción o carro se refiere a todos los ítemes que se llevaron en una instancia de
compra). Para resolver este problema se han desarrollado dos algoritmos: el algoritmo
APRIORI que basa su funcionamiento en múltiples lecturas de los datos y rápida
eliminación de candidatos de bajo soporte, y FPGrowth que almacena la información en
una estructura altamente comprimida conocida como FPTree. Es el algoritmo FPGrowth
el que se revisará en el presente documento.
Estructura Frequent Pattern Tree (FPTree).
Árbol FP.
El objetivo de un árbol FP es almacenar de manera altamente comprimida un conjunto de
transacciones, utilizando una estrategia similar a Patricia Tries (Un algoritmo de
compresión de conjuntos de Strings basada en uso de prefijos).
El Árbol FP no es más que una serie de listas de Nodos FP (una lista por cada tipo de
ítem presente en las transacciones), los cuales están vinculados entre sí en forma de árbol
(Fig 1).
Figura 1: Árbol FP.
El supuesto básico de la creación de un árbol FP es que los ítemes en una transacción
vienen ordenados de forma consistente, es decir, dado un ítem A y un ítem B, si A
precede a B en algún esquema de ordenamiento, entonces A siempre estará antes que B
en las transacciones (se ha comprobado en la práctica, que los mejores desempeños se
obtienen ordenando por soporte de los ítemes con A precede a B, si soporte de A >
soporte de B). De no cumplirse esto no habrá compresión de los datos mediante el uso de
prefijos y el podado no funcionará (El podado y su utilidad se verá más adelante).
La única información extraída de manera directa de un árbol FP es el soporte de los
ítemes contenidos en él. Esto se logra sumando los conteos de los ítemes que hay en cada
lista enlazada (Ver sección Nodo FP). En el diagrama anterior este total se muestra en las
cajas a la izquierda del árbol. Para obtener los patrones contenidos en un árbol FP se debe
usar la técnica de podado, descrita más adelante.
Nodo FP.
El Nodo FP es un híbrido entre un nodo de árbol y un nodo de lista enlazada. Hay
variados acercamientos para definir la estructura de un nodo FP. Las variaciones más
frecuentes están dadas por la estrategia de conexión entre nodos padre e hijo y si la lista
es de enlace simple o de doble enlace.
A continuación vemos un nodo FP en su forma más frecuente:
class FPNode {
//Identificador del nodo.
int id;
//Información relevante.
int item;
int conteo;
//Enlace padre-hijo.
FPNode padre;
//Enlace tipo lista.
FPNode siguiente;
}
Como se puede apreciar, cada nodo guarda dos campos de información: el identificador
de un ítem y el número de transacciones en que aparece, además de un puntero al padre y
el nodo siguiente. La principal ventaja de este nodo es su tamaño: 20 bytes. Un árbol FP
generado a partir de un conjunto de transacciones puede llegar sin problemas a contener
10 millones de nodos, lo que con el nodo mencionado, llevaría a un uso de memoria de
200 MB. Su principal desventaja es que se requieren pasos adicionales de procesamiento
de los datos iniciales para compensar la ausencia de punteros de padre a hijos.
A continuación vemos una posible variante del Nodo FP.
public class FPNode {
//Identificador del nodo.
int id;
//Información relevante.
int item;
int conteo;
//Enlace padre-hijo.
ListaEnlazada<FPNode> hijos;
//Enlace tipo lista.
FPNode siguiente;
FPNode anterior;
}
Esta variante incluye los dos cambios más comunes: punteros de padre a hijo (en vez de
hijo a padre) y lista de doble enlace para la relación siguiente-anterior. Entre las ventajas
de este tipo de nodo podemos señalar que: el árbol formado puede ser alimentado con las
transacciones prácticamente sin procesar, la existencia de un mecanismo que permite
acceder a los hijos y que la lista de doble enlace ayuda a eliminar nodos de forma más
rápida y sencilla (un caso frecuente de eliminación de nodos se da cuando un conjunto de
transacciones puede incluir devoluciones). Las desventajas de este esquema son: el
acceso a los hijos de un nodo (Es lento. Hay que iterar a través de la lista enlazada hijos)
y el tamaño del nodo crece considerablemente, lo que puede llevar a problemas de
memoria.
Podado.
El podado de un árbol FP permite, dado un ítem cualquiera de éste, encontrar un nuevo
árbol FP que represente las transacciones que comparten los antecesores del ítem con
éste.
Antes de explicar el algoritmo, veamos un ejemplo que muestre su utilidad. Dado el
siguiente árbol FP (Fig 2):
Figura 2: Árbol FP inicial.
Si podamos con C como parámetro obtendremos (Fig 3):
Figura 3: Árbol podado por C.
Esto se interpreta como que de las cinco veces que aparece el ítem C, aparece junto con B
cuatro veces y junto con A tres veces. Si podamos nuevamente con B como parámetro
obtendremos (Fig 4):
Figura 4: Árbol podado por C y por B.
Esto se interpreta de la siguiente manera: de las cuatro veces que aparece el patrón (C B)
tres de ellas también incluyen A, en otras palabras el patrón (C B A) tiene una frecuencia
de tres. Es importante entender que estos no son la totalidad de los patrones en los que
participa C, solo representan los patrones compuestos por C y sus antecesores.
El algoritmo para podar el árbol es el siguiente:
public FPTree podar(item, FPTree original){
FPTree resultado = new FPTree();
for(FPNode nodo =original.primerNodo(item);item != null; nodo=nodo.siguiente){
colgarRama(nodo.padre,nodo.cuenta,resultado);
}
retornar resultado;
}
public FPNode colgarRama(FPnode nodo, int cuenta, FPTree resultado){
if(nodo == null){
return nodo;
}
FPNode padre=colgarRama(nodo.padre, cuenta, resultado);
return resultado.addNodo(padre, nodo.id, nodo.item,cuenta);
}
El método podar itera por los nodos de la lista del ítem por el cual se está podando y
entrega al método colgarRama, los nodos padres de estos y el conteo del nodo. El conteo
del nodo es importante, pues los ítemes que aparecen en los nodos ancestros sólo
aparecen junto con el ítem de podado, una cantidad de transacciones igual al conteo del
nodo desde el que se llama inicialmente al método colgarRama en el método podar (esto
es porque el conteo del nodo es igual al número de transacciones que comparte con sus
ancestros).
Veamos un ejemplo del colgado de una rama, partiendo con el siguiente árbol (Fig 5):
Figura 5: Árbol a podar.
Si podamos por E, el primer llamado a colgarRama atravesaría los siguientes nodos (Fig
6):
Figura 6: Nodos seleccionados en primera llamada recursiva a colgarRama.
El árbol resultado quedaría de la siguiente forma (Fig 7):
Figura 7: Árbol resultado, después de primera llamada recursiva.
Es importante que el método addNodo pueda reconocer cuando se debe actualizar un
nodo, en vez de crear uno nuevo (para ello se usa el campo id de la estructura FPNode)
como se aprecia en la segunda ejecución del método colgarRama, la cual revisa tres
nodos que ya fueron agregados al árbol resultado (Fig 8).
Figura 8: Nodos seleccionado en segunda llamada recursiva.
El árbol “resultado” quedaría de la siguiente forma al finalizar este paso (Fig 9):
Figura 9: Árbol resultado después de segunda llamada recursiva.
No se generan nuevos nodos sino que se actualizan los totales de los nodos ya existentes.
Es posible realizar un podado en el cual cada rama es independiente de las otras,
manteniendo el resultado, pero esto implica perder gran parte de la compresión del
conjunto de transacciones, que es la principal ventaja de esta estructura.
Una vez completado el algoritmo retornaría el siguiente árbol (Fig 10):
Figura 10: Árbol resultado final.
Algoritmo FPGrowth.
El algoritmo FPGrowth es el proceso de obtención de todos los patrones frecuentes de un
conjunto de transacciones, mediante la generación del árbol FP que comprime las
transacciones y el podado recursivo de éste.
Creación del Árbol FP inicial.
La generación del árbol FP inicial es probablemente la parte más complicada del
algoritmo. Esta se puede dividir en dos fases:
Procesamiento Inicial de Datos.
En esta fase, transformamos el conjunto de transacciones desde el formato usado en la
mayoría de las bases de datos transaccionales, esto es, pares ordenados (transacción,
ítem), a un formato útil para el proceso de llenado de datos, donde cada transacción es un
arreglo ordenado de ítemes, y los datos se guardan en un arreglo ordenado de
transacciones (normalmente de manera lexicográfica).
Los pasos del procesamiento son los siguientes:
1. Calcular soportes de los ítemes: Se calcula la cantidad de veces que aparece
cada ítem en el conjunto.
2. Eliminar ítemes con soporte bajo: Se eliminan las entradas de los ítemes que no
cumplen con el soporte mínimo (si un ítem no cumple con él, no puede ser parte
de un patrón que lo cumpla). Esto se hace con la intención de lograr un llenado
más rápido del árbol.
3. Aplanar transacciones: Se transforman los pares ordenados (transacción, ítem)
en arreglos de ítemes. El identificador de la transacción se descarta.
4. Ordenar transacciones: Se ordenan las transacciones de manera lexicográfica.
Se puede ver un ejemplo claro de cómo se efectúan estos pasos y como transforman
los datos en las applets asociadas a este documento.
Llenado de Árbol FP.
El algoritmo de llenado del Árbol es el siguiente:
public void generarNodos(FPNode padre, int profundidad, Rango rango,
int[][] datos){
while(hayDatos(rango)){
(nuevo_rango, item)= buscar(profundidad, rango, datos);
nNodo=crearNodo(padre,item,rango.size());
generarNodos(nNodo,profundidad+1,nuevo_rango,datos);
}
}
public FPNode crearNodo(FPNode padre, String item, int conteo){
nodo=new FPNode(padre, item, conteo);
lista[item].ultimo().sgte=nodo;
}
Es importante entender que generarNodos y crearNodo son métodos del Árbol FP, es
decir, la información que se genere en ellos será agregada inmediatamente a la instancia
del árbol. El método crearNodo envuelve el proceso de generación de Nodos FP y se
preocupa que cada nodo creado sea añadido a la lista enlazada correspondiente.
El método generarNodos particiona los datos a cada nivel de profundidad y genera el
nodo correspondiente. La finalidad de esto se puede ver en el siguiente ejemplo:
Dado los siguientes datos (Fig 11):
Figura 11: Datos de entrada.
La primera partición elegida seria la siguiente (Fig 12):
Figura 12: Primera partición.
El estado del árbol después de agregar el nodo correspondiente (padre nulo, ítem A,
conteo 3) sería (Fig 13):
Figura 13: Árbol después de la primera partición.
Repitiendo el proceso 3 veces más tenemos (Fig 14):
Figura 14: Cuarta partición.
Después de agregar los nodos correspondientes el árbol es (Fig 15):
Figura 15: Árbol después de cuarta partición.
Repitiendo otras 3 veces (agregamos los nodos E y F con un conteo de 1) y luego
continuamos por la siguiente rama del árbol (Fig 16):
Figura 16: Séptima partición.
Agregando este nodo el árbol queda (Fig 17):
Figura 17: Árbol después de séptima partición.
Se continúa el proceso hasta acabar los datos. El objetivo de esta forma de llenado del
Árbol FP es pasar por cada nodo una sola vez (solo al momento de su creación), dado que
las posibles implementaciones de los Nodos FP hacen costoso encontrar un nodo
particular para actualizar su información (por ejemplo, el nodo E, cuyos antecesores sean
A, B y C).
Podado recursivo.
El algoritmo de podado del árbol es el siguiente:
public void buscarPatrones(String patron,int soporte_minimo, FPTree
patrones){
for(<Cada item contenido en el arbol>){
if(item.soporte()>soporte_minimo){
patrones.add(patron+" "item+" "+item.soporte());
buscarPatrones(patron+" "+item,soporte_minimo,
arbol.podar(item),patrones);
}
}
}
arbol,
Lista
En la primera llamada al método, la variable patrón es un String vacío y la variable
patrones es una lista vacía. El método agregará a la lista cada patrón+ítem que cumpla
con el soporte mínimo y se llamará a sí mismo, con el ítem agregado al patrón inicial,
además de entregar un árbol podado según el ítem correspondiente. Como apreciamos en
la sección podado esto permite encontrar los patrones frecuentes en que participa un ítem
y sus antecesores. Por el hecho de aplicar este algoritmo sobre todos los ítemes del árbol
obtendremos todos los patrones frecuentes en éste.
Compilación y Ejecución de Applets de Ejemplo.
El presente documento va acompañado del archivo fpgrowth.zip, el cual contiene el
código fuente de las applets de ejemplo.
Compilación
Se debe descomprimir el archivo fpgrowth.zip.:
[user@host:~]% unzip fpgrowth.zip
Al descomprimir se deben crear los siguientes directorios:
fpgrowth/
fpgrowth/html/
fpgrowth/bin/
fpgrowth/src/
Luego, se deben compilar los archivos fuente, contenidos en el directorio fpgrowth/src/ y
el resultado debe ser dejado en el directorio fpgrowth/bin/ (Para compilar se requiere JDK
1.4.2):
[user@host:~]% cd fpgrowth
[user@host:~/fpgrowth/]% javac -nowarn -d bin src/*
Una vez realizados estos pasos el programa esta listo para ser ejecutado.
Ejecución.
Para ejecutar basta con abrir el archivo fpgrowth/html/fpgrowth.html en un navegador que
tenga instalado el plugin de Java (preferentemente versión 1.4.2 o superior).