基于FP-Tree模型的頻繁軌跡模式挖掘方法

牛新征，牛嘉郡，蘇大壯，佘 堃(. 電子科技大學計算機科學與工程學院 成都 673；. 電子科技大學信息與軟件學院 成都 673)

?

基于FP-Tree模型的頻繁軌跡模式挖掘方法

牛新征1，牛嘉郡1，蘇大壯2，佘 堃2
(1. 電子科技大學計算機科學與工程學院 成都 611731；2. 電子科技大學信息與軟件學院 成都 611731)

【摘要】通過對經典頻繁模式數據結構FP-tree的擴展與改進，提出了一種適用于處理軌跡數據的靈活高效的FP-tree軌跡挖掘方法(NFTM)。首先運用二維篩選和GPS格式過濾的方法對軌跡進行預處理，然后將有效數據經一次掃描后，生成按照真實軌跡順序排列且具備時空屬性的改進型FP-tree，使用動態數組存儲模式挖掘過程中得到的候選集，根據用戶的輸入針對性輸出相應時間和頻率范圍的頻繁軌跡。最后通過與GSP算法、Prefixspan算法的對比測試表明，該算法具有更短執行時間和更優性能。

關 鍵 詞FP-tree; 頻繁軌跡模式; 模式挖掘; 時空屬性

FP-Tree-Based Approach for Frequent Trajectory Pattern Mining

NIU Xin-zheng1, NIU Jia-jun1, SU Da-zhuang2, and SHE Kun2
(1. School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 611731; 2. School of Information and Software Engineering, University of Electronic Science and Technology of China Chengdu 611731)

Abstract Frequent trajectory pattern mining algorithms research focuses on how to make frequent pattern mining algorithms suitable for the mining of temporal and spatial trajectory database and reduce the times of scanning database. This paper proposes a novel trajectory mining algorithms based on novel FP-tree trajectory mining(NFTM)for a more flexible and efficient data processing which is achieved by the improvement and extension of the classic algorithm of frequent pattern structure FP-tree. The first step is the preprocessing of the original locus by using two-dimensional screening and the GPS format sifting. Then the valid data are scanned once only to generate the improved type of FP-tree, which is permutated based on the order of the authentic locus and which is also of the space-time attribute. The candidate collection derived from the process of the pattern mining in dynamic digit group storage is creatively applied. The frequent locus in the corresponding period and frequency range is output in line with users’ input. Finally, through tests in comparison with two prevalent algorithms — the GSP algorithm and the Prefixspan algorithm, the conclusion is drawn that the new algorithm has the advantages of shorter executing time and greater ability.

Key words FP-tree; frequent trajectory pattern; pattern mining; spatial-temporal attribute

在過去的十年里，隨著移動設備的發展和普及，使全球范圍內各種大小的移動對象都得到較準確的定位和有效的跟蹤。用戶不但可以通過定位技術方便地獲取個人位置信息，而且信號接收設備可以從定位終端上采集到大量移動對象的軌跡數據。軌跡記錄著用戶在客觀世界的活動，一定程度上體現了人們的意圖、喜好和行為模式。如用戶的活動規律、所經過的地點順序和最常走的幾條路線等。越來越多的科研人員開始投入到GPS軌跡的研究，希望可以從粗放時空數據中挖掘出有價值的信息。

頻繁軌跡模式挖掘是軌跡研究中最流行的一種，可以建立在頻繁模式挖掘的基礎之上，所以本文研究了對頻繁模式挖掘經典算法FP-growth的改進創新，從而能靈活高效地從大量軌跡數據流中提取所需的頻繁軌跡模式。其研究成果可以為個性化推薦、交通、旅游等應用領域提供方便的服務。

1 研究背景

頻繁模式挖掘是數據挖掘研究中的一個重要課題。文獻[1-2]提出的算法被視為頻繁模式挖掘領域最基本的兩大算法。文獻[3]采用逐層迭代策略產生頻繁項集，是一種自底向上的方法。為了提高其效率，研究人員提出了FP-growth算法，利用了一個特殊的存儲結構FP-tree，能有效地提高挖掘效率?；谝陨蟽纱笏惴?，研究人員提出了很多其他處理頻繁模式挖掘的方法，如GSP[3]算法在Apriori算法的基礎上引入了時間約束、滑動時間窗以及分類層次技術。文獻[4]提出了PrefixSpan算法，采用基于投影的分治法來減小數據。文獻[5]提出SPADE算法采用基于序列格的搜索技術和連續操作，將原始問題分解為子問題。

以上算法都旨在挖掘事物數據庫，并未同時考慮到時間和空間屬性。但是時空屬性對于軌跡挖掘來說至關重要，文獻[6]首先將原始軌跡轉換成有時間約束的時空地點序列，提出了prefix-projection的方法來提取頻繁時空模式。文獻[7-8]定義了一個標有時態的軌跡序列模式Tpattern。文獻[9]將分布式編程思想應用到頻繁項集挖掘方法的MG-FSM[10]算法。

但以上諸多算法都需要兩次以上的數據庫掃描，降低了算法執行效率，因此，文獻[11]提出FARM算法，生成了一個不僅考慮了數據的時間屬性，還能在一個緊湊的數據結構中存儲大量數據的新型框架。此外，基于MASTER-M[12]算法的數據估計框架還可以為MSN估算傳感器丟失的數據。

由以上研究可以看出，對于頻繁軌跡模式挖掘而言，目前最關鍵的兩個研究點在于如何挖掘帶有時空屬性的軌跡和減少掃描數據庫的次數[13-14]。本文針對這兩個問題對FP-growth算法進行了改進：

1) 提出一種基于經緯度二維篩選和GPS格式過濾的軌跡預處理方法。

2) 改進FP-tree使其適用于軌跡處理，使用動態數組存儲挖掘出的候選軌跡集。

3) 能根據用戶的需要輸出不同時間段和不同頻率段的頻繁軌跡。

2 問題描述

本文所研究的軌跡是帶有時間屬性的文本軌跡流，每條軌跡由多個地點串聯而成，每兩個地點之間還帶有時間差。

定義 1 一個軌跡點vi是由一個三元組(xi,,yi,ti)構成的，xi,yi是經度和緯度，ti是時間戳。

定義 2 一條時空軌跡是由序列 S = v0, v1,…, vn= (x0, y0, t0),(x1, y1, t1), …, (xn, yn, tn)構成的，ti(i =0…n)是時間戳，是軌跡中某一點的經緯度。

本文的軌跡流模式是在文獻[7]上的擴展改進，原軌跡流模式定義如下：

式中，vn為地點；tn為時間戳。但不能認為從某地到下一個地點所需的時間可以嚴格控制為某個具體的時間點，而應該用一個大致的時間段來描述。所以本文采用的軌跡流模式如下：

定義 3 本文所使用的軌跡模式為：

式中，tαn為一個時間區間表示從所花費的最短時間和最長時間分別是和

定義 4 給定一個軌跡數據庫D，共有n條軌跡，軌跡支持度support是軌跡序列S的數量占總數n的百分比。

定義 5 最小支持度閾值min_sup是挖掘過程中過濾軌跡點和過濾軌跡的衡量標準，最后加入到頻繁軌跡集中的軌跡S的支持度support(S)> min_sup。

3 NFTM模型建立

3.1 模型綜述

本文的算法由3個模塊組成: 預處理模塊、軌跡樹構建模塊和頻繁軌跡模式挖掘模塊。在預處理模塊中，根據地點數據的經緯度進行異常和冗余數據的檢測并刪除。然后將數據輸入到第2個頻繁軌跡樹生成模塊中，通過一次數據庫掃描，動態地搭建一棵頻繁軌跡樹，并生成相鄰結點之間的時間差。進入第三個挖掘模塊后，可以根據用戶所要求的時間和頻率段輸出頻繁路徑，以及走完該路線所花費的最長時間和最短時間。該模型的整體框架如圖1所示。

圖1　NFTM的整體框架

3.2 預處理模塊

本文提出一種基于經緯度和GPS數據格式[15]的軌跡數據預處理方法。

軌跡模式挖掘所用到的是GPS軌跡數據集，設每個數據點由一個包含經度、緯度和時間的三元組item構成，而原始數據集非常龐大且格式不統一，所以首先檢查每個數據點的數據格式是否符合要求，將不規則點從數據集中刪去。設數組ft[ ]存儲經格式匹配函數過濾后的數據。將所有數據按經度進行分類，設數組sl[m][ ]用來存儲具有相同經度m的數據項，再將同一經度的item集按照不同的緯度進行劃分，并統計每類的item個數，用number表示。將小于閾值(通過對大量數據的測試得到，設為T)的數據組刪除。由于數據的采集間隔時間較短，造成了大量的冗余數據，嚴重浪費了處理時間。所以將相鄰連續的同一地點合并成一個，到達時間為第一個地點的到達時間。設final[ ]存放預處理后剩余的數據項。偽代碼如下：

輸入: file directory (一個文件目錄)

For each file from 0 to k

for each item from 0 to n

if format(itemn)==true

add itemnto ft[ ];

Put the triples which have the same

longitude into sl[m][ ];

for sl[ ][ ] from sl[0][ ] to sl[m][ ];

for each item form sl[m][ ];

if number of itemn< T

remove (itemn) from sl[m][ ];

i=0;

While sl[m][ ]!=null

If sl[m][i] ！= sl[m][i+1]

add sl[m][i] to final[ ];

the final[ ] coverage the original file

3.3 頻繁軌跡樹生成模塊

在頻繁軌跡樹生成模塊中，通過建立一種緊湊的數據結構存儲樹節點的屬性和相鄰結點之間的時間差值，只需掃描一次數據庫可動態的構建軌跡樹。構建軌跡樹部分的規則如下:

1) 如果多個路徑都經過某點，那么這個點應被合并成一項存儲在項頭表中。把兩條軌跡從頭結點開始的前幾個相同節點合并，從不同的節點開始分支。

2) 對頻繁模式的挖掘加入時間限制，分別挖掘出不同時間段的頻繁路徑或地點。時間段的限制根據用戶的輸入來定。

3) 考慮到實際應用場景，所以在構建軌跡樹時將各地點按真實軌跡順序排列。

4) 新增了一個有效的數據結構，用來存儲整條頻繁路徑的時間長度。

使用一個例子來描述如何應用以上規則構建一棵頻繁軌跡樹，首先定義了時間限定在(0～20)的6條簡化軌跡如下：

1) (v1,1)—(v2,3)—(v3,6)—(v4,7)

2) (v1,1)—(v2,9)—(v4,13)

3) (v4,3)—(v2,9)—(v5,11)—(v6,14)

4) (v4,2)—(v2,3)—(v6,4)—(v7,8)

5) (v4,7)—(v1,9)—(v7,14)—(v6,17)

vi代表地點，數字n代表時間。將以上6條軌跡輸入本模塊后，開始進行頻繁軌跡樹的構建，具體步驟如下：

1) 首先輸入時間限制，將預處理后的數據根據時間屬性再進行一次過濾，只保留在規定時間段內的數據。建立樹的根結點，設置為NULL。

2) 第一條軌跡輸入后，生成如圖2所示的項頭表，用來存儲每個數據項的值、對應的支持度以及指向數據項在樹中所處位置的指針。此外，在頭結點下生成一條軌跡，構建頻繁軌跡樹的第一條分支。在樹枝上即兩個相鄰的結點之間存儲時間間隔。

圖2　輸入(v1,v2,v3,v4)之后的存儲結構

3) 輸入第二條軌跡，支持度改變。v1和v2的出現順序與第一條軌跡相同，所以合并路線。由于第二條軌跡中v1和v2的時間差為8，所以時間差的最大值由2改為8。從v4起在樹中生成了另一條軌跡分支。v4結點第二次出現，所以第一條軌跡中的v4還需要具備一個指向第二條軌跡中v4的指針，稱為指向下一同名結點的指針。輸入第三條軌跡之后，如圖3所示，由于新增了兩個項頭表中沒有的地點v5和v6，所以將其加入項頭表中，并添加指向它們的指針。

圖3　輸入(v1,v2,v4) 和(v4,v2,v5,v6)之后的存儲結構

4) 輸入第四條軌跡，v4、v2和第三條軌跡重合，它們之間時間差的最小值由6變為1。將第一次出現的v7地點與支持度連同指向它的指針加入項頭表中。輸入第五條軌跡之后，如圖4所示，一顆完整軌跡樹構建完成。

圖4　輸入(v4,v2,v6,v7)和(v4,v1,v7,v6)之后的存儲結構

3.4 挖掘模塊

在挖掘模塊中，定義動態數組temp[ ]用來存放軌跡挖掘過程中的候選軌跡集，動態數組frequency[ ]用來存放軌跡的頻率。初始化頻繁軌跡集frequentSet[ ]和符合頻率條件的軌跡集finalSet[ ]使其為空。偽代碼如下：

輸入：min_supp(最小支持度閾值)、start and end(需要挖掘的頻率范圍)

for all locations liin the header table

if support(li)< min_supp

traverse the node-link containing li;

remove all nodes have lifrom tree;

for remaining items of header table

for all items named li

generate sub-tree with all paths ending by li; the same combined into one route, the route

generating set S, placed in the temp[ ];

Put the supportrouteinto the frequency[ ];

for all routes in temp[ ]

if S.support >= min_supp；

add S to frequentSet[ ];

for all routes in frequentSet[ ]

if S.support >=start &&

S.support< = end

add S to finalSet[ ];

output finalSet

從以上算法可以看出，本文相比于FP-growth算法的不同之處是：FP-growth算法在挖掘頻繁模式時，需遍歷FP樹來遞歸的生成條件FP樹，條件FP樹的每一個結點至少需要3個指針，護起來要花費較多的動態空間。本文使用數組存儲條件樹，將遍歷樹得到的子路線存儲在數組中，能有效地節約空間，提高時空效率。很多頻繁軌跡模式挖掘的算法最終只輸出最高頻率的路徑，這樣極易造成對特定群體而言只輸出一個地點，如對學生而言，最終可能只輸出“學?！?。所以經改進，可以根據用戶的需求輸出一定頻率范圍內的路徑。

4 實驗及其結果分析

4.1 數據集與環境

本文算法的測試部分所使用的是來自Geolife項目的真實數據集[GSP code 2013]，使用的測試集為200 KB，約12 000個地點項。測試集中的每一條軌跡路線都是由一系列地點項組成，每個項都包含經緯度和時間戳。將該算法與兩個經典頻繁模式挖掘算法GSP和Prefixspan進行了對比。所有測試實驗都在具有2.30 GHz速度的處理器以及4.00 GB主存的電腦上完成。代碼使用JAVA語言編寫。

4.2 測試結果和分析

本文從以下3個方面進行了對比。

1) 第一個對比如圖5所示。由圖5可以看出，3個算法的運行時間都隨著最小支持度的增長而增長。特別是GSP算法，在支持度小于0.55時，增長趨勢平滑，但之后迅速增長，時間趨近于無窮。由此可得，該算法的運行時間比其他兩個算法更短，且隨著支持度的變化增長趨勢穩定。

圖5　不同最小支持度下的運行時間

2) 第二個對比將最小支持度統一為0.55，如圖6所示。從圖中可看出，Prefixspan和該算法都是隨著地點數量的不斷增加，程序運行時間變長。不同的是前者的增長速度較快，而后者變化趨勢平穩，說明該算法對于處理不同地點數量的軌跡數據具有較優的性能。GSP算法變化趨勢并不平緩，這是因為軌跡數據增加并不表明得到的頻繁軌跡增加。如一個含1 000數據點的軌跡集可能有100個頻繁1項集，但是一個含500個數據點的軌跡集可能有200個頻繁1項集。GSP算法需多次掃描數據庫，掃描到的頻繁1項集越多，程序運行時間越長。而該算法只需要掃描一次數據庫，所以比GSP算法性能更穩定。

圖6　不同地點數量下程序運行時間的變化

3) 第三個對比如圖7所示。最小支持度固定在0.55，使用了4 000條軌跡進行測試?？梢钥闯鲭S著軌跡平均長度增加，程序運行時間越來越短，且變化平穩。該算法的運行時間比另外兩個更短。

圖7　不同平均軌跡長度下程序運行時間

4) 第四個對比如圖8所示，規定參與測試的軌跡平均長度為20，最小支持度閾值設為0.55。所使用的軌跡數量由500～2 500。程序運行時間隨著軌跡數量的增長而增長。該算法比其余兩個算法整體運行時間短，且增長趨勢更為平緩，可見性能更優。

圖8　不同軌跡數量下的程序運行時間

5 結 束 語

本文以FP-tree為模型，提出了一種更加優化且適用于處理軌跡數據的頻繁軌跡模式挖掘算法NFTM。通過有針對性的預處理模塊精簡了軌跡數據。在構建軌跡樹部分，只進行一次數據庫掃描，并且生成按照真實順序排列的同時具備時空屬性的軌跡樹。最后充分考慮各種現實因素，在挖掘部分使用數組作為存儲結構，并加入了自主限定時間、頻率的思想，使挖掘出的頻繁軌跡更加人性化，符合實際應用需求。

參 考 文 獻

[1] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules[C]//Very large data bases(VLDB). San Francisco, CA, USA: Morgan Kaufmann Publishers, 1994: 487-499.

[2] HAN Jia-wei, PEI Jian, YIN Yi-wen, et al. Mining frequent patterns without candidate generation: a frequent pattern tree approach[J]. Data Mining and Knowledge Discovery, 2004, 8(1): 53-87.

[3] SRIKANT R, AGRAWAL R. Advances in database technology—EDBT'96[M]. Berlin, Heidelberg: Springer, 1996: 1554-1558.

[4] PEI Jian, HAN Jia-wei, MORTAZAVI-ASL B, et al. PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth[C]//ICDE'01 Proceedings of the 17th International Conference on Data Engineering. Washington D C, USA: IEEE Computer Society, 2001: 215-224.

[5] ZAKI M J. SPADE: an efficient algorithm for mining frequent sequences[J]. Machine Learning, 2001, 11(5): 31-60.

[6] KANG Juyoung, YONG Hwan-Seung Y. Mining trajectory patterns by incorporating temporal properties[C]// Proceedings of the 1st International Conference on Emerging Database. Busan, Korea: Hwan-Seung, 2009: 63-68.

[7] GIANNOTTI F, NANNI M, PINELLI F, et al. Trajectory pattern mining[C]//Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. California, USA : Scan Jose, 2007: 330-339.

[8] PEI Jian, HAN Jia-wei, MAO run-ying. CLOSET: an efficient algorithm for mining frequent closed itemsets[C]// Proceedings of the 5th ACM-SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. Dallas, USA: ACM, 2000: 11-20.

[9] MILIARAKI I, BERBERICH K, GEMULLA R, et al. Mind the gap large-scale frequent sequence mining[C]// Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM 2013: 797-808.

[10] DEAN J, GHEMAWAT S. Mapreduce: Implied data processing on large clusters[C]//6th Symposium on Operating Systems Design and Implementation. [S.l.]: USENIX Association, 2004: 137-149.

[11] GRUENWALD L, CHOK H, ABOUKHAMIS M. Using data mining to estimate missing sensor data[C]//IEEE International Conference on Data Mining Workshops. Omaha, NE, USA: IEEE, 2007: 207- 212.

[12] GRUENWALD L, YANG Han-qing , SADIK M S, et al. Using data mining to handle missing data in multi-hop sensor network applications[C]//9th ACM International Workshop on Data Engineering for Wireless and Mobile Access. New York, USA: ACM, 2010: 9-16.

[13] Microsoft Research Asia. GSP code [EB/OL]. [2011-10-30]. http://www.philippe-fournierviger.com/spmf/index.php? link= documentation.php.

[14] GENG Xiao-liang, ARIMURA H, UNO T. Pattern mining from trajectory GPS data[C]//2012 IIAI International Conference on Advanced Applied Informatics. Fukuoka, USA: IEEE, 2012: 60-65.

[15] LIANG Wan-ga, HUA Kunyuan, TAO Ku, et al. Mining frequent trajectory pattern based on vague space partition[J]. Knowledge-Based Systems, 2013, 50: 100-111.

編 輯 黃 莘

作者簡介：牛新征(1978 ? )，男，博士，副教授，主要從事網絡計算、移動數據庫、中間件技術、數據挖掘等方面的研究.

收稿日期：2014 ? 11 ? 19；修回日期：2015 ? 01 ? 12

中圖分類號TP393

文獻標志碼A

doi:10.3969/j.issn.1001-0548.2016.01.014

基金資助：國家自然科學基金(61300192)