5. Recommender Systems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width: 100%; overflow: hidden;\">\n",
    "    <div style=\"width: 150px; float: left;\"> <img src=\"https://raw.githubusercontent.com/DataForScience/Networks/master/data/D4Sci_logo_ball.png\" alt=\"Data For Science, Inc\" align=\"left\" border=\"0\" width=160px> </div>\n",
    "    <div style=\"float: left; margin-left: 10px;\"> <h1>Graphs and Networks</h1>\n",
    "<h1>Lesson V - Recommender Systems</h1>\n",
    "        <p>Bruno Gonçalves<br/>\n",
    "        <a href=\"http://www.data4sci.com/\">www.data4sci.com</a><br/>\n",
    "            @bgoncalves, @data4sci</p></div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from pprint import pprint\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt \n",
    "\n",
    "import watermark\n",
    "\n",
    "%load_ext watermark\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Watermark the notebook with current versions of all loaded libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Python implementation: CPython\n",
      "Python version       : 3.8.5\n",
      "IPython version      : 7.19.0\n",
      "\n",
      "Compiler    : Clang 10.0.0 \n",
      "OS          : Darwin\n",
      "Release     : 21.6.0\n",
      "Machine     : x86_64\n",
      "Processor   : i386\n",
      "CPU cores   : 16\n",
      "Architecture: 64bit\n",
      "\n",
      "Git hash: e2a121886d5fb3c11344fccd2cf35c76180f7246\n",
      "\n",
      "matplotlib: 3.3.2\n",
      "numpy     : 1.19.2\n",
      "watermark : 2.1.0\n",
      "json      : 2.0.9\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%watermark -n -v -m -g -iv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load default figure style"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.style.use('./d4sci.mplstyle')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's use this simple example, where everything is easy to visualize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"data/bipartite.png\" width='400px'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We start by defining the adjacency matrix of our bipartite network. This is not the most efficient graph representation, but it is the most convenient in our case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = np.zeros((8, 6), dtype='int')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rows correspond to 'x' nodes and columns to 'y' nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "A[0, 0]=1\n",
    "A[0, 1]=1\n",
    "A[1, 0]=1\n",
    "A[1, 1]=1\n",
    "A[1, 3]=1\n",
    "A[2, 2]=1\n",
    "A[2, 4]=1\n",
    "A[3, 0]=1\n",
    "A[3, 3]=1\n",
    "A[4, 2]=1\n",
    "A[4, 4]=1\n",
    "A[5, 2]=1\n",
    "A[5, 5]=1\n",
    "A[6, 4]=1 \n",
    "A[6, 5]=1\n",
    "A[7, 4]=1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The adjacency matrix is then:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "array([[1, 1, 0, 0, 0, 0],\n",
      "       [1, 1, 0, 1, 0, 0],\n",
      "       [0, 0, 1, 0, 1, 0],\n",
      "       [1, 0, 0, 1, 0, 0],\n",
      "       [0, 0, 1, 0, 1, 0],\n",
      "       [0, 0, 1, 0, 0, 1],\n",
      "       [0, 0, 0, 0, 1, 1],\n",
      "       [0, 0, 0, 0, 1, 0]])\n"
     ]
    }
   ],
   "source": [
    "pprint(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(8, 6)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And we can easily calculate the degree of each kind of nodes as well, by simply summing over the rows or columns:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "kx = A.sum(axis=1)\n",
    "ky = A.sum(axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2, 3, 2, 2, 2, 2, 2, 1])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([3, 2, 3, 2, 4, 2])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ky"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The X and Y one-mode projections are:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.dot(A, A.T)\n",
    "Y = np.dot(A.T, A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "array([[2, 2, 0, 1, 0, 0, 0, 0],\n",
      "       [2, 3, 0, 2, 0, 0, 0, 0],\n",
      "       [0, 0, 2, 0, 2, 1, 1, 1],\n",
      "       [1, 2, 0, 2, 0, 0, 0, 0],\n",
      "       [0, 0, 2, 0, 2, 1, 1, 1],\n",
      "       [0, 0, 1, 0, 1, 2, 1, 0],\n",
      "       [0, 0, 1, 0, 1, 1, 2, 1],\n",
      "       [0, 0, 1, 0, 1, 0, 1, 1]])\n"
     ]
    }
   ],
   "source": [
    "pprint(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "array([[3, 2, 0, 2, 0, 0],\n",
      "       [2, 2, 0, 1, 0, 0],\n",
      "       [0, 0, 3, 0, 2, 1],\n",
      "       [2, 1, 0, 2, 0, 0],\n",
      "       [0, 0, 2, 0, 4, 1],\n",
      "       [0, 0, 1, 0, 1, 2]])\n"
     ]
    }
   ],
   "source": [
    "pprint(Y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And we can see that the y-projection neatly splits into two disconnected graphs, as expected"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[3, 2, 2, 0, 0, 0],\n",
       "       [2, 2, 1, 0, 0, 0],\n",
       "       [2, 1, 2, 0, 0, 0],\n",
       "       [0, 0, 0, 3, 2, 1],\n",
       "       [0, 0, 0, 2, 4, 1],\n",
       "       [0, 0, 0, 1, 1, 2]])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "order = [0, 1, 3, 2, 4, 5]\n",
    "Y[order, :][:, order]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Similarity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us definie the similarity between two users (X) or items (Y) to simply be the fraction of edges user x shares with user y. For convenience, we supply the one-mode X projection directly"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def similarity(X, kx):\n",
    "    S = X.copy().astype('float')\n",
    "    \n",
    "    for i in range(X.shape[0]):\n",
    "        for j in range(X.shape[1]):\n",
    "            S[i, j]/= np.min([kx[i], kx[j]])\n",
    "\n",
    "    return S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our similarity is then:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1.  1.  0.  0.5 0.  0.  0.  0. ]\n",
      " [1.  1.  0.  1.  0.  0.  0.  0. ]\n",
      " [0.  0.  1.  0.  1.  0.5 0.5 1. ]\n",
      " [0.5 1.  0.  1.  0.  0.  0.  0. ]\n",
      " [0.  0.  1.  0.  1.  0.5 0.5 1. ]\n",
      " [0.  0.  0.5 0.  0.5 1.  0.5 0. ]\n",
      " [0.  0.  0.5 0.  0.5 0.5 1.  1. ]\n",
      " [0.  0.  1.  0.  1.  0.  1.  1. ]]\n"
     ]
    }
   ],
   "source": [
    "S = similarity(X, kx)\n",
    "print(S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Naturally, this symmilarity metric is symmetric"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(S-S.T).mean()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can predict scores for all user/item pairs. The score for each user-item pair will be the average similarity of all users that have "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict_score(A, S):\n",
    "    v = np.dot(S, A)\n",
    "    norms = S.sum(axis=0)-np.diag(S)\n",
    "    \n",
    "    v = v/norms.reshape(-1,1)\n",
    "\n",
    "    return v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The predicted scores are then:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1.67 1.33 0.   1.   0.   0.  ]\n",
      " [1.5  1.   0.   1.   0.   0.  ]\n",
      " [0.   0.   0.83 0.   1.17 0.33]\n",
      " [1.67 1.   0.   1.33 0.   0.  ]\n",
      " [0.   0.   0.83 0.   1.17 0.33]\n",
      " [0.   0.   1.33 0.   1.   1.  ]\n",
      " [0.   0.   0.6  0.   1.2  0.6 ]\n",
      " [0.   0.   0.67 0.   1.33 0.33]]\n"
     ]
    }
   ],
   "source": [
    "v = predict_score(A, S)\n",
    "print(v.round(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, we not only have scores for the items that each user already rated, but also for other items as well:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 3],\n",
       "       [2, 5],\n",
       "       [3, 1],\n",
       "       [4, 5],\n",
       "       [5, 4],\n",
       "       [6, 2],\n",
       "       [7, 2],\n",
       "       [7, 5]])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.transpose(np.nonzero(np.sign(v)-A)) # Get the coordinates of the non-zero elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From this matrix we would know to recommend **y4** to **x1**, **y6** to **x3**, etc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"width: 100%; overflow: hidden;\">\n",
    "     <img src=\"data/D4Sci_logo_full.png\" alt=\"Data For Science, Inc\" align=\"center\" border=\"0\" width=300px> \n",
    "</div>"
   ]
  }
 ],
 "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.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}