协同算法范文

2024-05-30

协同算法范文（精选9篇）

协同算法第1篇

关键词：推荐引擎,协同过滤算法,数据稀疏,奇异值分解

0引言

协同过滤(CollaborativeFiltering,CF)是目前推荐引擎中应用最广泛的个性化推荐技术之一。其通过研究用户历史行为,分析用户兴趣(或项目属性),为用户建立模型,依据活跃用户对项目的评价,来寻找与活跃用户兴趣相同的用户组,然后用该用户组中评价比较高的一组项目序列为活跃用户作出相关推荐[1,2]。

现有协同过滤算法分为基于用户的协同过滤、基于项目的协同过滤和基于模型的协同过滤[3]。基于用户的协同过滤是向用户推荐与其兴趣相似的其他用户喜欢的物品,依据的是用户之间的相似度;基于项目的协同过滤是向用户推荐与其先前喜欢的项目相似的项目,依据的是项目之间的相似度;基于模型的协同过滤则依据已有的部分成熟算法建立模型,然后为用户进行推荐,常见的有聚类、关联规则、贝叶斯网络等。

1协同过滤中的数据稀疏性问题及解决方法

协同过滤算法推荐需利用用户对项目资源的评价信息矩阵。如果用户对项目资源的评价不够多,则无法产生精确的推荐,导致用户体验不佳,这就是协同过滤算法中存在的数据稀疏性问题。信息矩阵的数据稀疏性本质上是由高维数据引起的,是协同过滤算法的经典问题。现有解决数据稀疏性方法主要有聚类分析[4,5]、奇异值分解等。

2改进的 BAS(BayesAfterSVD)算法

协同过滤技术的关键是找到最优邻居集合,要解决计算信息矩阵稀疏性问题,可以从两个方面着手:1寻找一个更为精确的相似性度量方法,在同等稀疏程度情况下,得到更好的邻居集合;2对计算信息矩阵进行降维处理,并填补计算信息矩阵中的缺失项,使其成为一个稠密的计算信息矩阵,为协同过滤后的计算提供更多的数据源,从而提高推荐质量。

2.1主要技术

(1)贝叶斯(Bayes)度量。

F(i)是对项目i感兴趣的用户数目。α为惩罚因子,取值0~1,在实际应用中以物品的热度来进行度量。对热销用品,与其有关联的物品越多,则α越接近1。需要注意的是,当α=0时,则变成了传统的贝叶斯公式;当α=1时,则所有物品都影响物品间相似度。

(2)奇异值分解(SVD)。计算矩阵R代表用户的评分行为,其中R[u][i]表示用户u对项目i的评分。首先将计算矩阵R分解为两个低维相乘矩阵。

其中,P∈Rf×m和Q∈Rf×n是两个降维后的矩阵。

用户u对项目i的评价预测值R’(u,i)=r’ui,可通过下式计算:

其中,puf=P(u,f),qif=Q(i,f)。矩阵分解思想为利用最小化RMSE思想,直接通过训练集中所观察的数据对P、Q矩阵进行学习。在利用RMSE作为评测指标时,加入防止过拟合项λ(‖pu‖2+ ‖qi‖2),其中λ是正则化参数,从而得到损失函数。

2.2算法过程

首先采用SVD方法预测未打分的评分预测值,得到一个稠密的计算矩阵;然后,利用填补后的计算矩阵,配合加入惩罚因子的贝叶斯公式,采用获取最优邻居集合的方法,求取实际未评分的项目的预测值,该方法称为BAS(BayesAfterSVD)算法。BAS算法流程如下:1获取用户项目信息矩阵,将计算矩阵R规范为Rn;2利用SVD对信息矩阵进行降维处理,同时进行缺失项填充;3选中一个用户,利用修正后的贝叶斯公式求得活跃用户与其他用户的相似度;4依照与活跃用户的相似性度量大小进行排序,选择前N个用户作为活跃用户的最优邻居;5求出每个活跃用户i对未评分项目j的预测值。

3算法实现与实验分析

3.1评价指标

(1)均方根误差(RMSE )和平均绝对误差(MAE )。评分预测的准确度一般通过均方根误差(RMSE )和平均绝对误差(MAE )计算。对于测试集中的一个用户u和项目i,令rui是用户u对项目i的实际评分,而r'ui是推荐引擎计算出的预测评分,则:

MAE采用绝对值计算预测误差,定义为:

(2)TopN推荐。TopN推荐的预测准确率通常通过准确率(precision)/召回率(recall)来进行度量。

令R(u)表示用户u推荐N个物品,而T(u)是用户在测试集上的行为列表,则推荐结果的召回率为:

推荐结果的准确率为:

(3)覆盖率(Coverage)。该指标描述一个推荐引擎对项目长尾的发觉能力。最直观的描述为推荐引擎能够推荐出来的项目占总项目集合的比例。假设系统的用户集合为U ,推荐引擎向每个用户推荐一个长度为N的项目列表R(u)。则推荐引擎的覆盖率可定义为:

为更细致地描述推荐引擎挖掘长尾的能力,需要统计推荐列表中不用项目出现次数的分布。可以参考信息论中的信息熵:

其中,p(i)是项目i的流行度除以所有项目流行度之和。

3.2数据集说明

为评估不同算法的推荐效果,使用以下公开数据集:

(1)MovieLens数据集。该数据集 (http://www.grouplens.org/node/73)包含3个不同版本,本次实验选用中等大小的数据集。该数据集包含约100万条评分,涵盖了6000多个用户对4000多部电影的评分情况,用户可以对电影评5个不同等级的分数(1-5分),并且每位用户至少曾为20部电影作过评价。

(2)Jester数据集。该数据集是加州大学伯克利分校发布的一个关于笑话的数据集(http://www.ieor.berkeley.edu/~goldberg/jester-data/),包含约410万记录,收集了73421个用户对100个笑话的评分(评分范围从10~10)。该数据集分为3个部分,本次实验采用了第三部分,该部分为24938个用户的评分,且打分项目数目在15~35之间。

定义用户计算矩阵中未评分条目所占的百分比作为稀疏密度来度量采用数据集的稀疏特性,比如MovieLens数据集的稀疏密度约为:

3.3实验分析

本次实验中采用MovieLens数据集和Jester数据集进行试验。

3.3.1数据稀疏性对推荐结果的影响

大多使用推荐引擎的网站,尤其是一些大型的电子商务网站,比如淘宝、京东商城等,用户真正接触的物品信息数量以及进行评价的信息常常达不到物品信息总量的1%,这就导致了计算信息矩阵的极端稀疏,容易导致推荐质量令用户不满意,或者用户体验不佳。

通过实验来比较常规协同过滤(采用余弦相关性和加入惩罚因子的贝叶斯公式)在MovieLens与Jester两个数据集中不同稀疏密度下的推荐效果。选取MovieLens数据集和Jester数据集中各两组数据集作对比,结果分别如表1、表2所示。其中:MI15为MovieLens数据集中前1500个用户的评分;MII15为MovieLens数据集中前1500个用户中评分数目小于30的评分;JI15为Jester数据集中前1500个用户的评分;JII15为Jester数据集中前1500个用户中评分数目小于30的评分。对每个数据集根据实验需要将其划分为训练集和测试集,且二者比例约为4∶1。

从表1、表2可以看出,当数据比较稀疏 (即当选定MII15和JII15两个数据集)时,SVD与常规的协同过滤方法(不论是采用加入惩罚因子的贝叶斯方法还是余弦相似度)推荐结果类似,唯一不同的是随着数据集稀疏密度的变化,相较与其它两种算法,SVD算法预测结果变化幅度比较小,即其对数据稀疏的敏感程度要优于常规的协同过滤方法。随着抽取子数据集系数密度越来越大,推荐引擎的推荐效果越好,但当数据子集比较稠密时,可以看出常规的协同过滤方法(特别是采用加入惩罚因子的贝叶斯方法)比SVD算法要好。实验证明数据集的稀疏性是影响推荐引擎效果的重要因素。

3.3.2针对选定数据集,选定适当的k值

对于MovieLens数据集,从用户评分数据中选择评分数目小于40的用户,得到数据集包括约200多个用户和1200多部电影,然后将数据集随机划分为训练集与测试集,训练集和测试集的比例为4∶1。

对于Jester数据集,直接选取用户评分项目从15~35的用户,得到数据集包括约24900个用户的评分,将数据集随机分成训练集与测试集,二者之间的比例约为4∶1。

在基于SVD分解的模型中,矩阵最终维数k是关键参数,如果k过大,则失去了SVD分解的意义,如果k过小,则不能很好反映原有矩阵的信息特性,故首先需要确定参数k,然后再采用本文提出的BAS算法。

从图1中可以看出,当k =25时,平均绝对误差(MAE)最小,所以对于该数据集,维数k =25是最佳的,在采用BAS算法实验中,针对MovieLens数据集,选取k=25。从图2中可以看出,针对Jester数据集,当k =8时,平均绝对误差(MAE)最小,所以对于Jester数据集,维数k =8是最佳的,在采用BAS算法的实验中,针对Jester数据集,选取k=8。

3.3.3在选定的数据集上进行不同算法的推荐

利用实验中所用的数据集确定k值,图3和图4分别为选定的MovieLens数据集和Jester数据集上不同算法的预测结果。

从图3可以看出,BAS算法比朴素贝叶斯及SVD算法得到的推荐效果都要好,但当邻居数目超过20时,BAS方法的结果和朴素贝叶斯方法(即常规协同过滤方法)的结果趋于相交,所以当邻居数目超过一定数量时,BAS方法的优越性不明显,考虑到现实中用户只对为其推荐的前几条信息感兴趣,所以20个邻居在选定数据集下是可以接受的。同时以上结果也可以从另一个方面反映MAE可以比较好地评价推荐引擎结果推荐的准确性。

协同过滤所需的计算信息矩阵经过奇异值分解处理后,原始的计算信息矩阵维度减小了,使得原本高维模型的计算转换成了指定维度下的矩阵运算,有效缩减了原有问题的规模。实验表明,奇异值分解应用于协同过滤时,尤其是应用于数据稀疏度比较高的信息矩阵计算时,能有效提高推荐引擎的推荐精度,虽然矩阵的奇异值分解计算量比较大,但可以离线进行,从而弥补运算量大带来的损耗。从实验结果看出,BAS方法的推荐质量与其它常见的方法相比有一定的提高。

4结语

协同算法第2篇

一种多无人机协同侦察航路规划算法仿真

无人机协同侦察航路规划的算法复杂,数据量大,不易收敛.针对这些特点,采用了基于分散规划、集中调整思想的层次分解策略来确定参考航路.首先改进了粒子群优化算法,并运用该算法确定无人机的协同任务初始航路;然后给出了一种新的.航路光顺优化指标,对初始航路平滑修正.仿真实验结果表明,该方法能够解决无人机的协同侦察航路规划问题,是一种效率较高的规划算法.

作者：杨遵雷虎民 YANG Zun LEI Hu-min 作者单位：空军工程大学导弹学院,陕西三原,713800刊名：系统仿真学报 ISTIC PKU英文刊名：JOURNAL OF SYSTEM SIMULATION年，卷(期)：19(2)分类号：V279 TP391.9关键词：无人机侦察航路规划粒子群优化算法层次分解序列二次规划

协同算法第3篇

摘要：随着信息技术和互联网的发展，在信息过载的时代，用户面对海量的信息，难以正确选择。协同过滤推荐是个性化推荐中比较成熟的算法，但其稀疏性、冷启动、可扩展性问题仍然存在，尤其是不能应用于分布式推荐。在Hadoop平台上，Mahout实现了分布式基于项目的协同过滤推荐算法，该算法能够有效解决传统算法的海量数据处理的效率问题和可扩展性问题。实验结果表明，Mahout上基于项目的协同过滤推荐算法具有较好的计算高效性和可扩展性。

关键词：分布式协同过滤；Mahout；推荐系统

中图分类号：TP391 文献标识码：A

1引言

互联网和电子商务系统的兴起与发展，将人们带入了网络经济发展时代，同时网络中的信息量也在爆炸式地增长。网络信息虽然给人们带来了更多的选择，但数量庞大及自身质量差异，越来越呈现一种信息过载的趋势，使得如何从这些海量信息中识别出真正有价值的信息变得越来越困难。然而，推荐系统的出现改变了这一状况，尤其是个性化推荐服务技术的发展，成为解决信息过载问题最有效的工具，它能够收集和分析用户的信息，主动地推荐用户可能感兴趣的信息。

个性化推荐中的协同过滤推荐是比较成功的一种，它的概念是由Goldberg、Nicols、Oki以及Terry在1992年首次提出的，主要思想是，利用已有用户群过去的行为或意见预测当前用户最可能喜欢哪些东西或对哪些东西感兴趣。不到两年，Grouplens系统展示了协同过滤方法既能跨网计算又能自动完成，该系统是基于用户评分的自动化协同过滤推荐系统，用于推荐电影和新闻。麻省理工学院的Ringo系统针对音乐唱片和艺术家进行推荐。虽然传统的协同过滤推荐算法在信息过滤方面呈现出了极大的优势，但随着信息量的增加，算法在不同领域的应用中出现了很多的问题，包括稀疏性问题、冷启动问题、可扩展性问题。

为了解决这些问题，文献基于动态规划思想，根据用户以及产品的相似性，自适应地选择预测目标的近邻对象作为推荐群，同时计算把握率较高的信任子群，提出了一种不确定近邻的协同过滤推荐算法，来对预测结果进行平衡的推荐，有效缓解了用户评分数据稀疏的情况。文献在基于弱关系的微博类社交网络中，提出两阶段聚类的推荐算法GCCR，将图摘要方法和基于内容相似度的算法相结合，实现基于用户兴趣的主题推荐，有效缓解了矩阵稀疏性和冷启动问题。文献采用传播的思想，提出了一种改进的基于内存的协同过滤推荐算法SPCF，该算法通过相似度传播，寻找到更多，更可靠的邻居，从用户和项目两方面信息考虑对用户进行推荐，缓解了数据稀疏性问题。

传统的协同过滤推荐算法虽然从一定程度上减少了矩阵稀疏和冷启动问题，但随着数据规模的不断扩大，可扩展性方面仍然表现的比较差，无法适应海量数据的处理，尤其是无法应用于分布式平台。为此，国内外研究者进行了一系列的研究，这些研究大多是针对Hadoop平台和MapReduce并行编程模型，提出相关的分布式协同过滤算法。文献提出了MapReduce范式可扩展的基于相似性的邻居算法，该算法中，针对分割数据设计出运行在并行处理平台上的基本比较对，并采用降低采用率的interaction-cut技术，处理“超级用户”的计算开销，有效地解决了用户或项目大规模增长的情况下扩展性和产生推荐的速度问题。文献针对基于User-based的协同过滤算法的伸缩性问题，实现了基于Hadoop平台的User-based协同过滤算法，从而实现了算法的线性伸缩。文献提出了Hadoop平台上扩展的Item-based协同过滤推荐算法，将单机上基于项目的协同过滤算法的三个最密集的计算分割为四个MapReduce阶段，有效地解决了文献提出的算法的扩展性和效率问题，但是MapReduce阶段的项目相似度计算要求两个项目在同一节点机器上，并且要求用户数量远大于项目数量，对于项目不断增长的情况下，会增加算法的计算量。

本文所要介绍的就是Mahout在Hadoop框架下基于项目的协同过滤推荐算法的实现，该算法是基于MapReduce并行编程模型，不仅有效地解决了在海量数据下算法处理的效率问题，而且解决了随着大量用户和项目的增加产生的可扩展性问题。

2协同过滤推荐算法

协同过滤推荐算法主要包括基于用户和项目的推荐，其中基于项目的协同过滤推荐算法是目前业界应用最多的算法，所以本节内容以基于项目的协同过滤推荐算法为介绍对象，它主要分析用户的行为记录来计算项目之问的相似度。推荐系统首先建立基于项目的数据模型，然后针对目标项目计算项目与项目之间的相似性，得到目标项目的若干最近邻，最后根据最近邻来预测用户对项目的评分，产生对应的推荐列表。

2.1相似性度量方法

相似性度量方法是计算用户或项目问的相似性计算，本节内容是以项目之问的相似的研究为例，即基于项目的协同过滤算法。基于项目i和项目j通常有3种相似性度量方法：标准的余弦相似性（式（1））、修正的余弦相似性（式（2））、相关相似性（式（3））。其中，R_u，i表示用户u对项目i的评分，R_i和R_j分别表示项目i和项目j上所有用户的平均评分，U_ij为项目i和项目j共同评分的用户集合，U_i和U_j分别为项目i和项目j评分的用户集合。

2.2产生推荐

基于项目i的k个最近邻居，采用基于项目均值的加权平均值Pu，i，来预测用户u对其未评分或浏览项目的评分。

其中，kNN_i表示项目i的k最近邻居集合，R_i，R_i分别表示项目i和j上所有用户打分的平均值。

3Mahout中分布式协同过滤推荐算法实现

3.1Hadoop和Mahout开源框架

Hadoop是Apache软件基金会旗下的一个开源分布式计算平台。Hadoop以分布式文件系统HDFS和MapReduce为核心，为用户提供了系统底层细节透明的分布式基础架构。HDFS的高容错性、高伸缩性等优点允许用户将Hadoop部署在低廉的硬件上，形成分布式系统；MapReduce分布式编程模型允许用户在不了解分布式系统底层细节的情况下开发并行应用程序。所以用户可以利用Hadoop轻松地组织计算机资源，从而搭建自己的分布式计算平台，并且可以充分利用集群的计算和存储能力，完成海量数据的处理。

Mahout是2008年作为Apache Lucene的子项目出现的，到2010年4月成为了Apache的顶级开源项目。Apache Mahout的分布式计算的主要目标是建立可伸缩性的机器学习算法，通过Map Reduce模式运行在Hadoop平台上。目前Apache Mahout项目包含聚类、分类、协同过滤推荐、频繁子项挖掘和频繁模式挖掘五个部分。

本文意在结合Hadoop平台和Mahout开源框架，对Mahout中分布式基于项目的协同过滤推荐算法进行分析并通过实验实现其算法。

3.2算法实现

在Mahout中，实现的是基于项目的分布式协同过滤算法，该算法一共包含6个过程，这个6个过程使用了7个Map Reduce的Job任务来进行数据处理。数据流程图如图1所示：

1）用户矩阵

用户矩阵的求解过程，就是针对图1的用户一项目评分矩阵的一个数据抽取过程，把同一个用户评价过的所有项目进行整合，针对每个用户，形成用户分向量itemid：pref，含义为项目ID：用户评价，然后形成每个用户的用户向量，最终形成用户矩阵。Mahout中使用了一个Job任务来进行形成用户向量的数据处理，输出key/value对的格式是，其中的Long Writable和Vector Writable分别对应的是itemid和用户向量的格式。

2）项目矩阵

项目矩阵的求解过程和用户矩阵的求解过程很相似，但两者抽取的规则不一样，针对每个项目，形成项目分向量userid：pref。同样在Mahout中也使用了一个Job任务来进行形成项目矩阵的数据处理，输出的key/value对的格式是，其中的IntWritable和VectorWritable分别对应的是userid和项目向量的格式。

3）项目矩阵平方和

在Mahout中使用了一个Job任务来对4.2中的项目矩阵求解平方和，针对每个项目的项目向量，项目矩阵平方和的求解方法为求解项目向量的模的平方。

4）项目相似度矩阵

项目相似度矩阵的求解在Mahout中是由两个Job任务共同处理完成的，第一个Job任务是计算项目与项目之问的相似度，假设有N个项目，首先计算项目1和项目2的相似度，以此类推，最后计算项目1与项目N的相似度，但要注意的是，在计算项目2与项目1的相似度时，因为在计算项目1与其它项目相似度时已经计算过与项目2的相似度了，所以项目2只需计算除项目1以外的与其它项目的相似度。第二个Job任务是续接，所谓续接就是把没有计算相似度的项目加入到其它项目中去，例如在第一个Job任务中，计算项目2与其它项目相似度时是没有计算与项目1的相似度，所以必须将项目1与项目2的相似度续接到项目2中，最后输出形成项目相似度矩阵表。项目相似度的计算公式如下：

其中，i₁，i₂分别代表项目1和项目2，U代表两个项目共同有过平方的用户集，P_ui₁，代表用户u对项目1的评分，P_ui₂代表用户u对项目2的评分，Sim代表的是两个项目的相似度，squssub>i₁是对应的项目1的平方和。

5）用户一项目相似度矩阵

用户一项目相似度矩阵是结合用户矩阵和项目相似度矩阵，为每一个用户生成用户一项目向量，Mahout使用了一个Job任务来对这些矩阵进行处理，输出key/value对的格式为，IntWritable和VectorAndPrefsWritable分别是用户和用户一项目相似度矩阵对应的格式。

6）用户推荐矩阵

用户推荐矩阵是由Mahout中的一个Job任务根据用户一项目相似度矩阵计算产生的，推荐矩阵中为每一个用户产生一个推荐向量，推荐向量由多个推荐项目及其预测评分组成，计算公式如下：

其中，simi_Im是用户U₁针对项目Im的相似度矩阵，M为用户评价过的项目集，pref_Im是用户U₁针对项目Im的评分，公式（7）只是求用户U₁的推荐向量，然而，可以用公式（7）为所有用户求得推荐矩阵。

4实验结果及其分析

4.1实验配置和数据集

经分析，在小数据集条件下通过伪分布式模式或小集群的Hadoop分布式模式调试的工程，可以胜任完全分布式模式下的大数据集分布式计算的任务。本实验在一台台式机上建立三台虚拟机，并通过这三台虚拟机建立3个节点的Hadoop集群，其中包括1个Master节点，2个Slave节点，台式机具体配置信息如下：Intel（R）Pentium（R）CPUG2030@3.00GHz，6GRAM，80G硬盘。虚拟机操作系统为Ubuntu12.04，Hadoop版本为1.1.2，Mahout版本为Mahout-0.8。在我们的实验中，将每个Slave节点的map和reduce任务支持的最大数都设置为4，由于map和reduce任务不是同时执行，所以整个集群可以支持8个map和8个reduce任务，实验中将这些map和reduce任务视为计算节点数。

本实验采用MovieLens数据集（http：//grou-plens.org/datasets/movielens）。MovieLens是一个基于Web的研究型推荐系统，用于接收用户对电影的评分并提供相应的电影推荐列表。我们选取的数据集包含6040个用户对3952部电影上的1000209条评分记录，其中，每个用户至少对20部电影进行了评分。另外，引入了稀疏等级的概念，其定义为用户评分数据矩阵中未评分条目所占的百分比，实验数据集的稀疏等级为1-1000209/（6040*3952）-0.9581。

4.2性能评估

首先，在相同的数据集上针对不同等级的用户数量，比较单机和分布式的基于项目协同过滤推荐算法的推荐时间，并评估算法效率；然后利用分布式的推荐算法的加速比，随着计算节点数的增加，评估固定数据规模下算法运行的性能变化情况，并验证算法的可扩展性。

1）推荐算法时间比较

本实验的MovieLens数据有1000209条用户评分记录，为了方便观察单机与分布式推荐时问的比较结果，将数据分为7个等级，如表1所示，数据等级分别选取500、1000、2000、3000、4000、5000、6000、6040个用户。实验就是分别对这7个等级的用户的评分记录数量进行处理，为所有用户推荐至多3个项目，然后比较不同条件下的推荐时问，如图2所示：

其中，横坐标表示为用户数量，纵坐标表示为对应不同用户数量推荐项目的推荐时间，以分钟为单位。从图2中可以看出，针对单机和两节点的推荐时间比较接近，这是因为在两节点的Hadoop集群环境下，只有一个主节点和一个从节点，节点之间除了必要的数据处理任务外，还要调度集群资源，以便合理的安排任务。三节点的集群整体的推荐时间要优于前两者，推荐项目时能节省很多的时间，可以得知，集群规模越大，计算的时间越少，对于单机需要几个小时才能处理的数据，如果集群规模有上百台，那么只需要几分钟就能够将数据处理完，这说明集群更适合处理海量的数据，并且效率更高。

2）加速比

加速比性能分析的计算公式如（8）所示。其中T₁代表的是单个计算节点并行执行算法的总时间，T_p代表的是包含p个计算节点并行执行算法的总时间。如果算法是可扩展的，那么当数据规模固定时，加速比与计算节点的增加将呈现线性关系。本实验将数据集按评分记录数分成三个等级，分别为10000、100000、1000209，实验结果如图3所示：

可以看出，三个等级数据规模的加速比与计算节点数的增加近似呈线性关系，而且当数据规模增加时，加速比更大。由此可以得出，Mahout上分布式的基于项目的协同过滤算法在处理更大规模的数据时算法的加速比表现的更好，有效地解决了算法的可扩展性问题。

5总结

基于协同过滤的推荐算法研究第4篇

互联网的新时代到来的标志是WEB2.0技术的应用, 网络用户不再局限于通过互联网获取信息知识, 而是主动参与创造信息资源, 通过互联网WEB2.0这样的平台在网络上互相交流和沟通。在互联网时代基于WEB2.0技术的博客、论坛、BBS社交等发展和应用迅速, 这些应用最大的特点就是用户作为中心, 是数据的生产者和消费者。随着互联网技术的快速发展, 网络上的信息大量增长, 数据增长迅猛。据美国互联网数据中心最新的统计表明, 近些年来互联网数据的增长量占整个互联网数据总量的9/10, 而且每年互联网数据以49%的速度递增, 大量的互联网数据对数据存储是一个很大的挑战, 信息过载的问题受到世界各国互联网专家的高度重视, 互联网用户不能准确而及时地从大量的互联网数据中获取自己需要的数据的问题。对信息过载问题有效的解决办法就是应用对信息检索和过滤技术, 常用的搜索引擎作为信息检索的技术已经取得了很大的成效, 搜索引擎是对关键字进行检索, 查询出用户自己需要的信息, 但是某些情况下用户不能准确地获取自己的关键词信息, 这样就不能对信息进行查询, 这也是搜索引擎存在的弊端。信息过滤技术可以解决搜索引擎不能查询的问题, 信息过滤技术是对海量的数据进行挖掘, 然后对信息数据对比分析, 把用户感兴趣的数据推荐给用户。在信息过滤技术中最具有代表性的就是推荐系统, 英文简称RS, 它是基于WEB的个性化信息服务方式, 推荐系统采用的重要方式是协同过滤算法, 协同过滤算法具有极大的学术价值和商业价值, 被广泛地应用。协同过滤英文简称CF, 协同过滤算法是推荐系统发展的产物, 最近几年电子商务的快速发展使推荐系统协同过滤算法得到了广泛地应用, 为用户提供个性化的购买服务的推荐应用, 增加用户对电子商务网站的信任度。

推荐系统是一个软件系统, 把用户感兴趣的项目推荐给用户, 项目指为用户推荐的商品或者物品, 推荐系统是一种智能的信息过滤的应用, 帮助用户在海量的项目中找出自己感兴趣的项目, 推荐出来的项目显示方式是以列表排列显示给用户的, 在排列的列表的项目符号是推荐系统根据用户对项目感兴趣的程度自动排列的。根据对用户感兴趣程度的判断, 推荐系统通过日常对用户相关信息的收集和项目特征进行匹配推荐, 也可以收集用户的历史标注信息来判断用户对项目感兴趣的程度。随着电子商务的发展, 在网上商店的商品数量越来越多, 用户找到自己需要的商品难度太大, 推荐系统可以很好地解决这个问题。在解决信息过载的问题中推荐系统得到了广泛地应用, 用户在购买商品时的购买记录被记录下来, 丰富了推荐系统的数据库, 使推荐系统为用户推荐信息更精确。

2 基于协同过滤的推荐算法研究的现状

在电子商务系统中, 用户和项目的数量非常巨大, 推荐系统的精确度要求非常高, 协同过滤算法面临的主要问题是数据稀疏性和扩展性问题等。数据稀疏性问题是协同过滤算法中最重要的问题, 在商业推荐系统中, 用户和项目的数量很大, 用户在很少的项目上有评分记录, 这样造成了评分矩阵的稀疏性。通常评分矩阵的密度要小于1%, 导致对项目相识度的计算不准确, 对推荐精度造成很大的影响。在推荐系统中用户和项目增长速度快, 新用户刚注册进系统中, 由于没有历史标注的评分记录, 对应的标注信息不能匹配, 造成推荐系统不能为用户推荐项目。在协同过滤算法中数据稀疏性问题的解决可以采用降维法, 降维法主要是降低推荐算法对数据稀疏的敏感度, 把高维降到低维。解决数据稀疏性问题还可以采用融合内容的混合协同过滤, 这种方法主要引进外界的信息源, 增加相识度计算的准确, 降低数据稀疏问题。

协同过滤算法按照实现方法的不同, 分为基于内存方法和基于模型的方法2种, 基于内存协同过滤算法是协同过滤算法早期一直到现在都采用的主要方法, 基于内存的协同过滤算法是对矩阵的信息进行评价, 找出相似的项目, 然后按照项目的相似度推荐给用户。数据挖掘技术的应用为协同过滤算法应用注入了新的能量。基于内存的协同过滤算法, 假设每个用户都有一个相似兴趣的用户组或者每个项目都有一个相似用户特征的项目群, 基于内存的协同过滤算法通过找到用户的兴趣群主是按照一定的相似度评价标准, 然后推荐给用户, 那么推荐的标准是按照用户在项目上的评分为标准的。基于内存的协同过滤算法分为基于内存的TOP-N推荐算法、基于缺省标注填充的协同办公算法和基于逆用户频率的协同过滤算法等。基于内存的协同过滤算法简单实用, 基于内存的协同过滤算法把项目推荐给用户的工作都是在线完成的, 而且所有的算法的计算都是在内存中进行的, 基于内存的协同过滤算法的原理是找出用户的相邻集合, 主要是按照相似度的评价标准进行, 并按照相邻集合标准的信息来预测。由于算法的计算是在内存中并且是在线完成的, 所以主要问题就是扩展性的问题。基于模型的协同过滤算法以评价矩阵为训练数据模型, 通过训练的模型来识别出相识的项目智能推荐给用户。

3 基于协同过滤的推荐算法研究

3.1 融合社交网络信息的协同过滤算法

基于协同过滤的推荐算法研究中, 本文对融合社交网络信息的协同过滤算法进行了研究, 在研究中, 本文的评价标准采用平均精度作为性能推荐的依据, 用户项目的评价矩阵信息和用户社交网络信息都在数据集中。本文提出了算法的有效性, 把社交网络信息和协同过滤算法相集合提高推荐的精确度, 算法提出了邻居选择算法和缺失值算法, 在邻居选择算法中包括基于社交网络信息、基于评价矩阵信息和融合了社交网络与评价矩阵信息结合的算法。在缺失值算法中包括对原评价矩阵预测和不对原评价矩阵预测2种。针对社交网络信息推荐系统的问题提出社交网络信息协同过滤算法, 社交网络信息协同过滤算法是把评价矩阵信息和社交网络信息两方面融合到一起, 从根本上提高了邻居选择算法的精确度, 预防了冷启动的发生。缓解数据稀疏问题采用的是缺失值算法增加评价矩阵的密度。融合社交网络信息的协同过滤算法有效地提高了基于协同过滤的推荐算法的精确度, 融合社交网络信息的协同过滤算法框架结构合理, 算法可以根据评价矩阵以外的用户信息来建立用户相似度模型。

3.2 融合基于用户和基于项目协同过滤算法

基于用户方法和基于项目方法这2种方法被电子商务推荐系统广泛应用, 基于用户方法和基于项目方法这2种方法最主要的特点就是精确度高, 这也是2种方法被广泛应用的根本原因, 也是两者的共同点。不同的是基于用户方法和基于项目方法推荐项目结果的范围不一样, 本文采用机器学习框架把基于用户方法和基于项目方法2种方法有机地结合到一起, 2种方法取长补短, 推荐系统的推荐度提高了, 而且数据稀疏性所带来的影响也被缓解了。

4 结语

目前解决信息过滤技术的最好、最有效的方法就是协同过滤算法, 协同过滤算法也是目前最为科学的推荐算法。基于协同过滤的推荐算法还有许多问题需要解决, 在协同过滤算法中针对本身的数据稀疏性和模型融合的问题, 需要提出更有效的解决方案。

参考文献

[1]方娟, 梁文灿.一种基于协同过滤的网格门户推荐模型[J].电子与信息学报, 2010 (7) :1585-1590.

[2]汪静, 印鉴, 郑利荣, 等.基于共同评分和相似性权重的协同过滤推荐算法[J].计算机科学, 2010 (2) :99-103.

基于密度敏感距离的协同训练算法第5篇

传统的机器学习方法大多只考虑有标记数据或者只考虑未标记数据,即监督学习和无监督学习两类。随着数据采集技术和存储技术的发展,获取大量未标签样例已经比较容易,而由于需要耗费一定的人力和物力,获取大量已标签样例则相对比较困难。因而在很多实际数据集中,未标签样例的数量远大于已标签样例的数量。如果只使用少量已标签样例,那么由监督学习训练得到的学习模型不具有很好的泛化能力,同时造成大量未标签样例的浪费;如果只使用大量未标签样例,那么无监督学习将会忽略已标签样例的价值。因此,研究如何综合利用少量已标签样例和大量的未标签样例来提高学习性能的半监督学习成为当前机器学习和模式识别的重要研究领域之一。

半监督学习受到了国际机器学习和数据挖掘界的高度重视,目前多种半监督学习方法已经被提出,按学习目的可以分为半监督分类、半监督聚类和半监督回归及半监督离群点检测算法。按照学习方式分可以分为:生成式模型算法、基于图正则化框架的半监督学习算法和协同训练算法[1]等,其中协同训练算法通过训练两个独立的分类器,采用互助方式迭代地扩充彼此标签数据集并以此重新构造分类器,直至分类器不发生变化为止。该算法要求数据集存在两个不相交独立的属性子集也称为两个视图。文献[1]证明,在充分冗余视图这一条件成立时,标准协同训练算法可以有效地通过利用未标记数据提升分类器的性能。为了进一步提高协同训练算法分类性能,文献[2]在协同训练算法中引入了特征选择技术提出了一种FESCOT协同训练算法,有效地删除了对提高算法分类性能不影响甚至降低分类性能的不相关或冗余属性,从而取得了很好的效果。

尽管基本的协同训练算法已经成功应用到众多领域,但它要求数据集存在充分冗余视图,这对现实获得的数据集往往难以满足。为此文献[3]提出了一种改进的协同算法,不受属性集划分的约束,可用整个属性集训练两个分类器,但增加了另一种约束即要求这两个分类器所用的监督学习算法能够将实例空间划分为等价类集合,而且训练过程需要频繁使用耗时的交叉验证作决定。随后Tri-training[4]和Co-Forest[5]进一步克服了上述算法对属性集或对分类器的限制,适用性更广。其中Tri-training使用三个分类器相互训练,迭代过程中若存在两个分类器对某个未标记数据预测分类相同时,那么就用此类标签对该未标签数据进行标注然后加入到第三个分类器下一轮训练集中,这样通过迭代扩充彼此的标签数据集后重新训练,直至三个分类器不再发生变化为止。Co-Forest是对Tri-training算法的扩充,它借鉴了组合学习的思想,利用N个分类器来参加相互迭代训练,得到了更好的结果。

半监督学习算法在充分利用少量标签数据训练分类器时,同时应该充分挖掘并利用全体数据内在的聚类分布,只有这两者相辅相成,才能达到获得更高泛化能力学习系统的目的。为了更好地协调利用好这两种信息,本文提出一种基于密度敏感距离的协同训练算法,其基本思想是:首先在全体数据集上构造全联图,在构造全联图时使用基于图的密度敏感距离测度,得到全体数据集的相似矩阵,同时对少量标签数据利用多分类器组合算法进行学习获取弱分类器,然后融合密度敏感距离获得的相似矩阵的信息给出未标签数据预测分类标记,进而对未标签数据进行选择从给出下一轮训练样本,重复上述迭代过程直至满足停止条件。实验证明可以取得较好的效果。

1密度敏感距离的协同训练算法

1.1问题描述

标签数据集χl⊆Χ×Υ={(x1,y1),…,(xl,yl)},xi∈χ⊆Rm,l为标签数据的个数,yi∈Υ={1,…,c}为类标签,未标签数据集χu⊆Χ={x1,…,xu}。u为未标签数据的个数。假设l<<u,n=l+u。可知当l较小时,仅仅使用xl训练出的分类器,由于训练样本数量不足导致其性能往往不够理想,因此尽可能地挖掘出在未标记数据所蕴含的聚类信息,用以辅助在少量标签样本上获得的弱分类器,达到性能较好的分类器。因此问题就在于如何有效利用少量标签数据,同时充分挖掘出隐藏在大量未标签数据中的聚类信息,协调好这二者关系,从而得到一个较好的半监督学习算法。

1.2算法过程分析

针对如何有效利用少量标签数据,本文提出的算法中采用多分类器组合方法,1984年,文献[10]中提出机器学习的另类理念。他认为学习模型无需绝对精确,只需概率近似正确PAC(Probably Approximately Correct)即可。由此,他建立了PAC的理论基础。Kearns和Valiant (1988,1994)在PAC的基础上,提出弱可学习的理论。文献[11]首先证明了著名的弱学习定理,即只要能够找到比随机猜测略好的弱学习算法,就可以将其提升为强学习算法。在半监督学习问题中,少量的标签数据通常能保证得到比随机猜测稍好的弱分类器。由于分类器组合方法是根据样本训练多分类器来完成分类任务,这些分类器具有一定的互补功能,在减少分类误差上比较成功,同时当各成员分类器的差异性较大,组合分类器的误差就越小。文献[4,5]中,成功地利用多分类器的方法获得了较好的半监督学习算法也充分证明了采用该项策略的有效性。

针对如何充分挖掘出隐藏在大量未标签数据中的聚类信息,根据聚类假设可知,同一簇的数据趋向于分布在一个密度相对较高的区域内,而不同簇之间则存在一个数据分布相对较于稀疏的密度较低的区域。由此可以推论,判别边界应该在密度较低的区域出现。因此希望能得到这样一个距离度量,可以描述同一个簇的数据点之间具有较高的相似性,不同簇的数据点之间具有较低的相似性。本文算法通过引入文献[9]中的密度敏感距离来获得数据集之间的相似性度量,该相似性度量可以有效描述数据的实际聚类分布,它通过放大不同簇之间数据点间距离,同时缩短同一簇内数据点间距离,最终有效描述数据的实际聚类分布。其基本思想是如果两个数据点可以由一条穿过高密度区域的路径相连接,则这两点间将被赋予较高的相似度,否则将被赋予较低的相似度。样本i和样本j之间的距离Dij计算如下:

w(i,j)=exp(ρd(i,j)-1) (1)

$D_{i j} = \min_{p \in p_{i j}} \sum_{k = i}^{k + 1 = j} w (k, k + 1)$ (2)

式中d(i,j)为根据欧氏距离得出样本i与样本j的距离,pij为连接样本i到样本j所有路径的集合。

针对上述二种信息如何有效结合,上述二种信息是相对独立地从数据集中获取的信息。如何有效地利用将直接影响到分类器的泛化误差,本文提出的算法中我们采用加权处理的方法,具体做法为:首先通过密度敏感距离获得数据集之间的相似矩阵Sn×n,进而容易得到数据集的近邻矩阵NNn×k,其中NN(i,k)表示第i个样本的第k个近邻为第NN(i,k)个样本,通过少量标签数据训练的弱分类器组合获得的基分类器对未标签数据进行投票,根据未标签数据各个类的得票率可以得到每个样本属于各个类的隶属向量distrn×c,distr(i,j)表示第i个样本属于j类的概率为distr(i,j)。因此得到融入密度敏感距离信息的隶属向量为:

$d i s t r_{i}^{*} = μ \sum_{j = 1}^{k} d i s t r_{Ν Ν (i, j) \times c} + (1 - μ) d i s t r_{i \times c}$ (3)

式中μ为折中系数,distr $_{i}^{*}$ 为最终得到的隶属向量,k为近邻个数,其它变量如前所述。

1.3算法描述

基于密度敏感距离的协同训练算法步骤:

输入:已标签数据集L,未标签数据集U,近邻个数K,置信因子θ,分类器个数N,相似性度量变量ρ。

输出: $C^{*} (x) = \underset{y}{a r g m a x} \sum_{j = 1}^{Ν} δ (C_{j} (x) = y)$

(如果参数为真则δ(·)=1,否则δ(·)=0)

步骤:

1) 根据式(1)、式(2)可以求得数据集的距离矩阵;

2) 由步骤1)得到的距离矩阵,对每个样本数据取距离最小的k个近邻,从而可以得到近邻矩阵NNn×k;

3) 构造N个随机森林,采用bootstrap方法选取训练集。对N个随机森林进行训练,得到初始的弱分类器;

4) 对每个分类器重复如下步骤:

a) 计算除当前分类器外其它N-1个分类器的组合分类误差,误差计算方法为袋外估计法,若小于前一次的误差,则进行如下步骤,否则当前分类器不需要更新;

b) 用其它N-1个分类器对未标签数据进行分类中,得到每个未标签数据属于各个类的隶属向量distri×c;

c) 利用式(3)求得融入密度敏感距离后的隶属向量distr $_{i}^{*}$ ,再取隶属度最大的类标号为该未标签数据的预测标签,并设相应的隶属度为该样本的权值;

d) 根据步骤c)加入标签后的未标签数据选取训练集,对权值小于阈值θ的进行删除。

5) 当有分类器需要重新训练时,重复步骤(4),否则停止;

6) 利用最终生成的分类器,对测试集进行分类,并计算出误差。

2实验与分析

2.1实验数据

在本节中,将通过一系列实验来验证本文所提出算法的有效性,实验所用的实验集来源于UCI机器学习公用数据[12]。

2.2实验结果与分析

实验中所用到的三个算法分别为:一是仅仅使用分类器组合方法在标签数据上训练获得的分类器,二是文献[5]提出的Co-Forest算法,三是本文提出的密度敏感距离协同训练算法。对于每个数据集首先通过十折交叉方法将其分为训练集与测试集,然后在训练集上按照标签数据占训练集数据比例为η%进行随机抽取生成标签数据,把训练集中的剩下的(1-η)%作为未标签数据。实验结果为上述方法重复运行十次,各协同训练算法在测试集上错误率取平均值得到最终测试集上的错误率见表2。本文算法中实验参数设置为近邻数:5,相似性度量ρ为3,置信因子θ为0.75,折中系数μ为0.5,分类器个数为:6。基分类器采用:随机树。实验结果如表2所示。

在上述七个数据集上进行的21个实验中,我们发现有18组比另二种算法在测试集上获得了更小的错误率,说明了密度敏感距离的协同训练算法的有效性,同时通过分析我们发现本文提出的算法比较适合解决一些字符、数字识别问题。

3结语

本文提出的基于密度敏感的协同训练算法,它通过多分类器组合方法很好地利用少量标签数据,同时利用密度敏感距离度量有效地挖掘出隐含在数据中的聚类信息,从而可以很好地辅助在少量标签数据集上生成的组合分类算法,从而有效提高其泛化能力,最后实验也证明了该方法是有效的、合适的。

参考文献

[1]Blum A,Mitchell T.Combining labeled and unlabeled data with co-training[C]//Proceedings of the 11th Annual Conference on Computa-tional Learning Theory,Madison,WI,1998:92-100.

[2]Li G Z,Liu T Y.FESCOT:Feature Selection for Co-Training[J].Jour-nal of Shanghai University,Springer&Shanghai University Press,2008,12(1):47-51.

[3]Goldman S,Zhou Y.Enhancing supervised learning with unlabeled data[C]//Proceedings of the 17th ICML.San Francisco,CA:Morgan Kauf-mann,2000:327-334.

[4]Zhou Z H,Li M.Tri-training:exploiting unlabeled data using threeclassifiers[J].IEEE Transactions on Knowledge and Data Engineer-ing,2005,17(11):1529-1541.

[5] Li M , Zhou Z H. Improve computer-aided diagnosis with machine learning techniques using undiagnosed samples[J].IEEE Transactions on Systems ,Man and Cybernetics-Part A ,2007,37(6):1088-1098.

[6] Zhu Xiao-Jin. Semi-supervised Learning with Graphs [D] .Carnegie Mellon University, 2005.

[7] Chapelle O , Scholkopf B , Zien A. Semi-supervised Learning[M] . Cambridge :MIT Press ,2006.

[8]Wang W,Zhou Z H.Analyzing co-training style algorithms[C]//Pro-ceedings of the 18th European Conference on Machine Learning.War-saw,Poland,2007:454-465.

[9] Chapelle O , Zien A. Semi2supervised classification by low density separation [C]//Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics.Barba2 dos :Society for Artificial Intelligence and Statistics ,2005:57-64.

[10] Valiant L G. A theory of the learnable[J].Communications of ACM,1984,27 (11) :1134-1142.

[11]Shapire R E.The strength of weak learnability[J].Machine Learn-ing,1990,5(2):197-227.

基于位置信息的协同过滤推荐算法第6篇

随着移动互联网的普及,在线市场的出现和急剧增长极大地影响了消费者的消费习惯,并为消费者提供了海量的产品服务和关于这些产品服务的信息。当消费者面对数以百万计的在线商品可以自由购买时,也使选择最符合消费者需求的产品变得更为困难。移动互联网服务和信息内容的日益增长将逐渐超出人们所能接受的范围,加之移动设备输入、处理、显示输出等方面能力有限,为移动用户带来沉重的“移动信息过载”问题[1]。因此,近年来移动推荐系统(mobile recommender system)[2]已成为推荐系统研究领域[3]的研究热点之一。它能够为移动用户提供自动化和个性化的商品购买建议,并逐渐成为缓解“移动信息过载”和改善移动网络资源利用率和用户体验的有效手段。

目前,移动设备也迅速普及,据CNNIC基础数据显示,截止2013年底手机网民数达到了5亿。由于手机网民大多使用智能移动设备,使得互联网信息服务逐步向移动端过渡,也使得移动电子商务进入快速发展期。通过移动设备的定位功能(如GPS定位),很多移动端的应用可以普遍获取用户的地理位置信息。此外,孟祥武等[2]总结了近年来移动推荐系统的应用和发展,也指出了基于位置的移动推荐的方向及对相关算法技术的需求。

Online To Offline(O2O)模式[4],是将线下实体经济与互联网向融合,通过互联网有效地聚集线下资源和线上购买群体,并将线下资源推送给线上用户,使互联网成为线下交易前台的一种商业模式。O2O模式中用户在线上接受推荐的线下资源完成下单、支付等流程后,凭订单凭证去线下商家提取商品或享受服务,可见线下资源和用户的位置信息对O2O模式的线上推荐是有着不可缺的重要性的。目前这种以在线支付为核心的O2O模式成为了电子商务的新亮点,相关产业日趋成熟,众多创新公司纷纷布局O2O领域[5]。

本文将提出一种基于位置信息的协同过滤推荐算法。主要解决如下问题:

(1)这种改进的推荐算法,首先通过计算地理位置的距离对项目集进行预过滤,缩小推荐的范围,大幅减少推荐过程中计算量,能解决推荐的实时性问题。

(2)由于个体的评分和对距离的感知的差异,提出对top-N推荐列表的修正,解决了对O2O模式推荐的适应问题。

(3)将传统的“用户-项目”2维协同过滤推荐引入位置信息转化为“用户-项目-位置”3维协同过滤推荐,对规避冷启动问题和提高推荐的质量有很好的效果。

2 相关工作

2.1 计算距离

距离的计算方法[6]有Euclidean distance、Minkowski Distance、Mahalanobis distance.这里采用最简单和最常用的距离度量方法Euclidean distance,计算方法如下:

这里,n是维度或者属性的数量,xk和yk分别是对象x和y的第k个属性。

2.2 协同过滤

协同过滤[3]被认为是推荐系统中最流行和广泛被应用的一种技术,它的原理就是根据推荐用户与其他用户在过去偏好的相似程度进行推荐。偏好相似程度的计算是基于用户过去对项目的评分记录的相似相似性。相似性的计算方法有cosine相似性和Pearson Correlation(PC)相似性。由于前者的测量没有考虑两个用户评分的均值和方差的差异,所以这里采用更为流行的Pearson Corre-lation(PC)相似性。

其中,ui和uj分别表示给项目i和项目j评分过的用户集,用户集uij=ui∩uj,rui表示用户u对项目i的评分,ruj表示用户u对项目j的评分,r珔i和r珔j分别表示项目i和项目j在过去的的所有用户评分的均值。PC(i,j)表示项目i和项目j的相似性,其值越大相似程度越高,反之相似程度越小。

2.3 初步预测评分

当用户给一个项目评分时,每个用户都有自己的评分范围,这里采用中心化(mean-centering)的思想对预测评分进行规范化[7]。具体的计算方法如下:

这里,表示对用户u项目i的初步预测评分,r珔i表示项目i在过去的所有评分的均值,ruj表示用户u对项目j的评分,Nu(i)表示将要把待推荐的项目i推荐给用户u,用户u过去评分过的项目的集合。wij表示待推荐项目i和用户u的评分过的项目j的相似性,其中的相似性wij=PC(i,j)。

2.4 最终预测评分

用户u在某一地理位置对用地理位置距离dexp以内的项目i的偏好最终预测值rui的计算公式为:

其中,dui表示用户u和项目i的实际地理位置距离,dexp表示用户u提交的位置信息后,用特定地理位置距离dexp对u提交的位置附近区域内的项目集进行预过滤,dexp是一个经验值。比如取值为500 米、1000 米、1500 米等,根据所在区域项目的密集程度和用户对距离的敏感程度而异。ρ是为了将预测评分的范围修正为历史评分的分布范围,在后面的数据集实验中ρ=5/6。

3 基于位置信息的协同过滤推荐算法

3.1 相关定义

定义1 位置距离表示在某一区域内的用户提交自己的位置信息时,通过提交的位置信息与这一区域内所有在线的项目的位置进行距离计算,计算出的实际地理位置距离。位置距离dui小于经验值dexp(比如dexp=500米)的项目构成协同过滤的项目集合Iui,从而达到对推荐项目集预过滤的目的。其中,位置信息是从移动终端的移动通信服务或者GPS服务获取的位置坐标。

定义2 “用户-项目-位置”3 维协同过滤推荐模型,可以记作CF(U,I,L)模型,它是一个3 维的向量空间{User,Item,Location},每个维度分别用各自的属性值组成向量来表示。它的意义在于虽然引入了第三维,但是在降维的过程中有利于缓解协同过滤推荐中相似性计算量巨大和冷启动等难题。

3.2 设计思想

本文借鉴了上下文预过滤的思想[8],考虑了适应O2O模式的需求和发展,将上下文感知提炼和简化为地理位置信息获取。通过用户与项目位置距离计算对在线项目集进行预过滤得到协同过滤项目集Iui.Iui数量的大小是由经验值dexp控制的,将会是保证推荐效果的规模适当的项目集合,从而能有效减少初步预测评分中相似性的计算量。同时,也借鉴文献[9]对3维模型进行降维,以适应在用户-项目(user-item)2 维矩阵中相似度的计算。还用了中心化(mean-centering)思想对初步预测评分进行了规范化。在对用户u对项目i的最终评分预测中又加入了位置距离的权重形成top-N推荐列表,这样做的好处有:(1)提高推荐精确性和有效性;(2)克服协同过滤中不能对新用户和新项目作出有效推荐的问题。比如,当面对新用户时,权重wij=PC(i,j)=0,^rui=r珋i,加入位置距离的权重最后也能在位置距离上由近及远结合项目的历史评分均值的高低给出预测评分由高到底的top-N个项目的推荐列表。

3.3 推荐过程描述

本节在数据模型的算法设计的基础上,在移动设备用户提交位置信息后,对算法的输入、输出、详细流程展开描述

输入:CF(U,I,L)模型的数据;当前用户u及位置信息location(GPSJD,GPSWD)。

输出:用户u在当前位置location(GPSJD,GPSWD),对附近区域在线项目集Iui中的项目的最终预测评分由高到低的top-N在线项目列表。

算法的具体过程,分为以下步骤:

(1)获取当前用户u及位置信息location(GPSJD,GPSWD),设置经验值dexp,根据式(1),遍历附近区域在线项目集Item计算出用户与项目的位置距离d(u,i),如果置距离d(u,i)小于dexp则将项目i加入预过滤在线项目集Iui.

(2)取出当前用户u的过去评分过的项目集合Iuj.

(3)在预过滤项目集Iui中取出项目i的历史评分用户集u_i.

(4)在用户u的历史评分过的项目集合Iuj中取出项目j的历史评分用户集u_j.

(5)用户集u_i和用户集u_j取交集的到共同的用户集u_ij.

(6)如果用户集u_ij非空,则用式(2)计算项目i和项目j的相似性PC(i,j),否则,PC(i,j)=0。

(7)如果用户u的历史评分过的项目集合Iuj非空,循环执行步骤(4)、步骤(5)、步骤(6)计算出所有的PC(i,j)。

(8)令wij=PC(i,j),用式(3)计算出对项目i的初步预测评分^rui.

(9)用式(4)计算出对项目的最终预测评分rui.

(10)如果预过滤在线项目集Iui非空,循环执行步骤(3)至步骤(9)依次计算出预过滤的在线项目集Iui所有项目的最终预测评分。

(11)将用户名、项目名、位置距离、初步预测评分和最终预测评分组成数据框,并按照最终预测评分由高到低排序生成top-N推荐列表,完成推荐过程。

4 实验结果及分析

为了验证本文提到的算法的有效性和可行性,及其推荐的精度和改进后的优势,进行了如下线下实验进行验证。实验平台是PC,intel i3 350M处理器2.26GHz,RAM 2GB和Windows 7 操作系统。开发工具用的是RSudio,算法是用R语言编写的。

4.1 数据集

因为获取既有位置信息又有用户偏好的移动推荐系统相关数据集要比获取传统的互联网推荐系统相关数据集更为困难[2],而且目前开没有权威可用的开源数据集。为了验证算法,本文采用两个数据集结合处理得到的仿真实验数据集:一个是美国明尼苏达州立大学的Group Lens研究小组提供的Movie Lens数据集(http://www.grouplens.org)。它包含了943位用户对1682 部电影的10万条评分。该数据集的原始用户-项目评分矩阵的稀疏度为93.7%.还有一个是中国科学院等几个机构举办中国第一届大数据技术创新创业大赛中第五道赛题提供的北京市12000 辆出租车在2012 年11 月所产生的所有GPS数据中的样本数据(http://bigdatacontest.ccf.org.cn/)。数据的处理过程如下:

首先,把Movie Lens数据集的1682部电影模拟推荐的项目,并给每个项目赋予出租车的位置坐标信息。同样,将943位用户也赋予位置坐标信息。项目集和用户集的地理位置坐标分布如图1 和图2。项目与用户位置坐标赋予的方法是连续的截取同一区域和时间段(5秒)内出租车反馈的位置坐标,从分布图看大致可以模拟出一个区域商业中心。

再将10万条用户评分分为训练集和测试集。其中,前者占8万条用于计算相似性和预测评分,后者占2万条用于检验预测评分推荐的效果。

4.2 评价指标

实验评估标准的选择是实验的重要组成部分。合理的评估标准能够很好地评价算法性能,发现算法的有待改进之处。本实验从推荐的准确性方面考虑,选取了协同过滤中常用的平均绝对误差MAE(Mean Absolute Er-ror)[10]作为实验结果的评估标准。平均绝对误差MAE是评价推荐算法质量的标准之一,它通过计算预测评分与真实评价数据上的差别来衡量推荐结果的准确性。MAE的值越小,推荐准确性越高。假设预测的用户评分集合表示为{p1,p2,…,pN},对应的实际用户评分集合为{q1,q2,…,qN},则具体的MAE计算公式为

4.3 实验结果分析

由于考虑了适用于O2O电子商务模式,本文提出的基于位置信息的协同过滤推荐算法与传统的协同过滤推荐算法在邻居的概念上有显著的区别。改进算法中的邻居首先是地理位置距离相近的邻居,其次才是在计算相似性度量上的邻居。传统的协同过滤推荐算法以文献[11]为例,都是先计算项目的相关程度选择在相似性度量的上的邻居,所以传统的协同过滤存在冷启动问题,即对新用户和新项目都无法作出推荐。

在传统的算法中,如果一个用户的历史评分项目的数量是m,在线项目的数量是n,那么相似性的计算量为O(mn)。在改进的算法中,如果一个用户的历史评分项目的数量是m,对在线项目通过预过滤后的地理位置上的邻居的数量是w,那么相似性的计算量为O(mw)。从相似性的计算量对比来看,因为w要比n小好几个数量级,且地理距离预过滤的计算量显然要比相似性的计算量小的多,所以改进算法的计算量将显著减少。同时,咱相似性计算的过程中也缓解了用户-项目二维矩阵中评分极度稀疏的问题。

Movie Lens数据集中有943位用户和1682部电影,构成了一个943×1682的用户-项目二维矩阵。如果没有对推荐的项目进行预过滤,在计算项目-项目之间的相似度时,就要依次计算历史评分项目与所有其它项目之间的相似度。通过地理位置距离对项目集进行预过滤后,相似性的计算量将极大地减少,从而很好地适应用户、项目和位置经常变化的实时推荐。预过滤项目集的大小与选定的距离经验值dexp有关,这个经验值反映的是不同用户对地理位置距离的敏感程度。在本实验的数据集上500~2500米距离上对应的邻居数量变化如图3。

本实验分别采用基于传统的协同过滤算法和本文提出的改进的基于位置信息的协同过滤算法在结合的数据集上进行实验。其中传统的协同过滤没有进行预过滤,改进算法利用地理位置的距离对项目集进行了预过滤。实验的评分预测精度的对比如图4所示,由于实验数据集的限制,用地理位置距离预过滤后的项目集邻居数目会显著减少。但是,改进算法对不同用户的评分范围进行了规范化,最终改进算法的还是有较好的推荐精度,MAE值比较低。在相同邻居数目的情况下,MAE值略低于传统的协同过滤推荐。

实验还验证了本算法能有效规避协同过滤中的冷启动问题,即对新项目和新用户都能作出有效推荐。在实验计算结果数据中可截取如下数据说明对新项目的推荐:在对用户164的top-N推荐列表中,项目1565和1236是新项目,没有历史评分,所以这两个项目的平均评分都是0,初步预测评分也是0。但是,用户与两个项目的地理位置距离分别是155.5685米和736.5743米,在最终的预测评分中考虑距离的权重所以两个新项目的最终评分分别是0.7036929和0.2195214,并是两个项目出现在了推荐列表的末端。在现实中,如果新项目离用户很近,给予它出现在推荐列表末端的机会是很有实际意义的。

在Movie Lens数据集中没有新用户的情况,通过添加的新用户也能得出推荐列表。推荐列表与前面的新项目情况的截取数据相似,只是项目的平均评分不为0,最终评分预测是平均评分结合距离权重得到的。推荐列表的实际意义是将距离近也受到其他用户好评的项目推荐给新用户。

5 结语

本文在协同过滤的推荐系统相关研究的基础上,结合移动电子商务的发展带来的机遇和对移动推荐系统的需求。考虑了O2O模式的特点,提出一种基于位置雅息的协同过滤算法。在“用户-项目-位置”3维协同过滤推荐模型中,对于已有的用户或者项目会先通过第3维位置进行预过滤,降维到传统的“用户-项目”2维中计算相似性,并对不同用户评分范围规范化,最后又引入第3维的权重做出推荐。对于新用户和新项目也能通过第3维来作出推荐。该算法在推荐过程的启动、计算量、推荐质量和实际意义都有一定的鼓进。未来改进的方向在于在最后的推荐列表中考虑时间、项目类别等上下文信息,为用户提供更为个性化推荐。

参考文献

[1]Wang L C,Meng X W,Zhang Y J.A cognitive psychology-based approach to user preferences elicitation for mobile network services[J].Acta Electronica Sinica,2011,39(11):2547~2553.

[2]孟祥武等.移动推荐系统及其应用[J].软件学报,2013,24:91~108.

[3]许海玲,吴潇,李晓东,阎保平.互联网推荐系统比较研究[J].软件学报,2009,20(2):350~361.

[4]余思琴等.O2O模式对电子商务带来的机遇和挑战探析[J].电子商务,2013,3(1):84~85.

[5]卢益清,李忱.O2O商业模式及发展前景研究[J].企业经济,2013,11:98~101.

[6]Adomavicius G,et al.Data mining for recommender systems(book chapter).Recommender Systems Hand-book.New York,Dordrecht,Heidelberg,London:Springer Press,2011:39~97.

[7]Adomavicius G,Tuzhilin A.A Comprehensive survey of neighborhood-based recommendation methods(book chapter).Recommender Systems Handbook.New York,Dordrecht,Heidelberg,London:Springer Press,2011:107~144.

[8]Adomavicius G,et al.Incorporating contextual information in recommender systems using a multidimensional approach[J].ACM Transactions on Information Systems,2005,23(1):103~145.

[9]徐风苓,孟祥武,王立才.基于移动用户上下文相似度的协同过滤推荐算法[J].电子与信息学报,2011,33(11):2785~2789.

[10]Herlocker J L,et al.Evaluating collaborative filtering recommender systems[J].ACM Transactions on Information Systems,2004,22(1):5~53.

多小区下行链路协同算法应用研究第7篇

主公共控制信道和业务信道频率在N频点网络中, 由于在复用度方面存在差异, 导致两者在特性方面出现不一致的现象, 主公共控制信道的质量难以对业务信道的质量进行真实的反映, 基于主公共控制信道实现覆盖的优化。在高负荷网络环境下, 同频干扰现象比较严重, 用户的感知受到严重的影响, 出现有信号却不能电话、信号良好无法接通电话、通话时话音时断时续等现象。因此, 在高负荷网络环境下, 提高用户的感知、确保网络性能的稳定成为关键问题。

在高负荷网络环境下, 面对同频干扰的问题, 作为一种同频干扰规避算法, 多小区下行链路干扰协同MDIC主要策略是对服务小区的功率及相邻区域的干扰情况进行综合考虑, 将资源合理分配给用户, 在一定程度上确保下行链路C/I的良好;同时对用户下行链路的C/I进行实时监控, 通过调整防止进一步恶化, 进而确保用户业务的连续性, 提升用户的感知。

1 算法概述

目前各个阶段都考虑干扰的规避方案, 相互配合相互补充, 构成一个完整的干扰规避体系, 称之为MDIC算法 (多小区下行干扰协同评估算法) , 算法主要实现对小区间干扰的抑制。由于单小区联合检测比较成熟, 因此, 小区内的下行干扰对终端的影响通常是比较小的, 其干扰主要来自小区间, 而小区间的下行干扰主要来自邻区。

1.1 算法的思路

首先, 综合考虑服务小区和邻区信息, 将用户分配在干扰较小的资源上。

其次, 由于环境的变化和用户的移动造成的资源干扰, 可以将用户调整到干扰较小的资源上。

最后, 如果突发性强干扰来临时, 不能及时将用户调整到干扰较小的资源上, 可以通过挽救措施进行规避。

1.2 M DIC算法的应用阶段

1.2.1 分配资源。

在干扰较小的资源上分配新用户。基于这种理念, 实施内外圈干扰隔离方案和多小区下行干扰协同评估的资源分配方案。

1.2.2 调整资源。

用户遭受到的干扰比较严重时, 可以在干扰较小的资源上重新分配该用户。从这个角度来说, 对受干扰的资源进行调整。

1.2.3 异常挽救阶段。

TD-SCDM A中的M DIC功能主要是规避下行同频干扰, 使得用户获得更好的无线服务。算法主要从接入过程、保持过程两个方面来消除干扰, 所以分两部分进行。目前室内外基本都是异频组网, 因此只需要开启室外小区的MDIC功能即可, 室内小区不需要开启。

2 算法流程

2.1 分配资源的算法

2.1.1 获取潜在干扰邻区。

通常情况下, 为了提高用户的感知, 将多个室外的邻区配置在室内, 室内受区域的影响, 那么, 接收到的室外的邻区, 对于终端来说是不一样的, 判断准则: (1) 在PCCPCH RSCP方面, 如果服务小区超过台配置的门限, 那么终端处于小区的中心区域。 (2) 如果服务小区与邻区的PCCPCH RSCP之差低于后台配置的门限值, 那么就可以认为该邻区处在潜在干扰邻区内。

2.1.2 获取干扰邻区的信息。

确定干扰邻区后, 对于相同频点上的邻区和服务小区, 通过利用内部接口可以获取各个时隙的TCP、当前占用的物理资源, 邻区的路损等信息。

2.1.3 计算时隙C/I。

复用频点的各个时隙的C/I可以根据服务小区和邻区的TCP、路损等信息进行计算, 具体算法如下: (1) 通过RNC内部消息获取服务小区、潜在干扰邻区的频点信息、各个频点的每个时隙的TCP、RU资源等信息; (2) 服务小区和干扰邻区的路损信息根据终端上报的PCCPCH RSCP得到; (3) 复用频点各个下行时隙可提供的剩余功率根据服务小区的复用频点上的TCP等信息得到, 进而获取信号功率C; (4) 服务小区的下行干扰通过服务小区TCP、路损等信息进行计算, 而邻区干扰通过邻区TCP、路损等信息进行计算; (5) 底躁+本小区干扰+邻区干扰构成复用频点下行总干扰I; (6) 复用频点的C/I值通过第3步和第5步的结果得到。

2.1.4 资源分配。

在潜在的干扰邻区, 如果用户处于小区边缘, 那么: (1) 如果后台开关处于“边缘用户优选专用频点”位置, 需要将用户分配室内的专用频点; (2) 如果后台开处于“边缘用户优选复用频点”位置, 根据C/I的计算结果进行判断:首先, 如果通过最大的C/I满足业务的需求, 需要将复用频点分配给用户, 并在复用频点上选择一个C//I最大的时隙;其次, 如果复用频点没有任何时隙的C/I能够满足业务的需求, 需要将专用频点分配给该用户。

2.2 资源调整算法

2.2.1 判断目前用户无线链路情况。

当用户的下行发射功率SCP较大, 且终端测量到的下行ISCP较大时, 需要将用户分配到干扰较小的资源上 (1) 保持业务时, 首先I-ub口的SCP A测量控制进行下发;定义SCP A事件:用户下行发射功率超过A事件门限, 持续时间time too trigger; (2) 上报A事件后, 下发1i测量控制给终端;定义1i事件:用户的下行ISCP大于1i门限, 持续时间time too trigger; (3) 1i经终端上报后, 终端的下行干扰和发射功率表明都较大, 难以保证用户的感知, 需要将用户调整到一个干扰较小的资源上。

2.2.2 调整资源。

当需要调整用户的资源时, 需要为用户选择一个干扰较小的资源, 在一定程度上满足用户的感知, 具体流程与资源分配中流程相似。

2.3 异常挽救算法流程

通常情况下, MDIC会将用户分配在干扰较小的资源上, 受干扰突发性的影响, 可能会出现网络侧在用户受到强干扰时, 未能将用户调整到干扰较小的资源, 通常的做法是释放用户, 具体如下:

2.3.1 小区更新后的处理。

如果用户在稳态下对小区更新进行上报, 为其重新分配资源;小区更新在切换过程中, 也会分布一套资源。

2.3.2 RL failure后。

当出现rl failure时, 通过采取措施进行挽救, 将用户调整到干扰较小的资源上。

2.3.3 下行RLC不可恢复错误。

当下行rlc出现不可恢复的错误时, 通过采取措施进行挽救, 将用户调整到干扰较小的资源上。

2.3.4 重配超时。

重配超时后, 通过采取措施进行挽救, 将用户调整到干扰较小的资源上。

综上所述, 在空口出现异常时, 在多数情况下, 通过采取措施进行挽救, 从而降低掉话率。

3 验证MDIC功能

3.1 验证有效性

(1) 算法开启前, 对选定区域进行路测, 算法开启后进行测试指标对比验证; (2) 算法开启后, 对接通率、掉话率、切换成功率进行前后对比验证; (3) 由于现网终端性能的差异和不稳定性, 算法性能可能受到终端测量异常的限制。

3.2 选定区域

某区TD网络选取RNC811区域做MDIC专项, 所选区域内包含11个宏站点和2个室分站点, 共35个小区, 76块载频。

3.3 后台KPI指标对比

对比MDIC功能修改前后指标发现, 语音接通率由99.87%变为99.89%, 改善0.02%, PS域接通率由99.66%变为99.70%, 改善0.04%, 掉话率和掉线率基本持平, 同频接力切换成功率由99.32%变为99.36%, 改善0.04%, 异频接力切换成功率由99.43%变为99.44%, 改善0.04%。

3.4 前台测试指标对比

对比MDIC功能发现, 语音接通率和掉话率一致, 均未发生事件, MDIC功能开启前DPCH C/I为9.172, M DIC功能开启后DPCH C/I为9.150, 开启后略有差距, M DIC功能开启前UE发射功率为-18.300dbm, M DIC功能开启后UE发射功率为-27.408dbm, 开启后比开启前减少手机发射功率9.108dbm, 改善明显。MDIC功能开启前后, 高质差小区数量由17变为16, 有所改善, 减少1个;上行BLER由原来的1.45%变为1.91%, 有所恶化, 恶化0.46%;下行BLER由原来的1.75%变为1.44%, 有所改善, 优化0.31%。

4 结论

M DIC功率开启后对接通率指标、切换成功率指标有所提高, 对掉话率指标无明显提升, 减少了手机发射功率, 降低全网底噪, 减少了高质差小区数量, 建议全网推广。

参考文献

[1]陈海军.CDMA网络簇划分及优化[J].中小企业管理与科技 (下旬刊) , 2012.05.

[2]景娜.浅谈无线网络中的主要技术[J].价值工程, 2010.35.

反映用户兴趣变化的协同过滤算法第8篇

协同过滤算法是时至今日非常成功的一种个性化推荐技术[1,2],在很多领域中得到了应用[3]。协同过滤算法中最重要的一步是相似度的计算方法。传统的协同过滤算法在计算相似度时多采用余弦相似性、相关相似性、修正的余弦相似性[2]等度量方法。以上方法基本都是依据双方共同评价的项目进行相似性计算的。但是在现实的用户评分矩阵中,用户的评分在大多情况下是比较稀疏的,用户对某项目的共同评分就更加稀少。可见传统的相似性计算方法是有一定弊端的。有人提出了基于用户兴趣度的相似性度量,考虑了用户对不同项目类型的兴趣度对用户相似性的影响。但是这种方法不能解决用户兴趣随时间变化的问题。本文把基于项目相似度的数据权重[4]的方法与基于用户兴趣的相似度度量[5]相结合,两者结合,既能解决评分矩阵稀疏时相似性计算不准确的问题,又能考虑用户兴趣的转移。

1 传统的协同过滤算法

传统的协同过滤算法有三个核心步骤[6],下面以基于用户的协同过滤算法为例来介绍三个关键步骤:

第一步

用户对项目评分的表示方法。用m×n阶的矩阵R(m×n)来表示m个用户对n个项目的评分。其中m表示用户的个数,n表示项目的个数,矩阵中的Rij即为用户i对项目j的评分。如果某用户对某项目没有评分,那么用0表示。

第二步

计算用户间的相似性,形成最近邻居。计算用户的相似性是协同过滤算法的核心,也是最关键的一步。这步需要计算用户间的相似度,从而生成目标用户的最近邻居集,而后根据邻居的喜好信息进行推荐。相似度算法的选择直接的影响最后推荐结果的精度。

目前计算相似性的方法种类繁多,但使用最多的是下面三种方法:

1)余弦相似性

余弦相似性。某用户对m个项目的评分是用户评分矩阵中的一个行向量,用户的个数为n,代表共有n个这样的行向量。第一步中提到,若用户没有对某个项目评分,那么这个评分默认为0。那么任意两个行向量间余弦的夹角就可以表示这两个用户间的相似性:

其中Ri,c表示用户i对项目c的评分,Rj,c表示用户j对项目c的评分。

2)相关相似性

设Iij表示用户i和j进行过共同评分的项目集合,由于Person相关系数经常用来衡量变量间的线性相关程度,那么用户间的相似性也可以通过Person相关系数来衡量:

其中Ri,c表示用户i对项目c的评分,Rj,c表示用户j对项目c的评分,表示用户i对评价过项目评分的平均分,表示用户j对评价过项目评分的平均分。

3)修正的余弦相似性

修正的余弦相似性在计算时,通过使用减去用户对项目的平均评分的方法,来考虑不同用户评分尺度不同的问题,从而达到对余弦相似性进行改善的目的。修正的余弦相似性公式如下:

其中Iij表示用户i和j行进过共同评分的项目集合,Ii表示用户i评过分的项目集合,Ij表示用户j评过分的项目集合。

第三步

预测评分,生成Top-N推荐。对目标用户有两类推荐结果可以计算,一是用户对任意项目的预测评分,二是TopN推荐集。在目标用户u的最近邻居集S生成以后,u对任意项目的预测评分方法如下:

其中Ru为用户u的评分平均值,sim (u,v)为两个用户u与v的相似度,Rv,i为用户v对项目i的评分。

取其中排在前面的而且目标用户中未出现过的前N个项目作为Top-N推荐集。

2 改进算法描述

2.1 基于用户兴趣度的相似性

2.1.1 基于用户兴趣的相似性度量的描述

基于用户兴趣的相似性度量方法认为用户间的相似度不只与用户评过分的项目有关,并且与用户本身对某项目的感兴趣的程度有关。如果两个用户有相似的爱好时,则认为它们之间的相似度比较高。用户对某项的兴趣程度如下:

其中Nu,i为用户u对i类项目的评价个数,Nu为用户u的总评价个数。那么用户之间的兴趣相似度计算如下:

2.1.2 基于用户兴趣的相似性度量的优缺点

这种新的相似度的计算方法在一定程度上克服了传统相似性计算方法只依据用户评分的不足,同时也在一定程度上减少了用户评分稀疏带来的负面影响。但是用户的兴趣度会随着时间的变化而变化,这种方法并不能有效地反映用户兴趣变化对推荐效率的影响。

2.2 基于项目相似度的数据权重

2.2.1 基于项目相似度的数据权重的描述

设Iu为用户u访问过的项目集合,定义一个可调控的时间窗T,在时间窗内用户u访问过的资源集合定义为Iut,从而用户的最近兴趣可以用Iut来表示。对于在时间窗内的项目i∈Iu,无论u何时访问i,如果Iut中有很多项目和i都很相似,说明项目i符合用户的当前兴趣,那么我们认为在之后一段时间内,u感兴趣的项目和项目i是很可能相似的,在对用户u生成推荐时项目i可能会起到比较重要的作用。基于项目相似度的权重可以用函数WS[u,i]来表示,用它来衡量资源i与用户u兴趣的相关程度。通过计算i和Iut的总体相似度sim[i,Iut]得到WS[u,i],而sim[i,Iut]可以用i和Iut中每个资源j的平均相似度来表示:

其中,size[Iut]表示Iut中的资源个数。

2.2.2 基于项目相似度的数据权重的意义

近期的协同过滤算法中考虑用户兴趣变化时,大多使用某种基于时间的数据权重方法[7]。这类方法的核心思想是时间权重随着用户访问时间呈线性变化,越是近期被用户访问资源,其时间权重越重。即越是近期的访问数据其重要性越大。但是用户的兴趣是经常反复变化的,因此用户的历史数据对于生成推荐也非常重要。基于时间权重的方法忽略了历史数据的作用,这是弊端。而基于项目相似度的数据权重能有效地利用历史数据反映用户的兴趣变化。从而更客观地反映用户的兴趣变化。

2.3 考虑用户兴趣变化的加权相似度

把式(6)与式(7)合并,得到一种新的加权求相似度的方法:

前面提到过,协同过滤算法中最重要的一个步骤是计算用户间的相似性。式(6)中的基于用户兴趣的相似性度量与传统的形似度求法相比可以在一定程度上解决用户评分矩阵稀疏的情况,但是它无反映用户的兴趣变化。而式(7)是一种有效的解决用户兴趣变化的方法,因而将式(7)基于项目的相似度数据权重与式(6)结合起来,得到一种新的计算用户相似度的方法。通过使用这种新的相似性计算方法对之前的协同过滤算法进行改进。这种计算方法集成了以上两种方法的优点,在有效地解决了评分用户稀疏问题的同时也考虑了用户的兴趣变化。

3 实验结果及分析

3.1 实验数据集

MovieLens是很著名的协同过滤推荐系统。它提供了超过5000部的电影以及超过70000的用户。而且它含有能够反映用户兴趣变化的时间属性。因为本实验需要验证新的相似度解决稀疏性的问题以及解决用户兴趣转移的优越性,所以需要两组数据集。

第一组实验需要验证本文算法在解决稀疏性问题上的改进。此组实验在该数据集中提取记录包括450个用户和2954部电影,共69988条记录,本实验中数据集的稀疏度为:

本组实验将其中80%的数据作为训练集,剩下的20%为测试集。此数据集记为数据集A。

第二组实验需要验证本文算法在解决用户兴趣转移上的改进。为了避免数据稀疏性问题的发生,此组实验在数据集中提取记录时,要求每个用户最少为60部电影评过分并且每部电影最少被60个用户评过分,最终提取的数据集包括45个用户,275部电影,其中时间跨度为40天,共4666条记录。

本组实验将其中80%的数据作为训练集,剩下的20%为测试集。此数据集记为数据集B。

3.2 实验的度量指标

推荐质量常用来衡量一个推荐算法优秀与否,在推荐系统中通肠认为,如果通过推荐算法得到的结果能够和用户的兴趣爱好相符合,能够达到用户满意的程度,那么此推荐系统就会被用户认可,进而用户对此推荐系统的信赖度会增加。最终网站的销售量会大大增加,会形成客户满意和网上商家获益的一种双赢局面。因此推荐算法的优劣直接关系到整个电子商务系统的好坏。目前学术界在评定推荐算法优劣时,通常把平均绝对偏差MAE作为指标。平均绝对偏差是计算实际评分值与系统中使用的推荐算法得到的预测评分值之间的差值来反映算法的准确性,MAE方法[8]如下式所示:

其中实际评分集合用P={p1,p2,…,pn}表示,预测评分集合用Q={q1,q2,…,qn}表示。MAE值越小,则表示使用此推荐算法得到的预测评分值与用户的实际评分值越接近,从而表示此推荐算法越准确。

3.3 实验结果

本文设置两组对比实验,分别验证本文算法在解决用户评分矩阵稀疏性和用户兴趣转移上的先进性。

第一组验证在解决用户评分矩阵稀疏性上的先进性,比较文献[5]中算法与本文算法,此组对比实验采用数据集A。对比实验如图1所示。

实验结果表明,本文算法的MAE值比文献[5]中算法的MAE值要低,而且在用户稀疏的情况下这种效果更加明显,可见本文算法在解决稀疏性问题上性能更好。

第二组验证在解决用户兴趣转移上的先进性,比较使用基于用户兴趣度相似性的协同过滤算法与本文算法,此组对比实验采用数据集B。对比实验如图2所示。

因为此组实验中使用的是数据集B,所以此组实验中不存在稀疏性的影响。由图2可知,本文算法的MAE值明显偏小,因为本文算法考虑了用户兴趣的转移,所以在推荐质量上本文算法的性能更好。

4 结语

本文针对协同过滤算法中存在的稀疏性以及不能及时反映用户兴趣变化的问题,提出了将基于用户兴趣度的相似性和基于项目的相似度的数据权重相结合的一种相似性计算方法。

对比实验表明,将基于用户兴趣度的相似性和基于项目的相似度的数据权重引入到协同过滤算法中后,可以更好地解决评分矩阵的稀疏性并且同时能够更有效地捕捉用户兴趣,因此推荐精度更高。

未来的工作方向是如何自动调整基于项目相似度的数据权重方法中时间窗口,这样会比设置固定参数确定窗口大小更精确,因此对于时间窗口的自动调整是进一步研究的目标。

参考文献

[1]Greg Linden,Brent Smith,Jeremy York.Amazon-com recommendations: Item-to-item collaborative filtering[J].IEEE Internet Computing, 2003,7(1):76-80.

[2]Adomavicius G.Tuzhilin A.Toward the next generation of recommender systems;A survey of the state-of-the-art and possible extensions [J].IEEE Transactions on Knowledge and Data Engineering,2005, 17(6):734-749.

[3]潘宇,林鸿飞,杨志豪.基于用户聚类的电子商务推荐系统[J].计算机应用与软件,2008,25(4):25-26.

[4]嵇晓声,刘宴兵,罗来明.协同过滤中基于用户兴趣的相似性度量方法[J].计算机应用,2010,30(10):2618-2620.

[5]刑春晓,高凤荣,战思南,等.适应用户兴趣变化的协同过滤推荐算法[J].计算机研究与发展,2007,44(2):296-301.

[6]Breese J S,Heckerman D,Kadie C.Empirical analysis of predictive algorithms for collaborative filtering[C]//Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence,1998:43 -52.

[7]郑先荣,曹先彬.线性逐步遗忘协同过滤算法的研究[J].计算机工程,2007,33(6):72-82.

基于用户兴趣度的协同过滤算法第9篇

信息技术的井喷式发展使我国的历史学研究进入了信息化的轨道,历史资源数量巨大。以辛亥革命为例,辛亥革命是中国近代史上具有划时代意义的大事件,并且关于辛亥革命的资料文献众多,研究者搜寻所需信息的成本越来越高。传统搜索引擎缓解了信息检索的压力,但传统的搜索引擎将研究者视为一个群体,未考虑个性化差异,难以满足研究者的个性化需求。因此,需将个性化推荐技术应用于历史领域中。个性化推荐技术根据已有的用户数据,对目标用户进行信息推荐,帮助用户快捷的检索到自己所需要的信息。

2 基于用户兴趣度的协同过滤算法

协同过滤技术是要确定目标用户的最近邻居,确定用户最近邻居是利用用户间的相似性,用户兴趣度是衡量用户相似性最重要的指标。当确定了用户对某类资源的兴趣度时,可以将邻居用户中兴趣度高的资源进行聚类,从而进行资源推荐。

2.1 用户兴趣度

根据用户对网页的浏览行为,可以判断用户对网页的兴趣度,故可利用用户浏览行为计算用户兴趣度[1]。在历史领域中,服务器端所记录用户在网页上的行为包括以下几种:

1)用户下载网页提供的资源。

2)用户长时间的浏览网页。

3)用户频繁的访问网页。

基于以上情况本文提出一种基于访问次数、浏览时间以及下载情况的兴趣度归一算法。设用户浏览网页Wi的次数为Frequent(Wi),第k次浏览页面Wi的时间为Time(Wi,k),第j次浏览页面时下载网页中的内容Download(Wi,j),若页面提供资源下载,则用户对网页Wi的兴趣度为Down_Interest(Wi),若页面不提供资源下载,则用户对页面Wi的兴趣度为Time_Interest(Wi),则在平衡提供下载资源的页面与未提供下载资源的页面后,设用户对任意页面X的兴趣度Interest(X)。

假设在不考虑下载的情况下,用户从本次查询页面列表中共点击L个页面,构成本次用户点击页面集T,则T中所有页面的总浏览时间可看成一个数列,计算此数列的平均值u和标准方差ð,然后用高斯归一化公式处理[2],页面兴趣度计算如下:

若考虑下载情况,用户从本次查询页面列表中共点击L个页面,在本次查询列表中共从N个页面中下载资源,构成本次用户下载资源集M,则M中所有页面的下载情况可以构成一个数列,若在页面中下载资源,则页面的下载情况为1,否则为0,由此计算数列的平均值m和标准方差n,然后用高斯归一化公式处理,页面兴趣度计算如下:

故用户对任意页面X的综合兴趣度Interest(X)计算如下:

2.2 相似度计算

向量空间中的相似性sim(D1,D2)用于度量两个文档D1,D2当文档被表示为文档空间的向量,就可以利用向量之间的距离公司来表示文档之间的相似度。文档的分类过程可以转化为计算文档向量之间的距离。相似度大的文档,相对应的向量之间的距离近;反之,相似度校的文档,相对应的向量之间的距离就远[3]。目前广泛采用的是三种计算相似性的方法:余弦相似性、Pearson相关相似性和修正的余弦相似性[4]。

本文采用的相似性计算方法为余弦距离计算公式:

其中Wi代表词频向量。

本文结合余弦距离计算公式和用户兴趣度作为相似性度量方法,将用户代替文档的角色,资源代替词的角色,用户对资源的兴趣度代替词频向量的角色,得出目标用户User和用户i的用户兴趣度的余弦相似性sim_Interest(User,Useri)度量计算公式:

其中Interest(Rk)代表目标用户对资源k的兴趣度,Interest(Ri,k)代表用户i对资源k的兴趣度。

2.3 基于用户兴趣度的协同过滤资源聚类算法

结合以上分析,本文给出基于用户兴趣度的协同过滤算法。

算法:基于用户兴趣度的协同过滤算法。

算法功能:确定推荐资源。

输入:用户行为集。

输出:推荐资源集。

本算法复杂度为O(N*M),其中:N表示最近邻居用户,M表示分析得到的资源数。

3 模拟实验的结果和评价