Se FPGrowth todavía se considera “estado del arte” en la minería patrón frecuente?

Question

Por lo que yo sé el desarrollo de algoritmos para resolver el problema del patrón frecuente Minería (FPM), el camino de mejoras tiene algunos puntos de control principales. En primer lugar, la Apriori algoritmo fue propuesta en 1993, por Agrawal et al. , junto con la formalización del problema. El algoritmo fue capaz de tira-off algunos conjuntos de los conjuntos de 2^n - 1 (Powerset) mediante el uso de un enrejado para mantener los datos. Un inconveniente del enfoque era la necesidad de volver a leer la base de datos para calcular la frecuencia de cada conjunto ampliado.

Más tarde, en el año 1997, Zaki et al. propuso el algoritmo Eclat , que insertado la frecuencia resultante de cada conjunto dentro de la celosía . Esto se hizo mediante la adición de, en cada nodo de la red, el conjunto de transacción-ids que tenían los artículos de la raíz al nodo referido. La contribución principal es que uno no tiene que volver a leer todo el conjunto de datos para conocer la frecuencia de cada conjunto, pero la memoria necesaria para mantener dicha estructura de datos incorporado puede exceder el tamaño del propio conjunto de datos.

En 2000, Han et al propusieron un algoritmo llamado FPGrowth , junto con una estructura de datos de prefijo-árbol llamado FPTree. El algoritmo fue capaz de proporcionar una compresión de datos significativa, a la vez que la concesión de que los conjuntos de elementos frecuentes solamente sería cedido (sin generación de conjunto de elementos candidato). Esto se hizo principalmente por la clasificación de los artículos de cada transacción en orden decreciente, de manera que los elementos más frecuentes son los que tienen el menor número de repeticiones en la estructura de datos de árbol. Puesto que la frecuencia solamente desciende mientras atraviesa el árbol en profundidad, el algoritmo es capaz de tira-off conjuntos de elementos no frecuentes.

Editar

Por lo que yo sé, esto puede ser considerado como un algoritmo de estado-of-the-art, pero me gustaría saber sobre otras soluciones propuestas. ¿Qué otros algoritmos para FPM se consideran "estado-of-the-art"? ¿Cuál es el intuición / principal contribución de este tipo de algoritmos?

es el algoritmo FPGrowth todavía se considera "estado del arte" en la minería patrón frecuente? Si no, ¿qué algoritmo (s) se puede extraer conjuntos de elementos frecuentes de grandes conjuntos de datos de manera más eficiente?

Answer 1

El estado del arte como en:? Utilizado en la práctica o trabajado en la teoría

A priori se utiliza en todas partes, excepto en el desarrollo de nuevos algoritmos conjunto de elementos frecuentes. Es fácil de implementar y fácil de reutilización en diferentes dominios. Encontrará cientos de implementaciones a priori de calidad variable. Y es fácil de conseguir APRIORI mal, en realidad.

FPgrowth es mucho más difícil de implementar, pero también mucho más interesante. Por lo tanto, desde un punto de vista académico, trata todo el mundo para mejorar FPgrowth -. Conseguir trabajo basado en APRIORI aceptado será muy difícil por ahora

Si usted tiene una buena aplicación, cada algoritmo tiene es bueno y es malo situaciones en mi opinión. Una buena aplicación APRIORI será solamente necesidad de escanear la base de datos k veces para encontrar todos los conjuntos de elementos frecuentes de longitud k . En particular, si sus ajustes de datos en la memoria principal esto es barato. Lo que puede matar APRIORI es demasiados frecuentes 2-conjuntos de elementos (en particular, cuando no usan un trie y técnicas de aceleración similares, etc.). Funciona mejor en los datos de gran tamaño con un bajo número de conjuntos de elementos frecuentes.

Eclat trabaja en columnas; pero tiene que leer cada columna con mucha más frecuencia. Hay algunos trabajos en diffsets para reducir este trabajo. Si los datos no cabe en la memoria principal, Eclat sufre probablemente más de Apriori. Yendo primera profundidad, sino que también será capaz de devolver un primer resultado interesante mucho antes de lo priori, y se puede utilizar estos resultados para ajustar los parámetros; por lo que necesita menos iteraciones para encontrar buenos parámetros. Sin embargo, por diseño, no puede explotar la poda tan limpiamente como lo hizo priori.

FPGrowth comprime el conjunto de datos en el árbol. Esto funciona mejor cuando se tiene una gran cantidad de registros duplicados. Probablemente se podría obtener de bastantes ganancias para Apriori y Eclat también si se puede preclasificar sus datos y duplicados de combinación en vectores ponderados. FPGrowth hace esto a un nivel extremo. El inconveniente es que la aplicación es mucho más difícil; y una vez que este árbol no cabe en la memoria más se pone un desastre de implementar.

En cuanto a los resultados de rendimiento y puntos de referencia - no confía en ellos. Hay tantas cosas para poner en práctica de forma incorrecta. Trate de 10 implementaciones diferentes, y se obtiene 10 resultados de rendimiento muy diferentes. En particular, para APRIORI, tengo la impresión de que la mayoría de las implementaciones se rompen en el sentido de que faltan algunas de las principales aportaciones de APRIORI ... y de los que tienen derecho estas partes, la calidad de optimizaciones varía mucho.

En realidad, hay papeles incluso sobre cómo implementar estos algoritmos de manera eficiente:

Las implementaciones eficientes de Apriori y Eclat.
Cristiano Borgelt
Taller de Frecuente Conjunto de objetos Implementaciones Minería (FIMI 2003, Melbourne, FL, EE.UU.).

También es posible que desee leer estas encuestas en este dominio:

• Goethals, Bart. "Encuesta sobre el patrón de la minería frecuente." Univ. de Helsinki (2003).

• Ferenc Bodon, una encuesta sobre el conjunto de elementos frecuente Minería, Informe Técnico, Universidad de Budapest de Tecnología y Económica, 2006,

• frecuente de artículos Conjunto Minería
  Cristiano Borgelt
  Comentarios Wiley Interdisciplinary: minería de datos y descubrimiento de conocimiento 2 (6): 437-456. 2012

Answer 2

La mayor parte de la reciente patrón frecuente se aproxima a lo que he visto en la literatura se basan en la optimización de FPGrowth. Tengo que admitir, que no he visto muchos desarrollos dentro de la literatura en FPM en muchos años.

Este Wikibook destacado muchas de las variantes en FPGrowth que están fuera allí.