6.2.4. Модифицированное правило k ближайших соседей.

Недостаток решающего правила k ближайших соседей заключается в необходимости помнить все объекты и сравнивать неизвестный объект со всеми этими объектами. Этот недостаток был бы не таким существенным, если бы удалось исключить часть из этих объектов, оставив лишь сравнительно небольшое число представителей. Объекты, находящиеся вблизи границы байесовского решающего правила, сильно влияют на результат применения метода k ближайших соседей, но объекты, далекие от границы, не влияют на решение. Поэтому систематическое исключение этих «невлияющих» объектов позволяет уменьшить как время вычислений, так и требования к памяти. Соответствующая процедура получила название модифицированного правила k ближайших соседей [Харт, 1968].

Для простоты приведем метод исключения невлияющих объектов в случае (т. е. для правила ближайшего соседа). Метод можно легко модифицировать для общего случая. В приведенном ниже описании метода слова ПАМЯТЬ и ОТСЕВ являются идентификаторами двух разных массивов памяти.

1. Первый объект заносится в ПАМЯТЬ.

2. Каждый следующий объект классифицируется с помощыо правила ближайшего соседа; при этом используются только те объекты, которые находятся в массиве ПАМЯТЬ. Если классификация произведена правильно, объект выбрасывают в ОТСЕВ. Если объект классифицирован неправильно, его заносят в ПАМЯТЬ.

3. Эта процедура повторяется, пока не будут просмотрены все N объектов.

4. После того как все объекты просмотрены, спова применяют описанную выше процедуру, но лишь к объектам, находящимся в массиве ОТСЕВ, и повторяют ее до тех пор, пока не оказывается, что в процессе просмотра ни один из объектов не переходит из массива ОТСЕВ в массив ПАМЯТЬ.

В работе [Харт, 1968] приведены два примера, иллюстрирующие эффективность описанного выше метода.

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

2. Множество из 6295 машинописных символов (25 классов в -мерном пространстве) после четырех итераций было представлено 197 объектами.