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

• 作者: 刁兴春 周星 曹建军 许永平 郑奇斌
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 数据质量 数据完整性 数据填补 k近邻算法 局部敏感哈希
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 第三届CCF大数据学术会议(CCF BigData 2015)
• 页码范围: 397-401
• 页数: 5页
• 分类号: TP391
• 字数: 6764字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2016.02.0397

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刁兴春		13	128	7.0	11.0
2	曹建军		10	115	7.0	10.0
3	郑奇斌	解放军理工大学指挥信息系统学院	3	8	1.0	2.0
4	周星	解放军理工大学指挥信息系统学院	8	40	2.0	6.0
5	许永平		2	29	2.0	2.0