3. TIFU KNN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "cca073eb",
   "metadata": {},
   "source": [
    "### TIFU KNN\n",
    "Один из самых эффективных алгоритмов для решения задачи next basket recommendation  \n",
    "Была использована его вариация  \n",
    "Примерный алгоритм следующий:\n",
    "* Каждую корзину кодируем как вектор, где на i-й позиции стоит количество i-го товара в этой корзине\n",
    "* Далее складываем все корзины каждого пользователя:\n",
    "    - Либо как взвешенное среднее по всем корзинам\n",
    "    - Либо как сумму векторов, умноженных на веса\n",
    "    - !Старые корзины имеют меньший коэффициент\n",
    "    \n",
    "    Коэффициент **`r`**\n",
    "* По полученным векторам находим ближайших соседей (**`k_nearest`**) каждого пользователя и:\n",
    "    - Либо берем итоговый вектор пользователя как взвешенное среднее по всем соседям и самому пользователю (чем дальше сосед, чем меньше коэффициент)\n",
    "    - Либо находим взвешенное среднее по всем соседям, а дальше итоговый вектор получаем как P = v_user * alpha + v_avg_neighbors * (1 - alpha)\n",
    "    \n",
    "    Коэффициент **`alpha`**\n",
    "* Далее находим позиции (**`top_k`**) в итоговом векторе каждого пользователя, где значения максимальны - это и есть рекомендации  \n",
    "  \n",
    "В оригинальном алгоритме корзины каждого пользователя разбиваются на группы, но так как в среднем покупок у пользователя не так много, этот шаг был убран\n",
    "\n",
    "Оптимальной из проверенных комбинаций параметров оказалась:\n",
    "* **`r = 0.75`**\n",
    "* **`k_nearest = 30`**\n",
    "* **`alpha = 0.95`**\n",
    "* **`top_k = 18`**\n",
    "\n",
    "Статья о TIFU KNN (2020): https://arxiv.org/pdf/2006.00556.pdf\n",
    "\n",
    "! Можно запускать в режиме \"Run all\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "79fb04b1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n",
      "Wall time: 1.65 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "%pylab inline\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "from sklearn.metrics import f1_score\n",
    "from sklearn.neighbors import NearestNeighbors\n",
    "from implicit.lmf import LogisticMatrixFactorization\n",
    "from scipy import sparse\n",
    "from tqdm import tqdm\n",
    "tqdm.pandas()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "7c16c8c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.read_csv(\"data/main.csv\")\n",
    "\n",
    "df.rename(columns={\"order_completed_at\":\"time\"}, inplace=True) # rename \"order_completed_at\" column to \"time\"\n",
    "df[\"time\"] = pd.to_datetime(df[\"time\"], format=\"%Y-%m-%d %H:%M:%S\") # \"time\" column to datetime type"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "119e459b",
   "metadata": {},
   "outputs": [],
   "source": [
    "r = 0.75\n",
    "k_nearest = 30\n",
    "alpha = 0.95 \n",
    "top_k = 18"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ed4483ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "carts_count = 881\n",
    "users_count = 20000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "1e71cc15",
   "metadata": {},
   "outputs": [],
   "source": [
    "def duplicates_to_count(t):\n",
    "    return t.groupby(['user_id', 'time'])['cart'].value_counts() \\\n",
    "                                                  .to_frame() \\\n",
    "                                                  .rename(columns={\"cart\":\"count\"}) \\\n",
    "                                                  .reset_index()\n",
    "\n",
    "def count_to_duplicates(t):\n",
    "    g = t.copy()\n",
    "    g[\"to_explode\"] = g[\"count\"].apply(lambda x: [i for i in range(x)])\n",
    "    g = g.explode(\"to_explode\") \\\n",
    "         .drop(columns=[\"count\", \"to_explode\"])\n",
    "    return g\n",
    "\n",
    "def make_train_targets(t, level=1):\n",
    "    user_last_time = t.groupby([\"user_id\"])[\"time\"].max().to_frame().reset_index()\n",
    "    user_last_time[\"last_buy\"] = 1\n",
    "    \n",
    "    train = pd.merge(t, user_last_time, on=[\"time\", \"user_id\"], how=\"left\")\n",
    "    train = train[train[\"last_buy\"] != 1]\n",
    "    train.drop(columns=[\"last_buy\"], inplace=True)\n",
    "    \n",
    "    if level >= 2:\n",
    "        return make_train_targets(train, level-1)\n",
    "    \n",
    "    user_last_time.drop(columns=[\"last_buy\"], inplace=True)\n",
    "    \n",
    "    user_last_carts = pd.merge(user_last_time, t, on=[\"user_id\", \"time\"], how=\"left\")\n",
    "    \n",
    "    skeleton = make_skeleton(t)\n",
    "    targets = pd.merge(skeleton, user_last_carts.drop(columns=[\"time\"]), on=[\"user_id\",\"cart\"], how=\"left\")\n",
    "    targets.fillna(0, inplace=True)\n",
    "    targets[\"count\"] = targets[\"count\"].apply(lambda x: x if x <= 1 else 1).astype(int)\n",
    "    targets.rename(columns={\"count\":\"target\"}, inplace=True)\n",
    "    return train, targets\n",
    "\n",
    "def make_skeleton(t):\n",
    "    return t.groupby(\"user_id\")[\"cart\"].unique().to_frame().reset_index().explode(\"cart\")\n",
    "\n",
    "def user_cart_pivot_table(t):\n",
    "    g = pd.pivot_table(t, columns=\"cart\", index=[\"user_id\", \"time\"], values=\"count\", aggfunc=np.sum, fill_value=0)\n",
    "    for cart in list(set(df[\"cart\"].unique()).difference(set(t[\"cart\"].unique()))):\n",
    "        g[cart] = 0\n",
    "    return g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "847531d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "df = duplicates_to_count(df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6a32b6f1",
   "metadata": {},
   "outputs": [],
   "source": [
    "train, targets = make_train_targets(df, level=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "bc67b888",
   "metadata": {},
   "outputs": [],
   "source": [
    "main = user_cart_pivot_table(train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "fe2b274e",
   "metadata": {},
   "outputs": [],
   "source": [
    "main = main.reindex(sorted(main.columns), axis=1).reset_index()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "607b0220",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th>cart</th>\n",
       "      <th>user_id</th>\n",
       "      <th>time</th>\n",
       "      <th>0</th>\n",
       "      <th>1</th>\n",
       "      <th>2</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "      <th>5</th>\n",
       "      <th>6</th>\n",
       "      <th>7</th>\n",
       "      <th>...</th>\n",
       "      <th>871</th>\n",
       "      <th>872</th>\n",
       "      <th>873</th>\n",
       "      <th>874</th>\n",
       "      <th>875</th>\n",
       "      <th>876</th>\n",
       "      <th>877</th>\n",
       "      <th>878</th>\n",
       "      <th>879</th>\n",
       "      <th>880</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>2020-07-19 09:59:17</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>2020-08-24 08:55:32</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>2019-05-08 16:09:41</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>2020-01-17 14:44:23</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>2020-02-06 22:46:55</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>5 rows × 883 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "cart  user_id                time  0  1  2  3  4  5  6  7  ...  871  872  873  \\\n",
       "0           0 2020-07-19 09:59:17  0  0  0  0  0  0  0  0  ...    0    0    0   \n",
       "1           0 2020-08-24 08:55:32  0  0  0  0  0  1  0  0  ...    0    0    0   \n",
       "2           1 2019-05-08 16:09:41  0  0  0  0  0  0  0  0  ...    0    0    0   \n",
       "3           1 2020-01-17 14:44:23  0  0  0  0  0  0  0  0  ...    0    0    0   \n",
       "4           1 2020-02-06 22:46:55  0  0  0  0  0  0  0  0  ...    0    0    0   \n",
       "\n",
       "cart  874  875  876  877  878  879  880  \n",
       "0       0    0    0    0    0    0    0  \n",
       "1       0    0    0    0    0    0    0  \n",
       "2       0    0    0    0    0    0    0  \n",
       "3       0    0    0    0    0    0    0  \n",
       "4       0    0    0    0    0    0    0  \n",
       "\n",
       "[5 rows x 883 columns]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "main.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "c97303da",
   "metadata": {},
   "outputs": [],
   "source": [
    "main.sort_values('time', ascending=False, inplace=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "17c092dd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th>cart</th>\n",
       "      <th>user_id</th>\n",
       "      <th>time</th>\n",
       "      <th>0</th>\n",
       "      <th>1</th>\n",
       "      <th>2</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "      <th>5</th>\n",
       "      <th>6</th>\n",
       "      <th>7</th>\n",
       "      <th>...</th>\n",
       "      <th>871</th>\n",
       "      <th>872</th>\n",
       "      <th>873</th>\n",
       "      <th>874</th>\n",
       "      <th>875</th>\n",
       "      <th>876</th>\n",
       "      <th>877</th>\n",
       "      <th>878</th>\n",
       "      <th>879</th>\n",
       "      <th>880</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>134963</th>\n",
       "      <td>10497</td>\n",
       "      <td>2020-09-03 20:03:55</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>187074</th>\n",
       "      <td>19237</td>\n",
       "      <td>2020-09-03 19:42:35</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>139882</th>\n",
       "      <td>11107</td>\n",
       "      <td>2020-09-03 15:19:32</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>159623</th>\n",
       "      <td>13763</td>\n",
       "      <td>2020-09-03 14:35:33</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>161461</th>\n",
       "      <td>14041</td>\n",
       "      <td>2020-09-03 13:43:03</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>...</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>5 rows × 883 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "cart    user_id                time  0  1  2  3  4  5  6  7  ...  871  872  \\\n",
       "134963    10497 2020-09-03 20:03:55  0  0  0  0  0  0  0  0  ...    0    0   \n",
       "187074    19237 2020-09-03 19:42:35  0  0  0  0  0  0  0  0  ...    0    0   \n",
       "139882    11107 2020-09-03 15:19:32  0  0  0  0  0  0  0  0  ...    0    0   \n",
       "159623    13763 2020-09-03 14:35:33  0  0  0  0  0  0  0  0  ...    0    0   \n",
       "161461    14041 2020-09-03 13:43:03  0  0  0  0  0  0  0  0  ...    0    0   \n",
       "\n",
       "cart    873  874  875  876  877  878  879  880  \n",
       "134963    0    0    0    0    0    0    0    0  \n",
       "187074    0    0    0    0    0    0    0    0  \n",
       "139882    0    0    0    0    0    0    0    0  \n",
       "159623    0    0    0    0    0    0    0    0  \n",
       "161461    0    0    0    0    0    0    0    0  \n",
       "\n",
       "[5 rows x 883 columns]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "main.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "39137033",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|█████████████████████████████████████████████████████████████████████| 189406/189406 [00:00<00:00, 1209804.12it/s]\n"
     ]
    }
   ],
   "source": [
    "users_all_carts = [[] for i in range(users_count)]\n",
    "main_array = main.to_numpy()\n",
    "for arr in tqdm(main_array):\n",
    "    users_all_carts[arr[0]].append(arr[2:])\n",
    "    \n",
    "# Теперь users_all_carts содержит для каждого пользователя набор его корзин, закодированных как вектор"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "a421ba79-9f0a-486e-8502-453f9d06d2b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Вектор пользователя формируется как среднее взвешенное всех его корзин (более старые корзины имеют меньший вес)\n",
    "def get_users_one_cart_as_avg(users, r):\n",
    "    users_as_avg_cart = [[] for i in range(users_count)]\n",
    "    for i in tqdm(range(len(users))):\n",
    "        cart = pd.Series(np.zeros(carts_count), dtype=float)\n",
    "        cur_weights = 0\n",
    "        for j in range(len(users[i])):\n",
    "            weight = r**(j)\n",
    "            cart += pd.Series(users[i][j]) * weight\n",
    "            cur_weights += weight\n",
    "        if cur_weights == 0:\n",
    "            cur_weights = 1\n",
    "        cart /= cur_weights\n",
    "        users_as_avg_cart[i] = cart.tolist()\n",
    "    return users_as_avg_cart\n",
    "\n",
    "# Вектор пользователя формируется как сумма векторов, умноженных на веса (более старые корзины имеют меньший вес)\n",
    "def get_users_one_cart_as_attenuation(users, r):\n",
    "    users_as_attenuation_cart = [[] for i in range(users_count)]\n",
    "    for i in tqdm(range(len(users))):\n",
    "        cart = pd.Series(np.zeros(carts_count), dtype=float)\n",
    "        for j in range(len(users[i])):\n",
    "            cart += pd.Series(users[i][j]) * r**(j)\n",
    "        users_as_attenuation_cart[i] = cart.tolist()\n",
    "    return users_as_attenuation_cart"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "872bbd1f",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|███████████████████████████████████████████████████████████████████████████| 20000/20000 [01:12<00:00, 276.29it/s]\n"
     ]
    }
   ],
   "source": [
    "users_as_vectors = get_users_one_cart_as_avg(users_all_carts, r) ### YOU CAN CHANGE THE FUNCTION"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3120f760",
   "metadata": {},
   "source": [
    "Ближайших соседей также можно искать несколькими способами:\n",
    "* NearestNeighbors из sklearn\n",
    "* Матричное разложение из implicit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "6f3e31dd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_neighbors_nn(users_carts, k): #GOOD\n",
    "    model = NearestNeighbors()\n",
    "    model.fit(users_carts)\n",
    "    neighbors = model.kneighbors(users_carts, n_neighbors=k+1, return_distance=False)\n",
    "    return neighbors\n",
    "\n",
    "def get_neighbors_mf(users_carts, k):\n",
    "    model = LogisticMatrixFactorization(iterations=100)\n",
    "    model.fit(sparse.csr_matrix(users_carts).transpose())\n",
    "    neighbors = [ [] for i in range(users_count)]\n",
    "    for i in tqdm(range(users_count)):\n",
    "        nbrs = model.similar_users(i, k+1)\n",
    "        for tpl in nbrs:\n",
    "            neighbors[i].append(tpl[0]) \n",
    "    return neighbors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "735d3a01",
   "metadata": {},
   "outputs": [],
   "source": [
    "neighbors = get_neighbors_nn(users_as_vectors, k_nearest) ### YOU CAN CHANGE THE FUNCTION"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "215759a0-7b2e-411a-ae54-834d5e1c02d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Итоговый вектор пользователя высчитывается по формуле P = v_user * alpha + v_avg_neighbors * (1 - alpha)\n",
    "def combine_with_neighbors_avg(users_carts, neighbors, alpha):\n",
    "    avg_nbrs = [ [] for i in range(users_count) ]\n",
    "    for i in tqdm(range(users_count)):\n",
    "        avg = pd.Series(np.zeros(carts_count))\n",
    "        cur_weights = 0\n",
    "        for j in range(1, len(neighbors[i])):\n",
    "            avg += pd.Series(users_carts[neighbors[i][j]]) * (len(neighbors[i]) - j)\n",
    "            cur_weights += (len(neighbors[i]) - j)\n",
    "        avg /= (cur_weights if cur_weights != 0 else 1)\n",
    "        avg_nbrs[i] = avg\n",
    "    return [pd.Series(users_carts[i]) * alpha + pd.Series(avg_nbrs[i]) * (1-alpha) for i in range(users_count)]\n",
    "\n",
    "# Итоговый вектор пользователя высчитывается как сумма вектора пользователя и векторов его соседей,\n",
    "# умноженных на коэффициенты (чем дальше сосед, тем меньше коэффициент)\n",
    "# Этот вариант позволяет получить большее значение метрики\n",
    "def combine_with_neighbors_attenuation(users_carts, neighbors, alpha):\n",
    "    users_p = [ [] for i in range(users_count)]\n",
    "    for i in tqdm(range(len(neighbors))):\n",
    "        users_p[i] = pd.Series(users_carts[i])\n",
    "        for j in range(1, k_nearest+1):\n",
    "            users_p[i] += alpha**(j) * pd.Series(users_carts[neighbors[i][j]])\n",
    "    return users_p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "57ceed84",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|███████████████████████████████████████████████████████████████████████████| 20000/20000 [03:07<00:00, 106.57it/s]\n"
     ]
    }
   ],
   "source": [
    "users_as_final_vectors = combine_with_neighbors_attenuation(users_as_vectors, neighbors, alpha) ### YOU CAN CHANGE THE FUNCTION"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31588925-e765-4357-9eda-2f37a550700e",
   "metadata": {},
   "source": [
    "Сформируем итоговые рекомендации для каждого пользователя"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "767200d1",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████████████████████████████████████████████████████████████████████| 20000/20000 [00:03<00:00, 6128.98it/s]\n"
     ]
    }
   ],
   "source": [
    "users_best_basket = []\n",
    "for i in tqdm(range(users_count)):\n",
    "    users_best_basket.append(users_as_final_vectors[i].sort_values(ascending=False).head(top_k).index.tolist())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "758ca1f9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[57,\n",
       "  14,\n",
       "  84,\n",
       "  22,\n",
       "  82,\n",
       "  383,\n",
       "  409,\n",
       "  432,\n",
       "  379,\n",
       "  382,\n",
       "  61,\n",
       "  5,\n",
       "  430,\n",
       "  23,\n",
       "  41,\n",
       "  398,\n",
       "  441,\n",
       "  402]]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "users_best_basket[:1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e1d0e3c",
   "metadata": {},
   "source": [
    "Можно также добавлять к рекомендациям предметы, найденные через закономерности, см. `2. Apriori.ipynb`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "83f3311c",
   "metadata": {},
   "outputs": [],
   "source": [
    "add_carts_from_apriori = False\n",
    "\n",
    "if add_carts_from_apriori:\n",
    "    ap = pd.read_csv(\"data/apriori_top_20.csv\")\n",
    "    ap_map = {}\n",
    "    for index, row in ap.iterrows():\n",
    "        ap_map[int(row[\"from\"])] = int(row[\"to\"])\n",
    "    \n",
    "    for i in tqdm(range(users_count)):\n",
    "        for key in ap_map.keys():\n",
    "            if key in users_best_basket[i] and ap_map[key] not in users_best_basket[i]:\n",
    "                users_best_basket[i].append(ap_map[key])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9179fdc3-d9ec-404e-b3d5-c932f30f9461",
   "metadata": {},
   "source": [
    "Сформируем датафрейм с рекомендациями"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "75e4e9d0-e276-4b3a-98a5-ac14fb937a54",
   "metadata": {},
   "outputs": [],
   "source": [
    "recs = pd.DataFrame()\n",
    "recs[\"user_id\"] = [i for i in range(users_count)]\n",
    "recs[\"items\"] = users_best_basket"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "385f4e2b-affc-4bee-af9c-30041cf122c8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>user_id</th>\n",
       "      <th>items</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>[57, 14, 84, 22, 82, 383, 409, 432, 379, 382, ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>[55, 798, 169, 812, 171, 14, 170, 88, 198, 441...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>[57, 61, 23, 382, 82, 84, 403, 398, 22, 17, 38...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>[57, 61, 84, 398, 430, 382, 19, 41, 383, 22, 1...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>[57, 398, 61, 84, 22, 420, 17, 14, 430, 388, 1...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   user_id                                              items\n",
       "0        0  [57, 14, 84, 22, 82, 383, 409, 432, 379, 382, ...\n",
       "1        1  [55, 798, 169, 812, 171, 14, 170, 88, 198, 441...\n",
       "2        2  [57, 61, 23, 382, 82, 84, 403, 398, 22, 17, 38...\n",
       "3        3  [57, 61, 84, 398, 430, 382, 19, 41, 383, 22, 1...\n",
       "4        4  [57, 398, 61, 84, 22, 420, 17, 14, 430, 388, 1..."
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recs.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43f943f3-6633-4f55-a9c2-81c81103d509",
   "metadata": {},
   "source": [
    "Приведём рекомендации в удобный для оценивания метрики вид"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "5057aee5-300e-4272-a739-b7811f2891b2",
   "metadata": {},
   "outputs": [],
   "source": [
    "recs = recs.explode('items').rename(columns={'items': 'cart'})\n",
    "recs['predict'] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4287cde3-ca22-43aa-a770-7eda115e4409",
   "metadata": {},
   "source": [
    "Добавим верные ответы"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "65d045bd",
   "metadata": {},
   "outputs": [],
   "source": [
    "res = pd.merge(targets, recs, on=[\"user_id\", 'cart'], how=\"left\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "620c770e",
   "metadata": {},
   "outputs": [],
   "source": [
    "res['predict'] = res['predict'].fillna(0).astype(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "b25b3d9b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>user_id</th>\n",
       "      <th>cart</th>\n",
       "      <th>target</th>\n",
       "      <th>predict</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>14</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>20</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>0</td>\n",
       "      <td>57</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>0</td>\n",
       "      <td>82</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0</td>\n",
       "      <td>379</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   user_id cart  target  predict\n",
       "0        0   14       0        1\n",
       "1        0   20       0        0\n",
       "2        0   57       1        1\n",
       "3        0   82       0        1\n",
       "4        0  379       0        1"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "1dfb2e27",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.40996"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "round(f1_score(res[\"target\"], res[\"predict\"]), 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a04d0901",
   "metadata": {},
   "source": [
    "#### Мини-исследование алгоритмов\n",
    "При фиксированных параметрах \n",
    "* r = 0.8\n",
    "* k_nearest = 20              \n",
    "* alpha = 0.85    \n",
    "* top_k = 15\n",
    "* level = 1\n",
    "\n",
    "Менялись варианты (1) усреднения корзин пользователя, (2) поиска ближайших соседей и (3) объединения пользователя с соседями, получил следующие значения метрики\n",
    "* (1)-(2)-(3) - score\n",
    "* avg-nn-avg - 0.37851\n",
    "* avg-nn-att - 0.39407 - best\n",
    "* avg-mf-avg - 0.37861\n",
    "* avg-mf-att - 0.38423\n",
    "* att-nn-avg - 0.37727\n",
    "* att-nn-att - 0.38949 \n",
    "* att-mf-avg - 0.37817\n",
    "* att-mf-att - 0.38835  \n",
    "\n",
    "** att - attenuation - затухание, при таком подходе мы берем коэффициент затухания от новых покупок к старым \n",
    "  \n",
    "Что можно сказать точно - для усреднения корзин пользователя лучше использовать get_users_one_cart_as_attenuation()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "ce6d481f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# r = 0.75\n",
    "# k_nearest = 30\n",
    "# alpha = 0.95     Scores: 0.40996, 0.41104, 0.37132 - mean=0.39744\n",
    "# top_k = 18\n",
    "# avg-nn-att"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "f3cfeaa3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# r = 0.8\n",
    "# k_nearest = 20             \n",
    "# alpha = 0.85     Scores: 0.39407, 0.38983, 0.35291 - mean=0.37894\n",
    "# top_k = 15\n",
    "# avg-nn-att"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "c4f67bdc",
   "metadata": {},
   "outputs": [],
   "source": [
    "# r = 0.85\n",
    "# k_nearest = 26    \n",
    "# alpha = 0.91     Scores: 0.39005, 0.38579, 0.34770 - mean=0.37451\n",
    "# top_k = 14\n",
    "# avg-nn-att"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "83e1d324",
   "metadata": {},
   "outputs": [],
   "source": [
    "# r = 0.9\n",
    "# k_nearest = 30    \n",
    "# alpha = 0.75    Scores: 0.35904, 0.35214, 0.31353 - mean=0.34157\n",
    "# top_k = 10\n",
    "# avg-nn-att"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "01e043fd-f185-4914-8726-c47bd7d9754c",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}