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

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

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

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

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

ql(m, n) = q (wl, w(m, n)) = aqlm + bqln + gqmn + d | qlm - qln |

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

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

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

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

 








Дата добавления: 2015-12-08; просмотров: 893;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.