TY - GEN
T1 - Improving k-NN graph accuracy using local intrinsic dimensionality
AU - Houle, Michael E.
AU - Oria, Vincent
AU - Wali, Arwa M.
N1 - Funding Information:
Acknowledgments. M.E. Houle acknowledges the financial support of JSPS Kakenhi Kiban (A) Research Grant 25240036 and JSPS Kakenhi Kiban (B) Research Grant 15H02753. V. Oria acknowledges the financial support of NSF Research Grant DGE 1565478.
PY - 2017
Y1 - 2017
N2 - The k-nearest neighbor (k-NN) graph is an important data structure for many data mining and machine learning applications. The accuracy of k-NN graphs depends on the object feature vectors, which are usually represented in high-dimensional spaces. Selecting the most important features is essential for providing compact object representations and for improving the graph accuracy. Having a compact feature vector can reduce the storage space and the computational complexity of search and learning tasks. In this paper, we propose NNWID-Descent, a similarity graph construction method that utilizes the NNF-Descent framework while integrating a new feature selection criterion, Support-Weighted Intrinsic Dimensionality, that estimates the contribution of each feature to the overall intrinsic dimensionality. Through extensive experiments on various datasets, we show that NNWID-Descent allows a significant amount of local feature vector sparsification while still preserving a reasonable level of graph accuracy.
AB - The k-nearest neighbor (k-NN) graph is an important data structure for many data mining and machine learning applications. The accuracy of k-NN graphs depends on the object feature vectors, which are usually represented in high-dimensional spaces. Selecting the most important features is essential for providing compact object representations and for improving the graph accuracy. Having a compact feature vector can reduce the storage space and the computational complexity of search and learning tasks. In this paper, we propose NNWID-Descent, a similarity graph construction method that utilizes the NNF-Descent framework while integrating a new feature selection criterion, Support-Weighted Intrinsic Dimensionality, that estimates the contribution of each feature to the overall intrinsic dimensionality. Through extensive experiments on various datasets, we show that NNWID-Descent allows a significant amount of local feature vector sparsification while still preserving a reasonable level of graph accuracy.
KW - Feature selection
KW - Intrinsic dimensionality
KW - Vector sparsification
KW - k-nearest neighbor graph
UR - http://www.scopus.com/inward/record.url?scp=85031303591&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85031303591&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-68474-1_8
DO - 10.1007/978-3-319-68474-1_8
M3 - Conference contribution
AN - SCOPUS:85031303591
SN - 9783319684734
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 110
EP - 124
BT - Similarity Search and Applications - 10th International Conference, SISAP 2017, Proceedings
A2 - Borutta, Felix
A2 - Kroger, Peer
A2 - Seidl, Thomas
A2 - Beecks, Christian
PB - Springer Verlag
T2 - 10th International Conference on Similarity Search and Applications, SISAP 2017
Y2 - 4 October 2017 through 6 October 2017
ER -