第5章 实验

5.1 实验设定

数据集。本文采用[1]中提供的数据集来测试推荐系统性能，该数据集采集自美国著名基于位置的手机服务网站Foursquare，数据集中包括美国两个最大的城市——纽约（NYC）和洛杉矶（LA）——的用户的位置记录（留言），这些位置记录不止分布在这两个城市，还分布在美国其他城市和世界各地，图5.1展示了用户的位置记录的分布情况。可以看到NYC和LA用户在美国的位置记录非常多，但是在全球各地也广泛地留下了位置记录，这对于推荐系统来说是一个巨大的挑战——为用户推荐全球各地的位置是一个几乎不可能完成的任务。

因为位置推荐系统是有地域性的，所以本文将以在美国的位置记录作为测试的样本，即只推荐美国的位置，尤其是LA和NYC两个城市周围的位置（因为用户来自这两个城市，而且在这两个城市的位置记录最多），但是用户在其他地区的位置记录仍然作为分析用户偏好和计算用户相似度的依据。图5.2展示了用户的历史记录在美国的分布情况。

表5.1展示了实验数据集的统计数据，其中洛杉矶（LA）和纽约（NYC）这两列表示LA和NYC的用户的统计数据，“合并”这一列表示这两个城市用户的合并的统计数据。

实验中选取了家乡在新泽西州（NJ）的用户作为测试用户集，为了保证实验结果的准确性，进一步挑选其中留言数大于7的用户做测试，并且要求待推荐的位置在LA或者NYC附近，表5.2展示了测试集的统计数据。

基准方法。本文的方法将与下面三种基准方法做比较，分别是基于位置的协同过滤（Location-based Collaborative Filtering，简称LCF）的推荐方法、基于用户的协同过滤（User-based Collaborative Filtering，简称UCF）的推荐方法、基于偏好感知（Preference-Aware，简称PA）的推荐方法。表5.3对比了三个基准算法和本文算法的差异。

评估方法。本文采用的评估标准有两个，一是推荐的有效性，二是推荐的效率，实验中将本文提出的推荐方法与三种基准方法进行这两个标准的对比分析。

1）推荐有效性。由于在实际的基于位置的社交网络的系统来评测推荐的有效性是非常困难的，所以本文采用模拟推荐的方法对系统进行评估，将一个用户的位置记录分为两个部分：一部分是训练集，用于系统学习用户偏好；一部分是测试集，用于测试系统的性能。对于训练集，系统认为用户去过这些位置；对于测试集，系统会认为用户没有去过测试集中的位置，然后将推荐的位置与测试集中的位置进行比对，重合的位置的数目越多，说明系统的推荐性能越好。由于用户的位置记录的分布是非常广泛的（见图5.1和图5.2），所以在对用户进行位置推荐时不能是漫无目的的推荐，应该选取合理的地理范围对用户进行位置推荐，本文采用的模拟实验的评估方法如图5.3所示。

图5.3中，左半部分图中的黑色圆表示一个用户的测试集中的位置，取这些位置的最小外界矩形（MBR，即图中虚线部分）作为推荐范围；右半部分图中斜线圆表示系统为用户推荐的位置。对比这两个部分就可以对系统进行推荐有效性评估了，推荐有效性包括两个指标：准确率和召回率，它们的计算方法分别如公式(5-1)和(5-2)所示。

其中 代表正确推荐的位置的数目，N代表推荐的位置的数目，L代表需要推荐的位置的数目。以图5.3为例，推荐到的测试集中的位置的数目是2，推荐的总数目是4，因此准确率是2/4=50%；测试集中位置的总数目是3，因此召回率是2/3≈67.7%。

2）推荐效率。推荐效率主要是指在线推荐部分所消耗的时间，即在给定用户、推荐范围、推荐数目的情况下，返回推荐结果所需要的时间。推荐效率主要取决于以下两个因素：一是推荐范围的大小，二是推荐数目的多少。可以想见，推荐范围越大，推荐数目越多，推荐效率可能越低，反之亦然。因此，在接下来的实验中，对推荐效率的评估要考虑到这两个因素的变化对系统性能的影响。

5.2 实验结果

下面使用5.1节介绍的模拟实验的方法对本文提出的推荐系统的有效性和效率与基准方法进行对比评估。

5.2.1 推荐有效性

在推荐有效性的对比实验中，本文的基于位置的算法（LR）和基于用户的算法（UR）都使用了1000个热门位置，即候选位置集由群组成员访问过的位置和这1000个热门位置组成；其他三个基准算法依据上文的描述来实现。实验结果如图5.4所示。

图5.4 推荐有效性随推荐数目N的变化

图5.4展示了使用不同方法在不同的推荐数目N下的平均准确率和召回率。可以看到，基于位置的协同过滤方法（LCF）无论在准确率还是召回率上都是最好的，本文提出的基于位置的推荐方法（LR）的准确率与LCF不相伯仲（几乎完全重合），但是召回率比LCF要差一些，这是因为LCF是基于全部位置的，而LR是基于群组推荐的位置的，群组推荐的位置要比全部位置少很多，因为候选位置的数量对召回率有很大的影响，所以LR的召回率要比LCF的召回率低。本文提出的基于用户的推荐方法（UR）比基于用户的协同过滤算法（UCF）的准确率要好，而召回率要差一些，这是因为UCF和LCF一样是基于全部位置的，而UR和LR一样是基于群组推荐的位置的，所以UR的召回率比UCF低，另外由于UCF使用的用户相似度评价函数比UR简单，所以UCF的准确率比UR要低一些。图中LCF和LR的有效性明显比UCF和UR高，说明在本实验数据集中基于位置的协同过滤方法比基于用户的协同过滤方法要好，正如上文所讨论的，这并不是适用于所有推荐系统的绝对正确的结论，因为数据集特性的不同会使得不同方法的推荐效果不同。最后再来看下基于偏好感知的推荐方法（PA），它在准确率和召回率上都是介于LR和UR之间的，由于PA使用的也是基于位置的协同过滤算法，所以可以得出本文提出的LR算法比PA算法要好的结论，而在推荐数目较少时，UR的召回率比PA要高，说明UR在某些情况下也比PA要好。

图5.4中，准确率的曲线一般是逐渐下降的，而召回率的曲线一般是逐渐上升的，这是因为随着推荐数目N的增多，推荐到的正确的位置的数目的增长变缓，但其绝对数目仍然在增长。比如N=5时，系统正确推荐了3个位置，而N=10时，系统正确推荐了5个位置，可以看到多推荐的5个位置中只有2个正确的推荐，所以准确率由0.6降到了0.5，假设一共有20个位置需要被推荐，则召回率由0.15增长到0.25。

图5.4研究了推荐数目对推荐有效性的影响，其使用的用户的位置记录规模是一定的（为7），图5.5则研究位置记录规模对推荐有效性的影响，其中，推荐数目是一定的，设定N=20。

从图5.5中可以看到，随着位置记录规模的增长，五种方法的准确率都逐渐上升，尤其是LR和LCF的上升最为明显。这是因为这五种方法都是基于用户位置记录来工作的，尤其是LR和LCF方法中，位置记录的数目越多，计算两个位置的相似度就越准确，所以推荐的准确性就越高。五种方法的召回率则都有所降低，其中UR和UCF降低的幅度尤其明显，这看起来是不合理的，因为本实验采用的模拟实验方法的测试数据集的初始规模一定，如果拿出更多的位置记录作为训练集，则测试集中的位置记录规模变小，召回率应该有所增大，但是事实上，由于正确推荐的数目下降（准确率和正确推荐数目不是正相关的）的速度比测试集中的位置记录规模下降的速度快，所以整体来讲召回率会有所降低。

除了上面对比的推荐数目和位置记录规模以外，影响推荐有效性的第三个因素是位置密度，图5.6研究了位置密度对推荐有效性的影响，这里设定推荐数目N=10。

从图5.6可以看出，总体来说，准确率随着位置密度的增加而降低，召回率随着位置密度的增加而增加。直觉上，同样面积的范围里的位置越多，推荐到正确位置的概率就越低，推荐准确率就越低，实验结果证明了这个直觉的结论的正确性。召回率方面，随着位置密度的增加，候选推荐位置就越多，推荐到的可能的正确的位置就越多（与概率不同，概率是降低的，但是绝对数量是增加的），因此召回率会增大。

以上三个实验分别研究了推荐数目、位置记录规模和位置密度对推荐有效性的影响，实验结果表明本文的推荐算法比较有效，并且表明本文的基于位置的方法比基于用户的方法更加有效。

5.2.2 推荐效率

影响推荐效率的因素主要是推荐数目和推荐范围，由于本文提出的算法中，计算前N个推荐位置是通过对所有位置的协同过滤得分排序得到的，并没有使用Top-k算法，所以推荐数目对推荐效率的影响可以忽略，但是我们仍可以比较本文算法与基准算法的效率，即比较它们推荐的平均耗时，如图5.7所示。

本文实验的测试机器是一台IBM服务器，该服务器拥有6核12线程3.47GHz的Intel Xeon处理器，128G内存，运行SuSE Linux Enterprise Server 11.2系统和gcc-4.3.4。从图5.7可以看到，本文提出的推荐算法LR和UR的效率最高，即平均完成一次推荐耗时最少，其中LR算法耗时约17毫秒，UR算法耗时约12毫秒，而相比之下，UCF算法效率最差，耗时近800毫秒。分析造成这种实验结果的原因，可以发现本文提出的基于群组的推荐算法可以有效地过滤掉无关的位置，为协同过滤算法找到一个较小的候选位置集；而LCF、UCF算法由于没有使用群组对位置进行过滤，所以候选位置集很大，导致协同过滤时计算量非常大，效率较低；PA算法由于采用了偏好感知的候选挑选算法，利用“当地专家”来获取候选位置，得到的候选位置集也比较小，所以推荐效率介于本文算法和LCF/UCF算法之间。

推荐范围对推荐效率的影响主要体现在推荐范围内的位置的数量上，在位置密度一定的情况下，推荐范围越大，候选位置可能就越多，推荐效率就越差。从图5.8中可以看出本文提出的LR和UR算法随着推荐范围的增大，平均推荐时间的增长速度比其他三个方法要慢，体现出本文提出的基于群组的推荐方法在效率上有比较好的稳定性，不会随着推荐范围的增大而剧烈变化。

以上两组实验结果表明本文提出的LR和UR算法的效率显著高于其他三个基准算法，结合推荐的有效性可以知道，LR算法在有效性和效率上都有很好的表现，是一种比较好的推荐策略。

第6章 总结

本文的创新点在于基于群组进行位置推荐，大大加快了推荐算法的运行效率，并且保持了较高的有效性；本文的缺点在于对文中提出的解决方案的对比分析还不够，比如没有分析用户聚类时特征值的选取对推荐性能的影响、群组规模分布情况对推荐性能的影响等，这也是今后可以研究的方向。

参考文献

[1] Bao J, Zheng Y, Mokbel M F. Location-based and preference-aware recommendation using sparse geo-social networking data[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. ACM, 2012: 199-208.

[2] Yang D N, Shen C Y, Lee W C, et al. On socio-spatial group query for location-based social networks[C]//Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012: 949-957.

[3] Amer-Yahia S, Roy S B, Chawlat A, et al. Group recommendation: Semantics and efficiency[J]. Proceedings of the VLDB Endowment, 2009, 2(1): 754-765.

[4] Zheng Y. Computing with spatial trajectories[M]. Springer Science+ Business Media, 2011.

[5] Ye M, Yin P, Lee W C. Location recommendation for location-based social networks[C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2010: 458-461.

[6] Berjani B, Strufe T. A recommendation system for spots in location-based online social networks[C]//Proceedings of the 4th Workshop on Social Network Systems. ACM, 2011: 4.

[7] Jin Z, Shi D, Wu Q, et al. LBSNRank: personalized pagerank on location-based social networks[C]//Proceedings of the 2012 ACM Conference on Ubiquitous Computing. ACM, 2012: 980-987.

[8] Herlocker J L, Konstan J A, Borchers A, et al. An algorithmic framework for performing collaborative filtering[C]//Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 1999: 230-237.

[9] Goldberg D, Nichols D, Oki B M, et al. Using collaborative filtering to weave an information tapestry[J]. Communications of the ACM, 1992, 35(12): 61-70.

[10] Zheng Y, Zhang L, Xie X, et al. Mining interesting locations and travel sequences from GPS trajectories[C]//Proceedings of the 18th international conference on World wide web. ACM, 2009: 791-800.

[11] Kodama K, Iijima Y, Guo X, et al. Skyline queries based on user locations and preferences for making location-based recommendations[C]//Proceedings of the 2009 International Workshop on Location Based Social Networks. ACM, 2009: 9-16.

[12] Chow C Y, Bao J, Mokbel M F. Towards location-based social networking services[C]//Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Location Based Social Networks. ACM, 2010: 31-38.

[13] MacQueen J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. 1967, 1(281-297): 14.

[14] Johnson S C. Hierarchical clustering schemes[J]. Psychometrika, 1967, 32(3): 241-254.

[15] Guttman A. R-trees: a dynamic index structure for spatial searching[M]. ACM, 1984.

[16] Zheng V W, Zheng Y, Xie X, et al. Collaborative location and activity recommendations with GPS history data[C]//Proceedings of the 19th international conference on World wide web. ACM, 2010: 1029-1038.

[17] Huang W, Li G, Tan K L, et al. Efficient safe-region construction for moving top-k spatial keyword queries[C]//Proceedings of the 21st ACM international conference on Information and knowledge management. ACM, 2012: 932-941.

[18] Zhong R, Fan J, Li G, et al. Location-aware instant search[C]//Proceedings of the 21st ACM international conference on Information and knowledge management. ACM, 2012: 385-394.

[19] Sarwar B, Karypis G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th international conference on World Wide Web. ACM, 2001: 285-295.

[20] Kruk S R, Decker S. Semantic social collaborative filtering with foafrealm[J]. 2005.

[21] Eisen M B, Spellman P T, Brown P O, et al. Cluster analysis and display of genome-wide expression patterns[J]. Proceedings of the National Academy of Sciences, 1998, 95(25): 14863-14868.

[22] Gartrell M, Xing X, Lv Q, et al. Enhancing group recommendation by incorporating social relationship interactions[C]//Proceedings of the 16th ACM international conference on Supporting group work. ACM, 2010: 97-106.

[23] Chinnam N. Group Recommendation in Social Networks[R]. MARYLAND UNIV BALTIMORE DEPT OF COMPUTER SCIENCE AND ELECTRICAL ENGINEERING, 2011.

[24] Berjani B, Strufe T. A recommendation system for spots in location-based online social networks[C]//Proceedings of the 4th Workshop on Social Network Systems. ACM, 2011: 4.

[25] Ye M, Yin P, Lee W C. Location recommendation for location-based social networks[C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2010: 458-461.

[26] Chaudhuri D, Samal A. A simple method for fitting of bounding rectangle to closed regions[J]. Pattern recognition, 2007, 40(7): 1981-1989.

 

分享让更多人看到