多維頻繁路徑算法在RFID圖書館的應(yīng)用

雷赟

（江西理工大學(xué)圖書館 贛州 341000）

多維頻繁路徑算法在RFID圖書館的應(yīng)用

雷赟

（江西理工大學(xué)圖書館 贛州 341000）

深入研究了應(yīng)用于圖書館的RFID數(shù)據(jù)集，使用RFID多維頻繁路徑挖掘算法，按照不同的閾值、不同的尺度以及不同的維度，將圖書館的RFID數(shù)據(jù)劃分為兩部分，即多維模式與序列模式。經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證可以看出，順序處理非路徑維數(shù)據(jù)算法和順序處理路徑數(shù)據(jù)算法兩者都可以有效地挖掘出RFID多維頻繁路徑，并且兩個(gè)算法都可以記錄不同類型讀者借閱圖書的詳細(xì)情況。通過(guò)快速有效挖掘出的射頻識(shí)別圖書館管理系統(tǒng)中所獲得信息的相關(guān)數(shù)據(jù)，方便更加合理有效地進(jìn)行圖書分配，以及需要購(gòu)買圖書分類的趨勢(shì)目錄，基于資源的分配依據(jù)，為圖書館管理者作出正確的決定。

RFID 多維頻繁路徑挖掘 圖書館管理

RFID技術(shù)在圖書館應(yīng)用得越來(lái)越廣泛，它所產(chǎn)生的路徑信息也變得越來(lái)越多，研究和管理RFID系統(tǒng)所產(chǎn)生的海量數(shù)據(jù)也變得越來(lái)越重要，充分發(fā)掘其價(jià)值內(nèi)涵是實(shí)現(xiàn)和推動(dòng)RFID應(yīng)用的關(guān)鍵因素。

一、圖書館RFID數(shù)據(jù)

圖書館RFID數(shù)據(jù)的內(nèi)涵：圖書館RFID數(shù)據(jù)可以表示成一個(gè)三元組集合（EPC,Location,Time）。EPC是唯一的，用來(lái)識(shí)別一本書的電子代碼。Location則為圖書所在的位置，Time則是掃描圖書的時(shí)間。由于在RFID數(shù)據(jù)庫(kù)中加上了路徑數(shù)據(jù)以及EPC標(biāo)識(shí)，要想快速?gòu)腞FID數(shù)據(jù)庫(kù)獲取數(shù)據(jù)，最關(guān)鍵的技術(shù)就是要挖掘移動(dòng)趨勢(shì)的頻繁路徑數(shù)據(jù)信息。

二、RFID多維數(shù)據(jù)結(jié)構(gòu)

RFID多維數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵：對(duì)RFID數(shù)據(jù)倉(cāng)庫(kù)的結(jié)構(gòu)進(jìn)行詳細(xì)解析，主要包括：（1）信息表，包括圖書名稱、作者、出版社、圖書類別等；（2）停駐表，儲(chǔ)存在相同地點(diǎn)存放的所有圖書的信息；（3）路徑表，存放停留記錄的路徑信息，根據(jù)停駐表中的關(guān)聯(lián)信息來(lái)生成一條路徑記錄。以上三個(gè)抽象的信息就成為一個(gè)RFID多維數(shù)據(jù)結(jié)構(gòu)。

三、RFID多維頻繁路徑挖掘算法

多維路徑的定義：將形如二元組的結(jié)構(gòu)形式稱為多維路徑[1]125。

本文提出了Dim-path（順序處理非路徑維數(shù)據(jù)）與Path—dim（順序處理路徑數(shù)據(jù)）兩種算法。

算法l：Dim-path算法

IN：即RFID數(shù)據(jù)庫(kù)以及最小支持?jǐn)?shù)閾值

OUT：封閉多維路徑集合（CMP）

具體算法描述：

Step1：根據(jù)非路徑維數(shù)據(jù)，選用BUC-1ike算法，對(duì)其進(jìn)行挖掘封閉多維模式；

Step2：由上一步挖掘的數(shù)據(jù)建立多維模式投影數(shù)據(jù)庫(kù)；

Step3：選用MCP算法，挖掘封閉多維模式的路徑投影數(shù)據(jù)庫(kù)；

Step4：得到準(zhǔn)封閉多維路徑，并將其加入到集合CMP；

Step5：檢測(cè)CMP集合是否封閉，把所有非封閉的多維路徑都刪除，最后輸出CMP集合。

算法2：Path-dim算法

IN：即RFID數(shù)據(jù)庫(kù)以及最小支持?jǐn)?shù)閾值

OUT：封閉多維路徑集合（CMP）

具體算法描述：

Step1：選用MCP算法，對(duì)路徑數(shù)據(jù)進(jìn)行挖掘封閉路徑；

Step2：為第一步得到的封閉路徑建立路徑投影數(shù)據(jù)庫(kù)；

Step3：選用BUC-like算法，挖掘封閉多維模式的路徑投影數(shù)據(jù)庫(kù)；

Step4：得到的準(zhǔn)封閉多維路徑，并將其加入到集合CMP；

Step5：檢測(cè)CMP集合是否封閉，把所有非封閉多維路徑都刪除，最后輸出CMP集合。

這兩種算法同樣都是使用MCP算法挖掘封閉的多維路徑[2]55。首先，從查找位置數(shù)據(jù)開始，建立位置數(shù)據(jù)庫(kù)序列，然后挖掘封閉位置序列，建立一個(gè)停留時(shí)間投影數(shù)據(jù)庫(kù)。合并之后生成準(zhǔn)封閉路徑，最后檢測(cè)封閉性，把非封閉多維路徑全部刪除，獲得封閉路徑[3]105。

Dim-path算法在挖掘封閉多維模式時(shí)，選擇的是BUC-1ike算法，圖1的BUC樹顯示的是多維模式的挖掘過(guò)程。

對(duì)表1的數(shù)據(jù)執(zhí)行Dim-path算法，進(jìn)行封閉頻繁多維路徑挖掘。

Step1：根據(jù)非路徑維數(shù)據(jù)，選用BUC-1ike算法，對(duì)其進(jìn)行挖掘封閉多維模式；

設(shè)置min=2。根據(jù)圖3.1，按照順序，進(jìn)行挖掘，得到集合CMD={（高級(jí)程序設(shè)計(jì)C++）（*）:4;（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）:2;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）:2}。

Step2:構(gòu)建多維模式投影數(shù)據(jù)庫(kù)；

PDB（高級(jí)程序設(shè)計(jì)C++.*）={（f1,1）（f2,3）（f4,5）（f5, 9）,（f1,1）（f2,3）（f4,5）（f5,6）,（f1,2）（f2,3）（f4,5）（f5,6）,（f1,2）（f2,3）（f3,5）（f4,5）}；

PDB（高級(jí)程序設(shè)計(jì)C++.西安電子科技大學(xué)出版社）={（f1,1）（f2,3）（f4,5）（f5,9）,（f1,1）（f2,3）（f4,5）（f5,6）}；

PDB（高級(jí)程序設(shè)計(jì)C++.北京理工大學(xué)出版社）={（f1,2）（f2,3）（f4,5）（f5,6）,（f1,2）（f2,3）（f3,5）（f4,5）}；

Step3：選用MCP算法，挖掘封閉多維模式的路徑投影數(shù)據(jù)庫(kù)；

CP（高級(jí)程序設(shè)計(jì)C++.*）={（f1,*）（f4,*）:4;（f1,2）（f4, *）:3;（f1,*）（f2,3）（f4,5）（f5,*）:3;（f1,2）（f2,3）（f4,3）（f5,*）:3;（f1,*）（f2,3）（f4,5）（f5,6）:2}；

CP（高級(jí)程序設(shè)計(jì)C++.西安電子科技大學(xué)出版社）= {（f1,*）（f2,3）（f4,5）（f5,*）:2}；

CP（高級(jí)程序設(shè)計(jì)C++.北京理工大學(xué)出版社）={（f1, 2）（f2,3）（f4,*）:2}；

Step4：合并封閉多維模式和封閉路徑，得到CMP集合；

CMP={（高級(jí)程序設(shè)計(jì)C++）（*）（f1,*）（f4,*）:4;（高級(jí)程序設(shè)計(jì)C++）（*）（f1,*）（f2,3）（f4,5）（f5,*）:3;（高級(jí)程序設(shè)計(jì)C++）（*）（f1,2）（f2,3）（f4,5）（f5,*）:2;（高級(jí)程序設(shè)計(jì)C++）（*）（f1,*）（f2,3）（f4,5）（f5,6）:2;（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）（f1,*）（f2,3）（f4,5）（f5,*）:2;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）（f1,2）（f2,3）（f4,*）:2}。

Step5：檢測(cè)封閉性，刪除非封閉多維路徑；

最后（f1,2）（f4,*）:2;不是封閉多維路徑，被刪除，執(zhí)行完畢。

對(duì)表1的數(shù)據(jù)執(zhí)行Path-dim算法，進(jìn)行封閉頻繁多維路徑挖掘。

Step1：選用MCP算法，對(duì)路徑數(shù)據(jù)進(jìn)行挖掘封閉路徑；

設(shè)置min=2。選用MCP算法，挖掘封閉路徑CP={（f1, *）（f4,*）:3;（f1,2）（f4,*）:2;（f1,*）（f2,3）（f4,5）（f5,*）:3;（f1,2）（f2,3）（f4,5）（f5,*）:2;（f1,*）（f2,3）（f4,5）（f5,6）:2}；

Step2：構(gòu)建路徑投影數(shù)據(jù)庫(kù)；

PDF（f1,*）（f4,*）={（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）;（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）}；

PDF（f1,2）（f4,*）={（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）}；

PDF（f1,*）（f2,3）（f4,5）（f5,*）={（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）;（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）}；

PDF（f1,2）（f2,3）（f4,5）（f5,*）={（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）}；

PDF（f1,*）（f2,3）（f4,5）（f5,6）={（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）}；

Step3：選擇利用BUC-like算法，挖掘封閉多維模式；

CMD（f1,*）（f4,*）={（高級(jí)程序設(shè)計(jì)C++）（*）:3;（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）:2;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）:1}；

CMD（f1,2）（f4,*）={（高級(jí)程序設(shè)計(jì)C++）（*）:2;（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）:1;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）:1}；

CMD（f1,*）（f2,3）（f4,5）（f5,*）={（高級(jí)程序設(shè)計(jì)C++）（*）:3;（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）: 2;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）:1}；

CMD（f1,2）（f2,3）（f4,5）（f5,*）={（高級(jí)程序設(shè)計(jì)C++）（*）:2}；

CMD（f1,*）（f2,3）（f4,5）（f5,6）={（高級(jí)程序設(shè)計(jì)C++）（*）:2}；

Step4：得到的準(zhǔn)封閉多維路徑，并將其加入到集合CMP；

圖1 樹

圖2 不同最小支持度閾值下算法執(zhí)行時(shí)間比較

圖3 在不同維度下比較算法的執(zhí)行時(shí)間

圖4 尺度不同時(shí)比較算法時(shí)間

圖5 不同密度算法的操作比較

CMP={（高級(jí)程序設(shè)計(jì)C++）（*）（f1,*）（f4,*）:3;（高級(jí)程序設(shè)計(jì)C++）（*）（f1,*）（f2,3）（f4,5）（f5,*）:3;（高級(jí)程序設(shè)計(jì)C++）（*）（f1,2）（f2,3）（f4,5）（f5,*）:2;（高級(jí)程序設(shè)計(jì)C++）（*）（f1,*）（f2,3）（f4,5）（f5,6）:2;（高級(jí)程序設(shè)計(jì)C++）（西安電子科技大學(xué)出版社）（f1,*）（f2,3）（f4,5）（f5,*）:2;（高級(jí)程序設(shè)計(jì)C++）（北京理工大學(xué)出版社）（f1,2）（f2,3）（f4,*）:1}。

Step5：最后刪除非封閉多維路徑。

四、在圖書館中應(yīng)用的實(shí)驗(yàn)結(jié)果分析

本文將通過(guò)以下幾個(gè)實(shí)驗(yàn)的比較來(lái)進(jìn)一步驗(yàn)證Dim-Path和Path-Dim算法的可行性和準(zhǔn)確性。

實(shí)驗(yàn)環(huán)境是CPUIntelCorei5，4G內(nèi)存，2TB硬盤；Microsoft Windows XP；Microsoft Visual C++6.0。

實(shí)驗(yàn)使用的數(shù)據(jù)是模擬數(shù)據(jù)。支持度用支持?jǐn)?shù)與數(shù)據(jù)庫(kù)記錄數(shù)的比值來(lái)表示。

表1 RFID數(shù)據(jù)庫(kù)示例

實(shí)驗(yàn)1：取最小支持度閾值（a）若干，非路徑維維度為3，RFID圖書館數(shù)據(jù)庫(kù)中存有6萬(wàn)條數(shù)據(jù)。實(shí)驗(yàn)得出的結(jié)果如圖2所示。

由圖2可知，隨著a的增大，執(zhí)行算法所需要的時(shí)間逐漸降低[4]89。同樣的，Path-dim算法最終算法的運(yùn)行所需時(shí)間明顯縮短了。

實(shí)驗(yàn)2：取若干個(gè)非路徑維度，RFID圖書館數(shù)據(jù)庫(kù)中存有6萬(wàn)條數(shù)據(jù)，最小支持度閾值為0.01。實(shí)驗(yàn)得出的結(jié)果如圖3所示。

分別進(jìn)行了路徑維數(shù)和非路徑維度的挖掘，并分離出駐留時(shí)間序列和位置序列的數(shù)據(jù)，該方法明顯降低了算法的執(zhí)行時(shí)間。在Dim-Path算法執(zhí)行后可能會(huì)出現(xiàn)封閉頻繁路徑模式的空集合；同樣的，Path-Dim算法也可能會(huì)出現(xiàn)封閉頻繁多維模式的空集合。Dim-Path算法的復(fù)雜度要高于Path-Dim算法。因此Dim-path算法花費(fèi)的時(shí)間比Path-dim算法花費(fèi)的時(shí)間長(zhǎng)。

實(shí)驗(yàn)3：RFID圖書館數(shù)據(jù)庫(kù)存儲(chǔ)從6萬(wàn)條數(shù)據(jù)增加到10萬(wàn)條，最小支持度閾值為0.01。實(shí)驗(yàn)得出的結(jié)果如圖4所示。

由圖4可以看出,數(shù)據(jù)庫(kù)記錄的次數(shù)越多，實(shí)現(xiàn)這兩種算法的時(shí)間越長(zhǎng)，不同的是，非路徑維算法的時(shí)間增加明顯大于路徑算法。

實(shí)驗(yàn)4：以RFID圖書館數(shù)據(jù)庫(kù)中存儲(chǔ)了6萬(wàn)條記錄為例，設(shè)置非路徑維維度為3，并且設(shè)置最小支持度閾值為0.01。實(shí)驗(yàn)得出的結(jié)果如圖5所示。從圖5可以看出，隨著密度的降低，非路徑維屬性的值將逐漸分散，而封閉的尺寸模式的數(shù)量將逐漸變小。

從圖5可以看出，非路徑維密度大，則Dim-Path算法挖掘所得到的封閉頻繁多維模式更多，效率低，Path-Dim算法要挖掘的多維停留時(shí)間序列更少，效率高。密度減少后，Dim-Path算法的工作量變小。Path-Dim算法在密度降低后，工作量增大。

實(shí)驗(yàn)得出：當(dāng)封閉多維模式數(shù)量較多的時(shí)候，選擇Path-dim算法，則效率相對(duì)更高。當(dāng)封閉多維模式數(shù)量較少的時(shí)候，選擇Dim-path算法，則效率相對(duì)更高[5]15。Dim-path算法對(duì)數(shù)據(jù)進(jìn)行了多次掃描，所以效率低。依據(jù)數(shù)據(jù)庫(kù)，來(lái)選擇合適的算法，可以取得較為理想的挖掘效果。

本文深入研究了多維頻繁路徑挖掘算法，針對(duì)RFID技術(shù)所生成的海量路徑數(shù)據(jù)集，提出了兩種算法，即Dim—path與Path-dim挖掘算法實(shí)驗(yàn)結(jié)果表明，本文所提出的算法可以高效準(zhǔn)確的對(duì)RFID圖書館數(shù)據(jù)有效地進(jìn)行多維頻繁路徑挖掘。本文算法能高效挖掘RFID圖書館管理系統(tǒng)中的相關(guān)數(shù)據(jù)所獲取的信息，方便更加合理有效的圖書分配，以及需要購(gòu)買圖書分類的趨勢(shì)目錄，基于資源的分配依據(jù)，為圖書館管理者作出正確的決定。

[1]宗瑩.分析RFID技術(shù)在圖書館中的應(yīng)用[J].電子技術(shù)與軟件工程.2016（12）.

[2]江波.基于RFID的圖書館館藏管理方法研究[J].計(jì)算機(jī)集成制造系統(tǒng).2015（5）.

[3]陳嘉懿,曲建峰,李鮑.高校圖書館超高頻RFID數(shù)據(jù)模型規(guī)范研究[J].大學(xué)圖書館學(xué)報(bào).2014（5）.

[4]王莉.圖書館RFID標(biāo)簽應(yīng)用比較研究[J].圖書館理論與實(shí)踐. 2013（3）.

[5]向瓊.基于UFHRFID的圖書館智能管理系統(tǒng)分析與實(shí)現(xiàn)[D].廈門大學(xué)，2014.

★作者雷赟，江西理工大學(xué)圖書館副研究館員，研究方向維圖書館數(shù)字化自動(dòng)化。

2014年江西省藝術(shù)科學(xué)規(guī)劃項(xiàng)目（YG2014093）。

G201

A

2016-09-08