摘 要： 針對(duì)序列模式的幾個(gè)經(jīng)典的算法的缺點(diǎn),，提出了一種基于時(shí)間約束序列模式的快速產(chǎn)生候選項(xiàng)的方法（TFEGC）,。此算法不但避免了頻繁的掃描數(shù)據(jù)庫(kù)，還考慮了時(shí)間限制因素,，避免了無用的候選序列的產(chǎn)生,，提高了算法運(yùn)行的時(shí)間效率。
關(guān)鍵詞： 序列模式挖掘,；時(shí)間約束,；候選項(xiàng);快速產(chǎn)生
序列模式挖掘在很多領(lǐng)域都具有十分重要的意義，比如它可以根據(jù)分析顧客購(gòu)買行為來決定商品的擺放位置,，從而制定商場(chǎng)的營(yíng)銷策劃,。所以,，近年來出現(xiàn)了很多序列模式挖掘的改進(jìn)算法,，目前提出算法中，有兩類比較典型：GSP[1]算法和采用分治策略來進(jìn)行模式增長(zhǎng)的PrefixSpan[2]算法,。但是這兩種算法都存在一定的缺點(diǎn),。參考文獻(xiàn)[3]中提出的快速有效的產(chǎn)生候選項(xiàng)的FEGC算法，不需要多次掃描數(shù)據(jù)庫(kù),，且不需要在前一次迭代的基礎(chǔ)上來產(chǎn)生候選項(xiàng),，也不需對(duì)非頻繁項(xiàng)進(jìn)行剪枝或修剪，能夠達(dá)到快速產(chǎn)生候選項(xiàng)的效果,。但是,，F(xiàn)EGC算法是針對(duì)數(shù)據(jù)庫(kù)總體的序列來產(chǎn)生候選項(xiàng)的，有些并不是有效的和用戶感興趣的序列,，這在實(shí)際應(yīng)用中就耗費(fèi)了大量的時(shí)間和空間,，如分析顧客的購(gòu)買行為，就不需要將其一月份購(gòu)買的產(chǎn)品和十二月份購(gòu)買的產(chǎn)品放在一起進(jìn)行研究比較,。所以本文在FEGC算法的基礎(chǔ)上將時(shí)間限制因素加了進(jìn)去,，可稱之為TFEGC算法，本算法繼承了FEGC算法的優(yōu)點(diǎn),，而且避免了不必要的,、無用的一些候選項(xiàng)的產(chǎn)生，提高了算法的運(yùn)行效率,，且在序列結(jié)合的過程中,，只需檢查uid,、fid(t)以及s(t)的值，便可知道與哪些項(xiàng)進(jìn)行結(jié)合,，無須再進(jìn)行檢驗(yàn),。
1 相關(guān)算法介紹
GSP算法，即廣義序列模式算法,，使用序列模式的向下封閉性,，并采用多次掃描的候選產(chǎn)生-測(cè)試方法，它是由Srikant和Agrawal于1996年提出的,。它的主要思想是利用序列模式的種子集,，即前次掃描得來的序列模式來產(chǎn)生潛在的頻繁序列，即候選序列,，每個(gè)候選序列都會(huì)比產(chǎn)生它的種子序列模式多包含一個(gè)項(xiàng),。直到一遍掃描不能產(chǎn)生新的序列模式或者新的候選序列時(shí)，算法終止,。
PrefixSpan算法是前綴投影序列模式增長(zhǎng)算法[4],，此算法的特點(diǎn)是不需要產(chǎn)生候選項(xiàng)，算法思想是先找出各個(gè)頻繁項(xiàng),，然后分別產(chǎn)生它們所對(duì)應(yīng)的投影數(shù)據(jù)庫(kù),，接著對(duì)各個(gè)投影數(shù)據(jù)庫(kù)進(jìn)行挖掘，最后將前綴模式與后綴模式相連得到頻繁序列,。此算法的缺點(diǎn)就在于可能會(huì)產(chǎn)生大量的投影數(shù)據(jù)庫(kù),，而且要掃描數(shù)據(jù)庫(kù)多次[3]。
FEGC算法的特點(diǎn)有：（1）Head,、Body,、Tail的引入，在一個(gè)交易序列中,，處于Head的項(xiàng)在形成二序列時(shí),，只能作為二序列中的Head，處于Body的項(xiàng)在形成二序列時(shí),，既可以作為Head,也可以作為Tail,；（2）Nid的引入，Nid的作用是用來規(guī)定在形成候選序列的過程中的2-序列的結(jié)合順序[1],。
2 TFEGC算法的理論和相關(guān)概念
對(duì)于給定的某個(gè)顧客的交易數(shù)據(jù)序列B={(Item,，TID)，…},其中Item表示交易的項(xiàng),，TID表示交易的時(shí)間,，設(shè)I={(i1，t1)，(i2,，t2),，…(in，tn)}是由n個(gè)不同的項(xiàng)組成的序列,，它記錄了某個(gè)顧客在不同的時(shí)間購(gòu)買的產(chǎn)品,，然后根據(jù)時(shí)間限制將這個(gè)序列劃分成不同的子序列，再將這些子序列轉(zhuǎn)化為2-序列[5],，最后以這些2-序列為基礎(chǔ),，找出所有的候選項(xiàng)。
2.2 公式的應(yīng)用及td的引入
上面的三個(gè)公式都是為了解決利用TFEGC算法來求候選項(xiàng)時(shí)遇到的問題,，它們所發(fā)揮的作用可通過下面的具體例子來進(jìn)行詳細(xì)描述,。
由圖1可知所有的2-序列過程，下面以子序列<bcde>產(chǎn)生的2-序列<bc>為例,，具體過程如下：
（1）計(jì)算出uid=4-2=2,，fid(c)=4-2=2，fid(d)=4-3=1,，s(c)=2-1=1,，s(d)=3-1=2；
（2）對(duì)于2-序列<bc>,，因?yàn)閟(c)=1,，說明它只能與排在子序列<bcde>之后的第一個(gè)子序列產(chǎn)生的2-序列相結(jié)合，由圖1可知是子序列<cdef>產(chǎn)生的2-序列,；又因?yàn)閒id(c)=2,，說明它只能與<cdef>產(chǎn)生的前兩個(gè)2-序列<cd>、<ce>相結(jié)合,，生成<bcd>、<bce>,；又因?yàn)閟(d)=2,、fid(d)=1，說明<bcd>還可以與排在子序列<bcde>之后的第二個(gè)子序列<def>產(chǎn)生的第一個(gè)2-序列<de>進(jìn)行結(jié)合,生成<bcde>,e為子序列<bcde>的最后一項(xiàng),，不作考慮,。
由上面的步驟（2）可知，雖然求得了s(c)的值,，但是在算法的實(shí)現(xiàn)過程中,，并不知道子序列<cdef>就是排在子序列<bcde>之后的第一個(gè)子序列，為了解決這個(gè)問題,，引入了td的值,，為節(jié)省存儲(chǔ)空間，可以用矩陣的形式來存儲(chǔ)td的值，如圖2所示,。
矩陣中沒有出現(xiàn)項(xiàng)e和項(xiàng)f,，因?yàn)轫?xiàng)f為序列的最后一項(xiàng)，所以它不會(huì)與任何二序列進(jìn)行結(jié)合,，由圖1知并沒有產(chǎn)生以e為首項(xiàng)的子序列,，所以不會(huì)產(chǎn)生以e為首項(xiàng)的2-序列。
其中,，[1,，1]=1-0=1,表示排在以a為首字母的子序列之后的第一個(gè)子序列，是以b為首字母的子序列,；[2,，2]=2-1=1，表示排在以b為首字母的子序列之后的第一個(gè)序列,，是以c為首字母的子序列,依此類推,。
所以，當(dāng)算出s(t)的值時(shí),，只需比較其與td的值,，當(dāng)s(t)=td的值時(shí)，則此序列就是所要結(jié)合的2-序列,。
3 TFEGC算法
3.1 算法思想
本算法一共有四大步,，第一步是根據(jù)時(shí)間限制將原序列劃分為多個(gè)子序列；第二步是將得到的子序列轉(zhuǎn)化為2-序列,；第三步是根據(jù)uid,、fid(t)和s(t)的值將2-序列進(jìn)行結(jié)合，從而得到所有的候選項(xiàng),；第四步根據(jù)最小支持度minsup得到頻繁項(xiàng)集,。
從上所述可以看出，此算法的主要特點(diǎn)有：(1)加入了時(shí)間限制因素,；(2)只需要掃描數(shù)據(jù)庫(kù)一次,，節(jié)省了算法的運(yùn)行時(shí)間；(3)引入了uid,、fid(t),、s(t)，使之在形成n-序列的過程中,，能夠準(zhǔn)確地找到要結(jié)合的2-序列,，不需要掃描所有子序列產(chǎn)生的二序列，提高了算法的時(shí)間效率,。
3.2 TFEGC核心算法描述
2-序列結(jié)合的算法如下：
for all I∈DB{ //I為滿足時(shí)間限制的子序列
l=strlen(I),；
uid=l-2,；
for(n is smaller thanl ){
if(in∈I and n≠1 and n≠1)
{ //in不能為首尾兩項(xiàng)
s(in)=n-1；
fid(in)=l-n,；}
}
for(scan the Matrix Chart of td){//掃描矩陣td
if(td==s(in)){
record the item r and
record those 2-sequence se whose first item is r,；}
//r用來存放首項(xiàng)，se用來
//存放以其為首項(xiàng)形成的2-序列
}
for all tn∈se{
if(tn.index==fid(in)){//找到所要結(jié)合的2-序列
in+tn,；}//2-序列in和2-序列tn相結(jié)合
}
}
3.3 算法舉例
為了進(jìn)一步描述TFEGC算法,，以圖1中的子序列<abc>產(chǎn)生的第一個(gè)2-序列<ab>為例，求以這個(gè)2-序列為基礎(chǔ)所形成的候選項(xiàng)過程,，如圖3所示,。
4 實(shí)驗(yàn)結(jié)果
算法實(shí)驗(yàn)環(huán)境為PentiumⅣ3.0 GHz雙核 PC機(jī)器，內(nèi)存為1 GB,，Windows XP操作系統(tǒng),，采用C++語言在VC編程環(huán)境下實(shí)現(xiàn)。實(shí)驗(yàn)測(cè)試數(shù)據(jù)采用IBM數(shù)據(jù)生成器,，該生成器是目前數(shù)據(jù)挖掘相關(guān)研究中使用廣泛和權(quán)威的生成器,，可以通過設(shè)置參數(shù)生成不同特性的數(shù)據(jù)集，具體參數(shù)含義如表1所示,。
PrefixSpan算法和TFEGC算法在不同的支持度下的運(yùn)行時(shí)間如圖4所示,，從結(jié)果可以看出文中提出的方法優(yōu)于PrefixSpan算法，因?yàn)門FEGC算法只需要掃描數(shù)據(jù)庫(kù)一次,，而且由于uid,、fid(t)以及s(t)的引入，避免了一些無用序列的產(chǎn)生,，大大減少了運(yùn)行時(shí)間,。
圖5所示的是FEGC和TFEGC在不同數(shù)量的顧客下算法的運(yùn)行時(shí)間，從中也可以看出TFEGC算法的運(yùn)行時(shí)間少于FEGC算法的運(yùn)行時(shí)間,。這是因?yàn)樵诙蛄械慕Y(jié)合過程中,，TFEGC不需要逐個(gè)掃描其他的二序列，只需查看uid,、fid(t)以及s(t)的值就可以判斷應(yīng)該與哪些二序列進(jìn)行結(jié)合,，而且生成的用戶不感興趣的序列也大大減少了。因?yàn)榧尤肓藭r(shí)間的限制,，所以根據(jù)支持度來提取頻繁序列的時(shí)間也就相應(yīng)地減少了。
本文提出的算法,，可由用戶自己設(shè)定時(shí)間限制來查找頻繁序列,，也可以用來處理不同數(shù)量的客戶群，所以具有一定的靈活性,。又因?yàn)槠渲粧呙钄?shù)據(jù)庫(kù)一次,，而且二序列的結(jié)合也具有一定的明確性,，所以在時(shí)間效率上具有一定的優(yōu)越性[6]。
參考文獻(xiàn)
[1] SRIKANT R,，AGRAWAL R.Mining sequential patterns:generalizations and performance improvements[C].Proc.of Int’l Conf.on Extending Database Technology,，1996：3-17.
[2] PEI J，HAN J,，Mortazavi-Asl B,，et al.Prefixspan: mining sequential patterns efficiently by prefix-projected pattern growth[C].Proc.of Int.Conf.on Data Eng. (ICDE’01)，2001：215-224.
[3] Liao Weicheng,，Yang Donlin,，Wu Jungpin，et al.Fast and effective generation of candidate-sequences for sequential pattern mining[C].2009 Fifth International Joint Conference on INC,，IMS and IDC,，2009:2006-2009.
[4] 趙暢，楊冬青,，唐世渭.Web日志序列模式挖掘[J].計(jì)算機(jī)應(yīng)用,，2000，9（20）：13-16.
[5] 連一峰,，戴英俠,，王航.基于模式挖掘的用戶行為異常檢測(cè)[J].計(jì)算機(jī)學(xué)報(bào)，2002,，25(3)：325-329.
[6] 吉根林,，帥克，孫志揮．?dāng)?shù)據(jù)挖掘技術(shù)及其應(yīng)用[J].南京師范大學(xué)學(xué)報(bào)(自然科學(xué)版),，2000,，23(2)：25-27.