Алгоритм классификации ближайших соседей (KNN)

Вводные замечания

Задачи классификации основаны на оценке схожести классифицируемых объектов с объектами, для которых принадлежность к то или иному классу известна. Если формально для оценки сходства объектов в пространстве $X$ вводится некоторая функция расстояния или метрика $\rho (x,x')$, то алгоритмы классификации, основанные на анализе подобной функции, часто называют метрическими, даже в тех случаях, когда функция $\rho$ не удовлетворяет всем аксиомам метрики (например, аксиоме треугольника).Типичным представителем алгоритмов классификации, использующих эту логику, является алгоритм k-ближайших соседей — k-nearest neighbors algorithm (KNN). Метод был впервые разработан Эвелином Фиксом и Джозефом Лоусоном Ходжесом в 1951 году, и позднее развит Томасом Ковером. Все метрические алгоритмы имеют базовые формальные основания и особенности, поэтому, целесообразно начать с краткокого рассмотрения математических оснований метрических алгоримов

Математические основы метрических алгоритмов классификации**

Постановка задачи метрической классификации

Имеется пространство объектов $X$ и конечное множество имён классов $Y$.На множестве $X$ задана функция расстояния $\rho :X \times X \to (0,\infty ]$.Существует целевая зависимость $y^* :X \to Y$ значения которой известны только на объектах обучающей выборки $X^l = \left( {x_i ,y_i } \right)_i^l ,y_i = y^* \left( {x_i } \right)$.Требуется построить алгоритм классификации $a: X → Y$ , аппроксимирующий целевую зависимость $y^*(x)$ на всём множестве $X$

Метод ближайших соседей и его обобщения

Для произвольного объекта $u \in X$ расположим элементы обучающей выборки $x_1, . . . , x_l$ в порядке возрастания расстояний до $u$:

$$\rho \left( {u,x_{1,u} } \right) \le \rho \left( {u,x_{2,u} } \right)....\rho \left( {u,x_{i,u} } \right),$$

где через $x_{i,u}$ обозначается $i$-й сосед объекта $u$. Аналогичное обозначение введём и для ответа на $i$-м соседе: $y_{i,u} = y^* \left( {x_{i,u} } \right)$.Каждый объект $u \in X$ порождает свою перенумерацию выборки $x_{1,u}, . . . , x_{l,u}$.

Алгоритм ближайшего соседа (nearest neighbor, NN) является самым простым алгоритмом классификации. Он относит классифицируемый объект $u \in X^l$ к тому классу, которому принадлежит ближайший обучающий объект:

$$a\left( {u,X^l } \right) = y_{1,u}$$

Обучение NN сводится к элементарному запоминанию выборки $X^l$ . Единственное достоинство этого алгоритма — простота реализации. Недостатков гораздо больше:

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

• Отсутствие параметров, которые можно было бы настраивать по выборке. Алгоритм полностью зависит от того, насколько удачно выбрана метрика $\rho$ .

• В результате — низкое качество классификации

Алгоритм $k$ ближайших соседей (k nearest neighbors, kNN). Чтобы сгладить шумовое влияние выбросов, будем классифицировать объекты путём голосования по $k$ ближайшим соседям. Каждый из соседей $x_{i,u}$, $i = 1, . . . , k$ голосует за отнесение объекта $u$ к своему классу $y_{i,u}$. Алгоритм относит объект $u$ к тому классу, который наберёт большее число голосов:

$$a\left( {u;X^l ,k} \right) = \mathop {\arg \max }\limits_{y \in Y} \sum\limits_{i = 1}^k {\left[ {y_{i,u} = y} \right]}$$

При $k = 1$ этот алгоритм совпадает с предыдущим, следовательно, неустойчив к шуму. При $k = l$, наоборот, он чрезмерно устойчив и вырождается в константу.Таким образом, крайние значения $k$ нежелательны. На практике оптимальное значение параметра $k$ определяют по критерию скользящего контроля с исключением объектов по одному (leave-one-out, LOO). Для каждого объекта $x_i \in X^l$ проверяется,правильно ли он классифицируется по своим $k$ ближайшим соседям.

$$LOO\left( {X^l ,k} \right) = \sum\limits_{i = 1}^l {\left[ {a\left( {x_i ;X^l \backslash \left\{ {x_i } \right\},k} \right) \ne y_i } \right]} \to \mathop {\min }\limits_k$$

Если классифицируемый объект $x_i$ не исключать из обучающей выборки,то ближайшим соседом $x_i$ всегда будет сам $x_i$, и минимальное (нулевое) значение функционала $LOO(k)$ будет достигаться при $k = 1$

Недостаток $kNN$ в том, что максимальная сумма голосов может достигаться на нескольких классах одновременно. В задачах с двумя классами этого можно избежать, если брать только нечётные значения $k$. Более общая тактика, которая годится и для случая многих классов — ввести строго убывающую последовательность вещественных весов $w_i$, задающих вклад $i$-го соседа в классификацию

$$a\left( {u;X^l ,k} \right) = \mathop {\arg \max }\limits_{y \in Y} \sum\limits_{i = 1}^k {\left[ {y_{i,u} = y} \right]} w_i$$

Выбор последовательности $w_i$ является эвристикой. Если взять линейно убывающие веса $w_i = \frac{{k + 1 - i}}{k}$ , то неоднозначности также могут возникать, хотя и реже (пример: классов два; первый и четвёртый сосед голосуют за класс 1, второй и третий — за класс 2; суммы голосов совпадают). Неоднозначность устраняется окончательно,если взять нелинейную последовательность, скажем, геометрическую прогрессию:$w_i = q^i$ , где знаменатель прогрессии $q \in (0, 1)$ является параметром алгоритма.

Обобщённый метрический классификатор. Описанные выше алгоритмы классификации являются частными случаями одной общей формулы.Пусть задана весовая функция $w(i, u)$, которая оценивает степень важности $i$-го соседа для классификации объекта $u$. Естественно полагать, что эта функция неотрицательна и не возрастает по $i$. Согласно гипотезе компактности чем меньше $i$,тем ближе объекты $u$ и $x_{i,u}$, тем выше шансы, что они принадлежат одному классу.

Метрическим алгоритмом классификации с обучающей выборкой $X^l$ будем называть отображение вида:

$$a\left( {u;X^l } \right) = \mathop {\arg \max }\limits_{y \in Y} \underbrace {\sum\nolimits_{i = 1}^l {\left[ {y_{i,u} = y} \right]w(i,u)} }_{\Gamma _y \left( {u,X^l } \right)}\;\;\;(1)$$

Алгоритм $a$ относит объект $u$ к тому классу, для которого суммарный вес ближайших обучающих объектов $\Gamma _y \left( u \right) \equiv \Gamma _y \left( {u,X^l } \right)$ максимален. Выбирая весовую функцию $w(i, u)$, можно получать различные типы метрических алгоритмов классификации:

• $w\left( {i,u} \right) = \left[ {i = 1} \right]$ - ближайший сосед;

• $w\left( {i,u} \right) = \left[ {i \le k} \right]$ -$k$ ближайших соседей;

• $w\left( {i,u} \right) = \left[ {i \le k} \right]q^i$ -$k$ взвешенных ближайших соседей

Обучающая выборка $X^l$ играет роль параметра алгоритма $a$. Настройка сводится к запоминанию выборки, и, возможно, оптимизации ещё каких-то параметров(например, размера и состава),однако сами объекты не подвергаются обработке и сохраняются «как есть». По этой причине метрические алгоритмы относятся к методам вывода на основе прецедентов (case-based reasoning, CBR). Здесь действительно можно говорить о «выводе», так как на вопрос «почему объект $u$ был отнесён к классу $y$?» алгоритм может дать понятный эксперту ответ: «потому, что имеются прецеденты — схожие с ним объекты,принадлежащие классу $y$», и предъявить список этих прецедентов.

Достоинства простых метрических алгоритмов типа kNN.

• Простота реализации и возможность введения различных модификаций.

• Возможность интерпретировать классификацию объекта путём предъявления пользователю ближайшего объекта или нескольких. "Прецедентная" логика работы алгоритма хорошо понятна экспертам в таких предметных областях, как медицина, биометрия, юриспруденция.

Недостатки простых метрических алгоритмов типа kNN.

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

• Поиск ближайшего соседа «в лоб» требует сравнения классифицируемого объекта со всеми объектами выборки за $O(l)$ операций. Для задач с большими выборками это может оказаться накладно. Проблема решается с помощью эффективных алгоритмов поиска ближайших соседей, которые требуют в среднем $O(ln l)$ операций.

• В исходном виде модель алгоритмов kNN крайне бедна. Она имеет только свободный параметр k, да и тот дискретный с небольшим числом разумных альтернатив. Для обогащения модели необходимо вводить веса объектов и/или параметризовать способ вычисления метрики.Выходом из этого положение является использования концепта ML, где обучающая выборка может варьироваться и по размеру и по составу объектов, а k и метрика это гиперпараметры алгоритма KNN могут оцениваться с помощью соотвествующих статистических процедур, разработанных в рамках парадигмы ML.

Проблема выбора метрик

Выбор метрики $\rho \left( {x,x'} \right)$ в пространстве объектов $X$ является серьёзной проблемой в задачах классификации. Метрика — это математическая модель сходства объектов, и её выбор во многих случаях не однозначен. В то же время, в большинстве метрических алгоритмов предполагается, что метрика фиксирована. В последнее время всё чаще применяются методы,в которых метрика настраивается по обучающей выборке.

Если объекты описываются набором признаков $f_11(x), . . . , f_n(x)$, первое, что приходит в голову — применить евклидову метрику:

$$\rho \left( {x,x'} \right) = \left( {\sum\limits_{j = 1}^n {\left( {f_j \left( x \right) - f_j \left( {x'} \right)} \right)^2 } } \right)^{\frac{1}{2}}$$

Её обобщением является взвешенная метрика Минковского:

$$\rho \left( {x,x'} \right) = \left( {\sum\limits_{j = 1}^n {c_j \left| {f_j \left( x \right) - f_j \left( {x'} \right)} \right|^p } } \right)^{\frac{1}{p}}$$

где $c_j$ — веса признаков, показатель степени $p$ может принимать значения от 1 до $\infty$ включительно.Когда $p = 1$, то имеем так называемое манхэттенское расстояние. Если $p = 2$, то приходим к евклидову расстоянию. Есть еще одно расстояние, называемое расстоянием Чебышева, которое возникает при $p = \infty$:

• $\rho \left( {x,x'} \right) = \sum\limits_{j = 1}^n {c_j \left| {f_j \left( x \right) - f_j \left( {x'} \right)} \right|}$ - манхэттенское расстояние

• $\rho \left( {x,x'} \right) = \mathop {\max }\limits_{j = 1,...,n} c_j \left| {f_j \left( x \right) - f_j \left( {x'} \right)} \right|$ -расстояние Чебышева

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

При реализации алгоритма KNN в рамках концепции ML может использоваться по мимо рассмотренных выше метрик еще целое множество метрик:

The 'metric' parameter of KNeighborsClassifier must be a str among {'minkowski', 'cityblock', 'kulsinski', 'yule', 'infinity', 'chebyshev', 'mahalanobis', 'rogerstanimoto', 'haversine', 'russellrao', 'l1', 'canberra', 'sokalmichener', 'pyfunc', 'euclidean', 'precomputed', 'dice', 'manhattan', 'matching', 'jaccard', 'cosine', 'seuclidean', 'hamming', 'braycurtis', 'nan_euclidean', 'p', 'l2', 'correlation', 'sqeuclidean', 'sokalsneath'}

Выбор конкретной метрики определяется характером и размером исходных данных на базе использования метов ML,связанных с оценкой гиперпарметров алгоритма KNN.

Что касается весов $c_j$ их часто задают исходя из следующего соображения:вес точек обратно пропорционален их расстоянию. В этом случае более близкие соседи точки запроса будут иметь большее влияние, чем соседи, находящиеся дальше.Однако такой способ не позволяет учитывать относительную важность (ценность, информативность) признаков, а в многомерных пространствах приводит к проблеме «проклятия размерности» (curse of dimensionality) — чем выше размерность пространства признаков, тем более устойчивой становится значение метрики.Увеличение размерности в пределе $n →\infty$ приводит к тому, что все точки выборки становятся почти одинаково далеки друг от друга. Становится невозможно выделить локальную окрестность объекта, теряется информация о структуре метрического пространства. Это существенно затрудняет решение задачи классификации.

Решение заключается в том, чтобы применять более тонкие методы для настройки весов $c_j$.В частности целесообразно, если это возможно, использовать информацию от экспертов о важности признаков. Причём в пространствах с избыточным количеством признаков значительная часть весов должна обнуляться.

Простой численный пример использования алгоритма KNN

Алгоритм knn - один из самых простых алгоритмов классификации. Даже при такой простоте он может дать очень конкурентоспособные результаты. Этот алгоритм является алгоритмом с учителем, где известна цель, но неизвестна траектория движения к ней. Понимание алгоритма ближайших соседей составляет квинтэссенцию машинного обучения. Как же работает этот алгоритм ? Лучше всего это можно понять на простом конкретном примере.

Рассмотрим следующую задачу. Имеется класс из пятнадцати учеников. Учитель исходя из среднего балла учеников по гуманитарным дисциплинам (литература, языки, история и т.д.) и среднего балла по точным естественно-научным дисциплинам (математика, физика, химия и.т.д) делит учеников на следующие кластеры: положительные универсалии (Yplus-отличники), лирики(G), физики(E), негативные универсалии (Yminus-троечники)

Данные на основании которых учитель осуществил свою классификацию  представлены ниже: 

| №|   x_est    |   y_gum     |  cl_u     |
| 1|    4.7     |    4.9      | Yplus     |
| 2|    3.5     |    4.9      | G         |
| 3|    4.7     |    3.6      | E         |
| 4|    4.6     |    5.0      | Yplus     |
| 5|    3.3     |    3.0      | Yminus    |
| 6|    4.9     |    3.9      | E         |
| 7|    4.8     |    3.5      | E         |
| 8|    3.3     |    4.9      | G         |
| 9|    3.5     |    4.7      | G         |
|10|    4.9     |    4.9      | Yplus     |
|11|    3.3     |    3.3      | Yminus    |
|12|    3.7     |    4.8      | G         |
|13|    3.9     |    4.6      | G         |
|14|    5.0     |    3.3      | E         |
|15|    3.0     |    3.1      | Yminus    |

В класс пришли три новых ученика, у которых имется следующая успеваемость:

| № | xnov_est | ynov_gum |
| 1 | 4.0      | 4.0      |
| 2 | 4.6      | 4.1      |
| 3 | 3.5      | 4.2      |

Перед учителем стоит задача к какому кластеру отнести вновь прибывших учеников. 
Визуально картина выглядит следующим образом (рис. 1)

Как видно из рисунка 1 раньше ученики в классе были распределены по достаточно компактным четырем кластерам (G - лирики, E- физики , Yplus -отличники, Yminus -троечники). Новые ученики (отмечены красными кружками) не попадают в привычную картинку, они распологаются между сформированных кластеров. Учитель в растеренности к какому кластеру отнести вновь прибывших. И здесь ему на помощь приходит алгоритм ближайших соседей.

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

$$d_{j0,i} = \sqrt {\left( {x_{j0} - x_i } \right)^2 + \left( {y_{j0} - y_i } \right)^2 }$$

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

1уч. 2уч. 3уч. 4уч.  5уч. 6уч. 7уч. 8уч. 9уч. 10уч. 11уч. 12уч. 13уч. 14уч. 15уч.
н1  1.14 1.03 0.81 1.17 1.22  0.91 0.94 1.14 0.86 1.27  0.99  0.85  0.61  1.22  1.35 
н2  0.81 1.36 0.51 0.90 1.70  0.36 0.63 1.53 1.25 0.85  1.53  1.14  0.86  0.89  1.89 
н3  1.39 0.70 1.34 1.36 1.22  1.43 1.48 0.73 0.50 1.57  0.92  0.63  0.57  1.75  1.21

Рассмотрим эту матрицу внимательнее. Пусть нас интересует новый ученик с номером 1, его расстояния со всеме старыми учениками представлены в первой строке матрицы (на рис. 1 в виде соотвествующих стрелок). Найдем для него ближайшего соседа. Таким является ученик 13 ( 0.608), который принадлежит кластеру G. Вторым по близости является ученик 3 (0.806, Е), третьим ученик 12 (0.854, G), четвертым ученик 9 (0.860, G). Этот процесс можно продолжить и дальше. Но что это дает нам с точки зрения решения задачи ? А это дает нам информацию для принятия решения об принадлежности 1-го нового ученика к соотвествующему кластеру. Но чтобы использовать эту информацию мы должны сначала принять решение на каком шаге нужно прекратить процесс поиска ближайших соседей. То есть определить параметр k и сформулировать правило принятия решения о принадлежности оцениваемого объекта на основании информации о ближайших k соседях. Интуитивно понятно,что чиcло k должно быть относительно небольшим (как минимум на порядок меньше числа используемых для оценки объектов) и желательно быть нечетным. Так как самое простое правило может состоять в следующем: оцениваемый объект относится к тому кластеру, к которому принадлежит большинство из k ближайших соседей. В нашем случае наиболее целесообразным является k=3 (G,E,G) при k=4 (G,E,G,G) , следовательно, 1-го нового ученика необходимо отнести к клатеру G. Аналогично поступаем со вторым и третьим новыми учениками. Графически сразу видно,что второй новый ученик будет отнесен к кластеру E, а третий к кластеру G.

Реализация KNN классификатора в python

Алгоритм KNeighborsClassifier реализован в виде одного из пакетов модуля sklearn.cluster. Для его использования необходимо загрузить пакет:

from sklearn.neighbors import KNeighborsClassifier

Вызов:

KNeighborsClassifier(n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=None)

Параметры :

n_neighbors целое число, по умолчанию = 5 -Количество используемыхсоседей;

weights {'uniform', 'distance'}, вызываемые или нет, по умолчанию = 'uniform' -Весовая функция, используемая при прогнозировании. Возможные значения:

• 'uniform': одинаковые веса. Все точки в каждой окрестности имеют одинаковый вес.

• 'distance': вес точек обратно пропорционален их расстоянию. в этом случае более близкие соседи точки запроса будут иметь большее влияние, чем соседи, находящиеся дальше.

• [callable]: определяемая пользователем функция, которая принимает массив расстояний и возвращает массив той же формы, содержащий веса.

algorithm {'auto', 'ball_tree', 'kd_tree', 'грубый'}, по умолчанию = 'auto' Алгоритм, используемый для вычисления ближайших соседей:

• 'ball_tree' будет использоватьBallTree

• «kd_tree» будет использоватьKDTree

• 'brute' будет использовать поиск методом грубой силы.

• «auto» попытается выбрать наиболее подходящий алгоритм на основе значений, переданных в fit метод.

leaf_size целое число, по умолчанию = 30 -Размер листа передается в BallTree или KDTree. Это может повлиять на скорость построения и запроса, а также на объем памяти, необходимый для хранения дерева. Оптимальное значение зависит от характера проблемы.

p целое, по умолчанию = 2 Параметр мощности для метрики Минковского. Когда p = 1, это эквивалентно использованию manhattan_distance (l1) и euclidean_distance (l2) для p = 2. Для произвольного p используется minkowski_distance (l_p).

metric str или вызываемая, default='minkowski' Метрика, используемая для вычисления расстояния. По умолчанию используется «минковский», что приводит к стандартному евклидову расстоянию при p = 2. Допустимые значения показателей см. в документации по scipy.spatial.distance и перечисленным метрикам distance_metrics.

metric_params dict, по умолчанию = нет Дополнительные аргументы ключевого слова для метрической функции.

n_jobs int, по умолчанию = Нет Количество параллельных заданий, запускаемых для поиска соседей. None означает 1, если только в joblib.parallel_backend контексте. -1 означает использование всех процессоров.

Атрибуты :

classes_ массив формы (n_classes,) Метки классов, известные классификатору

effective_metric_ str или callble Используемая метрика расстояния. Он будет таким же, как metricпараметр, или его синонимом, например, «евклидово», если для metricпараметра установлено значение «Минковский», а для p параметра установлено значение 2.

effective_metric_params_ dict Дополнительные аргументы ключевого слова для метрической функции. Для большинства метрик будет то же самое, что и у metric_params параметра, но они также могут содержать значение параметра p, если для effective_metric_ атрибута установлено значение «Минковский».

n_features_in_ int Количество функций, наблюдаемых во время подгонки .

feature_names_in_ ndarray формы ( n_features_in_,) Названия функций, видимых во время подгонки . Определяется только в том случае, если X имена объектов состоят из строк.

n_samples_fit_ int Количество выборок в подобранных данных.

outputs_2d_ bool False, когда во yвремя подгонки форма имеет значение (n_samples, ) или (n_samples, 1), в противном случае — True.

Методы:

fit(X, y) Подбор классификатора k-ближайших соседей для набора обучающих данных

Параметры :

X {массив, разреженная матрица} формы (n_samples, n_features) или (n_samples, n_samples), если metric='precomputed' Данные обучения.

y {разреженная матрица в виде массива} формы (n_samples,) или (n_samples, n_outputs) Целевые значения.

Возвращает : классификатор KNeighbours Подобранный классификатор k-ближайших соседей.

get_metadata_routing ( ) Получить маршрутизацию метаданных этого объекта.

Возвращает :маршрутизацию запроса метаданных. Инкапсулирующая MetadataRequest информацию о маршрутизации.

kneighbors(X=None, n_neighbors=None, return_distance=True) Найдите K-соседей точки.

Возвращает: индексы и расстояния до соседей каждой точки.

Параметры :

X {массив, разреженная матрица}, форма (n_queries, n_features) или (n_queries, n_indexed), если метрика == 'предварительно вычисленная', по умолчанию = нет.Точка или точки запроса. Если не указано, возвращаются соседи каждой индексированной точки. В этом случае точка запроса не считается своим соседом.

n_neighbors int, по умолчанию = нет.Количество соседей, необходимое для каждого образца. По умолчанию используется значение, переданное конструктору.

return_distance bool, по умолчанию = True. Возвращать или нет расстояния.

Возвращает :

neigh_dist ndarray формы (n_queries, n_neighbours) Массив, представляющий длины точек, присутствует только в том случае, если return_distance=True.

neigh_ind ndarray формы (n_queries, n_neighbours) Индексы ближайших точек в матрице населения.

get_params(deep=True) Получить параметры для этой оценки.

Параметры : deepbool, default=True. Если True, вернут параметры для этого оценщика и содержащиеся в нем подобъекты, которые являются оценщиками.

Возвращает :params dict Имена параметров сопоставлены с их значениями.

kneighbors_graph(X=None, n_neighbors=None, mode='connectivity') Вычислить (взвешенный) граф k-соседей для точек в X.

Параметры :

X {массив, разреженная матрица} формы (n_queries, n_features) или (n_queries, n_indexed), если метрика == 'предварительно вычисленная', по умолчанию = нет. Точка или точки запроса. Если не указано, возвращаются соседи каждой индексированной точки. В этом случае точка запроса не считается своим соседом. Форма metric='precomputed'должна быть (n_queries, n_indexed). В противном случае форма должна быть (n_queries, n_features).

n_neighbors int, по умолчанию = нет.Количество соседей для каждого образца. По умолчанию используется значение, переданное конструктору

mode{'connectivity', 'distance'}, default='connectivity'.Тип возвращаемой матрицы: «связность» вернет матрицу связности с единицами и нулями, в «расстоянии» ребра представляют собой расстояния между точками, тип расстояния зависит от выбранного параметра метрики в классе NearestNeighbors.

Возвращает :Разреженная матрица формы (n_queries, n_samples_fit).n_samples_fitколичество выборок в подобранных данных. дает вес ребра. Матрица имеет формат CSR.A[i, j]ij

predict(X) Прогнозируйте метки классов для предоставленных данных.

Параметры :

X {массив, разреженная матрица} формы (n_queries, n_features) или (n_queries, n_indexed), если метрика == 'предварительно вычислена'.Тестовые образцы.

Возвращает : y ndarray формы (n_queries) или (n_queries, n_outputs) Метки классов для каждого образца данных.

predict_proba(X) Оценки вероятности возврата для тестовых данных X.

Параметры : X {массив, разреженная матрица} формы (n_queries, n_features) или (n_queries, n_indexed), если метрика == 'предварительно вычислена'.Тестовые образцы.

Возвращает : p ndarray формы (n_queries, n_classes) или список n_outputs таких массивов, если n_outputs > 1. Вероятности классов входных выборок. Классы расположены в лексикографическом порядке.

score(X, y, sample_weight=None) Возвращает среднюю точность данных испытаний и меток.

Параметры :

Форма, подобная массиву X (n_samples, n_features).Тестовые образцы.

y массивообразной формы (n_samples,) или (n_samples, n_outputs) Настоящие этикетки для X.

sample_weight имеет форму массива (n_samples), по умолчанию = нет Образцы весов.

Возвращает : score float

set_params(params)** Установить параметры этой оценки.

Параметры : ** params dict Параметры оценки.

Возвращает : self estimator instance Экземпляр оценщика.

set_score_request ( * , sample_weight : Union [ bool , None , str ] = '$UNCHANGED$' ) → KNeighborsClassifie Метаданные запроса, передаваемые в score метод.

Параметры : sample_weight str, True, False или None, default=sklearn.utils.metadata_routing.UNCHANGED. Маршрутизация метаданных для sample_weight параметра в score.

Возвращает : self object. Обновленный объект.

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

import warnings
import numpy as np
import scipy.stats as st
from pandas import Series, DataFrame
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt

warnings.simplefilter('ignore')

vec01=['| №|   x_est    |   y_gum     |  cl_u     |',
'| 1|    4.7     |    4.9      | Yplus     |',      
'| 2|    3.5     |    4.9      | G         |',      
'| 3|    4.7     |    3.6      | E         |',      
'| 4|    4.6     |    5.0      | Yplus     |', 
'| 5|    3.3     |    3.0      | Yminus    |',
'| 6|    4.9     |    3.9      | E         |',       
'| 7|    4.8     |    3.5      | E         |',      
'| 8|    3.3     |    4.9      | G         |',      
'| 9|    3.5     |    4.7      | G         |',      
'|10|    4.9     |    4.9      | Yplus     |',      
'|11|    3.3     |    3.3      | Yminus    |',
'|12|    3.7     |    4.8      | G         |',       
'|13|    3.9     |    4.6      | G         |',
'|14|    5.0     |    3.3      | E         |',
'|15|    3.0     |    3.1      | Yminus    |']

print('Данные на основании которых учитель осуществил свою классификацию  представлены ниже: ')
print('                                                             ')
for i in range(0, 16):
    print(vec01[i])
print('                                                             ')
print('В класс пришли три новых ученика, у которых имется следующая успеваемость:')
print('                                                             ')
vec02=['| № | xnov_est | ynov_gum |',      
'| 1 | 4.0      | 4.0      |',
'| 2 | 4.6      | 4.1      |',
'| 3 | 3.5      | 4.2      |']
print('                                                             ')
for i in range(0, 4):
    print(vec02[i])

#формирование массива меток

Y=['Yplus','G','E','Yplus','Yminus','E','E','G','G','Yplus','Yminus','G','G','E','Yminus']   
y=np.array(Y)
y=y.reshape((15, 1))

#формирование массивов предикторов

X = np.zeros((15, 2))
Xnow= np.zeros((3, 2))

for i in range(1, 16):    
    cic00=vec01[i]
    cic01=cic00[8:11]    
    cic02=cic00[21:24]
    X[i-1,0]= float(cic01)
    X[i-1,1]= float(cic02)

for i in range(1, 4):
    cic00=vec02[i]
    cic01=cic00[6:9]    
    cic02=cic00[17:20]
    Xnow[i-1,0]= float(cic01)
    Xnow[i-1,1]= float(cic02)    
    
#обучение классификатора KNN
from sklearn.neighbors import KNeighborsClassifier
classifier = KNeighborsClassifier(n_neighbors=3)
classifier.fit(X, y)

#классификация новых учеников
y_pred = classifier.predict(Xnow)
print('                                                             ')
print('Результаты классификации')
print('Метки новых учеников')
print(y_pred)    
    
ydf= DataFrame(y, columns=['Class'])   
Xdf=DataFrame(X, columns=['x_est','y_gum'])   
Xydf = pd.concat([Xdf, ydf],axis=1)    

ynowdf= DataFrame(y_pred, columns=['Class'])   
Xnowdf=DataFrame(Xnow, columns=['x_est','y_gum'])   
Xynowdf = pd.concat([Xnowdf, ynowdf],axis=1)    
Xysumdf=pd.concat([Xydf,Xynowdf],ignore_index=True, axis=0)

print('                                                             ')
print('Сводная таблица результатов(новые ученики 15,16,17)')
print(Xysumdf)


Xydf1=Xydf.query("Class == 'E'")
Xydf2=Xydf.query("Class == 'G'")
Xydf3=Xydf.query("Class == 'Yplus'")
Xydf4=Xydf.query("Class == 'Yminus'")
Xynowdf1=Xynowdf.query("Class == 'E'")
Xynowdf2=Xynowdf.query("Class == 'G'")

plt.figure(figsize=(10, 6))
plt.scatter(Xydf1['x_est'], Xydf1['y_gum'], 
            c ='red', label = 'E',s=100,
            marker = '*', alpha = 0.8)
plt.scatter(Xydf2['x_est'], Xydf2['y_gum'], 
            c ='blue',label = 'G',s=100,
            marker = '*', alpha = 0.8)
plt.scatter(Xydf3['x_est'], Xydf3['y_gum'], 
            c ='green',label = 'Yplus',s=100,
            marker = '*', alpha = 0.8)
plt.scatter(Xydf4['x_est'], Xydf4['y_gum'], 
            c ='gold',label = 'Yminus',s=100,
            marker = '*', alpha = 0.8)
plt.scatter(Xynowdf1['x_est'], Xynowdf1['y_gum'], 
            c ='red',label = 'E нов.',s=150,
            marker = 'o', alpha = 1.0)
plt.scatter(Xynowdf2['x_est'], Xynowdf2['y_gum'], 
            c ='blue',label = 'G нов.',s=150,
            marker = 'o', alpha = 1.0)

plt.legend()
plt.title('Графические результаты классификации новых учеников')
plt.xlabel("Средний балл по естественно-научным дисциплинам")
plt.ylabel("Средний балл по гуманитарным дисциплинам")
plt.show()

Данные на основании которых учитель осуществил свою классификацию  представлены ниже: 
                                                             
| №|   x_est    |   y_gum     |  cl_u     |
| 1|    4.7     |    4.9      | Yplus     |
| 2|    3.5     |    4.9      | G         |
| 3|    4.7     |    3.6      | E         |
| 4|    4.6     |    5.0      | Yplus     |
| 5|    3.3     |    3.0      | Yminus    |
| 6|    4.9     |    3.9      | E         |
| 7|    4.8     |    3.5      | E         |
| 8|    3.3     |    4.9      | G         |
| 9|    3.5     |    4.7      | G         |
|10|    4.9     |    4.9      | Yplus     |
|11|    3.3     |    3.3      | Yminus    |
|12|    3.7     |    4.8      | G         |
|13|    3.9     |    4.6      | G         |
|14|    5.0     |    3.3      | E         |
|15|    3.0     |    3.1      | Yminus    |
                                                             
В класс пришли три новых ученика, у которых имется следующая успеваемость:
                                                             
                                                             
| № | xnov_est | ynov_gum |
| 1 | 4.0      | 4.0      |
| 2 | 4.6      | 4.1      |
| 3 | 3.5      | 4.2      |
                                                             
Результаты классификации
Метки новых учеников
['G' 'E' 'G']
                                                             
Сводная таблица результатов(новые ученики 15,16,17)
    x_est  y_gum   Class
0     4.7    4.9   Yplus
1     3.5    4.9       G
2     4.7    3.6       E
3     4.6    5.0   Yplus
4     3.3    3.0  Yminus
5     4.9    3.9       E
6     4.8    3.5       E
7     3.3    4.9       G
8     3.5    4.7       G
9     4.9    4.9   Yplus
10    3.3    3.3  Yminus
11    3.7    4.8       G
12    3.9    4.6       G
13    5.0    3.3       E
14    3.0    3.1  Yminus
15    4.0    4.0       G
16    4.6    4.1       E
17    3.5    4.2       G

Перейдем к рассмотрению применения KNeighborsClassifier для решения более серьёзной задачи классификации регионов РФ по типу экономики. Исходные данные те же, что мы использовали раньше( см.раздел 2_1 этой главы). Результаты алгоритма KNN зависят естественно от исходных данных, но также от целого ряда гиперпараметров, которые можно задавать и оценивать в рамках концепта ML. Во-первых,реализуя идею разбиения исходных данных на обучающую и тестовую последовательности мы получаем параметр, который определяется размером и составом тестовой (обучаюшей) последовательности. Этот параметр влиет на точность классификации тестовых объектов. Исходя из логики работа алгоритма KNN, необходимо также исследовать влияния таких параметров как: k -число соседей и используемая метрика. Есть еще один важный фактор веса признаков (функций) и точек соседей , но мы будем использовать гипотезу о равенстве весов. Прежде всего оценим для наших данных диопозоны значений параметров, влиящих на точность классификации. Величину обучающей(тестовой) последовательности целесообразно рассматривать в интервале [0.2,0.9]. Параметр k-число соседей в интервале [1,8], а используемые метрики следующие:cityblock,cosine,euclidean,nan_euclidean,canberra,braycurtis,chebyshev,minkowski(p=3). Ниже представлен скрипт, где в режиме диалога можно задать метрику и параметр k, а размер теста зафиксирован на уровне 0.2.При каждом прогоне скрипта осуществляется классификация на тесте, строиться матрица путаницы и расчитывается точность классификации.Ценность этих отдельных результатов невелика, так как при осуществлении классификации и расчете точности параметры, влияющие на результаты, зафиксированы нам одном уровне. Но в скрипте реализуются еще две процедуры. С помощью одной строиться зависимость ошибки (величина обратная точности) классификации от k при фиксированных величине test и используемой метрики.Вторая процедура основана на перекрестной проверке т.е многоратно варьируются размер и состав test(train) последовательностей и наждом уровне их уровне оценивается средняя точность классификации. В результате строятся так называемые кривые обучения. Ценность этих данных конечно выше чем, тех о которых мы говорили выше, но параметр k и метрика в данной процедуре также зафиксированы.

#Knn

import warnings
import numpy as np
import scipy.stats as st
from pandas import Series, DataFrame
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
import plotly
import plotly.express as px
import plotly.graph_objs as go

warnings.simplefilter('ignore')

#ввод исходных данных из файла
Regdata =pd.ExcelFile('REG_RU_03.xlsx')
Regtab1 =Regdata.parse('dan04')
#print(Regtab1)
ind=np.arange(0,len(Regtab1), 1)


Reg1df=DataFrame(Regtab1,index=ind,columns=['Name','PI_N','Pcx_N','PP_N','Claster'])
Reg1df = np.round(Reg1df,decimals = 2) 
Reg2df=Reg1df[['PI_N','Pcx_N','PP_N']]
Reg1df

y=Reg1df['Claster']
y=np.array(y)
X=np.array (Reg2df)

#нормирование значений элементов массива X
SUMX=X[:,0] +X[:,1] + X[:,2] 
X[:,0] =(X[:,0] /SUMX)*100
X[:,1] =(X[:,1] /SUMX)*100
X[:,2] =(X[:,2] /SUMX)*100

#выделение обучающей и тренировочной последовательностей
X_train, X_test, y_train, y_test = train_test_split  ( X , y , test_size=0.2, random_state=0)

#print('Фактические метки классов на тесте')
#print(y_test)

#Обучение 
Knn=3
KnnSTR=str(Knn)
met='euclidean'
print('ЗАДАНА МЕТРИКА',met) 
print('ХОТИТЕ ИЗМЕНИТЬ МЕТРИКУ? ВВЕДИТЕ: yes')
uslov=input()
if uslov =='yes':
    print('Введите метрику: cityblock,cosine,euclidean,nan_euclidean,canberra,braycurtis,chebyshev,minkowski')    
    met=input()
    print('ИСПОЛЬЗУЕМАЯ МЕТРИКА',met)

print('ЗАДАН n_neighbors= ',Knn)     
print('ХОТИТЕ ИЗМЕНИТЬ n_neighbors? ВВЕДИТЕ: yes')    
uslovK=input()    
if uslovK =='yes':
    print('Введите n_neighbors: 1 , 2, 3, 4, 5, 6, 7, 8')    
    Knn=int(input())
    print('ИСПОЛЬЗУЕМЫЙ n_neighbors=',Knn)
    KnnSTR=str(Knn)
    
from sklearn.neighbors import KNeighborsClassifier
classifier = KNeighborsClassifier(metric = met,p=3,n_neighbors=Knn)
classifier.fit(X_train, y_train)


#проверка на тестовой последовательности
y_pred = classifier.predict(X_test)

print('Фактические метки классов на тесте')
print(y_test)
print('Прогнозные метки классов на тесте')
print(y_pred)

#Оценка качества классификации
from sklearn.metrics import accuracy_score
eplus = accuracy_score(y_test, y_pred)
print('Bepнocть: %.2f' %eplus)

print('Матрица путаницы')
import matplotlib.pyplot as plt
from sklearn.metrics import confusion_matrix, ConfusionMatrixDisplay
cm = confusion_matrix(y_test, y_pred, labels=classifier.classes_)
disp = ConfusionMatrixDisplay(confusion_matrix=cm,display_labels=classifier.classes_)
disp.plot()
plt.show()

# ПОСТРОЕНИЕ КРИВЫХ ОБУЧЕНИЯ ==============================================


train_ndf=[]
train_meandf=[]
test_meandf=[]

from sklearn.model_selection import learning_curve
#gnb = GaussianNB()
train_size_abs, train_scores, test_scores = learning_curve(
classifier, X, y, train_sizes=np.linspace (0.1, 1, 100) )

for train_size, cv_train_scores, cv_test_scores in zip(train_size_abs, train_scores, test_scores):
    train_ndf.append(train_size)
    train_meandf.append(cv_train_scores.mean())
    test_meandf.append(cv_test_scores.mean())
    #print(f"{train_size} образцы использовались для обучения модели")
    #print(f"Средняя точность обучения {cv_train_scores.mean():.2f}")
    #print(f"Средняя точность теста {cv_test_scores.mean():.2f}")
train_n=DataFrame(train_ndf,columns=['train_size'])
train_mean=DataFrame(train_meandf,columns=['train'])
test_mean=DataFrame(test_meandf,columns=['test'])
tab_LC=pd.concat([train_n,train_mean,test_mean],axis=1)


plt.figure(figsize=(10, 6))                         
plt.plot(tab_LC.train_size,tab_LC.train,color='green', linewidth=2.0,label='train')
plt.plot(tab_LC.train_size,tab_LC.test,color='r', linewidth=2.0,label='test')
plt.xlabel(r'$trainsize$ размер обучающей выборки',fontsize=18)
plt.ylabel('Средняя точность',fontsize=18)
plt.title(r'Кривые обучения Knn='+KnnSTR+' '+met, fontsize=18)
plt.legend()
plt.grid(True)
plt.show()


#Построение графика ошибки
error = []
# Calculating error for K values between 1 and 40
for i in range(1, 9):
    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))

plt.figure(figsize=(12, 6))
plt.plot(range(1, 9), error, color='red', linestyle='dashed', marker='o',
         markerfacecolor='blue', markersize=10)
plt.title('График влияния значения K на величину средней ошибки')
plt.xlabel('Значение K')
plt.ylabel('Средняя ошибка ' +met)
plt.show()

ЗАДАНА МЕТРИКА euclidean
ХОТИТЕ ИЗМЕНИТЬ МЕТРИКУ? ВВЕДИТЕ: yes

ЗАДАН n_neighbors=  3
ХОТИТЕ ИЗМЕНИТЬ n_neighbors? ВВЕДИТЕ: yes
yes
Введите n_neighbors: 1 , 2, 3, 4, 5, 6, 7, 8
8
ИСПОЛЬЗУЕМЫЙ n_neighbors= 8
Фактические метки классов на тесте
[2 2 1 5 1 2 0 2 4 0 2 4 4 0 4 2 2]
Прогнозные метки классов на тесте
[2 2 1 5 1 2 0 2 4 0 2 4 4 0 4 2 2]
Bepнocть: 1.00
Матрица путаницы

#ПРСТРОЕНИЕ КРИВЫХ ОБУЧЕНИЯ С ИСПОЛЬЗОВАНИЕМ LearningCurveDisplay
import numpy as np
import scipy.stats as st
from pandas import Series, DataFrame
import pandas as pd
from sklearn.datasets import load_digits
from sklearn.naive_bayes import GaussianNB
import matplotlib.pyplot as plt
from sklearn.model_selection import LearningCurveDisplay
from sklearn.utils import shuffle

#ввод исходных данных из файла
Regdata =pd.ExcelFile('REG_RU_03.xlsx')
Regtab1 =Regdata.parse('dan04')
#print(Regtab1)
ind=np.arange(0,len(Regtab1), 1)


Reg1df=DataFrame(Regtab1,index=ind,columns=['Name','PI_N','Pcx_N','PP_N','Claster'])
Reg1df = np.round(Reg1df,decimals = 2) 
Reg2df=Reg1df[['PI_N','Pcx_N','PP_N']]
Reg1df

y=Reg1df['Claster']
y=np.array(y)
X=np.array (Reg2df)

#нормирование значений элементов массива X
SUMX=X[:,0] +X[:,1] + X[:,2] 
X[:,0] =(X[:,0] /SUMX)*100
X[:,1] =(X[:,1] /SUMX)*100
X[:,2] =(X[:,2] /SUMX)*100



X, y = shuffle(X, y, random_state=10)
LearningCurveDisplay.from_estimator( KNeighborsClassifier(metric = met,p=3,n_neighbors=Knn), X, y, train_sizes=np.linspace (0.1, 1, 100), cv=5)
plt.show()

Необходимо попробовать расчитывать среднюю точность классификации как двухмерную функцию от k и размера и состава test(train) последовательности. Ниже прведен скрипт python, который обеспечивает: онлайн выбор метрики, случайную генерацию размера и состава test последовательности, расчет для каждой пары значений параметров k и доля test последовательности средней точности классификации и строит на основании полученных данных 3D поверхность средней точности.

# KNN: ПОСТРОЕНИЕ 3D ПОВЕРХНОСТИ СРЕДНЕЙ ТОЧНОСТИ НА ТЕСТЕ

import warnings
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
from pandas import Series, DataFrame
import pandas as pd
import numpy as np
from scipy.interpolate import griddata
import plotly.graph_objects as go
import warnings
import scipy.stats as st
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
import plotly
import plotly.express as px
import plotly.graph_objs as go

warnings.simplefilter('ignore')

#ввод исходных данных из файла
Regdata =pd.ExcelFile('REG_RU_03.xlsx')
Regtab1 =Regdata.parse('dan04')
#print(Regtab1)
ind=np.arange(0,len(Regtab1), 1)


Reg1df=DataFrame(Regtab1,index=ind,columns=['Name','PI_N','Pcx_N','PP_N','Claster'])
Reg1df = np.round(Reg1df,decimals = 1) 
Reg2df=Reg1df[['PI_N','Pcx_N','PP_N']]
Reg1df

y=Reg1df['Claster']
y=np.array(y)
X=np.array (Reg2df)

#нормирование значений элементов массива X
SUMX=X[:,0] +X[:,1] + X[:,2] 
X[:,0] =(X[:,0] /SUMX)*1
X[:,1] =(X[:,1] /SUMX)*1
X[:,2] =(X[:,2] /SUMX)*1


xi = np.linspace(0.2, 0.9, 8)
yi = np.linspace(1, 8, 8)
#accurdf=[]
accurdf = np.zeros((8, 8))
N=np.linspace(1, 500, 500)

print('Введите метрику: cityblock,cosine,euclidean,nan_euclidean,canberra,braycurtis,chebyshev,minkowski')
met=input()
print('ИСПОЛЬЗУЕМАЯ МЕТРИКА',met)


j=-1
for isr in xi:
    j=j+1
    kk=-1
    for knn in yi:
        knn=int(knn)
        kk=kk+1
        Smean=0 
        for nn in N: 
            X1,y1=X,y
            X_train, X_test, y_train, y_test = train_test_split(X1,y1,test_size=isr)
            #Обучение 
            classifier = KNeighborsClassifier( metric = met,p=5,n_neighbors=knn)
            classifier.fit(X_train, y_train)
            #проверка на тестовой последовательности
            y_pred = classifier.predict(X_test)
            #Оценка качества классификации
            eplus = accuracy_score(y_test, y_pred) 
            Smean = Smean+eplus/int(max(N))
        
        accurdf[j,kk]=Smean

accurdf
N1=int(max(N))
tit1='  N='
tit2=str(N1)
tit=tit1+tit2+' метрика='+met

# Сброс ограничений на количество выводимых рядов
pd.set_option('display.max_rows', None)
# Сброс ограничений на число столбцов
pd.set_option('display.max_columns', None)

print(" ================  ТАБЛИЦА ТОЧНОСТИ accurdf" + tit + " ================== ")
Accurdf = pd.DataFrame(data=accurdf,index=["Test_size=0.2","Test_size=0.3","Test_size=0.4","Test_size=0.5",
"Test_size=0.6","Test_size=0.7","Test_size=0.8","Test_size=0.9"], columns=["K=1","K=2","K=3","K=4","K=5","K=6","K=7","K=8"])
Accurdf=np.round(Accurdf,decimals = 3)
print(Accurdf)
print(" ================================================================================== ")
print('ОПРЕДЕЛЕНИЕ opt ЗНАЧЕНИЙ accuracy, Test_size, К : метрика= ',met) 
nameK=["K=1","K=2","K=3","K=4","K=5","K=6","K=7","K=8"]
nameTest=["Test_size=0.2","Test_size=0.3","Test_size=0.4","Test_size=0.5","Test_size=0.6","Test_size=0.7",
          "Test_size=0.8","Test_size=0.9"]
AccyrList = Accurdf.values.tolist()
max_value = max(max(AccyrList, key=max))
max_value
res = [(obj[0], obj[1].index(max_value)) for obj in enumerate(AccyrList) if max_value in obj[1]]
res1=res[0]
nam1=nameK[res1[1]]
nam2=nameTest[res1[0]]
print('accuracy_max= ',max_value,'  ',nam2,' ',nam1)

fig = go.Figure(go.Surface(x=yi,y=xi,z=accurdf,opacity=0.8))
fig.update_traces(contours_z=dict(show=True, usecolormap=True,
                                  highlightcolor="limegreen", project_z=True))
fig.update_layout(title= ' KNN:Зависимость средней точности на тесте от доли test и К'+tit, autosize= False , 
                  width= 900 , height= 800 , 
                  margin=dict(l= 65 , r= 50 , b= 65 , t= 90 )) 

fig.update_layout(scene = dict(
                    xaxis_title='X=число соседей К',
                    yaxis_title='Y=доля теста',
                    zaxis_title='Z=средняя точность на тесте'))   

fig.show()

Введите метрику: cityblock,cosine,euclidean,nan_euclidean,canberra,braycurtis,chebyshev,minkowski
cityblock
ИСПОЛЬЗУЕМАЯ МЕТРИКА cityblock
 ================  ТАБЛИЦА ТОЧНОСТИ accurdf  N=500 метрика=cityblock ================== 
                 K=1    K=2    K=3    K=4    K=5    K=6    K=7    K=8
Test_size=0.2  0.916  0.927  0.934  0.913  0.922  0.895  0.897  0.882
Test_size=0.3  0.917  0.906  0.925  0.904  0.904  0.883  0.883  0.870
Test_size=0.4  0.912  0.898  0.909  0.890  0.891  0.870  0.861  0.836
Test_size=0.5  0.907  0.885  0.897  0.865  0.866  0.838  0.825  0.797
Test_size=0.6  0.902  0.862  0.874  0.840  0.830  0.797  0.768  0.737
Test_size=0.7  0.876  0.833  0.834  0.789  0.765  0.730  0.689  0.649
Test_size=0.8  0.843  0.763  0.744  0.686  0.632  0.584  0.524  0.477
Test_size=0.9  0.727  0.603  0.519  0.438  0.358  0.294  0.260  0.237
 ================================================================================== 
ОПРЕДЕЛЕНИЕ opt ЗНАЧЕНИЙ accuracy, Test_size, К : метрика=  cityblock
accuracy_max=  0.934    Test_size=0.2   K=3

Live Graf 3d KNN Py

Для анализа влияния метрики можно прогнать скрипт для каждой метрики,а их всего восемь и сравнить полученные результаты. В общем случае нужно ранжировать матрицы результатов, полученных для каждой метрики. Можно предложить, например, следующий способ: для каждого элемента $i,j$ построить ранжированный ряд (таких рядов будет 64) и для каждой метрики сложить соотвествующие ранги. Полученные значения суммарных рангов позволят ранжировать метрики по средней точности классификации. Желающие могут проделать эту процедуру. Но мы для сравнения метрик будем использовать только максимальное значение средней точности, получаемое при использовании каждой метрики. Сравнение метрик по максимальному элементу в матрицах результатов представлено ниже.

# АНАЛИЗ ВЛИЯНИЯ МЕТРИКИ НА ТОЧНОСТЬ КЛАССИФИКАЦИИ
import matplotlib.pyplot as plt
Test_size =[0.2,0.2,0.2,0.2,0.2,0.2,0.2]
Knn=[3,3,3,3,3,3,3]
Accurmax=[0.934,0.922,0.931,0.928,0.933,0.927,0.931]
NameMetric=['cityblock','cosine','euclidean','nan_euclidean','braycurtis','chebyshev','minkowski(p=3)']
data_par={ 'Accurmax': Accurmax,'Test_size' : Test_size,'Knn' : Knn,'NameMetric': NameMetric}
Paramoptdf=DataFrame(data_par)
print(Paramoptdf)

NamMetric=list(Paramoptdf.NameMetric)
AccurMax=list(Paramoptdf.Accurmax)

def addlabels(x,y):
    for i in range(len(x)):
        plt.text(i, y[i], y[i], ha = 'center',fontsize=18, 
                Bbox = dict(facecolor = 'white', alpha = .9))

colors = ['red', 'orange', 'yellow', 'green', 'blue', 'violet','black']

fig = plt.figure(figsize = (10, 5))
plt.bar(NamMetric, AccurMax, color =colors,alpha=0.6)
addlabels(NamMetric,AccurMax)
plt.xlabel("Используемая метрика",fontsize=12)
plt.ylabel("Максимальное значение средней точности",fontsize=12)
plt.title("График влияния метрики на максимальное значение средней точности",fontsize=16)
plt.ylim(0.910,0.940) 
plt.tight_layout()

plt.show()

   Accurmax  Test_size  Knn      NameMetric
0     0.934        0.2    3       cityblock
1     0.922        0.2    3          cosine
2     0.931        0.2    3       euclidean
3     0.928        0.2    3   nan_euclidean
4     0.933        0.2    3      braycurtis
5     0.927        0.2    3       chebyshev
6     0.931        0.2    3  minkowski(p=3)

В результате при объёме вариациии test последовательности по составу для кажого уровня ее размера и k равном N=500 для всех метрик получены орt значения k=3, Test_size=0.2,а величине accuracy_max наилучшая метрика 'cityblock'. Как видно из графика accuracy_max по метрикам различаются незначительно (сильно выпадает только метрика 'cosine'). Каждый элемент матрицы результатов можно представить как условную случайную велечину и используя статистические подходы оценить значимо ли отличаются их средние значения при разных значениях метрики.

Реализация KNN классификатора в R

Алгоритм KNN реализован в нескольких библиотеках R, рассмотрим library(class).

Описание

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

Применение:

knn(train, test, cl, k = 1, l = 0, prob = FALSE, use.all = TRUE)

Аргументы:

train матрица или кадр данных случаев обучающего набора.

test матрица или кадр данных тестового набора случаев. Вектор будет интерпретироваться как вектор-строка для одного случая.

cl значения истинной классификации обучающей выборки

k учитывается количество соседей.

l минимальное количемтво голосов за определенное решение, в противном случае doubt.

prob если это правда, доля голосов за выигравший класс возвращается как атрибут prob.

use.all контролирует обработку связей k .Если true, включаются все расстояния, равные наибольшему k. Если значение false, выбирается случайный выбор расстояний, равных th, для использования именно k соседей.

Оценка:

Значения классификации для объектов тестового набора. doubt будет возвращен как NA.

Для иллюстрации реализации алгоритма KNN в library(class) ниже приведены соотвествующие скпипты R на тех же данных о регионах РФ. Влияние велечины k на точность (ошибку) при фиксированном разбиении на train и test здесь отличается от того, что мы получили при использовании python реализации KNN.Желающие могут попробовать использовать KNN из library(FNN).

#Алгоритм Knn
options(warn=-1)
library(openxlsx)
#library(FNN)  # KNN
library(class) # KNN
library(gmodels)
library(caret)
require(ggplot2)
library(ggthemes)

#ЗАГРУЗКА ИЗ EXSEL ПЕВИЧНЫХ ДАННЫХ
N=6 # номер листа с данными
x <-read.xlsx("REG_RU_03.xlsx", sheet = N)
#x
xreg <-data.frame(X1=x$PI_N,X2=x$Pcx_N,X3=x$PP_N,Class=x$Claster)

xreg[,'Class']<-factor(xreg[,'Class'])
xreg_f <-xreg[,'Class']

xregSum =xreg[,'X1']+xreg[,'X2']+xreg[,'X3']
xreg[,'X1']=xreg[,'X1']/xregSum
xreg[,'X2']=xreg[,'X2']/xregSum
xreg[,'X3']=xreg[,'X3']/xregSum

xstr_nor <-xreg[,1:3]
xstr_nor <-cbind(xstr_nor,xreg_f)
xstr_nor <-cbind(x$Name,xstr_nor)

#Исследования влияния на ошибку велечины К-----

set.seed(4948493)
reg_sample<-sample(1:nrow(xstr_nor),size=nrow(xstr_nor)*.8)
reg_train<-xstr_nor[reg_sample,] #Выбор 80% строк
reg_test<- xstr_nor[-reg_sample,] #Выбор 20% строк

xreg_ftrain <-reg_train[,5]
xreg_ftest <-reg_test[,5]
reg_train <-reg_train[,-5]
reg_test <-reg_test[,-5]


reg_acc<-numeric()
for(i in 1:8){
 predict<-knn(reg_train[,2:4] ,reg_test[,2:4],
 xreg_ftrain,k=i)
 reg_acc<-c(reg_acc,
 mean(predict==xreg_ftest))
}
#reg_acc
options(repr.plot.width = 14, repr.plot.height =8)

plot(1-reg_acc,type="l",lwd = 5,ylab="Ошибка",
xlab="K",main="Величина ошибки в зависимости от K",)
grid(nx = NULL, ny = NULL,
     lty = 2,      # Grid line type
     col = "gray", # Grid line color
     lwd = 3)      # Grid line width

print('Прогноз классов на тесте')
reg.TEST <-cbind(reg_test,xreg_ftest,predict)
reg.TEST

#Исследования влияния на ошибку величины К при вариации обучения и теста

Kn=8
#Kn=12
trial_sum<-numeric(Kn)
trial_n<-numeric(Kn)
set.seed(6033850)
for(i in 1:1000){
reg_sample<-sample(1:nrow(xstr_nor),size=nrow(xstr_nor)*.8)
reg_train<-xstr_nor[reg_sample,] #Выбор 80% строк
reg_test<- xstr_nor[-reg_sample,] #Выбор 20% строк
test_size<-nrow(reg_test)

xreg_ftrain <-reg_train[,5]
xreg_ftest <-reg_test[,5]
reg_train <-reg_train[,-5]
reg_test <-reg_test[,-5]

for(j in 1:Kn){
predict<-knn(reg_train[,2:4],reg_test[,2:4],xreg_ftrain,k=j)
trial_sum[j]<-trial_sum[j]+sum(predict==xreg_ftest)
trial_n[j]<-trial_n[j]+test_size
}
}


Err= (trial_sum / trial_n) # ТОЧНОСТЬ
#Err= 1-(trial_sum / trial_n) # ОШИБКА
Errdf =data.frame(K=seq(from=1, to=8, by=1),ERROR_m = Err)

theme_update(text = element_text(size=20))
g4 <-ggplot(data=Errdf, aes(x=K),
colors = "Accent")
g4 <-g4 +geom_point(aes(y=ERROR_m),size=5)
g4 <-g4 +geom_line( aes(y=ERROR_m),colour='red',linetype=1,size=2)
g4 <-g4 +labs(title ="       Величина средней точности от K(1000 выборок обучения и теста )",
x="Значение К", y="Точность")
g4  <-g4+theme(axis.text = element_text(size = 16, angle=0,face = "plain")) 
g4  <-g4+theme(plot.title = element_text(size = 22,face = "plain"))
g4  <-g4+theme( axis.title = element_text(size = 18,face = "plain"))
g4



print('Матрица путаницы и точность модели')
confusionMatrix(predict,xreg_ftest)
CrossTable(x=xreg_ftest,y=predict,prob.chisq = TRUE)

[1] "Прогноз классов на тесте"

A data.frame: 17 × 6

	x$Name	X1	X2	X3	xreg_ftest	predict
	<chr>	<dbl>	<dbl>	<dbl>	<fct>	<fct>
5	Ивановская область	0.0051546392	0.08333333	0.9115120	2	2
19	Республика Карелия	0.3576938693	0.02111246	0.6211937	4	4
21	Архангельская область	0.4773978315	0.01834862	0.5042535	1	1
28	г. Санкт-Петербург	0.0128017687	0.00000000	0.9871982	2	2
35	Ростовская область	0.0248456230	0.24031965	0.7348347	0	0
37	Республика Ингушетия	0.0600000000	0.77333333	0.1666667	3	5
44	Республика Марий Эл	0.0045067601	0.22183275	0.7736605	0	0
45	Республика Мордовия	0.0003060912	0.23752678	0.7621671	0	0
57	Курганская область	0.0177638454	0.23563218	0.7466040	0	0
60	Челябинская область	0.0777802541	0.06323824	0.8589815	2	2
62	Республика Тыва	0.5434083601	0.26045016	0.1961415	1	1
63	Республика Хакасия	0.2906463268	0.05700522	0.6523485	4	4
64	Алтайский край	0.0157194680	0.28191397	0.7023666	0	0
68	Новосибирская область	0.0651403997	0.13445484	0.8004048	2	2
69	Омская область	0.0020551967	0.09894304	0.8990018	2	2
71	Республика Бурятия	0.2564372044	0.08985812	0.6537047	4	4
80	Еврейская автономная область	0.0103941819	0.29223259	0.6973732	0	0

[1] "Матрица путаницы и точность модели"

Confusion Matrix and Statistics

          Reference
Prediction 0 1 2 3 4 5
         0 1 0 0 0 0 0
         1 0 3 0 0 0 0
         2 1 0 5 0 0 0
         3 0 0 0 0 0 0
         4 0 1 0 0 4 0
         5 0 0 0 0 0 2

Overall Statistics
                                          
               Accuracy : 0.8824          
                 95% CI : (0.6356, 0.9854)
    No Information Rate : 0.2941          
    P-Value [Acc > NIR] : 7.61e-07        
                                          
                  Kappa : 0.8462          
                                          
 Mcnemar's Test P-Value : NA              

Statistics by Class:

                     Class: 0 Class: 1 Class: 2 Class: 3 Class: 4 Class: 5
Sensitivity           0.50000   0.7500   1.0000       NA   1.0000   1.0000
Specificity           1.00000   1.0000   0.9167        1   0.9231   1.0000
Pos Pred Value        1.00000   1.0000   0.8333       NA   0.8000   1.0000
Neg Pred Value        0.93750   0.9286   1.0000       NA   1.0000   1.0000
Prevalence            0.11765   0.2353   0.2941        0   0.2353   0.1176
Detection Rate        0.05882   0.1765   0.2941        0   0.2353   0.1176
Detection Prevalence  0.05882   0.1765   0.3529        0   0.2941   0.1176
Balanced Accuracy     0.75000   0.8750   0.9583       NA   0.9615   1.0000

 
   Cell Contents
|-------------------------|
|                       N |
| Chi-square contribution |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  17 

 
             | predict 
  xreg_ftest |         0 |         1 |         2 |         4 |         5 | Row Total | 
-------------|-----------|-----------|-----------|-----------|-----------|-----------|
           0 |         1 |         0 |         1 |         0 |         0 |         2 | 
             |     6.618 |     0.353 |     0.123 |     0.588 |     0.235 |           | 
             |     0.500 |     0.000 |     0.500 |     0.000 |     0.000 |     0.118 | 
             |     1.000 |     0.000 |     0.167 |     0.000 |     0.000 |           | 
             |     0.059 |     0.000 |     0.059 |     0.000 |     0.000 |           | 
-------------|-----------|-----------|-----------|-----------|-----------|-----------|
           1 |         0 |         3 |         0 |         1 |         0 |         4 | 
             |     0.235 |     7.456 |     1.412 |     0.026 |     0.471 |           | 
             |     0.000 |     0.750 |     0.000 |     0.250 |     0.000 |     0.235 | 
             |     0.000 |     1.000 |     0.000 |     0.200 |     0.000 |           | 
             |     0.000 |     0.176 |     0.000 |     0.059 |     0.000 |           | 
-------------|-----------|-----------|-----------|-----------|-----------|-----------|
           2 |         0 |         0 |         5 |         0 |         0 |         5 | 
             |     0.294 |     0.882 |     5.931 |     1.471 |     0.588 |           | 
             |     0.000 |     0.000 |     1.000 |     0.000 |     0.000 |     0.294 | 
             |     0.000 |     0.000 |     0.833 |     0.000 |     0.000 |           | 
             |     0.000 |     0.000 |     0.294 |     0.000 |     0.000 |           | 
-------------|-----------|-----------|-----------|-----------|-----------|-----------|
           4 |         0 |         0 |         0 |         4 |         0 |         4 | 
             |     0.235 |     0.706 |     1.412 |     6.776 |     0.471 |           | 
             |     0.000 |     0.000 |     0.000 |     1.000 |     0.000 |     0.235 | 
             |     0.000 |     0.000 |     0.000 |     0.800 |     0.000 |           | 
             |     0.000 |     0.000 |     0.000 |     0.235 |     0.000 |           | 
-------------|-----------|-----------|-----------|-----------|-----------|-----------|
           5 |         0 |         0 |         0 |         0 |         2 |         2 | 
             |     0.118 |     0.353 |     0.706 |     0.588 |    13.235 |           | 
             |     0.000 |     0.000 |     0.000 |     0.000 |     1.000 |     0.118 | 
             |     0.000 |     0.000 |     0.000 |     0.000 |     1.000 |           | 
             |     0.000 |     0.000 |     0.000 |     0.000 |     0.118 |           | 
-------------|-----------|-----------|-----------|-----------|-----------|-----------|
Column Total |         1 |         3 |         6 |         5 |         2 |        17 | 
             |     0.059 |     0.176 |     0.353 |     0.294 |     0.118 |           | 
-------------|-----------|-----------|-----------|-----------|-----------|-----------|

 

Ниже приведен R скрипт построения 3d поверхности точности классификации на тесте регионов РФ.

# KNN: ПОСТРОЕНИЕ 3D ПОВЕРХНОСТИ СРЕДНЕЙ ТОЧНОСТИ НА ТЕСТЕ
options(warn=-1)
library(openxlsx)
library(e1071) # naiveBayes
library(caTools)
library(caret)
library(class)
library(gmodels)
library(plotly)

#ЗАГРУЗКА ИЗ EXSEL ПЕВИЧНЫХ ДАННЫХ
N=6 # номер листа с данными
x <-read.xlsx("REG_RU_03.xlsx", sheet = N)
#x
xreg <-data.frame(X1=x$PI_N,X2=x$Pcx_N,X3=x$PP_N,Class=x$Claster)

xreg[,'Class']<-factor(xreg[,'Class'])
xreg_f <-xreg[,'Class']

xregSum =xreg[,'X1']+xreg[,'X2']+xreg[,'X3']
xreg[,'X1']=xreg[,'X1']/xregSum
xreg[,'X2']=xreg[,'X2']/xregSum
xreg[,'X3']=xreg[,'X3']/xregSum

xstr_nor <-xreg[,1:3]
xstr_nor <-cbind(xstr_nor,xreg_f)
xstr_nor <-cbind(x$Name,xstr_nor)

N <<-1:500 # объем вариаций на каждом уровне train и К
accurdf <<- matrix(0, ncol = 8, nrow = 8)## Создать нулевую матрицу 

# Функция расчета матрицы точности классификации KNN
f <- function(sr,kn){
j=0
for (isr in sr)
#-------------------------формирование и вариация train test
{ #print(isr)
j=j+1  
for (knn in kn)
      #-----------------------вариация по гипер параметру knn
{ #print(knn)    
Smean=0      
for (nn in N)
          #-------------------классификация и формирование матрицы средней точности
{#print(nn)
split <- sample.split(xstr_nor, SplitRatio = isr)
train_cl <- subset(xstr_nor , split == "TRUE")
test_cl <- subset(xstr_nor, split == "FALSE")
predict<-knn(train_cl[,2:4],test_cl[,2:4],train_cl$xreg_f,k=knn)
# Матрица путаницы
cm <- table(test_cl$xreg_f,predict)
# Оценка модели
accuracy=confusionMatrix(cm)$overall[1]  
Smean = Smean+accuracy/max(N) 
#Smean = Smean+ max(N)
} # конец цикла по N
#print(c(j, knn,Smean))
accurdf[j,knn]=Smean
} # конец цикла по knn
} # конец цикла по isr
return(accurdf)
} # конец функции


sr=seq(from=0.2, to=0.9, by=0.1)
kn=seq(from=1, to=8, by=1) 
z=f(sr,kn)

t1='KNN:Зависимость средней точности на тесте от доли train и К'
t2=as.character(max(N))
t3=' N='
tit=paste(t1,t3,t2)
t4='===============  ТАБЛИЦА ТОЧНОСТИ accurdf'
t5=' ============= '
tittab=paste(t4,t3,t2,t5)

print(tittab)
Accurdf <- as.data.frame(z)
colnames(Accurdf) <- c('K=1', 'K=2', 'K=3','K=4', 'K=5', 'K=6', 'K=7', 'K=8')
rownames(Accurdf) <- c("Train_size=0.2", "Train_size=0.3", "Train_size=0.4", "Train_size=0.5",
"Train_size=0.6", "Train_size=0.7", "Train_size=0.8", "Train_size=0.9")
library(dplyr)
Accurdf  %>% mutate(across(where(is.numeric), ~ round(., 3)))
print('===========================================================')
accurmax= max(Accurdf)
accurmax2=round(accurmax, 3)
accurind=which(Accurdf == accurmax, arr.ind = TRUE)
Sr=1-sr[accurind[1]] 
K= accurind[2]
cat('accuracymax=',accurmax2,'k=',K,'Доля test=',Sr)

fig <- plot_ly(x = kn, y = sr, z = z) %>% add_surface(name='Поверхность точности',colors = c('blue', 'green','red'))
fig <- fig %>% layout(title = tit,width=950, height=800,
                      scene = list(xaxis = list(title = 'y=число соседей К',gridcolor = 'blue'),
                     yaxis = list(title = 'x=доля train  ',gridcolor = 'blue'),
                     zaxis = list(title = 'z=средняя точность',gridcolor = 'blue')),
                     paper_bgcolor = 'rgb(243, 243, 243)',
                     plot_bgcolor = '#e5ecf6'
                     )

              

fig

[1] "===============  ТАБЛИЦА ТОЧНОСТИ accurdf  N= 500  ============= "

A data.frame: 8 × 8

	K=1	K=2	K=3	K=4	K=5	K=6	K=7	K=8
	<dbl>	<dbl>	<dbl>	<dbl>	<dbl>	<dbl>	<dbl>	<dbl>
Train_size=0.2	0.841	0.767	0.718	0.677	0.629	0.556	0.485	0.419
Train_size=0.3	0.837	0.768	0.715	0.672	0.632	0.567	0.474	0.428
Train_size=0.4	0.923	0.883	0.881	0.852	0.823	0.790	0.751	0.721
Train_size=0.5	0.921	0.879	0.883	0.850	0.823	0.787	0.752	0.718
Train_size=0.6	0.937	0.924	0.937	0.903	0.895	0.883	0.873	0.841
Train_size=0.7	0.939	0.924	0.936	0.900	0.889	0.881	0.871	0.847
Train_size=0.8	0.928	0.957	0.976	0.941	0.913	0.901	0.905	0.895
Train_size=0.9	0.926	0.958	0.977	0.936	0.914	0.899	0.906	0.896

[1] "==========================================================="
accuracymax= 0.977 k= 3 Доля test= 0.1

Live Graf 3d KNN R