Proximity Graphs for Nearest NeighborDecision Rules: Recent Progress

摘要

In the typical nonparametric approach to pattern classifcation, randomrndata (the training set of patterns) are collected and used to design a decisionrnrule (classifer). One of the most well known such rules is the к-nearest-rnneighbor decision rule (also known as instance-based learning, and lazy learn-rning) in which an unknown pattern is classifed into the majority class amongrnits к nearest neighbors in the training set. Several questions related to thisrnrule have received considerable attention over the years. Such questions in-rnclude the following. How can the storage of the training set be reducedrnwithout degrading the performance of the decision rule? How should the re-rnduced training set be selected to represent the diu000berent classes? How largernshould к be? How should the value of к be chosen? Should all к neighborsrnbe equally weighted when used to decide the class of an unknown pattern? Ifrnnot, how should the weights be chosen? Should all the features (attributes)rnwe weighted equally and if not how should the feature weights be chosen?rnWhat distance metric should be used? How can the rule be made robust tornoverlapping classes or noise present in the training data? How can the rule bernmade invariant to scaling of the measurements? Geometric proximity graphsrnsuch as Voronoi diagrams and their many relatives provide elegant solutionsrnto most of these problems. After a brief and non-exhaustive review of somernof the classical canonical approaches to solving these problems, the methodsrnthat use proximity graphs are discussed, some new observations are made,rnand avenues for further research are proposed.