Predpogoj: K najbližje sosedje 
 

Uvod

Recimo, da imamo nabor podatkov elementov, od katerih ima vsak številčno ovrednotene značilnosti (kot je višina, teža, starost itd.). Če je število funkcij n postavke lahko predstavimo kot točke v an n -dimenzijska mreža. Glede na nov predmet lahko izračunamo razdaljo od predmeta do vsakega drugega predmeta v nizu. Izberemo k najbližje sosede in vidimo, kam je razvrščena večina teh sosedov. Tja razvrstimo novo postavko.
Tako nastane problem kako lahko izračunamo razdalje med predmeti. Rešitev tega je odvisna od nabora podatkov. Če so vrednosti realne, običajno uporabimo evklidsko razdaljo. Če so vrednosti kategorične ali binarne, običajno uporabimo Hammingovo razdaljo.
Algoritem:  
 

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

testiranje programske opreme

Branje podatkov

Naj bo naša vhodna datoteka v naslednji obliki:
 

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

Vsaka postavka je vrstica in pod 'Razred' vidimo, kam je postavka razvrščena. Vrednosti pod imeni funkcij ('Višina' itd.) so vrednosti, ki jih ima postavka za to funkcijo. Vse vrednosti in funkcije so ločene z vejicami.
Te podatkovne datoteke postavite v delovni imenik podatki2 in podatke . Izberite enega in prilepite vsebino takšno, kot je, v besedilno datoteko z imenom podatke .
Brali bomo iz datoteke (imenovane 'data.txt') in vnos razdelili po vrsticah:
 

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

Prva vrstica datoteke vsebuje imena funkcij s ključno besedo 'Razred' na koncu. Imena funkcij želimo shraniti na seznam:
 

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

Nato preidemo na sam nabor podatkov. Elemente bomo shranili na seznam z imenom predmete katerega elementi so slovarji (eden za vsako postavko). Ključi teh slovarjev predmetov so imena funkcij in 'Razred' za shranjevanje razreda elementov. Na koncu želimo elemente na seznamu premešati (to je varnostni ukrep, če so elementi v čudnem vrstnem redu). 
 

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

Razvrščanje podatkov

S podatki, shranjenimi v predmete zdaj začnemo graditi naš klasifikator. Za klasifikator bomo ustvarili novo funkcijo Razvrsti . Za vnos bo vzel element, ki ga želimo razvrstiti na seznam predmetov in k število najbližjih sosedov.
če k je večja od dolžine nabora podatkov, ne nadaljujemo z razvrščanjem, saj ne moremo imeti več najbližjih sosedov, kot je skupno število postavk v naboru podatkov. (alternativno bi lahko nastavili k kot predmete dolžina namesto vrnitve sporočila o napaki)
 

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

Izračunati želimo razdaljo med elementom, ki ga je treba razvrstiti, in vsemi predmeti v nizu za usposabljanje, na koncu pa ohraniti k najkrajše razdalje. Za ohranitev trenutnih najbližjih sosedov uporabljamo seznam, imenovan sosedje . Vsak element ima vsaj dve vrednosti, eno za razdaljo od predmeta, ki ga je treba razvrstiti, in drugo za razred, v katerem je sosed. Razdaljo bomo izračunali s posplošeno evklidsko formulo (za n dimenzije). Nato bomo izbrali razred, ki se pojavi večino časa sosedje in to bo naš izbor. V kodi: 
 

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

Zunanje funkcije, ki jih moramo izvajati, so Evklidska razdalja Posodobite sosede Izračunaj razred sosedov in FindMax .
 

Iskanje evklidske razdalje

programi python

Posplošena evklidska formula za dva vektorja x in y je naslednja: 

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

V kodi: 

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

Posodabljanje sosedov

Imamo seznam sosedov (ki bi moral imeti dolžino največ k ) in želimo dodati element na seznam z dano razdaljo. Najprej bomo preverili, ali sosedje imajo dolžino k . Če ima manj, mu dodamo predmet ne glede na razdaljo (saj moramo izpolniti seznam do k preden začnemo zavračati predmete). Če ne, bomo preverili, ali ima element krajšo razdaljo od predmeta z največjo razdaljo na seznamu. Če je to res, bomo element z največjo razdaljo zamenjali z novim elementom.
Da bi hitreje našli element največje razdalje, bomo seznam ohranili razvrščen v naraščajočem vrstnem redu. Tako bo zadnji element na seznamu imel največjo razdaljo. Zamenjali ga bomo z novim artiklom in ga ponovno razvrstili.
Za pospešitev tega postopka lahko implementiramo razvrščanje z vstavljanjem, kjer vstavimo nove elemente na seznam, ne da bi morali razvrstiti celoten seznam. Koda za to je sicer precej dolga in čeprav preprosta bo ovirala vadnico. 
 

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 razred sosedov

Tukaj bomo izračunali razred, ki se najpogosteje pojavlja v sosedje . Za to bomo uporabili drug slovar, imenovan štetje kjer so ključi imena razredov, ki se pojavljajo v sosedje . Če ključ ne obstaja, ga bomo dodali, sicer bomo njegovo vrednost povečali. 
 

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

chmod 755

V to funkcijo bomo vnesli slovar štetje vgradimo Izračunaj razred sosedov in vrnili mu bomo 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ček

S tem je ta vadnica kNN končana.
Zdaj lahko razvrstite nove nastavitve elementov k kot se vam zdi primerno. Običajno se za k uporablja liho število, vendar to ni potrebno. Za razvrstitev novega elementa morate ustvariti slovar s ključi imen funkcij in vrednosti, ki označujejo element. Primer razvrstitve:
 

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

Celotna koda zgornjega pristopa je podana spodaj: - 
 

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

Izhod: 

0.9375

Rezultat se lahko razlikuje od stroja do stroja. Koda vključuje funkcijo Fold Validation, vendar ni povezana z algoritmom, ki ga uporablja za izračun natančnosti algoritma.