7. Модель алгоритма (дельта(1)-r)-средних для весовых функций Беждека и Данна
Спускаясь вниз по уровням иерархии от модели 6, получаем:
изолированная 
-конус над 
— часть множества линейных отображений 
состоящая из всех отображений, при которых вершина 
переходит в точку
где
Рассмотрим теперь в рамках нашего подхода вопросы сходимости 
Мы выделим два класса моделей 
и приведем результаты их математического исследования, дающие возможность единообразно доказать сходимость широкого класса 
Определение 
называется сходящимся, если в его движении 
-последовательность описаний 
сходится в метрике пространства 
к некоторому предельному описанию
Подчеркнем, что метрика в 
индуцированная, как правило, метрикой в 
(например, евклидовой метрикой в 
когда 
является важным параметром при настройке математической модели 
на специфику решаемой задачи.
Определение 5. Модель 
называется корректной, если: 
Для данных 
оператор 
меняет состояние только подмножества 
а 
причем это изменение полностью определяется описанием 
существует интерпретирующий функционал ограниченный снизу на данном движении алгоритма, такой, что для любого 
и по существует величина 
такая, что как только 
то 
(см. определение 3).
Далее, говоря об интерпретирующем функционале 
корректной Додели, мы всегда будем подразумевать, что он удовлетворяет условию 
определения 5.
Лемма 1. Пусть 
интерпретирующий функционал корректной Додели 
Тогда из равенства 
следует, 
для всех 
гц.
Оказывается, что для большого класса 
верно и обратное утверждение.
Лемма 2. Если множество значений интерпретирующего функционала 
конечно, то в модели 
условие 
определения 5 выполняется тогда и только тогда, когда из 
для 
следует, что 
Теорема 1. Если множество значений интерпретирующего функционала 
корректной модели 
конечно, то в движении этого алгоритма последовательность описаний 
стабилизируется, т. е. существует такое 
что 
для всех 
Доказательство предыдущих результатов использует только свойство 
Следующий результат показывает роль свойства 
Теорема 2. Если в движении алгоритма, описываемого корректной моделью, последовательность описаний 
стабилизируется, начиная с номера 
то соответствующая последовательность состояний 
задает стабилизирующуюся классификацию выборки т. е. как только 
для 
для всех 
Отметим, что небольшое отклонение от стандартного вида формул (1) — (3) для классификатора 
отвечающего функционалу 
вызвано как раз желанием получить оператор обладающий свойством 
Внимательный читатель, несомненно, обратит внимание на то, что в основном тексте авторы книги задают оператор 
в стандартном виде, а в комментариях к ряду конкретных алгоритмов указывают, что для стабилизируемости последовательности классификаций необходима его соответствующая модификация.
В случае когда оператор 3) не зависит от первого аргумента, т. е. задается отображением 
(это имеет место во всех алгоритмах 
из конечности множества 
и теорем 1 и 2 следует стабилизируемость движений алгоритмов, описываемых такими корректными моделями. Следующий результат лежит в основе исследования сходимости алгоритмов последовательного типа, описываемых корректной моделью для бесконечных выборок (ср. [18]).
Лемма 3. Пусть 
-движение алгоритма, описываемого некоторой корректной моделью. Тогда для любого 
натурального 
существует номер 
такой, что 
для всех 
Определение 6. Модель 
называется усиленно корректной, если: 
оператор 
удовлетворяет условию 
определения 5; 
существует интерпретирующий на данном движении алгоритма ограниченный снизу функционал 
и строго монотонно возрастающая функция 
причем 
такие, что как только 
то
Нетрудно проверить, что усиленно корректная модель является корректной. Обратим внимание, что из тождества Гюйгенса, которое
имеет место для большинства критериев качества классификации, используемых в книге, вытекает, что соответствующие алгоритмы МДС описываются усиленно корректными моделями.
В ряде случаев оказывается, что и не нужно прибегать к общей математической теории сходимости, а достаточно воспользоваться просто иерархической структурой многообразия всех 
Например, взяв за основу очень элементарное доказательство стабилизируемости движения алгоритма 
-средних (см. гл. 1 книги), мы, используя описанный выше «подъем» модели этого алгоритма до алгоритма 
-средних, непосредственно получаем стабилизируемость движения алгоритма 
-средних, а спускаясь вниз к модели 
-средних, получаем элементарное доказательство стабилизируемости движения алгоритма «Форель». Отметим, что впервые этот результат был получен более сложным способом в [8].
С. А. АЙВАЗЯН, В. М. БУХШТАБЕР
ЛИТЕРАТУРА
(см. скан)
