（计算机软件与理论专业论文）基于模糊粗糙集的移动对象k近邻预测.pdf

山东大学硕士学位论文 摘要 移动对象未来趋势及其近邻预测查询技术由于更适合在交通调度、基于位置 服务、天气预报、智能导航等领域的应用，并且在智能交通系统、地理信息系统、 军事中有着广泛的应用前景，而得到了广泛的关注。通过在移动对象上安装定位 设备，便能够有效记录存储移动对象的运动状态，然后根据移动对象当前的运动 特性对其未来进行各方面的预测。由于自身及外界的诸多因素，对象的运动状态 会不断地发生变化，从而预测过程中就会有很多不确定性出现。现在有许多研究 致力于移动对象及其k 近邻预测中不确定性的处理，具体的包括时间不确定性和 空间不确定性。本文主要研究的是基于移动对象未来趋势的空间不确定性。 实现近邻预测查询的关键技术由空间数据索引技术和基于索引结构的最近 邻查询算法两部分组成。相比较而言，t p r 树在索引的空间、索引方法分割数 据还是分割空间以及索引结构是否必须进行周期性的重建等方面具有其它几种 索引结构无法企及的优势，1 p 查询不仅可以找到查询点当前的近邻，同时还包 括了结果的有效期以及在有效期后将发生的变化。所以，本文的移动对象近邻预 测不确定性分析研究将基于t p r 树和t p 近邻查询算法。之后，借用模糊一粗 糙集理论将传统方法得到的结果进行分析比对，即： 1 首先，针对移动对象预测位置的不确定性具体表现为它的真实位置在预 测位置周边区域的模糊隶属度，分析了已有方法得出的预测位置的模糊 性； 2 再用传统方法求得基于预测位置的扩展k + m 近邻集； 3 针对预测位置的模糊不确定性必然会累及传统近邻查询得到的k 近邻的 精确度，同时会引起k 近邻集合基于“k 近邻”不分明关系的粗糙不确 定性，所以借助近邻点的模糊一粗糙隶属函数来最终确定所求k 近邻集 合中的各个点。 最后，通过时空数据产生器产生相应的动态数据源，对移动点用唧i l 树建 立索引结构，用引入影响时间的t p 近邻预测查询算法，再对基于模糊一粗糙集 的移动对象最近邻预测算法进行精确度分析。尽管计算量有些增大，但数值分析 可以表明我们的方法明显提高了移动对象k 近邻预测的精确度。另外，由于研究 山东大学硕士学位论文 中的模糊一粗糙隶属函数中用到了w 中各点到模糊空间r 中2 n 个p 的可能位 置取样点的距离，这种取样的方法会一定程度上影响精确度。所以，未来的工作 将致力于基于非取样方法的移动对象k 近邻预测，从而争取精确度的进一步提 高。 关键词：移动对象；k 近邻查询；模糊集；粗糙集 i i 山东大学硕士学位论文 a b s t r a c t 1 h er e s e a r c ho fd i r e c t i o n 锄dn e i 曲b o r s p r e d i c t i o no fm o v i 】呜o b j e c t sa r e c h a l l e n g e db yt 量l e r e 印p l i c 撕0 no nt m 珩c 甜e n l p e r ，s e n ，i c eb 嬲e d0 np o s i t i o n ，w e a m e r f o r e c a s t ，印嘶u d en 撕g a t i o n 妙s t e l i l ，g e o g r a p h yi n f o n i l 撕0 n 夥s t e m 锄dl i l i l i t a r y a 日 a i r s w ec o u l dn o t e 锄dd e p o s i tm o v i n gd b je c t s s 协t u sm e s s a g e s 诵mm eh e l p0 f g p so nm em o v i i 唱o b j e c t s p r e d i c t i o no f 血ef u t u r ec 锄b ed o n eb yt l l e s ep o s 饥l r a l i k a n k 缸w h i l e ，a sar e su ：i to ft h ei n f l u e n c e 丘o ms e l f - i i l 】 1 i c t e do ro u t s i d ef k 屯o r s ， m o v i n go b je c t s s t a t u sm e s s a g e sw o u l dc h 锄g ec o n s t a l l t l y s ot h e r ew o u l db em a n y l h l c e n a i 埘e sa p p e a ri nt h ep r e d i c t i o n m a n ys c h o l a r sh a v et a l 【e 1 1u p 、访mt l l ed i s p o s a l s o f 廿l e 岫c e 栅n t i e sm a te ) 【i s ti n 缸1 em o v i n go 场e c t sa i l di t sk - n e a r e s tn e i g h b o r s p r e i i i 曲o n 1 1 l e 眦c e r t a i n 够i n d u d e st e i 印o r a l0 n e 锄ds p 撕a l0 n e h 1t 量l i sp a p e rw e 删n l yd i s c u s st l l es p a c e m c e r t 豳石e s0 fm em o v i n go b je c t s 向_ t u r ed i r e c 缸0 n t h et e c h n o l o g y so fn e i g l l b o 瑙 p r e d i c t i o n a r em a i l l l y c o m p o s e db ym e t e c h n o l o g yo fs p a c ed a t ai i l d e x 锄dt 量l e 撕血m 舐co fn e i g h b o r s p r e d i 曲o nb 嬲e do n i i l d e x c o i n p a r e d 谢t 量lo t h e r s ， r 仃e eh 嬲m o r es u p e r i o r i 够0 ns p a c eo fi i l d e ) 【，p l 锄 o f 妇ap a r t i 石0 n 锄di n d e xh a 访n gs e a s o n a lr e b u i l do rn o t t pq u e 黟c 0 u l df i n d n e i 曲b o r so fc u 仃e mp 0 毗觚d i i r v o l v e sp e r i o do f v a l i d i t ) ro f 血ee l l d s 趾dm ec h a i l g 鼯 a r e r 也i s 矗m e t h e 眦c e r t a i n 够a n a l y s i so fm o 访n go b j e c t s n e i g h b o rp r e d i c t i o nw o u l d b eb a s e do n 也ei n d e xs t r i 】曲】r eo f r 仃e ea n dt h e 碰缸1 m 舐co f t pq u e 巧a n dt 量l e i l ， c o m p a r e 锄da 1 1 出s i sb ym 乙巧r o u 曲s e t s 、) v i l lb eu s e do nt h er e s u n so f t 量l e m h a v ea na n a l y s i so nt 量l ef u z 巧m e m b e r 出pd e g r e eo fm o v i l 鸣o b j e c t s p r e d i c t p o s i 6 0 n ，砒i c hr e s u l 协筋m r 锄dt p ，弱血e 吼c e r t a i n 够o fi t sp r e d i c t e dp o s i 石 a p p e a r s 嬲t t l ef 位巧i n e i l l _ b e r s h i pd e g r e et t l a t l ea c t u a lp o s i t i o na tm er e 百o na r o u n d p r e d i c t e dp o s i t i o n f i n di t se 斌e n d e dk+mn e a r e s tn e i 曲b o rs 吒w h i c hi sa l s 0e d u c e df r o m 仃a d i t i o n a lm e t b o d s 0 l i la c c o u mo fm ef h z 巧一吼c e r t a i r r 眵o fi n 0 访n go b j e c t s p r e d i c t e dp o s i t i o n ，也e a c c 呦c yo ft 量l ek n e a r e s tn e i g h b o rm a t0 b t a i n e db yt 量l e 仃a 凼石o nk n n 融o d 啪u l d b ea 饪缸e d t h er o u g h - 皿c e n a i n 锣 o ft t l ek - n e a r e s tn e i g h b o rb 勰e do nm e i l l d i s c e n l i b i l i 锣r e l a ：t i o no f “k n e 盯e s tn e i g h b o r 锄e 玛e sa c c o r d i n 西y t l l ef u z 巧- r o u g h n l e r n b e r s h i pf 缸舐0 ni se m p l o y e dt 0o b t a i l lt l l e 缸a lk n e a r e s tn e i 曲b o rs e t i i i 山东大学硕士学位论文 a tl a s t ，m ed y n 枷cd a t aa r ep r o d u c e db yg e n a r a t es p a t i ot e m p o r a ld a ：t a w i 也 t p r 仃e ei n d e xf o rm 0 v i n go b j e c t s 趴dt pq u e 巧谢mi n f e c 石o nt i m e ，w el l s en l e m e t h o do fp r e d i c t i o no fm o v i n go b j e c t s n e i 曲b o rb yf 也巧r o u g hs e t st 0 锄a l y z e 血e p r e c i s i o no ft h er e s u l t s i ti sc o n c l u d e dt 1 1 a t ，c o m p a r e dt o l ea c t 岫lp o s i t i o no f 协e m o v i n go b je c t s ，廿l e 锄由s i sb a s e d0 nm et h e o 巧o ff 也巧- r o u g hs e t sc 觚p r o m o t et 1 1 e p r e c i s i o no fi t sk - n e a r e s tn e i g h b o rs e tn o t i c e a b l y ，t h o u g hw eh a v ee n h a n c e dm e c a l c u l 撕o n a lq u a n t i 够t h ed i s t 觚c ef | r o me a c hp o i n ti nk + mn e a r e s tn e i g h b o rwt 0 2 ns 锄p l e dp o i n t sn l a ti n o v i n go b j e c tpm a yl i e si n 畸s p a c erw h i c hi sr e f e 盯e di i l f 也巧- r o u g hm e m b e r s h i p 劬c 石o n ，h a su s e ds 锄p l em e m o d nm e 肌s t 量l a tt h e r em 碍 b ea ni m p a c to nt l l ea c c i l r a c y s oi 1 1f u _ t u r ew o r k ，、ew o u l di n v e s t i g a t em o r ep r e c i s e a l g o r i m mf o rm ep r e d i c 石o no fm o v i n go b je c t s k n e a r e s tn e i 曲b o rb 嬲e d0 n n o n s 锄p l e dm e m o d k e y w o r d 8 ： m o vin go b j e c t ：kn e a r e s tn eig h b o rq u e r y ； f u z z y8 e t s ；r o u g h 8 e t s i v 原创性声明和关于学位论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：扯日 期：主竺芝垒皇 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 导师签名：溢重塑么自期：之丝丝 山东大学硕士学位论文 第一章绪论 随着移动计算，无线通信及定位技术的发展，如何有效地对移动对象进行查 询、管理，以及提供准确的基于位置近邻服务等应用需求，使得时空数据库研究 面临着新的挑战【1 1 。 1 1 研究背景与意义 目前国内外许多学者针对不同的应用已经提出了各种移动对象索引技术，但 总体来说移动对象索引技术方面的研究仍然处于初步阶段。其中移动对象未来趋 势及其最近邻居预测技术由于更适合在智能交通调度、基于位置服务、天气预报、 智能导航等领域的应用，在智能交通系统、地理信息系统、军事中有着广泛的应 用前景，从而得到了广泛的关注【2 】，例如：“已知某车现在的位置、时速和运动 方向，查询未来一小时后离它最近的几个加油站或者食宿供给处”、“卫星云图 上某降雨云正以某速度向某方向移动，查询几分钟后离它最近的几个影响降雨的 因子一。 通过在移动对象上安装定位设备( g p s ) ，便能够有效的记录存储移动对象 的运动状态，如当前所处的位置坐标、运动速度、方向以及周边因素等信息。然 后根据移动对象当前的运动特性对未来各个方面进行预测。由于自身及外界诸多 因素，对象的运动状态会不断地发生变化，预测过程中就会相应的有很多不确定 性出现。现在有许多研究致力于移动对象及其k 近邻预测中不确定性的处理【3 1 ， 具体的包括时间和空间不确定性，例如：“预计什么时候到达某个指定地方 、 “预计某指定时刻到达什么地点。其中移动对象预测位置的不确定性表现在它 的真实位置在预测位置周边区域的模糊隶属度，而这种模糊不确定性必然会累及 最后得到的k 近邻的精确度，同时会引起k 近邻集合基于“k 近邻 不分明关系 的粗糙不确定性。做好这些不确定性数据的分析，对于得到更精确的数据有着重 大的意义。 此外，由于空间物体数量众多，导致空间数据量十分庞大，所以计算出已知 点和所有空间物体的距离，找出距离已知点最近的物体是不切实际的。特别在多 山东大学硕士学位论文 维空间里，这样的查询会更费时。因此，需要研究高效快速查询算法解决这类问 题。同时，由于移动环境下所有物体都是连续运动的和信息不确定的，在此基础 上的最近邻查询非常复杂，所以空间查询的优化以及预测的精准度势必成为空间 应用的难点和突破点。相应的，如何将静态环境下的最近邻查询扩展到移动环境 下成为研究中的重点，能够有效地处理大量移动对象的最近邻查询精确预测算法 便显得尤为重要。 1 2 研究现状 移动对象的连续运动对数据库技术提出了新的要求和挑战。现存的数据库管 理系统不能够处理连续变化的数据，如移动对象的位置。这是因为，在传统数据 库中，如果数据不被修改，数据是一直保持不变的。而要在数据库中表示移动对 象并回答关于位置的查询，移动对象的位置需要连续更新。显而易见，移动对象 位置的频繁更新是不现实的，为了解决这一问题，能够描述移动对象及其位置信 息的移动对象数据库应运而生【4 】。 1 9 9 7 年p s i s t l a 、o w 0 1 f s 0 n 和s c h 锄l b e d a i n 提出了移动对象数据库的基本 数据模型m o s t ( m o 、，i n go b je c t ss p a t i o t e m p o r a l ) 吲模型。这个模型的关键在 于动态属性的提出。动态属性将移动对象的位置用一个时间函数来表示，解决了 移动对象位置随着时间的推进不断更新的难题。一个动态属性a 由三个子属性 a u p d a t e v a l u e 、a u p d a t 舐r m 、a 缸l 舐o n 来表示。其中a 自m c t i o n 是一个以时间 为变量的函数，在t = o 时刻，它的值为0 。动态属性a 的值定义如下：在 a u p d a t e d m e 时刻，a 的值为a u p d a t e v a l u e ，那么在a u p d a t e t i m e + t o 时刻， a 的值为a u p d a t e v a l u e + a m n c t i o n ( t o ) 。与此同时，还提出了适用于m o s t 数 据模型的查询语言f t l ( f u t u r et e m p o r a ll o 百c ) ，可以查询移动对象当前和未来 的位置。 现存的数据库数据模型加入动态属性后所形成的m o s t 模型，是移动对象 数据库的基本模型，可以有效地对移动对象的位置信息进行描述。随着科学技术 的进步，动态环境的不断发展，移动对象数据库将变得越来越重要，在此基础上 的移动对象索引技术和移动对象查询及预测研究便成为可移动对象数据库的核 心问题【6 。引。 2 山东大学硕士学位论文 1 2 1 索引技术的相关研究 从关系数据库、空间数据库、时序数据库，到时空数据库和移动对象数据库， 它们对数据的查询要求越来越高，所需的索引技术也越来越具有挑战性。有效地 解决数据库的索引问题，是数据库研究者所共同关注的【9 】。 空间数据库是用来存储、管理各种空间或非空间信息的计算机信息应用系统 【1 0 】。传统关系型数据库用b + 树为数据建立索引，但b + 树是一维索引，无法处理 空间数据库中的二维和多维空间数据。目前，已经研究出许多高效的空间索引方 法【1 1 ，1 2 】，大致分为如下四类，其中主流方法都是采用树索引结构： ( 1 ) 基于二叉树的索引技术 典型范例包括k d 树1 3 1 、m k d 树以及s k d 树【1 5 1 等。k d 树是一种二分 索引树结构，主要用于索引多维数据点，但是对复杂的空间目标的索引却必须采 用近似方法和空间映射技术。因此针对k d 树空间关系的低查询效率，庞大的索 引树，需要存储在外存的缺点，同时为了能够索引复杂的空间目标，便提出了适 合索引二维空间目标的，基于实体标志重复存储技术的树。s i 树的提出 避免了空间目标的重复存储以及空间映射，用空间目标的中心点来对空间目标集 进行二分索引。然而，以上这些方法对非点状空间目标的索引效率都较低。 ( 2 ) 基于b 树的索引技术 目前的空间数据索引技术很多都基于b 树，实践证明它们对大型数据库的 索引具有出色表现。其中，r 树的思想是将空间目标及索引空间用其最小包含 矩形来近似表示。由于允许区间重叠，导致了搜索路径的平均数量的增加，尤其 在维数增高时很可能会导致索引次数和存储空间的大量增加，严重影响了查询效 率。为了避免索引空间重叠的问题，采用强制重新插入来调整r 树结构的r + 树 被提出【1 6 l 。而r 奉树【1 刀在插入操作时则将叶子结点和非叶子结点分开考虑，同时 提出了既考虑最小包含矩形的周长，也考虑其相互重叠的面积的方法，来衡量空 间上的聚集，在分裂溢出结点时也提出了更为复杂的算法。l b e nr 树1 8 1 利用 一种空间填充曲线碰l b e f t ，把各个数据矩形的中心映射为碰l b e r t 曲线上的一个 值。将多维空间的空间对象映射到一维空间，使得高维数据在低维空间有一个对 应。而且，高维空间数据之间的关系能够在低维的映射中得到定的保留。之后， 利用该变换保持的空间聚集的特性来解决这个问题。然而，这类索引结构需要解 山东大学硕士学位论文 决的主要问题仍然是减少区域的重叠，提高搜索效率。上面的众多方法都不能很 完善地衡量空间的聚集，只能作到局部的优化，无法保证由此形成的r 树的整 体组合结构最优。 ( 3 ) 基于哈希的网格技术【1 9 1 基本思路是将索引空间划分为相等或者不相等的一些小方网格，与每个网格 相关联的空间目标存储在同一磁盘页上，而网格的访问地址则可以直接通过求数 组下标或应用某种算法得到，常见的方法有g d df i l e 【2 0 1 等，这类方法主要适用于 索引多维空间点。 ( 4 ) 空间目标排序法 基本思想是将索引空间划分为许多小的格子，然后对每个格子指定一个唯一 的数字或编码，空间目标用与其相交的一个或多个格子的数字来表示，或者用与 其相交格子的编码求得的另一个唯一的编码来表示。这种方法的实质是将多维空 间的实体映射到一维空间，然后采用一维的数值对多维的空间目标进行排序，常 见的方法有q u a d 仃e e 2 1 1 、z o r d i n g 【捌等。 移动对象数据库于1 9 9 7 年被提出后，至今为止，国内外对其索引技术的研 究还处于初级阶段，提出的几种索引结构大部分都是由空间索引结构发展而来 的。移动对象索引技术分为两类：索引移动对象当前和未来位置的技术以及索引 移动对象历史轨迹的技术。 索引移动对象历史轨迹的技术，大多数都是将空间数据进行离散的处理，并 没有考虑到其连续变化，通过加入一个时间维，使移动对象在d 维空间的运动 转化为d + 1 维空间的轨迹来描述。2 0 0 0 年由p f o s e r 等提出两种方法s 1 r t r e e ( s p 撕o t e m p o r a lr - t r e e ) 和t b t r e e ( t r 匈e c t o 巧- b 吼d l et r e e ) 2 3 1 。这两种树结构对 于索引移动对象轨迹的查询要优于r 树系列。2 0 0 1 年y t a 0 和d p 印a d i 嬲又 提出了m v 3 r t r e e ( m u l 五v e r s i o n3 dr t r e e ) 2 4 j ，此结构将舢j l t i - v e r s i o nb t r e e 【2 5 j 和3 dr - t r e e 相结合，可以较好地索引移动对象的历史轨迹。索引移动对象当前 和未来位置的技术，目前有以下几种方法被提出： ( 1 ) t a y e b 等1 9 9 8 年首次提出了移动对象的索引方法【2 6 1 ，可以对移动对象的 未来位置进行索引。这种方法将索引空间分割成四部分，采用孙偶q u 础r e e 来 索引移动对象。假设移动对象在d 维空间运动，通过加入一个时间维，将移动 4 山东大学硕士学位论文 对象的未来轨迹转化为d + l 维空间的线来索引，然后通过移动对象动态属性的 时间函数有效地进行未来位置的预测。然而这种方法需要不断存储线的信息，从 而可能会导致过量的存储。 ( 2 ) l 幻1 l i o s 等1 9 9 9 年提出了在一维和二维空间索引移动对象未来位置的方 法【2 7 】，此方法采用h o u g h 转换【2 8 1 将移动对象的轨迹在更高维空间中映射成点， 然后采用1 1 b 鼍t r e e 1 的点存取方法和多个b + t r e e 的方法进行索引。为了适应 这种数据的转化，这种情况下的查询也要进行转化。并且，这种索引结构不能够 扩展到高维空间，具有很大的局限性。 ( 3 ) s a l t e n i s 等2 0 0 0 年提出了一种基于r 树的扩展树：t p r 树 ( t i m e p a r 锄e t e r i z e dr - t r ) 3 们，它是一种以时间为参数并且能够存储动态目标 的索引结构，可以将所有基于m o s t 模型的移动对象进行存储，树中的各个结 点都是一个以时间为参数的表达式，可以有效地表示移动物体的方向和速度。此 后，这种时间参数的空间索引方法逐渐成为一种较为流行的方法。2 0 0 2 年 p r 0 c o p i u c 等【3 1 】针对，r - t r e e 随时间的推移其查询性能降低的特点，提出 s t 触o t r e e ( s p 撕o - t 唧o r a ls e l f a 西u s 缸n gr - t r e e ) ，当查询性能降低到设定的限 度时，s t 舢0 t r e e 将自动调整索引结构。显然，s t a r t r e e 最适合更新频率较 低的场合。随后，s a l t e i l i s 等p 2 1 又对像- t r e e 进行扩展，提出r e 船t r e e 。为 了减小查询代价，引入移动对象的失效时间( e 冲i r a t i o n 矗m e ) ，其主要目的是避 免在较长时间内移动对象没有更新其运动状态导致查询性能下降的问题。t a 0 等 则认为，r - t r e e 索引结构在查询性能方面并不是最优的，给出新的最小代价目 标函数，并以此目标函数为基础，对n 醛t r e e 的插入算法做了相应的改进，更 好地考虑了移动目标的动态属性，形成名为 r t r e e 的索引结构【3 3 】。t p t r e e 在算法上要比t p r t r e e 复杂得多。最近，j e n s e n 掣3 4 】提出了一种基于b + t r e e 的索引结构b x t r e e 。b x - t r e e 仍然用线性函数f ( t ) 来描述移动对象的运动状态， 但移动对象的分类索引方式不再使用t p b r ，而是按移动对象的更新时刻来分类， 即以时间轴分类。 以上的算法应用于未来查询时，都是仅有当前速度影响预测。预测的不确定 性本身较过去查询更强，这样移动物体的实际位置经常处于不确定体积之外，导 致频繁的速度更新，因此x u b 等【3 5 1 将指数滤波方法较多地用于时间序列预测中， 山东大学硕士学位论文 由系统内存保存最近的h 个速度更新。尽管这有效地提高了预测位置的精确度， 但仍是有其不确定性存在的。 1 2 2 移动对象近邻查询的相关研究 最近邻查询问题一直是数据库研究中的重要应用领域，解决近邻问题的最直 接方法是计算数据集合中的每个点到查询点的距离，和查询点之间距离较小的那 些点被当作近邻。这种方法的搜索时间随着数据点数目的增加呈线性增长。由于 在空间数据库中数据点的数目巨大而且是多维的，采用这种直接方法搜索近邻的 效率非常低。因此，需要将数据集合预处理到一种数据结构来加快近邻搜索。然 而，过去的大部分研究工作一直集中于静态环境下的最近邻查询。随着近几年移 动对象数据库的发展，使得最近邻查询问题扩展到了移动环境这一领域。有效地 查询移动环境下移动物体的最近邻便显得极为重要了。 静态环境的查询算法中，最基本的最近邻查询算法是基于r 树的b a b ( b r a l l c h a n d - b o u l l d ) 算法，其中包括深度优先遍历r 树的d f ( d 印t 1 f i r 哟算法和 宽度优先遍历r 树的b f ( b r e a d t h f i r s t ) 算法，都可以应用于发出查询请求的物 体和被查询的目标都是静止的情况。d f 算法由n r o u s s o p o u l u s 等1 9 9 5 年提出【3 6 】， 这种方法通过查询点q 和结点e 的子树中所包含目标的距离的最小值 i s t 值、以及查询点q 和结点e 的子树中所包含目标的距离的最大值 m n 心iax d i s t 值作为判断条件，深度优先遍历r 树来查询最近邻，并在文献3 7 l 中分析了这种算法的性能。一种改进的d f 算法由k l c h e 姐g 和a w f u 于 1 9 9 8 年提出【3 引，这种方法只采用m 【n d i s t 值作为判断条件深度优先遍历r 树 完成查询。g r 两a l t a s o n 和h s 锄e t 于1 9 9 9 年提出的b f 查询算法【3 9 1 ，此算法 采用了一个优先队列保存到目前为止已经访问过的结点，从所有结点中选择下一 个要处理的结点，是一个较为优越的算法。 对于发出查询请求的物体是移动的、被查询的目标是静止的最近邻查询问 题，也有一些方法被提出。其中，一种解决这个问题的方法采用v df v o r o n o i d i a g r a m ) 模型i 删这一概念，这种方法适用于移动查询点对静态目标的查询，静 态目标通过r 树对其建立索引，但是这种方法只适用于查找移动对象的一个最 近邻，无法将其扩展到k 个最近邻的查询。另一个最近邻查询算法于2 0 0 1 年由 z s o n g 提出h 1 1 ，通过在取样点重复应用最近邻查询算法，为一个移动查询点找 6 山东大学硕士学位论文 到连续最近邻。这种方法采用前一个点的计算结果来计算后点，避免重复运算。 然而，不同的取样频率会影响到结果的精确性。另外一种不会产生错误的方法于 2 0 0 2 年由y t 等提出【2 。柏】，是一种基于r 树的查询算法，可以有效地通过一 次查询得出移动点的连续最近邻，避免了分割点的丢失和高代价的查询，在性能 上也有较大提高。 上述的方法只适用于静止查询点对静止查询目标的最近邻查询，或者移动查 询点对静止查询目标的最近邻查询。对于移动对象数据库中，查询点和查询目标 都是移动的情况，则无法应用上述方法完成最近邻查询。随着移动对象数据库的 产生，最近邻查询问题扩展到移动环境成为必然的趋势，于是，对于移动环境下 这一问题的研究成为了国内外学者共同的研究热点。国外至今为止提出了几种能 够索引移动对象未来位置索引结构，例如：p q u 础r e e 、1 1 b 鼍t r e e 、 r 树 等。那么在一种适合于进行未来最近邻查询的索引结构的基础上，通过执行有效 的最近邻查询算法，完成移动环境下的未来最近邻查询将是解决这一问题的有效 途径。 移动环境下的最近邻查询算法于1 9 9 9 年由g k b l l i o s 等提出阳】，这种算法 采用复制转换的方法，将一个移动点的运动轨迹x ( t ) = 】【o + v 0 转化成在空间中 的一个点( ) ( o ，v x ) ，然后在此基础上采用h b 鼍t r e e 和b + t r e e 索引结构完成最近 邻查询。但是，这种方法只适用于一维空间，无法扩展到二维空间。r b e n e t i s 等2 0 0 2 年提出了基于，r 树的最近邻查询算法【删，可以应用于二维空间的移 动对象最近邻查询，并可扩展到多维空间。然而，该算法只能完成未来段时间的 最近邻查询，不能进行连续的最近邻查询，具有一定的局限性。 综上所述，之前所有的最近邻查询的方法都没有涉及到由于预测移动对象位 置的模糊不确定性而影响到的k 近邻精确度，以及k 近邻集合基于“k 近邻一不 分明关系的粗糙不确定性。 1 3 论文主要工作 本文将主要研究基于移动对象未来趋势的空间不确定性。移动对象预测位置 的不确定性表现在它的真实位置在预测位置周边区域的模糊隶属度，这种模糊不 确定性必然会累及传统k 近邻查询得到的k 近邻的精确度，同时会引起k 近邻集 7 山东大学硕士学位论文 合基于“k 近邻 不分明关系的粗糙不确定性。已往研究没有涉及到这种现象的 处理，所以本文将先具体研究适于未来近邻查询的 r 树索引结构以及1 1 p 近邻 查询方法，之后借用模糊一粗糙集理论将其得到的结果进行分析比对，在预测位 置模糊不确定性方面对移动对象进行分析，即通过一个函数来表现它真实位置在 预测位置周边区域的模糊隶属度。这主要为下一步获得更精确的k 近邻集合服 务。接着，计算其扩展k + m 近邻的模糊一粗糙隶属函数，最终得出更精确的k 近邻集合中的各个点。最后，通过实验验证算法的精确性以及有效性。 论文后续章节的结构安排如下： 第二章分别具体地介绍空间数据库的索引结构以及移动对象k 近邻查询的 方法，为移动对象近邻预测的进一步研究奠定技术基础。 第三章是模糊集和粗糙集的发展和基本概念以及两者的分析结合，为移动对 象近邻预测的进一步研究奠定理论基础。 第四章先分析了移动对象k 近邻预测的不确定性，之后介绍了选用的 r 树索引结构以及，i p 近邻查询方法，然后基于此，提出了基于模糊一粗糙集理论 的移动对象k 近邻预测的具体分析方法、步骤以及算法实现，并通过实验数据得 出相应参数的合适取值以及结果近邻集更精确的结论。 第五章对课题研究做了客观总结，提出了它提高精确度的同时存在的影响精 确度的细节，以及有待进一步研究的部分。 山东大学硕士学位论文 第二章移动对象近邻查询概述 移动对象数据库中，实现最近邻预测查询的关键技术由空间数据索引技术和 基于索引结构的最近邻查询算法两部分组成。有效的空间数据索引技术是快速检 索信息的基础，且便于在此基础上的查询算法的实现。因此，移动环境下的最近 邻查询研究要以能够索引移动对象的动态索引结构为基础，然后，将静态环境下 的最近邻查询算法扩展到移动环境中。本章将介绍经典的空间数据库索引技术， 以及基本的基于r 树的最近邻查询算法理论，从而为后文的研究工作奠定技术 基础。 2 1 空间数据库索引结构 与传统的数据库管理系统相比，空间数据库涉及对现实世界大量空间目标的 处理。然而，空间目标具有其特殊性。首先，空间目标往往具有不规则的几何形 状，而且目标之间的空间关系复杂，存储需求量大；其次，针对空间目标的空间 操作，计算的代价比起传统的操作复杂、运算量大；最后空间目标的空间次序难 以定义，无法应用通常的排序技术。因此，这种数据需要特殊的数据结构才能有 效地处理。 空间索引是按照空间分布特性来组织和存储数据的几何数据结构【4 5 l 。建立空 间索引机制的主要目的是提供对数据的访问路径或指针，便于对空间目标的查询 以及对各种空间数据进行操作，提高对空间数据的搜索速度。目前存在许多索引 结构和技术来解决空间数据库中查询数据集问题4 6 1 ，但是总体而言，都是由r 树 派生出来的各种变种。 2 1 1r 树索引结构 r 树实际是对b + 树的扩充，因而它不仅具有b + 树特有的动态平衡性( 所有 叶结点都在同一层上) ，而且能进行多维索引。r 树的每一个节点n 都对应着 磁盘页d ( 和区域i ( n ) ，如果结点不是叶结点，则该结点的所有子结点的区域 都在区域i 的范围之内，且存储在磁盘页d ( 如中；如果结点是叶结点，那 么磁盘页d ( 中存储的将是区域i 范围之内的一系列子区域，子区域紧紧 9 山东大学硕士学位论文 围绕空间对象，一般是空间对象的最小外接矩形( m i n i m 啪b o u d i n gr e c t 锄d e ， r ) 。r 树数据结构的定义如下： ( 1 ) 除去根结点，r 树中所有的结点所能包含的空间对象为【nm 】，其中m 【o ，m 2 】。m 表示r 树结点所能存储的最大空间对象数。根结点至少含有两 个空间实体。 ( 2 ) r 树的索引结点存储的空间实体描述为( 血n o ( 1 e m ) ，其中的d r 表示该 结点的一个孩子结点的区域范围，而n o d e m 则表示为该子区域在磁盘存储中的 位置。 ( 3 ) r 树数据结点都在同一层，它们存储的空间实体为( m b r ，o d ) ，用来表示 m b r 个存储在o 位置的空间对象的最小外接矩形。 下面给出一个r 树的实例。在图2 一l 中地图被分为a 、b 两块，其中a 块 中包含了空间对象d 、e 、f 、g ，而b 块中包含了空间对象h 、i 、j 、k 。图中 虚线框分别表示覆盖a 、b 两块中所有对象的最小范围。与划分后的地图相对 应的有一个4 阶r 树，该树除根结点外的所有结点最少含2 个元素，最多含4 个元素。 r 。 i ib 口 1 一 口 一口 ab l | b efg翻i，k 图2 1r 树对地图空间的划分 如果对图2 1 中b 块要加入空间对象l ，由于b 块将含有5 个空间对象， 而r 树是4 阶的，因此要分裂成b 、c 两块，r 树也相应进行分裂，如图2 2 所示。 同样，在删除空间对象时，有可能引起r 树某些结点的合并。 r 树的查询比较简单，如图2 3 所示，其中w 是用户查询范围。 1 0 山东大学硕士学位论文 查询时，先在图2 1 的r 树根结点中查与w 相交的块，a 与w 相交，则 再在a 的子结点中查与w 相交的对象，d 、e 、f 、g 都不与w 相交，则返回 到根结点，找到下一个与w 相交的块b ，再在b 的子结点中查与w 相交的对 象，最终查找到h 是与w 相交的对象。 l 一 i ：a i i 图2 2r 树插入及结点分裂后结果 日 l _ _ _ - _ _ - _ 一 口 l _ - _ - - - - - _ _ _ _ 一 门 i _ - _ - - _ - - - 一 口 图2 - 3r 树查询操作 由于r 树具有动态平衡的特性，因此它在处理空间对象时便具有很大的灵 活性以及比较高的效率。但也正是为了保持其动态平衡性，使得r 树的插入删 除过程较为复杂，从而在插入、删除频繁时可能产生振荡的现象，相应的降低了 效率。 此外，r 树有一个重要的特点，就是兄弟节点对应的空间区域可以互相重 叠，这样的特性使得r 树比较容易进行删除和插入操作，但却使空间搜索的效 率降低，因为区域之间有重叠，可能要对多条路径进行搜索后才能得到最后的结 果。 - i - _ _ _ - i - -一点 i一 -_ 一 - 口 埋 臼。 山东大学硕士学位论文 2 1 2r + 树与r 树 在r + 树中，兄弟节点的空间区域没有重叠，这样划分空间可以使空间搜索 的效率提高。r + 树对空间划分如图2 4 。 i - - - - ：a i 图2 - 4r + 树对地图空间的划分 对r 树来说，覆盖区域的大小和叠置是影响其搜索性能的重要因素。某一 层的r 树的覆盖范围是能包含这一层的所有节点覆盖范围的最小范围。叠置是 某一层的两个和多个节点的公共区域的总和。如果一个查询窗口落在k 个相互 重置的区域内，那么最坏要遍历k 个子节点。无叠置情况只有在数据点是预知 的情况下出现，并且对r 树使用紧缩技术，搜索效率会显著的提高。采取分割 矩形的方法会避免在中间节点之间出现重置。当较低层出现矩形叠置时，把矩形 分割成几个子矩形。r + 树在避免叠置的同时增加了树的高度，但这远小于搜索 多个短路径的开支。 r 唯树的改进主要是针对3 个方面： ( 1 ) 节点的重叠度； ( 2 ) 节点所覆盖的区域； ( 3 ) 最小邻接矩形的形状。 其中最重要的改进是对树的插入算法。由于采用了强制重插入的思想，从而 使索引的效率大大的提高。但酣树和r 树在删除以及搜索方面基本一致，即 两者的数据结构是相同的，因此由r 树索引转向r 木索引是比较方便的。移动 对象数据库中，因为牵扯到移动对象的运动速度，所以，r 树在移动数据库中的 山东大学硕士学位论文 扩展n r 树便提出。本文的移动对象近邻预测不确定性研究基于 r 树， 其结构将在后面章节中具体讲述。 2 2 移动对象k 近邻查询 近邻查询的有效实现，近年来一直是空间查询中研究的热点。例如，用户指 定某一位置或屏幕上的某一物体，要求系统从数据库中找出距离最近的5 个物 体。当使用者对空间物体的分布情况并不熟悉时，也可以进行最近邻居查询，例 如，已知某车现在的位置、时速和运动方向，查询未来一小时后，离它最近的几 个加油站或者食宿供给处。 解决近邻问题的最直接方法是计算数据集合中的每个点到查询点的距离，和 查询点之间距离较小的那些点被当作近邻。这种方法的搜索时间随着数据点数目 的增加呈线性增长。由于在空间数据库中数据点的数目巨大而且是多维的，采用 这种直接方法搜索近邻的效率非常低。因此，需要将数据集合预处理到一种数据 结构来加快近邻搜索。 目前已经有很多有效的近邻搜索技术被提出。这些技术大都是将数据集合中 的点预处理到一种索引结构，通过一定的策略对不必要访问的节点进行剪枝，尽 量减少访问节点的数量，从而提高空间查询的效率。由于r 树查询效率高，适 用范围广，并且支持高维的空间对象，很多算法都是基于r 树索引的。这里我 们先介绍的几种近邻查询技术都是基于r 树索引的，但对于其他索引结构也是 适用的。 2 2 1 静态环境的近邻查询 从上节可知，r 树中的每个叶子结点由若干个( ko i d ) 组成。其中 m b r ( m m m a lb o u n d i n gr