对比模式挖掘研究进展

◆魏芹双

（河北工业大学计算机科学与软件学院 天津 300401）

对比模式挖掘研究进展

◆魏芹双

（河北工业大学计算机科学与软件学院 天津 300401）

对比模式能够描述两类或多类样本中的对比信息，识别不同类别样本集合的特征，在商品推荐、用户行为分析和电力供应预测等领域有着广泛的应用。传统的序列模式挖掘不能描述多类样本中的对比信息，因此越来越多的研究者投入到对比模式挖掘的研究行列。本文总结近几年来对比模式挖掘取得的重大成果和进展，特别地分析研究了其中几个经典算法，最后对对比模式挖掘发展趋势进行了展望，以便对带有间隙约束的对比模式挖掘做进一步的研究。

对比模式; 序列模式挖掘

0 前言

近年来，序列模式挖掘在众多领域的研究中发挥着重要作用，越来越多的研究者加入到序列模式挖掘问题的研究行列。对比模式能够描述两类或多类样本中的对比信息，识别不同类别样本集合的特征，在商品推荐、用户行为分析和电力供应预测等领域有着广泛的应用。

对比序列模式的概念最早是由Ji等人[1]在2007年提出的，它是序列模式挖掘的一个重要研究方向。对比模式是指模式在正例序列库中是频繁的并且在负例序列库中是非频繁的，Ji等人[1]设计了满足间隙约束的最小对比模式挖掘算法ConSGapMiner算法。经过多年的发展，对比序列模式挖掘的研究取得了较大的进步，研究者们提出了很多性能良好的算法。Shah等人建立了一个以对比模式作为特征的分类器，应用在多肽折叠预测问题上; Wang等人[2]首次提出将密度的概念融入到对比模式挖掘中，并设计了满足密度约束和间隙约束的对比模式挖掘算法gd-DSPMiner算法; Duan等人对基于显露模式的对比挖掘进行了详尽的研究; Yang等人[3]为解决由于用户设置不恰当的支持度阈值而造成频繁模式丢失的问题提出了带间隔约束的top-k对比模式挖掘算法kDSP-Miner算法; Wang等人设计了带紧凑间隔约束的最小对比序列模式挖掘算法MDSP-CGC算法，该算法可以不需要提前设置间隔约束，可以直接对候选模式进行分析自动计算最适合的间隔约束; Yang等人将基于单元素序列的最小对比序列模式挖掘扩展为基于元素集合序列的最小比模式挖掘。

本文对上述几个经典算法的进行简单介绍并且对它们进行评述。

1 对比模式挖掘算法

1.1 ConSGapMiner算法

对比数据可以应用于生物医学、分类器的创建等诸多领域，Ji等人[1]提出了可以挖掘出满足间隙约束的最小的对比模式挖掘算法ConSGapMiner算法。所谓的最小就是挖掘出对比模式的超模式均不是满足间隙约束的对比模式。

该算法的思想是:首先扫描序列库中的所有序列，生成字符集∑并建立字典树; 利用深度优先遍历字典树的方法对长度为l（l〉0）的候选模式集C’l中的模式生成长度为l+1的待挖掘模式集Cl+1; 利用比特集合（Bitset）数组计算得到长度为l+1的待挖掘模式在各个序列中的支持数，从而计算该模式在正例序列库D+和负例序列库D-中支持度; 如果在模式在正例序列库D+中的支持度大于等于正例支持度阈值并且在负例序列库D-中的支持度小于等于负例支持度阈值，将这个模式加入最小对比模式集中，否则将模式加入到候选模式集C’l+1，用于生成长度为l+2的待挖掘模式集Cl+2。迭代上述过程直到候选模式集为空。

现代计算机体系结构有对对二进制数进行移位操作和逻辑操作有非常高的效率，因此ConSGapMiner算法利用比特值集合的运算可以很快的得到模式在序列中的支持数。ConSGapMiner算法的提出为之后的研究起到了重要的引导作用。但它也存在一些不足:利用深度优先挖掘的办法时，一些最小的对比模式不能及时发现，这样剪枝策略得不到充分的发挥，会造成空间与时间上的浪费，从而影响挖掘的效率。

1.2 gd-DSPMiner算法

带有密度约束的序列模式更有助于生物学家研究发现生物序列中的一些特殊因子的分布情况，更有利于发现新的突变因子等。因此Wang等人[2]提出密度的概念，并且将密度与满足间隙约束的对比模式相融合提出了满足密度约束和间隙约束的对比模式的挖掘算法gd-DSPMiner算法。

该算法利用匹配三元组进行模式在序列中出现数的计算。在对比模式挖掘的过程中，将长度为l（l〉0）的待挖掘模式Cl分为四个不相交的集合:所有长度小于等于l的gd-DSP（满足密度约束和间隙约束的对比模式）的模式集合Pl，不可能是gd-DSP的模式集合Ul，子模式是gd-DSP的模式集合Ml和超模式可能是gd-DSP的模式集合Rl。通过连接集合Rl中的任意两个长度为l的候选模式，得到长度为l+1的待挖掘模式，从而得到所有的待挖掘模式集Cl+1; 根据gd-DSP的定义，只有Cl+1中的模式有可能产生满足要求的对比模式，因此仅仅对Cl+1中的模式进行挖掘，大大提高了挖掘的效率。

gd-DSPMiner算法的提出解决了ConSGapMiner算法采用深度优先遍历字典树生成候选模式而造成的重复挖掘的问题，但在计算模式在序列中的支持数时采用了匹配三元组的方法，该方法中不管模式在序列的某位置是否产生出现都会为该位置建立匹配三元组，因此造成了空间上的浪费。在设置参数方面必须进行多次实验，才可以得到合适的密度、支持度阈值以及间隙约束。

1.3 kDSP-Miner算法

上文提到的ConSGapMiner算法和gd-DSPMiner算法虽然可以快速的得到满足要求的对比模式，但设置不恰当的支持度阈值可能会造成对比模式的丢失，往往需要经过多次实验才可以得到合适的正例支持度阈值和负例支持度阈值。Yang等人[3]提出了带间隔约束的top-k对比序列模式挖掘算法kDSP-Miner算法。用户在挖掘对比最显著的k个对比模式时，不需要手动输入支持度阈值，避免了由于支持度阈值设置不合理而影响挖掘效果的问题。这里提到的top-k是指带间隔约束的对比度，即模式在正例序列库中的支持度与负例序列库中的支持度之差。

该算法通过扫描数据集，生成字母表∑并生成集合枚举树;利用深度优先遍历基于∑的集合枚举树方法逐一产生候选对比序列模式; 分别对每一个候选模式进行挖掘，如果对比度大于已有的top-k中的对比度最小的模式就将该模式替换为当前模式。迭代上述过程，直到完成对集合枚举树的遍历。

该算法采用三个裁剪策略和一个加速策略提高了算法的挖掘效率。为了提高该算法对高维序列进行处理的能力，同时进一步设计了kDSP-Miner的多线程版。Wang等人同样针对设置不合理的参数而造成频繁模式的丢失问题提出了MDSP-CGC算法，原理与kDSP-Miner算法类似，在此不再赘述。

2 总结

本文对对比模式挖掘产生的背景进行了分析，指出提出对比模式挖掘的意义所在。重点对近几年来提出的经典算法进行简单的介绍对它们的优缺点进行分析。目前已有的对比模式挖掘算法均是在周期性间隙约束的条件下进行的，如何在非周期性间隙约束条件下进行对比模式的挖掘值得我们进一步探索。

[1]Ji Xiaonan，James Bailey，Dong Guozhu.Mining minimal distinguishing subsequence patterns with gap constraints [J].Knowledge Information Systems，2007.

[2]Wang Xianming，Duan Lei，Dong Guozhu，et al.Efficient mining of density-aware distinguishing sequential patterns with gap constraints [M].In:Proceedings of the 19th International Conference of Database Systems for Advanced Applications，2014.

[3]杨皓，段磊，胡斌等.带间隔约束的Top-k对序列模式挖掘[J].软件学报，2015.