论文部分内容阅读
摘 要：频繁模式挖掘是指挖掘数据库中频繁出现的模式，但挖掘全部频繁模式的方式往往会产生数量巨大的模式，不仅降低了挖掘效率，与此同时增加了用户获取重要信息的难度。本文对最大模式挖掘和闭合模式挖掘这两种频繁模式压缩技术进行了介绍和综述。在此基础上对序列模式挖掘中应用模式压缩技术进行了总结与展望。
关键词：序列模式挖掘;频繁模式;最大模式;闭合模式
随着云计算、移动互联网和物联网等新一代信息技术的广泛应用。多样的、海量的全球数据以爆炸般的速度快速生成，这意味着人类已经进入大数据的信息时代。在面对海量数据信息，数据库中存储的数据量急剧膨胀，如何从海量且繁杂的信息中提取价值信息成为亟须解决的难题。传统的模式挖掘只是挖掘满足最小支持度阈值的频繁子序列，挖掘出的频繁模式完全集往往包含数量巨大的模式且大量冗余信息。随着序列模式挖掘应用领域越来越广泛，用户对于序列模式挖掘提出了更为苛刻的要求，挖掘全部频繁模式往往满足不了用户的需求，这样不仅需要花费大量的时间，而且用户很难在结果集中获取有用的信息，因此压缩模式集的技术成为众多学者的研究热点。
一、最大模式
定义（最大模式）若存在一频繁模式，其所有超模式都为非频繁模式，则称该模式为最大模式。
模式挖掘技术的主要是根据模式满足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—），男，汉族，河北衡水人，硕士，学生，研究方向：序列模式挖掘。
关键词：序列模式挖掘;频繁模式;最大模式;闭合模式
随着云计算、移动互联网和物联网等新一代信息技术的广泛应用。多样的、海量的全球数据以爆炸般的速度快速生成，这意味着人类已经进入大数据的信息时代。在面对海量数据信息，数据库中存储的数据量急剧膨胀，如何从海量且繁杂的信息中提取价值信息成为亟须解决的难题。传统的模式挖掘只是挖掘满足最小支持度阈值的频繁子序列，挖掘出的频繁模式完全集往往包含数量巨大的模式且大量冗余信息。随着序列模式挖掘应用领域越来越广泛，用户对于序列模式挖掘提出了更为苛刻的要求，挖掘全部频繁模式往往满足不了用户的需求，这样不仅需要花费大量的时间，而且用户很难在结果集中获取有用的信息，因此压缩模式集的技术成为众多学者的研究热点。
一、最大模式
定义（最大模式）若存在一频繁模式，其所有超模式都为非频繁模式，则称该模式为最大模式。
模式挖掘技术的主要是根据模式满足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—），男，汉族，河北衡水人，硕士，学生，研究方向：序列模式挖掘。