Метод ближайшего соседа и его обобщения

Пусть на множестве объектов X задана функция расстояния

ρ: X×X → [0,∞).

Существует целевая зависимость y∗: X → Y, значения которой известны только на объектах обучающей выборки X^ℓ = (x_i,y_i)^ℓ_i=1, y_i = y∗(x_i). Множество классов Y конечно. Требуется построить алгоритм классификации a: X → Y, аппроксимирующий целевую зависимость y∗(x) на всём множестве X.

Обобщённый метрический классификатор

Для произвольного объекта u ∈ X расположим элементы обучающей выборки x¹,...,x^ℓ в порядке возрастания расстояний до u:

где через x⁽ⁱ⁾_u обозначается i-й сосед объекта u. Соответственно, ответ на i-м соседе объекта u есть y⁽ⁱ⁾_u = y∗(x⁽ⁱ⁾_u). Таким образом, любой объект u ∈ X порождает свою перенумерацию выборки.

Метрический алгоритм классификации с обучающей выборкой X^ℓ относит объект u к тому классу y ∈ Y, для которого суммарный вес ближайших обучающих объектов Гy(u,X^ℓ) максимален:

где весовая функция w(i,u) оценивает степень важности i-го соседа для классификации объекта u. Функция Γy(u,X^ℓ) называется оценкой близости объекта u к классу y.

Метрический классификатор определён с точностью до весовой функции w(i,u). Обычно она выбирается неотрицательной, не возрастающей по i. Это соответствует гипотезе компактности, согласно которой чем ближе объекты u и x⁽ⁱ⁾_u, тем выше шансы, что они принадлежат одному классу. Обучающая выборка Xℓ играет роль параметра алгоритма a. Настройка сводится к запоминанию выборки, и, возможно, оптимизации каких-то параметров весовой функции, однако сами объекты не подвергаются обработке и сохраняются «как есть». Алгоритм a(u;X^ℓ) строит локальную аппроксимацию выборки Xℓ, причём вычисления откладываются до момента, пока не станет известен объект u. По этой причине метрические алгоритмы относятся к методам ленивого обучения (lazy learning), в отличие от усердного обучения (eager learning), когда на этапе обучения строится функция, аппроксимирующая выборку. Метрические алгоритмы классификации относятся также к методам рассуждения по прецедентам (case-based reasoning, CBR). Здесь действительно можно говорить о «рассуждении», так как на вопрос «почему объект u был отнесён к классу y?» алгоритм может дать понятное экспертам объяснение: «потому, что имеются схожие с ним прецеденты класса y», и предъявить список этих прецедентов. Выбирая весовую функцию w(i,u), можно получать различные метрические классификаторы, которые подробно рассматриваются ниже.

Метод ближайших соседей

Алгоритм ближайшего соседа (nearest neighbor, NN) относит классифицируемый объект u ∈ X^ℓ к тому классу, которому принадлежит ближайший обучающий объект: w(i,u) = [i = 1]; a(u;X^ℓ) = y⁽¹⁾_u.

Этот алгоритм является, по всей видимости, самым простым классификатором. Обучение NN сводится к запоминанию выборки X^ℓ. Единственное достоинство этого алгоритма — простота реализации. Недостатков гораздо больше:

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

• Отсутствие параметров, которые можно было бы настраивать по выборке. Алгоритм полностью зависит от того, насколько удачно выбрана метрика ρ.

• В результате — низкое качество классификации.