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

 

     (n-2) строки для последней матрицы ,берутся из предыдущей, а первая строка вычисляется заново. Вычисления могут быть сведены к минимуму, при условии, что удастся выразить , k = 1, 2,…, n; (k ¹ i ¹ j) через элементы первоначальной матрицы.

     Изначально  определено расстояние между одноэлементными кластерами, однако следует определять расстояния и между кластерами, которые содержат более чем один элемент. Это можно осуществить различными способами, и в зависимости от выбранного способа мы получаем алгоритмы кластерного анализа с различными свойствами. Можно, например, положить расстояние между кластером i + j и некоторым другим кластером k, который равен среднему арифметическому расстояний между кластерами i и k и кластерами j и k:

      = ½ ( + ). 

     Но  можно также определить как минимальное из этих двух расстояний:  

      = min ( + ). 

     Следовательно, описан первый шаг работы агломеративного иерархического алгоритма. Дальнейшие шаги аналогичны.

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

       = A(w) min( djk) + B(w) max( ), где

     A(w) = , если £

     A(w) = , если >

     B(w) = , если £

     B(w) = , если >  

     где и - число элементов в кластерах i и j, а w – свободный параметр, определяющий конкретный алгоритм. При w = 1 мы получаем алгоритм «средней связи», для которого формула перерасчета расстояний имеет вот такой вид: 

       =

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

     Смысл параметра w становится очевидным, если предположить, что w® ¥. Формула пересчета расстояний принимает вид: 

       = min (, ) 

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

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

     В случае кластер анализа объектов наиболее частой мерой различия служит либо квадрат евклидова расстояния 

       

     (где  , - значения h-го признака для i-го и j-го объектов, а m - число характеристик), либо само евклидово расстояние. В случае если признакам приписывается разный вес, то эти веса можно учесть при вычислении расстояния  

       

     Порой в качестве меры различия используется расстояние, вычисляемое по формуле: 

       

     называющиеся: "хэмминговым", "манхэттенским" или "сити-блок" расстоянием.

     Естественной  мерой сходства характеристик объектов во многих задачах - это коэффициент корреляции между ними 

       

     где , ,di ,dj - средние и среднеквадратичные отклонения для характеристик i и j. Мерой рaзличия между характеристиками может служить величина 1-r. Порой В задачах знак коэффициента корреляции несуществен и зависит лишь от выбора единицы измерения. Тогда в качестве меры различия между характеристиками применяется ô1 - ô.

 

Дендограммы 

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

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

     

     Рис1 

     На  рисунке 1 показан один из примеров дендограммы. Рис 1 описывает случай шести объектов (n=6) и k характеристик. Объекты А и С самые близки и следовательно объединяются в один кластер на уровне близости, равном 0,9. Объекты D и Е совмещаются при уровне 0,8. Теперь имеем 4 кластера: (А, С), (F), (D, E), (B).

     Далее строятся кластеры (А, С, F) и (E, D, B), соответствующие уровню близости 0,7 и 0,6. Окончательно все объекты группируются в одно подмножество при уровне 0,5.

     Вид дендограммы зависит от выбора меры сходства или расстояния между объектом и кластером и метода кластеризации. Самым важным моментом будет выбор меры сходства или меры расстояния между объектом и кластером.

     Число алгоритмов кластерного анализа достаточно велико. Всех можно подразделить на иерархические и неиерархические.

     Иерархические делятся на:

     а) агломеративные, характеризуемые последовательным объединением исходных элементов и  соответствующим уменьшением числа  кластеров;

     б) дивизимные (делимые), в которых число  кластеров возрастает, начиная с  одного, в результате чего образуется последовательность расщепляющих групп.

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

       

 

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

     В ходе исследования на основе данных социальной статистики пивоваренной компании «Балтика» было опрошено 2956 респондентов и их мнение по поводу  внутренней и внешней политики компании. На основе этих данных принято решение произвести кластерный анализ и разбиение респондентов на активистов и оппозиционеров.  Но не все опрашиваемые были включены в число кластеров, если респондент не давал четкого ответа, или затруднялся в нем, значит он исключался. Таким образом, из выборки было изъято 1420 респондентов.

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

     В данной практике мы используем метод Уорда.

     

     На  данной дендограмме представлены результаты методом Уорда.

   Для каждой группы считается квадратичная Евклидова дистанция от средних величин переменных внутри кластера и средних величин переменных, присоединяемых к нему. Происходит деление совокупности на два крупных кластера, в один из которых входит четыре переменных в верхней части таблицы, а оставшиеся девятнадцать переменных - в другой. Далее, при детальном изучении полученных данных можно заметить, что большой кластер образован из двух возможных кластеров.

 

Заключение

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

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

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

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

1. http://www.ed.vseved.ru/
2. http://www.baltika.com
3. http://www.statsoft.ru/home/textbook/modules/stcluan.html
4. Магнус Я.Р., Катышев П.К., Пересецкий А.А. Эконометрика. Начальный курс: Учебник. – М.: Дело, 2001.