💻 computer science

CATD-LPT-CFPM- Cluster Aware Top-Down Linear Prefix Tree for Closed Frequent Pattern Mining

El artículo propone el marco CATD-LPT-CFPM, el cual mejora la minería de patrones frecuentes cerrados mediante la agrupación de transacciones para reducir el espacio de búsqueda y el empleo de una estrategia de poda multinivel con un mecanismo de Poda de Cerradura Top-Down para minimizar el procesamiento redundante y el uso de memoria, a pesar de incurrir en cierta sobrecarga por la agrupación y la construcción del árbol.

Autores originales: M Sinthuja, P Saranya, M. Diviya

Publicado 2026-07-30

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: M Sinthuja, P Saranya, M. Diviya

Artículo original bajo licencia CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que eres un detective intentando resolver un misterio en un almacén enorme y caótico lleno de millones de carritos de la compra. Tu trabajo no es solo descubrir qué compró la gente, sino encontrar las combinaciones secretas de artículos que aparecen juntas una y otra vez. Este campo de la ciencia se llama "minería de patrones frecuentes". Piensa en esto como intentar averiguar que las personas que compran "pan" y "mantequilla" casi siempre compran también "mermelada". Pero aquí está el truco: si simplemente enumeras cada combinación, te sentirás abrumado. Podrías descubrir que el "pan" aparece 1,000 veces, el "pan y mantequilla" aparece 900 veces, y el "pan, mantequilla y mermelada" aparece 800 veces. Enumerar todos estos de forma separada es como escribir cada paso de una receta cuando solo necesitas el plato final; es una gran pérdida de tiempo y papel.

Para solucionar esto, los científicos utilizan un truco llamado "patrones frecuentes cerrados". En lugar de listar cada paso, solo listan las combinaciones que son únicas en su frecuencia. Si el "pan y la mantequilla" aparecen 900 veces, pero añadir la "mermelada" reduce el recuento a 800, entonces el "pan y la mantequilla" es un patrón "cerrado" porque te dice algo que la lista más larga no dice. Sin embargo, encontrar estos patrones especiales en bases de datos enormes y densas (como un almacén donde casi todos los carritos tienen los mismos 50 artículos) es increíblemente difícil. Los métodos antiguos son como intentar leer cada uno de los recibos del almacén uno por uno, lo que lleva una eternidad y consume toda tu memoria. A menudo se quedan atrapados en un laberinto de información duplicada, desperdiciando energía en patrones que en realidad no cuentan una historia nueva.

Aquí es donde entra la nueva investigación. Un equipo de científicos del Instituto de Tecnología de Vellore ha propuesto un nuevo y astuto método llamado CATD-LPT-CFPM. En lugar de mirar todo el almacén a la vez, decidieron organizar primero los recibos. Imagina clasificar todos los carritos de la compra en diferentes habitaciones según su característica más obvia, como poner todos los carritos con "cables USB" en una habitación y todos los carritos con "discos duros" en otra. Esto es la agrupación (clustering). Al agrupar las transacciones similares, reducen el problema gigante en rompecabezas más pequeños y manejables.

Una vez que los carritos están en sus habitaciones, el equipo construye un "Árbol de Prefijo Lineal" especial para cada habitación. Piensa en este árbol como un árbol genealógico para los artículos de compra, pero dibujado en una línea recta para ahorrar espacio. Luego, recorren este árbol desde la parte superior (la raíz) hasta la parte inferior (las hojas), lo que llaman un enfoque Top-Down (de arriba hacia abajo). Mientras caminan, utilizan una técnica de "poda". Si ven una rama que no tiene suficiente "soporte" (es decir, que los artículos no se compran con la frecuencia suficiente), cortan esa rama inmediatamente. Mejor aún, utilizan un nuevo truco llamado Poda de Cierre Top-Down (Top-Down Closedness Pruning). Esto es como revisar a un padre y a su hijo: si el hijo tiene exactamente el mismo número de compradores que el padre, el padre es redundante y se corta. Esto asegura que solo conserven los patrones más únicos e informativos.

El artículo encuentra que este método es un maestro de la eficiencia cuando se trata de la memoria. En las pruebas utilizando conjuntos de datos del mundo real como "Mushroom" (una base de datos de características de hongos), "Chess" (un conjunto de datos de juego denso) y "Online Shopping", el nuevo método utilizó significativamente menos memoria que las técnicas anteriores. Por ejemplo, en el conjunto de datos Mushroom con un umbral de soporte específico, el nuevo método utilizó aproximadamente 28.12 MB de memoria, mientras que el método anterior "FP-Close" utilizó 30.36 MB y "DFI-List" utilizó 30.71 MB. En el conjunto de datos de Online Shopping, la diferencia fue aún más clara: el nuevo método utilizó solo 7.06 MB, mientras que los otros rondaban los 14 MB.

Sin embargo, hay una compensación. El artículo señala explícitamente que, si bien el nuevo método ahorra memoria y crea una lista de patrones más limpia y organizada, es más lento en términos de tiempo de ejecución. Debido a que el método tiene que hacer un trabajo extra —clasificar los carritos en habitaciones, construir los árboles y verificar los duplicados—, tarda más en terminar el trabajo. En el conjunto de datos Mushroom, el nuevo método tardó 20.28 segundos en ejecutarse, mientras que el método anterior "DFI-Graph" terminó en tan solo 0.76 segundos. Los autores son claros al respecto: este nuevo enfoque no es una mejora mágica de velocidad; es un "ahorrador de memoria" que organiza el espacio de búsqueda para evitar la redundancia.

Al final, los investigadores sugieren que este enfoque es mejor para situaciones en las que te importa más tener una lista de patrones compacta y no redundante y ahorrar espacio de almacenamiento que obtener la respuesta en un segundo. Es como elegir organizar cuidadosamente toda tu biblioteca para que puedas encontrar cualquier libro instantáneamente después, en lugar de simplemente agarrar un montón de libros rápidamente y esperar encontrar lo que necesitas. El artículo concluye que, aunque la versión actual toma más tiempo debido a los pasos adicionales de agrupación y construcción de árboles, logra minar patrones frecuentes cerrados de manera efectiva, ofreciendo una forma prometedora de manejar grandes y desordenados conjuntos de datos sin ahogarse en la información duplicada.

Resumen Técnico: CATD-LPT-CFPM para la Minería de Patrones Frecuentes Cerrados

Planteamiento del Problema

La minería de conjuntos de elementos frecuentes (FIM) es un proceso fundamental en la minería de reglas de asociación, sin embargo, los enfoques tradicionales suelen sufrir la generación de excesivos patrones duplicados y sin sentido. Si bien la minería de patrones frecuentes maximales reduce el tamaño de la salida, no logra preservar los valores de soporte precisos de los subconjuntos, lo que la hace insuficiente para ciertas necesidades analíticas. En consecuencia, la minería de Patrones Frecuentes Cerrados (CFP) ha emergido como una alternativa preferida, ofreciendo una representación concisa y sin pérdida de todos los patrones frecuentes.

No obstante, los algoritmos de minería de CFP existentes enfrentan desafíos significativos cuando se aplican a conjuntos de datos densos y a gran escala:

Alta Carga Computacional: Los métodos tradicionales a menudo requieren escanear toda la base de datos de transacciones o construir una única estructura de búsqueda global, lo que conduce a un alto consumo de memoria y tiempo de ejecución.
Explosión del Espacio de Búsqueda: Los conjuntos de datos densos resultan en un espacio de búsqueda masivo, haciendo que el descubrimiento de patrones significativos sea computacionalmente costoso.
Redundancia: Sin un recorte eficiente, los algoritmos pueden procesar conjuntos de elementos redundantes, aumentando los costos de almacenamiento y análisis.

El artículo argumenta que las estructuras de búsqueda única actuales son ineficientes para datos densos, lo que requiere un nuevo enfoque que divida el espacio de búsqueda y emplee mecanismos de recorte avanzados para reducir la redundancia y el uso de recursos.

Metodología: CATD-LPT-CFPM

Los autores proponen CATD-LPT-CFPM (Cluster Aware Top-Down Linear Prefix Tree for Closed Frequent Pattern Mining), un marco diseñado para optimizar el proceso de minería mediante el agrupamiento de transacciones y el recorte multinivel. La metodología procede a través de las siguientes etapas:

1. Preprocesamiento y Ordenamiento de Transacciones

La base de datos de transacciones se preprocesa para calcular los conteos de soporte de los elementos individuales. Los elementos que caen por debajo del umbral de soporte mínimo son descartados. Los elementos restantes se ordenan en orden descendente de soporte para maximizar el uso compartido de prefijos en las estructuras de árbol subsiguientes.

2. Agrupamiento de Transacciones (Clustering)

La base de datos se particiona en $k$ grupos ( $C = \{c_1, c_2, \dots, c_k\}$ ) basados en prefijos compartidos. Las transacciones con elementos iniciales similares se agrupan. Este paso tiene como objetivo crear grupos homogéneos, limitando así el alcance de la minería de patrones dentro de cada grupo y evitando la necesidad de procesar toda la base de datos como una sola unidad.

3. Recorte de Eliminación de Grupos (CEP)

Antes de construir las estructuras de datos, los grupos se evalúan frente al umbral de soporte mínimo. Si el número total de transacciones en un grupo ( $|C_i|$ ) es menor que el soporte mínimo, el grupo es descartado. Esto evita la construcción innecesaria de árboles de prefijos para segmentos de datos poco prometedores, reduciendo la sobrecarga inicial de memoria.

4. Construcción de Árbol de Prefijo Lineal (LPT) por Grupo

Para cada grupo retenido, se construye un Árbol de Prefijo Lineal (LPT) independiente.

Las transacciones dentro de un grupo se insertan en el LPT.
Las transacciones que comparten prefijos comunes se fusionan en el mismo camino, incrementando los conteos de soporte de los nodos.
Nuevas secuencias crean nuevas ramas.
Cada nodo almacena el nombre del elemento, el conteo de soporte, el enlace al nodo y una bandera que indica el estado de la rama.
Esta estructura permite una investigación de patrones enfocada dentro de grupos específicos en lugar de una búsqueda global.

5. Recorrido Descendente y Recorte Basado en Soporte

Los LPT se recorren desde la raíz hacia las hojas. Durante el recorrido:

Los nodos con conteos de soporte por debajo del umbral de soporte mínimo se descartan inmediatamente.
Esta eliminación temprana reduce el volumen de patrones candidatos antes de la verificación de clausura (closedness).

6. Recorte de Clausura Descendente (TDCP)

Se aplica un novedoso mecanismo de Recorte de Clausura Descendente (TDCP) para identificar patrones cerrados locales dentro de cada grupo.

El algoritmo compara el valor de soporte de un nodo padre (subconjunto) con sus nodos hijos (superconjuntos).
Si $Soporte(Subconjunto) = Soporte(Superconjunto)$, el subconjunto se considera no cerrado y se descarta.
Si $Soporte(Subconjunto) > Soporte(Superconjunto)$, el subconjunto se retiene como un patrón frecuente cerrado local.
Este paso minimiza el almacenamiento de conjuntos de elementos duplicados durante la fase de minería local.

7. Cálculo de Soporte Global y Verificación de Clausura

Los patrones cerrados locales de todos los grupos se fusionan para generar el conjunto global final.

Cálculo de Soporte Global: El soporte de los patrones locales se recalcula agregando los conteos a través de toda la base de datos de transacciones para asegurar la frecuencia global.
Verificación de Clausura Global: Una verificación final compara los subconjuntos globales con sus superconjuntos globales. Si un superconjunto tiene el mismo soporte global que el subconjunto, el subconjunto se descarta por ser redundante.
Esta verificación de dos etapas (primero local y luego global) asegura que la salida final contenga solo patrones frecuentes globales compactos, completos y cerrados.

Contribuciones Clave

Minería Consciente de Grupos (Cluster-Aware): La introducción del agrupamiento de transacciones para dividir el espacio de búsqueda, permitiendo una minería enfocada en grupos homogéneos en lugar de procesar toda la base de datos en una sola pasada.
Árbol de Prefijo Lineal (LPT) por Grupo: La construcción de LPT separados y compactos para cada grupo, lo que reduce los requisitos de almacenamiento y permite un recorrido eficiente.
Recorte de Clausura Descendente (TDCP): Un mecanismo novedoso que identifica patrones no cerrados durante el recorrido comparando los soportes de los nodos padre e hijo, minimizando eficazmente el análisis de conjuntos de elementos duplicados.
Estrategia de Recorte Multinivel: Un marco integral que combina el Recorte de Eliminación de Grupos, el Recorte Basado en Soporte y el Recorte de Clausura para reducir sistemáticamente el espacio de búsqueda y la huella de memoria.

Resultados Experimentales

Los autores evaluaron CATD-LPT-CFPM utilizando tres conjuntos de datos de referencia: Mushroom, Chess y un conjunto de datos personalizado de Compras en Línea (Online Shopping). El algoritmo se comparó con los métodos existentes: FP-Close, DFI-Growth y DFI-List.

Consumo de Memoria

Desempeño: El método propuesto demostró una eficiencia de memoria superior en comparación con FP-Close, DFI-Growth y DFI-List en todos los conjuntos de datos.
Consistencia: El uso de memoria se mantuvo relativamente constante y bajo incluso cuando variaban los umbrales de soporte mínimo. Por ejemplo, en el conjunto de datos Mushroom con un soporte mínimo de 1218, CATD-LPT-CFPM utilizó ~28.12 MB, mientras que FP-Close utilizó ~30.36 MB y DFI-List utilizó ~30.71 MB. La brecha se amplió en umbrales de soporte más altos.
Escalabilidad: El enfoque de agrupamiento gestionó eficazmente el consumo de memoria para conjuntos de datos densos al evitar la construcción de una única y masiva estructura global.

Tiempo de Ejecución

Compromiso (Trade-off): El artículo reconoce que CATD-LPT-CFPM tiene un mayor tiempo de ejecución en comparación con los algoritmos de base.
Causas: El aumento de tiempo se atribuye a la sobrecarga computacional de la fase de agrupamiento, la construcción de múltiples árboles de prefijo y la verificación de clausura en múltiples etapas (local y global).
Datos: En el conjunto de datos Mushroom (MinSup 1218), CATD-LPT-CFPM tomó ~80.56 segundos, mientras que FP-Close tomó ~1.13 segundos y DFI-Growth tomó ~0.54 segundos. Tendencias similares se observaron para los conjuntos de datos Chess y Online Shopping.
Justificación: Los autores argumentan que el costo de tiempo es un compromiso aceptable por las ganancias significativas en eficiencia de memoria y la reducción de la generación de patrones redundantes.

Reducción de Patrones

El estudio confirmó que a medida que aumenta el umbral de soporte mínimo, el número de patrones frecuentes y cerrados generados disminuye, recortando eficazmente el espacio de búsqueda.
La minería de patrones cerrados redujo con éxito el tamaño de la salida significativamente (por ejemplo, los patrones cerrados fueron cuatro veces más pequeños que los patrones frecuentes en el conjunto de datos Mushroom), validando la eficacia de los mecanismos de verificación de clausura.

Significado y Reivindicaciones

El artículo posiciona a CATD-LPT-CFPM como un método prometedor para la minería de conjuntos de elementos frecuentes cerrados, particularmente en escenarios donde se priorizan la eficiencia de memoria, la reducción de patrones y la extracción de conocimiento estructurado sobre la velocidad de ejecución bruta.

Los autores afirman que el marco:

Proporciona un marco de minería compacto que recorta eficazmente los patrones redundantes.
Mejora la interpretabilidad de los patrones al proporcionar una representación concisa y sin pérdida.
Es ideal para grandes conjuntos de datos transaccionales debido a su estructura de agrupamiento y de árbol, que gestiona el consumo de memoria de manera más efectiva que los enfoques tradicionales de estructura única.
Ofrece una solución equilibrada para conjuntos de datos densos donde los métodos existentes luchan contra la alta ocupación de memoria y la explosión del espacio de búsqueda.

Los autores concluyen que, si bien el tiempo de ejecución es actualmente mayor debido a los pasos de procesamiento adicionales, la capacidad del marco para minimizar las necesidades de almacenamiento y organizar el espacio de búsqueda lo convierte en una contribución valiosa al campo de la minería de patrones frecuentes. Se sugiere que el trabajo futuro se centre en el procesamiento paralelo y en la mejora de las estrategias de recorte para optimizar aún más el tiempo de ejecución.