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=\"data/D4Sci_logo_ball.png\" alt=\"Data For Science, Inc\" align=\"left\" border=\"0\"> </div>\n",
    "    <div style=\"float: left; margin-left: 10px;\"> <h1>Graphs and Networks</h1>\n",
    "<h2>Lesson V - Recommender Systems</h2>\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",
    "import heapq\n",
    "\n",
    "import numpy as np\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": [
      "numpy      1.16.2\n",
      "matplotlib 3.1.0\n",
      "watermark  1.8.1\n",
      "Sun Nov 17 2019 \n",
      "\n",
      "CPython 3.7.3\n",
      "IPython 6.2.1\n",
      "\n",
      "compiler   : Clang 4.0.1 (tags/RELEASE_401/final)\n",
      "system     : Darwin\n",
      "release    : 19.0.0\n",
      "machine    : x86_64\n",
      "processor  : i386\n",
      "CPU cores  : 8\n",
      "interpreter: 64bit\n",
      "Git hash   : f89240ab925f410093a911852114d463147d1d93\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": "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": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "kx = A.sum(axis=1)\n",
    "ky = A.sum(axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2, 3, 2, 2, 2, 2, 2, 1])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([3, 2, 3, 2, 4, 2])"
      ]
     },
     "execution_count": 9,
     "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": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.dot(A, A.T)\n",
    "Y = np.dot(A.T, A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "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": 12,
   "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": 13,
   "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": 13,
     "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": 26,
   "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": 27,
   "metadata": {},
   "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": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 29,
     "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": 30,
   "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": 34,
   "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 cna 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": 39,
   "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": 39,
     "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}