Algoritmos de Asociación

TRABAJO DE INTELIGENCIA ARTIFICAL
ALGORITMOS DE ASOCIACIN
INTEGRANTES:
MARIO BARRIOS PACHECO
GUSTAVO RODRGUEZ ROMERO
PRESENTADO A:
JOHN ARRIETA ARRIETA
UNIVERSIDAD DE CARTAGENA
JUNIO DE 2015
Qu es un algoritmo de minera de datos?

Es un conjunto de clculos y reglas heursticas que permite crear un modelo de
minera de datos a partir de los datos.
Para crear un modelo, el algoritmo analiza primero los datos proporcionados en
busca de tipos especficos de patrones o tendencias.
El algoritmo usa los resultados de este anlisis para definir los parmetros ptimos
para la creacin del modelo de minera de datos
El modelo de minera de datos crea un algoritmo a partir de los datos, puede tomar
diversas formas incluyendo:
Un conjunto de clsteres que describe cmo se relacionan los casos de un

conjunto de datos.
Un rbol de decisin que predice un resultado y que describe cmo afectan
a este los distintos criterios.
Un modelo matemtico que predice las ventas.
Un conjunto de reglas que describen cmo se agrupan los productos en
una transaccin y las probabilidades de que dichos productos se adquieran
juntos.
Algoritmos de asociacin
Son algoritmos que buscan correlaciones entre diferentes atributos de un conjunto
de datos. La aplicacin ms comn de esta clase de algoritmo es la creacin de
reglas de asociacin.
Los algorimos de este tipo son:
A priori
Eclat
Partition
FP-Grow
Algoritmo A priori
El algoritmo tiene dos pasos: el paso JOIN(junta) y el paso PRUNE(optimizacin).
El paso JOIN consiste en calcular los conjuntos de K tems frecuentes, y el paso
PRUNE se encarga de depurar aquellos conjuntos de K tems que incluyen algn
K-1conjuntos de tems no frecuentes dentro o que no ha alcanzado el nivel de
soporte mnimo reduciendo la cantidad de K tems frecuentes, optimizando as el
proceso.
Funcionamiento algoritmo a priori
Ejemplo
Un gran supermercado lleva un seguimiento de los datos de ventas de la unidad
de mantenimiento de stock (SKU) para cada artculo, y por lo tanto es capaz de
saber qu artculos son comprados usualmente juntos. A priori es una forma
moderadamente eficaz de construir una lista de pares frecuentes comprado el
objeto de estos datos. La base de datos de transacciones consisten en los
conjuntos {1,2,3,4}, {1,2,3,4,5}, {2,3,4}, {2,3,5}, {1,2,4}, {1,3,4}, {2,3,4 , 5}, {1,3,4,5},
{3,4,5}, {1,2,3,5}. cada nmero de corresponde a un producto como "mantequilla"
o "agua". El primer paso de Apriori es contar las frecuencias, llamado los soportes,
de cada artculo miembro por separado:
Item
Support
Podemos definir un nivel de soporte mnimo para calificar como "frecuente", que
depende del contexto. Para este caso, dejar que el min support = 4. Por lo tanto,
todos son frecuentes. El siguiente paso es generar una lista de todos los 2 pares
de los elementos frecuentes. Haban cualquiera de los puntos anteriores no han
sido frecuentes, no habran sido incluidos como posible miembro de posibles
pares de 2 artculos. De esta manera, Apriori poda el rbol de todos los conjuntos
posibles. En la prxima paso que nuevamente seleccionamos slo estos
elementos (ahora 2 pares son elementos) que son frecuentes (los pares escritas
en negritatexto):
Item
support
{1,2}
{1,3}
{1,4}
{1,5}
{2,3}
{2,4}
{2,5}
{3,4}
{3,5}
{4,5}
Generamos la lista de los 3-triples de los elementos frecuentes (conectando par

frecuente con cada elemento frecuente).
Item
Support
{1,2,4}
{2,3,4}
{2,3,5}
{3,4,5}
El algoritmo terminar aqu porque el par {2, 3, 4, 5} generado en el siguiente paso

no tiene el apoyo deseado. Ahora vamos a aplicar el mismo algoritmo en el mismo
conjunto de datos teniendo en cuenta que el apoyo es min 5. Obtener los
siguientes resultados:
Item
Support
Item
support
{1,2}
{1,3}
{1,4}
{1,5}
{2,3}
{2,4}
{2,5}
{3,4}
{3,5}
{4,5}
El algoritmo termina aqu, porque ninguno de los 3-triples generados en el paso 3

tiene el apoyo deseado.
Algoritmo Eclat
El algoritmo Eclat se utiliza para realizar la minera de conjunto de elementos. Esto
nos permite encontrar patrones frecuentes en los datos como por ejemplo, si un
consumidor compra leche, tambin compra pan. Este tipo de patrn se llama
reglas de asociacin y se utiliza en muchos dominios de aplicacin.
La idea bsica del algoritmo Eclat es utilizar intersecciones en el conjunto de datos
para calcular el soporte de un conjunto de elementos candidatos para evitar la
generacin de subconjuntos que no existen en el rbol de prefijo.
Se basan en realizar un agrupamiento (clustering) entre los tems
para aproximarse al conjunto de tems frecuentes maximales y luego
emplean algoritmos eficientes para generar los tems frecuentes contenidos en
cada grupo. Para el agrupamiento proponen dos mtodos que son
empleados despus de descubrir los conjuntos frecuentes de dos elementos:
el primero, por clases de equivalencia: esta tcnica agrupa los itemsets que
tienen el primer tem igual. El segundo, por la bsqueda de cliques
maximales: se genera un grafo de equivalencia cuyos nodos son los tems,

y los arcos conectan los tems de los itemsets frecuentes, se agrupan los tems
por aquellos que forman cliques maximales
Funcionamiento algoritmo Eclat
Los cliques maximales generan conjuntos maximales potencialmente frecuentes

ms refinados, pero su clculo es computacionalmente ms costos.
Para cada conjunto maximal potencialmente frecuente se requiere ahora un
mtodo de recorrido de bsqueda para encontrar los conjuntos frecuentes. Dos de
estos mtodos son:
Trabaja de manera similar al algoritmo A priori pero comenzando con los

2-itemsets frecuentes
Recorrido hbrido top-down/buttom-up: en la fase top-down ordena los
elementos 2-itemsets frecuentes del cluster en orden descendiente de
su soporte, y comenzando por un elemento, extender el itemset con un
tem cada vez hasta que el itemset se vuelva infrecuente. En la fase
buttom-up, se trabaja de manera similar que en A priori pero combinando
los elementos que no fueron aglutinados en la primera fase con los
elementos del conjunto inicial
Por ejemplo, para el conjunto maximal potencialmente frecuente {1, 2, 3, 4, 5, 6}

estos mtodos trabajara de la siguiente forma.
Con la primera de las tcnicas se generan los conjuntos de tems frecuentes, con
la segunda se generan slo los conjuntos frecuentes maximales, los restantes
conjuntos frecuentes son subconjuntos de estos.
Algoritmo Partition
Este algoritmo propone fraccionar la base de datos en tantas partes como fueren
necesarias para que todas las transacciones en cada particin estn en la
memoria (Savesere, Omiecinski, y Navatie, 1995). En contraste con los vistos
hasta el momento, este algoritmo recorre la base de datos slo dos veces. En la
primera, cada particin es minada independientemente para encontrar los
conjuntos de tems frecuentes en la particin y luego se mezclan estos para
generar el total de los conjuntos de tems candidatos.
Muchos de estos pueden ser falsos positivos, pero ninguno falso negativo
(notemos que si existen m particiones, para que un itemset tenga soporte s debe
poseer un soporte no menor que s/m al menos en una de las m particiones, los
conjuntos candidatos sern por tanto los que cumplan esta condicin). En la
segunda pasada se cuenta la ocurrencia de cada candidato, aquellos cuyo soporte
es mayor que el mnimo soporte especificado se retienen como conjuntos
frecuentes. Este algoritmo emplea el mecanismo de interseccin entre conjuntos
para determinar su soporte, en este caso cada tem en una particin mantiene la
lista de los identificadores de las transacciones que contienen a dicho tem.

Algoritmos de Asociación

Cargado por

Copyright:

Formatos disponibles

Algoritmos de Asociación

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Algoritmos de Asociación

Cargado por

Copyright:

Formatos disponibles

TRABAJO DE INTELIGENCIA ARTIFICAL

Qu es un algoritmo de minera de datos?

Un conjunto de clsteres que describe cmo se relacionan los casos de un

Funcionamiento algoritmo a priori

Generamos la lista de los 3-triples de los elementos frecuentes (conectando par

El algoritmo terminar aqu porque el par {2, 3, 4, 5} generado en el siguiente paso

El algoritmo termina aqu, porque ninguno de los 3-triples generados en el paso 3

maximales: se genera un grafo de equivalencia cuyos nodos son los tems,

Funcionamiento algoritmo Eclat

Los cliques maximales generan conjuntos maximales potencialmente frecuentes

Trabaja de manera similar al algoritmo A priori pero comenzando con los

Por ejemplo, para el conjunto maximal potencialmente frecuente {1, 2, 3, 4, 5, 6}

También podría gustarte