摘 要：傳統(tǒng)周期模式挖掘忽略了模式本身的相關(guān)性和時(shí)效性，導(dǎo)致獲取到一些實(shí)用價(jià)值有限的弱相關(guān)且時(shí)效性較低的模式。因此，提出了新穎的基于時(shí)效性和相關(guān)性約束的周期模式挖掘方法（correlation and recency periodic frequent pattern－breadth first search，CRPFP－BFS）和（correlation and recency periodic frequent pattern－depth first search，CRPFP－DFS）。將給定的數(shù)據(jù)庫(kù)壓縮到一個(gè)列式結(jié)構(gòu)的列表CRPFP－List中，CRPFP－BFS和CRPFP－DFS 分別采用廣度優(yōu)先和深度優(yōu)先搜索方式遞歸地進(jìn)行挖掘，同時(shí)利用支持度、周期、時(shí)效性以及相關(guān)性剪枝策略減少搜索空間，以有效地發(fā)現(xiàn)相關(guān)時(shí)效周期模式。與當(dāng)前最先進(jìn)算法在密集數(shù)據(jù)集和稀疏數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果表明CRPFP－BFS和CRPFP－DFS具有較低的內(nèi)存占用和更高的運(yùn)行效率，并且具有良好的可擴(kuò)展性，其中CRPFP－DFS適合于內(nèi)存要求嚴(yán)格的情況，CRPFP－BFS在長(zhǎng)事務(wù)稀疏數(shù)據(jù)集下的運(yùn)行效率更高。

關(guān)鍵詞：頻繁模式挖掘； 周期模式； 相關(guān)時(shí)效周期模式； 相關(guān)性； 時(shí)效性

中圖分類(lèi)號(hào)：TP301.6文獻(xiàn)標(biāo)志碼： A文章編號(hào)：1001－3695（2024）04－016－1064－06

doi：10.19734/j.issn.1001－3695.2023.09.0397

Periodic pattern mining based on recency and correlation constraints

Yan Haibo， Xun Yaling， Ren Ziqian， Hou Yafei， Hu Xiaoying

Abstract：Traditional periodic pattern mining ignores the correlation and recency of the patterns， and therefore obtains some weakly correlated and recency patterns with limited practical value. To address the issue， this paper proposed novel periodic pattern mining methods based on recency and correlation constraints named CRPFP－BFS and CRPFP－DFS. By transforming a given database into a column－based structure CRPFP－List， CRPFP－BFS and CRPFP－DFS recursively mined its data using breadth－first and depth－first search， respectively. At the same time， CRPFP－BFS and CRPFP－DFS applied four pruning strategies based on support， period， recency and correlation to reduce the search space， thereby effectively discovering correlation recency periodic patterns. By comparing with the current state－of－the－art algorithms on dense and sparse datasets， and the experimental results show that the CRPFP－BFS and CRPFP－DFS have lower memory usage， higher operating efficiencies and good scalability. Among them， CRPFP－DFS is suitable for situations with strict memory requirements， and CRPFP－BFS performs more efficiently for long transaction sparse databases.

Key words：frequent pattern mining; periodic pattern; correlation recency periodic pattern; correlation; recency

0 引言

隨著工業(yè)發(fā)展，從工業(yè)生產(chǎn)到金融市場(chǎng)，從醫(yī)療監(jiān)測(cè)到交通管理，各種系統(tǒng)和設(shè)備產(chǎn)生了大量時(shí)序數(shù)據(jù)。時(shí)序數(shù)據(jù)中記錄了事件、過(guò)程和狀態(tài)的時(shí)間演化，蘊(yùn)涵著隱藏在時(shí)間軸上的模式、趨勢(shì)和規(guī)律。因此準(zhǔn)確而高效地從時(shí)序數(shù)據(jù)中分析隱藏的有價(jià)值的信息成為了備受關(guān)注的研究課題。周期模式作為存在于時(shí)序數(shù)據(jù)中的一類(lèi)重要特征規(guī)則，在GPS軌跡分析［1］、動(dòng)作分析［2］以及基因序列［3］研究等眾多領(lǐng)域都具有重要的實(shí)用意義。Ozden等人［4］為了挖掘循環(huán)關(guān)聯(lián)規(guī)則，將數(shù)據(jù)庫(kù)按時(shí)間維度分割成不重疊的子集，并研究了模式的周期性行為，為周期模式挖掘的產(chǎn)生奠定了基礎(chǔ)。Tanbeer等人［5］提出在事務(wù)數(shù)據(jù)庫(kù)中，如果連續(xù)出現(xiàn)的事務(wù)之間的間隔總是小于用戶定義的最大maxGap周期性，則該模式是周期性的。在此基礎(chǔ)上，Amphawan等人［6］提出了一種受Eclat啟發(fā)的算法MTKPP，其采用深度優(yōu)先搜索和垂直數(shù)據(jù)庫(kù)表示來(lái)枚舉所有周期性頻繁模式。為了解決挖掘效率問(wèn)題，F(xiàn)ournier等人［7］提出了一種稱(chēng)為局部周期模式的方法，它可被看作是傳統(tǒng)的周期性模式挖掘的擴(kuò)展。為了解決最大周期約束過(guò)于嚴(yán)格所帶來(lái)的限制，Kiran等人［8］設(shè)計(jì)了一種使用周期頻率來(lái)挖掘所有部分周期模式的算法。隨后，提出了一種使用平均周期的PFP挖掘算法［9］。但是這些方法對(duì)于動(dòng)態(tài)數(shù)據(jù)庫(kù)的處理效果并不令人滿意，因此荀亞玲等人［10］針對(duì)動(dòng)態(tài)數(shù)據(jù)庫(kù)中的部分周期模式挖掘計(jì)算復(fù)雜度過(guò)高和擴(kuò)展性差等問(wèn)題，提出了一種結(jié)合多尺度理論的部分周期模式挖掘算法。然而，這些方法挖掘出的模式仍受到嚴(yán)格約束，為了能夠識(shí)別可能不總是符合周期約束的周期模式，F(xiàn)ournier等人［11］通過(guò)引入穩(wěn)定性概念搜索具有穩(wěn)定性的周期模式，在此基礎(chǔ)上提出一種名為T(mén)SPIN［12］的算法，幫助用戶更加直觀地指定模式數(shù)量k，而不必設(shè)置最小支持度，避免了反復(fù)實(shí)驗(yàn)。

但是單序列挖掘算法缺乏對(duì)多元序列周期模式的挖掘能力。因此Fournier等人［13］提出了在多元時(shí)序中識(shí)別共有周期模式的解決辦法，定義了基于多元序列的周期標(biāo)準(zhǔn)差、序列周期比等屬性來(lái)挖掘多時(shí)間序列的共有周期。同時(shí)Fournier等人［14］在此基礎(chǔ)上加入Bond屬性，提出了多元時(shí)序的罕見(jiàn)相關(guān)周期模式的挖掘算法。但這些模型并不能處理不同數(shù)據(jù)庫(kù)中多元時(shí)間序列間的相關(guān)關(guān)系。因此，Xun等人［15］設(shè)計(jì)了一個(gè)稱(chēng)為相關(guān)部分周期的模式，相比于傳統(tǒng)的周期模式能夠很好地刻畫(huà)不同數(shù)據(jù)庫(kù)中多元時(shí)間序列間的相關(guān)關(guān)系。

從以上分析可知，現(xiàn)有的周期模式挖掘研究主要集中在周期模式的識(shí)別上，而忽略了所挖掘模式的內(nèi)在相關(guān)性［16］，且沒(méi)有考慮到時(shí)間衰減［17］對(duì)模式挖掘的影響。針對(duì)以上問(wèn)題，本文提出了一種適應(yīng)于時(shí)序數(shù)據(jù)庫(kù)周期模式挖掘的可擴(kuò)展的挖掘框架，該框架在模式挖掘過(guò)程中結(jié)合了模式的相關(guān)性和時(shí)效性，以發(fā)現(xiàn)更有價(jià)值的模式。本文的主要貢獻(xiàn)如下：

a）在周期頻繁模式挖掘框架中，引入了相關(guān)性和具有時(shí)間因素的時(shí)效性，提出了一種新的周期模式——相關(guān)時(shí)效周期模式。

b）設(shè)計(jì)了新的數(shù)據(jù)結(jié)構(gòu)CRPFP－List，適用于時(shí)序數(shù)據(jù)庫(kù)中相關(guān)時(shí)效周期模式挖掘。并提出相應(yīng)的挖掘算法（correlation and recency periodic frequent pattern－breadth first search，CRPFP－BFS）和（correlation and recency periodic frequent pattern－depth first search，CRPFP－DFS），其分別采用廣度優(yōu)先搜索和深度優(yōu)先搜索獲取完整的相關(guān)時(shí)效周期模式。同時(shí)算法采用依賴支持度、周期、時(shí)效性以及相關(guān)性的剪枝策略，有效減少了算法搜索空間，進(jìn)一步提升了挖掘效率。

1 相關(guān)定義

1.1 周期頻繁模式

2.2 剪枝策略

為減少相關(guān)時(shí)效周期模式挖掘過(guò)程中模式的搜索空間，利用模式在支持度、時(shí)效性、相關(guān)性和周期性方面具有的反單調(diào)性或者單調(diào)性，提出了有效的剪枝策略，以進(jìn)一步提高算法的挖掘效率。其中Xk為k模式，Ts（Xk）為模式Xk的時(shí)間戳集合，Xk+1為Xk的超集k+1模式，Ts（Xk+1）為模式Xk+1的時(shí)間戳集合，因此有XkXk+1，Ts（Xk+1）Ts（Xk）。

a）支持度剪枝策略。如果模式Xk的sup小于最小支持度minSup，則模式Xk的任何擴(kuò)展模式都不滿足定義7而被剪枝，即minSup具有反單調(diào)性。

證明

對(duì)于任意的模式Xk和其超集Xk+1，即XkXk+ sup（Xk）=|Ts（Xk）|，sup（Xk+1）=|Ts（Xk+1）|，因此sup（Xk+1）≤ sup（Xk）＜minSup。說(shuō)明支持度剪枝策略滿足反單調(diào)性，模式Xk的任何擴(kuò)展模式都不滿足定義7而被剪枝。

b） 周期剪枝策略。如果模式Xk的周期per大于最大周期maxPer，則模式Xk的任何擴(kuò)展模式都無(wú)法滿足定義7而被剪枝。

證明

如果per（Xk）≤per（Xk+1）且per（Xk）＞maxPer，則對(duì)于模式Xk的擴(kuò)展模式Xk+1有per（Xk+1）＞maxPer。因此，周期剪枝策略具有單調(diào)性，模式Xk的任何擴(kuò)展模式都將不滿足定義7而被剪枝。

c）時(shí)效性剪枝策略。如果模式Xk的rec小于最小時(shí)效性minRec，則模式Xk的任何擴(kuò)展模式都無(wú)法滿足定義7而被剪枝，因此時(shí)效性具有反單調(diào)性。

證明

給定Xk和其超集Xk+1，即XkXk+1，它們的時(shí)效性定義分別為 rec（Xk）=∑XkTs∧Ts∈TDBrec（Xk，Ts），rec（Xk+1）=∑Xk+1Ts∧Ts∈TDBrec（Xk+1，Ts），因此rec（Xk+1）≤rec（Xk）＜minRec。 由此可以看出，時(shí)效性剪枝策略滿足反單調(diào)性，模式Xk的任何擴(kuò)展模式都不滿足定義7而被剪枝。

d）相關(guān)性剪枝策略。如果模式Xk的相關(guān)性Kulc（Xk）小于最小相關(guān)性minCor，且TDB中的模式按支持度升序排序，則模式Xk+1的任何擴(kuò)展模式都不滿足定義7而被剪枝，具體證明見(jiàn)文獻(xiàn)［17］。

2.3 一模式挖掘算法

算法1描述了使用CRPFP－List挖掘一模式的過(guò)程。使用如表1所示的數(shù)據(jù)庫(kù)來(lái)描述該算法的流程。令minSup=3，maxPer=3，minRec=2且minCor=0.5。

算法1 一模式挖掘

輸入：時(shí)序數(shù)據(jù)庫(kù)TDB；最小支持度minSup；最大周期maxPer；最小時(shí)效性minRec；最小相關(guān)性minCor；CRPFP－List=。

輸出：CRPFP－List。

1 for each transaction ts∈TDB do

2 set tscur =ts; //初始化tscur為當(dāng)前時(shí)間戳ts

3for each item i ∈ tscur.X do

4 if i not in CRPFP－List then /*對(duì)不在CRPFP－List中的項(xiàng)目i的操作*/

5 insert i and tscur into the CRPFP－List /*將項(xiàng)目i和時(shí)間戳tscur插入到CRPFP－List中*/

6 TSl ［i］=tscur

7 per［i］=（tscur-tsinitial）

8 else //對(duì)已經(jīng)在CRPFP－List中的項(xiàng)目i的操作

9 Add i.tscur in the CRPFP－List

10 per［i］=max（per［i］， （tscur-TSl［i］））

11 TSl ［i］=scur

12 for each item i in CRPFP－List do /*針對(duì)CRPFP－List中的所有項(xiàng)目進(jìn)行循環(huán)*/

13 sup［i］= length（TS－List（i）） //支持度計(jì)算

14 rec［i］=calculate（TS－List（i））//時(shí)效性計(jì)算

15if sup［i］lt;minSup or rec［i］lt;minRec or Kulc［i］lt;minCor then

16 prune i from the CRPFP－List //從CRPFP－List中剪枝項(xiàng)目i

17 else

18 calculate per［i］=max（per［i］，（tsfinal-TSl［i］））

19 if per［i］gt;maxPer then

20 prune i from the CRPFP－List

21 sort the remaining items in the CRPFP－List in ascending order of their support

22 call CRPFP－BFS/DFS（CRPFP－List） /*調(diào)用CRPFP－BFS或CRPFP－DFS 函數(shù)*/

對(duì)第一條事務(wù)，ts=1在CRPFP－List中分別插入項(xiàng)目a，b，c，e，f。這些項(xiàng)目的TS－List設(shè)置為1，per和TSl分別設(shè)置為1和1（算法1的第6、7行）。對(duì)第二條事務(wù)，其中ts=2，將新項(xiàng)目d插入到CRPFP－List中，在其TS－List中添加時(shí)間戳2（=tscur）。同時(shí)，將per和TSl值分別設(shè)定為2和2。另一方面，將2（=tscur）添加到已經(jīng)存在的項(xiàng)目的TS－List中，其中per和TSl分別被設(shè)置為1和2（算法1的第9～11行）。對(duì)其余事務(wù)重復(fù)類(lèi)似的過(guò)程。模式e和f從CRPFP－List中被修剪（使用周期剪枝策略），因?yàn)槠渲芷诖笥谟脩糁付ǖ膍axPer（算法1中的第15～20行）。CRPFP－List中的剩余項(xiàng)目被認(rèn)為是相關(guān)時(shí)效周期模式，并按其支持度升序排序（算法1中的第21行）。表4中展示了經(jīng)過(guò)排序之后生成的最終CRPFP－List。

算法2描述了采用廣度優(yōu)先搜索方式尋找所有相關(guān)時(shí)效周期模式的過(guò)程。使用表4的CRPFP－List描述算法的流程。

從項(xiàng)目d開(kāi)始，它是CRPF－List中的第一個(gè)項(xiàng)目（算法2第2行）。由于d是相關(guān)時(shí)效周期模式，移動(dòng)到其子節(jié)點(diǎn)da，并通過(guò)執(zhí)行d和a的TS－List的交集來(lái)生成其TS－List，即TSda=TSd∩TSa（算法2第3、4行）。記錄da的時(shí)間戳，驗(yàn)證da是否為冗余模式，若為冗余模式則根據(jù)相應(yīng)的剪枝策略剪枝，減少冗余模式的生成（算法2第5行）。da是相關(guān)時(shí)效周期模式，移動(dòng)到a后面的c，并執(zhí)行d和c的TS－List的交集生成其TS－List，即TSdc=TSd∩TSc。記錄dc的時(shí)間戳，并將其識(shí)別為相關(guān)時(shí)效周期模式。在當(dāng)前一模式的CRPFP－List遞歸完成后，進(jìn)入（k+1）模式的遞歸（算法2第7行）。對(duì)搜索空間中的剩余節(jié)點(diǎn)重復(fù)類(lèi)似的過(guò)程，以找到所有相關(guān)時(shí)效周期模式。

2.5 CRPFP－DFS算法

算法3 相關(guān)時(shí)效周期模式挖掘CRPFP－DFS

輸入：CRPFP－List；最小支持度minSup；最大周期maxPer；最小時(shí)效性minRec；最小相關(guān)性minCor。

輸出：所有的相關(guān)時(shí)效周期模式。

算法3描述了采用深度優(yōu)先搜索方式尋找所有相關(guān)時(shí)效周期模式的過(guò)程。使用表4的CRPFP－List描述算法的流程。

從項(xiàng)目d開(kāi)始，它是CRPFP－List中的第一個(gè)項(xiàng)目（算法3第2行）。從其子節(jié)點(diǎn)da開(kāi)始，通過(guò)d和a的TS－List的交集生成其TS－List，即TSda=TSd∩Ta（算法3第3、4行）。驗(yàn)證模式da是否為冗余模式（算法3第5行）。移動(dòng)到a后面的c，生成其TS－List，即TSdc將其識(shí)別為相關(guān)時(shí)效周期模式。此時(shí)項(xiàng)目d與b生成其TS－List，即TSdb，通過(guò)驗(yàn)證模式db的時(shí)效性rec=1.725小于最小時(shí)效性2，根據(jù)時(shí)效性剪枝策略模式db是冗余模式，搜索空間中db及其子節(jié)點(diǎn)都應(yīng)被剪除。在當(dāng)前模式的CRPFP－List遞歸完成后，進(jìn)入（k+1）模式的遞歸（算法2中的第7行），即對(duì)da、dc進(jìn)行遞歸。對(duì)搜索空間中的剩余節(jié)點(diǎn)重復(fù)類(lèi)似的過(guò)程，以找到所有相關(guān)時(shí)效周期模式。

3 實(shí)驗(yàn)結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

為了評(píng)估本文算法的效率，所有實(shí)驗(yàn)都在一臺(tái)配置為Intel CoreTM i5－7300HQ CPU @ 2.50 GHz、16 GB RAM和64位Microsoft Windows 10操作系統(tǒng)的個(gè)人計(jì)算機(jī)上基于Python 3.9實(shí)現(xiàn)。本文選擇四個(gè)稀疏數(shù)據(jù)集和一個(gè)密集數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。以上所有數(shù)據(jù)集均可從序列模式挖掘框架SPMF［18］下載。這些數(shù)據(jù)集的詳細(xì)信息如表5所示。對(duì)比算法選擇了未考慮時(shí)效性與相關(guān)性的PFP－growth+ +［19］、PS－growth［20］和PF－ECLAT［21］算法。

3.2 不同參數(shù)對(duì)算法效率的影響評(píng)估

3.2.1 minCor對(duì)算法效率的影響

該組實(shí)驗(yàn)驗(yàn)證了minCor參數(shù)對(duì)算法性能的影響。在實(shí)驗(yàn)中，T10I4D100K、BMS－WebView－1、mushroom和retail中的minSup分別設(shè)置為0.1%、0.07%、12%、0.09%，maxPer設(shè)置為5%、20%、30%、14%，minRec為30%、3.1%、20%、20%。實(shí)驗(yàn)結(jié)果如圖1以及表6所示。折線圖表示這兩種算法的運(yùn)行時(shí)間，柱狀圖表示算法的內(nèi)存占用。增加minCor通常會(huì)減少運(yùn)行時(shí)間。隨著minCor的增加，minCor對(duì)模式的過(guò)濾會(huì)更加嚴(yán)格，導(dǎo)致更多的模式被拋棄，因此模式的數(shù)量會(huì)明顯減少。與此同時(shí)兩種算法的內(nèi)存消耗會(huì)隨之減少，因?yàn)閙inCor被設(shè)置為更大值時(shí)，更少的模式被挖掘，從而減少了內(nèi)存消耗。同時(shí)在這四個(gè)數(shù)據(jù)集中，CRPFP－DFS的內(nèi)存消耗始終小于CRPFP－BFS。在密集數(shù)據(jù)集mushroom中，CRPFP－BFS的內(nèi)存消耗極高，由于CRPFP－BFS采用廣度優(yōu)先的方式逐層的廣度搜索模式的組合。但是，需要存儲(chǔ)每個(gè)層級(jí)的模式，在數(shù)據(jù)集中存在大量符合條件的模式時(shí)，可能會(huì)占用較多的內(nèi)存。因此在密集數(shù)據(jù)集中，這樣的方式可能導(dǎo)致模式的數(shù)量爆炸，增大算法的內(nèi)存消耗，使算法難以應(yīng)用于大規(guī)模數(shù)據(jù)集。

3.2.2 minRec對(duì)算法效率的影響

該組實(shí)驗(yàn)驗(yàn)證了minRec參數(shù)對(duì)算法性能的影響。在實(shí)驗(yàn)中，T10I4D100K，BMS－WebView－1，mushroom和retail中的minSup分別設(shè)置為0.1%、0.07%、12%、0.09%、maxPer為5%、20%、30%、14%，minCor為30%、4%、12%、10%。實(shí)驗(yàn)結(jié)果如圖2以及表7所示。折線圖表示這兩種算法的運(yùn)行時(shí)間，柱狀圖表示算法的內(nèi)存占用。隨著minRec的增加，不同數(shù)據(jù)集中挖掘的模式都呈現(xiàn)減少趨勢(shì)。兩種算法的時(shí)間消耗持續(xù)下降，但是在BMS－WebView－1中CRPFP－DFS的時(shí)間表現(xiàn)明顯更好，同時(shí)在任意數(shù)據(jù)集中CRPFP－DFS的內(nèi)存消耗都更小。因?yàn)樯疃葍?yōu)先策略優(yōu)先探索可能的組合路徑，直到不能生成模式為止，然后回溯到上一個(gè)狀態(tài)繼續(xù)挖掘。這種方式的特點(diǎn)是對(duì)內(nèi)存需求較小，因?yàn)橐淮沃恍枰幚硪粭l組合路徑。

3.3 算法性能評(píng)估與分析

3.3.1 maxPer對(duì)算法性能的影響

該組實(shí)驗(yàn)通過(guò)改變maxPer來(lái)評(píng)估算法的性能表現(xiàn)。在實(shí)驗(yàn)中，BMS－WebView－1和mushroom中的minSup分別設(shè)置為0.07%、12%、minCor為4%、12%，minRec為3.1%、20%，其中minCor和minRec的參數(shù)根據(jù)3.2節(jié)中實(shí)驗(yàn)進(jìn)行設(shè)定。圖3中折線圖表示算法的運(yùn)行時(shí)間，柱狀圖表示模式數(shù)量。實(shí)驗(yàn)結(jié)果如圖3、4所示。從圖3可以看出，在密集數(shù)據(jù)集mushroom中CRPFP－BFS和CRPFP－DFS的時(shí)間表現(xiàn)相對(duì)于PFP－growth+ +和PS－growth來(lái)說(shuō)并不好，僅優(yōu)于PF－ECLAT。在密集數(shù)據(jù)集mushroom中，可能會(huì)有很多模式同時(shí)出現(xiàn)在多個(gè)事務(wù)中導(dǎo)致CRPFP－List記錄過(guò)多的信息，增大了算法處理的數(shù)據(jù)量，影響其效率。同時(shí)模式增長(zhǎng)類(lèi)算法通過(guò)構(gòu)建模式樹(shù)并利用其壓縮性質(zhì)，這種壓縮的數(shù)據(jù)結(jié)構(gòu)使得模式增長(zhǎng)類(lèi)算法在處理密集數(shù)據(jù)集時(shí)具有更好的效率。而在稀疏數(shù)據(jù)集中，CRPFP－DFS相對(duì)于其他算法在時(shí)間上具有一定優(yōu)勢(shì)。從圖4可以得知，CRPFP－DFS在BMS－WebView－1比所有其他最先進(jìn)的算法消耗更少的內(nèi)存，隨著maxPer值的增大，差異也變得更加顯著。

3.3.2 minSup對(duì)算法性能的影響

本組實(shí)驗(yàn)通過(guò)改變minSup，評(píng)估CRPFP－BFS、CRPFP－DFS、PFP－growth+ +、PS－growth和PF－ECLAT算法的性能。在實(shí)驗(yàn)中，BMS－WebView－1和mushroom中的maxPer分別設(shè)置為20%、30%，minCor為4%、12%，minRec為3.1%、20%。圖5中折線圖表示算法的運(yùn)行時(shí)間，柱狀圖表示模式數(shù)量。從圖5中可以看出， 隨著minSup的增大，五種算法的時(shí)間消耗都呈下降趨勢(shì)，對(duì)BMS－WebView－1這樣的短事務(wù)數(shù)據(jù)集，CRPFP－DFS算法搜索空間較小，遞歸深度相對(duì)較淺，不會(huì)產(chǎn)生過(guò)多的遞歸調(diào)用，能夠更快地遍歷所有可能的項(xiàng)集組合，因此時(shí)間表現(xiàn)極好。從圖6可以看到，CRPFP－DFS在BMS－WebView－1數(shù)據(jù)集中比所有其他算法消耗更少的內(nèi)存，因?yàn)樗谒阉鳂?shù)的深度方向上進(jìn)行遞歸只需要保存當(dāng)前分支路徑上的信息，而不是整個(gè)搜索空間的結(jié)構(gòu)，有效地減少了內(nèi)存占用，從而具有良好的內(nèi)存優(yōu)勢(shì)。

根據(jù)圖3和5的實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，無(wú)論是在稀疏數(shù)據(jù)集還是在密集數(shù)據(jù)集中，相關(guān)時(shí)效周期模式的數(shù)量總是會(huì)小于minSup和maxPer下的周期模式的數(shù)量。這說(shuō)明當(dāng)僅考慮模式的minSup和maxPer時(shí)，會(huì)挖掘出大量的周期模式，但其中只有部分模式具有強(qiáng)相關(guān)性和時(shí)效性，其余模式則是冗余的。

此外，在實(shí)際應(yīng)用中，大量的周期模式可能無(wú)法為決策者提供有力的數(shù)據(jù)支持。這些模式具有較差的時(shí)效性，包含大量過(guò)期信息，并且缺乏相關(guān)性的聯(lián)系。因此，這些模式并不符合現(xiàn)實(shí)應(yīng)用中的興趣模式，所以，相關(guān)時(shí)效周期模式的挖掘被認(rèn)為比周期模式更具價(jià)值。

3.4 算法可擴(kuò)展性測(cè)試

本組實(shí)驗(yàn)評(píng)估了所提算法在運(yùn)行時(shí)間和內(nèi)存需求上的可擴(kuò)展性，實(shí)驗(yàn)采用真實(shí)世界的數(shù)據(jù)集Kosarak，由于其包含大量不同的項(xiàng)目和交易，將數(shù)據(jù)集分為五個(gè)部分，再將每個(gè)部分添加到前一部分后評(píng)估算法的可擴(kuò)展性。圖7展示出了當(dāng)minSup=0.1%，maxPer=1%，minCor=60%且minRec=60%時(shí)的實(shí)驗(yàn)結(jié)果。

圖中線條表示該算法的運(yùn)行時(shí)間，柱狀圖表示算法的內(nèi)存占用。從圖中可以得出以下兩點(diǎn)結(jié)論：a）很明顯兩種算法的運(yùn)行時(shí)間以及內(nèi)存需求隨著數(shù)據(jù)集的增長(zhǎng)幾乎都呈線性增加；b）對(duì)于任何給定的數(shù)據(jù)集大小，相比于CRPFP－DFS算法，CRPFP－BFS會(huì)消耗更少的運(yùn)行時(shí)間。因?yàn)楫?dāng)事務(wù)數(shù)量增加時(shí)，minSup、maxPer、minRec及minCor約束條件放松，搜索空間變大，算法可以找到更多的模式，從而消耗更多的時(shí)間及內(nèi)存占用。

4 電影推薦應(yīng)用分析

電影推薦是一種新興的模式挖掘應(yīng)用，通過(guò)挖掘分析有助于電影院了解觀眾的觀影偏好、優(yōu)化排片場(chǎng)次，以提高影院的效益。因此，以歐洲真實(shí)影院的數(shù)據(jù)記錄為例，部分記錄整理如表8所示。通過(guò)使用CRPFP－BFS和CRPFP－DFS算法進(jìn)行了挖掘分析，挖掘結(jié)果如表9所示。

從表9中可以看出，帶有action和adventure屬性的影片之間存在著最高的相關(guān)性，同時(shí)也具有最高的觀看時(shí)效性。這說(shuō)明具有action和adventure屬性的影片在市場(chǎng)上是主要的觀影選擇，這一發(fā)現(xiàn)與歐美影片的拍攝趨勢(shì)相符，驗(yàn)證了CRPFP－BFS和CRPFP－DFS算法的有效性。相較于傳統(tǒng)周期模式挖掘算法僅能根據(jù)支持度及周期信息進(jìn)行推薦，本文算法能根據(jù)周期模式的相關(guān)性及時(shí)效性，挖掘出更有價(jià)值的相關(guān)時(shí)效周期模式。例如：具有war及adventure屬性的影片的相關(guān)性及觀看時(shí)效性均未達(dá)到給定閾值而被剪枝，而具有sci－fi、action及adventure這三類(lèi)屬性的影片的相關(guān)性均高于0.75，對(duì)應(yīng)的觀看時(shí)效性均高于5.5。從時(shí)效性及相關(guān)性來(lái)分析，說(shuō)明觀眾近期更傾向于觀看帶有sci－fi、action和adventure這三類(lèi)屬性的影片。因此針對(duì)該影院的經(jīng)營(yíng)可以作出兩點(diǎn)建議：首先，建議增加帶有action和adventure屬性影片的排片場(chǎng)次，同時(shí)推出針對(duì)此類(lèi)影片的折扣套餐以提高用戶粘性;其次，應(yīng)該增加引進(jìn)同時(shí)具有sci－fi、action、adventure多屬性影片的數(shù)量，以適應(yīng)觀眾觀影偏好的變化。

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

本文致力于在時(shí)序數(shù)據(jù)庫(kù)中挖掘相關(guān)時(shí)效周期模式，設(shè)計(jì)了適用于相關(guān)時(shí)效周期模式挖掘的CRPFP－List結(jié)構(gòu)，提出兩種有效的算法CRPFP－BFS和CRPFP－DFS，利用minSup、maxPer、minRec及minCor剪枝策略消除冗余模式，有效減少了模式搜索空間，進(jìn)一步提升了挖掘效率。通過(guò)與其他算法在不同的數(shù)據(jù)集上的實(shí)驗(yàn)，驗(yàn)證了CRPFP－BFS和CRPFP－DFS的性能。實(shí)驗(yàn)分析表明，CRPFP－BFS和CRPFP－DFS在相關(guān)時(shí)效周期模式挖掘方面表現(xiàn)出了較高的性能，CRPFP－DFS表現(xiàn)出了良好的內(nèi)存占用效率，而CRPFP－BFS在時(shí)間消耗上相較于CRPFP－DFS在長(zhǎng)事務(wù)稀疏數(shù)據(jù)集中具有一定優(yōu)勢(shì)。未來(lái)將繼續(xù)致力于開(kāi)發(fā)更高效的并行和分布式算法，以提高處理大規(guī)模時(shí)序數(shù)據(jù)庫(kù)的能力。

參考文獻(xiàn)：

［1］Zhang Dongzhi， Lee K， Lee I. Mining hierarchical semantic periodic patterns from GPS－collected spatio－temporal trajectories［J］.Expert Systems with Applications ， 2019，122 ： 85－101.

［2］Vitagliano E， Vitale E， Russo G， et al. Analysis of the periodic component of vertical land motion in the Po Delta （Northern Italy） by GNSS and hydrological data［J］.Remote Sensing ， 2022， 14 （5）： 1126.

［3］Zhao Chengchen， Xiu Wenchao， Hua Yuwei， et al. CStreet： a computed Cell State trajectory inference method for time－series single－cell RNA sequencing data［J］.Bioinformatics，202 37 （21）： 3774－3780.

［4］Ozden B，Ramaswamy S，Silberschatz A. Cyclic association rules［C］//Proc of the 14th International Conference on Data Engineering. Pisca－taway，NJ： IEEE Press， 1998： 412－421.

［5］Tanbeer S K， Ahmed C F， Jeong B S， et al. Discovering periodic－frequent patterns in transactional databases［C］//Proc of the 13th Pacific－Asia Conference on Knowledge Discovery and Data Mining. Berlin： Springer， 2009： 242－253.

［6］Amphawan K， Lenca P， Surarerks A. Mining top－k periodic－frequent pattern from transactional databases without support threshold［C］//Proc of the 3rd International Conference on Advances in Information Technology. Berlin： Springer， 2009： 18－29.

［7］Fournier V P， Yang Peng， Kiran R U， et al. Mining local periodic patterns in a discrete sequence［J］.Information Sciences ， 202 544 ： 519－548.

［8］Kiran R U， Shang H， Toyoda M， et al. Discovering partial periodic itemsets in temporal databases［C］//Proc of the 29th International Conference on Scientific and Statistical Database Management. New York： ACM Press， 2017： 1－6.

［9］Fournier V P， Lin Chunwei， Duong Q H， et al. PFPM： discovering periodic frequent patterns with novel periodicity measures［C］//Proc of the 2nd Czech－China Scientific Conference. 2017： 23－35.

［10］荀亞玲， 王林青， 蔡江輝， 等. 基于多尺度的時(shí)序數(shù)據(jù)部分周期模式增量挖掘［J］. 計(jì)算機(jī)應(yīng)用， 2023， 43 （2）： 391－397. （Xun Yaling， Wang Linqing， Cai Jianghui， et al. Partial periodic pattern incremental mining of time series data based on multi－scale［J］.Journal of Computer Applications ， 2023， 43 （2）： 391－397.）

［11］Fournier V P， Yang Peng， Lin Chunwei， et al. Discovering stable periodic－frequent patterns in transactional data［C］//Advances and Trends in Artificial Intelligence. From Theory to Practice： Proc of the 32nd International Conference on Industrial， Engineering and Other Applications of Applied Intelligent Systems. Cham： Springer， 2019： 230－244.

［12］Fournier V P， Wang Ying， Yang Peng， et al. TSPIN： mining top－k stable periodic patterns［J］.Applied Intelligence ， 2022， 52 （6）： 6917－6938.

［13］Fournier V P， Li Zhitian， Lin Chunwei， et al. Efficient algorithms to identify periodic patterns in multiple sequences［J］.Information Sciences ， 2019， 489 ： 205－226.

［14］Fournier V P， Yang Peng， Li Zhitian， et al. Discovering rare correlated periodic patterns in multiple sequences［J］.Data amp; Knowledge Engineering ， 2020， 126 ： 101733.

［15］Xun Yaling， Wang Linqing， Yang Haifeng， et al. Mining relevant partial periodic pattern of multi－source time series data［J］.Information Sciences，2022，615 ： 638－656.

［16］Gan Wensheng， Lin Chunwei， Fournier V P， et al. Extracting non－redundant correlated purchase behaviors by utility measure［J］.Knowledge－Based Systems ， 2018， 143 ： 30－41.

［17］Qi Yanlin， Zhang Xiaojie， Chen Guoting， et al. Mining periodic trends via closed high utility patterns［J］.Expert Systems with Applications，2023，228：120356.

［18］Fournier V P， Zhang Yimin， Lin Chunwei， et al. Mining local and peak high utility itemsets［J］.Information Sciences，2019，481 ： 344－367.

［19］Kiran R U， Kitsuregawa M， Reddy P K. Efficient discovery of periodic－frequent patterns in very large databases［J］.Journal of Systems and Software ， 2016， 112 ： 110－121.

［20］Kiran R U， Anirudh Saideep C， et al. Finding periodic－frequent patterns in temporal databases using periodic summaries［J］.Data Science and Pattern Recognition ， 2019， 3 （2）： 24－46.

［21］Ravikumar P， Likhitha P， Venus V R， et al. Efficient discovery of periodic－frequent patterns in columnar temporal databases［J］.Electronics ， 202 10 （12）： 1478.

收稿日期：2023－09－05；修回日期：2023－10－31基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（62272336）

作者簡(jiǎn)介：閆海博（1998—），男，河南內(nèi)鄉(xiāng)人，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘與并行計(jì)算；荀亞玲（1980—），女（通信作者），山西臨汾人，教授，碩導(dǎo)，博士，主要研究方向?yàn)閿?shù)據(jù)挖掘與并行計(jì)算（xunyl55@126.com）；任姿芊（1999—），女，山西運(yùn)城人，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘與并行計(jì)算；侯亞飛（1999—），男，河北保定人，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘與并行計(jì)算；胡曉瑩（1996—），女，山西平陸人，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘與并行計(jì)算．