Patron de la fp

Crecimiento Fp vs apriori

En la era actual, una gran parte de nuestra vida consiste en entrar en diferentes aplicaciones y buscar nuestros requisitos. Una de las cosas únicas es el autocompletado, es decir, antes de poner una palabra completa en la barra de búsqueda, obtenemos algunas recomendaciones. A veces la barra de búsqueda nos recomienda exactamente lo que queríamos buscar, o a veces nos recomienda otras opciones que desconocemos. Para realizar esto en cualquier plataforma se requiere una forma perfecta de encontrar el conjunto de elementos frecuentes de forma eficiente. Esto funciona como un sistema de recomendación que trabaja con pares de palabras frecuentes y conjuntos de elementos que aparecen juntos con frecuencia. Todo esto entra en el ámbito de la minería de datos. El árbol FP es una estructura de datos especial que ayuda a todo el algoritmo a encontrar la mejor recomendación.

FP-tree (Frequent Pattern tree) es la estructura de datos del algoritmo FP-growth para extraer conjuntos de elementos frecuentes de una base de datos mediante el uso de reglas de asociación. Es una alternativa perfecta al algoritmo apriori.

Sugiere un enfoque de generación y prueba de conjuntos candidatos similar al de Apriori. Pero es bastante lento, y se vuelve más lento cuando hay muchos patrones disponibles en la minería. Por lo tanto, se propone FP-tree. La alternativa del algoritmo apriori, la estructura de árbol de patrones frecuentes (FP-tree), es una estructura de datos en forma de árbol para almacenar patrones frecuentes.

Crecimiento de Fp en la minería de datos

Paso 6: Construir el árbol FP condicional en la secuencia de orden inverso de F – Lista {E,M,P,B} y generar el conjunto de elementos frecuentes. El árbol FP condicional es un subárbol que se construye considerando las transacciones de un ítem en particular y luego eliminando ese ítem de todas las transacciones.

En cuanto a los elementos E y M, los nodos del árbol FP condicional tienen un recuento (soporte) de 1 (menor que el umbral mínimo de soporte 2). Por lo tanto, el conjunto de elementos frecuentes es nulo. En el caso del ítem P, el nodo B del árbol de FP condicional tiene un count(support) de 3 (que satisface el umbral mínimo de soporte). Por lo tanto, el conjunto de elementos frecuentes se genera añadiendo el elemento P a B.

Definición del algoritmo Fp-growth

En general, el algoritmo ha sido diseñado para operar en bases de datos que contienen transacciones, como las compras de los clientes de una tienda. Un conjunto de artículos se considera “frecuente” si cumple un umbral de soporte especificado por el usuario. Por ejemplo, si el umbral de soporte se fija en 0,5 (50%), un conjunto de artículos frecuentes se define como un conjunto de artículos que aparecen juntos en al menos el 50% de todas las transacciones de la base de datos.

En particular, y lo que lo diferencia del algoritmo de minería de patrones frecuentes Apriori, FP-Growth es un algoritmo de minería de patrones frecuentes que no requiere la generación de candidatos. Internamente, utiliza una estructura de datos denominada FP-tree (árbol de patrones frecuentes) sin generar explícitamente los conjuntos de candidatos, lo que lo hace especialmente atractivo para grandes conjuntos de datos.

[1] Han, Jiawei, Jian Pei, Yiwen Yin y Runying Mao. “Mining frequent patterns without candidate generation. “Un enfoque de árbol de patrones frecuentes”. Data mining and knowledge discovery 8, no. 1 (2004): 53-87.

Por defecto, fpgrowth devuelve los índices de las columnas de los elementos, lo que puede ser útil en operaciones posteriores como la minería de reglas de asociación. Para mejorar la legibilidad, podemos establecer use_colnames=True para convertir estos valores enteros en los respectivos nombres de los elementos:

Generador de árboles Fp

El algoritmo de crecimiento FP basado en el árbol de prefijos es un proceso de dos pasos: la construcción del árbol de patrones frecuentes (árbol FP) y la generación de los patrones frecuentes a partir del árbol. Después de construir el árbol FP, si simplemente utilizamos los árboles FP condicionales (CFP-tree) para generar los patrones de elementos frecuentes, podemos encontrarnos con el problema de la construcción recursiva del árbol CFP y un gran número de generación de conjuntos de elementos redundantes. Lo que también conduce a un enorme espacio de búsqueda y a un requerimiento masivo de memoria. En este artículo, hemos propuesto un nuevo diseño de estructura de datos denominado árbol FP condicional modificado (MCFP-tree). Además, hemos propuesto un nuevo algoritmo de crecimiento de patrones llamado Modified FP-Growth (MFP-Growth), que utiliza enfoques top-down y bottom-up para generar eficientemente los patrones frecuentes sin construir recursivamente el MCFP-tree. Durante la fase de extracción, sólo se mantiene un árbol MCFP en la memoria principal en cualquier momento y se elimina inmediatamente o se descarta de la memoria después de realizar la extracción. Del análisis experimental se desprende que el algoritmo MFP-Growth propuesto requiere menos memoria para construir el árbol MCFP en comparación con el árbol FP condicional. Además, la ejecución del método MFP-Growth es significativamente más rápida que el tradicional FP-Growth, ya que no genera patrones redundantes.

Entradas creadas 3216

Publicaciones relacionadas

Comienza escribiendo tu búsqueda y pulsa enter para buscar. Presiona ESC para cancelar.

Volver arriba