多粒度時空事件序列相似度算法研究

汪成亮， 黃利瑩， 趙凱

(重慶大學(xué) 計算機學(xué)院，重慶 400044)

隨著無線通信技術(shù)、嵌入式技術(shù)等技術(shù)的不斷發(fā)展，智能環(huán)境也進入了飛速發(fā)展階段，它在環(huán)境監(jiān)測、智能家居、醫(yī)療護理等方面[1-3]得到了廣泛的應(yīng)用. 智能環(huán)境下經(jīng)過處理可以得到用戶大量的日?；顒邮录蛄袛?shù)據(jù)，包括活動類型、活動開始時間與結(jié)束時間、位置信息等，對這些事件序列進行相似度度量，可以聚類分析出行為相似的用戶、進行用戶行為異常檢測、查詢與給定序列相似的其他行為序列等，將其與健康醫(yī)療或智能推薦等領(lǐng)域[4-7]相結(jié)合，為用戶提供個性化信息服務(wù)，用以改善用戶的日常生活.

當(dāng)前，關(guān)于用戶行為分析的研究之一就是用戶行為相似度計算，主要集中于不帶有時間空間信息或帶有固定時間空間信息的活動序列相似度計算，本文認(rèn)為僅僅從單一層次來計算時空事件序列相似度是不夠的，難以準(zhǔn)確地進行相似度度量. 例如，如圖1所示，利用現(xiàn)有的活動序列相似度計算方法，事件序列1與事件序列2顯然相似性不高，但若放大空間層次和活動層次，如圖2所示，則事件序列1與事件序列2的相似性明顯高于圖1所示. 因此，需要從不同的粒度對時空事件序列進行相似度比較.

圖1 事件序列相似性比較Fig.1 Similarity comparison of event sequences

圖2 調(diào)整空間和活動層次后的事件序列相似性比較Fig.2 Similarity comparison of event sequences after adjusting spatial and activity levels

與本文相關(guān)的工作主要是事件序列相似度計算方面. 關(guān)于事件序列的相似性度量，目前已經(jīng)有了一定的研究成果. Banerjee等[8]把兩序列的交叉程度作為其相似性的度量標(biāo)準(zhǔn), 采用兩個序列的最大共同子序列LCS表示序列的距離；Mannila等[9]用編輯距離表示兩序列的相似度，其基本思想是：兩序列的相似性反映為把一個序列轉(zhuǎn)換成另一序列的工作量. 然而以上方法僅處理純粹的定性信息，如字母，而不能處理帶有時間、空間信息的序列. Ying等[10]提出語義軌跡模式相似度方法來度量兩個軌跡之間的相似性，該方法將軌跡轉(zhuǎn)化為具有語義標(biāo)簽的位置序列，通過最長公共子序列計算兩個序列的相似度，但該方法忽略了時間、活動信息，僅考慮空間相似度；Sajimon Abraham等[11]提出時空相似度算法TraSimilar來度量用戶軌跡相似度，該方法將原始軌跡數(shù)據(jù)中的空間信息視為一組序列，利用序列比對方法測量軌跡之間的空間相似度，然后再求兩條軌跡中對應(yīng)相同空間位置的時間距離，將時間相似度定義為時間距離的倒數(shù)；Yuan等[12]提出了時空編輯距離方法來衡量用戶軌跡之間的相似度，該方法擴展了傳統(tǒng)編輯距離算法的成本函數(shù)，以便結(jié)合空間和時間因素. 以上方法比較的是帶有固定時間空間信息軌跡之間的時空相似度，忽略了時間、空間信息的多尺度表達，且沒有考慮活動之間的相似度.

NW算法[13]廣泛應(yīng)用于序列比對，但該算法僅是對字符之間的簡單比較，無法準(zhǔn)確高效地對時空事件序列進行相似性比較，因此，本文對NW算法進行了改進，提出了多粒度時空序列比對算法MGSSA，實現(xiàn)了從不同的層次計算時空序列相似度，最后理論分析和實驗驗證表明了該算法的有效性. 與NW算法相比，本文提出的MGSSA算法在一般情況下，度量時空事件序列相似度的效率和語義完整性均優(yōu)于NW算法.

1 相關(guān)概念

1.1 時空事件、時空事件序列

給定活動類型集合E={e1,e2,…,en}，n為活動類型總數(shù)，時空事件表示為一個三元組event=(t,e,p)，其中，t=(tstart,tend)，tstart為事件的開始時間，tend為事件的結(jié)束時間；e為活動類型集E中的某個事件；p為事件發(fā)生時用戶所在的位置. 時空事件具有多粒度的特性. 時空事件序列表示為L={event1,event2,…,eventn}，其中n為時空事件序列中事件的總數(shù).

1.2 粒度

時空事件具有多粒度[14]的特性，下面分別對活動粒度、空間粒度、時間粒度進行定義.

定義1活動粒度：在智能環(huán)境下，對通過傳感器檢測或識別到的活動進行多層次的分類(如圖3所示)，則每一層次稱為一個活動粒度，一個活動粒度表示為AG(i)(i表示活動粒度的個數(shù)).

圖3 活動粒度Fig.3 Activity granularity

定義2空間粒度：設(shè)R為智能環(huán)境區(qū)域(如圖4所示)，在R內(nèi)有n個互不相交的子區(qū)域p(i)?R(1≤i≤n)且p(i)∩p(j)=?(1≤i,j≤n),p(i)被稱為是一個空間粒，則所有p(i)(1≤i≤n)空間粒構(gòu)成的即為一個空間粒度，一個空間粒度表示為SG(i)(i表示空間粒的個數(shù)). 圖4中，智能環(huán)境區(qū)域經(jīng)過一次劃分所得的子區(qū)域p(1)～p(4)各為一個空間粒，所有的p(i)空間粒構(gòu)成一個空間粒度，每個子區(qū)域p(i)再次進行劃分得到子區(qū)域p(i1)～p(i4)，所有的p(in)空間粒構(gòu)成另一個空間粒度，依此類推到其他各空間粒度.

圖4 空間粒度Fig.4 Spatial granularity

定義3時間粒度：設(shè)T=[t0,tn]是時間域,T內(nèi)有n個互不相交且時間間隔相同的時間區(qū)間：t(i)=[ti1,ti2],t(j)=[tj1,tj2],(t0≤ti1

圖5 時間粒度Fig.5 Temporal granularity

1.3 事件時間關(guān)系

傳統(tǒng)的序列挖掘中的事件很多都是瞬時事件，這樣事件的發(fā)生關(guān)系很簡單. 而對于帶有時間間隔的事件來說，因為每個事件都有兩個時間點，事件間的關(guān)系就要復(fù)雜得多，下面就對時間間隔事件間的關(guān)系表達[15]做詳細(xì)的介紹.

對于兩個事件event1、event2的關(guān)系來說，本文定義以下幾種關(guān)系模式，在定義中默認(rèn)為event1在event2之前發(fā)生，即tstart(event1)≤tstart(event2).

①NoOverlap(event1,event2)：表示事件event2在event1結(jié)束時或結(jié)束之后發(fā)生，即tend(event1)≤tstart(event2).

②Overlap(event1,event2)：表示事件event1與事件event2發(fā)生的時間上有重疊，即tstart(event1)≤tstart(event2)，tend(event1)>tstart(event2)且tend(event1)

③Contain(event1,event2)：表示事件event1包含事件event2，即tstart(event1)≤tstart(event2)，tend(event1)>tend(event2)或tstart(event1)

④Equal(event1,event2)：表示事件event1與event2同時發(fā)生并且同時結(jié)束，即tstart(event1)=tstart(event2)且tend(event1)=tend(event2).

但是在現(xiàn)實生活中事件發(fā)生的時間并非十分精確，如有的開始結(jié)束時間可能精確到小時，有的可能精確到分、秒. 這樣就使事件界限的定義模糊不清，也使得事件間的關(guān)系定義模糊不清. 于是，本文接著通過加入時間限制方法，將上述定義的4種關(guān)系模式轉(zhuǎn)化為下面所示的4種關(guān)系，可以看出，關(guān)系定義的基本概念是相同的，只是加入了一個時間限制值，當(dāng)時間差超過這一限制時，兩個事件之間的關(guān)系才成立.

給定一個閾值th(th>0)，th對于不同的關(guān)系定義是不同的. 那么上述4種關(guān)系可以重新定義如下：

①NoOverlap(event1,event2)：tstart(event2)-th≤tend(event1)≤tstart(event2)+th或tend(event1)+th≤tstart(event2). 說明：在一些情況下，如果兩個事件的間隔時間太長，那么這個“NoOverlap”關(guān)系是沒有意義的，所以設(shè)置一個最大時間差tmax，當(dāng)tstart(event2)-tend(event1)>tmax時，兩個事件“NoOverlap”關(guān)系不成立，即兩個事件沒有任何關(guān)系.

②Overlap(event1,event2)：tstart(event1)+th≤tstart(event2)，tend(event1)+th≤tend(event2).

③Contain(event1,event2)：tstart(event1)+th≤tstart(event2)，tend(event1)≥tend(event2)+th或tstart(event1)+thtend(event2)+th或tstart(event2)-th≤tstart(event1)≤tstart(event2)+th，tend(event1)

④Equal(event1,event2)：tstart(event2)-th≤tstart(event1)≤tstart(event2)+th且tend(event2)-th≤tend(event1)≤tend(event2)+th.

1.4 序列比對Needleman-Wunsch算法

NW算法是基于動態(tài)規(guī)劃的全局最優(yōu)比對算法，能夠找出序列的最優(yōu)比對并計算其最大相似性.

序列之間字符可能匹配、不匹配或匹配gap(由插入或刪除操作產(chǎn)生)，NW算法定義了一個字符得分系統(tǒng)，可以針對不同的情況設(shè)計不同的得分系統(tǒng)，設(shè)字符x與y進行比較時的得分函數(shù)W(x,y)為

(1)

NW算法將兩個序列a,b變成等長序列，不等長則用gap補足，形成一個二維矩陣，矩陣的單元是計算得出的對應(yīng)子序列的相似度值. 用S(i,j)表示矩陣單元的值，則序列a和序列b的全局最優(yōu)比對可表示為

S(i,j)=

(2)

根據(jù)式(2)可以計算出矩陣中每個單元格的分?jǐn)?shù)，最后即可得到完整的序列比對后的相似度矩陣. 矩陣右下角的相似度值最大，從矩陣右下角回溯至左上角，即可得到序列最優(yōu)比對的結(jié)果.

2 多粒度時空序列相似度計算

本文提出了一種基于NW算法的多粒度時空序列比對算法(multi-granularspatiotemporalsequencesalignment,MGSSA)，通過將空間和時間信息結(jié)合到得分函數(shù)中來改進傳統(tǒng)的NW算法. 并能通過粒度調(diào)控來從不同粒度對時空序列進行相似性比較.

2.1 時空事件相似度及時空事件可比性

算法NW是從序列第一個到最后一個，一個一個進行比較，一條序列比個遍，然后得出最優(yōu)解，僅僅是對兩個字符串的最優(yōu)比較. 然而，對于此問題，即計算兩個時空事件序列的相似度，而不是序列的最優(yōu)比較得分，且時空事件序列不僅包含活動信息，還包含時間、空間信息，所以基于NW算法的得分函數(shù)，提出了時空事件相似度計算公式如下.

定義4時空事件相似度：eventi=(ti,ei,pi)和eventj=(tj,ej,pj)是時空事件序列L中的兩個時空事件，那么eventi和eventj的相似度計算公式如下：

w(eventi，eventj)=

(3)

式中:Sactivity表示兩個事件eventi,eventj比較的活動相似度；Stime表示兩個事件eventi,eventj比較的時間相似度；Sspace表示兩個事件eventi,eventj比較的空間相似度；u1、u2、u3分別為Sactivity、Stime、Sspace對應(yīng)的相似度權(quán)重，用來調(diào)整對活動相似度、時間相似度、空間相似度的敏感度，且u1+u2+u3=1；d1、d2為自定義得分值.

此外，基于時間相關(guān)性的考慮，如早上發(fā)生的事件與晚上發(fā)生的事件進行比較是沒有多大意義的. 因此，不需要從序列的第一項一直比較到最后一項，只需要將一個序列中的事件eventi和另一序列中與eventi滿足時空事件可比性的連續(xù)事件集進行比較即可. 序列可比性定義如下：

定義5時空事件可比性：已知兩個時空事件序列L1={event11,event12,…,event1n}與L2={event21,event22,…,event2n}，對于L1中任意一項event1i(1≤i≤n),若L2序列中存在連續(xù)事件event2j,event2(j+1),…,event2(j+a)(0≤a≤m-1,1≤j≤m-a)，都滿足關(guān)系Overlap(event1i,event2(j+a))、Contain(event1i,event2(j+a))、Equal(event1i,event2(j+a))、NoOverlap(event1i,event2(j+a))中的任意一種關(guān)系，則稱L1中的事件event1i與L2中的連續(xù)事件event2j,event2(j+1),…,event2(j+a)具有時空事件可比性. 且序列L1中的事件event1i的下一事件event1(i+1)只需和L2中以事件event2j開始的事件逐一進行比較，而不用從序列L2的第一項開始比較.

基于此思想改進之后，序列進行的比較次數(shù)減少，改善了算法效率，而且還更符合實際意義.

2.2 時空序列相似度及多粒度時空序列相似度求解算法

基于NW算法的全局最優(yōu)比對及時空事件相似度計算公式，下面給出時空事件序列相似度的定義.

定義6時空序列相似度：對于兩個時空事件序列L1={event11,event12,…,event1n},L2={event21,event22…,event2n}，有序列Li={event11,event12,…,event1i}與Lj={event21,event22,…,event2j}(Li?L1,Lj?L2)的比較得分S(i,j)計算公式如下.

S(i,j)=

(S(0,0)=0)

(4)

通過公式可以求得時空序列相似度得分矩陣M，得分矩陣的最后一行最后一列數(shù)值即為兩個時空序列L1、L2的相似度值. 具體求解過程如下.

算法1：多粒度時空序列比對算法MGSSA

Input:Spatiotemporal event sequenceL1andL2,activity granularityi1, temporal granularityi2, spatial granularityi3;

Output:Similarity ofL1andL2;

Initialization:Set score matrixMto 0;

1:fori=0 to |L1| do

2:temp=0;

3: forj=0 to |L2| do

4: ifL1[i] andL2[j] satisfy the relationship of Contain, Overlap, Equal or NoOverlap

5: if(temp==0)

6: temp=j;

7: ifL1[i].activity andL2[j].activity belong to a class

8: if simactivity[i1]!=0

9: simactivity[i1]=MGAS(L1[i].activity,L2[j].activity,i1);

10: if simtime[i2]!=0

11:simtime[i2]= MGTS(L1[i].time,L2[j].time,i2);

12: if simposition[i3]!=0

13:simposition[i3]=MGSS(L1[i].position,L2[j].position,i3);

14: sim=u1simactivity[i1]+u2simtime[i2]+u3simposition[i3];

15:M[i][j]=max(M[i-1][j-1]+sim,M[i-1][j]+d2,M[i][j-1]+d2);

16: else

17:M[i][j]=max(M[i-1][j-1]+d1,M[i-1][j]+d2,M[i][j-1]+d2);

18:j=temp;

19:returnM[|L1|-1][|L2|-1];

該算法通過時空事件可比性的思想，減少序列事件的比較次數(shù)，通過分別求給定粒度下的活動、時間、空間相似度來度量事件的相似度，將每次求得的某種粒度下的活動、時間、空間相似度保存起來，當(dāng)改變粒度時可以減少重復(fù)計算，提高算法效率. 下面具體介紹算法MGAS(multi-granularity activity similarity)、MGTS(multi-granularity time similarity)、MGSS(multi-granularity spatial similarity).

多粒度活動相似度算法MGAS，描述如下.

算法2：多粒度活動相似度算法MGAS

Input:Activity typese1ande2of the spatiotemporal eventevent1andevent2in the sequence and the given activity granularity i;

Output:Activity similaritySactivityofevent1andevent2;

Initialization:The multi-way tree of activity type and a hashtable;

1:Find the nodes ofe1ande2in the multi-way tree, let them beaandb;

2: if Node(a,1)=Node(b,1) ∥the Node(x,y)indicates the yth parent of nodex

3: Find the ith parent nodes Node(a,i)and Node(b,i)ofaandb;

4: ifa.level<=i

5: Node(a,i)=a;

6: ifb.level<=i

7: Node(b,i)=b;

8: if Node(a,i)=Node(b,i)

9:Sactivity=1;

10: else ifa.level=b.level

11: Let num be be equal to the number of common nodes from the root node toaandb;

12:Sactivity=num/a.level;

13: else ifa.level≠b.level

14: maxlevel=max(a.level,b.level);

15: Let num be equal to the number of common nodes from the root node toaandb;

16:Sactivity=num/maxlevel;

17: returnSactivity;

算法2基于活動多叉樹和通過整棵樹構(gòu)造出的一個哈希表. 由時空事件可比性的定義判斷事件是否可比，然后判斷兩個事件的活動類型是否屬于同一大類，滿足以上兩個條件的事件項根據(jù)給定活動粒度來求活動相似度，實現(xiàn)了從多種粒度來求活動相似度. 由于構(gòu)造了哈希表，該算法空間復(fù)雜度較大，查找的時間復(fù)雜度為O(1).

對可求出活動相似度的兩個事件求時間相似度、空間相似度. 在提出多粒度時間相似度算法之前，先給出事件時間關(guān)系權(quán)重的定義.

由于事件時間關(guān)系對兩個事件的時間相似度是有影響的，根據(jù)事件時間關(guān)系的定義，下面給出事件時間關(guān)系權(quán)重定義.

定義7事件時間關(guān)系權(quán)重：若event1和event2為時空事件序列中的兩個時空事件，這兩個事件發(fā)生的時間信息分別為t1和t2，則這兩個時空事件的事件時間關(guān)系權(quán)重RV(t1,t2)計算公式如下.

(5)

多粒度時間相似度算法MGTS描述如下.

算法3：多粒度時間相似度算法MGTS

Input:Time informationt1andt2of the spatiotemporal eventevent1andevent2in the sequence and the given temporal granularityi;

Output:Time similarityStimeofevent1andevent2;

1:ifevent1andevent2satisfy the relationship of Contain, Overlap or Equal

2: Divide the time axis according to the given granularityi, and number from 1, thent1andt2can be represented by digital sequencel1andl2;

3: Calculate the longest common subsequenceLCS(l1,l2) of sequencel1andl2;

4:Si=|LCS(l1,l2)|/(|l1|+|l2|-|LCS(l1,l2)|);

5:Stime=Si*RelationshipValue(t1,t2);

6:else ifevent1andevent2satisfy the relationship of NoOverlap

7:Stime=1;

8:else

9:Stime=0;

10:returnStime;

算法3基于給定的某一粒度，將時間軸劃分并編號，通過最長公共子序列LCS算法求出時間相似度，實現(xiàn)了以多種粒度來求時間相似度. 最長公共子序列算法經(jīng)過優(yōu)化后，時間復(fù)雜度為O(nlogn)，所以算法3的時間復(fù)雜度為O(nlogn).

多粒度空間相似度算法MGSS描述如下.

算法4：多粒度空間相似度算法MGSS

Input:Spatial informationp1andp2of the spatiotemporal eventevent1andevent2in the sequence and the given spatial granularityi;

Output:Spatial similaritySspaceofevent1andevent2;

Initialization:The multi-way tree of position and a hashtable;

1:Find the nodes ofp1andp2in the multi-way tree, let them beaandb;

2:Find the ith parent nodesNode(a,i) andNode(b,i) ofaandb;

3:ifNode(a,i)=Node(b,i)

4:Sspace=1;

5:else

6.Sspace=0;

7:returnSspace;

算法4基于空間類型多叉樹和其構(gòu)造的哈希表，同樣也可從多種粒度來求空間相似度. 該算法的時間復(fù)雜度為O(1).

3 實驗評估

本文主要對產(chǎn)生時空事件序列的仿真環(huán)境進行簡單介紹、對提出的多粒度時空序列比對算法MGSSA進行有效性驗證，并將其與NW算法進行時間復(fù)雜度和相似度準(zhǔn)確率的對比，最后將其作為距離度量方法來進行聚類分析. 實驗采用的硬件環(huán)境為Win7操作系統(tǒng)，程序基于Visual Studio、Matlab平臺和C++、Matlab語言實現(xiàn).

3.1 仿真環(huán)境介紹

本文的實驗數(shù)據(jù)是通過本團隊自行開發(fā)的智能環(huán)境仿真系統(tǒng)(smart environment simulator tool)[16]產(chǎn)生的，在該系統(tǒng)下可導(dǎo)入某個實際環(huán)境的布局，從而在其中放置智能節(jié)點，并對其中的兩兩智能節(jié)點進行連接，從構(gòu)成智能節(jié)點網(wǎng)絡(luò)，如圖6所示.

圖6 仿真環(huán)境展示Fig.6 Demonstration of smart environment simulator tool

3.2 MGSSA算法實驗有效性驗證

本實驗通過序列可視化方法來對多粒度時空序列比對算法進行有效性驗證，如表1所示.

表1 序列可視化

為了驗證有效性，本文做了4組實驗，實驗結(jié)果如表2所示，圖7(a)以初始粒度顯示了3條不同的序列，可以看出3條序列相似度較低. 改變空間粒度為SG(2)，3條序列如圖7(b)所示，從圖7(b)可以看出L1與L2的軌跡相同，而L3則與L1、L2相異. 再次改變空間粒度為SG(1)，3條序列如圖7(c)所示，可以看出3條序列軌跡都相同. 在圖7(c)的基礎(chǔ)上改變活動粒度如圖7(d)所示，可以看出不同事件序列之間，事件的活動類型大致相同，即原本不同的序列其實可以看作是同一序列.

表2 實驗結(jié)果

圖7 不同空間粒度、活動粒度對比Fig.7 Comparison of different spatial granularity and activity granularity

以上說明在不同的粒度下，時空序列之間的相似度也是不同的，序列的相似度是隨著粒度的變化而變化的，在某一種粒度下序列之間差異大，而改變粒度后則可看作是相同的序列.

3.3 MGSSA算法與NW算法對比

3.3.1時間復(fù)雜度

不進行粒度調(diào)整時，NW算法是從序列第一項到最后一項，一項一項進行比較，一條序列比個遍，所以NW算法的時間復(fù)雜度為O(n2). MGSSA算法根據(jù)序列項的可比性的思想，使得序列項的比較次數(shù)大大減少，改善了算法效率，所以從序列事件項的比較次數(shù)來看MGSSA算法優(yōu)于NW算法. 但是MGSSA算法時間復(fù)雜度由序列事件項的比較次數(shù)和求解事件項相似度共同決定，求解事件項相似度方法的時間復(fù)雜度主要由多粒度活動、時間、空間相似度算法決定，所以MGSSA算法的最壞時間復(fù)雜度為O(n2logn).

在進行粒度調(diào)整時，MGSSA算法根據(jù)已有的計算結(jié)果可以快速調(diào)整出結(jié)果，即無需重新計算活動相似度、時間相似度或空間相似度，所以MGSSA算法的最好時間復(fù)雜度為O(n). 而NW算法每次則需要重新進行計算. 下面基于大量仿真得到的序列對兩種算法進行運行時間比較實驗，實驗結(jié)果如圖8所示，可知當(dāng)時空事件序列數(shù)量為10、100、1 000時，MGSSA算法的平均運行時間均要少于NW算法，所以從平均時間復(fù)雜度對比結(jié)果來看，MGSSA算法要優(yōu)于NW算法.

圖8 MGSSA與NW算法的平均運行時間對比Fig.8 Comparison of average running time between MGSSA and NW

3.3.2語義完整性

NW算法僅是對字符之間的簡單比較，字符比較相似度只有1和0的區(qū)分，對時空序列相似度計算較為片面和粗糙，缺乏語義方面的考量. 本文的MGSSA算法結(jié)合語義提出了新的活動、時間、空間相似度度量方法，能更好地度量事件相似度，反映的信息更豐富更全面，更能符合實際情況.

3.4 聚類分析

下面以本文提出的MGSSA算法為相似度計算方法，采用層次聚類法對時空序列進行聚類分析，實驗以不同的圖案代表不同的類.

從聚類結(jié)果中選取一些序列來進行說明，如表3所示，初始粒度下的聚類結(jié)果如圖9(a)所示，L3與L6為同一類，L10與L28為同一類，而L1、L15、L20則各為一類. 改變活動粒度、空間粒度后，序列的聚類結(jié)果也隨之改變，如圖9(b)所示，可以看出，粒度變化后原本不在同一類的序列相似度變高，變成了同一類，L1、L3與L10為同一類，L6與L28為同一類，L15與L20為同一類. 本實驗說明了本文提出的從多粒度多尺度計算時空序列相似度的模型是有效且合宜的.

表3 聚類結(jié)果比較

圖9 初始聚類結(jié)果及改變粒度后的聚類結(jié)果對比Fig.9 Comparison of initial clustering result and clustering result after changing granularity

4 結(jié)束語

現(xiàn)有的關(guān)于用戶行為分析很少有從不同粒度對時空事件序列進行相似度計算，從而缺乏對行為事件多粒度多視角的全面認(rèn)知. 本文從大量的時空事件序列出發(fā)，在序列比對算法NW的基礎(chǔ)上，設(shè)計了一種能從多粒度多角度計算時空序列相似度的算法MGSSA，該算法主要通過計算給定粒度下的時間相似度、空間相似度、活動類型相似度的加權(quán)平均來度量時空序列之間的相似度. 并且最后實驗驗證了該算法的有效性和可行性. 本研究為其他學(xué)者研究多粒度時空序列相似性提供了參考及指導(dǎo).