协同过滤的一种个性化推荐算法研究

计算机应用研究

ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ

Ｖｏｌ．２５Ｎｏ．１Ｊａｎ．２００８

协同过滤的一种个性化推荐算法研究

郭艳红，邓贵仕

（大连理工大学系统工程研究所，辽宁大连１１６０２３）

倡

摘　要：在分析传统推荐算法不足的基础上，提出一种稀疏矩阵下的个性化改进策略。首先进行一对一的个性化预测，得到虚拟用户评分矩阵，在此基础上再进行综合预测。该方法避免了传统推荐算法中推荐值与用户相似度不密切相关的弊端，提高了协同过滤的预测精度，尤其是在矩阵极端稀疏情况下的预测精度。最后通过实验验证了算法的有效性和优越性。

关键词：协同过滤；稀疏矩阵；相似度；个性化推荐

中图分类号：ＴＰ３９１　　　文献标志码：Ａ　　　文章编号：１００１唱３６９５（２００８）０１唱００３９唱０３

Ｉｍｐｒｏｖｅｄｐｅｒｓｏｎａｌｉｚｅｄｒｅｃｏｍｍｅｎｄａｔｉｏｎａｌｇｏｒｉｔｈｍｉｎｃｏｌｌａｂｏｒａｔｉｖｅｆｉｌｔｅｒｉｎｇ

（ＩｎｓｔｉｔｕｔｅｏｆＳｙｓｔｅｍｓＥｎｇｉｎｅｅｒｉｎｇ，ＤａｌｉａｎＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，ＤａｌｉａｎＬｉａｏｎｉｎｇ１１６０２３，Ｃｈｉｎａ）

ＧＵＯＹａｎ唱ｈｏｎｇ，ＤＥＮＧＧｕｉ唱ｓｈｉ

Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒａｎａｌｙｚｅｄｔｈｅｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｔｒａｄｉｔｉｏｎａｌｃｏｌｌａｂｏｒａｔｉｖｅｆｉｌｔｅｒｉｎｇａｎｄａｄｖａｎｃｅｄａｋｉｎｄｏｆｐｅｒｓｏｎａｌｉｚｅｄｐｒｅｄｉｃｔｉｖｅｓｔｒａｔｅｇｙ：ｏｎｅｔｏｏｎｅｐｒｅｄｉｃｔｉｏｎｔｏｃｏｒｒｅｃｔｔｈｉｓｓｉｔｕａｔｉｏｎｔｏｉｍｐｒｏｖｅｔｈｅｐｒｅｄｉｃｔｉｖｅａｃｃｕｒａｃｙｉｎｓｐａｒｓｅｍａｔｒｉｘ．Ｔｏｐｒｏｖｅｔｈｅｓｕｐｅｒｉｏｒｉｔｙｏｆｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍ，ｔｈｉｓｐａｐｅｒｕｓｅｄｃｏｓｉｎｅｓｉｍｉｌａｒｉｔｙａｎｄｐｅａｒｓｏｎｓｉｍｉｌａｒｉｔｙｔｏｍｅａｓｕｒｅｔｈｅｓｉｍｉｌａｒｉｔｙａｍｏｎｇｕｓｅｒｓａｎｄｔｈｅｎｐｒｏｄｕｃｅｄｔｈｅｐｒｅｄｉｃｔｉｏｎｓｕｓｉｎｇｔｒａｄｉｔｉｏｎａｌｃｏｌｌａｂｏｒａｔｉｖｅｆｉｌｔｅｒｉｎｇａｎｄｔｈｅｎｅｗｐｅｒｓｏｎａｌｉｚｅｄｐｒｅｄｉｃｔｉｖｅａｌｇｏ唱ｒｉｔｈｍ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｐｒｏｖｅｔｈｅｖａｌｉｄｉｔｙａｎｄｓｕｐｅｒｉｏｒｉｔｙｏｆｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍａｔｌａｓｔ．Ｋｅｙｗｏｒｄｓ：ｃｏｌｌａｂｏｒａｔｉｖｅｆｉｌｔｅｒｉｎｇ；ｓｐａｒｓｅｍａｔｒｉｘ；ｓｉｍｉｌａｒｉｔｙ；ｐｅｒｓｏｎａｌｉｚｅｄｒｅｃｏｍｍｅｎｄａｔｉｏｎ　　协同过滤算法不依赖于商品的语义描述，只根据用户的意ｔｅｍ）中应用最广泛和成功的技术。但是协同过滤推荐系统中见或行为即能产生推荐，是目前推荐系统（ｒｅｃｏｍｍｅｎｄｅｒｓｙｓ唱

协同过滤基于以下假设：人与人之间存在偏好和兴趣上的相似；人对事物的偏好是具有稳定性的，因此可根据过去的偏好预测未来的选择。

user2F

user3

ABC

G

项目空间巨大，导致矩阵极端稀疏。传统的推荐算法在高维稀疏矩阵上进行运算往往导致不准确的推荐，从而影响系统的应用和推广。本文从协同过滤的推荐算法入手，指出传统推荐算

法在矩阵稀疏情况下的不足，进而提出一种新的个性化推荐策略，通过算法进行模拟，改进了精度。

DE

１　协同过滤算法及分析

１畅１　协同过滤工作原理

在实际生活中，对于不熟悉的问题或事物，人们往往要咨

user1

图1协同过滤原理图１畅２　协同过滤算法的步骤近邻、产生推荐

［２］

一般说来，协同过滤算法可以分为构建用户档案、寻找最

三步。

询自己的朋友或是信任的人，根据他们的判断和看法和作出自己的选择。

协同过滤就是模拟这个过程，根据用户的行为和其他用户的行为（评分、评论、购买历史、浏览次数、在某一网页上的停留时间等）的比较，找出最相似的邻居，根据与之最相似邻居的兴趣或偏好预测出该用户的兴趣或偏好，以帮助其进行决策的一种算法。

图１显示了协同过滤的原理

［１］

１）构建用户档案　收集用户的评分、评价行为等，并进行数据清理、转换和录入，最终形成用户对各种项目的评价矩阵，如表１所示。其中：Ｒｉｊ代表第ｉ个用户Ｕｉ对商品Ｉｊ的评分。一般说来，０≤Ｒｉｊ≤５。分数越高，用户对该项目的认可度越高。

表１　用户评分矩阵

用　户ｕｓｅｒ１…

ｕｓｅｒｉ

ｉｔｅｍ１４５…／／

ｉｔｅｍ２５４…／／

商　品………………

……………／

ｉｔｅｍｎ－１

／５５…５

ｉｔｅｍｎ４／３…４

。其中用户１、２和３都对

项目Ａ、Ｂ和Ｃ表现出兴趣，如这三个用户都评价了电影Ａ、Ｂ和Ｃ，这种重合表明他们有相似的兴趣。因此，可以认为向用户２推荐Ｄ和Ｅ是比较可行的，因为Ｄ和Ｅ都被用户１和３所喜欢。

…ｕｓｅｒｎ

收稿日期：２００６唱１１唱２１；修回日期：２００７唱０２唱２９　　基金项目：国家自然科学基金资助项目（７０６７１０１６，７０２７２０５０）

作者简介：郭艳红（１９７７唱），女，博士研究生，主要研究方向为电子商务推荐系统、知识管理方法和技术（ｇｕｏｙａｎｈｏｎｇｍａｉｌ＠ｓｉｎａ．ｃｏｍ）；邓贵仕（１９４５唱），教授，博导，主要研究方向为电子商务方法和技术、复杂系统建模和方针、信息系统方法和技术．

・４０・计算机应用研究第２５卷

　　２）寻找最近邻居　在这一阶段，计算目标用户与数据库内各个用户的相似度，寻找相似度最高的作为最近邻居集。一般说来，可采用ｐｅａｒｓｏｎ相关度公式（式（１））、ｃｏｓｉｎｅ相关度公式（式（２））以及修正的余弦相关度（式（３））计算用户之间的相似度。

ｓｉｍ（ｉ，ｊ）＝ｕ∈钞Ｉｉ，ｊ

（Ｒｉ，ｕ－Ｒｉ）（Ｒｊ，ｕ－Ｒｊ）／

（

ｕ∈钞Ｉｓｉｍ（ａ，ｉ，ｉ）ｊ

（Ｒｉ，ｕ－Ｒｉ）２

ｕ∈钞Ｉ＝ｃｏｓ（ａ，ｉ）＝（ａｉｉ），／

ｊ

（Ｒｊ，ｕ－Ｒｊ）２）

（１）ｓｉｍ（ｉ，ｊ）＝‖ａ‖‖－Ｒｉ‖ｕ∈钞Ｉｉ，ｊ

（Ｒ（２）ｉ，ｕ－Ｒｉ）（Ｒｊ，ｕｊ）／

２

ｕ钞∈Ｉｉ

（Ｒｉ，ｕ－

Ｒｉ）ｕ钞∈Ｉｊ

（Ｒｊ，ｕ－Ｒｊ）

２

（３）

在式（２）的余弦相似性中，ａ和ｉ分别代表用户Ｕａ和Ｕｉ

的评分向量。在式（１）（３）中，Ｒｉ，ｕ和Ｒｊ，ｕ分别代表用户ｉ和ｊ对项目ｕ的评分；Ｒｉ和Ｒｊ代表用户ｉ和ｊ的平均评价值。用户ｉ和ｊ评价过的项目集合分别用Ｉｉ和Ｉｊ表示，两者的交集Ｉｉｊ＝Ｉｉ∩Ｉｊ。

３）预测阶段　通过最近邻居集产生推荐，传统的推荐算法一般有如下两种：

Ｐａ，ｙ＝钞ｕ∈Ｎ

ｓｉｍ（ａ，ｕ）Ｒｕ，ｙ／ｕ钞∈Ｎ

｜ｓｉｍ（ａ，ｕ）｜

（４）Ｐａ，ｙ＝Ｒａ＋ｕ∈钞Ｎａ

ｓｉｍ（ａ，ｕ）（Ｒｕ，ｙ－Ｒｕ）／ｕ∈钞Ｎａ

｜ｓｉｍ（ａ，ｕ）｜

（５）

其中：Ｐａ，ｙ代表目标用户对项目ｙ的预测值；Ｒｕ，ｙ代表目标客户ａ的最近邻居集内的用户ｕ对项目ｙ的评价。这里的目标用户ａ的最近邻居集由Ｎａ表示，所以ｕ∈Ｎａ。

式（４）和（５）的区别是后者考虑到了不同用户的评价风格问题。

１畅３　协同过滤算法是把用户与项目关联起来形成一个矩阵稀疏矩阵下的协同过滤算法分析

，由

于项目空间巨大，这个矩阵往往是极端稀疏的。据统计，电子商务系统中，用户评价过的数目往往不超过这个系统商品数目的１％。因此，表１中绝大部分是未知项。

在用户评分矩阵非常稀疏的情况下，通过相似度计算得到的用户最近邻居中，往往只有很少的用户对某个项目ｊ作出评价。如果只有一个用户对项目作出评价，式（４）和（５）就可推导如下：

Ｐａ，ｙ＝钞ｓｉｍｕ∈Ｎ（ｓｉｍａ，ｕ（）ａＲ，ｕ）Ｒｕ，ｙ／ｕ钞∈Ｎ

｜ｓｉｍ（ａ，ｕ）｜＝

ｕ，ｙ／

ｓｉｍ（ａ，ｕ）＝Ｒｕ，ｙ（６）

Ｐａ，ｙ＝Ｒａ＋ｕ钞∈Ｎａ

ｓｉｍ（ａ，ｕ）（Ｒｕ，ｙ－Ｒｕ）／ｕ钞∈Ｎａ

｜ｓｉｍ（ａ，ｕ）｜＝Ｒａ＋

ｓｉｍ（ａ，ｕ）（Ｒｕ，ｙ－Ｒｕ）／

ｓｉｍ（ａ，ｕ）＝Ｒａ＋（Ｒｕ，ｙ－Ｒｕ）（７）

　　这说明当最近邻居集内只有一个用户对某一项商品产生了非零评价时，最终的预测值将与相似度无关，只与这个用户的原始评价有关。但实际情况并非如此。

更进一步，如果这个向量代表的用户ｉ是许多乃至所有用户的最近邻居，那么对所有目标用户而言，对某一项目的推荐值都为这个用户的原始评价值。如果这个用户对某一项目的评价为５，那么所有用户都会根据这个用户的评价值得到为５的推荐值。这个项目将成为排行榜上的第一名（ｔｏｐｏｎｅ），这是不准确的。因为这个推荐仅仅是根据一个用户对这个项目产生的比较极端的评价；相反，如果这个用户对某一项目产生一个极端低的评价，如１，那么这个项目也就永远不能有机会推荐给其他人。这两种情况都是非常不符合实际情况的。上述两种情况由于数据集的巨大而时有发生。传统的推荐算法

在矩阵稀疏的情况下，严重影响了系统的推荐精度，降低了系统的可信度。

２２畅　１　改进的个性化推荐策略及算法

在矩阵稀疏的情况下个性化的推荐策略及原理

，传统推荐算法在一定程度上抹煞了

用户间的相似度对推荐结果的影响。尤其是当最近邻居集内只有一个用户对某个项目产生评价时，最后的推荐精度大大降低。

在现实世界中，人们常常咨询朋友或信任的人。他们的推荐往往是一对一的行为，即找到一个相似的用户，根据目标客户与相似客户的相似度产生对某一项目的预测值；再找到一个相似的用户，根据它们之间的相似程度产生一个预测值……，直到找完所有的相似用户；最后根据每个相似用户产生的预测值产生最后的预测值。这个过程如图２右侧所示；左侧部分为传统推荐算法的推荐过程。

最

邻居的评价

最近邻居的评价一对一预测虚拟评最分近邻居矩阵目标用户相似度

相似度传的均值推荐

个性化的推荐图2传推荐算法与新推荐算法的推荐过程２畅２　根据个性化推荐算法

２．１节的分析，个性化推荐算法可分为两个步骤，即一对一的个性化预测和综合相似度的最终预测。

根据一对一的原理，本文对传统的两种推荐算法进行改

进，即目标客户对某个项目的评价是根据最近邻居集内的每个邻居产生一个评价；最后根据所有对这个项目产生过评价的最近邻居再次引入相似度，产生一个综合评价。这个个性化的推荐算法如式（８）所示。

ｐａｉ，ａ）（ｐｉ，ｙ＝ｐａ＋ｓｉｍ（ｉ，ｙ－ｐｉ）　ｐｉ，ｙ≠００

ｐ０（８）

ｉ，ｙ＝

其中：ｉ∈Ｎ′，Ｎ为最近邻居集，Ｎ′彻Ｎ是所有对项目ｙ评价不为０的用户集；ｐｉａ

，ｙ代表目标客户ａ的最近邻居集内的用户ｉ对项目ｙ的预测值；ｐａ和ｐ分别代表目标客户和最近邻居集内用户ｉ的评价均值；ｓｉｍ（ｉ，ａ）代表目标客户ａ与最近邻居集内用户ｉ的相似度；ｐｉ，ｙ代表用户ｉ的对项目ｙ的评价值。

根据２．１节，在得知每个相似度用户对项目ｙ的预测值的基础上，综合各自的相似度可得最后的目标客户对项目ｙ的预测值为

ｐａ，ｙ＝［ｉ钞∈Ｎ′

ｓｉｍ（ｉ，ａ）×ｐａｉ，ｙ］／

ｉ钞∈Ｎ′

｜ｓｉｍ（ｉ，ａ）｜（９）

由于选取最为相似的邻居作为最近邻居集，而负的相似度值意味着两个用户很不相似。可以认为，在计算预测值时，所取的最近邻的相似度值都为正，即ｓｉｍ（ｉ，ａ）≥０，则有如下推导：

ｐａ，ｙ＝钞ｉ∈Ｎ′

ｓｉｍ（ｉ，ａ）×［ｐａ＋ｓｉｍ（ｉ，ａ）（ｐｉ，ｙ－ｐｉ）］／ｉ钞∈Ｎ′

ｓｉｍ（ｉ，ａ）＝

［ｉ钞∈Ｎ′

ｓｉｍ（ｉ，ｐａ）×ｐａ＋钞ｉ∈Ｎ′ｓｉｍ（ｉ，ａ）２×

（ｐｉ，ｙ－ｐａ）］／ｉ钞∈Ｎ′

ｓｉｍ（ｉ，ａ）＝ａ＋钞ｉ∈Ｎ′

ｓｉｍ（ｉ，ａ）２×（ｐｉ，ｙ－ｐａ）／ｉ钞∈Ｎ′

ｓｉｍ（ｉ，ａ）

（１０）

３３畅　１　实验结果与分析

为了验证算法的有效性数据集的筛选

，采用ＧｒｏｕｐＬｅｎｓ工作组提供的公

第１期郭艳红，等：协同过滤的一种个性化推荐算法研究・　　　４１・

开数据集（ｈｔｔｐ：／／ｍｏｖｉｅｌｅｎｓ．ｕｍｎ．ｅｄｕ／）。ＭｏｖｉｅＬｅｎｓ是由美国名尼苏达大学ＧｒｏｕｐＬｅｎｓ工作组研究人员开发的基于Ｗｅｂ的研究型推荐系统，它用于接收用户对电影的评价，并提供相应的电影推荐列表。自１９９６年推出以来，取得了很大的成功；目前该系统的用户已经超过４３０００人，用户评价的项目超过１６００个。本文也使用了ＭｏｖｉｅＬｅｎｓ提供的用户评分数据用于算法测试。

本文采用ＭｏｖｉｅＬｅｎｓ工作组提供的ｍｌ数据集。它由９４３个用户的１００００条１～５的评价数据组成。数据集有１６８２个电影项目，每个用户至少对２０个电影项目作出评价。

整个实验数据集进一步划分为训练集和测试集。为此，引入变量ｘ作为测试集占整个数据集的百分比。本文选用ｘ＝０．２，即在整个数据集中，训练集占８０％，测试集占２０％，即训练集为１０００００×８０％＝８００００条数据，测试集为１０００００×２０％＝２００００条数据。

为了保证实验的准确性，重复实验五次。每次测试集的数据都各不相同。为了度量整个数据集的稀疏性，引入稀疏度的概念，其定义为用户未评价数据占整个数据集的比例。本文所

用数据集的稀疏度为（９４３×１６８２－１０００００）／（９４３×１６８２）×１００％＝９３．７％

３畅２　ＲＳ度量标准

ｍｅａｓｕｒｅ）的评价方法一般有统计精度度量（ｓｔａｔｉｓｔｉｃｐｒｅｃｉｓｉｏｎ

决策支持精度度量方法中的平均绝对偏差（ｄｅｃｉｓｉｏｎｓｕｐｐｏｒｔＭＡＥｍｅａｓｕｒｅ（ｍｅａｎ）

［３，４］

ａｂｓｏｌｕｔｅ两种。

ｅｒｒｏｒ）和统计精度度量通过计算推荐数据与真实评价数据之间数值上的差别来衡量推荐结果的好坏。最常用的是ＭＡＥ法。设测试集内目标客户的推荐数据集为Ｐａ＝｛ｐａ，ｊǖｊ＝１…ｎ｝，目标客户的真实评价集为Ｒａ＝｛ｒａ，ｊǖｊ＝１…ｎ｝。对于每一个不为零的预测—评价对棟ｐＮ

ａ，ｊ，ｒａ，ｊ棡，都有ＭＡＥ＝钞｜ｐａ，ｊ－ｒａ，ｊ｜Ｎ。其中：Ｎ为测试集内目标客户ａ的预测值和真实评价值都ｌ／不为０的项目个数。ＭＡＥ越小，推荐精度越高。

由于ＭＡＥ方法简单、易于理解和操作，本文采用ＭＡＥ的方法度量预测的精度。３畅３　实验过程

１）相似度公式的选取

式（１）～（３）是协同过滤算法常用的三种度量相似度的公式。为了获得较好的实验结果，本文分别用这三种公式对测试集和训练集用户之间的相似性进行计算。值的分布如表２所示。

　　从表２中可以看出，相似度分布最差的是修正的余弦相似度。在０～１内，分布比较集中在［０，０．１５］，比例高达８７％，这说明用此公式计算出的用户之间的相似度过低。用这种公式得不到计算结果的占１．５％，计算结果小于等于０的占１１．２。之所以这样，是因为修正的余弦相似性公式的分子部分要计算两个用户之间共同评价过的项目。而在稀疏矩阵的情况下，两个用户共同评价过的项目非常少，分子的值非常小，甚至没有；余弦相似性的分母部分是两个用户共同评价过的项目空间，这部分值相对于分母而言显得过大。因此导致整个相似度公式的值非常小，与实际情况不相符。Ｐｅａｒｓｏｎ相关度和余弦相似度计算公式各有优缺点。余弦相似度公式可以得出所有用户

之间的相似度，但相似度值相对来说集中在［０，０．５］。Ｐｅａｒｓｏｎ相关性相似度公式由于在分子分母上计算的都是两个用户共同评价过的项目，相似度值相对来说分布较分散。从表中可看出［０，１］内都有分布。另一方面，由于要计算两个用户共同评价过的项目，ｐｅａｒｓｏｎ相关相似性公式得不出计算结果的为２畅３１％。

表2三种相似度值与个数分布表范公

式

余弦相似性修正的余弦相似性

0.1sim<00

4886665

7086601

706在以上分析的基础上，通过对余弦相似度和ｐｅａｒｓｏｎ相关相似度两种公式对的预测精度进行比较，结果如图３所示。

从图３中可以看出，不论应用哪一种传统的预测算法（考虑评价风格与否），余弦相似度都表现出比ｐｅａｒｓｏｎ相关相似度良好的预测精度。这是因为在稀疏矩阵项目空间下运算，两个用户共同评价过的项目数量很少，根据很少的共同评价过的项目来判断两个用户相似与否，可信度并不高。所以虽然表１的ｐｅａｒｓｏｎ相似度表现出良好的分布特性，但实际的预测值并不理想。另一方面，图３再次证明余弦相似度的有效性。

基于以上分析，笔者在以后的实验中，采用余弦相似性对用户的相似度进行度量。

２）实验结果及分析

为了验证本文算法的有效性，以式（４）和（５）作为对照，分别以余弦相似性和ｐｅａｒｓｏｎ相关相似性作为相似度度量标准计算其ＭＡＥ。最近邻居个数为１～３０，与本文提出的个性化推荐算法（ＰＣＦ）进行比较。实验结果如图４所示。其中：ＴＣＦ１代表传统的协同过滤算法且不考虑评价风格的影响，即式（４）所示；ＴＣＦ２代表传统的协同过滤算法并且考虑评价风格的影响，即式（５）所示；ＰＣＦ为本文提出的个性化协同过滤算法。从图中可以看出，ＰＣＦ的预测精度是最好的，并在不同邻居个数的情况下表现出良好的稳定型；ＴＣＦ１次之；ＴＣＦ２精度最差。

1.20.81

0.951

0.850.90.60.40.750.80.20.650.70

0.6

1357cosine蛳CF14cosine8最蛳CF2近邻12pearson个数16蛳CF120pearson蛳CF2

图4TCF1最9近邻1113151719

基于余弦TCF2

个数

相似性的PCF协同图3不同相似度的预测精度比较过滤推荐算法的精度比较另外，在邻居个数很少的情况下，本文的个性化推荐算法的精度与传统推荐算法相比有着明显的优越性。当选取的最近邻超过１２个时，本文算法的预测精度与传统（下转第５８页）

・５８・３　模拟实验

计算机应用研究第２５卷

４　结束语

ＳＮ算法。其基本思想就是在保证网络拓扑的边连通度大于１

本文通过深入的分析，结合计算机图论的知识提出了ＥＲ唱

为了测试该算法的性能，利用网络模拟器ＯＰＮＥＴ搭建网络拓扑结构对它进行模拟，并与标准洪泛算法和ＲＳＮ算法的性能进行比较。算法性能比较包括两个指标：网络洪泛ＬＳＡｓ的总数量和失效节点对网络拓扑的影响。模拟器随机产生的网络拓扑包含１５个网络节点、２５条链路。在限定３０ｓ内，任何一个节点随机地发生改变而洪泛ＬＳＡｓ，统计网络节点发送的ＬＳＡｓ的总数量。

由图４的模拟结果可以看出，ＥＲＳＮ算法发送的报文数量比标准的洪泛算法减少了４５％，比ＲＳＮ算法减少了３０％，大大减少了报文的发送数量，减轻了网络负载。

B伊10

ERSN2.5RSN

原始拓扑23

4

的情况下，尽可能地减少每个路由器的链路数目，从而减少需要洪泛的ＬＳＡｓ。因为算法减少的只是每个路由器发送的冗余ＬＳＡｓ的数量，所以不会降低洪泛的可靠性，但可以有效降低发

送的ＬＳＡｓ数量。它大大降低了链路状态路由协议给网络带来的负载。参考文献：

［１］ＨＵＩＴＥＭＡＣ．ＲｏｕｉｎｇｉｎｔｈｅＩｎｔｅｒｎｅｔ［Ｍ］．ＮＪ：Ｐｒｅｎｔｉｃｅ唱Ｈａｌｌ，１９９５：

１２７唱１４９．

［２］ＡＨＯＡ，ＬＥＥＤ．ＨｉｅｒａｒｃｈｉｃａｌｎｅｔｗｏｒｋｓａｎｄｔｈｅＬＳＡＮ唱ｓｑｕａｒｅｄｐｒｏｂ唱

ｌｅｍｉｎＯＳＰＦｒｏｕｔｉｎｇ［Ｃ］／／ＰｒｏｃｏｆＩＥＥＥＣｏｎｆｅｒｅｎｃｅｏｎＧＬＯＢＥＣＯＭ．［３］ＲＦＣ３６２３，ＧｒａｃｅｆｕｌＯＳＰＦｒｅｓｔａｒｔ［Ｓ］．

ＮｅｗＹｏｒｋ：ＩＥＥＥＰｒｅｓｓ，２０００：３９７唱４０３．

ADGIJECFH1.50.501

［４］ＳＨＡＩＫＨＡ，ＤＵＢＥＲ，ＶＡＲＭＡＡ．Ａｖｏｉｄｉｎｇｉｎｓｔａｂｉｌｉｔｙｄｕｒｉｎｇｇｒａｃｅ唱

05

10

15

t/s

20

25

30

KLｆｕｌｓｈｕｔｄｏｗｎｏｆＯＳＰＦ［Ｃ］／／ＰｒｏｃｏｆＩＥＥＥＣｏｎｆｅｒｅｎｃｅｏｎＩＮＦＯＣＯＭ．［５］ＮＡＲＶＡＥＺＰ，ＳＩＵＫＹ，ＨＯＮＧＹＴ．Ｌｏｃａｌｒｅｓｔｏｒａｔｉｏｎａｌｇｏｒｉｔｈｍｆｏｒ

ｌｉｎｋ唱ｓｔａｔｅｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌｓ［Ｃ］／／Ｐｒｏｃｏｆｔｈｅ８ｔｈＩＥＥＥＣｏｎｆｅｒｅｎｃｅｏｎ３５２唱３５７．［６］

ＣｏｍｐｕｔｅｒＣｏｍｍｕｎｉｃａｔｉｏｎｓａｎｄＮｅｔｗｏｒｋｓ．Ｂｏｓｔｏｎ：ＩＥＥＥＰｒｅｓｓ，１９９９：ＭＩＹＡＭＵＲＡＴ，ＫＵＲＩＭＯＴＯＴ，ＡＯＫＩＭ．Ｅｎｈａｎｃｉｎｇｔｈｅｎｅｔｗｏｒｋｓｃａｌａｂｉｌｉｔｙｏｆｌｉｎｋ唱ｓｔａｔｅｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌｓｂｙｒｅｄｕｃｉｎｇｔｈｅｉｒｆｌｏｏｄｉｎｇＰｒｅｓｓ，２００３：２６３唱２７１．版社，２００３：５６唱８２．

［８］谢政．网络算法与复杂性理论［Ｍ］．长沙：国防科学技术大学出版

社，２００３：１３９唱１５７．

［９］ＭＯＹＪ．ＯＳＰＦ：ａｎａｔｏｍｙｏｆａｎＩｎｔｅｒｎｅｔｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌ［Ｍ］．Ｂｏｓｔｏｎ：

Ａｄｄｉｓｏｎ唱Ｗｅｓｌｅｙ，１９９８：７２唱８３．

ｏｖｅｒｈｅａｄ［Ｃ］／／ＰｒｏｃｏｆＩＥＥＥＣｏｎｆｅｒｅｎｃｅｏｎＨＰＳＲ．Ｔｏｒｉｎｏ：ＩＥＥＥ［７］殷剑宏，吴开亚．图论及其算法［Ｍ］．北京：中国科学技术大学出

ＮｅｗＹｏｒｋ：ＩＥＥＥＰｒｅｓｓ，２００２：３９７唱４０３．

图3ERSN算法得到的网络拓扑图4模拟结果假设模拟器产生的网络拓扑的每个节点都随机失效。当任意一个节点失效时，网络拓扑被分割成的两个部分，统计网络中存在多少个这样的节点。由表１可以看出，标准洪泛算法和ＥＲＳＮ算法中不存在这样的节点：当这个节点失效时，网络被分割成的两个部分，从而使节点的链路状态数据库不能统一。ＲＳＮ算法中存在两个这样的节点：当这两个节点失效时，ＲＳＮ算法不能使节点统一它们的链路状态数据库，从而保证洪泛的可靠性。

表１　比较失效节点个数

算法标准ＥＲＳＮＲＳＮ

失效节点个数

０２０

［１０］ＲＦＣ１１９５，ＵｓｅｏｆＯＳ１ＩＳ唱ＩＳｆｏｒｒｏｕｔｉｎｇｉｎＴＣＰ／ＩＰａｎｄｄｕａｌｅｎｖｉｒｏｎ唱

ｍｅｎｔｓ［Ｓ］．

（上接第４１页）推荐算法（考虑不同用户之间的评价风格）的预定。下一步的工作是把该算法应用到具体的系统中，检验其实际运行的效果。参考文献：

［１］ＨＥＲＬＯＣＫＥＲＪ，ＫＯＮＳＴＡＮＪ，ＢＯＲＣＨＥＲＳＡ，ｅｔａｌ．Ａｎａｌｇｏｒｉｔｈｍｉｃ

ｆｒａｍｅｗｏｒｋｆｏｒｐｅｒｆｏｒｍｉｎｇｃｏｌｌａｂｏｒａｔｉｖｅｆｉｌｔｅｒｉｎｇ［Ｃ］／／ＰｒｏｃｏｆＣｏｎｆｅ唱ｒｅｎｃｅｏｎＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔｉｎＩｎｆｏｒｍａｔｉｏｎＲｅｔｒｉｅｖａｌ．ＮｅｗＹｏｒｋ：Ｓｐｒｉｎｇｅｒ，１９９９：２６３唱２６６．

测精度相比，保持了一致。当用户个数大于１２后，无论是哪种算法，预测精度都没有明显的变化。

通过分析可知，当用户的最近邻个数很少时，对要预测的项目往往只有更少的用户对之作出评价，即此时对这个项目的评价是极端稀疏的。本文算法由于充分考虑了用户的相似度对最后结果的影响，取得了较好的推荐结果。

４　结束语

在分析协同过滤推荐原理的基础上，笔者提出了一种个性化的推荐策略和算法，即在最近邻居集的范围内，根据每个最近邻居与目标客户的相似度，先对各个项目产生一个预测值；然后根据各自的相似度，在预测值的基础上产生一个综合的最后推荐值。实验证明这种算法在矩阵稀疏的情况下，可以取得很好的推荐精度，并且在不同邻居个数的情况下，结果比较稳

［２］ＧＯＬＤＢＥＲＧＤ，ＮＩＣＨＯＬＳＤ，ＯＫＩＢＭ，ｅｔａｌ．Ｕｓｉｎｇｃｏｌｌａｂｏｒａｔｉｖｅｆｉｌ唱

ｔｅｒｉｎｇｔｏｗｅａｖｅａｎｉｎｆｏｒｍａｔｉｏｎｔａｐｅｓｔｒｙ［Ｊ］．ＣｏｍｍｕｎｉｃａｔｉｏｎｓｏｆｔｈｅＡＣＭ，１９９２，３５（１２）：６１唱７０．

［３］ＳＡＲＷＡＲＢ，ＫＡＲＹＰＩＳＧ，ＫＯＮＳＴＡＮＪ，ｅｔａｌ．Ｉｔｅｍ唱ｂａｓｅｄｃｏｌｌａｂｏｒａ唱

ｔｉｖｅｆｉｌｔｅｒｉｎｇｒｅｃｏｍｍｅｎｄａｔｉｏｎａｌｇｏｒｉｔｈｍｓ［Ｃ］／／Ｐｒｏｃｏｆｔｈｅ１０ｔｈＩｎｔｅｒ唱２９５．

ｎａｔｉｏｎａｌＷｏｒｌｄＷｉｄｅＷｅｂＣｏｎｆｅｒｅｎｃｅ．ＮｅｗＹｏｒｋ：Ｓｐｒｉｎｇｅｒ，２００１：２８５唱

［４］邓爱林，朱杨勇，施伯乐．基于项目评分预测的协同过滤算法［Ｊ］．

软件学报，２００３，１４（９）：１６２１唱１６２８．