基于标签聚类与用户模型的个性化推荐方法研究

刘如娟

〔摘 要〕社会标签系统是Web2.0中提出的概念，旨在更好地表达用户的兴趣和意愿。而标签聚类是社会标签系统的个性化推荐中一个重要的研究课题。本文研究了如何基于标签聚类与用户模型来进行个性化推荐的方法。通过计算标签的相似度进行标签聚类，结合用户模型，根据标签聚类结果做出推荐。通过采用CiteULike公布的数据集进行实验证明，与未采用标签聚类的推荐方法相比，本方法不仅可提高推荐的命中率，优化目标资源的排名，而且能为用户发现更多新的感兴趣的资源。

〔关键词〕社会化网络；社会标签系统；标签聚类；用户模型；个性化推荐

〔中图分类号〕G250.73 〔文献标识码〕A 〔文章编号〕1008-0821（2016）06-0074-05

〔Abstract〕Social tag system is a new concept proposed in Web2.0 to express users interest more clearly.And tag clustering is an important research topic in personalized recommendation.This paper proposed a personalized recommendation method based on tag clustering and user model.Tag clustering was realized by calculating similarity between tags and made recommendations according to tag clustering results.Experiment results using CiteULike data set show，proposed method which could improve the recommendation hit ratio compared with general recommendation algorithm，optimize ranking of objective resources，and help users to discover new resources easier.

〔Key words〕social networks；social tag system；tag clustering；user model；personalized recommendation

在Web2.0时代，用户不仅是内容的浏览者，同时也是内容的创造者。由于网络信息的爆炸式增长，用户常常在海量信息中无法快速找到自己需要的资源。目前，大多数Web2.0网站都提供了社会标签系统，例如：Delicious，Last.fm，Flickr，CiteULike以及豆瓣网等。在这些网站中，用户可以按照自己的理解，自由地用标签对自己感兴趣的资源进行标注。同时，用户还可以根据标签对资源进行访问，并且可以利用对自己感兴趣的其他人所做的标签去发现一些自己感兴趣的新资源。用户在标注资源时所使用的标签既反映了用户自身的兴趣爱好，又反映了资源的特点。作为联系用户和资源的纽带，标签是反映用户数据的重要数据源。因此可以利用用户在标注资源时所使用的标签为用户推荐其所需要的资源。

但是传统的协同过滤推荐算法并没有将标签信息考虑到推荐过程中，因此不能挖掘到标签所蕴含的丰富的个性化信息，无法适应社会标签系统中个性化推荐的要求。同时，由于社会化标注具有一定的随意性和不可控性，带来的标签语义模糊性以及数据稀疏性问题，影响了利用标签进行个性化推荐的效果。因此，研究如何通过标签聚类发现同一标签所表达的不同含义，理解用户的真正意图，为其推荐更加符合其兴趣的资源具有重要意义。

近几年来，基于标签数据的推荐方法研究获得了学术界广泛的关注，如何利用用户标签数据设计高效准确的个性化推荐算法，为用户提供适合其个性化需求的资源和标签，已经成为个性化推荐研究领域重要的研究内容之一。

本文主要研究用户给资源标注标签的行为，对标签进行聚类，通过分析用户标签数据确定推荐算法，将基于用户模型与基于链接关系的相似度计算方法相结合，研究增加标签聚类后的个性化推荐方法，通过与以往推荐方法的比较，证明可提高推荐的质量和性能。

文章结构如下：第一部分对本文的研究内容进行简单介绍。第二部分对国内外研究现状进行介绍。第三部分描述本文采用的标签推荐算法，通过标签聚类提高推荐系统的性能，实现资源推荐。第四部分的实验设计评测指标验证该推荐系统各方面的性能。第五部分总结全文并且对未来工作进行展望。

1 国内外研究现状

随着社会化网络的迅速发展，基于标签数据的推荐算法的研究已经成为该领域的研究热点之一。文献[1-2]提出的基于图的FolkRank算法是其中之一，这种方法的基本思想主要是利用标签与资源以及标签与用户之间的链接信息，但这种方法并没有很好的考虑用户标签中所蕴含的个性化涵义，因此无法给不同的用户推荐个性化标签。

而将标签信息与传统的推荐模型相结合的研究是个性化推荐研究的一个新方向。文献[3]提出一种新的基于标签的协同推荐模型，将用户的标签信息抽象为用户向量，从而对资源进行协同推荐[4]。文献[5]采取了类似的方法，主要是采用WordNet来计算不同用户之间的相似度，来进行协同推荐。文献[6]中提出了基于张量分解的标签推荐方法，该方法将社会标签系统数据集合表示为3阶张量的形式，利用高阶奇异值分解技术来挖掘用户、标签及资源之间的潜在语义。通过与两种重要的推荐算法进行比较，证明在准确率和召回率上都有明显提高。

文献[7]提出了一种基于资源共现的随机游走方法来聚类标签；文献[8]利用标签共现的分布相似性来增强标签相关性，结合递归贪婪算法和模块化函数实现了标签的聚类；文献[9]介绍了一种基于资源共现的标签单链接层次聚类算法来提高信息检索的效率；文献[10]通过建立标签共现网络，提出了一种基于标签相似性的聚类算法对标签共现网络进行分割，并建立标签聚类簇。

将聚类技术应用到资源推荐中也是个性化推荐领域的研究方向之一。文献[11]的研究表明可以利用层次聚类的方法将资源进行分类，可以在一定程度上消除标签的冗余性和歧义性等问题。文献[12]提出了一种基于核信息传播的标签聚类方法，利用余弦夹角函数在标签的资源向量空间上来测量标签之间的相关性。文献[13]的研究认为利用层次聚类可以将标签聚类成与主题相关的类，将标签表示为基于Web资源的向量，运用层次聚类算法进行标签聚类，并将聚类结果应用到社会标签系统的个性化推荐系统中，以此来提升用户体验，但是层次聚类方法不具有很好的可伸缩性，合并或分裂点选择比较困难，同时在合并或分裂的过程中需要检查和估算大量的对象或结果。

以上方法主要通过建立标签的资源向量空间模型或以标签的资源共现为基础来计算标签的相似性，缺点在于忽略了三元标注数据中的用户信息，无法利用标签与标签之间的语义关系以及标签与用户之间的关系，使得聚类的结果不能完整表达标签的语义。为了解决以上问题，本文采用了一种基于标签相似度计算的聚类方法，实验证明，该方法可提高个性化推荐系统的性能。

2 基于标签聚类的个性化推荐

对标签聚类的研究中，最重要的是能够找到一种好的聚类方法，该方法能够综合考虑到标签与用户间以及标签与资源间的关系，使得算法所产生的聚类既能充分的反映用户对某一主题的偏好程度，又能够体现对资源的反应程度。而聚类算法中的核心问题就是如何计算标签之间的相似度，使得聚类能够更加准确地描述标签的个性化特征，更好地为推荐打下基础。本节通过计算标签的相似度，研究一种标签聚类算法，将基于用户和资源链接关系相结合计算标签相似度。实验证明进行标签聚类后确实能够提高目标资源的推荐排名和命中率。

表1展现了利用上述公式计算出的CiteULike数据集中recommendersystem标签的相关标签及对应的相似度。

2.2 标签聚类算法

目前的聚类方法有很多，本文采用的聚类算法是借用k-means算法的思想，基于标签相似度的计算实现的。同时对k-means算法进行了改进，提高了标签聚类的精度。

首先计算基本标签两两之间的相似度，将相似性大于一定阈值的基本标签归于同一原始类别中。然后将只包含极少数标签的类作为奇异值去掉，进行进一步聚类，如算法3.1所示。标签聚类算法可以离线运行。

Step 1 经过初始化，将所有具有共同标注资源的标签对（ti，tj）及其相似度Simr（ti，tj）存储到集合SimRe中；

Step 2 在SimRe中寻找具有最大相似度的簇进行合并，直到簇中标签对的最高相似度差值小于limit；

Step 3 将同一聚类的所有标签作为该聚类的中心，重新计算聚类中标签的相似度，直到聚类中心不再发生变化。

通过算法3.1，这样可以完成社会化标签的聚类。经过聚类，聚类数目能够远远小于基本标签的数目，即kn。后续的实验将对该方法进行验证。

2.3 基于用户模型的个性化资源推荐

采用的推荐系统结构如图1所示，推荐过程分为两个阶段：在第一阶段，用户点击标签时，运行协同过滤算法做出初始的推荐，为用户提供资源集合；在第二阶段，考虑用户模型和标签聚类后，对该资源集合重新排名，生成个性化的推荐结果。实现过程如算法3.2所示：

3 实验评测

本文采用CiteULike公布的数据集进行算法性能的评测。CiteULike具有大量带标签的资源数据集，本文从中取出约10%的数据进行试验。原始数据库中，每条数据都包括文章号、用户名（MD5值）、收藏时间及收藏时用的标签4个字段。若用户在标注一篇文章时使用了多个标签，则这些标签分别存入多条数据中。由于本文研究是根据用户标签来对用户进行聚类，考虑用户标签与所标注的文章间的关系，因此从原始数据表中提取文章号、用户名与标签3个字段的数据，形成一个以用户名、其使用标签及所标注的文章号为字段的表。

3.1 数据处理

对数据进行简单的预处理，包括对无实际意义的标签，如词组“no-tag”或纯数字标签等进行删除，为简化后续计算对只被一个用户使用的标签将不进入聚类分析计算。经过处理后，数据包含3 276个用户、30 667篇论文和11 377个标签。采用5层交叉验证（5-fold cross validation）的方法，即将用户集分成5份，依次将每一份作为测试集，另4份合并作为训练集进行实验，得到5个不同的测试/训练集，标签的聚类算法在训练集上进行。依次对每个（测试/训练集）测试，将最终得到的5个测试结果做算术平均计算，得到最终的评估结果。

具体试验是在Java JDk 1.6.0的环境下，运用MySQL数据库存储用户、标签和文献信息，形成（用户-标签-文献）数据库，并且使用navicat可视化客户端管理数据，在MyEclipse 6.5下计算社会化标签与资源（这里就是论文数据）间的关联系数。

标签数据的聚类分析实验采用由新西兰怀卡托大学开发的开源数据挖掘工作平台——怀卡托智能分析环境WEKA3.7.0运行算法3.1，进行标签聚类。在初步聚类后，得到一些只包含极少数标签的类，这些特殊的类包含了那些兴趣特殊、异于他人的用户所产生的标签，与其他用户兴趣缺乏重叠，很难利用这些标签进行资源推荐，因此将这部分标签作为奇异值删除。继续进行聚类分析，得到的聚类结果中虽然已经没有包含极少数标签的类，但仍存在一个大类，其中包含的标签数量占总标签数量的近一半。比较理想的聚类效果应该是每个类中的标签相对比较均衡，因此对这样的大类单独提取出来继续进行聚类。若再聚类后依然得到标签数量极少的类别，则再进行奇异值处理。经过上述的反复聚类后，发现再继续聚类也不能聚成几个有明显区别的类时停止聚类。通过多次的聚类分析，解决了标签的数据稀疏性问题，为提高推荐性能做好准备。

3.2 评估标准

运行算法3.2，首先采用imp[14]方法对推荐结果进行评估。运用“leave one out”方法，对任意指定资源，即文献，先将其对应的（用户-标签-资源）组从推荐列表中移除，再分别运行基于标签的协同过滤推荐算法及增加聚类后的推荐算法，检查提出的推荐算法能否提高该篇文献在推荐列表中的排名。

在imp方法中，推荐算法的推荐资源数目没有限制。推荐列表中如果有目标资源，排名等于它在列表里面的真实排名，如果没有找到排名就等于∞。

其中，rb为协同过滤推荐算法推荐的目标资源的排名，rp为基于标签聚类的算法推荐的目标资源的排名。

对所有测试用户计算imp然后求出算术平均，可以看出，imp值越高，目标资源的排名越靠前，说明相应的算法的推荐效果越好。图2是利用imp评测方法得到的实验结果。本实验中，应用标签聚类的推荐算法α值为0.7的时候其结果最佳，而协同过滤推荐算法α值为0.2的时候最佳。从图2中可以看出推荐结果的线形加权值对资源排名的影响，α值的过高或过低都影响算法的性能。同时能够证明，基于标签聚类的推荐系统确实可以提高目标资源的排名。

另外，我们对标签聚类算法中的阈值limit进行不同的取值，通过对命中率[15]的比较来检验limit取值对命中率的影响及改进后的推荐算法是否能得到对命中文献更高的排名。命中率是指系统为测试集中每个用户做出正确推荐的概率，所谓一次正确推荐（命中）是指推荐列表中包含被去除的那篇文献。命中率定义为如下公式：

其中hit表示对测试集中用户做出的推荐列表包含被去除的文献的次数，testset表示测试用户集的大小。图3是命中率的实验结果。从图中可以看出，增加标签聚类后的命中率要比一般协同过滤方法的高，而且当阈值limit取值为0.3时，命中率是最高的。

综上所述，和一般推荐方法相比，基于标签聚类的方法可优化指定文献在推荐列表中的排名，能达到较好的效果，验证了算法的有效性。

4 存在的问题及展望

本文通过计算标签相似度，实现了一种标签聚类算法，在此基础上提出推荐算法进行个性化推荐。通过实验证明，和传统的协作过滤算法相比较，该方法有比较明显的改进，验证了标签聚类在Folksonomy个性化服务中确实能够有效提高推荐服务质量。未来工作将继续优化标签的聚类方法，并能够运用在个性化推荐服务系统中，提高推荐个性化服务质量。

参考文献

[1]R.Jaschke，L.Marinho，A.Hotho，L.Schmidt-Thieme，and G.Stumme.Tag Recommendations in Folksonomies.Lecture Notes In Computer Science，4702：506，2007.

[2]A.Hotho，R.Jaschke，L.Schmidt-Thieme，and G.Stumme.FolkRank：A Ranking Algorithm for Folksonomies.In Proc.FGIR，2006.

[3]R.Nakamoto，S.Nakajima，J.Miyazaki，and S.Uemura.Tag-based Contextual Collaborative Filtering.In 18th IEICE Data Engineering Workshop，2007.

[4]J Wang，Arjen P.de Vries，Marcel J.T.Reinders.Unifying User-based and Item-based Collaborative Filtering Approaches by Similarity Fusion，sigir 06.

[5]S.Zhao，N.Du，A.Nauerz，X.Zhang，Q.Yuan，and R.Fu.Improved Recommendation based on Collaborative Tagging Behaviors.IUI08，January 13-16，2008，Maspalomas，Gran Canaria，Spain.

[6]PanagiotisSymeonidis，AlexandrosNanopoulos，YannisManolopoulos.Tag recommendations based on tensor dimensionality reduction.In RecSys08，October 23-25，2008，Lausanne，Switzerland.

[7]Cui Jianwei，Liu Hongyan，He Jun，et al.Tagclus：A random walk based method for tag clustering[J].Knowledge and Information Systems，2011，27（2）：193-225.

[8]Begelman G，Keller P，Smadja F.Automated tag clustering：Improving search and exploration in the tag space[C].Collaborative Web Tagging Workshop at WWW2006.Edinburgh：ACM，2006：15-33.

[9]Knautz K，Soubusta S，Stock W G.Tag clusters as information retrieval interfaces[C].Proceedings of the 43rd Hawaii International Conference on System Sciences.Big Island，Hawaii：IEEE Computer Society Press，2010：1-10.

[10]王萍，张际平.一种社会性标签聚类算法[J].计算机应用与软件，2010，27（2）：126-129.

[11]P.Heymann and H.Garcia-Molina.Collaborative Creation of Communal Hierarchical Taxonomies in Social Tagging Systems.Technical report，Technical Report 2006-10，Computer Science Department，April 2006.

[12]Xu Guandong，Zong Yu，Jin Ping，et al.KIPTC：A kernel information propagation tag clustering algorithm[J].Journal of Intelligent Information Systems，2013：1-18.

[13]Shepitsen A，Gemmell J，Mobasher B，et al.Personalized recommendationin social tagging systems using hierarchical clustering[C].Proceedings of the 2008 ACM Conference on Recommender Systems.New York：ACM，2008：259-266.

[14]Ellen M.Voorhees.The TREC-8 Question Answering Track Report.Proceedings of TREC8：77-82，1999.

[15]S.McNee，I.Albert，D.Cosley，P.Gopalkrishnan，S.K.Lam，A.M.Rashid，J.A.Konstan，J.Riedl.On the Recommending of Citations for Research Papers.In Proceedings of the ACM 2002 Conference on Computer Supported Cooperative Work（CSCW 2002），New Orleans，LA，2002：116-125.