陈晋音,陈一贤,林 翔,吴洋洋

(浙江工业大学 信息学院,杭州 310000)

1 引 言

随着大数据技术的广泛应用,如何有效利用大数据来提高人们的生活品质已经引起了越来越多的关注.然而,过大的数据量往往会超出处理者的处理能力,即信息超载问题.推荐方法是解决信息超载问题的一个很好的解决方案,它通过收集用户的个性,习惯和偏好来生成相应的推荐信息.而传统的推荐方法如协同过滤、非负矩阵分解等方法具有无法充分挖掘用户或项目特征,受数据稀疏性影响大,当数据量增加时计算复杂度高等问题.

为了解决这些问题,许多学者提出了很多有效的方法.其中一个提高推荐准确度的方法是从评论数据中寻找更多的特征,而不是只使用用户对项目的评分信息.Wang等人[1]使用改进的情感字典来计算每个评论的情感分数,将加权调整后的平均值和修改后的平均值结合,以此计算每个项目的分数.这种方法本质上是用情感得分代替用户直接评分,忽略了评论中含有众多的项目特征.考虑到传统的基于矩阵分解的方法很难对用户解释矩阵分解得到的结果,Zhai等人[2]将语言主题模型与矩阵分解相结合,以发现用户和项目的隐藏特征.Wang等人[3]使用基于特征的加权非负矩阵分解算法来查找每个特征的最具代表性的句子,以此来总结每个特征.

近年来基于图结构的推荐系统受到越来越多的重视.在该模型中,用户和项目被认为是二分图中的节点,而它们间的交互信息被认为是连边.在这种表示下,推荐问题被转换为链路预测问题.最近,在用户-项目二分网络上已经出现了许多有效的推荐算法,例如物质扩散(MD)算法和热传导(HC)算法.MD算法[4]实质上是邻居用户在对象之间的资源重新分配方法.HC算法[5]像一个从项目到相邻用户并再次返回项目的热传导过程,它具有高度的多样性,但是精度较低.

本文提出了一种基于评论分析双层图的个性化推荐算法.该算法使用双层双向网络模型进行个性化推荐.本文的主要贡献如下:

1)提出了一种无监督的评论挖掘方法,相比传统的频繁项Apriori算法,该方法借助部分特征列表和word2vec对频繁名词项进行删减,具有更高的准确率和可扩展性.

2)提出了一种双层双向加权二分图模型,该模型配合聚类算法增加了算法处理大数据的能力并降低了数据稀疏性对算法的影响,从而获得更准确的推荐结果.

本文的其余部分的结构如下.第二节介绍了当下在评论挖掘、二分网络投影方面的相关工作.第三节描述了基于评论分析双层图的个性化推荐方法.第四节使用Yelp数据集和Amazon数据集进行实验,将本文的算法与其他推荐算法进行比较.第五节总结本文的工作.

2 相关工作

2.1 用户评论挖掘

大多数评论挖掘工作的重心在特征提取与情感分析两部分.做特征提取的先驱是 Hu等人[6],Hu等人使用Apriori算法提取评论中的频繁项,然后修建频繁项集来获得产品特征并寻找距离特征最近的形容词作为情感词.之后大多数的特征提取工作都具有提取频繁项的步骤,这种方法的基本假设是产品特征的出现频率相较其他词或短语将更高.还有一种寻找特征与情感词的方法是使用依存关系分析,Khan 等人[7]罗列一些句法关系作为语言模板,提取评论句子中与模板相匹配的短语,以此作为特征或情感词,Devasia等人[8]使用斯坦福依存关系分析工具提取句子中各个词之间的语法关系,针对不同的语法关系来提取不同词性的单词.这两种方法因为没有判别寻找到的名词或名词短语是否是真正的特征项,所以实际效果一般.Sharma等人[9]创建特征列表来寻找电影评论,虽然能比较准确的找出评论中存在的特征,但因为列表并不能全部枚举,所以仍然会有特征没有被提取出来.

现有的情感分析方法主要可以分为基于词典与基于机器学习两种方法.基于机器学习的方法包括使用朴素贝叶斯,支持向量机,递归深度模型和最大熵等,它可以被用于特定领域的情感分析中.基于词典的方法是指通过查询字典获取各个单词的情感得分,以此来判断句子倾向.Hu等人[6]选择多个已知情感方向的形容词生成种子列表,然后使用wordnet预测情感词列表中所有单词的情感方向.还有一些工作[9]借助SentiWordNet,得到每个单词的情感得分,以此来判断句子的情感倾向.由于借助情感词典可以快速的得到单词的情感得分,所以基于词典的情感分析算法在多个领域都有良好的表现.但是因为单词的情感得分受上下文关系影响,所以独立考虑每个单词的得分有其局限性.

2.2 基于二分图结构的推荐系统

近年来,许多系统将用户与项目间的关系建模为双向网络.Chang等人[10]应用监督学习的方法来预测维基百科二分网络中的隐藏连边.Zhang等人[11]将社区结构添加到用户-项目关系中,并将原始算法与双向网络中检测到的社区相结合,从而使建议更加个性化.Xia等人[12]提出了一种计算两个不同节点之间的链接概率的方法.并且还提出了一些基于核函数的方法来用于双向网络链路预测.

物质扩散算法[4]的实质是一种邻居对象之间的资源重新分配算法.基于物质扩散算法,Chen等人[13]在物质扩散模型中考虑项目间的相似性以提高准确率.Zeng等人[14]提出相似优先扩散机制,即加强或削弱与目标用户相似的用户的权重.Wang 等人[15]将相似性函数与二分网络相结合,基于相似性网络使得资源重分配过程更加个性化.

当下已经有很多研究工作已经证明基于聚类的推荐系统对于计算大规模数据集有效率高、扩展性强等特点[16].本文使用评论挖掘提取产品的多维特征,使用密度聚类提高处理大规模数据的能力以应对数据稀疏性对模型的影响,还提出了一种基于评分数据的不对称加权方法并将之用于双层双向网络模型,最后在双层图网络中使用物质扩散算法以实现个性化推荐.

2.3 物质扩散算法

对于不加权的二分网络,任意节点中的资源将平均分配给它的邻居节点.图1显示了这种分配的具体过程.如图1(a)所示,三个项目节点最初被赋予的权重分别为x,y和z.资源分配过程首先从项目到用户然后重新分配回项目.在每一步之后资源的分配情况如图1(b)和图 1(c)所示.经过这两个步骤之后,位于这三个项目节点中的最终资源分布用x′,y′ 和z′表示,其计算方法如公式(1)所示:

(1)

本文可以注意到公式(1)中的3×3矩阵有一个明显的特点,即每一列中元素的总和为1,由于每个项目节点连接到不同的用户节点,所以此矩阵是不对称的.

图1 二分网络中资源分配过程Fig.1 Illustration of the resource-allocation process in bipartite network

对于一个二分图网络G(U,B,L),其中L为连边集合,U={U1,U2,…,Um}和B={B1,B2,…,Bn}分别表示用户和项目集合.设f(bi)表示物品节点bi的初始资源,lip是大小为n×m的分配矩阵,由连边权重定义,k(bi)为分配矩阵lip的第i列元素的和.则经过第一步资源流动后,用户节点up的资源大小为：

(2)

(3)

接下来资源从U流向B,最终物品节点bi的资源为:

(4)

或者写做:

(5)

式中:

(6)

3 基于评论分析双层图结构的推荐

本文提出了一种基于评论分析双层图结构的推荐方法(RM-DGR),其主要步骤包括:

1)基于评论的文本分析结果和用户-商品(user-item)签到关系,构建用户和商品的特征并分别进行密度聚类.

2)构建用户簇和商品簇的双层双向二分图网络,在双层图上使用物质扩散算法实现个性化推荐.

该算法的框架图2所示.首先对评论进行词汇级情感分析,获得各项目的特征向量,再根据签到关系进行特征映射,获得各用户的特征向量,以此对项目和用户分别进行密度聚类.之后使用用户簇和项目簇构建二部图网络,在资源重新分配后,选中目标用户簇和得分最高的K个项目簇再次构建二部图网络,完成个性化推荐.

图2 RM-DGR框架Fig.2 Framework of the RM-DGR

3.1 词汇级情感分析

本节的目标是通过对评论进行情感分析构建项目的特征向量.注意到句子中的特征有隐式特征与显式特征之分,但是在评论中隐式特征出现次数极少[9],是故在此本文只考虑显式特征.本文中情感分析的流程可以分为以下五个主要步骤:提取频繁项、创建特征列表、将频繁项与列表中的特征相匹配、判断评论中句子的情感方向、针对每个特征总结所有评论.

3.1.1 特征提取

首先我们对评论文件进行词性标注并删除停用词,停用词通常是冠词、介词、连词,它们经常出现在文本中但却没有实际含义.这些停用词会对特征提取造成干扰.由于产品的特征绝大多数是名词或名词短语并且出现得较为频繁,因此本文提取评论中的频繁名词项作为候选特征.但是并不是所有频繁名词项都是真正的特征.为了删除这种非特征的频繁名词项,本文创建包含少量特征的特征列表并与word2vec配合使用.例如对于餐厅,本文可以如表1所示的列表.

创建的特征列表并不必包括太多的真实特征,只包含少量即可,接下来使用word2vec[17]对特征列表进行扩充.首先使用word2vec将单词转化为向量,选择余弦相似度来度量每一个名词频繁项与特征列表中单词的相似度,然后挑选出相似度大于阈值的名词频繁项作为特征.需注意的是,因为word2vec产生的词向量是基于文本的上下文关系,是故最终挑选出的特征未必都是名词.

表1 特征列表
Table 1 List of features

聚类用特征特征食物food,vegetable,fruits,fried,eat,meat服务service,delivery,order,waiter环境environment,atmosphere,air,music,space

算法1.项目特征提取

过程(FC,S,θ,δ):

foreachsiinS

foreach wordinPOS tagging

ifword is noun

extract the noun word

endif

Count the number of times each noun word occurred

Extract noun words whose occurrence number greater thanθ

foreach frequent noun wordn

fi.extend(n)

break

endif

endfor

endfor

3.1.2 情感分析

情感分析的目的是根据评论句子中情感词的情感倾向,判断句子的倾向从而将评论句子进行分类.情感词是指能够体现评论者情感倾向的单词.情感分析的方法有多种,本文中选用的方法是SentiWordNet,它在很多研究工作中被使用并且表现良好.

SentiWordNet是一个庞大的字典资源.它包含一个很大的文本文件,存有字典中每一个单词的用法与得分.借助SentiWordNet,对于每个单词的每种用法,本文都会得到与之相应的积极得分(PosScore)与消极得分(NegScore),将积极得分与消极得分相减,可以得到这种用法的得分.

Score=PosScore-NegScore

(7)

最终得分的取值在[-1,1]之间,大于0时该用法具有积极倾向,反之则具有消极倾向.

另外因为句子中表示情感倾向的词大多是形容词、副词、动词、名词,所以本文提取句子中除了特征外的形容词、副词、动词、名词作为情感词.在根据情感词计算句子的情感得分前,还必须考虑否定词的存在,例如以下句子:

“The food in the restaurant is not terrible”

在这个句子中not 和 terrible的得分均为负值,若是直接将句子中的所有情感词得分相加作为句子的得分,那么结果将不再准确.所以在计算情感得分时必须考虑否定词的存在.

本文中情感分析的步骤如下:

Step 1.寻找评论中含有特征的句子.

Step 2.对每个句子提取句子中除了特征外的形容词、副词、动词、名词作为情感词.

Step 3.如果句子中含有否定词,则标记否定词之后距离否定词最近的情感词标记优先级为形容词、副词、动词、名词.若之后没有情感词,则向前寻找情感词.

Step 4.使用SentiWordNet 得到每一个情感词的得分,对于被标记的情感词,它的最终得分为SentiWordNet得分的相反数.

Step 5.将句子中所有情感词的得分和作为句子的得分.

3.1.3 评论总结

在总结所有评论前,需要构建每条评论的特征向量,假设有共有n个用于聚类用特征,则构建评论R的特征向量MR的算法如下:

算法2.构建评论特征向量

过程(S,F):

InitializeMRto zero vector;

foreachsiinS

Calculate the score of the sentencefs

Extract the characteristics of the sentencef

foreachfiinF

iffinfi

endif

endfor

endfor

returnMR

基于评论对不同特征的情感倾向,可以得到一个评论-特征矩阵,如表2所示.

表2 评论-特征矩阵
Table 2 Review-feature matrix

(8)

其中R为评价项目j的所有评论,m为其个数.

3.2 针对个性化推荐的双层图结构模型

3.2.1 距离度量

在构建双层图结构之前,我们首先要对用户和项目分别进行聚类.考虑到簇的个数与形状的不确定性,我们采用Rodriguez 等人[18]提出的密度聚类算法,该算法能够自动确定聚类中心并在多个领域表现良好.

(9)

用户间的相似性由他们间不同的条目数量决定:

dist(U1,U2)=num(s1-s2)

(10)

式中:

(11)

(12)

(13)

3.2.2 推荐过程

推荐过程分为两部分:基于簇的个性化推荐和基于目标用户的个性化推荐.首先本文根据聚类结果建立用户簇与项目簇之间的第一层二分网络,节点间的权重由用户簇与项目簇之间的访问记录数定义.设P表示用户簇节点,I表示项目簇节点.在这种情况下,对于公式(3)中的lip与ljp,计算方法为:

lIP=lPI=∑i∈I∑p∈Paip

(14)

式中:

(15)

之后通过公式(2)～公式(6)和公式(14)～公式(15),我们可以得到基于簇的个性化推荐结果.

本文通过构建第二层二分网络来完成针对目标用户的个性化推荐.第二层二分网络使用目标用户所在的用户簇和上一层簇推荐中的资源最高的K个项目簇来构建.在第二个二分网络中,每一个节点表示一个用户或项目.考虑到用户对项目的评分范围为1～5,本文取3作为阈值来判断用户的情感取向从而得到两个二分网络,其一由积极连边构成,另一个则由消极连边构成.

在第二层二分网络中,用户p和项目i间权重定义为:

(16)

对于表示消极倾向的二分网络,lip<0.通过这个二分网络的个性化推荐可以表示用户对每个项目的不喜欢程度.最后,将两种二分网络中各项目节点资源之差作为最终结果,从而得到最终推荐列表.

3.2.3 复杂度分析

对于密度聚类算法[18],计算n维数据的局部密度ρ,距离δ和划分各数据点的时间复杂度均为O(n),所以聚类过程的时间复杂度为O(n).在双层图推荐过程中,因为第二层图结构中节点数量远大于第一层图的节点数量,所以仅考虑第二层图的时间复杂度.设目标用户簇中的用户数量为N′,项目簇中的项目数量为M′,则双层图推荐的时间复杂度是O(N′*M′).因为N′和M′远小于用户数N和项目数M,所以双层图结构有效地降低了MD算法的时间复杂度O(N*M).由于双层图推荐依旧需要存储全部信息,所以它的存储复杂度与MD算法相同,但是在第一层推荐后,我们可以删除我们大量不需要的签到信息,提前释放大量存储空间.

4 实验结果与分析

4.1 数据集

实验数据集是在第七届Yelp数据竞赛中使用的公共数据集.在本论文中,选择签到数量最多的三个州来测试本文的算法:拉斯维加斯,凤凰城,斯科茨代尔,其中每个用户至少含有5条访问记录.

除Yelp数据集外,我们还在Amazon数据集[19]上测试我们的算法.在实验中我们所选数据集为Amazon零食数据集,其中每个用户至少含有10条访问记录.

过滤后各数据集的数据分布如表3所示.

实验中本文依据访问时间8:2将数据集划分为训练集和测试集.实验环境为PC i7-4710MQ和8 GBs RAM.

表3 各数据集的数据分布
Table 3 Data volume of the selected datasets

州 用户数量餐厅数量签到数量拉斯维加斯160664068202435凤凰城5860258480820斯科茨代尔3076107138989亚马逊4323856986876

4.2 评价指标与方法

本文使用准确率、召回率、F值分析推荐结果.

(17)

(18)

(19)

在实验中使用的对比算法为IBCF 算法,UBCF 算法,NMF 算法和PMF 算法.除此之外,本文还将原算法与选择性删减后的原算法进行比较,以验证聚类和评论挖掘对算法的影响.接下来本文简单介绍这些对照算法.

DGR-Ⅰ:该算法直接使用所有的用户与项目构建二分网络.即通过单层网络直接完成个性化推荐.

DGR-Ⅱ:该算法项目间相似度距离的度量方法与用户相似,都是使用项目的标签信息进行度量.

4.3 结果与分析

实验中Word2vec训练数据为部分维基百科数据集,其中单词数量为15857306个,词汇数量是98331个.在实验中本文选择频繁项阈值θ为评论个数的1%,相似度阈值δ为0.6,使用的特征列表如表4与表5所示.

表4 Yelp数据集使用的特征列表
Table 4 List of features used in Yelp datasets

聚类用特征特征食物food,vegetable,fruits,cook,eat,bite,meat,entrees服务service,delivery,order,waiter,waitress,parking环境environment,atmosphere,air,spot,music,fountains

表5 Amazon数据集使用的特征列表
Table 5 List of features used in Amazon dataset

聚类用特征特征Snacktaste,flavor,product,food,fried,spicy,snack,meatPriceprice,cost,worthHealthhealth,weight,calorie,nutrient,caffeine,vitamin

最终挑选出的频繁项与特征信息如表6所示.我们可以看出使用频繁项集挖掘算法和word2vec删除了大量名词项并且将原本只包含少量特征的特征列表大幅扩展.

表7展示了RM-DGR与DGR-Ⅰ算法的运行时间,表明了双层图结构有效提高了MD算法的效率.

图3-图6展示了对于不同推荐长度k,各项指标的变化曲线.从图中可以看出RM-DGR的总体表现明显优于其他算法,尤其在拉斯维加斯区域内,各项指标优势较为明显.这表明评论挖掘与密度聚类的加入非常有效提高了算法在处理大规模数据时的准确率.对于Amazon数据集,由于该数据集中用户极少对同一家商户有访问记录,所以所有算法在该数据集上的表现效果均有所下降,但是通过对比我们仍能发现相较于其他算法,RM-DGR仍有明显优势.是故我们认为在推荐算法中加入评论挖掘、聚类机制确实有助于提高推荐效果.在凤凰城区域中,我们可以看到RM-DGR算法的准确率与F值两项指标对于其他算法有一定优势,但在召回率一项上略低于对照算法DGR-I算法.这可能是因为在凤凰城区域数据中,项目个数较少的用户所签到的餐厅可能比较特殊,它们归属于较小的餐厅簇.如此一来,这些餐厅在簇推荐过程中被删去,因为这些用户的签到餐厅个数少,所以这对召回率的影响较大,是故会出现准确率高于对照算法,而召回率却略低的情况.

表6 各数据集的名词项、频繁项与特征个数
Table 6 Number of frequent items and feature

州 名词数量频繁项数量特征数量拉斯维加斯83260375159凤凰城47147394163斯科茨代尔36584349147Amazon40731369167

图3 拉斯维加斯区域的实验结果Fig.3 Evaluation results comparing with other algorithms in Las Vegas

图4 凤凰城区域的实验结果Fig.4 Evaluation results comparing with other algorithms in Phoenix

图5 斯科茨代尔区域的实验结果Fig.5 Evaluation results comparing with other algorithms in Scottsdale

图6 亚马逊零食数据集的实验结果Fig.6 Evaluation results of controlled experiment in Amazon

表7 双层图结构对MD算法的影响(s)
Table 7 Effect of double-layer graph on MD algorithm(s)

州RM-DGRDGR-Ⅰ拉斯维加斯63.688.7凤凰城13.625.4斯科茨代尔4.713.7Amazon43.466.2

相比对照算法仅使用评分一项特征,本文使用评论挖掘分析多种特征可以更好地对项目进行建模.在图推荐前加入密度聚类,一方面使得图中节点数大量减少,另一方面经过簇推荐也过滤了大量明显不相干的项目,是故本文在各数据上可以取得更好的推荐效果.

5 总 结

本文提出了一种基于评论分析双层图的推荐方法.我们的目的是克服传统的个性化推荐算法的缺点:这些算法具有较高的时间复杂度,仅仅使用评分信息,不能有效地解决数据稀疏性等问题.我们的算法步骤如下:首先,通过词汇级情感分析和基于签到关系的映射,得到用户和项目的特征信息,然后分别对用户和项目进行聚类.接下来,根据聚类结果,采用基于双图结构推荐算法,对用户进行个性化推荐.在未来,我们的目标是寻找将文本信息嵌入图结构的更合适的方法并在模型中考虑社交关系,以此得到更合理的个性化推荐结果.并且,我们也想建立一个更完整的动态推荐系统.