可扩展和自适应的协同过滤，挖掘频繁项目coo。外文翻译资料

Scalable and adaptive collaborative filtering by mining frequent item co-

occurrences in a user feedback stream

A. Murat Yagcia,⁎, Tevfik Aytekinb, Fikret S. Gurgena

a Department of Computer Engineering, Bogazici University, Bebek 34342, Istanbul

b Department of Computer Engineering, Bahcesehir University, Besiktas 34349, Istanbul

A B S T R A C T

Neighborhood-based methods are one of the mainstream approaches to collaborative filtering. A common problem with these methods is scalability to large number of users and items. Consequently, the adaptivity of a neighborhood-based model to system dynamics is often compromised due to model constraints and prolonged training intervals. These drawbacks can be important in designing demanding applications of today and the future. In this paper, we propose a novel real-time scalable and adaptive collaborative filtering algorithm,SASCF, suitable for personalized and item-to-item recommendations, in which the underlying neighborhood-based model is updated on-the-fly with the streaming user feedback. The algorithm does not perform an offline search for finding nearest neighbors in a full item similarity matrix. Instead, taking a landmark window over the user feedback stream, a space-efficient summary structure is maintained. This structure corresponds to the result of a standing iceberg query for finding every items top-k frequently co-occurring items over a specified support threshold. Mining such frequent co-occurrences can facilitate approximate computation of several useful item similarity measures. The algorithm offers scalability thanks to the space-efficient summary structure which handles ever-changing users, items, and item similarities in a resource aware fashion. It also offers

adaptivity in the sense that newly arriving user-item interactions are immediately integrated into the model. The model is always up-to-date and it can readily be used to recommend items to users with the most recent information.

Keywords:Collaborative filtering、Recommender systems、Data stream mining、Real-time intelligent systems、 Nearest neighbor search

1. Introduction

Collaborative filtering is an information filtering technique based on past interactions between system users (or agents) and items rather than specific user or item features. It has been widely and successfully used in recommender systems (Ricci et al., 2015). Accuracy, recall,diversity, robustness, and privacy preservation are among commonly desired performance criteria of such systems. Moreover, in todays demanding applications, scalability and adaptivity are two additionally important performance criteria. The former refers to systems ability to deal with large collections of users and items together with their massive interactions. The latter may refer to a faster response to dynamic nature of these collections due to new users, new items, and recent user interactions with the system, as well as adaptation in the presence of concept drift. Fulfilling these criteria facilitates recommen- dation of large-scale durable items as well as fast-moving items, for

example, in news and social networks. Collaborative filtering can be used for personalized or item-to-item recommendations. Ways for achieving personalization include recom-mending to a user top-N similar items to her item preference history,or recommending to a user items by looking at item preferences of similar users. Without the personalization step, collaborative filtering can still be used to define a similarity between items based on item preferences of many collaborating users, which enables item-to-item recommendations.Neighborhood-based methods (Ricci et al., 2015, Chapter 2) are one of the mainstream approaches to collaborative filtering. A common problem of these methods is scalability (Deshpande and Karypis, 2004; Vinagre et al., 2015). Consequently, the adaptivity of a neighborhood-based model to system dynamics is often compromised due to model constraints and prolonged training intervals with the increasing numbers of users, items, and their interactions. These drawbacks can be important in many demanding applications and they are our first motivation for this study. One way to approach problems in achieving scalability and adaptivity is to design collaborative filtering algorithms using the data stream model. Data stream mining (Leskovec et al., 2014; Gama, 2010;Liberty and Nelson, 2012) uses this model to maintain informative and space-efficient summaries of data by performing incremental updates as it streams. The summaries and the associated mining algorithms can facilitate resource aware computing, and they are useful for both server-side massive scale stream processing and in-device processing where computational resources are scarcer. Moreover, processing data gradually as it arrives can often make a more efficient use of available computational resources compared to batch processing (Miner and Shook, 2012). Therefore, our second motivation for this study is that although data stream mining approaches can be used for scalability and adaptivity to temporal dynamics, such approaches are not common (Vinagre et al., 2015) in the case of neigborhood-based collaborative filtering. In this work, we propose a novel real-time neighborhood-based collaborative filtering algorithm by extending ideas from data stream mining to improve scalability and adaptivity. The interactions between users and items are assumed to be binary, that is, a positive interaction or no interaction at all which is a very common real life scenario (Gantner et al., 2011; Vinagre et al., 2014). If there is extra assessment information in the stream, such as a rating, it can be used to define a binarization threshold. Instead of an item similarity matrix, the algorithm maintains very compact summaries of frequent cooccurrences of every item. These summaries are achieved by single pass frequent item finding algorithms for stre

剩余内容已隐藏，支付完成后下载完整资料

可扩展和自适应的协同过滤，挖掘频繁项目coo。

用户反馈流中的事件。

A. Murat Yagcia，， Tevfik Aytekinb, Fikret S. Gurgena。

博加兹大学计算机工程系，Bebek 34342，伊斯坦布尔。

b计算机工程系，Bahcesehir大学，贝西克塔斯34349，伊斯坦布尔。

A B S T R A C T。

基于邻域的方法是协同过滤的主流方法之一。这些方法的一个常见问题是对大量用户和项目的可伸缩性。因此，由于模型约束和训练间隔的延长，基于邻域模型对系统动力学的适应性常常受到损害。这些缺点在设计今天和将来的应用时很重要。在本文中，我们提出了一种新型的实时可伸缩和自适应协同过滤算法SASCF，适用于个性化和逐项的推荐，在此基础上，底层的基于邻域的模型在流用户反馈中实时更新。该算法不执行离线搜索，寻找一个完整的项目相似矩阵中的最近邻居。相反，在用户反馈流上使用一个具有里程碑意义的窗口，将维护一个空间高效的概要结构。这个结构对应于一个站立的冰山查询的结果，该查询用于在指定的支持阀值上查找每个项目的top-k经常共同发生的项目。挖掘频繁的联合事件可以方便地计算几个有用的项目相似性度量。该算法提供了可伸缩性，这得益于空间高效的概要结构，该结构可以处理不断变化的用户、项目和资源感知方式中的项目相似性。它还提供了

自适应的感觉是，新到的用户项目交互将立即集成到模型中。该模型总是最新的，它可以随时向用户推荐最新的信息。

关键词:协同过滤，推荐系统，数据流挖掘，实时智能系统，最近邻搜索。

1。介绍

协同过滤是一种信息过滤技术，它基于系统用户(或代理)和项目之间的过去交互，而不是特定的用户或项目特性。它已广泛应用于推荐系统(Ricci et al.， 2015)。准确性、召回、多样性、健壮性和隐私保护是这些系统的常见性能标准之一。此外，在当今的要求很高的应用程序中，可伸缩性和适应性是另外两个重要的性能标准。前者指的是系统处理大量用户和项目的能力以及它们之间的巨大交互作用。后者可能是由于新用户、新项目和最近用户与系统的交互，以及在概念漂移的存在下的适应，对这些集合的动态特性的快速响应。满足这些标准有助于为大规模耐用品和快速移动项目的推荐。

例如，在新闻和社交网络中。协同过滤可用于个性化或逐项推荐。实现个性化的方法包括对用户的项目偏好历史进行重新组合，或者通过查看类似用户的项目偏好来推荐用户项。在没有个性化步骤的情况下，仍然可以使用协作过滤来定义基于许多协作用户的项目偏好的项目之间的相似度，从而支持逐项推荐。于社区的方法(Ricci等人，2015，第2章)是协同过滤的主流方法之一。这些方法的一个常见问题是可伸缩性(Deshpande和Karypis, 2004;Vinagre et al .,2015)。因此，由于模型约束和长时间的训练间隔，随着用户、项目和交互的增加，基于社区的模型对系统动力学的适应性常常受到损害。这些缺点在许多苛刻的应用程序中都很重要，它们是我们研究的第一个动机。解决可伸缩性和适应性问题的一种方法是使用数据流模型设计协同过滤算法。数据流挖掘(Leskovec et al.， 2014;Gama, 2010;Liberty和Nelson, 2012)利用这个模型，通过在数据流中执行增量更新来保持数据的信息和空间效率的总结。概要和相关的挖掘算法可以促进资源感知计算，它们对于服务器端大规模流处理和在设备处理中非常有用，因为计算资源非常少。而且，随着它的到来，处理数据的逐渐增加，通常会比批处理(Miner and抖动，2012)更有效地利用可用的计算资源。因此，本研究的第二个动机是，尽管数据流挖掘方法可用于可扩展性和对时间动态的适应性，但这种方法并不常见(Vinagre et al.， 2015)，以基于neigborhood的协同过滤为例。在这一工作中，我们提出了一种新的实时的基于邻域的协同过滤算法，该算法通过扩展数据流挖掘的思想来提高可扩展性和自适应能力。用户和项目之间的交互被认为是二进制的，也就是说，一个积极的交互或根本没有交互，这是一个非常常见的真实场景(Gantner et al.， 2011;Vinagre et al .,2014)。如果在流中有额外的评估信息，比如评级，它可以用来定义二值化阈值。该算法不使用项目相似矩阵，而是对每一项的频繁出现进行了非常紧凑的总结。这些总结是通过对流进行单次频繁项查找算法来实现的，这些算法也可以根据需求随时返回近似的top-k频繁项。据我们所知，我们的第一个工作是将这个算法家族应用于基于邻域的协同过滤。所得到的摘要所取得的项目相似矩阵压缩比可以在第4节中给出。挖掘的共点可以方便地计算出几个有用的相似性度量方法来决定一个项目的最近邻居(NNs)。建议的协同过滤方法适用于个性化和非个性化的逐项推荐。本文的主要贡献如下:

bull;在流中扩展频繁项查找算法，以有效地发现流中频繁出现的top-k。这些共存曲线始终是最新的，它们被证明有助于计算若干有用的项相似性度量。

bull;一种新型的可伸缩和自适应的基于社区的协同过滤算法SASCF，它可用于个性化或项目到项目的推荐，并提供系统中最新的信息。该算法具有资源意识，可以通过控制参数利用现有系统资源实时生成智能结果。

bull;利用所提出的摘要结构，对一个完整的项目相似矩阵进行压缩，给出了理论和实证结果。此外，该结构还保持了在排序顺序中与它们的近似计数一致的top-k项目。

bull;我们通过经验证明，排序后的物品的共同出现证明了幂律分布。我们还展示了为每个人捕捉top-k共同事件的支持阈值。项目通常分布在不同数据集的单一模式下。

bull;我们对所提出的协同过滤算法的排序能力进行了综合的实证结果，并通过各种方法对算法进行了基准测试。从不同的推荐领域中得到了4个大的真实生命数据集的结果。

本文组织如下:我们在第2节中提到相关的工作。然后，我们介绍了在第3部分中提出的可伸缩和自适应协同过滤的建议方法的细节。第4节给出了实际生活数据集的实验和实验结果。最后，我们的结论和进一步的研究可能性在第5节中给出。

2。相关工作

我们总结了与我们的工作相关的关键文献。

不同的部分。

协同过滤

关于协同过滤的大量文献的重要参考文献(Ricci et al.， 2015;Bobadilla et al .,2013)。我们专注于与工作相关的部分。在(Deshpande和Karypis, 2004)中描述了一种基于内存的协同过滤算法，在这里，基于项目的社区搜索被用来向用户推荐top-N项目。本文还讨论了各种项目相似性度量的效用。这样一种算法的增量版本可以计算出用户之间基于皮尔逊-相关的相似点(Papagelis et al.， 2005)。算法假定数据流的形式〈用户,项目,评级〉元组和商店簿记变量所有可能的user-user对执行必要的更新。虽然报告了改进的运行时间，但每次更新都需要与用户数量保持线性关系，并且在主内存中维护一个完整的相似矩阵。一个相关的概念(Miranda和Jorge,2009)被报告为二进制评级，“用户”，“项目”，在内存中，两个完整的矩阵分别保持一致和相似。另一种增量算法是在(roet al.， 2013)中提出的，在该算法中，利用轻量级相似性函数实现了一些空间优势，而不损失预测精度。这些增量算法是精确的，它们试图在一次传递中完成所需的更新。但是，他们并没有试图保持对有用信息的空间有效的总结，这在使用大型项目存储库时可能会出现问题。此外，它们还需要在最后的相似矩阵上进行后处理以找到最近邻。我们的工作提供了关于这两个方面的研究。

个性化推荐在推荐之前考虑用户的交互历史。然而，许多工业应用都提供非个性化的逐项推荐列表(Hidasi和Tikk,2013;Koenigstein and Koren, 2013)，比如那些与“经常购买的物品”相对应的物品，以及“通过考虑单个或非常少的物品相互作用来看待这个问题的人”。这可能是由于缺乏个人信息或响应时间限制。由于我们的协作过滤方法提供了最新和高效的顶级查询，因此个性化和项目到项目的建议对于大型动态项目存储库来说变得更便宜了。

与网上个性化推荐算法的文献相反，这种算法以渐进的方式学习，但也允许多次传递数据，因此，使用严格的数据流模型的推荐算法文献非常有限(Vinagre et al.， 2015)。从这一模型借鉴的几个初步设想已经在(Nasraoui et al.， 2007;华et al .,2011)。基于流采样的矩阵分解(Koren et al.， 2009)已经在(diazar - aviles et al.， 2012;陈et al .,2013)。(罗et al .,2012;Recht和Re, 2013)，作者展示了可伸缩建议的矩阵分解模型的并行批量计算方法。这种潜在的因素模型通常需要多次传递数据才能收敛。此外，尽管通过并行化可能减少模型计算时间，但它们通常更适合于预先计算的建议而不是自适应。在(Vinagre et al.， 2014)中，有人认为，单次增量矩阵分解对于从正态反馈流中学习是很有用的，而对于效率的最重要的建议中，有一些是需要权衡的。本文还提出了一种数据流模型的评价协议。我们将在第4.3节中进一步讨论此方法，并将其与我们的建议进行比较。在(Lommatzsch和Albayrak, 2015)的新闻推荐领域中，比较了一组简单的基于流的非个性化推荐，并采用了一种基本的协同过滤方法，该方法只使用最近的和有限的用户交互，这些交互适合于缓存。它依赖于这些减少的交互量来减少生成建议列表的时间。最近的一些有趣的方法是基于实时项目的专有推荐系统，利用现有的分布式计算框架(Huang et al.， 2015)，以及基于实时事件处理系统的概念协同过滤思想的证明(Ludmann, 2015)。

3。方法

我们首先在3.1节中解释了协同过滤方法的基础。然后，在第3.2节中，我们继续扩展寻找频繁项的想法，以便在流中找到频繁的项。对于流程中的每一个不同的项目，都将维护其经常出现的项目的摘要。换句话说，每个摘要包含了在流中的一个不同的项条件下的频繁项。top-k经常在一个项目的摘要中共同出现的项目可以被认为是它最近的邻居的近似值。提出的协同过滤算法，SASCF，将一个完整的项目相似矩阵替换为一个更加压缩的摘要结构，该结构可以为每个项目和排序顺序提供近似的top-k联合出现。在第3.3节中，详细阐述了个性化和项目到项目的建议。基于top-k项目共发生的相似性度量是用于推荐目的，而无需进一步需要一个离线的最近邻搜索算法。我们在3.4中对我们的方法和计算复杂性进行了比较分析。

3.1。预赛

3.1.1。于社区的协同过滤

于社区的协同过滤算法(里奇et al .,2015年,第2章)通常测量user-item偏好的用户或项目之间的相似度矩阵,Risin;ℝ|ge;情况|times;| |,对相似性函数,其中U是组用户在系统中,我是项目的集合。在基于用户的方法中，大多数类似用户对用户的偏好在提出建议时被考虑，而在基于项目的方法中，大多数类似的项目都考虑到用户的项目偏好历史。我们的协同过滤方法是基于一个广泛使用的基于离线项目的协同过滤算法(Deshpande和Karypis,2004)，我们将其命名为OFFLINECF。我们的主要目标是实现一个更可伸缩的、自适应的协同过滤算法，同时在OFFLINECF中保留推荐的质量。

OFFLINECF工作如下:在模型建立阶段,对于每一个项目我isin;,k计算最相似的物品与相应的相似之处。这些相似之处通常要求建立的准确计算,更新和存储物品相似度矩阵,年代isin;ℝ|我|times;| |。一个评级预测步骤并不一定要执行，因为首要目标是最重要的建议。头N个推荐问题对应于确定一组有序的物品我′sub;我′,| |le;N,我′cap;Iu =empty;,和Iu是一组特定用户uisin;已经与之交互。解决这个问题查询用户u,C所识别的候选项集的联盟每个我isin;Iu的k最相似的物品,从欧盟通过移除任何东西已经在国际单位。对每项产品icisin;C,相似性Iu集被认为是相似的和所有的物品我isin;Iu和ic,只使用k最相似的物品我。最后,C是降序排序的项目对这个和相似性和前N项选为头N个列表。前n预测阶段使上述算法具有个性化。相反,如果新的交互的用户你的项目,我们只是建议我Nle;k最相似的物品,这可以被视为一种非个性化item-to-item建议。例如，在二进制交互的情况下，使用cos或dot产品(Lee et al.， 2007)相似度，系统可以回答诸如“经常购买的商品”和“查看这类商品的人”之类的查询。本文提出的方法将这类算法扩展到一个实时的环境中，并结合了更多的可扩展性和适应性的解决方案。我们注意到，我们的方法不同于项目的相似点，它也可以被用来有效地发现和保持用户的相似点，但是我们并没有在这个工作中进一步利用这个想法。

3.1.2。监控经常项目和频繁的top-k项目。

为了便于讨论，在算法1中，我们举例说明了在一个流中查找频繁项的单遍频繁算法(Karp et al.， 2003;自由,2013)。让我成为|的一组|不同的项目，S是n个项目的流。我说的一个项目的频率数fi是它在流中出现的次数。如果允许我们使用| i |计数器，那么保持所有精确的项目频率是很简单的。但是,算法1可以确保O(l)空间(l =lfloor;1 /ϕrfloor;和l lt; lt; | |)中使用最坏的情况下,近似频率计数,胃肠道,forall;我,fiminus;gile;n / l。此外,所有项目与fi gt;ϕn保证在k的关键操作的算法删除一个外观计数器中的每一项,如果计数器都忙得不可开交。更新操作确保流汇总总是存储在大多数l计数器中，gi是对真实频率计数fi的有用近似，即使gi=0。我们展示了在3.2节中发现频繁项共同出现的想法的有用性。

算法1。单通过频繁的算法。

输入:学生:一连串的物品,ϕ:支持阈值

输出:凯西:Lsube;K,L是频繁项集满足ϕ

(1)K []; 剩余内容已隐藏，支付完成后下载完整资料

资料编号：[22009]，资料为PDF文档或Word文档，PDF文档可免费转换为Word