Иерархический кластерный анализ. Проблема индексации

Наряду с обычным, «раздельным», кластерным анализом широко применяется иерархический кластерный анализ, цель которого состоит в получении всей иерархии разбиений, а не отдельного разбиения. Считается, что иерархия точнее характеризует размытую структуру данных, чем отдельное разбиение. Получить конкретное разбиение в случае необходимости сравнительно легко сечением графа иерархий.

Основные определения Пусть О = { O ¹, O ², …,O^N } – конечное множество объектов. Иерархией h на О называется система подмножеств (классов) { K: K O }такая, что

1) O h;

2) { Oⁱ } h, i= 1,2 ,…,N;

3) для пересекающихся подмножества K и K ´, т.е. K K´ ≠ Ø, K K´ либо K´ K.

Пример. Пусть О = { О ¹, О ² ,…, О ⁵}. Тогда система подмножеств

h = {{ O ¹}, { O ²}, …,{ O ⁵}, { O ¹ ,O ²}, { O ³ ,O ⁴}, { O ¹ ,O ² ,O ⁵}, O }

является иерархией на О.

Иерархия может быть представлена на языке теории графов. Графом иерархии h на О называется ориентированный граф (V,E), вершины v V которого соответствуют множествам K h, а ребра e E – парам (K´,K), таким что K´ K. Ребро e = (K´,K) изображается стрелкой с началом K´ и концом K.

Иерархической классификацией данного множества объектов

О = { O ¹, O ², …,O^N } называется построение иерархии h на О, отражающей наличие однородных в определенном смысле классов.

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

В иерархическом кластерном анализе используются два вида алгоритмов: дивизимные и агломеративные. В дивизимных алгоритмах множество О постепенно делится на все более мелкие подмножества, в агломеративных – наоборот: точки множества О постепенно объединяются во все более крупные подмножества. Соответственно графы иерархий, полученные при помощи этих алгоритмов, называют дивизимными и агломеративными. Дивизимные алгоритмы называют также нисходящими (движение против стрелок на графе иерархии), агломеративные – восходящими (движение вдоль стрелок). Если на каждом шаге такого алгоритма объединяются только два кластера, то говорят о бинарном агломеративном алгоритме. Далее рассматриваются лишь такие алгоритмы.

Более подробно схема работы бинарного агломеративного алгоритма выглядит следующим образом. Исходное множество О = ={ O ¹, O ², …,O^N } рассматривается как множество одноэлементных кластеров; выбирают два из них, например K_i и K_j, которые наиболее близки в смысле введенной метрики друг другу и объединяют их в один кластер. Новое множество кластеров будет иметь уже
N- 1 элемент K ₁ ,K ₂ ,…, { K_i,K_j } ,…,K_N..

Рассматривая полученное множество в качестве исходного и повторяя процесс, получают последовательные множества кластеров, состоящие из N- 2, N- 3 и т.д. кластеров.

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

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 9

Связь D - и G -оптимального планирования.

Связь D- и G-Оптимального планирования.

Критерий D-оптимальности Критерий D -оптимальности требует такого расположения точек в области планирования , при котором определитель матрицы имеет минимальную величину. Иными словами, план D -оптимален, если .

Известно, что объем эллипсоида рассеяния пропорционален корню из величины определителя ковариационной матрицы, т.е. . С учетом (3.8) V ~ .

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

Критерий G-оптимальности План G-оптимален, если он обеспечивает наименьшую величину максимальной дисперсии оценки зависимой переменной: .

На практике желательно использовать планы, удовлетворяющие одновременно нескольким критериям. В общем случае такого сочетания свойств не наблюдается. В теории планирования эксперимента доказано, что непрерывный D -оптимальный план является также G -оптимальным. Условие D -оптимальности дискретного плана имеет следующий вид: . (6.2)

Если для дискретного D -оптимального плана имеет место , то этот план является также A -оптимальным. Построение D -оптимальных планов является сложной вычислительной задачей. Аналитический путь здесь оказывается возможным в некоторых простейших случаях (полиномиальная модель от одной переменной, квадратичная регрессия от переменных для стандартной области (гиперкуб)). В общем случае для построения D -оптимальных планов используются численные методы, связанные с минимизацией определителя матрицы С либо максимизацией определителя информационной матрицы F’F, что несомненно проще в вычислительном отношении.