Hans Journal of Data Mining 数据挖掘, 2012, 2, 38-42 http://dx.doi.org/10.12677/hjdm.2012.24008 Published Online October 2012 (http://www.hanspub.org/journal/hjdm.html) Cell Phone User Daily Mobility Pattern Analysis Based on Spectrum Clustering Method Tao Huang1, Chen Zhou2, Benxiong Huang2, Lai Tu2 1Wuhan Hongxin Communication Technology Co., Ltd., Wuhan 2The Department of Electronics and Information Engineering, Huazhong University of Science and Technology, Wuhan Email: tulai.net@gmail.com Recei ved: Au g. 9th, 2012; revised: Aug. 22nd, 2012; accepted: Sep. 6th, 2012 Abstract: Along with the development of telecommunication industry and the popularization of mobile phones, cell phones make records of human social behavior data including the call volume, calling patterns, and the location of the cellular phones of their subscribers. How to reveals the rules of human movement behavior based on those data, to make the mobility behavior prediction, has become a rising issue. This article extract characteristics of user mobility and find several kinds of their daily paths though call detail records using spectrum clustering method. The regularity of the same kind of the daily path with different time and special information has been analyzed based on statistic method. Keywords: Mobility Pattern; Spectrum Clustering; Call Detail Records 基于谱聚类的手机用户日移动行为分析 黄 涛1,周 晨2, 黄本雄 2,涂 来2 1武汉虹信通信技术有限责任公司,武汉 2华中科技大学电子与信息工程系,武汉 Email: tulai.net@gmail.com 收稿日期:2012 年8月9日;修回日期:2012 年8月22 日;录用日期:2012 年9月6日 摘 要:随着通信业的发展和手机的普及,手机记录了大量的人类社交行为数据,其中包括了每个用户每次通 话行为以及当时通话的地理位置。如何通过这些数据揭示出人类移动行为的内在规律,从而找到用户的移动特 性做出相应的移动行为预测,成为了一个重要的课题。本文通过谱聚类方法,分析手机通话数据,通过提取特 征,建立日行为路径相似度的模型,对一个典型用户的日移动行为进行同质归并处理,从而找出以天为单位相 同的移动路径。并从星期和活动地域的角度,针对聚类结果中不同簇的日移动路径分别进行了统计分析。 关键词:移动行为模式;谱聚类;用户通话清单 1. 引言 随着信息化时代的发展,人们的生活越来越离不 开手机,手机通信数据里隐藏着大量用户移动的规 律,对这些规律的研究工作不但能够提高通信运行商 的服务质量、优化网络,而且有助于揭示人类移动行 为的动态特性[1]。 目前,越来越多的研究者开始将目光投向通过手 机的通信数据,并致力于从中找出用户行为的规律, 但研究仍处于起步阶段[2]。文献[2]通过用户移动行为 模式的鉴别和分析,认为移动行为模式相近的两个陌 生用户会以更高的概率成为朋友。文献[1]通过手机通 信数据,统计了其同一位置同一时刻一星期为单位的 通话次数的分布。文献[3]通过手机通信数据,对移动 *资助信息:本文受新一代宽带无线移动通信网国家科技重大专项 (2010ZX03001-001-02)“TD-SCDMA 增强型网络优化工具研发” 资助。 Copyright © 2012 Hanspub 38 基于谱聚类的手机用户日移动行为分析 行为模式与一种传染性疾病的比较,找出了两者之间 的关联。 在研究手机的通信数据的时候,用户隐私是一个 敏感的话题,但正如文献[1]中指出,研究人员分析的 是加密后的匿名数据,目的仅是深入的研究人类的移 动行为规律及其特征,能够有效的克服传统研究中人 类行为数据不易采集的缺陷。 在人们开始试图利用手机的通信数据研究人类 移动行为之前,移动行为轨迹是一个热点。作为人类 移动行为采集工具的有 GPS、移动无线网络以及蓝牙 设备,研究致力于找出个人或是群体的移动规律、轨 迹以及交往规律[4],其他与移动规律有关的课题还包 括了动物移动特性[5]、车辆移动轨迹特征[6]、疾病传 播特性[7]等,其目的也是通过移动行为测量数据找出 规律。 与一般的移动行为数据稍稍不同的是,手机通信 数据并没有在时间上均匀的提取用户的位置信息,而 且其对地理位置的记录并不精确,仅知道通话事件发 生时手机用户大概在哪个区域,而且其区域的大小都 不相同[2]。所以,对于这类特定的数据,需要使用不 同的方法去挖掘出其中所暗含的行为特性。 本文提出了一种基于手机通信数据的分析方法, 以用户一天内经过地点的数据集合为一个单元,通过 该用户行走方位定义日移动路径相似性,再通过谱聚 类方法将其行为分为若干类。本文第二章介绍了选取 数据的规则和相似性的定义;第三章介绍了本方法中 选用的谱聚类算法的具体处理过程,第四章中展示了 聚类结果以及一些针对性的统计分析,最后一章中得 出了本文的结论以及后期工作。 2. 用户移动模型 2.1. 日移动行为指标 已有手机用户连续的u M 天的手机通信数据,包 括每次通话事件发生时的日期、时刻、服务基站标识。 每个基站都有一定的覆盖范围,不同基站的覆盖范围 是不同的。如果手机用户进入该基站的覆盖范围,并 打出或接听电话,则该基站为其服务基站。提供此次 服务的基站标识被记录在手机通信数据中。 如果合并相同的服务基站,则可以从手机用户 第天的手机通信数据中,得到 这一 天为他服 务过 的 基站标识集合 。通过基站与其覆盖范围的对应关 系,可以得到该用户这一天去过的地理区域集合 。 令为第 天基站标识集合中不同基站标识的个 数,则有 u t t B t S t ntt B tt B nS t j nn 。 2.2. 移动行为相似度 手机用户 u第i天与第天移动行为的相似度 i ij S S j ij ij nS n sNnS ij i (1) 其中令 ij j nSS 为第 天与第天该用户都去过的 地理区域的个数,而 i ij j j S i NS 为第 天与第 天该 用户去过的地理区域的总个数。 i j ij s 是一个大于等于零 小于等于 1的实数,当两天去过的区域完全相同则为 1,而当其区域完全不同时则其为零。 相似度 s 度量了两天移动行为模式的差异程度, 如果某用户周一周二有规律的上下班,而周末会在家 里休息或去购物,则可以得到周一与周二的行为相似 程度较高,而周一与周末相似程度较低。 3. 社区挖掘方法:谱聚类 3.1. 相似度矩阵 将手机用户u第i天的移动行为看做一个点, 而 两天之间的相似程度看成连接两个点的边,则用户 u M 天的通信数据,可以构造成一个图 E, u GN, 其中 为点集,其有 N M 个点, 为边的集合,是一 个 E M M 的对称矩阵,其对角线元素为 1,E的第 行 记录了第 i个点与其他各点(包括它自己)的连接程度, 是一个大于等于零小于等于1的实数,零值代表没 有连接,1代表紧密连接。 i ij E 本文通过社区挖掘方法,以将图 划分为若干个 子图的方式,将用户的日行为分为若干个行为类别。 社区挖掘方法大体分为三种,基于优化的算法、启发 式和其他[8],其中谱聚类方法属于基于优化的算法, 它将求解最小截问题转化为求解带约束的二次型优 化问题: u G T min X T X LXX 的方法,其中,向量 X 表示网络划分,L表示对称半正定矩阵,为拉普拉 斯矩阵的不同变体,它可以是 L DW也可以是 12 12 D DLDW 或是其他形式[8],其中矩阵 D 为矩阵 的度 ,将边矩W矩阵 阵 E 中不为零的数值置 Copyright © 2012 Hanspub 39 基于谱聚类的手机用户日移动行为分析 为1得到阵 W,本文采用拉普拉斯矩阵矩 L DW。 在聚类方法中,与k均值聚类不同,谱聚类不易陷 局部最优值中[8],故本文采用谱聚类分析,其较为适 合分析本文中提出的移动模型的方法。 3.2. 入 谱聚类原理与算法 文献中表述 2中提出,矩阵 [9] L 的k 零的 分, 步骤为[9]: 集的相似度矩阵 零特 量空间; 它经典聚类算 量空 在进行谱 要将相似度矩阵 三个 为其 了对角 余全 1所示 日期 将相似度矩阵 E中小于 弱连 阈值为 ,裁剪后的相似度矩阵为 重特征值为 W; 前k个 法对特征向 E所示进行 ,这是因 线元素不为零其 ,其中 35是 某个阈值的 特征向量等价于图G的k个划 且特征值为零 的特征空间被这 k个特征向量划分[9],即图 G非联通 子图的个数与L的零特征值个数相同,且每一个特征 值为 0的特征向量对应图 G的一个非联通子图一个社 区划分。 其具体 Step1 构建表示样本 Step2 通过计算W拉普拉斯矩阵L的任意 征值(小于 13 11 的特征值)与其对应的特征 向量,构建特征向 Step3 利用 k均值或其 0 间中的特征向量进行聚类。 4. 分析结果 4.1. 用户数据初始化 聚类之前, 步骤的初始化处理,使之满足运算条件。这三个 步骤分别是去零行、去孤点和去弱连接。 相似度矩阵 E某一行对角线元素不为零 对应的一天没有任何的通话行为,这一类点需要 被清洗掉,否则无法计算。 相似度矩阵E某一行除 部为零是因为其对应的一天的移动行为不与任 何一天相似,在其构造的网络拓扑图中,该点为孤岛。 该用户在这一天通话并不充分或当日移动行为异常, 无法代表其该天的移动行为轨迹,而且如果保留这类 点,会降低聚类运算的灵敏度。 处理后的相似度矩阵E如图 的个数。 第三步需要 接边去除,因为两个点虽然连接但是连接强度很 弱,很有可能是由于一些行为噪声造成的干扰,适当 的裁剪一些弱连接的边,会使得社区的主要结构更加 的明显。 令裁剪 Thr 0 E 对 应的零特征值的个数为 0 n,其聚类质量度量为 1P SSESSB 其中的簇内凝聚半径 簇间分离度 , 为 2 1 , i K i ixc SSEdist cx 2 , 11 kk ij ij SSBc c ,其 聚类结果中的第 i簇的中 , 中x为每一天的行为点为, i c 当心点,k为总的簇个数。 P 越小时,即簇内凝聚半径越小同时簇间分离度越大 时,簇分割质量好。 令0.5, 3ak 。裁剪阈值 与零特征值的个 数 Thr 0 n对 中黑色实心点所示,其中横轴为 裁剪阈值Thr 纵轴为零特征值的个数 0 n。可以看到随 应关系如图 2 05 10 15 20 25 30 35 0 5 10 15 20 25 30 35 Figure 1. Improved matrix of similarity E 图1. 处理后的相似度矩阵 E Figure 2. The relationship between clustering partition and 图2. 裁剪阈值与和簇分割效果度量的对 应关系 Thr and 0 n Thr 零特征值的个数 0 n Copyright © 2012 Hanspub 40 基于谱聚类的手机用户日移动行为分析 着裁剪阈值T的增加其对应的 特征值的个数也呈 与簇 hr 加。 中 簇分 r的增 。 阈值Thr 零 阶跃式增裁剪阈值分割效果度量 P对应 关系如图 2蓝色五角 所示,其中横轴为裁剪阈 值纵轴为量 P,可以看到 P也随着 ,而当仅有一个零特征值 由图可知 .06是最优的,本 果 阵每列对应类别如图 3所 示,谱聚类分析后的相似度矩阵如图 4所示,其中横 轴35 为天数,纵轴为簇的类别。 3中横轴代表有通话行为发生的日期,纵轴中 1~3 表了谱聚类的1~3类移动行为,可以看到 动行为较多,第 。也可以看出该用 行为较为规律, 周期性较强,一 般会以类 1行为活动3~5 天,接着按照类 3强,一般 Thr 星点 割效果度 加而递增 , 3。 Thr 裁剪阈值 时,P 文取裁剪 Th 4.2. 谱聚类结 最小 00Thr 0.0 谱聚类分析后的相似矩 图 本别代 第一类活 三类较少 户的移动 行动切换的 Figure 3. Every corresponding column of the matrix of similarity 图3. 相似矩阵每列对应类别 05 1015 2025 3035 0 会以类 1行为活动3~5 天,接着按照类 行为模式活3 5 10 15 2 0 2 5 3 0 3 5 Figure 4. The matrix of similarity after spectral clustering process 图4. 谱聚类分析后的相似度矩阵 统计 活动范围 理区域 跃1天,再以类 2移动模式活动 2~5天。图 4为谱聚 类分析后的相似度矩阵,从左上角到右下角分别为第 1~3 类行为,聚类结果其簇间干扰较少,簇内也较为 紧凑。其中类3既与类 1相似又与类 2相似,在两这 类行为间起到过渡作用。 4.3. 每类行为的活动范围 统计每类日移动行为所对应的 i i S 集合, i C为 t tC S ,其中 t S为该用户第 t天曾去过的地 第i类的日期集合。其 M 天的总活动范围 123 ,SSS 如图 5所示。 为1 S即移动行 ,S 图中红色点为类 1所对应的活动 范围 ,将 ,蓝色点为 2 S移动行为类 2所对应的活动范 围,黑色点为 3 S移动行为类 3所对应的活动范围。 由先验知识可以得知,蓝色点与红色点属于两个不同 的城区,其中一个为首要城市一个为二级城市,而黑 色点属于郊区。该用户会以天为单位,周期的穿越郊 区往返与这两个不同的城区之间。 4.4. 星期统计 即 即 M 以星期为条件 天的行为数据分为两类,统 计周 为 1的行为占 一至周五中三类行 所占的比重,以及周六周日 三类移动行为的比例,如下图6所示。 由上图可以看出,该用户在工作日类 Figure 5. , S SSS 132, 动范围 图5. 天的总活 M , S SSS 132, Copyright © 2012 Hanspub 41 基于谱聚类的手机用户日移动行为分析 Copyright © 2012 Hanspub 42 class2 weekday class3 class1 class2 weekend class1 Figure 6. Three behaviors analysis during weekday or weekend 图6. 周一至周五(weekday)及周六周日(weekend)中三类行为所 大多数,说明其在周一至周五经常在首要城市中活 动,其行为类 3也集中在工作日,说明其时常在工作 手机用户 日在两地间穿梭。而周末时,该用户类 2的占大多数, 说明其在周末会在次要城市中活动,其没有类 3的行 为,说明他很少在周末两地奔波。 5. 结论 本文从 M 天的通话记录中,提取每天的 移动特征,将一天的移动行为看成一个点,构造一 网络 类 为的地理切换界限较 明显 分布较为分散的情况下,如何去识别用户 日移 手机用户,其上班期间与下班之 后会 的移动路径、 不同 参考文献 (References) ang, T. Schoenharl, G. Madey 个 o 拓扑图。通过谱聚 方法,将日移动模式分割成 几个不同的类型,并统计了每一种日行为类型的主要 活跃地带,以及工作日与周末的因素对该用户该日的 移动行为模式的影响程度。 本文选择的典型事例用户的通话行为较多,其地 理活动范围较大,所以其日行为 h ,其工作日与周末的因素对其移动有一定的影 响,而且其在地域间往返的存在周期,其规律性较为 明显。 后续工作有几个方向,首先地理活动范围较小而 且其基站 的 f S 动行为。因为当地理活动范围较小时,以不同目 的的移动行为地域间没有明显的界限;而当基站分布 较为分散时,大多数基站都只提供过一次服务,任两 天的移动相似性很低,无法准确的找出其不同的移动 路径,不适合使用本文提出的移动行为模型。所以, 如何建立较之本文更为复杂的行为模型,能够更加准 确的更有容错性的找出用户几种不同的常用路径,是 有待解决的课题。 第二,对于城镇 有不同的移动行为,如果单以日期为单位鉴别其 路径,可能会产生一些混乱无法解释的聚类结果,的 是否可以结合时段的分类,进一步的找出用户的移动 行为规律,使其预测工作更加的准确。 第三,如何建立一种架构,将有不同 的移动模式的用户进行区分和统计。针对不同的 用户提出不同的分析方法与处理参数,当增加新用户 的时候,能够更快速准确的对其进行定位与分析。 [1] J. Candia, M. C. González, P. W and A. L. Barabási. Uncovering individual and collective human dynamics from mobile phone records. Journal of Physics A: Mathematical and Theoretical, 2008, 41: Article ID: 224015. [2] D. Wang, D. Pedreschi, C. Song, F. Giannotti and A. L. Barabási. Human mobility, social ties, and link prediction. 17th ACM SIGKDD Conference on Knowledge Discovery and Data Min- ing (KDD’11), 2011. [3] J. Tatem, Y. Qiu, D. L. Smith, O. Sabot, A. S. Ali and B. Moonen. The use of mobile phne data for the estimation of the travel patterns and imported Plasmodium falciparum rates among Zanzibar residents. Malaria Journal, 2009, 8(1): 287. [4] M. Musolesi, C. Mascolo. Mobility models for systems evalua- tion: A survey. Middleware for Network Eccentric and Mobile Applications, 2009: 43-62. [5] R. M. Fewster, C. Southwell, D. L. Borchers, S. T. Buckland and A. R. Pople. The influence of animal mobility on the assumption of uniform distances in aerial line-transect surveys. Wildlife Research, 2008, 35(4): 275-288. [6] C. Curtis, T. Perkins. Travel behaviour: A review of recent literature, 2006. ttp:www.urbanet.curtin.edu.au/local/pdf/ARC_TOD_Working_ Paper_3.pdf [7] C. Martin, P. P. Pastoret, B. Brochier, M. F. Humblet and C. Saegerman. A survey of the transmission of infectious diseases/ infections between wild and domestic ungulates in Europe. Veterinary Research, 2011, 42(1): 70. [8] B. Yang, D. Y. Liu, L. Jiming, D. Jin and H. B. Ma. Complex network clustering methods. Journal ooftware, 2009, 20(1): 54-66. [9] U. Von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 2007, 17(4): 395-416. |