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

 Содержание

ВВЕДЕНИЕ

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

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

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

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

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

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

Глава 1. Определение и задача кластерного  анализа

1.1. Определение  кластерного анализа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2. Задача кластерного анализа. Функции расстояния и меры сходства.

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

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

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

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

Введём понятие "расстояние между объектами". Данное понятие  является интегральной мерой сходства объектов между собой. Объекты i-ый и j-ый состояли бы в одном кластере, когда расстояние (отдаленность) между точками Х_i и Х_j было бы достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между Х_i и Х_j из Е_р, где Е_р - р-мерное евклидово пространство. Расстоянием между объектами в пространстве признаков называется такая неотрицательная функция , которая является функцией расстояния (метрикой) удовлетворяя следующим аксиомам:

а) ≥ 0, для всех Х_i и Х_j из Е_р

б) = 0, тогда и только тогда, когда Х_i = Х_j

в) =

г) ≤ + , где Х_j; Х_i и Х_k - любые три вектора из Е_р.

Значение d(Х_i, Х_j) для Х_i и Х_j называется расстоянием между Х_i и Х_j и эквивалентно расстоянию между x_i и x_j соответственно выбранным характеристикам (F₁, F₂, F₃, ..., F_р).

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

1. Евклидова метрика 

Наиболее распространенная функция расстояния. Представляет собой  геометрическим расстоянием в многомерном  пространстве:

где  X_i , X_j - координаты i-го и j-го объектов в p-мерном пространстве;

 – величина k -той компоненты у i-го (j-го) объекта (k=1,2,...,p, i,j=1,2,...,n).

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

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

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

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

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

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

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

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

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

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

Пусть n измерений Х₁, Х₂,..., Х_n представлены в виде матрицы данных размером p×n:

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

Меру близости (сходства) объектов удобно представить как обратную величину от расстояния между объектами. Т.е. это является понятие сходства между объектами G_i. и G_j. Неотрицательная вещественная функция S(Х_i ; Х_j) = S_ij называется мерой сходства, если :

1) 0≤ <1 для Х_i ¹ Х_j

2) = 1

3) =

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

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

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

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

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

1. Итеративный метод. Предполагается, что каждый рассматриваемый объект относится к одному из k классов. Некоторые авторы (например, А. И. Орлов) считают, что данная группа вовсе не относится к кластеризации и противопоставляют её под названием «дискриминация», то есть выбор отнесения объектов к одной из известных групп (обучающих выборок).

• K-средних (K-means)

• K-medians
• EM-алгоритм
• Алгоритмы семейства FOREL
• Дискриминантный анализ

2. Методы на основе систем искусственного интеллекта. Весьма условная группа, так как методов AI очень много и методически они весьма различны.

• Метод нечеткой кластеризации C-средних (C-means)

• Нейронная сеть Кохонена
• Генетический алгоритм

3. Логический метод. Построение дендрограммы осуществляется с помощью дерева решений.
4. Теоретико-графовый метод.

• Графовые алгоритмы кластеризации

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

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

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

6. Другие методы. Не вошедшие в предыдущие группы.

• Статистические алгоритмы кластеризации
• Ансамбль кластеризаторов
• Алгоритмы семейства КRAB
• Алгоритм, основанный на методе просеивания
• DBSCAN и др.

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

На практике чаще всего  применяют два подхода: вероятностный и иерархический.

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

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

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

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

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

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

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

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

Рис.1 Принцип работы агломеративных и дивизимных методов.

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

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

Иерархические алгоритмы  связаны с построением дендрограмм (от греческого dendron - "дерево"), которые  являются результатом иерархического кластерного анализа. Дендрограмма описывает близость отдельных точек  и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров (см. рис. 1).

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

Существует много способов построения дендрограмм. В дендрограмме объекты могут располагаться  вертикально или горизонтально. Ниже приведен пример вертикальной дендрограммы (см. рис. 2).

Рис. 2 Пример дендрограммы.

Буквы N, M, C и т.д. соответствуют номерам объектов или наблюдений исходной выборки. Видно, что на первом шаге каждое наблюдение представляет один кластер (вертикальная линия), на втором шаге наблюдаем объединение таких наблюдений: N и M; C, D и E; G и K; B и F. На втором шаге продолжается объединение в кластеры: наблюдения N, M, C, D, E и G, K, L. Данный процесс продолжается до тех пор, пока все наблюдения не объединятся в один кластер.

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

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

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

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

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

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

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

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

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

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

2.2. Итеративные методы кластерного анализа. Метод k – средних.

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

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

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

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