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

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

作　　者：李松[1] 胡晏铭 郝晓红[1] 张丽平[1] 郝忠孝[1] Li Song;Hu Yanming;Hao Xiaohong;Zhang Liping;Hao Zhongxiao(School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080)

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《计算机研究与发展》2021年第3期609-623,共15页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61872105);黑龙江省自然科学基金项目(LH2020F047);黑龙江省留学归国人员科学基金项目(LC2018030);黑龙江省教育厅科学技术研究项目(12531z004)。

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

关 键 词：近似k近邻 高维数据 关联规则 HASH 熵 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]