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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、 |posp-posq| （其中對(duì)象p和q在同一條路網(wǎng)邊（na, nb）上）；對(duì)象和結(jié)點(diǎn)間的直接距離定義為：Dd(p, na) = posp和Dd(p, nb) = W(na, nb) -posp 定義4：給定網(wǎng)絡(luò)結(jié)點(diǎn)ni和nj，則結(jié)點(diǎn)間的網(wǎng)絡(luò)距離Dn(ni,nj)定義為從結(jié)點(diǎn)ni到結(jié)點(diǎn)nj的最短路徑距離。假設(shè)移動(dòng)對(duì)象p和q在某一時(shí)刻位于不同網(wǎng)絡(luò)邊上，其位置分別為：（na, nb, posp）和（nc, nd, posq），則移動(dòng)對(duì)象間的網(wǎng)絡(luò)距離定義為：Dn(p,q) = min x(a,b), y(c,d) (Dd(p,nx)+Dn(nx,ny)+Dd(ny,q) 定義5：移動(dòng)對(duì)象相似度M(

15、p,q) = Dn2(p,q) + a(Vp-Vq)2 其中a是與速度屬性相關(guān)的一個(gè)權(quán)值。由于速度決定了對(duì)象將來的位置，對(duì)聚類特征的更新具有很大的影響，因此對(duì)象之間的相似度除了考慮對(duì)象的位置之外，還考慮了對(duì)象的速度。為了提高對(duì)大量對(duì)象的聚類速度和聚類的可擴(kuò)展性，我們引入了文獻(xiàn)中定義的聚類特征的概念，并對(duì)其進(jìn)行了擴(kuò)展，加入了速度的匯總信息以及聚類所在的路網(wǎng)邊的信息。定義6：聚類特征定義為：CF = (N, CX, CV, E, t) 其中N是聚類中包含的對(duì)象個(gè)數(shù)，CX為聚類所包含的所有對(duì)象在t時(shí)刻的位置的和，CV為聚類所包含的所有對(duì)象在t時(shí)刻的速度的和，E是聚類所在的網(wǎng)絡(luò)邊的集合，t為聚類的更新

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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