基于移动用户上下文相似度的张量分解推荐算法

余可钦，吴映波，李 顺，蒋佳成，向 德，王天慧

(1.信息物理社会可信服务计算教育部重点实验室(重庆大学)，重庆400030； 2.重庆大学 软件学院，重庆 401331)(*通信作者电子邮箱wyb@cqu.edu.cn)

基于移动用户上下文相似度的张量分解推荐算法

余可钦1,2，吴映波1,2*，李 顺1,2，蒋佳成1,2，向 德1,2，王天慧1,2

(1.信息物理社会可信服务计算教育部重点实验室(重庆大学)，重庆400030； 2.重庆大学 软件学院，重庆 401331)(*通信作者电子邮箱wyb@cqu.edu.cn)

针对移动服务推荐中用户上下文环境复杂多变和数据稀疏性问题，提出一种基于移动用户上下文相似度的张量分解推荐算法——UCS-TF。该算法组合用户间的多维上下文相似度和上下文相似可信度，建立用户上下文相似度模型，再对目标用户的K个邻居用户建立移动用户-上下文-移动服务三维张量分解模型，获得目标用户的移动服务预测值，生成移动推荐。实验结果显示，与余弦相似性方法、Pearson相关系数方法和Cosine1改进相似度模型相比，所提UCS-TF算法表现最优时的平均绝对误差(MAE)分别减少了11.1%、10.1%和3.2%;其P@N指标大幅提升，均优于上述方法。另外，对比Cosine1算法、CARS2算法和TF算法，UCS-TF算法在数据稀疏密度为5%、20%、50%、80%上的预测误差最小。实验结果表明UCS-TF算法具有更好的推荐效果，同时将用户上下文相似度与张量分解模型结合，能有效缓解评分稀疏性的影响。

用户上下文；上下文相似度模型；数据稀疏；张量分解算法；移动服务推荐

0 引言

随着移动通信技术和移动互联网的快速发展，移动设备成为用户获取网络信息和移动服务的重要工具，用户在“任何时间、任何地点、以任何方式”获取移动服务成为可能[1]。用户在不同上下文条件下有不同的移动服务需求，但爆炸性增长的移动应用程序使得用户难以找到最感兴趣或者最相关的移动服务[2]。因此，如何根据用户在不同情境下的偏好，向用户推荐符合当前上下文约束的移动服务成为目前移动推荐中急需解决的问题之一。移动推荐系统能有效识别和预测用户偏好，主动推荐用户感兴趣的个性化信息或服务，减少查找信息的时间[3]。

与传统的互联网推荐相比，移动推荐引入了复杂多变的用户上下文环境(如时间、位置、情绪等)来提高推荐系统的性能。通过收集用户上下文信息为用户提供上下文感知的推荐服务是目前研究的热点[4]。移动推荐大多基于传统的推荐算法，如协同过滤推荐[5-6]、基于内容的推荐[7]、混合推荐[8]等，主要利用用户行为数据建立用户-项目二元模型来生成移动推荐，但没有充分考虑用户复杂的上下文环境；同时，上下文信息的引入使推荐系统的稀疏性问题更加严重。针对以上问题，一些研究者提出了一些有效和实用的新方法。如文献[9] 提出处理多维上下文数据的方法，通过寻找目标用户当前相似的上下文集合进行预过滤，将“移动用户-上下文-移动服务”降维为“移动用户-移动服务”二维模型，最后通过协同过滤方法进行预测，能得到更好的推荐性能；但该方法没有考虑用户行为和上下文的关联信息。文献[10]提出了改进的上下文感知推荐系统(Context-Aware Recommender Systems recommendation, CARS2)算法，将上下文信息定义为与用户和项目共享相同的潜在空间，综合利用显示反馈数据和隐式反馈数据进行建模，能得到较好的推荐结果；但这种方法的模型太复杂。文献[11] 提出了一个新颖的方法来选择和权衡上下文特征，并预先假设上下文特征选择概率和它们的权重是相同的，再匹配用户上下文向用户推荐合适的项目，实验表明该方法有助于提高推荐质量。针对多维情境信息难以表达和建模的问题，文献[12]将情境信息作为附加特征融入用户信息中计算用户相似性，提高了预测精度。但上述方法都不能很好地处理多维和动态变化的上下文信息，无法满足用户在实时变化的上下文情景中的需求。

本文提出基于移动用户上下文相似度的张量分解推荐(User-Context-Service Tensor Factorization, UCS-TF)算法，构造用户多维上下文相似度模型，将张量分解方法引入移动服务推荐系统中，对目标用户的邻居用户进行建模，预测出用户在特定上下文下访问移动服务的偏好值，有效处理高维稀疏上下文数据。最后在Appazaar数据集上验证了本文所提方法能获得更好的推荐效果，有效利用用户的多维上下文信息，缓解了数据稀疏性问题。

1 UCS-TF算法描述

1.1 用户上下文相似度模型

在移动环境中，移动用户的行为和上下文环境(如时间、位置、天气等)有着密切的关系。例如，有些用户在上班途中喜欢浏览新闻，在运动时喜欢听音乐，在中午休息时间喜欢玩游戏、听音乐。用户在使用相同移动服务时所处上下文条件的重合度可以度量两个用户偏好的相似性。文献[13]认为“相似用户对项目的偏好也具有相似性”这一观点不太准确，原因是相似用户在为项目打分时，所处的上下文条件不完全相同，在相同或者相似的上下文条件下表达的用户偏好，对预测目标用户偏好才更准确。因此，本节提出一种新的计算用户上下文相似度方法，利用用户使用共同移动服务的频次信息计算用户上下文相似度及上下文相似性的可信度，并将用户上下文相似度模型引入张量分解算法中。因此，首先要定义用户上下文相似度模型，构造目标用户的邻居集合。用多维向量表示上下文信息cj=(cj1,cj2,…,cjn)，定义单维上下文类型cjt(t∈[1,n])。用户的上下文信息复杂多样，如果比较与用户相关的所有上下文的相似度会增加模型的复杂度，同时降低算法效率，因此，考虑用户在使用移动服务过程中最相关的四类上下文信息，如下所示。

1)时间：如上午(6：00—12：00)、下午 (12：00—18：00) 、晚上 (18：00—24：00)、凌晨(0:00—6：00)。

2)日期类型：如工作日、周末。

3)位置：如家、办公室、其他。

4)运动情况：如静止、走路、更快、无效。

移动用户在不同上下文环境下使用移动服务的频次信息较评分信息更容易获取到，统计两个用户使用共同移动服务时的上下文频次信息，可以比较两个用户上下文的相似度。如移动用户u1在上述四类上下文环境下使用过五种移动服务S=(s1,s2,…,s5)，得到表1所示数据。第一行数据表示移动用户u1工作日的上午在办公室使用了移动服务s1，此时移动用户处于静止状态，其他数据以此类推。

表1 上下文数据示例

移动用户ui在上下文cj情境下使用了移动服务sk，每一个cj又包含t个上下文类型，每个单维上下文cjt包含m个属性值，则计算上下文cjt的各个属性频次值为：

(1)

其中：F(cjt,m)表示单维上下文cjt的第m个属性值的标准化频次值，fs,m表示在移动服务s中单维上下文cjt属性值m出现的频次，S为移动用户ui使用过的移动服务集合 。表2为表1中用户ui上下文的各个属性标准化频次。

表2 上下文属性值标准化频次值

由单维上下文计算得到的频次信息可以得到每个用户的多维上下文信息为一个向量。由此，对余弦相似度公式进行修改，两个移动用户ui1和ui2间上下文相似性计算定义如下：

(2)

另外，用户共同使用移动服务所占比例影响着用户上下文相似度的可信度，使用Jaccard相似性系数来计算两个上下文集合相似度的可信度。

(3)

其中Sui1和Sui2分别为移动用户ui1和ui2使用过的移动服务集合。

因此，组合用户间多维上下文相似度和上下文相似可信度得到最终的用户上下文相似度，即组合式(2)和式(3)得到：

Sim(ui1,ui2)=SimC(ui1,ui2,c)×Confi(ui1,ui2)

(4)

根据Sim(ui1,ui2)的值，选择目标用户的K个邻居。

1.2 基于用户上下文相似度的张量分解模型

张量能够完整地表示高维数据并维持高维空间数据的本征结构信息，因此张量分解方法广泛应用于上下文感知推荐系统。张量分解的最终目标是补充移动用户、上下文和移动服务变量构成的稀疏张量缺失的评分值，将分解得到的紧凑估计值作为用户的TOP-N移动服务推荐列表。典型的张量分解方法有Tucker分解和ParaFac分解。Tucker分解一种高阶的主成分分析，它将一个张量表示成一个核心(core)张量沿每一个mode乘上一个矩阵。Tucker分解能得到一个较好的近似，因此本文采用Tucker分解方法建立张量分解模型。

传统张量分解算法考虑所有用户行为对目标用户预测值的影响，因数据稀疏性，绝大部分用户和当前目标用户根本不存在交集，导致预测精度不高。本文通过用户上下文相似度模型选择与目标用户最相似的K个用户，过滤掉不相关用户数据对预测的影响，建立移动用户-上下文-移动服务三阶张量分解模型如下：

Yijk=G×UU×CC×SS

(5)

三阶张量Yijk被分解成核心矩阵G和三个分别代表移动用户U、上下文C和移动服务S的因子矩阵，其中核心张量G∈Rdu×dc×ds，各因子矩阵U∈Ri×du，C∈Rj×dc，S∈Rk×ds。

此模型进行移动服务预测时，为了获得最优的移动服务预测值，Xijk和Yijk需要满足式(6)：

(6)

引入用户上下文相似度，对与目标用户最相似的K个用户进行张量分解，对式(6)进行修正如下：

(7)

其中:Un表示用户Ui的K个邻居用户集合;Sim(Ui,Un) 表示用户Ui和Un之间的相似度，可由式(4)计算得到。

为了求解式(7)，得到最小化函数值，本文通过梯度下降法进行求解。其迭代公式为xk=xk-1-ηg′(xk-1)，η表示梯度方向上的搜索步长。向梯度相反的方向移动x，直到x值的变化使得在两次迭代之间的差值足够小，则说明此时已经达到局部最小值。梯度下降法的迭代公式如式(8)～(11)所示。

(8)

(9)

(10)

(11)

求解式(8)～(11)中的梯度，即核心张量G和各因子矩阵U、C、S的偏导数，公式如(12)～(15)所示：

(12)

(13)

(14)

(15)

其中⊗表示克罗内克积(Kronecker product)，克罗内克积是两个任意大小的矩阵间的运算，是张量积的特殊形式。将式(12)～(15)分别代入式(8)～(11)，通过迭代分别求得核心张量G和因子矩阵U、S、C，通过式(5)的张量分解模型重构获得目标用户在不同上下文情境下使用移动服务的预测值，根据预测值排序由高到低给用户推荐合适的移动服务。

2 实验结果及分析

2.1 数据集

本文实验使用的是Appazaar数据集，该数据集包括3 260个用户在不同上下文情境下使用18 205个移动应用程序的370万条记录。Appazaar数据集是从一个上下文感知的个性化移动应用推荐系统Appazaar使用日志中得到的，其根据用户的上下文和偏好向用户推荐最相关的移动应用程序。本实验使用到的Appazaar数据集中上下文主要包括以下四类：时间(4个属性，如上午、下午等)、日期类型(2个属性，如工作日、周末)、位置(3个属性，如家、办公室、其他)、运动情况(4个属性，如静止、走路等)，这四类上下文信息是影响用户选择移动服务的关键因素。本实验将该数据集按照8∶2随机划分为训练集和测试集，训练集用于学习推荐方法中的参数，测试集用来验证推荐的准确性。

2.2 评价指标

本文采用平均绝对误差(Mean Absolute Error, MAE)和P@N两个评价指标来衡量移动服务推荐算法的准确度。平均绝对误差值越小，P@N值越大，推荐性能越好。

1)平均绝对误差定义为：

其中：Xijk表示移动用户ui在cj情境下使用移动服务sk的实际值，Yijk表示使用基于张量分解和用户关系的推荐模型预测移动用户ui在cj情境下使用移动服务sk的预测值，N表示推荐的移动服务个数。

2)P@N定义为：

即表示预测用户可能常用的Top-N项移动服务占用户u实际常用Top-N项服务的比值，用来衡量用户常用Top-N项移动服务的预测正确性。

2.3 实验过程与结果

2.3.1 实验设置

本节主要验证本文所提出的基于移动用户上下文相似度的张量分解推荐算法(UCS-TF算法)的有效性，将其与传统的相似度度量方法如余弦相似性(Cosine Similarity, COS)、Pearson相关系数协同过滤方法进行对比；同时也与现有的一些先进算法进行比较，包括：

1)CARS2算法[10]。该算法提出了一种学习上下文特征的方法：针对显示反馈数据，可以使用二次损失函数进行评分预测；针对隐式反馈数据，通过成对的和成列的表的排名损失函数得到Top-N推荐列表。然后通过随机梯度下降法求得模型参数值，再利用模型求解最终的推荐列表。

2)Cosine1算法[14]。该算法是对余弦相似度计算方法的改进，为不同的目标项目选择不同的邻居，用户的相似度由各项目与目标项目之间的加权相似度表示，最后通过协同过滤的方法进行推荐。

3)TF(Tensor Factorization)算法[15]。该方法利用传统的张量分解算法直接对用户-项目-上下文进行张量建摸，代替了传统的用户-项目二维矩阵，能得到较好的预测值。

本实验使用的Appazaar数据集包括〈移动用户ID，移动服务ID，移动服务使用次数，上下文信息〉，为了数据计算方便和对比明显，首先对数据集中的移动服务使用次数进行离散化，将其使用次数转化到[1,5]内，作为移动用户在特定上下文下使用移动服务的预测评分值。实验中设张量分解模型的正则化参数λ1=λ2=λ3=0.001，梯度下降法的搜索步长η=0.01。

2.3.2 结果及分析

首先比较UCS-TF算法和余弦相似性(COS)、Pearson相关系数协同过滤方法和Cosine1算法在不同邻居用户数目(K)情况下的算法性能，结果如表3所示。

由表3可知，随着K值增加，各个相似度算法平均绝对误差整体趋势都在减小，预测精度提高。在不同数量的最近邻中，UCS-TF算法比其他相似度计算方法的预测准确度都高，与余弦相似性方法、Pearson相关系数和Cosine1算法相比，表现最优时平均绝对误差减少11.1%、10.1%和3.2%(K=40)。

由图1可知，在不同数量的最近邻集合中，UCS-TF算法在P@5和P@10的准确度也是最高的，且在P@5时推荐准确度明显比其他方法高，在K=30时，比Cosine1算法提高了34.8%的准确度，比余弦相似性方法和Pearson相关系数方法分别提升了约5倍和3倍的推荐精度。这主要是因为本文在计算用户相似度时考虑了用户间上下文的相似度和相似度的可信度，充分利用了用户共有特征，能更加准确地计算用户的相似度，从而提高预测性能。

图1 各种相似度计算方法P@N比较

为了研究用户间共同项目评分对计算用户相似度的影响，本节还进行稀疏性验证。从Appazaar数据集中分别随机抽取5%、20%、50%、80%进行对比实验，并将抽取的数据集依次按照8∶2随机划分为训练集和测试集，通过与余弦相似性、Pearson相关系数方法、Cosine1算法、CARS2算法和TF算法进行比较，验证本文所提方法的有效性。实验中选取K=40，此时，本文UCS-TF算法能得到较好的预测结果。在不同数据稀疏密度下，各个算法的平均绝对误差对比如表4所示。

表4 不同数据稀疏密度下各个算法MAE值比较

由表4可知，随着数据稀疏密度减小，各算法的平均绝对误差值不断增大，说明数据稀疏性在一定程度上会降低算法的推荐准确度。其中，传统的余弦相似性和Pearson相关系数协同过滤方法的误差最大；而在此基础上进行改进的Cosine1算法、CARS2算法相对于余弦相似性和Pearson相关系数协同过滤方法能减小误差，但是误差仍然较大；而TF算法与本文的UCS-TF算法具有相近的推荐性能，但本文所提算法精度最高，整体优于其他方法。

图2(a)和图2(b)分别表示各个算法在不同数据稀疏密度下P@5和P@10的表现值，可以看出UCS-TF算法在P@5和P@10指标中都有较为明显的提升，且表现稳定。这表明UCS-TF算法在评分数据稀疏时能够较好地进行预测推荐。

图2 各种算法在不同数据稀疏密度下的P@N比较

3 结语

本文提出了一种新的计算用户上下文相似度的方法，通过用户间使用共同移动服务频次值来计算多维上下文相似度，并通过可信度进行加权，建立用户上下文相似度模型，得到目标用户的K个邻居集合，能更加准确地找到相似用户。为了处理多维上下文数据，利用邻居用户建立移动用户-上下文-移动服务三维张量分解模型，获得目标用户的移动服务预测值。实验结果表明，有效地将移动用户的上下文相似度和上下文相似可信度进行融合，能够提高推荐性能并缓解数据稀疏性。但UCS-TF算法主要通过模型计算用户间上下文的相似性，还未考虑广泛的社交关系对用户移动服务选择的影响，因此这也将成为下一步研究的重点。

References)

[1] McGRAW I, PRABHAVALKAR R, ALVAREZ R, et al. Personalized speech recognition on mobile devices [C]// ICASSP 2016: Proceedings of the 2016 IEEE International Conference on Acoustics, Speech and Signal Processing. Piscataway, NJ: IEEE, 2016: 5955-5959.

[2] BRIDA P, PICHÉ R, KOTSOPOULUS S, et al. Enabling technologies for smart mobile services [J]. Mobile Information Systems, 2016, 2016: Article ID 3196046.

[3] ASHLEY-DEJO E, NGWIRA S, ZUVA T. A survey of context-aware recommender system and services [C]// ICCCS 2015: Proceedings of the 2015 International Conference on Computing, Communication and Security. Piscataway, NJ: IEEE, 2015: 1-6.

[4] 王立才,孟祥武, 张玉洁.上下文感知推荐系统[J].软件学报,2012,23(1):1-20. (WANG L C, MENG X W, ZHANG Y J. Context-aware recommender systems [J]. Journal of Software, 2012, 23(1): 1-20.)

[5] NILASHI M, BAGHERIFARD K, IBRAHIM O, et al. Collaborative filtering recommender systems [J]. Research Journal of Applied Sciences, Engineering and Technology, 2013, 5(16): 4168-4182.

[6] SHI Y, LRASON M, HANJIALIC A. Collaborative filtering beyond the user-item matrix: a survey of the state of the art and future challenges [J]. ACM Computing Surveys, 2014, 47(1): Article No. 3.

[7] ACHAKULVISUT T, ACUNA D E, RUANGRONG T, et al. Science concierge: a fast content-based recommendation system for scientific publications [J]. PLOS ONE, 2016, 11(7): e0158423.

[8] DE CAMPOS L M, FERNNDEZ-LUNA J M, HUETE J F, et al. Combining content-based and collaborative recommendations: a hybrid approach based on Bayesian networks [J]. International Journal of Approximate Reasoning, 2010, 51(7): 785-799.

[9] 徐风苓,孟祥武,王立才.基于移动用户上下文相似度的协同过滤推荐算法[J].电子与信息学报,2011,33(11):2785-2789. (XU F L, MENG X W, WANG L C. A collaborative filtering recommendation algorithm based on context similarity for mobile users[J]. Journal of Electronics & Information Technology, 2011, 33(11): 2785-2789.)

[10] SHI Y, KARATZOGLOU A, BALTRUNAS L, et al. CARS2: learning context-aware representations for context-aware recommendations [C]// CIKM ’14: Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. New York: ACM, 2014: 291-300.

[11] ZAMMALI S, AROUR K, BOUZEGHOUB A. A context features selecting and weighting methods for context-aware recommendation [C]// COMPSAC 2015: Proceedings of the 2015 IEEE 39th Annual International Computer Software and Applications Conference. Washington, DC: IEEE Computer Society, 2015: 575-584.

[12] WASID M, KANT V, ALI R. Frequency-based similarity measure for context-aware recommender systems [C]// ICACCI 2016: Proceedings of the 2016 International Conference on Advances in Computing, Communications and Informatics. Piscataway, NJ: IEEE, 2016: 627-632.

[13] CHEN A. Context-aware collaborative filtering system: predicting the user’s preference in the ubiquitous computing environment [C]// LoCA 2005: Proceedings of the 2005 International Symposium on Location- and Context-Awareness, LNCS 3479. Berlin: Springer-Verlag, 2005: 244-253.

[14] CHOI K, SUH Y. A new similarity function for selecting neighbors for each target item in collaborative filtering [J]. Knowledge-Based Systems, 2013, 37: 146-153.

[15] KARATZOGLOU A, AMATRIAIN X, BALTRUNAS L, et al. Multiverse recommendation: n-dimensional tensor factorization for context-aware collaborative filtering [C]// Recsys 2010: Proceedings of the 4th ACM Conference on Recommender Systems. New York: ACM. 2010: 79-86.

Tensorfactorizationrecommendationalgorithmbasedoncontextsimilarityofmobileuser

YU Keqin1,2, WU Yingbo1,2*, LI Shun1,2,JIANG Jiacheng1,2, XIANG De1,2,WANG Tianhui1,2

(1.KeyLaboratoryofDependableServiceComputinginCyberPhysicalSociety(ChongqingUniversity),MinistryofEducation,Chongqing400030,China;2.SchoolofSoftwareEngineering,ChongqingUniversity,Chongqing401331,China))

To solve the problem of complex context and data sparsity, a new algorithm for the tensor decomposition based on context similarity of mobile user was proposed, namely UCS-TF (User-Context-Service Tensor Factorization recommendation). Multi-dimensional context similarity model was established with combining the user context similarity and confidence of similarity. Then,K-neighbor information of the target user was applied to the three-dimensional tensor decomposition, composed by user, context and mobile-service. Therefore, the predicted value of the target user was obtained, and the mobile recommendation was generated. Compared with cosine similarity method, Pearson correlation coefficient method and the improved Cosine1 model, the Mean Absolute Error (MAE) of the proposed UCS-TF algorithm was reduced by 11.1%, 10.1% and 3.2% respectively; and the P@N index of it was also significantly improved, which is better than that of the above methods. In addition, compared with Cosine1 algorithm, CARS2 algorithm and TF algorithm, UCS-TF algorithm had the smallest prediction error on 5%, 20%, 50% and 80% of data density. The experimental results indicate that the proposed UCS-TF algorithm has better performance, and the user context similarity combining with the tensor decomposition model can effectively alleviate the impact of score sparsity.

user context; context similarity model; data sparseness; tensor decomposition algorithm; mobile service recommendation

2017- 01- 20;

2017- 03- 12。

国家十二五科技支撑计划项目(2014BAH25F01)；国家自然科学青年基金项目(71301177)；中央高校基本科研业务费资助项目(106112014CDJZR008823)；重庆市基础科学与前沿技术研究项目(cstc2013jcyjA1658)。

余可钦(1991—)，女，湖南益阳人，硕士研究生，CCF会员，主要研究方向：上下文感知推荐系统； 吴映波(1978—)，男，湖北通城人，副教授，博士，CCF会员，主要研究方向：服务计算、软件服务工程； 李顺(1991—)，男，河南安阳人，博士研究生，CCF会员，主要研究方向：服务计算、数据挖掘； 蒋佳成(1992—)，男，四川双流人，硕士研究生，CCF会员，主要研究方向：云计算、虚拟机放置； 向德(1992—)，男，重庆石柱人，硕士研究生，CCF会员，主要研究方向：大数据流式计算的资源调度； 王天慧(1994—)，男，湖南邵阳人，硕士研究生，CCF会员，主要研究方向：用户行为分析与推荐系统。

1001- 9081(2017)09- 2531- 05

10.11772/j.issn.1001- 9081.2017.09.2531

TP311

A

This work is partially supported by the National Science and Technology Support Program of China (2014BAH25F01), the National Natural Science Foundation of China (71301177), the Fundamental Research Funds for the Central Universities (106112014CDJZR008823), the Basic and Advanced Research Program of Chongqing (cstc2013jcyjA1658).

YUKeqin, born in 1991, M. S. candidate. Her research interests include context-aware recommendation system.

WUYingbo, born in 1978, Ph. D., associate professor. His research interests include service computing, software services engineering.

LIShun, born in 1991, Ph. D. candidate. His research interests include service computing, data mining.

JIANGJiacheng, born in 1992, M. S. candidate. His research interests include cloud computing, virtual machine placement.

XIANGDe, born in 1992, M. S. candidate. His research interests include resource scheduling for large data flow computing.

WANGTianhui, born in 1994, M. S. candidate. His research interests include behavior targeting and recommendation system.