Эволюционные алгоритмы кластеризации

Формулировка задачи кластеризации в общем случае не задаёт условие близости относительно метрики (см. теорему Клейнберга); в связи с этим, многие разработанные методы и алгоритмы решения задачи кластеризации предполагают применимость конкретной меры близости объектов для анализа рассматриваемой выборки. Альтернативный подход заключается в задании индекса кластеризации как меры близости объектов внутри кластеров и использовании универсального метода для оптимизации этого индекса; эволюционные алгоритмы являются одним из семейств таких универсальных методов.

Описание метода

Для решения задачи кластеризации (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$ истинное соответвует рёбрам остовного дерева, разделяющим кластеры.