1. <tbody id="kgli8"><nobr id="kgli8"><sub id="kgli8"></sub></nobr></tbody>

          <tbody id="kgli8"><listing id="kgli8"></listing></tbody>

          <mark id="kgli8"><tt id="kgli8"></tt></mark>
          <mark id="kgli8"></mark>
            <code id="kgli8"><var id="kgli8"></var></code>
            
            
          1. <menuitem id="kgli8"></menuitem><tbody id="kgli8"></tbody>

              面向軌跡大數據的高效聚類算法設計與實現

              來源: www.halxjx.net 發布時間:2021-10-21 16:42
              論文地區:中國 論文語言:中文 論文類型:軟件工程
              這是一篇優秀的軟件工程論文范文,主要從面向軌跡大數據的高效聚類算法設計與實現展開探討,在充分分析軌跡多屬性特征的基礎上,通過對已有聚類方法的改進、并行化和結合,提出了和通過一套面向大規模軌跡數據的高效
                  這是一篇優秀的軟件工程論文范文,主要從面向軌跡大數據的高效聚類算法設計與實現展開探討,在充分分析軌跡多屬性特征的基礎上,通過對已有聚類方法的改進、并行化和結合,提出了和通過一套面向大規模軌跡數據的高效聚類算法,并通過大量實驗驗證了算法的有效性和高效性。

                 摘要:調研了軌跡聚類方面的相關研究工作,針對調研結果闡明了本文的研究目的,主要思路以及研究的主要內容。在充分分析軌跡多屬性特征的基礎上,通過對已有聚類方法的改進、并行化和結合,提出了和通過一套面向大規模軌跡數據的高效聚類算法,并通過大量實驗驗證了算法的有效性和高效性。

              第一章 緒論

              1.1 研究背景及意義
              隨著現如今通信技術的成熟和車輛的普及,為了加強道路運輸的車輛監督管理,交通運輸部門要求車輛使用具有行駛記錄功能的 GPS 或北斗定位裝置[1]。大量的車輛運動軌跡點信息是可以通過 GPS 終端實時采集而得到的。隨著時間的增長,收集的車輛軌跡數據的量越來越大,達到了 TB 甚至 PB 級別的數據量。這些數據中包含著大量未發掘的有價值的信息,可以通過對這些信息的挖掘,找出車輛行駛、異常[2]、擁堵和熱區分布[3][4]等規律性時空知識,并將這些信息運用到交通安全控制、車流量管控等實際應用領域。利用這樣的關系不但可以預測車輛的行駛軌跡、發現司機的駕駛習慣、監控道路的擁堵情況,也可以將新增數據用于實時交通狀況的預報等各種智能交通應用場景。
              軌跡聚類分析是發現車輛軌跡共同行為模式最直觀、最有價值的一類方法。現有大部分軌跡聚類分析的研究大多是依據軌跡的形狀特征和時空特征展開,很少關注軌跡速度、方向等運動學特征,更缺乏對多類軌跡特征的融合分析,這樣可能造成度量的軌跡間相似度精確不高,不能全面體現軌跡間的實際相似情況。此外,在軌跡聚類分析的算法選擇方面,雖然適用于軌跡或軌跡點數據本身的聚類算法種類繁多,但是在實際應用中,不同的聚類算法得出的聚類結果在效果、精度和效率都存在明顯差異,所以對面向軌跡數據的聚類算法的選擇對于軌跡聚類分析是否有效起著決定意義的作用,特別是聚類算法中軌跡相似度的定義和度量方法是聚類準確度的直接決定因素。
              在軌跡數據的聚類分析效率方面,現有研究大多針對已經收集好的歷史軌跡數據進行分析。然而,軌跡數據是實時更新的,并且呈現指數級爆炸增加的趨勢,這對軌跡聚類算法的效率提出了更高的要求。一方面大規模軌跡數據的聚類分析已經很難在單機系統完成,需要對聚類過程進行分布并行處理。雖然已有很多研究關注了并行聚類方法的研究,但分布式聚類過程在提高算法數據處理規模和效率的同時,也勢必帶來了聚類結果在全局精度方面的損失。另一方面,軌跡數據作為一種實時更新的實體,每次的少量數據更新都需要全部軌跡數據的重新聚類,嚴重影響了軌跡聚類的分析結果對于時延敏感型智能交通的應用,研究有效的軌跡增量聚類方法也是亟待解決的問題。
              圖 3. 3 EDR 的操作
              圖 3. 3 EDR 的操作
              .............................

              1.2 研究內容
              本文以軌跡數據聚類為主要研究內容,希望通過聚類操作準確發現具有不同特征的軌跡簇集,以支持基于此分析結果的更深入研究,例如預測軌跡異常、交通安全預警等現實場景。下面給出本文各部分的研究內容及主要技術路線。
              總體而言,本文的研究內容包括四個方面:軌跡特征選擇,軌跡聚類算法、軌跡聚類的并行化及增量化模型與實現。在軌跡數據的特征選擇方面,通過對軌跡經緯度、速度、角度等多維度特征的提取和融合,將軌跡數據的時空和運動特征體現的更加完整,同時使用這些特征作為軌跡關鍵點的篩選標準,從而可以在盡量不丟失軌跡信息的前提下,將軌跡數據進行精簡,以便加快后續軌跡數據聚類分析的速度。在軌跡數據的聚類分析方面,利用離散Fréchet 距離度量具有多種特征的軌跡間的相似程度,并選擇了高效的 K-Means 算法作為軌跡聚類的主要實現方法,提出了支持多特征的軌跡聚類算法 FK-Means。通過模擬生成符合現實情況的多種類型的軌跡數據集,驗證了 FK-Means 算法的聚類效果。在大規模軌跡數據的高效聚類方面,分別研究了面向大量歷史軌跡的離線并行聚類算法和面向少量增量軌跡的在線增量聚類算法。首先,在軌跡并行聚類研究方面,將 MapReduce 框架與 FK-Means 聚類算法結合,使用 LOF 算法優化聚類結果,提高軌跡聚類的處理效率和精度;其次,在軌跡增量聚類研究方面,將聚類過程分為兩個階段,第一階段先對新增數據使用 FK-Means 算法進行聚類,得出新增數據的聚類結果,然后在第二階段將新增數據的聚類結果和歷史數據的聚類結果進行整合,這一階段中由于新增數據的數量級比歷史數據的數量級小很多,為了加快搜索的速度,所以在對聚類結果的遍歷過程中加入了 DBFS 算法,在聚類結果整合中,為了保證聚類結果的準確度,引入了 Chameleon 算法對最終得出的聚類結果重新整合,使得局部聚類的效果盡可能接近全局聚類的效果。
              .............................

              第二章 相關研究工作

              2.1 軌跡相似度度量
              在軌跡相似度度量研究方面,現有工作中最常采用的方法是根據不同軌跡間地理位置距離的相近程度判斷他們是否相似。例如,文獻[5]將了歐幾里得距離與軌跡經緯度相結合計算軌跡間的相似度,通過計算兩條軌跡中對應點之間經緯度的歐式距離的均值或其他統計特征值來表征軌跡間的相似度。這種方法在面對大量高緯度軌跡數據的時候,效率會明顯的降低。為了提高軌跡相似度度量的處理速度,Chan 等人將離散小波技術和距離計算方式相結合,實現了對軌跡數據的降維處理[6][7]。但是由于每個軌跡集實際采樣的情況是不盡相同的,例如采樣頻率不同,傳感器錯誤導致的采樣缺失等,上述方法是沒有辦法在這種情況下準確地找到兩條軌跡中的對應軌跡點的。針對該問題,文獻[8]將整條軌跡數據劃分為多個軌跡段,再通過歐幾里得公式計算軌跡段之間的距離,當兩條軌跡采樣率不同時,會單獨進行比較和處理。文獻[9]提出了一種快速匹配相似性查詢的方法,該方法利用最長公共子序列 LCS 算法對軌跡間相似度進行度量,通過計算最長公共子序列數,選出數值高于指定閾值的軌跡序列,將這樣的一對軌跡序列定義為相似序列。由于該方法不需要比較所有的軌跡點,所以即使軌跡集中含有大量的噪聲點也不會太影響相似度的計算結果。面對不同的采樣情況,文獻[10]則提出通過對時空軌跡特征的分析,利用軌跡所在路徑和速度曲線定義新的軌跡,使軌跡符合動態時間封裝算法(DTW)的條件,并使用 DTW 算法來計算軌跡間相似度,即根據時間時序對軌跡數據進行局部縮放,解決軌跡數據由于采樣頻率不同或缺失軌跡點導致的模板匹配問題,使得求出的軌跡相似度更加合理。不過 DTW 算法要求軌跡點之間具有時間連續性,因此,算法沒有辦法在小部分區間內識別軌跡完全不相似的情況。
              上述的方法對軌跡相似度的度量大多僅依賴軌跡的經緯度屬性,然而軌跡作為一種復雜的時空數據,還具有速度、方向、路網約束等多種特征。融合軌跡的多種不同特征分析軌跡間的相似度,能更加準確地反映移動對象的運動特征。文獻[11]是通過時間和空間兩個角度對軌跡數據進行過濾,增加后續對軌跡相似度計算的精度。但是由于該算法模型中對軌跡的定義并不清晰,較少考慮路網的情況,所以面對不同類型的路網時,其相似度度量的準確度會受到一定影響。僅僅對軌跡數據進行過濾,而不對軌跡相似性度量的概念重新定義,對軌跡相似度度量精度改進有限。為此,文獻[12]從時空維度給出了一種基于單位時間平均值Hausdorff 距離的軌跡相似性度量方法,該方法有效提高了軌跡數據聚類結果的質量。、
              .........................

              2.2 聚類算法
              軌跡數據聚類是軌跡分析的重要方面,是將具有不同時間和空間相似度特征的時空對象劃分為多個類或簇,使同一類內的對象相似性程度高,而不同類之間數據的相異程度高[19]。針對軌跡聚類分析已有不少研究成果。吳笛等人[20]對南海旋渦軌跡進行時空聚類分析,在空間聚類的基礎上提出軌跡線段時間距離的度量方法和閾值確定原則,驗證了基于密度的軌跡時空聚類方法的有效性。文獻[21]使用改進后的 TRACLUS 算法對劃分后的軌跡數據進行聚類分析,以此來推測軌跡的運動趨勢。文獻[22]在 TRACLUS 算法的基礎上加入了方向、速度等語義時空信息,提出了一種新的軌跡聚類算法,實驗證明該算法有效提高了聚類精度。但由于 TRACLUS 算法受輸入參數和噪聲數據影響較大。為了解決這個問題,文[23]提出了一種基于密度峰值的軌跡聚類算法(TCDP),實驗結果表明 TCDP 算法具有更好的軌跡聚類效果。為了解決軌跡過長導致的聚類困難問題,文獻[24]提出一種新的軌跡聚類算法 iBTC,算法將 Dijkstra 算法和獨立森林的思想相結合,求出軌跡的最佳分段并整合,并使用細分-合并過程對軌跡數據進行聚類。文獻[25]提出一種以軌跡子段為聚類目標的聚類算法 CTIHD,實驗結果表明該算法相比同類算法具有更好的軌跡聚類效果。考慮到軌跡聚類研究在智能交通場景中的應用,廖律超等提出了一種基于路網下的軌跡潛在語義關聯的譜聚類方法[26],實現了軌跡空間向量的建模,可快速提取軌跡的關鍵特征信息,通過降維劃分語義子空間,實驗結果表明潛在的語義相關性對軌跡進行快速譜聚類具有一定的處理優勢。夏英等人在對交通系統進行進一步研究的時候,創新性的引用了流量、擁堵狀態等數據,并且根據具體應用過程中的實際情況對每一個所使用的屬性在時間和空間上進行分析,研究各個變量之間的相關性,通過研究表明,這種創新性的算法是能夠提高準確性并且使效率大大提高的[27]。
              圖 3. 1 DTW 的操作
              圖 3. 1 DTW 的操作
              ...............................

              第三章 軌跡聚類方法...........................................10
              3.1 相關理論基礎..........................................................10
              3.1.1 軌跡相似性度量算法..........................................10
              3.1.2 聚類算法................................................12
              第四章 軌跡并行聚類.......................................28
              4.1 相關理論基礎.....................................................28
              4.1.1 Hadoop 介紹................................................28
              4.1.2 MapReduce 分布式框架介紹......................................28
              第五章 軌跡增量聚類....................................................43
              5.1 相關理論基礎......................................................43
              5.1.1 變色龍算法......................................................43
              5.1.2 雙向廣度優先搜索算法..............................44

              第五章 軌跡增量聚類

              5.1 相關理論基礎
              在面對新增數據聚類結果與歷史數據聚類結果融合的問題上, 變色龍(Chameleon)算法比第四章使用的 LOF 算法更合適。Chameleon 算法的執行需要對聚類集中全部的類進行搜索,而 LOF 算法只對局部類簇進行搜索,由于新增數據與歷史數據的類屬關系不明確,如果采用局部搜索的方法會降低聚類結果精度。
              5.1.1 變色龍算法
              Chameleon 算法涉兩個環節:結合 hMetic 算法獲取相對較小的類集合按照相似度將最小類集合并獲取新的類集。在第一個環節中,主要思路為:基于 K-最近鄰算法,hMetic 算法按照邊的權重實際分割關系圖,隨機指定一個點,再找到類中與之相似度最高的 K 個點,便構成了最小類,其中,相似度的分析借助點間距大小實現。在第二個階段中,主要思路為:深入分析兩個類的相似性,大多是結合類的鄰近性以及類內對象的連接狀況分析類的相似性,也就是說,若兩個類均存在非常大的互連性,同時兩者臨近,則可以將兩者合并起來。
              5.1.2 雙向廣度優先搜索算法
              雙向廣度優先搜索(DBFS)算法是對 BFS 的延伸。BFS 算法會按照廣度優先原則由一個方向啟動搜索,直至檢索所有節點或者獲取目標節點。不同于 BFS 算法,DBFS 算法基于兩個方向進行搜索,會按照廣度優先的原則啟動,能夠按照實際需求、數據的特點等制定搜索方向,當兩個搜索方向重合時或者獲取目標節點時,這一算法停止。所以,相比 BFS 算法,DBFS 算法所獲取的搜索樹深度大幅降低,不管是時間上還是空間上,這一算法均比較優異。按照搜索速度以及最初搜索方向的差異,DBFS 算法可分成兩類:一是在兩個方向上輪流搜索;二是先從有限搜索點數相對較少的方向開始。至于兩個方向節點數是否相同,第二種方式未做限定,能更好的的貼合現實狀況。在搜索前,廣度優先搜索算法(BFS)未設定具體的目標。
              ..........................

              第六章 總結與展望

              6.1 總結
              本文調研了軌跡聚類方面的相關研究工作,針對調研結果闡明了本文的研究目的,主要思路以及研究的主要內容。在充分分析軌跡多屬性特征的基礎上,通過對已有聚類方法的改進、并行化和結合,提出了和通過一套面向大規模軌跡數據的高效聚類算法,并通過大量實驗驗證了算法的有效性和高效性。主要貢獻包括如下三個方面:
              (1)通過對軌跡數據關鍵點、代表點的選取,可以在盡量不丟失聚類準確度的前提下加快軌跡數據的聚類分析速度。使用離散 Fréchet 距離度量方法計算軌跡多個屬性的相似度并融合,再將該相似度與 K-Means 算法相結合提出了基于軌跡多屬性融合的 FK-Means 算法,實現了更全面體現軌跡特征的聚類分析過程。
              (2)為了提高軌跡數據的聚類分析效率,在對大規模軌跡數據處理方面使用了并行化聚類的思想,將 MapReduce 框架與 FK-Means 算法結合,實現了聚類的并行化操作,在盡量不影響聚類準確度的前提下可以更快的處理大量數據,并使用改進后的 LOF 因子對得出的聚類結果進行優化,提高并行聚類結果的準確度。
              (3)在對新增軌跡數據的聚類分析方面,使用了增量聚類的思想。首先利用 FK-Means聚類算法新增數據進行聚類;然后將雙向廣度算法與 Chameleon 算法相結合提出了 DC 算法,實現了對新增軌跡數據高效并準確的聚類分析。
              參考文獻(略)
              返回頂部
              必赢亚洲