Representación del Kernel y Medida de Similitud para Datos Incompletos

Información Básica

• ID del Artículo: 2510.13352
• Título: Kernel Representation and Similarity Measure for Incomplete Data
• Autores: Yang Cao, Sikun Yang, Kai He, Wenjun Ma, Ming Liu, Yujiu Yang, Jian Weng
• Clasificación: cs.LG (Aprendizaje Automático)
• Fecha de Publicación: 15 de octubre de 2024 (Envío a arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2510.13352v1

Resumen

Este artículo aborda el desafío fundamental de la medida de similitud para datos incompletos mediante el método del kernel de proximidad (proximity kernel). Los métodos tradicionales descartan datos incompletos o realizan preprocesamiento de imputación, lo que resulta en pérdida de información y sesgo en la estimación de similitud. El kernel de proximidad calcula directamente la similitud entre datos incompletos en el espacio de características del kernel, sin necesidad de imputación explícita en el espacio original. El método introduce un mecanismo de binning dependiente de los datos combinado con asignación de proximidad, proyectando los datos en representaciones dispersas de alta dimensión que se adaptan a variaciones de densidad local. Para el manejo de valores faltantes, se propone una estrategia de retroceso en cascada para estimar la distribución de características faltantes. Los experimentos de agrupamiento en 12 conjuntos de datos reales incompletos demuestran que el método supera a los métodos existentes mientras mantiene complejidad temporal lineal.

Antecedentes de Investigación y Motivación

Problema Central

La medida de similitud para datos incompletos es un desafío fundamental en minería de redes, sistemas de recomendación y análisis de comportamiento de usuarios. Los datos del mundo real son inherentemente incompletos debido a preferencias de privacidad de usuarios, falta de respuesta en encuestas e información voluntariamente no divulgada.

Importancia del Problema

1. Prevalencia Generalizada: En sistemas de recomendación, los usuarios típicamente califican solo una pequeña cantidad de elementos, produciendo matrices usuario-elemento altamente dispersas
2. Heterogeneidad de Datos: La falta de datos puede afectar simultáneamente características numéricas, categóricas o mixtas
3. Impacto en Tareas Posteriores: La medida de similitud es fundamental para agrupamiento, clasificación y detección de anomalías; estimaciones de similitud inexactas reducen significativamente el rendimiento de tareas

Limitaciones de Métodos Existentes

1. Métodos de Eliminación: Ignoran valores faltantes o eliminan completamente muestras incompletas, causando pérdida grave de información y sesgo
2. Métodos de Imputación: Utilizan estadísticas o técnicas complejas para rellenar valores faltantes, frecuentemente incapaces de capturar distribuciones de datos subyacentes, potencialmente introduciendo patrones artificiales que no reflejan la verdadera estructura de similitud
3. Métodos de Aprendizaje Profundo: Aunque prometedores, típicamente requieren grandes conjuntos de datos y recursos computacionales sustanciales, carecen de garantías teóricas y son sensibles a hiperparámetros

Motivación de la Investigación

Los métodos existentes adoptan una estrategia de "dos fases" (imputación primero, luego cálculo de similitud). Este artículo propone un nuevo enfoque para manejar conjuntamente la imputación y la medida de similitud en el espacio de representación del kernel.

Contribuciones Principales

1. Propone el Método del Kernel de Proximidad: Proyecta datos en representaciones dispersas de alta dimensión mediante binning de frecuencia igual y asignación de proximidad basada en Voronoi, adaptándose a densidad local sin necesidad de estimación de densidad explícita
2. Estrategia de Retroceso en Cascada: Para el manejo de valores faltantes, propone una estrategia de coincidencia con restricciones progresivamente relajadas, desde intersección hasta unión y luego a priors globales
3. Complejidad Temporal Lineal: Logra complejidad temporal lineal, haciendo el método escalable a conjuntos de datos grandes
4. Validación Experimental: Demuestra rendimiento superior a métodos existentes en tareas de agrupamiento en 12 conjuntos de datos

Explicación Detallada del Método

Definición de Tarea

Dado un conjunto de datos D = {x₁, x₂, ..., xₙ} con n muestras, donde cada muestra xᵢ ∈ ℝᵈ es un vector de características d-dimensional que puede contener valores faltantes (representados como NaN). El objetivo es calcular una función de similitud s : D × D → 0,1 que cuantifique la similitud entre dos muestras cualesquiera, para ser utilizada en tareas posteriores como agrupamiento.

Arquitectura del Modelo

1. Binning Dependiente de Datos y Asignación de Proximidad

Selección de Centros de Bins: Para cada característica j, se utilizan bins de frecuencia igual para seleccionar nᵦᵢₙₛ centros de bins:

c_{j,k} = percentile(X_{obs,j}, (k-1)×100/(n_{bins}-1))

donde k ∈ {1,2,...,nᵦᵢₙₛ}, y Xₒᵦₛ,ⱼ representa todos los valores observados de la característica j.

Mecanismo de Asignación de Proximidad: Utiliza asignación de proximidad en lugar de pertenencia a intervalo tradicional:

b_{i,j} = argmin_{k∈{1,...,n_{bins}}} |x_{i,j} - c_{j,k}|

Esto crea un diagrama de Voronoi del espacio de características, donde cada centro cⱼ,ₖ define una celda de Voronoi.

Característica de Adaptación a Densidad:

• En regiones densas: La distancia entre centros consecutivos es pequeña, creando celdas de Voronoi pequeñas, donde dos puntos a la misma distancia tienen mayor probabilidad de caer en diferentes celdas
• En regiones dispersas: La distancia entre centros consecutivos es grande, creando celdas de Voronoi grandes, donde dos puntos a la misma distancia tienen mayor probabilidad de caer en la misma celda

2. Construcción de Codificación One-Hot

Para cada característica j y muestra i, se construye un vector binario hᵢ,ⱼ ∈ {0,1}^{n_}:

h_{i,j,k} = {1 si b_{i,j} = k; 0 en otro caso}

La codificación completa es la concatenación de todas las características: zᵢ = hᵢ,₁, hᵢ,₂, ..., hᵢ,ₐ

3. Estrategia de Retroceso en Cascada para Manejo de Valores Faltantes

Nivel 1 - Coincidencia de Intersección: Busca muestras que coincidan en todas las características observadas:

S₁(i) = ∩_{j∈O_i} C_{i,j}

donde C_{i,j} = {m : m≠i, b_{m,j} = b_{i,j}}

Nivel 2 - Coincidencia de Unión: Si S₁(i) = ∅, relaja a coincidencia en cualquier característica observada:

S₂(i) = ∪_{j∈O_i} C_{i,j}

Nivel 3 - Prior Global: Si S₂(i) = ∅, utiliza la distribución global:

p_{j,k} = cantidad de muestras en bin k para característica j / cantidad de muestras con característica j observada

Para cada nivel, se utiliza incrustación de media del kernel (KME) para estimar la codificación faltante:

h_{i,j,k} = 1/|S(i)| ∑_{m∈S(i)} h_{m,j,k}

Puntos de Innovación Técnica

1. Adaptación a Densidad sin Estimación Explícita: Mediante la combinación de binning de frecuencia igual y asignación de proximidad, se logra naturalmente la partición adaptada a densidad
2. Procesamiento Conjunto en Espacio del Kernel: Maneja valores faltantes en el espacio de representación en lugar del espacio original, evitando la introducción de patrones artificiales
3. Estrategia de Coincidencia Progresiva: Criterios de coincidencia que van de estrictos a relajados, maximizando la utilización de información disponible

Definición del Kernel de Proximidad

K(x_m, x_n) = 1/d · z_m^T z_n = <z_m, z_n>

Este kernel satisface la condición de Mercer (simetría y semi-definición positiva), con interpretación probabilística: calcula la probabilidad esperada de que dos muestras caigan en el mismo bin en todas las características.

Configuración Experimental

Conjuntos de Datos

Se utilizan 12 conjuntos de datos reales de UCI, abarcando múltiples dominios:

• Diagnóstico Médico: Kidney, Hepatitis, Heart, Tumor, Cancer
• Clasificación Biológica: Soybean, Mushroom
• Análisis Financiero: Credit
• Predicción Demográfica: Adult
• Análisis Político: Voting
• Otros: Mammography, Horse

Los conjuntos de datos varían de 155 a 48,842 muestras, con dimensiones de 5 a 35, y tasas de falta de datos de 0.15% a 19.39%.

Métricas de Evaluación

Se utiliza Información Mutua Normalizada (NMI) para evaluar la calidad del agrupamiento, empleando agrupamiento K-means con número de clusters igual al número de clases verdaderas.

Métodos de Comparación

9 métodos representativos:

1. Imputación Simple: Imputación por media
2. Métodos Estadísticos: MissForest, MICE, KNN, EM
3. Aprendizaje Profundo: GAIN, MIRACLE, MIWAE
4. Métodos del Kernel: HI-PMK

Detalles de Implementación

• Cada experimento se repite 10 veces y se promedian los resultados
• Se realiza ajuste de hiperparámetros para todos los métodos base
• El número de bins del kernel de proximidad se busca en {2,3,4,6,8}

Resultados Experimentales

Resultados Principales

1. Rendimiento General: Logra el mejor o segundo mejor rendimiento en 10 de 12 conjuntos de datos, con NMI promedio más alto (0.4245)
2. Significancia Estadística: La prueba de Friedman-Nemenyi muestra que el kernel de proximidad es significativamente superior a todos los demás métodos excepto HI-PMK
3. Estabilidad: Los gráficos de caja muestran que el kernel de proximidad no solo tiene el mejor rendimiento promedio, sino también un desempeño más consistente en diferentes conjuntos de datos

Experimentos de Robustez ante Tasa de Falta de Datos

Se prueba en conjuntos de datos 3L y Messidor con tasas de falta de datos del 10%-50%:

• Mantiene rendimiento superior estable en tasas bajas a moderadas (10%-40%)
• Mantiene rendimiento razonable incluso en tasas extremas (50%)
• En comparación, KNN y MissForest tienen rendimiento casi nulo a 30% de falta de datos

Análisis de Escalabilidad

• Complejidad Temporal: O(nd + d·n log n), lineal respecto al número de muestras para dimensión fija
• Complejidad Espacial: O(nd), lineal respecto al número de muestras y características
• Tiempo de Ejecución Real: Significativamente más rápido que HI-PMK y MIWAE

Análisis de Sensibilidad

Cuando el número de bins varía de 2 a 10, el cambio de NMI en tres conjuntos de datos es muy pequeño (por ejemplo, en el conjunto Mammo varía entre 0.30-0.33), demostrando que el método es insensible a hiperparámetros.

Trabajo Relacionado

Métodos de Imputación Tradicionales

• Imputación Simple: Imputación por media/moda, computacionalmente eficiente pero incapaz de preservar la variabilidad natural de los datos
• Imputación KNN: Basada en k muestras más similares, pero con rendimiento deficiente en datos de alta dimensión dispersos
• Algoritmo EM: Basado en estimación de densidad de máxima verosimilitud, requiere supuestos de distribución fuertes
• MICE: Crea múltiples conjuntos de datos imputados, computacionalmente costoso y requiere especificación cuidadosa del modelo
• MissForest: Utiliza bosques aleatorios para imputación iterativa, puede sobreajustarse y carece de garantías de convergencia

Métodos de Aprendizaje Profundo

• GAIN: Utiliza redes generativas adversariales para aprender la distribución de datos faltantes
• MIWAE: Utiliza modelos de variables latentes profundas para maximizar el límite inferior de verosimilitud de datos observados
• MIRACLE: Combina inferencia causal con aprendizaje profundo para mejorar la calidad de imputación

Métodos del Kernel

• Distancias Tradicionales: La distancia euclidiana no se aplica directamente a datos incompletos
• HI-PMK: Método del kernel dependiente de datos, pero con complejidad computacional alta y sensibilidad a hiperparámetros

Conclusiones y Discusión

Conclusiones Principales

1. El kernel de proximidad logra exitosamente calcular directamente la similitud entre datos incompletos en el espacio de características del kernel, evitando imputación explícita en el espacio original
2. El binning dependiente de datos combinado con asignación de proximidad crea una representación que se adapta a densidad local, sin necesidad de estimación de densidad explícita
3. La estrategia de retroceso en cascada utiliza efectivamente la información disponible, relajando progresivamente desde coincidencia estricta a priors globales
4. El método logra rendimiento superior mientras mantiene complejidad temporal lineal

Limitaciones

1. Supuestos sobre Mecanismo de Falta de Datos: La evaluación actual se basa principalmente en mecanismo MCAR (falta completamente aleatoria), mientras que datos reales frecuentemente exhiben patrones MAR y MNAR más complejos
2. Estrategia de Binning: El binning de frecuencia igual puede no ser óptimo para todas las distribuciones de datos
3. Garantías Teóricas: Carece de garantías teóricas de convergencia para el mecanismo de retroceso en cascada

Direcciones Futuras

1. Investigar el comportamiento del método bajo mecanismos de falta de datos MAR y MNAR
2. Explorar estrategias de selección de binning adaptativo
3. Establecer garantías teóricas de convergencia para el mecanismo de retroceso en cascada
4. Extender a tipos de datos y estructuras más complejas

Evaluación Profunda

Fortalezas

1. Innovación del Método: Unifica imputación y cálculo de similitud en el espacio de representación del kernel, evitando problemas de métodos tradicionales de dos fases
2. Fundamento Teórico: Proporciona pruebas rigurosas de validez del kernel, satisfaciendo la condición de Mercer
3. Practicidad: La complejidad temporal lineal hace el método aplicable a aplicaciones a gran escala
4. Experimentación Exhaustiva: Evaluación completa en múltiples conjuntos de datos, incluyendo pruebas de significancia estadística
5. Robustez: Insensible a hiperparámetros, con desempeño estable bajo diferentes tasas de falta de datos

Deficiencias

1. Limitación del Mecanismo de Falta de Datos: Evaluación principalmente bajo supuesto MCAR, adaptabilidad a patrones de falta más complejos no suficientemente verificada
2. Estimación de Densidad: Aunque afirma no necesitar estimación de densidad explícita, el binning de frecuencia igual es esencialmente una estimación de densidad implícita
3. Independencia de Características: El modelado de dependencias entre características en la estrategia en cascada puede ser insuficiente
4. Equidad de Comparación: En comparaciones con métodos de aprendizaje profundo, puede haber diferencias en recursos computacionales y grado de ajuste

Impacto

1. Contribución Académica: Proporciona un nuevo marco teórico para medida de similitud en datos incompletos
2. Valor Práctico: Tiene valor directo en aplicaciones como sistemas de recomendación, minería de redes, etc.
3. Reproducibilidad: Proporciona enlace de código, facilitando verificación y promoción del método

Escenarios de Aplicación

1. Sistemas de Recomendación: Manejo de dispersidad en matrices de calificación usuario-elemento
2. Minería de Redes: Manejo de incompletitud en datos de comportamiento de usuarios
3. Análisis de Datos Médicos: Manejo de valores faltantes en datos clínicos
4. Procesamiento de Datos a Gran Escala: Complejidad lineal adecuada para aplicaciones a gran escala

Referencias

El artículo cita 21 referencias relacionadas, abarcando múltiples campos incluyendo manejo de datos faltantes, métodos del kernel y aprendizaje profundo, proporcionando una base teórica sólida y puntos de referencia para comparación.

Resumen: El método del kernel de proximidad propuesto en este artículo realiza contribuciones importantes en el campo de la medida de similitud para datos incompletos. Mediante diseño ingenioso de representación del kernel y estrategia de retroceso en cascada, logra un buen equilibrio entre rendimiento y eficiencia. A pesar de algunas limitaciones, su innovación y practicidad le confieren valor importante en campos de aplicación relacionados.