高效的一次性弱間隙序列模式挖掘算法

楊鴻茜，武優(yōu)西*，耿萌，劉靖宇，李艷

（1.河北工業(yè)大學(xué)人工智能與數(shù)據(jù)科學(xué)學(xué)院，天津 300401；2.河北工業(yè)大學(xué)經(jīng)濟管理學(xué)院，天津 300401）

0 引言

隨著大數(shù)據(jù)的發(fā)展和應(yīng)用，如何高效地挖掘出數(shù)據(jù)背后的潛在信息并將這些信息整合利用到更深層次的研究中變得尤為重要。序列模式挖掘（SPM）［1-2］作為數(shù)據(jù)挖掘［3-4］領(lǐng)域的一個重要子課題，被廣泛應(yīng)用于脫氧核糖核酸（DNA）檢測［5-6］、生物遺傳學(xué)［7-8］、文本檢索［8-9］、股票預(yù)測［9-10］等領(lǐng)域。

傳統(tǒng)的SPM 方法［11-12］只考慮模式在序列中是否出現(xiàn)，而忽略了模式的重復(fù)性。因此，為了更加靈活地應(yīng)對用戶的挖掘需求，發(fā)現(xiàn)更有價值的模式，帶間隙約束的可重復(fù)SPM 方法應(yīng)運而生。根據(jù)模式的出現(xiàn)形式可以將其分為4 種情況，即無特殊條件［13］、無重疊條件［14-15］、不相交條件［16-17］和一次性條件［18-19］。其中，一次性條件［20-21］是指序列中的任何項目只能被模式匹配一次，這種約束條件既規(guī)避了結(jié)果集爆炸的問題，又盡可能地避免遺漏重要的信息。

在傳統(tǒng)的間隙約束序列模式挖掘中，模式的每一項都被認為具有相同意義，這與實際情況是不符的。比如，商人會更關(guān)注高利潤的商品，股民會更關(guān)注波動較大的股票市場信息。因此，弱間隙約束的概念被提出并用于序列模式挖掘領(lǐng)域，即僅挖掘那些用戶更感興趣的項，而忽略其他不重要的項。文獻［22］提出了一次性弱間隙強模式挖掘（OWSP-Miner）算法，可以實現(xiàn)在單項序列中挖掘一次性自適應(yīng)弱間隙強模式。

但是上述算法只能在一種特殊序列中進行挖掘，即單項序列。實際生活中的通用序列由若干項集組成，每個項集都包含許多有序的項，即項集序列。在項集序列中研究此問題更有價值和實用性。本文提出一次性弱間隙序列模式挖掘（OWP）算法，該算法在更具通用性的項集序列上高效挖掘一次性弱間隙強模式。首先區(qū)別于單項序列上的一次性定義，重新定義一次性條件以適用于項集序列的情況，在支持度計算方面，提出SupII 算法，采用倒排索引的數(shù)據(jù)結(jié)構(gòu)避免重復(fù)掃描數(shù)據(jù)庫，提高算法的匹配效率。然后在候選模式生成部分，采用模式連接策略，減少冗余候選模式數(shù)量。

1 相關(guān)工作

自序列模式挖掘的概念被提出以來，其廣泛應(yīng)用于大數(shù)據(jù)挖掘、文本分析、生物信息學(xué)等諸多領(lǐng)域［23-24］。近年來，由于帶間隙［25］的模式更具靈活性并且能夠考慮模式在序列上的重復(fù)性，相關(guān)研究的重點不斷向間隙約束序列模式挖掘靠攏。文獻［26］提出一種有效的方法來挖掘具有間隙約束的完整閉合序列模式；文獻［27］提出基于通配符約束的生物序列模式挖掘算法，使用單向掃描和雙向掃描相結(jié)合的方式在生物序列中挖掘帶有通配符的頻繁模式；文獻［28］提出一個挖掘框架，可以在物聯(lián)網(wǎng)設(shè)備產(chǎn)生的不確定數(shù)據(jù)集中挖掘潛在的高平均效用模式；文獻［29］將具有特定間隙數(shù)的序列模式挖掘方法應(yīng)用于DNA 序列。

然而，在上述算法中，所使用的數(shù)據(jù)集的每一項都被認為是具有相同意義的。而在實際應(yīng)用中，用戶對于不同的項目感興趣程度也是不同的。因此，文獻［30］提出一種基于弱間隙的模式挖掘算法，根據(jù)影響程度將項目集劃分為強項集合和弱項集合，僅挖掘那些用戶更感興趣的強模式。雖然該算法的效率很高，但它沒有關(guān)注到序列項目使用的重復(fù)性，并且可能造成結(jié)果集爆炸的問題。為了避免該問題，文獻［22］提出OWSP-Miner 算法，該算法挖掘一次性條件下自適應(yīng)弱間隙強模式，一次性條件既可以有效減少冗余模式的產(chǎn)生，又充分考慮到了模式在序列上的重復(fù)性。

然而，OWSP-Miner 只能在單項序列上進行挖掘，并不適用于通用的項集序列。因此，本文提出OWP 算法來挖掘頻繁的一次性弱間隙強模式。

2 相關(guān)定義

定義1（序列數(shù)據(jù)庫）序列數(shù)據(jù)庫是一個包含k條序列的集合，表示為D=｛s1，s2，…，s｝k。T=｛t1，t2，…，t｝c是數(shù)據(jù)庫D中所有項的集合，其中，c是T的大小。D中的每條序列都是一個包含若干個項集的列表，表示為si=si1，si2，…，sin，其中，n為序列si的大小，表示為size（si）=n。每個項集sij都是集合T的一個有序子集，用lij=len（si）j表示項集的長度，序列的長度是它所包含項集長度的總和，即

定義2（強項集合和弱項集合）所有的項根據(jù)用戶感興趣程度分為強項集合（τ）和弱項集合（ω），并且τ∩ω=?,τ∪ω=T。

例1給定一個項集序列數(shù)據(jù)庫D如表1 所示，其 中，s1=（bc）（bef）（abce）（abd）（abd）（cf）（adf），可知，T=｛a，b，c，d，e，f｝，size（s1）=7，len（s1）=20。如果強項集合為τ=｛a，b，d，e｝，那么弱項集合就為ω=｛c，f｝。

表1 項集序列數(shù)據(jù)庫DTable 1 Itemset sequence dataset D

定義3（弱間隙強模式）大小為r的弱間隙強模式可表示為p=p1*p2*…*pr，其中，pi?τ（1 ≤i≤r），*表示任意數(shù)量的弱項集。

定義4（出現(xiàn)和一次性出現(xiàn)）給定序列s=s1，s2，…，sn和一個模式p=p1*p2*…*pr。如果存在r個整數(shù)o=滿足pi?,1 ≤i≤r,1 ≤o1＜o2＜…oi＜…＜or≤n，并且oi-1和oi之間的任一項集都是弱項集，那么o=被稱為模式p在序列s上的一個出現(xiàn)。給定模式p在s上的另一個出現(xiàn)o'=，如果滿足對任意q和t，若，那么就稱o和o'是模式p在序列s上的2 個一次性出現(xiàn)。

定義5（支持度）弱間隙強模式p在序列si上滿足一次性條件的出現(xiàn)次數(shù)就稱作模式p在序列si上的支持度，表示為sup（p，si）。模式p在序列數(shù)據(jù)庫D上的支持度是模式p在D中各條序列上的支持度之和，即

例2給定序列s1=（bc）（bef）（abce）（abd）（abd）（cf）（adf）和一個弱間隙強模式p=（b）*（b）*（ad）。如果忽略弱間隙約束，那么因為p1=（b）?s1=（bc），p2=（b）?s2=（bef），p3=（ad）?s4=（abd），則<1，2，4>是模式p在s1上的一個出現(xiàn)。然而，當τ=｛a，b，d，e｝，ω=｛c，f｝時，<1，2，4>就不是一個出現(xiàn)，因為s3=（abce）中存在強項，所以<1，2，4>不滿足弱間隙約束。顯然，<2，3，4>、<3，4，5>和<4，5，7>是模式p滿足弱間隙約束的全部出現(xiàn)。其中，<2，3，4>和<3，4，5>不滿足一次性條件，因為p1∩p2=b≠?并且索引3 在兩次出現(xiàn)中被重復(fù)使用，即項集（abce）中的項'b'在出現(xiàn)<2，3，4>中與p2匹配，在出現(xiàn)<3，4，5>中又重復(fù)與p1匹配。盡管<2，3，4>和<4，5，7>也重復(fù)使用了s4，但是在<2，3，4>中，使用的是s4=（abd）中的項'd'，而在出現(xiàn)<4，5，7>中，使用的是s4=（abd）中的項'b'，因此它們是滿足一次性條件的兩個出現(xiàn)。綜上所述，一次性弱間隙條件下p的所有出現(xiàn)為<2，3，4>和<4，5，7>，即p在序列s1上的支持度為sup（p，s1）=2。同理，sup（p，s2）=1，sup（p，s3）=0。根據(jù)定義5，模式p在序列數(shù)據(jù)庫D中的支持度為

定義6（頻繁模式）給定一個最小支持度閾值minsup，如果一個弱間隙強模式p在序列數(shù)據(jù)庫D上的支持度不小于minsup，那么模式p就被稱為一個頻繁的一次性弱間隙強模式。

例3在例2 中，若給定minsup 為3，則模式p=（b）*（b）*（ad）是一個頻繁的一次性弱間隙強模式，因為其在表1 所示的項集序列數(shù)據(jù)庫中的支持度sup（p，D）=3≥minsup。

定義7（一次性弱間隙序列模式挖掘）給定項集序列數(shù)據(jù)庫D、弱項集合和最小支持度閾值minsup，一次性弱間隙序列模式挖掘的研究目標是挖掘序列數(shù)據(jù)庫D中所有頻繁的一次性弱間隙強模式。

3 算法描述

3.1 準備階段

為了在后續(xù)計算支持度的過程中減少對原始數(shù)據(jù)的遍歷次數(shù)以及無用候選模式的生成，準備階段主要有2 個步驟：創(chuàng)建倒排索引和剪枝不頻繁的項以獲得1 長度的頻繁模式集合。

步驟1掃描序列數(shù)據(jù)庫以獲得所有項的集合，并為每個序列創(chuàng)建各自的倒排索引。

定義8（倒排索引）對包含k條序列的序列數(shù)據(jù)庫D，創(chuàng)建k個倒排索引I=｛i1，i2，…，ik｝。倒排索引ij對應(yīng)序列sj，如果sj有h個不同的項，那么倒排索引ij=｛k1∶v1，k2∶v2，…，kh∶vh｝，其中，鍵k（a1≤a≤h）存儲的是項，而值va存儲的是項ka出現(xiàn)位置的列表。

例4給定序列s1=s1s2s3s4s5s6s7=（bc）（bef）（abce）（abd）（abd）（cf）（adf）。以 項'a'為 例，不難發(fā) 現(xiàn)'a'出現(xiàn)在序列中的第3 個項集、第4 個項集、第5 個項集以及第7 個項集中，因此，項'a'的倒排索引為［3，4，5，7］。同理，可以得到該序列相應(yīng)的倒排索引為：i1=｛'a'：［3，4，5，7］，'b'：［1，2，3，4，5］，'c'：［1，3，6］，'d'：［4，5，7］，'e'：［2，3］，'f'：［2，6，7］｝。

步驟2依次計算每個強項的支持度，如果該項的支持度小于minsup，則對其進行剪枝。此外，剪枝所有弱項，因為弱間隙約束規(guī)定弱項只允許出現(xiàn)在間隙中，而不可以構(gòu)成模式。

例5在例4 中，假設(shè)在s1中挖掘1 長度的頻繁模式，若minsup 為3，τ=｛a，b，d，e｝，ω=｛c，f｝，則強項'e'被剪枝，因為它的支持度為2。盡管項'c'和'f'的支持度都為3，但它們依然要被剪枝，因為它們是弱項。

3.2 支持度計算

在第3.1 節(jié)中，通過創(chuàng)建倒排索引和剪枝得到了長度為1 的頻繁模式集合。關(guān)鍵問題是計算長度為m（m≥2）的模式p在序列s中的支持度?；谀Ｊ街懈黜椀某霈F(xiàn)位置，提出SupII算法來計算長度為m（m≥2）的模式的支持度。SupII 算法主要分為5 個步驟。

步驟1給定長度為m（m≥2）的模式p=e1，e2，…，ej，…，em（1≤j≤m，ej?τ）。首先為模式p所使用的倒排索引創(chuàng)建m層節(jié)點。

例6給定一 個弱間 隙強模式p=（b）*（b）*（ad），由例4 可知，模式p中包含的項'a'、'b'和'd'的倒排索引分別為'a'：［3，4，5，7］、'b'：［1，2，3，4，5］、'd'：［4，5，7］，則創(chuàng)建4 層節(jié)點如圖1 所示。

圖1 模式p 在序列s1中的所有出現(xiàn)Fig.1 The supports pattern p in sequence s1

步驟2為了保證一次性條件，創(chuàng)建并初始化使用字典u以記錄不同項被使用過的位置。使用字典中的每個元素都由兩個部分組成：鍵和值。鍵存儲項，值存儲對應(yīng)項被使用過的位置索引。

比如，當計算模式p=（b）*（b）*（ad）的支持度時，初始化使用字典u為｛'a'：［］，'b'：［］，'d'：［］｝。

步驟3按照p=e1，e2，…，ej，…，em（1≤j≤m，ej?τ）從左往右的順序，從第1 層的每一個未被使用過的位置開始，自上而下尋找模式p所有滿足一次性弱間隙約束的出現(xiàn)。對于所有的eu…e（v1≤u≤v≤m）可分為以下2 種情況：

1）若eu…ev在同一個項集內(nèi)，則對于所有的ej（u≤j≤v），出現(xiàn)位置相同。

2）若eu…ev在不同項集內(nèi)，則根據(jù)項集的先后順序，出現(xiàn)位置也保持相應(yīng)的先后順序，并且不同項集間滿足弱間隙約束。

例如，在圖1 中，1 是第1 層中第1 個沒有被使用過的位置，于是在第2 層中尋找大于1 且未被使用過的位置，即2。繼續(xù)在第3 層尋找大于2 且未被使用過的位置，得到位置3。但是，在同一個項集內(nèi)的第4 層中沒有找到位置3。因此，位置3 被舍棄，回溯到第3 層的下一個位置4。然而，在位置2、4 中，即s2和s4之間存在強項s3=（abce），不滿足弱間隙約束，因此，需要回溯到第2 層，尋找第2 層中下一個未被使用的位置3。此時，位置1、3 也不滿足弱間隙約束，于是繼續(xù)回溯到第1 層找到下一個位置2。按照同樣的方法向下迭代，可以找到模式p的一次出現(xiàn)<2>、<3>、<4，4>，即<2，3，4>。

步驟4得到模式p的一次出現(xiàn)后，需要在使用字典u中更新當前已使用過的位置。

例如，在獲得模式p的第1 個出現(xiàn)<2，3，4>后，更新使用字典為u=｛'a'：［4］，'b'：［2，3］，'d'：［4］｝，因為（b）、（b）和（ad）分別對應(yīng)<2>、<3>、<4，4>。

步驟5重復(fù)步驟3 和步驟4，直到任一倒排索引指向NULL。

繼續(xù)計算模式p的支持度，當獲得第1 層的下一個位置3 時，因為3 已經(jīng)存在于使用字典u中，即'b'：［2，3］，所以不滿足一次性條件，因此，選擇下一個位置4。重復(fù)上述步驟，可以得到模式p在s1中的第2 次出現(xiàn)<4>、<5>、<7，7>，即<4，5，7>。同時，更新使 用字典為u=｛'a'：［3，7］，'b'：［2，3，4，5］，'d'：［4，7］｝。當尋找下一個出現(xiàn)時，第1 層的倒排索引指向NULL，算法結(jié)束。

SupII 算法的偽代碼如算法1 所示。

算法1SupII 算法

3.3 候選模式生成

傳統(tǒng)的序列模式挖掘方法通常采用I-Connection和S-Connection 來生成候選模式，這種方法的本質(zhì)是枚舉策略，雖然可以避免遺漏有希望的候選模式，但同時也會產(chǎn)生大量冗余的模式而極大地增加運行時間。為了解決這個問題，本文采用模式連接策略來生成候選模式。

定義9（前綴和后綴模式，子模式和超模式）如果一個長度為m的模式p=e1，e2，…，em，那么模式r=e1，e2，…，em-1和q=e2，e3，…，em分別為模式p的前綴和后綴，表示為r=prefix（p）和q=suffer（p）。此外，模式r和q被稱為模式p的子模式，模式p又被稱為模式r和q的超模式。

定義10（I-Join，S-Join）給 定2 個長度為m的弱間隙強模式q和r，其中，模式r表示為r=e1，e2，…，em-1，em。如果suffer（q）=prefix（r），根據(jù)em-1，em可 分為以下2 種情況：

1）em-1和em存在于同一個項集中。在這種情況下，使用I-Join 的方法生成超模式t，即添加項em到模式q的最后一個項集中，表示為t=q⊕r。

2）em-1和em存在于2 個不同項集中。在這種情況下，使用S-Join 的方法生成超模式t，即將項集（em）附加到模式q的末尾，表示為t=q?r。

例7給定3 個4 長度的弱間隙強模式p=（b）*（ab）*（d），q=（ab）*（de）和r=（ab）*（d）*（e），可 知，suffer（p）=prefix（q）=prefix（r）=（ab）*（d），因此，模式p和q可以通過I-Join 生成超模式t1=（b）*（ab）*（de），模式p和r可以通過S-Join 生成超模式t2=（b）*（ab）*（d）*（e）。

定義11（模式連接）用2 個長度為m的頻繁模式通過I-Join 和S-Join 生成長度為m+1 的候選模式，這個方法被稱為模式連接。需要注意的是，在使用I-Join 方法時，同一項集內(nèi)的項要按字典順序排序。

例8給定1 長度的頻繁模式集：｛（a），（b），（d）｝，可以通過I-Join 生成超模式（ab）、（ad）和（bd），但是模式（da）不合規(guī)則，因為它沒有按照字典順序排序。

下面通過例9 來闡述模式連接策略的優(yōu)越性。

例9給定2 長度的頻繁模式集｛（ad），（b）*（a），（d）*（b）｝和1 長度的頻繁模式集｛（a），（b），（d）｝。如果采用傳統(tǒng)的I-Connection 和S-Connection方法生成候選模式的話，將得到12 個3 長度的候選模式。但是如果采用模式連接策略，只生成（ad）*（b）、（d）*（b）*（a）和（b）*（ad）3 個候選模式。顯然，模式連接策略大幅減少了候選模式的數(shù)量。因此，模式連接策略優(yōu)于I-Connection 和S-Connection 方法，能夠有效縮減候選模式數(shù)量，達到提高挖掘效率的目的。

模式連接策略的偽代碼如算法2 所示。

算法2PatternJoin 算法

3.4 OWP 算法

本節(jié)通過OWP 算法來挖掘序列數(shù)據(jù)庫中所有頻繁的一次性弱間隙強模式，具體步驟如下：

步驟1遍歷序列數(shù)據(jù)庫D，創(chuàng)建倒排索引I。

步驟2計算各項的支持度，剪枝不頻繁的強項并將頻繁的強項存入FP1與FPItem。

步驟3在FPm-1（m≥2）基礎(chǔ)上，使用模式連接策略生成長度為m的候選模式Candim。

步驟4通過SupII 算法計算Candim中每個候選模式的支持度，并將頻繁的模式存入FPm與FPItem。

步驟5重復(fù)步驟3 和步驟4，直到?jīng)]有新的候選模式生成，算法結(jié)束。

OWP 算法的偽代碼如算法3 所示。

算法3OWP 算法

OWP 算法主要有以下2 個優(yōu)點：1）OWP 采用倒排索引結(jié)構(gòu)，避免了對原始序列數(shù)據(jù)庫的重復(fù)掃描，并且使用項的出現(xiàn)位置計算模式支持度，提高了搜索與計算效率；2）OWP 采用模式連接策略生成候選模式，減少了冗余候選模式的生成，其效率遠遠優(yōu)于經(jīng)典的I-Connection 和S-Connection 方法。

3.5 時空復(fù)雜度分析

3.5.1 時間復(fù)雜度

OWP 算法的時間復(fù)雜度為O（k×N/r+L×logaL），其中，k、r、N和L分別為模式最大長度、1 長度模式的數(shù)量、序列總長度和候選模式數(shù)量。

OWP 算法的時間復(fù)雜度主要由準備階段、支持度計算和候選模式生成3 個部分構(gòu)成。在準備階段，創(chuàng)建倒排索引，其時間復(fù)雜度為O（N/r）；在支持度計算階段，SupII 算法的時間復(fù)雜度為O（k×N/r）；在候選模式生成階段，模式連接策略的時間復(fù)雜度為O（L×logaL）。因此，OWP 算法的時間復(fù)雜度為O（N/r+k×N/r+L×logaL）=O（k×N/r+L×logaL）。

3.5.2 空間復(fù)雜度

OWP 算法的空間復(fù)雜度為O（k×N/r+L），其中，k、r、N和L分別為模式最大長度、1 長度模式的數(shù)量、序列總長度和候選模式數(shù)量。

OWP 算法的空間復(fù)雜度由準備階段創(chuàng)建的倒排索引、支持度計算時占用的內(nèi)存空間和生成的候選模式3 個部分組成。其中，準備階段創(chuàng)建的倒排索引的空間復(fù)雜度為O（N/r）；在支持度計算階段，SupII 算法的空間復(fù)雜度為O（k×N/r）；在候選模式生成階段的空間復(fù)雜度為O（L）。因此，OWP 算法的空間復(fù)雜度為O（N/r+k×N/r+L）=O（k×N/r+L）。

4 實驗分析

4.1 實驗數(shù)據(jù)集

本文采用6 個真實數(shù)據(jù)集來驗證OWP 算法的運行效率，其中，D1 是項集序列數(shù)據(jù)集，D2、D3 是序列數(shù)據(jù)集，D4、D5 和D6 是氨基酸數(shù)據(jù)集，都是單項序列數(shù)據(jù)集。

實驗運行環(huán)境：操作系統(tǒng)為64 位Windows 10，處理器為Inter?CoreTMi5-9300U，主頻為2.20 GHz，內(nèi)存為8 GB，開發(fā)語言為Python，開發(fā)環(huán)境為PyCharm。

表2 所示為所選用數(shù)據(jù)集。

表2 實驗數(shù)據(jù)集Table 2 Experimental datasets 單位：個

4.2 對比算法

本文主要采用以下對比算法：

1）OWP-p：為驗證準備階段剪枝策略的有效性，本文設(shè)計了OWP-p 算法，與OWP 算法相比，該算法沒有使用此剪枝策略。

2）Ows-OWP：為了驗證SupII 算法在計算支持度方面的優(yōu)越性，采用Ows-OWP 算法作為對比，該算法采用文獻［27］提出的one-way scan 算法計算模式的支持度。

3）OWP-e：為了驗證模式連接策略的有效性，使用OWP-e 算法作為對比算法，該算法在候選模式生成時采用以廣度優(yōu)先為基礎(chǔ)的枚舉法。

4.3 挖掘效果

本文采 用3 個對比算法OWP-p、Ows-OWP 和OWP-e 在D1～D6 這6 個數(shù)據(jù)集上進行實驗，設(shè)置不同數(shù)據(jù)集上的minsup 分別為450、500、600、35、24 和20。其中，D1～D3 為項集序列數(shù)據(jù)集，隨機設(shè)置其10%的項為弱項，D4～D6 為氨基酸序列，設(shè)置非必要氨基酸為弱項，即弱項集合為ω=｛A，D，E，U，O，X｝。圖2、圖3 和表3 分別為運行時間、內(nèi)存消耗以及候選模式數(shù)量的對比結(jié)果。

圖2 D1～D6 運行時間對比Fig.2 Comparison of D1～D6 running time

圖3 D1～D6 內(nèi)存消耗對比Fig.3 Comparison of D1～ D6 memory consumption

表3 生成的候選模式數(shù)量Table 3 The number of candidate patterns generated 單位：個

根據(jù)上述實驗結(jié)果，可以得出如下結(jié)論：

1）剪枝策略可以有效提高算法效率。OWP 的效率優(yōu)于OWP-p。以D1 為例，觀察圖2、圖3 和表3可知，OWP 和OWP-p 的運行時間分別是9.20 s 和24.41 s，內(nèi)存消耗分別是28.53 MB 和29.76 MB，生成的候選模式數(shù)量分別為570 個和2 051 個。運行時間增長了24.41/9.20=2.653 倍，內(nèi)存消耗減少了3.51%。類似情況出現(xiàn)在每個數(shù)據(jù)集上，主要原因是：對非頻繁強項和所有弱項進行剪枝，即縮減了FP1的大小，在生成2 長度的候選模式時，可以大大地減少在I-Join 和S-Join 過程中產(chǎn)生的冗余模式，同時減少了計算冗余候選模式支持度而造成的時間和空間的浪費。因此，剪枝策略可以有效提高算法的運行效率。

2）無論在項集序列數(shù)據(jù)集上還是在單項序列數(shù)據(jù)集上，OWP 的表現(xiàn)優(yōu)于Ows-OWP。在運行時間方面，OWP 的運行時間少于Ows-OWP。以D1 為例，由表3 可知，在OWP 和Ows-OWP 都生成570 個候選模式的情況下，通過圖2 可以看出它們的運行時間分別為9.20 s 和12.40 s。類似的情況也出現(xiàn)在其他數(shù)據(jù)集上，出現(xiàn)這種情況的主要原因是：SupII算法采用倒排索引結(jié)構(gòu)，利用項目出現(xiàn)的位置索引計算模式支持度，避免了重復(fù)掃描數(shù)據(jù)庫造成的時間浪費，因此運行時間大大縮短。在內(nèi)存消耗方面，觀察圖3 可知，除了在D2 中，OWP 比Ows-OWP 的內(nèi)存消耗高，分別是25.73 MB 和24.96 MB，在其他數(shù)據(jù)集中OWP 算法的內(nèi)存消耗都低于Ows-OWP 算法，造成這種情況的原因是：由于SupII 算法需要提前申請額外空間來構(gòu)建倒排索引，這產(chǎn)生了一定的內(nèi)存消耗。當數(shù)據(jù)集的項數(shù)較多時，如D2 有277 個，這就使得OWP 占用的空間略微增加。根據(jù)表2 可知，其他數(shù)據(jù)集的項目數(shù)較少，所以O(shè)WP 用于創(chuàng)建倒排索引產(chǎn)生的空間消耗較低。因此，在內(nèi)存消耗方面，OWP 算法在項數(shù)較多的數(shù)據(jù)集上內(nèi)存消耗略高，在項數(shù)較少的數(shù)據(jù)集上內(nèi)存消耗略低。根據(jù)圖2、圖3 可知，以D1 為例，OWP 比Ows-OWP的運行時間增長了12.40/9.20=1.348 倍，內(nèi)存消耗減少了0.07%。綜上所述，OWP 算法優(yōu)于Ows-OWP算法。

3）模式連接策略可以有效減少候選模式的數(shù)量。無論在項集序列數(shù)據(jù)集上還是在單項序列數(shù)據(jù)集上，OWP-e 的運行時間、內(nèi)存消耗和候選模式的生成數(shù)量均大于OWP。以D1 為例，由圖2、圖3 和表3可知，OWP 和OWP-e 的運行時間分別是9.20 s 和33.05 s，內(nèi)存消耗分別是28.53 MB 和30.02 MB，生成的候選模式數(shù)量分別是570 個和2 764 個，運行時間增長了33.05/9.20=3.592 倍，內(nèi)存消耗減少了5%。這種情況也普遍出現(xiàn)在其他數(shù)據(jù)集上，出現(xiàn)這一情況的原因如下：OWP 采用模式連接策略，可以減少冗余候選模式的生成數(shù)量，也減少了用于計算它們支持度的時間和內(nèi)存消耗。因此，OWP 算法優(yōu)于OWP-e 算法。

綜上所述，OWP 算法可以比其他對比算法更高效地挖掘一次性弱間隙強模式。

4.4 可擴展性

為了驗證OWP 算法的可擴展性，分別選取3 個對比算 法OWP-p、Ows-OWP 和OWP-e，在 以D1 為基礎(chǔ)的數(shù)據(jù)集D1_1、D1_2、D1_3、D1_4、D1_5、D1_6上進行實驗。這些數(shù)據(jù)集分別是D1 大小的1～6 倍。設(shè)置不同數(shù)據(jù)集上的minsup 分別為450、900、1 350、1 800、2 250 和2 700。圖4、圖5 分別為挖掘結(jié)果的運行時間和內(nèi)存消耗對比。

圖4 不同大小數(shù)據(jù)集上的運行時間對比Fig.4 Comparison of running time on different size datasets

圖5 在不同大小數(shù)據(jù)集上的內(nèi)存消耗對比Fig.5 Comparison of memory consumption on different sizes datasets

觀察圖4 和圖5 可以得出以下結(jié)論：

OWP 算法在運行時間和內(nèi)存消耗方面都隨著數(shù)據(jù)集的增大呈線性增加。比如，OWP 算法在D1_1上的運行時間為9.20 s，內(nèi)存消耗為28.73 MB，在D1_6 上運行時間為34.62 s，內(nèi)存消耗為66.39 MB，即運行時間增長了34.62/9.20=3.763 倍，內(nèi)存消耗增加了66.39/28.73=2.310 倍。由此可見，OWP 的運行時間和內(nèi)存消耗增長的倍數(shù)遠低于數(shù)據(jù)集大小增長的倍數(shù)，證明OWP 具有良好的可擴展性。此外，OWP-p 的運行時間增長了130.26/24.41=5.336 倍，內(nèi)存消耗 增加了67.20/29.76=2.258 倍；Ows-OWP 的 運行時間增長了51.54/12.40=4.156 倍，內(nèi)存消耗增加了62.62/28.87=2.169 倍；OWP-e 的運行時間增長了163.87/33.05=4.958 倍，內(nèi)存消耗增加了66.39/30.02=2.212 倍。分析可知，在運行時間上，其他3 種對比算法增加的倍數(shù)要高于OWP，但是在內(nèi)存消耗上其他3 種對比算法的表現(xiàn)要略微優(yōu)于OWP。出現(xiàn)這種情況的原因是：OWP 采用的剪枝策略、SupII 算法和模式連接策略有效提高了算法的運行效率，但同時OWP 由于采用SupII 算法計算支持度，當數(shù)據(jù)集變大時，創(chuàng)建倒排索引所占據(jù)的空間也會變大，因此比Ows-OWP 消耗了更多內(nèi)存空間。然而，OWP-p 和OWP-e 生成的冗余候選模式雖然會造成一定的內(nèi)存占用，但是由于數(shù)據(jù)集項數(shù)較少且不隨著數(shù)據(jù)集變大而增加，因此它們內(nèi)存消耗增加的倍數(shù)要略微低于OWP。

綜上所述，OWP 的挖掘性能不會隨著數(shù)據(jù)集的增大而降低，因此，OWP 在大數(shù)據(jù)集上也可以高效地挖掘出用戶感興趣的模式。

5 結(jié)束語

本文提出在更具通用性的項集序列數(shù)據(jù)集上挖掘一次性弱間隙強模式的OWP 算法。在準備階段，通過掃描數(shù)據(jù)庫對序列中的各項創(chuàng)建對應(yīng)的倒排索引，并采用剪枝策略剪枝弱項和非頻繁強項，精簡1長度的頻繁模式集合。在支持度計算方面，采用倒排索引結(jié)構(gòu)，根據(jù)模式出現(xiàn)位置索引計算候選模式支持度，避免重復(fù)掃描數(shù)據(jù)庫帶來的時間消耗，從而大幅提高了運行效率。在候選模式生成方面，采用基于Apriori 屬性的模式連接策略，有效減少候選模式的生成數(shù)量。在真實數(shù)據(jù)集上的實驗結(jié)果驗證了OWP 算法的高效性與可擴展性。下一步將對如何解決弱間隙約束條件重復(fù)判斷的問題進行研究，以達到在序列、模式增長或者出現(xiàn)次數(shù)增加時，可以高效計算模式支持度。