ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2021, Vol. 58 ›› Issue (3): 609-623.doi: 10.7544/issn1000-1239.2021.20200285

• 软件技术 • 上一篇    下一篇

基于维度分组降维的高维数据近似k近邻查询

李松,胡晏铭,郝晓红,张丽平,郝忠孝   

  1. (哈尔滨理工大学计算机科学与技术学院 哈尔滨 150080) (lisongbeifen@163.com)
  • 出版日期: 2021-03-01
  • 基金资助: 
    国家自然科学基金项目(61872105);黑龙江省自然科学基金项目(LH2020F047);黑龙江省留学归国人员科学基金项目(LC2018030);黑龙江省教育厅科学技术研究项目(12531z004)

Approximate k-Nearest Neighbor Query of High Dimensional Data Based on Dimension Grouping and Reducing

Li Song, Hu Yanming, Hao Xiaohong, Zhang Liping, Hao Zhongxiao   

  1. (School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080)
  • Online: 2021-03-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61872105), the Natural Science Foundation of Heilongjiang Province of China (LH2020F047), the Scientific Research Foundation for Returned Scholars Abroad of Heilongjiang Province of China (LC2018030), and the Technology Research Project of Heilongjiang Provincial Education Department (12531z004).

摘要: 针对现有的高维空间近似k近邻查询算法在数据降维时不考虑维度间关联关系的问题, 首次提出了基于维度间关联规则进行维度分组降维的方法.该方法通过将相关联维度分成一组进行降维来减少数据信息的损失, 同时针对Hash降维后产生的数据偏移问题, 设置了符号位并基于符号位的特性对结果进行精炼; 为提高维度间关联规则挖掘的效率, 提出了一种新的基于UFP-tree的频繁项集挖掘算法.通过将数据映射成二进制编码来进行查询, 有效地提高了近似k近邻查询效率, 同时基于信息熵筛选编码函数, 提高了编码质量; 在查询结果精炼的过程, 基于信息熵对候选集数据的编码位进行权重的动态设定, 通过比较动态加权汉明距离和符号位碰撞次数返回最终近似k近邻结果.理论和实验研究表明, 所提方法能够较好地处理高维空间中近似k近邻查询问题.

关键词: 近似k近邻, 高维数据, 关联规则, Hash,

Abstract: Aiming at the problem that the existing high-dimensional space AkNN query algorithm does not consider the association relationship between dimensions when reducing the data dimensionality, we propose the method which groups the dimensions based on association rules between dimensions to reduce the data dimensionality first. The algorithm reduces the loss of data information by dividing the related dimensions into a group for dimensionality reduction. At the same time, in order to solve the problem of data offset caused by Hash reduction, the sign bits are set and the query result is refined based on the characteristics of the sign bits. To improve the efficiency of mining association rules between dimensions, a new frequent itemset mining algorithm based on the UFP-tree is proposed in this paper. In order to improve the efficiency of the AkNN query, we map the data into binary codes and query based on the codes. And the coding functions are filtered by information entropy to improve the coding quality. In the process of refining the query results, weights are dynamically set based on the information entropy of the encoded bits of the candidate set data, and the final AkNN results are returned by comparing the dynamic weighted Hamming distance and the number of sign bit collisions. Theoretical and experimental studies show that the proposed method can effectively deal with AkNN query problems in high-dimensional spaces.

Key words: approximate k nearest neighbor, high-dimensional data, association rules, Hash, entropy

中图分类号: