摘  要： 針對序列模式的幾個經(jīng)典的算法的缺點，提出了一種基于時間約束序列模式的快速產(chǎn)生候選項的方法（TFEGC）。此算法不但避免了頻繁的掃描數(shù)據(jù)庫，還考慮了時間限制因素，避免了無用的候選序列的產(chǎn)生，提高了算法運行的時間效率。
關(guān)鍵詞： 序列模式挖掘；時間約束；候選項;快速產(chǎn)生

    序列模式挖掘在很多領(lǐng)域都具有十分重要的意義，比如它可以根據(jù)分析顧客購買行為來決定商品的擺放位置，從而制定商場的營銷策劃。所以，近年來出現(xiàn)了很多序列模式挖掘的改進算法，目前提出算法中，有兩類比較典型：GSP[1]算法和采用分治策略來進行模式增長的PrefixSpan[2]算法。但是這兩種算法都存在一定的缺點。參考文獻[3]中提出的快速有效的產(chǎn)生候選項的FEGC算法，不需要多次掃描數(shù)據(jù)庫，且不需要在前一次迭代的基礎(chǔ)上來產(chǎn)生候選項，也不需對非頻繁項進行剪枝或修剪，能夠達到快速產(chǎn)生候選項的效果。但是，F(xiàn)EGC算法是針對數(shù)據(jù)庫總體的序列來產(chǎn)生候選項的，有些并不是有效的和用戶感興趣的序列，這在實際應(yīng)用中就耗費了大量的時間和空間，如分析顧客的購買行為，就不需要將其一月份購買的產(chǎn)品和十二月份購買的產(chǎn)品放在一起進行研究比較。所以本文在FEGC算法的基礎(chǔ)上將時間限制因素加了進去，可稱之為TFEGC算法，本算法繼承了FEGC算法的優(yōu)點，而且避免了不必要的、無用的一些候選項的產(chǎn)生，提高了算法的運行效率，且在序列結(jié)合的過程中，只需檢查uid、fid(t)以及s(t)的值，便可知道與哪些項進行結(jié)合，無須再進行檢驗。
1 相關(guān)算法介紹
    GSP算法，即廣義序列模式算法，使用序列模式的向下封閉性，并采用多次掃描的候選產(chǎn)生-測試方法，它是由Srikant和Agrawal于1996年提出的。它的主要思想是利用序列模式的種子集，即前次掃描得來的序列模式來產(chǎn)生潛在的頻繁序列，即候選序列，每個候選序列都會比產(chǎn)生它的種子序列模式多包含一個項。直到一遍掃描不能產(chǎn)生新的序列模式或者新的候選序列時，算法終止。
    PrefixSpan算法是前綴投影序列模式增長算法[4]，此算法的特點是不需要產(chǎn)生候選項，算法思想是先找出各個頻繁項，然后分別產(chǎn)生它們所對應(yīng)的投影數(shù)據(jù)庫，接著對各個投影數(shù)據(jù)庫進行挖掘，最后將前綴模式與后綴模式相連得到頻繁序列。此算法的缺點就在于可能會產(chǎn)生大量的投影數(shù)據(jù)庫，而且要掃描數(shù)據(jù)庫多次[3]。
    FEGC算法的特點有：（1）Head、Body、Tail的引入，在一個交易序列中，處于Head的項在形成二序列時，只能作為二序列中的Head，處于Body的項在形成二序列時，既可以作為Head,也可以作為Tail；（2）Nid的引入，Nid的作用是用來規(guī)定在形成候選序列的過程中的2-序列的結(jié)合順序[1]。
2 TFEGC算法的理論和相關(guān)概念
    對于給定的某個顧客的交易數(shù)據(jù)序列B={(Item，TID)，…},其中Item表示交易的項，TID表示交易的時間，設(shè)I={(i1，t1)，(i2，t2)，…(in，tn)}是由n個不同的項組成的序列，它記錄了某個顧客在不同的時間購買的產(chǎn)品，然后根據(jù)時間限制將這個序列劃分成不同的子序列，再將這些子序列轉(zhuǎn)化為2-序列[5]，最后以這些2-序列為基礎(chǔ)，找出所有的候選項。

2.2 公式的應(yīng)用及td的引入
    上面的三個公式都是為了解決利用TFEGC算法來求候選項時遇到的問題，它們所發(fā)揮的作用可通過下面的具體例子來進行詳細(xì)描述。
    由圖1可知所有的2-序列過程，下面以子序列<bcde>產(chǎn)生的2-序列<bc>為例，具體過程如下：
    （1）計算出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）對于2-序列<bc>，因為s(c)=1，說明它只能與排在子序列<bcde>之后的第一個子序列產(chǎn)生的2-序列相結(jié)合，由圖1可知是子序列<cdef>產(chǎn)生的2-序列；又因為fid(c)=2，說明它只能與<cdef>產(chǎn)生的前兩個2-序列<cd>、<ce>相結(jié)合，生成<bcd>、<bce>；又因為s(d)=2、fid(d)=1，說明<bcd>還可以與排在子序列<bcde>之后的第二個子序列<def>產(chǎn)生的第一個2-序列<de>進行結(jié)合,生成<bcde>,e為子序列<bcde>的最后一項，不作考慮。

    由上面的步驟（2）可知，雖然求得了s(c)的值，但是在算法的實現(xiàn)過程中，并不知道子序列<cdef>就是排在子序列<bcde>之后的第一個子序列，為了解決這個問題，引入了td的值，為節(jié)省存儲空間，可以用矩陣的形式來存儲td的值，如圖2所示。

    矩陣中沒有出現(xiàn)項e和項f，因為項f為序列的最后一項，所以它不會與任何二序列進行結(jié)合，由圖1知并沒有產(chǎn)生以e為首項的子序列，所以不會產(chǎn)生以e為首項的2-序列。
    其中，[1，1]=1-0=1,表示排在以a為首字母的子序列之后的第一個子序列，是以b為首字母的子序列；[2，2]=2-1=1，表示排在以b為首字母的子序列之后的第一個序列，是以c為首字母的子序列,依此類推。
    所以，當(dāng)算出s(t)的值時，只需比較其與td的值，當(dāng)s(t)=td的值時，則此序列就是所要結(jié)合的2-序列。
3 TFEGC算法
3.1 算法思想
    本算法一共有四大步，第一步是根據(jù)時間限制將原序列劃分為多個子序列；第二步是將得到的子序列轉(zhuǎn)化為2-序列；第三步是根據(jù)uid、fid(t)和s(t)的值將2-序列進行結(jié)合，從而得到所有的候選項；第四步根據(jù)最小支持度minsup得到頻繁項集。
    從上所述可以看出，此算法的主要特點有：(1)加入了時間限制因素；(2)只需要掃描數(shù)據(jù)庫一次，節(jié)省了算法的運行時間；(3)引入了uid、fid(t)、s(t)，使之在形成n-序列的過程中，能夠準(zhǔn)確地找到要結(jié)合的2-序列，不需要掃描所有子序列產(chǎn)生的二序列，提高了算法的時間效率。
3.2 TFEGC核心算法描述
    2-序列結(jié)合的算法如下：
    for all I∈DB{        //I為滿足時間限制的子序列
              l=strlen(I)；                 
              uid=l-2；
           for(n is smaller thanl ){
                if(in∈I and n≠1 and n≠1)
{  //in不能為首尾兩項
                 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用來存放首項，se用來
//存放以其為首項形成的2-序列
        }
    for all tn∈se{
           if(tn.index==fid(in)){//找到所要結(jié)合的2-序列
               in+tn；}//2-序列in和2-序列tn相結(jié)合
        }
    }
3.3 算法舉例
    為了進一步描述TFEGC算法，以圖1中的子序列<abc>產(chǎn)生的第一個2-序列<ab>為例，求以這個2-序列為基礎(chǔ)所形成的候選項過程，如圖3所示。

4 實驗結(jié)果
    算法實驗環(huán)境為PentiumⅣ3.0 GHz雙核 PC機器，內(nèi)存為1 GB，Windows XP操作系統(tǒng)，采用C++語言在VC編程環(huán)境下實現(xiàn)。實驗測試數(shù)據(jù)采用IBM數(shù)據(jù)生成器，該生成器是目前數(shù)據(jù)挖掘相關(guān)研究中使用廣泛和權(quán)威的生成器，可以通過設(shè)置參數(shù)生成不同特性的數(shù)據(jù)集，具體參數(shù)含義如表1所示。

    PrefixSpan算法和TFEGC算法在不同的支持度下的運行時間如圖4所示，從結(jié)果可以看出文中提出的方法優(yōu)于PrefixSpan算法，因為TFEGC算法只需要掃描數(shù)據(jù)庫一次，而且由于uid、fid(t)以及s(t)的引入，避免了一些無用序列的產(chǎn)生，大大減少了運行時間。
    圖5所示的是FEGC和TFEGC在不同數(shù)量的顧客下算法的運行時間，從中也可以看出TFEGC算法的運行時間少于FEGC算法的運行時間。這是因為在二序列的結(jié)合過程中，TFEGC不需要逐個掃描其他的二序列，只需查看uid、fid(t)以及s(t)的值就可以判斷應(yīng)該與哪些二序列進行結(jié)合，而且生成的用戶不感興趣的序列也大大減少了。因為加入了時間的限制，所以根據(jù)支持度來提取頻繁序列的時間也就相應(yīng)地減少了。

    本文提出的算法，可由用戶自己設(shè)定時間限制來查找頻繁序列，也可以用來處理不同數(shù)量的客戶群，所以具有一定的靈活性。又因為其只掃描數(shù)據(jù)庫一次，而且二序列的結(jié)合也具有一定的明確性，所以在時間效率上具有一定的優(yōu)越性[6]。
參考文獻
[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].計算機應(yīng)用，2000，9（20）：13-16.
[5] 連一峰，戴英俠，王航.基于模式挖掘的用戶行為異常檢測[J].計算機學(xué)報，2002，25(3)：325-329.
[6] 吉根林，帥克，孫志揮．?dāng)?shù)據(jù)挖掘技術(shù)及其應(yīng)用[J].南京師范大學(xué)學(xué)報(自然科學(xué)版)，2000，23(2)：25-27.