2.5. Алгоритм BIGFOR.
Иногда
встречаются такие большие таблицы данных, которые не умещаются целиком в оперативную
память и должны обрабатываться по частям. Для таксономии таких массивов
предназначен итеративный алгоритм BIGFOR.
Вначале
в оперативную память вводится массив из
объектов (
), который с помощью
алгоритма FOREL-2 делится
на
таксонов.
Описание таксона состоит из координат его центра и количества
его внутренних
точек («веса» центра). Это краткое описание запоминается в отведенном месте памяти.
Затем в память вводится следующая порция данных, с которой проделывается та же
процедура. После повторения этих шагов
раз, где
, получается массив из
точек, представляющих
собой центры таксонов, возникавших на каждом шаге. Группировка этих точек в
таксонов
делается с помощью варианта
алгоритма FOREL-2, который
при вычислении координат центра тяжести внутренних точек учитывает вес этих
точек. После нахождения центров
таксонов весь массив из то точек
перераспределяется между ними. При поочередном просмотре каждая точка относится
к тому таксону
,
расстояние до центра которого оказывается минимальным.
Если число исходных
объектов то слишком велико, процедура укрупнения таксонов может быть не двух-,
а многоступенчатой, скатывание таксонов во все более крупные «шарики» делается
несколько раз. Критерий качества таксономии, получаемой алгоритмом BIGFOR,
тот же, что и у алгоритма FOREL.