（计算机软件与理论专业论文）交通数据的多维索引研究.pdf

变通数据的多维索引研究 交通数据的多维索引研究 专业：计算机软件与理论 硕士生： 肖恒聪 指导老师：印鉴教授 摘要 通过对交通数据的分析处理来提高交通管理的效率，是现代智能交通系统 ( i t s ) 研究的核心问题。随着道路条件的日益完善，越来越多的交通数据被积累 了下来，从海量的历史交通数据中找到所需要的数据成为了一项耗时的工作。本 文利用多维向量的索引结构x 一树来组织交通数据，根据交通数据的时序性特点。 提出了一种新的相似性度量方法并将其应用到x _ 树索引中。实验表明，本文的 交通数据多维索引可提供快速的k 最近邻居( k n n ) 查询，为交通流量的预测和 异常探测等交通领域的数据挖掘应用提供便利。 关键词： 交通数据数据挖掘多维索弓 z 交通数据的多维索引研究 i n d e x i n gi r l u i t i d i m e n s i o n a l1 ：r a f f i cd a l ：a m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：x i a oh e n g c o n g s u p e r v i s o r ：p r o f e s s o ry i nj i a n a b s t r a c t t h ep r o b l e mo ff i n d i n gu s e f u li n f o r m a t i o nf r o mt h et r a f f i cd a t ah a s a t t r a c t e dm u c ha t t e n t i o ni nt h e i t s ( i n t e l l i g e n c et r a n s p o r ts y s t e m ) r e s e a r c hf i e l d h o w e v e r , t h er e t r i e v a lo fu s e f u li n f o r m a t i o nf r o mh u g e t r a f f i cd a t aw a s t e sal o to f t i m e t h i s p a p e r t r e a t st r a f f i cd a t aa s m u l t i d i m e n s i o n a lv e c t o r sa n du s e sam u l t i d i m e n s i o n a li n d e xs t r u c t u r e x - t r e et oo r g a n i z et h e n lan e ws i m i l a r i t ym e a s u r ei su s e df o ri n d e x i n g t h et i m e s e r i e st r a f f i cd a t aa n dt h ei n d e xs t r u c t u r ei sm o d i f i e d o u r e x p e r i m e n t ss h o wt h a tt h ei n d e xc a np r o v i d em u c hf a s t e rk n n r e t r i e v a l t h a ns e q u e n t i a ls c a n k e y w o r d s ：t r a f f i cd a t a ，d a t am i n i n g ，m u l t i d i m e n s i o n a li n d e x 3 交通数据的多维索引研究 1 1 背景 第1 章引言 随着计算机技术的发展和道路交通设施的日渐完善，城市道路和高速公路的 监测系统积累了大量的交通数据，如每天的车流量的记录和道路的占有率记录 等。如果能够正确地处理和分析这些数据，将给交通管理的决策提供有力的支持。 因此，如何将数据挖掘技术应用于交通数据咀提高管理的效率，已成为现代智能 交通研究的一个核心问题。 目前，交通数据的主要来源是铺设在道路下面的车流量监测器f 1 j 。这些监测 器是由磁感线圈和累加器组成的传感器，每当有车辆经过时，磁感线圈会产生感 应电流，使累加器加1 ，当到达固定的时间间隔时，传感器将累加器中的车流量 数值传到数据中心，并把累加器清零，重新开始计算车流量。发达国家的城市道 路和高速公路一般都铺设了车流量监测器，我国近年的道路建设中也开始了铺设 工作，没有铺设监测器的也大多在设计上为今后的铺设预留了位置。 在城市道路或高速公路的网络上，往往分布了成百上千的车流量监测器，数 据中心在每个时间间隔收到的是成百上千的车流量数据，这些数据不但包含了车 流量本身的信息，也包含了空间位置和时间的信息，是时空数据。时空数据挖掘 是数据挖掘的一个崭新的领域【2 l f 3 1 ，一方面，数据中包含了空间对象，空间对象 在空间位置上是相互关联的，而以往的数据挖掘方法往往认为数据的各属性是相 互独立的；另一方面，数据中包含了时间信息，所以时空数据也是一种时序数据， 代表的是动态的趋势，因此趋势分析和周期分析等时间序列的分析方法将显得更 为重要。 时空数据挖掘主要有以下的应用【3 】： 1 数据分害o ( s c g m c n t a t i o n ) ，主要是指带有时空信息的分类和聚类。 2 依赖分析( d e p e n d e n c ya n a l y s i s ) ，指通过对数据某些属性的分析，预测另一 些属性的值。 3 异常检测( d e v i a t i o na n do u t l i e ra n a l y s i s ) ，是从数据中找出背离预期聚类的 孤立点，快速发现异常的技术。 4 趋势发现( t r e n dd i s c o v e r y ) ，包括对时间序列挖掘，预测趋势走向等。 5 概化和细化( g e n e r a l i z a t i o na n dc h a r a c t e r i z a t i o n ) ，是指对时空数据的总体评 价和分层次的描述。 对交通数据而言，趋势发现很有价值。如果能够准确地、迅速地预测出车流 变通数据的多维索引研究 的分布以及各道路的拥塞情况，那么交通管理中心便有可能提前做好部署，防止 交通出现不良的状况。目前存在多种交通流预测的模型【4 】，当中的许多模型是需 要通过在大量历史数据中进行相似性查找来预测交通情况的。如近几年兴起的非 参数回归模型，它不需先验知识，只需寻找历史数据中与当前点相似的“近邻”， 通过那些“近邻”来预测下一时刻值。这种模型的一个最大的问题是寻找近邻的 速度太慢，一般的复杂数据的相似性查找都需要扫描数据库中所有的数据才能找 出“近邻”，这需要耗费大量的时问。另外交通状况的聚类和异常检测都有可能 要用到相似性查找。因此相似性查找的速度已成为瓶颈，若能提高它的速度，许 多工作的效率都将得到改善。 相似性查找一般包括了域查找( r a n g eq u e r y ) 和k 最近邻居查找( k n nq u e r y ) 。 如果对数据集s 中的对象之间定义一个在实数域r 上的相似性度量函数d ：a b - r ，对于给定的查询对象q 以及域半径r ，则域查找可以定义为： r a n g e o u e r y ( q ，i ) = a la s 且d ( a ，m r ) 。 而对于给定的查询对象q ，k 最近邻居查找j ( n n q u e r y ( q ) 则是找出s 的一个子 集s t ，s 。中包含k 个对象，且对s 冲的任意对象a 和s i 外的任意对象b ，有d ( a ，q ) d ( b ，q ) 。 以下是对大量的交通历史数据应用相似性查找的例子： a 找出新港西路东往西方向过去一年中与今天上午车流量变化最相似的一 天。( k n n 查找) b 找出与昨天广州大桥大塞车之前一小时车流量变化相似度低于1 0 的所有 历史记录。( 域查找) 如果不对数据集作任何处理，那么在进行域查找和k 最近邻居查找时，必须 依次计算数据集中所有的对象与查询对象之间的相似度。当数据集非常大的时 候，这种顺序扫描的方法会非常的缓慢。因此，有必要对已有的交通数据进行索 引，加快相似性查找的速度，从而提高交通数据挖掘的效率。 本文从多维向量的角度研究交通数据的索引方法，根据交通数据的时序性特 点，引入了新的相似性度量，并将传统的多维索引方法加以改进以适应新的相似 性度量，实验表明，该索引提高了交通数据相似性查询的效率。 1 2 论文的结构 本文分为五章。第二章介绍了多维索引以及相似度查找等方面的相关知识和 国内外研究情况，第三章详细讲述了两种不同的交通数据索引并给出了具体的实 现方法，第四章是实验的结果和分析，最后一章是总结和展望。 6 交通数据的多维索引研究 第2 章多维索引及相关知识介绍 无论从空间分布的角度还是从时间序列的角度，交通数据都可以看作是多维 向量。例如，令每一个监测器作为一维，若监测器总数为k ，则数据中心每次接 收到的数据便是一个k 维的向量。如果把交通数据看作是时间序列，那么每个时 间间隔也可以看作是一维，若监测器每分钟发送一次数据，则一个监测器在- - d , 时内发送的数据便是一个6 0 维的向量。因此，可以考虑用多维索引结构来组织 海量的交通数据，以便快速地进行相似性查找。 2 1r - 树 2 1 1r - 树的结构 最早出现的有效的多维索引结构是r 树【5 i 。r 树是b 树向多维空间的扩展， 它的结构和b 树类似。要了解r 树，必须首先介绍擐小限定矩形的概念。 定义2 - 1 ( 最小限定矩形) 在k 维空间上，n 个对象的最小限定矩形( m b r ) 是指能够把这n 个对象都包含在内的最小k 维超矩形。 k 维超矩形的结构为( l l ，u 1 ，i a ，u 2 , ，k ，u k ) ，其中k 是指第i 维的下界， u i 是指第i 维的上界。如一个二维矩形可以表示为( x 1 ，y l ，x 2 ，y 2 ) 。 k 维空阃的对象可以是点，可以是超矩形，也可以是其他任何形状，对r 树而言，则只有点和超矩形两种形式。图2 - 1 ( a ) 给出了二维m b r 的例子：点a , b ，c 的最小限定矩形是k 点d , e ，地的最小限定矩形是l ，点l l 埘的最小限定矩形是 m ，而矩形k k m 的最小限定矩形是r 。 图2 - 1 0 ) 二维m b r 7 图2 - 1 ( b ) r - 树结构 交通数据的多维索引研究 定义2 - 2 ( r - 树)r 树是索引多维空间对象的树状索引结构，它满足如下 性质： ( 1 ) 叶子结点若不是根结点，则它管辖m m 个空间对象； ( 2 ) 叶子结点的表示形式为( m b r ，对象集) ，其中m b r 为该叶子结点管辖 的所有对象的最小限定矩形，对象集则包含了该结点管辖的对象的所有 信息； ( 3 ) 非叶子结点若不是根结点，则它有m m 个子结点； ( 4 ) 非叶子结点的表示形式为( m b r 。，p t n ，p t r 2 ，p t r n ) ，其中m b r o 是 限定该结点所有子结点m b r 的最小限定矩形，即能把所有子结点的 m b r 都包含在内的最小矩形，p t r 则是指向第1 个子结点的指针； ( 5 ) 根结点若不是叶子结点，则至少有两个子结点： ( 6 ) 所有的叶子结点都在同一层上。 图2 - 2 给出了一棵简单的r - 树对二维空间对象的索引情况，a ，b ，c ，d ，e ，g ，h ， j 十个点按其空间分布被分到三个叶子结点中，k , l , m 分别是它们的最小限定 矩形。在叶子结点的上一层，有一个更大的矩形r 将k , l m 限定起来，组成一 个非叶子结点。 2 1 2r - 树的查找策略 r 树最初只提供点查找和超矩形查找的方法【5 】。随着应用领域的扩展，r 树 的后续研究给出了在r 树下的域查找和k 最近邻居查找的方法f 6 】。 点查找是指在索引中找到和查询点相同的点。点查找的策略是：给定一个查 询点o ( x 1 ，x 2 一，xk ) ，检查q 是否在根结点的m b r 中，则返回f a l s e ，如果是， 则检查根结点每个子结点的m b r ，看q 属于哪个子结点，便沿着该子结点继续 往下查找，一直到叶子结点，再依次匹配q 与叶子结点中的点，最后返回匹配 的信息。 矩形查找是指给定一个超矩形，在索引中找到所有落在该超矩形范围的点。 矩形查找的策略是：给定一个查询边界超矩形r ( x 1 ，y l ，x 。y 由，其中x i ，y i 分别 是矩形在第i 维的上下界。首先检查r 是否与根结点的m b r 有重叠的地方，如 果是，则检查根结点的每个子结点的m b r 是否与r 有重叠，若有重叠则继续查 找下去，直到叶子结点，再依次判断叶子结点中的点是否在r 中，最后返回所 有落在r 中的点。 域查找的策略是：给定一个查询点q ( x t ，x 2 ，x n ) 和半径r ，把根结点入栈。 8 交通数措的多维索引研究 然后进行如下循环：在栈中弹出一个结点，检查以q 为中心、r 为半径的n 维超 球体o 和该结点的m b r 是否相交，若相交则把该结点的所有子结点入栈， 若 该结点是叶子结点，则顺序检查结点中的数据是否在0 中。返回所有落在。中 的点。 k 最近邻居查找的策略如下： 给定一个查询点q ( x l ，x 2 ，x 。) ，初始化k 最近距离k d i s t 为无穷大，结果 集为空，将根结点入栈。然后进行如下循环直到栈为空，结果集中的便是k 个 最近邻居： 在栈中弹出一个结点，若为非叶结点，则依次计算该结点的每个子结点的 m b r 边界与q 的最短距离m i n d i s t ，若m 1 n d l s t d i s t ，将该子结点放入栈中： 若为叶子结点，则依次计算结点中的点p 与q 的欧几里德距离k 饵q ) ，如果 k ( p , q ) k d i s t ，则把p 放入结果集中，若结果集中元素个数大于k ，则把结果集 中距q 最远的点删除，并把k d i s t 置为结果集中的点与q 的最远距离。然后对 栈中的所有结点用启发函数m i n m a x d i s t 排序。 因为篇幅所限，m i n d i s t 和m i n m a x d i s t 的具体定义和描述请参看【6 】。 由于r _ 树的结构平衡，对空间的划分较为合理。在利用r 一树进行查询时， 能够迅速地通过查询点的坐标找到相应的入口，剪去了大量不相关的结点，从而 极大地提高了查找的效率。 2 1 3r - 树的构建 r 树是一种动态的索引结构，即它能够满足数据的插入和删除操作。构建一 棵r 树，就是从一棵空的r 树依次插入数据条目的过程【5 l or 树的插入方法和 b 树类似，是一个从根结点到叶子结点的过程，由于在数据和描述上的区别， r 树的插入方法在以下两个方面需要特别加以考虑： f 1 ) 如何选择一个叶子结点进行插入： ( 2 1 若一个结点在插入数据后容量超出了范围应当如何处理。 对于第一个问题，艮树采取了如下策略： 首先设根结点为当前结点，若当前结点不是叶子结点，则进行循环：检查当 前结点的所有子结点的m b r ，选择m b r 扩展最小面积便可以包含插入点的那 个子结点c ，并把c 设为当前结点。直到当前点为叶子结点，该结点便是要插入 的叶子结点。 由2 1 1 节知道，r - 树每个结点的条目数( 非叶结点的子结点数目和叶结点 的数据数目) 必须在m m 之间，因此r 树的插入操作有可能使某个叶子结点 9 交通数据的多维索引研究 的条目数超过上限m ，这时候，与b 树类似，r 树要采取结点的分裂策略。分 裂的主要思想是：从叶子结点开始，将条目数超过上限的结点分成两个结点，使 分裂后的两结点满足一定的评价标准( 评价标准有很多，如使父结点的m b r 变 动最少【5 1 ，使分裂后弼结点的重叠面积最r i d 7 1 ，等等) 。由于叶子结点的分裂将导 致父结点的条目数增多，这有可能使父结点的条目超出上限，因此在叶子节点分 裂后，要向上检查父结点是否已满，若满了，则需要在父结点上继续使用分裂策 略。如果根结点的条目也满了，则将根结点分裂，并创建一个新的根结点，它是 原根结点分裂后的两结点的父结点。 r 树的删除操作也分为两个步骤，首先按照点查找的方法找到要删除的条目 所在的结点，然后进行删除。 和插入的时候相反，数据的删除可能会导致结点的条目数少于下限m ，这个 时候，r 树采取的是重插入策略，即把条目数少于m 的结点删除，结点里的数 据重新插入到r 树中。由于叶结点被删除，因此有可能会导致叶结点的父结点 条目数少于下限，这时，用类似的方法对父结点剩余的条目进行重插入，不同的 是重插入的时候非叶结点的条目要插入到该结点原来的层次当中，以保证r _ 树 的平衡性。 无论是插入还是删除操作，都会导致r _ 树结点的m b r 发生变化，而底层 m b r 的变化可能会引起上层m b r 的变化，因此进行插入和删除操作后，需要 重新调整受影响结点的m b r 值，使其刚好限定该结点的所有子结点。 2 1 4r - 树的改进 r 树比较成功地索引了二维和三维空间的数据，但是后续的研究指出了r - 树的许多不足之处。如r - 树的分裂会导致各结点m b r 重叠的面积过大【7 l ，这会 造成在查找的时候访问到无用的结点，降低了查找效率。在维度较高的时候， r 树的分裂策略将导致m b r 重叠面积超过9 0 以上，它的查找效率甚至不如最 简单的顺序查找弼。 r + 树【7 】在分裂策略上对r _ 树进行了改进。r ，一树关注到了r 树的m b r 重叠 问题，在选择插入路径时考虑了m b r 的面积、空白区域和重叠大小，并通过引 入了强制重插入机制来改进r - 树的性能。 r + - 树在低维度时可以改善m b r 重叠的情况，但是随着维度的升高，r + 树 的策略也无法阻止m b r 重叠区域的增加。x - 树1 8 l 考虑到这种情况，引入了超结 点( s u p e m o d 0 。在结点无法找到合适的方法进行分裂时，便不进行分裂，任由结 点的条目数增加。这样处理可以避免由于m b r 重叠过多导致的查询效率的降低。 交通数据的多维索引研究 2 2 降维方法 2 2 1 维诅咒现象( d i m e n s i o n a l i t yc u r s e ) 所谓维诅咒现象，是指几乎所有的多维索引结构的查找时间随着维度的增加 成指数级增长，最终将退化为顺序查找1 9 1 。即便是被认为较能适应高维数据的 r i 树家族索弓l 结构也都不可避免地受到了维诅咒。一般认为，r 树和x 树的适 用维度范围在2 0 维之内，但交通数据的维度至少是上百维的，如果不作任何降 维处理，索引将很难达到好的效果。 2 2 2 高维数据索引框架 为了使索引技术能应用到更高维的数据，必须对高维数据进行降维。降维的 目的是希望能将高维数据转化成相对低维的数据，且两两数据之间的相似度在降 维前后尽量保持一致。f a s t m a p l l 0 】能在降维之后保持数据间的欧几里德距离和降 维前几乎完全一样，但这种精确的降维方法往往效率低下，用f a s t m a p 降维前需 要先计算出向量间的相似性矩阵，而且一旦有新数据插入，便需要重新计算所有 的降维结果。目前大多数的降维方法都是通过由f a l o u t s o s 等提出的g e m i n i ( g e n e r i cm u l t i m e d i a i n d e x i n g ) 框架 1 1 1 来与多维索引结构相结合的。 g e m i n i 框架可以表示为如下几个步骤： ( 1 ) 确定高维数据的相似性距离函数d ( a ，协： ( 2 ) 用一种降维的方法将数据从高维空间映射到低维空间； ( 3 ) 在低维空间中找到一个相似性距离函数d l ，使得对于高维空问中所有的 点a 、b 在低维空间的对应点a 、b ，有d 1 ( a ，b ) d ( a ，b ) 。具有这种性 质的相似性距离函数称为原函数的下界( l o w e rb o u n d ) 估计函数； ( 4 ) 用r - 树或其改进版本来索引降维后的数据； ( 5 ) 进行查找时，先在r - 树上找到符合条件的候选集，再找到候选集中数据 对应的原高维数据，进行重新计算和确认，将不满足条件的数据过滤掉。 g e m i n i 框架中最关键的步骤是第三步，即在降维后找出原相似度函数的下 1 1 交通数据的多维索引研究 界估计函数。可以证明了只要能找到这样的相似性距离函数，g e m i n i 框架就 可以毫无遗漏地进行高维数据的域查找和k 最近邻居查找【“1 。 设原数据维度为n ，降维后维度为n ，所有降维后的数据已被r 树索引。 o 为n 维查询点，r 为域查找的半径，则用g e m i n i 框架的域查找算法和k 最 近邻居算法可以分别描述为： r a n g e q u e r y ( q ，r ) ： 1 用同样的降维方法把q 转换为n 维向量q l ； 2 调用r - 树索引的域查找算法，查询点和半径分别为q 。和r ，得到候选 集c ； 3 将c 中每个n 维向量a a 还原成原来的n 维向量a 。，并返回所有满足 d ( a h 。q ) r 的向量a 科。 k n n ( q ) ： 1 用同样的降维方法把q 转换成n 维向量q 。； 2 调用r - 树索引的k n n 查找算法，查询点为q l ，得到k 个最近邻居 a l - a k | 3 将距q 1 最远的邻居赴还原成n 维向量氐，计算d ( 赴，q ) 的值； 4 调用r a n g c q u c r y ( q ，d c ，q ”，得到候选集s ，在s 中用j 顿序查找 方法找出与o 最近的k 个邻居。 由上面的算法可以看出，如果下界估计函数d l 越接近原来的距离函数d ， 则在域查找和k 最近邻居查找时得到的候选集中的元素个数会越少，这将加快 查询的速度。因此，如何在降维之后找到一个尽量逼近原相似性距离函数的下界 估计函数，是高维数据索引研究的重要问题。 2 2 3 离散傅立叶变换( d f d 时间序列是一种最常见的多维向量。早期对时间序列的降维研究一般把注意 力集中在离散傅立叶变换上【9 1 1 1 2 1 。傅立叶变换是用一系列的正弦( 余弦) 波的 叠加来逼近时间序列的方法。设一时间序列为x 。，t - 0 ，1 ，n 一1 ，离散傅立叶 正变换将该序列转换为n 个复数x f ，f _ - 0 ，i 一，n i ，公式如下： 蜀= 1 石羹一_ 坤m 厂，。k 奎望塾塑竺童丝室! ! 竺塞 其中i 是1 的平方根。可以通过离散傅立叶的反变换将xf 还原成xt ，公式如 下： n - 1 耽= 1 ，l x f e x p ( j 2 n f t n ) t = 0 , 1 ，腮一1 同 因为复数可以用实部和虚部来表示，因此，离散傅立叶变换相当于将一个n 维的向量转变为2 n 维的向量。离散傅立叶变换有个特点：两向量之间的欧几里 德距离在离散傅立叶变换前后是一样的，而且经过转换后向量通常前几维的绝对 值较大，而后面的数值则接近于零。因此，只要用离散傅立叶变换后的前几维数 值，便可以近似地表示原来的向量 9 1 。由于两向量前几维的欧几旱德距离必定小 于两向量问的欧几单德距离，所以降维后的欧几里德距离便是原欧几里德距离的 下界估计函数。 离散傅立叶变换与索引相结合的具体方法是：将n 维的向量经过离散傅立叶 变换后，取出前2 k 个系数( k n ) ，用r 树进行索引，然后用欧几里德距离作为 相似性距离函数，便可用g e m i n i 框架进行域查询和k 最近邻居查询。 2 2 4 离散小波变换( d w t ) c h a n 等人提出了用h a a r 小波来对时间序列进行降维，并认为由于离散小波 变换对于维数n 的时间复杂度为o ( n ) ，比离散傅立叶变换的0 ( nl o gn ) 要小， 而且实现比较简单，因此用离散小波变换对时间序列进行降维要优于离散傅立叶 变换【1 3 i 。但w u 等人通过大量实验表明，由于离散小波变换的下界估计函数没 有离散傅立叶变换的下界估计函数那么接近原距离，因此它需要更长时间的后续 检查，这导致了离散小波变换和离散傅立叶变换对时间序列的降维效果基本相当 的1 1 钔。 h a a r 小波定义见参考文献i t 3 ，对时间序列进行h a a r 小波变换，实际上是 对该时间序列的相邻的两两分量之间不断取均值的过程，下面是用h a a r 小波变 换时间序列( 9 ，7 ，3 ，5 ) 的例子： 分解个数均值系数 4 ( 9 7 3 5 ) 一 2 ( 84 ) ( 1 1 ) 1 ( 6 )( 2 ) 首先，将序列相邻两两分量取均值，得到( 8 ，4 ) ，系数是平均前的第一个分 量与均值之差，所以得到( 1 ，- 1 ) 。然后再平均后的序y u ( 8 , 4 ) 两两相邻分量取均值， 交通数据的多维索引研究 得到6 ，同理得到系数8 - 6 = 2 。这样，对序列( 9 ，7 ，3 ，5 ) 进行h a a r 小波变换后得到 的序列为( 6 ，2 ，1 ，1 ) 。要将序列还原，只需按逆方向操作即可。 若对n 维时间序列h a a r 小波变换后，只取前2 1 个系数( 2 1 ) ，可以证明 h a a r 小波变换后的欧几里德距离满足g e m i n i 框架的下界估计函数条件【l ，也 就是说，两序列降维后的欧几里德距离要小于原序列的欧几里德距离。因此，可 以用g e m i n i 框架进行域查找和k 最近邻居查找。 2 2 5 分段近似法( p a a ) 和自适应分段近似法( a p c a ) 分段近似法【1 5 】是一种很直观的降维方法，如果一个n 维的向量要降到k 维， 则将n 维向量平均分成k 段，以每n k 个分量为一段，取每段的平均值作为新向 量的一个维。以下是分段近似法的一个例子：设原向量( 1 ，3 ，4 5 ，3 ，2 ，o 1 ，3 ，2 ，4 是1 2 维的向量，要降到4 维，分段近似法将每1 2 4 = 3 个分量取平均值，便得 到降维后的向量( 2 6 7 3 3 3 ，1 3 3 ，4 ) 。 分段近似法对于欧氏距离的下界估计函数为： d r ( x ，y ) = 历二叩) 2 其中x i ，y i 为原来的1 1 维序列墨y 的第i 个分量，x ，y 是用分段近似法降维后的 n 维序列。可以证明d r u j ( q l i ) 2i fc i k 0o t h e r w i s e u i = m a x ( q “：q “i ) b = m a x ( q h ：q 【+ r ) 容易证明，l b _ k e o g h ( q ，q d t w ( q ，c ) 【2 2 j 。因此它可以作为估计受限d t w 距离的下界估计函数。 有了下界估计函数l b _ k e o g h ，就可以对时间序列进行以受限d t w 为相似 度的多维索引。具体的方法是：对x 树应用域查找和k 最近邻居查找时，只需 对查询的向量q 进行矩形化，即按照l b _ k e o g h 中u i 和k 的计算方法找出q 的 每个分量q j 的u j 值和l i 值，然后将查询点q ( q t ，q ) 转化为查询矩形r ( l 1 ， u l ，ku 。) 。利用l b _ k e o g h 函数，x - 树下的域查找算法和k 最近邻居查找 交通数据的多维索引研究 算法可以改造为如下： 域查找算法：( 入口参数为查询点q ，半径r ) ( 1 ) 将点q 转化为查询矩形r ( 将根结点放入队列q u e u e 中 f 3 1 从q u e u e 中取出一个结点设为当前结点。若当前结点不是叶结点，计算 查询矩形r 与当前结点所有子结点m b r 的m i n d i s t 距离，如果 m 1 n d i s t r ，则将对应的子结点放入队列q u e u e 中。若当前结点是叶结 点，则计算q 与结点中所有向量c 的l b _ k e c i g h 距离，若l bk e o g h ( q ，c ) r ，则继续计算q 和c 的受限d t w 距离d t wk e o g h ，若 d t w _ k e c l g l l ( q ，0 r ，则将向量c 放入r e s u r 集中。 ( 4 ) 若q u e u e 不为空，跳到第( 3 ) 步 ( 5 ) 返回r e s u l t 集 k 最近邻居查找算法：( 入口参数为查询点q ) ( 1 ) 将点q 转化为查询矩形r ，将k 最近邻居距离k d i s t 设为无穷大，k 最 近邻居集k n e a r e s t 设为空； ( 将根结点放入队列q u e u e 中： ( 3 ) 从q u e u e 中取出一个结点作为当前结点。若当前结点不是叶结点，计算r 与当前结点所有子结点m b r 的m i n d i s t 距离，如果m i n d i s t k d i s t ， 则将对应的子结点放入q u e u e 中。若当前结点是叶结点，对结点中的每 一个向量c ，顺序计算l bk e o g h ( q ，q ，若l a _ k e o g h ( q , c ) u it h e n d i s t a n t = d i s t a n t + ( b u i ) 2 e l s ei f ( u i l i ) t h e n d i s t a n t = d i s t a n t + ( u i 1 i ) 2 e n d r e t u r n s q r t ( d i s t a n t ) e n d 3 3 3 受限动态时间弯曲的不足和改进 对d t w 的弯曲路径进行限制是出于以下的考虑：一是容易索引，二是可以 防止弯曲路径边缘化( 图3 - 5 a ) 。弯曲路径边缘化实际是将序列中的某些维被过 度的扩展，导致了各维度间的重要性不均衡。如图3 5 a 所示，通过弯曲路径可 知，序列0 和c 的d t w 距离为： d t w ( q ，c ) = d b a s e ( c l ，q o + d b a s e ( c l ，q g + + d b a s c ( c l ，q n t ) + d b a s e ( e 2 ，q 。) + d b a s c ( c 3 ，q n ) + + d b a s e ( c , q o ) 。 可以看出，c - 和q 。的重要性被严重夸大了，它们分别使用了n 1 次，这将 造成两序列的相似度比实际的相似关系偏小。如图3 5 是两个十维的序列c ( 1 0 ，2 ，1 ，1 ，2 ，1 ，1 ，1 ，2 1 ) 和o ( 1 ，9 ，1 0 , 9 ，l o , 9 ，1 0 ，9 ，l o , 3 ) ，它们的动态时间弯曲路径恰好 如图3 - 5 ( a ) 所示，从直观上来看，这两个序列是很不同的，但是由于弯曲路径边 缘化，它们的d t w 距离仅为1 0 6 ，不能正确反映实际的相似度。引入3 3 2 节 对d t w 路径的限制后，这种情况得到了部分的改善。 q c ( a ) 图3 - 5 弯曲路径边缘化 交通数据的多维索引研究 但是3 3 2 节所用的弯曲路径限制方法也有弊端，如果弯曲路径限制参数 r e s t r i c t 取得太小，则计算出来的d t w 距离与欧几里德距离差别不大，丧失了 d t w 的优点；如果r e s t r i c t 取得较大，则容易出现图3 - 6 的情况：虽然弯曲路径 的边缘化没有图3 5 严重，但是仍然出现了某些维的作用被严重夸大的现象。如 c 4 和q 8 占去了大部分的路径，个别维度的过度扩展将使得序列曲线变形比较严 重( 图3 - 6 啷) 。 8 qa 、 卜 、 图3 6 限制弯曲路径仍会出现路径“局部”边缘化 针对以上的不足，本文对弯曲路径的限制方法作了改进，把对弯曲路径全局 的限制交成局部的限制，从而定义了一种新的局部受限的动态时间弯曲距离 d t wl o c a l 。具体的限制如下：局部限制常数设为k ，则向量每维只能最多扩展 k 次，如果在弯曲路径中对某序列的一维连续使用超过k 次，必须强制性地使弯 曲路径跳向该序列的下一维，更直观地，在弯曲路径图中，如果路径沿着一个方 向( 上或右) 连续走了k 步之后，第k + 1 步就不能再向相同的方向走了，必须 向斜上方跳一格。如图3 7 所示，路径从( c l ，0 1 ) 开始，到( c 1 ，q 3 ) ，此时已经 连续向上走了3 步，必须强制性地跳到( c 2 ，q 4 ) 。同理，从( c 4 ，q s ) n ( c 6 ，0 5 ) ， 因为同时向右方走了三步，因此要向斜上方跳一格。经过这种局部限制以后，由 于每个点的扩展次数有限制，所以不会出现序列c 的一个点匹配序列o 的半个 序列这种现象，相似度计算更加合理。 q k = 3 l 234 56 - 891 0 c 图3 7 局部受限的弯曲路径 o 哇 l 交通数据的多维索引研究 3 3 4 索引以局部受限d t w 为相似度的序列 本节将使用x 树的索引结构来索引以局部受限d t w 为相似度的序列。首先 观察局部受限的d t w 可能出现在弯曲路径的什么位置。考察长度为1 0 的两序 列的两种极限情况：一种是尽可能地先向上走、再向右走，另种是尽可能地先 向右走、再向上走，分别可以表示为图3 - 8 ( a ) 和图3 培( b ) 。考察图3 - 8 0 ) ，容易 知道，所有从( c l ，q 1 ) 出发，最终到达( c 1 0 ，q 1 0 ) 的弯曲路径中，满足局部限 制条件k = 2 的路径是不可能出现在黑色折线的左上方区域的，同样地，也不可能 出现在图3 - 8 ( b ) 的黑色折线右下方的区域。因此这两条折线是k = 2 时局部受限 d t w 弯曲路径可能出现区域的边界。两幅图重叠起来便可以得到局部受限d t w 弯曲路径的有效区域( 图3 - 8 ( c ) ) q c k = 2 ( a )嘞 图3 - 8 局部受限弯曲路径的有效区域 c k = - 2 观察图3 8 ( c ) 可以发现，在弯曲路径中，c 1 只可能和q 1 ，q 2 搭配，c 2 只可 能和q i q 4 搭配，哟此类推，序列c 所有的点都可以找到它在q 中可能搭配 的点。因此，可以定义局部受限的动态时间弯曲的下界估计函数。 首先，令u i = m a x ( c i 可能搭配的点q j 的值 ) ，l i = m i n ( c i 可能搭配的点 q j 的值 ) ；那么，局部受限的d t w 距离的下界估计函数定义为： l b l o c a l ( q ，c ) 它的形式与l bk e o g h 是一样的，但是u i 和l i 的计算方法却是不同的。下 面讲述如何找出在q 中所有可能与c i 搭配的点。因为这些q 中的点必然是连续 的，令q b c 咖为起始点，q 。n d 为终止点，则在总维数为n ，限制为k 的弯曲路径 交通数据的多维索引研究 中，c i 对应的o b e g i n ( d 和q 。姻的参数b e g i n 与e n d 可通过下式计算( 其中的“” 若不能整除，则取商的整数部分1 ： b e g i n ( i ) = m a x ( ( i - 1 ) k ，1 1 一k ( n i + 1 ) + 1 ) ， e n d ( i ) = r a i n ( i + l 【n - ( n - i ) k ) ， u i = m a x ( q b e g i n ( i ) ：q 。d o ) ) ， l i = m i n ( o b c 鲥o ：q c h a ( i ) ) 有了下界估计函数之后，就可以按照3 3 2 节的域查找和k 最近邻居查找的 算法，用x 一树索引以局部受限d t w 为相似度的多维向量。不同的是下界估计函 数由l b _ k e o g h 变成l b _ l o c a l ，两序列的相似度也由d t w _ k e o g h 变成了 d t w _ l o c a l 。由于篇幅关系，局部受限的动态时间弯曲d t l l o c a l 计算方法在附 录2 中给出。 3 3 5 降维处理 如果向量的维度超出了x - 树的索引范围，需要使用降维的方法。k e o g h 等 人提出了在受限d t w 作为相似度时，可用分段近似法( 见2 2 5 节) 来对向量 进行降维【2 2 l 。 设对n 维向量c 进行分段近似后得到的n 维向量为e 正。，：n ) ，则 l b _ k c o g h 的下界估计函数是： 加一咕播n 【嚣( 亭i 篓- - l i ) 2 毯 谚= m a x ( u 甜_ 1 ) + 1 1 ，u 和) l i = m i n ( l 斋( f l + i ，l n ) 然后，利用g e m i n i 框架，就可以索引以d t w _ i o c a l 为相似度的高维向量 使用d t wl o c a l 作为相似度的索引结构仍然可以沿用上述的降维方法，不 交通数据的多维索引研究 最后，总结一下带降维的交通数据时序索引的流程：首先用分段近似的降维 方法把已经分割好的所有交通序列c 转化成降维后的e ，然后建一棵空的x 树， 把e 逐个插入x 树索引中。进行域查询和k 最近邻居查找时，对查询向量q 用本节介绍的方法算出垡和互，组成查询矩形r ( h ，弘。，k ，! k ) ，然后分别 进行以下步骤： 域查找：从根结点开始，计算当前结点第一个子结点n o d e 的m b r 与r 的 m i n d i s t 距离，如果m i n d i s t 小于半径r 则继续向下查找，否则计算下一个子 结点。若到达叶结点，则计算叶结点内的向量e 与q 的l bp a a 距离。对于所 图3 - 9 域查找流程图 交通数据的多维索引研究 有l bp a a ( e ，q ) r 的向量e ，计算它降维前的向量c 与q 的l b 1 0 c a l 距离，若 l bl o c a l ( c ，r 再计算q 与c 的局部受限d t w 距离d ，若d r ，则把c 加入 到结果集r e s u l t 中。最终返回r e s u l t 集。域查询的流程图如图3 9 所示。 k 最近邻居查找：将k 最近邻居距离d 置为无穷大，从根结点开始，计算依 次计算当前结点子结点n o d e 的m b r 与r 的m i n d i s t ，若m i n d i s t d 则继续往下 查找，否则计算下一个结点。若到达了叶结点，则计算时结点的向量e 与q 的 图3 1 0k 最近邻居查找流程图 3 l 交通数据的多维索引研究 l b _ p a a 距离。若l bp a a ( e ，q ) d ，继续计算e 降维前的向量c 与q 的l bl o c a l 距离，若l b _ l o c a l ( q ，c ) d ，再计算q 与c 的局部受限d t w 距离，若 d t w l o c a l ( q ，q d ，则把c 加入k n e a r e s t 集中，若k n e a r e s t 集元素个数大于k ， 便把距q 最远那个向量删除，同时把d 调整为新k n e a r e s t 集中与q 最远的向量 的距离。k 最近邻居查找流程如3 一l o 所示。 交通数据的多维索引研究 第4 章实验结果和分析 4 1 实验数据的描述 本文的所有实验数据来自美国华盛顿州高速公路在2 0 0 4 年2 月1 7 日至3 月 1 0 日的交通流量记录。部分高速公路的分布如图4 - 1 所示，在高速公路上分布着 1 0 2 7 个车流量监测器，这些监测器每一分钟发送一条数据到数据中心。 图4 - 1实验所用交通数据的部分道路示意图 交通数据的多维索引研究 4 2 交通数据平面索引的实验结果和分析 从3 2 1 节可知，对全部1 0 2 7 个监测器所组成的超高维向量作交通数据平面 索引是没有太大的现实意义的。因此，本文在实验时按照地域的分布抽取了不同 数量的监测器组成了不同维度的多维向量集。如图4 - 1 中由椭圆圈起的灰色部分 是本文采集1 2 8 维向量所选取的监测器所在的地理位置。 首先，对降维方法的效果作比较。实验分别用不同的降维方法与x -