Further information:

Download and source code:

• Download tutorial and applet source code.

Glossary of terms

classifier: A system or method that given some measurements about an object (the "features") assigns a class membership ("label") to that object.

non-parametric classifier: A classifier that does not incorporate any assumptions about the data distributions in feature space. Such an assumption is typically a parametric model, described by a small number of parameters. For example, see Bayes classifier with Gaussian distributions.

Bayes classifier (with Gaussian distributions): A parametric classifier that assumes multi-variate Gaussian ("Normal") data distributions in the multi-dimensional feature space. The class means and covariance matrix are estimated from the training data, and new samples are labeled as the class having the maximum aposteriori probability.

graph: A set of points in space, together with a set of "edges" (line segments) connecting pairs of points from the set. Typically, not all possible pairs of points are connected.

Relative Neighborhood graph: Given a set of points in the plane, two points are connected by an edge ab if there are no other points inside lune(a,b). The lune of two points is the intersection of the interiors of the two circles centered at a and at b, and both with radius equal to the distance between a and b (see [9], [12])

Beta skeletons: A continuous family of proximity graphs proposed by Kirkpatrick and Radke [10]. These graphs are defined by a positive real parameter Beta. Lower values of Beta give denser graphs (with more edges). There are two types of Beta-skeletons: lune-based (the neighborhood is an intersection of discs), and circle-based (the neighborhood is a union of discs). For Beta=1 the skeleton is in fact the Gabriel graph, and for Beta=2 the (lune-based) skeleton is the Relative Neighborhood graph. See also:

• Lune-based Beta-skeletons interactive applet and tutorial by Xiaoming Zhong.
• Circle-based Beta-skeletons interactive applet and information - in a tutorial by Yuan Zhang.

Bibliography

1

R. Barandela and E. Gasca.
Decontamination of training samples for supervised pattern recognition methods.
In F.J. et al. Ferri, editor, Advances in Pattern Recognition. Joint IAPR International Workshops SSPR and SPR 2000. Proceedings., volume 1876 of Lecture Notes in Computer Science, pages 621-630. Springer-Verlag, 2000.

2

B.V. Dasarathy.
Minimal consistent set (MCS) identification for optimal nearest neighbor decision systems design.
IEEE Transactions on Systems, Man and Cybernetics, 24(3):511-17, March 1994.

3

B.V. Dasarathy and J.S. Sanchez.
Tandem fusion of nearest neighbor editing and condensing algorithms - data dimensionality effects.
Proceedings of 15th International Conference on Pattern Recognition, pages 692-5 vol.2, sep 2000.

4

B.V. Dasarathy, J.S. Sanchez, and S. Townsend.
Nearest neighbour editing and condensing tools-synergy exploitation.
Pattern Analysis and Applications, 3(1):19-30, 2000.

5

Richard O. Duda.
Pattern recognition for human computer interfaces (course notes).
http://www-engr.sjsu.edu/knapp/HCIRODPR/PR_home.htm , 1997.
web course notes.

6

David Eppstein.
A fractal beta-skeleton with high dilation.
http://www1.ics.uci.edu/~eppstein/junkyard/betadil.html .

7

F.J. Ferri, J.S. Sanchez, and F. Pla.
Editing prototypes in the finite sample size case using alternative neighborhoods.
In Advances in Pattern Recognition. Joint IAPR International Workshops. SSPR'98 and SPR'98. Proceedings, pages 620-9. Springer-Verlag, 1998.

8

Jerzy W. Jaromczyk and Miroslaw Kowaluk.
Constructing the relative neighborhood graph in 3-dimensional Euclidean space.
Discrete Appl. Math., 31(2):181-191, 1991.
First Canadian Conference on Computational Geometry (Montreal, PQ, 1989).

9

Jerzy W. Jaromczyk and Godfried T. Toussaint.
Relative neighborhood graphs and their relatives.
Proc. IEEE, 80(9):1502-1517, sept 1992.

10

DB Kirkpatrick and JD Radke.
A framework for computational morphology.
In GT Touissant, editor, Computational Geometry, pages 217-248. Elsevier, 1985.

11

J.S. Sanchez, F. Pla, and F.J. Ferri.
Prototype selection for the nearest neighbour rule through proximity graphs.
Pattern Recognition Letters, 18(6):507-513, Jun 1997.

12

Godfried T. Toussaint.
The relative neighbourhood graph of a finite planar set.
Pattern Recognition, 12(4):261-268, 1980.

13

Godfried T. Toussaint, Binay K. Bhattacharya, and Ronald S. Poulsen.
The application of Voronoi diagrams to non-parametric decision rules.
In Proc. 16th Symposium on Computer Science and Statistics: The Interface, Atlanta, Georgia, pages 97-108, March 1984.