Основы проектирования систем искусственного интеллекта


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


Рис.  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, приходим к расстоянию, измеряемому по принципу ближайшего соседа.


- Начало -  - Назад -  - Вперед -