12. Решение задач кластерного анализа в интегрированных системах

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

Таблица 9

Исходные данные

№ п/п

1

2

3

4

5

6

Х1

2

4

5

12

14

15

Х2

8

10

7

6

6

4

Где х1 - объем выпускаемой продукции;

х2 - среднегодовая стоимость основных промышленно-производственных фондов. Зависимость между признаками приведена на рис. 12.

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

1. Принцип “ближайшего соседа”.

Решение задачи:

В Excel 7.0 создаем таблицу с исходными данными и таблицы (матрицы) с расчетами (табл.10).

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

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

,

Где l - признаки; k - количество признаков, расстояние между объектами 1 и 2 равно:

Р11=0; .

Расчеты последующих расстояний Аналогичны.

1. Формулу: =КОРЕНЬ((B5-B5)^2+(B6-B6)^2) помещаем в ячейку В14 и рассчитываем расстояние р11, затем в ячейке В15 - расстояние р12 по формуле: =КОРЕНЬ((B5-C5)^2+(B6-C6)^2) и т. д., пока не будет произведен расчет расстояний между всеми шестью объектами (ячейки В14:В29):

P11=0; p12=2.83; p13=3.16; p14=10.20; p15=12.17;

P16=13.6; p23=3.16; p24=8.94; p25=10.77; p26=12.53;

P34=7.07; p35=9.06; p36=10.44; p45=2; p46=3.61; p56=2.24.

2. Полученные данные помещаем в таблицу (матрицу) - ячейки D15:J21. Из матрицы расстояний следует, что объекты 4 и 5 наиболее близки P45=2.00 и поэтому объединяются в один кластер. Для расчета наименьшего расстояния используется формула: =МИН(F16:J16;G17:J17;H18:J18;I19:J19;J20) - ячейка E22.

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

Номер кластера

1

2

3

4

5

Состав кластера

(1)

(2)

(3)

(4,5)

(6)

3. Матрицу расстояний помещаем в ячейки D25 - I30, воспользуемся этой матрицей расстояний, чтобы рассчитать расстояние объединяемых объектов 4,5 и 6, которые имеют наименьшее расстояние PMIN=P4,5,6=2.24 (формула =МИН(F26:I26;G27:I27;H28:I28;I29 в ячейке E32). После объединения имеем четыре кластера: S(1), S(2), S(3), S(4,5,6).

Таблица 10

Исходные данные

4. Вновь находим матрицу расстояний (табл.11), помещаем рассчитанные значения в ячейки D35 - H39 и объединяем объекты 1 и 2, имеющие наименьшее расстояние PMIN=P1,2=2.83 (формула =МИН(F36:H36;G37:H37;H38) в ячейке E41). Расстояние между остальными кластерами остается без изменения. В результате имеем три кластера: S(1,2), S(3), S(4,5,6).

5. Объединим теперь объекты 1,2 и 3, расстояние между которыми равно: PMIN=P1,2,3=3.16 (формула =МИН(F45:G45;G46) в ячейке E49.

6. Таким образом, при проведении кластерного анализа по принципу “ближайшего соседа” получили два кластера: S(1,2,3), S(4,5,6), расстояние между которыми равно:

P(1,2,3); (4,5,6) = 7,07.

Таблица 11

Расчетные значения

Результаты иерархической классификации объектов представлены на рис.13 в виде

Дерева объединения кластеров - дендрограммы, где по оси ординат приводятся расстояния между объединяемыми на данном этапе кластерами.

Рис.13. Дендрограмма

2. Принцип “дальнего соседа”.

Решение задачи:

Расчеты расстояний Аналогичны предыдущему принципу.

1. Формулу: =КОРЕНЬ((B3-B3)^2+(B4-B4)^2) помещаем в ячейку В9 и рассчитываем расстояние р11, затем в ячейке В10 - расстояние р12 по формуле: =КОРЕНЬ((B3-C3)^2+(B4-C4)^2) и т. д., пока не будет произведен расчет расстояний между всеми шестью объектами (ячейки В9:В24):

P11=0; p12=2.83; p13=3.16; p14=10.20; p15=12.17;

P16=13.6; p23=3.16; p24=8.94; p25=10.77; p26=12.53;

P34=7.07; p35=9.06; p36=10.44; p45=2; p46=3.61; p56=2.24.

Полученные данные помещаем в таблицу (матрицу) - ячейки E11:K17 (табл.12). Из матрицы расстояний следует, что объекты 4 и 5 имеют наименьшее значение P45=2.00 и поэтому объединяются в один кластер. Для расчета расстояния используется формула: =МИН(G12:K12;H13:K13;I14:K14;J15:K15;K16) в ячейке F19.

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

Номер кластера

1

2

3

4

5

Состав кластера

(1)

(2)

(3)

(4,5)

(6)

2. Для решения задачи воспользуемся принципом “дальнего соседа”: искомое расстояние между кластерами S(4), S(5) p15=12.17, т. к. p15=12.17 больше p14=10.20, поэтому матрица расстояний примет вид (ячейки E22:J27):

Для расчета расстояния применим формулу =МИН(G23;H23:H24;I23:I25;J23:J26), помещенную в ячейке F29, получив расстояние PMIN=P2,3=2.83. Объединяем кластеры 1и 2 в один.

Таблица 12

Исходные данные

После объединения имеем матрицу расстояний, отображенную в табл.13 и следующие кластеры: S(1,2), S(3), S(4,5), S(6).

3. Вновь находим матрицу расстояний, помещаем рассчитанные значения в ячейки E32 - I36 и объединяем объекты 1,2 и 3, имеющие расстояние PMIN=P1,2=3.16 (формула =МИН(G33:I33;H34:I34;I35) в ячейке F38). Расстояние между остальными кластерами остается без изменения. В результате имеем три кластера: S(1,2,3), S(4,5), S(6).

4. Объединим теперь объекты 4,5 и 6, расстояние между которыми равно: PMIN=P1,2,3=3.61 (формула =МИН(G42:H42;H43) в ячейке F46). Матрица расстояний размещается в ячейках E41-H44.

5. Таким образом, при проведении кластерного анализа по принципу “дальнего соседа” получили два кластера: S(1,2,3), S(4,5,6), расстояние между которыми равно:

P(1,2,3); (4,5,6) = 13,60.

Таблица 13.

Расчетные значения

Результаты иерархической классификации объектов представлены на рис. 14 в виде дендрограммы.

Рис. 14. Дендрограмма

© 2011-2024 Контрольные работы по математике и другим предметам!