Автор оригинала: Scott Robinson.
Алгоритм K-ближайших соседей (KNN) – это тип алгоритмов контролируемого машинного обучения. KNN чрезвычайно прост в реализации в своей самой базовой форме и все же выполняет довольно сложные задачи классификации. Это ленивый алгоритм обучения, так как он не имеет специальной фазы обучения. Скорее, он использует все данные для обучения при классификации новой точки данных или экземпляра. KNN-это непараметрический алгоритм обучения, который означает, что он ничего не предполагает о базовых данных. Это чрезвычайно полезная функция, поскольку большинство реальных данных на самом деле не следуют никаким теоретическим предположениям, например линейной разделимости, равномерного распределения и т. Д.
В этой статье мы увидим, как KNN может быть реализован с помощью библиотеки Scikit-Learn Python. Но перед этим давайте сначала исследуем теорию, лежащую в основе KNN, и посмотрим, каковы некоторые плюсы и минусы этого алгоритма.
Теория
Интуиция, лежащая в основе алгоритма KNN, является одним из самых простых из всех контролируемых алгоритмов машинного обучения. Он просто вычисляет расстояние от новой точки данных до всех других обучающих точек данных. Расстояние может быть любого типа, например евклидово или манхэттенское и т. Д. Затем он выбирает K-ближайшие точки данных, где K может быть любым целым числом. Наконец, он присваивает точку данных классу, к которому принадлежит большинство из K точек данных.
Рассмотрим этот алгоритм в действии на простом примере. Предположим, у вас есть набор данных с двумя переменными, который при построении графика выглядит так, как показано на следующем рисунке.
Ваша задача состоит в том, чтобы классифицировать новую точку данных с “X” в “Синий” класс или “Красный” класс. Координатными значениями точки данных являются и. Предположим, что значение K равно 3. Алгоритм KNN начинается с вычисления расстояния точки X от всех точек. Затем он находит 3 ближайшие точки с наименьшим расстоянием до точки X. Это показано на рисунке ниже. Три ближайших пункта окружены.
Последний шаг алгоритма KNN состоит в том, чтобы присвоить новую точку классу, к которому принадлежит большинство из трех ближайших точек. Из рисунка выше видно, что две из трех ближайших точек относятся к классу “Красных”, а одна-к классу “Синих”. Поэтому новая точка данных будет классифицирована как “Красная”.
Плюсы и минусы KNN
В этом разделе мы представим некоторые плюсы и минусы использования алгоритма KNN.
Плюсы
- Это чрезвычайно легко реализовать
- Как уже было сказано ранее, это алгоритм ленивого обучения и поэтому не требует обучения перед тем, как делать прогнозы в реальном времени. Это делает алгоритм KNN намного быстрее, чем другие алгоритмы, требующие обучения, например SVM, линейная регрессия и т. Д.
- Поскольку алгоритм не требует обучения перед тем, как делать прогнозы, новые данные могут быть добавлены легко.
- Для реализации KNN требуется только два параметра-значение K и функция расстояния (например, евклидова или манхэттенская и т. Д.)
Аферы
- Алгоритм KNN плохо работает с данными высокой размерности, потому что при большом количестве измерений алгоритму становится трудно вычислить расстояние в каждом измерении.
- Алгоритм KNN имеет высокую стоимость прогнозирования для больших наборов данных. Это связано с тем, что в больших наборах данных стоимость вычисления расстояния между новой точкой и каждой существующей точкой становится выше.
- Наконец, алгоритм KNN плохо работает с категориальными объектами, так как трудно найти расстояние между измерениями с категориальными объектами.
Реализация алгоритма KNN с помощью Scikit-Learn
В этом разделе мы увидим, как библиотека Scikit-Learn Python может быть использована для реализации алгоритма KNN менее чем в 20 строках кода. Инструкции по загрузке и установке библиотеки Scikit learn доступны по адресу here .
Примечание : Код, приведенный в этом руководстве, был выполнен и протестирован с помощью Python Jupyter notebook.
Набор данных
Мы собираемся использовать знаменитый набор данных iris для нашего примера KNN. Набор данных состоит из четырех атрибутов: sepal-width, sepal-length, petal-width и petal-length. Это атрибуты конкретных видов растений ириса. Задача состоит в том, чтобы предсказать класс, к которому принадлежат эти растения. В наборе данных есть три класса: 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 | 0.2 | 3.5 | 1.4 | 5.1 |
| Ирис-сетоза | 1 | 0.2 | 3.0 | 1.4 | 4.9 |
| Ирис-сетоза | 2 | 0.2 | 3.2 | 1.3 | 4.7 |
| Ирис-сетоза | 3 | 0.2 | 3.1 | 1.5 | 4.6 |
| Ирис-сетоза | 4 | 0.2 | 3.6 | 1.4 | 5.0 |
Предварительная обработка
Следующий шаг-разбить наш набор данных на его атрибуты и метки. Для этого используйте следующий код:
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_neighbours . Это в основном значение для К. Идеального значения для K не существует, и оно выбирается после тестирования и оценки, однако для начала 5, по-видимому, является наиболее часто используемым значением для алгоритма KNN.
Последний шаг-сделать прогнозы по нашим тестовым данным. Для этого выполните следующий сценарий:
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 находится между 5 и 18. Я бы посоветовал вам поиграть со значением K, чтобы увидеть, как оно влияет на точность предсказаний.
Ресурсы
Хотите узнать больше о Scikit-Learn и других полезных алгоритмах машинного обучения? Я бы рекомендовал проверить некоторые более подробные ресурсы, например онлайн-курс:
Хотя чтение сообщений в блогах, подобных этому, является отличным началом, большинство людей, как правило, лучше учатся с визуальными эффектами, ресурсами и объяснениями из курсов, подобных приведенным выше.
Вывод
KNN-это простой, но мощный алгоритм классификации. Он не требует обучения для составления прогнозов, что, как правило, является одной из самых сложных частей алгоритма машинного обучения. Алгоритм KNN широко используется для поиска сходства документов и распознавания образов. Он также использовался для разработки рекомендательных систем, а также для уменьшения размерности и предварительной обработки шагов компьютерного зрения, в частности задач распознавания лиц.
Отсюда я бы посоветовал вам реализовать алгоритм KNN для другого набора данных классификации. Варьируйте размер теста и тренировки вместе со значением K, чтобы увидеть, как ваши результаты отличаются и как вы можете повысить точность своего алгоритма. Хорошая коллекция классификационных наборов данных доступна здесь для вас, чтобы играть.
К каким еще приложениям вы применили алгоритм KNN? Как это у тебя получилось? Дайте нам знать в комментариях!