Data Mining On Location-based Social Networks

Mobile Internet grows rapidly with the increasing popularity of mobile devices while social network arises along with the development of the Internet. The diversifi-cation of positioning technologies let people to acquire real-time information regarding their locations more easily. When social network comes across diversifying positioning technologies, it triggers the advent of location-based social network. On location-based social network, due to its many advantages, human mobility records get accumulated a great deal. Such a large volume of mobility data carry a variety of life styles and individual preferences. Therefore, by mining based on this data, we can find the po-tential patterns, regularity and preferences, so that we can leverage this knowledge to facilitate people daily lives and help them acquire lots of fresh and useful information. At the same time, the businesses can also benefit from the targeted advertisement and recommendation. To this end, we concentrate on mining this large scale mobility data from the past, current and future perspective. And this mining task mainly includes three problems, that is, location naming, location prediction and location recommenda-tion. However, mining on this large volume data is required to deal with many chal-lenges from scalability, data scarcity, the fusion of multiple sources and the skewness of distribution. To address these challenges, we put forward the corresponding effective approaches to solve these problems. In particular, the main results, contributions and innovations of this dissertation are summarized as follows:l)We propose location naming problem, which maps from the physical location to point-of-interest and thus automatically provides appropriate semantic names for users given their physical location. This problem is naturally boiled down to a learning to rank problem by drawing analogy between location naming and local search. Then we de-sign a local search framework, based on which we propose a user and spatio-temporal preference model(STUP) for location naming. This model takes user preference, spa- tial preference and temporal preference into account by learning-to-rank techniques. When extracting user preference, for the sake of alleviating the sparsity of user check-in history, we propose ranking-based collaborative filtering for learning user interest in user preference. Besides, in order to fuse social relationship from social network, we add a constraint that guarantees the similarity between friends’mobility pattern into the ranking-based collaborative filtering. By evaluating STUP on a check-in dataset from Dianping, we find that STUP outperforms the competing baselines, provide accurate semantic names for23.6%-26.6%test queries.2)We propose exploration prediction problem, which forecasts whether the next loca-tion has been visited before or not, thus this problem is cast into a binary classification problem. In this classification problem, we propose three types of features, includ-ing history-based features, temporal-based features and spatial-based features. These features not only reflects people personality trait of neophilia, but also indicates the current status of novelty seeking. Based on exploration prediction, we further put for-ward collaborative exploration and periodically returning(CEPR) model for location prediction so that we resort to the behavior patterns of similar users to overcome the effect of data scarcity on regular location prediction. When people are predicted as exploring, it will resort to recommending algorithm to discover potentially interesting location around their activity areas; when they are forecast as returning, it can lever-age regularity in their individual history to find the most possible candidate to visit in the next step. Such a divide-and-conquer to location history is well motivated from many different perspectives. Besides, when learning regular location prediction algo-rithms, due to the skewness of frequency distribution, we conduct Bayesian learning by means of such a prior distribution that encodes the skewness. Then these algorithms are evaluated on two check-in datasets with6M and36M check-ins, respectively. The results show that the classification error rate of exploration prediction on both dataset achieves around20%, greatly superior to the baselines. And the results indicates that CEPR can improve the prediction performance as much as30%compared to regular lo-cation prediction algorithms. Additionally, we also study the predictability of location on location-based social network and verify the existence of sequential dependence and regularity in location history.3) We propose a GeoMF model, which jointly conducts geographical modeling and ma-trix factorization, to deal with the challenge from user-POI matrix sparsity. In this model, we first propose to utilize weighted matrix factorization for POI recommen-dation from the viewpoint that check-ins provides implicit feedback since it could be better than the other methods. Then we arguments user latent factors and POI latent factors from weighted matrix factorization with users activity area vector and POIs in-fluence area vector, respectively. Based on this augmented model, we not only model spatial clustering phenomenon from the perspective of two-dimensional kernel density estimation, but it also helps to explain why modeling the spatial clustering phenomenon could deal with the problem stemming from matrix sparsity. The proposed algorithm is evaluated on a large scale check-in dataset. The evaluating results indicates that the weighted matrix factorization is superior to other competing baselines and that incorpo-rating spatial clustering phenomenon modeling into matrix factorization could improve the recommendation performance.