基于動態(tài)多最小支持度的用戶頻繁軌跡挖掘

嚴愛俐，劉漫丹

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

0 引 言

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

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

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

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

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

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

定義2 支持度(Support)：一個序列的支持度被定義為數(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)：用戶定義衡量支持度的一個閾值，表示項在統(tǒng)計意義上的最低重要性，記作min_sup；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 序列壓縮和序列匹配

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

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

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

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

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

2.2 多最小支持度的計算

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

(2)

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

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

(3)

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

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

f(x)=ln(x+1)

(4)

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

(5)

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

f(x)=exp(-πx2)

(6)

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

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

(7)

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

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

(8)

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

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

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

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

當Tk=[start+(k-1)T,start+kT], 1≤k≤n時，由式(7)可得用戶u在地點li的最小支持度，記為MIS(luTk,i)， 則用戶u在n個周期內(nèi)地點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的在地點li出現(xiàn)的概率為Pu,li， 在計算T(k+1)周期地點li的最小支持度時需要迭加權(quán)值計算，具體計算如式(12)所示

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

(12)

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

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

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

(13)

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

具體挖掘步驟如下：

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

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

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

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

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

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

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

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

3 某高校用戶頻繁項挖掘

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

本仿真實驗的硬件環(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開發(fā)環(huán)境。本文采用2019年09月至2019年12月某高校學(xué)生移動軌跡數(shù)據(jù)共包含6991個用戶，獲取的真實數(shù)據(jù)包含“手機的MAC地址、AP的MAC地址、rssi、時間、地點類別、樓宇、房間”，具體信息見表5。

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

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

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

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

3.2 實驗結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4)運行時間分析

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

圖3 用戶的頻繁移動軌跡

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

表11 L-PrefixSpan和DMS-PrefixSpan算法運行時間比較

4 結(jié)束語

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