2022, Vol. 48
开放科学（资源服务）标志码（OSID）：
分析不同类型数据样本之间的差异性对于分类、特征选择、突变点检测等研究具有重要意义。在数据挖掘领域中，对比模式发现任务是为了找到在不同类别标签的数据样本集合中出现频率差异显著的模式[1]。目前，对比模式被广泛应用在医学（如探索不同外科手术之间的联系[2]）、生物学（如发现蛋白质中的磷酸化基序[3]）、音乐学（如找到不同类型曲目的旋律差别[4]）等领域。
传统的对比模式挖掘算法根据数据类型不同分为面向序列数据和面向非序列数据的对比模式挖掘算法[5-6]；根据策略的不同分为基于阈值约束和TOP-K差异约束的算法[7-8]。这些算法的不同之处主要体现在候选模式生成方式、对比性度量、剪枝方式、搜索方式和数据结构方面。
由于传统的对比模式挖掘算法将注意力放在如何快速有效地找到满足自定义约束的模式上，而算法返回报告的结果中存在一定数量的假阳性模式[9]。假阳性模式是指模式单纯偶然地满足对比模式挖掘算法定义的对比性度量约束，而没有真实地表现不同类别数据样本集合的差异特征。由于假阳性模式提供了错误的信息，因此有必要对挖掘到的模式进行质量评估。统计显著性检验是一种常用的模式质量评估方法[10]。该方法首先构建任务相关零假设，随后计算相应的统计显著性度量值决定是否拒绝零假设。如果多个零假设被同时检验，则称为多重假设检验。在对比模式发现任务中，常用的统计显著性检验方法有直接计算方法[11]和置换检验方法[12]。无论在序列数据还是非序列数据中，置换检验方法的效率都优于直接计算方法[13-14]。
在直接计算方法和置换检验方法返回的结果中存在许多的冗余对比模式[15]。冗余对比模式是受子模式统计显著性的影响而呈现出统计显著性的超模式。因此，冗余对比模式实际上没有提供新的信息，且携带的额外信息还会对后续任务产生一定的干扰。除闭频繁模式以外[13]，置换检验方法中常用的冗余对比模式过滤方法还有比较约束法[14]。该方法基于的假设是超模式的统计显著性只有大于子模式的统计显著性，才会提供额外有用的信息。实际上，统计显著的超模式和子模式之间并不一定具备这样的关系，然而比较约束法能够过滤掉一定数量的冗余对比模式和许多非冗余对比模式。
本文设计FSPRP和FEPRP算法用于过滤置换检验方法中的冗余对比模式。通过在置换过程中固定子模式属性列的方式，打破子模式和超模式在置换样本集合中的联系，从而计算不受子模式统计显著性影响的超模式p值。FSPRP算法依据标准置换检验原理，通过生成一定次数的置换样本集合构建零分布，而FEPRP算法基于精确置换检验原理，通过计算每个模式的对比性度量值分布构建零分布。
1 问题定义 1.1 对比模式挖掘令D为一个数据样本集合，其中每条样本s均能被属性集A={A1，A2，…，A|A|}表示。假设a是Aj的一个值，则Aj=a被称作一个项t。单个或多个项构成的集合，即{t1，t2，…，tk}，被称为模式，用x表示，同时该模式的长度被定义为项的个数，用k表示。对比模式给定模式x1和x2，如果x1中所有的项均被x2包含，则x1被称作x2的子模式，x2被称作x1的超模式。
如果一条样本s的Aj属性的值是a，那么称样本s包含Aj=a这个项。如果一条样本s含有模式x所有的项，则称样本s包含模式x，表示为x⊇s。x在D中的支持度被定义为D中包含x的样本数量，即sup（x，D）=|{s | s∈D ˄ x⊇s}|。如果x的支持度超过一个自定义阈值θsup，则x被认为是频繁模式。近年来，研究人员提出许多频繁模式挖掘算法，例如，FP-growth算法[16]、Charm算法[17]等。
如果Acla是一个类别属性，那么Acla的每种值都被称为一个类别标签。在包含类别属性的D中，如果一些模式在不同类别标签的样本中支持度呈现较大差异，这样的模式就被称为对比模式。该差异可以由不同的对比性度量进行量化，即如果一个模式的对比性度量值超过一个自定义的阈值θdis，那么该模式就是对比模式。为便于描述后续方法，假定Acla仅包含两种值c1和c2，从而D根据该属性划分为D1和D2。传统的对比模式挖掘算法通常包含两个步骤：首先，挖掘样本集合D1中的频繁模式；其次，在这些频繁模式中找到所有满足阈值θdis的对比模式。
1.2 冗余对比模式如果一个模式本身是非统计显著的模式，但其被错误地认定为统计显著的模式并用于后续决策，这样的模式被认为假阳性模式。传统的对比模式挖掘算法报告结果中存在大量的假阳性模式，这些假阳性模式提供的错误信息会干扰后续决策。本文采用统计显著性检验方法过滤这些假阳性模式。在统计显著性检验中，模式的统计显著性由p值度量，其定义是在零假设为真的前提下，找到一个至少同样极端的模式的概率。p值越小则表明统计显著性越强。
常用的统计显著性检验方法分为直接计算方法[11]和置换检验方法[12]。直接计算方法将模式服从的分布当作零分布，直接计算得到模式的p值；置换检验方法通过置换类别标签生成新的置换样本集合，再从置换样本集合中构建零分布计算模式的p值。然而，在直接计算方法和置换检验方法返回的结果中均存在一定数量的冗余对比模式。冗余对比模式是给定超模式x2和子模式x1，如果x2的统计显著性来源于x1，那么x2就是冗余对比模式。冗余对比模式没有提供新的信息，保留它们会造成后续不必要的计算开销，甚至还会干扰后续决策。
在直接计算方法中，文献[18]提出使用模式集合挖掘策略过滤冗余对比模式，规定同一个集合中的模式必须满足相异性约束才能被保留。文献[19]设计了3种冗余度量，并提出一个启发式搜索的方法找到非冗余的对比模式组。文献[20]在局部约束的基础上额外定义基于子模式的全局约束，要求模式必须同时满足2个约束才是非冗余对比模式。文献[15]设计CP-tree和PDP-tree两种树形结构用于计算和比较超模式和子模式的统计显著性，从而过滤不满足约束阈值的冗余对比模式。
无论在序列数据还是非序列数据的对比模式发现任务中，置换检验方法的检验效力均强于直接计算方法[13-14]。在置换检验方法中，保留闭频繁模式是最基本的冗余对比模式过滤方法[13]。闭频繁模式是如果x1不存在一个超模式x2，使得x2和x1具有相同的支持度，那么x1就是闭频繁模式，但这种方法只能过滤掉少量冗余对比模式。在置换检验方法的基础上，冗余对比模式通常还采用比较约束法进一步过滤[14]。比较约束法将子模式和超模式的p值进行直接比较，如果超模式的p值大于子模式的p值，则超模式被认定为冗余对比模式。实际上，统计显著的超模式的p值和子模式的p值并不一定具备这种关系，因此，比较约束法在过滤冗余对比模式的同时，也会过滤许多非冗余的统计显著的超模式。
1.3 固定属性置换过程面向对比模式发现的置换检验方法无论使用精确零分布还是近似零分布，都遵循标准随机置换过程。该过程通过随机交换类别标签得到置换样本集合。标准随机置换过程如图 1所示。例如，假定D包含8条样本，每条样本由6个普通属性和1个类别属性构成，类别属性的值由c1和c2表示，如图 1（a）所示。根据样本的编号，样本集合随机生成一个置换序列：s7，s6，s2，s8，s4，s1，s3，s5。随后根据该置换序列指定样本的类别标签，将样本s1的类别标签c1指派给样本s7，并将其放在原来s1的位置，样本s2的类别标签c1指派给样本s6，并将其放到原来s2的位置，以此类推，就得到了标准随机置换过程的置换样本集合，如图 1（b）所示。
|
Download:
|
| 图 1 标准随机置换过程 Fig. 1 The standard random permutation process | |
从图 1可以看出，标准随机置换过程并不会打破子模式和超模式对应样本的联系，即置换样本集合中包含超模式和子模式的样本数量等于原始样本集合中包含它们的数量，例如，给定子模式x1={t11}和超模式x2={t11，t31}，原始样本集合中有4条样本{s1，s2，s4，s7}包含x1和x2，经过置换后，置换样本集合中仍有4条样本{s'1，s'3，s'5，s'6}包含x1和x2。因此，在标准随机置换计算得到的结果中，如果x1和x2均是统计显著的，那么x2的统计显著性很有可能是由x1的统计显著性导致，即x2很大概率是冗余对比模式。
一种可行的过滤冗余对比模式原理是在置换过程中打破超模式与子模式对应样本的联系。本文提出一个固定属性的置换过程。在该置换过程中，如果一个子模式是统计显著的，则固定该子模式所有项对应的属性列，仅置换余下的属性列。例如，假定原始样本集合与图 1（a）中的原始样本集合相同，且子模式x1={t11}是统计显著的。同样地，令随机生成的置换序列为s7、s6、s2、s8、s4、s1、s3、s5。固定属性置换过程首先将t11对应的属性列A1固定，余下的属性A2~A6列根据置换序列置换。固定属性置换过程如图 2所示。固定属性置换过程将样本s1的类别标签c1指派给不包含A1属性的样本s7，并将其放在样本s1原来的位置；将样本s2的类别标签c1指派给不包含A1属性的样本s6，并将其放在样本s2原来的位置，以此类推，得到了置换样本集合。
|
Download:
|
| 图 2 固定属性置换过程 Fig. 2 The fixed attribute permutation process | |
从图 2（b）可以看出，置换样本集合中仅有2条样本{s'1，s'5}包含x1和x2，说明固定属性置换过程打破了子模式和超模式对应样本的联系。因此，在固定属性置换过程生成的置换样本集合包含超模式和子模式的样本数量不一定等于原始样本集合中包含超模式和子模式的样本数量。在该置换过程中，每条样本非固定的项称为可置换样本，固定的项称为固定样本。对于s2而言，{t23，t31，t41，t52，t62}是可置换样本，{t11}是固定样本。基于上述置换过程，本文提出两个新的面向置换检验的冗余对比模式过滤算法：FSPRP算法和FEPRP算法。
2 FSPRP算法FSPRP算法首先使用Charm方法挖掘D1中的闭频繁模式[17]，随后计算每个闭频繁模式的对比性度量GGrowth Rate值[7]，如式（1）所示：
| $ {G}_{\mathrm{G}\mathrm{r}\mathrm{o}\mathrm{w}\mathrm{t}\mathrm{h}\mathrm{ }\mathrm{R}\mathrm{a}\mathrm{t}\mathrm{e}}(x, D)=\frac{{s}_{\mathrm{s}\mathrm{u}\mathrm{p}}(x, {D}_{1})}{{s}_{\mathrm{s}\mathrm{u}\mathrm{p}}(x, {D}_{2})} $ | (1) |
在这些模式中，满足阈值θdis的模式被认定为候选对比模式。FSPRP算法根据固定属性置换过程，由短到长为各长度的模式生成一定数量的置换样本集合（长度为1的模式除外），并进行对比模式挖掘；利用这些对比模式的对比性度量值构建各个长度相应的零分布Nk。每个候选对比模式被赋予一个p值度量其统计显著性，其定义是发现一个至少与该对比模式对比性度量值相同的对比模式概率。最后，将某个候选对比模式x的对比性度量值放置到其长度对应的零分布Nk中就能计算出其p值，如式（2）所示：
| $ {p}_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}}(x, {N}_{k})=\frac{\left|\right\{n\left|{G}_{\mathrm{G}\mathrm{r}\mathrm{o}\mathrm{w}\mathrm{t}\mathrm{h}\mathrm{R}\mathrm{a}\mathrm{t}\mathrm{e}}\right(x, D)\le n\wedge n\in {N}_{k}\}|}{\left|{N}_{k}\right|} $ | (2) |
上述零分布Nk是通过固定属性置换过程建立的，因此由Nk计算得到k长度候选对比模式的p值去除了统计显著子模式的影响。最后，FSPRP算法采用错误发现率（FFDR）度量约束k长度候选对比模式假阳性结果的数量[21]，如式（3）所示：
| $ {F}_{\mathrm{F}\mathrm{D}\mathrm{R}}({X}_{k}, \alpha )=\left\{\left.x\right|{p}_{value}\left(x\right)\le \frac{\alpha \times {o}_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}}\left(x\right)}{\left|{X}_{k}\right|}\wedge x\in {X}_{k}\right\} $ | (3) |
其中：α为统计显著水平；Xk为k长度候选对比模式的集合，oorder（x）为根据x的p值在Xk中从小到大的排序位置。详细的FSPRP算法步骤见算法1。
算法1 FSPRP（D，θsup，θdis，h，z，α）
输入 数据样本集合D={D1，D2}；支持度阈值θsup；对比性度量阈值θdis，固定个数h，置换次数z，统计显著水平α
输出 统计显著的对比模式集合E
1.X ← cp_mine（D1，θsup，θdis）
2.X1，X2，…，Xmaxl（X） ← group（X）
3.for i = 1 to z do
4.D'← sr_permute（D）
5.X'← cp_mine（D'1，θsup，θdis）
6.N1← N1∪mv_extract（X'，1）
7.end for
8.E ← E∪sig_patterns（X1，N1，α）
9.for k = 2 to maxl（X）do
10.for i = 1 to z do
11.D'← af_ permute（D，E，h）
12.X'← cp_mine（D'1，θsup，θdis）
13.Nk← Nk∪mv_extract（X'，k）
14.end for
15.E ← E∪sig_patterns（Xk，Nk，α）
16.end for
FSPRP算法步骤主要分为3步：
1）使用cp_mine（）方法挖掘D1中的候选对比模式。随后，使用group（）方法根据模式的长度进行分组（第1、2步）。
2）运用标准随机置换过程sr_permute（）对D执行z次置换，并挖掘这些置换样本集合D'1中的对比模式。利用mv_extract（）方法提取1长度模式的对比性度量值，并用其构建1长度模式的零分布N1，由于它们不存在统计显著的子模式（第3~7步），因此对长度为1的模式运用标准随机置换过程。通过N1计算1长度候选对比模式的p值，并用错误发现率约束找到统计显著的1长度对比模式，即sig_ patterns（）。最后，将所有统计显著的1长度对比模式放入保存统计显著的对比模式集合E中（第8步）。
3）对于长度大于1的模式，从短到长依次运用固定属性置换过程af_permute（）执行z次置换。为提升效率，置换过程每次同时固定h个统计显著的子模式对应的属性列，随后，对置换样本集合进行挖掘，并计算其中模式的对比性度量值用于构建k长度模式的零分布Nk。从Nk中计算得到k长度候选对比模式的p值，并用错误发现率约束得到统计显著的k长度对比模式。这些k长度对比模式p值的计算均考虑了统计显著的子模式的影响。最后，所有统计显著的k长度对比模式放入集合E中。E的最终结果是过滤了冗余对比模式的统计显著的对比模式（第9~16步）。
3 FEPRP算法FSPRP算法具有以下3个缺点：1）候选对比模式的p值可能为0，p值为0是一个非常极端的近似值，它表示该对比模式的统计显著性无穷大；2）多次运行FSPRP算法得到的统计显著对比模式可能不同；3）由于FSPRP算法需要使用固定属性置换过程生成一定次数的置换样本集合，随后还需要对样本集合进行对比模式挖掘，因此FSPRP算法计算开销较大。
FSPRP算法采用标准置换检验中通过生成一定置换次数的置换样本集合构建零分布的策略，因此产生上述缺点。由于每次运行FSPRP算法生成置换样本集合不同，从而导致构建的零分布也不相同。文献[14]利用精确置换检验解决标准置换检验中的问题。精确置换检验的基本原理是独立计算每个对比模式的对比性度量值分布，然后合并得到相应的精确零分布。根据精确置换检验计算生成零分布的原理，本文提出使用固定属性置换过程的FEPRP算法。
FEPRP算法计算得到对比模式x的对比性度量值分布，首先要清楚x在固定属性置换过程生成的置换样本集合中的数量分布，x的数量分布分为x不存在统计显著的子模式和x存在一个或多个统计显著的子模式。在x不存在统计显著的子模式没有固定的属性列，x在固定属性置换过程生成的置换样本集合中的数量分布等价于x在标准随机置换过程生成的置换样本集合中的数量分布。设x在置换样本集合D'1中的数量为v，其分布情况如表 1所示。
|
下载CSV 表 1 在标准随机置换过程中对比模式x的样本集合数量分布 Table 1 The number of sample set distribution of contrast mode x in the standard random permutation process |
在对比模式x存在一个或多个统计显著的子模式中，设对比模式x某一个统计显著的子模式为xu，x*表示x除去xu剩下的项，即x－xu。在固定属性置换过程中，xu对应的属性列不随置换序列而改变，从而当一条包含x*的可置换样本被置换到包含xu的固定样本的位置时，才能在置换样本集合中形成一条包含x的样本，即包含x*的可置换样本与包含xu的固定样本相结合得到一条包含x的样本。x在置换样本集合中的数量分布取决于有多少条包含x*的可置换样本被置换到包含xu的固定样本的位置。因此，x的数量分布实际上是由x*的数量分布决定。
x*可以被置换到3个部分：与D1中包含xu的固定样本结合（表示为D1*），与D2中包含xu的固定样本结合（表示为D2*），与D1和D2中不包含xu的固定样本结合（表示D~）。当且仅当包含x*的可置换样本被置换到D1*和D2*中时，才能生成相应的包含x的样本。设D1*中x*的数量为q，D2*中x*的数量为r，那么x*在固定属性置换过程生成的置换样本集合中的数量分布如表 2所示。从表 2可以看出，q和r决定着x*在置换样本集合中的分布情况，对于每个q会存在多个与之匹配的r，反之亦然。当q和r确定后，x在置换样本集合中的数量分布也随之确定。
|
下载CSV 表 2 在固定属性置换过程中x*的样本集合数量分布 Table 2 The number of sample set distribution of x* in the fixed attribute permutation process |
x的对比性度量值分布由对比性度量值和其在置换样本集合中出现的次数构成。对比性度量值可由x的每种数量分布计算得到，其对应的次数可以通过模拟该数量分布对应的置换样本集合生成得到。
在x不存在统计显著的子模式中，x在固定属性置换过程生成的置换样本集合中的数量分布等价于标准随机置换过程生成的置换样本集合中的数量分布。因此，v的最小值L（v）为max{θsup，|D1|+
| $ {n}_{\mathrm{s}\mathrm{e}{\mathrm{t}}_{1}}^{\mathrm{p}}(x, v)=\left(\begin{array}{c}{s}_{\mathrm{s}\mathrm{u}\mathrm{p}}(x, D)\\ v\end{array}\right)\left(\begin{array}{c}\left|D\right|-{s}_{\mathrm{s}\mathrm{u}\mathrm{p}}(x, D)\\ \left|{D}_{1}\right|-v\end{array}\right) $ | (4) |
在x存在一个或多个统计显著的子模式中，x的数量分布由x*的数量分布决定，即每个q和r决定了x在固定属性置换过程生成的置换样本集合
每个对比性度量值对应的次数也可以通过模拟
| $ {s}_{\mathrm{c}1}({x}^{\mathrm{*}}, q)=\left(\begin{array}{c}{s}_{\mathrm{s}\mathrm{u}\mathrm{p}}({x}^{\mathrm{*}}, D)\\ q\end{array}\right) $ | (5) |
| $ {s}_{\mathrm{c}1}({x}^{*}, q)=\left(\begin{array}{c}\left|D\right|-{s}_{\mathrm{s}\mathrm{u}\mathrm{p}}({x}^{*}, D)\\ {s}_{\mathrm{s}\mathrm{u}\mathrm{p}}({x}_{\mathrm{u}}, {D}_{1})-q\end{array}\right) $ | (6) |
| $ {n}_{\mathrm{d}1}({x}^{\mathrm{*}}, q)={s}_{\mathrm{c}1}({x}^{\mathrm{*}}, q){s}_{\mathrm{c}2}({x}^{\mathrm{*}}, q) $ | (7) |
FEPRP算法从余下的包含x*可置换样本中取出r条放入
| $ {s}_{\mathrm{c}3}({x}^{\mathrm{*}}, q, r)=\left(\begin{array}{c}{s}_{\mathrm{s}\mathrm{u}\mathrm{p}}({x}^{\mathrm{*}}, D)-q\\ r\end{array}\right) $ | (8) |
| $ {s}_{\mathrm{c}4}({x}^{\mathrm{*}}, q, r)=\left(\begin{array}{c}\left|D\right|-{s}_{\mathrm{s}\mathrm{u}\mathrm{p}}({x}^{\mathrm{*}}, D)-{s}_{\mathrm{s}\mathrm{u}\mathrm{p}}({x}_{\mathrm{u}}, {D}_{1})+q\\ {s}_{\mathrm{s}\mathrm{u}\mathrm{p}}({x}_{\mathrm{u}}, {D}_{2})-r\end{array}\right) $ | (9) |
| $ {n}_{\mathrm{d}2}({x}^{\mathrm{*}}, q, r)={s}_{\mathrm{c}3}({x}^{\mathrm{*}}, q, r){s}_{\mathrm{c}4}({x}^{\mathrm{*}}, q, r) $ | (10) |
最后将余下的可置换样本放入D~中，且D~可能的组成数量为1，模拟了固定属性置换过程中x在
| $ {n}_{\mathrm{s}\mathrm{e}{\mathrm{t}}_{2}}^{\mathrm{p}}({x}^{*}, q, r)={n}_{\mathrm{d}1}({x}^{*}, q){n}_{\mathrm{d}2}({x}^{*}, q, r) $ | (11) |
由于上述对比性度量值分布的计算是基于固定属性置换过程得到的，因此其打破了统计显著的子模式对超模式的影响。在计算每个超模式x的对比性度量分布时，如果考虑其所有统计显著的子模式xu，则能够计算得到固定属性置换过程对应的精确零分布。但在实际应用中，一个较长的模式可能包含许多统计显著的子模式，考虑到算法的实用性，FEPRP算法只去除了统计显著性最强的m个子模式的影响，详细的FEPRP算法步骤见算法2。
算法2 FEPRP（D，θsup，θdis，m，α）
输入 数据样本集合D={D1，D2}；支持度阈值θsup；对比性度量阈值θdis，子模式个数m，统计显著水平α
输出 统计显著的对比模式集合E
1.X1，X2，…，Xmaxl（X） ← group（cp_mine（D1，θsup，θdis））
2.X'1，X'2，…，X'maxl（X） ← group（cp_mine（D，θsup，θdis））
3.for k = 1 to maxl（X）do
4.for each x in X'k
5.if x not exists xu
6.B←brcd_consruct（x，θsup，θdis）
7.else
8.B←facd_consruct（x，E，m，θsup，θdis）
9.Nk← Nk∪B
10.end for
11.E ← E∪sig_patterns（Xk，Nk，α）
12.end for
1）使用cp_mine（）方法挖掘D1中的候选对比模式和D中所有可能在置换样本集合中出现的对比模式，随后使用group（）方法根据模式的长度进行各自分组（第1~2步）。
2）从长度为1的模式开始，由短到长依次为不同长度的模式构建零分布Nk。具体而言，对于每个长度为k的模式x，如果其不存在统计显著的子模式xu，使用brcd_consruct（）方法计算其对比性度量值分布B，即用式（1）计算每个的对比性度量值，用式（4）计算每个对比性度量值相应的置换样本集合的数量（第5~6步）；如果x存在统计显著的子模式xu，使用facd_consruct（）方法计算其对比性度量值分布B，即先找到x统计显著性最强的m个子模式，随后将每个子模式视作xu，用式（1）计算每对q和r分布的对比性度量值，用式（11）计算每个对比性度量值对应的置换样本集合的数量（第7~8步）。计算得到所有k长度模式的对比性度量值分布后，将其合并就能得到k长度模式的零分布Nk（第9步）。
3）利用sig_patterns（）方法计算每个k长度模式的p值，并使用错误发现率约束得到统计显著的k长度对比模式，再将这些模式放到集合E中。迭代完成后，E的最终结果即是过滤了冗余对比模式的统计显著的对比模式（第11步）。
4 实验为验证FSPRP和FEPRP算法过滤冗余对比模式的效率，在4个不同类型的数据样本集合上进行实验。实验对比算法为DA算法[1]、SP算法[13]、SPRF算法[12]和IEPCSP算法[14]，其中DA和SP算法分别使用直接计算方法和标准置换检验方法找到统计显著的对比模式，且这两个算法都未考虑冗余对比模式问题。SPRF和IEPCSP算法分别使用标准置换检验和精确置换检验挖掘统计显著的对比模式，此外还采用比较约束方法过滤结果中的冗余对比模式。在实验中，如无特殊说明FEPRP算法仅考虑8个统计显著性最强的子模式，FSPRP算法的置换次数为1 000。为了进行统一比较，每个对比算法都采用Charm方法挖掘候选对比模式，且使用错误发现率作为多重假设检验约束。所有实验均在一台配置为2.40 GHz CPU和12 GB内存的设备上运行。
4.1 实验数据实验采用4个不同类型的真实数据样本集合：即german、hypo、gamma和adult。这4个数据样本集合均源自于UCI machine learning repository数据库[22]，其中，german是银行客户信用特征样本集；hypo是甲状腺疾病患者特征样本集；gamma是γ-粒子成像特征样本集；adult是成人收入特征样本集。实验样本集合信息如表 3所示，其中对连续的属性值进行了离散化。
|
下载CSV 表 3 实验样本集合信息 Table 3 Information of experimental sample set |
不同算法的统计显著对比模式数量如图 3所示，其中所有算法参数相同，即θsup、θdis和α相同。从图 3可以看出，在各个样本集合中DA和SP算法返回的统计显著模式数量远远大于其他算法。基于直接计算方法和标准随机置换过程方法返回的结果中保留了大量的冗余对比模式。此外，在4种使用冗余对比模式过滤的算法中，FSPRP和FEPRP算法返回的模式数量多于SPRF和IEPCSP算法。其原因是FSPRP和FEPRP算法采用的固定属性置换过程是在考虑子模式影响的条件下计算得出的超模式p值。
|
Download:
|
| 图 3 不同算法的统计显著的对比模式数量 Fig. 3 The number of statistically significant contrast patterns of different algorithms | |
为更进一步分析冗余对比模式过滤情况，SPRF、IEPCSP、FSPRP和FEPRP算法在hypo样本集合上不同长度模式数量
|
下载CSV 表 4 在hypo样本集合上各算法不同长度模式数量对比 Table 4 The number of patterns with different lengths comparison of each algorithms on hypo sample set |
为体现冗余对比模式对后续任务的影响以及过滤的好处，将各算法报告的模式作为数据样本集中提取的特征进行分类预测实验。本文将每个统计显著的对比模式作为一个特征，利用每条样本与所有模式的包含关系生成特征向量。统计显著的对比模式作为特征是因为其本身反映了不同类别标签样本集合的差异性[23]。考虑到分类模型自身因素影响，实验采用3种不同机制的模型，即决策树分类模型[24]、逻辑回归分类模型[24]和随机森林分类模型[24]。此外，为了避免偶然性，本文使用十折交叉验证的平均正确率作为预测结果，决策树分类模型下不同算法的分类准确率对比如表 5所示，逻辑回归分类模型不同算法的分类准确率如表 6所示，随机森林分类模型不同算法的分类准确率如表 7所示。
|
下载CSV 表 5 在决策树分类模型下不同算法的分类准确率对比 Table 5 The classification accuracy comparison among different algorithms under decision tree classifier model |
|
下载CSV 表 6 在逻辑回归分类模型下不同算法的分类准确率对比 Table 6 The classification accuracy comparison among different algorithms under logistic resupession classifier model |
|
下载CSV 表 7 在随机森林分类模型下不同算法的分类准确率 Table 7 The classification accuracy comparison among different algorithms under random forest classifier model |
从表 5~表 7可以看出，DA和SP算法的分类准确率低于其他4个算法，虽然DA和SP算法使用统计显著性检验去除一定数量的假阳性模式，但其结果还保留着大量的冗余对比模式，尤其是在gamma和adult样本集合返回的结果中。这些冗余对比模式提供的额外无用信息对分类模型产生了一定干扰。本文使用比较约束方法或者固定属性置换过程都过滤了一定数量的冗余对比模式，从而提高准确率。
结合图 3可知，虽然SPRF和IEPCSP算法过滤的模式数量多于FSPRP和FEPRP算法，但其相应的准确率却低于FSPRP和FEPRP算法，其原因是SPRF和IEPCSP算法利用比较约束法要求超模式的统计显著性必须大于其子模式才能予以保留，但事实上超模式和子模式的统计显著性并不一定具备这样的关系，从而导致SPRF和IEPCSP算法在过滤冗余对比模式的同时，也过滤了许多非冗余的统计显著模式，从而丢失许多差异特征。而FSPRP和FEPRP算法从冗余对比模式的本质出发，使用固定属性置换过程打破超模式和子模式在置换样本集合中的联系，真正过滤了受子模式统计显著性影响的冗余对比模式，因此达到了更高的预测准确率。
冗余对比模式会给后续任务决策带来干扰，使用固定属性置换过程的FSPRP和FEPRP算法能够过滤掉置换检验中一定数量的冗余对比模式，且比使用比较约束法的SPRF和IEPCSP算法效果更优。
4.2.3 FSPRP算法和FEPRP算法的讨论上述实验结果表明，FEPRP算法略优于FSPRP算法，这体现在FEPRP算法报告的模式数量更少但分类准确率更高。虽然FSPRP和FEPRP算法建立的都是近似零分布，但是FSPRP算法采用生成固定属性置换样本集合的方式，而FEPRP算法通过计算对比模式对比性度量值分布的方式。为探究2种算法的构建方式差别，实验通过计算得到german和hypo样本集合的精确零分布分别为3 259和6 748，并对比不同置换次数z的FSPRP算法和不同子模式数量m的FEPRP算法返回的模式数量与精确零分布返回的模式数量。在german和hypo样本集合上不同算法的近似零分布对比如表 8所示。
|
下载CSV 表 8 在german和hypo样本集上不同算法的近似零分布对比 Table 8 Approximate null distributions comparison among different algorithms on german and hypo sample sets |
从表 8中可以得出，增加FSPRP算法中z和增加FEPRP算法中m均能得到各自更接近精确零分布返回的结果。FEPRP算法在m=10时近似零分布与精确零分布的结果已相差不大，但FSPRP算法在m=2 000时近似零分布与精确零分布的结果还存在一定差距，表明FEPRP算法相较于FSPRP算法更易得到一个接近精确零分布的近似零分布。
由于FSPRP算法零分布的建立方式依据标准置换检验方法，其存在标准置换检验中的p值可能为0、结果不唯一、计算开销大3个缺点；FEPRP算法虽然没有建立精确零分布，但其使用精确置换检验中计算对比性度量值分布建立零分布的策略，在m确定的情况下，FEPRP算法构造的零分布也是确定的。本文进行对比实验以验证FEPRP算法不存在FSPRP算法中3个缺点。
FSPRP算法在各样本集合中p值为0的对比模式数量对比如图 4所示。从图 4可以看出，FSPRP算法在每个样本集合中均存在一定数量p值为0的对比模式，FEPRP算法在构建每个模式的对比性度量值分布时，总能找到和该模式对比性度量值相等或更大的模式，所以FEPRP算法不存在p值为0的模式。FSPRP和FEPRP算法在adult样本集合上各运行100次返回的模式数量如图 5所示。从图 5可以看出，FSPRP算法返回的结果不唯一，由于每次使用固定属性置换过程生成的置换样本集合均不一样，因此计算得到的对比模式的p值也不相同。FEPRP算法在m给定的情况下，每次构建的零分布都是相同的，因此其结果始终相同。
|
Download:
|
| 图 4 在不同样本集合上FSPRP算法的p值对比 Fig. 4 The p values comparison of FSPRP algorithm on different sample sets | |
|
Download:
|
| 图 5 FSPRP和FEPRP算法运行100次的模式数量 Fig. 5 The number of patterns of FSPRP and FEPRP algorithms in the 100 runs | |
FSPRP算法的运行时间主要受置换次数z的影响，而FEPRP算法的运行时间主要受子模式个数m的影响。在gamma样本集合上FSPRP和FEPRP算法的运行时间对比如图 6所示。从图 6（a）可以看出，FSPRP算法在各个置换次数下的运行时间均超过FEPRP算法在各个子模式数量下的运行时间，说明FSPRP算法的计算开销大于FEPRP算法。其主要原因是置换样本集合的生成和对比模式的挖掘都是计算开销较大的操作。FSPRP算法在生成零分布的过程中需要实际使用固定属性置换过程生成置换样本集合，随后再对这些样本集合进行对比模式挖掘；而FEPRP算法在对样本集合进行一次挖掘后，只需要模拟固定属性置换过程生成置换样本集合就能够计算得到零分布，而不用实际生成置换样本集合，这样就大幅减少了运行时间。
|
Download:
|
| 图 6 在gamma样本集合上FSPRP和FEPRP算法的运行时间对比 Fig. 6 The running time comparison of the FSPRP and FEPRP algorithms on gamma sample set | |
因此，FEPRP算法整体性能优于FSPRP算法，其更适用于置换检验中过滤冗余对比模式。
5 结束语本文提出2个使用固定属性置换过程的冗余对比模式过滤算法（FSPRP和FEPRP），分别利用生成一定数量的置换样本集合和计算模式对比性度量值分布的方式建立零分布。实验结果表明，FSPRP和FEPRP算法能够过滤置换检验中一定数量的冗余对比模式，且相较于比较约束法的效果更优。与FSPRP算法相比，FEPRP算法分类准确率较高，更适用于过滤置换检验中的冗余对比模式。由于在固定属性置换过程中每次得到的样本都会发生改变，因此后续将设计适用于FSPRP算法的一次数据挖掘方法，以减少运行时间。此外，将固定属性置换检验方法应用于解决序列数据中冗余对比模式的过滤问题，也将是下一步研究的重点方向。
| [1] |
HÄMÄLÄINEN W, WEBB G I. A tutorial on statistically sound pattern discovery[J]. Data Mining and Knowledge Discovery, 2019, 33(2): 325-377. DOI:10.1007/s10618-018-0590-x |
| [2] |
FORESTIER G, PETITJEAN F, SENIN P, et al. Finding discriminative and interpretable patterns in sequences of surgical activities[J]. Artificial Intelligence in Medicine, 2017, 82(1): 11-19. |
| [3] |
CHENG A, GRANT C E, NOBLE W S, et al. MoMo: discovery of statistically significant post-translational modification motifs[J]. Bioinformatics, 2019, 35(16): 2774-2782. DOI:10.1093/bioinformatics/bty1058 |
| [4] |
NEUBARTH K, SHANAHAN D, CONKLIN D. Supervised descriptive pattern discovery in native American music[J]. Journal of New Music Research, 2018, 47(1): 1-16. DOI:10.1080/09298215.2017.1353637 |
| [5] |
FOURNIER P, LIN J C, KIRAN R U, et al. A survey of sequential pattern mining[J]. Data Science and Pattern Recognition, 2017, 1(1): 54-77. |
| [6] |
KOH Y S, RAVANA S D. Unsupervised rare pattern mining: a survey[J]. ACM Transactions on Knowledge Discovery from Data, 2016, 10(4): 1-29. |
| [7] |
FANG G, PANDEY G, WANG W, et al. Mining low-support discriminative patterns from dense and high-dimensional data[J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 24(2): 279-294. |
| [8] |
杨皓, 段磊, 胡斌, 等. 带间隔约束的Top-k对比序列模式挖掘[J]. 软件学报, 2015, 26(11): 2994-3009. YANG H, DUAN L, HU B, et al. Mining Top-k distinguishing sequential patterns with gap constraint[J]. Journal of Software, 2015, 26(11): 2994-3009. (in Chinese) |
| [9] |
WEBB G I, VREEKEN J. Efficient discovery of the most interesting associations[J]. ACM Transactions on Knowledge Discovery from Data, 2014, 8(3): 1-31. |
| [10] |
ZHANG A S, SHI W Z, WEBB G I. Mining significant association rules from uncertain data[J]. Data Mining and Knowledge Discovery, 2016, 30(4): 928-963. DOI:10.1007/s10618-015-0446-6 |
| [11] |
HE Z Y, ZHANG S M, GU F Y, et al. Significance-based discriminative sequential pattern mining[J]. Expert Systems with Applications, 2019, 122(1): 54-64. |
| [12] |
LLINARES-LÓPEZ F, SUGIYAMA M, PAPAXANTHOS L, et al. Fast and memory-efficient significant pattern mining via permutation testing [C]//Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2016: 725-734.
|
| [13] |
LIU G M, ZHANG H J, WONG L. Controlling false positives in association rule mining [C]//Proceedings of the VLDB Endowment. New York, USA: ACM Press, 2011: 145-156.
|
| [14] |
吴军, 欧阳艾嘉, 张琳. 面向对比序列模式发现的独立精确置换检验算法[J]. 计算机工程, 2021, 47(8): 45-53, 61. WU J, OUYANG A J, ZHANG L. Discovering contrast sequential patterns based on independent exact permutation testing[J]. Computer Engineering, 2021, 47(8): 45-53, 61. (in Chinese) |
| [15] |
HE Z Y, GU F Y, ZHAO C. Conditional discriminative pattern mining: concepts and algorithms[J]. Information Sciences, 2017, 375(1): 1-15. |
| [16] |
高权, 万晓冬. 基于负载均衡的并行FP-Growth算法[J]. 计算机工程, 2019, 45(3): 32-35, 40. GAO Q, WAN X D. Parallel FP-growth algorithm based on load balance[J]. Computer Engineering, 2019, 45(3): 32-35, 40. (in Chinese) |
| [17] |
ZAKI M J, HSIAO C J. Charm: an efficient algorithm for closed itemset mining [C]//Proceedings of the 2nd SIAM International Conference on Data Mining. Arlington, USA: SIAM Press, 2002: 457-473.
|
| [18] |
GUNS T, NIJSSEN S, RAEDT L. K-pattern set mining under constraints[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(2): 402-418. DOI:10.1109/TKDE.2011.204 |
| [19] |
VAN L M, KNOBBE A. Diverse subgroup set discovery[J]. Data Mining and Knowledge Discovery, 2012, 26(2): 208-242. |
| [20] |
LIU X Q, WU J, GONG H P, et al. Mining conditional phosphorylation motifs[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2014, 11(5): 915-927. DOI:10.1109/TCBB.2014.2321400 |
| [21] |
ZHU Y L, GUO W. Family-wise error rate controlling procedures for discrete data [EB/OL]. [2020-11-12]. https://arxiv.org/abs/1711.08147.
|
| [22] |
DUA D, GRAFF C. UCI machine learning repository [EB/OL]. [2020-11-10]. http://archive.ics.uci.edu/ml.
|
| [23] |
LOYOLA G O, MONROY R, RODRÍGUEZ J, et al. Contrast pattern-based classification for bot detection on twitter[J]. IEEE Access, 2019, 7: 45800-45817. DOI:10.1109/ACCESS.2019.2904220 |
| [24] |
HAN J W, KAMBER M. Data mining: concepts and techniques[M]. San Francisco, USA: Morgan Kaufmann Publishers, 2000.
|