Предуслов: К најближи комшије 
 

Увод

Рецимо да нам је дат скуп података ставки од којих свака има нумерички вредноване карактеристике (као што је висина и тежина старости итд.). Ако је број карактеристика н можемо представити ставке као тачке у н -димензионална мрежа. С обзиром на нову ставку можемо израчунати растојање од ставке до сваке друге ставке у скупу. Ми бирамо к најближи суседи и видимо где је већина ових суседа класификована. Ту класификујемо нову ставку.
Дакле, проблем постаје како можемо израчунати растојања између предмета. Решење за ово зависи од скупа података. Ако су вредности реалне, обично користимо Еуклидско растојање. Ако су вредности категоричке или бинарне, обично користимо Хемингову дистанцу.
алгоритам:  
 

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

Читање података

Нека наша улазна датотека буде у следећем формату:
 

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

Свака ставка је линија и под 'Класа' видимо где је ставка класификована. Вредности испод назива обележја ('Висина' итд.) су вредност коју ставка има за то обележје. Све вредности и карактеристике су одвојене зарезима.
Поставите ове датотеке са подацима у радни директоријум дата2 и података . Изаберите један и налепите садржај какав јесте у текстуалну датотеку под називом података .
Читаћемо из датотеке (назване 'дата.ткт') и поделићемо унос по редовима:
 

f = open('data.txt' '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 now 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]}; # 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); 

Класификација података

Са подацима ускладиштеним у ставке сада почињемо да градимо наш класификатор. За класификатор ћемо креирати нову функцију Класификујте . Као улаз ће узети ставку коју желимо да класификујемо на листи ставки и к број најближих суседа.
Ако к је већа од дужине скупа података, не настављамо са класификацијом јер не можемо имати више најближих суседа од укупног броја ставки у скупу података. (Алтернативно, могли бисмо поставити к као ставке дужина уместо враћања поруке о грешци)
 

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

Желимо да израчунамо растојање између ставке коју треба класификовати и свих ставки у сету за обуку на крају задржавајући к најкраће удаљености. Да бисмо задржали тренутне најближе суседе користимо листу тзв комшије . Сваки најмањи елемент има две вредности, једну за растојање од ставке коју треба класификовати, а другу за класу у којој се сусед налази. Израчунаћемо растојање преко генерализоване Еуклидове формуле (за н димензије). Затим ћемо изабрати класу која се појављује већину времена комшије и то ће бити наш избор. у коду: 
 

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

Спољне функције које треба да применимо су ЕуцлидеанДистанце УпдатеНеигхбоурс ЦалцулатеНеигхборсЦласс и ФиндМак .
 

Проналажење Еуклидске удаљености

схелл сорт

Генерализована Еуклидова формула за два вектора к и и је следећа: 

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

у коду: 

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

ЦалцулатеНеигхборсЦласс

Овде ћемо израчунати класу која се најчешће појављује у комшије . За то ћемо користити још један речник под називом цоунт где су кључеви имена класа која се појављују у комшије . Ако кључ не постоји, додаћемо га, иначе ћемо повећати његову вредност. 
 

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

Закључак

Тиме је овај кНН туторијал завршен.
Сада можете класификовати поставке нових ставки к како ти одговара. Обично се за к користи непаран број, али то није неопходно. Да бисте класификовали нову ставку, потребно је да направите речник са кључевима, називима карактеристика и вредностима које карактеришу ставку. Пример класификације:
 

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

Комплетан код горњег приступа је дат у наставку: - 
 

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

Излаз: 

0.9375

Излаз може да варира од машине до машине. Код укључује функцију Фолд Валидатион, али није повезан са алгоритмом који је ту за израчунавање тачности алгоритма.