基于稀疏子集分析的軌跡聚類發(fā)現(xiàn)*

薛 璇 陳平華

（廣東工業(yè)大學計算機學院 廣州 510006）

1 引言

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

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

2 相關工作

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

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

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

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

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

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

圖1 算法模型框架

3.1 構(gòu)建特征矩陣

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

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

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

圖2 網(wǎng)格S

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

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

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

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

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

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

給定N條軌跡，構(gòu)建N×N相似度矩陣D，

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

3.2 稀疏子集分析

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

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

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

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

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

3.3 軌跡聚類

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

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

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

4 實驗結(jié)果分析

4.1 實驗數(shù)據(jù)

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

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

4.2 實驗結(jié)果與分析

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

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

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

圖3 約束參數(shù)w=0.2 聚類結(jié)果

圖4 約束參數(shù)w=0.8 聚類結(jié)果

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

5 結(jié)語

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

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