Кластерный анализ, его задача, методы и алгоритмизация

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

Экономический факультет

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

Кластерный  анализ его задача, методы и алгоритмизация 
 
 
 

Курсовая  работа

студента 3 курса группы ММЭ-3

дневного  отделения

специальности 061800 «Математические методы экономике»

Чентырева Виктора Юрьевича 

Научный руководитель

к.ф-м.н., доцент Подкорытова О.А. 

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

2011

Оглавление

Введение 3

Задача кластерного анализа 4

Методы кластерного анализа 8

Алгоритм последовательной кластеризации 10

Дендограммы 16

Применение кластерного анализа на практике 18

Заключение 20

Список использованной литературы 21 

 

Введение 

                При исследовании  и дальнейшим анализе социально-экономических явлений человек сталкивается с большим количеством проблем, связанных с многомерностью их описания. Это проявляется при сегментировании рынка, прогнозирование конъектуры рынка, разбиение стран по типологии и различным факторам, исследование цикличности экономики и так далее и тому подобное.

         Для решения данных проблем существует много методов, но наиболее эффективным является метод многомерного анализа, к нему относятся кластерный анализ, таксономия, факторный анализ и распознавание образов. Кластерный анализ наиболее подходит для многомерного анализа в классификации, а факторный в исследование связи.

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

      В ходе данной работы будут поставлены цели в более глубоком изучение кластерного анализа, а именно его задача, методы и алгоритмизация. Также будет произведена попытка в применение кластерного анализа на основе социологического опроса в пивоваренной компании «Балтика».  
 
 

Задача  кластерного анализа 

     Задача  кластерного анализа заключается в том, что на основании данных, содержащихся во множестве Х, разбить множество объектов G на m (m – целое) кластеров Q1, Q2, …, Qm, так, чтобы каждый объект принадлежал одному единственному подмножеству разбиения. А так же чтобы объекты, принадлежащие одному и тому же кластеру, были похожими, в то время как объекты, принадлежащие разным кластерам были разнородными.

     Например (на основе элитной недвижимости), пусть G включает n квартир, любая из которых характеризуется метражом (F1), видом из окна (F2), благополучностью района (F3), близость торговых и развлекательных центров (F4), наличие охраны (F5), тип дома (F6) и так далее. Значит Х1 (вектор измерений) представляет собой набор указанных характеристик для первой квартиры, Х2 - второй, Х3 для третьей, и так далее. Задача заключается в том, чтобы разбить квартиры по ценовой стоимости.

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

       

     где - представляет собой измерения j-го объекта.

     Для решения задачи кластерного анализа надо определить понятие сходства и разнородности.

     Ясно, что объекты i-ый и j-ый попадали бы в один кластер, если бы расстояние (отдаленность) между точками и было достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Следовательно, попадание в один или иные кластеры объектов определяется понятием расстояния между и из Ер, где Ер - р-мерное евклидово пространство. Неотрицательная функция d (, ) является функцией расстояния (метрикой), если: 

     а) d (, ) ³ 0, для всех Хi и из Ер

     б) d (, ) = 0, тогда и только тогда, когда =

     в) d (, ) = d(,)

     г) d (, ) £ d (, ) + d(, Хj), где Хj; и - любые три вектора из Ер. 

     Значение d (, Хj) для и является расстоянием между и и равно расстоянию между G и соответственно выбранным характеристикам (F1, F2, F3, ..., Fр).

     Наиболее часто употребляются данные функции расстояний: 

     1. Евклидово расстояние   d2(, ) =

     2. l1 - норма    d1(, ) =

     3. Сюпремум - норма   d¥ (, ) = sup

     k = 1, 2, ..., р

     4. lp - норма    dр(, ) =  

     Евклидова метрика  наиболее популярна. Метрика l1 самая легкая для вычислений. Сюпремум-норма легко считается и включает в себя процедуру упорядочения, а lp - норма охватывает функции расстояний 1, 2, 3,.

     Пусть n измерений Х1, Х2,..., Хn представлены в виде матрицы данных размером p ´ n:  

       

     А значит расстояние между парами векторов d (, ) могут быть представлены в виде симметричной матрицы расстояний: 

       

     Понятием, противоположным расстоянию, есть понятие сходства между объектами . и . Неотрицательная вещественная функция S(   ) = называется мерой сходства, если : 

     1) 0£ S ( , )<1 для ¹

     2) S (, ) = 1

     3) S (, ) = S(, )  

     Можно объединить пары значений мер сходства в матрицу сходства: 

       

     Величина - коэффициент сходства.  

 

Методы  кластерного анализа 

     На  данный момент существует много методов кластерного анализа.  Ознакомимся с некоторыми из них (ниже приводимые методы принято называть методами минимальной дисперсии).

     Пусть Х - матрица наблюдений: Х = (Х1, Х2,..., ) и квадрат евклидова расстояния между и определяется по формуле: 

       

1. Метод полных связей.

     Суть  метода заключается в том: два объекта, принадлежащих одному и тому же кластеру, имеют коэффициент сходства, меньше некоторого порогового значения S. В терминах евклидова расстояния d означает, что расстояние между двумя точками (объектами) кластера не должно превышать некоторого порогового значения h. Следовательно, h определяет максимально допустимый диаметр подмножества, образующего кластер.

2. Метод максимального локального расстояния.

     Каждый  объект рассматривается как одноточечный кластер. Объекты группируются по данному правилу: два кластера объединяются, если максимальное расстояние между точками одного кластера и точками другого минимально. Процедура заключается из n-1 шагов и результатом являются разбиения, совпадающие со всевозможными разбиениями в предыдущем методе для любых пороговых значений. 

3. Метод Уорда.

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

4. Центроидный метод.

     Расстояние  между двумя кластерами определяется как евклидово расстояние между  центрами (средними) этих кластеров:

      = (`X –`Y)Т(`X –`Y) Кластеризация идет поэтапно на каждом из n–1 шагов объединяют два кластера G и p, которые имеют минимальное значение . Если n1 много больше n2, следовательно, центры объединения двух кластеров близки друг к другу и характеристики второго кластера при объединении кластеров практически игнорируются. Порой этот метод называют методом взвешенных групп.

 

Алгоритм последовательной кластеризации 

     Рассмотрим  Ι = (Ι1, Ι2, … Ιn) как множество кластеров {Ι1}, {Ι2},…{Ιn}. Выберем два из них, например, и , которые более близки друг к другу и объединим их в один кластер. Новое множество кластеров, состоящее уже из n-1 кластеров, будет:

     {Ι1}, {Ι2}…, {Ι i , Ι j}, …, {Ιn}.

     Повторяя  процесс, получаем последовательные множества кластеров, которые состоят из (n-2), (n-3), (n–4) и т.д. кластеров. В завершение процедуры можно получить кластер, состоящий из n объектов и совпадающий с первоначальным множеством Ι = (Ι1, Ι2, … Ιn).

     В качестве меры расстояния берется квадрат евклидовой метрики . и вычислим матрицу D = { }, где - квадрат расстояния между Ι i и Ι j: 

 

     Пусть расстояние между  и будет минимальным:

       = min { , i ¹ j}. Образуем с помощью и   новый кластер

     { , }.

     Cтроим новую ((n-1), (n-1)) матрицу расстояния