OPTICS與離線批處理在軌跡聚類中的應用

郭 雨,陳金勇,張新宇,李 梁,孫未未

(1.復旦大學 計算機科學技術學院,上海 201203; 2.中國電子科技集團公司航天信息應用技術重點實驗室,石家莊 050081)

0 概述

計算機網絡技術在各個領域的廣泛應用以及GPS定位、傳感器、衛星遙感等先進定位技術的不斷發展,形成了大量時空軌跡數據,如許多基于位置的服務(Location Based Service,LBS)應用積累了豐富的用戶出行路線與移動軌跡數據。這些大規模的數據可以弱化數據質量低下的缺點[1],使得從中提取出隱含信息并演化出新型應用成為可能。由于服務都建立在對大量時空軌跡數據簡化分析和高效提取的基礎上,因此如何高效地利用這些數據便相應成為數據分析的熱點問題。

軌跡模式挖掘是通過大量的空間軌跡分析移動物體的移動模式,其由包含特定模式的單個軌跡或具有相似模式的一組軌跡來表示。為了找到由不同運動物體共享的代表性路徑或共同趨勢,通常需要對類似的軌跡進行聚類。軌跡聚類在數據分析中發揮了至關重要的作用,因為它在揭示物體移動潛在趨勢的同時為行為模式的刻畫提供支持,并且可以用于旅行路線建議、出行模式理解以及后續位置預測等諸多方面[2-3]。

在軌跡聚類問題上,許多不同類型的聚類方法被提出應用于復雜的實際情況。文獻[4-5]為在道路監控時檢測異常車流提出的在線軌跡聚類方法,避免了傳統的“兩步聚類”,而是在獲取數據時使用樹形結構在線更新聚類結果,構建概率轉移模型以判斷異常數據。也有研究者提出對數據進行二次篩選達到降載的目的[6]。為了對受道路網絡約束的軌跡數據進行聚類,研究者又提出適應道路網絡視點的距離度量法,并將其應用于新的軌跡聚類算法[7-9]。針對隱私保護需求,文獻[10-11]對傳統軌跡聚類算法進行改進,使其能夠利用更多的信息。此外,也有將軌跡轉換為特征向量[12]、加入隱馬爾可夫模型[13-14]或者運用最長公共子序列(LCSS)進行聚類[15]的算法,且都在不同領域得到了應用。

關于適用于軌跡分析的聚類方法,研究者發現:與傳統的k-means聚類相比,基于密度的聚類算法有明顯優勢[16],例如:聚類結果可以自然擴展形成任意形狀;能夠發現任意數量的類別以更好地適應源數據;能夠很好地處理數據中的噪聲。文獻[17]提出基于密度的聚類算法TRACLUS,通過軌跡分割、聚類、生成3個步驟進行軌跡聚類并得到對應的頻繁模式。TRACLUS算法不需要考慮軌跡的時間因素,即使一些運動對象從未同時在一起移動,也有可能被分在同一組聚類。該算法不以一條完整的軌跡為單位進行聚類,而是通過軌跡分割將軌跡轉化為若干條線段,再對線段進行聚類,因此,生成的聚類結果更為靈活多變。TRACLUS的算法思想也被用于軌跡離群點檢測[18]、軌跡分類[19]以及增量聚類等工作[20]。

TRACLUS在聚類時使用傳統的DBSCAN算法,需要人為設定參數ε與MinLns,并且由于實際需求的不同,可能會得到不同疏密程度的聚類結果,此時參數的設定幾乎完全取決于工程師的經驗。同時,由于每生成一次聚類結果都需要對所有數據運行一遍完整算法,這增加了在大規模數據集上調試參數的難度。也有類似TRACLUS的算法,如文獻[21]算法,其先將軌跡分割為線段,再將線段投影至一維空間并做聚類,最后在聚類完成的線段中提取運動模式。該算法的聚類過程在一維空間中實現,避免了在二維空間中線段聚類的許多實際困難,但相應也會損失一定的可用信息。一些學者將改進的Hausdorff距離與離散Fréchet距離作為TRACLUS算法的距離度量,考慮了更多的影響因素,獲得了更有效的聚類結果[22-24],但這些嘗試都未關注運行速度的優化。

本文將OPTICS[25]這一基于DBSCAN的改進算法用于優化TRACLUS算法,同時通過引入離線批處理過程使其能夠自動給出若干可選的參數并生成對應的聚類結果,從而減少工程師在調整參數上需要花費的時間與精力。

1 形式化表示及問題定義

1.1 形式化表示

軌跡Ti是一個多維點序列,通常表示為{p1,p2,…,pli},其中,li是軌跡Ti的長度,pj是一個多維點。本文算法不使用軌跡的時間信息,因此不需要特意記錄pj的時間信息。

軌跡序列集合I是軌跡的無序集合,通常表示為{T1,T2,…,TnI},其中nI是集合中軌跡的數量。

軌跡分割針對一個線段pipj,其中pi和pj是從同一軌跡中選擇的點,通過從一條軌跡中選擇若干個點(記為n′個),取其中任意相鄰兩點可以得到共(n′-1)個軌跡分割結果。

聚類O是一個軌跡分割的集合,屬于同一個聚類的軌跡分割在設定的距離下相互接近。

代表軌跡Ri是一個多維點的序列{p1,p2,…,pl′i},其中l′i是軌跡Ri的長度,用于表示一個聚類中所有線段主要行為虛構的軌跡。

1.2 問題定義

根據給定的軌跡序列集合I,算法需要生成一個聚類的集合O={C1,C2,…,CnI},以及每個聚類對應的一個代表軌跡。

2 TRACLUS算法

TRACLUS算法分軌跡分割、聚類和生成3個子部分進行軌跡聚類[17]。首先應用最小描述長度(MDL)原理,將原序列分解成代表原軌跡序列的特征線段集合;然后通過DBSCAN得到線段的聚類;最后對每一個聚類生成一個對應的代表軌跡。算法第一部分軌跡劃分的時間復雜度為O(N),第二部分線段聚類的時間復雜度為O(N2),如果使用合理索引如R-tree,可將時間復雜度降至平均O(NlogaN),第三部分特征軌跡的生成需要經過排序,因此,復雜度為O(NlogaN)。顯然,在不使用高效的索引時,第二部分為整個算法的復雜度瓶頸,達到了O(N2),而當使用高效的索引時,雖然第二和第三部分復雜度一致,但由于復雜度常數上R-tree遠大于排序,因此第二部分依然是整個算法的瓶頸。

此外,由于DBSCAN包含2個人為控制的參數MinLns與ε,分別代表鄰域內的對象個數與鄰域大小,用于共同決定鄰域的密度。它們的確定需要依靠數據分析任務的實際需求和數據分析工程師的經驗,但實踐中工程師可能會在這其中耗費大量無意義的時間而又難以保證其設置的合理性。為了在大規模數據上運用該算法,本文將對該部分進行優化。

由于本文的目的在于對TRACLUS算法第二部分(使用DBSCAN對線段進行密度聚類)的優化,因此算法第一部分(軌跡分割)與第三部分(代表軌跡的生成)[17]的具體實現本文不再贅述。

3 聚類算法優化

3.1 基于OPTICS的密度聚類優化

DBSCAN存在一個一般化的改進版本,被稱為OPTICS[25]。OPTICS并不直接生成數據集聚類,而是先為聚類分析生成一個有序排列,再對比有序排列進行后續處理以得到聚類結果。這個有序排列代表了各樣本點基于密度的聚類結構,數據越接近,越有可能被分在同一聚類的樣本,在排列中的位置就越靠近。以樣本點輸出次序為橫軸,以可達距離為縱軸,可通過實驗得到如圖1所示的輸出結果。

圖1 OPTICS有序排列輸出結果

樣本的聚類在圖1中體現為低谷,當以參數ε2為閾值時,有序排列被劃分為3個小于ε2的低谷,每個低谷對應一個樣本聚類;而當以更小的參數ε1為閾值時,有序排列被劃分為多個小于ε1的低谷,同樣一個低谷對應一個樣本聚類。因為在對多個不同的參數ε生成聚類時,所使用的有序排列是完全相同的,所以如果根據有序排列生成聚類的運行時間小于傳統DBSCAN算法的運行時間,那么當ε閾值數量增多時,算法的運行速度就會得到改善。

傳統DBSCAN算法[26]十分經典,本文不再贅述。OPTICS在DBSCAN的基礎上,增加了核心距離和可達距離[25]2個新的定義:

定義1(核心距離) 一個對象p在參數ε與MinLns下的核心距離,等于其第MinLns近的對象到對象p的距離。如果對象p的ε鄰域中對象個數小于MinLns,那么對象p在參數ε與MinLns下的核心距離為UNDEFINED。

定義2(可達距離) 對象o和對象p在參數ε與MinLns下的可達距離為max(核心距離(o),distance(o,p))。如果對象p的ε鄰域中對象個數小于MinLns,那么對象p在參數ε與MinLns下的可達距離為UNDEFINED。

生成有序排列的函數偽代碼如下:

算法1ExpandClusterOrder

輸入objects[]

輸出ResultList[],ReachDist[],CoreDist[]

Initialize:

Visited[]=[false]

temp=1

while temp<=objects.size do

m=null

i=1

while i<=objects.size do

if visited[i]==false then

m=i

end if

end while

visited[m]=true

ResultList[temp]=m

CoreDist[m]=FindMinLnsthDistance()

for each i in EpsNeighborhood(m) do

ReachDist_=max(CoreDist[m],dist(i,m))

if ReachDist[i]>ReachDist_ then

if visited[i]==false then

ReachDist[x]=ReachDist_

end if

無線數據與能量協同傳輸技術：編碼與調制設計………………………………………………胡杰，金石 24-5-43

end if

end for

temp=temp+1

end while

ExpandClusterOrder函數每次選擇一個未被選擇的對象m,且滿足ReachDist[m](之前已被選擇的對象到對象m的最近距離)為最小值。將對象m添加到結果序列,并標注其已被選擇。FindMinLnsthDistance()函數會計算對象m的核心距離,隨后枚舉對象m的ε鄰域,用m到其他對象的可達距離更新ReachDist數組。如此循環直到所有對象都被選擇。

根據定義1與定義2可知,OPTICS使用的參數ε是一個限制鄰域大小上限的寬松上界,過大的參數ε僅可能拖慢運行時間,而不會影響之后生成的聚類質量。如果將參數ε設置為正無窮,那么核心距離與可達距離均不會出現UNDEFINED,此時需要枚舉所有對象對并計算它們的間距以得到核心距離并更新可達距離,復雜度退化到O(N2),與不使用高效空間索引的DBSCAN相同。如果根據實際需求確定了參數ε的上限(并不需要十分精確),那么OPTICS也可以使用高效空間索引,在O(logaN)的時間內得到第MinLns近的對象并更新鄰域的可達距離,從而將總的時間復雜度降低到O(NlogaN)。因此,相對于DBSCAN而言,OPTICS的時間復雜度并沒有增加,參數ε設置不再敏感。

3.2 基于有序排列的聚類

雖然已經獲得了對聚類元素的有序排列,但為了得到最終需要的密度聚類結果,仍需要對此排列進行分析。如果已知一個DBSCAN參數ε的取值,通過算法2可以得到對應的密度聚類結果。

輸入ResultList,ReachDist,CoreDist

輸出mark[]

Initialize:

mark[]=[UNCLASSIFIED]

clusterID=0

i=1

while i<=ResultList do

x=ResultList[i]

if ReachDist[x]>eps then

if CoreDist[x]<=eps then

clusterID=clusterID + 1

mark[x]=clusterID

else

mark[x]=NOISE

end if

else

mark[x]=clusterID

end if

end while

ExtractDBSCANClustering函數依序枚舉有序排列中的每一個對象,如果當前被枚舉對象x的可達距離小于參數ε,那么將對象x與前一個對象合并到同一個聚類中;否則,如果對象x的核心距離小于參數ε,則將對象x標記為一個新的聚類。當可以合并時,將對象x與其前一個對象合并是合理的[25],具體證明此處不再贅述。由于ExtractDBSCANClustering函數只對有序排列進行一次掃描,因此時間復雜度為O(N)。

3.3 參數ε的生成

使用OPTICS替代DBSCAN用于密度聚類,可以大幅縮短多組參數存在時的運行時間,但在ExtractDBSCANClustering階段依然需要手動指定參數ε。如果能夠根據中間結果自動生成可供參考的參數ε,則能大幅減少參數調整的工作量。

考慮密度聚類中參數ε的定義[26],即用于確定聚類對象的鄰域大小,聚類對象間的距離整體越大,通常就需要越大的鄰域用以判斷疏密(過小的鄰域將難以包含足夠的對象以至于隨機性過大),而聚類對象間的距離整體越小,就需要越小的鄰域(過大的鄰域將包含過多的對象以至于密度趨近于整體平均密度,從而失去代表性)。

通過分析算法2可以發現,兩個相鄰的對象是否被合并到同一個聚類,僅與它們的可達距離有關,而核心距離僅影響了在未被合并時是否將其判斷為噪聲。因此,參數ε與聚類對象可達距離的分布有關。可達距離的分布示例如圖2所示,其中橫軸為可達距離,縱軸為等于可達距離的聚類對象數量。

圖2 聚類對象可達距離分布

本文用正態分布擬合此分布,并計算N等分點的數值(N為任意設定的整數),將它們作為一系列可選的參數ε返回。雖然越靠近邊界(如10%與90%處)的數值通常被需要的可能性越小,但本文依然將其作為參數納入考慮,因為ExtractDBSCANClustering的時間復雜度僅為O(N),相對于ExpandClusterOrder的時間復雜度O(N2)或O(NlogaN)顯得微不足道。

3.4 離線批量聚類

OPTICS算法的ExtractDBSCANClustering函數運行一次只能對一組參數生成對應的聚類結果,面對需要對多組參數分別生成聚類結果的需求,仍有一定的優化空間。

上文3.2節已經提到,在OPTICS的有序排列中相鄰的兩個對象,后者或者與前者合并到同一個聚類,或者成為一個新的聚類,或者成為噪聲。如果將噪聲視為僅含有一個對象的聚類(在正常的密度聚類中,不會出現只含有一個對象的聚類,它無法擴展也無法被擴展,因此沒有分析意義),那么相鄰的兩個對象是否被合并僅與可達距離有關。隨著參數ε的逐漸增大,可達距離越小的對象將會越早被合并,已經被合并到同一個聚類內的對象不會再被拆分至兩個聚類。如圖1所示,在參數ε從ε1逐漸增加的過程中,原先被幾個峰分隔的許多個聚類逐漸合并,直至增加到ε2時只剩下3個聚類。

正是由于只存在集合合并的操作,并查集很適合被用于維護這些聚類之間的關系。在將可達距離與參數ε按升序排序后,當參數ε增大后,小于參數ε的可達距離也相應增加,只需要將這些新增的相鄰對象合并,即可得到對應新參數ε的聚類結果。上述操作的算法偽代碼如下:

算法3offlineExtractClustering

輸入ResultList,ReachDist

輸出cluster[]

Initialize:

DistList=sort(ReachDist)

i=1

while i<=size do

mark[i]=i

end while

cur=1

for each eps in EpsList do

cur=RenewClustering(cur,eps,DistList)

cluster[eps]=mark

end for

算法4RenewClustering

輸入cur,eps,DistList

輸出cur

while cur

if DistList[cur]>eps then

break;

end if

x=DistList[cur].from

mark.merge(x,x-1)

cur=cur+1

end while

上述代碼對ReachDist數組進行從小到大排序,并存儲在DistList數組中。從小到大枚舉每一個候選的ε,每次調用RenewClustering函數以更新mark數組。RenewClustering 函數從當前cur位置開始掃描DistList內的對象,如果當前對象的ReachDist小于參數ε,那么說明對應的位置需要進行一次合并,調用并查集merge函數。如果可達距離大于參數ε,那么之后的可達距離也均大于ε,此次更新就到此結束,返回移動后的cur。

可以看到,該部分對所有待計算的ε取值都計算出了對應的聚類結果,且所有對象僅被單調掃描了一次,因此其復雜度為O(αN)(其中α為并查集效率常數)。而在傳統OPTICS的ExtractDBSCANClustering過程中,該部分的復雜度為O(運行次數×N)。

3.5 時間復雜度分析

傳統TRACLUS算法時間復雜度瓶頸在第二部分的線段密度聚類上,因為使用了DBSCAN,所以在對多組不同的參數進行密度聚類時,時間復雜度為O(參數組數×N2),即使使用了合理的空間索引,時間復雜度也為O(參數組數×CNlogaN)(其中C為空間索引帶來的巨大常數)。當數據規模較大且參數組數較多時,未經優化的算法會嚴重拖長運行時間。

經過優化后,DBSCAN被OPTICS替代,原本對每組參數需要掃描所有數據并計算它們的間距,現在可以一次完成,復雜度降為O(CNlogaN+參數組數×N),其中前部分是生成有序排列的代價,后部分是從排列中對每組參數生成對應聚類結果的代價。經過離線批處理優化,從有序排列生成對應聚類結果的過程被進一步合并,復雜度降為O(CNlogaN+αN+參數組數)(其中α為并查集的時間復雜度常數,通常小于5)。可以發現,優化后第二部分的時間復雜度幾乎不受參數組數影響,這在需要對多組參數進行計算的情況下是較大的改進。

4 實驗與結果分析

本文實驗環境為單個計算機,處理器型號 Intel(R) Core(TM) i5-4690K CPU @ 3.50 GHz,內存大小為16 GB,操作系統為 Win10(64位),使用相同軟件環境。

本文在Starkey項目提供的1995年鹿類動物遷徙軌跡數據集(http://www.fs.fed.us/pnw/starkey/data/tables/)上進行對比實驗,該數據集是相關問題的經典數據集,TRACLUS原論文也在該數據集下進行實驗。實驗結果表明,在生成相同質量聚類結果的同時,本文所提出的優化算法花費時間小于原算法,由此說明本文的優化確實對其有所改進。為了對比,2種算法都沒有使用諸如R-tree數據結構等額外的優化結構。

2種算法一次性生成N張聚類結果所需要消耗的時間比較如表1所示(當參數ε組數N大于33時,傳統TRACLUS算法的運行時間過長,不再具有比較的意義)。可以看出,TRACLUS所花費的時間與參數ε組數近似呈正比例關系,而使用離線與OPTICS優化后的TRACLUS,雖然在僅有一組ε參數時花費的時間高于TRACLUS(因為有更大的常數),但隨著參數ε的取值數量增長,算法運行的時間增長緩慢,遠低于直接使用TRACLUS進行聚類的耗費。正如之前的分析,改進后的算法節省了大量重復計算過程,在同時對多組ε參數進行計算時具有明顯的速度優勢。

表1 多組參數情況下的聚類時間比較

可以看出,因為TRACLUS的第三部分仍要對聚類結果進行再加工,所以優化后的算法聚類時間依然隨著參數ε組數增加而保持緩慢增長,但這個增長十分緩慢,以至于生成對應81組參數的聚類結果所花費的時間,也未超過生成對應1組參數的聚類結果所花費時間的兩倍。

5 結束語

本文運用OPTICS算法與離線批處理技術改進TRACLUS軌跡聚類算法。優化后的算法從需要兩個外部參數降低到僅需要其中一個,即能夠自動生成可供參考的參數組并輸出對應多種密度的聚類結果,同時只額外消耗極少的時間,從而提高效率。實驗結果表明,在最優參數未知需要對多組參數進行軌跡聚類時,改進算法在運行速度上較原算法具有明顯優勢。本文僅對TRACLUS的密度聚類部分進行改進,在未來工作中,將對軌跡劃分和代表軌跡生成部分進行優化,進一步提升軌跡聚類的效率及質量。