TY - GEN
T1 - Proximity-graph instance-based learning, support vector machines, and high dimensionality
T2 - 8th International Conference on Machine Learning and Data Mining in Pattern Recognition, MLDM 2012
AU - Toussaint, Godfried T.
AU - Berzan, Constantin
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2012
Y1 - 2012
N2 - Previous experiments with low dimensional data sets have shown that Gabriel graph methods for instance-based learning are among the best machine learning algorithms for pattern classification applications. However, as the dimensionality of the data grows large, all data points in the training set tend to become Gabriel neighbors of each other, bringing the efficacy of this method into question. Indeed, it has been conjectured that for high-dimensional data, proximity graph methods that use sparser graphs, such as relative neighbor graphs (RNG) and minimum spanning trees (MST) would have to be employed in order to maintain their privileged status. Here the performance of proximity graph methods, in instance-based learning, that employ Gabriel graphs, relative neighborhood graphs, and minimum spanning trees, are compared experimentally on high-dimensional data sets. These methods are also compared empirically against the traditional k-NN rule and support vector machines (SVMs), the leading competitors of proximity graph methods.
AB - Previous experiments with low dimensional data sets have shown that Gabriel graph methods for instance-based learning are among the best machine learning algorithms for pattern classification applications. However, as the dimensionality of the data grows large, all data points in the training set tend to become Gabriel neighbors of each other, bringing the efficacy of this method into question. Indeed, it has been conjectured that for high-dimensional data, proximity graph methods that use sparser graphs, such as relative neighbor graphs (RNG) and minimum spanning trees (MST) would have to be employed in order to maintain their privileged status. Here the performance of proximity graph methods, in instance-based learning, that employ Gabriel graphs, relative neighborhood graphs, and minimum spanning trees, are compared experimentally on high-dimensional data sets. These methods are also compared empirically against the traditional k-NN rule and support vector machines (SVMs), the leading competitors of proximity graph methods.
KW - Gabriel graph
KW - Instance-based learning
KW - machine learning
KW - minimum spanning tree (MST)
KW - proximity graphs
KW - relative neighborhood graph (RNG)
KW - sequential minimal optimization (SMO)
KW - support vector machines (SVM)
UR - http://www.scopus.com/inward/record.url?scp=84864922736&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84864922736&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-31537-4_18
DO - 10.1007/978-3-642-31537-4_18
M3 - Conference contribution
AN - SCOPUS:84864922736
SN - 9783642315367
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 222
EP - 236
BT - Machine Learning and Data Mining in Pattern Recognition - 8th International Conference, MLDM 2012, Proceedings
Y2 - 13 July 2012 through 20 July 2012
ER -