code_and_report.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 数据挖掘第二次编程作业--推荐系统\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import print_function\n",
    "import cPickle\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import os\n",
    "import matplotlib.pyplot as plt\n",
    "import math\n",
    "import random\n",
    "from nltk.corpus import stopwords\n",
    "from nltk.tokenize import WordPunctTokenizer\n",
    "from nltk.stem.porter import PorterStemmer\n",
    "import codecs\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "DATA_FILE = \"./data/train.dat\"\n",
    "PKL_FILE = \"./data/df.pkl\"\n",
    "RENEWED_FNAME = \"./data/renewed-train.dat\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. 数据预处理分析\n",
    "\n",
    "为大致了解数据，先对数据做简要处理。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "提取出数据的前三列，即`usr id`，`item id`和`rating`数据，并存入单独文件，为便于后续处理。另外，考虑到如果时间有限，可以依据此文件做基础的基于评分数据的推荐，而忽略评论数据。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_ratings_into_file(src_fname, dst_fname):\n",
    "    \"\"\" 将训练数据的前三列，即用户id，物品id和评分提取出来，存入目标文件 \"\"\"\n",
    "    outf = open(dst_fname, 'a+')\n",
    "    with open(src_fname, 'r') as inf:\n",
    "        for line in inf.readlines():\n",
    "            items = line.split(\" \")[:3]\n",
    "            newLine = \"\"\n",
    "            for i in items:\n",
    "                newLine += (i + \" \")\n",
    "            newLine.strip()\n",
    "            newLine += '\\n'\n",
    "            outf.write(newLine)\n",
    "    outf.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def load(fname):\n",
    "    \"\"\" 将文件数据导入pandas.DataFrame。\n",
    "    如果首次导入，则将此dataFrame存入同名pkl文件，方便后续调用；如果同名pkl文件存在，则直接从此pkl文件中导入。\n",
    "    \"\"\"\n",
    "    pkl_fname = \".{}.pkl\".format(fname.split(\".\")[-2])\n",
    "    \n",
    "    if not os.path.exists(pkl_fname):\n",
    "        df = pd.read_csv(fname, sep=\"\\s+\", header=None)\n",
    "        df.columns = [\"User\", \"Item\", \"Rating\"]\n",
    "        \n",
    "        with open(pkl_fname, 'wb') as pklf:\n",
    "            cPickle.dump(df, pklf)\n",
    "    else:\n",
    "        with open(pkl_fname, 'r') as pklf:\n",
    "            df = cPickle.load(pklf)\n",
    "            \n",
    "    return df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In 'train.dat', 21443 users and 16610 items in total.\n"
     ]
    }
   ],
   "source": [
    "df = load(RENEWED_FNAME)\n",
    "\n",
    "usrs = pd.value_counts(df.User)\n",
    "items = pd.value_counts(df.Item)\n",
    "\n",
    "print(\"In 'train.dat', {} users and {} items in total.\".format(usrs.size, items.size))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "count    21443.000000\n",
       "mean        18.344728\n",
       "std         19.736327\n",
       "min          2.000000\n",
       "25%          9.000000\n",
       "50%         12.000000\n",
       "75%         20.000000\n",
       "max        562.000000\n",
       "Name: User, dtype: float64"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "usrs.describe()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "count    16610.000000\n",
       "mean        23.682480\n",
       "std         27.098671\n",
       "min          4.000000\n",
       "25%         10.000000\n",
       "50%         15.000000\n",
       "75%         26.000000\n",
       "max        533.000000\n",
       "Name: Item, dtype: float64"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "items.describe()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "经过上述处理，可以看到训练数据中，一共有21443个用户，和16610个物品，二者在量级上一致。于是，如果构建用户-物品矩阵，此矩阵维度将是 $21443\\times16610$ 。\n",
    "\n",
    "**另外，可以看到75%的用户只评论了至多20个物品；而75%的物品只被至多26个用户同时评论。**已经可以认为服从长尾分布，下面从分布图上进一步证实这一点。\n",
    "\n",
    "以下，绘制训练数据中，用户出现次数的分布图以及物品出现次数的分布图。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAtcAAAENCAYAAADEw0mJAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3XucXXV96P3Pd2ZyvwcmISSBhDuIBDQgrdjKRcUrntZarfXSw1N8WuulHp+qtc957Kl9pKd9auupx4rSI9rWayuC4gUBrXJUCBIChFsIYK4k4RJyv8x8nz/2mmSSzCR7JnvP3mvW5/16zSt7r7X2Wt8Z9Dvf+a7f77ciM5EkSZJ09DpaHYAkSZI0WlhcS5IkSQ1icS1JkiQ1iMW1JEmS1CAW15IkSVKDWFxLkiRJDWJxLUmSJDWIxbUaLiLuj4iXNvpcEfF4RFzWiPMefO6RFBGnR8TSiNgSEe8Z6etLUh/z9RGve9h8HTVPRMQpIx2b2ldXqwNQuUTE48BsYC/QAywHvgBck5m9AJn5vDrP839k5g8Od1w956rXwdds5LmH6E+A2zLz3BZdX1IFmK8b4rD5OmtP4jux731ErAZem5l3j1B8akN2rjUcr83MKdQSytXAB4FrG3mBiBjNf/idCNzfygAiorOV15c0YszXR6fufB0Rx1L7Y2Z5UyNS27O41rBl5ubMvAH4beDtEXE2HHg7MCI+GBFriltqD0XEpRHxReAE4MaI2BoRf9Lvcx+MiGXAtojoGuDW4vkRsTwinomI/xUR4/t2RET2vzUXEZ+PiI8Vrw+55sHnjogzI+KHEfFscQvydf32PR4RH4iIZRGxOSK+0v/a/R3hPLcCFwP/UMRx2gCf/1hE/F2/9/MiYltEdETESRHx7YjYFBHPRcTNB33294ufz+aI+E5EzCq2XxkRN0fEtRHxDPD+I51L0uhhvm5avr4yIq4vvpdV1OqqpyLiqb4/Oo6Ql78XEZ8ufkYPR8RZEfHeiPhlkZt/o9+1zNklYXGto5aZdwCrgZf03x4RpwN/BJxfdE5eATyemW8FfkmtozI5M/97v4+9GXg1MD0z9w5wubcU5zkZOA34szpjPNw1iYgxwI3A94FZwLuBfym+hz5vBC4HFgLnAO84+DpHOk9mXgL8GPijIo6HBwj3POCefu8XAfcXt3G/ANxErTsyC/hov2v/KfB/Aq8DuoE1wMf6neNC4JvAMcAnD3cuSaOT+br+89SZrxcB92TmCuADwNeLY4/JzL115OXFwNeBY4F7ge8U+04G/oIDf2bm7JKwuFajrAVmHrStBxgHnBURYzLz8cx89Ajn+WRmrsrMHYPs/4di/9PAX1JL7o1wITAZuDozd2fmrcC3Djr/JzNzbXHtG4GBxuDVc54jORdY1u/9on7vTwY6gc7M3JmZtwMUnZCPAG/OzBWZuZvard/z+53jbzLzhszszcxdg51L0qhnvq7/PEeyiP3NkEXA0r4ddeblj2fmLZnZNyb+3sz8+8zcA9zHgXPjzNklYXGtRpkLPN1/Q/GX/Puo/XW9ISK+HBHHH+E8q4aw/wngSOer1/HAqr5JPv3OP7ff+/X9Xm+nlpSHc55BFcl4NgeO8eufvN8CXAGsLYZ49P2CvJTaL8Y7itubzwLfBTYX+88BvnbQ5QY7l6TRzXxd/3mO5Bz25+dzOfCuYz15+Vv9jj9rgPcP9ntvzi4Ji2sdtYg4n1oy+snB+zLzXzPzImqTQhL4q75dg5xusO195vd7fQK1Dkyf7cDEfu+PG8K51wLzI6L//ydOoHYLbyiO9jxnAY9k5k7YN1HoYorOdWbempmXFsctYv+tzpnANzJzer+vaZn50og4ERjDgUn6cOeSNEqZrxt3niK3dgEri3OcTb/ONUfOy2OB/kNNzj3o8+f0f2/OLg+Law1bREyNiNcAXwb+OTPvPWj/6RFxSUSMA3YCO4C+DsGTwEnDuOy7ojbBbya1221f6bdvKfA7EdEZEZcDv37QZw93zZ9TS/Z/EhFjorae6muL720ojvY8AUwsJgd1AH9NbZzesoj4jYg4NSICmALMYH/i/QVwcUS8APb9t7miOHYRtVuN+7ozRziXpFHGfN2U8ywClhXL8U0ovvrXVXXn5YiYSu2PmoOHBN5T7Ddnl4jFtYbjxojYQu2W30eAvwV+b4DjxlFb+mkTtVt0s4APF/s+DvxZcavsA0O49r9Sm3yyEniU/RNDAN5LLTE+S+322fUHfXbQaxZj4V4LvLKI938Cb8vMBxmCBpznJ9SS64PAD6jdul2dmc8AFwE/ArZQm9RydTFGkMz8KfDfgH+LiK3Uxu5dXiT9A8YBFgY9l6RRxXw9iAacZ998mMzcBvwjsDxqa10PNS+fA6zIzO0AA3TCzdklErX/xpIkSZKOlp1rSZIkqUEsriVJkqQGsbiWJEmSGsTiWpIkSWqQriMf0r6OPfbYXLBgQavDkKQhu+uuuzZlZner4xhJ5mxJZVZv3i51cb1gwQKWLFnS6jAkacgi4olWxzDSzNmSyqzevO2wEEmSJKlBLK4lSZKkBrG4liRJkhrE4lqSJElqEItrSZIkqUEsriVJkqQGsbiWJEmSGqRyxfX/uv0xvrVsbavDkCTV4fv3r+czP3q01WFIUt0qV1x/8WdP8N371rc6DElSHW59cAP/dPtjrQ5DkupWueIaIFsdgCSpbmnSllQilSuuo9UBSJLqFiZtSSVTueIasHUtSSViypZUJpUrriOCNFVLUknYupZULtUrrlsdgCRpSBxzLalMKldcg4laksqiNubapC2pPCpXXDs5RpLKw5QtqWwqV1yDnWtJKhNztqQyqVxxHfZBJGlAEfF4RNwbEUsjYkmxbWZE3BwRjxT/zii2R0R8MiJWRMSyiHhBc2JqxlklqXkqV1wDrhYiSYO7ODPPzczFxfsPAbdk5qnALcV7gFcCpxZfVwGfblZAZmxJZVK54touiCQNyRXAdcXr64DX99v+haz5GTA9IuY0+uLebZRUNpUrrsHxe5I0iAS+HxF3RcRVxbbZmbmueL0emF28ngus6vfZ1cW2xgdl0pZUIl2tDkCS1DYuysw1ETELuDkiHuy/MzMzIoZU6RZF+lUAJ5xwwpAD8m6jpLKpZue61QFIUhvKzDXFvxuAbwAXAE/2Dfco/t1QHL4GmN/v4/OKbQef85rMXJyZi7u7u4cX17A+JUmtUbniOiIcFiJJB4mISRExpe818HLgPuAG4O3FYW8Hvlm8vgF4W7FqyIXA5n7DRxoXV6NPKElNVrlhISZqSRrQbOAbURuH0QX8a2Z+NyLuBL4aEVcCTwBvLI6/CXgVsALYDvxeswKzISKpTCpXXNeYqSWpv8xcCSwaYPtTwKUDbE/gXc2OKxx0LalkKjgspNURSJKGwtVCJJVJU4vrdnzaF3iLUZLKxJQtqUxGonPdVk/7snMtSeVhzpZUNq0YFtLSp32BXRBJKhWTtqQSaXZx3fCnfUXEVRGxJCKWbNy4ccgB+ShdSSoPc7aksmn2aiENf9pXZl4DXAOwePHiYfUznBwjSeVhxpZUJk3tXDfjaV9Hy/F7klQe5mxJZdO04rpdn/YFdkEkqUy82yipTJo5LKQtn/YVuBSfJJWFjWtJZdO04rpdn/blPUZJKhf7IZLKpHJPaAQTtSSVhf0QSWVTueLaPC1J5eJQPkllUrniGpwcI0llEbauJZVM5Ypr87QklUs6mE9SiVSuuJYklYcrPEkqm8oV1zauJalETNqSSqZyxTXYBZGkMjFlSyqTyhXXTo6RpPIIW9eSSqZyxTU4OUaSSsWULalEKldcOzlGksrDm42SyqZ6xbWJWpJKxbuNksqkcsU12LmWpLKwHyKpbCpXXDs5RpLKxYaIpDKpXHEN3mKUpLJwKJ+ksqlecW2ilqRSsR0iqUyqV1zjLUZJKguH8kkqm8oV16ZpSSqXtCMiqUQqV1yDtxglqSwizNmSyqVyxbWTYySpPEzZksqmcsU1YBtEkgYREZ0RcXdEfKt4vzAifh4RKyLiKxExttg+rni/oti/oFkxOSpEUplUrrgOwqX4JGlw7wUe6Pf+r4BPZOYpwDPAlcX2K4Fniu2fKI5rPG83SiqZ6hXX5mlJGlBEzANeDXyueB/AJcDXi0OuA15fvL6ieE+x/9LieEmqtMoV1+AtRkkaxN8BfwL0Fu+PAZ7NzL3F+9XA3OL1XGAVQLF/c3H8ASLiqohYEhFLNm7cOOSArNYllU3limv7KpJ0qIh4DbAhM+9q5Hkz85rMXJyZi7u7u4/mPA2MSpKap6vVAbSCKVqSDvFi4HUR8SpgPDAV+HtgekR0Fd3pecCa4vg1wHxgdUR0AdOApxodlA0RSWVTvc61Nxkl6RCZ+eHMnJeZC4A3Abdm5luA24A3FIe9Hfhm8fqG4j3F/luzie1lG9eSyqLpxXV7LutklpakOn0QeH9ErKA2pvraYvu1wDHF9vcDH2rGxW2ISCqbkehct9WyTt5ilKTDy8wfZuZritcrM/OCzDwlM38rM3cV23cW708p9q9sakzNPLkkNVBTi+t2XdbJJC1J5WBDRFLZNLtz3XbLOkmSysfhfJLKomnFdTsv62SOlqRysHEtqWyauRRfmy7rFA4LkaSSMW9LKoumda7bdVknuyCSVB59Y6694yipLFqxznVLl3UCzNKSVBJNmtcuSU0zIk9ozMwfAj8sXq8ELhjgmJ3AbzU7FvO0JJVPOjBEUklU7gmN4Ng9SZIkNUflimsb15JUPo7mk1QWlSuuwSQtSWXhUD5JZVO54trJMZIkSWqWyhXX4MQYSSqLcDCfpJKpXHFtmpak8nE4n6SyqFxxDSZpSSoLR/JJKpvKFdcRFteSVDYO55NUFpUrrh0YIknlYcaWVDYVLK59iIwklY13HCWVReWKa8fvSVJ59OVsa2tJZVG54hogbYFIUim4FJ+ksqlccW2alqTysSkiqSwqV1xLksrDoXySyqZyxbWJWpLKx761pLKoXHENzjqXJElSc1SuuHZyjCSVRxS3G7O3xYFIUp0qV1yDT/qSpLLoKPohvd5ylFQSlSuuffy5JJVHZ1Fd95i4JZVEJYtrSVI5dBRJ2861pLKoXHENzjqXpLLYV1w75lpSSVSuuHZCoyQdKiLGR8QdEXFPRNwfEX9ebF8YET+PiBUR8ZWIGFtsH1e8X1HsX9CMuDqL31IOC5FUFpUrrsEnfUnSAHYBl2TmIuBc4PKIuBD4K+ATmXkK8AxwZXH8lcAzxfZPFMc13P7OtXlbUjlUr7i2cS1Jh8iarcXbMcVXApcAXy+2Xwe8vnh9RfGeYv+lEY2f1bJvQqPFtaSSqF5xjWOuJWkgEdEZEUuBDcDNwKPAs5m5tzhkNTC3eD0XWAVQ7N8MHDPAOa+KiCURsWTjxo1DjskJjZLKZkjFdUTMiIhzmhXMSLBxLalKhpK3M7MnM88F5gEXAGcc7fUz85rMXJyZi7u7u4f8+Y4Oi2tJ5XLE4joifhgRUyNiJvAL4LMR8bfND62JzNGSRrGjzduZ+SxwG/ArwPSI6Cp2zQPWFK/XAPOL63UB04CnGvQt7NMZfcNCGn1mSWqOejrX0zLzOeA3gC9k5ouAy470oXaded6EIYGS1G6GnLcjojsiphevJwAvAx6gVmS/oTjs7cA3i9c3FO8p9t+aTZgtvm+1EMdcSyqJeorrroiYA7wR+NYQzt2WM8/BxrWkUW84eXsOcFtELAPuBG7OzG8BHwTeHxErqI2pvrY4/lrgmGL7+4EPNfIb6OOYa0ll03XkQ/hvwPeA2zPzzog4CXjkSB8qOhiDzTz/nWL7dcBHgU9Tm3n+0WL714F/iIhodCckcCk+SaPekPN2Zi4Dzhtg+0pq468P3r4T+K3GhDs4i2tJZXPE4jozvwZ8rd/7lcBv1nPyiOgE7gJOAT7FEGaeR0TfzPNNB53zKuAqgBNOOKGeMA6KacgfkaRSOZq83W5cik9S2dQzofG0iLglIu4r3p8TEX9Wz8nbceY5OCxE0uh2NHm73bhaiKSyqWfM9WeBDwN7YN+twzcN5SLtNPPcxrWkCjjqvN0uXC1EUtnUU1xPzMw7Dtq2d8Aj+2nXmecANkAkjXLDytvtqKP4LWXnWlJZ1DOhcVNEnEwxmiIi3gCsq+Nzc4DrinHXHcBXM/NbEbEc+HJEfAy4mwNnnn+xmHn+NE3qsrgUn6QKGG7ebjv7JjQ65lpSSdRTXL8LuAY4IyLWAI8Bv3ukD7XrzHOAdNS1pNFtWHm7He2b0GjnWlJJ1LNayErgsoiYBHRk5pbmh9U89q0ljXajKW93hKuFSCqXIxbXxbjptwELqD2YAIDMfE9TI2siGyCSRrPRlLc7XS1EUsnUMyzkJuBnwL1A+edr27qWNPqNmrztaiGSyqae4np8Zr6/6ZGMIBsgkka5UZO3+1YLcViIpLKoZym+L0bE70fEnIiY2ffV9MiaJGxdSxr9Rk3edliIpLKpp3O9G/hr4CPsf7hhAic1K6hmciU+SRUwavJ2pxMaJZVMPcX1fwFOycxNzQ5mpDTp2TSS1C5GTd728eeSyqaeYSErgO3NDmSk2LiWVAGjJm/buZZUNvV0rrcBSyPiNmBX38YyLunUxxQtaZQbNXl730NkLK4llUQ9xfX1xdeo4JhrSRUwavK2w0IklU09T2i8biQCGUnmaEmj2WjK265zLalsBi2uI+KrmfnGiLiXQ0dSZGYuam5ozeFSfJJGq9GYt/etc21XRFJJHK5z/d7i3weA/6vf9gD+e9MiGgHpqGtJo9Ooy9t9nevnduxpcSSSVJ9Bi+vMXFe8PCUzn+i/LyLOaGpUTeSYa0mj1WjM212dtdZ1rxMaJZXE4YaF/AHwh8BJEbGs364pwO3NDqyZvLsoaTQajXl7/Jhacd03sVGS2t3hhoX8K/Ad4OPAh/pt35KZTzc1qiaKcCk+SaPWqMvbY4vO9a69zmiUVA6HGxayGdgMvHnkwhkJdj8kjU6jMW9HBGM7O9htcS2pJOp5QuOo47AQSSqPMZ1hcS2pNCpXXHcEpNW1JJXG2K4O9rjQtaSSqFxx3dkRrpcqSSUytsthIZLKo3LFdUcEPS7pJEmlMbarg912riWVROWK686OcL1USSoRJzRKKpPKFdcdAdbWklQeY7s62bW3p9VhSFJdqldcO+Zakg4REfMj4raIWB4R90fEe4vtMyPi5oh4pPh3RrE9IuKTEbEiIpZFxAuaFduksZ1s321xLakcKldcd0a4WogkHWov8F8y8yzgQuBdEXEWtYfR3JKZpwK3sP/hNK8ETi2+rgI+3azApozvYuuuvc06vSQ1VOWKayc0StKhMnNdZv6ieL0FeACYC1wBXFccdh3w+uL1FcAXsuZnwPSImNOM2CaPH8PWnRbXksqhacV1u95i7OgIetO1riVpMBGxADgP+DkwOzPXFbvWA7OL13OBVf0+trrYdvC5roqIJRGxZOPGjcOKZ/K4LrbYuZZUEs3sXLflLcbOqD3+3Npakg4VEZOBfwPel5nP9d+Xta7EkLJnZl6TmYszc3F3d/ewYpoyvsvOtaTSaFpx3a63GDtqtbWTGiXpIBExhlph/S+Z+e/F5if7cnHx74Zi+xpgfr+Pzyu2NdzkcV3s2NPDXte6llQCIzLmup1uMXYU1bXjriVpv4gI4Frggcz82367bgDeXrx+O/DNftvfVgzpuxDY3C+3N9TkcV0AbNvliiGS2l/Ti+t2u8XY4bAQSRrIi4G3ApdExNLi61XA1cDLIuIR4LLiPcBNwEpgBfBZ4A+bFdjk8bXiesuuPc26hCQ1TFczT364W4yZua4Vtxg7iz8nHBYiSftl5k+AGGT3pQMcn8C7mhpUYUrRuX5ux16YMRJXlKTha+ZqIW15i7Gvc91rcS1JpdBZDOfbsGVniyORpCNrZue67xbjvRGxtNj2p9RuKX41Iq4EngDeWOy7CXgVtVuM24Hfa0ZQ+4prx1xLUinMmTYBgD095m1J7a9pxXW73mLsdEKjJJVK35jrrY65llQC1XtCY0ffsJAWByJJqkvfaiGudS2pDKpXXBe9dMdcS1I5TCk6189ZXEsqgcoV131PaHRYiCSVw/gxnYzt7GCLxbWkEqhccb1/WIjFtSSVxZTxXWzZ6ZhrSe2vesX1vtVCWhyIJKluU8Z3OSxEUilUrrjue4jMrr0+RleSymLK+DF2riWVQuWK6917ay3rXXttXUtSWUwZ38Wqp7e3OgxJOqLKFdfHT689jGDHHjvXklQWnR3B409ZXEtqf5UrrieOrS3ptG2XY/ckqSzOOn4qPb3p0BBJba9yxfWkcZ0AbN9t51qSymLejIkAPL7J7rWk9la94nps32N07VxLUlmcffxUAJav29ziSCTp8KpXXBeP0d1ucS1JpXHCzFrn2gfJSGp3lSuuJ46tDQvZ5rAQSSqNmZPG0tkRLFtt51pSe6tccT2uq4POjmD7brsfklQWEcGksZ2seXZHq0ORpMOqXHEdEUwY08mD67a0OhRJ0hAcP30CTzy1rdVhSNJhVa64Bti5p4eezFaHIUkaglNmTWbT1t309Jq/JbWvShbXLzppJs/tcK1USSqTF544A4Clq55pcSSSNLhKFtfTJ45l+brnWh2GJGkILlg4E4Clq5zUKKl9VbK43rO3lzEdlfzWJam0Tps9BYCH1tsckdS+Kllhnn7cFLbu3kuv4/YkqTTGdHYwbcIYHlzvhHRJ7auSxfW0CWPIhC0+SEaSSuWM46bwyJNbWx2GJA2qksV131MaH7L7IUmlcvpxU9ixp4ent+1udSiSNKBKFtdnzpkKwOOulypJpdK3Ysi3l61tcSSSNLBKFtenzZ4MwPK1ToqRpDK57MzZAPzwoY0tjkSSBlbJ4nri2NqwkJWb7FxLUplMGtfFyd2TuOXBDU5Kl9SWKllcQ617fdfjT7c6DElqGxHxTxGxISLu67dtZkTcHBGPFP/OKLZHRHwyIlZExLKIeMFIxfniU44F4Kb71o3UJSWpbk0rrts9Sc+fMZFtu3vsfEjSfp8HLj9o24eAWzLzVOCW4j3AK4FTi6+rgE+PUIz80SWnAPC5Hz82UpeUpLo1s3P9edo4SV940jEArN28o9mXkqRSyMz/AA6+pXcFcF3x+jrg9f22fyFrfgZMj4g5IxHnrCnjOW32ZJauepYnn9s5EpeUpLo1rbhu9yQ9d8YEAO53UqMkHc7szOwbf7EemF28ngus6nfc6mLbASLiqohYEhFLNm5s3CTE9156GgCf/Y+VDTunJDXCSI+5PqokDY1L1GcfPw2ARzf6MAJJqkdmJjCksXSZeU1mLs7Mxd3d3Q2L5VXPPw6Az/3kMWphSVJ7aNmExuEk6eJzDUnUdq4lqS5P9t1JLP7dUGxfA8zvd9y8YtuIiAh+e3Ht8p+xey2pjYx0cd02SbqzI5g/cwK3PrDhyAdLUnXdALy9eP124Jv9tr+tmJB+IbC5353JEfHR1z0PgKu/86CT0yW1jZEurtsqSZ81Zyo79vQ4IUaSgIj4EvBT4PSIWB0RVwJXAy+LiEeAy4r3ADcBK4EVwGeBPxzpeCeM7eSNi+cB8I27R6xpLkmH1cyl+No+Sf/2+bVm+beWuVaqJGXmmzNzTmaOycx5mXltZj6VmZdm5qmZeVlmPl0cm5n5rsw8OTOfn5lLWhHzn77qTAD+4tvLW3F5STpEV7NOnJlvHmTXpQMcm8C7mhXLYF562iygNtv8yosWjvTlJUlHafrEsbzwxBnc9cQzXH/3Gl5/3oBz4SVpxFT2CY0AHR3BabMns/65nWzcsqvV4UiShuF/vPk8AN73laVs27W3xdFIqrpKF9cAH3j56QB89sfONpekMjp++gTe+WsnAXDBX/7AyY2SWqryxfXLzqottX3tT3yMriSV1YdeeQYLj53Ett09/Ofr7mx1OJIqrPLFdUTw8rNm09Ob/PTRp1odjiRpGCKCm//41wD44UMb+cDX7mlxRJKqqvLFNcBHXl2bbX7VF5b4pC9JKqmuzg5+8sGLAfj6Xav5g3++q8URSaoii2vgxGMmsWj+dLbs2suH//3eVocjSRqmeTMmcudHLgPgO/et54pP3c6O3T0tjkpSlVhcF770+y8C4Mt3ruLGe9a2OBpJ0nB1TxnHvR99OQD3rHqWM//rd/nZSof9SRoZFteFiWO7+PZ7LgLg3V+6m6e2ujSfJJXVlPFjePAvLuf15x4PwJuu+Rkfv+kBh/5JajqL636ed/w0PvzKMwB40f97C3t6elsckSRpuMaP6eTv3nQe//i7LwDgM/+xkoUfvol7Vj3b4sgkjWYW1wd556+fzJlzprK3Nznrv36XrT6QQJJK7fKz53D/n7+CCxbOBOCKT93OGz/zU/73ik12siU1nMX1AL717os4bfZk9vQkZ/8/32PtsztaHZIk6ShMGtfFV9/5K1zz1hdyzKSx3PHY0/zO537O+X95Cz9+ZKMPnpHUMBbXA+jsCL7/x7/OS0/vBuBXr76Vq7/zoB0OSSq5lz/vOO76v1/Gt99zEcdOHsumrbt467V3cNKf3sRffns56zfvbHWIkkouylwwLl68OJcsWdLUa3zuxyv52LcfAKAj4DNvXbzvqY6SNFwRcVdmLm51HCNpJHL2UGQmj2zYyidufpjv3Ld+3/buKeN48/nz+d0LT2TW1PEtjFBSO6k3b1tc12H77r2884t38eNHNgEwY+IY3nXxKVx50UIiounXlzT6WFy3l+279/Jvd63mhnvWcufjz+zbftrsyZwzbzpveOE8XnjiDMZ0esNXqiqL6ya4f+1mPn7Tg/xkxaZ9297xqwu48qKFzJ85ccTikFR+Ftftq6c3+dqSVdy4bC23rzhwfezzF8zgecdP4/Kzj+NFC2faYJEqxOK6iTZt3cWH/m0ZP3hgw75tx00dz+vPm8t/Om8up86aTEeHCVfS4Cyuy2H33l4eWPcctzzwJDfcs5bHn9p+wP4LFs7kRQtn8tpFxzNn2nimjB/TokglNZvF9QjY09PL9Xev4St3rmLJE/tvI47t7ODiM7q5+PRZXHzGLGY7Zk/SQSyuy2nnnh7uX/ujukoXAAALrUlEQVQc19+9hm/fu46nt+0+YP8586Yxf8ZELjxpJi89fRbHTB7LuK5OOm24SKVncT3CenuTH6/YxNfvWs137l3H3n7LOs2eOo7TZk/hsjNn88ITZ7Dg2ElMHtfVwmgltZrF9eiwt6eX2x7ayJ2PP82KDVu57aENDPRr9ZVnH0dPb/KfzpvL+DGdnL9wpr8HpJKxuG6hzOTZ7Xv4wQNPcv3SNSxbvZktOw98GM2CYyZywjGTWHjMRM47YQYvPb2bKePH0BE4hk+qAIvr0amnN3l2+25+tvJpVj+znXvXbObhJ7ewccsuntm+54BjZ0wcQ09v8mundXPc1PHMmzGBC08+BoA5UycwbaJDTKR2YnHdRvqK7fvWbuah9Vu48Z61RARLB3kE76uefxwRwTGTxvKSU2trbS+aN80loaRRxOK6elZs2ML23T386KGNbNy6i+27e7jxnrV0dQTbdvcccvzZc6cCkAnnzp/OKbMmAzBl/Bhe/rzZ9LVhJozppMtVTKSms7gugR27e9iwZSe3r3iKTVt38dimbdyz+lkCeHTjtkOOnzi2E4COCF67aA4Q9PYmrzh7NhPH1m4vLjx2kmO8pRKwuFZ/z2zbzc8fe4pM9jViMqE3k9se2njEz7/8rNn03fQ8d/4MTu6etG/f2XOncfz0Cc0KXaoMi+uS27W3h0ee3ArAvWs2s3Jj7fXDT25l+brnANi2ay/bB+h2zJ467oD3r1t0PB39hppMGtfFpWfOOuCYsZ0dnDJrskNSpBFica167drbw44i1+/u6eXby9bRU8zrWb7uOZavrf1OyISHntwy4Dmmjt8/vntsVwevWzT3gP2Tx3XyirOPO2DbmM4OTul29Supj8V1Rdy/djObd9TG8T20fgsPP7ll32SaRzdu5d41mw84fuee3kHPNX5MB/NmHLpe95lzpnL67MkDfualp89i2oSBxwV2TxnH+DGd9XwbUuVYXKsZNm7ZxZPP7X+E+/1rN/PAuv0F931rNtcK8H6/+rfsOnBOUH/jujo4qfvA/N/T28srnncc0yeOPeT446eN51dPPnbAc43pin13WaUyqjdv+7/yknve8dP2vR4sofW3a28Pt6/YxJ6e/Zk1M7nxnnWHHJskN927nhUbtnLjIOf7m+8/fNjrnXfC9EH39fYmr3z+HCbUUYBPHNvJZWfuv+15JOPHdFrYS6qc7inj6J6y/+7l2XOnHebomoF/L8D1d6+h56AG3Obte7jj8ad5+MkVw4rvnHnTmDVl4KGLEXD67ClHjPkFJ04f9BxSO7C4rphxXZ1ccsbsQ7ZffvacAY/v7c1DkmufOx57mnWbdw64b+mqZ3jioIct9Ldxyy4eXL+Fe1ZvHvSYo3X+ghnD7pKc1D2J59fxS+lIOiL49dO6mTpId/9ouG6upEYY/PfCcQMcXVvre9feQ++Cbt6+h1sefHLApQh37OnhhqVr2duTrH12x4DnXb7uOW5e/mRdMdezjGFPb/K6RcczYWx9jZbM5HXnzmVc19Amh0bAabOnMMZJpSo4LEQts3XXXnYPkKAPtrenl+/ev37fGMMjeXrbbn740MZhjxO8Z5BVXNrN3OkTDntnoNFO6p7ckD84hmLR/MG7XGXnsBDpQJu372HNIIV3n1/88hke23TohP+Drd+8k/94uP7fA33DK4/G6bOnDOtze3t7ec05xzdk3fMXn3Isc6Y1NmdOnzjG+ViFUo65jojLgb8HOoHPZebVhzveRK1m2L57Lxu37GrIuX766FNsaNC5+rv1wQ08t/PofxnUa+UAq9eMlIl1dp2GIqj9sVDPLfM+J3dPOuT402dPYcakQ8ed1hWDxbXUVn628qlDnklRj5uXr+e5HUP/HMCmrbsOeMJzO5owppNfKdZfb6RJ47p45SB3R+o1eVwXLzn12BEr/ktXXEdEJ/Aw8DJgNXAn8ObMXD7YZ0zU0sjYvH0Pq54ZfJhPM9yz+lker6NDNRzfu/9Jduw5dKWdwRzuj62Fx07ixndfNOSu02gprofSFDFnS4fauafngKc6D9fdv3yGRzdsbUBE+/3o4Y1s2rq7oeeE2kTbBnzL+xyuCdObyW+8YB6dRQF++nFTeNP584e1NnwZJzReAKzIzJUAEfFl4Apg0OJa0siYNnEM0yaO7JCQoXSVh+ojrz5rSMdv3LKLRzYcuMTZ0lXP8qU7fsljm7bxk0c2DTo+dTQrmiKfol9TJCJuOFxTRNKBGjX5/iWndu978FyjvOPFCxt6vj49vcnKjVuPqsDe09PLN5euOewxKzdu4xe/fIbv3rceqA0bhdpd5U+95QXDv/gRtFNxPRdY1e/9auBFLYpFkvY5eAUGqK3O89uL5/ORb9zHjOo+ptqmiKQh6+wITh3mGPX+htqE2fDcTv7quw+xeMGMo7724bRTcV2XiLgKuArghBNOaHE0kqrsmMnj+Me3vrDVYbTSEZsi5mxJ7WLW1PH8f29c1PTrtNO6MWuA+f3ezyu2HSAzr8nMxZm5uLu7sbc/JEmNZc6WVDXtVFzfCZwaEQsjYizwJuCGFsckSRpcXU0RSaqStimuM3Mv8EfA94AHgK9m5v2tjUqSdBg2RSTpIG015jozbwJuanUckqQjy8y9EdHXFOkE/smmiKSqa6viWpJULjZFJOlAbTMsRJIkSSo7i2tJkiSpQSyuJUmSpAaJzAY+3H2ERcRG4IlhfPRYYFODwymTqn//4M+g6t8/tP5ncGJmVmrh5wrk7DLEWYYYwTgbqQwxQjnirCtvl7q4Hq6IWJKZi1sdR6tU/fsHfwZV//7Bn0GZlOW/VRniLEOMYJyNVIYYoTxx1sNhIZIkSVKDWFxLkiRJDVLV4vqaVgfQYlX//sGfQdW/f/BnUCZl+W9VhjjLECMYZyOVIUYoT5xHVMkx15IkSVIzVLVzLUmSJDWcxbUkSZLUIBbXkiRJUoNYXEuSJEkNYnEtSZIkNYjFtSRJktQgFtcadSJiQUTcd9C2j0bEB5pwra39rrkjIu6OiAci4o6IeEejrydJo9FBufR3mnSNd0TEPxSvPxoRayJiaUQ8EhH/HhFnNeO6qh6La6lOEdF1hEMezczzMvNM4E3A+yLi90YgNEkaLRYATSmuB/CJzDw3M08FvgLcGhHdI3RtjWIW16qciHhPRCyPiGUR8eVi26SI+Kei43x3RFxRbH9HRNwQEbcCt9R7jcxcCbwfeE9TvglJGp2uBl5SdJT/OCI6I+KvI+LOIme/EyAiXhoRP4qIb0bEyoi4OiLeUuTweyPi5KFcNDO/AnyfkSvsNYodqRMnjUYfAhZm5q6ImF5s+whwa2b+52LbHRHxg2LfC4BzMvPpIV7nF8AZjQlZkirhQ8AHMvM1ABFxFbA5M8+PiHHA7RHx/eLYRcCZwNPASuBzmXlBRLwXeDfwviFe25ythrC41miUR9i+DPiXiLgeuL7Y9nLgdf3GZY8HTihe3zyMwhoghvEZSdJ+LwfOiYg3FO+nAacCu4E7M3MdQEQ8Sq3zDHAvcPEwrmXOVkNYXGs0egqYcdC2mcBjxetXA78GvBb4SEQ8n1pS/c3MfKj/hyLiRcC2YcZxHvDAMD8rSarl5ndn5vcO2BjxUmBXv029/d73Mrz65jxgyTA+Jx3AMdcadTJzK7AuIi4BiIiZwOXATyKiA5ifmbcBH6TWBZkMfA94d0RE8ZnzjiaGiFgA/A3wP47mPJJUMVuAKf3efw/4g4gYAxARp0XEpEZfNCJ+k1qX/EuNPreqx861Rqu3AZ+KiL8t3v95Zj5aJOh/johp1Doin8zMZyPiL4C/A5YVBfhjwGuGeM2TI+JuakNKthTn/nwjvhlJqohlQE9E3AN8Hvh7aiuI/KJofmwEXt+ga/1xRPwuMAm4D7gkMzc26NyqsMgcbHiqJEmSpKFwWIgkSZLUIBbXkiRJUoNYXEuSJEkNYnEtSZIkNYjFtSRJktQgFteSJElSg1hcS5IkSQ3y/wMHf8JNgBdDhwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 864x288 with 2 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.subplot(1, 2, 1)\n",
    "usrs.plot.line(figsize=(12, 4))\n",
    "plt.xlabel(\"User ID\")\n",
    "plt.ylabel(\"times\")\n",
    "plt.title(r\"Distribution of $users$\")\n",
    "\n",
    "plt.subplot(1, 2, 2)\n",
    "items.plot.line(figsize=(12, 4))\n",
    "plt.xlabel(\"Item ID\")\n",
    "plt.ylabel(\"times\")\n",
    "plt.title(r\"Distribution of $items$\")\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由以上图，可以发现无论是用户，还是物品，都是符合长尾分布（也，[齐夫分布](https://en.wikipedia.org/wiki/Zipf%27s_law)）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def RSME(r, r_hat):\n",
    "    \"\"\" 计算均方根误差 \"\"\"\n",
    "    assert r.size == r_hat.size\n",
    "    \n",
    "    error = 0.0\n",
    "    for i, j in zip(r, r_hat):\n",
    "        error += (i - j) ** 2\n",
    "    error = math.sqrt(error) / r.size\n",
    "    \n",
    "    return error "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Simon Funk的SVD分解\n",
    "\n",
    "参考：[Simon Funk's Blog](http://sifter.org/~simon/journal/20061211.html)\n",
    "\n",
    "对用户-物品矩阵 $R$ 分解到低维空间上的两矩阵 $P$ 和 $Q$ 相乘。\n",
    "\n",
    "$$\\hat{R} = P^\\text{T}Q$$\n",
    "\n",
    "则，对于用户 $u$ 对物品 $i$ 的评分预测可表示为：\n",
    "\n",
    "$$\\hat{r}=\\sum_f p_{uf}q_{if}$$\n",
    "\n",
    "利用训练集最小化RSME来学习矩阵 $P$ 和 $Q$ ：\n",
    "\n",
    "$$\\min C(P, Q) = \\min_{p,q}\\sum_{(u,i)\\in Train}\\left( r_{ui}-\\sum_{f=1}^F p_{uf}q_{if} \\right)^2 + \\lambda\\left( \\lVert p_u \\rVert^2 + \\lVert q_i \\rVert^2\\right)$$\n",
    "\n",
    "利用随机梯度下降法（SGD）求解上述最优化问题，有\n",
    "$$\\frac{\\partial C}{\\partial p_{uf}} = -2\\left(r_{ui}-\\hat{r}_{ui}\\right)q_{if}+2\\lambda p_{uf}$$\n",
    "\n",
    "$$\\frac{\\partial C}{\\partial q_{if}} = -2\\left(r_{ui}-\\hat{r}_{ui}\\right)p_{uf}+2\\lambda q_{if}$$\n",
    "\n",
    "于是，有如下更新公式：\n",
    "$$p_{uf} =: p_{uf} + \\alpha \\left(\\left(r_{ui}-\\hat{r}_{ui}\\right)q_{if} - \\lambda p_{uf}\\right)$$\n",
    "\n",
    "$$q_{if} =: q_{if} + \\alpha\\left(\\left(r_{ui}-\\hat{r}_{ui}\\right) p_{uf} - \\lambda q_{if}\\right)$$\n",
    "\n",
    "以上算法被称之为**L**atent **F**actor **M**odel（LFM）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict(u, i, p, q):\n",
    "    \"\"\" 预测用户 u 在物品 i 上的评分 \"\"\"\n",
    "    sum = 0.0\n",
    "    for f in range(len(p[u])):\n",
    "        sum += p[u][f] * q[i][f]\n",
    "    return sum\n",
    "#     return sum(p[u][f] * q[i][f] for f in range(len(p[u])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def init_LFM(train, F):\n",
    "    \"\"\"初始化参数 p 和 q，据《推荐系统实践》：“，根据经验，随机数需要和1 / sqrt(F)成正比“ \"\"\"\n",
    "    p = dict()\n",
    "    q = dict()\n",
    "\n",
    "    for index in range(train.count()[0]):\n",
    "        u, i, rating = list(train.values[index])\n",
    "        if u not in p:\n",
    "            p[u] = [random.random() / math.sqrt(F) for f in range(F)]\n",
    "        if i not in q:\n",
    "            q[i] = [random.random() / math.sqrt(F) for f in range(F)]\n",
    "    return p, q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def learn_LFM(train, F, n, alpha=0.001, lamb=0.02):\n",
    "    \"\"\" 学习隐语义模型参数 \"\"\"\n",
    "    p, q = init_LFM(train, F)\n",
    "\n",
    "    for step in range(n):\n",
    "        for index in range(train.count()[0]):\n",
    "            u, i, rui = list(train.values[index])\n",
    "            \n",
    "            rui_hat = predict(u, i, p, q)\n",
    "            eui =  rui - rui_hat\n",
    "            for f in range(F):\n",
    "                p[u][f] += alpha * (eui * q[i][f] - lamb * p[u][f])\n",
    "                q[i][f] += alpha * (eui * p[u][f] - lamb * q[i][f])\n",
    "        # end for\n",
    "        alpha *= 0.9     # the requirement of SGD method\n",
    "    # end for\n",
    "    return p, q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "small_data = load(\"./data/small-renewed-train.dat\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "small_data = small_data.iloc[:, :3]\n",
    "\n",
    "p, q = learn_LFM(small_data, 10, 2000, 0.001, 0.02)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "small_data = small_data.iloc[:, :3]\n",
    "prediction = []\n",
    "for index in range(small_data.count()[0]):\n",
    "    u, i, rui = list(small_data.values[index])\n",
    "    rui_hat = int(round(predict(u, i, p, q)))\n",
    "    if rui_hat > 5:\n",
    "        rui_hat = 5\n",
    "    prediction.append(rui_hat)\n",
    "small_data[\"Prediction\"] = prediction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "small_data.head(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "error = RSME(small_data[\"Rating\"], small_data[\"Prediction\"])\n",
    "error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## 3.加入偏置项后的LFM\n",
    "\n",
    "此处参考「3」。\n",
    "\n",
    "预测公式：\n",
    "\n",
    "$$\\hat{r}_{ui} = \\mu + b_u + b_i + p_u^\\text{T}q_i$$\n",
    "\n",
    "其中：\n",
    "\n",
    "- $\\mu$ 是训练集中所有记录的评分的全局平均数；\n",
    "- $b_u$ 为用户偏置项；\n",
    "- $b_i$ 为物品偏置项。\n",
    "\n",
    "于是，描述为如下最优化问题：\n",
    "\n",
    "$$\\min C(P, Q) = \\min_{p,q}\\sum_{(u,i)\\in Train}\\left( r_{ui}- \\mu - b_u - b_i - \\sum_{f=1}^F p_{uf}q_{if} \\right)^2 + \\lambda_1\\left( \\lVert p_u \\rVert^2 + \\lVert q_i \\rVert^2\\right) + \\lambda_2\\left(\\lVert b_u \\rVert^2 + \\lVert b_i \\rVert^2\\right)$$\n",
    "\n",
    "此处，为了简便，取 $\\lambda_1=\\lambda_2=\\lambda$ ，同样，利用**SGD**可以得出如下偏导：\n",
    "\n",
    "$$\\frac{\\partial C}{\\partial b_u} = -2\\left(r_{ui} - \\hat{r}_{ui}\\right)+2\\lambda_2 b_u\n",
    "\\qquad\n",
    "\\frac{\\partial C}{\\partial b_i} = -2\\left(r_{ui} - \\hat{r}_{ui}\\right)+2\\lambda_2 b_i$$\n",
    "\n",
    "$$\\frac{\\partial C}{\\partial p_{uf}} = -2\\left(r_{ui}-\\hat{r}_{ui}\\right)q_{if}+2\\lambda_1 p_{uf}\n",
    "\\qquad\n",
    "\\frac{\\partial C}{\\partial q_{if}} = -2\\left(r_{ui}-\\hat{r}_{ui}\\right)p_{uf}+2\\lambda_1 q_{if}$$\n",
    "\n",
    "与更新公式:\n",
    "\n",
    "$$b_u =: b_u + \\alpha \\left(\\left(r_{ui} - \\hat{r}_{ui}\\right) - \\lambda_2 b_u\\right)\n",
    "\\qquad\n",
    "b_i =: b_i + \\alpha \\left(\\left(r_{ui} - \\hat{r}_{ui}\\right) - \\lambda_2 b_i\\right)$$\n",
    "\n",
    "$$p_{uf} =: p_{uf} + \\alpha \\left(\\left(r_{ui}-\\hat{r}_{ui}\\right)q_{if} - \\lambda_1 p_{uf}\\right)\n",
    "\\qquad\n",
    "q_{if} =: q_{if} + \\alpha\\left(\\left(r_{ui}-\\hat{r}_{ui}\\right) p_{uf} - \\lambda_1 q_{if}\\right)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "avg_rating = int(round(small_data[\"Rating\"].sum()*1.0 / small_data[\"Rating\"].count()))\n",
    "avg_rating       # mu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def learn_bias_LFM(train, F, n, alpha, lamb, mu):\n",
    "    \"\"\" 学习带有偏置量的LFM模型 \"\"\"\n",
    "    bu, bi, p, q = init_bias_LFM(train, F)\n",
    "    for step in range(n):\n",
    "        for index in range(train.count()[0]):\n",
    "            u, i, rui = list(train.values[index])\n",
    "            rui_hat = predict_bias(u, i, p, q, bu, bi, mu)\n",
    "            eui = rui - rui_hat\n",
    "            \n",
    "            # updating parameters \n",
    "            bu[u] += alpha * (eui - lamb * bu[u])\n",
    "            bi[i] += alpha * (eui - lamb * bi[i])\n",
    "            for f in range(F):\n",
    "                p[u][f] += alpha * (q[i][f] * eui - lamb * p[u][f])\n",
    "                q[i][f] += alpha * (p[u][f] * eui - lamb * q[i][f])\n",
    "        # end for\n",
    "        alpha *= 0.9\n",
    "    # end for\n",
    "    return bu, bi, p, q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def init_bias_LFM(train, F):\n",
    "    \"\"\" 初始化带偏置量的LFM模型里的偏置参数和隐变量参数 \"\"\"\n",
    "    p = dict()\n",
    "    q = dict()\n",
    "    bu = dict()\n",
    "    bi = dict()\n",
    "    \n",
    "    for index in range(train.count()[0]):\n",
    "        u, i, rui = list(train.values[index])\n",
    "        bu[u] = 0\n",
    "        bi[i] = 0\n",
    "        if u not in p:\n",
    "            p[u] = [random.random() / math.sqrt(F) for f in range(F)]\n",
    "        if i not in q:\n",
    "            q[i] = [random.random() / math.sqrt(F) for f in range(F)]\n",
    "    # end for\n",
    "    \n",
    "    return bu, bi, p, q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict_bias(u, i, p, q, bu, bi, mu):\n",
    "    \"\"\" 运用带偏置量的模型进行预测 \"\"\"\n",
    "    prediction = mu + bu[u] + bi[i]\n",
    "    for f in range(len(p[u])):\n",
    "        prediction += p[u][f] * q[i][f]\n",
    "    return prediction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "small_data = small_data.iloc[:, :3]\n",
    "\n",
    "bu, bi, p, q = learn_bias_LFM(small_data, 6, 1000, 0.001, 0.02, avg_rating)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prediction = []\n",
    "for index in range(small_data.count()[0]):\n",
    "    u, i, rui = list(small_data.values[index])\n",
    "    result = predict_bias(u, i, p, q, bu, bi, avg_rating)\n",
    "    rui_hat = int(round(result))\n",
    "    if rui_hat > 5:\n",
    "        rui_hat = 5\n",
    "    prediction.append(rui_hat)\n",
    "small_data[\"Prediction\"] = prediction\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "small_data.head(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "error = RSME(small_data[\"Rating\"], small_data[\"Prediction\"])\n",
    "error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.考虑带评论信息的LFM\n",
    "\n",
    "当考虑到评论信息时，可以认为：关于物品 $i$ 的全部评论可以刻画此物品的特征。于是，可对下式中的 $q_i$ 做替换：\n",
    "\n",
    "$$\\hat{r}_{ui} = \\mu + b_u + b_i + p_u^\\text{T}q_i$$\n",
    "\n",
    "将评论考虑在内：(此处参考论文「1」)\n",
    "\n",
    "$$\\hat{r}_{ui} = \\mu + b_u + b_i + p_u^\\text{T}\\left(\\frac{1}{\\lvert R_i\\rvert} \\sum_{w\\in R_i}q_w\\right)$$\n",
    "\n",
    "其中，$R_i$ 关于物品 $i$ 的所有评论的词集，$q_w$ 则是关于词 $w$的隐语义(latent factors)向量。另外，最优化问题变为：\n",
    "\n",
    "$$\\min_{p,q}\\sum_{(u,i)\\in Train}\\left( r_{ui}- \\mu - b_u - b_i - p_u^\\text{T}\\left(\\frac{1}{\\lvert R_i\\rvert} \\sum_{w\\in R_i}q_w\\right) \\right)^2 + \\lambda_1\\left( \\lVert p_u \\rVert^2 + \\sum_{w\\in R_i}\\lVert q_w \\rVert^2\\right) + \\lambda_2\\left(\\lVert b_u \\rVert^2 + \\lVert b_i \\rVert^2\\right)$$\n",
    "\n",
    "同样，使用SGD迭代求解上述最优化问题，有关于 $p_u$ 和 $q_w$ 的更新公式：（其他参数的更新公式同上节）\n",
    "\n",
    "\n",
    "$$p_u =: p_u + \\alpha \\cdot \\left( \\left( r_{ui} - \\hat{r}_{ui}\\right) \\cdot \\frac{1}{\\lvert R_i\\rvert}\\sum_{w\\in R_i}q_w-\\lambda_1p_u\\right)$$\n",
    "$$q_w =: q_w + \\alpha \\cdot\\left( \\left(r_{ui} - \\hat{r}_{ui}\\right)\\cdot\\frac{1}{\\lvert R_i \\rvert}\\cdot p_u-\\lambda_1 q_w\\right)$$\n",
    "\n",
    "另外，在上海交通大学的论文「2」中，采用 $\\frac{1}{Z}\\sum_{w\\in R_i}q_w$ 替换 $\\frac{1}{\\lvert R_i\\rvert} \\sum_{w\\in R_i}q_w$ 。\n",
    "\n",
    "$$\\hat{r}_{ui} = \\mu + b_u + b_i + p_u^\\text{T}\\left(\\frac{1}{Z}\\sum_{w\\in R_i}q_w\\right)$$\n",
    "\n",
    "其中论文作者的参考取值为，$q_w\\in\\mathbb{R}^{200}$, $Z = \\sqrt{\\lvert R_i\\rvert}$ 。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "line = \"\"\"Ji9PeffxjwqPLO7pEfSpKQ jQsNFOzDpxPmOurSWCg1vQ 3 328 i'm not saying pei wei is the best asian food i've ever tasted far from it it's a \n",
    "fairly large chain that puts on the appearance of something more refined it's essentially to asian food what olive garden is to italian \n",
    "food with that said i've always had pretty good experiences with pei wei the food although not spectacular is better than some of the \n",
    "overcooked chicken drowning in msg offered by some of the local chinese restaurants the portions are good sized the food is generally \n",
    "consistent and the prices are really reasonable considering this is a corporate chain in some cases cheaper than the local establishments \n",
    "or dare i say it's name panda express which is overpriced crap the time before last that i went they forgot the tomato's and the dressing\n",
    "for an asian chopped chicken salad that my wife ordered i didn't discover that the dressing was missing until i got home i immediately called \n",
    "the restaurant and was speaking to a manager within 30 seconds the manager apologized and asked me if i would like to come back to the restaurant\n",
    "or if he could have my address so he could send me a gift certificate i decided to go back to the restaurant when i got the restaurant i told the \n",
    "person at the counter my name and they already had a bag set aside for me the manager came over and explained to me there was another full salad \n",
    "in the bag and he put additional dressing for the salad we already had and additionally he gave me a coupon for free lettuce wraps which mental note \n",
    "i need to use i must say i was impressed with this manager and it was refreshing after being in situations where a manager has taken back the bag\n",
    "plate and essentially k's your food and returns it to you overall great customer service consistent food and a good option for takeout in surprise\"\"\"\n",
    "metas = line.split(\" \")\n",
    "item = metas[1]\n",
    "review_cnt = metas[3]\n",
    "review = metas[4:]\n",
    "\n",
    "print(item)\n",
    "print(review_cnt)\n",
    "print(review[:20])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_reviews(fname):\n",
    "    \"\"\" 将所有评论数据导入，为每个物品构建评论词集，不考虑词频和词序，\n",
    "    使用nltk库去除停用词和标点符号，并且对词进行词干化处理\n",
    "    @param:\n",
    "        fname:          string, 训练数据集文件名\n",
    "    @return:\n",
    "        train:          DataFrame, 训练数据集\n",
    "        reviews:        dict, 每个物品对应的评论词集\n",
    "    \"\"\"\n",
    "\n",
    "    print(\"loading training data\")\n",
    "    punctuations = {',', '.', ':', ';', '?', '(', ')', '[', ']', '!', '@', '#', '%', '$', '*'} # 自定义英文表单符号集合\n",
    "    english_stopwords = set(stopwords.words(\"english\"))\n",
    "    tokenizer = WordPunctTokenizer()\n",
    "    stemmer = PorterStemmer()      # 词干化处理\n",
    "\n",
    "    reviews = dict()\n",
    "    review_list = []\n",
    "    fuir = PREFIX + \"u-i-r.dat\"\n",
    "    if not os.path.exists(fuir):\n",
    "        save_uir = True\n",
    "        dstf = codecs.open(fuir, mode=\"a+\", encoding=\"utf-8\")\n",
    "    else:\n",
    "        save_uir = False\n",
    "\n",
    "    with codecs.open(fname, mode='r', encoding='utf-8') as f:\n",
    "        line = f.readline()\n",
    "        line_no = 0\n",
    "        while line:\n",
    "            metas = line.split(\" \")\n",
    "\n",
    "            # 将所有(usr, item, rating)条目存为单独文件，以备基础LFM使用\n",
    "            if save_uir:\n",
    "                new_line = \"\"\n",
    "                for i in metas[:3]:\n",
    "                    new_line += (i + \" \")\n",
    "                new_line = new_line.strip()\n",
    "                dstf.write(new_line + BR)\n",
    "\n",
    "            item = metas[1]    # item id\n",
    "            review_str = \"\"\n",
    "            for word in metas[4:]:\n",
    "                review_str += word + \" \"\n",
    "            wordset = {stemmer.stem(word) for word in tokenizer.tokenize(review_str)} \\\n",
    "                         - punctuations - english_stopwords\n",
    "\n",
    "            if wordset:\n",
    "                review_list.append(wordset)\n",
    "            else:\n",
    "                review_list.append(set())\n",
    "\n",
    "            if item not in reviews:\n",
    "                reviews[item] = wordset\n",
    "            else:\n",
    "                reviews[item].update(wordset)\n",
    "\n",
    "            line_no += 1\n",
    "            if line_no % 1000 == 0:\n",
    "                # print(\".\", end=\"\")\n",
    "                print(\"{} entries hanled.\".format(line_no))\n",
    "            line = f.readline()\n",
    "        # end while\n",
    "    # end with\n",
    "    if save_uir:\n",
    "        dstf.close()\n",
    "\n",
    "    train = load(fuir)\n",
    "    train[\"Review\"] = review_list\n",
    "\n",
    "    with open(PREFIX + \"train.pkl\", 'wb') as ftrain:\n",
    "        cPickle.dump(train, ftrain)\n",
    "\n",
    "    with open(PREFIX + \"review.pkl\", \"wb\") as freview:\n",
    "        cPickle.dump(reviews, freview)\n",
    "\n",
    "    return train, reviews\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fname = \"./data/small-train.dat\"\n",
    "\n",
    "reviews, review_list= load_reviews(fname)\n",
    "\n",
    "print(len(reviews))\n",
    "print(len(review_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dictionary = set()\n",
    "for review in review_list:\n",
    "    dictionary.update(review)\n",
    "    \n",
    "print(\"length of review dictionary = {}.\".format(len(dictionary)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def init_bias_LFM_with_reviews(train, dictionary, F):\n",
    "    \"\"\" 初始化 考虑评论与偏置项的LFM模型 \"\"\"\n",
    "    p = dict()\n",
    "    q = dict()\n",
    "    bu = dict()\n",
    "    bi = dict()\n",
    "    \n",
    "    for word in dictionary:\n",
    "        q[word] = [random.random() / math.sqrt(F) for f in range(F)]\n",
    "    \n",
    "    for index in range(train.count()[0]):\n",
    "        u, i = train.values[index][:2]\n",
    "        bu[u] = 0\n",
    "        bi[i] = 0\n",
    "        if u not in p:\n",
    "            p[u] = [random.random() / math.sqrt(F) for f in range(F)]\n",
    "    return p, q, bu, bi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict_bias_LFM_with_reviews(u, i, words, F, p, q, bu, bi, mu):\n",
    "    \"\"\" 考虑评论与偏置项的LFM的预测函数，其中：\n",
    "    \n",
    "    u        用户id\n",
    "    i        物品id\n",
    "    words    物品i对应的评论词集\n",
    "    F        隐向量的维度\n",
    "    p        已训练完成的用户向量字典\n",
    "    q        已训练完成的词向量字典\n",
    "    bu       已训练完成的用户偏置量\n",
    "    bi       已训练完成的物品偏置量\n",
    "    mu       全局评分平均值\n",
    "    \n",
    "    \"\"\"\n",
    "    prediction = mu + bu[u] + bi[i]\n",
    "    \n",
    "    q_total = [0] * F\n",
    "    for word in words:\n",
    "        q_total = [i + j / math.sqrt(len(words)) for i, j in zip(q_total, q[word])]\n",
    "    \n",
    "    for f in range(F)4031:\n",
    "        prediction += p[u][f] * q_total[f]\n",
    "    \n",
    "    return prediction  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def learn_bias_LFM_with_reviews(train, reviews, dictionary, F, n, alpha, lambda1, lambda2, mu):\n",
    "    \"\"\" 学习考虑评论与偏置项的LFM模型，其中：\n",
    "    \n",
    "        train                训练数据，一个条目为(usr_id, item_id, rating, review)\n",
    "        reviews              以item_id为索引的字典，存储关于当前物品的全部评论信息\n",
    "        F                    隐向量的维度\n",
    "        n                    SGD迭代次数\n",
    "        alpha                SGD参数\n",
    "        lambda1, lambda2     对于偏置项的正则化参数\n",
    "        mu                   全局评分平均值\n",
    "    \n",
    "    \"\"\"\n",
    "    p, q, bu, bi = init_bias_LFM_with_review(train, dictionary, F)\n",
    "    for iter in range(n):\n",
    "        for index in range(train.count()[0]):\n",
    "            u, i, rui, review_words = train.values[index]\n",
    "\n",
    "            rui_hat = predict_bias_LFM_with_reviews(u, i, reviews[i], F, p, q, bu, bi, mu)\n",
    "\n",
    "            eui = rui - rui_hat\n",
    "\n",
    "            # bu and bi\n",
    "            bu[u] += alpha * (eui - lambda2 * bu[u])\n",
    "            bi[i] += alpha * (eui - lambda2 * bi[i])\n",
    "\n",
    "            # updating p_u\n",
    "            q_total = [0] * F\n",
    "            Z = math.sqrt(len(review_words))\n",
    "            for word in review_words:\n",
    "                q_total = [i + j for i, j in zip(q_total, q[word])]\n",
    "            q_total = [i / Z for i in q_total]\n",
    "\n",
    "            for f in range(F):\n",
    "                p[u][f] += alpha * (q_total[f] * eui - lambda1 * p[u][f])\n",
    "            \n",
    "            # updating q_w\n",
    "            for word in review_words:\n",
    "                for f in range(F):\n",
    "                    q[word][f] += alpha * (p[u][f] * eui / Z - lambda1 * q[word][f])\n",
    "        # end for\n",
    "        alpha *= 0.9\n",
    "    # end for\n",
    "    return p, q, bu, bi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.参数设置\n",
    "根据论文「1」中参数设置，做如下参考设置\n",
    "\n",
    "隐变量维度：$$F=20$$\n",
    "\n",
    "正则化参数：$$\\lambda_1=0.8\\quad\\lambda_2=0.4$$\n",
    "\n",
    "学习率：$$\\alpha=0.008$$\n",
    "```python\n",
    "\n",
    "class LFMWithReview(object):\n",
    "    \"\"\" 将评论数据考虑在内的LFM模型 \"\"\"\n",
    "    def __init__(self, F=20, n=2000, alpha=0.008, lambda1=0.8, lambda2=0.4):\n",
    "        ……\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.python版本实验结果\n",
    "\n",
    "将以上考虑评论信息的LFM模型整理，并在完整的训练数据集上运行（代码见`LFM_with_review.py`）。有如下实验结果：\n",
    "\n",
    "### 6.0在small-train数据上的运行测试\n",
    "为测试模型的可运行性以及检测代码是否存在bug，先在小数据集（104条训练数据）上运行，结果如下：\n",
    ">loading training data<br>\n",
    "dictionary loaded / dumped.<br>\n",
    "dictionary word vectors initialized.<br>\n",
    "bias vectors and user vectors initialized.<br>\n",
    "global average rating: 3.53846<br>\n",
    "initialization time: 0.07s<br>\n",
    "iteration 0, Duration: 0.43s<br>\n",
    "iteration 1, Duration: 0.43s<br>\n",
    "iteration 2, Duration: 0.43s<br>\n",
    "iteration 3, Duration: 0.43s<br>\n",
    "……<br>\n",
    "iteration 198, Duration: 0.43s<br>\n",
    "iteration 199, Duration: 0.43s<br>\n",
    "learning total time: 88.61s<br>\n",
    "model dumped.<br>\n",
    "======learning finished.=======<br>\n",
    "model loaded.<br>\n",
    "==================================================<br>\n",
    "precision = 37/100 = 0.37\n",
    "\n",
    "其中，模型对训练数据的拟合准确率（模型预测值与真实值相同）达到37%。\n",
    "\n",
    "以下，开始在完整数据集上运行：\n",
    "\n",
    "### 6.1加载数据与初始化过程\n",
    ">加载训练数据集用时: 114.985569954s<br>\n",
    ">加载评论数据用时: 28.175755024s<br>\n",
    ">dictionary loaded / dumped.<br>\n",
    ">词集隐向量初始化用时: 5.87744188309s(about 0.0016326227453h)<br>\n",
    ">偏置量向量与用户向量初始化用时: 31873.5920711s(about 8.85377557529h)<br>\n",
    ">global average rating: 3.76204<br>\n",
    ">initialization time: 31879.55s\n",
    "\n",
    "其中，以上运行结果中，加载训练数据与加载评论数据用时为加载序列化对象用时。运行前，已将训练集的文本文件导入到DataFrame格式中，将各物品对应评论词集导入到dict格式，并存储为序列化文件，其用时大致为6小时。\n",
    "\n",
    "### 6.2 训练模型过程\n",
    ">`feng@RS-ubuntu:~/rs$ stdbuf -o0 python LFM_with_reviews.py > final.log &`<br>\n",
    ">`feng@RS-ubuntu:~/rs$ cat final.log`<br>\n",
    ">加载训练数据集用时: 116.260338068<br>\n",
    ">加载评论数据用时: 28.2748670578<br>\n",
    ">dictionary loaded / dumped.<br>\n",
    ">词集隐向量初始化用时: 5.87294006348s(about 0.00163137223985h)<br>\n",
    ">偏置量向量与用户向量初始化用时: 1.14972901344s(about 0.000319369170401h)<br>\n",
    ">global average rating: 3.76204<br>\n",
    ">initialization time: 7.09s<br>\n",
    ">iteration 0, Duration: **42027.59s**<br>\n",
    ">`feng@RS-ubuntu:~/rs$ kill 120311`\n",
    "\n",
    "其中，以上运行结果中，加载与初始化过程都是加载上一次运行时保存的序列化对象文件，故而用时较短。但当程序完成第一次迭代后，选择终止了程序的运行。因为第一次迭代用时大致为42000秒，也就是近12小时。完成一次迭代即需要12小时，模型参数中设置迭代次数为200次，则需要100天。被迫选择中止运行。\n",
    "\n",
    "CPU占用情况：（2核16内存微软Azure云平台Ubuntu虚拟机）\n",
    "![CPU占用情况](./cpu.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7.C++版本运行结果\n",
    "由于上述python语言各方法时间复杂度太高，无法在合理时间内运行出结果。故转而求助于C++语言，将只考虑偏置项而不考虑评论的LFM模型改写为C++语言运行。结果大致如下：\n",
    "\n",
    "C++语言版本见具体目录文件，此处不再列出。\n",
    "\n",
    "### 7.1参数设置为：`n = 50, alpha = 0.08, lambda = 0.8`时：\n",
    "\n",
    ">\tMSE: 1.13612\t\n",
    "Iteration 0, time cost: 100\tMSE: 1.04631\t\n",
    "Iteration 1, time cost: 100\tMSE: 1.03089\t\n",
    "Iteration 2, time cost: 98\tMSE: 1.02222\t\n",
    "Iteration 3, time cost: 98\tMSE: 1.01525\t\n",
    "Iteration 4, time cost: 98\tMSE: 1.00906\t\n",
    "Iteration 5, time cost: 98\tMSE: 1.00342<br>\n",
    "……<br>\n",
    "Iteration 44, time cost: 98\tMSE: 0.94367\t\n",
    "Iteration 45, time cost: 98\tMSE: 0.943546\t\n",
    "Iteration 46, time cost: 98\tMSE: 0.943434\t\n",
    "Iteration 47, time cost: 97\tMSE: 0.943333\t\n",
    "Iteration 48, time cost: 98\tMSE: 0.943242\t\n",
    "Iteration 49, time cost: 98\tMSE: 0.942418<br>\n",
    "Learning time cost: 4907s.\n",
    "\n",
    "迭代次数为50次，每次迭代耗时为100s左右，MSE随迭代次数逐渐下降。\n",
    "\n",
    "### 7.2参数设置为：`n = 20, alpha = 0.18, lambda = 0.8`时：\n",
    ">\tMSE: 1.17838\t\n",
    "Iteration 0, time cost: 98s,\tMSE: 1.12607\t\n",
    "Iteration 1, time cost: 97s,\tMSE: 1.1099\t\n",
    "Iteration 2, time cost: 97s,\tMSE: 1.09597\t\n",
    "Iteration 3, time cost: 96s,\tMSE: 1.08332\t\n",
    "Iteration 4, time cost: 97s,\tMSE: 1.07179\t\n",
    "……<br>\n",
    "Iteration 16, time cost: 97s,\tMSE: 0.987829\t\n",
    "Iteration 17, time cost: 97s,\tMSE: 0.983851\t\n",
    "Iteration 18, time cost: 97s,\tMSE: 0.980191\t\n",
    "Iteration 19, time cost: 96s,\tMSE: 0.945461<br>\n",
    "Learning time cost: 1940s.\n",
    "\n",
    "### 7.3参数设置为：`n = 100, alpha = 0.25, lambda = 0.08`时：\n",
    ">Iteration 0, time cost: 98s,\tMSE: 1.18943\t\n",
    "Iteration 1, time cost: 97s,\tMSE: 1.1653\t\n",
    "Iteration 2, time cost: 97s,\tMSE: 1.1449\t\n",
    "Iteration 3, time cost: 97s,\tMSE: 1.12712\t\n",
    "Iteration 4, time cost: 97s,\tMSE: 1.11139\t\n",
    "Iteration 5, time cost: 97s,\tMSE: 1.09728\t\n",
    "Iteration 6, time cost: 97s,\tMSE: 1.08452\t\n",
    "Iteration 7, time cost: 98s,\tMSE: 1.07291<br>\t\n",
    "……<br>\n",
    "Iteration 96, time cost: 97s,\tMSE: 0.942441\t\n",
    "Iteration 97, time cost: 97s,\tMSE: 0.942439\t\n",
    "Iteration 98, time cost: 98s,\tMSE: 0.942437\t\n",
    "Iteration 99, time cost: 98s,\tMSE: 0.942422<br>\n",
    "Learning time cost: 9772s.\n",
    "\n",
    "可见，MSE由1.18943下降到0.942422。\n",
    "### 7.4参数设置为：`n = 200, alpha = 0.17, lambda = 0.08`时：\n",
    ">Iteration 0, time cost: 98s,\tMSE: 1.11749\t\n",
    "Iteration 1, time cost: 99s,\tMSE: 1.10209\t\n",
    "Iteration 2, time cost: 98s,\tMSE: 1.08891\t\n",
    "Iteration 3, time cost: 97s,\tMSE: 1.07692\t\n",
    "Iteration 4, time cost: 97s,\tMSE: 1.06594\t\n",
    "Iteration 5, time cost: 97s,\tMSE: 1.05587\t\n",
    "Iteration 6, time cost: 97s,\tMSE: 1.04662<br>\n",
    "……\t<br>\n",
    "Iteration 194, time cost: 97s,\tMSE: 0.942435\t\n",
    "Iteration 195, time cost: 97s,\tMSE: 0.942435\t\n",
    "Iteration 196, time cost: 96s,\tMSE: 0.942435\t\n",
    "Iteration 197, time cost: 97s,\tMSE: 0.942435\t\n",
    "Iteration 198, time cost: 97s,\tMSE: 0.942435\t\n",
    "Iteration 199, time cost: 96s,\tMSE: 0.942433<br>\n",
    "Learning time cost: 19462s.\n",
    "而此次迭代过程中，MSE下降到0.942435左右，继续迭代则变化很小；可见在此时，迭代200已经能使算法收敛到局部最优。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 实验结论与感悟\n",
    "---\n",
    "此次实验，耗时比较长，但问题主要在于代码时间复杂度太高，运行所需时间太长。编码过程相对短暂，只需要个把小时便能完成。由于从上学期的专业课开始，已经习惯于用Python语言来解决问题，另外又由于数据挖掘与推荐系统也属于数据问题，也就不假思索的采用了Python语言。但后续运行时，才意识到程序的复杂度，耗时之巨！\n",
    "\n",
    "本次实验，也参考了许多博客，论文与教材，总体来说收获还是相当多的。也对稍微大一些的数据集的处理有了直观上的感受，觉得还是个非常耗时与消耗计算资源的过程。\n",
    "\n",
    "最后，非常抱歉又晚交作业，实在是非常羞愧。由此给张老师带来的麻烦，我诚挚的道歉，望老师海涵。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考资料\n",
    "\n",
    "- 「1」[L.Hu, A.Sun, and Y.Liu. Your neighbors affect your ratings: on geopraghical neighborhood influence to rating prediction.](https://dl.acm.org/citation.cfm?id=2609593)\n",
    "\n",
    "- 「2」[K.Chen, T.Chen, G.Zheng, O.Jin, E.Yao, and Y.Yu. Collaborative personalized tweet recommendation.](https://dl.acm.org/citation.cfm?id=2348372)\n",
    "\n",
    "- 「3」项亮《推荐系统实践》\n",
    "\n",
    "- 「4」[Simon Funk's Blog](http://sifter.org/~simon/journal/20061211.html)\n"
   ]
  }
 ],
 "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}