Автор: Пользователь скрыл имя, 21 Ноября 2010 в 08:07, курсовая работа
Первые публикации по кластерному анализу появились в конце 30-х годов. Термин кластерный анализ, впервые введенный Трионом (Tryon) в 1939 году, включает в себя более 100 различных алгоритмов. Но активное развитие этих методов и их широкое использование началось в конце 60-х – 70-х годов. В дальнейшем это направление многомерного анализа очень интенсивно развивалось.
Целью курсовой работы является изучение основных типов задач кластер-анализа и основных типов кластер-процедур, а так же рассмотрение мер близости и расстояний между объектами.
Введение……………………………………………………………………………………….3
1. Основные типы задач кластер-анализа и основные типы кластер-процедур…………..4
2. Методы кластерного анализа………………………………………………………………5
3. Меры близости и расстояния между объектами………………………………………….7
4. Расстояния между классами объектов…………………………………………………….9
5. Пример……………………………………………………………………………………….10
Заключение…………………………………………………………………………………….18
Список литературы……………………………………………………………………………19
При задании расстояний и мер близости нужно помнить о необходимости соблюдения следующих естественных требований:
- требования симметрии (d(Oi, Oj)= d(Oj, Oi) и r(Oi, Oj)= r(Oj, Oi));
- требования максимального сходства объекта с самим собой (r(Oi, Oi)= r(Oj, Oi));
- требования при заданной метрике монотонного убывания r(Oi, Oj) по d(Oi, Oj), т.е. из d(Ok,Ol) d(Oi, Oj) должно с необходимостью следовать выполнение неравенства r(Ok,Ol) r(Oi, Oj).
Конечно, выбор метрики (или меры близости) является узловым моментом исследования, от которого решающим образом зависит окончательный вариант разбиения объектов на классы при заданном алгоритме разбиения. В каждой конкретной задаче этот выбор должен производится по-своему.
В качестве примеров расстояний и мер
близости, сравнительно широко используемых
в задачах кластер-анализа, приведем здесь
следующие.
Евклидово расстояние. Это наиболее общий тип расстояния. Оно попросту является геометрическим расстоянием в многомерном пространстве и вычисляется по формуле
,
где - значения k-го признака для i-го и j-го объектов, а p – число характеристик.
Заметим, что евклидово расстояние вычисляется по исходным данным, а не по стандартизованным данным. Это обычный способ его вычисления, который имеет определенные преимущества (например, расстояние между двумя объектами не изменяется при введении в анализ нового объекта, который может оказаться выбросом).
Взвешенное евклидово расстояние.
.
Обычно применяется в ситуациях, в которых так или иначе удается приписать каждой из компонент вектора наблюдений Х некоторый неотрицательный «вес» wk , пропорциональный степени его важности с точки зрения решения вопроса об отнесении заданного объекта к тому или иному классу. Удобно полагать при этом , .
Определение весов wk связано, как правило, с дополнительным исследованием, например получением и использованием обучающих выборок, организацией опросов экспертов и обработкой их мнений, использованием некоторых специальных моделей. Попытки определения весов только по информации, содержащейся в исходных данных, как правило, не дают желаемого эффекта, а иногда могут лишь отдалить от истинного решения.
Хеммингово расстояние (расстояние городских кварталов), также называемое «манхэттенским» или «сити-блок» расстоянием.
.
Это расстояние рассчитывается как среднее разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако, отметим, что для этой меры влияние отдельных больших разностей (выбросов) уменьшается (так как они не возводятся в квадрат).
4. Расстояния между классами объектов
При конструировании различных процедур
классификации (кластер-процедур) в ряде
ситуаций оказывается целесообразным
введение понятия расстояния между целыми
группами объектов. Приведем примеры наиболее
распространенных расстояний, характеризующих
взаимное расположение отдельных групп
объектов. Пусть Si – i-я группа (класс,
кластер) объектов, ni
- число объектов, образующих группу Si
, векторо
- среднее арифметическое векторных
наблюдений, входящих в Si
(другими словами,
- «центр тяжести» i-й группы), а
- расстояние между группами Sl
и Sm.
Метод ближнего соседа или одиночная связь.
Здесь расстояние между двумя кластерами
определяется расстоянием между двумя
наиболее близкими объектами (ближайшими
соседями) в различных кластерах. Этот
метод позволяет выделять кластеры сколь
угодно сложной формы при условии, что
различные части таких кластеров соединены
цепочками близких друг к другу элементов.
В результате работы этого метода кластеры
представляются длинными "цепочками"
или "волокнистыми" кластерами, "сцепленными
вместе" только отдельными элементами,
которые случайно оказались ближе остальных
друг к другу.
Метод наиболее удаленных соседей или полная связь.
Здесь расстояния между кластерами определяются
наибольшим расстоянием между любыми
двумя объектами в различных кластерах
(т.е. "наиболее удаленными соседями").
Метод хорошо использовать, когда объекты
действительно происходят из различных
"рощ". Если же кластеры имеют в некотором
роде удлиненную форму или их естественный
тип является "цепочечным", то этот
метод не следует использовать.
Метод Варда. В качестве расстояния
между кластерами берется прирост суммы
квадратов расстояний объектов до центров
кластеров, получаемый в результате их
объединения. В отличие от других методов
кластерного анализа для оценки расстояний
между кластерами, здесь используются
методы дисперсионного анализа. На каждом
шаге алгоритма объединяются такие два
кластера, которые приводят к минимальному
увеличению целевой функции, т.е. внутригрупповой
суммы квадратов. Этот метод направлен
на объединение близко расположенных
кластеров и "стремится" создавать
кластеры малого размера.
Метод невзвешенного попарного среднего (метод невзвешенного попарного арифметического среднего).
.
В качестве
расстояния между двумя кластерами берется
среднее расстояние между всеми парами
объектов в них. Этот метод следует использовать,
если объекты действительно происходят
из различных "рощ", в случаях присутствия
кластеров "цепочного" типа, при предположении
неравных размеров кластеров.
Метод взвешенного попарного среднего (метод взвешенного попарного арифметического среднего). Этот метод похож на метод невзвешенного попарного среднего, разница состоит лишь в том, что здесь в качестве весового коэффициента используется размер кластера (число объектов, содержащихся в кластере).
Этот метод рекомендуется использовать
именно при наличии предположения о кластерах
разных размеров.
Невзвешенный центроидный метод (метод невзвешенного попарного центроидного усреднения).
В качестве расстояния между двумя кластерами в этом методе берется расстояние между их центрами тяжести.
.
Взвешенный центроидный
метод (метод взвешенного попарного
центроидного усреднения ). Этот метод
похож на предыдущий, разница состоит
в том, что для учета разницы между размерами
кластеров (числе объектов в них), используются
веса. Этот метод предпочтительно использовать
в случаях, если имеются предположения
относительно существенных отличий в
размерах кластеров.
5. Пример
Приведены результаты опроса пяти студентов 3 курса, о том сколько времени в день каждый из них тратит:
А) на учебу ( ч.);
Б) на интернет
(
ч.).
Номер студента | 1 | 2 | 3 | 4 | 5 |
(ч) | 0,75 | 1,25 | 1 | 2,4 | 3 |
(ч) | 4 | 2 | 2,5 | 0,25 | 1,5 |
Требуется:
С помощью алгомеративного иерархического алгоритма провести классификацию студентов и построить дендограмму:
1) при
использовании обычной
2) при
использовании взвешенной
Решение
1а) Проведем классификацию, выбрав при обычном евклидовом расстоянии принцип «ближайшего соседа».
В обычной евклидовой метрике расстояние между наблюдениями 1 и 2 равно
Аналогично находим расстояние между всеми пятью наблюдениями и строим матрицу расстояний
Из матрицы расстояний следует, что объекты 2 и 3 наиболее близки (d2.3=0,56), поэтому объединим их в один кластер. После объединения объектов имеем четыре кластера: S1, S2,3, S4, S5.
Расстояние между кластерами будем находить по принципу «ближайшего соседа». Так, расстояние между кластером S1и S2,3 равно:
d(1,(2,3))=min(d1.2, d1.3)=min(2,06; 1,52)=1,52
Проводя
аналогичные расчеты для d(4,(
Объединим наблюдения 4 и 5 имеющие наименьшее расстояние d4,5=1,39. После объединения имеем три кластера S1, S(2,3), S(4,5).
Вновь строим матрицу расстояний. Для этого необходимо рассчитать расстояния d(1; (4,5)) и d((2,3);(4,5)):
d(1; (4,5))=min(d1.4,d1.5)=3,36;
d((2,3);(4,5))=min(d2.4, d2.5, d3.4, d3.5)=1,82.
Получим матрицу расстояний
Далее объединяем кластеры S1 и S(2.3), расстояние между которыми, как это видно из матрицы D3, минимально: d1,(2..3)=1,52. В результате этого получим два кластера: S(1.2.3) и S(4.5). Матрица расстояний будет иметь вид:
Из матрицы D4 следует, что на расстоянии d(1.2.3).(4.5)=1.82 все пять наблюдений объединяются в один кластер. Результаты кластерного анализа представим графически в виде дендрограммы рис.1.
Рис.1. Дендограмма (обычное евклидово расстояние, ближайший сосед)
На основании анализа результатов применения
кластерной процедуры можно сделать вывод,
что наилучшим является разбиение пяти
студентов на два кластера: S(1.2.3)
и S(4.5).
1б) Проведем классификацию, выбрав при обычном евклидовом расстоянии принцип «дальнего соседа».
Как и в случае (1а), мы используем обычное евклидово расстояние, поэтому матрица D1 остается без изменения. Согласно агломеративному алгоритму объединения в один кластер объекты 2 и 3, как наиболее близкие d2..3=0,56. После объединения имеем четыре кластера: S1, S2,3, S4, S5.
Вычисляя расстояние между кластерами по принципу «дальнего соседа», имеем:
d1.(2,3)=max(d1.2,d1.3)=2,06;
d4.(2,3)= max(d4.2,d4.3)=2,65;
d5.(2,3)= max(d5.2,d5.3)=2,24.
Соответственно, имеем новую матрицу попарных расстояний:
Объединим объекты 4 и 5 в один кластер, как наиболее близкие (d4,5=1,39).
После объединения имеем три кластера: S1, S(2,3), S(4,5).
Информация о работе Методы построения типологических групп (основные понятия кластерного анализа)