smile.classification

Class KNN<T>

java.lang.Object

smile.classification.KNN<T>

All Implemented Interfaces:

java.io.Serializable, Classifier<T>, SoftClassifier<T>

public class KNN<T>
extends java.lang.Object
implements SoftClassifier<T>, java.io.Serializable

K-nearest neighbor classifier. The k-nearest neighbor algorithm (k-NN) is a method for classifying objects by a majority vote of its neighbors, with the object being assigned to the class most common amongst its k nearest neighbors (k is a positive integer, typically small). k-NN is a type of instance-based learning, or lazy learning where the function is only approximated locally and all computation is deferred until classification.

The best choice of k depends upon the data; generally, larger values of k reduce the effect of noise on the classification, but make boundaries between classes less distinct. A good k can be selected by various heuristic techniques, e.g. cross-validation. In binary problems, it is helpful to choose k to be an odd number as this avoids tied votes.

A drawback to the basic majority voting classification is that the classes with the more frequent instances tend to dominate the prediction of the new object, as they tend to come up in the k nearest neighbors when the neighbors are computed due to their large number. One way to overcome this problem is to weight the classification taking into account the distance from the test point to each of its k nearest neighbors.

Often, the classification accuracy of k-NN can be improved significantly if the distance metric is learned with specialized algorithms such as Large Margin Nearest Neighbor or Neighborhood Components Analysis.

Nearest neighbor rules in effect compute the decision boundary in an implicit manner. It is also possible to compute the decision boundary itself explicitly, and to do so in an efficient manner so that the computational complexity is a function of the boundary complexity.

The nearest neighbor algorithm has some strong consistency results. As the amount of data approaches infinity, the algorithm 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-NN is guaranteed to approach the Bayes error rate, for some value of k (where k increases as a function of the number of data points).

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	KNN.Trainer<T> Trainer for KNN classifier.

Constructor Summary

Constructors

Constructor and Description
KNN(KNNSearch<T,T> knn, int[] y, int k) Constructor.
KNN(T[] x, int[] y, Distance<T> distance) Constructor.
KNN(T[] x, int[] y, Distance<T> distance, int k) Learn the K-NN classifier from data of any generalized type with a given distance definition.

Method Summary

Modifier and Type	Method and Description
static KNN<double[]>	learn(double[][] x, int[] y) Learn the 1-NN classifier from data of type double[].
static KNN<double[]>	learn(double[][] x, int[] y, int k) Learn the K-NN classifier from data of type double[].
int	predict(T x) Predicts the class label of an instance.
int	predict(T x, double[] posteriori) Predicts the class label of an instance and also calculate a posteriori probabilities.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface smile.classification.Classifier

predict

Constructor Detail

KNN

public KNN(KNNSearch<T,T> knn,
           int[] y,
           int k)

Constructor.

Parameters:

knn - k-nearest neighbor search data structure of training instances.

y - training labels in [0, c), where c is the number of classes.

k - the number of neighbors for classification.

KNN

public KNN(T[] x,
           int[] y,
           Distance<T> distance)

Constructor. By default, this is a 1-NN classifier.

Parameters:

x - training samples.

y - training labels in [0, c), where c is the number of classes.

distance - the distance measure for finding nearest neighbors.

KNN

public KNN(T[] x,
           int[] y,
           Distance<T> distance,
           int k)

Learn the K-NN classifier from data of any generalized type with a given distance definition.

Parameters:

k - the number of neighbors for classification.

x - training samples.

y - training labels in [0, c), where c is the number of classes.

distance - the distance measure for finding nearest neighbors.

Method Detail

learn

public static KNN<double[]> learn(double[][] x,
                                  int[] y)

Learn the 1-NN classifier from data of type double[].

Parameters:

x - the training samples.

y - training labels in [0, c), where c is the number of classes.

learn

public static KNN<double[]> learn(double[][] x,
                                  int[] y,
                                  int k)

Learn the K-NN classifier from data of type double[].

Parameters:

k - the number of neighbors for classification.

x - training samples.

y - training labels in [0, c), where c is the number of classes.

predict

public int predict(T x)

Description copied from interface: Classifier

Predicts the class label of an instance.

Specified by:

predict in interface Classifier<T>

Parameters:

x - the instance to be classified.

Returns:

the predicted class label.

predict

public int predict(T x,
                   double[] posteriori)

Description copied from interface: SoftClassifier

Predicts the class label of an instance and also calculate a posteriori probabilities. Classifiers may NOT support this method since not all classification algorithms are able to calculate such a posteriori probabilities.

Specified by:

predict in interface SoftClassifier<T>

Parameters:

x - the instance to be classified.

posteriori - the array to store a posteriori probabilities on output.

Returns:

the predicted class label