吳 軍，歐陽艾嘉，張 琳

（遵義師范學(xué)院信息工程學(xué)院，貴州遵義 563000）

0 概述

分析不同類型數(shù)據(jù)樣本之間的差異性對于分類、特征選擇、突變點檢測等研究具有重要意義。在數(shù)據(jù)挖掘領(lǐng)域中，對比模式發(fā)現(xiàn)任務(wù)是為了找到在不同類別標(biāo)簽的數(shù)據(jù)樣本集合中出現(xiàn)頻率差異顯著的模式［1］。目前，對比模式被廣泛應(yīng)用在醫(yī)學(xué)（如探索不同外科手術(shù)之間的聯(lián)系［2］）、生物學(xué)（如發(fā)現(xiàn)蛋白質(zhì)中的磷酸化基序［3］）、音樂學(xué)（如找到不同類型曲目的旋律差別［4］）等領(lǐng)域。

傳統(tǒng)的對比模式挖掘算法根據(jù)數(shù)據(jù)類型不同分為面向序列數(shù)據(jù)和面向非序列數(shù)據(jù)的對比模式挖掘算法［5-6］；根據(jù)策略的不同分為基于閾值約束和TOP-K 差異約束的算法［7-8］。這些算法的不同之處主要體現(xiàn)在候選模式生成方式、對比性度量、剪枝方式、搜索方式和數(shù)據(jù)結(jié)構(gòu)方面。

由于傳統(tǒng)的對比模式挖掘算法將注意力放在如何快速有效地找到滿足自定義約束的模式上，而算法返回報告的結(jié)果中存在一定數(shù)量的假陽性模式［9］。假陽性模式是指模式單純偶然地滿足對比模式挖掘算法定義的對比性度量約束，而沒有真實地表現(xiàn)不同類別數(shù)據(jù)樣本集合的差異特征。由于假陽性模式提供了錯誤的信息，因此有必要對挖掘到的模式進行質(zhì)量評估。統(tǒng)計顯著性檢驗是一種常用的模式質(zhì)量評估方法［10］。該方法首先構(gòu)建任務(wù)相關(guān)零假設(shè)，隨后計算相應(yīng)的統(tǒng)計顯著性度量值決定是否拒絕零假設(shè)。如果多個零假設(shè)被同時檢驗，則稱為多重假設(shè)檢驗。在對比模式發(fā)現(xiàn)任務(wù)中，常用的統(tǒng)計顯著性檢驗方法有直接計算方法［11］和置換檢驗方法［12］。無論在序列數(shù)據(jù)還是非序列數(shù)據(jù)中，置換檢驗方法的效率都優(yōu)于直接計算方法［13-14］。

在直接計算方法和置換檢驗方法返回的結(jié)果中存在許多的冗余對比模式［15］。冗余對比模式是受子模式統(tǒng)計顯著性的影響而呈現(xiàn)出統(tǒng)計顯著性的超模式。因此，冗余對比模式實際上沒有提供新的信息，且攜帶的額外信息還會對后續(xù)任務(wù)產(chǎn)生一定的干擾。除閉頻繁模式以外［13］，置換檢驗方法中常用的冗余對比模式過濾方法還有比較約束法［14］。該方法基于的假設(shè)是超模式的統(tǒng)計顯著性只有大于子模式的統(tǒng)計顯著性，才會提供額外有用的信息。實際上，統(tǒng)計顯著的超模式和子模式之間并不一定具備這樣的關(guān)系，然而比較約束法能夠過濾掉一定數(shù)量的冗余對比模式和許多非冗余對比模式。

本文設(shè)計FSPRP 和FEPRP 算法用于過濾置換檢驗方法中的冗余對比模式。通過在置換過程中固定子模式屬性列的方式，打破子模式和超模式在置換樣本集合中的聯(lián)系，從而計算不受子模式統(tǒng)計顯著性影響的超模式p值。FSPRP 算法依據(jù)標(biāo)準(zhǔn)置換檢驗原理，通過生成一定次數(shù)的置換樣本集合構(gòu)建零分布，而FEPRP 算法基于精確置換檢驗原理，通過計算每個模式的對比性度量值分布構(gòu)建零分布。

1 問題定義

1.1 對比模式挖掘

令D為一個數(shù)據(jù)樣本集合，其中每條樣本s均能被屬性集A=｛A1，A2，…，A|A|｝表示。假設(shè)a是Aj的一個值，則Aj=a被稱作一個項t。單個或多個項構(gòu)成的集合，即｛t1，t2，…，tk｝，被稱為模式，用x表示，同時該模式的長度被定義為項的個數(shù)，用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的樣本數(shù)量，即sup（x，D）=|｛s|s∈D∧x?s｝|。如果x的支持度超過一個自定義閾值θsup，則x被認為是頻繁模式。近年來，研究人員提出許多頻繁模式挖掘算法，例如，F(xiàn)P-growth算法［16］、Charm算法［17］等。

如果Acla是一個類別屬性，那么Acla的每種值都被稱為一個類別標(biāo)簽。在包含類別屬性的D中，如果一些模式在不同類別標(biāo)簽的樣本中支持度呈現(xiàn)較大差異，這樣的模式就被稱為對比模式。該差異可以由不同的對比性度量進行量化，即如果一個模式的對比性度量值超過一個自定義的閾值θdis，那么該模式就是對比模式。為便于描述后續(xù)方法，假定Acla僅包含兩種值c1和c2，從而D根據(jù)該屬性劃分為D1和D2。傳統(tǒng)的對比模式挖掘算法通常包含兩個步驟：首先，挖掘樣本集合D1中的頻繁模式；其次，在這些頻繁模式中找到所有滿足閾值θdis的對比模式。

1.2 冗余對比模式

如果一個模式本身是非統(tǒng)計顯著的模式，但其被錯誤地認定為統(tǒng)計顯著的模式并用于后續(xù)決策，這樣的模式被認為假陽性模式。傳統(tǒng)的對比模式挖掘算法報告結(jié)果中存在大量的假陽性模式，這些假陽性模式提供的錯誤信息會干擾后續(xù)決策。本文采用統(tǒng)計顯著性檢驗方法過濾這些假陽性模式。在統(tǒng)計顯著性檢驗中，模式的統(tǒng)計顯著性由p值度量，其定義是在零假設(shè)為真的前提下，找到一個至少同樣極端的模式的概率。p值越小則表明統(tǒng)計顯著性越強。

常用的統(tǒng)計顯著性檢驗方法分為直接計算方法［11］和置換檢驗方法［12］。直接計算方法將模式服從的分布當(dāng)作零分布，直接計算得到模式的p值；置換檢驗方法通過置換類別標(biāo)簽生成新的置換樣本集合，再從置換樣本集合中構(gòu)建零分布計算模式的p值。然而，在直接計算方法和置換檢驗方法返回的結(jié)果中均存在一定數(shù)量的冗余對比模式。冗余對比模式是給定超模式x2和子模式x1，如果x2的統(tǒng)計顯著性來源于x1，那么x2就是冗余對比模式。冗余對比模式?jīng)]有提供新的信息，保留它們會造成后續(xù)不必要的計算開銷，甚至還會干擾后續(xù)決策。

在直接計算方法中，文獻［18］提出使用模式集合挖掘策略過濾冗余對比模式，規(guī)定同一個集合中的模式必須滿足相異性約束才能被保留。文獻［19］設(shè)計了3 種冗余度量，并提出一個啟發(fā)式搜索的方法找到非冗余的對比模式組。文獻［20］在局部約束的基礎(chǔ)上額外定義基于子模式的全局約束，要求模式必須同時滿足2 個約束才是非冗余對比模式。文獻［15］設(shè)計CP-tree 和PDP-tree 兩種樹形結(jié)構(gòu)用于計算和比較超模式和子模式的統(tǒng)計顯著性，從而過濾不滿足約束閾值的冗余對比模式。

無論在序列數(shù)據(jù)還是非序列數(shù)據(jù)的對比模式發(fā)現(xiàn)任務(wù)中，置換檢驗方法的檢驗效力均強于直接計算方法［13-14］。在置換檢驗方法中，保留閉頻繁模式是最基本的冗余對比模式過濾方法［13］。閉頻繁模式是如果x1不存在一個超模式x2，使得x2和x1具有相同的支持度，那么x1就是閉頻繁模式，但這種方法只能過濾掉少量冗余對比模式。在置換檢驗方法的基礎(chǔ)上，冗余對比模式通常還采用比較約束法進一步過濾［14］。比較約束法將子模式和超模式的p值進行直接比較，如果超模式的p值大于子模式的p值，則超模式被認定為冗余對比模式。實際上，統(tǒng)計顯著的超模式的p值和子模式的p值并不一定具備這種關(guān)系，因此，比較約束法在過濾冗余對比模式的同時，也會過濾許多非冗余的統(tǒng)計顯著的超模式。

1.3 固定屬性置換過程

面向?qū)Ρ饶Ｊ桨l(fā)現(xiàn)的置換檢驗方法無論使用精確零分布還是近似零分布，都遵循標(biāo)準(zhǔn)隨機置換過程。該過程通過隨機交換類別標(biāo)簽得到置換樣本集合。標(biāo)準(zhǔn)隨機置換過程如圖1 所示。例如，假定D包含8 條樣本，每條樣本由6 個普通屬性和1 個類別屬性構(gòu)成，類別屬性的值由c1和c2表示，如圖1（a）所示。根據(jù)樣本的編號，樣本集合隨機生成一個置換序列：s7，s6，s2，s8，s4，s1，s3，s5。隨后根據(jù)該置換序列指定樣本的類別標(biāo)簽，將樣本s1的類別標(biāo)簽c1指派給樣本s7，并將其放在原來s1的位置，樣本s2的類別標(biāo)簽c1指派給樣本s6，并將其放到原來s2的位置，以此類推，就得到了標(biāo)準(zhǔn)隨機置換過程的置換樣本集合，如圖1（b）所示。

圖1 標(biāo)準(zhǔn)隨機置換過程Fig.1 The standard random permutation process

從圖1 可以看出，標(biāo)準(zhǔn)隨機置換過程并不會打破子模式和超模式對應(yīng)樣本的聯(lián)系，即置換樣本集合中包含超模式和子模式的樣本數(shù)量等于原始樣本集合中包含它們的數(shù)量，例如，給定子模式x1=｛t11｝和超模式x2=｛t11，t31｝，原始樣本集合中有4 條樣本｛s1，s2，s4，s7｝包含x1和x2，經(jīng)過置換后，置換樣本集合中仍有4 條樣本｛s'1，s'3，s'5，s'6｝包含x1和x2。因此，在標(biāo)準(zhǔn)隨機置換計算得到的結(jié)果中，如果x1和x2均是統(tǒng)計顯著的，那么x2的統(tǒng)計顯著性很有可能是由x1的統(tǒng)計顯著性導(dǎo)致，即x2很大概率是冗余對比模式。

一種可行的過濾冗余對比模式原理是在置換過程中打破超模式與子模式對應(yīng)樣本的聯(lián)系。本文提出一個固定屬性的置換過程。在該置換過程中，如果一個子模式是統(tǒng)計顯著的，則固定該子模式所有項對應(yīng)的屬性列，僅置換余下的屬性列。例如，假定原始樣本集合與圖1（a）中的原始樣本集合相同，且子模式x1=｛t11｝是統(tǒng)計顯著的。同樣地，令隨機生成的置換序列為s7、s6、s2、s8、s4、s1、s3、s5。固定屬性置換過程首先將t11對應(yīng)的屬性列A1固定，余下的屬性A2～A6列根據(jù)置換序列置換。固定屬性置換過程如圖2 所示。固定屬性置換過程將樣本s1的類別標(biāo)簽c1指派給不包含A1屬性的樣本s7，并將其放在樣本s1原來的位置；將樣本s2的類別標(biāo)簽c1指派給不包含A1屬性的樣本s6，并將其放在樣本s2原來的位置，以此類推，得到了置換樣本集合。

圖2 固定屬性置換過程Fig.2 The fixed attribute permutation process

2 FSPRP 算法

FSPRP 算法首先使用Charm 方法挖掘D1中的閉頻繁模式［17］，隨后計算每個閉頻繁模式的對比性度量GGrowthRate值［7］，如式（1）所示：

在這些模式中，滿足閾值θdis的模式被認定為候選對比模式。FSPRP 算法根據(jù)固定屬性置換過程，由短到長為各長度的模式生成一定數(shù)量的置換樣本集合（長度為1 的模式除外），并進行對比模式挖掘；利用這些對比模式的對比性度量值構(gòu)建各個長度相應(yīng)的零分布Nk。每個候選對比模式被賦予一個p值度量其統(tǒng)計顯著性，其定義是發(fā)現(xiàn)一個至少與該對比模式對比性度量值相同的對比模式概率。最后，將某個候選對比模式x的對比性度量值放置到其長度對應(yīng)的零分布Nk中就能計算出其p值，如式（2）所示：

上述零分布Nk是通過固定屬性置換過程建立的，因此由Nk計算得到k長度候選對比模式的p值去除了統(tǒng)計顯著子模式的影響。最后，F(xiàn)SPRP 算法采用錯誤發(fā)現(xiàn)率（FFDR）度量約束k長度候選對比模式假陽性結(jié)果的數(shù)量［21］，如式（3）所示：

其中：α為統(tǒng)計顯著水平；Xk為k長度候選對比模式的集合，oorder（x）為根據(jù)x的p值在Xk中從小到大的排序位置。詳細的FSPRP 算法步驟見算法1。

算法1FSPRP（D，θsup，θdis，h，z，α）

FSPRP 算法步驟主要分為3 步：

1）使用cp_mine（）方法挖掘D1中的候選對比模式。隨后，使用group（）方法根據(jù)模式的長度進行分組（第1、2 步）。

2）運用標(biāo)準(zhǔn)隨機置換過程sr_permute（）對D執(zhí)行z次置換，并挖掘這些置換樣本集合D'1中的對比模式。利用mv_extract（）方法提取1 長度模式的對比性度量值，并用其構(gòu)建1 長度模式的零分布N1，由于它們不存在統(tǒng)計顯著的子模式（第3～7 步），因此對長度為1 的模式運用標(biāo)準(zhǔn)隨機置換過程。通過N1計算1 長度候選對比模式的p值，并用錯誤發(fā)現(xiàn)率約束找到統(tǒng)計顯著的1 長度對比模式，即sig_patterns（）。最后，將所有統(tǒng)計顯著的1 長度對比模式放入保存統(tǒng)計顯著的對比模式集合E中（第8 步）。

3）對于長度大于1 的模式，從短到長依次運用固定屬性置換過程af_permute（）執(zhí)行z次置換。為提升效率，置換過程每次同時固定h個統(tǒng)計顯著的子模式對應(yīng)的屬性列，隨后，對置換樣本集合進行挖掘，并計算其中模式的對比性度量值用于構(gòu)建k長度模式的零分布Nk。從Nk中計算得到k長度候選對比模式的p值，并用錯誤發(fā)現(xiàn)率約束得到統(tǒng)計顯著的k長度對比模式。這些k長度對比模式p值的計算均考慮了統(tǒng)計顯著的子模式的影響。最后，所有統(tǒng)計顯著的k長度對比模式放入集合E中。E的最終結(jié)果是過濾了冗余對比模式的統(tǒng)計顯著的對比模式（第9～16 步）。

3 FEPRP 算法

FSPRP 算法具有以下3 個缺點：1）候選對比模式的p值可能為0，p值為0 是一個非常極端的近似值，它表示該對比模式的統(tǒng)計顯著性無窮大；2）多次運行FSPRP 算法得到的統(tǒng)計顯著對比模式可能不同；3）由于FSPRP 算法需要使用固定屬性置換過程生成一定次數(shù)的置換樣本集合，隨后還需要對樣本集合進行對比模式挖掘，因此FSPRP 算法計算開銷較大。

FSPRP 算法采用標(biāo)準(zhǔn)置換檢驗中通過生成一定置換次數(shù)的置換樣本集合構(gòu)建零分布的策略，因此產(chǎn)生上述缺點。由于每次運行FSPRP 算法生成置換樣本集合不同，從而導(dǎo)致構(gòu)建的零分布也不相同。文獻［14］利用精確置換檢驗解決標(biāo)準(zhǔn)置換檢驗中的問題。精確置換檢驗的基本原理是獨立計算每個對比模式的對比性度量值分布，然后合并得到相應(yīng)的精確零分布。根據(jù)精確置換檢驗計算生成零分布的原理，本文提出使用固定屬性置換過程的FEPRP 算法。

FEPRP 算法計算得到對比模式x的對比性度量值分布，首先要清楚x在固定屬性置換過程生成的置換樣本集合中的數(shù)量分布，x的數(shù)量分布分為x不存在統(tǒng)計顯著的子模式和x存在一個或多個統(tǒng)計顯著的子模式。在x不存在統(tǒng)計顯著的子模式?jīng)]有固定的屬性列，x在固定屬性置換過程生成的置換樣本集合中的數(shù)量分布等價于x在標(biāo)準(zhǔn)隨機置換過程生成的置換樣本集合中的數(shù)量分布。設(shè)x在置換樣本集合D'1中的數(shù)量為v，其分布情況如表1 所示。

表1 在標(biāo)準(zhǔn)隨機置換過程中對比模式x 的樣本集合數(shù)量分布Table 1 The number of sample set distribution of contrast mode x in the standard random permutation process

在對比模式x存在一個或多個統(tǒng)計顯著的子模式中，設(shè)對比模式x某一個統(tǒng)計顯著的子模式為xu，x*表示x除去xu剩下的項，即x-xu。在固定屬性置換過程中，xu對應(yīng)的屬性列不隨置換序列而改變，從而當(dāng)一條包含x*的可置換樣本被置換到包含xu的固定樣本的位置時，才能在置換樣本集合中形成一條包含x的樣本，即包含x*的可置換樣本與包含xu的固定樣本相結(jié)合得到一條包含x的樣本。x在置換樣本集合中的數(shù)量分布取決于有多少條包含x*的可置換樣本被置換到包含xu的固定樣本的位置。因此，x的數(shù)量分布實際上是由x*的數(shù)量分布決定。

x*可以被置換到3 個部分：與D1中包含xu的固定樣本結(jié)合（表示為D*1），與D2中包含xu的固定樣本結(jié)合（表示為D*2），與D1和D2中不包含xu的固定樣本結(jié)合（表示D～）。當(dāng)且僅當(dāng)包含x*的可置換樣本被置換到D*1和D*2中時，才能生成相應(yīng)的包含x的樣本。設(shè)中x*的數(shù)量為q，D*2中x*的數(shù)量為r，那么x*在固定屬性置換過程生成的置換樣本集合中的數(shù)量分布如表2 所示。從表2 可以看出，q和r決定著x*在置換樣本集合中的分布情況，對于每個q會存在多個與之匹配的r，反之亦然。當(dāng)q和r確定后，x在置換樣本集合中的數(shù)量分布也隨之確定。

表2 在固定屬性置換過程中x＊的樣本集合數(shù)量分布Table 2 The number of sample set distribution of x＊ in the fixed attribute permutation process

x的對比性度量值分布由對比性度量值和其在置換樣本集合中出現(xiàn)的次數(shù)構(gòu)成。對比性度量值可由x的每種數(shù)量分布計算得到，其對應(yīng)的次數(shù)可以通過模擬該數(shù)量分布對應(yīng)的置換樣本集合生成得到。

在x不存在統(tǒng)計顯著的子模式中，x在固定屬性置換過程生成的置換樣本集合中的數(shù)量分布等價于標(biāo)準(zhǔn)隨機置換過程生成的置換樣本集合中的數(shù)量分布。因此，v的最小值L（v）為max｛θsup，|D1|+ssup（x，D1）-|D|｝，最大值U（v）為min｛ssup（x，D），|D1|｝。由于每個v對應(yīng)一個對比性度量值，因此可以通過從小到大遞增v得到所有的對比性度量值。至于每個對比性度量值對應(yīng)的次數(shù)，可通過模擬D′1中恰好有v條樣本包含x的置換樣本集合生成計算得到，先從包含x的樣本ssup（x，D）中選取v條放入中，然后從不包含x的樣本|D| -ssup（x，D）中選取|D1| -v條放入中，最后將余下的樣本放入中。因此，該置換樣本集合的數(shù)量如式（4）所示：

在x存在一個或多個統(tǒng)計顯著的子模式中，x的數(shù)量分布由x*的數(shù)量分布決定，即每個q和r決定了x在固定屬性置換過程生成的置換樣本集合和中的支持度。q的最小值L（q）為max｛θsup，ssup（xu，D1）+ssup（x*，D）-|D|｝，最大值U（q）為min｛ssup（x*，D），ssup（xu，D1）｝。r的最小值L（r）為max｛0，ssup（x*，D）-q-|D|+ssup（xu，D2）｝，r的最大值U（r）為min｛ssup（x*，D）-q，ssup（xu，D2）｝。由于q和r對應(yīng)x在固定屬性置換過程生成的置換樣本集合和中的支持度，從而通過一對q和r計算得出x的一個對比性度量值。

每個對比性度量值對應(yīng)的次數(shù)也可以通過模擬和中分別有q和r條樣本包含x的置換樣本集合計算得到，先從包含x*可置換樣本中取出q條放入中，再從不包含x*可置換樣本中取出ssup（xu，D1）-q條放入中。所有可能的的組成數(shù)量如式（5）～式（7）所示：

FEPRP 算法從余下的包含x*可置換樣本中取出r條放入中，再從余下的不包含x*可置換樣本中取出ssup（xu，D2）-r條放入中。所有可能的組成數(shù)量如式（8）～式（10）所示：

最后將余下的可置換樣本放入D～中，且D～可能的組成數(shù)量為1，模擬了固定屬性置換過程中x在和中支持度分別為q和r的置換樣本集合的生成，且該置換樣本集合的數(shù)量如式（11）所示：

由于上述對比性度量值分布的計算是基于固定屬性置換過程得到的，因此其打破了統(tǒng)計顯著的子模式對超模式的影響。在計算每個超模式x的對比性度量分布時，如果考慮其所有統(tǒng)計顯著的子模式xu，則能夠計算得到固定屬性置換過程對應(yīng)的精確零分布。但在實際應(yīng)用中，一個較長的模式可能包含許多統(tǒng)計顯著的子模式，考慮到算法的實用性，F(xiàn)EPRP 算法只去除了統(tǒng)計顯著性最強的m個子模式的影響，詳細的FEPRP 算法步驟見算法2。

算法2FEPRP（D，θsup，θdis，m，α）

1）使用cp_mine（）方法挖掘D1中的候選對比模式和D中所有可能在置換樣本集合中出現(xiàn)的對比模式，隨后使用group（）方法根據(jù)模式的長度進行各自分組（第1～2 步）。

2）從長度為1 的模式開始，由短到長依次為不同長度的模式構(gòu)建零分布Nk。具體而言，對于每個長度為k的模式x，如果其不存在統(tǒng)計顯著的子模式xu，使用brcd_consruct（）方法計算其對比性度量值分布B，即用式（1）計算每個的對比性度量值，用式（4）計算每個對比性度量值相應(yīng)的置換樣本集合的數(shù)量（第5～6 步）；如果x存在統(tǒng)計顯著的子模式xu，使用facd_consruct（）方法計算其對比性度量值分布B，即先找到x統(tǒng)計顯著性最強的m個子模式，隨后將每個子模式視作xu，用式（1）計算每對q和r分布的對比性度量值，用式（11）計算每個對比性度量值對應(yīng)的置換樣本集合的數(shù)量（第7～8 步）。計算得到所有k長度模式的對比性度量值分布后，將其合并就能得到k長度模式的零分布Nk（第9 步）。

3）利用sig_patterns（）方法計算每個k長度模式的p值，并使用錯誤發(fā)現(xiàn)率約束得到統(tǒng)計顯著的k長度對比模式，再將這些模式放到集合E中。迭代完成后，E的最終結(jié)果即是過濾了冗余對比模式的統(tǒng)計顯著的對比模式（第11 步）。

4 實驗

為驗證FSPRP 和FEPRP 算法過濾冗余對比模式的效率，在4 個不同類型的數(shù)據(jù)樣本集合上進行實驗。實驗對比算法為DA 算法［1］、SP 算法［13］、SPRF算法［12］和IEPCSP 算法［14］，其中DA 和SP 算法分別使用直接計算方法和標(biāo)準(zhǔn)置換檢驗方法找到統(tǒng)計顯著的對比模式，且這兩個算法都未考慮冗余對比模式問題。SPRF 和IEPCSP 算法分別使用標(biāo)準(zhǔn)置換檢驗和精確置換檢驗挖掘統(tǒng)計顯著的對比模式，此外還采用比較約束方法過濾結(jié)果中的冗余對比模式。在實驗中，如無特殊說明FEPRP 算法僅考慮8 個統(tǒng)計顯著性最強的子模式，F(xiàn)SPRP 算法的置換次數(shù)為1 000。為了進行統(tǒng)一比較，每個對比算法都采用Charm 方法挖掘候選對比模式，且使用錯誤發(fā)現(xiàn)率作為多重假設(shè)檢驗約束。所有實驗均在一臺配置為2.40 GHz CPU 和12 GB 內(nèi)存的設(shè)備上運行。

4.1 實驗數(shù)據(jù)

實驗采用4 個不同類型的真實數(shù)據(jù)樣本集合：即german、hypo、gamma 和adult。這4 個數(shù)據(jù)樣本集合均源自于UCI machine learning repository 數(shù)據(jù)庫［22］，其中，german 是銀行客戶信用特征樣本集；hypo 是甲狀腺疾病患者特征樣本集；gamma 是γ-粒子成像特征樣本集；adult 是成人收入特征樣本集。實驗樣本集合信息如表3 所示，其中對連續(xù)的屬性值進行了離散化。

表3 實驗樣本集合信息Table 3 Information of experimental sample set

4.2 實驗結(jié)果

4.2.1 返回的模式數(shù)量

不同算法的統(tǒng)計顯著對比模式數(shù)量如圖3 所示，其中所有算法參數(shù)相同，即θsup、θdis和α相同。從圖3 可以看出，在各個樣本集合中DA 和SP 算法返回的統(tǒng)計顯著模式數(shù)量遠遠大于其他算法?；谥苯佑嬎惴椒ê蜆?biāo)準(zhǔn)隨機置換過程方法返回的結(jié)果中保留了大量的冗余對比模式。此外，在4 種使用冗余對比模式過濾的算法中，F(xiàn)SPRP 和FEPRP 算法返回的模式數(shù)量多于SPRF 和IEPCSP 算法。其原因是FSPRP 和FEPRP 算法采用的固定屬性置換過程是在考慮子模式影響的條件下計算得出的超模式p值。

圖3 不同算法的統(tǒng)計顯著的對比模式數(shù)量Fig.3 The number of statistically significant contrast patterns of different algorithms

為更進一步分析冗余對比模式過濾情況，SPRF、IEPCSP、FSPRP 和FEPRP 算法在hypo 樣本集合上不同長度模式數(shù)量l（省略了8 長度模式以后的信息）如表4 所示。從表4 可以看出，長模式過濾的比率高于短模式過濾的比率，這是因為模式越長包含的子模式越多，從而受子模式統(tǒng)計顯著性影響的可能性就越大。SPRF 和IEPCSP 算法針對長模式過濾的力度大于FSPRP 和FEPRP 算法，這表明比較約束方法較固定屬性置換過程對長模式的要求更加苛刻，從而更易保留較短的模式。

表4 在hypo 樣本集合上各算法不同長度模式數(shù)量對比Table 4 The number of patterns with different lengths comparison of each algorithms on hypo sample set

4.2.2 分類預(yù)測結(jié)果

為體現(xiàn)冗余對比模式對后續(xù)任務(wù)的影響以及過濾的好處，將各算法報告的模式作為數(shù)據(jù)樣本集中提取的特征進行分類預(yù)測實驗。本文將每個統(tǒng)計顯著的對比模式作為一個特征，利用每條樣本與所有模式的包含關(guān)系生成特征向量。統(tǒng)計顯著的對比模式作為特征是因為其本身反映了不同類別標(biāo)簽樣本集合的差異性［23］?？紤]到分類模型自身因素影響，實驗采用3 種不同機制的模型，即決策樹分類模型［24］、邏輯回歸分類模型［24］和隨機森林分類模型［24］。此外，為了避免偶然性，本文使用十折交叉驗證的平均正確率作為預(yù)測結(jié)果，決策樹分類模型下不同算法的分類準(zhǔn)確率對比如表5 所示，邏輯回歸分類模型不同算法的分類準(zhǔn)確率如表6所示，隨機森林分類模型不同算法的分類準(zhǔn)確率如表7 所示。

表5 在決策樹分類模型下不同算法的分類準(zhǔn)確率對比Table 5 The classification accuracy comparison among different algorithms under decision tree classifier model %

表6 在邏輯回歸分類模型下不同算法的分類準(zhǔn)確率對比Table 6 The classification accuracy comparison among different algorithms under logistic resupession classifier model %

表7 在隨機森林分類模型下不同算法的分類準(zhǔn)確率Table 7 The classification accuracy comparison among different algorithms under random forest classifier model %

從表5～表7 可以看出，DA 和SP 算法的分類準(zhǔn)確率低于其他4 個算法，雖然DA 和SP 算法使用統(tǒng)計顯著性檢驗去除一定數(shù)量的假陽性模式，但其結(jié)果還保留著大量的冗余對比模式，尤其是在gamma和adult 樣本集合返回的結(jié)果中。這些冗余對比模式提供的額外無用信息對分類模型產(chǎn)生了一定干擾。本文使用比較約束方法或者固定屬性置換過程都過濾了一定數(shù)量的冗余對比模式，從而提高準(zhǔn)確率。

結(jié)合圖3 可知，雖然SPRF 和IEPCSP 算法過濾的模式數(shù)量多于FSPRP 和FEPRP 算法，但其相應(yīng)的準(zhǔn)確率卻低于FSPRP 和FEPRP 算法，其原因是SPRF 和IEPCSP 算法利用比較約束法要求超模式的統(tǒng)計顯著性必須大于其子模式才能予以保留，但事實上超模式和子模式的統(tǒng)計顯著性并不一定具備這樣的關(guān)系，從而導(dǎo)致SPRF 和IEPCSP 算法在過濾冗余對比模式的同時，也過濾了許多非冗余的統(tǒng)計顯著模式，從而丟失許多差異特征。而FSPRP 和FEPRP 算法從冗余對比模式的本質(zhì)出發(fā)，使用固定屬性置換過程打破超模式和子模式在置換樣本集合中的聯(lián)系，真正過濾了受子模式統(tǒng)計顯著性影響的冗余對比模式，因此達到了更高的預(yù)測準(zhǔn)確率。

冗余對比模式會給后續(xù)任務(wù)決策帶來干擾，使用固定屬性置換過程的FSPRP 和FEPRP 算法能夠過濾掉置換檢驗中一定數(shù)量的冗余對比模式，且比使用比較約束法的SPRF 和IEPCSP 算法效果更優(yōu)。

4.2.3 FSPRP 算法和FEPRP 算法的討論

上述實驗結(jié)果表明，F(xiàn)EPRP 算法略優(yōu)于FSPRP算法，這體現(xiàn)在FEPRP 算法報告的模式數(shù)量更少但分類準(zhǔn)確率更高。雖然FSPRP 和FEPRP 算法建立的都是近似零分布，但是FSPRP 算法采用生成固定屬性置換樣本集合的方式，而FEPRP 算法通過計算對比模式對比性度量值分布的方式。為探究2 種算法的構(gòu)建方式差別，實驗通過計算得到german 和hypo 樣本集合的精確零分布分別為3 259 和6 748，并對比不同置換次數(shù)z的FSPRP 算法和不同子模式數(shù)量m的FEPRP 算法返回的模式數(shù)量與精確零分布返回的模式數(shù)量。在german 和hypo 樣本集合上不同算法的近似零分布對比如表8 所示。

表8 在german 和hypo 樣本集上不同算法的近似零分布對比Table 8 Approximate null distributions comparison among different algorithms on german and hypo sample sets

從表8 中可以得出，增加FSPRP 算法中z和增加FEPRP算法中m均能得到各自更接近精確零分布返回的結(jié)果。FEPRP 算法在m=10 時近似零分布與精確零分布的結(jié)果已相差不大，但FSPRP 算法在m=2 000 時近似零分布與精確零分布的結(jié)果還存在一定差距，表明FEPRP 算法相較于FSPRP 算法更易得到一個接近精確零分布的近似零分布。

由于FSPRP 算法零分布的建立方式依據(jù)標(biāo)準(zhǔn)置換檢驗方法，其存在標(biāo)準(zhǔn)置換檢驗中的p值可能為0、結(jié)果不唯一、計算開銷大3 個缺點；FEPRP 算法雖然沒有建立精確零分布，但其使用精確置換檢驗中計算對比性度量值分布建立零分布的策略，在m確定的情況下，F(xiàn)EPRP 算法構(gòu)造的零分布也是確定的。本文進行對比實驗以驗證FEPRP 算法不存在FSPRP算法中3 個缺點。

FSPRP 算法在各樣本集合中p值為0 的對比模式數(shù)量對比如圖4 所示。從圖4 可以看出，F(xiàn)SPRP 算法在每個樣本集合中均存在一定數(shù)量p值為0 的對比模式，F(xiàn)EPRP 算法在構(gòu)建每個模式的對比性度量值分布時，總能找到和該模式對比性度量值相等或更大的模式，所以FEPRP 算法不存在p值為0 的模式。FSPRP 和FEPRP 算法在adult 樣本集合上各運行100 次返回的模式數(shù)量如圖5 所示。從圖5 可以看出，F(xiàn)SPRP 算法返回的結(jié)果不唯一，由于每次使用固定屬性置換過程生成的置換樣本集合均不一樣，因此計算得到的對比模式的p值也不相同。FEPRP算法在m給定的情況下，每次構(gòu)建的零分布都是相同的，因此其結(jié)果始終相同。

圖4 在不同樣本集合上FSPRP 算法的p 值對比Fig.4 The p values comparison of FSPRP algorithm on different sample sets

圖5 FSPRP 和FEPRP 算法運行100 次的模式數(shù)量Fig.5 The number of patterns of FSPRP and FEPRP algorithms in the 100 runs

FSPRP 算法的運行時間主要受置換次數(shù)z的影響，而FEPRP 算法的運行時間主要受子模式個數(shù)m的影響。在gamma 樣本集合上FSPRP 和FEPRP 算法的運行時間對比如圖6 所示。從圖6（a）可以看出，F(xiàn)SPRP 算法在各個置換次數(shù)下的運行時間均超過FEPRP 算法在各個子模式數(shù)量下的運行時間，說明FSPRP 算法的計算開銷大于FEPRP 算法。其主要原因是置換樣本集合的生成和對比模式的挖掘都是計算開銷較大的操作。FSPRP 算法在生成零分布的過程中需要實際使用固定屬性置換過程生成置換樣本集合，隨后再對這些樣本集合進行對比模式挖掘；而FEPRP 算法在對樣本集合進行一次挖掘后，只需要模擬固定屬性置換過程生成置換樣本集合就能夠計算得到零分布，而不用實際生成置換樣本集合，這樣就大幅減少了運行時間。

圖6 在gamma 樣本集合上FSPRP 和FEPRP 算法的運行時間對比Fig.6 The running time comparison of the FSPRP and FEPRP algorithms on gamma sample set

因此，F(xiàn)EPRP 算法整體性能優(yōu)于FSPRP 算法，其更適用于置換檢驗中過濾冗余對比模式。

5 結(jié)束語

本文提出2 個使用固定屬性置換過程的冗余對比模式過濾算法（FSPRP 和FEPRP），分別利用生成一定數(shù)量的置換樣本集合和計算模式對比性度量值分布的方式建立零分布。實驗結(jié)果表明，F(xiàn)SPRP 和FEPRP 算法能夠過濾置換檢驗中一定數(shù)量的冗余對比模式，且相較于比較約束法的效果更優(yōu)。與FSPRP 算法相比，F(xiàn)EPRP 算法分類準(zhǔn)確率較高，更適用于過濾置換檢驗中的冗余對比模式。由于在固定屬性置換過程中每次得到的樣本都會發(fā)生改變，因此后續(xù)將設(shè)計適用于FSPRP 算法的一次數(shù)據(jù)挖掘方法，以減少運行時間。此外，將固定屬性置換檢驗方法應(yīng)用于解決序列數(shù)據(jù)中冗余對比模式的過濾問題，也將是下一步研究的重點方向。