Учебное пособие для студентов магистерских программ москва Екатеринбург 014 удк ббк п

Иерархические процедуры кластер-анализа 
Иерархические процедуры подразделяются на агломеративные и 
дивизимные. 
Основной алгоритм иерархических процедур состоит в последо-
вательном объединении (разделении) групп элементов. В агломера-
тивных процедурах предполагается, что вначале каждый объект 
представляет собой отдельный кластер, и процесс заключается в объ-
единения отдельных объектов, а в дивизимных вся совокупность объ-
ектов вначале является единым кластером, и процесс заключается в 
разъединении объектов. 
В иерархических алгоритмах строится полное дерево вложен-
ных кластеров, при этом число кластеров самим алгоритмом не опре-
деляется. Определение числа кластеров должно проводиться иссле-
дователем на основе предположений, не относящихся к работе самого 
алгоритма: на основании порога слияния кластеров или исходя из со-
держательной сущности данных. 
Иерархические процедуры, по сравнению с другими кластер-
процедурами, дают более полный и тонкий анализ структуры иссле-
дуемых объектов и имеют наглядную интерпретацию в виде дендро-
граммы. Однако на каждом шаге иерархического алгоритма вычисля-
ется вся матрица расстояний, что требует больших вычислительных 
мощностей, поэтому алгоритмы применяются только для небольшого 
числа объектов (не более нескольких сотен). 
Примером иерархических алгоритмов являются следующие
47
: 
Агломеративный иерархический алгоритм «ближайшего сосе-
да»
(одиночной связи). В этом алгоритме матрица расстояний между 
кластерами определяется с помощью метода «ближайшего соседа». 
Первый шаг алгоритма состоит в выделении каждого объекта
Х
i
(
i
= 
1,2,...,
n
) в отдельный кластер. На втором шаге объединяются два са-
мых близких объекта (кластера) и по методу ближайшего соседа пе-
ресчитывается матрица расстояний, размерность которой понижается 
на 1. Процедура объединения кластеров и пересчета матрицы рас-
стояний продолжается до тех пор, пока все исходные объекты не бу-
дут объединены в один класс. Так как в этом алгоритме расстояние 
47
Айвазян С.А., Мхиатрян В.С. Прикладная статистика и основы эконометрики. Учебник для вузов. – 
М.:ЮНИТИ, 1998. – 1022 с. 

---

175 
между любыми двумя кластерами равно расстоянию между двумя 
самыми близкими элементами, из разных кластеров, то получаемые в 
итоге кластеры могут иметь сложную форму, в частности, может воз-
никнуть так называемый «цепочечный эффект», когда форма класте-
ра не является выпуклой и объекты представляют собой цепочку. 
Для устранения цепочечного эффекта при образовании класте-
ров в алгоритме ближайшего соседа может быть введено ограничение 
на максимальное расстояние между элементами одного кластера. За-
дается порог, определяющий это расстояние, и, если при образовании 
кластеров расстояние между некоторыми объектами превысит этот 
порог, то такие объекты разносятся в разные кластеры. 
Агломеративные иерархические алгоритмы «средней связи» и 
«полной связи»
. В этих алгоритмах по сравнению с первым изменяет-
ся лишь метод вычисления расстояния между объектами. В методе 
средней связи расстояние между кластерами рассчитывается как 
среднее из расстояний между всевозможными парами объектов, при-
надлежащих разным кластерам. Метод полной связи («дальнего со-
седа») определяет расстояние между двумя кластерами как расстоя-
ние между двумя самыми удаленными объектами, принадлежащими 
разным кластерам.
Иерархические процедуры, использующие последовательность 
порогов.
В схеме таких процедур дополнительно задается последова-
тельность порогов 
с
1
, с
2
,…,с
t
. На первом шаге алгоритма происходит 
попарное объединение объектов, удаленных друг от друга не более 
чем на величину 
с
1
. На втором шаге алгоритма объединяются объек-
ты или уже образованные кластеры, расстояние между которыми не 
превосходит 
с
2
и т. д. Эффективность таких процедур и возможность 
выбора подходящих пороговых значений непосредственно связаны с 
геометрической структурой изучаемого множества объектов.
Иерархические методы дают полную картину объединения объ-
ектов в кластеры, однако они достаточно трудоёмки: на каждом шаге 
алгоритма необходимо рассчитывать матрицу расстояний для всех 
текущих кластеров. Время расчета в иерархических алгоритмах рас-
тёт пропорционально третьей степени от числа объектов в исходных 
данных.
Параллельные кластер-процедуры 
В параллельных процедурах на каждом шаге алгоритма произ-
водится одновременный расчет для всех исходных объектов, поэтому 

---

176 
задача кластеризации решается с помощью перебора различных ва-
риантов разбиения. Однако уже для нескольких десятков классифи-
цируемых объектов полный перебор всех вариантов разбиения прак-
тически невозможен. Поэтому в различных параллельных алгоритмах 
кластеризации используются те или иные методы сокращения числа 
рассматриваемых вариантов. 
В качестве примера рассмотрим схему алгоритмов «последова-
тельного переноса точек из класса в класс». В этих алгоритмах ис-
пользуется некоторое начальное разбиение объектов на кластеры, ко-
торое может быть выбрано произвольно или получено с помощью 
предварительной обработки исходных наблюдений. Для данного раз-
биения производится вычисление выбранного критерия качества раз-
биения Q. После этого каждый объект, рассматриваемый как само-
стоятельный кластер, поочередно помещается во все имеющиеся на 
данный момент кластеры. Для каждого такого перемещения рассчи-
тывается функционал качества Q, и объект закрепляется за тем кла-
стером, для которого значение функционала качества является наи-
лучшим. Работа алгоритма продолжается до тех пор, пока перемеще-
ния объектов не перестанут приводить к повышению качества раз-
биения. Подобную процедуру можно применять несколько раз для 
одной и той же исходной совокупности объектов с различными на-
чальными разбиениями, что позволяет выбрать наилучшие качество 
разбиения на кластеры. 
Последовательные кластер-процедуры 
Как было указано выше, при большом числе объектов (от не-
скольких сотен) трудоемкость и вычислительное время иерархиче-
ских и параллельных процедур резко возрастает. Для больших масси-
вов данных используются последовательные процедуры, в которых 
на каждом шаге итерации производится последовательный обсчет 
только небольшой части исходных объектов.
Наиболее общей последовательной кластер-процедурой являет-
ся 
метод k-средних (K-meansclustering)
. В этом методе на основании 
некоторых внешних предположений или проведенного предвари-
тельного анализа задается число кластеров, на которые должны быть