З.Н. Русакова, А.В. Орел
8
Описание итерационного алгоритма:
просматривается горизонтальный список элементов. Текущему
элементу (назовем его родительским) назначается номер кластера. Для
рассматриваемого родительского элемента просматривается верти-
кальный список ближайших элементов, которые назовем дочерними;
на каждом шаге цикла просмотра из вертикального списка ло-
кального сгущения выбирается текущий элемент — дочерний для
родительского, и для него формируется кластер. Этому выбранному
элементу назначается заданный номер родительского кластера, т. е.
элемент помещается в кластер родительского элемента. Этот же но-
мер кластера должен быть назначен элементу с таким же номером
элемента (или именем точки) в горизонтальном списке и его бли-
жайшим элементам, записанным в его вертикальном списке.
В результате осуществляется агрегирование данных: слияние ло-
кальных сгущений дочерних элементов с родительскими, для чего бли-
жайшие элементы дочернего подключаются (переносятся) в список
ближайших соседей родительского элемента верхнего уровня.
При подключении списков необходимо определить пересечение
элементов рассматриваемого подключаемого дочернего списка бли-
жайших и списка элементов родительского формируемого кластера и
исключить элементы пересечения: т. е. элементы, уже входящие в
список ближайших, не добавляются в формируемый кластер. После
подключения новых элементов списка к кластеру рассматриваемый
дочерний элемент горизонтального списка и его вертикальный спи-
сок ближайших удаляются. Если элементы списка локального сгуще-
ния уже включены в список родительского списка, он сам удаляется
из горизонтального списка без подключения.
Такая процедура выполняется для всех элементов формируемого
кластера. Далее выбирается следующий элемент из списка форми-
руемого кластера. По его номеру выполняется поиск в горизонталь-
ном списке и к формируемому кластеру добавляются новые точки из
его дочернего списка ближайших элементов, после чего элемент из
горизонтального списка и сам список удаляются.
Процедура формирования кластера заканчивается после исчерпа-
ния списка просматриваемых точек кластера. При этом необходим
определенный порядок выбора и записи элементов в список кластера.
Реализуется вариант: запись новых в хвост списка формируемого
кластера, выбор элемента для поиска новых ближайших из головы.
Список формируемого кластера после определенного числа итерации
подключений практически не пополняется, так как все элементы
уже вошли в кластер, что означает окончание итеративной процеду-
ры формирования кластера.
После выхода из цикла по списку ближайших соседей для роди-
тельского списка на текущем шаге формируется кластер. Формализо-
