ch03/3-recsys-evaluation-indices.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# 推荐系统评测指标\n",
    "本节将介绍各种推荐系统的评测指标，可用于评价推荐系统各方面的性能。有些指标可以定量计算，有些只能定性描述，有的可通过离线实验计算，有的需通过用户调查获得，还有的只能在线评测。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org79bb7cc\"></a>\n",
    "## 用户满意度\n",
    "\n",
    "用户满意度是评测推荐系统的最重要指标，只能通过用户调查或在线实验获得。\n",
    "\n",
    "用户调查获得用户满意度主要是通过调查问卷的形式。\n",
    "\n",
    "例如如下的调查问题：\n",
    "\n",
    "下面哪句话最能描述你看到推荐结果后的感受？\n",
    "\n",
    "-   推荐的物品都是我非常想看的。\n",
    "-   推荐的物品很多我都看过了，确实是符合我兴趣的不错物品。\n",
    "-   推荐的物品和我的兴趣是相关的，但我并不喜欢。\n",
    "-   不知道为什么会推荐这些物品，它们和我的兴趣丝毫没有关系。\n",
    "\n",
    "在设计问卷时需要考虑用户各方面的感受，如此用户才能针对问题给出自己准确的回答。\n",
    "\n",
    "在在线系统中，用户满意度主要通过一些对用户行为的统计得到。\n",
    "\n",
    "有些网站会通过设计一些用户反馈界面收集用户满意度。\n",
    "\n",
    "更一般的情况，可以用点击率、用户停留时间和转化率等指标度量用户的满意度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org8caac35\"></a>\n",
    "## 预测准确度\n",
    "\n",
    "度量一个推荐系统或者推荐算法预测用户行为的能力。\n",
    "\n",
    "**最重要的推荐系统离线评测指标，该指标可通过离线实验计算。**\n",
    "\n",
    "计算该指标时需要有一个离线的数据集，该数据集包含用户的历史行为记录。将该数据集分成训练集和测试集。通过在训练集上建立用户的行为和兴趣模型预测用户在测试集上的行为，并计算预测行为和测试集上实际行为的重合度作为预测准确度。\n",
    "\n",
    "预测准确度指标：\n",
    "\n",
    "-   评分预测（预测用户对物品评分的行为）\n",
    "\n",
    "    评分预测的预测准确度一般通过 **均方根误差（root-mean-square error，RMSE）** 和 **平均绝对误差（mean absolute error，MAE）** 计算。\n",
    "\n",
    "    对于测试集中的一个用户 $u$ 和 物品 $i$ ，令 $r_{ui}$ 是用户 $u$ 对物品 $i$ 的实际评分，而 $\\hat{r}_{ui}$ 是推荐算法给出的预测评分，则有：\n",
    "\n",
    "    \\begin{equation}\n",
    "    RMSE = \\sqrt{\\frac{\\sum_{u,i \\in T}(r_{ui} - \\hat{r}_{ui})^2}{|T|}} \\nonumber\n",
    "    \\end{equation}\n",
    "\n",
    "    MAE采用绝对值计算预测误差，其定义为：\n",
    "\n",
    "    \\begin{equation}\n",
    "    MAE = \\frac{\\sum_{u,i \\in T}|r_{ui} - \\hat{r}_{ui}|}{|T|} \\nonumber\n",
    "    \\end{equation}\n",
    "\n",
    "    Netflix认为RMSE加大了对预测不准的用户物品评分的惩罚（平方项的惩罚），因而对系统的评测更加苛刻。研究表明，如果评分系统是基于整数建立的（即用户给的评分都是整数），那么对预测结果取整会降低MAE的误差<sup><a id=\"fnr.1\" class=\"footref\" href=\"#fn.1\">1</a></sup>。\n",
    "    \n",
    "    ```python\n",
    "    import math\n",
    "\n",
    "    def RMSE(records):\n",
    "        \"\"\"均方根误差\n",
    "\n",
    "        Args:\n",
    "        - records:存放用户评分数据，records[i] = [u, i, rui, pui]\n",
    "        \"\"\"\n",
    "        return math.sqrt(sum([(rui - pui) ** 2 for u, i, rui, pui in records]) / float(len(records)))\n",
    "\n",
    "    def MAE(records):\n",
    "        \"\"\"平均绝对误差\n",
    "\n",
    "        Args:\n",
    "        - records:存放用户评分数据，records[i] = [u, i, rui, pui]\n",
    "        \"\"\"\n",
    "        return sum([abs(rui - pui) for u, i, rui, pui in records]) / float(len(records))\n",
    "    ```\n",
    "\n",
    "-   TopN推荐\n",
    "\n",
    "    网站提供推荐服务时，一般是给用户一个个性化的推荐列表，这种推荐叫做 **TopN推荐** 。\n",
    "\n",
    "    TopN推荐的预测准确率一般通过准确率（precision）和召回率（recall）度量。\n",
    "\n",
    "    -   召回率\n",
    "\n",
    "        令 $R(u)$ 是根据用户在训练集上的行为给用户作出的推荐列表，而 $T(u)$ 是用户在测试集上的行为列表。那么，推荐结果的召回率定义为：\n",
    "\n",
    "        \\begin{equation}\n",
    "        Recall=\\frac{\\sum_{u\\in U}|R(u) \\cap T(u)|}{\\sum_{u\\in U}|T(u)|}  \\nonumber\n",
    "        \\end{equation}\n",
    "\n",
    "    -   准确率\n",
    "\n",
    "        \\begin{equation}\n",
    "        Precision=\\frac{\\sum_{u\\in U}|R(u) \\cap T(u)|}{\\sum_{u\\in U}|R(u)|}  \\nonumber\n",
    "        \\end{equation}\n",
    "\n",
    "    下面的代码同时计算一个推荐算法的准确率和召回率：\n",
    "\n",
    "    ```python    \n",
    "    def precision_recall(test, N, Recommend=None):\n",
    "       \"\"\"准确率、召回率\n",
    "\n",
    "        Args:\n",
    "        - test: 测试集\n",
    "        - N: 推荐物品个数\n",
    "        - Recommend: 推荐模型算法\n",
    "\n",
    "        :return: 准确率和召回率\n",
    "        \"\"\"\n",
    "        hit = 0\n",
    "        n_recall = 0\n",
    "        n_precision = 0\n",
    "        for user, items in test.items():\n",
    "            rank = Recommend(user, N)\n",
    "            hit += len(rank & items)\n",
    "            n_recall += len(items)\n",
    "            n_precision += N\n",
    "        return hit / (1.0 * n_recall), hit / (1.0 * n_precision)    \n",
    "    ```\n",
    "\n",
    "有时，为了全面评测TopN推荐的准确率和召回率，一般会选取不同的推荐列表长度N，计算出一组准确率/召回率，然后画出准确率/召回率曲线（precision/recall curve）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org0c8909c\"></a>\n",
    "## 覆盖率\n",
    "\n",
    "覆盖率（coverage）描述一个推荐系统对物品长尾的发掘能力。\n",
    "\n",
    "覆盖率有不同的定义方法，最简单的定义为 **推荐系统能够推荐出来的物品占总物品集合的比例。**\n",
    "\n",
    "系统用户集合为 $U$ ，推荐系统给每个用户推荐一个长度为 $N$ 的物品列表 $R(u)$ ，则覆盖率为：\n",
    "\n",
    "\\begin{equation}\n",
    "Coverage=\\frac{U_{u\\in U}R(u)}{|I|}   \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "覆盖率是一个内容提供商会关心的指标。\n",
    "\n",
    "覆盖率为100%的推荐系统可以将每个物品都推荐给至少一个用户。\n",
    "\n",
    "**一个好的推荐系统不仅需要有比较高的用户满意度，也要有较高的覆盖率。**\n",
    "\n",
    "**为了更细致地描述推荐系统发掘长尾的能力，需要统计推荐列表中不同物品出现次数的分布。** 如果所有的物品都出现在推荐列表中，且出现的次数差不多，那么推荐系统发掘长尾的能力就很好。因此，可以通过研究物品在推荐列表中出现次数的分布描述推荐系统挖掘长尾的能力。\n",
    "\n",
    "如果这个分布比较平，那么说明推荐系统的覆盖率较高，而如果这个分布较陡峭，说明推荐系统的覆盖率较低。\n",
    "\n",
    "在信息论和经济学中有两个著名的指标可以用来定义覆盖率。第一个是信息熵：\n",
    "\n",
    "\\begin{equation}\n",
    "H=-\\underset{i=1}{\\overset{n}{\\sum}} p(i) \\log p(i)  \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "$p(i)$ 是物品 $i$ 的流行度除以所有物品流行度之和。\n",
    "\n",
    "第二个指标是基尼系数（Gini Index）<sup><a id=\"fnr.2\" class=\"footref\" href=\"#fn.2\">2</a></sup>：\n",
    "\n",
    "\\begin{equation}\n",
    "G=\\frac{1}{n-1}\\underset{j=1}{\\overset{n}{\\sum}}(2j-n-1)p(i_{j})   \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "这里，$i_{j}$ 是按照物品流行度 $p$ 从小到大排序的物品列表中第 $j$ 个物品。\n",
    "\n",
    "下面的代码可用来计算给定物品流行度分布后的基尼系数：\n",
    "\n",
    "```python\n",
    "def gini_index(p):\n",
    "    \"\"\"基尼系数\n",
    "\n",
    "    Args:\n",
    "    - p: the dict of item popularity\n",
    "\n",
    "    :return: gini index\n",
    "    \"\"\"\n",
    "    j = 1\n",
    "    n = len(p)\n",
    "    G = 0\n",
    "    for item, weight in sorted(p.items(), key=lambda q: q[1]):\n",
    "        G += (2 * j - n - 1) * weight\n",
    "        j += 1\n",
    "    return G / float(n - 1)\n",
    "```\n",
    "\n",
    "评测推荐算法具有马太效应：\n",
    "\n",
    "评测推荐系统是否具有马太效应的简单办法就是使用基尼系数。如果 $G1$ 是从初始用户行为中计算出的物品流行度的基尼系数， $G2$ 是从推荐列表中计算出的物品流行度的基尼系数，那么如果 $G2 > G1$ ，就说明推荐算法具有马太效应。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org1032765\"></a>\n",
    "## 多样性\n",
    "\n",
    "多样性描述推荐列表中物品两两之间的不相似性。多样性和相似性是对应的。\n",
    "\n",
    "假设 $s(i,j)\\in [0,1]$ 定义了物品 $i$ 和 $j$ 之间的相似度，那么用户 $u$ 的推荐列表 $R(u)$ 的多样性定义如下：\n",
    "\n",
    "\\begin{equation}\n",
    "Diversity(R(u))=1-\\frac{\\sum_{i,j\\in R(u),i\\ne j}s(i,j)}{\\frac{1}{2}|R(u)|(|R(u)|-1)}   \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "推荐系统的整体多样性可以定义为所有用户推荐列表多样性的平均值：\n",
    "\n",
    "\\begin{equation}\n",
    "Diversity=\\frac{1}{|U|}\\underset{u\\in U}{\\sum}Diversity(R(u))   \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "**不同的物品相似度度量函数 $s(i,j)$ 可以定义不同的多样性。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org79c3558\"></a>\n",
    "## 新颖性\n",
    "\n",
    "给用户推荐那些他们以前没有听说过的物品。\n",
    "\n",
    "在一个网站中实现新颖性的最简单办法是吧那些用户之前在网站中对其有过行为的物品从推荐列表中过滤掉。\n",
    "\n",
    "评测新颖度的最简单办法是利用推荐结果的平均流行度，因为越不热门的物品越可能让用户觉得新颖。如果推荐结果中物品的平均热门程度较低，那么推荐结果就可能有比较高的新颖性。\n",
    "\n",
    "不同用户不知道的东西是不同的，要准确地统计新颖性需要做用户调查。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org82a5dc3\"></a>\n",
    "## 惊喜度（serendipity）\n",
    "\n",
    "惊喜度与新颖性有什么区别？\n",
    "\n",
    "如果推荐结果和用户的历史兴趣不相似，但却让用户觉得满意，那么就可以说推荐结果的惊喜度很高，而推荐的新颖性仅取决于用户是否听说过这个推荐结果。\n",
    "\n",
    "提高推荐惊喜度需要提高推荐结果的用户满意度，同时降低推荐结果和用户历史兴趣的相似度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org1bf5fe6\"></a>\n",
    "## 信任度\n",
    "\n",
    "如果用户信任推荐系统，那么就会增加用户和推荐系统的交互。\n",
    "\n",
    "度量推荐系统的信任度只能通过问卷调查的方式，询问用户是否信任推荐系统的推荐结果。\n",
    "\n",
    "两种方法：\n",
    "\n",
    "1.  增加推荐系统的透明度（transparency），主要办法是提供推荐解释。\n",
    "2.  考虑用户社交网络信息，利用用户好久信息给其做推荐，并用好友进行推荐解释。\n",
    "\n",
    "此问题的研究主要集中在评论网站Epinion的推荐系统上。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"orgf6926d5\"></a>\n",
    "## 实时性\n",
    "\n",
    "包括两个方面：\n",
    "\n",
    "1.  推荐系统需要实时地更新推荐列表来满足用户新的行为变化\n",
    "\n",
    "    与用户行为相应的实时性，可通过推荐列表的变化速率来评测。如果推荐列表在用户有行为后变化不大，或者没有变化，说明推荐系统的实时性不高。\n",
    "\n",
    "2.  能够将新加入系统的物品推荐给用户\n",
    "\n",
    "    主要考验推荐系统处理物品冷启动的能力。\n",
    "\n",
    "    对于新物品推荐能力，可利用用户推荐列表中有多大比例的物品是当天新加的来评测。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org54932e2\"></a>\n",
    "## 健壮性\n",
    "\n",
    "健壮性衡量了一个推荐系统抗击作弊的能力。\n",
    "\n",
    "作弊方法：\n",
    "\n",
    "-   行为注入攻击（profile injection attack）\n",
    "-   针对评分系统的攻击\n",
    "\n",
    "**利用模拟攻击的方法来评测推荐算法的健壮性。**\n",
    "\n",
    "提高系统的健壮性，可以选择健壮性高的算法，还有以下方法：\n",
    "\n",
    "-   设计推荐系统时尽量使用代价比较高的用户行为\n",
    "-   在使用数据前，进行攻击检测，从而对数据进行清理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org8da779b\"></a>\n",
    "## 商业目标\n",
    "\n",
    "最本质的商业目标就是平均一个用户给公司带来的盈利。\n",
    "\n",
    "不同的网站具有不同的商业目标。\n",
    "\n",
    "设计推荐系统时需要考虑最终的商业目标，除了满足用户发现内容的需求，也要利用推荐系统加快实现商业上的指标。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"orgbe5f455\"></a>\n",
    "## 总结\n",
    "\n",
    "|            | 离线实验 | 问卷调查 | 在线实验 |\n",
    "|------------|----------|----------|----------|\n",
    "| 用户满意度 | ×        | √        | ○        |\n",
    "| 预测准确度 | √        | √        | ×        |\n",
    "| 覆盖率     | √        | √        | √        |\n",
    "| 多样性     | ○        | √        | ○        |\n",
    "| 新颖性     | ○        | √        | ○        |\n",
    "| 惊喜度     | ×        | √        | ×        |\n",
    "\n",
    "对于可以离线优化的指标，应该在给定覆盖率、多样性、新颖性等限制条件下，尽量优化预测准确度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org2d95de8\"></a>\n",
    "\n",
    "## 评测维度\n",
    "\n",
    "增加评测维度的目的是知道一个算法在什么情况下性能最好，可以为融合不同推荐算法取得最好的整体性能带来参考。\n",
    "\n",
    "一般来说，评测维度分为如下3种：\n",
    "\n",
    "-   **用户维度:** 主要包括用户的人口统计学信息、活跃度以及是不是新用户等。\n",
    "-   **物品维度:** 包括物品的属性信息、流行度、平均分以及是不是新加入的物品等。\n",
    "-   **时间维度:** 包括季节，是工作日还是周末，是白天还是晚上等。\n",
    "\n",
    "如果能够在推荐系统评测报告中包含不同维度下的系统评测指标，就能帮助全面地了解推荐系统性能，找到一个看上去比较弱的算法的优势，发现一个看上去比较强的算法的缺点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "## 脚注\n",
    "\n",
    "<sup><a id=\"fn.1\" class=\"footnum\" href=\"#fnr.1\">1</a></sup> Gábor Takács、István Pilászy和Bottyán Németb的论文“Major components of the gravity recommendation system”。\n",
    "\n",
    "<sup><a id=\"fn.2\" class=\"footnum\" href=\"#fnr.2\">2</a></sup> 参见Guy Shani和 Asela Gunawardana的“Evaluating Recommendation Systems”。"
   ]
  }
 ],
 "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.6.4"
  },
  "name": "3-recsys-evaluation-indices.ipynb",
  "toc": {
   "colors": {
    "hover_highlight": "#ddd",
    "running_highlight": "#FF0000",
    "selected_highlight": "#ccc"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "272px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": false,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}