Condition préalable: K le plus proche voisins 
 

qu'est-ce que le haut-parleur

Introduction

Supposons que nous recevions un ensemble de données d'éléments ayant chacun des caractéristiques valorisées numériquement (comme la taille, le poids, l'âge, etc.). Si le nombre de fonctionnalités est n nous pouvons représenter les éléments sous forme de points dans un n -grille dimensionnelle. Étant donné un nouvel élément, nous pouvons calculer la distance entre cet élément et tous les autres éléments de l'ensemble. Nous choisissons le k les voisins les plus proches et nous voyons où sont classés la plupart de ces voisins. Nous y classons le nouvel élément.
Le problème devient donc comment nous pouvons calculer les distances entre les éléments. La solution à ce problème dépend de l’ensemble de données. Si les valeurs sont réelles, nous utilisons généralement la distance euclidienne. Si les valeurs sont catégoriques ou binaires, nous utilisons généralement la distance de Hamming.
Algorithme:  
 

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

Lecture des données

Soit notre fichier d'entrée au format suivant :
 

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

Chaque élément est une ligne et sous « Classe », nous voyons où l'élément est classé. Les valeurs sous les noms de caractéristiques (« Hauteur », etc.) sont la valeur que l'élément a pour cette caractéristique. Toutes les valeurs et caractéristiques sont séparées par des virgules.
Placez ces fichiers de données dans le répertoire de travail données2 et données . Choisissez-en un et collez le contenu tel quel dans un fichier texte nommé données .
Nous lirons le fichier (nommé 'data.txt') et diviserons l'entrée par lignes :
 

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

La première ligne du fichier contient les noms des fonctionnalités avec le mot-clé « Class » à la fin. Nous souhaitons stocker les noms des fonctionnalités dans une liste :
 

parcours de précommande d'un arbre

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

Ensuite, nous passons à l'ensemble de données lui-même. Nous enregistrerons les éléments dans une liste nommée articles dont les éléments sont des dictionnaires (un pour chaque élément). Les clés de ces dictionnaires d'éléments sont les noms des caractéristiques plus « Classe » pour contenir la classe d'éléments. En fin de compte, nous voulons mélanger les éléments de la liste (c'est une mesure de sécurité au cas où les éléments seraient dans un ordre étrange). 
 

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

Classer les données

Avec les données stockées dans articles nous commençons maintenant à construire notre classificateur. Pour le classificateur nous allons créer une nouvelle fonction Classer . Il prendra en entrée l'élément que nous voulons classer dans la liste des éléments et k le nombre des voisins les plus proches.
Si k est supérieur à la longueur de l'ensemble de données, nous ne procédons pas à la classification car nous ne pouvons pas avoir plus de voisins les plus proches que la quantité totale d'éléments dans l'ensemble de données. (alternativement, nous pourrions définir k comme articles longueur au lieu de renvoyer un message d'erreur)
 

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

Nous voulons calculer la distance entre l'élément à classer et tous les éléments de l'ensemble d'apprentissage en gardant finalement la distance k distances les plus courtes. Pour conserver les voisins les plus proches actuels, nous utilisons une liste appelée voisins . Chaque élément contient au moins deux valeurs, une pour la distance de l'élément à classer et une autre pour la classe dans laquelle se trouve le voisin. Nous calculerons la distance via la formule euclidienne généralisée (pour n dimensions). Ensuite nous choisirons la classe qui apparaît le plus souvent dans voisins et ce sera notre choix. En code: 
 

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 fonctions externes que nous devons implémenter sont Distance Euclidienne Mettre à jour les voisins Calculer la classe des voisins et TrouverMax .
 

Trouver la distance euclidienne

La formule euclidienne généralisée pour deux vecteurs x et y est la suivante : 

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

En code: 

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

Mise à jour des voisins

Nous avons notre liste de voisins (qui devrait avoir au maximum une longueur de k ) et nous voulons ajouter un élément à la liste avec une distance donnée. Nous vérifierons d'abord si voisins avoir une longueur de k . S'il en a moins, nous y ajoutons l'élément quelle que soit la distance (car nous devons remplir la liste jusqu'à k avant de commencer à rejeter des articles). Sinon, nous vérifierons si l'élément a une distance plus courte que l'élément avec la distance maximale dans la liste. Si cela est vrai, nous remplacerons l'élément avec la distance maximale par le nouvel élément.
Pour trouver plus rapidement l’élément de distance maximale, nous conserverons la liste triée par ordre croissant. Ainsi, le dernier élément de la liste aura la distance maximale. Nous le remplacerons par un nouvel article et nous le trierons à nouveau.
Pour accélérer ce processus, nous pouvons implémenter un tri par insertion dans lequel nous insérons de nouveaux éléments dans la liste sans avoir à trier la liste entière. Le code pour cela est cependant plutôt long et bien que simple, il enlisera le didacticiel. 
 

dateformat.format java

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; 

Calculer la classe des voisins

pile en DS

Ici, nous calculerons la classe qui apparaît le plus souvent dans voisins . Pour cela nous utiliserons un autre dictionnaire appelé compter où les clés sont les noms de classes apparaissant dans voisins . Si une clé n'existe pas nous l'ajouterons sinon nous incrémenterons sa valeur. 
 

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; 

TrouverMax

Nous entrerons dans cette fonction le dictionnaire compter nous construisons Calculer la classe des voisins et nous rendrons son max.
 

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; 

Conclusion

Avec cela, ce tutoriel kNN est terminé.
Vous pouvez maintenant classer les nouveaux paramètres d'éléments k comme bon vous semble. Habituellement, pour k, un nombre impair est utilisé mais ce n’est pas nécessaire. Pour classer un nouvel élément, vous devez créer un dictionnaire avec pour clés les noms de caractéristiques et les valeurs qui caractérisent l'élément. Un exemple de classement :
 

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

Le code complet de l'approche ci-dessus est donné ci-dessous : - 
 

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

Sortir: 

0.9375

Le rendement peut varier d'une machine à l'autre. Le code inclut une fonction Fold Validation mais elle n'a aucun rapport avec l'algorithme, elle est là pour calculer la précision de l'algorithme.