汪成亮， 黃利瑩， 趙凱

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

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

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

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

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

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

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

1 相關(guān)概念

1.1 時(shí)空事件、時(shí)空事件序列

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

1.2 粒度

時(shí)空事件具有多粒度[14]的特性，下面分別對(duì)活動(dòng)粒度、空間粒度、時(shí)間粒度進(jìn)行定義.

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

圖3 活動(dòng)粒度Fig.3 Activity granularity

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

圖4 空間粒度Fig.4 Spatial granularity

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

圖5 時(shí)間粒度Fig.5 Temporal granularity

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

傳統(tǒng)的序列挖掘中的事件很多都是瞬時(shí)事件，這樣事件的發(fā)生關(guān)系很簡(jiǎn)單. 而對(duì)于帶有時(shí)間間隔的事件來(lái)說(shuō)，因?yàn)槊總€(gè)事件都有兩個(gè)時(shí)間點(diǎn)，事件間的關(guān)系就要復(fù)雜得多，下面就對(duì)時(shí)間間隔事件間的關(guān)系表達(dá)[15]做詳細(xì)的介紹.

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

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

②Overlap(event1,event2)：表示事件event1與事件event2發(fā)生的時(shí)間上有重疊，即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同時(shí)發(fā)生并且同時(shí)結(jié)束，即tstart(event1)=tstart(event2)且tend(event1)=tend(event2).

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

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

①NoOverlap(event1,event2)：tstart(event2)-th≤tend(event1)≤tstart(event2)+th或tend(event1)+th≤tstart(event2). 說(shuō)明：在一些情況下，如果兩個(gè)事件的間隔時(shí)間太長(zhǎng)，那么這個(gè)“NoOverlap”關(guān)系是沒(méi)有意義的，所以設(shè)置一個(gè)最大時(shí)間差tmax，當(dāng)tstart(event2)-tend(event1)>tmax時(shí)，兩個(gè)事件“NoOverlap”關(guān)系不成立，即兩個(gè)事件沒(méi)有任何關(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 序列比對(duì)Needleman-Wunsch算法

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

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

(1)

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

S(i,j)=

(2)

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

2 多粒度時(shí)空序列相似度計(jì)算

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

2.1 時(shí)空事件相似度及時(shí)空事件可比性

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

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

w(eventi，eventj)=

(3)

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

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

定義5時(shí)空事件可比性：已知兩個(gè)時(shí)空事件序列L1={event11,event12,…,event1n}與L2={event21,event22,…,event2n}，對(duì)于L1中任意一項(xiàng)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)具有時(shí)空事件可比性. 且序列L1中的事件event1i的下一事件event1(i+1)只需和L2中以事件event2j開(kāi)始的事件逐一進(jìn)行比較，而不用從序列L2的第一項(xiàng)開(kāi)始比較.

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

2.2 時(shí)空序列相似度及多粒度時(shí)空序列相似度求解算法

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

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

S(i,j)=

(S(0,0)=0)

(4)

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

算法1：多粒度時(shí)空序列比對(duì)算法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];

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

多粒度活動(dòng)相似度算法MGAS，描述如下.

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

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

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

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

(5)

多粒度時(shí)間相似度算法MGTS描述如下.

算法3：多粒度時(shí)間相似度算法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基于給定的某一粒度，將時(shí)間軸劃分并編號(hào)，通過(guò)最長(zhǎng)公共子序列LCS算法求出時(shí)間相似度，實(shí)現(xiàn)了以多種粒度來(lái)求時(shí)間相似度. 最長(zhǎng)公共子序列算法經(jīng)過(guò)優(yōu)化后，時(shí)間復(fù)雜度為O(nlogn)，所以算法3的時(shí)間復(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基于空間類型多叉樹(shù)和其構(gòu)造的哈希表，同樣也可從多種粒度來(lái)求空間相似度. 該算法的時(shí)間復(fù)雜度為O(1).

3 實(shí)驗(yàn)評(píng)估

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

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

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

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

3.2 MGSSA算法實(shí)驗(yàn)有效性驗(yàn)證

本實(shí)驗(yàn)通過(guò)序列可視化方法來(lái)對(duì)多粒度時(shí)空序列比對(duì)算法進(jìn)行有效性驗(yàn)證，如表1所示.

表1 序列可視化

為了驗(yàn)證有效性，本文做了4組實(shí)驗(yàn)，實(shí)驗(yàn)結(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ǔ)上改變活動(dòng)粒度如圖7(d)所示，可以看出不同事件序列之間，事件的活動(dòng)類型大致相同，即原本不同的序列其實(shí)可以看作是同一序列.

表2 實(shí)驗(yàn)結(jié)果

圖7 不同空間粒度、活動(dòng)粒度對(duì)比Fig.7 Comparison of different spatial granularity and activity granularity

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

3.3 MGSSA算法與NW算法對(duì)比

3.3.1時(shí)間復(fù)雜度

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

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

圖8 MGSSA與NW算法的平均運(yùn)行時(shí)間對(duì)比Fig.8 Comparison of average running time between MGSSA and NW

3.3.2語(yǔ)義完整性

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

3.4 聚類分析

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

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

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

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

4 結(jié)束語(yǔ)

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