Приветствую!

В своей дипломной работе я проводил обзор и сравнительный анализ алгоритмов кластеризации данных. Подумал, что уже собранный и проработанный материал может оказаться кому-то интересен и полезен.
О том, что такое кластеризация, рассказал sashaeve в статье «Кластеризация: алгоритмы k-means и c-means» . Я частично повторю слова Александра, частично дополню. Также в конце этой статьи интересующиеся могут почитать материалы по ссылкам в списке литературы.

Так же я постарался привести сухой «дипломный» стиль изложения к более публицистическому.

Понятие кластеризации

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

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

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

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

Меры расстояний

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

После того, как мы определили вектор характеристик, можно провести нормализацию, чтобы все компоненты давали одинаковый вклад при расчете «расстояния». В процессе нормализации все значения приводятся к некоторому диапазону, например, [-1, -1] или .

Наконец, для каждой пары объектов измеряется «расстояние» между ними - степень похожести. Существует множество метрик, вот лишь основные из них:

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

Классификация алгоритмов

Для себя я выделил две основные классификации алгоритмов кластеризации.

1. Иерархические и плоские.
   Иерархические алгоритмы (также называемые алгоритмами таксономии) строят не одно разбиение выборки на непересекающиеся кластеры, а систему вложенных разбиений. Т.о. на выходе мы получаем дерево кластеров, корнем которого является вся выборка, а листьями - наиболее мелкие кластера.
   Плоские алгоритмы строят одно разбиение объектов на кластеры.
2. Четкие и нечеткие.
   Четкие (или непересекающиеся) алгоритмы каждому объекту выборки ставят в соответствие номер кластера, т.е. каждый объект принадлежит только одному кластеру. Нечеткие (или пересекающиеся) алгоритмы каждому объекту ставят в соответствие набор вещественных значений, показывающих степень отношения объекта к кластерам. Т.е. каждый объект относится к каждому кластеру с некоторой вероятностью.

Объединение кластеров

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

1. Одиночная связь (расстояния ближайшего соседа)
   В этом методе расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. Результирующие кластеры имеют тенденцию объединяться в цепочки.
2. Полная связь (расстояние наиболее удаленных соседей)
   В этом методе расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. наиболее удаленными соседями). Этот метод обычно работает очень хорошо, когда объекты происходят из отдельных групп. Если же кластеры имеют удлиненную форму или их естественный тип является «цепочечным», то этот метод непригоден.
3. Невзвешенное попарное среднее
   В этом методе расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них. Метод эффективен, когда объекты формируют различные группы, однако он работает одинаково хорошо и в случаях протяженных («цепочечного» типа) кластеров.
4. Взвешенное попарное среднее
   Метод идентичен методу невзвешенного попарного среднего, за исключением того, что при вычислениях размер соответствующих кластеров (т.е. число объектов, содержащихся в них) используется в качестве весового коэффициента. Поэтому данный метод должен быть использован, когда предполагаются неравные размеры кластеров.
5. Невзвешенный центроидный метод
   В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести.
6. Взвешенный центроидный метод (медиана)
   Этот метод идентичен предыдущему, за исключением того, что при вычислениях используются веса для учета разницы между размерами кластеров. Поэтому, если имеются или подозреваются значительные отличия в размерах кластеров, этот метод оказывается предпочтительнее предыдущего.

Обзор алгоритмов

Алгоритмы иерархической кластеризации

Среди алгоритмов иерархической кластеризации выделяются два основных типа: восходящие и нисходящие алгоритмы. Нисходящие алгоритмы работают по принципу «сверху-вниз»: в начале все объекты помещаются в один кластер, который затем разбивается на все более мелкие кластеры. Более распространены восходящие алгоритмы, которые в начале работы помещают каждый объект в отдельный кластер, а затем объединяют кластеры во все более крупные, пока все объекты выборки не будут содержаться в одном кластере. Таким образом строится система вложенных разбиений. Результаты таких алгоритмов обычно представляют в виде дерева – дендрограммы. Классический пример такого дерева – классификация животных и растений.

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

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

Алгоритмы квадратичной ошибки

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

Где c j - «центр масс» кластера j (точка со средними значениями характеристик для данного кластера).

Алгоритмы квадратичной ошибки относятся к типу плоских алгоритмов. Самым распространенным алгоритмом этой категории является метод k-средних. Этот алгоритм строит заданное число кластеров, расположенных как можно дальше друг от друга. Работа алгоритма делится на несколько этапов:

1. Случайно выбрать k точек, являющихся начальными «центрами масс» кластеров.
2. Отнести каждый объект к кластеру с ближайшим «центром масс».
3. Пересчитать «центры масс» кластеров согласно их текущему составу.
4. Если критерий остановки алгоритма не удовлетворен, вернуться к п. 2.

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

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

Нечеткие алгоритмы

Наиболее популярным алгоритмом нечеткой кластеризации является алгоритм c-средних (c-means). Он представляет собой модификацию метода k-средних. Шаги работы алгоритма:

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

Алгоритмы, основанные на теории графов

Суть таких алгоритмов заключается в том, что выборка объектов представляется в виде графа G=(V, E) , вершинам которого соответствуют объекты, а ребра имеют вес, равный «расстоянию» между объектами. Достоинством графовых алгоритмов кластеризации являются наглядность, относительная простота реализации и возможность вносения различных усовершенствований, основанные на геометрических соображениях. Основными алгоритмам являются алгоритм выделения связных компонент, алгоритм построения минимального покрывающего (остовного) дерева и алгоритм послойной кластеризации.

Алгоритм выделения связных компонент

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

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

Алгоритм минимального покрывающего дерева

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

Путём удаления связи, помеченной CD, с длиной равной 6 единицам (ребро с максимальным расстоянием), получаем два кластера: {A, B, C} и {D, E, F, G, H, I}. Второй кластер в дальнейшем может быть разделён ещё на два кластера путём удаления ребра EF, которое имеет длину, равную 4,5 единицам.

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

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

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

,

Где G t = (V, E t) - граф на уровне с t ,
,
с t – t-ый порог расстояния,
m – количество уровней иерархии,
G 0 = (V, o) , o – пустое множество ребер графа, получаемое при t 0 = 1,
G m = G , то есть граф объектов без ограничений на расстояние (длину ребер графа), поскольку t m = 1.

Посредством изменения порогов расстояния {с 0 , …, с m }, где 0 = с 0 < с 1 < …< с m = 1, возможно контролировать глубину иерархии получаемых кластеров. Таким образом, алгоритм послойной кластеризации способен создавать как плоское разбиение данных, так и иерархическое.

Сравнение алгоритмов

Вычислительная сложность алгоритмов

Сравнительная таблица алгоритмов

Алгоритм кластеризации	Форма кластеров	Входные данные	Результаты
Иерархический	Произвольная	Число кластеров или порог расстояния для усечения иерархии	Бинарное дерево кластеров
k-средних	Гиперсфера	Число кластеров	Центры кластеров
c-средних	Гиперсфера	Число кластеров, степень нечеткости	Центры кластеров, матрица принадлежности
Выделение связных компонент	Произвольная	Порог расстояния R
Минимальное покрывающее дерево	Произвольная	Число кластеров или порог расстояния для удаления ребер	Древовидная структура кластеров
Послойная кластеризация	Произвольная	Последовательность порогов расстояния	Древовидная структура кластеров с разными уровнями иерархии

Немного о применении

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

В отличие от полносвязного графа, в ориентированном дереве не все вершины соединены ребрами, при этом общее количество ребер равно n–1, где n – число вершин. Т.е. применительно к узлам дерева, работа алгоритма выделения связных компонент упростится, поскольку удаление любого количества ребер «развалит» дерево на связные компоненты (отдельные деревья). Алгоритм минимального покрывающего дерева в данном случае будет совпадать с алгоритмом выделения связных компонент – путем удаления самых длинных ребер исходное дерево разбивается на несколько деревьев. При этом очевидно, что фаза построения самого минимального покрывающего дерева пропускается.

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

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

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

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

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

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

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

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

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

Иерархические (древовидные) процедуры - наиболее распространённые алгоритмы кластерного анализа по их реализации на ЭВМ. Различают агломеративные (от слова agglomerate - собирать) и итеративные дивизивные (от слова division - разделять) процедуры.

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

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

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

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

иерархического объединения в кластеры:

• 1. Правило одиночной связи. На первом шаге объединяются два наиболее близких объекта, т.е. имеющие максимальную меру сходства. На следующем шаге к ним присоединяется объект с максимальной мерой сходства с одним из объектов кластера, т.е. для его включения в кластер требуется максимальное сходство лишь с одним членом кластера. Метод называют еще методом ближайшего соседа, так как расстояние между двумя кластерами определяется как расстояние между двумя наиболее близкими объектами в различных кластерах. Это правило "нанизывает" объекты для формирования кластеров. Недостаток данного метода - образование слишком больших продолговатых кластеров.
• 2. Правило полных связей. Метод позволяет устранить недостаток, присущий методу одиночной связи. Суть правила в том, что два объекта, принадлежащих одной и той же группе (кластеру), имеют коэффициент сходства, который больше некоторого порогового значения S. В терминах евклидова расстояния это означает, что расстояние между двумя точками (объектами) кластера не должно превышать некоторого порогового значения d. Таким образом, d определяет максимально допустимый диаметр подмножества, образующего кластер. Этот метод называют еще методом наиболее удаленных соседей, так как при достаточно большом пороговом значении d расстояние между кластерами определяется наибольшим расстоянием между любыми двумя объектами в различных кластерах.
• 3. Правило невзвешенного попарного среднего. Расстояние между двумя кластерами определяется как среднее расстояние между всеми парами объектов в них. Метод эффективен, когда объекты в действительности формируют различные группы, однако он работает одинаково хорошо и в случаях протяженных (цепочного типа) кластеров.
• 4. Правило взвешенное попарное среднее. Метод идентичен предыдущему, за исключением того, что при вычислении размер соответствующих кластеров используется в качестве весового коэффициента. Желательно этот метод использовать, когда предполагаются неравные размеры кластеров.
• 5. Невзвешенный центроидный метод. Расстояние между двумя кластерами определяется как расстояние между их центрами тяжести.
• 6. Взвешенный центроидный метод. Идентичен предыдущему, за исключением того, что при вычислениях расстояния используют веса для учета разности между размерами кластеров. Поэтому, если имеются (или подозреваются) значительные отличия в размерах кластеров, этот метод оказывается предпочтительнее предыдущего.
• 7. Правило Уорда (Варда). В этом методе в качестве целевой функции применяют внутригрупповую сумму квадратов отклонений, которая есть не что иное, как сумма квадратов расстояний между каждой точкой (объектом) и средней по кластеру, содержащему этот объект. На каждом шаге объединяются такие два кластера, которые приводят к минимальному увеличению целевой функции, т.е. внутригрупповой суммы квадратов отклонений. Этот метод направлен на объединение близко расположенных кластеров. Замечено, что метод Уорда приводит к образованию кластеров примерно равных размеров и имеющих форму гиперсфер.

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

Метод k-средних

Предположим, есть гипотезы относительно числа m кластеров (по переменным или наблюдениям). Тогда можно задать программе создать ровно m кластеров так, чтобы они были настолько различны, насколько это возможно. Именно для решения задач этого типа предназначен метод k-means (k-средних). Гипотеза может основываться на теоретических соображениях, результатах предшествующих исследований или догадке. Выполняя последовательное разбиение на различное число кластеров, можно сравнивать качество получаемых решений.

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

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

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

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

Методы кластерного анализа можно расклассифицировать на:

• внутренние (признаки классификации равнозначны);
• внешние (существует один главный признак, остальные определяют его).

Внутренние методы в свою очередь можно разделить на:

• иерархические (процедура классификация имеет древовидную структуру);
• неиерархические.

• агломеративные (объединяющие);
• дивизивные (разъединяющие).

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

Пусть объекты i и j принадлежат множеству M и каждый объект описывается k признаками, тогда будем говорить, что на множестве M задана метрика, если для любой пары объектов, принадлежащих множеству M, определено неотрицательное число d ij , удовлетворяющее следующим условиям (аксиомам метрики):

1. Аксиома тождества: d ij = 0 ⇔ i ≡ j .
2. Аксиома симметричности: d ij = d ji ∀ i , j .
3. Неравенство треугольника: ∀ i , j , z ∈M, выполняется неравенство d iz ≤ d ij + d zj .

Пространство, на котором введена метрика, называется метрическим. Наиболее используемыми являются следующие метрики:

1. Метрика Евклида:

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

2. Метрика нормированного Евклида. Нормализованные евклидовы расстояния более подходят для переменных, измеряемых в различных единицах или значительно различающихся по величине.

Если дисперсии по характеристикам отличаются друг от друга, то:

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

3. Метрика city-block (манхэттенская метрика, получившая свое название в честь района Манхэттен, который образуют улицы, расположенные в виде пересечения параллельных прямых под прямым углом; как правило, применяется для номинальных или качественных переменных):

4. Метрика на основе корреляции: d ij =1- |r ij |.

5. Метрика Брея-Картиса, которая также используется для номинативных и ранговых шкал, обычно данные предварительно стандартизируются:

Расстояния, вычисляемые на основе коэффициента корреляции, отражают согласованность колебаний оценок, в отличие от метрики Евклида, которая определяет схожесть в среднем. Выбор метрики определяется задачей исследования и типом данных. Помимо приведенных выше методов, разработаны метрики для ранговых и дихотомических переменных и т.д. (во всех выше приведенных формулах i,j – номера столбцов; k – номер строки; d ij – элемент матрицы расстояний; x ik , x jk – элементы исходной матрицы; n – количество объектов).

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

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

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

Далее чередование пунктов 1 и 2 производится до тех пор, пока все объекты не будут объединены в один класс. Графическое представление результатов обычно осуществляется в виде дерева иерарахической кластеризации. По оси X располагаются классифицируемые объекты (на одинаковом расстоянии друг от друга); по оси Y – расстояния, на основании которых происходит объединение объектов в кластеры. Для определения «естественного» числа кластеров применяется критерий разбиения на классы в виде отношения средних внутрикластерных расстояний к межкластерным расстояниям. Глобальный минимум соответствует «естественному» числу классов, а локальные минимумы – под- и над- структурам (нижним и верхним границам).

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

При объединении i -го и j- го классов в класс k , расстояние между новым классом k и любым другим классом h пересчитывается одним из приведенных ниже способов (стратегии объединения). Расстояния между другими классами сохраняются неизменными. Наиболее распространенными являются следующие стратегии объединения (название несколько не соответствует содержанию; в соответствии с выбранными формулами производится пересчет расстояния от объектов до вновь образованного класса):

1. Стратегия «ближайшего соседа» – сужает пространство (классы объединяются по ближайшей границе)

2. Стратегия «дальнего соседа» – растягивает пространство (классы объединяются по дальней границе):

3. Стратегия «группового среднего» – не изменяет пространство (объекты объединяются в соответствии с расстоянием до центра класса) :

где n i , n j , n k – число объектов соответственно в классах i , j , k .

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

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

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

Таблица 1. Матрица смешения для коллектива из 9 человек

Используя метрику Евклида, получаем симметричную матрицу расстояний, которая является основой для кластерного анализа.

Таблица 2. Матрица расстояний, полученная с использованием метрики Евклида

Результат применения агломеративного иерархического метода КА к полученной матрице при использовании пакета STATISTICA – дерево классификации – представлен на рис.1.: по горизонтальной оси откладываются на одинаковом расстоянии номера объектов (членов команды), по вертикальной оси – расстояние, на котором объединяются эти объекты.

Можно заметить, что выделилось два класса: в один вошли объекты 5, 8, 9, 7, 6, 4, а в другой – 3, 2, 1. Отделимость классов оценивается сравнением внутрикластерных и межкластерных расстояний на качественном уровне.

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

Рис. 1. Дерево классификации

Для определения «естественного» числа кластеров, на которые может быть разбита совокупность объектов, а возможно, и для выделения более «тонкой» структуры применялся следующий критерий: на каждом уровне иерархической кластеризации выполнялось разбиение множества на данное число классов. В основу примененной для этого формулы была заложена идея физической плотности или, точнее, объема пространства, занимаемого данным множеством объектов (Савченко, Рассказова, 1989). Для каждой пары кластеров оценивалась степень их внутренней связанности друг с другом. Для этого вычислялось среднее внутрикластерное расстояние для каждого кластера из заданной пары; если при этом в класс входит всего один элемент, то расстояние соответствует минимальному расстоянию до какого-либо из элементов. Если в классе более одного элемента, но все различия между ними равны 0, то в формуле отражается аналогия с объемом пространства, занимаемого одним объектом. Формула учитывает, что в данном случае в одной точке пространства находится лишь один объект с большей «удельной плотностью».

В качестве оценки связанности берется отношение среднего внутрикластерного расстояния к межкластерному:

где а i и а j – средние внутрикластерные расстояния классов i и j ; b ij – среднее межкластерное расстояние между этими же классами.

Оценка «естественного» разбиения производится по следующей формуле:

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

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

Однако в стандартных пакетах, как отмечалось выше, такая оценка, к сожалению, не предусмотрена. Для получения более детальной информации о полученных классах используются другие методы кластеризации: например, дендритный анализ дает возможность проследить близость объектов в классах и более подробно изучить их структуру; метод k -means позволяет качественно описать каждый класс объектов и провести сравнительный анализ степени выраженности исследуемых характеристик у представителей обоих классов.

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

Итак, объекты – это вершины дендрита, а расстояния между ними – дуги. На первом этапе к каждому объекту находится ближайший (находящийся к нему на минимальном расстоянии) объект и составляются пары. Число пар равно числу объектов. Далее, если есть симметричные пары (например: i______j, j_____i), то одна из них убирается; если в двух парах присутствует один и тот же элемент, то пары объединяются через этот элемент. Например, две пары:

i__________j ,

j______k

объединяются в связку i ___________j ________k .

На этом заканчивается построение скоплений (плеяд) первого порядка. Затем определяются минимальные расстояния между объектами скоплений первого порядка, и эти скопления объединяются до тех пор, пока не будет построен дендрит. Группы объектов считаются вполне отделимыми, если длина дуги между ними d lk > C p , где C p = С ср + S , С ср – средняя длина дуги, S – стандартное отклонение.

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

Применение дендритного анализа к рассматриваемым данным позволило получить следующий дендрит (см. рис. 2).

Итак, в описанном выше случае C p = 4.8. Это означает, что выделяются три класса, что несколько отличается от результата, полученного с помощью агломеративного метода. Из первого класса, в который входили объекты 1, 3, 2, отделился первый член коллектива. Во второй класс вошли объекты 8, 4, 9, 7, 6, 5 (аналогично результатам, полученным с помощью агломеративного метода).

Рис. 2. Дендрит (форма простого дерева): над дугами дендрита указаны расстояния между объектами

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

Помимо агломеративных иерархических методов существует также большое количество итеративных методов кластерного анализа . Основное отличие их состоит в том, что процесс классификации начинается с задания начальных условий: это может быть число классов, критерий завершения классификации и т.д. К таким методам относятся, например, дивизивные методы, методы k-means и другие, требующие от исследователя интуиции и творческого подхода. Еще до проведения классификации необходимо представлять, какое количество классов должно быть образовано, когда закончить процесс классификации и т.д. От верно выбранных начальных условий будет зависеть результат классификации, поскольку некорректно выбранные условия могут приводить к «размытости» классов. Таким образом, эти методы используются, если есть теоретическое обоснование, например, количества ожидаемых классов, а также после проведения иерархических методов классификации, которые позволяют выработать наиболее оптимальную стратегию исследования.

Метод k-means можно отнести к итеративным методам эталонного типа. Название ему было дано Дж. Мак-Куином. Существует много различных модификаций данного метода. Рассмотрим одну из них.

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

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

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

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

Пусть эталоны представлены таким образом:

Тогда если рассматриваемый объект j относится к эталону k , то данный эталон (т.е. центр образовавшегося класса) пересчитывается следующим образом:

здесь v jo – вес эталона j в нулевой итерации.

Остальные эталоны остаются неизменными.

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

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

Обычно в методе k-means реализуется процедура построения усредненных профилей каждого класса (см. рис. 3), что дает возможность проводить качественный анализ выраженности признаков у представителей каждого класса. Для сравнения классов по выраженности тех или иных характеристик используется процедура, подобная ANOVA, сравнивающая внутрикластерные и межкластерные дисперсии по каждой характеристике и тем самым позволяющая осуществить проверку значимости различия классов по исследуемым характеристикам.

Рис. 3. Усредненные профили классов

Таблица 3. Номера объектов и расстояния от центра классов

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

Таблица 4. Анализ отделимости классов (жирным шрифтом выделены те характеристики, по которым наблюдается значимое различие между классами).

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

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

Формальное описание ситуации сводится к следующему. Задано множество M элементов А 1 , А 2 ,…, А n и множество типов попарной близости этих элементов. Пусть количество этих типов m. Различные типы близости отличаются друг от друга тем, что каждый представляет собой близость по какому-либо качеству, присущему всем элементам множества. Таким образом, выделяются m качеств каждого элемента и производится сравнение (вычисление расстояний или различий) по каждому из этих качеств, что и дает m типов близости элементов. Для каждого типа близости задается матрица попарных расстояний (или различий), отражающая структуру множества элементов m по отношению к данному типу близости. Всего должно быть задано m таких матриц.

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

1. Ассоциативный кластер. Согласно Выготскому, в ассоциативном комплексе прежде всего выделяется элемент, который будет образовывать его ядро, затем остальные элементы объединяются с ядром. И здесь Выготский отмечает следующую характерную особенность данного комплекса: «Элементы могут быть вовсе не объединены между собой. Единственным принципом их обобщения является их фактическое родство с основным ядром комплекса. Связь, объединяющая их с этим последним, может быть любой ассоциативной связью» (Выготский, 1982, с. 142).

Дадим описание простейшего варианта алгоритма образования ассоциативного кластера в терминах приведенной выше формальной схемы. Сначала из заданного множества M элементов выбирается один, который будет играть роль ядра ассоциативного кластера. Ясно, что можно построить столько ассоциативных кластеров, сколько элементов в множестве M , выбирая поочередно в качестве ядра все элементы множества. Итак, выберем один элемент A k . Далее, по каждому качеству (т.е. для каждой матрицы расстояний) выбирается элемент, ближайший к элементу A k . Таким образом, мы получаем m или более элементов, если по каким-либо признакам выделяются два или более элементов, отстоящих от A k на одно и то же минимальное по этому признаку расстояние. Совокупность элемента A k как ядра и всех таким образом выбранных ближайших к нему элементов по каждому признаку и составляет ассоциативный кластер.

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

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

Рассмотрим конкретный пример применения простейшего алгоритма образования ассоциативного кластера для анализа отношений в малой группе.

Количество членов малой группы, т.е. элементов рассматриваемого множества, n =9. Было выбрано m =3 различных типов отношений между членами малой группы: 1) взаимоотношения, связанные с основной работой, 2) взаимоотношения, связанные с неделовыми формами общения, 3) взаимоотношения, связанные с участием в дополнительной работе. По каждому типу отношений методами экспертных оценок были получены матрицы попарных различий (расстояний) между всеми членами группы.

В соответствии с описанным выше простейшим алгоритмом образования ассоциативного кластера были построены все 9 кластеров, причем в качестве ядра были выбраны поочередно все члены малой группы. На рис. 4 представлен пример полученного ассоциативного кластера, в котором в качестве ядра взят элемент А 1.

Рис. 4. Ассоциативный кластер с ядром А 1

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

Теперь приведем описание алгоритма образования цепного кластера в принятых нами терминах формальной модели. Сначала из заданного множества m элементов выбирается один, который станет первым элементом, составляющим цепной кластер. Затем для каждого качества (т.е. для каждой матрицы расстояний из m заданных матриц) выбирается элемент, ближайший к первому. Из полученных M минимальных расстояний выбирается наименьшее и фиксируется номер соответствующей матрицы и номер элемента – этот элемент и будет вторым в цепном кластере. Далее процедура повторяется для второго элемента, причем первый из процесса отбора исключается. Процесс повторяется столько раз, сколько элементов в множестве M .

Заметим, что если на каком-либо шаге построения цепного кластера минимальная величина будет не у одной, а у двух или более пар элементов, то в этом случае может быть построено несколько эквивалентных цепных кластеров. Графическое изображение построенного нами цепного кластера, начинающегося с элемента А 1 , представлено на рис. 5, где видно, как к группе из элементов А 1 , А 3 , А 4 присоединяются последовательно остальные элементы. Однако необходимо подчеркнуть, что в данном исследовании цепной кластер менее информативен, чем ассоциативный, тем не менее он предоставляет дополнительные к ассоциативному кластеру сведения.

Рис. 5. Цепной кластер с ядром А 1 .

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

Выберем сначала один элемент, который будет ядром ассоциативно-цепного кластера, в этом качестве может выступать любой элемент множества. Затем применим алгоритм образования простейшего ассоциативного кластера. Рассмотрим далее множество элементов, составивших простейший кластер. Применим к этому множеству элементов алгоритм построения обобщенного ассоциативного кластера. Далее к получившемуся множеству элементов, которые составляют обобщенный кластер, снова применим алгоритм образования. Будем повторять эту процедуру до тех пор, пока в строящийся кластер не объединятся все элементы исходного множества. Полученную в результате описанного процесса структуру и будем называть ассоциативно-цепным кластером. Это название оправданно тем, что структура подобного кластера представляет собой центральный простейший ассоциативный кластер и цепочки из элементов, составляющих простейший кластер. На рис. 6 представлен пример построения ассоциативно-цепного кластера для рассматриваемых нами экспериментальных данных. В качестве исходного элемента взят элемент А 1 .

Рис. 6. Ассоциативно-цепной кластер с ядром А 1

Мы видим, что к образовавшемуся простейшему ассоциативному кластеру с ядром А 1 присоединяются элементы А 2 , А 6 , А 7 и, наконец, элементы А 8 и А 9 на различных итерациях. Если коротко охарактеризовать смысл ассоциативно-цепного кластера, то можно сказать, что он описывает структуру заданного множества элементов по отношению к одному выделенному (на рис. 6 это элемент А 1 ).

4. Кластер-коллекция . Рассмотрим, наконец, тип кластера, соответствующий комплексу-коллекции Выготского. Характеризуя его, ученый пишет, что комплексы этого типа «больше всего напоминают то, что принято называть коллекциями. Здесь различные неконкретные предметы объединяются на основе взаимного дополнения по какому-либо одному признаку и образуют единое целое, состоящее из разнородных, взаимно дополняющих друг друга частей». И далее: «Эта форма мышления часто соединяется с описанной выше ассоциативной формой. Тогда получается коллекция, составленная на основе различных признаков» (Выготский, 1982, с. 142–143).

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

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

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

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

Для первой матрицы – три кластера:

Для второй – четыре кластера:

Для третьей – четыре кластера:

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

Таким образом, в кластер-коллекцию входят элементы А 2 , А 7 , А 8 , А 9 и еще один (любой) элемент первого множества, например, А 1 . Очевидно, что элементы кластера-коллекции А 1 , А 2 , А 7 , А 8 , А 9 отличаются друг от друга хотя бы по одному признаку на величину, большую h =7. Так, например, элементы А 1 и А 2 отличаются лишь по одному третьему признаку, элементы А 1 и А 7 по второму и третьему, а, скажем, элементы А 8 и А 9 – по всем трем.

Метод латентных классов

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

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

Метод латентных классов можно использовать для дихотомических переменных и порядковых шкал. Наблюдаемые переменные могут быть измерены в дихотомической шкале наименований, т.е. являются переменными (0,1) (xi =1 – наличие признака и xi =0 – отсутствие признака). Тогда наблюдаемые вероятности могут быть объяснены с помощью латентных переменных, т.е. с помощью латентных распределений и соответствующих условных распределений (Лазарфельд, 1996).

Объясняющее уравнение первого рода имеет вид:

где наблюдаемые переменные – х i ; плотность вероятности наблюдаемых переменных – ρ i ; множество латентных переменных – φ , плотность вероятности латентных переменных – g(φ). Объясняющее уравнение n-го порядка имеет вид:

Основным предположением всех моделей латентных структур является локальная независимость. Это следует понимать так: для данной латентной характеристики наблюдаемые переменные независимы в смысле теории вероятностей. Аксиома локальной независимости имеет вид:

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

По дискретности или непрерывности и по виду характеристической кривой различают следующие модели: модели латентных групп (латентную вероятность p группы можно обозначить через g , а операционную характеристику – через ); модель латентных профилей (обобщение модели латентных групп, когда наблюдаемые переменные считаются непрерывными); модель латентных расстояний, которая имеет в качестве характерной кривой функцию скачка.

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

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

1. Относительное число испытуемых в классе (мы задавали его первоначально P(k) = 1/k ).
2. Характеристический параметр класса r(i, k) – матрица вероятности появления определенного ответа на i -й вопрос, если испытуемый относится к k -му классу. Он должен быть различным для разных классов. Мы задавали его и одинаковым для испытуемых, принадлежащих к одному классу, и различным для каждого класса. Предполагается, что условная вероятность такого события, как ответ испытуемого категории q на j вопрос, постоянна для всех испытуемых, принадлежащих к классу k . Вероятность появления ответа категории q(1,2,...,Q) равна вероятности q , являющейся суммой реализаций дихотомической случайной переменной.

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

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

1. Матрицу профилей ответов.
2. Матрицу априорных вероятностей: вероятности определенного ответа на i-й вопрос при условии, что испытуемый относится к k-му классу.
3. Относительное число испытуемых в классе.

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

Априорные распределения могут задаваться (1) стандартным способом (априорная вероятность пропорциональна числу классов); (2) исходя из профессиональных соображений, т.е. априорно задаются две латентные характеристики:

1. Количество латентных классов (k ) и соответствующее им относительное число испытуемых в классе Р(k);
2. Параметр, определяющий вероятность определенного ответа на 1-й вопрос при условии, что испытуемый относится к k -му классу r (k ).

Вероятность появления 1-го паттерна профиля:

Алгоритм метода латентных групп.

а) количество латентных классов К ,

б) количество вопросов М,

в) количество возможных категорий ответов Q ,

г) количество испытуемых N ,

д) начальное распределение.

Р(k ) – относительное число испытуемых, которые входят в класс, например Р(k) = 1/k.

Задаем начальные значения характеристик параметров классов r(i,k ) ; k = 1,..., k ; i =1,…, M ; r(i,k ) – параметр, определяющий вероятность появления определенного ответа на i- й вопрос, если испытуемый относится к k- му классу.

Вводим Xij – ответ i- го испытуемого на j- й вопрос: i =1,…,N ; j =1,...,M .

Определяем множество различных паттернов ответов: , где х ij = a ij ,a ij – ответ на j- й вопрос. Считаем количество таких паттернов: n(i), i=1,…,L; n(i a). Вычисляем вероятность появления паттерна i a при условии, что он генерируется испытуемым, относящимся к k-му классу:

Вычисляем вероятность появления такого паттерна:

Вычисляем апостериорную вероятность того, что испытуемый относится к классу k, если он ответил i a:

Вычисляем математическое ожидание количества паттернов у испытуемых класса k:

Считаем оценку относительного числа испытуемых, относящихся к классу k:

Вычисляем математическое ожидание количества паттернов, в которых ответ на j-й вопрос есть x∈{ 0,...,1,Q), при условии, что отвечающие относятся к классу k:

Вычисляем оценку параметров:

Если, то мы получаем интересующие нас параметры классов, т.е

В противном случае процедура повторяется. Также нами были разработаны четыре варианта оценки кластерных разбиений. Есть множество испытуемых Х. ||X||=N – мощность множества Х равна N, т.е. N – испытуемых. В результате LSA мы получаем для каждого из К классов и N испытуемых:

– вероятность для i-го испытуемого принадлежать к k-му классу. Определяя max Pi, мы относим испытуемого i к классу, к которому он принадлежит, с максимальной вероятностью.

Разбивая множество Х на классы указанным выше образом, получаем: k X – множество испытуемых, попавших в k-й класс; – количество испытуемых, попавших в k-й класс. Тогда можно предложить следующие оценки разбиений: средняя «четкость» кластеров, наименьшая «четкость» кластеров, интегральная «четкость» кластеров, связность кластеров. Аналогично методу иерархической кластеризации, описанному выше, наиболее верно отражающей реальную структуру оказалась оценка, названная нами – связность кластеров.

Тогда возьмем два класса; их параметры – относительное число испытуемых в классе, вероятность для i-го испытуемого принадлежать к k-му классу. Из двух вероятностей выбирается большая, что и определяет класс, к которому «принадлежит» испытуемый (реально испытуемый может не принадлежать ни к одному из классов). Если при этом в одном из анализируемых классов не оказалось ни одного испытуемого, то суммарная вероятность по этому классу равна 0. Вызывает несомненный интерес тот факт, что именно «связность» работает в обоих методах, разработанных в лаборатории математической психологии, – методе латентных классов и методе иерархической кластеризации. При кластерном анализе это можно было оценить и визуально, изучая картинку дерева. В ЛСА это можно заметить следующим образом: до данного количества кластеров (определяемых этой оценкой) профили классов существенно отличаются друг от друга, а далее заметно лишь незначительное отличие. Данный метод позволяет выделить наиболее типичные паттерны восприятия стимулов и проанализировать их профили. Метод основан на вероятностном подходе, поэтому является более универсальным по сравнению с другими методами кластерного анализа. Наиболее часто метод ЛСА используется при адаптации методик, так как позволяет выделить типичные паттерны ответов и в соответствии с ними структурировать множество испытуемых, а для каждого типа оценить апостерионую вероятность. В представленной статье описаны различные методы кластерного анализа и показано, в каких случаях их можно применять с наибольшей эффективностью по отдельности, а также совместно друг с другом. Итак, в статье представлены стандартные методы, реализованные в наиболее часто используемых статистических пакетах, их развитие и усовершенствование, которое реализовано на данном этапе только в оригинальных пакетах, а также оригинальные методы, отсутствующие в статистических пакетах.

Задачи кластеризации в 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. Далее снижать число групп не следует, т.к. это приводит к снижению качества модели. После получения кластеров происходит выбор переменных наиболее важных в экономическом смысле и наиболее тесно связанных с выбранным критерием конъюнктуры - в данном случае с котировками Лондонской биржи металлов на цинк. Этот подход позволяет сохранить значительную часть информации, содержащейся в первоначальном наборе исходных показателей конъюнктуры.

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

А мы не можем даже осознать весь этот объем, а не то что разобраться в нем.

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

Кластерный анализ – это исследование объектов путем объединения их по однородным группам со схожими признаками. Его методы применимы буквально во всех сферах: от медицины до торговли на Форекс, от автострахования до археологии. А для маркетологов и спецов по кадрам он просто незаменим.

Об этом подробнее – в статье.

Что такое кластер

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

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

1. иерархический кластерный анализ,
2. кластеризация методом k-средних.

Где применяется кластерный анализ:

• В маркетинге это сегментация конкурентов и потребителей.
• В менеджменте:
  1. разбиение персонала на различные по уровню мотивации группы,
  2. классификация поставщиков,
  3. выявление схожих производственных ситуаций, при которых возникает брак.
• В медицине - классификация симптомов, пациентов, препаратов.
• В социологии - разбиение респондентов на однородные группы.

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

Поясним суть кластерного анализа, не прибегая к строгой терминологии.

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

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

Поясним, как сформирована приведенная выше таблица. В первом столбце расположен номер кластера - группы, данные по которой отражены в строке. Например, первый кластер на 80% составляют мужчины. 90% первого кластера попадают в возрастную категорию от 30 до 50 лет, а 12% респондентов считает, что льготы очень важны. И так далее.

Попытаемся составить портреты респондентов каждого кластера:

1. Первая группа — в основном мужчины зрелого возраста, занимающие руководящие позиции. Соцпакет (MED, LGOTI, TIME-свободное время) их не интересует. Они предпочитают получать хорошую зарплату, а не помощь от работодателя.
2. Группа два — наоборот, отдает предпочтение соцпакету. Состоит она, в основном, из людей «в возрасте», занимающих невысокие посты. Зарплата для них безусловно важна, но есть и другие приоритеты.
3. Третья группа — наиболее «молодая». В отличие от предыдущих двух, очевиден интерес к возможностям обучения и профессионального роста. У этой категории сотрудников есть хороший шанс в скором времени пополнить первую группу.

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

Источник: "nickart.spb.ru"

Кластерный анализ — это ключ к пониманию рынка

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

Построение кластерного графика

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

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

Это наиболее точный и детальный анализ, так как показывает точечное распределение объемов сделок по каждому ценовому уровню актива. На рынке постоянно идет противоборство интересов продавцов и покупателей. И каждое самое маленькое движение цены (тик), является тем ходом к компромиссу – ценовому уровню - который в данный момент устраивает обе стороны.

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

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

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

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

Кластерный график

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

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

Торговля на Форекс с помощью КА

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

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

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

Источник: "orderflowtrading.ru"

Области и особенности применения анализа кластеров

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

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

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

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

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

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

Техника кластеризации применяется в самых разнообразных областях. Хартиган (Hartigan, 1975) дал прекрасный обзор многих опубликованных исследований, содержащих результаты, полученные методами кластерного анализа. Например, в области медицины кластеризация заболеваний, лечения заболеваний или симптомов заболеваний приводит к широко используемым таксономиям.

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

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

Древовидная кластеризация

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

Рассмотрим горизонтальную древовидную диаграмму. Диаграмма начинается с каждого объекта в классе (в левой части диаграммы). Теперь представим себе, что постепенно (очень малыми шагами) вы «ослабляете» ваш критерий о том, какие объекты являются уникальными, а какие нет. Другими словами, вы понижаете порог, относящийся к решению об объединении двух или более объектов в один кластер.

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

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

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

Меры расстояния

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

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

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

1. Евклидово расстояние.

Это, по-видимому, наиболее общий тип расстояния. Оно попросту является геометрическим расстоянием в многомерном пространстве и вычисляется следующим образом:

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

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

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

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

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

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

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

Однако отметим, что для этой меры влияние отдельных больших разностей (выбросов) уменьшается (так как они не возводятся в квадрат). Манхэттенское расстояние вычисляется по формуле:

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

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

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

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

   где r и p - параметры, определяемые пользователем.

   Несколько примеров вычислений могут показать, как «работает» эта мера:

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

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

Правила объединения или связи

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

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

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

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

• Одиночная связь (метод ближайшего соседа).

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

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

• Полная связь (метод наиболее удаленных соседей).

В этом методе расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. «наиболее удаленными соседями»).

Этот метод обычно работает очень хорошо, когда объекты происходят на самом деле из реально различных «рощ».

Если же кластеры имеют в некотором роде удлиненную форму или их естественный тип является «цепочечным», то этот метод непригоден.

• Невзвешенное попарное среднее.

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

Отметим, что в своей книге Снит и Сокэл (Sneath, Sokal, 1973) вводят аббревиатуру UPGMA для ссылки на этот метод, как на метод невзвешенного попарного арифметического среднего - unweighted pair-group method using arithmetic averages.

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


В книге Снита и Сокэла (Sneath, Sokal, 1973) вводится аббревиатура WPGMA для ссылки на этот метод, как на метод взвешенного попарного арифметического среднего - weighted pair-group method using arithmetic averages.

• Невзвешенный центроидный метод.

В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести.

Снит и Сокэл (Sneath and Sokal (1973)) используют аббревиатуру UPGMC для ссылки на этот метод, как на метод невзвешенного попарного центроидного усреднения - unweighted pair-group method using the centroid average.

• Взвешенный центроидный метод (медиана).

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

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

Снит и Сокэл (Sneath, Sokal 1973) использовали аббревиатуру WPGMC для ссылок на него, как на метод невзвешенного попарного центроидного усреднения - weighted pair-group method using the centroid average.

• Метод Варда.

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

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

Двувходовое объединение

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

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

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

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

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

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

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

Метод K средних

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

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

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

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

С вычислительной точки зрения вы можете рассматривать этот метод, как дисперсионный анализ «наоборот».

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

1. минимизировать изменчивость внутри кластеров,
2. максимизировать изменчивость между кластерами.

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

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

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

Источник: "biometrica.tomsk.ru"

Классификация объектов по характеризующим их признакам

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

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

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

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

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

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

Вот несколько примеров применения кластерного анализа:

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

Источник: "statmethods.ru"

Общие сведения о кластерном анализе

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

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

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

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

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

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

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

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

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

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

Преимущества и недостатки

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

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

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

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

Методы

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

В пакете Statistica реализуются следующие методы кластеризации:

• Иерархические алгоритмы – древовидная кластеризация. В основе иерархических алгоритмов лежит идея последовательной кластеризации. На начальном шаге каждый объект рассматривается как отдельный кластер. На следующем шаге некоторые из ближайших друг к другу кластеров будут объединяться в отдельный кластер.
• Метод К-средних. Этот метод используется наиболее часто. Он относится к группе так называемых эталонных методов кластерного анализа. Число кластеров К задается пользователем.
• Двухвходовое объединение. При использовании этого метода кластеризация проводится одновременно как по переменным (столбцам), так и по результатам наблюдений (строкам).

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

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

Нормирование переменных

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

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

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

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

Для этого нужно щелкнуть правой кнопкой мыши по имени переменной и в открывшемся меню выбрать последовательность команд: Fill/ Standardize Block/ Standardize Columns. Значения нормированной переменной станут равными нулю, а дисперсии – единице.

Метод К-средних в программе Statistica

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

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

В качестве примера рассмотрим результаты опроса 17-ти сотрудников предприятия по удовлетворенности показателями качества служебной карьеры. В таблице даны ответы на вопросы анкеты по десятибалльной шкале (1 – минимальный балл, 10 – максимальный).

Имена переменных соответствуют ответам на следующие вопросы:

1. СЛЦ – сочетание личных целей и целей организации;
2. ОСО – ощущение справедливости в оплате труда;
3. ТБД – территориальная близость к дому;
4. ОЭБ – ощущение экономического благосостояния;
5. КР – карьерный рост;
6. ЖСР – желание сменить работу;
7. ОСБ – ощущение социального благополучия.

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

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

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

В программе Statistica кластерный анализ выполняется следующим образом.

1. Создать файл данных.
2. Выбрать модуль Statistics/ Multivariable Exploratory Techniques/ Cluster Analysis. Нажать ОК, в результате чего появится диалоговое окно:

   

3. В появившемся окне выбрать метод кластеризации K-means clustering и нажать ОК.
4. В появившемся диалоговом окне необходимо установить следующие настройки:

   
   

   • Выбрать переменные кнопкой Variables.
   • Выбрать объекты кластеризации: это могут быть переменные – столбцы (Variables сolumns)), либо наблюдения – строки (Cases (Rows)). Сначала проведем кластеризацию по строкам (Cases(rows)).
   • Выбрать число кластеров.
     Этот выбор делает пользователь, исходя из собственных предположений о числе групп схожих объектов.

     При выборе количества кластеров руководствуйтесь следующим:

     1. Количество кластеров, по возможности, не должно быть слишком большим.
     2. Расстояние, на котором объединялись объекты данного кластера, должно быть, по возможности, гораздо меньше расстояния, на котором к этому кластеру присоединяется еще что-либо.
     При выборе количества кластеров чаще всего есть одновременно несколько правильных решений. Нас интересует, например, как соотносятся ответы на вопросы анкеты у рядовых сотрудников и руководства предприятия. Поэтому выбираем K=2. Для дальнейшей сегментации можно увеличивать число кластеров.
     
   • Далее необходимо выбрать начальное разбиение объектов по кластерам (Initial cluster centers). Пакет Statistica предлагает:
     1. выбрать наблюдения с максимальным расстоянием между центрами кластеров;
     2. рассортировать расстояния и выбрать наблюдения с постоянными интервалами (установка по умолчанию);
     3. взять первые наблюдения за центры и присоединять остальные объекты к ним.

     Для наших целей подходит первый вариант.

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

Результаты анализа можно посмотреть в появившемся диалоговом окне:

Если выбрать вкладку Graph of means, будет построен график координат центров кластеров:

Каждая ломаная линия на этом графике соответствует одному из кластеров:

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

Можно отметить, что просматриваются существенные отличия в отношении двух групп людей к служебной карьере почти по все вопросам. Лишь в одном вопросе наблюдается полное единодушие – в ощущении социального благополучия (ОСБ), вернее, отсутствии такового (2,5 балла из 10).

Можно предположить, что:

1. кластер 1 отображает рабочих,
2. кластер 2 – руководство:
   • Руководители больше удовлетворены карьерным ростом (КР), сочетанием личных целей и целей организации (СЛЦ).
   • У них выше уровень ощущения экономического благосостояния (ОЭБ) и ощущения справедливости в оплате труда (ОСО).
   • Территориальная близость к дому (ТБД) волнует их меньше, чем рабочих, вероятно, из-за меньших проблем с транспортом.
   • Также у руководителей меньше желания сменить работу (ЖСР).

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

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

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

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

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

Высшему руководству следует обратить особое внимание на сложившуюся ситуацию.

Результаты дисперсионного анализа по каждому признаку выводятся по нажатию кнопки Analysis of variance:

Выводятся:

• суммы квадратов отклонения объектов от центров кластеров (SS Within),
• суммы квадратов отклонений между центрами кластеров (SS Between),
• значения F-статистики,
• уровни значимости р.

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

Кнопка Save classifications and distances выводит номера объектов, входящих в каждый кластер и расстояния объектов до центра каждого кластера.

Состав каждого кластера и расстояния объектов от центра

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

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

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

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

После загрузки модуля кластерного анализа и выбора Joining (tree clustering), в окне ввода параметров кластеризации можно изменить следующие параметры:

1. Исходные данные (Input). Они могут быть в виде матрицы исследуемых данных (Raw data) и в виде матрицы расстояний (Distance matrix).
2. Кластеризацию (Cluster) наблюдений (Cases (raw)) или переменных (Variable (columns)), описывающих состояние объекта.
3. Меры расстояния (Distance measure). Здесь возможен выбор следующих мер:
   • евклидово расстояние (Euclidean distances),
   • квадрат Евклидова расстояния (Squared Euclidean distances),
   • расстояние городских кварталов (манхэттенское расстояние, City-block (Manhattan) distance), расстояние Чебышева (Chebychev distance metric),
   • степенное расстояние (Power…;),
   • процент несогласия (Percent disagreement).
4. Метод кластеризации (Amalgamation (linkage) rule).
   Здесь возможны следующие варианты:
   • одиночная связь (метод ближайшего соседа) (Single Linkage),
   • полная связь (метод наиболее удаленных соседей) (Complete Linkage),
   • невзвешенное попарное среднее (Unweighted pair-group average),
   • взвешенное попарное среднее (Weighted pair-group average),
   • невзвешенный центроидный метод (Unweighted pair-group centroid),
   • взвешенный центроидный метод (медиана) (Weighted pair-group centroid (median)),
   • метод Уорда (Ward’s method).

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

Древовидная структура графика позволяет определить кластеры в зависимости от выбранного порога – заданного расстояния между кластерами.

Кроме того, выводится матрица расстояний между исходными объектами (Distance matrix); средние и среднеквадратичные отклонения для каждого исходного объекта (Distiptive statistics). Для рассмотренного примера проведем кластерный анализ переменных с установками по умолчанию. Результирующая дендрограмма изображена на рисунке:

На вертикальной оси дендрограммы откладываются расстояния между объектами и между объектами и кластерами. Так, расстояние между переменными ОЭБ и ОСО равно пяти. Эти переменные на первом шаге объединяются в один кластер.

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

Из графика видно, что вопрос «желание сменить работу» (ЖСР) образует отдельный кластер. Вообще, желание свалить куда угодно посещает всех в равной степени. Далее отдельный кластер составляет вопрос о территориальной близости к дому (ТБД).

По степени важности он стоит на втором месте, что подтверждает вывод о необходимости строительства жилья, сделанный по результатам исследования методом K-средних.

Ощущение экономического благосостояния (ОЭБ) и справедливости в оплате труда (ОСО) объединены - это блок экономических вопросов. Карьерный рост (КР) и сочетание личных целей и целей организации (СЛЦ) также объединены.

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

Результаты

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