Collaborative_Filter.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1682L, 943L) (1682L, 943L)\n[[5 4 0 0 4]\n [3 0 0 0 3]\n [4 0 0 0 0]\n [3 0 0 0 0]\n [3 0 0 0 0]]\nAverage rating for movie 1 (Toy Story): 3.878319 / 5\n"
     ]
    }
   ],
   "source": [
    "#本文是协同过滤模型用于电影推荐\n",
    "import scipy.io as sio\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "#  Y is a 1682x943 matrix, containing ratings (1-5) of 1682 movies on \n",
    "#  943 users\n",
    "#  R is a 1682x943 matrix, where R(i,j) = 1 if and only if user j gave a\n",
    "#  rating to movie i\n",
    "data = sio.loadmat('ex8_movies.mat')\n",
    "\n",
    "Y = data['Y'] #[1682*943] movies * users\n",
    "R = data['R'] #[1682*943] 0 or 1\n",
    "print Y.shape,R.shape\n",
    "print Y[0:5,0:5]\n",
    "print 'Average rating for movie 1 (Toy Story): %f / 5'\\\n",
    "      %(np.mean(Y[0,R[0,:]==1]))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1682L, 10L) (943L, 10L)\n[[1682]] [[943]] [[10]]\n"
     ]
    }
   ],
   "source": [
    "#load movies data set\n",
    "params = sio.loadmat('ex8_movieParams.mat')\n",
    "X = params['X']\n",
    "Theta = params['Theta']\n",
    "num_users = params['num_users']\n",
    "num_movies = params['num_movies']\n",
    "num_features = params['num_features']\n",
    "print X.shape,Theta.shape\n",
    "print num_movies,num_users,num_features\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "reg = 0,this value should be about 22.22\n22.2246037257\nreg = 1.5,this value should be about 31.34\n31.3440562443\n"
     ]
    }
   ],
   "source": [
    "#compute the cost\n",
    "#note:no x0 = 1, no 1/m  !!!!!!!!没有x0=1,也没有除以m\n",
    "def computeCost(x,theta,y,r,reg=0):\n",
    "    j = 0\n",
    "    x_grad = np.zeros_like(x)\n",
    "    theta_grad = np.zeros_like(theta)\n",
    "    \n",
    "    j_temp = (x.dot(theta.T) - y)**2\n",
    "    j = 0.5 * np.sum(j_temp[r==1]) + 0.5 * reg * np.sum(theta**2) \\\n",
    "        + 0.5 * reg * np.sum(x**2) \n",
    "    \n",
    "    x_grad = np.dot(((x.dot(theta.T)-y)*r),theta) + reg * x\n",
    "    theta_grad = np.dot(((x.dot(theta.T)-y)*r).T,x) + reg * theta\n",
    "    \n",
    "    return j,x_grad,theta_grad\n",
    "    \n",
    "#Reduce the data set size so that this runs faster\n",
    "#用一个小模型测试一下算法是否正确\n",
    "nu, nm, nf = 4, 5, 3\n",
    "X1 = X[0:nm,0:nf]\n",
    "Theta1 = Theta[0:nu,0:nf]\n",
    "Y1 = Y[0:nm,0:nu]\n",
    "R1 = R[0:nm,0:nu]\n",
    "\n",
    "#check the cost\n",
    "J,x_g,theta_g = computeCost(X1,Theta1,Y1,R1,0)\n",
    "print\"reg = 0,this value should be about 22.22\\n\",J\n",
    "\n",
    "J2,x_g2,theta_g2 = computeCost(X1,Theta1,Y1,R1,1.5)\n",
    "print\"reg = 1.5,this value should be about 31.34\\n\",J2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#compute numerical_gradient数值计算梯度\n",
    "def eval_numerical_gradient(f, x, verbose=True, h=0.00001):\n",
    "    \"\"\" \n",
    "    a naive implementation of numerical gradient of f at x \n",
    "    - f should be a function that takes a single argument\n",
    "    - x is the point (numpy array) to evaluate the gradient at\n",
    "    \"\"\" \n",
    "    \n",
    "    fx = f(x) # evaluate function value at original point\n",
    "    grad = np.zeros_like(x)\n",
    "    # iterate over all indexes in x\n",
    "    it = np.nditer(x, flags=['multi_index'], op_flags=['readwrite'])\n",
    "    while not it.finished:\n",
    "        \n",
    "        # evaluate function at x+h\n",
    "        ix = it.multi_index\n",
    "        oldval = x[ix]\n",
    "        x[ix] = oldval + h # increment by h\n",
    "        fxph = f(x) # evalute f(x + h)\n",
    "        x[ix] = oldval - h\n",
    "        fxmh = f(x) # evaluate f(x - h)\n",
    "        x[ix] = oldval # restore\n",
    "        \n",
    "        # compute the partial derivative with centered formula\n",
    "        grad[ix] = (fxph - fxmh) / (2 * h) # the slope\n",
    "        if verbose:\n",
    "          print ix, grad[ix]\n",
    "        it.iternext() # step to next dimension\n",
    "    return grad\n",
    "\n",
    "def rel_error(x, y):\n",
    "  \"\"\" returns relative error \"\"\"\n",
    "  return np.max(np.abs(x - y) / (np.maximum(1e-8, np.abs(x) + np.abs(y))))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ -1.4485962   -2.38226893   1.70710777  -1.4485962   -2.38226893\n    1.70710777]\n [ -2.18041855   6.88240991  -7.8848515   -2.18041855   6.88240991\n   -7.8848515 ]\n [  8.23023857  -1.02191424  -4.0025453    8.23023857  -1.02191424\n   -4.0025453 ]\n [ 14.13447555  -5.85369614  -5.0379881   14.13447555  -5.85369614\n   -5.0379881 ]]\n[[  0.73826162   2.09184519  -0.48151182   0.73826162   2.09184519\n   -0.48151182]\n [  1.18589767   1.21853183  -1.81195221   1.18589767   1.21853183\n   -1.81195221]\n [ -5.30305981   8.71447069 -11.02419571  -5.30305981   8.71447069\n  -11.02419571]\n [ 10.43018863  -4.31754416  -6.23177659  10.43018863  -4.31754416\n   -6.23177659]\n [  0.27896481  -1.40228679   1.58240075   0.27896481  -1.40228679\n    1.58240075]]\nx max relative error: 6.712613e-11\ntheta max relative error: 1.661263e-10\n"
     ]
    }
   ],
   "source": [
    "#check the gradient ,进行梯度检查，一般都是产生小数字，小模型，因为数值梯度计算量太大\n",
    "#create the small data\n",
    "\n",
    "x_t = np.random.rand(4,3)\n",
    "theta_t = np.random.rand(5,3)\n",
    "y_t = x_t.dot(theta_t.T) #4,5\n",
    "y_t[np.random.rand(*y_t.shape)>0.5] = 0\n",
    "r_t = np.zeros_like(y_t)\n",
    "r_t[y_t != 0] = 1\n",
    "#print y_t,r_t\n",
    "\n",
    "X_t = np.random.randn(*x_t.shape)\n",
    "Theta_t = np.random.randn(*theta_t.shape)\n",
    "nu_t = 5\n",
    "nm_t = 4\n",
    "nf_t = 3\n",
    "\n",
    "\n",
    "j,x_grad,theta_grad = computeCost(X_t,Theta_t,y_t,r_t,1.5)\n",
    "f = lambda W:computeCost(X_t,Theta_t,y_t,r_t,1.5)[0] #f = J(x)\n",
    "x_grad1 = eval_numerical_gradient(f,X_t , verbose=False, h=0.00001)\n",
    "theta_grad1 = eval_numerical_gradient(f, Theta_t, verbose=False, h=0.00001)\n",
    "#放在一起对比一下，前三列是x_grad，后三列是x_grad1\n",
    "display_X = np.hstack((x_grad,x_grad1))\n",
    "print display_X\n",
    "display_Theta = np.hstack((theta_grad,theta_grad1))\n",
    "print display_Theta\n",
    "\n",
    "print '%s max relative error: %e' % ('x', rel_error(x_grad, x_grad1))\n",
    "print '%s max relative error: %e' % \\\n",
    "      ('theta', rel_error(theta_grad, theta_grad1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Toy Story (1995) ', 'GoldenEye (1995) ', 'Four Rooms (1995) ', 'Get Shorty (1995) ', 'Copycat (1995) ']\n"
     ]
    }
   ],
   "source": [
    "def load_data(filename):#导入电影数据\n",
    "    movieList = []\n",
    "    file = open(filename)\n",
    "    for line in file.readlines():\n",
    "        lineArr = line.strip().split(' ')\n",
    "        col_num = len(lineArr)\n",
    "        temp = ''\n",
    "        for i in xrange(col_num):\n",
    "            if i==0:\n",
    "                continue\n",
    "            temp= temp + lineArr[i] + ' '\n",
    "        movieList.append(temp)\n",
    "    return movieList\n",
    "\n",
    "movieList = load_data('movie_ids.txt')\n",
    "print movieList[:5]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Rated 4 for Toy Story (1995) \nRated 3 for Twelve Monkeys (1995) \nRated 5 for Usual Suspects, The (1995) \nRated 4 for Outbreak (1995) \nRated 5 for Shawshank Redemption, The (1994) \nRated 3 for While You Were Sleeping (1995) \nRated 5 for Forrest Gump (1994) \nRated 2 for Silence of the Lambs, The (1991) \nRated 4 for Alien (1979) \nRated 5 for Die Hard 2 (1990) \nRated 5 for Sphere (1998) \n"
     ]
    }
   ],
   "source": [
    "#Entering ratings for a new user\n",
    "my_ratings = np.zeros((1682,1))\n",
    "my_ratings[0] = 4\n",
    "my_ratings[97] = 2\n",
    "my_ratings[6] = 3\n",
    "my_ratings[11]= 5\n",
    "my_ratings[53] = 4\n",
    "my_ratings[63]= 5\n",
    "my_ratings[65]= 3\n",
    "my_ratings[68] = 5\n",
    "my_ratings[182] = 4\n",
    "my_ratings[225] = 5\n",
    "my_ratings[354]= 5\n",
    "for i in range(1682):\n",
    "    if my_ratings[i]>0:\n",
    "        print \"Rated %d for %s\" %(my_ratings[i],movieList[i])\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1682L, 944L) (1682L, 944L)\n(1682L, 10L)\n(944L, 10L)\n"
     ]
    }
   ],
   "source": [
    "#Learning Movie Ratings\n",
    "#将新的用户的评分数据放入数据集合,进行训练\n",
    "#Add our own ratings to the data matrix\n",
    "YY = np.hstack((my_ratings,Y))\n",
    "RR = np.hstack((my_ratings!=0,R))\n",
    "print YY.shape,RR.shape\n",
    "#Normalize Ratings\n",
    "#进行数值归一化\n",
    "def normalizeRatings(y,r):\n",
    "    m,n = y.shape\n",
    "    ymean = np.zeros((m,1))\n",
    "    ynorm = np.zeros_like(y)\n",
    "    for i in xrange(m):\n",
    "        idx = np.where(r[i,:]==1)\n",
    "        ymean[i] = np.mean(y[i,idx])\n",
    "        ynorm[i,idx] = y[i,idx] - ymean[i]\n",
    "        \n",
    "    return ymean,ynorm\n",
    "    \n",
    "Ymean,Ynorm = normalizeRatings(YY,RR)\n",
    "\n",
    "num_users1 = YY.shape[1]\n",
    "num_movies1 = YY.shape[0]\n",
    "num_features1 = 10\n",
    "#Set Initial Parameters (Theta, X)\n",
    "XX = np.random.randn(num_movies1,num_features1)\n",
    "TTheta = np.random.randn(num_users1,num_features1)\n",
    "print XX.shape\n",
    "print TTheta.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Warning: Maximum number of iterations has been exceeded.\n         Current function value: 27696.300753\n         Iterations: 100\n         Function evaluations: 149\n         Gradient evaluations: 149\n"
     ]
    }
   ],
   "source": [
    "from scipy import optimize\n",
    "#还是使用优化算法去训练\n",
    "\n",
    "args = (Ynorm,RR,num_users1,num_movies1,num_features1,1.5)\n",
    "params = np.hstack((XX.ravel(),TTheta.ravel())).ravel()\n",
    "#we use the scipy.optimize.fmin_cg,so we need to change the \n",
    "#function computeCost(),beacause x must be 1-D\n",
    "def Cost(params,*args):\n",
    "    '''now params is 1-D,include [x,theta]'''\n",
    "    y,r,nu,nm,nf,reg = args\n",
    "    j = 0\n",
    "    x = params[0:nm*nf].reshape(nm,nf)\n",
    "    theta = params[nm*nf:].reshape(nu,nf)\n",
    "    \n",
    "    j_temp = (x.dot(theta.T) - y)**2\n",
    "    j = 0.5 * np.sum(j_temp[r==1]) + 0.5 * reg * np.sum(theta**2) \\\n",
    "        + 0.5 * reg * np.sum(x**2) \n",
    "    \n",
    "    return j\n",
    "\n",
    "def grad(params,*args):\n",
    "    y,r,nu,nm,nf,reg = args\n",
    "    #unfold into x and theta\n",
    "    x = params[0:nm*nf].reshape(nm,nf)\n",
    "    theta = params[nm*nf:].reshape(nu,nf)\n",
    "    x_grad = np.zeros_like(x)\n",
    "    theta_grad = np.zeros_like(theta)\n",
    "    x_grad = np.dot(((x.dot(theta.T)-y)*r),theta) + reg * x\n",
    "    theta_grad = np.dot(((x.dot(theta.T)-y)*r).T,x) + reg * theta\n",
    "    #fold the x_grad and theta_grad\n",
    "    g = np.hstack((x_grad.ravel(),theta_grad.ravel())).ravel()\n",
    "    return g\n",
    "\n",
    "    \n",
    "res = optimize.fmin_cg(Cost,x0=params,fprime=grad,args=args,maxiter=100)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1682L, 10L) (944L, 10L)\n(1682L, 944L)\n[ 3.83399475  3.34586129  4.46180229  3.76026786  3.44922026]\nfavorite 1 score is 5,for:Return of the Jedi (1983) \nfavorite 2 score is 5,for:Star Wars (1977) \nfavorite 3 score is 5,for:Empire Strikes Back, The (1980) \nfavorite 4 score is 5,for:Independence Day (ID4) (1996) \nfavorite 5 score is 5,for:Renaissance Man (1994) \nfavorite 6 score is 5,for:Star Kid (1997) \nfavorite 7 score is 5,for:Marlene Dietrich: Shadow and Light (1996) \nfavorite 8 score is 5,for:Saint of Fort Washington, The (1993) \nfavorite 9 score is 5,for:Santa with Muscles (1996) \nfavorite 10 score is 5,for:Someone Else's America (1995) \n"
     ]
    }
   ],
   "source": [
    "#get the bestX,bestTheta\n",
    "#改变一下参数的shape\n",
    "bestX = res[0:num_movies1*num_features1].reshape(num_movies1,num_features1)\n",
    "bestTheta = res[num_movies1*num_features1:].reshape(num_users1,num_features1)\n",
    "\n",
    "\n",
    "print bestX.shape,bestTheta.shape\n",
    "#预测一下分数\n",
    "score = bestX.dot(bestTheta.T) + Ymean\n",
    "#只有第一行是新用户的分数\n",
    "my_score = score[:,0]  #line 1 is my scoce\n",
    "print score.shape\n",
    "print my_score[:5]\n",
    "#排序，推荐最高的分数的电影给新用户\n",
    "sort_index = my_score.argsort()\n",
    "favorite = 10\n",
    "for i in xrange(favorite):\n",
    "    print \"favorite %d score is %d,for:%s\" \\\n",
    "          %(i+1,my_score[sort_index[-(i+1)]],movieList[sort_index[-(i+1)]])\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}