摘 要：周期高效用序列模式挖掘（PHUSPM）因其能夠發(fā)現(xiàn)時(shí)間序列中更具實(shí)際價(jià)值的規(guī)律性模式而備受關(guān)注，但現(xiàn)有的PHUSPM算法難以有效地處理數(shù)據(jù)集的增量更新，且未考慮大規(guī)模數(shù)據(jù)下算法的向下閉包性和復(fù)雜性。針對(duì)該問(wèn)題，提出了IncPUS-Miner算法，有效地實(shí)現(xiàn)了周期高效用序列模式（PHUSPs）的增量挖掘。IncPUS-Miner引入了一種名為pu-tree的新型數(shù)據(jù)結(jié)構(gòu)，每個(gè)樹節(jié)點(diǎn)對(duì)應(yīng)一個(gè)更新效用列表（UUL）用于存儲(chǔ)相應(yīng)序列的輔助信息，當(dāng)有增量數(shù)據(jù)加入時(shí)，該結(jié)構(gòu)使得項(xiàng)目信息能夠靈活更新，從而增強(qiáng)了算法的動(dòng)態(tài)適應(yīng)性和可擴(kuò)展性。此外，還提出了兩種新的序列效用上界PUB和EUB，以及兩種相應(yīng)的剪枝策略，有效地減少了計(jì)算負(fù)擔(dān)。實(shí)驗(yàn)結(jié)果表明，在真實(shí)數(shù)據(jù)集上，IncPUS-Miner算法可以有效地增量挖掘PHUSPs，與其他算法相比，在運(yùn)行效率和內(nèi)存消耗上展現(xiàn)出了優(yōu)越的性能。

關(guān)鍵詞：增量挖掘； 高效用序列模式； 周期序列模式； 序列模式挖掘

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2024）08-008-2301-08

doi：10.19734/j.issn.1001-3695.2023.12.0607

Effective incremental mining algorithm forperiodic high-utility sequential patterns

Xun Yaling， Ren Ziqian， Yan Haibo

（College of Computer Science & Technology， Taiyuan University of Science & Technology， Taiyuan 030024， China）

Abstract：Periodic high utility sequential pattern mining（PHUSPM） has attracted much attention because it can find more practical regular patterns in time series. 0WckXHg/1zH9NyqfpE2D7w==However， existing PHUSPM algorithms struggle to effectively handle incremental updates and overlook the downward closure property and complexity of the algorithm in large-scale data. To solve this problem， this paper proposed an IncPUS-Miner algorithm， which effectively realized the incremental mining of periodic high-utility sequential patterns（PHUSPs）. IncPUS-Miner introduced a novel data structure called pu-tree. Each tree node corresponded to an updated utility list（UUL） to store the auxiliary information of the corresponding sequence. When incremental data was added， this structure allowed flexible updates to project information， thereby enhancing the dynamic adaptability and scalability of the algorithm. In addition， this paper proposed two new upper boundsdn8fJNqDdQNk1RMoa5x/Zw== of sequence utility， PUB and EUB， and two corresponding pruning stra-tegies， which effectively reduced the computational burden. The experimental results show that the IncPUS-Miner algorithm effectively realizes the incremental mining of PHUSPs on real data， and shows superior performance compared with other algorithms.

Key words：incremental mining; high utility sequential pattern; periodic sequential pattern; sequential pattern mining

0 引言

高效用序列模式挖掘（HUSPM）是數(shù)據(jù)挖掘的焦點(diǎn)之一，其任務(wù)是在定量序列中找到所有具有高效用的子序列［1］。HUSPM的效用度量與傳統(tǒng)序列模式挖掘［2］的支持度量不同，不具有單調(diào)性或反單調(diào)性，無(wú)法直接用于搜索空間剪枝［3］。因此，如何制定更有效的效用上限，以優(yōu)化搜索空間并提高性能是HUSPM面臨的挑戰(zhàn)之一［4，5］。

隨著大數(shù)據(jù)時(shí)代的興起，新數(shù)據(jù)不斷產(chǎn)生。由于靜態(tài)方法需要重新掃描整個(gè)數(shù)據(jù)集執(zhí)行挖掘，導(dǎo)致增量挖掘過(guò)程非常耗時(shí)。因此，一些能夠有效處理增量數(shù)據(jù)的序列數(shù)據(jù)挖掘算法應(yīng)運(yùn)而生［6～12］。Yun等人［7］提出了基于索引列表的增量高效用模式挖掘（IIHUM）算法，僅需一次數(shù)據(jù)集掃描。Kim等人［8］提出了基于樹狀結(jié)構(gòu)的高平均效用項(xiàng)集（IMHAUI）的增量挖掘算法。Wang等人［9］采用基于候選模式樹結(jié)構(gòu)的算法來(lái)實(shí)現(xiàn)增量挖掘高效用序列模式。這些增量算法旨在處理高效用模式的問(wèn)題，未考慮模式的周期性約束。毛伊敏等人［10］提出了改進(jìn)的并行關(guān)聯(lián)規(guī)則增量挖掘算法，為處理大規(guī)模數(shù)據(jù)集的挖掘提供了有效方法。

周期性高效用序列模式挖掘（PHUSPM）發(fā)現(xiàn)的模式不僅具有高效用特性，還呈現(xiàn)周期性出現(xiàn)規(guī)律［13］，在實(shí)際應(yīng)用中具有重要意義［14］。例如，在市場(chǎng)分析中，分析消費(fèi)者購(gòu)買習(xí)慣的周期性和高效用模式可幫助商家優(yōu)化促銷策略。在基因序列分析中［15］，尋找具有特定周期性和高效用的模式有助于理解生物過(guò)程中的重要事件。近年來(lái)，F(xiàn)ournier-Viger及其團(tuán)隊(duì)［16］提出了PHM算法，用于尋找周期性高效用項(xiàng)集。Dinh等人［13］提出PHUSPM算法，但由于未采用剪枝策略，導(dǎo)致執(zhí)行時(shí)間長(zhǎng)且內(nèi)存占用大。Dinh等人［17］提出了基于PUSP結(jié)構(gòu)的PUSOM算法，可以發(fā)現(xiàn)序列數(shù)據(jù)庫(kù)中的所有PHUSPs，但不適用于動(dòng)態(tài)數(shù)據(jù)集。盡管已有一些有效的周期性高效用序列模式挖掘算法，PHUSPs挖掘仍面臨以下問(wèn)題和挑戰(zhàn)：

a）數(shù)據(jù)集的增量更新。傳統(tǒng)的PHUSPM算法在處理新數(shù)據(jù)時(shí)需要重新從頭開始挖掘，導(dǎo)致大量重復(fù)開銷，難以有效應(yīng)對(duì)數(shù)據(jù)集變化。

b）向下閉包性。周期高效用模式挖掘考慮向下閉包性質(zhì)，增加了算法復(fù)雜性，特別是在處理動(dòng)態(tài)序列數(shù)據(jù)時(shí)需要不斷更新向下閉包性。

c）復(fù)雜性和效率?，F(xiàn)代大規(guī)模數(shù)據(jù)集的增加使得周期高效用模式挖掘算法需要在保持高效性的同時(shí)處理復(fù)雜性。設(shè)計(jì)更高效的數(shù)據(jù)結(jié)構(gòu)和算法是必要的，以在大規(guī)模數(shù)據(jù)上進(jìn)行快速挖掘。

針對(duì)上述問(wèn)題，本文提出一種新的增量挖掘算法IncPUS-Miner，允許在現(xiàn)有模式的基礎(chǔ)上高效地更新和增加新模式，而無(wú)須重新掃描整個(gè)數(shù)據(jù)集，從而減少了不必要的開銷。其主要貢獻(xiàn)總結(jié)如下：

a）提出一種新的數(shù)據(jù)結(jié)構(gòu)，稱為pu-tree，并設(shè)計(jì)了樹節(jié)點(diǎn)更新效用列表（UUL），用于存儲(chǔ)相應(yīng)序列的輔助信息，以便在數(shù)據(jù)更新時(shí)快速獲取序列的效用等輔助信息，避免不必要的重復(fù)計(jì)算開銷?；谠摂?shù)據(jù)結(jié)構(gòu)提出一個(gè)新的增量周期性高效用模式挖掘算法IncPUS-Miner，以有效挖掘大規(guī)模和不斷更新的序列數(shù)據(jù)中的周期性高效用模式。

b）為了減少冗余計(jì)算，定義了兩個(gè)新的序列效用上界，分別稱為PUB和EUB，并提出了兩種相應(yīng)的剪枝策略，以顯著提高挖掘效率。

c）在真實(shí)數(shù)據(jù)集上進(jìn)行大量的實(shí)驗(yàn)表明，IncPUS-Miner算法能夠有效地增量挖掘PHUSPs，算法性能優(yōu)于其他對(duì)比算法。

1 相關(guān)定義

I={i1，i2，…，in}，n≥1是一組包含n個(gè)項(xiàng)目的有限集。序列數(shù)據(jù)庫(kù)中每個(gè)項(xiàng)記為（ik，qk），其中ik∈I（1≤k≤n），qk表示內(nèi)部效用值，外部效用值用p（ik）表示。在表1所示的序列數(shù)據(jù)集中，（a，2）表示項(xiàng)目a的內(nèi)部效用值為2。表2體現(xiàn)了每個(gè)項(xiàng)目對(duì)應(yīng)的外部效用，如a的外部效用值為3。

T=［（i1，q1），（i2，q2），…，（im，qm）］可以表示為一條事務(wù)。一般情況下，事務(wù)中的項(xiàng)目順序按照字典順序來(lái)排序。表1給出的序列數(shù)據(jù)庫(kù)包含6條序列，每個(gè)序列Si（1≤i≤6）又包含多條事務(wù)T。比如S1中包含了3條事務(wù)，分別是T1=［（a，2）（c，1）］，T2=［（e，2）］，T3=［（b，6）］。

模式t屬于項(xiàng)集，它的表示方法有t1=〈（i1i2i3）〉和t2=〈i1i2i3〉，模式t1表示包含的三個(gè)項(xiàng)存在于同一事務(wù)中，而模式t2表示三個(gè)項(xiàng)各自存在于不同事務(wù)里。

定義1 項(xiàng)目效用。對(duì)于項(xiàng)目i，其在序列S的第j個(gè)事務(wù)中的效用定義為

U（i，j，S）=q（i，j，S）×p（i）（1）

例1 U（a， 1， S2）= 3，U（a ， 2， S2）= 12。

定義2 項(xiàng)集效用。項(xiàng)集X在序列S的第j個(gè)事務(wù)中的效用被定義為

U（X，j，S）=∑i∈XU（i，j，S）（2）

例2 U（〈ac〉，〈1，2〉，S2）=U（a，1，S2）+U（c，2，S2）=27。

定義3 模式在序列中的效用。模式t在序列S中的效用記為U（t，S），定義為模式t在序列S中的所有實(shí)例效用的最大值。其中，〈j1，j2，…，j|s|〉是模式t在序列S中出現(xiàn)的事務(wù)號(hào)的集合。

U（t，S）=max{∑i∈tU（i，〈j1，j2，…，j|S|〉，S）}（3）

例3 給定一個(gè)模式t=〈ac〉，它在序列S2出現(xiàn)的事務(wù)號(hào)集合為〈〈1，2〉，〈1，3〉，〈2，3〉〉，故U（〈ac〉，S2）=max{U（〈ac〉，〈1，2〉，S2），U（〈ac〉，〈1，3〉，S2），U（〈ac〉，〈2，3〉，S2）}=max{27，11，20}=27。

定義4 模式在數(shù)據(jù)集中的效用。模式t在數(shù)據(jù)集D中的效用記為

UD（t）=∑S∈D∧tSU（t，S）（4）

定義5 高效用序列模式。當(dāng)模式t的效用UD（t）≥minutil時(shí)，模式t為序列數(shù)據(jù)庫(kù)D中的高效用序列模式，否則認(rèn)為模式t是低效用模式。其中，minutil是用戶給定的最小效用閾值。

例4 給定模式t=〈ac〉，minutil為20，根據(jù)表1所示，模式t=〈ac〉只出現(xiàn)在S2和S5兩個(gè)序列中，所以UD（〈ac〉）=U（〈ac〉，S2）+U（〈ac〉，S5）=27+7=34。34>20，因此，模式t=〈ac〉是高效用模式。

給定數(shù)據(jù)集D={S1，S2，…，Sn}和模式t，模式t在數(shù)據(jù)集D中出現(xiàn)的序列列表為S（t，D）={Si1，Si2，…，Sik}，其中1≤i1<i2<…< ik≤n，Sik是指第ik條序列。模式t在D中的擴(kuò)展序列列表為g（t，D）={Si0，Si1，Si2，…，Sik}，Sid（Si0）=0。

定義6 模式的周期。在g（t，D）中連續(xù)出現(xiàn)的兩個(gè)序列之間相距的序列數(shù)稱為這兩個(gè)序列的周期，記為per，即式（5）。Si（k+1）是指數(shù)據(jù)集D中的最后一條序列，Sid（Si（k+1））=|D|=n。

per（t，ik）=Sid（Si（k+1））-Sid（Sik）（5）

例5 根據(jù)表1的數(shù)據(jù)集D（n=5），模式t=〈ac〉的擴(kuò)展序列列表g（〈ac〉，D）={S0，S2，S5}，即i0=0，i1=2，i2=5。根據(jù)式（5），得到per（〈ac〉，i0）=2-0=2，per（〈ac〉，i1）=5-2=3，per（〈ac〉，i2）=n-5=0，因此per（〈ac〉）={2，3，0}。對(duì)于模式t=〈（ac）〉，它表示項(xiàng)目a和c存在于同一事務(wù)中，它的序列列表S（〈（ac）〉，D）={S1，S2，S5}， g（〈（ac）〉，D）={S0，S1，S2，S5}，計(jì)算得到per（〈（ac）〉）={1，1，3，0}。

下面介紹三個(gè)周期性度量，分別是最大周期度量、最小周期度量和平均周期度量。這三種度量為用戶發(fā)現(xiàn)PHUSPs提供了更多的靈活性，比如，用戶可以選擇通過(guò)使用三種度量或只使用最大周期度量來(lái)找到序列數(shù)據(jù)庫(kù)中的周期模式。

定義7 周期性度量。模式t最大周期值記為maxper（t）=max（per（t）），最小周期值是minper（t）=min（per（t）），平均周期值是avgper（t）=∑per（t）|per（t）|。

例6 根據(jù)定義6中的示例可知，模式t=〈ac〉的周期per（〈ac〉）={2，3，0}，那么模式t的最大周期值為maxper（t）=max{2，3，0}=3，最小周期值是minper（t）=min{2，3，0}=0，平均周期值是avgper（t）=5/3=1.67。

絕大多數(shù)的周期模式挖掘算法僅僅依賴于最大周期度量（maxPer），這可能導(dǎo)致一些模式由于滿足最大周期約束而被挖掘出來(lái)，盡管它們只在少數(shù)序列中出現(xiàn)。這種單一度量的方法存在不足之處。因此，本文算法選擇綜合三種度量，以提供更多靈活性給用戶的同時(shí)，確保挖掘出更有實(shí)際意義的模式。

定義8 周期高效用序列模式。給定模式t以及5個(gè)用戶給定的閾值（minutil，maxPer，minPer，maxAvg，minAvg）。如果模式t同時(shí)滿足以下兩個(gè)條件，則被稱為周期高效用模式（PHUSP）：a）模式t滿足定義5，即UD（t）≥minutil；b）模式t滿足maxper（t）≤maxPer，minper（t）≥minPer且minAvg≤avgper（t）≤maxAvg。

定義9 插入序列。當(dāng)序列S插入數(shù)據(jù)集D后，獨(dú)立構(gòu)成一條新的序列時(shí)，將S稱為插入序列。在表1中，S6是插入序列。

定義10 附加序列。當(dāng)序列S插入數(shù)據(jù)集D后，附加在原始數(shù)據(jù)集中的序列S0結(jié)尾，從而形成S0·S形式的新序列，這樣的序列稱為附加序列。在表1中，S4和S5是附加序列。

定義11 模式連接。模式的擴(kuò)展分為I-連接和S-連接［5］。對(duì)于給定模式t，I-連接指的是將與模式t在同一事務(wù)中存在的項(xiàng)i附加到t后，形成一個(gè)新的項(xiàng)集，表示為〈t⊕i〉。類似地，S-連接表示將模式t后續(xù)事務(wù)中的項(xiàng)i附加到t后，形成一個(gè)新的項(xiàng)集，表示為〈ti〉。這兩種連接方式是模式擴(kuò)展的關(guān)鍵策略。

2 IncPUS-Miner算法

IncPUS-Miner算法采用pu-tree結(jié)構(gòu)，通過(guò)效用列表存儲(chǔ)序列的相關(guān)信息，以便在更新數(shù)據(jù)時(shí)快速獲取相關(guān)信息。同時(shí)設(shè)計(jì)了兩個(gè)序列效用上界及兩種剪枝策略，縮減了算法的搜索空間，以進(jìn)一步提高算法性能。

2.1 序列效用上界

在文獻(xiàn)［5］中提出了兩個(gè)效用上界，即前綴擴(kuò)展效用（PEU）和簡(jiǎn)化序列效用（RSU）。PEU上界策略需要計(jì)算模式t在序列中每次出現(xiàn)時(shí)的效用值及當(dāng)下位置的剩余效用之和，再選擇最大值作為模式在該序列的PEU值，這樣的計(jì)算過(guò)程復(fù)雜。為了提高挖掘效率，在本節(jié)中提出了兩個(gè)新的序列效用上界，稱為前綴-效用上界（PUB）和擴(kuò)展-效用上界（EUB），在2.1.1節(jié)和2.1.2節(jié)中分別給出了定義。

2.1.1 前綴-效用上界（PUB）

假如模式t在序列S中出現(xiàn)的位置為j：〈j1，j2，…，jm〉，模式t在序列S中的PUB值定義如式（6），j1是指模式t首次出現(xiàn)的位置。模式t的PUB值表示如式（7）所示。

PUB（t，S）=Umax（t，S）+RU（t，j1，S） RU＞00其他（6）

PUB（t）=∑t∈S∩S∈DPUB（t，S）（7）

模式t在序列S中的PUB值指的是模式t在序列中出現(xiàn)的最大效用值與模式t首次出現(xiàn)位置的剩余效用值之和。

例7 在表1的原始數(shù)據(jù)集D中，模式t=〈a〉在序列S1中的PUB值表示為PUB（t，S1）=U（〈a〉，S1）+RU（〈a〉，1，S1）=6+44=50，同理計(jì)算得到PUB（t，S2）=12+54=66，PUB（t，S3）=6+4=10，PUB（t，S4）=0，PUB（t，S5）=15+25=40。因此，模式t在數(shù)據(jù)集D中的PUB值表示為PUB（〈a〉）=166。

定理1 向下閉包性質(zhì)。給定兩個(gè)模式t和t′，如果t′包含t（t′是t的擴(kuò)展模式），那么滿足PUB（t′）≤PUB（t）。

證明 假設(shè)序列S中存在兩個(gè)模式t和t′，模式t′是t的擴(kuò)展模式，表示為t′=t·t″。模式t在序列S中首次出現(xiàn)位置的剩余效用為RU（t，j1，S），且RU（t，j1，S）≥Umax（t″）+RU（t″，j1，S），根據(jù)式（6），可得PUB（t，S）≥Umax（t，S）+Umax（t″）+RU（t″，j1，S），又因?yàn)镽U（t″，j1，S）=RU（t′，j1，S），所以PUB（t，S）≥PUB（t′，S）。

例8 給定兩個(gè)模式t=〈a〉和t′=〈ac〉，t′是t的擴(kuò)展模式。在表1的原始數(shù)據(jù)集D中，模式t=〈a〉出現(xiàn)在序列S1、S2、S3、S4、S5中，模式t′=〈ac〉只出現(xiàn)在序列S2、S5中，計(jì)算得到PUB（〈a〉）=166，PUB（〈ac〉）=46。由此可以得出，如果模式t′是模式t的超集，則滿足PUB（t′）≤PUB（t）。

定理2 給定一個(gè)模式t，對(duì)于它的每個(gè)擴(kuò)展模式t′，都滿足U（t′）≤PUB（t）。

證明 假設(shè)模式t出現(xiàn)在序列S中，p是S中t的實(shí)例擴(kuò)展位置（即模式t最后項(xiàng)出現(xiàn)的位置）。由于t是t′的前綴，若假設(shè)t′=t·t″，其中t″不為空集。那么模式t′在S中的效用包括兩部分：一是模式t的擴(kuò)展位置p處的效用；二是t″的效用（t″一定出現(xiàn)在擴(kuò)展位置p之后）。因此，模式t′的效用可以表示為U（t′）=U（t）+U（t″），U（t″）屬于剩余序列的一個(gè)子序列。而PUB（t）=Umax（t）+RU（t，j1），即模式t在序列S中出現(xiàn)的最大效用值與模式t首次出現(xiàn)位置的剩余效用值（即最大剩余效用值）之和。由于U（t）<Umax（t），U（t″）<RU（t，j1），可以得到U（t′）≤PUB（t）。

2.1.2 擴(kuò)展-效用上界（EUB）

假如在序列S中，模式t′由模式t經(jīng)過(guò)I-連接或S-連接擴(kuò)展而來(lái)，模式t′在序列S中的EUB值記為EUB（t′，S），表示如式（8）所示。模式t′在數(shù)據(jù)集D中的EUB值記為EUB（t′），表示如式（9）所示。

EUB（t′，S）=PUB（t，S） tS∧t′S0其他（8）

EUB（t′）=∑S∈DEUB（t′，S）（9）

定理3 給定一個(gè)模式t，對(duì)于它的每個(gè)擴(kuò)展模式t′，都滿足U（t′）≤ EUB（t′）。

證明 假設(shè)模式t可以通過(guò)I-連接或S-連接擴(kuò)展生成模式t′。根據(jù)定理2的證明可知，U（t′）≤PUB（t），在式（8）中表示EUB（t′，S）=PUB（t，S），因此，可以推出U（t′）≤EUB（t′）的結(jié)論。

2.2 剪枝策略

根據(jù)PUB和EUB這兩個(gè)效用上界，對(duì)應(yīng)提出了兩種剪枝策略，即前綴效用上界策略和擴(kuò)展效用上界策略。

策略1 前綴效用上界策略。假設(shè)t和minutil分別是候選模式和最小效用閾值。如果PUB（t）≤minutil，那么算法不需要檢查模式t及其擴(kuò)展后代。

該剪枝策略可以防止算法考慮沒有希望的項(xiàng)，因?yàn)镻UB上界具有向下閉包屬性，當(dāng)PUB（t）≤minutil時(shí)，就認(rèn)為模式t及它的所有擴(kuò)展模式都是無(wú)用的。

策略2 擴(kuò)展效用上界策略。設(shè)t和minutil分別是候選模式和當(dāng)前最小效用閾值，模式t通過(guò)I-連接或S-連接擴(kuò)展生成模式t′。當(dāng)EUB（t）≤minutil時(shí)，算法將停止擴(kuò)展模式t′。

根據(jù)定理3，EUB（t）是模式t以及它所有后代的效用上界，因此，當(dāng)EUB（t）<minutil時(shí)，以t為根的子樹可以安全地修剪，并不會(huì)影響挖掘結(jié)果。

由于需要考慮模式的周期性約束，下面介紹第三種剪枝策略［16］。

定理4 最大周期值單調(diào)性。給定兩個(gè)模式t和t′，其中t′是t的擴(kuò)展模式。因此，maxper（t′）≥maxper（t）。

證明 若S（t′）和S（t）是分別包含模式t′和t的序列集合。由于tt′，所以S（t′）S（t）。當(dāng)S（t′）=S（t）時(shí)，模式t和t′有相同的周期，即maxper（t）=maxper（t′）。若S（t′）S（t）時(shí)，per（t′）中的任何周期都不能小于per（t）中的周期，所以maxper （t′）>maxper（t）。

策略3 最大周期閾值修剪策略。假設(shè)t是一個(gè)出現(xiàn)在數(shù)據(jù)庫(kù)D中的高效用模式，maxPer是用戶給定的最大周期閾值。如果maxper（t）>maxPer，則模式t及其后代都不是周期高效用模式。

根據(jù)定義8，如果模式t不滿足maxper（t）>maxPer，那么模式t就不是周期高效用模式。通過(guò)定理4可知，模式t的所有后代的maxper值都大于maxPer，故它們都不是PHUSPs。

2.3 pu-tree結(jié)構(gòu)

文獻(xiàn)［10］提出了一種有效的基于候選模式樹結(jié)構(gòu)的增量算法，該算法能夠在不斷更新的數(shù)據(jù)庫(kù)中挖掘高效用序列模式，但未考慮模式的周期性。為了更全面地處理模式的效用和周期相關(guān)數(shù)據(jù)，提出了一種新的數(shù)據(jù)結(jié)構(gòu)，稱為pu-tree。該結(jié)構(gòu)以樹狀形式組織，其中每個(gè)樹節(jié)點(diǎn)代表一個(gè)項(xiàng)目，每個(gè)樹路徑代表一個(gè)模式或模式的一部分。算法掃描一次數(shù)據(jù)庫(kù)后，構(gòu)建這個(gè)樹，并將模式的相關(guān)信息都存儲(chǔ)在該樹節(jié)點(diǎn)的更新效用列表（UUL）中，以便在不需要重新計(jì)算的情況下快速獲取模式的相關(guān)信息。UUL包含的內(nèi)容有：

a）U（t）：模式t在輸入數(shù)據(jù)集中的效用值，即模式t在所有序列中的最大效用值之和。

b）PUB（t）：模式t在輸入數(shù)據(jù)集中的PUB值，即模式t在所有序列中的PUB值之和。

c）maxper（t）、minper（t）、avgper（t）：模式t在輸入數(shù)據(jù)集中的最大周期值、最小周期值和平均周期值。

d）IsPHUSP：若模式t是周期高效用模式，就記為yes，否則記為no。

2.4 算法描述

IncPUS-Miner包括初始和增量?jī)蓚€(gè)階段。在初始階段，提出了算法PUS-Miner，實(shí)現(xiàn)從原始數(shù)據(jù)庫(kù)D中挖掘PHUSPs。當(dāng)加入增量數(shù)據(jù)后， IncPUS-Miner算法能夠有效處理增量數(shù)據(jù)，更新pu-tree結(jié)構(gòu)，挖掘出新的PHUSPs?，F(xiàn)設(shè)定閾值：minutil=30，maxPer=3，minPer=0，minAvg=0.5，maxAvg=2。根據(jù)表1的示例數(shù)據(jù)集，在圖1展現(xiàn)了所提出的增量挖掘方法的整體體系結(jié)構(gòu)。圖2展示了掃描原始數(shù)據(jù)集D后，模式t=〈a〉的UUL列表結(jié)構(gòu)示例。圖3顯示了掃描原始數(shù)據(jù)集D后構(gòu)建的pu-tree結(jié)構(gòu)，圖4是加入增量數(shù)據(jù)后的pu-tree結(jié)構(gòu)。

2.4.1 初始挖掘階段

如算法1所示，PUS-Miner算法的主要思路是構(gòu)建候選模式樹pu-tree，再以深度優(yōu)先搜索（DFS）的方式從原始數(shù)據(jù)集中提取具有高效用值的模式（PHUSP）。在處理每個(gè)節(jié)點(diǎn)t時(shí)，PUS-Miner首先檢查PUB（t）是否小于minutil。若PUB（t）小于minutil，那么PUS-Miner可以跳過(guò)節(jié)點(diǎn)t的擴(kuò)展步驟。當(dāng)PUB（t）大于或等于minutil時(shí)，PUS-Miner會(huì)掃描D中t的投影數(shù)據(jù)庫(kù)，以查找所有具有高EUB值的擴(kuò)展序列t′。對(duì)于每個(gè)t′，PUS-Miner會(huì)構(gòu)建相應(yīng)的節(jié)點(diǎn)結(jié)構(gòu)，將其作為t的子節(jié)點(diǎn)。如果t′是一個(gè)周期性高效用模式，PUS-Miner將其添加到PHUSP集中，并以t′為輸入遞歸調(diào)用PUS-Miner算法，以繼續(xù)擴(kuò)展t′。由于應(yīng)用了效用上界剪枝策略，算法PUS-Miner可以考慮較少的項(xiàng)目集，優(yōu)化了算法的時(shí)間復(fù)雜度。

算法1 PUS-Miner（t）

輸入：序列數(shù)據(jù)集D；模式t的投影數(shù)據(jù)集D|t；最小效用閾值ε；最大周期閾值maxPer；最小周期閾值minPer；最大平均周期閾值maxAvg；最小平均周期閾值minAvg。

輸出：PHUSPs的集合（PHUSP）。

1 scan D to calculate the utility values of all 1-pattern;

//掃描數(shù)據(jù)集D，計(jì)算所有1-模式的效用值

2 remove the utility values of 1-pattern less than ε;

//移除效用值小于ε的1-模式

3 initialize an set PHUSP; //初始化PHUSP集

4 scan D|t once to find extend-pattern，

add I-Extension items of t to i-list;

add S-Extension items of t to s-list;

//掃描模式t的投影數(shù)據(jù)集D，發(fā)現(xiàn)模式t的所有擴(kuò)展項(xiàng)

5 remove low EUB items from i-list and s-list； /*從擴(kuò)展模式列表i-list和s-list中刪除低EUB值的項(xiàng)*/

6 for each item i∈i-list and s-list do

//對(duì)于i-list和s-list中的每個(gè)項(xiàng)

7 if i∈i-list then //如果項(xiàng)i存在于i-list中

8 t′←〈t⊕i〉 //經(jīng)I-連接，模式t和項(xiàng)i組成新模式t′

9 if i∈s-list then //如果項(xiàng)i存在于s-list中

10 t′←〈ti〉 //經(jīng)S-連接，模式t和項(xiàng)i組成新模式t′

11 BuildNode（t′） and add t′ to pu-tree;

//構(gòu)造模式t′的樹節(jié)點(diǎn)，并添加它到結(jié)構(gòu)pu-tree中

12 if（maxper（t′）≤maxPer） then //剪枝策略3

13 if（PUB（t′）≥ε） //剪枝策略1

14 IsPeriodic（S（t′），minPer，maxPer，maxAvg，minAvg）

//調(diào)用IsPeriodic方法，判斷t′是否滿足其余周期度量

15 if true then //若滿足

16 insert t′ into PHUSP; //將模式t′存入PHUSP集

17 PUS-Miner（t′）; //遞歸調(diào)用PUS-Miner（t′），繼續(xù)擴(kuò)展t′

18 return;

2.4.2 增量挖掘階段

載入增量數(shù)據(jù)后，原始數(shù)據(jù)集D更新為D′。數(shù)據(jù)集D′可以看作兩部分：一部分是數(shù)據(jù)集更新時(shí)并沒有發(fā)生改變的序列，將這部分稱為無(wú)更新數(shù)據(jù)，記為NDB；另一部分是在數(shù)據(jù)集更新時(shí)有發(fā)生變化的序列，稱為更新數(shù)據(jù)，記為UDB。例如，在表1中，NDB包含序列S1、S2、S3，UDB包含序列S4、S5、S6、S7。另外，對(duì)于數(shù)據(jù)集更新后的每個(gè)模式t，都必須考慮以下兩種情況：

a）模式t在D和D′中都屬于周期高效用模式；

b）模式t在D中不屬于周期高效用模式，但在D′中屬于周期高效用模式。

算法2 IncPUS-Miner（t）

輸入：更新數(shù)據(jù)集D′；模式t的投影數(shù)據(jù)集D′|t；最小效用閾值ε；最大周期閾值maxPer；最小周期閾值minPer；最大平均周期閾值maxAvg；最小平均周期閾值minAvg；PHUSP集。

輸出：新的PHUSPs集（PHUSP）。

1 if all sequences in UDB|t are empty sequences then

2 return;//當(dāng)更新數(shù)據(jù)UDB為空時(shí)，返回

3 if PUBD′（t）<ε then

4 return; //當(dāng)模式t的PUB值小于ε時(shí)，返回

5 scan D′|t to calculate the EUB of all t’s extension sequences;

//掃描模式t的投影數(shù)據(jù)集D′，計(jì)算EUB（t′）

6 for each t’s extension sequences t′∈D′ do

7 if EUBD′（t′）≥ε then //剪枝策略2

8 if t′∈UDB then //若模式t′屬于更新數(shù)據(jù)

9 if t′∈pu-tree then//模式t′已存在于pu-tree結(jié)構(gòu)

10 UpdateNode（t′）;

//更新模式t′在pu-tree結(jié)構(gòu)中的相關(guān)信息

11 IncPUS-Miner （t′）;//遞歸調(diào)用IncPUS-Miner方法

12 else //若模式t′不存在于pu-tree結(jié)構(gòu)

13 BuildNode（t′） and add t′ to pu-tree;

//構(gòu)造模式t′的樹節(jié)點(diǎn)，并添加它到結(jié)構(gòu)pu-tree中

14 if （maxper（t′）≤maxPer） then //剪枝策略3

15 if（PUB（t′）≥ε） then //剪枝策略1

16 IsPeriodic（S（t′）， minPer， maxPer， maxAvg， minAvg）

//調(diào)用IsPeriodic方法，判斷t′是否滿足其余周期度量

17 if true then //若滿足

18 insert t′ into PHUSP; //將t′存入PHUSP集

19 PUS-Miner（t′）; /*遞歸調(diào)用PUS-Miner（t′），繼續(xù)擴(kuò)展模式t′*/

20 else

21 skip node t′;//跳過(guò)模式t′

2.4.3 IsPeriodic方法

在算法3中體現(xiàn)了IsPeriodic方法的具體操作，該方法用來(lái)判斷高效用模式是否具有周期性。IsPeriodic方法首先掃描模式t出現(xiàn)的序列集S（t），計(jì)算其最小周期值、最大周期值和平均周期值（第1～3行）。如果t是一個(gè)周期模式（第4行），則該過(guò)程返回true（第5行）；否則，返回false（第7行）。

算法3 IsPeriodic方法

輸入：模式t出現(xiàn)的序列集S（t）； 最大周期閾值maxPer；最小周期閾值minPer；最大平均周期閾值maxAvg；最小平均周期閾值 minAvg。

輸出：如果模式t是周期模式，返回true；否則，返回flase。

1 calculate maxper（t）=max（per（t））;//計(jì)算t的最大周期值

2 calculate minper（t）=min（per（t））;//計(jì)算t的最小周期值

3 calculate avgper（t） = |S|/（S（t）+1）;//計(jì)算t的平均周期值

4 if （maxper（t）≤maxPer & minper（t）≥minPer & minAvg≤avgper（t）≤maxAvg） then //判斷模式t是否滿足周期性條件

5 return true; //若滿足，返回true

6 else

7 return false; //若不滿足，返回false

3 實(shí)驗(yàn)評(píng)價(jià)

為了評(píng)估IncPUS-Miner算法的有效性，選擇了三種先進(jìn)的算法作為對(duì)比算法，分別為PHM算法［16］、PUSOM算法［17］和FHUQI- Miner算法［18］。

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)運(yùn)行環(huán)境為一臺(tái)1.90 GHz CPU和16 GB內(nèi)存，運(yùn)行64位微軟Windows 11的計(jì)算機(jī)，基于Java編寫。實(shí)驗(yàn)使用了4個(gè)真實(shí)數(shù)據(jù)集來(lái)評(píng)估算法的性能，其特征總結(jié)如表3所示。所有的數(shù)據(jù)集來(lái)自SPMF數(shù)據(jù)庫(kù)［19］。

Bible是稠密數(shù)據(jù)集，它包含36 369個(gè)序列和13 905個(gè)不同項(xiàng)目。Kosarak10k是稀疏數(shù)據(jù)集，它包含了從一個(gè)匈牙利新聞門戶網(wǎng)站收集的10 000個(gè)點(diǎn)擊流數(shù)據(jù)序列。Chess數(shù)據(jù)集和Retail數(shù)據(jù)集都是具有合成效用值的真實(shí)數(shù)據(jù)集。Chess數(shù)據(jù)集是稠密數(shù)據(jù)集，Retail數(shù)據(jù)集是高度稀疏的數(shù)據(jù)集。

3.2 增量挖掘結(jié)果的準(zhǔn)確性

本節(jié)對(duì)IncPUS-Miner算法增量挖掘的準(zhǔn)確性進(jìn)行了實(shí)驗(yàn)。選擇了稠密數(shù)據(jù)集Bible和稀疏數(shù)據(jù)集Kosarak10k，minutil分別設(shè)置為100 000和10 000，其余參數(shù)設(shè)為固定值（maxPer=100，maxAvg=20，minPer=minAvg=1）。

在實(shí)驗(yàn)中，每個(gè)數(shù)據(jù)集被分為5批、10批。IncPUS-Miner算法的挖掘結(jié)果如圖5所示。可以看出，隨著批次的加入，算法發(fā)現(xiàn)的PHUSPs數(shù)量也在增加，且相同數(shù)據(jù)集在不同批次下挖掘模式的最終數(shù)量是相等的。因此，IncPUS-Miner算法可以有效地處理增量數(shù)據(jù)，逐步挖掘所有PHUSPs。

3.3 所提剪枝策略的有效性

本組實(shí)驗(yàn)將提出的兩個(gè)新的效用上界（PUB，EUB）與前人提出的上界（PEU，RSU）［10］進(jìn)行對(duì)比，以評(píng)估其在模式挖掘中的性能。采用四個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，以確保比較的全面性和可靠性，如圖6所示。由于剪枝策略是針對(duì)模式效用提出的，故將最小效用閾值（minutil）作為X軸，挖掘過(guò)程中算法的運(yùn)行時(shí)間與內(nèi)存占用情況作為Y軸。通過(guò)分析實(shí)驗(yàn)結(jié)果，應(yīng)用所提剪枝策略的IncPUS-Miner算法在運(yùn)行時(shí)間和內(nèi)存占用方面都優(yōu)于應(yīng)用傳統(tǒng)效用上界的IncPUS-Miner算法。因此，所提的剪枝策略可以有效減少算法搜索空間，節(jié)省時(shí)間與內(nèi)存消耗。

3.4 參數(shù)對(duì)算法的影響及算法性能評(píng)估

在實(shí)際應(yīng)用中，為了合理設(shè)置IncPUS-Miner相關(guān)參數(shù)，需考慮數(shù)據(jù)集特征和研究問(wèn)題需求。在3.4.1節(jié)和3.4.2節(jié)中分別評(píng)估了參數(shù)minutil和maxPer對(duì)算法性能的影響。

3.4.1 minutil對(duì)算法效率的影響

本組實(shí)驗(yàn)旨在通過(guò)對(duì)每個(gè)數(shù)據(jù)集設(shè)置不同的最小效用閾值（即minutil）來(lái)評(píng)估算法的性能。實(shí)驗(yàn)將IncPUS-Miner算法與三個(gè)對(duì)比算法在數(shù)據(jù)集上進(jìn)行比較，并將參數(shù)minPer和minAvg設(shè)置為1，剩余參數(shù)maxPer和maxAvg在每個(gè)數(shù)據(jù)集都設(shè)定為經(jīng)驗(yàn)值，具體數(shù)值在圖7中體現(xiàn)。

通過(guò)分析圖7發(fā)現(xiàn)，隨著最小效用閾值的增加，滿足條件的項(xiàng)集逐漸減少，導(dǎo)致算法的運(yùn)行時(shí)間下降。值得注意的是，IncPUS-Miner算法在所有情況下的運(yùn)行時(shí)間均低于其他對(duì)比算法，這得益于提出的pu-tree結(jié)構(gòu)和剪枝策略，它們共同作用有效提高了挖掘效率。pu-tree結(jié)構(gòu)使算法能夠更快速且精準(zhǔn)地定位潛在高效項(xiàng)目集，而剪枝策略則進(jìn)一步減少了搜索空間，從而降低了計(jì)算成本。這兩個(gè)因素共同確保了IncPUS-Miner在不同最小效用閾值下都能取得較快的運(yùn)行速度。

與靜態(tài)挖掘PHUSPs算法相比，增量挖掘PHUSPs需要考慮新添加的事務(wù)，這更為復(fù)雜。通過(guò)比較四種算法在內(nèi)存使用方面的性能可以看出，IncPUS-Miner算法比其他三種算法消耗更少的內(nèi)存。在密集數(shù)據(jù)集中的PHUSPs數(shù)量相對(duì)較大，會(huì)生成更多的候選項(xiàng)集。因此，IncPUS-Miner算法在稀疏數(shù)據(jù)集上有更好的效果。

實(shí)驗(yàn)結(jié)果表明，IncPUS-Miner算法在處理各種數(shù)據(jù)集時(shí)都表現(xiàn)出優(yōu)越的性能，可以有效地逐步挖掘PHUSPs。

3.4.2 maxPer對(duì)算法效率的影響

本組實(shí)驗(yàn)研究了最大周期閾值（maxPer）對(duì)算法性能產(chǎn)生的影響。由于參數(shù)maxPer對(duì)FHUQI- Miner算法沒有影響，實(shí)驗(yàn)只對(duì)比了PHM、PUSOM和IncPUS-Miner三種算法，并記錄了它們?cè)诓煌琺axPer值下的運(yùn)行時(shí)間與內(nèi)存消耗情況。在圖8中呈現(xiàn)的實(shí)驗(yàn)結(jié)果可知，隨著maxPer值的增加，所有算法的運(yùn)行時(shí)間和內(nèi)存消耗均呈上升趨勢(shì)。這是因?yàn)殡S著maxPer值的增大，滿足周期性的高效用模式數(shù)量也隨之增加，使得算法需要處理更多的模式，因而在執(zhí)行過(guò)程中消耗更多的計(jì)算資源和內(nèi)存空間。對(duì)于特定問(wèn)題場(chǎng)景，通過(guò)合理設(shè)置maxPer值，可以在滿足性能需求的同時(shí)減少不必要的計(jì)算負(fù)擔(dān)。

通過(guò)比較不同算法的性能變化情況可以看出，IncPUS-Miner算法在各個(gè)maxPer值下表現(xiàn)出明顯的優(yōu)勢(shì)。具體而言，相對(duì)于其他兩種算法，IncPUS-Miner算法在高maxPer值情境下的運(yùn)行時(shí)間和內(nèi)存消耗增長(zhǎng)更為緩慢，這表明該算法在處理大規(guī)模周期模式的數(shù)據(jù)時(shí)具有更強(qiáng)的適應(yīng)性。

3.5 可擴(kuò)展性

該組實(shí)驗(yàn)選擇數(shù)據(jù)集Bible和Retail評(píng)估了數(shù)據(jù)庫(kù)大小及增量數(shù)據(jù)對(duì)IncPUS-Miner算法整體性能的影響。依據(jù)上述實(shí)驗(yàn)，將參數(shù)minPer和minAvg固定設(shè)置為1，并以25%的增量改變數(shù)據(jù)庫(kù)的大小，比較了四種算法在運(yùn)行時(shí)間和內(nèi)存消耗方面的性能，實(shí)驗(yàn)結(jié)果如圖9所示。從圖9可以看出，PHM算法在數(shù)據(jù)集上的運(yùn)行時(shí)間和內(nèi)存消耗明顯高于其他四種算法。這是因?yàn)镻HM算法采用的事務(wù)加權(quán)利用率（TWU）度量較為寬泛，使得算法需要處理更多的候選模式。另外，該算法在處理新數(shù)據(jù)時(shí)需要重新從頭開始挖掘模式，進(jìn)一步增加了運(yùn)行時(shí)間和內(nèi)存消耗的負(fù)擔(dān)。因此， PHM算法在處理增量數(shù)據(jù)挖掘任務(wù)時(shí)顯得不夠適用。與之相對(duì)，IncPUS-Miner算法在逐漸增大的序列數(shù)據(jù)集中展現(xiàn)出更為優(yōu)越的性能。這是因?yàn)镮ncPUS-Miner算法采用的pu-tree結(jié)構(gòu)在處理增量數(shù)據(jù)時(shí)不僅可以有效地維護(hù)和更新模式的信息，而且能夠支持算法在增量情境下的高效運(yùn)行；其次，算法采用的剪枝策略可以有效減少冗余計(jì)算，隨著數(shù)據(jù)集規(guī)模的增大，該剪枝策略能夠精確地確定哪些模式是無(wú)用的，從而更早地進(jìn)行剪枝，減少候選模式的數(shù)量，提高了算法在挖掘過(guò)程中的效率。

4 基因序列應(yīng)用分析

在生物醫(yī)學(xué)領(lǐng)域中，考慮到一些基因在特定疾病中的重要性以及在生物治療下的時(shí)間特性，通過(guò)PHUSPM分析有助于識(shí)別在特定疾病的發(fā)病機(jī)制中重要的基因調(diào)控序列模式。

表4呈現(xiàn)了一個(gè)基因序列數(shù)據(jù)集的實(shí)例。第一列標(biāo)識(shí)了六個(gè)肺炎患者的ID，其余列提供了在TP1、TP2、TP3、TP4這四個(gè)時(shí)間點(diǎn)上七種基因的基因表達(dá)值（內(nèi)部效用）?；虻耐獠啃в脩?yīng)該代表基因?qū)σl(fā)肺炎的重要性，這里使用DisGeNET提出的基因-疾病關(guān)聯(lián)評(píng)分（score）作為每個(gè)基因的外部效用，如表5所示。通過(guò)PUS-Miner和IncPUS-Miner算法進(jìn)行挖掘分析，提取挖掘結(jié)果中的前兩條PHUSPs記錄在表6中。

觀察表6的挖掘結(jié)果發(fā)現(xiàn)，IncPUS-Miner算法能夠及時(shí)捕捉到新的基因調(diào)控模式，這些模式很可能與肺炎的發(fā)生和發(fā)展密切相關(guān)。隨著病患者基因數(shù)據(jù)的積累，該算法允許實(shí)時(shí)更新模型，能夠?qū)崟r(shí)挖掘出在不同階段的肺炎中起關(guān)鍵作用的基因調(diào)控序列，從而更全面地理解基因在特定疾病發(fā)病機(jī)制中的作用。從總體結(jié)果來(lái)看，該算法能夠更有效地探索基因與疾病之間的關(guān)系，為生物醫(yī)學(xué)領(lǐng)域數(shù)據(jù)分析提供了有益的工具。

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

針對(duì)PHUSPs的增量挖掘問(wèn)題，設(shè)計(jì)了一種高效的算法IncPUS-Miner。IncPUS-Miner算法依賴于pu-tree結(jié)構(gòu)和更新效用列表（UUL）來(lái)促進(jìn)增量挖掘過(guò)程。pu-tree結(jié)構(gòu)可以有效處理新數(shù)據(jù)，UUL用來(lái)存儲(chǔ)簡(jiǎn)潔的輔助信息，以消除冗余計(jì)算，提高算法整體效率。此外，還介紹了兩個(gè)新的序列效用上界以及對(duì)應(yīng)的剪枝策略，有助于更準(zhǔn)確地確定無(wú)用模式，并在挖掘過(guò)程中更早地進(jìn)行剪枝，從而減少執(zhí)行時(shí)間和內(nèi)存使用。實(shí)驗(yàn)結(jié)果表明，IncPUS-Miner算法可以有效地從增量數(shù)據(jù)庫(kù)中挖掘PHUSPs，且在執(zhí)行時(shí)間和內(nèi)存使用方面優(yōu)于其他算法，該算法為解決PHUSPs的增量挖掘問(wèn)題提供了可靠且高效的解決方案，為應(yīng)對(duì)資源有限性的實(shí)際應(yīng)用場(chǎng)景提供了顯著的優(yōu)勢(shì)。未來(lái)研究將專注于自適應(yīng)策略，通過(guò)智能調(diào)整算法參數(shù)，更好地適應(yīng)不同數(shù)據(jù)分布的變化，從而提升算法在實(shí)時(shí)環(huán)境中的性能表現(xiàn)。

參考文獻(xiàn)：

［1］Fournier-Viger P， Lin J C W， Kiran R U， et al. A survey of sequential pattern mining［J］. Data Science and Pattern Recognition， 2017，1（1）： 54-77.

［2］吳軍， 歐陽(yáng)艾嘉， 張琳. 基于標(biāo)準(zhǔn)置換檢驗(yàn)的差異序列模式挖掘算法［J］. 計(jì)算機(jī)應(yīng)用研究， 2021， 38（3）： 710-713. （Wu Jun， Ouyang Aijia， Zhang Lin. Mining discriminative sequential patterns based on standard permutation testing［J］. Application Research of Computers， 2021， 38（3）： 710-713.）

［3］Gan Wensheng， Lin J C W， Zhang Jiexiong， et al. Fast utility mining on sequence data［J］. IEEE Trans on Cybernetics， 2021，51（2）： 487-500.

［4］Ahmed C F， Tanbeer S K， Jeong B S. A novel approach for mining high-utility sequential patterns in sequence databases［J］. ETRI Journal， 2010，32（5）： 676-686.

［5］Wang Junzhe， Huang J L， Chen Yicheng. On efficiently mining high utility sequential patterns［J］. Knowledge & Information Systems， 2016， 49（2）： 597-627.

［6］Han Meng， Shan Zhihui， Han Qiang. Incrementally updating high utility quantitative itemsets mining algorithm［J］. Journal of Intelligent & Fuzzy Systems， 2022， 43： 2435-2448.

［7］Yun U， Nam H， Lee G， et al. Efficient approach for incremental high utility pattern mining with indexed list structure［J］. Future Generation Computer Systems， 2019， 95： 221-239.

［8］Kim D， Yun U. Efficient algorithm for mining high average utility itemsets in incremental transaction databases［J］. Applied Intelligence， 2017， 47（1）： 114-131.

［9］Wang Junzhe， Huang J L. Incremental mining of high utility sequential patterns in incremental databases［C］//Proc of the 25th ACM International on Conference on Information and Knowledge Management. New York： ACM Press， 2016： 2341-2346.

［10］毛伊敏， 鄧千虎， 鄧小鴻， 等. 改進(jìn)的并行關(guān)聯(lián)規(guī)則增量挖掘算法［J］. 計(jì)算機(jī)應(yīng)用研究， 2021，38（10）： 2974-2980. （Mao Yimin， Deng Qianhu， Deng Xiaohong， et al. Improved parallel association rules incremental mining algorithm［J］. Application Research of Computers， 2021， 38（10）： 2974-2980.）

［11］Yun U， Ryang H， Lee G， et al. An efficient algorithm for mining high utility patterns from incremental databases with one database scan［J］. Knowledge-Based Systems， 2017， 124： 188-206.

［12］Wang Junzhe， Huang Jiunlong. On incremental high utility sequential pattern mining［J］. ACM Trans on Intelligent Systems and Technology， 2018， 9（5）： 1-26.

［13］Dinh T， Huynh V N， Le B. Mining periodic high utility sequential patterns［C］//Proc of Asian Conference on Intelligent Information and Database Systems. Cham： Springer， 2017： 545-555.

［14］Xie Shiyong， Zhao Long. An efficient algorithm for mining stable periodic high-utility sequential patterns［J］. Symmetry， 2022， 14（10）： 2032.

［15］Zihayat M， Davoudi H， An A. Top-k utility-based gene regulation sequential pattern discovery［C］//Proc of IEEE International Confe-rence on Bioinformatics and Biomedicine. Piscataway，NJ： IEEE Press， 2016： 266-273.

［16］Fournier-Viger P， Lin J C W， Duong Q H， et al. PHM： mining perio-dic high-utility itemsets［M］//Perner P.Advances in Data Mining. Cham： Springer， 2016： 64-79.

［17］Dinh D T， Le B， Fournier-Viger P， et al. An efficient algorithm for mining periodic high-utility sequential patterns［J］. Applied Intelligence， 2018， 48（12）： 4694-4714.

［18］Nouioua M， Fournier-Viger P， Wu C W， et al. FHUQI-Miner： fast high utility quantitative itemset mining［J］. Applied Intelligence， 2021， 51： 6785-6809.

［19］Fournier-Viger P， Gomariz A， Gueniche T， et al. SPMF： a Java open-source pattern mining library［J］. The Journal of Machine Learning Research， 2014，15（1）： 3389-3393.