Предпоставка: K най-близкият съседи 
 

Въведение

Да кажем, че ни е даден набор от данни от елементи, всеки от които има числено оценени характеристики (като Височина Тегло Възраст и т.н.). Ако броят на характеристиките е п можем да представим елементите като точки в an п - размерна мрежа. При даден нов елемент можем да изчислим разстоянието от елемента до всеки друг елемент в комплекта. Ние избираме к най-близки съседи и виждаме къде са класифицирани повечето от тези съседи. Класифицираме новия елемент там.
Така че проблемът става как можем да изчислим разстоянията между елементите. Решението на това зависи от набора от данни. Ако стойностите са реални, обикновено използваме евклидовото разстояние. Ако стойностите са категорични или двоични, обикновено използваме разстоянието на Хеминг.
Алгоритъм:  
 

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

Четене на данни

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

Всеки елемент е ред и под „Клас“ виждаме къде е класифициран елементът. Стойностите под имената на характеристиките („Височина“ и т.н.) са стойността, която елементът има за тази характеристика. Всички стойности и функции са разделени със запетаи.
Поставете тези файлове с данни в работната директория данни2 и данни . Изберете един и поставете съдържанието както е в текстов файл с име данни .
Ще четем от файла (с име 'data.txt') и ще разделим входа по редове:
 

mysql вмъкване в

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

Класифициране на данните

С данните, съхранени в елементи сега започваме да изграждаме нашия класификатор. За класификатора ще създадем нова функция Класифицирайте . Той ще приеме като вход елемента, който искаме да класифицираме в списъка с елементи и к броя на най-близките съседи.
Ако к е по-голяма от дължината на набора от данни, ние не продължаваме с класифицирането, тъй като не можем да имаме повече най-близки съседи от общото количество елементи в набора от данни. (алтернативно можем да зададем k като елементи дължина вместо връщане на съобщение за грешка)
 

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

Искаме да изчислим разстоянието между елемента, който ще се класифицира, и всички елементи в набора за обучение в крайна сметка, запазвайки к най-къси разстояния. За да запазим текущите най-близки съседи, използваме списък, наречен съседи . Всеки елемент има най-малко две стойности, една за разстоянието от елемента, който ще бъде класифициран, и друга за класа, в който е съседът. Ще изчислим разстоянието чрез обобщената Евклидова формула (за п размери). След това ще изберем класа, който се появява през повечето време съседи и това ще бъде нашият избор. В код: 
 

chmod 755

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

Външните функции, които трябва да внедрим, са Евклидово разстояние Актуализиране на съседите Изчислете NeighborsClass и FindMax .
 

Намиране на евклидово разстояние

Обобщената евклидова формула за два вектора x и y е следната: 

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; 

Изчислете NeighborsClass

Тук ще изчислим класа, който се появява най-често в съседи . За това ще използваме друг речник, наречен брой където ключовете са имената на класовете, които се появяват в съседи . Ако ключът не съществува, ще го добавим, в противен случай ще увеличим стойността му. 
 

как да получите iphone emojis на android

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

Ние ще въведем в тази функция речника брой ние вграждаме Изчислете NeighborsClass и ние ще върнем неговия макс.
 

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; 

Заключение

С това този kNN урок е завършен.
Вече можете да класифицирате настройката за нови елементи к както намериш за добре. Обикновено за k се използва нечетно число, но това не е необходимо. За да класифицирате нов елемент, трябва да създадете речник с ключове за имената на характеристиките и стойностите, които характеризират елемента. Пример за класификация:
 

подравнете изображението с css

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

Резултатът може да варира от машина до машина. Кодът включва функция за Fold Validation, но тя не е свързана с алгоритъма, който е там за изчисляване на точността на алгоритъма.