Кластерный анализ. Типы процедур кластер-анализа Проверка качества кластеризации

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

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

Алгоритм k-средних (k-means)

Наиболее распространен среди неиерархических методов алгоритм k-средних , также называемый быстрым кластерным анализом . Полное описание алгоритма можно найти в работе Хартигана и Вонга (Hartigan and Wong, 1978). В отличие от иерархических методов, которые не требуют предварительных предположений относительно числа кластеров, для возможности использования этого метода необходимо иметь гипотезу о наиболее вероятном количестве кластеров.

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

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

Описание алгоритма

1. Первоначальное распределение объектов по кластерам.

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

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

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

   В результате каждый объект назначен определенному кластеру.

2. Итеративный процесс.

   Вычисляются центры кластеров , которыми затем и далее считаются покоординатные средние кластеров. Объекты опять перераспределяются.

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

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

   На рис. 14.1 приведен пример работы алгоритма k-средних для k, равного двум.

Рис. 14.1.

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

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

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

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

Заключение

Кластерный анализ - метод группировки объектов в классы на основании экспериментальных данных о свойствах объектов.

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

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

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

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

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

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

Перечислим недостатки кластерного анализа:

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

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

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

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

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

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

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

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

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

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

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

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

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

• 1) р(ЗД>0,
• 2) p(X,Y)=p (Y,X),
• 3) р(Х, У) = 0 X = Y,
• 4) P (X,Y) P (Z,Y).

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

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

2) взвешенное евклидово расстояние

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

и полагают, что ^ w* = 1;

• 3) хеммингово расстояние (или city-block) - расстояние по карте между кварталами в городе

4) расстояние Махаланобиса (или угол Махаланобиса)

где А - симметричная положительно определенная матрица весовых коэффициентов (часто выбирается диагональной); А - матрица ковариаций векторов Х 19 ...,Х п;

5) расстояние Минковского

Расстояния 1), 2), 3) или 5) используют в случае нормального распределения независимых случайных величин X l9 ...,X n ~N(M,A) или в случае их однородности по геохимическому смыслу, когда каждый вектор одинаково важен для классификации. Расстояние 4) используют в случае наличия ковариационной связи векторов Х х,...,Х п.

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

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

Пусть S { - /-ый кластер, состоящий из n t векторов или точек. Пусть

X (l) - выборочное среднее по точкам, попадающим в кластер S f , или центр тяжести кластера 5.. Тогда различают следующие расстояния между кластерами, не имеющими внутри других кластеров:

1) расстояние между кластерами по принципу «ближнего соседа»

2) расстояние между кластерами по принципу «дальнего соседа»

3) расстояние между центрами тяжести групп

4) расстояние между кластерами по принципу «средней связи»

5) обобщенное расстояние по Колмогорову

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

где S^ k ^ - кластер, полученный объединением классов S k и S t .

Все частные случаи расстояний получаются из этой обобщенной формулы. При а = р = 1 / 2, 8 = -1/2, у = 0 имеем расстояние по принципу «ближнего соседа», при а = р = 5 = 1/ 2, у = О - «дальнего соседа»,

при а =---, р =--- ,5 = 0, у = 0 - расстояние по центрам тяже-

п к + n i п к + n i

сти групп.

Методы кластерного анализа подразделяются на I) агломеративные (объединяющие), II) дивизимные (разделяющие) и III) итеративные.

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

Рассмотрим подробнее агломеративные методы. Агломеративные методы являются наиболее простыми и распространенными среди алгоритмов кластерного анализа. На первом шаге каждый вектор или объект Х 19 ...,Х п исходных данных рассматривается как отдельный кластер или класс. По вычисленной матрице расстояний выбираются наиболее близкие друг к другу и объединяются. Очевидно, что процесс завершится через (п - 1) шаг, когда в результате все объекты будут объединены в один кластер.

Последовательность объединений можно представить в виде дендрограммы, или дерева. На рис. 1.18 показано, что на первом шаге были объединены векторы X t ,X 2 , так как расстояние между ними 0,3.

На втором шаге к ним был присоединен вектор Х 3 , отстоящий от кластера {Х 1 ,Х 2 } на расстояние 0,5, и т. д. На последнем шаге объединяются все векторы в один кластер.

Рис. 1.18.

К агломеративным относят методы одиночной, средней, полной связи и метод Уорда.

1. Метод одиночной связи. Пусть X v ...,X n - векторные данные, причем каждый вектор образует один кластер. Сначала вычисляется матрица расстояний между этими кластерами, причем в качестве метрики используется расстояние по принципу ближнего соседа. С помощью этой матрицы выбирают два наиболее близких вектора, которые и образуют первый кластер 5,. На следующем шаге между S ] и оставшимися векторами (которые мы считаем кластерами) вычисляется новая матрица расстояний, причем в качестве метрики используется расстояние между кластерами, объединенными в классы (а = р = 1/ 2, 5 = -1/2, у = 0). Ближайший к полученному ранее классу S { кластер объединяется с ним, образуя S 2 . И т. д. Через п- 1 шагов получаем, что все векторы объединены в один кластер.

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

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

• 2. Метод полной связи. Метод практически повторяет метод одиночной связи за исключением того, что включение нового объекта в кластер происходит тогда и только тогда, когда расстояние между объектами (векторами или кластерами) меньше некоторого наперед заданного числа. Число задается пользователем. Расстояние вычисляется только по принципу «дальнего соседа» (то же самое можно сказать и про расстояние между классами, объединенными в классы - только принцип дальнего соседа при ос = р = 8 = 1/2, у = 0).
• 3. Метод средней связи. Алгоритм образования кластеров совпадает с алгоритмом одиночной связи, однако при решении вопроса о включении нового объекта в кластер вычисления производятся по принципу средней связи. Как и в методе полной связи, все вычисленные между кластерами расстояния сравниваются с задаваемым пользователем числом. И если оно (расстояние) меньше заданного числа, новый объект включается в старый класс. Таким образом, метод средней связи отличается от метода полной связи только способом вычисления расстояния между кластерами.
• 4. Метод УОРДА. Пусть Х 19 ...,Х п - данные, причем каждый вектор образует один кластер. Находим матрицу расстояний, используя какую-нибудь метрику (например, расстояние Махаланобиса), определяем по ней наиболее близкие друг к другу кластеры. Вычисляем сумму квадратов отклонений векторов внутри кластера S k по формуле:

где к - номер кластера, i - номер вектора в кластере, j - номер координаты X t е У1 Р, п к - число векторов в кластере, X jk - выборочное среднее X i в S k . Величина V k характеризует отклонения векторов друг от друга внутри кластера (нового S k +S f или старого^). Расчет V k следует проводить до и после объединения, причём нужно перебирать все возможные варианты таких объединений. В дальнейшем в кластер S k добавляются только те векторы или кластеры, которые приводят к наименьшему изменению V k после объединения и, как следствие, которые будут расположены на минимальном расстоянии от исходного кластера S k .

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

1. Метод /г-средних. Пусть имеются векторы X l9 ...,X n e9F и их необходимо разбить на к кластеров. На нулевом шаге из п векторов случайным образом выбираем к из них, считая, что каждый образует один кластер. Получаем множество кластеров-эталонов,...,е[ 0) с весами

coj 0) ,...,X. и вычисляем матрицу расстояний между X. и эталонами е 1 (0) ,...,^ 0) по некоторой метрике, например по евклидовой:

На основе знания вычисленной матрицы расстояний вектор Х { помещается в тот эталон, расстояние до которого минимально. Допустим для определенности, что это. Он заменяется новым, пересчитанным с учетом присоединенной точки, по формуле

Кроме того, пересчитывается и вес:

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

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

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

• 2. Метод поиска сгущений. Это следующий итеративный алгоритм. Он не требует априорного задания числа кластеров. На первом шаге вычисляется матрица расстояний между Х Х9 ... 9 Х п еУ1 р по какой-нибудь метрике. Затем случайным образом выбирают один вектор, который будет играть роль центра первого кластера. Это начальное приближение. Положим, что этот вектор лежит в центре р-мерной сферы радиуса R, причем этот радиус задается исследователем. После этого определяются векторы X Si ,... 9 X Sk , попавшие внутрь этой сферы, и по ним высчитывается выбо-
• - 1 к

рочное математическое ожидание X = ~У]Х 5 . Затем центр сферы пере-

носится в X , и расчетная процедура повторяется. Условием окончания итерационного процесса является равенство векторов средних X , найденных на т и (т+ 1) шагах. Попавшие внутрь сферы элементы Х 9 ... 9 Х

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

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

Пусть Х Х9 ... 9 Х п еУ1 Р - некоторая совокупность наблюдений, которая разбивается на классы S = {S l9 ... 9 S k } 9 причем к заранее известно. Тогда основные функционалы качества разбиения при известном числе кластеров имеют вид:

1) Взвешенная сумма внутриклассовых дисперсий

где а{1) - выборочное математическое ожидание кластера S l .

Функционал Q { (S) позволяет оценить меру однородности всех кластеров в целом.

2) Сумма попарных внутриклассовых расстояний между элементами или

где п 1 - число элементов в кластере S { .

3) Обобщенная внутриклассовая дисперсия

где n j - число элементов в S ., А; . - выборочная ковариационная матрица для Sj.

Функционал является средней арифметической характеристикой обобщенных внутриклассовых дисперсий, подсчитанных для каждого кластера. Как известно, обобщенная дисперсия позволяет оценить степень рассеивания многомерных наблюдений. Поэтому Q 3 (S) позволяет оценить средний разброс векторов наблюдений в классах S l9 ... 9 S k . Отсюда и его название - обобщенная внутриклассовая дисперсия. Q 3 (S) применяется в случае, когда необходимо решить задачу о сжатии данных или о сосредоточении наблюдений в пространстве с размерностью меньше исходной.

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

где n t и п т - число векторов в классах S l ,S m ; X,Х т - центрированные исходные данные; S* - объединенная ковариационная матрица кластеров S n S m: S* =---(XjX l +X^X m) . Как и ранее, значение Q 4 (S )

п,+п т -2

сравнивают с табличным значением, вычисленным согласно формуле

где m - исходная размерность векторов наблюдений, а - уровень значимости.

Гипотеза Н 0 принимается с вероятностью (1-ос), если Q 4 (S) n _ m , и отвергается в противном случае.

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

Если число кластеров в S = {S l9 ...,S k } заранее неизвестно, то используют следующие функционалы качества разбиения при произвольно выбираемом целом m :

I I к 1 1 m

- - средняя мера внутриклас-

П i =1 n i XjeSj X"tSj J

сового рассеяния,

• (1 П / 1 W
• - X ~-~ r “ мера концентрации точек множества

п nV л J J

S, - число элементов в кластере, содержащем точку Х г

Заметим, что при произвольном значении параметра т функционал Z m (S) достигает минимума, равного I/ п, если исходное разбиение на кластеры S = {S l9 ...,S k } является разбиением на моно кластеры S. = {Xj }, так как V(X t) = 1. В то же время Z m (S ) достигает максимума, равного 1, если S - один кластер, содержащий все исходные данные,

так как V(X {) = n. В частных случаях можно показать, что Z_ l (S) = -, где к - число различных кластеров в S = {S l9 ... 9 S k } 9 Z X (S) = max - ,

*" V п)

где n t - число элементов в кластере S i9 Z^(S) = min - ,

г " п)

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

гарантирует существование экстремума Q(S ).

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Подобные документы

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

доклад , добавлен 02.11.2009


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

дипломная работа , добавлен 20.07.2015


Моделирование. Детерминизм. Задачи детерминированного факторного анализа. Способы измерения влияния факторов в детерминированном анализе. Расчёт детерминированных экономико-математических моделей и методов факторного анализа на примере РУП "ГЗЛиН".

курсовая работа , добавлен 12.05.2008


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

дипломная работа , добавлен 09.10.2013


Завдання та етапи кластерного аналізу, вимоги до інформації. Приклад класифікації економічних об"єктів за допомогою алгоритму кластерного аналізу, методи перевірки стійкості кластеризації, інтерпретація результатів аналізу та побудування дендрограми.

реферат , добавлен 15.07.2011


Основная терминология, понятие и методы факторного анализа. Основные этапы проведения факторного анализа и методика Чеботарева. Практическая значимость факторного анализа для управления предприятием. Метода Лагранжа в решении задач факторного анализа.

контрольная работа , добавлен 26.11.2008


Выполнение кластерного анализа предприятий с помощью программы Statgraphics Plus. Построение линейного уравнения регрессии. Расчет коэффициентов эластичности по регрессионным моделям. Оценка статистической значимости уравнения и коэффициента детерминации.

Введение

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

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

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

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

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

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

Разработка типологии или классификации.

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

Представление гипотез на основе исследования данных.

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

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

Цель занятия

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

Практическое задание

Разработать алгоритмы методов ближнего соседа и k -средних и реализовать их в виде компьютерных программ. С помощью ДСЧ сгенерировать 50 реализаций x = (x 1 , x 2) – случайной 2-мерной величины, координаты которой распределены равномерно в интервале (3,8). Распределить их с помощью разработанных программ на минимальное число кластеров, каждый из которых помещается в сфере радиуса 0,15.

Методические указания

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

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

• дисперсия кластера;

  среднеквадратическое отклонение.

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

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

Дисперсия кластера – это мера рассеяния точек в пространстве относительно центра кластера.

Среднеквадратичное отклонение (СКО) объектов относительно центра кластера – квадратный корень из дисперсии кластера.

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

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

иерархические;

неиерархические.

Каждая группа включает множество подходов и алгоритмов.

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

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

Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении больших кластеров на меньшие.

Иерархические агломеративные методы (Agglomerative Nesting, AGNES)

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

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

Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA)

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

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

Меры сходства

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

Евклидово расстояние является геометрическим расстоянием в многомерном пространстве и вычисляется по формуле (4.1).

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

Квадрат евклидова расстояния вычисляется по формуле (4.2).

(4.2)

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

(4.3)

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

(4.4)

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

(4.5)

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

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

(4.6)

Методы объединения или связи

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

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

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

Невзвешенное попарное среднее– расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них.

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

Невзвешенный центроидный метод – расстояние между двумя кластерами определяется как расстояние между их центрами тяжести.

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

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

Метод ближайшего соседа

Расстояние между двумя классами определяется как расстояние между ближайшими их представителями.

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

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

Итеративные методы.

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

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

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

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

Алгоритм k-средних (k-means)

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

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

выбираются или назначаются k наблюдений, которые будут первичными центрами кластеров;

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

после назначения всех наблюдений отдельным кластерам производится замена первичных кластерных центров на кластерные средние;

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

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

Описание алгоритма

Первоначальное распределение объектов по кластерам.

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

выбор k- наблюдений для максимизации начального расстояния;

случайный выбор k- наблюдений;

выбор первых k- наблюдений.

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

Итеративный процесс.

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

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

число итераций равно максимальному числу итераций.

Проверка качества кластеризации

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

Достоинства алгоритма k-средних :

простота использования;

быстрота использования;

понятность и прозрачность алгоритма.

Недостатки алгоритма k-средних :

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

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

Отчет должен содержать:

описание и блок-схемы алгоритмов;

исходные тексты программных модулей;

результаты работы алгоритмов в виде графиков.