Анализ метода K ближайших соседей

Достоинства метода

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

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

Метод может применяться в онлайн-обучении (online machine learning), когда данные поступают динамическим потоком и быстро устаревают, например, при автоматической торговле на бирже. Для этого в качестве обучающей выборке нужно учитывать только те объекты, которые мы недавно пронаблюдали.

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

Недостатки метода

Для работы метода необходимо хранить все объекты обучающей выборки, поскольку все объекты по сути и составляют параметры метода.

Параметрические и непараметрические методы

Методы, в которых число параметров растёт с ростом объема выборки называются непараметрическими в противоположность параметрическим методам, в которых число параметров заранее фиксировано. Например распределение случайной величины мы можем моделировать Гауссовым распределением - тогда, с ростом выборки наблюдений, число параметров (среднее и матрица ковариации) будет оставаться прежним. Если же мы оцениваем распределение гистограммой, то, с ростом числа наблюдений, логично делать гистограмму более точной, увеличивая число столбцов гистограммы с ростом числа наблюдений. И этот метод становится уже непараметрическим.

Непараметрические методы не делают таких существенных предположений о распределении данных, как параметрические, поэтому обычно работают точнее, когда накоплено достаточное количество наблюдений.

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

Ускорение поиска ближайших соседей

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

• Можно ускорить вычисление расстояний между объектами, снизив число признаков.

• Можно уменьшить размер выборки, отобрав только эталонные объекты для каждого класса и существенные объекты на границах между классами, отбросив неинформативные.

• Можно упорядочить объекты по определённой структуре признакового пространства. Поиск похожих объектов вместо полного перебора тогда сведётся к направленному поиску по этой структуре (KD-trees, ball-trees либо направленный поиск по графу близости между объектами (proximity graph)).

• Можно использовать локально-чувствительное хэширование (locality sensitive hashing), при котором строится хэш-функция, отображающая метрически близкие объекты в одинаковые значения. Тогда, отобразив целевой объект в какое-то значение хэш-функции, можно сразу найти похожие объекты. Это будут объекты обучающей выборки, для которых хэш-функция приняла такое же значение.

Проклятие размерности

Также метод подвержен так называемому проклятию размерности (curse of dimensionality). Суть проклятия размерности заключается в том, что с ростом размерности признакового пространства $D$ для обеспечения определённого уровня точности методу необходим экспоненциальный рост числа наблюдений (относительно $D$). Если же рост числа наблюдений не происходит, то точность работы метода снижается. Пусть нам нужно построить прогноз для объекта $\mathbf{x}\in\mathbb{R}^D$. Поместим этот объект в центр двух вложенных друг в друга $D$-мерных кубов со сторонами $S$ и $S-\varepsilon$, где $\varepsilon$ - какая-то малая фиксированная константа, например 0.001. Тогда объем внутреннего куба будет $(S-\varepsilon)^D$, а объём внешнего - $S^D$. Отношение двух объёмов будет экспоненциально быстро стремиться к нулю с ростом $D$, и уже при небольшом значении $D$ будет пренебрежимо малым:

$$\frac{(S-\varepsilon)^D}{S^D}=\left(\frac{S-\varepsilon}{S}\right)^D \to 0 \text{ при } D\to\infty.$$

Это означает, что доля объема, покрываемого внутренним кубом от объема внешнего куба будет становиться пренебрежимо малой, а почти весь объем внешнего куба будет концентрироваться на его границе. Аналогичные рассуждения можно провести и для двух сфер вокруг целевого объекта - с ростом $D$ почти весь объем внешней сферы будет концентрироваться на её границе.

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

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

Не всё так плохо

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