现在的位置: 首页 > 综合 > 正文

协同过滤算法的问题及解决方案

2013年08月15日 ⁄ 综合 ⁄ 共 5862字 ⁄ 字号 评论关闭
1 协同过滤在应用中存在的问题

    尽管协同过滤在电子商务推荐系统中的应用获得了较大的成功,但随着站点结构、内容复杂度和用户人数的不断增加,基于协同过滤的推荐系统的发展面临着两个主要挑战:

    1) 提高协同过滤算法的可扩展性

    协同过滤算法能够容易地为千万记用户提供量化的推荐,但是对于电子商务网站,往往需要给成千上万的用户提供推荐,这就一方面需要提高响应速度,能够为用户实时地进行推荐;另一方面还应考虑到存储空间的要求,尽量减少推荐系统运行对系统的负担。

   2) 提高对个性化推荐的质量

    用户需要得到值得信任的推荐来帮助他找到喜欢的产品。假如用户相信推荐购买了商品,而后发现并不喜欢,则会降低用户对推荐结果的信任度,同时将不愿再次使用该推荐系统。

    从一定意义上讲,推荐系统面临的这两个挑战之间存在着矛盾,系统要提高算法的可扩展性及响应时间,在质量上必然会有所损失。因此,如何协调好这两方面的要求,使推荐系统不仅有用而且实用,是实现协同过滤技术需要考虑的重要因素。

    为了能够更好地改进协同过滤技术,适应推荐系统发展的需要,首先要分析协同过滤在实现过程中存在的问题,从而进行有针对性的改进。通过对协同过滤技术以及推荐系统的研究,我们发现协同过滤技术的实现中存在的问题主要有以下几点。

   1.1 稀疏性问题

    协同过滤技术的实现首先需要使用用户—项评价矩阵对用户信息进行表示,尽管这在理论上很简单,但实际上,许多电子商务推荐系统要对大量的数据信息进行处理,而在这些系统中一般用户购买商品的总量占网站总商品量的1%左右,因此造成了评价矩阵(用户-项矩阵)非常稀疏。在这种数据量大而且又稀疏的情况下,一方面难以找到最近邻居用户集,另一方面进行相似性计算的耗费也会很大。

    同时,由于数据非常稀疏,在形成目标用户的最近邻居用户集时,往住会造成信息的丢失,从而导致推荐效果的降低。例如,邻居用户关系传递性的丢失。用户A与用户B相关程度很高,用户B与用户C相关程度也很高,但由于用户A与用户C很少对共同的产品进行评价,而认为两者关联程度较低,由于数据的稀疏性,丢失了用户A与用户C之间潜在的关联。

    1.2 冷启动问题

    冷启动问题又称第一评价问题(first- rater),或新物品问题(New-item),从一定角度可以看成是稀疏问题的极端情况。因为传统的协同过滤推荐是基于相似用户/物品计算来得到目标用户的推荐,在一个新的项目首次出现的时候,因为没有用户对它作过评价,因此单纯的协同过滤无法对其进行预测评分和推荐。而且,由于新项目出现早期,用户评价较少,推荐的准确性也比较差[25]。相似的,推荐系统对于新用户的推荐效果也很差。冷启动问题的极端的案例是:当一个协同过滤推荐系统刚开始运行的时候,每个用户在每个项目上都面临冷启动问题。

   1.3 可扩展性问题

    在协同过滤推荐算法中,全局数值算法能及时利用最新的信息为用户产生相对准确的用户兴趣度预测或进行推荐,但是面对日益增多的用户,数据量的急剧增加,算法的扩展性问题(即适应系统规模不断扩大的问题)成为制约推荐系统实施的重要因素。虽然与基于模型的算法相比,全局数值算法节约了为建立模型而花费的训练时间,但是用于识别“最近邻居”算法的计算量随着用户和项的增加而大大增加,对于上百万的数目,通常的算法会遇到严重的扩展性瓶颈问题。该问题解决不好,直接影响着基于协同过滤技术的推荐系统实时向用户提供推荐问题的解决,而推荐系统的实时性越好,精确度越高,该系统才会被用户所接受。

基于模型的算法虽然可以在一定程度上解决算法的可扩展性问题,但是该类算法往往比较适于用户的兴趣爱好比较稳定的情况,因为它要考虑用户模型的学习过程以及模型的更新过程,对于最新信息的利用比全局数值算法要差些。

    分析以上协同过滤在推荐系统实现中面临的两个问题,它们的共同点是均考虑到了最近邻居的形成问题(包括用户信息获得的充分性、计算耗费等)。但是应该看到协同过滤在推荐系统的实现中,要获得最近邻居用户,必须通过一定的计算获得用户之间的相似度,然后确定最佳的邻居个数,形成邻居用户集。而在这一过程中,如果对全部数据集进行相似性计算,虽然直接,但是运算量和时间花费都极大,无法适应真实的商务系统。如果通过对训练集数据(整个数据集的某一子集)进行实验获得,虽然不必对整个数据集进行计算,但是必须通过将多次实验结果统计出来才可能得到,这无疑也增加了推荐结果获得的代价和误差。并且如果考虑到数据集的动态变化,这一形成最近邻居用户集技术的实际应用价值越来越小。因此,考虑使用更为有效的最近邻居用户形成办法,对于协同过滤的应用非常必要。

    2 解决协同过滤中稀疏性问题的方法

    2.1 基于内容的协作过滤方法

    基于内容的推荐(Content-based recommendation)是基于内容抽取项目特征属性的推荐技术,是信息过滤技术的延续与发展。

    在基于内容的推荐系统中,项目或对象是通过相关的特征属性来定义的。如,像新闻组过滤系统NewsWeeder这样的文本推荐系统用它们的文本词汇作为特征。这个方法的根本思想是:一个用户将更会喜欢那些和他已经购买的项目相似的那些项目。在这类方法中,历史信息用来反映项目之间的关系,如一个项目的购买经常导致另一个项目或一组项目的购买。因此,该方法是利用用户-项目矩阵分析每个项目的相似性,在这个基础上计算被推荐的前N个项目。

    基于内容的推荐系统是基于用户评价对象的特征,学习用户的兴趣。Schafer, Konstan和Riedl称这种方法为项目-项目相关关系法。由于这种方法不需要去识别那些邻近的用户,所以推荐算法的速度快得多。

    基于内容的推荐对项目的属性特点的历史信息进行学习,其优势在于提高了推荐的可测量性,并且能够对推荐结果作出比较好的解释。基于内容的推荐能发现用户感兴趣的项目,但是不能发现新的内容。

    基于内容的推荐存在以下不足之处:

    1) 信息挖掘不全面。一般的,基于内容的推荐只能对一定内容进行浅显的分析。在一些领域,项目属性并不能体现一些隐含的特点,如,电影、音乐或饭店等。即使是文本文件,推荐也只能获取内容中的有限方面的信息,但是其中还有许多其他方面影响用户的经历。如,根据网页内容的推荐,就完全忽视了美学的品质、所有多媒体的信息(包括嵌入在图片中的文字)和诸如加载时间等网络因素。

    2) 推荐的内容有限。不仅是基于内容的推荐,很多推荐技术都存在所谓“超越专门化”的问题。当系统仅仅根据用户资料或项目描述来进行推荐的时候,用户被限制在只能得到与以往熟悉的内容相类似的项目。这样不利于挖掘用户潜在的兴趣。

3) 缺乏用户反馈。这是推荐系统的普遍性问题。对项目进行评价对于用户来说是一项繁重的任务,所以评价越少越好。在基于内容的推荐中,对项目属性的描述是影响未来推荐效果的唯一因素,这就意味着减少评价数量的同时,推荐性能也降低了。

    2.2 基于项的协同过滤算法

    基于项的(Item-based)协同过滤推荐根据用户对相似项的评分预测该用户对目标项的评分,它基于这样一个假设:如果大部分用户对一些项的评分比较相似,则当前用户对这些项的评分也比较相似。基于项的协同过滤推荐系统使用统计技术找到目标项的若干最近邻居,由于当前用户对最近邻居的评分与对目标项的评分比较类似,所以可以根据当前用户对最近邻居的评分预测当前用户对目标项的评分,然后选择预测评分最高的前若干项作为推荐结果反馈给用户[22]。

表2用户评分数据

星球大战 泰坦尼克 指环王 廊桥遗梦
甲 4        2        4         4
乙 3       5        3        3
丙 2       2        3        2
丁 5        1        5         ?

    Item-based协同过滤推荐算法的核心就是通过用户对目标项最近邻居的评分产生最后的推荐结果,用户对目标项的评分通过用户对目标项最近邻居评分的加权平均值逼近。例如,在表2所示的用户评分数据中,Item-based协同过滤推荐算法需要预测用户丁对项“廊桥遗梦”的评分。通过数据分析发现,用户群体对“廊桥遗梦”的评分与对“星球大战”的评分非常相似,“星球大战”是“廊桥遗梦”的最佳邻居,因此丁对‘星球大战’的评分对预测值的影响最大。其次,用户群体对“指环王”的评分与用户对“泰坦尼克”的评分也比较相似,因此丁对“泰坦尼克”的评分对预测值的影响也比较大。而“廊桥遗梦”不是“泰坦尼克”的好邻居,因为用户群体对它们的评分存在冲突,所以丁对“廊桥遗梦”的评分对预测值的影响相对小一些。在实际的预测过程中,只搜索目标项相似性最高的前若干个邻居,然后根掘相似性大小预测用户对目标项的评分。

    与User-based协同过滤推荐算法不同,Item-based协同过滤推荐算法通过计算项之间的相似性,选择目标项的最近邻屠集合,根据当前用户对最近邻居的评分预测用户目标项的评分,然后选择预测评分最高的前若干件商品作为推荐结果反馈给用户。Item-based协同过滤推荐算法可以分为如下两个阶段:

   1) 最近邻查询:搜索目标项的最近邻居。

   2) 推荐产生:根据用户对目标项最近邻居的评分信息预测用户对目标项的评分,产生top-N商品推荐。

2.3 基于内容推荐和协同推荐的组合推荐算法

    尽管传统的协同过滤推荐的效果相当显著,但是冷开始和稀疏问题仍是影响其性能的重要问题。其关键问题在于,协同过滤的特点是要求有很多个用户对项目进行评价后,用户才互相帮助并协同选择项目。然而对于一个新项目,由于以往没有任何人对它作过评价,它就无法参与到推荐和评价中,因此推荐系统就失去了作用。评价的人越多,系统就越能发挥出其最大作用。所以对一个新项目,需要研究并解决在初始情况下如何让它参与推荐和评价,使整个推荐系统朝良性循环的方向发展。

    由于解决问题的角度和方法不同,基于内容的推荐能有效的解决协同过滤的冷开始和稀疏问题。可以用一个简单的例子描绘其作用:假设一个用户已对来自网站ESPN.com的NBA网页作出过爱好的评价,而另一用户对来自网站CNNSI.com的NBA网页也作出过爱好的评价,如果只用协同过滤的话,将不能发现这两个用户的相似之处。然而,基于内容的分析是基于用户评价对象(项目)的特征属性,学习用户的兴趣,因此能发现这两个项目是相似的。那么,根据相似项目的属性以及用户对相似项目的评分,可以初步预测用户对新项目的评分,这样就得到了对冷开始问题的一个解决途径,同时,稀疏性问题也可以得到有效的解决。

    基于上述分析,有研究者提出了一种采用基于内容的推荐改进协同过滤的组合推荐方法,利用基于内容推荐对相似项目的研究弥补协同过滤推荐在新项目推荐方面的不足,从而有效的解决冷开始和稀疏问题。该组合推荐算法首先利用基于内容的推荐分析项目的特征属性、找出新项目的相似项目,然后通过用户对相似项目的评价来预测对新项目的评分,最后使用传统的协同过滤推荐在相似项目的范围内计算邻居用户并给出最终的预测评分,使新项目参与到推荐中。

   2.4 基于聚类的协同过滤推荐算法

     随着电子商务系统的进一步扩大,协同过滤推荐算法的实时性要求遇到了巨大挑战。在一个用户和商品均数以万计的系统中,同时为数以万计的用户提供实时的推荐服务越来越困难[4]。

    GroupLens是第一个用于处理大规模数据集的自动化系统过滤推荐系统,用于向系统用户实时提供新闻推荐服务。在GroupLens推荐系统中,首先必须对新闻进行手工分类,将不同新闻划分到不同的新闻组中。由于每个用户在特定时刻均处于一个特定的新闻组内,因此最近邻查询也限制在该新闻组内部,向该用户提供的推荐结果也限制在该新闻组内部。这种方式可以有效减小搜索空间,从而有效解决协同过滤推荐算法面临的实时性挑战。

    这种解决方案主要存在如下不足。首先,根据内容信息对项进行手工分类存在很大的主观因素,因此也是不精确的。其次,在许多大型的电子商务系统中,项数量及其巨大,对项进行手工分类非常耗时,因此是不现实的。最后,这种推荐方法只能推荐一定范围内的商品信息,从而失去了向用户提供其它有价值推荐的机会。

    为了解决推荐系统中存在的上述问题,一个有效的方法就是根据内容信息对项进行自动分类。这种方案也存在一定弊端,其主要问题就是必须输入所有项的内容信息,在很多场合,项的内容信息无法获取,例如图形、图像、视频等信息。

基于聚类的(Cluster-based)协同过滤推荐算法提出了另外一种解决方案。将整个用户空间根据用户的购买习惯和评分特点划分为若干个不同的聚类,从而使得聚类内部用户对项的评分尽可能相似,而不同聚类间用户对商品的评分尽可能不同。根据每个聚类中用户对商品的评分信息生成一个虚拟用户,虚拟用户代表了该聚类中用户对商品的典型评分,将所有虚拟用户对商品的评分作为新的搜索空间,查询当前用户在虚拟用户空间中的最近邻居,产生对应的椎荐结果。相对于原始的用户空间而言,虚拟的用户空间要小得多,因此最近邻查询的效率也高得多,可以有效提高推荐算法的实时响应速度。

    聚类分析在数据挖掘领域进行了深入研究。K-means聚类算法是最简单同时也是非常有效的聚类算法。采用K-means聚类算法对整个用户空间进行聚类的主要步骤如下:

    1) 随机选择k个用户作为种子节点,将k个用户对项的评分数据作为初始的聚类中心。
    2) 对剩余的用户集合,计算每条用户与k个聚类中心的相似性,将每个用户分配到相似性最高的聚类中。
    3) 对新生成的聚类,计算聚类中所有用户对项的平均评分,生成新的聚类中。
    4) 重复以上2到3步,直到聚类不再发主改变为止。

    生成聚类之后,Cluster-based协同过滤推荐算法可以分为如下两步:

    1) 虚拟用户集主成:根据不同的聚类生成对应的聚类中心,聚类中心与聚类中其他用户的距离之和最小,代表该聚类中用户对商品的典型评分。将所有的聚类中心作为虚拟的用户集合。

    2) 推荐产生:在虚拟的用户集合上使用各种相似牲度量方法搜索当前用户的若干最近邻居,然后根据最近邻居对商品的评分信息产生对应的推荐结果。最近邻搜索和推荐产生的方法跟协同过滤推荐算法类似,在此不再赘述。

抱歉!评论已关闭.