基于地理位置的社交网络近年得到了非常多的关注。为了提升用戶粘性和吸引用戶,社交問路提供商会提供給用戶基于地理信息的广告和优惠券等服务。方了让广告和优惠券的投递更有效, 预测用戶下个可能访问的地点变得尤为重要。但是,预测地点一个不可避免的挑战就是數一百万计的候选地点构成了庞大的預測空间,使得整个预测过程变成复杂且缓慢。在本论文中,我們利用用戶签到的类別信息对潜在的用戶运动模式進行了建模并提出了一个混合隐马尔可夫模型去预测用戶下个可能访问的地点类别。基于预测出的类别,我們继而对用戶可能访问的地点进行了預測。在类別层次进行建模的好处是能有效地減少候选地点的个數并且能准确地描述用戶行动的实际意义。一般来說,用戶的行为会受到令人偏好的影响,基于这个現象,我們还运用分类的方法对用戶根据其令人愛好的不同進行了划分并对每个组群制定各自的隐马尔可夫模型。实验結果表示如果先预测用可能访问的地点类别,能使得地点预测空间极大地减少预测精度也会变高。 / 在预测用可能访问的地点之后,另外一个很重要的问题是选择将优惠券投递给哪些用从而将产品或地点的影响最大化。在实际运用中,这种将影响最大化的算法会遇到速度上的壁垒。在本论文中,我们研究了在基于地理位置的社交网络中的影响最大化问题,并提出了一个分割方法能有效地提升算法的运行速度。实验结果显示我们的算法在于业界标准方法达到几乎一致的影响力的前提下,能更快地运行。 / Location-based social networks have been gaining increasing popularity in recent years. To increase users’ engagement with location-based services, it is important to provide attractive features, one of which is geo-targeted ads and coupons. To make ads and coupons delivery more effective, it is essential to predict the location that is most likely to be visited by a user at the next step. However, an inherent challenge in location prediction is a huge prediction space, with millions of distinct check-in locations as prediction target. In this thesis we exploit the check-in category information to model the underlying user movement pattern. We propose a framework which uses a mixed hidden Markov model to predict the category of user activity at the next step and then predicts the most likely location given the estimated category distribution. The advantages of modeling on the category level include a significantly reduced prediction space and a precise expression of the semantic meaning of user activities. In addition, as user check-in behaviors are heavily influenced by their preferences, we take a clustering approach to group users with similar preferences, and train a separate hidden Markov model for each group. Extensive experimental results show that, with the predicted category distribution, the number of location candidates for prediction is much smaller, while the location prediction accuracy becomes higher. / Choosing the right users to deliver the coupons and maximizing the influence spread is also an important problem in LBSN, which is called influence maximization problem. In practice speed is an important issue to solve the influence maximization problem. In this thesis, we study the influence maximization problem in location-based social networks and propose a scalable partition approach to solve the influence maximization problem efficiently. Experimental results show that our partition approach achieves quite similar influence spread performance with the original influence maximization approach, while running much faster. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Zhu, Zhe. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 93-101). / Abstracts also in Chinese. / Abstract --- p.i / Acknowledgement --- p.vi / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background Study --- p.11 / Chapter 2.1 --- Location prediction --- p.11 / Chapter 2.2 --- Influence maximization --- p.16 / Chapter 3 --- User Activity and Location Prediction in Location-based Social Networks --- p.20 / Chapter 3.1 --- Data Analysis --- p.20 / Chapter 3.1.1 --- Data Collection --- p.21 / Chapter 3.1.2 --- Dataset Properties --- p.22 / Chapter 3.2 --- User Activity Prediction --- p.26 / Chapter 3.2.1 --- Definitions --- p.27 / Chapter 3.2.2 --- Category Prediction based on HMM --- p.28 / Chapter 3.2.3 --- Mixed HMM with Temporal and Spatial Covariates --- p.34 / Chapter 3.2.4 --- User Preference Modeling --- p.41 / Chapter 3.3 --- Location Prediction --- p.43 / Chapter 3.4 --- Experimental Evaluation --- p.45 / Chapter 3.4.1 --- Data Preparation --- p.46 / Chapter 3.4.2 --- Category Prediction --- p.47 / Chapter 3.4.3 --- Location Prediction --- p.51 / Chapter 3.5 --- Summary --- p.58 / Chapter 4 --- A Partition Approach to Scalable Influence Maximization in Location-based Social Networks --- p.60 / Chapter 4.1 --- Problem definition --- p.60 / Chapter 4.2 --- Influence probability --- p.62 / Chapter 4.2.1 --- Base model --- p.62 / Chapter 4.2.2 --- Distance and similarity model --- p.65 / Chapter 4.2.3 --- Location entropy model --- p.72 / Chapter 4.3 --- Partition approach --- p.74 / Chapter 4.4 --- Evaluation --- p.79 / Chapter 4.4.1 --- Data preparation --- p.79 / Chapter 4.4.2 --- Precision evaluation --- p.80 / Chapter 4.4.3 --- Influence spread evaluation --- p.83 / Chapter 4.4.4 --- Running time --- p.86 / Chapter 4.5 --- Summary --- p.88 / Chapter 5 --- Conclusion --- p.90 / Bibliography --- p.93
Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_328645 |
Date | January 2012 |
Contributors | Zhu, Zhe., Chinese University of Hong Kong Graduate School. Division of Information Engineering. |
Source Sets | The Chinese University of Hong Kong |
Language | English, Chinese |
Detected Language | English |
Type | Text, bibliography |
Format | electronic resource, electronic resource, remote, 1 online resource (xiv, 101 leaves) : ill. (some col.) |
Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0018 seconds