Введение

Непараметрический метод классификации, контролируемое обучение с учителем (классификация/регрессия), но НЕ алгоритм кластеризации.

В статистике алгоритм k ближайших соседей (k NN) является непараметрическим методом обучения с учителем, впервые разработанным Эвелин Фикс и Джозефом Ходжесом в 1951 году, а позднее расширенным Томасом Коувером. Как для классификации, так и для регрессии, полезной техникой может быть присвоение весов вкладу соседей, так чтобы более близкие соседи вносили больший вклад в среднее значение, чем более удалённые. Например, распространённая схема взвешивания заключается в присвоении каждому соседу веса, равного 1/d, где d – расстояние до этого соседа. Соседи выбираются из набора объектов, для которых известен класс (в случае k NN классификации) или значение свойства объекта (в случае k NN регрессии). Это можно рассматривать как обучающий набор данных для алгоритма, хотя явный этап обучения не требуется. Особенность алгоритма k NN заключается в его чувствительности к локальной структуре данных.

Статистическая структура

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

Алгоритм

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

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

Лучший выбор k зависит от данных; как правило, большие значения k уменьшают влияние шума на классификацию, но делают границы между классами менее выраженными. Хороший k можно выбрать с помощью различных эвристических методов (см. оптимизацию гиперпараметров). Особый случай, когда класс предсказывается как класс ближайшего образца обучения (т.е. когда k = 1), называется алгоритмом ближайших соседей. Точность алгоритма k NN может существенно снижаться из-за наличия зашумленных или нерелевантных признаков, или если масштабы признаков не соответствуют их значимости. Значительные исследовательские усилия были направлены на выбор или масштабирование признаков для повышения точности классификации. Особенно популярным подходом является использование эволюционных алгоритмов для оптимизации масштабирования признаков. Другой популярный подход – масштабирование признаков на основе взаимной информации между данными обучения и классами обучения. В задачах бинарной (двухклассовой) классификации полезно выбирать k нечетным числом, чтобы избежать ничьих при голосовании. Один из распространенных способов выбора эмпирически оптимального k в этом случае – метод бутстрэпа.

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

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

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

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

для некоторых констант и .
Выбор предлагает компромисс между двумя слагаемыми в приведенном выше выражении, при котором ошибка k-го ближайшего соседа сходится к ошибке Байеса с оптимальной (минимаксной) скоростью .

Учебный процесс

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

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

Для данных с высокой размерностью (например, при числе измерений больше 10) обычно выполняется понижение размерности перед применением алгоритма k NN, чтобы избежать эффектов "проклятия размерности". "Проклятие размерности" в контексте k NN по сути означает, что евклидово расстояние становится неинформативным в высоких размерностях, поскольку все векторы оказываются почти равноудалёнными от вектора запроса (представьте множество точек, расположенных примерно на окружности, с точкой запроса в центре; расстояние от запроса до всех точек данных в пространстве поиска почти одинаково). Выделение признаков и понижение размерности можно объединить в один этап, используя методы анализа главных компонент (PCA), линейного дискриминантного анализа (LDA) или канонического корреляционного анализа (CCA) в качестве этапа предварительной обработки, за которым следует кластеризация с помощью k NN на векторах признаков в пространстве пониженной размерности. Этот процесс также называют низкоразмерным вложением. Для очень высокоразмерных наборов данных (например, при выполнении поиска схожести по потоковому видео, данным ДНК или высокоразмерным временным рядам) единственным практически реализуемым вариантом может быть быстрый приближённый поиск k NN с использованием локально-чувствительного хеширования, "случайных проекций", "эскизов" или других методов поиска схожести в высоких размерностях из набора инструментов VLDB.

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

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

Валидация результатов

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