《基于时空感知的用户角色推理-胡亚慧.pdf》由会员分享，可在线阅读，更多相关《基于时空感知的用户角色推理-胡亚慧.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 38 卷第 3 期 电 子 与 信 息 学 报 Vol . 38No.3 2016 年 3 月 Journal of Electronics & Information Technology Mar . 2016 基于时空感知的用户角色推理 胡亚慧李石君*余 伟杨 莎方其庆(武汉大学计算机学院 武汉 430079) (空军预警学院 武汉 430019) 摘 要：随着大数据和信息技术的发展，更好地理解用户的行为轨迹在个性化推荐、广告推荐等方面越来越重要。该文依据大数据环境下的城市计算理论，提出一种基于情境感知的用户角色推理模型。 通过用户的行为轨迹分析其行为的时空特性；结合时间、语义分析等构
2、造识别用户角色概率推理模型；通过算法克服识别用户角色的主观性、动态适应性差等问题。实验结果证明了该文所提模型的可行性、精确性和预测准确性。 关键词：大数据；城市计算；情境感知；用户角色 中图分类号：TP391 文献标识码：A 文章编号：1009-5896(2016)03-0517-06 DOI: 10.11999/JEIT150700 Inferring Social Roles with Spatio-temporal Awareness HU YahuiLI ShijunYU WeiYANG ShaFANG Qiqing(Computer School, Wuhan University,
3、 Wuhan 430079, China) (Air Force Early Warning Academy, Wuhan 430019, China) Abstract: With the development of big data and information technology, a better understanding of users trajectories is of great importance for the design of many applications, such as personalized recommendation, behavioral
4、 targeting and computational advertising. In this paper, with the theory of urban computing based on big data, a model of recognizing information veracity of users on the social media networks is proposed. The behavior characteristics of users trajectories based on context awareness are analyzed. Th
5、e model of recognizing the truth of social roles is formalized and built. The subjectivity of recognizing users roles is overcomed. Furthermore, experiments are conducted with large-scale and real-world datasets. The results show that the proposed model offers a powerful ability for recognition of t
6、ruth social roles. Key words: Big data; Urban computing; Context awareness; Social roles 1 引言随着城市信息化、大数据分析技术和数据科学技术的不断发展，基于位置的服务(Location Based Service, LBS)作为新一代的信息网络服务方式，能够收集到带有明确地理位置坐标的数据，将地图与兴趣点(Point Of Interest, POI )有效地结合，不仅可以识别出用户的兴趣点 POI、常出入的功能区域，收稿日期： 2015-06-08；改回日期： 2015-09-16；网络出版： 2015
7、-11-19 *通信作者：李石君 基金项目：国家自然科学基金( 61272109)，中央高校基本科研业务费专项资金( 2042014kf0057)，湖北省自然科学基金( 2014CFB289)，空军预警学院青年创新基金(2013ZDJC0101) Foundation Items: The National Natural Science Foundation of China (61272109), The Fundamental Research Funds for Central Universities (2042014kf0057), The National Natural Sc
8、ience Foundation of Hubei Province of China (2014CFB289), Air Force Early Warning Academy (2013ZDJC0101) 还可以识别出所在城市的交通状况、发展状态等信息1 4。 目前，从用户的行为轨迹数据中发现其社会角色，为不同社会角色的用户提供有针对性的 服务是基于位置服务研究的一个热点5 8，其主要思想是通过轨迹聚类分析，将用户的角色按照不同的轨迹进行划分。 文献 8使用图挖掘的方法将图中具有相似结构的行为轨迹提取出来，对节点进行无监督聚类，从而实现角色提取。文献 9从轨迹时空关联语义和时态熵角度发现移
9、动对象社会角色。文献 10首次提出社交媒体中的用户具有物以类聚人以群分的特性即同质性，包括性别、年龄、宗教信仰、教育程度、职业、社会地位、网络位置、行为等。而造成同质性的原因主要有地理位置、家庭关系、所在机构。可见人的社会角色分析离不开以上这些因素。 文献 11发现具有朋友关系的用户具有相同的属518 电 子 与 信 息 学 报 第 38 卷 性，例如同一所大学的同学或者同一公司的职员具有相同的职业。但是，在进一步的研究中发现即使同一公司的职员，其分工也不同，承担的角色也就有所不同，例如设计师、工程师、销售员、经理、测试员等等。 文献 12用因子图模型实现了社交媒体的时间感知分析。 文献1 3
10、对异构网络建立了一个用户角色推理模型。 文献1 4分析了与用户角色和地位相关的社会因素和原理，并进行量化分析。 考虑到用户的角色识别，其行为轨迹离不开所在城市的功能区域划分。对于城市功能区域的识别，文献1 5通过人的行为轨迹和兴趣点 POI 能够识别出城市的功能区域。紧接着，该研究团队改进了方法，利用潜在轨迹发现功能区域16。 因此，通过用户的行为轨迹中识别出用户角色，为不同的社会角色提供有针对性的信息服务，从而提高个性化服务的质量，这也是本文研究的目的。本文的主要研究工作包括： (1)从时间序列角度分析出用户的行为特征，包括轨迹的规律性和周期性、访问频次、区域跳变性、区域游离性等特征； (2
11、)考虑到不用角色的用户在某个特定时间出现在某个位置存在着一定的规律性，结合马尔 科夫模型对用户的移动轨迹建模，从 上下文 情境感知角度推理用户角色； (3)在真实数据上进行实验分析，表明本文算法在准确率上与现有方法相比有较大的提高。 本文内容安排如下：第 1 节介绍国内外相关研究工作；第 2 节描述基于时空感知的用户行为特征；第 3 节构建基于情境感知的用户角色识别模型和算法实现过程；第 4 节通过实验验证分析了本文方法；第 5 节总结全文。 2 用户行为特征分析 首先从用户的行为轨迹中发现用户的出行规律，对其行为特征进行分析，从而为判别其角色做基础。如图 1 所示，从用户的签到数据中，将用户
12、频繁去往的位置，即 经纬度信息结合地图，将其逐一标注出来，即可得出用户常去的区域有哪些。如图 2 所示， 5 个用户(横坐标)在某天的 24 小时(纵坐标)的频繁功能区域。 定义1 时间序列 用 T=t1, t2, , ti, , tn表示。 其中， t 表示 任何两个相邻时间差，即1=iitt t。时间序列对应用户的每个签到时间。 图 1 用户行为轨迹示例 图 2 用户一天 24 小时的轨迹记录示例 定义2 功能区域和区域轨迹序列 将用户的签到数据与百度地图 API17对应获取其地理标签，从地理标签中提取诸如“学校”、“医院”、“饭店”等表示区域类型的关键词。结合文献9,16提出的基于语义的
13、 功能区域划分方法，功能 区域集合 R=r1,r2, , rl, =学校，医院， ，生活区， ，表示用户所在的不同区域。用户iu 的区域轨迹序列iR , (2) (1) , , (),ii irr rl，其中 ri(l)表示用户iu 的第 l个位置， t 表示从位置 ri(l-1)到位置 ri(l)的时间间隔。随着时间的推移，用户所在的位置是在不断变化的。任意时刻，用户都有一个物理位置与之对应。 定义3 区域访问频次 设用户iu 在访问区域所有区域驻留的总时间为iiRT 和 所有 区域访问的次数为iiRF ，如果用户iu 在区域 ()ir j 中驻留的时间和访问该区域的次数分别记为()iir
14、jT 和()iir jF ，用户iu 访问区域 ()ir j 的频次为 () ()Tim( , ( ) logiiiijrrijiiiujrRRTFTF(1) 当用户 ui访问区域 ()ir j 的频次 Tim( , ( )i iruj 时视为噪声数据， 是访问频次阈值。 定义4 区域周期性 特定角色的用户其行为轨迹在时间 序列上存在着规律性和周期性。例如公司职员、企业员工等上班族的早出晚归的生活作息，在时间和空间上的概率分布近似为高斯分布18： 2|,i r ttPt t r N (2) 第 3 期 胡亚慧等： 基于时空感知的用户角色推理 519 以功能区域： 家(H)和办公场所(W )为例
15、，用户在一天内的空间分布存在两个 2 维正态分布，且两种分布的峰值正好在家(H)和办公场所(W )17。 , , ( )| (), , ( )u iHi uiu iWN H H ct HPr r c tN W W ct W(3) 其中， ()uict表示时刻it 用户所处的状态属于 H 或 W分布。 定义5 区域游离度 某种角色的用户常常频繁往返于一个或多个区域。如学生常常往返于教室、宿舍和食堂，上班族在工作日常常往返于单位和家庭住所，即从式(3 )中找出 P ，即用户频繁游离的区域。其中， 是概率阈值。 定义6 区域跳变性 在 某一时间段内，用户平均访问区域的个数。例如出租车司机的区域跳变性
16、很高，而医生或教师每天的区域跳变性就很低，即 11Tim , ( )niitnitu r jBR(4) 当 B 时视为噪声数据， 是区域跳变阈值。 定义7 用户角色 用户的角色有多种，如医生，学生，教师，职员，销售员等。刻画一个用户的角色，可以从区域访问频次，区域亲密度，区域跳变性等方面进行逻辑推理，即 A=a1,a2,a3, = 教师，医生， 职工， 。 3 基于情境感知的用户角色识别 3.1 模型建立 为了有效地 识别用户角色，对于每一个用户的行为轨迹分别从区域，时间和用户3 维向量空间S 进行分析，如图3 所示，即 S=(R,T,U)，其中 R表示区域集合，T 表示时间集合，U 表示用户
17、集合。图中，黑色方形表示用户在某个时刻出现在某 功能 区域，白色方形表示用户在相应时刻没有出现在某 功能 区域。 图 3 基于情境感知的用户角色识别模型 假定 总共有 l 个用户， m 个区域， 用户iu 在 3 维空 间向量 S中的记录所占比例为 111, ()|=, ()mijijmilijiiujPuujrr U (5) 其中， 函数 1, ( ), ()=0, ( )iiiiurrujujjr用户访问了区域用户没有访问区域； 分母表示所有用户访问所有区域的总次数。 在 t 时间内，用户iu 访问区域 ()ir j 的概率为 1, (), ()|nitiiiirujPu jrPuU(6)
18、 分子表示用户iu 访问区域 ()ir j 的总数。 结合式(2 )和式( 3)，用户 ui访问区域 ()ir j 的时间概率分布为 2()| () ,iirj ttPt j Nr (7) 假设用户iu 的角色是教师 a1，其访问学校区域的频率应该比其他功能区域高， 且教师属于上班族，有早出晚归的工作习惯，在时间上满足式(2 )和式( 3)的概率分布。 如果用户iu 的角色是出租车司机，其访问各种功能区域的随机性很大，且在每个位置停留的时刻很短，其轨迹序列很难寻找出规律，需要通过区域访问频次、区域游离度和区域跳变性设定的阈值来衡量。但是如果用户ku 的角色是公交车司机，不仅有规律的作息时间，其
19、轨迹也具有规律性和周期性。因此很容易区别开出租车司机和公交车司机。 根据 N阶 Markov空间，用户 ui从当前 区域 ()ir j转到下一个区域 ( 1)ir j 的概率为 2,() ,( 1)( 1)| ( ) =,( 1) ,()ii iimiiii iijPurj PurjPrj rjPurj Purj(8) 其中，分子表示用户 ui在 t 时刻位于区域 ()ir j ，而在 t+1 时刻位于区域 ( 1)ir j 总数。 推理一个用户是某种角色，需要从时间概率分布上和空间区域分布上来衡量 ，即 , () ,(,)= (| ()+ ( , ( )+(1 ) ( ( +1)| ( )(
20、|)ikiikiu j aAiiri iiPa u Pt jPu j Pr j r jrPur URU (9) , (0, 1) 是权重。 如图 4 所示， 用户ui一周内在学校、医院、生活区、商业区4 个区域内访问的概率。 520 电 子 与 信 息 学 报 第 38 卷 图 4 用户 ui一周内访问不同区域的概率 3.2 算法 (1)数据预处理阶段： 为了提高数据质量需要去掉数据中的噪声数据， 在实验前先将数据集进行预处理，处理规则如下： 根据式 (1)，将用户 ui访问区域 ()ir j 的频次Tim( , ( )i iruj 的数据删除。 根据文献9,15,16 ,19以及实验发现，用
21、户访问某区域频率低于 5 次，并且在该区域停留时间低于 30 min的数据会严重降低实验的准确率， 即频次阈值 =0.1。例如，一个销售员轨迹频次太低时，他的行为 轨迹全部集中在某个区域 (如学校) ，推断模型会将该用户误判为教育人员( 教师和学生) ，从而会训练出一个错误的推断模型。根据式( 3)，概率至少要大于 20%，即概率阈值 =0.2；根据式(4 )，跳变阈值 =5。 (2)算法实现过程： 对任意用户进行角色识别算法如表 1 所示。 表1 用户角色识别算法 算法1 用户角色识别算法 输入：用户 check in 数据，城市功能区域集合 输出：用户角色集合 Map阶段 输入： , 处理
22、：以实体的 id 为键，将 value 与 ts 进行映射； Reduce阶段 输入： key=; value= 处理： for each item of D do Compute |iPu U according to 式 (5); Compute , ()iirPu j according to 式(6); Compute ( | ( )iPjrt according to 式(7); Compute ( ( +1)| ( )iiPrj rj according to 式(8); Compute (, )kiPa u according to 式(9); end for 4 实验结果与分析
23、 本实验利用虚拟化技术，通过开源的虚拟化软件 Oracle Virtualbox 将高性能 NF8560M2 服务器虚拟出 30 个主机节点，并以此为底层的分布式硬件环境。每个节点虚拟出一颗 XENO E7-4807 的 CPU和 4 G 的内存，主机采用的是 Windows Server 2008 R2 的操作系统，节点采用的是 Ubuntu 12 操作系统的 Hadoop 0.2 平台。 4.1 实验数据集 为了更充分 地 体现算法的效果，实验采用真实的数据集，数据集信息如表 2 所示。在 Gowalla 提供的数据集中抽取了 4206641 个 Gowalla 上的签到记录，这些签到记录
24、由 25653 个用户在 2009 年 1 月到 2010 年 11 月期间生成。每个签到记录包含用户 ID, POI ID, POI 地理位置坐标，签到时间。Foursquare 数据集包括 17, 908 个用户在 2010 年 1月到 2011 年 1 月期间生成的 2, 127, 401 个签到记录。将实验数据集按照 2: 8 的比例分为训练集和测试集，以验证实验的准确性和合理性。 表2 数据集信息表 GoWalla Foursquare Duration 01/2009-11/2010 01/2010-01/2011 Users 25653 17908 Check-ins 42066
25、41 2127401 Unique locations 694617 43509 Links 203502 258131 Test check-ins 3017602 1834735 4.2 评价指标 为了判断本 实验的效果，从算法的准 确性方面进行检验。 本文采用平均准确率(Precision , P)、平均召回率 (Recall, R )和 平均综合评价指标( measureF )衡量实验的准确性6,7。设候选的数据集空间 D，其中实际不一致的数据集为 IND，用本文算法自动发现的不一致数据集为 TIND，则整个算法的平均准确率： IND TINDTINDP (9) 整个算法的平均召回率：
26、 IND TINDINDR (10) 整个算法的平均综合评价指标： 第 3 期 胡亚慧等： 基于时空感知的用户角色推理 521 12 PRFPR(11) 4.3 实验结果与分析 (1)参数设置 本实验采用 2种人工标注的方式进行训练。 一种是抽验选择数据集，将数据进行人工提取，构造精确的数据集进行初始训练；另一种是根据初始训练参数进行识别，对结果进行抽验和标注，根据标注结果进行参数调整，求解满足最佳效果的参数值。 训练得到的各阈值参数如表 3 所示。 (2)准确率比较 根据轨迹语义识别用户角色特征的典型算法 MSTP20与本文算法进行比 较 (见图 5)。说明 本文算法准确率明显优于 MSTP
27、。 (3)运行时间比较 在时间效率上，使用相同规模的数据，调整分析次数，两种方法的表现结果如图 6 所示。在固定的数据规模情况下，两种方法的运行时间呈线性增长。 当数据规模增大时， MSTP 的时间复杂度为多项式，而本文 算法仍为线性时间复杂度。 5 结束语 本文将社交媒体中用户的行为轨迹和城市功能区域相结合，从而识别出用户的角色信息。依据大数据环境下的城市计算理论，提出一种基于情境感知的用户角色识别模型： (1)通过用户的行为轨迹分析其行为的时空特性； (2)综合考虑影响用户角色的多种要素结合时间、语义分析等构造识别用户角色模型；(3)通过算法克服识别用户角色的主观性、动态适应性差等问题 。
28、 实验结果表明，该模型具有更好的动态适应性和预测准确性。 表3 本文所采用的阈值参数 参数名 参数值 0.2 5 0.1 0.3 0.35 图 5 实验结果对比 图 6 性能分析曲线 参 考 文 献 1 王静远, 李超 , 熊璋, 等 . 以数据为中心的智慧城市研究综述J. 计算机研究与发展, 2014, 51(2): 239-259. WANG Jingyuan, LI Chao, XIONG Zhang, et al. Survey of data-centric smart cityJ. Journal of Computer Research and Development, 2014
29、, 51(2): 239-259. 2 李鹏, 于晓洋, 孙渤禹, 等 . 基于用户群组行为分析的视频推荐方法研究J. 电子与信息学报, 2014, 36(6): 1485-1491. doi: 10.3724/SP.J.1146.2013.01225. LI Peng, YU Xiaoyang, SUN Boyu, et al. Video recommendation method based on group user behavior analysisJ. Journal of Electronics & Information Technology, 2014, 36(6): 148
30、5-1491. doi: 10.3724/SP.J.1146.2013.01225. 3 徐风苓 , 孟祥武 , 王立才 . 基于移动用户上下文相似度的协同过滤推荐算法J. 电子与信息学报 , 2011, 33(11): 2785-2789. doi: 10.3724/SP.J.1146.2011.00384. XU Fengling, MENG Xiangwu, and WANG Licai. A collaborative filtering recommendation algorithm based on context similarity for mobile usersJ. Jo
31、urnal of Electronics & Information Technology, 2011, 33(11): 2785-2789. doi: 10.3724/SP.J.1146.2011.00384. 4 PAN Gang, QI Guande, ZHANG Wangsheng, et al. Trace analysis and mining for smart cities: Issues, methods, and applicationsJ. IEEE Communications Magazine, 2013, 51(6): 120-126. 5 王玉斌, 孟祥武, 胡勋
32、. 一种基于信息老化的协同过滤推荐算法 J. 电子与信息学报 , 2013, 35(10): 2391-2396. doi: 10.3724/SP.J.1146.2012.01473. WANG Yubin, MENG Xiangwu, and HU Xun. Information aging-based collaborative filtering recommendation algorithmJ. Journal of Electronics & Information Technology, 2013, 35(10): 2391-2396. doi: 10.3724/SP.J.11
33、46. 2012.01473. 6 YAN Zhixian, CHAKRABOTRY D, PARENT C, et al. Semantic trajectories: Mobility data computation and annotationJ. ACM Transactions on Intelligent Systems and Technology, 2012, 9(4): 39: 1-39: 34. 7 YING J J C, LEE W C, and TSENG V S. Mining 522 电 子 与 信 息 学 报 第 38 卷 geographic-temporal
34、-semantic patterns in trajectories for location predictionJ. ACM Transactions on Intelligent Systems and Technology, 2013, 5(1): 2:1-2:34. 8 HENDERSON K, GALLAGHER B, ELIASSI-RAD T, et al. RolX: Structural role extraction & mining in large graphsC. Proceeding of the 18th ACM SIGKDD International Con
35、ference on Knowledge Discovery and Data Mining, Beijing, 2012: 1231-1239. 9 马宇驰, 杨宁 , 谢琳, 等 . 基于轨迹时空关联语义和时态熵的移动对象社会角色发现 J. 计算机研究与发展 , 2012, 49(10): 2153-2160. MA Yuchi, YANG Ning, XIE Lin, et al. Social roles discovery of moving objects based on spatial temporal associated semantics and temporal ent
36、ropy of trajectoriesJ. Journal of Computer Research and Development, 2012, 49(10): 2153-2160. 10 MCPHERSON M, SMITH-LOVIN L, and COOK J M. Birds of a feather: homophily in social networks J. Annual Review of Sociology, 2001(27): 415-444. 11 MISLOVE A, VISWANATH B, KRISHNA P G, et al. You are who you
37、 know: Inferring user profiles in online social networksC. Proceedings of the 3rd International Conference on Web Search and Web Data Mining, New York, 2010: 251-260. 12 TAN Chenhao, LEE Lililan, TANG Jie, et al. User-level sentiment analysis incorporating social networksC. Proceedings of the 17th A
38、CM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, 2011: 1397-1405. 13 TANG J, LOU T, and KLEINBERG J. Inferring social ties across heterogeneous networksC. Proceedings of the 5th International Conference on Web Search and Web Data Mining, Seattle, 2012: 743-752. 1
39、4 ZHAO Yuchen, WANG Guan, YU Philip S, et al. Inferring social roles and statuses in social networksC. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, 2013: 695-703. 15 YUAN Jing, ZHENG Yu, and XIE Xing. Discovering regions of different fu
40、nctions in a city using human mobility and poisC. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, 2012: 186-194. 16 YUAN Jing, ZHENG Yu, XIE Xing, et al. Discovering urban functional zones using latent activity trajectoriesJ. IEEE Transact
41、ions on Knowledge and Data Engineering, 2015, 27(3): 712-725. 17 BAIDU. MapOL. http:/ 2012. 18 CHO E, MYERS S A, and LESKOVEC J. Friendship and mobility: User movement in location-based social networksC. Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mini
42、ng, San Diego, 2011: 1082-1090. 19 马武彬, 刘明星, 黄宏 斌 , 等 . 依据历史轨迹构建城市出租车移动概率模型J. 国防科技大学学报, 2014, 36(6): 129-134. MA Wubin, LIU Mingxing, HUANG Hongbin, et al. The moving probability model of urban cabs based on history trajectoryJ. Journal of National University of Defense Technology, 2014, 36(6): 129-
43、134. 20 YING Jiaching, LU Chan, LEE Wangchien, et al. Mining user similarity from semantic trajectoriesC. Proceedings of the 2010 International Workshop on Location Based Social Networks, San Jose, 2010: 19-26 胡亚慧： 女 ， 1980 年生， 博士生， 研究方向为数据挖掘、城市计算、大数据. 李石君： 男， 1964 年生，教授，研究方向为数据挖掘、数据库、大数据. 余 伟： 男， 1987 年生，博士，研究方向为数据挖掘、城市计算、大数据. 杨 莎： 女， 1980 年生，博士生，研究方向为数据挖掘、电子商务、大数据. 方其庆： 男， 1979 年生，博士，研究方向为数据挖掘、大数据.