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