吳 軍，歐陽艾嘉，張琳

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

0 引言

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

2 基本定義

2.1 序列模式

假設(shè)D=｛d1，d2，…，d|D|｝是一個有限的序列記錄的集合，其中每一條記錄di是由C中的項構(gòu)成。如果一個序列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|。

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

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

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

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

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

3 ISSPM算法

3.1 影響度

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

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

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

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

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

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

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

3.2 項集置換

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

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

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

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

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

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

第一步 假定從1～5 中隨機選擇的α為3，表示每條序列記錄需要置換3 個項。

第二步 依據(jù)序列記錄的編號，生成了一個隨機的置換順序為：d5，d3，d8，d7，d1，d2，d6，d4；再為每一條序列記錄隨機挑選3 個項，并記錄這些項的位置。得到的結(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ù)置換順序和項的位置置換相應(yīng)的項，具體而言，將d1的第3、5、7 位置對應(yīng)的項置換到d5的第1、6、2 位置；將d2的第4、1、2 位置對應(yīng)的項置換到d3的第7、3、4 位置；不斷執(zhí)行上述置換操作，直到將d8的第5、8、4 位置對應(yīng)的項置換到d4的第6、1、3 位置就得到了一個隨機序列記錄集合D'，如圖1（b）所示。

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

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

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

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

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

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

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

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

3.4 算法過程

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

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

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

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

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

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

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

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

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

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

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

輸出 無。

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

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

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

輸出 計算出p值的序列模式集合S。

算法4 詳細的步驟描述如下：

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

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

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

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

4 實驗與結(jié)果分析

為了驗證ISSPM 算法的性能，實驗使用了4 個真實序列記錄集合和10 個仿真序列記錄集合作為實驗數(shù)據(jù)，并對比了3 個高效的序列模式挖掘算法：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 算法不僅使用了支持度度量興趣度還采用了置換檢驗評估序列模式的質(zhì)量。實驗中，置換檢驗的次數(shù)設(shè)置為1 000，所有算法均以Java 語言實現(xiàn)，實驗設(shè)備為一臺2.40 GHz CPU 和16 GB 內(nèi)存的計算機設(shè)備。

4.1 真實序列記錄集合實驗

4.1.1 真實序列記錄集合簡介

4 個不同類型的真實序列記錄集合分別為：Book、Unix、Peptide 和Bike：Book 是圖書摘要文本的序列記錄集合［21］；Unix 是用戶操作命令的序列記錄集合［26］；Peptide 是人類肽段的序列記錄集合［27］；Bike 是共享單車停靠站的序列記錄集合［23］。詳細信息如表2 所示。

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

4.1.2 真實序列記錄集合實驗結(jié)果

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

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

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

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

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

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

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

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

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

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

4.2 仿真序列記錄集合實驗

4.2.1 仿真序列記錄集合生成

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

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

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

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

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

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

4.2.2 仿真序列記錄集合實驗結(jié)果

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

表4 各個算法在仿真序列記錄集合上報告的非假陽性序列模式和假陽性序列模式的數(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)計信息可以看出，PSPM 和SPDL 算法報告的序列模式中假陽性序列模式的數(shù)量占比達到了78%以上。導(dǎo)致這個情況的原因是PSPM 和SPDL 算法是純粹基于興趣度約束的算法，只要序列模式滿足了約束，就會被認定為有趣的序列模式，沒有考慮這些序列模式可能是因為數(shù)據(jù)的隨機性導(dǎo)致的；而PSDSP、ISSPMFWER和ISSPMFDR算法均使用了置換檢驗對報告的模式進行評估，過濾了大量的假陽性序列模式。

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

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

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

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

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

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

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

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

5 結(jié)語

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