环境的时空数据挖掘研究现状与展望

!"
・ 博士论坛 ・
!!!!" !"
$
ቤተ መጻሕፍቲ ባይዱ
!!!!"
摘 要 关键词
面向移动环境的时空数据挖掘研究现状与展望
陈 捷$ 唐世渭 $ 杨冬青 ! 王腾蛟 !
$ （北京大学视觉与听觉信息处理国家重点实验室， 北京 $"";<$ ） ! （北京大学计算机科学与技术系， 北京 $"";<$ ）
=->)+?： (@0,A+0B1C#DEF#01F#(,
定位服务、 移动商务等重大应用得以发展的内在动因。随着移 动通信向第三代的演变， 移动用户的定位技术和设备也正在迅 速普及。正是由于移动用户定位技术进入实用阶段， 极大地推 动 了 移 动 增 值 业 务 的 重 要 方 面 —基 于 位 置 的 服 务 及 其 相 关 应 用领域的迅速发展， 包括如下三个方面： 基于位置的服务 （&’()*+’,-.)/01 2034+(0/， 是当 （$ ） &.2 ） 前一项正在蓬勃发展的移动增值服务。 它是指根据用户的空间 位置及时地提供与位置信息相关的移动信息服务， 包括基于位 置信息的交通信息查询， 商场打折信息、 酒店和餐厅等周边信 息查询服务， 紧急救助， 区域广告和基于位置的游戏和娱乐等 等。 对于移动通信网络运营商来说， 对手机的准确定位有 （! ） 利于无线网络资源和移动性管理。 如可以了解话务量的时空分 布， 优化网络规划； 微观上可以准确地监测移动台的移动， 实现
!#$#$
相关理论基础
&$’
（$ ） 时空数据模型。 目前， 建立高效统一的时空数据模型还 存在相当的困难 ， 在过去的二十多年里， 各相关领域为此已提 出不少模型， 它们来自不同的背景并能够满足各自不同的需求 与限制。这里只列举与移动 （点 ） 对 象 相 关 的 数 据 模 型 &!’： (# 快 照。通常用一组时间戳 )(* 数据， 其缺点是数据冗余度高 &+’。((# 基于事件的模型。,-./.-0 等提出一种适用栅格数据的基于事 件的数据模型 1*234， 该模型能够表示出一系列相关的事件， 减 小 了 冗 余 。 (((# 移 动 对 象 时 空 （46*2） 模 型 是 789:;8< 等 提
（!""! ） 文章编号 $""!-;55$$%-"""$-"5
!"##$%& ’&(&") (%* +#,)-$.& ,/ ’-(&0,12$3-,#(4 5(&( 60%0%7 0% &8$ 6,904$ :,#4*
!8$% ;0$< 2(%7 ’80=$0< >(%7 5,%7?0%7@ :(%7 2$%7A0(,@ $ （ H0,*03 ’I 6,I’3>)*+’, 2(+0,(0JK)*+’,)? &)C#’, L)(@+,0 G03(0D*+’, ’I .0+A+,M N,+403/+*OJ.0+A+,M $"";<$） ! （ H’>DF*03 2(+0,(0 ),1 70(@,’?’MO ’I .0+A+,M N,+403/+*O ， .0+A+,M $"";<$）
!#$#!
时空数据挖掘 由于 )(* 及时间快照数据的可获取性， 将时间信息嵌入空
[ 的 I 站点的交通事故 ! 在 2!\! 到 2!\+ 时 间 段 内 高 速 路 ]
的 @ 站点的不寻常的高交通流量” 。 （5 ） TF<-;F;>4F<-M 是 ,:8;-M 等设想的一个对车辆对象进行 时空数据挖掘的原型系统。 其目标是从车辆对象的轨迹数据库 中抽取车辆运动的运动模式， 预测交通堵塞、 提供备选路线等。
基金项目： 国家 T<5 重点基础研究发展规划项目资助 （编号： ； :$TTT"5!<"U ） GVN-6.L 创新研究院的资助 作者简介： 陈捷， 男， 博士后， 研究方向为智能信息处理。唐世渭， 男， 教授， 博士生导师， 主要研究方向为数据库与信息系统。 $T%; 年生， $T5T 年生， 杨冬青， 女， 教授， 博士生导师， 主要研究方向为数据库与信息系统。王腾蛟， 男， 博士， 讲师， 主要研究方向为数据 $TWU 年生， $T<5 年生， 库与信息系统。
引言
人们社会活动的 “移 动 性 ” 是移动通信、 移动互联网、 移动
小区间的最佳切换等， 促进无线网络运行效率的改善。 在智能交通系统 （672 ） 中自动车辆定位系统 （89&2 ） 是 （5 ） 但是它需要占用宝贵的无线频带资源和额外 672 系统的核心， 的硬件投资。而利用移动定位系统实现的 89&2 可以将定位、 通信、 计算机信息处理与控制等构成一个有机整体， 有利于多 种信息的融合， 而且具有更好的城市覆盖和灵活方便的漫游管 理功能等。 然而， 各种定位设备不断地产生积累海量的包含移动对象 时空信息的数据， 这些数据中隐藏着丰富的知识， 具有潜在的 巨大的应用价值。同时， 这些数据构成了复杂的时空对象和关 系，因此给时空数据挖掘研究提出了许多富有挑战性的课题， 这也是该文得以展开的出发点。 时空数据挖掘是数据挖掘研究 的前沿领域之一， 它的研究内容涉及到多个领域， 如空间数据 移动对象数据 挖掘、 时态数据挖掘以及时空数据库、 时态 :62 、 库等等。 该文将分别从时空数据挖掘的理论基础研究和相关应 用研究的现状、重点解决的问题以及进展情况等进行论述， 最
&%’ 。在移动环境下， 人们考虑后者。对于移动 和连续 （高更新率）
!#!
!#!#$
应用研究
在下列应用领域的代表性研究项目主要包括： 环境与交通 （$ ） *0898MW 等人实现了一个分布式并行查询和分析挖掘环
境原 型 X6YLZ1*2， 可 以 从 地 球 科 学 栅 格 数 据 库 抽 取 复 杂 的 时空对象并进行分析挖掘。 主要用于为地球物理科学家建造 ) 字节规模数据中时空模式的知识发现环境。 （! ） XOF00FP88MF 等 利 用 他 们 开 发 的 基 于 图 的 结 构 挖 掘 系 统 其中引入了地震时 *Z@3Z1 进行了地震活动的结构关系挖掘， 间之间有限的空间和时间关系如 “空 间 邻 近 ” （C= 公 里 ） 和 “时 等， 使得发现的子结构中反映出 了 地 震 活 动 间邻近” （+% 小时） 的时空规律。 （+ ） *O-QOAM 等人研究了面向城市智能交通系统数据分析 的时空数据挖掘问题。 他们尝试并建造了交通流量监测数据的 多维数据模型， 并利用数据挖掘经典算法实现或设计了一些关 于交通流量监测数据的空间、时间数据挖掘以及时空数据任 务， 如发现这样的时空关联规则： “ 在 2$ 到 2! 时间段内高速路
点对象， 一般假设对象的运动轨迹是时间的分段线性函数。目 前已研究了 $>3 ， !>3 空间的索引技术，后者的研究比前者困 难， 但对于重点考虑移动对象在交通道 路 网 络 中 移 动 的 $#=>3 问题， 能够简化为 $>3 空间的问题处理。有效支持轨迹查询的 索 引 技 术 包 括 *2?> 树 ， 2@> 树 ， 以 及 侧 重 于 预 测 未 来 位 置 的
B9)&#(.&： 814),(0/ +, >’C+?0 (’>>F,+()*+’, ),1 ?’()*+’, 10*03>+,)*+’, *0(@,’?’M+0/ @)40 30/F?*01 +, *@0 3)D+1 (’??0(P *+’, ’I ) @FM0 )>’F,* ’I /D)*+’-*0>D’3)? 1)*)#6, *@0 >’C+?0 Q’3?1， *@0 )+> ’I /D)*+’-*0>D’3)? 1)*) >+,+,M +/ *’ 0R*3)(* E,’Q?01M0 F/0IF? *’ /FDD’3* 10(+/+’, >)E+,M I’3 ?’()*+’,-C)/01 /034+(0/， +,*0??+M0,* *3),/D’3*)*+’, /O/*0>/ 0*(## 6, *@+/ D)P D03， *@0’30*+()? ),1 )DD?+()*+’, )/D0(*/ ’I /D)*+’-*0>D’3)? 1)*) >+,+,M )30 /F340O01， ),1 IF*F30 30/0)3(@ 1+30(*+’,/ )30 1+/(F//01# C$D=,#*)： L’C+?+*O ， S)*) L+,+,M ， 2D)*+’-70>D’3)? S)*)
移动通信与无线定位技术的迅速发展导致了大量时空数据的产生，面向移动环境的时空数据挖掘的目标就是
从这些数据中抽取知识， 为基于位置的服务、 智能交通系统等提供有效的决策支持。文章分别从时空数据挖掘的理论基 础研究和相关应用研究的现状、 重点解决的问题以及进展情况展开论述， 并展望了未来的发展方向。 移动性 数据挖掘 时空数据 文献标识码 8 中图分类号 7G5$$#$5
!
时空数据挖掘的研究现状与发展
事实上， 尽管不少时空数据挖掘研究是面向各特定应用领
域的， 一些研究工作还正处于起步阶段， 但它已受到国际学术 界和工业界的广泛关注。 下面从理论研究和应用研究两方面分 别展开论述。
!#$
理论研究
近年来， 数据挖掘的研究对象已经从事务型数据库扩展到
空间数据库、 时空数据库、 移动对象数据库等。 时空数据挖掘的 理论研究主要受到空间数据挖掘和时态数据挖掘研究的影响， 并以经典的数据挖掘理论为基础， 同时还受到时空数据表示和 存取方式的限制。
&5’
出的用于移动对象数据库的模型 以预测移动对象将来的位置。
&=’
， 46*2 模 型 提 供 随 时 间 连
续变化的动态属性， 查询结果依赖于查询请求的时刻， 因此可 时空数据索引。抽象的时空数据模型必须与有效的数 （! ） 据结构和索引结合才能满足查询要求。直到近几年， 有关时空 数据库和移动对象数据库的索引研究文章开始较多地出现， 一 般按更新频率将其研究的对象环境分为两类： 离散 （低更新率）
万方数据
计算机工程与应用 !""!#$%
$
后总结， 并展望未来的发展方向。
为可能， 如时空元规则、 时空泛化、 时空聚类和关联、 演化规则 等。INMAOAP 等在文 &$$’中对这几种时空规则进行了较详细的 论述。 需要指出的是， 文中遗漏了一类重要的挖掘任务： 时空预 测， 当然如果考虑线性运动的假设， 则对于移动对象数据库该 任务就退化为关于对象未来的空间位置的查询； 对于时空数据 库尤其是时态 )(* 应用而言，时空预测具有重要的应用价值， 但是其方法也是与具体问题相关的， ,8QMARAS 在 文 &$!’ 中 对 时 空预测的相关文献进行了总结， 并提出了一种基于均匀采样网 格的预测算法。 比较权威的有关时空数据挖掘算法的文献可以 参考文献 &J’&$+’。 在时空图象序列处理领域， TOA< 等 通 过 引 入 , > 树 （,-A<8>S8.<0>0M-- ） 研 究 了 空 间 数 据 流 的 Q> 近 邻 快 速 分 类 算 （栅格数据） 的无损压缩表示。 HF 法， ,>树是一种原始空间数据 等运用了小波变换和 *64 （自组织 映 射 ） 神经网络研究了时空 数据的聚类算法。 由于可能涉及到用户隐私和商业机密等原因， 供研究使用 的移动对象的真实时空数据不易获得。因此， 2O-8E8MFEF; 等研 究了移动对象轨迹生成的算法， 能够提供具有一定语义的移动 对象轨迹仿真数据。另外， @F00<-M 研究了时空对象的近似特征 描述理论， 首先定义时空区域 （;DA0F8>0-PD8MA9 M-UF8< ） 是由空 间和时间成分组成， 然后基于空间与时间成分的拓扑关系定义 了时空区域之间的拓扑关系， 并使用粗糙集的概念定义了时空 之间的拓扑关系， 因此可用于知识不 区域近似 （ADDM8VFPA0F8<;） 完全的时空对象的构造的特征描述问题。
2,?> 树 等 。 最 近 2A8 等 提 出 将 4B@> 树 和 +3 ?> 树 结 合 的
能够以较小的代价支持时间戳和间隔窗口查询。 4B+?> 树 &C’， 提出 另外， ,ADAEFA; 等首次研究了时空数据仓库的索引问 题 &G’， 了一种支持时空数据 6HI, 操作的框架， 他们将空间维和时间 维作为一个数据立方体的一个复合维处理。