Voraussetzung: K am nächsten Nachbarn 
 

Einführung

Angenommen, wir erhalten einen Datensatz mit Elementen, die jeweils numerisch bewertete Merkmale aufweisen (wie Größe, Gewicht, Alter usw.). Wenn die Anzahl der Features ist N Wir können die Elemente als Punkte in einem darstellen N -dimensionales Gitter. Bei einem neuen Artikel können wir den Abstand zwischen dem Artikel und jedem anderen Artikel im Set berechnen. Wir wählen das aus k Nächste Nachbarn und wir sehen, wo die meisten dieser Nachbarn klassifiziert sind. Wir klassifizieren das neue Element dort.
Das Problem wird also wie wir die Abstände zwischen Gegenständen berechnen können. Die Lösung hierfür hängt vom Datensatz ab. Wenn die Werte reell sind, verwenden wir normalerweise den euklidischen Abstand. Wenn die Werte kategorial oder binär sind, verwenden wir normalerweise die Hamming-Distanz.
Algorithmus:  
 

Zeichenfolge Java

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

Daten lesen

Unsere Eingabedatei soll das folgende Format haben:
 

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

Jedes Element ist eine Zeile und unter „Klasse“ sehen wir, in welche Kategorie das Element eingeordnet ist. Die Werte unter den Merkmalsnamen („Höhe“ usw.) sind der Wert, den das Element für dieses Merkmal hat. Alle Werte und Merkmale werden durch Kommas getrennt.
Platzieren Sie diese Datendateien im Arbeitsverzeichnis Daten2 Und Daten . Wählen Sie eine aus und fügen Sie den Inhalt unverändert in eine Textdatei mit dem Namen ein Daten .
Wir lesen aus der Datei (mit dem Namen „data.txt“) und teilen die Eingabe nach Zeilen auf:
 

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

Die erste Zeile der Datei enthält die Funktionsnamen mit dem Schlüsselwort „Class“ am Ende. Wir möchten die Feature-Namen in einer Liste speichern:
 

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

Dann gehen wir zum Datensatz selbst über. Wir speichern die Elemente in einer Liste mit dem Namen Artikel deren Elemente Wörterbücher sind (eines für jedes Element). Die Schlüssel zu diesen Artikelwörterbüchern sind die Feature-Namen plus „Klasse“ zur Aufnahme der Artikelklasse. Am Ende wollen wir die Elemente in der Liste mischen (dies ist eine Sicherheitsmaßnahme für den Fall, dass die Elemente in einer seltsamen Reihenfolge sind). 
 

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

Klassifizierung der Daten

Mit den gespeicherten Daten Artikel Wir beginnen nun mit dem Aufbau unseres Klassifikators. Für den Klassifikator erstellen wir eine neue Funktion Klassifizieren . Als Eingabe wird der Artikel verwendet, den wir in der Artikelliste klassifizieren möchten k die Anzahl der nächsten Nachbarn.
Wenn k größer als die Länge des Datensatzes ist, fahren wir mit der Klassifizierung nicht fort, da wir nicht mehr nächste Nachbarn haben können als die Gesamtzahl der Elemente im Datensatz. (Alternativ könnten wir k als festlegen Artikel Länge anstatt eine Fehlermeldung zurückzugeben)
 

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

Wir möchten am Ende den Abstand zwischen dem zu klassifizierenden Element und allen Elementen im Trainingssatz berechnen und dabei das beibehalten k kürzeste Distanzen. Um die aktuell nächsten Nachbarn zu behalten, verwenden wir eine Liste namens Nachbarn . Jedes Element enthält mindestens zwei Werte, einen für die Entfernung vom zu klassifizierenden Element und einen anderen für die Klasse, in der sich der Nachbar befindet. Wir berechnen die Entfernung mithilfe der verallgemeinerten euklidischen Formel (z N Abmessungen). Dann wählen wir die Klasse aus, die am häufigsten vorkommt Nachbarn und das wird unsere Wahl sein. Im 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); 

Die externen Funktionen, die wir implementieren müssen, sind Euklidischer Abstand UpdateNeighbors CalculateNeighborsClass Und FindMax .
 

Finden der euklidischen Distanz

Die verallgemeinerte euklidische Formel für zwei Vektoren x und y lautet: 

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

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

Nachbarn aktualisieren

Wir haben unsere Nachbarnliste (die höchstens eine Länge von haben sollte k ) und wir möchten der Liste ein Element mit einem bestimmten Abstand hinzufügen. Zuerst prüfen wir, ob Nachbarn haben eine Länge von k . Wenn es weniger hat, fügen wir das Element unabhängig von der Entfernung hinzu (da wir die Liste bis zu füllen müssen). k bevor wir mit der Ablehnung von Artikeln beginnen). Wenn nicht, prüfen wir, ob das Element einen kürzeren Abstand hat als das Element mit der maximalen Entfernung in der Liste. Wenn das zutrifft, ersetzen wir den Artikel mit der maximalen Entfernung durch den neuen Artikel.
Um den Eintrag „Maximale Entfernung“ schneller zu finden, wird die Liste in aufsteigender Reihenfolge sortiert. Das letzte Element in der Liste hat also die maximale Entfernung. Wir werden es durch einen neuen Artikel ersetzen und ihn erneut sortieren.
Um diesen Prozess zu beschleunigen, können wir eine Einfügungssortierung implementieren, bei der wir neue Elemente in die Liste einfügen, ohne die gesamte Liste sortieren zu müssen. Der Code dafür ist jedoch ziemlich lang und obwohl er einfach ist, wird er das Tutorial verlangsamen. 
 

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; 

CalculateNeighborsClass

Hier berechnen wir die Klasse, die am häufigsten vorkommt Nachbarn . Dafür verwenden wir ein anderes Wörterbuch namens zählen wobei die Schlüssel die Klassennamen sind, die in erscheinen Nachbarn . Wenn ein Schlüssel nicht existiert, fügen wir ihn hinzu, andernfalls erhöhen wir seinen Wert. 
 

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

Wir werden das Wörterbuch in diese Funktion eingeben zählen wir bauen ein CalculateNeighborsClass und wir geben sein Maximum zurück.
 

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; 

Abschluss

Damit ist dieses kNN-Tutorial abgeschlossen.
Sie können jetzt neue Elemente klassifizieren k wie Sie es für richtig halten. Normalerweise wird für k eine ungerade Zahl verwendet, aber das ist nicht notwendig. Um ein neues Element zu klassifizieren, müssen Sie ein Wörterbuch mit Schlüsseln, Merkmalsnamen und Werten erstellen, die das Element charakterisieren. Ein Beispiel für die Klassifizierung:
 

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

Der vollständige Code des oben genannten Ansatzes ist unten angegeben: 
 

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

Ausgabe: 

0.9375

Die Leistung kann von Maschine zu Maschine variieren. Der Code enthält eine Faltvalidierungsfunktion, die jedoch nichts mit dem Algorithmus zu tun hat, mit dem die Genauigkeit des Algorithmus berechnet wird.