6.3.3. Использование «локальных» метрик: исследование сходимости алгоритма ANATYP-B

Алгоритм ANATYP-B отличается от алгоритма ANATYP-A, описанного в 6.2.3, тем, что метрика, которой снабжено не является фиксированной, а на каждом шаге адаптируется к результатам проводимого анализа.

6.3.3.1. Обозначения и определения

множество метрик на

определяются так же, как в 6.2.1;

пространство центров агрегирования, элементами его являются пары, состоящие из некоторой метрики и -мерного аффинного многообразия;

или, иначе, пространство К-центров; отображение, позволяющее связать с каждым подмножеством А из метрику на обозначаемую также (алгоритм ANATYP-A можно рассматривать как частный случай, когда отображение постоянно); отображение, определенное для формулой

Если обозначить через момент инерции точки х относительно аффинного многообразия в метрическом пространстве то

— отображение, определенное для формулой

Если обозначить через остаточную инерцию относительно аффинного многообразия с распределением (полной массы 1 и связанным с в метрическом пространстве то

отображение, такое, что

отображение, такое, что

где и функция определяется как в 6.2.1, однако следует иметь в виду, что

Это означает, что если «расстояние» от него до в меньше, чем до

Пусть означает композицию двух отображений

где метрика, соответствующая А в силу отображения функция из алгоритма ANATYP-A, т. е. при заданной метрике отображение сопоставляет сгущению А аффинное -мерное многообразие натянутое на главные оси инерции этого сгущения в метрическом пространстве Будем обозначать также через отображение, которое каждому разбиению ставит в соответствие набор

Замечание. Если в предполагается, что зависят от то связаны центр тяжести сгущения — его «главное» подпространство инерции.)

6.3.3.2. Исследование алгоритма

Алгоритм ANATYP-B описывается с помощью функций по схеме из 6.2.3. Чтобы проследить за его ходом, изучим свойства последовательности определенной ниже. Для каждой итерации положим

где некоторое начальное разбиение.

Пусть последовательных элемента последовательности

где

Свойства последовательности

1. Преобразование является -свертываемым (см. [15]) и, следовательно, таким, что

если следовательно, если сходимость не достигнута, то мы имеем строгое неравенство

2. Преобразование относительно отображения обладает следующим свойством:

Даже если следовательно, обладает свойством

которое слабее, чем -свертываемость (см. [15]), поскольку не является, вообще говоря, центром агрегирования Тем не менее для из этого свойства вытекает

где последнее равенство является определением для Имеем

В силу свойств 1 и 2

(свойство инъективности (см. Напротив, ничего нельзя сказать о разности между моментами инерции сгущения относительно вычисленных в а затем в

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

На интуитивном уровне это можно объяснить следующим образом: в начале работы алгоритма первое улучшение критерия весьма велико и полностью компенсирует величину возможно, отрицательную. На итерациях же, близких к конечной стадии работы алгоритма, классы отличаются очень мало, поэтому метрики так же мало отличаются, и, следовательно, величина очень близка к нулю. Кроме того, в редких случаях, когда последовательность не убывала, срабатывали критерии остановки алгоритма (см. 6.2.3.3), так как либо относительная разность была меньше фиксированного порога, хотя отрицательна, либо после значения большего, чем предыдущее, значения критерия снова убывали.

Интерес к этому алгоритму объясняется в основном тем, что он позволяет проводить факторный анализ локальных соответствий для случаев, интересных с точки зрения приложений. Замечание.

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