頻繁模式壓縮綜述

摘?要：頻繁模式挖掘是指挖掘數據庫中頻繁出現的模式，但挖掘全部頻繁模式的方式往往會產生數量巨大的模式，不僅降低了挖掘效率，與此同時增加了用戶獲取重要信息的難度。本文對最大模式挖掘和閉合模式挖掘這兩種頻繁模式壓縮技術進行了介紹和綜述。在此基礎上對序列模式挖掘中應用模式壓縮技術進行了總結與展望。

關鍵詞：序列模式挖掘;頻繁模式;最大模式;閉合模式

隨著云計算、移動互聯網和物聯網等新一代信息技術的廣泛應用。多樣的、海量的全球數據以爆炸般的速度快速生成，這意味著人類已經進入大數據的信息時代。在面對海量數據信息，數據庫中存儲的數據量急劇膨脹，如何從海量且繁雜的信息中提取價值信息成為亟須解決的難題。傳統的模式挖掘只是挖掘滿足最小支持度閾值的頻繁子序列，挖掘出的頻繁模式完全集往往包含數量巨大的模式且大量冗余信息。隨著序列模式挖掘應用領域越來越廣泛，用戶對于序列模式挖掘提出了更為苛刻的要求，挖掘全部頻繁模式往往滿足不了用戶的需求，這樣不僅需要花費大量的時間，而且用戶很難在結果集中獲取有用的信息，因此壓縮模式集的技術成為眾多學者的研究熱點。

一、最大模式

定義（最大模式）若存在一頻繁模式，其所有超模式都為非頻繁模式，則稱該模式為最大模式。

模式挖掘技術的主要是根據模式滿足Apriori性質，即頻繁模式的所有子模式都是頻繁的，非頻繁模式的所有超模式都是非頻繁的。雖然在利用Apriori性質進行頻繁模式挖掘的過程中，可以有效地剪枝，但是這樣同時造成了模式集的規模呈指數性增長問題。最大模式挖掘作為一種有效的模式壓縮技術，在不改變用戶設定的最小支持度閾值前提下，挖掘出的序列模式集更加簡潔，有效減小頻繁模式集的規模，很大程度上減少了數據冗余，并且保留了數據集的表達能力。

最大模式挖掘算法按照模式搜索策略可以分為兩種：深度優先搜索和廣度優先搜索。深度優先搜索以DepthProject算法為代表，DepthProject算法對字典樹進行深度優先搜索，根據選擇性投影數據庫原理進行模式支持度計算。該方法同時使用了超頻繁模式剪枝策略，可以有效減少運行時間和內存空間的使用。廣度優先搜索則以MaxMiner算法為代表。MaxMiner算法首次提出搜索空間樹的概念，以集合枚舉樹作為搜索范圍，采取與Apriori性質一致的寬度優先搜索策略，該算法將尾項集按照支持度降序排列，盡可能早地對項集進行剪枝，從而提高超集剪枝效率。

二、閉合模式

定義（閉合模式）若存在一頻繁模式，不存在與其具有相同支持度的超模式，則該模式為閉合模式。

在挖掘閉合模式算法中以CloSPan算法和BIDE算法為代表。CloSPan算法通過只挖掘頻繁的閉子集而不是挖掘完整的頻繁子集，在生成候選模式和消除非閉合模式的兩個階段，減少了時間和空間開銷。它還利用了早期終止機制等技術，避免了不必要的搜索空間遍歷、反向子模式和反向超級模式挖掘方法，吸收了一些不必要的模式。BIDE算法在對新模式進行閉合檢查時，采用向前拓展事件和向后拓展事件的方式，可以有效地避免候選模式維護和檢測問題。采用深度優先搜索，更加深度的剪枝搜索空間，在線輸出頻繁閉合模式，以更加有效的方式檢測閉合模式。可以有效地減少內存消耗，提高運行效率。

三、總結與展望

挖掘最大模式是對全部頻繁模式結果集進行壓縮，較大幅度壓縮了模式集規模，提供了頻繁模糊與非頻頻繁模式之間的邊界信息，但是與閉合模式相比并未提供最大模式子模式的支持度信息。而挖掘閉合模式保存了頻繁模式結果集的全部信息，即模式的表達方式和支持度兩種信息。但是由于閉合模式的定義過于嚴格，當支持度閾值較小時，閉合模式的結果集依然龐大。

模式集壓縮研究中，許多學者也提出了新的研究方向，如對比序列模式[1]挖掘的研究，挖掘序列數據庫中對比度較高的模式集，從而挖掘出表現更加突出的結果集。同樣Wu等人[2]設計了一個基于MAPB算法的啟發式算法MAPBOK，該算法挖掘無特殊條件下不同長度模式下的前K種頻繁模式，可以有效減少模式集規模。與此同時，為了挖掘出更加有價值的模式，學者們對模式的出現進行約束，提出了無重疊條件[3，4，5]序列模式挖掘。約束模式中項在序列中的匹配次數和位置，可以有效挖掘出更加有價值的模式，使挖掘出結果集更加簡潔，更有意義。

因此學者們需要在如何避免模式集中包含過多的冗余模式和減少模式集大小方面提出更加有效的挖掘算法，為用戶提供更加精準的模式集方面做出更多探索。

參考文獻：

[1]柴欣，高一寒，武優西，等.基于密度約束的對比模式挖掘[J].計算機科學，2019，46（12）：2630.

[2]Wu Y，Wang L，Ren J，et al.Mining sequential patterns with periodic wildcard gaps[J].Applied Intelligence，2014，41（1）：99116.

[3]Wu Y，Shen C，Jiang H，et al.Strict pattern matching under nonoverlapping condition[J].Science China Information Sciences，2017，60（1）：012101.

[4]武優西，王振坤，史巧碩，等.無重疊條件下的Topk序列挖掘[J].小型微型計算機系統，2019，40（10）：21702174.

[5]Wu Y，Tong Y，Zhu X，et al.NOSEP：Nonoverlapping sequence pattern mining with gap constraints[J].IEEE Transactions on Cybernetics，2018，48（10）：28092822.

作者簡介：張帥（1994—），男，漢族，河北衡水人，碩士，學生，研究方向：序列模式挖掘。