nb_correlation.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# **CUHK-STAT3009** Notebook - Correlation-based Recommender Systems\n"
      ],
      "metadata": {
        "id": "aPB8phgbTCcO"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "CshSr7MIS5BW"
      },
      "outputs": [],
      "source": [
        "# Load and pro-processed dataset\n",
        "import numpy as np\n",
        "import pandas as pd\n",
        "\n",
        "## Upload Netflix dataset in CUHK-STAT3009 Github repo\n",
        "\n",
        "train_url = \"https://raw.githubusercontent.com/statmlben/CUHK-STAT3009/main/dataset/train.csv\"\n",
        "test_url = \"https://raw.githubusercontent.com/statmlben/CUHK-STAT3009/main/dataset/test.csv\"\n",
        "\n",
        "dtrain = pd.read_csv(train_url)\n",
        "dtest = pd.read_csv(test_url)\n",
        "\n",
        "train_rating = dtrain['rating'].values\n",
        "train_rating = np.array(train_rating, dtype=float)\n",
        "train_pair = dtrain[['user_id', 'movie_id']].values\n",
        "\n",
        "test_rating = dtest['rating'].values\n",
        "test_rating = np.array(test_rating, dtype=float)\n",
        "test_pair = dtest[['user_id', 'movie_id']].values\n",
        "\n",
        "n_user = max( max(train_pair[:,0]), max(test_pair[:,0]) ) + 1\n",
        "n_item = max( max(train_pair[:,1]), max(test_pair[:,1]) ) + 1"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Implement Correlation-based (user-based) recommender systems\n",
        "\n",
        "- Method 1: store distance matrix\n",
        "\n",
        "  - Steps\n",
        "    - develop `user_co_rating` function\n",
        "    - define `user_d` function\n",
        "    - define `user_d_mat`\n",
        "    - make prediction based on Algo1\n",
        "\n",
        "- Method 2: without store distance matrix\n",
        "\n",
        "  - Steps\n",
        "    - Loop over $u$ then loop over $i \\in \\mathcal{I}_u$\n",
        "    - Compute distance for user u in the loop over u\n",
        "    - find a valid neighbor in the loop *over* $i$\n",
        "\n",
        "\n",
        "- Note\n",
        "  - time-space trade-off: [how to profiling and timing Code](https://jakevdp.github.io/PythonDataScienceHandbook/01.07-timing-and-profiling.html)?"
      ],
      "metadata": {
        "id": "s9EI5kK6TaSZ"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### `user_co_rating`: find co-rating items for two users\n",
        "\n",
        "- Structure:\n",
        "\n",
        "  - **Input**: pair of users $(u,v)$; training set \n",
        "  - **Output**: co-rating items and their ratings\n",
        "\n",
        "- Steps:\n",
        "\n",
        "  - Find all indices for $u$ and $v$\n",
        "  - Find co-rated items\n",
        "  - Find indices for co-rated items for $u$ and $v$ separately\n",
        "\n",
        "- Tips:\n",
        "\n",
        "  - save indices for all users/items"
      ],
      "metadata": {
        "id": "y9WOCvgLTrRy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# save indices for all users/items\n",
        "index_item = [np.where(train_pair[:,1] == i)[0] for i in range(n_item)]\n",
        "index_user = [np.where(train_pair[:,0] == u)[0] for u in range(n_user)]"
      ],
      "metadata": {
        "id": "vSMODttHWmut"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# test index sets\n",
        "train_pair[index_user[0]].T"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "c10vHJh8WyDf",
        "outputId": "8b7d6093-b0a6-497e-e63d-63228e1d8b25"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[   0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,\n",
              "           0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,\n",
              "           0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,\n",
              "           0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,\n",
              "           0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,\n",
              "           0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,\n",
              "           0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,\n",
              "           0],\n",
              "       [2720, 1935, 3126, 3386, 1118, 1686,  151, 1456, 2893,  571,  712,\n",
              "         586, 3148, 2306, 3295,  395, 2198, 1546, 1164, 3256,  426,  977,\n",
              "        2885, 1019, 3487, 1292, 3383, 1577, 2790, 2337, 2345,  945, 1428,\n",
              "        1306, 2977, 2531, 1133, 1778, 1473, 3276, 2157, 1501,  993, 3516,\n",
              "        2716, 2497,  453,  916, 2554, 3114, 1790, 1931, 2505, 2922, 1734,\n",
              "        1395, 3007, 1504,  133, 3058, 1423,  183,  634, 1333,  132,  467,\n",
              "         285, 1555, 2249, 1227, 3543,  229, 2685, 3150,   21, 1448, 1424,\n",
              "        2609]])"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def user_co_rating(index_u,index_v,train_pair,train_rating):\n",
        "    \"\"\"\n",
        "    Find co-rated items of two users.\n",
        "\n",
        "    Input\n",
        "    -----\n",
        "    index_u: index set of rated records for user u\n",
        "    index_v: index set of rated records for user v\n",
        "    train_pair: user-item pairs in training set\n",
        "    train_rating: ratings for `train_pair`\n",
        "\n",
        "    Output\n",
        "    ------\n",
        "    indices for co-rated items by users u and v\n",
        "    \"\"\"\n",
        "    ## Step 1: find co-rated item\n",
        "\n",
        "    # find items for u and v\n",
        "    item_u = train_pair[index_u][:,1]\n",
        "    item_v = train_pair[index_v][:,1]\n",
        "    # find co-rating items by `set`\n",
        "    item_co = list(set(item_u).intersection(set(item_v)))\n",
        "    if len(item_co) == 0:\n",
        "        return None, None\n",
        "    else:\n",
        "        ## Step 2: indices for co-rated items for both users\n",
        "        \n",
        "        # find the co-rating vectors by using `np.isin`\n",
        "        ind_co_u = np.where(np.isin(item_u, item_co))[0]\n",
        "        ind_co_v = np.where(np.isin(item_v, item_co))[0]\n",
        "\n",
        "        # Make sure the indices for both users are corresponding to the same items\n",
        "        ind_co_u = ind_co_u[np.argsort(item_u[ind_co_u])]\n",
        "        ind_co_v = ind_co_v[np.argsort(item_v[ind_co_v])]\n",
        "\n",
        "        ## alternative way to find the valid indices\n",
        "        # ind_co_u = [np.where(item_u == item_co_tmp)[0][0] for item_co_tmp in item_co]\n",
        "        # ind_co_v = [np.where(item_v == item_co_tmp)[0][0] for item_co_tmp in item_co]\n",
        "        return index_u[ind_co_u], index_v[ind_co_v]"
      ],
      "metadata": {
        "id": "VZVWjlcDTdEu"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "## test function\n",
        "ind_co_u, ind_co_v = user_co_rating(index_user[0],index_user[1],train_pair,train_rating)\n",
        "train_pair[ind_co_u].T"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "nOyUc-peXR8p",
        "outputId": "087824c3-d325-44aa-9d4b-0042db023e60"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[   0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,\n",
              "           0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,\n",
              "           0],\n",
              "       [ 133,  229,  571,  712,  916, 1118, 1133, 1306, 1448, 1456, 1501,\n",
              "        1504, 1778, 2198, 2497, 2505, 2893, 2922, 2977, 3058, 3114, 3386,\n",
              "        3543]])"
            ]
          },
          "metadata": {},
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "train_pair[ind_co_v].T"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Bm0v-khlZNJc",
        "outputId": "ce7eb81f-f3ed-4536-98ba-8be3bd55c523"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[   1,    1,    1,    1,    1,    1,    1,    1,    1,    1,    1,\n",
              "           1,    1,    1,    1,    1,    1,    1,    1,    1,    1,    1,\n",
              "           1],\n",
              "       [ 133,  229,  571,  712,  916, 1118, 1133, 1306, 1448, 1456, 1501,\n",
              "        1504, 1778, 2198, 2497, 2505, 2893, 2922, 2977, 3058, 3114, 3386,\n",
              "        3543]])"
            ]
          },
          "metadata": {},
          "execution_count": 11
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Define `user_d` function\n",
        "\n",
        "- Structure:\n",
        "  - Input: pair of ind of users (𝑢,𝑣); training set\n",
        "  - Output: co-rating items and their ratings\n",
        "\n",
        "- Steps:\n",
        "  - Find indices for co-rated items for 𝑢 and 𝑣 by `user_co_rating`\n",
        "  - Compute distance\n",
        "\n"
      ],
      "metadata": {
        "id": "sYSABfb8zWzY"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from scipy import spatial\n",
        "\n",
        "def user_d(index_u,index_v,train_pair,train_rating, distance='euclidean'):\n",
        "    \"\"\"\n",
        "    Find co-rated items of two users.\n",
        "\n",
        "    Input\n",
        "    -----\n",
        "    index_u: index set of rated records for user u\n",
        "    index_v: index set of rated records for user v\n",
        "    train_pair: user-item pairs in training set\n",
        "    train_rating: ratings for `train_pair`\n",
        "\n",
        "    Output\n",
        "    ------\n",
        "    distance btw users u and v\n",
        "    \"\"\"\n",
        "\n",
        "    ind_co_u, ind_co_v = user_co_rating(index_u,index_v,train_pair,train_rating)\n",
        "    if (ind_co_u is None) or (ind_co_v is None):\n",
        "      return 0.\n",
        "    rating_co_u, rating_co_v = train_rating[ind_co_u], train_rating[ind_co_v]\n",
        "    if distance == 'euclidean':\n",
        "      return np.sqrt(np.sum((rating_co_u - rating_co_v)**2)) + 1e-4\n",
        "    elif distance == 'cosine':\n",
        "      return spatial.distance.cosine(rating_co_u, rating_co_v) + 1e-4\n",
        "    elif distance == 'correlation':\n",
        "      return np.corrcoef(rating_co_u, rating_co_v) + 1e-4\n",
        "    else:\n",
        "      raise Exception(\"Sorry, distance must be euclidean, cosine, or correlation\") "
      ],
      "metadata": {
        "id": "EoNNegXSJrHX"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "## test function\n",
        "user_d(index_user[0],index_user[1],train_pair,train_rating)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kYf23LVcLpph",
        "outputId": "f16f45aa-d1ca-4252-c63e-7b66de55332b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4.69041575982343"
            ]
          },
          "metadata": {},
          "execution_count": 21
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "## test (u,v) = (0,4); None co-rated items\n",
        "print(user_co_rating(index_user[0],index_user[4],train_pair,train_rating))\n",
        "print(user_d(index_user[0],index_user[4],train_pair,train_rating))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "cB1x5a2nMBJ2",
        "outputId": "fd7efb3d-e625-47a6-f5ad-1c374cba7c30"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(None, None)\n",
            "0.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Define `user_d_mat` function\n",
        "\n",
        "- Structure:\n",
        "  - Input: training set\n",
        "  - Output: distance matrix for all users\n",
        "\n",
        "- Steps:\n",
        "  - call `user_d` in a pairwise look\n",
        "\n",
        "- Note:\n",
        "  - save the distance matrix by `scipy.sparse.lil_matrix`"
      ],
      "metadata": {
        "id": "DMh2tJhRUS1B"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from scipy.sparse import lil_matrix\n",
        "\n",
        "def user_d_mat(train_pair, train_rating, distance='euclidean'):\n",
        "    ## Compute the similarity matrix for all users\n",
        "    # sparse matrix \n",
        "    D = lil_matrix((n_user, n_user))\n",
        "    # pairwise loop over users\n",
        "    for u in range(n_user):\n",
        "        if u%500 == 0:\n",
        "            print('dis-vec for user_id %d' %u)\n",
        "        for v in range(u):\n",
        "          # we could cut more\n",
        "            if (len(index_user[u]) == 0) or (len(index_user[v]) == 0):\n",
        "                continue\n",
        "            ## to make a difference to zero\n",
        "            D[u,v] = user_d(index_user[u],index_user[v],train_pair,train_rating,distance)\n",
        "    return D + D.T"
      ],
      "metadata": {
        "id": "oj1dVMWVURr4"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "D_mat = user_d_mat(train_pair, train_rating)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WUav1aBwVU5E",
        "outputId": "cd68874a-5155-4234-a8bb-0c52477344a7"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "dis-vec for user_id 0\n",
            "dis-vec for user_id 500\n",
            "dis-vec for user_id 1000\n",
            "dis-vec for user_id 1500\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "D_mat.nnz\n",
        "print('sparseness: %.3f' %(1-D_mat.nnz/(n_user**2)))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "iXtOF2cEV2Sv",
        "outputId": "ce232c1b-cb60-4c39-e906-e1f6aa012b7d"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "sparseness: 0.621\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "D_mat[0,1]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Ozy2lgqqXUqc",
        "outputId": "edf7686b-82b1-4b43-a4cd-82114f6bb771"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4.69041575982343"
            ]
          },
          "metadata": {},
          "execution_count": 42
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Make prediction based on `D_mat`\n",
        "\n",
        "- Steps\n",
        "  - Loop over $(u,i) \\in \\Omega^{te}$\n",
        "  - Find a valid top-k neighbor with C1 & C2\n",
        "  - Average over the neighbor"
      ],
      "metadata": {
        "id": "7MR4aabrZVhq"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "glb_mean = train_rating.mean()\n",
        "pred_rating = np.zeros_like(test_rating)\n",
        "\n",
        "# loop over test records\n",
        "for j in range(len(test_pair)):\n",
        "    ## find user_id and item_id for each record in test_pair\n",
        "    user_tmp, item_tmp = test_pair[j,0], test_pair[j,1]\n",
        "    \n",
        "    # C1: find which users rated `item_tmp`\n",
        "    ## find index of all records rated item_tmp\n",
        "    index_tmp = index_item[item_tmp]\n",
        "    ## from `index_tmp`, we find the users rated `item_tmp`, and its ratings\n",
        "    rated_users = train_pair[index_tmp][:,0]\n",
        "    rated_ratings = train_rating[index_tmp]\n",
        "    # C2: compute the distance of `rated_users`\n",
        "    D_tmp = D_mat[user_tmp, rated_users].toarray()[0]\n",
        "    ## remove dissimilar users: 0 means no corated items for two users\n",
        "    rated_users = rated_users[D_tmp>0]\n",
        "    rated_ratings = rated_ratings[D_tmp>0]\n",
        "    D_tmp = D_tmp[D_tmp>0]\n",
        "    if (len(D_tmp) == 0):\n",
        "        # if no rated users or no similar users, predicted by user_mean\n",
        "        ## find the records for `user_tmp`\n",
        "        index_user_tmp = index_user[user_tmp]\n",
        "        # if no records for user_tmp\n",
        "        ## predict by glb mean\n",
        "        if len(index_user_tmp) == 0:\n",
        "            pred_rating[j] = glb_mean\n",
        "        else:\n",
        "            pred_rating[j] = train_rating[index_user_tmp].mean()\n",
        "    else:\n",
        "        # if we do find similar co-rated user\n",
        "        ## predict by average of top-10 users\n",
        "        \n",
        "        # find top 5 rated-users\n",
        "        top_index = np.argsort(D_tmp)[:50]\n",
        "        pred_rating[j] = np.mean(rated_ratings[top_index])"
      ],
      "metadata": {
        "id": "oLkqUZIcZUvc"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "## RMSE for correlation based RS\n",
        "rmse_crs = np.sqrt(np.mean((pred_rating - test_rating)**2))\n",
        "print('RMSE for correlation-base RS: %.3f' %rmse_crs)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "YjuyGHdSeAq0",
        "outputId": "f2654339-20d4-4e15-eceb-25d5904eb801"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "RMSE for correlation-base RS: 1.042\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Prediction without distance matrix\n",
        "\n",
        "- Loop over $u$ then loop over $i \\in \\mathcal{I}_u$\n",
        "- Compute distance for user u in the loop over u\n",
        "- find a valid neighbor in the loop *over* $i$"
      ],
      "metadata": {
        "id": "E6DJe7oe-eyB"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "pred_rating = np.zeros_like(test_rating)\n",
        "glb_mean = train_rating.mean()\n",
        "\n",
        "# loop over user\n",
        "for user_tmp in range(n_user):\n",
        "    if user_tmp%500 == 0:\n",
        "        print('predict for user_id %d' %user_tmp)\n",
        "    # find all records for user_tmp in test_pair\n",
        "    # which we want to make prediction in this loop\n",
        "    index_user_tmp = np.where(test_pair[:,0] == user_tmp)[0]\n",
        "    if len(index_user_tmp) == 0:\n",
        "        # no record to predict for this user, skip this user\n",
        "        continue\n",
        "    # the index of records that `user_tmp` rated in training set\n",
        "    train_index_user_tmp = index_user[user_tmp]\n",
        "    # compute weights of `user_tmp` across others\n",
        "    d_all = [user_d(index_user[user_tmp],index_user[v],train_pair,train_rating) for v in range(n_user)]\n",
        "    d_all = np.array(d_all)\n",
        "    # loop over items in test set of `user_tmp`\n",
        "    for record in index_user_tmp:\n",
        "        item_tmp = test_pair[record,1]\n",
        "        # find co-rated users on `item_tmp`\n",
        "        ## find the index of `item_tmp`\n",
        "        index_item_tmp = index_item[item_tmp]\n",
        "        ## find the rated_users of `item_tmp`\n",
        "        rated_users = train_pair[index_item_tmp][:,0]\n",
        "        rated_ratings = train_rating[index_item_tmp]\n",
        "        d_rated = d_all[rated_users]\n",
        "        ## remove the users with 0 weights, which means no shared record with user u\n",
        "        rated_users = rated_users[d_rated>0]\n",
        "        rated_ratings = rated_ratings[d_rated>0]\n",
        "        d_rated = d_rated[d_rated>0]\n",
        "        ## find the weight of rated users\n",
        "        if len(rated_users) == 0:\n",
        "            # if no rated users, then predict by user-mean\n",
        "            if len(train_index_user_tmp) == 0:\n",
        "                pred_rating[record] = glb_mean\n",
        "            else:\n",
        "                pred_rating[record] = train_rating[train_index_user_tmp].mean()\n",
        "        else:\n",
        "            top_index = np.argsort(d_rated)[:20]\n",
        "            pred_rating[record] = np.mean(rated_ratings[top_index])"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kpPi86IS-pis",
        "outputId": "da2a34cf-a12b-42f9-c5ff-d87bb74e8ac6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "predict for user_id 0\n",
            "predict for user_id 500\n",
            "predict for user_id 1000\n",
            "predict for user_id 1500\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "## RMSE for correlation based RS\n",
        "rmse_crs = np.sqrt(np.mean((pred_rating - test_rating)**2))\n",
        "print('RMSE for correlation-base RS: %.3f' %rmse_crs)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "RY7dCyPPBAR1",
        "outputId": "e465cc35-d7d1-48dd-c66a-af084d782279"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "RMSE for correlation-base RS: 1.044\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Package user-based correlation RS as a Python function"
      ],
      "metadata": {
        "id": "16MTqV40ErkJ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def cor_rs_user(train_pair, train_rating, test_pair):\n",
        "    # compute basic quatities\n",
        "    n_user, n_item = max(train_pair[:,0].max(), test_pair[:,0].max())+1, max(train_pair[:,1].max(), test_pair[:,1].max())+1\n",
        "    index_item = [np.where(train_pair[:,1] == i)[0] for i in range(n_item)]\n",
        "    index_user = [np.where(train_pair[:,0] == u)[0] for u in range(n_user)]\n",
        "\n",
        "    pred_rating = np.zeros(len(test_pair))\n",
        "    # compute glb mean\n",
        "    glb_mean = train_rating.mean()\n",
        "\n",
        "    # loop over user\n",
        "    for user_tmp in range(n_user):\n",
        "        if user_tmp%500 == 0:\n",
        "            print('predict for user_id %d' %user_tmp)\n",
        "        # find all records for user_tmp in test_pair\n",
        "        # which we want to make prediction in this loop\n",
        "        index_user_tmp = np.where(test_pair[:,0] == user_tmp)[0]\n",
        "        if len(index_user_tmp) == 0:\n",
        "            # no record to predict for this user, skip this user\n",
        "            continue\n",
        "        # the index of records that `user_tmp` rated in training set\n",
        "        train_index_user_tmp = index_user[user_tmp]\n",
        "        # compute weights of `user_tmp` across others\n",
        "        d_all = [user_d(index_user[user_tmp],index_user[v],train_pair,train_rating) for v in range(n_user)]\n",
        "        d_all = np.array(d_all)\n",
        "        # loop over items in test set of `user_tmp`\n",
        "        for record in index_user_tmp:\n",
        "            item_tmp = test_pair[record,1]\n",
        "            # find co-rated users on `item_tmp`\n",
        "            ## find the index of `item_tmp`\n",
        "            index_item_tmp = index_item[item_tmp]\n",
        "            ## find the rated_users of `item_tmp`\n",
        "            rated_users = train_pair[index_item_tmp][:,0]\n",
        "            rated_ratings = train_rating[index_item_tmp]\n",
        "            d_rated = d_all[rated_users]\n",
        "            ## remove the users with 0 weights, which means no shared record with user u\n",
        "            rated_users = rated_users[d_rated>0]\n",
        "            rated_ratings = rated_ratings[d_rated>0]\n",
        "            d_rated = d_rated[d_rated>0]\n",
        "            ## find the weight of rated users\n",
        "            if len(rated_users) == 0:\n",
        "                # if no rated users, then predict by user-mean\n",
        "                if len(train_index_user_tmp) == 0:\n",
        "                    pred_rating[record] = glb_mean\n",
        "                else:\n",
        "                    pred_rating[record] = train_rating[train_index_user_tmp].mean()\n",
        "            else:\n",
        "                top_index = np.argsort(d_rated)[:20]\n",
        "                pred_rating[record] = np.mean(rated_ratings[top_index])\n",
        "    return pred_rating"
      ],
      "metadata": {
        "id": "uUM3sK8WFLZf"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "## test function\n",
        "\n",
        "pred_rating = cor_rs_user(train_pair, train_rating, test_pair)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "HgaaMn7MF8nE",
        "outputId": "ff8c0276-c6d6-4149-c27c-4395e0360470"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "predict for user_id 0\n",
            "predict for user_id 500\n",
            "predict for user_id 1000\n",
            "predict for user_id 1500\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "## RMSE for correlation based RS\n",
        "rmse_crs = np.sqrt(np.mean((pred_rating - test_rating)**2))\n",
        "print('RMSE for correlation-base RS: %.3f' %rmse_crs)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Xbg803esHFBj",
        "outputId": "da64b5a4-eea0-49c6-84b3-2a9ebcedf123"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "RMSE for correlation-base RS: 1.044\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Sequential models: baseline + correlation RS\n",
        "\n",
        "- fit `user-mean` and `item-mean`\n",
        "- then use `correlation-based` RS"
      ],
      "metadata": {
        "id": "DO4nz4JIHnyq"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "## recall baseline methods\n",
        "\n",
        "def user_mean(train_pair, train_rating, test_pair):\n",
        "    n_user = max(train_pair[:,0].max(), test_pair[:,0].max())+1\n",
        "    pred = np.zeros(len(test_pair))\n",
        "    glb_mean_value = train_rating.mean()\n",
        "    for u in range(n_user):\n",
        "        # find the index for both train and test for user_id = u\n",
        "        ind_test = np.where(test_pair[:,0] == u)[0]\n",
        "        ind_train = np.where(train_pair[:,0] == u)[0]\n",
        "        if len(ind_test) == 0:\n",
        "            continue\n",
        "        if len(ind_train) < 3:\n",
        "            pred[ind_test] = glb_mean_value\n",
        "        else:\n",
        "            # predict as user average\n",
        "            pred[ind_test] = train_rating[ind_train].mean()\n",
        "    return pred\n",
        "\n",
        "def item_mean(train_pair, train_rating, test_pair):\n",
        "    n_item = max(train_pair[:,1].max(), test_pair[:,1].max())+1\n",
        "    pred = np.zeros(len(test_pair))\n",
        "    glb_mean_value = train_rating.mean()\n",
        "    for i in range(n_item):\n",
        "        # find the index for both train and test for item_id = i\n",
        "        ind_test = np.where(test_pair[:,1] == i)[0]\n",
        "        ind_train = np.where(train_pair[:,1] == i)[0]\n",
        "        if len(ind_test) == 0:\n",
        "            continue\n",
        "        if len(ind_train) < 3:\n",
        "            pred[ind_test] = glb_mean_value\n",
        "        else:\n",
        "            # predict as user average\n",
        "            pred[ind_test] = train_rating[ind_train].mean()\n",
        "    return pred\n",
        "\n",
        "def rmse(true_rating, pred_rating):\n",
        "  return np.sqrt(np.mean((true_rating - pred_rating)**2))"
      ],
      "metadata": {
        "id": "qVe5bkIsH_Id"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "pred_rating = user_mean(train_pair, train_rating, test_pair)\n",
        "res_rating = train_rating - user_mean(train_pair, train_rating, train_pair)\n",
        "\n",
        "print('rmse for user mean: %.3f' %rmse(test_rating, pred_rating))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0zKlhXz-IFu8",
        "outputId": "da421757-1461-4a7f-f6e9-9c6514f5053c"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "rmse for user mean: 1.013\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "## compute the residual rating\n",
        "## test_pair -> train_pair\n",
        "\n",
        "pred_res_item = user_mean(train_pair, res_rating, test_pair)\n",
        "\n",
        "res_rating = res_rating - item_mean(train_pair, res_rating, train_pair)\n",
        "pred_rating = pred_rating + pred_res_item\n",
        "print('rmse for user mean: %.3f' %rmse(test_rating, pred_rating))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9OX30dcXIZqJ",
        "outputId": "9e33b0c7-b4b2-4e05-a485-79e2bdc08b3a"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "rmse for user mean: 0.964\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "pred_res_corr = cor_rs_user(train_pair, res_rating, test_pair)\n",
        "pred_rating = pred_rating + pred_res_corr"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DOQmcvj4Ix37",
        "outputId": "9488a2eb-281e-433a-cfc1-6826628692a7"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "predict for user_id 0\n",
            "predict for user_id 500\n",
            "predict for user_id 1000\n",
            "predict for user_id 1500\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "print('rmse for user mean: %.3f' %rmse(test_rating, pred_rating))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "1XKFYeDzJus8",
        "outputId": "352556f7-bbc6-40dc-cd4d-982659543f84"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "rmse for user mean: 0.984\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## To-do list\n",
        "\n",
        "- **STAT**\n",
        "  - [ ] Understand the motivation of correlation based methods\n",
        "  - [ ] strength and weakness for each method\n",
        "  - [ ] Understand various distance\n",
        "\n",
        "- **Code**\n",
        "\n",
        "  - [ ] implement `item_co_rating`, `item_d`\n",
        "  - [ ] explore [`scipy.sparse`](https://docs.scipy.org/doc/scipy/reference/sparse.html)\n",
        "  - [ ] implement Algos 3 and 4 for item-based correlation RS"
      ],
      "metadata": {
        "id": "FmndT6Sl6Fn6"
      }
    }
  ]
}