Preduvjet: K najbliži susjedi 
 

Uvod

Recimo da nam je dan skup podataka stavki od kojih svaka ima numerički vrednovane značajke (kao što je Visina Težina Dob itd.). Ako je brojanje značajki n stavke možemo prikazati kao točke u an n -dimenzionalna mreža. S obzirom na novi predmet možemo izračunati udaljenost od predmeta do svakog drugog predmeta u skupu. Mi biramo k najbliži susjedi i vidimo gdje je većina tih susjeda klasificirana. Tamo klasificiramo novu stavku.
Tako nastaje problem kako možemo izračunati udaljenosti između predmeta. Rješenje za to ovisi o skupu podataka. Ako su vrijednosti stvarne, obično koristimo euklidsku udaljenost. Ako su vrijednosti kategoričke ili binarne, obično koristimo Hammingovu udaljenost.
Algoritam:  
 

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

Čitanje podataka

Neka naša ulazna datoteka bude u sljedećem formatu:
 

c# popis

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

Svaka stavka je linija i pod 'Klasom' vidimo gdje je stavka klasificirana. Vrijednosti pod nazivima značajki ('Visina' itd.) su vrijednost koju stavka ima za tu značajku. Sve vrijednosti i značajke odvojene su zarezima.
Smjestite ove podatkovne datoteke u radni direktorij podaci2 i podaci . Odaberite jedan i zalijepite sadržaj kakav jest u tekstualnu datoteku pod nazivom podaci .
Čitat ćemo iz datoteke (pod nazivom 'data.txt') i podijelit ćemo unos po linijama:
 

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

Prvi redak datoteke sadrži nazive značajki s ključnom riječi 'Class' na kraju. Želimo pohraniti nazive značajki na popis:
 

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

Zatim prelazimo na sam skup podataka. Stavke ćemo spremiti na popis pod nazivom stavke čiji su elementi rječnici (po jedan za svaku stavku). Ključevi ovih rječnika stavki su nazivi značajki plus 'Klasa' za držanje klase stavke. Na kraju želimo promiješati stavke na popisu (ovo je sigurnosna mjera u slučaju da su stavke u čudnom redoslijedu). 
 

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

Klasificiranje podataka

S podacima pohranjenim u stavke sada počinjemo graditi naš klasifikator. Za klasifikator ćemo kreirati novu funkciju Klasificirati . Kao ulaz uzet će stavku koju želimo klasificirati na popis stavki i k broj najbližih susjeda.
Ako k veći od duljine skupa podataka, ne nastavljamo s klasifikacijom jer ne možemo imati više najbližih susjeda od ukupne količine stavki u skupu podataka. (alternativno bismo mogli postaviti k kao stavke duljina umjesto vraćanja poruke o pogrešci)
 

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

Želimo izračunati udaljenost između stavke koju treba klasificirati i svih stavki u skupu za obuku na kraju zadržavajući k najkraće udaljenosti. Da zadržimo trenutne najbliže susjede koristimo listu tzv susjedi . Svaki element najmanje ima dvije vrijednosti, jednu za udaljenost od stavke koju treba klasificirati, a drugu za klasu u kojoj se susjed nalazi. Izračunat ćemo udaljenost pomoću generalizirane Euklidove formule (za n dimenzije). Zatim ćemo odabrati razred koji se pojavljuje većinu vremena susjedi i to će biti naš odabir. U kodu: 
 

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

Vanjske funkcije koje trebamo implementirati su Euklidska udaljenost Ažuriraj susjede Izračunaj NeighborsClass i FindMax .
 

Određivanje euklidske udaljenosti

leksikografski poredak

Opća euklidska formula za dva vektora x i y je sljedeća: 

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

U kodu: 

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

Ažuriranje susjeda

Imamo popis naših susjeda (koji bi trebao imati najviše duljinu od k ) i želimo dodati stavku na popis sa zadanom udaljenošću. Prvo ćemo provjeriti je li susjedi imaju duljinu od k . Ako ima manje, dodajemo mu stavku bez obzira na udaljenost (jer moramo popuniti popis do k prije nego počnemo odbijati predmete). Ako nije, provjerit ćemo ima li stavka kraću udaljenost od stavke s maksimalnom udaljenošću na popisu. Ako je to istina, zamijenit ćemo stavku s maksimalnom udaljenošću novom stavkom.
Kako bismo brže pronašli maksimalnu udaljenost, popis ćemo poredati uzlaznim redoslijedom. Tako će posljednja stavka na popisu imati najveću udaljenost. Zamijenit ćemo ga novim artiklom i ponovno ćemo ga sortirati.
Kako bismo ubrzali ovaj proces, možemo implementirati Insertion Sort gdje ubacujemo nove stavke na popis bez potrebe za sortiranjem cijelog popisa. Kôd za ovo je ipak prilično dugačak i iako jednostavan zasmetat će poduku. 
 

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; 

Izračunaj NeighborsClass

Ovdje ćemo izračunati klasu koja se najčešće pojavljuje u susjedi . Za to ćemo koristiti drugi rječnik tzv računati gdje su ključevi imena klasa koja se pojavljuju u susjedi . Ako ključ ne postoji, mi ćemo ga dodati, inače ćemo povećati njegovu vrijednost. 
 

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

string split bash

U ovu funkciju unijet ćemo rječnik računati ugrađujemo Izračunaj NeighborsClass i vratit ćemo mu maks.
 

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; 

Zaključak

Time je ovaj kNN tutorijal završen.
Sada možete klasificirati postavke novih stavki k kako vama odgovara. Obično se za k koristi neparan broj, ali to nije nužno. Da biste klasificirali novu stavku, trebate stvoriti rječnik s ključevima naziva značajki i vrijednostima koje karakteriziraju stavku. Primjer klasifikacije:
 

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

Potpuni kod gornjeg pristupa dan je u nastavku:- 
 

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

Izlaz: 

0.9375

Izlaz može varirati od stroja do stroja. Kod uključuje funkciju Fold Validation, ali nije povezana s algoritmom jer postoji za izračun točnosti algoritma.