数据缺失情况下的相似性搜索

《ACM Transactions on Intelligent Systems and Technology》：Similarity Search with Data Missing

相似性搜索是数据挖掘、信息检索等领域的基础问题，其核心在于构建高精度相似性矩阵。针对数据缺失导致的矩阵误差，本文提出校准方法：利用对称性和正半定性约束构建目标函数，设计高效算法优化矩阵估计，并通过理论分析和实验验证其有效性及计算效率。

　　

摘要

相似性搜索是一个基础的研究问题，在数据挖掘、信息检索和机器学习等多个研究领域有着广泛的应用。其核心思想是根据特定的相似性度量标准，在大规模数据库中找到与查询项最相似的数据样本，并且该样本的相似性得分最高。然而，相似性搜索可能会面临高昂的计算成本和存储成本，这促使我们需要在各种场景下设计高效且快速的相似性搜索算法。但在现实世界中，数据缺失是不可避免的，这会导致相似性得分不准确，进而使得相似性矩阵也不准确。因此，在观测数据不完整的情况下，获得一个准确的相似性矩阵并非易事。为了解决这个问题，我们提出了一种相似性矩阵校准方法，用于估计高质量的相似性矩阵，从而提高相似性搜索的性能。首先，我们定义了一个目标函数，用于最小化初始不准确相似性矩阵与最优估计相似性矩阵之间的差异，并利用对称性和半正定性（PSD）这两个固有属性作为约束条件来指导校准过程。接着，我们设计了一种高效算法，能够生成接近真实相似性矩阵的高质量相似性矩阵。理论分析证明了我们提出方法的效率，而针对真实世界数据集的大量实验结果也验证了该方法在相似性矩阵校准任务及后续相似性搜索任务中的有效性和高效性。