袁紅娟

泰州學(xué)院 數(shù)理信息學(xué)院，江蘇 泰州 225300

GFExtractor：事件序列上有效挖掘無冗余情節(jié)規(guī)則的算法

袁紅娟

泰州學(xué)院 數(shù)理信息學(xué)院，江蘇 泰州 225300

1 引言

情節(jié)規(guī)則的概念首先由Mannila等人[1]提出，用于描述情節(jié)之間的因果關(guān)系。事件序列上挖掘情節(jié)規(guī)則，目前主要有Mannila提出的MINEPI算法，Hatonen等人提出的TASA算法[2]、Meger等人提出的WinMiner[3]算法等，主要應(yīng)用于網(wǎng)絡(luò)安全監(jiān)控[4]、事務(wù)日志分析[5]、傳感器數(shù)據(jù)分析處理[6]、交通流預(yù)測等方面。

現(xiàn)有的挖掘情節(jié)規(guī)則的算法，大多數(shù)基于滑動窗口或最小發(fā)生來計(jì)算情節(jié)的支持度，對支持度的“過計(jì)數(shù)”導(dǎo)致挖掘質(zhì)量不高，且從頻繁情節(jié)集產(chǎn)生的情節(jié)規(guī)則存在冗余，導(dǎo)致挖掘效率不高。而直接從頻繁閉情節(jié)集產(chǎn)生情節(jié)規(guī)則，同樣存在冗余。假設(shè)有事件序列ES如圖1所示。

圖1 事件序列ES

當(dāng)支持度閾值min_sup=2，置信度閾值min_conf=0.4時(shí)，該序列有34個(gè)頻繁情節(jié)，7個(gè)頻繁閉情節(jié)，直接從頻繁閉情節(jié)挖掘得到46個(gè)情節(jié)規(guī)則，存在冗余。

為有效地在事件序列上挖掘無冗余的情節(jié)規(guī)則，定義了情節(jié)生成子概念，結(jié)合頻繁閉情節(jié)，提出挖掘無冗余情節(jié)規(guī)則的算法GFExtractor（Generator&Frequent Closed Episode Extractor）。該算法基于非重疊的最小發(fā)生的支持度定義[7]和深度優(yōu)先搜索策略，產(chǎn)生情節(jié)生成子集與頻繁閉情節(jié)集，在兩者之間抽取無冗余的情節(jié)規(guī)則。在挖掘過程中，利用非生成子剪枝策略淘汰非生成子情節(jié)，利用向前、向后雙向擴(kuò)展檢查淘汰非閉情節(jié)，避免維護(hù)頻繁情節(jié)集，節(jié)省存儲空間，提高運(yùn)行效率。

雙向擴(kuò)展檢查挖掘頻繁閉情節(jié)的BIDEFCE算法，可參考作者的另一篇文章《BIDEFCE：一種基于雙向擴(kuò)展的頻繁閉情節(jié)挖掘算法》。

2 相關(guān)工作

在研究情節(jié)規(guī)則挖掘之前，關(guān)聯(lián)規(guī)則挖掘和序列模式挖掘的研究由來已久。

（1）關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則挖掘的對象是一個(gè)事務(wù)數(shù)據(jù)庫，將包含在相同交易集的項(xiàng)集的集合稱為等價(jià)類[8]。為控制由頻繁項(xiàng)集產(chǎn)生的關(guān)聯(lián)規(guī)則的數(shù)量，Pasquier等人引入了項(xiàng)集生成子[9]的概念：在同一等價(jià)類中，最小的元素稱為項(xiàng)集生成子，最大的元素稱為閉項(xiàng)集。根據(jù)MDL（最小描述長度）原理[10]，項(xiàng)集生成子比閉項(xiàng)集具有更小的描述長度。從項(xiàng)集生成子和頻繁閉項(xiàng)集產(chǎn)生無冗余的關(guān)聯(lián)規(guī)則，主要的算法有Gen，DPMiner等。Gen[11]算法采用廣度優(yōu)先搜索策略，定義了精確關(guān)聯(lián)規(guī)則基和近似關(guān)聯(lián)規(guī)則基的概念，精確關(guān)聯(lián)規(guī)則基由具有最小前件與最大后件的精確關(guān)聯(lián)規(guī)則（置信度等于100%）組成，近似關(guān)聯(lián)規(guī)則基由具有最小前件與最大后件的近似關(guān)聯(lián)規(guī)則（置信度小于100%）組成。DPMiner[12]算法則采用了深度優(yōu)先搜索策略，利用FP樹挖掘頻繁閉項(xiàng)集及其生成子，生成等價(jià)類。

（2）序列模式挖掘

序列模式挖掘的對象是一個(gè)序列數(shù)據(jù)庫，由相同序列集支持的序列模式的集合稱為等價(jià)類。同一等價(jià)類中，不存在等支持度真子序列的序列模式稱為序列生成子[13]，不存在等支持度超序列的序列模式稱為閉序列。同樣，根據(jù)MDL原理，序列生成子比閉序列具有更小的描述長度。主要算法有GenMiner。GenMiner[13]算法采用深度優(yōu)先搜索策略，創(chuàng)建并存儲所有序列模式的前綴搜索樹PSL，遍歷PSL，得到序列模式生成子超集并進(jìn)行過濾，得到最后的序列模式生成子集合。

（3）情節(jié)規(guī)則挖掘

情節(jié)規(guī)則挖掘與前兩者不同，挖掘的對象是一個(gè)事件序列。

Mannila等人提出的MINEPI算法中，情節(jié)規(guī)則形如且 β是α的子情節(jié)，情節(jié)規(guī)則表示α、 β發(fā)生的起始時(shí)間相同，若 β在win1寬度的時(shí)間區(qū)間內(nèi)發(fā)生，緊接著α將會在win2寬度的時(shí)間區(qū)間內(nèi)發(fā)生，算法基于頻繁情節(jié)集抽取情節(jié)規(guī)則。

由Hatonen等人提出的TASA算法，基于滑動窗口的支持度定義及廣度優(yōu)先搜索策略，多次掃描事件序列挖掘頻繁情節(jié)，再基于頻繁情節(jié)集抽取情節(jié)規(guī)則，最后再通過剪枝、排序、分組等技術(shù)來篩選冗余的情節(jié)規(guī)則。

由Meger等人提出的WinMiner算法，基于最小發(fā)生的支持度定義和深度優(yōu)先搜索策略，單遍掃描事件序列，挖掘頻繁情節(jié)的過程中無需生成候選情節(jié)，再基于頻繁情節(jié)集抽取情節(jié)規(guī)則。

上述算法均是從頻繁情節(jié)集中抽取所有的情節(jié)規(guī)則，存在大量冗余。由朱輝生[14]等人提出的Extractor算法，基于最小且非重疊的支持度定義和深度優(yōu)先搜索策略來發(fā)現(xiàn)頻繁閉情節(jié)及其生成子，生成無冗余的情節(jié)規(guī)則。但在生成規(guī)則時(shí)需雙重遍歷并維護(hù)頻繁情節(jié)集。

針對以上不足，本文提出了GFExtractor算法。算法基于非重疊的最小發(fā)生的支持度定義和深度優(yōu)先搜索策略，在挖掘頻繁情節(jié)的同時(shí)，及時(shí)淘汰非生成子情節(jié)及非閉情節(jié)，產(chǎn)生情節(jié)生成子集Gen和頻繁閉情節(jié)集FCE，再在Gen和FCE之間抽取無冗余的情節(jié)規(guī)則。算法避免了遍歷和維護(hù)頻繁情節(jié)集，節(jié)省存儲空間，提高了情節(jié)規(guī)則挖掘的效率和質(zhì)量。

3 相關(guān)概念

定義1（事件序列event sequence）設(shè)E是一組事件類型，事件＜e，t＞，e∈E，t是事件發(fā)生的時(shí)間，則事件序列ES=(s，Ts，Te)，其中s=＜(t1)，(e2，t2)，…，(en，tn)＞，ei∈E，ti＜ti+1(1≤i＜n)，Ts表示事件序列的起始時(shí)間，Te表示事件序列的結(jié)束時(shí)間。

定義2（情節(jié)episode/子情節(jié)subepisode）情節(jié)是事件發(fā)生的偏序集合，情節(jié)α=＜e2，…，ek＞，ei∈E(1≤i≤k)，其中ei出現(xiàn)在ej之前(1≤i＜j≤k)，情節(jié)長度=k。設(shè)情節(jié)α=＜e1，e2，…，ek＞，情節(jié) β=＜e1'，e2'，…，ej'＞(j≤k)，其中存在整型序列1≤l1＜l2＜…≤lj，且ei'=eli(1≤i≤j)，則稱 β是α的子情節(jié)，α是 β的超情節(jié)。

定義3（前綴prefix/投影project/增長growth）給定情節(jié)α=＜e1，e2，…，ek＞，情節(jié) β=＜e1'，e2'，…，ej'＞(j≤k)，其中情節(jié)β是α的子情節(jié)，設(shè)m是β在α中首次出現(xiàn)的結(jié)束位置，其中對于所有的i(1≤i≤m≤k)，滿足ei=ei''，則情節(jié)γ=＜e1''，e2''，…，em''＞稱為β在α上的前綴，表示為 prefix(α，β)。如情節(jié)α=ABACBC，子情節(jié)β=BC，則 prefix(α，β)=ABAC。β在α上的投影則是從情節(jié)α中刪除 β在α上的前綴之后剩余的部分，表示為project(α，β)。如情節(jié)α=ABACBC，子情節(jié) β=AB，project(α，β)=ACBC。設(shè)情節(jié)α=＜e2，…，ek＞，1-情節(jié)e=＜e'＞，對 α和e連接形成超情節(jié) β=＜e1，e2，…，ek，e'＞，稱作對α進(jìn)行增長，表示為 β=growth(α，e)，主要用于深度優(yōu)先搜索時(shí)，增長形成新情節(jié)。

定義4（向前擴(kuò)展檢查forcheck/向后擴(kuò)展檢查backcheck）

定義4參考BIDEFCE算法的定義，借鑒BIDE[15]算法思想，用于在深度優(yōu)先搜索生成新情節(jié)的時(shí)候，對當(dāng)前情節(jié)進(jìn)行向前、向后擴(kuò)展檢查，判斷當(dāng)前情節(jié)是否存在向前或向后擴(kuò)展項(xiàng)。若存在，則當(dāng)前情節(jié)非閉，直接淘汰；若均為空，則情節(jié)待定，加入頻繁閉情節(jié)超集FCE中，供進(jìn)一步辨別是否為閉情節(jié)。對當(dāng)前情節(jié)α進(jìn)行向前、向后擴(kuò)展檢查分別表示為 forcheck(α)、backcheck(α)。

定義5（非重疊的最小發(fā)生non-overlapping minmal occurrence/支持度support）設(shè)情節(jié)α在事件序列上的最小發(fā)生集合表示為α.mo，若情節(jié)α的兩次最小發(fā)生則稱這兩次發(fā)生是非重疊的最小發(fā)生[16]。從事件序列上第一個(gè)最小發(fā)生開始計(jì)算，情節(jié)α在事件序列上非重疊的最小發(fā)生的最大集合表示為α.nomo，最大集合中元素的數(shù)量是情節(jié)的支持度，即

如圖1中的事件序列ES，情節(jié)β=ABA的最小且非重疊的發(fā)生情節(jié) β在事件序列上的支持度本文的支持度均采用絕對支持度。

定義6（頻繁情節(jié)/頻繁閉情節(jié)/情節(jié)生成子episode generator）設(shè)支持度閾值min_sup，若情節(jié)α在事件序列上非重疊的最小發(fā)生的支持度α.sup≥min_sup，則稱情節(jié)α是頻繁情節(jié)。設(shè)情節(jié)α是頻繁情節(jié)，且在事件序列上不存在等支持度的超情節(jié)，則稱情節(jié)α是頻繁閉情節(jié)。設(shè) β是頻繁情節(jié)，f是頻繁閉情節(jié)，其中 β?f，且在事件序列上β不存在等支持度的真子情節(jié)，則稱情節(jié) β是 f的一個(gè)情節(jié)生成子。

定義7（情節(jié)規(guī)則/情節(jié)規(guī)則的支持度/情節(jié)規(guī)則的置信度）設(shè)情節(jié)α和 β，其中 β?α，以 β為前件，β在α上的投影 project(α，β)為后件，則在α和 β之間產(chǎn)生情節(jié)規(guī)則，記作 β?project(α，β)。

由情節(jié) α和 β生成的情節(jié)規(guī)則，其支持度定義為support(β?project(α，β))=support(α)，即規(guī)則的支持度等于情節(jié)α在事件序列上的支持度。

由情節(jié)α和β生成的情節(jié)規(guī)則，其置信度定義為：

若情節(jié)規(guī)則置信度等于1，稱為精確情節(jié)規(guī)則；置信度小于1，稱為近似情節(jié)規(guī)則。

設(shè)情節(jié)規(guī)則的最小支持度閾值min_sup和最小置信度閾值min_conf，若support(β?project(α，β))≥min_sup，則稱該情節(jié)規(guī)則是頻繁的；若confidence(β?project(α，β))≥min_conf，則稱該情節(jié)規(guī)則是可信的。

定義8（無冗余情節(jié)規(guī)則）一個(gè)情節(jié)規(guī)則γ:g→r是無冗余情節(jié)規(guī)則，當(dāng)且僅當(dāng)不存在情節(jié)規(guī)則γ':g'→r'，有supprot(γ)=support(γ')及 confidence(γ)=confidence(γ')，且g'?g和r?r'。

本文情節(jié)規(guī)則由一個(gè)四元組構(gòu)成γ=(g，r，sup，conf)，分別表示情節(jié)規(guī)則的前件、后件、支持度和置信度。

4 挖掘無冗余情節(jié)規(guī)則的GFExtractor算法

GFExtractor算法分為如下3步：

（1）搜索階段：深度優(yōu)先搜索，淘汰非生成子情節(jié)及非閉情節(jié)，得到情節(jié)生成子超集和頻繁閉情節(jié)超集。

（2）過濾階段：刪除非生成子情節(jié)及非閉情節(jié)，得到最后的情節(jié)生成子集Gen及頻繁閉情節(jié)集FCE。

（3）生成規(guī)則階段：根據(jù)情節(jié)生成子集Gen及頻繁閉情節(jié)集FCE，分別產(chǎn)生精確情節(jié)規(guī)則和近似情節(jié)規(guī)則，其中對近似情節(jié)規(guī)則進(jìn)行消除冗余后件的處理，最后得到無冗余情節(jié)規(guī)則集R。

4.1 主要算法

因?yàn)轭l繁1-情節(jié)長度為1，不存在等支持度的真子情節(jié)，則頻繁1-情節(jié)都是情節(jié)生成子，直接加入情節(jié)生成子超集Gen中。

GFExtractor（ES，min_sup，min_conf）

輸入：事件序列ES，最小支持度閾值min_sup，最小置信度閾值min_conf

輸出：無冗余情節(jié)規(guī)則集合R

GFExtractor（）算法1～2行，首先初始化情節(jié)生成子超集Gen和頻繁閉情節(jié)超集FCE為空。第3行單遍掃描事件序列并生成頻繁1-情節(jié)集合F1。4～7行遍歷頻繁1-情節(jié)集合F1，將各1-情節(jié)加入情節(jié)生成子集合Gen中；若當(dāng)前1-情節(jié)向前、向后擴(kuò)展檢查均為空，情節(jié)待定，加入頻繁閉情節(jié)超集FCE中（參考BIDEFCE算法）。第8行，調(diào)用MINE（）子算法，深度優(yōu)先搜索，挖掘所有的頻繁情節(jié)。9～11行，對頻繁閉情節(jié)超集FCE進(jìn)行過濾，刪除閉合性檢查為假的情節(jié)（參考BIDEFCE算法）。12～14行，對情節(jié)生成子超集Gen進(jìn)行過濾，刪除生成子檢查為假的情節(jié)。15～16行，在情節(jié)生成子集合Gen和頻繁閉情節(jié)FCE之間產(chǎn)生情節(jié)規(guī)則，并輸出。

MINE（）算法17～20行，遍歷頻繁1-情節(jié)集合F1，增長當(dāng)前情節(jié)α和1-情節(jié)e得到新情節(jié)β；根據(jù)α和e的最小發(fā)生計(jì)算β的最小發(fā)生，進(jìn)而計(jì)算出β非重疊的最小發(fā)生；21～25行，如果情節(jié)β是頻繁情節(jié)，且β的支持度與其真子情節(jié)α和e的支持度均不等，β是待定生成子情節(jié)，加入情節(jié)生成子超集Gen中；若情節(jié)β的向前、向后擴(kuò)展檢查均為空，β是待定閉情節(jié)，加入頻繁閉情節(jié)超集FCE中（參考BIDEFCE算法）；第26行，遞歸調(diào)用MINE（）算法。

MINE（）算法遞歸調(diào)用，深度優(yōu)先遍歷并生成新情節(jié)，通過非生成子情節(jié)剪枝和非閉情節(jié)淘汰策略，盡快產(chǎn)生情節(jié)生成子超集Gen和頻繁閉情節(jié)超集FCE，避免維護(hù)頻繁情節(jié)集合，壓縮搜索空間。GFExtractor（）算法通過生成子檢查和閉情節(jié)檢查對Gen和FCE進(jìn)行過濾，并在兩者之間產(chǎn)生情節(jié)規(guī)則。

4.2 非生成子情節(jié)的剪枝

MINE（）算法中，新情節(jié)β=growth(α，e)，由真子情節(jié)α和頻繁1-情節(jié)e增長得到。若情節(jié)β的支持度等于真子情節(jié)α或1-情節(jié)e的支持度，根據(jù)定義6可以得出情節(jié)β必定是非生成子情節(jié)，盡快淘汰。即

若情節(jié)β是頻繁的，且它的支持度不等于真子情節(jié)α及e的支持度，則情節(jié)β是否生成子情節(jié)待定，加入情節(jié)生成子超集Gen中。

說明在事件序列上，對于新情節(jié)β，若存在支持度相同的真子情節(jié)，則情節(jié)β為非生成子情節(jié)。因此MINE（）算法的第22～23行，對非生成子情節(jié)進(jìn)行剪枝淘汰，只保留生成子待定情節(jié)到Gen中，縮小搜索范圍。

4.3 生成子情節(jié)檢查

在情節(jié)生成子超集Gen中，若某情節(jié)不存在具有相同支持度的真子情節(jié)，則該情節(jié)為生成子情節(jié)。

GeneratorCheck（g）算法中，遍歷生成子超集Gen，判斷當(dāng)前情節(jié)g是否存在等支持度的真子情節(jié)f，若存在，則返回假，表示g是非生成子情節(jié)。遍歷完生成子超集Gen，若不存在等支持度的真子情節(jié)f，則返回真，表示g是生成子情節(jié)。

生成子情節(jié)檢查只需遍歷生成子超集Gen，避免掃描頻繁情節(jié)集合，降低搜索空間。

情節(jié)的閉合性檢查，參考BIDEFCE算法。

4.4 生成情節(jié)規(guī)則

情節(jié)規(guī)則在情節(jié)生成子集Gen及頻繁閉情節(jié)集FCE之間生成，要求置信度大于等于閾值min_conf。

CreateRule（Gen，F(xiàn)CE，min_conf，R）

輸入：情節(jié)生成子集合Gen，頻繁閉情節(jié)集合FCE，最小置信度閾值min_conf

CreateRule（）算法第1行，初始化情節(jié)規(guī)則集合R為空。第2行，外層遍歷情節(jié)生成子集合Gen。第3行內(nèi)層遍歷頻繁閉情節(jié)集合FCE。4～10行，若當(dāng)前生成子情節(jié)g是閉情節(jié)f的真子序列，則可在兩者之間生成情節(jié)規(guī)則；SUCC集合保存情節(jié)規(guī)則的后件，初始化為空；r=project(f，g)計(jì)算g在f上的投影，作為情節(jié)規(guī)則的后件；若生成子情節(jié)g與閉情節(jié)f等支持度，則置信度為1，生成精確情節(jié)規(guī)則，加入集合R中；否則將后件r加入到SUCC集合中。11～14行，針對當(dāng)前生成子g，遍歷其后件集合SUCC；若后件s不是冗余的后件，即在SUCC中不存在與s等支持度的超情節(jié)，且置信度大于等于min_conf，則生成近似情節(jié)規(guī)則，并加入到集合R中。第15行，返回情節(jié)規(guī)則集合R。

CreateRule（）算法針對近似情節(jié)規(guī)則作了消除冗余后件的處理，保證情節(jié)規(guī)則有著最小前件和最大后件。如圖1所示的事件序列ES上，有情節(jié)生成子B∶3與頻繁閉情節(jié)ABACE∶2及ACBE∶2，它們之間可以產(chǎn)生情節(jié)規(guī)則，如表1所示。

表1 情節(jié)規(guī)則示例

此時(shí)，兩個(gè)近似情節(jié)規(guī)則前件相同且等支持度、等置信度，存在冗余。CreateRule（）算法的第11～14行，對冗余后件E進(jìn)行了刪除，避免生成冗余情節(jié)規(guī)則B->E。

5 運(yùn)行實(shí)例

以圖1所示的事件序列ES為例，支持度閾值min_sup= 2，置信度閾值min_conf=0.4，運(yùn)行GFExtractor算法，共生成8個(gè)情節(jié)生成子，7個(gè)頻繁閉情節(jié)，在情節(jié)生成子與頻繁閉情節(jié)之間，經(jīng)過消除冗余后件處理，最后產(chǎn)生14個(gè)無冗余的情節(jié)規(guī)則。

由表4可知，相對于通過閉情節(jié)與頻繁情節(jié)集挖掘出的所有46個(gè)情節(jié)規(guī)則，GFExtractor算法基于情節(jié)生成子和頻繁閉情節(jié)挖掘出14個(gè)情節(jié)規(guī)則，數(shù)量大大減少，同時(shí)也沒有丟失信息。

表2 ES上的情節(jié)生成子集合Gen

表3 ES上的頻繁閉情節(jié)集合FCE

表4 ES上的情節(jié)規(guī)則集合R

6 算法性能分析

假設(shè)事件序列ES，長度為L，頻繁1-情節(jié)集合F1，頻繁情節(jié)集合FE，情節(jié)生成子超集Gen，頻繁閉情節(jié)超集FCE，頻繁情節(jié)的最大長度max_len，則算法GFExtractor的復(fù)雜度分析如下：

6.1 時(shí)空復(fù)雜度分析

GFExtractor算法的主要時(shí)間代價(jià)是搜索階段的非閉情節(jié)判斷、過濾階段的生成子檢查和閉合性檢查，以及情節(jié)規(guī)則的生成。

參考BIDEFCE算法，搜索階段的非閉情節(jié)判斷的時(shí)間復(fù)雜度為O(|FE|?L?max_len)。過濾階段，生成子檢查時(shí)間復(fù)雜度為O(|Gen|2?max_len)，閉合性檢查時(shí)間復(fù)雜度為O(|FCE|2?max_len)。情節(jié)規(guī)則生成，時(shí)間復(fù)雜度為O(|Gen|?|FCE|)。由于通過非生成子情節(jié)剪枝和非閉情節(jié)判斷后，情節(jié)生成子超集Gen和頻繁閉情節(jié)超集FCE中的元素?cái)?shù)量大大減少，因此GFExtractor算法的時(shí)間復(fù)雜度為O(|FE|?L?max_len)。

GFExtractor算法在挖掘無冗余情節(jié)規(guī)則過程中，無需維護(hù)頻繁情節(jié)集，只需維護(hù)情節(jié)生成子超集Gen和頻繁閉情節(jié)超集FCE及情節(jié)規(guī)則集R，而情節(jié)規(guī)則集R是由Gen和FCE計(jì)算得來，因此空間復(fù)雜度為O(|Gen|?|FCE|)，遠(yuǎn)小于TASA和WinMiner算法。

6.2 實(shí)驗(yàn)評估

基于非重疊的最小發(fā)生的支持度定義，對經(jīng)典算法TASA和WinMiner算法進(jìn)行了調(diào)整，然后與本文的GFExtractor算法進(jìn)行了時(shí)空性能的比較。實(shí)驗(yàn)的硬件環(huán)境：2 GHz Intel?CoreTM2 Duo CPU，內(nèi)存2 GB，操作系統(tǒng)Windows XP，程序采用VC實(shí)現(xiàn)。實(shí)驗(yàn)數(shù)據(jù)集基于中國知網(wǎng)CNKI平臺的文獻(xiàn)資源，選用知網(wǎng)的一個(gè)WEB服務(wù)器上2010-09-01至2010-09-30之間的日志數(shù)據(jù)，內(nèi)容包括232 438條讀者閱讀文獻(xiàn)的事件序列，提取閱讀文獻(xiàn)的標(biāo)題為事件類型，閱讀時(shí)間為事件發(fā)生的時(shí)間，挖掘文獻(xiàn)之間的引用關(guān)系。

6.2.1 運(yùn)行時(shí)間和支持度閾值、置信度閾值的關(guān)系

圖2、圖3顯示，隨著支持度閾值或置信度閾值的減小，3種算法運(yùn)行時(shí)間均在增加，其中GFExtractor算法要優(yōu)于其他兩種算法，原因是該算法采用了深度優(yōu)先搜索策略，并應(yīng)用非生成子剪枝策略加快挖掘生成子情節(jié)的進(jìn)程。

圖2 置信度閾值為60%時(shí)運(yùn)行時(shí)間

圖3 支持度閾值為7時(shí)運(yùn)行時(shí)間

6.2.2 內(nèi)存開銷和支持度閾值、置信度閾值的關(guān)系

圖4、圖5顯示，隨著支持度閾值或置信度閾值的減小，3種算法的內(nèi)存開銷均在增加，GFExtractor算法要優(yōu)于其他兩種算法。原因是GFExtractor算法是從情節(jié)生成子集和頻繁閉情節(jié)集中抽取情節(jié)規(guī)則，不需要維護(hù)頻繁情節(jié)集合。

圖4 置信度閾值為60%時(shí)內(nèi)存開銷

圖5 支持度閾值為7時(shí)內(nèi)存開銷

6.2.3 規(guī)則數(shù)量和支持度閾值、置信度閾值的關(guān)系

圖6、圖7顯示，隨著支持度閾值或置信度閾值的減小，3種算法均產(chǎn)生了更多的情節(jié)規(guī)則，GFExtractor算法產(chǎn)生的規(guī)則數(shù)量要小于其他兩種算法，原因是GFExtractor算法是基于情節(jié)生成子集和頻繁閉情節(jié)集產(chǎn)生的無冗余情節(jié)規(guī)則，而其他算法是基于頻繁情節(jié)集產(chǎn)生的所有情節(jié)規(guī)則，存在冗余。

圖6 置信度閾值為60%時(shí)規(guī)則數(shù)量

圖7 支持度閾值為7時(shí)規(guī)則數(shù)量

7 結(jié)論

本文提出的GFExtractor算法基于非重疊的最小發(fā)生的支持度定義及深度優(yōu)先搜索策略，采用非生成子情節(jié)剪枝策略，及時(shí)淘汰非生成子情節(jié)，加快情節(jié)生成子的挖掘過程；采用雙向擴(kuò)展檢查判斷并淘汰非閉情節(jié)，加快頻繁閉情節(jié)的挖掘過程；在情節(jié)生成子集與頻繁閉情節(jié)集之間，有效刪除近似情節(jié)規(guī)則的冗余后件，最后產(chǎn)生無冗余的情節(jié)規(guī)則。理論分析和實(shí)驗(yàn)性能研究證明GFExtractor算法能有效地挖掘事件序列上的無冗余情節(jié)規(guī)則。

[1]Mannila H，Toivonen H，Verkamo A I.Discovering frequent episodes in sequences[C]//Proceedings of the 1stACM SICKDD ConferenceonKnowledgeDiscoveryandData Mining，Montreal，Canada，1995：210-215.

[2]Hatonen K，Klemettinen M，Mannila H，et al.Knowledge discovery from telecommunication network alarm databases[C]// Proceedings of the 12th IEEE International Conference on Data Engineering，New Orleans，Louisiana，1996：115-122.

[3]Meger N，Rigotti C.Constraint-based mining of episode rules and optimal window sizes[C]//Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Database，Pisa，Italy，2004：313-324.

[4]Hwang K，Cai M，Chen Y，et al.Hybrid intrusion detection with weighted signature generation over anomalous internet episodes[J].IEEE Transactionson Dependable and Secure Computing，2007，4（1）：41-55.

[5]Wang P，Wang H，Liu M，et al.An algorithmic approach to event summarization[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data，Indianapolis，Indiana，USA，2010：183-194.

[6]Patnaik D，Marwah M，Sharma R，et al.Sustainable operation and management of data center chillers using temporaldatamining[C]//Proceedingsofthe15thACM SIGKDD Conference on Knowledge Discovery and Data Mining，Paris，F(xiàn)rance，2009：1305-1313.

[7]Zhu H，Wang P，He X，et al.Efficient episode mining with minimal and non-overlapping occurrences[C]//Proceedings of the 10th IEEE International Conference on Data Mining，Sydney，Australia，2010：1211-1216.

[8]Bastide Y，Taouil R，Pasquier N，et al.Mining frequent patterns with counting inference[J].SIGKDD Explorations，2000，2（2）：66-75.

[9]Pasquier N，Bastide Y，Taouil R，et al.Discovering frequent closed itemsets for association rules[C]//Proceedings of the 7th International Conference on Database Theory，Jerusalem，Israel，1999：398-416.

[10]Li J，Li H，Wong L，et al.Minimum description length principle：generators are preferable to closed patterns[C]//Proceedings of the 21st National Conference on Artificial Intelligence Conference，Boston，Massachusetts，USA，2006：409-414.

[11]Bastide Y，Pasquier N，Taouil R，et al.Mining minimal non-redundant association rules using frequent closed itemsets[C]//Proceedings of the 1stInternationalConference on Computational Logic，London，UK，2000：972-986.

[12]Li J，Liu G，Wong L.Mining statistically important equivalence classes and delta-discriminative emerging patterns[C]// Proceedingsofthe13th ACM SICKDD Conferenceon Knowledge Discovery and Data Mining，San Jose，California，USA，2007：430-439.

[13]Lo D，Khoo S C，Li J.Mining and ranking generators of sequentialpatterns[C]//ProceedingsoftheSIAM International Conference on Data Mining，Atlanta，Georgia，USA，2008：553-564.

[14]朱輝生，汪衛(wèi)，施伯樂.基于頻繁閉情節(jié)及其生成子的無冗余情節(jié)規(guī)則抽取[J].計(jì)算機(jī)學(xué)報(bào)，2012（1）：53-63.

[15]Wang J，Han J.BIDE：efficient mining of frequent closed sequences[C]//Proceedings of the 20th International Conference on Data Engineering.Boston：IEEE，2004：79-90.

[16]朱輝生，汪衛(wèi)，施伯樂.基于最小且非重疊發(fā)生的頻繁閉情節(jié)挖掘[J].計(jì)算機(jī)研究與發(fā)展，2013（4）：852-860.

YUAN Hongjuan

School of Mathematics and Information,Taizhou University,Taizhou,Jiangsu 225300,China

Mining episode rules in event sequence aims to discover the causal relationship between the episodes.To mine non-redundant episode rules in event sequence,the algorithm of GFExtractor is proposed in this paper,based on the support definition of non-overlapping minimal occurrences and the depth-first search strategy.GFExtractor uses the pruning technology to eliminate non-generator episodes,and uses the forward and backward extension check to eliminate non-closed episodes.Nonredundant episode rules are generated between a superset of Gen and FCE.Experimental results confirm the validity of algorithm in mining non-redundant episode rules in event sequence.

episode generator;frequent closed episode;episode rules

事件序列上挖掘情節(jié)規(guī)則，旨在發(fā)現(xiàn)情節(jié)之間的因果關(guān)系?；诜侵丿B的最小發(fā)生的支持度定義及深度優(yōu)先搜索策略，提出在事件序列上挖掘無冗余情節(jié)規(guī)則的GFExtractor算法。利用非生成子情節(jié)的剪枝策略，淘汰非生成子情節(jié)；利用向前、向后擴(kuò)展檢查，淘汰非閉情節(jié)；最終在情節(jié)生成子集Gen與頻繁閉情節(jié)集FCE之間產(chǎn)生無冗余的情節(jié)規(guī)則。實(shí)驗(yàn)結(jié)果證實(shí)了算法在事件序列上挖掘無冗余情節(jié)規(guī)則的有效性。

情節(jié)生成子；頻繁閉情節(jié)；情節(jié)規(guī)則

A

TP311

10.3778/j.issn.1002-8331.1306-0271

YUAN Hongjuan.GFExtractor：algorithm of mining non-redundant episode rules effectively in event sequence.Computer Engineering and Applications,2013,49（23）：106-111.

袁紅娟（1979—），女，講師，研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘。E-mail：yhj_blue@126.com

2013-06-24

2013-09-04

1002-8331（2013）23-0106-06