nearest neighbor (pattern recognition)

The nearest neighbor algorithm in pattern recognition is a method for classifying phenomena based upon observable features. In the algorithm, each feature is assigned a dimension to form a multidimensional feature space. A training set of objects with apriori known class are processed by feature extraction and plotted within the multi-dimensional feature space. The offsets in each dimension are referred to as the feature vector. This is the training or learning stage. Because the engine can be retrained to classify various phenomena, pattern recognition is part of machine learning. The testing phase begins with phenomena to be classified (the class not being known apriori) and extracts the same set of features. The geometric distance is computed between the new feature vector and each apriori feature vector from the training set. The shortest distance thus computed is to the nearest neighbor. The apriori class of the nearest neighbor is now assigned to the phenomena to be classified. Obviously, this algorithm will be more computationally intensive as the size of the training set grows. Many optimizations have been given over the years, these generally seek to reduce the number of distances actually computed. Some optimizations involve partitioning the feature space, and only computing distances within specific nearby volumes. Other variations of the algorithm include the k-Nearest Neighbor algorithm where several of the nearest feature vectors are computed, and the classification is made with the highest confidence only if all of the nearest neighbors are of the same class. Nearest neighbor has some strong consistency results. As the amount of data approaches infinity, nearest neighbor is guaranteed to yield an error rate no worse than twice the Bayes error rate (the minimum achievable error rate given the distribution of the data). k-nearest neighbor is guaranteed to approach the Bayes error rate, for some value of k.

Nearest Neighbor (Pattern Recognition)

See also