嚴(yán)愛(ài)俐，劉漫丹

(華東理工大學(xué) 信息科學(xué)與工程學(xué)院，上海 200237)

0 引 言

融合移動(dòng)互聯(lián)網(wǎng)、大數(shù)據(jù)、云計(jì)算、物聯(lián)網(wǎng)等現(xiàn)代化信息技術(shù)，推動(dòng)校園教學(xué)管理、教師教學(xué)模式、學(xué)生學(xué)習(xí)模式等方面的改革，為廣大師生提供了全面智能感知、個(gè)性化的服務(wù)[1,2]。隨著高校的信息化建設(shè)，會(huì)產(chǎn)生一些校園數(shù)據(jù)，例如一卡通消費(fèi)數(shù)據(jù)、圖書(shū)館借閱數(shù)據(jù)等，通過(guò)對(duì)這些數(shù)據(jù)進(jìn)行頻繁序列模式挖掘能夠發(fā)現(xiàn)很多隱藏的信息。

常用的序列模式挖掘算法有Apriori算法[3]、FP-Growth(frequent pattern growth)算法[4]、FreeSpan算法[5]及PrefixSpan算法[6]等。針對(duì)數(shù)據(jù)量大、分布范圍廣的數(shù)據(jù)集，本文選擇用PrefixSpan算法進(jìn)行序列挖掘。但該算法在執(zhí)行過(guò)程中，需要遞歸構(gòu)造投影數(shù)據(jù)集，從而影響了算法的運(yùn)行時(shí)間。目前，已有不少學(xué)者針對(duì)上述問(wèn)題提出了改進(jìn)。文獻(xiàn)[7]中通過(guò)支持度末尾判斷和后綴指針偽投影的方法進(jìn)行改進(jìn)，文獻(xiàn)[8]中提出基于后綴索引的PrefixSpan算法和基于投影數(shù)據(jù)庫(kù)的PrefixSpan改進(jìn)算法，文獻(xiàn)[9]中借助已生成的序列模式投影提出AprioriAll-PrefixSpan改進(jìn)算法，等等。針對(duì)PrefixSpan算法存在的缺陷，本文從閾值、運(yùn)行效率和運(yùn)行內(nèi)存角度出發(fā)，分別提出相應(yīng)的改進(jìn)舉措。

1 相關(guān)定義及工作

本文采用PrefixSpan算法從獲取的校園數(shù)據(jù)中挖掘出用戶的頻繁軌跡模式，PrefixSpan算法是由JW Han等[6]提出的，算法的思想與Apriori算法類(lèi)似。從長(zhǎng)度為1的前綴開(kāi)始挖掘序列模式，搜索對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)得到長(zhǎng)度為1的前綴對(duì)應(yīng)的頻繁序列，然后遞歸挖掘長(zhǎng)度為2的前綴所對(duì)應(yīng)的頻繁序列。以此類(lèi)推，一直遞歸到不能挖掘到更長(zhǎng)的前綴挖掘?yàn)橹埂?/p>

下面對(duì)PrefixSpan算法中涉及的相關(guān)概念抽象成具體的數(shù)學(xué)表達(dá)式，具體定義如下：

定義1 序列：假設(shè)存在序列數(shù)據(jù)集D={S1,S2,…,Sj,…,SN}， 其中序列Sj(1≤j≤N) 由m項(xiàng)構(gòu)成，即Sj={ij,1,ij,2,…ij,k,…,ij,m}, (1≤k≤m)，ij,k表示Sj中的第k項(xiàng)；令序列s={ij,k}， 則稱(chēng)序列s是序列Sj的子序列，序列Sj為序列s的超序列；

定義2 支持度(Support)：一個(gè)序列的支持度被定義為數(shù)據(jù)集中包含該序列的記錄數(shù)占數(shù)據(jù)集總序列數(shù)的比值。假設(shè)序列數(shù)據(jù)集D={S1,S2,…,SN}， 序列Sj={ij,1,ij,2,…ij,k,…,ij,m}， 則子序列s={ij,k} 的支持度即

(1)

定義3 最小支持度(Minimum Support)：用戶定義衡量支持度的一個(gè)閾值，表示項(xiàng)在統(tǒng)計(jì)意義上的最低重要性，記作min_sup；

定義4 頻繁序列：假設(shè)數(shù)據(jù)集D中存在子序列s，滿足其支持度≥最小支持度，即sup(s)≥min_sup， 則子序列s稱(chēng)為頻繁序列，若子序列s由n項(xiàng)組成，則子序列s又可稱(chēng)為頻繁n-序列；

定義5 投影數(shù)據(jù)庫(kù)：假設(shè)有序列Sj={ij,1,ij,2,…ij,k,…,ij,m}， 其中子序列sj={ij,1,ij,2,…,ij,k}, (1≤k≤m)， 則稱(chēng)序列sj是序列Sj的序列前綴，序列Sj為序列sj的序列投影；子序列s′j={ij,k+1,ij,k+2,…,ij,m}， 稱(chēng)其為序列Sj的序列后綴；由s′j(1≤j≤N) 組成的數(shù)據(jù)庫(kù)稱(chēng)為投影數(shù)據(jù)庫(kù)。

本文是基于PrefixSpan算法的改進(jìn)，下面將通過(guò)表1中的具體實(shí)例解釋PrefixSpan算法的整個(gè)運(yùn)行過(guò)程，設(shè)定min_sup=0.5， 對(duì)應(yīng)的最小支持度閾值次數(shù)為：min_sup*序列總數(shù)N=0.5*4=2次。

表1 序列數(shù)據(jù)集實(shí)例

首先對(duì)序列數(shù)據(jù)集第一次掃描，統(tǒng)計(jì)所有項(xiàng)出現(xiàn)的次數(shù)：{a}：4、：4、{c}：4、iqck0qg：3、{e}：2、{f}：2、{g}：1。其中{g}出現(xiàn)次數(shù)不滿足最小支持度閾值次數(shù)，則頻繁1-序列集如下：{a}、、{c}、2issq00、{e}、{f}。將這些頻繁1-序列作為前綴并找出對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)，見(jiàn)表2。

表2 頻繁1-序列前綴及對(duì)應(yīng)投影數(shù)據(jù)庫(kù)

接著以前綴ckismiw為例介紹整個(gè)挖掘過(guò)程，其它序列前綴挖掘方法類(lèi)似。對(duì)序列{a}對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)進(jìn)行統(tǒng)計(jì)：{a}：1、：2、{c}：3、{e}：1、{f}：1、{_f}：1，其中滿足min_sup閾值次數(shù)的是、{c}，則頻繁2-序列為{db}、{dc}。以頻繁2-序列為前綴找出對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)，見(jiàn)表3。

表3 頻繁2-序列前綴及對(duì)應(yīng)投影數(shù)據(jù)庫(kù)

同理對(duì)2-序列前綴的投影數(shù)據(jù)庫(kù)中各項(xiàng)進(jìn)行統(tǒng)計(jì)，前綴{dc}中項(xiàng)出現(xiàn)2次得到頻繁3-序列{dcb}對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)見(jiàn)表4。根據(jù)投影數(shù)據(jù)庫(kù)發(fā)現(xiàn)沒(méi)有滿足條件的項(xiàng)，因此無(wú)法產(chǎn)生頻繁4-序列，以mwwec0o為序列前綴挖掘的所有頻繁序列如下：c8yyuke、{db}、{dc}、{dcb}。

表4 頻繁3-序列前綴及對(duì)應(yīng)投影數(shù)據(jù)庫(kù)

2 動(dòng)態(tài)多最小支持度前綴投影挖掘算法(DMS-PrefixSpan)

由于PrefixSpan算法的基本思想是，根據(jù)確定的最小支持度min_sup從序列集合中挖掘出滿足條件的頻繁序列。因此min_sup的選擇就顯得極為重要，如果min_sup設(shè)置過(guò)高會(huì)導(dǎo)致一些重要的隱藏信息被丟失，反之設(shè)置過(guò)低則挖掘的結(jié)果中混入大量干擾信息。針對(duì)用戶的頻繁軌跡挖掘，其移動(dòng)軌跡中通常會(huì)包含一些熱點(diǎn)地區(qū)，但這些地區(qū)在軌跡中的重要程度相對(duì)較低。例如在校園中大部分用戶會(huì)在特定時(shí)間出現(xiàn)在食堂、教室等地點(diǎn)，如果僅根據(jù)這些數(shù)據(jù)希望挖掘出各個(gè)用戶之間的社會(huì)關(guān)系，很大程度上會(huì)得到所有人的行為軌跡都是相似的。另外，同一個(gè)地點(diǎn)對(duì)不同用戶的重要性是不同的。例如在博物館工作的工作人員和去博物館游覽的游客，明顯能夠看出博物館在后者軌跡模式中重要性明顯超過(guò)前者，在這種情況下確定的工作人員和游客去博物館的最小支持度應(yīng)該有所區(qū)別。

其次，用戶不同的需求促使用戶有不同的行為，隨著年齡、角色、生活環(huán)境的變化需求也在不斷發(fā)生變化。例如，校園網(wǎng)絡(luò)中的用戶在大二、大三選修的課程不同，因此其上課的教室、時(shí)間、同學(xué)也是不同的；選修的課程安排在上學(xué)期或者下學(xué)期，會(huì)對(duì)其某段時(shí)間的生活作息產(chǎn)生影響。因此通過(guò)分析用戶行為的轉(zhuǎn)變，試著分析其背后行為轉(zhuǎn)變的原因?qū)W(xué)生管理和資源分配具有指導(dǎo)意義。

針對(duì)上文提到的單一最小支持度和行為模式變化問(wèn)題，本文將從以下兩個(gè)方面：多最小支持度和動(dòng)態(tài)頻繁序列挖掘進(jìn)行討論。此外，由于使用數(shù)據(jù)集時(shí)間跨度很長(zhǎng)且用戶數(shù)據(jù)量很多，因此算法改進(jìn)還需要考慮到內(nèi)存消耗問(wèn)題。本文將引入動(dòng)態(tài)多最小支持度的PrefixSpan改進(jìn)算法稱(chēng)為動(dòng)態(tài)多最小支持度前綴投影挖掘算法，簡(jiǎn)稱(chēng)DMS-Prefix-Span算法。

2.1 序列壓縮和序列匹配

由于PrefixSpan算法挖掘的結(jié)果存在大量的冗余，為了減少挖掘結(jié)果的內(nèi)存占用，提出序列壓縮和序列匹配兩個(gè)概念，將引入序列壓縮和序列匹配的PrefixSpan算法稱(chēng)為最長(zhǎng)頻繁項(xiàng)集挖掘算法，簡(jiǎn)稱(chēng)L-PrefixSpan算法。其中序列壓縮和序列匹配的概念如下：

假設(shè)從數(shù)據(jù)集D中存在頻繁n-序列，頻繁n-序列是從頻繁1-序列中衍生增長(zhǎng)而來(lái)的，可以發(fā)現(xiàn)頻繁1～(n-1) 序列為頻繁n-序列的子序列，則只保留頻繁n-序列即可，這種操作稱(chēng)為序列壓縮。

遍歷整個(gè)挖掘結(jié)果序列集合，若其中某序列為其它序列的子序列，則去除這條冗余的子序列，以保證結(jié)果中所有序列互相不為子序列或超序列的關(guān)系，這種操作稱(chēng)為序列匹配。

根據(jù)圖1可以發(fā)現(xiàn)，挖掘的頻繁項(xiàng)如下： {a},{ab},{ac},{af},{abc},{abb},{acb},{abcf},{abbf}， 經(jīng)過(guò)序列壓縮可得到如下的結(jié)果： {abcf},{abbf},{acb},{af}； 根據(jù)序列壓縮結(jié)果可以進(jìn)一步發(fā)現(xiàn)：序列 {af} 為序列 {abcf} 和 {abbf} 的子序列，則經(jīng)過(guò)序列匹配可得到最終的結(jié)果： {abcf},{abbf},{acb}。 以此類(lèi)推，可以發(fā)現(xiàn)經(jīng)過(guò)序列壓縮和序列匹配，挖掘的頻繁序列會(huì)大大減少，因此占用內(nèi)存空間也會(huì)減少。

圖1 PrefixSpan算法挖掘結(jié)果示例

2.2 多最小支持度的計(jì)算

某無(wú)線網(wǎng)絡(luò)中所有用戶的軌跡序列集合為UR={R1,R2,…,Ru,…,RN}， 該無(wú)線網(wǎng)絡(luò)中采集的所有地點(diǎn)區(qū)域項(xiàng)集為L(zhǎng)={l1,l2,…,li,…,lM}， 其中M為該無(wú)線網(wǎng)絡(luò)中地點(diǎn)區(qū)域總數(shù)。則地點(diǎn)區(qū)域li的地點(diǎn)熱度用群體地點(diǎn)分布頻率(frequency of locations in the group，F(xiàn)LG)表示，如式(2)所示

(2)

式中：N(li) 為統(tǒng)計(jì)的軌跡序列中含有地點(diǎn)區(qū)域li的序列出現(xiàn)次數(shù)，N為軌跡序列中所有軌跡序列總數(shù)。

假設(shè)無(wú)線網(wǎng)絡(luò)中的某用戶u其軌跡序列集合為Ru={ru,1,ru,2,…,ru,x,…,ru,Ku}， 其中Ku為該用戶軌跡序列總長(zhǎng)度，元素ru,x為軌跡點(diǎn)記錄，ru,x=(tu,x,lu,x) 表示用戶u的第x個(gè)軌跡記錄的出現(xiàn)時(shí)間tu,x和出現(xiàn)地點(diǎn)lu,x。 用戶個(gè)人的地點(diǎn)偏好用個(gè)人地點(diǎn)分布頻率(frequency of locations in the personal tracks，F(xiàn)LP)表示，如式(3)所示

(3)

式中：K(lu,i) 為用戶u軌跡序列中含有地點(diǎn)區(qū)域li的序列出現(xiàn)次數(shù)。

綜合考慮地點(diǎn)熱度和個(gè)人地點(diǎn)概率分布，需要將FLG(li) 和FLP(lu,i) 分別根據(jù)其與最小支持度的變化規(guī)律進(jìn)行非線性映射轉(zhuǎn)換。由于FLP(lu,i) 表示用戶u的地點(diǎn)偏好程度，計(jì)算得到的數(shù)值越大表明地點(diǎn)li對(duì)用戶越重要。選擇映射函數(shù)的時(shí)候要考慮到min_sup與用戶在地點(diǎn)出現(xiàn)的頻率成正比，所以選用的映射函數(shù)在 [0,1] 范圍內(nèi)單調(diào)遞增的自然對(duì)數(shù)函數(shù)進(jìn)行變換，具體函數(shù)如式(4)所示

f(x)=ln(x+1)

(4)

FLG(li) 表示地點(diǎn)熱度，數(shù)值越大則表明地點(diǎn)li的熱度越高。而min_sup與該地點(diǎn)在整個(gè)軌跡序列中出現(xiàn)的次數(shù)成反比，因此選擇映射函數(shù)在 [0,1] 范圍內(nèi)為單調(diào)遞減的函數(shù)。由于指數(shù)函數(shù)和對(duì)數(shù)函數(shù)互為反函數(shù)，所以FLG(li) 的映射函數(shù)選用標(biāo)準(zhǔn)對(duì)數(shù)函數(shù)，具體如式(5)所示

(5)

SuperMap建庫(kù)的核心工作是對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)換處理，轉(zhuǎn)換處理的標(biāo)準(zhǔn)數(shù)據(jù)能直接應(yīng)用于后續(xù)數(shù)據(jù)的處理，采用的建庫(kù)模式是從臨時(shí)庫(kù)到標(biāo)準(zhǔn)庫(kù)再到調(diào)查庫(kù)。

f(x)=exp(-πx2)

(6)

根據(jù)式(2)至式(6)，可得用戶u在地點(diǎn)li的最小支持度，記為MIS(lu,i)， 具體表達(dá)式如式(7)所示

MIS(lu,i)=ln(FLP(lu,i)+1)*exp(-π(FLG(li))2)

(7)

根據(jù)式(7)，求得用戶u在該無(wú)線網(wǎng)絡(luò)中所有地點(diǎn)的多最小支持度閾值，記為MMS(L)， 具體表達(dá)式如式(8)所示

MMS(L)={MIS(lu,1),MIS(lu,2),…,MIS(lu,i),…,MIS(lu,M)}

(8)

2.3 動(dòng)態(tài)頻繁序列挖掘

一般情況下，對(duì)數(shù)據(jù)流頻繁項(xiàng)的挖掘都是基于某個(gè)時(shí)間段對(duì)數(shù)據(jù)的分析和研究[10]。主要有兩個(gè)原因：一是數(shù)據(jù)量過(guò)于龐大挖掘過(guò)程會(huì)消耗很多時(shí)間，二是不同時(shí)間段的數(shù)據(jù)重要程度不同。根據(jù)數(shù)據(jù)流中的不同時(shí)序范圍，可以把數(shù)據(jù)流模型劃分為如下3類(lèi)：快照模型、界標(biāo)模型和滑動(dòng)窗口模型[11]。參考文獻(xiàn)[12]中提到，根據(jù)挖掘模式結(jié)果集合的精簡(jiǎn)程度，可以分為全集模式挖掘方法和壓縮模式挖掘方法等；壓縮模式主要包括閉合模式、最大模式、top-k模式以及三者之間的組合模式。根據(jù)2.1節(jié)中提到的序列壓縮和序列匹配，本文中的挖掘模式為壓縮模式中的最大模式挖掘。

挖掘用戶頻繁軌跡的過(guò)程中，綜合考慮到數(shù)據(jù)量和時(shí)效性兩方面，選擇用滑動(dòng)窗口模型，即窗口的起始時(shí)間和結(jié)束時(shí)間都是變化的。在整個(gè)過(guò)程中，存在用戶本身在不同時(shí)段對(duì)不同地點(diǎn)偏好程度不同的問(wèn)題，因此用戶在不同時(shí)間段內(nèi)不同地點(diǎn)的min_sup是不同的。文獻(xiàn)[13-15]中涉及上述問(wèn)題，無(wú)論是采用滑動(dòng)窗口模型還是衰減窗口模型，無(wú)論數(shù)據(jù)集是密集數(shù)據(jù)集或者稀疏數(shù)據(jù)集，均根據(jù)所有之前時(shí)間窗口的事務(wù)占比確定項(xiàng)的權(quán)重，但本文的權(quán)值是基于前一個(gè)時(shí)間窗口的事務(wù)占比，通過(guò)不斷循環(huán)該操作既沒(méi)有忽視之前的數(shù)據(jù)，同時(shí)也大大縮短了計(jì)算消耗的時(shí)間，其對(duì)于內(nèi)存消耗、運(yùn)行時(shí)間及實(shí)驗(yàn)結(jié)果均有所改善。

用戶u的軌跡序列集合為Ru={ru,1,ru,2,…,ru,x,…,ru,Ku} 且ru,x=(tu,x,lu,x)， 以周期T為窗口大小劃分用戶軌跡，假設(shè)用戶數(shù)據(jù)的起始時(shí)間為start、 結(jié)束時(shí)間為end， 則用戶的軌跡序列的滑動(dòng)窗口劃分方式如下： 〈start,start+T,…,start+kT,…,end〉， 且有n個(gè)周期。

當(dāng)Tk=[start+(k-1)T,start+kT], 1≤k≤n時(shí)，由式(7)可得用戶u在地點(diǎn)li的最小支持度，記為MIS(luTk,i)， 則用戶u在n個(gè)周期內(nèi)地點(diǎn)li的最小支持度MMS(lu,i) 如式(9)所示

MMS(lu,i)={MIS(luT1,i),MIS(luT2,i),…,MIS(luTn,i)}

(9)

(10)

(11)

根據(jù)Tk周期內(nèi)用戶u的在地點(diǎn)li出現(xiàn)的概率為Pu,li， 在計(jì)算T(k+1)周期地點(diǎn)li的最小支持度時(shí)需要迭加權(quán)值計(jì)算，具體計(jì)算如式(12)所示

MIS(luT(k+1),i)=MIS(luT(k+1),i)×e-PuTk,li,k=2,3,…,n

(12)

根據(jù)式(12)可以計(jì)算出用戶u在T1～Tn周期地點(diǎn)li所有的最小支持度。

對(duì)M個(gè)地點(diǎn)重復(fù)上述步驟，得到用戶u在該無(wú)線網(wǎng)絡(luò)中所有地點(diǎn)的動(dòng)態(tài)多最小支持度閾值，記為DMS(L)， 具體表達(dá)式如式(13)所示

DMS(L)={MMS(lu,1),MMS(lu,2),…,MMS(lu,i),…,MMS(lu,M)}

(13)

2.4 DMS-PrefixSpan算法的實(shí)現(xiàn)步驟

具體挖掘步驟如下：

步驟1 首先對(duì)移動(dòng)軌跡的序列數(shù)據(jù)集預(yù)處理，然后將數(shù)據(jù)集以T為周期劃分為n個(gè)區(qū)域稱(chēng)為T(mén)k(k=1,2,…,n)， 令k=1；

步驟2 從Tk開(kāi)始根據(jù)式(7)計(jì)算所有地點(diǎn)的多最小支持度閾值MMS(LTk)；

步驟3 結(jié)合MMS(LTk) 根據(jù)式(12)計(jì)算所有地點(diǎn)的動(dòng)態(tài)多最小支持度閾值DMS(LTk)={MIS(luTk,1),MIS(luTk,2),…,MIS(luTk,i),…,MIS(luTk,M)}；

步驟4 對(duì)Tk區(qū)域內(nèi)所有出現(xiàn)的地點(diǎn)進(jìn)行計(jì)數(shù)，找出所有滿足閾值DMS(LTk) 的地點(diǎn)保存作為頻繁i-項(xiàng)集，令i=1；

步驟5 對(duì)于每個(gè)長(zhǎng)度為i且滿足閾值MIS(luTk,i) 要求的前綴進(jìn)行遞歸挖掘：①找出前綴對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)，如果投影數(shù)據(jù)庫(kù)為空，則遞歸返回；②統(tǒng)計(jì)投影數(shù)據(jù)庫(kù)中各個(gè)地點(diǎn)出現(xiàn)的次數(shù)，將滿足閾值MIS(luTk,i) 要求的地點(diǎn)與當(dāng)前的前綴合并，得到新的前綴；若不存在滿足要求的地點(diǎn)，則遞歸返回；③令i=i+1， 保存合并后的前綴作為頻繁i-項(xiàng)集，并遞歸返回步驟5；

步驟6 遍歷頻繁軌跡模式集合，進(jìn)行序列匹配，剔除挖掘的冗余頻繁序列；

步驟7 根據(jù)式(10)計(jì)算不同地點(diǎn)在用戶的軌跡中出現(xiàn)的概率，令k=k+1， 遞歸返回步驟2；

經(jīng)過(guò)n次周期的計(jì)算，獲得用戶在不同周期內(nèi)所有的頻繁序列集。

3 某高校用戶頻繁項(xiàng)挖掘

3.1 數(shù)據(jù)預(yù)處理

本仿真實(shí)驗(yàn)的硬件環(huán)境為Intel(R) Core(TM) i7-2600 CPU @ 3.40 GHz，4 GB內(nèi)存，軟件環(huán)境為Windows 8 64位操作系統(tǒng)，Matlab R2019b軟件和Pycharm開(kāi)發(fā)環(huán)境。本文采用2019年09月至2019年12月某高校學(xué)生移動(dòng)軌跡數(shù)據(jù)共包含6991個(gè)用戶，獲取的真實(shí)數(shù)據(jù)包含“手機(jī)的MAC地址、AP的MAC地址、rssi、時(shí)間、地點(diǎn)類(lèi)別、樓宇、房間”，具體信息見(jiàn)表5。

表5 某高校無(wú)線網(wǎng)絡(luò)獲取部分信息

首先根據(jù)獲取的記錄數(shù)量，保留記錄數(shù)大于等于1000的用戶共有4673名。然后對(duì)原始數(shù)據(jù)中的異常數(shù)據(jù)進(jìn)行處理：根據(jù)獲取的數(shù)據(jù)發(fā)現(xiàn)有些用戶在同一時(shí)刻獲取無(wú)線網(wǎng)絡(luò)登錄點(diǎn)是兩個(gè)不同的MAC地址，所以將用戶在5分鐘以內(nèi)的數(shù)據(jù)進(jìn)行合并，使用接收無(wú)限信號(hào)最強(qiáng)的MAC地址作為其確切的登錄點(diǎn)。

由于原始的PrefixSpan算法挖掘的結(jié)果不強(qiáng)調(diào)項(xiàng)之間的先后順序，為解決這一問(wèn)題，本文將原始的地點(diǎn)項(xiàng)做出一些改進(jìn)。表6為用戶u的部分移動(dòng)軌跡數(shù)據(jù)，第2列時(shí)間是將原來(lái)的年月日表示方法轉(zhuǎn)變?yōu)閿?shù)值表示，第4列為改進(jìn)地點(diǎn)項(xiàng)集表示，例如改進(jìn)后的地點(diǎn)項(xiàng)(21,22)是由在當(dāng)前時(shí)間點(diǎn)出現(xiàn)的地點(diǎn)和下一個(gè)出現(xiàn)的地點(diǎn)組成。

表6 用戶u部分移動(dòng)軌跡數(shù)據(jù)

3.2 實(shí)驗(yàn)結(jié)果及分析

本文從挖掘用戶的頻繁模式總數(shù)、平均頻繁軌跡模式個(gè)數(shù)和平均軌跡序列模式序列長(zhǎng)度3個(gè)方面，對(duì)比分析基本算法和改進(jìn)算法的運(yùn)行時(shí)間、運(yùn)行效率等。另外，還分析了序列壓縮和序列匹配對(duì)挖掘序列的個(gè)數(shù)影響，下面為具體實(shí)驗(yàn)的比較分析結(jié)果。

(1)L-PrefixSpan算法序列壓縮與序列匹配效果對(duì)比

根據(jù)上文2.1節(jié)中提到的序列壓縮與序列匹配的概念，為驗(yàn)證序列壓縮和序列匹配去除冗余軌跡的效果，將PrefixSpan算法和L-PrefixSpan算法挖掘頻繁序列的個(gè)數(shù)進(jìn)行比較，具體的實(shí)驗(yàn)結(jié)果見(jiàn)表7，圖2為不同最小支持度條件下PrefixSpan算法和L-PrefixSpan算法挖掘結(jié)果對(duì)比的柱形圖。

表7 PrefixSpan算法和L-PrefixSpan算法 挖掘頻繁軌跡數(shù)量對(duì)比

從圖2中可以觀察到，隨著最小支持度min_sup的增大，PrefixSpan算法和L-PrefixSpan算法挖掘結(jié)果數(shù)量也在隨之減小。以最小支持度min_sup=0.05為例，可以發(fā)現(xiàn)經(jīng)過(guò)序列壓縮和序列匹配，L-PrefixSpan算法挖掘結(jié)果數(shù)量只占PrefixSpan算法的50%左右，換言之剔除的冗余率大概在50%左右，而其它的最小支持度結(jié)果比較的剔除冗余率也在50%左右。根據(jù)圖2和表7的結(jié)果驗(yàn)證了序列壓縮和序列匹配的效果，表明序列壓縮和序列匹配對(duì)于剔除冗余率具有顯著的效果。

圖2 PrefixSpan算法和L-PrefixSpan算法挖掘結(jié)果對(duì)比

(2)多最小支持度結(jié)果分析

為驗(yàn)證DMS-PrefixSpan算法的有效性，本文將L-PrefixSpan算法與DMS-PrefixSpan算法的挖掘結(jié)果進(jìn)行比較。表8為DMS-PrefixSpan算法挖掘結(jié)果，表9為不同最小支持度下L-PrefixSpan算法挖掘結(jié)果。表中UserNum為存在頻繁軌跡挖掘結(jié)果的用戶數(shù)，PatternNum為挖掘的頻繁軌跡模式總數(shù)，AvgPatternNum為平均每個(gè)用戶頻繁軌跡模式數(shù)，AvgPatternNum/T為每個(gè)周期用戶的平均頻繁軌跡模式數(shù)，AvgPatternLen為平均每個(gè)頻繁軌跡模式的序列長(zhǎng)度，AvgPatternLen/T為每個(gè)周期的平均序列長(zhǎng)度。

表8 DMS-PrefixSpan算法挖掘結(jié)果

表9 L-PrefixSpan算法挖掘結(jié)果

根據(jù)表9可以發(fā)現(xiàn)：對(duì)于L-PrefixSpan算法，隨著最小支持度的增大，挖掘的UserNum值、PatternNum值、AvgPatternNum值、AvgPatternLen值都隨之減小；對(duì)比DMS-PrefixSpan算法的挖掘結(jié)果，所有的AvgPatternLen值均穩(wěn)定在4左右，但DMS-PrefixSpan算法中的AvgPatternNum值大于L-PrefixSpan算法在不同最小支持度條件下的AvgPatternNum數(shù)值。表明改進(jìn)后的DMS-PrefixSpan算法不僅能夠挖掘出用戶所有的頻繁項(xiàng)集，而且在保證挖掘結(jié)果的前提下也沒(méi)有影響算法的運(yùn)行效率，算法的具體運(yùn)行時(shí)間見(jiàn)表11。

(3)動(dòng)態(tài)頻繁序列挖掘結(jié)果分析

根據(jù)表10的頻繁序列結(jié)果展示，可以發(fā)現(xiàn)：該用戶的行為軌跡在宿舍樓和教學(xué)樓之間徘徊(第一個(gè)數(shù)字“1”表示宿舍樓，“2”表示教學(xué)樓)；最長(zhǎng)的頻繁序列為 ((131，132)， (132，131))和((132，131)， (131，132))， 即用戶最長(zhǎng)的頻繁序列為131→132→131或者132→131→132，符合數(shù)據(jù)集集中分布在宿舍樓的特點(diǎn)。用戶具體的頻繁序列移動(dòng)軌跡如圖3所示，其中線段較粗的表示該用戶經(jīng)常往返的路線，而線段較細(xì)的表示頻繁序列軌跡中相對(duì)頻率較低的。從圖3中能夠直觀看出，該用戶經(jīng)常往返于宿舍與教學(xué)樓、教學(xué)樓之間和宿舍之間，表明該學(xué)生的行為模式較為單一。且該用戶經(jīng)常往返于教學(xué)樓之間，表明該用戶的連續(xù)課程安排在不同的教學(xué)樓之間；學(xué)?？梢愿鶕?jù)用戶行為之間的時(shí)間差及行動(dòng)速度，合理安排課間休息時(shí)間及課程時(shí)間、地點(diǎn)的安排等。

表10 DMS-PrefixSpan算法頻繁序列結(jié)果展示

(4)運(yùn)行時(shí)間分析

表11為L(zhǎng)-PrefixSpan算法和DMS-PrefixSpan算法運(yùn)行時(shí)間對(duì)比，可以發(fā)現(xiàn)隨著支持度的增加，L-PrefixSpan算法的運(yùn)行時(shí)間在隨之減少；而DMS-PrefixSpan算法的運(yùn)行過(guò)程中，即使包含滑動(dòng)窗口模型和多最小支持度模型，但是其運(yùn)行時(shí)間介于min_sup=0.3和min_sup=0.4之間，表明改進(jìn)后的DMS-PrefixSpan算法有較好的運(yùn)行效率。

圖3 用戶的頻繁移動(dòng)軌跡

根據(jù)實(shí)驗(yàn)(1)～實(shí)驗(yàn)(4)的實(shí)驗(yàn)結(jié)果分析，實(shí)驗(yàn)(1)中實(shí)驗(yàn)結(jié)果驗(yàn)證了序列壓縮和序列匹配的有效性，實(shí)驗(yàn)(2)、實(shí)驗(yàn)(4)分別從挖掘的用戶頻繁序列模式個(gè)數(shù)、平均序列長(zhǎng)度及運(yùn)行時(shí)間凸顯了改進(jìn)算法的優(yōu)勢(shì)。實(shí)驗(yàn)(3)中涉及到用戶動(dòng)態(tài)頻繁序列模式挖掘，可以將挖掘結(jié)果進(jìn)一步用于研究用戶的異常行為及學(xué)校如何對(duì)課程進(jìn)行合理安排。

表11 L-PrefixSpan和DMS-PrefixSpan算法運(yùn)行時(shí)間比較

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

本文就傳統(tǒng)的頻繁項(xiàng)模式挖掘中的單一最小支持度存在的問(wèn)題做出了改進(jìn)，引入多最小支持度動(dòng)態(tài)確定模型，在充分運(yùn)用獲取數(shù)據(jù)的基礎(chǔ)上避免由于最小支持度的問(wèn)題影響最終的挖掘結(jié)果。針對(duì)PrefixSpan算法中大量冗余的頻繁序列，利用序列壓縮和序列匹配極大減少了存儲(chǔ)空間。為查看用戶在一段時(shí)間的地點(diǎn)偏好，運(yùn)用加權(quán)的方式使得挖掘結(jié)果綜合考慮過(guò)去和現(xiàn)在不同的行為習(xí)慣，并且也大大縮短了挖掘的運(yùn)行時(shí)間。分析研究挖掘的一系列結(jié)果，可以了解用戶的行為習(xí)慣、地點(diǎn)偏好變化等情況。