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

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

0 引言

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

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

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

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

1 相關(guān)工作

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

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

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

2 相關(guān)定義

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

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

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

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

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

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

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

例2給定序列s1=（bc）（bef）（abce）（abd）（abd）（cf）（adf）和一個(gè)弱間隙強(qiáng)模式p=（b）*（b）*（ad）。如果忽略弱間隙約束，那么因?yàn)閜1=（b）?s1=（bc），p2=（b）?s2=（bef），p3=（ad）?s4=（abd），則<1，2，4>是模式p在s1上的一個(gè)出現(xiàn)。然而，當(dāng)τ=｛a，b，d，e｝，ω=｛c，f｝時(shí)，<1，2，4>就不是一個(gè)出現(xiàn)，因?yàn)閟3=（abce）中存在強(qiáng)項(xiàng)，所以<1，2，4>不滿足弱間隙約束。顯然，<2，3，4>、<3，4，5>和<4，5，7>是模式p滿足弱間隙約束的全部出現(xiàn)。其中，<2，3，4>和<3，4，5>不滿足一次性條件，因?yàn)閜1∩p2=b≠?并且索引3 在兩次出現(xiàn)中被重復(fù)使用，即項(xiàng)集（abce）中的項(xiàng)'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）中的項(xiàng)'d'，而在出現(xiàn)<4，5，7>中，使用的是s4=（abd）中的項(xiàng)'b'，因此它們是滿足一次性條件的兩個(gè)出現(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ù)庫(kù)D中的支持度為

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

例3在例2 中，若給定minsup 為3，則模式p=（b）*（b）*（ad）是一個(gè)頻繁的一次性弱間隙強(qiáng)模式，因?yàn)槠湓诒? 所示的項(xiàng)集序列數(shù)據(jù)庫(kù)中的支持度sup（p，D）=3≥minsup。

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

3 算法描述

3.1 準(zhǔn)備階段

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

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

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

例4給定序列s1=s1s2s3s4s5s6s7=（bc）（bef）（abce）（abd）（abd）（cf）（adf）。以 項(xiàng)'a'為 例，不難發(fā) 現(xiàn)'a'出現(xiàn)在序列中的第3 個(gè)項(xiàng)集、第4 個(gè)項(xiàng)集、第5 個(gè)項(xiàng)集以及第7 個(gè)項(xiàng)集中，因此，項(xiàng)'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依次計(jì)算每個(gè)強(qiáng)項(xiàng)的支持度，如果該項(xiàng)的支持度小于minsup，則對(duì)其進(jìn)行剪枝。此外，剪枝所有弱項(xiàng)，因?yàn)槿蹰g隙約束規(guī)定弱項(xiàng)只允許出現(xiàn)在間隙中，而不可以構(gòu)成模式。

例5在例4 中，假設(shè)在s1中挖掘1 長(zhǎng)度的頻繁模式，若minsup 為3，τ=｛a，b，d，e｝，ω=｛c，f｝，則強(qiáng)項(xiàng)'e'被剪枝，因?yàn)樗闹С侄葹?。盡管項(xiàng)'c'和'f'的支持度都為3，但它們依然要被剪枝，因?yàn)樗鼈兪侨蹴?xiàng)。

3.2 支持度計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法1SupII 算法

3.3 候選模式生成

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

定義9（前綴和后綴模式，子模式和超模式）如果一個(gè)長(zhǎng)度為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 個(gè)長(zhǎng)度為m的弱間隙強(qiáng)模式q和r，其中，模式r表示為r=e1，e2，…，em-1，em。如果suffer（q）=prefix（r），根據(jù)em-1，em可 分為以下2 種情況：

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

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

例7給定3 個(gè)4 長(zhǎng)度的弱間隙強(qiáng)模式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 個(gè)長(zhǎng)度為m的頻繁模式通過I-Join 和S-Join 生成長(zhǎng)度為m+1 的候選模式，這個(gè)方法被稱為模式連接。需要注意的是，在使用I-Join 方法時(shí)，同一項(xiàng)集內(nèi)的項(xiàng)要按字典順序排序。

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

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

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

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

算法2PatternJoin 算法

3.4 OWP 算法

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

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

步驟2計(jì)算各項(xiàng)的支持度，剪枝不頻繁的強(qiáng)項(xiàng)并將頻繁的強(qiáng)項(xiàng)存入FP1與FPItem。

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

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

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

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

算法3OWP 算法

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

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

3.5.1 時(shí)間復(fù)雜度

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

OWP 算法的時(shí)間復(fù)雜度主要由準(zhǔn)備階段、支持度計(jì)算和候選模式生成3 個(gè)部分構(gòu)成。在準(zhǔn)備階段，創(chuàng)建倒排索引，其時(shí)間復(fù)雜度為O（N/r）；在支持度計(jì)算階段，SupII 算法的時(shí)間復(fù)雜度為O（k×N/r）；在候選模式生成階段，模式連接策略的時(shí)間復(fù)雜度為O（L×logaL）。因此，OWP 算法的時(shí)間復(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分別為模式最大長(zhǎng)度、1 長(zhǎng)度模式的數(shù)量、序列總長(zhǎng)度和候選模式數(shù)量。

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

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

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

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

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

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

表2 實(shí)驗(yàn)數(shù)據(jù)集Table 2 Experimental datasets 單位：個(gè)

4.2 對(duì)比算法

本文主要采用以下對(duì)比算法：

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

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

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

4.3 挖掘效果

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

圖2 D1～D6 運(yùn)行時(shí)間對(duì)比Fig.2 Comparison of D1～D6 running time

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

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

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

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

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

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

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

4.4 可擴(kuò)展性

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

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

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

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

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

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

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

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