K-vecinos más cercanos, clasificación basada en distancias.

knn.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Author: Overxfl0w13 #
# KNN para representaciones vectoriales #

def p_distance(v1,v2,p=2): 
	
	""" Calcula las distancias de la familia Lp, http://gyazo.com/b4183c93c58575351334366e3c07370b .
		Se asumen parámetros correctamente introducidos.
	
		Parámetros
		v1 -- vector 1
		v2 -- vector 2
		p  -- indicador de la distancia a emplear según la familia Lp
	
		Excepciones
		...
	"""
	s = 0
	if p!=0:
		for x in xrange(len(v1)): s += (v1[x]-v2[x])**p
		return s**(1.0/p)
	else:
		return max(map(abs,[v1[x]-v2[x] for x in xrange(len(v1))]))

def extract_class(stest,k_neighbours,samples_train,p):
	""" Extrae la clase correcta en función de la maxima cantidad de vecinos a mínima distancia de la muestra de test,
    a igualdad de vecinos mínimos, se calcula por mínima distancia.
    Se asumen parámetros correctamente introducidos.
    
    Parámetros 
    stest 		  -- muestra de test a clasificar
    k_neighbours  -- k vecinos a menor distancia de la muestra stest
    samples_train -- muestras de entrenamiento en caso de que se requiera desempate
    p             -- indicador de la distancia a emplear según la familia Lp
    
    Excepciones
	...
    """ 
	hash_neigh = {}
	for k_neigh in k_neighbours: 
		if k_neigh[0][1] not in hash_neigh: hash_neigh[k_neigh[0][1]] = 1
		else: hash_neigh[k_neigh[0][1]] += 1
	c_max = max(hash_neigh,key=hash_neigh.get)
	# Si hay alguna otra clase con el mismo número de vecinos, desempatar con el vecino de menor distancia entre las clases y la muestra #
	c_equals = [c_max]
	for key in hash_neigh: 
		if hash_neigh[key]==c_max: c_equals.append(key)
	min_distance = float('inf')
	for cls in c_equals:
		for v in samples_train:
			if v[1]==cls:
				dist = p_distance(stest,v[0])
				if dist<min_distance: min_distance,c_max = dist,cls
	return c_max
		
	
def knn(samples_test,samples_train,k,p):
	""" Clasifica las muestras de test en funcion de las muestras de entrenamiento. 
	Se asumen parámetros correctamente introducidos.
	
	Parámetros
	samples_test  -- muestras a clasificar
	samples_train -- prototipos iniciales (muestras de entrenamiento ya clasificadas)
	k             -- nº de vecinos a emplear en el clasificador
	p             -- indicador de la distancia a emplear según la familia Lp
	
	Excepciones
	...
	"""
	for stest in samples_test:
		k_neigh = []
		for strain in samples_train:
			# Si los k-vecinos aun no se han rellenado, llenarlos. #
			if len(k_neigh)<k: k_neigh.append([strain,p_distance(stest,strain[0],p)])
			# Si ya hay k-vecinos seleccionados, mirar si mejora la distancia en comparación al vecino con máxima distancia. #
			else: 
				dist = p_distance(stest,strain[0],p)
				m    = max(k_neigh,key=lambda x: x[1])
				if dist<m[1]: k_neigh[k_neigh.index(m)]=[strain,dist]
		print "Muestra",stest,"clasificada en la clase",extract_class(stest,k_neigh,samples_train,p)	

if __name__ == "__main__":
	knn([(3,1),(5,4)],[((1,2),1),((1,3),1),((2,2),1),((2,3),1),((5,2),2),((5,3),2),((5,4),2),((4,3),2),((4,4),2)],3,2)