Hugo Palmer - Test technique Data Scientist.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Growth Data Scientist – Test technique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Travail réalisé par Hugo Palmer, dans le cadre d'une candidature chez Deezer.\n",
    "\n",
    "Mise en forme dans le Jupyter Notebook, code: Python 3.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Importation des librairies classiques\n",
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Profil d'écoutes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Génération de fichiers d'écoutes aléatoires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comme les fichiers de données ne sont pas fournis, je crée une fonction qui les génère automatiquement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def generate_file_day(nb_users=20, nb_artists=10, nb_lines=1000):\n",
    "    countries = ['FR', 'UK']\n",
    "    id_users = np.random.randint(nb_users, size=(nb_lines))\n",
    "    #we affect to each user a country. We assume they do not change of country the same day\n",
    "    country_of_user = np.random.choice(countries, size=(nb_users), p=[0.7, 0.3])\n",
    "    id_countries = [country_of_user[id_users[i]] for i in range(nb_lines)]\n",
    "    \n",
    "    id_tracks = np.random.randint(nb_artists*10, size=(nb_lines))\n",
    "    #we assume that the artist of track_id is: track_id%nb_artists\n",
    "    id_artists = id_tracks % nb_artists\n",
    "    \n",
    "    # creates the dictionnary to prepare the creation of the dataframe\n",
    "    d = {'user_id':id_users, 'country': id_countries, 'artist_id':id_artists, 'track_id':id_tracks}\n",
    "    data = pd.DataFrame(data=d)\n",
    "    \n",
    "    return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "data1 = generate_file_day()\n",
    "data2 = generate_file_day()\n",
    "data3 = generate_file_day()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Index(['artist_id', 'country', 'track_id', 'user_id'], dtype='object')"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data1.columns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Définition d'un profil d'écoutes par utilisateur"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous supposons que les utilisateurs ne changent pas d'un jour à l'autre (cependant, cela ne serait pas très compliqué à prendre en compte si besoin). Nous définissons une table :\n",
    "- l'index est le user_id\n",
    "- l'unique colonne est une liste:\n",
    "        - chaque élément de cette liste est un couple d'integer: \n",
    "            * le track_id\n",
    "            * le nombre de fois que ce track a été écouté dans l'histoire d'écoute de cet user_id\n",
    "Ainsi, chaque fois que nous devons mettre à jour le profil d'utilisateur avec un fichier de logs d'une journée, pour chaque ligne du fichier log, on accède à la ligne correspondante dans le profil, on ajoute le track_id s'il n'est pas dans la liste de morceaux déjà écoutés, ou on incrémente le nombre de fois que ce morceau a été écouté s'il était déjà présent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "users_list = np.array(range(20))\n",
    "list_dicts = [{} for i in range(20)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#takes as input a data frame line with the following columns: 'artist_id', 'country', 'track_id', 'user_id]\n",
    "def add_track_to_user(df_line, dict_user):\n",
    "    #If the track_id is not in the user profile, we add it \n",
    "    if df_line.track_id not in dict_user.keys():\n",
    "        dict_user[df_line.track_id] = 1 #initialization to 1: the track has been heard once by the user\n",
    "    else:\n",
    "        dict_user[df_line.track_id] +=1\n",
    "    return dict_user"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We read the file line per line (here it is a pandas data frame, but we do as if if was a line per line reader of a csv file)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def add_log_to_profiles(data_day):\n",
    "    for index, row in data_day.iterrows():\n",
    "        add_track_to_user(row, list_dicts[row.user_id])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "add_log_to_profiles(data1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, the history of listening of the user_id=0 is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 1, 67: 1, 4: 1, 97: 1, 72: 1, 9: 1, 10: 1, 14: 1, 79: 2, 16: 1, 81: 1, 18: 1, 83: 1, 85: 1, 87: 1, 25: 1, 90: 1, 27: 1, 29: 1, 30: 1, 96: 1, 33: 1, 99: 1, 36: 3, 39: 2, 40: 1, 78: 1, 45: 1, 46: 1, 54: 1, 57: 1, 59: 2, 60: 1, 61: 1}\n"
     ]
    }
   ],
   "source": [
    "print(list_dicts[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are able to easily update the logs when we get more data from new days:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "add_log_to_profiles(data2)\n",
    "add_log_to_profiles(data3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The history of listening of the user_id=0 is now:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: 2, 1: 1, 4: 1, 9: 2, 10: 3, 14: 4, 16: 1, 17: 1, 18: 1, 20: 1, 23: 1, 24: 1, 25: 3, 26: 1, 27: 2, 28: 2, 29: 2, 30: 2, 31: 1, 33: 1, 34: 3, 35: 1, 36: 4, 38: 1, 39: 2, 40: 1, 41: 1, 42: 1, 43: 3, 44: 4, 45: 3, 46: 2, 47: 1, 50: 2, 51: 2, 53: 1, 54: 4, 55: 1, 56: 3, 57: 4, 58: 3, 59: 3, 60: 2, 61: 2, 63: 2, 65: 2, 67: 1, 69: 1, 70: 1, 71: 1, 72: 3, 73: 2, 74: 4, 75: 2, 76: 3, 77: 1, 78: 1, 79: 2, 81: 1, 82: 1, 83: 2, 85: 3, 87: 2, 88: 1, 90: 1, 91: 1, 93: 2, 95: 1, 96: 2, 97: 3, 99: 1}\n"
     ]
    }
   ],
   "source": [
    "print(list_dicts[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Proximité d'utilisateurs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### a - Définition d'une mesure de similarité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous avons défini dans la partie précédente un profil d'écoutes pour les utilisateurs. L'étpe suivante est de le normaliser, pour obtenir une distribution de probabilités d'écoutes de chaque morceau par chaque utilisateur.\n",
    "\n",
    "Pour un utilisateur i, on définit le vecteur d'écoutes normalisé X_i, de taille [nombre de tracks dans le catalogue], tel que pour un track k, X_i[k] est le nombre d'écoutes du morceau k divisé par le nombre total de morceaux écoutés. Pour deux utilisateurs i et j, on peut alors calculer une similarité comme: \n",
    "\n",
    "s(i,j) = \\sum_{k} |X_i[k]- X_j[k]|\n",
    "\n",
    "Ainsi, deux utilisateurs écoutat souvant les mêmes morceaux seront considérés comme 'proches'."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### b - Taille, propriétés et stockage de la matrice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette matrice doit avoir les propriétés suivantes:\n",
    "    - symétrique\n",
    "    - à diagonale nulle\n",
    "    - On choisit de la normaliser sur [0,1] (c'est un parti-pris)\n",
    "    \n",
    "Par ailleurs, en la stockant sous forme de matrice, elle aurait 16M*16M= 256 000 millards d'éléments, ce qui est beaucoup trop gros pour être chargé en mémoire vive.\n",
    "\n",
    "On pourrait donc la stocker dans une base de données:\n",
    "    - index1 = utilisateur i\n",
    "    - index2 = utilisateur i\n",
    "    - value = valeur de la similarité M(i,j)\n",
    "\n",
    "Comme la matrice est symétrique, on peut ne stocker que la première moitié des données; par exemple, ne garder une ligne que si user_id(i)<=user_id(j)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### c- Trouver les utilisateurs les plus proches"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def get_random_symm_matrix(size=4):\n",
    "    similarity = np.zeros((size,size))\n",
    "    for i in range(size):\n",
    "        for j in range(size):\n",
    "            if i==j:\n",
    "                similarity[i,j] = 0\n",
    "            else: \n",
    "                similarity[i,j] = np.random.rand()\n",
    "                similarity[j,i] = similarity[i,j]\n",
    "    return similarity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "similarity = get_random_symm_matrix(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.          0.49818077  0.25763072  0.39301777  0.8052992   0.06085522\n",
      "   0.42298104  0.89364427  0.27978438  0.11747913]\n",
      " [ 0.49818077  0.          0.70803795  0.12693327  0.82916492  0.39758701\n",
      "   0.56686821  0.10121018  0.5204363   0.54685897]\n",
      " [ 0.25763072  0.70803795  0.          0.9306011   0.68520396  0.91664292\n",
      "   0.25617291  0.39568905  0.58932435  0.18085064]\n",
      " [ 0.39301777  0.12693327  0.9306011   0.          0.13623248  0.38333467\n",
      "   0.90289772  0.69267482  0.14509173  0.29646569]\n",
      " [ 0.8052992   0.82916492  0.68520396  0.13623248  0.          0.54794499\n",
      "   0.84933069  0.329232    0.75390829  0.13487226]\n",
      " [ 0.06085522  0.39758701  0.91664292  0.38333467  0.54794499  0.\n",
      "   0.85781849  0.16921563  0.96466229  0.53524898]\n",
      " [ 0.42298104  0.56686821  0.25617291  0.90289772  0.84933069  0.85781849\n",
      "   0.          0.72770393  0.74541567  0.02405212]\n",
      " [ 0.89364427  0.10121018  0.39568905  0.69267482  0.329232    0.16921563\n",
      "   0.72770393  0.          0.13046972  0.35963674]\n",
      " [ 0.27978438  0.5204363   0.58932435  0.14509173  0.75390829  0.96466229\n",
      "   0.74541567  0.13046972  0.          0.54599877]\n",
      " [ 0.11747913  0.54685897  0.18085064  0.29646569  0.13487226  0.53524898\n",
      "   0.02405212  0.35963674  0.54599877  0.        ]]\n"
     ]
    }
   ],
   "source": [
    "print(similarity)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# stores it as a dataframe (ie nearly bdd)\n",
    "def get_bdd(matrix):\n",
    "    bdd = pd.DataFrame(columns=['index1', 'index2', 'value'])\n",
    "    for i in range(len(matrix)):\n",
    "        for j in range(len(matrix)):\n",
    "            if i <= j:\n",
    "                df2 = pd.DataFrame([[i,j,matrix[i,j]]], columns=['index1', 'index2', 'value'] )\n",
    "                bdd=bdd.append(df2)\n",
    "    bdd.index1 = bdd.index1.astype(int)\n",
    "    bdd.index2 = bdd.index2.astype(int)\n",
    "    return bdd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "bdd = get_bdd(similarity)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def getSimilarUsers(user, bdd, nb_similar=3):\n",
    "    sub_data = bdd.loc[(bdd.index1==user) | (bdd.index2==user)]\n",
    "    sub_data = bdd.loc[((bdd.index1==user) | (bdd.index2==user)) & (bdd.index1!=bdd.index2)]\n",
    "    other_index = np.zeros(len(sub_data.index))\n",
    "    simil = np.zeros(len(sub_data.index))\n",
    "    i=0\n",
    "    for index, row in sub_data.iterrows():\n",
    "        if row.index1 != user:\n",
    "            other_index[i] = row.index1\n",
    "        else:\n",
    "            other_index[i] = row.index2\n",
    "        simil[i] = row.value\n",
    "        i+=1\n",
    "    return other_index[np.argsort(-simil)[:nb_similar]].astype(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4 2 6]\n"
     ]
    }
   ],
   "source": [
    "similar_1 = getSimilarUsers(1, bdd)\n",
    "print(similar_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.49818077,  0.        ,  0.70803795,  0.12693327,  0.82916492,\n",
       "        0.39758701,  0.56686821,  0.10121018,  0.5204363 ,  0.54685897])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# check: we extract the line corresponding to the user 1 from the matrix:\n",
    "similarity[1,:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.82916492,  0.70803795,  0.56686821])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "similarity[1,similar_1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Which are indeed the three highest."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Apply to a fairly high number of users"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "similarity = get_random_symm_matrix(100)\n",
    "bdd = get_bdd(similarity)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "similar_89 = getSimilarUsers(89, bdd, nb_similar=20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[56 12 63 33 66  1 99 60 84 96 73 22 43 57 10 46 25 20 26  9]\n"
     ]
    }
   ],
   "source": [
    "print(similar_89)"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}