§ 4. Иерархические структуры

В последнее время в области анализа данных отмечается рост интереса к анализу так называемых символьных объектов [50], с помощью которых описываются разного рода обобщенные характеристики некоторого массива исходных данных. Символьным объектом может быть обнаруженная в этом массиве логическая закономерность типа «если ... то ...», направленный граф, отражающий зависимость одних объектов от других и т. п. В частности, результаты иерархической таксономии выявляют структуру множества объектов, которую можно наглядно представить графически в виде иерархического дерева, начальные вершины (листья) которого отображают все объекты исходного множества, промежуточные вершины (ветви) описывают все более крупные таксоны (концепты), а конечная вершина (корень) представляет собой объединение всего исходного множества объектов в один таксон. Такую форму могут иметь, например, описания структур баз данных, технических систем, организационных структур предприятий. При изучении нескольких различных массивов данных может потребоваться сравнение между собой их внутренних структур, что приводит к необходимости измерять степень близости, похожести между иерархическими структурами.

В работах [76,78] и предыдущей главе описаны методы анализа символьных объектов, имеющих форму конъюнкций типа «если ... то ...». Данная работа посвящена введению меры близости или расстояния на множестве символьных объектов типа иерархий [88].

Определим понятие «иерархия». Обозначим через  конечное множество объектов, , а через  — множество непустых частей множества , называемых таксонами и обозначаемых через . Теперь воспользуемся определением иерархии, данным в [50].

Иерархией  множества  называется множество подмножеств  таких, что:

1) (терминальные вершины (листья) — одноэлементные множества);

2) (наибольший таксон (корень) содержит все элементы );

3) для любых вершин  мы имеем либо , либо , либо .

Таким образом, иерархия — это многоуровневая структура, в которой объекты, находящиеся в одном таксоне на некотором (-м) уровне, остаются в одном таксоне на -м и всех других более высоких уровнях. Первому уровню соответствуют терминальные вершины (п. 1 в определении иерархии), а последнему, максимальному, уровню (обозначим его через ) — наибольший таксон, содержащий все элементы ; этот таксон можно обозначить тем же символом  (п. 2 в определении иерархии). На каждом уровне происходит или не происходит объединение таксонов (п. 3 в определении иерархии).

Обозначим точкой каждый таксон иерархии. Тогда отрезки, соединяющие эти точки (или вершины иерархии), передают порядок образования таксонов, который отвечает пп. 1-3 определения. На рис. 45 показана, например, иерархия , которая содержит три уровня с шестью, тремя и одной вершиной на уровнях  соответственно. Иерархия  содержит десять терминальных вершин , , , первого уровня, шесть таксонов на втором уровне, четыре таксона на уровне , два таксона на уровне  и один таксон на верхнем пятом уровне .

Можно представить себе и вырожденный случай иерархии, свернутую в одну изолированную вершину на первом уровне (иерархия  на рис. 45). Каждая -я вершина -го уровня графа   может характеризоваться структурным индексом , равным числу примыкающих к ней ребер. В нашем примере  для всех терминальных вершин иерархий  и , индексы их других вершин принимают значения от 2 до 4:  и т. д., а индекс .

Рис. 45

Терминальные вершины могут быть равнозначными, но могут и отличаться по значимости (насыщенности, весу). Так может быть, например, когда листья представляют собой таксоны с разным числом входящих в них объектов. Весовой индекс вершины обозначим через . Значения весовых индексов терминальных вершин, нормированных так, чтобы их сумма на каждом иерархическом уровне равнялась 100, указаны на рис. 45 в строке  (под чертой). Весовой индекс нетерминальных вершин уровня  равен сумме индексов вершин, входящих в эту вершину из предыдущего уровня .