Привет, Хабр! На связи команда матчинга и группировки из ecom.tech. Наша команда решает задачи поиска, группировки и сортировки товаров с помощью алгоритмов машинного обучения. Например, такие алгоритмы объединяют товары от разных продавцов в одной карточке, что дает покупателям возможность сэкономить время и деньги.
Сегодня мы расскажем, как исследовали алгоритмы community detection для группировки товаров, с какими проблемами столкнулись и при чём тут матчинг. Статья будет полезна всем, кто работает с большими объемами данных и ищет способы оптимизировать операции с этими данными. Поехали!
Группируем бесконечность
В отличие от магазина или рынка современный маркетплейс имеет бесконечную полку товаров. И, если в масштабах оффлайн торговли количество товаров ограничено вместимостью помещения, то в интернет пространство можно вместить всё, что душе угодно. И даже немного больше.
Однако тут возникает соответствующая проблема – как просмотреть, завести, систематизировать и поддерживать актуальным фактически «бесконечный» ассортимент? Особенно, если одна позиция представлена в нескольких вариациях. Обычные дубли (когда на один товар одного продавца заведено несколько карточек) просто удаляются. Но как быть, если один и тот же товар приезжает к покупателям трудами нескольких поставщиков и описан разными терминами? Например, серебристый playstation может быть заведен в базу как «консоль», «плейстейшн» и просто «приставка». Не говоря уже о богатстве синонимов к слову «серебристый».
Так появляется задача объединения в группы одинаковых (или максимально похожих) товаров, которые затем присоединяются к одной карточке товара. Группировка полезна:
Для продавцов в аналитических сервисах. Имея данные о товарах-аналогах и предложениях конкурентов, продавец может эффективнее выстраивать стратегию управления собственным продуктом. Например, корректировать ценообразование, увеличивать доступность через расширение складской сети, улучшать инфомодель и контент.
Для покупателей в увеличении вариантов выбора. Если пользователь ищет какой-то определенный товар, сервис может предложить ему несколько альтернатив по цене/доступности этого товара, а также рекомендации других товаров, выстроенные на базе всей группы.
При чем тут матчинг
Предположим, у нас есть маркетплейс с каким-то объемом товаров. Каждый из товаров имеет определенный набор характеристик: фотографию, название, описание, цену, отзывы. На основе этих характеристик и люди, и модели сравнивают/выбирают товары. Конечно, каждый по-своему. Но представим, что нам нужно не просто сравнить, но ещё и рассортировать эти товары на группы – табуретки к табуреткам, а бананы к бананам. Для этого нужно:
Сопоставить набор характеристик каждого товара со всеми остальными товарами на этом маркетплейсе и для каждого из товаров найти какое-то количество кандидатов на «похожесть».
Сформировать критерий отбора и с его помощью выбрать среди полученных кандидатов наиболее достоверные (их может получиться как пара десятков, так и ни одного).
Объединить отобранные «достоверные» пары товар-кандидат в группы.
За первый пункт этого списка отвечает матчинг. О том, как он работает и какие модели применяются, мы уже писали в серии статей здесь, здесь и здесь. Даже если вы хорошо знакомы с понятием матчинга – рекомендуем заглянуть.
Для тех, кто не собирается заглядывать, расскажем о задаче продуктового матчинга кратко – это сопоставление между собой характеристик товаров с целью найти наиболее похожие, а желательно идентичные. Нам в этом помогает система, состоящая из картиночной модели, текстового bi-encoder в связке с faiss для первичного подбора кандидатов, cross-encoder в роли реранжировщика текстов и кэтбуста для финальной оценки похожести кандидатов (с текстами, картинками, ценами и еще несколькими табличными признаками). Итогом становится набор пар товаров-кандидатов из существующей базы для каждого товара-запроса. Откуда на финальном шаге мы можем выбрать (или не выбрать) матч для каждого товара-запроса. Как правило, матчинг используется для поиска на площадках-конкурентах, и в качестве запроса выступает товар со сторонней площадки, а в качестве кандидатов – товары в нашей базе.
Подбор кандидатов для группировки идет по тому же сценарию с одним важным различием – источником товаров-запросов и товаров-кандидатов выступает одна и та же выборка (например, база товаров нашего маркетплейса). И если нам нужно сгруппировать какую-то выборку товаров, мы запускаем процесс матчинга этой выборки «самой на себя».
Дальше идёт предварительная фильтрация. Как и в матчинге, каждая из полученных пар имеет характеристику в виде скора финальной модели. И для следующего этапа мы оставляем только те пары, скор которых превышает некую заранее подобранную пороговую величину. Если скор выше неё – мы считаем найденную пару уверенным матчем.
Тайные сообщества товаров
Итак, у нас есть выборка товаров, часть из которых мы связали в пары с некоторым весом. Как правило, эти взаимосвязи оказываются очень похожи на… социальные сети. А взаимодействует с В, а B взаимодействует еще и с C, D, E и еще десятком других товаров (людей). А общается с E, но не пересекается с C и так далее до бесконечности. Кого исключить, а кого оставить в этом тесном кругу – на первый взгляд совершенно непонятно. Но на помощь приходит задача кластеризации на графах.
Кластеризация на графах наиболее известна как задача community detection (CD) – поиск в структуре графа сплоченных групп узлов, обладающих сильными внутригрупповыми и относительно слабыми межгрупповыми связями. Наиболее часто она возникает в контексте различных сетевых сообществ. И за последние 15-20 лет для её решения было разработано немало методов и подходов, которые успешно работают не только для соцсетей, но и в задачах биологии, финансового анализа, поиска информации – везде, где нужно разбить графовую структуру на составляющие.
Модулярности, вероятности, спектральные разбиения
Попробуем немного систематизировать информацию о community detection и вкратце расскажем про алгоритмы, основанные на понятии модулярности, а также, использующие близкие к ней метрики, label propagation, спектральные и вероятностные методы.
Modularity (как оценка качества разбиения графа на сообщества) была введена Гирваном и Ньюменом ещё в 2002 году. Она сравнивает, насколько относительная плотность внутри сообществ выше при данном разбиении графа, чем при некотором случайном его разбиении. В своем «первозданном» виде алгоритм обладает высокой вычислительной сложностью и не подходит для больших (> 1000 узлов) графов. Но именно этот подход заложил основу для последующих исследований.
Здесь mc – количество связей внутри комьюнити с, ec – количество внешних связей этого комьюнити, m – полное количество связей в сети. Вычитаемое внутри скобки характеризует количество связей, которое могло бы быть у сообщества с в некотором случайном графе (т.е. в графе, связи внутри которого задаются рандомно и не имеют структуры). Понятно, что аналитически максимизировать эту функцию мы не можем, и поиск наибольшего значения модулярности требует перебора всех вариантов в поиске того, при котором относительное число связей внутри сообществ будет максимально далеко от случайного (1 – идеальное разбиение, 0 – случайное разбиение, -1 – разбиение «хуже», чем случайное). Стоит добавить, что формула не предполагает учёт качества связей между узлами и работает только с невзвешенными графами (ребро либо есть, либо нет) – однако в реализации последующих алгоритмов, использующих модулярность, эта возможность предусмотрена.
Как работает алгоритм:
Вычисляют ребро с наибольшей степенью посредничества (т.е. ребро, через которое проходит больше всего кратчайших путей в графе).
Это ребро удаляют.
Считают модулярность.
Повторяют шаги 1-3 до тех пор, пока в графе не останется рёбер.
Выбирают конфигурацию с наибольшей модулярностью.
Есть более прагматичные варианты, которые завершаются не с последним удаленным ребром, а в случае не-увеличения модулярности (когда она осталась прежней или стала меньше).
Использование модулярности в качестве оптимизационной величины сопряжено с так называемой «проблемой разрешения»: алгоритм «не видит» сообщества, размер которых меньше определенного порога. Даже если это сообщества с полным набором внутренних связей и минимумом внешних. Порог зависит от общего количества ребер в графе, поэтому в достаточно больших графах априори невозможно сказать, является ли каждое комьюнити действительно одним модулем или кластером более мелких.
Алгоритм Лувена
Метод Лувена (Louvain – не фамилия, а город в Бельгии, в котором работает команда разработчиков метода) один из наиболее известных и эффективных подходов к оптимизации модулярности и выявлению сообществ. В противоположность алгоритму Гирвана-Ньюмена, поиск сообществ ведётся не по пути разбиения графа, а наоборот, путем объединения узлов. Это позволяет достичь скорости и производительности достаточной для работы на графах с десятками миллионов узлов (152 минуты на кластеризацию графа в 118 млн. узлов).
Как работает алгоритм:
1. На начальном этапе назначаем каждому узлу свое сообщество.
2. Для каждого i-го узла рассматриваем всех его j соседей и оцениваем выигрыш модулярности от перемещения i в сообщество j. Если выигрыш положителен, перемещаем.
3. Процесс происходит многократно и последовательно для всех узлов до тех пор, пока есть возможности к максимизации модулярности.
4. Когда повысить модулярность уже нельзя, полученные сообщества объединяются в мета-узлы (веса связей суммируются) и шаги 1-3 повторяются заново.
5. Процесс объединения и укрупнения может происходить несколько раз, пока не будет достигнута конфигурация, при которой дальнейшее повышение модульности невозможно.
Одна из существенных проблем алгоритма Лувена – склонность к образованию внутренне несвязанных сообществ. Например, связующий узел был переоптимизирован в другое сообщество, а в оставшемся образуются две плохо связанные части (картинка). Также нерешенной остаётся проблема предела разрешения модулярности – часто более мелкие сообщества объединяются в одно. Но несмотря на все сложности, алгоритм Лувена является одним из наиболее часто используемых при кластеризации графов. И, если вы не знаете, с чего начать – начинать стоит с него.
Многие алгоритмы, описанные в литературе, базируются на алгоритме Лувена с различными доработками. Например, оптимизацией процесса выбора узлов для перемещения в соседнее сообщество, стартового разбиения или пересмотра промежуточных результатов.
Частично упомянутые проблемы были решены с появлением алгоритма Лейдена: его авторы ввели такой шаг, как пересмотр полученных сообществ (refine) после очередного перемещения узлов. Кроме того, для ускорения процесса проводится обход не всех узлов, а только тех, которые претерпевали изменения на последнем шаге.
Label propagation algorithm (LPA)
Алгоритм похож на KNN на графах. Сначала каждому узлу присваивается своё сообщество и затем алгоритм итеративно находит структуру графа на основании обновления меток вершин в зависимости от наиболее часто встречающихся меток среди соседей (при паритете выбор случаен).
LPA может быть как синхронным, так и асинхронным. В синхронной модели метка (т.е. номер сообщества) для каждой вершины на шаге i вычисляется на основе меток соседей на шаге i − 1 (т.е. обновление происходит сразу по всем узлам и зависит от предыдущего состояния). Асинхронный алгоритм выполняет обновление меток на основе текущего состояния i, последовательно по графу. Синхронный алгоритм прост в реализации и легко распараллеливается, поскольку в рамках одного шага нет зависимостей между метками. Но синхронное обновление может привести к так называемой осцилляции меток - когда две группы узлов на каждом шаге как бы меняются метками и алгоритм не может сойтись.
Чаще всего причиной осцилляции в LPA является двудольный или циклический компонент. Двудольный – это когда граф (или его компонент) можно разделить на две части так, что все ребра будут соединять узлы одного множества с узлами другого.
Эта проблема решается в асинхронных сетях, но алгоритм становится нестабильным, т.к. последовательность обновления выбирается случайно в каждой итерации и в каждом запуске результат может отличаться. Также асинхронный LPA склонен к созданию очень больших сообществ.
Алгоритм, которым мы пользовались в рамках нашего исследования – полусинхронный (semi-asynchronic). На первом его этапе выполняется «раскрашивание» – каждому узлу присваивается некая метка (цвет) так, чтобы ни одна из двух соседних вершин не была раскрашена одинаково. На втором этапе метки распространяются поочередно для каждого «цвета» – например, все узлы цвета А обновляются в зависимости от меток ближайших соседей (если таких цветов несколько, то обновление определяется случайным образом), затем обновляются узлы цвета В и так далее. Этап распространения меток повторяется пока алгоритм не сойдётся или не закончится заданное число шагов.
Формально LPA не является основанным на модулярности алгоритмом, но в литературе встречается использование модулярности для оценки качества получаемых на каждом этапе сообществ.
Спектральные методы
Это алгоритмы, базирующиеся на спектральном разложении матриц (т.е. разложении по собственным векторам).
Как работает алгоритм:
Строится матрица подобия, которая фиксирует взаимосвязи между узлами (обычно это матрица смежности, но возможны варианты).
Из матрицы смежности вычисляется матрица Кирхгофа, в которой на пересечении i-ой строки и i-го столбца стоит валентность вершины с номером i (т.е. количество ребер, для которых вершина является концом/началом). В ячейках ij при наличии ребра стоит -1, при отсутствии - 0.
Для полученной матрицы Кирхгофа проводят поиск собственных значений и собственных векторов (их количество зависит от предполагаемого количества сообществ).
Вектора кластеризуются, например с помощью обычного k-means.
Спектральные методы хорошо работают для обнаружения сообществ со сложными топологическими структурами и для разных структур сети - разреженных, плотных, несвязных. Однако применение метода предполагает наличие некой априорной информации об анализируемой структуре. А также сопряжено с трудоемким вычислением спектрального разложения, которые в среднем требует O(n^3) операций, где nxn-размер матрицы.
Вероятностные методы
Метод случайных блужданий можно отнести к вероятностным. Основная его идея в том, что за счёт более плотных связей внутри графа и менее плотных снаружи вероятность остаться внутри одного сообщества при случайном перемещении по ребрам заметно выше, чем выйти из него. Для поиска выбирается некоторое небольшое количество шагов (обычно от 3 до 8), на основе матрицы смежности графа вводится матрица вероятности перехода из узла i в узел j за выбранное количество шагов и затем на ее основе выделяются сообщества (высокая вероятность перехода – одно сообщество, низкая – разные).
Infomap – ещё один из популярных вероятностных методов. Также использует случайные блуждания, но гораздо более продолжительные, кодируя перемещения «случайного пользователя» с помощью кодов Хаффмана. Так мы знаем, что в большинстве реальных сетей существуют области, в которых случайный посетитель, обычно остаётся надолго, а перемещения между такими областями относительно редки. Это позволяет комбинаторно объединять их в коды Хаффмана, используя префиксный код для каждого «региона» и уникальные коды для его внутренних узлов, при этом повторно используя эти коды в других регионах. Это немного напоминает создание карт городов на основании блужданий. Объединяя улицы в один город мы можем называть их точно так же, как и в соседнем, используя для разделения префикс в виде названия города.
В целом, в деле community detection в ход идут многочисленные модели из других областей знаний – скрытые марковские модели, модель спиновых стекол, генетические алгоритмы, модели взаимодействия несмешиваемых жидких сред, топологические подходы, использующие в качестве базы мат аппарат для описания искривления многомерных пространств. Естественно, используются и нейросети. Наиболее полный и свежий обзор, попавшийся на момент написания статьи, лежит вот здесь.
Вот так сюрприз
Есть целое семейство методов, в которых авторы берут за основу алгоритм Лувена, а в качестве функции оптимизации используют не модулярность в чистом виде, а некоторые ее приближения, основанные на том же принципе сравнения внутренней и внешней плотности сообществ. Одно из них носит неожиданное название surprise, а именно «невероятность» найти такое распределение узлов и связей в некотором случайном графе. Его максимизация позволяет выбрать такое разбиение на комьюнити, которое даст максимальную долю взаимодействий внутри кластера и минимальную долю взаимодействий между ними.
Математически это выражается как:
Где D(q || <q>) – бинарная дивергенция Кульбака-Лейблера. Значения q и <q> будет проще описать, опираясь на таблицу ниже. Первый из этих параметров q – описывает свойства полученного разбиения и равен количеству ребер, попавших внутрь сообществ к общему количеству ребер в графе. Величина <q> характеризует ожидаемую долю внутренних ребер при таком же разбиении для полного графа. Таким образом, алгоритм балансирует между попыткой включить максимум ребер внутрь сообществ (тогда q будет максимально) и разбить структуру на минимальные сообщества (тогда <q> будет наименьшим).
Использование surprise в качестве функции оптимизации фактически решает проблему разрешения. С другой стороны, алгоритм склонен находить подструктуры в больших монолитных сообществах. И если модулярность, как правило, недооценивает количество сообществ, то surprise чаще ошибается в сторону переоценки.
Еще одна особенность метода в том, что при кластеризации сообществ в графе с полными связями он будет работать неправильно (т.е. ДКЛ будет равна нулю - это граничный случай и авторы указывают на него).
Что использовать или постановка задачи
Итак, какие алгоритмы интересны в контексте нашей задачи?
1) Производительные, поскольку речь идет о миллионах товаров.
2) Работающие со взвешенными графами. Это не строгое условие, но из этапа матчинга у нас есть такая важная составляющая, как веса, т.к. именно вес связи дает нам понимание, насколько связь крепка, а его использование в CD алгоритме должно повысить точность результата.
3) Обнаруживающие небольшие сообщества в больших структурах.
4) Искомое количество сообществ неизвестно даже примерно (здесь мы, фактически, отметаем группу спектральных методов).
5) Работающие с несвязанными графами, когда полученная структура уже состоит из больших раздельных кластеров, которые надо разбить на кластера поменьше (и здесь, вероятно, не очень эффективными окажутся методы со случайными блужданиями).
Что мы использовали:
Ради интереса мы попробовали и несколько других алгоритмов, но результаты оказались менее впечатляющими с точки зрения метрик и/или быстродействия.
Про библиотеку
Для работы будем использовать библиотеку CDLib, поддерживаемый пакет Python, позволяющий извлекать сообщества из сложных сетей, сравнивать их и оценивать. Библиотека принимает на вход объекты networkx/ igraph и содержит несколько десятков стандартизированных реализаций CD алгоритмов для кластеризации изолированных, перекрывающихся и нечетких сообществ, а также инструменты для анализа результатов, сравнения метрик (например, модулярности) и даже отслеживания динамики изменения.
В целом, является очень удобным инструментов для исследователя. Из минусов можно отметить довольно скудную документацию (правда, к каждому методу приведены ссылки, которые можно исследовать самостоятельно), а также низкую производительность и высокое потребление памяти для некоторых алгоритмов.
Про метрики
В нашем случае бизнес-задача состояла в том, чтобы группировать товары с максимальной точностью (precision 97% и выше) и получить при этом максимально возможный recall. Метрики, которые мы используем для своей внутренней оценки, базируются на матрицах смежности истинного разбиения на группы и предсказанного. Из их сравнения вычисляются, соответственно, true positive (1 и в предсказании, и в истинной матрице), false positive (1 в предсказании, 0 в истинной матрице) и false negative (1 в истинной матрице, и 0 в предсказании). Итоговые precision и recall считаются по классическим формулам для этих величин.
Результаты и анализ
Для расчетов и подбора порогов мы использовали выборку из 6 млн. товаров Мегамаркета. Примерно такой же объем был и у тестовой выборки. Для каждого товара мы использовали такие характеристики: изображение, название, описание, атрибуты, категории и цену.
При достигнутой точности 0.97 наибольший recall показал метод surprise_communitiy. В таблице приведено значение modularity (вычисляется при помощи CDLib на основании полученного разбиения), однако эта величина указана лишь справочно, так как оптимизация в методах ведётся по разным величинам.
О порогах, фильтрах и кратных рёбрах
Заметную роль в полученном результате играет качество предварительной фильтрации. Вспомним начало статьи. Часть, отвечающая за поиск кандидатов, выдает top N (не меньше!) вариантов для каждого товара. Часть из них заведомо будет ложно-положительной, а если всё это просто закинуть в алгоритм community detection – качество разбиения будет не самым лучшим. Не поможет даже учёт весов. При этом даже минимальной отсечки по порогу иногда бывает достаточно, чтобы заметно повысить качество кластеризации.
Но «минимальной отсечки» для требуемой точности 0.97 оказывается недостаточно. При изучении влияния false positive на качество разбиения алгоритмом surprise community мы обратили внимание, что при наличии false positive связей, алгоритм склонен укрупнять группы. Например, наличие «случайных» узлов, связанных с двумя группами близких товаров, может приводить к слиянию этих групп. А без них группы хорошо разделяются, несмотря на перекрестные ребра. При наличии связующего false positive между несколькими небольшими группами, алгоритм может объединять эти группы в одну более крупную или формировать сообщество с центром в fp, «оторвав» часть истинных групп.
Кроме того, даже среди высоких скоров встречаются ложные матчи. Например, когда продавец слово в слово заполняет карточки товара с одним небольшим различием.
Достижение требуемой точности потребовало от нас скрупулезной работы с предварительной фильтрацией. Мы учитываем несколько скоров, включая скор картиночной модели и текстового реранжировщика, а также добавляем фильтрацию по специфическим атрибутам товаров. Обратная сторона этой медали – большое количество настроек и плохая гибкость модели к изменениям товарного ассортимента.
В попытках упростить этот этап пайплайна, мы попробовали переложить часть нагрузки по принятию решений на графовый алгоритм. Работ, в которых авторы рассматривают кратные ребра в community detection неожиданно не обнаружилось вообще. В тех случаях, где связь между узлами характеризуется несколькими весами решение сводится, как правило, к получению некой суперпозиции этих весов. Мы сделали следующее:
после нестрогой фильтрации подали кратные ребра (т.е. несколько весов для одного ребра) в алгоритм surprise_community,
объединили веса с помощью “суммирующей” функции, подобрали порог по этому весу и использовали один вес в surprise_community.
Использование кратных ребер при кластеризации не дало ни ухудшения метрик, ни статистически значимого прироста.
Во втором варианте в качестве «суммирующей» функции мы использовали арифметическое среднее и гармоническое среднее промежуточных скоров пайплайна (скор похожести текстов, скор похожести изображений). Простую сумму мы также попробовали, но ввиду отсутствия картинок и картиночного скора для некоторых пар, этот вариант проигрывает по охвату.
Среднее арифметическое и гармоническое среднее дали прирост охвата на 1,6% и 1,8% соответственно, однако на дальнейших тестах среднее оказалось более устойчиво и показало прирост охвата до 5%. И хотя прирост кажется скромным, выигрыш от использования единого веса вместо набора весов в большей гибкости и упрощении калибровки.
При качественно выполненной фильтрации между группами фактически нет ребер и алгоритм может объединять узлы с точностью близкой к 100%
Алгоритм хорошо собирает в группы похожие товары. Хоть зеленая и желтая группа представляют, фактически, один товар, в рамках поставленной задачи это разные группы - т.к. одна имеет качественное описание со множеством атрибутов, а вторая - только название. При менее строгом подходе две этих группы будут объединены.
Итак, мы посмотрели, на какие шаги раскладывается задача группировки товаров и какие методы можно использовать непосредственно на этапе группировки. Надеемся, эта статья окажется полезной и тем, кто впервые сталкивается с community detection, и тем, кто ищет для себя новые подходы. Однако стоит помнить, что во многом применяемые инструменты зависят от постановки и специфики конкретной бизнес-задачи. Вполне вероятно, что при других требованиях, условиях и данных эффективными окажутся другие алгоритмы и подходы. Каждая задача имеет свое решение и мы желаем вам найти свой оптимум и без всяких surprise.