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

• выбор 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 10³² различных туров. Предполагая около триллиона операций в секунду, это займет 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 туров. Хотя этот код работает очень быстро, у него много бинарных операций. ⁶