bayesian-personalized-ranking.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# BPR Bayesian Personalized Ranking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ThetaLog.com"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load các thư viện cần thiết\n",
    "import os\n",
    "import math\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from urllib.request import urlopen\n",
    "from zipfile import ZipFile\n",
    "from scipy.sparse import csr_matrix, dok_matrix\n",
    "from sklearn.metrics import roc_auc_score\n",
    "\n",
    "np.random.seed(12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_movielens_data():\n",
    "    \"\"\"\n",
    "    Tải tập tin dữ liệu từ trang chủ grouplens\n",
    "    Tập dữ liệu: ml-100k\n",
    "\n",
    "    :return dataframe: pandas df\n",
    "    \"\"\"\n",
    "    zipurl = 'http://files.grouplens.org/datasets/movielens/ml-100k.zip'\n",
    "    zipresp = urlopen(zipurl)\n",
    "\n",
    "    # Nếu không có thì tài về từ mạng internet\n",
    "    if not os.path.isdir('ml-100k'):\n",
    "        print('Downloading: http://files.grouplens.org/datasets/movielens/ml-100k.zip')\n",
    "        with open(\"ml-100k.zip\", \"wb\") as file:\n",
    "            file.write(zipresp.read())\n",
    "            file.close()\n",
    "        print('Completed!')\n",
    "\n",
    "    # Giải nén\n",
    "    zipdata = ZipFile(\"ml-100k.zip\")\n",
    "    zipdata.extractall(path = '')\n",
    "    zipdata.close()\n",
    "\n",
    "    # Load dữ liệu từ Pandas\n",
    "    file_path = os.path.join('ml-100k', 'u.data')\n",
    "    names = ['users', 'items', 'ratings', 'timestamp']\n",
    "    dataframe = pd.read_csv(file_path, sep = '\\t', names = names)\n",
    "    return dataframe"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataframe = load_movielens_data()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "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>users</th>\n",
       "      <th>items</th>\n",
       "      <th>ratings</th>\n",
       "      <th>timestamp</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>196</td>\n",
       "      <td>242</td>\n",
       "      <td>3</td>\n",
       "      <td>881250949</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>186</td>\n",
       "      <td>302</td>\n",
       "      <td>3</td>\n",
       "      <td>891717742</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>22</td>\n",
       "      <td>377</td>\n",
       "      <td>1</td>\n",
       "      <td>878887116</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>244</td>\n",
       "      <td>51</td>\n",
       "      <td>2</td>\n",
       "      <td>880606923</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>166</td>\n",
       "      <td>346</td>\n",
       "      <td>1</td>\n",
       "      <td>886397596</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   users  items  ratings  timestamp\n",
       "0    196    242        3  881250949\n",
       "1    186    302        3  891717742\n",
       "2     22    377        1  878887116\n",
       "3    244     51        2  880606923\n",
       "4    166    346        1  886397596"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Xem thử dữ liệu trông thế nào\n",
    "dataframe.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def convert_to_bpr_mat(dataframe, threshold=3):\n",
    "    \"\"\"\n",
    "    Chuyển đổi DataFrame MovieLens 100K ban đầu sang ma trận BPR\n",
    "    Mỗi dòng là Users\n",
    "    Mỗi cột là Item\n",
    "    Định dạng ma trận thưa\n",
    "\n",
    "    :param dataframe: pandas df movielens 100K\n",
    "    :param threshold: ngưỡng ratings chấp nhận nên khuyến nghị\n",
    "    :return bpr_mat: np.array - ma trận thưa bpr\n",
    "    \"\"\"\n",
    "    tempdf = dataframe.copy()\n",
    "    tempdf['positive'] = tempdf['ratings'].apply(func=lambda x: 0 if x < threshold else 1)\n",
    "\n",
    "    # Vì tập dữ liệu này đánh index từ 1 nên chuyển sang kiểu category\n",
    "    # để tránh việc chúng ta có ma trận\n",
    "    tempdf['users'] = tempdf['users'].astype('category')\n",
    "    tempdf['items'] = tempdf['items'].astype('category')\n",
    "\n",
    "    bpr_mat = csr_matrix((tempdf['positive'],\n",
    "                          (tempdf['users'].cat.codes,\n",
    "                           tempdf['items'].cat.codes)))\n",
    "    bpr_mat.eliminate_zeros()\n",
    "    del tempdf\n",
    "    return bpr_mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "bpr_mat = convert_to_bpr_mat(dataframe)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def split_to_train_test(bpr_mat, test_ratio = 0.2, verbose=True):\n",
    "    \"\"\"\n",
    "    Chia tập dữ liệu ra thành tập train & tập test\n",
    "\n",
    "    :param bpr_mat: ma trận bpr\n",
    "    :param test_ratio: float - tỉ lệ test set\n",
    "\n",
    "    :return train: ma trận bpr train\n",
    "    :return test: ma trận bpr test\n",
    "    \"\"\"\n",
    "    # Số lượng người dùng\n",
    "    n_users = bpr_mat.shape[0]\n",
    "    # Dùng ma trận thưa Dictionary Of Keys tối ưu hơn cho công đoạn này\n",
    "    train = bpr_mat.copy().todok()\n",
    "    test = dok_matrix(train.shape) # Lưu ý hiện tại test là ma trận 0\n",
    "\n",
    "    # với mỗi người dùng u\n",
    "    # chia số trường hợp nên khuyến nghị với tỉ lệ test_ratio đươc cho\n",
    "    # phần nào thuộc về test\n",
    "    for u in range(n_users):\n",
    "        split_index = bpr_mat[u].indices\n",
    "        # đếm số trường hợp nên khuyến nghị\n",
    "        count_positive = split_index.shape[0]\n",
    "        n_splits = math.ceil(test_ratio * count_positive)\n",
    "        test_index = np.random.choice(split_index, size=n_splits, replace=False)\n",
    "        # Xem như dữ liệu chưa biết trong tập train\n",
    "        train[u, test_index] = 0\n",
    "        # Xem như dữ liệu nhìn thấy trong tập test\n",
    "        test[u, test_index] = 1\n",
    "\n",
    "    train, test = train.tocsr(), test.tocsr()\n",
    "\n",
    "    # Nếu cần in thông tin ra ngoài\n",
    "    if verbose:\n",
    "        print('BPR matrix with %d stored elements' % bpr_mat.nnz)\n",
    "        print('Train matrix with %d stored elements' % train.nnz)\n",
    "        print('Test matrix with %d stored elements' % test.nnz)\n",
    "    return train, test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "BPR matrix with 82520 stored elements\n",
      "Train matrix with 65641 stored elements\n",
      "Test matrix with 16879 stored elements\n"
     ]
    }
   ],
   "source": [
    "bpr_train, bpr_test = split_to_train_test(bpr_mat, test_ratio=0.2, verbose=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict_bpr(W, H, user=None):\n",
    "    \"\"\"\n",
    "    Hàm trả về X_hat\n",
    "\n",
    "    :param W: ma trận W từ MF\n",
    "    :param H: ma trận H từ MF\n",
    "    :param user: người dùng (nếu None mặt định trả về tất cả)\n",
    "\n",
    "    :return predict_scores: điểm dự đoán từ BPR MF\n",
    "    \"\"\"\n",
    "    if user is None:\n",
    "        return W @ H.T\n",
    "    else:\n",
    "        return W[user] @ H.T\n",
    "\n",
    "def recommend_bpr(bpr_matrix, predict_score, user, n_rmd_items=None):\n",
    "    \"\"\"\n",
    "    Dự đoán những sản phẩm mà người dùng muốn mua\n",
    "    Những sản phẩm nào đã thích rồi thì không trả về nữa\n",
    "    Trả về index theo bpr_matrix (đánh từ 0)\n",
    "\n",
    "    :param bpr_matrix: ma trận bpr hiện tại\n",
    "    :param predict_score: điểm dự đoán các item\n",
    "    :param user: số thứ tự người dùng của predict score\n",
    "    :param n_rmd_items: số lượng sản phẩm trả về, mặc định tất cả\n",
    "\n",
    "    :return rmd_items: danh sách các sản phẩm khuyến nghị\n",
    "    \"\"\"\n",
    "    # Số lượng sản phẩm\n",
    "    n_items = bpr_matrix.shape[1]\n",
    "    # những sản phẩm đã thích rồi\n",
    "    liked_items = bpr_matrix[user].indices\n",
    "    scores = predict_score.copy()\n",
    "\n",
    "    # index ban đầu khi chưa sắp xếp\n",
    "    sort_index = np.arange(0, n_items)\n",
    "\n",
    "    # Xóa các sản phẩm đã mua\n",
    "    sort_index = np.delete(sort_index, liked_items)\n",
    "    scores = np.delete(scores, liked_items)\n",
    "\n",
    "    # sắp xếp và trả về theo số thứ tự của score\n",
    "    arg_sort = np.argsort(-scores)\n",
    "\n",
    "    # dùng sort_index để lấy số thứ tự ban đầu\n",
    "    rmd_items = sort_index[arg_sort]\n",
    "\n",
    "    if len(rmd_items) >= n_rmd_items and n_rmd_items is not None:\n",
    "        rmd_items = rmd_items[: n_rmd_items]\n",
    "    return rmd_items\n",
    "\n",
    "def auc_score(predict_mat, bpr_mat):\n",
    "    \"\"\"\n",
    "    Tính Area under the ROC curve (AUC)\n",
    "    cho bài toán hệ khuyến nghị\n",
    "\n",
    "    :param predict_mat: ma trận dữ đoán bpr mf\n",
    "    :param bpr_mat: ma trận train hoặc test\n",
    "    :return auc: area under the roc curve\n",
    "    \"\"\"\n",
    "    auc = 0.0\n",
    "    n_users, n_items = bpr_mat.shape\n",
    "\n",
    "    # u và row tương ứng user và bp\n",
    "    for u in range(n_users):\n",
    "        y_pred = predict_mat[u]\n",
    "        y_true = np.zeros(n_items)\n",
    "        y_true[bpr_mat[u].indices] = 1\n",
    "        auc += roc_auc_score(y_true, y_pred)\n",
    "    auc /= n_users\n",
    "    return auc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def learn_bpr_mf_sgd(bpr_mat, alpha=0.01, lamb=0.01, k=12, n_iters=10000):\n",
    "    \"\"\"\n",
    "    Thuật toán học BPR MF SGD (một điểm dữ liệu duy nhất)\n",
    "\n",
    "    :param bpr_mat: ma trận bpr\n",
    "    :param alpha: hệ số learning rate\n",
    "    :param lamb: hệ số lambda của bình thường hóa regularization\n",
    "    :param k: số lượng latent factor trong bài toán MF\n",
    "    :param n_iters: số vòng lặp\n",
    "\n",
    "    :return W: ma trận W\n",
    "    :return H: ma trận H\n",
    "    \"\"\"\n",
    "    n_users, n_items = bpr_mat.shape\n",
    "    # Khởi tạo ma trận W và ma trận H\n",
    "    W = np.ones(shape=(n_users, k))\n",
    "    H = np.ones(shape=(n_items, k))\n",
    "    # Tập các sản phẩm nên khuyến nghị\n",
    "    pos = np.split(bpr_mat.indices, bpr_mat.indptr)[1:-1]\n",
    "    # Tập các sản phẩm không nên khuyến nghị\n",
    "    neg = [np.setdiff1d(np.arange(0, n_items,1), e) for e in pos]\n",
    "\n",
    "    # lặp\n",
    "    for _ in range(n_iters):\n",
    "        # ngẫu nghiên 3 bộ (u,i,j) từ D_S\n",
    "        u = np.random.randint(0, n_users)\n",
    "        i = pos[u][np.random.randint(0, len(pos[u]))]\n",
    "        j = neg[u][np.random.randint(0, len(neg[u]))]\n",
    "\n",
    "        # Tính xuij\n",
    "        xui = (W[u] * H[i]).sum()\n",
    "        xuj = (W[u] * H[j]).sum()\n",
    "        xuij = xui - xuj\n",
    "\n",
    "        # mũ tự nhiên e của xuij\n",
    "        exp_xuij = np.exp(xuij)\n",
    "\n",
    "        # sgd cho tham số Theta (W và H)\n",
    "        W[u] = W[u] + alpha * ( exp_xuij / (1+exp_xuij) * (H[i] - H[j]) + lamb * W[u])\n",
    "        H[i] = H[i] + alpha * ( exp_xuij / (1+exp_xuij) * W[u] + lamb * H[i])\n",
    "        H[j] = H[j] + alpha * ( exp_xuij / (1+exp_xuij) * (-W[u]) + lamb * H[j])\n",
    "    return W, H"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def learn_bpr_mf_mini_batch(bpr_mat, batch=100, alpha=0.01, lamb=0.01, k=12, n_iters=100):\n",
    "    \"\"\"\n",
    "    Thuật toán học BPR MF Mini Batch\n",
    "\n",
    "    :param bpr_mat: ma trận bpr\n",
    "    :param batch: số lượng điểm dữ liệu mỗi n_iters\n",
    "    :param alpha: hệ số learning rate\n",
    "    :param lamb: hệ số lambda của bình thường hóa regularization\n",
    "    :param k: số lượng latent factor trong bài toán MF\n",
    "    :param n_iters: số vòng lặp\n",
    "\n",
    "    :return W: ma trận W\n",
    "    :return H: ma trận H\n",
    "    \"\"\"\n",
    "    n_users, n_items = bpr_mat.shape\n",
    "    # Khởi tạo ma trận W và ma trận H\n",
    "    W = np.ones(shape=(n_users, k))\n",
    "    H = np.ones(shape=(n_items, k))\n",
    "    # Tập các sản phẩm nên khuyến nghị\n",
    "    # (chuyển về numpy luôn cho tiện)\n",
    "    pos = np.array(np.split(bpr_mat.indices, bpr_mat.indptr)[1:-1])\n",
    "    # Tập các sản phẩm không nên khuyến nghị\n",
    "    neg = np.array([np.setdiff1d(np.arange(0, n_items,1), e) for e in pos])\n",
    "\n",
    "    # lặp\n",
    "    for _ in range(n_iters):\n",
    "        # mỗi u,i,j là một np array index\n",
    "        u = np.random.choice(np.arange(0,n_users), batch, replace=False)\n",
    "        i = []\n",
    "        j = []\n",
    "        for users in u:\n",
    "            i.append(pos[users][np.random.randint(0, len(pos[users]))])\n",
    "            j.append(neg[users][np.random.randint(0, len(neg[users]))])\n",
    "        i = np.array(i)\n",
    "        j = np.array(j)\n",
    "\n",
    "        # Tính xuij\n",
    "        xui = (W[u] * H[i]).sum(axis=1)\n",
    "        xuj = (W[u] * H[j]).sum(axis=1)\n",
    "        xuij = xui - xuj\n",
    "\n",
    "        # mũ tự nhiên e của xuij\n",
    "        exp_xuij = np.exp(xuij).reshape(batch, 1)\n",
    "\n",
    "        # minibatch gradient descent cho Theta (W và H)\n",
    "        W[u] = W[u] + alpha * ( exp_xuij / (1+exp_xuij) * (H[i] - H[j]) + lamb * W[u])\n",
    "        H[i] = H[i] + alpha * ( exp_xuij / (1+exp_xuij) * W[u] + lamb * H[i])\n",
    "        H[j] = H[j] + alpha * ( exp_xuij / (1+exp_xuij) * (-W[u]) + lamb * H[j])\n",
    "    return W, H"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train: 0.841916\n",
      "Test: 0.828263\n"
     ]
    }
   ],
   "source": [
    "W_sgd, H_sgd = learn_bpr_mf_sgd(bpr_train, n_iters=10000, k=12)\n",
    "pred_mat_sgd = predict_bpr(W_sgd, H_sgd)\n",
    "\n",
    "print('Train: %f' % auc_score(pred_mat_sgd, bpr_train))\n",
    "print('Test: %f' % auc_score(pred_mat_sgd, bpr_test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train: 0.842083\n",
      "Test: 0.829265\n"
     ]
    }
   ],
   "source": [
    "W_mb, H_mb = learn_bpr_mf_mini_batch(bpr_train, batch=100, n_iters=100, k=12)\n",
    "pred_mat_mb = predict_bpr(W_mb, H_mb)\n",
    "\n",
    "print('Train: %f' % auc_score(pred_mat_mb, bpr_train))\n",
    "print('Test: %f' % auc_score(pred_mat_mb, bpr_test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[257 287 180  99  49]\n"
     ]
    }
   ],
   "source": [
    "u = 28\n",
    "n_rmd_items = 5\n",
    "score = predict_bpr(W_mb, H_mb, u)\n",
    "rmd_items = recommend_bpr(bpr_train, score, u, n_rmd_items)\n",
    "print(rmd_items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tham khảo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "01. Steffen Rendle, Christoph Freudenthaler, Zeno Gantner and Lars Schmidt-Thieme. BPR: Bayesian Personalized Ranking from Implicit Feedback. \n",
    "02. Weike Panand, Li Chen. GBPR: Group Preference Based Bayesian Personalized Ranking for One-Class Collaborative Filtering. Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. https://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/viewFile/6316/7124\n",
    "03. Michael D. Ekstrand, Joseph A Konstan. Personalized Ranking (with Daniel Kluver). Matrix Factorization and Advanced Techniques - University of Minnesota. https://www.coursera.org/lecture/matrix-factorization/personalized-ranking-with-daniel-kluver-s3XJo\n",
    "04. Kim Falk. Practical Recommender Systems. Manning Publications.\n",
    "05. Ethen (MingYu) Liu. Bayesian Personalized Ranking. http://ethen8181.github.io/machine-learning/recsys/4_bpr.html\n",
    "06. Alfredo Láinez Rodrigo, Luke de Oliveira. Distributed Bayesian Personalized Ranking in Spark. https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/rodrigo_oliveira.pdf"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}