Représentation par Noyau et Mesure de Similarité pour Données Incomplètes

Informations Fondamentales

• ID de l'article: 2510.13352
• Titre: Kernel Representation and Similarity Measure for Incomplete Data
• Auteurs: Yang Cao, Sikun Yang, Kai He, Wenjun Ma, Ming Liu, Yujiu Yang, Jian Weng
• Classification: cs.LG (Apprentissage Automatique)
• Date de publication: 15 octobre 2024 (soumission arXiv)
• Lien de l'article: https://arxiv.org/abs/2510.13352v1

Résumé

Cet article aborde le défi fondamental de la mesure de similarité pour les données incomplètes en proposant une méthode de noyau de proximité (proximity kernel). Les méthodes traditionnelles soit rejettent les données incomplètes, soit effectuent d'abord un prétraitement d'imputation, ce qui entraîne une perte d'information et des biais dans l'estimation de la similarité. Le noyau de proximité calcule directement la similarité entre les données incomplètes dans l'espace des caractéristiques du noyau, sans nécessiter d'imputation explicite dans l'espace original. La méthode introduit un mécanisme de binning dépendant des données combiné à une allocation de proximité, projetant les données dans une représentation creuse de haute dimension qui s'adapte aux variations de densité locale. Pour le traitement des valeurs manquantes, une stratégie de secours en cascade est proposée pour estimer la distribution des caractéristiques manquantes. Les expériences de clustering sur 12 ensembles de données incomplètes réelles montrent que la méthode surpasse les méthodes existantes tout en maintenant une complexité temporelle linéaire.

Contexte de Recherche et Motivation

Problème Central

La mesure de similarité pour les données incomplètes est un défi fondamental dans l'exploration de réseaux, les systèmes de recommandation et l'analyse du comportement des utilisateurs. Les données du monde réel sont intrinsèquement incomplètes en raison des préférences de confidentialité des utilisateurs, des non-réponses aux enquêtes et de la divulgation volontaire d'informations.

Importance du Problème

1. Omniprésence: Dans les systèmes de recommandation, les utilisateurs évaluent généralement seulement un petit nombre d'articles, produisant une matrice utilisateur-article hautement creuse
2. Hétérogénéité des données: Les valeurs manquantes peuvent affecter simultanément les caractéristiques numériques, catégoriques ou mixtes
3. Impact sur les tâches en aval: La mesure de similarité est fondamentale pour le clustering, la classification et la détection d'anomalies; une estimation inexacte de la similarité réduit considérablement les performances des tâches

Limitations des Méthodes Existantes

1. Méthodes de suppression: Ignorer les valeurs manquantes ou supprimer complètement les échantillons incomplets, entraînant une perte d'information grave et des biais
2. Méthodes d'imputation: Utiliser des statistiques ou des techniques complexes pour remplir les valeurs manquantes, souvent incapables de capturer la distribution de données sous-jacente, pouvant introduire des motifs artificiels qui ne reflètent pas la véritable structure de similarité
3. Méthodes d'apprentissage profond: Bien que prometteuses, elles nécessitent généralement de grands ensembles de données et des ressources informatiques importantes, manquent de garanties théoriques et sont sensibles aux hyperparamètres

Motivation de la Recherche

Les méthodes existantes adoptent une stratégie « en deux étapes » (imputation d'abord, puis calcul de la similarité). Cet article propose une nouvelle approche pour traiter conjointement l'imputation et la mesure de similarité dans l'espace de représentation du noyau.

Contributions Principales

1. Proposition de la méthode du noyau de proximité: Projection des données dans une représentation creuse de haute dimension par binning équifréquent et allocation de proximité basée sur Voronoi, s'adaptant à la densité locale sans estimation de densité explicite
2. Stratégie de secours en cascade: Pour le traitement des valeurs manquantes, une stratégie d'appariement progressif relâchant les contraintes de l'intersection à l'union puis aux priors globaux
3. Complexité temporelle linéaire: Réalisation d'une complexité temporelle linéaire, rendant la méthode extensible aux grands ensembles de données
4. Validation expérimentale: Démonstration de performances supérieures aux méthodes existantes dans les tâches de clustering sur 12 ensembles de données

Explication Détaillée de la Méthode

Définition de la Tâche

Étant donné un ensemble de données D = {x₁, x₂, ..., xₙ} contenant n échantillons, où chaque échantillon xᵢ ∈ ℝᵈ est un vecteur de caractéristiques d-dimensionnel pouvant contenir des valeurs manquantes (représentées par NaN). L'objectif est de calculer une fonction de similarité s : D × D → 0,1, quantifiant la similarité entre deux échantillons quelconques, pour une utilisation dans des tâches en aval telles que le clustering.

Architecture du Modèle

1. Binning Dépendant des Données et Allocation de Proximité

Sélection des centres de binning: Pour chaque caractéristique j, utiliser le binning équifréquent pour sélectionner nᵦᵢₙₛ centres de binning:

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

où k ∈ {1,2,...,nᵦᵢₙₛ}, Xₒᵦₛ,ⱼ représente toutes les valeurs observées de la caractéristique j.

Mécanisme d'allocation de proximité: Utiliser l'allocation de proximité plutôt que l'appartenance à un intervalle traditionnel:

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

Ceci crée un diagramme de Voronoi de l'espace des caractéristiques, où chaque centre cⱼ,ₖ définit une cellule de Voronoi.

Caractéristique d'adaptation à la densité:

• Dans les régions denses: L'espacement entre les centres consécutifs est petit, créant de petites cellules de Voronoi; deux points à la même distance sont plus susceptibles de tomber dans des cellules différentes
• Dans les régions creuses: L'espacement entre les centres consécutifs est grand, créant de grandes cellules de Voronoi; deux points à la même distance sont plus susceptibles de tomber dans la même cellule

2. Construction de l'Encodage One-Hot

Pour chaque caractéristique j et échantillon i, construire un vecteur binaire hᵢ,ⱼ ∈ {0,1}^{n_}:

h_{i,j,k} = {1 if b_{i,j} = k; 0 otherwise}

L'encodage complet est la concaténation de toutes les caractéristiques: zᵢ = hᵢ,₁, hᵢ,₂, ..., hᵢ,ₐ

3. Stratégie de Secours en Cascade pour le Traitement des Valeurs Manquantes

Niveau 1 - Appariement par intersection: Trouver les échantillons qui correspondent sur toutes les caractéristiques observées:

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

où C_{i,j} = {m : m≠i, b_{m,j} = b_{i,j}}

Niveau 2 - Appariement par union: Si S₁(i) = ∅, relâcher à l'appariement sur n'importe quelle caractéristique observée:

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

Niveau 3 - Prior global: Si S₂(i) = ∅, utiliser la distribution globale:

p_{j,k} = nombre d'échantillons dans le bin k pour la caractéristique j / nombre d'échantillons avec la caractéristique j observée

Pour chaque niveau, utiliser l'intégration de moyennes du noyau (KME) pour estimer l'encodage manquant:

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

Points d'Innovation Technique

1. Adaptation à la densité sans estimation explicite: Grâce à la combinaison du binning équifréquent et de l'allocation de proximité, la segmentation adaptée à la densité est réalisée naturellement
2. Traitement conjoint dans l'espace du noyau: Traiter les valeurs manquantes dans l'espace de représentation plutôt que dans l'espace original, évitant l'introduction de motifs artificiels
3. Stratégie d'appariement progressive: Des critères d'appariement stricts aux critères relâchés, maximisant l'utilisation des informations disponibles

Définition du Noyau de Proximité

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

Ce noyau satisfait la condition de Mercer (symétrie et semi-défini positif), possédant une interprétation probabiliste: calcul de la probabilité attendue que deux échantillons tombent dans le même bin sur toutes les caractéristiques.

Configuration Expérimentale

Ensembles de Données

Utilisation de 12 ensembles de données réels de l'UCI, couvrant plusieurs domaines:

• Diagnostic médical: Kidney, Hepatitis, Heart, Tumor, Cancer
• Classification biologique: Soybean, Mushroom
• Analyse financière: Credit
• Prédiction démographique: Adult
• Analyse politique: Voting
• Autres: Mammography, Horse

Les ensembles de données contiennent entre 155 et 48 842 échantillons, avec des dimensions de 5 à 35 et des taux de valeurs manquantes de 0,15% à 19,39%.

Métriques d'Évaluation

Utilisation de l'information mutuelle normalisée (NMI) pour évaluer la qualité du clustering, avec clustering K-means où le nombre de clusters est défini comme le nombre de classes réelles.

Méthodes de Comparaison

9 méthodes représentatives:

1. Imputation simple: Imputation par la moyenne
2. Méthodes statistiques: MissForest, MICE, KNN, EM
3. Apprentissage profond: GAIN, MIRACLE, MIWAE
4. Méthodes à noyau: HI-PMK

Détails d'Implémentation

• Chaque expérience répétée 10 fois avec moyenne
• Optimisation des hyperparamètres pour toutes les méthodes de base
• Nombre de bins du noyau de proximité recherché dans {2,3,4,6,8}

Résultats Expérimentaux

Résultats Principaux

1. Performance globale: Atteint les meilleures ou deuxièmes meilleures performances sur 10 des 12 ensembles de données, avec le plus haut NMI moyen (0,4245)
2. Signification statistique: Le test de Friedman-Nemenyi montre que le noyau de proximité est significativement supérieur à toutes les autres méthodes sauf HI-PMK
3. Stabilité: Les diagrammes en boîte montrent que le noyau de proximité non seulement obtient les meilleures performances moyennes, mais aussi les plus cohérentes sur différents ensembles de données

Expériences de Robustesse aux Taux de Valeurs Manquantes

Test sur les ensembles de données 3L et Messidor avec des taux de valeurs manquantes de 10%-50%:

• Maintien d'une supériorité stable aux taux de valeurs manquantes faibles à modérés (10%-40%)
• Maintien de performances raisonnables même aux taux extrêmes (50%)
• En comparaison, KNN et MissForest voient leurs performances chuter à presque zéro à 30% de valeurs manquantes

Analyse de Scalabilité

• Complexité temporelle: O(nd + d·n log n), linéaire par rapport au nombre d'échantillons pour une dimension fixe
• Complexité spatiale: O(nd), linéaire par rapport au nombre d'échantillons et de caractéristiques
• Temps d'exécution réel: Significativement plus rapide que HI-PMK et MIWAE

Analyse de Sensibilité

Avec le nombre de bins variant de 2 à 10, les variations de NMI sur trois ensembles de données sont minimes (par exemple, l'ensemble de données Mammo fluctue entre 0,30-0,33), montrant que la méthode est insensible aux hyperparamètres.

Travaux Connexes

Méthodes d'Imputation Traditionnelles

• Imputation simple: Imputation par la moyenne/mode, efficace en calcul mais incapable de préserver la variabilité naturelle des données
• Imputation KNN: Basée sur les k échantillons les plus similaires, mais performances faibles sur les données de haute dimension creuses
• Algorithme EM: Basé sur l'estimation de densité par maximum de vraisemblance, nécessite des hypothèses de distribution fortes
• MICE: Crée plusieurs ensembles de données imputés, coûteux en calcul et nécessite une spécification minutieuse du modèle
• MissForest: Utilise les forêts aléatoires pour l'imputation itérative, peut surapprentissage et manque de garanties de convergence

Méthodes d'Apprentissage Profond

• GAIN: Utilise les réseaux antagonistes génératifs pour apprendre la distribution des données manquantes
• MIWAE: Utilise les modèles à variables latentes profondes pour maximiser la limite inférieure de vraisemblance des données observées
• MIRACLE: Combine l'inférence causale et l'apprentissage profond pour améliorer la qualité d'imputation

Méthodes à Noyau

• Distances traditionnelles: La distance euclidienne ne s'applique pas directement aux données incomplètes
• HI-PMK: Méthode à noyau dépendante des données, mais complexité de calcul élevée et sensibilité aux hyperparamètres

Conclusion et Discussion

Conclusions Principales

1. Le noyau de proximité réussit à calculer directement la similarité entre les données incomplètes dans l'espace des caractéristiques du noyau, évitant l'imputation explicite dans l'espace original
2. Le binning dépendant des données combiné à l'allocation de proximité crée une représentation qui s'adapte à la densité locale, sans nécessiter d'estimation de densité explicite
3. La stratégie de secours en cascade utilise efficacement les informations disponibles, progressant graduellement de l'appariement strict aux priors globaux
4. La méthode réalise des performances supérieures tout en maintenant une complexité temporelle linéaire

Limitations

1. Hypothèses sur le mécanisme de valeurs manquantes: L'évaluation actuelle est principalement basée sur le mécanisme MCAR (Missing Completely At Random); les données réelles présentent souvent des motifs MAR et MNAR plus complexes
2. Stratégie de binning: Le binning équifréquent peut ne pas être optimal pour toutes les distributions de données
3. Garanties théoriques: Absence de garanties de convergence théoriques pour le mécanisme de secours en cascade

Directions Futures

1. Étudier le comportement de la méthode sous les mécanismes de valeurs manquantes MAR et MNAR
2. Explorer les stratégies de sélection de binning adaptatif
3. Établir les garanties de convergence théoriques pour le mécanisme de secours en cascade
4. Étendre à des types de données et structures plus complexes

Évaluation Approfondie

Points Forts

1. Innovativité de la méthode: Unification de l'imputation et du calcul de similarité dans l'espace de représentation du noyau, évitant les problèmes des méthodes traditionnelles en deux étapes
2. Fondation théorique: Fournit des preuves rigoureuses de l'efficacité du noyau, satisfaisant la condition de Mercer
3. Praticité: La complexité temporelle linéaire rend la méthode applicable aux applications à grande échelle
4. Expérimentation complète: Évaluation exhaustive sur plusieurs ensembles de données, incluant les tests de signification statistique
5. Robustesse: Insensibilité aux hyperparamètres, performances stables à différents taux de valeurs manquantes

Insuffisances

1. Limitation du mécanisme de valeurs manquantes: Évaluation principalement sous l'hypothèse MCAR; l'adaptabilité aux motifs de valeurs manquantes plus complexes n'est pas suffisamment vérifiée
2. Estimation de densité: Bien que prétendant ne pas nécessiter d'estimation de densité explicite, le binning équifréquent est essentiellement une forme d'estimation de densité implicite
3. Indépendance des caractéristiques: La modélisation des dépendances entre caractéristiques dans la stratégie de secours peut être insuffisante
4. Équité de la comparaison: Les ressources informatiques et le degré d'optimisation dans les comparaisons avec les méthodes d'apprentissage profond peuvent présenter des différences

Impact

1. Contribution académique: Fournit un nouveau cadre théorique pour la mesure de similarité des données incomplètes
2. Valeur pratique: Possède une valeur directe dans les applications telles que les systèmes de recommandation et l'exploration de réseaux
3. Reproductibilité: Fournit des liens de code, facilitant la vérification et la promotion de la méthode

Scénarios d'Application

1. Systèmes de recommandation: Traitement de la parcimonie de la matrice évaluation utilisateur-article
2. Exploration de réseaux: Traitement de l'incomplétude des données de comportement des utilisateurs
3. Analyse de données médicales: Traitement des valeurs manquantes dans les données cliniques
4. Traitement de données à grande échelle: La complexité linéaire convient aux applications à grande échelle

Références

L'article cite 21 références connexes, couvrant plusieurs domaines tels que le traitement des données manquantes, les méthodes à noyau et l'apprentissage profond, fournissant une base théorique solide et des références de comparaison pour cette recherche.

Résumé: La méthode du noyau de proximité proposée dans cet article apporte une contribution importante au domaine de la mesure de similarité pour les données incomplètes. Grâce à une conception ingénieuse de la représentation du noyau et à une stratégie de secours en cascade, elle réalise un bon équilibre entre performance et efficacité. Malgré certaines limitations, son innovativité et sa praticité lui confèrent une valeur importante dans les domaines d'application connexes.