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 в виде дендрограммы.
| < Предыдущая | Следующая > |
|---|
