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