吳 軍，歐陽艾嘉，張 琳

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

0 概述

在現(xiàn)實世界的許多應(yīng)用中都存在大量的序列數(shù)據(jù)，如基因序列、文本序列、軌跡序列等。發(fā)現(xiàn)序列數(shù)據(jù)中的序列模式是一個十分重要的研究問題［1-2］。其中，在不同類型的序列數(shù)據(jù)分布中呈現(xiàn)顯著對比性的模式被稱作對比序列模式［3］。對比序列模式具有非常重要的應(yīng)用價值，比如在生物蛋白質(zhì)序列中發(fā)現(xiàn)生物標記［4］、在風險評估和管理中預防攻擊行為［5］等。

為了挖掘?qū)Ρ刃蛄心Ｊ剑恍┓椒ū幌嗬^提出［3，6-8］。這些方法將注意力主要集中在對比性度量選擇以及閾值約束設(shè)定上，使得結(jié)果中會存在一定數(shù)量偶然滿足了算法約束但不能體現(xiàn)真實對比性的對比序列模式。這樣的模式被稱為假陽性模式，它們提供的錯誤信息會對后續(xù)分析產(chǎn)生嚴重的干擾。

DSPM-MTC 方法運用統(tǒng)計顯著性檢驗過濾了結(jié)果中的部分假陽性對比序列模式［9］，其使用直接計算法來計算p-value 值。在統(tǒng)計顯著性檢驗中，每個被檢驗的對比序列模式會根據(jù)其分布信息計算得到一個p-value 值，該值的大小度量了其統(tǒng)計顯著性。對比序列模式的p-value 值越小，則為假陽性模式的可能性就越小。

標準置換檢驗是一種常用的統(tǒng)計顯著性檢驗方法，在非序列數(shù)據(jù)的模式發(fā)現(xiàn)任務(wù)中其檢驗效力高于直接計算法［10］。標準置換檢驗通過置換數(shù)據(jù)類型標簽生成一定數(shù)量的置換數(shù)據(jù)集合，從中計算得到對比性度量值并建立相應(yīng)的零分布，從而由該零分布計算得出被檢驗的對比序列模式的p-value 值。值得注意的是，標準置換檢驗通常只執(zhí)行一定次數(shù)的置換過程，因此其生成的只是精確零分布的一個近似零分布。使用該近似零分布檢驗挖掘結(jié)果存在p-value 值可能為0、零分布共享、結(jié)果不唯一和計算開銷大4 個缺點，這些缺點限制了標準置換檢驗的實用性。

經(jīng)過分析發(fā)現(xiàn)，導致標準置換檢驗上述缺點的原因是其構(gòu)建的零分布是一個共享近似零分布。為此，本文提出一種通過模擬置換過程構(gòu)建獨立精確零分布的解決方案。通過設(shè)計基于獨立精確置換檢驗的IEP-DSP 算法，挖掘統(tǒng)計顯著的對比序列模式，找到原始數(shù)據(jù)集合中和置換數(shù)據(jù)集合中的對比序列模式，并根據(jù)長度進行分組，計算置換數(shù)據(jù)集合每組中各個模式的對比性度量值分布，合并置換數(shù)據(jù)集合每組中的對比性度量值分布構(gòu)建各自的獨立精確零分布，通過獨立精確零分布計算原始數(shù)據(jù)集合每組中候選對比序列模式的精確p-value 值，并運用錯誤發(fā)現(xiàn)率（False Discovery Rate，F(xiàn)DR）度量將每組的假陽性模式數(shù)量約束在置信度為α的統(tǒng)計顯著水平下，以保留更多的真對比序列模式。

1 相關(guān)工作

數(shù)據(jù)挖掘領(lǐng)域的目標是從數(shù)據(jù)中發(fā)現(xiàn)有價值的信息。為了得到正確信息，對數(shù)據(jù)挖掘算法結(jié)果進行評估成為當前熱門研究問題［11-13］。在對比序列模式挖掘任務(wù)中，傳統(tǒng)的挖掘算法將注意力放在了約束度量的設(shè)計和挖掘效率的優(yōu)化上［3，6-8］，沒有對挖掘到的對比序列模式進行質(zhì)量評估，即判別挖掘到的模式是否真實地體現(xiàn)了數(shù)據(jù)類別的特征。

運用統(tǒng)計顯著性檢驗評估挖掘到的模式質(zhì)量成為模式發(fā)現(xiàn)領(lǐng)域中熱門研究方向，并相繼提出一些不同策略的統(tǒng)計顯著性檢驗方法。這些方法在模式挖掘過程中評估模式質(zhì)量，或者在挖掘后的結(jié)果中進行模式質(zhì)量評估。BRIN 等［14］運用chi-square 檢驗評估挖掘到統(tǒng)計顯著性模式，然后根據(jù)一個設(shè)定的閾值過濾掉非統(tǒng)計顯著的模式；ZHANG 等［15］定義了一種新的模式SQ 規(guī)則，并提出了一種隨機檢驗的方法用于發(fā)現(xiàn)統(tǒng)計顯著的SQ 規(guī)則。WEBB［16］認為上述方法隨著假設(shè)數(shù)量的增加，假陽性模式的數(shù)量也會增加，并針對該缺點，提出了直接計算法。LIU等［10］運用標準置換檢驗發(fā)現(xiàn)統(tǒng)計顯著模式，并提出一次挖掘技術(shù)和預存儲技術(shù)減少標準置換檢驗的計算開銷；隨后，研究人員提出2 個改進的置換檢驗算法［17-18］，這2 個算法避開挖掘計算生成零分布，運用westfall-young 置換過程計算得到模式的置換檢驗近似p-value，從而提升了置換檢驗用于模式發(fā)現(xiàn)任務(wù)的效率；PELLEGRINA 等［19］設(shè)計了Spumante 算法，該算法運用一種新穎的無條件檢驗找到統(tǒng)計顯著的模式。無條件檢驗與Fisher 檢驗等條件檢驗相比，對數(shù)據(jù)的假設(shè)要求更少。

以上方法僅在非序列數(shù)據(jù)的模式發(fā)現(xiàn)問題中得到了驗證。為了提高序列數(shù)據(jù)中挖掘到的模式的質(zhì)量，HE 等［9］設(shè)計了DSPM-MTC 算法挖掘統(tǒng)計顯著的對比序列模式。該算法首先生成每個被檢驗模式的超幾何分布，然后根據(jù)該分布直接計算得到模式的p-value 值并進行非統(tǒng)計顯著模式過濾，這種根據(jù)服從分布計算p-value 值的方法稱為直接計算法。文獻［10］驗證了在非序列數(shù)據(jù)集中，標準置換檢驗方法的性能優(yōu)于直接計算法，但是由于置換的隨機性，標準置換檢驗存在4 個缺點。為探索置換檢驗對序列數(shù)據(jù)模式發(fā)現(xiàn)任務(wù)的有效性，并考慮到標準置換檢驗的缺點，本文提出使用獨立精確置換檢驗的IEP-DSP 算法挖掘統(tǒng)計顯著的對比序列模式，以進一步提升報告的對比序列模式的質(zhì)量。

2 問題描述

2.1 對比序列模式挖掘

令字母表為E=｛e1，e2，…，e|E|｝，一個序列模式t是由E中元素構(gòu)成的一個有序符號列表，其中mi∈E。如果一個序列模式t包含k個元素，則t的長度為k。給定2 個序列模式t1=和，如果t2的每一個元素m*

j都存在于t1中，且符合t1的元素順序，則t2被稱作是t1的子序列，表示為給定一個包含n條序列的數(shù)據(jù)集合D=｛s1，s2，…，sn｝和某個序列模式t，t在D中的支持度sup（t，D）被定義為即D中包含t的序列數(shù)量。當且僅當序列模式t在D中的支持度超過了自定閾值θsup，t就被認為是D中的頻繁序列模式。目前，已經(jīng)提出了許多頻繁序列模式挖掘算法［20］，如GSP、Spade、PrefixSpan 等算法。

假設(shè)數(shù)據(jù)集合D含有ν個類型標簽，即D=｛D1，D2，…，Dν｝，若序列模式t在不同Di中的支持度sup（t，Di）呈現(xiàn)顯著對比性，則t被稱為對比序列模式。上述對比性可以由不同的對比性度量量化［21］，例如Growth rate、Diffsup、OddsRatio 等。為了便于闡明本文提出方法，后續(xù)討論均假定D=｛D1，D2｝。

對比序列模式挖掘任務(wù)的目標是找到所有支持度不小于θsup且對比度性度量值不小于θdis的序列模式，即頻繁且存在對比性的序列模式。

2.2 標準置換檢驗

由于傳統(tǒng)的對比序列模式挖掘算法只考慮了對比性度量約束，從而結(jié)果中會存在一定數(shù)量的假陽性模式，假陽性模式?jīng)]有真正體現(xiàn)不同類型數(shù)據(jù)集的對比特征。統(tǒng)計顯著性檢驗被廣泛應(yīng)用于假陽性結(jié)果的過濾，運用統(tǒng)計顯著性檢驗進行質(zhì)量評估時，建立的零假設(shè)為對比序列模式在D1和D2中具有相同的分布。同時，每個對比序列模式會被分配一個p-value 值度量其統(tǒng)計顯著性。一個對比序列模式t的p-value 值的定義是在假設(shè)零假設(shè)為真的前提下，獲得一個至少與t同樣極端的對比序列模式的概率，這里的極端主要體現(xiàn)在對比性度量值的大小。

一般地，可以通過設(shè)定一個p-value 值的置信度閾值α決定是否拒絕零假設(shè)，但當有多個對比序列模式需要被同時檢驗時，即多重假設(shè)檢驗，這種策略會導致假陽性結(jié)果的增加。FDR 是多重假設(shè)檢驗中常用的度量約束，其定義是整個結(jié)果中假陽性對比序列模式比例的期望值，可以使用BH 方法約束整個結(jié)果的FDR 值［22］。

標準置換檢驗是一種常用的統(tǒng)計顯著性檢驗方法［10］，其核心過程如圖1 所示。首先，挖掘原始數(shù)據(jù)集合D1中的候選對比序列模式R；然后，根據(jù)零假設(shè)生成一定數(shù)量的置換數(shù)據(jù)集合，挖掘并計算每個置換數(shù)據(jù)集合中對比序列模式的對比性度量值；最后，用所有計算得到的對比性度量值建立該置換檢驗的零分布，并通過該零分布計算所有候選對比序列模式的p-value 值。

圖1 標準置換檢驗過程Fig.1 Process of standard permutation testing

在標準置換檢驗中，窮舉生成一個集合所有可能的置換數(shù)據(jù)集合是不切實際的，所以通常只產(chǎn)生一定數(shù)量的置換數(shù)據(jù)集合，這導致了構(gòu)建的零分布不是精確零分布。使用該近似零分布進行模式統(tǒng)計顯著性評估存在以下4 個缺點：

1）某些對比序列模式的p-value 值計算結(jié)果為0；

2）共享同一個零分布會增大模式之間的互相影響；

3）同一數(shù)據(jù)集進行多次檢驗得到的統(tǒng)計顯著的對比序列模式數(shù)量不一致；

4）增大置換次數(shù)會導致計算開銷的顯著增大。

這些缺點會大幅降低標準置換檢驗的實用性。分析發(fā)現(xiàn)造成標準置換檢驗4 個缺點的根本原因是置換過程構(gòu)建了一個共享近似零分布。因此，快速構(gòu)建獨立精確零分布是去除4 個缺點的一個可行的解決方案。

3 IEP-DSP 算法

IEP-DSP 算法從序列數(shù)量分布出發(fā)，運用排列組合的思想模擬置換過程，直接計算得到不同長度對比序列模式的置換檢驗獨立精確零分布。

3.1 候選對比序列模式

IEP-DSP 算法選定WRAcc（Weighted Relative Accuracy）作為對比性度量［21］。給定一個對比序列模式t，其WRAcc 值主要考慮了2 個部分信息：t的相對支持度和t的支持度比率與數(shù)據(jù)比率的差別。具體的WRAcc 值的計算公式為：

其中：q表示D1中包含t的序列數(shù)量，即支持度sup（t，D1）。

IEP-DSP 算法運用Spade 算法挖掘頻繁序列模式［23］。Spade 算法先將數(shù)據(jù)集中的序列表示為垂直結(jié)構(gòu)，再運用序列聯(lián)合操作構(gòu)建樹形結(jié)構(gòu)以找到所有的頻繁序列模式。如果一個頻繁序列模式的對比性度量值超過了閾值θdis，則該頻繁序列模式被稱為候選對比序列模式，表示為to。

3.2 獨立精確置換檢驗

給定置換數(shù)據(jù)集合中的一個對比序列模式t′，數(shù)據(jù)置換過程會改變它在置換數(shù)據(jù)集合和中的序列數(shù)量分布。假設(shè)t′在中的支持度為q′，則它在和中的序列數(shù)量分布如表1 所示。

表1 模式t 的序列數(shù)量分布Table 1 Sequence number distribution of pattern t

從表1 可以看出，給定q′值后其余數(shù)值均可以寫成基于q′的計算公式，即對于一個確定的q′，t′在和的數(shù)量分布是唯一的。

獨立精確置換檢驗的過程如圖2 所示。首先，找到候選對比序列模式R和所有可能在置換數(shù)據(jù)集合中出現(xiàn)的對比序列模式R′，并根據(jù)模式長度進行各自分組；其次，針對集合中每個對比序列模式t′，計算出其相應(yīng)的對比性度量值分布；再次，合并集合中每個對比序列模式t′的對比性度量值分布即得到對應(yīng)的獨立精確零分布；最后，從獨立精確零分布中計算出Rk中每個候選對比序列模式的精確p-value 值。

圖2 獨立精確置換檢驗過程Fig.2 Process of independent exact permutation testing

獨立精確置換檢驗最關(guān)鍵的步驟是每個模式對比性度量值分布的計算，該分布由對比性度量值和其在置換數(shù)據(jù)集合中的次數(shù)構(gòu)成。給定一個t′，t′的每個q′僅對應(yīng)一個對比性度量值，即wra（t′，q′）。q′的最小值L（t′）為min｛θsup，|D1|+sup（t′，D1）-|D|｝，最大值U（t′）為min｛sup（t′，D），|D1|｝，因此q′∈［L（t′），U（t′）］。

t′的每個對比性度量值在置換數(shù)據(jù)集合中相應(yīng)的次數(shù)，可以通過以下模擬置換過程計算得出：

其中：g1（t′，q′）表示從D中含有t′的序列中隨機拿出q′條放入中；g2（t′，q′）表示從D中不含t'的序列中隨機拿出|D1|-q′條放入中。因此，g1（t′，q′）與g2（t′，q′）相乘表示只有q′條序列含有t′的置換數(shù)據(jù)集合的數(shù)量。同時，再考慮和內(nèi)部序列的排列可能性：|D1|！和|D2|！，式（4）的結(jié)果即是wra（t′，q′）值在置換數(shù)據(jù)集合中相應(yīng)的次數(shù)。

從而，Rk中每個候選對比序列模式to的精確p-value 值計算如下：

其中：W表示中比to更極端的模式對應(yīng)的序列數(shù)量分布集合，即W=｛q′|wra（to，sup（to，D1）≤wra（t′，q′））｝。

從式（6）可以得知，最終精確p-value 值的計算公式的分子分母均為式（4）的累加結(jié)果。因此，為了減少計算開銷，可以刪去式（4）中的|D1|！和|D2|！項，即：

3.3 約束度量

計算得到Rk中每個候選對比序列模式的精確p-value值后，IEP-DSP 算法運用BH 方法將Rk中的FDR 度量值約束在置信度為α的統(tǒng)計顯著水平下。具體而言，先將Rk中候選對比序列模式按照p-value 值從小到大排序進行排列得到Ck，然后進行如下計算：

最終非統(tǒng)計顯著的對比序列模式ci將被過濾。

3.4 IEP-DSP 算法步驟

根據(jù)以上討論，詳細的IEP-DSP 算法步驟見算法1。

算法1 相應(yīng)的解釋如下：

1）運用pattern_mining（）方法挖掘D1中的候選對比序列模式并放入集合R（第1 步）；運用pattern_mining（）方法挖掘D中的對比序列模式并放入集合R'，R'中的模式即是所有可能在置換數(shù)據(jù)集合中出現(xiàn)的對比序列模式（第2 步）。

2）運用len_cla（）方法將R和R'中的模式根據(jù)長度進行分組（第3 步、第4 步）。對于每個，分別用iend_generation（）方法建立其對應(yīng)的獨立精確零分布Ik（第5 步、第7 步）。

3）對于每個獨立精確零分布Ik，根據(jù)zwr值的降序排列所有對，并根據(jù)該順序累加Ik中對的znc值（第8 步～第11 步）。上述操作是為了快速檢索大于等于某個對比性度量值的WRAcc值的個數(shù)。每個Ik中最后一個對的znc值即是該獨立精確零分布中所有的WRAcc 值個數(shù)。

4）對于Rk中每個候選對比序列模式to，運用find_wra（）方法找到比to更極端的模式數(shù)量x；隨后to的精確p-value 值可由x/last_nc（Ik）計算得出，其中l(wèi)ast_nc（）返回Ik中最后一個對的znc值（第12 步～第16 步）。

5）運用redundancy_remove（）方法過濾Rk中冗余模式。這里的冗余模式指的是p-value 值大于等于任一子模式的p-value 值的候選對比序列模式；再運用p_sort（）方法根據(jù)p-value 值從小到大排序模式后，就能夠使用BH（）方法將每組Rk中的FDR 控制在置信度為α的統(tǒng)計顯著水平下，最終，合并所有即得到統(tǒng)計顯著的對比序列模式集合C*（第17 步～第20 步）。

IEP-DSP 算法各步驟的時間復雜度分析：頻繁模式挖掘算法的時間復雜度分析見文獻［23］，其對IEP-DSP 算法的時間復雜度影響不大；模式長度分組操作可以在模式數(shù)量的線性階時間內(nèi)完成；構(gòu)建每個對應(yīng)的獨立精確零分布操作等同于計算R′中每個對比序列模式t′的對比性度量值分布，因此該操作的時間復雜度為O（|R′|avg（U（t′）-L（t′））；排序操作和累加操作可以在統(tǒng)計度量值數(shù)量的線性對數(shù)階和線性階時間內(nèi)完成；p-value 值計算操作、去冗余操作和FDR 計算操作均可在模式數(shù)量的線性階時間內(nèi)完成。從上述分析可知：IEP-CSP 算法的時間復雜度主要由構(gòu)建獨立精確零分布操作決定，即O（|R′|avg（U（t′）-L（t′））。

從式（1）和式（4）中可以發(fā)現(xiàn)，如果置換數(shù)據(jù)集合中2 個對比序列模式和在D中的支持度相同，即sup（，D）等于sup（，D），那么和構(gòu)建的對比性度量值分布就相同。為了減少IEP-DSP 算法的時間復雜度，支持度相同的模式的對比性度量值分布只需計算1 次即可。因此，IEP-DSP 算法的時間復雜度減少為，其中表示合并R′中所有支持度相同的對比序列模式的結(jié)果。

4 實驗

為了驗證IEP-DSP 算法的有效性，在真實數(shù)據(jù)集和仿真數(shù)據(jù)集上進行了大量對比實驗。對比的方法包括SP-DSP 算法、DSPM-MTC 算法［9］、ESM 算法［7］和IMP 算法［3］。其中，SP-DSP 算法使用標準置換檢驗挖掘?qū)Ρ刃蛄心Ｊ?。在所有算法中，ESM 算法和IMP 算法是基于對比性度量約束的挖掘算法，IEP-DSP算法、SP-DSP 算法和DSPM-MTC 算法是基于統(tǒng)計顯著性檢驗的挖掘算法，且這3 個算法均使用FDR 作為約束。所有實驗均使用一臺配置為2.40 GHz CPU和12 GB 內(nèi)存的電腦設(shè)備。

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

4.1.1 數(shù)據(jù)信息

實驗選用了4 個不同類型的真實數(shù)據(jù)集，即Epitope［24］、Unix［25］、Question［26］和Phospep［27］。Epitope是抗原蛋白序列的數(shù)據(jù)集；Unix 是用戶操作序列的數(shù)據(jù)集；Question 是文本序列的數(shù)據(jù)集；Phospep 是磷酸化肽段序列的數(shù)據(jù)集。數(shù)據(jù)集的詳細信息如表2 所示，其中，kmin、kmax和kavg分別表示序列最短長度、序列最長長度和序列平均長度。

表2 真實數(shù)據(jù)集信息Table 2 Information of the real data sets

4.1.2 真實數(shù)據(jù)集實驗結(jié)果

為評估每個算法的挖掘能力，本文首先對比了每個算法在相同參數(shù)下（θsup，θdis，α）報告的對比序列模式數(shù)量，結(jié)果如圖3 所示。從實驗結(jié)果可以看出：基于統(tǒng)計顯著性檢驗的方法得到的模式數(shù)量遠小于基于對比性度量約束的方法，這是因為基于統(tǒng)計顯著性檢驗的方法除了考慮對比性度量約束外，還會考慮統(tǒng)計顯著性約束；在基于對比性度量約束的方法中，ESM 算法得到的模式數(shù)量非常多，其原因是ESM 算法沒有使用去冗余的方法；在基于統(tǒng)計顯著性檢驗的方法中，IEP-DSP 算法比SP-DSP 算法、DSPM-MTC 算法報告的模式數(shù)量更多，這表明獨立精確置換檢驗能夠拒絕更多的零假設(shè)。

圖3 每個算法在不同的數(shù)據(jù)集上報告的對比序列模式數(shù)量Fig.3 Number of contrast sequential patterns reported by each method on different data sets

由于真實數(shù)據(jù)集中對比序列模式真假信息的缺失，不能直接根據(jù)各個算法報告的模式結(jié)果評價其有效性，因此后續(xù)實驗采用一種間接的分類預測方法評估返回的模式質(zhì)量［28］，即根據(jù)每個算法報告的模式信息，為數(shù)據(jù)集中的每條序列構(gòu)建一個特征向量，將該向量送入分類器進行預測。特征向量的每個值是該序列和模式的包含關(guān)系，即包含為1，不包含則為0。該實驗能夠間接反映挖掘到的模式的真假性的原因是：真對比序列模式本質(zhì)上體現(xiàn)了不同類型序列數(shù)據(jù)的相異性。為了減小分類器本身影響，實驗采用了3 種不同類型的分類器，分別為樸素貝葉斯、支持向量機和多層感知機。實驗結(jié)果如表3～表5 所示，每個正確率值均取自于10 次預測結(jié)果的平均值。

表3 樸素貝葉斯分類器的分類正確率Table 3 Classification accuracy reported by the Naive Bayes classifier

表4 支持向量機分類器的分類正確率Table 4 Classification accuracy reported by the support vector machine classifier

表5 多層感知機分類器的分類正確率Table 5 Classification accuracy reported by the multilayer perceptron classifier

從不同分類器的分類結(jié)果中可以看出：基于統(tǒng)計顯著性檢驗的方法的分類正確率高于基于對比性度量約束的方法。因此，可以說明基于統(tǒng)計顯著性檢驗的方法過濾了許多假陽性對比序列模式。以Question 數(shù)據(jù)集為例，基于對比性度量約束的方法會返回和模式，而基于統(tǒng)計顯著性檢驗的方法只有和模式。is 和the 在英文句子中出現(xiàn)頻率很高，且通常作為語法結(jié)構(gòu)出現(xiàn)，因此它們無法表現(xiàn)句子的差別，從而給分類器造成干擾。

基于統(tǒng)計顯著性檢驗的3 種算法的準確率高低排序為：IEP-DSP 算法>SP-DSP 算法>DSPM-MTC 算法，這個結(jié)果證明了IEP-DSP 算法能夠保留更多的真對比序列模式。以Phospep 數(shù)據(jù)集實驗結(jié)果為例，IEP-DSP 算法保留了模式，而SP-DSP 算法和DSPM-MTC 算法只保留了模式，從而導致7 條包含的磷酸化肽段被分類為非磷酸化肽段，此現(xiàn)象說明了模式應(yīng)該是真對比序列模式。綜上，IEP-DSP 算法不僅能夠過濾大量假陽性模式，還能夠盡可能地保留真對比序列模式。

4.1.3 IEP-DSP 算法與SP-DSP 算法

在2 個置換檢驗算法中，IEP-DSP 算法使用的是獨立精確置換檢驗構(gòu)建精確零分布，SP-DSP 算法使用的是標準置換檢驗構(gòu)建共享近似零分布。為了證明獨立精確零分布能夠去除共享近似零分布的4 個缺點，本文進行了以下的討論和實驗。

在SP-DSP 算法報告的結(jié)果中，存在一定數(shù)量p-value 值為0 的對比序列模式。這是因為SP-DSP算法生成的置換數(shù)據(jù)集合中沒有找到比這些模式更為極端的模式存在。而在IEP-DSP 算法報告的結(jié)果中，所有模式的p-value 值均不為0。這是因為IEP-DSP 算法考慮了所有的置換數(shù)據(jù)集合，總能找到至少和這些模式一樣極端的模式存在。p-value值等于0 是一個非常差的近似值，它表達的意義是這些模式的統(tǒng)計顯著性無窮大。然而，在某些非常謹慎的應(yīng)用中，即使α設(shè)置得非常小也無法過濾掉這些模式。

在SP-DSP 算法中，不同長度模式的p-value 值均通過同一個共享零分布計算得到；而在IEP-DSP算法中，不同長度模式的p-value 值通過各自的獨立零分布計算得到。在共享零分布中，子模式和超模式之間存在相應(yīng)序列數(shù)據(jù)的反單調(diào)性，從而在計算p-value 值時會存在一定程度的互相干擾，這個情況導致了SP-DSP 算法報告的模式數(shù)量少于IEP-DSP算法。

圖4（a）展示了在Phospep 數(shù)據(jù)集上運行100 次IEP-DSP 算法和SP-DSP 算法返回的結(jié)果?？梢钥闯觯篠P-DSP 算法結(jié)果會有波動，而IEP-DSP 算法結(jié)果是唯一的。這是因為標準置換檢驗中置換數(shù)據(jù)集合的生成存在隨機性，從而構(gòu)建的近似零分布也存在隨機性，而獨立精確置換檢驗構(gòu)建的每個獨立精確零分布都是唯一的。標準置換檢驗的隨機性導致了SP-DSP 算法難以判定處于閾值邊界的對比序列模式的統(tǒng)計顯著性，可以采用多次運行取平均的方法，但這必然會導致計算開銷的大幅提升。

圖4（b）展示了在Unix 數(shù)據(jù)集中IEP-DSP 算法和SP-DSP 算法的運行時間?？梢钥闯觯篒EP-DSP 算法的運行時間顯著低于SP-DSP 算法的運行時間，其原因是IEP-DSP 算法不需要實際生成置換數(shù)據(jù)集合，而SP-DSP 算法不僅需要實際生成一定次數(shù)的置換數(shù)據(jù)集合，還需要對置換數(shù)據(jù)集合進行挖掘。此外，對于不同的數(shù)據(jù)集合而言，很難確定需要執(zhí)行多少次置換才能得到一個誤差較小的近似零分布。為了得到更準確的近似零分布，SP-DSP 算法需要增加置換次數(shù)，這會導致SP-DSP 算法需要的更多的運行時間。

圖4 2 種算法的對比序列模式數(shù)量和運行時間Fig.4 Distinguishing seguential patterns number and running time of two algorithms

綜上，IEP-DSP 算法能夠去除SP-DSP 算法的4 個缺點。這體現(xiàn)了獨立精確置換檢驗相較于標準置換檢驗的優(yōu)勢。

4.2 仿真數(shù)據(jù)集實驗

4.2.1 數(shù)據(jù)生成

由于真實數(shù)據(jù)集缺少對比序列模式真假的信息，實驗生成了仿真實驗數(shù)據(jù)進一步驗證各個算法的有效性。仿真數(shù)據(jù)的生成步驟如下：

1）假設(shè)Efalse=｛e1，e2，…，e30｝表示隨機元素字母表，Etrue=｛e31，e32，…，e42｝表示植入元素字母表。

2）從Efalse中隨機挑選元素生成4 000 條長度為30 的序列數(shù)據(jù)組成D2；從D2中隨機挑選800 條序列數(shù)據(jù)組成D1。

3）從Etrue中隨機挑選6 個字母作為長度為1 的對比序列模式，并指定任意4 個模式的支持度范圍為150～190，余下2 個模式支持度范圍為40～80。6 個模式的支持度的和等于800。為每個模式選擇1 個位置進行植入，具體做法是直接用模式替代D1序列中相應(yīng)元素，同時每條序列數(shù)據(jù)包含且只包含1 個長度為1 的植入模式。

4）從Etrue中挑選未使用的4 個字母同支持度最高的4 個長度為1 的模式結(jié)合生成長度為2 的對比序列模式。其中，支持度最高的2 個長度為1 的模式生成的長度為2 的模式支持度范圍為110～150，其余2 個生成的長度為2 的模式支持度范圍為40～80。植入方式同第3 步。

5）從Etrue中選擇未使用的2 個字母同支持度最高的2 個長度為2 的模式結(jié)合生成長度為3 的對比序列模式，這2 個長度為3 的模式的支持度范圍為40～80。植入方式同第3 步。

通過上述步驟，人為植入了6 個長度為1、4 個長度為2 和2 個長度為3 的對比序列模式。同時，在挖掘算法返回的對比序列模式中，如果某個對比序列模式包含Etrue中的元素，則該模式被認定為真對比序列模式；反之，如果某個對比序列模式僅包含Efalse中的元素，則該模式被認定為假陽性對比序列模式。

4.2.2 仿真數(shù)據(jù)實驗結(jié)果

為減小隨機性的影響，實驗共生成了10 組仿真數(shù)據(jù)集。各個算法返回的對比序列模式信息如表6所示，其中每個結(jié)果取自于10 個仿真數(shù)據(jù)集挖掘結(jié)果的平均值。從表6 可以看出，基于對比性度量約束的ESM 算法和IMP 算法都報告了許多對比序列模式，其中大部分模式為假陽性對比序列模式；而基于統(tǒng)計顯著性檢驗的DSPM-MTC 算法、SP-DSP 算法和IEP-DSP 算法報告的模式數(shù)量較少，且大部分為真對比序列模式。在這3 種方法中，IEP-DSP 算法報告的模式數(shù)量最多，且假陽性對比序列模式最少，這證明了IEP-DSP 算法能過濾掉大量對比性度量約束方法中報告的假陽性模式，且相較于SP-DSP 算法和DSPM-MTC 算法能夠保留更多的真對比序列模式，體現(xiàn)了IEP-DSP 算法挖掘?qū)Ρ刃蛄心Ｊ降膬?yōu)勢。值得注意的是，ESM 算法報告了許多真對比序列模式，這是因為ESM 算法沒有使用去冗余方法，從而導致了大量真對比序列模式實際上提供了重復的信息。

表6 不同算法的真對比序列模式和假陽性模式數(shù)量Table 6 Number of true distinguishing seguential patterns and false positive patterns of different algorithms

5 結(jié)束語

為過濾對比序列模式挖掘算法中存在的大量假陽性模式，本文提出一種面向?qū)Ρ刃蛄心Ｊ降莫毩⒕_置換檢驗挖掘算法。該算法能為不同長度的模式分別構(gòu)建獨立精確零分布，從而能夠計算出精確p-value 值。實驗結(jié)果表明，該算法不僅能夠去除一定數(shù)量的假陽性對比序列模式，且能夠比其他統(tǒng)計顯著性檢驗方法保留更多的真對比序列模式，驗證了獨立精確置換檢驗相較于標準置換檢驗的優(yōu)越性。此外，本文算法傾向于保留較短的對比序列模式，主要是因為其采用了去冗余方法，即如果一個對比序列模式t的p-value 值大于其任何一個子模式tsub的p-value 值，則該對比序列模式被認定為冗余模式。由于t和tsub的支持度具備反單調(diào)性關(guān)系，因而tsub會對t的統(tǒng)計顯著性產(chǎn)生影響，但該影響不具備反單調(diào)性關(guān)系。單純地運用p-value 值比較方法能夠去除掉一定數(shù)量的冗余模式，但是也會過濾掉一些非冗余模式。因此，下一步將研究更優(yōu)的去除子對比序列模式統(tǒng)計顯著性影響的方法。