Predpoklad: K najbližšie susedov 
 

Úvod

Povedzme, že dostaneme súbor údajov položiek, z ktorých každý má číselne hodnotené vlastnosti (ako je výška, hmotnosť, vek atď.). Ak je počet funkcií n položky môžeme reprezentovať ako body v an n -rozmerná mriežka. Vzhľadom na novú položku môžeme vypočítať vzdialenosť od položky ku každej ďalšej položke v súprave. Vyberáme k najbližší susedia a vidíme, kam je zaradená väčšina týchto susedov. Tam zaradíme novú položku.
Takže problém nastáva ako môžeme vypočítať vzdialenosti medzi položkami. Riešenie závisí od súboru údajov. Ak sú hodnoty skutočné, zvyčajne používame euklidovskú vzdialenosť. Ak sú hodnoty kategorické alebo binárne, zvyčajne používame Hammingovu vzdialenosť.
Algoritmus:  
 

súbor json

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

Čítanie údajov

Nech je náš vstupný súbor v nasledujúcom formáte:
 

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 riadok a pod 'Class' vidíme, kde je položka zaradená. Hodnoty pod názvami prvkov ('Výška' atď.) sú hodnoty, ktoré má položka pre daný prvok. Všetky hodnoty a vlastnosti sú oddelené čiarkami.
Umiestnite tieto dátové súbory do pracovného adresára údaje2 a údajov . Vyberte jeden a vložte obsah tak, ako je, do textového súboru s názvom údajov .
Budeme čítať zo súboru (s názvom 'data.txt') a vstup rozdelíme na riadky:
 

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

Prvý riadok súboru obsahuje názvy prvkov s kľúčovým slovom 'Class' na konci. Chceme uložiť názvy funkcií do zoznamu:
 

vložiť mysql do

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

Potom prejdeme k samotnému súboru údajov. Položky uložíme do zoznamu s názvom položky ktorých prvkami sú slovníky (jeden pre každú položku). Kľúčmi k týmto slovníkom položiek sú názvy funkcií plus 'Trieda' na uloženie triedy položiek. Nakoniec chceme položky v zozname zamiešať (ide o bezpečnostné opatrenie v prípade, že sú položky v podivnom poradí). 
 

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

Klasifikácia údajov

S údajmi uloženými v položky teraz začneme zostavovať náš klasifikátor. Pre klasifikátor vytvoríme novú funkciu Klasifikovať . Vezme ako vstup položku, ktorú chceme klasifikovať v zozname položiek a k počet najbližších susedov.
Ak k je väčšia ako dĺžka súboru údajov, nepokračujeme v klasifikácii, pretože nemôžeme mať viac najbližších susedov, ako je celkový počet položiek v súbore údajov. (Alternatívne by sme mohli nastaviť k ako položky dĺžka namiesto vrátenia chybovej správy)
 

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

Chceme vypočítať vzdialenosť medzi položkou, ktorá sa má klasifikovať, a všetkými položkami v tréningovej sade na konci dodržania k najkratšie vzdialenosti. Na udržanie aktuálnych najbližších susedov používame zoznam tzv susedov . Každý prvok má prinajmenšom dve hodnoty, jednu pre vzdialenosť od položky, ktorá sa má klasifikovať, a druhú pre triedu, v ktorej sa sused nachádza. Vzdialenosť vypočítame pomocou zovšeobecneného euklidovského vzorca (napr. n rozmery). Potom vyberieme triedu, ktorá sa v nej vyskytuje najčastejšie susedov a to bude naša voľba. V kóde: 
 

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é funkcie, ktoré musíme implementovať, sú Euklidovská vzdialenosť UpdateNeighbors CalculateNeighborsClass a FindMax .
 

Nájdenie euklidovskej vzdialenosti

Zovšeobecnený euklidovský vzorec pre 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óde: 

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

Aktualizácia susedov

Máme zoznam našich susedov (ktorý by mal mať nanajvýš dĺžku k ) a chceme pridať položku do zoznamu s danou vzdialenosťou. Najprv skontrolujeme, či susedov mať dĺžku k . Ak má menej, pridáme k nej položku bez ohľadu na vzdialenosť (pretože potrebujeme naplniť zoznam až do k predtým, než začneme odmietať položky). Ak nie, skontrolujeme, či má položka kratšiu vzdialenosť ako položka s maximálnou vzdialenosťou v zozname. Ak je to pravda, nahradíme položku s maximálnou vzdialenosťou novou položkou.
Aby sme rýchlejšie našli položku maximálnej vzdialenosti, budeme udržiavať zoznam zoradený vo vzostupnom poradí. Takže posledná položka v zozname bude mať maximálnu vzdialenosť. Nahradíme ho novým tovarom a znova ho roztriedime.
Na urýchlenie tohto procesu môžeme implementovať triedenie vkladania, kde vkladáme nové položky do zoznamu bez toho, aby sme museli triediť celý zoznam. Kód na to je však dosť dlhý a hoci jednoduchý, návod zablokuje. 
 

java pole zoradené

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

Tu vypočítame triedu, ktorá sa najčastejšie vyskytuje susedia . Na to nám poslúži iný slovník tzv počítať kde kľúče sú názvy tried vyskytujúce sa v susedov . Ak kľúč neexistuje, pridáme ho, inak jeho hodnotu zvýšime. 
 

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 tejto funkcie vložíme slovník počítať zabudujeme CalculateNeighborsClass a my jej vrátime 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áver

čísla pre abecedu

Týmto je tento tutoriál kNN dokončený.
Teraz môžete klasifikovať nastavenie nových položiek k ako uznáte za vhodné. Zvyčajne sa pre k používa nepárne číslo, ale to nie je potrebné. Ak chcete klasifikovať novú položku, musíte vytvoriť slovník s kľúčmi, názvami funkcií a hodnotami, ktoré charakterizujú položku. Príklad klasifikácie:
 

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

Úplný kód vyššie uvedeného prístupu je uvedený nižšie: - 
 

# 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 sa môže líšiť od stroja k stroju. Kód obsahuje funkciu Validation Fold, ale nesúvisí s algoritmom, je tu na výpočet presnosti algoritmu.