上下文感知的文档推荐

--一种基于序列访问数据的方法

陈弢

上世纪九十年代以来，随着信息技术尤其是互联网的发展，使得人们迅速改变了信息匮乏的状态，转而引发的是“信息过载”的问题。为了帮助人们从浩瀚文海中获得最相关的文档，最常用的方法是根据用户的搜索词对文档进行排序，这就是人们常用的搜索引擎。然而，这种对文档推荐的方式一般只考虑用户输入的搜索词，而忽略了背景，目的，用户所在的时间、空间等上下文的信息。在特定场合，这样的方法不能有效的定位关键信息，从而无法提供个性化的服务。在本文，我们就介绍一种基于序列访问数据的上下文感知的文档推荐。

《Context-AwareDocument Recommendation by Mining Sequential Access Data》是EMC中国研究院跟EMC负责企业内容管理平台(Enterprise Content ManagementPlatform)的产品部门一起合作研究的课题。双方通过长时间的深入交流，明确了产品部门的实际需求，确立了2到3个关于推荐的具体项目。对不同项目，我们有不同的侧重点。通过成功的“产”与“研”之间的合作，有的成果直接进入了Documentum|Centerstage平台原型，有的成果转化成了论文、专利。本文要重点介绍的就是其中关于上下文感知的文档推荐的项目的研究成果，发表在今年的KDD 2012Workshop on Context Discovery and Data Mining。论文链接在这儿（Link）。在KDD上介绍这项工作的时候，Canon Research和Nokia Research的很多研究员表示了很大的兴趣，于是笔者（@数据学习-陈弢）萌发了在此介绍这个工作的念头。

1. 问题提出

EMC Documentum|Centerstage是一个企业级的项目协作和内容管理平台。大家可以把它理解成为Web2.0的企业化。参与者按照空间、项目给予相应权限，可以对于参与的项目贡献文档，评论。其他属于此空间或者项目的用户将会被通知相应变动。用户每天都会贡献一个或者多个文档，也会在项目进行中去访问一些文档。

Figure 1企业内容管理平台Documentum|Centerstage

图1形象的解释了在这个平台上，文档是核心资源。用户的行为可以描述成对于文档的按序列的访问。在某个内部的小型部署上，统计到有2000多用户，多达近10万的文档。本文要探讨的问题就是如何在这样的生产环境中有效地向用户推荐所需文档。

2. 现有解决方案和问题

推荐方法可以基于不同的信息，比如协同过滤中就有item-based 和user-based的不同类别。我们将现有的文档推荐方法分为以下几种，对每种方法大致介绍其原理以及在我们的应用场景中所面对的挑战。

1. Document Content based Approach：此方法类似于互联网上的关键词搜索：用户提交查询词，基于文档的内容和查询词的相似度计算，返回最相关的文档。这种方法的适用前提是用户清楚地知道自己所需要的文档大概内容，以及能够将自己的目标准确的用查询词表示。这儿的挑战主要是内容表示难度。一方面，用户经常很难准确表述在某一项目的某一阶段自己所需要的文档的关键词；其二，我们的文档以各种不同形式存在，比如ppt，pdf，word等等，如何将其内容同意表示成某一固定形式的向量需要深入研究。

2. User Profile based Approach：这种方法基于用户信息，比如记录到某用户正在参与项目A，那么在系统会更可能推荐与项目A有关的文档给此用户。单纯应用此方法的缺陷在于在项目协作平台上，用户的profile会经常改变，一个参与项目A的用户可能在一个礼拜后加入了项目B。如何将这种信息快速的传达到系统并在推荐时考虑最新信息是一个挑战。

3. User Feedback based Approach: 在协同过滤一类的推荐算法里，基于的是每一个用户对于每一个item，即文档的反馈（比如三星的5星的）。在这样的矩阵上可以用一些矩阵分解（Matrixfactorization）的方法计算出某一个用户对某些文档的中意程度。在项目协作场景中应用这种方法的挑战在于用户的反馈信息可能对文档推荐任务的信息量太低，甚至无关。比如UserA是一个数据分析爱好者，他很喜欢一个叫做DecisionTree.doc的文档，但是在项目协作中他有可能正在参与一个网络虚拟化的项目，那么推荐DecisionTree.doc无疑是一种干扰推荐。

综上，现有的方法主要基于文档或者用户的信息，并没有考虑到项目协作平台这个特殊的场景。在下面我们介绍如何考虑用户的上下文，并以此作为推荐依赖的主要信息，达到合理、准确的推荐。

3. 基本想法和问题形式化

我们的解决方案基于这样一个基本的想法：一个用户正在工作所处的上下文可以从他最近的活动序列中推理得到；考虑这种活动的上下文可以帮助精确的推荐。上图的例子很好的说明了这个想法。某人A首先阅读了一片介绍Naïve Bayes的文档，接着打开了Decisiontree的文档，之后又访问了SVM的介绍。从这种活动序列中我们可以推测A正在参与或者关注数据分析的某项目，更具体的，这个项目更可能是关于某个分类（classification）任务（因为NB，DT，SVM都是分类的模型和算法）。那么可能的前三位推荐文档就应该是1. 随机森林（Random Forest），2. Data Mining Introduction，和3. Kmeans。其中概率最高的Random Forest（0.3）是一种高级的分类模型，而概率稍低的Kmean（0.25）是一种聚类模型。

这样的，我们可以把问题形式化成为如下的一个基于访问序列的文档推荐问题。

对严格数学定义和描述不感冒的读者可以认为我们的问题就是已经收集了用户历史的访问序列数据，然后在一个新的序列里，如何推荐下一个出现的文档。

4. 技术细节

本节，我们介绍如何利用数据分析的方法解决上面定义的基于序列的推荐问题。首先我们介绍所应用的模型，其次，我们简述大概的架构，最后是介绍如何处理由于数据稀疏所带来的问题。

我们参考了语言模型LanguageModels里面的一些模型。其中最基本的是N-Gram模型。一个N-Gram模型必须满足N-1 Markov Property，即

也就是说下一个出现的文档只跟之前的N-1个文档组成的序列有关。这样的假设大大的缩小了模型的定义空间，使得我们可以用简单的最大似然估计（MLE）来估计模型的参数，从而实现文档的推荐。由于N-Gram假设有一个固定的、全局的N，在任何情况下下一个文档的推荐都只依赖于前N-1个文档，这会带来一些模型灵活性的问题。举例说明这个假设的不合理性：在I am这个词序列中，am一般只依赖于前一个词（如果是he，she，或者其他词，后面不可能是am）；而比如open source software中，software的出现不仅仅依赖于source，而是依赖于open source这样的一个二词的组合。

基于这样的限制，我们考虑一种变长的Markov模型-Variable Memory Markov （VMM）model。在这个模型中，我们允许变长的上下文，而给这个变长设定一个上限Nmax。为了具体实现VMM，我们采用了一种基于Prediction Suffix Tree (PST) 的实现。

如图所示的PST是一个树状结构，其中根节点e是一个无意义节点。所有其它节点均表示某个文档，比如我们有文档a，b，c，d。每一个内部节点都表示一个上下文序列，这个序列即为从此节点到根节点的路径上的所有节点。比如，红色圈中的节点a即代表了一个序列为“ab”的上下文。每个叶节点表示了在给定了他的父节点所表示的上下文的情况下的下一个可能的文档。比如，框中的 1.0表示在给定序列ab后，那么下一个文档概率为1的应该是c。

在我们的构架中，我们利用了Offline-Online的两阶段过程。如图所示，

在离线阶段，我们从收集的历史数据学习得到一个PST树，然后当在线进行推荐时，我们只需要基于训练得到的PST来预测下一个文档。其中，VMM的学习算法同样基于最大似然估计的原理，详细的介绍需要公式太多，这儿暂且略过。

对于数据稀疏，我们采用了两类解决思路，一是利用模型的剪枝才做来简化模型，而是利用平滑的一些技巧。到底用什么样的标准作做剪枝，以及哪种平滑技术的效果更好，都是论文重点研究的问题。论文中，我们有详尽的实验论证，感兴趣的读者可以参考。

5. 实验和总结

总结一下，我们明确了实际内容管理平台上的文档推荐问题，并且把这个问题形式化成为一个基于序列的文档预测问题。在调研了语言模型里的方法后，我们采用VMM/PST模型构建了Offline/Online的两阶段方法来处理这个问题。细节上，我们采用剪枝和平滑的方法来处理数据稀疏行的问题。在实际收集的数据上，我们的方案能够达到接近80%的推荐准确率。数字显示了方法的有效性，同时也说明还有提高的空间。对文档推荐感兴趣的研究人员可以给我们提提新的想法，或者一起工作把精度进一步提高。

附： 作者在KDD上介绍这项工作时使用的照片。

原文连接：http://blog.sina.com.cn/s/blog_67897ff801015lsq.html