k_nearest_neighbour.py

Go to the documentation of this file.

## @package face_contour_detector.learing.k_nearest_neighbour
#  Implementation of the k-nearest-neighbour algorithm
#  @author Fabian Wenzelmann

import heapq
import math

## @brief Calculate the euclidean distance of two n-dimensional points.
#
#  The euclidean distance for two points \f$p = (p_1, p_2, \dots, p_n)\f$ and \f$q = (q_1, q_2, \dots, q_n)\f$ is defined as follows: \f$ ED(p, q) = \sqrt{ \sum\limits_{i=1}^n (q_i - p_i)^2 } \f$
def euclidean_distance(p1, p2):
    distance_sum = 0
    for x, y in zip(p1, p2):
        distance_sum += (x - y)**2
    return math.sqrt(distance_sum)

## @brief Find for <i>point</i> it's k nearest neighours in the iterable object <i>points</i>
#  @param point the reference points which near neighbours you want to find
#  @param points iterable object of other points (distance to point is calculated for each point in this "set")
#  @param k defines how many neighbours are found in the result list (if the length of the list is smaller than k a list of <i>points</i> is returned)
#  @param key the distance function is not called on point and a point in points directly. The key function is called on point and the result is passed to the distance function
#  @param key2 similar to key but this function is applied to each point in the points "set". Default is None which means that key is used. The advantage of having to key functions is that we can apply different functions on point and all other points.
#  @param distance a distance function that defines a float distance between two points. The distance function is applied to key(point) and key2(p) where <i>p</i> is a point form <i>points</i>. Default is euclidean_distance
#  @return List with the k nearest neighbours of <i>point</i> in <i>points</i>
#  <i>point</i> is the reference point the distance is calculated form. <i>points</i> is the iterable object with all other points. Calculates a
#  list containing the k-nearest neighbours of <i>point</i> in <i>points</i>. If <code>len(points) < k</code> the list has length
#  <code>len(points)</code>.
def k_nearest_neighbours(point, points, k, key=lambda x: x, key2=None, distance=euclidean_distance):
        if key2 is None:
                key2 = key
        h = []
        for p in points:
                heapq.heappush(h, (distance(key(point), key2(p)), p))
        size = len(h)
        return [ heapq.heappop(h)[1] for i in range(min(k, size)) ]