【文章內容簡介】 8 圖 3線段間距離函數(shù)的三部分 定義 1. iL 和 jL 之間的垂直距離定義如下 212 221),(????? ??? ll llLLd ji （ 1） 定義 2. iL 和 jL 之間的平行距離定義如下 ),(),( 2||1|||| llLLd ji ? ??? （ 2） 1||l 是 sp 到 is 和 ie 距離中較小值， 2||l 是 ep 到 is 和 ie 距離中較小值。 定義 3. iL 和 jL 之間的角度距離定義如下 ????? ?? ????00001 8 090| | ,|| 900),s i n (||||),( ? ??? ifL ifLLLd jjji （ 3） 另外， iiieiiis esuspesusp .,. 21 ???? （ 4） 其中，||| | | |||.)c o s (,||||.,||||.2221 jjiijjiiiiiijiiiiiji eses eseses esesues esssu ??? ?（ 5） 定義兩線段間距離如下： ),(.),(.),(.),( |||| jijijiji LLdwLLdwLLdwLLd i s t ????? ??，其中權值 ?w 、 ||w 、 ?w 在本文中取 1。 臺風軌跡分割 特征點提取 軌跡行為劇烈變化位置上的點就是特征點。軌跡在每個特征點處分割，每個中南大學本科生畢業(yè)論文 第 3 章 軌跡聚類算法 9 分割由兩相鄰特征點間線段表示。這樣，軌跡就被分割為一系列線段，稱線段為軌跡分割。下圖顯示軌跡和它的軌跡分割。 圖 33 軌跡及 其軌跡分割 理想的軌跡分割應包含兩個可取的性質：準確性和簡明性。準確性指軌跡和它的軌跡分割集間的差別應盡可能的小。簡明性指軌跡分割的數(shù)目應盡可能的小。這兩個性質相互矛盾，因此需要在兩者間找到一個理想平衡點。 可以采用廣泛應用于信息理論的最小描述長度（ MDL）準則來發(fā)現(xiàn)準確性和簡明性間的理想平衡點。 MDL 包含兩部分： L(H)和 L(D|H)。其中， H 指假設， D 指數(shù)據(jù)。 L(H)是假設的描述長度； L(D|H)是數(shù)據(jù)在假設的幫助下編碼的描述長度。對解釋 D 的最佳假設 H 是使 L(H)和 L(D|H)之和最小時的值。 在軌跡 分割難題中，假設與特定軌跡分割集相對應。想找到理想的軌跡分割，就是找最佳分割，也就是用 MDL 準則找最佳假設。下圖顯示了 L(H)和 L(D|H)的構想。 圖 34 L(H)和 L(D|H) 假定軌跡 le n iji pppppTR ??321? 和特征點集 ? ?c p a riccc pppp , 321 ? 。然后，用公式 6 規(guī)劃 L(H)， )( 1?cjcjpplen 表示線段 1?cjcjpp 的長度。所以， L(H)表示所有軌跡分割長度之和。 ??? ?? 11 2 ))((log)( 1i jjp a rj cc ppl e nHL (6) 中南大學本科生畢業(yè)論文 第 3 章 軌跡聚類算法 10 ? ?? ??? ?? ???? ?? ?? 11 1 12121 11 )),((l o g)),((l o g)|( i jjjjjjparjcck kkcckkcc ppppdppppdHDL ? (7) 另一方面，用公式 7 規(guī)劃 L(D|H)。 L(D|H)表示軌跡和它的軌跡 分割間差異之和。對每個軌跡分割，將軌跡分割和屬于分割的線段 )1( 11 ??? ?? jjkk ckcpp 間差異加起來。用垂直距離和角度距離之和衡量差異。可以不考慮平行距離，因為軌跡包圍了它的軌跡分割。 長度和距離是真值。在實踐中，將真值 x 編碼，假定精度為 ? ，使得編碼數(shù)?x 滿足 |x ?x | ? 。如果 x 很大，并且 ?xx? ， ?22 lo glo g)( ?? xxL 。這里，設 ? 為1。這樣， )(xL 與 x2log 相等。 用線段的長度代替線段端點來定義 L(H)。原因有二，首先，要通過他們的相互距離對線段聚類。 L(H)中的長度和距離函數(shù)，也就是線段間的垂直、平行、角度距離，在衡量相互距離上比線段端點更好。即新定義更適合子軌跡聚類工作。其次，不用端點的一個很重要原因是使聚類結果不受線段坐標影響。這樣，一束線段可以由低坐標位置轉換到高坐標位置； 然而，距離函數(shù)應該還能正確度量相互距離。如果用兩端點的坐標值規(guī)劃 L(H)，聚類結果可以被這樣的轉換更改。 注意， L(H)度量簡明度， L(D|H)度量準確度。因為三角不相等， L(H)會隨著軌跡分割數(shù)目的增加而增加。同時， L(D|H)顯然會隨著軌跡分割集偏離軌跡而增加。 前面提到，需要找到一使 L(H)+L(D|H)最小的理想分割。 解決方案的關鍵想法是將局部理想看做全局理想。讓 ),( jipar ppMDL 表示 ip和 jp 間軌跡的 MDL 花費，假定 ip 和 jp 是僅有的特征點。讓 ),( jinopar ppMD L 表示 ip 和 jp 間沒有特征點時軌跡的 MDL 花費，即保持原有軌跡時。),( jinopar ppMD L 中的 L(D|H)是 0。然后局部理想是對每個使 jki ?? 的 k 滿足),( jipar ppMDL ? ),( jinopar ppMD L 的最長軌跡分割 jipp 。如果前者小于后者，選擇 kp 作為特征點使得 MDL 花費更小。而且因為簡明性的緣故增大軌跡分割長度。 中南大學本科生畢業(yè)論文 第 3 章 軌跡聚類算法 11 下圖五顯示了近似軌跡分割算法。對軌跡上的每個點計算 ),( jinopar ppMD L 和),( jipar ppMDL （ 5~6 行）。如果 ),( jipar ppMDL 大于 ),( jinopar ppMD L ，將緊鄰的前一個點插入到特征點集 iCP中（ 8 行）。然后從那一點重復相同過程（ 9 行）。否則增加后備軌跡分割的長度（ 11 行）。 算法 2：近似軌跡分割算法 近似軌跡分割算法 輸入：軌跡 le n iji pppppTR ??321? 輸出：特征點集 iCP 算法： p1 添加到 iCP； 1，長度為 1； （開始索引 +長度 ? leni）時 04. 當前索引 =開始索引 +長度； 05. 計算 ),( jipar ppMDL ； 06. 計算 ),( jinopar ppMD L ； 07. 如果 ),( jipar ppMDL ),( jinopar ppMD L ； 08. 將前一點添加到特征點集； 09. 開始索引 =當前索引 1，長度 =1； 10. 否則 11. 長度 =長度 +1 12. 將結束點添加到特征點集 近似算法的時間復雜度為 )(nO ， n 為軌跡長度。 中南大學本科生畢業(yè)論文 第 3 章 軌跡聚類算法 12 構造特征線段 經(jīng)過上一步驟的操作，每個軌跡對應一個特征點集。特征點集中從始 點到終點，每兩個相鄰特征點可以構成一小線段，即特征線段。 有時候特征點的提取也會不理想，如下圖舉例。假設使 MDL 花費最小的理想分割是 ? ?51,pp 。該算法不能發(fā)現(xiàn)準確方案，因為他在 p4 處停止掃描，在此),( jipar ppMDL 大于 ),( jinopar ppMD L 。當然，該算法的精確性已經(jīng)很高了。 圖 35 特征點提取 特征線段聚類 基于密度的特征線段空間聚類 距離函數(shù)概述 距離函數(shù)是三種距離的加權和。首先，垂直距離主要衡量從不同軌跡提取的線段間的位置差異。其次，平行距離主要衡量從相同軌跡提取的線段間的位置差異，一個軌跡中兩臨近線段間的平行距離總是 0。最后，角度距離衡量線段間方向差異。 距離函數(shù)的對稱性對于避免聚類結果的模棱兩可很重要。如果距離函數(shù)是不對稱的，不同聚類結果可以通過過程順序獲得。 基于密度聚類的概念 以下定義是基于密度聚類所需的 概念。 D 表示所有線段集。改變本來為 DBSCAN算法提出的點的定義為線段的。 定義 4. 屬于 D 的線段 iL 的 ? 鄰域定義為 ? ??? ??? ),(|)( jiji LLd i s tDLLN 。 中南大學本科生畢業(yè)論文 第 3 章 軌跡聚類算法 13 定義 5. 如果 M inLnsLN i ?)(? ，那么屬于 D 的線段 iL 稱為核心線段。 定義 6. 如果 )( ji LNL ?? 并且 M inL nsLN j ?)(? ，從線段 DLj? 到線段 DLi? 是直接密度可達的。 定義 7. 如果有一屬于 D 的線段鏈 iijj LLLL , 11 ?? ? 使得 kL 從 1?kL 是直接密度可達的，那么從線段 DLj? 到線段 DLi? 是密度可達的。 定義 8. 如果有一線段 DLk? 使得線段 DLi? 和線段 DLj? 對 kL 是密度可達的，那么 iL 對 jL 是密度 連接的。 定義 9. 非空子集 Dc? 是密度連接集，如果 c滿足以下兩個條件： （ 1） 對于任意屬于 c的 iL 、 jL ， iL 對 jL 是 密度連接的； （ 2） 對于任意屬于 D的 iL 、 jL ，如果 iL 屬于 c， jL 對 iL 是密度可達的，那么 jL屬于 c。 在下圖描繪這些定義。密度可達性是直接密度可達性的轉化終止，其關系是不對稱的。只有核心線段是互相密度可達的。然而，密度連接性卻是對稱關系。讓