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

Не путать с k-означает кластеризацию.

В статистика, то kалгоритм ближайших соседей (k-NN) это непараметрический метод, предложенный Томас Обложка используется для классификация и регресс.^[1] В обоих случаях вход состоит из k ближайшие примеры обучения в пространство функций. Результат зависит от того, k-NN используется для классификации или регрессии:

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

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

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

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

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

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

Статистическая установка

Предположим, у нас есть пары ${\displaystyle (X_{1},Y_{1}),(X_{2},Y_{2}),\dots ,(X_{n},Y_{n})}$ принимая ценности в ${\displaystyle \mathbb {R} ^{d}\times \{1,2\}}$, куда Y это метка класса Икс, так что ${\displaystyle X|Y=r\sim P_{r}}$ за ${\displaystyle r=1,2}$ (и распределения вероятностей ${\displaystyle P_{r}}$). Учитывая некоторую норму ${\displaystyle \|\cdot \|}$ на ${\displaystyle \mathbb {R} ^{d}}$ и точка ${\displaystyle x\in \mathbb {R} ^{d}}$, позволять ${\displaystyle (X_{(1)},Y_{(1)}),\dots ,(X_{(n)},Y_{(n)})}$ быть переупорядочиванием обучающих данных таким образом, чтобы ${\displaystyle \|X_{(1)}-x\|\leq \dots \leq \|X_{(n)}-x\|}$

Алгоритм

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

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

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

Часто используемый показатель расстояния для непрерывные переменные является Евклидово расстояние. Для дискретных переменных, например для классификации текста, можно использовать другую метрику, например метрика перекрытия (или же Расстояние Хэмминга ). В контексте данных микрочипа экспрессии генов, например, k-NN использовался с коэффициентами корреляции, такими как Пирсон и Спирмен, в качестве метрики.^[5] Часто точность классификации k-NN можно значительно улучшить, если метрика расстояния изучена с помощью специализированных алгоритмов, таких как Большая маржа по ближайшему соседу или же Анализ компонентов окружения.

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

Выбор параметра

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

Точность kАлгоритм -NN может сильно ухудшиться из-за присутствия зашумленных или нерелевантных функций, или если масштаб функций не соответствует их важности. Было вложено много исследовательских усилий в выбор или же масштабирование особенности для улучшения классификации. Особо популярный^{[нужна цитата ]} подход - это использование эволюционные алгоритмы для оптимизации масштабирования функций.^[8] Другой популярный подход - масштабирование объектов по взаимная информация обучающих данных с обучающими классами.^{[нужна цитата ]}

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

В 1-классификатор ближайшего соседа

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

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

Взвешенный классификатор ближайшего соседа

В k-классификатор ближайшего соседа можно рассматривать как присваивающий k ближайшие соседи вес ${\displaystyle 1/k}$ и все остальные 0 масса. Это может быть обобщено на взвешенные классификаторы ближайшего соседа. То есть где я-ому ближайшему соседу присваивается вес ${\displaystyle w_{ni}}$, с ${\displaystyle \sum _{i=1}^{n}w_{ni}=1}$. Имеет место аналогичный результат о сильной согласованности взвешенных классификаторов ближайших соседей.^[10]

Позволять ${\displaystyle C_{n}^{wnn}}$ обозначают взвешенный ближайший классификатор с весами ${\displaystyle \{w_{ni}\}_{i=1}^{n}}$. При соблюдении условий регулярности^{[требуется дальнейшее объяснение ]} на распределениях классов избыточный риск имеет следующее асимптотическое разложение^[11]

${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{wnn})-{\mathcal {R}}_{\mathcal {R}}(C^{Bayes})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},}$

для констант ${\displaystyle B_{1}}$ и ${\displaystyle B_{2}}$ куда ${\displaystyle s_{n}^{2}=\sum _{i=1}^{n}w_{ni}^{2}}$ и ${\displaystyle t_{n}=n^{-2/d}\sum _{i=1}^{n}w_{ni}\{i^{1+2/d}-(i-1)^{1+2/d}\}}$.

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

${\displaystyle w_{ni}^{*}={\frac {1}{k^{*}}}\left[1+{\frac {d}{2}}-{\frac {d}{2{k^{*}}^{2/d}}}\{i^{1+2/d}-(i-1)^{1+2/d}\}\right]}$ за ${\displaystyle i=1,2,\dots ,k^{*}}$ и

${\displaystyle w_{ni}^{*}=0}$ за ${\displaystyle i=k^{*}+1,\dots ,n}$.

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

Характеристики

k-NN - это частный случай переменная пропускная способность, "баллонная" оценка плотности ядра с униформой ядро.^[12][13]

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

k-NN имеет сильные последовательность полученные результаты. Поскольку объем данных приближается к бесконечности, двухклассный k-Алгоритм NN гарантированно дает частоту ошибок не хуже, чем в два раза Коэффициент байесовских ошибок (минимально достижимая частота ошибок с учетом распределения данных).^[14] Различные улучшения k-NN скорости возможны с использованием графиков близости.^[15]

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

${\displaystyle R^{*}\ \leq \ R_{k\mathrm {NN} }\ \leq \ R^{*}\left(2-{\frac {MR^{*}}{M-1}}\right)}$

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

Частота ошибок

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

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

${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{knn})-{\mathcal {R}}_{\mathcal {R}}(C^{Bayes})=\left\{B_{1}{\frac {1}{k}}+B_{2}\left({\frac {k}{n}}\right)^{4/d}\right\}\{1+o(1)\},}$

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

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

Метрическое обучение

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

Извлечение признаков

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

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

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

Уменьшение размеров

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

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

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

Для очень многомерных наборов данных (например, при выполнении поиска сходства в потоковом видео в реальном времени, данных ДНК или многомерных Временные ряды ) быстрый бег приблизительный k-NN поиск с использованием хеширование с учетом местоположения, "случайные проекции",^[19] "зарисовки" ^[20] или другие методы поиска многомерного сходства из VLDB набор инструментов может быть единственным возможным вариантом.

Граница решения

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

Сжатие данных

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

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

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

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

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

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

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

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

Расчет соотношения границ.

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

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

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

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

Эффективно сканировать обучающие примеры в порядке уменьшения соотношения границ.^[23] Граничный коэффициент обучающего примера Икс определяется как

а(Икс) = ||х'-у||/||х-у||

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

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

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

• Редукция модели CNN для классификаторов k-NN
• 

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

• 

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

• 

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

• 

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

• 

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

k-NN регресс

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

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

k-NN выброс

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

Подтверждение результатов

А матрица путаницы или «матрица соответствия» часто используется как инструмент для проверки точности k-NN классификация. Более надежные статистические методы, такие как критерий отношения правдоподобия также может применяться.^{[как? ]}

Смотрите также

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

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

Рекомендации

1. Альтман, Наоми С. (1992). "Введение в непараметрическую регрессию ядра и ближайшего соседа" (PDF). Американский статистик. 46 (3): 175–185. Дои:10.1080/00031305.1992.10475879. HDL:1813/31637.
2. Пирьонеси С. Мадех; Эль-Дираби Тамер Э. (01.06.2020). «Роль аналитики данных в управлении инфраструктурными активами: преодоление проблем, связанных с размером и качеством данных». Журнал транспортного машиностроения, часть B: Тротуары. 146 (2): 04020022. Дои:10.1061 / JPEODX.0000175.
3. Хасти, Тревор. (2001). Элементы статистического обучения: интеллектуальный анализ данных, вывод и прогнозирование: с 200 полноцветными иллюстрациями. Тибширани, Роберт., Фридман, Дж. Х. (Джером Х.). Нью-Йорк: Спрингер. ISBN  0-387-95284-5. OCLC  46809224.
4. Эта схема является обобщением линейной интерполяции.
5. Jaskowiak, Pablo A .; Кампелло, Рикардо Дж. Г. Б. «Сравнение коэффициентов корреляции как меры несходства для классификации рака в данных экспрессии генов». Бразильский симпозиум по биоинформатике (BSB 2011): 1–8. CiteSeerX  10.1.1.208.993.
6. Куманс, Дэнни; Массарт, Дезире Л. (1982). «Альтернативные правила k-ближайшего соседа в контролируемом распознавании образов: Часть 1. Классификация k-ближайшего соседа с использованием альтернативных правил голосования». Analytica Chimica Acta. 136: 15–27. Дои:10.1016 / S0003-2670 (01) 95359-0.
7. Everitt, Brian S .; Ландау, Сабина; Лиз, Морвен; и Шталь, Даниэль (2011) «Разные методы кластеризации», в Кластерный анализ, 5-е издание, John Wiley & Sons, Ltd., Чичестер, Великобритания
8. Нигш, Флориан; Бендер, Андреас; ван Бюрен, Бернд; Тиссен, Йос; Нигш, Эдуард; Митчелл, Джон Б. О. (2006). «Прогноз температуры плавления с использованием алгоритмов k-ближайшего соседа и оптимизации генетических параметров». Журнал химической информации и моделирования. 46 (6): 2412–2422. Дои:10.1021 / ci060149f. PMID  17125183.
9. Холл, Питер; Park, Byeong U .; Самворт, Ричард Дж. (2008). «Выбор порядка соседей в классификации ближайших соседей». Анналы статистики. 36 (5): 2135–2152. arXiv:0810.5276. Bibcode:2008arXiv0810.5276H. Дои:10.1214 / 07-AOS537. S2CID  14059866.
10. Стоун, Чарльз Дж. (1977). «Последовательная непараметрическая регрессия». Анналы статистики. 5 (4): 595–620. Дои:10.1214 / aos / 1176343886.
11. Самворт, Ричард Дж. (2012). «Оптимальные взвешенные классификаторы ближайшего соседа». Анналы статистики. 40 (5): 2733–2763. arXiv:1101.5783. Дои:10.1214 / 12-AOS1049. S2CID  88511688.
12. Террелл, Джордж Р .; Скотт, Дэвид В. (1992). «Оценка плотности переменного ядра». Анналы статистики. 20 (3): 1236–1265. Дои:10.1214 / aos / 1176348768.
13. Миллс, Питер (2012-08-09). «Эффективная статистическая классификация спутниковых измерений». Международный журнал дистанционного зондирования.
14. Обложка, Томас М.; Харт, Питер Э. (1967). «Классификация паттернов ближайшего соседа» (PDF). IEEE Transactions по теории информации. 13 (1): 21–27. CiteSeerX  10.1.1.68.2616. Дои:10.1109 / TIT.1967.1053964.
15. Туссен, Годфрид Т. (апрель 2005 г.). «Геометрические графы близости для улучшения методов ближайшего соседа в обучении на основе экземпляров и интеллектуальном анализе данных». Международный журнал вычислительной геометрии и приложений. 15 (2): 101–150. Дои:10.1142 / S0218195905001622.
16. Деврой, Люк; Дьёрфи, Ласло; Лугоши, Габор (1996). Вероятностная теория распознавания образов. Springer. ISBN  978-0-3879-4618-4.
17. Бейер, Кевин; и другие. "Когда" ближайший сосед "имеет значение?" (PDF). Теория баз данных - ICDT'99. 1999: 217–235.
18. Шоу, Блейк; и Джебара, Тони; «Вложение, сохраняющее структуру», в Материалы 26-й ежегодной международной конференции по машинному обучению, ACM, 2009 г.
19. Бингхэм, Элла; и Маннила, Хейкки; «Случайная проекция при уменьшении размерности: приложения к графическим и текстовым данным», в Материалы седьмой международной конференции ACM SIGKDD по открытию знаний и интеллектуальному анализу данных, ACM, 2001 г.
20. Райан, Донна (редактор); Открытие высокой производительности во временных рядах, Берлин: Springer, 2004, ISBN  0-387-00857-8
21. Бремнер, Дэвид; Демейн, Эрик; Эриксон, Джефф; Яконо, Джон; Лангерман, Стефан; Морен, Пат; Туссен, Годфрид Т. (2005). «Чувствительные к выходу алгоритмы для вычисления границ решения ближайшего соседа». Дискретная и вычислительная геометрия. 33 (4): 593–604. Дои:10.1007 / s00454-004-1152-0.
22. Харт, Питер Э. (1968). «Краткое правило ближайшего соседа». IEEE Transactions по теории информации. 18: 515–516. Дои:10.1109 / TIT.1968.1054155.
23. Миркес, Евгений М .; KNN и потенциальная энергия: апплет, Университет Лестера, 2011 г.
24. Рамасвами, Шридхар; Растоги, Раджив; Шим, Кюсок (2000). Эффективные алгоритмы извлечения выбросов из больших наборов данных. Материалы международной конференции ACM SIGMOD 2000 года по управлению данными - SIGMOD '00. п. 427. Дои:10.1145/342009.335437. ISBN  1-58113-217-4.
25. Campos, Guilherme O .; Зимек, Артур; Сандер, Йорг; Кампелло, Рикардо Дж. Г. Б .; Миченкова, Барбора; Шуберт, Эрих; Согласие, Ира; Хоул, Майкл Э. (2016). «Об оценке неконтролируемого обнаружения выбросов: меры, наборы данных и эмпирическое исследование». Интеллектуальный анализ данных и обнаружение знаний. 30 (4): 891–927. Дои:10.1007 / s10618-015-0444-8. ISSN  1384-5810. S2CID  1952214.

дальнейшее чтение

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