一次性條件下top-k高平均效用序列模式挖掘算法

楊克帥，武優西*，耿 萌，劉靖宇，李 艷

（1.河北工業大學 人工智能與數據科學學院，天津 300401；2.河北工業大學 經濟管理學院，天津 300401）

0 引言

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

傳統頻繁序列模式挖掘只考慮模式是否在序列中出現，而忽略了它在序列的出現次數。為解決此問題，重復挖掘方法［6-12］應運而生，該方法通過模式匹配技術計算模式在一條序列的出現次數。例如：假定有兩個消費者，他們的購買次序分別形成了兩條消費序列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中均有出現。由于傳統的序列模式挖掘方法不甄別模式在序列中的重復性，因此模式（ab）（c）在S1和S2中的支持度為2。而可重復序列模式挖掘則甄別模式在序列中的重復性，易知模式（ab）（c）在S2中的出現了3 次，出現位置為因此在可重復序列模式挖掘中，模式（ab）（c）在S1和S2中的支持度分別為1 和3，總支持度為4。由此可見，消費者2 比消費者1 在模式（ab）（c）上具有更大的興趣。因此，可重復序列模式挖掘與傳統序列模式挖掘方法顯著不同。

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

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

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

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

1 相關工作

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

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

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

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

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

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

3）候選模式剪枝策略不同。提出滿足反單調性的平均效用上界，在此基礎上構建高效的候選模式生成策略與剪枝策略。

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

2 問題定義

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

表1 序列數據庫DTab.1 Sequence database D

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

定義2出現和一次性出現。給定m個整數L=當且僅當1 ≤l1

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

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

定義4效用與平均效用。

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

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

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

例2 給定序列數據庫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高平均效用模式。序列數據庫中平均效用值最高的k個模式被稱為top-k高平均效用模式。

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

3 算法描述

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

3.1 平均效用計算

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

步驟1 創建m層節點，其中m是模式P的大小。第j層是位置數組Aj，存儲了pj的位置信息。若pj只有一項，Aj存儲該項的出現位置；否則Aj存儲該項集內所有項的位置交集。

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

步驟2 為了處理一次性條件，初始化模式中項重復關系數組R。

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

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

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

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

步驟4 返回第一層繼續重復步驟3，直到沒有新的出現生成。

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

算法1 CSP 算法。

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

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

3.2 候選模式生成

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

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

項集擴展 在模式的最后一個項集內有序擴展新項。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 TOUP算法

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

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

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

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

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

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

TOUP 算法的偽代碼如下：

算法2 TOUP 算法。

輸入 序列數據庫D，效用表T，參數k；

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

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

4 實驗與結果分析

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

4.1 數據集

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

表3 實驗數據集Tab.3 Experimental datasets

實驗運行環境 操作系統為Ubuntu，處理器為Intel Xeon Silver 4210，主頻為2.20 GHz，內存為64 GB，開發語言為Python，開發工具為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 算法的基礎上未對長度為1 的模式進行剪枝。

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

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

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

根據以上實驗結果，可得出以下結論：

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

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

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

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

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

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

綜上，TOUP 算法在內存消耗、運行時間和候選模式數方面均優于其他對比算法。

4.3.2 可擴展性

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

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

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

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

4.3.3k值對實驗結果的影響

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

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

由表9 可知，候選模式數量隨著k值的增大而增大，如TOUP 算法在k=10 和k=20 時，候選模式數分別為369 和956。而更多的候選模式生成，導致更多的支持度計算次數，即更多的運行時間消耗，在表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 不同參數k的運行時間對比 單位：sTab.10 Comparison of running time with different parameter k unit：s

5 結語

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

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