Система автоматического выбора и оценки алгоритмов кластеризации и их параметров тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Муравьёв Сергей Борисович

• Муравьёв Сергей Борисович
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Муравьёв Сергей Борисович

Реферат

Synopsis

Введение

Глава 1. Обзор предметной области

1.1 Постановка задачи кластеризаци

1.2 Существующие меры качества

1.3 Существующие алгоритмы кластеризации

1.4 Эволюционные алгоритмы

1.4.1 Общие понятия

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

1.5 Мета-обучение

1.5.1 Общие принципы мета-обучения

1.5.2 Общий подход мета-обучения для задач машинного обучения

1.5.3 Мета-обучение для задач кластеризации

1.6 Общие понятия задачи оптимизации гиперпараметров

1.6.1 Базовые понятия

1.6.2 Алгоритмы оптимизации гиперпараметров

1.6.3 Задача автоматического выбора модели и ее гиперпараметров

1.7 Задача о многоруком бандите и алгоритмы её решения

1.8 Задачи, решаемые в диссертационном исследовании

Выводы по главе

Глава 2. Выбор меры качества для задач кластеризации

2.1 Методологии исследования мер качества кластеризации

2.2 Оценка качества кластеризации на основе визуального восприятия асессорами

2.2.1 Обшие понятия

2.2.2 Процедура оценивания разбиений

2.3 Оценка качества работы существующих мер с точки зрения критериев визуального восприятия

2.3.1 Критерии оцеки мер качества

2.3.2 Выбор лучшей меры качества

2.4 Подход к автоматизации оценки качества разбиений

2.4.1 Построение мета-классификатора

2.4.2 Извлечение мета-признаков

2.4.3 Результаты работы мета-классификаторов

Выводы по главе

Глава 3. Метод выбора и настройки гиперпараметров эвристического алгоритма кластеризации на основе обучения с подкреплением

3.1 Метод автоматического выбора и настройки

3.1.1 Стратегия разделения времени

3.1.2 Предлагаемый метод на основе обучения с подкреплением

3.1.3 Процесс настройки гиперпараметров на базе алгоритма SMAC

3.2 Решения задачи о многоруком бандите

3.2.1 Группа классических алгоритмов

3.2.2 Методы, основанные на внутреннем устройстве алгоритма SMAC

3.2.3 Смешанные методы

3.3 Экспериментальное исследование предложенных методов

3.3.1 Аппаратное обеспечение вычислительных машин для экспериментов

3.3.2 Построение набора данных наборов данныхMD-97

3.3.3 Экспериментальные исследования вспомогательных компонентов

3.3.4 Основные эксперименты

3.3.5 Статистическая значимость полученных результатов

Выводы по главе

Глава 4. Эволюционный алгоритм кластеризации с параметрами,

настраиваемыми на основе принципа мета-обучения

4.1 Инкрементальное вычисление внутренних мер качества

4.1.1 Инкреметальный апроксимирующий пересчёт меры Calinski-Harabasz

4.1.2 Инкреметальный апроксимирующий пересчёт меры COP

4.1.3 Инкрементальный точный пересчёт меры Silhouette

4.1.4 Инкрементальный апроксимирующий пересчёт меры Davies-Bouldin

4.1.5 Инкрементальный апроксимирующий перечсёт модифицированной меры Davies-Bouldin

4.1.6 Инкрементальный точный пересчёт меры Dunn

4.1.7 Инкрементальный апроксимирующие пересчёт меры C Index

4.1.8 Инкрементальный апроксимирующий пересчёт меры CS

4.1.9 Инкрементальный апроксимирующий пересчёт меры Sym-Index

4.1.10 Инкрементальный апроксимирующий пересчёт меры SymDB

4.1.11 Инкрементальный апроксимирующий пересчёт меры SV

4.1.12 Инкрементальный апроксимирующий пересчёт меры OS

4.1.13 Инкрементальный апроксимирующий пересчёт меры S_Dbw

4.1.14 Инкрементальный апроксимирующий пересчёт мер gD41, gD51, gD33, gD43, gD53 и точный пересчёт меры gD31

4.2 Разработанные мутации для эволюционных алгоритмов кластеризации

4.2.1 Меры значимости в кластеро-ориентированных преобразованиях

4.2.2 Кластеро-ориентированные преобразования: разбиение, слияние, удаление, перемещение

4.2.3 Преобразование на основе центроидов и прототипов

4.2.4 Преобразование на остовном дереве выборки

4.2.5 Другие преобразования

4.3 Анализ используемых эволюционных алгоритмов кластеризации

4.3.1 Выбор схемы эволюционного алгоритма

4.3.2 Схема эволюционного алгоритма (1 + 1)

4.3.3 Операция мутация эволюционного алгоритма

4.4 Настройка эволюционного алгоритма кластеризации при помощи мета-обучения

4.4.1 Извлечение мета-признаков

4.4.2 Оценка целевого значения гиперпараметра

4.4.3 Обучение мета-классификатора

4.4.4 Описание алгоритма

4.4.5 Основные эксперименты

4.4.6 Анализ эффективности предлагаемой автоматизации

4.5 Сравнение с алгоритмом автоматического выбора и настройки алгоритма кластеризации при помощи обучения с подкрепеле-

нием

Выводы по главе

Глава 5. Описание программного комплекса

5.1 Состав комплекса программ

5.2 Структура проекта

5.2.1 Пакет ^¡Р^Шог

5.2.2 Пакет RLClustering

5.2.3 Пакет EvoClustering

5.3 Руководство пользователя

5.4 Внедрение программного комплекса в Statanly Technologies

5.5 Внедрение программного комплекса в рамках проекта государственного задания № 2.8866.2017/8

Выводы по главе

Заключение

Список литературы

Список иллюстраций

Список таблиц

Приложение А. Полученные графики для алгоритма выбора и настройки гиперпараметров эвристического алгоритма кластеризации

Приложение Б. Таблицы с результатами для алгоритма выбора и настройки гиперпараметров эвристического алгоритма кластеризации

Приложение В. Графики с результатами для эволюционного алгоритма кластеризации с настраиваемыми мутациями

Приложение Г. Таблицы с результатами для эволюционного алгоритма кластеризации с настраиваемыми мутациями

Публикации

Реферат

Введение диссертации (часть автореферата) на тему «Система автоматического выбора и оценки алгоритмов кластеризации и их параметров»

Общая характеристика работы

Актуальность темы. Кластеризация является классической и крайне востребованной задачей машинного обучения. Вместе с тем, математически корректного определения данной задачи не было сформулировано научным сооб-ществом1. Неформально её можно определить как поиск разбиения множества некоторых объектов на подмножества так, чтобы похожие объекты попали в одно и то же подмножество. Задача кластеризации возникает во многих жизненных областях, среди которых биология, психология, обработка изображений, распознавание образов, компьютерная безопасность.

Недостаток информации о производительности работы того или иного алгоритма машинного обучения ведёт к увеличению роли специалистов в данной области. В реальной жизни задача выбора и настройки алгоритма машинного обучения является экспертной. Однако такая работа слишком затратна по времени, поскольку выполняется человеком фактически вручную, а следовательно, неэффективна. Это обсуславливает актуальность разработки методологического, алгоритмического и программного инструментария для автоматизации поиска или синтеза решений для задач машинного обучения.

Одним из ключевых аспектов в автоматических системах задач является критерий качества, по которому сравниваются возможные решения. В связи с тем, что математически корректного определения у задачи кластеризации нет, универсальной численной меры оценки задачи кластеризации также не существует. Вместо этого предложено множество разных вариантов для оценки качества разбиений, которые можно объединить в два подхода: внешние и внутренние. Внешние меры используют сторонние данные о решаемой задаче, например, разметку набора данных, описывающих задачу, на классы. В общем случае такие меры не применимы, поскольку для новых данных такая разметка отсутствует. Однако в зависимости от требований решаемой задачи для построения универсальных кластеризационных моделей такие меры могут быть применимы. Внутренние меры ориентируются исключительно на структуры разбиений без использования внешних данных. На сегодняшний день разработано около 30 таких мер, однако среди них не выявлено универсальной. В совокупности это приводит к тому, что для разработки автоматических систем для решения задачи кластеризации необходимо определить, какие меры следует использовать как критерий качества.

lHennig, C. What are the true clusters? // Pattern Recognition Letters. 2015. Vol. 64. P. 53-62.

Также было предложено большое число подходов к решению задачи кластеризации. Можно выделить два подхода. Первый заключается в том, что производится процесс оптимизации некоторых функционалов, которые обычно не являются конечными мерами качества разбиений. Данный подход реализуют алгоритмы кластеризации, такие как k-Means, иерархический алгоритм и DBSCAN. Для удобства будем далее называть такие методы «эвристическими алгоритмами кластеризации», поскольку все они основаны на некотором эвристическом предположении. В рамках другого подхода производится обход пространства возможных разбиений с целью поиска наилучшего по задаваемой мере качества. Данный подход реализуют эволюционные алгоритмы кластеризации. Рассматриваемые алгоритмы обладают параметрами, такими как операторы мутации и скрещивания, и выбор этих параметров также является актуальной задачей.

Исходя из изложенного выше, автоматизация процесса выбора меры оценки, а также выбора и настройки алгоритма, решающего задачу кластеризации, является актуальной задачей.

Степень разработанности темы.

Важным аспектом системы автоматического выбора и настройки алгоритма для решения задачи кластеризации является мера оценки качества её решения. На сегодняшний одним из подходов к оценке результатов в области исследования задач кластеризации производится внешними мерами, которые используют сторонние данные о решаемой задаче. Такой подход не универсален, поскольку предсказать поведение алгоритмов применительно к новой задаче при отсутствии какой-либо сторонней информации о ней представляется невозможным. Olatz Arbelaitz2 произвёл обзор большинства из существующих внутренних мер оценки разбиений. Были проведены сравнения на различных данных, однако лучшей меры выявлено не было.

На сегодняшний день была опубликована только одна работа Daniel Gomes Ferrari3, описывающая метод автоматизации выбора эвристических алгоритмов кластеризации на основе принципа мета-обучения. Основная идея мета-обучения состоит в сведении задачи выбора алгоритма к задаче обучения с учителем: задачи описываются мета-признаками, характеризующими свойства решаемой задачи, а агрегированные сведения о работе алгоритмов (лучший алгоритм, ранжирование над алгоритмами и т.д.) выступают целевой функцией. D. G. Ferrari предложил метод автоматического выбора эвристического алгоритма кластеризации при помощи мета-обучения. Было предложено мета-признаковое описание задач кластеризации, а также произведено ранжирование результатов при помощи нескольких внутренних мер оценки разбиений. Произведено также сравнение с заранее известными разбиениями для используемых в работе задач.

2Arbelaitz, O., Gurrutxaga, I., Muguerza, J., PeRez, J. M., Perona, I. An extensive comparative study of cluster validity indices // Pattern Recognition. 2013. Vol. 46, no. 1. P. 243-256.

3Ferrari, D. G., De Castro, L. N. Clustering algorithm selection by meta-learning systems: A new distance-based problem characterization and ranking combination methods // Information Sciences. 2015. Vol. 301. P. 181-194.

Предложенный в этой работе метод производит выбор из фиксированного числа моделей, не позволяет их настраивать их гиперпараметры, а следовательно, не может применяться на практике.

Eduardo Raul Hruschka4 произвёл обзор существующих эволюционных алгоритмов кластеризации, однако никаких рекомендаций касательно выбора того или иного алгоритма в работе не приводится.

Целью данной работы является повышение качества решения задачи кластеризации при условии заданных ограничений на время его поиска.

Для достижения указанной цели определены следующие задачи исследования:

а) Разработать подход к автоматизации оценки качества разбиений на основе их визуального восприятия, базирующийся на принципе мета-обучения.

б) Разработать метод выбора и настройки гиперпараметров эвристического алгоритма кластеризации по заранее выбранной мере качества, основанный на принципах обучения с подкреплением.

в) Разработать эволюционный алгоритм кластеризации с параметрами, настраиваемыми на основе принципа мета-обучения по заранее выбранной мере качества.

г) Разработать программный комплекс, реализующий эволюционный алгоритм и алгоритмы на базе подхода и метода, изложенных выше, и позволяющий осуществлять построение оптимального разбиения для заданной задачи по выбранной мере качества.

д) Провести вычислительные эксперименты для оценки работы эволюционного алгоритма и алгоритмов на базе подхода и метода, изложенных выше.

Объект исследования — задача кластеризации.

Предмет исследования — автоматизация выбора и настройки алгоритмов поиска решения задачи кластеризации.

Основные положения, выносимые на защиту:

а) Подход к автоматизации оценки качества разбиений на основе их визуального восприятия, базирующийся на принципе мета-обучения.

б) Метод выбора и настройки гиперпараметров эвристического алгоритма кластеризации по заранее выбранной мере качества, основанный на принципах обучения с подкреплением.

в) Метод инкрементального пересчёта внутренних мер оценки разбиений, полученных в результате применения эволюционных алгоритмов кластеризации.

4Hruschka, E. R., Campello, R. J., Freitas, A. A., [et al.]. A survey of evolutionary algorithms for clustering // IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews). 2009. Vol. 39, no. 2. P. 133-155.

г) Эволюционный алгоритм кластеризации с параметрами, настраиваемыми на основе принципа мета-обучения по заранее выбранной мере качества.

д) Программный комплекс, реализующий эволюционный алгоритм и алгоритмы на базе подхода и метода, изложенных выше, и позволяющий осуществлять построение оптимального разбиения для заданной задачи кластеризации по выбранной мере качества.

Научная новизна заключается в следующем:

а) Впервые был предложен подход к автоматизации оценки качества разбиений, на основе их визуального восприятия, базирующийся на принципе мета-обучения. Новизна предложенного подхода заключается в разработке методологии визуальной оценки мер на основе визуальной оценке разбиений и сведении задачи предсказания такой оценки для новых наборов данных к задаче классификации в пространстве мета-признаков, описывающих поставленную задачу кластеризации.

б) Впервые был предложен метод выбора и настройки гиперпараметров эвристического алгоритма кластеризации по заранее выбранной мере качества, основанный на принципах обучения с подкреплением. Новизна предложенного метода заключается в том, что в нём используется метод обучения с подкреплением, а именно алгоритм многорукого бандита, который осуществляет поиск компромисса между исследованием и эксплуатацией процессов настройки параметров для различных алгоритмов кластеризации.

в) Впервые был предложен метод ускорения вычисления внутренних мер оценки разбиений, полученных в результате применения эволюционных алгоритмов кластеризации. Показано, что разработанные на базе метода алгоритмы значительно уменьшают время подсчёта мер при изменении структуры разбиения, тем самым оптимизируют вычисления функции приспособленности при эволюционном методе поиска оптимального разбиения.

г) Впервые был предложен эволюционный алгоритм кластеризации с параметрами, настраиваемыми на основе принципа мета-обучения по заранее выбранной мере качества. Новизна предложенного алгоритма заключается в сведении задач выбора мутаций эволюционных стратегий к задаче выбора алгоритма.

Методология и методы исследования. Работа выполнена преимущественно в методологии машинного обучения, в работе используются методы дискретной математики, теория вычислительной сложности, теория оптимизации, в частности, теория эволюционных вычислений, парадигма мета-обучения, методы объединения ранжирований, математической статистики а также методология проведения вычислительных экспериментов для оценки работы алгоритмов.

Достоверность полученных результатов обеспечивается корректным обоснованием постановок задач, точной формулировкой критериев оценки, до-

казательствами оценок, а также подтверждаются результатами вычислительных экспериментов по использованию предложенных в диссертации подхода и методов. Результаты согласуются с результатами, полученными другими авторами.

Теоретическая значимость работы состоит в том, что был предложен метод агрегации асессорских оценок визуального восприятия разбиений, метод оценки качества работы внутренних мер качества кластеризации на основе асес-сорских оценок визуального восприятия. Также был предложен метод сведения асессорских оценок визуального восприятия к внутренним мерам качества задач кластеризации при помощи мета-обучения. Помимо этого, был предложен метод сведения задачи выбора и настройки параметров алгоритма кластеризации к задаче о многоруком бандите. Также были предложены методы инкрементального пересчёта внутренних мер оценки задач кластеризации и метод автоматического выбора и настройки эволюционного алгоритма, решающего задачу кластеризации.

Практическая значимость работы состоит в том, что эволюционный алгоритм и алгоритмы на базе предложенного подхода и метода позволяют ускорять и улучшать решения для различных задач кластеризации, а также определять численную меру качества разбиения на основе визуальных оценок.

Внедрение результатов работы. Результаты работы использовались в учебном процессе факультета информационных технологий и программирования Университета ИТМО при руководстве бакалаврскими работами и магистерскими диссертациями, авторы и названия которых приведены в диссертации. Предложенный подход к выбору меры качества использовался в компании Statanly Technologies (г. Санкт-Петербург) для разработки алгоритма поиска документов ограниченного размера в базе по их описанию на языке спецификаций информационного пространства. А именно, был использован алгоритм на основе подхода к выбору меры качества разбиения при помощи мета-обучения, представленный в диссертационном исследовании, для оценки кластеризации векторных представлений слов (эмбеддингов) с целью эффективного построения обратного индекса на каждом из полученных кластеров, по которому, в свою очередь осуществляется поиск документов. Также алгоритмы на базе предложенных методов выбора и настройки алгоритмов кластеризации были использованы для построения системы автоматического решения задач машинного обучения, являющейся собственной разработкой компании Statanly Technologies. Помимо этого, в рамках проекта государственного задания №2.8866.2017/8.9 «Технология разработки программного обеспечения систем управления ответственными объектами на основе глубокого обучения и конечных автоматов», выполняемого в рамках базовой части государственного задания, использовался алгоритм на базе метода выбора и настройки гиперпараметров эвристического алгоритма кластеризации, основанный на принципах обучения с подкреплением, для синтеза состояний детерминированного конечного автомата на основе состояний глубокой рекуррентной сети, имитирующей работу этого автомата.

Апробация результатов работы. Основные результаты работы докладывались на следующих конференциях и семинарах:

а) XVIII Международная конференция по мягким вычислениям (SCM'2015). 2015, Санкт-Петербург.

б) Научная и учебно-методическая конференция Университета ИТМО.

2016 г., Университет ИТМО, Санкт-Петербург.

в) Научная и учебно-методическая конференция Университета ИТМО.

2017 г., Университет ИТМО, Санкт-Петербург.

г) Научная и учебно-методическая конференция Университета ИТМО.

2018 г., Университет ИТМО, Санкт-Петербург.

д) Научная и учебно-методическая конференция Университета ИТМО.

2019 г., Университет ИТМО, Санкт-Петербург.

е) Всероссийский VII Конгресс молодых ученых. 2018, Санкт-Петербург.

ж) European Conference on Data Analysis (ECDA'2018). 2018, Падерборн, Германия.

и) European Conference on Machine Learning and Principles and Practice of Knowledge Discovery inDatabases (ECML PKDD 2019). 2019, Вюрцбург, Германия.

Личный вклад автора. Идея и формализация подхода к автоматизации оценки качества разбиений на основе визуального восприятия при помощи мета-обучения принадлежит совместно автору диссертации и А.А. Фильченкову, реализация алгоритма на базе предложенного подхода принадлежит лично автору диссертации. Идея метода выбора и настройки параметров алгоритма кластеризации для заданной задачи по заранее выбранной мере, основанный на принципах обучения с подкреплением принадлежит совместно автору диссертации и А.А. Фильченкову, формализация данного метода принадлежит лично автору диссертации, реализация алгоритма на базе предложенного метода и проведение вычислительных экспериментов принадлежит совместно автору диссертации и В.В. Шаламову. Идея методов инкрементального пересчёта мер принадлежит совместно автору диссертации и А.А. Фильченкову, формализация данных методов принадлежит лично автору диссертации. Реализация и проведение вычислительных экспериментов алгоритмов инкрементального пересчёта внутренних мер оценки принадлежат совместно автору диссертации и С.В. Кочковой. Идея метода выбора и настройки эволюционных алгоритмов кластеризации и их параметров принадлежит совместно автору диссертации и А.А. Фильченкову. Формализация данного метода принадлежит лично автору диссертации. Реализация алгоритма на базе предложенного метода и проведение вычислительных экспериментов принадлежат совместно автору диссертации и Д.С. Томпу.

Публикации. Основные результаты по теме диссертации изложены в десяти публикациях, из них пять опубликованы в изданиях, индексируемых в базе цитирования Scopus, одна публикация издана в журнале, рекомендованном ВАК.

Содержание работы

Во введении обосновывается актуальность исследований, проводимых в рамках данной диссертационной работы, приводится обзор научной литературы по изучаемой проблеме, формулируется цель, ставятся задачи работы, излагается научная новизна и практическая значимость представляемой работы.

Первая глава посвящена обзору предметной области и результатов существующих исследований автоматизации решения задачи кластеризации. Кроме того, в первой главе приведена терминология и изложены известные результаты ряда разделов информатики, которые необходимы для описания предлагаемых в диссертации методов и алгоритмов.

В разделе 1.1 приведено определение задачи кластеризации, а также области её применения. Пусть X - совокупность объектов, а Y - множество возможных разбиений этих объектов на непересекающиеся множества, которые связаны некоторой неизвестной зависимостью f. Задача кластеризации заключается в том, чтобы восстановить эту зависимость таким образом, чтобы объекты одного кластера лежали максимально близко друг к другу по некоторой заданной мере расстояния р, а сами кластеры были максимально удалены друг от друга.

В разделе 1.2 приведено описание используемых в работе внутренних мер качества разбиений, полученных в результате применения алгоритмов кластеризации.

В разделе 1.3 приведено описание работы существующих алгоритмов кластеризации, используемых в работе, и их гиперпараметры. Гиперпараметры -параметры, значения которых задаются до начала обучения, не изменяются в процессе обучения и не зависят от заданного набора данных. В контексте задачи кластеризации под обучением стоит понимать процесс подбора значений параметров для того или иного алгоритма кластеризации для заданного набора данных. Будем оперировать строгим понятием алгоритм и гиперпараметр, однако в литературе и на практике границы применимости этих терминов размыты, указав однако, что в частности в данной работе используются алгоритмы и гиперпараметры из библиотеки scikit-learn5.

В разделе 1.4 приведено описание принципа работы эволюционных алгоритмов в целом и эволюционных алгоритмов кластеризации в частности. Также в данном разделе приводится краткий обзор существующих идей, которые легли в основу создания мутаций для эволюционных алгоритмов кластеризации, которые были реализованы в данной работе.

В разделе 1.5 описан общий принцип мета-обучения, позволяющий в частности решить задачу выбора внутренней меры оценки разбиения, полученного

5Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Pret-tenhofer, P., Weiss, R., Dubourg, V, Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, E. Scikit-learn: Machine Learning in Python // Journal of Machine Learning Research. 2011. Vol. 12. P. 2825-2830.

в результате применения алгоритма кластеризации, за счет сведения ее к задаче обучения с учителем.

В литературе термин мета-обучение, в основном, используется в двух смыслах: в широком и узком. В широком смысле под мета-обучением понимается набор подходов, методов и техник, направленных на перенос знаний о решении одних задач на ускорение поиска решения других задач. Мы будем пользовать узким определением.

Мета-обучение - подход для решения задачи выбора алгоритмов, в которой алгоритмы машинного обучения применяются к мета-данным о работа алгоритмов машинного обучения на разных задачах6. Мета-признак описывает свойство задачи, например, разрежен ли набор данных, какое число категориальных или вещественнозначных признаков объектов содержится в наборе данных, число возможных меток, размер набора данных и многое другое. В такой постановке объектами выступают наборы данных наборов данных.

В разделе 1.6 описаны общие понятия задачи оптимизации гиперпараметров. В частности, приведена формализация задачи автоматического выбора модели алгоритма кластеризации и её гиперпараметров. Сначала формально определим задачу. Моделью А будем называть алгоритм машинного обучения. Каждая модель ассоциируется с некоторым набором гиперпараметров Л = {А1,А2 ,...,А„}е Л. Для разных моделей алгоритмов задаются различные пространства Л. Модель с выбранными значениями гиперпараметров Л будем обозначать Ал.

Пусть задана некоторая мера качества Q. Задача оптимизации гиперпараметров заключается в подборе таких Л* € Л, при которых заданная модель алгоритма А достигнет наилучшего качества на наборе объектов X: Q(AЛ, X). Для удобства будем считать, что оптимум по мере будет достигаться при минимальных значениях из её области определения. Таким образом задачу оптимизации гиперпараметров можно записать в следующем:

Л* £ эд^ттQ(AЛ,Х). лел

В разделе приводятся различные алгоритмы оптимизации гиперпараметров, в частности рассматривается алгоритм SMAC1, использующийся в работе.

Применительно к задаче кластеризации стоит отметить, что даже один и тот же алгоритм с разными гиперпараметрами по-разному разбивает на кластеры множество объектов, что, следовательно, дает разные оценки качества кластеризации. Соответственно, возникает задача выбора модели алгоритма кластеризации и оптимизации гиперпараметров выбранной модели.

6Hutter, F., Kotthoff, L., Vanschoren, J. Automated Machine Learning-Methods, Systems, Challenges. 2019.

1Hutter, F., Hoos, H. H., Leyton-Brown, K. Sequential model-based optimization for general algorithm configuration//Learning and Intelligent Optimization. Springer, 2011. P. 507-523.

Задача выбора модели алгоритма и ее гиперпараметров в общем случае формально записывается как поиск модели алгоритма А*х, который бы минимизировал Q : А*х е а^ттАеАХеЛ Q(Ajx,D), где А = {А1,А2,...,Ак} — набор моделей алгоритмов, с каждой из которых связано пространство гиперпараметров Л1, Л2,..., Лк соответственно.

В разделе также приводятся существующие на сегодняшний день решения задачи автоматического выбора модели и ее гиперпараметров Auto-WEKAi, TPOT9 и Auto-SЫeamw.

В разделе 1.7 описывается задача многорукого бандита, а также классические алгоритмы Softmax и UCB-1, решающие эту задачу.

В разделе 1.8 на основе результатов обзора формулируются задачи, решаемые в настоящей диссертации.

Вторая глава посвящена исследованию проблемы выбора меры качества для задач кластеризации. В данной главе приводится описание критериев оценки визуального восприятия разбиений, а также описывается метод оценки мер качества на основе сформированных критериев. Также в данной главе приведено описание подхода к автоматизации оценки качества разбиений на основе визуального восприятия пользователей, базирующийся на принципе мета-обучения.

В разделе 2.1 рассматриваются методологии, которые применяются исследователями, предлагающими новые меры оценки алгоритмов кластеризации. На сегодняшний день существует четыре основных методологии:

а) Сравнение результатов с заранее известными разбиениями наборов данных, наиболее часто применяющаяся техника.

б) Полностью теоретическое исследование меры, основанное на её структурных свойствах.

в) Исследования стабильности, устойчивости меры и других её характеристик. Данный метод обычно требует изменения данных в том или ином виде (например, subsampling).

г) Сравнение на основе визуальной оценки разбиения.

Стоит отметить, что наборы данных, используемые в ходе применения первой методологии, обычно имеют единственное очевидное разбиение. Таким образом, применение первой методологии обычно влечёт за собой применение четвёртой из вышеприведённого списка. Исследование теоретических свойств на текущий момент не является автоматизируемым. Исследование стабильности и других характеристик, применяемое в рамках методологии второго пункта из

8Kotthoff, L., Thornton, C., Hoos, H. H., Hutter, F., Leyton-Brown, K. Auto-WEKA 2.0: Automatic model selection and hyperparameter optimization in WEKA // The Journal of Machine Learning Research. 2017. Vol. 18, no. 1. P. 826-830.

9Olson, R. S., Bartley, N., Urbanowicz, R. J., Moore, J. H. Evaluation of a Tree-based Pipeline Optimization Tool for Automating Data Science // Proceedings of the Genetic and Evolutionary Computation Conference 2016. Denver, Colorado, USA : ACM, 2016. P. 485-492. (GECCO '16).

10Feurer, M., Klein, A., Eggensperger, K., Springenberg, J., Blum, M., Hutter, F. Efficient and robust automated machine learning // Advances in Neural Information Processing Systems. 2015. P. 2962-2970.

списка выше, основано на предположении о том, что конечное разбиение должно быть устойчивым к любым изменениям исследуемого набора данных. Однако подобное ограничение не может быть рассмотрено в качестве универсального критерия. Кластеризация является довольно естественным с точки зрения человеческого мозга процессом, который протекает всё время в ходе нашей жизни11. На основе вышеперечисленного можно заключить, что метод оценки разбиений на основе визуального восприятия имеет фундаментальные основания и фактически служит основной для всех универсальных методологий оценки качества мер разбиений.

В данном разделе также приводится предположение о том, что разбиения, полученные в результате применения алгоритмов кластеризации, с точки зрения визуального восприятия можно оценивать как адекватные или неадекватные, а также проводить сравнения разбиений друг с другом для выявления наилучшего. На рисунке Р.1 приведён пример сравнения различных разбиений примитивного набора данных с точки зрения адекватности, а также с точки зрения сравнения разбиений друг с другом. Чем выше на рисунке расположено разбиение, тем оно лучше с точки зрения попарного сравнения с другими разбиениями.

Рисунок Р.1 - Пример возможного сравнения разбиений с точки зрения визуального восприятия.

Список литературы диссертационного исследования кандидат наук Муравьёв Сергей Борисович, 2019 год

Литература

1. Halkidi M., Batistakis Y., Vazirgiannis M. On clustering validation techniques // Journal of Intelligent Information Systems. 2001. V. 17. N 2-3. P. 107-145. doi: 10.1023/a:1012801612483

2. Jain A.K., Murty M.N., Flynn P.J. Data clustering: a review // ACM Computing Surveys. 1999. V. 31. N 3. P. 264-323. doi: 10.1145/331499.331504

3. Mirkin B. Clustering for Data Mining: a Data Recovery Approach. CRC Press, 2005. 296 p. doi: 10.1201/9781420034912

4. Schlee D., Sneath P.H., Sokal R.R., Freman W.H. Numerical taxonomy. The principles and practice of numerical classification // Systematic Zoology. 1975. V. 24. N 2. P. 263-268. doi: 10.2307/2412767

5. Holzinger K.J., Harman H.H. Factor Analysis: A Synthesis of Factorial Methods. Chicago: University of Chicago Press, 1941. 417 p.

6. Chou C.H., Su M.C., Lai E. A new cluster validity measure and its application to image compression // Pattern Analysis and Applications. 2004. V. 7. N 2. P. 205-220. doi: 10.1007/s10044-004-0218-1

7. Luo M., Wang L.N., Zhang H.G. An unsupervised clustering-based intrusion detection method // Acta Electronica Sinica. 2003. V. 31. N 11. P. 1713-1716.

8. Von Luxburg U., Williamson R.C., Guyon I. Clustering: science or art // Proc. ICML Workshop on Unsupervised and Transfer Learning. Bellevue, USA, 2012. V. 27. P. 65-79.

9. Aggarwal C.C., Reddy C.K. Data Clustering: Algorithms and Applications. CRC press, 2013. 674 p. doi: 10.1201/b15410

10. Fraley C., Raftery A.E. How many clusters? Which clustering method? Answers via model-based cluster analysis // The Computer Journal. 1998. V. 41. N 8. P. 578-588. doi: 10.1093/comjnL/41.8.578

11. Hennig C. What are the true clusters? // Pattern Recognition Letters. 2015. V. 64. P. 53-62. doi: 10.1016/j.patrec.2015.04.009

12. Pal N.R., Biswas J. Cluster validation using graph theoretic concepts // Pattern Recognition. 1997. V. 30. N 6. P. 847-857. doi: 10.1016/s0031-3203(96)00127-6

13. Ferrari D.G., De Castro L.N. Clustering algorithm selection by meta-learning systems: A new distance-based problem characterization and ranking combination methods // Information Sciences. 2015. V. 301. P. 181-194. doi: 10.1016/j.ins.2014.12.044

14. Tibshirani R., Walther G., Hastie T. Estimating the number of clusters in a data set via the gap statistic // Journal of the Royal Statistical Society: Series B (Statistical Methodology). 2001. V. 63. N 2. P. 411-423. doi: 10.1111/1467-9868.00293

15. Sugar C.A., James G.M. Finding the number of clusters in a dataset // Journal of the American Statistical Association. 2003. V. 98. N 463. P. 750-763. doi: 10.1198/016214503000000666

16. Pelleg D., Moore A.W. X-means: Extending k-means with efficient estimation of the number of clusters // Proc. 17th Int. Conf. on Machine Learning. Stanford, USA, 2000. Part 1. P. 727734.

17. Thornton C., Hutter F., Hoos H.H., Leyton-Brown K. Auto-WEKA: Combined selection and hyperparameter optimization of classification algorithms // Proc. 19th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining. Chicago, USA, 2012. P. 847-855. doi: 10.1145/2487575.2487629

References

1. Halkidi M., Batistakis Y., Vazirgiannis M. On clustering validation techniques. Journal of Intelligent Information Systems, 2001, vol. 17, no. 2-3, pp. 107-145. doi: 10.1023/a:1012801612483

2. Jain A.K., Murty M.N., Flynn P.J. Data clustering: a review. ACM Computing Surveys, 1999, vol. 31, no. 3, pp. 264-323. doi: 10.1145/331499.331504

3. Mirkin B. Clustering for Data Mining: a Data Recovery Approach. CRC Press, 2005, 296 p. doi: 10.1201/9781420034912

4. Schlee D., Sneath P.H., Sokal R.R., Freman W.H. Numerical taxonomy. The principles and practice of numerical classification. Systematic Zoology, 1975, vol. 24, no. 2, pp. 263-268. doi: 10.2307/2412767

5. HolzingerKJ., HarmanH.H. FactorAnalysis:A Synthesis ofFactorial Methods. Chicago, University of Chicago Press, 1941, 417 p.

6. Chou C.H., Su M.C., Lai E. A new cluster validity measure and its application to image compression. Pattern Analysis and Applications, 2004, vol. 7, no. 2, pp. 205-220. doi: 10.1007/s10044-004-0218-1

7. Luo M., Wang L.N., Zhang H.G. An unsupervised clustering-based intrusion detection method. Acta Electronica Sinica, 2003, vol. 31, no. 11, pp. 1713-1716.

8. Von Luxburg U., Williamson R.C., Guyon I. Clustering: science or art. Proc. ICML Workshop on Unsupervised and Transfer Learning. Bellevue, USA, 2012, vol. 27, pp. 65-79.

9. Aggarwal C.C., Reddy C.K. Data Clustering: Algorithms and Applications. CRC press, 2013, 674 p. doi: 10.1201/b15410

10. Fraley C., Raftery A.E. How many clusters? Which clustering method? Answers via model-based cluster analysis. The Computer Journal, 1998, vol. 41, no. 8, pp. 578-588. doi: 10.1093/comjnl/41.8.578

11. Hennig C. What are the true clusters? Pattern Recognition Letters, 2015, vol. 64, pp. 53-62. doi: 10.1016/j.patrec.2015.04.009

12. Pal N.R., Biswas J. Cluster validation using graph theoretic concepts. Pattern Recognition, 1997, vol. 30, no. 6, pp. 847-857. doi: 10.1016/s0031-3203(96)00127-6

13. Ferrari D.G., De Castro L.N. Clustering algorithm selection by meta-learning systems: A new distance-based problem characterization and ranking combination methods. Information Sciences, 2015, vol. 301, pp. 181-194. doi: 10.1016/j.ins.2014.12.044

14. Tibshirani R., Walther G., Hastie T. Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2001, vol. 63, no. 2, pp. 411-423. doi: 10.1111/1467-9868.00293

15. Sugar C.A., James G.M. Finding the number of clusters in a dataset. Journal of the American Statistical Association, 2003, vol. 98, no. 463, pp. 750-763. doi: 10.1198/016214503000000666

16. Pelleg D., Moore A.W. X-means: Extending k-means with efficient estimation of the number of clusters. Proc. 17thInt. Conf. on Machine Learning. Stanford, USA, 2000, part 1, pp. 727734.

17. Thornton C., Hutter F., Hoos H.H., Leyton-Brown K. Auto-WEKA: Combined selection and hyperparameter optimization of classification algorithms. Proc. 19th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining. Chicago, USA, 2012, pp. 847-855. doi: 10.1145/2487575.2487629

18. Olson R.S., Bartley N., Urbanowicz R.J., Moore J.H. Evaluation of a tree-based pipeline optimization tool for automating data science // Proc. Genetic and Evolutionary Computation Conference. Denver, USA, 2016. P. 485-492. doi: 10.1145/2908812.2908918

19. Feurer M., Klein A., Eggensperger K., Springenberg J., Blum M., Hutter F. Efficient and robust automated machine learning // Advances in Neural Information Processing Systems. 2015. V. 2. P. 2962-2970.

20. Ефимова В.А., Фильченков А.А., Шалыто А.А. Применение обучения с подкреплением для одновременного выбора модели алгоритма классификации и ее структурных параметров // Машинное обучение и анализ данных. 2016. № 2. С. 244-254.

21. Kotthoff L., Thornton C., Hoos H.H., Hutter F., Leyton-Brown K. Auto-WEKA 2.0: Automatic model selection and hyperparameter optimization in WEKA // The Journal of Machine Learning Research. 2017. V. 18. N 1. P. 826-830.

22. Sutton R.S., Barto A.G. Introduction to Reinforcement Learning. Cambridge: MIT press, 1998. 322 p.

23. Hutter F., Hoos H.H., Leyton-Brown K. Sequential model-based optimization for general algorithm configuration // Lecture Notes in Computer Science. 2011. V. 6683. P. 507-523. doi: 10.1007/978-3-642-25566-3_40

24. Arbelaitz O., Gurrutxaga I., Muguerza J., Perez J. M., Perona I. An extensive comparative study of cluster validity indices // Pattern Recognition. 2003. V. 46. N 1. P. 243-256. doi: 10.1016/j.patcog.2012.07.021

25. Filchenkov A., Muravyov S., Parfenov V. Towards cluster validity index evaluation and selection // Proc. IEEE Artificial Intelligence and Natural Language Conference. St. Petersburg, Russia, 2016. P. 1-8.

18. Olson R.S., Bartley N., Urbanowicz R.J., Moore J.H. Evaluation of a tree-based pipeline optimization tool for automating data science. Proc. Genetic and Evolutionary Computation Conference. Denver, USA, 2016, pp. 485-492. doi: 10.1145/2908812.2908918

19. Feurer M., Klein A., Eggensperger K., Springenberg J., Blum M., Hutter F. Efficient and robust automated machine learning. Advances in Neural Information Processing Systems, 2015, vol. 2, pp. 2962-2970.

20. Efimova V.A., Filchenkov A.A., Shalyto A.A. Reinforcement-based simultaneous classification model and its hyperparameters selection. Machine Learning and Data Analysis, 2016, no. 2, pp. 244-254. (in Russian)

21. Kotthoff L., Thornton C., Hoos H.H., Hutter F., Leyton-Brown K. Auto-WEKA 2.0: Automatic model selection and hyperparameter optimization in WEKA. The Journal of Machine Learning Research, 2017, vol. 18, no. 1, pp. 826-830.

22. Sutton R.S., Barto A.G. Introduction to Reinforcement Learning. Cambridge, MIT press, 1998, 322 p.

23. Hutter F., Hoos H.H., Leyton-Brown K. Sequential modelbased optimization for general algorithm configuration. Lecture Notes in Computer Science, 2011, vol. 6683, pp. 507-523. doi: 10.1007/978-3-642-25566-3_40

24. Arbelaitz O., Gurrutxaga I., Muguerza J., Perez J. M., Perona I. An extensive comparative study of cluster validity indices. Pattern Recognition, 2003, vol. 46, no. 1, pp. 243-256. doi: 10.1016/j.patcog.2012.07.021

25. Filchenkov A., Muravyov S., Parfenov V. Towards cluster validity index evaluation and selection. Proc. IEEE Artificial Intelligence and Natural Language Conference. St. Petersburg, Russia, 2016, pp. 1-8.

Авторы

Муравьёв Сергей Борисович — программист, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, Scopus ID: 57194035005, ORCID ID: 0000-0002-4251-1744, [e-mail]

Ефимова Валерия Александровна — программист, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, ORCID ID: 0000-0002-5309-2207, [e-mail]

Шаламов Вячеслав Владимирович — аспирант, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, Scopus ID: 57191077141, ORCID ID: 0000-0002-5647-6521, [e-mail]

Фильченков Андрей Александрович — кандидат физико-математических наук, доцент, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, Scopus ID: 55507568200, ORCID ID: 0000-0002-1133-8432, [e-mail]

Сметанников Иван Борисович — кандидат технических наук, ассистент, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, Scopus ID: 56902520900, ORCID ID: 0000-0003-3376-9468, [e-mail]

Authors

Sergey B. Muravyov — Software engineer, ITMO University, Saint Petersburg, 197101, Russian Federation, Scopus ID: 57194035005, ORCID ID: 0000-0002-4251-1744, [e-mail]

Valeria A. Efimova — Software engineer, ITMO University, Saint Petersburg, 197101, Russian Federation, ORCID ID: 0000-0002-5309-2207, [e-mail]

Vyacheslav V. Shalamov — postgraduate, ITMO University, Saint Petersburg, 197101, Russian Federation, Scopus ID: 57191077141, ORCID ID: 0000-0002-5647-6521, [e-mail]

Andrey A. Filchenkov — PhD, Associate Professor, ITMO University, Saint Petersburg, 197101, Russian Federation, Scopus ID: 55507568200, ORCID ID: 0000-0002-1133-8432, [e-mail]

Ivan B. Smetannikov — PhD, Assistant, ITMO University, Saint Petersburg, 197101, Russian Federation, Scopus ID: 56902520900, ORCID ID: 0000-0003-3376-9468, [e-mail]

ISSN: 2571-3701 (Online), 1803-3814 (Printed) https://doi.Org/10.13164/mendel.2019.l.087 Soft Computing

EFFICIENT COMPUTATION OF FITNESS FUNCTION FOR EVOLUTIONARY CLUSTERING

Sergey Muravyov^, Denis Antipov, Arina Buzdalova, Andrey Filchenkov

Computer Technology Lab, ITMO University, Russia

[e-mail]1, [e-mail], [e-mail], [e-mail]

Abstract

Evolutionary algorithms (EAs) are random search heuristics which can solve various optimization problems. There are plenty of papers describing different approaches developed to apply evolutionary algorithms to the clustering problem, although none of them addressed the problem of fitness function computation. In clustering, many clustering validity indices exist that are designed to evaluate quality of resulting points partition. It is hard to use them as a fitness function due to their computational complexity. In this paper, we propose an efficient method for iterative computation of clustering validity indices which makes application of the EAs to this problem much more appropriate than it was before.

Keywords: Clustering, evolutionary clustering, clustering validity indices, fitness ¿SpS c??Juae 2019

function. Published: 24 June 2019

1 Introduction

The goal of clustering is to define a finite set of categories (clusters) to describe a dataset according to similarities among its objects [1]. There are plenty of applications of clustering: from image processing [2] and market segmentation [3] to web mining [4] and document categorization.

Clustering problem is initially formulated in general terms. Many mathematical formalisms were suggested to describe it. It was recognized quite a long time ago that the selection of a certain formalism to estimate the clustering quality will strongly influence both the algorithm that should be chosen and the result claimed to be the best [5], and that it is hard to compare different formalisms [6]. Kleinberg formulated three essential properties of clustering algorithms and proved that there is no way to create an algorithm that fits all these properties simultaneously [7].

There are two ways of evaluating clustering partitions, namely internal and external measures. External measures use some extra information about the task, for example, different benchmarks or class labels. These measures can not be applied in real life, because there might not be any external information about the problem to be solved. Internal measures use only the information about the structure of partition itself and only clustering validity indices (CVIs) satisfy this requirements.

Approaches to solve clustering task can be also divided into two categories: indirect, when we use a blackbox optimization algorithm with built-in quality evaluation measure, for example, k—Means [8], Spectral algorithm [12], DBSCAN [9] that are actually conventional clustering algorithms; and direct when we can set quality measure and search for the optimal partition in the space of all possible partitions for a given task. This problem is a discrete optimization task, one of the ways to solve it is to apply evolutionary algorithms [10].

Evolutionary algorithms (EAs) is a general name of a class of the random search heuristics that were inspired by the ideas of natural evolution. Namely, they are based on iterative improvement of some existing solution via mutation, crossover and selection operators. Often evolutionary algorithms cannot find optimal solution in reasonable time, however they were found effective for finding good enough solutions pretty fast. This makes them suitable for solving NP-hard problems, which clustering problem belongs to.

To apply an EA one first needs to define a quality measure for all solutions,, which is often called a fitness function. The main problem of all CVIs is super linear time complexity that might be crucial for the performance of an evolutionary clustering algorithm, no matter what strategy is chosen.

In this paper, we propose new incremental methods for computation of different CVIs' and provide experiments on several primitive strategies to find out if our method works faster than conventional CVI computation with the same outcomes. We study how using of the incremental CVI evaluation can improve the performance of three considered EAs solving a clustering problem.

The structure of the paper is following. Section 2 contains the description of incremental methods and provides the comparison with conventional CVI computation on different datasets. In section 3, we provide a description of the strategies that were used to test the CVI incremental computation approach. Section 4 provides the information about experiments.

2 Incremental CVI evaluation

In this section, we provide the description of new methods of incremental CVI computation. We considered 19 CVIs in this paper: Calinski-Harabasz index, Dunn index, C-Index, Davies-Bouldin Index, Modified Davies-Bouldin Index, Silhouette index, gD31, gD41, gD51, gD33, gD43, gD53 indices, CS index, Sym-Index, SymDB index, COP index, SV index, OS index, S_Dbw index. Descriptions of all these CVIs can be found in [11]. Due to the size limits of the paper we provide detailed incremental methods only for Calinski-Harabaz index, COP index, Silhouette index and Modified Davies-Bouldin index. Implementations of incremental computation for the other indices can be found in our repository1. Although we do not provide the methods for all the CVIs used in the paper, in the Table 2 we show that incremental recalculation complexity is much better than full recalculation of each CVI.

Table 1: Time complexity comparison between full and incremental recalculation of CVIs CVI Full time complexity Incremental time complexity

Calinski-Harabasz index O(n log n) O(n)

Dunn index O(n2 ) O(1)

Davies-Bouldin Index O(n log n) O(n)

Modified Davies-Bouldin Index O(n log n) O(n)

Silhouette index O(n2 ) O(n)

C-Index O(n log n) O(n)

gD31 O(n2 ) O(n)

gD41 o(n2 ) O(n)

gD51 o(n2 ) O(n)

gD33 o(n2 ) O(n)

gD43 o(n2 ) O(n)

gD53 O(n log n) O(n)

CS index O(n log n) O(n)

Sym-Index O(n2 ) O(n)

SymDB index o(n2 ) O(n)

COP index o(n2 ) O(n)

SV index O(n log n) O(n)

OS index O(n2 log n) O(n)

S-Dbw index O(n log n) O(n)

2.1 General notation

First, we introduce some formal notations of incremental computation. We denote by X a dataset, which consists of N points; C is its partition consisting of clusters C\, ••• , Cm. Centroid of cluster C is defined accordingly:

Ck = iCl JC x ■ (1)

The centroid of the entire dataset is defined as follows

1

N

x=N s xi. (2)

■i ex

The formula of the Euclidean distance between objects p and q, that has dimensionality n, of the dataset is:

de(p,q) = J E (Pk - qk)2 (3)

The mutation operator used inside EAs changes the structure of partition C by moving some points from one cluster to another. The task of incremental CVI recalculation is to effectively recalculate the value of CVI after such small change in the structure without recalculating it from scratch (which can take too much time). Further when discussing the iterative recalculation of CVI we denote by xid the point that was moved by mutation, by Ca the initial cluster of this point and by Cb — the cluster this point was moved to.

1https://github.com/AntipovDen/EvoClusterization

S. Muravyov et al. Soft Computing

2.2 Calinski-Harabasz index

This measure is calculated by the formula:

CH(X) N — K Ecfc GC C lde (^,X) (4)

CH (X ) = "K—-v^-77—• (4)

K — 1 £Ck GC^ GCk (xi,Cfc )

The numerator is the sum of the distances from the centroids of the clusters to the centroid dataset, the denominator is the sum over the distances from points to the centroids of their clusters. Accordingly, when recalculating, it is necessary to update the standing from Ca to X, from Cb to X and also the distances from the points of the Ca cluster to its centroid, from the points of the Cb cluster to its centroid and remove the distance de(xid, Ca), and instead add the distance de(xid, Cb). But since updating the distances from all points to the centroid is a rather expensive operation, the following optimization was applied - if the centroid moved less than e multiplied by the diameter of the dataset, the corresponding distances are not recalculated.

Complexity assessment: the measure itself is calculated for O(n), where n is the size of the dataset, but since it is still necessary to additionally calculate the diameter for optimization during the recalculation, the diameter calculation adds O(n log n) to asymptotics, so that the final asymptotics is obtained just as follows. Incremental counting takes O(n) for updating centroids. Further, if the distances from the points to the centroids are not recalculated (and recalculation will be necessary only in the worst case, when the centroid will move strongly), then the final operations will take O(1), and in general the final estimate is O(n). If we had to recalculate the distance to the centroids, then this adds another O(n) pass with the calculation of the Euclidean metric.

2.3 COP index

The measure is calculated as follows:

1 _ 1/|Cfc |£ _c de (Xi,Cfc)

COP(C) = -1 V |Ck| ^ kGCk e( " k> (5)

N C"GC mmXiGck maxI;eck de(xi, xj)

During the initial calculation it is proposed to save de (xi, Ck), it is also necessary to save de (xi, Xj) for each i and j, all possible distances for counting maxima (two-dimensional array), and also all maxima for a minimum (one-dimensional array). In other words, for each cluster we will separately store an array of numerators and denominators.

During the recalculation procedure, it will be necessary to remove de(xid, Ca) from the numerator for the term for Ca and add the term de(xid, Cb) for the numerator of Cb. The distances from the points of the Ca and Cb clusters to their centroids will not be recalculated if the centroids have shifted less than e multiplied by the diameter of the dataset. Also, in the arrays for the denominator Ca, it will be necessary to add all possible distances de(xid, xj), where xj £ Ca, and remove all possible distances de(xid,j ), where xj £ Cb, from the arrays for the denominator Cb. Then you just need to recalculate private for Ca and Cb.

Complexity assessment: the initial calculation of the measure requires the calculation of all possible de(xi, xj), which takes O(n2) time, then you just have to count the minima and maxima de(xi, Ck), all this together takes O(n2) time, and it is still necessary to calculate the diameter to accelerate the incremental conversion, which takes O(nlogn) time, but the final asymptotic remains O(n2).

During recalculation it is necessary to update the arrays of the corresponding numerators and denominators for Ca and Cb and recalculate the minima and maxima only for Ca and Cb and only if new distances for Ca are less or more, and for Cb only if xid . It is also required to update centroids for O(n) time and, in the worst case, to recalculate additionally the distances from points to centroids of the Ca and Cb clusters for O(n), but the final asymptotics remains O(n) time.

2.4 Silhouette index

The measure is calculated as follows:

Si/(C) = i V V b(xi,Cfc) — a(xi,Cfc) (6)

( ) N /-c 4c max(a(xi, Cfc),b(xi, Cfc)), ( )

ck GC xi GCk

where

a(xi,Cfc) = 1/|Cfc| ^ de(xi,xj), (7)

and

b(xi,Cfc) = min (1/|Ck| £ de(Xi,Xj)). (8)

Cl GO \Ck

xj GCi

Here, a(xi, Ck) and b(xi, Ck) are computed for all points in the dataset. Accordingly, it is necessary to keep them during the initial calculation. Then, when moving point xid from cluster Ca to cluster Cb, you need to re-calculate a(xid, Cb) and b(xid, Cb), and also update the values of a(xi, Ck) and b(xi, Ck) for all points of the clusters Ca and Cb. Then you need to re-calculate the sum and get an answer.

Complexity assessment: counting a(xi, Ck) and b(xi, Ck) takes O(n) times, respectively, counting them for all points takes O(n2) time. Further, the final answer is calculated for O(n). During recalculation procedure, it is necessary to re-calculate the functions a(xi, Ck) and b(xi, Ck), but only for one point, which takes O(n). Further, the values of these functions are updated in O(1) for all points of the clusters Ca and Cb, which also takes O(n), and the counting of the final answer also takes O(n). So the final complexity of the recalculation is O(n).

2.5 Modified Davies-Bouldin index

First let's consider the original Davies-Bouldin index formula:

DB(C) = ! V max SM^M, (9)

K GC\Ck de (Ck ,Ci) ' V 1

where

S(Ck) = l/|Cfc| V de(xi,Ck). (10)

xi GCk

In the implementation, the function S(Ck) is used, during the initial calculation it is proposed to save it. It is also necessary to calculate in advance the sums of all possible S(Ck) + S(Cj), then divide them by de(Ck, Ci) and store. Accordingly for the CVI computation it is necessary to find the maximum by the sets of this divisions.

Now, to recalculate this CVI, it is necessary to update S(Ca) and S(Cb) and the saved quotients, in which S(Ca) and S(Cb) were used, to find the maximum. But the operation of recalculating distances from a point to the centroid of its cluster is expensive - therefore, if the centroid has moved less than e, multiplied by the diameter of the dataset, S(Ca) and S(Cb), will not be recalculated. At the end, the search for the maximum is performed again.

Complexity assessment: the initial calculation takes O(n) to find all S(Ck) and O(nlogn) to find the diameter of the dataset, which is necessary to speed up the conversion. Recalculation takes O(n) in the worst case, so if the centroids have greatly moved, and in the best case it is O(K), where K is the number of clusters, but it is very small compared to the size of the dataset, therefore this asymptotics is equal to O(1), and it is also necessary at the beginning to recalculate the centroids, which will take O(n) time, so the final complexity is O(n).

Next, consider the modified Davies-Bouldin index. The CVI is calculated as follows:

DB*(C) = 1 V maxciGC\Ck (S(CkH Ci)) ( )

( ) K CkGC minCi gc\C de (Ck ,Ci) . ( )

Here, the recalculation principal practically coincides with the recalculation principal of the original Dadies-Bouldin index, the main difference is that we save not the divisions, but the sums from the numerator. To recalculate the denominator, it will be necessary to recalculate the corresponding de(Ck, Ci) for combinations with Ca and Cb.

The complexity estimate is the same as the complexity of the original Davies-Bouldin index, that is O(n log n) to be recalculated, and O(n) for recalculation, because the recalculation of the denominator will take a maximum of O(K2), which is O(1) in the current scope, and the recalculation of the numerator essentially coincides with the recalculation of the division in the original Davies-Bouldin index.

3 Evolutionary strategies

In this section, we describe three evolutionary strategies used in our experiments. For all of them by initial solution we mean some partition that was obtained through application of some conventional clustering algorithm.

Greedy algorithm. This one of the most simple EAs iteratively mutates the initial solution while it manages to find some strictly better solution. Namely, it stops as soon as the solution that it obtains through the mutation of the best-so-far solution is not the new best one.

The mutation operator first calculates for each point x the distances to the centroids of each cluster that x does not belong to. Then it finds px, that is, the minimal of such distances for point x. Finally, it moves 2l points, where t is the number of the current iteration, with minimal px to the clusters that are the nearest to

those points (in terms of the distance to the centroid). All ties in selection of the points to move as well as in choice of the nearest centroid are broken uniformly at random.

(1 + 1) EA. This algorithm generally reproduces the principles of the greedy algorithm, but uses different stopping criteria and mutation operator. The (1 + 1) EA keeps the best-so-far partition and on each iteration mutates it and replaces the current one with the new one if the new partition is not worse than the current one. It stops after its time limit is reached.

In contrast to the greedy algorithm, the mutation operator of (1 + 1) EA is randomized. First, it also calculates px, the distance to the nearest cluster for each point x. Then it chooses some number of points to move, and each point x is chosen with a probability proportional to p-1. The number of points to move is equal to the veiled mutation rate for the current population.

To increase the effectiveness of our algorithm, we use the 1/5-th rule to control the value of the mutation rate. Initially the mutation rate is one. After each successful iteration, which is such that the new solution is at least as good as the best-so-far solution, we divide the mutation rate by two (but it cannot become less than one point). After unsuccessful iteration we multiply the mutation rate by 21/4, but bound it with the half of the size of the solution. This rule while being easy to implement has been shown to be effective both in practical and theoretical analysis [13].

(1+4) EA. The main difference of this EA from the (1 + 1) EA is that in each iteration it generates and evaluates 4 new solutions in parallel. This increases the cover of the search space and helps to find new better solutions. However, parameter control for this algorithm is more complicated, so we do not use the 1/5-th rule for it. Instead, we generate the 4 solutions with different mutation rates, namely 1, 2, 4, and 8, using the same mutation operator as for the (1 + 1) EA.

4 Experiments

In Section 2, we showed that the theoretical time complexity of the proposed incremental CVI recalculation methods is lower than the time complexity of the conventional recalculation. Here we provide experiments to check this statement in practice. Also we check the reliability of the incremental computation. Some incremental CVI computations have approximations, for example approximate calculation of centroids. So we have to check if incremental CVI computations make the same results as conventional CVI computations.

Experimental setup was the following: we took 5 datasets from the UCI database2: glass, iris, wholesale, seeds, and ionosphere. We used 4 CVIs mentioned in Section 2. Each strategy from Section 3 was performed 10 times for each dataset and each CVI (all runs had the same initial clustering obtained through Spectral clustering algorithm [12]). The results of the experiments are shown in Table 2 and Figure 1.

In Figure 1 we present the results of our study on the reliability of incremental CVI computation. We used the same experiment setting for each dataset and each CVI. We compare each algorithm using the incremental CVI computations and the conventional CVI computations. We set time limit of 5 minutes for all of the experiments.

We exclude the results for the greedy algorithm from Table 1, since this algorithm has not reached any CVI improvements regardless the way of CVI computation.

From Figure 1, we conclude that in most cases incremental CVI computation provide almost the same CVI rates as conventional computation, so we showed the reliability of suggested incremental CVI computation approach. We also note few exceptions that might be caused by finding some local minimum by (1 + 1) strategy, especially modified Davies-Bouldin index on wholesale and iris datasets.

In Table 2, we present the results of our study on how much faster the optimization algorithms with incremental CVI are than the ones with conventional CVI. In these experiments for each pair dataset-CVI we first ran each algorithm with incremental CVI and time limit of 5 minutes. Then we ran the same algorithm with conventional CVI until it found some clustering that was at least as good as the one found by the corresponding run of the algorithm with incremental CVI (with the same initialization). These runs can take too much time, so we also added the time limit of 25 minutes for them.

In this approach we have a risk that a run of an algorithm with an incremental CVI does not improve the initial cluster. Therefore, the corresponding run of the algorithm with a conventional CVI does not perform any iteration, since its initial clustering is already as good as the one found by the first algorithm. We call such unfortunate runs invalid runs and we call all other runs valid.

Among the valid runs we also distinguish successful runs, that are the runs of an algorithm with conventional CVI that have finished before their time limit. The ratio of the successful runs to the valid runs is shown in the last column of Table 2.

In order to calculate the expected mean value of the algorithm runtime and the standard deviation of the runtime we use the same technique as in [14]. It was developed for the populations estimation but can be also

2https://archive.ics.uci.edu/ml/datasets.php

10

a 2

Calinski-Harabaz

¥

-□ (1 + 1) □ (1 + 1)* □ (1+4) -□(1+4)*

2 6

a 2

•10-

COP

CY

<> 1 1 1 □ (1 + 1) □ (1 +1)* □ (1 + 4) □ (1+4)*

S T L^ si

iii

0.1

5 • 10-

Modified Davies-Bouldin

Xy

] (1 + 1) (1 + 1)* ] (1 + 4) ](1 +4)*

•10-

0.5

Silhouette

Xy

A | 1 1 1 □ (1 + 1) □ (1 + 1)* □ (1 + 4) □ (1+4)*

T —

□ □ T st- . .T

III

Figure 1: Comparison of different CVI improvements for each dataset. Algorithms without star (*) mark use incremental CVI computation, algorithms with a star use conventional CVI computation. Both types of algorithms perform 10 runs each and have 5 minutes time limit.

0

4

2

0

2

0

1

0

Table 2: Time estimations for the algorithms that use conventional CVI computation. Algorithms with incremental CVI computation reach the same measure rates in 5 minutes in all the cases.

Dataset CVI Mean, min Deviation, min Successful runs

(1 + 1) (1 + 4) (1 + 1) (1 + 4) (1 + 1) (1 + 4)

Calinski-Harabaz 75.1 — 86.6 — 2/8 —

glass COP 22.8 > 25 30 unknown 5/9 0/10

Modified Davies-Bouldin > 25 — unknown — 0/9 —

Silhouette 50.2 0.0298 61.2 0.000224 3/9 10/10

Calinski-Harabaz > 25 > 25 unknown unknown 0/6 0/10

iris COP 17.1 > 25 26.4 unknown 6/10 0/10

Modified Davies-Bouldin 3.58 — 10.1 — 7/8 —

Silhouette > 25 > 25 unknown unknown 0/4 0/10

Calinski-Harabaz 3.52 — 8.79 — 9/10 —

wholesale COP 68.1 > 25 70.1 unknown 3/10 0/10

Modified Davies-Bouldin 0.192 > 25 0.139 unknown 10/10 0/10

Silhouette 23.4 > 25 30.2 unknown 5/9 0/10

Calinski-Harabaz 31.3 > 25 41.9 unknown 4/9 0/10

seeds COP 234 — 237 — 1/10 —

Modified Davies-Bouldin 6.45 — 14 — 8/10 —

Silhouette 20 > 25 26.6 unknown 6/10 0/10

Calinski-Harabaz 75.1 — 86.6 — 2/8 —

ionosphere COP 37.8 — 48.4 — 4/10 —

Modified Davies-Bouldin 3.98 — 8.81 — 9/10 —

Silhouette 50.5 > 25 61.2 unknown 2/6 0/10

applied to the algorithm runtime calculation. Let ES be the average of runtime for successful runs, R be the ratio of successful runs, G be the maximum runtime until restart and DS be the standart deviation of runtime for successful runs. Then the expectation of the runtime until success E is:

E = Es + i—R G. (12)

R

The standart deviation of the runtime D can be estimated by the equation:

D = y E| — E2 + D| + R (G2 + GE). (13)

However, the expected mean can be calculated only if the number of successful runs is at least 1. If for some setting we do not have any successful runs, we can only conclude that the mean runtime is at least the time limit and cannot say anything about its deviation. In Table 2 in such cases we write "> 25" for the mean runtime and "unknown" for its deviation.

We also exclude the results for the greedy algorithm from Table 2, since the valid runs of this algorithm were observed only in one setting.

From Table 2 we conclude that in most settings the algorithm with conventional CVI computation require much more time to find a clustering that is at least as good as the one found by the same algorithm with incremental CVI computation in 5 minutes. The few exceptions are highlighted in Table 2. We note that for three of these five exceptions deviation is relatively high, and the 5 minutes time limit given for the algorithm with incremental CVI computation lies inside the confidence interval.

For the other two exceptions (Silhouette index on the glass dataset and modified Davies-Bouldin index on the wholesale dataset) we noticed that it took no more than 166 iterations for the algorithm with conventional CVI to reach the desired value of measure. This implies that the algorithm with iterative CVI also finds such good clustering in a small number of iterations and then does not improve it until it reaches its time limit.

5 Conclusion

In this paper, we present and examine a new fast method of fitness function computation for evolutionary clustering algorithms. The proposed approach is based on gathering temporary data from CVI computation on previous iteration. It appears that our approach achieves better results than the conventional CVI computation

in most of the considered cases. The suggested method is planed to be tested on more sophisticated evolutionary

strategies [15].

Acknowledgement: The methods for incremental CVIs computation were developed under the research

project financially supported by The Russian Science Foundation, Agreement 17-71-30029.

References

[1] Kaufman, L. and Rousseeuw, P. J. 2009. Finding groups in data: an introduction to cluster analysis, vol. 344. John Wiley & Sons, USA.

[2] Jain, A. K. and Dubes, R. C. 1998. Algorithms for clustering data, vol. 6. Prentice hall, Englewood Cliffs, NJ, USA.

[3] Bigus, J. P. 1996. Data mining with neural networks: solving business problems from application development to decision support. McGraw-Hill, New York, USA.

[4] Mecca, G., Raunich, S., and Pappalardo, A. 2007. A new algorithm for clustering search results Data & Knowledge Engineering 62, 3, pp. 504-522.

[5] Anderberg, M. R. 1973. Cluster analysis for applications: probability and mathematical statistics: a series of monographs and textbooks. Academic press, USA.

[6] Bonner, R. E. 1964. On some clustering techniques. IBM journal of research and development 8, 1, pp. 22-32.

[7] Kleinberg, J. M. 2003. An impossibility theorem for clustering. In Advances in Neural Information Processing Systems 15 (NIPS 2002). MIT Press, pp. 463-470.

[8] Arthur, D. and Vassilvitskii, S. 2007. k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms.ACM, New Orleans, Louisiana, pp. 1027-1035.

[9] Ester, M. et al. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining -KDD 1996. AAAI Press, Portland, Oregon, pp. 226-231.

[10] Chakrabarti, D., Kumar, R., and Tomkins, A. 2006. Evolutionary clustering. In Proceedings of the 12th ACM international conference on Knowledge discovery and data mining - SIGKDD 2006. ACM, Philadelphia, PA, pp. 554-560.

[11] Arbelaitz, O. et al. 2013. An extensive comparative study of cluster validity indices. Pattern Recognition 46, 1, pp. 243-256.

[12] Ng, A. Y., Jordan, M. I., and Weiss, Y. 2002. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems 14, 2, pp. 849-856.

[13] Doer, B. and Doer, C. 2015. Optimal Parameter Choices Through Self-Adjustment: Applying the 1/5-th. In Proceedings of the Genetic and Evolutionary Computation Conference - GECCO 2015. ACM, pp. 1335-1342.

[14] Buzdalov, M. and Buzdalova, A. 2013. Adaptive Selection of Helper-Objectives for Test Case Generation. In 2013 IEEE Congress on Evolutionary Computation. IEEE, pp. 2245-2250. DOI: 10.1109/CEC.2013. 6557836

[15] Hruschka E. R. et al. 2009. A survey of evolutionary algorithms for clustering. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) 2, 39, pp. 133-155.

Meta-learning Based Evolutionary Clustering Algorithm

Dmitry Tomp1'2, Sergey Muravyov1'2, Andrey Filchenkov1'2, and Vladimir Parfenov2

1 Machine Learning Lab information Technologies and Programming Faculty ITMO University, 49 Kronverksky Pr., St. Petersburg 197101, Russia [e-mail], [e-mail], [e-mail], [e-mail]

Abstract. In this work, we address the hard clustering problem. We present a new clustering algorithm based on evolutionary computation searching a best partition with respect to a given quality measure. We present 32 partition transformation that are used as mutation operators. The algorithm is a (1 + 1) evolutionary strategy that selects a random mutation on each step from a subset of preselected mutation operators. Such selection is performed with a classifier trained to predict usefulness of each mutation for a given dataset. Comparison with state-of-the-art approach for automated clustering algorithm and hyperparameter selection shows the superiority of the proposed algorithm.

Keywords: clustering - evolutionary clustering - meta-learning - evolutionary computation

1 Introduction

Clustering is an unsupervised learning problem that has real-world data mining applications in fields such as bioinformatics [1], market segmentation [2], sociological studies [3] and many others.

The hard clustering task is formulated as splitting a dataset into partitions of similar objects; however, a specific measure of partition quality depends on a particular subject field and cannot be given in a general case due to the Kleinberg's theorem [4].

There is a wide variety of state-of-the-art clustering algorithms, including K-Means, Affinity Propagation, Agglomerative Clustering and Mean Shift, implemented in popular libraries like Scikit-Learn [5] and WEKA [6]. Most of them are designed based on some expectation on how a good partition should look like, making them indirectly tied to one or some particular partition quality criteria.

An alternative approach to the problem involves determining a partition quality criterion separately from selecting a clustering algorithm to seek a partition that satisfies the chosen criterion. For instance, one may choose to optimize

an internal scalar partition quality measures called cluster validity indices (CVI) such as Silhouette [7], Davies-Bouldin [8], Calinski-Harabasz [9], DBCV [10] or many others. A sound review of them can be found in [11]. In this case, any optimization algorithm (possibly dedicated to solving a clustering problem in particular) can be used to optimize such a measure.

Evolutionary algorithms have been used as a stochastic method of searching optimal solutions for a wide variety of problems. For clustering, an evolutionary algorithm may consider a partition as an individual, apply mutation and/or crossover operators to modify partitions and compare them using a specified cluster validity index. A nice survey [12] describing many attempts to solve a clustering problem using evolutionary algorithms.

Meta-learning is a popular approach to machine learning automation that is a development of algorithms that helps to choose machine learning models and tune their hyperparameters to perform better on specific kinds of input data. In meta-learning framework, the choice of a machine learning algorithm and its parameters is made by applying a supervised learning model that treats a dataset as a single vector of its scalar and/or categorical meta-features. The meta-learning approach has been applied to clustering problem previously in [13, 14], but these algorithms choose between state-of-the-art clustering methods without any regard for alternatives like evolutionary algorithms.

In this work, we focus on developing new clustering algorithm based on evolutionary computation. In this case, mutation operators are partition transformation. We propose 32 mutation operators inspired by ideas described in [12]. Experiments showed that only some of these mutations are useful in finding the best partitions of a dataset. What is even more important, sets of useful mutations vary for different datasets. Based on this, we propose an evolutionary-based clustering algorithm that preselects useful mutations for a particular dataset using meta-learning, adopting an approach presented in [15].

Section 2 contains description of our evolutionary algorithm and mutation operators. In Section 3, we explain how we preselect mutations via meta-learning. In Section 4, our we describe experimental setup and provide measurement results. Finally, in Section 5, we discuss efficiency of the proposed algorithm based on experimental results and point out some directions of further work that can be done in the field of clustering automation.

2 Proposed evolutionary clustering algorithm

2.1 Scheme of the evolutionary algorithm

We use the (1 + 1) as a basic evolution strategy, which is a best among the strategies we tested (see 2.2). Given a subset of mutations, it chooses a random mutation from the set, applies it to the current individual and get another partition. In a general case, the random choice can be performed according to an arbitrary (and possibly dynamically adjusted) probability vector. We initialize the partition for a given dataset by a random number of clusters build along

correspondent number of axes that go through the centroid of the dataset. The success of the mutation is defined by the value of the chosen fitness function, if it is better that its ancestor then mutation is treated successful. Pseudocode of our algorithm is provided in listing 1. We have chosen a stopping criterion of 250 consequent unsuccessful iterations based on early experimental runs. The algorithm also stops if either our mutation operator appears to be inapplicable to the current individual, or current number of clusters exceeds a certain threshold (for our experiments, we chose 70 as a fixed upper bound).

The latter part of the stopping condition is explained by two reasons. First, some CVIs considered in this work appear to perform very slowly on partitions with large number of clusters, second, it has been observed experimentally that the proposed algorithm sometimes converges to an "optimal" partition with most clusters containing from 1 to 5 objects.1

Algorithm 1 Algorithm (1 +1) with an externally selected mutation subset

function ONEPLUsONE(cvi, dataset, mutationSubset) currentIndividual ^ iNlTlALlZE(dataset)

currentIndex ^ EvALUATEPARTlTlON(cvi, currentInidividual)

unsuccessfulSteps ^ 0

while unsuccessfulSteps < 250 do

newIndividual ^ MUTATE(individual, mutationSubset) > see listing 2

if (newIndividual = 0) and (NUMCLUSTERS(newIndividual) > 70) then

return currentIndividual end if

newIndex ^ EvALUATEPARTlTlON(cvi, newIndividual) if newIndex currentIndex then currentIndividual ^ newIndividual currentIndex ^ newIndex unsuccessfulSteps ^ 0 else

unsuccessfulSteps ^ unsuccessfulSteps + 1 end if end while

return currentIndividual end function

A pseudocode for mutation application routine is shown in listing 2. In certain cases, a particular mutation cannot be applied to a partition, for example mutation, if applied to a current partition, would produce an inconsistent partition with a single cluster in it. The mutations used by our algorithm are described in Section 2.3.

1 This phenomenon is most likely related to properties of a specific CVI and can be further mitigated, e.g. by applying different initialization method or using a more complex mutation/evolutionary scheme.

Sometimes it is also possible that all available mutations cannot be applied to the partition; upon such an occurrence, the algorithm terminates.

Algorithm 2 Mutation application

function MuTATE(individual, usefulMutations) unusedMutations ^ CopY(usefulMutations) mutation ^ 0 repeat

mutation ^ RANDOмCнoICE(usefulMutations) if MuTATIONNoтApPLICABLE(mutation, currentIndividual) then if HAsREPLACEMENT(mutation) then

mutation ^ GEтREPLACEMENT(mutation) else

unusedMutations ^ unusedMutations \{mutation} mutation ^ 0 end if end if

until (mutation = 0) and (usefulMutations = 0) if mutation = 0 then

return ApplyMutation(mutation, individual) else

return 0 end if end function

2.2 Choosing scheme of the evolutionary algorithm

The choice of the (1 +1) scheme was based on early experimental results, which will be described in this Section.

In this work, we considered evolutionary schemes from the (1 + A) family, namely:

— (1+1) with random mutation from listing 1,

— (1+A = 10) that applies 10 random mutations on each step, possibly choosing a particular stochastic mutation several times;

— (1 + A = 32) that applies each of the implemented 32 mutations once.

We observed that all tested evolutionary schemes demonstrate approximately the same partition quality, while the (1 + 1) algorithm outperforms two other schemes in execution time. Some relevant results are illustrated in Figure 1.

2.3 Mutations for clustering

We used a total number of 32 mutations, all of them inspired by a survey in [12] and works [1,16,17] in particular. In this section, each of them will be described in detail. For lucidity, each mutation operator is given its unique number index M* to clarify how a total number of 32 mutations is obtained.

Cluster-oriented mutation A cluster-oriented mutation chooses a cluster (or, in a certain case, a pair of clusters) and modifies its content by moving its objects to or from other clusters.

Note that every mutation in this section is presented in either 5 or 3 variations depending on the number of interestingness measures it is used with - the logic of choosing a cluster according to interestingness values is described in the next subsection. For instance, (M1—M5) notation means that the mutation is used with trivial separation, diameter-based separation, mean centroid distance separation, density sparseness and validity index, respectively. Hyperplane split-gene mutation. A cluster is split into a pair new clusters by a hyperplane. The hyperplane is chosen in either of two ways:

— with random norm and position (M1—M5);

— directly between centroid and the point, which is the farthest from centroid in the cluster, perpendicular to line between them (M6).

Spanning tree split-gene mutation. A minimum spanning tree is built based on objects in the cluster and distances between them. The mutation chooses an edge in the tree probabilistically based on edge weights; the chosen edge is removed and the tree is split into a pair of connected components, each of them corresponding to a new cluster (M7—M10). Merge-gene mutation. Two chosen clusters are merged into one (M11—M13). Cluster elimination mutation. A cluster is removed; all its objects are reclassified into nearest clusters based on their centroids (M14—M18). Remove-and-reclassify mutation. A small set of l random objects from the cluster is attached to other nearest clusters based on distances to their centroids. The number l ^ B (jc.j|, jlj^ is chosen according to the binomial distribution, where \ci\ is number of objects in the cluster (M19—M23). Cluster expansion mutation. For a chosen cluster, a small set of l random objects from other clusters are attached to it. The objects are chosen selectively based on their distances to centroid of the target cluster - an object that is closer to the target cluster is more likely to be reclassified into it by the mutation (M24).

Choosing clusters selectively A cluster-oriented mutation from previous subsection chooses a set of clusters (or pairs of clusters) and operates on them

sequentially. More specifically: a number l ~ B (k, of clusters undergoing mutation is chosen out of k total clusters or l clusters are chosen according to probabilities proportional to interestingness values of the clusters.

In this work, we use the interestingness measures based on [10,18]:

— Mean centroid distance separation, which is used as a separation for generalized Dunn indices gDx3, where x stands for any cohesion of a generalized Dunn measure.

— Diameter separation, which is used as a separation for generalized Dunn indices gDx 1.

— Density sparseness separation DSC(i) from the DBCV index formula.

— Validity index separation Vc(i) from the DBCV index formula.

— Centroid distance cohesion, which is used as a cohesion for generalized Dunn indices gD^x.

— Density cohesion, which is originally called density separation of pair of clusters DSPC(i,j) in description of the DBCV index.

— Trivial interestingness measure, in which clusters or pairs of clusters are chosen pseudo-randomly.

It is worth noting that all cohesion measures and VC separation are descending, while others are ascending. The less is value of the descending measure, the greater should be probability of a cluster (pair of clusters) with this measure to be chosen. For this condition to hold, descending measure values are flipped symmetrically based on their maximum and minimum values - after that transformation, the clusters are chosen using the method described above.

Prototype-based mutation A partition will be referred to as centered if it is encoded with a set of synthesized objects called centres, with a direct correspondence between clusters and centres. In a centered partition, an object belongs to a cluster if and only if center of this cluster is closest to the object among others.

Similarly, a partition will be referred to as prototype-based if it is encoded with a set of real objects called prototypes and an object belongs to a cluster if and only if prototype of this cluster is closest to the object.

Some of the mutations listed below operate on centered or prototype-based partitions only and cannot be applied to integer-encoded partitions. See 2.1 for logic that is performed when a mutation cannot be performed with a partition.

K-Means step. Centroids of old clusters are computed; a new centered partition is composed with these centroids as centres (M25). Centroid hill climbing. A single randomly chosen coordinate of a centered partition is either multiplied by 1 +2$ if it is non-zero or set to 2d, otherwise. d is chosen from uniform distribution U([-1,1]) (M26). Mean Shift step. Centroids of old clusters are computed; for each of them, an object closest to this centroid is found. A new prototype-based partition is composed with these real objects as prototypes (M27). Prototype hill climbing. A random set of 1+ prototypes is added to the prototype-based partition; another random set of I- prototypes is removed from it. Values of

1+ and 1 are chosen based on binomial distributions: 1+ — B^n — k, n—,

1- — B (k,1) (M28).

Minimum spanning tree mutation An individual can be represented as a set of edges in the minimum spanning tree built for the whole dataset. More specifically, k clusters can be represented as connectivity components of this spanning tree after k — 1 edges are removed from it. We use two mutations treating partition as a set of edges in the spanning tree. The first one can be performed with any partition, while the last one operates on partitions which are already represented using this format. Both of them are represented as (M29), because choice between is determined by partition encoding. Creating a tree-based partition. For an arbitrary source partition, the mutation finds all weights in the spanning tree connecting objects from different clusters L = {(p, q) E E\3i,j : i = j,p E Ci,q E Cj}, where E are edges of the spanning tree, Ci is the i-th cluster in source partition, and p, q are objects in the dataset connected with the edge. Number 1 of edges to be removed from the spanning tree to form clusters of the new partition is chosen according to binomial distribution 1 - B (JL| — 1, jLj^). After that, 1 edges are selected with probability of an edge to be chosen proportional to weight of that edge: Pp,q — d(p, q). With the selected edges removed from the tree, a new tree-based partition is obtained. Modifying a tree-based partition. For a tree-based partition, the mutation adds and removes some edges from the spanning tree similarly to prototype hill-climbing mutation described above. The numbers of edges to be added and removed are determined according to similar binomial distributions, while the choice of edges is performed in a guided fashion with probabilities proportional to their weights. The more is distance between objects connected by the edge, the greater is probability for this edge to appear in the resulting partition.

Other mutations We also utilize two non-cluster-oriented mutations operating on a partition with integer encoding — i.e. a cluster is explicitly assigned for each object in the dataset. The first one reclassifies an object with its k nearest neighbors to another cluster [19] (M30). The second one is a special case of this mutation with k = 1 (M31). Another mutation (M32) used just transfer some random points from one cluster to another. The main aspect is that the CVI is computed in incremental way on each iteration [20].

3 Prediction of Useful Mutations via Meta-Learning

As it has been mentioned in 2.1, the algorithm requires a subset of mutations to be preselected for particular dataset and CVI. This subset is determined at the beginning of the algorithm according to prediction performed by a trained meta-classifier. Idea behind applying meta-learning here is simple. We run the evolutionary algorithm many times with all mutations and evaluated how many

times each mutation improves an individual. The results indicate that datasets are associated with various subsets of useful mutations. This means that each mutation may be useful or not useful depending on a dataset the evolutionary algorithm is applied to. Predicting mutations in meta-learning framework can be considered as hyper-heuristic [21,22] and was applied in a similar manner for selecting mutations of an evolutionary algorithm applied to a routing problem [15].

3.1 Meta-features

The meta-features a meta-classifier include statistical and distance-based metafeatures from [13] and landmarks which are composed as follows: four state-of-the-art clustering algorithms are run on the dataset. If an algorithm works with a predetermined number of clusters, it is initialized with a value tfn, where n is length of the dataset, then for each of the resulting four partitions, values of different CVIs are computed. In our setup, we used 10 CVIs mentioned in 4.

3.2 Determining target value

The proposed setup also requires usefulness of each mutation to be determined for each pair of a test dataset and CVI.

We perform this evaluation by running (1+A) algorithm on datasets with the following modification: on every step, each mutation described in 2.3 is applied to current partition once. This implies that A = 32, which is the exact number of mutations we used in our setup.

We consider a mutation useful if it has led to improvement of the CVI value at least once during execution of (1 + A). For partial noise reduction, we run the (1 + A) algorithm twice for each pair of CVI and dataset and consider a union of useful mutations from both runs as a target set for the classification task. We have collected statistics for our runs of (1 + A), it can be found at https://bit.ly/30Kb7kZ

4 Experimental setup

We used 93 datasets from the OpenML repository [23] and 4 synthetic datasets generated as unions of normal distributions, similarly to [11]. The algorithm was tested with 10 CVIs, namely: Silhouette [7], Davies-Bouldin [8], Generalized Dunn [18] (Dunn, gDi3, gDn, gD^3, gD5i, gD53), Calinski-Harabasz [9], DBCV [10].

For quality and time measurement of our approach in comparison with [24], we performed 10 runs of automated (1 +1) algorithm, 10 runs of non-automated version of our (1 + 1) algorithm (which considers all mutations useful) and 10 runs of automated clustering algorithm from [24]. This procedure was performed for every pair of CVI and dataset, resulting in a total number of 29100 runs.

(b) HappinessRank_2015

Fig. 2: Boxplots comparing CVI values reached by clustering algorithms for 3 example datasets. "predicted" stands for (1 + 1) with predicted mutations, "all" means non-automated version of (1 + 1) and "shalamov" is partition quality of reinforcement-based algorithm proposed by Shalamov et al. [24]

Resulting quality value is computed as mean value and standard deviation of a CVI for a particular dataset - figure 2 illustrates this comparison method for some datasets2. Time is computed as mean execution time over all 10 runs for each pair of CVI and dataset.

4.1 Effectiveness of proposed automation

We compared performance of the (1 + 1) algorithm with two configurations: the first one uses mutations predicted by the meta-classifier, while the last one considers all mutations applicable to any CVI and dataset. In other words, we analyze effectiveness of our automation by comparing performance of automated (1 + 1) algorithm with its non-automated version. The comparison results are presented in Table 1.

2 Full collection of comparison boxplots can be found at https://bit.ly/2Zr3WwG

Table 1: Number of (1 + 1) runs, grouped by CVI. "worse" stands for automated version reaching worse quality than non-automated; "not worse", conversely, means that partition quality was not degraded by applied automation. tp,ta are running times of automated and non-automated versions of the algorithm, respectively.

Dunn Davies-Bouldin Calinski-Harabasz

worse not worse worse not worse worse not worse

tp > ta 2 48 0 45 1 6

tp < ta 18 29 3 49 18 72

Generalized Dunn41 Generalized Dunn13 DBCV

worse not worse worse not worse worse not worse

tp > ta 2 32 0 27 0 48

tp < ta 16 47 17 53 0 49

Generalized Dunn51 Generalized Dunn43 Silhouette

worse not worse worse not worse worse not worse

tp > ta 1 17 2 33 4 15

tp < ta 10 69 7 55 20 58

Generalized Dunn53 All CVIs

worse not worse worse not worse

tp > ta 3 14 15 285

tp < ta 8 72 117 553

4.2 Comparison with reinforcement-based automated clustering method

In a recent work [24], an optimal clustering partition is obtained by performing SMAC (sequential model-based algorithm configuration [25]) iterations to optimize hyperparameters of state-of-the-art algorithms. To choose an algorithm that will be optimized in the next iteration, the multi-armed bandit problem is solved based on previous performance improvements of the trained models. In this Section, partition quality obtained by our automated approach is compared to this method.

For each CVI and dataset, we launch the reinforcement-based method with time budget equal to the average running time of our algorithm with these configuration and input. Table 2 shows the comparison results.

5 Conclusion

In this paper, we introduced 32 mutations for transforming partitions. Based on this, we propose an evolutionary clustering algorithm, which uses not all, but preselect the most useful for a given dataset using meta-learning. The proposed approach is based on predicting the set of useful mutations for each clustering task instead of choosing all the mutations available inside the evolutionary clustering algorithm. It appears that our approach achieves better results in most of the considered cases in terms of partition quality measured by different CVIs

Table 2: Number of (1 +1) runs compared to reinforcement-based approach [24], grouped by CVIs. "Worse" stands for (1 + 1) reaching worse partition quality, "same" stands for quality values being equal with accuracy within standard deviation, "greater" means that the evolutionary algorithm outperformed the reinforcement-based approach.