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

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

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

• В регрессии k-NN выходом является значение свойства объекта. Это значение является средним из значений k ближайших соседей.

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

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

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

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

Статистическая установка [ править ]

Предположим, у нас есть пары, принимающие значения в , где Y - метка класса X , так что for (и распределения вероятностей ). Учитывая некоторую норму на и точку , пусть будет переназначения обучающих данных , таких , что .${\ 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 х \ в \ mathbb {R} ^ {d}}$${\ displaystyle (X _ {(1)}, Y _ {(1)}), \ точки, (X _ {(n)}, Y _ {(n)})}$${\ Displaystyle \ | Икс _ {(1)} - х \ | \ Leq \ точки \ Leq \ | X _ {(n)} - х \ |}$

Алгоритм [ править ]

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

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

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

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

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

Выбор параметра [ править ]

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

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

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

1 -ближайший сосед классификатор [ править ]

Самый интуитивно понятный классификатор типа ближайшего соседа - это классификатор одного ближайшего соседа, который присваивает точку x классу своего ближайшего соседа в пространстве признаков, то есть .${\ Displaystyle C_ {п} ^ {1nn} (х) = Y _ {(1)}}$

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

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

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

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

${\ displaystyle {\ mathcal {R}} _ {\ mathcal {R}} (C_ {n} ^ {wnn}) - {\ mathcal {R}} _ {\ mathcal {R}} (C ^ {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}\{i^{1+2/d}-(i-1)^{1+2/d}\}}$

Оптимальная схема взвешивания , которая уравновешивает два члена на изображении выше, представлена ​​следующим образом: set , ${\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 - это частный случай "баллонной" оценки плотности ядра с переменной полосой пропускания и однородным ядром . ^{[13] [14]}

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

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

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

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

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

Частота ошибок [ править ]

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

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

${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{knn})-{\mathcal {R}}_{\mathcal {R}}(C^{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^{*}=\lfloor Bn^{\frac {4}{d+4}}\rfloor }$${\displaystyle k^{*}}$${\displaystyle {\mathcal {O}}(n^{-{\frac {4}{d+4}}})}$

Метрическое обучение [ править ]

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

Извлечение функций [ править ]

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

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

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

Уменьшение размеров [ править ]

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

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

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

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

Граница решения [ править ]

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

Обработка данных [ править ]

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

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

Выбор классов-выбросов [ править ]

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

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

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

CNN для сокращения данных [ править ]

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

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

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

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

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

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

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

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

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

• Редукция модели CNN для классификаторов k-NN
• Рис. 1. Набор данных.

• Рис. 2. Карта классификации 1NN.

• Рис. 3. Классификационная карта 5NN.

• Рис. 4. Сокращенный набор данных CNN.

• Рис. 5. Карта классификации 1NN на основе извлеченных прототипов CNN.

k -NN регрессия [ править ]

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

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

k -NN выброс [ править ]

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

Проверка результатов [ править ]

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

См. Также [ править ]

• Классификатор ближайшего центроида
• Проблема ближайшей пары точек

Ссылки [ править ]

Дальнейшее чтение [ править ]

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