Иерархическая кластеризация на основе дендрограммы

Функция Z = linkage(Y, ’method’) возвращает иерархическое дерево кластеров. Ее аргументами является вектор Y, возвращаемый функцией pdist. Строка ‘method’ задает метод кластеризации:

• ‘single’ – алгоритм ближайшего соседа;
• ‘complete’ – алгоритм дальнего соседа;
• ‘average’ – алгоритм средней связи;
• ‘centroid’ – центроидный метод – по центрам тяжести групп;
• ‘ward’ – пошаговый алгоритм.

На первом шаге ближайшие объекты объединяются парами и каждая найденная пара рассматривается как новый объект. Каждый следующий объект присоединяется или к одному из исходных, или к одной из ранее образованных групп, группы могут объединяться. Матрица Z имеет (m -1) строку и 3 столбца. Первые 2 столбца – номера объединяемых объектов, третий – расстояние между ними.

Функция dendrogram(Z) создает графическое отображение полученного дерева кластеров.

Функция cophenet(Z,Y) возвращает аналог коэффициента корреляции, характеризующий качество разбиения: чем ближе к 1, тем лучше.

Функция inconsistent(Z) возвращает коэффициенты несовместимости для каждого уровня дерева и тоже характеризует качество разбиения.

  Функция T = cluster(Z, cutoff) или T = cluster(Z, cutoff, depth) объединяет все перечисленные функции. Здесь

• Z – матрица, возвращаемая функцией linkage;
• Если параметр cutoff имеет значение от 0 до 1, то он задает порог для коэффициентов несовместимости, при достижении которого кластер считается сформированным;
• Если параметр cutoff – целое число >1, то он задает число кластеров;
• depth – промежуточный параметр, указывающий, сколько уровней просматривается при нахождении коэффициентов несовместимости;
• Т – столбец длины n с номерами кластеров, к которым приписан каждый объект.

  Функция T = clusterdata(X, cutoff) объединяет все перечисленные функции.

  В Документе 8.3 сформирована 2-мерная выборка из ранее рассмотренного примера и приведены варианты обращения к нескольким стандартным функциям ИМС MatLab, на рис.8.3, 8.4 – экранный вывод.

 

Документ 8.3. Кластеризация на основе дендрограммы

clear; clc; % 7 двумерных векторов X =[3 1.7; 1  1; 2 3; 2 2.5; 1.2 1; 1.1 1.5; 3 1 ]; Y=pdist(X,'euclid'); Z=linkage(Y,'complete'); dendrogram(Z); % иерархическое дерево кластеров U=cophenet(Z,Y); disp ('Оценка качества разбиения'); disp (U); V = inconsistent (Z); disp ('Коэффициенты несовместимости'); disp (V);

 

Оценка качества разбиения 0.9186 Коэффициенты несовместимости 0.2000    0   1.0000    0 0.5000    0   1.0000    0 0.3550 0.2191 2.0000    0.7071 0.7000    0        1.0000    0 1.1096 0.8793 3.0000    1.1479 1.6183 0.9703 3.0000    0.6366

Рис.8.3. Экранный вывод в Документе 8.3

Рис.8.4. Дендрограмма - графический вывод в Документе 8.3

Оценка качества разделения

    Качество разбиения обычно характеризуют отношением среднего расстояния между центрами классов к среднему расстоянию элементов внутри каждого класса от его центра.

    В версиях ИМС MatLab, начиная с 7x, этой цели служит специальная функция silhouette(X0,T,’distance’,’sqEuclidean’). Результат вычислений в Документе 8.2 с использованием этой функции приведен на рис.8.5.

Рис.8.5. Результат вычислений в Документе 8.2 с использованием функции silhouette

 

Задания на лабораторную работу

5. Смоделировать две 3-мерные выборки (n =100) из нормального закона с различными средними и ковариационными матрицами.

6. Произвести кластеризацию полученных данных 3 различными способами.

7. Проанализировать зависимость результатов кластеризации от расстояния Махаланобиса между исходными классами.

8. Перейти к плоскости главных компонент и изобразить на ней зоны притяжения каждого из классов.

Контрольные вопросы

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

ЗАКЛЮЧЕНИЕ

Электронное учебное пособие по дисциплине «Интеллектуальный анализ данных» разработано в соответствии с федеральным государственным образовательным стандартом (ФГОС ВО 3++) по уровню магистратуры.

В электронном учебном пособии содержится систематическое изложение основ современных методов анализа многомерных данных.

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1. Большаков А.А., Каримов Р.Н. М. Методы обработки многомерных данных и временных рядов. Учебное пособие для ВУЗов. - Горячая линия-Телеком, 2015. – 522 с.

2. Большев Л.Н., Смирнов Н.В. Таблицы математической статистики.- М.: Наука, 1965.- 464с.

3. Дьяконов В., Круглов В. Математические пакеты расширения MATLAB. Специальный справочник. - СПб: Питер, 2001

4. Мхитарян В.С. Анализ данных. Учебник для академического бакалавриата. - М.: Юрайт, 2016. 

5. Советов Б.Я., Цехановский В.В. Информационные технологии. Учебник для прикладного бакалавриата. - М.: Юрайт, 2016.

6. Чубукова И. Data Mining. - М.: Юрайт, 2016