kNN.py

#!/usr/bin/env python # This code is part of the Biopython distribution and governed by its # license. Please see the LICENSE file that should have been included # as part of this package. """ 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. """ import numpy 00032 class kNN(object): """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. """ 00042 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

Generated by Doxygen 1.6.0 Back to index