В октябре 2021 года наша Школа Больших Данных запустила новый курс для дата-аналитиков и разработчиков распределенных приложений про решение реальных бизнес-задач средствами графовых вычислений в популярных фреймворках Big Data. Читайте далее, почему графовые алгоритмы так хороши для выявления мошеннических схем в страховании и финансовых операциях, как определить интересы пользователя в рекомендательных системах и оптимизировать транспортные маршруты с помощью Apache Spark GraphX и GraphFrames, а также зачем использовать для этого Node4j, Cassandra и другие графовые NoSQL-СУБД.
Что такое графовая аналитика: типовые кейсы и базовые понятия
Математические структуры и алгоритмы окружают нас повсюду, причем не только в сложных научных задачах, но и ежедневных жизненных ситуациях. Например, проложить наиболее короткий маршрут от дома до офиса или найти друзей в соцсетях. Это – лишь пара примеров реализации графовых алгоритмов, которые относятся к дискретной математике и широко применяются во множестве бизнес-задач:
- выявление сообществ и определение интересов потребителей для формирования персональных маркетинговых предложений;
- разработка рекомендательных систем для интернет-магазинов и контент-сайтах;
- обнаружение подозрительных финансовых транзакций;
- выявление мошеннических схем в банковских операциях и страховании имущества;
- интеллектуальная обработка текстов – тематическое моделирование, кластеризация документов и извлечение смысла из данных;
- расчет рейтинга инфлюенсеров – популярных пользователей соцсетей и их постов в соцсетях;
- поиск пропавших людей и подозреваемых через анализ сети их знакомых;
- оптимизация транспортных маршрутов и другие логистические задачи – поиск кратчайшего, самого быстрого или самого дешевого пути.
Математически граф состоит из вершин, связанных друг с другом ребрами. Вершины представляют собой некоторые объекты, отношения между которыми показывают ребра. Например, пользователь соцсети – это вершина графа, а его отношения с другими пользователями (друг, коллега, родственник и пр.) – это ребра. Каждое ребро может иметь вес – число, которое описывает стоимость, емкость, длину или другую характеристику отношения между вершинами. Таким образом, бизнес-задача оптимизации маршрута с помощью графовых алгоритмов сводится к определению метрики, которую нужно улучшить (стоимость, длина и т.д.) и выявлению кратчайшего пути от начальной вершины графа к конечной через продвижение по его ребрам.
Подробнее о некоторых прикладных кейсах применения графовых алгоритмов в реальных бизнес-приложениях читайте наши статьи в блоге Школы Больших Данных:
- Умный антифрод: как Big Data и Machine Learning защищают ваши деньги
- Что такое AML или Big Data и Machine Learning против отмывания денег
- Big Data и Machine Learning против мошенничеств в сфере страхования: 7 реальных кейсов
Технологии Big Data для графовой аналитики
В аналитике больших данных обработка графа сводится к его обходу для поиска определенных узлов, соответствующих нужным шаблонам, поиску связанных узлов и отношений. Сегодня для этого активно используются специальные базы данных и вычислительные технологии, ориентированные именно на графовую обработку данных. В частности, в NoSQL-СУБД графовые хранилища выделяют в отдельную категорию, оптимизированную для хранения структур данных в виде графов, например, InfoGrid, Neo4j, Amazon Neptune, OrientDB, AllegroGraph, Blazegraph, InfiniteGraph, FlockDB, Titan, ArangoDB. В таких базах данных ребра графа являются хранимыми, поэтому его обход не требует дополнительных вычислений вместо соединения таблиц через JOIN в SQL. Чаще всего графовые СУБД поддерживают ACID-требования к обработке транзакций и специализированные языки запросов: Gremlin, Cypher, SPARQL, GraphQL и пр.
Из вычислительных фреймворков для задач графовой аналитики в области Big Data сегодня чаще всего используются модули GraphX и GraphFrames в Apache Spark, Gelly в Apache Flink и GraphLab. Еще применяются генераторы графов: Cycle Graph, Grid Graph, Hypercube Graph, Path Graph и Star Graph. А для визуализации закономерностей в основе отношений между объектами графа есть специальные средства типа D3.js, Linkurious и GraphLab Canvas.
Практически в любом инструменте графовой аналитики используется парадигма Pregel – наиболее популярная реализация вершинной обработки графов. Наименование этого подхода расшифровывается как сокращение от «Parallel Graph Google» и происходит от названия реки в Калининграде, бывшем немецком Кёнисберге, который считается родиной самой знаменитой транспортная задачи на графах про маршрут по 7 мостам. Именно Pregel лежит в основе главного поискового алгоритма Google – ранжирование веб-страниц (PageRank). А реализация этого подхода в Apache Giraph помогла Facebook за несколько минут обработать около триллиона ребер пользовательских графов на небольшом кластере из 200 узлов.
Подробнее о технических особенностях использования парадигмы Pregel в Apache Spark читайте в наших статьях на блоге Школы Больших Данных:
- Графовая аналитика больших данных с Apache Spark GraphX: что такое Pregel
- Графовая аналитика больших данных с Apache Spark: GraphX и GraphFrames
А освоить практическое применение графовых алгоритмов в бизнес-приложениях, чтобы создавать собственные системы аналитики Big Data, вам помогут краткосрочные курсы обучения и повышения квалификации ИТ-специалистов в Школе Больших Данных нашего УЦ «Коммерсант»:
Всего за несколько дней интенсивной работы вы узнаете всю необходимую теорию про основы графовой обработки больших данных, познакомитесь с современными алгоритмами и технологиями хранения, анализа и визуализации графов. А также под руководством опытного преподавателя разработаете собственное приложение для решения конкретной бизнес-задачи.
До встречи на занятиях!