Improving k-NN graph accuracy using local intrinsic dimensionality

Michael E. Houle; Vincent Oria; Arwa M. Wali

doi:10.1007/978-3-319-68474-1_8

Improving k-NN graph accuracy using local intrinsic dimensionality

Michael E. Houle, Vincent Oria, Arwa M. Wali

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Similarity Search and Applications - 10th International Conference, SISAP 2017, Proceedings
Editors	Felix Borutta, Peer Kroger, Thomas Seidl, Christian Beecks
Publisher	Springer Verlag
Pages	110-124
Number of pages	15
ISBN (Print)	9783319684734
DOIs	https://doi.org/10.1007/978-3-319-68474-1_8
State	Published - 2017
Event	10th International Conference on Similarity Search and Applications, SISAP 2017 - Munich, Germany Duration: Oct 4 2017 → Oct 6 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10609 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	10th International Conference on Similarity Search and Applications, SISAP 2017
Country/Territory	Germany
City	Munich
Period	10/4/17 → 10/6/17

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Keywords

Feature selection
Intrinsic dimensionality
Vector sparsification
k-nearest neighbor graph

Access to Document

10.1007/978-3-319-68474-1_8

Cite this

Houle, M. E., Oria, V., & Wali, A. M. (2017). Improving k-NN graph accuracy using local intrinsic dimensionality. In F. Borutta, P. Kroger, T. Seidl, & C. Beecks (Eds.), Similarity Search and Applications - 10th International Conference, SISAP 2017, Proceedings (pp. 110-124). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10609 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-68474-1_8

Houle, Michael E. ; Oria, Vincent ; Wali, Arwa M. / Improving k-NN graph accuracy using local intrinsic dimensionality. Similarity Search and Applications - 10th International Conference, SISAP 2017, Proceedings. editor / Felix Borutta ; Peer Kroger ; Thomas Seidl ; Christian Beecks. Springer Verlag, 2017. pp. 110-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{58122dbff5e846e09cf06e67f75039ef,

title = "Improving k-NN graph accuracy using local intrinsic dimensionality",

abstract = "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.",

keywords = "Feature selection, Intrinsic dimensionality, Vector sparsification, k-nearest neighbor graph",

author = "Houle, {Michael E.} and Vincent Oria and Wali, {Arwa M.}",

note = "Publisher Copyright: {\textcopyright} 2017, Springer International Publishing AG.; 10th International Conference on Similarity Search and Applications, SISAP 2017 ; Conference date: 04-10-2017 Through 06-10-2017",

year = "2017",

doi = "10.1007/978-3-319-68474-1_8",

language = "English (US)",

isbn = "9783319684734",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "110--124",

editor = "Felix Borutta and Peer Kroger and Thomas Seidl and Christian Beecks",

booktitle = "Similarity Search and Applications - 10th International Conference, SISAP 2017, Proceedings",

address = "Germany",

}

Houle, ME, Oria, V & Wali, AM 2017, Improving k-NN graph accuracy using local intrinsic dimensionality. in F Borutta, P Kroger, T Seidl & C Beecks (eds), Similarity Search and Applications - 10th International Conference, SISAP 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10609 LNCS, Springer Verlag, pp. 110-124, 10th International Conference on Similarity Search and Applications, SISAP 2017, Munich, Germany, 10/4/17. https://doi.org/10.1007/978-3-319-68474-1_8

Improving k-NN graph accuracy using local intrinsic dimensionality. / Houle, Michael E.; Oria, Vincent; Wali, Arwa M.
Similarity Search and Applications - 10th International Conference, SISAP 2017, Proceedings. ed. / Felix Borutta; Peer Kroger; Thomas Seidl; Christian Beecks. Springer Verlag, 2017. p. 110-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10609 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Improving k-NN graph accuracy using local intrinsic dimensionality

AU - Houle, Michael E.

AU - Oria, Vincent

AU - Wali, Arwa M.

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 -

Houle ME, Oria V, Wali AM. Improving k-NN graph accuracy using local intrinsic dimensionality. In Borutta F, Kroger P, Seidl T, Beecks C, editors, Similarity Search and Applications - 10th International Conference, SISAP 2017, Proceedings. Springer Verlag. 2017. p. 110-124. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-68474-1_8

Improving k-NN graph accuracy using local intrinsic dimensionality

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this