基于影響度的統(tǒng)計(jì)顯著序列模式挖掘算法

吳 軍，歐陽艾嘉，張琳

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

0 引言

數(shù)據(jù)挖掘技術(shù)能夠從海量數(shù)據(jù)中提取有價(jià)值的信息，幫助人們理解數(shù)據(jù)并做出正確的決策。序列模式發(fā)現(xiàn)是數(shù)據(jù)挖掘領(lǐng)域中一個(gè)核心的研究任務(wù)，該任務(wù)的目標(biāo)是找到序列記錄集合中滿足最小興趣度閾值約束的模式［1］。這些序列模式中蘊(yùn)藏著許多有價(jià)值的信息，因而研究人員將序列模式發(fā)現(xiàn)應(yīng)用到了不同的領(lǐng)域中。例如，在移動網(wǎng)絡(luò)中發(fā)現(xiàn)移動目標(biāo)的行為規(guī)律［2］、在電子政務(wù)中向用戶推薦相關(guān)服務(wù)［3］等。

目前，針對序列模式挖掘任務(wù)，人們提出了許多有效的算法［4-5］，其中大部分算法使用了支持度作為序列模式的興趣度度量方法，并將核心注意力放在了如何高效快速地挖掘滿足約束的序列模式上，即探索高效的生成策略和剪枝方法。通過分析發(fā)現(xiàn)，這些算法存在兩個(gè)問題。

第一個(gè)問題是這些算法使用的支持度是興趣度最基礎(chǔ)的度量方法，在一些情況下無法真實(shí)地體現(xiàn)模式的興趣度，從而導(dǎo)致挖掘到的部分序列模式提供的信息是無價(jià)值的。具體而言，表1 展示了ATS（Adventures of Tom Sawyer）文本序列記錄集合中支持度最大的5 個(gè)序列模式［6］。從表1 中可以看出：一方面，5 個(gè)序列模式均是由ATS 集合中支持度最大的項(xiàng)and、to 和of 組成，即便and、to 和of 不具備任何關(guān)聯(lián)，它們重復(fù)和組合得到的序列模式也很有可能呈現(xiàn)較大的支持度，因此，依據(jù)支持度無法判斷上述5 個(gè)序列模式是否真的有趣。另一方面和兩個(gè)序列模式支持度相差不大，表明and 和to 兩個(gè)項(xiàng)的順序無關(guān)緊要，這與序列模式定義中順序的重要性相違背，這兩個(gè)模式不應(yīng)該出現(xiàn)在最終的結(jié)果中。在以上兩種情況中，支持度均無法真實(shí)地體現(xiàn)序列模式的興趣度。

表1 ATS文本序列記錄集合中支持度最大的5個(gè)序列模式Tab.1 Top-5 sequential patterns with largest degree of support in ATS dataset

第二個(gè)問題是這些算法沒有對挖掘到的序列模式進(jìn)行質(zhì)量評估，導(dǎo)致結(jié)果中會存在大量的假陽性序列模式［7］。假陽性序列模式是隨著數(shù)據(jù)隨機(jī)波動產(chǎn)生的滿足算法興趣度約束的模式，這樣的序列模式?jīng)]有真實(shí)地反映序列記錄集合的總體特征，因此，根據(jù)它們提供的錯誤信息做出的分析和決策會走向錯誤的方向，甚至可能造成重大的損失。

為了更為如實(shí)地度量序列模式的興趣度并減少結(jié)果中的假陽性序列模式，本文提出了一個(gè)基于影響度的統(tǒng)計(jì)顯著序列模式挖掘算法——ISSPM（Influence-based Significant Sequential Patterns Mining）。該算法針對支持度造成的興趣度偏差問題，設(shè)計(jì)了一個(gè)新的興趣度度量方法稱為影響度。該影響度不僅考慮了序列模式包含的項(xiàng)的支持度造成的影響，還考慮了這些項(xiàng)之間的順序特征。針對質(zhì)量評估問題，ISSPM 算法引入了兩個(gè)多重假設(shè)檢驗(yàn)約束：錯誤率發(fā)現(xiàn)族（Family-Wise Error Rate，F(xiàn)WER）和偽發(fā)現(xiàn) 率（False Discovery Rate，F(xiàn)DR）［8］，并提出了一個(gè)面向無類型標(biāo)簽序列記錄集合的置換檢驗(yàn)方法控制結(jié)果中假陽性序列模式的數(shù)量。真實(shí)序列記錄集合和仿真序列記錄集合中的實(shí)驗(yàn)結(jié)果表明，ISSPM 算法報(bào)告的統(tǒng)計(jì)顯著序列模式不僅興趣度更強(qiáng)，而且假陽性序列模式數(shù)量更少，從而這些模式提供的信息更有價(jià)值且更加可靠。

1 相關(guān)工作

模式發(fā)現(xiàn)算法按照面向的數(shù)據(jù)類型可以分為非序列模式挖掘算法和序列模式挖掘算法。在非序列模式挖掘任務(wù)中，文獻(xiàn)［9］中通過構(gòu)建并遞歸地挖掘頻繁模式樹得到頻繁模式，該算法只需要掃描兩次序列記錄集合即可；文獻(xiàn)［10］中采用前綴投影的思想，通過分治法將頻繁模式挖掘工作劃分為獨(dú)立的任務(wù)實(shí)現(xiàn)了并行挖掘；其余非序列模式挖掘算法可以參考文獻(xiàn)［11-12］。在序列模式挖掘任務(wù)中，為了減少候選序列模式的生成，文獻(xiàn)［13］中提出了一個(gè)在投影數(shù)據(jù)中單個(gè)項(xiàng)支持度的計(jì)算方法，并采用深度優(yōu)先的方式遞歸生成序列模式；文獻(xiàn)［14］中使用回溯策略計(jì)算候選序列模式在網(wǎng)絡(luò)樹上的非重疊支持度，并且還設(shè)計(jì)了三種剪枝策略縮小搜索空間；其余序列模式挖掘算法可以參考文獻(xiàn)［4-5］。非序列模式挖掘任務(wù)和序列模式挖掘任務(wù)的區(qū)別在于是否考慮項(xiàng)之間的順序，因而序列模式挖掘任務(wù)通常更具有挑戰(zhàn)性。

以上算法主要在模式挖掘效率方面進(jìn)行了探索，除此之外，研究人員還將注意力投向了興趣度度量方法的研究中。支持度是模式興趣度最為基礎(chǔ)的度量方法，除此以外，在支持度的基礎(chǔ)上還定義了一些其他的度量方法，例如，置信度［15］、提升度［16］和杠桿率［17］等。置信度能夠體現(xiàn)項(xiàng)集與項(xiàng)集之間的聯(lián)系情況；提升度能夠反映模式與包含項(xiàng)之間的獨(dú)立程度；杠桿率能夠弱化項(xiàng)對模式興趣度的影響；但是，以上興趣度度量方法均無法體現(xiàn)模式在不同類型記錄集合中的分布差異。為了刻畫這樣的分布差異，又提出了成長率［18］和比值比［19］等興趣度度量方法。成長率能夠體現(xiàn)模式在不同類型記錄集合中的絕對支持度占比情況，而比值比能夠反映模式在不同類型記錄集合中的相對支持度占比情況。通常而言，符合最小興趣度約束的模式數(shù)量通常較多，為了降低結(jié)果的冗余程度，一些算法從模式集合的角度設(shè)計(jì)了全局興趣度度量方法。例如，文獻(xiàn)［20］中設(shè)計(jì)了覆蓋率，覆蓋率體現(xiàn)了模式與模式之間支持度的依賴情況；文獻(xiàn)［21］中定義了最大子杠桿率，該度量方法考慮了子模式興趣度的影響。關(guān)于不同興趣度度量方法更為詳細(xì)的對比和選擇策略可以參考文獻(xiàn)［22］。

近年來，為了減少結(jié)果中假陽性序列模式的數(shù)量，從而降低錯誤決策造成的損失，使用統(tǒng)計(jì)顯著性檢驗(yàn)評估挖掘到的模式質(zhì)量成為模式發(fā)現(xiàn)任務(wù)中的熱門研究問題。比如，文獻(xiàn)［23］中引入標(biāo)準(zhǔn)置換檢驗(yàn)構(gòu)建零分布以過濾低質(zhì)量的序列模式；文獻(xiàn)［24］中提出了一個(gè)新的無條件檢驗(yàn)，隨后使用該檢驗(yàn)計(jì)算模式的p值并根據(jù)該值返回統(tǒng)計(jì)顯著的序列模式。更多的統(tǒng)計(jì)顯著性檢驗(yàn)評估方法可以參考文獻(xiàn)［7］。

2 基本定義

2.1 序列模式

假設(shè)D=｛d1，d2，…，d|D|｝是一個(gè)有限的序列記錄的集合，其中每一條記錄di是由C中的項(xiàng)構(gòu)成。如果一個(gè)序列s是一條記錄di的子序列，則稱di包含s，表示為s?di。s在D中的覆蓋數(shù)量指的是D中包含s的序列記錄的數(shù)量，即cov(s，D)=| {di|di∈D∧s?di}|。s在D中的支持度被定義為D中包含s的序列記錄的比例，即sup(s，D)=cov(s，D)/|D|。

興趣度是衡量一個(gè)序列是否提供了有用信息的指標(biāo)，其中，支持度是最為基礎(chǔ)的興趣度度量方法。具有興趣度的序列被稱為序列模式。由于單個(gè)項(xiàng)無法表現(xiàn)順序特征，從而只考慮長度大于等于2 的序列模式。序列模式發(fā)現(xiàn)任務(wù)的目的是找到序列記錄集合中滿足最小興趣度閾值θins約束的序列模式，這些滿足約束的序列模式被認(rèn)定為有趣的序列模式。

2.2 統(tǒng)計(jì)顯著序列模式

研究發(fā)現(xiàn)，基于興趣度約束的挖掘算法報(bào)告的結(jié)果中存在一定數(shù)量的假陽性序列模式，即這些序列模式滿足約束的興趣度是由于數(shù)據(jù)隨機(jī)波動性造成的，因此，假陽性序列模式所反映的信息并不能夠體現(xiàn)序列記錄集合的真實(shí)特征。

統(tǒng)計(jì)顯著性檢驗(yàn)方法是常用的過濾假陽性序列模式的途徑。該方法的步驟是：首先構(gòu)建任務(wù)相關(guān)的零假設(shè)；其次定義并收集統(tǒng)計(jì)度量構(gòu)建零分布；最后根據(jù)計(jì)算得到的統(tǒng)計(jì)顯著性拒絕或者接受零假設(shè)。在序列模式發(fā)現(xiàn)任務(wù)中，零假設(shè)為序列模式在原始集合中的興趣度與其在隨機(jī)集合中興趣度一致，即序列模式是由數(shù)據(jù)隨機(jī)波動性產(chǎn)生的。依據(jù)該零假設(shè)，設(shè)計(jì)了統(tǒng)計(jì)度量和相應(yīng)的收集方法，詳細(xì)內(nèi)容見3.1～3.3 節(jié)。在統(tǒng)計(jì)顯著性檢驗(yàn)中，每個(gè)被評估的序列模式s的統(tǒng)計(jì)顯著性由一個(gè)p值度量，p值的定義是在隨機(jī)集合中觀察到比該模式的原始興趣度值更大的興趣度值的概率。p值越小表明該序列模式的統(tǒng)計(jì)顯著性越強(qiáng)。

由于算法報(bào)告的序列模式通常很多，尤其是在興趣度約束閾值設(shè)置得比較小時(shí)，不宜采用單重假設(shè)檢驗(yàn)對序列模式進(jìn)行逐一評估。多個(gè)序列模式被一同評估的情況被稱作多重假設(shè)檢驗(yàn)。錯誤率判斷族和偽發(fā)現(xiàn)率被廣泛應(yīng)用于多重假設(shè)檢驗(yàn)中約束假陽性結(jié)果數(shù)量的上限。其中，錯誤率判斷族的定義是發(fā)現(xiàn)一個(gè)被錯誤拒絕的零假設(shè)的概率；偽發(fā)現(xiàn)率的定義是被錯誤拒絕的零假設(shè)占所有被拒絕的零假設(shè)的比例的期望值。通過統(tǒng)計(jì)顯著性檢驗(yàn)的序列模式被稱為統(tǒng)計(jì)顯著序列模式。統(tǒng)計(jì)顯著序列模式發(fā)現(xiàn)任務(wù)的目標(biāo)是運(yùn)用多重假設(shè)檢驗(yàn)找到在統(tǒng)計(jì)顯著水平為θsig下統(tǒng)計(jì)顯著的序列模式。

3 ISSPM算法

3.1 影響度

觀察發(fā)現(xiàn)直接使用支持度作為序列模式的興趣度度量方法會存在兩個(gè)問題：

1）序列模式包含的項(xiàng)的支持度對其本身的支持度存在著較大影響；

2）序列模式的支持度無法體現(xiàn)包含的項(xiàng)的順序特征。

因此支持度無法如實(shí)地度量某些模式的興趣度。經(jīng)過分析，解決第1 個(gè)問題的一種可行的策略是對序列模式的支持度進(jìn)行修正。具體而言，給定一個(gè)序列模式s=如果構(gòu)成s的各個(gè)項(xiàng)是互相獨(dú)立的，那么由這些項(xiàng)構(gòu)成s的支持度的期望值為：

該期望值表達(dá)的含義是即使s的各個(gè)項(xiàng)之間不具備順序聯(lián)系，s也會有較大的概率在D中出現(xiàn)exsup(s，D) ×|D|次。因此，exsup（s，D）在一定程度上量化了各個(gè)項(xiàng)的支持度對序列模式本身支持度的影響，從而可以通過減去該影響得到s的修正支持度，即：

在問題2）中，給定兩個(gè)序列模式sa=和sb=sa與sb的支持度均超過了最小興趣度閾值θins且比較接近。雖然sa和sb的支持度均滿足θins約束，但它們不應(yīng)該被認(rèn)定為有趣的序列模式，否則這樣會導(dǎo)致c1和c2的順序無關(guān)緊要。造成上述問題的原因是支持度本身沒有考慮項(xiàng)的順序特征。分析發(fā)現(xiàn)，大部分算法在得到一個(gè)長度大于等于2的序列模式時(shí)，都采用了兩個(gè)子模式按照一定的規(guī)則拼接的方式。因此，一種可行的解決問題2）的策略是在忽略拼接規(guī)則的條件下計(jì)算兩個(gè)子模式可能構(gòu)成的序列模式的支持度以判斷這些項(xiàng)的順序是否重要。

其中：Gger表示ger（sa，sb）的結(jié)果集合，avg（）表示Gger集合中序列模式支持度的平均值。上述inf（）被稱作s的影響度，其不僅考慮了s包含的項(xiàng)的支持度對s本身支持度的影響，也考慮了項(xiàng)之間的順序特征。ISSPM 算法將采用影響度作為序列模式的興趣度度量方法和統(tǒng)計(jì)度量方法。

3.2 項(xiàng)集置換

根據(jù)零假設(shè)的定義，生成的隨機(jī)序列記錄集合D'要和原始序列記錄集合D保持特征的一致性，即保證D'中序列記錄數(shù)量與D中相等；D'中序列記錄的長度與D中相等；D'中每個(gè)項(xiàng)的出現(xiàn)頻率與D中相等。如果D'沒有滿足上述要求，將會引入額外的誤差。

標(biāo)準(zhǔn)置換方法是最簡單的生成隨機(jī)序列記錄集合的方式。由于序列模式發(fā)現(xiàn)任務(wù)面向的原始序列記錄集合不一定含有類型標(biāo)簽，從而無法通過直接交換類型標(biāo)簽的方式生成隨機(jī)序列記錄集合［25］，因此，針對無類型標(biāo)簽序列記錄集合設(shè)計(jì)了一種新的置換方法叫作項(xiàng)集置換方法，步驟如下：

1）計(jì)算出D中最短的序列記錄長度lmin，并從1 到lmin隨機(jī)選擇一個(gè)整數(shù)α，該整數(shù)表示每條序列記錄需要交換的項(xiàng)的數(shù)量。

2）生成一個(gè)序列記錄編號的置換順序，再為每條序列記錄隨機(jī)挑選α個(gè)不重復(fù)的項(xiàng)，并記錄下這些項(xiàng)對應(yīng)的位置。

3）針對每一條序列記錄，將對應(yīng)位置的項(xiàng)置換給置換順序中相應(yīng)的序列記錄，置換的位置為該序列記錄在第2）步中記錄的位置。

例如，假定字母表C=｛c1，c2，…，c15｝，D由8 條序列記錄構(gòu)成，序列記錄的最短長度為5，最長長度為9，詳細(xì)情況見圖1（a）。

第一步 假定從1～5 中隨機(jī)選擇的α為3，表示每條序列記錄需要置換3 個(gè)項(xiàng)。

第二步 依據(jù)序列記錄的編號，生成了一個(gè)隨機(jī)的置換順序?yàn)椋篸5，d3，d8，d7，d1，d2，d6，d4；再為每一條序列記錄隨機(jī)挑選3 個(gè)項(xiàng)，并記錄這些項(xiàng)的位置。得到的結(jié)果為｛d1：3，5，7｝，｛d2：4，1，2｝，｛d3：7，3，4｝，｛d4：6，1，3｝，｛d5：1，6，2｝，｛d6：2，5，1｝，｛d7：3，9，4｝，｛d8：5，8，4｝。

第三步 根據(jù)置換順序和項(xiàng)的位置置換相應(yīng)的項(xiàng)，具體而言，將d1的第3、5、7 位置對應(yīng)的項(xiàng)置換到d5的第1、6、2 位置；將d2的第4、1、2 位置對應(yīng)的項(xiàng)置換到d3的第7、3、4 位置；不斷執(zhí)行上述置換操作，直到將d8的第5、8、4 位置對應(yīng)的項(xiàng)置換到d4的第6、1、3 位置就得到了一個(gè)隨機(jī)序列記錄集合D'，如圖1（b）所示。

圖1 項(xiàng)集置換方法生成的隨機(jī)序列記錄集合Fig.1 Random sequential record dataset generated by itemset permuting method

由于項(xiàng)集置換方法沒有生成新的序列記錄，因此其生成的D'包含的序列記錄數(shù)量與D中相等；此外，項(xiàng)集置換方法從每條序列記錄中挑選的項(xiàng)數(shù)量一樣，且保證了這些被挑選的項(xiàng)都被置換到了新的位置，因此其生成的D'中的序列記錄長度和各個(gè)項(xiàng)的出現(xiàn)頻率與D中相等。綜上，項(xiàng)集置換方法滿足一致性中的3 個(gè)要求。

3.3 假陽性結(jié)果約束

使用一定次數(shù)的項(xiàng)集置換方法可以生成多個(gè)不同的隨機(jī)序列記錄集合D'，對每個(gè)D'實(shí)施挖掘能夠得到一定數(shù)量有趣的序列模式，將這些有趣的序列模式的影響度存儲在集合H中就完成了收集統(tǒng)計(jì)度量值的任務(wù)。為了減少收集統(tǒng)計(jì)度量值的計(jì)算開銷，使用文獻(xiàn)［7］中的一次挖掘技術(shù)。此外，考慮到不同長度序列模式之間共用零分布可能會產(chǎn)生一定程度的干擾，從而為不同長度的序列模式構(gòu)建了不同的零分布nud（H，l）。

每個(gè)從D中挖掘得到的序列模式s的統(tǒng)計(jì)顯著性由各自的p值量化。p值表示在給定零假設(shè)為真的前提下，從隨機(jī)序列記錄集合中發(fā)現(xiàn)一個(gè)至少和s的影響度一樣大的序列模式的概率，s的p值計(jì)算公式如下：

為了嚴(yán)格控制假陽性序列模式的數(shù)量，ISSPM 算法使用了多重假設(shè)檢驗(yàn)，即將同一長度的模式一同評估，并引入了Bonferroni 和Benjamini 校正來約束同一長度模式的錯誤率判斷族和偽發(fā)現(xiàn)率［8］，從而約束了假陽性序列模式的數(shù)量。具體而言，錯誤率判斷族通過Bonferroni 校正的計(jì)算公式為：

其中Sl表示D中長度為l的序列模式的集合。在使用Benjamini 校正約束偽發(fā)現(xiàn)率時(shí)，首先需要將Sl中的序列模式根據(jù)p值從小到大的順序進(jìn)行排序得到Sl'，然后通過公式計(jì)算得到：

其中os表示s在S'l中的位置。通過式（9）和式（10）保留的序列模式就是統(tǒng)計(jì)顯著序列模式。

3.4 算法過程

ISSPM 算法首先遞歸地以深度優(yōu)先的方式挖掘滿足最小興趣度閾值約束的序列模式；隨后，使用置換檢驗(yàn)構(gòu)建相應(yīng)的零分布并計(jì)算出被評估模式的p值；最后，依據(jù)不同的多重假設(shè)檢驗(yàn)約束返回各自的統(tǒng)計(jì)顯著序列模式。詳細(xì)的ISSPM 算法步驟見算法1。

算法1 ISSPM（D，C，θins，θsig，β）。

輸入 序列記錄集合D，字母表C，最小興趣度閾值θins，統(tǒng)計(jì)顯著水平θsig，置換次數(shù)β；

輸出 統(tǒng)計(jì)顯著序列模式的集合MFWER和MFDR。

其中，inf_mine（）方法是從序列記錄集合D中挖掘得到滿足興趣度約束θins的模式，其詳細(xì)的步驟見算法2 和算法3；per_test（）方法是使用項(xiàng)集置換方法構(gòu)建零分布，并計(jì)算出被評估序列模式的p值，其詳細(xì)的步驟見算法4；len_divi（）方法是依據(jù)長度對序列模式進(jìn)行分組。

算法2 inf_mine（D，C，θins）。

輸入 序列記錄集合D，字母表C，最小興趣度閾值θins；

輸出 滿足興趣度約束的有趣的序列模式集合G。

算法2 首先將原始序列記錄集合轉(zhuǎn)換成了垂直表示形式Dver，即將每條序列記錄包含多個(gè)項(xiàng)的表示形式轉(zhuǎn)換成每個(gè)項(xiàng)被哪幾條序列記錄所包含的表示形式（第1）步）。隨后，過濾掉支持度小于θins的項(xiàng)（第2）～5）步）。接著，將挖掘過程中代表模式長度的變量l初始化為1；將挖掘過程中存儲有趣的序列模式的集合G初始化為空集（第6）～7）步）。最后，通過遞歸地調(diào)用dep_mine（）方法以深度優(yōu)先的方式找到所有滿足θins約束的序列模式（詳細(xì)步驟見算法3），并將其返回（第8）～9）步）。

算法3 dep_mine（Q，θins，G，l，Dver）。

輸入 用于拼接的模式集合Q，最小興趣度閾值θins，存儲有趣的序列模式集合G，拼接模式的長度l，垂直序列記錄集合Dver；

輸出 無。

算法3 首先將Q中每個(gè)非1 長度的序列模式放入G中，并引入Gcom集合來存儲拼接后滿足θins約束的序列模式（第1）～4）步）；接著，使用pat_comb（）方法對Q中模式進(jìn)行兩兩拼接，拼接的條件是sa和sb模式l-1 個(gè)前綴項(xiàng)必須相同（第5）～6）步）；然后，通過修正支持度zads和可能構(gòu)成的模式集合Gger計(jì)算模式stmp的影響度zinf，如果zinf滿足θins約束，便將其放入Gcom集合中（第7）～12）步）；最后，如果Gcom集合不為空集，將遞歸地使用dep_mine（）方法進(jìn)行l(wèi)+1 長度模式的拼接，直到找到所有影響度滿足θins約束的有趣的序列模式（第13）～15）步）。

算法4 per_test（D，C，G，θins，β）。

輸入 序列記錄集合D，字母表C，有趣的序列模式集合G，最小興趣度閾值θins，置換次數(shù)β；

輸出 計(jì)算出p值的序列模式集合S。

算法4 詳細(xì)的步驟描述如下：

1）利用len_divi（）方法依據(jù)長度對序列模式進(jìn)行分組，分組的目的是使不同長度的序列模式從不同的零分布中計(jì)算p值（第1）步）。

2）采用項(xiàng)集置換方法生成β個(gè)隨機(jī)序列記錄集合D'，并從這些D'中收集統(tǒng)計(jì)度量值（第2）～9）步）。具體而言，首先利用num_sele（）方法得到每條記錄交換的項(xiàng)數(shù)量α；接著利用seq_gene（）和ind_gene（）方法生成隨機(jī)置換順序和每條序列記錄需要交換的項(xiàng)的位置；然后利用ite_perm（）方法依據(jù)置換順序和項(xiàng)的位置進(jìn)行置換得到D'；最后利用inf_upda（）方法更新序列模式在D'中的影響度，并將其保存在集合H中。

3）對于被評估的每組序列模式Gl，使用nud（）方法為該組序列模式建立零分布Hl，再從該零分布計(jì)算出這組中每個(gè)序列模式的p值，最后將這些序列模式返回（第10）～14）步）。

分析ISSPM 算法的步驟，發(fā)現(xiàn)其時(shí)間復(fù)雜度主要由序列模式挖掘、置換檢驗(yàn)和非統(tǒng)計(jì)顯著模式過濾三部分構(gòu)成。在挖掘部分中，找到滿足θins約束的序列模式的算法使用了基于前綴樹構(gòu)建的策略，根據(jù)文獻(xiàn)［13］的分析，其相應(yīng)的時(shí)間復(fù)雜度為O（|D|（lmax）2），其中l(wèi)max表示D中最長的序列記錄長度。在置換檢驗(yàn)部分中，針對每一次置換，首先需要生成隨機(jī)序列記錄集合D'，其相應(yīng)的時(shí)間復(fù)雜度為O（α|D|）；隨后，使用了文獻(xiàn)［7］中的一次挖掘技術(shù)直接更新了G中每個(gè)序列模式在D'中的影響度，即從前綴樹的根以深度優(yōu)先的方式遞歸更新每個(gè)節(jié)點(diǎn)的影響度，其相應(yīng)的時(shí)間復(fù)雜度為O(|G||D|)。置換檢驗(yàn)零分布的構(gòu)建需要執(zhí)行β次置換，因此序列模式置換檢驗(yàn)部分的時(shí)間復(fù)雜度為O(β|D|(α+|G|))。在非統(tǒng)計(jì)顯著模式過濾部分中，主要對|G|個(gè)模式分組并分別進(jìn)行FEWR 和FDR 約束計(jì)算。FWER 和FDR 的計(jì)算開銷為常數(shù)，故該部分的時(shí)間復(fù)雜度為O(|G|)。綜上，ISSPM 算法總的時(shí)間復(fù)雜度為O(|D|(lmax)2+β|D|(α+|G|)+|G|)。

4 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證ISSPM 算法的性能，實(shí)驗(yàn)使用了4 個(gè)真實(shí)序列記錄集合和10 個(gè)仿真序列記錄集合作為實(shí)驗(yàn)數(shù)據(jù)，并對比了3 個(gè)高效的序列模式挖掘算法：PSPM（Prefix-projected Sequential Patterns Mining）［13］、SPDL（Sequential Patterns Discovering under Leverage）［17］和 PSDSP（Permutation Strategies for Discovering Sequential Patterns）［23］。其中：PSPM算法使用支持度作為興趣度度量方法，SPDL 算法使用杠桿率作為興趣度度量方法，PSDSP 算法不僅使用了支持度度量興趣度還采用了置換檢驗(yàn)評估序列模式的質(zhì)量。實(shí)驗(yàn)中，置換檢驗(yàn)的次數(shù)設(shè)置為1 000，所有算法均以Java 語言實(shí)現(xiàn)，實(shí)驗(yàn)設(shè)備為一臺2.40 GHz CPU 和16 GB 內(nèi)存的計(jì)算機(jī)設(shè)備。

4.1 真實(shí)序列記錄集合實(shí)驗(yàn)

4.1.1 真實(shí)序列記錄集合簡介

4 個(gè)不同類型的真實(shí)序列記錄集合分別為：Book、Unix、Peptide 和Bike：Book 是圖書摘要文本的序列記錄集合［21］；Unix 是用戶操作命令的序列記錄集合［26］；Peptide 是人類肽段的序列記錄集合［27］；Bike 是共享單車?？空镜男蛄杏涗浖希?3］。詳細(xì)信息如表2 所示。

表2 真實(shí)序列記錄集合的信息Tab.2 Information of real-world sequential record datasets

4.1.2 真實(shí)序列記錄集合實(shí)驗(yàn)結(jié)果

為了能夠?qū)Ρ雀鱾€(gè)算法挖掘序列模式的能力，實(shí)驗(yàn)首先在相同的興趣度約束θins和統(tǒng)計(jì)顯著性水平θsig下運(yùn)行了各個(gè)算法，然后統(tǒng)計(jì)了各個(gè)算法報(bào)告的模式中支持度超過一定數(shù)值的序列模式數(shù)量，實(shí)驗(yàn)結(jié)果見圖2，其中ISSPMFWER表示ISSPM 算法使用FWER約束，ISSPMFDR表表示ISSPM算法使用FDR 約束。

從圖2 可知，PSPM 算法在各個(gè)序列記錄集合中報(bào)告的模式數(shù)量最多，其原因是PSPM 算法直接使用了支持度作為興趣度約束，只要模式的支持度超過了最小興趣度閾值，該模式就被認(rèn)定為有趣的序列模式；由于SPDL 和PSDSP 算法在支持度的基礎(chǔ)上分別使用了杠桿率和統(tǒng)計(jì)顯著性檢驗(yàn)約束，從而SPDL 和PSDSP 算法報(bào)告的模式數(shù)量比PSPM 算法少；ISSPMFWER和ISSPMFDR算法報(bào)告的模式數(shù)量最少，其原因包括兩個(gè)方面：一方面，ISSPMFWER和ISSPMFDR算法使用了影響度作為興趣度度量方法，影響度不僅考慮了項(xiàng)的支持度對模式本身支持度的影響，還考慮了模式包含的項(xiàng)之間的順序特征，因此影響度相較于支持度約束性更強(qiáng)；另一方面，ISSPMFWER和ISSPMFDR算法還對挖掘結(jié)果進(jìn)行了置換檢驗(yàn)，通過FWER 和FDR 約束了假陽性序列模式的數(shù)量，從而又過濾了大量的假陽性序列模式。

圖2 各個(gè)算法在真實(shí)序列記錄集合上報(bào)告的序列模式數(shù)量Fig.2 Number of sequential patterns reported by each algorithm on real-world sequential record datasets

圖2 中，PSDSP、ISSPMFWER和ISSPMFDR算法報(bào)告的模式數(shù)量少于PSPM 和SPDL 算法，這是因?yàn)镻SPM 和SPDL 算法是基于興趣度約束的算法，而PSDSP、ISSPMFWER和ISSPMFDR算法在興趣度約束上還引入了統(tǒng)計(jì)顯著性檢驗(yàn)評估模式的質(zhì)量。多重假設(shè)檢驗(yàn)是對所有報(bào)告的模式進(jìn)行約束，而不是單一地判斷某個(gè)模式是否滿足了約束，從而統(tǒng)計(jì)顯著性檢驗(yàn)的約束能力通常更強(qiáng)且結(jié)果更可靠。此外，ISSPMFWER算法報(bào)告的模式數(shù)量少于ISSPMFDR算法，其原因是在相同的統(tǒng)計(jì)顯著水平下錯誤率判斷族的約束能力強(qiáng)于偽發(fā)現(xiàn)率。

上述實(shí)驗(yàn)只是從各個(gè)算法報(bào)告的模式數(shù)量方面進(jìn)行了討論，由于真實(shí)序列記錄集合中缺少真正有趣的序列模式信息，便無法直接判斷哪個(gè)算法報(bào)告的結(jié)果中真正有趣的序列模式占比最多。為了間接對比各個(gè)算法的挖掘能力，提取了各個(gè)算法在Book 序列記錄集合中報(bào)告的興趣度值最大的7個(gè)2 長度序列模式，詳細(xì)的結(jié)果見表3。

根據(jù)表3 中的信息可以看出PSPM 和PSDSP 算法結(jié)果相同，這是因?yàn)樗鼈兌际褂昧酥С侄茸鳛榕d趣度度量方法。觀察這兩個(gè)算法報(bào)告的結(jié)果發(fā)現(xiàn)7 個(gè)2 長度序列模式均由支持度最大的項(xiàng)algorithm、learn、data 和model 重復(fù)或組合而成，因此這些序列模式的支持度主要源自其包含的項(xiàng)，支持度并沒有體現(xiàn)它們真實(shí)的興趣度，從而導(dǎo)致這些序列模式提供了無意義的信息。

表3 各個(gè)算法在Book序列記錄集合上報(bào)告的興趣度最大的7個(gè)2長度的序列模式Tab.3 Top 7 2-length sequential patterns with the largest interestingness reported by each algorithm on Book dataset

SPDL 算法在表3 中的7 個(gè)模式雖然均不為algorithm、learn、data 和model 這4 個(gè)單詞組 合，但其報(bào)告 的和序列模式具有相差不大的支持度，因此和algorithm，problem 序列模式均不應(yīng)該被認(rèn)定為有趣的序列模式。造成這個(gè)結(jié)果的原因是杠桿率沒有體現(xiàn)項(xiàng)的順序特征。

ISSPMFWER和ISSPMFDR算法計(jì)算興趣度的方法相同，故表3 中使用ISSPM 算法表示其共同的結(jié)果。從這7 個(gè)序列模式可知兩點(diǎn)：一是它們均不由algorithm、learn、data 和model 這4個(gè)單詞共同組成；二是不存在諸如和這樣項(xiàng)順序置換的模式。這證明了ISSPM 算法使用的影響度不僅減弱了項(xiàng)的支持度對模式本身支持度的影響，還捕獲了模式中項(xiàng)的順序特征，更為真實(shí)地反映了序列模式的興趣度。

綜上，ISSPM 算法在真實(shí)序列記錄集合中報(bào)告的序列模式數(shù)量更少且興趣度更強(qiáng)，這些統(tǒng)計(jì)顯著序列模式能更好地反映序列記錄集合中有價(jià)值的信息。

4.2 仿真序列記錄集合實(shí)驗(yàn)

4.2.1 仿真序列記錄集合生成

由于真實(shí)序列記錄集合中缺少真正有趣的序列模式的相關(guān)信息，接下來的實(shí)驗(yàn)采用人工嵌入有趣的序列模式的方式生成了仿真序列記錄集合。詳細(xì)的仿真序列記錄集合生成步驟如下：

1）設(shè)字母表C=｛c1，c2，…，c60｝包含60 個(gè)項(xiàng)，序列記錄的最短長度lmin=8，最長長度lmax=16。

2）隨機(jī)生成一個(gè)屬于［lmin，lmax］的整數(shù)l*，并從字母表中隨機(jī)有放回抽取l*個(gè)項(xiàng)。根據(jù)抽取順序?qū)⑦@l*個(gè)項(xiàng)表示成一條序列記錄。重復(fù)上述過程直到生成10 000 條序列記錄。

3）從C*=｛c37，c38，…，c60｝中隨機(jī)挑選10 個(gè)不同的項(xiàng)構(gòu)成5 個(gè)2 長度的序列模式，這些序列模式的支持度在［0.1，0.2］。接著，將這些序列模式按照相應(yīng)的支持度隨機(jī)嵌入到10 000 條序列記錄中。為了不引入額外的干擾模式，一條序列記錄至多只能嵌入一個(gè)2 長度序列模式。

4）用C*余下的項(xiàng)構(gòu)成3 個(gè)3 長度和1 個(gè)4 長度序列模式，這些序列模式的支持度均在［0.1，0.2］。然后以第3）步中相同的方式將其嵌入序列記錄中。

經(jīng)過上述步驟生成的仿真序列記錄集合中包含了人工嵌入的5 個(gè)2 長度模式、3 個(gè)3 長度模式和1 個(gè)4 長度模式，這9 個(gè)序列模式被認(rèn)為是真正有趣的序列模式。在各個(gè)算法報(bào)告的序列模式中，如果某個(gè)序列模式的所有項(xiàng)均在C-C*集合中，那么該序列模式被認(rèn)定為假陽性序列模式，因?yàn)槠錄]有包含任何有用的信息；反之，如果某個(gè)序列模式含有C*集合中的項(xiàng)，該序列模式被認(rèn)定為非假陽性序列模式。此外，為了避免偶然性，實(shí)驗(yàn)中生成了10 個(gè)仿真序列記錄集合。

4.2.2 仿真序列記錄集合實(shí)驗(yàn)結(jié)果

各個(gè)對比算法分別在相同的θins和θsig參數(shù)下對10 個(gè)仿真序列記錄集合實(shí)施了序列模式挖掘。為了能夠比較各個(gè)算法的挖掘能力，實(shí)驗(yàn)統(tǒng)計(jì)了每個(gè)算法報(bào)告的模式中支持度超過一定數(shù)值的序列模式情況，具體的信息見表4，其中對10 個(gè)仿真序列記錄集合的結(jié)果取了平均值。

表4 各個(gè)算法在仿真序列記錄集合上報(bào)告的非假陽性序列模式和假陽性序列模式的數(shù)量Tab.4 Number of non-false positive patterns and false positive patterns reported by each algorithm on synthetic sequential pattern datasets

根據(jù)表4 的統(tǒng)計(jì)信息可以看出，PSPM 和SPDL 算法報(bào)告的序列模式中假陽性序列模式的數(shù)量占比達(dá)到了78%以上。導(dǎo)致這個(gè)情況的原因是PSPM 和SPDL 算法是純粹基于興趣度約束的算法，只要序列模式滿足了約束，就會被認(rèn)定為有趣的序列模式，沒有考慮這些序列模式可能是因?yàn)閿?shù)據(jù)的隨機(jī)性導(dǎo)致的；而PSDSP、ISSPMFWER和ISSPMFDR算法均使用了置換檢驗(yàn)對報(bào)告的模式進(jìn)行評估，過濾了大量的假陽性序列模式。

PSDSP 和ISSPMFDR算法均用了偽發(fā)現(xiàn)率作為假陽性序列模式數(shù)量的約束，但PSDSP 算法的結(jié)果中假陽性序列模式數(shù)量占比為4.51%，而ISSPMFDR算法的結(jié)果中假陽性序列模式數(shù)量占比為3.39%。其原因有兩點(diǎn)：一是PSDSP 算法使用的置換方法不滿足一致性要求，引入了額外的誤差；二是ISSPMFDR算法使用的影響度減弱了項(xiàng)的支持度對模式本身支持度的影響，從而過濾了少量的假陽性序列模式。此外，ISSPMFWER算法的結(jié)果中假陽性序列模式數(shù)量占比為0.93%，這再次驗(yàn)證了錯誤率發(fā)現(xiàn)族約束能力強(qiáng)于偽發(fā)現(xiàn)率，但I(xiàn)SSPMFWER算法報(bào)告的非假陽性序列模式數(shù)量也少于ISSPMFDR算法。當(dāng)錯誤決策會造成相當(dāng)嚴(yán)重的后果時(shí)，應(yīng)當(dāng)考慮使用ISSPMFWER算法，否則可以選擇ISSPMFDR算法保留更多有價(jià)值的信息。

除了統(tǒng)計(jì)每個(gè)算法報(bào)告的序列模式數(shù)量外，實(shí)驗(yàn)還分析了每個(gè)算法在10 個(gè)仿真序列記錄集中報(bào)告的興趣度最大的20 個(gè)模式中嵌入序列模式的發(fā)現(xiàn)率，具體的結(jié)果見表5。根據(jù)表5 能夠發(fā)現(xiàn)，PSPM 和PSDSP 算法發(fā)現(xiàn)嵌入序列模式的數(shù)量最少。造成這個(gè)結(jié)果的原因是支持度排名前列的單個(gè)項(xiàng)重復(fù)或者組合形成的2 長度序列模式擁有非常大的支持度，從而導(dǎo)致嵌入序列模式的支持度未能排進(jìn)前20。甚至如果θins設(shè)置得較大，嵌入序列模式很可能不會出現(xiàn)在這兩個(gè)算法報(bào)告的結(jié)果中，這再次說明支持度沒有如實(shí)地表達(dá)這些模式的興趣度。

表5 各個(gè)算法在仿真序列記錄集合上嵌入模式的發(fā)現(xiàn)率 單位：%Tab.5 Embedded patterns discovery rate reported by each algorithm on synthetic sequential pattern datasets unit：%

SPDL 算法報(bào)告的嵌入模式數(shù)量不及ISSPM 算法，這是因?yàn)镾PDL 算法雖然考慮了模式包含項(xiàng)的影響，但忽略了項(xiàng)之間的順序特征，從而導(dǎo)致一些項(xiàng)相同但順序不同的2 長度序列模式出現(xiàn)在結(jié)果中；ISSPM 算法使用的影響度，既考慮了模式包含項(xiàng)的支持度的影響，又考慮了這些項(xiàng)的順序特征，因此更為真實(shí)地反映了序列模式的興趣度，結(jié)果中嵌入模式的發(fā)現(xiàn)率最高。ISSPM 算法在某幾個(gè)仿真序列記錄集合中未能發(fā)現(xiàn)所有的嵌入序列模式，造成這個(gè)結(jié)果的主要原因是ISSPM 算法允許一個(gè)序列模式的子模式也成為有趣的序列模式。在這幾個(gè)仿真序列記錄集合中，嵌入的3 長度和4 長度序列模式的子模式也表現(xiàn)出了很高的興趣度，從而導(dǎo)致某些嵌入的2 長度序列模式的興趣度沒有排進(jìn)前20，但值得注意的是這些子模式也包含了真實(shí)有用的信息。

接下來的實(shí)驗(yàn)對比了各個(gè)算法在10 個(gè)仿真序列記錄集合中的平均運(yùn)行時(shí)間，詳細(xì)的實(shí)驗(yàn)結(jié)果見表6。

表6 各個(gè)算法在仿真序列記錄集合上的平均運(yùn)行時(shí)間 單位：sTab.6 Average running time of each algorithm on synthetic sequential pattern datasets unit：s

從表6 中可知，PSPM 和SPDL 算法在挖掘階段的時(shí)間多于PSDSP 和ISSPM 算法，這是因?yàn)镻SPM 和SPDL 算法使用的逐層通用序列模式挖掘算法計(jì)算開銷高于PSDSP 和ISSPM算法使用的樹形垂直序列模式挖掘算法。由于ISSPM 算法在挖掘過程中需要計(jì)算兩個(gè)模式可能構(gòu)成的序列模式的修正支持度，故計(jì)算開銷大于PSDSP 算法，但也在可接受的時(shí)間范圍之內(nèi)。在評估階段，PSDSP 和ISSPM 算法分別使用了不同的置換檢驗(yàn)方法評估挖掘到的序列模式質(zhì)量，但PSDSP算法的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)高于ISSPM 算法，根本原因是PSDSP 算法生成隨機(jī)序列記錄集合后需要對該集合進(jìn)行挖掘以提取相應(yīng)的支持度來構(gòu)建零分布，而ISSPM 算法使用的一次挖掘技術(shù)在生成隨機(jī)序列記錄集合后僅需要更新相應(yīng)序列模式的影響度即可。由于挖掘過程的計(jì)算開銷非常大，導(dǎo)致大幅增加了PSDSP 算法的運(yùn)行時(shí)間。

綜上，ISSPM 算法在仿真序列記錄集合中報(bào)告的統(tǒng)計(jì)顯著序列模式不僅興趣度更強(qiáng)，并且假陽性序列模式的占比更少，運(yùn)行時(shí)間相較于使用了不同置換檢驗(yàn)方法的PSDSP 算法更少。

5 結(jié)語

為了能夠更真實(shí)地度量序列模式的興趣度并提升挖掘結(jié)果的質(zhì)量，提出了一個(gè)使用影響度的挖掘算法——ISSPM算法。該算法在挖掘過程中不僅考慮了模式包含的項(xiàng)的支持度對模式本身支持度的影響，還考慮了這些項(xiàng)之間的順序特征；此外，ISSPM 算法還設(shè)計(jì)了一個(gè)基于項(xiàng)集置換的置換檢驗(yàn)方法過濾假陽性序列模式。實(shí)驗(yàn)使用了真實(shí)序列記錄集合和仿真序列記錄集合，實(shí)驗(yàn)結(jié)果表明，ISSPM 算法相較于PSPM、SPDL 和PSDSP 算法不僅能夠找到興趣度更強(qiáng)的序列模式，還能夠過濾大量的假陽性序列模式，因此，ISSPM 算法報(bào)告的統(tǒng)計(jì)顯著序列模式提供的信息更有價(jià)值且更加可靠。實(shí)驗(yàn)過程中發(fā)現(xiàn)ISSPM 算法的計(jì)算開銷較大，仔細(xì)分析這些計(jì)算開銷主要源自兩個(gè)方面：隨機(jī)序列記錄集合的生成和序列模式影響度的更新。未來工作將從模式發(fā)現(xiàn)算法并行化的角度出發(fā)降低ISSPM 算法的運(yùn)行時(shí)間；ISSPM 算法允許超模式和子模式同時(shí)成為有趣的序列模式，導(dǎo)致某些超模式與子模式有可能提供了重復(fù)的信息，因此同時(shí)保存它們會造成不必要的資源浪費(fèi)，后續(xù)工作也會研究如何判定統(tǒng)計(jì)顯著序列模式的冗余性，并提出相關(guān)的冗余模式過濾算法；此外，還會嘗試將三支決策應(yīng)用到統(tǒng)計(jì)顯著序列模式挖掘中，以發(fā)現(xiàn)更多的高質(zhì)量模式。