10.4. Исследование сходимости алгоритмов АК

Определение 10.7. Модель ААК называется корректной, если

1) для данных оператор К меняет состояние только подмножества , причем это изменение полностью определяется описанием

2) существует интерпретирующий функционал F, ограниченный снизу на данном движении алгоритма, такой, что для любого существует что, как только то (см. определение 10.5).

Далее, говоря об интерпретирующем функционале F корректной модели, всегда будем подразумевать, что он удовлетворяет условию 2 определения 10.7.

Лемма 10.1. Пусть F — интерпретирующий функционал корректной модели . Тогда из равенства следует, что для всех

Оказывается, что для большого класса ААК верно и обратное утверждение.

Лемма 10.2. Если множество значений интерпретирующего функционала F конечно, то в модели ААК условие 2 определения 10.7 выполняется тогда и только тогда, когда из для следует, что

Теорема 10.1. Если множество значений интерпретирующего функционала F корректной модели ААК конечно, то в движении этого алгоритма последовательность описаний стабилизируется, т. е. существует такое что для всех

Доказательство предыдущих результатов использует только свойство 2 определения 10.7. Следующий результат показывает роль свойства 1.

Теорема 10.2.

Если в движении алгоритма, описываемого корректной моделью, последовательность описаний стабилизируется начиная с номера то соответствующая последовательность состояний задает стабилизирующуюся классификацию выборки О, т. е. как только для , то для всех

В случае когда оператор D не зависит от первого аргумента, т. е. задается отображением (это имеет место во многих алгоритмах, например во всех алгоритмах МДС (см. § 7.4)), то из конечности множества и теорем 10.1 и 10.2 следует стабилизируемость движений алгоритмов, описываемых такими корректными моделями. Следующий результат лежит в основе исследования сходимости алгоритмов последовательного типа, описываемых корректной моделью для бесконечных выборок (ср. [139]).

Лемма 10.3. Пусть — движение алгоритма, описываемого некоторой корректной моделью. Тогда для любого и натурального N существует номер такой, что для всех .

Определение 10.8. Модель ААК называется усиленно корректной, если:

1) оператор К удовлетворяет условию 1 определения 10.7;

2) существует интерпретирующий на данном движении алгоритма ограниченный снизу функционал F и строго монотонно возрастающая функция причем такие, что как только то

Нетрудно проверить, что усиленно корректная модель является корректной.

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

(10.23)

где

Пример 10.10. Рассмотрим интерпретирующий функционал

в модели алгоритма -средних. Тогда из (10.23) получаем

Так как для всех q, то получаем, что модель алгоритма -средних является усиленно корректной.

Аналогично проверяется, что и модель алгоритма средних является корректной для любого .

Применяя теперь теорему 10.1, получаем, что движение алгоритма -средних стабилизируется.

Пример 10.11. Пусть — невозрастающая функция, являющаяся параметром модели алгоритма выделения размытого кластера (см. п. 10.3.4). Для каждого натурального числа N введем новую функцию где символ операции взятия целой части числа. Из свойств операции следует, что для всех

Теорема 10.3. Допустим, что у для всех Тогда движение алгоритма выделения размытого кластера с параметром стабилизируется для всех [42].

В заключение приведем результат, который служит основой для построения новых усиленно корректных моделей ААК.

Лемма 10.4. Пусть заданы следующие компоненты структуры модели ААК: и некоторый ограниченный снизу функционал такой, что . Тогда для любой строго монотонной функции существует оператор вместе с которым данные компоненты образуют усиленно корректную модель ААК.

Требуемый оператор действует по формуле: