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

Непараметрический метод классификации

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

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

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

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

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

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

Статистическая настройка

Предположим, что у нас есть пары, принимающие значения в , где Y — метка класса X , так что для (и распределений вероятностей ). Учитывая некоторую норму на и точку , пусть будет переупорядочением обучающих данных таким образом, что . ${\displaystyle (X_{1},Y_{1}),(X_{2},Y_{2}),\dots ,(X_{n},Y_{n})}$ ${\displaystyle \mathbb {R} ^{d}\times \{1,2\}}$ ${\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 квадрат. Если k = 5 (пунктирный круг), он относится к синим квадратам (3 квадрата против 2 треугольников внутри внешнего круга).

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

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

Применение классификатора k- NN с учетом k = 3 соседей. Слева — учитывая контрольную точку «?», алгоритм ищет 3 ближайшие точки в обучающем наборе и принимает большинство голосов для классификации его как «класс красный». Справа — итеративно повторяя прогноз по всему пространству признаков (X1, X2), можно изобразить «поверхность принятия решений».

Обычно используемой метрикой расстояния для непрерывных переменных является евклидово расстояние . Для дискретных переменных, таких как классификация текста, может использоваться другая метрика, такая как метрика перекрытия (или расстояние Хэмминга ). Например, в контексте данных микроматриц экспрессии генов k -NN использовался с коэффициентами корреляции, такими как Пирсон и Спирмен, в качестве метрики. ^[5] Часто точность классификации k -NN может быть значительно улучшена, если метрика расстояния изучается с помощью специализированных алгоритмов, таких как Large Margin Nearest Neighbor или Neighbourhood components analysis .

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

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

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

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

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

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

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

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

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

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

Пусть обозначает взвешенный ближайший классификатор с весами . При соблюдении условий регулярности, которые в асимптотической теории являются условными переменными, требующими предположений для дифференциации параметров с некоторыми критериями. На распределениях классов избыточный риск имеет следующее асимптотическое разложение ^[11] для констант и , где и . ${\displaystyle C_{n}^{wnn}}$ ${\displaystyle \{w_{ni}\}_{i=1}^{n}}$ $${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{wnn})-{\mathcal {R}}_{\mathcal {R}}(C^{\text{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}\left\{i^{1+2/d}-(i-1)^{1+2/d}\right\}}$

Оптимальная схема взвешивания , которая уравновешивает два термина на дисплее выше, имеет следующий вид: набор , для и для . ${\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 гарантированно выдает частоту ошибок не хуже, чем в два раза больше частоты ошибок Байеса (минимально достижимая частота ошибок, учитывая распределение данных). ^[2] Различные улучшения скорости k -NN возможны с использованием графов близости. ^[14]

Для многоклассовой k- NN классификации Ковер и Харт (1967) доказали верхнюю границу частоты ошибок, где — частота ошибок Байеса (минимально возможная частота ошибок), — асимптотическая частота ошибок k- NN, а M — число классов в задаче. Эта граница является жесткой в ​​том смысле, что как нижняя, так и верхняя границы достижимы некоторым распределением. ^[15] Для и по мере того, как частота ошибок Байеса приближается к нулю, этот предел уменьшается до «не более чем в два раза больше частоты ошибок Байеса». $${\displaystyle R^{*}\ \leq \ R_{k\mathrm {NN} }\ \leq \ R^{*}\left(2-{\frac {MR^{*}}{M-1}}\right)}$$ ${\displaystyle R^{*}}$ ${\displaystyle R_{kNN}}$ ${\displaystyle M=2}$ ${\displaystyle R^{*}}$

Коэффициент ошибок

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

Пусть обозначает k ближайших соседей-классификаторов, основанных на обучающем наборе размера n . При определенных условиях регулярности избыточный риск дает следующее асимптотическое разложение ^[11] для некоторых констант и . ${\displaystyle C_{n}^{knn}}$ $${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{knn})-{\mathcal {R}}_{\mathcal {R}}(C^{\text{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^{*}=\left\lfloor Bn^{\frac {4}{d+4}}\right\rfloor }$ ${\displaystyle k^{*}}$ ${\displaystyle {\mathcal {O}}\left(n^{-{\frac {4}{d+4}}}\right)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Сокращение данных

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

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

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

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

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

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

Сжатый метод ближайших соседей для сокращения объема данных

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

Расчет граничного коэффициента

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

При наличии обучающего набора X CNN работает итеративно:

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

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

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

а ( х ) = ⁠‖ х'-у ‖/‖ ху ‖⁠

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

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

Ниже представлена ​​иллюстрация 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.

к-NN-регрессия

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

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

к-NN выброс

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

Проверка результатов

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

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

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

• Ближайший центроидный классификатор
• Задача о ближайшей паре точек
• Граф ближайшего соседа
• Категоризация объектов на основе сегментации

Ссылки

1. Fix, Evelyn; Hodges, Joseph L. (1951). Дискриминационный анализ. Непараметрическая дискриминация: свойства последовательности (PDF) (отчет). Школа авиационной медицины ВВС США, Рэндольф-Филд, Техас. Архивировано (PDF) из оригинала 26 сентября 2020 г.
2. Cover, Thomas M. ; Hart, Peter E. (1967). "Классификация шаблонов ближайшего соседа" (PDF) . IEEE Transactions on Information Theory . 13 (1): 21–27. CiteSeerX 10.1.1.68.2616 . doi :10.1109/TIT.1967.1053964. S2CID  5246200. 
3. Хасти, Тревор. (2001). Элементы статистического обучения: добыча данных, вывод и прогнозирование: с 200 полноцветными иллюстрациями . Тибширани, Роберт., Фридман, Дж. Х. (Джером Х.). Нью-Йорк: Springer. ISBN 0-387-95284-5. OCLC  46809224.
4. Эта схема является обобщением линейной интерполяции.
5. Jaskowiak, Pablo A.; Campello, Ricardo JGB (2011). «Сравнение коэффициентов корреляции как мер различия для классификации рака в данных по экспрессии генов». Бразильский симпозиум по биоинформатике (BSB 2011) : 1–8. CiteSeerX 10.1.1.208.993 . 
6. Coomans, Danny; Massart, Desire L. (1982). «Альтернативные правила k-ближайших соседей в контролируемом распознавании образов: Часть 1. Классификация k-ближайших соседей с использованием альтернативных правил голосования». Analytica Chimica Acta . 136 : 15–27. doi :10.1016/S0003-2670(01)95359-0.
7. Эверитт, Брайан С.; Ландау, Сабина; Лиз, Морвен; и Шталь, Дэниел (2011) «Различные методы кластеризации», в Кластерный анализ , 5-е издание, John Wiley & Sons, Ltd., Чичестер, Великобритания
8. Нигш, Флориан; Бендер, Андреас; ван Бюрен, Бернд; Тиссен, Йос; Нигш, Эдуард; Митчелл, Джон БО (2006). «Прогнозирование точки плавления с использованием алгоритмов k-ближайших соседей и оптимизации генетических параметров». Журнал химической информации и моделирования . 46 (6): 2412–2422. doi :10.1021/ci060149f. PMID  17125183.
9. Холл, Питер; Пак, Бёнг У.; Сэмворт, Ричард Дж. (2008). «Выбор порядка соседей в классификации ближайших соседей». Annals of Statistics . 36 (5): 2135–2152. arXiv : 0810.5276 . Bibcode : 2008arXiv0810.5276H. doi : 10.1214/07-AOS537. S2CID  14059866.
10. Стоун, Чарльз Дж. (1977). «Последовательная непараметрическая регрессия». Annals of Statistics . 5 (4): 595–620. doi : 10.1214/aos/1176343886 .
11. Сэмворт, Ричард Дж. (2012). «Оптимальные взвешенные классификаторы ближайшего соседа». Annals of Statistics . 40 (5): 2733–2763. arXiv : 1101.5783 . doi : 10.1214/12-AOS1049. S2CID  88511688.
12. Террелл, Джордж Р.; Скотт, Дэвид В. (1992). «Оценка плотности переменного ядра». Annals of Statistics . 20 (3): 1236–1265. doi : 10.1214/aos/1176348768 .
13. Миллс, Питер (2012-08-09). "Эффективная статистическая классификация спутниковых измерений". Международный журнал дистанционного зондирования .
14. Туссен, Годфрид Т. (апрель 2005 г.). «Геометрические графы близости для улучшения методов ближайшего соседа в обучении на основе экземпляров и добыче данных». Международный журнал вычислительной геометрии и приложений . 15 (2): 101–150. doi :10.1142/S0218195905001622.
15. Девройе, Л., Дьёрфи, Л. и Лугоши, Г. Вероятностная теория распознавания образов. Discrete Appl Math 73, 192–194 (1997).
16. Девройе, Люк; Дьёрфи, Ласло; Лугоши, Габор (1996). Вероятностная теория распознавания образов . Springer. ISBN 978-0-3879-4618-4.
17. Бейер, Кевин и др. «Когда имеет смысл термин «ближайший сосед»?» (PDF) . Теория баз данных — ICDT'99 . 1999 : 217–235.
18. Шоу, Блейк; Джебара, Тони (2009), «Встраивание с сохранением структуры» (PDF) , Труды 26-й ежегодной международной конференции по машинному обучению (опубликовано в июне 2009 г.), стр. 1–8, doi :10.1145/1553374.1553494, ISBN 9781605585161, S2CID  8522279
19. Бингем, Элла; Маннила, Хейкки (2001). «Случайная проекция в снижении размерности». Труды седьмой международной конференции ACM SIGKDD по обнаружению знаний и добыче данных - KDD '01 . стр. 245–250. doi :10.1145/502512.502546. ISBN 158113391X. S2CID  1854295.
20. Райан, Донна (редактор); High Performance Discovery in Time Series , Берлин: Springer, 2004, ISBN 0-387-00857-8 
21. Бремнер, Дэвид; Демейн, Эрик ; Эриксон, Джефф; Иаконо, Джон ; Лангерман, Стефан ; Морин, Пэт ; Туссен, Годфрид Т. (2005). «Чувствительные к выходу алгоритмы для вычисления границ решений ближайшего соседа». Дискретная и вычислительная геометрия . 33 (4): 593–604. doi : 10.1007/s00454-004-1152-0 .
22. Харт, Питер Э. (1968). «Правило сжатого ближайшего соседа». Труды IEEE по теории информации . 18 : 515–516. doi :10.1109/TIT.1968.1054155.
23. Mirkes, Евгений М.; KNN и потенциальная энергия: апплет, Университет Лестера, 2011
24. Рамасвами, Шридхар; Растоги, Раджив; Шим, Кьюсок (2000). "Эффективные алгоритмы для извлечения выбросов из больших наборов данных". Труды международной конференции ACM SIGMOD 2000 года по управлению данными - SIGMOD '00 . Труды международной конференции ACM SIGMOD 2000 года по управлению данными – SIGMOD '00. стр. 427–438. doi :10.1145/342009.335437. ISBN 1-58113-217-4.
25. Кампос, Гильерме О.; Зимек, Артур; Сандер, Йорг; Кампелло, Рикардо Дж. ГБ.; Миценкова, Барбора; Шуберт, Эрих; Ассен, Ира; Хоул, Майкл Э. (2016). «Об оценке неконтролируемого обнаружения выбросов: меры, наборы данных и эмпирическое исследование». Data Mining and Knowledge Discovery . 30 (4): 891–927. doi :10.1007/s10618-015-0444-8. ISSN  1384-5810. S2CID  1952214.

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

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