受限網(wǎng)絡(luò)的移動對象聚類研究

1、受限網(wǎng)絡(luò)的移動對象聚類研究1 引言隨著3G時代的到來，眾多具有定位功能的無線手持設(shè)備的大量普及，定位技術(shù)和無線傳感器技術(shù)進(jìn)一步的發(fā)展，都使得移動對象的大量位置信息可以實時的獲得，除了對這些大量的實時數(shù)據(jù)進(jìn)行高效的管理和查詢，還需要對這些數(shù)據(jù)進(jìn)行有效的分析，挖掘移動對象運動的知識，找出運動過程中有趣的模式變化，以此來進(jìn)行系統(tǒng)負(fù)載均衡，進(jìn)行有目標(biāo)有針對性的銷售等。例如可以發(fā)掘出手機(jī)移動用戶的運動模式，找出某段時間哪些服務(wù)區(qū)內(nèi)的用戶密集，以合理的分配手機(jī)頻率帶寬。另外還可以對城市道路上車輛的運動模式的變化進(jìn)行交通控制和預(yù)測等。聚類分析是就對數(shù)據(jù)對象進(jìn)行分組，使得同一個組中對象之間具有較高的相似度，而

2、不同組中的對象差別較大。聚類分析構(gòu)成了基本的數(shù)據(jù)分析功能，已經(jīng)廣泛的應(yīng)用在許多應(yīng)用中，包括圖像處理、數(shù)據(jù)壓縮、模式標(biāo)識以及市場研究。通過聚類可以識別出密集和稀疏的區(qū)域，因而發(fā)現(xiàn)全局的分布模式，以及數(shù)據(jù)屬性之間有趣的相互關(guān)系。對移動對象進(jìn)行聚類分析可以應(yīng)用于天氣預(yù)報（颼風(fēng)聚類）、城市交通阻塞的預(yù)測、動物遷徙分析、移動計算、異常分析等。目前的大部分聚類方法主要針對靜態(tài)的數(shù)據(jù)對象，而移動對象的聚類工作還很少。Yifan Li等人在10中考慮到移動對象本身的特征，利用移動對象的運動趨勢，引入了一種移動微聚類（moving mirco-cluster）的概念第一次提出了移動對象聚類的問題。所謂移動微聚類

3、就是用來表示一組在現(xiàn)在和將來的位置都很接近的移動對象的集合。它綜合考慮了移動對象的位置和速度這兩個運動參數(shù)。通過一個矩形框來限定每個移動微聚類。隨著移動對象的運動狀態(tài)的不斷變化，這個矩形框也會隨之變化，為了保證移動微聚類的有效性，在某個適當(dāng)?shù)臅r刻，移動微聚類的矩形框?qū)l(fā)生分裂，矩形框內(nèi)的移動對象將被重組。然而此方法聚類限定框經(jīng)常超出，維護(hù)代價很高。維護(hù)聚類分裂和合并的數(shù)量多，并且占了算法的整個運行時間。最近，Kalnis等人12也定義了運動聚類的概念，提出了從一個時空數(shù)據(jù)集（歷史軌跡記錄）中自動發(fā)現(xiàn)運動聚類的三種方法。與聚類軌跡和挖掘運動模式相比，運動聚類的標(biāo)識可能隨著其位置和內(nèi)容的改變而保

4、持不變。然而這些工作都是對空間中的移動對象進(jìn)行處理，主要考慮的是移動對象本身的一些運動特征，并沒有考慮到移動對象所在的空間，例如道路網(wǎng)絡(luò)的拓?fù)鋵τ谝苿訉ο缶垲惖挠绊懙?。在許多真實的應(yīng)用中，移動對象的運動大多都是受限于一定的空間網(wǎng)絡(luò)中的（典型的為道路網(wǎng)絡(luò)上的車輛）。因此通過網(wǎng)絡(luò)距離而不是歐氏距離來定義對象之間的相似度/不相似度更具有實際意義。然而目前的移動對象聚類的工作都是基于歐氏距離的，不能運用到受限網(wǎng)絡(luò)的移動對象聚類上。而已有的空間網(wǎng)絡(luò)上的對象聚類方法雖然基于路網(wǎng)距離，但不是動態(tài)的，不能對路網(wǎng)上的移動對象進(jìn)行聚類。本文將針對受限于道路網(wǎng)絡(luò)上的移動對象聚類方法進(jìn)行研究，根據(jù)網(wǎng)絡(luò)距離重新定義受限

5、網(wǎng)絡(luò)的移動對象聚類問題，提出新的基于路網(wǎng)距離的移動對象聚類方法。由于移動對象自身的動態(tài)性（位置隨著時間連續(xù)的發(fā)生改變）和在路網(wǎng)上運動的復(fù)雜性以及路網(wǎng)上對象相似度衡量標(biāo)準(zhǔn)的改變（由歐氏距離變?yōu)槁肪W(wǎng)距離），這些都增加了路網(wǎng)上移動對象聚類的復(fù)雜性，傳統(tǒng)的聚類方法很難適用于路網(wǎng)上移動對象的聚類分析。我們將首先根據(jù)網(wǎng)絡(luò)距離相似度標(biāo)準(zhǔn)重新定義受限于道路網(wǎng)絡(luò)上的移動對象聚類問題，然后從加快道路網(wǎng)上對象的最短路徑距離計算入手，引入網(wǎng)絡(luò)結(jié)點編碼的方法來加速網(wǎng)絡(luò)距離的計算?；诖颂岢鲆惶谆诖疟P的存儲和索引方法以支持對大量的對象進(jìn)行高效的聚類分析。最后我們將利用路網(wǎng)上對象運動的特點，提出新的基于路網(wǎng)距離的移動對象

6、聚類方法，對城市道路網(wǎng)絡(luò)上車輛的擁堵情況進(jìn)行有效的檢測和預(yù)測，并通過聚類算法來支持路網(wǎng)上新型的查詢處理。存在的聚類方法由于難以挖掘出對象的其它可用信息，僅僅通過對象自身的空間相似性如距離來進(jìn)行粗糙分組，需要反復(fù)的掃描所有的對象信息，其代價很高。我們觀察到：1）由于對象運動受限于網(wǎng)絡(luò)，對象的聚類可以利用路網(wǎng)的信息來發(fā)掘，聚類與路網(wǎng)的結(jié)點和邊相關(guān)。例如路網(wǎng)上在同一個邊或相鄰邊上的車輛很可能在一個聚類中。而位于不相鄰的路段上的車輛不太可能聚類在一起；交通擁堵通常發(fā)生在城市道路路口，即路網(wǎng)結(jié)點附近的車輛很可能聚類在一起。2）可以將移動對象通過路網(wǎng)來表示，即所在的路段和相對于路段起點的距離位置，這樣移動

7、對象的運動信息本身已經(jīng)包含了路網(wǎng)邊和結(jié)點等信息，我們可以在對他們聚類時利用這些信息來提供聚類的精度和效率。3）路網(wǎng)中移動對象具有一定的規(guī)律性，且有一定的運動趨勢，例如：某個移動對象在某個路段的運動狀態(tài)和運動特征基本上相似：以一個相對穩(wěn)定的速度運動朝一個特定的方向運動。我們可以利用其來較為精確的預(yù)測對象未來的運動并進(jìn)一步預(yù)測聚類的變化，如分裂和合并。因此對于路網(wǎng)的情況，我們可以開發(fā)出網(wǎng)絡(luò)的特征來縮減搜索空間，避免一些不必要的距離計算（如運動在不相鄰路段上的對象的路網(wǎng)距離）。通過使用移動對象表示中包含的邊和結(jié)點的信息來改進(jìn)聚類的精度和效率，我們提出兩種新的聚類方法，基于邊的聚類（一種層次聚類方法）

8、和基于結(jié)點的聚類（一種劃分和層次混合聚類方法）。這兩種新的算法開發(fā)了網(wǎng)絡(luò)的特征來縮減搜索空間，避免一些不必要的距離計算（如運動在不相鄰路段上的對象的路網(wǎng)距離）。具體來說，我們通過使用移動對象所包含的邊和結(jié)點的信息來改進(jìn)聚類結(jié)果的精度，提高聚類算法的效率。為了保證聚類結(jié)果的有效性，聚類將隨著其中的移動對象一起運動，在適當(dāng)?shù)臅r刻也會發(fā)生分裂和合并。我們將通過聚類結(jié)果所包含的邊和結(jié)點的信息以及移動對象運動的規(guī)律性和運動趨勢來預(yù)測聚類的分裂和合并，盡可能的降低移動對象聚類的總代價。本文的貢獻(xiàn)：1根據(jù)路網(wǎng)上移動對象的網(wǎng)絡(luò)距離定義了路網(wǎng)上移動對象的聚類問題2引入網(wǎng)絡(luò)結(jié)點編碼技術(shù)來加速網(wǎng)絡(luò)距離計算，并提出了

9、一套基于磁盤的存儲方案。3利用交通路網(wǎng)的特征，提出了兩種新的聚類方法，分別利用結(jié)點和邊信息來減少搜索空間，避免一些不必要的距離計算。4對提出的技術(shù)進(jìn)行了一系列的實驗評估，結(jié)果驗證了我們提出的聚類方法在對路網(wǎng)上的移動對象進(jìn)行聚類時具有高的準(zhǔn)確度和效率。2 相關(guān)背景和基本模型2.1 問題和挑戰(zhàn)當(dāng)聚類的目標(biāo)從靜態(tài)的空間對象改變?yōu)檫\動在道路網(wǎng)絡(luò)中的移動對象時，聚類的復(fù)雜性將大大增加，現(xiàn)有的聚類方法也不再適用。在這種環(huán)境下聚類面臨的問題和復(fù)雜性主要包括下面三個方面：1） 路網(wǎng)上移動對象的固有特征路網(wǎng)上的移動對象數(shù)量巨大而且它們的位置會隨著時間發(fā)生連續(xù)的改變，使得聚類的結(jié)果也可能隨著時間、隨著移動對象的運

10、動而變化，即使對象很小的位置改變也可能導(dǎo)致完全不同的聚類結(jié)果。同時由于交通系統(tǒng)自身的動態(tài)性、隨機(jī)性和復(fù)雜性，對象在路網(wǎng)上的運動也異常復(fù)雜，使得很難抓住對象的趨勢。2） 路網(wǎng)上移動對象之間相似度的度量標(biāo)準(zhǔn)由歐氏距離變?yōu)槁肪W(wǎng)距離傳統(tǒng)方法上在計算移動對象之間的相似度時，所采用的方法是直接計算移動對象之間的歐氏距離（Euclidean distance），而在道路網(wǎng)絡(luò)的情況下，應(yīng)該考慮使用網(wǎng)絡(luò)距離（network distance）來計算移動對象之間的相似度。這又會增加聚類計算的復(fù)雜性。兩個任意對象的網(wǎng)絡(luò)距離需要代價很高的最短路徑算法，不能在常量時間內(nèi)計算出來，另外聚類不是針對道路網(wǎng)絡(luò)的結(jié)點，而是運動

11、在路網(wǎng)圖邊上的任意位置上的移動對象，因此結(jié)點間的最短路徑算法也要進(jìn)行一定的變化。目前的幾個聚類方法中的一些概念如聚類中心、總結(jié)概要等難以在路網(wǎng)情況下定義。具體來說，給定路網(wǎng)上的一組對象，由于不存在一個唯一的網(wǎng)絡(luò)點，離這組中所有點的平均距離最小，因此不能使用網(wǎng)絡(luò)距離來定義他們的聚類中心，而且即使有這樣的中心點，找到他們的代價也很高。3） 路網(wǎng)上移動對象聚類對相鄰的移動對象產(chǎn)生影響，相鄰聚類之間會產(chǎn)生影響路網(wǎng)上的移動對象聚類不僅會隨其中對象的運動而變化，同時反過來聚類也會影響周圍移動對象自身的運動，如使其減少速度，使已有的聚類變得更大。另外相鄰的聚類之間也很可能逐漸結(jié)合形成更大的聚類。因此移動對象

12、運動的路網(wǎng)限制要求我們必須重新定義其聚類問題。下面我們將定義路網(wǎng)上移動對象聚類的基本模型，具體包括道路網(wǎng)絡(luò)模型、移動對象路網(wǎng)表示模型、基于網(wǎng)絡(luò)距離相似性的定義、移動對象間相似度和聚類間相似度的定義、聚類特征的定義、聚類中心的定義、聚類評價函數(shù)的定義等。另外，聚類隨著其中移動對象的運動而移動，同時為了保證聚類的有效性，必須在某一時刻進(jìn)行聚類分裂和合并，這都會導(dǎo)致聚類特征的更新，因此我們對聚類特征的這些更新操作也進(jìn)行了定義。2.2 問題定義和基本模型道路網(wǎng)絡(luò)模型：定義1：一個道路網(wǎng)絡(luò)可以表示為一個無向帶權(quán)圖G=(V, E, W)，其中V時頂點的集合（如道路的結(jié)點），E是邊的集合，W為正的實數(shù)集合（

13、W：E->IR+），表示邊對應(yīng)的權(quán)值移動對象路網(wǎng)表示模型：定義2：道路網(wǎng)絡(luò)上的移動對象在某個時刻的位置可以表示為（Oid, ni, nj, pos, v, t），其中Oid為對象ID，ni和nj是對象所在的路網(wǎng)邊的兩個結(jié)點，pos0, W(e)是對象離結(jié)點ni的距離。v是對象的速度。t為對象更新時間。移動對象的位置建模為時間的線性函數(shù)，假設(shè)在路網(wǎng)上的每一個邊上移動對象勻速運動。 基于路網(wǎng)距離相似性的定義：定義3：假設(shè)移動對象p和q在某一時刻位于同一條網(wǎng)絡(luò)邊上，其位置分別為：（na, nb, posp）和（na, nb, posq）則同一邊上的移動對象間直接距離定義為：Dd(p, q) =

14、 |posp-posq| （其中對象p和q在同一條路網(wǎng)邊（na, nb）上）；對象和結(jié)點間的直接距離定義為：Dd(p, na) = posp和Dd(p, nb) = W(na, nb) -posp 定義4：給定網(wǎng)絡(luò)結(jié)點ni和nj，則結(jié)點間的網(wǎng)絡(luò)距離Dn(ni,nj)定義為從結(jié)點ni到結(jié)點nj的最短路徑距離。假設(shè)移動對象p和q在某一時刻位于不同網(wǎng)絡(luò)邊上，其位置分別為：（na, nb, posp）和（nc, nd, posq），則移動對象間的網(wǎng)絡(luò)距離定義為：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是與速度屬性相關(guān)的一個權(quán)值。由于速度決定了對象將來的位置，對聚類特征的更新具有很大的影響，因此對象之間的相似度除了考慮對象的位置之外，還考慮了對象的速度。為了提高對大量對象的聚類速度和聚類的可擴(kuò)展性，我們引入了文獻(xiàn)中定義的聚類特征的概念，并對其進(jìn)行了擴(kuò)展，加入了速度的匯總信息以及聚類所在的路網(wǎng)邊的信息。定義6：聚類特征定義為：CF = (N, CX, CV, E, t) 其中N是聚類中包含的對象個數(shù)，CX為聚類所包含的所有對象在t時刻的位置的和，CV為聚類所包含的所有對象在t時刻的速度的和，E是聚類所在的網(wǎng)絡(luò)邊的集合，t為聚類的更新

16、時間聚類特征是對給定子聚類的統(tǒng)計匯總。它記錄了計算聚類和有效利用存儲的關(guān)鍵度量，因為它匯總了關(guān)于子聚類的信息，而不是存儲所有的對象。聚類評價函數(shù)的定義（平均誤差準(zhǔn)則）：定義7：平均誤差總和：E(Ci,mi): i 1,k = i 1,k pci Dn(p, mi) 其中p為路網(wǎng)上的數(shù)據(jù)對象，mi是聚類Ci的平均值。平均誤差準(zhǔn)則試圖使生成的聚類結(jié)果盡可能的緊湊和獨立。2.2 進(jìn)一步的觀察移動對象的運動受限于道路網(wǎng)絡(luò)后，給其聚類方法帶來了巨大的問題和挑戰(zhàn)，然而另一個方面，道路網(wǎng)絡(luò)也給聚類帶來了更多的額外信息，可以幫助提高聚類的效率和精度。我們進(jìn)一步觀察到：1） 路網(wǎng)中移動對象具有一定的規(guī)律性，且有

17、一定的運動趨勢，例如：某個移動對象在某個路段的運動狀態(tài)基本上相似：以一個相對穩(wěn)定的速度運動朝一個特定的方向運動；某些移動對象在某條路段上的運動特征基本上相似等。我們可以利用其來較為精確的預(yù)測對象未來的運動并進(jìn)一步預(yù)測聚類的變化，如分裂和合并。2） 由于對象運動受限于網(wǎng)絡(luò)，對象的聚類可以利用路網(wǎng)的信息來發(fā)掘，聚類與路網(wǎng)的結(jié)點和邊相關(guān)。a) 路網(wǎng)上在同一個邊或相鄰邊上的車輛很可能在一個聚類中。而位于不相鄰的路段上的車輛不太可能聚類在一起。b) 交通擁堵通常發(fā)生在城市道路路口，因此路網(wǎng)結(jié)點附近的車輛很可能聚類在一起3） 可以將移動對象通過路網(wǎng)來表示，即所在的路段和相對于路段起點的距離位置，這樣移動對

18、象的運動信息本身已經(jīng)包含了路網(wǎng)邊和結(jié)點等信息，我們可以在對他們聚類時利用這些信息來提供聚類的精度和效率。4） 存在的聚類方法由于難以挖掘出對象的其他可用信息，因此僅僅通過對象自身的相似性如距離來進(jìn)行brute-force分組，需要反復(fù)的掃描所有的對象信息，其代價很高。而對于路網(wǎng)的情況，我們可以開發(fā)出網(wǎng)絡(luò)的特征來縮減搜索空間，避免一些不必要的距離計算（如運動在不相鄰路段上的對象的路網(wǎng)距離）。3 路網(wǎng)上的移動對象聚類方法考慮到移動對象運動的路網(wǎng)限制，我們首先引入了基于編碼的路網(wǎng)距離計算方法來加快移動對象之間路網(wǎng)距離的計算，并且基于結(jié)點的編碼提出了聚類的磁盤存儲結(jié)構(gòu)。最后針對路網(wǎng)上的移動對象聚類，提

19、出了兩個新的聚類算法，基于邊的聚類（一種層次聚類方法）和基于結(jié)點的聚類（一種劃分和層次混合聚類方法）。這兩種新的算法開發(fā)了網(wǎng)絡(luò)的特征來縮減搜索空間，避免一些不必要的距離計算（如運動在不相鄰路段上的對象的路網(wǎng)距離）。具體來說，我們通過使用移動對象所包含的邊和結(jié)點的信息來改進(jìn)聚類結(jié)果的精度，提高聚類算法的效率。通過聚類結(jié)果所包含的邊和結(jié)點的信息來預(yù)測聚類的分裂和合并。3.1 基于編碼的路網(wǎng)距離計算加速技術(shù)和磁盤存儲結(jié)構(gòu)采用網(wǎng)絡(luò)距離作為路網(wǎng)上移動對象聚類的相似性標(biāo)準(zhǔn)后，需要大量的網(wǎng)絡(luò)上任意兩點最短路徑距離的計算，它也成為路網(wǎng)上移動對象聚類的核心組件。常見的最短路徑計算采用Dijkstra算法，其最差

20、情況下的復(fù)雜度為O(|E| log |E|)，其中E為路網(wǎng)上結(jié)點的個數(shù)。雖然目前有很多最短路徑算法的改進(jìn)，但其計算復(fù)雜度仍很高。因此，為了加快聚類的速度，我們將嘗試避開最短路徑計算，而引入基于編碼的路網(wǎng)距離計算方法來加快移動對象之間路網(wǎng)距離的計算，即使用一種新的編碼技術(shù)對每個結(jié)點進(jìn)行編碼，將不同結(jié)點編碼的海明距離與結(jié)點之間的最短路徑距離相關(guān)聯(lián)，則計算任意兩個結(jié)點的網(wǎng)絡(luò)距離就可以轉(zhuǎn)換為直接計算結(jié)點編碼的海明距離。這種方法將大大加快網(wǎng)絡(luò)上任意兩點間的網(wǎng)絡(luò)距離的計算，從根本上解決路網(wǎng)上對象聚類代價高的問題。對路網(wǎng)上的結(jié)點進(jìn)行編碼的具體方法和過程如下：1） 將道路網(wǎng)絡(luò)轉(zhuǎn)換為相關(guān)的平面圖，即將路網(wǎng)圖各條

21、邊離散化（由單位長度組成），通過插入虛結(jié)點，使得路網(wǎng)圖由單位長度（權(quán)值）的邊構(gòu)成。2） 找出所有邊的交替切割，根據(jù)切割對結(jié)點編碼。其中交替切割定義為一系列的邊e1,e2,e3,ek其中ei,ei+1屬于同一個面F，而ei+1是面F與ei相反的邊。若切割的邊從圖G中刪除，則圖G被分成兩個不相鄰的部分G/L0和G/L1。分別對其中一部分的所有結(jié)點編碼追加一位置0，另一部分追加一位置1。3） 計算兩個結(jié)點的編碼的海明距離，即為兩結(jié)點最短路徑距離的兩倍。兩個點a0a1a2am-1和b0b1b2bm-1(ai,bi0,1)的海明距離定義為ak<>bk的個數(shù)k。計算海明編碼的過程本質(zhì)上是計算兩

22、個結(jié)點分別在切割兩邊的切割（最短路徑包括的邊）的數(shù)目，即為最短路徑的長度。切割需要滿足以下條件：切割一條邊上點之間的最短路徑距離不經(jīng)過切割所在的邊，切割兩邊的點之間的最短路徑距離經(jīng)過且只經(jīng)過一條切割所在的邊。具體的例子如圖所示，其中左圖顯示了一個路網(wǎng)和其相應(yīng)的平面圖以及邊de的交替切割，右圖顯示了結(jié)點的編碼情況。結(jié)點a和f編碼的海明距離為10，因此其a和f 的最短路徑距離為5。這種方法實際上將海明編碼的特征與路網(wǎng)的特征結(jié)合起來，通過計算海明編碼的距離來計算路網(wǎng)節(jié)點之間的距離。它在進(jìn)行結(jié)點編碼的過程中，將路網(wǎng)中的各個路段進(jìn)行了分割，把各個路段完整地分割成幾個小路段單元。然而，在真實的路網(wǎng)中，各個

23、路段的長度參差不一，很難找到一個合適的單元度量值來確切地分割他們。因為如果這個值太小，而海明編碼的長度將會很長，將大大地降低處理查詢的效率；如果度量值很大，有些路段可能會小于這個度量值，因此可能導(dǎo)致偏差。我們通過實驗來得到了路段劃分的尺度，使得能夠很好的在查詢效率和誤差之間進(jìn)行權(quán)衡。由于真實的道路網(wǎng)絡(luò)非常復(fù)雜，而且路網(wǎng)中有大量的移動對象運動，為了支持高效的聚類算法，我們需要設(shè)計基于磁盤的存儲結(jié)構(gòu)和索引結(jié)構(gòu)。路網(wǎng)上的移動對象聚類算法可能需要快速的查找對象所在的邊、聚類所在的邊以及任意結(jié)點或邊的相鄰結(jié)點或者邊。因此我們設(shè)計的存儲結(jié)構(gòu)需要考慮到路網(wǎng)結(jié)點的存儲（包括結(jié)點的編碼，相鄰結(jié)點鏈表）、移動對象

24、自身的存儲（移動對象的位置、速度等信息）和聚類特征的存儲（所包含的對象個數(shù)、位置概要、速度概要、聚類中心、所在的結(jié)點邊等），其中路網(wǎng)結(jié)點是靜態(tài)的，不隨時間變化，而移動對象和聚類特征都是動態(tài)的，隨著時間連續(xù)的變化。另外存儲結(jié)構(gòu)必須把他們之間的對應(yīng)關(guān)系很好地表示出來，即移動對象和路網(wǎng)邊的關(guān)系，聚類和路網(wǎng)邊的關(guān)系以及移動對象和聚類的關(guān)系等。因此設(shè)計一個基于磁盤的存儲結(jié)構(gòu)將面臨如下挑戰(zhàn)：1）如何高效的存儲這些信息，并能夠表示出他們之間的關(guān)系，如何在移動對象和聚類特征中加入邊和結(jié)點的信息；2）如何反映出移動對象和聚類特征隨時間變化的動態(tài)性，即如何加入時態(tài)信息；3）是否考慮歐氏距離和路網(wǎng)距離的相關(guān)性，是否

25、需要基于空間位置來存儲對象和網(wǎng)絡(luò)結(jié)點我們設(shè)計了聚類R樹（CR-tree）的磁盤存儲結(jié)構(gòu)，CR-tree由三層構(gòu)成，能夠高效的存儲路網(wǎng)、移動對象和聚類特征。另外采用一個主內(nèi)存哈希表來存儲聚類和移動對象之間的映射關(guān)系。CR-tree的結(jié)構(gòu)如圖所示，包括三層結(jié)構(gòu)。1） 上層R樹索引道路網(wǎng)絡(luò)。內(nèi)部結(jié)點為(MBR, Childptr)，其中MBR為最小限定矩陣，Childptr為指向孩子結(jié)點的指針。葉結(jié)點的每個入口為(nodei, nodej, codei, codej, MOListptr)，其中包含路網(wǎng)的每條邊所在的結(jié)點、相關(guān)的結(jié)點編碼和指向當(dāng)前時間運動在該邊上的移動對象隊列鏈表頭指針2） 中間層為

26、移動對象隊列鏈表結(jié)構(gòu)。以隊列鏈表組織當(dāng)前時刻移動對象具體信息的存儲，將位于同一個邊上的移動對象形成一個優(yōu)先隊列鏈表，并按照對象的位置順序排列。列表中的每項存儲一個移動對象的詳細(xì)信息 (oid, nodei, nodej, cid, pos, v, t)，其中oid為對象的標(biāo)識符，nodei和nodej為對象所在的路段邊，cid為對象所屬的聚類，pos為對象所在的邊的位置，v為對象的速度，t為當(dāng)前時間3） 下層為一個倒置的聚類特征樹，每個葉結(jié)點為(CF, MOListptr)，包括每個聚類特征以及指向其所包含的移動對象列表的頭指針。由于我們聚類的目標(biāo)是對交通道路網(wǎng)絡(luò)上的交通擁堵情況進(jìn)行實時檢測和

27、預(yù)測，聚類當(dāng)前時刻路網(wǎng)上的移動對象，并預(yù)測聚類將來的變化，因此只需存儲和索引移動對象當(dāng)前的運動信息和聚類當(dāng)前的特征信息。我們假設(shè)移動對象在路網(wǎng)上每個邊的運動為時間的線性函數(shù)，因此每個移動對象在一個邊上的位置信息只需記錄下進(jìn)入該路段邊的時間和速度。在這條邊上任意位置的信息可以通過線性函數(shù)計算出來。當(dāng)移動對象離開這條邊進(jìn)入下一條邊時，只需將其從當(dāng)前列表的末尾刪除，并插入到新的邊所指的移動對象列表頭。3.2 基于邊的路網(wǎng)移動對象聚類算法存在的聚類方法由于難以挖掘出對象的其它可用信息，僅僅通過對象自身的空間相似性如距離來進(jìn)行粗糙的分組，需要反復(fù)掃描所有的對象信息，其代價很高。而對于路網(wǎng)的情況，我們可以

28、開發(fā)出網(wǎng)絡(luò)的特征來縮減搜索空間，避免一些不必要的距離計算（如運動在不相鄰路段上的對象的路網(wǎng)距離）。通過使用移動對象表示中包含的邊和結(jié)點的信息來改進(jìn)聚類的精度和效率，我們提出了兩種新的聚類方法，基于邊的聚類和基于結(jié)點的聚類?；谶叺囊苿訉ο缶垲惙譃閮刹?，過濾階段和求精階段。即先根據(jù)路網(wǎng)的邊將移動對象進(jìn)行分組，得到初步的聚類，再對其進(jìn)行求精，即分裂和合并找到準(zhǔn)確的聚類。它實際上是一種層次聚類方法，具體算法如下：1） 過濾階段（Filter Phase）：根據(jù)移動對象所在的邊將其分組，即位于同一個邊上的移動對象指定到同一個聚類中。則初始聚類的個數(shù)為路網(wǎng)上邊的個數(shù)。2） 求精階段（Refinement

29、 Phase）：循環(huán)的進(jìn)行下面的步驟：根據(jù)距離閥值，先對長的邊上的聚類進(jìn)行分裂，再對相鄰邊上聚類進(jìn)行合并。通過移動對象相似度來分裂聚類：若某個聚類中最臨近對象的最大網(wǎng)絡(luò)距離超過一個距離閥值§1，將此聚類進(jìn)行分裂。通過聚類間相似度來合并聚類：兩個相鄰聚類間最小網(wǎng)絡(luò)距離（兩個聚類中網(wǎng)絡(luò)距離最近的移動對象的相似度）小于某個閥值§2，則將這兩個聚類進(jìn)行合并。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 基于結(jié)點的路網(wǎng)移動對象聚類算法基于結(jié)點的移動對象聚類分為三步，預(yù)處理階段、過濾階段和求精階段。即先在長路網(wǎng)的邊上插入一些虛擬結(jié)點，并將結(jié)點作為虛擬的對象，再根據(jù)結(jié)點將移動對象進(jìn)行分組，得到初步的聚類，最后對其進(jìn)行求精，即交換聚類中心和合并聚類找到準(zhǔn)確的聚類。它實際上是一種劃分和層次混合聚類方法，具體算法如下：1） 預(yù)處理結(jié)點（Preprocess Phase）：路網(wǎng)的長的邊上（以路網(wǎng)邊的平均長度作為閥值）增加虛結(jié)點，將所有結(jié)點作為“虛對象”2） 過濾階段（Filter

33、Phase）：選擇每個結(jié)點作為聚類的中心點。對于每個對象，根據(jù)路網(wǎng)距離找到其最近的結(jié)點（所在邊上的兩個結(jié)點之一），并將此對象歸類到結(jié)點對應(yīng)的初始聚類中。3） 求精階段（Refinement Phase）：循環(huán)的進(jìn)行下面的步驟：將結(jié)點最相鄰的對象點替換聚類中心，重新指定每個對象到相應(yīng)的聚類中（查找離對象最近的聚類中心對象）。根據(jù)聚類間相似度來合并相鄰的聚類。即兩個相鄰聚類間最小網(wǎng)絡(luò)距離小于某個閥值§2，則將這兩個聚類進(jìn)行合并。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 聚類的分裂和合并為了避免隨著時間聚類惡化的問題，即同一聚類中的對象由于不同的速度和位置，經(jīng)過一段時間后分散，而違背了微聚類對象相鄰的條件。需要在適當(dāng)?shù)臅r間分裂和重組織以保證在任何時間聚類中的對象相鄰且聚類在地理上緊湊的。因此其中的主要問題變?yōu)槿绾握业铰肪W(wǎng)上聚類需要分裂的時間，

37、如何進(jìn)行重組織使得聚類更有效。我們將結(jié)合使用聚類限定矩陣和聚類半徑的方法標(biāo)識聚類的分裂和合并。即在道路網(wǎng)絡(luò)的某條路段上的微小聚類使用一維的限定矩陣的方法表示其分裂和合并，而在道路交叉口即路網(wǎng)的結(jié)點附近使用聚類半徑的方法來標(biāo)識聚類的分裂和合并。具體來說，聚類分裂發(fā)生在下列兩種情況下：1） 聚類中的大多數(shù)對象移動到結(jié)點附近時2） 聚類的邊界超過一定的閥值，如聚類的長度間隔超過原來的一個比例（如15）當(dāng)聚類發(fā)生在道路網(wǎng)絡(luò)上，我們可以通過一維的限定矩陣即一維的長度間隔來綁定每個聚類，聚類的大小隨著時間增長，當(dāng)長度間隔的大小超過閥值L時分裂MMC。閥值L的大小取決于當(dāng)前時刻長度間隔的大小，且不同的聚類其

38、閥值不同。聚類長度間隔的邊界點隨時間而改變，它是一個分段線性函數(shù)，分段點為邊界點改變的時刻。因此標(biāo)識分裂時刻等同于標(biāo)識出邊界點變化的時刻（簡化為最右邊的對象變化）即關(guān)鍵事件（critical incident）。其中有三種方法：順序查找：掃描每個移動對象，找當(dāng)前最右邊的對象將要生效的最近的將來時間。其時間復(fù)雜度為O(n2)。動態(tài)全排序：動態(tài)維護(hù)對象的位置順序，將關(guān)鍵事件存儲在一個優(yōu)先隊列Pq中。部分排序：只需部分排序?qū)ο?，足以?biāo)識最右邊的對象即可。使用運動堆結(jié)構(gòu)（kinetic heap），可以節(jié)省在不可能引起的邊界點改變的內(nèi)部對象間不必要的事件發(fā)生。其時間復(fù)雜度為O(nlogn)。 當(dāng)聚類中

39、的大多數(shù)對象移動到結(jié)點附近時，使用平均半徑函數(shù)R(t)自動檢測聚類分裂時間，決定何時分裂，而不必在大量分裂合并事件時維護(hù)聚類的限定框。R(t)可以從聚類特征中計算出來。當(dāng)聚類的平均半徑R(t)超過閥值Ps（聚類不再緊湊）時進(jìn)行分裂。在最大間隔時間內(nèi)R(t)為遞增線性函數(shù)或者凹的拋物線，它和Ps有三種情況。始終在Ps之下無分裂，超過Ps在當(dāng)前時間就分裂，在ts時刻超過Ps分裂。聚類的分裂過程如下：分裂時選擇邊界點中與聚類速度差較大的邊界點和與聚類速度方向不同的邊界點加入到最近的聚類中或者作為一個新的單獨的聚類。而聚類的合并發(fā)生在相鄰的聚類運動到一起時，即當(dāng)Dn (CMON1, CMON2) &l

40、t; D，將兩個聚類進(jìn)行合并，即對其聚類特征進(jìn)行相應(yīng)的操作。4 路網(wǎng)上的移動對象聚類應(yīng)用1. 新型查詢的支持2. 交通阻塞的預(yù)測可以對城市道路上車輛的運動模式的變化進(jìn)行交通控制和預(yù)測等。預(yù)測移動對象未來的聚集信息。這個應(yīng)用具有重要的意義，它可以方便地預(yù)測路網(wǎng)在未來時刻各個路段的通暢程度，可以運用它來對移動對象進(jìn)行實時的導(dǎo)航。3. 城市交通巡邏車的分布根據(jù)某一類型的車輛（如出租車）在城市道路網(wǎng)絡(luò)上運動情況的聚類分析，合理安排和調(diào)度出租車在城市路網(wǎng)上的運動分布。5 性能分析和實驗5.1 實驗環(huán)境和參數(shù)Brinkoff數(shù)據(jù)集，使用三個地圖的數(shù)據(jù)作為三個數(shù)據(jù)集D1, D2, D35.2 實驗內(nèi)容1.

41、聚類初始化：與空間網(wǎng)絡(luò)上的聚類方法比較（改進(jìn)后的劃分方法和層次方法）Yiu & Mamoulis SIGMOD'041）聚類的有效性：聚類的評價標(biāo)準(zhǔn)（平方誤差函數(shù)）2）聚類的效率：聚類構(gòu)造的CPU時間3）聚類的擴(kuò)展性：數(shù)據(jù)集大小增加時的聚類效率2. 移動對象聚類的維護(hù)代價（聚類的分裂和合并）：與MMC比較 Li & Han KDD04聚類的有效性：不同時刻對聚類評價聚類的更新效率：聚類分裂和合并的IO代價聚類數(shù)目的影響、更新周期的影響、更新時間的影響3. 密度查詢的影響5.3 實驗總結(jié)6 相關(guān)工作對路網(wǎng)上的移動對象運動模式進(jìn)行分析和挖掘的研究是數(shù)據(jù)挖掘和移動數(shù)據(jù)庫兩個鄰

42、域的交叉研究方向。在數(shù)據(jù)挖掘領(lǐng)域，有大量的工作集中在對靜態(tài)數(shù)據(jù)集的聚類方法上1-8，可以將這些方法分類為劃分方法1-2，層次方法3-6，基于密度的方法7，基于網(wǎng)格的方法和基于模型的方法。一個好的聚類方法的一般準(zhǔn)則是：在同一個類中的對象之間盡可能的“接近”或相關(guān)，而不同類中的對象之間盡可能的“遠(yuǎn)離”或不同。算法的選擇取決于數(shù)據(jù)的類型、聚類的目的和應(yīng)用。劃分的方法構(gòu)造不同的分割，然后對其進(jìn)行評估和求精。即隨機(jī)的劃分對象為K組，循環(huán)地交換不同組間的對象，直到聚類的質(zhì)量不再改進(jìn)。有兩種比較流行的啟發(fā)式方法：k-平均算法(k-means)1為每個聚簇用該簇中對象的平均值表示而k-中心點算法(k-medo

43、ids)2中每個聚簇用接近聚類中心的一個對象表示。這些啟發(fā)式的聚類方法對中小規(guī)模的數(shù)據(jù)庫中發(fā)現(xiàn)球狀簇很適用，其算法簡單，適合于壓縮緊湊，聚類之間較分離的情況。然而這些算法的效率低、代價高，對于噪音或outlier點敏感；必須事先給定k的值，給定不同的k值就會呈現(xiàn)不同聚類效果；僅能創(chuàng)建類似于球形的聚類，難以處理復(fù)雜形狀的聚類；難以處理大規(guī)模的數(shù)據(jù)集；不用應(yīng)用于帶categorical屬性的數(shù)據(jù)，擴(kuò)展性不好，對于高維不能適用。層次的方法是對給定的數(shù)據(jù)對象的集合進(jìn)行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以分為凝聚的和分裂的。層次的方法缺陷在于，一旦一個步驟（合并或分裂）完成，他就不能被撤消

44、，不能更正錯誤的決定，每個層次的不同劃分對于聚類的結(jié)果影響很大。有兩種方法可以改進(jìn)層次聚類的結(jié)果：在每層劃分中，仔細(xì)分析對象間的“連接”，例如CURE和Chameleon中的做法。綜合層次凝聚和迭代的重定位方法。首先用自底向上的層次算法，然后用迭代的重定位來改進(jìn)結(jié)果，如BIRCH中的方法。BIRCH3是一個綜合的層次聚類方法，它利用層次方法的平衡迭代歸約和聚類遞增的聚類靜態(tài)對象，并引入聚類特征的概念和一個高度平衡的聚類特征樹 (CF樹)。而CURE4利用代表點聚類。它不用單個質(zhì)心或?qū)ο髞泶硪粋€簇，而是選擇數(shù)據(jù)空間中固定數(shù)目的具有代表性的點。Chameleon6是利用動態(tài)模型的層次聚類算法。在

45、它的聚類過程中，如果兩個簇間的互連性和近似度與簇內(nèi)部對象間的互連性和近似度高度相關(guān)，則合并這兩個簇。基于動態(tài)模型的合并過程有利于自然的和同構(gòu)的聚類的發(fā)現(xiàn)，而且只要定義了相似度函數(shù)就可以應(yīng)用于所有類型的數(shù)據(jù)。Chameleon與CUER和DBSCAN相比，在發(fā)現(xiàn)高質(zhì)量的任意形狀的聚類方面有更強(qiáng)的能力。基于密度的方法其主要思想是只要鄰近區(qū)域的密度（對象或數(shù)據(jù)點的數(shù)目）超過某個閥值，就唏噓聚類。具體來說這種方法是基于連接性和密度函數(shù)，發(fā)現(xiàn)空間中的密集區(qū)，即對象彼此靠近的區(qū)域，如果點之間的距離小于一個閥值，則將這些點放到同一個聚類中，即從低密集區(qū)中分離出來。這個方法可以用來過濾孤立點數(shù)據(jù)，發(fā)現(xiàn)任意形狀

46、的簇。DBSCAN7是一個有代表性的基于密度的方法，它根據(jù)一個密度閥值來控制聚類的增長。算法通過檢查數(shù)據(jù)庫中每個點的鄰域來尋找聚類。如果一個點p的鄰域包含多于Minpts個點，則創(chuàng)建一個以p作為核心對象的新簇。然后，DBSCAN反復(fù)地尋找從這些核心對象直接密度可達(dá)的對象，這個過程可能涉及一些密度可達(dá)簇的合并。當(dāng)沒有任何新的點可以被添加到任何簇時，該過程結(jié)束。該方法的問題在于對于參數(shù)值（，Minpts）的選擇非常敏感，設(shè)置的細(xì)微不同將可能導(dǎo)致差別很大的聚類結(jié)果，運行時間為O（nlogn）。OPTICS是另一個基于密度的方法，它為自動的和交互的聚類分析計算一個聚類順序。基于網(wǎng)格的方法把對象空間量化

47、為有限數(shù)目的單元，形成了一個網(wǎng)格結(jié)構(gòu)。所有的聚類操作都在這個網(wǎng)格結(jié)構(gòu)上進(jìn)行。其優(yōu)點是處理的速度很快，處理時間獨立數(shù)據(jù)對象的數(shù)目，只和量化空間中每一維的單元數(shù)目有關(guān)。STING是基于網(wǎng)格方法的一個典型的例子。CLIQUE和WaveCluster既是基于網(wǎng)格的又是基于密度的。基于模型的方法為每個聚類假設(shè)一個模型，數(shù)據(jù)對給定模型的最佳擬和。一個基于模型的算法可能通過構(gòu)建反映數(shù)據(jù)點空間分布的密度函數(shù)來定位聚類。分為統(tǒng)計方法（COBWEB）和神經(jīng)網(wǎng)絡(luò)方法（SOMs）。移動對象數(shù)據(jù)庫的研究起源于時空數(shù)據(jù)庫領(lǐng)域，正式開始于九十年代后期，最早由美國Illinois大學(xué)芝加哥分校的Ouri Wolfson及其研

48、究小組提出。他們通過引入了動態(tài)屬性的概念提出了一個新的移動對象時空（MOST）模型來對移動對象進(jìn)行建模，并提出了將來邏輯語言（FTL）。隨后，基于線性約束模型、時空網(wǎng)格存儲模型、基于抽象數(shù)據(jù)類型的移動對象數(shù)據(jù)庫模型5開始出現(xiàn)。最近兩年，MOD的研究熱點開始轉(zhuǎn)向受限網(wǎng)絡(luò)的移動對象數(shù)據(jù)庫，相關(guān)的數(shù)據(jù)模型、索引和查詢等工作開始出現(xiàn)。移動對象的索引方面的研究工作主要集中在兩個方面：1）對過去位置或歷史軌跡的索引；2）對現(xiàn)在和可預(yù)期將來的索引。最近的研究工作開始關(guān)注于受限網(wǎng)絡(luò)上的索引研究，多數(shù)工作都是通過路網(wǎng)或者空間填充曲線的映射方法對所索引的數(shù)據(jù)進(jìn)行降維，將路網(wǎng)索引中的三維問題轉(zhuǎn)變成兩個低維的子問題。

49、路網(wǎng)上的查詢處理也是這幾年研究的重點，它與空間網(wǎng)絡(luò)數(shù)據(jù)庫的查詢處理相關(guān)，即使用路網(wǎng)距離來代替二維空間的歐幾何距離。路網(wǎng)上的典型查詢包括區(qū)域查詢（查詢某個時間段處于某個地理區(qū)域的移動對象）、KNN查詢（查詢離某一點最近的K個移動對象）以及連接查詢（查詢滿足條件的移動對象組合）等，大量的研究工作集中在如何高效的處理這些查詢問題。作為時空數(shù)據(jù)的聚類分析的一部分，移動對象數(shù)據(jù)的聚類分析成為最近關(guān)注的研究熱點之一。由于移動對象位置連續(xù)變化的固有特性使得難以抓住數(shù)據(jù)的趨勢和規(guī)律，這給移動對象的聚類分析帶來了很大的困難。2004年Yifan Li和Jiawei Han等人在9中考慮到移動對象本身的這種特征，

50、將微聚類方法運用到移動對象上，利用移動對象的運動趨勢，引入了移動微聚類(moving mirco-cluster)的概念，動態(tài)維護(hù)聚類的限定框，以保證微聚類在地理上足夠的緊湊。所謂的移動微聚類就是用來表示一組在現(xiàn)在和將來的位置都很接近的移動對象的集合。它綜合考慮移動對象的位置和速度這兩個運動參數(shù)。通過一個矩形框來限定每個移動微聚類。隨著移動對象的運動狀態(tài)的不斷變化，這個矩形框也會隨之變化，為了保證移動微聚類的有效性，在某個適當(dāng)?shù)臅r刻，移動微聚類的矩形框?qū)l(fā)生分裂，矩形框內(nèi)的移動對象將被重組。這可以通過事先定義一個閾值來實現(xiàn)。這成為了移動對象聚類的第一個工作。另外文獻(xiàn)10也提出一個直方圖技術(shù)，

51、使用“距離”函數(shù)結(jié)合位置和速度不同，配置了“K-center”聚類算法來構(gòu)造直方圖。但直方圖的維護(hù)代價高，大量更新時直方圖需重建。最新的有關(guān)移動對象聚類的工作定義了移動聚類的概念11，提出了從一個時空數(shù)據(jù)集（歷史軌跡記錄）中自動發(fā)現(xiàn)移動聚類的三種方法。與聚類運動軌跡和挖掘運動模式相比，移動聚類的標(biāo)識可能隨著其位置和內(nèi)容的改變而保持不變。然而目前的這些移動對象聚類的工作都是基于歐氏距離的，不能運用到受限網(wǎng)絡(luò)的移動對象聚類上。文獻(xiàn)8考慮到空間網(wǎng)絡(luò)對于移動對象聚類算法的影響，引入了網(wǎng)絡(luò)距離(network distance)的概念，采用路網(wǎng)距離代替?zhèn)鹘y(tǒng)的歐幾距離(Euclidean distance

52、)表示移動對象之間的相似性。另外，還提出了幾種傳統(tǒng)的聚類算法(劃分聚類、層次聚類和基于密度聚類算法)的變形，用于處理真實路網(wǎng)上的移動對象。這些算法通過挖掘路網(wǎng)本身的一些特性，避免計算任意兩個移動對象的距離，提高了計算移動對象相似性的效率。這些已有的空間網(wǎng)絡(luò)上的對象聚類方法雖然基于路網(wǎng)距離，但針對空間網(wǎng)絡(luò)上的靜態(tài)對象聚類，不是動態(tài)的，不能對路網(wǎng)上的移動對象進(jìn)行聚類。目前還沒有專門針對路網(wǎng)上移動對象的進(jìn)行聚類分析的研究工作。關(guān)于最短路徑計算問題，CCAM13是一個基于磁盤的存儲結(jié)構(gòu)，其目的是最小化最短路徑計算過程的IO訪問。網(wǎng)絡(luò)結(jié)點基于其連接性和訪問的頻率，跟它們的鄰接鏈表一起分組到磁盤頁上。相鄰

53、的結(jié)點存儲在相同的磁盤頁上。另外文獻(xiàn)14中提出了層次的索引來對磁盤頁分組并存儲預(yù)計算的最短路徑距離總結(jié)信息。最近針對路網(wǎng)上的查詢處理，文獻(xiàn)15提出了一個體系結(jié)構(gòu)集成網(wǎng)絡(luò)連接和歐氏位置信息，配置了一個基于磁盤的網(wǎng)絡(luò)表示方法，保留的連接和位置信息，并通過路網(wǎng)距離對最鄰近查詢、范圍查詢和最近對查詢進(jìn)行了重新的評估。另外文獻(xiàn)16提出了一種新的基于路網(wǎng)編碼的方法來對路網(wǎng)上的節(jié)點進(jìn)行編碼，用于高效地回答空間或時空查詢。通過證明可以得到，兩個節(jié)點的海明編碼距離對應(yīng)于這兩個節(jié)點實際的物理空間距離，因而，我們通過分析計算海明碼的距離就可以很快地找出路網(wǎng)中兩個節(jié)點之間的最短路徑。另外，編碼方法還可以有效地獲取路網(wǎng)

54、中關(guān)于空間或時空查詢的許多重要的特征。7 總結(jié)本文主要針對受限于道路網(wǎng)絡(luò)上的移動對象聚類方法進(jìn)行研究，根據(jù)網(wǎng)絡(luò)距離重新定義路網(wǎng)上移動對象的聚類問題。引入結(jié)點編碼的方法來加速網(wǎng)絡(luò)距離的計算，開發(fā)路網(wǎng)上對象運動的特點，提出新的基于路網(wǎng)距離的移動對象聚類方法，基于邊的聚類方法和基于結(jié)點的聚類方法，并提出了相應(yīng)的聚類合并和分裂的算法。一系列的實驗表明新的聚類方法具有高的準(zhǔn)確度和效率。通過對路網(wǎng)上的移動對象進(jìn)行聚類分析可以對城市道路網(wǎng)絡(luò)上車輛的擁堵情況進(jìn)行有效的檢測和預(yù)測。參考文獻(xiàn)1. L. Kaufman and P. J. Rousseeuw. Finding Groups in Data: An Introduction to Cluster Analysis. John Wile