移动终端用户群体发现研究范文

摘要：针对现有方法在移动终端用户群体发现中不能兼顾社会关系和位置属性的问题，提出基于反向标签传播算法的重叠群体发现方法.根据移动终端用户的位置信息推断社会关系拓扑图，提取时空共现区.将时空共现区作为位置属性标签，标注社会关系拓扑图.在标签拓扑图上进行反向标签传播，消除节点伴随标签.经过反复迭代，在标签稳定状态下的每一个节点保留所属群体的主标签.根据用户社会关系和稳定状态下的节点主标签完成群体划分与识别.在4个真实数据集上比较反向标签传播算法与3种同类方法，实验结果表明，反向标签传播算法较好地兼顾了用户社会关系和位置属性，群体发现结果的标准互信息（NMI）与综合评价函数（F）分别比次优者平均高8.97%和3.87%.

关键词：移动终端；位置数据；重叠群体发现；反向标签传播；社会关系；位置属性

随着移动通信网络的快速发展和移动终端定位技术的广泛应用，基于位置的服务（locationbasedservices,LBS）[1]影响着人类生产生活的方方面面.通过LBS应用，移动终端用户构成了庞大的社会网络，产生了大量的位置数据.群体是指2个及以上的个体由于特定的内在因素（兴趣、目标、利益等）自发或者有组织地聚集在一起形成的集合[2].群体发现是社会网络研究的重要内容[3]，有助于进一步分析群体用户的行为模式与交互规律，实施舆情引导控制和异常群体监控[4].移动终端用户群体发现是指通过分析用户在使用LBS应用时产生的位置数据，挖掘具有相同内在因素的用户集合.复杂网络的社团挖掘方法[5]主要依据用户关系拓扑图进行聚类，忽略了用户的其他属性，难以发现属性特征相似的群体[2].移动终端用户具有较强的位置属性，复杂网络的社团挖掘方法不适用于移动终端用户的群体发现.在现有的针对位置社交网络（location-basedsocialnetwork,LB-SN）的社团挖掘方法中，Hung等[6]和Boston等[7]根据位置数据提取用户的移动行为模式，将行为模式相似的用户聚类为一个社团/群体.但是现实生活中行为模式相似的用户不一定具有社会关系，例如在相同路线经过的上班族、在同一个商圈居住的居民等，所以Boston等[7]所述方法发现的群体存在不准确性.Jayadevan等[8]根据位置共现信息估计用户社会关系强度，得到社会关系拓扑图，使用社团挖掘方法发现移动用户群体，但是该方法将共现信息转化为社会关系，弱化了用户的位置属性.假定场景：给定3个用户（1、2、3）和3个位置（Ⅰ、Ⅱ、Ⅲ）.用户1频繁出现在Ⅰ和Ⅱ，用户2频繁出现在Ⅰ和Ⅲ，用户3频繁出现在Ⅱ和Ⅲ.每2个用户通过共现位置建立了社会关系.从社会关系的角度分析，3个用户可以属于同一个群体；但是从位置属性的角度看，三者没有共同的共现位置，属于不同的群体.Lim等[9]指出时空叠加关系发现的群体以位置为中心，具有高度的位置相似性.Brown等[10]根据网络结构图和用户签到的位置信息研究同一网络中线上和线下用户群体的差异性，指出线下用户群体具有位置聚集性.Brown等[11]和Liu等[12]利用用户社会关系和签到地点双重信息发现位置社团，根据签到信息计算用户的社会关系强度，将社会关系强度作为社会关系拓扑图中边的权值，删除权值小于阈值的边，用传统社团挖掘算法发现位置社团.但是Brown等[11]和Liu等[12]将位置信息与社会关系相融合，根据社会关系拓扑图发现的群体同样可能存在位置属性不强的问题；同时移动终端上既有社交类应用，也有非社交类应用，在非社交类应用中用户间交流互动较少，无法直接提取用户的社会关系，因此Brown等[11]和Liu等[12]的方法在移动终端用户的群体发现中的普适性不强.综上所述，位置数据不能直接表达用户的社会关系，复杂网络群体发现方法不能直接用于移动用户的群体发现；同时移动用户群体具有社会关系和位置聚集双重属性，现有以复杂网络和位置社交网络为对象的社团挖掘方法难以同时兼顾社会关系和位置属性，所发现群体具有不准确性.为此，以位置信息为对象，提取用户社会关系和位置属性，将前者作为用户关系拓扑图，后者作为用户标签，并通过标签传播算法将两者结合起来，提出一种有效的移动终端用户群体发现方法.

1基本思路

移动终端用户群体发现的目的是从数量众多的用户中筛选出具有稠密社会关系和相似位置属性的用户群体.一方面，移动用户通常在多个地点签到，具有多个位置标签；另一方面，现实生活中每个用户拥有多种类型的社会关系，可能属于多个群体.同一群体成员的位置标签既有共性，也有差异.用户在某个群体中的标签差异性可能与用户所属的其他群体有关.现有方法不能很好处理上述位置属性多标签与社会关系多群体的问题.本研究提出基于反向标签传播算法（reversela-belpropagationalgorithm,Reverse-LPA）的移动终端用户重叠群体发现方法.根据签到位置信息推断移动终端用户社会关系拓扑图，提取用户的时空共现区作为标签，通过标签初始化得到标签拓扑图.在标签拓扑图上进行反向标签传播，对于节点的每个标签，依据其在邻居节点中的状态，标记其状态为“保留”或“消除”；反复迭代，根据标签的状态将符合条件标签删除，得到稳定状态的用户标签拓扑图；最终在标签拓扑图上根据节点连接关系和标签分布情况提取用户群体.

2位置数据预处理

2.1社会关系推断移动终端用户社会关系推断是指根据用户签到位置数据的时间和空间关系判断用户社会关系强度.目前常用的方法有共现频次法[13]、轨迹相似法[14]和特征提取法[15-17]等.选取马春来等[17]提出的方法，根据用户签到位置的总体属性、用户活跃性、位置多样性和位置特殊性等4类特征，使用改进的随机森林算法判断用户是否存在社会关系，在用户社会关系判断的基础上构建用户关系拓扑图.

2.2时空共现区提取d={u,p,⟨lo,la⟩}up⟨lo,la⟩zρ−τtρτzo−λsoλzc=(zρ−τt,zo−λs)zρ−τtzo−λs定义位置数据为，其中为用户，为签到时间，为经纬度.时空共现（spatio-temporalco-occurrence）[13,15]是指用户在一定的时间区间和空间区域相遇的事件，发生时空共现事件的时空区域称为时空共现区.设为以时间点为起点、时长为的时间段，为以为圆心、半径为的空间区域，为不同用户在时间段和空间区域内相遇所对应的时空共现区.使用基于密度峰值的快速聚类算法（clusteringbyfastsearchandfindofdensitypeaks，CFSFDP）[18]对位置数据进行聚类，每一个聚类簇为1个时空共现区.

3反向标签传播算法

标签传播算法（labelpropagationalgorithm,LPA）是一种复杂度较低的社团发现方法[19]，包括标签初始化、标签传播和传播停止条件3个部分.将用户时空共现区作为位置属性标签，结合标签初始化与用户社会关系拓扑图，有助于提高移动终端用户群体发现结果的准确性.因为移动终端用户通常会在多个位置签到，对应多个时空共现区，所以标签初始化后的社会关系拓扑图中的每个用户节点拥有多个标签.现有LPA大多为1个用户节点初始化1个标签，无法处理多标签的情况，因此本研究对现有的LPA进行改进，提出一种反向标签传播算法.

4Reverse-LPA可行性证明

Reverse-LPA的标签传播过程与现有的LPA差别比较大，需要证明可行性.Reverse-LPA的主要原理是在节点连接关系上经过多次传播获取标签的稳定状态，保留每个群体熵值最小的主标签.根据Reverse-LPA的标签传播过程，可以通过证明节点标签稳定状态的存在性论证Reverse-LPA的可行性.节点标签稳定状态的存在性可以从2个方面进行证明：伴随标签的稳定状态为“消除”；熵值最小主标签的稳定状态为“保留”，其他主标签的稳定状态为“消除”.

5实验及结果分析

5.1数据集简介

基于Reverse-LPA的移动终端用户群体发现方法，Boston等[7]和Jayadevan等[8]提出的对比方法只需要位置信息即可完成群体发现工作，但Liu等[12]提出的对比方法还需要用户社会关系信息，数据集需要同时具有用户签到位置和社会关系信息.本研究选取来自社交网站Gowalla、Brightkite和Foursquare上的签到位置数据，通过实验验证Reverse-LPA的有效性.Gowalla、Brightkite数据集来源于Cho等[22]的研究，数据内容主要包括用户ID、位置、时间和关注关系.Foursquare数据集来源于Bao等[23]的研究，内容包括用户身份、签到事件、地点和关注关系.由于Foursquare用户的签到频率比较稀疏，为了保证数据的可用性，选取签到事件不少于8次的用户进行实验.为了分析Reverse-LPA群体发现的准确性，利用Foursquare数据集相对丰富的用户信息，使用问卷调查获取部分用户的真实群体信息.根据身份信息和Foursquare网站定位用户的Facebook主页，获取用户的Email并且发送调查问卷.问卷内容主要包括与用户有关注关系的Foursquare用户的Face-book昵称和社会关系类型选项.根据问卷结果，将用户身份数据中家庭地址（HomeCity）一致并且有家人（Family）关系的用户划分为一个群体；将Facebook主页中工作地点（或单位）一致并且有同事（Colleague）关系的用户划分为一个群体.在49062个Foursquare用户中获取到Email账号31049个，回收有效调查问卷648份，成功划分群体154个，涉及1832个用户，命名为Fsqtrue数据集.

5.2评价指标

5.2.1标准互信息　已知群体背景信息时，使用标准互信息（normalizedmutualinformation，NMI）评价群体发现算法的性能.NMI取值范围为[0,1.0]，数值越大表明群体发现算法输出结果与群体真实结构越接近，算法性能越好.

5.3结果分析

QovSg实验结果分析包含两部分.首先在4个数据集上观察评价指标NMI、、、F在Reverse-LPA迭代过程中的变化规律，验证Reverse-LPA的可行性；其次通过比较Reverse-LPA与其他算法在数据集上的群体划分指标值.6结　语NMIF提出了基于Reverse-LPA的移动终端用户群体发现方法，根据位置数据推断用户社会关系拓扑图，提取用户时空共现区.以时空共现区为标签标记社会关系拓扑图，在标签拓扑图上进行反向标签传播.通过反复迭代，逐步消除伴随标签，最终保留每个用户所属群体的主标签.将拓扑图上拥有相同主标签的用户划分为一个群体，得到移动终端用户群体结构.Reverse-LPA算法较好地考虑了用户社会关系和位置属性，其可行性和有效性在真实数据集上得到了验证，Reverse-LPA的评价指标与分别比次优者平均高出8.97%和3.87%.今后可在此基础上进一步研究在用户社会关系类型等信息辅助下的移动终端用户群体发现方法.

作者：李志；单洪；马涛；黄郡单位：国防科技大学