一種基于MP－tree的頻繁路徑挖掘算法

趙 利，徐永成，胡孔法，陳 崚

（揚州大學(xué) 信息工程學(xué)院，江蘇 揚州 225127）

射頻識別［1－3］（radio frequency identification，RFID）是一種非接觸式的自動識別技術(shù)，目前已廣泛應(yīng)用于制造業(yè)、醫(yī)療護理和交通運輸?shù)榷鄠€領(lǐng)域.RFID標簽可以貼在一包物品、一箱物品甚至單個物品上，當標簽進入磁場時會發(fā)送自身的EPC（electronic product code）編碼等信息，部署在不同位置的RFID閱讀器通過天線發(fā)送一定頻率的射頻信號，讀取標簽中的信息并解碼后將數(shù)據(jù)送至RFID中間件［4－5］進行相關(guān)處理，RFID中間件對數(shù)據(jù)進行簡單的過濾、清洗和融合等處理后再傳送給網(wǎng)絡(luò)上的其他用戶.分析物品在供應(yīng)鏈中的移動可以得到物品的路徑痕跡信息，了解這些路徑信息可以極大地提高商業(yè)運轉(zhuǎn)的效率；但是直接對這些路徑數(shù)據(jù)進行分析必然帶來數(shù)據(jù)的爆炸，因此必須運用有效的方法對數(shù)據(jù)進行預(yù)處理.然而，到目前為止，針對RFID數(shù)據(jù)管理技術(shù)的研究還不是很多，很多問題還有待解決.由于RFID路徑信息的特殊性和分析的復(fù)雜性，因此有關(guān)挖掘頻繁路徑［6－8］的算法并不多，而且效率很低.如果應(yīng)用傳統(tǒng)的Apriori算法［9－10］，則效率非常低，也不切實際，因為將Apriori算法應(yīng)用于RFID移動路徑數(shù)據(jù)，產(chǎn)生的候選項將是不可估計的.本文就是在這些工作的基礎(chǔ)上，引入挖掘頻繁路徑的思想，提出了挖掘頻繁路徑的算法MP（movement path）－mine.

1 相關(guān)概念和定義

RFID數(shù)據(jù)一般由三元組組成，形如（EPC，location，time），其中EPC是對每個物品進行唯一標識的電子產(chǎn)品編碼，location表示閱讀器讀取發(fā)生的位置，time表示閱讀器讀取發(fā)生的時間.用數(shù)對pi＝（li，ti）表示對象在時間ti訪問了li，規(guī)定如果p1＝p2，則必須使t1＝t2并且l1＝l2，這樣將一系列記錄集成起來就能得到物品的移動路徑信息，形如〈（l1，t1），（l2，t2），…，（li，ti），…，（lm，tm）〉.令T＝〈（l1，t1），（l2，t2），…，（lm，tm）〉，稱T 是一個長度為m 的模式，即m－pattern.

定義1 假設(shè)有路徑p1＝（a1），（a2），…，（ai），…，（am），p2＝（b1），（b2），…，（bj），…，（bn），其中ai和bj都是形如（li，ti）的路徑段，i＝1，2，…，m；j＝1，2，…，n.若存在一組整數(shù)1≤j1≤j2≤…≤jm≤n，有a1?bj1，a2?bj2，…，am?bjn成立，則稱p1是p2的子路徑，記為p1?p2.

定義2 設(shè)置一個支持數(shù)閾值δ，令support p為路徑p的支持數(shù)，表示RFID數(shù)據(jù)庫中包含路徑p的RFID數(shù)據(jù)元組的數(shù)量.若support p≥δ，則稱路徑p為頻繁路徑（frequency－path）.

2 挖掘頻繁路徑算法：MP－mine

2.1 構(gòu)建 MP－tree（移動路徑樹）

構(gòu)建MP－tree可以帶來兩方面好處：①只須掃描數(shù)據(jù)庫一次就可以挖掘出所有的頻繁移動路徑；②MP－tree屬于壓縮狀態(tài)，便于加載到存儲器中進行有效處理.

在MP－tree構(gòu)建過程中，用一個節(jié)點表來記錄所有不同標簽第一次出現(xiàn)的地址和總共的計數(shù)，MP－tree中的每個節(jié)點（用 MR－node表示）都采用以下的結(jié)構(gòu)存儲：MR－node：＝｛label，parent－link，next－link，children table｝，其中l(wèi)abel用來表示這個節(jié)點，parent－link和next－link是兩個指針，分別指向該節(jié)點的父節(jié)點和下一個節(jié)點，children table用來存儲該節(jié)點的所有孩子節(jié)點.對于每一個TR－tree，可用一個頭表來記錄時間序列的層次結(jié)構(gòu)，表中每個元素都設(shè)一個指針，表中的第n個元素就指向TR－tree中第n層的第1個節(jié)點.在TR－tree中每個節(jié)點都設(shè)一個指針，用于指向它的兄弟節(jié)點，TR－tree中每個節(jié)點都采用以下結(jié)構(gòu)存儲：TR－node：＝｛label，parent－link，peer－link，children table｝.

算法1：MP－tree構(gòu)建算法

輸入：物品的RFID移動路徑信息庫D；輸出：MP－tree.

第1步：從D中選取一條有序的移動路徑序列p，從p中分別提取路徑序列和時間序列；

第2步：MP－tree的插入，①從根節(jié)點開始將路徑序列插入MP－tree中；②用一個節(jié)點表記錄路徑中出現(xiàn)的節(jié)點的計數(shù)；③設(shè)置每個節(jié)點的parent－link和next－link；

第3步：TR－tree的插入，①在路徑序列的尾節(jié)點插入對應(yīng)的時間序列；②如果TR－tree是新構(gòu)建的，則用一個頭表來記錄時間序列的層次結(jié)構(gòu)，表中每個元素都設(shè)一個指針，表中的第n個元素就指向TR－tree中第n層的第1個節(jié)點；③設(shè)置TR－tree中每個插入節(jié)點的parent－link和peerlink；

第4步：如果在D中有更多的移動路徑序列，則回到第1步，否則返回當前的MP－tree.

2.2 MP－mine算法

算法2：MP－mine算法

輸入：一個MP－tree（MT），最小支持度閾值δ；輸出：所有頻繁的移動路徑序列.

第1步：瀏覽節(jié)點表中的每個標簽，將節(jié)點計數(shù)大于最小支持度閾值δ的節(jié)點存儲在集合M－L中；

第2步：如果M－L為空，則輸出MT的前綴模式并返回；

第3步：對集合M－L中的每個標簽l進行如下處理：①將每個標簽l對應(yīng)TR－tree中的所有不同節(jié)點以及計數(shù)存儲到集合L－T中，然后將L－T中計數(shù)大于δ的標簽存儲到集合TR－L中；②如果TR－L為空，則輸出MT的前綴模式并返回；③對TR－L中每個標簽t，以（l，t）作為前綴，重新構(gòu)造一個MP－tree MP′；④ 對于MP′，遞歸調(diào)用以上方法進行頻繁移動路徑挖掘.

整個挖掘過程采用深度優(yōu)先搜索（DFS）的方法，構(gòu)建MP－tree和挖掘頻繁的移動路徑采用遞歸的方法.

3 實驗與結(jié)果分析

為了進一步說明本文MP－mine算法的有效性，現(xiàn)將其與Apriori算法進行比較.本文通過對同一RFID路徑數(shù)據(jù)庫采用不同的支持度以及不同的路徑長度進行了實驗對比.實驗環(huán)境基于Windows XP SP3，內(nèi)存為2GB，CPU為AMD，2.0GHz，實驗環(huán)節(jié)使用Visual C＋＋6.0編寫，采用的實驗數(shù)據(jù)為基于某RFID物流管理系統(tǒng)中的人工合成數(shù)據(jù).

實驗1比較了兩種挖掘算法的運行時間.通過同一路徑數(shù)據(jù)庫下不同的最小支持度來比較兩種算法的效果，實驗結(jié)果如圖1所示.實驗1的路徑數(shù)據(jù)庫所具有的路徑數(shù)目為100 000，最小支持度閾值為0.1% ～0.5%.

由圖1可見，當最小支持度閾值較小時，MP－mine算法的優(yōu)勢比較明顯，因為最小支持度閾值較小時，相應(yīng)頻繁路徑的最大長度較大；隨著最小支持度閾值的不斷增大，Apriori算法的優(yōu)勢越發(fā)明顯.因為隨著最小支持度閾值的不斷增大，頻繁路徑的最大長度不斷減小，相應(yīng)的Apriori算法掃描數(shù)據(jù)庫次數(shù)減少.對于MP－mine自身，因為無論頻繁路徑長度如何變化，算法掃描數(shù)據(jù)庫的次數(shù)均為1，所以算法的運行時間較少.

實驗2通過不同大小的路徑數(shù)據(jù)庫比較了兩種挖掘算法的運行時間.該實驗采用的minSup為0.5，路徑數(shù)據(jù)庫大小從包含100 000條路徑到包含500 000條路徑，實驗結(jié)果如圖2所示.

圖1 不同最小支持度閾值下的運行時間比較Fig.1 Execution time for different support thresholds

圖2 不同路徑計數(shù)下的運行時間Fig.2 Execution time for different paths

由圖2可見，隨著數(shù)據(jù)庫中路徑數(shù)的不斷增大，兩種算法的運行時間都相應(yīng)增加，因為路徑數(shù)越大，掃描數(shù)據(jù)庫的時間越長；路徑數(shù)越大，MP－mine算法的優(yōu)勢越發(fā)明顯，這是因為隨著路徑數(shù)的不斷增大，Apriori算法將產(chǎn)生大量的候選項，同時掃描數(shù)據(jù)庫的時間也不斷增加，因此算法花費時間增加的速度越來越快.對于MP－mine自身，因為無論頻繁路徑長度如何變化，算法掃描數(shù)據(jù)庫的次數(shù)均為1，所以時間相應(yīng)增加的趨勢不是十分明顯.

［1］陳竹西，孫艷，胡孔法，等.基于路徑編碼的RFID數(shù)據(jù)壓縮技術(shù)研究［J］.揚州大學(xué)學(xué)報：自然科學(xué)版，2008，11（2）：53－56.

［2］GONZALEZ H，HAN Jia－wei，LI Xiao－lei，et al.Warehousing and analyzing massive RFID data sets［C］／／Proceedings of the 22nd International Conference on Data Engineering.Washington，DC：IEEE Computer Society，2006：83.

［3］CHAWATHE S S，KRISHNAMURTHY V，RAMACHANDRAN S，et al.Managing RFID data［C］／／Proceedings of the 30th International Conference on Very Large Data Bases.Toronto：Morgan Kaufmann，2004：1189－1195.

［4］PARK Sung－mee，SONG Jeong－h(huán)wan，KIM Chae－soo，et al.Load balancing method using connection pool in RFID middle ware［C］／／Proceedings of the Fifth ACIS International Conference on Software Engineering Research，Management and Applications.Busan：［s.n.］，2007：132－137.

［5］AL－JAROODI J，AZIZ J，MOHAMED N.Middle ware for RFID systems：an overview［C］／／Proceedings of the 2009 33rd Annual IEEE International Computer Software and Applications Conference.Washington，DC：IEEE Computer Society，2009：154－159.

［6］WANG Jian－yong，HAN Jia－wei.BIDE：efficient mining of frequent closed sequences［C］／／Proceedings of 20th International Conference on Data Engineering.Boston：IEEE Computer Society，2004：79－90.

［7］ZHANG Hong－jiang，YANG Qiang，SU Zhong.What Next：a prediction system for web requests using N－gram sequence models［C］／／Proceedings of the First International Conference on web Information Systems and Engineering.Washington，DC：IEEE Computer Society，2000：200－207.

［8］HAN Jia－wei，PEI Jian，YIN Yi－wen.Mining frequent patterns without candidate generation［C］／／Proceedings of the ACM SIGMOD International Conference on Management of Data.New York，NY：ACM，2000：1－12.

［9］PORKODI R，BHUVANESWARI V，RAJESH R，et al.An improved association rule mining technique for XML data using XQUERY and apriori algorithm ［C］／／Proceedings of the 2009IEEE International Advance Computing Conference.Patiala：［s.n.］，2009：1510－1514.

［10］SHI Yong－ge，ZHOU Yi－qun.An improved apriori algorithm ［C］／／Proceedings of 2010IEEE International Conference on Granular Computing.Washington，DC：IEEE Computer Society，2010：759－762.?