本科生毕业论文评语 学号 学生姓名邵虎专业地理信息系统 导师姓名刘瑜职称副教授 论文题目 中文 英文 支持人类移动性研究的软件平台实现 Implementation of a Software Platform for Human Mobility Research 人类移动性模式

Transcription

1 本科生毕业论文 题目 : 支持人类移动性研究的软件平台实现 Implementation of a Software Platform for Human Mobility Research 姓 名 : 邵虎 学 号 : 院 系 : 地球与空间科学学院 专 业 : 地理信息系统专业 指导教师 : 刘瑜 2011 年 6 月

2 本科生毕业论文评语 学号 学生姓名邵虎专业地理信息系统 导师姓名刘瑜职称副教授 论文题目 中文 英文 支持人类移动性研究的软件平台实现 Implementation of a Software Platform for Human Mobility Research 人类移动性模式研究目前是国际学术界研究的重点, 目前已经有许多模型被提出, 这些模型着重考虑移动中步长和角度的分布特征, 同时地理环境因素对这些分布特征的影响也是一个重要研究内容 在研究中, 基于 Monte Carlo 的模拟以及统计度量是关键 我们需要一个软件平台, 人类移动模拟和模式计算, 并考察和验证其与地理环境之间的关系 本论文工作即是这样一个软件平台的开发, 该平台采用 Java 语言, 实现了数据管理 交互与可视化 模拟轨迹生成 模式计算等功能, 对于人类移动研究具有基础 指 导 教 性的意义 论文开发工作量大, 结构合理, 书写规范 师 评 语 指导教师签字 : 年月日

3 支持人类移动性研究的软件平台实现 摘要 每个人的出行轨迹都看似杂乱无章, 然而, 大量人群的轨迹集合背后, 却可能隐含着特定的行为模式 研究和揭示人类移动行为背后的规律, 已经成为近年来国内外 GIS 界研究的热点 然而当前并没有一个比较通用的软件来支持这一研究过程, 因此, 笔者在毕业设计中试图实现一款软件平台, 来辅助人类移动性的研究 本文将针对该款软件的理论基础 软件设计和实现等进行简要的描述 关键词 : 人类移动性研究软件设计利维飞行

4 Implementation of a Software Platform for Human Mobility Research Shao Hu (Geographic Information System) Supervised by Liu Yu Abstract The trajectory of individual seems disorderly and irregular. However, there may exist simple reproducible patterns behind huge sample s trajectories. It has been a research focus to explore and reveal the regularity behind human s movement behavior in recent years. Unfortunately, there does not exist a common software tool to support this research. We thus implemented a software platform that can support human mobility research. In this paper, we will simply describe the basic theories of this software, the software design and how the software platform works. Keywords: human mobility research, software design, levy flight

5 目录 1. 导论 关于人类移动性的基础知识介绍 随机行走 (random walk) 布朗运动(Brownian motion) 和利维飞行 (Levy flight) 指数分布 幂律分布 利用不同分布进行轨迹模拟的效果比较 回转半径 (Radius of Gyration) 特征向量 (Eigenvector) 熵 (Entropy) 软件平台架构设计 软件基本功能需求定义 软件构架 关键类及接口介绍 软件实现中的关键技术描述 软件平台效果展示 总结和展望 参考文献 致谢... 37

6 1. 导论 从人口的迁徙到电子病毒的传播, 从城市规划到流行病的防治, 再到移动通 信资源的合理利用甚至是气候变化的研究, 一系列的实际应用都依赖于我们能够 准确预测人类在下一刻位置的能力 (Song, et al., 2010) 人类移动性 (human mobility) 的研究近年来已经成为地理信息系统领域的热点 人们生活在一定的空间范围内, 其出行 工作 旅游 购物等活动都可以和 相应的空间位置点联系起来, 在一定时间范围内形成连续的时空轨迹 每个个体 的移动轨迹看似杂乱且没有规律 ; 然而, 大规模人群移动轨迹集合背后却可能隐 藏着特定的统计规律 Barabási 等人发现, 人类可以通过其行为方式来表征 (characterized): 根据对大量样本实时追踪数据的分析表明, 尽管人们之间的出行 历程各不相同且丰富多样, 但仍然遵从简单的重复模式 (González, et al., 2008) 这就说明, 从大量轨迹样本集合中提取出人类的行为模式和遵从的规律, 并进一 步应用于研究是可能的 现代信息通讯技术的快速发展, 使得通过基于位置感知设备获取海量个体的 移动信息成为可能 诸多研究通过分析不同尺度下大样本人类移动轨迹, 都发现 其遵从一定的统计规律 并且可以将得到的规律进一步扩展, 用于解决实际问题 Chaintreau 等人通过 WiFi GSM 以及 imote 1 等技术, 获得在剑桥 香港 MIT 等不同大学内的 8 个数据集 通过分析不同设备的 通讯间隔时间 2, 他们发现 通讯间隔时间更加服从幂律分布 (Power Law Distribution) 而不是目前大多数移 动模型中默认使用的指数分布 利用幂律分布规律和 imote 获得的用户位置样本 信息, 他们建立了新的移动设备通讯模型, 并根据该模型设计了优化的信息传送 算法 (opportunistic forwarding algorithm) 应用于手持移动设备 (Chaintreau, et al., )(Hui, et al., 2005)(Hui, et al., 2008) Rhee 等人通过收集分布在不同区域下 1 small portable wireless radio devices: 小型便携无线发射设备 2 intercontact time: 定义为一对通讯设备在两次成功连接之间的间隔时间 3 大学校园 曼哈顿市区 迪斯尼主题公园和农牧产品交易会 1

7 多个志愿者超过 1000 小时的 GPS 位置数据, 通过分析发现这些轨迹具有 无标度 (scale free) 和不符合中心极限等的特性 在常用的数据模型中, 利维飞行 (Levy flight or Levy walk) 比布朗运动 (Brown motion) 和随机行走 (Random way point) 模型更加符合实际的轨迹特征 他们以此进行了新的模拟并且设计了新的移动网络路由协议 (Rhee, et al., 2008) 在对流感传播模型研究中,Merler 和 Ajelli 不但考虑了疾病的传播特性和机制, 同时考虑到了人口异质性 (population heterogeneity) 和人类移动性 ( 这里主要是幂律分布和指数分布 ) 对疾病传播的影响 建立了覆盖欧洲 37 个国家的随机 空间直观和基于个体的流感传播仿真模型, 使得对疾病进行定量化预测和控制成为可能 (Merler, et al., 2010) 图 1. 人类移动性在疾病传播模型中的应用, 图中为欧洲的航空运输量 其中 : 绿色为小于 10 4 人 / 年, 黄色为 人 / 年, 橙色为 人 / 年, 红色为 人 / 年, 紫色为大于 10 8 人 / 年 (Merler, et al., 2010) 从上面的例子可以看到 : 目前人类移动性的研究不但已经成为学界研究的热点, 并且一些成果已经应用到不同的领域, 解决一些实际的问题 其研究的方法或过程主要可以归纳为以下几步 :i. 数据的获取 :GPS 手机 wifi 浮动车(floating car) 调查采访 研究人类有关的物品的流动( 如货币 ) 甚至是动物的移动轨迹等等 科技的进步使得我们获取数据的手段和获取的数据质量都在不断提高 ii. 数据的格式化 整理和表达, 包括转换为统一处理格式 去除奇异点 单位归一 2

8 化 投影显示等等 iii. 数据分析和模式 模型的提取 利用一些可以反映个体行为特征的指标结合统计学知识来提取大量个体时空轨迹背后隐含的行为模式, 利用不同的分布函数对轨迹的时空特征进行拟合, 建立一定的模型, 甚至试图解释这种行为模式下的动力学特征 iv. 利用 iii 步中建立起来的模型进行仿真模拟, 同时和实际数据进行对比, 验证模型精度 v. 应用得到的模型来解决实际问题, 如上文提到的优化移动网络传输算法 传染病控制 城市建设等等 针对以上提到的一般性研究过程, 如果能有一个专业的分析工具, 可以将不同的数据整合起来, 解决 ii iii iv 步中的问题 提取轨迹的时空特征 进行相应的统计分析 仿真模拟, 那将具有非常重大的意义 这就是笔者本科毕业设计主要进行的工作 本论文接下来的内容将按照如下方式组织 : 第 2 部分介绍目前一些研究所证实的轨迹特征和服从的分布方式, 以及用于描述个体移动轨迹的一些特定指标 第 3 部分主要介绍软件系统架构和主要功能 第 4 部分介绍软件实现和功能展示 第 5 部分介绍研究中仍存在的问题以及软件需要进一部完善的地方 2. 关于人类移动性的基础知识介绍 2.1 随机行走 (random walk) 布朗运动 (Brownian motion) 和利 维飞行 (Levy flight) 我们软件平台的核心任务之一就是要利用随机模型对人类的出行轨迹进行模拟, 因此首先我们对随机行走的一些概念进行简要的介绍 随机行走 ( 或随机游走 ) 指的是由连续的随机步骤构成的轨迹, 以及对其所进行的数学形式化表达 例如在气体或液体中运动的分子的路径踪迹, 动物的觅食轨迹或者股票的价格波动等等 随机行走的概念最早由 Karl Pearson 在 1905 年引入 (Pearson, 1905), 并被广泛应用于生态 经济 心理 计算机 物理 化学等领域 3

9 从随机行走的概念可以看出, 其定义是比较宽泛的, 在实际应用中会采用很多的特定形式 例如比较著名的醉汉模型 (drunkard's walk) 或者我们后面将要提到的利维飞行, 都属于随机行走的特例 一个比较常见的随机行走模型是在二维规则格网 (regular lattice) 中的随机行走 每一步都只能走向和当前格网相邻的 4 个格网中, 向 4 个方向行走的概率相同 图 2 展示了一个二维规则格网的随机行走过程 图 2. 二维规则格网中的随机行走模拟 在显微镜下看起来连成一片的液体, 实际上是由许许多多分子组成的 液体分子不停地做无规则的运动, 不断地随机撞击悬浮微粒 悬浮的微粒足够小时, 受到的来自各个方向的液体分子的撞击作用是不平衡的 在某一瞬间, 微粒在另一个方向受到的撞击作用强, 致使微粒又向其它方向运动 这样, 就引起了微粒的无规则的布朗运动 布朗运动主要用于对液体或气体中分子运动的描述, 以及对这一类随机运动的数学模拟, 因此这一类的数学理论也常被称为粒子理论 (particle theory) 布朗运动数学模型在实际中也有广泛的应用, 如常被应用于对股价的预测中 爱因斯坦等人曾对布朗运动进行详细的论证和推导 (Einstein, 1956), 数学上 4

10 用维纳过程 (Wiener process) 来描述布朗运动 维纳过程 W t ( 时间 t 的函数 ) 满足以下三个条件 :i.w 0 = 0; ii. W t 是连续函数 ;iii. W t 是独立增量过程并且其增量服从分布 :W t W s ~N(0, t s)( 对所有 0 s t), 其中 N(μ, σ 2 ) 满足均值是 μ, 方差为 σ 2 的正态分布 (Morters, et al., 2008) 布朗运动如图 3 所示 图 3. 布朗运动展示, 图中为 3 条实际的乳胶微粒布朗运动轨迹 液体中微粒 ( 如 花粉 ) 轨迹的获取方式一般为每隔固定时间 ( 如 20 秒 ), 记录一次微粒的位置, 并连续地将微粒位置在坐标纸上绘制出来, 得到连续的布朗运动轨迹 法国数学家皮埃尔 保罗 利维 (Paul Pierre Lévy, ) 曾提出下面 这样的问题 : 是否存在这样 N 个变量 (X 1, X 2, X N ), 他们服从独立同分布并且满 足他们的概率之和 X 1 + X X N 具有相同的函数形式? 如果存在, 该函数形 式有将是怎样的? 符合以上要求的概率密度函数都可以称之为利维飞行 (Gutowski, 2001) 服从利维飞行概率分布的只有少数的几个解析形式, 而幂律分 1 布就是其中之一 对于前面提到的随机行走的一般形式还是布朗运动, 只要其 步长所服从分布的方差是有限的 ( 并不一定要是正态分布 ), 而方向为均匀分布, 那么根据中心极限定理 (central limit theorem), 经过相当次数的随机行走后, 个 体的位置和初始点的距离在任意坐标轴上趋向于正态分布 (Codling, et al., 2008) 而利维飞行则恰恰不服从这一特点, 因为利维飞行步长服从的概率分布模型, 在 一定条件下其方差是无穷大的 2 1 幂律分布的详细介绍见 :2.3 2 幂律分布的方差计算见 :

11 不同的随机行走方式, 其背后都有相应的概率分布模型来支持它 在实际应用中常被用来进行模拟的概率分布模型有高斯 ( 正态 ) 分布, 指数分布和幂律分布模型, 由于高斯分布非常常见, 在各个领域都有广泛应用, 因此接下来我们主要对指数分布和幂律分布进行介绍 而幂律分布在轨迹模拟中最为重要 1, 因此我们将对幂律分布做详细介绍 2.2 指数分布 指数分布的函数形式定义为 : p x = ae bx (1) 其中 b > 0, 在实际应用中 x( 步长 ) 都有下限值 x bottom, 一旦下限值 x bottom 确定, 其系数 a 也就可以通过标准化而确定下来 标准化 均值以及方差的计算 : 根据概率分布积分值为 1 的特点, 通过标准化 ( 取值范围内积分 ) 过程, 就可以 计算出系数 a 的值 1 = p(x)dx = a e bx dx x bottom x bottom a = b e bx x bottom (2) 解得 : a = be bx bottom (3) 均值 μ 的计算方式为 : μ = xp(x)dx = a xe bx dx x bottom x bottom (4) 积分求得 : 1 三种分布的比较见 2.4 6

12 μ = x bottom + 1 b (5) 方差 σ 2 的计算方式 : σ 2 = x μ 2 2 p x dx = a x μ e bx p x dx x bottom x bottom (6) 积分求得 : σ 2 = 1 b 2 (7) 从以上的计算结果可以知道, 指数分布的均值和方差总是有限的, 因此服从中心极限定理 2.3 幂律分布 幂律分布的函数形式定义为 : p x = Cx α (8) 其中 α 为定值, 被称为指数项 (exponent), C 为常数项 (Newman, 2005) González(González, et al., 2008), Hui(Hui, et al., 2005), K. Lee(Lee, et al., 2009) 等人的研究均证明, 人类出行轨迹的一系列特征值 ( 包括步长 回转半径 停留时间 ) 均服从幂律分布 不只是人类, 许多动物的觅食模式也服从幂律分布 (Rhee, et al., 2008) 如信天翁(albatrosses)(Viswanathan, et al., 1996) 豺(jackals)(Atkinson, et al., 2002) 以及蜘蛛猴(spider monkeys)(ramos-fernandez, et al., 2004) 等, 由于食物或猎物在空间上往往呈利维分布, 因此, 利维行走 (Levy walk) 也是动物发现随机分布食物的最佳方式 (Viswanathan, et al., 1999) 鉴于幂律分布的重要性以及在轨迹模拟中的广泛应用, 我们在软件平台中优先实现对利维飞行的模拟 接下来我们对幂律分布的重要特性以及幂律分布随机数的产生方法做进一步的介绍 (Newman, 2005) 7

13 2.3.1 标准化 均值以及方差的计算 : 根据 (8) 式中幂律分布的定义,x 的取值范围必须有一个下限 x bottom, 而其上 限可以为无穷大 一旦 x bottom 确定, 其系数 C 也可以通过标准化确定 : 当 α > 1 时, 均值 μ 的计算方式为 : 1 = p(x)dx = C x α dx x bottom x bottom = α 1 C = (α 1)x bottom μ = xp(x)dx = C x α+1 dx x bottom 当 α > 2 时, 均值有限 : x bottom = C 1 α x1 α x bottom C 2 α x2 α x bottom (9) (10) (11) 当 α 2 时, 均值无限 方差 σ 2 的计算方式 : μ = C 2 α x 2 α bottom = α 1 α 2 x bottom (12) σ 2 = x μ 2 p x dx = x 2 + μ 2 2xμ p x dx x bottom x bottom = x 2 p x dx + 2μ xp x dx + μ 2 p x dx x bottom x bottom x bottom C = 3 α x3 α x bottom + 2μ 2 + μ 2 C = 3 α x3 α x bottom + 3μ 2 (13) 当 α > 3 时, 方差有限 : 8

14 σ 2 = C 3 α x 3 α bottom = α 1 α 3 x 2 bottom + 3 α 1 α 2 x bottom (14) 当 α 3 时, 方差无限, 此时的幂律分布不服从中心极限定理, 而自然界中许多 服从幂律分布的现象, 其系数 α 的范围都在 2 到 3 之间 服从幂律分布随机数的产生方式 在目前的编程环境中, 能够产生的 ( 伪 ) 随机数一般仅限于少数的几种, 如 Java 的基本语言包 util 中只提供服从均匀分布 (uniformly distributed) 和高斯分布两种类型的随机数 1, 这就需要我们通过特定的技巧来模拟产生符合幂律分布的 ( 伪 ) 随机数 ( 李铁军, 2010)(Press, 1986) 幂律分布的累积分布函数 P(x), 当 x [x bottom, ) 时,P x [0, 1) 因此可通过幂律分布的累积函数反解来获得服从幂律分布的随机变量 : 先获取 [0, 1) 范围内服从均匀分布的随机数 ζ, 令 P(δ) = ζ, 则 δ 服从幂律分布 δ 1 α = δ ζ = P δ = p x dx = C x α dx = C 1 α x xbottom bottom ζ(1 α) C δ x bottom = C 1 α (δ1 α 1 α x bottom ) 1 α + x bottom ζ(1 α) = α 1 (α 1)x bottom 1 α + x bottom x 1 α δ 1 α = (1 ζ )x bottom (15) (16) 因此 : δ = 1 1 ζ 1 α 1 xbottom 由于 ζ 是 0, 1 中均匀分布的随机数, 因而 γ = 1 ζ 是 (0,1] 之间均匀分布的随机 数, 最后 : (17) 1 Java api documentation, 条目 :Class Random. 9

15 δ = 1 γ 1 α 1 xbottom 而 γ 的获取是非常容易的, 因此, 服从幂律分布的随机变量 δ 也就可以轻易地得到 了 (18) 2.4 利用不同分布进行轨迹模拟的效果比较 根据 (8) 式, 如果我们要对幂律分布函数进行分段概率计算,x 下限为 x bottom, 积分区间为 x k 1, x k = [x bottom a k 1, x bottom a k ], 则积分结果为 : x k x k p x dx = C x α dx = C x k 1 x k 1 a α 1 1 α 1 (x bottom a k ) α+1 (19) 从积分区间的设定和积分结果来看, 他们都是幂律形式的, 对二者取 log 值, 则 log y log x 服从线性分布 因此, 我们从理论上可以证明 : 如果一个样本集合服从幂律分布, 那么对其作概率统计直方图, 在线性坐标系中是快速下降的, 同时由于幂律方差较大的特性 ( 当幂指数 α 3 时, 方差无限 ), 在图上可以看到模拟结果中 x( 步长 ) 的取值范围非常大 而在 双 log 坐标系下则应该是线性的 同样的, 我们可以对幂律分布函数进行互补累积概率 (complementary cumulative distribution function,ccdf) 进行计算,x 下限为 x bottom, 积分区间为 x,, 则积分结果为 : y = P x = C x x α dx = C α 1 x (α 1) = x bottom x α 1 (20) 对 y 取 log 值也可以发现 log y log x 服从线性分布 笔者通过软件平台模拟了一条步长服从幂律分布, 方向服从均匀分布的长程轨迹, 其共有 10 5 个节点, 并分别对其进行了频率统计和互补累积频率统计, 并分别在线性坐标系下和双 log 坐标系下绘制出直方图, 如图 4 所示 在图 4-d 图 4-e 中的直方图呈非常明显的 10

16 直线形态, 这也是我们直观判断一个样本是否符合幂律分布的方法 图 4. a. 笔者在软件平台中模拟的出行轨迹, 其步长服从幂律分布, 方向服从均与分布 ;b. 频率统计在线性坐标系下的直方图, 其中轨迹均值为 3.10, 由于方差较大的特性, 最大步长达到 8000 多, 我们看到概率在步长增长的情况下迅速下降, 但仍有很大的步长值出现 ;c. 互补累积频率在线性坐标系下的直方图, 同样当步长增加时, 累积频率迅 e 速下降 d. 频率统计在 双 log 坐标系下的直方图, 由于步长增大时样本量迅速减少的原因, 在尾部出现剧烈 震荡, 但线性特性仍旧非常明显 e. 互补累积频率在线性坐标系下的直方图, 该直方图呈现明显的线性特征 高斯分布和指数分布同样是非常常见分布类型, 在许多动物和人类的行为轨迹被揭示出更加服从幂律分布之前, 布朗运动 ( 高斯分布 ) 和指数分布也常常被用来进行轨迹模拟和研究, 因此笔者在软件平台中同时实现了对布朗运动 指数分布和利维飞行的模拟 为了对比的方便, 我们将幂律分布和指数分布的下限均设定为 1, 通过参数调节使得两种分布的理论均值都是 3, 而高斯分布可以通过 Java 语言直接模拟, 我们设定高斯分布的均值为 3, 均方差为 3, 模拟结果对比如图 5 所示 其中 a 为高斯分布,b 为指数分布,c 为幂律分布 同时将三种分布的互补累积频率在 双 log 坐标系中绘制 明显可以看到从左到右, 长程移动 出现的概率越来 11

17 越大 这在互补累积频率直方图中也可以看到 : 当步长 (x) 增大时, 高斯分布中出现的频率迅速下降, 在指数分布中概率下降的速度也很快, 而在幂律分布中下降的速度最慢 而人们的实际出行活动模式更加符合幂律分布 : 我们日常的工作生活往往局限在小范围内, 体现为较短步长, 但又有相当的概率会出现长程的旅游 出差等等 ; 动物也是一样, 当某地食物减少, 生存环境恶化后, 就进行长距离的迁徙, 寻找到新的食物源后, 便短暂定居下来, 活动范围减小, 如此周而复始 因此, 利用幂律分布对生物活动轨迹进行模拟, 比利用其他分布更加合理 图 5. 笔者利用软件平台分别对三种不同分布函数进行模拟的结果图, 三种轨迹均有 个节点, 为了利于比较, 笔者通过参数设定使得三者具有相同的步长均值 其中上面是轨迹图, 下面是互补累积分布统计图在 双 log 坐标系下的表现 a. 高斯分布模拟 ( 布朗运动 ) 从 a2. 中可以看到, 当 x 增大时, 累计概率有明显的拐点, 在步长小于 10 时就迅速下降, 最大步长为 b. 指数分布模拟, 从 b2 中可以看到, 随着 x 的增大, 累积概率下降也较快, 最大步长为 c. 幂律分布模拟 ( 利维飞行 ) 从 c1 来看, 其点的数目明显比前两个要少, 其原因是幂律分布模拟中 长程移动 出现的概率较大, 使得大多数短程运动被投影地非常小, 因此显得节点数较少 从 c2 中可以看到 : 随着 x 的增大, 幂律分布累积概率下降最慢 ( 这也使得幂律分布的方差很大 ), 在幂律分布模拟中, 出现的最大步长为

18 个体活动于一定的时空范围内, 任意时刻都对应着明确的位置 我们通过特定的手段 ( 如 GPS WiFi 网络移动终端等 ) 每隔一定时间间隔, 获取个体所在的位置, 并按照时序将这些位置连接起来, 就形成了个体移动的轨迹 当然, 由于现有技术和数据获取方式的约束, 我们也可以通过其他的方式间接地了解人类移动状况 例如利用做了标记的钞票, 通过钞票出现的地点和时间 (Brockmann, et al., 2006), 或者通过个体移动电话直接通话或收发短信时连接基站的位置和时间来反映人类的移动特性 (González, et al., 2008) 图 6. 个体移动 GPS 轨迹图例 (Rhee, et al., 2008), 该图中的轨迹来自迪斯尼乐园 中一个游客的旅游轨迹 对于个体的移动轨迹, 我们不但可以对其步长 速度 在某一点或某一小范 围的停留时间 速度等进行统计分析, 同时还可以利用一些专门的指标来揭示其 特征 13

19 2.5 回转半径 (Radius of Gyration) 回转半径用来计算轨迹中所有点和其中心点距离的平方根 1, 其计算公式如下 : r g= 1 n n i=1 (r i r m ) 2 回转半径可以用来表征轨迹的特征 如 (21) 式中所示 : n 表示轨迹中点的数目,r i 表 (21) 示第 i 个点的数目 r m 则表示所有点的中心 r m = 1 n n i=1 r i 从公式中我们可以 看到, 回转半径可以用来度量个体的移动范围 一般来说, 移动范围越大, ROG 也越大 (González, et al., 2008) 2.6 特征向量 (Eigenvector) 在介绍特征向量之前, 我们先引入转动惯量 (Moment of Inertia) 的概念, 转动惯量可以帮助我们将不同的轨迹置于统一的参考系统中, 以便对它们进行比较 借鉴力学中刚体的涵义, 我们可以定义一条轨迹在某区域的到访次数作为轨迹在这一特定区域的 质量分布 首先将一条轨迹定义为到访位置的集合: {(x 1, y 1 ), (x 2, y 2 ), (x n, y n )}, 其中 n 是到访点的数目 一个物体的转动惯量指的是其质量在给定轴上的平均分布 一个二维物体的转动惯量则可以用 2 2 的矩阵来表征 : I xy I = I xx I yx I yy (22) 结合标准的物理转动惯量的计算公式, 轨迹转动惯量的计算方式如下 : n I xx y i 2 i=1 (23) 1 维基百科, 条目 -Radius of gyration. 14

20 n I yy x i 2 i=1 (24) I xy = I yx x i y i n i=1 由于 I 是对称矩阵, 因此我们可以通过主成分分析将 I 变为对角矩阵 I D = (e 1, e 2 ), I D 可以表示为 : I D = I I 2 I 1 和 I 2 既是转动惯量的主惯性力矩, 也是 I 的特征值 I 1 I 2 通过以下公式求得 : I 1 = 1 2 (I xx + I yy ) 1 2 μ I 2 = 1 2 I xx + I yy μ μ 4I xy I yx + I 2 xx 2I xx I yy + I2 yy 我们将 e 1 和 e 2 定义为特征轨迹的特征向量, 它们同时也是给定向量的对称轴 15 (25) (26) (27) (28) (29) 如图 7 所示 : 计算轨迹特征向量的实际意义在于 :i. 可以提取轨迹移动的主 方向, 统计大量样本的移动方向有助于我们发现人类移动特征和城市形态或者道 路走向之间的相互联系 例如 M. Kim 等人在研究在达特茅斯学院中通过 WiFi 获得的轨迹数据时, 发现轨迹方向的分布并不是均匀分布的, 而是后明显的主方 向 而主方向恰好和学院内部的主道路方向一致 (Kim, et al., 2006), 当然他们统 计方向的方式和笔者的阐述不尽相同, 但这并不能否定特征向量这一指标的代表 性 ii. 默认 e 1 e 2, 我们定义轨迹的扁率为 f = e 1 e 2 e 1, 则对于特定的轨迹, 扁率可能能够反映其一定的行为特征 例如对于一个生活规律的人, 主要往返与

21 住宿地和工作地之间, 其轨迹扁率势必很大, 因此通过扁率计算有助于我们进行 进一步的信息提取 而这些工作都是以特征向量为基础的 图 7. 轨迹的特征向量提取, 通过特征向量可以有效地表征轨迹的主要移动方向, 对称性以及形态特征 (González, et al., 2008) 2.7 熵 (Entropy) 熵的概念最早出现于热力学过程 1, 但后来被广泛应用于信息论等其他研究领域, 并被赋予了新的涵义 在信息论中, 熵作为一项指标可用于度量随机变量的不确定性 2 Song 等人指出, 熵也许是用来度量时间序列 ( 这里主要指时间 ) 可预测性最基础的指标了 (Song, et al., 2010), 他们同时给出了熵的 3 种不同计算方 1 2 维基百科, 条目 -Entropy. 维基百科, 条目 -Entropy(information theory). 16

22 式 在此我们仅针对一种较有代表性的进行详细论述 : N p(i) S = P(i)log 2 i=1 (30) 式中 N 是到访的不同区域的总数目 对于一条特定轨迹, 如果具有 n 个不同 点, 由于落在不同区域的点可能有重复, 可以理解 :N n p(i) 表示到访第 i 个区域的概率 一个极端情况 : 个体对于所有区域的到访概率均匀, 则 S e1 = N 1 log 1/N N 2 = log N 2,N 1, 因此 S e1 0, 并且 N 越大,S e1 也越大 ; 另一种极端情况是 : 个体的行为完全可以预见, 到访一个特定地区 j 的概率是 1, 到访其他地区的概率则均为 0, 此时 S e2 = 1 log 1 N i=1,i j 0 log 2 = 0 从熵的计算可以看出, 轨迹的熵值越大, 则表示个体到访一组点的概率越均匀, 对其位置的预测也越困难 ; 而轨迹的熵值越小, 表示个体到访特定点的概率较高, 对其位置预测的精度也较高 在上面我们提到 : 由于空间是连续的, 但是提取重访点就要求我们合理地将 研究范围划分成离散的子区 由于数据获取的方式和类型各不相同, 因此对研究 范围的划分方式也不尽相同 例如, 对于通过手机基站获得的用户手机位置数据 或者通过无线网络路由接入点获得的移动网络设备数据, 可以基于基站或路由器, 将整个研究范围划分 voronoi 图, 然后分别统计落在每个泰森多边形中的点的数 目并计算概率就可以了 而对于 GPS 数据或者随机模拟的数据, 就无法进行 voronoi 划分了 由于软件实现过程中很重要的一方面就是进行轨迹模拟, 因此 笔者在此利用了聚类分析的思想对重访点进行了提取 聚类分析提取重访点的基 本流程是 :1 对于一条具有 n 个节点的轨迹, 将其每个节点看做 一类, 则可 以分为 n 个类 2 计算 n 个类中两两之间的距离 (A B 两个类的距离为 A 中所 有点到 B 中所有点的最短欧式距离 ), 得到一个 n 维距离矩阵 3 提取矩阵中的 最小值, 即得到距离最短的两个类 4 将距离最短的两个类合并成一类, 并且分 别计算各类之间的距离, 得到一个新的 n-1 维矩阵 5 重复 [34] 步直到达到某 一阈值 6 对任意一个类, 计算其中所有点的中心点作为该类的重访点的位置, 17

23 统计该类中点的数目并除以总数 n 作为该重访点的到访概率 对于 5 中阈值的设定可以有两种方式,1. 是统计轨迹步长的平均距离 L 并乘以一个系数 a 作为阈值, 当 4 中各类之间的最短距离大于 al 时, 停止聚类 另一种方法是对原始类的个数 N 乘以相应的系数 b 作为阈值 当余下的类的个数小于 bn 时 (0 < b 1), 停止聚类 ( 毛善君, 2010) 图 8. 左图是通过基站划分的 voronoi 图 (Song, et al., 2010), 并进行重访点提取的结果 ; 右图为笔者模拟产生的出行轨迹 ( 共有节点 1000 个 ), 步长服从幂律分布, 方向服从均匀分布, 红色点为通过聚类分析提取的重访点, 点面积越大表示到访概率越大 阈值设定为 1. 6L (L 为步长的平均值 ) 3. 软件平台架构设计 在前面的章节中我们已经论述了关于人类移动性研究软件平台实现的必要 性和可以反映轨迹特征的指标 在本章, 我们进一步论述软件平台的功能需求, 基本架构并对关键的一些类和接口进行简要描述 3.1 软件基本功能需求定义 作为一个综合分析平台, 该软件应当能够对轨迹的获取 模拟, 特征指标提 取, 统计分析, 显示输出, 后续实际应用提供全过程的支持 我们对软件平台的 基本功能定义如下 : 18

24 i 实际轨迹的输入 支持对主流格式轨迹数据的输入, 以便对轨迹进行进一步分析 这里的主流轨迹数据格式包括 shp 格式 (ArcGIS shpfile) 的线类型文件 GPS 格式数据 自定义的 csv 格式数据等等 ii 其他数据的输入 包括路网 建筑等矢量 (shp) 数据, 人口 经济等栅格 (ASCII) 数据 这些数据一方面可以用在作为约束条件, 对轨迹的模拟过程进行调节, 另一方面可以在显示输出中作为底图, 更好地解释轨迹特征 iii 轨迹模拟 利用不同的概率分布模型, 同时结合 ii 中的约束条件, 对人类出行模式进行模拟, 并生成相应的轨迹数据 iv 对个体轨迹特征指标进行提取和计算 包括最基本的步长, 速度 ( 在有时间数据的条件下 ), 移动方向, 以及上面章节提到的回转半径 特征向量 熵等等 v 对群体移动规律进行统计学分析 对于大量样本数据, 利用 iv 对各个轨迹分析, 然后对整体样本进行统计, 包括计算均值 方差 概率密度 累积概率密度等等 vi 结果显示和输出 将 i ii iii 步获取的结果进行图像显示, 并支持最基本的漫游 缩放功能 将 iv 中的统计结果进行显示, 包括指标的显示和统计直方图的输出 最后支持将结果输出到文件中 : 模拟轨迹输出为 shp 文件或自定义 csv 文件, 统计结果输出为 txt 文件, 模拟结果 直方图输出为图片 3.2 软件构架 关键类及接口介绍 在 3.1 节中我们看到, 软件平台支持对个体轨迹的全过程处理分析, 软件基本功能构架如图 9 所示 软件包含核心的几个数据类型 ( 如轨迹类 轨迹管理类 栅格管理类 路网管理类等等 ) 以及 3 个基本功能模块 : 输入和模拟模块, 指标计算和统计分析模块, 显示输出模块四大部分 接下来我们就分别对这几个部分进行介绍 19

25 图 9. 软件功能架构图 核心数据类型 核心数据类型指的是在本软件平台中用来存储和管理数据, 并且起到承接作用, 将各个功能模块联系起来的 类 (Class) 数据结构, 我们对这些数据类型的参数和核心方法作以简要的介绍 1 i. Node ( 节点类 ) 节点类是最基础的数据类, 也是构成轨迹的基础, 一个节点包括了其坐标和到达该节点的时刻 表 1. 节点类成员及方法描述成员 1 由于篇幅所限, 这里我们仅对核心数据类中较重要的参数 (parameter) 和方法 (method) 进行介绍, 而不 进行完全介绍 20

26 public Double X, Y 横纵坐标 public Calendar Time 到访时刻 方法 public Node(double x, double y, 构造函数并设定初始值 Calendar time) public Double distanceto(node node) 计算两个节点之间的距离 ii. Trajectory( 轨迹类 ) 1 轨迹类是整个软件平台的核心, 也是连接各个模块的桥梁 反映轨迹特性的 一些指标都是通过轨迹类中的方法来计算得到, 并在其他模块中进行统计分析 显示和存储的 成员 表 2. 轨迹类成员及方法描述 public ArrayList<Node> NodeList public int ID 路径点集合链表 唯一标识号 方法 Public nodelist) Trajectory(ArrayList<Node> nodelist 节点列表 Public double[] getsetplist() Public double getrog() Public double[] getprincipalaxes() Public double[] getentropybyamount (double amountpercentage) Public double[] getentropybydistance (double averagedistancepercentage) 获取轨迹的步长列表计算轨迹的回转半径计算特征向量的大小以及方向计算轨迹的熵 ( 以数量百分比作为阈值 ) 计算轨迹的熵 ( 以平均距离乘以相应系数作为阈值 ) 1 各个模块将在下面的章节中进一步介绍 21

27 iii. TrajectoryPool ( 轨迹集合管理类 ) TrajectoryPool 用来对轨迹数据进行统一管理和操作, 以保证数据准确性和一致性, 利于其他模块调用等 表 3. 轨迹集合管理类成员及方法描述成员 Public ArrayList<Trajectory> 轨迹集合 TrajectoryCollection public MBR 1 Boundary 路径集合的最小外包矩形 public CoordinateReferenceSystem 2 CoordinateReference 用于记录当前轨迹集合的投影参照系, 保证数据一致性 方法 public void Fill (TrajectoryGenerator 3 安全地为本类中填充轨迹数据 generator) iv. TrajectoryGenerator( 轨迹生成类 ) TrajectoryGenerator 本身是抽象类 (abstract class), 在该类中实现了产生新的轨迹数据的接口方法 继承该类的数据生成模块, 都可以通过该接口被 TrajectoryPool 所调用, 以安全方式为软件提供数据 这样做的优点是 :1. 使得软件能够将不同时轨迹数据整合起来, 在内存中形成统一的数据结构 (Trajectory), 以便分析和调用 ;2. 提高程序的可扩展性, 任何实现该接口的模块都可以为软件提供数据, 使得新的模型或数据源可以被快速地整合到软件平台中 ;3. 提高软件内部逻辑结构一致性 表 4. 轨迹生成类成员及方法描述成员 本程序自行定义的最小外包矩形类投影参照系统类 抽象路径获取类, 在下面进一步介绍 22

28 public CoordinateReferenceSystem 用于记录将要生成轨迹集合的投影参 CoordinateReference 照系, 保证数据一致性 方法 public abstract Trajectory 获取下一条轨迹数据 GetNextTrajectory(); v. Roads( 道路类 ) 和 Field( 场数据类 ) Roads 主要对道路数据进行统一管理,Field 则主要对场数据进行管理 其作用同 TrajectoryPool 一方面用于显示, 使用户更好地理解轨迹数据 ; 另一方面可以作为轨迹模拟的约束条件 表 5. 道路类成员及方法描述成员 public ArrayList<Geometry 1 > roadlist 道路集合 public CoordinateReferenceSystem 用于记录将要生成轨迹集合的投影参 CoordinateReference 照系, 保证数据一致性 方法 public void Fill(RoadGenerator 2 roadgenerator) 通过 RoadGenerator 安全地为该类填充 数据 表 6. 场数据类成员及方法描述 成员 public GridCoverage2D 3 栅格数据结构 GridCoverage 1 地理实体模型类, 由 GeoTools 软件包实现,Geometry 本身为抽象类, 在 Roads 中使用的类型为继承自 Geometry 的 LineString 和 MiltiLineString 关于 GeoTools 将在下面章节进一步描述 2 道路生成类, 其作用同 TrajectoryGenerator, 实现数据模型的统一管理 3 二维栅格数据模型类, 由 GeoTools 软件包实现, 可以对栅格数据进行统一管理并支持一些基本的运算 23

29 public CoordinateReferenceSystem 用于记录将要生成轨迹集合的投影参 CoordinateReference 照系, 保证数据一致性 方法 public double getnodatavalue() 计算数据结构中用来标识 无数据 区 域的值 ( 如 -9999) public double[] getextremums() 计算各个波段的极值, 以便进一步统计 分析和绘制过程中颜色表的设置 vi. LevyFlightView (extends FrameView)(GUI) LevyFlightView 作为图形用户界面, 主要用来相应用户的各种操作, 调用各个模块进行数据处理分析, 并将结果及时反馈给用户 支持 LevyFlightView 进行数据管理的类为 EnvironmentParameter 类, 该类中存储了一个 TrajectoryPool, 一个 Roads 和一个 Field 以及各种预定义的环境变量, 如图形显示规则和用于效率优化的结果缓存等等 输入和模拟模块介绍 输入和模拟模块的主要作用是产生轨迹 (Trajectory) 道路(Roads) 和场 (Field) 数据, 为下一步统计分析做准备 其功能的实现主要由一系列数据生成类 (generator) 和数据导入类 (importer) 完成 其介绍如下表所示 : 表 7. 数据生成及数据导入类描述 名称 继承 描述 SHPRoadImporter RoadGenerator 加载 shp 格式的道路数据, 通过 RoadGenerator 提供的接口为 Roads 填充数据 SHPTraImporter TrajectoryGenerator 加载 shp 格式的轨迹数 据, 并 通 过 24

30 TrajectoryGenerator 提供的接口为 TrajectoryPool 填充数据 GPSTraImporter TrajectoryGenerator 加载 GPS 类型的轨迹数据 CustomTraImporter TrajectoryGenerator 加载自定义类型 (csv 格式 ) 的轨迹数据 PowerLawTraGen TrajectoryGenerator 利用幂律分布模型, 并结合其他类型的数据约束生成轨迹数据 ExpTraGen TrajectoryGenerator 利用指数分布模型, 并结合其他类型的数据约束生成轨迹数据 GaussianTraGen TrajectoryGenerator 利用高斯 ( 正态 ) 分布模型, 并结合其他类型的数据约束生成轨迹数据 GeotiffFieldImporter FieldGenerator 加载具有坐标投影信息的 geotiff 或 jpg 格式的栅 格 文 件 并 通 过 FieldGenerator 提供的数据接口为 Field 填充数据 ASCIIFieldImporter FieldGenerator 加载通用数据格式的 ASCII 文件 输入和模拟模块为图 9 中的蓝色部分 25

31 3.2.3 指标计算和统计分析模块 在本软件平台中对指标计算和统计分析功能的实现采用了不同的策略 指标 计算功能被整合到不同的数据类中 1, 如熵 回转半径的计算 而统计分析功能 的实现则由独立的类来完成, 其相互关系如图 9 中绿色和紫色部分 : TrajectoryPool 对轨迹集合进行管理, 计算轨迹的各项指标并生成一致的数据结 构 ( 一般为 ArrayList 2 链表类型 ), 而这些一致的数据结构可以被专门的统计分析 类进一步使用 这样的设计思路也是为了提高软件的可扩展性和逻辑一致性 统 3 计分析由类 FrequencyCal 来实现, 它的构造函数接受统一的数据结构和统计策 4 略作为参数 主要实现的频率分布 (PDF) 统计, 累积频率 (CDF) 统计 互 补累积频率 (CCDF) 统计 均值 极值 方差等的统计计算, 并对统计结果在 内存中进行保存, 以提高软件效率 显示和输出模块 5 本软件平台对模拟和计算结果都进行了友好 美观的显示和方便的输出, 交 互性强 显示模块主要有 4 个部分, 如表 8 所示 : 表 8. 软件显示模块描述 模块名称控件及类支持细节描述 地图显示模块 JMapPane 6 通过功能强大的 JMapPane 类加上笔者的 1 见 ii 2 ArrayList:java 提供的集合管理类, 可以将多个相同类型的实例 ( 如 Double) 作为一个集合统一管理调用 3 统一数据结构指的就是上面提到的 ArrayList<Double> 和 TrajectoryPool 4 统计策略用来规定统计区域的划分问题, 由专门的类 StatisticBinningStrategy 进行管理, 并接受用户的调整 5 显示效果见第 4 节效果展示 6 由 Geotools 提供, 继承自 JPanel 26

32 深度定制, 实现各种基础数据的地图显示, 漫游 缩放 选择以及栅格数据的颜色表设定 操作日志模块 JTextPane 1 记录并以不同颜色输出 用户的操作过程, 提高软 件的互操作性和友好性 统计图表显示模块 StaticGraPanel 2, 对各种指标的频率统计 StatisticGraphGen 3, 累积频率统计 和互补累 StatisticGraphGenSchema 4 积频率统计进行直观显 示, 并支持用户进行相应的显示参数设置 特征指标显示模块 JTextPane 将一些无法进行图表显示的计算和统计在此输出供用户浏览 至于输出模块, 则支持将所有模拟 计算和统计结果以合适的格式输出 模拟结果如模拟产生的各种轨迹数据, 输出为 shp 格式文件 ( 时间数据以高度维 -Z 值存储 ) 或者存储为自定义的文件格式, 这样可以保留更多的附加信息, 如数据产生的时间 利用的模型 约束条件等等 计算和统计结果以 txt 格式输出文档, 同时按照用户的需求产生相应的图片 显示和输出模块为图 9. 软件功能架构图中红色部分 1 Java 提供的基础控件 2 专业定制的图表显示控件, 继承自 JPanel 3 统计图表生成类 4 统计图表显示参数管理类 27

33 3.3 软件实现中的关键技术描述 编程语言和平台 由于 Java 语言良好的跨平台特性, 面向对象的特点 广泛的应用背景 以及 丰富的学习资源 1, 本软件平台采用 Java 作为开发语言 2 开发平台采用 NetBeans 3, 操作系统平台采用 Windows Geotools 4 简介 Geotools 是一款功能非常强大的 GIS 开发工具包, 采用 Java 语言编写, 完全免费和开源 GeoTools 本身在开发过程中完全遵循 OGC 标准 (Open Geospatial Consortium), 这使得 Geotools 常常被用来经行 GIS 解决方案的开发 5 本软件平台的数据加载 显示模块以及基础数据类中也大量利用了 GeoTools 中的类和功能模块, 这大大缩短了本软件平台的开发周期 同时由于 Geotools 的开放性, 这丝毫不影响我们软件的跨平台特性 4. 软件平台效果展示 6 经过笔者及实验室一个学期的努力, 现已按照软件设计思路, 完成了软件平 台的大部分内容 : 整体框架已经建立完成, 并且可以进行基本的数据输入 模型 模拟统计和显示功能 软件整体界面如图 10 所示 图中的 a, b, c, d 四部分分别 对应了 中的地图显示模块 操作日志模块 统计图表显示模块和特征指标 显示模块 地图操作, 坐标显示等功能均已完善 1 维基百科, 条目 - Java_(programming_language). 2 jdk1.6.0_24 3 NetBeans IDE 维基百科, 条目 - GeoTools. 6 关于软件完成工作的介绍, 见致谢 28

34 图 10. 软件平台整体效果示例 a. 地图显示模块, 当前显示的内容有 : 道路图层为北京市地铁线路图层, 栅格图层为地铁线路图层的多级缓冲分析结果, 同时以笔者自定义的颜色板 (colormap) 经行渲染 蓝色短线为笔者通过已有模块生成的服从幂律分布的轨迹集合, 共有 1000 条轨迹, 每一条轨迹包含 100 个节点 轨迹方向服从均匀分布, 轨迹起始点受其他图层约束, 均匀分布在其他图层的最小外包矩形内 b. 操作日志模块, 不同的颜色代表不同的结果, 如红色代表操作失败或放弃 黑色代表信息输出, 该模块有利于提高交互性 c. 统计图表显示模块, 将统计结果显示出来并支持用户进行显示参数的设定 1 根据 中论述的不同策略, 本模块支持两种层面的结果显示方案 一种是对整个轨迹集合的特定指标进行统计, 并显示结果 (macro analysis); 另一种则是对单个轨迹经行分析并显示结果 2 (trajectory analysis) 当前显示的是对 1000 条轨迹的熵 (entropy) 的统计直方图, 均为线性坐标系 从图中可以直观地看到熵的分 1 见图 10-d 2 见图 11 29

35 布类似于正态分布 d. 特征指标显示模块, 统计结果中不能图表显示的在这里 输出, 如样本数 均值 极值 方差等 由于轨迹分析是本软件的核心, 因此我们重点开发了这一部分的内容, 在轨迹图层上, 用户可以在按住 Ctrl 键的同时通过鼠标点击选择轨迹, 选中的轨迹会被高亮显示出来, 各种属性信息在专门的窗口中显示 ; 同时进行实时分析, 将结果在右侧显示出来, 这就保证了很好的交互性 显示效果如图 11 所示 图 11. 轨迹分析界面, 该区域为图 10 中红色区域放大的结果 被选中的轨迹以高亮 ( 青色 ) 显示, 同时右边的分析模块实时计算参数并显示结果, 直方图统计的是轨迹的步长 我们可以看到单个轨迹在 双 log 直方图中也表现为近似于直线 下面是一些特征指标的显示, 包括步长的均值 方差 轨迹重心坐标 熵 回转半径等 左边对话框中显示的是文件记录中 ( 如 shp 文件 ) 关于该轨迹的属性信息 包括各个字段名和值 最后, 本软件为用户提供了丰富且方便的交互体验, 图 12 中显示的就是几 种较有代表性的交互窗口 30

36 图 12. 软件平台交互窗口展示 a. 轨迹模拟参数设定对话框, 用户可以对参数 进行详细设置, 同时具有文本提示以及为用户提供约束选择 b. 栅格显示设置窗 口, 用户可以选择波段 RGB 渲染或单波段颜色板 (colormap) 渲染, 软件提供 数十种预定义的颜色板, 同时支持用户自定义颜色板 c. 重访点提取参数设置窗 1 口, 用户可以按照不同的策略设定提取算法的阈值 d. 直方图统计设定模块, 用户可以选择直方图以线型或柱形表现, 同时设定线宽, 线颜色, 圆点半径和 颜色, 甚至是坐标轴标尺 ( 线性或 log 性 ), 以便显示美观 科学的统计图, 更 好地揭示统计规律 5. 总结和展望 作为一款对人类移动性研究进行辅助支持的软件平台, 其软件体系还是相当 复杂的, 完成整个系统需要的工作量也是很庞大的 由于本次工作是笔者毕业设 1 见 2.3 对熵的描述 31

37 计的主要内容, 考虑到时间和精力的限制, 在软件实现的过程中采取的策略是从最重要的方面入手, 先进行整体的架构设计, 定义通用的类和接口, 将软件最主要的类和图形用户界面优先实现, 然后再进一步完善各个细节和具体的功能 因此, 到目前为止, 虽然我们软件平台的主题功能已经基本实现, 但可以进一步优化的地方还有很多, 例如 : i. 实现对内存的优化管理 虽然 JDK 平台实现了内存的托管机制, 极大地简化了编程过程, 但这带来的副作用却是内存使用的低效率 例如我们再前面曾模拟产生了一条具有 10 5 个节点的轨迹, 如果要计算该轨迹的熵, 就要开辟一个 的矩阵进行重访点提取, 这就要占用极大的内存 因此当我们在熵计算完成后, 就必须及时释放内存, 否则后面的工作将无法进行 然而 Java 语言的内存托管机制却不能保证这种内存释放的时效性 因此, 我们必须对内存的使用进行优化 ii. 跨平台的实现 在软件设计之初, 我们之所以选择 java 语言就是看中了其优秀的跨平台特性 在软件开发的过程中我们仅利用了单一的平台, 因此如果需要真正地实现跨平台, 还需要我们在不同的系统环境下对软件进行进一步的调试和编译 iii. 面向应用的, 更加复杂的轨迹模拟模型的引入 我们设计该软件的初衷本来就是要支持面向应用的轨迹分析和模型模拟, 而不是仅仅局限于理想情况 由于实际情况千变万化, 应用领域也不尽相同 因此面向每一个实际的应用, 我们可能都要定制专门的模拟模型, 结合实际数据进行模型模拟和计算 例如 Kim 等人针对达特茅斯学院的轨迹模拟, 先进行实际轨迹的分析以确定模型参数, 同时利用不同时段的人口分布数据, 学院的土地利用数据等对模型进行修正和约束 (Kim, et al., 2006), 最终得到较为精确的模拟结果 我们软件平台目前的进度仅仅实现了对一些比较流行的模型, 结合简单地理约束条件进行的较为通用的模拟 因此, 在这一方面我们要走的路还有很长 iv. 软件的进一步完善 只要我们愿意, 软件质量就总是会有提升的空间 我们的软件平台, 在功能上可完善的地方也有很多 例如定义统一的结果输出规范, 制定我们自己的轨迹存储文件 (custom file) 格式等等 32

38 人类移动性研究目前既是一个热点领域, 也是一个前沿领域, 新的理论 技术 分析方法都在不断被研究者提出 这也对我们的软件平台提出了更高的要求 : 一方面在设计上要更加注重软件构架的可扩展性和通用性, 同时提高软件计算效率 ; 另一方面要紧跟目前的研究进展, 将新的轨迹模拟模型 研究指标等及时整合到软件中去, 使我们的软件发挥更大的作用 33

39 参考文献 Atkinson, R. P. D., et al Scale-free dynamics in the movement patterns of jackals. OIKOS, vol. 98, no , pp Brockmann, D., Hufnagel, L. and Geisel, T The scaling laws of human travel. Nature , pp Chaintreau, Augustin and Hui, Pan Impact of Human Mobility on Opportunistic Forwarding Algorithms. IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 6, NO Codling, Edward A., Plank, Michael J and Benhamou, Simon Random walk models in biology. Journal of the royal society interface , pp Einstein, A Investigations on the Theory of Brownian Movement. New York: Dover:ISBN González, Marta C., Hidalgo, César A. and Barabási, Albert-László Understanding Individual Human Mobility. Nature Understanding Individual Human Mobility Supplementary Material. Nature Gutowski, Marek Lévy flights as an underlying mechanism for global optimization algorithms. arxiv v1. 6 4, Hui, Pan and Crowcroft, Jon Human mobility models and opportunistic communications system design. Philosophical Transaction of the Royal Soctiy , pp Hui, Pan, et al Pocket Switched Networks and Human Mobility in Conference Environments. Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking New York, NY, USA:ACM. 2005, pp Kim, Minkyong, Kotz, David and Kim, Songkuk Extracting a mobility 34

40 model from real user traces. In Proceedings of the 25th Annual Joint Conference of the IEEE Computer and Communications Societies. (INFOCOM) Lee, Kyunghan, et al SLAW: A New Mobility Model for Human Walks. IEEE, In Proceedings of INFOCOM. 2009, pp Merler, Stefano and Ajelli, Marco The role of population heterogeneity and human mobility in the spread of pandemic influenza. Proceedings of the Royal Society B, , pp Morters, Peter and Peres, Yuval Brownian Motion(Draft version). 5 25, Newman, M. E. J Power laws, Pareto distributions and Zipf's law. Contemporary Physics , pp Pearson, K The problem of the Random Walk. Nature. 72, Press, W. H Numerical Recipes: the Art of Scientific Computing. s.l. : Cambridge university press, Ramos-Fernandez, G., et al Levy walk patterns in the foraging movements of spider monkeys (ateles geoffroyi). Behavioural Ecology and Sociobiology, vol , pp Rhee, Injong, et al On the Levy-walk Nature of Human Mobility: Do Humans Walk like Monkeys? IEEE INFOCOM 2008 IEEE Conference on Computer Communications , pp Song, Chaoming, et al Limits of Predictability in Human Mobility. Science , 2010, p Viswanathan, G. M., et al Levy flights search patterns of wandering albatrosses. Nature, vol , pp Viswanathan, G. M., et al Optimizing the success of random searches. Nature, vol , pp 李铁军 Generation of RVs and Variance reduction. 北京大学数学科学院课程课件 年. 35

41 毛善君 地学数学模型. 北京大学遥感与地理信息系统专业教材 年 2 月, 页

42 致谢 本次毕业设计的完成标志着我大学本科生学习生活的结束 在美丽的燕园度过了自己充实的四年大学时光 在此期间, 所有教导过我的老师们, 您们勤勤恳恳 教书育人, 不但教我们如何做学问, 亦教我们如何做人生 我们会分外珍惜从您们那里学到的东西, 他们将会陪伴我们一生, 指引我们前进 在此我谨向老师们表达自己最诚挚的感谢和祝福, 祝老师们身体健康, 工作顺利 孙敏老师作为我们 07GIS 的班主任, 不但要完成对我们的教学任务, 同时还在我们平时的生活学习上给予我们莫大的关怀和帮助, 特别是老师的国学情怀, 一直在潜移默化地影响着我们, 使我们受益匪浅 在此向孙老师表达我们特别的敬意 大学四年时间使我们培养起浓厚的同窗情谊,07GIS 永远是最优秀的, 最奋发向上的, 在此向我所有的同窗好友致敬, 很庆幸我们有缘一路风雨同舟, 相互扶持 在此特别感谢我们班的班长蔡亚平同学和团支书底骞同学, 你们为我们班的发展付出了太多的精力 本次毕业设计工作可以顺利完成, 特别要感谢我的导师刘瑜老师 刘老师在初期的论文选题以及中间的基础理论 编程技术 软件设计方面都给予了我莫大的支持 同时在软件细节实现等方面刘老师还给了我很多自由发挥的空间, 使得我可以按照自己的想法来实现软件 刘老师同时也将是我研究生阶段的导师, 本次的毕业设计内容也算是我们实验室当前的一项研究工作, 这次工作给我从本科生的学习阶段向研究生的科研阶段提供了一个比较好的过渡 使我可以较快适应实验室的工作方式, 因此, 特别向刘老师表示感谢 笔者本次毕业设计的完成过程中, 实验室的同学们也给予我了很大的帮助 康朝贵师兄帮助我快速熟悉了人类移动性方面的基础理论, 肖昱师姐 高松师兄 刘亮师兄和王星光师兄在论文写作方面也给我提出了很多有益的意见 施力学弟还帮助我完成了相当一部分的代码, 最后徐励 刘磊和底骞同学经常和我在实验室共同进行毕业设计, 我们相互讨论, 相互鼓励, 大家都得到了促进, 在此向各位表示真诚的感谢 37