Redes neuronales: así de sencillo (Parte 18): Reglas asociativas

Contenido

• Introducción
• 1. Reglas asociativas
• 2. El algoritmo Apriori
• 3. El algoritmo FP-Grows
• Conclusión
• Enlaces

Introducción

A medida que aumenta la cantidad de información a analizar, también aumenta el interés por el método de aprendizaje no supervisado. En los últimos artículos de esta serie, ya hemos visto los algoritmos de clusterización y de reducción de la dimensionalidad, que se relacionan con los métodos de aprendizaje no supervisado. En este artículo, seguiremos explorando los métodos de aprendizaje no supervisado. Asimismo, le proponemos familiarizarse con otro tipo de problema a resolver: el análisis de reglas asociativas. Este tipo de tarea se formuló por primera vez en el comercio minorista para analizar las cestas de la compra, como una búsqueda de los conjuntos de productos más frecuentes. Hoy en día, los algoritmos para resolver este tipo de problemas se usan ampliamente en varios campos. Veamos cómo podemos utilizar este algoritmo en el trading.

1. Reglas asociativas

La tarea del análisis de reglas asociativas pertenece a las tareas aplicadas de Data Mining y es una de las principales entre ellas, ya que nos permite identificar las correlaciones entre los datos en las bases de datos voluminosas.

Este tipo de tarea se formuló y definió por primera vez en el comercio minorista, cuando los responsables de marketing comenzaron a pensar en cómo las empresas podían beneficiarse del análisis de una gran base de datos de transacciones en efectivo. En contraste con la época anterior, cuando solo se analizaban las ventas totales, el novedoso análisis de los ingresos de efectivo de los clientes descubría nuevos horizontes, porque permitía analizar conjuntos individuales de productos adquiridos por los clientes.

El primer algoritmo fue creado en 1993 por un grupo de desarrolladores de IBM. Precisamente entonces se formularon los postulados básicos que constituyeron la base de todo un grupo de algoritmos.

En primer lugar, las reglas halladas con ayuda de los algoritmos deben encontrarse con frecuencia. Es decir, deberán ser no aleatorias y repetirse al menos un cierto número de veces en la base de datos analizada. Deberá confirmarse en la práctica, por así decirlo. Y desde el punto de vista estadístico, una muestra de transacciones que contenga dicha regla deberá ser representativa. Para cumplir este requisito, en todos los algoritmos de búsqueda de reglas asociativas deberá haber un parámetro de soporte mínimo (MinSup - soporte mínimo), que indique en fracciones de "1" la relación entre la frecuencia de aparición de las reglas y el número total de transacciones de la muestra analizada.

Y aquí hay que entender que teniendo un conjunto de 3 atributos A, B y C según las reglas de la combinatoria sin considerar la posición de los elementos, podemos obtener 7 conjuntos diferentes que contengan de 1 a 3 de estos atributos. A medida que el número de características aumente, también lo hará el número de combinaciones posibles. Y, teniendo en cuenta el tamaño de las bases de datos, recalcular directamente la frecuencia de aparición de cada conjunto de características se convertirá en una tarea que requiere mucho tiempo. Con frecuencia, un tiempo inasumible. Por consiguiente, los autores aprovecharon la propiedad de anti-monotonicidad.

Si en la base de datos solo aparece un conjunto de características A, su frecuencia será igual a la de la propia característica A. No obstante, si el número de conjuntos encontrados es mayor, su frecuencia solo podrá ser menor, ya que el número total de apariciones de estos en la muestra analizada será igual al número de apariciones de la característica A. Así, si la frecuencia de aparición de una característica es inferior al soporte mínimo, entonces, como consecuencia, la frecuencia de todas las posibles variantes de los conjuntos que contienen esa característica también será inferior al soporte mínimo. Y esto significará que solo tenemos que calcular la frecuencia de aparición de cada característica para eliminar una parte significativa de los conjuntos aleatorios que no tienen ningún valor práctico para nosotros.

Como podemos ver, los algoritmos para encontrar reglas asociativas son muy diferentes aquí de todos los algoritmos anteriormente analizados. Si antes tratábamos de aprovechar al máximo todos los datos disponibles, ahora los algoritmos de búsqueda de reglas asociativas filtran inmediatamente los rasgos aleatorios (ruidosos).

El segundo parámetro usado en todos los algoritmos de búsqueda de reglas asociativas es el nivel de confianza mínima de la regla (MinConf - minimal confidence), que también se indica en fracciones de unidad. Para explicar este parámetro, debemos decir que cada regla tiene 2 partes: un antecedente y un consecuente. Tanto el antecedente como el consecuente pueden constar de una sola característica o de un conjunto de ellas. En general, la regla suena aproximadamente así: si el antecedente es verdadero, muy a menudo habrá un consecuente.

Nótese que la probabilidad de que haya un "consecuente" cuando hay un "antecedente" no es del 100%. La probabilidad mínima de aparición de un "consecuente" se establecerá usando el parámetro MinConf. Cuando se cumpla este parámetro, la regla se considerará válida y se almacenará en el array de reglas. Se define como la relación entre la frecuencia de la regla y la frecuencia con la que aparece el antecedente.

2. El algoritmo Apriori

El algoritmo Apriori probablemente sea uno de los algoritmos más conocidos para encontrar reglas asociativas. Fue propuesto por Rakesh Agrawal y Ramakrishnan Sikrant en 1994. El algoritmo se basa en un proceso iterativo de búsqueda de los patrones más frecuentes en una base de datos, con la posterior extracción de reglas a partir de los patrones seleccionados.

Para comprender todo mejor, vamos a ver el funcionamiento del algoritmo con un pequeño ejemplo de 10 transacciones con 5 características.

ID de la transacción	Contenido
T1	BCDE
T2	BCD
T3	B
T4	BCD
T5	D
T6	ACD
T7	BCDE
T8	BCE
T9	CDE
T10	AD

Introducimos en el problema una constante de soporte mínimo de 0,3 y una constante de confianza mínima de 0,7 (30% y 70% respectivamente).

Hay que entender que todos los algoritmos de búsqueda de reglas asociativas trabajan con arrays binarios. Por lo tanto, para empezar, presentaremos los datos anteriores como una tabla binaria.

ID de la transacción	A	B	C	D	E
T1	0	1	1	1	1
T2	0	1	1	1	0
T3	0	1	0	0	0
T4	0	1	1	1	0
T5	0	0	0	1	0
T6	1	0	1	1	0
T7	0	1	1	1	1
T8	0	1	1	1	0
T9	0	0	1	1	1
T10	1	0	0	1	0

Partiendo de esta tabla, resulta fácil calcular que la característica A aparece solo 2 veces y su soporte es de 0,2 o 20%. Calculamos igualmente los soportes para el resto de las características: B — 0.6, C — 0.7, D — 0.8, E — 0.4. Como podemos ver, solo la característica A no cumple el requisito de soporte mínimo, por lo que quedará excluida del procesamiento posterior debido a la propiedad de anti-monotonicidad.

A partir de los elementos restantes, recopilamos los candidatos a patrones frecuentemente encontrados. En el paso anterior, identificamos los signos más frecuentes. Y según el algoritmo, identificamos conjuntos de 2 características como candidatos: BC, BD, BE, CD, CE, DE.

Ahora tenemos que volver a revisar toda la base de datos e identificar el soporte para cada uno de los candidatos seleccionados.

ID de la transacción	BC	BD	BE	CD	CE	DE
T1	1	1	1	1	1	1
T2	1	1	0	1	0	0
T3	0	0	0	0	0	0
T4	1	1	0	1	0	0
T5	0	0	0	0	0	0
T6	0	0	0	1	0	0
T7	1	1	1	1	1	1
T8	1	0	1	0	1	0
T9	0	0	0	1	1	1
T10	0	0	0	0	0	0

Como podemos ver, el soporte de todos nuestros candidatos cumple la condición de soporte mínimo: BC — 0.5, BD — 0.4, BE — 0.3, CD — 0.6, CE — 0.4, DE — 0.3. Pero esta situación no siempre es posible. En la resolución de problemas prácticos, resulta más probable que algunos candidatos queden descartados.

A continuación, continuamos el proceso iterativo y esta vez recopilamos los conjuntos candidatos de 3 características. Para ello, tomamos los patrones frecuentemente seleccionados en la iteración anterior y combinamos los pares que difieren solo en un elemento. De esta forma, identificamos cuatro candidatos: BCD, BCE, BDE, CDE.

Y según el algoritmo Apriori, tenemos que volver a recorrer toda la base de datos e identificar los soportes para todos los nuevos candidatos.

ID de la transacción	BCD	BCE	BDE	CDE
T1	1	1	1	1
T2	1	0	0	0
T3	0	0	0	0
T4	1	0	0	0
T5	0	0	0	0
T6	0	0	0	0
T7	1	1	1	1
T8	0	1	0	0
T9	0	0	0	1
T10	0	0	0	0

Como resultado, obtendremos los siguientes soportes para nuestros candidatos: BCD — 0.4, BCE — 0.3, BDE — 0.2, CDE — 0.3. En esta iteración, el soporte del conjunto BDE no cumple el requisito de soporte mínimo, así que lo excluimos. Los candidatos restantes pasarán a la condición de patrón frecuente.

En la siguiente iteración, formamos conjuntos candidatos de 4 características. En este caso, a partir de los patrones seleccionados en la iteración anterior, solo podremos conformar un candidato BCDE. Pero antes de repasar toda la base de datos para calcular el soporte de este candidato, veamos su componente BDE. En la última iteración, eliminamos a este candidato porque su soporte era de 0,2, lo cual está por debajo del requisito de soporte mínimo de 0,3. En consecuencia, según la propiedad de anti-monotonicidad, para el candidato BCDE, el soporte no puede superar 0,2. Y esto se encuentra por debajo del nivel de soporte mínimo.

Como no tenemos más candidatos, detenemos el proceso de búsqueda de patrones frecuentes y pasamos al segundo subproceso: definir reglas a partir de los patrones frecuentes seleccionados. Para ello, dividiremos los patrones seleccionados en antecedente y consecuente. A continuación, determinaremos el nivel de confianza de cada regla y lo comparamos con el nivel de confianza mínimo requerido.

Después crearemos las reglas secuencialmente para cada producto y conjunto. Como en el primer paso hemos eliminado todos los patrones con la característica A (su soporte está por debajo del requisito mínimo), empezaremos a definir las reglas con la característica B.

De los patrones seleccionados, seleccionaremos todos los que contengan el producto analizado. Asimismo, extraeremos de los patrones la característica B para el consecuente, y la parte restante será el antecedente. Además, determinaremos el grado de confianza de cada regla creada.

El nivel de confianza de una regla muestra la probabilidad de que aparezca un consecuente al formarse un antecedente. Para determinarlo, no necesitaremos volver a revisar toda la base de datos. Solo tendremos que dividir el soporte del patrón completo por el soporte del antecedente, que ya hemos calculado en la fase de selección de patrones frecuentes.

Patrón	Antecedente	Soporte	Regla
BC (0.5)	C (0.7)	0.71.	C -> B
BD (0.4)	D (0.8)	0.50	D -> B
BE (0.3)	E (0.4)	0.75.	E -> B
BCD (0.4)	CD (0.6)	0.67	CD -> B
BCE (0.3)	CE (0,4)	0.75.	CE -> B

Las reglas D -> B y CD -> B no cumplen el requisito de soporte mínimo de 0,7, así que las excluimos.

De forma similar, definimos las demás reglas.

Patrón	Antecedente	Soporte	Regla
BC (0.5)	B (0.6)	0.83	B -> C
CD (0.6)	D (0.8)	0.75.	D -> C
CE (0,4)	E (0.4)	1.00	E -> C
BCD (0.4)	BD (0.4)	1.00	BD -> C
BCE (0.3)	BE (0.3)	1.00	BE -> C
CDE (0.3)	DE (0.3)	1.00	DE -> C
CD (0.6)	C (0.7)	0.86.	C -> D
DE (0.3)	E (0.4)	0.75.	E -> D
BCD (0.4)	BC (0.5)	0.80	BC -> D
CDE (0.3)	CE (0,4)	0.75.	CE -> D

Hemos examinado uno de los algoritmos de recuperación de reglas asociativas más conocidos, Apriori. Pero debemos decir que, a pesar de su sencillez y familiaridad, poca gente lo usa en la práctica hoy en día. La cuestión es que, como podemos ver, el cuello de botella del método analizado son las múltiples pasadas realizadas por la base de datos para evaluar los soportes de los candidatos a patrones frecuentes. A medida que aumenta el volumen de bases de datos a analizar, esto se convierte en un problema cada vez mayor. Esto prácticamente se resuelve en el siguiente algoritmo, que requiere solo 2 pasadas por la base de datos, independientemente del tamaño de la misma o del número de características que haya que analizar.

3. El algoritmo FP-Grows

Para resolver los problemas anteriores, le sugerimos estudiar uno de los algoritmos de búsqueda de reglas asociativas más rápidos, FP-Grows (Frequent Pattern - Grows). Debido a las peculiaridades de construcción del algoritmo, durante su ejecución se realiza una enumeración completa de todos los elementos de la muestra de entrenamiento solo 2 veces. No existen otras llamadas a la muestra de entrenamiento en el algoritmo.

Al igual que el algoritmo de búsqueda de reglas asociativas comentado anteriormente, el algoritmo FP-Grows puede dividirse condicionalmente en 2 subtareas:

1. Hallazgo de patrones frecuentes. En el algoritmo en cuestión, esto se denomina construcción del árbol FP.
2. Definición de las reglas.

El algoritmo comienza seleccionando características aleatorias. Para ello, de forma similar al algoritmo anterior, efectuamos una primera pasada por toda la muestra de entrenamiento y calculamos el soporte de cada característica. A continuación, eliminamos las características cuya frecuencia de aparición es inferior al soporte mínimo.

El resto de las características están clasificadas según el orden descendente de sus soportes. Para el ejemplo anterior, obtenemos la serie:

D (0.8) -> C (0.7) -> B (0.6) -> E(0.4) 

A continuación, hacemos crecer el árbol FP. Para ello, realizamos una segunda pasada por la muestra de entrenamiento. En este caso, en cada operación tomamos solo las características que aparecen con frecuencia, clasificamos en orden descendente su soporte, y construimos el camino en nuestro árbol. De este modo, el nodo con el máximo soporte estará en la raíz del árbol, y el nodo con el mínimo soporte será su hoja. Además, crearemos un contador para cada nodo, asignando en la primera iteración un valor de contador igual a 1 (o 1/N, donde N será el tamaño de la muestra de entrenamiento).

A continuación, tomaremos de la base de datos la siguiente transacción y construiremos para ella un camino de la misma forma, añadiéndolo después a nuestro árbol. Para ello, partiendo de la raíz del árbol, comprobaremos el camino con las ramas ya existentes. En cuanto a la repetición de la ruta desde la raíz, simplemente aumentaremos el contador de los nodos existentes. Para la nueva parte, crearemos una ramificación.

El ciclo de iteración se repite hasta que toda la muestra de entrenamiento se agota. Para el ejemplo anterior, obtendremos el siguiente árbol FP.

Hay que decir que, con un alto grado de probabilidad, podemos encontrar caminos diferentes a la propia raíz. También en este caso serán posibles dos opciones:

• la construcción de un bosque,
• la creación de una especie de nodo raíz que unirá toda la muestra.

Resulta bastante obvio que, al inicio del proceso de crecimiento del árbol FP, en su mayor parte, se crearán nuevos nodos. Sin embargo, a medida que avancemos en la muestra de entrenamiento llegaremos a aumentar los contadores de los nodos existentes sin crear nuevas ramificaciones. Lo bueno de este algoritmo es que durante la construcción del árbol podemos comprimir la muestra de entrenamiento hasta un tamaño que podamos manipular fácilmente dentro de la memoria RAM de la computadora sin tener que acceder a la base de datos.

El trabajo posterior de definición de reglas se lleva a cabo con el árbol FP, sin referencia a la base de datos original.

Las reglas se construyen para todas las características en orden ascendente de soporte.

Recordemos que en la primera etapa eliminamos todas las características con una frecuencia inferior a la especificada y ahora, nuestro árbol contiene solo las características que aparecen con frecuencia. Además, al construir el árbol hemos clasificado las características en orden descendente, lo cual significa que las características que tenemos con un soporte mínimo son hojas.

Empezando a definir las reglas con las características con menos soporte, nos moveremos desde las hojas hasta la raíz del árbol. En este caso, tampoco se ha establecido explícitamente una relación de causalidad. El algoritmo asume que los rasgos con menos soporte aparecen debido a la combinación de características con más soporte.

Pero volvamos a nuestro algoritmo de definición de reglas. Vamos a tomar la característica con el soporte más bajo e identificar todos los caminos en el árbol FP que conduzcan a dicha característica. Lo primero que miramos al seleccionar los caminos es la frecuencia con la que aparece la característica deseada al formar el patrón a partir de las características del camino. El criterio para la selección del camino es la relación entre el soporte de la característica en el camino y el soporte del nodo precedente. Esta relación no deberá ser inferior al nivel de confianza mínimo de la norma.

En el ejemplo anterior, la característica E es la que menos soporte tenía. Hay 3 caminos que conducen a ella en nuestros árboles de FP: DCBE (0.2), DCE (0.1), CBE(0.1). Ninguno de estos caminos cumple el requisito de soporte mínimo, y dos de ellos no cumplen el requisito mínimo de confianza. Por consiguiente, no podemos crear una única regla para la característica E. Debemos decir que esto se confirma con los resultados obtenidos del algoritmo Apriori. 

Eliminamos las hojas E de nuestro árbol y vemos el siguiente aspecto de nuestro árbol FP.

El siguiente elemento a analizar es la característica B. Es la que menos soporte tiene entre las restantes. Hay tres caminos para ella: DCB (0.4), B (0.1), CB (0.1).

En los caminos seleccionados, se asigna un soporte a cada característica que precede a la característica analizada en ese camino.

A partir de los caminos seleccionados, se genera una lista de características participantes y se determina el soporte a cada característica. Nótese que el soporte se define como la relación entre el número de apariciones de una característica en los caminos seleccionados y el número total de registros en la muestra de entrenamiento original. Por lo tanto, el nuevo soporte de cada característica no podrá superar ni el soporte inicial de la característica ni el soporte de la característica analizada (para la que se definen las reglas).

Aquí también eliminaremos las características con un soporte inferior al mínimo. Asimismo, colocaremos las características restantes en orden de soporte descendente.

En nuestro ejemplo, obtendremos C (0,5), D (0,4).

Tenga en cuenta que, como hemos calculado los soportes de las características basándonos únicamente en los caminos seleccionados, los valores obtenidos podrían ser muy diferentes de los valores originales. Como consecuencia de este factor, algunas de las características podrían desaparecer, y su orden en la nueva jerarquía podría cambiar.

A continuación, según la nueva jerarquía, construimos un nuevo árbol privado a partir de los caminos seleccionados. El algoritmo para construir el árbol no será distinto del algoritmo del árbol FP descrito anteriormente.

Las ramas del árbol privado construido serán los antecedentes de las reglas cuyo consecuente será nuestra característica analizada.

Después de construir el árbol privado, eliminaremos los nodos de la característica analizada del árbol FP original. El truco será analizar la característica con un soporte mínimo, lo cual significa que todos los nodos que contengan este rasgo serán hojas del árbol FP. Por lo tanto, su eliminación no ejercerá ningún efecto sobre los caminos de las otras características (ya hemos hablado de la causalidad).

Además, al eliminar gradualmente las características analizadas, reduciremos gradualmente nuestro árbol FP . De este modo, se reducirá el volumen para la posterior búsqueda de caminos en el análisis de las siguientes características. Y esto afectará al rendimiento general del algoritmo.

Del mismo modo, construiremos las reglas para cada característica en la jerarquía original del árbol FP.

Tenga en cuenta que solo podemos construir reglas para las características que estén precedidas por al menos un rasgo raíz en el árbol FP. Para las características de la raíz, no podemos construir reglas porque no tenemos nada que atribuir al antecedente, salvo, claro está, la visita de un cliente potencial a la tienda. Si viene a la tienda, significará que va a comprar algo, y es probable que sea algo de entre los artículos más vendidos de la tienda. Pero ello quedará fuera del alcance del algoritmo en cuestión.

Conclusión

En este artículo, hemos presentado otro tipo de problema que se resuelve con métodos de aprendizaje no supervisado: la búsqueda de reglas asociativas. Hemos visto 2 algoritmos para encontrar reglas asociativas: Apriori y FP-Grows, pero hay muchos más. Por desgracia, no podemos incluir el tema completo en un artículo, solo nos da para los aspectos teóricos. En el siguiente artículo, analizaremos la construcción práctica de un algoritmo de búsqueda de reglas asociativas usando MQL5. Asimismo, evaluaremos su rendimiento en la resolución de un problema comercial práctico.

Enlaces

1. Redes neuronales: así de sencillo (Parte 14): Clusterización de datos
2. Redes neuronales: así de sencillo (Parte 15): Clusterización de datos usando MQL5
3. Redes neuronales: así de sencillo (Parte 16): Uso práctico de la clusterización
4. Redes neuronales: así de sencillo (Parte 17): Reducción de la dimensionalidad
5. Fast Algorithms for Mining Association Rules
6. Mining Frequent Patterns without Candidate Generation