6.2.3. Алгоритм ANATYP-A

6.2.3.1. Описание

Итерационный процесс вызывает поочередно функции определенные в 6.2.1. Схематическое представление его в виде упрощенной блок-схемы приведено на рис. 6.1.

Последовательные этапы состоят в следующем:

1. Случайный розыгрыш или оценивание (исходя из возможной априорной информации о данных) разбиения множества на Ктлх классов.

2. Поиск -центров агрегирования разбиения (на итерации, Этап 2 состоит в вычислении для каждого класса центра тяжести и первых главных осей инерции т. е. в применении «функции»

3. Вычисление критерия для каждой пары Последовательность положительных вещественных чисел определенных для каждой итерации позволяет следить за ходом алгоритма.

В 6.2.3 доказано, что при некоторых условиях этот алгоритм сходится.

4. Проверяется, сошелся ли алгоритм (или, что то же, стабилизировалась ли последовательность

5. Вычисление «близостей» между классифицируемыми индивидуумами и К аффинными многообразиями, полученными на этапе 2. В результате получают таблицу «расстояний» размерности

Рис. 6.1 (см. скан)

6. Построение нового разбиения исходя из таблицы близостей, вычисленной на этапе 5, т. е. применение функции на итерации:

Замечание. Этапы 6, 2, 3, 4, 5 в указанном порядке составляют одну итерацию.

7. Останов происходит при достижении устойчивого элемента т. е. разбиения такого, что тогда имеем:

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

6.2.3.2. Сходимость алгоритма

Сходимость алгоритма равносильна сходимости последовательности положительных вещественных чисел: где разбиение, полученное на итерации, исходя из начального разбиения

В факторном типологическом анализе последовательность сходится убывая.

Доказательство аналогично доказательству из 1. 3. 6.

Более детальное изучение сходимости алгоритма и свойств преобразований в частном случае типологического факторного анализа можно найти в [15].

6.2.3.3. Процедуры остановки алгоритма

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

1. Проверяя относительное убывание критерия, останавливают итерационныи процесс, если где заданное малое число. Приходится предполагать выпуклость кривой убывания Выпуклость наблюдается на практике для последних итераций.

2. Проверяя устойчивость классов, используют понятие количества информации (доставляемого разбиением когда имеют разбиение которое будет уточнено в 6.4.5.1; останов происходит, когда это количество становится меньше заданного малого числа. В этом случае считают, что переход от к слишком мало модифицирует матрицы, по которым рассчитываются представительства классов.

3. Проверяя устойчивость полученных -мерных аффинных многообразий (критерий, используемый только в случае осей, т. е. вычисляют угол между осями, полученными для одного и того же класса на двух последовательных итерациях, и останавливаются, когда оси более не «поворачиваются».

Результаты критериев 2 и 3 являются, вообще говоря, согласованными, однако они не всегда проявляются одновременно, ибо удаление небольшого числа точек может изменить количество информации, а оси при этом не повернутся, что происходит в случае, когда точки близки к пересечению аффинных многообразий или имеют очень малую массу, и, обратно, устранение влияния удаленной точки или точки с большой

массой может изменить ось, но заметно не изменит количество информации.

Способ использования этих критериев уточняется в блок-схеме, риведенной на рис. 6.2.

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

Рис. 6.2

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