Необхідна умова: K найближчий сусіди 
 

вступ

Скажімо, нам надано набір даних елементів, кожен з яких має числові значення характеристик (наприклад, Зріст Вага Вік тощо). Якщо кількість функцій є п ми можемо представити елементи як точки в an п -розмірна сітка. Маючи новий предмет, ми можемо обчислити відстань від предмета до кожного іншого предмета в наборі. Ми вибираємо k найближчі сусіди, і ми бачимо, де більшість із цих сусідів класифіковано. Ми класифікуємо новий елемент там.
Отже, проблема стає як ми можемо обчислити відстані між предметами. Рішення цього залежить від набору даних. Якщо значення дійсні, ми зазвичай використовуємо евклідову відстань. Якщо значення категоричні або двійкові, ми зазвичай використовуємо відстань Хеммінга.
Алгоритм:  
 

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

Читання даних

android.process.acore постійно зупиняється

Нехай наш вхідний файл має такий формат:
 

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") і розділимо вхідні дані на рядки:
 

топології

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 кількість найближчих сусідів.
Якщо k більше, ніж довжина набору даних, ми не продовжуємо класифікацію, оскільки ми не можемо мати більше найближчих сусідів, ніж загальна кількість елементів у наборі даних. (як альтернатива ми могли б встановити k як елементи довжина замість повернення повідомлення про помилку)
 

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

Ми хочемо обчислити відстань між елементом, який потрібно класифікувати, та всіма елементами в навчальному наборі, зрештою зберігаючи k найкоротші відстані. Щоб зберегти поточних найближчих сусідів, ми використовуємо список під назвою сусіди . Кожен найменший елемент містить два значення, одне для відстані від об’єкта, що класифікується, а інше для класу, до якого належить сусід. Ми розрахуємо відстань за допомогою узагальненої формули Евкліда (для п розміри). Потім ми виберемо клас, який з’являється найчастіше сусіди і це буде наш вибір. У коді: 
 

виділений html

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

Зовнішні функції, які нам потрібно реалізувати, є Евклідова відстань Оновити сусідів Обчислити клас сусідів і 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); 

Оновлення сусідів

У нас є список наших сусідів (довжина якого не повинна перевищувати k ), і ми хочемо додати елемент до списку на заданій відстані. Спочатку ми перевіримо, чи сусіди мають довжину k . Якщо він менше, ми додаємо предмет до нього незалежно від відстані (оскільки нам потрібно заповнити список до k перш ніж ми почнемо відхиляти товари). Якщо ні, ми перевіримо, чи має елемент меншу відстань, ніж елемент із максимальною відстанню у списку. Якщо це правда, ми замінимо елемент із максимальною відстанню на новий.
Щоб швидше знайти максимальну відстань, список буде відсортований у порядку зростання. Отже, останній елемент у списку матиме максимальну відстань. Ми замінимо його новим товаром і знову відсортуємо.
Щоб пришвидшити цей процес, ми можемо реалізувати сортування вставленням, за допомогою якого ми вставляємо нові елементи в список без необхідності сортувати весь список. Код для цього, однак, досить довгий і хоча простий, завадить підручнику. 
 

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; 

Обчислити клас сусідів

Тут ми розрахуємо клас, який найчастіше зустрічається в сусіди . Для цього ми будемо використовувати інший словник під назвою розраховувати де ключі - це імена класів, які з'являються в сусіди . Якщо ключ не існує, ми додамо його, інакше ми збільшимо його значення. 
 

на java

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

Ми введемо в цю функцію словник розраховувати ми вбудовуємо Обчислити клас сусідів і ми повернемо його макс.
 

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 як вважаєте за потрібне. Зазвичай для k використовується непарне число, але це не обов’язково. Щоб класифікувати новий елемент, вам потрібно створити словник із ключами назв ознак і значень, які характеризують елемент. Приклад класифікації:
 

різниця між лисицею та вовком

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, але вона не пов’язана з алгоритмом, оскільки вона існує для обчислення точності алгоритму.