基于項(xiàng)位置索引的閉合連續(xù)序列模式挖掘算法

矯春蘭,劉建賓

(1.北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京 100101；2北京信息科技大學(xué) 軟件工程研究中心，北京 100101)

0 引言

序列模式挖掘是數(shù)據(jù)挖掘的一個(gè)重要領(lǐng)域，它在生物基因?qū)W、氨基酸序列分析、Web日志分析、代碼知識(shí)挖掘、客戶購(gòu)買行為分析預(yù)測(cè)等領(lǐng)域應(yīng)用廣泛?，F(xiàn)有的序列模式挖掘算法主要分為兩類，一類是以Apriori、GSP算法為代表的候選生成與測(cè)試方法；另一類是以PrefixSpan為代表的模式增長(zhǎng)方法。前者需要不斷重復(fù)掃描數(shù)據(jù)庫(kù)生成候選序列并進(jìn)行測(cè)試檢查，并且會(huì)生成大量無(wú)用的候選序列模式影響挖掘的效率；后者經(jīng)掃描一次數(shù)據(jù)庫(kù)后產(chǎn)生頻繁項(xiàng)，并根據(jù)頻繁項(xiàng)生成對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)，通過遞歸的方式把搜索空間劃分為更小的投影數(shù)據(jù)庫(kù)，這樣挖掘過程中不產(chǎn)生候選序列，但是構(gòu)造投影數(shù)據(jù)庫(kù)會(huì)造成較大的開銷。傳統(tǒng)的序列挖掘算法挖掘較大數(shù)據(jù)庫(kù)中的序列模式往往生成大量冗余序列。為減少挖掘結(jié)果集又不失完整性，有研究者提出了挖掘閉合序列模式與最大序列模式。常規(guī)的閉合順序模式挖掘算法在產(chǎn)生大量低效和冗余模式時(shí)面臨巨大挑戰(zhàn)，尤其是在使用低支持閾值或模式豐富的數(shù)據(jù)庫(kù)時(shí)?，F(xiàn)有的閉合序列挖掘算法包括CloSpan[1]、BIDE[2]等，是基于順序的算法，并不涉及連續(xù)性約束，所挖掘的結(jié)果存在跳躍與間隔的序列。然而并不是所有的頻繁順序序列模式都是用戶感興趣的。在生物基因?qū)W中常常需要分析連續(xù)的基因片段，在代碼知識(shí)挖掘中也需要探索連續(xù)出現(xiàn)的代碼片段。2015年文獻(xiàn)[3]首次提出基于生成—測(cè)試方法的閉合連續(xù)序列挖掘算法CCSPAN。文獻(xiàn)[4]應(yīng)用CCSPAN算法挖掘代碼中具有連續(xù)性約束的過程模式[5]得到可重用的代碼模式，但此算法需要不斷掃描數(shù)據(jù)庫(kù)生成候選測(cè)試序列，產(chǎn)生較大的時(shí)間開銷。

本文基于BIDE算法思想提出利用模式增長(zhǎng)的方式生成模式候選序列數(shù)據(jù)庫(kù)，并根據(jù)項(xiàng)的位置索引直接定位到具有連續(xù)約束的序列，減少對(duì)數(shù)據(jù)庫(kù)的重復(fù)搜索。根據(jù)頻繁項(xiàng)的位置索引采用向前與向后兩種策略檢查當(dāng)前頻繁候選連續(xù)序列的閉合性，減少了搜索空間。在增長(zhǎng)連續(xù)局部候選項(xiàng)時(shí)，通過掃描頻繁1-序列集對(duì)非頻繁項(xiàng)進(jìn)行剪枝，提前結(jié)束候選序列的擴(kuò)展，減少算法挖掘的時(shí)間。

1 相關(guān)工作

序列挖掘問題最初由Agrawal等[6]提出，挖掘得到的是序列模式的完全結(jié)果集。但當(dāng)模式較長(zhǎng)或支持度較低時(shí)算法性能降低。為此Pasquier等首次提出閉合序列模式，閉合序列模式結(jié)果更緊湊、更完整，它排除了那些與之支持度相同的超模式。由于不產(chǎn)生多余模式，所以挖掘過程更高效。Clospan算法是Han Jiawei等首次提出的用于挖掘閉合序列的算法，該算法是基于候選生成—測(cè)試方式進(jìn)行挖掘，需要維護(hù)已挖掘的閉序列候選集，算法執(zhí)行過程中占用大量?jī)?nèi)存，算法效率不夠高。因此文獻(xiàn)[7]提出根據(jù)項(xiàng)的位置來(lái)挖掘閉合序列模式的PosD算法，利用位置信息檢查支持度以提高挖掘效率。為減少內(nèi)存消耗，BIDE算法被提出，該算法無(wú)需維護(hù)候選頻繁閉序列，采用一種深度搜索空間剪枝方法與雙向擴(kuò)展模式閉合檢查機(jī)制減少時(shí)間消耗。

然而通常所說(shuō)的閉合序列挖掘結(jié)果并沒有連續(xù)約束，挖掘結(jié)果是間隔跳躍的。連續(xù)序列對(duì)生物連續(xù)基因的判斷具有重要意義。在分析用戶訪問網(wǎng)絡(luò)日志時(shí)，往往也需要分析連續(xù)訪問模式，因此連續(xù)模式挖掘算法成為了研究熱點(diǎn)。MacosVSpan算法是在prefixSpan算法的基礎(chǔ)上提出的，通過構(gòu)造固定長(zhǎng)度的生成樹在大型生物數(shù)據(jù)序列中挖掘最大頻繁連續(xù)序列。當(dāng)序列較長(zhǎng)時(shí)，MacosVSpan算法會(huì)產(chǎn)生大量的投影數(shù)據(jù)庫(kù)。文獻(xiàn)[8]提出了一種挖掘連續(xù)序列的prefixSpan算法，為保證序列的連續(xù)性，采取后綴第一項(xiàng)是否頻繁這種首尾相接的方式得到完整、連續(xù)的頻繁序列。文獻(xiàn)[9]使用滑動(dòng)窗口來(lái)挖掘連續(xù)序列，通過改變滑動(dòng)窗口的位置進(jìn)行序列模式計(jì)算。以上方法雖能得到頻繁連續(xù)序列，但是挖掘的是序列完全集，挖掘結(jié)果存在大量冗余模式，因此，Zhang Jingsong等提出了具有連續(xù)性約束的閉合序列挖掘算法CCSPAN。該算法基于候選測(cè)試—生成方式進(jìn)行挖掘，采用首尾子序列進(jìn)行檢測(cè)頻繁并剪枝，挖掘得到連續(xù)閉合序列模式，但此算法需要不斷掃描數(shù)據(jù)庫(kù)生成候選測(cè)試序列，產(chǎn)生較大的時(shí)間開銷。

本文基于模式增長(zhǎng)的方式，通過在序列中直接定位頻繁項(xiàng)的位置從而找到其連續(xù)局部項(xiàng)，以此得到頻繁連續(xù)子序列，同時(shí)根據(jù)項(xiàng)的位置信息得到其連續(xù)的前項(xiàng)與后項(xiàng)的支持度來(lái)進(jìn)行閉合判斷。

2 相關(guān)概念

定義1項(xiàng)項(xiàng)是數(shù)據(jù)挖掘中粒度最小的單位。設(shè)I={i1,i2,…,iN}是一個(gè)項(xiàng)集，項(xiàng)集是項(xiàng)的非空集合，其中iN是項(xiàng)。

定義2 序列序列是具有順序的列表，是項(xiàng)的有序組合，記做S=。其中si稱為元素。序列的長(zhǎng)度是指序列中不同項(xiàng)的數(shù)目，有k個(gè)項(xiàng)的序列也被稱為k-序列，例如{ACCB}是一個(gè)長(zhǎng)度為3的4-序列。

定義3 連續(xù)子序列給定兩個(gè)序列S1=，S2=，S1是S2的一個(gè)連續(xù)子序列，可以定義為S1?S2，當(dāng)且僅當(dāng)①1≤k1

定義4 序列數(shù)據(jù)庫(kù)指一個(gè)序列的集合。記做D={S1,S2,…,Sn},|D|表示數(shù)據(jù)庫(kù)中序列的數(shù)量。

定義5 支持度給定一個(gè)序列數(shù)據(jù)庫(kù)D，序列a在D中的支持度記做Sup(a)，Sup(a)=|{s|s∈D，a∈s}|表示D中包含序列a的序列數(shù)目。

定義6 閉合序列對(duì)于一個(gè)序列S，其所有超集的支持度均不等于序列S的支持度，則稱S為閉合序列。

定義7 頻繁閉合連續(xù)序列滿足最小支持度的閉合且連續(xù)的序列。

定義8 子序列首項(xiàng)對(duì)于序列S，其首項(xiàng)為S中的第一個(gè)項(xiàng)，例如{AC}是序列{CACB}的子序列，其首項(xiàng)為A。

定義9 子序列末項(xiàng)對(duì)于序列S，其末項(xiàng)為S中的最后一個(gè)項(xiàng)。例如{ABC}是序列{AABC}的子序列，其末項(xiàng)為C。

性質(zhì)1頻繁序列的任意子序列都是頻繁的，非頻繁序列的任意超序列一定是不頻繁的。

3 LCCS算法設(shè)計(jì)

3.1 項(xiàng)位置索引結(jié)構(gòu)

項(xiàng)在序列數(shù)據(jù)庫(kù)中的索引結(jié)構(gòu)包含兩個(gè)域：data數(shù)據(jù)項(xiàng)和項(xiàng)的索引指針node。指針域node指向索引表，索引表包含項(xiàng)所在序列的序列sid和項(xiàng)在序列中的偏移位置loc。根據(jù)sid可以直接找到頻繁項(xiàng)對(duì)應(yīng)的序列，無(wú)需掃描整個(gè)序列數(shù)據(jù)庫(kù)。loc索引可以直接定位到頻繁項(xiàng)在序列中的位置，無(wú)需掃描整個(gè)序列。

對(duì)于表1所示的序列數(shù)據(jù)庫(kù)得到的頻繁項(xiàng)的索引結(jié)構(gòu)如圖1所示，其中A的位置索引(1,1)表示項(xiàng)A出現(xiàn)在序列數(shù)據(jù)庫(kù)中的第一個(gè)序列ACABC中第一個(gè)位置。

表1 序列數(shù)據(jù)庫(kù)

定義10 前向局部項(xiàng)也稱連續(xù)局部候選項(xiàng)，表示子序列S末項(xiàng)所在位置的后一項(xiàng)。例如子序列{ABC}是{AABCD}的子序列，其在序列中的連續(xù)局部項(xiàng)為D。

定義11 后向局部項(xiàng)表示子序列S首項(xiàng)所在位置的前一項(xiàng)。例如子序列{AB}在{AABC}的后向局部項(xiàng)為第一個(gè)A。

定理1支持度計(jì)算。對(duì)不同的sid序列號(hào)進(jìn)行計(jì)數(shù)可得到項(xiàng)的支持度。

證明因?yàn)閟id序號(hào)具有標(biāo)識(shí)唯一性，相同的sid號(hào)表明項(xiàng)在同一個(gè)序列中出現(xiàn)兩次，所以可以采用sid號(hào)對(duì)支持度進(jìn)行統(tǒng)計(jì)。

定理2向前閉合判定。當(dāng)前子序列的支持度為n,其前向局部項(xiàng)的支持度也為n，則當(dāng)前子序列一定是不閉合的。

證明因?yàn)榍跋蚓植宽?xiàng)與子序列S是同時(shí)出現(xiàn)的，通過前向局部項(xiàng)的支持度便可得到S的超序列的支持度。根據(jù)閉合序列的定義可知，當(dāng)子序列S與其所有超集的支持度相等時(shí)，序列S一定是不閉合的。

定理3向后閉合判定。當(dāng)前子序列的支持度為n，其后項(xiàng)局部項(xiàng)的支持度也為n，則當(dāng)前子序列一定是不閉合的。

證明與定理2同理可得。

3.2 算法思想

LCCS算法是一種基于頻繁項(xiàng)位置索引的深度優(yōu)先挖掘算法，采用遞歸的方式對(duì)序列進(jìn)行擴(kuò)展以及閉合檢查，直到該序列無(wú)法增長(zhǎng)。算法分為3個(gè)部分：候選序列數(shù)據(jù)庫(kù)的生成，連續(xù)局部頻繁項(xiàng)的生成與擴(kuò)展以及連續(xù)閉合序列的判定。利用頻繁項(xiàng)的序列號(hào)sid找到序列數(shù)據(jù)庫(kù)中的候選序列，無(wú)需掃描所有序列，通過不斷劃分搜索空間來(lái)減少數(shù)據(jù)庫(kù)掃描所用的時(shí)間。利用頻繁候選子序列的各個(gè)項(xiàng)在序列中的位置偏移量loc定位到頻繁候選子序列的連續(xù)局部候選項(xiàng)，得到連續(xù)序列模式，減少挖掘過程中產(chǎn)生的大量冗余模式。根據(jù)頻繁候選子序列中各個(gè)項(xiàng)的loc位置，得到其在序列中的后向局部項(xiàng)與前向局部項(xiàng)，并依據(jù)出現(xiàn)次數(shù)分別對(duì)其進(jìn)行計(jì)數(shù)，根據(jù)給定的支持度來(lái)判斷當(dāng)前序列是否閉合。

3.3 算法步驟

LCCS算法步驟如下：

步驟1掃描數(shù)據(jù)庫(kù)得到所有的頻繁1-序列，以及1-序列項(xiàng)的位置信息(sid，loc)，并保存頻繁1-序列的信息。

步驟2對(duì)于每個(gè)頻繁k-序列進(jìn)行遞歸調(diào)用LCCS算法。

步驟3連續(xù)局部頻繁項(xiàng)的生成。在對(duì)應(yīng)的數(shù)據(jù)庫(kù)中利用模式增長(zhǎng)方式向后尋找連續(xù)局部頻繁項(xiàng)，在此過程中通過掃描步驟1中的頻繁項(xiàng)并根據(jù)性質(zhì)1來(lái)修剪候選局部項(xiàng)，提前剪去非頻繁的局部項(xiàng)，并最終得到頻繁局部項(xiàng)的sid與loc。

步驟4連續(xù)閉合序列的判定。此過程分為向前與向后兩個(gè)策略進(jìn)行檢測(cè)，無(wú)論向前或是向后閉合檢查，只要當(dāng)前子序列是非連續(xù)閉合則此序列非閉合。首先判斷當(dāng)前序列與前向局部項(xiàng)支持度是否相等，相等則非閉合執(zhí)行步驟6，不相等再判斷是否存在當(dāng)前子序列的后向局部項(xiàng)支持度與該序列支持度相等的項(xiàng)，存在則當(dāng)前序列非閉合進(jìn)入步驟6，閉合則輸出。

步驟5連續(xù)頻繁項(xiàng)的擴(kuò)展。根據(jù)步驟4中得到的局部連續(xù)頻繁項(xiàng)，對(duì)當(dāng)前k-序列進(jìn)行向后擴(kuò)展成為長(zhǎng)度k+1的候選子序列。

步驟6候選序列數(shù)據(jù)庫(kù)的生成。對(duì)每個(gè)頻繁子序列根據(jù)sid構(gòu)造頻繁項(xiàng)的序列數(shù)據(jù)庫(kù)，并重復(fù)進(jìn)行步驟3到步驟6的操作。

3.4 實(shí)例說(shuō)明

下面以表1所示的序列數(shù)據(jù)庫(kù)為例，設(shè)置最小支持度為2來(lái)說(shuō)明利用LCCS算法挖掘頻繁連續(xù)閉合序列模式。

1)掃描數(shù)據(jù)庫(kù)，得到所有頻繁項(xiàng)以及位置信息并根據(jù)項(xiàng)不同的sid號(hào)計(jì)算每個(gè)項(xiàng)的支持度，得到圖1所示的頻繁1-序列信息表。

2)首先以{A}作為頻繁子序列，根據(jù)其sid信息獲取對(duì)應(yīng)的序列形成數(shù)據(jù)庫(kù)即表1。

3)遍歷數(shù)據(jù)庫(kù)。根據(jù){A}的loc信息，得到{A}的前向局部項(xiàng)C和B，如圖2所示，并判斷前一項(xiàng)是否在頻繁1-序列中來(lái)判斷前一項(xiàng)的頻繁性，以此提前剪去不頻繁項(xiàng)。根據(jù)給定的支持度并最終得到{A}的頻繁連續(xù)局部項(xiàng)為B，B的支持度為4。

4)對(duì)當(dāng)前頻繁子序列{A}進(jìn)行向前與向后閉合性檢查。向前檢查{A}與其連續(xù)局部頻繁項(xiàng)支持度是否相等，其中{A}的支持度為4，其連續(xù)局部頻繁項(xiàng)的支持度B也為4，因此當(dāng)前子序列{A}不是閉合序列，無(wú)需向后檢查，{A}不是連續(xù)閉合序列。

5)對(duì)當(dāng)前頻繁子序列進(jìn)行向后擴(kuò)展，將當(dāng)前頻繁子序列{A}與局部頻繁項(xiàng)B組合形成長(zhǎng)度為2的頻繁子序列{AB}，更新其位置信息更新并保存。

6)以遞歸的方式以{AB}為頻繁子序列，重復(fù)前述2)至5)操作，其中進(jìn)行3)得到{AB}的局部頻繁項(xiàng)為B和C。在進(jìn)行閉合檢查時(shí)，首先進(jìn)行向前檢查，發(fā)現(xiàn){AB}的支持度為4，前向局部項(xiàng)C與B支持度均為2，因此還需向后閉合檢查。根據(jù){AB}中A的(sid，loc)，得到{AB}的后向局部項(xiàng)C與{AB}支持度相等，以此判斷當(dāng)前2-子序列{AB}并非連續(xù)閉合序列。

3.5 算法偽代碼

算法描述:LCCS算法偽代碼輸入:序列數(shù)據(jù)集合SDB與最小支持度min-sup輸出:頻繁連續(xù)閉合序列模式1:subItem=getSubItem()CallgetItemFrequencies()2:getItemFrequencies(minSup,subItem):3:foreachsequenceinsdbdo4:foreachiteminsequencedo5:itemloc.set(i,loc+1)6:iffirstItemcontainsitem7:iffrequencecontainitem8:frequence.loc_i.add(itemloc)9:else10:frequence.add(itemloc)11:iffrequence.loc_i.size()

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)

算法運(yùn)行所需的環(huán)境為Intel(R)Core(TM)i5-4200U 1.60GHz處理器，8 GB內(nèi)存，Windows10操作系統(tǒng)，算法采用java語(yǔ)言編寫并在 eclipse環(huán)境下編譯。實(shí)驗(yàn)數(shù)據(jù)采用SPMF[10]數(shù)據(jù)挖掘算法數(shù)據(jù)庫(kù)中的BMSWebView1，共含60 000條數(shù)據(jù)，包含497個(gè)不同元素，元素?cái)?shù)值較小，多數(shù)在4位數(shù)以內(nèi)；Kasarak共含10 000條數(shù)據(jù)。在不同支持度下與CCSPAN算法以及BIDE算法做對(duì)比實(shí)驗(yàn)，結(jié)果如圖3～5所示。

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

取支持度0.02%～0.1%對(duì)包含10 000條數(shù)據(jù)的Kasarak數(shù)據(jù)集進(jìn)行測(cè)試，其結(jié)果如圖3所示。從圖中可以看出，LCCS算法的執(zhí)行時(shí)間優(yōu)于CCSPAN算法，但隨著支持度的增加，支持度達(dá)到0.8%左右時(shí)，LCCS算法執(zhí)行效率減弱，這是因?yàn)楫?dāng)支持度較高時(shí)，在第一次掃描數(shù)據(jù)庫(kù)時(shí)需要不斷構(gòu)建大量的項(xiàng)位置信息并計(jì)算支持度，造成時(shí)間消耗。取支持度0.005%～0.012%對(duì)包含60 000條數(shù)據(jù)的BMSWebView-1數(shù)據(jù)集進(jìn)行測(cè)試，可以明顯看出LCCS算法執(zhí)行時(shí)間優(yōu)于CCSPAN算法。這是因?yàn)楫?dāng)數(shù)據(jù)集較為稀疏時(shí)其效果更佳，加入的頻繁項(xiàng)位置信息可以直接找到候選連續(xù)序列，同時(shí)可以根據(jù)位置信息判斷閉合性，這樣減少了掃描數(shù)據(jù)庫(kù)的時(shí)間，提高了連續(xù)序列挖掘的效率。LCCS算法相比于BIDE算法，在支持度較低時(shí)有較為明顯的優(yōu)勢(shì)，這是因?yàn)榧尤脒B續(xù)約束后，挖掘得到更為具體的結(jié)果，產(chǎn)生的閉合連續(xù)序列模式遠(yuǎn)少于閉合序列模式總數(shù)，避免了產(chǎn)生大量無(wú)用候選集。但隨著支持度的增加LCCS算法并不占優(yōu)勢(shì)，這是因?yàn)楫?dāng)支持度增加時(shí)滿足的閉合序列模式數(shù)量較少，此時(shí)LCCS算法趨近于BIDE算法，但由于LCSS算法需要計(jì)算項(xiàng)的位置信息，造成時(shí)間消耗。實(shí)驗(yàn)證明，LCCS算法適用于數(shù)據(jù)量較大、密度較稀疏的數(shù)據(jù)且設(shè)置相對(duì)較低的支持度來(lái)挖掘頻繁出現(xiàn)的閉合連續(xù)序列模式。

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

為了提高算法的挖掘效率，本文提出了基于位置信息的LCCS算法挖掘連續(xù)閉合序列。在BIDE算法的基礎(chǔ)上，通過模式增長(zhǎng)方式向后直接擴(kuò)展頻繁序列，利用項(xiàng)的位置進(jìn)行向前與向后閉合檢查從大量數(shù)據(jù)中挖掘頻繁連續(xù)閉合序列。本文算法有如下優(yōu)點(diǎn)：

1)無(wú)需反復(fù)掃描序列數(shù)據(jù)庫(kù)，只需根據(jù)位置信息直接定位序列進(jìn)行擴(kuò)展與閉合檢查，這大大減少了搜索時(shí)間花銷。

2)無(wú)需產(chǎn)生大量無(wú)用的候選序列，加快了算法運(yùn)行時(shí)間，節(jié)省了存儲(chǔ)空間。

在實(shí)驗(yàn)中，LCCS算法雖然在某種程度上加快了程序運(yùn)行的時(shí)間，提高了程序執(zhí)行的效率，但是，本研究的連續(xù)閉合序列挖掘算法在時(shí)間和空間上都還有繼續(xù)提升的空間，該算法對(duì)支持度較高的稠密型數(shù)據(jù)執(zhí)行效率還有待提高。算法的好壞直接影響程序執(zhí)行的性能，連續(xù)閉合序列也是未來(lái)應(yīng)該著重研究的方向。