Группировки и кластерный анализ
Кластерный анализ как инструмент группировки объектов. Коэффициенты оценки подобия на практике. Задача кластерного анализа. Иерархические методы его применения. Проверка качества кластеризации. Методика применения основных методов кластерного анализа.
| Рубрика | Математика |
| Вид | курс лекций |
| Язык | русский |
| Дата добавления | 19.09.2017 |
| Размер файла | 209,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Группировки и кластерный анализ
В общем случае при статистических исследованиях может рассматриваться к объектов, каждый из которых может характеризоваться l признаками по n интервалам времени.
Для получения как можно более простых математических зависимостей и корректного применения основного метода статистических исследований - регрессионного анализа, обладающего сравнительной простотой и конструктивностью, рекомендуется обеспечить однородность исследуемых вероятностных объектов по всем трём вышеназванным показателям, т. е. по объектам, по признакам и по временным интервалам. Для группировки объектов используется кластерный анализ, для групппировки признаков - факторный и компонентный анализ, для группировки временных интервалов ? периодизация. В любом случае при группировке добиваются, чтобы различия внутри выделенных групп были бы минимальны, а между группами максимальны. Невзирая на наличие формализации всех методов группировок все они являются численными методами и их можно отнести к эвристическим методам, основанным на «здравом смысле».
Для оценки подобия (однородности) на практике используется три типа мер: коэффициенты подобия, коэффициенты связи, показатели расстояния.
1. Коэффициенты подобия можно применять если уровни признаков
могут быть представлены целыми числами. Числа переводятся в двоичную систему и в них подсчитывается количество совпадающих разрядов («0» с «0», «1» с «1»). Например, рассмотрим два объекта, характеризующихся тремя признаками. Исходные данные объектов и результаты вычислений приведены в таблице 5.1.
Таблица 5.1
|
Объект |
Признак x1 |
Признак x2 |
Признак x3 |
Кол. совп. «0» |
Кол. совп. «1» |
Общее кол. совп. |
Вероят. общ. кол. |
|
|
1 |
35 |
102 |
78 |
|||||
|
2 |
75 |
56 |
11 |
|||||
|
1 |
0100011 |
1100110 |
1001110 |
|||||
|
2 |
1001011 |
0111000 |
0001011 |
5 |
5 |
10 |
0,476 |
В таблице 5.1 представлены результаты вычисления наиболее используемого коэффициента подобия по общему количеству совпадений «0» и «1» в двоичных разрядах чисел. Можно учитывать только количество совпадений «1» (коэффициент Рао) 5/21=0,238. Чтобы усилить значимость совпадений можно использовать коэффициент Хаммана (10-11)/21=?0,048 (где 5+5=10 количество совпадений, а 21-10=11 количество несовпадений значений в разрядах). Если в числитель подставить количество совпадений «1» в разрядах чисел, а в знаменатель количество пар хотя бы с одной «1», то можно вычислить коэффициент Роджерса-Танимото) 5/16=0,3125.
Коэффициенты связи, как правило, применяются для группировки признаков. В качестве коэффициента связи чаще всего используется коэф- фициент линейной корреляции, а для проведения группировки квадратная матрица коэффициентов линейной корреляции между признаками.
В качестве показателей расстояния используются:
- Евклида;
- Хемминга;
- Чебышева;
- Минковского.
Кластерный анализ
Термин кластерный анализ (впервые ввел Tryon, 1939). В настоящее время известно около 100 различных алгоритмов проведения кластерного анализа. Кластерный анализ не накладывает каких-либо ограничений на представление признаков исследуемых объектов. Желательно только, чтобы переменные измерялись в сравнимых шкалах.
Кластерный анализ позволяет упростить математические модели объектов, входящих в выделенные кластеры за счёт однородности признаков (их меньшей изменчивости).
Кластерный анализ может применяться и к совокупностям временных рядов, здесь могут выделяться периоды схожести некоторых показателей и определяться группы временных рядов со схожей динамикой.
Обычно перед началом классификации данные стандартизируются. Иногда различные независимые переменные измеряются в разных шкалах с различными диапазонами. Если значения одной переменной измеряются в сотнях и изменяются в пределах десяти, в то время как другая переменная в среднем равна нулю и изменяется в пределах единицы, то вклад последней в расстояние между объектами будет пренебрежительно малым. Результатом стандартизации является приведение всех переменных к единой шкале.
Задача кластерного анализа
Задача кластерного анализа заключается в том, чтобы разбить множество, состоящее из k объектов на m кластеров (m - целое число, меньшее чем k) так, чтобы каждый объект принадлежал только одному кластеру с однородными признаками и чтобы объекты, принадлежащие разным кластерам, были с разнородными признаками. Кластерный анализ
Поставим задачу выделения кластеров по показателям расстояния между признаками в группируемых ОИ с выполнением следующих условий.
; (5.1)
, (5.2)
где k - количество объектов;
- расстояние между i-м и j-м объектами;
- символ Кронекера, принимающий значение 1, если i-ый и j-ый объекты входят в один и тот же кластер; и значение 0, если не входят.
Признаки представляются либо в натуральных единицах измерения, либо в стандартизированной форме, в которой их средние значения равны нулю, а стандартные отклонения равны единице. В стандартных процедурах для проведения кластерного анализа, как правило задается либо количество кластеров, либо пороговое значение для условия (5.1). Условие (5.1) обеспечивает минимум расстояний между признаками объектов, вошедших в один и тот же кластер; а (5.2) максимум этих расстояний между объектами, вошедшими в разные кластеры.
Технология применения кластерного анализа включает в себя следующие этапы:
1. Стандартизация исходных статистических данных выполняется в случаях, когда учитываемые признаки имеют различные единицы измерения или значительно отличаются по масштабам единиц измерения.
2. Вычисление расстояний между признаками объектов и суммарного расстояния между объектами по всем признакам и составление матрицы расстояний между объектами.
3. Поиск наименьшего расстояния между объектами и объединение двух объектов с наименьшим расстоянием между ними в один кластер.
4. Вычисление расстояний между объектами и формирующимися кластерами и преобразование матрицы расстояний между ними. Переход к пункту 3 и выполнение пунктов 3 и 4 до тех пор, пока не будут сгруппированы все объекты и сформированные кластеры в один общий кластер, после чего переход к пункту 5.
5. Выдача перечней объектов по выделенным кластерам в виде таблицы и соответствующей дендрограммы с указанием расстояний между объектами в выделенных кластерах и сформированными кластерами.
Расстояние между объектами по Евклиду вычисляется по формуле:
. (5.3)
Для придания больших весов более отдаленным друг от друга объектам можно воспользоваться квадратом евклидова расстояния путем возведения в квадрат стандартного евклидова расстояния.
(5.4)
Манхэттенское расстояние (расстояние городских кварталов), также называемое "хемминговым". Это расстояние рассчитывается как среднее разностей по координатам. В большинстве случаев эта мера расстояния приводит к результатам, подобным при использовании евклидова расстояния. Для расстояния хемминга влияние имеющихся «выбросов» (больших отклонений) меньше, чем при использовании евклидова расстояния, поскольку в этом случае координаты не возводятся в квадрат.
; ; . (5.5)
Расстояние Чебышева. Это расстояние следует использовать, когда необходимо определить два объекта как "различные", если они сильно отличаются отличаются по какому-то одному измерению.
; (5.6)
Степенное расстояние (обобщенное степенное расстояние Минковского) используется в том случае, если необходимо прогрессивно увеличить или уменьшить вес, относящийся к размерности, для которой соотвествующие объекты сильно отличаются.
; (5.7)
В формуле (5.7) параметры r и p, определяются в зависимости от задачи. Параметр p ответственен за постепенное взвешивание разностей по отдельным измерениям, параметр r влияет на прогрессивное взвешивание больших расстояний между объектами.
В формулах (5.3) - (5.7) приняты следующие обозначения:
dij ? расстояние между i-ым и j-ым объектами;
k - количество объектов;
l - количество признаков;
xig - значение i-го признака g-го объекта;
xjg ? значение j-го признака g-го объекта.
Расстояние от формирующегося кластера с вошедшими в него объектами до других объектов может вычисляться по следующим правилам.
Принцип ближайшего соседа.
, при ; (5.8)
,при .
Принцип наиболее удаленного соседа.
, при ; (5.9)
,при .
3.Принцип среднего расстояния.
. (5.10)
Принцип медианы.
. (5.11)
В формулах (5.8) - (5.11) приняты следующие обозначения:
- расстояние между q-ым кластером, к которому подсоединен еще один объект, и g-ым объектом или кластером;
- расстояние между i-ым и g-ым объектами или кластерами;
- расстояние между j-ым и g-ым объектами или кластерами;
- расстояние между i-ым и j-ым объектами или кластерами.
Решением задачи кластерного анализа является разбиение, удовлетворяющее заданным условиям (5.1) и (5.2). Рассмотрим пример процедуры кластерного анализа.
Пример 5.0
Допустим, мы имеем совокупность, состоящую из 13-ти объектов, которые характеризуются двумя признаками: x1 и x2. Данные по ним приведены в таблице 5.1.
Представим переменные х1 и х2 в виде диаграммы рассеивания, приведённой на рис.5.1. В таблице 5.1 объекты вошедшие в одни и те же кластеры выделены одинаковыми цветами. На рисунке 5.1 мы видим три кластера. Объекты, которые по значениям х1 и х2 "похожи" друг на друга, принадлежат к одному кластеру; объекты из разных кластеров не похожи друг на друга.
Кластер имеет следующие математические характеристики: центр, радиус, среднеквадратическое отклонение, размер кластера.
Центр кластера - это среднее геометрическое место точек в пространстве переменных. Среднее геометрическое n значений определяется по формуле:
Радиус кластера - максимальное расстояние точек от центра кластера.
Кластеры могут быть перекрывающимися. Такая ситуация возникает, когда обнаруживается перекрытие кластеров. В этом случае невозможно при помощи математических процедур однозначно отнести объект к одному из двух кластеров. Такие объекты называют спорными.
Спорный объект - это объект, который по мере сходства может быть отнесен к нескольким кластерам.
Размер кластера может быть определен либо по радиусу кластера, либо по среднеквадратичному отклонению объектов для этого кластера. Объект относится к кластеру, если расстояние от объекта до центра кластера меньше радиуса кластера. Если это условие выполняется для двух и более кластеров, объект является спорным.
Методы кластерного анализа
На практике наиболее часто используются следующие методы кластерного анализа:
- иерархический;
- k-средних;
- двувходовое объединение.
Иерархические методы кластерного анализа
Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении больших кластеров на меньшие.
Иерархические агломеративные методы (Agglomerative Nesting, AGNES)
Эта группа методов характеризуется последовательным объединением исходных объектов и соответствующим уменьшением числа кластеров. В начале работы алгоритма все объекты являются отдельными кластерами. На первом шаге наиболее похожие объекты объединяются в кластер. На последующих шагах объединение продолжается до тех пор, пока все объекты не будут составлять один кластер.
Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA)
Эти методы являются логической противоположностью агломеративным методам. В начале работы алгоритма все объекты принадлежат одному кластеру, который на последующих шагах делится на меньшие кластеры, в результате образуется последовательность расщепляющих групп.
Принцип работы описанных выше групп методов в виде дендрограммы показан на рис 5.2.
Рис.5.2
Иерархические методы кластерного анализа используются при сравнительно небольших объемах наборов данных. Преимуществом иерархических методов кластеризации является их наглядность.
Иерархические алгоритмы связаны с построением дендрограмм (от греческого dendron - "дерево"), которые являются результатом иерархического кластерного анализа. Дендрограмма описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров.
Дендрограмма (dendrogram) - древовидная диаграмма, содержащая n уровней, каждый из которых соответствует одному из шагов процесса последовательного укрупнения кластеров. Дендрограмму также называют древовидной схемой, деревом объединения кластеров, деревом иерархической структуры.
Существует много способов построения дендрограмм. В дендрограмме объекты могут располагаться вертикально или горизонтально. Пример вертикальной дендрограммы приведен на Рис.5.3.
Рис.5.3
Если рис.5.3 повернуть по часовой стрелке на угол 90 градсов,то получим горизонтальную дендрограмму.
Иерархические методы кластеризации различаются правилами построения кластеров. В качестве правил выступают критерии, которые используются при решении вопроса о "схожести" объектов при их объединении в группу (агломеративные методы) либо разделения на группы (дивизимные методы). Из них наиболее распространены методы: одиночной связи, полных связей, средней связи, Уорда.
Метод ближнего соседа или одиночная связь. Здесь расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. Этот метод позволяет выделять кластеры сколь угодно сложной формы при условии, что различные части таких кластеров соединены цепочками близких друг к другу элементов. В этом методе кластеры представляются длинными "цепочками" или "волокнистыми" кластерами, "сцепленными вместе" только отдельными элементами, которые случайно оказались ближе остальных друг к другу.
Метод наиболее удаленных соседей или полная связь. Расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. "наиболее удаленными соседями"). Метод хорошо использовать, когда объекты являются представителями различных "рощ". Если же кластеры имеют в некотором роде удлиненную форму или их естественный тип является "цепочечным", то этот метод не следует использовать.
Метод средней связи. Для решения вопроса о включении нового объекта в уже существующий кластер вычисляется среднее значение меры сходства, которое затем сравнивается с заданным пороговым уровнем.
Метод Уорда (Ward's method). В качестве расстояния между кластерами берется прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в результате их объединения (Ward, 1963). В отличие от других методов кластерного анализа для оценки расстояний между кластерами, здесь используются методы дисперсионного анализа. На каждом шаге алгоритма объединяются такие два кластера, которые приводят к минимальному увеличению целевой функции, т.е. внутригрупповой суммы квадратов. Этот метод направлен на объединение близко расположенных кластеров и "стремится" создавать кластеры малого размера.
Метод невзвешенного попарного среднего. В качестве расстояния между двумя кластерами берется среднее расстояние между всеми парами объектов в них. Этот метод следует использовать, если объекты являются представителями различных "рощ", а в случаях присутствия кластеров "цепочного" типа, при предположении неравных размеров кластеров.
Метод взвешенного попарного среднего. Этот метод похож на метод невзвешенного попарного среднего, разница состоит лишь в том, что здесь в качестве весового коэффициента используется размер кластера (число объектов, содержащихся в кластере). Этот метод рекомендуется использовать при наличии предположения о кластерах разных размеров.
Невзвешенный центроидный метод. В качестве расстояния между двумя кластерами в этом методе берется расстояние между их центрами тяжести.
Взвешенный центроидный метод. Этот метод похож на предыдущий, разница состоит в том, что для учета разницы между размерами кластеров (числе объектов в них), используются веса. Этот метод предпочтительно использовать в случаях, если имеются предположения относительно существенных отличий в размерах кластеров.
Методику иерархического кластерного анализа можно представить в виде последовательности процедур:
1. Стандартизации исходных статистических данных выполняется в случаях, когда учитываемые признаки имеют различные единицы измерения или значительно отличаются по масштабам единиц измерения.
2. Вычисления расстояний между признаками объектов и суммарного расстояния между объектами по всем признакам и составление матрицы расстояний между объектами.
3. Поиска наименьшего расстояния между объектами и объединение двух объектов с наименьшим расстоянием между ними в один кластер.
4. Вычисления расстояний между объектами и формирующимися кластерами и преобразование матрицы расстояний между ними. Переход к пункту 3 и выполнение пунктов 3 и 4 до тех пор, пока не будут сгруппированы все объекты и сформированные кластеры в один общий кластер, после чего переход к пункту 5.
5. Выдачи перечней объектов по выделенным кластерам в виде таблицы и соответствующей дендрограммы с указанием расстояний между объектами в выделенных кластерах и сформированными кластерами.
Метод k-средних
При большом количестве объектов иерархические методы кластерного анализа не эффективны, или даже совсем не пригодны. В таких случаях используют неиерархические методы, основанные на разделении, которые представляют собой итеративные методы дробления исходной совокупности. В процессе деления новые кластеры формируются до тех пор, пока не будет выполнено правило остановки.
Такая неиерархическая кластеризация состоит в разделении набора данных на определенное количество отдельных кластеров. Существует два подхода. Первый заключается в определении границ кластеров как наиболее плотных участков в многомерном пространстве исходных данных, т.е. определение кластера там, где имеется большое "сгущение точек". Второй подход заключается в минимизации меры различия объектов.
Наиболее распространен среди неиерархических методов алгоритм k-средних, также называемый быстрым кластерным анализом. В отличие от иерархических методов, которые не требуют предварительных предположений относительно числа кластеров, для возможности использования этого метода необходимо выдвинуть гипотезу о наиболее вероятном количестве кластеров.
Алгоритм k-средних строит k кластеров, расположенных на возможно больших расстояниях друг от друга. Основной тип задач, которые решает алгоритм k-средних, - наличие предположений (гипотез) относительно числа кластеров, при этом они должны быть различны настолько, насколько это возможно. Выбор числа k может базироваться на результатах предшествующих исследований, теоретических соображениях или интуиции.
Общая идея алгоритма: для заданного фиксированного количества кластеров - k средние значения признаков максимально возможно отличаются друг от друга.
Первоначальное распределение объектов по кластерам.
По выбранному количеству кластеров - k на первом шаге в качестве их центров выбирается k объектов. Каждому кластеру соответствует один центр. Выбор начальных центров может осуществляться следующими методами:
- выбор первых k-объектов;
- случайный выбор k-объектов;
- выбор первых двух объектов в качестве центров двух первых кластеров по максимальному расстоянию между ними (по k-средним); в качестве центра третьего кластера выбирается объект суммарное расстояние которого от объектов, ранее выбранных в качестве центров кластеров, максимально. И таким образом определяются объекты в качестве центров всех остальных кластеров с общим количеством - k кластеров. В результате каждому из k кластеров назначется объект в качестве первоначального центра.
Затем все объекты распределяются по k кластерам по наименьшему расстоянию к объекта м, выбранным в качестве центров кластеров.
Итеративный процесс перераспределения объектов в кластерах
Вычисляются центры сформированных кластеров, которыми затем и далее считаются покоординатные средние кластеров. Объекты перераспределяются по наименьшему расстоянию их покоординатного среднего и поокординатных средних каждого кластера.
Итеративный процесс вычисления центров и перераспределения объектов в кластерах продолжается до тех пор, пока не выполнено одно из условий:
- кластерные центры стабилизировались, т.е. все объекты входят в кластеры, в которые они входили до текущей итерации;
- число итераций равно максимальному заданному числу итераций.
На рис.5.4 приведен пример алгоритма k-средних для k, равного двум.
Рис.5.4
Выбор числа выделяемых кластеров является сложным вопросом. Если нет предположений относительно этого числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и т.д., сравнивая полученные результаты.
Проверка качества кластеризации
После получений результатов кластерного анализа методом k-средних проверяется качество кластеризации (т.е. оценивается, насколько кластеры отличаются друг от друга). Для этого рассчитываются средние значения для каждого кластера и определяется разница средняя разница между ними. При хорошей кластеризации должны быть получены сильно отличающиеся средние для всех объектов, или хотя бы большей их части.
Достоинства алгоритма k-средних:
- простота использования;
- быстрота использования;
- понятность и прозрачность алгоритма.
Недостатки алгоритма k-средних:
- алгоритм слишком чувствителен к выбросам, которые могут искажать среднее. Возможным решением этой проблемы является использование модификации алгоритма - алгоритм k-медианы;
- алгоритм может медленно работать при большом количестве объектов и большом количестве признаков объектов.
Пример 5.1. Кластерный анализ. Евклидово расстояние
Ближайший сосед
Требуется разделить шесть объектов на два кластера. Объекты -
информационные системы характеризуются двумя признаками:
Х1-среднее время решения одной задачи в минутах;
Х2-количество задач, в решении которых было отказано ввиду перегрузки информационной системы.
Значения признаков Х1 и Х2 для шести вариантов информационной системы представлены в таблице 5.1.1.
Таблица 5.1.1
|
№ Код |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
X1 |
2 |
4 |
5 |
12 |
14 |
15 |
|
|
X2 |
8 |
10 |
7 |
6 |
6 |
4 |
Ввиду того, что размерность признаков сравнительно ненамного отличается друг от друга, то стандартизацию признаков можно не проводить. Если же принято решение о стандартизации, то можно использовать следующий метод.
Берём минимальное значение первого признака Х11=2.
Берём максимальное значение первого признака Х16=15.
Вычислим новые значения первого признака по формуле: х1i=(Х1i-2)/(15-2).
Берём минимальное значение второго признака Х26=4.
Берём максимальное значение второго признака Х22=10.
Вычислим новые значения второго признака: х1i=(Х2i-4)/(10-4).
Результаты вычислений представим в таблице 5.1.1*.
Таблица 5.1.1*
|
№ Код |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
X1 |
0 |
2/13 |
3/13 |
10/13 |
12/13 |
1 |
|
|
X2 |
2/3 |
1 |
1/2 |
1/3 |
1/3 |
0 |
Отметим, что оба признака в таблице 19.1* занимают диапазон от 0 до 1.
Второй способ заключается в таком перерасчёте признаков, чтобы оценки их математических ожиданий стали равными нулю, а оценки средних квадратических отклонений стали равными единице. Для этого используется следующая формула:
xij=(Xij-m1i*)/уi*.
Результаты вычислений приведены в таблице 5.1.1** .
Таблица 5.1.1**
|
№ Код |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
X1 |
-1,18097 |
-0,826682 |
-0,649536 |
0,590 |
0,945 |
1,122 |
|
|
X2 |
0,572 |
1,551 |
0,082 |
-0,408248 |
-0,408248 |
-1,38804 |
По таблице 5.1.1 построен график, представленный на рис.5.1.1.
Рис. 5.1.1
По формуле (5.3) вычислены расстояния между объектами. Приведём два примера вычисления расстояний между 1 и 5 объектами и 2 и 6 объектами.
Процесс вычисления расстояния между 1 и 5 объектами поясняется на рис.5.1.2; между 2 и 6 объектами на рис.5.1.3.
Рис. 5.1.2
Рис.5.1.3
Аналогично по формуле Евклида вычислены расстояния между всеми остальными объектами по двум признакам. Результаты вычислений представлены в виде таблицы 5.1.2
Таблица 5.1.2
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
1 |
0 |
2,83 |
3,16 |
10,19 |
12,17 |
13,60 |
|
|
2 |
0 |
3,16 |
8,94 |
10,77 |
12,53 |
||
|
3 |
0 |
7,07 |
9,06 |
10,44 |
|||
|
4 |
0 |
2,00 |
3,61 |
||||
|
5 |
0 |
2,24 |
|||||
|
6 |
0 |
Жирным шрифтом в таблице 5.1.2 выделено наименьшее расстояние между четвёртым и пятым объектами. Их объединяем в один объект 4,5. Расстояния между этим укрупнённым и исходными объектами определены по принципу «ближайшего соседа». На рис.5.1.4 поясним этот принцип для определения расстояния между 1 объектом и формируемой совокупностью, состоящей из 4 и 5 объектов.
Рис. 19.4
Аналогично предыдущему определены расстояния других объектов с формируемой совокупностью, состоящей из 4 и 5 объектов, и составлена таблица расстояний , представленная в таблице 5.1.3.
Таблица 5.1.3
|
1 |
2 |
3 |
4,5 |
6 |
||
|
1 |
0 |
2,83 |
3,16 |
10,19 |
13,60 |
|
|
2 |
0 |
3,16 |
8,94 |
12,53 |
||
|
3 |
0 |
7,07 |
10,44 |
|||
|
4,5 |
0 |
2,24 |
||||
|
6 |
0 |
Жирным шрифтом в таблице 5.1.3 выделено наименьшее расстояние между объектом 4,5 и шестым объектом. Их объединяем в один объект 4,5,6. Расстояния между этим укрупнённым и исходными объектами определены по правилу «ближайшего соседа» и приведены в таблице 5.1.4.
Таблица 5.1.4
|
1 |
2 |
3 |
4,5,6 |
||
|
1 |
0 |
2,83 |
3,16 |
10,19 |
|
|
2 |
0 |
3,16 |
8,94 |
||
|
3 |
0 |
7,07 |
|||
|
4,5,6 |
0 |
Жирным шрифтом в таблице 5.1.4 выделено наименьшее расстояние меж-ду первым и вторым объектами. Их объединяем в один объект 1,2. Расстояния между этим укрупнённым и другими объектами определены по правилу «ближайшего соседа» и представлены в таблице 5.1.5.
Таблица 5.1.5
|
1,2 |
3 |
4,5,6 |
||
|
1,2 |
0 |
3,16 |
8,94 |
|
|
3 |
0 |
7,07 |
||
|
4,5,6 |
0 |
Жирным шрифтом в таблице 5.1.5 выделено наименьшее расстояние между объединённым объектом 1,2 и третьим объектом. Их объединяем в один объект 1,2,3. Расстояния между укрупнёнными объектами опреде-лены по правилу «ближайшего соседа» и приведены в таблице 5.1.6.
Таблица 5.1.6
|
1,2,3 |
4,5,6 |
||
|
1,2,3 |
0 |
7,07 |
|
|
4,5,6 |
0 |
Таким образом процесс кластерного анализа закончен . Выделено два кластера. Расстояние между кластерами равно 7,07. Дендрограмма резуль-татов кластерного анализа приведена на рис. 5.1.5.
Рис.5.1.5
Представим результаты кластерного анализа в виде двух матриц: расстояний между объектами (таблица 5.1.7) и символов Кронекера (таблица 5.1.8).
Таблица 5.1.7
|
№ объектов |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
0 |
2,83 |
3,16 |
10,19 |
12,17 |
13,60 |
|
|
2 |
0 |
3,16 |
8,94 |
10,77 |
12,53 |
||
|
3 |
0 |
7,07 |
9,06 |
10,44 |
|||
|
4 |
0 |
2,00 |
3,61 |
||||
|
5 |
0 |
2,24 |
|||||
|
6 |
0 |
Таблица 5.1.8
|
№ объектов |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
0 |
1,00 |
1,00 |
0,00 |
0,00 |
0,00 |
|
|
2 |
0 |
1,00 |
0,00 |
0,00 |
0,00 |
||
|
3 |
0 |
0,00 |
0,00 |
0,00 |
|||
|
4 |
0 |
1,00 |
1,00 |
||||
|
5 |
0 |
1,00 |
|||||
|
6 |
0 |
Подсчитаем сумму расстояний между объектами:
0+2,83+3,16+10,19+12,17+13,60+0+ 0+ 3,16+ 8,94+10,77+12,53+0+ 0+ 0+ 7,07+ 9,06+10,44+0+ 0+ 0+ 0+ 2+ 3,61+0+ 0+ 0+ 0+ 0+ 2,24 =111,77.
Среднее расстояние = 111,77/15=7,45.
Сумма расстояний между объектами, вошедшими в кластеры:
1•2,83+1•3,16+1•3,16+1•2,00+1•3,61+1•2,24=17,00.
Среднее расстояние между объектами в кластерах = 17,00/6=2,83.
Сумма расстояний между объектами, находящимися в разных кластерах:
(1-0)•10,19+(1-0)•12,17+(1-0)•13,60++(1-0)•8,94+(1-0)•10,77+(1-0)•12,53+(1-0)•7,07+(1-0)•9,06+ (1-0)•10,44= 94,77.
Среднее расстояние между объектами, находящимися в разных кластерах =94,77/9=10,53.
Таким образом, мы убедились, что условия постановки задачи (19.1) и
(19.2) выполнены, т.е. среднее расстояние между элементами в кластерах более, чем в два с половиной раза меньше чем среднее расстояние между объектами: 7,45/2,83=2,63; а расстояние между объектами, находящимися в различных кластерах почти в полтора раза превышает среднее расстояние между объектами =10,53/7,45.
Пример 5.2. Кластерный анализ. Евклидово расстояние. Наиболее удалённый сосед
Требуется разделить шесть объектов на два кластера. Объекты - информационные системы характеризуются двумя признаками:
Х1-среднее время решения одной задачи в минутах;
Х2-количество задач, в решении которых было отказано ввиду перегрузки информационной системы.
Значения признаков Х1 и Х2 для шести объектов представлены в таблице 5.2.1.
Таблица 5.2.1
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
X1 |
2 |
4 |
5 |
12 |
14 |
15 |
|
|
X2 |
8 |
10 |
7 |
6 |
6 |
4 |
Вычислены расстояния между объектами по формуле Евклида по всем признакам, которые приведены в таблице 5.2.2.
Таблица 5.2.2
|
№ объектов |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
0 |
2,83 |
3,16 |
10,19 |
12,17 |
13,60 |
|
|
2 |
0 |
3,16 |
8,94 |
10,77 |
12,53 |
||
|
3 |
0 |
7,07 |
9,06 |
10,44 |
|||
|
4 |
0 |
2,00 |
3,61 |
||||
|
5 |
0 |
2,24 |
|||||
|
6 |
0 |
Жирным шрифтом в таблице 5.2.2 выделено наименьшее расстояние между четвёртым и пятым объектами. Их объединяем в один объект 4,5. Расстояния между этим укрупнённым и исходными объектами определены по принципу «наиболее удалённого соседа», применение которого для вычисления расстояния между 1 объектом и формируемым объектом, который состоит из 4 и 5 объектов поясняет рис.5.2.1 .
Рис.5.2.1
Аналогично определены расстояния между другими объектами и объектом, состоящим из 4 и 5 объектов, и составлена таблица расстояний 5.2.3.
Таблица 5.2.3
|
1 |
2 |
3 |
4,5 |
6 |
||
|
1 |
0 |
2,83 |
3,16 |
12,17 |
13,60 |
|
|
2 |
0 |
3,16 |
10,77 |
12,53 |
||
|
3 |
0 |
9,06 |
10,44 |
|||
|
4,5 |
0 |
3,61 |
||||
|
6 |
0 |
Жирным шрифтом в таблице 5.2.3 выделено наименьшее расстояние
между первым и вторым объектами. Их объединяем в один объект 1,2. Расстояния между этим укрупнённым и остальными объектами определены по правилу « наиболее удалённого соседа» и представлены в таблице 5.2.4.
Таблица 5.2.4
|
1,2 |
3 |
4,5 |
6 |
||
|
1,2 |
0 |
3,16 |
12,17 |
13,60 |
|
|
3 |
0 |
9,06 |
10,44 |
||
|
4,5 |
0 |
3,61 |
|||
|
6 |
0 |
Жирным шрифтом в таблице 5.2.4 выделено наименьшее расстояние между объектом 1.2 и третьим объектом. Их объединяем в один объект 1,2,3.
Расстояния между этим укрупнённым и другими объектами определены по правилу «наиболее удалённого соседа» и приведены в таблице 5.2.5.
Таблица 5.2.5
|
1,2,3 |
4,5 |
6 |
||
|
1,2,3 |
0 |
12,17 |
13,60 |
|
|
4,5 |
0 |
3,61 |
||
|
6 |
0 |
Жирным шрифтом в таблице 5.2.5 выделено наименьшее расстояние между объединённым объектом 4,5 и шестым объектом. Их объединяем в один объект 4,5.6. Расстояния между укрупнёнными объектами определены по правилу «наиболее удалённого соседа» и приведены в таблице 5.2.6.
Таблица 5.2.6
|
1,2,3 |
4,5,6 |
||
|
1,2,3 |
0 |
13.60 |
|
|
4,5,6 |
0 |
Таким образом процесс кластерного анализа закончен. Выделено два кластера. Расстояние между кластерами равно 13,6. Дендрограмма результа-тов кластерного анализа приведена на рис. 5.2.2.
Рис.5.2.2
Пример 5.3. Кластерный анализ. Евклидово расстояние. По среднему значению
Требуется разделить шесть объектов на два кластера. Объекты -
информационные системы характеризуются двумя признаками:
Х1-среднее время решения одной задачи в минутах;
Х2-количество задач, в решении которых было отказано ввиду перегрузки информационной системы.
Значения признаков Х1 и Х2 для шести объектов приведены в таблице 5.3.1.
Таблица 5.3.1
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
X1 |
2 |
4 |
5 |
12 |
14 |
15 |
|
|
X2 |
8 |
10 |
7 |
6 |
6 |
4 |
Вычислены расстояния между объектами по формуле Евклида по двум признакам, которые приведены в таблице 5.3.2.
Таблица 5.3.2
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
1 |
0 |
2,83 |
3,16 |
10,19 |
12,17 |
13,60 |
|
|
2 |
0 |
3,16 |
8,94 |
10,77 |
12,53 |
||
|
3 |
0 |
7,07 |
9,06 |
10,44 |
|||
|
4 |
0 |
2,00 |
3,61 |
||||
|
5 |
0 |
2,24 |
|||||
|
6 |
0 |
Жирным шрифтом в таблице 19.16 выделено наименьшее расстояние между четвёртым и пятым объектами. Их объединяем в один объект 4,5. Расстояния между этим укрупнённым и исходными объектами определены по принципу «среднего значения» и представлены в таблице 19.17. Вычисление среднего расстояния пояснено на рис.5.3.1
Рис.5.3.1
Таблица 19.17
|
1 |
2 |
3 |
4,5 |
6 |
||
|
1 |
0 |
2,83 |
3,16 |
11,18 |
13,60 |
|
|
2 |
0 |
3,16 |
9,855 |
12,53 |
||
|
3 |
0 |
8,065 |
10,44 |
|||
|
4,5 |
0 |
2,925 |
||||
|
6 |
0 |
Жирным шрифтом в таблице 19.17 выделено наименьшее расстояние между первым и вторым объектами. Их объединяем в один объект 1,2. Расстояния между этим укрупнённым и остальными объектами определены по принципу « среднего значения» и представлены в таблице 19.18.
Таблица 19.18
|
1,2 |
3 |
4,5 |
6 |
||
|
1,2 |
0 |
3,16 |
10,5175 |
13,065 |
|
|
3 |
0 |
8,0650 |
10,44 |
||
|
4,5 |
0 |
2,925 |
|||
|
6 |
0 |
Жирным шрифтом в таблице 18.19 выделено наименьшее расстояние между объектом 4,5 и шестым объектом. Их объединяем в один объект 4,5,6. Расстояния между этим укрупнённым и другими объектами определены по правилу «среднего значения» и представлены в таблице 19.19.
Таблица 19.19
|
1,2 |
3 |
4,5,6 |
||
|
1,2 |
0 |
3,16 |
11,79125 |
|
|
3 |
0 |
9,25250 |
||
|
4,5.6 |
0 |
Жирным шрифтом в таблице 19.19 выделено наименьшее расстояние между объединённым объектом 1,2 и третьим объектом. Их объединяем в один объект 1,2,3. Расстояния между укрупнёнными объектами определены по правилу «среднего значения» и представлены в таблице 19.20.
Таблица 19.20
|
1,2,3 |
4,5,6 |
||
|
1,2,3 |
0 |
10,521875 |
|
|
4,5,6 |
0 |
Таким образом процесс кластерного анализа закончен. Выделено два кластера. Расстояние между выделенными кластерами равно 10,52. Дендрограмма результатов кластерного анализа представлена на рис. 19.9.
Рис.19.9
Пример 5.4. Кластерный анализ. Евклидово расстояние.
По медиане
Требуется разделить шесть объектов на два кластера. Объекты - информационные системы характеризуются двумя признаками:
Х1-среднее время решения одной задачи в минутах;
Х2-количество задач, в решении которых было отказано ввиду перегрузки информационной системы.
Значения признаков Х1 и Х2 для шести объектов представлены в таблице 19.21.
Таблица 19.21
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
X1 |
2 |
4 |
5 |
12 |
14 |
15 |
|
|
X2 |
8 |
10 |
7 |
6 |
6 |
4 |
Вычислены расстояния между объектами по формуле Евклида по двум признакам, которые представлены в таблице 19.22.
Таблица 19.22
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
1 |
0 |
2,83 |
3,16 |
10,19 |
12,17 |
13,60 |
|
|
2 |
0 |
3,16 |
8,94 |
10,77 |
12,53 |
||
|
3 |
0 |
7,07 |
9,06 |
10,44 |
|||
|
4 |
0 |
2,00 |
3,61 |
||||
|
5 |
0 |
2,24 |
|||||
|
6 |
0 |
Жирным шрифтом в таблице 19.22 выделено наименьшее расстояние между четвёртым и пятым объектами. Их объединяем в один объект 4,5. Расстояния между этим укрупнённым и исходными объектами определены по принципу «медианы» и представлены в таблице 19.23. Применение принципа по вычислению расстояния между первым объектом и формирующимся объектом, состоящим из 4 и 5 объектов поясняется рис.5.4.1.
Таблица 19.23
|
1 |
2 |
3 |
4,5 |
6 |
||
|
1 |
0 |
2,83 |
3,16 |
7,8692705 |
13,60 |
|
|
2 |
0 |
3,16 |
6,9266965 |
12,53 |
||
|
3 |
0 |
5,6583675 |
10,44 |
|||
|
4,5 |
0 |
2,8328 |
||||
|
6 |
0 |
Жирным шрифтом в таблице 19.23 выделено наименьшее расстояние между первым и вторым объектами. Их объединяем в один объект 1,2. Расстояния между этим укрупнённым и остальными объектами определены по правилу « медианы» и представлены в таблице 19.24.
Таблица 19.24
|
1,2 |
3 |
4,5 |
6 |
||
|
1,2 |
0 |
2,8254866 |
7,2767125 |
12.999162 |
|
|
3 |
0 |
5,6583675 |
10,44 |
||
|
4,5 |
0 |
2,8328 |
|||
|
6 |
0 |
Жирным шрифтом в таблице 19.24 выделено наименьшее расстояние между объектом 1,2 и третьим объектом. Их объединяем в один объект 1,2.3. Расстояния между этим укрупнённым и другими объектами определены по правилу «медианы» и представлены в таблице 19.25.
Таблица 19.25
|
1,2,3 |
4,5 |
6 |
||
|
1,2,3 |
0 |
6,363017 |
11,704275 |
|
|
4,5 |
0 |
2,8328 |
||
|
6 |
0 |
Жирным шрифтом в таблице 19.25 выделено наименьшее расстояние между объединённым объектом 4,5 и шестым объектом. Их объединяем в один объект 4,5,6. Расстояния между укрупнёнными объектами определены по правилу «медианы» и представлены в таблице 19.26.
Таблица 19.26
|
1,2,3 |
4,5,6 |
||
|
1,2,3 |
0 |
9,4201385 |
|
|
4,5,6 |
0 |
Таким образом, процесс кластерного анализа закончен. Выделено два кластера. Расстояние между кластерами равно 9,42. Дендрограмма результатов кластерного анализа представлена на рис. 19.11.
Рис.19.11. Результаты кластерного анализа
По типовым представителям
Требуется разделить шесть объектов на два кластера. Объекты - информационные системы характеризуются двумя признаками:
Х1-среднее время решения одной задачи в минутах;
Х2-количество задач, в решении которых было отказано ввиду перегрузки информационной системы.
Значения признаков Х1 и Х2 для шести объектов представлены в таблице 19.27.
Таблица 19.27
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
X1 |
2 |
4 |
5 |
12 |
14 |
15 |
|
