熵选择多重二进制编码

发布时间：2018-07-14 10:17

【摘要】：为了解决查询高维浮点型数据的近邻点需要计算代价昂贵的欧式距离,内存占用率较高的问题,将高维浮点型数据通过哈希映射函数映射为低维二进制编码,并保证同一样本点在两种空间内的归一化距离满足相似性。从而在实现近邻检索任务时,可使用代价较低的汉明距离替换欧式距离,达到降低检索复杂度的目的。为保证由哈希函数生成的二进制编码具有较优的近邻检索性能,本文首先基于查找机制得到数据集适应空间分布特性的二进制标签,然后利用SVM算法得到二进制标签的分类平面,并选择其中具有最大熵值的平面函数作为最终的哈希映射函数。为了进一步提高近邻检索性能,在训练阶段,初始化多种不同的编码中心点用以生成多重二进制标签,并得到与此相应的多重哈希函数和多重二进制编码。在检索过程中,建立了基于多重二进制编码的近邻检索体系,返回具有较小平均汉明距离的样本点作为最终检索结果。实验结果表明:与其他现存优秀算法相比,本文算法可以快速、有效地将浮点型数据转化为二进制编码,而且基于这些二进制编码的近邻检索性能较优。
[Abstract]:In order to solve the problem of high cost Euclidean distance and high memory occupancy, the high-dimensional floating-point data is mapped to low-dimensional binary code by hash mapping function. The normalized distance of the same sample point in two kinds of space satisfies the similarity. In order to reduce the retrieval complexity, the lower cost hamming distance can be used to replace the Euclidean distance. In order to ensure that the binary code generated by the hash function has better nearest neighbor retrieval performance, the binary label of the data set adapted to spatial distribution is obtained based on the lookup mechanism. Then the classification plane of binary label is obtained by SVM algorithm, and the plane function with maximum entropy is selected as the final hash mapping function. In order to further improve the performance of nearest neighbor retrieval, in the training stage, many different coding centers are initialized to generate multiple binary tags, and corresponding multiple hash functions and multiple binary codes are obtained. In the retrieval process, the nearest neighbor retrieval system based on multiplex binary coding is established, and the sample point with small average hamming distance is returned as the final retrieval result. The experimental results show that the proposed algorithm can transform floating-point data into binary code quickly and effectively, and the performance of nearest neighbor retrieval based on these binary codes is better.
【作者单位】：吉林大学计算机科学与技术学院;吉林大学符号计算与知识工程教育部重点实验室;华东师范大学计算机科学与软件工程学院;
【基金】：国家自然科学基金项目(61101155) 吉林省自然科学基金项目(20140101184JC;20150520063JH) 吉林大学研究生创新基金项目(2015051)
【分类号】：TP391.41

【相似文献】