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

不完全データのカーネル表現と類似度測度

基本情報

論文ID: 2510.13352
タイトル: Kernel Representation and Similarity Measure for Incomplete Data
著者: Yang Cao, Sikun Yang, Kai He, Wenjun Ma, Ming Liu, Yujiu Yang, Jian Weng
分類: cs.LG（機械学習）
発表日時: 2024年10月15日（arXiv投稿）
論文リンク: https://arxiv.org/abs/2510.13352v1

要旨

本論文は、不完全データの類似度測度という基礎的課題に対して、近接カーネル（proximity kernel）手法を提案している。従来の手法は不完全データを破棄するか、事前に補完処理を行うかのいずれかであり、情報損失と類似度推定の偏りをもたらしていた。近接カーネルは、元の空間での明示的な補完を必要とせず、カーネル特徴空間において不完全データ間の類似度を直接計算する。本手法は、データ依存のビニング機構と近接割り当てを導入し、局所密度変化に適応する高次元疎表現にデータを投影する。欠損値処理に対しては、欠損特徴分布を推定するためのカスケード後退戦略を提案している。12個の実不完全データセット上のクラスタリング実験により、線形時間計算量を維持しながら既存手法を上回る性能を示している。

研究背景と動機

核心的問題

不完全データの類似度測度は、ネットワークマイニング、推薦システム、ユーザー行動分析における基礎的課題である。実世界のデータは、ユーザープライバシー選好、調査無回答、情報の自発的非開示などの要因により、本質的に不完全である。

問題の重要性

広範な存在性: 推薦システムにおいて、ユーザーは通常少数のアイテムのみを評価し、高度に疎なユーザー-アイテム行列を生成する
データの異質性: 欠損は数値型、カテゴリ型、または混合型特徴に同時に影響を与える可能性がある
下流タスクへの影響: 類似度測度はクラスタリング、分類、異常検知などのタスクの基礎であり、不正確な類似度推定はタスク性能を著しく低下させる

既存手法の限界

削除手法: 欠損値を無視するか不完全サンプルを完全に除去し、深刻な情報損失と偏りをもたらす
補完手法: 統計量または複雑な技術を用いて欠損値を埋めるが、潜在的なデータ分布を捉えられず、真の類似度構造を反映しない人工的パターンを導入する可能性がある
深層学習手法: 有望ではあるが、通常大規模データセットと膨大な計算資源を必要とし、理論的保証が欠け、超パラメータに敏感である

研究動機

既存手法は「二段階」戦略（先補完後類似度計算）を採用しているが、本論文はカーネル表現空間における補完と類似度測度の統合処理という新しい視点を提案する。

核心的貢献

近接カーネル手法の提案: 等頻度ビニングとボロノイベース近接割り当てを通じて、明示的密度推定を必要とせず局所密度に適応する高次元疎表現にデータを投影する
カスケード後退戦略: 欠損値処理に対して、交集合から和集合を経て全体先験への段階的制約緩和マッチング戦略を提案する
線形時間計算量: 線形時間計算量を実現し、大規模データセットへの拡張性を確保する
実験検証: 12個のデータセット上のクラスタリングタスクにおいて既存手法を上回る性能を実証する

手法の詳細

タスク定義

n個のサンプルを含むデータセットD = {x₁, x₂, ..., xₙ}が与えられ、各サンプルxᵢ ∈ ℝᵈはd次元特徴ベクトルであり、欠損値（NaNで表記）を含む可能性がある。目標は、任意の2つのサンプル間の類似度を定量化する類似度関数s : D × D → 0,1を計算することであり、これは下流のクラスタリングなどのタスクに用いられる。

モデルアーキテクチャ

1. データ依存ビニングと近接割り当て

ビニング中心の選択: 各特徴jに対して、等頻度ビニングを用いてnᵦᵢₙₛ個のビニング中心を選択する：

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

ここでk ∈ {1,2,...,nᵦᵢₙₛ}、Xₒᵦₛ,ⱼは特徴jのすべての観測値である。

近接割り当て機構: 従来の区間メンバーシップではなく近接割り当てを採用する：

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

これは特徴空間のボロノイ図を作成し、各中心cⱼ,ₖはボロノイセルを定義する。

密度適応特性:

密集領域では：連続中心間距離が小さく、小さなボロノイセルを作成し、同じ距離の2点がより異なるセルに落ちやすい
疎領域では：連続中心間距離が大きく、大きなボロノイセルを作成し、同じ距離の2点がより同じセルに落ちやすい

2. ワンホットエンコーディング構築

各特徴jとサンプルiに対して、二進ベクトルhᵢ,ⱼ ∈ {0,1}^{n_}を構築する：

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

完全なエンコーディングはすべての特徴の連結：zᵢ = hᵢ,₁, hᵢ,₂, ..., hᵢ,ₐ

3. 欠損値処理のためのカスケード後退戦略

レベル1 - 交集合マッチング: すべての観測特徴でマッチするサンプルを探索する：

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

ここでC_{i,j} = {m : m≠i, b_{m,j} = b_{i,j}}

レベル2 - 和集合マッチング: S₁(i) = ∅の場合、任意の観測特徴でのマッチングに緩和する：

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

レベル3 - 全体先験: S₂(i) = ∅の場合、全体分布を使用する：

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

各レベルに対して、カーネル平均埋め込み（KME）を用いて欠損エンコーディングを推定する：

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

技術的革新点

明示的推定なしの密度適応: 等頻度ビニングと近接割り当ての組み合わせにより、密度適応分割を自然に実現する
カーネル空間での統合処理: 元の空間ではなく表現空間で欠損値を処理し、人工的パターンの導入を回避する
段階的マッチング戦略: 厳密から緩いマッチング基準への移行により、利用可能な情報の活用を最大化する

近接カーネルの定義

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

このカーネルはマーサー条件（対称性と正半定値性）を満たし、確率的解釈を持つ：すべての特徴において2つのサンプルが同じビニングに落ちる期待確率を計算する。

実験設定

データセット

UCIから12個の実データセットを使用し、複数の領域をカバーしている：

医療診断：Kidney, Hepatitis, Heart, Tumor, Cancer
生物分類：Soybean, Mushroom
金融分析：Credit
人口予測：Adult
政治分析：Voting
その他：Mammography, Horse

データセットのサンプル数は155から48,842、次元数は5から35、欠損率は0.15%から19.39%である。

評価指標

標準化相互情報量（NMI）を用いてクラスタリング品質を評価し、K-meansクラスタリングを採用し、クラスタ数を真のクラス数に設定する。

比較手法

9種類の代表的手法：

単純補完：平均値補完
統計的手法：MissForest, MICE, KNN, EM
深層学習：GAIN, MIRACLE, MIWAE
カーネル手法：HI-PMK

実装詳細

各実験を10回繰り返し平均値を取得
すべてのベースライン手法に対して超パラメータ調整を実施
近接カーネルのビニング数を{2,3,4,6,8}から探索

実験結果

主要結果

全体性能: 12個のデータセット中10個で最良または次点の性能を達成し、平均NMIが最高（0.4245）
統計的有意性: Friedman-Nemenyi検定により、近接カーネルはHI-PMKを除くすべての他の手法に対して統計的に有意に優れていることが示された
安定性: 箱ひげ図は、近接カーネルが平均性能で最適であるだけでなく、異なるデータセット間での性能がより一貫していることを示している