7.4.3. Формализация процесса кластеризации

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

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

- к одному кластеру относятся те объекты, которые расположены достаточно близко друг к другу,

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

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

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

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

Суть метода заключается в следующем.

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

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

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

3. Операция 2 выполняется до тех пор, пока все объекты не станут сгруппированными.

4. В результате выполнения п.п. 2, 3 получается последовательность (цепочка) расстояний с указанием объектов, для которых эти расстояния вычислены.

5. К полученной последовательности применяется технология выявления промахов в ряду наблюдений (см. работу «Случайные величины»).

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

7.4.4. Порядок выполнения работы

Для выполнения работы используется файл Кластерный анализ.xls.

На Лист2 этой книги находятся данными о 78 объектах РФ (6 показателей).

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

Таблица 7.1

N п/п	N по списку	Объект	X1	X2
1	20	Кировская обл.	1560	1451
2	31	Нижегородская обл.	3598	2045,3
3	35	Оренбургская обл.	2199	1774,4
4	37	Пензенская обл.	1504	1440,5
5	43	Республика Башкортостан	4091	2339,7
6	44	Республика Бурятия	1019	1765,2
7	45	Республика Дагестан	2179	1197
8	46	Республика Ингушетия	466	1008,2
9	50	Республика Марий Эл	750	1052,3
10	51	Республика Мордовия	910	1497,7
11	54	Республика Татарстан	3768	2362,4
12	70	Удмуртская Республика	1616	1833
13	71	Ульяновская обл.	1440	1558,9
14	75	Чувашская Республика	1346	1326,2

Для имеющихся 14 объектов необходимо провести двумерную кластеризацию по двум первым показателям (Численность населения (тыс. чел.) и Средний доход на душу населения (руб/мес)). Эти показатели отражаются на имеющейся на этом же листе точечной диаграмме.

Для получения цепочки расстояний достаточно щелкнуть по кнопке «Расчет». В результате будут получены следующие результаты.

Таблица 7.2

		E	F	G	H
10		N	Расстояния	Номер1	Номер2
11		1	1,580785941	1	4
12		2	4,172284936	4	13
13		3	5,684705731	4	14
14		4	10,00815363	12	13
15		5	13,21538863	10	14
16		6	9,05471484	6	10
17		7	14,89015946	9	10
18		8	7,960007134	8	9
19		9	16,191226	3	12
20		10	18,44375842	3	7
21		11	39,5504765	2	3
22		12	11,1579027	2	11
23		13	8,939773259	5	11

Для 14 объектов получена цепочка, состоящая из 13 расстояний.

Процедура выделения кластеров производится следующим образом:

– просмотр начинается с первого расстояния. Оно сравнивается со вторым и третьим расстояниями. Все они пока одного порядка. Но четвертое расстояние подозрительно велико по сравнению с первыми тремя.

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

При этом для расстояний 1 – 4 вычисляются среднее и дисперсия и на их основе V-критерий.

Для этого:

• в ячейку B24 вводится формула =СРЗНАЧ(F11:F14);

• в ячейку B25 вводится формула =ДИСПРА(F11:F14);

• в ячейку B26 вводится формула =ABS(B24-F14)/(3/4*B25)^(1/2).

В результате получено следующее:

	A	B
24	Среднее	5,36148256
25	Дисперсия	9,350970798
26	V-критерий	1,754619489

Далее необходимо сравнить вычисленный критерий с табличным. При уровне значимости, равном 0,05, для четырех измерений этот критерий равен 1,69. Таким образом, вычисленное значение критерия больше табличного. Поэтому делается вывод о том, что проверяемое значение (10,00815363), действительно является промахом, т.е. резко отличается от остальных значений.

В табл. 7.2 эти строки выделены.

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

В результате:

к первому кластеру можно отнести объекты входящий в перечень до этого расстояния – объекты 1, 4, 13 и 14.

Аналогично должны быть рассмотрены оставшиеся расстояния.

Для этого:

– просмотр начинается с 5 расстояния. Очевидно, что расстояния 5 – 10 одного порядка. А расстояние 11 «подозрительно» большое.

Для его проверки выполним аналогичные вычисления:

• в ячейку C24 вводится формула =СРЗНАЧ(F15:F21);

• в ячейку C25 вводится формула =ДИСПРА(F15:F21);

• в ячейку C26 вводится формула =ABS(C24-F21)/(6/7*C25)^(1/2).

Результат вычислений:

	A	B	C
24	Среднее	5,36148256	17,043676
25	Дисперсия	9,350970798	96,410418
26	V-критерий	1,754619489	2,4758548

Вычисленное значение V-критерия также больше табличного (V=2,09 для семи измерений и уровня значимости, равного 0,05. Поэтому делаем вывод о том, что расстояние 11 является границей между кластерами и ко второму кластеру следует отнести объекты 12, 10, 6, 9, 8, 3 и 7.

Для оставшихся объектов (2, 5 и 11) проверку можно не производить и их можно отнести к третьему кластеру.

На рис. 7.5 приведены визуализированные результаты кластеризации (исходная диаграмма построена в Excel, а кластеры обведены вручную в Paint).

Рис.7.5. Визуализация результатов кластеризации