多維頻繁路徑算法在RFID圖書館的應用

雷赟

（江西理工大學圖書館 贛州 341000）

多維頻繁路徑算法在RFID圖書館的應用

雷赟

（江西理工大學圖書館 贛州 341000）

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

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

RFID技術在圖書館應用得越來越廣泛，它所產生的路徑信息也變得越來越多，研究和管理RFID系統所產生的海量數據也變得越來越重要，充分發掘其價值內涵是實現和推動RFID應用的關鍵因素。

一、圖書館RFID數據

圖書館RFID數據的內涵：圖書館RFID數據可以表示成一個三元組集合（EPC,Location,Time）。EPC是唯一的，用來識別一本書的電子代碼。Location則為圖書所在的位置，Time則是掃描圖書的時間。由于在RFID數據庫中加上了路徑數據以及EPC標識，要想快速從RFID數據庫獲取數據，最關鍵的技術就是要挖掘移動趨勢的頻繁路徑數據信息。

二、RFID多維數據結構

RFID多維數據結構的內涵：對RFID數據倉庫的結構進行詳細解析，主要包括：（1）信息表，包括圖書名稱、作者、出版社、圖書類別等；（2）停駐表，儲存在相同地點存放的所有圖書的信息；（3）路徑表，存放停留記錄的路徑信息，根據停駐表中的關聯信息來生成一條路徑記錄。以上三個抽象的信息就成為一個RFID多維數據結構。

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

多維路徑的定義：將形如二元組的結構形式稱為多維路徑[1]125。

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

算法l：Dim-path算法

IN：即RFID數據庫以及最小支持數閾值

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

具體算法描述：

Step1：根據非路徑維數據，選用BUC-1ike算法，對其進行挖掘封閉多維模式；

Step2：由上一步挖掘的數據建立多維模式投影數據庫；

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

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

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

算法2：Path-dim算法

IN：即RFID數據庫以及最小支持數閾值

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

具體算法描述：

Step1：選用MCP算法，對路徑數據進行挖掘封閉路徑；

Step2：為第一步得到的封閉路徑建立路徑投影數據庫；

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

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

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

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

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

對表1的數據執行Dim-path算法，進行封閉頻繁多維路徑挖掘。

Step1：根據非路徑維數據，選用BUC-1ike算法，對其進行挖掘封閉多維模式；

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

Step2:構建多維模式投影數據庫；

PDB（高級程序設計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（高級程序設計C++.西安電子科技大學出版社）={（f1,1）（f2,3）（f4,5）（f5,9）,（f1,1）（f2,3）（f4,5）（f5,6）}；

PDB（高級程序設計C++.北京理工大學出版社）={（f1,2）（f2,3）（f4,5）（f5,6）,（f1,2）（f2,3）（f3,5）（f4,5）}；

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

CP（高級程序設計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（高級程序設計C++.西安電子科技大學出版社）= {（f1,*）（f2,3）（f4,5）（f5,*）:2}；

CP（高級程序設計C++.北京理工大學出版社）={（f1, 2）（f2,3）（f4,*）:2}；

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

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

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

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

對表1的數據執行Path-dim算法，進行封閉頻繁多維路徑挖掘。

Step1：選用MCP算法，對路徑數據進行挖掘封閉路徑；

設置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：構建路徑投影數據庫；

PDF（f1,*）（f4,*）={（高級程序設計C++）（西安電子科技大學出版社）;（高級程序設計C++）（西安電子科技大學出版社）;（高級程序設計C++）（北京理工大學出版社）;（高級程序設計C++）（北京理工大學出版社）}；

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

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

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

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

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

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

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

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

CMD（f1,2）（f2,3）（f4,5）（f5,*）={（高級程序設計C++）（*）:2}；

CMD（f1,*）（f2,3）（f4,5）（f5,6）={（高級程序設計C++）（*）:2}；

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

圖1 樹

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

圖3 在不同維度下比較算法的執行時間

圖4 尺度不同時比較算法時間

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

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

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

四、在圖書館中應用的實驗結果分析

本文將通過以下幾個實驗的比較來進一步驗證Dim-Path和Path-Dim算法的可行性和準確性。

實驗環境是CPUIntelCorei5，4G內存，2TB硬盤；Microsoft Windows XP；Microsoft Visual C++6.0。

實驗使用的數據是模擬數據。支持度用支持數與數據庫記錄數的比值來表示。

表1 RFID數據庫示例

實驗1：取最小支持度閾值（a）若干，非路徑維維度為3，RFID圖書館數據庫中存有6萬條數據。實驗得出的結果如圖2所示。

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

實驗2：取若干個非路徑維度，RFID圖書館數據庫中存有6萬條數據，最小支持度閾值為0.01。實驗得出的結果如圖3所示。

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

實驗3：RFID圖書館數據庫存儲從6萬條數據增加到10萬條，最小支持度閾值為0.01。實驗得出的結果如圖4所示。

由圖4可以看出,數據庫記錄的次數越多，實現這兩種算法的時間越長，不同的是，非路徑維算法的時間增加明顯大于路徑算法。

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

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

實驗得出：當封閉多維模式數量較多的時候，選擇Path-dim算法，則效率相對更高。當封閉多維模式數量較少的時候，選擇Dim-path算法，則效率相對更高[5]15。Dim-path算法對數據進行了多次掃描，所以效率低。依據數據庫，來選擇合適的算法，可以取得較為理想的挖掘效果。

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

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

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

[3]陳嘉懿,曲建峰,李鮑.高校圖書館超高頻RFID數據模型規范研究[J].大學圖書館學報.2014（5）.

[4]王莉.圖書館RFID標簽應用比較研究[J].圖書館理論與實踐. 2013（3）.

[5]向瓊.基于UFHRFID的圖書館智能管理系統分析與實現[D].廈門大學，2014.

★作者雷赟，江西理工大學圖書館副研究館員，研究方向維圖書館數字化自動化。

2014年江西省藝術科學規劃項目（YG2014093）。

G201

A

2016-09-08