Proximity-graph instance-based learning, support vector machines, and high dimensionality: An empirical comparison

Godfried T. Toussaint, Constantin Berzan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationMachine Learning and Data Mining in Pattern Recognition - 8th International Conference, MLDM 2012, Proceedings
Pages222-236
Number of pages15
DOIs
StatePublished - 2012
Event8th International Conference on Machine Learning and Data Mining in Pattern Recognition, MLDM 2012 - Berlin, Germany
Duration: Jul 13 2012Jul 20 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7376 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th International Conference on Machine Learning and Data Mining in Pattern Recognition, MLDM 2012
CountryGermany
CityBerlin
Period7/13/127/20/12

Keywords

  • Gabriel graph
  • Instance-based learning
  • machine learning
  • minimum spanning tree (MST)
  • proximity graphs
  • relative neighborhood graph (RNG)
  • sequential minimal optimization (SMO)
  • support vector machines (SVM)

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Proximity-graph instance-based learning, support vector machines, and high dimensionality: An empirical comparison'. Together they form a unique fingerprint.

Cite this