Кластеризация

СберСервис крупнейшая сервисная компания федерального значения, оказывающая услуги по комплексному техническому обслуживанию широкого спектра информационно-телекоммуникационного оборудования, рабочих мест, офисной техники, серверов и телефонии. Компания является единственным на территории СНГ премиум-партнером компании Zabbix, в ней работает самая крупная команда в России в сфере ИТ-мониторинга, разрабатывая уникальные технические решения в области комплексного внедрения систем мониторинга для организаций с высоконагруженной ИТ-инфраструктурой. Данный факт объясняет, почему в качестве основной платформы для мониторинга СберСервис выбирает Zabbix.

О чем эта статья?

Как следует из названия, в статье предлагается концепция организации мониторинга с высокой доступностью. В роли подопытного выступает Zabbix Server, для организации Active-Active кластера применяется Corosync и Pacemaker, а работает это всё на Linux. Данное ПО является OpenSource, поэтому такое решение доступно каждому.

В процессе эксплуатации Zabbix для мониторинга высоконагруженной ИТ-инфраструктуры (рост количества элементов данных, рост числа узлов сети, большая глубина хранения сырых данных, постоянно растущие потребности пользователей) многие сталкиваются с проблемами производительности сервера Zabbix во время старта или перезапуска. В условиях High Load (>60k NVPS) обычная перезагрузка сервера Zabbix превращается в весьма длительную, хотя и штатную процедуру. Время от запуска службы до появления данных в мониторинге может достигать 15-20 минут.

Столкнувшись с этим, и проанализировав ситуацию, команда мониторинга пришла к решению, что поможет кластеризация по принципу Active-Active. Кроме того, была поставлена цель добиться Disaster Recovery путем переноса на разные ЦОДы.

Задача

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

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

Требования

При создании кластера необходимо учесть два важных критерия:

• управление нодами ZabbixServer без видимого прерывания сервиса мониторинга на время проведения различных технических работ по обновлению, правке конфигураций и т. д., именно поэтому не подойдет виртуализация в чистом виде;

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

Встроенный функционал схемы кластеризации ресурсов в режиме Active-Passive с использованием Pacemaker и Corosync рассматривался уже много раз и в частности на Хабре естьподробная статьядля случая кластеризации БД истатья про кластеризацию Заббикса(вместо Corosync использовался cman, но смысл тот же).

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

Команда смогла придумать схему и реализовать логику работы всех компонентов и модулей системы для воплощения в реальность отказоустойчивого кластера, работающего в режиме Active-Active как с применением в схеме аппаратного балансировщика нагрузки (LoadBalancer), так и без него.

Полученное решение реализует два важных для системы мониторинга свойства:

• Непрерывность мониторинга

• Отказоустойчивость мониторинга

Рассмотрим реализацию решения High Available ZabbixServer в режиме Active-Active без LoadBalancerПринципиальная схема взаимодействия компонентов:

Принцип работы

Использование в схеме менеджера управления кластерными ресурсами (Cluster resource) подразумевает развертывание компонентов управления кластером на виртуальном сервере. Таким образом достигается отказоустойчивость управляющего модуля.

В кластере существует 2 ноды. При подготовке нод следует учитывать свойства stonith и quorum их необходимо отключить.
Свойство quorum применяется для схемы кластера от 3х нод и более. Если в схеме кластера, состоящего из 2х нод использовать данное свойство, тогда при падении одной ноды произойдёт выключение всех ресурсов.

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

ocf::heartbeat:ZBX-IPaddressocf::heartbeat:ZBX-Instance

При аварийном выходе из строя основной ноды, кластерные ресурсы перемещаются на резервную ноду. Ресурс ZBX-IPaddress управляет виртуальным ip-адресом и входит в стандартный набор кластерных ресурсов (IPaddr2). ZBX-Instance самописный кластерный ресурс для сервиса zabbix-server и управления подключениями к БД. На каждом Zabbix-сервере в конфигурационном файле прописаны разные пользователи БД, при этом, в любой момент времени пользователь основного Zabbix-сервера имеет права Read/Write, а пользователь резервного права ReadOnly, поэтому на обеих нодах служба zabbix-server может находиться в запущенном состоянии (привет, Active-Active).

Перевод кластерных ресурсов в случае сбоя выглядит следующим образом. Ресурс ZBX-IP-address переводит виртуальный IP-адрес на другую ноду, а ресурс ZBX-Instance переводит пользователя БД резервного zabbix-сервера в режим Read/Write, а пользователя БД основного zabbix-сервера в режим ReadOnly, при этом закрывая имеющиеся к БД старые сессии подключения. Таким образом мониторинг инфраструктуры не прекращается. Непрерывность записи информации достигается за счет буферизации снятых метрик с объектов мониторинга на стороне ZabbixProxy. После того как прокси получает подключение к серверу, он передает накопленные данные.

Важный нюанс применение данной схемы подходит только в случае нахождения master и slave ZabbixServer-нод в одной подсети.

Рассмотрим реализацию решения High Available ZabbixServer в режиме Active-Active с LoadBalancer

Принципиальная схема взаимодействия компонентов:

Принцип работы

Решение с применением аппаратной балансировки сетевой нагрузки на основе сигнального порта выглядит следующим образом. Аппаратный балансировщик нагрузки отправляет трафик на ноду, на которой доступен сигнальный порт, если порт доступен на обеих нодах, LoadBalancer не будет отправлять трафик на какую-либо из нод. Решение можно использовать, когда ноды кластера находятся в разных подсетях, что позволило развернуть высокодоступный кластер для работы в географически распределенном ЦОД.

В Pacemaker создаются кластерные ресурсы:

ocf::heartbeat:ZBX-Cluster-Socketocf::heartbeat:ZBX-Instance

Ресурс ZBX-Cluster-Socket управляет сигнальным портом на ноде нужен для работы LoadBalancer-а.

Ресурс ZBX-Instance управляет процессом zabbix-server-а и правами доступа к БД.

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

Ресурс ZBX-Cluster-Socket создаётся с помощью встроенной в Pacemaker функциональности по созданию ресурсов из системного процесса (службы). Служба сигнального порта обыкновенная самописная служба, которая просто открывает на хосте соответствующий порт, за состоянием которого будет наблюдать LoadBalancer. Осуществлена привязка ресурса ZBX-Cluster-Socket к ресурсу ZBX-Instance посредством ограничения (constraint) для того, чтобы кластерные ресурсы перемещались совместно. Corosync, управляя ресурсом ZBX-Cluster-Socket, поддерживает в открытом состоянии только порт 101 на основной Master-node и в закрытом состоянии порт 201 на резервной Slave-node. Для LoadBalancer сигналом на переключение/отправку трафика являются: открытый порт 101 на первой ноде или открытый порт 201 на второй ноде, если оба порта на обеих нодах открыты, или оба закрыты, трафик никуда не отправляется.

Переключение ресурсов с текущей Master-node на текущую Slave-node происходит следующим образом:

При падении Master-node, порт 101 становится недоступным, тогда сигналом для LoadBalancer на переключение трафика будет являться открытый порт 201 на Slave-node. Corosync, определив, что Master-node недоступна, переключает ресурсы ZBX-Instance и ZBX-Cluster-Socket вместе на Slave-node, а благодаря скрипту resource_movement, на основе которого Pacemaker создал ресурс ZBX-Instance происходит смена прав пользователей User_A и User_B в базе данных, при этом закрываются все старые сессии подключения к БД.

Что произойдет в случае потери связности между нодами кластера при условии полной работоспособности нод?

Схема та же: кластер состоит из 2-х нод Master-node (пользователь User_A) и Slave-node (User_B), на Master-node запущены кластерные ресурсы.

При потере связи каждая из нод определит, что другая нода недоступна, тогда обе запустят у себя кластерные ресурсы. Master-node перезапускать ничего не будет и продолжит работу, определяя свою роль главной. Slave-node тоже посчитает себя главной и запустит у себя кластерные ресурсы. При этом LoadBalancer определит, что на Master-node и Slave-node доступны порты ZabbixServer и управляющий порт, соответственно LoadBalancer прекратит передачу сетевого трафика.

Следует отметить важный момент какими будут права доступа к базе данных соответствующих пользователей? Одна из нод по-прежнему будет иметь доступ к БД с правами Read/Write, а другая с правами ReadOnly, так как:

• Если связь Slave-node с БД не была потеряна, то Slave-node во время включения у себя кластерных ресурсов произведет смену прав пользователей: для User_A права изменятся на ReadOnly, а для User_B права изменятся на Read/Write.

• Если связь Slave-node с БД потеряна, следовательно Slave-node не сможет выполнить переключение прав пользователей.

• После восстановления связности кластерные ресурсы снова переместятся на Master-node, LoadBalancer определит, что управляющий порт доступен только на Master-node и начнёт передавать ей сетевой трафик.

Заключение

Данный кейс иллюстрирует принципиальную идею и концепцию придуманного решения (а точнее 2-х реализаций), и не является прямым руководством к действию. Инфраструктуры и ограничения у всех разные, а инженеры, перед которыми ставятся похожие задачи не нуждаются в How to.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

гдеи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Привет, Хабр! Компьютерное зрение и искусственный интеллект одни из самых востребованных направлений в современном IT. Поэтому мы выбрали именно их для учебного"Межгалактического Хакатона 2021"который организовали НИТУ МИСиС и Zavtra.Online (подразделение SkillFactory по работе с университетами).

В хакатоне были представлены 5 кейсов от разных компаний, и одним из них был кейс от компании IntelliVision кластеризация изображений транспортных средств. Его и выбрала команда финалистов, описав реализацию подобного проекта от А до Я.

Начало работы

Целью любого кластерного анализа является поиск существующих структур. Так и в нашей задаче были даны изображения, которые нужно разбить на кластеры и интерпретировать каждый из них. В качестве исходных данных нам предоставили изображения транспортных средств разных типов, цветов, ракурсов и деталей. Исходные изображения были загружены в нейронную сеть, которая определила паттерны и построила модель, и эта модель отображается в виде вектора (дескриптора), полученного на промежуточном (скрытом) слое нейронной сети. Варианты дескрипторов, полученные с помощью глубокого обучения, были исходными данными для дальнейшей кластеризации: color_model, osnet, efficientnet-b7, type_model.

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

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

Особенности выполнения задания

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

Сначала проводилась работа по понижению размерности данных для увеличения скорости обучения моделей, но PCA давал малоинформативные результаты, а t-SNE из библиотеки scikit-learn имел низкую производительность. И тут на помощь пришёлRapids бесплатный open-source фреймворк для ускорения обработки данных от NVIDIA, в котором есть библиотека машинного обучения cuML. Задача была решена в Jupyter Notebook в Google Colab, так как в эту среду легко установитьRapids, а также использовать его совместно с GPU Tesla K80 с 13 Гб видеопамяти на борту.

Исследование набора данных color_model

Этот набор данных в виде csv файла из 416314 строк и 128 столбцов был получен при помощи модели регрессии для определения цвета транспортных средств в формате RGB. Это единственный набор, который было возможно использовать для проведения экспериментов без понижения размерности.

Кандидатами в лучшее число кластеров на основе метода локтя оказались 3 и 4.

По визуализации результатов кластеризации (кандидаты в лучшие кластеры) для стандартизированных и нормированных данных видно, что предобработка данных повлияла на результат кластеризации. Разделение на 2 и 3 кластера почти одинаковое вне зависимости от способа обработки данных, но есть разница в разбиении на 4 кластера.

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

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

Видно, что в зависимости от потребностей при 2-х, 3-х и 4-х кластерах вне зависимости от типа обработки можно получить кластеры:

[Светлый-Тёмный],

[Светлый-Тёмный-Цветной],

[Светлый-Серый-Тёмный-Цветной]

А что же другие алгоритмы? Мы попробовали также DBSCAN, и у него получилось выделить отдельно выбросы фото низкого качества. Это фото с включёнными фарами, вблизи и сзади. Интересный эффект кластер жёлтых автомобилей.

Видно, что, комбинируя K-means и DBSCAN, можно в зависимости от потребностей получить разбивку на цветовые кластеры с различной детализацией, а также выделить выбросы.

Исследование набора данных osnet

Следующим набором дескрипторов, на котором мы провели исследования, сталosnet.

Из условий задачи нам было известно, что для построения дескрипторов osnet использовалась нейронная сеть, обученная для повторной идентификации людей, животных и машин (reID). В отличие от type_model и color_model эта модель не обучалась на исходном датасете veriwild.

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

В связи большим размером данныхosnet(csv файл из 416314 строк и 512 столбцов) и ограниченности имеющихся вычислительных мощностей и сроков все эксперименты проводились на предобработанных данных с пониженной при помощи t-SNE размерностью.

Помимо простого алгоритма k-Means мы решили проверить Mini-Banch k-Means. Как и ожидалось, Mini-Banch k-Means справился быстрее, но качество кластеризации, показанное простым k-Means, оказалось лучше.

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

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

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

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

Также мы увидели, что модель не разделила транспортные средства на отдельные кластеры в зависимости от типа: седан/джип/грузовик/автобус. Можно предположить, что другие параметры кластеризации позволят улучшить качество такого разбиения.

Особый интерес представляет способность модели выделять нестандартные кластеры. К примеру, нам показалось, что в одном из экспериментов модель выделила в отдельный кластер объекты с бликами и пятнами:

Исследование набора данных efficientnet-b7

Следующим этапом исследования было исследование работы модели на дескрипторе Efficientnet-b7. Этот дескриптор был самым большим по размеру (416314, 2560), данная модель классификации изображений обучена на Imagenet и до этой работы данных из veriwild не видела.

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

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

Затем кластеризовали данные на 2, 3, 4, 20 кластеров методом k-Means, как показавшим лучшие результаты на предыдущих моделях, описанных выше.

Аналогично описанию выше было определено исследуемое количество кластеров с помощью Elbow method clistering (метод локтя):

В силу схожей природы индекса Дэвиса Болдуина (ДБ) и метода локтя в данном исследовании взят индекс ДБ с его локтями в точках 9 и 20. Для того чтобы компенсировать недостаток данного индекса, заключающийся во влиянии масштаба данных на значение индекса, применена нормализация данных перед исследованием (craftappmobile.com).

Визуализация для нормализованной модели:

Результаты кластеризации (в виду большого числа картинок, все под спойлерами):

Кластер 0 светлые машины, задом.Кластер 1 тёмные машины.Кластер 2 светлые машины, передом.

Кластер 0 светлые машины, передом.Кластер 1 тёмные машины, передом.Кластер 2 светлые машины, задом много выбросов.Кластер 3 тёмные машины, задом много выбросов.

Кластер 0 светлые машины, передом, ракурс направо, внедорожник (вэн) много выбросов.Кластер 1 тёмные машины, задом, ракурс влево много выбросов. Кластер 2 светлые машины, задом, ракурс влево.Кластер 3 светлые машины, задом, ракурс вправо, внедорожник (вэн) много выбросов.Кластер 4 синие машины, передом, ракурс вправо.Кластер 5 белые машины, передом, ракурс вправо, внедорожник (вэн).Кластер 6 белые машины, задом, ракурс вправо, седан много выбросов.Кластер 7 белые машины, передом, ракурс вправо, седан много выбросов.Кластер 8 тёмные машины, передом, ракурс вправо много выбросов.

Кластер 0 красный, передом, влево много выбросов из-за сливающегося цвета фар.Кластер 1 т.-серый, перед, вправо, кроссовер.Кластер 2 синий, зад, вправо много выбросов.Кластер 3 белый, перед, вправо нет ошибок, кузов определён неточно: хэтчбек/кроссовер.Кластер 4 св.-серый, зад, вправо, седан.Кластер 5 т.-серый/чёрный, перед, влево, кроссовер.Кластер 6 белый, зад, вправо, кроссовер.Кластер 7 белые, перед, вправо, седан.Кластер 8 белый, зад, влево, кроссовер.Кластер 9 т.-серый, перед, вправо, седан.Кластер 10 т.-серый, зад, вправо, седан.Кластер 11 св.-серый, перед, влево, вэн. Кластер 12 св.-серый, перед, вправо, вэн.Кластер 13 белый, перед, вправо, седан.Кластер 14 т.-серый/чёрный, перед, влево, седан смешан с кластером 5.Кластер 15 белый, перед, влево, седан.Кластер 16 т.-серый, зад, влево, седан.Кластер 17 св.-серый, перед, вправо, кроссовер.Кластер 18 чёрный, перед, вправо, кроссовер много выбросов.Кластер 19 чёрный, перед, вправо, седан.

Выводы:

1. Модель кластеризации с 20 кластерами, определёнными методом локтя с помощью индекса Дэвиса Болдуина показала себя лучше, чем модели с меньшим количеством кластеров, и в целом достаточно информативно.

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

3. Ошибок в кластере не более 33 % (3 из 9), но чаще 22 % (2 из 9), при этом всего кластеров с ошибками 40 % (8 из 20).

4. Следует отметить, что модель плохо различает данные (фотографии), когда фары и машина одного цвета: происходит больше ошибок.

5. Для упрощения работы с моделью можно применять методы уменьшения размерности, в частности, t_SNE показал лучший результат уменьшив размерность с (416314, 2560) до (416314, 2), что позволило использовать значительно меньшие мощности вычисления и получить вполне интерпретируемый результат.

6. Более подробного анализа выбросов в данном разделе не производилось.

Исследование набора данных type_model

Набор данных в виде csv файла, имеющего 416314 и 512 столбцов, был получен при помощи модели определения типа, и в целом работа с ним была аналогична работе с набором color.

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

Кластеризация проводилась как на стандартных, так и на нормированных данных.

Как и в случае с набором данных color, результаты кластеризации на данных, размерность которых была понижена при помощи t-SNE, целом не дают чёткого деления на кластеры.

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

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

Кластер 0 седаны (небольшие авто),
Кластер 1 кроссоверы (джипы),
Кластер 2 микроавтобусы, автобусы (крупные авто).

В случае с 6 кластерами их условно можно идентифицировать следующим образом:

Кластер 0 седаны (вид спереди).
Кластер 1 джипы, хэтчбеки.
Кластер 2 мини-вэны.
Кластер 3 седаны (вид сзади).
Кластер 4 грузовики.
Кластер 5 хэтчбеки.

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

Заключение

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

Участники командыCloud_9:

• Екатерина Лушпина Team Leader / презентация / коммуникация / статья;

• Анастасия Сухоносенко Product Manager / план исследования / код-фреймворк / презентация / статья;

• Александр Кудрявцев Speaker, Team Member / исследование / презентация / спикер / статья;

• Наталья Авдеева Team Member / исследование / презентация / статья;

• Павел Озернов Team Member / исследование / техническая поддержка / презентация / статья.

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

Примечание редактора

Если в вашей компании есть кейcы по Data Science, которые вы бы хотели решить в рамках хакатона или стать ментором пишите в личные сообщенияskillfactory_school. Также мы будем рады индустриальным партнёрам для наших программ и можем предложить им разные виды сотрудничества: членство в наблюдательном совете, экспертиза для создания курсов, стажировки в ваших компаниях для студентов и другие виды партнёрства. Давайте развивать Data Science вместе!

Узнать больше про нашу магистратуру можно на сайтеdata.misis.ruи вTelegram-канале.

Ну, и, конечно, не магистратурой единой!.. Хотите узнать больше проData Science,машинное и глубокое обучение заглядывайте к нам на соответствующие курсы; будет непросто, но увлекательно.

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

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering

Улучшение интерпретируемой модели Prophet с помощью глубокого обучения

Привет, хабровчане. В рамках набора учащихся на онлайн-курс "Machine Learning. Advanced" подготовили перевод материала.

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

Изучая прогнозирование временных рядов, рано или поздно вы наткнетесь на чрезвычайно популярную модель Prophet, разработанную Facebook. Она приобрела свою большую популярность благодаря тому, что обеспечивает хорошие показатели с точки зрения точности, интерпретируемых результатов и, в то же время, автоматизирует многие элементы (например, подбор гиперпараметров или конструирование признаков) за пользователя. Вот почему ее относительно просто использовать как и опытным датасайентистам, так и энтузиастам с меньшим техническим багажом.

Можете себе представить, насколько я был приятно удивлен, когда недавно наткнулся на новую библиотеку для прогнозирования временных рядов NeuralProphet. Как вы можете понять из названия библиотеки, это по сути старая добрая Prophet только на стероидах, которыми в данном конкретном случае являются нейронные сети. Учитывая, что в настоящее время я довольно много работаю с временными рядами, я очень хотел проверить, какова она в сравнении с обычной Prophet.

В этой статье я кратко расскажу вам, что такое NeuralProphet и чем она отличается от классической библиотеки. Затем я применю на практике обе библиотеки, чтобы увидеть, насколько хорошо они могут выполнять одну и ту же задачу прогнозирования временных рядов. Определенно, вам будет полезно иметь некоторое представление о прогнозировании временных рядов, чтобы понимать всю терминологию. Давайте начнем!

NeuralProphet

Чтобы понять, что такое NeuralProphet, я кратко рассмотрю ее составные части и объясню, как все они складываются воедино.

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

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

Источник

Мы можем рассматривать Prophet как расширение базовых авторегрессионных моделей. Вместо того, чтобы просто использовать лаговые значения целевой переменной, модель предоставляет дополнительную форму конструирования признаков она применяет ряд Фурье к входной переменной. Это позволяет нам аналитикам дополнительно поднастраивать модель для повышения производительности, а также декомпозировать результаты для лучшей интерпретируемости. Prophet имеет множество других полезных функций, некоторые из которых мы перечислим ниже:

• Prophet может использовать дополнительные внешние регрессоры т.е. не только лаговые значения цели

• модель может учитывать эффект праздников

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

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

• поскольку типы сетей, разработанные для прогнозирования последовательностей (а временные ряды также являются последовательностями), изначально были разработаны для обработки естественного языка и компьютерного зрения, они требуют значительного объема данных.

• настройка гиперпараметров, безусловно, не так проста, как в параметрических моделях

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

Как упоминалось во введении, основными преимуществами использования Prophet являются хорошая производительность, интерпретируемость, а также простота установки и использования. Именно на это авторы NeuralProphet ориентировались в разработке своей библиотеки сохранить все преимущества Prophet, улучшив при этом его точность и масштабируемость за счет внедрения улучшенного бэкенда (PyTorch вместо Stan) и использования авторегрессионной сети (AR-Net), чтобы объединить масштабируемость нейронных сетей с интерпретируемостью авторегрессионных моделей. Если охарактеризовать AR-Net одним предложением, то это однослойная сеть, которая обучена имитировать авторегрессионный процесс в сигнале временного ряда, но в гораздо большем масштабе, чем традиционные модели.

NeuralProphet против Prophet

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

• NeuralProphet в целях оптимизации использует градиентный спуск PyTorch, что значительно ускоряет моделирование

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

• Лаговые регрессоры моделируются с использованием отдельной нейронной сети прямого распространения.

• Кроме того, модель имеет настраиваемые нелинейные глубокие слои сетевых сетей прямого распространения

• Модель настраивается на определенные горизонты прогноза (больше 1).

• Она предлагает настраиваемые потери и метрики.

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

Установка

На момент написания, лучший способ установить NeuralProphet это клонировать репозиторий и установить ее прямо оттуда, запустив pip install. в каталоге. Самую актуальную информацию о процедуре установки см. в этой части инструкции.

Установив библиотеки, импортируем их в Python.

import pandas as pdfrom fbprophet import Prophetfrom neuralprophet import NeuralProphetfrom sklearn.metrics import mean_squared_error# plottingimport matplotlib.pyplot as plt# settingsplt.style.use('seaborn')plt.rcParams["figure.figsize"] = (16, 8)

neural_prophet_1.py hosted with by GitHub

Подготовка данных

В этом примере мы будем работать с набором данных Peyton Manning (звезда НФЛ). Если вы не американец, вам, вероятно, придется заглянуть в статью в Википедии, чтобы понять шутку в документации к Prophet. Но вернемся к нашей теме набор данных содержит лог ежедневных просмотров его странички в Википедии.

Набор данных был собран командой Facebook, чтобы показать, как работает Prophet, и доступен для использования как в Prophet, так и в NeuralProphet.

Мы загружаем данные, выполнив следующую строку:

# loading the datasetdf = pd.read_csv('../neural_prophet/example_data/wp_log_peyton_manning.csv')print(f'The dataset contains {len(df)} observations.')df.head()

neural_prophet_2.py hosted with by GitHub

Для тех, кто раньше не работал с Prophet, для запуска модели нам нужны два столбца с соответствующими именами: ds столбец даты/таймстемпа, а y переменная, которую мы хотим прогнозировать. Учитывая, что это учебный набор данных, он уже подготовлен.

Затем мы выводим данные на график, чтобы иметь возможность сделать некоторый базовые предположения. Учитывая взлеты и падения, я могу предположить, что рост популярности коррелирует с сезонами НФЛ. Пожалуйста, поправьте меня, если я ошибаюсь.

df.plot(x='ds', y='y', title='Log daily page views');

# getting the train/test splittest_length = 365df_train = df.iloc[:-test_length]df_test = df.iloc[-test_length:]

neural_prophet_3.py hosted with by GitHub

Prophet

Как уже упоминалось, Prophet упрощает конечным пользователям получение прогнозов. Мы уложились в 4 строчки кода. Мы можем кратко их рассмотреть. Сначала мы создаем экземпляр модели, используя настройки по умолчанию. Затем мы обучаем модель, используя обучающие данные. Чтобы получить прогнозы, нам нужно создать так называемый future dataframe. Мы указываем количество дней, на которое мы хотим сделать прогноз. По умолчанию метод также включает исторические данные. Таким образом, мы получим подобранные величины (прогнозы с использованием данных из обучающей выборки). Наконец, мы получаем прогнозы и сохраняем их в preds_df_1.

prophet_model = Prophet()prophet_model.fit(df_train)future_df = prophet_model.make_future_dataframe(periods=test_length)preds_df_1 = prophet_model.predict(future_df)

neural_prophet_4.py hosted with by GitHub

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

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

В качестве последнего шага мы отражаем на графике извлеченные компоненты. Этот процесс аналогичен стандартной декомпозиции временных рядов.

prophet_model.plot_components(preds_df_1);

Мы можем наблюдать на графике тенденцию на протяжении многих лет вместе с недельной и годовой составляющими.

NeuralProphet

К счастью, API NeuralProphet практически идентичен оригинальному Prophet. Таким образом, уже зная, что мы делали в предыдущем примере, нам будет очень легко применить NeuralProphet к задаче прогнозирования временных рядов.

nprophet_model = NeuralProphet()metrics = nprophet_model.fit(df_train, freq="D")future_df = nprophet_model.make_future_dataframe(df_train,                                                  periods = test_length,                                                  n_historic_predictions=len(df_train))preds_df_2 = nprophet_model.predict(future_df)

neural_prophet_5.py hosted with by GitHub

Естественно, мы используем другой класс для инстанцирования экземпляра модели. Другие отличия заключаются в явном указании частоты данных при обучении модели (исходный Prophet был в первую очередь предназначен для ежедневных данных) и упоминании длины исторической выборки, которую мы хотим включить в future dataframe. Чтобы примеры были как можно более похожими, мы включаем все исторические данные.

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

nprophet_model.plot(preds_df_2);

Затем мы наносим компоненты на график. На момент написания в прогнозах нет доверительных интервалов (как правило, в preds_df_2 гораздо меньше столбцов, чем в preds_df_1, но это, скорее всего, скоро изменится!), но мы можем включить невязки для периода обучения.

nprophet_model.plot_components(preds_df_2, residuals=True);

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

nprophet_model.plot_parameters();

Мы включили сюда только два графика, так как оставшиеся два перекрываются с графиками, полученными с помощью plot_components (еженедельная и годовая сезонность).

Сравнение показателей

Наконец, мы сравниваем производительность моделей. Для этого мы помещаем все прогнозы в тестовый DataFrame, наносим на график результаты и вычисляем среднеквадратичную ошибку (MSE).

# prepping the DataFramedf_test['prophet'] = preds_df_1.iloc[-test_length:].loc[:, 'yhat']df_test['neural_prophet'] = preds_df_2.iloc[-test_length:].loc[:, 'yhat1']df_test.set_index('ds', inplace=True)print('MSE comparison ----')print(f"Prophet:\t{mean_squared_error(df_test['y'], preds_df_1.iloc[-test_length:]['yhat']):.4f}")print(f"NeuralProphet:\t{mean_squared_error(df_test['y'], preds_df_2.iloc[-test_length:]['yhat1']):.4f}")df_test.plot(title='Forecast evaluation');

neural_prophet_6.py hosted with by GitHub

Запуск этого кода создаст следующий график.

Хотя может быть трудно однозначно сказать, какие прогнозы ближе к фактическим, расчет MSE ясно показывает победителя NeuralProphet.

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

Выводы

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

Лично я бы не советовал всем отказываться пока от Prophet в пользу NeuralProphet, в основном потому, что библиотека все еще молода и постоянно развивается, что может быть не лучшим фактором для использования в производственной среде. Тем не менее, я однозначно рекомендую следить за ее развитием!

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

Ссылки:

• Neural Prophet: https://github.com/ourownstory/neural_prophet

• Facebook Prophet: https://facebook.github.io/prophet/

• AR-Net: https://arxiv.org/pdf/1911.12436.pdf

Узнать подробнее о курсе "Machine Learning. Advanced"

Смотреть вебинар Кластеризация временных рядов

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

Один из подходов к решению данной задачи (чтобы метод кластеризации автоматически отсеивал выбросы) получил название "optimally tuned robust improper maximum likelihood estimator" и был описан вот в этой статье 2017 года (http://dx.doi.org/10.1080/01621459.2015.1100996), а недавно и получил реализацию на R. Поговорим о нем.

Минутка теории

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

Математический апгрейд классического алгоритма состоит в том, что берется чуть иное предположение. Считается, что функция вероятности распределения точек является суммой смеси гауссиан и равномерного распределения шумовых точек (считается, что выбросы распределены равномерно), то есть

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

но вот с такими ограничениями

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

Эксперимент

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

library(ggplot2)# Создаем базу данныхset.seed(739)n <- 500 # numer of pointsy <- abs(c(rnorm(n,5,2)))x <- c(rnorm(n,5,1))/sqrt(y)class<-rep(1,n)dat1 <- as.data.frame(cbind(x,y,class)) # Первый кластер - что-то типа кривоугольного прямоугольного треугольникаy <- c(rnorm(n,8,0.4))x <- rlnorm(n, meanlog = log(7), sdlog = 0.2) class<-rep(2,n)dat2 <- as.data.frame(cbind(x,y,class)) # Второй кластер - больше похож на форме на горизонтальный прямоугольникy <- c(runif(n, min = 2, max = 7))x <- c(rnorm(n,8,0.4))class<-rep(3,n)dat3 <- as.data.frame(cbind(x,y,class)) # Третий кластер - вертикальный прямоугольникy <- c(runif(n/10, min = 0, max = 10))x <- c(runif(n/10, min = 0, max = 10))class<-rep(0,n/10)dat4 <- as.data.frame(cbind(x,y,class)) # Шумdat <- rbind(dat1,dat2,dat3,dat4)colnames(dat) <- c("x","y", "class")dat$class <- as.factor(dat$class)dat_test <- as.data.frame(dat)p_base <- ggplot(dat,aes(x=x,y=y,color=class)) + geom_point()ggExtra::ggMarginal(p_base, groupColour = TRUE, groupFill = TRUE)

Получаем вот такую картинку

Пакет otrimle достаточно современен в том плане, что в нем уже есть функция, позволяющая сравнить результаты кластеризации в случае задания нескольких кластеров. Зададим число кластеров от 2 до 5, и попробуем посмотреть на ход выполнения.

library(otrimle)clus <- otrimleg(dat[,c(1,2)], G=2:5, monitor=1) # параметр monitor позволяет видеть ход выполнения

В результате выведется вот что-то такое

В теории, этого уже достаточно для определения оптимального числа кластеров (мы же решаем задачу на максимум, и, в теории, нужно взять число кластеров, для которого iloglik максимален. С другой же стороны, видно, что значимого преимущества в разбиении на 4 или 5 кластеров по сравнению с 3 нет - поэтому выбор количества кластеров в значительной степени эмпирика). Но желательно посмотреть еще и на количество наблюдений внутри кластеров. Поэтому, не отходя далеко, жмем

clus$solution

и получаем следующую информацию

Для каждого из построенных разбиений Noise - количество элементов, классифицированных как выбросы. Совсем аномальных кластеров (в которых 1,2,10 наблюдений) вроде бы нет - поэтому более подробно посмотрим на разбиение с 5 кластерами.

clus_2 <-otrimle(dat[,c(1,2)], G = 5, npr.max = 0.01, erc = 20, monitor = TRUE)# npr.max - максимальная доля выбросов в выборке# erc - соотношение максимального/минимального собственных значенияclus_2$codeclus_2$flag

Если clus_2$code возвращает 0, это значит, что задача оптимизации вообще не решилась, если clus_2$code = 1, это означает, что EM-алгоритм не сошелся (и надо поиграться с параметрами), если clus_2$code = 2, то все хорошо, алгоритм все посчитал.

Параметр clus_2$flag дает информацию о внутренней структуре работы алгоритма. Если

clus_2$flag = 1, то присутствует вырождение апостерирорных вероятностей

Фактически, это говорит о наличии лишних кластеров, так как вероятность одного из компонент смеси близка к 0.

clus_2$flag = 2, то для сходимости алгоритма было нарушено предположение о доли шума

clus_2$flag = 3, то для при расчетах ограничение на долю шума было использовано

clus_2$flag = 4, то для при расчетах было использовано ограничение на отношение собственных значений

В нашем случае все хорошо (clus_2$code = 2, clus_2$flag = 4), продолжаем разбираться дальше.

clus_2$mean # центра кластеровhead(clus_2$tau) # вероятности принадлежности к кластерамhead(clus_2$cluster) # принадлежность к кластерам

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

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