推荐系统算法

Netflix 在网上举办了一个挑战赛，奖励100万美元向全世界选手提出一套电影的推荐系统，RMSE比当前系统小10%的最优秀的那支队伍将获得该奖项。

但是如何评价一个更好的推荐系统？What do we mean by better?

在Netflix Prize, 对系统的性能评价使用了用户对电影的实际评分与推荐系统对每部电影预测评分之间的RMSE。如果说我们希望向人们展示他们可能对某部电影会有多喜欢，那RMSE越小自然越好。然而，这很可能不是我们想要的。用户实际关注的很可能是他们最喜欢的top-K部电影，至于他们不喜欢的电影，误差大一些无所谓。

chen_1st在他的博客中举了个例子，假定训练集中某用户有10个评分为5的商品，1000个评分为1的商品。在以RSME为优化目标时，这1010个商品是同等重要的，因此，算法会花费更大的精力去保证评分为1的商品的预测值尽量准确，相比之下，评分为5的商品被忽视了。而对于Top-K推荐来说，算法实际上应该尽量保证评分为5的商品的预测的准确性，评分为1的商品的预测结果是无关紧要的。

用RMSE做目标，预测的是用户对每个商品感兴趣的程度，而以Recall或者Precision为目标，预测的是用户最感兴趣的商品有哪些，这是两个完全不同的目标，为优化RMSE而设计的算法不见得适用于top-n推荐。在CofiRank等文献中，也有相关讨论。

相似地，在Web检索中，用户期望相关结果尽可能排在前面，因而往往以precision作为评价指标。而在专利检索中，用户期望尽可能多地返回相关结果，因而recall更合适的评价指标。搜索引擎不关心所有的文本估计的误差是否都很小，它只关心Top-K条结果是否十分准确。

在论文《The Relationship Between Precision-Recall and ROC Curves》中，作者把chen_1st例子中的数据集叫做highly-skewed dataset。作者在文中表明，对于二分类问题，ROC曲线可以比accuracy更好地评价算法的效果，然而在highly-skewed dataset上，ROC曲线会得到overly optimistic performance。而此时Precision-Recall曲线则能更好地反映这种数据集下的算法性能。

Reference

1.http://cacm.acm.org/blogs/blog-cacm/22925-what-is-a-good-recommendation-algorithm/fulltext

2.http://hi.baidu.com/chen_1st/item/741319e9a83c61a52f140b9e

3.The Relationship Between Precision-Recall and ROC Curves

------------------------------

jiang1st2010

原文地址：http://www.cnblogs.com/jiang1st2010/archive/2013/05/20/perfomance_evaluation_of_recsys.html

原csdn地址：http://blog.csdn.net/jiang1st2010

在CIO委员会提出了FEAF与联邦企业架构实施指南后，美国白宫的管理与预算办公室（OMB）接下了管理和协调联邦企业架构建设的责任，并于2002年成立了专门从事联邦企业架构开发的企业架构项目管理办公室（FEA-PMO）。与FEAF不一样，FEA（Federal Enterprise Architecture，即联邦企业架构）并不是一种理论化的企业架构开发方法论，而是联邦政府所要建立的企业架构本身，以及在联邦企业架构的建设过程中所需要的各种管理和规划工具。FEA用于指导联邦政府改善其对信息技术的投资，并着眼于在全联邦政府范围内共享可重用的信息技术资源。OMB的《Enterprise Architecture Assessment Framework v3.0》将FEA所涵盖的内容分为如下三个部分：

FEA参考模型
联邦过渡框架（FTF，The Federal Transition Framework）
企业架构评估框架（OMB EA Assessment Framework）

在这三个部分中，FEA参考模型充是整个企业架构的核心内容。通过从五个层面定义参考模型（性能模型、业务模型、服务组件模型、技术模型和数据模型），FEA为各个机构提供了一套公共的企业架构描述方法，从而使得采用不同企业架构框架的机构可以使用相同的语言进行交流。

由于FEA的重点之一就是帮助机构发现联邦政府各机构中可被重用的信息技术资源（数据、应用或业务流程等），因而需要一个可以通观全局的机构来为其他各个机构定期发布能够进行跨部门使用的各种信息技术资源。这个部门就是OMB，而这些被定期发布的能够进行跨部门使用的信息就是联邦过渡框架（TFT）所定义的内容了。同时，为了使这些共享的信息能够被很好地集成到各个机构之中，TFT中的各项内容也采用五层参考模型的方式进行描述。

为了评估和检验各个机构的企业架构建设情况，OMB提出了企业架构评估框架（EAAF）。在此框架中，OMB从企业架构的完成度、使用情况和结果影响这三个角度出发，分别制定了一系列评估标准来衡量各机构对于联邦企业架构项目的执行情况，并且此框架还指明了这一评估过程的具体执行方式。

FEA参考模型

FEA包含了一系列便于在联邦各机构中进行跨部门分析的参考模型，同时这些参考模型还有助于在整个联邦政府范围内或在某个部门之中寻找重复的投资、识别差距和合作机会。这些参考模型形成了一套框架，借此各部门可以用一种通用且统一的方式对联邦企业架构的重要组成元素进行描述，从而实现在全联邦政府范围内改善针对信息技术资源的管理和利用。按照关注点的不同，FEA的参考模型序列包含如下五种参考模型：

性能参考模型（PRM，Performance Reference Model）
业务参考模型（BRM，Business Reference Model）
服务组件参考模型（SRM/CRM，Service Component Reference Model）
技术参考模型（TRM，Technical Reference Model）
数据参考模型（DRM，Data Reference Model）

FEA五层参考模型

性能参考模型PRM

作为处在所有参考模型最上面的参考模型，性能参考模型从战略的角度对各个机构的业务进行了分类和描述，在这里称为业务视线（line of sight）。每条业务视线描述了各个机构相关任务的输入、输出以及其对外所产生结果之间的因果关系。这里所说的“输入”指的是执行业务所必需的各种先决条件，例如技术等方面内容；“输出”指的是各个机构在日常活动和流程中所产生出的各种直接结果； “结果”指的是各机构日常活动和流程对外所提供的服务以及所产生的影响。简单来说，这些视线描述了这样一个过程：各个机构采用某些输入，在某些业务流程和日常活动的支持下对外界提供服务，并通过这些服务对外界环境发生影响。

PRM框架示意图

除了对这些视线的定义，性能参考模型在这些视线的基础之上针对“输入”、“输出”和“结果”这三个方面分别提出了一系列性能衡量指标。通过使用性能参考模型各个机构可以在战略层面以业务线的方式裁剪和描述其任务目标，并且该参考模型还对业务线中各个组成部分如何进行性能评估提出了可供借鉴的参考指标及其定义，而针对这些种类繁多的性能指标，PRM采用了如下的层次结构对他们进行分类归纳：

PRM内容组织结构

测量域（Measurement Area）：是PRM框架针对各测量指标在最高层次进行组织的概念，与在机构和方案层面制定的性能目标直接相关。PRM中包含如下六种测量域：

任务与业务结果（Mission and Business Results）
客户结果（Custom Results）
流程与活动（Processes and Activities）
人力资本（Human Capital）
技术（Technology）
其他固定资产（Other Fixed Assets）

测量分类（Measurement Category）：在每个测量域中根据不同的属性而归纳出的不同组合。例如，在任务与业务结果（Mission and Business Results）测量域中就包含了市民服务（Services for Citizens）、服务交付支持（Support Delivery of Services）和政府资源管理（Management of Government Resources）这三个测量分类。
测量分组（Measurement Grouping）：在测量分类中根据测量指标的类型而进行的进一步分组。
测量指标（Measurement Indicator）：具体的测量标准，例如用户满意度百分比等。

业务参考模型BRM

业务参考模型为联邦政府的各条业务线（LOB，Line-of-Business）提供了一个功能性的视图，它既包括了各机构的内部运营行为，也包括了其对公民提供的各种服务。需要注意的是，业务参考模型中关于机构业务的定义独立于具体的机构，它采用一种通用的方式对各机构的业务进行描述，而不是为每个机构量身定制一套业务模型。业务参考模型采用如下的层次化组织方式对联邦政府的业务功能进行了归纳：

BRM内容组织结构

在业务参考模型中定义了如下四种业务领域：

市民服务（Services for Citizens）业务领域：此服务是政府的最终目标，是其对外部公民所能提供的各种服务。
交付模式（Mode of Delivery）业务领域：包含了政府为了达成目标所采用的机制。
服务交付支持（Support Delivery of Services）业务领域：包含了用于支持政府运行的各种关键政策和计划与管理基础。
政府资源管理（Management of Government Resources）业务领域：包含为了支持联邦政府的有效率运行而针对所有领域资源的管理功能。

业务参考模型采用上面的划分方式将联邦政府的各项业务和功能进行了归纳，从而形成了如下图所示的业务参考模型：

BRM内容示意

如上图所示，业务参考模型从四个业务领域对联邦政府的各条业务线进行了归类。其中需要注意的是，市民服务（Services for Citizens）、服务交付支持（Support Delivery of Services）和政府资源管理（Management of Government Resources）这三个业务领域在前面的性能参考模型中已经出现过，但是在性能参考模型中这三个同名测量分类中的内容表示的是联邦政府对这三个方面所定义的各项性能评估指标，而在业务参考模型中这三个业务领域被用来对联邦政府为了实现政府目标而采用的业务行为进行描述，即性能参考模型定纲领和指标，而业务参考模型定内容。此外，服务交付支持（Support Delivery of Services）业务领域中定义了各种用于支援政府运行的支持性功能，而针对这些功能性能衡量指标就要参照性能参考模型中流程与活动（Processes and Activities）测量域的内容了。