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

РЕФЕРАТ

Пояснительная записка : 31с., 2 рис., 6 источников

Объект исследования – анализ многомерных данных – кластерный анализ.

Цель работы – изучить методы анализа многомерных данных, а именно кластерный анализ.

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

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

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

АНАЛИЗ МНОГОМЕРНЫХ ДАННЫХ, КЛАСТЕРНЫЙ АНАЛИЗ, КАЧЕСВО КЛАСТЕРИЗАЦИИ, ФУНКЦИОНАЛЫ КАЧЕСТВА, НАСЕЛЕННОСТЬ КЛАСТЕРОВ, ДЕНДРОГРАММЫ

СОДЕРЖАНИЕ

Вступление                                                                                                         5

1 Кластерный анализ. Общие сведения                                                          7

1.1 Основные понятия                                                                                      7

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

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

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

4 Число кластеров                                                                                            17

5 Дендрограммы                                                                                              19

6 Применение к интервальным данным, частотам и бинарным данным  20

7 Решение задач с помощью кластерного анализа                                       23

Выводы                                                                                                            30

Перечень ссылок                                                                                              31

ВСТУПЛЕНИЕ

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

Кластерный анализ наиболее ярко отражает черты многомерного анализа в классификации, факторный анализ – в исследовании связи.

Иногда подход кластерного анализа называют в литературе численной таксономией, численной классификацией, распознаванием с самообучением и т.д.

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

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

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

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

В задачах  социально-экономического прогнозирования весьма перспективно сочетание кластерного анализа  с другими количественными методами (например, с регрессионным анализом).

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

В кластерном анализе считается, что:

а) выбранные характеристики допускают в принципе желательное разбиение на кластеры;

б) единицы измерения (масштаб) выбраны правильно.

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

1 Кластерный анализ. Общие сведения

Первое применение кластерный анализ нашел в социологии. Название кластерный анализ происходит от английского слова cluster – гроздь, скопление. Впервые в 1939 был определен предмет кластерного анализа и сделано его описание исследователем Трионом. Главное назначение кластерного анализа – разбиение множества исследуемых объектов и признаков на однородные в соответствующем понимании группы или кластеры. Это означает, что решается задача классификации данных и выявления соответствующей структуры в ней. Методы кластерного анализа можно применять в самых различных случаях, даже в тех случаях, когда речь идет о простой группировке, в которой все сводится к образованию групп по количественному сходству.

1.1 Основные понятия

Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования:

а) внутри групп объекты должны быть тесно связаны между собой;

б) объекты разных групп должны быть далеки друг от друга;

в) при прочих равных условиях распределения объектов по группам должны быть равномерными.

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

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

Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть wi — i-я группа (класс, кластер) объектов, Ni — число объектов, образующих группу wi, вектор i — среднее арифме­тическое объектов, входящих в wi (другими словами [i — «центр тяжести» i-й группы), a q ( wl, wm ) — расстояние меж­ду группами wl и wm

Рис.  1 Различные способы определения расстояния между кластерами wl и wm: 1 — по центрам тяжести, 2 — по ближайшим объектам, 3 — по самым далеким объектам

Расстояние ближайшего соседа есть расстояние между бли­жайшими объектами кластеров:

Расстояние дальнего соседа — расстояние между самыми дальними объектами кластеров:

Расстояние центров тяжести равно расстоянию между центральными точками кластеров:

Обобщенное (по Колмогорову) расстояние между классами, или обобщенное K-расстояние, вычисляется по формуле

В частности, при    и при   - имеем

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

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

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

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

Функционалы качества и конкретные алгоритмы автомати­ческой классификации достаточно полно и подробно рассмот­рены в специальной литературе. Эти функционалы и ал­горитмы характеризуются различной трудоемкостью и подчас требуют ресурсов высокопроизводительных компьютеров. Раз­нообразные процедуры кластерного анализа входят в состав практически всех современных пакетов прикладных программ для статистической обработки многомерных данных.

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