--- /dev/null
+#!/usr/bin/env python
+
+"""
+This module provides code for doing k-nearest-neighbors classification.
+
+k Nearest Neighbors is a supervised learning algorithm that classifies
+a new observation based the classes in its surrounding neighborhood.
+
+Glossary:
+distance The distance between two points in the feature space.
+weight The importance given to each point for classification.
+
+
+Classes:
+kNN Holds information for a nearest neighbors classifier.
+
+
+Functions:
+train Train a new kNN classifier.
+calculate Calculate the probabilities of each class, given an observation.
+classify Classify an observation into a class.
+
+ Weighting Functions:
+equal_weight Every example is given a weight of 1.
+
+"""
+
+#TODO - Remove this work around once we drop python 2.3 support
+try:
+ set = set
+except NameError:
+ from sets import Set as set
+
+import numpy
+
+class kNN:
+ """Holds information necessary to do nearest neighbors classification.
+
+ Members:
+ classes Set of the possible classes.
+ xs List of the neighbors.
+ ys List of the classes that the neighbors belong to.
+ k Number of neighbors to look at.
+
+ """
+ def __init__(self):
+ """kNN()"""
+ self.classes = set()
+ self.xs = []
+ self.ys = []
+ self.k = None
+
+def equal_weight(x, y):
+ """equal_weight(x, y) -> 1"""
+ # everything gets 1 vote
+ return 1
+
+def train(xs, ys, k, typecode=None):
+ """train(xs, ys, k) -> kNN
+
+ Train a k nearest neighbors classifier on a training set. xs is a
+ list of observations and ys is a list of the class assignments.
+ Thus, xs and ys should contain the same number of elements. k is
+ the number of neighbors that should be examined when doing the
+ classification.
+
+ """
+ knn = kNN()
+ knn.classes = set(ys)
+ knn.xs = numpy.asarray(xs, typecode)
+ knn.ys = ys
+ knn.k = k
+ return knn
+
+def calculate(knn, x, weight_fn=equal_weight, distance_fn=None):
+ """calculate(knn, x[, weight_fn][, distance_fn]) -> weight dict
+
+ Calculate the probability for each class. knn is a kNN object. x
+ is the observed data. weight_fn is an optional function that
+ takes x and a training example, and returns a weight. distance_fn
+ is an optional function that takes two points and returns the
+ distance between them. If distance_fn is None (the default), the
+ Euclidean distance is used. Returns a dictionary of the class to
+ the weight given to the class.
+
+ """
+ x = numpy.asarray(x)
+
+ order = [] # list of (distance, index)
+ if distance_fn:
+ for i in range(len(knn.xs)):
+ dist = distance_fn(x, knn.xs[i])
+ order.append((dist, i))
+ else:
+ # Default: Use a fast implementation of the Euclidean distance
+ temp = numpy.zeros(len(x))
+ # Predefining temp allows reuse of this array, making this
+ # function about twice as fast.
+ for i in range(len(knn.xs)):
+ temp[:] = x - knn.xs[i]
+ dist = numpy.sqrt(numpy.dot(temp,temp))
+ order.append((dist, i))
+ order.sort()
+
+ # first 'k' are the ones I want.
+ weights = {} # class -> number of votes
+ for k in knn.classes:
+ weights[k] = 0.0
+ for dist, i in order[:knn.k]:
+ klass = knn.ys[i]
+ weights[klass] = weights[klass] + weight_fn(x, knn.xs[i])
+
+ return weights
+
+def classify(knn, x, weight_fn=equal_weight, distance_fn=None):
+ """classify(knn, x[, weight_fn][, distance_fn]) -> class
+
+ Classify an observation into a class. If not specified, weight_fn will
+ give all neighbors equal weight. distance_fn is an optional function
+ that takes two points and returns the distance between them. If
+ distance_fn is None (the default), the Euclidean distance is used.
+ """
+ weights = calculate(
+ knn, x, weight_fn=weight_fn, distance_fn=distance_fn)
+
+ most_class = None
+ most_weight = None
+ for klass, weight in weights.items():
+ if most_class is None or weight > most_weight:
+ most_class = klass
+ most_weight = weight
+ return most_class
git://source.jalview.org / jabaws.git / blobdiff