Кластерным анализом называются разнообразные формализованные процедуры построения классификаций объектов. Лидирующей наукой в развитии кластерного анализа была биология. Предмет кластерного анализа (от англ. «cluster» - гроздь, пучок, группа) был сформулирован в 1939 г. психологом Робертом Трионом. Классиками кластерного анализа являются американские систематики Роберт Сокэл и Питер Снит. Одно из важнейших их достижений в этой области - книга «Начала численной таксономии», выпущенная в 1963 году. В соответствии с основной идеей авторов, классификация должна строится не на смешении плохо формализованных суждений о сходстве и родстве объектов, а на результатах формализованной обработки результатов математического вычисления сходств/отличий классифицируемых объектов. Для выполнения этой задачи нужны были соответствующие процедуры, разработкой которых и занялись авторы.

Основные этапы кластерного анализа таковы:
1. выбор сравнимых друг с другом объектов;
2. выбор множества признаков, по которому будет проводиться сравнение, и описание объектов по этим признакам;
3. вычисление меры сходства между объектами (или меры различия объектов) в соответствии с избранной метрикой ;
4. группировка объектов в кластеры с помощью той или иной процедуры объединения ;
5. проверка применимости полученного кластерного решения.

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

Существует ли единственно правильное решение, которое надо найти, выбирая совокупность объектов, набор признаков, тип метрики и процедуру объединения? Нет. Чтобы доказать это, приведем фрагмент статьи, ссылка на которую дана в предыдущем абзаце.

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

На какой объект более похож объект А: на B или на C? Если использовать в качестве метрики сходства расстояние, то на C: |AC|<|AB|. А если полагаться на корреляцию между показанными на рисунке признаками (которую можно описать как угол между вектором, идущим к объекту из начала координат, и осью абсцисс), то на B: . А как правильно? А единственно правильного ответа нет. С одной стороны, взрослая жаба более похожа на взрослую лягушку (обе взрослые), с другой - на молодую жабу (обе жабы)! Правильность ответа зависит от того, что мы считаем более важным ".

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

8.2. Пример выполнения кластерного анализа "на пальцах"

Чтобы пояснить типичную логику кластерного анализа, рассмотрим его наглядный пример. Рассмотрим совокупность из 6 объектов (обозначенных буквами), охарактеризованных по 6 признакам самого простого типа: альтернативных, принимающих одно из двух значений: характерен (+) и нехарактерен (-). Описание объектов по принятым признакам называется "прямоугольной" матрицей. В нашем случае речь идет о матрице 6×6, т.е. ее можно считать вполне "квадратной", но в общем случае количество объектов в анализе может не быть равно количеству признаков, и "прямоугольная" матрица может иметь разное количество строк и столбцов. Итак, зададим "прямоугольную" матрицу (матрицу объекты/признаки):

Выбор объектов и описание их по определенному набору признаков соответствуют двум первым этапам кластерного анализа. Следующий этап - построение матрицы сходств или различий ("квадратной" матрицы, матрицы объекты/объекты). Для этого нам надо выбрать метрику. Поскольку наш пример носит условный характер, имеет смысл выбрать самую простую метрику. Как проще всего определить расстояние между объектами A и B? Посчитать количество отличий между ними. Как вы можете увидеть, объекты A и B отличаются по признакам 3 и 5, итого, расстояние между этими двумя объектами соответствует двум единицам.

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

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

Какие два объекта ближе всего друг к другу? B и F, они отличаются только по одному признаку. Суть кластерного анализа - в объединении подобных объектов в кластер. Объединяем объекты B и F в кластер (B F). Покажем это на схеме. Как вы видите, объекты объединены на том уровне, который соответствует дистанции между ними.

Рис. 8.2.1. Первый шаг кластеризации условного набора из 6 объектов

Теперь у нас не шесть объектов, а пять. Перестраиваем "квадратную" матрицу. Для этого нам потребуется определить, чему равно расстояние от каждого объекта до кластера. Растояние от A до B составляло 2 единицы, а от A до F - 3 единицы. Чему равно расстояние от A до (BF)? Правильного ответа тут нет. Вот, посмотрите, как расположены друг относительно друга эти три объекта.

Рис. 8.2.2. Взаимное расположение трех объектов

Может быть, расстояние от объекта до группы - это расстояние от объекта до ближайшего к нему объекта в составе группы, т .е., │A(BF) │=│AB │? Эта логика соответствует присоединению по максимальному сходству .

А может быть, расстояние от объекта до группы - это расстояние от объекта до наиболее удаленного от него объекта в составе группы, т .е., │A(BF) │=│AF │? Эта логика соответствует присоединению по минимальному сходству .

Можно также считать, что расстояние от объекта до группы - это среднее арифметическое расстояний от этого объекта до каждого из объектов в составе группы, т .е., │A(BF) │=(│AB │+│AF │)/2. Это решение называется присоединением по среднему сходству .

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

Теперь самой близкой парой объектов являются D и E. Объединим и их тоже.

Рис. 8.2.3. Второй шаг кластеризации условного набора из 6 объектов

Перестроим "квадратную" матрицу для четырех объектов.

Мы видим, что тут есть две возможности для объединения на уровне 2,5: присоединение A к (BF) и присоединение (BF) к (DE). Какую из них выбрать?

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

Рис. 8.2.4. Первый вариант третьего шага кластеризации условного набора из 6 объектов

Выбрав этот вариант, мы должны были бы построить такую "квадратную" матрицу 3×3.

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

Рис. 8.2.5. Второй вариант третьего шага кластеризации условного набора из 6 объектов

Ему соответствует такая матрица 3×3:

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

В таком случае, следующим шагом является объединение объектов A и C, показанный на рис. 8.6.

Рис. 8.2.6. Четвертый шаг кластеризации

Строим матрицу 2×2:

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

Рис. 8.2.7. Пятый и последний шаг кластеризации

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

Рис. 8.2.8. Окончательный вид древовидного графа, полученного в результате кластеризации

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

8.3. Принципиальные ограничения и недостатки кластерного анализа

Как интерпретировать граф, показанный на рис. 8.2.8? Однозначного ответа нет. Чтобы ответить на этот вопрос, надо понимать, какие данные и для какой цели мы кластеризовали. "На поверхности" лежит вывод, что мы зарегистрировали, что исходная совокупность из 6 объектов состоит из трех пар. Глядя на получившийся график, в этом трудно усомниться. Однако справедлив ли этот вывод?

Вернитесь к самой первой "квадратной" матрице 6×6 и убедитесь: объект E находился на расстоянии в две единицы и от объекта D, и от объекта F. Сходство E и D на итоговом "дереве" отражено, а вот то, что объект E был столь же близок к объекту F - потерялось без следа! Как это объяснить?

В том результате кластеризации, который показан на рис. 8.2.8, полностью отсутствует информация о дистанции │EF │, там есть только информация о дистанциях │DE │ и │(BF)(DE) │!

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

Указанное обстоятельство является одним из серьезных недостатков кластерного анализа.

Еще один из коварных недостатков кластерного анализа упомянут в статье

Задачи кластеризации в Data Mining

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.Задача кластеризации

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

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

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

где x j - представляет собой измерения 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 и эквивалентно расстоянию между G i и G j соответственно выбранным характеристикам (F 1 , F 2 , F 3 , ..., F р).

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

1. Евклидово расстояние d 2 (Х i , Х j) =

2. l 1 - нормаd 1 (Х i , Х j) =

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

k = 1, 2, ..., р

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

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

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

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

Понятием, противоположным расстоянию, является понятие сходства между объектами G i . и G j . Неотрицательная вещественная функция S(Х i ; Х j) = S i j называется мерой сходства, если:

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

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

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

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

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

2. Методы кластеризации

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим Ι = (Ι 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 ) .

В качестве меры расстояния возьмем квадрат евклидовой метрикиd i j 2 . и вычислим матрицу D = {d i j 2 }, где d i j 2 - квадрат расстояния между

Ι i и Ι j:

				….	Ι n
		d 12 2	d 13 2	….	d 1n 2
			d 23 2	….	d 2n 2
				….	d 3n 2
….				….	….
Ι n

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

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

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

	{ Ι i , Ι j }				….	Ι n
{ Ι i ; Ι j }		d i j 2 1	d i j 2 2		….	d i j 2 n
			d 12 2	d 1 3	….	d 1 2 n
					….	d 2 n
					….	d 3n

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

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

d i+j,k = ½ (d i k + d j k).

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

d i+j,k = min (d i k + d j k).

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

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

d i+j,k = A(w) min(d ik d jk) + B(w) max(d ik d jk), где

A(w) = , если d ik £ d jk

A(w) = , если d ik > d jk

B(w) = , если d i k £ d jk

B (w ) = , если d ik > d jk

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

d i+j,k =

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

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

d i+j,k = min (d i ,k d jk)

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

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

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

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

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

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

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

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

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

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

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

Таблица значений 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

Довольно часто критерием объединения (числа кластеров) становится изменение соответствующей функции. Например, суммы квадратов отклонений:

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

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

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

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

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

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

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

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

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

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

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

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

6. Данные

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

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

Z -вклад показывает, сколько стандартных отклонений отделяет данное наблюдение от среднего значения:

Где x i – значение данного наблюдения, – среднее, S – стандартное отклонение.

Среднее для Z -вкладов является нулевым и стандартное отклонение равно 1.

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

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

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

обобщенные показатели социально-экономического развития – 9 баллов;

показатели отраслевого распределения занятого населения – 7 баллов;

показатели распространенности наемного труда – 6 баллов;

показатели, характеризующие человеческий элемент производительных сил – 6 баллов;

показатели развития материальных производительных сил – 8 баллов;

показатель государственных расходов – 4балла;

«военно-экономические» показатели – 3 балла;

социально-демографические показатели – 4 балла.

Оценки экспертов отличались сравнительно высокой устойчивостью.

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

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

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

Рассмотрим некоторые приложения кластерного анализа.

1. Деление стран на группы по уровню развития.

Изучались 65 стран по 31 показателю (национальный доход на душу населения, доля населения занятого в промышленности в %, накопления на душу населения, доля населения, занятого в сельском хозяйстве в %, средняя продолжительность жизни, число автомашин на 1 тыс. жителей, численность вооруженных сил на 1 млн. жителей, доля ВВП промышленности в %, доля ВВП сельского хозяйства в %, и т.д.)

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

Первый шаг подобного анализа заключается в выявлении пары народных хозяйств, учтенных в матрице сходства, расстояние между которыми является наименьшим. Это, очевидно, будут наиболее сходные, похожие экономики. В последующем рассмотрении обе эти страны считаются единой группой, единым кластером. Соответственно исходная матрица преобразуется так, что ее элементами становятся расстояния между всеми возможными парами уже не 65, а 64 объектами – 63 экономики и вновь преобразованного кластера – условного объединения двух наиболее похожих стран. Из исходной матрицы сходства выбрасываются строки и столбцы, соответствующие расстояниям от пары стран, вошедших в объедение, до всех остальных, но зато добавляются строка и столбец, содержащие расстояние между кластером, полученным при объединении и прочими странами.

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

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

Дальнейшие процедуры аналогичны описанным выше: на каждом этапе матрица преобразуется так, что из нее исключаются два столбца и две строки, содержащие расстояние до объектов (пар стран или объединений – кластеров), сведенных воедино на предыдущей стадии; исключенные строки и столбцы заменяются столбцоми строкой, содержащими расстояния от новых объединений до остальных объектов; далее в измененной матрице выявляется пара наиболее близких объектов. Анализ продолжается до полного исчерпания матрицы (т. е. до тех пор, пока все страны не окажутся сведенными в одно целое). Обобщенные результаты анализа матрицы можно представить в виде дерева сходства (дендограммы), подобного описанному выше, с той лишь разницей, что дерево сходства, отражающее относительную близость всех рассматриваемых нами 65 стран, много сложнее схемы, в которой фигурирует только пять народных хозяйств. Это дерево в соответствиис числом сопоставляемых объектов включает 65 уровней. Первый (нижний) уровень содержит точки, соответствующие каждых стране в отдельности. Соединение двух этих точек на втором уровне показывает пару стран, наиболее близких по общему типу народных хозяйств. На третьем уровне отмечается следующее по сходству парное соотношение стран (как уже упоминалось, в таком соотношении может находиться либо новая пара стран, либо новая странаи уже выявленная пара сходных стран). И так далее до последнего уровня, на котором все изучаемые страны выступают как единая совокупность.

В результате применения кластерного анализа были получены следующие пять групп стран:

· афро-азиатская группа;

· латино-азиатская группа;

· латино-среднеземнаморская группа;

· группа развитых капиталистических стран (без США)

· США

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

2. Деление стран по критерию близости культуры.

Как известно маркетинг должен учитывать культуру стран (обычаи, традиции, и т.д.).

Посредством кластеризации были получены следующие группы стран:

· арабские;

· ближневосточные;

· скандинавские;

· германоязычные;

· англоязычные;

· романские европейские;

· латиноамериканские;

· дальневосточные.

3. Разработка прогноза конъюнктуры рынка цинка.

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

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

Например, задача разработки прогноза конъюнктуры рынка цинка.

Первоначально было отобрано 30 основных показателей мирового рынка цинка:

Х 1 - время

Показатели производства:

Х 2 - в мире

Х 4 - Европе

Х 5 - Канаде

Х 6 - Японии

Х 7 - Австралии

Показатели потребления:

Х 8 - в мире

Х 10 - Европе

Х 11 - Канаде

Х 12 - Японии

Х 13 - Австралии

Запасы цинка у производителей:

Х 14 - в мире

Х 16 - Европе

Х 17 - других странах

Запасы цинка у потребителей:

Х 18 - в США

Х 19 - в Англии

Х 10 - в Японии

Импорт цинковых руд и концентратов (тыс. тонн)

Х 21 - в США

Х 22 - в Японии

Х 23 - в ФРГ

Экспорт цинковых руд и концентратов (тыс. тонн)

Х 24 - из Канады

Х 25 - из Австралии

Импорт цинка (тыс. тонн)

Х 26 - в США

Х 27 - в Англию

Х 28 - в ФРГ

Экспорт цинка (тыс. Тонн)

Х 29 -из Канады

Х 30 - из Австралии

Для определения конкретныхзависимостей был использован аппарат корреляционно-регрессионногоанализа. Анализ связей производился на основе матрицы парных коэффициентов корреляции. Здесь принималась гипотеза о нормальном распределении анализируемых показателей конъюнктуры.Ясно, что r ij являются не единственно возможным показателем связи используемых показателей. Необходимость использования кластерного анализа связано в этой задачес тем, что число показателей влияющих нацену цинка очень велико. Возникает необходимость их сократить по целому ряду следующих причин:

а) отсутствие полных статистических данных по всем переменным;

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

в) оптимальное использование методов регрессионного анализа требует превышения числа наблюдаемых значений над числом переменных не менее, чем в 6-8 раз;

г) стремление к использованию в модели статистически независимых переменных и пр.

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

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

(j = 1, 2, …, m ),

где j - номер кластера, n - число элементов в кластере.

r ij -коэффициент парной корреляции.

Таким образом, процессу группировки должно соответствовать последовательное минимальное возрастание значения критерия E .

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

Кластерный анализ появился сравнительно недавно - в 1939 году. Его предложил ученый К. Трион. Дословно термин "кластер" в переводе с английского "cluster" означает кисть, сгусток, пучок, группа.

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

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

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

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

Основными задачами кластерного анализа являются:

Разработка типологии или классификации исследуемых объектов;

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

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

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

Кластерный анализ требует осуществления таких последовательных шагов:

1) проведение выборки объектов для кластеризации;

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

3) оценка степени сходства объектов;

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

5) проверка достоверности результатов кластерного решения.

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

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

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

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

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

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

осуществляются путем агломеративного (объединительных) действий. Они предусматривают следующие операции:

Последовательное объединение подобных объектов с образованием матрицы сходства объектов;

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

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

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

Одним из самых распространенных способов проведения итерационных процедур вот уже более сорока лет выступает метод k-средних (разработан в 1967 Дж. Маккуин). Применение его требует осуществления следующих шагов:

Разделение исходных данных исследуемой совокупности на заданное количество кластеров

Вычисление многомерных средних (центров тяжести) выделенных кластеров

Расчета Евклидовой расстояния каждой единицы совокупности определенных центров притяжения кластеров и построение матрицы расстояний, основанная на метрике расстояний. Используют различные метрики расстояний, например Евклидова расстояние (простая и взвешенная), Манхэттенский, Чебышева, Минковского, Махалонобиса и тому подобное;

Определение новых центов притяжения и новых кластеров.

Наиболее известными и широко применяемыми методами

формирование кластеров являются:

Единичного связи;

Полного связи;

Среднего связи;

Метод Уорда.

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

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

Метод средней связи основывается на использовании среднего расстояния между кандидатом на включение в кластер и представителями имеющегося кластера.

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

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

Исследователи применяют кластерный анализ в различных исследованиях, например при изучении уровня благосостояния населения стран СНГ (А. Мирошниченко). Сначала для этого были отобраны 16 статистических основных социально-экономических показателей, характеризующих уровень жизни граждан в различных странах СНГ:

1) ВВП в расчете на душу населения, дол. США;

2) среднемесячная номинальная заработная плата, рус. руб.;

3) среднемесячный размер пенсии, рус. руб.;

6) доля расходов на покупку продуктов питания в потребительских расходах домохозяйств, процентов;

7) потребление мяса и мясопродуктов в среднем за год в расчете на одного человека, кг;

8) количество пшеничного хлеба, что можно было бы приобрести на сумму среднего наличного денежного дохода в месяц (на одного человека), кг;

9) общий коэффициент рождаемости (на 1000 человек населения);

10) коэффициент младенческой смертности (умерло детей в возрасте до одного года на 1000 родившихся)

11) число занятых в процентах к экономически активному населению;

12) обеспеченность населения жильем в среднем (на одного человека), м2 общей площади;

13) количество больных злокачественными новообразованиями (на 100 000 населения), лиц;

14) количество зарегистрированных преступлений (на 100 000 населения), ед.;

15) выбросы вредных веществ в атмосферу стационарными источниками загрязнения (на одного человека), кг;

16) посещение музеев в среднем за год (на 1000 населения), ед. (табл. 12.7).

Кратера анализ осуществляется на основе сопоставим и однонаправленных показателей. Поэтому показатели входной матрицы следует сначала стандартизировать. Одним из распространенных способов для неоднородных совокупностей (в частности в нашем примере) является стандартизация показателей путем отношения отклонения - а к единице стандартизации q. В этом случае единицей стандартизации будет фактический вариационный размах.

При этом, как показано в научных трудах ученых-экономистов AM Ерин и С.С. Ващаев, для показателей-стимуляторов берется, тогда как для показателей-дестимуляторы. Исходя из этого, стандартизированные значения показателей рассчитываются по формулам:

Для показателей стимуляторов:;

Для показателей-дестимуляторы:.

где - стандартизированное значение i-ro показателя для у-й единицы совокупности,;

Входное значение i-го показателя для j-й единицы совокупности.

Полученные стандартизированные входные данные представлены в табл.12.8.

	Азербайджан	Беларусь		Казахстан	Кыргызстан			Таджикистан

Таблица 12.8. Матрица стандартизированных входных данных

	Азербайджан	Беларусь		Казахстан	Кыргызстан			Таджикистан

Следующим шагом кластерного анализа должна быть построение матрицы расстояний, предполагает прежде всего выбор метрики расстояний. На практике применяют различные метрики расстояний: Евклидова, взвешенная Евклидова, Манхэттенского, Чебышева, Минковского, Махалонобиса D 2 и др. В данном случае распределение стран СНГ на группы можно осуществить с помощью Манхэттенской расстояния. Она рассчитана по формуле

,

где и - стандартизированные значение i-го показателя j-й и k-й единиц совокупности.

Исходя из выбранной меры расстояний, можно построить симметричную матрицу расстояний между странами СНГ (табл. 12.9).

	Страны СНГ	Азербайджан	Беларусь		Казахстан	Кыргызстан			Таджикистан
	Азербайджан
	Беларусь
	Казахстан
	Кыргызстан
	Таджикистан

Следующим этапом анализа является выбор метода объединения стран СНГ в кластеры. Как уже отмечалось, наиболее распространенными методами формирования кластеров являются:

Единичного связи;

Полного связи;

Среднего связи;

Метод Уорда.

Воспользуемся методом Уорда, который позволяет минимизировать внутригрупповую дисперсию внутри кластеров. Согласно этому методу, присоединение объектов к кластерам осуществляется при минимальном прироста внутригрупповой суммы квадратов отклонений. Это способствует образованию кластеров примерно одинакового размера, которые имеют форму гиперсферу. Дендрограму результатов кластерного анализа показано на рис 12.5.

Рис. 12.5. Дендрограма результатов кластерного анализа стран СНГ по уровню жизни населения

Как видно из рисунка, вертикальная ось дендрограммы отражает страны СНГ, а горизонтальная является расстоянием объединения.

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

Рис. 12.6. График списке объединения стран СНГ в кластеры

Как видим оптимальным, согласно установленным требованиям оптимальности, является разбиение стран СНГ по уровню жизни населения на три кластера. Отметим, что оптимальной считается такое количество кластеров, равной разности количества наблюдений (в нашем примере - 9) и количества шагов, после которых расстояние объединения растет скачкообразно (в нашем примере - 6).

Таким образом, страны СНГ разделены на три кластера. К первому кластера вошли Азербайджан и Таджикистан, в другой - Беларусь, Украина, Россия и Казахстан, и третьего - Армения, Молдова и Кыргызстан.

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

Рис. 12.7. Средние значения показателей для каждого кластера

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

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

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

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

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

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

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

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

Пример использования

Имеем пять объектов, которые характеризуются по двум изучаемым параметрам – x и y .

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

Кластерный анализ: проблемы в использовании

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

Иерархический кластерный анализ

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

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

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

• одиночной и полной связи;
• средней взаимосвязи Кинга;
• центроидный метод;
• прием групповых средних.

Для оценки результатов кластеризации применяют следующие критерии:

• индекс четкости;
• коэффициент разбиения;
• обычная, нормализованная и модифицированная энтропия;
• второй и третий функционал Рубенса.

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

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