基于网络分割聚类的标签语义规范化推荐算法

叶 婷 曹 杰

(南京财经大学信息工程学院 江苏 南京 210046)

基于网络分割聚类的标签语义规范化推荐算法

叶 婷 曹 杰

(南京财经大学信息工程学院 江苏 南京 210046)

传统的推荐算法多以用户评分数据计算用户的兴趣偏好以及资源相似度，对稀疏数据以及新用户的推荐质量较低。考虑到用户标签数据的随意性和语义模糊性，提出基于标签网络分割聚类的语义规范化方法并建立基于规范化标签的用户兴趣模型。该模型能在不改变用户兴趣的前提下有效降低用户标签兴趣模型的向量维数，并能避免分析标签语义的复杂过程，且能根据用户自身的理解来获取用户兴趣。最后将标签兴趣模型应用到推荐算法中。通过与经典的推荐算法进行比较，验证了该算法能有效缓解数据稀疏性、推荐冷启动问题，提升了推荐结果的准确性，能获得更好的推荐效果。

标签 语义规范化 推荐算法

0 引 言

随着计算机科技的迅猛发展，社会的进步已经离不开信息网络，人们获取信息的方式以及沟通交流的方式也在不断增多，互联网已经极大地改变了人们的生活。然而，网络中充斥着复杂多样的信息，人们享受着足不出户便可以搜索丰富网络资源的同时，也不得不忍受“信息过载”带来的生活上的不便。传统的搜索引擎技术已经不能满足用户的搜索需要，因此个性化推荐技术孕育而生。个性化推荐系统可以挖掘分析用户的历史行为数据，并构建用户的兴趣模型从而智能地从海量信息资源中筛选出用户需要的资源推荐给用户，从而很好地缓解了信息过载问题[1]。然而，推荐系统自身也存在一些弊端，主要表现为系统的数据稀疏性问题、冷启动问题等，这些缺陷会一定程度上影响推荐的效率以及准确率。

在个性化推荐系统中灵活地利用用户自定义标签的特性，使推荐系统的研究迎来了一个崭新的时代。因为标签系统的标签是由用户自主标注的，所以标签不仅包含资源的特征属性，还可以反映出用户的兴趣和认知偏好等信息。同时，利用标签信息进行用户的兴趣模型的构建，可以提高用户兴趣模型的贴切度与准确度。其次，通过分析标签的语义信息可以挖掘出用户对于资源的喜好，以方便找到与目标用户有相似喜好的用户集群，从而可以更加精确地推荐其感兴趣的项目集合给该用户。然而随着标签应用越来越广泛，标签中出现的弊端也越来越明显，由于标签的自主性，存在标签的语义表达概念模糊，并且不同用户认知也存在差异，这导致其表达的语义不准确，同时用户可能在输入标签时不够严谨，也导致大量噪声标签的存在。目前，不少学者都进行了相关的学术研究。Wei等[2]通过用户标注在资源上的标签信息构建用户的偏好主题模型，并结合用户的评分信息以增强推荐效果。Martins等[3]利用正面和负面用户反馈迭代选择输入标签并结合遗传算法策略来学习推荐函数，从而有效地解决冷启动问题。Gan等[4]提出构建对象-用户-标签异构网络，并采用随机游走算法与重启模型以将关联的强度分配给候选对象，从而提供用户优先查询对象以加强推荐。Cao等[5]融合混合型协同过滤算法提出Web服务的双向推荐机制，该机制既可以为用户推荐感兴趣的Web服务，也可以为服务者提供潜在用户。Kim等[6]结合用户的评分信息将资源分为积极项目和消极项目，分别计算用户的兴趣模型。Xu等[7]提出SemRec系统，利用层次式聚类方法将经常共同出现的标签放在同一类簇并结合其语义信息以进一步增强推荐性能。Xie等[8]通过标签向量来表示用户和资源，然后求用户和资源的相似性匹配度再进行相关性推荐。

由于用户标签数据的稀疏性、异构性等特点，推荐算法的正确率往往不尽如人意。以上研究大多只是考虑标签的频数信息而没有很好地利用标签丰富的语义信息来丰富个性化模型。为此，本文提出基于网络分割聚类的标签语义规范化方法，用语义明确且能较好地表达一类资源主题的规范化标签替代用户的随意标签，构建个性化推荐的用户规范化标签兴趣数据模型并应用到推荐算法中。

1 基于外部词库的标签语义关联构建

用户自定义标签具有很强的自主性和无约束性，且网络中标签数据的稀疏性使其不能很好地被利用到推荐系统中。由于网络中的标签繁杂多维化，想要充分利用标签所表达的丰富的语义信息，就需要借助外部词库建立标签之间的语义关联。因此提出了基于英文维基百科的外部词库构建标签的语义关联，利用标签的语义特征为后面的研究做好准备工作。

1.1 Word2vec的语义模型训练

Word2vec是Google于2013年新开发的一款基于深度学习的工具[9]。它基于特定的语料库，利用优化后的训练模型得到词语的包含了自然语言中的语义和语法关系的向量表达形式，为自然语言的研究开辟了一个新的领域。在向量空间模型中，做两个向量的相似度(向量距离/夹角)运算，其中模型中向量的相似度即代表两个词之间语义的相似度，换句话说，就是两个词在同一个语义场景出现的概率，词向量的算术运算则是计算机的“命辞遣意”。词向量是词性特征常用的表达方式，因为它具有丰富的语义信息。词向量共400维，单位维上的值表示包含特定的语法和语义上表述的特性。本部分采取分布式的表现形式，它是一个低维的、稠密的实值向量。其中每一维表现了单词的一个潜在词性特征，该特性蕴含了丰富的语义和句法特征信息。

通过离线深度学习训练，形成知识库，支持数据分析功能的词之间的相似度计算。本部分采用英文的维基百科数据作为训练模型的源数据，维基百科是目前知识库增长速度最快且规模最大的百科全书，有250万多篇的文章和不计其数的投稿人,其数目庞大的网络入口、互相参考的网络以及以树为主体的图结构层次的分类能提供丰富的精确定义的语义知识[10]。

1.2 基于维基百科的标签语义关联的构建

在众分众类的标注系统中, 用户标注行为较为自由，通常表示相同意思但标注的标签往往是同一词根的不同演变形式，包括英文标签的单复数、大小写、时态等各种问题。为了减小标签构建Word2vec的计算复杂度，本文对英文标签首先进行两步预处理缩减一定的标签：对非英文字符以及大写字母等进行剔除或替换，并利用词根提取算法处理单复数并提取词根,最后进行比较以及合并重复标签。

本文基于外部词库训练语义模型，形成结构化的语义词典，对于任意输入的英文标签可以给出其语义训练模型中的词向量表示。其中，词与词之间的相似度可以表示为两个词对应的Word2vec的语义空间上的距离，极大地简化了词与词之间相似度的计算，以构成标签的语义关联。

2 基于网络分割的标签语义规范化推荐算法

社会标签系统中用户自定义标签可以根据自己的认知和理解随意进行标签标注，具有很强的无约束性和自由性，标签自身真正的含义不一定能精确表达用户真正的意图，因此标签存在语义模糊、歧义性以及标签滥用等较严重的语义问题。针对标签存在的语义问题，本文提出一种基于加权网络分割的标签聚类规范化方法，即用户产生的繁杂随意标签用与其相似且核心度高的规范化标签代替，在不改变用户本身兴趣爱好的前提下以期得到更加精确的用户兴趣模型。本文首先构建基于融合相似度的标签共现网络，并提出了衡量标签节点核心程度的计算方法。该聚类算法基于标签节点的核心度，并结合标签融合相似度来进行网络分割，将与核心节点相似的节点划分成一个子网，同时该类簇的聚类中心即可理解为该类簇的核心节点。首先定义如下三个概念以便于后面的研究：

定义1基于融合相似度的标签共现网络定义为一个加权网络G=,其中V代表标签集合，E表示边集合，W表示标签相似度集合。网络节点之间的边表示这两个标签共同标注过至少一个资源，且边的权值表示这两个标签的融合相似度。

定义2标注矩阵定义为m×n矩阵A=(Aij),其中Aij表示标签i和在资源j上标注的次数，即标签频度。

定义3关联度矩阵定义为m×n矩阵B=(Bij)其中Bij表示标签i与资源j的关联程度，其关联程度的计算借鉴TF-IDF思想并进行改进，可以记为TagBasedTFIDF：

(1)

其中:R(ti)表示标签ti标注的资源总数。

2.1 标签相似度计算

定义4规范化标签定义为用户公众认可的由用户产生的表达概念明确的标签，各规范化标签之间的相似度为0或可以忽略不计。将用户定义的标签用语义规范化的标签数据表示，其能够有效地缓解标签表达概念不精确、语义模糊等问题。标签相似度计算由下列属性确定。

(1) 标签资源共现相似度：标签a和标签a′的资源共现相似度定义如下：

(2)

其中:对于标签a，令N(a)为有标签a的物品集合，na,i为物品i打上标签a的用户数，本文通过如上余弦现相似度公式计算标签a和标签b的资源共现相似度：

(2) 标签词向量语义相似度：标签a和标签b′的语义相似度即它们对应Word2vec的余弦相似度。定义如下：

(3)

(3) 标签融合相似度:

(4)

其中:λ为调节权重。线性融合标签关于用户数据的资源共现相似度和关于标签的词向量语义相似度，得出用户数据中标签与标签之间的融合相似度，作为聚类的相似度计算公式。

2.2 标签核心度计算

标签的核心度用来衡量该标签在标签网络中的核心程度，主要由标签融合相似度、标签主题度综合计算。

定义5标签主题度用于衡量一个标签能否很好地表现一类资源主题。如果该标签所表示的资源都较为相似则可以认为这个标签能够较好地表示一个资源主题。我们用Ct表示被标签t标注的资源均值中心，由式(5)计算。其中R(t)表示标签t所表示的资源总数，资源ri由关联度矩阵B中的列向量表示。

(5)

标签的主题度由标签标注的资源中心Ct与该标签标注的所有资源之间的平均余弦相似度计算：

(6)

标签的核心度计算公式如下：

(7)

其中:t′表示标签共现网络图中与标签t相连接的标签。

2.3 算法流程

基于网络分割聚类的标签规范化推荐算法：

输入：用户—规范化标签—资源数据{U,T,I}，聚类数目K,推荐资源个数N。

输出：目标用户u的Top-N推荐集。

第1步计算标签之间的融合相似度，构建基于融合相似度的资源共现标签网络。并计算标签网络中每个标签节点v的核心度。

第2步将节点按核心度降序的顺序插入链表L。

第3步取出链表首节点即核心度最高的标签节点，并在标签网络中逐个判断其邻接节点的相似度是否大于该邻接节点与其任何节点的相似度，如果是则将该点与首节点划为一个类簇，并把该节点从链表中删去。

第4步得到类簇以首节点为核心的规范化标签，并从L中删除。

第5步重复第3步、第4步，直到链表L为空或聚类数目达到K，停止聚类。

第6步得到各个类簇的聚类中心即规范化标签，以及用户的自定义标签集合，将用户自定义标签替换成其所在类簇的聚类中心(规范化标签)，形成新的用户—规范化标签—资源数据{U,Ts,I}。

第7步计算标签基于TF-IDF的权重构建用户的兴趣模型并应用到协同过滤的推荐算法。取前N个资源组成Top-N推荐集合recommend-list={i1,i2,…,iN}并输出。算法的伪代码见算法1。

算法1基于网络分割的标签聚类规范化的推荐算法

输入：用户-规范化标签-资源数据Q={U,T,I}，聚类数目K,推荐资源个数N

输出:目标用户u的Top-N推荐集recommend-list

1:creat the resource co-occurrence label network based on fusion similarity

2:for each vertexv∈Vdo

3: computeCore(v)

4: end for

5: insert allCore(v) by ascending order into ListL

6: while (Lis not empty or number of clusters!=K)

7: select the first vertexviinL

8: for each adjacent edgevjofvido

9: ifeij> each adjacent edge ofvjofvido

10: assignvjto the cluster withvi

11: deletevjfromL

12: end if

13: end for

14: deletevifromL

15: obtain a cluster with label=vi16: end while

17:Transfor the User tags to the normalized tagsvi

18: for all useruinQdo

19: use TF-IDF compute the weight

20: produce the user intrest model

21: find the KNN neighbors

22: take the top-N item

23: end for

23:outputrecommend-list={i1,i2,…,iN}

2.4 标签规范化结果展示

在MovieLens数据集中，通过网络分割聚类的标签规范化方法，将数据集中用户自定义标签与规范化标签形成关联。 经过网络分割聚类的规范化标签及与其聚类为一个类簇即相映射的自定义标签数据部分展示如下，并根据这些自定义标签与其对应的规范化标签之间的融合相似度按大到小的顺序排列，实验结果见表1。

表1 语义规范化标签与用户自定义标签

3 规范化标签的应用与实验结果分析

3.1 数据集

为了验证本文算法的有效性，本文采用MovieLens和Delicious两组数据集[11]，具体数据集集合见表2。本实验将语义规范化的标签并结合TF-IDF算法实验采用5折交叉验证，每次将数据集随机选取80%数据为训练集，剩余20%数据为测试集，对五次结果取平均作为最终结果。

表2 数据集结构

3.2 度量标准

本文实验中采用准确率(Precision)、召回率(Recall)、F-measure作为度量算法优劣的评价标准；准确率表示为用户产生的推荐列表中，有多大比例的资源是用户真正喜欢的，如式(8)表示；召回率表示用户真正喜欢的商品中，有多大比例的商品进入了推荐列表，如式(9)表示，准确率和召回率越高，表示推荐效果越好[12]；同时还使用了一个平衡以上两种指标的综合评价指标F-measure,如式(10)表示。设R(u)指用户在训练集上通过分析用户行为得到的推荐列表，T(u)表示用户在测试集中的行为列表。则推荐结果的准确率定义如下：

(8)

推荐结果的召回率定义如下：

(9)

F-measure定义为：

(10)

3.3 实验结果

本文将基于网络分割聚类的标签规范化后的标签应用推荐算法中，实验试图从两个方面展开：一是分析在标签规范化中融合相似计算的参数λ对推荐结果的影响，二是比较所提方法与其他推荐算法进行推荐效率与准确率的比较。

(1) 确定融合相似度参数λ对推荐质量的影响

本部分测试λ的值对推荐结果的影响，实验设置λ的值为0到1，值变化的间隔为0.1，并设置邻居数目分别为20、40、60、80，每组数据集上分别进行实验，实验中分别测试推荐结果的Precision。其结果如表3所示。

表3 不同参数λ值对Precision变化情况

从表3可以看出，参数λ值的变化确实可以影响推荐结果，但总体变化不大。其中当λ=0表示在标签规范化过程中标签相似度计算仅考虑计算标签的资源共现相似度，而当λ=1表示仅考虑计算标签的语义相似度，最终规范后的标签应用到推荐算法的效率都不高，而融合相似度计算方法后推荐效果明显好于单一的计算方法。表3中可获知，当λ值不断变化时，Precision值会有所变化，但当λ=0.4时，Precison值普遍最大。

(2) 算法推荐效果比较

为了进一步验证本文标签规范化推荐算法的有效性，将本文算法NT-CF与两个较新的算法tensor-u[13]与colla-tv[14]和一个经典推荐算法T-CF[15]用Precision、Recall、F-measure三个度量标准验证实验，根据前面的实验所知，设K=60，λ=0.4，随着推荐列表的数量N值的变化，三个度量标准的值也会不同，并将N设置从5到25变化，值变化间隔为5。对比结果如图1、图2所示。通过在Movielens和Delicious两个数据集上三个度量标准进行对比，可知本文的算法在准确率、召回率、F-measure三个度量标准都明显好于其他推荐算法。

图1 Movielens数据集结果对比

图2 Delicious数据集结果对比

4 结 语

鉴于目前所有的数据集和具体任务的需求，本文围绕“基于网络分割聚类的标签语义规范化推荐算法”问题，首先引入英文维基百科词库训练Word2vec语义模型，以便于构建标签之间的语义关联，计算独立标签之间的语义相似度；继而分析用户标注行为数据，构建基于融合相似度的标签共现网络，实现基于节点核心度和相似性的加权网络分割聚类算法。将用户的自定义标签用能表示所在类簇的特征标签即规范化标签代替并构建用户兴趣模型，在不改变用户的前提下一定程度上减少向量维数简化计算，并将规范化标签构建用户兴趣模型并应用到协同过滤算法中。与已有的基于标签的推荐算法在三个度量标准上进行对比，从而验证了本文算法的有效性。

[1] Verma C,Hart M,Bhatkar S,et al.Improving Scalability of Personalized Recommendation Systems for Enterprise Knowledge Workers[J].IEEE Access,2016,4:204-215.

[2] Wei S,Zheng X,Chen D,et al.A hybrid approach for movie recommendation via tags and ratings[J].Electronic Commerce Research and Applications,2016,18:83-94.

[3] Martins E F,Belém F M,Jussara M.On cold start for associative tag recommendation[J].JASIST,2016,67(1):83-105.

[4] Gan M,Sun L,Jiang R.Trinity:walking on a user-object-tag heterogeneous network for personalised recommendations[J].Journal of Computer Science and Technology,2016,31(3):577-594.

[5] Cao J,Wu Z,Wang Y,et al.Hybrid Collaborative Filtering algorithm for bidirectional Web sevice recommendation[J].Knowledge and Information Systems,2013,36(3):607-627.

[6] Kim H N,Alkhaldi A.Collaborative user modeling with user-generated tags for social recommender systems[J].Expert Systems with Applications,2013,2(32):564-572.

[7] Xu G,GuY,Dolog P,et al.SemRec:A Semantic Enhancement Framework for Tag Based Recommendation[C]//Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence.SanFrancisco,California:AAAI Press,2015:321-330.

[8] Xie H,Li X,Wang T,et al.Incorporating sentiment into tag-based user profiles and resource profiles for personalized search in folksonomy[J].Information Processing & Management,2016,52(1):61-72.

[9] Servan C,Berard A,Elloumi Z,et al.Word2vec vs DBnary:Augmenting meteor using vector representations or lexical resources?[C]//Proceedings of COLING 2016,the 26th International Conference on Computational Linguistics,2016:1159-1168.

[10] Flati T,Vannella D,Pasini T,et al.MultiWiBi:The multilingual Wikipedia bitaxonomy project[J].Artificial Intelligence,2016,241(12):66-102.

[11] Yilmaz R M,Baydas O.Pre-service teachers’ behavioral intention to make educational animated movies and their experiences[J].Computers in Human Behavior,2016,63(12):41-49.

[12] Chen J,Li K,Tang K.A parallel patient treatment time prediction algorithm and its applications in hospital queuing-recommendation in a big data environment[J].IEEE Access,2016,4:1767-1783.

[13] Zhang S,Ge Y.Personalized tag recommendation based on transfer matrix and collaborative filtering[J].Journal of Computer and Communications,2015,3:9-17.

[14] Peng J,Zeng D.Collaborative filtering in social tagging systems based on joint item-tag recommendations[C]//Proceedings of the 19th ACM international conference on Information and knowledge management,2014:809-818.

[15] Tso-Sutter K H L,Marinho L B,Schmidt-Thieme L.Tag-aware recommender systems by fusion of collaborative filtering algorithms[C]//Proceedings of the 2010ACM Symposium on Applied Computing.NewYork:ACM press,2010:1995-1999.

ARECOMMENDATIONALGORITHMWITHTAGSSEMANTICNORMALIZATIONBASEDONNETWORKSEGMENTATIONCLUSTERING

Ye Ting Cao Jie

(CollegeofInformationandEngineering,NanjingUniversityofFinanceandEconomics,Nanjing210046,Jiangsu,China)

The traditional recommendation algorithm mostly uses the user rating data to calculate the user’s interest preference and the resource similarity, and the recommendation quality to the sparse data as well as the new user is low. Considering the randomness and semantic ambiguity of user label data, a semantic normalization method based on label network segmentation clustering is proposed and a user interest model based on canonical label is established. The model can effectively reduce the vector dimension of the user’s tag interest model without changing the user’s interest. It can avoid the complicated process of tag semantics and obtain user interest according to the user’s own understanding. Moreover, the label interest model has applied to the recommendation algorithm. Compared with the classical recommendation algorithm, it is verified that the algorithm can effectively alleviate the sparsity of data and recommend the cold start problem. It can improve the accuracy of the recommended results, and obtain better recommendation results.

Tag Semantic normalization Recommendation algorithm

2017-01-16。叶婷，硕士，主研领域：数据挖掘，推荐系统。曹杰，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.11.012