基于位置序列的廣義后綴樹用戶相似性計算方法

1、https:/基于位置序列的廣義后綴樹用戶相似性計算方法基于位置序列的廣義后綴樹用戶相似性計算方法摘要：為了解決移動數(shù)據(jù)形成的軌跡間用戶相似性問題，提出了一種基于位置序列的廣義后綴樹（LSGST）用戶相似性計算方法。該算法首先從移動數(shù)據(jù)中抽取位置序列，同時將位置序列映射為字符串，完成了對位置序列的處理到對字符串處理的轉(zhuǎn)化工作；然后，構(gòu)建不同用戶間的位置序列廣義后綴樹；最后，分別從經(jīng)過的相似地方個數(shù)、最長公共子序列、頻繁公共位置序列三方面對相似性進(jìn)行具體計算。理論分析和仿真表明，該算法提出的三個計算指標(biāo)在計算相似性方面具有理想的效果；除此之外，與構(gòu)造后綴樹的普通方法相比，時間復(fù)雜度較低；與動態(tài)規(guī)

2、劃和樸素字符串匹配方法相比，該算法在尋找最長公共子串、頻繁公共位置序列時，效率更高。實驗結(jié)果表明 LSGST 能夠有效測量相似性，同時減少了尋找測量指標(biāo)時需要處理的軌跡數(shù)據(jù)量，并在時間復(fù)雜度方面明顯優(yōu)于對比算法。關(guān)鍵詞：移動數(shù)據(jù)；用戶相似性；位置序列；字符串匹配；廣義后綴樹中圖分類號： TP391文獻(xiàn)標(biāo)志碼：AAbstract ： To solve the user similarity between trajectories formed bymobility data， an algorithm based on Location Sequence Generalized SuffixT

3、ree （LSGST） was proposed. First， the location sequence was extractedfrom mobility data. At the same time the location sequence was mapped to astring. The transformation from the processing of location sequence to theprocessing of string was completed. Then the location sequence generalizedsuffix tre

4、e between different users was constructed. The similarity wascalculated in detail from the number of similar positions， longest commonsubsequence and the frequent common position sequence. The theoreticalanalysis and simulation results show that the proposed algorithm has idealeffect in terms of sim

5、ilarity measure. Besides ， compared to the ordinaryconstruction method， the proposed algorithm has low time complexity. In thecomparison with dynamic programming and naive stringmatching ，theproposed algorithm has higher efficiency when searching for the longestcommon substring and frequent public p

6、osition sequence. The experimentalresults indicate that the LSGST can measure the similarity effectively ，meanwhile reduces the trajectory data when searching for the measurementindex， and has better performance in time complexity.英文關(guān)鍵詞Key words：mobility data； user similarity； location sequence； str

7、ingmatching； generalized suffix treehttps:/0 引言本文在上述基礎(chǔ)上，提出基于位置序列的廣義后綴計算用戶相似性算法。首先從原始中英全 GPS 軌跡中抽取位置序列，同時將其表示成字符串，將對位置序列的處理轉(zhuǎn)化為了對字符串的處理；然后構(gòu)造用戶間位置序列廣義后綴樹，實現(xiàn)了在構(gòu)造的同時對相似地方個數(shù)、最長公共子序列、頻繁公共位置序列的尋找；最后，通過這三方面對相似性進(jìn)行具體計算。1 問題描述1.1 基本定義原始軌跡記錄了移動物體的位置、時間信息，如圖 1 所示，記錄了經(jīng)過位置的時刻和持續(xù)時間（通過計算相鄰位置的時間差獲得），從原始軌跡中抽取位置序列，只需要將時

8、間去除即可。位置序列獲得后，需將其映射為字符串。比如，用戶與字符串中的 AB 會混淆，是否可選用其他變量代替？LS 后的字母是否應(yīng)下標(biāo)？可以選用其他變量。LS 后的字母是下標(biāo)。1.3 構(gòu)造廣義后綴樹用戶位置序列映射為字符串后，構(gòu)造廣義后綴樹，由于普通后綴樹常用于處理單個字符串，而本文需要處理多條用戶軌跡，即相當(dāng)于處理多個字符串，因此使用廣義后綴樹進(jìn)行處理。廣義后綴樹是一種壓縮字典樹，它將只有一個子節(jié)點的內(nèi)部節(jié)點全部壓縮，形成一個內(nèi)部節(jié)點至少含有兩個子節(jié)點的后綴樹，能夠處理多個字符串組的匹配問題22?；诤缶Y樹基礎(chǔ)，構(gòu)造位置序列廣義后綴樹 （Location Sequence Generaliz

9、ed Suffix Tree，LSGST）實現(xiàn)對多個用戶位置序列的處理，具體構(gòu)造時利用了 Ukkonen22構(gòu)造后綴樹的思想，在構(gòu)造過程中通過索引對具體信息進(jìn)行標(biāo)記。需要用到的相關(guān)定義介紹如下。1）對字符串進(jìn)行預(yù)處理，并加入?yún)^(qū)分不同字符串和表示字符串結(jié)尾的特殊符號“#”。2）將不同字符串按照從左至右的順序加入后綴樹，其中根節(jié)點不包含任何字符。4）構(gòu)造過程中，每加入一個字符都對每個節(jié)點進(jìn)行信息的更新。1.4 尋找相似地點及最長公共位置序列一般情況下，用戶在日常生活中共同經(jīng)過的地方越多，便更可能存在某種聯(lián)系。通過尋找用戶經(jīng)過的相似地方個數(shù)、最長公共位置序列，量化具體相似度值，值的大小揭示用戶間存在

10、的特殊聯(lián)系。通過抽取的位置序列可統(tǒng)計出用戶間的相似地方個數(shù)。傳統(tǒng)尋找最長公共子序列方法，一般在樹構(gòu)造后再遍https:/歷，以尋找到深度最深且同時屬于兩個子串的序列，這種方法在構(gòu)造、遍歷階段都花費了許多時間，復(fù)雜度較大。為了減少時間開銷，提出了在構(gòu)造 LSGST的過程中，同時查詢每個節(jié)點信息的方法，并引入?yún)?shù) Record 記錄當(dāng)前位置中的最長公共子序列 Record（Depth， Cover，LCS），其中 LCS 為用戶間經(jīng)過的最長公共子序列。具體尋找過程如下：1）從根節(jié)點出發(fā)記錄節(jié)點信息，Record（1，）為信息查詢的初始狀態(tài)。2）加入每個字符都分別更新每個葉子節(jié)點的信息。3）每加入一

11、個字符，Record 中的信息都與當(dāng)前字符更新信息進(jìn)行比較，如果節(jié)點的深度大于 Record 中記錄的深度，且節(jié)點覆蓋度大于 1，則記錄當(dāng)前節(jié)點對應(yīng)的字符串，同時更新 Record。4）最后取出 Record 中的最長公共子序列信息。1.5 挖掘頻繁公共位置序列定義 5 最小出現(xiàn)次數(shù)。公共位置序列在整個軌跡數(shù)據(jù)庫中出現(xiàn)的最小次數(shù)。定義 6 頻率計數(shù)器。表示從根節(jié)點到某個節(jié)點的軌跡字符串在全部軌跡中出現(xiàn)的頻率。利用公式 fCount=ni=1index.strPosition（i）缺少內(nèi)容進(jìn)行計算，其中 n 指的是葉子節(jié)點表示的后綴在不同字符串中出現(xiàn)的次數(shù)。圖 2 描述了頻率計數(shù)器在廣義后綴樹中

12、的具體表示方法，其中：節(jié)點用圓圈表示，連接節(jié)點的邊用字符串子串表示。每個節(jié)點記錄了從根節(jié)點到該節(jié)點經(jīng)過邊的所有子串，每個葉子節(jié)點記錄了字符串對應(yīng)的不同后綴，且每個節(jié)點記錄了節(jié)點編號和頻率計數(shù)器，以（strID：fCount）的形式來表示，當(dāng)頻率計數(shù)器的值大于等于最小出現(xiàn)次數(shù)時，該節(jié)點所對應(yīng)的子序列才能被選擇出來。例如，設(shè)置最小出現(xiàn)次數(shù)為 3，則在是否錯誤，應(yīng)為圖 2？為圖 2。算法 1 描述了具體尋找頻繁公共位置序列的方法，其中：1）6）行將位置序列轉(zhuǎn)化為字符串，并構(gòu)造廣義后綴樹；第 8）14）行，首先尋找頻率計數(shù)器大于最小出現(xiàn)次數(shù)的節(jié)點，然后比較節(jié)點間頻率計數(shù)器的大小，尋找頻率計數(shù)器最大的節(jié)

13、點，最后在頻率計數(shù)器最大的節(jié)點中分別比較該節(jié)點表示的序列長短，若長度大于最小序列長度，則將該序列加入到頻繁公共位置序列集合中。2 相似性測量從兩個用戶經(jīng)過的相似地方個數(shù)、最長公共位置序列和頻繁公共位置序列三方面對不同用戶間的相似性進(jìn)行具體計算。2.1 相似地方個數(shù)相似性https:/計算兩個用戶經(jīng)過的相似地方不考慮位置的順序性，只考慮兩條軌跡中出現(xiàn)相似地方的個數(shù)，將經(jīng)過的多個相似地方累加，能夠得到一個測量指標(biāo)，具體如式（1）所示。其中：LocationNumi 表示位置 i 在具體軌跡中出現(xiàn)的次數(shù)；P、Q 分別表示軌跡 P、Q 中總位置個數(shù)。計算位置 i 在軌跡 P、Q 中出現(xiàn)的頻率，能夠統(tǒng)計

14、出共同出現(xiàn)在兩條軌跡中的所有位置頻率，lSim（P，Q）值越大，表示兩條軌跡中經(jīng)過的相似地方個數(shù)越多。2.2 MLength 最長公共位置序列相似性利用廣義后綴樹能夠?qū)ふ业杰壽E間的最長公共位置序列，當(dāng)計算相似性時，有兩方面需要考慮：一是最長公共位置序列 MLength 的個數(shù)；二是不同軌跡的長度，即軌跡包含的位置個數(shù)。通過這兩個指標(biāo)來衡量，考慮原始軌跡長度的原因是，當(dāng)軌跡較長時，位置點信息較多，能夠獲得 MLength 的可能性更大，因此通過它來調(diào)節(jié)不同軌跡的平衡性，使結(jié)果更加真實合理。具體通過下列公式進(jìn)行計算。2.3 頻繁公共位置序列相似性除了上述兩種相似性測量之外，還利用頻繁公共位置序列對

15、軌跡間相似性進(jìn)行測量。首先記錄出現(xiàn)頻率最高的公共子序列，然后利用式（5）對具體相似性進(jìn)行計算，其中：Maxfre 表示軌跡對間最大頻率，Ratio（MLen 是否代表MLength，為什么式中等式兩邊形式不統(tǒng)一？的，代表 M-Length 公式中出現(xiàn)的M-Len 都代表 M-Length，等式兩邊形式不一，是因為當(dāng)初在排版的時候，M-Length 太長，導(dǎo)致公式超出頁面大小，所以用 M-Len 來代替了 M-Length。3 實驗結(jié)果分析3.1 數(shù)據(jù)預(yù)處理數(shù)據(jù)集記錄了反映用戶日常行為的連續(xù)數(shù)據(jù)和位置注釋信息，將位置信息按時間排列，形成用戶軌跡。抽取位置序列時，發(fā)現(xiàn)用戶注釋的位置名稱多樣化，如對

16、多媒體實驗室的注釋，在數(shù)據(jù)集中出現(xiàn)“ML”“Media Laboratory”等，公園街的注釋出現(xiàn)“Park St”“Prkst”等，預(yù)處理階段，將多樣化的詞都用同一個詞來表示。除此之外，許多注釋并不代表一個地方，而是代表某個區(qū)域，這個區(qū)域由于覆蓋范圍廣，并不知道具體位置，為了解決這個問題，使用這個詞作為查詢關(guān)鍵詞，并在谷歌地圖中查詢，如“Park St”代表一個區(qū)域，它所在的區(qū)域通過查詢能夠獲得“車站，教堂，餐廳”等位置序列，因此將數(shù)據(jù)集中“Park St”以“車站，教堂，餐廳”來表示，如圖 3 所示。3.2 時間復(fù)雜度分析對于長度分別為 m、n 的字符串 M 和 N，通常采用動態(tài)規(guī)劃和樸素

17、字符串匹配尋找最長公共子串，其中動態(tài)規(guī)劃通常需要構(gòu)造一個二維表，且表中含有mn 項，利用遞推方式尋找最長公共子串，其時間復(fù)雜度為 O（mn）；樸素字https:/符串匹配則通過移動步長進(jìn)行尋找，其時間復(fù)雜度為 O（n-m+1）m）；利用廣義后綴樹尋找最長公共子串，由于在構(gòu)造樹時就已經(jīng)對最長公共子串、頻繁公共子序列進(jìn)行了尋找，因此其時間復(fù)雜度也就是構(gòu)造廣義后綴樹方法的復(fù)雜度 O（n）。這三種方法中，最后一種時間復(fù)雜度最低。除此之外，對于處理多個字符串組問題，廣義后綴樹的時間復(fù)雜度為線性，而其他兩種方法的時間開銷則會根據(jù)字符串長度的增加而變大。3.3 相似性計算為了度量用戶相似度具體值，分別從提出

18、的三個角度進(jìn)行計算，表 1 列出了不同長度的軌跡間，經(jīng)過相似地方時相似度的值，以序列長度 14 作為比較基準(zhǔn)，表中 seqL、sameP、freApp、nlSim、lSim 分別表示序列長度、相同地方個數(shù)、相同地方出現(xiàn)次數(shù)、不考慮序列長度時相似度值、考慮序列長度時相似度值。從表 1 中可以看出，不考慮位置序列長度時，相似度值根據(jù)經(jīng)過的相似位置個數(shù)和出現(xiàn)頻率獲得，呈遞增趨勢；考慮位置序列長度時，相似度值除了依靠相似地方的個數(shù)和出現(xiàn)頻率之外，還根據(jù)長度來決定，其值并沒有出現(xiàn)某種遞增趨勢。如序列長度為 73 的軌跡，在和序列長度為 48 的軌跡進(jìn)行相似度比較時，盡管其序列長度較長，但當(dāng)經(jīng)過相同地方個

19、數(shù)相同時，其相似度值卻相對較低。由于實際情況中，不同用戶經(jīng)過的位置序列長度不同，使得測量過程中出現(xiàn)不平衡現(xiàn)象，在相似度計算時，考慮長度能夠減弱這種不平衡，使得相似度值更加合理。表 3 通過軌跡間頻繁位置序列計算相似度，從表中可以看出，考慮軌跡長度時，頻率相似度在出現(xiàn)頻率很高的情況下也不一定值最大，它和序列出現(xiàn)的頻率、長度都有關(guān)。從表 13 中可以看出，三種相似度值并沒有呈現(xiàn)一種規(guī)律性變化，因為影響相似度值的因素很多，其值不會按照一定指標(biāo)增長或減少。除此之外，基于頻繁公共位置序列的相似度值略高于其他兩種，這是因為在日常生活中，當(dāng)人們頻繁經(jīng)過相似位置序列時，更有可能存在某種關(guān)系，如學(xué)生通常都以“寢室 實驗室 食堂 宿舍”這樣的位置序列出現(xiàn)。4 結(jié)語通過構(gòu)造的位置序列廣義后綴樹對用戶間相似性進(jìn)行具體測量，首先通過映射方法將位置序列問題轉(zhuǎn)化為字符串匹配問題，在此基礎(chǔ)上，構(gòu)造用戶間位置序列廣義后綴樹，并在構(gòu)造的同時尋找相似地方個數(shù)、最長公共子序列、頻繁公共子序列，然后從這三方面測量具體相似