Алгоритм K-ближайших соседей в Python и Scikit-Learn

Алгоритм K-ближайших соседей (KNN) - это тип контролируемых алгоритмов машинного обучения. KNN [https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm] чрезвычайно легко реализовать в его самой простой форме, но при этом выполняет довольно сложные задачи классификации. Это алгоритм ленивого обучения, поскольку он не имеет специальной фазы обучения. Скорее, он использует все данные для обучения при классификации новой точки данных или экземпляра. KNN - это непараметрический алгоритм обучения, что означает

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

В этой статье мы увидим, как KNN можно реализовать с помощью библиотеки Python Scikit-Learn. Но перед этим давайте сначала исследуем теорию, лежащую в основе KNN, и посмотрим, каковы некоторые из плюсов и минусов этого алгоритма.

Теория

Интуиция, лежащая в основе алгоритма KNN, является одним из самых простых из всех алгоритмов контролируемого машинного обучения. Он просто вычисляет расстояние от новой точки данных до всех других точек данных обучения. Расстояние может быть любого типа, например, евклидова или манхэттенского и т. Д. Затем выбираются K-ближайшие точки данных, где K может быть любым целым числом. Наконец, он присваивает точку данных классу, к которому принадлежит большинство K точек данных.

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

Datapointучасток{.ezlazyload .img-responsive}

Ваша задача - отнести новую точку данных с 'X' к классу «синий» или «красный». Значения координат точки данных: x = 45 и y = 50. Предположим, значение K равно 3. Алгоритм KNN начинается с вычисления расстояния точки X от всех точек. Затем он находит 3 ближайшие точки с наименьшим расстоянием до точки X. Это показано на рисунке ниже. Обведены три ближайшие точки.

График Datapoint обведенкружком{.ezlazyload .img-responsive}

Последним шагом алгоритма KNN является присвоение новой точки классу, которому принадлежит большинство из трех ближайших точек. Из рисунка выше видно, что две из трех ближайших точек относятся к классу «Красный», а одна - к классу «Синий». Поэтому новая точка данных будет классифицирована как «красная».

Плюсы и минусы KNN

В этом разделе мы представим некоторые плюсы и минусы использования алгоритма KNN.

Плюсы

  1. Реализовать очень просто
  2. Как было сказано ранее, это алгоритм ленивого обучения , поэтому он не требует обучения перед тем, как делать прогнозы в реальном времени. Это делает алгоритм KNN намного быстрее, чем другие алгоритмы, требующие обучения, например SVM, линейная регрессия и т. Д.
  3. Поскольку алгоритм не требует обучения перед выполнением прогнозов, новые данные можно добавлять без проблем.
  4. Для реализации KNN требуются только два параметра, то есть значение K и функция расстояния (например, евклидова или манхэттенская и т. Д.)

Минусы

  1. Алгоритм KNN плохо работает с данными большого размера, потому что при большом количестве измерений алгоритму становится сложно вычислять расстояние в каждом измерении.
  2. Алгоритм KNN имеет высокую стоимость прогнозирования для больших наборов данных. Это связано с тем, что в больших наборах данных стоимость вычисления расстояния между новой точкой и каждой существующей точкой становится выше.
  3. Наконец, алгоритм KNN плохо работает с категориальными признаками, поскольку трудно найти расстояние между измерениями с категориальными признаками.

Реализация алгоритма KNN с помощью Scikit-Learn

В этом разделе мы увидим, как библиотеку Python Scikit-Learn можно использовать для реализации алгоритма KNN менее чем в 20 строках кода. Инструкции по загрузке и установке библиотеки Scikit learn доступны здесь .

Примечание . Код, представленный в этом руководстве, был выполнен и протестирован с помощью записной книжки Python Jupyter.

Набор данных

Мы собираемся использовать известный набор данных радужной оболочки глаза для нашего примера KNN. Набор данных состоит из четырех атрибутов: ширина чашелистика, длина чашелистика, ширина лепестка и длина лепестка. Это атрибуты конкретных видов ириса. Задача - предсказать, к какому классу принадлежат эти растения. В наборе данных три класса: Iris-setosa, Iris-versicolor и Iris-virginica. Более подробная информация о наборе данных доступна здесь .

Импорт библиотек

 import numpy as np 
 import matplotlib.pyplot as plt 
 import pandas as pd 

Импорт набора данных

Чтобы импортировать набор данных и загрузить его в наш фреймворк pandas, выполните следующий код:

 url = "https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data" 
 
 # Assign colum names to the dataset 
 names = ['sepal-length', 'sepal-width', 'petal-length', 'petal-width', 'Class'] 
 
 # Read dataset to pandas dataframe 
 dataset = pd.read_csv(url, names=names) 

Чтобы увидеть, как на самом деле выглядит набор данных, выполните следующую команду:

 dataset.head() 

Выполнение вышеуказанного скрипта отобразит первые пять строк нашего набора данных, как показано ниже:

  длина чашелистика   ширина чашелистика   длина лепестка   ширина лепестка   Класс

0 5.1 3.5 1.4 0,2 Ирис-сетоса 1 4.9 3.0 1.4 0,2 Ирис-сетоса 2 4,7 3,2 1.3 0,2 Ирис-сетоса 3 4.6 3.1 1.5 0,2 Ирис-сетоса 4 5.0 3,6 1.4 0,2 Ирис-сетоса

Предварительная обработка

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

 X = dataset.iloc[:, :-1].values 
 y = dataset.iloc[:, 4].values 

X содержит первые четыре столбца набора данных (т. Е. Атрибуты), а y содержит метки.

Тренировка тестового сплит

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

Чтобы создать тренировочные и тестовые сплиты, выполните следующий скрипт:

 from sklearn.model_selection import train_test_split 
 X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.20) 

Приведенный выше сценарий разбивает набор данных на 80% данных поезда и 20% данных теста. Это означает, что из 150 записей обучающий набор будет содержать 120 записей, а тестовый набор - 30 из этих записей.

Масштабирование функций

Перед тем, как делать какие-либо фактические прогнозы, всегда рекомендуется масштабировать функции, чтобы все они могли быть оценены единообразно. Википедия довольно хорошо объясняет рассуждения:

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

Алгоритм градиентного спуска (который используется в обучении нейронных сетей и других алгоритмах машинного обучения) также быстрее сходится с нормализованными функциями.

Следующий скрипт выполняет масштабирование функций:

 from sklearn.preprocessing import StandardScaler 
 scaler = StandardScaler() 
 scaler.fit(X_train) 
 
 X_train = scaler.transform(X_train) 
 X_test = scaler.transform(X_test) 

Обучение и прогнозы

Тренировать алгоритм KNN и делать с его помощью прогнозы чрезвычайно просто, особенно при использовании Scikit-Learn.

 from sklearn.neighbors import KNeighborsClassifier 
 classifier = KNeighborsClassifier(n_neighbors=5) 
 classifier.fit(X_train, y_train) 

Первый шаг - импортировать класс KNeighborsClassifier из библиотеки sklearn.neighbors Во второй строке этот класс инициализируется одним параметром, то есть n_neigbours . Это в основном значение для K. Не существует идеального значения для K, и оно выбирается после тестирования и оценки, однако для начала наиболее часто используемым значением для алгоритма KNN является 5.

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

 y_pred = classifier.predict(X_test) 

Оценка алгоритма

Для оценки алгоритма наиболее часто используемыми метриками являются матрица неточностей, точность, отзывчивость и оценка f1. Для вычисления этих показателей можно использовать методы confusion_matrix и classification_report sklearn.metrics Взгляните на следующий сценарий:

 from sklearn.metrics import classification_report, confusion_matrix 
 print(confusion_matrix(y_test, y_pred)) 
 print(classification_report(y_test, y_pred)) 

Результат вышеупомянутого скрипта выглядит так:

 [[11 0 0] 
 0 13 0] 
 0 1 6]] 
 precision recall f1-score support 
 
 Iris-setosa 1.00 1.00 1.00 11 
 Iris-versicolor 1.00 1.00 1.00 13 
 Iris-virginica 1.00 1.00 1.00 6 
 
 avg / total 1.00 1.00 1.00 30 

Результаты показывают, что наш алгоритм KNN смог классифицировать все 30 записей в тестовом наборе со 100% точностью, что превосходно. Хотя алгоритм очень хорошо работал с этим набором данных, не ожидайте одинаковых результатов со всеми приложениями. Как отмечалось ранее, KNN не всегда так же хорошо работает с многомерными или категориальными функциями.

Сравнение частоты ошибок со значением K

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

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

В этом разделе мы построим график средней ошибки для предсказанных значений тестового набора для всех значений K от 1 до 40.

Для этого давайте сначала вычислим среднее значение ошибки для всех прогнозируемых значений, где K находится в диапазоне от 1 до 40. Выполните следующий сценарий:

 error = [] 
 
 # Calculating error for K values between 1 and 40 
 for i in range(1, 40): 
 knn = KNeighborsClassifier(n_neighbors=i) 
 knn.fit(X_train, y_train) 
 pred_i = knn.predict(X_test) 
 error.append(np.mean(pred_i != y_test)) 

Вышеупомянутый скрипт выполняет цикл от 1 до 40. На каждой итерации вычисляется средняя ошибка для предсказанных значений тестового набора, и результат добавляется в список error

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

 plt.figure(figsize=(12, 6)) 
 plt.plot(range(1, 40), error, color='red', linestyle='dashed', marker='o', 
 markerfacecolor='blue', markersize=10) 
 plt.title('Error Rate K Value') 
 plt.xlabel('K Value') 
 plt.ylabel('Mean Error') 

Выходной график выглядит так:

Коэффициент ошибок значенияK{.ezlazyload .img-responsive}

Из выходных данных мы видим, что средняя ошибка равна нулю, когда значение K находится между 5 и 18. Я бы посоветовал вам поиграть со значением K, чтобы увидеть, как оно влияет на точность прогнозов.

Ресурсы

Хотите узнать больше о Scikit-Learn и других полезных алгоритмах машинного обучения? Я бы порекомендовал изучить более подробные ресурсы, например онлайн-курс:

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

Заключение

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

Отсюда я бы посоветовал вам реализовать алгоритм KNN для другого набора данных классификации. Измените размер теста и обучения вместе со значением K, чтобы увидеть, как различаются ваши результаты и как вы можете повысить точность своего алгоритма. Здесь вы можете поиграть с хорошей коллекцией наборов классификационных данных.

В каких еще приложениях вы применили алгоритм KNN? Как это сработало для вас? Дайте нам знать об этом в комментариях!

comments powered by Disqus

Содержание