面向?qū)Ρ刃蛄心Ｊ桨l(fā)現(xiàn)的獨(dú)立精確置換檢驗(yàn)算法

吳 軍，歐陽艾嘉，張 琳

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

0 概述

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

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

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

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

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

1 相關(guān)工作

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

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

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

2 問題描述

2.1 對比序列模式挖掘

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

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

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

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

2.2 標(biāo)準(zhǔn)置換檢驗(yàn)

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

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

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

圖1 標(biāo)準(zhǔn)置換檢驗(yàn)過程Fig.1 Process of standard permutation testing

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

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

2）共享同一個(gè)零分布會(huì)增大模式之間的互相影響；

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

4）增大置換次數(shù)會(huì)導(dǎo)致計(jì)算開銷的顯著增大。

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

3 IEP-DSP 算法

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

3.1 候選對比序列模式

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

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

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

3.2 獨(dú)立精確置換檢驗(yàn)

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

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

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

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

圖2 獨(dú)立精確置換檢驗(yàn)過程Fig.2 Process of independent exact permutation testing

獨(dú)立精確置換檢驗(yàn)最關(guān)鍵的步驟是每個(gè)模式對比性度量值分布的計(jì)算，該分布由對比性度量值和其在置換數(shù)據(jù)集合中的次數(shù)構(gòu)成。給定一個(gè)t′，t′的每個(gè)q′僅對應(yīng)一個(gè)對比性度量值，即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′的每個(gè)對比性度量值在置換數(shù)據(jù)集合中相應(yīng)的次數(shù)，可以通過以下模擬置換過程計(jì)算得出：

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

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

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

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

3.3 約束度量

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

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

3.4 IEP-DSP 算法步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在2 個(gè)置換檢驗(yàn)算法中，IEP-DSP 算法使用的是獨(dú)立精確置換檢驗(yàn)構(gòu)建精確零分布，SP-DSP 算法使用的是標(biāo)準(zhǔn)置換檢驗(yàn)構(gòu)建共享近似零分布。為了證明獨(dú)立精確零分布能夠去除共享近似零分布的4 個(gè)缺點(diǎn)，本文進(jìn)行了以下的討論和實(shí)驗(yàn)。

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

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

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

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

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

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

4.2 仿真數(shù)據(jù)集實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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