基于包含與演繹分析的無冗余序列規則挖掘

周　新　王乙民　劉　婧　尤　濤

1(西安市煙草專賣局　陜西 西安 710061)2(西北工業大學計算機學院　陜西 西安 710129)

?

基于包含與演繹分析的無冗余序列規則挖掘

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

1(西安市煙草專賣局陜西 西安 710061)2(西北工業大學計算機學院陜西 西安 710129)

序列規則挖掘旨在發現頻繁序列之間的因果關聯，當前最優的序列規則產生方法僅考慮兩規則間的包含關系而沒有考慮多規則間的演繹關系，故而存在大量冗余。引入演繹無冗余規則的概念，分析演繹冗余的原因，重新定義了無冗余規則的概念。在頻繁閉序列及其生成子的基礎上，基于最大重疊項冗余性檢查給出了無冗余規則抽取算法。理論分析和實驗評估表明該算法在處理效率基本不變的前提下，提高了序列規則的生成質量。

事件序列規則包含演繹無冗余

0　引　言

隨著計算機和因特網技術的迅猛發展，從各種各樣應用中收集到的數據量越來越龐大，從海量數據中挖掘出有價值的信息和知識已經成為數據挖掘研究領域中的重要任務之一[1]。序列作為一種重要數據形式，刻畫了事件之間的緊隨關系，而序列間的因果關聯通過序列規則描述。基于序列規則[2]的預測被廣泛運用在科學與工程學、商業、客戶行為分析、股票趨勢預測、DNA 序列分析、Web使用行為分析等領域。但目前的序列規則挖掘算法往往產生大量的多余規則。以最具代表性的包含無冗余規則生成算法Extractor[3]為例，其挖掘結果仍然存在冗余。

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

表3所列的規則，按照包含無冗余序列規則的定義，已經是最精簡的序列規則。但仔細觀察不難發現，規則和實際可演繹出規則。導出過程如下：由規則可知AB的支持度為3；由規則可知ABACE的支持度為2。依計算可知，以AB為規則前件、ACE為規則后件的序列規則支持度為2，置信度為67%。因此表3中，為多余規則。

而挖掘結果中的冗余不僅會加大相關應用系統的負擔，也不利于工作人員理解，制約工作效率。

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

表1　ES上的頻繁閉序列

表2　ES上的序列生成子

表3　ES上的包含無冗余序列規則

1　研究現狀

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

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

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

產生最小前件序列規則全集的典型算法為GenMiner[6]，其規則基為頻繁序列與生成子。算法首先采用深度優先的搜索策略來創建存儲所有序列的前綴搜索樹PSL，然后通過遍歷PSL得到包含所有序列模式生成子的超集，據此可以得到最小前件序列規則。

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

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

2　SRRM

2.1 相關定義[7]

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

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

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

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

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

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

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

2.2演繹規則

可見包含無冗余序列規則是對兩規則間包含關系進行的約簡。下面我們給出多規則間的演繹關系。

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

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

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

定義9給定序列規則γ(l,r,s,c,w)，若不存在序列規則γ′(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)同時成立。即γ不可以從其他規則產生，則稱γ是一個演繹無冗余規則，否則是一個演繹冗余規則。

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

表5　規則演繹的情況分解表

對于情形1來說，已知γ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)，假設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可推導。

對于情形2來說，推導過程與情形1類似，只是增加了γ1·l≠γ2·l的條件，并不影響結論。情形2可推導。

對于情形3來說，已知γ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，假設γ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可推導。

對于情形4來說，推導過程與情形3類似，只是增加了concat(γ1·l,γ1·r)≠concat(γ2·l,γ2·r)的條件，并不影響結論。情形4可推導。

對于情形5來說，已知γ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可推導。

定義10(無冗余規則)。滿足包含無冗余特征和演繹無冗余特征的規則集合稱為無冗余規則。可見無冗余規則既避免了兩規則間的包含關系，又避免了多規則間的演繹關系。

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

2.3SRRM算法流程

通過分析包含無冗余序列規則的產生過程可知，生成子向頻繁閉序列投影時，對于互相重疊的生成子和閉序列，它們既可作為閉序列被其他生成子投影，又可作為生成子向其他閉序列投影，這造成了冗余演繹規則。

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

定理2生成子向頻繁閉序列投影時，對互相重疊的生成子和閉序列，重疊集內部會存在互相包含關系，這些關系中，只需考慮最大的重疊項進行演繹規則冗余檢查即可。

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

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

算法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

經過演繹規則冗余性檢查，表3中的規則，，可被刪除。

2.4 算法性能分析

設L為事件序列ES的長度，ε為ES中的事件類型集，FE為ES上所有頻繁序列組成的集合，則算法SRRM的復雜度分析如下。

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

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

可見，相比與當前最優的包含無冗余序列規則挖掘算法Extractor，沒有增加任何時空消耗。

3　實　驗

3.1實驗設計

實驗采用來自煙草網絡[8]日志數據庫的真實數據集，選取一個煙草網站服務器上的2013年第20周的日志數據，該數據包括了456個用戶的總計163 514個操作，操作類型有400種。我們選取當前最優的Extractor算法與SRRM對比，程序采用C++實現。實驗所在計算機的配置為CPU INTEL E8500 2.93 GHz，RAM 4 GB，Windows XP Professional。

3.2實驗結果

實驗1規則個數與置信度閾值的關系。設min_sup=10，通過置信度不斷變更，得到了兩算法在規則產生情況上的對比(如圖1所示)。可見，隨著置信度閾值的減少，兩個算法均發現了更多的序列規則，這是由于置信度閾值越小，將會有更多的規則滿足閾值約束。同時，SRRM發現的規則個數少于Extractor。這是因為SRRM產生的是無冗余規則集，Extractor產生的是包含無冗余序列規則集。當置信度為30%時，存在的演繹規則冗余較大，平均下來SRRM得到的規則與Extractor得到的規則相比，下降了近50%。當置信度為70%時，存在的演繹規則冗余小，平均下來SRRM得到的規則與Extractor得到的規則相比，下降了30%左右。

實驗2規則個數與支持度閾值的關系。設置信度閾值為50%，通過min_sup不斷變更，得到了兩算法在規則產生情況上的對比(如圖2所示)。可以看出，隨著支持度閾值的減少，算法均發現了更多的序列規則，而SRRM發現的規則個數少于Extractor。原因同實驗1。

圖1　規則個數和置信度閾值關系圖　圖2　規則個數和支持度閾值關系圖

實驗3規則個數與序列長度的關系。設min_sup=10，置信度閾值為60%，得到了序列長度對兩算法產生規則的影響情況(如圖3所示)。可見，隨著序列長度的增加(從1天到5天)，算法均發現了更多的序列規則，但SRRM發現的規則個數少于Extractor。原因同實驗1。

由于兩算法的時空復雜度相同，所以兩個算法的執行效率比較，我們只列出各運行時間與置信度閾值的關系，其他情況這里就不再贅述。

實驗4運行時間與置信度閾值的關系。設min_sup=10，通過置信度不斷變更，得到了兩算法運行時間上的對比(如圖4所示)。可見，隨著置信度閾值的減少，算法的運行時間都線性增加，SRRM執行時間較Extractor略高，這是由于它還需要進行演繹規則檢查。

圖3　規則個數和序列長度關系圖　圖4　運行時間和置信度閾值關系圖

各實驗聯合分析，SRRM雖然在處理時間上略有增加，但卻將規則個數精簡了許多。

4　結　語

針對當前最優的包含無冗余序列規則產生方法沒有考慮序列規則間的演繹關系因素，故而存在大量冗余的問題，本文引入了無冗余演繹規則的概念，提出了新的無冗余序列規則概念呢，并給出了無冗余序列規則生成方法。理論分析和實驗評估表明該算法能對包含無冗余序列規則進行進一步壓縮，提供了更為精簡的序列規則。當然，序列規則挖掘只是序列預測的第一步，后續工作我們將研究基于無冗余序列規則的預測方法。

[1] Thiet P T H I.基于前綴樹結構的序列模式挖掘算法研究[D].湖南大學,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] 朱輝生,汪衛,施伯樂.基于頻繁閉序列及其生成子的無冗余序列規則抽取[J].計算機學報,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].中國工業經濟,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。國家自然科學基金項目(61303225)。周新，本科，主研領域：數據挖掘，數據流處理。王乙民，本科。劉婧，本科。尤濤，講師。

TP311.13

A

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