Министерство образования и науки РФ

Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»

кафедра математического обеспечения ЭВМ

Отчет

по лабораторной работе №3

«Кластерный анализ»

по дисциплине «Анализ и интерпретация данных»

Выполнил: студент гр. 3341 Рыжок М.С.

Проверил: Жукова Н.А.

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

Лабораторная работа №3

«Кластерный анализ»

Цель работы : Исследование методов кластер-анализа с помощью системы STATISTIKA

1. Исследования провести на имеющихся данных IRIS а также на модельных примерах в соответствии с индивидуальным заданием

2. Исследовать методы иерархической группировки -JOINING (TREE CLUSTERING)

3. Провести исследование иерархической кластеризации при использовании кластеризации по признакам

4. Выбрать метод кластеризации K-Means Clustering (метод К-средних) из меню CLUSTERING METHOD

Предварительные сведения

Термин кластерный анализ (впервые ввел Tryon, 1939) в действительности включает в себя набор различных алгоритмов классификации. Общий вопрос, задаваемый исследователями во многих областях, состоит в том, как организовать наблюдаемые данные в наглядные структуры, т.е. развернуть таксономии. Например, биологи ставят цель разбить животных на различные виды, чтобы содержательно описать различия между ними. В соответствии с современной системой, принятой в биологии, человек принадлежит к приматам, млекопитающим, амниотам, позвоночным и животным. Заметьте, что в этой классификации, чем выше уровень агрегации, тем меньше сходства между членами в соответствующем классе. Человек имеет больше сходства с другими приматами (т.е. с обезьянами), чем с "отдаленными" членами семейства млекопитающих (например, собаками) и т. д

Фактически, кластерный анализ является не столько обычным статистическим методом, сколько "набором" различных алгоритмов "распределения объектов по кластерам". Существует точка зрения, что в отличие от многих других статистических процедур, методы кластерного анализа используются в большинстве случаев тогда, когда вы не имеете каких-либо априорных гипотез относительно классов, но все еще находитесь в описательной стадии исследования. Следует понимать, что кластерный анализ определяет "наиболее возможно значимое решение".

Деревья кластеризации

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

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

Шаг	Расстояние	№ объекта	№ объекта		№ объекта		…
1	0.000000	102		143		…
2	.1000000	8		40		…
3	.1000000	1		18		…
4	.1000000	10		35		…
5	.1000000	129		133		…
6	.1000000	11		49		…
7	.1414214	1		18	41	…
8	.1414214	30		31		…
9	.1414214	58		94		…
10	.1414214	81		82		…

Наглядным образом можно представить результат процедуры в виде дерева.

Использующиеся меры расстояния между объектами:

• Евклидово расстояние

• Расстояние городских кварталов (манхэттенское):

• Расстояние Чебышева:

Использующиеся способы объединения кластеров :

• Одиночная связь (метод ближайшего соседа). В этом методе расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах

• Полная связь (метод наиболее удаленных соседей). В этом методе расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. "наиболее удаленными соседями").

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

• Метод Варда. Метод минимизирует сумму квадратов (SS) для любых двух (гипотетических) кластеров, которые могут быть сформированы на каждом шаге.

Ниже приведены деревья классификации по расстоянию между объектами.

1. Принцип объединения - одиночная связь, расстояние – евклидово.

2. Принцип объединения - одиночная связь, расстояние – чебышевское1.3 Принцип объединения - одиночная связь, расстояние – манхэттенское

2.1 Принцип объединения - полная связь, расстояние – евклидово

2. Принцип объединения - полная связь, расстояние – чебышевское

2.3 Принцип объединения - полная связь, расстояние – манхэттенское

3.1 Принцип объединения – метод Варда, расстояние – евклидово

3.2 Принцип объединения – метод Варда, расстояние – чебышевское

3.3 Принцип объединения – метод Варда, расстояние – манхэттенское

4.1 Принцип объединения – невзвешенное попарное среднее, расстояние – евклидово

4.2 Принцип объединения – невзвешенное попарное среднее, расстояние – чебышевское

4.3. Принцип объединения – невзвешенное попарное среднее, расстояние – манхэттенское

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

1. Принцип объединения - одиночная связь, расстояние – евклидово

Расстояние	Obj. No.	Obj. No.	Obj. No.	Obj. No.
25,86407	Ширина чашелистика	Ширина лепестка
25,87489	Ширина чашелистика	Ширина лепестка	Длина лепестка
28,95238	īДлина чашелистика	Ширина чашелистика	Ширина лепестка	Длина лепестка

2. Принцип объединения - одиночная связь, расстояние – чебышевское

	Obj. No.	Obj. No.	Obj. No.	Obj. No.
4,000000	Ширина чашелистика	Ширина лепестка
4,300000	Ширина чашелистика	Ширина лепестка	īДлина лепестка
4,600000	īДлина чашелистика	Ширина чашелистика	Ширина лепестка	īДлина лепестка

3. Принцип объединения - одиночная связь, расстояние – манхэттенское

	Obj. No.	Obj. No.	Obj. No.	Obj. No.
278.7	Ширина чашелистика	Ширина лепестка
302.7	Ширина чашелистика	Ширина лепестка	īДлина лепестка
312	īДлина чашелистика	Ширина чашелистика	Ширина лепестка	īДлина лепестка

1. Принцип объединения - полная связь, расстояние – евклидово

	Obj. No.	Obj. No.	Obj. No.	Obj. No.
25,86407	Ширина чашелистика	Ширина лепестка
28,95238	Длина чашелистика	Длина лепестка
57,18304	Длина чашелистика	Длина лепестка	Ширина чашелистика	Ширина лепестка

2. Принцип объединения - полная связь, расстояние – чебышевское

	Obj. No.	Obj. No.	Obj. No.	Obj. No.
4.00	Ширина чашелистика	Ширина лепестка
4.60	Длина чашелистика	Длина лепестка
5.90	Длина чашелистика	Длина лепестка	Ширина чашелистика	Ширина лепестка

3. Принцип объединения - полная связь, расстояние – манхэттенское

	Obj. No.	Obj. No.	Obj. No.	Obj. No.
278.7	Ширина чашелистика	Ширина лепестка
312.0	Длина чашелистика	Длина лепестка
696.6	Длина чашелистика	Длина лепестка	Ширина чашелистика	Ширина лепестка

1. Принцип объединения – метод Варда, расстояние – евклидово

	Obj. No.	Obj. No.	Obj. No.	Obj. No.
25.86407	Ширина чашелистика	Ширина лепестка
28.95238	Длина чашелистика	Длина лепестка
49,19687	Длина чашелистика	Длина лепестка	Ширина чашелистика	Ширина лепестка

2. Принцип объединения – метод Варда, расстояние – чебышевское

	Obj. No.	Obj. No.	Obj. No.	Obj. No.
4,000000	Ширина чашелистика	Ширина лепестка
4,600000	Длина чашелистика	Длина лепестка
5,700000	Длина чашелистика	Длина лепестка	Ширина чашелистика	Ширина лепестка

3. Принцип объединения – метод Варда, расстояние – манхэттенское

	Obj. No.	Obj. No.	Obj. No.	Obj. No.
278,7000	Ширина чашелистика	Ширина лепестка
312,0000	Длина чашелистика	Длина лепестка
605,6500	Длина чашелистика	Длина лепестка	Ширина чашелистика	Ширина лепестка

1. Принцип объединения – невзвешенное попарное среднее, расстояние – евклидово

	Obj. No.	Obj. No.	Obj. No.	Obj. No.
25,86407	Ширина чашелистика	Ширина лепестка
28,95238	Длина чашелистика	Длина лепестка
38,30255	Длина чашелистика	Длина лепестка	Ширина чашелистика	Ширина лепестка

2. Принцип объединения – невзвешенное попарное среднее, расстояние – чебышевское

	Obj. No.	Obj. No.	Obj. No.	Obj. No.
4,000000	Ширина чашелистика	Ширина лепестка
4,500000	Ширина чашелистика	Ширина лепестка	Длина лепестка
5,200000	Длина чашелистика	Ширина чашелистика	Ширина лепестка	Длина лепестка