0 引言

随着互联网的快速发展,社交网络因其快速传递信息的特性获得了人们的青睐,微博作为一种典型的社交网络,得到了广大用户的认可和关注。在新浪微博中,用户只能阅读关注人所发布的微博信息,而无法获得关注人以外的其他用户发布的其感兴趣的微博信息,因此如何帮助用户发现除关注人以外发布的有用信息,成为了当前研究的一个热点问题。作为用户服务的推荐系统不仅能为用户提供个性化的服务,而且过程简单、高效并被广泛使用。但是它也存在着缺点,冷启动^[1]问题一直以来是一个亟待解决的难题。例如在基于协同过滤的推荐算法中,由于没有新加入用户的历史偏好数据,导致了算法的冷启动问题;而在基于标签的推荐算法中,由于没有新加入用户的标签数据,导致了算法的冷启动问题。

目前,已有大量的学者利用群体智能算法来解决协同过滤推荐算法中的冷启动问题。王桐等^[2]通过构造一种基于时间因子的混合推荐模型,引入时间因子、用户和项目的信息到协同过滤推荐算法中,并利用柯西分布量子粒子群算法来搜索该模型中的最优参数组合进行推荐;徐雅斌等^[3]考虑用户特征、签到特点和位置爱好点的语义特征,将蚁群算法与改进的混合协同过滤算法组合起来对个性化的位置信息进行推荐,并在冷启动的环境下验证了该算法的性能;硕良勋等^[4]针对冷启动问题,提出了一种改进的最近邻协同过滤推荐算法,利用粒子群算法选择最近邻中最优的参数,并利用用户-项目评分矩阵计算项目-用户之间的相似度,获得项目-用户的最近邻并进行推荐。吴月萍等^[5]将推荐算法模拟成蚂蚁觅食的原理,并将聚类中心作为蚂蚁的食物源进行推荐,不但解决了新用户的冷启动问题,而且提高了推荐的准确率。通过上述研究发现,利用群体智能算法来解决协同过滤推荐算法中的冷启动问题,并对其进行推荐,取得了不错的推荐效果，因此可以考虑利用群体智能算法来解决基于标签推荐中的冷启动问题。

Karaboga等^[6]的研究表明,在群体智能算法中,人工蜂群(Artificial Bee Colony,ABC)算法的性能相当于甚至高于差分演化算法、遗传算法和粒子群优化算法。因此为了保证在解决冷启动问题的同时提高推荐算法的准确率,本文选择人工蜂群算法应用在微博推荐的问题上,提出了一种融合标签与人工蜂群的微博推荐算法(Recommendation algorithm combined Tag and ABC,TABC-R)。

1 标签数据的表示

用户标签作为描述自身特征和兴趣爱好的载体,已被用户广泛使用,因此运用标签集表示用户兴趣具有重要的意义。新浪微博规定每个用户只能为自己添加10个标签的描述信息,但新加入微博系统的用户往往没有为自己添加标签信息或者为自己添加很少的标签信息,这就需要能够找到一种方式为用户提取标签。设某用户发布的微博集合为D_i={d_i1,d_i2,…,d_im},m为用户发布微博的总个数。对于用户的标签集,本文采用TextRank排序方法^[7]在其发布的微博集合D_i中提取权重较大的TOP-10个关键词作为用户的标签集。

TextRank排序方法采用式(1)的方式计算每个词语节点的分数：

$S({t_i}) = (1 - d) + d*\sum\limits_{{t_j} \in E({t_i})} {{{{w_{ji}}} \over {\sum\limits_{{t_k} \in E({t_j})} {{w_{jk}}} }}} S({t_j})$

(1)

其中:d=0.85^[8]；t为词语节点的集合；E为边;对于给定的节点t_i,E(t_i)表示指向该点和该点指向的所有词语的集合;w_ji表示连接节点t_j和节点t_i的边的权重。为词语设置任意的初值,递归计算直到某个词语的分数收敛,收敛后每个词语都获得了一个代表该词语节点关键程度的分数。根据分数的大小取TOP-10个词语作为该用户的标签集,根据标签集便可进行标签权重、标签属性、标签属性权重和用户权重的定义。

定义1 标签权重。用户的标签集定义为t={t₁,t₂,…,t_i,…,t₁₀},每个标签权重的值S(t_i)为TextRank排序方法所得的TOP-10个词语节点的分数。

定义2 标签属性。用户的一个标签信息定义为: t_i=(t_i¹,t_i²,…,t_i^p),其中：i∈[1, 10],t_i^p 为标签t_i的第p个属性,该属性可以是标签名称、词性等。

定义3 标签属性权重。描述用户对标签属性的偏好值,定义为一个二元组(t_i,t_ri),其中：t_i为用户的第i个标签；t_ri为该标签属性权重值,该属性权重值为用户对标签t_i各个属性的偏好值之和。t_ri的计算方法如式(2)所示：

${{t}_{ri}}=\sum\limits_{n=1}^{p}{w_{i}^{n}\times }q_{i}^{p}$

(2)

其中:$\sum\limits_{n=1}^{p}{w_{i}^{n}=1}$表示用户对其第i个标签的属性偏好权重；q^p_i表示用户第i个标签的第p个属性的质量值。

定义4 用户权重。该权重u_r由两部分组成:用户社交权重和用户标签权重。

1) 用户社交权重:用于描述用户在社交网络中的重要程度,用户社交权重越大,在社交网络中越重要。

用户的社交网络包括关注用户following和粉丝用户follower,定义用户社交权重为u_r1,因此u_r1的计算方法如式(3)所示：

${u_{r1}} = {w_1} \times follower({u_i}) + {w_2} \times following({u_i})$

(3)

其中:w₁和w₂分别为粉丝用户和关注用户的权重分配值,为了避免u_r1的值过大,将该值归一化到[0,1]。

2) 用户标签权重:指某个用户的标签集在所有用户标签集中所占的权重,用户标签权重越大,该用户的权威就越大。定义用户标签权重为u_r2,u_r2根据用户标签集合中的每个标签的tf×idf值求和得到,计算方法如式(4)所示：

${{u}_{r2}}=\sum\limits_{i=1}^{10}{t{{f}_{i}}}\times id{{f}_{i}}$

(4)

其中:tf_i表示标签t_i在所有的微博文档中出现的次数；idf_i表示标签t_i在所有微博文档中的逆向文档频率。

根据上述两部分可知用户权重u_r的计算方法如式(5)所示：

${{u}_{r}}={{w}_{3}}\times {{u}_{r1}}+{{w}_{4}}\times {{u}_{r2}}$

(5)

其中:w₃和w₄为用户社交权重和用户标签权重的权重值。

2 改进的微博推荐算法 2.1 传统的人工蜂群算法

传统的人工蜂群(ABC)算法^[9-10]是一种启发于蜜蜂觅食行为的智能算法。该算法包含三个基本的组成要素:食物源、被雇佣的蜜蜂(引领蜂)和未被雇佣的蜜蜂(侦查蜂和跟随蜂)。两种基本的行为:为食物源招募蜜蜂和放弃某个食物源。具体的人工蜂群的步骤如下:

1) 初始化时期。

利用侦查蜂初始化代表食物源的向量x_i(i=1,2,…,N),N是食物源的数量,每个x_i都包含D个变量x_ij(j=1,2,…,D),利用式(6)对生成维数为D的N个食物源进行初始化。

${{x}_{ij}}={{x}_{j\min }}+rand(0,1)\times ({{x}_{j\max }}-{{x}_{j\min }})$

(6)

其中:x_jmin和x_jmax是x_ij变量的取值上下限；rand(0,1)表示0~1均匀分布的随机数。

2) 引领蜂时期。

引领蜂会根据其记忆中食物源的位置进行邻居搜索,寻找食物源附近更好的食物源。搜索公式如式(7)所示：

${{v}_{ij}}={{x}_{ij}}+{{\varphi }_{ij}}\times ({{x}_{ij}}-{{x}_{\phi j}})$

(7)

其中:φ_ij是一个区间[-1,1]内的随机数；x_φj是一个随机选择的食物源。当引领蜂找到一个食物源之后,会采用式(8)的方式评估其适应度值,并应用贪心法对食物源进行选择。

$fi{{t}_{i}}=\left\{ \begin{align} & \frac{1}{(1+{{f}_{i}})}\ \ \ \ \ \ \ \ \ \ \ {{f}_{i}}\ge 0 \\ & 1+abs({{f}_{i}})\ \ \ \ \ \ otherwise \\ \end{align} \right.$

(8)

3) 观察蜂时期。

引领蜂会向在蜂巢中等待的观察蜂来分享它们获得的食物源信息,观察蜂会根据这些信息进行一种随机的选择。 f_i被选中的概率p_i可用式(9)表示：

${{p}_{i}}=\frac{fi{{t}_{i}}}{\sum\limits_{i=1}^{N}{fi{{t}_{i}}}}$

(9)

当食物源x_i被一只观察蜂选中后,利用式(7)产生邻居食物源v_i,计算其适应度值。在雇佣蜂时期,用贪心法来作出选择。

4) 侦察蜂时期。

未雇佣蜂随机搜索食物源,称为侦察蜂。如果引领蜂通过尝试给定的次数之后,仍然未能提高解的质量,则引领蜂就变成为侦察蜂,其拥有的解就会被放弃。侦察蜂在搜索空间内利用式(6)来搜索新的食物源。

按照上述步骤,判断食物源的搜索次数Trial是否达到预先设定的阈值Limit,若是,算法结束；否则,转到步骤2)继续迭代。

2.2 适应度函数的构建

对于一条待推荐的微博采用中国科学院分词系统 ICTCLAS(Institute of Computing Technology,Chinese Lexical Analysis System)进行分词,分词后的词语与用户标签相同或者相似得越多,表明用户对该微博感兴趣的程度越大,因此该问题可以转换为对用户标签和微博中的词语进行同义词的判断。本文采用文献^[11]方法进行相似度计算,那么标签t_i和微博中词语t_j的相似度计算方法如式(10)所示：

$Sim({{t}_{i}},{{t}_{j}})=\sum\limits_{k=1}^{4}{{{\beta }_{k}}}si{{m}_{k}}({{t}_{i}},{{t}_{j}})$

(10)

其中:sim_k(t_i,t_j)分别为标签t_i和微博中词语t_j的第一独立义原、其他独立义原、关系义原和符号义原描述式的相似度计算方法； β_k是可调节的因子,且β₁+β₂+β₃+β₄=1。计算完相似度之后,可根据式(11)的方式来判断用户的标签集和一条待推荐微博中是否具有同义词。

$Sim({{t}_{i}},{{t}_{j}})=\left\{ \begin{align} & Sim({{t}_{i}},{{t}_{j}})Sim({{t}_{i}},{{t}_{j}})\ge \delta \\ & 0Sim({{t}_{i}},{{t}_{j}})<\delta \\ \end{align} \right.$

(11)

如果某个用户的标签集与该条待推荐微博中的词语进行相似度计算都满足Sim(t_i,t_j)<δ,则认为两者中没有同义词,用户对该条微博不感兴趣,因此不考虑该条微博的推荐问题;如果某个用户标签集与该条待推荐微博中的词语进行相似度计算具有Sim(t_i,t_j)≥δ的情况出现,则认为两者中具有同义词,那么便对这样的待推荐微博进行适应度值的计算,根据适应度值的大小决定是否对该条待推荐微博进行推荐,适应度值的计算方法如式(12)所示：

$fi{{t}_{i}}=\sum\limits_{i=1}^{10}{(Sim}({{t}_{i}},{{t}_{j}})\times (S({{t}_{i}})+{{t}_{ri}}))$

(12)

其中:Sim(t_i,t_j)表示某个用户的标签t_i和一条待推荐微博中词语t_j相似度的大小;S(t_i)表示标签t_i在 TextRank 排序中节点的分数,即标签权重;t_ri表示用户对标签t_i的偏好值,即标签属性权重。

2.3 微博推荐算法 2.3.1 对应关系

蜜蜂采蜜行为与微博推荐算法的对应关系如表 1所示。

由表 1可知每个食物源对应推荐算法中的一条待推荐微博,假设待推荐微博集合X=(x₁,x₂,…,x_n),其中：微博x_i可根据食物源的表示方式在本文中表示为一个3维的向量,分别为微博x_i中所包含的用户标签集t_i和微博x_i中词语t_j的相似度Sim(t_i,t_j),所包含的标签权重S(t_i)和标签属性权重t_ri的值,根据式(12)计算该待推荐微博的适应度值,用于人工蜂群中对于每个解的评价;食物源的质量对应推荐算法中待推荐微博的适应度值的大小;寻找及采蜜的速度对应推荐算法的求解速度;食物源最大质量对应推荐算法中推荐的最优微博,即该微博具有最大的适应度值。

2.3.2 推荐过程描述

一种融合标签和人工蜂群的微博推荐算法的具体推荐步骤如下所示。

第1步 初始化。

在开始时刻输入相关的参数,设定食物源个数=引领蜂的个数=跟随蜂的个数(SN),搜索次数的阈值Limit,最大迭代次数Max,设置当前迭代次数为cycle=0;

将用户权重u_r较大的前SN个用户初始化为引领蜂,其他用户初始化为侦察蜂和跟随蜂,并运用引领蜂用户根据式(6)初始化待推荐的微博。这样初始化的目的是因为用户权重u_r越大,用户在社交网络中具有越重要的位置,该用户的标签集中包含的标签也越符合大多数人的兴趣爱好,推荐给该用户的微博大家感兴趣的程度就越大,因此,本文根据用户权重u_r来初始化蜂群。

第2步 推荐算法的搜索策略。

①根据式(12)计算待推荐微博的适应度值,同时根据式(7)、(8)为引领蜂用户找到适应度值较大的一条待推荐的微博。

②根据步骤①可知,每个初始化为引领蜂的用户都已存储了一条待推荐微博的信息,将它与其他的待推荐微博的适应度值进行比较,根据适应度值的大小分为以下三种情况:

a) 如果引领蜂用户存储的待推荐微博的适应度值排名非常低,则引领蜂用户放弃自己当前所拥有的微博信息,成为侦查蜂,根据式(6)搜索新的微博;

b) 如果引领蜂用户存储的待推荐微博的适应度函数值大于其他的待推荐微博的适应度值,则该引领蜂用户保存自己已存储的微博信息,并将该信息作为选择供观察蜂用户使用,执行步骤③;

c) 其他情况下,引领蜂用户保存自己已存储的微博信息,且该信息不再供观察蜂用户使用。

③观察蜂用户根据当前所有待推荐微博的适应度值按照式(9)的方式选择自己喜欢的微博,同样利用式(7)进行邻域搜索新的微博,并按照贪心选择的方式选择新的适应度值较大的微博;

④若某条待推荐微博被搜索的次数连续超过Limit次并且没有新解,则执行步骤⑤；否则对应的引领蜂用户放弃该微博,并转换为侦查蜂用户,利用式(6)寻找新的微博信息;

⑤记录当前具有最优适应度值的微博;

⑥判断该算法是否达到了最大迭代次数MCS,如未达到则转至第2步；若达到了则转至第3步。

第3步 确定最优解,向用户进行推荐。

输出当前最优解fit_i,即Sim(t_i,t_j),S(t_i)和t_ri都具有最大值时的最优适应度值,并将具有最优适应度值的微博推荐给相应的用户。

具体的流程如图 1所示。

3 实验结果与分析 3.1 实验数据与预处理

对于中文微博的研究现在正处于起步阶段,因此目前还没有公认的数据集和标注集。本文使用的实验数据是通过新浪微博API采集的2016年2月21日晚发布的微博数据,去除部分没有意义的微博(如微博内容少于5个字的微博),保留有意义的微博作为待推荐微博；并对待推荐微博进行处理,如去除表情符号、@某人的字样和URL链接等噪声信息,采用中国科学院的分词系统进行分词,并且去除停用词、高频词和低频词等词汇。

同时在新浪微博中随机采集400名用户,以及每位用户发布的所有历史微博信息,将这些信息作为一个大文档进行预处理,采用第2章中的TextRank排序方法,为每个用户生成自己的标签数据集。同时将这400名用户平均分成4组,D1、D2、D3和D4,在每组中选择40名用户作为测试集。

为了评价推荐微博的有效性,邀请了10位合适的志愿者对推荐出的微博数据进行标注。在每组测试集中,他们首先根据测试用户的标签数据集选择与自己偏好一致的4位用户,然后代替这4位用户对推荐结果进行标注。标注的形式采用评分制的形式标注为1~5分,其中：1分表示特别不喜欢,2分表示有些不喜欢,3分表示既不讨厌也不喜欢,4分表示有些喜欢,5分表示特别喜欢。

3.2 评价指标

本文使用的评价算法性能的指标为准确率Precision和召回率Recall^[12],令I(u_i)为本文算法为用户推荐的微博列表,D(u_i)为测试集中用户评分在4分以上的微博列表,准确率和召回率的计算公式分别如式(13)和式(14)所示：

$precision=\frac{\sum\nolimits_{{{u}_{i}}\in U}{\left| I({{u}_{i}})\cap D({{u}_{i}}) \right|}}{\left| I({{u}_{i}}) \right|}$

(13)

$recall=\frac{\sum\nolimits_{{{u}_{i}}\in U}{\left| I({{u}_{i}})\cap D({{u}_{i}}) \right|}}{\left| D({{u}_{i}}) \right|}$

(14)

其中：U为进行推荐的用户集合。

3.3 实验结果与分析 3.3.1 参数设置

搜索次数Limit表示食物源质量连续搜索Limit次没有提高将被放弃,该参数设置的优劣直接决定算法的全局搜索能力。实验将群体规模设置为50,最大迭代次数MCS为2000,并且搜索次数Limit的取值范围设定在10~50,并以10为增倍的5个取值,即Limit∈{10,20,30,40,50}。为了给Limit设置一个合理的值,分别在4组数据集上进行实验。针对搜索次数Limit取不同的值在4组数据集上运行10次,10次运行结果的平均值作为搜索次数不同时的准确率和召回率。图 2~3为搜索次数Limit对于准确率和召回率的影响。

由图 2~3可看出,在数据集D1、D2、D3和D4上，当Limit<30时，随着搜索次数Limit的不断增加,本文算法的准确率和召回率也随之增加；但当Limit>30时,准确率和召回率则随着搜索次数的增加而不断减少。因此搜索次数Limit=30时具有较好的准确率和召回率,所以本文实验中Limit设为30。

3.3.2 对比实验

为验证本文提出的TABC-R算法的有效性和准确性,将TABC-R算法和基于标签的推荐(Tag-based Recommendation,T-R)算法及基于人工蜂群的推荐算法(Recommendation algorithm based on Artificial Bee Colony,ABC-R)在本文数据集上进行对比实验。T-R算法是根据用户标注的标签作为兴趣爱好实现相应的推荐功能。ABC-R算法是根据人工蜂群算法中的适应度函数的大小向用户进行推荐。表 2给出了三种方法在4个用户数据集上的对比实验结果。

通过表 2可知,TABC-R算法在用户数据集D1、D2、D3和D4上的准确率和召回率均高于T-R算法和ABC-R算法。TABC-R算法与T-R算法相比,T-R算法虽然也考虑了用户标注的标签信息,但是它并没有考虑新加入用户的标签信息,存在新用户的冷启动问题;而TABC-R算法利用TextRank方法解决了新用户的冷启动问题,从而准确率和召回率平均提高了1.5%和1.22%。TABC-R算法与ABC-R算法相比,同样是都使用人工蜂群算法来提高推荐的准确率问题,但是ABC-R算法在准确率和召回率均有一定的提高。TABC-R算法与ABC-R算法相比,同样是都使用人工蜂群算法来提高推荐的准确率问题,但是ABC-R算法在准确率和召回率上仍然小于TABC-R算法,说明TABC-R算法在提高推荐算法的准确性上具有一定的有效性。因此,TABC-R算法不但能解决基于标签推荐算法的冷启动问题,而且对提高推荐算法的准确性也具有一定的效果。

4 结语

本文算法主要是通过模拟蜜蜂采蜜的行为向用户推荐其感兴趣的微博,首先算法根据标签信息构造人工蜂群算法中的适应度函数,然后利用人工蜂群的搜索策略,搜索具有最优适应度值的微博进行推荐。同时本文方法具有一定的通用性,不仅能够应用在以新浪微博为基础的推荐场景中，而且能够应用在其他的推荐场景中,例如应用于某些新闻网站中为用户推荐其感兴趣的新闻。在利用人工蜂群算法进行推荐的过程中,速度也可作为判断算法有效性的标准,因此下一步可以考虑提高搜索速度的问题。