Метод ближайшего соседа: пример работы

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

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

Гипотеза метода

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

Специфика методики ближайших соседей

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

Методика взвешенных соседей

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

Гипотеза компактности

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

Основная формула

Разберем подробнее метод ближайшего соседа. Если предложена обучающая выборка вида «объект-ответ» X^m = {(x_1,y_1),dots,(x_m,y_m)}- если для множества объектов задают функцию расстояния rho(x,x`), которая представлена в виде адекватной модели сходства объектов, при увеличении значения данной функции понижается сходство между объектами x, x`.

Для любого объекта u выстроим объекты обучающей выборки x_i по мере возрастания расстояний до u:

rho(u,x_{1- u}) leq rho(u,x_{2- u}) leq cdots leq rho(u,x_{m- u}),

где x_{i- u} характеризует объект обучающей выборки, являющийся i-м соседом исходного объекта u. Подобное обозначение используем и для ответа на i-м соседе: y_{i- u}. В итоге получаем, что произвольный объект u провоцирует изменение нумерации собственной выборки.

Определение числа соседей k

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

Если взять k = m, алгоритм будет максимально устойчивым и выродится в постоянную величину. Именно поэтому для достоверности важно не допускать крайних показателей k.

На практике в качестве оптимального показателя k применяют критерий скользящего контроля.

Отсев выбросов

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

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

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

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

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

Применение сверхбольших выборок

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

Для того чтобы справиться с поставленной задачей, применяют два способа:

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

Правила подбора методики

Выше была рассмотрена классификация. Метод ближайшего соседа применяют при решении практических задач, в которых известна заранее функция расстояния rho(x,x`). При описании объектов числовыми векторами используют евклидову метрику. Подобный выбор не имеет специального обоснования, но подразумевает измерение всех признаков «в едином масштабе». Если не учесть данный фактор, то в метрике будет преобладать признак, имеющий наибольшие числовые значения.

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

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

Заключение

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

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

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