基于迭代主成分分析的哈希算法研究与实现

李志韩　王洪亚

摘 要：为了提高高维空间近邻搜索算法的查询性能，本文结合DSH算法和迭代PCA方法的优点提出迭代PCA哈希算法。该算法查询效果良好，充分利用数据集的分布信息、有严格的理论保证。该算法在达到相同精度的条件下较LSH算法和DSH算法查询花费时间少。该算法提供了一种解决近邻搜索问题有效方法。

关键词：近邻查找； 迭代PCA； 查询性能； 哈希算法

Abstract： In order to improve the query performance of the neighbor search algorithm， this paper combines the advantages of DSH algorithm and iterative PCA method to propose an iterative PCA hash algorithm. The algorithm has a strict theoretical guarantee and makes full use of the distribution information of the data set， therefore has a good query effect. Compared with the LSH algorithm and the DSH algorithm， this algorithm requires less query time to achieve the same accuracy. The algorithm provides an effective method to solve the neighbor search problem.

Key words： nearest neighbor search； iterative PCA； query performance； hash algorithm

引言

近邻搜索被广泛应用在信息检索、数据库、图像识别、数据挖掘以及机器学习等方面。特别是在当下的大数据时代，亿万级别的数据量等待着计算机来处理，因此能否提出一种近邻搜索的高效方法，在有限的时间和空间之内满足用户的近邻查询需求就显得尤为重要。

针对以上背景，本文提出迭代PCA哈希算法。介绍了迭代PCA哈希算法的基本思想；通过实验验证了迭代PCA哈希算法的实验效果优于DSH算法和LSH算法。

1 迭代PCA哈希算法

在近邻搜索研究领域，LSH算法[1]已经具有相当不错的查询效果。但LSH算法在维度升高时，查询效果下降明显。为了能更好地利用数据分布信息，学者们提出了不同的哈希学习近邻搜索算法，比如DSH算法[5]和迭代PCA方法[4]。本文结合DSH算法和迭代PCA方法的优点，提出了迭代PCA哈希算法，并运用python编程实现LSH算法、DSH算法、迭代PCA哈希算法，基于实验结果进而分析3种算法的查询效果。

1.1 基本思想

文献[5]提出的DSH算法实现简单，查询效果优于LSH算法。但DSH算法没有理论证明，对数据集只進行一次PCA，没能充分利用数据集的分布信息。而文献[4]提出的迭代PCA方法有严格的理论证明，通过反复对数据集进行PCA，充分学习数据集的分布信息。然而迭代PCA方法存在2个缺陷，首先参数难以设定，其次点到空间的距离定义不合理。结合DSH算法和迭代PCA方法的优点，本文提出迭代PCA哈希算法。迭代PCA哈希算法反复对数据集进行PCA，充分学习数据集的分布信息；迭代PCA方法为迭代PCA哈希算法提供严格的理论证明；查询实现上借鉴位置敏感哈希的实现方法，实现简单。

3 结束语

本文给出了PCA空间良好“捕获”数据集点的距离定义。这个距离定义是在PCA数学理论基础上提出的，迭代PCA方法没有明确的给出良好“捕获”的定义，参数难以确定，在实现上很难做到。提出的距离定义依据投影向量的垂直距离来定义，几何含义非常的明确清晰。

文中提出了一种近邻搜索的方法，迭代PCA哈希算法。迭代PCA哈希算法经过对数据集的学习，将数据集进行分区。不过迭代PCA哈希算法所占的索引大小和内存大小与数据导向型哈希算法及位置敏感哈希算法一样。迭代PCA哈希算法在达到相同精度的前提下，大大降低了数据导向型哈希算法和位置敏感哈希算法所遍历的点的个数，降低了算法的查询时间。

实验验证迭代PCA哈希算法的查询效果良好。运用python实验工具实现LSH算法、DSH算法、迭代PCA哈希算法。实验结果表明在达到相同查询精度，迭代PCA哈希算法查询时间最少；迭代PCA哈希算法不存在奇异点（0，0），表明数据集经迭代PCA哈希算法投影分布稠密、均匀；迭代PCA哈希算法快速收敛到较高精度位置，减少寻找合适阈值w的时间。

参考文献

[1] INDYK P， MOTWANI R. Approximate nearest neighbors： Towards removing the curse of dimensionality[C]//Proceedings of the 30th Symposium on Theory of Computing（STOC'98）. DALLAS， TX， USA：ACM，1998： 604-613.

[2] SUN Yifang， WANG Wei， QIN Jianbin，et al. SRS： Solving c-approximate nearest neighbor queries in high dimensional Euclidean space with a tiny index[J].PVLDB， 2014，8（1）： 1-12.

[3] HUANG Qiang， FENG Jianlin， ZHANG Yikai， et al. Query-aware locality-sensitive hashing for approximate nearest neighbor search[C]// PVLDB ，2015，9（1）： 1-12.

[4] ABDULLAH A，ANDONI A，KANNAN R， et al. Spectral approaches to nearest neighbor search [C]//2014 IEEE 55th Annual Symposium on Foundations of Computer Science （FOCS）.Philadelphia， PA， USA：IEEE， 2014：581-590.

[5] ZHANG Wei， GAO Ke， ZHANG Yongdong， et al. Data-oriented locality sensitive hashing [C]//Proceedings of the 18th ACM international conference on Multimedia. Firenze， Italy ：ACM，2010：1131-1134 .

[6] HOTELLING H. Analysis of a complex of statistical variables into principal components[J]. Journal of Educational Psychology， 1933，24：417-441.

[7] ROBINSONJ T. The K-D-B-Tree ： A search structure for large multidimensio- nal dynamic indexes [C]//Proc. ACM-SIGMOD International Conference on Management of Data .Ann Arbor，MI，USA：ACM，1981：10-18.

[8] HENRICH A， SIX H W， WIDMAYER P. The LSD tree： Spatial access to multidimensional point and non point objects[C]//Proceedings of the Fifteenth International Conference on VLDB. Amsterdam， The Netherlands：Morgan Kaufman，1989：43-53.

[9] KIBRIYA A M， FRANK E. An empirical comparison of exact nearest neighbour algorithms[M]//KOK J N， KORONACKI J， DE MANTARAS R L， et al. Knowledge Discovery in Databases： PKDD 2007. Lecture Notes in Computer Science. Berlin/ Heidelberg：Springer， 2007：140-151.

[10]MOORE A. Efficient Memory-based Learning for Robot Control[D]. USA：University of Cambridge， 1991.

[11]GUTTMAN A. R-trees： a dynamic index structure for spratial searching[M]//Readings in database systems. San Francisco， CA， USA：Morgan Kaufmann Publishers Inc.，1988：599-609.

[12]BECKMANNN， KRIEGEL H P， SCHNEIDER R， et al. The R*-tree： An efficient and robust access method for points and rectangles+ [C]// Proceedings of the 1990 ACM SIGMOD international conference on Management of daTA. Atlantic City：ACM，1990：322-331.

[13]SELLIS T K， ROUSSOPOULOS N， FALOUTSOS C. The R+-tree： A dynamic index for multidimensional objects [C]// Proceedings of the 13th VLDB. Brighton， England：[s.n.]， 1987： 507- 518.

[14]常會丽.基于移动搜索的关键词优化技术探索与研究[J]. 信息与电脑，2018（6）：6-7，10.

[15]BAWA M，CONDIE T， GANESAN P. LSH Forest： Self tuning indexes for similarity search[C]// International Conference on World Wide Web， WWW 2005. Chiba， Japan：IW3C2，2005：651-660.