Иерархическое группирование

Рис. 12. Результаты работы иерархической агломеративной процедуры группирования объектов, представленные в виде дендрограммы.

Классификационные процедуры иерархического типа предназначены для получения наглядного представления о стратификационной структуре всей исследуемой совокупности объектов. Эти процедуры основаны на последовательном объе­динении кластеров (агломеративные процедуры) и на последо­вательном разбиении (дивизимные процедуры). Наибольшее распространение получили агломеративные процедуры. Рас­смотрим последовательность операций в таких процедурах.

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

Различные варианты определения расстояния между кла­стерами дают различные варианты иерархических агломеративных процедур. Учитывая специфику подобных процедур, для задания расстояния между классами оказывается достаточным указать порядок пересчета расстояний между классом w_l и классом w(m, n) являющимся объединением двух других классов w_m и w_n по расстояниям q_mn = q(w_m, w_n) и q_ln = q(w_l, w_n) между этими классами. В литературе предлагается следующая общая формула для вычисления расстояния между некоторым классом w_l и классом w(m, n):

q_{l(m, n)} = q (w_l, w(m, n)) = aq_lm + bq_ln + gq_mn + d | q_lm - q_ln |

где a, b, g и d — числовые коэффициенты, определяющие на­целенность агломеративной процедуры на решение той или иной экстремальной задачи. В частности, полагая a = b = -d = ½ и g = 0, приходим к расстоянию, измеряемому по принципу ближайшего соседа. Если положить a = b = d = ½ и g = 0, то расстояние между двумя классами определится как расстояние между двумя самыми далекими объектами этих классов, то есть это будет расстояние дальнего соседа. И, наконец, выбор коэффициентов соотношения по формулам

приводит к расстоянию q_cp между классами, вычисленному как среднее расстояние между всеми парами объектов, один из ко­торых берется из одного класса, а другой из другого.

Использование следующей модификации формулы

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