75
правок
Изменения
Нет описания правки
[[Кластеризация#Постановка задачи кластеризации|Формулировка задачи кластеризации]] в общем случае не задаёт условие близости относительно метрики (см. [[Кластеризация#Теорема невозможности Клейнберга|теорему Клейнберга]]); в связи с этим, многие разработанные [[Кластеризация#Методы кластеризации|методы и алгоритмы]] решения задачи кластеризации предполагают применимость конкретной меры близости объектов для анализа рассматриваемой выборки.
Альтернативный подход заключается в задании [[Оценка качества в задаче кластеризации|индекса кластеризации]] как меры близости объектов внутри кластеров и использовании универсального метода для оптимизации этого индекса; '''[[эволюционные алгоритмы]]''' являются одним из семейств таких универсальных методов.
= Описание метода =
Для решения задачи кластеризации (hard clustering) эволюционный алгоритм использует:
= Параметры эволюционного алгоритма =
Из описания выше следует, что эволюционный алгоритм кластеризации задаётся рядом гиперпараметров - таких как инициализация, применяемые мутации, схема самого алгоритма и т.п. Некоторые исследованные элементы конфигурации эволюционного алгоритма кластеризации приведены ниже.
== Представление особи ==
Различные мутации, кроссоверы и способы инициализации особи предполагают некоторое её представление в памяти. Например:
* '''целочисленное кодирование по меткам кластеров''' (''label-based integer encoding'') - для каждого объекта в выборке его кластер задаётся непосредственно. Таким образом, вся особь - это массив из $N$ чисел, соответствующих кластерам элементов выборки размера $N$.
* '''решётчатое кодирование''' - для каждого вещественного признака (''feature'') объектов одного кластера задаются верхняя и нижняя граница. Таким образом, область одного кластера $f$-мерной выборки ограничивается $f$-мерным гиперкубом.
* '''вещественное кодирование''' (''real encoding'') - для каждого кластера $f$-мерной выборки задаётся его ''центроид'' - синтезированный объект, определяемый его координатами в пространстве выборки. Принадлежность объекта к кластеру определяется центроидом, который ближе всего к объекту согласно используемой метрике. Вся особь определяется вещественным вектором размера $k \cdot f$.
* '''бинарное кодирование''' (''binary encoding'') - то же самое, что и вещественное кодирование, но в качестве центроида используется элемент выборки (''прототип''). Таким образом, одна особь может быть представлена вектором из $N$ булевых значений, из которых $k$ истинных определяют прототипы соответствующих $k$ кластеров.
* '''древесное бинарное кодирование''' ('''tree-based binary encoding''') - по выборке строится [[Остовные деревья: определения, лемма о безопасном ребре|минимальное остовное дерево]]; особь кодируется вектором из $N-1$ булевых значений, среди которых $k-1$ истинное соответвует рёбрам остовного дерева, разделяющим кластеры.
== Мутации ==
