Введение

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

Давайте посмотрим на пример ниже, чтобы лучше понять

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

Зачем нам нужен алгоритм K-NN?

Предположим, есть две категории, то есть Категория A и Категория B, и у нас есть новая точка данных x1, поэтому эта точка данных будет принадлежать к какой из этих категорий. Чтобы решить эту проблему, нам понадобится алгоритм K-NN. С помощью K-NN мы можем легко определить категорию или класс конкретного набора данных. Рассмотрим диаграмму ниже:

Как работает K-NN?

Работу K-NN можно объяснить на основе следующего алгоритма:

  • Шаг 1: Выберите число K соседей
  • Шаг 2. Вычислите евклидово расстояние для числа K соседей.
  • Шаг 3: Возьмите K ближайших соседей в соответствии с рассчитанным евклидовым расстоянием.
  • Шаг 4: Среди этих k соседей подсчитайте количество точек данных в каждой категории.
  • Шаг 5: Назначьте новые точки данных той категории, для которой число соседей является максимальным.
  • Шаг 6: Наша модель готова.

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

  • Сначала мы выберем количество соседей, поэтому мы выберем k = 5.
  • Затем мы рассчитаем евклидово расстояние между точками данных. Евклидово расстояние - это расстояние между двумя точками, которое мы уже изучили в геометрии. Его можно рассчитать как:

  • Вычислив евклидово расстояние, мы получили ближайших соседей, таких как три ближайших соседа в категории A и два ближайших соседа в категории B. Рассмотрим изображение ниже:

  • Как мы видим, 3 ближайших соседа относятся к категории A, следовательно, эта новая точка данных должна принадлежать к категории A.

Как выбрать значение K?

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

  • Как вы можете убедиться из приведенного выше изображения, если мы продолжим с K = 3, то мы прогнозируем, что тестовые входные данные принадлежат классу B, а если мы продолжим с K = 7, то мы прогнозируем, что тестовые входные данные принадлежат классу A.
  • Вот как вы можете представить, что значение K сильно влияет на производительность KNN.

Тогда как выбрать оптимальное значение K?

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

Теперь вы получите представление о выборе оптимального значения K путем реализации модели.

Расчет расстояния:

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

Евклидово расстояние: Евклидово расстояние рассчитывается как квадратный корень из суммы квадратов разностей между новой точкой (x) и существующей точкой (y).

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

Расстояние Хэмминга: используется для категориальных переменных. Если значение (x) и значение (y) совпадают, расстояние D будет равно 0. В противном случае D = 1.

Способы выполнения КНН

KNeighborsClassifier (n_neighbors = 5, *, weights = 'uniform', algorithm = 'auto', leaf_size = 30, p = 2, metric = 'minkowski', metric_params = None, n_jobs = None, ** kwargs) < br /> алгоритм: {'auto', 'ball_tree', 'kd_tree', 'brute'}, по умолчанию = 'auto'

Грубая сила

Рассмотрим простой случай с двухмерным графиком. Если мы посмотрим математически, простая интуиция состоит в том, чтобы вычислить евклидово расстояние от точки интереса (класс которой нам нужно определить) до всех точек в обучающей выборке. Затем мы берем класс с большинством баллов. Это называется методом грубой силы.

k-мерное дерево (kd tree)

k-d дерево - это иерархическое двоичное дерево. Когда этот алгоритм используется для k-NN classficaition, он переупорядочивает весь набор данных в бинарной древовидной структуре, чтобы при предоставлении тестовых данных он выдавал результат путем обхода дерева, что занимает меньше времени, чем грубый поиск.

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

<html>
<head>
    <meta charset=utf-8" />
    <title>Ball Tree vs. KD Tree</title>
    <nav>
    <a href="/r/">R</a>
    <a href="/js/">JavaScript</a>
    <a href="/python/">Python</a>
    </nav>
</head>
<body>
    <h1>What is a tree?</h1>
    <ul>
        <li>List item one</li>
        <li>List item two</li>
    </ul>
    <h2>How does a tree look like?</h2>
</body>
</html>

Мяч дерево

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

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

Окончательное результирующее дерево шаров выглядит следующим образом:

Сравнение и сводка

Грубая сила может быть наиболее точным методом из-за учета всех точек данных. Следовательно, ложному кластеру не присваивается никакая точка данных. Для небольших наборов данных метод грубой силы оправдан, однако для увеличения объема данных KD или Ball Tree являются лучшей альтернативой из-за их скорости и эффективности.

Реализация модели KNN

Давайте запустим приложение, импортировав все необходимые пакеты. Затем прочтите файл телекоммуникационных данных с помощью функции read_csv ().

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.ticker import NullFormatter
import pandas as pd
import matplotlib.ticker as ticker
%matplotlib inline
df = pd.read_csv('Telecustomers.csv')
df.head()

Набор данных

Как видите, имеется 12 столбцов, а именно: регион, срок пребывания в должности, возраст, семейное положение, адрес, доход, ed, работа, выход на пенсию, пол, проживание и custcat. У нас есть целевой столбец custcat, который разделяет клиентов на четыре группы:

  • 1- Базовое обслуживание
  • 2- Электронное обслуживание
  • 3- Плюс Сервис
  • 4- Общее обслуживание
X = df.drop(['custcat'], axis = 1)
y = df['custcat']
from sklearn import preprocessing
X = preprocessing.StandardScaler().fit(X).transform(X.astype(float))
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split( X, y, test_size=0.2, random_state=4)
from sklearn.neighbors import KNeighborsClassifier
from sklearn import metrics
#Train Model and Predict
k = 4  
neigh = KNeighborsClassifier(n_neighbors = k).fit(X_train,y_train)
Pred_y = neigh.predict(X_test)
print("Accuracy of model at K=4 is",metrics.accuracy_score(y_test, Pred_y))

  • Мы собираем все независимые характеристики данных в фрейм данных X, а целевое поле - в фрейм данных y. Затем мы обрабатываем данные и нормализуем их.
  • После разделения данных мы берем 0,8% данных для обучения, а остальные - для целей тестирования.
  • Мы импортируем модель классификатора из библиотеки sklearn и подгоняем модель, инициализировав K = 4. Таким образом, мы достигли здесь точности 0,32.

Пришло время улучшить модель и найти оптимальное значение k.

error_rate = []
for i in range(1,40):
 knn = KNeighborsClassifier(n_neighbors=i)
 knn.fit(X_train,y_train)
 pred_i = knn.predict(X_test)
 error_rate.append(np.mean(pred_i != y_test))
plt.figure(figsize=(10,6))
plt.plot(range(1,40),error_rate,color='blue', linestyle='dashed', 
         marker='o',markerfacecolor='red', markersize=10)
plt.title('Error Rate vs. K Value')
plt.xlabel('K')
plt.ylabel('Error Rate')
print("Minimum error:-",min(error_rate),"at K =",error_rate.index(min(error_rate)))

Из графика видно, что наименьшая полученная ошибка составляет 0,59 при K = 37. Далее мы визуализируем график между точностью и значением K.

acc = []
# Will take some time
from sklearn import metrics
for i in range(1,40):
    neigh = KNeighborsClassifier(n_neighbors = i).fit(X_train,y_train)
    yhat = neigh.predict(X_test)
    acc.append(metrics.accuracy_score(y_test, yhat))
    
plt.figure(figsize=(10,6))
plt.plot(range(1,40),acc,color = 'blue',linestyle='dashed', 
         marker='o',markerfacecolor='red', markersize=10)
plt.title('accuracy vs. K Value')
plt.xlabel('K')
plt.ylabel('Accuracy')
print("Maximum accuracy:-",max(acc),"at K =",acc.index(max(acc)))

Теперь вы видите улучшенные результаты. Мы получили точность 0,41 при K = 37. Поскольку мы уже построили график ошибок и получили минимальную ошибку при k = 37, мы получим лучшую эффективность при этом значении K.

Спасибо за чтение, надеюсь, вам понравилось!