基于時間索引的0-N數(shù)據(jù)結(jié)構(gòu)在序列模式挖掘算法中的應(yīng)用

劉彥保，袁 倩，雷 珍，朱文婷

(延安大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，陜西延安716000)

基于時間索引的0-N數(shù)據(jù)結(jié)構(gòu)在序列模式挖掘算法中的應(yīng)用

劉彥保，袁 倩，雷 珍，朱文婷

(延安大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，陜西延安716000)

在0-N數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上結(jié)合時間索引，建立根據(jù)時間片段劃分的序列數(shù)據(jù)塊，通過對原始數(shù)據(jù)存儲結(jié)構(gòu)的改進達到減小掃描范圍的目的，提高序列模式挖掘算法的效率。

時間索引；數(shù)據(jù)結(jié)構(gòu)；序列模式挖掘

GSP(generalized sequential patterns)算法是基于候選產(chǎn)生-測試的序列模式挖掘算法。該算法主要存在兩個缺陷：一是需要掃描多次數(shù)據(jù)庫，候選序列集合長度每增加1，就要掃描一次原始序列數(shù)據(jù)庫，造成嚴(yán)重的性能瓶頸；二是產(chǎn)生候選序列眾多，如果原始序列數(shù)據(jù)庫巨大，容易造成內(nèi)存的溢出[1]。文獻[2]通過改變數(shù)據(jù)結(jié)構(gòu)減少對原始數(shù)據(jù)的掃描次數(shù)。文獻[3]提出了一種多時間間隔的序列模式挖掘算法，可以分區(qū)間精確顯示多時間間隔的序列模式挖掘結(jié)果。文獻[4]中作者在支持度的計算中，對數(shù)據(jù)構(gòu)造了索引，通過索引指向需要遍歷的客戶序列以達到減小算法搜索空間的目的。

本文通過對原始數(shù)據(jù)中存儲結(jié)構(gòu)的分析，在0-N數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上通過引入時間索引使原始數(shù)據(jù)在存儲時根據(jù)時間區(qū)間進行劃分，使整個掃描過程在起始階段就減小了掃描范圍，以達到提高運算效率的目的。

1 0-N數(shù)據(jù)結(jié)構(gòu)

在之前對序列模式挖掘問題的研究中序列數(shù)據(jù)結(jié)構(gòu)以序列為索引如表1所示。文獻[2]中針對車輛路徑預(yù)測問題，提出了以項目為索引的0-N數(shù)據(jù)結(jié)構(gòu)如表2所示。假設(shè)有候選序列〈a,b〉，需要檢測該候選序列的支持度，在序列數(shù)據(jù)結(jié)構(gòu)中，需通過掃描整個數(shù)據(jù)庫來實現(xiàn)，但是在0-N數(shù)據(jù)結(jié)構(gòu)中僅僅只需要掃描a、b所在的列即可，減少了工作量提高了算法的運行效率。

表1 序列結(jié)構(gòu)數(shù)據(jù)表

表2 0-N數(shù)據(jù)結(jié)構(gòu)表

2 改進的存儲結(jié)構(gòu)

在數(shù)據(jù)挖掘中，人們往往更為關(guān)注近期的發(fā)展趨勢，所以在此基礎(chǔ)上受上述思想和方法的啟發(fā)，對原始數(shù)據(jù)的數(shù)據(jù)存儲結(jié)構(gòu)進行了改進，對數(shù)據(jù)構(gòu)造索引，以劃分的時間區(qū)間建立索引，時間區(qū)間可以是24小時或是一個星期也可以是一個月，根據(jù)不同的時長需要將原始數(shù)據(jù)進行劃分。本文通過對文獻[2]和文獻[4]的研究，在0-N數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上對其建立時間索引，以劃分的時間區(qū)間段為索引，通過索引指向需要掃描的序列，按照時間區(qū)間將整個原始數(shù)據(jù)劃分為多個數(shù)據(jù)區(qū)間，其結(jié)構(gòu)如下所示，現(xiàn)假設(shè)將時間區(qū)間劃分為T1，T2，T3階段，每個階段的數(shù)據(jù)表如表4-6所示，則在進行數(shù)據(jù)掃描前僅需要對需要檢測的數(shù)據(jù)項進行時間范圍的判斷，假設(shè)時間t?T1內(nèi)，則需要掃描索引表3，找出T1時間段所指向的數(shù)據(jù)表D1，找到后跳轉(zhuǎn)至該數(shù)據(jù)表進行掃描。

表3 時間索引表

表4 T1時間段數(shù)據(jù)表D1

表5 T2時間段數(shù)據(jù)表D2

表6 T3時間段數(shù)據(jù)表D3

3 實例分析

在超市購物中，客戶的運動在超市商品的排列以及人們購物習(xí)慣的影響下，存在著一定的規(guī)律，使預(yù)測客戶下一個購買的商品成為可能，假設(shè)有一系列分布在貨架上的商品為節(jié)點構(gòu)成的商品網(wǎng)絡(luò)，客戶購買商品的規(guī)律性表現(xiàn)在客戶總是往返于重復(fù)的節(jié)點，不同客戶的購物習(xí)慣可能會導(dǎo)致客戶購買順序發(fā)生改變的現(xiàn)象，但是其經(jīng)過節(jié)點的次序具有規(guī)律性。

現(xiàn)假設(shè)有一系列分布在超市中的商品為節(jié)點構(gòu)成的商品網(wǎng)絡(luò)，那么客戶的購買痕跡就可以用節(jié)點的順序排列來表示?，F(xiàn)有A-E表示在超市中商品的分布情況，構(gòu)成以商品為節(jié)點的購物網(wǎng)絡(luò)如圖1所示。設(shè)I={Ii,i=1，2，…，m}是一個項目集合，項目集在本問題中表示節(jié)點(商品)，軌跡序列〈s1,s2,…,sm〉表示項目的順序排列，時間〈t1,t2,…,tm〉表示該軌跡完成的時間即用戶完成購買行為，在之前的研究中，采用記錄到達每一節(jié)點的最初時間以及到達下一節(jié)點的間隔時間來進行多時間的劃分，計算符合元素間隔及滑動窗口。本文所采用的具有時間索引的0-N數(shù)據(jù)結(jié)構(gòu)中根據(jù)超市購物的特點僅使用軌跡完成時間為結(jié)束時間并將其記錄在時間屬性中，時間屬性只需要表明在這一時刻用戶結(jié)束了購物活動。結(jié)束時間在超市購物系統(tǒng)中以客戶在收銀臺付款交易成功時的時間為該用戶購買軌跡完成時間，則序列數(shù)據(jù)庫DB由〈t,sid,S〉表示，其中t表示完整序列產(chǎn)生的時間，sid表示序列號，S表示軌跡序列，對客戶購買軌跡數(shù)據(jù)轉(zhuǎn)換為具有時間屬性的序列數(shù)據(jù)庫如表7所示，轉(zhuǎn)化成具有時間屬性的0-N數(shù)據(jù)結(jié)構(gòu)如表8所示，并將其按時間劃分進一步轉(zhuǎn)化為具有時間劃分的0-N的結(jié)構(gòu)數(shù)據(jù)表如表9-11所示，表9表示時間索引表，表10表11分別表示表示T10時間段指向的數(shù)據(jù)表D10，T11時間段指向的數(shù)據(jù)表D11。

表7 具有時間屬性的客戶購買軌跡序列數(shù)據(jù)庫

表8 具有時間屬性的客戶購買痕跡0-N結(jié)構(gòu)數(shù)據(jù)表

表9 時間索引表

表10 T10時間段指向數(shù)據(jù)表D10

表11 T11時間段指向數(shù)據(jù)D11

圖1 模擬的購物網(wǎng)絡(luò)圖

現(xiàn)假設(shè)有序列〈T1,T2,…,Tm〉表示劃分的時間段，假設(shè)按照m=24對24小時進行劃分則對應(yīng)的有T1表示時間從00∶00至01∶00以此類推(在此按照等價劃分進行區(qū)間劃分)，并在存儲數(shù)據(jù)T時采用指針數(shù)據(jù)類型且指向?qū)?yīng)時間段產(chǎn)生的軌跡序列表如圖1所示，假如需要對t0=10∶05的客戶購買軌跡進行預(yù)測，首先需要確定當(dāng)前時間t0包含在那個時間段內(nèi)，經(jīng)判斷t0是屬于T10區(qū)間段的，掃描表10時間索引表找到T10指向的數(shù)據(jù)表，發(fā)現(xiàn)T10對應(yīng)的數(shù)據(jù)庫為D10，則找到數(shù)據(jù)表D10并對其進行掃描操作，最后通過序列模式挖掘算法產(chǎn)生返回值。

4 結(jié)果分析

本文以超市購物為前提，記錄每次購物完成的最終時間，并在0-N數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上采用時間索引，根據(jù)時間索引將原始數(shù)據(jù)劃分為多個數(shù)據(jù)塊，采用這種數(shù)據(jù)存儲結(jié)構(gòu)可以使掃描數(shù)據(jù)時只需要掃描某一時間片段內(nèi)的數(shù)據(jù)，從而使需要掃描的數(shù)據(jù)減少，減少掃描時間，并且僅引入結(jié)束時間屬性，減少了數(shù)據(jù)的存儲空間，同時也可以省去在計算過程中計算時間間隔的過程，采用時間索引的0-N數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)可以使序列模式挖掘算法的時間復(fù)雜度以及空間復(fù)雜度降低，提高序列模式挖掘算法的效率。

5 總結(jié)

本文通過在0-N數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上引入時間索引，通過索引指向需要掃描的數(shù)據(jù)減少掃描空間，減少了候選序列測試的工作量，減小了整個過程的時間復(fù)雜度以及空間復(fù)雜度，提高了算法的運算效率。但這一方法同樣也存在著缺陷，例如：因為只是掃描部分時間內(nèi)的的序列所以會導(dǎo)致搜索結(jié)果不是很精確，這個問題也是后續(xù)研究的重點之一。

[1]黨育民.序列模式挖掘算法研究[J].江西師范大學(xué)學(xué)報(自然科學(xué)版)，2009，33(5)：604-607.

[2]李杰，王娜娜，李志鵬，等.面向個性化交通信息服務(wù)的車輛行駛路徑關(guān)聯(lián)規(guī)則挖掘[J].系統(tǒng)工程理論與實踐，2013，33(12)：3209-3215.

[3]李廣源，馬楠，曹丹陽.一種多時間間隔序列模式挖掘算法[J].微電子學(xué)與計算機，2012，29(4)：10-13.

[4]劉亞男.基于時間間隔的事件序列頻繁模式挖掘算法研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2011.

[責(zé)任編輯 畢 偉]

Application of Sequential Pattern Mining Algorithm Based on the Time Index 0-NData Structure

LIU Yan-bao,YUAN QIAN,LEI ZHEN,ZHU Wen-ting

(College of Mathematics and Computer Science,Yan′an University,Yan′an 716000,China)

On the basis of the 0-Ndata structure combined with the construct time index,set up the sequence data block according to the time slice,Through the change of the data structure of the original data to achieve the purpose of reducing the scanning range to improving the efficiency of sequential pattern mining.

time index; data structure; sequential pattern mining

2015-09-23

劉彥保(1964—)，男，陜西綏德人，延安大學(xué)教授。

TP311

A

1004-602X(2015)04-0030-03