Теоретические основы кластерного анализа
Кластеризация, решение задач коммивояжера с помощью генетических алгоритмов. Разбиение участников рейда на группы методом древовидной кластеризации, выявление центра сбора участников с помощью генетических алгоритмов. Проверка качества кластеризации.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 05.02.2014 |
| Размер файла | 2,0 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Оглавление
1. Введение
2. Теоретические основы кластерного анализа
2.1 Объединение (древовидная кластеризация)
2.1.1 Иерархическое дерево
2.1.2 Меры расстояния
2.1.3 Правила объединения
2.2 Метод К средних
2.2.1 Описание алгоритма
2.2.2 Проверка качества кластеризации
2.3 Кластеризация с помощью генетических алгоритмов
2.4 Решение задачи коммивояжера с помощью генетических алгоритмов
3.1 Описание объектов кластеризации
3.2 Разбиение участников рейда на группы методом древовидной кластеризации
3.3 Разбиение участников рейда на группы методом К средних
3.4 Разбиение участников рейда на группы и выявление центра сбора участников рейда с помощью генетических алгоритмов
3.5 Нахождение оптимальных путей для каждой из групп
4 Заключение
1. Введение
Постановка задачи следующая. Участники рейда должны выйти из точки встречи, посетить по разу в неизвестном порядке магазины 2, 1, 3.. n и вернуться в точку сбора. Расстояния между магазинами известны. В каком порядке следует обходить магазины в течение рейда, чтобы замкнутый путь (тур) участников был кратчайшим?
По сути это задача Коммивояжёра. Задача о бродячем торговце, одна из известных задач конечной математики. Формулируется следующим образом: даны n городов и известны расстояния между каждыми двумя городами; коммивояжёр, выходящий из какого-нибудь города, должен посетить n - 1 других городов и вернуться в исходный. В каком порядке ему нужно посещать города (по одному разу каждый), чтобы общее пройденное расстояние было минимальным? К задачам такого типа, связанным с объездом ряда пунктов и возвращением в исходную точку, относятся: задачи доставки продуктов питания в магазины, подвода электроэнергии к потребителям, построения кольцевой линии электропередач, различные задачи, возникающие при автоматизации монтажа схем. Методы решения Коммивояжёра задачи сводятся к организации полного перебора вариантов; никакого эффективного алгоритма не известно.
Магазинов всего 38, для этого участники разбиваются на группы, для экономии времени. Оптимальное количество групп определяется с помощью кластерного анализа.
«Кластерный анализ - совокупность математических методов, предназначенных для формирования относительно «отдаленных» друг от друга групп «близких» между собой объектов по информации о расстояниях или связях (мерах близости) между ними. По смыслу аналогичен терминам: автоматическая классификация, таксономия, распознавание образов без учителя. « Такое определение кластерного анализа дано в последнем издании «Статистического словаря». Фактически «кластерный анализ» - это обобщенное название достаточно большого набора алгоритмов, используемых при создании классификации. Кластерный анализ широко используется в науке как средство типологического анализа. В любой научной деятельности классификация является одной из фундаментальных составляющих, без которой невозможны построение и проверка научных гипотез и теорий. Таким образом, в работе рассматриваются основы кластерного анализа.
Ленивые люди ищут простейшие пути прохождения. От выбора порядка прохождения контрольных точек зависит время прохождения, а так же затраты на дорогу. В пути тратятся драгоценные физические силы, являющиеся ограниченным человеческим ресурсом, а успеть необходимо многое. Эту задачу решают спортсмены во время спортивного ориентирования, почтальон при разносе пенсий и почты, а так же проверяющие предприятий. Это все подтверждает актуальность данной работы древности.
2. Теоретические основы кластерного анализа
древовидная кластеризация коммивояжер
Термин кластерный анализ (впервые ввел Tryon, 1939) в действительности включает в себя набор различных алгоритмов классификации. Общий вопрос, задаваемый исследователями во многих областях, состоит в том, как организовать наблюдаемые данные в наглядные структуры, т. е. развернуть таксономии.
Фактически, кластерный анализ является не столько обычным статистическим методом, сколько «набором» различных алгоритмов «распределения объектов по кластерам». Существует точка зрения, что в отличие от многих других статистических процедур, методы кластерного анализа используются в большинстве случаев тогда, когда вы не имеете каких-либо априорных гипотез относительно классов, но все еще находитесь в описательной стадии исследования. Кластерный анализ определяет «наиболее возможно значимое решение».
Техника кластеризации применяется в самых разнообразных областях. Хартиган (Hartigan, 1975) дал прекрасный обзор многих опубликованных исследований, содержащих результаты, полученные методами кластерного анализа. Ввсякий раз, когда необходимо классифицировать «горы» информации к пригодным для дальнейшей обработки группам, кластерный анализ оказывается весьма полезным и эффективным.
2.1 Объединение (древовидная кластеризация)
Назначение этого алгоритма состоит в объединении объектов в достаточно большие кластеры, используя расстояние между объектами. Типичным результатом такой кластеризации является иерархическое дерево.
2.1.1 Иерархическое дерево
Рассмотрим горизонтальную древовидную диаграмму. Диаграмма начинается с каждого объекта в классе (в левой части диаграммы). Постепенно (очень малыми шагами) ослабляется критерий о том, какие объекты являются уникальными, а какие нет. Другими словами, понижается порог, относящийся к решению об объединении двух или более объектов в один кластер.
В результате, связываеся вместе всё большее и большее число объектов и агрегируется (объединяется) все больше и больше кластеров, состоящих из все сильнее различающихся элементов. Окончательно, на последнем шаге все объекты объединяются вместе. На этих диаграммах горизонтальные оси представляют расстояние объединения (в вертикальных древовидных диаграммах вертикальные оси представляют расстояние объединения). Так, для каждого узла в графе (там, где формируется новый кластер) можно видеть величину расстояния, для которого соответствующие элементы связываются в новый единственный кластер. Когда данные имеют ясную «структуру» в терминах кластеров объектов, сходных между собой, тогда эта структура, скорее всего, должна быть отражена в иерархическом дереве различными ветвями. В результате успешного анализа методом объединения появляется возможность обнаружить кластеры (ветви) и интерпретировать их.
2.1.2 Меры расстояния
Объединение или метод древовидной кластеризации используется при формировании кластеров расстояния между объектами. Эти расстояния могут определяться в одномерном или многомерном пространстве. Наиболее прямой путь вычисления расстояний между объектами в многомерном пространстве состоит в вычислении евклидовых расстояний. Если есть двух- или трёхмерное пространство, то эта мера является реальным геометрическим расстоянием между объектами в пространстве (как будто расстояния между объектами измерены рулеткой). Однако алгоритм объединения не «заботится» о том, являются ли «предоставленные» для этого расстояния настоящими или некоторыми другими производными мерами расстояния, что более значимо для исследователя; и задачей исследователей является подобрать правильный метод для специфических применений.
Евклидово расстояние. Это наиболее общий тип расстояния. Оно попросту является геометрическим расстоянием в многомерном пространстве и вычисляется следующим образом:
расстояние (x, y) = {i (xi - yi) 2 }1/2
Евклидово расстояние (и его квадрат) вычисляется по исходным, а не по стандартизованным данным. Это обычный способ его вычисления, который имеет определенные преимущества (например, расстояние между двумя объектами не изменяется при введении в анализ нового объекта, который может оказаться выбросом). Тем не менее, на расстояния могут сильно влиять различия между осями, по координатам которых вычисляются эти расстояния. К примеру, если одна из осей измерена в сантиметрах, а вы потом переведете ее в миллиметры (умножая значения на 10), то окончательное евклидово расстояние (или квадрат евклидова расстояния), вычисляемое по координатам, сильно изменится, и, как следствие, результаты кластерного анализа могут сильно отличаться от предыдущих.
Квадрат евклидова расстояния. Иногда может возникнуть желание возвести в квадрат стандартное евклидово расстояние, чтобы придать большие веса более отдаленным друг от друга объектам. Это расстояние вычисляется следующим образом:
расстояние (x, y) = i (xi - yi) 2
Расстояние городских кварталов (манхэттенское расстояние). Это расстояние является просто средним разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако отметим, что для этой меры влияние отдельных больших разностей (выбросов) уменьшается (так как они не возводятся в квадрат). Манхэттенское расстояние вычисляется по формуле:
расстояние (x, y) = i |xi - yi|
Расстояние Чебышева. Это расстояние может оказаться полезным, когда желают определить два объекта как «различные», если они различаются по какой-либо одной координате (каким-либо одним измерением). Расстояние Чебышева вычисляется по формуле:
расстояние (x, y) = Максимум|xi - yi|
Степенное расстояние. Иногда желают прогрессивно увеличить или уменьшить вес, относящийся к размерности, для которой соответствующие объекты сильно отличаются. Это может быть достигнуто с использованием степенного расстояния. Степенное расстояние вычисляется по формуле:
расстояние (x, y) = (i |xi - yi|p) 1/r
где r и p - параметры, определяемые пользователем. Несколько примеров вычислений могут показать, как «работает» эта мера. Параметр p ответственен за постепенное взвешивание разностей по отдельным координатам, параметр r ответственен за прогрессивное взвешивание больших расстояний между объектами. Если оба параметра - r и p, равны двум, то это расстояние совпадает с расстоянием Евклида.
Процент несогласия. Эта мера используется в тех случаях, когда данные являются категориальными. Это расстояние вычисляется по формуле:
расстояние (x, y) = (Количество xi yi) /
2.1.3 Правила объединения или связи
На первом шаге, когда каждый объект представляет собой отдельный кластер, расстояния между этими объектами определяются выбранной мерой. Однако когда связываются вместе несколько объектов, возникает вопрос, как следует определить расстояния между кластерами? Другими словами, необходимо правило объединения или связи для двух кластеров. Здесь имеются различные возможности: например, можно связать два кластера вместе, когда любые два объекта в двух кластерах ближе друг к другу, чем соответствующее расстояние связи. Другими словами, используется «правило ближайшего соседа» для определения расстояния между кластерами; тот метод называется методом одиночной связи. Это правило строит «волокнистые» кластеры, т. е. кластеры, «сцепленные вместе» только отдельными элементами, случайно оказавшимися ближе остальных друг к другу. Как альтернативу вы можете использовать соседей в кластерах, которые находятся дальше всех остальных пар объектов друг от друга. Этот метод называется метод полной связи. Существует также множество других методов объединения кластеров, подобных тем, что были рассмотрены.
Одиночная связь (метод ближайшего соседа). Как было описано выше, в этом методе расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. Это правило должно, в известном смысле, нанизывать объекты вместе для формирования кластеров, и результирующие кластеры имеют тенденцию быть представленными длинными «цепочками».
Полная связь (метод наиболее удаленных соседей). В этом методе расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т. е. «наиболее удаленными соседями»). Этот метод обычно работает очень хорошо, когда объекты происходят на самом деле из реально различных «рощ». Если же кластеры имеют в некотором роде удлиненную форму или их естественный тип является «цепочечным», то этот метод непригоден.
2.2 Метод K средних
Имея гипотезы относительно числа кластеров (по построению точек на плоскости), системе указывается образовать ровно четыре кластера так, чтобы они были настолько различны, насколько это возможно. Это именно тот тип задач, которые решает алгоритм метода K средних. В общем случае метод K средних строит ровно K различных кластеров, расположенных на возможно больших расстояниях друг от друга.
С вычислительной точки зрения можно рассматривать этот метод, как дисперсионный анализ «наоборот». Программа начинает с K случайно выбранных кластеров, а затем изменяет принадлежность объектов к ним, чтобы: (1) - минимизировать изменчивость внутри кластеров, и (2) - максимизировать изменчивость между кластерами. Данный способ аналогичен методу «дисперсионный анализ (ANOVA) наоборот» в том смысле, что критерий значимости в дисперсионном анализе сравнивает межгрупповую изменчивость с внутригрупповой при проверке гипотезы о том, что средние в группах отличаются друг от друга. В кластеризации методом K средних программа перемещает объекты (т. е. наблюдения) из одних групп (кластеров) в другие для того, чтобы получить наиболее значимый результат при проведении дисперсионного анализа (ANOVA).
Обычно, когда результаты кластерного анализа методом K средних получены, можно рассчитать средние для каждого кластера по каждому измерению, чтобы оценить, насколько кластеры различаются друг от друга. В идеале вы должны получить сильно различающиеся средние для большинства, если не для всех измерений, используемых в анализе. Значения F-статистики, полученные для каждого измерения, являются другим индикатором того, насколько хорошо соответствующее измерение дискриминирует кластеры.
2.2.1 Описание алгоритма
Первоначальное распределение объектов по кластерам.
Выбирается число k, и на первом шаге эти точки считаются «центрами» кластеров. Каждому кластеру соответствует один центр.
Выбор начальных центроидов может осуществляться следующим образом:
выбор k-наблюдений для максимизации начального расстояния;
случайный выбор k-наблюдений;
выбор первых k-наблюдений.
В результате каждый объект назначен определенному кластеру.
Итеративный процесс.
Вычисляются центры кластеров, которыми затем и далее считаются покоординатные средние кластеров. Объекты опять перераспределяются.
Процесс вычисления центров и перераспределения объектов продолжается до тех пор, пока не выполнено одно из условий:
кластерные центры стабилизировались, т. е. все наблюдения принадлежат кластеру, которому принадлежали до текущей итерации;
число итераций равно максимальному числу итераций.
Выбор числа кластеров является сложным вопросом. Если нет предположений относительно этого числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и т. д., сравнивая полученные результаты.
2.2.2 Проверка качества кластеризации
После получений результатов кластерного анализа методом k-средних следует проверить правильность кластеризации (т. е. оценить, насколько кластеры отличаются друг от друга). Для этого рассчитываются средние значения для каждого кластера. При хорошей кластеризации должны быть получены сильно отличающиеся средние для всех измерений или хотя бы большей их части.
Достоинства алгоритма k-средних:
простота использования;
быстрота использования;
понятность и прозрачность алгоритма.
Недостатки алгоритма k-средних:
алгоритм слишком чувствителен к выбросам, которые могут искажать среднее. Возможным решением этой проблемы является использование модификации алгоритма - алгоритм k-медианы;
алгоритм может медленно работать на больших базах данных. Возможным решением данной проблемы является использование выборки данных.
2.3 Кластеризация с помощью генетических алгоритмов
Генетический алгоритм (ГА), основанный на генетических процессах биологических организмов: биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора и по принципу «выживает наиболее приспособленный».
Программа также может развивать соответствующим образом закодированные решения, выбирая из них наиболее подходящее. Обычно генетические алгоритмы дают хорошие результаты для задач оптимизации многопараметрических функций. Однако, как и другие методы эволюционных вычислений, они не гарантирует обнаружения глобального решения за полиномиальное время. Генетические алгоритмы не гарантируют и того, что глобальное решение будет найдено, но они хороши для поиска «достаточно хорошего» решения задачи «достаточно быстро».
Генетический алгоритм работает с популяцией - совокупностью особей, которые представляют собой возможные решения данной задачи. Каждая особь оценивается степенью её приспособленности, что соответствует тому, насколько «хорошо» данное решение задачи.
Наиболее приспособленные особи могут скрещиваться и производить потомство. В результате получаются новые особи, сочетающие в себе «хорошие» характеристики, полученные от родителей. Возможность скрещивания менее приспособленных особей меньше, поэтому признаки, которыми они обладали, будут элиминироваться из популяции в процессе эволюции. Из поколения в поколение хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге, популяция будет сходиться к оптимальному решению задачи. Также существует возможность мутации особи, когда часть её характеристик случайным образом изменяется. Благодаря этому можно выйти из состояния локального оптимума, получить новое возможное решение.
2.4 Решение задачи коммивояжера c использованием генетических алгоритмов
Разработано решение задачи коммивояжера (TSP) с помощью генетического алгоритма (ГА). В задаче коммивояжера, цель - найти кратчайшее расстояние между N разными городами. Путь, по которому продавец должен пройти называется туром.
Проверка всех вариантов прохода по N городам будет N!. Для расчета 30 туров по городу придется измерить общее расстояние в 2, 65 X 1032 различных туров. Предполагая около триллиона операций в секунду, это займет 252. 333. 390. 232. 297 лет. Добавление еще одного города вызовет увеличение количества расчетов на 31!. Очевидно, что это решение неприемлемо.
Генетический алгоритм может быть использован, чтобы найти решение за гораздо более короткий срок. Хотя он не может найти лучшее решение, он может стать практически идеальным решением для расчета 100 туров по городу менее чем за минуту. Есть несколько основных шагов в решении задачи коммивояжера помощью генетических алгоритмов.
Во-первых, создать группу из многих случайных туры в так называемой популяции. Этот алгоритм использует жадные вычисления для расчета первоначальной популяции, отдавая предпочтение связи городам, которые находятся близко друг к другу.
Во-вторых, выбрать из 2х лучше (кратчайших) туров родителей в популяции и скомбинировать их, сделать два новых потомка. Надеясь, что эти потомки будут лучше, чем любой из родителей.
С небольшой вероятностью потомки туров мутируют. Это делается, чтобы предотвратить идентичность всех туров в популяции.
Новые потомки туров ребенка заменяют собой длиннейшие туры в популяции. Численность особей в популяции остается неизменной.
Новые туры детей неоднократно создаются до достижения желаемой цели. Генетические алгоритмы имитируют природу и эволюцию с использованием принципов выживания наиболее приспособленных особей.
2 наиболее сложных вопроса, с использованием генетического алгоритма для решения задачи коммивояжера является вопрос кодирования тура и алгоритм кроссовера, который используется, чтобы объединить два тура родителей, для получения потомков тура.
В стандартном генетическом алгоритме, кроссовер обеспечивается случайным выбором позиции в родительской последовательности и обменом частей родителей. В этом примере, точка пересечения - между 3-м и 4-м пунктом списка.
|
Родитель 1 |
FAB | ECGD |
|
|
Родитель 2 |
DEA | CGBF |
|
|
Ребенок 1 |
FAB | CGBF |
|
|
Ребенок 2 |
DEA | ECGD |
Трудность задачи коммивояжера состоит в том, что в каждый город может быть использован в туре только один раз. Если буквы в приведенном выше примере представляют города, туры-потомки, созданные этим кроссовером, будут считаться недействительными. 1-й ребенок едет в город F и B два раза, и никогда не выйдет в города D или E.
Кодирование не может быть просто списком городов в порядке, как они были посещены. Для этого созданы другие методы кодирования. Хотя эти методы не будут создавать недействительные туры, они не принимают во внимание тот факт, что тур «ABCDEFG»такой же, как «GFEDCBA». Чтобы решить эту проблему должным образом кроссовер алгоритма должен быть сложнее.
Мое решение хранит ссылки в обоих направлениях для каждого тура. В приведенном выше примере о турах, новый родитель 1 будет сохранен как:
|
Город |
Первая вершина |
Вторая вершина |
|
|
A |
F |
B |
|
|
B |
A |
E |
|
|
C |
E |
G |
|
|
D |
G |
F |
|
|
E |
B |
C |
|
|
F |
D |
A |
|
|
G |
C |
D |
Кроссовер операции гораздо сложнее, чем сочетание двух строк. Кроссовер будет использовать все ссылки, которые есть в обоих родителях, и место этих связей в обоих детей. Тогда для Потомка 1, выбор ссылки состит в выборе среди Родителя 2, а затем Родителя 1. Для потомка 2, выбор состоит из 2го родителя и родителя 1 с другим набором ссылок. Для любой потомка, есть вероятность того, что ссылка может создать недействительными тур, где вместо одного пути в тур будет создано много разорванных туров. Эти ссылки должны быть отвергнуты. Для заполнения оставшихся недостающих звеньев, города выбираются случайным образом. Так как кроссовер не совершенно случайный, этот кроссовер будем называть жадным.
В конце концов, генетический алгоритм сделает так, что все решения будут идентичны. Это не является идеальным решением. Если все особи в генетическом алгоритме станут идентичны, генетический алгоритм не сможет улучшить решение. Есть два способа обойти это. Первый заключается в использовании очень больших начальных размеров популяции, так, что генетическому алгоритму потребуется много времени, чтобы все особи стали идентичны. Второй метод - мутация, когда случайные потомки мутируют, создавая новый уникальный тур.
Этот генетический алгоритм также использует жадные вычисления при расчете первоначальной популяции. Ссылки на города в первоначальном туре не являются полностью случайными. Генетический алгоритм предпочитает делать ссылки между городами, которые близки друг к другу. Это делается на каждом шаге, иначе это сделало бы всех особей идентичными.
Есть 6 параметров для управления работой генетического алгоритма:
Численность населения - численность населения первоначального числа случайных туров, которые создаются, когда алгоритм начинает работу. Большая численность особей требует больше времени, чтобы найти результат. Меньшее население увеличивается вероятность того, что каждый тур в известной степени будет замещать другой и быть идентичным. Это увеличивает вероятность того, что лучшее решение не будет найдено.
Квартал / Группа Размер - Каждое поколение, это количество туров, случайно выбранное из популяции. 2 лучшие туры родителей. Худшем 2 туров получить заменены детей. Для группы размер, высокое число возрастет вероятность того, что действительно хорошие экскурсии будет выбран в качестве родителей, но он также вызывает много гастролирует никогда не будет использоваться в качестве родителей. Большой размер группы приведет алгоритм работает быстрее, но он не может найти самое лучшее решение.
Мутация% - процент, что каждый ребенок после кроссовер будет проходить мутации Когда тур мутировал, один из городов случайно переехал из одной точки в тур на другой.
# Близлежащих городов - В рамках жадные исходной популяции, А. предпочитают ссылка города, которые находятся близко друг к другу, чтобы сделать первоначальный туров. При создании исходной популяции это число городов, которые считаются близкими.
Рядом города Коэффициенты% - это процентная вероятность, что любой из ссылки в случайном тур в исходной популяции предпочтут использовать близлежащие города, а не совершенно случайных города. Если А. выбирает для использования территории города, то есть в равной степени случайность, что это будет какой-либо один из городов по сравнению с предыдущим параметром.
Максимальная поколений - Сколько кроссоверы выполняются до алгоритм завершается.
Другие варианты, которые могут быть настроены являются (примечание: данные доступны только в загружаемой версии) :
Случайное начальное - Это семена для генератора случайных чисел. Имея фиксированные, а не случайных зерно, то вы можете повторить предыдущие результаты тех пор, пока все остальные параметры те же. Это очень полезно при поиске ошибок в алгоритме.
Город List - загружаемая версия позволяет импортировать списки из города XML файлов. Опять же, при отладке проблем, полезно иметь возможность запускать алгоритм с той же точных параметров.
Начальные значения параметра:
|
Параметр |
Начальное значение |
|
|
Размер популяции |
10, 000 |
|
|
Размер группы |
5 |
|
|
Мутации |
3% |
|
|
Количество соседних вершин |
5 |
|
|
Коэффициенты соседних городов |
90% |
Примечание: Я написал эту программу в 1995 году в прямом C. Туры в популяции были сохранены в массиве в 32 бит Int, где каждый бит указывает на связь. Ex: Если тур [0] = 00000000000001000000010000000000 в двоичном, а затем город 0 подключен к городской 11 и 19. Эта реализация была гораздо быстрее, чем текущий C# версии. Жадную часть - кроссовер может быть выполнен на практике бинарных и на 2 туров. Хотя этот код работает очень быстро, у него много бинарных операций.
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 и вернуться в точку сбора. Расстояния между магазинами известны. В каком порядке следует обходить магазины в течение рейда, чтобы замкнутый путь (тур) участников был кратчайшим?
Магазины перенумерованы числами jТ= (1, 2, 3.. n). Тур участника может быть описан циклической перестановкой t= (j1, j2,.., jn, j1), причём все j1.. jn - разные номера; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Расстояния между парами вершин Сij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал
(1)
Во-первых, в постановке Сij означали расстояния, поэтому они должны быть неотрицательными, т. е. для всех jТ:
Сij0; Cjj=? (2)
(последнее равенство означает запрет на петли в туре), симметричными, т. е. для всех i, j:
Сij= Сji. (3)
и удовлетворять неравенству треугольника, т. е. для всех:
Сij+ СjkCik (4)
В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2) - (4) не удовлетворяют. Особенно часто нарушается условие (3). Поэтому мы будем различать два варианта ЗК: симметричную задачу, когда условие (3) выполнено, и несимметричную - в противном случае. Условия (2) - (4) по умолчанию мы будем считать выполненными.
Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры t= (j1, j2,.., jn, j1) и t'= (j1, jn,.., j2, j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.
Зафиксируем на первом и последнем месте в циклической перестановке номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т. к. каждый засчитан два раза: как t и как t'.
Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i, j) проведено, если Сij=0 и не проведено, если Сij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).
В терминах теории графов симметричную ЗК можно сформулировать так:
Дана полная сеть с n вершинами, длина ребра (i, j) = Сij. Найти гамильтонов цикл минимальной длины.
В несимметричной ЗК вместо «цикл» надо говорить «контур», а вместо «ребра» - «дуги» или «стрелки».
Некоторые прикладные задачи формулируются как ЗК, но в них нужно минимизировать длину не гамильтонова цикла, а гамильтоновой цепи. Такие задачи называются незамкнутыми. Некоторые модели сводятся к задаче о нескольких коммивояжерах, но мы здесь их рассматривать не будем.
Итак, для решения этой задачи необходимо составить для каждой группы матрицу расстояний, размерностью n*n, где n - число посещаемых магазинов.
Диалоговое окно GH выглядит следующим образом. Оно похоже на надстройку поиск решений Exsel - так же выбирается целевая функция, подбираемые параметры (в GH - хромосомы) и ограничения. Типы хромосом в нашем случае - перечисляемые и уникальные - поскольку в 1 магазин мы можем зайти 1 раз за рейд.
Результаты решения задачи коммивояжера:
Удобнее всего пройти следующим образом:
|
магазин |
Расстояние |
X |
Y |
||
|
9 |
12 |
0, 000164537 |
52, 941291 |
36, 0495329 |
|
|
7 |
16 |
0, 035143166 |
52, 941127 |
36, 0495329 |
|
|
4 |
19 |
0, 003595822 |
52, 925719 |
36, 0179472 |
|
|
6 |
17 |
0, 021212348 |
52, 929289 |
36, 017518 |
|
|
1 |
22 |
0, 017418649 |
52, 947761 |
36, 0279465 |
|
|
5 |
18 |
0, 004258032 |
52, 949438 |
36, 0452843 |
|
|
8 |
14 |
0, 012212259 |
52, 953496 |
36, 0465717 |
|
|
3 |
20 |
0, 02294063 |
52, 950368 |
36, 0583765 |
|
|
2 |
21 |
0, 024728014 |
52, 941291 |
36, 0495329 |
|
|
10 |
начало |
0, 00 |
52, 941205 |
36, 0503464 |
Второй кластер:
|
# |
магазин |
Раcстояние |
X |
Y |
|
|
9 |
начало |
0, 003121177 |
52, 97995 |
36, 053936 |
|
|
1 |
29 |
0, 007659475 |
52, 979654 |
36, 057043 |
|
|
3 |
33 |
0, 006574704 |
52, 986268 |
36, 060905 |
|
|
5 |
35 |
0, 018209236 |
52, 985157 |
36, 067386 |
|
|
2 |
32 |
0, 011545436 |
52, 967197 |
36, 064382 |
|
|
6 |
36 |
0, 009761768 |
52, 969808 |
36, 053135 |
|
|
4 |
34 |
0, 010376991 |
52, 976914 |
Подобные документы
 |