Aprendizaje de reglas de asociación

Aprendizaje de reglas de asociación es un método popular y bien investigado para descubrir interesantes relaciones entre variables en grandes bases de datos. Se pretende identificar reglas fuertes descubiertas en bases de datos utilizando diferentes medidas de interés. Basado en el concepto de reglas fuertes, Rakesh Agrawal et al. introdujo reglas de Asociación para descubrir las regularidades entre productos de datos de transacciones a gran escala grabados por punto de venta Sistemas (POS) en los supermercados. Por ejemplo, la regla $\{\mathrm{onions, potatoes}\} \Rightarrow \{\mathrm{burger}\}$ encontrado en las ventas de datos de un supermercado indicaría que si un cliente compra las cebollas y papas juntos, él o ella es probable que también comprar carne de la hamburguesa. Dicha información puede utilizarse como base para las decisiones sobre las actividades de marketing tales como, por ejemplo, promocional fijación de precios o colocaciones de productos. Además del ejemplo anterior de Análisis de la cesta de la compra las reglas de asociación se emplean hoy en muchas áreas de aplicación incluyendo Minería de uso Web, detección de intrusos, Producción continua, y Bioinformática. En contraste con minería de secuencia, aprendizaje de reglas de asociación típicamente no tiene en cuenta el orden de elementos dentro de una transacción o a través de las transacciones.

Definición

Base de datos de ejemplo con los 4 artículos y 5 transacciones

Identificador de la transacción	leche	pan	mantequilla	cerveza
1	1	1	0	0
2	0	0	1	0
3	0	0	0	1
4	1	1	1	0
5	0	1	0	0

Siguiendo la definición original de Agrawal et al. el problema de la explotación minera de regla de asociación se define como: dejar $I=\{i_1, i_2,\ldots,i_n\}$ ser un conjunto de $n$ atributos binarios llamados artículos. Dejar $D = \{t_1, t_2, \ldots, t_m\}$ ser un conjunto de transacciones llamado el base de datos. Cada transacción en $D$ tiene un identificador de transacción y contiene un subconjunto de los elementos $I$. A regla se define como una implicación de la forma $X \Rightarrow Y$ donde $X, Y \subseteq I$ y $X \cap Y = \emptyset$. Los conjuntos de artículos (para corto itemsets) $X$ y $Y$ se llaman antecedente (lado izquierdo o LHS) y consecuente (mano derecha o RHS) de la regla respectivamente.

Para ilustrar los conceptos, utilizamos un pequeño ejemplo del dominio de supermercado. Es el conjunto de ítems $I= \{\mathrm{milk, bread, butter, beer}\}$ y una pequeña base de datos que contiene los elementos (1 códigos presencia y 0 ausencia de un elemento en una transacción) se muestra en la tabla a la derecha. Podría ser una regla de ejemplo para el supermercado $\{\mathrm{butter, bread}\} \Rightarrow \{\mathrm{milk}\}$ lo que significa que si se compran pan y mantequilla, los clientes también compran leche.

Nota: este ejemplo es extremadamente pequeño. En aplicaciones prácticas, una regla necesita un apoyo de varias cien transacciones antes de que pueda ser considerado estadísticamente significativo, y bases de datos contienen a menudo miles o millones de transacciones.

Conceptos útiles

Para seleccionar reglas interesantes del conjunto de todas las reglas posibles, pueden utilizarse las restricciones sobre diversas medidas de importancia e interés. Las limitaciones más conocidas son los umbrales mínimos de apoyo y confianza.

• El apoyo $\mathrm{supp}(X)$ de un conjunto de ítems $X$ se define como la proporción de las transacciones en el conjunto de datos que contienen el conjunto de ítems. En la base de datos de ejemplo, el conjunto de ítems $\{\mathrm{milk, bread, butter}\}$ cuenta con un apoyo de $1/5=0.2$ puesto que ocurre en el 20% de todas las transacciones (operaciones en 1 de cada 5).

• El confianza de una regla se define $\mathrm{conf}(X\Rightarrow Y) = \mathrm{supp}(X \cup Y) / \mathrm{supp}(X)$. Por ejemplo, la regla $\{\mathrm{butter, bread}\} \Rightarrow \{\mathrm{milk}\}$ tiene una confianza de $0.2/0.2=1.0$ en la base de datos, lo que significa que para el 100% de las transacciones que contengan mantequilla la regla es correcta (100% de las veces que un cliente compra mantequilla y pan, la leche es comprado también). Ten cuidado al leer la expresión: supp(X∪Y) significa "soporte para las ocurrencias de transacciones donde X e Y aparecen", no"soporte para las ocurrencias de transacciones donde Ya sea X o Y aparece", la última interpretación que se deriven porque Unión conjunto es equivalente a disyunción lógica. El argumento de $\mathrm{supp}()$ es un conjunto de condiciones previas y así llega a ser más restrictiva que crece (en lugar de más inclusivo).

• Confianza puede interpretarse como una estimación de la probabilidad $P(Y|X)$, la probabilidad de encontrar el lado derecho de la regla en las transacciones con la condición de que estas transacciones también contienen la LHS.

• El Levante de una regla se define como $\mathrm{lift}(X\Rightarrow Y) = \frac{ \mathrm{supp}(X \cup Y)}{ \mathrm{supp}(X) \times \mathrm{supp}(Y) }$ o la relación entre el apoyo observado para que esperar si X e Y se independiente. La regla $\{\mathrm{milk, bread}\} \Rightarrow \{\mathrm{butter}\}$ tiene una elevación de $\frac{0.2}{0.4 \times 0.4} = 1.25$.

• El convicción de una regla se define como $\mathrm{conv}(X\Rightarrow Y) =\frac{ 1 - \mathrm{supp}(Y) }{ 1 - \mathrm{conf}(X\Rightarrow Y)}$. La regla $\{\mathrm{milk, bread}\} \Rightarrow \{\mathrm{butter}\}$ tiene una convicción de $\frac{1 - 0.4}{1 - .5} = 1.2$y puede ser interpretado como el cociente de la frecuencia prevista que X ocurre sin Y (es decir, la frecuencia que la regla hace una predicción incorrecta) si X e Y son independientes dividido por la frecuencia observada de predicciones incorrectas. En este ejemplo, el valor de convicción de 1.2 muestra que la regla $\{\mathrm{milk, bread}\} \Rightarrow \{\mathrm{butter}\}$ sería incorrecto 20% más a menudo (1,2 veces más a menudo), si la asociación entre X e Y fue puramente azar.

Proceso

Conjunto de ítems frecuentes enrejado, donde el color de la caja indica cuántas transacciones contienen la combinación de los elementos. Tenga en cuenta que los niveles inferiores del enrejado pueden contener como máximo el número mínimo de artículos de sus padres; por ejemplo {ac} puede tener solamente a lo más $min(a,c)$ artículos. Esto se llama el propiedad de cierre hacia abajo.

Las reglas de asociación son generalmente requeridas para satisfacer un apoyo mínimo especificado por el usuario y una confianza mínima especificada por el usuario al mismo tiempo. Generación de reglas de asociación se divide generalmente en dos pasos separados:

1. En primer lugar, mínimo apoyo se aplica para encontrar todo itemsets frecuentes en una base de datos.
2. En segundo lugar, estos itemsets frecuentes y la restricción mínima confianza se utilizan para formar las reglas.

Mientras que el segundo paso es sencillo, el primer paso necesita más atención.

Encontrando todos itemsets frecuentes en una base de datos es difícil puesto que implica buscar todos itemsets posibles (artículo combinaciones). El conjunto de itemsets posible es la conjunto potencia sobre $I$ y tiene tamaño $2^n-1$ (excluyendo el conjunto vacío, que no es un conjunto de ítems válido). Aunque el tamaño de la powerset crece exponencialmente el número de artículos $n$ en $I$, búsqueda eficiente es posible utilizando el propiedad de cierre hacia abajo de apoyo (también llamado anti-moniticidad) que garantiza que por un conjunto de ítems frecuente, todos sus subconjuntos son también frecuentes y así para un conjunto de ítems infrecuente, todos sus súper series también deben ser infrecuentes. Aprovechando esta propiedad, algoritmos eficientes (por ejemplo, Apriori y Eclat) puede encontrar todo itemsets frecuentes.

Historia

Popularizó el concepto de reglas de asociación particularmente debido al artículo 1993 de Agrawal et al., que ha adquirido más de 6.000 citas según Google Scholar, a partir de marzo de 2008, y es así uno de los artículos más citados en el campo de la minería de datos. Sin embargo, es posible que ahora se llama "reglas de asociación" es similar a lo que aparece en el documento de 1966 en GUHA, desarrolló un método de minería de datos generales por Petr Hájek et al.

Medidas alternativas de interés

Además de las medidas de confianza, otras de interestingness para las reglas se han propuesto. Algunas medidas populares son:

• Todo-confianza

• Fuerza colectiva

• Convicción

• Apalancamiento

• Elevación (originalmente llamado interés)

Puede encontrar una definición de estas medidas aquí. Varias medidas más se presentan y se comparan por Tan et al. Buscando técnicas que se pueden modelar lo que el usuario conoce (y utilizar estos modelos como medidas de interés) es actualmente una tendencia activa de investigación bajo el nombre de "Interestingness subjetiva".

Asociaciones estadísticamente sonidas

Una limitación del enfoque estándar para descubrir las asociaciones es que mediante la búsqueda de un número masivo de posibles asociaciones en busca de colecciones de objetos que parecen estar asociados, hay un gran riesgo de encontrar muchas asociaciones espurias. Estas son las colecciones de elementos que co-ocurren con frecuencia inesperada en los datos, pero hacen sólo por casualidad. Por ejemplo, supongamos que estamos considerando una colección de 10.000 artículos y buscando las reglas que contiene dos elementos en el lado izquierdo y 1 punto en el lado derecho. Hay aproximadamente 1.000.000.000.000 dichas normas. Si aplicamos una prueba estadística de independencia con un nivel de significancia de 0.05 significa que hay sólo un 5% de probabilidades de aceptar una regla si no hay ninguna asociación. Si suponemos que hay no hay asociaciones, sin embargo habrá que esperar a encontrar las reglas de 50,000,000,000. Descubrimiento de asociación estadísticamente sonido controla este riesgo, en la mayoría de los casos reduce el riesgo de encontrar cualquier asociaciones espurias a un nivel de significancia especificado por el usuario.

Algoritmos

Muchos algoritmos para generar las reglas de asociación se presentaron con el tiempo.

Algunos algoritmos conocidos son Apriori, Eclat y FP-Growth, pero ellos sólo hacen la mitad del trabajo, puesto que son algoritmos de minería itemsets frecuentes. Otro paso que debe hacerse después de generar las reglas de itemsets frecuentes encontrados en una base de datos.

Algoritmo Apriori

Artículo principal: Algoritmo Apriori

Apriori es el algoritmo más conocido a las reglas de Asociación de la mina. Se utiliza una estrategia de búsqueda en amplitud para contar el apoyo de itemsets y utiliza una función de generación de candidatos que explota la propiedad de cierre hacia abajo del soporte.

Algoritmo de eclat

ECLAT (Alt ECLAT, soportes para la transformación de clase de equivalencia) es un algoritmo de búsqueda en profundidad mediante intersección conjunto.

Algoritmo de FP-crecimiento

FP está parado para el patrón frecuente.

En el primer paso, el algoritmo cuenta la ocurrencia de los elementos (pares de atributo y valor) en el conjunto de datos y los almacena para 'tabla'. En el segundo paso, se construye la estructura de árbol FP insertando las instancias. Artículos en cada instancia debe ordenarse por orden decreciente de su frecuencia en el conjunto de datos, para que el árbol puede ser procesado rápidamente. Artículos en cada instancia que no alcancen el umbral de una cobertura mínima se descartan. Si muchos casos comparten elementos más frecuentes, FP-árbol proporciona alta compresión cerca de raíz del árbol.

Proceso recursivo de esta versión comprimida del principal conjunto de datos crece sets de objetos grandes directamente, en lugar de generar elementos de candidato y probándolas contra la base de datos. Crecimiento comienza desde el fondo de la tabla de cabecera (teniendo ramas más largas), encontrando coincidencia dada la condición de todas las instancias. Se crea nuevo árbol, con recuentos proyectadas desde el árbol original correspondiente al conjunto de instancias que están condicionadas por el atributo, con cada nodo a la suma de sus cuentas de los niños. Crecimiento recursivo termina cuando no condicionada en el atributo de los elementos individuales con umbral mínimo soporte, y procesamiento continúa en los restantes elementos de encabezado del FP-árbol original.

Una vez que ha finalizado el proceso recursivo, se han encontrado todos los conjuntos de gran artículo con una cobertura mínima, y creación de reglas de asociación comienza.

Otros

AprioriDP

AprioriDP utiliza Programación dinámica en el conjunto de ítems frecuentes minera. El principio de funcionamiento es eliminar la generación de candidatos como FP-árbol, pero apoyo cuenta en estructura de datos especializados en vez de árbol.

Asociación regla minería algoritmo basado en contexto

Artículo principal: Contexto basado en las reglas de asociación

CBPNARM es el algoritmo desarrollado recientemente, que se desarrolla en 2013 a mina de reglas de asociación sobre la base de contexto. Se utiliza la variable de contexto sobre la base de que el apoyo de un conjunto de ítems se cambia en base a que las reglas están pobladas por fin al conjunto de reglas.

Nodo conjunto basado en algoritmos

ALETA, PrePost y PPV están tres algoritmos basados en conjuntos de nodos. Usan los nodos en un codificación FP-árbol para representar a itemsets y emplear una estrategia de búsqueda en profundidad al descubrimiento itemsets frecuente mediante "intersección" de los conjuntos de nodos.

Procedimiento de GUHA ASSOC

GUHA es un método general para el análisis exploratorio de datos que tiene fundamentos teóricos en cálculos observacionales.

El procedimiento de Asoc. es un método GUHA que minas por las reglas de asociación generalizado uso rápido bitstrings operaciones. Las reglas de asociación minadas por este método son más generales que las salida por apriori, por ejemplo "artículos" se puede conectar tanto con la conjunción y disyuntivas y la relación entre antecedente y consecuente de la regla es no restringida al ajuste mínimo apoyo y confianza en apriori: puede usarse una combinación arbitraria de las medidas de interés compatibles.

Búsqueda de OPUS

OPUS es un algoritmo eficiente para el descubrimiento de la regla que, en contraste con la mayoría de las alternativas, no requiere monotono o monotono contra restricciones como mínimo apoyo. Inicialmente usado para encontrar las reglas para una consecuente fijo Posteriormente se ha extendido para encontrar las reglas con cualquier objeto como un consecuente. La búsqueda de OPUS es la tecnología de núcleo en el popular Magnum Opus sistema de descubrimiento de asociación.

Lore

Una historia famosa sobre minería de regla de asociación es la historia de "cerveza y pañales". Una supuesta encuesta de comportamiento de los compradores de supermercado descubrió que los clientes (presumiblemente jóvenes) que comprar pañales tienden también a comprar cerveza. Esta anécdota se hizo popular como un ejemplo de reglas de asociación tan inesperado podría encontrarse de datos diarias. Hay diferentes opiniones sobre cuánto de la historia es verdadera. Daniel Powers dice:

En 1992, Thomas Blischok, Gerente de un retail consulting group en Teradata y su personal había preparado un análisis de canastas de mercado 1,2 millones de unos 25 Osco Drug stores. Las consultas de base de datos se desarrollaron para identificar las afinidades. El análisis "descubrió que entre 5:00 y 19:00 que los consumidores compraron cerveza y pañales". Osco gerentes no explotar la relación cerveza y pañales moviendo los productos más cerca juntos en los estantes.

Otros tipos de explotación minera de la Asociación

Reglas de Asociación de relación múltiple:: Las reglas de asociación relación múltiple (MRAR) es una nueva clase de asociación que gobierna en contraste con las reglas de asociación primitivo, simple y ni siquiera multi relacionales (que generalmente se extrajeron de múltiples bases de datos), cada elemento de regla consiste en una sola entidad sino varias relaciones. Estas relaciones indican una relación indirecta entre las entidades. Considere la siguiente MRAR donde el primer elemento consiste en tres relaciones vivir en, cerca y húmedo:: "Aquellos que vivir en un lugar que es cerca de la una ciudad con húmedo son y también el tipo de clima más joven de 20 -> su condición de salud es buena". Tales reglas de asociación son extraíbles de datos RDBMS o web semántica.

Contexto basado en las reglas de asociación es una forma de gobierno de la asociación. Contexto basado en las reglas de asociación reclama mayor precisión en la minería regla Asociación teniendo en cuenta una variable de nombre variable oculta el contexto que cambia el conjunto final de las reglas de asociación dependiendo del valor de las variables de contexto. Por ejemplo, la orientación de las cestas en canasta análisis refleja un patrón extraño en los primeros días del mes.Esto podría ser debido contexto anormal es decir sueldo se dibuja en el comienzo del mes

Contraste conjunto de aprendizaje es una forma de aprendizaje asociativo. Contraste establece los alumnos Utilice reglas que difieren significativamente en su distribución a través de subconjuntos.

Clase ponderado aprendizaje es otra forma de aprendizaje asociativo en el cual peso puede asignarse a las clases para dar atención a un tema en particular de preocupación para el consumidor de los resultados de la minería de datos.

Descubrimiento del patrón de orden superior facilitar la captura de los patrones de orden superior (politeístas) o asociaciones de eventos que son intrínsecas a complejos datos del mundo real.

Descubrimiento de K-óptimo patrón proporciona una alternativa al enfoque estándar para el aprendizaje de la regla de asociación que requiere que cada patrón aparecen con frecuencia en los datos.

Conjunto de ítems frecuente aproximado minera es una versión relajada de la minería del conjunto de ítems frecuentes que permite que algunos de los artículos en algunas de las filas a ser 0.

Reglas de asociación generalizada taxonomía jerárquica (jerarquía de concepto)

Reglas de asociación cuantitativa datos categóricos y cuantitativos

Reglas de Asociación de datos intervalo por ejemplo la partición se extendieron la edad en 5-año-incremento

Reglas de la Asociación

Minería patrón secuencial Descubre subsecuencias que son comunes a más de secuencias de minsup en una base de datos de secuencia, donde se encuentra minsup por el usuario. Una secuencia es una lista ordenada de las transacciones.

Reglas secuenciales descubriendo las relaciones entre los elementos teniendo en cuenta el orden de tiempo. Generalmente se aplica sobre una base de datos de secuencia. Por ejemplo, una regla secuencial en base de datos de secuencias de transacciones del cliente puede ser que los usuarios que compraron una computadora y CD-ROMs, compró más adelante una webcam, con un dado confianza y apoyo.

Warmr se envía como parte de la suite de minería de datos ACE. Permite aprender regla de Asociación para reglas relacionales de primer orden.

Véase también

• Secuencia minera
• Sistema de producción

Enlaces externos

Bibliografías

• Bibliografía extensa sobre las reglas de asociación por J.M. Luna
• Hahsler, Michael; Bibliografía anotada sobre las reglas de asociación
• Statsoft electrónico Statistics Textbook: Las reglas de asociación

Implementaciones

• Implementaciones de Java. Algoritmos de minería de regla de asociación
• SIPINA, un software de minería de datos libre, académico que incluye un modelo para el aprendizaje de la regla de asociación.
• KXEN, un software comercial de minería de datos
• Widget de Silverlight para demostración en directo de explotación minera de la regla de asociación utilizando el algoritmo Apriori
• RapidMiner, una suite de software libre de Java datos minera (Community Edition: GNU)
• Naranja, una suite de software de minería de datos libres, módulo orngAssoc
• Implementación de Rubí (AI4R)
• unenfoque, un paquete de reglas de Asociación minera y itemsets frecuentes con R
• Implementación de Christian Borgelt del Apriori, FP-Growth y Eclat
• Frecuente el conjunto de ítems minería implementaciones repositorio (FIMI)
• Patrón frecuente de minería implementaciones de Bart Goethals
• Weka, una colección de algoritmos de aprendizaje máquina para las tareas de minería de datos escritos en Java
• KNIME un flujo de trabajo de código abierto orientado a la plataforma de procesamiento y análisis de datos
• Zaki, Mohammed J.; Software de minería de datos
• Magnum Opus, un sistema para el descubrimiento de asociación estadísticamente sonido
• Minero de lISp, las minas de las reglas de asociación (GUHA) generalizadas (usos bitstrings, no algoritmo apriori)
• Ferda cartográfico, una plataforma de explotación minera extensible datos visuales, implementa procedimientos GUHA ASSOC y dispone de minería de datos multirelational
• STATISTICA, software de estadísticas comerciales con un módulo de reglas de asociación
• SPMF, una plataforma de minería de datos de código abierto ofreciendo más de 48 algoritmos para la Asociación regla minería, explotación minera del conjunto de ítems y minería patrón secuencial. Incluye un simple código java y la interfaz de usuario se distribuye bajo la licencia GPL.
• ARtool, Regla de asociación GPL Java minería aplicación con interfaz gráfica, ofrece implementaciones de varios algoritmos para el descubrimiento de patrones frecuentes y extracción de las reglas de asociación (incluye Apriori y FPgrowth)
• EasyMiner, un sistema de extracción de regla asociación basada en web para la minería interactivo. Demo gratuita. Basado en Minero de lISp

Otras Páginas

• Abogado pasante
• Ley de Australia del sur 1834
• Bonsecours
• Gremio de autores v. HathiTrust
• Quiste meniscal
• Hoja de linea
• Endometrin
• Kim Young-moo
• Electropoise
• Quimica con plantillas de acidos nucleicos
• Universidad de Colorado Denver Business School
• Lanzamiento de equidad
• Lecomte (arquero)