Постановка задачи. Пусть - множество объектов; - множество допустимых ответов

Пусть - множество объектов; - множество допустимых ответов. Задана обучающая выборка . Задано множество объектов .

Требуется найти множество ответов для объектов .

Алгоритм взвешенных ближайших соседей

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

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

где через обозначается тот объект обучающей выборки, который является -м соседом объекта . Аналогичное обозначение введём и для ответа на -м соседе: .

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

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