英语原文共 28 页

在协同过滤中使用应用关联检索技术缓解稀疏性问题

ZAN HUANG, HSINCHUN CHEN, and DANIEL ZENG

亚利桑那大学

当今推荐系统在许多应用中广泛应用，用于向潜在的消费者提供产品、服务和信息项目上的推荐。最成功的协同过滤算法是基于过去的事务和反馈来推荐给来自拥有相似利益的消费者。限制协同过滤有效性的一个主要问题是稀疏性问题，它指的是事务或反馈数据稀少不足以识别消费者兴趣的相似性的情况。在本文中，我们提出利用关联检索框架和相关的扩散激活算法，通过消费者过去的交易和反馈来探索消费者之间的传递关联，从而解决这一稀疏性问题。这种传递关联是一个有价值的信息来源，有助于推断消费者的兴趣，并可以探讨如何处理稀疏性问题。为了评估我们的方法的有效性，我们使用一家网上书店的数据集进行了一项实验研究。我们尝试了三种扩展激活算法，包括约束漏电容算法（constrained Leaky Capacitor algorithm）,分支约束串行符号搜索算法（branch-and-bound serial symbolic search algorithm）和Hopfield网络并行松弛搜索算法（Hopfield net parallel relaxation search algorithm）。将这些算法与不考虑传递关联的几种协作过滤方法进行了比较:一种简单的图搜索方法、两种基于用户的方法变体和一种基于项的方法。我们的实验结果表明，基于传播激活的方法在推荐精度、召回率、f -测度和等级得分上显著优于其他协同过滤方法。我们还观察到传播激活方法的过度激活效应：将传递关联与非稀疏的过往事务数据合并，可能会“稀释”用于推断用户首选项的数据，导致推荐性能下降。

本研究获得以下部分资助:NSF数字图书馆计划-2，“高性能数字图书馆系统:从信息检索到知识管理”，IIS-9817473, 1999年4月至2002年3月，以及NSF信息技术研究，“开发协作信息和知识管理基础设施”，IIS-0114011, 2001年9月至2004年8月。曾博士还隶属于中国科学院(CAS)复杂系统与智能科学重点实验室，获得了中国科学院开放研究项目(ORP-0303)的部分资助。作者地址:亚利桑那州大学管理信息系统系，地址:亚利桑那州图森市海伦东街1130号麦克莱伦大厅430室，邮箱:AZ 85721{壮族,hchen,曾庆红}@eller.arizona.edu.Permission允许将部分或全部作品的数字或硬拷贝用于个人或课堂使用，但不收取任何费用，前提是这些拷贝不是为了利润或直接的商业利益而制作或分发的，并且这些拷贝在显示的第一页或初始屏幕上显示此通知以及完整的引用。必须尊重ACM以外的其他人拥有的此作品组件的版权。允许用信用证提取。以其他方式复制、重新发布、在服务器上发布、重新分发到列表或在其他作品中使用此作品的任何组件都需要事先获得特定的许可和/或费用。可向美国纽约百老汇大街1515号，ACM, Inc.，邮编10036，传真: 1(212)869-0481，或permissions@acm.org请求许可。

C 2004 ACM 1046-8188/04/0100-0116 $5.00

稀疏性问题的关联检索技术

类别和主题描述符：H.1.2[模型与原理]:用户/机器系统-人的信息处理;H.3.3[信息存储与检索]:信息检索与检索信息过滤;相关性反馈;检索模型。

一般术语:算法，设计，实验

关键词:推荐系统，协同过滤，稀疏性问题，联想检索，传播激活

1. 介绍

推荐作为一种社交过程在许多应用程序中对消费者来说扮演着重要的角色，因为对于每个消费者来说，独立地了解所有可能的替代方案是非常昂贵的。根据特定的应用程序设置，消费者可能是购买者(例如，在网上购物中)、信息寻求者(例如，在信息检索中)或搜索特定专业知识的组织。此外，推荐作为一种个性化的营销机制，最近引起了业界的极大兴趣(如网上购物和广告)。

推荐系统的开发使推荐过程自动化。推荐系统研究原型的例子有:PHOAKS [Terveen et al. 1997]， Syskills and Webert [Pazzani and Billsus 1997]，Fab [Balabanovic and Shoham 1997]， GroupLens [Konstan et al. 1997;Sarwar et al. 1998]。这些系统向潜在的相关方推荐各种类型的Web资源、在线新闻、电影等。推荐系统的大规模商业应用可以在许多电子商务网站找到，如亚马逊、CDNow、药店和MovieFinder。这些商业系统根据以前的交易和反馈向潜在消费者推荐产品。它们正在成为标准电子商务技术的一部分，通过将浏览器转换为购买者、增加交叉销售和建立客户忠诚度，这些技术可以增强电子商务销售[Schafer et al. 2001]。

最常用和最成功的推荐方法之一是协同过滤方法。[Hill et al. 1995;Resnick et al. 1994;Shardanand and Maes 1995]。在预测给定消费者的潜在利益时，该方法首先根据过去的交易和产品反馈信息识别一组相似的消费者，然后根据这些相似消费者的观察行为进行预测。尽管协作过滤被广泛采用，但它仍受到几个主要限制，包括稀疏性、系统可伸缩性等等[Sarwar et al. 2000a]。

在本文中，我们将重点讨论稀疏性问题，稀疏性问题是指缺乏预先的事务和反馈数据，这使得预测哪些消费者与给定的消费者相似变得困难和不可靠。例如，在线书店使用的推荐系统使用过去的购买历史对消费者进行分组，然后根据同一组中的其他消费者购买了什么向单个消费者进行推荐。然而，当这样的系统只能访问少量的过去的事务记录(相对于图书和消费者的总数)时，确定哪些消费者彼此相似以及他们的兴趣从根本上变得困难。

本文提出了一种在协同过滤环境下处理稀疏性问题的新方法。在我们的方法中，我们研究了二部图（bipartite graphs）中的协同过滤。一组节点表示用于潜在消费的产品、服务和信息项。另一个集合代表消费者或用户。事务和反馈被建模为连接这两个集合之间的节点的链接。在这个基于图形的框架下，我们应用关联检索技术，包括几种扩散激活算法，显式地生成传递关联，并将其用于协同过滤。初步实验结果表明，当稀疏性存在时，这种基于关联检索的方法可以显著提高协同过滤系统的有效性。

本文的其余部分组织如下。第2节概述了现有的协同过滤工作，并详细讨论了稀疏性问题。第3节总结了我们处理稀疏性问题的基于关联检索的方法。3.1节介绍了协同过滤的关联检索和相关的基于图的模型。第3.2节详细介绍了我们提出的基于关联检索的协同过滤方法的总体设计。第3.3节介绍了扩展激活算法，它提供了在我们的框架下用于探索传递关联的计算机制。我们打算解决的具体研究问题总结在3.4节中。第四部分详细介绍了我们研究的扩散激活算法。第5节提出了一项实验研究，旨在回答第3.4节中关于我们方法有效性的研究问题，并总结了实验结果。在第6节中，我们总结了我们的研究成果，并指出了未来的发展方向。

1. 协同过滤与稀疏性问题

在这一节中，我们简要回顾了以往关于协同过滤的研究和系统开发，并介绍了稀疏性问题，这是阻碍协同过滤系统进一步开发和采用的主要技术挑战之一。

2.1协同过滤

协同过滤通过聚合系统中相似用户的经验来生成个性化推荐。从概念上讲，这种方法使“口碑”推荐过程自动化。协同过滤的一个关键方面是识别与需要推荐的用户类似的消费者或用户。聚类模型、贝叶斯网络模型和专门的关联规则算法等技术已被用于这一识别目的[Breese et al. 1998;Lin等。2002]。基于相似的消费者或邻居，可以使用最常用的商品方法[Sarwar et al. 2000a]来生成推荐。

协同过滤是迄今为止最成功的推荐系统方法[Sarwar et al. 2000a]，并已广泛应用于各种应用[Burke 2000;Claypool等，1999;Mobasher et al. 2000;asraou等，1999;Pazzani 1999;Sarwar et al. 1998]。尽管协作过滤方法在许多应用程序设置中取得了成功，但据报告，它有几个主要限制，包括稀疏性、可伸缩性和同义词问题[Sarwar et al. 2000b]。当事务或反馈数据稀疏且不足以识别邻居时，就会出现稀疏问题，这是限制推荐质量和协作过滤适用性的主要问题。我们的研究重点是开发一种有效的方法，即使在没有足够的数据的情况下也能提出高质量的建议。下一节将详细讨论稀疏性问题。

2.2稀疏性问题

在协同过滤系统中，用户或消费者通常由他们购买或评级的物品来表示。例如，在一个销售200万本书的在线书店中，每个消费者都由一个包含200万个元素的布尔特征向量表示。每个元素的值取决于该消费者是否在过去的交易中购买了相应的图书。通常，值1表示发生了这样的购买，0表示没有发生这样的购买。当涉及多个使用者时，可以使用由表示这些使用者的所有向量组成的矩阵来捕获过去的事务。我们称这个矩阵为消费者-产品交互矩阵。一般术语“交互”指的是这个矩阵，而不是更具体的“购买”或“交易”，因为对于一般的推荐系统，还有其他类型的关系，如消费者和产品之间的显式和隐式评级。210/5000

现在我们介绍一些贯穿整篇文章的符号。我们用C表示消费者的集合，P表示商品的集合。我们表示消费者-商品交互矩阵C | |times;| | P矩阵a =(aij),这样表示：

注意，在我们的研究中，我们关注实际发生的事务，所以aij是二进制的。在其他推荐场景中，如涉及评级的场景中，aij可以采用其他类别或连续值(例如，5级评级量表和感兴趣的概率)。

在大型电子商务网站等大型应用中，无论是商品数量|P|，还是消费者数量|C|，都是很大的。在这种情况下，即使记录了很多交易，消费者-产品交互矩阵仍然可以是非常稀疏的，即A中只有极少数元素的值为1。这个问题通常被称为稀疏性问题，它对协作过滤方法的有效性有很大的负面影响。由于稀疏性，两个给定用户之间的相似性(或相关性)很可能为零，使得协作过滤无效[Billsus and Pazzani 1998]。即使对于正相关的用户对，这种相关度量可能也不可靠。

冷启动问题进一步说明了解决稀疏性问题的重要性。冷启动问题是指新用户或项目刚刚进入系统的情况[Schein et al. 2002]。协同过滤不能为新用户生成有用的推荐，因为缺乏足够的以前的评级或购买。类似地，当一个新项目进入系统时，协同过滤系统不太可能向很多用户推荐它，因为很少有用户对这个项目进行评级或购买。从概念上讲，冷启动问题可以看作是稀疏性问题的一个特殊实例，其中消费者-产品交互矩阵a的某些行或列中的大多数元素为0。

许多研究人员试图缓解稀疏性问题。Sarwar等人[2001]提出了一种基于项目的方法来解决可伸缩性和稀疏性问题。基于事务或反馈数据，识别出与目标用户过去购买的产品类似的产品，然后推荐。将项目相似性计算为对应列(项)向量之间的相关性。据报道，在某些应用中，这种基于项目的方法比基于用户的方法获得了更好的推荐质量，后者是推荐系统中使用的主要方法，它依赖于行(用户)向量之间的相关性

另一种被提出的方法，降维，旨在直接降低消费者-产品交互矩阵的降维。一个简单的策略是形成项目或用户的集群，然后使用这些集群作为基本单元进行推荐。可以采用更先进的技术来实现降维。例如统计技术，如主成分分析(PCA) [Goldberg et al. 2001]和信息检索技术，如潜在语义索引(LSI) [Billsus and Pazzani 1998;Sarwar et al. 2000b]。实证研究表明，降维在某些应用中可以显著提高推荐质量，但在其他应用中效果不佳[Sarwar et al. 2000b]。降维方法通过去除不具有代表性或无关紧要的消费者或产品来压缩消费者-产品交互矩阵来解决稀疏性问题。然而，在此缩减过程中可能会丢失潜在的有用信息。这可能部分解释了基于降维的协同过滤方法在性能方面的混合结果。

研究人员还试图将协作过滤与基于内容的推荐方法结合起来，以缓解稀疏性问题[Balabanovic and Shoham 1997; Basu et al. 1998; Condliff et al. 1999; Good et al. 1999; Huang et al. 2002; Pazzani 1999; Sarwar et al. 1998]。这种方法不仅考虑了过去消费者与产品之间的交互作用，而且考虑了直接从产品的内在属性或属性派生出来的产品或产品之间的相似性。我们将这种方法称为混合方法。以前使用混合方法的大多数研究表明，与上面讨论的基于用户的方法相比，推荐质量有了显著的提高。然而，混合方法需要关于产品的额外信息和度量来计算它们之间有意义的相似性。在实践中，获取这样的产品信息可能很困难或很昂贵，并且可能不容易获得相关的相似性度量。

我们的研究在不同的框架下处理稀疏问题。我们并没有减少消费者-产品交互矩阵A的维数(从而使其不那么稀疏)，而是建议探索消费者与产品之间的传递交互，以扩充矩阵A，并使其具有有意义的“密集”，以供推荐之用。传递交互背后的直觉可以用下面的例子来解释。假设用户c1和c2买了书p1 c2和c3买了书p2。不考虑传递交互的标准协同过滤方法将c1与c2关联，c2与c3关联，但c1与c3不关联。然而，一种包含传递交互的方法将识别c1和c3之间的关联关系，并将这种传递交互插入到消费者-产品交互矩阵A中以获得建议。

我们的研究重点是开发一种计算方法来探索传递用户和项目的相似性，以解决协同过滤环境下的稀疏性问

资料编号：[4246]