吳 軍，歐陽(yáng)艾嘉，張 琳

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

0 概述

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

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

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

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

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

1 問題定義

1.1 對(duì)比模式挖掘

令D為一個(gè)數(shù)據(jù)樣本集合，其中每條樣本s均能被屬性集A=｛A1，A2，…，A|A|｝表示。假設(shè)a是Aj的一個(gè)值，則Aj=a被稱作一個(gè)項(xiàng)t。單個(gè)或多個(gè)項(xiàng)構(gòu)成的集合，即｛t1，t2，…，tk｝，被稱為模式，用x表示，同時(shí)該模式的長(zhǎng)度被定義為項(xiàng)的個(gè)數(shù)，用k表示。對(duì)比模式給定模式x1和x2，如果x1中所有的項(xiàng)均被x2包含，則x1被稱作x2的子模式，x2被稱作x1的超模式。

如果一條樣本s的Aj屬性的值是a，那么稱樣本s包含Aj=a這個(gè)項(xiàng)。如果一條樣本s含有模式x所有的項(xiàng)，則稱樣本s包含模式x，表示為x?s。x在D中的支持度被定義為D中包含x的樣本數(shù)量，即sup（x，D）=|｛s|s∈D∧x?s｝|。如果x的支持度超過一個(gè)自定義閾值θsup，則x被認(rèn)為是頻繁模式。近年來，研究人員提出許多頻繁模式挖掘算法，例如，F(xiàn)P-growth算法［16］、Charm算法［17］等。

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

1.2 冗余對(duì)比模式

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

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

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

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

1.3 固定屬性置換過程

面向?qū)Ρ饶Ｊ桨l(fā)現(xiàn)的置換檢驗(yàn)方法無(wú)論使用精確零分布還是近似零分布，都遵循標(biāo)準(zhǔn)隨機(jī)置換過程。該過程通過隨機(jī)交換類別標(biāo)簽得到置換樣本集合。標(biāo)準(zhǔn)隨機(jī)置換過程如圖1 所示。例如，假定D包含8 條樣本，每條樣本由6 個(gè)普通屬性和1 個(gè)類別屬性構(gòu)成，類別屬性的值由c1和c2表示，如圖1（a）所示。根據(jù)樣本的編號(hào)，樣本集合隨機(jī)生成一個(gè)置換序列：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)隨機(jī)置換過程的置換樣本集合，如圖1（b）所示。

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

從圖1 可以看出，標(biāo)準(zhǔn)隨機(jī)置換過程并不會(huì)打破子模式和超模式對(duì)應(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)隨機(jī)置換計(jì)算得到的結(jié)果中，如果x1和x2均是統(tǒng)計(jì)顯著的，那么x2的統(tǒng)計(jì)顯著性很有可能是由x1的統(tǒng)計(jì)顯著性導(dǎo)致，即x2很大概率是冗余對(duì)比模式。

一種可行的過濾冗余對(duì)比模式原理是在置換過程中打破超模式與子模式對(duì)應(yīng)樣本的聯(lián)系。本文提出一個(gè)固定屬性的置換過程。在該置換過程中，如果一個(gè)子模式是統(tǒng)計(jì)顯著的，則固定該子模式所有項(xiàng)對(duì)應(yīng)的屬性列，僅置換余下的屬性列。例如，假定原始樣本集合與圖1（a）中的原始樣本集合相同，且子模式x1=｛t11｝是統(tǒng)計(jì)顯著的。同樣地，令隨機(jī)生成的置換序列為s7、s6、s2、s8、s4、s1、s3、s5。固定屬性置換過程首先將t11對(duì)應(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］，隨后計(jì)算每個(gè)閉頻繁模式的對(duì)比性度量GGrowthRate值［7］，如式（1）所示：

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

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

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

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

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

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

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

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

3 FEPRP 算法

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

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

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

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

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

x*可以被置換到3 個(gè)部分：與D1中包含xu的固定樣本結(jié)合（表示為D*1），與D2中包含xu的固定樣本結(jié)合（表示為D*2），與D1和D2中不包含xu的固定樣本結(jié)合（表示D～）。當(dāng)且僅當(dāng)包含x*的可置換樣本被置換到D*1和D*2中時(shí)，才能生成相應(yīng)的包含x的樣本。設(shè)中x*的數(shù)量為q，D*2中x*的數(shù)量為r，那么x*在固定屬性置換過程生成的置換樣本集合中的數(shù)量分布如表2 所示。從表2 可以看出，q和r決定著x*在置換樣本集合中的分布情況，對(duì)于每個(gè)q會(huì)存在多個(gè)與之匹配的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的對(duì)比性度量值分布由對(duì)比性度量值和其在置換樣本集合中出現(xiàn)的次數(shù)構(gòu)成。對(duì)比性度量值可由x的每種數(shù)量分布計(jì)算得到，其對(duì)應(yīng)的次數(shù)可以通過模擬該數(shù)量分布對(duì)應(yīng)的置換樣本集合生成得到。

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

在x存在一個(gè)或多個(gè)統(tǒng)計(jì)顯著的子模式中，x的數(shù)量分布由x*的數(shù)量分布決定，即每個(gè)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對(duì)應(yīng)x在固定屬性置換過程生成的置換樣本集合和中的支持度，從而通過一對(duì)q和r計(jì)算得出x的一個(gè)對(duì)比性度量值。

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)

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

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

表3 實(shí)驗(yàn)樣本集合信息Table 3 Information of experimental sample set

4.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.3 FSPRP 算法和FEPRP 算法的討論

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

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

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

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

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

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

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

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

圖6 在gamma 樣本集合上FSPRP 和FEPRP 算法的運(yùn)行時(shí)間對(duì)比Fig.6 The running time comparison of the FSPRP and FEPRP algorithms on gamma sample set

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

5 結(jié)束語(yǔ)

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