49  Patrones Secuenciales: GSP y PrefixSpan

Hasta ahora una transacción ha sido un conjunto: el ticket \(\{\text{pan}, \text{leche}\}\) es el mismo que \(\{\text{leche}, \text{pan}\}\). Pero en muchos datos el orden es la información principal. En una tienda en línea, pasar de la búsqueda a la ficha del producto y luego al carrito describe un recorrido de compra; recorrer las mismas páginas al revés describe otra cosa. Lo mismo ocurre con las compras sucesivas de un cliente (primero la impresora, meses después los cartuchos), los eventos de un expediente clínico o los pasos de un proceso registrados en una bitácora. La minería de patrones secuenciales busca las subsecuencias de eventos que se repiten en muchas secuencias (Agrawal y Srikant 1995; Han et al. 2012).

En el almacén de datos, la materia prima es la misma tabla de hechos que en los capítulos anteriores, pero ahora se agrupa por cliente o por sesión y se ordena por fecha: una tabla de hechos de eventos web (clickstream) con llave de sesión, página y marca de tiempo produce directamente una secuencia por sesión.

49.1 Intuición: cinco sesiones de una tienda en línea

Una tienda en línea registró cinco sesiones. Cada letra es una página visitada, en orden:

Sesión	Recorrido	Abreviado
\(S_1\)	inicio → búsqueda → ficha → carrito → pago	⟨I, B, F, C, P⟩
\(S_2\)	inicio → ficha → búsqueda → ficha → carrito	⟨I, F, B, F, C⟩
\(S_3\)	búsqueda → ficha → carrito → pago	⟨B, F, C, P⟩
\(S_4\)	inicio → búsqueda → ficha → ficha	⟨I, B, F, F⟩
\(S_5\)	inicio → carrito → pago	⟨I, C, P⟩

Tabla 49.1: Cinco sesiones de navegación (I = inicio, B = búsqueda, F = ficha de producto, C = carrito, P = pago).

Algunas observaciones sin fórmulas:

• El recorrido búsqueda → ficha → carrito aparece en tres sesiones (\(S_1\), \(S_2\), \(S_3\)). Es un patrón de compra.
• Buscar y ver una ficha ocurre en cuatro sesiones, pero ver una ficha y después buscar solo en una (\(S_2\)). Como conjuntos, \(\{B, F\}\) es lo mismo en ambos casos; como secuencias, son patrones distintos con frecuencias muy diferentes.
• En \(S_1\), el patrón inicio → carrito aparece aunque haya páginas en medio. Un patrón secuencial respeta el orden, pero admite huecos.

49.2 Construcción numérica paso a paso

49.2.1 Contención y soporte

Una sesión contiene un patrón si se pueden encontrar sus páginas en la sesión, en el mismo orden, aunque haya otras páginas entre ellas. Por ejemplo, ⟨I, C⟩ está en \(S_1 = ⟨\mathbf{I}, B, F, \mathbf{C}, P⟩\), en \(S_2\) y en \(S_5\), pero no en \(S_3\) (no tiene inicio) ni en \(S_4\) (no tiene carrito): su conteo de soporte es 3. Una sesión cuenta una sola vez aunque contenga el patrón varias veces: ⟨F⟩ aparece dos veces en \(S_2\) y en \(S_4\), y su conteo es 4, no 6.

Fijamos un conteo mínimo de 3 sesiones. Las cinco páginas son frecuentes: I, B, F y C aparecen en 4 sesiones y P en 3.

49.2.2 PrefixSpan: crecer el patrón desde un prefijo

La idea de PrefixSpan (Pei et al. 2001) es la de FP-Growth aplicada al orden: en lugar de generar candidatos, fija un prefijo y mira solo lo que ocurre después de él. Para cada sesión que contiene el prefijo se guarda el sufijo que sigue a su primera aparición; el conjunto de esos sufijos es la base proyectada.

Prefijo ⟨B⟩. Cortamos cada sesión después de su primera búsqueda:

Sesión	Sesión completa	Sufijo después de B
\(S_1\)	⟨I, B, F, C, P⟩	⟨F, C, P⟩
\(S_2\)	⟨I, F, B, F, C⟩	⟨F, C⟩
\(S_3\)	⟨B, F, C, P⟩	⟨F, C, P⟩
\(S_4\)	⟨I, B, F, F⟩	⟨F, F⟩
\(S_5\)	⟨I, C, P⟩	(no contiene B)

Tabla 49.2: Base proyectada sobre el prefijo ⟨B⟩.

En los sufijos, F aparece en 4, C en 3 y P en 2. Por lo tanto ⟨B, F⟩ (4) y ⟨B, C⟩ (3) son frecuentes y ⟨B, P⟩ (2) no. Observa que no hubo que volver a recorrer las sesiones completas: el conteo de la extensión se hace dentro de la base proyectada.

Prefijo ⟨B, F⟩. Proyectamos de nuevo, ahora sobre los sufijos: ⟨C, P⟩, ⟨C⟩, ⟨C, P⟩ y ⟨F⟩. C aparece en 3, P en 2 y F en 1: solo ⟨B, F, C⟩ (3) es frecuente.

Prefijo ⟨B, F, C⟩. Los sufijos son ⟨P⟩ (\(S_1\)), vacío (\(S_2\)) y ⟨P⟩ (\(S_3\)). P aparece en 2: no hay extensión frecuente y esta rama termina. Lo mismo ocurre con ⟨B, C⟩, cuyos sufijos son ⟨P⟩, vacío y ⟨P⟩.

Repitiendo el procedimiento para los otros prefijos de longitud 1:

Prefijo	Base proyectada	Extensiones frecuentes
⟨I⟩	⟨B,F,C,P⟩, ⟨F,B,F,C⟩, ⟨B,F,F⟩, ⟨C,P⟩	⟨I,B⟩ (3), ⟨I,F⟩ (3), ⟨I,C⟩ (3)
⟨I, B⟩	⟨F,C,P⟩, ⟨F,C⟩, ⟨F,F⟩	⟨I,B,F⟩ (3)
⟨I, F⟩	⟨C,P⟩, ⟨B,F,C⟩, ⟨F⟩	ninguna (C y F llegan a 2)
⟨F⟩	⟨C,P⟩, ⟨B,F,C⟩, ⟨C,P⟩, ⟨F⟩	⟨F,C⟩ (3)
⟨C⟩	⟨P⟩, vacío, ⟨P⟩, ⟨P⟩	⟨C,P⟩ (3)
⟨P⟩	vacío en las tres sesiones	ninguna

Tabla 49.3: Bases proyectadas del resto de los prefijos (conteo mínimo 3).

El resultado completo son 14 patrones secuenciales frecuentes: 5 de longitud 1 (I, B, F, C, P), 7 de longitud 2 (⟨I,B⟩, ⟨I,F⟩, ⟨I,C⟩, ⟨B,F⟩, ⟨B,C⟩, ⟨F,C⟩, ⟨C,P⟩) y 2 de longitud 3 (⟨I,B,F⟩ y ⟨B,F,C⟩). Igual que con los itemsets, muchos son redundantes; los maximales son cuatro: ⟨I,B,F⟩, ⟨B,F,C⟩, ⟨I,C⟩ y ⟨C,P⟩.

49.2.3 GSP: la alternativa por niveles

GSP (Srikant y Agrawal 1996) es la versión secuencial de Apriori. En cada nivel genera candidatos, los poda con la propiedad antimonótona y recorre toda la base para contarlos:

• Nivel 2. Con 5 páginas frecuentes hay \(5 \times 5 = 25\) candidatos, porque el orden importa y una página puede repetirse (⟨F, F⟩ es un candidato válido). Con itemsets serían solo 10 pares. Resultan frecuentes los 7 pares de arriba.
• Nivel 3. Se unen dos patrones cuando el primero sin su primer elemento coincide con el segundo sin su último elemento¹: ⟨I,B⟩ + ⟨B,F⟩ → ⟨I,B,F⟩. Salen 7 candidatos; la poda descarta 3 (por ejemplo ⟨I,C,P⟩, porque ⟨I,P⟩ no es frecuente) y se cuentan 4, de los cuales 2 son frecuentes.
• Nivel 4. ⟨I,B,F⟩ + ⟨B,F,C⟩ → ⟨I,B,F,C⟩, que se poda porque ⟨I,B,C⟩ no es frecuente. Fin.

¹ En GSP original, la poda revisa solo las subsecuencias contiguas de longitud \(k-1\) (las que se obtienen quitando el primer o el último elemento, o un ítem de un elemento interior). La razón es que, con una restricción de hueco máximo, quitar un evento interior puede crear un hueco demasiado grande y la antimonotonía deja de valer para esas subsecuencias. Sin restricciones de tiempo, como aquí, se pueden revisar todas las subsecuencias de longitud \(k-1\), lo que poda más.

GSP cuenta \(5 + 25 + 4 = 34\) candidatos y recorre la base tres veces. PrefixSpan llega a los mismos 14 patrones sin generar ningún candidato que no aparezca en los datos.

49.3 Formalización

Sea \(\mathcal{E}\) el conjunto de eventos posibles (páginas, productos, diagnósticos) y \(\mathcal{S} = \{s_1, \ldots, s_n\}\) una base de secuencias.

Definición (secuencia y subsecuencia). Una secuencia es una lista ordenada \(s = ⟨e_1, e_2, \ldots, e_\ell⟩\) con \(e_j \in \mathcal{E}\); su longitud es \(\ell\). Una secuencia \(\alpha = ⟨a_1, \ldots, a_k⟩\) es subsecuencia de \(s\), y se escribe \(\alpha \sqsubseteq s\), si existen posiciones \(j_1 < j_2 < \cdots < j_k\) tales que \(a_r = e_{j_r}\) para todo \(r\).

Definición (soporte de un patrón secuencial). El conteo de soporte de \(\alpha\) es el número de secuencias que lo contienen, \[\sigma(\alpha) = |\{s \in \mathcal{S} : \alpha \sqsubseteq s\}|, \tag{49.1}\] y \(\alpha\) es un patrón secuencial frecuente si \(\sigma(\alpha) \ge \sigma_{\min}\).

En la definición original (Agrawal y Srikant 1995) cada elemento de la secuencia es a su vez un itemset (los productos comprados en una misma visita)². Aquí usamos un evento por posición, que es el caso más común en clickstream y bitácoras.

² En el caso general, una secuencia es una lista de itemsets, por ejemplo ⟨(impresora, papel), (cartuchos)⟩: en la primera visita se compraron dos productos juntos y en la segunda, uno. La contención exige que cada elemento del patrón esté incluido en un elemento distinto de la secuencia, respetando el orden. PrefixSpan maneja este caso distinguiendo dos tipos de extensión: agregar un ítem al último elemento o agregar un elemento nuevo.

Antimonotonía. Si \(\alpha \sqsubseteq \beta\), toda secuencia que contiene a \(\beta\) contiene a \(\alpha\), así que \(\sigma(\beta) \le \sigma(\alpha)\). Es la misma propiedad de los itemsets y es la que justifica la poda de GSP. Lo que cambia es el tamaño del espacio de búsqueda: con \(m\) eventos hay \(m^k\) secuencias posibles de longitud \(k\), frente a \(\binom{m}{k}\) itemsets, y las secuencias pueden ser más largas que el número de eventos distintos.

Proyección. Sea \(\alpha\) un prefijo. Para cada \(s \sqsupseteq \alpha\), el sufijo \(s|_\alpha\) es lo que queda de \(s\) después de la aparición de \(\alpha\) que termina más a la izquierda³. La base proyectada es \(\mathcal{S}|_\alpha = \{s|_\alpha : s \in \mathcal{S},\ \alpha \sqsubseteq s\}\). El resultado que hace funcionar a PrefixSpan (Pei et al. 2004) es: \[\sigma_{\mathcal{S}}(\alpha \cdot x) = \big|\{u \in \mathcal{S}|_\alpha : x \in u\}\big|, \tag{49.2}\] donde \(\alpha \cdot x\) agrega el evento \(x\) al final de \(\alpha\). Es decir, el soporte de cada extensión se obtiene contando eventos en la base proyectada, que es más pequeña que la original y se encoge con cada paso.

³ Usar la aparición que termina más a la izquierda deja el sufijo más largo posible, así que no se pierde ninguna extensión. En \(S_2 = ⟨I, F, B, F, C⟩\) con prefijo ⟨F⟩, el sufijo es ⟨B, F, C⟩ y no ⟨C⟩; con el segundo se perdería la extensión ⟨F, B⟩.

Algoritmo PrefixSpan. Llamar a PrefixSpan(⟨⟩, 𝒮):

1. Contar, en la base actual, en cuántas secuencias aparece cada evento.
2. Para cada evento \(x\) con conteo \(\ge \sigma_{\min}\): reportar \(\alpha \cdot x\), construir \(\mathcal{S}|_{\alpha \cdot x}\) y llamar recursivamente a PrefixSpan(α·x, 𝒮|α·x).

	GSP	PrefixSpan	SPADE
Estrategia	Por niveles (anchura)	Crecimiento de patrones (profundidad)	Profundidad o anchura sobre listas de ocurrencias
Candidatos	Genera y poda	No genera	Une listas de identificadores
Recorridos de la base	Uno por nivel	Uno por proyección (sobre bases cada vez menores)	Uno, para construir la representación vertical
Restricciones de tiempo	Sí (hueco máximo, ventana)	Con adaptaciones	Con adaptaciones
Referencia	Srikant y Agrawal (1996)	Pei et al. (2001)	Zaki (2001)

Tabla 49.4: Algoritmos clásicos de patrones secuenciales.

GSP admite de forma natural restricciones de tiempo⁴, como exigir que entre dos eventos no pasen más de 30 minutos. Esa flexibilidad es la razón por la que su poda usa subsecuencias contiguas, como se explica en la nota sobre la unión.

⁴ Las restricciones más comunes son el hueco mínimo y máximo entre eventos consecutivos del patrón, la ventana deslizante (eventos cercanos en el tiempo se tratan como simultáneos) y la duración máxima del patrón completo. Todas reducen el número de patrones y los hacen más interpretables.

49.4 Laboratorio: la base proyectada de PrefixSpan

El laboratorio reproduce el recorrido de PrefixSpan sobre las sesiones de la Tabla 49.1. Elige un evento para extender el prefijo y observa cómo se encoge la base proyectada; las barras cuentan en cuántos sufijos aparece cada evento. Al final puedes editar las sesiones.

Laboratorio · Patrones secuenciales

¿Qué ocurre después del prefijo?

Extiende el prefijo con un evento frecuente, retrocede o salta a cualquier patrón de la lista.

Conteo mínimo:

Prefijo actual:

Soporte del prefijo

Sufijos no vacíos

Extensiones frecuentes

Patrones frecuentes (total)

Base proyectada

aparición del prefijo más a la izquierda sufijo proyectado

¿En cuántos sufijos aparece cada evento?

extensión frecuente no alcanza el mínimo conteo mínimo

Todos los patrones frecuentes (clic para saltar)

Editar las sesiones (letras I, B, F, C, P)

Guía del laboratorio.

1. El laboratorio empieza con el prefijo ⟨B⟩. Comprueba la Tabla 49.2: los sufijos y los conteos F = 4, C = 3 y P = 2.
2. Predice antes de hacer clic: si extiendes a ⟨B, F⟩, ¿cuántas extensiones frecuentes quedarán? Comprueba y sigue hasta que la rama termine. ¿Por qué el sufijo de \(S_2\) queda vacío en ⟨B, F, C⟩?
3. Ve a ⟨F⟩ con la lista de patrones. En \(S_2\), ¿por qué el sufijo es ⟨B, F, C⟩ y no ⟨C⟩? (Pista: aparición más a la izquierda.)
4. Baja el conteo mínimo a 2. ¿Cuántos patrones hay ahora y cuál es el más largo? Sube a 4: ¿qué patrón de longitud 2 sobrevive?
5. Rómpelo: cambia \(S_4\) a IBFC. Antes de mirar, ¿qué patrones nuevos deberían volverse frecuentes con conteo mínimo 3? (Deberías encontrar tres, y uno de ellos tiene longitud 4.) ¿Cuál es ahora el soporte de ⟨B, F, C⟩?

49.5 Implementación en Python

49.5.1 Contención y soporte

sesiones = [list("IBFCP"), list("IFBFC"), list("BFCP"), list("IBFF"), list("ICP")]

def contiene(patron, secuencia):
    """¿Es `patron` subsecuencia de `secuencia`? (mismo orden, se permiten huecos)"""
    it = iter(secuencia)
    return all(e in it for e in patron)   # `in` consume el iterador: garantiza el orden

def soporte(patron, base):
    return sum(contiene(patron, s) for s in base)

for p in [("B", "F"), ("F", "B"), ("I", "C"), ("B", "F", "C"), ("F",)]:
    print(f"⟨{', '.join(p)}⟩: {soporte(p, sesiones)} sesiones")

⟨B, F⟩: 4 sesiones
⟨F, B⟩: 1 sesiones
⟨I, C⟩: 3 sesiones
⟨B, F, C⟩: 3 sesiones
⟨F⟩: 4 sesiones

El truco de contiene es que e in it avanza el iterador hasta encontrar e; la siguiente búsqueda empieza donde terminó la anterior, así que el orden se respeta sin manejar índices.

49.5.2 PrefixSpan desde cero

La implementación sigue literalmente el algoritmo: contar eventos en la base actual, y para cada evento frecuente reportar el patrón, proyectar y llamar recursivamente. El parámetro traza imprime el recorrido para compararlo con las tablas de la sección manual.

from collections import Counter

def proyectar(base, evento):
    """Sufijos después de la primera aparición de `evento` en cada secuencia que lo contiene."""
    return [s[s.index(evento) + 1:] for s in base if evento in s]

def prefixspan(base, min_conteo, prefijo=(), traza=False):
    patrones = []
    conteos = Counter(e for s in base for e in set(s))   # cada secuencia cuenta una vez
    for evento in sorted(conteos):
        if conteos[evento] < min_conteo:
            continue
        nuevo = prefijo + (evento,)
        patrones.append((nuevo, conteos[evento]))
        proyectada = proyectar(base, evento)
        if traza:
            sufijos = ", ".join("⟨" + ",".join(s) + "⟩" if s else "vacío" for s in proyectada)
            print(f"{'  ' * len(prefijo)}⟨{','.join(nuevo)}⟩ ({conteos[evento]}) -> {sufijos}")
        patrones += prefixspan([s for s in proyectada if s], min_conteo, nuevo, traza)
    return patrones

patrones = prefixspan(sesiones, min_conteo=3, traza=True)
print(f"\n{len(patrones)} patrones secuenciales frecuentes")

⟨B⟩ (4) -> ⟨F,C,P⟩, ⟨F,C⟩, ⟨F,C,P⟩, ⟨F,F⟩
  ⟨B,C⟩ (3) -> ⟨P⟩, vacío, ⟨P⟩
  ⟨B,F⟩ (4) -> ⟨C,P⟩, ⟨C⟩, ⟨C,P⟩, ⟨F⟩
    ⟨B,F,C⟩ (3) -> ⟨P⟩, vacío, ⟨P⟩
⟨C⟩ (4) -> ⟨P⟩, vacío, ⟨P⟩, ⟨P⟩
  ⟨C,P⟩ (3) -> vacío, vacío, vacío
⟨F⟩ (4) -> ⟨C,P⟩, ⟨B,F,C⟩, ⟨C,P⟩, ⟨F⟩
  ⟨F,C⟩ (3) -> ⟨P⟩, vacío, ⟨P⟩
⟨I⟩ (4) -> ⟨B,F,C,P⟩, ⟨F,B,F,C⟩, ⟨B,F,F⟩, ⟨C,P⟩
  ⟨I,B⟩ (3) -> ⟨F,C,P⟩, ⟨F,C⟩, ⟨F,F⟩
    ⟨I,B,F⟩ (3) -> ⟨C,P⟩, ⟨C⟩, ⟨F⟩
  ⟨I,C⟩ (3) -> ⟨P⟩, vacío, ⟨P⟩
  ⟨I,F⟩ (3) -> ⟨C,P⟩, ⟨B,F,C⟩, ⟨F⟩
⟨P⟩ (3) -> vacío, vacío, vacío

14 patrones secuenciales frecuentes

La sangría de la traza es el árbol de búsqueda: cada línea es un prefijo frecuente y, a su derecha, su base proyectada. Las secuencias vacías se descartan antes de la llamada recursiva porque no pueden aportar extensiones.

49.5.3 GSP desde cero, para comparar

import pandas as pd

def gsp(base, min_conteo):
    eventos = sorted({e for s in base for e in s})
    nivel = [(e,) for e in eventos if soporte((e,), base) >= min_conteo]
    resultado, resumen = list(nivel), [{"nivel": 1, "candidatos contados": len(eventos), "frecuentes": len(nivel)}]
    k = 1
    while nivel:
        previos = set(nivel)
        if k == 1:   # todos los pares ordenados, con repetición
            candidatos = [a + b for a in nivel for b in nivel]
        else:        # unión: a sin su primer elemento == b sin su último
            candidatos = [a + b[-1:] for a in nivel for b in nivel if a[1:] == b[:-1]]
            candidatos = [c for c in candidatos   # poda por antimonotonía
                          if all(c[:i] + c[i + 1:] in previos for i in range(len(c)))]
        nivel = [c for c in candidatos if soporte(c, base) >= min_conteo]   # un recorrido de la base
        resultado += nivel
        k += 1
        resumen.append({"nivel": k, "candidatos contados": len(candidatos), "frecuentes": len(nivel)})
    return resultado, pd.DataFrame(resumen)

patrones_gsp, resumen_gsp = gsp(sesiones, min_conteo=3)
print("¿Mismos patrones que PrefixSpan?", set(patrones_gsp) == {p for p, _ in patrones})
resumen_gsp

¿Mismos patrones que PrefixSpan? True

	nivel	candidatos contados	frecuentes
0	1	5	5
1	2	25	7
2	3	4	2
3	4	0	0

Los dos algoritmos son exactos: cambian el camino, no la respuesta. GSP cuenta 34 candidatos con un recorrido completo de la base por nivel; PrefixSpan solo cuenta eventos que efectivamente aparecen en cada base proyectada.

49.5.4 Patrones maximales y cerrados

Las definiciones del capítulo de itemsets cerrados y maximales se trasladan sin cambios, reemplazando \(\subseteq\) por \(\sqsubseteq\): un patrón es cerrado si ninguna supersecuencia tiene el mismo soporte y maximal si ninguna supersecuencia es frecuente (Yan et al. 2003).

def condensar(patrones):
    soporte_de = dict(patrones)
    filas = []
    for p, c in patrones:
        mayores = [q for q in soporte_de if len(q) == len(p) + 1 and contiene(p, q)]
        filas.append({"patrón": "⟨" + ", ".join(p) + "⟩", "conteo": c,
                      "cerrado": all(soporte_de[q] < c for q in mayores),
                      "maximal": not mayores})
    return pd.DataFrame(filas)

condensado = condensar(patrones)
print(f"{len(condensado)} frecuentes | {condensado['cerrado'].sum()} cerrados | {condensado['maximal'].sum()} maximales")
condensado[condensado["cerrado"]].sort_values("conteo", ascending=False)

14 frecuentes | 7 cerrados | 4 maximales

	patrón	conteo	cerrado	maximal
2	⟨B, F⟩	4	True	False
4	⟨C⟩	4	True	False
8	⟨I⟩	4	True	False
3	⟨B, F, C⟩	3	True	True
5	⟨C, P⟩	3	True	True
10	⟨I, B, F⟩	3	True	True
11	⟨I, C⟩	3	True	True

Como en los itemsets, basta revisar las supersecuencias con un evento más: si una supersecuencia lejana tuviera el mismo soporte, también lo tendrían todas las intermedias.

49.6 Ejemplo práctico: clickstream de una tienda en línea

Simulamos 2 000 sesiones de una tienda en línea con una cadena de Markov⁵: desde cada página, la siguiente se elige con probabilidades fijas, y en cualquier momento el visitante puede salir. La pregunta de negocio es qué recorridos son frecuentes y cuáles se asocian con una compra.

⁵ Una cadena de Markov es un proceso en el que la probabilidad del siguiente estado depende solo del estado actual, no de la historia completa. Aquí, la probabilidad de ir a «carrito» depende solo de la página en la que está el visitante. Es un modelo simple que basta para generar recorridos realistas.

import numpy as np

rng = np.random.default_rng(11)
transiciones = {
    "inicio":    {"búsqueda": .45, "categoría": .35, "ofertas": .10, "salida": .10},
    "búsqueda":  {"ficha": .65, "búsqueda": .15, "salida": .20},
    "categoría": {"ficha": .55, "categoría": .15, "búsqueda": .10, "salida": .20},
    "ofertas":   {"ficha": .55, "salida": .45},
    "ficha":     {"reseñas": .25, "carrito": .30, "ficha": .15, "búsqueda": .10, "salida": .20},
    "reseñas":   {"carrito": .50, "ficha": .25, "salida": .25},
    "carrito":   {"pago": .55, "ficha": .15, "salida": .30},
    "pago":      {"salida": 1.0},
}

def simular_sesion(max_paginas=12):
    sesion = ["inicio"]
    while len(sesion) < max_paginas:
        opciones = transiciones[sesion[-1]]
        siguiente = str(rng.choice(list(opciones), p=list(opciones.values())))
        if siguiente == "salida":
            break
        sesion.append(siguiente)
    return sesion

clickstream = [simular_sesion() for _ in range(2000)]
compra = np.array(["pago" in s for s in clickstream])
print(f"{len(clickstream)} sesiones | longitud media {np.mean([len(s) for s in clickstream]):.1f} páginas"
      f" | conversión {compra.mean():.1%}")
for s in clickstream[:4]:
    print("  " + " → ".join(s))

2000 sesiones | longitud media 4.2 páginas | conversión 25.3%
  inicio → búsqueda → ficha → ficha → reseñas → carrito
  inicio → búsqueda → ficha
  inicio → categoría → ficha → carrito → ficha → carrito → pago
  inicio → categoría → ficha

Con un soporte mínimo de 5 % (100 sesiones), PrefixSpan encuentra todos los recorridos frecuentes en una fracción de segundo. Como todas las sesiones empiezan en «inicio», cada patrón aparece también con «inicio» delante y con el mismo soporte: es exactamente la redundancia que eliminan los patrones cerrados.

import time

t0 = time.perf_counter()
frecuentes_web = prefixspan(clickstream, min_conteo=100)
t1 = time.perf_counter()
cerrados_web = condensar(frecuentes_web)
print(f"{len(frecuentes_web)} patrones frecuentes en {t1 - t0:.2f} s | "
      f"{cerrados_web['cerrado'].sum()} cerrados | {cerrados_web['maximal'].sum()} maximales")

155 patrones frecuentes en 0.01 s | 48 cerrados | 17 maximales

Para cada patrón cerrado de longitud 2 o más que no incluye el pago, calculamos la tasa de conversión de las sesiones que lo contienen y la comparamos con la conversión global. Es la misma lógica del lift de los capítulos de reglas, aplicada a la regla «recorrido ⇒ compra».

import plotly.express as px

filas = []
for p, c in frecuentes_web:
    if len(p) < 2 or "pago" in p:
        continue
    if not cerrados_web.loc[cerrados_web["patrón"] == "⟨" + ", ".join(p) + "⟩", "cerrado"].item():
        continue
    tiene = np.array([contiene(p, s) for s in clickstream])
    filas.append({"patrón": " → ".join(p), "soporte": c / len(clickstream),
                  "conversión": compra[tiene].mean(), "longitud": len(p)})
recorridos = pd.DataFrame(filas)
recorridos["lift"] = recorridos["conversión"] / compra.mean()

fig = px.scatter(recorridos, x="soporte", y="conversión", size="longitud", hover_name="patrón",
                 hover_data={"lift": ":.2f", "longitud": True}, color="lift",
                 color_continuous_scale=["#94a3b8", "#2563eb"], size_max=14)
fig.add_hline(y=compra.mean(), line_dash="dash", line_color="#dc2626",
              annotation_text=f"conversión global {compra.mean():.0%}")
fig.update_layout(height=420, xaxis_tickformat=".0%", yaxis_tickformat=".0%")
fig.show()

Figura 49.1: Patrones secuenciales cerrados del clickstream (sin la página de pago). Eje horizontal: soporte; eje vertical: tasa de conversión de las sesiones que contienen el patrón. La línea discontinua es la conversión global. Los recorridos que pasan por el carrito convierten más del doble que el promedio; los que pasan por las reseñas sin llegar al carrito quedan en un punto intermedio.

recorridos.sort_values("lift", ascending=False).head(8).round(3)

	patrón	soporte	conversión	longitud	lift
30	inicio → ficha → ficha → carrito	0.138	0.625	4	2.472
27	inicio → ficha → carrito	0.406	0.622	3	2.460
8	inicio → búsqueda → ficha → ficha → carrito	0.086	0.614	5	2.427
36	inicio → ficha → reseñas → carrito	0.159	0.607	4	2.399
19	inicio → categoría → ficha → carrito	0.164	0.605	4	2.391
6	inicio → búsqueda → ficha → carrito	0.248	0.602	4	2.380
21	inicio → categoría → ficha → ficha → carrito	0.054	0.589	5	2.327
23	inicio → categoría → ficha → reseñas → carrito	0.069	0.587	5	2.320

Tabla 49.5: Recorridos cerrados con mayor lift sobre la conversión (soporte ≥ 5 %).

Dos advertencias al leer estos resultados. Primero, son descriptivos: que las sesiones que pasan por el carrito conviertan más no significa que llevar a alguien al carrito cause la compra; en buena parte, quien ya decidió comprar es quien llega al carrito. Segundo, en datos reales el soporte mínimo y la definición de sesión (¿30 minutos de inactividad?, ¿un día?) cambian por completo los patrones, igual que la definición de transacción en los capítulos anteriores.

En producción no hace falta la implementación propia: pyspark.ml.fpm.PrefixSpan ejecuta el mismo algoritmo de forma distribuida en Spark, y bibliotecas como SPMF reúnen decenas de variantes (Fournier-Viger et al. 2017).

49.7 Ventajas y limitaciones

Aspecto	Patrones secuenciales
Qué aportan	Orden y recorridos, no solo coocurrencia
Espacio de búsqueda	Mucho mayor que el de itemsets (\(m^k\) frente a \(\binom{m}{k}\))
Algoritmo recomendado	PrefixSpan (o SPADE) en general; GSP si hay restricciones de tiempo
Riesgo principal	Explosión de patrones redundantes: conviene reportar cerrados o maximales
Decisiones críticas	Definición de sesión, granularidad del evento, soporte mínimo
Interpretación	Descriptiva; para predecir el siguiente paso se usan modelos secuenciales (cadenas de Markov, redes recurrentes)

Tabla 49.6: Resumen de la minería de patrones secuenciales.

Referencias

Agrawal, Rakesh, y Ramakrishnan Srikant. 1995. «Mining Sequential Patterns». Proceedings of the Eleventh International Conference on Data Engineering (ICDE), 3-14.

Fournier-Viger, Philippe, Jerry Chun-Wei Lin, Rage Uday Kiran, Yun Sing Koh, y Rincy Thomas. 2017. «A Survey of Sequential Pattern Mining». Data Science and Pattern Recognition 1 (1): 54-77.

Han, Jiawei, Micheline Kamber, y Jian Pei. 2012. Data Mining: Concepts and Techniques. 3.ª ed. Morgan Kaufmann.

Pei, Jian, Jiawei Han, Behzad Mortazavi-Asl, et al. 2001. «PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth». Proceedings of the 17th International Conference on Data Engineering (ICDE), 215-24.

Pei, Jian, Jiawei Han, Behzad Mortazavi-Asl, et al. 2004. «Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach». IEEE Transactions on Knowledge and Data Engineering 16 (11): 1424-40.

Srikant, Ramakrishnan, y Rakesh Agrawal. 1996. «Mining Sequential Patterns: Generalizations and Performance Improvements». Advances in Database Technology – EDBT’96, Lecture Notes en Computer Science, vol. 1057: 1-17.

Yan, Xifeng, Jiawei Han, y Ramin Afshar. 2003. «CloSpan: Mining Closed Sequential Patterns in Large Datasets». Proceedings of the 2003 SIAM International Conference on Data Mining, 166-77.

Zaki, Mohammed J. 2001. «SPADE: An Efficient Algorithm for Mining Frequent Sequences». Machine Learning 42 (1–2): 31-60.