基于特征选择的局部敏感哈希位选择算法

doi:10.11959/j.issn.2096-0271.2021061

Abstract

Abstract:

Locality sensitive hashing is one of the most popular information retrieval methods, which needs to generate long hashing bits to meet the retrieval requirement.However, a long hashing bits requires huge storage space, and contains plenty of redundant hashing bits.In order to solve this problem, ten simple and efficient selection algorithms in feature engineering were adopted to extract the hashing bits which carry the largest amount of information from the long hashing bits which were generated by locality sensitive hashing, and the redundant and useless hash bits were removed.Those ten algorithms tried to capture the performance of each hashing bit or the correlation among bits, such as variance and hamming distance.During selection process, the useless or high-correlated hashing bits were removed.Then the selected hashing bits were compared with the original long hashing bits.The experimental results on four common datasets show that the selected hashing bits works as well as the original hashing bits, and their reduction ratio can reach from 30% to 70%.

Key words: approximate nearest neighbor search, hashing learning, hashing bit selection, feature selection, dimensionality reduction

CLC Number:

TP391

Wenhua ZHOU, Huawen LIU, Enhui LI. Algorithm of locality sensitive hashing bit selection based on feature selection[J]. Big Data Research, 2021, 7(6): 67-77.

Figures/Tables 7

算法	CIFAR-10				MNIST
算法	128/102	256/205	512/410	1 024/819	128/102	256/205	512/410	1 024/819
LSH	0.169 9	0.179 0	0.183 9	0.188 0	0.390 4	0.410 2	0.428 1	0.451 6
NDomSet	0.167 5	0.178 9	0.184 1	0.190 4	0.389 8	0.412 5	0.434 5	0.460 4
Euc	0.161 0	0.178 7	0.178 6	0.184 9	$0 . 3638$	0.391 9	0.412 7	0.439 2
Cosine	0.168 1	0.178 6	0.183 6	0.187 8	0.380 0	0.406 4	0.429 8	0.453 7
HCF	0.166 3	0.178 5	0.182 4	0.187 8	0.378 2	0.402 7	0.423 9	0.448 6
Jaccard	0.168 2	0.178 3	0.183 1	0.187 8	0.377 9	0.404 5	0.428 3	0.453 9
MI	0.168 5	0.178 2	0.183 5	0.187 6	0.380 6	0.406 4	0.428 1	0.453 6
Hamming	0.168 4	0.178 1	0.183 3	0.187 5	0.379 2	0.406 8	0.428 5	0.455 2
LCV	0.167 8	0.178 0	0.184 1	0.190 0	$0 . 3650$	0.392 3	0.417 8	0.440 9
LS	0.159 9	0.177 8	0.178 0	0.184 5	$0 . 3613$	$0 . 3856$	$0 . 4045$	0.432 8
IE	0.165 9	0.177 7	0.182 2	0.187 6	$0 . 3651$	0.392 3	0.417 8	0.441 1
Random	0.166 3	0.177 6	0.182 5	0.187 4	$0 . 3751$	0.403 6	0.424 0	0.450 5

References 30

[1]	KALANTIDIS Y , AVRITHIS Y . Locally optimized product quantization for approximate nearest neighbor search[C]// Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway:IEEE Press, 2014: 2329-2336.
[2]	ANDONI A , INDYK P . Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions[C]// Proceedings of the 2006 47th Annual IEEE Symposium on Foundations of Computer Science. Piscataway:IEEE Press, 2006: 459-468.
[3]	BENTLEY J L . Multidimensional binary search trees used for associative searching[J]. Communications of the ACM, 1975,18(9): 509-517.
[4]	SILPA-ANAN C , HARTLEY R . Optimised KD-trees for fast image descriptor matching[C]// Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway:IEEE Press, 2008: 1-8.
[5]	WEISS Y , ANTONIO T , ROB F . Spectral hashing[C]// Advances in Neural Information Processing Systems 21. Cambridge:The MIT Press, 2008: 1753-1760.
[6]	GIONIS A , INDYK P , MOTWANI R . Similarity search in high dimensions via hashing[C]// Proceedings of the 25th International Conference on Very Large Data Bases. California:Morgan Kaufmann Publishers, 1999: 518-529.
[7]	YAN C G , GONG B , WEI Y X ,et al. Deep multi-view enhancement hashing for image retrieval[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021,43(4): 1445-1451.
[8]	WANG J D , ZHANG T , SONG J K ,et al. A survey on learning to hash[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018,40(4): 769-790.
[9]	WANG Z , DUAN L Y , YUAN J S ,et al. To project more or to quantize more:minimizing reconstruction bias for learning compact binary codes[C]// Proceedings of the 25th International Joint Conference on Artificial Intelligence. California:AAAI Press, 2016: 2181-2188.
[10]	GONG Y C , LAZEBNIK S , GORDO A ,et al. Iterative quantization:a procrustean approach to learning binary codes for largescale image retrieval[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013,35(12): 2916-2929.
[11]	NOROUZI M , FLEET D J . Minimal Loss Hashing for Compact Binary Codes[C]// Proceedings of the 28th International Conference on Machine Learning. Madison:Omnipress, 2011: 353-360.
[12]	LIU W , WANG J , JI R R ,et al. Supervised hashing with kernels[C]// Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway:IEEE Press, 2012: 2074-2081.
[13]	WANG J , KUMAR S , CHANG S F . Semisupervised hashing for large-scale search[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012,34(12): 2393-2406.
[14]	ZHAO F , HUANG Y Z , WANG L ,et al. Deep semantic ranking based hashing for multi-label image retrieval[C]// Proceedings of the 2015 IEEE Conference on Computer Vision and Patten Recognition. Piscataway:IEEE Press, 2015: 1556-1564.
[15]	WANG J , LIU W , SUN A X ,et al. Learning hash codes with listwise supervision[C]// Proceedings of the 2013 IEEE International Conference on Computer Vision. Piscataway:IEEE Press, 2013: 3032-3039.
[16]	LIU X L , HE J F , CHANG S F . Hash bit selection for nearest neighbor search[J]. IEEE Transactions on Image Processing, 2017,26(11): 5367-5380.
[17]	LIU X L , HE J F , LANG B ,et al. Hash bit selection:a unified solution for selection problems in hashing[C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Piscataway:IEEE Press, 2013: 1570-1577.
[18]	ZHANG D C , LIU X L , LANG B . Hash bit selection using Markov process for approximate nearest neighbor search[C]// Proceedings of the International Conference on Advances in Mobile Computing. New York:ACM Press, 2013: 205-208.
[19]	AL-TASHI Q , ABDULKADIR S J , RAIS H M ,et al. Approaches to multi-objective feature selection:a systematic literature review[J]. IEEE Access, 2020,8: 125076-125096.
[20]	CAI J , LUO J W , WANG S L ,et al. Feature selection in machine learning:a new perspective[J]. Neurocomputing, 2018,300: 70-79.
[21]	HEO J P , LEE Y , HE J F ,et al. Spherical hashing[C]// Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway:IEEE Press, 2012: 2957-2964.
[22]	SENLIOL B , GULGEZEN G , YU L ,et al. Fast correlation based filter (FCBF) with a different search strategy[C]// Proceedings of the 2008 23rd International Symposium on Computer and Information Sciences. Piscataway:IEEE Press, 2008: 1-4.
[23]	NGUYEN H V , BAI L . Cosine similarity metric learning for face verification[C]// Proceedings of the Asian Conference on Computer Vision. Heidelberg:Springer, 2010: 709-720.
[24]	GIERLICHS B , BATINA L , TUYLS P ,et al. Mutual information analysis[C]// Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems. Heidelberg:Springer, 2011: 426-442.
[25]	HE X F , CAI D , NIYOGI P . Laplacian score for feature selection[C]// Advances in Neural Information Processing System.[S.l.:s.n], 2005: 507-514.
[26]	ZHENG K F , WANG X J . Feature selection method with joint maximal information entropy between features and class[J]. Patten Recognition, 2018,77: 20-29.
[27]	ABOUELNAGA Y , ALI O S , RADY H ,et al. CIFAR-10:KNN-based ensemble of classifiers[C]// Proceedings of the 2016 International Conference on Computational Science and Computational Intelligence. Piscataway:IEEE Press, 2016: 1192-1195.
[28]	COHEN G , AFSHAR S , TAPSON J ,et al. EMNIST:extending MNIST to handwritten letters[C]// Proceedings of the 2017 International Joint Conference on Neural Networks. Piscataway:IEEE Press, 2017: 2921-2926.
[29]	RUSSELL B C , TORRALBA A , MURPHY K P ,et al. LabelMe:a database and web-based tool for image annotation[J]. International Journal of Computer Vision, 2008,77: 157-173.
[30]	TANG J Y , LEWIS P H . A study of quality issues for image-annotation with the Corel dataset[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2007,17(3): 384-389.

Metrics

Recommended 0

No Suggested Reading articles found!

哈希码长度/bit	256	307	358	409	512
运行时间/s	7.74	9.22	10.42	11.92	14.47

选择算法	时间复杂度	MAP	运行时间/s
NDomSet	O(n²d)	0.184 1	10.680 9
Euc	O(k²)	0.178 6	0.102 9
Cosine	O(k²)	0.183 6	0.195 5
HCF	O(k²)	0.182 4	0.143 9
Jaccard	O(k²)	0.183 1	0.581 3
MI	O(nk²)	0.183 5	10.143 9
Hamming	O(k²)	0.183 3	0.370 8
LCV	O(nk)	0.184 1	0.121 2
LS	O(n²)	0.178 0	0.403 4
IE	O(k)	0.182 2	0.005 7
Random	O(1)	0.182 5	0.000 7

Algorithm of locality sensitive hashing bit selection based on feature selection

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 30

Related Articles 1

Metrics

Recommended 0