Click or drag to resize
Accord.NET (logo)

KNearestNeighbors Class

K-Nearest Neighbor (k-NN) algorithm.
Inheritance Hierarchy
SystemObject
  Accord.MachineLearningTransformBaseDouble, Int32
    Accord.MachineLearningClassifierBaseDouble, Int32
      Accord.MachineLearningMulticlassClassifierBaseDouble
        Accord.MachineLearningMulticlassScoreClassifierBaseDouble
          Accord.MachineLearningBaseKNearestNeighborsKNearestNeighbors, Double, IMetricDouble
            Accord.MachineLearningKNearestNeighbors

Namespace:  Accord.MachineLearning
Assembly:  Accord.MachineLearning (in Accord.MachineLearning.dll) Version: 3.8.0
Syntax
[SerializableAttribute]
public class KNearestNeighbors : BaseKNearestNeighbors<KNearestNeighbors, double[], IMetric<double[]>>
Request Example View Source

The KNearestNeighbors type exposes the following members.

Constructors
  NameDescription
Public methodKNearestNeighbors
Creates a new KNearestNeighbors.
Public methodKNearestNeighbors(Int32)
Creates a new KNearestNeighbors.
Public methodKNearestNeighbors(Int32, IMetricDouble)
Creates a new KNearestNeighbors.
Public methodKNearestNeighbors(Int32, Double, Int32) Obsolete.
Creates a new KNearestNeighbors.
Public methodKNearestNeighbors(Int32, Int32, Double, Int32) Obsolete.
Creates a new KNearestNeighbors.
Public methodKNearestNeighbors(Int32, Int32, Double, Int32, IMetricDouble) Obsolete.
Creates a new KNearestNeighbors.
Top
Properties
  NameDescription
Public propertyClassCount Obsolete.
Gets the number of class labels handled by this classifier.
Public propertyDistance
Gets or sets the distance function used as a distance metric between data points.
(Inherited from BaseKNearestNeighborsTModel, TInput, TDistance.)
Public propertyInputs
Gets the set of points given as input of the algorithm.
(Inherited from BaseKNearestNeighborsTModel, TInput, TDistance.)
Public propertyK
Gets or sets the number of nearest neighbors to be used in the decision. Default is 5.
(Inherited from BaseKNearestNeighborsTModel, TInput, TDistance.)
Public propertyNumberOfClasses
Gets the number of classes expected and recognized by the classifier.
(Inherited from ClassifierBaseTInput, TClasses.)
Public propertyNumberOfInputs
Gets the number of inputs accepted by the model.
(Inherited from TransformBaseTInput, TOutput.)
Public propertyNumberOfOutputs
Gets the number of outputs generated by the model.
(Inherited from TransformBaseTInput, TOutput.)
Public propertyOutputs
Gets the set of labels associated with each Inputs point.
(Inherited from BaseKNearestNeighborsTModel, TInput, TDistance.)
Public propertyToken
Gets or sets a cancellation token that can be used to stop the learning algorithm while it is running.
(Inherited from BaseKNearestNeighborsTModel, TInput, TDistance.)
Top
Methods
  NameDescription
Public methodCompute(Double) Obsolete.
Computes the most likely label of a new given point.
Public methodCompute(Double, Double) Obsolete.
Computes the most likely label of a new given point.
Public methodCompute(Double, Double) Obsolete.
Computes the most likely label of a new given point.
Public methodDecide(TInput)
Computes class-label decisions for a given set of input vectors.
(Inherited from ClassifierBaseTInput, TClasses.)
Public methodDecide(TInput)
Computes a class-label decision for a given input.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodDecide(TInput, TClasses)
Computes a class-label decision for a given input.
(Inherited from ClassifierBaseTInput, TClasses.)
Public methodDecide(TInput, Boolean)
Computes class-label decisions for the given input.
(Inherited from MulticlassClassifierBaseTInput.)
Public methodDecide(TInput, Double)
Computes class-label decisions for the given input.
(Inherited from MulticlassClassifierBaseTInput.)
Public methodDecide(TInput, Int32)
Computes class-label decisions for the given input.
(Inherited from MulticlassClassifierBaseTInput.)
Public methodDecide(TInput, Double)
Computes a class-label decision for a given input.
(Inherited from MulticlassClassifierBaseTInput.)
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Protected methodFinalize
Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection.
(Inherited from Object.)
Public methodStatic memberFromTree
Creates a new KNearestNeighbors algorithm from an existing KDTreeT. The tree must have been created using the input points and the point's class labels as the associated node information.
Public methodGetHashCode
Serves as the default hash function.
(Inherited from Object.)
Public methodGetNearestNeighbors
Gets the top K points that are the closest to a given input.
(Overrides BaseKNearestNeighborsTModel, TInput, TDistanceGetNearestNeighbors(TInput, Int32).)
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Public methodLearn(TInput, Boolean, Double)
Learns a model that can map the given inputs to the given outputs.
(Inherited from BaseKNearestNeighborsTModel, TInput, TDistance.)
Public methodLearn(TInput, Int32, Double)
Learns a model that can map the given inputs to the given outputs.
(Inherited from BaseKNearestNeighborsTModel, TInput, TDistance.)
Public methodLearn(Double, Int32, Double)
Learns a model that can map the given inputs to the given outputs.
(Overrides BaseKNearestNeighborsTModel, TInput, TDistanceLearn(TInput, Int32, Double).)
Protected methodMemberwiseClone
Creates a shallow copy of the current Object.
(Inherited from Object.)
Public methodScore(TInput)
Computes a numerical score measuring the association between the given input vector and its most strongly associated class (as predicted by the classifier).
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScore(TInput)
Computes a numerical score measuring the association between the given input vector and its most strongly associated class (as predicted by the classifier).
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScore(TInput, Int32)
Computes a numerical score measuring the association between the given input vector and a given classIndex.
(Inherited from BaseKNearestNeighborsTModel, TInput, TDistance.)
Public methodScore(TInput, Int32)
Predicts a class label for the input vector, returning a numerical score measuring the strength of association of the input vector to its most strongly related class.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScore(TInput, Double)
Computes a numerical score measuring the association between the given input vector and its most strongly associated class (as predicted by the classifier).
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScore(TInput, Int32)
Computes a numerical score measuring the association between the given input vector and a given classIndex.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScore(TInput, Int32)
Computes a numerical score measuring the association between the given input vector and a given classIndex.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScore(TInput, Int32)
Predicts a class label for each input vector, returning a numerical score measuring the strength of association of the input vector to the most strongly related class.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScore(TInput, Int32, Double)
Computes a numerical score measuring the association between the given input vector and a given classIndex.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScore(TInput, Int32, Double)
Computes a numerical score measuring the association between the given input vector and a given classIndex.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScore(TInput, Int32, Double)
Predicts a class label for each input vector, returning a numerical score measuring the strength of association of the input vector to the most strongly related class.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScores(TInput)
Computes a numerical score measuring the association between the given input vector and each class.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScores(TInput)
Computes a numerical score measuring the association between the given input vector and each class.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScores(Double, Double)
Computes a numerical score measuring the association between the given input vector and each class.
(Overrides MulticlassScoreClassifierBaseTInputScores(TInput, Double).)
Public methodScores(TInput, Int32)
Predicts a class label vector for the given input vector, returning a numerical score measuring the strength of association of the input vector to each of the possible classes.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScores(TInput, Double)
Computes a numerical score measuring the association between the given input vector and each class.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScores(TInput, Int32)
Predicts a class label vector for each input vector, returning a numerical score measuring the strength of association of the input vector to each of the possible classes.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScores(TInput, Int32, Double)
Predicts a class label vector for the given input vector, returning a numerical score measuring the strength of association of the input vector to each of the possible classes.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodScores(TInput, Int32, Double)
Predicts a class label vector for each input vector, returning a numerical score measuring the strength of association of the input vector to each of the possible classes.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodToMulticlass
Views this instance as a multi-class generative classifier.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodToMultilabel
Views this instance as a multi-label distance classifier, giving access to more advanced methods, such as the prediction of one-hot vectors.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Public methodTransform(TInput)
Applies the transformation to an input, producing an associated output.
(Inherited from ClassifierBaseTInput, TClasses.)
Public methodTransform(TInput)
Applies the transformation to a set of input vectors, producing an associated set of output vectors.
(Inherited from TransformBaseTInput, TOutput.)
Public methodTransform(TInput, TClasses)
Applies the transformation to an input, producing an associated output.
(Inherited from ClassifierBaseTInput, TClasses.)
Public methodTransform(TInput, Boolean)
Applies the transformation to an input, producing an associated output.
(Inherited from MulticlassClassifierBaseTInput.)
Public methodTransform(TInput, Int32)
Applies the transformation to an input, producing an associated output.
(Inherited from MulticlassClassifierBaseTInput.)
Public methodTransform(TInput, Boolean)
Applies the transformation to an input, producing an associated output.
(Inherited from MulticlassClassifierBaseTInput.)
Public methodTransform(TInput, Double)
Applies the transformation to an input, producing an associated output.
(Inherited from MulticlassClassifierBaseTInput.)
Public methodTransform(TInput, Int32)
Applies the transformation to an input, producing an associated output.
(Inherited from MulticlassClassifierBaseTInput.)
Public methodTransform(TInput, Double)
Applies the transformation to an input, producing an associated output.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Public methodTransform(TInput, Double)
Applies the transformation to an input, producing an associated output.
(Inherited from MulticlassScoreClassifierBaseTInput.)
Top
Extension Methods
  NameDescription
Public Extension MethodHasMethod
Checks whether an object implements a method with the given name.
(Defined by ExtensionMethods.)
Public Extension MethodIsEqual
Compares two objects for equality, performing an elementwise comparison if the elements are vectors or matrices.
(Defined by Matrix.)
Public Extension MethodTo(Type)Overloaded.
Converts an object into another type, irrespective of whether the conversion can be done at compile time or not. This can be used to convert generic types to numeric types during runtime.
(Defined by ExtensionMethods.)
Public Extension MethodToTOverloaded.
Converts an object into another type, irrespective of whether the conversion can be done at compile time or not. This can be used to convert generic types to numeric types during runtime.
(Defined by ExtensionMethods.)
Top
Remarks

The k-nearest neighbor algorithm (k-NN) is a method for classifying objects based on closest training examples in the feature space. It is amongst the simplest of all machine learning algorithms: an object is classified 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).

If k = 1, then the object is simply assigned to the class of its nearest neighbor.

References:

  • Wikipedia contributors. "K-nearest neighbor algorithm." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 10 Oct. 2012. Web. 9 Nov. 2012. http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

Examples

The first example shows how to create and use a k-Nearest Neighbor algorithm to classify a set of numeric vectors in a multi-class decision problem involving 3 classes. It also shows how to compute class decisions for a new sample and how to measure the performance of a classifier.

// Create some sample learning data. In this data,
// the first two instances belong to a class, the
// four next belong to another class and the last
// three to yet another.

double[][] inputs =
{
    // The first two are from class 0
    new double[] { -5, -2, -1 },
    new double[] { -5, -5, -6 },

    // The next four are from class 1
    new double[] {  2,  1,  1 },
    new double[] {  1,  1,  2 },
    new double[] {  1,  2,  2 },
    new double[] {  3,  1,  2 },

    // The last three are from class 2
    new double[] { 11,  5,  4 },
    new double[] { 15,  5,  6 },
    new double[] { 10,  5,  6 },
};

int[] outputs =
{
    0, 0,        // First two from class 0
    1, 1, 1, 1,  // Next four from class 1
    2, 2, 2      // Last three from class 2
};


// Now we will create the K-Nearest Neighbors algorithm. For this
// example, we will be choosing k = 4. This means that, for a given
// instance, its nearest 4 neighbors will be used to cast a decision.
var knn = new KNearestNeighbors(k: 4);

// We learn the algorithm:
knn.Learn(inputs, outputs);

// After the algorithm has been created, we can classify a new instance:
int answer = knn.Decide(new double[] { 11, 5, 4 }); // answer will be 2.

// Let's say we would like to compute the error matrix for the classifier:
var cm = GeneralConfusionMatrix.Estimate(knn, inputs, outputs);

// We can use it to estimate measures such as 
double error = cm.Error;  // should be 
double acc = cm.Accuracy; // should be 
double kappa = cm.Kappa;  // should be
// After we have created and learned our model, let's say we would 
// like to save it to disk. For this, we can import the Accord.IO 
// namespace at the top of our source file namespace, and then use 
// Serializer's extension method Save:

// Save to a file called "knn.bin" in the basePath directory:
knn.Save(Path.Combine(basePath, "knn.bin"));

// To load it back from the disk, we might need to use the Serializer class directly:
var loaded_knn = Serializer.Load<KNearestNeighbors>(Path.Combine(basePath, "knn.bin"));

// At this point, knn and loaded_knn should be 
// two different instances of identical objects.

The second example show how to use a different distance metric when computing k-NN:

// Create some sample learning data. In this data,
// the first two instances belong to a class, the
// four next belong to another class and the last
// three to yet another.

double[][] inputs =
{
    // The first two are from class 0
    new double[] { -5, -2, -1 },
    new double[] { -5, -5, -6 },

    // The next four are from class 1
    new double[] {  2,  1,  1 },
    new double[] {  1,  1,  2 },
    new double[] {  1,  2,  2 },
    new double[] {  3,  1,  2 },

    // The last three are from class 2
    new double[] { 11,  5,  4 },
    new double[] { 15,  5,  6 },
    new double[] { 10,  5,  6 },
};

int[] outputs =
{
    0, 0,        // First two from class 0
    1, 1, 1, 1,  // Next four from class 1
    2, 2, 2      // Last three from class 2
};


// Now we will create the K-Nearest Neighbors algorithm. For this
// example, we will be choosing k = 4. This means that, for a given
// instance, its nearest 4 neighbors will be used to cast a decision.
var knn = new KNearestNeighbors<double[]>(k: 4, distance: new SquareEuclidean());

// We learn the algorithm:
knn.Learn(inputs, outputs);

// After the algorithm has been created, we can classify a new instance:
int answer = knn.Decide(new double[] { 11, 5, 4 }); // answer will be 2.

// Let's say we would like to compute the error matrix for the classifier:
var cm = GeneralConfusionMatrix.Estimate(knn, inputs, outputs);

// We can use it to estimate measures such as 
double error = cm.Error;  // should be 0
double acc = cm.Accuracy; // should be 1
double kappa = cm.Kappa;  // should be 1

The k-Nearest neighbor algorithm implementation in the framework can also be used with any instance data type. For such cases, the framework offers a generic version of the classifier. The third example shows how to use the generic kNN classifier to perform the direct classification of actual text samples:

// The k-Nearest Neighbors algorithm can be used with
// any kind of data. In this example, we will see how
// it can be used to compare, for example, Strings.

string[] inputs =
{
    "Car",     // class 0
    "Bar",     // class 0
    "Jar",     // class 0

    "Charm",   // class 1
    "Chair"    // class 1
};

int[] outputs =
{
    0, 0, 0,  // First three are from class 0
    1, 1,     // And next two are from class 1
};


// Now we will create the K-Nearest Neighbors algorithm. For this
// example, we will be choosing k = 1. This means that, for a given
// instance, only its nearest neighbor will be used to cast a new
// decision. 

// In order to compare strings, we will be using Levenshtein's string distance
var knn = new KNearestNeighbors<string>(k: 1, distance: new Levenshtein());

// We learn the algorithm:
knn.Learn(inputs, outputs);

// After the algorithm has been created, we can use it:
int answer = knn.Decide("Chars"); // answer should be 1.

// Let's say we would like to compute the error matrix for the classifier:
var cm = ConfusionMatrix.Estimate(knn, inputs, outputs);

// We can use it to estimate measures such as 
double error = cm.Error;  // should be 0
double acc = cm.Accuracy; // should be 1
double kappa = cm.Kappa;  // should be 1
See Also