Что такое кНН?
k-Nearest Neighbours — один из самых простых алгоритмов машинного обучения. Если быть точным, это алгоритм «классификации». Но из-за общей процедуры его также можно использовать для выбора признаков, обнаружения выбросов (редактирование Уилсона) и вменения отсутствующих значений. Его также называют обучение на основе экземпляров и ленивое обучение, потому что во время обучения оно ничего не делает! В kNN гиперпараметром является «k».
Работа kNN
kNN имеет простой рабочий механизм. Я объясню это в 4 шага. Когда приходит контрольная точка, вот что мы делаем в kNN:
- Зафиксируйте значение k
- Найдите k ближайших соседей по формуле евклидова расстояния (или любому алгоритму поиска расстояния)
- Голосуйте за ярлыки классов
- Прогноз
Позвольте мне проиллюстрировать kNN на простом примере. Предположим, что наш набор данных имеет 3 метки класса (A, B, C). Зафиксируем значение k равным 3, т. е. найдем 3 ближайших соседа. Теперь, когда приходит контрольная точка, мы находим 3 ближайших соседа в нашем наборе данных. Предположим, что наш алгоритм дал нам 3 ближайших соседа как A, A, C. Поскольку контрольная точка должна принадлежать только одному классу, мы должны выбрать только одну из A, A, C. Введем механизм голосования теперь, поскольку А равно 2, а С равно 1. «А» выигрывает игру, и мы назначаем контрольную точку, принадлежащую метке класса «А». Это так просто!
Теперь давайте посмотрим на подробное объяснение с кодом.
Объяснение алгоритма kNN
0. Импортируйте необходимые библиотеки
from sklearn import datasets import pandas as pd import numpy as np import seaborn as sns import random as rnd import csv import random import math import operator %matplotlib inline
Давайте поработаем со знаменитым набором данных Iris. Посмотрите на набор данных Iris, если вы о нем не знаете. Первым шагом является загрузка набора данных, а затем разделение нашего набора данных на обучающие данные и тестовые данные.
1. Загрузите набор данных и разделите набор данных.
Набор данных Iris можно загрузить двумя способами. Один из способов — загрузить его из библиотеки sklearn, а второй — загрузить с локального рабочего стола. Давайте последуем второму подходу.
def loadDataset(filename, split, trainingSet=[] , testSet=[]):
with open(filename, 'r') as csvfile:
lines = csv.reader(csvfile)
dataset = list(lines)
for x in range(len(dataset)-1):
for y in range(4):
dataset[x][y] = float(dataset[x][y])
if random.random() < split:
trainingSet.append(dataset[x])
else:
testSet.append(dataset[x])
loadDataset — это функция загрузки нашего набора данных. Открываем файл в режиме чтения как файл CSV. Поскольку наш набор данных состоит из значений, разделенных запятыми, мы используем считыватель CSV. Мы запускаем цикл и на каждой итерации преобразовываем тип данных и разделяем точку данных на поезд или тест в зависимости от возвращаемого значения случайной функции.
По умолчанию значения в наборе данных читаются как строки. Но значения (длина чашелистика, ширина чашелистика, длина лепестка и ширина лепестка) должны быть плавающего типа. Поэтому мы преобразуем их в плавающий тип.
Теперь нам нужно разделить наш набор данных на 2 части. Мы случайным образом разделяем набор данных и заполняем набор обучающих и тестовых данных.
Давайте вызовем эту функцию.
trainingSet=[]
testSet=[]
split = 0.67
loadDataset('iris.csv', split, trainingSet, testSet)
print('Train set is ', repr(len(trainingSet)))
print('Test set is ' , repr(len(testSet)))
После этого мы видим, что наш набор данных был успешно разделен на обучение и тестирование. Переходим к следующему шагу.
2. Определение расстояния и функции соседей
def euclideanDistance(instance1, instance2, length):
distance = 0
for x in range(length):
distance += pow((instance1[x] - instance2[x]), 2)
return math.sqrt(distance)
def getNeighbors(trainingSet, testInstance, k):
distances = []
length = len(testInstance)-1
for x in range(len(trainingSet)):
dist = euclideanDistance(testInstance, trainingSet[x], length)
distances.append((trainingSet[x], dist))
distances.sort(key=operator.itemgetter(1))
neighbors = []
for x in range(k):
neighbors.append(distances[x][0])
return neighbors
Как я уже говорил ранее, в алгоритме kNN мы измеряем расстояние между двумя точками по принципу Евклида. Именно это делается в функции «euclideanDistance». Если у нас есть 3 измерения, то формула принимает вид √(x2−x1)² + (y2−y1)²+ (z2−z1)² Но в нашем наборе данных у нас есть четыре измерения/столбца (длина чашелистика, ширина чашелистика, лепесток длина и ширина лепестка), поэтому мы добавляем дополнительный член в приведенную выше формулу, а затем возвращаем расстояние. Параметр «длина» — это количество измерений в нашем наборе данных, то есть 4.
В функции getNeighbors, учитывая контрольную точку, все обучающие данные, значение «k», функция должна возвращать k ближайших соседей этой контрольной точки во всем обучающем наборе. Для этого мы запускаем цикл для всего набора обучающих данных и на каждой итерации находим расстояние между контрольной точкой и обучающей точкой. После вычисления всех расстояний мы сортируем расстояния в порядке возрастания, потому что нам нужны только первые «k» ближайших соседей. Возвращаем ближайших соседей.
3. Голосование
def getResponse(neighbors):
classVotes = {}
for x in range(len(neighbors)):
response = neighbors[x][-1]
if response in classVotes:
classVotes[response] += 1
else:
classVotes[response] = 1
sortedVotes = sorted(classVotes.items(), key=operator.itemgetter(1), reverse=True)
return sortedVotes[0][0]
Как и в предыдущем примере, когда у нас было 2 A и 1 C, мы выбрали A в качестве метки класса для контрольной точки. В этой функции мы именно так и делаем. Найдя k ближайших соседей, мы должны проголосовать за метки классов. Это можно легко сделать, заполнив словарь classVotes. После заполнения словаря нам нужно отсортировать словарь, чтобы увидеть, кто победитель! И мы возвращаем победителя!
4. Определение точности нашей модели
Создать модель недостаточно, точность модели должна быть достаточно хорошей. Теперь точность — это (общее количество прогнозов, сделанных нашей моделью, деленное на правильные прогнозы). Проверить точность несложно. Это выглядит следующим образом:
def getAccuracy(testSet, predictions):
correct = 0
for x in range(len(testSet)):
if testSet[x][-1] == predictions[x]:
correct += 1
return (correct/float(len(testSet))) * 100.0
Все наши прогнозы хранятся в списке «прогнозы». Наши правильные прогнозы хранятся в наших тестовых данных. Итак, мы сравниваем предсказанные метки классов с исходными метками классов и, наконец, возвращаем точность.
5. Тестирование нашей модели
Здесь наступает важный шаг — «Проверка нашей модели». Мы тестируем нашу модель на тестовых данных и находим точность нашей модели.
predictions=[]
k = 3
for x in range(len(testSet)):
neighbors = getNeighbors(trainingSet, testSet[x], k)
result = getResponse(neighbors)
predictions.append(result)
print('Predicted is ' + repr(result) + ' Actual is ' + repr(testSet[x][-1]))
accuracy = getAccuracy(testSet, predictions)
print('Accuracy: ' + repr(accuracy) + '%')
Мы выбрали значение «k» равным 3, и для каждой контрольной точки в наборе тестовых данных мы находим ее ближайших соседей и голосуем за них. Мы храним все наши прогнозы в списке «прогнозы». Наконец, мы проверяем точность нашей модели!
Вот и все, мы написали алгоритм kNN с нуля!! Разве это не легко и весело?
Проблемы кНН
До сих пор мы видели, как работает kNN и где его можно использовать, но в чем его проблемы? Короче говоря, у него есть 2 основные проблемы.
Первый — «Большое время вычислений». Поскольку во время поезда он ничего не делает, а во время теста расстояния должны быть вычислены. Вычисление расстояния сильно зависит от количества объектов/размеров/столбцов в наборе данных. Если объектов больше, то вычисление расстояния становится трудоемким.
Второе, «Большой размер модели». Поскольку во время обучения он ничего не делает, в kNN наша модель — это данные. Данные = модель в kNN. Если наши данные огромны. Тогда наша модель тоже огромна, что является проблемой.
Надеюсь, вы получили некоторое представление о kNN. Если вам понравился контент, нажмите кнопку «Хлопать» и,
Свяжись со мной -
LinkedIn : https://linkedin.com/in/bomma-pranay
GitHub : https://github.com/Bomma-Pranay
--- By
Bomma Pranay
A Data Science Enthusiast
