Distance-Based Classifiers

Distance to classified samples of a training database can be used to determine labels of an unknown sample. Depending on the type of classifier, a distance-based classifier is related to Bayesian inference in different ways. Two popular methods exemplifying various concepts will be presented in this chapter. A nearest centroid classifier computes distances of an unseen sample to the class means in feature space. The closest distance to one of the class means decides on the label. Under certain assumptions about the likelihood function, this maximizes the posterior probability of a sample for this label given its features. A kNN classifier, however, bases its decision for a label on the k closest samples to an unseen sample. It directly approximates the a posteriori probability of a sample to belong to a class given its features. The quality of the estimate depends on the density of labeled training data. Efficient determination of the closest samples during inference requires some preprocessing to exclude far-away samples from the search. We will explain how this can be done by representing the feature space by a binary space partitioning tree that is created in a set-up phase prior to inference.