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