Кластерный анализ

Перевод Clustergram визуализация кластерного анализа на Python

28.05.2021 14:21:34 |

Автор: admin

В этой статье, переводом которой мы решили поделиться специально к старту курса о Data Science, автор представляет новый пакет Python для генерации кластерограмм из решений кластеризации. Библиотека была разработана в рамках исследовательского проекта Urban Grammar и совместима со scikit-learn и библиотеками с поддержкой GPU, такими как cuML или cuDF в рамках RAPIDS.AI.

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

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

Маттиас Шонлау предложил другой подход кластерограмму. Кластерограмма это двухмерный график, отражающий потоки наблюдений между классами по мере добавления кластеров. Это говорит вам о том, как перетасовываются ваши данные и насколько хороши ваши сплиты. Тал Галили позже реализовал кластерограмму для k-средних в R. Я использовал реализацию Таля, перенёс ее на Python и создал clustergram пакет Python для создания кластерограмм.

clustergram в настоящее время поддерживает метод k-средних, использование scikit-learn (включая реализацию Mini-Batch) и RAPIDS.AI cuML (если у вас есть GPU с поддержкой CUDA), Gaussian Mixture Model (только scikit-learn) и иерархическую кластеризацию на основе scipy.hierarchy. В качестве альтернативы мы можем создать кластерограмму на основе меток и данных, полученных с помощью альтернативных пользовательских алгоритмов кластеризации. Пакет предоставляет API, подобный sklearn, и строит кластерные диаграммы с помощью matplotlib, что даёт ему широкий выбор вариантов оформления в соответствии со стилем вашей публикации.

Установка

Установить clustergram можно при помощи conda или pip:

conda install clustergram -c conda-forge

или

pip install clustergram

В любом случае вам нужно установить выбранный бэкенд (scikit-learn и scipy или cuML).

from clustergram import Clustergramimport urbangrammar_graphics as uggimport seaborn as snsimport matplotlib.pyplot as pltfrom sklearn.preprocessing import scalesns.set(style='whitegrid')

Давайте рассмотрим несколько примеров, чтобы понять, как выглядит кластерограмма и что с ней делать.

Набор данных о цветке ириса

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

iris = sns.load_dataset("iris")g = sns.pairplot(iris, hue="species", palette=ugg.COLORS[1:4])g.fig.suptitle("Iris flowers", y=1.01)

Похоже, что setosa относительно чётко определённая группа, тогда как разница между versicolor и virginica меньше, поскольку они частично перекрываются (или, в случае ширины чашелистика, полностью).

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

Давайте начнём с кластеризации методом k-средних. Чтобы получить стабильный результат, мы можем запустить кластерную программу с 1000 инициализаций.

data = scale(iris.drop(columns=['species']))cgram = Clustergram(range(1, 10), n_init=1000)cgram.fit(data)ax = cgram.plot(    figsize=(10, 8),    line_style=dict(color=ugg.COLORS[1]),    cluster_style={"color": ugg.COLORS[2]},)ax.yaxis.grid(False)sns.despine(offset=10)ax.set_title('K-Means (scikit-learn)')

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

Мы ищем разделение, т. е. отвечаем на вопрос, принёс ли дополнительный кластер какое-либо значимое разделение? Шаг от одного кластера к двум большой хорошее и чёткое разделение. От двух до трёх свидетельство довольно хорошего раскола в верхней ветви. Но с 3 по 4 видимой разницы нет, потому что новый четвёртый кластер почти не отличается от существующей нижней ветви. Хотя сейчас она разделена на две части, это разделение не даёт нам много информации. Таким образом, можно сделать вывод, что идеальное количество кластеров для данных Iris три.

Мы также можем проверить некоторую дополнительную информацию, например оценку силуэта или оценку Калинского Харабазса.

fig, axs = plt.subplots(2, figsize=(10, 10), sharex=True)cgram.silhouette_score().plot(    xlabel="Number of clusters (k)",    ylabel="Silhouette score",    color=ugg.COLORS[1],    ax=axs[0],)cgram.calinski_harabasz_score().plot(    xlabel="Number of clusters (k)",    ylabel="Calinski-Harabasz score",    color=ugg.COLORS[1],    ax=axs[1],)sns.despine(offset=10)

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

Набор данных о пингвинах со станции Палмера

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

penguins = sns.load_dataset("penguins")g = sns.pairplot(penguins, hue="species", palette=ugg.COLORS[3:])g.fig.suptitle("Palmer penguins", y=1.01)

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

data = scale(penguins.drop(columns=['species', 'island', 'sex']).dropna())cgram = Clustergram(range(1, 10), n_init=1000)cgram.fit(data)ax = cgram.plot(    figsize=(10, 8),    line_style=dict(color=ugg.COLORS[1]),    cluster_style={"color": ugg.COLORS[2]},)ax.yaxis.grid(False)sns.despine(offset=10)ax.set_title("K-Means (scikit-learn)")

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

Можно ли сказать, что их три? Поскольку мы знаем, что их должно быть три... Ну, не совсем. Разница между разделениями 23 и 34 незначительна. Однако здесь виновником является метод K ближайших соседей, а не кластерограмма. Он просто не может правильно кластеризовать эти данные из-за наложений и общей структуры. Давайте посмотрим, как работает смешанная Гауссова модель (Gaussian Mixture).

cgram = Clustergram(range(1, 10), n_init=100, method="gmm")cgram.fit(data)ax = cgram.plot(    figsize=(10, 8),    line_style=dict(color=ugg.COLORS[1]),    cluster_style={"color": ugg.COLORS[2]},)ax.yaxis.grid(False)sns.despine(offset=10)ax.set_title("Gaussian Mixture Model (scikit-learn)")

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

Подобная ситуация случается очень часто. Идеального случая не существует. В конечном счёте нам необходимо принять решение об оптимальном количестве кластеров. Clustergam даёт нам дополнительные сведения о том, что происходит между различными вариантами, как они расходятся. Можно сказать, что вариант с четырьмя кластерами в данных Iris не помогает. Также можно сказать, что пингвины Палмера могут быть сложными для кластеризации с помощью k-средних, что нет решающего правильного решения. Кластерограмма не даёт простого ответа, но она даёт нам лучшее понимание, и только от нас зависит, как мы её [кластерограмму] интерпретируем.

Установить clustergram можно с помощью conda install clustergram -c conda-forge или pip install clustergram. В любом случае вам всё равно придётся установить бэкенд кластеризации: либо scikit-learn, либо cuML. Документация доступна здесь, а исходный код здесь, он выпущен под лицензией MIT.

Если вы хотите поиграть с примерами из этой статьи, блокнот Jupyter находится на GitHub. Вы также можете запустить его в среде interactive binder в браузере. Более подробную информацию можно найти в блоге Тала Галили и оригинальных статьях Матиаса Шонлау.

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

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

Другие профессии и курсы

ПРОФЕССИИ

КУРС

Подробнее..

Категории: Визуализация данных , Python , Open source , Блог компании skillfactory , R , Анализ данных , Gpu , Skillfactory , Кластерный анализ , Opensorce , Urban grammar , Cuml

Кластерный анализ каждому

19.01.2021 20:18:31 |

Автор: admin

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

Источник изображения: commons.wikimedia.org

Почему это круто

Кластерный анализ неформально можно определить как разбиение множества объектов так, чтобы похожие объекты попали в одно и то же подмножество, а объекты из разных подмножеств существенно различались. От обычной классификации по заданным признакам кластерный анализ отличается тем, что не алгоритм, а человек выявляет критерий кластеризации данных. Эта задача относится к классу обучения без учителя (англ. unsupervised learning), так как размеченного набора данных или какой-то заведомо известной информации о нём не предоставляется.

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

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

Сравнение применения алгоритмов с параметрами по умолчанию и с настроенными гиперпараметрами.

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

Как определить меру качества

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

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

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

Сравниваем разбиения

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

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

Сравниваем меры качества

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

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

Критерий ранжирования нормированная функция расстояния между ранжированием разбиений, задаваемым мерой качества, и агрегированным ранжированием разбиений, задаваемым оценками на основе визуального восприятия. Область значения данной функции: [0, 1]; чем значение функции ближе к , тем рассматриваемая мера качества лучше.

Для наглядности давайте рассмотрим пример с собранным мною набором данных из двухсот двумерных наборов данных 2D-200. Для каждого набора данных из 2D-200 были сформированы 14 разбиений. Эти разбиения были оценены пятью асессорами и девятнадцатью мерами качества. В итоге на наборе данных 2D-200 выявлены лучшие меры качества с точки зрения критериев Adq иЗатем для каждой меры по всем элементам из 2D-200 были вычислены следующие величины:

$BestCVI_{Adq}$ соотношение числа раз, когда мера отвечала критерию адекватности Adq к общему числу экспериментов;

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

Значения $BestCVI_{Adq}$ и для всех мер качества на наборе данных наборов данных 2D-200 представлены в таблице ниже.

Мера	$BestCVI_{Adq}$	Мера	$BestCVI_{Adq}$
DB		Sym
Dunn		CI
Silhouette		DB*
CH		gD31
S_Dbw		gD41
SymDB		gD51
CS		gD33
COP		gD43
SV		gD53
OS

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

Однако эффективная рекомендация из девятнадцати мер качества требует значительно большего числа наборов данных, чем представлено в 2D-200. Поэтому я построил множество из четырех самых лучших мер с точки зрения AvgCVI_R среднего значения, вычисляемого на основе критерия ранжирования мер: мера Silhouette, мера Calinski-Harabasz, мера gD41 и мера OS. В таблице приведены значения для всех исследованных мной внутренних мер качества.

Мера		Мера
*gD41*	$\mathbf{0,312}$	gD53
gD43		S_Dbw
gD33		Dunn
OS	$\mathbf{0,342}$	gD51
CH	$\mathbf{0,369}$	CI
*Silhouette*	$\mathbf{0,370}$	CS
SV		DB
Sym		COP
gD31		DB*
SymDB

Классификатор, который рекомендует меру качества

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

Как подобрать алгоритм

После того как мера качества известна, я определил два способа получения конечного разбиения, а именно построение эвристического или эволюционного алгоритмов кластеризации. В эвристических алгоритмах содержится неизменяемый критерий качества выстраиваемого разбиения, в эволюционных же критерий качества является гиперпараметром алгоритма. Гиперпараметры это параметры, значения которых задаются до начала обучения, не изменяются в процессе обучения и не зависят от заданного набора данных. Примерами эвристических алгоритмов служат такие алгоритмы, как k-Means, иерархический алгоритм и DBSCAN. Эволюционные алгоритмы осуществляют непосредственный поиск в пространстве возможных разбиений с целью найти оптимальное по задаваемой в качестве параметра мере качества.

Эвристические алгоритмы

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

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

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

Давайте формализуем задачу. Пусть задан некоторый временной бюджет на поиск лучшего алгоритма Требуется разбить его на интервалы T = t_1 + t_2 + . . . + t_m таким образом, что при запуске процессов $\pi_j$ с ограничением по времени t_i получается значение меры качества такое, что:

$Q(A_{\lambda_j}^{j}) \xrightarrow{(t_1, t_2, \ldots, t_m)} \min_j,$

где $A^j \in A, \lambda = \pi(t_i, A^j, \emptyset),$ и $t_1 + \ldots + t_m = T, t_i \geq 0 \: \forall i.$

В этом случае каждой ручке бандита соответствует определённая модель алгоритма кластеризации из конечного множества вызову ручки на итерации процесс оптимизации гиперпараметров этой модели в течение времени В результате будет достигнуто качество кластеризации $Q(A_{\lambda_i}^{i}, D).$

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

Иллюстрация работы метода выбора и настройки эвристического алгоритма MASSCAH представлена на рисунке ниже:

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

Одним из ключевых аспектов работы эволюционных алгоритмов является вычисление функции приспособленности. В нашем случае это внутренняя мера оценки разбиения. Важно научиться быстро её перерасчитывать, если структура кластеров изменилась. Переформулировать задачу можно так: пусть точка $x_{id}$ переместилась из кластера C_a в кластер C_b.

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

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

Мера	Полный пересчёт	Инкрементальный пересчёт	Точность пересчёта
Dunn	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	точный пересчёт
CH	$\mathcal{O}(n^2 \log(n))$	$\mathcal{O}(n)$	аппроксимация
CI	$\mathcal{O}(n \log(n))$	$\mathcal{O}(n)$	аппроксимация
DB	$\mathcal{O}(n \log(n))$	$\mathcal{O}(n)$	аппроксимация
Sil	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	точный пересчёт
gD31	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	точный пересчёт
gD33	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
gD41	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
gD43	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
gD51	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
gD53	$\mathcal{O}(n \log(n))$	$\mathcal{O}(n)$	аппроксимация
CS	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
DB*	$\mathcal{O}(n \log(n))$	$\mathcal{O}(n)$	аппроксимация
Sym	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
SymDB	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
COP	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
SV	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
OS	$\mathcal{O}(n^2 \log(n))$	$\mathcal{O}(n)$	аппроксимация
S_Dbw	$\mathcal{O}(n \log(n))$	$\mathcal{O}(n)$	аппроксимация

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

Эволюционный алгоритм кластеризации (1+1).

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

Ниже представлена таблица числа запусков алгоритма с автоматизацией и без неё, сгруппированная по оптимизируемым мерам качества. Хуже и не хуже означает, что автоматизированный алгоритм, соответственно, отстаёт либо не отстаёт от алгоритма без автоматической настройки параметров по качеству разбиений; среднее время работы алгоритма с автоматизацией и без неё соответственно.

Calinski-Harabasz		OS		gD41		Silhouette
хуже	не хуже	хуже	не хуже	хуже	не хуже	хуже	не хуже

Сравнение алгоритмов

Интересно сравнить алгоритм на основе выбора и настройки эвристических алгоритмов кластеризации MASSCAH с алгоритмом настройки эволюционного (1+1) алгоритма кластеризации.

Я предположил, что два алгоритма получают одинаковые значения меры качества, если интервалы этих значений [ - , + ] пересекаются. То есть была использована квантиль уровня $84,13\%$ для нормального распределения. Временной бюджет алгоритма, запускаемого на определённых мере и наборе данных, задавался равным среднему времени работы автоматизированного эволюционного алгоритма на этих мере и наборе данных. Я запустил алгоритмы со всеми отобранными ранее четырьмя мерами качества: Silhouette, Calinski-Harabasz, gD41 и OS. Для каждой пары мера набор данных производилось 10 запусков алгоритма. Полученные количества удачных и неудачных запусков приведены в таблице ниже.

Число положительных и отрицательных результатов сравнений алгоритмов на базе метода выбора и настройки эвристического алгоритма кластеризации на основе обучения с подкреплением, сгруппированные по мере качества разбиений. Столбец MASSCAH > Evo соответствует случаям, когда качество эволюционного алгоритма оказалось хуже, чем алгоритма на базе обучения с подкрепление, MASSCAH Evo что качества сравнимы, MASSCAH < Evo разработанный алгоритм опережает существующий результат.

		$MASSCAH \approx Evo$
Мера CH
Мера OS
Мера Silhouette
Мера gD41
Все меры
Мера Meta-CVI

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

Как применить всё это на практике

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

Схема описания работы программного комплекса.

Этот программный комплекс состоит из нескольких пакетов. Пакет CVI_Predictor реализует алгоритм предсказания меры для конкретной задачи кластеризации на основе мета-обучения. Пакет RL_Clustering реализует различные алгоритмы на базе представленного в работе метода выбора и настройки эвристического алгоритма кластеризации. Пакет Evo_Clustering реализует эволюционный алгоритм кластеризации с параметрами, настраиваемыми при помощи мета-обучения. Пакет Incremental_CVI реализует инкрементальное вычисление мер качества разбиений. Весь комплекс можно скачать на GitHub.

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

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

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

Помимо этого, программный комплекс был применён для разработки рекомендательной системы выбора научного руководителя и темы исследования для абитуриентов Университета ИТМО.

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