Теоретические основы кластерного анализа

 

3.1 Описание объектов кластеризации

Исходный файл данных содержит следующую информацию о  магазинах – координаты в пространстве. Были использованы адреса магазинов сберегайка в Железнодорожном и Заводском районах города Орла.

№	Адреса торговых точек	Часы работы
1	СМ «ЦУМ» г. Орел, пл. Мира, 1	с 8-00 до 22-00
2	СМ «Апельсин» г. Орел, ул. Пушкина, 20	с 8-00 до 24-00
3	Сберегайка г. Орел, 5 Августа 19	с 8-00 до 22-00
4	Сберегайка, г. Орел, Курская 35	с 8-00 до 22-00
5	Сберегайка, г. Орел, Ливенская 20 а	с 8-00 до 21-00
6	Сберегайка, г. Орел, Привокзальная 10	с 7-00 до 22-00
7	Сберегайка, г. Орел, Пушкина 20	с 8-00 до 22-00
8	Сберегайка, г. Орел, Революции 1	с 8-00 до 21-00
9	Сберегайка, г. Орел, Толстого 10	с 8-00 до 22-00
10	Сберегайка, г. Орел, Высокая 1	с 8-00 до 22-00
11	ВКС, г. Орел, Герцена, 2а	круглосуточно
12	СМ «Москва», г. Орел, ул. Комсомольская, 53	с 8-00 до 24-00
13	СМ "Апельсин", г. Орел, ул. Гагарина 51	с 8-00 до 23-00
14	СМ "Апельсин", г. Орел, ул. Васильевская, 138	с 8-00 до 23-00
15	Сберегайка, г. Орел, Гостинная 2/8	с 8-00 до 21-00
16	Сберегайка г. Орел, Комсомольская 139	с 8-00 до 22-00
17	Сберегайка, г. Орел, Кромская 9	с 8-00 до 22-00
18	Сберегайка, г. Орел, Латышских стрелков 1	с 8-00 до 22-00
19	Сберегайка, г. Орел, Машкарина 16	с 8-00 до 22-00
20	Сберегайка, г. Орел, МОПРа 4	с 8-00 до 22-00
21	Сберегайка, г. Орел, Поселковая 6	с 8-00 до 22-00

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

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

В STATISTICA реализованы классические методы кластерного анализа, включая методы k-средних, иерархической кластеризации и двухвходового объединения.

Заполним исходные денные – координаты находятся с помощью Google maps.

 

 

3.2 Разбиение участников рейда на  группы методом древовидной кластеризации

На первом этапе выясним, формируют ли магазины "естественные" кластеры, которые могут быть осмыслены.

Выберем Кластерный анализ в меню Анализ - Многомерный разведочный анализ для отображения стартовой панели модуля Кластерный анализ. В этом диалоге выберем Иерархическая классификация и нажмем OK.

Нажмем кнопку Переменные, выберем Все, в поле Объекты выберем Наблюдения (строки). В качестве правила объединения отметим Метод полной связи, в качестве меры близости – Евклидово расстояние. Нажмем ОК.

  

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

Мера близости, определяемая евклидовым расстоянием, является геометрическим расстоянием в n- мерном пространстве и вычисляется следующим образом:

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

Нажмем на кнопку Вертикальная дендрограмма.

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

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

 

3.3 Разбиение участников рейда на  группы методом К средних

Исходя из визуального  представления результатов, можно  сделать предположение, что магазины образуют четыре естественных кластера. Проверим данное предположение, разбив исходные данные методом К средних  на 4 кластера, и проверим значимость различия между полученными группами.

В Стартовой панели модуля Кластерный анализ выберем Кластеризация методом К средних.

Нажмем кнопку Переменные и выберем Все, в поле Объекты выберем Наблюдения (строки), зададим 4 кластера разбиения.

Метод K-средних заключается в следующем: вычисления начинаются с k случайно выбранных наблюдений (в нашем случае k=4), которые становятся центрами групп, после чего объектный состав кластеров меняется с целью минимизации изменчивости внутри кластеров и максимизации изменчивости между кластерами. Каждое следующее наблюдение (K+1) относится к той группе, мера сходства с центром тяжести которого минимальна.

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

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

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

В окне Результаты метода К средних выберем Дисперсионный анализ для определения значимости различия между полученными кластерами.

Итак, значение р<0.05, что  говорит о значимом различии.

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

Первый кластер:

Второй кластер:

Третий кластер:

Четвертый кластер:

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

Для проверки правильно ли выбрано 4 кластера с помощью метода     К-средних

Для этого  я последовательно разбила на 2 – 6 кластеров и занесла результаты в таблицу:

кластеры	стандартное отклонение	дисперсия	число объектов	итерраций
1	0,019	0,000321	28	1
2	0,209	0,000439	10
ср	0,114	0,00038	38
1	0,0107	0,000116	18	2
2	0,016	0,000276	7
3	0,0208	0,000433	13
ср	0,0158333	0,000275	38
1	0,013893	0,01328	6	3
2	0,01033	0,000107	15
3	0,007938	0,000063	8
4	0,009969	0,000099	9
ср	0,0105325	0,0033873	38
1	0,006551	0,000043	7	3
2	0,010189	0,000104	13
3	0,003041	0,000009	5
4	0,00937	0,000088	4
5	0,009969	0,000099	9
ср	0,007824	0,0000686	38
1	0,00782	0,0061	6	3
2	0,13647	0,000186	5
3	0,003041	0,000009	5
4	0,009583	0,000092	9
5	0,006977	0,00049	6
6	0,010357	0,000107	7
ср	0,0290413	0,001164	38

 

Выбрав минимальную  дисперсию и отклонение – получилось что правильнее всего разбить  на 4 кластера.

 

3.4 Разбиение участников рейда на  группы и выявление центра  сбора участников рейда с помощью  генетических алгоритмов 

После выполнения итераций в GH получились следующие координаты(они являются хромосомами).

 

Была поставлена небольшая вероятность мутации 1% для разнообразия поколений и большая вероятность скрещивания 90%. Размер популяции выбрала равным 50 – это достаточное количество для моего случая. За целевую функцию принимают сумму минимальных расстояний между точками.

Широта	Долгота
52,942	36,05
52,98	36,054
53,007	36,127
52,971	36,083
Целевая функция
0,525

Центры кластеров удобно представить графически, расстояние между ними максимально.

Сравнивая результаты полученные методом к-средних и в генетических алгоритмах мы увидим следующее:

Число точек  в классах
	GH	STATISTICA
Класс 1	9	6
Класс 2	8	15
Класс 3	6	8
Класс 4	15	9
всего	38	38

Это говорит о согласованности результатов кластеризации

 

3.5 Нахождение оптимальных путей  для каждой из групп

Участники должен выйти из точки встречи, посетить по разу в неизвестном порядке магазины 2,1,3..n и вернуться в точку сбора. Расстояния между магазинами известны. В каком порядке следует обходить магазины в течение рейда, чтобы замкнутый путь (тур) участников был кратчайшим?