Лаба 3-4 / Praktika_3_7501_Kiryanova

_{МИНОБРНАУКИ РОССИИ}

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра биотехнических систем

отчет

по практическому занятию №3

по дисциплине «Моделирование биологических процессов и систем»

Тема: Кластеризация

Вариант 8

Студентка гр. 7501		Кирьянова А.М.
Преподаватель		Скоробогатова А.И.

Санкт-Петербург

2020

Цель работы: осуществить кластеризацию данных с помощью различных иерархических методов.

Основные теоретические положения

Кластеризация (кластерный анализ) – задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты различных групп должны быть как можно более отличны.

Главное отличие кластеризации от классификации состоит в том, что перечень групп не задан четко и определяется в процессе работы алгоритма.

Цели кластеризации:

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

• Сжатие данных. Если исходная выборка избыточно большая, то ее можно сократить, оставив по одному наиболее типичному представителю от каждого кластера;

• Обнаружение новизны. Выделяются нетипичные объекты, которые не удается присоединить ни к одному из кластеров.

Этапы кластеризации:

1. Отбор выборки объектов кластеризации.

2. Определение множества переменных, по которым будут оцениваться объекты в выборке. При необходимости – нормализация значений переменянных.

3. Вычисление значений меры сходства между объектами (например, расстояний).

4. Применение метода кластерного анализа для создания групп сходных объектов (кластеров).

5. Выбор числа кластеров.

6. Представление результатов анализа.

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

Код программы

clc

clear

close all

%% Загрузка данных

k=8;

P1 = xlsread('clust.xlsx','Лист1','O1:O300');

P2 = xlsread('clust.xlsx','Лист1','P1:P300');

%% Нормирование

P1 = P1';

P2 = P2';

m = mean(P1);

sko = std(P1);

P11 = zeros(1,300);

for i = 1:300

P11(1,i) = (P1(1,i)-m)/sko;

end

m = mean(P2);

sko = std(P2);

P22 = zeros(1,300);

for i = 1:300

P22(1,i) = (P2(1,i)-m)/sko;

end

%% Создание общей матрицы

P=[P11' P22'];

%% Скаттерограмма на основании idx

figure()

idx = kmeans(P,3);

gscatter(P11,P22,idx,'rbm');

title('Скаттерограмма');

legend('Cluster 1','Cluster 2','Cluster 3','Location','best')

legend('boxoff')

%% Иерархический метод

tree1 = linkage(P,'average');

tree2 = linkage(P,'complete');

tree3= linkage(P,'weighted');

tree4 = linkage(P,'single');

tree5 = linkage(P,'ward');

%tree6 = linkage(P,'centroid');

%tree7 = linkage(P,'median');

figure()

D1=dendrogram(tree1,'Orientation','left','ColorThreshold','default');

set(D1,'LineWidth',2)

title('Average')

figure()

D2=dendrogram(tree2,'Orientation','left','ColorThreshold','default');

set(D2,'LineWidth',2)

title('Complete')

figure()

D3=dendrogram(tree3,'Orientation','left','ColorThreshold','default');

set(D3,'LineWidth',2)

title('Weighted')

figure()

D3=dendrogram(tree4,'Orientation','left','ColorThreshold','default');

set(D3,'LineWidth',2)

title('Single')

figure()

D3=dendrogram(tree5,'Orientation','left','ColorThreshold','default');

set(D3,'LineWidth',2)

title('Ward')

%% Метки кластеров и скаттерограммы

c1 = cluster(tree1,'Maxclust',4);

figure()

gscatter(P(:,1),P(:,2),c1,[1 0 0;0.75, 0, 0.9;0 1 0;0 1 1]);

legend('Cluster 1','Cluster 2','Cluster 3','Cluster 4','Location','best')

legend('boxoff')

title('Скаттерограмма относительно метода кластеризации Average');

c2 = cluster(tree2,'Maxclust', 3);

figure()

gscatter(P(:,1),P(:,2),c2,'grb');

legend('Cluster 1','Cluster 2','Cluster 3','Location','best')

legend('boxoff')

title('Скаттерограмма относительно метода кластеризации Complete');

c3 = cluster(tree3,'Maxclust', 2);

figure()

gscatter(P(:,1),P(:,2),c3,'cr');

legend('Cluster 1','Cluster 2','Location','best')

legend('boxoff')

title('Скаттерограмма относительно метода кластеризации Weighted');

c4 = cluster(tree4,'Maxclust', 2);

figure()

gscatter(P(:,1),P(:,2),c4,'cr');

legend('Cluster 1','Cluster 2','Location','best')

legend('boxoff')

title('Скаттерограмма относительно метода кластеризации Single');

c5 = cluster(tree5,'Maxclust', 2);

figure()

gscatter(P(:,1),P(:,2),c5,'cr');

legend('Cluster 1','Cluster 2','Location','best')

legend('boxoff')

title('Скаттерограмма относительно метода кластеризации Ward')

Обработка результатов эксперимента

Чтобы кластеризовать данные, предварительно их необходимо нормализовать по формуле стандартного z-распределения со средним, равным 0, и стандартным отклонением, равным 1:

где r – исходные данные; m – среднее значение по признаку; s – стандартное отклонение по признаку.

Затем построим скатерограмму пронормированных данных относительно параметра idz, рассчитанного функцией MATLAB kmean(), которая разделяет данные на количество кластеров, заданное пользователем (в нашем случае 3), с помощью k++ алгоритма (means++ algorithm k). Алгоритм работы реализуется следующим образом:

1. Из выборки данных X выбирается случайное однородное значение, которое принимается за центральное (центроид) и обозначается c₁.

2. Вычисляется расстояние от каждого объекта до c₁. Расстояние между c_j и наблюдением m обозначается как d(x_m,c_j).

3. Следующий центроид c₂ выбирается наугад с вероятностью

В результате получается скаттерограмма, представленная на рисунке 1.

Рисунок 1 – Скаттерограмма, полученная с помощью k++ алгоритма

Далее проведем иерархическую кластеризацию различными методами, которые представлены на рисунке 2.

Рисунок 2 – Методы иерархической кластеризации, предлагаемые документацией MATLAB

Для использования методов, представленных на рисунке 2, используется функция linkage() c указанием выбранного метода.

Результаты иерархической кластеризации

1. Метод средней связи Average

Рисунок 3 – Дендрограмма и скаттерограмма, полученные на основе метода средней связи Average

В этом методе и далее оптимальное число кластеров выбиралось визуально с помощью дендограммы. Для наглядности выбора в функции dendogram() использовался параметр 'ColorThreshold', помогающий определить оптимальное число кластеров по цветам (в данном случае 4). Затем с помощью cluster() были получены метки кластеров, относительно которых и строились конечные скаттерограммы.

2. Метод полной связи Complete

Рисунок 4 – Дендрограмма и скаттерограмма, полученные на основе метода полной связи Complete

3. Метод одиночной связи Single

Рисунок 5 – Дендрограмма и скаттерограмма, полученные на основе метода одиночной связи Single

4. Метод Уорда Ward

Рисунок 6 – Дендрограмма и скаттерограмма, полученные на основе метода Уорда Ward

5. Метод взвешенной средней связи Weighted

Рисунок 7 – Дендрограмма и скаттерограмма, полученные на основе метода взвешенной средней связи Weighted

По рисункам 4-7 видно, что для имеющегося набора данных использование метода одиночной связи наименее удачно, а чаще всего данные разделяются на 2 кластера. Можно предположить, что деление на два кластера является оптимальным.

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

Вывод

В ходе данной практической работы было рассмотрено понятие кластеризации, ее цели и задачи, осуществлена кластеризация данных иерархическим методом, подобрано оптимальное количество кластеров (предположительно 2). Изучены наглядные методы определения числа кластеров: построение дендрограмм и скатерограмм относительно расстояний между объектами, вычисленных различными способами.