Comparison of Outlier Detection Algorithms on String Data

Esta tesis compara dos algoritmos de detección de valores atípicos en datos de texto: una variante del factor de outlier local adaptada con una medida de Levenshtein ponderada y un nuevo método basado en expresiones regulares jerárquicas, demostrando que el primero es más eficaz cuando las distancias de edición son distintivas, mientras que el segundo sobresale cuando los valores esperados tienen una estructura claramente diferente a la de los outliers.

Lo esencial

¡Hola! Imagina que tienes una biblioteca gigante llena de libros escritos en un idioma extraño (sonidos, números y letras mezclados). Tu trabajo es encontrar los libros que no deberían estar ahí: los que están escritos en otro idioma, los que tienen páginas arrancadas o los que son simplemente una broma.

Esta tesis de Philip Maus es como un manual de instrucciones para dos "detectives" diferentes que intentan encontrar esos libros raros en una pila de texto. Aquí te explico cómo funcionan estos detectives usando analogías sencillas:

El Problema: ¿Cómo detectar lo raro en el texto?

La mayoría de los programas de inteligencia artificial son expertos encontrando números raros (como un precio de un producto que es 1 millón de dólares cuando lo normal es 10). Pero, ¿qué pasa si los datos son palabras o frases? Como "2023-01-01" (una fecha) o "Bonn" (una ciudad). Los números no sirven aquí, necesitamos detectives que entiendan el idioma y la estructura de las palabras.

El autor prueba dos detectives distintos:

---

Detective 1: El "Vecino Sospechoso" (Algoritmo LOF)

La Analogía: Imagina una fiesta llena de gente. La mayoría de los invitados se visten de manera similar (por ejemplo, todos llevan traje). De repente, llega alguien con un traje de payaso o una capa de superhéroe.

• Cómo funciona: Este detective mira a cada persona y le pregunta: "¿Quién te rodea?". Si estás en un grupo donde todos se parecen mucho entre sí, eres "normal". Pero si estás rodeado de gente que se parece a ti, pero tú eres muy diferente de ellos (o si estás solo en un rincón muy lejos de todos), el detective te marca como sospechoso.
• El truco especial: Para medir qué tan diferente es alguien, el detective usa una "regla de edición" llamada Levenshtein. Imagina que es como contar cuántas letras tienes que borrar o cambiar para que una palabra se parezca a otra.
  • Ejemplo: Cambiar una "a" por una "e" es un cambio pequeño (como cambiar una corbata azul por una roja). Pero cambiar una letra por un número es un cambio enorme (como cambiar un traje por una capa de superhéroe).
  • El autor creó una regla de edición inteligente que entiende que cambiar una letra por otra es "barato", pero cambiar una letra por un símbolo raro es "caro". Esto ayuda a detectar mejor a los intrusos.

Cuándo es bueno: Cuando los datos normales tienen una estructura muy clara y los "raros" son simplemente versiones un poco torcidas de lo normal (como fechas escritas mal o códigos postales con letras).

---

Detective 2: El "Arquitecto de Plantillas" (Algoritmo HiLRE)

La Analogía: Imagina que tienes una plantilla de galletas. La plantilla solo deja pasar galletas con forma de estrella. Si intentas meter una galleta cuadrada o triangular, la plantilla se niega a dejarla pasar.

• Cómo funciona: Este detective intenta crear la plantilla perfecta (un "expresión regular") que describa exactamente cómo se ven los datos normales.
  • Si los datos son códigos postales alemanes, el detective aprende que la plantilla debe ser: "Cinco dígitos numéricos".
  • Luego, toma todos los datos y los pasa por la plantilla. Si una palabra no encaja en la plantilla, ¡es un intruso!
• El truco especial: A veces, la plantilla puede ser demasiado estricta (solo acepta galletas de 5cm) o demasiado floja (acepta cualquier forma). El autor añadió un "botón de ajuste" para decirle al detective: "Oye, asegúrate de que tu plantilla acepte al menos al 80% de la gente, pero no aceptes a los raros".

Cuándo es bueno: Cuando los datos normales tienen una estructura muy rígida y predecible (como fechas, horas o códigos postales). Es excelente si sabes exactamente cómo deberían verse los datos.

---

La Gran Prueba: ¿Quién gana?

El autor puso a los dos detectives a trabajar con datos reales de hospitales alemanes (direcciones, fechas, números de teléfono).

1. Caso 1: Códigos postales vs. Nombres de ciudades.

   • Los códigos postales son siempre 5 números. Los nombres de ciudades son letras y tienen longitudes variadas.
   • Resultado: El Arquitecto de Plantillas fue un genio. Creó una plantilla de "5 números" y rechazó todo lo demás. El Vecino Sospechoso también lo hizo bien, pero a veces se confundía si un nombre de ciudad tenía exactamente 5 letras.

2. Caso 2: Nombres de ciudades vs. Códigos postales.

   • Aquí, los "datos normales" eran nombres de ciudades (muy variados, largos, cortos, con paréntesis).
   • Resultado: El Arquitecto de Plantillas se rindió. No pudo crear una plantilla que cubriera todos los nombres de ciudades sin incluir también a los códigos postales. Se volvió confuso. El Vecino Sospechoso tampoco lo hizo muy bien porque los nombres de ciudades son tan variados que es difícil saber quién es "normal" y quién es "raro".

3. Caso 3: Códigos postales vs. Números de teléfono y casas.

   • Aquí, los datos normales son 5 números. Los raros son números de teléfono (más largos) o direcciones de casas (con letras).
   • Resultado: El Vecino Sospechoso ganó. Como los números de teléfono son más largos, el detective vio que estaban "lejos" de la mayoría de los códigos postales y los marcó. El Arquitecto se confundió porque ambos son números y le costó distinguirlos.

Conclusión Simple

No existe un detective perfecto para todo.

• Si tus datos son como fichas de dominó (todos siguen una regla estricta, como fechas o códigos), usa al Arquitecto de Plantillas. Es muy preciso y no se equivoca mucho.
• Si tus datos son como una pila de ropa usada (tienen una forma general, pero varían en tamaño y detalles), usa al Vecino Sospechoso. Es mejor para encontrar lo que se sale de la norma por su tamaño o composición, aunque a veces marque a gente inocente.

El trabajo de Philip Maus nos enseña que, para limpiar datos o encontrar errores en textos, primero debemos entender si los datos son "rígidos" o "flexibles" para elegir al detective adecuado.

Resumen técnico

Aquí presento un resumen técnico detallado de la tesis de grado "Comparación de Algoritmos de Detección de Valores Atípicos en Datos de Cadenas" (Comparison of Outlier Detection Algorithms on String Data) de Philip Maus.

1. Planteamiento del Problema

La detección de valores atípicos (outliers) es un problema fundamental en el aprendizaje automático y la ciencia de datos, con aplicaciones críticas en la detección de fraudes, limpieza de datos y análisis de registros del sistema. Sin embargo, la literatura existente se centra predominantemente en datos numéricos. Existe una carencia significativa de investigación sobre la detección de anomalías en datos de cadenas de texto (strings).

El objetivo de esta tesis es desarrollar y comparar algoritmos capaces de detectar valores atípicos sintácticos en conjuntos de datos compuestos por cadenas de un solo "palabra" (sin necesidad de contexto semántico externo), abordando dos enfoques principales:

1. Enfoques basados en la densidad y la distancia (adaptación de algoritmos numéricos).
2. Enfoques basados en la inferencia de lenguajes formales (expresiones regulares).

2. Metodología

El autor propone y evalúa dos algoritmos distintos utilizando métricas de evaluación estándar (Curvas ROC, Tasa de Verdaderos Positivos y Falsos Positivos) en conjuntos de datos sintéticos y del mundo real (datos de hospitales alemanes).

A. Enfoque Basado en Vecinos más Cercanos (Local Outlier Factor - LOF)

Este algoritmo adapta el clásico Local Outlier Factor (LOF), diseñado para datos numéricos, para funcionar con cadenas.

• Métrica de Distancia: Utiliza la distancia de Levenshtein (distancia de edición) para calcular la similitud entre cadenas.
• Mejora Propuesta (Pesaje Jerárquico): Se introduce una variante de la distancia de Levenshtein ponderada. En lugar de asignar un costo unitario a todas las operaciones de sustitución, se utiliza una partición jerárquica de clases de caracteres (ej. dígitos, letras minúsculas, mayúsculas, puntuación). La distancia de sustitución depende de la distancia en el árbol de jerarquía entre los caracteres. Esto permite que el algoritmo sea más sensible a cambios sintácticos significativos (ej. cambiar un dígito por una letra) y menos sensible a cambios menores dentro de la misma clase.
• Parámetros:
  • Selección de $k$: Se utiliza un algoritmo heurístico llamado KFCS (basado en la consistencia del vecindario) para determinar automáticamente el número óptimo de vecinos ($k$).
  • Umbral Dinámico: En lugar de un umbral fijo, se propone un método iterativo que calcula la media de las puntuaciones de anomalía y ajusta el umbral multiplicativamente para detectar múltiples grupos de outliers.

B. Enfoque Basado en Expresiones Regulares (HiLRE)

Este es un algoritmo novedoso que infiere un modelo de datos esperado y marca como outliers todo lo que no coincide con él.

• Aprendizaje Incremental: Se basa en el algoritmo de aprendizaje de Expresiones Regulares Izquierdas Jerárquicas (HiLRE). Utiliza la misma partición jerárquica de caracteres que el enfoque LOF para generalizar cadenas en expresiones regulares restringidas.
• Estrategia de Selección ($H^*$): El algoritmo genera expresiones regulares para todos los subconjuntos posibles de los datos. Selecciona la expresión regular $H^*$ que maximiza la diferencia mínima entre el número de coincidencias de la expresión y sus subconjuntos.
• Parámetro de Ajuste ($p_{min}$): Se introduce un parámetro que define la proporción mínima de datos que la expresión regular seleccionada debe cubrir. Esto evita que el algoritmo seleccione expresiones demasiado específicas que solo coinciden con un pequeño grupo de datos "normales" y descartan el resto como outliers.

3. Contribuciones Clave

1. Adaptación de LOF a Cadenas: Implementación exitosa de LOF para datos de texto mediante el uso de la distancia de Levenshtein y una métrica de pesaje jerárquico que mejora la discriminación sintáctica.
2. Nuevo Algoritmo de Detección (HiLRE): Propuesta de un método basado en la inferencia de expresiones regulares jerárquicas para la detección de outliers, incluyendo un mecanismo de selección robusto y un parámetro de control de cobertura ($p_{min}$).
3. Análisis Comparativo Exhaustivo: Evaluación experimental de ambos algoritmos en diversos escenarios (datos limpios vs. datos con outliers, diferentes tipos de estructuras de datos como códigos postales, nombres de condados, fechas y números de teléfono).
4. Herramientas y Código: Desarrollo de herramientas para la extracción de datos de informes de calidad hospitalarios y publicación del código fuente para reproducibilidad.

4. Resultados Experimentales

Los experimentos se realizaron en conjuntos de datos reales (direcciones, fechas, horas) y sintéticos.

• Datos Estructurados (Códigos Postales):

  • El algoritmo HiLRE obtuvo un rendimiento excepcional (100% de detección de outliers, 0% de falsos positivos) cuando los datos esperados tenían una estructura rígida y bien definida (ej. códigos postales de 5 dígitos).
  • El algoritmo LOF funcionó bien pero fue menos preciso, a veces confundiendo nombres de condados de la misma longitud con códigos postales. La versión ponderada de LOF fue más estable que la estándar.

• Datos No Estructurados o Variados (Nombres de Condado):

  • HiLRE falló cuando los datos esperados carecían de una estructura regular clara (nombres de condados de longitudes y caracteres muy variados). No pudo inferir una expresión regular que capturara la "normalidad" sin incluir a los outliers.
  • LOF también tuvo dificultades, comportándose casi al azar, ya que la densidad de los datos era demasiado dispersa para distinguir claramente los outliers.

• Datos con Variaciones de Longitud (Códigos Postales vs. Números de Teléfono/Casas):

  • LOF superó a HiLRE en este escenario. Al basarse en la densidad y la distancia de edición, pudo identificar que las cadenas de los outliers (números de teléfono) eran estructuralmente similares pero de longitud diferente a los códigos postales.
  • HiLRE tuvo un rendimiento pobre, a menudo clasificando todo como outlier o nada, debido a la dificultad de encontrar una expresión regular que separara las longitudes sin sobreajustar o subajustar.

• Datos Limpios (Sin Outliers):

  • Ambos algoritmos pueden alcanzar una tasa de falsos positivos de cero ajustando sus parámetros (umbral para LOF, $p_{min}$ para HiLRE), aunque HiLRE requiere valores de $p_{min}$ más altos en datos con sesgos estacionales (ej. fechas de fin de año).

5. Significado y Conclusiones

La tesis demuestra que no existe un algoritmo universal para la detección de outliers en cadenas; la elección depende intrínsecamente de la naturaleza del conjunto de datos:

1. HiLRE es superior cuando los datos "normales" poseen una estructura sintáctica distintiva y rígida (como formatos de fecha, códigos postales o IDs fijos) que es fácilmente diferenciable de los outliers. Es ideal para validación de formatos estrictos.
2. LOF es superior cuando los outliers comparten la misma clase de caracteres que los datos normales pero difieren en longitud o en la distancia de edición (ej. números de teléfono vs. códigos postales, o errores tipográficos). Es más robusto ante la variabilidad estructural de los datos.
3. La métrica de distancia ponderada en LOF ofrece una ventaja en casos específicos donde la semántica de los caracteres (clases de caracteres) es más importante que la mera coincidencia de caracteres, permitiendo un ajuste fino del algoritmo.

Trabajo Futuro: El autor sugiere que futuras investigaciones deben abordar el análisis teórico de la complejidad temporal y espacial de estos algoritmos, así como extender la detección a cadenas de múltiples palabras y a la detección semántica (que requiere contexto externo), un área aún poco explorada.