Как мы сделали автоматический подбор похожих товаров

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

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

Как определить, что товары похожи? Можно сравнить характеристики, чем больше совпало, тем более похожи товары. Но это не работает так просто, к сожалению. На практике оказывается, что, как правило, почти не бывает товаров, где заполнены все характеристики. 80% — хороший результат. Во-вторых, какие-то характеристики важнее, чем другие. Например, телевизор с диагональю в 65 дюймов совершенно не похож на телевизор с диагональю 22 дюйма, хотя у обоих по 2 USB-порта. Или, другой пример, металлический корпус и алюминиевый корпус гораздо ближе друг к другу, чем к пластику, хотя это три разных значения.

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

1. Назначить характеристикам веса. Размер диагонали — важно, количество USB-портов — менее важно.
2. Определить область значений каждой характеристики, а на ней задать функцию расстояния между значениями.
3. Определиться со стратегией обработки случаев, когда для одного товара характеристика известна, а для другого — нет.
4. Имея расстояния между значениями всех характеристик, вычислить расстояние между товарами.
5. Подумать над производительностью, вычисление всех пар расстояний имеет сложность

   $$

   И если вычисление 50 миллионов расстояний для 10 тысяч товаров не кажется большой проблемой, то 50 миллиардов для 300 тысяч — уже много.

Давайте эти задачи решать. В какой-то мере это будет исследовательская работа.

Как мы определяем веса характеристик

С весами мы использовали две основные идеи.

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

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

1. Если характеристика числовая, то считаем корреляцию с ценой по Пирсону.
2. Если перечисление с взаимоисключающим выбором (но не чисел), то упорядочиваем его элементы по средней цене товаров с таким значением, и считаем корреляцию с ценой по Спирмену.
3. Если предусмотрен множественный выбор, то сводим его к множеству взаимоисключающих (да/нет), и считаем корреляцию каждого с ценой по Спирмену. Полученный коэффициент уменьшаем в зависимости от количества вариантов.
4. Считаем процент заполненных значений для каждой из характеристик и увеличиваем или уменьшаем её вес, полученный ранее.
5. Полученные значения могут использоваться в качестве весов, но на практике лучший результат получается, если их еще раз нелинейно преобразовать, сохраняя порядок.

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

Как мы считаем расстояние между товарами

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

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

Тогда в качестве функции расстояния можно взять такие функции:

• В случае чисел — разницу их значений, деленную на фактическую длину диапазона всех значений. То есть, если минимальная глубина всех стиральных машин составляет 35 см, а максимальная — 75 см, то размер диапазона составит 40 см. Умножим это число на вес характеристики.
• В случае перечислений — разницу порядковых номеров значений (помните, мы их упорядочивали?), деленную на количество значений в перечислении. Это число мы тоже умножим на вес характеристики.
• Если характеристика в одном из товаров не заполнена, возьмем среднее значение попарных расстояний между всеми заполненными значениями.

Теперь о производительности. На практике оказалось, что за приемлемое время (до 5 минут) мы можем посчитать попарные расстояния между 30 тысячами товаров. Но в то же время в некоторых категориях товаров больше, например, матрасов в каталоге может быть и сто тысяч, и в этом случае речь идет о увеличении затраченного времени в 10 раз.

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

$$

Это быстрее, чем

$$

Потом делим все товары на пересекающиеся группы (скажем, пересекающиеся на 20%), и считаем попарные расстояния внутри каждой группы. Таким образом, до 30 тысяч товаров в категории время обработки растет как

$$

а начиная с 30 тысяч — как

$$

Результаты

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


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

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