正在进行安全检测...
发布时间：1714660676 来源：文档文库
小
中
大
字号：
第４０卷第５期 ２０１６年１Ｏ月 北京交通大学学报 Ｖｏ１．４０ Ｎｏ．５ ０ｃｔ．２Ｏ１６ Ｊ０ＵＲＮＡＬ ＯＦ ＢＥＵＩＮＧ ＪＩＡ０Ｔ０ＮＧ ＵＮＩＶＥＲＳＩＴＹ 文章编号：１６７３—０２９１（２０１６）０５—００７０—０６ ＤＯＩ：１０．１１８６０／ｊ．ｉｓｓｎ．１６７３—０２９１．２０１６．０５．０１２ 基于社交网络和协同过滤的微博好友推荐算法 汪毓铎，黄太波 （北京信息科技大学信息与通信工程学院，北京１００１０１） 摘 要：微博作为近年来用户数量较多的社交应用，其用户的信息压力也相对较大，推荐技术对于 微博用户的体验和推广有很明显的帮助．本文将针对微博平台的好友推荐进行研究，分别采用基于 社交网络分析和基于协同过滤技术的推荐算法．经过两种算法的实验对比得出结论：基于协同过滤 的好友推荐算法具有较好的性能，在推荐好友数量较多的情况下依然具有较高的综合评价指标，提 高了好友推荐的质量． 关键词：推荐技术；微博；社交网络；协同过滤 中图分类号：ＴＰ３９１ 文献标志码：Ａ Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｍｔ‘ ｃｒｏｂｌ’’ ｏｇｇｉ‘ ｎｇ ｒｔｅｎ｛ｆｒｉｅｎｄ：ｂａｓｅｄＩｓ ａ ｏｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｉｎｇ ａｎｄ ｃｏｌｌａｂｏｒａｔｉｖｅ ｆｉｌｔｅｒｉｎｇ ＷＡＮＧ ｄｕｏ，ＨＵＡＮＧ Ｔａｉｂｏ （Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｂｅｉｊｉｎｇ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ １００１０１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｓ ａ ｓｏｃｉａｌ ａｐｐｌｉｃａｔｉｏｎ ｔｈａｔ ｈａｓ ａ ｌａｒｇｅ ｎｕｍｂｅｒ ｏｆ ｕｓｅｒｓ ｉｎ ｒｅｃｅｎｔｌｙ ｙｅａｒｓ，ｔｈｅ ｉｎｆｏｒｍａ— ｔｉｏｎ ｐｒｅｓｓｕｒｅ ｏｆ ｍｉｃｒｏｂｌｏｇｇｉｎｇ ｕｓｅｒｓ ｉｓ ｒｅｌａｔｉｖｅｌｙ ｐｏｗｅｒｆｕ１．Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ｔｅｃｈｎｏｌｏｇｙ ｉｓ ｈｅｌｐｆｕｌ ｔｏ ｕｓｅｒ ｅｘｐｅｒｉｅｎｃｅ ａｎｄ ｐｒｏｍｏｔｉｏｎ ｏｆ ｍｉｃｒｏｂｌｏｇｇｉｎｇ．Ｔｈｅ ｐａｐｅｒ ｓｔｕｄｉｅｓ ｏｎ ｔｈｅ ｆｒｉｅｎｄ ｒｅｃｏｍｍｅｎｄａ— ｔｉｏｎ ｏｎ ｔｈｅ ｍｉｃｒｏｂ１ｏｇｇｉｎｇ ｐｌａｔｆｏｒｍ，ａｎｄ ｔｈｅ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｂａｓｅｄ ｏｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ａｎａｌｙｓｉｓ ａｎｄ ｃｏｌｌａｂｏｒａｔｉｖｅ ｆｉｌｔｅｒｉｎｇ ａｒｅ ｒｅｓｐｅｃｔｉｖｅｌｙ ｉｎｔｒｏｄｕｃｅｄ．Ａｆｔｅｒ ｅｘｐｅｒｉｍｅｎｔａｌ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｅ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ，ｉｔ ｃｏｍｅｓ ｔｏ ｃｏｎｃｌｕｓｉｏｎ ｔｈａｔ ｆｒｉｅｎｄ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｏｌ— ｌａｂｏｒａｔｉｖｅ ｆｉｌｔｅｒｉｎｇ ｈａｓ ｂｅｔｔｅｒ ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ ｈａｓ ｇｏｏｄ ｅｖａｌｕａｔｉｏｎ ｉｎｄｅｘ ｕｎｄｅｒ ｔｈｅ ｌａｒｇｅ ｎｕｍｂｅｒ ｏｆ ｆｒｉｅｎｄ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ．Ｉｔ ａｌｓｏ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ｑｕａｌｉｔｙ ｏｆ ｆｒｉｅｎｄ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ． Ｋｅｙ ｗｏｒｄｓ：ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ｔｅｃｈｎｏｌｏｇｙ；ｍｉｃｒｏｂｌｏｇｇｉｎｇ；ｓｏｃｉａｌ ｎｅｔｗｏｒｋ；ｃｏｌｌａｂｏｒａｔｉｖｅ ｆｉｌｔｅｒｉｎｇ 随着微博用户人数的增加，用户发布的微博量 更是不计其数，信息量的急剧增长导致人们越来越 难获取到自己真正感兴趣的内容，这就是所谓的信 的飞速发展，导致用户对于社交网络服务的需求也 呈现急剧增长的趋势．网络社交已经成为人们日常 生活中的重要组成部分．在国外著名的社交网站主 要有Ｆａｃｅｂｏｏｋ和Ｔｗｉｔｔｅｒ等；在国内著名的社交网 站主要有新浪微博、腾讯微博和人人网等．目前新浪 微博的用户总数量和用户活跃数量均为国内同类产 品之最，本文选择新浪微博作为好友推荐的研究 平台． 息过载效应＿１］．解决信息过载的手段主要有搜索技 术和推荐技术．相比搜索技术，推荐技术具有更好的 过滤效果、灵活性及推广能力，因此被广泛应用于各 大电商门户网站及手机ＡＰＰ，如国内的淘宝网、京 东网及国外的Ａｍａｚｏｎ等．互联网和移动终端设备 收稿日期：２０１６－０６—０２ 作者简介：汪毓铎（１９６０一），男，辽宁北镇人，教授．研究方向为数据采集与信号处理．ｅｍａｉｌ：ｗａｎｇｙｕｄｕｏ＠ｂｉｓｔｕ．ｅｄｕ．ｃｎ．
第５期 汪毓铎等：基于社交网络和协同过滤的微博好友推荐算法 ７１ 在微博社交网络中，用户获取自己感兴趣的用 社交网络分析是数据挖掘的一个分支学科，它 是一种链接分析技术，意在分析社交网络中的结构 和行为 ］．在社交网络上，学者们已经对利用社交关 系进行个性化推荐做出了各种尝试．ＳｐｅｒｔｕｓＥ叼等使 用了不同的相似度计算策略在在线社区Ｏｒｋｕｔ上 进行个性化推荐．Ｇｅｙｅｒ＿１。。等在网络社区上根据社 交网络信息实现的话题推荐被证实比基于内容的推 荐具有更好的效果． 户主要有以下几种方式：１）通过自己感兴趣的微博 内容来关注发布此内容的用户，但在海量的信息中， 通过这种方式来寻找自己感兴趣的用户并不容易； ２）通过设置不同特征条件对所有微博用户进行检 索，这种方式往往会返回大量的结果，使用户无法进 行甄别和选择；３）由微博运营平台推荐好友，目前主 要的推荐方式为给目标用户推荐其好友最近关注的 用户，这种推荐方式相对比较简单和盲目，其效果并 不理想．因此，如何从海量的微博用户中，挖掘出目 标用户感兴趣的用户，并精准地推荐给目标用户，是 微博推荐系统中的一个很有意义的研究内容．在微 博推荐领域，已有许多人展开研究并获得一定成果． 比如根据用户关注的群体来推测用户的偏好，或者 根据用户的评论和参与的话题来预测用户的关注 点，然后为其推荐可能感兴趣的用户及话题ｒ２。］． 在具有社交功能的应用场景里，用户推荐是很 重要的功能之一．目前微博用户的推荐方法主要有 以下几种：１）社交网络推荐一般都是通过对用户好 友的关注关系网进行分析并推荐，由于用户与其好 友的关系建立并不都是基于共同兴趣，因此推荐准 确率较低；２）基于内容的推荐不依赖于用户的评分 数据，而是根据用户的历史行为来判断是否对用户 进行推荐，在动态预测推荐方面具有优势；３）协同过 滤推荐是推荐系统中最常用的方法，通过用户之间 的评分数据来进行相似度计算进行推荐，具有良好 的操作性及推荐效果，被广泛应用于各大网站；４）混 合推荐将多种推荐算法应用于推荐系统中，可以使 不同推荐算法的优点结合起来进行推荐，具有良好 的推荐效果． 协同过滤是利用与用户兴趣行为相似的最近的 邻居的偏好信息向当前用户产生推荐结果，以解决 用户所面临的信息过载的问题 ］．协同过滤这一概 念最先由Ｇｏｌｄｂｅｒｇ［５ 等提出，并将其应用于基于协 同过滤的推荐系统Ｔａｐｅｓｔｒｙ中，这是一个邮件处理 系统，用来帮助用户从每天接收的大量邮件中筛选 和分类邮件．在协同过滤推荐算法中，有很重要的一 个步骤，就是根据目标用户对于目标项目的评价行 为找出与其兴趣相似的用户．尽管根据用户对项目 的评价行为确实可以在一定程度上找出兴趣相似的 用户，但这种做法却忽略了用户之间的社交关系 ］． 在社交网络上往往越靠近的用户越具有相同的兴趣 爱好ｌ７］，所以将用户之间的社交关系融人到协同过 滤算法当中来是非常有必要的，这就要利用到社交 网络分析的知识． 综上所述，社交网络分析对于个性化好友推荐 是一个非常重要的方法和影响因素．而协同过滤算 法则是推荐系统中经典且高效的推荐算法．本文作 者将采用基于社交网络分析和基于协同过滤两种算 法来对于微博平台上的好友推荐进行研究． １ 基于社交网络分析的好友推荐算法 基于社交网络分析的微博好友推荐算法．利用 目标用户的关注关系数据，统计出每个用户的关注 用户和粉丝用户数据，计算用户的相似群体，根据相 似度排序向用户做好友推荐． １．１算法步骤描述 算法的具体步骤描述如下：１）从数据集中提取 出所有用户关系的子数据集，并对子数据集进行预 处理；２）计算预处理后的子数据集中所有用户间的 相似性；３）对用户相似群体进行相似度排序，获取目 标用户的相似群体；４）取相似群体中相似度最高的 前Ｎ个用户的关注对象来对目标用户进行推荐． １．２相似性度量 社交网络中没有评分数据，但却包含着非常丰 富的用户社交关系数据．在微博的社交网络中，用户 关注的好友并不是在现实生活中熟悉的朋友，很大 程度上是因为对其某些言论的认同或者兴趣才建立 的社交关系．这种社交关系包括互相关注关系和单 向关注关系． 常见的用户相似性度量方法，如余弦相似度、 Ｐｅａｒｓｏｎ相关系数及修正的余弦相似度等，对于用 户项目的评分向量比较依赖．考虑到微博中并没有 用户评分机制，故这里采用不同用户节点的“出度” 和“人度”来进行相似度计算．这里的“出度”指的就 是目标用户的关注用户集合，“人度”指的是目标用 户的粉丝用户集合． 具体的相似性度量方法为：假设用户甜的出度 为ｏｕｔ（ ），人度为ｉｎ（ ）；用户 的出度和人度分 别为ｏｕｔ（ ）和ｉｎ（ ）．则用户 与用户 的相似性 ｓｉｅｒ（ ， ）的计算有以下几种方法． １）ｉｎ方法，计算公式为
７２ 北京交通大学学报 第４Ｏ卷 Ｉｍ（ ， ）一 （１） 分形式的用户一用户评分矩阵．矩阵的每一个行向量 表示对应用户对集合中所有用户的评分．则用户之 Ｊｉｎ（ｕ）Ｕ ｉｎ（ｖ） ２）ｏｕｔ方法，计算公式为…］ 间的相似度可以用余弦相似度进行计算．设Ｉ为所 ｉｍ（ ， ）一 兰 （２） 有用户的集合，向量“和 分别表示用户 和 在 ＪＯｕｔ（ｕ）Ｕ ｏｕｔ（ｖ） ３）采用ｉｎ方法和ｏｕｔ方法，计算公式为 ｓｉ 一 ㈦ ２基于协同过滤的好友推荐算法 协同过滤推荐算法分为两种，分别为基于内存 和基于模型．基于内存的协同过滤算法也分为两种， 分别为基于用户和基于项目口 ．本文研究的是微博 平台的好友推荐，故采用基于用户的协同过滤算法 来对目标用户进行好友推荐． 基于用户的协同过滤算法的原理为，根据当前 用户的邻居用户的偏好信息来对当前用户进行推 荐．所谓邻居用户，指的是对于某些项目的评分与目 标用户比较接近的用户．基于用户的协同过滤算法 可分为：表示阶段、计算邻居用户阶段和推荐结果生 成阶段３个阶段ｌ】 ． １）表示阶段．Ｃ（ｎ，ｍ）是一个 ×ｍ阶矩阵．协 同过滤推荐算法所要处理的数据形式就是与此类似 的用户一项目评分矩阵＿ｌ ，用下式表示为 Ｃ（ ，ｍ）一 （４） 式中： 表示用户数； 表示项目数；矩阵元素ｃ 表 示用户ｉ对项目Ｊ的评分；与喜欢程度成正比．评分 可以采用不同的分制，如用１和０分别表示喜欢和 不喜欢，或者用１０分制来度量喜欢的程度． 利用协同过滤算法在进行微博好友推荐时，表 示阶段的矩阵应为用户一用户评分矩阵，矩阵的每个 元素是由对应用户间的关注关系量化而来的评分数 据，比如，当用户ｉ和用户 的关系为相互关注时，对 应的矩阵元素ｃ 为１，否则 为０． ２）计算邻居用户阶段．计算邻居用户阶段是基 于用户的协同过滤算法中的关键阶段．在此阶段中， 算法通过计算不同用户关注关系的相似度来衡量不 同用户兴趣的相似度．相似度的取值范围为［～１， １］，其大小表示用户的邻近程度．因此相似度越接近 １表示用户兴趣越相似，即为邻居用户． 在表示阶段，已经将用户的关注关系量化为评 上的所有评分信息．于是，用户Ｕ和 之间的余弦 相似度表示为 ｓｉｍ（ ， ）一ｃ。ｓ（“， ）一 ∑ Ｒ Ｒ （５） √∑ Ｒ ｕｉ√∑引Ｒ 式中，Ｒ 和Ｒ 分别表示用户 对项目ｉ的评分和 用户 对项目ｉ的评分． ３）推荐结果生成阶段．在对用户的相似度进行 排序后即可得到目标用户的邻居用户集合．不同于 为相似用户推荐项目，这里并不需要进行目标项目 的评分计算．采用的推荐方式为给当前用户推荐与 兴趣最相似的Ｎ个邻居用户有互相关注关系的用 户． ３实验与结果分析 ３．１ 实验数据 本文实验数据来自于数据堂，数据集为６３ ６４１ 个用户的新浪微博数据集，包括微博信息、微博转发 关系、用户信息和用户好友关系等数据．本文主要利 用用户的互相关注数据来对用户进行相似度计算和 好友推荐，故实验采用的数据为用户好友关系数据． ３．２数据预处理 原始数据为两列用户的ｕｉｄ数据（每一个用户 拥有一个唯一的身份识别码），表示第１列用户关注 第２列用户，故需要对原始数据进行预处理和过滤 操作． １）在基于社交网络分析的推荐算法实验中，由 于微博用户存在好友数量异常的垃圾用户及粉丝过 多的认证用户，这些用户对于实验对象的一般性有 所影响，故在原有数据集中去除这部分用户．原始数 据中用户的关注关系数据共有１ ３９１ ７１８条，从这些 关注关系数据统计得到有关注的用户为６１ ９７２个， 有粉丝用户为２４ ８９０个．为了提高实验的准确性和 用户的普遍性，选取了关注人数大于２Ｏ且小于 ５００，粉丝人数大于２０人且小于５ ０００的用户作为 研究目标用户，最终的目标群体为３ １０４位用户． ２）在基于协同过滤的推荐算法实验中，为了提 高实验的精度，从用户数据集中选取了互相关注人 数大于ｌＯ的用户，共有１ ０４４位用户作为最终的研
第５期 汪毓铎等：基于社交网络和协同过滤的微博好友推荐算法 ７３ 究目标，与这一群体有关注关系的用户共有５ ３１１ 位．由于微博平台中并没有用户对于用户的评分，所 以本文将用户之问的相互关注关系作为评分来构建 用户一用户评分矩阵．在本实验中，则是根据１ ０４４位 用户和涉及到的５ ３１１位用户的互相关注关系来构 ０ ３５ Ｏ ３０ 咎ｏ ２５ 巴０．２０ 避０ １５ ０ １Ｏ 建一个１０４４×５３１１用户一用户评分矩阵．矩阵的某 一Ｏ Ｏ５ Ｏ 行为对应用户对于集合中所有用户的评分向量． 采用Ｔｏｐ—Ｎ推荐中的准确率（Ｐｒｅｃｉｓｉｏｎ）、召回 ３．３评价指标 ５ ｌ５ ２５ ３５ ４５ ５５ ６５ ７５ ８５ ９５ 推荐人数 １ ＳＮ’ｉｎ和ＳＮ—ｏｕｔ的准确翠与召回率对比 Ｆｉｇ．１ Ｐｒｅｃｉｓｉｏｎ ａｎｄ ｒｅｃａｌｌ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＳＮ—ｉｎ ａｎｄ ＳＮ—ｏｕｔ ｍｅｔｈｏｄ 率（Ｒｅｃａｌ１）和Ｆ度量（Ｆ－ｍｅａｓｕｒｅ）作为衡量算法的 评价指标口 ．通过基于社交网络的好友推荐算法（ｉｎ 法和ｏｕｔ法）和基于协同过滤的好友推荐算法进行 准确率、召回率和Ｆ值的比较来对算法进行评价． 准确率定义为 Ｐ一 ！ ｕＥＵ 渐上升，且两个指标最终都趋于平稳．由此说明，准 确率和召回率是一对相互制约的评价指标，而且推 荐人数增加到一定数量时，准确率和召回率都不再 变化，算法同时也达到极限． ２）给出了ＳＮ—ｉｎ方法和ＳＮ—ｏｕｔ方法的Ｆ值对 比如图２所示． 三 Ｉ Ｒ（ ）Ｉ （６） 召回率定义为 Ｒ一 ｕＥＵ ㈩ ｌ Ｔ（ｕ）Ｉ ｍ脚 式中： 表示所有用户合集；Ｒ（乱）表示推荐算法生 成的推荐列表；Ｔ（ ）表示用户实际的好友列表． 将准确率Ｐ和召回率Ｒ值融合成一个度量值， 就是Ｆ度量．其定义为 ㈣ ａ・ｆ １＿』 罄 式中，ａ为参数，当ａ—ｌ时，则认为准确率和召回率 的权重是一样的．常用的Ｆ度量为Ｆｚ和Ｆ ｏ－ｓ．Ｆｚ表 明召回率具有更高的权重，Ｆ 则表明准确率具有 更高的权重．在微博好友推荐场景下，推荐的准确率 图２ ＳＮ—ｉｎ和ＳＮ－ｏｕｔ的Ｆ僵对比 Ｆｉｇ．２ Ｆ—ｍｅａｓｕｒｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＳＮ—ｉｎ ａｎｄ ＳＮ—ｏｕｔ ｍｅｔｈｏｄ 从图２中可以看出，随着推荐人数的增加，Ｆ 应该比召回率更加重要，这时就应该调整参数ａ的 取值．本实验中取ａ一０．５． ３．４结果分析 值达到峰值后略微下降，最终趋于平稳．ＳＮ—ｉｎ方法 在平均推荐人数为５０人时，Ｆ值达到峰值０．１９３ ８． ＳＮ—ｏｕｔ方法在平均推荐人数为６０人时，Ｆ值达到 峰值Ｏ．１５２ ９．这里可以看到，ＳＮ—ｉｎ方法的Ｆ值始终 使用了两种推荐算法分别在数据集上进行实 验，并进行实验结果的对比．第１种是基于社交网络 高于ＳＮ—ｏｕｔ方法，所以根据微博用户的粉丝群体相 似度计算来进行推荐的效果要好于根据用户的关注 的好友推荐算法，其中采用了两种不同的相似度计 算方法（ｉｎ方法和ｏｕｔ方法）进行比较，在实验中分 别被简称为ＳＮ—ｉｎ方法和ＳＮ—ｏｕｔ方法．第２种是基 于协同过滤的好友推荐算法（简称ＣＦ方法）． 群体进行推荐． ３）给出了基于协同过滤的好友推荐算法（ＣＦ方 法）的准确率、召回率及Ｆ 度量与推荐邻居数的对 应关系，如图３所示．通过对数据集的计算，在不同 １）给出了基于社交网络的推荐算法的ＳＮ—ｉｎ方 法和ＳＮ—ｏｕｔ方法的准确率与召回率对比如图ｌ所 示． 邻居数的情况下，１ ０４４位用户分别可以得到长度 不同的用户推荐列表．为了便于进行不同算法的推 荐性能对比，实验中使邻居数不变，将所有用户的推 荐人数相加后做平均计算即可得到邻居数与实际推 图１中从准确率对比可以看出：１）ＳＮ—ｉｎ方法 的准确率和召回率均相对高于ＳＮ～ｏｕｔ方法．２）随着 推荐人数的增加，准确率逐渐下降，相反召回率则逐 荐人数的对应数据．如表１所示．
７４ 北京交通Ｏ ３５ 皿皿ｌ ）３Ｏ ＿－－、０－－ ：： Ｄ ２５ 回 ：： ：：：： 