2025-11-24T15:01:18.137860

Kernel Representation and Similarity Measure for Incomplete Data

Cao, Yang, He et al.
Measuring similarity between incomplete data is a fundamental challenge in web mining, recommendation systems, and user behavior analysis. Traditional approaches either discard incomplete data or perform imputation as a preprocessing step, leading to information loss and biased similarity estimates. This paper presents the proximity kernel, a new similarity measure that directly computes similarity between incomplete data in kernel feature space without explicit imputation in the original space. The proposed method introduces data-dependent binning combined with proximity assignment to project data into a high-dimensional sparse representation that adapts to local density variations. For missing value handling, we propose a cascading fallback strategy to estimate missing feature distributions. We conduct clustering tasks on the proposed kernel representation across 12 real world incomplete datasets, demonstrating superior performance compared to existing methods while maintaining linear time complexity. All the code are available at https://anonymous.4open.science/r/proximity-kernel-2289.
academic

Kernel-Darstellung und Ähnlichkeitsmessung für unvollständige Daten

Grundlegende Informationen

  • Papier-ID: 2510.13352
  • Titel: Kernel Representation and Similarity Measure for Incomplete Data
  • Autoren: Yang Cao, Sikun Yang, Kai He, Wenjun Ma, Ming Liu, Yujiu Yang, Jian Weng
  • Klassifizierung: cs.LG (Maschinelles Lernen)
  • Veröffentlichungsdatum: 15. Oktober 2024 (arXiv-Einreichung)
  • Papier-Link: https://arxiv.org/abs/2510.13352v1

Zusammenfassung

Dieses Papier schlägt eine Proximity-Kernel-Methode vor, um die grundlegende Herausforderung der Ähnlichkeitsmessung bei unvollständigen Daten zu bewältigen. Herkömmliche Methoden verwerfen entweder unvollständige Daten oder führen zunächst eine Imputationsvorverarbeitung durch, was zu Informationsverlust und Verzerrungen bei der Ähnlichkeitsschätzung führt. Der Proximity-Kernel berechnet die Ähnlichkeit zwischen unvollständigen Daten direkt im Kernel-Merkmalsraum, ohne explizite Imputation im ursprünglichen Raum zu erfordern. Die Methode führt einen datenabhängigen Binning-Mechanismus in Kombination mit Proximity-Zuweisung ein, um Daten in hochdimensionale spärliche Darstellungen zu projizieren, die sich an lokale Dichteschwankungen anpassen. Zur Behandlung fehlender Werte wird eine kaskadierende Fallback-Strategie zur Schätzung der Verteilung fehlender Merkmale vorgeschlagen. Clustering-Experimente auf 12 echten unvollständigen Datensätzen zeigen, dass die Methode bei Beibehaltung linearer Zeitkomplexität bestehende Methoden übertrifft.

Forschungshintergrund und Motivation

Kernproblem

Die Ähnlichkeitsmessung bei unvollständigen Daten ist eine grundlegende Herausforderung beim Netzwerk-Mining, in Empfehlungssystemen und bei der Analyse von Benutzerverhalten. Daten aus der realen Welt sind aufgrund von Benutzervertraulichkeitspräferenzen, fehlenden Umfrageantworten und freiwilliger Nichtoffenlegung von Informationen von Natur aus unvollständig.

Bedeutung des Problems

  1. Weit verbreitet: In Empfehlungssystemen bewerten Benutzer typischerweise nur eine kleine Anzahl von Elementen, was zu hochgradig spärlichen Benutzer-Element-Matrizen führt
  2. Datenheterogenität: Fehlende Werte können gleichzeitig numerische, kategorische oder gemischte Merkmale beeinflussen
  3. Auswirkungen auf nachgelagerte Aufgaben: Die Ähnlichkeitsmessung ist die Grundlage für Clustering-, Klassifizierungs- und Anomalieerkennung, und ungenaue Ähnlichkeitsschätzungen können die Aufgabenleistung erheblich beeinträchtigen

Einschränkungen bestehender Methoden

  1. Löschmethoden: Ignorieren fehlende Werte oder entfernen unvollständige Stichproben vollständig, was zu erheblichem Informationsverlust und Verzerrungen führt
  2. Imputationsmethoden: Verwenden statistische Größen oder komplexe Techniken zum Ausfüllen fehlender Werte, können jedoch häufig die zugrunde liegende Datenverteilung nicht erfassen und können künstliche Muster einführen, die nicht die wahre Ähnlichkeitsstruktur widerspiegeln
  3. Deep-Learning-Methoden: Obwohl vielversprechend, erfordern sie normalerweise große Datensätze und erhebliche Rechenressourcen, bieten keine theoretischen Garantien und sind empfindlich gegenüber Hyperparametern

Forschungsmotivation

Bestehende Methoden verwenden eine „zweistufige" Strategie (zuerst Imputation, dann Ähnlichkeitsberechnung). Dieses Papier schlägt einen neuen Ansatz vor, der Imputation und Ähnlichkeitsmessung gemeinsam im Kernel-Darstellungsraum behandelt.

Kernbeiträge

  1. Proximity-Kernel-Methode: Projiziert Daten durch gleichfrequente Binning und Voronoi-basierte Proximity-Zuweisung in hochdimensionale spärliche Darstellungen, ohne explizite Dichteschätzung und mit Anpassung an lokale Dichte
  2. Kaskadierende Fallback-Strategie: Schlägt eine progressive Lockerung der Matching-Strategie von Schnittmenge über Vereinigung bis zu globalen Priors für die Behandlung fehlender Werte vor
  3. Lineare Zeitkomplexität: Erreicht lineare Zeitkomplexität, was die Methode auf große Datensätze skalierbar macht
  4. Experimentelle Validierung: Demonstriert überlegene Leistung gegenüber bestehenden Methoden bei Clustering-Aufgaben auf 12 Datensätzen

Methodische Details

Aufgabendefinition

Gegeben ein Datensatz D = {x₁, x₂, ..., xₙ} mit n Stichproben, wobei jede Stichprobe xᵢ ∈ ℝᵈ ein d-dimensionaler Merkmalsvektor ist, der fehlende Werte enthalten kann (dargestellt als NaN). Das Ziel ist die Berechnung einer Ähnlichkeitsfunktion s : D × D → 0,1, die die Ähnlichkeit zwischen zwei beliebigen Stichproben quantifiziert und für nachgelagerte Aufgaben wie Clustering verwendet wird.

Modellarchitektur

1. Datenabhängiges Binning und Proximity-Zuweisung

Auswahl der Bin-Zentren: Für jedes Merkmal j werden nᵦᵢₙₛ Bin-Zentren mit gleichfrequentem Binning ausgewählt:

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

wobei k ∈ {1,2,...,nᵦᵢₙₛ} und Xₒᵦₛ,ⱼ alle beobachteten Werte des Merkmals j darstellt.

Proximity-Zuweisungsmechanismus: Verwendet Proximity-Zuweisung anstelle traditioneller Intervall-Mitgliedschaft:

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

Dies erzeugt ein Voronoi-Diagramm des Merkmalsraums, wobei jedes Zentrum cⱼ,ₖ eine Voronoi-Zelle definiert.

Dichteadaptive Eigenschaften:

  • In dichten Regionen: Der Abstand zwischen aufeinanderfolgenden Zentren ist klein, was kleine Voronoi-Zellen erzeugt; zwei Punkte mit gleichem Abstand fallen wahrscheinlicher in verschiedene Zellen
  • In spärlichen Regionen: Der Abstand zwischen aufeinanderfolgenden Zentren ist groß, was große Voronoi-Zellen erzeugt; zwei Punkte mit gleichem Abstand fallen wahrscheinlicher in die gleiche Zelle

2. One-Hot-Kodierung-Konstruktion

Für jedes Merkmal j und jede Stichprobe i wird ein binärer Vektor hᵢ,ⱼ ∈ {0,1}^{n_} konstruiert:

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

Die vollständige Kodierung ist die Verkettung aller Merkmale: zᵢ = hᵢ,₁, hᵢ,₂, ..., hᵢ,ₐ

3. Kaskadierende Fallback-Strategie zur Behandlung fehlender Werte

Stufe 1 - Schnittmengen-Matching: Sucht Stichproben, die bei allen beobachteten Merkmalen übereinstimmen:

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

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

Stufe 2 - Vereinigungs-Matching: Falls S₁(i) = ∅, wird auf beliebiges beobachtetes Merkmal-Matching gelockert:

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

Stufe 3 - Globales Prior: Falls S₂(i) = ∅, wird die globale Verteilung verwendet:

p_{j,k} = count of samples in bin k for feature j / count of samples with observed feature j

Für jede Stufe wird Kernel-Mittelwert-Einbettung (KME) zur Schätzung der fehlenden Kodierung verwendet:

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

Technische Innovationen

  1. Dichteadaptation ohne explizite Schätzung: Die Kombination von gleichfrequentem Binning und Proximity-Zuweisung ermöglicht natürlicherweise dichteadaptive Segmentierung
  2. Gemeinsame Verarbeitung im Kernel-Raum: Behandelt fehlende Werte im Darstellungsraum statt im ursprünglichen Raum und vermeidet künstliche Muster
  3. Progressive Matching-Strategie: Von striktem zu lockerem Matching-Kriterium, um die Nutzung verfügbarer Informationen zu maximieren

Proximity-Kernel-Definition

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

Dieser Kernel erfüllt die Mercer-Bedingung (Symmetrie und positive Semidefinitheit) und hat eine probabilistische Interpretation: berechnet die erwartete Wahrscheinlichkeit, dass zwei Stichproben bei allen Merkmalen in den gleichen Bins fallen.

Experimentelle Einrichtung

Datensätze

Es werden 12 echte Datensätze aus dem UCI-Repository verwendet, die mehrere Bereiche abdecken:

  • Medizinische Diagnose: Kidney, Hepatitis, Heart, Tumor, Cancer
  • Biologische Klassifizierung: Soybean, Mushroom
  • Finanzanalyse: Credit
  • Bevölkerungsprognose: Adult
  • Politische Analyse: Voting
  • Sonstige: Mammography, Horse

Die Datensätze umfassen 155 bis 48.842 Stichproben, 5 bis 35 Dimensionen und Fehlquoten von 0,15% bis 19,39%.

Bewertungsmetriken

Verwendet normalisierte gegenseitige Information (NMI) zur Bewertung der Clustering-Qualität, mit K-Means-Clustering und Clusterzahl gleich der Anzahl echter Klassen.

Vergleichsmethoden

9 repräsentative Methoden:

  1. Einfache Imputation: Mittelwert-Imputation
  2. Statistische Methoden: MissForest, MICE, KNN, EM
  3. Deep Learning: GAIN, MIRACLE, MIWAE
  4. Kernel-Methoden: HI-PMK

Implementierungsdetails

  • Jedes Experiment wird 10-mal wiederholt und gemittelt
  • Hyperparameter-Tuning für alle Baseline-Methoden
  • Bin-Anzahl für Proximity-Kernel wird aus {2,3,4,6,8} durchsucht

Experimentelle Ergebnisse

Hauptergebnisse

  1. Gesamtleistung: Erreicht beste oder zweitbeste Leistung auf 10 von 12 Datensätzen mit höchstem durchschnittlichem NMI (0,4245)
  2. Statistische Signifikanz: Friedman-Nemenyi-Test zeigt, dass Proximity-Kernel, außer gegenüber HI-PMK, signifikant besser als alle anderen Methoden ist
  3. Stabilität: Box-Plots zeigen, dass Proximity-Kernel nicht nur beste durchschnittliche Leistung hat, sondern auch konsistentere Leistung über verschiedene Datensätze

Robustheit-Experimente bei Fehlquoten

Tests bei 10%-50% Fehlquoten auf 3L- und Messidor-Datensätzen:

  • Behält stabile überlegene Leistung bei niedriger bis mittlerer Fehlquote (10%-40%)
  • Behält angemessene Leistung auch bei extremer Fehlquote (50%)
  • Im Vergleich dazu sinkt die Leistung von KNN und MissForest bei 30% Fehlquote fast auf Null

Skalierbarkeitsanalyse

  • Zeitkomplexität: O(nd + d·n log n), linear in Stichprobenzahl für feste Dimensionalität
  • Raumkomplexität: O(nd), linear in Stichprobenzahl und Merkmalszahl
  • Tatsächliche Laufzeit: Signifikant schneller als HI-PMK und MIWAE

Sensitivitätsanalyse

Bei Variation der Bin-Anzahl von 2 bis 10 zeigen sich kleine NMI-Änderungen über drei Datensätze (z.B. Mammo-Datensatz schwankt zwischen 0,30-0,33), was die Unempfindlichkeit der Methode gegenüber Hyperparametern zeigt.

Verwandte Arbeiten

Traditionelle Imputationsmethoden

  • Einfache Imputation: Mittelwert-/Modus-Imputation, rechnerisch effizient, aber kann natürliche Datenvariabilität nicht bewahren
  • KNN-Imputation: Basiert auf k ähnlichsten Stichproben, aber schlechte Leistung bei hochdimensionalen spärlichen Daten
  • EM-Algorithmus: Basiert auf Maximum-Likelihood-Dichteschätzung, erfordert starke Verteilungsannahmen
  • MICE: Erstellt mehrere imputierte Datensätze, rechnerisch teuer und erfordert sorgfältige Modellspezifikation
  • MissForest: Verwendet iterative Imputation mit zufälligen Wäldern, kann überangepasst sein und bietet keine Konvergenzgarantien

Deep-Learning-Methoden

  • GAIN: Verwendet generative adversarische Netzwerke zum Lernen der Verteilung fehlender Daten
  • MIWAE: Verwendet tiefe latente Variablenmodelle zur Maximierung der Evidenz-Untergrenze beobachteter Daten
  • MIRACLE: Kombiniert kausale Inferenz mit Deep Learning zur Verbesserung der Imputationsqualität

Kernel-Methoden

  • Traditionelle Distanzen: Euklidische Distanz ist nicht direkt auf unvollständige Daten anwendbar
  • HI-PMK: Datenabhängige Kernel-Methode, aber hohe Rechenkomplexität und Hyperparameter-Empfindlichkeit

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Der Proximity-Kernel berechnet erfolgreich die Ähnlichkeit zwischen unvollständigen Daten direkt im Kernel-Merkmalsraum und vermeidet explizite Imputation im ursprünglichen Raum
  2. Datenabhängiges Binning in Kombination mit Proximity-Zuweisung erzeugt Darstellungen, die sich an lokale Dichte anpassen, ohne explizite Dichteschätzung
  3. Die kaskadierende Fallback-Strategie nutzt verfügbare Informationen effektiv und lockert schrittweise von striktem Matching zu globalen Priors
  4. Die Methode erreicht überlegene Leistung bei Beibehaltung linearer Zeitkomplexität

Einschränkungen

  1. Annahmen zum Fehlmechanismus: Aktuelle Bewertung basiert hauptsächlich auf MCAR-Mechanismus (vollständig zufällige Fehlbarkeit), echte Daten zeigen häufig komplexere MAR- und MNAR-Muster
  2. Binning-Strategie: Gleichfrequentes Binning ist möglicherweise nicht optimal für alle Datenverteilungen
  3. Theoretische Garantien: Fehlende theoretische Konvergenzgarantien für kaskadierende Fallback-Mechanismus

Zukünftige Richtungen

  1. Untersuchung des Methodenverhaltens unter MAR- und MNAR-Fehlmechanismen
  2. Erkundung adaptiver Bin-Auswahlstrategien
  3. Etablierung theoretischer Konvergenzgarantien für kaskadierende Fallback-Mechanismus
  4. Erweiterung auf komplexere Datentypen und Strukturen

Tiefgreifende Bewertung

Stärken

  1. Methodische Innovation: Vereinigt Imputation und Ähnlichkeitsberechnung im Kernel-Darstellungsraum und vermeidet Probleme traditioneller zweistufiger Methoden
  2. Theoretische Grundlage: Bietet strenge Beweise für Kernel-Gültigkeit, erfüllt Mercer-Bedingung
  3. Praktikabilität: Lineare Zeitkomplexität macht die Methode für großskalige Anwendungen geeignet
  4. Umfassende Experimente: Gründliche Bewertung über mehrere Datensätze, einschließlich statistischer Signifikanztests
  5. Robustheit: Unempfindlich gegenüber Hyperparametern, stabile Leistung bei verschiedenen Fehlquoten

Mängel

  1. Fehlmechanismus-Einschränkung: Hauptsächlich unter MCAR-Annahme bewertet, Anpassungsfähigkeit an komplexere Fehlmuster nicht vollständig verifiziert
  2. Dichteschätzung: Obwohl behauptet wird, keine explizite Dichteschätzung zu benötigen, ist gleichfrequentes Binning im Wesentlichen eine implizite Dichteschätzung
  3. Merkmals-Unabhängigkeit: Modellierung von Merkmals-Abhängigkeiten in kaskadierten Strategien möglicherweise nicht ausreichend
  4. Vergleichsfairness: Bei Vergleich mit Deep-Learning-Methoden könnten Unterschiede in Rechenressourcen und Tuning-Grad bestehen

Auswirkungen

  1. Akademischer Beitrag: Bietet neuen theoretischen Rahmen für Ähnlichkeitsmessung bei unvollständigen Daten
  2. Praktischer Wert: Hat direkten Wert in Empfehlungssystemen, Netzwerk-Mining und anderen Anwendungen
  3. Reproduzierbarkeit: Stellt Code-Links bereit, unterstützt Methodenvalidierung und Verbreitung

Anwendungsszenarien

  1. Empfehlungssysteme: Behandlung von Spärlichkeit in Benutzer-Element-Bewertungsmatrizen
  2. Netzwerk-Mining: Behandlung von Unvollständigkeit in Benutzerverhaltensdaten
  3. Medizinische Datenanalyse: Behandlung fehlender Werte in klinischen Daten
  4. Großskalige Datenverarbeitung: Lineare Komplexität geeignet für großskalige Anwendungen

Literaturverzeichnis

Das Papier zitiert 21 verwandte Arbeiten, die mehrere Bereiche abdecken, darunter Behandlung fehlender Daten, Kernel-Methoden und Deep Learning, und bietet eine solide theoretische Grundlage und Vergleichsbenchmarks für diese Forschung.

Zusammenfassung: Die in diesem Papier vorgeschlagene Proximity-Kernel-Methode leistet wichtige Beiträge im Bereich der Ähnlichkeitsmessung bei unvollständigen Daten. Durch geschicktes Kernel-Darstellungsdesign und kaskadierende Fallback-Strategie erreicht sie ein gutes Gleichgewicht zwischen Leistung und Effizienz. Trotz einiger Einschränkungen machen ihre Innovation und Praktikabilität sie wertvoll für verwandte Anwendungsbereiche.