Requisito previo: K más cercano vecinos 
 

Introducción

Digamos que nos dan un conjunto de datos de elementos, cada uno de los cuales tiene características valoradas numéricamente (como altura, peso, edad, etc.). Si el recuento de características es norte Podemos representar los elementos como puntos en un norte -cuadrícula dimensional. Dado un elemento nuevo, podemos calcular la distancia entre él y todos los demás elementos del conjunto. Escogemos el k vecinos más cercanos y vemos dónde se clasifican la mayoría de estos vecinos. Clasificamos el nuevo elemento allí.
Entonces el problema se vuelve cómo podemos calcular las distancias entre elementos. La solución a esto depende del conjunto de datos. Si los valores son reales solemos utilizar la distancia euclidiana. Si los valores son categóricos o binarios solemos utilizar la distancia de Hamming.
Algoritmo:  
 

Given a new item: 1. Find distances between new item and all other items 2. Pick k shorter distances 3. Pick the most common class in these k distances 4. That class is where we will classify the new item

cómo convertir una cadena a un número entero en java

Lectura de datos

Dejemos que nuestro archivo de entrada tenga el siguiente formato:
 

Height Weight Age Class 1.70 65 20 Programmer 1.90 85 33 Builder 1.78 76 31 Builder 1.73 74 24 Programmer 1.81 75 35 Builder 1.73 70 75 Scientist 1.80 71 63 Scientist 1.75 69 25 Programmer

Cada elemento es una línea y en 'Clase' vemos dónde se clasifica el artículo. Los valores bajo los nombres de las características ('Altura', etc.) son el valor que tiene el artículo para esa característica. Todos los valores y características están separados por comas.
Coloque estos archivos de datos en el directorio de trabajo. datos2 y datos . Elija uno y pegue el contenido tal cual en un archivo de texto llamado datos .
Leeremos del archivo (llamado 'data.txt') y dividiremos la entrada por líneas:
 

f = open('data.txt' 'r'); lines = f.read().splitlines(); f.close();

La primera línea del archivo contiene los nombres de las funciones con la palabra clave "Clase" al final. Queremos almacenar los nombres de las funciones en una lista:
 

# Split the first line by commas # remove the first element and # save the rest into a list. The # list now holds the feature # names of the data set. features = lines[0].split(' ')[:-1];

Luego pasamos al conjunto de datos en sí. Guardaremos los elementos en una lista llamada elementos cuyos elementos son diccionarios (uno para cada ítem). Las claves de estos diccionarios de elementos son los nombres de las funciones más 'Clase' para contener la clase del elemento. Al final queremos mezclar los elementos de la lista (esta es una medida de seguridad en caso de que los elementos estén en un orden extraño). 
 

items = []; for i in range(1 len(lines)): line = lines[i].split(' '); itemFeatures = {'Class' : line[-1]}; # Iterate through the features for j in range(len(features)): # Get the feature at index j f = features[j]; # The first item in the line # is the class skip it v = float(line[j]); # Add feature to dict itemFeatures[f] = v; # Append temp dict to items items.append(itemFeatures); shuffle(items); 

Clasificando los datos

Con los datos almacenados en elementos Ahora comenzamos a construir nuestro clasificador. Para el clasificador crearemos una nueva función. Clasificar . Tomará como entrada el elemento que queremos clasificar en la lista de elementos y k el número de los vecinos más cercanos.
Si k es mayor que la longitud del conjunto de datos, no continuamos con la clasificación ya que no podemos tener más vecinos más cercanos que la cantidad total de elementos en el conjunto de datos. (alternativamente podríamos establecer k como el elementos longitud en lugar de devolver un mensaje de error)
 

if(k > len(Items)): # k is larger than list # length abort return 'k larger than list length';

Queremos calcular la distancia entre el elemento a clasificar y todos los elementos del conjunto de entrenamiento al final manteniendo la k distancias más cortas. Para mantener los vecinos más cercanos actuales utilizamos una lista llamada vecinos . Cada elemento como mínimo tiene dos valores, uno para la distancia desde el elemento a clasificar y otro para la clase en la que se encuentra el vecino. Calcularemos la distancia mediante la fórmula euclidiana generalizada (para norte dimensiones). Luego elegiremos la clase que aparece la mayor parte del tiempo en vecinos y esa será nuestra elección. En código: 
 

def Classify(nItem k Items): if(k > len(Items)): # k is larger than list # length abort return 'k larger than list length'; # Hold nearest neighbors. # First item is distance  # second class neighbors = []; for item in Items: # Find Euclidean Distance distance = EuclideanDistance(nItem item); # Update neighbors either adding # the current item in neighbors  # or not. neighbors = UpdateNeighbors(neighbors item distance k); # Count the number of each # class in neighbors count = CalculateNeighborsClass(neighbors k); # Find the max in count aka the # class with the most appearances. return FindMax(count); 

Las funciones externas que necesitamos implementar son Distancia Euclidiana ActualizarVecinos CalcularVecinosClase y BuscarMax .
 

Encontrar la distancia euclidiana

Linux cambiar el nombre del directorio

La fórmula euclidiana generalizada para dos vectores xey es la siguiente: 

distance = sqrt{(x_{1}-y_{1})^2 + (x_{2}-y_{2})^2 + ... + (x_{n}-y_{n})^2}

En código: 

def EuclideanDistance(x y): # The sum of the squared  # differences of the elements S = 0; for key in x.keys(): S += math.pow(x[key]-y[key] 2); # The square root of the sum return math.sqrt(S); 

Actualizando vecinos

Tenemos nuestra lista de vecinos (que como máximo debería tener una longitud de k ) y queremos agregar un elemento a la lista con una distancia determinada. Primero comprobaremos si vecinos tener una longitud de k . Si tiene menos, le agregamos el elemento independientemente de la distancia (ya que necesitamos llenar la lista hasta k antes de empezar a rechazar artículos). De lo contrario, comprobaremos si el elemento tiene una distancia más corta que el elemento con la distancia máxima en la lista. Si eso es cierto, reemplazaremos el artículo con distancia máxima por el nuevo artículo.
Para encontrar el elemento de distancia máxima más rápidamente, mantendremos la lista ordenada en orden ascendente. Entonces el último elemento de la lista tendrá la distancia máxima. Lo reemplazaremos con un artículo nuevo y lo ordenaremos nuevamente.
Para acelerar este proceso, podemos implementar una ordenación por inserción donde insertamos nuevos elementos en la lista sin tener que ordenar toda la lista. Sin embargo, el código para esto es bastante largo y, aunque simple, atascará el tutorial. 
 

def UpdateNeighbors(neighbors item distance k): if(len(neighbors) > distance): # If yes replace the last # element with new item neighbors[-1] = [distance item['Class']]; neighbors = sorted(neighbors); return neighbors; 

CalcularVecinosClase

Aquí calcularemos la clase que aparece con más frecuencia en vecinos . Para eso usaremos otro diccionario llamado contar donde las claves son los nombres de las clases que aparecen en vecinos . Si una clave no existe, la agregaremos; de lo contrario, incrementaremos su valor. 
 

def CalculateNeighborsClass(neighbors k): count = {}; for i in range(k): if(neighbors[i][1] not in count): # The class at the ith index # is not in the count dict. # Initialize it to 1. count[neighbors[i][1]] = 1; else: # Found another item of class  # c[i]. Increment its counter. count[neighbors[i][1]] += 1; return count; 

BuscarMax

c booleano

Ingresaremos a esta función el diccionario. contar construimos en CalcularVecinosClase y le devolveremos su máximo.
 

def FindMax(countList): # Hold the max maximum = -1; # Hold the classification classification = ''; for key in countList.keys(): if(countList[key] > maximum): maximum = countList[key]; classification = key; return classification maximum; 

Conclusión

Con esto finaliza este tutorial de kNN.
Ahora puedes clasificar la configuración de nuevos elementos k como mejor le parezca. Normalmente para k se utiliza un número impar pero no es necesario. Para clasificar un nuevo elemento, necesita crear un diccionario con claves, los nombres de las características y los valores que caracterizan el elemento. Un ejemplo de clasificación:
 

newItem = {'Height' : 1.74 'Weight' : 67 'Age' : 22}; print Classify(newItem 3 items);

El código completo del enfoque anterior se proporciona a continuación: - 
 

# Python Program to illustrate # KNN algorithm # For pow and sqrt import math from random import shuffle ###_Reading_### def ReadData(fileName): # Read the file splitting by lines f = open(fileName 'r') lines = f.read().splitlines() f.close() # Split the first line by commas  # remove the first element and save # the rest into a list. The list  # holds the feature names of the  # data set. features = lines[0].split(' ')[:-1] items = [] for i in range(1 len(lines)): line = lines[i].split(' ') itemFeatures = {'Class': line[-1]} for j in range(len(features)): # Get the feature at index j f = features[j] # Convert feature value to float v = float(line[j]) # Add feature value to dict itemFeatures[f] = v items.append(itemFeatures) shuffle(items) return items ###_Auxiliary Function_### def EuclideanDistance(x y): # The sum of the squared differences # of the elements S = 0 for key in x.keys(): S += math.pow(x[key] - y[key] 2) # The square root of the sum return math.sqrt(S) def CalculateNeighborsClass(neighbors k): count = {} for i in range(k): if neighbors[i][1] not in count: # The class at the ith index is # not in the count dict.  # Initialize it to 1. count[neighbors[i][1]] = 1 else: # Found another item of class  # c[i]. Increment its counter. count[neighbors[i][1]] += 1 return count def FindMax(Dict): # Find max in dictionary return  # max value and max index maximum = -1 classification = '' for key in Dict.keys(): if Dict[key] > maximum: maximum = Dict[key] classification = key return (classification maximum) ###_Core Functions_### def Classify(nItem k Items): # Hold nearest neighbours. First item # is distance second class neighbors = [] for item in Items: # Find Euclidean Distance distance = EuclideanDistance(nItem item) # Update neighbors either adding the # current item in neighbors or not. neighbors = UpdateNeighbors(neighbors item distance k) # Count the number of each class  # in neighbors count = CalculateNeighborsClass(neighbors k) # Find the max in count aka the # class with the most appearances return FindMax(count) def UpdateNeighbors(neighbors item distance k ): if len(neighbors) < k: # List is not full add  # new item and sort neighbors.append([distance item['Class']]) neighbors = sorted(neighbors) else: # List is full Check if new  # item should be entered if neighbors[-1][0] > distance: # If yes replace the  # last element with new item neighbors[-1] = [distance item['Class']] neighbors = sorted(neighbors) return neighbors ###_Evaluation Functions_### def K_FoldValidation(K k Items): if K > len(Items): return -1 # The number of correct classifications correct = 0 # The total number of classifications total = len(Items) * (K - 1) # The length of a fold l = int(len(Items) / K) for i in range(K): # Split data into training set # and test set trainingSet = Items[i * l:(i + 1) * l] testSet = Items[:i * l] + Items[(i + 1) * l:] for item in testSet: itemClass = item['Class'] itemFeatures = {} # Get feature values for key in item: if key != 'Class': # If key isn't 'Class' add  # it to itemFeatures itemFeatures[key] = item[key] # Categorize item based on # its feature values guess = Classify(itemFeatures k trainingSet)[0] if guess == itemClass: # Guessed correctly correct += 1 accuracy = correct / float(total) return accuracy def Evaluate(K k items iterations): # Run algorithm the number of # iterations pick average accuracy = 0 for i in range(iterations): shuffle(items) accuracy += K_FoldValidation(K k items) print accuracy / float(iterations) ###_Main_### def main(): items = ReadData('data.txt') Evaluate(5 5 items 100) if __name__ == '__main__': main() 

Producción: 

0.9375

La producción puede variar de una máquina a otra. El código incluye una función de validación de plegado, pero no está relacionada con el algoritmo, ya que está ahí para calcular la precisión del algoritmo.