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

Эта статья посвящена контролируемой классификации/регрессии, но НЕ алгоритму кластеризации. Алгоритмы поиска ближайших соседей см. в разделе Поиск ближайших соседей .

Не путать с кластеризацией k-средних .

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

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

классификатор

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

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

$${\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)\},$$

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

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

$$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]$$

для $i=1,2,\dots ,k^{*}$ и

$$w_{ni}^{*}=0$$

для $i=k^{*}+1,\dots ,n$.

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

Свойства

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

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

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

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

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

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

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

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

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

$${\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)\},$$

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

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

Обучение метрикам

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

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

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

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

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

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

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

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

Извлечение признаков и уменьшение размерности можно объединить за один этап с использованием методов анализа главных компонентов (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, Харта алгоритм ) — алгоритм, предназначенный для сокращения набора данных для классификации k -NN. Он выбирает набор прототипов U из обучающих данных, так что 1NN с U может классифицировать примеры почти так же точно, как 1NN делает это со всем набором данных.

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

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

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

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

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

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

а ( Икс ) = ‖ x'-y ‖ / ‖ xy ‖

где ‖ 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.

• Сокращение модели 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, тем ниже локальная плотность, тем больше вероятность, что точка запроса является выбросом. Несмотря на свою простоту, эта модель выбросов, наряду с другим классическим методом интеллектуального анализа данных, локальным фактором выбросов , работает довольно хорошо по сравнению с более поздними и более сложными подходами, согласно крупномасштабному экспериментальному анализу.

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

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

См. также

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

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

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