一種基于單序列的序列模式挖掘方法研究

陳未如， 吳玲玲， 王翠青

(沈陽化工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧沈陽110142)

近年來序列模式挖掘［1］已成為數(shù)據(jù)挖掘［2］的一個(gè)重要方面，其應(yīng)用范圍也不局限于交易數(shù)據(jù)庫.在web挖掘、文本分析、DNA序列分析、股票趨勢(shì)分析等新型應(yīng)用數(shù)據(jù)源眾多方面得到針對(duì)性研究.序列模式(Sequential Patterns)是指在序列數(shù)據(jù)庫中頻繁出現(xiàn)的序列.序列模式挖掘涉及到支持度、用戶指定的最小支持度、頻繁子序列、序列模式性質(zhì)等，參見文獻(xiàn)［1］.

序列模式挖掘有2種主要的框架:多序列的序列模式挖掘［3］和單序列的序列模式挖掘［4］.序列模式挖掘問題由Agrawal和Srikant首先提出，在基于 Apriori的 GSP算法中，Srikant和Agrawal推廣了早期提出的概念，包括時(shí)間約束、滑動(dòng)時(shí)間窗口和用戶定義的分類法［5］.Kazuhiro Shimizu和Takao Miura提出了文本挖掘和析取模式的概念，并提出基于單序列的頻繁析取模式挖掘的新方法.介紹了一種滿足反單調(diào)性的復(fù)雜的計(jì)算方法，并證明了方法有效可行［6］.到目前為止，基于多序列的序列模式挖掘的研究十分廣泛，現(xiàn)有的關(guān)系模式挖掘理論也大多基于多序列.因此，本文將重點(diǎn)研究基于單序列的序列模式的性質(zhì)和挖掘方法.

1 基于單序列數(shù)據(jù)庫的序列模式

單序列通常是相當(dāng)長(zhǎng)的數(shù)據(jù)串.與多序列不同，在單序列中判斷元素間關(guān)聯(lián)性的依據(jù)是它們之間的距離，元素間的關(guān)聯(lián)性隨距離的增大而減小.筆者關(guān)心的是頻繁出現(xiàn)在相對(duì)近的距離內(nèi)的子序列.由此引出如下滑動(dòng)窗口［7］的概念.

定義1 滑動(dòng)窗口(Sliding Window).對(duì)于給定的正整數(shù)w，在單序列s上從某一個(gè)元素開始的w個(gè)元素所組成的序列稱之為一個(gè)數(shù)據(jù)窗口，w稱為該數(shù)據(jù)窗口的寬度.一個(gè)寬度為w的數(shù)據(jù)窗口最多包含w個(gè)元素，這樣的數(shù)據(jù)窗口可以從單序列的第一個(gè)元素開始一直向后滑動(dòng)，稱之為滑動(dòng)窗口.滑動(dòng)窗口覆蓋了單序列從某一元素開始的長(zhǎng)度為w的序列片段.對(duì)于給定長(zhǎng)度為n的單序列和滑動(dòng)窗口寬度w，存在n個(gè)滑動(dòng)窗口，表示為s(w)={s1，s2，…，si，…，sn}，窗口的下標(biāo)對(duì)應(yīng)單序列元素的序號(hào).單序列s的一個(gè)寬度為w的滑動(dòng)窗口si可表示為si∈s(w).可以想象，滑動(dòng)窗口sn，sn-1，…，sn-w+1所覆蓋元素的個(gè)數(shù)分別為1，2，…，w.

通常，滑動(dòng)窗口的寬度w設(shè)置為用戶感興趣的元素關(guān)聯(lián)距離，即在單序列中距離超出該w的元素之間被認(rèn)為是沒有關(guān)聯(lián).或者說，只有處在同一窗口內(nèi)的元素才被認(rèn)為是有關(guān)聯(lián)的.由于窗口是滑動(dòng)的，序列中的某一元素可能處于不同的窗口中.

定義2 包含與正包含.對(duì)于給定寬度為w的滑動(dòng)窗口si和序列α，滑動(dòng)窗口si所對(duì)應(yīng)的序列片段包含序列α，則也稱窗口si包含序列α，或序列α包含于窗口si，記為α∠si(如果α∠si，也稱α是si的子序列，si是的α超序列［1］).特別地，若序列α的首字符與窗口si的首字符相同，則稱窗口si正包含序列α，或序列α正包含于窗口si，記為α⊿si.

顯然，如果一個(gè)序列α是序列s的某一窗口si的子序列，則也一定是序列s的子序列.

定義3 基于單序列數(shù)據(jù)庫的序列支持度.對(duì)于給定的滑動(dòng)窗口寬度w，在單序列數(shù)據(jù)庫(SSDB)中，所有不同窗口SSDB(w)={s1，s2，…，si，…，sn}中正包含子序列α的滑動(dòng)窗口數(shù)目之和稱為子序列α的支持度.即:

例1: 給定單序列s=＜a b c a b d a b b b e c b a b d＞，序列及位置標(biāo)號(hào)如表1所示.

表1 單序列s=＜a b c a b d a b b b e c b a b d＞位置編號(hào)Table 1 Position number of single sequence s=＜a b c a b d a b b b e c b a b d＞

若用戶給定的滑動(dòng)窗口的寬度為w=6，則序列s對(duì)子序列α=＜a，b，c＞的支持情況如表2所示.

表2 序列s對(duì)子序列α=＜a，b，c＞的支持情況Table 2 Sequence s pair sequence α=＜a，b，c＞support case

s中支持序列α=＜a，b，c＞的滑動(dòng)窗口有2個(gè)，即α的支持度為support(α)=2.

定義4 基于單序列數(shù)據(jù)庫的序列模式.在單序列數(shù)據(jù)庫(SSDB)中，對(duì)于滑動(dòng)窗口寬度w，以及用戶指定的最小支持度minsup，若子序列α的支持度大于等于minsup，即support(α)≥minsup，則稱α為序列模式(SP，Sequential Pattern).

例2: 對(duì)于例1給定的單序列s，若用戶給定的滑動(dòng)窗口的寬度為w=6，用戶指定的最小支持度minsup=0.125，子序列＜abc＞的支持度support(＜abc＞)=2/16=0.125≥minsup，故子序列＜abc＞為序列模式.同樣，可得單序列s的所有序列模式:＜a＞，＜b＞，＜c＞，＜d＞，＜aa＞，＜ab＞，＜ac＞，＜ad＞，＜ba＞，＜bb＞，＜bc＞，＜bd＞，＜ca＞，＜cb＞，＜cd＞，＜aab＞，＜aba＞，＜abb＞，＜abc＞，＜abd＞，＜bab＞，＜bad＞，＜bba＞，＜bbb＞，＜bbc＞，＜bbd＞，＜bca＞，＜bcb＞，＜cab＞，＜cad＞，＜cba＞，＜cbb＞，＜cbd＞，＜abab＞，＜abbb＞，＜babd＞，＜bcab＞，＜bcba＞，＜cabd＞，＜cbab＞.

同多序列序列模式一樣，單序列模式也滿足Apriori性質(zhì)［8］，即基于關(guān)聯(lián)規(guī)則挖掘的Apriori性質(zhì).

性質(zhì)1 單序列模式Apriori性質(zhì)(反單調(diào)性)［8］.一個(gè)序列模式的子序列一定也是序列模式.

根據(jù)單序列模式Apriori性質(zhì)，可設(shè)計(jì)相應(yīng)的基于單序列的序列模式挖掘算法.

定義5 序列覆蓋.對(duì)于給定的序列α，β和序列s，如果α∠s且β∠s，則必然存在一個(gè)s的連續(xù)子序列s'，使α∠s'且β∠s'.如果不存在連續(xù)序列s″，使s″≠s'，且s″∠s'，α∠s″，β∠s″，稱s'為序列集{α，β}對(duì)序列s的覆蓋，表示為s'= Covers(α，β).序列s'的長(zhǎng)度稱為序列α和β對(duì)序列s的覆蓋長(zhǎng)度，記為ds(α，β).一般地，序列集{α1，α2，…，αn}對(duì)序列s的覆蓋 Covers(α1，α2，…，αn)是指s中包含所有序列α1，α2，…，αn的最小連續(xù)子序列，該連續(xù)子序列的長(zhǎng)度就是序列集{α1，α2，…，αn}對(duì)序列s的覆蓋長(zhǎng)度，記為ds(α1，α2，…，αn).特殊地，當(dāng) n=1時(shí)，Covers(α)是指s中包含序列α的最小連續(xù)子序列，其覆蓋長(zhǎng)度記為ds(α).通常，序列或序列集對(duì)序列s的覆蓋表示為相對(duì)s的下標(biāo)i和覆蓋長(zhǎng)度d的二元組{i，d}.

例3: 對(duì)于例1給定的單序列s，設(shè)滑動(dòng)窗口的寬度為w=6，以起始位置為1的滑動(dòng)窗口s1為例，可得以下幾種情況:

(1)序列＜abc＞和＜bca＞在s1中交叉出現(xiàn)，ds(＜abc＞，＜bca＞)=4，Covers1(＜abc＞，＜bca＞)={1，4};

(2)序列＜abc＞和＜abd＞在s1中接續(xù)出現(xiàn)，ds(＜abc＞，＜abd＞)=6，Covers1(＜abc＞，＜abd)={1，6};

(3)序列＜abc＞和＜bd＞在s1中間隔出現(xiàn)，ds(＜abc＞，＜bd＞)=6，Covers1(＜abc＞，＜bd＞)={1，6};

(4)序列＜abd＞在s1中的覆蓋長(zhǎng)度ds(＜abd＞)=6，Covers1(＜abd＞)={1，6};

(5)序列＜a＞，＜b＞，＜d＞在s1中覆蓋長(zhǎng)度 ds(＜a＞，＜b＞，＜d＞)=6，Covers1(＜a＞，＜b＞，＜d＞)={1，6}.

根據(jù)覆蓋的定義，有下列性質(zhì)成立:

性質(zhì)2 一個(gè)序列的覆蓋長(zhǎng)度大于等于該序列的長(zhǎng)度.

性質(zhì)3 兩個(gè)序列的覆蓋長(zhǎng)度小于等于這兩個(gè)序列自身覆蓋長(zhǎng)度之和;同理，n個(gè)序列的覆蓋長(zhǎng)度小于等于這n個(gè)序列自身覆蓋長(zhǎng)度之和.

性質(zhì)4 對(duì)于序列α，β和序列s，設(shè)Covers(α) ={i，x}，Covers(β)={j，y}，Covers(α，β)={k，z}，j＞i，如果j=i+x，則k=i，z=x+y;如果j＜i+x，則k=i，z=max(j－i+y，x);如果j＞i+x，則k=i，z=j－i+y.

性質(zhì)5 序列或序列集對(duì)于給定序列s的覆蓋可能多于一個(gè).

2 基于單序列數(shù)據(jù)的序列模式挖掘算法

前一節(jié)給出的各種性質(zhì)有助于設(shè)計(jì)高效的挖掘算法，并為相關(guān)算法的正確性證明提供依據(jù).對(duì)于一個(gè)長(zhǎng)度為n的單序列s，設(shè)計(jì)一個(gè)m× n正包含矩陣Q，令Q［i，j］表示s的滑動(dòng)窗口sj對(duì)序列模式i支持情況，即序列模式i對(duì)sj的覆蓋長(zhǎng)度.

算法 基于單序列的序列模式挖掘(S3PM算法).

輸入:長(zhǎng)度為n的單序列數(shù)據(jù)庫SSDB，客戶給定的最小支持度 minsup，滑動(dòng)窗口的寬度w.

輸出:滿足最小支持度minsup和滑動(dòng)窗口寬度w要求的序列模式集SP.

方法:

(1)SP=nul;

(2)計(jì)算所有長(zhǎng)度為1的序列模式，加入序列模式集SP_1中，對(duì)于SSDB中的每一個(gè)單字符a，計(jì)算a出現(xiàn)的頻度，如果support(a)≥minsup，則表明它是一個(gè)序列模式，在矩陣Q中加入相應(yīng)行i，令SP=SP∪{a};并對(duì)于每處出現(xiàn)a的位置j，令Q［i，j］=1;對(duì)應(yīng)其他位置k的Q［i，k］=0;

(3)L=0;i=|SP_1|+1;

(4)do

(5)L++;

(6)for each sp in SP_L //在SP_L基礎(chǔ)上求SP_L+1

(7)令t表示sp對(duì)應(yīng)Q所在行;

(8)for each sp1 in SP_1 //判斷SP與SP _1是否可構(gòu)成新的序列模式

(9)Q［i，0］=0; //記錄可能的新模式的支持?jǐn)?shù)

(10)令v表示sp1對(duì)應(yīng)Q所在行;

(11)for j=1 to n－L－1

(12)if Q［t，j］==null then{Q［i，j］= null;continue;}

(13)u=min(n，j+w);

(14)for k=j+Q［t，j］to u

(15)if Q［v，k］≠null and j－t+Q［v，k］≤w then

(16)Q［i，j］=j－t+Q［v，k］;

(17)Q［i，0］++;

(18)endif

(19)endfor

(20)endfor

(21)if Q［i，0］(minsup*n then

(22)SP=SP∪{sp+sp1}; //sp+sp1表示SP與SP_1的串聯(lián)

(23)i++;

(24)endif

(25)endfor

(26)endfor

(27)until在L_序列模式集基礎(chǔ)上未得到任何新的L+1_序列模式

(28)最后得到的SP就是所求序列模式集.

對(duì)于例1給定的單序列s=＜a b c a b d a b b b e c b a b d＞，若用戶給定的滑動(dòng)窗口的寬度為w=6，用戶指定的最小支持度minsup= 0.125，執(zhí)行算法S3PM挖掘構(gòu)成及結(jié)果見表3.

表3 基于單序列數(shù)據(jù)的序列模式挖掘算法的執(zhí)行過程示例Table 3 Examples of implementation process of algorithms on mining Sequential Pattern based on single data sequence

3 實(shí)驗(yàn)驗(yàn)證與性能分析

實(shí)驗(yàn)數(shù)據(jù)是某大學(xué)關(guān)于偏序模式挖掘的研究生畢業(yè)論文.此文本數(shù)據(jù)共包含25 122個(gè)字符.

WinSize是指滑動(dòng)窗口寬度，MinSup是指用戶給定的最小支持度，L1代表1_序列模式集，也可以表示為SP_1.類似地，L_序列模式集表示長(zhǎng)度為L(zhǎng)的所有序列模式組成的序列模式集，即SP_L.

(1)算法可以得到模式的全集和閉包集，若設(shè)定WinSize=6，MinSup=0.001，挖掘全集及閉包集結(jié)果見表4.

表4 序列模式挖掘的全集和閉包集Table 4 Complete sets and closure sets ofsequential pattern mining

由于閉包集可以減小冗余，故以下各種序列模式挖掘結(jié)果都是閉包集.

(2)當(dāng)MinSup=0.001時(shí)，不同WinSize挖掘結(jié)果見表5.

表5 不同WinSize挖掘結(jié)果Table 5 Mining results of different WinSize

如表5所示，當(dāng)MinSup一定時(shí)，隨著WinS-ize的增大，總模式數(shù)不斷增大，L_序列模式集的個(gè)數(shù)不斷增大.這種規(guī)律正與基于滑動(dòng)窗口的序列模式的形式相吻合，滑動(dòng)窗口寬度增大，其所覆蓋的字符數(shù)目增多，字符出現(xiàn)的正包含次數(shù)也隨之增大，故子序列的支持度增大.

在算法挖掘過程中，得到的序列模式＜偏序關(guān)系模式挖掘＞、＜關(guān)系模式挖掘＞、＜偏序模式挖掘＞、＜序列模式挖掘＞和＜并發(fā)序列模式＞等模式與此研究生畢業(yè)論文的關(guān)鍵字相吻合，驗(yàn)證了算法的有效性.

(3)當(dāng)WinSize=6時(shí)，不同MinSup所得挖掘結(jié)果見表6.

表6 不同MinSup所得挖掘結(jié)果Table 6 Mining results of different MinSup

如表6所示，當(dāng)WinSize一定時(shí)，隨著Min-Sup的增大，總模式數(shù)不斷減小，L_序列模式集的個(gè)數(shù)不斷減小.這種規(guī)律正與基于單序列的序列模式概念相吻合，support(α)≥minsup，稱α為序列模式.若minsup增大，子序列α的個(gè)數(shù)自然變小.

4 結(jié)束語

序列模式挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要研究方向，基于單序列的序列模式是本文提出的新的類型模式，目前沒有同類工作.在各個(gè)領(lǐng)域具有廣泛的應(yīng)用，其中包括股票分析、文本挖掘、客戶購買行為模式預(yù)測(cè)、web訪問和DNA序列分析等新型應(yīng)用數(shù)據(jù)源，這將是今后工作的重點(diǎn)研究方向.

［1］ Han Jiawei，Micheline Kamber.數(shù)據(jù)挖掘:概念與技術(shù)［M］.范明，孟小峰，等譯.8版.北京:機(jī)械工業(yè)出版社，2001:8－10.

［2］ 紀(jì)希禹，韓秋明，李微.數(shù)據(jù)挖掘技術(shù)應(yīng)用實(shí)例［M］.北京:機(jī)械工業(yè)出版社，2009:1－10.

［3］ Ding Bolin，Lo David，Han Jiawei，et al.Efficient Mining of Closed Repetitive Gapped Subsequences from a Sequence Database［DB/OL］.(2010－09－30)［2011－12－22］.http://aisl.umbc.edu/ show/resource/id/433/Efficient%20Mining % 20of%20Closed%20Repetitive%20Gapped% 20Subsequences%20from%20a%20Sequence% 20Database.html.

［4］ Han Jiawei，Micheline Kamber.Data Mining:Concepts and Techniques［M］.北京:機(jī)械工業(yè)出版社，2005:470－490.

［5］ Agrawal R，Srikant R.Mining Sequential Patterns［DB/OL］.(2003－05－13)［2011－12－22］.http://rakesh.agrawal-family.com/papers/.

［6］ Shimizu K，Miura T.Disjunctive Sequential Patterns on Single Data Sequence and Its Anti-monotonicity［M］∥Perner P，Imiya A.Lecture Machine Learning and Data Mining in Pattern Recognition.Notes in Computer Science:Ms.Hitomi Kanehara and Risa Wataya，2005:376－383.

［7］ 李國徽，楊兵，胡惇，等.挖掘滑動(dòng)窗口中的數(shù)據(jù)流頻繁模式［J］.小型微型計(jì)算機(jī)系統(tǒng)，2008，29 (8):45－49.

［8］ 張長(zhǎng)海，胡孔法，陳凌.序列模式挖掘算法綜述［J］.揚(yáng)州大學(xué)學(xué)報(bào)，2007，10(1):41－45.