受限网络的移动对象聚类研究

1、受限网络的移动对象聚类研究1 引言随着3G时代的到来，众多具有定位功能的无线手持设备的大量普及，定位技术和无线传感器技术进一步的发展，都使得移动对象的大量位置信息可以实时的获得，除了对这些大量的实时数据进行高效的管理和查询，还需要对这些数据进行有效的分析，挖掘移动对象运动的知识，找出运动过程中有趣的模式变化，以此来进行系统负载均衡，进行有目标有针对性的销售等。例如可以发掘出手机移动用户的运动模式，找出某段时间哪些服务区内的用户密集，以合理的分配手机频率带宽。另外还可以对城市道路上车辆的运动模式的变化进行交通控制和预测等。聚类分析是就对数据对象进行分组，使得同一个组中对象之间具有较高的相似度，而

2、不同组中的对象差别较大。聚类分析构成了基本的数据分析功能，已经广泛的应用在许多应用中，包括图像处理、数据压缩、模式标识以及市场研究。通过聚类可以识别出密集和稀疏的区域，因而发现全局的分布模式，以及数据属性之间有趣的相互关系。对移动对象进行聚类分析可以应用于天气预报（飕风聚类）、城市交通阻塞的预测、动物迁徙分析、移动计算、异常分析等。目前的大部分聚类方法主要针对静态的数据对象，而移动对象的聚类工作还很少。Yifan Li等人在10中考虑到移动对象本身的特征，利用移动对象的运动趋势，引入了一种移动微聚类（moving mirco-cluster）的概念第一次提出了移动对象聚类的问题。所谓移动微聚类

3、就是用来表示一组在现在和将来的位置都很接近的移动对象的集合。它综合考虑了移动对象的位置和速度这两个运动参数。通过一个矩形框来限定每个移动微聚类。随着移动对象的运动状态的不断变化，这个矩形框也会随之变化，为了保证移动微聚类的有效性，在某个适当的时刻，移动微聚类的矩形框将会发生分裂，矩形框内的移动对象将被重组。然而此方法聚类限定框经常超出，维护代价很高。维护聚类分裂和合并的数量多，并且占了算法的整个运行时间。最近，Kalnis等人12也定义了运动聚类的概念，提出了从一个时空数据集（历史轨迹记录）中自动发现运动聚类的三种方法。与聚类轨迹和挖掘运动模式相比，运动聚类的标识可能随着其位置和内容的改变而保

4、持不变。然而这些工作都是对空间中的移动对象进行处理，主要考虑的是移动对象本身的一些运动特征，并没有考虑到移动对象所在的空间，例如道路网络的拓扑对于移动对象聚类的影响等。在许多真实的应用中，移动对象的运动大多都是受限于一定的空间网络中的（典型的为道路网络上的车辆）。因此通过网络距离而不是欧氏距离来定义对象之间的相似度/不相似度更具有实际意义。然而目前的移动对象聚类的工作都是基于欧氏距离的，不能运用到受限网络的移动对象聚类上。而已有的空间网络上的对象聚类方法虽然基于路网距离，但不是动态的，不能对路网上的移动对象进行聚类。本文将针对受限于道路网络上的移动对象聚类方法进行研究，根据网络距离重新定义受限

5、网络的移动对象聚类问题，提出新的基于路网距离的移动对象聚类方法。由于移动对象自身的动态性（位置随着时间连续的发生改变）和在路网上运动的复杂性以及路网上对象相似度衡量标准的改变（由欧氏距离变为路网距离），这些都增加了路网上移动对象聚类的复杂性，传统的聚类方法很难适用于路网上移动对象的聚类分析。我们将首先根据网络距离相似度标准重新定义受限于道路网络上的移动对象聚类问题，然后从加快道路网上对象的最短路径距离计算入手，引入网络结点编码的方法来加速网络距离的计算。基于此提出一套基于磁盘的存储和索引方法以支持对大量的对象进行高效的聚类分析。最后我们将利用路网上对象运动的特点，提出新的基于路网距离的移动对象

6、聚类方法，对城市道路网络上车辆的拥堵情况进行有效的检测和预测，并通过聚类算法来支持路网上新型的查询处理。存在的聚类方法由于难以挖掘出对象的其它可用信息，仅仅通过对象自身的空间相似性如距离来进行粗糙分组，需要反复的扫描所有的对象信息，其代价很高。我们观察到：1）由于对象运动受限于网络，对象的聚类可以利用路网的信息来发掘，聚类与路网的结点和边相关。例如路网上在同一个边或相邻边上的车辆很可能在一个聚类中。而位于不相邻的路段上的车辆不太可能聚类在一起；交通拥堵通常发生在城市道路路口，即路网结点附近的车辆很可能聚类在一起。2）可以将移动对象通过路网来表示，即所在的路段和相对于路段起点的距离位置，这样移动

7、对象的运动信息本身已经包含了路网边和结点等信息，我们可以在对他们聚类时利用这些信息来提供聚类的精度和效率。3）路网中移动对象具有一定的规律性，且有一定的运动趋势，例如：某个移动对象在某个路段的运动状态和运动特征基本上相似：以一个相对稳定的速度运动朝一个特定的方向运动。我们可以利用其来较为精确的预测对象未来的运动并进一步预测聚类的变化，如分裂和合并。因此对于路网的情况，我们可以开发出网络的特征来缩减搜索空间，避免一些不必要的距离计算（如运动在不相邻路段上的对象的路网距离）。通过使用移动对象表示中包含的边和结点的信息来改进聚类的精度和效率，我们提出两种新的聚类方法，基于边的聚类（一种层次聚类方法）

8、和基于结点的聚类（一种划分和层次混合聚类方法）。这两种新的算法开发了网络的特征来缩减搜索空间，避免一些不必要的距离计算（如运动在不相邻路段上的对象的路网距离）。具体来说，我们通过使用移动对象所包含的边和结点的信息来改进聚类结果的精度，提高聚类算法的效率。为了保证聚类结果的有效性，聚类将随着其中的移动对象一起运动，在适当的时刻也会发生分裂和合并。我们将通过聚类结果所包含的边和结点的信息以及移动对象运动的规律性和运动趋势来预测聚类的分裂和合并，尽可能的降低移动对象聚类的总代价。本文的贡献：1根据路网上移动对象的网络距离定义了路网上移动对象的聚类问题2引入网络结点编码技术来加速网络距离计算，并提出了

9、一套基于磁盘的存储方案。3利用交通路网的特征，提出了两种新的聚类方法，分别利用结点和边信息来减少搜索空间，避免一些不必要的距离计算。4对提出的技术进行了一系列的实验评估，结果验证了我们提出的聚类方法在对路网上的移动对象进行聚类时具有高的准确度和效率。2 相关背景和基本模型2.1 问题和挑战当聚类的目标从静态的空间对象改变为运动在道路网络中的移动对象时，聚类的复杂性将大大增加，现有的聚类方法也不再适用。在这种环境下聚类面临的问题和复杂性主要包括下面三个方面：1） 路网上移动对象的固有特征路网上的移动对象数量巨大而且它们的位置会随着时间发生连续的改变，使得聚类的结果也可能随着时间、随着移动对象的运

10、动而变化，即使对象很小的位置改变也可能导致完全不同的聚类结果。同时由于交通系统自身的动态性、随机性和复杂性，对象在路网上的运动也异常复杂，使得很难抓住对象的趋势。2） 路网上移动对象之间相似度的度量标准由欧氏距离变为路网距离传统方法上在计算移动对象之间的相似度时，所采用的方法是直接计算移动对象之间的欧氏距离（Euclidean distance），而在道路网络的情况下，应该考虑使用网络距离（network distance）来计算移动对象之间的相似度。这又会增加聚类计算的复杂性。两个任意对象的网络距离需要代价很高的最短路径算法，不能在常量时间内计算出来，另外聚类不是针对道路网络的结点，而是运动

11、在路网图边上的任意位置上的移动对象，因此结点间的最短路径算法也要进行一定的变化。目前的几个聚类方法中的一些概念如聚类中心、总结概要等难以在路网情况下定义。具体来说，给定路网上的一组对象，由于不存在一个唯一的网络点，离这组中所有点的平均距离最小，因此不能使用网络距离来定义他们的聚类中心，而且即使有这样的中心点，找到他们的代价也很高。3） 路网上移动对象聚类对相邻的移动对象产生影响，相邻聚类之间会产生影响路网上的移动对象聚类不仅会随其中对象的运动而变化，同时反过来聚类也会影响周围移动对象自身的运动，如使其减少速度，使已有的聚类变得更大。另外相邻的聚类之间也很可能逐渐结合形成更大的聚类。因此移动对象

12、运动的路网限制要求我们必须重新定义其聚类问题。下面我们将定义路网上移动对象聚类的基本模型，具体包括道路网络模型、移动对象路网表示模型、基于网络距离相似性的定义、移动对象间相似度和聚类间相似度的定义、聚类特征的定义、聚类中心的定义、聚类评价函数的定义等。另外，聚类随着其中移动对象的运动而移动，同时为了保证聚类的有效性，必须在某一时刻进行聚类分裂和合并，这都会导致聚类特征的更新，因此我们对聚类特征的这些更新操作也进行了定义。2.2 问题定义和基本模型道路网络模型：定义1：一个道路网络可以表示为一个无向带权图G=(V, E, W)，其中V时顶点的集合（如道路的结点），E是边的集合，W为正的实数集合（

13、W：E->IR+），表示边对应的权值移动对象路网表示模型：定义2：道路网络上的移动对象在某个时刻的位置可以表示为（Oid, ni, nj, pos, v, t），其中Oid为对象ID，ni和nj是对象所在的路网边的两个结点，pos0, W(e)是对象离结点ni的距离。v是对象的速度。t为对象更新时间。移动对象的位置建模为时间的线性函数，假设在路网上的每一个边上移动对象匀速运动。 基于路网距离相似性的定义：定义3：假设移动对象p和q在某一时刻位于同一条网络边上，其位置分别为：（na, nb, posp）和（na, nb, posq）则同一边上的移动对象间直接距离定义为：Dd(p, q) =

14、 |posp-posq| （其中对象p和q在同一条路网边（na, nb）上）；对象和结点间的直接距离定义为：Dd(p, na) = posp和Dd(p, nb) = W(na, nb) -posp 定义4：给定网络结点ni和nj，则结点间的网络距离Dn(ni,nj)定义为从结点ni到结点nj的最短路径距离。假设移动对象p和q在某一时刻位于不同网络边上，其位置分别为：（na, nb, posp）和（nc, nd, posq），则移动对象间的网络距离定义为：Dn(p,q) = min x(a,b), y(c,d) (Dd(p,nx)+Dn(nx,ny)+Dd(ny,q) 定义5：移动对象相似度M(

15、p,q) = Dn2(p,q) + a(Vp-Vq)2 其中a是与速度属性相关的一个权值。由于速度决定了对象将来的位置，对聚类特征的更新具有很大的影响，因此对象之间的相似度除了考虑对象的位置之外，还考虑了对象的速度。为了提高对大量对象的聚类速度和聚类的可扩展性，我们引入了文献中定义的聚类特征的概念，并对其进行了扩展，加入了速度的汇总信息以及聚类所在的路网边的信息。定义6：聚类特征定义为：CF = (N, CX, CV, E, t) 其中N是聚类中包含的对象个数，CX为聚类所包含的所有对象在t时刻的位置的和，CV为聚类所包含的所有对象在t时刻的速度的和，E是聚类所在的网络边的集合，t为聚类的更新

16、时间聚类特征是对给定子聚类的统计汇总。它记录了计算聚类和有效利用存储的关键度量，因为它汇总了关于子聚类的信息，而不是存储所有的对象。聚类评价函数的定义（平均误差准则）：定义7：平均误差总和：E(Ci,mi): i 1,k = i 1,k pci Dn(p, mi) 其中p为路网上的数据对象，mi是聚类Ci的平均值。平均误差准则试图使生成的聚类结果尽可能的紧凑和独立。2.2 进一步的观察移动对象的运动受限于道路网络后，给其聚类方法带来了巨大的问题和挑战，然而另一个方面，道路网络也给聚类带来了更多的额外信息，可以帮助提高聚类的效率和精度。我们进一步观察到：1） 路网中移动对象具有一定的规律性，且有

17、一定的运动趋势，例如：某个移动对象在某个路段的运动状态基本上相似：以一个相对稳定的速度运动朝一个特定的方向运动；某些移动对象在某条路段上的运动特征基本上相似等。我们可以利用其来较为精确的预测对象未来的运动并进一步预测聚类的变化，如分裂和合并。2） 由于对象运动受限于网络，对象的聚类可以利用路网的信息来发掘，聚类与路网的结点和边相关。a) 路网上在同一个边或相邻边上的车辆很可能在一个聚类中。而位于不相邻的路段上的车辆不太可能聚类在一起。b) 交通拥堵通常发生在城市道路路口，因此路网结点附近的车辆很可能聚类在一起3） 可以将移动对象通过路网来表示，即所在的路段和相对于路段起点的距离位置，这样移动对

18、象的运动信息本身已经包含了路网边和结点等信息，我们可以在对他们聚类时利用这些信息来提供聚类的精度和效率。4） 存在的聚类方法由于难以挖掘出对象的其他可用信息，因此仅仅通过对象自身的相似性如距离来进行brute-force分组，需要反复的扫描所有的对象信息，其代价很高。而对于路网的情况，我们可以开发出网络的特征来缩减搜索空间，避免一些不必要的距离计算（如运动在不相邻路段上的对象的路网距离）。3 路网上的移动对象聚类方法考虑到移动对象运动的路网限制，我们首先引入了基于编码的路网距离计算方法来加快移动对象之间路网距离的计算，并且基于结点的编码提出了聚类的磁盘存储结构。最后针对路网上的移动对象聚类，提

19、出了两个新的聚类算法，基于边的聚类（一种层次聚类方法）和基于结点的聚类（一种划分和层次混合聚类方法）。这两种新的算法开发了网络的特征来缩减搜索空间，避免一些不必要的距离计算（如运动在不相邻路段上的对象的路网距离）。具体来说，我们通过使用移动对象所包含的边和结点的信息来改进聚类结果的精度，提高聚类算法的效率。通过聚类结果所包含的边和结点的信息来预测聚类的分裂和合并。3.1 基于编码的路网距离计算加速技术和磁盘存储结构采用网络距离作为路网上移动对象聚类的相似性标准后，需要大量的网络上任意两点最短路径距离的计算，它也成为路网上移动对象聚类的核心组件。常见的最短路径计算采用Dijkstra算法，其最差

20、情况下的复杂度为O(|E| log |E|)，其中E为路网上结点的个数。虽然目前有很多最短路径算法的改进，但其计算复杂度仍很高。因此，为了加快聚类的速度，我们将尝试避开最短路径计算，而引入基于编码的路网距离计算方法来加快移动对象之间路网距离的计算，即使用一种新的编码技术对每个结点进行编码，将不同结点编码的海明距离与结点之间的最短路径距离相关联，则计算任意两个结点的网络距离就可以转换为直接计算结点编码的海明距离。这种方法将大大加快网络上任意两点间的网络距离的计算，从根本上解决路网上对象聚类代价高的问题。对路网上的结点进行编码的具体方法和过程如下：1） 将道路网络转换为相关的平面图，即将路网图各条

21、边离散化（由单位长度组成），通过插入虚结点，使得路网图由单位长度（权值）的边构成。2） 找出所有边的交替切割，根据切割对结点编码。其中交替切割定义为一系列的边e1,e2,e3,ek其中ei,ei+1属于同一个面F，而ei+1是面F与ei相反的边。若切割的边从图G中删除，则图G被分成两个不相邻的部分G/L0和G/L1。分别对其中一部分的所有结点编码追加一位置0，另一部分追加一位置1。3） 计算两个结点的编码的海明距离，即为两结点最短路径距离的两倍。两个点a0a1a2am-1和b0b1b2bm-1(ai,bi0,1)的海明距离定义为ak<>bk的个数k。计算海明编码的过程本质上是计算两

22、个结点分别在切割两边的切割（最短路径包括的边）的数目，即为最短路径的长度。切割需要满足以下条件：切割一条边上点之间的最短路径距离不经过切割所在的边，切割两边的点之间的最短路径距离经过且只经过一条切割所在的边。具体的例子如图所示，其中左图显示了一个路网和其相应的平面图以及边de的交替切割，右图显示了结点的编码情况。结点a和f编码的海明距离为10，因此其a和f 的最短路径距离为5。这种方法实际上将海明编码的特征与路网的特征结合起来，通过计算海明编码的距离来计算路网节点之间的距离。它在进行结点编码的过程中，将路网中的各个路段进行了分割，把各个路段完整地分割成几个小路段单元。然而，在真实的路网中，各个

23、路段的长度参差不一，很难找到一个合适的单元度量值来确切地分割他们。因为如果这个值太小，而海明编码的长度将会很长，将大大地降低处理查询的效率；如果度量值很大，有些路段可能会小于这个度量值，因此可能导致偏差。我们通过实验来得到了路段划分的尺度，使得能够很好的在查询效率和误差之间进行权衡。由于真实的道路网络非常复杂，而且路网中有大量的移动对象运动，为了支持高效的聚类算法，我们需要设计基于磁盘的存储结构和索引结构。路网上的移动对象聚类算法可能需要快速的查找对象所在的边、聚类所在的边以及任意结点或边的相邻结点或者边。因此我们设计的存储结构需要考虑到路网结点的存储（包括结点的编码，相邻结点链表）、移动对象

24、自身的存储（移动对象的位置、速度等信息）和聚类特征的存储（所包含的对象个数、位置概要、速度概要、聚类中心、所在的结点边等），其中路网结点是静态的，不随时间变化，而移动对象和聚类特征都是动态的，随着时间连续的变化。另外存储结构必须把他们之间的对应关系很好地表示出来，即移动对象和路网边的关系，聚类和路网边的关系以及移动对象和聚类的关系等。因此设计一个基于磁盘的存储结构将面临如下挑战：1）如何高效的存储这些信息，并能够表示出他们之间的关系，如何在移动对象和聚类特征中加入边和结点的信息；2）如何反映出移动对象和聚类特征随时间变化的动态性，即如何加入时态信息；3）是否考虑欧氏距离和路网距离的相关性，是否

25、需要基于空间位置来存储对象和网络结点我们设计了聚类R树（CR-tree）的磁盘存储结构，CR-tree由三层构成，能够高效的存储路网、移动对象和聚类特征。另外采用一个主内存哈希表来存储聚类和移动对象之间的映射关系。CR-tree的结构如图所示，包括三层结构。1） 上层R树索引道路网络。内部结点为(MBR, Childptr)，其中MBR为最小限定矩阵，Childptr为指向孩子结点的指针。叶结点的每个入口为(nodei, nodej, codei, codej, MOListptr)，其中包含路网的每条边所在的结点、相关的结点编码和指向当前时间运动在该边上的移动对象队列链表头指针2） 中间层为

26、移动对象队列链表结构。以队列链表组织当前时刻移动对象具体信息的存储，将位于同一个边上的移动对象形成一个优先队列链表，并按照对象的位置顺序排列。列表中的每项存储一个移动对象的详细信息 (oid, nodei, nodej, cid, pos, v, t)，其中oid为对象的标识符，nodei和nodej为对象所在的路段边，cid为对象所属的聚类，pos为对象所在的边的位置，v为对象的速度，t为当前时间3） 下层为一个倒置的聚类特征树，每个叶结点为(CF, MOListptr)，包括每个聚类特征以及指向其所包含的移动对象列表的头指针。由于我们聚类的目标是对交通道路网络上的交通拥堵情况进行实时检测和

27、预测，聚类当前时刻路网上的移动对象，并预测聚类将来的变化，因此只需存储和索引移动对象当前的运动信息和聚类当前的特征信息。我们假设移动对象在路网上每个边的运动为时间的线性函数，因此每个移动对象在一个边上的位置信息只需记录下进入该路段边的时间和速度。在这条边上任意位置的信息可以通过线性函数计算出来。当移动对象离开这条边进入下一条边时，只需将其从当前列表的末尾删除，并插入到新的边所指的移动对象列表头。3.2 基于边的路网移动对象聚类算法存在的聚类方法由于难以挖掘出对象的其它可用信息，仅仅通过对象自身的空间相似性如距离来进行粗糙的分组，需要反复扫描所有的对象信息，其代价很高。而对于路网的情况，我们可以

28、开发出网络的特征来缩减搜索空间，避免一些不必要的距离计算（如运动在不相邻路段上的对象的路网距离）。通过使用移动对象表示中包含的边和结点的信息来改进聚类的精度和效率，我们提出了两种新的聚类方法，基于边的聚类和基于结点的聚类。基于边的移动对象聚类分为两步，过滤阶段和求精阶段。即先根据路网的边将移动对象进行分组，得到初步的聚类，再对其进行求精，即分裂和合并找到准确的聚类。它实际上是一种层次聚类方法，具体算法如下：1） 过滤阶段（Filter Phase）：根据移动对象所在的边将其分组，即位于同一个边上的移动对象指定到同一个聚类中。则初始聚类的个数为路网上边的个数。2） 求精阶段（Refinement

29、 Phase）：循环的进行下面的步骤：根据距离阀值，先对长的边上的聚类进行分裂，再对相邻边上聚类进行合并。通过移动对象相似度来分裂聚类：若某个聚类中最临近对象的最大网络距离超过一个距离阀值§1，将此聚类进行分裂。通过聚类间相似度来合并聚类：两个相邻聚类间最小网络距离（两个聚类中网络距离最近的移动对象的相似度）小于某个阀值§2，则将这两个聚类进行合并。E_CMON () / Initiate the priority queue P and Q P = new priority queue; Q = new priority queue; for each network e

30、dge (nx, ny) with moving objects on it if the MOList is not NULL /Initiate the cluster feature CjCj.edge = (nx,ny)/Scan the MOList to compute the max similarity of adjacent objects and add the objects and max similarity into the cluster feature maxdist = 0 for each object oi of the MOList insert oi

31、into cluster Cj update the maxdist Cj.maxdist = maxdist enqueue (P,Cj) while the queue P is not NULL dequeue (p, Cj)splitted (Cj) = falseif Cj.maxdist > § Spitcluster (Cj, C1, C2) enqueue (P, C1) enqueue (P, C2) splitted (Cj) = true if Not splitted (Cj)for each adjacent cluster Ci to Cj if D

32、n(Ci,Cj) <§ Mergecluster (Ci, Cj, C) Enqueue (P, C)3.3 基于结点的路网移动对象聚类算法基于结点的移动对象聚类分为三步，预处理阶段、过滤阶段和求精阶段。即先在长路网的边上插入一些虚拟结点，并将结点作为虚拟的对象，再根据结点将移动对象进行分组，得到初步的聚类，最后对其进行求精，即交换聚类中心和合并聚类找到准确的聚类。它实际上是一种划分和层次混合聚类方法，具体算法如下：1） 预处理结点（Preprocess Phase）：路网的长的边上（以路网边的平均长度作为阀值）增加虚结点，将所有结点作为“虚对象”2） 过滤阶段（Filter

33、Phase）：选择每个结点作为聚类的中心点。对于每个对象，根据路网距离找到其最近的结点（所在边上的两个结点之一），并将此对象归类到结点对应的初始聚类中。3） 求精阶段（Refinement Phase）：循环的进行下面的步骤：将结点最相邻的对象点替换聚类中心，重新指定每个对象到相应的聚类中（查找离对象最近的聚类中心对象）。根据聚类间相似度来合并相邻的聚类。即两个相邻聚类间最小网络距离小于某个阀值§2，则将这两个聚类进行合并。N_CMON ()Input: / Initiate the priority queue P and Q P = new priority queue; Q =

34、 new priority queue; Add virtual node to the long edgefor each network node ni C(i).medoid = nifor each network edge (nx, ny) with moving objects on it if the MOList is not NULL /Scan the MOList to add the objects into nearest cluster for each object oi of the MOList if Dn(oi, nx) < Dn(oi, ny) in

35、sert oi into cluster C(x) else insert oi into cluster C(y) for each network node ni find the nearest object oi C(i).medoid = oiinsert <Ci, oi> into queue Pfor each object oj in the ci for each adjacent node nx to ni if Dn(oj, nx) < Dn(oj, oi) delete oj from the cluster C(i)insert oj into th

36、e cluster C(j) while the queue P is not NULL dequeue (p, Cj)for each adjacent cluster Ci to Cj if Dn(Ci,Cj) <§ Mergecluster (Ci, Cj, C) Enqueue (P, C)3.4 聚类的分裂和合并为了避免随着时间聚类恶化的问题，即同一聚类中的对象由于不同的速度和位置，经过一段时间后分散，而违背了微聚类对象相邻的条件。需要在适当的时间分裂和重组织以保证在任何时间聚类中的对象相邻且聚类在地理上紧凑的。因此其中的主要问题变为如何找到路网上聚类需要分裂的时间，

37、如何进行重组织使得聚类更有效。我们将结合使用聚类限定矩阵和聚类半径的方法标识聚类的分裂和合并。即在道路网络的某条路段上的微小聚类使用一维的限定矩阵的方法表示其分裂和合并，而在道路交叉口即路网的结点附近使用聚类半径的方法来标识聚类的分裂和合并。具体来说，聚类分裂发生在下列两种情况下：1） 聚类中的大多数对象移动到结点附近时2） 聚类的边界超过一定的阀值，如聚类的长度间隔超过原来的一个比例（如15）当聚类发生在道路网络上，我们可以通过一维的限定矩阵即一维的长度间隔来绑定每个聚类，聚类的大小随着时间增长，当长度间隔的大小超过阀值L时分裂MMC。阀值L的大小取决于当前时刻长度间隔的大小，且不同的聚类其

38、阀值不同。聚类长度间隔的边界点随时间而改变，它是一个分段线性函数，分段点为边界点改变的时刻。因此标识分裂时刻等同于标识出边界点变化的时刻（简化为最右边的对象变化）即关键事件（critical incident）。其中有三种方法：顺序查找：扫描每个移动对象，找当前最右边的对象将要生效的最近的将来时间。其时间复杂度为O(n2)。动态全排序：动态维护对象的位置顺序，将关键事件存储在一个优先队列Pq中。部分排序：只需部分排序对象，足以标识最右边的对象即可。使用运动堆结构（kinetic heap），可以节省在不可能引起的边界点改变的内部对象间不必要的事件发生。其时间复杂度为O(nlogn)。 当聚类中

39、的大多数对象移动到结点附近时，使用平均半径函数R(t)自动检测聚类分裂时间，决定何时分裂，而不必在大量分裂合并事件时维护聚类的限定框。R(t)可以从聚类特征中计算出来。当聚类的平均半径R(t)超过阀值Ps（聚类不再紧凑）时进行分裂。在最大间隔时间内R(t)为递增线性函数或者凹的抛物线，它和Ps有三种情况。始终在Ps之下无分裂，超过Ps在当前时间就分裂，在ts时刻超过Ps分裂。聚类的分裂过程如下：分裂时选择边界点中与聚类速度差较大的边界点和与聚类速度方向不同的边界点加入到最近的聚类中或者作为一个新的单独的聚类。而聚类的合并发生在相邻的聚类运动到一起时，即当Dn (CMON1, CMON2) &l

40、t; D，将两个聚类进行合并，即对其聚类特征进行相应的操作。4 路网上的移动对象聚类应用1. 新型查询的支持2. 交通阻塞的预测可以对城市道路上车辆的运动模式的变化进行交通控制和预测等。预测移动对象未来的聚集信息。这个应用具有重要的意义，它可以方便地预测路网在未来时刻各个路段的通畅程度，可以运用它来对移动对象进行实时的导航。3. 城市交通巡逻车的分布根据某一类型的车辆（如出租车）在城市道路网络上运动情况的聚类分析，合理安排和调度出租车在城市路网上的运动分布。5 性能分析和实验5.1 实验环境和参数Brinkoff数据集，使用三个地图的数据作为三个数据集D1, D2, D35.2 实验内容1.

41、聚类初始化：与空间网络上的聚类方法比较（改进后的划分方法和层次方法）Yiu & Mamoulis SIGMOD'041）聚类的有效性：聚类的评价标准（平方误差函数）2）聚类的效率：聚类构造的CPU时间3）聚类的扩展性：数据集大小增加时的聚类效率2. 移动对象聚类的维护代价（聚类的分裂和合并）：与MMC比较 Li & Han KDD04聚类的有效性：不同时刻对聚类评价聚类的更新效率：聚类分裂和合并的IO代价聚类数目的影响、更新周期的影响、更新时间的影响3. 密度查询的影响5.3 实验总结6 相关工作对路网上的移动对象运动模式进行分析和挖掘的研究是数据挖掘和移动数据库两个邻

42、域的交叉研究方向。在数据挖掘领域，有大量的工作集中在对静态数据集的聚类方法上1-8，可以将这些方法分类为划分方法1-2，层次方法3-6，基于密度的方法7，基于网格的方法和基于模型的方法。一个好的聚类方法的一般准则是：在同一个类中的对象之间尽可能的“接近”或相关，而不同类中的对象之间尽可能的“远离”或不同。算法的选择取决于数据的类型、聚类的目的和应用。划分的方法构造不同的分割，然后对其进行评估和求精。即随机的划分对象为K组，循环地交换不同组间的对象，直到聚类的质量不再改进。有两种比较流行的启发式方法：k-平均算法(k-means)1为每个聚簇用该簇中对象的平均值表示而k-中心点算法(k-medo

43、ids)2中每个聚簇用接近聚类中心的一个对象表示。这些启发式的聚类方法对中小规模的数据库中发现球状簇很适用，其算法简单，适合于压缩紧凑，聚类之间较分离的情况。然而这些算法的效率低、代价高，对于噪音或outlier点敏感；必须事先给定k的值，给定不同的k值就会呈现不同聚类效果；仅能创建类似于球形的聚类，难以处理复杂形状的聚类；难以处理大规模的数据集；不用应用于带categorical属性的数据，扩展性不好，对于高维不能适用。层次的方法是对给定的数据对象的集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的。层次的方法缺陷在于，一旦一个步骤（合并或分裂）完成，他就不能被撤消

44、，不能更正错误的决定，每个层次的不同划分对于聚类的结果影响很大。有两种方法可以改进层次聚类的结果：在每层划分中，仔细分析对象间的“连接”，例如CURE和Chameleon中的做法。综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果，如BIRCH中的方法。BIRCH3是一个综合的层次聚类方法，它利用层次方法的平衡迭代归约和聚类递增的聚类静态对象，并引入聚类特征的概念和一个高度平衡的聚类特征树 (CF树)。而CURE4利用代表点聚类。它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。Chameleon6是利用动态模型的层次聚类算法。在

45、它的聚类过程中，如果两个簇间的互连性和近似度与簇内部对象间的互连性和近似度高度相关，则合并这两个簇。基于动态模型的合并过程有利于自然的和同构的聚类的发现，而且只要定义了相似度函数就可以应用于所有类型的数据。Chameleon与CUER和DBSCAN相比，在发现高质量的任意形状的聚类方面有更强的能力。基于密度的方法其主要思想是只要邻近区域的密度（对象或数据点的数目）超过某个阀值，就唏嘘聚类。具体来说这种方法是基于连接性和密度函数，发现空间中的密集区，即对象彼此靠近的区域，如果点之间的距离小于一个阀值，则将这些点放到同一个聚类中，即从低密集区中分离出来。这个方法可以用来过滤孤立点数据，发现任意形状

46、的簇。DBSCAN7是一个有代表性的基于密度的方法，它根据一个密度阀值来控制聚类的增长。算法通过检查数据库中每个点的邻域来寻找聚类。如果一个点p的邻域包含多于Minpts个点，则创建一个以p作为核心对象的新簇。然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有任何新的点可以被添加到任何簇时，该过程结束。该方法的问题在于对于参数值（，Minpts）的选择非常敏感，设置的细微不同将可能导致差别很大的聚类结果，运行时间为O（nlogn）。OPTICS是另一个基于密度的方法，它为自动的和交互的聚类分析计算一个聚类顺序。基于网格的方法把对象空间量化

47、为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构上进行。其优点是处理的速度很快，处理时间独立数据对象的数目，只和量化空间中每一维的单元数目有关。STING是基于网格方法的一个典型的例子。CLIQUE和WaveCluster既是基于网格的又是基于密度的。基于模型的方法为每个聚类假设一个模型，数据对给定模型的最佳拟和。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。分为统计方法（COBWEB）和神经网络方法（SOMs）。移动对象数据库的研究起源于时空数据库领域，正式开始于九十年代后期，最早由美国Illinois大学芝加哥分校的Ouri Wolfson及其研

48、究小组提出。他们通过引入了动态属性的概念提出了一个新的移动对象时空（MOST）模型来对移动对象进行建模，并提出了将来逻辑语言（FTL）。随后，基于线性约束模型、时空网格存储模型、基于抽象数据类型的移动对象数据库模型5开始出现。最近两年，MOD的研究热点开始转向受限网络的移动对象数据库，相关的数据模型、索引和查询等工作开始出现。移动对象的索引方面的研究工作主要集中在两个方面：1）对过去位置或历史轨迹的索引；2）对现在和可预期将来的索引。最近的研究工作开始关注于受限网络上的索引研究，多数工作都是通过路网或者空间填充曲线的映射方法对所索引的数据进行降维，将路网索引中的三维问题转变成两个低维的子问题。

49、路网上的查询处理也是这几年研究的重点，它与空间网络数据库的查询处理相关，即使用路网距离来代替二维空间的欧几何距离。路网上的典型查询包括区域查询（查询某个时间段处于某个地理区域的移动对象）、KNN查询（查询离某一点最近的K个移动对象）以及连接查询（查询满足条件的移动对象组合）等，大量的研究工作集中在如何高效的处理这些查询问题。作为时空数据的聚类分析的一部分，移动对象数据的聚类分析成为最近关注的研究热点之一。由于移动对象位置连续变化的固有特性使得难以抓住数据的趋势和规律，这给移动对象的聚类分析带来了很大的困难。2004年Yifan Li和Jiawei Han等人在9中考虑到移动对象本身的这种特征，

50、将微聚类方法运用到移动对象上，利用移动对象的运动趋势，引入了移动微聚类(moving mirco-cluster)的概念，动态维护聚类的限定框，以保证微聚类在地理上足够的紧凑。所谓的移动微聚类就是用来表示一组在现在和将来的位置都很接近的移动对象的集合。它综合考虑移动对象的位置和速度这两个运动参数。通过一个矩形框来限定每个移动微聚类。随着移动对象的运动状态的不断变化，这个矩形框也会随之变化，为了保证移动微聚类的有效性，在某个适当的时刻，移动微聚类的矩形框将会发生分裂，矩形框内的移动对象将被重组。这可以通过事先定义一个阈值来实现。这成为了移动对象聚类的第一个工作。另外文献10也提出一个直方图技术，

51、使用“距离”函数结合位置和速度不同，配置了“K-center”聚类算法来构造直方图。但直方图的维护代价高，大量更新时直方图需重建。最新的有关移动对象聚类的工作定义了移动聚类的概念11，提出了从一个时空数据集（历史轨迹记录）中自动发现移动聚类的三种方法。与聚类运动轨迹和挖掘运动模式相比，移动聚类的标识可能随着其位置和内容的改变而保持不变。然而目前的这些移动对象聚类的工作都是基于欧氏距离的，不能运用到受限网络的移动对象聚类上。文献8考虑到空间网络对于移动对象聚类算法的影响，引入了网络距离(network distance)的概念，采用路网距离代替传统的欧几距离(Euclidean distance

52、)表示移动对象之间的相似性。另外，还提出了几种传统的聚类算法(划分聚类、层次聚类和基于密度聚类算法)的变形，用于处理真实路网上的移动对象。这些算法通过挖掘路网本身的一些特性，避免计算任意两个移动对象的距离，提高了计算移动对象相似性的效率。这些已有的空间网络上的对象聚类方法虽然基于路网距离，但针对空间网络上的静态对象聚类，不是动态的，不能对路网上的移动对象进行聚类。目前还没有专门针对路网上移动对象的进行聚类分析的研究工作。关于最短路径计算问题，CCAM13是一个基于磁盘的存储结构，其目的是最小化最短路径计算过程的IO访问。网络结点基于其连接性和访问的频率，跟它们的邻接链表一起分组到磁盘页上。相邻

53、的结点存储在相同的磁盘页上。另外文献14中提出了层次的索引来对磁盘页分组并存储预计算的最短路径距离总结信息。最近针对路网上的查询处理，文献15提出了一个体系结构集成网络连接和欧氏位置信息，配置了一个基于磁盘的网络表示方法，保留的连接和位置信息，并通过路网距离对最邻近查询、范围查询和最近对查询进行了重新的评估。另外文献16提出了一种新的基于路网编码的方法来对路网上的节点进行编码，用于高效地回答空间或时空查询。通过证明可以得到，两个节点的海明编码距离对应于这两个节点实际的物理空间距离，因而，我们通过分析计算海明码的距离就可以很快地找出路网中两个节点之间的最短路径。另外，编码方法还可以有效地获取路网

54、中关于空间或时空查询的许多重要的特征。7 总结本文主要针对受限于道路网络上的移动对象聚类方法进行研究，根据网络距离重新定义路网上移动对象的聚类问题。引入结点编码的方法来加速网络距离的计算，开发路网上对象运动的特点，提出新的基于路网距离的移动对象聚类方法，基于边的聚类方法和基于结点的聚类方法，并提出了相应的聚类合并和分裂的算法。一系列的实验表明新的聚类方法具有高的准确度和效率。通过对路网上的移动对象进行聚类分析可以对城市道路网络上车辆的拥堵情况进行有效的检测和预测。参考文献1. L. Kaufman and P. J. Rousseeuw. Finding Groups in Data: An Introduction to Cluster Analysis. John Wile