www.machinelearningmastery.ru

Машинное обучение, нейронные сети, искусственный интеллект
Header decor

Home

Учебник по внедрению k-ближайших соседей в Python с нуля

Дата публикации 2014-09-12

Алгоритм k-Nearest Neighbours (или сокращенно kNN) - это простой алгоритм, который можно понять и реализовать, и мощный инструмент, которым можно воспользоваться.

В этом руководстве вы будете реализовывать алгоритм k-Nearest Neighbors с нуля в Python (2.7). Реализация будет специфической для задач классификации и будет продемонстрирована с использованием задачи классификации цветов ириса.

Это руководство предназначено для вас, если вы программист на Python или программист, который может быстро поднять Python, и вас интересует, как реализовать алгоритм k-Nearest Neighbors с нуля.

Что такое k-Ближайшие соседи

Модель для kNN - это весь набор обучающих данных. Когда для невидимого экземпляра данных требуется прогноз, алгоритм kNN будет искать в наборе обучающих данных для k наиболее похожих экземпляров. Атрибут предсказания наиболее похожих экземпляров суммируется и возвращается как прогноз для невидимого экземпляра.

Мера сходства зависит от типа данных. Для реальных данных можно использовать евклидово расстояние. Другие другие типы данных, такие как категориальные или двоичные данные, расстояние Хемминга могут быть использованы.

В случае проблем регрессии может быть возвращено среднее значение прогнозируемого атрибута. В случае классификации, наиболее распространенный класс может быть возвращен.

Как работает k-Nearest Neighbours

Алгоритм kNN относится к семейству алгоритмов конкурентного обучения и ленивого обучения, основанных на экземплярах.

Алгоритмы на основе экземпляров - это те алгоритмы, которые моделируют проблему, используя экземпляры данных (или строки) для принятия прогнозирующих решений. Алгоритм kNN представляет собой крайнюю форму методов, основанных на экземплярах, поскольку все обучающие наблюдения сохраняются как часть модели.

Это конкурентный алгоритм обучения, потому что он внутренне использует конкуренцию между элементами модели (экземплярами данных) для принятия прогнозирующего решения. Объективная мера сходства между экземплярами данных заставляет каждый экземпляр данных конкурировать «побеждать» или быть максимально похожим на данный невидимый экземпляр данных и вносить свой вклад в прогноз.

Ленивое обучение относится к тому факту, что алгоритм не строит модель до тех пор, пока не потребуется прогноз. Это лениво, потому что это работает только в последнюю секунду. Преимущество этого заключается в том, что включаются только данные, относящиеся к невидимым данным, которые называются локализованной моделью. Недостатком является то, что в вычислительном отношении может быть дорого повторять один и тот же или аналогичный поиск для больших наборов обучающих данных.

Наконец, kNN является мощным, потому что он не предполагает ничего о данных, кроме меры расстояния, которая может быть рассчитана последовательно между любыми двумя экземплярами. Как таковой, он называется непараметрическим или нелинейным, поскольку не принимает функциональной формы.

Получите БЕСПЛАТНУЮ карту алгоритмов Mind

Я создал удобную карту разума из 60+ алгоритмов, организованных по типу.

Загрузите его, распечатайте и используйте.

Скачать бесплатно


Также получите эксклюзивный доступ к алгоритмам машинного обучения по электронной почте мини-курса.

& NBSP;

& NBSP;

Классифицировать цветы, используя измерения

Тестовая задача, которую мы будем использовать в этом уроке - классификация радужной оболочки.

Задача состоит из 150 наблюдений за цветами ириса трех разных видов. Есть 4 измерения данных цветов: длина чашелистика, ширина чашелистика, длина лепестка и ширина лепестка, все в одной единице сантиметров. Предсказанный признак - вид, который является одним из setosa, versicolor или virginica.

Это стандартный набор данных, в котором вид известен во всех случаях. Таким образом, мы можем разделить данные на обучающие и тестовые наборы данных и использовать результаты для оценки реализации нашего алгоритма. Хорошая точность классификации по этой проблеме выше 90%, обычно 96% или лучше.

Сохраните файл в текущем рабочем каталоге с именем файла «iris.data«.

Как реализовать k-Nearest Neighbours в Python

Этот учебник разбит на следующие шаги:

  1. СправитьсяДанные: откройте набор данных из CSV и разбейте его на наборы тестовых / обучающих данных.
  2. сходство: Вычислить расстояние между двумя экземплярами данных.
  3. соседи: Найдите k наиболее похожих экземпляров данных.
  4. отклик: Генерировать ответ из набора экземпляров данных.
  5. точность: Подвести итог точности прогнозов.
  6. Главный: Связать все это вместе.

1. Обработка данных

Первое, что нам нужно сделать, это загрузить наш файл данных. Данные в формате CSV без строки заголовка или каких-либо кавычек. Мы можем открыть файл с помощью функции открытия и прочитать строки данных, используя функцию чтения вCSVмодуль.

Read a CSV File in Python
			Python
			
			
import csv
with open('iris.data', 'rb') as csvfile:
	lines = csv.reader(csvfile)
	for row in lines:
		print ', '.join(row)

Затем нам нужно разделить данные на обучающий набор данных, который kNN может использовать для прогнозирования, и тестовый набор данных, который мы можем использовать для оценки точности модели.

Сначала нам нужно преобразовать цветочные меры, загруженные в виде строк, в числа, с которыми мы можем работать. Далее нам нужно разбить набор данных случайным образом на наборы поездов и данных. Соотношение 67/33 для поезда / теста является стандартным соотношением.

Собрав все воедино, мы можем определить функцию под названиемloadDatasetкоторый загружает CSV с предоставленным именем файла и разбивает его случайным образом на наборы данных для обучения и тестирования, используя предоставленный коэффициент разделения.

Load a dataset and spit into train and test sets in Python
			Python
			
			
import csv
import random
def loadDataset(filename, split, trainingSet=[] , testSet=[]):
	with open(filename, 'rb') 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])

Загрузите CSV-файл набора данных iris flowers в локальный каталог. Мы можем проверить эту функцию с помощью нашего набора данных iris следующим образом:

Test the loadDataset function in Python
			Python
			
			
trainingSet=[]
testSet=[]
loadDataset('iris.data', 0.66, trainingSet, testSet)
print 'Train: ' + repr(len(trainingSet))
print 'Test: ' + repr(len(testSet))

2. Сходство

Для того, чтобы делать прогнозы, нам нужно вычислить сходство между любыми двумя данными экземплярами данных. Это необходимо для того, чтобы мы могли найти k наиболее похожих экземпляров данных в наборе обучающих данных для данного члена набора тестовых данных и, в свою очередь, сделать прогноз.

Учитывая, что все четыре измерения цветов являются числовыми и имеют одинаковые единицы измерения, мы можем напрямую использовать евклидову меру расстояния. Это определяется как квадратный корень из суммы квадратов разностей между двумя массивами чисел (прочитайте это снова несколько раз и дайте ему погрузиться).

Кроме того, мы хотим контролировать, какие поля включить в расчет расстояния. В частности, мы хотим включить только первые 4 атрибута. Один из подходов состоит в том, чтобы ограничить евклидово расстояние фиксированной длиной, игнорируя конечный размер.

Собрав все это вместе, мы можем определитьЕвклидово расстояниефункционировать следующим образом:

Calculate Euclidean distance in Python
			Python
			
			
import math
def euclideanDistance(instance1, instance2, length):
	distance = 0
	for x in range(length):
		distance += pow((instance1[x] - instance2[x]), 2)
	return math.sqrt(distance)

Мы можем проверить эту функцию с некоторыми примерами данных, как показано ниже:

Test the euclideanDistance function in Python
			Python
			
			
data1 = [2, 2, 2, 'a']
data2 = [4, 4, 4, 'b']
distance = euclideanDistance(data1, data2, 3)
print 'Distance: ' + repr(distance)

3. Соседи

Теперь, когда у нас есть мера сходства, мы можем использовать ее, чтобы собрать k наиболее похожих экземпляров для данного невидимого экземпляра.

Это простой процесс вычисления расстояния для всех экземпляров и выбора подмножества с наименьшими значениями расстояния.

НижеgetNeighborsфункция, которая возвращает k наиболее похожих соседей из обучающего набора для данного экземпляра теста (используя уже определенныйЕвклидово расстояниефункция)

Locate most similar neighbours in Python
			Python
			
			
import operator 
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

Мы можем проверить эту функцию следующим образом:

Test the getNeighbors function in Python
			Python
			
			
trainSet = [[2, 2, 2, 'a'], [4, 4, 4, 'b']]
testInstance = [5, 5, 5]
k = 1
neighbors = getNeighbors(trainSet, testInstance, 1)
print(neighbors)

4. Ответ

После того как мы нашли наиболее похожих соседей для тестового экземпляра, следующая задача - разработать прогнозируемый ответ на основе этих соседей.

Мы можем сделать это, позволив каждому соседу проголосовать за свой атрибут класса и принять прогноз большинства.

Ниже представлена ​​функция для получения ответа большинства проголосовавших от ряда соседей. Предполагается, что класс является последним атрибутом для каждого соседа.

Summarize a prediction from neighbours in Python
			Python
			
			
import operator
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.iteritems(), key=operator.itemgetter(1), reverse=True)
	return sortedVotes[0][0]

Мы можем проверить эту функцию с некоторыми соседями по тестированию следующим образом:

Test the getResponse function in Python
			Python
			
			
neighbors = [[1,1,1,'a'], [2,2,2,'a'], [3,3,3,'b']]
response = getResponse(neighbors)
print(response)

Этот подход возвращает один ответ в случае ничьей, но вы можете обрабатывать такие случаи особым образом, например, не возвращая ответа или выбирая непредвзятый случайный ответ.

5. Точность

У нас есть все части алгоритма kNN на месте. Важным остается вопрос о том, как оценить точность прогнозов.

Простой способ оценить точность модели - это вычислить соотношение общих правильных прогнозов из всех сделанных прогнозов, которое называется точностью классификации.

НижеgetAccuracyфункция, которая суммирует итоговые правильные прогнозы и возвращает точность в процентах от правильных классификаций.

Calculate accuracy of predictions in Python
			Python
			
			
def getAccuracy(testSet, predictions):
	correct = 0
	for x in range(len(testSet)):
		if testSet[x][-1] is predictions[x]:
			correct += 1
	return (correct/float(len(testSet))) * 100.0

Мы можем протестировать эту функцию с помощью тестового набора данных и прогнозов следующим образом:

Test the getAccuracy function in Python
			Python
			
			
testSet = [[1,1,1,'a'], [2,2,2,'a'], [3,3,3,'b']]
predictions = ['a', 'a', 'a']
accuracy = getAccuracy(testSet, predictions)
print(accuracy)

6. Главный

Теперь у нас есть все элементы алгоритма, и мы можем связать их вместе с основной функцией.

Ниже приведен полный пример реализации алгоритма kNN с нуля в Python.

Example of kNN implemented from Scratch in Python
			Python
			
			
# Example of kNN implemented from Scratch in Python

import csv
import random
import math
import operator

def loadDataset(filename, split, trainingSet=[] , testSet=[]):
	with open(filename, 'rb') 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])


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

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.iteritems(), key=operator.itemgetter(1), reverse=True)
	return sortedVotes[0][0]

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
	
def main():
	# prepare data
	trainingSet=[]
	testSet=[]
	split = 0.67
	loadDataset('iris.data', split, trainingSet, testSet)
	print 'Train set: ' + repr(len(trainingSet))
	print 'Test set: ' + repr(len(testSet))
	# generate predictions
	predictions=[]
	k = 3
	for x in range(len(testSet)):
		neighbors = getNeighbors(trainingSet, testSet[x], k)
		result = getResponse(neighbors)
		predictions.append(result)
		print('> predicted=' + repr(result) + ', actual=' + repr(testSet[x][-1]))
	accuracy = getAccuracy(testSet, predictions)
	print('Accuracy: ' + repr(accuracy) + '%')
	
main()

Запустив пример, вы увидите результаты каждого прогноза по сравнению с фактическим значением класса в наборе тестов. В конце прогона вы увидите точность модели. В этом случае чуть более 98%.

Example output
			
			
			
...
> predicted='Iris-virginica', actual='Iris-virginica'
> predicted='Iris-virginica', actual='Iris-virginica'
> predicted='Iris-virginica', actual='Iris-virginica'
> predicted='Iris-virginica', actual='Iris-virginica'
> predicted='Iris-virginica', actual='Iris-virginica'
Accuracy: 98.0392156862745%

Идеи для расширений

Этот раздел предлагает вам идеи для расширений, которые вы могли бы применить и исследовать с помощью кода Python, который вы реализовали в рамках этого руководства.

  • регрессия: Вы можете адаптировать реализацию для работы с проблемами регрессии (прогнозирование реального значения атрибута). Суммирование ближайших экземпляров может включать в себя получение среднего значения или медианы прогнозируемого атрибута.
  • нормализация: Когда единицы измерения различаются между атрибутами, атрибуты могут доминировать в их вкладе в измерение расстояния. Для задач такого типа вы должны изменить масштаб всех атрибутов данных в диапазон 0-1 (называемый нормализацией), прежде чем вычислять сходство. Обновите модель для поддержки нормализации данных.
  • Альтернативная мера расстояния: Существует много доступных дистанционных измерений, и вы можете даже разработать собственные дистанционные измерения, если хотите. Реализуйте альтернативную меру расстояния, такую ​​как расстояние Манхэттена или произведение векторной точки.

Есть еще много расширений этого алгоритма, которые вы могли бы изучить Две дополнительные идеи включают поддержку взвешенного по расстоянию вклада для k-наиболее похожих экземпляров в прогнозирование и более совершенные структуры на основе дерева данных для поиска похожих экземпляров.

Ресурс, чтобы узнать больше

В этом разделе будут представлены некоторые ресурсы, которые вы можете использовать, чтобы узнать больше об алгоритме k-Nearest Neighbours с точки зрения теории о том, как и почему он работает, и практических соображений по его реализации в коде.

проблема

Код

В этом разделе приведены ссылки на реализации с открытым исходным кодом kNN в популярных библиотеках машинного обучения. Просмотрите их, если вы планируете внедрить собственную версию метода для оперативного использования.

книги

У вас может быть одна или несколько книг по прикладному машинному обучению. В этом разделе освещаются разделы или главы в общих прикладных книгах по машинному обучению, которые относятся к k-ближайшим соседям.

Учебное пособие

В этом уроке вы узнали о алгоритме k-Nearest Neighbor, его работе и некоторых метафорах, которые можно использовать, чтобы подумать об алгоритме и связать его с другими алгоритмами. Вы реализовали алгоритм kNN в Python с нуля таким образом, чтобы вы понимали каждую строку кода и могли адаптировать реализацию для изучения расширений и для удовлетворения собственных потребностей проекта.

Ниже приведены 5 ключевых уроков из этого урока:

  • k-ближайший сосед: Простой алгоритм для понимания и реализации и мощный непараметрический метод.
  • Метод на основе экземпляров: Моделирование проблемы с использованием экземпляров данных (наблюдений).
  • Конкурентное обучение: Обучающие и прогнозирующие решения принимаются внутренней конкуренцией между элементами модели.
  • Ленивый обученияМодель не строится до тех пор, пока она не понадобится для прогнозирования.
  • Мера сходства: Расчет показателей объективного расстояния между экземплярами данных является ключевой особенностью алгоритма.

Вы внедрили kNN, используя этот учебник? Как же вы идете? Что ты узнал?

Оригинальная статья

Footer decor

© www.machinelearningmastery.ru | Ссылки на оригиналы и авторов сохранены. | map