34)Методы иерархического кластерного анализа. Алгоритмическая схема. Геометрическая интерпретация результатов. Основные иерархические методы:
1
.
Метод полных связей заключается
в сравнении расстояний с эталоном. Если
расстояние меньше, чем эталон, то
заносится в первый кластер.
2. Метод одиночной связи. Сначала все объекты признаются отдельно взятыми кластерами. Далее начинается поиск наиболее близких объектов по матрице расстояний.
Далее относительно первого кластера, содержащего два объекта (1, 2), ищется минимальное расстояние. И т.д.
Основной недостаток:
- неизвестно, где получить разрыв между кластерами.
- нет критерия классификации
- если оказалось несколько одинаковых минимумов, то параллельно ведется образование нескольких кластеров, следовательно, нечеткость классификации
3. Метод средних связей
- Сначала все объекты признаются отдельно взятыми кластерами
- находится матрица расстояний
- путем сравнения эталона и среднего расстояния объекты заносятся в кластеры
4. Метод Уорда. Содержит внутри себя критерий классификации - минимизация внутригрупповой суммы квадратов отклонений (ВСК) на основе метрики расстояний:
,
i – номер объекта,
вошедшего в кластер; m
– размер-ть признаков. простр-ва
Данная величина будет возрастать на
(по формуле статистического расстояния)
при условии, что в кластер присоединяются
новые объекты.
Данный метод требует, чтобы
на
всем признаковом пространстве.
В общем виде для любых произвольно
взятых кластеров (I,J), которые,
объединяясь, образуют кластер K,
можно записать, что расстояние
будет высчитываться как:
,
где
- внутригрупповая сумма квадратов
кластеров I и J;
- межгрупповая сумма квадратов (МСК) –
матрица.
След матрицы МСК равен статистическому расстоянию между центрами тяжести кластеров I и J.
Для программирования этих методов на компьютере понадобятся следующий коэффициент:
Три системы весов
- метод ближайшего соседа:
- метод дальнего соседа:
- медианный метод:
- метод средней связи:
- центроидный метод:
- метод Уорда:
Иерархический метод всегда завершается дендрограммой:
Дивизивный метод
Алгоритм иерархического метода
1 шаг. Формирование матрицы объект-признак
и каждая строка этой матрицы объявляется
кластером:
2 шаг. Нормировка (если требуется)
3 шаг. Подбор метрики в виде
или
,
чувствительной к исходным данным
4 шаг. Расчет первоначальной матрицы расстояний, либо переход к матрице объект-объект.
5 шаг. Поиск минимального значения в
матрице D:
.
Далее объединяем первые два кластера
i и k
и присваиваем этому кластеру № по
наименьшему из 2-х порядковых номеров.
6 шаг. Выбор стратегии классификации и пересчет матрицы расстояний с учетом выбранной стратегии.
7 шаг. Работа с модифицированной матрицей D, которая позволит найти и объединить два самых близких кластера.
8 шаг. Повторять шаги 6 и 7 до тех пор, пока все кластеры не будут объединены в один, либо до тех пор, пока не будет выполнена целевая функция классификаций