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

ВВЕДЕНИЕ		3
1.	Определение и задача кластерного  анализа	5
1.1	Определение кластерного  анализа	5
1.2.	Задача кластерного  анализа. Функции расстояния и меры сходства.	7
2.	Методы кластерного  анализа	11
2.1.	Иерархические агломеративные методы	13
2.2.	Итеративные методы группировки. Метод k-средних	17
3.	Кластерный анализ в  программе Statistica	21
ЗАКЛЮЧЕНИЕ		29
СПИСОК ИСТОЧНИКОВ И  ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ		30
Приложение 1 Статистические данные
Приложение 2 Дендрограмма с нанесенными линиями пороговых расстояний
Приложение 3 Объединения объектов методом Уорда
Приложение 4 Выделение классов на дендрограмме
Приложение 5  Отсортированные по алфавиту данные с номерами                        классов

 Содержание

 

ВВЕДЕНИЕ

 

"Кластерный анализ  – совокупность математических  методов, предназначенных для  формирования относительно "отдаленных" друг от друга групп "близких"  между собой объектов по информации  о расстояниях или связях (мерах  близости) между ними, распознавание  образов без учителя" .

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

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

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

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

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

 

Глава 1. Определение и задача кластерного  анализа

1.1. Определение  кластерного анализа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

1.2. Задача кластерного анализа. Функции расстояния и меры сходства.

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

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

 

 

 

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

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

Введём понятие "расстояние между объектами". Данное понятие  является интегральной мерой сходства объектов между собой. Объекты i-ый и j-ый состояли бы в одном кластере, когда расстояние (отдаленность) между точками Х_i и Х_j было бы достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между Х_i и Х_j из Е_р, где Е_р - р-мерное евклидово пространство. Расстоянием между объектами в пространстве признаков называется такая неотрицательная функция , которая является функцией расстояния (метрикой) удовлетворяя следующим аксиомам:

 

а) ≥ 0, для всех Х_i и Х_j из Е_р

б) = 0, тогда и только тогда, когда Х_i = Х_j

в) =

г) ≤ + , где Х_j; Х_i и Х_k - любые три вектора из Е_р.

Значение d(Х_i, Х_j) для Х_i и Х_j называется расстоянием между Х_i и Х_j и эквивалентно расстоянию между x_i и x_j соответственно выбранным характеристикам (F₁, F₂, F₃, ..., F_р).

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

1. Евклидова метрика 

Наиболее распространенная функция расстояния. Представляет собой  геометрическим расстоянием в многомерном  пространстве:

 

где  X_i , X_j - координаты i-го и j-го объектов в p-мерном пространстве;

 – величина k -той компоненты у i-го (j-го) объекта (k=1,2,...,p, i,j=1,2,...,n).

2. Квадрат евклидова расстояния

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

 

 

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

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

 

4. Расстояние Чебышева

Это расстояние может оказаться  полезным, когда нужно определить два объекта как «различные», если они различаются по какой-либо одной координате. Расстояние Чебышева вычисляется по формуле:

 

5. Степенное расстояние

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

 

где r и p – параметры, определяемые пользователем. Параметр p ответственен за постепенное взвешивание разностей по отдельным координатам, параметр r ответственен за прогрессивное взвешивание больших расстояний между объектами. Если оба параметра – r и p — равны двум, то это расстояние совпадает с расстоянием Евклида.

 

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

Пусть n измерений Х₁, Х₂,..., Х_n представлены в виде матрицы данных размером p×n:

Тогда расстояние между парами векторов могут быть представлены в виде симметричной матрицы расстояний:

Меру близости (сходства) объектов удобно представить как обратную величину от расстояния между объектами. Т.е. это является понятие сходства между объектами G_i. и G_j. Неотрицательная вещественная функция S(Х_i ; Х_j) = S_ij называется мерой сходства, если :