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 Representation and Similarity Measure for Incomplete Data

基本信息

  • 论文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 (Machine Learning)
  • 发表时间: 2024年10月15日 (arXiv提交)
  • 论文链接: https://arxiv.org/abs/2510.13352v1

摘要

本文针对不完整数据的相似性度量这一基础性挑战，提出了邻近核（proximity kernel）方法。传统方法要么丢弃不完整数据，要么先进行插补预处理，导致信息丢失和相似性估计偏差。邻近核直接在核特征空间中计算不完整数据间的相似性，无需在原始空间进行显式插补。该方法引入数据依赖的分箱机制结合邻近分配，将数据投影到适应局部密度变化的高维稀疏表示中。对于缺失值处理，提出了级联回退策略来估计缺失特征分布。在12个真实不完整数据集上的聚类实验表明，该方法在保持线性时间复杂度的同时，性能优于现有方法。

研究背景与动机

核心问题

不完整数据的相似性度量是网络挖掘、推荐系统和用户行为分析中的基础性挑战。现实世界数据由于用户隐私偏好、调查无响应、信息自愿不披露等因素而本质上不完整。

问题重要性

  1. 广泛存在性: 推荐系统中用户通常只对少量物品评分，产生高度稀疏的用户-物品矩阵
  2. 数据异构性: 缺失性可能同时影响数值型、类别型或混合型特征
  3. 下游任务影响: 相似性度量是聚类、分类和异常检测等任务的基础，不准确的相似性估计会显著降低任务性能

现有方法局限性

  1. 删除方法: 忽略缺失值或完全移除不完整样本，导致严重信息丢失和偏差
  2. 插补方法: 使用统计量或复杂技术填充缺失值，往往无法捕获潜在数据分布，可能引入不反映真实相似性结构的人工模式
  3. 深度学习方法: 虽然有前景，但通常需要大数据集和大量计算资源，缺乏理论保证且对超参数敏感

研究动机

现有方法采用"两阶段"策略（先插补后计算相似性），本文提出在核表示空间中联合处理插补和相似性度量的新思路。

核心贡献

  1. 提出邻近核方法: 通过等频分箱和基于Voronoi的邻近分配，将数据投影到高维稀疏表示中，无需显式密度估计即可适应局部密度
  2. 级联回退策略: 针对缺失值处理，提出从交集到并集再到全局先验的渐进式约束放松匹配策略
  3. 线性时间复杂度: 实现了线性时间复杂度，使方法可扩展到大规模数据集
  4. 实验验证: 在12个数据集上的聚类任务中展示了优于现有方法的性能

方法详解

任务定义

给定包含n个样本的数据集D = {x₁, x₂, ..., xₙ}，每个样本xᵢ ∈ ℝᵈ是d维特征向量，可能包含缺失值（表示为NaN）。目标是计算相似性函数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}|

这创建了特征空间的Voronoi图，每个中心cⱼ,ₖ定义一个Voronoi单元。

密度自适应特性:

  • 在密集区域：连续中心间距离小，创建小的Voronoi单元，相同距离的两点更可能落入不同单元
  • 在稀疏区域：连续中心间距离大，创建大的Voronoi单元，相同距离的两点更可能落入同一单元

2. 一热编码构建

对每个特征j和样本i，构建二进制向量hᵢ,ⱼ ∈ {0,1}^{n_}：

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

完整编码为所有特征的连接：zᵢ = hᵢ,₁, hᵢ,₂, ..., hᵢ,ₐ

3. 级联回退策略处理缺失值

Level 1 - 交集匹配: 寻找在所有观测特征上都匹配的样本：

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

其中C_{i,j} = {m : m≠i, b_{m,j} = b_{i,j}}

Level 2 - 并集匹配: 如果S₁(i) = ∅，放松到任意观测特征匹配：

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

Level 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}

技术创新点

  1. 密度自适应无需显式估计: 通过等频分箱和邻近分配的组合，自然实现密度自适应分割
  2. 核空间联合处理: 在表示空间而非原始空间处理缺失值，避免引入人工模式
  3. 渐进式匹配策略: 从严格到宽松的匹配准则，最大化可用信息利用

邻近核定义

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

该核满足Mercer条件（对称性和正半定性），具有概率解释：计算两样本在所有特征上落入相同分箱的期望概率。

实验设置

数据集

使用12个来自UCI的真实数据集，涵盖多个领域：

  • 医疗诊断：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种代表性方法：

  1. 简单插补：均值插补
  2. 统计方法：MissForest, MICE, KNN, EM
  3. 深度学习：GAIN, MIRACLE, MIWAE
  4. 核方法：HI-PMK

实现细节

  • 每个实验重复10次取平均值
  • 对所有基线方法进行超参数调优
  • 邻近核的分箱数在{2,3,4,6,8}中搜索

实验结果

主要结果

  1. 整体性能: 在12个数据集中的10个上取得最佳或次佳性能，平均NMI最高(0.4245)
  2. 统计显著性: Friedman-Nemenyi检验显示，邻近核除了与HI-PMK外，显著优于所有其他方法
  3. 稳定性: 箱线图显示邻近核不仅平均性能最优，在不同数据集上的表现也更加一致

缺失率鲁棒性实验

在3L和Messidor数据集上测试10%-50%的缺失率：

  • 在低到中等缺失率(10%-40%)下保持稳定优越性能
  • 在极端缺失率(50%)下仍维持合理性能
  • 相比之下，KNN和MissForest在30%缺失率时性能几乎降至零

可扩展性分析

  • 时间复杂度: O(nd + d·n log n)，对固定维度线性于样本数
  • 空间复杂度: O(nd)，线性于样本数和特征数
  • 实际运行时间: 显著快于HI-PMK和MIWAE

敏感性分析

分箱数从2到10变化时，在三个数据集上的NMI变化很小（如Mammo数据集在0.30-0.33间波动），显示方法对超参数不敏感。

相关工作

传统插补方法

  • 简单插补: 均值/众数插补，计算高效但无法保持数据自然变异性
  • KNN插补: 基于k个最相似样本，但在高维稀疏数据上表现差
  • EM算法: 基于最大似然密度估计，需要强分布假设
  • MICE: 创建多个插补数据集，计算昂贵且需要仔细指定模型
  • MissForest: 使用随机森林迭代插补，可能过拟合且缺乏收敛保证

深度学习方法

  • GAIN: 使用生成对抗网络学习缺失数据分布
  • MIWAE: 使用深度潜变量模型最大化观测数据似然下界
  • MIRACLE: 结合因果推理与深度学习改进插补质量

核方法

  • 传统距离: 欧氏距离不直接适用于不完整数据
  • HI-PMK: 数据依赖核方法，但计算复杂度高，超参数敏感

结论与讨论

主要结论

  1. 邻近核成功实现了在核特征空间中直接计算不完整数据相似性，避免了原始空间的显式插补
  2. 数据依赖分箱结合邻近分配创造了自适应局部密度的表示，无需显式密度估计
  3. 级联回退策略有效利用可用信息，从严格匹配逐步放松到全局先验
  4. 方法在保持线性时间复杂度的同时实现了优越性能

局限性

  1. 缺失机制假设: 当前评估主要基于MCAR（完全随机缺失）机制，现实数据常表现出更复杂的MAR和MNAR模式
  2. 分箱策略: 等频分箱可能不是所有数据分布的最优选择
  3. 理论保证: 缺乏级联回退机制的理论收敛保证

未来方向

  1. 研究MAR和MNAR缺失机制下的方法行为
  2. 探索自适应分箱选择策略
  3. 建立级联回退机制的理论收敛保证
  4. 扩展到更复杂的数据类型和结构

深度评价

优点

  1. 方法创新性: 将插补和相似性计算统一在核表示空间中，避免了传统两阶段方法的问题
  2. 理论基础: 提供了核有效性的严格证明，满足Mercer条件
  3. 实用性: 线性时间复杂度使方法适用于大规模应用
  4. 实验充分: 在多个数据集上的全面评估，包括统计显著性检验
  5. 鲁棒性: 对超参数不敏感，在不同缺失率下表现稳定

不足

  1. 缺失机制限制: 主要在MCAR假设下评估，对更复杂缺失模式的适应性未充分验证
  2. 密度估计: 虽然声称无需显式密度估计，但等频分箱本质上是一种隐式密度估计
  3. 特征独立性: 级联策略中特征间依赖关系的建模可能不够充分
  4. 比较公平性: 与深度学习方法的比较中，计算资源和调优程度可能存在差异

影响力

  1. 学术贡献: 为不完整数据相似性度量提供了新的理论框架
  2. 实用价值: 在推荐系统、网络挖掘等应用中具有直接价值
  3. 可复现性: 提供了代码链接，有助于方法的验证和推广

适用场景

  1. 推荐系统: 处理用户-物品评分矩阵的稀疏性
  2. 网络挖掘: 处理用户行为数据的不完整性
  3. 医疗数据分析: 处理临床数据中的缺失值
  4. 大规模数据处理: 线性复杂度适合大规模应用

参考文献

论文引用了21篇相关文献，涵盖了缺失数据处理、核方法、深度学习等多个领域的重要工作，为本研究提供了坚实的理论基础和对比基准。

总结: 本文提出的邻近核方法在不完整数据相似性度量领域具有重要贡献，通过巧妙的核表示设计和级联回退策略，实现了性能和效率的良好平衡。尽管存在一些局限性，但其创新性和实用性使其在相关应用领域具有重要价值。