Алгоритм отбора признаков

Если признаков слишком много, а расстояние вычисляется как сумма отклонений по отдельным признакам, то возникает проблема проклятия размерности. Суммы большого числа отклонений с большой вероятностью имеют очень близкие значения (согласно закону больших чисел). Получается, что в пространстве высокой размерности все объекты примерно одинаково далеки друг от друга; выбор k ближайших соседей становится практически произвольным.

Проблема решается путём отбора относительно небольшого числа информативных признаков (features selection).

В работе использован алгоритм жадного добавления признаков Add.

В алгоритме Add строится набор информативных призаков. Работа начинается с пустого множества. На каждом шаге добавяется новый признак, который при использовании с ранее выбранными минимизирует внешний критерий при числе признаков равном (в данной работе внешний критерий - это ). Если в течении шагов значение внешнего критерия не доставляло минимум внешнему критерию или добавлены все признаки, то алгоритм прекращает работу.

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