Реферат: Кластерный анализ в задачах социально-экономического прогнозирования

Глава 1.

КЛАСТЕРНЫЙ АНАЛИЗ В ЗАДАЧАХСОЦИАЛЬНО-ЭКОНОМИЧЕСКОГО ПРОГНОЗИРОВАНИЯ

1.1

Введение в кластерныйанализ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2

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

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

Например, пусть Gвключает n стран,любая из которых характеризуется ВНП на душу населения (F1), числом Мавтомашин на 1 тысячу человек (F2), душевым потреблениемэлектроэнергии (F3), душевым потреблением стали (F4) и т.д. Тогда Х1(вектор измерений) представляет собой набор указанных характеристик для первойстраны, Х2 — для второй, Х3 для третьей, и т.д. Задачазаключается в том, чтобы разбить страны по уровню развития.

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

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

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

Понятно то, что объекты i

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

а) d(Хi, Хj) ³

0,для всех Хiи Хj из Ер

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

= Хj

в) d(Хi, Хj) = d(Хj, Хi

)

г) d(Хi, Хj) £

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

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

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

1. Евклидово расстояние d2(Хi, Хj) = <img src="/cache/referats/3361/image004.gif" v:shapes="_x0000_i1026">

2. l1 — норма d1(Хi, Хj) = <img src="/cache/referats/3361/image006.gif" v:shapes="_x0000_i1027">

3. Сюпремум — норма d¥

(Хi, Хj) = sup<img src="/cache/referats/3361/image008.gif" v:shapes="_x0000_i1028">

k = 1, 2, ..., р

4. lp — норма dр(Хi, Хj) = <img src="/cache/referats/3361/image010.gif" v:shapes="_x0000_i1029">

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

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

Тогда расстояние междупарами векторов d(Хi

, Хj)могут быть представлены в виде симметричной матрицы расстояний:

Понятием, противоположнымрасстоянию, является понятие сходства между объектами Gi

.иGj. Неотрицательнаявещественная функция S(Хi; Хj) = Sij называетсямерой сходства, если :

1) 0£

S(Хi, Хj)<1 для Хi¹Хj

2) S(Хi, Хi) = 1

3) S(Хi, Хj) = S(Хj, Хi

)

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

Величину Sijназывают коэффициентомсходства.

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

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

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

и Хj определяется по формуле:

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

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

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

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

3)Метод Ворда.

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

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

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

d2ij = (`

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

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

Рассмотрим Ι = (Ι1, Ι2,… Ιn)как множество кластеров {Ι1},{Ι2},…{Ιn}.Выберем два из них, например, Ιi

и Ιj, которые в некотором смысле более близки друг кдругу и объединим их в один кластер. Новое множество кластеров, состоящее ужеиз n-1 кластеров, будет:

{Ι1}, {Ι2}…,{Ιi

, Ιj}, …, {Ιn}.

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

В качестве меры расстояниявозьмем квадрат евклидовой метрики di

j2. и вычислим матрицу D= {dij2}, где dij2 — квадрат расстояния между

Ιi

и Ιj:

Ι1

Ι2

Ι3

….

Ιn

Ι1

d122

d132

….

d1n2

Ι2

d232

….

d2n2

Ι3

….

d3n2

….

Ιn

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

di

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

{Ιi, Ιj}. Построим новую ((n-1), (n-1))матрицу расстояния

{Ιi, Ιj}

Ι1

Ι2

Ι3

….

Ιn

{Ιi; Ιj}

dij21

dij22

di j23

….

di j2n

Ι1

d122

d13

….

d12n

Ι2

di j21

….

d2n

Ι3

….

d3n

Ιn

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

i ¹j)через элементы первоначальной матрицы.

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

di+j,k= ½ (di k+ dj k).

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

di+j,k = min (di k+ dj k).

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

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

di+j,k= A(w)min(dikdjk) + B(w) max(dikdjk), где

A(w) = <img src="/cache/referats/3361/image020.gif" v:shapes="_x0000_i1034">, еслиdik£

djk

A(w) = <img src="/cache/referats/3361/image022.gif" v:shapes="_x0000_i1035">еслиdik>

djk

B(w) =<img src="/cache/referats/3361/image024.gif" v:shapes="_x0000_i1036">, если di

k£djk

B(w) = <img src="/cache/referats/3361/image026.gif" v:shapes="_x0000_i1037">еслиdik >

djk

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

di+j,k= <img src="/cache/referats/3361/image028.gif" v:shapes="_x0000_i1038">

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

Наглядный смысл параметра wстановится понятным, если положить w ®

¥. Формула пересчета расстоянийпринимает вид:

di+j,k= min (di

,kdjk)

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

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

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

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

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

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

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

где mi ,mj,d

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

1.5 Число кластеров.

Очень важным вопросомявляется проблема выбора необходимого числа кластеров. Иногда можно mчислокластеров выбирать априорно. Однако в общем случае это число определяется впроцессе разбиения множества накластеры.

Проводились исследованияФортьером и Соломоном, и было установлено, что число кластеров должно бытьпринято для достижения вероятности a

того, что найдено наилучшееразбиение. Таким образом, оптимальное число разбиений является функциейзаданной доли bнаилучших или в некоторомсмысле допустимых разбиений во множестве всех возможных. Общее рассеяние будет тем больше, чем выше доля bдопустимых разбиений. Фортьери Соломон разработали таблицу, по которой можно найти число необходимыхразбиений. S(a,b)в зависимости от aи b(где a — вероятность того, чтонайдено наилучшее разбиение, b — доля наилучших разбиений вобщем числе разбиений) Причем в качестве меры разнородности используется немера рассеяния, а мера принадлежности, введенная Хользенгером и Харманом.Таблица значений S(a,b)приводится ниже.Таблица значений S(a,b)ba 0.20 0.10 0.05 0.01 0.001 0.0001 0.20 8 11 14 21 31 42 0.10 16 22 29 44 66 88 0.05 32 45 59 90 135 180 0.01 161 230 299 459 689 918 0.001 1626 2326 3026 4652 6977 9303 0.0001 17475 25000 32526 55000 75000 100000

Довольно часто критериемобъединения (числа кластеров) становится изменение соответствующей функции.Например, суммы квадратов отклонений: <img src="/cache/referats/3361/image038.gif" v:shapes="_x0000_i1043">

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

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

1.6 Дендограммы.

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

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

Рис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.

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

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

Иерархические алгоритмысвязаны с построением дендограмм и делятся на:

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

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

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

1.7 Данные

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

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

еще рефераты

Еще работы по математике

Реферат по математике

Геометрия Лобачевского

20 Июня 2015

Реферат по математике

Опыт использования ЭВМ на уроках математики

29 Августа 2013

Реферат по математике

Гениальные математики Бернулли

29 Августа 2013

Реферат по математике

Комбинаторика

3 Августа 2015