75
правок
Изменения
Нет описания правки
[[Кластеризация#Постановка задачи кластеризации|Формулировка задачи кластеризации]] в общем случае не задаёт условие близости относительно метрики (см. [[Кластеризация#Теорема невозможности Клейнберга|теорему Клейнберга]]); в связи с этим, многие разработанные [[Кластеризация#Методы кластеризации|методы и алгоритмы]] решения задачи кластеризации предполагают применимость конкретной меры близости объектов для анализа рассматриваемой выборки.
Альтернативный подход заключается в задании [[Оценка качества в задаче кластеризации|индекса кластеризации]] как меры близости объектов внутри кластеров и использовании универсального метода для оптимизации этого индекса; '''[[эволюционные алгоритмы]]''' являются одним из семейств таких универсальных методов.
= Описание метода =
Для решения задачи кластеризации (hard clustering) эволюционный алгоритм использует:
Следует заметить, что если алгоритм использует хотя бы одну операцию разбиения, то должна быть включена в рассмотрение какая-нибудь операция слияния, и наоборот. Иначе количество кластеров либо уменьшится до двух, либо возрастёт до $N$.
=== Модификация прототипа ===
Над прототипами (как вещественно, так и бинарно закодированными) можно проводить операции удаления и добавления; также у вещественного прототипа (центроида) можно поменять координаты. Помимо этого, можно получить гибрид эволюционного алгоритма и ''K-Means'', совершая в качестве одной из возможных мутирующих операций шаг алгоритма $k$ средних значений. Аналогично можно внедрить EM-шаг из ''Gaussian mixture'', но для этого нужно при кодировании особи задавать дисперсию распределения при каждом центроиде.== Кроссовер ==В качестве операций кроссовера различными авторами были опробованы:* '''k-точечный кроссовер''' (''k-point crossover'') на целочисленном и вещественном кодировании;* '''однородный кроссовер''' (''uniform crossover'') на древесном бинарном кодированиии;* '''скрещивание кластеров''' - из выбранного кластера первой особи удаляется часть объектов, после чего в него добавляется часть объектов, принадлежащих некоторому кластеру второй особи. Удалённые объекты переназначаются в другие кластеры первой особи. На всех стадиях этой операции, требующих выбор объектов или кластеров, можно использовать как выборочную (''guided''), так и полностью случайную (''unguided'') стратегии, аналогично описанию мутаций разбиения и слияния.== Инициализация ==Задание особей первого поколения алгоритма может производиться с помощью различных эвристик:* '''случайная инициализация''' - объекты назначаются в кластеры полностью случайным образом. Качество у полученной особи наихудшее, но можно использовать этот способ для тестирования.* '''случайный выбор прототипов''' - прототипы бинарно закодированной особи задаются случайно.* '''пространственная инициализация''' - например, объекты назначаются в кластеры на основе их координаты вдоль случайной оси.* '''запуск другого алгоритма кластеризации''' - особь можно инициализировать с помощью ''K-Means'', [Иерархическая кластеризация|иерархической кластеризации] и проч.== Виды алгоритмов ==Различными авторами были опробованы для кластеризации такие алгоритмы как Roulette wheel selection, $(\mu + \lambda)$, алгоритм многокритериальной оптимизации PESA-II, ...
