- Mon 12 December 2022
- обучение
- #mlsystemdesign
Двенадцатая лекция открытого курса "Дизайн систем машинного обучения", "Временные ряды и графы".
Слайды можно скачать тут mlsysd12ods.pdf
Текстовая расшифровка, пока не вычитана:
Добрый день, меня зовут Дмитрий Колодезев и это 12 лекция курса про дизайн систем машинного обучения — "Временные ряды и графы".
Прежде чем строить какие-то модели, нам нужно понять, с чем мы собственно работаем, то есть что мы знаем про данные. А что мы вообще можем знать про данные? Во-первых, мы можем знать, как они устроены, откуда они берутся, как мы их собираем, то есть какие преобразования, какие-нибудь операции, которые происходят над данными, когда мы их складываем куда-то, где храним, детекция аномалий — как мы находим аномальные значения, как мы заполняем пропущенные значения, как мы можем взять какую-то репрезентативную подвыборку из наших данных, если их слишком много или нам нужно разделить на обучающий и тестовый наборы, что мы можем на них предсказывать, и можем ли мы построить на этих данных векторное представление.
Вообще говоря, все это довольно неочевидные вопросы во многих практических случаях. Например, как собираем данные — для аэрофотосъемки или для космических снимков очень нетривиальный вопрос. У нас солнечные лучи проходят через атмосферу, которая более-менее затуманена водяными парами, отражаются от земли, еще раз проходят через атмосферу, попадают на датчики спутника, который может их собирать разным способом. Сам по себе спутник, прежде чем нам эти данные передадут, скорее всего, их отправил куда-то, и этим данным выполнили привязку и сделали первичную предобработку, при которой интересные нам данные могли потеряться, ну и так далее. То есть сам по себе процесс обработки данных очень важен, потому что многие проблемы в данных возникают именно в процессе подготовки, и, не зная процессы, мы не сможем с ними ничего делать. Но это лекция про графы и временные ряды, и давайте посмотрим, что мы знаем про временные ряды, или time series.
Во-первых, как они устроены. Временные ряды — это последовательность однотипных значений, индексированных временем. Что такое индексированных временем? Это означает, что на них есть некий порядок и временные отметки, то есть мы можем посмотреть, какое значение соответствовало, например, 1 января или, например, скажем, 25 марта.
Обычно временные ряды — это количественные данные, то есть вещественные числа, но они также могут быть порядковыми и номинальными. Порядковые данные — это когда у нас определен порядок: например, в оценках пятерка лучше четверки, четверка лучше тройки, тройка лучше двойки, двойка лучше единицы, но, насколько двойка лучше единицы, толком никто не знает. То есть у нас определен порядок, но никакие операции, например, сложить двойку с тройкой и получить пятерку, мы сделать не можем. А номинальное — это когда у нас на данных нет порядка, то есть, например, у нас есть красный, зеленый, синий или груши, яблоки, апельсины и нет никакого однозначного порядка, по которому мы могли бы сказать, что, допустим, груша это лучше, чем яблоко, а яблоко это лучше, чем апельсин.
Во временных рядах обычно одно значение, но точно также может быть несколько значений, например, датчик может выдавать сразу вектор значений.
Они могут быть взяты через равные промежутки времени или через произвольные промежутки времени, то есть, например, идеальный временный ряд — это когда у нас через один и тот же шаг взяты значения, например, каждую секунду или каждую минуту или каждый день, но очень часто у нас данные доступны не всегда, а вот в какие-то кусочки. И передаваться они могут неравномерно, иногда могут быть пропущены изначально, иногда просто без всякой схемы, то есть, как получится снять отчет, так и получится.
Ну и разные переменные в одних и тех же временных рядах могут быть взяты с разной частотой. Время может быть указано с разной точностью и в разных часовых поясах. Про часовые пояса — это вообще интересный момент, потому что, когда мы строим систему, мы как бы предполагаем, что все временные отметки мы можем сравнивать между собой и все они в одном часовом поясе. Там можно отдельным образом по этому поводу работать, я чуть-чуть попозже приведу примеры.
Про временные ряды — какие бывают величины? Например, величины бывают измеряемые, они отличаются тем, что они имеют мгновенное значение, то есть в любой момент мы можем сказать, что моментальное значение величины такое-то. Например, скорость вращения двигателя — в любой момент у нас есть какая-то скорость вращения двигателя. Есть энергопотребление, и, несмотря на то, что его меряют в киловаттах в час, вообще-то говоря, мы можем померить энергопотребление в секунду. Температура сервера в градусах, курс акций. С курсом акций тоже сложно — обычно под курсом акций понимают некоторую усредненную величину между продажей акций или между состоявшимися сделками по продаже или состоящимися сделками по покупке. То есть, курс акций на самом деле сложный агрегат, но можно сказать, что в какой-то конкретный момент для каких-то акций установлен какой-то курс. Ранг сайта в поисковой выдаче — например, у нас сайт был на пятой позиции в поисковой выдаче, стал на третьей. И вот это пример порядковых данных. Понятно, что третья позиция лучше, чем пятая или седьмая, но никаких арифметических операций над ними мы производить не можем.
Еще временные ряды могут быть номинальными. Это, например, состояние замка — открыт или закрыт. То есть, мы можем представлять это как целое число, допустим, 0 или 1, но вообще-то это номинальные данные. Их может быть больше — например, если это состояние системы больше, чем 2, то представлять их в виде нуля, единицы и двойки может быть некорректно.
И есть еще агрегированные значения. Они не имеют смысла без указания временного отрезка. Например, сумма продаж — сколько продал наш интернет-магазин. За час? За день? За месяц? За год? То есть, без указания временного отрезка сам по себе показатель не имеет никакого смысла. Или, например, количество показателей на сайте. Счетчики поисковых систем, например, Google или Яндекс, они нам показывают, например — прямо сейчас на сайте у нас 15 человек. Обычно это означает, что 15 человек у нас было за последние, например, 10 минут или 5 минут.
Во временных рядах очень важно само время. И во временных рядах могут быть указаны часовые пояса или не указаны. При этом часовые пояса могут влиять на дату. Часовые пояса могут быть указаны или не указаны. Часовые пояса, кстати, влияют на дату. То есть, например, у нас есть отчеты, которые генерируются по новосибирскому и по московскому времени для разных пользователей. И суммы за сутки в них не совпадают, потому что в новосибирские сутки попадает кусочек, который не попадает в московские, а в московские попадает кусочек, который не попадает в новосибирские.
Желательно, если, конечно, это получится, иметь единый часовой пояс. Причем лучше всего в UTC-0, то есть по Гринвичу. Но даже в этом случае точно будут проблемы — кто-то решит, что это московское время, а кто-то решит, что это местное время. Если все сервера в одной локации — например, у нас большинство серверов стоят в московских датацентрах, то можно использовать время этой локации. Но и тут будут проблемы — то есть кто-то решит, что время по Гринвичу, а некоторые системы принципиально работают только с временем по Гринвичу.
Если источник данных не сообщает часовой пояс, то нужно добавить его в данные при сохранении. То есть проблемы будут все равно. Вы могли ошибиться при определении его. Пример, когда источник данных не передает часовой пояс — это, например, в браузере кто-то указывает какое-то время, у вас есть время события у клиента в приложении. То есть хорошо, если приложение вам сообщит часовой пояс. Может сообщить локацию, допустим, и тогда из локации вы можете вычислить часовой пояс.
Сам по себе часовой пояс источника может меняться. То есть day saving time, например — разница во времени между Новосибирском и, скажем, Сиднеем меняется в разное время года. И законы про то, как переводятся часы на летнее и зимнее время, они тоже меняются. То есть вы можете предположить, например, что летом часы переводятся на час, а потом закон отменят, и они перестанут переводиться. И у вас есть данные до этого периода и после этого периода.
Ну и библиотеки часто конвертируют часовые пояса внутри себя, причем иногда разные версии одной и той же библиотеки делают это по-разному. То есть вы отладили все эти глюки с временем, обновили версию питона, обновили версию pymongo, и у вас время, которое сохранялось в одном часовом поясе, начало сохраняться в другом. В общем, за временем надо следить, нужен глаз да глаз.
Как мы собираем временные ряды? Если источников данных мало, то они могут писать в базу данных сами, но чаще всего данные приходят нам через какой-то API. В API кто-то отправляет нам данные, скорее всего, в JSON. Типа data нет в JSON. Соответственно, данные приходят строкой. Как эта строка сформатирована — ну, как повезет.
Тип данных есть в binary JSON, BSON, который используется в MongoDB. И тут тоже есть проблема — когда вы сохраняете данные, допустим, в MongoDB, она их хранит в BSON, и потом вы экспортируете их в JSON, и вот они снова строки.
Удобно складывать временные ряды в топики Kafka, о которой мы как-то говорили раньше, и их можно использовать прямо из Kafka, не складывая в базу. То есть мы можем считать какие-то оконные статистики прямо в Kafka до записи в базу. Также из Kafka мы можем пересэмплировать данные перед записью в базу или накапливать данные пакетами.
Про накапливать данные — многие базы данных неэффективно работают в ситуации, когда мы пишем в них по одной записи. Например, ClickHouse очень не любит сценарий, когда мы записываем по одной строчке. Допустим, если мы комбинируем наши данные по 100 строк и записываем в ClickHouse, то будет скорость практически такая же, как если мы записывали по одной строчке. То есть там и там мы сможем условно сделать 100 записей в секунду. Это связано с тем, что ClickHouse при получении каждой строчки данных, при каждом новом пакете данных, он сохраняет их сразу на диск, а потом занимается переупаковкой данных на диске, поэтому для него сама по себе операция записи какого-то количества строчек достаточно дорогая. Поэтому все системы, которые работают с ClickHouse, нагружены. Они обычно комбинируют где-то данные, часто в той же самой Kafka, которая имеет прямой коннект, sync, в ClickHouse. И ClickHouse забирает их оттуда крупными пачками. Это здорово снижает нагрузку на ClickHouse и ускоряет запись.
Где мы храним данные? Мы можем хранить данные в обычных реляционных базах данных, например PostgreSQL, Oracle или Microsoft SQL Server. Там обычно всегда есть типы данных для времени и какие-нибудь операции над временем — то есть получить часть данных, загрубить, выбрать какую-нибудь оконную статистику по временному ряду.
Есть колоночные база данных, такие, как ClickHouse. Они хранят данные по колонкам, то есть каждый столбец хранится отдельно. Это удобно тем, что, допустим, у нас в отчете несколько столбцов — например, дата, время, температура, влажность, давление. И дата у нас в течение дня не меняется вообще, то есть у нас одна и та же самая дата весь день идет. Время, понятно, каждый раз разное. Температура меняется, скажем, каждую сотую запись, давление — каждую пятисотую запись. И ClickHouse архивирует, сжимает столбцы так же примерно, как это делает архиватор. Он хранит словарь данных, и внутри он хранит данными сжатыми. То есть, вместо того, чтобы хранить дату для каждой из строчек, он говорит — ну, вот у меня есть значение дата, а дальше все десять тысяч строчек используют это мое сохраненное значение номер один из словаря. Это здорово снижает занимаемое место и на самом-то деле позволяет эффективно работать с данными, но замедляет запись. То есть появляется некоторый этап переупаковки, когда он сначала пишет их всырую, потом сжимает, переупаковывает. То есть это особенность, про которую надо знать.
Часто time series, временные ряды, хранят в файловой системе, например, в S3. Ну, или когда вы их храните в Hadoop, фактически вы их храните в распределенной файловой системе, например, в parquet или в tab separated файлах.
У Amazon, AWS, есть база для хранения time series, которая построена поверх S3. Есть non-SQL базы данных, например, такие, как MongoDB или Redis, которые часто используют для хранения временных рядов. Redis быстрый, хороший, но несколько менее масштабируемый, чем MongoDB. MongoDB масштабируется хорошо и сильно, особенно если продумать идеологию шардирования. И у нее есть оконные функции, которые позволяют работать с временными рядами эффективно. И в последней версии MongoDB добавили специальный тип коллекции, оптимизированный для временных рядов.
Есть специальная time series база данных, например, Influx, в которой часто хранят статистику собираемой серверов телеметрии, или TimeScaleDB. В Hadoop, когда хранят данные, если у вас есть Hadoop, там есть hbase и поверх нее Open Time Series Database. В случае, если у вас есть Hadoop, наверное, вариантов других и нет. Если вы работаете в инфраструктуре Google, то у вас есть выбор — хранить данные в BigQuery или BigTable. В BigQuery получается несколько дешевле и, на мой вкус, мощнее. Там можно делать ML-модели, которые работают прямо внутри BigQuery. В BigTable она быстрее, но хранение системы, хранение данных получаются дороже. У Яндекса есть Yandex.DataBase, совместимый по API с AWS Dynamo DB амазоновской.
Проблема временных рядов в том, что они поступают все время. То есть, если обычные транзакционные данные у нас поступают, когда стряслось какое-нибудь событие, то временные ряды обычно идут потоком, то есть их много. И нам нужно делить данные на части для хранения. Естественное партиционирование во временных рядах – это партиционирование по времени. То есть, мы, например, сегодняшний день складываем в одну физическую таблицу, вчерашний день – в другую, позавчерашний – в третью. У, например, того же самого ClickHouse мы задаем ключ партиционирования — как раз вот дату. Проблема такого подхода в том, что все новые данные всегда пишутся в самую последнюю партицию. С этим можно бороться отдельным образом, но про это надо просто помнить, что если у вас есть 100 серверов, они партиционированы по времени, то все время на запись у вас будет нагружен только один сервер.
Какой способ хранения временных рядов выбрать? Ну, во-первых, надо выбирать то, что уже есть в системе. То есть, вы уже как-то храните данные, и ваши временные ряды, скорее всего, надо хранить там же, где хранится все остальное. Если данных мало, однозначно храните в реляционной базе данных. Если у вас есть Hadoop, используйте Open Time Series Database. Если данные сложные, то есть, у вас по каждому отсчету не просто пара чисел, а какой-то словарь, причем, может быть, с меняющейся структурой — то есть, сегодня он один, завтра другой, послезавтра третий — то, наверное, MongoDB будет хорошим выбором. Если мы часто пишем данные и редко их читаем, то ClickHouse идеален — он как раз был придуман для хранения временных рядов, кликстримов, статистики, вебсайтов. Если данных очень много, то лучше всего брать что-нибудь облачное, вроде BigQuery или TimeStream.
Как мы заливаем туда данные? TimeScaleDB — хороший сценарий: мы льем наши временные ряды в Kafka, а у Kafka есть sink в TimeScaleDB. У ClickHouse та же самая модель — льем данные в Kafka, ClickHouse умеет из sink Kafka забирать. Sink — это то, что стоит на конце конвейера. То есть, если помните, когда мы говорили про Kafka, я сравнивал ее с некоторым конвейером, багажной лентой, по которой движутся ваши чемоданы, и вы ищете в них свой. Так вот, в конце этой багажной ленты стоит так называемый sink, их может быть несколько, который отправляет данные куда-нибудь. Он может просто удалять данные, которые дошли до конца, а может заливать их в базу данных пачками. Есть sink из Kafka в Redis, есть sink из Kafka в MongoDB. Если вы используете TimeStream амазоновский, то естественно использовать Amazon Kinesis — это функционально аналогичная Kafka система, брокер сообщений. Для BigQuery, пожалуй, правильный подход будет — с помощью DataFlow (это Hosted версия Apache Beam) писать в BigQuery.
Пример, как мы могли бы обрабатывать временные ряды с Kafka — есть статья про детектирование аномалий, ссылка на слайде. То есть у нас есть некоторый источник транзакций, постоянных во времени операций, есть брокер Kafka, который берет данные из топиков и пишет, наверное, в какую-то базу данных. И тут же прямо из топика — как мы помним, у одного топика может быть несколько подписчиков, — стоит система аномалий, которая, грубо говоря, просматривает проезжающие по багажной ленте чемоданы и ищет, нет ли в них чего-нибудь странного. И, как только аномалия найдена, она ставит сообщение об аномалии в другой топик для аномалий, откуда все заинтересованные лица его заберут, отправят оповещение, сделают еще что-нибудь, предпримут какие-нибудь меры, которые нужно предпринять, когда аномалия детектирована. То есть у нас есть топик, по которому идут исходные данные, и топик, — один или несколько, — в который у нас уходят сюда аномалии, сюда насчитанные статистики и так далее.
По ссылке на слайде есть разбор того, как можно построить предсказания на временных рядах, которые прямо сейчас льются в нашу систему. То есть с помощью Apache Beam у нас есть два потока. Первый — наши данные льются в Pub/Sub, это брокер сообщений гугловский, попадают в DataFlow, который их сохранит в BigQuery. Это тот самый первый поток с транзакционными данными, прием данных. А дальше, как только данные попали в BigQuery, мы можем в DataFlow написать постоянный запрос, который будет все время подтягивать свежие данные, попавшие в BigQuery. И DataFlow вытаскивает их оттуда, отправляет в библиотеку Prophet, которая выполняет предсказания на временных рядах, и складывает предсказанные обратно в BigQuery. Таким образом, у нас текут в базу данных данные, в наше хранилище BigQuery, и сразу параллельно насчитываются прогнозы, прямо по мере поступления данных.
Еще примеры — из документации по DataFlow, Time Series Streaming. Там два примера. Один из них — торговый робот для торговли акциями, а второй — работа с IoT, интернетом вещей, то есть сбором данных с устройств. И вот тут мы видим, что у нас есть некоторые потоки сырых данных. И на этих данных мы насчитываем некоторые агрегирующие значения, то есть это линия аккумулятора. На них же мы насчитываем некоторые скользящие метрики, в данном случае скользящие средние, например, и некоторые производные метрики — то есть мы можем считать некоторые прогнозы, исходя из уже насчитанных наших средних и каких-то аккумуляторов, агрегированных данных. И в результате мы можем либо отдавать какие-то торговые сигналы — то есть продаем, покупаем эти акции, потому что они падают, они растут, либо в случае time series streaming от каких-нибудь датчиков мы можем заполнять пропущенные значения, либо выполнять детектирование аномалий, очистку и так далее.
Что используют для анализа временных рядов? Во-первых, много доброй старой статистики — это ARIMA, SARIMA, DARIMA и так далее. Часто используют градиентный бустинг, в основном в соревнованиях, потому что он очень удобен. Есть от Tinkoff Etna Time Series Forecasting Framework, есть прекрасная библиотека Prophet, она простая, удобная и под капотом использует систему вероятностного программирования Stan. Соответственно, вы можете не только построить модель с помощью Prophet, но и переписать их базовую модель, дополнить какими-то признаками. Это немножко сложнее, чем просто запустить прогноз Prophet, но, в общем, тоже вполне делается.
Prophet придумали в фейсбуке, когда он еще назывался фейсбуком, для того, чтобы делать тысячи прогнозов в день. То есть хороший аналитик данных за два дня прогноз сделает гораздо лучше, чем Prophet. Может быть, даже за полдня, если все время одни и те же похожие временные ряды идут. Но проблема в том, что, если вам нужно делать много прогнозов, скажем, тысячи прогнозов, то вам понадобится тысячи аналитиков. Это дорого, неудобно и медленно. И для решения этой проблемы как раз фейсбук разработал библиотеку Prophet.
Есть библиотека Luminaire для мониторинга и поиска аномалий во временных рядах. Из библиотек для поиска аномалий во временных рядах это, наверное, самое лучшее. Есть Gluon Time Series — это библиотека для вероятностного моделирования временных рядов на питоне. И сравнительно свежее дополнение в PyTorch Forecasting про Temporal Fusion Transformers, трансформеры для предсказания временных рядов.
При работе с временными рядами бейзлайны наши обычно очень простые. То есть самый простой и очевидный бейзлайн для временных рядов — "завтра будет так же, как вчера". Несколько более сложный — в тех случаях, когда у нас есть какая нибудь выраженная сезонность — это "завтра будет так же, как год назад", или "завтра будет так же, как в такой же день недели на прошлой неделе". Или "завтра будет такой же прирост" — то есть позавчера мы продали 10 шоколадок, вчера мы продали 15 шоколадок, сегодня мы продали 20 шоколадок, а завтра, наверное, продадим 25. У этого подхода, очевидно, есть ограничения, то есть, когда нибудь он перестанет работать, но в определенных пределах он работает. И еще хороший бейзлайн, тут его на слайде нет, это скользящее среднее. То есть "завтра будет так же, как в среднем было за последние 7 дней", или 7 дней с поправкой на сезонность по дням недели.
Как быть с сэмплингом во временных рядах? То есть предположим, что у нас есть данные с точностью до секунды, но нам так точно не надо, нам нужны данные за каждые 15 минут. А как мы можем выбрать наши точки данных с нужной нам частотой? Зачастую вот эти вот как раз 15 минут они попадают на участок между двумя точками. То есть предположим, что у нас данные приходят каждые 3 минуты, а мы хотим, чтобы они у нас были каждые 15 минут. Очень часто наш сэмпл будет не кратный 3 минутам. И тогда есть подход такой, что мы можем просто или взять ближайший, то есть сэмпл перед этим, или интерполировать, сгладить между двумя сэмплами.
Зачастую точки бывают с переменным шагом, и тогда нам нужно их пересэмплировать, тоже взять среднее какое-нибудь. Если значения пропущены, мы можем взять среднее или интерполировать. Есть хороший обзор про работу с нерегулярно сэмплированными временными рядами. Но надо заметить, что мы же много лет работали с обработкой сигналов, в которых upsampling и downsampling, скажем, в работе со звуком — это совершенно нормальные явления. И наши time series в этом смысле — точно такой же сигнал, с которым также можно делать upsampling и downsampling. Тут ссылки на статью в Википедии, где разобраны эти подходы.
Временные ряды можно представлять как тексты. Звучит немножко странно, но предположим, что у нас есть курс акции, допустим, и мы его представляем, вот эти телодвижения, которые происходят с курсом акции, как слова — например, "сильно выросло", "слабо выросло", "стоит на месте". А потом учим, например, языковую модель или какой-нибудь анализ тональности или что-нибудь еще. И есть старая статья, она есть в дополнительных материалах, про разные подходы к представлению данных во временных рядах. Несмотря на странность этого подхода, когда мы представляем временные ряды или какие-то последовательности транзакций как тексты, у Воронцова, допустим, аспиранты из его BigARTM очень много делали таких предсказаний — брали модель, предназначенную для текстов, и с ее помощью анализировали музыкальное предпочтение в плейлистах, или какую-то аналитику делали поверх финансовых транзакций.
Кроме временных рядов, к странным данным я отнес бы графовые данные. Графовые данные – это некоторые данные, описывающие отношения между сущностями. То есть у нас в обычных табличных данных есть какая-то сущность и ее атрибуты. А в графовых данных у нас отношения между несколькими сущностями, например, между двумя.
Граф состоит из вершин и ребер. Он может быть ориентированный или неориентированный, то есть у нас может быть симметричное или несимметричное отношение между сущностями. Он может иметь циклы или не иметь. Он может быть взвешенный — в частном случае, это когда у нас на связи между сущностями к ним приписано какое-нибудь число. Например, я люблю яблоки сильнее, чем, допустим, апельсины, а груши сильнее, чем яблоки. И вот на графе между мной и грушей, там, скажем, меньше вес, а, допустим, на яблоке больше вес. Но это частный случай каких-нибудь атрибутов в узлах и ребрах, то есть атрибуты могут быть в узлах графа, а могут быть в ребрах графа. И, в принципе, про графы много есть интересной математики и терминологии.
У нас тут не про графы лекция, но примеры практических графов, которые приходилось анализировать — это, например, цитирование в научных статьях. Некоторые научные статьи ссылаются на другие научные статьи, и вот у нас направленный граф.
Есть ссылки на веб-страницах — это тоже направленный граф, какая-то страница ссылается на какую-то другую страницу, и в этом графе есть циклы.
Коммуникации в социальных сетях. Вася написал Пете, Петя написал Маше, Маша написала Васе. Тут граф может быть как направленный, так и не направленный, в зависимости от того, как мы о нём думаем.
Дорожный граф на карте. То есть, например, у нас одна улица с другой улицей связаны, то есть, они имеют пересечения, на которых можно с одной улицы на другую переехать. И, таким образом, мы можем считать узлом улицу, а ребрами перекрестки. Ну, или более очевидный подход — мы можем считать узлами перекрестки, а ребрами улицы. Дорожный граф широко используется в пространственном анализе, его часто берут из OpenStreetMap, например, где дороги – это линии, считают их ребрами графа.
Маршруты транспорта. То есть, у нас есть некоторые узлы, остановки или транспортные хабы, точки пересадки, и есть некоторые ребра, то есть, перегоны транспорта от остановки к остановке.
Графы бенефициаров организации. То есть, допустим, Вася владеет 10% организации ООО "Рога и Копыта", "Рога и Копыта" владеют 20% ООО "Белое и Пушистое", ООО «Белое и Пушистое» владеет допустим, "Цветмедзагранпоставка". И, чтобы понять, влияет ли Вася конкретно на "Цветмедзагранпоставку", нам нужно построить граф этих самых бенефициаров. Недавно случилось банкротство криптобиржи FTX, и, если бы был в открытом доступе граф ее бенефициаров, в котором явно видно, что она вкладывала деньги в организации, которые вкладывали деньги в нее, которые она потом снова вкладывала в них, то есть, что есть такое накручивание капитализации — если бы инвесторы раньше это видели, наверное, она бы обанкротилась сильно раньше.
Графы денежных потоков — то есть, как деньги идут через страну, через организацию или через отрасль.
И некоторые графы взаимосвязей систем. В медицине очень любят строить, в биоинформатике, графы. Например, в работе щитовидной железы задействовано 8, например, гормонов, и некоторые гормоны тормозят выработку других гормонов, а другие гормоны, наоборот, их потенциируют, и всякий раз, когда мы в эту систему влазим, — допустим, даем человеку гормональный препарат, — система пытается вернуть себя в то состояние, в котором она была до этого. И, не понимая вот этот граф взаимосвязей, мы не сможем лечить сложные болезни. То есть большинство гормональных препаратов, большинство психотропных препаратов, они встраиваются в сложные графы взаимосвязей, не моделируя которые, мы не сможем ни предсказать, ни получить результата.
Где возникают графовые данные? Везде, где у нас есть две и более сущностей в одной записи — клиент купил товар, организация заплатила другой организации, то есть это транзакционные данные — финансы, это данные структуры — биология, химия, это журналы работы — то есть, например, больной пришел на прием к врачу, в регистратуре его записали к терапевту, терапевт его записал к невропатологу, и мы можем представить путь больного по врачам, как путешествие больного по некоторому графу, маршруту.
Вообще многое можно с пользой представить как граф, есть хорошая статья, "Графовый анализ — обзор и области применения", и тут ссылка на слайде с ней.
Как собирать графовые данные? Обычно графовые данные приходят как табличные данные, то есть в сборе они выглядят как таблички. Например, кликстрим, поток событий о переходах пользователей. Данные могут приходить в виде кликстрима, могут приходить в виде потока транзакций. Как правило, в большой системе мы их все сначала складываем в Kafka или в Kinesis или в какой-нибудь аналог.
Как мы работаем с графами? Есть специальные графовые базы данных, а еще графовые операции, то есть графовые запросы, более-менее поддерживаются во всех серьезных реляционных базах данных. Там есть так называемые рекурсивные запросы, которые позволяют сделать запрос, основываясь на результатах предыдущего выполнения этого же самого запроса. И с помощью рекурсивного запроса мы можем вытаскивать графы из обычных табличек.
В MongoDB есть операция Graph Lookup, которая более-менее эффективно позволяет вытаскивать запросы цепочке глубиной, скажем, до 10 из графа. До 10 ребер она эффективно использует индексы, дальше она деградирует немножко в производительности.
Когда говорят о графовых базах данных, всегда вспоминает Neo4j, но Neo4j достаточно дорогая, если вы используете её платную версию, и сильно ограничена, если используете бесплатную.
Есть Apache TinkerPop, такая графовая база данных, и она позволяет работать с большими объемами графовых данных более-менее прилично. Например, тут у нас есть граф из людей и фильмов, то есть есть у нас два кинофильма, Val и Troop Zero, и три пользователя — Алиса, живущая в Техасе, Боб, живущий в Вайоминге, и Кэрол, тоже живущая в Техасе. И нас интересует, много ли людей, живущих в Техасе, любят фильм Troop Zero, понравился ли им фильм. И мы выполняем следующий графовый запрос — ко всем объектам нашей базы данных, к узлам базы данных, которые имеют метку, что это фильм, то есть мы отбираем только синенькие кружочки в данном случае, которые имеют атрибут названия Troop Zero, у нас останется один синенький кружочек, находится в отношении likes с некоторыми узлами, у которых есть атрибут "живут в США в Техасе". И count, посчитать количество — то есть это вот пример графового запроса, который позволяет достаточно сложные вещи вытаскивать из графовой базы данных.
Для анализа графовых данных широко используются нейронные сети. Тут примерно с 2016 года произошла революция, сначала придумали алгоритм DeepWalk, и затем его усовершенствовали в LINE и HARP, и вот тут статьи на слайде есть.
Представим себе самый простой подход, как мы могли бы, допустим, анализировать графы. Предположим, что у нас есть социальная сеть, и в ней есть инфлюенсеры, то есть люди, которые связаны с большим количеством других людей. А есть просто пользователи, которые фактически только на инфлюенсеров и подписаны, ну и на свой ближний круг. Как бы могли отличить от них от других? Например, мы могли бы в каждый узел случайно встать и совершить, например, 100 случайных переходов по ребрам этого графа и посмотреть, насколько далеко бы мы оказались от него. С помощью таких операций мы можем построить эмбеддинг, то есть, например, в среднем мы после 10 переходов оказываемся на расстоянии 3 ребер, после, допустим, 100 переходов мы оказываемся на расстоянии 6 ребер, и вот эта гистограмма, на каком расстоянии мы оказываемся после какого-то количества случайных вблужданий, может нам дать информацию о том, инфлюенсер это или просто вот такой рядовой пользователь, который никому не интересен.
В PapersWithCode есть отдельный раздел про граф-эмбеддинги и пара хороших инструментов, это Deep Graph Library, она более-менее tool agnostic, то есть, она может работать как с Pytorch, так с TensorFlow, MXNet, это библиотека для графовых операций, для работы с графами, с графовыми данными. И есть отдельно Pytorch Geometric, которая хорошо позволяет работать с графами, новая библиотека, очень мне нравится.
Что можно делать с графами? Во-первых, можно использовать графовые эмбеддинги как признаки в моделях. То есть, мы, допустим, насчитали для каждого узла некоторые эмбеддинги, и потом мы можем говорить, что — ага, это инфлюенсер, а это просто пользователь, это коррупционер, а это честный чиновник, это отмывание денег, а это нормальная хорошая операция. Мы можем предсказывать новые ребра графа, то есть, новые ребра графа в случае соцсетей — это, допустим, предсказание связи, что вы могли бы подружиться с вот этим человеком, возможно, вас заинтересует подписка на вот этого пользователя.
Кроме этого, мы можем подгружать в фоновом режиме страницу для просмотра, то есть, допустим, у вас есть банковское приложение, вы зашли на какую-то страницу, и более-менее понятно, на какую страницу, на какой узел графа вы перейдете дальше. То есть, мы сделали предсказание, и давайте мы сразу подгрузим данные для этой страницы, чтобы ваш пользовательский опыт был такой бесшовный — вы такие нажали, а оно сразу готово уже.
Также мы можем предсказывать исчезновение ребер, то есть, например, отказ от использования сервиса — ага, этот пользователь от этой услуги откажется, это ребро у нас пропадет.
Мы можем искать кратчайшие пути, можем искать устойчивые подграфы. Поиск устойчивых подграфов, то есть, повторяющихся операций — это важная задача в, допустим, process mining или robot process automation. Это когда у нас есть устаревшее программное обеспечение, к которому нет API, а мы к его веб-интерфейсу пишем робота, который кликает на кнопки, вводит текст в поля, и в результате, как бы, программное обеспечение, которое не имеет API — мы для него искусственно сверху API навернули. Так вот, какие операции пользователей нам надо оборачивать в API — это мы как раз можем выяснить, проанализировав устойчивые подграфы в их действиях. То есть, запросто может быть, что каждое утро пользователь заходит и ровно в определенном порядке нажимает 30 кнопок и совершенно механически передвигает 30 переключателей, мы видим этот подграф в его графе транзакций и автоматизируем его, делаем это все одной операцией.
Process mining — это в принципе история про анализ графов операций. Предположим, что у нас есть некоторые журналы операций — пользователь приходит, звонит нашему менеджеру, просит подобрать продукт, менеджер подбирает продукт, отзванивается ему в ответ, пользователь говорит, что ему что-то понравилось, менеджер отправляет коммерческое предложение, пользователь оплачивает, все вот эти операции у нас фиксируются и мы можем посмотреть, что смотрите — у нас с момента этой операции до вот этой проходит в среднем столько-то времени, то есть у нас есть вес на графе, или здесь у нас возникает петля после того, как пользователю выставили счет, а он снова обратился к менеджеру с просьбой подобрать другой какой-то продукт.
Анализируя графы процессов, мы можем выявлять неоптимальности в графах, мы можем как-то оптимизировать наши процессы и для каждого конкретного процесса можем предсказать, чем этот процесс кончится — то есть купит или не купит этот пользователь, судя по его поведению.
Дополнительные материалы: