Předpoklad: K nejbližší sousedé 
 

Zavedení

Řekněme, že dostáváme datovou sadu položek, z nichž každá má číselně ohodnocené vlastnosti (jako je výška váha věk atd.). Pokud je počet funkcí n můžeme položky reprezentovat jako body v an n -rozměrná mřížka. Vzhledem k novému předmětu můžeme vypočítat vzdálenost od předmětu ke každému dalšímu předmětu v sadě. Vybíráme k nejbližší sousedy a vidíme, kam je většina těchto sousedů zařazena. Tam zařadíme novou položku.
Takže problém se stává jak můžeme vypočítat vzdálenosti mezi položkami. Řešení závisí na souboru dat. Pokud jsou hodnoty reálné, obvykle používáme euklidovskou vzdálenost. Pokud jsou hodnoty kategorické nebo binární, obvykle používáme Hammingovu vzdálenost.
Algoritmus:  
 

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

Čtení dat

Nechť je náš vstupní soubor v následujícím formátu:
 

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

Každá položka je řádek a pod 'Class' vidíme, kam je daná položka zařazena. Hodnoty pod názvy prvků ('Výška' atd.) jsou hodnoty, které má položka pro daný prvek. Všechny hodnoty a vlastnosti jsou odděleny čárkami.
Umístěte tyto datové soubory do pracovního adresáře údaje2 a data . Vyberte jeden a vložte obsah tak, jak je, do textového souboru s názvem data .
Budeme číst ze souboru (s názvem 'data.txt') a vstup rozdělíme na řádky:
 

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

První řádek souboru obsahuje názvy prvků s klíčovým slovem 'Class' na konci. Chceme uložit názvy funkcí do seznamu:
 

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

Poté přejdeme k samotnému souboru dat. Položky uložíme do seznamu s názvem položky jehož prvky jsou slovníky (jeden pro každou položku). Klíči k těmto slovníkům položek jsou názvy funkcí plus 'Class' pro udržení třídy položek. Nakonec chceme položky v seznamu zamíchat (toto je bezpečnostní opatření v případě, že jsou položky v podivném pořadí). 
 

úplná tabulka pravdivosti sčítačky

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

Klasifikace dat

S daty uloženými do položky nyní začneme vytvářet náš klasifikátor. Pro klasifikátor vytvoříme novou funkci Klasifikovat . Vezme jako vstup položku, kterou chceme klasifikovat v seznamu položek a k počet nejbližších sousedů.
Li k je větší než délka souboru dat, s klasifikací nepokračujeme, protože nemůžeme mít více nejbližších sousedů, než je celkový počet položek v souboru dat. (alternativně bychom mohli nastavit k jako položky délka namísto vracení chybové zprávy)
 

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

Chceme vypočítat vzdálenost mezi klasifikovanou položkou a všemi položkami v tréninkové sadě na konci dodržení k nejkratší vzdálenosti. Pro udržení aktuálních nejbližších sousedů používáme seznam tzv sousedé . Každý prvek má přinejmenším dvě hodnoty, jednu pro vzdálenost od klasifikovaného předmětu a druhou pro třídu, ve které se soused nachází. Vzdálenost vypočítáme pomocí zobecněného euklidovského vzorce (např. n rozměry). Poté vybereme třídu, která se vyskytuje nejčastěji sousedé a to bude naše volba. V kódu: 
 

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

Externí funkce, které musíme implementovat, jsou Euklidovská vzdálenost Aktualizovat sousedy CalculateNeighborsClass a FindMax .
 

Hledání euklidovské vzdálenosti

Zobecněný euklidovský vzorec pro dva vektory x a y je tento: 

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

V kódu: 

knn algoritmus

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

Aktualizace Neighbors

Máme seznam našich sousedů (který by měl mít maximálně délku k ) a chceme přidat položku do seznamu s danou vzdáleností. Nejprve zkontrolujeme, zda sousedé mít délku k . Pokud má méně, přidáme k němu položku bez ohledu na vzdálenost (jelikož potřebujeme naplnit seznam až k než začneme položky odmítat). Pokud ne, zkontrolujeme, zda má položka kratší vzdálenost než položka s maximální vzdáleností v seznamu. Pokud je to pravda, nahradíme položku s maximální vzdáleností novou.
Abychom rychleji našli položku maximální vzdálenosti, budeme udržovat seznam seřazený ve vzestupném pořadí. Takže poslední položka v seznamu bude mít maximální vzdálenost. Nahradíme ji novou položkou a znovu ji roztřídíme.
Pro urychlení tohoto procesu můžeme implementovat řazení vložení, kdy vkládáme nové položky do seznamu, aniž bychom museli třídit celý seznam. Kód pro to je však poměrně dlouhý a i když je jednoduchý, tutoriál zničí. 
 

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

Zde vypočítáme třídu, která se vyskytuje nejčastěji sousedé . K tomu nám poslouží jiný slovník tzv počítat kde klíče jsou názvy tříd, které se objevují sousedé . Pokud klíč neexistuje, přidáme jej, jinak jeho hodnotu zvýšíme. 
 

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

Do této funkce vložíme slovník počítat zabudujeme CalculateNeighborsClass a my vrátíme jeho 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; 

Závěr

Tímto je tento tutoriál kNN dokončen.
Nyní můžete klasifikovat nastavení nových položek k jak uznáte za vhodné. Obvykle se pro k používá liché číslo, ale to není nutné. Chcete-li klasifikovat novou položku, musíte vytvořit slovník s klíči, názvy funkcí a hodnotami, které položku charakterizují. Příklad klasifikace:
 

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

Kompletní kód výše uvedeného přístupu je uveden níže: - 
 

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

výstup: 

0.9375

Výstup se může lišit stroj od stroje. Kód obsahuje funkci Validation Fold, ale nesouvisí s algoritmem, je zde pro výpočet přesnosti algoritmu.