一种基于随机森林的LBS用户社会关系判断方法

doi:10.11896/j.issn.1002-137X.2016.12.040

摘要/Abstract

摘要： 根据LBS用户位置信息对用户之间是否存在社会关系进行判断,是基于位置大数据的情报挖掘领域中的一个新兴问题,可为群体发现及社团划分提供信息支撑。以时空共现理论为依据,将时空共现区特征归纳为4类,提出了一种基于随机森林的用户社会关系判断方法。该方法包括特征选择和训练分类环节。首先,针对特征空间存在不相关和冗余特征而影响判断性能的问题,提出一种基于Fisher准则和χ²检验的特征选择算法,对无关、冗余特征进行剔除；然后采用随机森林进行分类判断,克服了现有方法训练速度慢、容易过拟合的问题。以LBSN用户Check-in数据为例进行的实验结果表明,该方法能够以较低的计算代价和较高的准确率实现社会关系的判断。

关键词: 基于位置的服务,时空共现,随机森林,社会关系推断

Abstract: Inferring social ties from the location information of LBS users,which can provide more information for group discovery and community detection,is now becoming a new problem in intelligence mining from location big data.Based on the theory of co-occurrences,the features of co-occurrences region were divided into four categories,and a new me-thod based on random forests for social ties inferring was proposed in this paper.The method consists of feature selection phase and classification phase.Firstly,for the problem that uncorrelatedand redundant features will affect the accuracy of result,an algorithm based on Fisher criterion and χ² test was proposed to remove the uncorrelated and redundant features.Secondly,random forests was applied in the classification to overcome the problem of existing method that training phase is slow and the model is easily over-fitting.Check-in data of LBSN users is chosen as test data in experiment,the results indicate the feasibility and effectiveness of the method.

Key words: LBS,Spatio-temporal co-occurrences,Random forests,Social ties inferring

马春来,单洪,马涛,顾正海. 一种基于随机森林的LBS用户社会关系判断方法[J]. 计算机科学, 2016, 43(12): 218-222. https://doi.org/10.11896/j.issn.1002-137X.2016.12.040

MA Chun-lai, SHAN Hong, MA Tao and GU Zheng-hai. Random Forests Based Method for Inferring Social Ties of LBS Users[J]. Computer Science, 2016, 43(12): 218-222. https://doi.org/10.11896/j.issn.1002-137X.2016.12.040

参考文献

[1] Zickuhr K.Location-based services[EB/OL].(2013-09-12)[2016-11-14].http://www.pewintemet.org/2013/09/12/location-based.services
[2] Lu X,Wetter E,Bharti N,et al.Approaching the limit of predictability in human mobility[J].Scientific Reports,2013,3(10):1-9
[3] Song C,Qu Z,Blumm N,et al.Limits of predictability in human mobility[J].Science,2010,327(5968):1018-1021
[4] Guo C,Liu J N,Fang Y,et al.Value extraction and collaborative mining methods for location big data[J].Journal of Software,2014,5(4):713-730 (in Chinese) 郭迟,刘经南,方媛,等.位置大数据的价值提取与协同挖掘方法[J].软件学报,2014,25(4):713-730
[5] Psorakis I,Voelkl B,Garroway C J,et al.Inferring social structure from temporal data[J].Behavioral Ecology and Sociobiology,2015,69(5):857-866
[6] Psorakis I,Roberts S J,Rezek I,et al.Inferring social network structure in ecological systems from spatio-temporal data streams[J].Journal of the Royal Society Interface,2012:9(76):3055-3066
[7] Jayadevan V,Bharadwaj K,Kumar A,et al.Discovering Local Social Groups using Mobility Data[J].International Journal of Computer Applications,2015,120(21):15-20
[8] Lim K H,Chan J,Leckie C,et al.Detecting location-centric communities using social-spatial links with temporal constraints[C]∥European Conference on Information Retrival.2015:489-494
[9] Yu R,He X,Liu Y.GLAD:group anomaly detection in social media analysis[C]∥Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.2014:1-7
[10] Steurer M,Trattner C.Acquaintance or partner? Predicting par-tnership in online and location-based social networks[C]∥2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM).2013:372-379
[11] Crandall D J,Backstrom L,Cosley D,et al.Inferring social ties from geographic coincidences[J].Proceedings of the National Academy of Sciences,2010,107(52):22436-22441
[12] Li R,Liu J,Yu J X,et al.Co-occurrence prediction in a large location-based social network[J].Frontiers of Computer Science,2013,7(2):185-194
[13] Cranshaw J,Toch E,Hong J,et al.Bridging the gap between physical location and online social networks[C]∥Proceedings of the 12th ACM International Conference on Ubiquitous Computing.2010:119-128
[14] Hsieh H,Yan R,Li C.Where You Go Reveals Who You Know:Analyzing Social Ties from Millions of Footprints[C]∥Procee-dings of the 24th ACM International on Conference on Information and Knowledge Management.ACM,2015:1839-1842
[15] Shokri R,Theodorakopoulos G,Danezis G,et al.Quantifying location privacy:the case of sporadic location exposure[C]∥Proceedings of the 11th International Symposium PETS 2011.2011:57-76
[16] Cho E,Myers S A,Leskovec J.Friendship and mobility:user movement in location-based social networks[C]∥Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2011:1082-1090
[17] Fernández-Delgado M,Cernadas E,Barro S,et al.Do we need hundreds of classifiers to solve real world classification problems?[J].The Journal of Machine Learning Research,2014,15(1):3133-3181
[18] Verikas A,Gelzinis A,Bacauskiene M.Mining data with random forests:A survey and results of new tests[J].Pattern Recognition,2011,44(2):330-349
[19] Gao H,Tang J,Liu H.Exploring Social-Historical Ties on Location-Based Social Networks[C]∥The 6th International Aaai Conference on Weblogs And Social Media.2012:1-8

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed