一種基于序列模式的RFID 數(shù)據(jù)挖掘算法

張長(zhǎng)海

摘要：隨著大數(shù)據(jù)海量增長(zhǎng)和物聯(lián)網(wǎng)技術(shù)快速發(fā)展，RFID（射頻識(shí)別技術(shù)）數(shù)據(jù)挖掘技術(shù)已成為當(dāng)前研究的熱點(diǎn).為此，該文重點(diǎn)研究了RFID移動(dòng)數(shù)據(jù)特點(diǎn)，并根據(jù)數(shù)據(jù)特性提出一種高效的基于序列模式的RFID移動(dòng)數(shù)據(jù)挖掘算法。該算法將RFID移動(dòng)數(shù)據(jù)庫(kù)分為兩部分進(jìn)行挖掘，首先采用高效的序列模式挖掘算法挖掘LOCATION序列數(shù)據(jù)，然后對(duì)挖掘LOCATION序列數(shù)據(jù)集進(jìn)行TIME序列數(shù)據(jù)挖掘，進(jìn)而組合LOCATION序列集和TIME序列集產(chǎn)生有效的RFID移動(dòng)數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明該算法能夠有效地挖掘RFID移動(dòng)序列數(shù)據(jù)，處理時(shí)間短，效率高。

關(guān)鍵詞： RFID移動(dòng)數(shù)據(jù)； 序列模式技術(shù)； 數(shù)據(jù)挖掘技術(shù)

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）13-0259-02

Abstract： With the Internet of Things technology， RFID （radio frequency identification technology） data mining technology has become a hot research. focus on the logistics and transport characteristics of RFID data path， proposed an efficient path for RFID-based sequential pattern data mining algorithms the algorithm uses divide and conquer technique， place the RFID data into sequence data and time series data mining， respectively， and thus the effective combination of location data and time series data sequence to generate a valid path to RFID data. Case analysis shows that through the algorithm： in the RFID path database， this method can efficiently tap the RFID path data.

Key words： RFID data； sequential patterns； data mining

隨著信息化社會(huì)推進(jìn)，物聯(lián)網(wǎng)技術(shù)越來(lái)越受到關(guān)注，國(guó)家政府大力支持物聯(lián)網(wǎng)產(chǎn)業(yè)發(fā)展，其中RFID技術(shù)產(chǎn)業(yè)更是成為社會(huì)熱點(diǎn)。RFID技術(shù)產(chǎn)業(yè)主要包含射頻識(shí)別收發(fā)端、短距離無(wú)線傳輸端和后臺(tái)數(shù)據(jù)處理端，其中數(shù)據(jù)處理端尤為重要?，F(xiàn)在社會(huì)RFID技術(shù)已經(jīng)應(yīng)用到各行各業(yè)，有圖書館圖書信息管理、零售商商品信息管理、物流倉(cāng)儲(chǔ)管理、信息化物流運(yùn)輸?shù)取＝鼛啄陙?lái)，隨著物聯(lián)網(wǎng)技術(shù)產(chǎn)業(yè)快速發(fā)展，RFID產(chǎn)業(yè)產(chǎn)生大量RFID數(shù)據(jù)。那么，如何能夠有效地挖掘到有價(jià)值的RFID數(shù)據(jù)，能夠?yàn)槠笫聵I(yè)單位提供更加有效的決策支持尤為重要，因此，RFID數(shù)據(jù)挖掘逐漸成為社會(huì)研究熱點(diǎn)。

世界上很多零售商都已經(jīng)開始使用RFID技術(shù)，尤其是在零售產(chǎn)業(yè)的倉(cāng)儲(chǔ)和物流環(huán)節(jié)。隨著電子信息技術(shù)推進(jìn)，電子標(biāo)簽價(jià)格逐步下降，各大零售商開始在大量物品商品包裝上黏貼RFID電子標(biāo)簽，以能夠有效地跟蹤監(jiān)控商品。商品上部署的RFID系統(tǒng)生成移動(dòng)軌跡，對(duì)于供應(yīng)鏈管理等有很大價(jià)值，同時(shí)RFID系統(tǒng)會(huì)產(chǎn)生大量的RFID數(shù)據(jù)，面對(duì)這種海量式、數(shù)據(jù)爆炸式的RFID數(shù)據(jù)，如何挖掘出有意義的數(shù)據(jù)尤為重要。目前社會(huì)上存在一些RFID數(shù)據(jù)挖掘方法：如采用傳統(tǒng)的序列模式挖掘方法，這種方法沒(méi)有考慮RFID數(shù)據(jù)特性，把RFID數(shù)據(jù)看做一個(gè)整體數(shù)據(jù)集進(jìn)行挖掘，因此，挖掘效率低，挖掘結(jié)果不夠精確。為了能夠有效地挖掘RFID移動(dòng)數(shù)據(jù)，本文提出一種RFID移動(dòng)數(shù)據(jù)挖掘算法，該算法該算法將RFID移動(dòng)數(shù)據(jù)庫(kù)分為兩部分進(jìn)行挖掘，首先采用高效的序列模式挖掘算法挖掘LOCATION序列數(shù)據(jù)，然后對(duì)挖掘LOCATION序列數(shù)據(jù)集進(jìn)行TIME序列數(shù)據(jù)挖掘，進(jìn)而組合LOCATION序列集和TIME序列集產(chǎn)生有效的RFID移動(dòng)數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明該算法能夠有效地挖掘RFID移動(dòng)序列數(shù)據(jù)，處理時(shí)間短，效率高。

1 基于序列模式的RFID數(shù)據(jù)挖掘算法

1.1 RFID數(shù)據(jù)挖掘基本概念

RFID序列數(shù)據(jù)庫(kù)如圖表1所示，該數(shù)據(jù)庫(kù)內(nèi)有4條RFID數(shù)據(jù)記錄，如何從這四條數(shù)據(jù)記錄挖掘出有價(jià)值的信息數(shù)據(jù)至關(guān)重要。首先，4條數(shù)據(jù)記錄中的（濰坊）、（青島）、（濟(jì)南）、（泰安）表示RFID移動(dòng)數(shù)據(jù)中的地點(diǎn)數(shù)據(jù)，可稱之為地點(diǎn)序列數(shù)據(jù)；數(shù)據(jù)記錄中的（1）、（1）、（1）、（2）表示RFID移動(dòng)數(shù)據(jù)中的時(shí)間數(shù)據(jù)，可稱之為時(shí)間序列數(shù)據(jù)。因此，有如下定義：

定義1 如果RFID數(shù)據(jù)庫(kù)中有一條記錄：p=（s1， l1）（s2， l2）...（sn， ln），那么，該記錄中的tl=（s1）（s2）...（sn）稱之為該記錄的RFID地點(diǎn)序列，其為該數(shù)據(jù)庫(kù)的主要數(shù)據(jù)參數(shù)。

定義2 如果RFID數(shù)據(jù)庫(kù)中有一條記錄：p=（s1， l1）（s2， l2）...（sn， ln），那么，該記錄中的ql=（l1）（l2）...（ln）稱之為該記錄的RFID時(shí)間序列，其為該數(shù)據(jù)庫(kù)的次要數(shù)據(jù)參數(shù)。

上表四條記錄中，第一條記錄和第三條記錄中的地點(diǎn)序列數(shù)據(jù){（濰坊）、（青島）、（濟(jì)南）、（泰安）}出現(xiàn)過(guò)2次，假設(shè)設(shè)置該數(shù)據(jù)庫(kù)支持?jǐn)?shù)閾值為2，那么該地點(diǎn)序列不存在長(zhǎng)度更長(zhǎng)的序列，因此，稱之為頻繁地點(diǎn)序列。有如下定義：

定義3假如存在一條路徑序列數(shù)據(jù)T，且不存在路徑序列數(shù)據(jù)S，使得TS，并且數(shù)據(jù)庫(kù)支持?jǐn)?shù)閾值二者相同，即support（T）=support（S），那么就稱T為頻繁RFID序列數(shù)據(jù)。

例1 表1所示的數(shù)據(jù)庫(kù)中，第一條序列數(shù)據(jù)（濰坊， 1）（青島， 1）（濟(jì)南， 1）（泰安， 2）中的{（濰坊）、（青島）、（濟(jì)南）、（泰安）}為地點(diǎn)序列數(shù)據(jù)，{（1）、（1）、（1）、（2）}為時(shí)間序列數(shù)據(jù)。

例2表1所示的數(shù)據(jù)庫(kù)中，前四條序列數(shù)據(jù)的地點(diǎn)序列數(shù)據(jù)分別是{（濰坊）、（青島）、（濟(jì)南）、（泰安）}、{（濰坊）、（青島）、（泰安）}、{（濰坊）、（青島）、（濟(jì)南）、（泰安）}、{（濰坊）、（青島）、（泰安）}。如果該RFID序列數(shù)據(jù)庫(kù)支持?jǐn)?shù)閾值為2，那么地點(diǎn)序列數(shù)據(jù){（濰坊）、（青島）、（濟(jì)南）、（泰安）}滿足最小支持?jǐn)?shù)2，即滿足在RFID數(shù)據(jù)庫(kù)記錄中出現(xiàn)2次條件，同時(shí)該地點(diǎn)序列數(shù)據(jù){（濰坊）、（青島）、（濟(jì)南）、（泰安）}又不存在超序列， 因此，稱之為頻繁地點(diǎn)序列數(shù)據(jù)。

1.2基于序列模式的RFID數(shù)據(jù)挖掘算法描述

本文中將采用分治策略，即將RFID數(shù)據(jù)庫(kù)中的序列數(shù)據(jù)分為地點(diǎn)序列數(shù)據(jù)和時(shí)間序列數(shù)據(jù)進(jìn)行處理，從地點(diǎn)序列數(shù)據(jù)庫(kù)中挖掘出頻繁的地點(diǎn)序列，然后對(duì)頻繁地點(diǎn)序列進(jìn)行映射，形成候選時(shí)間序列集合，然后采用數(shù)據(jù)庫(kù)挖掘方法挖掘候選時(shí)間序列集合，該方法簡(jiǎn)單有效，挖掘數(shù)據(jù)完整。

基于序列模式的RFID數(shù)據(jù)挖掘算法描述如下：

輸入： RFID sequential_DB， Min_Support.

輸出： The full frequent RFID data for CD.

1： 投影RFID序列數(shù)據(jù)庫(kù)，構(gòu)造RFID地點(diǎn)序列數(shù)據(jù)庫(kù)集合DataB=L_sequence（RFID sequential DB）。

2： 按照給定最小支持度閾值計(jì)算該RFID序列數(shù)據(jù)庫(kù)的最小支持?jǐn)?shù)值為Min_count=|DataB|*Min_Support。

3： 調(diào)用經(jīng)典序列數(shù)據(jù)挖掘算法APRIORI算法，生成頻繁地點(diǎn)序列數(shù)據(jù)集。

4： 投影頻繁地點(diǎn)序列數(shù)據(jù)集，生成與頻繁地點(diǎn)序列數(shù)據(jù)集對(duì)應(yīng)的候選時(shí)間序列數(shù)據(jù)集。

5： 調(diào)用經(jīng)典序列數(shù)據(jù)挖掘算法APRIORI算法，生成頻繁時(shí)間序列數(shù)據(jù)集。

6： 將頻繁地點(diǎn)序列數(shù)據(jù)集和頻繁時(shí)間序列數(shù)據(jù)集進(jìn)行組合，依據(jù)APRIORI性質(zhì)檢測(cè)組合數(shù)據(jù)集的封閉性，同時(shí)刪除非封閉數(shù)據(jù)集。

7： 返回生成CD。

2 RFID數(shù)據(jù)挖掘算法實(shí)例分析

物聯(lián)網(wǎng)系統(tǒng)下層采集數(shù)據(jù)，經(jīng)過(guò)數(shù)據(jù)清洗等組成RFID路徑序列數(shù)據(jù)庫(kù)。本文舉例如表1所示。假設(shè)該RFID路徑序列數(shù)據(jù)庫(kù)最小支持?jǐn)?shù)閾值Min_support=0.5，那么挖掘整個(gè)RFID頻繁數(shù)據(jù)序列過(guò)程如下：

第一步，投影RFID路徑序列數(shù)據(jù)庫(kù)，生成RFID地點(diǎn)序列數(shù)據(jù)庫(kù)集合，如表2所示。

3 結(jié)束語(yǔ)

隨著物聯(lián)網(wǎng)技術(shù)高速發(fā)展，將產(chǎn)生海量式數(shù)據(jù)。為此，本文提出一種挖掘RFID路徑序列數(shù)據(jù)的算法。該算法將RFID移動(dòng)數(shù)據(jù)庫(kù)分為兩部分進(jìn)行挖掘，首先采用高效的序列模式挖掘算法挖掘LOCATION序列數(shù)據(jù)，然后對(duì)挖掘LOCATION序列數(shù)據(jù)集進(jìn)行TIME序列數(shù)據(jù)挖掘，進(jìn)而組合LOCATION序列集和TIME序列集產(chǎn)生有效的RFID移動(dòng)數(shù)據(jù)。通過(guò)實(shí)例測(cè)試分析，該算法能夠有效挖掘RFID價(jià)值數(shù)據(jù)，為企業(yè)提供智能決策支持。今后我們將重點(diǎn)研究對(duì)該RFID挖掘算法的優(yōu)化及更新。

參考文獻(xiàn)：

[1] 馬傳香， 余嘯， 李偉亮， 等. MR-GSP： 基于Map-Reduce的序列模式挖掘算法[J]. 計(jì)算機(jī)應(yīng)用研究，2015（11）.

[2] 鄧廣彪. 規(guī)范化序列模式在讀者借閱行為模式挖掘的應(yīng)用研究[J]. 計(jì)算機(jī)時(shí)代， 2014（4）.

[3] 馮麗蕓. 數(shù)據(jù)挖掘在我國(guó)醫(yī)保方面應(yīng)用綜述[J]. 電腦知識(shí)與技術(shù)， 2014（3）.

[4] 胡孔法， 陳竹西. 現(xiàn)代物流系統(tǒng)中的頻繁封閉路徑挖掘算法[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2009（4）： 229-235.

[5] Zhang Changhai， Hu Kongfa. FMGSP： An Efficient Method of Mining Global Sequential Patterns[C]. Hainan， China： FSKD，2007 ： 761-765.