Мы команда data science Ozon fresh. В этой статье мы расскажем об одной из наших задач – алгоритме, который помогает управлять нашим огромным ассортиментом.

Ozon fresh — это сервис быстрой доставки продуктов, бакалеи, бытовой техники, электроники и других товаров. В нашем ассортименте более 35 000 уникальных позиций (готовая еда, мясо, рыба, фрукты, овощи, товары для гигиены и многое другое). Специфика Ozon fresh заключается в мини-складах, где хранятся товары. Они доставляются клиентам в радиусе нескольких километров. 

Управление таким количеством позиций требует много человеческих и технологических ресурсов. У нас этим занимаются более 30 человек. Для упрощения работы мы используем различные группировки товарных позиций. Самая популярная — иерархическая четырёхуровневая группировка (далее мы будем называть её «категорийное дерево»).

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

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

• SKU, товар, товарная позиция — уникальный товар с уникальным идентификатором.

• Экземпляр товара — конкретная единица/штука, находящаяся на полке на складе.

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

• Категорийное дерево — иерархическая структура ассортимента для управления им.

Пример использования терминологии 

SKU — яблоки сезонные, садовые, 1 кг

На складе может быть десять разных упаковок с надписью «Яблоки сезонные, садовые, 1 кг»,

Категорийное дерево выглядит так: 

Как мы жили раньше

Историческая справка о том, как обычно происходит формирование категорийного дерева.

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

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

Когда культура ритейла только формировалась, категорийные деревья строились на базе CDT (Customer Decision Tree):

1. Собирались фокус-группы покупателей. 

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

3. На основании результатов формировались группы потребностей пользователей.

Пример: 

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

И как раз здесь возникает проблема: у каждого человека разная экспертиза и разное видение своей категории. Бывают ситуации, когда в компанию приходит новый категорийный менеджер и перестраивает категорийное дерево. Кроме того, есть много внешних факторов, которые не позволяют зафиксировать структуру дерева раз и навсегда (или хотя бы на долгое время). А ещё некоторые товары относятся к нескольким категориям сразу. Например, банку тушёнки можно отнести как к категории «Мясо», так и к категории «Консервы».

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

Муки поиска

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

Мы решили подойти к этому через определение товаров-аналогов.

Товар-аналог (иногда используют термин «товар-заменитель») — это товар со схожими свойствами. Если нужного покупателю товара нет в наличии, то он с большой вероятностью возьмёт товар-аналог.

Для себя мы сформулировали задачу так: 

1. Рассчитать степень аналогичности товаров между собой

2. Объединить в группы товары с высокой степенью аналогичности.

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

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

• у каждой категории свои наборы атрибутов, и их сложно учесть автоматически;

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

Этот вариант нам не подходил из-за сильного влияния человеческого фактора.

В качестве первой итерации мы использовали подход из статьи. В ней описан алгоритм автоматического построения CDT (customer decision tree) для food retail.

Для каждой пары товаров на основе истории чеков рассчитывается коэффициент похожести (The Yule’s Q coefficient) (в нашей терминологии это степень аналогичности) по формуле:

, где 

a — количество чеков, в которых не было ни одного товара из пары, 

b — количество чеков, в которых был только первый товар из пары, 

c — количество чеков, в которых был только второй товар из пары, 

d — количество чеков, в которых были оба товара из пары. 

После этого выполняется иерархическая кластеризация и строится дендрограмма на дефолтных параметрах для метода scipy.cluster.hierarchy.dendrogram.

Авторы статьи не ставят перед собой цели нахождения бакетов — они строят CDT. Но из-за того, что используемый ими метод раскрашивает близкие товары в один цвет, выглядит это так, как нам нужно:

Подход выглядит вполне достойно, но на наших данных он не сработал ???? Получившиеся бакеты оказались нелогичными. Мы и коллеги — категорийные менеджеры — не всегда могли интерпретировать полученное разбиение. В один бакет попадали непохожие товары, а очень похожие — наоборот, не объединялись в бакет. Кроме того, в итоговом разбиении было много выбросов.

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

В итоге мы получили по дендрограмме (а-ля CDT) для каждой категории четвёртого уровня (самой мелкой в нашем категорийном дереве),

Рассмотрим на примере категории «Яйцо куриное» (цены указаны на момент расчёта): 

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

Этот подход показался нам перспективным. Ниже рассмотрим его подробнее.

Мы уже видим, что выделяются группы товаров, которые можно назвать бакетами. Но остаётся вопрос: «Где провести границу?». Для примера на рисунке вертикальными разноцветными пунктирными линиями обозначено четыре порога, которые дадут нам два, три, четыре и пять бакетов соответственно. И, даже если мы выберем какое-то оптимальное пороговое значение для одной категории, оно, скорее всего, не подойдёт для других, так как там будут другие расстояния между товарами в векторном пространстве.

Мы придумали такие варианты выбора оптимального порога:

• Экспертно определить необходимое количество бакетов в каждой категории и подобрать порог таким образом, чтобы получить это число.

• Собрать дата-фрейм из атрибутов всех товаров и перебором для разных порогов решить задачу многоклассовой классификации через DecisionTreeClassifier (не путать с CDT). Выбрать тот порог, в котором получилось наименее глубокое дерево или дерево с наименьшим количеством листьев.

• Собрать дата-фрейм из атрибутов, так же перебрать пороговые значения и для каждого порога посчитать какую-нибудь метрику кластеризации, которая не требует истинного разбиения на классы, например calinski_harabasz_score, davies_bouldin_score или silhouette_score.

На самом деле их больше — это только те варианты, которые мы попробовали в рамках первого подхода. Если у вас есть другие идеи, поделитесь ими в комментариях ????

Резюмируя, итоговый пайплайн у нас получился такой:

1. Расчёт матрицы скоров аналогичности (как в статье).

2. Построение CDT для каждой категории товаров (на основе иерархической кластеризации).

3. Группировка товаров в бакеты.

Есть альтернативный вариант объединения товаров в группы аналогов, который мы пробовали реализовать.

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

Мы пробовали много разных методов поиска сообществ. В некоторых нас не устроило качество разбиения на бакеты. У других оказалась очень высокая вычислительная сложность и длительное время расчёта. Больше всего нам понравился Лувенский метод (и его реализация в библиотеке NetworkX). Но субъективно казалось, что мы не добились максимально возможного результата, — и мы решили вернуться к подходу с иерархической кластеризацией и дендрограммой.

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

Реализация

Первый шаг — расчёт матрицы скоров аналогичности. 

Матрица скоров аналогичности — это матрица вида:

За основу мы взяли статью. Давайте разберём важные аспекты из неё. 

Определения:

• Комплементы (иногда используют термин «товары-дополнители»)— товары, которые часто встречаются в одном чеке. Степень комплементарности товаров положительно скоррелирована с тем, как часто они встречаются в одном чеке.

• Аналоги — товары с совпадающими комплементами, которые редко встречаются в одном чеке. Степень аналогичности товаров положительно скоррелирована с тем, как похожи их товары-комплементы.

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

Упрощённый пример: 

Комплементами здесь являются булочка для хот-дога и сосиска (так как их часто покупают вместе), а аналогами —две приправы для тако (так как их часто покупают вместе с taco shell, но редко — вместе одном чеке).

В статье есть четыре разных способа определения степени комплементарности товаров. Два способа — симметричные (у них скор между i и j равен скору между j и i) и два — асимметричные. Мы попробовали реализовать все — и остановились на первом, так как асимметричные способы требовали какой-то дополнительной логики при последующем построении графов, а из двух симметричных способов первый просто проще.

Вот выбранная нами формула, по которой можно вычислить комплементарность товаров i и j:

Формула (1)

n_t — общее число чеков

d_l^(t) — число товаров в l-ом чеке

A_li (A_lj) равно 1, если товар i(j) был в чеке l, иначе равно 0

Аналогичность можно вычислить двумя разными способами — и мы опять остановились на первом, так как он симметричный:

Формула (2)

n_p — число товаров

W_ik^(c) (W_jk^(c)) — мера комплементарности между товарами i(j) и k, рассчитанная по формуле (1)

Поскольку в определениях аналогичности и комплементарности используются слова «редко» и «часто», а они оценочны, их нужно как-то формализовать. Если бы продажи товаров i и j не зависели друг от друга, то вероятность их совместного появления в одном чеке была бы p_ip_j. А мы оставляем только такие пары товаров, которые фактически встречались в одном чеке чаще или реже этой величины ± среднеквадратичное отклонение, умноженное на некоторый коэффициент. На языке формул:

Часто 

Формула (3)

Редко 

Формула (4)

cn_ij — число чеков, в которых присутствуют оба товара i и j

n_t — общее число чеков

p_i(p_j) — вероятность того, что товар i(j) попадёт в чек (число чеков с товаром i(j) / общее число чеков)

a_m, a_l — уровни значимости (мы экспертно подобрали их равными 0,45 и 0,35)

Ф — кумулятивная функция распределения стандартного нормального распределения (для расчёта Ф^-1 можно использовать метод ppf из модуля scipy.stats.norm)

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

Первым делом нам нужно вычислить степень комплементарности для каждой пары товаров по формуле (1). Вот как будет выглядеть расчёт степени комплементарности товаров i = 1 и j = 2 (это будет сумма шести слагаемых, так как у нас всего шесть чеков): 

Впрочем, у нас всего два ненулевых слагаемых, так как товары 1 и 2 вместе встречаются только в двух чеках.

А вот как выглядит матрица комплементарности для всех наших товаров:

Теперь нам нужно по формуле (3) обнулить в матрице комплементарности скоры тех пар товаров, которые недостаточно часто встречались в одном чеке. Но для начала построим матрицу с фактическим числом совместных покупок (матрицу с cn_ij):

Теперь посчитаем правые части выражения из формулы (3). Расчет на том же примере i = 1 и j = 2 :

А вот как выглядит матрица с правыми частями формулы (3) для всех пар товаров:

Далее необходимо оставить скоры только у тех пар товаров, которые часто встречались в одном чеке, а остальные — обнулить. Другими словами, оставляем в матрице только те скоры, которые соответствуют неравенству из формулы (3), а остальные заменяем на нули (они помечены синим):

Теперь, имея матрицу комплементарности, мы можем построиить матрицу аналогичности по формуле (2). Опять рассмотрим на примере i = 1 и j = 2:

Рассчитаем правые части неравенства формулы (4) — также на примере i = 1 и j = 2:

Проведём очередную манипуляцию по обнулению скоров, на этот раз по формуле (4) (синим цветом выделены отфильтрованные пары товаров):

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

Из неё можно сделать следующие выводы:

• Самая высокая степень аналогичности у товаров «Огурец 1» и «Огурец 2», что ожидаемо и логично.

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

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

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

Второй шаг — построение CDT для каждой категории товаров.

Напомню, что мы делаем иерархическую кластеризацию, результаты которой рассматриваем как CDT. В качестве коэффициентов похожести мы берём не The Yule’s Q coefficient, как в статье, а скоры аналогичности из первого шага.

Для визуализации получившихся CDT мы пользовались методом create_dendrogram из библиотеки Plotly.

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

• параметр distfun — метрика расчёта расстояния между векторами SKU (основные варианты параметра — евклидово, манхэттенское и косинусное расстояния);

• параметр linkagefun — способ приведения кластера из нескольких SKU в вектор для расчёта расстояния между кластерами (основные варианты параметра — single, complete, average).

Документация с описаниями этих параметров.

Вернёмся к разбивке категории «Яйца куриные» и рассмотрим её подробнее.

Тут мы видим довольно залипательную иерархическую структуру. Чем выше степень аналогичности, тем короче между ними линия:

Некоторые выводы, которые можно сделать, рассматривая эту картинку:

• Единственная позиция «Белок яичный» менее всего похожа на все остальные позиции. Она точно должна быть в отдельном бакете. А, возможно, её вообще следует вынести в отдельную категорию.

• Все остальные яйца разделились на две группы по качеству: С0 и СВ — в одной и С1 и С2 — в другой (хотя одна дорогая позиция С1 попала в группу с С0, что может говорить о том, что покупатели ее воспринимают так же, как С0).

• При этом единственная позиция СВ находится относительно далеко от товаров С0.

• Большие упаковки одного качества, но разных брендов находятся очень близко друг к другу.

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

А поскольку мы не можем объективно определить, насколько хорошо то или иное разбиение на бакеты, мы обратились за помощью к категорийным менеджерам. Мы построили CDT для каждой категории четвёртого уровня из нашего товарного каталога тремя способами (на основании трёх разных наборов параметров linkagefun и distfun, которые субъективно показались нам хорошими) и отдали их на оценку. Также мы попросили менеджеров проверить, насколько удачно автоматически подобрались пороговые значения. 

В некоторых категориях менеджерам не понравился ни один из предложенных нами вариантов.   

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

Вообще разбиение на бакеты — нетривиальная задача. В разных категориях люди по-разному определяют параметры выбора аналогов. Где-то основной критерий — это бренд (например, в категории детского питания). Где-то — вес или объём. Где-то — цена. Где-то — вкус. Где-то — определённое свойство товара (например, безлактозность или безглютеновость). При этом каждый из этих параметров может вносить свой вклад с определённым «весом». И иногда, если «веса» разных параметров близки, в бакетах получается трудноинтерпретируемая каша.

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

Потенциал для роста:

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

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

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

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

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

Список использованных библиотек: pandas, NumPy, Sklearn, SciPy, NetworkX, Plotly.

Вывод

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

Сегодня этот подход используется в Ozon fresh для решения следующих задач:

• оптимизация ассортиментной матрицы,

• рекомендации товаров в приложении,

• управление скидками в рамках ценообразования.

И показывает хорошие результаты.

Над проектом работали: Максим Бубон, Дарья Давыдова