K-Nearest Neighbours (или просто KNN) — алгоритм классификации и регрессии, основанный на предположении компактности, который предполагает, что объекты, близкие друг к другу в пространстве признаков, имеют схожие значения целевой переменной или принадлежат к одному классу.

Ноутбук с этими алгоритмами можно скачать с сайта Каггл (англ) и GitHub (Русский).

Как работает КНН

Алгоритм построен следующим образом:

  • 1) сначала рассчитывается расстояние между тестом и всеми обучающими выборками;

  • 2) затем среди них выбираются k ближайших выборок (соседей), причем число k задается заранее;

  • 3) окончательным прогнозом среди k ближайших выбранных выборок будет мода в случае классификации и среднее арифметическое в случае регрессии;

  • 4) Предыдущие шаги повторяются для всех тестируемых образцов.

Как работает КНН

Как работает КНН

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

  • Евклидово расстояние — самая простая и общепринятая метрика, определяемая как длина отрезка между двумя объектами. А И б в космосе с нетхарактеристики и рассчитывается по формуле:

d(a, b) = \sqrt{\sum_{i=1}^n (a_i - b_i)^2}

  • Манхэттенское расстояние — это метрика, определяемая как сумма абсолютных значений разностей координат двух точек пространства между двумя объектами. А И б с нетхарактеристики и рассчитывается по формуле:

d(a, b) = \sum_{i=1}^n |a_i - b_i|

  • Косинусное расстояние — это метрика, определяемая как угол между двумя векторами. А И б в космосе с нет характеристики и рассчитывается по формуле:

d(a, b) = 1 - \frac{\sum_{i=1}^n a_i b_i}{\sqrt{\sum_{i=1}^n a_i^2} \sqrt{\sum_{i=1 }^n b_i^2}}

Более быстрая оптимизация

Описанный выше тип КНС называется Грубая сила, поскольку он использует грубую силу для поиска ближайших соседей, что упрощает реализацию, но слишком медленно при работе с большими объемами данных. Для решения этой проблемы реализация scikit-learn предоставляет более продвинутые методы, основанные на двоичных деревьях, что обеспечивает значительный прирост производительности.

Шаровое дерево

BallTree — это древовидная структура, основанная на разбиении исходного пространства данных на вложенные гиперсферы, что позволяет более эффективно отсекать большие области пространства, в которых нет ближайших соседей для точек. В большинстве случаев этот алгоритм подходит для данных с произвольной метрикой расстояния.

Создание BallTree включает в себя следующие шаги.:

  • 1) из множества точек случайным образом выбирается одна из них и по ней находится самая дальняя точка;

  • 2) тогда все точки разбиваются на сферы (узлы) исходя из ближайшего расположения двух точек из шага 1, а расстояние между двумя сферами А и В в метрике М будет определяться следующим образом:

d_M(A, B) = \max(0, d_M(c_A, c_{B}) - r_A - r_{B}

Или Калифорния И c_{B} являются центрами сфер, а р_АИ р_Б их лучи.

  • 3) затем этот процесс рекурсивно повторяется для каждой сферы до тех пор, пока там не останется определенное количество точек или не будет достигнута заданная глубина дерева.

ЧИТАТЬ   МОК не пригласит Россию на Олимпиаду-2024 в назначенную дату

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

Дерево КД

KD-Tree (k-мерное дерево) — еще одна древовидная структура, отдаленно напоминающая BallTree, но в этом случае для разделения точек вместо гиперсфер используются гиперплоскости, что также эффективно оставляет только те области пространства данных, в которых находятся ближайшие соседи. может присутствовать. . Как правило, KD-Tree лучше всего подходит для данных с евклидовой или манхэттенской метрикой расстояния.

Построение KD-Tree включает в себя следующие шаги.:

  • 1) из набора точек выбирается одна из координат (обычно по одной для каждого уровня дерева, но это можно сделать и случайным образом) и по ней вычисляется медиана;

  • 2) затем все точки разбиваются на два узла (подмножества) по медиане: те, у которых значение выбранной координаты меньше или равно медиане, и те, у которых значение выбранной координаты больше;

  • 3) этот процесс рекурсивно повторяется для каждого узла до тех пор, пока там не останется определенное количество точек или не будет достигнута заданная глубина дерева.

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

Также стоит добавить, что KNN можно использовать в контексте обучения без учителя, например, в задачах кластеризации для расчета расстояний между объектами, например, в алгоритме DBSCAN (подробнее можно прочитать на странице Здесь). В scikit-learn для этого есть специальный класс. Ближайшие соседи.

Импорт необходимых библиотек

import numpy as np
import matplotlib.pyplot as plt
from mlxtend.plotting import plot_decision_regions
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, r2_score
from sklearn.datasets import load_iris, load_diabetes
from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor

Реализация Python с нуля

class KNearestNeighbors:

    def __init__(self, n_neighbors=5, regression=False):
        self.n_neighbors = n_neighbors
        self.regression = regression

    def fit(self, X_train, y_train):
        self.X_train, self.y_train = X_train, y_train

    def _euclidean_distances(self, x_test_i):
        return np.sqrt(np.sum((self.X_train - x_test_i) ** 2, axis=1))

    def _make_prediction(self, x_test_i):
        distances = self._euclidean_distances(x_test_i)   # distances to all neighbors
        k_nearest_indexes = np.argsort(distances)[:self.n_neighbors]
        targets = self.y_train[k_nearest_indexes]   # k-nearest neighbors target values

        return np.mean(targets) if self.regression else np.bincount(targets).argmax()

    def predict(self, X_test):
        return np.array([self._make_prediction(x) for x in X_test])

Код для рисования графика

def decision_boundary_plot(X, y, X_train, y_train, clf, feature_indexes, title=None):
    feature1_name, feature2_name = X.columns[feature_indexes]
    X_feature_columns = X.values[:, feature_indexes]
    X_train_feature_columns = X_train[:, feature_indexes]
    clf.fit(X_train_feature_columns, y_train)

    plot_decision_regions(X=X_feature_columns, y=y.values, clf=clf)
    plt.xlabel(feature1_name)
    plt.ylabel(feature2_name)
    plt.title(title)

Загрузка наборов данных

X1, y1 = load_iris(return_X_y=True, as_frame=True)
X1_train, X1_test, y1_train, y1_test = train_test_split(X1.values, y1.values, random_state=0)
print(X1, y1, sep='\n')


     sepal length (cm)  sepal width (cm)  petal length (cm)  petal width (cm)
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
..                 ...               ...                ...               ...
145                6.7               3.0                5.2               2.3
146                6.3               2.5                5.0               1.9
147                6.5               3.0                5.2               2.0
148                6.2               3.4                5.4               2.3
149                5.9               3.0                5.1               1.8

[150 rows x 4 columns]
0      0
1      0
2      0
3      0
4      0
      ..
145    2
146    2
147    2
148    2
149    2
Name: target, Length: 150, dtype: int64
X2, y2 = load_diabetes(return_X_y=True, as_frame=True)
X2_train, X2_test, y2_train, y2_test = train_test_split(X2.values, y2.values, random_state=0)
print(X2, y2, sep='\n')


          age       sex       bmi        bp        s1        s2        s3  \
0    0.038076  0.050680  0.061696  0.021872 -0.044223 -0.034821 -0.043401   
1   -0.001882 -0.044642 -0.051474 -0.026328 -0.008449 -0.019163  0.074412   
2    0.085299  0.050680  0.044451 -0.005670 -0.045599 -0.034194 -0.032356   
3   -0.089063 -0.044642 -0.011595 -0.036656  0.012191  0.024991 -0.036038   
4    0.005383 -0.044642 -0.036385  0.021872  0.003935  0.015596  0.008142   
..        ...       ...       ...       ...       ...       ...       ...   
437  0.041708  0.050680  0.019662  0.059744 -0.005697 -0.002566 -0.028674   
438 -0.005515  0.050680 -0.015906 -0.067642  0.049341  0.079165 -0.028674   
439  0.041708  0.050680 -0.015906  0.017293 -0.037344 -0.013840 -0.024993   
440 -0.045472 -0.044642  0.039062  0.001215  0.016318  0.015283 -0.028674   
441 -0.045472 -0.044642 -0.073030 -0.081413  0.083740  0.027809  0.173816   

           s4        s5        s6  
0   -0.002592  0.019907 -0.017646  
1   -0.039493 -0.068332 -0.092204  
2   -0.002592  0.002861 -0.025930  
3    0.034309  0.022688 -0.009362  
4   -0.002592 -0.031988 -0.046641  
..        ...       ...       ...  
437 -0.002592  0.031193  0.007207  
438  0.034309 -0.018114  0.044485  
439 -0.011080 -0.046883  0.015491  
440  0.026560  0.044529 -0.025930  
441 -0.039493 -0.004222  0.003064  

[442 rows x 10 columns]
0      151.0
1       75.0
2      141.0
3      206.0
4      135.0
       ...  
437    178.0
438    104.0
439    132.0
440    220.0
441     57.0
Name: target, Length: 442, dtype: float64

Модели обучения и оценка полученных результатов

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

ЧИТАТЬ   Российский дипломат заявил о скором выздоровлении

Однако следует обратить внимание на случай регрессии: низкий показатель r2 по умолчанию обусловлен небольшим количеством ближайших соседей. Если увеличить количество соседей до 30, то показатель r2 увеличится более чем в 2 раза, что указывает на важность выбора оптимального числа ближайших соседей.

классификатор КНН

knn_clf = KNearestNeighbors()
knn_clf.fit(X1_train, y1_train)
knn_clf_pred_res = knn_clf.predict(X1_test)
knn_clf_accuracy = accuracy_score(y1_test, knn_clf_pred_res)

print(f'KNN classifier accuracy: {knn_clf_accuracy:}')
print(knn_clf_pred_res)


KNN classifier accuracy: 0.9736842105263158
[2 1 0 2 0 2 0 1 1 1 2 1 1 1 1 0 1 1 0 0 2 1 0 0 2 0 0 1 1 0 2 1 0 2 2 1 0
 2]

КНН Регрессор

knn_reg = KNearestNeighbors(regression=True)
knn_reg.fit(X2_train, y2_train)
knn_reg_pred_res = knn_reg.predict(X2_test)
knn_reg_r2 = r2_score(y2_test, knn_reg_pred_res)

print(f'KNN regressor R2 score: {knn_reg_r2}')
print(knn_reg_pred_res)


KNN regressor R2 score: 0.18912404854026388
[253.6 188.6 183.2 138.4 177.8 189.6 111.8 229.  178.  266.8 147.6 193.8
 136.4  55.6 297.4  73.6  97.2  83.8 130.8 214.4 173.6 115.2 167.4 101.
 186.8 175.6  97.2  75.  172.4 144.2 205.4  63.8 161.6 190.8 110.2 159.2
 199.4 141.2 121.4 140.8 155.6 173.8 140.6 175.6 134.2  84.6 110.4 127.2
 107.4 209.2 130.2  78.2 183.6 105.  227.4 160.4 155.  104.6 119.2 175.8
 159.8 141.6 150.4 100.2 279.2 128.4  91.2 269.2 183.2  88.4 118.  151.6
  74.8  97.8 126.2 140.4 127.4 223.6 236.6 191.2 111.6 219.8  69.6 169.4
  87.6  92.6 112.  145.8 117.  153.2 115.2  92.8  67.6 172.   92.4 106.6
 208.4 173.8 113.2 104.4 141.6 128.2 226.   87.  247.6 147.6 223.6 217.2
 149.   72.6 182. ]

Классификатор KNN (scikit-learn)

sk_knn_clf = KNeighborsClassifier()
sk_knn_clf.fit(X1_train, y1_train)
sk_knn_clf_pred_res = sk_knn_clf.predict(X1_test)
sk_knn_clf_accuracy = accuracy_score(y1_test, sk_knn_clf_pred_res)

print(f'sk KNN classifier accuracy: {sk_knn_clf_accuracy:}')
print(sk_knn_clf_pred_res)

feature_indexes = [2, 3]
title1 = 'KNeighborsClassifier surface'
decision_boundary_plot(X1, y1, X1_train, y1_train, sk_knn_clf, feature_indexes, title1)


sk KNN classifier accuracy: 0.9736842105263158
[2 1 0 2 0 2 0 1 1 1 2 1 1 1 1 0 1 1 0 0 2 1 0 0 2 0 0 1 1 0 2 1 0 2 2 1 0
 2]
12aee3d8bc6046d6f5db3ac417f20d5d

Регрессор KNN (научное обучение)

sk_knn_reg = KNeighborsRegressor()
sk_knn_reg.fit(X2_train, y2_train)
sk_knn_reg_pred_res = sk_knn_reg.predict(X2_test)
sk_knn_reg_r2 = r2_score(y2_test, sk_knn_reg_pred_res)

print(f'sk KNN regressor R2 score: {sk_knn_reg_r2}')
print(sk_knn_reg_pred_res)


sk KNN regressor R2 score: 0.18912404854026388
[253.6 188.6 183.2 138.4 177.8 189.6 111.8 229.  178.  266.8 147.6 193.8
 136.4  55.6 297.4  73.6  97.2  83.8 130.8 214.4 173.6 115.2 167.4 101.
 186.8 175.6  97.2  75.  172.4 144.2 205.4  63.8 161.6 190.8 110.2 159.2
 199.4 141.2 121.4 140.8 155.6 173.8 140.6 175.6 134.2  84.6 110.4 127.2
 107.4 209.2 130.2  78.2 183.6 105.  227.4 160.4 155.  104.6 119.2 175.8
 159.8 141.6 150.4 100.2 279.2 128.4  91.2 269.2 183.2  88.4 118.  151.6
  74.8  97.8 126.2 140.4 127.4 223.6 236.6 191.2 111.6 219.8  69.6 169.4
  87.6  92.6 112.  145.8 117.  153.2 115.2  92.8  67.6 172.   92.4 106.6
 208.4 173.8 113.2 104.4 141.6 128.2 226.   87.  247.6 147.6 223.6 217.2
 149.   72.6 182. ]

Преимущества и недостатки КНН

Преимущества:

  • простота реализации и интерпретации;

  • используется во многих задачах, особенно в рекомендательных системах;

  • высокая точность прогнозов при правильном выборе метрик k и расстояния.

ЧИТАТЬ   «Чемпионат»: «Зенит» хочет завербовать защитника «Флуминенсе» Нино

По умолчанию:

  • высокое потребление памяти и низкая скорость работы из-за хранения и расчета расстояний между всеми обучающими и тестируемыми выборками (т.е. KNN в чистом виде);

  • чувствительность к выбросам и шуму, а также несбалансированным классам в данных;

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

Дополнительные источники

Статьи:

  • «Поиск ближайшего соседа методом грубой силы на графическом процессоре», Шэнгрен Ли и Нина Амента;

  • «Неконтролируемое разделение пространства для поиска ближайшего соседа», Абрар Фахим, Мохаммед Юнус Али и Мухаммад Аамир Чима;

  • «Дерево шаров: эффективная пространственная индексация для ограниченного поиска ближайших соседей в метрических пространствах», Мохамад Долатшах, Али Хадиан и Бехруз Минаи-Бидголи;

  • «Развитие KD-дерева и поиска KNN», Виджай Р. Тивари.

Документация:

Видео: А, два, три.


Дерево решений (КОРЗИНА) 🡆

Source

От admin