алгоритм k-ближайших соседей - k-nearest neighbors algorithm

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

• В классификации k-NN выводом является членство в классе. Объект классифицируется множеством голосов его соседей, при этом объекту присваивается класс, наиболее распространенный среди его k ближайших соседей (k - положительное целое число, обычно небольшое). Если k = 1, то объект просто назначается классу этого единственного ближайшего соседа.

• В регрессии k-NN выходом является значение свойства для объекта. Это значение является средним из значений k ближайших соседей.

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

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

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

Особенностью алгоритма k-NN является то, что он чувствителен к локальной структуре данных.

• 1 Статистическая настройка
• 2 Алгоритм
• 3 Выбор параметра
• 4 Классификатор 1-ближайшего соседа
• 5 Взвешенный классификатор ближайшего соседа
• 6 Свойства
• 7 Ошибка скорости
• 8 Метрическое обучение
• 9 Извлечение признаков
• 10 Уменьшение размерности
• 11 Граница принятия решения
• 12 Сокращение данных
  • 12.1 Выбор класса выбросов
  • 12.2 CNN для сокращения данных
• 13 k-NN регрессия
• 14 k-NN выброса
• 15 Проверка результатов
• 16 См. Также
• 17 Ссылки
• 18 Дополнительная литература

Предположим у нас есть пары $(X\; 1,\; Y\; 1),\; (X\; 2,\; Y\; 2),\dots ,\; (X\; n,\; Y\; n)\; \{\backslash \; displaystyle\; (X\_\; \{1\},\; Y\_\; \{1\}),\; (X\_\; \{2\; \},\; Y\_\; \{2\}),\; \backslash \; dots,\; (X\_\; \{n\},\; Y\_\; \{n\})\}$принимает значения в $R\; d\; \times \; \{1,\; 2\}\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{R\; \}\; ^\; \{d\}\; \backslash \; times\; \backslash \; \{1,2\; \backslash \}\}$, где Y - метка класса X, так что $X\; |\; Y\; =\; р\; \sim \; п\; р\; \{\backslash \; displaystyle\; X\; |\; Y\; =\; r\; \backslash \; sim\; P\_\; \{r\}\}$для $r\; =\; 1,\; 2\; \{\backslash \; displaystyle\; r\; =\; 1,2\}$(и распределения вероятностей $P\; r\; \{\backslash \; displaystyle\; P\_\; \{r\}\}$). Дана некоторая норма $\Vert \; \cdot \; \Vert \; \{\backslash \; displaystyle\; \backslash \; |\; \backslash \; cdot\; \backslash \; |\}$на $R\; d\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{R\}\; ^\; \{d\}\}$и точка $x\; \in \; R\; d\; \{\backslash \; displaystyle\; x\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{d\}\}$, пусть $(X\; (1),\; Y\; (1)),\dots ,\; (Икс\; (п),\; Y\; (п))\; \{\backslash \; Displaystyle\; (X\; \_\; \{(1)\},\; Y\; \_\; \{(1)\}),\; \backslash \; точки,\; (X\; \_\; \{(п)\},\; Y\; \_\; \{(п)\})\}$быть переупорядочиванием данных обучения так, чтобы $\Vert \; X\; (1)\; -\; x\; \Vert \; \le \; \cdots \; \le \; \Vert \; X\; (n)\; -\; x\; \Vert \; \{\backslash \; displaystyle\; \backslash \; |\; X\; \_\; \{(1)\}\; -\; x\; \backslash \; |\; \backslash \; leq\; \backslash \; dots\; \backslash \; leq\; \backslash \; |\; X\; \_\; \{(n)\}\; -\; x\; \backslash \; |\}$

Пример классификации k-NN. Тестовый образец (зеленая точка) следует классифицировать либо по синим квадратам, либо по красным треугольникам. Если k = 3 (круг сплошной линией), он назначается красным треугольникам, потому что внутри внутреннего круга 2 треугольника и только 1 квадрат. Если k = 5 (круг из пунктирной линии), он присваивается синим квадратам (3 квадрата против 2 треугольников внутри внешнего круга).

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

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

Обычно используемая метрика расстояния для непрерывных переменных - это евклидово расстояние. Для дискретных переменных, например, для классификации текста, можно использовать другую метрику, такую ​​как метрика перекрытия (или расстояние Хэмминга ). В контексте данных микроматрицы экспрессии генов, например, k-NN использовался с коэффициентами корреляции, такими как Пирсон и Спирмен, в качестве показателя. Часто точность классификации k-NN может быть значительно улучшена, если метрика расстояния изучена с помощью специализированных алгоритмов, таких как Large Margin Nearest Neighbor или Анализ компонентов соседства.

Недостаток основного " Классификация «большинством голосов» происходит, когда распределение по классам искажено. То есть примеры более частого класса имеют тенденцию доминировать в предсказании нового примера, потому что они имеют тенденцию быть общими среди k ближайших соседей из-за их большого количества. Один из способов решить эту проблему - взвесить классификацию с учетом расстояния от тестовой точки до каждого из ее k ближайших соседей. Класс (или значение в задачах регрессии) каждой из k ближайших точек умножается на вес, пропорциональный обратной величине расстояния от этой точки до контрольной точки. Другой способ преодоления перекоса - абстракция в представлении данных. Например, в самоорганизующейся карте (SOM) каждый узел является представителем (центром) кластера подобных точек, независимо от их плотности в исходных обучающих данных. Затем K-NN может быть применен к SOM.

Наилучший выбор k зависит от данных; как правило, большие значения k уменьшают влияние шума на классификацию, но делают границы между классами менее четкими. Хороший k можно выбрать с помощью различных эвристических методов (см. оптимизация гиперпараметров ). Частный случай, когда прогнозируется, что класс является классом ближайшей обучающей выборки (т.е.когда k = 1), называется алгоритмом ближайшего соседа.

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

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

Самый интуитивно понятный классификатор типа ближайшего соседа - это классификатор одного ближайшего соседа, который назначает точка x к классу ее ближайшего соседа в пространстве функций, то есть $C\; n\; 1\; nn\; (x)\; =\; Y\; (1)\; \{\backslash \; displaystyle\; C\_\; \{n\}\; ^\; \{1nn\}\; (x)\; =\; Y\; \_\; \{(\; 1)\}\}$.

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

Классификатор k-ближайшего соседа можно рассматривать как присвоение k ближайшим соседям веса $1\; /\; k\; \{\backslash \; displaystyle\; 1\; /\; k\}$и все остальные 0 вес. Это может быть обобщено на взвешенные классификаторы ближайшего соседа. То есть, где i-му ближайшему соседу назначается вес $wni\; \{\backslash \; displaystyle\; w\_\; \{ni\}\}$, где $\sum \; i\; =\; 1\; nwni\; =\; 1\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; w\_\; \{ni\}\; =\; 1\}$. Аналогичный результат о строгой согласованности взвешенных классификаторов ближайших соседей также имеет место.

Пусть $C\; nwnn\; \{\backslash \; displaystyle\; C\_\; \{n\}\; ^\; \{wnn\}\}$обозначает взвешенный ближайший классификатор с весами $\{wni\}\; i\; =\; 1\; n\; \{\backslash \; displaystyle\; \backslash \; \{w\_\; \{ni\}\; \backslash \}\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\}$. При соблюдении условий регулярности распределений классов избыточный риск имеет следующее асимптотическое разложение

$RR\; (C\; nwnn)\; -\; RR\; (CB\; ayes)\; =\; (B\; 1\; sn\; 2\; +\; B\; 2\; tn\; 2)\; \{1\; +\; o\; (1)\},\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{R\}\}\; \_\; \{\backslash \; mathcal\; \{R\}\}\; (C\_\; \{n\}\; ^\; \{wnn\})\; -\; \{\backslash \; mathcal\; \{R\}\}\; \_\; \{\backslash \; mathcal\; \{R\}\}\; (C\; ^\; \{Bayes\; \})\; =\; \backslash \; left\; (B\_\; \{1\}\; s\_\; \{n\}\; ^\; \{2\}\; +\; B\_\; \{2\}\; t\_\; \{n\}\; ^\; \{2\}\; \backslash \; right)\; \backslash \; \{1\; +\; o\; (1)\; \backslash \},\}$

для константы $B\; 1\; \{\backslash \; displaystyle\; B\_\; \{1\}\}$и $B\; 2\; \{\backslash \; displaystyle\; B\_\; \{2\}\}$, где $sn\; 2\; =\; \sum \; i\; =\; 1\; nwni\; 2\; \{\backslash \; displaystyle\; s\_\; \{n\}\; ^\; \{2\}\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; w\_\; \{ni\}\; ^\; \{2\}\}$и $tn\; =\; n\; -\; 2\; /\; d\; \sum \; я\; знак\; равно\; 1\; nwni\; \{я\; 1\; +\; 2\; /\; d\; -\; (я\; -\; 1)\; 1\; +\; 2\; /\; d\}\; \{\backslash \; displaystyle\; t\_\; \{n\}\; =\; n\; ^\; \{-\; 2\; /\; d\}\; \backslash \; sum\; \_\; \{i\; =\; 1\; \}\; ^\; \{n\}\; w\_\; \{ni\}\; \backslash \; \{i\; ^\; \{1\; +\; 2\; /\; d\}\; -\; (i-1)\; ^\; \{1\; +\; 2\; /\; d\}\; \backslash \}\}$.

Оптимальная схема взвешивания $\{wni\; \ast \; \}\; i\; =\; 1\; n\; \{\backslash \; displaystyle\; \backslash \; \{w\_\; \{ni\}\; ^\; \{*\}\; \backslash \}\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\}$, уравновешивающий два члена на приведенном выше дисплее. следующим образом: set $k\; \ast \; =\; \lfloor \; B\; n\; 4\; d\; +\; 4\; \rfloor \; \{\backslash \; displaystyle\; k\; ^\; \{*\}\; =\; \backslash \; lfloor\; Bn\; ^\; \{\backslash \; frac\; \{4\}\; \{d\; +\; 4\}\}\; \backslash \; rfloor\}$,

$wni\; *\; знак\; равно\; 1\; k\; *\; [1\; +\; d\; 2\; -\; d\; 2\; k\; *\; 2\; /\; d\; \{я\; 1\; +\; 2\; /\; d\; -\; (i\; -\; 1)\; 1\; +\; 2\; /\; d\}]\; \{\backslash \; displaystyle\; w\_\; \{ni\}\; ^\; \{*\}\; =\; \{\backslash \; frac\; \{1\}\; \{k\; ^\; \{*\}\}\}\; \backslash \; left\; [1\; +\; \{\backslash \; frac\; \{d\}\; \{2\}\}\; -\; \{\backslash \; frac\; \{d\}\; \{2\; \{k\; ^\; \{*\}\}\; ^\; \{2\; /\; d\}\}\}\; \backslash \; \{i\; ^\; \{1\; +\; 2\; /\; d\}\; -\; (i-1)\; ^\; \{1\; +\; 2\; /\; d\}\; \backslash \}\; \backslash \; right]\}$для $i\; =\; 1,\; 2,\dots ,\; K\; \ast \; \{\backslash \; displaystyle\; i\; =\; 1,2,\; \backslash \; dots,\; k\; ^\; \{*\}\}$и

$wni\; \ast \; =\; 0\; \{\backslash \; displaystyle\; w\_\; \{ni\}\; ^\; \{*\}\; =\; 0\; \}$для $i\; =\; k\; \ast \; +\; 1,\dots ,\; n\; \{\backslash \; displaystyle\; i\; =\; k\; ^\; \{*\}\; +\; 1,\; \backslash \; dots,\; n\}$.

С оптимальными весами доминирующий член в асимптотическое разложение избыточного риска: $O\; (n\; -\; 4\; d\; +\; 4)\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{O\}\}\; (n\; ^\; \{-\; \{\backslash \; frac\; \{4\}\; \{d\; +\; 4\}\}\})\}$. Аналогичные результаты верны при использовании классификатора ближайшего соседа.

k-NN является частным случаем переменной полосы пропускания, «баллонной» оценки плотности ядра с унифицированное ядро ​​.

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

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

Для классификации k-NN мультиклассов, Cover и Hart (1967) доказывают коэффициент ошибок верхней границы

$R\; \ast \; \le \; R\; k\; NN\; \le \; R\; \ast \; (2\; -\; MR\; \ast \; M\; -\; 1)\; \{\backslash \; displaystyle\; R\; ^\; \{*\}\; \backslash \; \backslash \; leq\; \backslash \; R\_\; \{k\; \backslash \; mathrm\; \{NN\}\}\; \backslash \; \backslash \; leq\; \backslash \; R\; ^\; \{*\}\; \backslash \; left\; (2\; -\; \{\backslash \; frac\; \{MR\; ^\; \{*\}\}\; \{M-1\}\}\; \backslash \; right)\}$

где $R\; \ast \; \{\backslash \; displaystyle\; R\; ^\; \{*\}\}$- коэффициент ошибок Байеса (который является минимально возможным коэффициентом ошибок), $R\; k\; NN\; \{\backslash \; displaystyle\; R\_\; \{kNN\}\}$- коэффициент ошибок k-NN, а M количество классов в задаче. Для $M\; =\; 2\; \{\backslash \; displaystyle\; M\; =\; 2\}$и поскольку коэффициент байесовских ошибок $R\; \ast \; \{\backslash \; displaystyle\; R\; ^\; \{*\}\}$приближается к нулю, это предел уменьшается до «не более чем вдвое выше байесовской ошибки».

Есть много результатов по частоте ошибок k классификаторов ближайшего соседа. Классификатор k-ближайшего соседа является строго (то есть для любого совместного распределения на $(X,\; Y)\; \{\backslash \; displaystyle\; (X,\; Y)\}$) согласованным при условии $k:\; =\; kn\; \{\backslash \; displaystyle\; k:\; =\; k\_\; \{n\}\}$расходится, а $kn\; /\; n\; \{\backslash \; displaystyle\; k\_\; \{n\}\; /\; n\}$сходится к нулю при $n\; \to \; \infty \; \{\; \backslash \; displaystyle\; n\; \backslash \; to\; \backslash \; infty\}$.

Пусть $C\; nknn\; \{\backslash \; displaystyle\; C\_\; \{n\}\; ^\; \{knn\}\}$обозначает классификатор k ближайших соседей на основе обучающего набора размера n. При определенных условиях регулярности избыточный риск дает следующее асимптотическое разложение

$RR\; (C\; nknn)\; -\; RR\; (CB\; ayes)\; =\; \{B\; 1\; 1\; k\; +\; B\; 2\; (kn)\; 4\; /\; d\}\; \{\; 1\; +\; о\; (1)\},\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{R\}\}\; \_\; \{\backslash \; mathcal\; \{R\}\}\; (C\_\; \{n\}\; ^\; \{knn\})\; -\; \{\backslash \; mathcal\; \{R\}\}\; \_\; \{\backslash \; mathcal\; \{R\; \}\}\; (C\; ^\; \{Bayes\})\; =\; \backslash \; left\; \backslash \; \{B\_\; \{1\}\; \{\backslash \; frac\; \{1\}\; \{k\}\}\; +\; B\_\; \{2\}\; \backslash \; left\; (\{\backslash \; frac\; \{k\}\; \{n\}\}\; \backslash \; right)\; ^\; \{4\; /\; d\}\; \backslash \; right\; \backslash \}\; \backslash \; \{1\; +\; o\; (1)\; \backslash \},\}$

для некоторых констант $B\; 1\; \{\backslash \; displaystyle\; B\_\; \{1\}\}$и $B\; 2\; \{\backslash \; displaystyle\; B\_\; \{2\}\}$.

Выбор $k\; \ast \; =\; \lfloor \; B\; n\; 4\; d\; +\; 4\; \rfloor \; \{\backslash \; displayst\; yle\; k\; ^\; \{*\}\; =\; \backslash \; lfloor\; Bn\; ^\; \{\backslash \; frac\; \{4\}\; \{d\; +\; 4\}\}\; \backslash \; rfloor\}$предлагает компромисс между двумя терминами на приведенном выше экране, для которого $k\; \ast \; \{\backslash \; displaystyle\; k\; ^\; \{*\}\}$-ошибка ближайшего соседа сходится к байесовской ошибке с оптимальной (минимакс ) скоростью $O\; (n\; -\; 4\; d\; +\; 4)\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{O\}\}\; (n\; ^\; \{-\; \{\backslash \; frac\; \{4\}\; \{d\; +\; 4\}\}\})\}$.

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

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

Пример типичного конвейера вычислений компьютерного зрения для распознавания лиц с использованием k-NN, включая этапы предварительной обработки выделения признаков и уменьшения размеров (обычно реализованные с OpenCV ):

1. Хаар обнаружение лиц
2. средний сдвиг анализ отслеживания
3. PCA или Fisher LDA проекция в пространство признаков с последующей классификацией k-NN

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

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

Извлечение признаков и уменьшение размеров можно объединить за один этап с помощью анализа главных компонентов (PCA), линейного дискриминантного анализа (LDA) или канонической корреляции методы анализа (CCA) в качестве этапа предварительной обработки, за которым следует кластеризация по k-NN по векторам признаков в пространстве уменьшенной размерности. В машинном обучении этот процесс также называется низкоразмерным встраиванием.

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

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

Сокращение данных является одним из самые важные проблемы для работы с огромными наборами данных. Обычно для точной классификации требуются только некоторые точки данных. Эти данные называются прототипами и могут быть найдены следующим образом:

1. Выберите выбросы класса, то есть обучающие данные, которые неправильно классифицированы по k-NN (для данного k)
2. Разделить остальные данных в два набора: (i) прототипы, которые используются для решений по классификации, и (ii) поглощенные точки, которые могут быть правильно классифицированы k-NN с использованием прототипов. Затем поглощенные точки могут быть удалены из обучающей выборки.

Выбор классов-выбросов

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

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

Выбросы класса с k-NN создают шум. Их можно обнаружить и разделить для дальнейшего анализа. Учитывая два натуральных числа, k>r>0, обучающий пример называется (k, r) NN классом-выбросом, если его k ближайших соседей включают более r примеров других классов.

CNN для сокращения данных

Сжатый ближайший сосед (CNN, алгоритм Hart ) - это алгоритм, предназначенный для сокращения набора данных для классификации k-NN. Он выбирает набор прототипов U из обучающих данных, так что 1NN с U могут классифицировать примеры почти так же точно, как 1NN со всем набором данных.

Расчет соотношения границ. Три типа точек: прототипы, выбросы классов и поглощенные точки.

Учитывая обучающий набор X, CNN работает итеративно:

1. Сканирует все элементы X, ища для элемента x, чей ближайший прототип из U имеет метку, отличную от x.
2. Удалите x из X и добавьте его в U
3. Повторяйте сканирование, пока в U не перестанут быть добавлены прототипы.

Используйте U вместо X для классификации. Примеры, не являющиеся прототипами, называются «поглощенными» точками.

Эффективно сканировать обучающие примеры в порядке уменьшения соотношения границ. Коэффициент границы обучающего примера x определяется как

a (x) = || x'-y || / || x-y ||

где || x-y || - это расстояние до ближайшего примера y, имеющего другой цвет, чем x, и || x'-y || - это расстояние от y до ближайшего к нему примера x 'с той же меткой, что и x.

Соотношение границ находится в интервале [0,1], потому что || x'-y || никогда не превышает || x-y ||. Такой порядок отдает предпочтение границам классов для включения в набор прототипов U. Точка с меткой, отличной от x, называется внешней по отношению к x. Расчет коэффициента границ показан на рисунке справа. Точки данных помечены цветами: начальная точка - x, а ее метка - красная. Внешние точки синие и зеленые. Ближайшей к x внешней точкой является y. Ближайшая к y красная точка - это x '. Соотношение границ a (x) = || x'-y || / || x-y || - атрибут начальной точки x.

Ниже представлена ​​серия рисунков CNN. Есть три класса (красный, зеленый и синий). Рис. 1: изначально в каждом классе 60 баллов. На рис. 2 показана карта классификации 1NN: каждый пиксель классифицируется по 1NN с использованием всех данных. На рис. 3 показана классификационная карта 5NN. Белые области соответствуют неклассифицированным регионам, где голосование 5NN привязано (например, если среди 5 ближайших соседей есть две зеленые, две красные и одна синяя точки). На рис. 4 показан сокращенный набор данных. Крестики - это выбросы классов, выбранные по правилу (3,2) NN (все три ближайших соседа этих экземпляров принадлежат другим классам); квадраты - прототипы, а пустые кружки - точки поглощения. В левом нижнем углу показаны номера классов-выбросов, прототипов и поглощенных баллов для всех трех классов. Количество прототипов в этом примере варьируется от 15% до 20% для разных классов. На рис. 5 показано, что карта классификации 1NN с прототипами очень похожа на карту с исходным набором данных. Цифры были получены с помощью апплета Миркса.

• Уменьшение модели CNN для классификаторов k-NN
• 

  Рис. 1. Набор данных.

• 

  Рис. 2. Карта классификации 1NN.

• 

  Рис. 3. Классификационная карта 5NN.

• 

  Рис. 4. Сокращенный набор данных CNN.

• 

  Рис. 5. Карта классификации 1NN на основе извлеченных прототипов CNN.

В регрессии k-NN алгоритм k-NN используется для оценки непрерывных переменных. Один из таких алгоритмов использует средневзвешенное значение k ближайших соседей, взвешенное по величине, обратной их расстоянию. Этот алгоритм работает следующим образом:

1. Вычислить расстояние Евклида или Махаланобиса от примера запроса до помеченных примеров.
2. Упорядочить помеченные примеры, увеличивая расстояние.
3. Найдите эвристически оптимальное число k ближайших соседей на основе RMSE. Это выполняется с помощью перекрестной проверки.
4. Рассчитать обратное средневзвешенное расстояние с k-ближайшими многомерными соседями.

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

A матрица неточностей или «матрица соответствия» часто используется в качестве инструмента для проверки точности классификации k-NN. Также могут применяться более надежные статистические методы, такие как критерий отношения правдоподобия.

• Математический портал

• Классификатор ближайшего центроида
• Проблема ближайшей пары точек

• Дашарати, Белур В., изд. (1991). Нормы ближайшего соседа (NN): методы классификации шаблонов NN. ISBN 978-0-8186-8930-7.
• Шахнарович Григорий; Даррелл, Тревор; Индик, Петр, ред. (2005). Методы ближайшего соседа в обучении и видении. MIT Нажмите. ISBN 978-0-262-19547-8.