基于稀疏子集分析的軌跡聚類發現*

薛 璇 陳平華

（廣東工業大學計算機學院 廣州 510006）

1 引言

隨著現如今人們在社區間的軌跡日漸增多，通過軌跡來檢測社區對于社會行為分析和推薦服務都成為關注熱點，所以對檢測社區的精確度要求越來越高。現有的研究側重于社會聯系和圖分區中的社區檢測，但在實踐中，由于隱私問題，現實生活中的生活聯系很難被捕捉。不過，我們可以利用Wi-Fi 和 GPS 設備捕捉人類行為軌跡［1～2］。為了更好地檢測軌跡中可能存在的社區，對檢測的精確度要求越來越高。一般地，社區檢測通常通過聚類來實現，軌跡聚類的目的是從一組運動物體的軌跡中識別聚類，其中特定聚類中的軌跡在一個或多個運動相關特征中表現出相似性［3］。軌跡數據的示例包括車輛位置數據，動物移動數據和人類行為跟蹤數據。 因此，對于軌跡數據集執行數據挖掘和行為分析的研究越來越受歡迎［4］。

現有研究通過將共享位置視為社區關系的唯一決定因素，可能錯過真實關系或者可能錯誤地識別不存在的社區。在社交圖社區檢測文獻［5］中，社區通常定義在基于鏈接的圖上，捕獲直接的成對交互；由于隱私問題或技術限制，這種明確的交互標記顯然難以在許多實際環境中直接獲得。Zhou等［1］對物理世界中的三種人類行為軌跡集進行分析，提出基于軌跡多源擴散模型社區檢測（Trajectory-based community detection by diffusion modeling on multiple information sources，TODMIS）算法，通過對軌跡數據集四個維度（語義、空間、時間、速度）的建模，將附加信息與原始軌跡數據相結合，并在多個相似性度量上構建擴散過程，在耦合的多圖上發現不同社區的集合（包括社區大小），并使用不同的真實數據集進行評估，實驗結果證明了該方法的有效性。

2 相關工作

TODMIS［2］使用稠密子圖檢測方法來檢測社區，該方法表示一個概率聚類的頂點集合，它是標準單形空間中的單位向量，然后引入二次函數來測量它們之間的平均邊緣權重，并且顯性集被定義為具有最大平均邊緣權重的子圖，其中圖中頂點表示軌跡，頂點間的權重代表軌跡間的相似度。目標是對頂點集進行迭代，每一次都能處理檢測到一個具有最大平均邊緣權重的子圖，該子圖就是所要獲取的社區。然后刪除已經構建子圖的頂點，再次優化過程，直至頂點集為空。

對于社區檢測的聚類問題，TODMIS 算法只在每次迭代中檢測現有軌跡集中最大相關性的軌跡集，并沒有考慮到迭代過程中可能存在的多個相關性較大的軌跡集，忽略最大相關性軌跡集與其他軌跡集的關系，從而陷入局部最優。其次，在每次迭代過程中，一些與社區相關性較大的軌跡被當作為異常值處理而被忽略，從而降低了社區檢測的精確度。因此選擇合適的方法對提高軌跡集聚類分析和社區檢測至關重要。

為了克服現有技術的缺點與不足，提高軌跡數據集聚類精確度，解決算法魯棒性和全局最優等問題，本文提供一種基于稀疏子集聚類分析的社區檢測方法，這可以避免陷入局部最優，在確定軌跡集的情況下，無需進行算法迭代和多次計算，提高檢測社區的效率。

3 基于稀疏子集分析的聚類算法

給定一軌跡集，我們的目標是發現軌跡集中存在具有相似性的軌跡組，定義為表示集或樣例。當在空間的度量下進行評估時，某個社區的軌跡表現出類似的行為。算法框架如圖1。

首先，對軌跡數據集進行預處理，構建軌跡相似度矩陣，由空間關系特征矩陣定義。通過全局對齊核（GAK-IP）［6］來測量兩個軌跡之間的空間相似度，構建軌跡集的空間關系矩陣。其次，將軌跡相似度矩陣轉化成不相似度矩陣，對不相似度矩陣進行稀疏子集選擇（DS3）［7］得到多個聚類簇；同時對每個聚類簇設置一個標簽，在軌跡數據集上構建圖，將標簽擴散到所有軌跡。

圖1 算法模型框架

3.1 構建特征矩陣

用戶的軌跡反映用戶的行為特征，用戶的移動路線可以用時間序列片段來表示。對于兩個用戶的軌跡，定義時間序列如下：

xa和xb表示第 ɑ 個用戶和第 b 個用戶的所有運動軌跡的時間序列表，長度分別為m 和n，xa(1 )表示在第一個時間用戶ɑ 所在的經緯度。由于每個用戶在相同時間內的軌跡移動長度不同，所以，當m=n時，用戶ɑ和b的軌跡相似性度量可以用歐式距離表示，即

當m≠n時，需要采用動態規劃法對齊時間序列，運用已有的DTW動態時間歸整算法構造一個m×n的矩陣網格S，如圖2 所示。矩陣元素d(i，j)表示xa(i)和xb(j)兩個點的歐式距離，即序列xa的每一個點和xb的每一個點之間的相似度，距離越小則相似度越高。在矩陣網格S 中尋找一條通過此網格中若干點的路徑，路徑通過的格點即為兩個序列進行計算對齊的點。

圖2 網格S

由于用戶軌跡長度不同，不能使用歐式距離進行匹配，需要在網格S中找到每個連續的點構成路徑，但是必須保證曲線中從初始點d(1 ，1) 開始到終點d(m，n)結束，這是就要找出代價最小的那條路徑，定義為R：

其中R的第k個元素定義為rk=(i，j)k，定義了序列xa和xb的映射。

路徑不是隨意選擇的，需要滿足兩個約束條件：1）任何一條軌跡的移動速度快慢都可能變化，但是其各部分的先后次序不可能改變，因此多選的路徑必定經過d(1 ，1) 和d(m，n)兩點，在網格S中從左下角出發，到右上角結束。2）如果當前路徑節點為Rk-1(i，j)，那對于路徑下一個節點Rk(i'，j' )必須滿足 0 ≤ (i' -i)≤1 和 0 ≤ (j'-j)≤1，在匹配路徑時，當前匹配的節點k-1的下一個節點k必須是k-1節點的相鄰節點，并且R 中的節點隨著時間單調進行匹配，以此保證xa和xb中每個坐標都在R 中出現，實現路徑的完整性。根據約束條件每個節點的路徑只有三個方向，當路徑已經通過了節點(i，j)，那么下一個通過的節點只可能是(i+ 1，j)，(i，j+1)或(i+ 1，j+1) 。所以匹配兩條軌跡代價最小的路徑：

K主要是用來對不同的長度的匹配路徑做補償。

定義一個累加距離c，從網格S中(1 ，1) 點開始匹配這兩個序列xa和xb，每經過一個節點，之前所有的節點幾點的距離都會累加，到達終點(m，n)后，累積之前經過節點的總距離，即為序列xa和xb的相似度。累積距離c(i，j)為當前節點距離d(i，j)，即點xa(i)和xb(j)的歐式距離與可以到達該點的最小鄰近節點的累積距離之和：

所以xa和xb的相似度cab=c(m，n)。

給定N條軌跡，構建N×N相似度矩陣D，

其中d(p，q)表示第p 條軌跡和第q 條軌跡的相似度，即d(p，q)=cpq，d(p，p)=0 表示軌跡 p 與自身最小距離為0。

3.2 稀疏子集分析

從大規模的數據集或模板中找出有信息量、代表性的子集是一個重要的問題。對于數量繁多復雜的軌跡集，給予一對原集和目標集的元素之間的不相似度，從原集中找到一個子集，稱為樣例或表示，使得其可以有效地描述目標集，運用解決行稀疏約束的跡最小化問題的算法［7］，對特定環境下的軌跡集進行行為分析。

給定一個原集A={a1，a2，...am} 和一個目標集B={b1，b2，...bn} ，分別包含 m 和 n 個數據。構建不相似度矩陣矩陣S，兩個數據集之間每一對元素的不相似度{sij} ，每一個{sij} 表示一個ai能表示bj的程度，sij的值越小，ai能越好地表示bj。一般地，相似度{dij} 和不相似度{sij} 可以通過sij=-dij來設置。

給定不相似度矩陣S，目標是選擇一個原集A使得可以有效的表示目標集B，定義稀疏矩陣C：M×N，關聯不相似度sij，ci是C的第i 行，且ci∈{0 ，1} ，表示ai是否可以表示bj。如果ai是bj的表示，ci=1。為了確保每一個bj能被一個ai表示，必須滿足

選擇一部分A的元素，根據不相似度，能夠很好地編碼，運用基于稀疏矩陣的行稀疏約束的跡最小化問題，實現兩個目標：1）如果ai被用于表示bj，其表示的代價sijcij∈{0 ，sij} ，則整個原集A表示bj的代價是并且用A編碼整個目標集B的代價是；2）當a是目標集B i的某一些元素的表示時，有ci≠0，即C的第i行非零，所以希望使用盡可能少的數據來表示，有較少的表示對應著有較少的非零行在C中。結合以上兩種情況，優化問題的目標函數如下：

其中f(·) 表示一個指示函數，如果其參數為0，其值為0；否則，值為1。目標函數的第一項對應表示的數量，第二項表示編碼目標集B的總代價。約束參數w＞0 權衡兩項的大小，對于小的w值，優化時更關注原集A能更好的編碼目標集B，能獲得更多的表示的數量。在極限的情況下w趨近于0時，目標集B中的每一個元素都由其對應的原集A中的距離最近元素表示，即其中另一方面，如果w的值過大，優化時更關注于矩陣C的行稀疏性，選擇數量較少的表示，對于一個充分大的w，目標集B只從原集A中選擇一個元素來表達。考慮到另一種情況，當原集A和目標集B相同的情況下，即A=B，當約束參數變得足夠小的時候，每一個數據點都由其自身來表示，即當sjj＜sij對任意的j和i≠j時，cii=1。

3.3 軌跡聚類

目標函數的最優解C*不僅表示原集A中的元素被選擇用做表示，也包含了目標集B中的元素的表示成員信息表，即

對應著概率向量Bj被原集A中的每一個元素表示，用優化的最終解得到了目標集B的聚類。定義集合{A?1，A?2， ...，A?T}代表一個原集表示目標集，可以賦予Bj被Aδj表示，根據如下公式

可將目標集B分開至T個組，對應T個表示。

4 實驗結果分析

4.1 實驗數據

在實驗中，選取的數據集來自于微軟T-Drive項目［18～19］，T-Drive軌跡數據集包含2008年2月2日至 2 月 8 日期間北京內 10，357 輛出租車的 GPS 軌跡。該數據集包含了1500 萬個坐標點，軌跡的總距離達到900多萬公里。

為了降低數據的復雜性，本文選取在2008年2月2日至2008年2月8日一周內的每天相同時間片段幾組不同的100 個出租車司機移動的軌跡，并且原始的數據集數據表達是經度緯度，為了方便計算，將經緯度映射到二維坐標上，橫軸為經度，縱軸為緯度。在時間片段相同的情況下，計算軌跡之間的相似性更為準確。

4.2 實驗結果與分析

由于實驗是在一個原集上聚類，即目標集是當前原集，選取約束參數w兩組不同的值（0.2，0.8）對100 組軌跡集進行稀疏子集分析，比較原集在約束參數不同的情況下，生成表示或樣例的個數。實驗結果如圖3和圖4所示。

如圖3所示，當w=0.2時，100個軌跡集中有聚類中心T有6 個，分別是{1 2，32，54，66，85，90} ，圖中顏色越深代表此聚簇所包含的信息量越重要，原集中的元素越能很好的表示目標集。

如圖4 所示，當w=0.8 時，數據集中的聚類中心T只有3 個，分別是{9 ，32，71} ，當w越大時，原集中可以表示目標集的元素越來越少，可用來表示的信息量數量較少。

圖3 約束參數w=0.2 聚類結果

圖4 約束參數w=0.8 聚類結果

綜上所述，在稀疏子集聚類時，需要找到合適的約束參數進行對比，從原集中找出能表示重要信息的樣例來表示目標集。本文算法在保持數據集的完整性的前提下對軌跡數據進行了有效的聚類分析，得到原集中有信息量的樣例。

5 結語

本文針對現實環境下的出租車軌跡進行數分析和聚類，研究相同時間片段內一個城市中出租車移動的軌跡特征，運用稀疏子集分析密集復雜的數據集，充分利用原集自身表示的特點，降低計算的復雜度，提高聚類檢測的效率。

但是，我們的工作還存在一些需要改進的地方，比如考慮多個維度的特征向量來更精確地表示數據集，將實驗運用到不同環境下的物理軌跡數據集，因為出租車行駛軌跡比較密集和復雜，路線的規劃一般由運營公司規劃，缺少靈活性，增加原集與目標集的對比和表示，提高稀疏子集分析的正確率。