李志韓　王洪亞

摘 要：為了提高高維空間近鄰搜索算法的查詢性能，本文結(jié)合DSH算法和迭代PCA方法的優(yōu)點提出迭代PCA哈希算法。該算法查詢效果良好，充分利用數(shù)據(jù)集的分布信息、有嚴(yán)格的理論保證。該算法在達(dá)到相同精度的條件下較LSH算法和DSH算法查詢花費時間少。該算法提供了一種解決近鄰搜索問題有效方法。

關(guān)鍵詞：近鄰查找； 迭代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

引言

近鄰搜索被廣泛應(yīng)用在信息檢索、數(shù)據(jù)庫、圖像識別、數(shù)據(jù)挖掘以及機(jī)器學(xué)習(xí)等方面。特別是在當(dāng)下的大數(shù)據(jù)時代，億萬級別的數(shù)據(jù)量等待著計算機(jī)來處理，因此能否提出一種近鄰搜索的高效方法，在有限的時間和空間之內(nèi)滿足用戶的近鄰查詢需求就顯得尤為重要。

針對以上背景，本文提出迭代PCA哈希算法。介紹了迭代PCA哈希算法的基本思想；通過實驗驗證了迭代PCA哈希算法的實驗效果優(yōu)于DSH算法和LSH算法。

1 迭代PCA哈希算法

在近鄰搜索研究領(lǐng)域，LSH算法[1]已經(jīng)具有相當(dāng)不錯的查詢效果。但LSH算法在維度升高時，查詢效果下降明顯。為了能更好地利用數(shù)據(jù)分布信息，學(xué)者們提出了不同的哈希學(xué)習(xí)近鄰搜索算法，比如DSH算法[5]和迭代PCA方法[4]。本文結(jié)合DSH算法和迭代PCA方法的優(yōu)點，提出了迭代PCA哈希算法，并運用python編程實現(xiàn)LSH算法、DSH算法、迭代PCA哈希算法，基于實驗結(jié)果進(jìn)而分析3種算法的查詢效果。

1.1 基本思想

文獻(xiàn)[5]提出的DSH算法實現(xiàn)簡單，查詢效果優(yōu)于LSH算法。但DSH算法沒有理論證明，對數(shù)據(jù)集只進(jìn)行一次PCA，沒能充分利用數(shù)據(jù)集的分布信息。而文獻(xiàn)[4]提出的迭代PCA方法有嚴(yán)格的理論證明，通過反復(fù)對數(shù)據(jù)集進(jìn)行PCA，充分學(xué)習(xí)數(shù)據(jù)集的分布信息。然而迭代PCA方法存在2個缺陷，首先參數(shù)難以設(shè)定，其次點到空間的距離定義不合理。結(jié)合DSH算法和迭代PCA方法的優(yōu)點，本文提出迭代PCA哈希算法。迭代PCA哈希算法反復(fù)對數(shù)據(jù)集進(jìn)行PCA，充分學(xué)習(xí)數(shù)據(jù)集的分布信息；迭代PCA方法為迭代PCA哈希算法提供嚴(yán)格的理論證明；查詢實現(xiàn)上借鑒位置敏感哈希的實現(xiàn)方法，實現(xiàn)簡單。

3 結(jié)束語

本文給出了PCA空間良好“捕獲”數(shù)據(jù)集點的距離定義。這個距離定義是在PCA數(shù)學(xué)理論基礎(chǔ)上提出的，迭代PCA方法沒有明確的給出良好“捕獲”的定義，參數(shù)難以確定，在實現(xiàn)上很難做到。提出的距離定義依據(jù)投影向量的垂直距離來定義，幾何含義非常的明確清晰。

文中提出了一種近鄰搜索的方法，迭代PCA哈希算法。迭代PCA哈希算法經(jīng)過對數(shù)據(jù)集的學(xué)習(xí)，將數(shù)據(jù)集進(jìn)行分區(qū)。不過迭代PCA哈希算法所占的索引大小和內(nèi)存大小與數(shù)據(jù)導(dǎo)向型哈希算法及位置敏感哈希算法一樣。迭代PCA哈希算法在達(dá)到相同精度的前提下，大大降低了數(shù)據(jù)導(dǎo)向型哈希算法和位置敏感哈希算法所遍歷的點的個數(shù)，降低了算法的查詢時間。

實驗驗證迭代PCA哈希算法的查詢效果良好。運用python實驗工具實現(xiàn)LSH算法、DSH算法、迭代PCA哈希算法。實驗結(jié)果表明在達(dá)到相同查詢精度，迭代PCA哈希算法查詢時間最少；迭代PCA哈希算法不存在奇異點（0，0），表明數(shù)據(jù)集經(jīng)迭代PCA哈希算法投影分布稠密、均勻；迭代PCA哈希算法快速收斂到較高精度位置，減少尋找合適閾值w的時間。

參考文獻(xiàn)

[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]常會麗.基于移動搜索的關(guān)鍵詞優(yōu)化技術(shù)探索與研究[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.