Priekšnosacījums: K tuvākais kaimiņiem 
 

Ievads

Pieņemsim, ka mums ir dota datu kopa ar vienumiem, kuriem katram ir skaitliski novērtētas pazīmes (piemēram, augums, svars, vecums utt.). Ja pazīmju skaits ir n mēs varam attēlot vienumus kā punktus an n - dimensiju režģis. Piešķirot jaunu preci, mēs varam aprēķināt attālumu no preces līdz visām pārējām komplekta vienībām. Mēs izvēlamies k tuvākie kaimiņi un mēs redzam, kur lielākā daļa no šiem kaimiņiem ir klasificēti. Mēs tur klasificējam jauno vienumu.
Tātad problēma kļūst kā mēs varam aprēķināt attālumus starp priekšmetiem. Risinājums ir atkarīgs no datu kopas. Ja vērtības ir reālas, mēs parasti izmantojam Eiklīda attālumu. Ja vērtības ir kategoriskas vai bināras, mēs parasti izmantojam Haminga attālumu.
Algoritms:  
 

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

Datu lasīšana

Ļaujiet mūsu ievades failam būt šādā formātā:
 

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

Katrs vienums ir rinda, un sadaļā “Klase” mēs redzam, kur vienums ir klasificēts. Vērtības zem objektu nosaukumiem (“Augstums” utt.) ir vērtība, kas vienumam ir šim objektam. Visas vērtības un funkcijas ir atdalītas ar komatiem.
Ievietojiet šos datu failus darba direktorijā dati2 un datus . Izvēlieties vienu un ielīmējiet saturu tādu, kāds tas ir, teksta failā ar nosaukumu datus .
Mēs lasīsim no faila (ar nosaukumu "data.txt") un sadalīsim ievadi pa rindām:
 

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

Faila pirmajā rindā ir objektu nosaukumi ar atslēgvārdu "Klase" beigās. Mēs vēlamies saglabāt objektu nosaukumus sarakstā:
 

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

Tad mēs pārejam pie pašas datu kopas. Mēs saglabāsim vienumus sarakstā ar nosaukumu preces kuru elementi ir vārdnīcas (katram vienumam viena). Šo vienumu vārdnīcu atslēgas ir objektu nosaukumi un 'Klase', lai saglabātu vienumu klasi. Beigās mēs vēlamies sajaukt vienumus sarakstā (tas ir drošības pasākums, ja preces atrodas dīvainā secībā). 
 

saistītais saraksts java

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

Datu klasificēšana

Ar datiem, kas tiek glabāti preces tagad sākam veidot savu klasifikatoru. Klasifikatoram izveidosim jaunu funkciju Klasificēt . Kā ievade tiks izmantots vienums, kuru vēlamies klasificēt preču sarakstā un k tuvāko kaimiņu skaits.
Ja k ir lielāks par datu kopas garumu, mēs neturpinām klasificēšanu, jo mums nevar būt vairāk tuvāko kaimiņu par kopējo vienumu skaitu datu kopā. (alternatīvi mēs varētu iestatīt k kā preces garums, nevis jāatgriež kļūdas ziņojums)
 

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

Mēs vēlamies aprēķināt attālumu starp klasificējamo priekšmetu un visiem mācību komplekta priekšmetiem, beigās saglabājot k īsākos attālumus. Lai saglabātu pašreizējos tuvākos kaimiņus, mēs izmantojam sarakstu ar nosaukumu kaimiņiem . Katram elementam vismazākajā daļā ir divas vērtības, viena attālumam no klasificējamās vienības un otra klasei, kurā atrodas kaimiņš. Mēs aprēķināsim attālumu, izmantojot vispārinātu Eiklīda formulu (par n izmēri). Pēc tam mēs izvēlēsimies klasi, kurā parādās lielāko daļu laika kaimiņiem un tā būs mūsu izvēle. Kodā: 
 

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

Ārējās funkcijas, kas mums jāīsteno, ir Eiklīda attālums Atjaunināt kaimiņus AprēķinātKaimiņu klase un FindMax .
 

Eiklīda attāluma atrašana

css fons

Vispārinātā Eiklīda formula diviem vektoriem x un y ir šāda: 

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

Kodā: 

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

Kaimiņu atjaunināšana

Mums ir mūsu kaimiņu saraksts (tam vajadzētu būt ne vairāk kā garam k ) un mēs vēlamies sarakstam pievienot vienumu ar noteiktu attālumu. Vispirms pārbaudīsim, vai kaimiņiem ir garums k . Ja tajā ir mazāk, mēs pievienojam preci neatkarīgi no attāluma (jo mums ir jāaizpilda saraksts līdz k pirms sākam noraidīt vienumus). Ja nē, mēs pārbaudīsim, vai precei ir mazāks attālums nekā precei ar maksimālo attālumu sarakstā. Ja tā ir taisnība, mēs aizstāsim preci ar maksimālo attālumu ar jauno preci.
Lai ātrāk atrastu maksimālā attāluma vienību, saraksts tiks sakārtots augošā secībā. Tātad pēdējam saraksta vienumam būs maksimālais attālums. Mēs to aizstāsim ar jaunu preci un šķirosim vēlreiz.
Lai paātrinātu šo procesu, mēs varam ieviest ievietošanas kārtošanu, kurā mēs ievietojam jaunus vienumus sarakstā, nekārtojot visu sarakstu. Lai gan šis kods ir diezgan garš, un, lai gan tas ir vienkāršs, apmācība tiks pārtraukta. 
 

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; 

AprēķinātKaimiņu klase

Šeit mēs aprēķināsim klasi, kurā visbiežāk parādās kaimiņiem . Šim nolūkam mēs izmantosim citu vārdnīcu ar nosaukumu skaitīt kur atslēgas ir klašu nosaukumi, kas parādās kaimiņiem . Ja atslēga neeksistē, mēs to pievienosim, pretējā gadījumā palielināsim tās vērtību. 
 

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

concat java virkne

Šai funkcijai mēs ievadīsim vārdnīcu skaitīt mēs iebūvējam AprēķinātKaimiņu klase un mēs atgriezīsim tā 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; 

Secinājums

Ar to šī kNN apmācība ir pabeigta.
Tagad varat klasificēt jaunu vienumu iestatījumu k kā uzskatāt par pareizu. Parasti k tiek izmantots nepāra skaitlis, bet tas nav nepieciešams. Lai klasificētu jaunu vienumu, ir jāizveido vārdnīca ar taustiņiem, objektu nosaukumiem un vērtībām, kas raksturo vienumu. Klasifikācijas piemērs:
 

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

Pilns iepriekš minētās pieejas kods ir norādīts zemāk: - 
 

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

Izvade: 

0.9375

Izvade var atšķirties atkarībā no mašīnas. Kods ietver Fold Validation funkciju, taču tā nav saistīta ar algoritmu, kas ir paredzēts algoritma precizitātes aprēķināšanai.