顧佩月 劉崢 李云 李濤

摘 要：對于事件序列中的時序依賴發(fā)現(xiàn)，傳統(tǒng)的頻繁情節(jié)發(fā)現(xiàn)方法一方面使用時間窗口機制挖掘事件之間簡單的關(guān)聯(lián)依賴，另一方面無法有效處理事件的交叉時序關(guān)聯(lián)。針對以上問題，提出了時滯情節(jié)發(fā)現(xiàn)的概念，在頻繁情節(jié)發(fā)現(xiàn)的基礎(chǔ)上，設(shè)計了一種基于相鄰事件匹配集（AEM）的時滯情節(jié)發(fā)現(xiàn)算法。首先，引入時滯的概率統(tǒng)計模型進行事件序列匹配，避免預(yù)先設(shè)定時間窗口，處理可能存在的交叉關(guān)聯(lián);然后，將時滯挖掘轉(zhuǎn)化為最優(yōu)化問題，使用迭代的方式得到時滯情節(jié)之間的時間間隔分布;最后，利用假設(shè)檢驗區(qū)分串行時滯情節(jié)和并行時滯情節(jié)。理論分析與實驗結(jié)果表明，與目前最新的時滯挖掘方法迭代最近事件（ICE）算法相比，基于AEM的時滯情節(jié)發(fā)現(xiàn)算法模擬的時滯分布與真實時滯分布的平均KL距離為0.056，縮短了20.68%。基于AEM的時滯情節(jié)發(fā)現(xiàn)算法通過時滯的概率統(tǒng)計模型衡量事件多種匹配情況的可能性，獲得一對多的相鄰事件匹配集，比ICE算法中的一對一匹配更加有效地模擬了實際情況。

關(guān)鍵詞：時序依賴;事件序列;頻繁情節(jié);時滯;概率統(tǒng)計模型

中圖分類號： TP391

文獻標志碼：A

Abstract： Concerning the problem that a predefined time window is usually used to mine simple association dependencies between events in the traditional frequent episode discovery， which cannot effectively handle interleaved temporal correlations between events， a concept of time-lag episode discovery was proposed. And on the basis of frequent episode discovery， Adjacent Event Matching set （AEM） based time-lag episode discovery algorithm was proposed. Firstly， a probability statistical model introduced with time-lag was introduced to realize event sequence matching and handle optional interleaved associations without a predefined time window. Then the discovery of time lag was formulated as an optimization problem which can be solved iteratively to obtain time interval distribution between time-lag episodes. Finally， the hypothesis test was used to distinguish serial and parallel time-lag episodes. The experimental results show that compared with Iterative Closest Event （ICE） algorithm which is the latest method of time-lag mining， the Kullback-Leibler （KL） divergence between true and experimental distributions discovered by AEM is 0.056 on average， which is decreased by 20.68%. AEM algorithm measures the possibility of multiple matches of events through a probability statistical model of time lag and obtains a one-to-many adjacent event matching set， which is more effective than the one-to-one matching set in ICE for simulating the actual situation.

Key words： temporal dependency; event sequence; frequent episode; time lag; probability statistical model

0 引言

近年來，隨著數(shù)據(jù)采集和存儲技術(shù)的不斷發(fā)展，各領(lǐng)域海量時序數(shù)據(jù)的研究逐漸成為數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的熱點問題[1]。時序數(shù)據(jù)通常記錄了事物隨著時間變化發(fā)展的不同狀態(tài)。

在各類領(lǐng)域中，時序數(shù)據(jù)通常會有兩種形式：第一種是時間序列，記錄連續(xù)時間內(nèi)事物變化值，例如股票數(shù)據(jù)、系統(tǒng)內(nèi)存占用率等;第二種是事件數(shù)據(jù)，記錄離散時間內(nèi)事物變化情況，例如購物籃數(shù)據(jù)[2]、Web數(shù)據(jù)[3]、社交網(wǎng)絡(luò)事件數(shù)據(jù)[4]等。同一事物的發(fā)展往往蘊含著一些不為人知的規(guī)律或固有模式，從事件數(shù)據(jù)中發(fā)現(xiàn)學習這些隱藏的有趣時序依賴模式，有助于對未來事物的發(fā)展進行預(yù)測或是對引起事件的根源進行追查。不同形式的時序數(shù)據(jù)依賴發(fā)現(xiàn)方式也有很大不同，本文主要研究離散時間上的序列集合，即事件數(shù)據(jù)中的時序依賴發(fā)現(xiàn)。

關(guān)聯(lián)規(guī)則[5]是現(xiàn)有工作中針對事件序列最簡單的時序依賴發(fā)現(xiàn)，也是后續(xù)許多時序依賴發(fā)現(xiàn)方法的基礎(chǔ)。關(guān)聯(lián)規(guī)則旨在發(fā)現(xiàn)時序數(shù)據(jù)中頻繁出現(xiàn)的項集，比較經(jīng)典的應(yīng)用就是購物籃數(shù)據(jù)。在此數(shù)據(jù)集中，每一條記錄代表一個客戶所有的購買記錄，通過關(guān)聯(lián)分析得到客戶可能同時購買的商品組合，從而幫助商場進行營銷。但是關(guān)聯(lián)規(guī)則的依賴事件是不考慮時間先后關(guān)系的，隨之又衍生了頻繁情節(jié)挖掘[6]，即在關(guān)聯(lián)規(guī)則的基礎(chǔ)上添加簡單的時間約束，通過設(shè)定時間窗口從發(fā)現(xiàn)的依賴中得知事件發(fā)生的先后順序。隨著生產(chǎn)應(yīng)用的需求變化，時序依賴發(fā)現(xiàn)中的時間參數(shù)從先后關(guān)系再到模糊的時間區(qū)間進而轉(zhuǎn)向具體的滯后時間挖掘。

在考慮兩類事件A、B之間的依賴時，通常是基于依賴存在于相鄰事件的假設(shè)上進行挖掘的，即若事件A、B是依賴的，那么事件B的發(fā)生只能與它之前的第一個事件A有關(guān)。但在實際復雜的生產(chǎn)環(huán)境中，事件之間的依賴不僅僅存在于相鄰發(fā)生，也有可能出現(xiàn)交叉依賴[7]的情況，導致無法判斷事件之間的對應(yīng)關(guān)系。例如圖1，在關(guān)聯(lián)規(guī)則、序列模式等時序依賴發(fā)現(xiàn)中，通常只考慮彼此相鄰的兩類事件依賴，即實線箭頭表示的依賴關(guān)系，但真實的時序依賴是相互交叉的，事件B可能與它之前的第一個或第二個甚至更前面的A有關(guān)，即b3不僅可能與a3有關(guān)，也可能與a2或a1有關(guān)。以上這些需求的變化都為事件時序依賴發(fā)現(xiàn)帶來了更多的問題和困難。

1 相關(guān)工作

來自不同領(lǐng)域的多樣化需求衍生了多種類型的事件依賴，一般根據(jù)處理的數(shù)據(jù)類型分為兩類。第一類是事務(wù)數(shù)據(jù)庫，其中每個事務(wù)是一系列事件的集合。每個事務(wù)通常記錄的是同一個實體的事件，例如銀行賬戶流水、顧客購物記錄。這種類型的時序依賴主要用于發(fā)現(xiàn)在某些事務(wù)中頻繁出現(xiàn)的子序列，關(guān)注不同個體之間相同的依賴模式。序列模式[8-9]、全依賴模式[10]、互依賴模式[11]、部分周期模式[12]是該類事件依賴中比較典型的模式依賴發(fā)現(xiàn)。

在實際應(yīng)用中因為某些條件限制，用戶無法獲得足夠的信息將事件數(shù)據(jù)劃分為事務(wù)，此時用戶面對的就是一系列事件。這就是第二類的時序依賴，也是本文重點關(guān)注的類型。其中，最基本的時序依賴是頻繁情節(jié)發(fā)現(xiàn)[6]。同一個情節(jié)中的事件發(fā)生在相近的時間區(qū)間內(nèi)，所以情節(jié)發(fā)現(xiàn)的一般方式都是采用用戶預(yù)定義時間窗口機制。通過滑動時間窗口將發(fā)生在同一個窗口中的事件視作一個事務(wù)，然后將從事務(wù)數(shù)據(jù)庫中發(fā)現(xiàn)頻繁子序列的思想應(yīng)用到頻繁情節(jié)發(fā)現(xiàn)中。傳統(tǒng)的情節(jié)發(fā)現(xiàn)只能揭示在一個預(yù)定義窗口內(nèi)頻繁發(fā)生的有序事件，情節(jié)內(nèi)事件之間發(fā)生的具體時間間隔是未知的。例如在大小為5的時間窗口中發(fā)現(xiàn)的情節(jié)〈A，B〉表示事件B會在事件A發(fā)生之后的4個單位時間內(nèi)發(fā)生，但不能準確提供具體的發(fā)生時刻。文獻[13]提出了固定間隔情節(jié)的概念，構(gòu)建了一種基于前綴樹的精確位置情節(jié)規(guī)則（Precise-Position Episode Rule trie， PER-trie）挖掘框架，用于獲得事件之間準確發(fā)生的時間間隔區(qū)間。

以上這些挖掘算法通常都需要用戶提前選定一個合適的時間窗口大小，這在實際應(yīng)用中是一件非常困難的事情，因為實際應(yīng)用中時序依賴發(fā)現(xiàn)的時間區(qū)間可能會從1秒到1天甚至更長不等，而不合適的時間窗口可能會導致一些超出窗口以外的依賴被忽視。文獻[14]算法不需要預(yù)先定義窗口，將空間統(tǒng)計學中的思想應(yīng)用到事件的時序依賴發(fā)現(xiàn)中，用空間點過程的距離度量計算事件發(fā)生的無條件分布和條件分布，將成對事件之間的依賴關(guān)系問題轉(zhuǎn)化為這兩個概率分布的比較，而事件之間的等待時間用一個卡方檢驗來計算。Tang等[7]考慮到時間間隔的隨機性，將交錯事件存在關(guān)聯(lián)的可能性納入依賴發(fā)現(xiàn)過程中，構(gòu)建了一個基于有序表的算法STScan （Sorted Table Scan），將成對事件之間可能存在的所有時間間隔都保存在鏈表中，通過掃描鏈表的子段得到所有的合格滯后區(qū)間。文獻[15]將時序依賴發(fā)現(xiàn)問題轉(zhuǎn)化為成對事件的時間間隔分布的學習，提出了一種基于期望最大化（Expectation Maximization， EM）的方法用于發(fā)現(xiàn)時序依賴中時滯的最大似然模型。Zller[16]基于迭代最近點（Iterative Closest Point， ICP）算法[17]思想構(gòu)建了迭代最近事件（Iterative Closest Event， ICE）算法尋找最合適的事件匹配集合滿足時滯分布波動性最小。

6 結(jié)語

本文針對事件數(shù)據(jù)中的時序依賴問題進行研究，提出了時滯情節(jié)發(fā)現(xiàn)這一概念，采用基于相鄰事件匹配集（AEM）的時滯情節(jié)發(fā)現(xiàn)算法，不需要預(yù)先定義時間窗口，通過時滯的概率統(tǒng)計模型發(fā)現(xiàn)成對并行和串行時滯情節(jié)。與算法ICE相比，基于AEM的時滯情節(jié)發(fā)現(xiàn)算法有效地提高了時滯模擬效果。但目前本文研究只關(guān)注了成對的時滯情節(jié)，三個及三個以上事件類型之間的時滯情節(jié)發(fā)現(xiàn)需要在事件序列匹配中構(gòu)建更加復雜的概率模型，這也是我們未來工作的重點研究方向，以便更好地將時滯情節(jié)發(fā)現(xiàn)應(yīng)用于實際生產(chǎn)中。

參考文獻：

[1] 李濤，劉崢，周綺鳳.應(yīng)用驅(qū)動的大數(shù)據(jù)挖掘[J].中興通訊技術(shù)，2016，22（2）：49-52. （LI T， LIU Z， ZHOU Q F. Application-driven big data mining[J]. ZTE Communications， 2016，22（2）：49-52.）

[2] WU C-W， LIN Y-F， YU P S， et al. Mining high utility episodes in complex event sequences [C]// Proceedings of the 2013 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2013： 536-544.

[3] 武健.時序Web數(shù)據(jù)挖掘方法[J].計算機應(yīng)用，2014，34（S2）：120-122. （WU J. Data mining method from time series Web data [J]. Journal of Computer Applications， 2014， 34（S2）： 120-122.）

[4] 郭跇秀，呂學強，李卓.基于突發(fā)詞聚類的微博突發(fā)事件檢測方法[J].計算機應(yīng)用，2014，34（2）：486-490. （GUO Y X， LYU X Q， LI Z. Bursty topics detection approach on Chinese microblog based on burst words clustering [J]. Journal of Computer Applications， 2014， 34（2）： 486-490.）

[5] AGRAWAL R， IMIELINSKI T， SWAMI A N. Mining association rules between sets of items in large databases [C]// Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1993： 207-216.

[6] MANNILA H， TOIVONEN H， VERKAMO A I. Discovery of frequent episodes in event sequences [J]. Data Mining & Knowledge Discovery， 1997， 1（3）：259-289.

[7] TANG L， LI T， SHWARTZ L. Discovering lag intervals for temporal dependencies [C]// Proceedings of the 2012 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2012： 633-641.

[8] AGRAWAL R， SRIKANT R. Mining sequential patterns [C]// Proceedings of the 1995 Eleventh International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 1995： 3-14.

[9] 李艷輝，劉浩，袁野，等.基于差分隱私的頻繁序列模式挖掘算法[J].計算機應(yīng)用，2017，37（2）：316-321. （LI Y H， LIU H， YUAN Y. Frequent sequence pattern mining with differential privacy[J]. Journal of Computer Applications， 2017， 37（2）： 316-321.）

[10] LIANG F， MA S， HELLERSTEIN J L. Discovering fully dependent patterns [C]// Proceedings of the 2002 SIAM International Conference on Data Mining. Philadelphia， PA： Society for Industrial and Applied Mathematics （SIAM）， 2002： 511-527.

[11] MA S， HELLERSTEIN J L. Mining mutually dependent patterns [C]// Proceedings of the 2001 IEEE International Conference on Data Mining. Washington， DC： IEEE Computer Society， 2001： 409-416.

[12] MA S， HELLERSTEIN J L. Mining partially periodic event patterns with unknown periods [C]//Proceedings of the 2001 17th International Conference on Data Engineering. Piscataway， NJ： IEEE， 2001：205-214.

[13] AO X， LUO P， WANG J， et al. Mining precise-positioning episode rules from event sequences [J]. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（3）： 530-543.

[14] LI T， MA S. Mining temporal patterns without predefined time windows [C]// Proceedings of the 4th IEEE International Conference on Data Mining. Washington， DC： IEEE Computer Society， 2004： 451-454.

[15] ZENG C， TANG L， LI T， et al. Mining temporal lag from fluctuating events for correlation and root cause analysis [C]// Proceedings of the 2014 10th International Conference on Network and Service Management. Washington， DC： IEEE Computer Society， 2014： 19-27.

[16] ZLLER M-A， BAUM M， HUBER M F. Framework for mining event correlations and time lags in large event sequences [C]// Proceedings of the IEEE 2017 15th International Conference of Industrial Informatics. Piscataway， NJ： IEEE， 2017： 3-4.

[17] BESL P J， McKAY N D. A method for registration of 3-D shapes [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002， 14（2）：239-256.

[18] GUO S， LIU Z， CHEN W， et al. Event extration from streaming system logs [C]// ICISA 2018Proceedings of the 9th International Conference on Information Science and Applications， LNEE 514. Singapore： Springer， 2018： 465-474.

[19] LI T， JIANG Y， ZENG C， et al. FLAP： an end-to-end event log analysis platform for system management [C]// Proceedings of the 2017 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2017： 1547-1556.

[20] FISCHLER M A， BOLLES R C. Random sample consensus： a paradigm for model fitting with applications to image analysis and automated cartography [J]. Readings in Computer Vision， 1987： 726-740.

[21] LI T， LIANG F， MA S， et al. An integrated framework on mining logs files for computing system management[C]// Proceedings of the 2005 Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2005： 776-781.