Requisit previ: K més propera veïns 
 

Introducció

Suposem que se'ns dóna un conjunt de dades d'elements amb característiques valorades numèricament (com alçada, pes, edat, etc.). Si el recompte de funcions és n podem representar els elements com a punts en un n -quadrícula dimensional. Donat un element nou, podem calcular la distància entre l'element i tots els altres elements del conjunt. Triem el k els veïns més propers i veiem on es classifiquen la majoria d'aquests veïns. Hi classifiquem el nou element.
Així que el problema esdevé com podem calcular les distàncies entre elements. La solució a això depèn del conjunt de dades. Si els valors són reals normalment fem servir la distància euclidiana. Si els valors són categòrics o binaris normalment fem servir la distància de Hamming.
Algorisme:  
 

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

Lectura de dades

pandes loc

Deixeu que el nostre fitxer d'entrada tingui el format següent:
 

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 element és una línia i a "Classe" veiem on es classifica l'element. Els valors sota els noms de les característiques ('Alçada', etc.) són el valor que té l'element per a aquesta característica. Tots els valors i característiques estan separats per comes.
Col·loqueu aquests fitxers de dades al directori de treball dades 2 i dades . Trieu-ne un i enganxeu el contingut tal com està en un fitxer de text anomenat dades .
Llegirem del fitxer (anomenat 'data.txt') i dividirem l'entrada per línies:
 

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

La primera línia del fitxer conté els noms de les característiques amb la paraula clau "Class" al final. Volem emmagatzemar els noms de les característiques en una llista:
 

# 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];

Després passem al conjunt de dades en si. Desarem els elements en una llista anomenada elements els elements dels quals són diccionaris (un per cada element). Les claus d'aquests diccionaris d'elements són els noms de les característiques més "Classe" per contenir la classe d'elements. Al final volem barrejar els elements de la llista (aquesta és una mesura de seguretat en cas que els articles estiguin en un ordre estrany). 
 

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); 

Classificació de les dades

Amb les dades emmagatzemades a elements ara comencem a construir el nostre classificador. Per al classificador crearem una nova funció Classificar . Prendrà com a entrada l'element que volem classificar la llista d'elements i k el nombre de veïns més propers.
Si k és més gran que la longitud del conjunt de dades, no seguim endavant amb la classificació, ja que no podem tenir més veïns més propers que la quantitat total d'elements del conjunt de dades. (alternativament podríem establir k com a elements longitud en lloc de tornar un missatge d'error)
 

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

Volem calcular la distància entre l'ítem a classificar i tots els ítems del conjunt de formació al final mantenint la k distàncies més curtes. Per mantenir els veïns més propers actuals fem servir una llista anomenada veïns . Cada element com a mínim té dos valors un per a la distància de l'element a classificar i un altre per a la classe en què es troba el veí. Calcularem la distància mitjançant la fórmula euclidiana generalitzada (per n dimensions). Després escollirem la classe que apareix la majoria del temps veïns i aquesta serà la nostra elecció. En codi: 
 

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); 

Les funcions externes que hem d'implementar són Distància Euclidiana Actualitza Veïns Calcula NeighborsClass i FindMax .
 

Trobar la distància euclidiana

comanda linux per a zip

La fórmula euclidiana generalitzada per a dos vectors x i y és aquesta: 

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

En codi: 

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); 

Actualització de Veïns

Tenim la nostra llista de veïns (que com a màxim hauria de tenir una longitud de k ) i volem afegir un element a la llista amb una distància determinada. Primer comprovarem si veïns tenen una longitud de k . Si en té menys, hi afegim l'element independentment de la distància (ja que hem d'omplir la llista fins a k abans de començar a rebutjar articles). En cas contrari, comprovarem si l'article té una distància més curta que l'element amb la distància màxima de la llista. Si això és cert, substituirem l'article amb la distància màxima pel nou.
Per trobar l'element de distància màxima més ràpidament, mantindrem la llista ordenada en ordre ascendent. Així, l'últim element de la llista tindrà la distància màxima. El substituirem per un nou element i el tornarem a ordenar.
Per agilitzar aquest procés podem implementar una ordenació d'inserció on inserim nous elements a la llista sense haver d'ordenar tota la llista. El codi per a això, però, és bastant llarg i, tot i que senzill, entorperà 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; 

Calcula NeighborsClass

Aquí calcularem la classe que apareix amb més freqüència veïns . Per a això utilitzarem un altre diccionari anomenat comptar on les claus són els noms de classe que apareixen veïns . Si no existeix una clau, l'afegirem en cas contrari n'augmentarem el 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; 

FindMax

if i else en bash

Introduirem a aquesta funció el diccionari comptar hi construïm Calcula NeighborsClass i tornarem el seu màxim.
 

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ó

Amb això s'ha acabat aquest tutorial de kNN.
Ara podeu classificar la configuració d'elements nous k com creguis convenient. Normalment per a k s'utilitza un nombre senar, però això no és necessari. Per classificar un ítem nou cal crear un diccionari amb les claus dels noms de les característiques i els valors que caracteritzen l'ítem. Un exemple de classificació:
 

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

El codi complet de l'enfocament anterior es mostra a continuació: - 
 

# 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() 

Sortida: 

0.9375

La sortida pot variar d'una màquina a una altra. El codi inclou una funció de validació de plecs, però no està relacionat amb l'algoritme, hi és per calcular la precisió de l'algorisme.