畢業(yè)設(shè)計（論文）基于空間聚類的臺風(fēng)軌跡提取

1、中南大學(xué)本科生畢業(yè)論文（設(shè)計）題 目 基于空間聚類的臺風(fēng)軌跡提取 學(xué)生姓名 指導(dǎo)教師 學(xué) 院 信息物理工程學(xué)院 專業(yè)班級 測繪06級03班 摘 要空間聚類是空間數(shù)據(jù)挖掘與空間分析的重要手段之一，常用于揭示空間數(shù)據(jù)分布規(guī)律以及發(fā)現(xiàn)空間數(shù)據(jù)異?！，F(xiàn)有的空間聚類方法多是針對空間點目標設(shè)計的，而實際應(yīng)用中積累了大量的軌跡數(shù)據(jù)如臺風(fēng)軌跡、gps導(dǎo)航數(shù)據(jù)、動物遷徙軌跡，對軌跡數(shù)據(jù)進行空間聚類分析有助于發(fā)現(xiàn)一些潛在的空間模式，具有重要的應(yīng)用價值。本文針對臺風(fēng)軌跡數(shù)據(jù)，探究了一種基于分割-聚群思想的軌跡數(shù)據(jù)空間聚類方法。首先系統(tǒng)回顧了空間聚類以及軌跡聚類的相關(guān)研究工作；進而重點介紹了基于分割-聚群思想的空間軌

2、跡聚類方法-traclus；最后，采用臺風(fēng)軌跡數(shù)據(jù)驗證了traclus算法在實際中的應(yīng)用效果，并對其應(yīng)用條件進行了分析，展望了空間軌跡聚類進一步研究的若干問題。關(guān)鍵詞：空間數(shù)據(jù)挖掘，空間聚類，臺風(fēng)軌跡，traclus算法abstractspatial clustering has played an important role in spatial data mining and spatial analysis. it can be used to discover the spatial association rules and spatial outliers in spatial

3、datasets. existing spatial clustering methods are mainly designed for spatial point objects. recent improvements in satellites and tracking facilities have made it possible to collect a large amount of trajectory data of moving objects. examples include vehicle position data, hurricane track data, a

4、nd animal movement data. there is increasing interest to perform data analysis over these trajectory data. discovering objects that have moved in a similar way is a meaningful data analysis task. thus, an efficient spatial clustering algorithm for trajectory data should be developed. in this paper,

5、we test a new partition-and-group based method for clustering trajectories in the application of hurricane track data. the performances of the traclus algorithm are fully performed. some issues can be further improved are also summarized.keywords: spatial data mining, spatial clustering, hurricane t

6、rack data, traclus algorithm目錄摘 要iabstractii目錄iii第一章 前言11.1研究背景與研究意義11.2本文研究內(nèi)容21.3本文組織結(jié)構(gòu)3第二章 相關(guān)研究回顧42.1 空間點數(shù)據(jù)聚類方法42.2 空間軌跡聚類方法5第三章 臺風(fēng)軌跡空間聚類算法73.1 算法概述73.1.1 問題描述73.1.2 traclus算法83.2 臺風(fēng)軌跡分割93.2.1 特征點提取93.2.2 構(gòu)造特征線段123.3 特征線段聚類133.3.1 基于密度的特征線段空間聚類133.3.2 簇的代表軌跡18第四章 實驗分析224.1 實驗設(shè)計224.2 臺風(fēng)軌跡提取結(jié)果224.3

7、結(jié)果分析24第五章 總結(jié)25參考文獻26致謝28iii中南大學(xué)本科生畢業(yè)論文 第1章 前言-第一章 前言1.1研究背景與研究意義隨著科技的發(fā)展和社會的進步，人們在工作生活當中需要掌握和運用的各類數(shù)據(jù)越來越多。為了在不增加數(shù)據(jù)量的情況下獲得更多有用信息，就要想辦法從各類數(shù)據(jù)中充分挖掘隱含的、潛在的信息?；谶@種想法，數(shù)據(jù)挖掘技術(shù)應(yīng)運而生。數(shù)據(jù)挖掘(data mining)，就是從大量數(shù)據(jù)中獲取有效的、新穎的、潛在有用的、最終可理解的模式的非平凡過程1。空間信息技術(shù)尤其是對地觀測技術(shù)的進步使得人們能更多的獲得并使用空間數(shù)據(jù)。將數(shù)據(jù)挖掘應(yīng)用于空間數(shù)據(jù)庫，以便從中發(fā)現(xiàn)空間知識的理論和技術(shù)，產(chǎn)生了一個新

8、的研究領(lǐng)域：空間數(shù)據(jù)挖掘與知識發(fā)現(xiàn)。空間數(shù)據(jù)挖掘是指從空間數(shù)據(jù)庫中抽取沒有清楚表現(xiàn)出來的隱含的知識和空間關(guān)系，并發(fā)現(xiàn)其中有用的特征和模式的理論、方法和技術(shù)2-8?？臻g聚類是空間數(shù)據(jù)挖掘技術(shù)的一個重要組成部分，其目的是將空間數(shù)據(jù)庫中的空間目標按照相似性分成一系列具有一定意義的簇，使得每個簇內(nèi)目標相似，而簇間目標不同，主要用于對大量空間數(shù)據(jù)進行深入分析，顯示空間數(shù)據(jù)分布規(guī)律，發(fā)現(xiàn)空間數(shù)據(jù)中的噪聲數(shù)據(jù)。目前空間聚類技術(shù)已廣泛用于多種應(yīng)用，包括市場研究，模式識別，數(shù)據(jù)分析和圖像處理等18-22?？臻g聚類技術(shù)雖然來源于傳統(tǒng)的聚類分析技術(shù)，然而由于空間聚類的研究對象空間數(shù)據(jù)的獨特性，傳統(tǒng)的聚類分析方法雖可

9、以用于空間聚類分析，但存在明顯的局限性。雜志中已經(jīng)報道了大量的空間聚類算法，代表算法包括k-均值，birch，dbscan，optics和sting。但以前的研究主要是針對點數(shù)據(jù)的聚類。最近衛(wèi)星定位技術(shù)和跟蹤監(jiān)測設(shè)施的發(fā)展，使我們能夠收集大量的移動物體的軌跡數(shù)據(jù)。包括車輛的位置數(shù)據(jù)，颶風(fēng)跟蹤數(shù)據(jù)，和動物的遷徙數(shù)據(jù)。對這些軌跡數(shù)據(jù)進行數(shù)據(jù)分析的需求持續(xù)增長。一種具有代表性的數(shù)據(jù)分析工作是尋找具有相似移動方式的對象。這樣，對于軌跡的一種有效聚類算法對這樣的數(shù)據(jù)分析工作是必須的?，F(xiàn)今存在的用于進行軌跡聚類的方法可分為整體軌跡聚類和局部軌跡聚類。整體軌跡聚類又分為基于概率和基于密度的聚類。局部軌跡聚類

10、的代表算法是分割-分組體系。然而整體軌跡聚類不能發(fā)現(xiàn)整體軌跡不同而部分相似的軌跡的相似部分（如例1）。例子1 圖1-1中的五個軌跡有共同子軌跡，由矩形框內(nèi)的粗箭頭標示。然而，如果對這些軌跡進行整體聚類，由于它們完全朝不同方向移動我們就不能發(fā)現(xiàn)共同行為；這樣就丟失了有用的信息。 圖1-1：公共子軌跡的例子解決方案是將軌跡分割成一系列線段，然后將相似線段分組。這一體系稱為分割-分組體系。該體系的主要優(yōu)點是能從軌跡數(shù)據(jù)庫中發(fā)現(xiàn)共同子軌跡。這就是為什么將軌跡分割成一系列線段的原因4-5。提取公共子軌跡非常有用，尤其在分析特殊區(qū)域，想要在那些區(qū)域中顯示公共行為時。在真實應(yīng)用中有很多例子，如：颶風(fēng)的登陸預(yù)

11、測。颶風(fēng)不僅影響當?shù)氐奶鞖庥袝r還會造成嚴重的生命財產(chǎn)損失，所以研究颶風(fēng)在氣候變化背景下的行為和變化有著重要的意義。氣象學(xué)家在努力提高預(yù)測颶風(fēng)登陸的時間和地點的能力。精確的登陸位置的預(yù)測更具重要性，因為它對減少颶風(fēng)損失是至關(guān)重要的。氣象學(xué)家會對颶風(fēng)靠近海岸線的共同行為感興趣，因為發(fā)現(xiàn)共同子軌跡有助于提高颶風(fēng)登陸預(yù)測精度。1.2本文研究內(nèi)容本文主要研究建立在分割-分組體系基礎(chǔ)上的用于在臺風(fēng)軌跡集中提取臺風(fēng)公共子軌跡的新的軌跡聚類算法：traclus，然后通過編程實現(xiàn)該過程，再對實驗結(jié)果進行比較以驗證其可行性并分析其優(yōu)缺點。該聚類算法包含分割和分組兩個階段。第一階段，用最小描述長度（mdl）準則實現(xiàn)

12、軌跡分割。第二階段則是一基于密度的線段聚類算法。在分割階段，每個軌跡被優(yōu)化劃分為一組線段。這些線段提供給下一個階段。在分組階段，相似的線段組成到一個簇里。線段簇往往是任意形狀的，軌跡數(shù)據(jù)庫也包含大量噪音。基于密度的聚類方法非常適合于軌跡聚類，因為它們能發(fā)現(xiàn)任意形狀的簇并且能剔除噪音。1.3本文組織結(jié)構(gòu)第1章 前言。闡述了本文的研究背景與研究意義，介紹了本文研究內(nèi)容，并對本文的組織結(jié)構(gòu)進行概述。第2章 空間聚類研究回顧。主要介紹了空間點數(shù)據(jù)聚類方法和空間軌跡數(shù)據(jù)聚類方法。第3章 軌跡聚類算法。提出第一階段的軌跡分割算法，第二階段的線段聚類算法。第4章 實驗分析。分析實驗結(jié)果并進行評價。第5章 總

13、結(jié)?？偨Y(jié)了本文的主要工作，并指出了進一步的研究方向。28中南大學(xué)本科生畢業(yè)論文 第2章 空間聚類研究回顧-第二章 相關(guān)研究回顧聚類是把大量的物理或抽象對象按照相似性分成不同類別的過程。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一簇中的對象彼此相似，與其它簇中的對象則不同23?？臻g聚類是聚類分析研究的重要組成部分，但又不同于傳統(tǒng)的聚類分析?；凇霸浇较嗨啤钡牡乩韺W(xué)指導(dǎo)思想，空間聚類將數(shù)據(jù)屬性劃分為空間屬性和非空間屬性兩部分，只有空間上鄰近的實體聚在一起才有意義，而空間上鄰近實體間的相似性又是通過非空間屬性來度量的。此外空間聚類的研究目標也從點目標擴展到了線目標和面目標。同時傳統(tǒng)聚類對數(shù)

14、據(jù)的各屬性等同看待，也不考慮實體的形狀，因此傳統(tǒng)的聚類方法雖然可以用于空間聚類分析，卻有一定的局限性9-16。2.1 空間點數(shù)據(jù)聚類方法大量空間聚類方法在文獻內(nèi)被報道。很難提供清晰的對簇的分類方法，因為這些類別可能重疊，一個方法可能有幾個類別的特征。在一般情況下，主要空間聚類算法分為四類：劃分的方法，層次的方法，基于密度方法，基于格網(wǎng)方法9： 劃分的方法：給定包含n個對象的數(shù)據(jù)庫或數(shù)據(jù)元組，用一分區(qū)方法構(gòu)造k(，讓。并返回第2步，否則停止。算法traclus是基于密度的局部軌跡聚類方法，在該方法中，簇是被低密度區(qū)域分離的高密度區(qū)域，詳細方法會在第三章提到。中南大學(xué)本科生畢業(yè)論文 第3章 軌跡聚

15、類算法-第三章 臺風(fēng)軌跡空間聚類算法 3.1 算法概述3.1.1 問題描述 想要在分割-分組體系的基礎(chǔ)上創(chuàng)建高效聚類算法traclus。先給定一系列軌跡，算法traclus生成一系列簇每個簇對應(yīng)一代表軌跡，其中軌跡，簇，代表軌跡定義如下。軌跡是一連串多維點。它表示為。在此，是一d維點。一個軌跡的長度不同于其他軌跡。軌跡稱為的子軌跡。簇是一系列軌跡分割。軌跡分割是線段，其中和是從相同軌跡中所選點。屬于相同簇的線段參照距離量測彼此臨近。注意，軌跡可以屬于多個簇，因為軌跡被分割成多個線段，然后對這些線段進行聚類操作。代表軌跡是和一般軌跡一樣的一列點。它是代表簇中軌跡分割主要行為的假想軌跡。注意代表軌

16、跡指示共同子軌跡。下圖顯示分割分組體系中軌跡聚類的概略過程。 圖3-1 分割分組體系軌跡聚類3.1.2 traclus算法 下圖顯示軌跡聚類算法traclus的提要。共有兩個階段，做子工作（第二、四、六行）時執(zhí)行三個算法。下文中會分別解釋這些算法。 算法1：traclus算法（軌跡聚類）- traclus算法（軌跡聚類）-輸入：軌跡集輸出：（1）簇集 （2）代表軌跡集算法： /*分割階段*/01.對每個軌跡做圖五；02.執(zhí)行近似軌跡分割，應(yīng)用結(jié)果得到線段集；03.積聚線段集到d集； /*分割階段*/04.對d進行線段聚類，得到簇集；05.對每個簇做圖十五；06.執(zhí)行生成代表軌跡操作，得到代表軌

17、跡；-用在線段聚類中的距離函數(shù)由三部分組成：垂直距離，平行距離，角度距離。這些部分適合于模式識別領(lǐng)域的相似度量。在圖3-2中直接說明。將三部分定義為定義13。 圖3-2、線段間距離函數(shù)的三部分定義1.和之間的垂直距離定義如下 （1）定義2.和之間的平行距離定義如下 （2）是到和距離中較小值，是到和距離中較小值。定義3.和之間的角度距離定義如下 （3）另外， （4）其中，（5）定義兩線段間距離如下：，其中權(quán)值、在本文中取1。3.2 臺風(fēng)軌跡分割3.2.1 特征點提取軌跡行為劇烈變化位置上的點就是特征點。軌跡在每個特征點處分割，每個分割由兩相鄰特征點間線段表示。這樣，軌跡就被分割為一系列線段，稱線

18、段為軌跡分割。下圖顯示軌跡和它的軌跡分割。 圖3-3 軌跡及其軌跡分割理想的軌跡分割應(yīng)包含兩個可取的性質(zhì)：準確性和簡明性。準確性指軌跡和它的軌跡分割集間的差別應(yīng)盡可能的小。簡明性指軌跡分割的數(shù)目應(yīng)盡可能的小。這兩個性質(zhì)相互矛盾，因此需要在兩者間找到一個理想平衡點?？梢圆捎脧V泛應(yīng)用于信息理論的最小描述長度（mdl）準則來發(fā)現(xiàn)準確性和簡明性間的理想平衡點。mdl包含兩部分：l(h)和l(d|h)。其中，h指假設(shè)，d指數(shù)據(jù)。l(h)是假設(shè)的描述長度；l(d|h)是數(shù)據(jù)在假設(shè)的幫助下編碼的描述長度。對解釋d的最佳假設(shè)h是使l(h)和l(d|h)之和最小時的值。在軌跡分割難題中，假設(shè)與特定軌跡分割集相對

19、應(yīng)。想找到理想的軌跡分割，就是找最佳分割，也就是用mdl準則找最佳假設(shè)。下圖顯示了l(h)和l(d|h)的構(gòu)想。 圖3-4 l(h)和l(d|h)假定軌跡和特征點集。然后，用公式6規(guī)劃l(h)，表示線段的長度。所以，l(h)表示所有軌跡分割長度之和。 (6) (7)另一方面，用公式7規(guī)劃l(d|h)。l(d|h)表示軌跡和它的軌跡分割間差異之和。對每個軌跡分割，將軌跡分割和屬于分割的線段 間差異加起來。用垂直距離和角度距離之和衡量差異。可以不考慮平行距離，因為軌跡包圍了它的軌跡分割。長度和距離是真值。在實踐中，將真值x編碼，假定精度為，使得編碼數(shù)滿足|x-|；08. 將前一點添加到特征點集；0

20、9. 開始索引=當前索引-1，長度=1； 10. 否則11. 長度=長度+112. 將結(jié)束點添加到特征點集-近似算法的時間復(fù)雜度為，n為軌跡長度。3.2.2 構(gòu)造特征線段經(jīng)過上一步驟的操作，每個軌跡對應(yīng)一個特征點集。特征點集中從始點到終點，每兩個相鄰特征點可以構(gòu)成一小線段，即特征線段。有時候特征點的提取也會不理想，如下圖舉例。假設(shè)使mdl花費最小的理想分割是。該算法不能發(fā)現(xiàn)準確方案，因為他在p4處停止掃描，在此大于。當然，該算法的精確性已經(jīng)很高了。 圖3-5 特征點提取3.3 特征線段聚類3.3.1 基于密度的特征線段空間聚類3.3.1.1 距離函數(shù)概述距離函數(shù)是三種距離的加權(quán)和。首先，垂直距

21、離主要衡量從不同軌跡提取的線段間的位置差異。其次，平行距離主要衡量從相同軌跡提取的線段間的位置差異，一個軌跡中兩臨近線段間的平行距離總是0。最后，角度距離衡量線段間方向差異。距離函數(shù)的對稱性對于避免聚類結(jié)果的模棱兩可很重要。如果距離函數(shù)是不對稱的，不同聚類結(jié)果可以通過過程順序獲得。 3.3.1.2 基于密度聚類的概念 以下定義是基于密度聚類所需的概念。d表示所有線段集。改變本來為dbscan算法提出的點的定義為線段的。定義4. 屬于d的線段的鄰域定義為。定義5. 如果，那么屬于d的線段稱為核心線段。定義6. 如果并且 ，從線段到線段是直接密度可達的。定義7. 如果有一屬于d的線段鏈使得從是直接

22、密度可達的，那么從線段到線段是密度可達的。定義8. 如果有一線段使得線段和線段對是密度可達的，那么對是密度連接的。定義9. 非空子集是密度連接集，如果c滿足以下兩個條件：（1） 對于任意屬于c的、，對是密度連接的；（2） 對于任意屬于d的、，如果屬于c，對是密度可達的，那么屬于c。 在下圖描繪這些定義。密度可達性是直接密度可達性的轉(zhuǎn)化終止，其關(guān)系是不對稱的。只有核心線段是互相密度可達的。然而，密度連接性卻是對稱關(guān)系。讓minlns為3。粗線段表示核心線段。鄰域由不規(guī)則橢圓表示。、和是核心線段；或?qū)κ侵苯用芏瓤蛇_的；對是密度可達的；、和都是密度連接的。 圖3-6 密度可達與密度連接圖3.3.1.

23、3 注意事項 因為線段有方向和長度，它們表現(xiàn)一些與基于密度聚類相關(guān)的有用特征。這里提及兩個注意事項。1.線段的鄰域的形狀不是圓或球，它取決于數(shù)據(jù)，一般為橢圓或橢球。主要受核心線段和鄰近線段的方向和長度影響。2.短線段能很大地降低聚類質(zhì)量。線段的長度表示它的方向強度；也就是，如果線段短，它的方向強度就低。意思是如果其中一個線段很短，那么不管真實角度如何，角度距離都很小。在下圖比較兩組線段，只有的長度不同。（a）中通過對是密度可達的，（b）中則不是密度可達的。因為與相隔很遠，（a）的結(jié)果是直接對立的。這樣短線段可能導(dǎo)致聚類超出。 圖3-7 短線段在聚類中的影響 這一問題的簡單解決方案是通過調(diào)整分割

24、標準使聚類分割更長。這樣，為了精確度而抑制分割。再具體點，為阻止分割，在圖5第6行中對加一個小的常量。實驗表明將軌跡分割長度提高2030%通常可以提高聚類質(zhì)量。3.3.1.4 特征線段空間聚類算法現(xiàn)在描述對線段的基于密度的聚類算法。給定一線段集d,用算法產(chǎn)生簇集o。它需要兩個算子和minlns，并將簇定義為密度連接集。算法traclus有很多特征與算法dbscan相同。與算法dbscan不同的是，不是所有密度連接集都能成為簇。需要考慮從中提取線段的軌跡的數(shù)目。這一數(shù)目典型的小于線段的數(shù)目。這里，檢查定義于定義10的軌跡基數(shù)。定義10.簇的參與軌跡集由定義。表示提取的軌跡。這樣稱為簇的軌跡基數(shù)。

25、下圖描述了線段聚類的算法。開始假定所有的線段都是未分類的。隨著算法的進展，它們被分類為簇或噪音。算法由三步組成。第一步（1-12行），算法計算每個未分類線段l的鄰域。如果l被判定為核心線段（7-10行），算法執(zhí)行第二步去擴展簇（9行）。簇目前只包含。第二步（17-28行），算法計算核心線段的密度連接集。擴展簇步驟計算直接密度可達線段（19-21），并將它們添加到臨時簇（22-24行）。如果新添加線段是未分類的，它就會為了進一步擴展而被添加到列，因為它可能是核心線段（25-26行）；否則它不會被添加到，因為已經(jīng)知道它不是核心線段。第三步（13-16），算法檢查每個簇的軌跡基數(shù)。如果它的軌跡基數(shù)低

26、于閥值，算法就會剔除相應(yīng)的簇。 算法3： 線段聚類算法- 線段聚類算法-輸入：（1）線段集， （2）兩個算子和minlns輸出：簇集算法：01. 將簇的id賦值為0；02. 將d內(nèi)所有線段標為未分類；03. 對每個屬于d的l,做04. 如果l是未分類的05. 計算；06. 如果07. 分配簇的id給； 08. 將插入列；09. 擴展簇（，簇id，）；10. 將簇的id加為1；11. 其它12. 將l標為噪音；13. 將分配給簇；14. 對每個，做15. 如果16. 從簇集o中移除c； 17. 擴展簇（，簇id，）18. 當時19. 讓m為中的第一個線段；20. 計算 ；21. 如果22. 對每

27、個23. 如果x是未分類的或是噪音24. 將簇id分配給x；25. 如果x是未分類的26. 將x插入列；27. 從列中移除m；28. -如果空間索引被應(yīng)用，那么該聚類算法的時間復(fù)雜度是，其中n是數(shù)據(jù)庫中線段總數(shù)。對于更高維（）則是。如果不用任何空間索引，將不得不掃描數(shù)據(jù)庫中所有線段。這樣，時間復(fù)雜度就是。如果使用像r樹一樣的合適索引，就能夠通過橫渡索引有效的找到鄰域的線段。這樣，時間復(fù)雜度就減小到。該算法很容易擴展以便支持帶權(quán)的軌跡。該擴展在很多應(yīng)用中都非常有用。距離函數(shù)不是米制的，因為它不服從三角不等式。即。這使得傳統(tǒng)空間索引的直接應(yīng)用很困難。一些技術(shù)可以用來對付這一難題。例如，可以采用常數(shù)

28、轉(zhuǎn)換插入法將不服從三角不等式的距離函數(shù)轉(zhuǎn)化為緊鄰的另一個。3.3.2 簇的代表軌跡簇的代表軌跡描述屬于簇的軌跡分割的大概移動?？梢园阉醋龃氐哪Ｐ?。需要從簇中提取大量的移動信息使得該領(lǐng)域?qū)＜夷軌蛎靼总壽E中的運動。這樣，為了從軌跡聚類中得到充足的實際可能，就確實需要代表軌跡。下圖說明生成代表軌跡的方法。代表軌跡是一列點。這些點是用掃描線方法確定的。當穿過簇的主軸方向線段掃描垂線時，計算撞擊掃描線的線段數(shù)目。該數(shù)字只有當掃描線通過開始點或結(jié)束點時才改變。如果該數(shù)字大于或等于minlns，計算這些關(guān)于主軸的線段的平均坐標并將之插入代表軌跡；否則，跳過臨時點。同時，如果前面一點太靠近，跳過臨時點平滑代

29、表軌跡。 圖3-8 提取代表軌跡下面更詳細的解釋以上方法。為表示簇的主軸，在定義11定義平均方向向量。將向量相加得到方向向量，并將結(jié)果標準化。這是個給對平均方向向量貢獻更多的較長向量的影響的探索法。在代表簇中每個線段的向量集上計算平均方向向量。定義11. 假定一向量集。的平均方向向量定義如公式（8）。這里，是的基數(shù)。 （8） 如上所述，計算關(guān)于平均方向向量的平均坐標。為使計算更容易，旋轉(zhuǎn)坐標軸使x軸與平均方向向量平行。這里，要用到公式（9）中的旋轉(zhuǎn)矩陣。角度可以通過平均方向向量和單位向量間的內(nèi)部乘積來獲得。如圖3-9在xy坐標系中計算平均坐標后，它就會轉(zhuǎn)回為xy坐標系中一點。 （9） 圖3-9

30、. x和y軸的旋轉(zhuǎn)。下圖顯示代表軌跡生成算法。首先計算平均方向向量并且暫時旋轉(zhuǎn)坐標軸（1-2行）。然后用旋轉(zhuǎn)軸坐標對始點和終點進行分類（3-4行）。當按照已分類的順序掃描始點和終點時，計算線段數(shù)并計算這些線段的平均坐標（5-12行）。 算法4：產(chǎn)生代表軌跡的算法- 代表軌跡生成算法-輸入：（1）線段簇，（2），（3）平滑算子輸出：的代表軌跡算法：01. 計算平均方向向量；02. 旋轉(zhuǎn)坐標軸使x軸與平行；03. 讓為簇中線段的始點與終點集； /*x 值表示x軸坐標*/04. 通過點的x值對中點分類；05. 對每個做 /*用掃描線（或平面）計算*/06. 讓為包含點x值的線段數(shù)目；07. 如果08

31、. ：=和緊鄰的前一點間x值的差別；09. 如果10. 計算平均坐標；11. 撤銷循環(huán)得到點；12. 將 附加到的末尾；- 下面討論參數(shù)和的數(shù)值選擇問題： 先展示選擇算子數(shù)值的探索法。采用熵原理。在信息原理中，回歸與關(guān)于與給定概率分布聯(lián)合的事件的不確定數(shù)目相關(guān)。如果所有輸出可能相等，熵應(yīng)最大。探索法是基于以下觀察。在最差的聚類中，趨于一致。即，對于太小的，對于幾乎所有線段都為1；對于太大的，對于幾乎所有線段都為，其中是線段總數(shù)。這樣回歸就最大化了。相反，在好的聚類中，趨于偏斜。這樣，熵變得較小。用公式（10）的熵定義。然后，找到使最小的值。理想的值可以通過模仿鍛煉技術(shù)有效獲得。 (10)其中，

32、 ， 然后展示選擇算子數(shù)值的探索法。在理想的數(shù)值上計算的平均。這一操作導(dǎo)致沒有附加花費，因為它能在計算時完成。然后，確定理想的值（）。這是正常的，因為應(yīng)大于來發(fā)現(xiàn)有意義的簇。 用探索法估計的算子數(shù)值并不確定真的理想。然而，相信探索法在理想數(shù)值可能存在處提供合理的變動。該領(lǐng)域?qū)＜夷軌蛟诠烙嬛抵車囉靡恍?shù)值，并通過視覺檢驗選擇最理想的一個。第四章中會證明該探索法的有效性。中南大學(xué)本科生畢業(yè)論文 第4章 實驗分析-第四章 實驗分析4.1 實驗設(shè)計 從美國聯(lián)合臺風(fēng)警報中心得到1950年至1970年間的大西洋臺風(fēng)數(shù)據(jù)集，并采用軌跡聚類算法traclus對其進行聚類來提取公共子軌跡，以驗證其可行性并分析

33、其優(yōu)缺點。該數(shù)據(jù)集中數(shù)據(jù)包含臺風(fēng)提取點的編號、緯度，經(jīng)度。用內(nèi)存足夠的電腦在xp系統(tǒng)上進行試驗，采用microsoft visual studio 2005編程軟件中的vb語言來編程執(zhí)行算法并用可視檢驗工具進行直觀檢驗。4.2 臺風(fēng)軌跡提取結(jié)果圖4-1為軌跡跟蹤數(shù)據(jù)原始圖像，圖4-2為特征點提取圖像。由圖4-2可知，mdl準則能很好的提取特征點，準確度很高。圖4-1.軌跡跟蹤數(shù)據(jù)圖像 圖4-2.特征點提取圖像圖4-3顯示了實驗中采用不同參數(shù)數(shù)值而顯示的的軌跡聚類成簇圖像，用可視檢驗和領(lǐng)域知識，得到理想算子數(shù)值：=2，=6，即圖4-4。由圖4-3中可以看出算子數(shù)值的影響。如果用更小的或更大的與理

34、想數(shù)值比較，算法traclus會發(fā)現(xiàn)更大或更小的（即有更少的線段）簇。相反，如果用更大的或更小的與理想數(shù)值比較，算法traclus會發(fā)現(xiàn)更小或更大的簇。 圖4-3.不同參數(shù)值聚類圖像比較 圖4-4.理想?yún)?shù)值聚類圖像圖中彩色線段集為聚類所得簇，黑色粗體線段為主要代表軌跡。從圖像看出所聚主要簇恰好是公共子軌跡。圖4-4顯示的結(jié)果大體是合理的。眾所周知颶風(fēng)沿著曲線移動，先是由東到西，變?yōu)橛赡系奖?，再變?yōu)橛晌飨驏|。還有些颶風(fēng)則沿著由東到西或是由西到東的直線移動。較低的水平簇表示由東到西的運動，較高的水平簇表示由西到東的運動，垂直簇表示由南到北的運動。4.3 結(jié)果分析經(jīng)過對實驗結(jié)果的分析，采用的軌跡聚

35、類算法traclus有如下特點。優(yōu)點：（1）能夠提取方向性較為一致的臺風(fēng)軌跡；（2）可以顧及軌跡的局部特征；（3）具有一定的抗噪性。缺點：（1）對于軌跡分布不均勻的情況，參數(shù)設(shè)置較為困難；（2）全局設(shè)置參數(shù)，可能受到局部噪聲的影響；（3）只適合提取方向性較好的軌跡，對于復(fù)雜形狀的軌跡（如弧狀）提取效果不理想。進一步，將針對上述局限采取針對性的改進措施，以期更好應(yīng)用于空間軌跡提取。中南大學(xué)本科生畢業(yè)論文 第5章 總結(jié)-第五章 總結(jié)該論文研究了在分割分組體系基礎(chǔ)上創(chuàng)建的軌跡聚類算法traclus。隨著算法的進展，軌跡在特征點處被分為一系列線段；然后在同一密集區(qū)域內(nèi)的相似線段組成簇。traclus的

36、主要優(yōu)點是：能從軌跡數(shù)據(jù)庫中發(fā)現(xiàn)公共子軌跡。為顯示traclus的效果，使用真實數(shù)據(jù)集（颶風(fēng)跟蹤數(shù)據(jù)）做了大量實驗。同時實施了視覺檢驗工具用于顯示簇的生成效果。視覺檢驗結(jié)果顯示traclus能有效的鑒別出簇的公共子軌跡。經(jīng)過分析，軌跡聚類算法traclus在以后可以做如下擴展：1. 運動模式：可以擴展算法來支持不同種類的運動模式，特別是圓形運動。算法traclus主要支持直線運動。這一擴展能通過增強產(chǎn)生代表軌跡的方法來完成。2. 預(yù)測時間：可以擴展算法以考慮聚類過程中的時間元素。將時間同位置一起被預(yù)測。這一擴展將很大的提高算法traclus的應(yīng)用能力?？偟膩碚f，本論文可以證明算法traclus

37、可以很好的從軌跡數(shù)據(jù)集中提取公共子軌跡。然后數(shù)據(jù)分析者們能夠通過公共子軌跡的特點從軌跡數(shù)據(jù)中取得新的深入見解。當然，這一工作只是第一步，還存在著很多像上面一樣的富有挑戰(zhàn)性的難題，可以對這些問題做調(diào)查作為將來的研究。中南大學(xué)本科生畢業(yè)論文 參考文獻-參考文獻1 fayyad u m, piatetsky-shapiro g, smyth p. from data mining to knowledge discovery: an overview. in advances in knowledge discovery and data mining, aaai/mit press, 1996.2

38、 miller h j and han j w. 2009. geographic data mining and knowledge discovery, second edition m. new york: crc press.3 盧林, 吳紀桃, 柳重堪. 2005. 基于特征的等高線數(shù)據(jù)聚類方法j. 測繪學(xué)報, 34(2): 138-141.4 lee j g, han j w and whang k y. 2007. trajectory clustering: a partition and group framework c. proceedings of 2007 acm-s

39、igod international conference on management of data, beijing, 593-604.5 y. huang, l z and zhang p. 2008. a framework for mining sequential patterns from spatio-temporal event data sets j. ieee trans. on knowledge and data engineering.6 jensen c, lin d and ooi b. 2007. continuous clustering of moving

40、 objects j. ieee trans. on knowledge and data engineering, 2007.7 palma a t, bogorny v, kuijpers b and alvares l o. 2008. a clustering based approach for discovering interesting places in trajectoriesc. proceedings of sac08, fortaleza, ceara, brazil8 gaffney s and smith p. 1999. trajectory clustering with mixtures of regression modelsc. proceedings of 1999 international conference of knowledge discovery and data mining, san diego, ca, 63-72.9 han j w, kamber m. 數(shù)據(jù)挖掘概念與技術(shù)，北京：機械工業(yè)出版社，2008.10 koperski k, han j w. discovery of spatial association rules in geograph