周　新　王乙民　劉　婧　尤　濤

1(西安市煙草專賣局　陜西 西安 710061)2(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院　陜西 西安 710129)

?

基于包含與演繹分析的無(wú)冗余序列規(guī)則挖掘

周新1,2王乙民1劉婧1尤濤2

1(西安市煙草專賣局陜西 西安 710061)2(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院陜西 西安 710129)

序列規(guī)則挖掘旨在發(fā)現(xiàn)頻繁序列之間的因果關(guān)聯(lián)，當(dāng)前最優(yōu)的序列規(guī)則產(chǎn)生方法僅考慮兩規(guī)則間的包含關(guān)系而沒有考慮多規(guī)則間的演繹關(guān)系，故而存在大量冗余。引入演繹無(wú)冗余規(guī)則的概念，分析演繹冗余的原因，重新定義了無(wú)冗余規(guī)則的概念。在頻繁閉序列及其生成子的基礎(chǔ)上，基于最大重疊項(xiàng)冗余性檢查給出了無(wú)冗余規(guī)則抽取算法。理論分析和實(shí)驗(yàn)評(píng)估表明該算法在處理效率基本不變的前提下，提高了序列規(guī)則的生成質(zhì)量。

事件序列規(guī)則包含演繹無(wú)冗余

0　引　言

隨著計(jì)算機(jī)和因特網(wǎng)技術(shù)的迅猛發(fā)展，從各種各樣應(yīng)用中收集到的數(shù)據(jù)量越來(lái)越龐大，從海量數(shù)據(jù)中挖掘出有價(jià)值的信息和知識(shí)已經(jīng)成為數(shù)據(jù)挖掘研究領(lǐng)域中的重要任務(wù)之一[1]。序列作為一種重要數(shù)據(jù)形式，刻畫了事件之間的緊隨關(guān)系，而序列間的因果關(guān)聯(lián)通過序列規(guī)則描述?；谛蛄幸?guī)則[2]的預(yù)測(cè)被廣泛運(yùn)用在科學(xué)與工程學(xué)、商業(yè)、客戶行為分析、股票趨勢(shì)預(yù)測(cè)、DNA 序列分析、Web使用行為分析等領(lǐng)域。但目前的序列規(guī)則挖掘算法往往產(chǎn)生大量的多余規(guī)則。以最具代表性的包含無(wú)冗余規(guī)則生成算法Extractor[3]為例，其挖掘結(jié)果仍然存在冗余。

我們來(lái)看下面的例子：某煙草管理局Web服務(wù)器上記載的一條用戶對(duì)多個(gè)品牌香煙的事務(wù)記錄，ES=。根據(jù)這些序列，需要找出該用戶的操作行為規(guī)則，從而有助于煙草管理局人員發(fā)現(xiàn)用戶操作之間的關(guān)聯(lián)、非法操作的流程。在支持度閾值minsup=2時(shí)，ES上所有的頻繁閉序列如表1所示，生成子如表2所示。通過運(yùn)行算法Extractor在序列ES上發(fā)現(xiàn)的所有的包含無(wú)冗余序列規(guī)則如表3所示。序列規(guī)則表達(dá)采用五元組的方式給出，例如某規(guī)則中，AAB和CD分別是規(guī)則的前件和后件，40為支持度，70%是置信度，9為窗口寬度。

表3所列的規(guī)則，按照包含無(wú)冗余序列規(guī)則的定義，已經(jīng)是最精簡(jiǎn)的序列規(guī)則。但仔細(xì)觀察不難發(fā)現(xiàn)，規(guī)則和實(shí)際可演繹出規(guī)則。導(dǎo)出過程如下：由規(guī)則可知AB的支持度為3；由規(guī)則可知ABACE的支持度為2。依計(jì)算可知，以AB為規(guī)則前件、ACE為規(guī)則后件的序列規(guī)則支持度為2，置信度為67%。因此表3中，為多余規(guī)則。

而挖掘結(jié)果中的冗余不僅會(huì)加大相關(guān)應(yīng)用系統(tǒng)的負(fù)擔(dān)，也不利于工作人員理解，制約工作效率。

據(jù)此，本文引入了演繹無(wú)冗余規(guī)則的概念，提出一種新的無(wú)冗余序列規(guī)則約簡(jiǎn)算法SRRM(Sequence rules reduction method)。該算法在傳統(tǒng)包含無(wú)冗余序列規(guī)則的基礎(chǔ)上，基于演繹規(guī)則約簡(jiǎn)的方法產(chǎn)生出序列規(guī)則的精簡(jiǎn)集。理論分析和實(shí)驗(yàn)評(píng)估證明該算法能有效地抽取給定事件序列上的序列規(guī)則，與包含無(wú)冗余序列規(guī)則相比，規(guī)則數(shù)量平均降低30%左右。

表1　ES上的頻繁閉序列

表2　ES上的序列生成子

表3　ES上的包含無(wú)冗余序列規(guī)則

1　研究現(xiàn)狀

已有規(guī)則挖掘的各類算法，雖然在數(shù)據(jù)組織、處理流程等方面各有不同，但主要分為三類，如表4所示。

表4　典型序列規(guī)則挖掘算法分類比較

產(chǎn)生序列規(guī)則全集的典型算法為TASA[4]、WinMiner[5]，該類算法以頻繁序列為規(guī)則基，通過投影的方式產(chǎn)生序列規(guī)則全集。

產(chǎn)生最小前件序列規(guī)則全集的典型算法為GenMiner[6]，其規(guī)則基為頻繁序列與生成子。算法首先采用深度優(yōu)先的搜索策略來(lái)創(chuàng)建存儲(chǔ)所有序列的前綴搜索樹PSL，然后通過遍歷PSL得到包含所有序列模式生成子的超集，據(jù)此可以得到最小前件序列規(guī)則。

產(chǎn)生包含無(wú)冗余序列規(guī)則集的典型算法為Extractor[3]，其規(guī)則基為頻繁閉序列與生成子。算法采用最小且非重疊發(fā)生的支持度定義和深度優(yōu)先的搜索策略來(lái)發(fā)現(xiàn)頻繁閉序列及其生成子；直接由頻繁閉序列及其生成子產(chǎn)生序列規(guī)則。Extractor算法的規(guī)則基——閉序列及其生成子已被證明可產(chǎn)生具有最小前件和最大后件的包含無(wú)冗余序列規(guī)則[7,8]。

從上述序列規(guī)則挖掘算法的發(fā)展不難看出，規(guī)則的產(chǎn)生方式經(jīng)歷了頻繁序列投影、頻繁序列及其生成子投影、頻繁閉序列及其生成子投影等階段；算法的效率、精確程度、精簡(jiǎn)粒度都在逐步提高。但卻忽略了多規(guī)則間的關(guān)聯(lián)關(guān)系在挖掘過程中的作用，造成了引言所述的規(guī)則冗余。本文引入的SRRM可有效解決這一問題。

2　SRRM

2.1 相關(guān)定義[7]

定義1(事件，事件流)。事件是給定事件類型集ε={E1,E2,…,En}中的事件E和事件發(fā)生時(shí)間t的二元組(E,t)。事件流是由若干ε中的事件按發(fā)生時(shí)間先后排列的序列，表示為ES=<(E1,t1),(E2,t2),…,(Es,ts)>。

定義2(序列)。一個(gè)序列是由若干事件組成的串，表示為α=<(E1,t1),(E2,t2),…,(Ek,tk)>，簡(jiǎn)記為α=。

定義4(發(fā)生)。給定事件流ES和序列α=，若ES在時(shí)間區(qū)間[t1,tk]上按α的事件排列順序出現(xiàn)了α所代表的所有事件，則稱ES上發(fā)生了序列α，時(shí)間區(qū)間[t1,tk]稱為α在ES上的一次發(fā)生。

定義5(支持度)。序列α在事件流ES上所有發(fā)生的數(shù)目稱為α的支持度，記為α·sup。

定義6(頻繁序列，頻繁閉序列，序列生成子)。給定支持度閾值min_sup，若序列α的支持度大于等于min_sup，則α是一個(gè)頻繁序列。若序列α是頻繁的，且α的支持度不等于α的任何一個(gè)真超序列的支持度，則α是一個(gè)頻繁閉序列。設(shè)f是一個(gè)閉序列，g?f，若g的支持度等于f的支持度，且g不存在與其支持度相同的任何一個(gè)真子序列，則g稱為閉序列f的一個(gè)序列生成子。

定義7(序列規(guī)則)。一個(gè)序列規(guī)則γ是一個(gè)五元組(l,r,s,c,ω)。其中γ的前件、后件、支持度、置信度和窗口寬度分別記為l、r、s、c、ω。

定義8給定序列規(guī)則γ(l,r,s,c,w)，若不存在序列規(guī)則γ′(l,r,s,c,w)，使得γ′·s=γ.s，γ′·c?γ·c，γ′·l?γ·l，γ′·r?γ·r，則稱γ是一個(gè)包含無(wú)冗余序列規(guī)則，否則是一個(gè)包含冗余序列規(guī)則。

2.2演繹規(guī)則

可見包含無(wú)冗余序列規(guī)則是對(duì)兩規(guī)則間包含關(guān)系進(jìn)行的約簡(jiǎn)。下面我們給出多規(guī)則間的演繹關(guān)系。

定理1規(guī)則演繹。如果規(guī)則γ、γ′、γ″之間，滿足(1) γ·l=γ′·l或者γ·l=concat(γ′·l,γ′·r)；(2) concat(γ·l,γ·r)=γ″·l或者concat(γ·l,γ·r)=concat(γ″·l,γ″·r)，則γ′∩γ″?γ。

證明：γ′·l、concat(γ′·l,γ′·r)的支持度可以由規(guī)則γ′得到，而γ·l滿足條件(1)，即γ·l的支持度可知；γ″·l、concat(γ″·l,γ″·r)的支持度可以由規(guī)則γ″得到，而concat(γ·l,γ·r)滿足條件(2)，即concat(γ·l,γ·r)的支持度可知；進(jìn)而可以計(jì)算規(guī)則γ的支持度、置信度，確定其窗口寬度。因此γ′∩γ″?γ。定理1得證。

由規(guī)則間的演繹定理，我們可以得到演繹無(wú)冗余規(guī)則的概念如下。

定義9給定序列規(guī)則γ(l,r,s,c,w)，若不存在序列規(guī)則γ′(l,r,s,c,w)、γ″(l,r,s,c,w)，使得(1) γ·l=γ′·l或者γ·l=concat(γ′·l,γ′·r)；(2) concat(γ·l,γ·r)=γ″·l或者concat(γ·l,γ·r)=concat(γ″·l,γ″·r)同時(shí)成立。即γ不可以從其他規(guī)則產(chǎn)生，則稱γ是一個(gè)演繹無(wú)冗余規(guī)則，否則是一個(gè)演繹冗余規(guī)則。

定理1和定義9分別給出了規(guī)則演繹和演繹無(wú)冗余規(guī)則的最一般描述，對(duì)描述進(jìn)行展開，可以得到規(guī)則演繹的各種情況如表5所示。為了不失一般性，我們對(duì)表5所示的各種情況分析如下。

表5　規(guī)則演繹的情況分解表

對(duì)于情形1來(lái)說(shuō)，已知γ1(l,r,s,c,w)和γ2(l,r,s,c,w)，γ1·l=γ2·l，concat(γ1·l,γ1·r)?concat(γ2·l,γ2·r)或concat(γ1·l,γ1·r)?concat(γ2·l,γ2·r)，假設(shè)concat(γ1·l,γ1·r)?concat(γ2·l,γ2·r)則必有concat(γ1·l,γ1·r)->project(concat(γ2·l,γ2·r),concat(γ1·l,γ1·r))，即γ3·l=concat(γ1·l,γ1·r)，γ3·r=project(concat(γ2·l,γ2·r),concat(γ1·l,γ1·r))，而γ3·s=γ2·s，γ3·c=γ2·s/γ1·s，情形1可推導(dǎo)。

對(duì)于情形2來(lái)說(shuō)，推導(dǎo)過程與情形1類似，只是增加了γ1·l≠γ2·l的條件，并不影響結(jié)論。情形2可推導(dǎo)。

對(duì)于情形3來(lái)說(shuō)，已知γ1(l,r,s,c,w)和γ2(l,r,s,c,w)，concat(γ1·l,γ1·r)=concat(γ2·l,γ2·r)，γ1·l?γ2·l或γ2·l?γ1·l，假設(shè)γ1·l?γ2·l則必有γ1·l->project(γ2·l,γ1·l)，即γ3·l=γ1·l，γ3·r=project(γ2·l,γ1·l)，而γ3·s=γ2·s/γ2·c，γ3·c=(γ2·s/γ2·c)/(γ1·s/γ1·c)，情形3可推導(dǎo)。

對(duì)于情形4來(lái)說(shuō)，推導(dǎo)過程與情形3類似，只是增加了concat(γ1·l,γ1·r)≠concat(γ2·l,γ2·r)的條件，并不影響結(jié)論。情形4可推導(dǎo)。

對(duì)于情形5來(lái)說(shuō)，已知γ1(l,r,s,c,w)和γ2(l,r,s,c,w)，γ1·l≠γ2·l，concat(γ1·l,γ1·r)≠concat(γ2·l,γ2·r)。γ1·l?concat(γ2·l,γ2·r)則必有γ1·l->project(concat(γ2·l,γ2·r),γ1·l)，即γ3·l=γ1·l，γ3·r=project(concat(γ2·l,γ2·r),γ1·l)，而γ3·s=γ2·s，γ3·c=γ2·s/(γ1·s/γ1·c)，情形5可推導(dǎo)。

定義10(無(wú)冗余規(guī)則)。滿足包含無(wú)冗余特征和演繹無(wú)冗余特征的規(guī)則集合稱為無(wú)冗余規(guī)則?？梢姛o(wú)冗余規(guī)則既避免了兩規(guī)則間的包含關(guān)系，又避免了多規(guī)則間的演繹關(guān)系。

文獻(xiàn)[3]依據(jù)頻繁閉序列和生成子，按照生成子在閉序列投影的方式，產(chǎn)生了包含無(wú)冗余序列規(guī)則，而這些規(guī)則中蘊(yùn)含了冗余的演繹規(guī)則。如何在包含無(wú)冗余序列規(guī)則中過濾到冗余的演繹規(guī)則呢？直觀的看，可以依據(jù)定義通過事后檢查的方式進(jìn)行過濾。但是這種事后過濾的方法仍需要遍歷整個(gè)規(guī)則集合，增加了處理的時(shí)間。下面我們從規(guī)則產(chǎn)生的過程中，分析冗余演繹規(guī)則的產(chǎn)生原因，得出其過濾算法。

2.3SRRM算法流程

通過分析包含無(wú)冗余序列規(guī)則的產(chǎn)生過程可知，生成子向頻繁閉序列投影時(shí)，對(duì)于互相重疊的生成子和閉序列，它們既可作為閉序列被其他生成子投影，又可作為生成子向其他閉序列投影，這造成了冗余演繹規(guī)則。

因此在生成規(guī)則的過程中，通過檢查、過濾機(jī)制就可以有效避免冗余演繹規(guī)則的產(chǎn)生。但即便如此，由于投影關(guān)系的傳遞性，進(jìn)行可演繹規(guī)則的過濾仍然是復(fù)雜的。為了提高演繹規(guī)則的過濾效率，我們給出如下定理。

定理2生成子向頻繁閉序列投影時(shí)，對(duì)互相重疊的生成子和閉序列，重疊集內(nèi)部會(huì)存在互相包含關(guān)系，這些關(guān)系中，只需考慮最大的重疊項(xiàng)進(jìn)行演繹規(guī)則冗余檢查即可。

證明：設(shè)有生成子g0、g1、g2，g1、g2是重疊集中的元素，并且g0可以投影到g1，g1可以投影到g2。由于投影規(guī)則是可傳遞的，g0也可以投影到g2，記為g0-g1-g2。設(shè)有閉序列e，滿足g2-e，則有g(shù)0-g1-g2-e。根據(jù)定理1，對(duì)于g0-g1-e而言，g0-e、g1-e兩條規(guī)則蘊(yùn)含g0-g1；對(duì)于g0-g2-e而言，g0-e、g2-e兩條規(guī)則蘊(yùn)含g0-g2；對(duì)于g1-g2-e而言，g1-e、g2-e兩條規(guī)則蘊(yùn)含g1-g2。可以看出，由g0-g1-e所產(chǎn)生的規(guī)則g0-e、g1-e完全包含在g1-g2-e、g0-g2-e所產(chǎn)生的規(guī)則中，而g2為重疊集中較大的元素。以此類推，可證明在進(jìn)行演繹規(guī)則冗余檢查時(shí)，只需要檢查重疊集最大元素的投影和被投影情況即可。得證。

依據(jù)定理2，生成規(guī)則的流程如算法所示。其中，1～13步為找出檢查重疊集最大的元素；14～18步找出最大元素的所有投影和被投影元素；19～29步為冗余演繹規(guī)則的過濾過程，即最大重疊元素的一次投影和被投影過程中，最多只產(chǎn)生兩個(gè)規(guī)則；30～35步為生成子和閉序列無(wú)重疊情況的規(guī)則產(chǎn)生?？梢?，算法依據(jù)重疊集的最大元素過濾掉了演繹序列規(guī)則，而算法本身產(chǎn)生的就是包含無(wú)冗余序列規(guī)則，最終產(chǎn)生了無(wú)冗余序列規(guī)則。

算法Precedure SRRM(Set ee, Set ge)

Input：ee：a set of non-redundant sequences

ge：a set of generatora

Output：result：a set of non-redundant sequence rules

1.Let result = empty

2.Find ge′ in ge which ge′ has the same item in ee

3.For each g1and g2in ge′

4. If g1can project to g2

5. Delete g1in ge′

6. If g2can project to g1

7. Delete g2in ge′

8.Let ge = ge - ge′ //找到閉序列和生成子的公共集合ge并去除ge中的重疊元素

9.Let gee = empty

10.For each g in gee

11. If g can project to one item in ge′

12. gee.add(g)

//找出ge中的可被投影集合gee

13.Let ge = ge -gee

14.Let ee′ = empty

15.For each e in ee

16. If one item in ge′ can project to e

17. ee′.add(e)

//找出ee中的可被ge中元素投影集合

18.Let ee = ee- ee′

19.For each g1in gee and g2in ge′ and e1 in ee′

20. If g1can project to g2and g2can project to e1

21. Let r =project(g1, g2)

22. Let a=contact(g1,r)

23. If a.sup/g.sup>=minconf

24. result.add(g1,r,a.sup,a.sup/g1.sup,a.w)

25. Let r=project(g2, e1)

26. Let a=contact(g2,r)

27. If a.sup/g.sup>=minconf

28. result.add(g2,r,a.sup,a.sup/g2.sup,a.w)

29.For each f in ee and g in ge

30. If g can project to f

31. Let r=project(g,f)

32. Let a=contact(g,r)

33. If a.sup/g.sup>=minconf

34. result.add(g,r,a.sup,a.sup/g.sup,a.w)

35.Return result

經(jīng)過演繹規(guī)則冗余性檢查，表3中的規(guī)則，，可被刪除。

2.4 算法性能分析

設(shè)L為事件序列ES的長(zhǎng)度，ε為ES中的事件類型集，F(xiàn)E為ES上所有頻繁序列組成的集合，則算法SRRM的復(fù)雜度分析如下。

時(shí)間復(fù)雜度：算法首先需要找到生成子集中具有和FE中相同元素的且之間不含前綴包含關(guān)系的生成子集gee，其復(fù)雜度為O(|FE|*|FE|)，然后需要在FE中分別找到FE可以對(duì)gee中元素進(jìn)行投影的元素集合以及gee可以對(duì)FE中元素進(jìn)行投影的元素集合，其復(fù)雜度皆為O(|FE|*|FE|)。此外，規(guī)則產(chǎn)生時(shí)需要將序列生成子一一投影到所有的頻繁閉序列中進(jìn)行規(guī)則產(chǎn)生，所以規(guī)則產(chǎn)生過程所需的時(shí)間復(fù)雜度為O(|FE|*|FE|)。

空間復(fù)雜度：由于需要維護(hù)所有的規(guī)則信息，最壞情況下空間復(fù)雜度為O(|FE|*|FE|)。因此空間復(fù)雜度為O(|FE|*|FE|)。

可見，相比與當(dāng)前最優(yōu)的包含無(wú)冗余序列規(guī)則挖掘算法Extractor，沒有增加任何時(shí)空消耗。

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

3.1實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)采用來(lái)自煙草網(wǎng)絡(luò)[8]日志數(shù)據(jù)庫(kù)的真實(shí)數(shù)據(jù)集，選取一個(gè)煙草網(wǎng)站服務(wù)器上的2013年第20周的日志數(shù)據(jù)，該數(shù)據(jù)包括了456個(gè)用戶的總計(jì)163 514個(gè)操作，操作類型有400種。我們選取當(dāng)前最優(yōu)的Extractor算法與SRRM對(duì)比，程序采用C++實(shí)現(xiàn)。實(shí)驗(yàn)所在計(jì)算機(jī)的配置為CPU INTEL E8500 2.93 GHz，RAM 4 GB，Windows XP Professional。

3.2實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)1規(guī)則個(gè)數(shù)與置信度閾值的關(guān)系。設(shè)min_sup=10，通過置信度不斷變更，得到了兩算法在規(guī)則產(chǎn)生情況上的對(duì)比(如圖1所示)?？梢姡S著置信度閾值的減少，兩個(gè)算法均發(fā)現(xiàn)了更多的序列規(guī)則，這是由于置信度閾值越小，將會(huì)有更多的規(guī)則滿足閾值約束。同時(shí)，SRRM發(fā)現(xiàn)的規(guī)則個(gè)數(shù)少于Extractor。這是因?yàn)镾RRM產(chǎn)生的是無(wú)冗余規(guī)則集，Extractor產(chǎn)生的是包含無(wú)冗余序列規(guī)則集。當(dāng)置信度為30%時(shí)，存在的演繹規(guī)則冗余較大，平均下來(lái)SRRM得到的規(guī)則與Extractor得到的規(guī)則相比，下降了近50%。當(dāng)置信度為70%時(shí)，存在的演繹規(guī)則冗余小，平均下來(lái)SRRM得到的規(guī)則與Extractor得到的規(guī)則相比，下降了30%左右。

實(shí)驗(yàn)2規(guī)則個(gè)數(shù)與支持度閾值的關(guān)系。設(shè)置信度閾值為50%，通過min_sup不斷變更，得到了兩算法在規(guī)則產(chǎn)生情況上的對(duì)比(如圖2所示)?？梢钥闯?，隨著支持度閾值的減少，算法均發(fā)現(xiàn)了更多的序列規(guī)則，而SRRM發(fā)現(xiàn)的規(guī)則個(gè)數(shù)少于Extractor。原因同實(shí)驗(yàn)1。

圖1　規(guī)則個(gè)數(shù)和置信度閾值關(guān)系圖　圖2　規(guī)則個(gè)數(shù)和支持度閾值關(guān)系圖

實(shí)驗(yàn)3規(guī)則個(gè)數(shù)與序列長(zhǎng)度的關(guān)系。設(shè)min_sup=10，置信度閾值為60%，得到了序列長(zhǎng)度對(duì)兩算法產(chǎn)生規(guī)則的影響情況(如圖3所示)?？梢姡S著序列長(zhǎng)度的增加(從1天到5天)，算法均發(fā)現(xiàn)了更多的序列規(guī)則，但SRRM發(fā)現(xiàn)的規(guī)則個(gè)數(shù)少于Extractor。原因同實(shí)驗(yàn)1。

由于兩算法的時(shí)空復(fù)雜度相同，所以兩個(gè)算法的執(zhí)行效率比較，我們只列出各運(yùn)行時(shí)間與置信度閾值的關(guān)系，其他情況這里就不再贅述。

實(shí)驗(yàn)4運(yùn)行時(shí)間與置信度閾值的關(guān)系。設(shè)min_sup=10，通過置信度不斷變更，得到了兩算法運(yùn)行時(shí)間上的對(duì)比(如圖4所示)?？梢?，隨著置信度閾值的減少，算法的運(yùn)行時(shí)間都線性增加，SRRM執(zhí)行時(shí)間較Extractor略高，這是由于它還需要進(jìn)行演繹規(guī)則檢查。

圖3　規(guī)則個(gè)數(shù)和序列長(zhǎng)度關(guān)系圖　圖4　運(yùn)行時(shí)間和置信度閾值關(guān)系圖

各實(shí)驗(yàn)聯(lián)合分析，SRRM雖然在處理時(shí)間上略有增加，但卻將規(guī)則個(gè)數(shù)精簡(jiǎn)了許多。

4　結(jié)　語(yǔ)

針對(duì)當(dāng)前最優(yōu)的包含無(wú)冗余序列規(guī)則產(chǎn)生方法沒有考慮序列規(guī)則間的演繹關(guān)系因素，故而存在大量冗余的問題，本文引入了無(wú)冗余演繹規(guī)則的概念，提出了新的無(wú)冗余序列規(guī)則概念呢，并給出了無(wú)冗余序列規(guī)則生成方法。理論分析和實(shí)驗(yàn)評(píng)估表明該算法能對(duì)包含無(wú)冗余序列規(guī)則進(jìn)行進(jìn)一步壓縮，提供了更為精簡(jiǎn)的序列規(guī)則。當(dāng)然，序列規(guī)則挖掘只是序列預(yù)測(cè)的第一步，后續(xù)工作我們將研究基于無(wú)冗余序列規(guī)則的預(yù)測(cè)方法。

[1] Thiet P T H I.基于前綴樹結(jié)構(gòu)的序列模式挖掘算法研究[D].湖南大學(xué),2013.

[2] Sarawagi S,Thomas S,Agrawal R.Integrating association rule mining with relational database systems:Alternatives and implications[C]//Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data,1998:343-354.

[3] 朱輝生,汪衛(wèi),施伯樂.基于頻繁閉序列及其生成子的無(wú)冗余序列規(guī)則抽取[J].計(jì)算機(jī)學(xué)報(bào),2012,35(1):53-64.

[4] 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.

[5] 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 Databases.Pisa,Italy,2004:313-324.

[6] Lo D,Khoo S C,Li J.Mining and Ranking Generators of Sequential Patterns[C]//SDM,2008:553-564.

[7] Van Der Aalst W.Process mining:Overview and opportunities[J].ACM Transactions on Management Information Systems (TMIS),2012,3(2):7.

[8] Sarawagi S,Thomas S,Agrawal R.Integrating association rule mining with relational database systems:Alternatives and implications[C]//Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data,1998:343-354.

[9] 王樹文,張永偉,郭全中.加快推進(jìn)中國(guó)煙草行業(yè)改革研究[J].中國(guó)工業(yè)經(jīng)濟(jì),2005(2):34-38.

NON-REDUNDANT SEQUENCE RULES MINING BASED ON INCLUSION AND DEDUCTION ANALYSIS

Zhou Xin1,2Wang Yimin1Liu Jing1You Tao2

1(Xi’anTobaccoMonopolyBureau,Xi’an710061,Shaanxi,China)2(SchoolofComputerScience,NorthwesternPolytechnicalUniversity,Xi’an710129,Shaanxi,China)

Sequence rule mining aims at finding the casual association between frequent sequences, current best sequence rules generation approach just considers the inclusion relationship between two rules but does not consider the deduction relationship among multi rules, therefore has lots redundancies. We introduce the concept of deductive non-redundant rules and analyse the reasons for deductive redundancy, as well as redefine the concept of non-redundant rules. We also present the non-redundant sequence rules extraction algorithm based on the maximum overlap term redundancy checking on the basis of frequent closed sequence and its generator. Theoretical analysis and experimental assessment demonstrate that this algorithm improves the generation quality of sequence rules with almost the same efficiency.

EventSequence ruleInclusionDeductionNon-redundant

2014-07-07。國(guó)家自然科學(xué)基金項(xiàng)目(61303225)。周新，本科，主研領(lǐng)域：數(shù)據(jù)挖掘，數(shù)據(jù)流處理。王乙民，本科。劉婧，本科。尤濤，講師。

TP311.13

A

10.3969/j.issn.1000-386x.2016.03.011