基于時效性和相關(guān)性約束的周期模式挖掘

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

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

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

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

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

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

b）設(shè)計(jì)了新的數(shù)據(jù)結(jié)構(gòu)CRPFP－List，適用于時序數(shù)據(jù)庫中相關(guān)時效周期模式挖掘。并提出相應(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)時效周期模式。同時算法采用依賴支持度、周期、時效性以及相關(guān)性的剪枝策略，有效減少了算法搜索空間，進(jìn)一步提升了挖掘效率。

1 相關(guān)定義

1.1 周期頻繁模式

2.2 剪枝策略

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

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

證明

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

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

證明

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

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

證明

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

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

2.3 一模式挖掘算法

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

算法1 一模式挖掘

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

輸出：CRPFP－List。

1 for each transaction ts∈TDB do

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

3for each item i ∈ tscur.X do

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

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

6 TSl ［i］=tscur

7 per［i］=（tscur-tsinitial）

8 else //對已經(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 /*針對CRPFP－List中的所有項(xiàng)目進(jìn)行循環(huán)*/

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

14 rec［i］=calculate（TS－List（i））//時效性計(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ù)*/

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

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

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

2.5 CRPFP－DFS算法

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

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

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

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

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

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

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

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

3.2 不同參數(shù)對算法效率的影響評估

3.2.1 minCor對算法效率的影響

該組實(shí)驗(yàn)驗(yàn)證了minCor參數(shù)對算法性能的影響。在實(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)行時間，柱狀圖表示算法的內(nèi)存占用。增加minCor通常會減少運(yùn)行時間。隨著minCor的增加，minCor對模式的過濾會更加嚴(yán)格，導(dǎo)致更多的模式被拋棄，因此模式的數(shù)量會明顯減少。與此同時兩種算法的內(nèi)存消耗會隨之減少，因?yàn)閙inCor被設(shè)置為更大值時，更少的模式被挖掘，從而減少了內(nèi)存消耗。同時在這四個數(shù)據(jù)集中，CRPFP－DFS的內(nèi)存消耗始終小于CRPFP－BFS。在密集數(shù)據(jù)集mushroom中，CRPFP－BFS的內(nèi)存消耗極高，由于CRPFP－BFS采用廣度優(yōu)先的方式逐層的廣度搜索模式的組合。但是，需要存儲每個層級的模式，在數(shù)據(jù)集中存在大量符合條件的模式時，可能會占用較多的內(nèi)存。因此在密集數(shù)據(jù)集中，這樣的方式可能導(dǎo)致模式的數(shù)量爆炸，增大算法的內(nèi)存消耗，使算法難以應(yīng)用于大規(guī)模數(shù)據(jù)集。

3.2.2 minRec對算法效率的影響

該組實(shí)驗(yàn)驗(yàn)證了minRec參數(shù)對算法性能的影響。在實(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)行時間，柱狀圖表示算法的內(nèi)存占用。隨著minRec的增加，不同數(shù)據(jù)集中挖掘的模式都呈現(xiàn)減少趨勢。兩種算法的時間消耗持續(xù)下降，但是在BMS－WebView－1中CRPFP－DFS的時間表現(xiàn)明顯更好，同時在任意數(shù)據(jù)集中CRPFP－DFS的內(nèi)存消耗都更小。因?yàn)樯疃葍?yōu)先策略優(yōu)先探索可能的組合路徑，直到不能生成模式為止，然后回溯到上一個狀態(tài)繼續(xù)挖掘。這種方式的特點(diǎn)是對內(nèi)存需求較小，因?yàn)橐淮沃恍枰幚硪粭l組合路徑。

3.3 算法性能評估與分析

3.3.1 maxPer對算法性能的影響

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

3.3.2 minSup對算法性能的影響

本組實(shí)驗(yàn)通過改變minSup，評估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ù)量。從圖5中可以看出， 隨著minSup的增大，五種算法的時間消耗都呈下降趨勢，對BMS－WebView－1這樣的短事務(wù)數(shù)據(jù)集，CRPFP－DFS算法搜索空間較小，遞歸深度相對較淺，不會產(chǎn)生過多的遞歸調(diào)用，能夠更快地遍歷所有可能的項(xiàng)集組合，因此時間表現(xiàn)極好。從圖6可以看到，CRPFP－DFS在BMS－WebView－1數(shù)據(jù)集中比所有其他算法消耗更少的內(nèi)存，因?yàn)樗谒阉鳂涞纳疃确较蛏线M(jìn)行遞歸只需要保存當(dāng)前分支路徑上的信息，而不是整個搜索空間的結(jié)構(gòu)，有效地減少了內(nèi)存占用，從而具有良好的內(nèi)存優(yōu)勢。

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

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

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

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

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

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

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

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

5 結(jié)束語

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

參考文獻(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ù)據(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)目：國家自然科學(xué)基金資助項(xiàng)目（62272336）

作者簡介：閆海博（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ì)算．