Prerequisito: K più vicino vicinato 
 

Introduzione

Supponiamo che ci venga fornito un set di dati di elementi ciascuno con caratteristiche valutate numericamente (come altezza, peso, età, ecc.). Se il conteggio delle funzionalità è N possiamo rappresentare gli elementi come punti in un N griglia bidimensionale. Dato un nuovo oggetto possiamo calcolare la distanza dall'oggetto a ogni altro oggetto del set. Scegliamo il k vicini più vicini e vediamo dove è classificata la maggior parte di questi vicini. Classifichiamo lì il nuovo elemento.
Quindi il problema diventa come possiamo calcolare le distanze tra gli elementi. La soluzione a questo dipende dal set di dati. Se i valori sono reali solitamente utilizziamo la distanza euclidea. Se i valori sono categorici o binari si usa solitamente la distanza di 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

Lettura dei dati

albero binario

Lascia che il nostro file di input sia nel seguente 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

Ogni elemento è una linea e sotto "Classe" vediamo in che categoria è classificato l'elemento. I valori sotto i nomi delle caratteristiche ("Altezza" ecc.) sono il valore che l'elemento ha per quella caratteristica. Tutti i valori e le caratteristiche sono separati da virgole.
Posiziona questi file di dati nella directory di lavoro dati2 E dati . Scegline uno e incolla il contenuto così com'è in un file di testo denominato dati .
Leggeremo dal file (denominato "data.txt") e divideremo l'input per righe:
 

l'età di salman khan khan

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

La prima riga del file contiene i nomi delle funzionalità con la parola chiave "Classe" alla fine. Vogliamo memorizzare i nomi delle funzionalità in un elenco:
 

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

Passiamo quindi al set di dati stesso. Salveremo gli elementi in un elenco denominato elementi i cui elementi sono dizionari (uno per ogni elemento). Le chiavi di questi dizionari di oggetti sono i nomi delle funzionalità più "Classe" per contenere la classe dell'oggetto. Alla fine vogliamo mischiare gli elementi nell'elenco (questa è una misura di sicurezza nel caso in cui gli elementi siano in un ordine strano). 
 

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

Classificare i dati

Con i dati memorizzati in elementi ora iniziamo a costruire il nostro classificatore. Per il classificatore creeremo una nuova funzione Classificare . Prenderà come input l'elemento che vogliamo classificare nell'elenco degli elementi e k il numero dei vicini più vicini.
Se k è maggiore della lunghezza del set di dati, non procediamo con la classificazione poiché non possiamo avere più vicini più prossimi del numero totale di elementi nel set di dati. (in alternativa potremmo impostare k come elementi lunghezza invece di restituire un messaggio di errore)
 

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

Vogliamo calcolare la distanza tra l'elemento da classificare e tutti gli elementi del set di addestramento mantenendo infine il file k distanze più brevi. Per mantenere gli attuali vicini più vicini utilizziamo un elenco chiamato vicinato . Ogni elemento in meno ha due valori uno per la distanza dall'oggetto da classificare e un altro per la classe in cui si trova il vicino. Calcoleremo la distanza tramite la formula euclidea generalizzata (per N dimensioni). Quindi sceglieremo la classe che appare più spesso in vicinato e quella sarà la nostra scelta. Nel codice: 
 

modelli di programmazione java

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

Le funzioni esterne che dobbiamo implementare sono Distanza euclidea Aggiorna vicini CalcoloClasseVicini E TrovaMax .
 

Trovare la distanza euclidea

La formula euclidea generalizzata per due vettori xey è questa: 

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

Nel codice: 

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

Aggiornamento dei vicini

Abbiamo la lista dei nostri vicini (che dovrebbe avere al massimo una lunghezza di k ) e vogliamo aggiungere un elemento all'elenco con una determinata distanza. Per prima cosa controlleremo se vicinato avere una lunghezza di k . Se ne ha meno, aggiungiamo l'elemento indipendentemente dalla distanza (poiché dobbiamo riempire l'elenco fino a k prima di iniziare a rifiutare gli articoli). In caso contrario, controlleremo se l'articolo ha una distanza inferiore rispetto all'articolo con la distanza massima nell'elenco. Se ciò è vero, sostituiremo l'articolo con la distanza massima con il nuovo articolo.
Per trovare più velocemente la voce Distanza massima manterremo l'elenco ordinato in ordine crescente. Quindi l'ultimo elemento nell'elenco avrà la distanza massima. Lo sostituiremo con un nuovo articolo e lo ordineremo di nuovo.
Per accelerare questo processo possiamo implementare un ordinamento di inserimento in cui inseriamo nuovi elementi nell'elenco senza dover ordinare l'intero elenco. Il codice per questo però è piuttosto lungo e, sebbene semplice, impantanerà il 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; 

CalcoloClasseVicini

Qui calcoleremo la classe che appare più spesso in vicinato . Per questo utilizzeremo un altro dizionario chiamato contare dove le chiavi sono i nomi delle classi che compaiono in vicinato . Se una chiave non esiste la aggiungeremo altrimenti ne incrementeremo il valore. 
 

albero binario vs albero di ricerca binario

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; 

TrovaMax

Inseriremo in questa funzione il dizionario contare costruiamo dentro CalcoloClasseVicini e restituiremo il suo massimo.
 

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; 

Conclusione

Con questo il tutorial su kNN è terminato.
Ora puoi classificare le nuove impostazioni degli elementi k come ritieni opportuno. Di solito per k viene utilizzato un numero dispari ma ciò non è necessario. Per classificare un nuovo oggetto è necessario creare un dizionario con le chiavi i nomi delle caratteristiche e i valori che caratterizzano l'oggetto. Un esempio di classificazione:
 

int raddoppiare

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

Il codice completo dell'approccio di cui sopra è riportato di seguito: - 
 

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

Produzione: 

0.9375

La resa può variare da macchina a macchina. Il codice include una funzione Fold Validation ma non è correlata all'algoritmo, è lì per calcolare l'accuratezza dell'algoritmo.