从社区检测到导师选择Rating-Free协同过滤

文摘

现在物品的数量,用户可以访问当Web上的导航是如此巨大,这些可能会感到迷失。推荐系统的方法来处理这个缤纷数据显示项符合用户需求。最受欢迎的技术推荐系统的协同过滤方法依赖于商品的偏好表达的用户,通常在形式的评级。在缺乏评级的情况下,传统的协同过滤技术不能应用。幸运的是,用户的行为,如他们的磋商,可以收集。在本文中,我们提出一个新的方法来执行协同过滤当没有可用评级但当用户协商是已知的。我们建议采取灵感来自当地社区检测算法形成社区的用户和推断的导师给定的用户。我们适应一个最先进的算法,以适应协同过滤的特点。实验表明,精度达到更高的基线不执行任何导师选择。另外,我们的模型几乎抵消了缺乏评级利用一套减少的导师。

1。介绍

民主化的互联网和网络技术导致了大量增加的信息,能为每一个人。这种增长是一个优势在其第一年的获取信息成为广义。然而,信息现在的体积如此巨大,用户无法轻易得到的信息搜索和淹没在资源的质量。这种过剩经常导致不满足用户的影响。

因此,当前的Web应用程序的一个关键问题是传递信息的整合机制,符合用户的需求,同时提高他们的满意度。

推荐系统(RSs)为用户提供个性化的推荐的资源或项目,基于他们对用户的知识。最近的观察显示,用户现在意识到自己的需要帮助(1和准备采取推荐系统2]。这些系统的日益普及信息寻求或商业电子商务意味着需要质量、精度和可靠性的建议已成为巨大的。推荐系统一般分为三类:基于内容的系统计算语义内容的推荐项目(3),以知识为基础的系统,建议依靠知识域,用户和预先制定启发式(4),最后协同过滤系统计算建议通过研究用户的偏好上项目,或他们的过去与系统的交互,叫的痕迹使用(5]。

协同过滤(CF)背后的一般原则可以总结成一句话:一个活跃的用户可能喜欢的东西他志同道合的用户(也称为邻居或导师)以前喜欢和他或她还没有咨询。用户通常表达是否他们喜欢一个项目评级(的形式下6]。基于这一信息,CF标识的用户类似的评级与活跃用户:他的导师。然后系统利用导师的集体知识的偏好,估计评级,这活跃的用户将分配给每一项他或她还没有评价。这种方式,系统能够确定哪些项目(s)推荐给用户:那些估计最高评级。

CF采用最近几年主要是由于这样的事实,不需要显式的用户信息先验:用户不需要填任何问卷或形式来得到一些建议。此外,不需要显式的信息项:避免繁琐和费时的索引任务(7]。此外,CF-based推荐的准确性提供给用户高相比,基于内容的方法(8),当系统变得足够数量(高)的评级。CF也有优势推荐项目不直接与这些活跃的用户已经喜欢。这一特性称为新奇或意外(9]。

CF的一个缺点是用户提供的评级的要求。依赖评级可能被惩罚,因为用户经常提供一些评级,不是说没有评级。事实上,将评级分配给一个项目是一个复杂和耗时的任务,和用户没有意识到的利益他们可以当评级项目。此外,用户提供的评级可能不可靠(10):在一个预定义的规模通常较小,评级应该分配给一个项目?例如,我们假设一个用户给定的电影,喜欢在1(他不喜欢)到5(他真的喜欢它)。他/她评级应该分配给这部电影吗?4或5 ?此外,在许多应用领域,系统不能要求用户条目。例如,当用户浏览网站或查阅新闻,问他们投票是不恰当的,因为它中断他们的信息寻求的过程。

标准CF依赖于相似性的计算评级(或偏好)用户执行导师之间选择。当没有可用评级,没有相似的偏好可以精确估计和古典CF技术无法使用。然后,问题是:如何选择导师时任何信息关于用户偏好(评级)和用户的相似性是已知的?

要回答这个问题,我们建议代表用户收集的系统在一个无关紧要的信息图。节点对应于用户。在图中,我们仅仅考虑到两个用户连接,如果他们有共同协商的行为。这个连接并不能反映偏好相似,但事实上,他们有一些常见的咨询项目。基于这种表示,我们调查的方法确定导师通过使用唯一的信息:图的结构(如没有体重相关的链接)。

社区检测算法是有效的检测社区或类图中的节点,专注于图的拓扑结构(11]。我们因此采取灵感来自社区检测算法,特别是一个当地社区检测算法从艺术的状态12),来解决协同过滤中的导师选择的问题。我们所知,图的结构,社区检测和当地社区检测算法从未利用帧的CF,特别是执行导师选择。

部分2侧重于CF和导师通常选择的方式。节3、社区检测和当地社区检测算法。部分4介绍我们的模型,利用当地社区检测算法来检测框架的导师CF。部分5和6分别是致力于这种新方法的评价和讨论的结果。最后,我们结束这项工作。

2。协同过滤

2.1。协同过滤一般

给定一组项目,和一组用户CF系统的输入数据集的评级用户已经分配给项目,大部分的时间在一个非二进制评定量表(例如,从1到5)。这组的形式存储在一个评级矩阵。让活跃的用户。对提出建议CF系统首先估计评级那将分配给所有的物品吗他还没有评价。第二,鉴于这组评分,系统建议项目估计评级最高的价值。在文献中,“提出建议”相当于估计用户的评级未分级的项目。

估计,该系统采用一种基于项目或基于用户的方法。基于项目的方法假设,用户将更有可能升值项目类似或相关的项目他已经喜欢。相反,基于用户的方法利用用户之间的相似性,并推荐一个用户的项目,他的志同道合的用户,或导师,感谢。在本文中,我们感兴趣的是基于用户的方法。

基本上有两种方法来实现基于用户的协同过滤算法,分别基于内存和基于模型的方法。基于内存的方法,也称为“懒惰学习”,仅仅利用了user-item评级矩阵没有任何变换当系统要求的建议。我们可以说,学习阶段是跳过。相反,基于模型的方法首先构建一个模型user-item评级矩阵,然后使用这个模型的提出建议。

2.2。基于内存的协同过滤

一个经典的方法估计评级中提出了基于内存的方法(1) 在哪里是一组用户评分项吗,是用户的评级吗已经分配给项目,用户的平均评级吗和是用户之间的相似性和。估计评级之间的绝对差的加权平均评级分配给项目的其他用户和他们的平均评级,添加到用户的平均评级。用户是相似的估计,他的体重就越高是多少。

两个用户之间的相似度是一个相似的评级,措施,如果两个用户评价(即。欣赏)项目以同样的方式。这种相似性是经典计算皮尔逊相关系数,提出了(2) 在哪里一般的用户评分项目的和和用户的平均评级吗。这种相关性测量已被证明是最适当的在基于用户的方法13]。

余弦度量也可以用来计算两个用户之间的相似度。相应的方程(3)提出了余弦度量计算 在哪里是项目的集合被。余弦度量已被证明是更有效的基于项目的方法,计算项目之间的相似度(14]。

相似度值(1)实例化相关或相似的价值(2)和(3)以上。文献[15概述方程,计算用户相似性或估计的评级。

虽然准确,但基于内存的方法受到组合复杂性问题,因为它需要计算每一对物品或用户之间的相似性。

2.3。基于模型的协同过滤

基于模型的协同过滤技术是一个不错的选择来降低时间复杂度的基于内存的协同过滤13]。这些算法包括在创建描述性模型关联用户,项目通过一个学习的过程和相关的评级。这些模型可以采取多种形式,如贝叶斯网络,类的物品和/或用户,等等。数据的基本理念是,部分知识可能足以提供准确的建议。作为一个例子,在1),只有一个子集的用户实际上是有用的估计。这个子集的用户被称为导师或社区的用户。在CF,导师是一个志同道合的用户代表用户用于计算估计的评级。导师的选择(及其数量)高度CF系统中影响三个主要功能:计算时间,估计评级的准确性和覆盖率。更具体地说,我们有以下。(我)导师选择优势加快评级评估过程只有一个子集的用户是用来评估评级16]。(2)导师选择增加推荐的准确性低相关的用户可能会降低估算的准确性(17]。此外,评级的准确性评估高度依赖于导师的充分性。(3)导师选择影响范围(18]。报道反映了推荐系统的能力来估计一个评级值对于一个给定的用户和一个给定的项。当没有评级可以估计的,没有可以执行的建议。导师的数量越低,覆盖率越低,因为导师已经评价项的概率很低。相反的,导师的数量越大,覆盖率越高。然而,这增加了计算时间。

鉴于这些特性,我们可以得出这样的结论:导师的选择是一个复杂和重要的任务高度影响的建议。

导师选择的两个主要方法中经常使用CF:直接邻居选择和集群。

2.3.1。直接邻居选择

给定一组有一个非空的用户相似度值,直接邻居选择在于保持符合给定条件的用户。

这一标准可以是一个阈值(19,20.]。相似度阈值是固定的先验的相似性和所有用户活跃用户超过这个阈值选择的导师。结果社区以用户为中心的。

标准也可以是一个整数值。的最近的邻居(资讯)被保留,固定一个先天(20.]。的邻居最高的相似度值作为导师的活跃用户(如果不到邻居的存在,所有的邻居都保持)。

直接邻居选择的一个主要缺点是可伸缩性。导师以来在运行时检测到所有用户的概要文件必须保存在内存中;每次重新计算用户相似性的导师选择和建议必须被执行。此外,的选择阈值的值或者是棘手。最后,然而,并不健壮的数据稀疏:它无法形成可靠的社区的高稀疏水平(21]。然而,相似之处是最新的建议时,以用户为中心的社区,这直接邻居选择方法是准确的。

2.3.2。聚类

第二种方法一般用于选择导师进行聚类。这些集群计算离线并定期构成模型重用生成的建议。根据如果基于项目或基于用户的选择方法,系统构建类的物品(14),或用户类(16]。基于项目CF是非常准确和高度改善可伸缩性,只要物品之间的关系保持相对静态的。基于项目的方法被广泛部署在一般工业和研究研究设置。然而,如前所述,在本文,我们将重点介绍如何基于用户的方法,因为它是更适合web应用程序项目极大的不稳定(16]:一组的物品经常改变,因为有些项目删除,新产品不断出现,一些其他修改。

具体地说,基于用户聚类识别用户组具有相似偏好,也就是说,那些似乎也有类似的评级13]。一旦创建集群,对活跃用户的建议可以利用所有用户的偏好(评级)属于集群的。

通常有三种聚类方法:分区(22),层次(16),和模糊技术(23]。大多数时候,CF依赖于一个分区技术。在这种情况下,用户分为分离集群:每个用户属于一个集群。

许多分区算法研究了CF的框架,如(24,25]。有些算法需要先验的集群,或一个固定大小的集群,其他相似度阈值,等等。这些算法参数。例如,k - means算法[22),计算集群,集群内平均成对用户之间相似性最大化。非参数算法的目标是最大化一个给定的标准(这通常代表的质量分类),没有任何参数选择手工(26]。

分区算法提供一个良好的集群技术之间的推荐精度。当推荐项目,利用集群的用户是健壮的可伸缩性问题,因为它降低了内存需求,和类计算离线。然而,分区算法经常遭受收敛问题,因为它们是高度敏感的起步条件(27]。此外,这类算法计算时间要求执行高。

层次聚类处理这些问题通过降低复杂性,加快收敛时间,允许计算的分布。Castagnos尤其是波伊尔提出了一个递归模型,简化了优化初始点的选择、人口分割到两个子集(每一步16]。然而,预期的质量是依赖数量的集群。如果集群的数量很低,该系统将提供不准确的建议。如果这个数字太大,有一个过度泛化的风险。

一个有趣的方式来避免偏见由于在于放松约束不好的集群化属于一个且只有一个类。这是模糊协同过滤的原则,分配的数据点集群并不困难(28]。

让我们观察,无论采用的方法,相似度值是利用;例如,它可能是一个在(2)或(3)。

在某些方法,相似度值与另一个标准结合使用。例如,[29日)提出了一个聚类算法的基础上,最近的邻居共享信息,除了他们的相似之处。在这种方法中,两个元素分组,如果他们分享他们的许多最近的邻居,如果他们是自己最近的邻居的其他元素。该算法已在许多领域,如信息检索中重用(30.)、数据库(31日和最近在数据流量32]。

2.4。讨论

在本节中,我们提出了CF中使用的主要方法选择导师。的直接邻居选择方法导致准确的建议。然而这种方法是可伸缩的和健壮的数据稀疏。集群的用户是解决这两个问题的一个方法33]。首先,它的优点只计算用户之间的相似性和定期选择导师,而不是每次需要的建议。第二,两个用户可能属于同一类相似,即使他们有一个空值(由于null corated项的数量)。第三,集群的大小没有先天的定义,然而,相反的方法和由此产生的集群,却可能有非常不同的大小。

然而这些聚类算法有几个缺点。(我)在大多数的聚类方法,用户仅属于一个集群。然而,在某些情况下,用户可能需要属于多个用户组。一些集群技术从而允许用户属于几个集群(34]。估计评级跨集群,然后平均加权在每个集群用户的参与程度。(2)一些用户可能边界节点(他们属于限制类的)。因此,他们的导师(那些在同一类)可能非常不同的实际最近的邻居,这可能会降低推荐性能。我们可以注意到这个缺点并不发生在使用直接邻居选择、社区形成的以用户为中心的。(3)尽管其应对能力的可伸缩性问题,众所周知,聚类生成的人越来越少所以不准确的建议(35,36]。(iv)一些作品集中在以用户为中心的集群。文献[17)提出了一种分散算法构建以用户为中心的集群。然而,复杂性仍然很高如果计算分布在大量的处理器。

不管导师选择的方法是什么,用户之间的相似度度量是必需的。因此,他们可以不使用的情况下没有相似性值是可用的。

基于上面的语句中,我们可以推断出发展中以用户为中心的社区或集群,其中每个用户可能属于多个社区(集群),将导致精度高的建议和解决稀疏和可伸缩性问题。

2.5。一元管理评级

大部分的工作在CF利用用户首选项评分的形式。正如前面提到的,在许多应用程序的情况下,评级不能被收集。只有用户磋商可能是已知的信息。这些磋商可以视为一元评级(咨询/没有咨询)。

当一元评级是可用的,可以使用三种主要方法。

第一种方法
旨在评估评级,用户将分配给项目如果他们认为他们。用户偏好估计从隐式反馈。在[37],飞船和金姆问题是否可能用隐式反馈代替显式的评级。他们提出三种类型的隐式反馈(检查、保留和引用)和一组可观察到的行为。Castagnos等人已扩展这项工作通过定义一个通用的隐式建模函数将隐式反馈到估计评级(38,39]。这种方法依赖于使用挖掘技术,从用法和推断偏好。通用函数首先收集每一个可能的隐式反馈。然后组织用户协商每项和每个用户,和综合数据下的标准形式。这些条件可能是时间和频率的咨询项目。最后,这些标准是用来提供一个估计的评级。这种方法减轻稀疏问题和提供的优势提供评级估计通过协同过滤技术可以重用。

然而,评级估计也非常侵入到用户的隐私,是由于很不精确推理过程的不确定性。作为一个例子,活跃的用户可以在电话中,解释了长咨询时间但一个项目的低利率。他也可以保存一个文档阅读后没有任何意见,或意外删除它。因此,隐式函数通常导致低劣的性能建模的准确性。

第二种方法
直接跳过评级评估步骤和应用相似措施一元的评级。Karypis [40),林登et al。41],米兰达和豪尔赫42采用一个基于项目的观点。他们计算相似性对项目,使用的改编版本cosine-based或条件概率的措施。如前所述,基于项目模型是已知准确;由于这些原因,一元模型提出了(40将在我们的实验评估框架。

最近,Redpath等人基于用户的CF扩展这些作品,在计算用户之间的相似性也适应余弦相似性度量或Jaccard系数(43]。这种方法假定项目数量两个用户coconsult越大,他们就越相似。然而,因为没有他们的偏好信息是已知的,这种假设可能并不总是真实的。这种方法也将评估在我们实验框架。

第三种方法
建议使用一个额外的信息用户咨询、订单的咨询项目。磋商的序列项开采(44,45]。然而,这种方法可能是很不精确的,因为它是极其困难和耗时的识别典型的健壮的使用模式下的不确定性。

在下一节中,我们关注社区检测方法的文献,来确定我们的一元评级框架之间的充分性和文学。

3所示。社区和当地社区检测

3.1。社区检测

呈现在前一节中,聚类过程需要的信息集群现有元素之间的链接,这些链接和关联的权重。这些元素和他们的链接也可以代表加权图的形式下,节点元素的聚集和边缘是他们的链接(例如,链接价值可能是元素)之间的相似性(46]。在我们的例子中,图的节点代表用户集群。

图聚类(最近获得了高度的关注47- - - - - -49),特别是由于众多领域数据可以在图表的形式表示。最著名的图聚类算法试图优化特定条件相关图表,如k-median最低金额,最小直径,等等,50]。其他算法是特定于应用程序的,可能利用已知特征的应用程序的数据或应用程序的域。在一般情况下,提出的方法进行聚类图无法轻易扩大大问题由于其高时间复杂度11]。

社区检测的概念与聚类图中的对象的概念。社区的概念可以从广义上讲:根据上下文,它可以是同义的模块,类,集群等等。社区检测图的目的是识别的对象,只有分析拓扑。结果社区图是一组节点之间的交互(相对)频繁。我们假设节点在一个社区可能共同属性或图中扮演类似的角色。例如,社区用户blogspace往往对应于用户的利益分享的话题。社区检测任务可以定义如下:“社区检测包括网络结构的分析与识别的目标社区,即组对象(表示为网络中的节点)更相互紧密连接(在网络上)比其余的对象”(51]。

社区检测方法已经应用于广泛的科学问题,例如,社交网络来识别组织的朋友(52,53),引用网络研究中心和科学学科的意义及其相互关系54,55),万维网来识别和管理Web页面主题(56),生物学和流行病学检测病毒的扩散57,58]。

在社交网络的框架,唐59]要求之间的实际差异图聚类和社区检测,并做出明确区分这两个过程的比较报告。聚类距离或相似矩阵而社区检测适用于离散数据和管理一个邻接矩阵。社区检测算法从而使用图形属性,利用概念如:k-clique, quasi-clique [60,node-betweenness edge-betweeness [52,61年),等等。因此,大多数的社区检测算法提出了在文献中已经为无向和未加权图设计的。然而,他们中的一些人已经提出了导演(56),加权(62年)或签名图(63年]。

算法用于检测社区可以分类与聚类相似的类别:fuzzy-community-detection [64年),层次社区检测(65年和分区66年]。例如,层次社区检测算法要么高度连接节点分组到越来越大的社区,或将图逐步划分为越来越小的断开连接的子图,确认为社区。层次社区检测算法的一个例子是Girvan和纽曼提出的,叫做GN算法(52]。这个算法使用边缘中间性测量,表达的重要性之后,整个图的边缘,当传输路径的最小长度。优势中间性价值高(几乎)所有最短路径连接节点的两个社区运行。GN算法将图像分为断开连接的子图,通过消除边缘中间性最高的得分。子图然后经历相同的过程,直到整个图分为一组孤立节点。

分区算法经常使用另一种信息:在一组节点链接的数量,和这组的节点之间的链接数剩下的图。社区是这样一组节点高度连接到对方,但连接节点在社区。因此,问题在于划分节点组,这样团体之间的边的数量非常少。组的数量必须事先定义的。分区算法的描述中可以找到(67年]。

让是一个图,一个邻接矩阵关联图中明确。让节点图的和的程度。让我们考虑的子图,哪个节点属于。的程度,,可以分成了两个元素,对: 在哪里连接节点的边的数量吗内其他节点和是连接到节点的数量在剩下的图。

Radicchi et al。68年)提出了两个社区的定义:强社区和弱社区。一个强大的社区定义如下:

是一个强大的社区,如果每个节点连接在社区内比与其他图。

弱势社区定义如下: 是一种弱社区如果度的总和吗比度的总和对其余的图。

我们可以注意到,一个强大的社区的定义比弱约束社区,作为连接措施适用于每个节点。此外,每一个强大的社区也是一个弱势社区。图1提出了图的一个例子。后者是分成两个社区(分别地。在红色和蓝色)在图2。

3.2。当地社区检测

在大规模图的背景下,可能出现两个问题:第一,完全图可能不知道;第二个图可能过于巨大的存储。例如,网络是如此之大,发展结构,没有图可以很容易地构造。此外,随着网络存储在一个分散的方式,建立这样一个图是很困难的。同样的原则,在Facebook等社交网络应用程序(http://www.facebook.com/),用户的数量非常巨大,网络不容易保存。

在推荐系统应用中,尤其是那些基于协同过滤,图表的物品(基于项目的方法)或图表的用户管理(基于用户的方法);相应的图形是巨大的和他们的存储是一项复杂的任务。具体来说,舞台上找到给定用户的最近邻居集(社区)图表的用户不容易处理的框架大图形。

在这种情况下,社区检测算法无法使用,因此,确定全局最优群落结构并不可行。相反,搜索可能有限决定的当地社区结构在附近一个查询节点。搜索的复杂性从而降低。当地社区检测算法来检测社区当图是巨大的,也就是说,不容易处理的。

相反的社区检测算法有一个全局视图的图,当地社区检测算法特征依赖当地的角度来看,允许检测社区当集中在一个特定的节点,而不是对整个图。

当地社区检测算法从一个查询节点(也称为种子节点)和迭代的节点添加到社区被发现,基于当地的图形视图。在每一步迭代的过程中,实际上节点添加到当地社区的节点高度连接的所有节点的社区,即节点充当桥梁与另一个社区(高中间状态值),并连接到整个社区。

当地社区检测算法的优势降低过程的复杂性,与标准的社区检测算法相比,只有一个子集的节点进行管理。当地社区检测算法主要用于在社交网络的框架(69年- - - - - -71年]。

相比与传统的图聚类算法和社区检测算法,执行分区的边缘,当地社区导致重叠社区发现算法。

提出了一些算法来检测当地社区。例如,田et al。72年)提出了一种算法用于未加权和加权图。

因此当地社区检测算法的特殊性的迭代和当地的观点。我们可以评论,在图聚类,一些迭代或/和当地算法也被提出。例如,歌曲和Kasabov [73年)提出了一个快速迭代一次通过的动态聚类算法。在[74年),当地的一个聚类算法提出了基于随机方法。

大多数的当地社区检测算法管理节点的三组(71年)如下:(我) 社区在建设中,这通常是初始化查询节点,(2) 不是在邻近的节点但分享一条边至少有一个元素,(3) 未知的节点,即这些不相邻。

在一些算法,集分为核心和边界。的核心没有边缘的节点,而边界集与一个节点至少有一个优势。

任何实现的当地社区检测算法requiresthe:(我)选择下一个节点的实例添加到社区,(2)终止判据(何时停止添加节点),(3)过滤(节点,如果有的话,必须从社区中删除)。

大多数的当地社区检测算法遵循算法提出的方案1。

最近,陈等人。12)提出了一个改进的古典当地社区检测算法应对问题的异常值往往是包含在社区。关于连接数量的信息被认为是形成的社区被平均的节点数量。的度量代表一个社区的“质量”。它与下面的两项计算。第一项平均内部节点度的措施和计算如下: 在哪里代表节点之间的边的数量和节点,节点的数量在吗。

第二项平均外部节点度的措施 在哪里是节点之间的连接的数量和外部节点。作为是的一个子集没有链接的节点,严格意义上相当于。

的指标的定义是

越高度规,社区就越好。在该算法中,由此产生的社区弱势群体,根据Radicchi等的定义。68年]。

该算法具有相同的方案中描述的算法1。(我)该算法首先,由一个节点、一个查询节点和。(2)在给定迭代步骤中,下一个节点的选择要插入的社区是由如下:最大化的节点被添加到。(3)终止判据是进化的价值的值时,算法停止减少。

该算法的优点是没有下限的连接必须是固定的。该算法自动确定约束,基于价值的。

4所示。社区检测的协同过滤算法

指出社区检测算法似乎适合我们的研究框架中,我们选择模型下的协同过滤的形式图:用户节点(顶点),边代表两个用户之间存在的联系。在协同过滤中使用用方法最初提出了Aggarwal等人在75年]。他们依靠相同的图结构和长的矮和可预测性的双重概念解决可伸缩性问题。探索图形可以快速识别邻居和用户提供宝贵的经验。此外,Ekstrand et al。76年)使用一个图结构和协同过滤推荐研究论文。在我们的例子中,这个图结构将高价值的发现社区一元评级上下文。

解释介绍,挑战我们的地址是不能收集评级,呈现传统CF方法无能为力。因此,唯一可用的信息,在这种情况下是一个给定的用户咨询项目(例如,一个Web页面)。虽然这比评级数据的信息量是很少的,一个巨大的数量的这些数据是可用的。

在这种情况下出现的一个主要问题是,选择最近的邻居或集群用户不是一项容易的任务,因为没有相似性值可以计算不够精确。正如之前所看到的,计算用户之间的相似性的一种方法依赖于使用余弦相似性度量,适应一元值或Jaccard系数(43]。

然而,计算相似性对所有用户是耗费时间。这需要时间,两个用户之间,是大量的物品。(http://www.eecs.berkeley.edu/ pliang cs294-spring08 /讲座/合作/ slides.pdf)此外,这些指标假设用户coconsult大量的项目,往往是相似的用户。然而,这些用户可能有相反的偏好和不可能实际上是相似的。

我们因此决定不计算这样一个相似度值,通过简化其计算阶段。我们认为,如果两个用户coconsulted超过(固定的)项目,这些用户很相似,这种相似性度量被固定到一个恒定值1。结果图未加权的边缘的显著特征。让我们注意到,这种相似性值的计算并不复杂。首先,它是一个计数。其次,在计算过程中,一旦达到计数,这个过程停止,创建了一个边缘。此外,输入数据不断发展,更新现有的边缘是边缘不需要进行了复查。

因此,我们面临的挑战是给定用户的选择导师,当没有信息用户之间的相似性是可用的。

第一个声明可以是太多的用户连接到活跃用户。此外,边是无关紧要的,系统不能选择最近的邻居。然而,可以使用一个额外的信息:图的结构。

我们因此提出利用当地社区检测算法来检测导师的活跃用户。这种算法主要利用图的结构(拓扑)通过设置的用户(社区)高度与用户在社区内,而不是与用户的社区。正如之前注意到的,一个社区内部的节点可能有共同的属性和/或图形中扮演类似的角色。因此,在协同过滤的框架,我们可以假定用户在社区也有类似的磋商行为或者类似的偏好。

更具体地说,我们的目标是在利用当地社区检测算法。当地社区检测是优先于一个社区检测算法有几个原因。(我)当地社区检测算法处理的可伸缩性问题社区检测算法。(2)一次查询节点选择,用户产生的社区可以被视为开始节点的导师吗。(3)导师是本地的和非对称的概念:一个导师是特定于一个给定的用户。例如一个用户可能是一个导师的,但可能不是一个导师的。当地社区检测算法处理这样的约束,而不是这样的社区检测算法。(iv)在执行每个可能的算法,由此产生的社区重叠。一些节点可以属于多个社区(甚至很多)。每个节点可以是多个用户的导师。(v)每个社区的大小不是固定的先验和社区的数量等于用户的数量。

我们建议使用一个适应和改进版本的当地社区检测算法提出的陈等人在12),因为它的设计有效地管理异常值,导致高质量的课程。该算法在12)将被称为在本文的其余部分,并将作为我们的基线。

4.1。选择唯一直接邻居

让我们提醒,我们的目标是检测每活动用户合适的导师。的算法的特点与元素,建立社区可能不是直接连接到用户的查询。结果可能不是集中在社区。作为一个结果,可能的边界限制他的社区,许多用户可能没有连接到社区呢,导致减少的推荐精度。

我们提出申请一些修改算法,以便妥善协同过滤的框架中使用。

在标准的推荐阶段CF,估计评级(或分数)的一个项目计算的加权平均邻居的评级在这个项目。权重是由活跃的用户之间的相似度值实例化和他的导师。因此如果活跃用户的社区是由用户没有连接相似(空值),这些用户将不会有用的建议阶段。这一观点的后果是:社区必须严格用户连接组成,这意味着算法(12]因此不是一个最佳的当地社区检测算法。

在LCD算法的迭代步骤,所有当前社区的邻居(候选节点)进行测试(公制评估)。节点最大化被包含在。我们建议放松这个约束通过减少候选节点的设置组用户连接。因此,属于社会的导师不仅是所有连接,但是也是高度与社区的用户,而不是与其他节点。

由此产生的社会将直接与导师的集合使用一个标准的资讯的方法。

这个改编版本的将被称为“以用户为中心的液晶”或UC-LCD。

4.2。过滤Subconnected节点

尽管这一事实被设计来应对意想不到的异常值纳入社区,一些局外人可能同样被包括在特定的配置图。作为一个例子,当关注的第一个迭代和算法,我们可以注意到最大化的节点是最小的节点。在最坏的情况下,此节点只能连接到一个节点的社区。然而,一旦这个subconnected节点包含在社区里,它仍然是在社区到结束的过程。subconnected尽管如此,正如这个节点,它将subconnected节点在社区内。因此,社区的质量降低。此外,这样一个节点也可以集成在进一步的迭代中,导致额外的集成节点可能subconnected社区。

改善的质量产生的社区,我们建议过滤subconnected节点的社区。在每个迭代步骤中,社会中的每个节点的连通性计算每个节点和连接价值低于预定义阈值从社区过滤掉。过滤过程提出了算法2。结果社区将仅由节点高度与社区的其他节点。新社区检测算法在算法3。

相反的过滤步骤提出了算法1在这个算法中,过滤在迭代。此外,节点可以过滤所有节点的社区,不仅最后一个节点插入到社区。的确,一个给定的节点可以连接到大多数节点在社区在一个迭代步骤中,这个连接可能会降低随着社区的增加。当然,连接阈值必须是固定的先验。

这个改进版本的,过滤掉subconnected节点将被称为。

4.3。推荐

一旦社区被计算,建议可以执行过程。在传统方法中,使用的导师,同样他们的相似之处与活跃用户。在这里,不活跃的用户之间的相似度信息和他的导师。因此,经典的评级估算步骤(1不能使用)。

我们建议适应这个等级的评估步骤,当没有使用相似性值是可用的。假设的数量最高的导师咨询了一个项目,的概率最高会喜欢这个项目。我们建议推荐方程计算条目的得分通过民主投票规则的导师之一。主要咨询项目在导师将这些建议。由此产生的方程提出了(10)

是一组用户的社区咨询项目。我们可以注意到,在传统聚类算法选择的邻居,导师的具体数量,将使用预先是未知的。这是社区的一个子集,但他们的数量将取决于项目的兴趣的评估分数。

5。实验

5.1。实验数据

本文中的实验旨在评估社区检测算法识别的充分性导师在CF。这些实验也旨在量化推荐项目的精确度损失没有可用评级时,也就是说,当经典方法不能使用。

我们选择两个语料库进行我们的实验艺术的状态,包含评级。在这些语料,我们用协商来代替评级。实验数据集我们选择知名MovieLens和杰斯特的数据集。

MovieLens数据集(http://movielens.org/)包含明确的评级,在1682部电影从943年匿名用户(项目)。中的每个评级变化范围从1(不喜欢)5(像)。每个用户都有额定至少20电影。数据稀疏数据集。

Jester数据集(http://goldberg.berkeley.edu/jester-data/)由180万个明确的评级,在100个笑话(物品)匿名用户。每个评级变化在连续从−10。每个用户都有额定至少36笑话。这个数据集的数据稀疏。

我们使用这两个数据集,以验证我们提出的算法,在不同的条件。MovieLens允许我们评估一个上下文的算法的鲁棒性高稀疏,有大量的物品,并在情况评级主要是非常积极的(平均评级值是3.53规模从1和5)。然而,这个数据集存在一个缺点:没有直接的评级之间的映射和可观察到的用户操作。一方面,用户可能认为,他们没有其他电影。另一方面,信用评级往往给直接在搜索结果页面和在产品详情页面不一定。此外,用户可能率电影实际上他们没有看过,或者他们看很久以前的事了。因此,我们选择了额外的数据集上验证算法。Netflix数据集比MovieLens患有同样的缺陷。在Jester相反,用户一定要读一个笑话能够率之前,他们随时能够阅读它们。此外,在MovieLens相反,Jester数据集不会面临任何稀疏问题,评级比MovieLens更均匀的分布和评级规模相当大。最后,有很多用户比Jester的物品,这是MovieLens互补,物品的数量几乎是用户数量的两倍。

常用的测试程序(参见“交叉验证子集生成脚本”,http://www.grouplens.org/system/files/README_10M100K.html),我们把这些语料分为五个部分,为了执行5倍交叉验证;培训由4部分和测试的最后一部分,重复5次,交替测试部分。MovieLens数据集,这部门提供的数据集;每个部分包含20%的评级。杰斯特的数据集,我们这个部门执行;我们随机将数据集分为5部分。类似于MovieLens数据集,每个部分包含20%的评级。

为语料,评级转换在磋商的形式;如果用户分配的值1是评价一个项目(任何评级价值),和0。因此,1意味着用户咨询项目,和0意味着他/她不是。

建立用户的图像,确定两个用户之间存在一条边,我们选择修复一个最小数量的coconsulted物品。MovieLens数据集,这个值被设置为20,所显示(77年]。Jester数据集,它被设置为36,因为它的最低数量是每个用户都有额定的笑话。因此,如果两个用户coconsulted超过20电影或36笑话,创建它们之间的链接,该链接的值等于1;还没有创建这两个用户之间的联系。

5.2。评价

在传统协同过滤,系统依赖于评级的用户分配给项目(在训练数据集)。这些评级都是用来估计未知参数的项目的用户还没有评价。这些缺失的评级比评级从测试数据集来评估这些估计的准确性。这个精度通常计算的形式下的意思是平均误差(美),计算估计评级之间的平均差和实际评级(14]。

Herlocker et al。9]证明这个指标实际上是不太准确的在考虑用户的评级,作为用户通常是想知道他是否会喜欢项目。因此,数篇论文提出用其他经典信息检索指标,如精度和召回(9,78年]。

在我们的实验中,当没有可用评级在训练和测试,没有评级可以估计。因此,美措施不能在这种情况下使用。

我们建议评价各种方法的性能提出了精度。系统的精确反映能力推荐用户会喜欢的物品。

在推荐过程中,系统计算出每一项的得分的活跃用户还没有咨询。这组物品然后根据这个分数排序,排在第一位的是推荐项目的集合。很明显,建议项的数量必须是固定的。

具体,精确定义是项目的比例,其中推荐的系统,用户实际上喜欢;这是定义如下:

精度值最高,最准确的系统。

然而,这种评估需要哪些物品信息实际上已经被用户喜欢的。在测试数据集,我们利用用户的评级实际上是已知的,因此,项目由用户也喜欢。MovieLens数据集,我们遵循的工作(79年):一个等级大于或等于4反映了用户喜欢一个项目。杰斯特的数据集,我们认为评级大于或等于6意味着用户喜欢这个项目。当然,这信息用户对项目的利益不会被用来计算建议,它将只用于评估方法的准确性。

在下面的实验中,我们固定数量的项目推荐的系统到10(前的大小列表),这是一个通常的大小推荐列表(80年,81年]。

5.3。描述数据集

我们在座的一些统计数据用于训练和评估方法。

正如前面说的,MovieLens数据集,用户的数量是943。每个用户在这个数据集额定至少20电影。5训练数据集,平均739个用户coconsulted / corated超过20项与至少一个其他用户。这些用户之间的连接的用户的平均数量是165 ();邻居的最大数量是612 ()和最小是1。

杰斯特集,用户的数量。每个用户在数据集额定至少36笑话。5训练数据集,用户coconsulted / covoted至少36笑话与至少一个其他用户。

之间的联系这些用户的平均数量是平均的(),最大数量()和最小是1。

5.4。基线模型与评级值

在本节中,我们感兴趣的建议当评级的准确性是可用的。我们关注的是基于用户的协同过滤。两种传统协同过滤的方法(见部分2.3精度值)将给我们参考。我们将测试方法不使用评级,目标是尽可能接近这些参考精度。

5.4.1之前。传统的协同过滤与资讯

我们第一次评估精度由选择直接选择导师的时候邻居(资讯)20.]。我们依靠皮尔逊相关系数(2)估计用户之间的相似度值,因为文献显示它工作得很好82年]。邻居的数量已经设置为50,全集;这个值代表了最佳精度之间的妥协和邻域大小根据我们所进行的实验,是按照所建议的(83年]。结果精度呈现在图3。我们可以先注意到大约是Jester的精确数据集低于MovieLens数据集上的一个。

5.4.2。古典与集群协同过滤

我们也评估精度选择导师时基于用户聚类技术(22]。k - means算法被使用和类的数量被设置为20。结果精度也呈现在图3。

比较这两种方法的精度测量时,我们可以注意到KNN-based协同过滤性能略优于clustering-based协同过滤;一个改进的实现在两个语料库,没有统计学意义。这个结论是按照艺术的状态。

以下部分是致力于评估精度只有协商的信息是可用的。

5.5。经典方法当评级不是可用的

在本节中,我们提出两种经典的方法当没有可用评级。

5.5.1。利用一系列的连接用户

当用户的评级并不可用,没有定量的联系很容易计算。因此,两个用户连接或没有;这个链接是无关紧要的。节中解释5。1连接两个用户,我们决定如果他们coconsulted超过一个固定数量的物品。作为一个结果,所有连接用户有相同的相似度值,邻居选择不容易。

一种构建活跃用户的组的导师是保持连接到他的所有用户。民主党投票推荐阶段在导师估计一个给定的得分项执行:更多的用户连接到活跃的用户咨询了一个项目,越活跃的用户应该喜欢这个项目。coconsulted项的最小数量一直设置为20 MovieLens Jester数据集的数据集和36。结果精度提出了两个数据集在第一栏的康涅狄格州。所有用户数据4和5。此外,平均大小,中间值和四分位产生的社区展示在表的第一行1和2。

MovieLens数据集,利用用户的协商,使用整个组连接用户的导师,这些导师和一个民主投票不会导致明显降低精度:相比开发用户的评级和资讯选择导师。相反,Jester数据集,实现大量减少:。

我们执行一个额外的实验研究如果Jester数据集上的大量减少是由于剥削的磋商(评级信息的损失),或者导师的选择。在这个实验中,一组导师选择利用评级,它比使用同一组5.5.1。民主投票然后被用于计算的建议。结果精度47.32,相当于减少相比精度获得使用评级为培训和测试。在Jester的数据集,我们可以得出这样的结论:评级值有很大影响精度的建议。这可能是解释为评定量表用于小丑,这不仅是连续的,但也比一个用于MovieLens数据集。

5.5.2。考虑到Coconsulted物品的数量

当没有评级可用,用户甚至可以因此计算之间的相似性。coconsulted物品的数量由两个用户可以使用为基础来计算这种相似性:一个可以假设用户有大量coconsulted项目往往是相似的。我们使用的相似性度量方法是在(42]。

活跃的用户选择的导师根据他们的相似性度量与活跃用户。用户的数量一直是被选择的实验为进出口贸易数量最高的精度值;它已经设置为50 450年MovieLens数据集和杰斯特的数据集。结果精度提出了在第二栏”# Co-cons。项目”的数据4和5。在全集,当导师的选择根据他们的coconsulted物品与活跃用户数量,精度下降相比,整个组连接用户的使用。这种减少是Jester特别大数据集:相比整个组连接用户的使用。这种减少只是MovieLens数据集。因此,导师的选择基于coconsulted物品的速度似乎并没有基于用户的方法是一个不错的选择。我们可以得出结论,用户往往咨询同样的商品往往是没有必要共享相同的观点。

让我们注意到,在以前的实验中,一个民主的投票中导师被用于推荐阶段。因此,电影推荐(最高的分数)可能会受欢迎的项目。来验证这个民主投票不下来推荐最受欢迎的项目,所有用户综合起来,提出评估建议的精度时最受欢迎的项目建议。并给出了相应的精度在第三栏“最流行。项目”的数据4和5。为语料,结果精度低于获得当利用整个组连接用户。因此,我们可以说,民主投票不下来推荐最受欢迎的项目。

5.6。基于项目的方法

如部分所示5。5利用coconsulted项的数量来计算用户之间的相似度降低了精度的基于用户的方法。然而,这些信息经常被用于基于项目的方法(40,41]。因此我们使用这个基于项目度量和评估相应的精度,所显示(40),向量规范化。第四条“基于项目”的人物4和5代表相应的精度。MovieLens数据集,结果精度略低于基于用户的方法之一;这种减少是关于。相反,Jester数据集的精度已经增加了。这些差异可以解释为这两个数据集的特点。MovieLens数据集有物品多用户,基于用户的方法会导致更准确的推荐。相反,基于项目的方法对Jester数据集执行更好的物品的数量小于用户的数量。

所达到的最高精度值相关的先前的实验是用一整套连接用户的导师。这些精度值将被视为评级时基线值并不可用。

5.7。社区检测算法

我们现在关注社区检测算法来检测导师的使用。

5.7.1。原来的算法(LCD)

虽然最初的算法(12)发现社区的缺点,包括用户不能直接连接到活跃的用户,我们都是一样的兴趣研究精度与由此产生的社区。与前面的实验中,一个民主投票的用户社区的计算来评估每一项的分数(10)和执行建议。让我们评论的用户产生的社区不是连接到活跃的用户不能用于推荐阶段。尽管可能大量的用户社区,用户的数量实际上有用的建议可能会因此降低。此外,随着液晶算法非以用户为中心的社区形式,活跃的用户可能会在他/她自己的社区的边界,这可能会导致较低的精度。

结果社区的特点提出了在第二行表1和2。正如所料,社区的大小大于基线(在考虑所有用户直接连接到活跃用户)。平均大小实际上是增加了为MovieLens数据集杰斯特的数据集。Jester数据集上的较小的增加是由于高百分比的用户连接到每个活跃用户。

并给出了相应的精度值在第五条“液晶”的人物4和5。低精度值:63.55 44.9 MovieLens数据集和杰斯特,对应于一个减少,分别和相比,整个组连接用户的使用。这种减少的原因可能是由于hereabove。较低的社区的大小的变化在杰斯特相比MovieLens的更小的减少可以解释精度。

学习导师的影响没有直接连接到活跃的用户,我们做了一个额外的实验。社区检测算法初始化的直接邻居(例如,最初是由活跃的用户吗和他连接用户)。然后算法执行发现额外的邻居。结果精度低于基线精度。我们可以得出结论,间接邻居在这种情况下不是有用的导师。

5.7.2。以用户为中心的算法UC-LCD

在本文中,我们提出适应液晶算法检测以用户为中心的社区,只有由用户连接活跃用户。推荐阶段是相同的比之前的实验中使用(10)。细节产生的社区提出了在第三行表1和2。这些社区社区中使用的部分的一个子集5.5.1。并给出了相应的精度在第六条“UC-LCD”数据4和5。

两全集,UC-LCD算法的精度达到超过液晶算法的精度,而达到一个类似的精度与基线(当使用一整套的邻居)。杰斯特集甚至略高。此外,这个类似的精度达到较小的导师。MovieLens数据集,平均社区比基线和1小小杰斯特的数据集。

5.7.3。过滤Subconnected用户社区(算法F-LCD)

节4.2,我们提出,当地社区检测算法提出的(12)插入的缺点在社区一些用户没有连接图。这些用户主要是插入在第一个迭代的社区。因此,这些用户社区的质量较低。因此,我们建议添加一个约束组成的社区,与社区内的每个元素的连接。在给定的步骤从社区中删除一个用户,如果他/她的连通性低于阈值固定的先验。这个阈值阈值称为连接。

我们进行了几个实验,连接阈值从0.0(没有删除,即)到1.0(如果不删除节点连接到社区的所有节点)。结果精度,根据这个阈值,提出了数字6和7。数据8和9礼物的大小社区的发展,取决于这个阈值。

除了这些实验中,我们评估的精度值加权边缘。与连接相关联的权重是用于部分5.5.2。的计算和措施从而适应考虑这些权重。不再使用链接的数量。取而代之的是边缘的值的总和。结果精度也提出了数字6和7。的大小相应的社区的发展,根据阈值,提出了数字8和9。

数据6和7显示,在两个语料库,利用加权的链接不会导致精度的显著增加,而不是过滤社区()。相反的,当使用F-LCD未加权的链接,精度的提高。MovieLens数据集的精度随着阈值的增加而增加,直到一个值。高于这个值,精度降低。最大的值是67.57,相当于增加了UC-LCD算法进行比较。这个小达到增加的导师低于。导师从基线相比(所有连接的用户),减少到达。

杰斯特集,与阈值,直到精度降低然后增加。最优阈值。相应的精确值是47.76,这对应于一个增加的与UC-LCD算法相比,而导师的数量减少。这种减少是当比较从基线的导师。

的精度自然仍然低于一个取得管理评级。然而,达到一个精确值非常接近这一目标。F-LCD和评级为依据的算法之间的差异不显著MovieLens数据集。

数据8和9表明社区的大小按照连接的价值降低门槛。未加权的图,这下降趋势尤为强烈MovieLens语料库:阈值是固定的时候出现,社区的大小除以2,和占52的平均用户。这个数字的大小类似于社区中使用的实验我们进行资讯的方法。相反,当使用加权图,减少更慢。例如,当连接阈值设置为,社区的大小仅仅是减少了,而这不仅仅减少了当使用未加权的图。这个小减少的原因是,当管理加权边缘,算法往往插入的社区用户提供高价值的链接上。用户提供高价值的链接上的用户往往咨询了很多物品,因此用户高度连接。

一个类似的结论可以得出Jester数据集。然而,当0.5是固定,减少社区的规模较低,这是由于高连接的节点。获得一个重要的降低阈值超过0.7时,这对应于上述阈值精度增加。

5.8。相似性评级为依据,以社区为基础的导师

在前面的小节中,实验表明,MovieLens数据集,F-LCD算法,平均48用户的社区规模,导致精度值不是很不同的获得时利用评级和资讯的方法。因此我们可以问在什么测量两组的社区,有类似的平均大小,是由相同的用户。

我们可以先说社区使用资讯时的最大尺寸是50岁,而这是80 F-LCD算法(表1)。进一步分析社区,我们建议评估用户属于社区的平均数量,为每个方法。作为社区的大小等于平均,社区用户的平均数量属于是等价的。然而,重新分区,用中位数和四分位数的数字可能会有所不同。表3礼物这个重新分配。

的分布属于社区的用户数量是不同的。当关注社区用户的最大数量属于,两种算法都有类似的值:约260,代表28%的社区。这意味着每个用户属于不到28%的社区。然而,当使用F-LCD算法时,一半的用户属于不到10社区,而他们属于小于35个社区。因此,F-LCD,用户倾向于要么属于几个社区,或许多社区,而重新分配与资讯似乎更均匀。

Jester数据集,一个类似的实验进行了。然而,我们建立了社区(有类似的平均大小的社区比F-LCD)的最佳精度。在社区的用户数量的分布也不同。具体地说,第一个四分位数和中位数是两次小F-LCD相比与资讯。

6。讨论

本文致力于识别的一个好方法发现导师rating-free协同过滤系统。

提出了在部分2.5,在缺乏评级,现有算法的文献通常认为,两个用户coconsulted两项越多,他们越有可能有类似的偏好(41,42]。以证实或否定这一假说,我们比较两种不同的导师选择的精度的措施策略。(1)我们的基线由导师在定义为整个组连接用户(称为“所有连接用户”数据4和5),(2)K最近的导师被选择的基础上他们coconsulted项的数量与活跃用户(见标签“# Co-consulted物品”数据4和5)。

第二个策略的结果精度并不增加相比,我们的基线。他们甚至降低精度和分别MovieLens和小丑。我们可以推断出的数量coconsultations两个用户之间不可靠地反映他们的偏好相似。这是反驳现有方法的最优性。

这个观察后,我们决定不管理任何用户之间相似性信息,并提出了几点意见和改进提高导师选择过程用图的方法。我们代表一组用户未加权图的形式下,用户联系,如果他们有coconsulted足够数量的物品。这个数字coconsulted项目首次用于预滤器的导师。随后,我们利用连通性在这个图,包括最相关的候选人的导师。我们的调查使我们提出的新模型灵感来自当地社区检测算法。精度达到了通过该模型类似于一个获得当所有连接用户考虑(我们的基线),在管理一组导师非常小(减少和是观察到的)。我们完善这个模型被丢弃,在社区检测的过程中,导师subconnected内设置其他导师(模型F-LCD)。结果精度的F-LCD相比,增加,同时减少组的导师在MovieLens和杰斯特。

提出了在部分2.5,基于项目的方法通常用于计算建议rating-free上下文(40]。因此,我们也比较了先前的精度指标(和F-LCD)一种基于项目的方法之一(见标签“基于项目”数据4和5)。结果表明,和F-LCD平均4.25%和6.2%,分别比基于项目的方法。

作为一个结论,如果coconsulted项的数量似乎并没有一个可靠的测量来检测导师,连通性(活跃的用户之间和他/她的导师,和导师的每一对之间)已被证明是更足够的这些实验的框架内。改善精度的同时要求获得少量的导师。

为什么我们选择MovieLens和杰斯特的数据集进行实验在于他们不同的特点。这些数据使我们能够可靠地验证模型的鲁棒性和相关性。MovieLens数据集稀疏级别(高),而杰斯特只有稀疏的水平。MovieLens数据集,每个用户都有至少咨询Jester数据集上的物品而至少每个用户都有咨询的物品。这意味着用户之间的连接性是非常不同的在MovieLens和小丑。此外,等级量表非常不同,使用的规模Jester MovieLens的四倍。其他值得注意的差异,我们发现利用用户的评级,两个语料库的精度值不同的大约20%。我们也做了一个实验的精度比较有和没有评级的建议。我们表明,Jester数据集,利用评级值的重要性和在很大程度上增加了精度高的价值,而只使用磋商。相反,MovieLens数据集,忽略了评级值影响较小。这种差异可能是由于不同的等级量表。

尽管这些差异的特点,精度的提高在rating-free感谢我们的模型已在这两个语料库。我们的rating-free模型F-LCD导致增加精度MovieLens,小丑,rating-free基线相比,而导师的数量减少了和,分别。甚至只有MovieLens,相应的精度低而获得的一个当管理评级。我们可以得出结论,连接是一个很好的信息,更好地反映用户之间相似性比coconsulted物品的数量。当然,最优连接阈值根据不同的图表。

7所示。结论

本文集中在导师选择问题的框架基于用户的协同过滤。导师选择的经典方法依赖于用户之间的相似度值。这种相似性计算的基础上,用户提供的评级,反映他们的偏好的物品。导师选择的两种主要的方法在文献中使用。第一种方法定义了导师的一个用户作为最高的用户相似度值。第二种方法集群用户由于其相似值,和用户互相视为导师在一个集群中。

在这项工作中,我们解决问题的导师选择在没有用户提供的评级是可用的。在这种情况下,无法精确地计算用户之间的相似度值;因此没有导师很容易做出选择。然而,可用的组用户协商。利用coconsulted物品的数量估计用户之间的相似度的方法。我们不打算利用这个信息来推断用户之间的相似性。我们提出的方法如果由两个阶段组成的。首先,我们认为两个用户coconsulted超过一个预定义的条目的数量可能相似的用户;他们的相似值固定为1。这种方法的优势使相似矩阵的设计更容易比经典方法。 Indeed, for each pair of users, the computation of the value of the similarity (0 or 1) comes down to a simple count that can be stopped when the minimum number of coconsulted items has been reached.

第二,我们代表用户的设置未加权图的形式下,我们利用当地社区检测算法,形成社区的用户,并推导出导师,在这个上下文。算法利用图像的结构和不注意边缘的价值。此外,他们有一个当地的图,它允许为每个用户设计一个社区,导致重叠社区。用于协同过滤的情况下,这些算法的优势直接邻居用户的古典方法的选择和分类。

我们适应先进的当地社区检测算法,发现社区适应协同过滤的特点:必须以用户为中心的社区,必须严格由直接连接的用户。用户属于给定用户的社区是他的导师。

然后,我们提出了进一步完善导师的设置过滤subconnected导师在社区,社区只有高度连接的用户组成。我们假设用户的更多的导师相连,导师的质量越高。

我们所知,利用图的结构已经很少在协同过滤的框架研究,尤其是执行导师检测。

这种方法已经被测试在两个数据集各种特征:评定量表,用户数量和物品,图的连通性,等等。实验结果表明,我们的当地社区检测算法F-LCD相比提高了精度基线模型,使用整个组(从连接用户来)。此外,使用的导师数量显著下降()。

因此,我们已经表明,当用户提供的评级并不可用,导师选择但是可以利用执行导师之间的连接性的地方相似的价值观,同时达到了良好的精度值。

作为一个未来的工作,我们计划研究时使用当地社区检测算法的评级是可用的。面临的挑战是如何准确地利用评级在这些算法的相似性。

在透视图中,我们也提出我们的模型扩展到安全问题。协同过滤是非常容易受到恶意攻击著称84年),因为它使用一个社区的意见相似的用户来预测当前用户的意见。因此,问题在于自动使得全球组用户的领导人之间的差异有助于建设相关建议,和攻击者的目的是降低服务或影响用户。分析用户之间的连接将有助于达到这一目标。

引用

1. ChoiceStream,“ChoiceStream个性化调查”,2006。视图:谷歌学术搜索
2. 美国Castagnos:琼斯,p .聚氨酯“眼球追踪产品推荐的用法,”第四届ACM会议程序推荐系统(RecSys 10),页29-36,巴塞罗那,西班牙,2010年。视图:出版商的网站|谷歌学术搜索
3. m . Pazzani和d . Billsus“自适应网络,”基于内容的推荐系统施普林格,柏林,德国,2007年。视图:谷歌学术搜索
4. r·d·伯克k·j·哈蒙德,公元前年轻,“知识导航复杂的信息空间,”13国家会议上人工智能(AAAI 96),1卷,页462 - 468,波特兰,矿石,美国,1996年8月。视图:谷歌学术搜索
5. d·戈德堡d·尼科尔斯,b .冲电气和d·特里”使用协同过滤挂毯编织一个信息,“ACM的通信,35卷,不。12日,第70 - 61页,1992年。视图:谷歌学术搜索
6. a . p . j . Wang•德•弗里斯和m . j . t . Reinders”统一的基于用户和基于项目的协同过滤方法的相似性融合,”学报》第29届国际市立图书馆年会在信息检索的研究与开发Seatttle,页501 - 508年,洗,美国,2006年8月。视图:谷歌学术搜索
7. Bruninghaus和k·d·阿什利”为索引法律案件,添加知识学习算法”学报》第七届国际会议上人工智能和法律1999年6月,页上行线,。视图:谷歌学术搜索
8. K.-Y。荣格,D.-H。公园,黄永发。李,“混合协同过滤和基于内容的过滤推荐系统改善,”《计算机科学国际会议可以' 04)卷,3036在计算机科学的课堂讲稿,第302 - 295页,2004年。视图:谷歌学术搜索
9. j·l·Herlocker j . a . Konstan l . g . Terveen和j·t·雷德尔“评估协同过滤推荐系统,”ACM交易信息系统,22卷,不。1,5-53,2004页。视图:出版商的网站|谷歌学术搜索
10. 答:布朗,哈马德,o .自助餐,a·波伊尔“对偏好关系在推荐系统中,”程序的偏好学习研讨会,欧洲机器学习和在数据库中知识发现的原理与实践(ECML-PKDD 10),2010年。视图:谷歌学术搜索
11. 走,“社区检测图”,物理的报告,卷486,不。3 - 5,75 - 174年,2009页。视图:谷歌学术搜索
12. r . j . Chen Zaane, r . Goebel“当地社区识别在社交网络”学报的发展社会网络分析和挖掘,第242 - 237页,2009年。视图:谷歌学术搜索
13. j . Breese d Heckerman, c . Kadie“实证分析预测的协同过滤算法,”《14日会议上的不确定性人工智能(可用98),1998年。视图:谷歌学术搜索
14. b·m·萨瓦尔g . Karypis j . Konstan和j . Reidl“基于项目的协同过滤推荐算法,”学报第十届国际会议上万维网(WWW的01),第295 - 285页,2001年。视图:谷歌学术搜索
15. l . Candillier f·迈耶,m .镶嵌细工,“比较先进的协同过滤系统”学报》第五届国际会议在机器学习和数据挖掘模式识别(MLDM ' 07)卷,4571在计算机科学的课堂讲稿莱比锡,页548 - 562年,德国,2007年7月。视图:谷歌学术搜索
16. 美国Castagnos和A·波伊尔,”一个客户机/服务器基于用户的协同过滤算法:模型和实现,”人工智能(17欧洲会议ECAI 06年),第621 - 617页,2006年。视图:谷歌学术搜索
17. Castagnos和a·波伊尔“个性化的社区在分布式推荐系统,”第29届欧洲会议IR研究学报》(ECIR ' 07)卷,4425在计算机科学的课堂讲稿,页343 - 355,罗马,意大利,2007年4月。视图:谷歌学术搜索
18. n . Lathia s冰雹,l·卡普拉“客户协同过滤,”国际信息处理联合会卷,263年,第134 - 119页,2008年。视图:出版商的网站|谷歌学术搜索
19. g·阿玛蒂,c . Carpineto g . Romano”在协同过滤选择一个有效的基于阈值的邻居,”学报欧洲会议信息检索(ECIR ' 07),第715 - 712页,2007年。视图:谷歌学术搜索
20. j . Herlocker j . Konstan a Borchers, j . Riedl“执行协同过滤的算法框架,”市立的诉讼,第237 - 230页,1999年。视图:谷歌学术搜索
21. m . Grcar b .命运,d . Mladenic“资讯与SVM在协同过滤框架中,”学报》第七届WEBKDD知识发现从Web研讨会(WEBKDD ' 05),2005年。视图:谷歌学术搜索
22. b . Mobasher r·伯克和j·j . Sandvig“基于模型的协同过滤作为一个防御姿态注入攻击,”21国家会议上的18创新应用人工智能和人工智能会议(AAAI 06年),卷2,页1388 - 1393,波士顿,质量,美国,2006年7月。视图:谷歌学术搜索
23. l·特朗红葡萄酒和A·迈耶“eElections模糊推荐系统,”学报第一国际会议上电子政务和信息系统角度(EGOVIS 10)卷,6267在计算机科学的课堂讲稿毕尔巴鄂,页62 - 76年,西班牙,August-September 2010。视图:出版商的网站|谷歌学术搜索
24. m·奥康纳和j . Herlocker”集群项目协同过滤,”《22日国际市立图书馆会议在信息检索的研究和开发(99年"),1999年。视图:谷歌学术搜索
25. Ungar l和d·福斯特“集群协同过滤的方法,”学报AAAI研讨会推荐系统,1998年。视图:谷歌学术搜索
26. a . m .马丁内斯,p . Mittrapiyanuruk和a . c .谷湖”graph-partitioning结合非参数聚类图像分割,“计算机视觉和图像理解,卷95,不。1,第85 - 72页,2004。视图:出版商的网站|谷歌学术搜索
27. p·s·布拉德利和美国m·法耶兹”精炼初始点$k$——集群”学报》第15届国际会议上机器学习(ICML ' 98)摩根考夫曼,页91 - 99年,1998年5月。视图:谷歌学术搜索
28. p . Perny和j . Zucker”协同过滤方法基于模糊偏好关系”学报4欧元工作组会议模糊集(EUROFUSE-SIC ' 99),1999年。视图:谷歌学术搜索
29. r·a·贾维斯和e·a·帕特里克”集群使用相似度度量基于共享附近的邻居,”IEEE计算机,22卷,不。11日,第1034 - 1025页,1973年。视图:谷歌学术搜索
30. l . Ertoz m·施泰因巴赫,诉Kumar“retrivial和聚类的信息,”寻找主题集合的文档:一个共享的最近邻方法吴w . h .熊,和美国Shekhar, Eds。,2002年。视图:谷歌学术搜索
31. s·r·Rastogi, k .垫片”治疗:一个有效的聚类算法对大型数据库”《ACM-SIGMOD国际会议管理数据(SIGMOD 98),没有。2、73 - 84年,1998页。视图:谷歌学术搜索
32. 陈j .阴x粉丝,y, j .任“高维共享最近邻聚类算法,”第二届国际会议上模糊系统和知识发现(FSKD ' 05)卷,3614在计算机科学的课堂讲稿Changsa,页494 - 502年,中国,2005年8月。视图:谷歌学术搜索
33. g .雪林,问:杨et al .,“可伸缩的协同过滤使用基于集群的平滑,”学报》第28届年度国际市立图书馆会议在信息检索的研究和开发(SIGIR 05),2005年。视图:谷歌学术搜索
34. n Srinivasa和s . Medasani“活跃的模糊聚类的协同过滤”学报IEEE国际会议上模糊系统2004年7月,页1697 - 1702。视图:谷歌学术搜索
35. j·b·谢弗,j . a . Konstan和j . Riedl“电子商务推荐应用,”数据挖掘和知识发现,5卷,不。1 - 2、115 - 153年,2001页。视图:谷歌学术搜索
36. X.-M。江,W.-G。歌,W.-G。冯,”插值优化协同过滤的个人和群体行为,”第八届亚太网络研讨会论文集(APWeb 06年)卷,3841在计算机科学的课堂讲稿哈尔滨,页568 - 578年,中国,2006年1月。视图:出版商的网站|谷歌学术搜索
37. d .飞船和j·金”,对推荐系统隐含的反馈,”《AAAI研讨会推荐系统,第83 - 81页,1998年。视图:谷歌学术搜索
38. s . CastagnosModelisation de遵守et apprentissage stochastique非监督de策略d有优势种盟盛德系临时工卷de矫揉造作的et d 'acces信息南希大学博士论文,2008年。
39. 美国Castagnos和a·波伊尔,”隐私问题建模时用户协同过滤推荐系统,”社会和人类的元素信息安全:新兴的趋势和对策,2008年。视图:谷歌学术搜索
40. g . Karypis“基于项目头n个推荐算法,评估”学报ACM 10日国际会议信息和知识管理(CIKM ' 01)2001年11月,页247 - 254。视图:谷歌学术搜索
41. g·林登、b·史密斯和j .纽约“Amazon.com建议:item-to-item协作过滤,”IEEE网络计算,7卷,不。1,第80 - 76页,2003。视图:出版商的网站|谷歌学术搜索
42. c·米兰达和a . m .豪尔赫,“增量为二进制评级,协同过滤”学报IEEE /每各月ACM国际会议网络智能(WI 08年),页389 - 392年,悉尼,澳大利亚,2008年12月。视图:出版商的网站|谷歌学术搜索
43. j . Redpath d·h·玻璃,s . McClean l·陈,“协同过滤推荐系统的目的和用户评级的意义,”美国第32欧洲信息检索会议(ECIR 10)卷,5993在计算机科学的课堂讲稿米尔顿凯恩斯,页394 - 406年,英国,2010年3月。视图:出版商的网站|谷歌学术搜索
44. b . Mobasher h·戴·t·罗和m .中川”提高协同过滤的有效性匿名web使用数据”诉讼IJCAI 2001智能技术研讨会上展出的Web个性化(ITWP 01),2001年。视图:谷歌学术搜索
45. g . Bonnin a .布朗,a·波伊尔,“网络智能和智能代理,小伙子。Skipping-Based合作建议从统计语言模型的启发,“Zeeshan-ul-Hassan Usmani, 2010年3月。视图:谷歌学术搜索
46. g . w .片状、r . Tarjan和k . Tsioutsiouliklis“图聚类和最低砍树,”互联网上数学,1卷,不。4、385 - 408年,2004页。视图:谷歌学术搜索
47. d .周、j·黄和b . Scholkopf”学习标记和未标记数据在一个有向图,”学报》第二十二届国际会议上机器学习(ICML ' 05),第1043 - 1036页,2005年。视图:谷歌学术搜索
48. k·津田和w·s .高贵,“学习内核从生物网络最大化熵,”生物信息学,20卷,不。1,第333 - 326页,2004。视图:出版商的网站|谷歌学术搜索
49. j . Callut k . Franoisse m . Saerens, p .杜邦“Semi-supervised分类图使用有界随机漫步,”17年机器学习研讨会论文集的比利时和荷兰(BENELEARN ' 08),第68 - 67页,2008年。视图:谷歌学术搜索
50. s e·谢弗“图聚类”,计算机科学评论,1卷,不。1、27 - 64年,2007页。视图:出版商的网站|谷歌学术搜索
51. 帕帕多普洛斯,y Kompatsiaris, a . Vakali”通过网络社区检测标签利用集体智慧,”学报》研讨会上集体知识获取和表示(CKCaR ' 09),2009年。视图:谷歌学术搜索
52. m . Girvan m·e·j·纽曼,“在社会和生物群落结构的网络,”美国国家科学院院刊》上的美利坚合众国,卷99,不。12日,第7826 - 7821页,2002年。视图:出版商的网站|谷歌学术搜索
53. n . Mishra r·施赖伯。斯坦顿,r . e . Tarjan“集群社会网络”纺织学报》天文学Web(帕' 07)课堂讲稿,在计算机科学中,56 - 67,2007页。视图:谷歌学术搜索
54. p . Wanjantuk和j·a·基恩,“找到相关文档引用图,通过社区”《IEEE通信和信息技术国际研讨会(ISCIT ' 04),1卷,第450 - 445页,2004年10月日本札幌。视图:谷歌学术搜索
55. m . Rosvall和c t . Bergstrom“随机漫步的地图揭示复杂网络社区结构,”美国国家科学院院刊》上的美利坚合众国,卷105,不。4、1118 - 1123年,2008页。视图:出版商的网站|谷歌学术搜索
56. g . w .片、美国劳伦斯和c·l·贾尔斯“有效识别网络社区,”学报第六届ACM SIGKDD国际会议上知识发现和数据挖掘(KDD ' 01),页150 - 160,波士顿,质量,美国,2000年8月。视图:谷歌学术搜索
57. d . y . Wang Chakrabarti, c . Wang和c·凯利斯“流行病蔓延在现实网络:一个特征值的观点,”学报》22日国际研讨会上可靠的分布式系统(阶跃恢复二极管' 03)25至34岁这个,页,佛罗伦萨,意大利,2003年10月。视图:谷歌学术搜索
58. f . Balem y气,c .凯利斯j . Klein-Seetharaman bar - joseph z,“蛋白质复杂的识别由当地监管图聚类,”生物信息学,24卷,不。13日,250 - 268年,2008页。视图:出版商的网站|谷歌学术搜索
59. l .唐”社交网络社区检测”,http://www.public.asu.edu/ huanliu / dmml_presentation / 2008 /。视图:谷歌学术搜索
60. r·阿尔巴”,用一个社会经济的集团的定义,“《数学社会学,第126 - 112页,1973年。视图:谷歌学术搜索
61. l·弗里曼,“一套措施基于中间性的中心,“人与人之间40卷,35-41,1977页。视图:谷歌学术搜索
62. h·伊诺,m .奖赏,a .中村“分区社区网络图的拓扑结构,”学报》第14届国际会议在万维网上,第669 - 661页,2005年。视图:谷歌学术搜索
63. 杨,w·k·张,j .刘”从签署了社交网络社区挖掘。”IEEE工程知识和数据,19卷,不。10日,1333 - 1348年,2007页。视图:出版商的网站|谷歌学术搜索
64. 格雷戈里,“一个算法来发现重叠社区结构网络,”学报》第11届欧洲的原理和实践的会议在数据库知识发现(PKDD ' 07)卷,4702在计算机科学的课堂讲稿,页91 - 102,华沙,波兰,2007年9月。视图:谷歌学术搜索
65. j·斯科特,社会网络分析:一个手册,鼠尾草,伦敦,英国,第二版,2000年版。
66. d . Chakrabarti”,该:parameter-free图分区和异常值检测,”程序数据库中知识发现的原理和实践的会议(PKDD ' 04)卷,3202在计算机科学的课堂讲稿,第124 - 112页,2004年。视图:谷歌学术搜索
67. a .烦恼,”图划分算法应用科学计算,“技术。代表,诺福克,弗吉尼亚州,美国,1997年。视图:谷歌学术搜索
68. f . Radicchi c可以见到效果,f . Cecconi住诉洛雷托,和d .巴黎”的定义和识别社区网络,美国国家科学院院刊》上的美利坚合众国,卷101,不。9日,第2663 - 2658页,2004年。视图:出版商的网站|谷歌学术搜索
69. a . Clauset m .牛曼和c·摩尔,“发现社区结构在非常大的网络,”物理评论,72卷,2005年。视图:谷歌学术搜索
70. f·罗,j . z . Wang和e . Promislow“探索当地社区结构在大型网络中,”学报IEEE /每各月ACM国际会议网络智能(WI 06年)2006年12月,页233 - 239。视图:出版商的网站|谷歌学术搜索
71. l .黑雁“增量检测当地社区结构,”《国际会议上的进步社会网络分析和挖掘,第87 - 80页,2010年。视图:谷歌学术搜索
72. j .田d·陈,傅y”一个新的本地检测算法在网络社区,”学报第一国际研讨会教育技术和计算机科学(ETCS ' 09),卷2,页721 - 724,武汉,中国,2009年3月。视图:出版商的网站|谷歌学术搜索
73. 问:歌曲和n . Kasabov“认知科学的基础,”ECM-A小说在线,进化聚类方法和它的应用程序埃德•波斯纳,麻省理工学院,631 - 682年,2001页。视图:谷歌学术搜索
74. j·g·布斯,g·卡塞拉,j . p . Hobert“集群使用目标函数和随机搜索,”英国皇家统计学会杂志》上,卷70,不。1,第139 - 119页,2008。视图:出版商的网站|谷歌学术搜索
75. c . c . Aggarwal k .肺吴,j·l·沃尔夫和p . s . Yu”长的矮孵化鸡蛋:一个新用的协同过滤方法,”第五届ACM SIGKDD学报》国际会议上知识发现和数据挖掘212年,页201 - ACM出版社,1999年。视图:谷歌学术搜索
76. m·d·Ekstrand Kannan p . j . a Stemper, j·t·巴特勒,j . a . Konstan和j·t·雷德尔“阅读列表,自动构建研究”第四届ACM会议程序推荐系统(RecSys 10)西班牙巴塞罗那,页159 - 166,,2010年9月。视图:出版商的网站|谷歌学术搜索
77. p . Viappiani b Faltings, p . Pu,“个性化搜索用example-critiquing建议,”人工智能研究杂志》上27卷,第503 - 465页,2006年。视图:谷歌学术搜索
78. 诉Schickel-Zuber和b . Faltings”,使用层次聚类学习theontologies在推荐系统中,使用”13 ACM SIGKDD学报》国际会议上知识发现和数据挖掘(KDD ' 07)圣何塞,页599 - 608年,加州,美国,2007年8月。视图:出版商的网站|谷歌学术搜索
79. l . Baltrunas f·里奇,“动态项权重,选择协同过滤,”Web 2.0采矿车间,ECML-PKDD施普林格,2007年。视图:谷歌学术搜索
80. c·齐格勒对分散的推荐系统博士论文,Albert-Ludwigs-Universitt弗莱堡,2005年。
81. a·布朗、g . Bonnin和a·波伊尔”历史相关的推荐系统基于局部匹配,”17学报》国际会议用户建模、适应、和个性化(UMAP ' 09)卷,5535在计算机科学的课堂讲稿特兰托,页343 - 348年,意大利,2009年6月。视图:出版商的网站|谷歌学术搜索
82. Shardanand和p·梅斯,“社会信息过滤:算法自动化“口碑营销”,“会议的程序在计算系统人为因素(CHI 95)1卷,第217 - 210页,1995年5月。视图:谷歌学术搜索
83. j . Herlocker j . a . Konstan和j·雷德尔”设计选择的实证分析于社区的协同过滤算法,”信息检索,5卷,不。4、287 - 310年,2002页。视图:谷歌学术搜索
84. r·伯克和b . Mobasher“信任和偏见在多智能推荐系统,”学报》研讨会上多智能信息检索和推荐系统,结合19世纪国际联合会议上人工智能(IJCAI 05展出),爱丁堡,苏格兰,2005年。视图:谷歌学术搜索

版权

版权©2011 Armelle布朗等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。