基于模糊聚类的旅游推荐算法

张应辉,李 雪

(东北大学 计算机科学与工程学院，辽宁 沈阳 110000)

基于模糊聚类的旅游推荐算法

张应辉,李 雪

(东北大学 计算机科学与工程学院，辽宁 沈阳 110000)

在旅游领域中，旅游者常常在旅游前从互联网上获取所需信息，但是在线旅游业日益严重的信息过载现象，使得用户不能得到他们想要的个性化信息。传统的基于协同过滤的旅游推荐研究普遍都存在稀疏性和可扩展性等问题，基于知识的推荐研究有时因用户无法表达清楚他们的需求而无法得到满意的推荐。针对已有的旅游推荐算法存在的问题，提出了一种基于模糊聚类的旅游推荐算法，为用户推荐符合其需求和偏好的旅游产品。该算法利用标签构建用户偏好景点模型和景点特征属性模型，对数据集进行模糊聚类，同时提出新的相似度度量。在此基础上，组合基于内容和协同过滤技术进行混合推荐。实验结果表明，该算法能显著提高推荐系统的效率以及可扩展性和准确度。

个性化；标签；相似性度量；模糊聚类；混合推荐

0 引 言

旅游推荐算法[1-3]的研究是旅游领域研究的热点。旅游网站不断兴起，推荐精度的高低直接影响用户是否选择预定该线路，影响用户对该旅游网站信息的兴趣度，兴趣度的高低决定了用户对该旅游网站的使用率。针对个性化旅游推荐[4-6]问题，学者们进行了深入研究。例如，基于协同过滤技术的旅游推荐研究[7]在一定程度上提高了推荐的多样性，但是普遍都存在稀疏性和可扩展性的问题。基于知识的、会话式的旅游推荐[8]方式使用交互&个性化代理以会话的形式逐步发现用户的偏好和需要，然后利用多属性效用理论对推荐结果进行排序，一定程度上提高了推荐的精确度。但此方法需要大量的领域知识和推理技术，需要考虑多方面的因素，有时用户很难准确地表达自己的需求，推荐效率缓慢。

针对上述问题，提出一种基于模糊聚类[9-12]的旅游推荐算法(Tourism Recommendation algorithm Based on Fuzzy Clustering,TRBFC)，建立了新的用户偏好景点模型[13-14]，提出了一种新的相似度计算方法，使用模糊聚类的方法对数据集进行聚类，在此基础上，组合基于内容和协同过滤的技术进行混合推荐。该算法使得系统的推荐效率、可扩展性进一步提高，改善了系统的稀疏性，进一步提高了推荐的准确率。

1 相关定义

TRBFC算法在构建用户偏好景点模型时，主要考虑了用户使用过的景点标签。当用户浏览旅游网站时，用户喜欢的景点都会有相应的标签，比如Tom喜欢的景点标签中经常出现“主题”、“海边”等短语，那么他可能喜欢主题游或海边游，其中“主题”出现的频率较高，Tom可能更喜欢此类景点。

定义1：如果系统中有q类景点标签，那么对用户，通过TRBFC算法构建的用户景点偏好模型如式(1)所示：

(1)

其中，pq表示标签q被用户ui使用的频率(即次数)。

定义2：如果系统中有q类景点标签，那么对于景点，通过TRBFC算法构建的景点特征属性模型如式(2)所示：

(2)

其中，aq表示标签q是否是景点si的标签。

(3)

其中，xij表示用户ui使用标签ti的个数。

(4)

其中，yij表示景点si是否包含标签ti，包含则值为1，反之为0。

(5)

其中，rij表示用户ui对景点si的评分。

评分值为[1,5]之间的整数,评分值由高到低表明用户对该景点兴趣的高低。若未评分，则取值0。

定义6：欧氏距离。欧几里德距离又叫欧氏距离，常用来计算两个向量间的距离，并认为这是两个向量的差距。TRBFC算法采用欧氏距离，如式(6)所示：

(6)

其中，dti表示用户ut对用户ui偏好景点之间的距离；xij为定义3中矩阵B中用户使用标签的频率(即个数)。

2 TRBFC算法的实现

由于一个景点可能拥有多个标签，可以属于多个不同的类，所以首先采用模糊聚类的方法对用户-标签数据集和景点-标签数据集进行聚类，使相近的景点或用户分为一组，其次组合基于内容和协同过滤的推荐算法，按照一定的关系组合二者，进行旅游景点的推荐。

首先对Oui进行模糊聚类。

(1)基本参数初始化。聚类的最终类别个数c，2≤c0)；用户-标签频率矩阵B；聚类中心矩阵V0和迭代次数计数器f=0。

(2)用户-标签隶属度矩阵Uf的更新。用式(7)进行更新：

(7)

(3)用户-标签聚类中心矩阵Vf+1更新,使用式(8):

(8)

(4)如果‖Vf-Vf+1‖<θ,则算法停止并返回用户-标签隶属度矩阵U和用户-标签聚类中心矩阵V,否则f=f+1,转向步骤(2)进行迭代计算。

(5)对于目标用户ut,根据隶属度找到它所在的类别，把式(6)作为新的相似度度量，计算ut与其所在类别中其他用户之间的相似度，按照相似度大小排序，排在最前面的N位即可作为目标用户的邻居集，记为N(ut)。

同理可以对Isi模糊聚类后获取景点-标签隶属度矩阵I和景点-标签聚类中心矩阵Q。此处不再证明。

在此基础上，推荐结果由基于内容和协同过滤的混合推荐算法来推荐获得。

(1)使用协同过滤方法对于目标用户ut的邻居集N(ut)，结合式(5)给出的用户评分矩阵R，对目标用户未选择的景点做预测评分，如式(9)所示：

(9)

其中，rtw表示目标用户ut对景点w做的预测评分；dij的值应该大于等于1。

得到预测评分后，按其高低把获得预测评分最高的Top-K个项目放入一个集合M中。

(2)使用基于内容的方法，根据隶属度判断目标用户ut正在查看的或者已经存在景点si所在的模糊类类别。si可能属于多个类。利用式(10)计算目标用户ut与所属聚类类别中其他景点的相似性：

(10)

其中，sim(a,si)是由景点si和类中其他景点a之间标签相同的个数比两者标签总的个数所得。

设置一个集合H，一个阈值β，当sim(a,si)>β，把景点si放入H中。对集合中的景点按相似度值大小排序。获取top-N个景点的推荐集合，N的值取5。

(3)综合集合M和H中的景点，两个集合相交得到最终的景点推荐集合HM。

3 实验结果及分析

3.1 数据来源

使用从途牛网中获取的旅游景点信息进行实验。在选取的整个数据集中，所有的景点数据为512，景点评分数据为67 690，评分取[1,5]中的任意整数，评分值由高到低代表旅游者对该景点的满意程度。在得到的数据集中，以用户-标签矩阵为例，形式如表1所示。

3.2 评价指标

训练集由随机抽取50 000条景点评分组成，测试集由剩余的数据组成，分别用传统的基于知识的旅游推荐、基于用户的协同过滤方法和改进算法进行比较。采用准确率和召回率作为评测标准。

表1 用户-标签矩阵B

(11)

(12)

其中，Pu为准确率；Ru为召回率；TMu为算法用户推荐景点的集合；Tu为用户在测试集上喜欢的景点的集合。

3.3 实验分析

图1和图2分别为传统的基于知识推荐、协同过滤推荐和文中算法的准确率测试和召回率测试。其中，U1是最终推荐景点数目为10的数据集，U2～U5分别是最终推荐景点数目为15、20、25、30的数据集，当最终推荐景点数目达到30时，准确率值上升缓慢，所以最终推荐景点数目不宜选择过大。

图1 准确率测试

图2 召回率测试

从两图中可以看出，与传统的算法相比，数据模糊聚类后，混合推荐算法的推荐精度要高一些。

4 结束语

针对传统旅游推荐算法推荐效率不高的问题，提出了一种模糊聚类方法，采用新的相似度度量，在一定程度上缩短了寻找用户邻居集和相似景点的时间，提高了效率和扩展性。另外采用混合推荐技术，在一定程度上改善了推荐系统的稀疏性和冷启动问题。

[1]HwangS,YanW.On-tourattractionrecommendationinamobileenvironment[C]//IEEEconferenceonpervasivecomputingandcommunications.NewJersey:IEEEPress,2012.

[2]RicciF,RokachL,ShapiraB,etal.Recommendersystemhandbook[M].[s.l.]:Springer,2011.

[3] 陈 梅.旅游信息智能推荐系统的研究与设计[D].贵阳:贵州大学,2010.

[4]LiuQ,GeY,LiZM,etal.Personalizedtravelpackagerecommendation[C]//IEEEinternationalconferenceondatamining.NewJersey:IEEEPress,2011:407-416.

[5] 安 维，刘启华，张李义.个性化推荐系统的多样性研究进展[J].图书情报工作，2013，57(20):127-135.

[6] 胡纳纳，李琳琳，武 尚.个性化的旅游推荐系统[J].信息技术，2013(2):135-139.

[7] 侯新华，文益民.基于协同过滤的旅游景点推荐[J].计算机技术与自动化,2012,31(4):116-119.

[8] 王显飞，陈 梅，李小天.基于约束的旅游推荐系统的研究与设计[J].计算机技术与发展，2012，22(2):141-145.

[9]ZenebeA,ZhouLina,NorcioAF.Userpreferencesdiscoveryusingfuzzymodels[J].FuzzySetsandSystems,2010,161:3044-3063.

[10]SrivastavaV,TripathiBK,PathakVK.AnevolutionaryfuzzyclusteringwithMurkowskidistances[C]//Proceedingsofthe2011internationalconferenceonneuralinformationprocessing.Shanghai,China:[s.n.],2011.

[11]ZhangChen,LiuBing.Possibilisticfuzzyclusteringalgorithmbasedonsampleweighted[C]//Proceedingsof3rdinternationalworkshoponintelligentsystemsandapplications.Wuhan,China:[s.n.],2011.

[12]TsaiDu-Ming,LinChung-Chan.FuzzyC-meansbasedclusteringforlinearlyandnonlinearlyseparabledata[J].PatternRecognition,2011,44(8):1750-1760.

[13]HuangWeidong,KhouryR,DawbornT,etal.WeBeVis:analyzinguserwebbehaviorthroughvisualmetaphors[J].ScienceChinaInformationSciences,2013,56(5):1-15.

[14]WuXiyuan,ZhengQinghua,WangPing.Aintelligentmethodofmodellingwebuserinterest[J].JournalofNewIndustrialization,2014(9):39-43.

[15] 肖曼生,阳姊兰，张居武，等.基于模糊相关度的模糊C均值聚类加权指数研究[J].计算机应用,2010,30(12):3388-3390.

A Tourism Recommendation Algorithm Based on Fuzzy Clustering

ZHANG Ying-hui，LI Xue

(School of Computer Science and Engineering,Northeastern University,Shenyang 110000,China)

In the field of tourism,tourists often get the information they need on the Internet before traveling,but the phenomenon of information overload online in tourism industry is becoming more and more serious,so that personalized information cannot be obtained by users.The problems of sparsity and scalability exist in the traditional tourism recommendation algorithm based on collaborative filtering,and sometimes users can’t express their needs and can’t be satisfied with the recommendation based on the knowledge of the recommendations.For these problems,a tourism recommendation algorithm based on fuzzy clustering is proposed,which is used for the users to recommend the tourism products that meet their needs and preferences.Tags are used by the algorithm to build user’s preference models and sights feature attribute model,fuzzy clustering on them.A new similarity measure is proposed.On this basis,the combination of content-based and collaborative filtering technology is recommended.Experimental results show that the proposed algorithm can significantly improve the efficiency,scalability and accuracy of the recommendation system.

individualization;tags;similarity measurement;fuzzy clustering;hybrid recommendation

2016-06-03

2016-09-08

时间：2016-11-22

国家自然科学基金资助项目(61262058)

张应辉(1972-),男,副教授,硕士生导师,研究方向为计算机图像处理、机器学习；李 雪(1991-),女,硕士研究生,研究方向为数据挖掘、机器学习。

http://www.cnki.net/kcms/detail/61.1450.TP.20161122.1227.020.html

TP301.6

A

1673-629X(2016)12-0099-04

10.3969/j.issn.1673-629X.2016.12.022