Эволюционные алгоритмы кластеризации — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
[[Кластеризация#Постановка задачи кластеризации|Формулировка задачи кластеризации]] в общем случае не задаёт условие близости относительно метрики (см. [[Кластеризация#Теорема невозможности Клейнберга|теорему Клейнберга]]); в связи с этим, многие разработанные [[Кластеризация#Методы кластеризации|методы и алгоритмы]] решения задачи кластеризации предполагают применимость конкретной меры близости объектов для анализа рассматриваемой выборки.  
 
[[Кластеризация#Постановка задачи кластеризации|Формулировка задачи кластеризации]] в общем случае не задаёт условие близости относительно метрики (см. [[Кластеризация#Теорема невозможности Клейнберга|теорему Клейнберга]]); в связи с этим, многие разработанные [[Кластеризация#Методы кластеризации|методы и алгоритмы]] решения задачи кластеризации предполагают применимость конкретной меры близости объектов для анализа рассматриваемой выборки.  
 
Альтернативный подход заключается в задании [[Оценка качества в задаче кластеризации|индекса кластеризации]] как меры близости объектов внутри кластеров и использовании универсального метода для оптимизации этого индекса; '''[[эволюционные алгоритмы]]''' являются одним из семейств таких универсальных методов.
 
Альтернативный подход заключается в задании [[Оценка качества в задаче кластеризации|индекса кластеризации]] как меры близости объектов внутри кластеров и использовании универсального метода для оптимизации этого индекса; '''[[эволюционные алгоритмы]]''' являются одним из семейств таких универсальных методов.
 +
 
= Описание метода =
 
= Описание метода =
 
Для решения задачи кластеризации (hard clustering) эволюционный алгоритм использует:
 
Для решения задачи кластеризации (hard clustering) эволюционный алгоритм использует:
Строка 9: Строка 10:
 
= Параметры эволюционного алгоритма =
 
= Параметры эволюционного алгоритма =
 
Из описания выше следует, что эволюционный алгоритм кластеризации задаётся рядом гиперпараметров - таких как инициализация, применяемые мутации, схема самого алгоритма и т.п. Некоторые исследованные элементы конфигурации эволюционного алгоритма кластеризации приведены ниже.
 
Из описания выше следует, что эволюционный алгоритм кластеризации задаётся рядом гиперпараметров - таких как инициализация, применяемые мутации, схема самого алгоритма и т.п. Некоторые исследованные элементы конфигурации эволюционного алгоритма кластеризации приведены ниже.
 +
== Представление особи ==
 +
Различные мутации, кроссоверы и способы инициализации особи предполагают некоторое её представление в памяти. Например:
 +
* '''целочисленное кодирование по меткам кластеров''' (''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$ истинное соответвует рёбрам остовного дерева, разделяющим кластеры.
 +
== Мутации ==

Версия 02:08, 8 апреля 2019

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

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

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

Мутации