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

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

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

К -ближайшему соседнему классификатору можно рассматривать как назначая K ближайших соседей веса и все остальные 0 веса. Это можно обобщить на взвешенные классификаторы ближайшего соседа. То есть, где i- му ближайшему соседу присваивается вес , с . Имеет место аналогичный результат о сильной согласованности взвешенных классификаторов ближайших соседей.

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

для констант и где и .

Оптимальная схема взвешивания , которая уравновешивает два члена на изображении выше, представлена ​​следующим образом: set ,

для и
для .

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

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

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

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

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

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

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

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

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

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

для некоторых констант и .

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

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

Эффективность классификации 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 примеров других классов.

Condensed Nearest Neighbor для сокращения данных

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

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

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

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

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

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

а ( х ) = | | х'-у | |/| | ху | |

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

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

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

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

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

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

k -NN выброс

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

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

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

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

использованная литература

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