面向置換檢驗的冗余對比模式過濾算法

吳 軍，歐陽艾嘉，張 琳

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

0 概述

分析不同類型數據樣本之間的差異性對于分類、特征選擇、突變點檢測等研究具有重要意義。在數據挖掘領域中，對比模式發現任務是為了找到在不同類別標簽的數據樣本集合中出現頻率差異顯著的模式［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）所示。

圖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原來的位置，以此類推，得到了置換樣本集合。

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

2 FSPRP 算法

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

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

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

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

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

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 所示。

表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的固定樣本結合（表示為D*1），與D2中包含xu的固定樣本結合（表示為D*2），與D1和D2中不包含xu的固定樣本結合（表示D～）。當且僅當包含x*的可置換樣本被置換到D*1和D*2中時，才能生成相應的包含x的樣本。設中x*的數量為q，D*2中x*的數量為r，那么x*在固定屬性置換過程生成的置換樣本集合中的數量分布如表2 所示。從表2 可以看出，q和r決定著x*在置換樣本集合中的分布情況，對于每個q會存在多個與之匹配的r，反之亦然。當q和r確定后，x在置換樣本集合中的數量分布也隨之確定。

表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|+ssup（x，D1）-|D|｝，最大值U（v）為min｛ssup（x，D），|D1|｝。由于每個v對應一個對比性度量值，因此可以通過從小到大遞增v得到所有的對比性度量值。至于每個對比性度量值對應的次數，可通過模擬D′1中恰好有v條樣本包含x的置換樣本集合生成計算得到，先從包含x的樣本ssup（x，D）中選取v條放入中，然后從不包含x的樣本|D| -ssup（x，D）中選取|D1| -v條放入中，最后將余下的樣本放入中。因此，該置換樣本集合的數量如式（4）所示：

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

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

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

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

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

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

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 所示，其中對連續的屬性值進行了離散化。

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

4.2 實驗結果

4.2.1 返回的模式數量

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

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

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

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

4.2.2 分類預測結果

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

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

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

表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 所示。

表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給定的情況下，每次構建的零分布都是相同的，因此其結果始終相同。

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

圖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 算法在對樣本集合進行一次挖掘后，只需要模擬固定屬性置換過程生成置換樣本集合就能夠計算得到零分布，而不用實際生成置換樣本集合，這樣就大幅減少了運行時間。

圖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 算法的一次數據挖掘方法，以減少運行時間。此外，將固定屬性置換檢驗方法應用于解決序列數據中冗余對比模式的過濾問題，也將是下一步研究的重點方向。