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

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

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

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

RFID數(shù)據(jù)一般由三元組組成，形如（EPC，location，time），其中EPC是對(duì)每個(gè)物品進(jìn)行唯一標(biāo)識(shí)的電子產(chǎn)品編碼，location表示閱讀器讀取發(fā)生的位置，time表示閱讀器讀取發(fā)生的時(shí)間.用數(shù)對(duì)pi＝（li，ti）表示對(duì)象在時(shí)間ti訪(fǎng)問(wèn)了li，規(guī)定如果p1＝p2，則必須使t1＝t2并且l1＝l2，這樣將一系列記錄集成起來(lái)就能得到物品的移動(dòng)路徑信息，形如〈（l1，t1），（l2，t2），…，（li，ti），…，（lm，tm）〉.令T＝〈（l1，t1），（l2，t2），…，（lm，tm）〉，稱(chēng)T 是一個(gè)長(zhǎng)度為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成立，則稱(chēng)p1是p2的子路徑，記為p1?p2.

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

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

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

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

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

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

輸入：物品的RFID移動(dòng)路徑信息庫(kù)D；輸出：MP－tree.

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

第2步：MP－tree的插入，①?gòu)母?jié)點(diǎn)開(kāi)始將路徑序列插入MP－tree中；②用一個(gè)節(jié)點(diǎn)表記錄路徑中出現(xiàn)的節(jié)點(diǎn)的計(jì)數(shù)；③設(shè)置每個(gè)節(jié)點(diǎn)的parent－link和next－link；

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

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

2.2 MP－mine算法

算法2：MP－mine算法

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

第1步：瀏覽節(jié)點(diǎn)表中的每個(gè)標(biāo)簽，將節(jié)點(diǎn)計(jì)數(shù)大于最小支持度閾值δ的節(jié)點(diǎn)存儲(chǔ)在集合M－L中；

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

由圖1可見(jiàn)，當(dāng)最小支持度閾值較小時(shí)，MP－mine算法的優(yōu)勢(shì)比較明顯，因?yàn)樽钚≈С侄乳撝递^小時(shí)，相應(yīng)頻繁路徑的最大長(zhǎng)度較大；隨著最小支持度閾值的不斷增大，Apriori算法的優(yōu)勢(shì)越發(fā)明顯.因?yàn)殡S著最小支持度閾值的不斷增大，頻繁路徑的最大長(zhǎng)度不斷減小，相應(yīng)的Apriori算法掃描數(shù)據(jù)庫(kù)次數(shù)減少.對(duì)于MP－mine自身，因?yàn)闊o(wú)論頻繁路徑長(zhǎng)度如何變化，算法掃描數(shù)據(jù)庫(kù)的次數(shù)均為1，所以算法的運(yùn)行時(shí)間較少.

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

圖1 不同最小支持度閾值下的運(yùn)行時(shí)間比較Fig.1 Execution time for different support thresholds

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

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

［1］陳竹西，孫艷，胡孔法，等.基于路徑編碼的RFID數(shù)據(jù)壓縮技術(shù)研究［J］.揚(yáng)州大學(xué)學(xué)報(bào)：自然科學(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.?