алгоритм 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 использовался с коэффициентами корреляции, такими как Пирсон и Спирмен, в качестве метрики. ^[5] Часто точность классификации k -NN можно значительно повысить, если метрику расстояния изучить с помощью специализированных алгоритмов, таких как анализ ближайших соседей с большим запасом или анализ компонентов окрестности .

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

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

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

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

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

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

Самый интуитивно понятный классификатор типа ближайшего соседа — это один классификатор ближайшего соседа, который присваивает точку 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\}}$

Оптимальная схема взвешивания , которая уравновешивает два термина на изображении выше, задается следующим образом: set , for и for . ${\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.

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

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

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

k -NN выброс

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

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

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

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

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

• Классификатор ближайшего центроида
• Задача о ближайшей паре точек
• Граф ближайших соседей

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

1. Фикс, Эвелин; Ходжес, Джозеф Л. (1951). Дискриминационный анализ. Непараметрическая дискриминация: свойства согласованности (PDF) (отчет). Школа авиационной медицины ВВС США, Рэндольф Филд, Техас. Архивировано (PDF) из оригинала 26 сентября 2020 г.
2. Cover, Томас М .; Харт, Питер Э. (1967). «Классификация шаблонов ближайших соседей» (PDF) . Транзакции IEEE по теории информации . 13 (1): 21–27. CiteSeerX 10.1.1.68.2616 . дои : 10.1109/TIT.1967.1053964. S2CID  5246200. 
3. Хасти, Тревор. (2001). Элементы статистического обучения: интеллектуальный анализ данных, логические выводы и прогнозирование: с 200 полноцветными иллюстрациями . Тибширани, Роберт, Фридман, Дж. Х. (Джером Х.). Нью-Йорк: Спрингер. ISBN 0-387-95284-5. ОСЛК  46809224.
4. Эта схема является обобщением линейной интерполяции.
5. Ясковяк, Пабло А.; Кампелло, Рикардо JGB (2011). «Сравнение коэффициентов корреляции как меры различия для классификации рака в данных об экспрессии генов». Бразильский симпозиум по биоинформатике (BSB 2011) : 1–8. CiteSeerX 10.1.1.208.993 . 
6. Куманс, Дэнни; Массарт, Желание Л. (1982). «Альтернативные правила k-ближайших соседей в контролируемом распознавании образов: Часть 1. Классификация k-ближайших соседей с использованием альтернативных правил голосования». Аналитика Химика Акта . 136 : 15–27. дои : 10.1016/S0003-2670(01)95359-0.
7. Эверитт, Брайан С.; Ландау, Сабина; Лиз, Морвен; и Шталь, Дэниел (2011) «Различные методы кластеризации», в «Кластерном анализе» , 5-е издание, John Wiley & Sons, Ltd., Чичестер, Великобритания.
8. Нигш, Флориан; Бендер, Андреас; ван Бюрен, Бернд; Тиссен, Джос; Нигш, Эдуард; Митчелл, Джон Б.О. (2006). «Прогнозирование температуры плавления с использованием алгоритмов k-ближайших соседей и оптимизации генетических параметров». Журнал химической информации и моделирования . 46 (6): 2412–2422. дои : 10.1021/ci060149f. ПМИД  17125183.
9. Холл, Питер; Пак, Бён У.; Сэмворт, Ричард Дж. (2008). «Выбор порядка соседей в классификации ближайших соседей». Анналы статистики . 36 (5): 2135–2152. arXiv : 0810.5276 . Бибкод : 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. Миллс, Питер (9 августа 2012 г.). «Эффективная статистическая классификация спутниковых измерений». Международный журнал дистанционного зондирования .
14. Туссен, Годфрид Т. (апрель 2005 г.). «Геометрические графы близости для улучшения методов ближайшего соседа в обучении на основе экземпляров и интеллектуальном анализе данных». Международный журнал вычислительной геометрии и приложений . 15 (2): 101–150. дои : 10.1142/S0218195905001622.
15. Деврой Л., Дьерфи Л. и Лугоши Г. Вероятностная теория распознавания образов. Дискретная прикладная математика 73, 192–194 (1997).
16. Деврой, Люк; Дьёрфи, Ласло; Лугоши, Габор (1996). Вероятностная теория распознавания образов . Спрингер. 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. дои : 10.1145/502512.502546. ISBN 158113391X. S2CID  1854295.
20. Райан, Донна (редактор); Открытие высокой производительности во временных рядах , Берлин: Springer, 2004, ISBN 0-387-00857-8 
21. Бремнер, Дэвид; Демейн, Эрик ; Эриксон, Джефф; Яконо, Джон ; Лангерман, Стефан ; Морен, Пэт ; Туссен, Годфрид Т. (2005). «Алгоритмы, чувствительные к выходу, для вычисления границ решения ближайшего соседа». Дискретная и вычислительная геометрия . 33 (4): 593–604. дои : 10.1007/s00454-004-1152-0 .
22. Харт, Питер Э. (1968). «Сокращенное правило ближайшего соседа». Транзакции IEEE по теории информации . 18 : 515–516. дои : 10.1109/TIT.1968.1054155.
23. Миркес, Евгений М.; KNN и потенциальная энергия: апплет, Лестерский университет, 2011 г.
24. Рамасвами, Шридхар; Растоги, Раджив; Шим, Кюсок (2000). «Эффективные алгоритмы выявления выбросов из больших наборов данных». Материалы международной конференции ACM SIGMOD 2000 г. по управлению данными - SIGMOD '00 . Материалы международной конференции ACM SIGMOD 2000 г. по управлению данными - SIGMOD '00. стр. 427–438. дои : 10.1145/342009.335437. ISBN 1-58113-217-4.
25. Кампос, Гильерме О.; Зимек, Артур; Сандер, Йорг; Кампелло, Рикардо Дж.Г.Б.; Миценкова, Барбора; Шуберт, Эрих; Согласен, Ира; Хоул, Майкл Э. (2016). «Об оценке неконтролируемого обнаружения выбросов: меры, наборы данных и эмпирическое исследование». Интеллектуальный анализ данных и обнаружение знаний . 30 (4): 891–927. дои : 10.1007/s10618-015-0444-8. ISSN  1384-5810. S2CID  1952214.

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

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