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

 

 

Введение

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

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

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

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

В 1925 г. советский гидробиолог  П.В. Терентьев разработал так называемый «метод корреляционных плеяд», предназначенный для группировки коррелирующих признаков. Этот метод дал толчок развитию методов группировки с помощью графов. Термин «кластерный анализ» впервые был предложен Трионом в 1939г. Слово «cluster» переводится с английского языка как «гроздь, кисть, пучок, группа». По этой причине первоначальное время этот вид анализа называли «гроздевым анализом». В начале 50-х годов появились публикации Р.Люиса, Е.Фикса и Дж. Ходжеса по иерархическим алгоритмам кластерного анализа. Заметный толчок развитие работ по кластерному анализу дали работы Р.Розенблатта по распознающему устройству (персептрону), положившие начало развитию теории «распознавания образов без учителя».

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

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

1.1 Понятие кластерный анализ

«Кластерный анализ - совокупность математических методов, предназначенных для формирования относительно «отдаленных» друг от друга групп «близких» между собой объектов по информации о расстояниях или связях (мерах близости) между ними. По смыслу аналогичен терминам: автоматическая классификация, таксономия, распознавание образов без учителя.» Такое определение кластерного анализа дано в последнем издании «Статистического словаря» (М.: Финансы и статистика, 1989. - 623с).

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

 

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

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

Кластерный анализ выполняет  следующие основные задачи:

- разработка типологии или классификации;

- исследование полезных концептуальных схем группирования объектов:

- порождение гипотез на основе исследования данных;

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

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

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

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

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

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

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

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

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

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

Кластерный анализ позволяет сокращать размерность данных, делать ее наглядной.

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

При всем при этом кластерный анализ предъявляет следующие требования к данным:

• показатели не должны коррелировать между собой;
• показатели должны быть безразмерными;
• распределение показателей должно быть близко к нормальному;
• показатели должны отвечать требованию «устойчивости», под которой понимается отсутствие влияния на их значения случайных факторов;
• выборка должна быть однородна, не содержать «выбросов».

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

Независимо от предмета изучения применение кластерного анализа  предполагает следующие этапы:

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

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

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

где 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) =

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

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

 k = 1, 2, ..., р

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

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

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

Тогда расстояние между  парами векторов 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 называют коэффициентом сходства.

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

Кластер имеет следующие  математические характеристики:

Центр кластера - это среднее геометрическое место точек в пространстве переменных.

Радиус кластера - максимальное расстояние точек от центра кластера.

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

Спорный объект - это объект, который по мере сходства может быть отнесен к нескольким кластерам.

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

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

Проводились исследования Фортьером и Соломоном, и было установлено, что число кластеров должно быть принято для достижения вероятности a того, что найдено наилучшее разбиение. Таким образом, оптимальное число разбиений является функцией заданной доли b наилучших или в некотором смысле допустимых разбиений во множестве  всех возможных. Общее рассеяние будет тем больше, чем выше доля b допустимых разбиений. Фортьер и Соломон разработали таблицу, по которой можно найти число необходимых разбиений. S(a, b) в зависимости от a и b (где a - вероятность того, что найдено наилучшее разбиение, b - доля наилучших разбиений в общем числе разбиений) Причем в качестве меры разнородности используется не мера рассеяния, а мера принадлежности, введенная Хользенгером и Харманом.² Значения S(a, b) приведены в таблице 1.

Таблица 1-Значения S(a, b)

b \ a	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