order | 0    1    2    3    4    5    6    7    8    9   | sum
----- | ------------------------------------------------ | ---
prod1 | 0.1  0.2  0.3  0.4  0.5  0.0  0.0  0.0  0.0  0.0 | 1.5
prod2 | 0.0  0.0  0.0  0.0  0.0  0.6  0.7  0.8  0.9  1.0 | 4.0

• Для товара купленного давно значение меньше (prod1=1.5), чем для товара купленного недавно (prod2=4.0).

$$ P = \alpha \cdot u_t + (1-\alpha) \cdot u_n $$

Предсказание состоит из двух компонентов:

1. Индивидуальный компонент (repeated purchase component) представлен как вектор пользователя $u_t$ (PIF).
2. Коллаборативный компонент представлен как усредненный PIF вектор похожих пользователей (ближайших соседей): $u_n = \text{avg}(U_{neighbor})$, где $U_{neighbor}$ вектора ближайших $k$ соседей ($k=300$).

Задача:

• Для расчета коллаборативного компонента для каждого из 100 000 пользователей необходимо найти 300 ближайших соседей используя PIF вектора пользователей.

Доп. условия:

1. Разряженные вектора (CSR format)
2. Длина вектора = 49 465

Время работы примитивной реализации KNN: ≈6 часов.

Для уменьшения времени необходимо использовать алгоритм ANN (Approximate Nearest Neighbour). В этой работе я использовал его открытую реализацию facebookresearch/pysparnn, т.к. она поддерживает разряженные вектора.

Время работы ANN составило 5 минут.

1. При $\alpha=1.0$, 100% информации берется из истории пользователя.
2. При $\alpha=0.9$, 90% информации берется из истории пользователя (индивидуальный компонент), а 10% из истории 300 похожих пользователей (коллаборативный компонент).

1. 70% товаров пользователь заказывал ранее.
2. До 20% товаров, заказанных пользователем впервые, можно найти в истории похожих пользователей.
3. 10% товаров, заказанных впервые, не встречаются в истории пользователя, ни похожих пользователей.
4. Затухающий коэффициент дает прирост в оценке. При $\alpha=1.0$ без затухающего коэффициента модель равносильна простой частотной модели:
   1. Без коэффициента затухания: 0.27455
   2. С коэффициентом затухания: 0.29716

Задача сводится к задаче бинарной классификации: для каждой пары пользователь-товар (user-item) модель предсказывает значение 1, если товар будет перезаказан (есть в целевой корзине), 0 если нет.

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

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

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

На основании таблицы транзакций рассчитываются признаки (features / фичи). Целевой признак: in_target = 1 если товар есть в целевой корзине, 0 если нет.

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

Для каждой пары пользователь-товар выходной вектор содержит значение в интервале [0, 1] выражающее вероятность перезаказа товара Б пользователем А. Для финального предсказания товары сортируются по убыванию вероятности.

Конструирование фичей

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

Признаки 3-х типов:

1. Признаки пользователя (u_ user):
   • Например: число транзакций, число уникальных товаров в истории, число заказов, средний размер заказа, среднее время между заказами и т.д.
2. Признаки товара (i_ item):
   • Например: сколько пользователей купили этот товар, сколько раз в среднем пользователь покупает этот товар, среднее время между заказами этого товара и т.д.
3. Признаки взаимодействия пользователя с конкретным товаром (ui_ user-item):
   • Например: сколько раз пользователь купил определенный товар, дней с момента последнего заказа этого товара, средняя позиция товара в корзине и т.д.

• i_days_delay_global_mid -- средний интервал между заказами товара Б среди всех пользователей;

  • Как часто пользователи в среднем перезаказывают товар Б.

• ui_total_buy_ratio -- доля заказов пользователя А, в которых есть товар Б;

  • = 1.0 если товар Б есть в 10 из 10 заказов пользователя А.
  • = 0.2 если товар Б есть в 2 из 10 заказов пользователя А.

• u_n_transactions -- число транзакций пользователя А;

  • Отражает активность пользователя.

• u_unique_items -- число уникальных товаров в истории покупок пользователя А;

  • Отражает его склонность пробовать новые товары.

• ui_total_buy -- число заказов пользователя А, в которых есть товар Б;

• ui_readyness_mid_abs -- отклонение пользователя А от привычного интервала перезаказа товара Б.

Показатель readyness (готовность):

• Например в среднем между заказами товара Б проходит 10 дней, т.е. ui_days_delay_mid = 10.
• Последний раз пользователь купил товар Б 12 дней назад, т.е. ui_days_passed = 12.
• Тогда ui_readyness_mid = (ui_days_passed - ui_days_delay_mid) = 2
  • Отрицательные значения = с последнего заказа прошло слишком мало времени, пользователь не готов купить товар.
  • Большое значение = прошло больше времени чем обычно, пользователь готов купить товар.

Полное описание всех признаков в приложении.

1. На точность предсказаний влияет качество и количество фичей.
2. Точность этого способа превосходит простую частотную модель, т.к. позволяет задействовать дополнительную информацию, например об интервале между заказами, времени суток и дне недели.

1. Одни и те же методы не подходят для разных типов товаров:

   1. Фильмы, музыка, книжный магазин

      • Однократные покупки
      • Задача: коллаборативная фильтрация
      • Рекомендации на основе похожих пользователей или товаров

   2. Гипермаркеты (еда, продовольственные товары)

      • Периодические покупки

      • Задача: генерация следующего набора элементов (NBR / NBP / Sets2sets)

      • Простые модели: подсчет покупок, средний интервал между заказами

   3. Техника, услуги, одежда

      • Смешанные покупки: однократные + периодические

      • Задача: генерация следующего элемента последовательности (Seq2seq)

2. Коллаборативная фильтрация подходит для рекомендаций (фильмы, однократные покупки), но не подходит для предсказания периодических покупок

• https://github.com/d-01/instacartlib
• Демо в Google Colab

Установка:

pip install https://github.com/d-01/instacartlib/archive/main.zip

Загрузка датасета:

from instacartlib import InstacartDataset

InstacartDataset(verbose=1).download(to_dir='instacart_data')

from instacartlib import NextBasketPrediction

nbp = NextBasketPrediction(verbose=1)
nbp.add_data('instacart_data')
nbp.load_model('catboost')  # or 'gbc'

nbp.get_predictions(user_ids=[20001, 85768])

nbp.predictions_to_csv('submission.csv')

user_id,product_id
1,196 12427 25133 10258 46149 39657 38928 35951 13032 49235
2,47209 19156 1559 18523 33754 16589 21709 24852 39928 22825
3,39190 47766 43961 21903 17668 18599 16797 48523 32402 22035
...

nbp_new = NextBasketPrediction(verbose=1)
nbp_new.add_data('instacart_data')
nbp_new.train_model()
nbp_new.save_model('model_nbp.dump')