8.3. Графические представления результатов иерархической классификации

Алгоритмы иерархической классификации по сравнению, например, с алгоритмами, описанными в гл. 7, применимы для классификации множеств X относительно небольшого объема, но зато позволяют в ряде случаев получить более полный анализ структуры исследуемого множества объектов Так, граф классификации дает представление о взаимосвязи между разбиениями и на разных уровнях, и если принято решение остановиться на разбиении множества X, то для каждого элемента можно оценить степень его принадлежности к классу для некоторого при помощи пути (простой цепи, см. 112, с. 147]), соединяющего вершины графа, соответствующие X и классу

Существенным преимуществом алгоритмов иерархической классификации является возможность наглядной интерпретации проведенного анализа.

Имеется большая свобода в построении на плоскости данного графа иерархии. Изучая различные изображения, согласованные с его структурой, можно получить ряд нетривиальных результатов об исследуемом множестве объектов, которые и рассмотрены ниже.

8.3.1. Индексации иерархии. Методы построения на плоскости графа иерархической классификации.

Опишем общую схему построения на плоскости i рафа агломеративной классификации Для получения изображения графа дивизимной классификации применимы те же методы, только во всех построениях надо поменять на противоположное направление оси ординат (см. рис. 8.2).

Определение 8.5 Индексацией v иерархии называется отображение ставящее в соответствие множеству число таким образом, что:

тогда и только тогда, когда S состоит из одного элемента; для каждой пары из s, такой, что .

Определение 8.6 Строгой индексацией v иерархии s называется ее индексация, удовлетворяющая условию: для каждой пары из s, такой, что

Пусть — некоторая индексированная агломеративная иерархия s на множестве построенная при помощи меры близости . Вершины графа этой иерархии, соответствующие множествам , обозначим через а вершины, соответствующие множествам — через Допустим, что вершины нанесены на плоскость, т. е. можно записать в координатах: Тогда, если , то положим

и соединим точки Далее будем использовать соединение, показанное на рис. 8.3. Начальный шаг построения обеспечивается тем, что, по предположению, вершины , располагаются на оси абсцисс. На этой оси они упорядочиваются так, чтобы в итоговом изображении графа минимизировать число пересечений ребер графа Например, если v — строгая индексация, то можно так упорядочить вершины что ребра будут соединяться только в вершинах. Таким образом каждая индексация задает изображение графа.

(см. скан)

Рис. 8.2. Графы иерархий, описывающие процедуры классификации: а) дивизимная (нисходящая) процедура; 6) агломеративная (восходящая) процедура

До последнего времени в пакетах программ реализовывалось графическое представление агломеративной иерархии, основанное на строгой индексации v, ставящей в соответствие множеству номер шага, на котором это множество было включено в иерархию. В этом случае индексация v любой иерархии s принимает значения Важные исследования по индексациям иерархий проведены в [248], на результаты [248] опирается изложение этих вопросов в книге.

8.3.2. Оцифровка изображения графа иерархической классификации.

При наглядной интерпретации результатов классификации большое значение имеет то, какую дополнительную информацию о структуре исследуемой совокупности объектов несет распределение на отрезке [0,1] числовой последовательности для выбранной индексации

Рис. 8.3. Правило соединения вершин при изображении на плоскости графа иерархической классификации с использованием индексирующего отображения

Рис. 8.4. Конфигурация точек множества из примера 8.3

Пример 8.3. Пусть — множество точек на плоскости, изображенное на рис. 8.4, и s — его агломеративная иерархия, построенная по мере близости (5.6): где Z, — центр класса Здесь , где Поэтому

Из рис. 8.5 видна роль выбора индексирующего отображения v. В случае а) наглядна последовательность вхождения классов в иерархию; в случае б) это невозможно увидеть, но очень наглядно распределение тех же классов числу элементов в них, хотя речь идет об одной и той же иерархии

(см. скан)

Рис. 8.5 Изображение графа иерархии S множества из примера 8.3 a) , где k — номер шага, на котором S включается в s; б)

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

Такие изображения графа называются оцифрованными.

Рис. 8.6. Инверсия в изображении графа иерархической классификации множества точек из примера 8.3 Здесь

Возникает задача: пусть -бинарная иерархия множества X, полученная агломеративным алгоритмом при помощи меры близости Найти индексацию v этой иерархии, такую, что

Так как любое множество однозначно представимо в виде для некоторых из s, то формула (8.8) вместе с условием , однозначно задает отображение v на s. Таким образом, сформулированная задача эквивалентна следующей:

для каких мер близости отображение v, задаваемое формулой (8.8), является индексацией.

Пример 8.4. Пусть — набор точек в евклидовом пространстве

— центр класса Тогда отображение v, задаваемое формулой (8.8), не является индексацией. Действительно, для точек из примера 8.3 имеем в случае где Таким образом, для получаем:

— противоречие с определением индексации. Если же мысленно для такого отображения v изобразим граф иерархии по правилу, описанному выше, то на этом изображении получим следующий фрагмент (рис. 8.6), где вершина, соответствующая объединению двух подмножеств, лежит по оси ординат ниже, чем вершина, соответствующая одному из этих подмножеств.

В этом случае говорят, что мера близости имеет инверсии. В § 8.4 приведены условия на меру близости, обеспечивающие отсутствие инверсий у нее. Ряд важнейших мер близости этим условиям удовлетворяет (см. теорему 8.1).