结合局部敏感哈希的k近邻数据填补算法

来源：计算机应用杂志2016年第2期北京时间：

作者：郑奇斌, 刁兴春, 曹建军, 周星, 许永平

单位：1. 解放军理工大学 指挥信息系统学院, 南京 210007;2. 总参第六十三研究所, 南京 210007

摘要：k近邻(kNN)算法是缺失数据填补的常用算法,但由于需要逐个计算所有记录对之间的相似度,因此其填补耗时较高。为提高算法效率,提出结合局部敏感哈希(LSH)的kNN数据填补算法LSH-kNN。首先,对不存在缺失的完整记录进行局部敏感哈希,为之后查找近似最近邻提供索引;其次,针对枚举型、数值型以及混合型缺失数据分别提出对应的局部敏感哈希方法,对每一条待填补的不完整记录进行局部敏感哈希,按得到的哈希值找到与其疑似相似的候选记录;最后在候选记录中通过逐个计算相似度来找到其中相似程度最高的k条记录,并按照kNN算法对不完整记录进行填补。通过在4个真实数据集上的实验表明,结合局部敏感哈希的kNN填补算法LSH-kNN相对经典的kNN算法能够显著提高填补效率,并且保持准确性基本不变。

关键词：数据质量,数据完整性,数据填补,k近邻算法,局部敏感哈希

基金资助：国家自然科学基金资助项目(61371196);中国博士后科学基金特别资助项目(201003797);解放军理工大学预研基金项目(20110604,41150301)。