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

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

0 引言

序列模式挖掘（Sequential Pattern Mining，SPM）作為數(shù)據(jù)挖掘領(lǐng)域中重要課題，旨在從序列數(shù)據(jù)庫［1］發(fā)現(xiàn)支持度（在序列數(shù)據(jù)庫中出現(xiàn)次數(shù)）滿足用戶最小支持度閾值的子序列，被廣泛應(yīng)用于多種實際場景，如DNA 序列檢測［2］、用戶購買行為分析［3］和網(wǎng)頁點擊流挖掘［4-5］等。

傳統(tǒng)頻繁序列模式挖掘只考慮模式是否在序列中出現(xiàn)，而忽略了它在序列的出現(xiàn)次數(shù)。為解決此問題，重復(fù)挖掘方法［6-12］應(yīng)運而生，該方法通過模式匹配技術(shù)計算模式在一條序列的出現(xiàn)次數(shù)。例如：假定有兩個消費者，他們的購買次序分別形成了兩條消費序列S1={(1，ab)（2，a）（3，abc）｝和S2={(1，bd)(2，ab)(3，acd)(4，abc)(5，ac)(6，ac)（7，ab）（8，ad）（9，cd）｝。以S1為例，它表示消費者1，第1 次購買了a 和b 兩樣商品；第2 次僅購買了a 商品；第3 次購買了a、b 和c 共三樣商品。易知模式（ab）（c）在S1和S2中均有出現(xiàn)。由于傳統(tǒng)的序列模式挖掘方法不甄別模式在序列中的重復(fù)性，因此模式（ab）（c）在S1和S2中的支持度為2。而可重復(fù)序列模式挖掘則甄別模式在序列中的重復(fù)性，易知模式（ab）（c）在S2中的出現(xiàn)了3 次，出現(xiàn)位置為因此在可重復(fù)序列模式挖掘中，模式（ab）（c）在S1和S2中的支持度分別為1 和3，總支持度為4。由此可見，消費者2 比消費者1 在模式（ab）（c）上具有更大的興趣。因此，可重復(fù)序列模式挖掘與傳統(tǒng)序列模式挖掘方法顯著不同。

此外，與一次性條件［12］不同，文獻［12］在單項序列上進行挖掘，即序列是由若干單項構(gòu)成的，此研究的對應(yīng)S1序列是｛abaabc｝；而本文在通用性更強的項集序列上進行研究，問題更通用、更復(fù)雜。

更重要的，目前大部分重復(fù)挖掘算法都是基于模式的出現(xiàn)頻率判斷模式的重要程度，忽略了項本身的重要程度。實際上，生活中的序列通常包含大量的輔助信息，例如銷售序列中商品的購買數(shù)與利潤。如果忽略項目的價值將會導(dǎo)致一些出現(xiàn)頻繁但用戶不感興趣的模式被發(fā)現(xiàn)。如商場商品中，面包的銷量高于鉆石，但鉆石帶給商家的利潤遠(yuǎn)高于面包，因此，只依據(jù)出現(xiàn)頻率判斷模式的重要程度并不合理。為解決此問題，研究者們提出高效用序列模式挖掘，為序列中的項賦予權(quán)重［13-16］（又稱效用）用來表示各項的重要程度。除此之外，由于模式的效用由模式中各項效用累加得出，隨著模式長度的增加而增加，導(dǎo)致較長的模式更容易成為高效用序列模式。為此，高平均效用序列模式挖掘［17］被提出，綜合考慮模式的出現(xiàn)頻率、各項的效用和模式長度，用于發(fā)現(xiàn)更符合用戶需求的模式。如Wu 等［18］提出的HAOP-Miner（self-adaptive High-Average utility One-off sequential Pattern Miner）算法主要解決一次性條件下自適應(yīng)高平均效用序列模式挖掘問題。HAOP-Miner 使用了用于計算模式支持度的Rf 算法，該算法采用逆序填充隊列減少冗余節(jié)點。雖然該算法可以用于高平均效用序列模式挖掘，但它的挖掘?qū)ο鬄閱雾椥蛄袛?shù)據(jù)庫，無法處理項集序列數(shù)據(jù)問題，并且它在先驗知識不足的情況下很難給出恰當(dāng)?shù)钠骄в瞄撝怠?/p>

上述高平均效用序列模式挖掘需要用戶提供最小平均效用閾值，然而在缺乏先驗知識的前提下，很難選擇合適的閾值。為此，top-k挖掘方法可在先驗性不足的情況下得到用戶所需數(shù)量的模式［19-21］。如Le 等［22］提出了top-k挖掘方式，用戶只需提前給出想要挖掘的模式數(shù)，通過采用閾值攀升的方式挖掘用戶最關(guān)注的k個模式；然而該算法僅根據(jù)支持度判斷模式重要性存在不足。Zhang 等［20］提出了TKUS 算法，該算法采用投影和局部搜索機制，并采用了序列效用攀升、提前終止和消除冗余模式的策略，大幅減小了搜索空間；但該算法基于定量數(shù)據(jù)庫挖掘top-k高效用模式，未考慮模式長度等因素，并只考慮了模式是否在序列中出現(xiàn)，沒有計算在一條序列中的重復(fù)出現(xiàn)次數(shù)，導(dǎo)致一些重要的模式被忽略。綜上所述，本文提出TOUP（Top-kOne-off high average Utility sequential Pattern mining）算法高效地挖掘一次性條件下用戶最感興趣的前k個高平均效用模式，可以根據(jù)閾值攀升的方式動態(tài)改變候選集和結(jié)果集，以達到最終挖掘出用戶最關(guān)注的k個高平均效用模式的目標(biāo)。

本文的主要工作如下：1）在支持度計算方面，提出基于各項出現(xiàn)位置與項重復(fù)關(guān)系數(shù)組的CSP（Calculation Support of Pattern）算法，以降低時間空間復(fù)雜度；2）在候選模式生成方面，提出基于最大平均效用上界的剪枝策略，以減少候選模式數(shù)；3）在多個真實數(shù)據(jù)集和合成數(shù)據(jù)集上驗證了TOUP算法的有效性。

1 相關(guān)工作

SPM 自被提出以來，廣泛應(yīng)用于諸多領(lǐng)域［23-26］，面對不同的挖掘需求，多種形式的SPM 被提出，如閉合模式挖掘［3］、最大模式挖掘［25］和負(fù)序列模式挖掘［26］等。傳統(tǒng)SPM 只考慮序列中是否存在該模式，而不考慮它在序列中重復(fù)出現(xiàn)，但模式在少數(shù)序列中多次出現(xiàn)的信息同樣重要。為解決此問題，文獻［6-8，11］根據(jù)模式在序列中的重復(fù)使用情況，研究了無約束、無重疊和一次性條件下重復(fù)序列模式挖掘問題。

然而，僅考慮模式的出現(xiàn)頻率無法滿足現(xiàn)實需求，例如用戶購買行為分析中，有些商品盡管銷量很高，但帶給商家的利潤較低；而有些商品雖然銷量很低，但所帶來的利潤很高。因此，需要采用效用［27-28］進行計算，高平均效用序列模式挖掘［29］通過綜合考慮模式的支持度、效用和長度，挖掘數(shù)據(jù)集中平均效用值不小于最小平均效用閾值的模式。Segura-Delgado 等［17］提出了一種進化算法，用于從受平均效用和可解釋性影響很好的縱向人類基因表達數(shù)據(jù)中挖掘生物相關(guān)的高平均效用序列規(guī)則；然而，模式的平均效用并不滿足反單調(diào)性，給候選模式生成與剪枝問題帶來很大的困難，為此，學(xué)者們提出了多種滿足反單調(diào)性的上界，利用反單調(diào)性對候選模式進行剪枝，以提高算法效率。Kim 等［30］提出了最大平均效用上界和最大剩余平均效用上界，由此提出了基于列表的新數(shù)據(jù)結(jié)構(gòu)，并由該數(shù)據(jù)結(jié)構(gòu)提出了兩個剪枝策略。然而，上述挖掘方法沒有考慮模式在序列中的重復(fù)性問題，為此，Wu 等［18］在單項序列上研究了可重復(fù)高平均效用序列模式挖掘問題，在支持度計算方面通過逆序填充算法高效地獲得模式在各條序列中的出現(xiàn)次數(shù)，在候選模式生成方面提出了支持度下界概念，并在此基礎(chǔ)上使用模式連接策略減少候選模式數(shù)。

上述研究均在用戶提供最小效用閾值的情況下進行挖掘，然而在沒有足夠的先驗知識前提下，無法設(shè)計合理的閾值，將會導(dǎo)致過多或過少的模式被發(fā)現(xiàn)。鑒于此問題，top-k挖掘方式被提出，用于挖掘用戶最感興趣的k個模式。Le等［22］提出了top-k挖掘方式，用戶只需提前給出想要挖掘模式數(shù)，通過采用閾值攀升的方式掃描候選集和結(jié)果集，使得最終只挖掘出用戶最關(guān)注的k個模式。但該算法僅能在不確定數(shù)據(jù)庫中挖掘頻繁序列模式，無法解決項集序列數(shù)據(jù)庫中挖掘高平均效用模式問題，且忽略了模式在序列中的重復(fù)出現(xiàn)。

綜上所述，本文提出一次性條件下top-k高平均效用序列模式挖掘算法，與先前研究相比存在如下差異：

1）挖掘模式類型不同。與頻繁序列模式挖掘不同，在考慮模式出現(xiàn)頻率的基礎(chǔ)上綜合考慮各項效用與模式長度，挖掘用戶更感興趣的高平均效用模式。

2）支持度計算方式不同。與傳統(tǒng)的只考慮模式是否出現(xiàn)的判別方式不同，使用模式匹配技術(shù)計算模式在序列中的具體出現(xiàn)次數(shù)，更好地表達用戶的興趣程度。

3）候選模式剪枝策略不同。提出滿足反單調(diào)性的平均效用上界，在此基礎(chǔ)上構(gòu)建高效的候選模式生成策略與剪枝策略。

4）結(jié)果集選擇方式不同。與預(yù)先設(shè)定最小閾值方式不同，采用top-k挖掘方法，在先驗性不足的情況下，挖掘用戶最感興趣的k個高平均效用模式。

2 問題定義

序列數(shù)據(jù)庫D由k條序列組成，記作D={S1，S2，…，Sk}。序列由n個項集組成，每個項集包含若干有序項，記作S=s1s2…sn，si?Σ（1 ≤i≤n），Σ表示數(shù)據(jù)庫D的項目集［31］。如表1 所示，序列數(shù)據(jù)庫D由2 條序列組成，項目集Σ={a，b，c，d}，其中序列S1中第一個項集S1=(1，ab)。

表1 序列數(shù)據(jù)庫DTab.1 Sequence database D

定義1模式［8］。大小為m的模式記作P=p1*p2*…*pm（或簡寫為P=p1p2…pm），其中*表示傳統(tǒng)通配符，意味著任意數(shù)量的項集都可以在這里出現(xiàn)。模式P的長度為模式中所有項的數(shù)量，記作len（P）。給定模式P=（ab）（a）（c），模式長度len（P）=4。

定義2出現(xiàn)和一次性出現(xiàn)。給定m個整數(shù)L=當(dāng)且僅當(dāng)1 ≤l1

定義3支持度。模式P在序列S中一次性出現(xiàn)數(shù)為P在S中的支持度，記作sup(P，S)。模式P在包含k條序列的序列數(shù)據(jù)庫D中的支持度記作

例1 給定如表1 所示序列數(shù)據(jù)庫D和模式P=(ab)(a)(c)。因 為p1=(ab) ?s1=(ab)，p2=(a) ?s2=(a) 和p3=(c) ?s3=(abc)，所以模式P在序列S1的一個出現(xiàn)，為同樣P在S1中有很多出現(xiàn)，如和雖然兩個出現(xiàn)中同時使用了位置3 但是在第一個出現(xiàn)中p3使用了s3中的項“c”，第二個出現(xiàn)中p1使用了s3中的項“a”和項“b”，并沒有重復(fù)使用序列中相同的項。因此滿足一次性條件，模式P在S1中有兩個一次性出現(xiàn)。同理可求得P在S2中有兩個一次性出現(xiàn)。所以P在序列數(shù)據(jù)庫D中的支持度為

定義4效用與平均效用。

在帶有效用的序列數(shù)據(jù)庫中項目i的效用值記作u（i），模式P的效用為模式中所有項的效用之和與模式支持度的乘積，記為：

模式在序列數(shù)庫中的平均效用為模式在數(shù)據(jù)庫中的效用與模式長度的比值，記為：

其中：pk為模式P中的項集，ij為項集pk中的項。

例2 給定序列數(shù)據(jù)庫D中各項的效用如表2 所示，項“a”和“b”的效用分別為10 和5。在例1 中，模式P的長度len(P)=4 和支持度sup(P，D)=4，所 以U(P，D)==4 ×((10+5)+8+10)=132，AU(P，D)=U(P，D)/len(P)=132/4=33。

表2 效用表Tab.2 Utility table

定義5top-k高平均效用模式。序列數(shù)據(jù)庫中平均效用值最高的k個模式被稱為top-k高平均效用模式。

問題陳述 預(yù)先給定序列數(shù)據(jù)庫D，效用表T和用戶定義的參數(shù)k，TOUP 的目標(biāo)是找出top-k高平均效用模式。

3 算法描述

為了挖掘top-k高平均效用模式，本文提出TOUP 算法，該算法包括平均效用計算和候選模式生成兩部分。3.1 節(jié)介紹了模式平均效用計算的方法，首先統(tǒng)計模式P中各項在序列中的位置信息，然后直接通過項的出現(xiàn)位置和模式P中各項的重復(fù)關(guān)系計算出模式支持度，避免了對序列數(shù)據(jù)庫的重復(fù)掃描，提高了計算效率。3.2 節(jié)介紹了候選模式生成策略，鑒于模式的平均效用不滿足反單調(diào)性的情況，提出了最大平均效用上界，并基于Apriori-like 性質(zhì)提出剪枝策略，有效減少了候選模式數(shù)。3.3 節(jié)中提出TOUP 算法，在挖掘過程中動態(tài)更新結(jié)果集與閾值，高效地發(fā)現(xiàn)用戶最感興趣的k個高平均效用模式。

3.1 平均效用計算

根據(jù)式（2）可知，模式的平均效用計算的關(guān)鍵問題是支持度的計算。傳統(tǒng)的支持度計算方法不考慮模式的重復(fù)出現(xiàn)次數(shù)，例如Srivastava 等［16］使用列表結(jié)構(gòu)記錄數(shù)據(jù)庫中的模式發(fā)生情況和效用，但是列表結(jié)構(gòu)只記錄模式是否發(fā)生，很難處理重復(fù)挖掘問題。OWSP-Miner（self-adaptive One-off Weak-gap Strong Pattern mining）算 法［12］和HAOP-Miner 算法［18］雖然可以處理重復(fù)挖掘問題，但兩者都是基于單項序列數(shù)據(jù)庫的挖掘算法，無法直接計算項集序列模式的支持度。為了解決面向項集序列數(shù)據(jù)的重復(fù)挖掘問題，高效計算模式支持度，本節(jié)提出基于各項出現(xiàn)位置與項重復(fù)關(guān)系數(shù)組的CSP 算法快速計算模式支持度。CSP 算法通過以下4 個步驟實現(xiàn)每條序列中的支持度計算。

步驟1 創(chuàng)建m層節(jié)點，其中m是模式P的大小。第j層是位置數(shù)組Aj，存儲了pj的位置信息。若pj只有一項，Aj存儲該項的出現(xiàn)位置；否則Aj存儲該項集內(nèi)所有項的位置交集。

例3 給定模式P=（ab）*（a）*（c），通過遍歷序列數(shù)據(jù)庫可知，項“a”“b”和“c”在序列S1中的位置信息分別為：［1，2，3，4，5］，［1，3，4］和［3，6］。由p1包含項“a”和項“b”，位置交集為［1，3，4］，所以A1=［1，3，4］。同理，位置數(shù)組A2和A3分別為［1，2，3，4，5］和［3，6］。

步驟2 為了處理一次性條件，初始化模式中項重復(fù)關(guān)系數(shù)組R。

定義6項重復(fù)關(guān)系數(shù)組。大小為m的模式P的項重復(fù)關(guān)系數(shù)組中包含m個集合，第j個集合存儲了模式P中與pj擁有相同項的項集所在位置。

例4 給定模式P=（ab）（a）（c），可知p1=（ab），p2=（a），則p1和p2擁有相同項，所以模式P的項重復(fù)關(guān)系數(shù)組R中第1個項集中存儲了p2的位置號2，第2 個項集中存儲了p1的位置號1，由于沒有其他重復(fù)使用項，所以模式P的項重復(fù)關(guān)系數(shù)組R（P）=［［2］［1］［］］。

步驟3 在尋找一次性出現(xiàn)時，需根據(jù)項重復(fù)關(guān)系數(shù)組R判斷該位置是否被使用。尋找第j層一次性出現(xiàn)位置時，判斷該位置是否存在于R［j］。數(shù)組A1中查找未被使用的項作為當(dāng)前節(jié)點e。然后重復(fù)以下操作：在下一層節(jié)點中查找未被使用的子節(jié)點c，使得c>e，直到尋找到第m層未被使用的子節(jié)點，至此該路徑記作：L。

例5 根據(jù)數(shù)組R可知，第一層的第一個元素為1，由于該元素是第一層第一個元素，所以該元素一定滿足一次性。尋找第二個項集的一次性出現(xiàn)位置，首先判斷第二層第一個元素1，由于元素1 不大于第一層節(jié)點1，且根據(jù)數(shù)組R［2］=［1］，第一層中的一次性出現(xiàn)位置為［1］，即第二層第一個元素1 不滿足一次性，刪去第二層元素1。判斷第二層第二個元素2，首先2>1，其次判斷位置一次性，由于R［2］=［1］，判斷第一層中的一次性出現(xiàn)位置為［1］，可知位置2 不在其中，所以位置2 滿足一次性條件，所以節(jié)點1 在第二層的子節(jié)點為節(jié)點2。同理可知節(jié)點3 是節(jié)點2 在第三層的子節(jié)點。步驟3 結(jié)束，得到出現(xiàn)

步驟4 返回第一層繼續(xù)重復(fù)步驟3，直到?jīng)]有新的出現(xiàn)生成。

例6 繼續(xù)掃描第一層中的元素，第二個元素是3，由數(shù)組R（P）=［［2］［1］［］］可知，p1和p2擁有重復(fù)元素“a”，在第一個出現(xiàn)中p2只使用了位置2，所以第一層第二個元素3 滿足一次性條件。由步驟3 的第二層和第三層的一次性出現(xiàn)位置分別為4 和6。由于沒有其他出現(xiàn)生成，步驟4 結(jié)束。CSP 算法的偽代碼如下：

算法1 CSP 算法。

定理1CSP 算法的時間復(fù)雜度和空間復(fù)雜度分別為：O(nml)和O(ml)，其中n、m和l分別代表數(shù)據(jù)庫大小、序列大小和模式大小。

證明 CSP 算法在計算支持度時，首先掃描數(shù)據(jù)庫中的各條序列，然后掃描序列以獲得各項集的位置數(shù)組，根據(jù)位置數(shù)組計算模式的一次性條件出現(xiàn)頻率。因此，CSP 算法的時間復(fù)雜度為O（nml）。CSP 算法主要內(nèi)存消耗為模式的位置數(shù)組，最壞情況下，位置數(shù)組可當(dāng)作一個m×l的多維數(shù)組，因此，CSP 算法的空間復(fù)雜度為O（ml）。

3.2 候選模式生成

本節(jié)介紹了生成候選模式的模式擴展方法，為了減少候選模式數(shù)，提高算法的挖掘效率，提出滿足反單調(diào)性的最大平均效用上界，并基于該上界提出剪枝策略對候選模式剪枝。

由于項集序列模式由若干項集構(gòu)成，項集中包含一個或多個有序的項，因此，在生成項集序列候選模式時本文采用項集擴展（I-extension）和序列擴展（S-extension）的方法［32］。

項集擴展 在模式的最后一個項集內(nèi)有序擴展新項。

序列擴展 在模式末尾添加一個新項集。

例7 給定模式P=（ab）*（a）*（c），項目集Σ={a，b，c，d}。根據(jù)項集擴展，模式P只能生成模式（ab）*a*（cd），這是因為項集中都是有序的項；根據(jù)序列擴展模式P可以生成模式（ab）*a*c*a、（ab）*a*c*b、（ab）*a*c*c 和（ab）*a*c*d。

雖然項集擴展和序列擴展不會丟失有效的候選模式，但是，模式的平均效用并不滿足反單調(diào)性，如例8 所述。

例8 在例1 中已計算出模式P=（ab）*（a）*（c）在序列數(shù)據(jù)庫中的支持度為4，即sup（P，D）=4。模式P'=（ab）*（c）是P的子模式，根據(jù)CSP 算法可得sup(P'，D)=4。根據(jù)式（2），可知AU(P，D)=132/4=33 和AU(P'，D)=92/3=30.7。盡管模式P'是模式P的子模式，但AU(P'，D)

例8 說明了模式的平均效用不滿足反單調(diào)性，無法直接使用Apriori 性質(zhì)對候選模式剪枝，導(dǎo)致基于枚舉樹的候選模式生成方法生成指數(shù)級候選模式。因此，本文提出滿足反單調(diào)性的最大平均效用上界，并基于該上界提出剪枝策略對候選模式剪枝。

定義7最大平均效用上界。

模式P在D的最大平均效用上界是它的支持度和項目集最大效用乘積，記為：

其中umax是項目集各項最大效用值。

例9 在例1 中模式P=（ab）*（a）*（c）在序列數(shù)據(jù)庫D中支持度為4。根據(jù)表2 可知umax=u(a)=10，因 此maub(P，D)=4 × 10=40。

定理2最大平均效用上界模式滿足反單調(diào)性。

證明 假設(shè)模式P'是模式P的子模式，L是序列S中模式P的出現(xiàn)。若序列S中模式P'的對應(yīng)出現(xiàn)為L'，則出現(xiàn)L'是L的子出現(xiàn)。因此，對于序列S中模式P'的每一個出現(xiàn)L'，都可以得到對應(yīng)的子出現(xiàn)L，表明序列S中模式P'的支持度不小于它的超模式支持度，即sup(P，S) ≤sup(P'，S)。由于umax是常數(shù)，maub(P，D)=sup(P，D) ×umax不大于maub(P'，D)=sup(P'，D) ×umax，因此，最大平均效用上界滿足反單調(diào)性。

定理3如果模式P的最大平均效用上界不大于最小平均效用閾值，即maub(P，D) ≤minau，則模式P的平均效用也不大于minau，即AU(P，D) ≤minau。

證明 因為umax是所有項的最大效用，所以P中每個項效用都不大于umax。由式（2）可知因此當(dāng)maub(P，D) ≤minau時，AU(P，D) ≤minau。

剪枝策略 如果模式P的最大平均效用上界不大于minau，即maub(P，D) ≤minau，則模式P及其所有的超模式都可以被剪枝，其中minau是當(dāng)前結(jié)果集中最小平均效用值。

例10 給定模式P=（ab）*（a）*（c），當(dāng)前minau=50。由例9 可知maub(P，D)=4 × 10=40

3.3 TOUP算法

本文提出TOUP 算法挖掘項集序列數(shù)據(jù)庫下top-k高平均效用模式，具體步驟如下：

步驟1 根據(jù)式（2）計算每個項的平均效用，將平均效用排名前k的項存進結(jié)果集K，獲得當(dāng)前最小平均效用閾值minau，若項的個數(shù)不大于k，則初始化minau為零。

步驟2 根據(jù)式（3）計算各項的maub值，若maub>minau，則將該項存入隊列C，并按照maub降序存儲在數(shù)組I中。

步驟3 隊列C中元素出隊列記為模式P，基于數(shù)組I使用項集擴展和序列擴展生成模式P超模式集Q。

步驟4 從Q中取出模式P'，分別根據(jù)式（2）和式（3）計算模式P'的au和maub，若maub(P'，D) >minau，將模式P'儲到隊列C中，并當(dāng)AU(P'，D) >minau時，更新結(jié)果集K，minau和數(shù)組I；否則模式P'被修剪，直到Q為空。

步驟5 迭代步驟3～4，直到C為空，得到結(jié)果集K。

TOUP 算法的偽代碼如下：

算法2 TOUP 算法。

輸入 序列數(shù)據(jù)庫D，效用表T，參數(shù)k；

定理4TOUP 算法的時間復(fù)雜度和空間復(fù)雜度分別為O（nmLt）和O(mL+t)，其中n、m、L和t分別代表數(shù)據(jù)庫大小、序列大小、最大模式大小和候選模式數(shù)。

證明 TOUP 算法的核心步驟為模式支持度計算，并且每個候選模式均需計算它的支持度。因此，TOUP 算法的時間復(fù)雜度為O（nmLt）。分析TOUP 算法可知，該算法主要內(nèi)存消耗在于候選模式和支持度計算過程中位置數(shù)組的存儲，因此，CSP 算法的空間復(fù)雜度為O(mL+t)。

4 實驗與結(jié)果分析

為驗證TOUP 算法的挖掘能力、可擴展性和不同參數(shù)對挖掘效率的影響，在真實數(shù)據(jù)集和合成數(shù)據(jù)集上對本文算法進行實驗分析。

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

本文采用5 個真實數(shù)據(jù)集和1 個合成數(shù)據(jù)集驗證TOUP算法效率，其中數(shù)據(jù)集SDB1（https：//tianchi.aliyun.com/dataset/dataDetail？dataId=45）是一個嬰兒產(chǎn)品的銷售數(shù)據(jù)集；數(shù)據(jù)集SDB2（http：//www.philippe-fournier-viger.com/spmf/datasets/_shop.txt）是網(wǎng)上購物點擊流數(shù)據(jù)集；SDB3、SDB5 和SDB6 是真實數(shù)據(jù)集，SDB4 是合成數(shù)據(jù)集，來自http：//www.philippe-fournier-viger.com/spmf/index.php？link=datasets.php。為了對比各算法在特殊序列數(shù)據(jù)庫中的挖掘效率，SDB5 和SDB6 為單項序列數(shù)據(jù)庫，其余為項集序列數(shù)據(jù)庫。表3 是對所選數(shù)據(jù)集的介紹。

表3 實驗數(shù)據(jù)集Tab.3 Experimental datasets

實驗運行環(huán)境 操作系統(tǒng)為Ubuntu，處理器為Intel Xeon Silver 4210，主頻為2.20 GHz，內(nèi)存為64 GB，開發(fā)語言為Python，開發(fā)工具為PyCharm。

4.2 對比算法

本文采用6 個對比實驗驗證TOUP 算法的有效性和可擴展性。其中TOUP-rf、TOUP-nus 和TOUP-dfs 共3 個對比算法用于消融實驗，驗證TOUP 算法各模塊的有效性。并使用HAOP-ms、HANP-oms 和PMBC-ms 算法驗證TOUP 算法挖掘的有效性。

TOUP-rf（TOUP-reverse fill）為了驗證CSP 算法的有效性，提出TOUP-rf 算法，該算法采用文獻［18］中提出的逆序填充策略計算模式支持度。

TOUP-nus（TOUP-no used itemset pruning strategy）為了驗證剪枝策略的有效性，提出了TOUP-nus 算法，該算法在TOUP 算法的基礎(chǔ)上未對長度為1 的模式進行剪枝。

TOUP-dfs（TOUP-depth first search）為了驗證廣度優(yōu)先生成候選模式對挖掘效率的影響，提出了TOUP-dfs 算法，該算法使用深度優(yōu)先生成候選模式。

HAOP-ms（HAOP-multiple itemsets）基于文獻［18］中提出的HAOP-Miner 算法。

HANP-oms（HANP-one-off multiple itemsets）該算法基于文獻［29］中提出的HANP-Miner（High average utility nonoverlapping sequential pattern mining）算法。

PMBC-ms（PMBC-multiple itemsets）基于文獻［33］中提出 的PMBC（Pattern Mining from Biological sequences with wildcard Constraints）算法。

將上述算法用于解決一次性項集序列模式挖掘問題。

4.3 實驗分析

4.3.1 挖掘能力

本文在6 個數(shù)據(jù)集上，與對比算法TOUP-rf、TOUP-nus、TOUP-dfs、HAOP-ms、HANP-oms 和PMBC-ms 在生成候選模式數(shù)、運行時間和內(nèi)存消耗上進行對比。其中預(yù)設(shè)k=10 和最小平均效用閾值minau=0，最小平均效用閾值在挖掘過程中攀升。表4～6 分別展示了TOUP 算法與各對比算法在候選模式數(shù)量、運行時間和內(nèi)存消耗方面的對比。

表4 在6個數(shù)據(jù)集上不同算法生成候選模式數(shù)量對比Tab.4 Comparison of number of candidate patterns generated by different algorithms on six datasets

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

1）TOUP 算法中使用的支持度計算算法更加高效。TOUP-rf 算法采用逆序填充策略計算模式支持度，由表4、6可知，TOUP 算法與TOUP-rf 算法生成候選模式數(shù)量相等，兩者內(nèi)存消耗相似。但從表5 中可以看出，在運行時間方面TOUP 算法少于TOUP-rf 算法。如數(shù)據(jù)集SDB1 上TOUP 運行時間為71 s，而TOUP-rf 運行時間則為123 s，TOUP 運行時間效率提高了42.3%。這是因為它采用了基于各項出現(xiàn)位置與項重復(fù)關(guān)系數(shù)組的CSP 算法，能夠快速搜索出現(xiàn)位置并判斷是否滿足一次性條件。因此，TOUP 算法優(yōu)于TOUP-rf。

表5 在6個數(shù)據(jù)集上不同算法運行時間對比 單位：sTab.5 Comparison of running time among different algorithms on six datasets unit：s

表6 在6個數(shù)據(jù)集上不同算法內(nèi)存消耗對比 單位：MBTab.6 Comparison of memory consumption among different algorithms on six datasets unit：MB

2）提前對1 長度模式進行剪枝可以有效提高算法挖掘效率。如表5、6 所示，TOUP 算法在運行時間和內(nèi)存消耗方面均少于TOUP-nus 算法，這是因為剪枝策略能夠有效減少可擴展項，在生成候選模式階段避免一些冗余模式生成，從而降低算法的時間和空間消耗。例如在表4 中TOUP 算法和TOUP-nus 算法在SDB1 上的生成候選模式數(shù)量分別為369 和1 206，相較于TOUP-nus，TOUP 的候選模式數(shù)縮減了69.4%。因此對1 長度模式進行剪枝可以減少候選模式生成，從而有效地提高算法效率。

3）使用廣度優(yōu)先的方式生成候選模式可提高算法挖掘效率。與TOUP 算法不同，TOUP-dfs 算法使用深度優(yōu)先遍歷枚舉樹生成候選模式。由表4 可知，TOUP-dfs 算法生成了過多的候選模式，如在SDB3 中，TOUP 算法生成了8 152 個候選模式，而TOUP-dfs 算法卻生成了63 818 個候選模式，TOUP算法的候選模式數(shù)降低了99.8%；在6 個數(shù)據(jù)集上，相較于TOUP-dfs 算法，TOUP 算法候選模式數(shù)降低了38.5%～99.8%。由于生成了較多的冗余候選模式，使得TOUP-dfs 算法有較長的運行時間，如表5 中TOUP-dfs 在SDB4 數(shù)據(jù)集上的運行時間為456 s，遠(yuǎn)高于TOUP 算法在SDB4 數(shù)據(jù)集上的運行時間13 s，所以TOUP 算法相較于TOUP-dfs 算法運行效率提高了97.1%；在6 個數(shù)據(jù)集上運行時間降低了33.6%～97.1%。造成這一現(xiàn)象的原因是深度遍歷方式會優(yōu)先生成較長的候選模式，而通常這種候選模式的平均效用值會很低。由此可見使用廣度遍歷生成候選模式可提高算法挖掘效率。

4）TOUP 算法相較于最新研究算法更加高效。如表5、6所示，TOUP 算法在運行時間和內(nèi)存消耗方面均優(yōu)于HAOP-ms、HANP-oms 和PMBC-ms 算法，因為TOUP 算法解決在項集序列數(shù)據(jù)庫中挖掘一次性條件下top-k高平均效用序列模式的問題更加高效，生成了更少的候選模式。例如在表4 中TOUP 算法和HAOP-ms 算法在SDB1 上的生成候選模式數(shù)量分別為369 和1 650，所以TOUP 算法相較于HAOP-ms 算法，候選模式數(shù)縮減了77.6%；在6 個數(shù)據(jù)集上，TOUP 算法的候選模式數(shù)降低了0.9%～77.6%，運行時間降低了57.9%～97.2%。因此新提出的TOUP 算法擁有更高的挖掘效率。

綜上，TOUP 算法在內(nèi)存消耗、運行時間和候選模式數(shù)方面均優(yōu)于其他對比算法。

4.3.2 可擴展性

為驗證TOUP 算法的可擴展性，將數(shù)據(jù)集SDB1 擴展至原來的1～6 倍生成數(shù)據(jù)集SDB1_1、SDB1_2、SDB1_3、SDB1_4、SDB1_5 和SDB1_6。本節(jié)使用6 個對比算法在上述數(shù)據(jù)集上進行實驗。預(yù)設(shè)k=10 和最小平均效用閾值minau=0。由于在倍數(shù)增長的數(shù)據(jù)集上各算法的候選模式數(shù)量大小不變，所以本節(jié)僅展現(xiàn)算法在各數(shù)據(jù)集上內(nèi)存消耗和運行時間的對比。表7、8 分別展示了運行時間和內(nèi)存消耗的實驗結(jié)果。

表7 在SDB1_1～SDB1_6數(shù)據(jù)集上不同算法的運行時間對比 單位：sTab.7 Comparison of running time among different algorithms on SDB1_1-SDB1_6 datasets unit：s

表8 在SDB1_1～SDB1_6數(shù)據(jù)集上不同算法的內(nèi)存消耗對比 單位：MBTab.8 Comparison of memory consumption among different algorithms on SDB1_1-SDB1_6 datasets unit：MB

隨著數(shù)據(jù)集大小的增長，TOUP 的運行時間和內(nèi)存消耗均在增加。由表7、8 可知當(dāng)數(shù)據(jù)集從1 倍增加到6 倍時，運行時間增長了5.8 倍，內(nèi)存消耗增長了1.2 倍。從以上數(shù)據(jù)分析，TOUP 挖掘效率和數(shù)據(jù)集大小呈正相關(guān)，且內(nèi)存消耗的增長速度遠(yuǎn)低于數(shù)據(jù)集大小的增長速度。除此之外，根據(jù)表7、8 可以發(fā)現(xiàn)，在任意大小的數(shù)據(jù)集中，TOUP 算法的運行時間與內(nèi)存消耗均低于其他對比算法。綜上所述，TOUP 算法在大規(guī)模數(shù)據(jù)集具有較好的可擴展性。

4.3.3k值對實驗結(jié)果的影響

為了驗證在不同k值下，TOUP 算法相較于其他算法有更好的挖掘性能，使用6 個對比算法在SDB1 數(shù)據(jù)集上進行實驗，將k值從10 遞增到20。表9、10 分別展示了運行時間和候選模式數(shù)量對比。

表9 不同參數(shù)k的生成候選模式數(shù)對比Tab.9 Comparison of number of generated candidate patterns with different parameter k

由表9 可知，候選模式數(shù)量隨著k值的增大而增大，如TOUP 算法在k=10 和k=20 時，候選模式數(shù)分別為369 和956。而更多的候選模式生成，導(dǎo)致更多的支持度計算次數(shù)，即更多的運行時間消耗，在表10 驗證了這點：k值越大，運行時間越長。如TOUP 算法在k=10 和k=20 時，運行時間分別 為71 s 和176 s，增長了1.5 倍。而TOUP-rf、TOUP-nus、TOUP-dfs、HAOP-ms、HANP-oms 和PMBC-ms 算法在k=10 和k=20 時，運行時間分別增長了1.6 倍、2.1 倍、3.8 倍、3.0倍、3.0 倍和1.6 倍。綜上所述，TOUP 算法挖掘效果更加高效。

表10 不同參數(shù)k的運行時間對比 單位：sTab.10 Comparison of running time with different parameter k unit：s

5 結(jié)語

本文提出了在一次性條件下top-k高平均效用序列模式挖掘算法TOUP，該算法可以在不具備先驗知識的情況下，挖掘用戶最感興趣的k個高平均效用模式。該算法主要包含平均效用計算與候選模式生成兩個步驟。在平均效用計算方面，采用各項的出現(xiàn)位置信息與項重復(fù)關(guān)系數(shù)組實現(xiàn)高效的支持度計算，從而快速地計算模式的平均效用；在候選模式生成方面，采用項集擴展和序列擴展的模式擴展方式生成候選模式，并提出滿足反單調(diào)性的最大平均效用上界，利用Apriori 性質(zhì)剪枝冗余的候選模式，大幅減少了候選模式的生成數(shù)，提高了挖掘效率。本文實驗部分通過與6 個對比算法進行對比，得出了TOUP 算法在候選模式生成、運行時間和內(nèi)存消耗方面的性能均優(yōu)于其他對比算法；還驗證了TOUP算法具有較強的可擴展性，且它的挖掘性能受參數(shù)k值影響最小。綜上所述，本文的實驗結(jié)果均驗證了TOUP 算法的高效性。

高平均效用序列模式挖掘的關(guān)鍵問題在于平均效用計算和候選模式生成，本文提出了通過位置信息和項重復(fù)關(guān)系數(shù)組的方式計算模式一次性出現(xiàn)與平均效用，使用基于最大平均效用的候選模式生成策略。但這樣的挖掘方式太復(fù)雜，未來將研究如何減少掃描數(shù)據(jù)庫次數(shù)，提高模式平均效用計算效率；研究更嚴(yán)格的上界與更優(yōu)的剪枝策略。