留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于改进重力模型的签到数据好友关系判断方法

张政 江南 曹一冰 张江水 杨振凯

张政, 江南, 曹一冰, 张江水, 杨振凯. 基于改进重力模型的签到数据好友关系判断方法[J]. 武汉大学学报 ( 信息科学版), 2022, 47(4): 604-612. doi: 10.13203/j.whugis20190180
引用本文: 张政, 江南, 曹一冰, 张江水, 杨振凯. 基于改进重力模型的签到数据好友关系判断方法[J]. 武汉大学学报 ( 信息科学版), 2022, 47(4): 604-612. doi: 10.13203/j.whugis20190180
ZHANG Zheng, JIANG Nan, CAO Yibing, ZHANG Jiangshui, YANG Zhenkai. A Method for Friendship Judgement Based on Improved Gravity Model with Check-in Data[J]. Geomatics and Information Science of Wuhan University, 2022, 47(4): 604-612. doi: 10.13203/j.whugis20190180
Citation: ZHANG Zheng, JIANG Nan, CAO Yibing, ZHANG Jiangshui, YANG Zhenkai. A Method for Friendship Judgement Based on Improved Gravity Model with Check-in Data[J]. Geomatics and Information Science of Wuhan University, 2022, 47(4): 604-612. doi: 10.13203/j.whugis20190180

基于改进重力模型的签到数据好友关系判断方法

doi: 10.13203/j.whugis20190180
基金项目: 

国家重点研发计划 2016YFB0502300

国家自然科学基金 41471336

详细信息
    作者简介:

    张政,博士生,主要研究方向为地理信息可视化与地理信息服务、空间数据挖掘、全空间信息系统。giser_zzy@163.com

    通讯作者: 江南,博士,教授。13653802609@163.com
  • 中图分类号: P208

A Method for Friendship Judgement Based on Improved Gravity Model with Check-in Data

Funds: 

The National Key Research and Development Program of China 2016YFB0502300

the National Natural Science Foundation of China 41471336

More Information
    Author Bio:

    ZHANG Zheng, PhD candidate, specializes in geographic information visualization and geographic information service, spatial data mining, pan spatial information system. E-mail: giser_zzy@163.com

    Corresponding author: JIANG Nan, PhD, professor. E-mail: 13653802609@163.com
  • 摘要: 利用签到数据进行好友关系预测是基于位置的社交网络的主要研究方向之一。由于社会关系网络数据往往事先难以获取,为了能够仅依靠位置签到数据实现好友关系判断,提出了一种基于改进重力模型的签到数据好友关系判断方法。首先,利用信息增益计算不同特征参数对好友关系的影响,并选择了用户居住地和时空共现区两个特征参数;然后,针对所选择的两个特征参数对重力模型进行改进,并利用Sigmoid函数将其值域映射到0~1,以便好友关系的判断及模型参数标定;最后,利用逻辑回归实现了模型参数的标定,并在测试数据集上实现了好友关系的预测。分别在Gowalla和Brightkite数据集上利用改进重力模型进行了交叉实验,并与好友关系概率模型进行了对比实验。结果表明,所提方法能够在仅仅依靠位置签到数据的条件下实现好友关系判断,模型在不同来源的数据之间具有较好的稳定性,且该方法的总体效果明显高于对比方法。
  • 图  1  签到数据的规则格网划分

    Figure  1.  Regular Grid Partition of Check-in Data

    图  2  关于距离的累积分布函数

    Figure  2.  Cumulative Distribution Function of Distance

    图  3  好友概率与居住地距离的函数关系

    Figure  3.  Probability of Friendship Between Two Users as a Function of Their Residence Distance

    图  4  好友概率与时空共现区个数的函数关系

    Figure  4.  Probability of Friendship Between Two Users as a Function of the Count of Co-occurrences

    图  5  Sigmoid函数图像

    Figure  5.  Graph of Sigmoid Function

    图  6  特征参数ROC曲线

    Figure  6.  ROC Curves of Characteristic Parameters

    图  7  对比实验的预测结果

    Figure  7.  Prediction Result of Contrast Experiment

    表  1  实验所用数据集

    Table  1.   Datasets Used in the Experiment

    数据集 用户数/个 签到点数/个 好友关系数/对 起止时间
    Gowalla 196 585 6 442 863 1 900 654 2009-02—2010-10
    Brightkite 58 227 4 747 178 428 156 2008-04—2010-10
    下载: 导出CSV

    表  2  不同特征参数的信息增益

    Table  2.   Information Gain of Different Characteristic Parameters

    特征参数 信息增益
    用户居住地 0.010 473
    时空共现区 0.012 467
    用户签到数目 0.000 813
    用户签到频率 0.000 452
    下载: 导出CSV

    表  3  实验结果的定量分析指标

    Table  3.   Quantitative Analysis of the Experimental Results

    数据集 指标
    不平衡度 α β 截距值 准确率 召回率 F
    Gowalla数据集 1∶3 0.948 1 2.451 2 -1.746 7 0.882 1 0.876 5 0.879 1
    1∶50 0.757 0 2.613 3 -3.242 6 0.901 2 0.875 1 0.883 4
    1∶100 0.743 6 1.226 7 -3.287 9 0.927 8 0.643 5 0.748 7
    1∶150 0.795 5 1.532 3 -4.448 1 0.946 1 0.661 2 0.778 2
    Brightkite数据集 1∶3 1.613 2 2.082 3 -1.539 2 0.871 9 0.853 2 0.862 0
    1∶50 1.285 7 1.537 6 -2.478 3 0.896 7 0.813 2 0.852 4
    1∶100 1.261 5 1.767 5 -4.111 6 0.937 7 0.732 6 0.814 5
    1∶150 1.262 2 1.875 6 -5.182 7 0.958 0 0.714 3 0.818 4
    下载: 导出CSV

    表  4  交叉对比实验的定量分析指标

    Table  4.   Quantitative Analysis of the Cross Correlation Experimental Result

    实验 准确率 召回率 F
    实验1 0.846 1 0.788 5 0.816 3
    实验2 0.859 1 0.853 7 0.856 1
    下载: 导出CSV
  • [1] 王家耀. 时空大数据时代的地图学[J]. 测绘学报, 2017, 46(10): 1226-1237 doi:  10.11947/j.AGCS.2017.20170308

    Wang Jiayao. Cartography in the Age of SpatioTemporal Big Data[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10): 1226-1237 doi:  10.11947/j.AGCS.2017.20170308
    [2] 龚健雅, 耿晶, 吴华意. 地理空间知识服务概论[J]. 武汉大学学报·信息科学版, 2014, 39(8): 883-890 doi:  10.13203/j.whugis20140119

    Gong Jianya, Geng Jing, Wu Huayi. Geospatial Knowledge Service: A Review[J]. Geomatics and Information Science of Wuhan University, 2014, 39(8): 883-890 doi:  10.13203/j.whugis20140119
    [3] 李德仁. 从测绘学到地球空间信息智能服务科学[J]. 测绘学报, 2017, 46(10): 1207-1212 doi:  10.11947/j.AGCS.2017.20170263

    Li Deren. From Geomatics to Geospatial Intelligent Service Science[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10): 1207-1212 doi:  10.11947/j.AGCS.2017.20170263
    [4] 陆锋, 刘康, 陈洁. 大数据时代的人类移动性研究[J]. 地球信息科学学报, 2014, 16(5): 665-672 https://www.cnki.com.cn/Article/CJFDTOTAL-DQXX201405002.htm

    Lu Feng, Liu Kang, Chen Jie. Research on Human Mobility in Big Data Era[J]. Journal of Geo-Information Science, 2014, 16(5): 665-672 https://www.cnki.com.cn/Article/CJFDTOTAL-DQXX201405002.htm
    [5] 罗惠, 郭斌, 於志文, 等. 基于网络拓扑和地理特征融合的朋友关系预测模型[J]. 计算机科学, 2014, 41(6): 43-47 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201406009.htm

    Luo Hui, Guo Bin, Yu Zhiwen, et al. Friendship Prediction Based on Fusion of Network Topology and Geographical Features[J]. Computer Science, 2014, 41(6): 43-47 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201406009.htm
    [6] Leskovec J, Lang K J, Dasgupta A, et al. Statistical Properties of Community Structure in Large Social and Information Networks[C]// The 17th International Conference on World Wide Web, Beijing, China, 2008
    [7] Wakita K, Tsurumi T. Finding Community Structure in Mega-Scale Social Networks: Extended Abstract[C]//The 16th International Conference on World Wide Web, Banff, Alberta, Canada, 2007
    [8] Kwak H, Choi Y, Eom Y H, et al. Mining Communities in Networks: A Solution for Consistency and Its Evaluation[C]//The 9th ACM SIGCOMM Conference on Internet Measurement Conference, Chicago, Illinois, USA, 2009
    [9] Ye M, Yin P F, Lee W C. Location Recommendation for Location-Based Social Networks[C]//The 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, San Jose, California, USA, 2010
    [10] Cho E, Myers S A, Leskovec J. Friendship and Mobility: User Movement in Location-Based Social Networks[C]//The 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, California, USA, 2011
    [11] Eagle N, Pentland A, Lazer D. Inferring Friendship Network Structure by Using Mobile Phone Data[J]. PNAS, 2009, 106(36): 15274-15278 doi:  10.1073/pnas.0900282106
    [12] Li R H, Liu J Q, 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 doi:  10.1007/s11704-013-3902-8
    [13] Crandall D J, Backstrom L, Cosley D, et al. Inferring Social Ties from Geographic Coincidences[J]. PNAS, 2010, 107(52): 22436-22441 doi:  10.1073/pnas.1006155107
    [14] Shannon C E. A Mathematical Theory of Communication[J]. The Bell System Technical Journal, 1948, 27(3): 379-423 doi:  10.1002/j.1538-7305.1948.tb01338.x
    [15] Mitchell T M. Machine Learning[M]. New York: The McGraw-Hill Companies, 1997
    [16] Scellato S, Noulas A, Lambiotte R, et al. SocioSpatial Properties of Online Location-Based Social Networks[C]//The 5th International Conference on Weblogs and Social Media, Barcelona, Catalonia, Spain, 2011
    [17] Liben-Nowell D, Novak J, Kumar R, et al. Geographic Routing in Social Networks[J]. PNAS, 2005, 102(33): 11623-11628 doi:  10.1073/pnas.0503018102
    [18] Backstrom L, Sun E, Marlow C. Find me if You Can: Improving Geographical Prediction with Social and Spatial Proximity[C]//The 19th International Conference on World Wide Web, Raleigh, North Carolina, USA, 2010
    [19] Lambiotte R, Blondel V D, De Kerchove C, et al. Geographical Dispersal of Mobile Communication Networks[J]. Physica A: Statistical Mechanics and Its Applications, 2008, 387(21): 5317-5325 doi:  10.1016/j.physa.2008.05.014
    [20] Hu Y Q, Wang Y G, Li D Q, et al. Possible Origin of Efficient Navigation in Small Worlds[J]. Physical Review Letters, 2011, 106(10): 108701 doi:  10.1103/PhysRevLett.106.108701
    [21] 马春来, 单洪, 马涛, 等. 一种基于随机森林的LBS用户社会关系判断方法[J]. 计算机科学, 2016, 43(12): 218-222 doi:  10.11896/j.issn.1002-137X.2016.12.040

    Ma Chunlai, Shan Hong, Ma Tao, et al. Random Forests Based Method for Inferring Social Ties of LBS Users[J]. Computer Science, 2016, 43(12): 218-222 doi:  10.11896/j.issn.1002-137X.2016.12.040
    [22] Cranshaw J, Toch E, Hong J, et al. Bridging the Gap Between Physical Location and Online Social Networks[C]//The 12th ACM International Conference on Ubiquitous Computing, New York, USA, 2010
    [23] 常晓猛, 乐阳, 李清泉, 等. 利用位置的虚拟社交网络地理骨干网提取[J]. 武汉大学学报·信息科学版, 2014, 39(6): 706-710 doi:  10.13203/j.whugis20140105

    Chang Xiaomeng, Yue Yang, Li Qingquan, et al. Extracting the Geographic Backbone of LocationBased Social Network[J]. Geomatics and Information Science of Wuhan University, 2014, 39(6): 706-710 doi:  10.13203/j.whugis20140105
    [24] 李雯静, 李少宁, 龙毅, 等. 利用重力模型进行GIS点群选取[J]. 武汉大学学报·信息科学版, 2013, 38(8): 945-949 http://ch.whu.edu.cn/article/id/2716

    Li Wenjing, Li Shaoning, Long Yi, et al. Point Cluster Selection in GIS Using Gravity Model[J]. Geomatics and Information Science of Wuhan University, 2013, 38(8): 945-949 http://ch.whu.edu.cn/article/id/2716
    [25] 徐睿, 梁循, 齐金山, 等. 极限学习机前沿进展与趋势[J]. 计算机学报, 2019, 42(7): 1640-1670 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201907012.htm

    Xu Rui, Liang Xun, Qi Jinshan, et al. Advances and Trends in Extreme Learning Machine[J]. Chinese Journal of Computers, 2019, 42(7): 1640-1670 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201907012.htm
    [26] 付仲良, 杨元维, 高贤君, 等. 利用多元Logistic回归进行道路网匹配[J]. 武汉大学学报·信息科学版, 2016, 41(2): 171-177 doi:  10.13203/j.whugis20150112

    Fu Zhongliang, Yang Yuanwei, Gao Xianjun, et al. Road Networks Matching Using Multiple Logistic Regression[J]. Geomatics and Information Science of Wuhan University, 2016, 41(2): 171-177 doi:  10.13203/j.whugis20150112
  • [1] 王乐洋, 孙坚强.  总体最小二乘回归预测模型的方差分量估计 . 武汉大学学报 ( 信息科学版), 2021, 46(2): 280-288. doi: 10.13203/j.whugis20180450
    [2] 赵忠国, 张峰, 郑江华.  多元自适应回归样条法的滑坡敏感性评价 . 武汉大学学报 ( 信息科学版), 2021, 46(3): 442-450. doi: 10.13203/j.whugis20190136
    [3] 魏海涛, 李柯, 赫晓慧, 田智慧.  融入空间关系的矩阵分解POI推荐模型 . 武汉大学学报 ( 信息科学版), 2021, 46(5): 681-690. doi: 10.13203/j.whugis20200355
    [4] 陶叶青, 王坚, 刘超.  附不等式约束的地表沉降时间序列自回归EIV模型 . 武汉大学学报 ( 信息科学版), 2020, 45(9): 1455-1460. doi: 10.13203/j.whugis20180268
    [5] 吕志鹏, 隋立芬.  基于变量投影法的自回归模型方差分量估计 . 武汉大学学报 ( 信息科学版), 2020, 45(2): 205-212. doi: 10.13203/j.whugis20180352
    [6] 王建民, 张锦.  基于高斯过程回归的变形智能预测模型及应用 . 武汉大学学报 ( 信息科学版), 2018, 43(2): 248-254. doi: 10.13203/j.whugis20160075
    [7] 刘耀林, 方飞国, 王一恒.  基于手机数据的城市内部就业人口流动特征及形成机制分析——以武汉市为例 . 武汉大学学报 ( 信息科学版), 2018, 43(12): 2212-2224. doi: 10.13203/j.whugis20180140
    [8] 张亦汉, 乔纪纲.  基于CA的溢油扩散时空过程模拟及敏感性分析 . 武汉大学学报 ( 信息科学版), 2017, 42(2): 208-215. doi: 10.13203/j.whugis20140719
    [9] 刘海燕, 庞小平, 王跃, 李忠香.  利用逻辑回归的南极常年考察站选址定量研究 . 武汉大学学报 ( 信息科学版), 2017, 42(3): 390-394. doi: 10.13203/j.whugis20150260
    [10] 李广春, 戴吾蛟, 杨国祥, 刘斌.  时空自回归模型在大坝变形分析中的应用 . 武汉大学学报 ( 信息科学版), 2015, 40(7): 877-893. doi: 10.13203/j.whugis20130549
    [11] 张恒才, 陆锋, 陈洁.  移动对象时空轨迹及社交关系一体化数据模型 . 武汉大学学报 ( 信息科学版), 2014, 39(6): 711-718. doi: 10.13203/j.whugis20140125
    [12] 姚宜斌, 黄书华, 陈家君.  求解自回归模型参数的整体最小二乘新方法 . 武汉大学学报 ( 信息科学版), 2014, 39(12): 1463-1466.
    [13] 常晓猛, 乐阳, 李清泉, 陈碧宇, 萧世伦, 涂伟.  利用位置的虚拟社交网络地理骨干网提取 . 武汉大学学报 ( 信息科学版), 2014, 39(6): 706-710. doi: 10.13203/j.whugis20140105
    [14] 李雯静, 李少宁, 龙毅, 邱佳.  利用重力模型进行GIS点群选取 . 武汉大学学报 ( 信息科学版), 2013, 38(8): 945-949.
    [15] 臧天宁, 云晓春, 张永铮, 门朝光.  僵尸网络关系云模型分析算法 . 武汉大学学报 ( 信息科学版), 2012, 37(2): 247-251.
    [16] 刘海庆, 夏幼明, 李晶, 尹红丽.  基于时序逻辑的多Agent系统协商模型及其推理与授权规则研究 . 武汉大学学报 ( 信息科学版), 2005, 30(9): 833-836.
    [17] 王新洲.  顾及模糊逻辑关系的稳健估计 . 武汉大学学报 ( 信息科学版), 1996, 21(4): 338-343.
    [18] 管泽霖, 鄂栋臣.  按克林索求和计算大地水准面差距垂线偏差及重力异常 . 武汉大学学报 ( 信息科学版), 1986, 11(4): 75-82.
    [19] 林森, 刘蓓蓓, 李建文, 刘旭, 秦昆, 郭桂祯.  基于BERT迁移学习模型的地震灾害社交媒体信息分类研究 . 武汉大学学报 ( 信息科学版), 0, 0(0): 0-0. doi: 10.13203/j.whugis20220167
    [20] 李杰文, 康朝贵.  一种基于时空棱柱的乘车行程可拼性判断模型 . 武汉大学学报 ( 信息科学版), 0, 0(0): -. doi: 10.13203/j.whugis20210633
  • 加载中
图(7) / 表(4)
计量
  • 文章访问数:  258
  • HTML全文浏览量:  66
  • PDF下载量:  27
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-04-29
  • 刊出日期:  2022-04-05

基于改进重力模型的签到数据好友关系判断方法

doi: 10.13203/j.whugis20190180
    基金项目:

    国家重点研发计划 2016YFB0502300

    国家自然科学基金 41471336

    作者简介:

    张政,博士生,主要研究方向为地理信息可视化与地理信息服务、空间数据挖掘、全空间信息系统。giser_zzy@163.com

    通讯作者: 江南,博士,教授。13653802609@163.com
  • 中图分类号: P208

摘要: 利用签到数据进行好友关系预测是基于位置的社交网络的主要研究方向之一。由于社会关系网络数据往往事先难以获取,为了能够仅依靠位置签到数据实现好友关系判断,提出了一种基于改进重力模型的签到数据好友关系判断方法。首先,利用信息增益计算不同特征参数对好友关系的影响,并选择了用户居住地和时空共现区两个特征参数;然后,针对所选择的两个特征参数对重力模型进行改进,并利用Sigmoid函数将其值域映射到0~1,以便好友关系的判断及模型参数标定;最后,利用逻辑回归实现了模型参数的标定,并在测试数据集上实现了好友关系的预测。分别在Gowalla和Brightkite数据集上利用改进重力模型进行了交叉实验,并与好友关系概率模型进行了对比实验。结果表明,所提方法能够在仅仅依靠位置签到数据的条件下实现好友关系判断,模型在不同来源的数据之间具有较好的稳定性,且该方法的总体效果明显高于对比方法。

English Abstract

张政, 江南, 曹一冰, 张江水, 杨振凯. 基于改进重力模型的签到数据好友关系判断方法[J]. 武汉大学学报 ( 信息科学版), 2022, 47(4): 604-612. doi: 10.13203/j.whugis20190180
引用本文: 张政, 江南, 曹一冰, 张江水, 杨振凯. 基于改进重力模型的签到数据好友关系判断方法[J]. 武汉大学学报 ( 信息科学版), 2022, 47(4): 604-612. doi: 10.13203/j.whugis20190180
ZHANG Zheng, JIANG Nan, CAO Yibing, ZHANG Jiangshui, YANG Zhenkai. A Method for Friendship Judgement Based on Improved Gravity Model with Check-in Data[J]. Geomatics and Information Science of Wuhan University, 2022, 47(4): 604-612. doi: 10.13203/j.whugis20190180
Citation: ZHANG Zheng, JIANG Nan, CAO Yibing, ZHANG Jiangshui, YANG Zhenkai. A Method for Friendship Judgement Based on Improved Gravity Model with Check-in Data[J]. Geomatics and Information Science of Wuhan University, 2022, 47(4): 604-612. doi: 10.13203/j.whugis20190180
  • 随着时空大数据时代的发展,“数据海量,知识难求”的问题日益突出,这严重阻碍了地理信息技术由数字化向智能化的转型升级[1-2]。而数据挖掘作为获取地理空间知识的重要技术,是推动实现地理信息智能化服务的关键[3]

    人类个体或群体在地理空间中的移动反映了错综复杂的人地关系[4],基于位置的社交网络通过时间序列、行为轨迹和地理位置的信息标记组合,可以帮助用户与外部世界建立更加广泛和密切的联系[5]。位置签到数据是利用带有GPS的智能终端记录某一时刻用户所处的地理空间位置、时间信息、属性信息等,其作为一种重要的众源地理空间数据为基于位置的社交网络(location based social networks,LBSN)提供了大数据支持。LBSN的发展使得大规模采集用户的位置数据成为可能,近年来,许多专家和学者面对海量位置签到数据以及用户间的社会关系网络开展了多方面的研究,主要有社交拓扑分析[6]、社区发现[7-8]、位置推荐[9]、好友关系预测[10]等。在好友关系预测方面,目前主要通过选取用户特征属性计算用户间的相似度,将相似度较高的用户之间预测为好友关系。按照依赖的数据类型,好友关系预测方法主要分为两类,一类是在位置签到数据的基础上结合已经存在的社会关系网络数据预测潜在好友关系[511],该方法的预测结果往往具有较高的正确率,但是在实际情况中,很难事先获取用户已经存在的社会关系网络数据,因此仅依靠位置签到数据来挖掘和预测好友关系更为现实。第二类方法主要依据用户访问时空共现区的频次建立相关模型进行预测[12-13],但仅仅依靠时空共现区进行预测的正确率相对较低,而且无法判断没有时空共现区的用户间关系。

    为了解决上述问题,本文提出了一种基于改进重力模型的签到数据好友关系判断方法。首先通过信息增益的方式选取了用户居住地和时空共现区作为两个特征参数,并分析了所选取的特征参数对好友关系的影响;然后通过Sigmoid函数对重力模型进行修改,使其值域映射在0~1以便于预测结果的分类;最后使用逻辑回归的方式标定了模型的参数值,通过交叉对比实验证明了本文模型的普适性。与现有模型的对比实验结果表明,本文提出的方法能够在仅仅依靠位置签到数据的条件下实现好友关系判断,且本文方法的总体效果明显高于对比方法,证明了本文模型的有效性。

    • 基于签到数据进行好友关系推理的关键在于选择合适的特征参数衡量和判断各个用户之间的关系。本文主要是基于Gowalla和Brightkite两组社交网络签到数据集进行实验和分析(见表 1),数据集中除了用户的签到数据外还包含用户间的社交关系数据,用户的签到数据是一个五元组:

      cini,j={ui,tj,Bj,Lj,lj}

      表 1  实验所用数据集

      Table 1.  Datasets Used in the Experiment

      数据集 用户数/个 签到点数/个 好友关系数/对 起止时间
      Gowalla 196 585 6 442 863 1 900 654 2009-02—2010-10
      Brightkite 58 227 4 747 178 428 156 2008-04—2010-10

      式中,cin(i,j)为第i个用户的第j条签到数据;ui为第i个用户的用户标识;tj为第j条签到数据的时间;BjLj分别为第j条签到数据的纬度和经度;lj为第j条签到数据的签到地点标识。用户间的社交关系数据是一个无向图Gs=(Us,Es),每一组数据记录了构成好友关系的用户UiUj的标识。

      本文以信息熵[14]表示社交网络中好友关系(目标属性)的信息量,利用信息增益(information gain,IG)[15]评估所选特征参数对目标属性的贡献程度。对于目标属性X和待评估特征参数Y,IG为X的信息熵H(X)与目标属性X关于待评估特征参数X的信息期望[14]的差值,计算如下:

      IG(X,Y)=H(X)-H(X | Y)

      设目标属性Xn个值{x1,x2xn}p(xi)为关于xi的概率统计函数,则信息熵计算如下:

      HX=i=1n -p(xi)log2p(xi)]

      设待评估特征参数有m个值{y1,y2ym}p(yi)为关于yi的概率统计函数,p(xi | yj)X=xiY=yi的条件概率,则信息熵计算如下:

      HX|Y=j=1mp(yi)i=1n[-p(xi |yj)log2p(xi | yj)]

      本文以Gowalla数据集中的纽约市的签到数据为例进行信息增益计算,其中用户人数n为3 101人,好友数r为10 194对,非好友数(Cn2-r)为4 796 356对,则目标属性(社交关系)的信息熵为0.021 892。选取用户居住地、时空共现区、用户签到数目、用户签到频率等几个特征参数计算信息增益,结果如表 2所示。由表 2可知,用户签到数目和用户签到时间的信息增益较小,说明其对目标属性的贡献程度较小。因此本文选取信息增益较大的用户居住地和时空共现区作为特征参数,并分别对用户居住地和时空共现区对好友关系的影响进行了分析。

      表 2  不同特征参数的信息增益

      Table 2.  Information Gain of Different Characteristic Parameters

      特征参数 信息增益
      用户居住地 0.010 473
      时空共现区 0.012 467
      用户签到数目 0.000 813
      用户签到频率 0.000 452
    • 由于签到数据中并没有明确地给出用户居住地的信息,因此本文将研究区域划分成s×s的离散规则格网,首先通过统计确定包含签到数据数量最多的格网,然后以该格网内所有签到点的中心位置作为用户居住地的预测位置,该方式的判断结果准确度可以达到85%以上[10]

    • 图 1所示,将研究区域划分成s×s大小的空间区域Ai,记各空间区域Ai包含用户签到数据的数量为ci,若Amax为各个空间区域中ci最大的区域,Amax中所包含签到数据的集合为{cin1,cin2cinn},则用户居住地位置(x¯,y¯)为:

      x¯=i=1nxin,y¯=i=1nyin

      图  1  签到数据的规则格网划分

      Figure 1.  Regular Grid Partition of Check-in Data

    • 好友之间的居住地平均距离远远小于所有用户之间的居住地平均距离[16],为了能够更加直观地分析用户居住地对好友关系的影响,本文采用累积分布函数(cumulative distribution function,CDF)描述用户居住地间的距离对好友概率的影响。设di为距离统计指标(i[0,n]),Dn个统计指标的集合,则关于距离的累积分布函数为:

      CDFDdi=P

      式中,Ddi,i[0,n]

      本文分别根据Gowalla数据集和Brightkite数据集绘制了CDF曲线,如图 2所示。由图 2可知,大约40%~50%的好友居住地距离在100 km以内,超过3%的好友居住地距离在1 km以内,这种现象在不同数据集中的表现是基本一致的,说明用户之间的好友关系很大程度上受限于空间距离,但仅仅从CDF曲线图中较难分析出好友关系与居住地距离之间的函数比例关系。

      图  2  关于距离的累积分布函数

      Figure 2.  Cumulative Distribution Function of Distance

      为了能够进一步分析好友关系是如何受限于用户居住地距离的,本文通过统计居住地距离为d的好友关系数Ld研究好友的概率P(d)与居住地距离d之间的函数关系,记Nd为用户之间居住地距离为d的数目,则有:

      Pd=LdNd

      图 3为两组数据集好友概率与居住地距离之间的函数关系图,由图 3可以发现,好友概率与居住地距离符合函数关系P(d)~d-α。文献[17-18]发现P(d)~d-1,文献[19]发现P(d)~d-2,而文献[20]发现P(d)d-1。本文结果与上述研究结果一致,且认为α的不同主要是由于数据源的类型(如微博签到数据、社交软件签到数据、移动通信数据等)不同引起的,即α值取决于数据源的类型。本文通过研究发现Gowalla数据集和Brightkite数据集的α值更接近于0.5。

      图  3  好友概率与居住地距离的函数关系

      Figure 3.  Probability of Friendship Between Two Users as a Function of Their Residence Distance

    • 文献[13]通过对Flickr数据集中带有地理标签的照片进行了分析,发现好友的概率随着时空共现区的个数增加而急剧增加,时空共现区的划分尺寸越小,好友概率越大,同时给出了好友概率-时空共现区模型。如图 1所示,假设γ为两个好友用户选择访问同一个时空区域的概率,在已知两个用户之间有k个共现区(事件Ck)的条件下,二者为好友关系(事件F)的概率[13]为:

      PF|Ck=p1kp1k+p2k(N-2)

      式中,N为用户数目;p1k=γ+1-γ/Np2k=1/N

    • 图 1所示,设Tj为持续时间为T的时间段,假设两个用户u1u2在同一时间段Tj均出现在同一空间区域Ai,则在AiTj约束条件下的区域被称为用户u1u2的时空共现区。当时间段T为2时,用户A和用户B之间的时空共现区个数k为3。时空共现区的大小s以及持续时间的长短T都会对好友关系的判断产生影响,文献[21]通过研究不同时空共现区的大小与样本数的关系,发现随着时空共现区数量的增加,样本总数迅速增加,但这并不意味好友关系的判断更加准确,而文献[22]研究表明,只有在合理的参数设置下,时空共现区的数量才与是否为好友关系密切相关。

    • 为了能够更进一步分析用户之间的时空共现区数量对好友关系的影响,本文通过统计每两个用户之间的时空共现区数量为c的好友关系数Qc,研究好友概率P(c)与时空共现区个数c之间的函数关系,记Nc为用户二元组时空共现区数量为c的数目,则有:

      Pc=QcNc

      在进行时空共现区数量统计时,每个1°格网范围内不重复统计时空共现区的个数,这样可以将全球范围划分为180×360=64 800个时空共现区。从本质上来讲,判断两两用户时空共现的条件应该是在时间段T内,两个用户签到数据之间的距离小于某一阈值,为了简化计算,本文通过判断两两用户签到数据是否在同一个划分格网来替代判断两两用户之间的距离是否小于阈值,这样时空共现区的大小s就代替了阈值。本文在实验过程中发现,如果在1°格网内重复统计时空共现区的数量,会造成好友概率P(c)对格网大小s不敏感。这是因为落在c个小尺寸时空共现区内的签到数据,有可能完全落在同一个较大尺寸的时空共现区内,例如当格网尺寸为0.01°时,c个时空共现区虽然在空间上邻近,但这并没有太多的实际意义,因为在0.01°尺寸的格网下用户大都在同一个城市范围内;而c个分布在不同城市甚至横跨整个国家的时空共现区,即使格网尺寸为1°,却更有实际意义,更能够代表两个用户之间是好友关系。

      本文对Gowalla数据集进行了实验,绘制出了好友概率与时空共现区个数的函数关系图,并根据式(8)计算出了实际值与估计值之间的误差,实验结果如图 4所示。

      图  4  好友概率与时空共现区个数的函数关系

      Figure 4.  Probability of Friendship Between Two Users as a Function of the Count of Co-occurrences

      图 4可以看出,当格网尺寸固定时,时间段T越短,时空共现区的个数越多,则好友的可能性越大;当时间段T、时空共现区个数固定时,则格网尺寸s越小,好友的可能性越大。例如,当时空共现区的数目c为3,时间段T为1 d时,s=1°的好友概率为5%左右,而s=0.001°的好友概率增长至82%左右。除此之外,时间段T越大,实际值与估计值之间的误差也越大。因此,根据上述分析,本文采用的参数值为s=0.001°,T=1 d。

    • 重力模型是以万有引力公式为依据,表达随着空间距离的增加,地理区域之间的联系强度逐步减弱的规律[23],属于一种地理空间分析模型[24]。由§1可知,随着距离的增加,用户之间的好友概率逐步减小;随着时空共现区个数的增加,用户之间的好友概率逐步增加。受此启发,本文采用重力模型来对好友关系进行判断。

    • 重力模型的基本形式如下:

      Gij=kmimjf(dij)

      式中,mimj分别是关于用户i和用户j的相关指标;一般情况下,f(dij)为关于空间距离dij的指数模型,即fdij=dij-α,其中α>0;k为重力模型的比例因子,是一个常数。

      由于好友概率与时空共现区个数基本呈现指数函数关系[13],所以利用cijβ代替mimj,其中β为两用户之间的时空共现区个数,cij为常数,则重力模型变为:

      Gij=kcijβdijα

      将式(11)两边取自然对数构建多元线性回归方程,则有:

      ln Gij=ln k+βln cij-αln dij

      式(12)是一个线性方程,只要通过样本值来标定参数αβ即可。由于ln Gij的取值范围是(-,+),但在进行好友关系判定时,这个值最好限制在[0,1]之间,因此本文对重力模型进行了改进。

    • 本文采用Sigmoid函数将ln Gij的值域映射到[0,1]之间,Sigmoid函数是一个S型函数,常常用于特征映射[25],其函数图像如图 5所示。

      图  5  Sigmoid函数图像

      Figure 5.  Graph of Sigmoid Function

      将式(12)代入到Sigmoid函数中,即可得到映射后的模型,该模型的值域为[0, 1],通过pij的值可判定两个用户之间是否是好友关系:

      pij=11+e-(ln k+βln cij-αln dij)
    • 模型的参数标定即通过样本数据,采用一元或多元回归、线性或非线性回归等,计算出回归常数项和回归系数项的过程,本文采用逻辑回归来标定模型参数。

    • 逻辑回归属于分类算法,可以处理二元分类以及多元分类问题[26],根据这一特征,可以将其用到好友关系判断问题(即“好友”或“非好友”)。设A={α1,α2αn}B={β1,β2βn}为样本输入,A为用户之间的居住地距离集,B为用户之间的时空共现区个数集。如果式(13)中pij>0.5,则分类结果为“好友”;如果pij<0.5,则分类结果为“非好友”;pij的值越靠近0.5,分类的准确率就越低,当pij=0.5时,逻辑回归模型本身无法确定分类结果。

      逻辑回归的基本步骤如下:(1)构造预测函数,即pij;(2)构造损失函数;(3)通过梯度下降法,确定损失函数的最小值及各个回归参数的值。可见除了构造预测函数之外,还需要构造合理的损失函数。

    • 损失函数就是衡量样本真实值与模型预测值之间差距的函数。当样本真值为1时,若模型的预测输出为1,损失值应尽可能为0,若模型的预测输出为0,损失值应尽量大;当样本真值为0时,若模型的预测输出为0,损失值应尽可能为0,若模型的预测输出为1,损失值应尽可能大。这里直接给出模型的损失函数为:

      L(p̑k,pk)=-[p̑klog (pk)+(1-p̑k)log (1-pk)]

      式中,pk为模型预测的输出值;p̑k为样本真实值(即“1,好友”或“0,非好友”)。从该损失函数可以看出,当p̑k分别取0或1时,其函数特性刚好满足要求。由损失函数可以得到m个训练样本的损失函数平均值为:

      Jθ=-1mk=1m[p̑klog pk+(1-p̑k)log (1-pk)]
    • 本文将社交网络签到数据集中的社交关系视为无向图GsUsEs),节点Us为用户,节点之间的边Es为用户关系(即“好友”或“非好友”),各个特征参数的值为边的属性。使用Gowalla数据集进行特征参数的有效性检验,把数据集分为训练集和测试集,再通过对模型的特征参数标定实现对好友关系的判断。

    • 分类算法只有在选取的特征参数能够较好地表征用户间的社会关系时才能够有较准确的预测结果[5]。信息增益在一定程度上可以评估特征参数的贡献程度,但并不能很好地评价特征参数的有效性。受试者工作特征曲线(receiver operating characteristic curve,ROC)是根据一系列不同的二分类方式(分界值或决定阈),以真阳性率(灵敏度)为纵坐标,假阳性率(1-特异度)为横坐标绘制的曲线,ROC曲线可以对特征参数进行有效性评价,ROC曲线下的面积(area under the curve,AUC)越接近1.0,表明结果的准确性越高,特征参数的选择就越有效果。

      本文选取Gowalla数据集中的部分用户数据进行特征参数有效性检验,随机选取600名用户共计199 317个签到数据,以当前数据集中的社交拓扑网络数据为基准值,图 6(a)为该数据集特征参数的ROC曲线图,其中,时空共现区特征参数的AUC值为0.710,用户居住地距离特征参数的AUC值为0.634,说明所选择的特征参数如果妥善设置阈值及系数时,会有一定的预测价值。为了能够确保特征参数有效性评估的普适性,本文在对比实验中选取Brightkite数据集中的部分用户数据,随机选取620名用户共计272 396个签到数据,其ROC曲线图如图 6(b)所示,其中,时空共现区特征参数的AUC值为0.760,用户居住地距离特征参数的AUC值为0.647,说明本文选取的特征参数在不同的社交网络签到数据集中具有同样的适用性。

      图  6  特征参数ROC曲线

      Figure 6.  ROC Curves of Characteristic Parameters

    • 衡量本文所提模型有效性的关键在于该模型能否通过现有的用户社交签到数据挖掘出具有好友关系的用户。本文分别在Gowalla和Brightkite数据集上验证方法的有效性,两两用户分别计算用户居住地距离d和时空共现区个数c,将现有的社交关系数据作为真值,其中0代表“非好友”,1代表“好友”,将数据分为70%的训练集和30%的测试集。由于社交网络拓扑的特点是好友关系边相对较为稀疏,也就是说,绝大多数的用户之间是非好友关系的,以Gowalla数据集在纽约市的签到数据为例,其中好友10 194对,非好友4 796 356对,数据的不平衡度约为1∶470,而研究结果表明,相对平衡的数据分布会得到较为理想的结果。

      本文随机选取Gowalla数据集中的20 000名用户,共计2 633 751条签到数据,其中社交关系数据中好友关系为840 151对,非好友关系为199 149 849对,不平衡度约为1∶240;随机选取Brightkite数据集中的20 000名用户,共计3 682 104条签到数据,其中社交关系数据中好友关系为322 664对,非好友关系为198 827 185对,不平衡度约为1∶610。为了能够考察数据不平衡度对好友关系判断结果的影响,分别将数据按照不平衡度1∶3、1∶50、1∶100和1∶150的配比输出,形成用于模型训练和测试的数据集。实验采用Python语言,通过逻辑回归实现本文所提出的模型的参数标定,模型的参数值αβ、截距(即lnk的值),以及准确率、召回率和F值(综合评价指标)的结果如表 3所示。

      表 3  实验结果的定量分析指标

      Table 3.  Quantitative Analysis of the Experimental Results

      数据集 指标
      不平衡度 α β 截距值 准确率 召回率 F
      Gowalla数据集 1∶3 0.948 1 2.451 2 -1.746 7 0.882 1 0.876 5 0.879 1
      1∶50 0.757 0 2.613 3 -3.242 6 0.901 2 0.875 1 0.883 4
      1∶100 0.743 6 1.226 7 -3.287 9 0.927 8 0.643 5 0.748 7
      1∶150 0.795 5 1.532 3 -4.448 1 0.946 1 0.661 2 0.778 2
      Brightkite数据集 1∶3 1.613 2 2.082 3 -1.539 2 0.871 9 0.853 2 0.862 0
      1∶50 1.285 7 1.537 6 -2.478 3 0.896 7 0.813 2 0.852 4
      1∶100 1.261 5 1.767 5 -4.111 6 0.937 7 0.732 6 0.814 5
      1∶150 1.262 2 1.875 6 -5.182 7 0.958 0 0.714 3 0.818 4

      表 3可以看出,随着数据不平衡度的增加,模型好友关系判断的准确率提高,而召回率和F值降低,这说明随着数据不平衡度的增加,模型更倾向于将用户之间的关系判定为非好友关系,这也与社交网络拓扑的特点相一致。即使是在不平衡度为1∶150时,该模型依然具有较高的准确率和一定的召回率,说明本文所选择的特征参数和提出的模型对于好友关系的判断具有良好的预测效果。除此之外,从不同的数据集结果来看,Brightkite数据集比Gowalla数据集有更高的准确率和召回率,即模型在Brightkite数据集上更为有效。

    • 交叉对比实验可以验证模型在不同数据集上的稳定性和适用性,即以一个数据集中的数据建立和训练模型,而以另一个数据集中的数据进行测试。

      对于交叉验证实验,本文使用§3.2.1中的数据,以70%的Gowalla数据作为训练数据,以30%的Brightkite数据作为测试数据进行实验1;反过来,以70%的Brightkite数据作为训练数据,以30%的Gowalla数据作为测试数据进行实验2。由于社交网络拓扑的好友边相对比较稀疏,不平衡度较大,为了减小数据不平衡度对判断结果的影响,实验将好友关系与非好友关系的平衡度定为1∶3,实验结果如表 4所示,实验1采用Gowalla数据集作为训练数据集构建和训练的模型,在Brightkite数据集上进行测试,得到的准确率为0.846 1,召回率为0.788 5;而实验2采用Brightkite数据集作为训练数据集构建和训练的模型,在Gowalla数据集上进行测试,得到的准确率为0.859 1,召回率为0.853 7。由表 4可以看出,交叉实验依然可以获得较为稳定和一致的结果,即本文所提出的模型在不同数据集之间具有较好的稳定性和适用性。

      表 4  交叉对比实验的定量分析指标

      Table 4.  Quantitative Analysis of the Cross Correlation Experimental Result

      实验 准确率 召回率 F
      实验1 0.846 1 0.788 5 0.816 3
      实验2 0.859 1 0.853 7 0.856 1
    • 本文采用文献[13]的好友关系概率模型,在§3.2.1中的Gowalla数据集上进行好友判断对比实验,实验结果如图 7所示。由于文献[13]中的好友关系概率模型只是给出两两用户之间的好友概率值,因此需要设置阈值δ,当概率值不小于该阈值时,用户间关系被判定为好友关系,否则为非好友关系。从图 7中可以看出,随着阈值δ的增加,准确率从0.66提高到0.83,而召回率从0.75几乎降为0。显然,本文的模型判断结果比对比方法提出的模型要好得多。

      图  7  对比实验的预测结果

      Figure 7.  Prediction Result of Contrast Experiment

    • 本文提出了基于改进重力模型的签到数据好友关系提取方法,选取Gowalla和Brightkite两组社交网络签到数据集对所选特征参数的有效性以及所构建模型对好友关系判断的准确性进行了验证,实验结果表明,本文所提出的模型和方法在仅仅依靠签到位置数据的条件下依然具有较高的准确率和召回率,且在不同的数据集上具有较为一致和稳定的结果,对好友关系的判断明显高于对比方法。

      本文目前获取到的签到数据中没有签到地点类型的相关信息,但事实上,签到地点的类型对用户时空共现区的判断是有一定影响的,比如,两个用户在商场具有许多相近的签到点,但由于商场的开放性,可能二者并非好友关系,而对于一些较为封闭的地点,如居民地、院校等,相近的签到点则代表着较高概率的好友关系。采用网络爬虫技术补充签到地点类型信息或者基于数据挖掘技术判断签到地点类型,将签到地点类型融入模型中,采用更加全面的信息建立模型来对好友关系进行判断,将是下一步工作的重点。

参考文献 (26)

目录

    /

    返回文章
    返回