基于迭代主成分分析的哈希算法研究與實現

李志韓　王洪亞

摘 要：為了提高高維空間近鄰搜索算法的查詢性能，本文結合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.