一種基于MDL的日志序列模式挖掘算法

杜詩晴，王 鵬，汪 衛

（1.復旦大學軟件學院，上海 201203；2.復旦大學計算機科學技術學院，上海 201203）

0 概述

日志數據記錄了互聯網系統運行時的狀態以及任務的開始與結束等重要事件，其易于獲取且含有豐富的信息，已經成為系統運維領域的重要數據源。系統運行產生的日志數據可被視作時序事件序列，利用序列模式挖掘技術可從時序事件序列中發現有意義的序列模式。挖掘得到的模式結果能夠有效幫助工程師理解系統行為，還可進一步用于異常檢測、故障診斷與原因分析等任務。

序列模式挖掘是數據挖掘領域中的重要研究課題之一，由AGRAWAL和SRIKANT［1］于1995年提出。傳統的序列模式挖掘算法致力于發現序列中頻繁出現的序列模式，但是該類算法生成的模式結果集數目眾多且信息冗余，不利于人工查看分析，因此從序列中挖掘出高質量低冗余的序列模式具有實際意義。為了減少模式結果的數目并降低模式結果冗余度，常用的方法是篩選出原始結果集中的部分模式作為最終結果返回，使得最終結果中的模式在充分代表原序列中典型行為模式的同時有效降低結果集數目。文本壓縮中廣泛使用的最小描述長度（Minimum Description Length，MDL）準則［2］是一種有效的篩選準則，該準則使得模式結果集中的復雜度和其代表序列的能力之間達到良好平衡。

目前，文獻［3-5］將MDL準則應用于序列模式挖掘，該類算法的基本思路是通過設計編碼方案，采用一組模式集合作為字典對原始序列進行編碼。由于編碼后所需的描述長度更少，因此該過程可視作對原始序列信息的壓縮。通過尋找具有最佳壓縮能力的集合作為結果返回，即可得到信息緊湊的模式結果。利用MDL準則篩選出的模式集合能夠最大程度地壓縮原始序列中的信息，因此該集合可以有效代表整個序列。然而，目前尚未有研究充分考慮時序序列中存在的時間規律性。日志數據記錄的是系統運行過程中重復產生的行為，系統日志中事件與事件之間通常存在顯著的時間規律性。相對于普通的序列模式而言，對相鄰事件之間的時間關系進行總結的模式能夠有效指示系統的運行狀態，這說明發現具有時間規律的模式具有一定的實際意義和應用價值。

本文提出一種從時序日志序列中挖掘序列模式（Discovering sequential patterns from Temporal log Sequences，DTS）的算法，通過挖掘序列中能充分代表事件關系和時序關系的模式，有效增強模式結果集的表達能力?；贛DL準則設計一種編碼方案，該方案以序列模式結果為字典集，在信息無損的前提下對原始時序序列進行編碼，并通過計算編碼前后的描述長度來衡量不同序列模式的有效性，從而發現高質量的序列模式結果集。

1 相關工作

國內外有許多關于日志分析領域的研究工作，如文獻［6］提出DeepLog算法，該算法將原始日志文本轉換為事件序列，并利用日志序列對系統進行異常檢測和原因分析。文獻［7］提出CloudSeer算法，以日志序列為輸入數據，并對系統運行時的工作流進行建模。文獻［8］提出一種基于歸一化特征判別的日志模板挖掘算法，將原始日志文本解析成不同的事件類型。文獻［9］利用層次聚類算法挖掘頻繁日志事件序列，并以此為基礎對不同類型的故障進行預測?，F有工作主要集中在通過日志分析進行自動化系統維護和故障分析［10］。本文旨在從原始日志序列中發現有意義的序列模式，且發現的模式可以用作在線監控和異常檢測等任務。

序列模式挖掘問題作為數據挖掘領域廣泛研究的重要課題之一，其具有很高的研究熱度。傳統的序列模式挖掘算法例如PrefixSpan算法［11］的生成模式結果集數目眾多且信息冗余。為解決該問題，用于衡量模式結果質量的不同模式語義被提出，例如閉頻繁模式集［12］、最大頻繁模式集［13］、高效用模式集［14］以及top-k模式集［15］等。然而，上述算法挖掘得到的模式結果集依舊存在高度冗余。

為進一步降低結果集冗余度，Krimp算法［16］將MDL準則應用于模式挖掘，并以此為評價標準篩選出最能代表原始數據的模式結果集合。GoKrimp算法［4］進一步將MDL準則應用拓展到序列模式挖掘領域，后續的SQS算法［3］和CSC算法［5］均沿用了該思路?，F有基于MDL準則的序列模式挖掘算法可以分為兩類。GoKrimp算法［4］和SQS算法［3］僅考慮了事件與事件之間的關系，通過對長時間間隔懲罰的方式，選擇事件間隔盡可能小的模式，得到的模式依舊存在一定的冗余且不能正確反映序列信息。CSC算法［5］將一條序列模式中相鄰事件之間的事件間隔限制為固定長度，并且不允許同一條模式中出現兩個同一類型的事件，極大地限制了模式的表達能力，且對于同一條序列需要更多的序列模式來表示。上述算法均未充分考慮處理時序序列中存在的時間規律性，相比之下，DTS利用模式中的事件關系以及相鄰事件之間的時間規律性來獲得更好的模式，并且能夠發現冗余度較低的模式集合。

2 問題描述

2.1 相關定義

定義1（時序日志序列）一條時序日志序列是由n條具有時間戳的日志構成的有序序列Slog={(log1，t1)，(log2，t2)，…，(logn，tn)}，其中ti≤ti+1(1≤i≤n)。序列的時間跨度為Δ(S)=tn-t1。時間戳的粒度可以按需設置為不同級別。

由于原始日志信息的形式為無結構文本，日志分析工作的一個常用預處理步驟是將無結構的日志文本解析為結構化的表示形式［17］。由同一條日志輸出語句生成的日志信息具有高度相似的結構，反之亦然。基于此觀察，一條原始日志文本可以被解析為事件類型和參數兩個部分信息。其中，事件類型對應日志輸出語句的文本常量部分，參數對應日志輸出語句中變量部分的取值。由于Drain算法［18］與現有同類算法相比具有優異的性能，因此本文使用該算法解析原始日志序列。一條日志信息logi可以被解析為[ei，para1，para2，…，parap]的結構化形式，其中，ei表示事件類型，paraj表示logi中的第j個參數值。由于本文的后續工作不涉及參數部分的信息，后續中僅用相應的事件類型ei表示一條日志。

定義2（事件類型集合）事件類型集合Σ={E1，E2，…，El}為日志序列Slog中出現的所有事件類型的集合。

定義3（解析后時序日志序列）通過對原始時序日志序列中的日志文本進行解析，得到解析后的時序日志序列S={(e1，t1)，(e2，t2)，…，(en，tn)}。

本文后續的模式挖掘工作以解析后的時序日志序列為輸入數據。序列模式的相關定義如下：

定義4（序列模式）一條序列模式Pi是由事件類型構成的偏序序列＜E1，E2，…，Em＞，Ej∈Σ(1≤j≤m)。其中，Ei出現在Ej之前(1≤i＜j≤m)，模式長度為m。

定義6（支持度）模式Pi的支持度suppi為所有非重疊的實例數目。如果2個實例之間不共享同一事件實例，則它們被認為是非重疊的。本文要求不同模式的實例之間也是非重疊的。

定義8（單事件序列模式）單事件序列模式Pi為只包含一個事件類型的特殊序列模式，Pi=＜Ei＞，且長度為1。單事件序列模式不包含直方圖信息。

2.2 問題定義

給定一條解析后時序日志序列S，本文目標是發現一組序列模式，這些模式能以最佳的形式無損壓縮原序列中的事件關系以及時間規律性。本文使用MDL準則作為衡量數據壓縮質量和結果復雜性之間平衡的指標。

MDL準則的基本思想為：給定模型集合M，對于序列S而言，模型M∈M能使描述長度L(S，M)=L(M)+L(S|M)最小，其中L(M)為M所需的描述長度，L(S|M)為編碼后的S所需的描述長度，描述長度按位級別計算。

對于本文的目標問題而言，模型M為序列模式Pi構成的集合P。確定好如何利用P中的模式對序列S進行編碼的方案后，可以通過計算編碼前后描述長度的變化來衡量模式質量。本文的問題可以形式化定義為：給定時序日志序列S，尋找模式集合P，使得描述長度L(S，P)=L(P)+L(S|P)最小。

3 編碼方案

本節給出具體的編碼方案和描述長度的計算方法。由于對序列編碼是本文評價模式質量的手段而非目標，因此DTS更關注于編碼后的描述長度而非具體的編碼結果。

3.1 模式集合編碼

根據MDL準則，需要計算模型編碼后的描述長度L(P)，計算方法如下所示：

下文介紹單條模式的描述長度L（P）i的計算過程。如表1所示，模式集合P中存儲了用于編碼的序列模式的內容，包括模式、支持度、模式編碼、描述相鄰事件之間時間間隔分布的直方圖和對應的編碼。

表1 模式集合的描述Table 1 Description of the set of patterns

以表1中的模式P1=＜ABC＞為例，該模式的支持度為20，模式編碼為C(P1)。P1使用了兩個直方圖分布描述事件A和事件B以及事件B和事件C之間的時間間隔分布。其中，事件A和事件B的時間間隔有兩種取值，分別為2和5，兩個非空桶的編碼分別為

對于每個模式Pi，需要對其內容序列和描述相鄰事件之間時間間隔分布的直方圖分別編碼。使用編碼（Code）替換模式在序列S中的實例，即可得到編碼后的序列。盡管S中的大部分事件會被一條模式所覆蓋，最終編碼后的序列中可能依舊保留一些孤立事件，這些事件不屬于任何模式的實例。本文用長度為1的單事件序列模式＜Ei＞對這些孤立事件進行編碼，Ei為孤立事件的事件類型。

對單條模式Pi而言，描述長度L(Pi)的計算如下：描述一個事件類型需要lb|Σ|位比特，因此長度為m的模式需要m×lb|Σ|位比特描述序列內容。本文使用全局唯一碼來描述每個模式。考慮到出現更頻繁的模式應當消耗更短的描述長度，因此二進制形式的模式編碼的長度由模式頻率fi決定，其中，F為所有模式支持度之和本文使用最佳前綴碼，因此編碼長度|C(Pi)|=-lbfi。

對一條序列進行編碼所需描述長度L(Pi)計算方法如下：

假設表1中模式集合描述的序列包含事件類型數目為|Σ|=100的序列，則表1中模式P1=＜ABC＞的描述長度如下所示：

3.2 序列編碼

圖1 時序事件序列編碼結果Fig.1 Encoding result of a temporal event sequence

使用模式集合P對序列S編碼所需的描述長度L(S|P)計算方法如下：

4 序列模式挖掘算法

文獻［4］證明了基于MDL準則從序列S中挖掘最優模式集合P為NP問題。因此，本文設計一種啟發式算法DTS迭代地從序列中發現模式。

假定序列S最初僅用單事件模式編碼，模式集合P初始狀態下為空，DTS迭代地更新P。本文涉及到的更新操作有兩種：添加操作和改進操作，且分別定義如下：

定義9（添加操作）將從序列中新發現的候選模式P添加到集合P中，更新后的模式集合為P ∪P。

定義10（改進操作）給定集合P中的某條序列模式P=＜E1，E2，…，Em＞，通過在位置j添加事件類型為E′的事件實例，對集合OP中部分實例改進，生成長度為m+1的新模式Pr，事件E′稱為改進事件。新模式Pr=P⊕E′有如下3種情況：

1）j=0，Pr=＜E′，E1，E2，…，Em＞。

2）j∈[1，2，…，m-1]，Pr=＜E1，E2，…，Ei，E′，Ei+1，Ei+2，…，Em＞。

3）j=m，Pr=＜E1，E2，…，Em，E′＞。

若OP中所有實例均被改進，稱作完全改進，更新后的集合為{P ?P}∪{Pr}，否則，稱作部分改進，Pm為原模式，更新后的模式集合為{P ?P}∪{Pm，Pr}。

一種常見的情況是候選模式P覆蓋的某些事件，亦是集合P中某條模式P′的改進事件，即出現了事件沖突。每輪迭代中決策更新操作時，若不存在事件沖突，可以直接采用添加操作將當前最佳候選模式更新到集合P中。在出現事件沖突的情況下，考慮到本文定義的編碼方案要求不同模式之間是非重疊的，即同一條事件實例不能被多個模式所覆蓋，DTS需要選擇更優的更新操作，即能夠使得描述長度L(P)+L(S|P)減少更多的更新操作。每次對集合P更新后，DTS對S中為新模式所覆蓋的事件實例進行編碼。DTS對集合P迭代更新，直到沒有更新操作能夠使得描述長度進一步減少為止。DTS維護了兩個數據結構來分別支持添加和改進這兩個更新操作，即候選模式集和候選改進表。下面詳細介紹這兩個數據結構和算法流程。

4.1 候選模式集

對于添加操作，被添加到P中的模式應當能夠最大限度地優化描述長度。一個直觀的思路是通過窮舉當前序列中所有模式來選擇最佳的候選模式，然而在指數級空間中搜索的復雜度很高。因此，在算法迭代過程中，候選模式集CP中僅存儲當前有潛力被添加到集合P的候選模式。候選模式P對描述長度優化能力的評價函數如式（6）所示，且gain(P)值越大，模式P的優化能力越強。

候選模式集CP的初始化計算如算法1所示，初始狀態下CP為不包含任何模式的空集。對于序列S中的每個事件類型E∈Σ，創建一個以E開頭的模式P，對該序列模式以深度優先的方式調用程序BestGrowth，計算以當前事件類型為開頭能生成的最佳序列模式。若最佳序列模式能進一步優化描述長度，將該模式加入候選模式集，即候選模式集CP貪心地存儲了以每種事件類型為開頭，并將能生成具有最佳優化能力的模式作為候選模式。

算法1候選模式集初始化Initialize CP

子程序BestGrowth嘗試將模式P擴展到長度為|P|+1且具有更好優化能力的新模式中，具體過程為：嘗試使用每個事件類型對當前模式擴展，得到新模式P′←P?E′。依次計算序列S中P′的最左實例并存入直到S中不存在P′的最左實例為止。其中，最左實例為序列中最早出現的實例，例如圖1中(a，0)(b，2)(c，5)即為模式＜ABC＞的一個最左實例。根據編碼方案計算gain(P′)，選取其中描述長度降低最多的模式作為最佳擴展結果返回。若本次調用BestGrowth沒有找到新擴展模式，程序返回null。

4.2 候選改進表

對于改進操作，DTS維護了一個候選改進表CR并用于存儲模式集合P中所有模式P所有位置上的最佳改進。一個模式P在位置j處的改進可以格式化地存儲為結構［改進位置j，改進事件E′，原模式Pm，改進模式Pr］。例如[1，F，DD，DFD]存儲的是模式DD在位置1處部分改進得到的模式DFD，原模式DD依舊保留部分實例。若DD被完全改進，結果為[1，F，null，DFD]。候選改進表中的改進結構以改進事件類型為索引，即同一改進事件類型關聯的改進結構聚集為一組。

每次由添加操作或改進操作新生成的模式P存入模式集合P后，需要對P計算其每個位置上可能的改進。對模式P計算改進操作的流程如算法2所示，對模式P的每個位置j調用程序Refine計算該位置上能生成的最佳改進，即最能減少編碼后描述長度的改進。若位置j上存在最佳改進，將最佳改進存入候選改進表，改進操作對描述長度優化能力的評價函數如式（7）所示，且值越大，則改進的優化能力越強。

算法2對模式P計算改進ComputeRefining

給定待改進模式P，改進位置j，改進事件E，子程序Refine計算是否能使用事件E在位置j處對模式P改進，具體過程為：首先根據改進操作的定義創建新模式Pr，對實例集合OP中的每個實例，計算該實例能否被事件E的實例按照定義進行改進，此處依舊遵循最左原則。若存在改進，將改進后的實例結果存入模式Pr的實例集合。若不為空，說明存在有效改進，OP中未被改進的實例OP?Oused對應原模式剩余的實例，用Pm表示原模式，返回改進結果為[j，E，Pm，Pr]。圖2展示了調用程序Refine(P，S，2，E)對模式計算改進的過程，使用事件對P的前兩個實例在位置2處改進得到模式Pr的實例集合，而第三個實例找不到滿足時序關系的改進事件實例e，因此保留為原模式Pm的實例。

圖2 Refine程序計算示例Fig.2 Example of the computation of Refine program

4.3 序列模式挖掘

DTS基于啟發式的思路迭代地從序列中挖掘模式，算法描述如算法3所示。首先對算法涉及的數據結構初始化（第1行～第2行），模式集合P初始狀態下為空，S僅用單事件序列模式編碼。調用程序InitializeCP初始化候選模式集CP，由于集合P中尚未存入新模式，則候選改進表CR初始狀態下為空。

算法3序列模式挖掘算法DTS

如前文所述，DTS對P的迭代更新是由候選模式主導的。在出現事件沖突的情況下，DTS選擇能夠使得描述長度減少更多的操作，比較模式P和改進對描述長度優化能力的函數為：

由于長模式或支持度較高的模式往往對描述長度有更多的優化，而改進操作的優化僅由單個事件貢獻，為了保證比較的公平性，此處比較的是單個事件的優化能力。函數返回值為正則表明模式P有更好的優化能力。

在開始迭代過程之前，從候選模式集CP中獲取當前最佳候選模式P，由于候選改進表CR為空，不存在事件沖突，直接將P存入集合P。由于加入了新模式，調用程序ComputeRefining計算其相應的改進并存入CR。在接下來的算法迭代過程中（第6行～15行），DTS首先從CP中獲取最佳候選模式P*，若沒有新的候選模式，迭代流程終止（第8行）。檢測CR中是否存在與P*事件沖突的改進，即模式P*中的事件是其他模式的改進事件，并獲取優化能力最佳的改進對集合P的更新采用添加操作還是改進操作取決于cmp函數的比較結果。

以圖3為例說明算法核心思想，圖3（a）所示為當前待更新的模式集合P以及當前迭代輪次的候選模式集CP和候選改進表CR。若當前CP中的最佳候選模式P*為P1=＜EF＞，相應的CR中兩個改進對P1存在事件沖突，其中=[1，F，DD，DFD]具有最佳的優化能力。調用函數cmp對二者的優化能力進行比較，若優化能力更強，模式集合P被改進操作更新為P′，更新后的模式集合如圖3（b）所示。否則，將P1存入P，模式集合P被添加操作更新為P″，更新后的模式集合如圖3（c）所示。每輪更新P后，需要及時對數據結構候選模式集CP以及候選改進表CR中的內容更新，刪除已經失效的模式和改進結構，并重新計算新的候選模式和改進結構。DTS對模式集合P的迭代更新在無法產生新候選模式后終止，隨后僅用改進操作更新P直到CR=?。

圖3 模式集合的更新示例Fig.3 Update example of pattern collection

5 實驗與結果分析

5.1 實驗環境

本文所有實驗在單機環境下運行，處理器為Intel?CoreTMi7-3770 CPU@ 3.40 GHz，內存為24 GB，操作系統為64位Windows 10。

5.2 實驗數據

本文采用真實Hadoop分布式文件系統（Hadoop Distributed File System，HDFS）環境運行生成的日志序列作為輸入數據，共生成8條不同長度的日志序列，其中4條日志序列是HDFS系統的NameNode生成的，包含200種事件類型，4條日志序列是HDFS系統的DataNode生成的，包含106種事件類型。這兩種日志數據有不同的特點，其中NameNode日志包含更豐富的事件類型和更復雜的系統行為，因此模式更為復雜，而DataNode日志包含相對更少的事件類型，其中的模式也相對更為簡單規律。

5.3 算法對比分析

實驗對DTS與SQS［3］、GoKrimp［4］、CSC［5］、ISM［19］算法進行對比分析。其中，文獻［3-5］都是基于MDL準則挖掘模式，ISM算法是一個基于概率的機器學習方法。對于CSC和DTS，輸入數據即為整條序列，對于其他3種算法，將序列切分為長度為10的子序列作為輸入數據。DTS由Java實現，其余算法的源代碼由作者提供。

5.3.1 運行效率的評估

本節使用不同長度的日志數據對算法的效率和可擴展性進行評估，5種算法所需運行時間如圖4所示。值得指出的是，盡管5種算法的結果呈現在一張圖內，CSC、GoKrimp和DTS算法的時間單位為秒，SQS和ISM的時間單位為分鐘，為了節省空間，本文將不同數量級的運行時間展示在同一張圖片內。從圖4可以看出，DTS略慢于CSC和GoKrimp，這是因為CSC和GoKrimp在計算過程中通過設定間隔閾值的方式減枝，極大地減少了搜索空間，但后續實驗證明這也限制了模式的表達能力。盡管DTS相對來說耗時較長，但也只需400 s即可處理長度為600 000的復雜日志序列，這是一個可以接受的耗時時間，說明DTS可以高效發現模式且有很好的可擴展性。相比之下，SQS和ISM算法效率不高，處理日志所需耗時從幾十分鐘到幾小時不等，難以滿足日常應用需求。

圖4 不同數據集下的運行時間對比Fig.4 Comparison of processing time under different datasets

5.3.2 模式表達能力的評估

本節使用不同長度的日志序列對模式結果的表達能力進行評估，使用到的評估指標為壓縮率（Compression Ratio，CR）。基于MDL準則篩選模式挖掘出的模式結果可以用于對序列編碼，與原序列所需描述長度相比，編碼后的序列長度大幅減少。根據MDL準則描述長度越小，用于編碼的模式集合表達能力越強。壓縮率的計算為只使用單事件序列模式對序列編碼所需描述長度和使用模式集合對序列編碼所需描述長度的比值。

實驗所涉及的基于MDL準則算法的壓縮率如圖5所示。從圖5可以看出：對于NameNode日志，DTS在所有長度的日志序列上均取得了最高的壓縮率。在對比算法中，SQS的壓縮率最好，CSC和GoKrimp相對更差，如前所述，這兩種算法的減枝和貪心策略使得它們不能很好地處理復雜的日志序列；對于DataNode日志，所有算法的壓縮率都較低，這是因為該日志中的模式更為簡短。DTS在部分序列上仍然擁有最高的壓縮率，僅在兩條序列上略遜于CSC，這與前文的分析一致，CSC更適合處理模式相對簡短的序列數據，但是后續實驗分析可以看出CSC結果的冗余度很高。DTS在大部分數據上取得了最好的壓縮率，這表明DTS挖掘出的模式能更好地代表原序列。

圖5 不同數據集下的壓縮率對比Fig.5 Comparison of compression ratio under different datasets

5.3.3 模式冗余度的評估

DTS挖掘出的模式集合能更好地對序列進行壓縮，這并不意味著DTS的模式集合有很高的冗余度，本節對該結論加以實驗驗證。本文采用的評估指標如下：

1）平均序列間編輯距離（Average inter-sequence Edit Distance，AED）［19］：用于評估模式與模式之間的文本相似度，計算方式為對模式集合CP中所有模式P與CP中其他模式P′之間編輯距離的最小值求平均值，且AED越高，模式集合冗余度越低。

2）平均序列間杰卡德距離（Average intersequence Jaccard Distance，AJD）：用于評估模式與模式之間的杰卡德相似度，計算方式與AED類似。

3）事件覆蓋率（Event Coverge，EC）［20］：用于評估模式集合對事件類型的覆蓋率，且EC越高，說明模式集合涵蓋的事件類型越豐富。

表2展示了5種算法在不同數據集下的3種評估指標結果。其中，最優結果加粗表示。由于空間限制，此處僅列出兩個最長序列的結果。從表2可以看出：DTS具有最大的AED和AJD；與其他算法相比，DTS發現的模式具有最低冗余度；此外，DTS在事件覆蓋率方面也優于其他算法，這表明DTS挖掘出的模式結果在高質量的同時且低冗余，這對于人工分析和處理是非常便利的。

表2 5種算法在不同數據集下的模式冗余度對比Table 2 Comparison of pattern redundancy of five algorithms under different datasets

6 結束語

為從時序日志序列中發現高質量的序列模式，本文提出一種基于MDL的序列模式挖掘算法DTS。DTS能夠以黑盒的方式處理日志數據，在不需要任何先驗系統知識的情況下，從日志序列中發現有意義的行為序列用于日志分析。該算法結合系統行為在執行時間上存在一定規律性的特點，設計一種考慮事件關系以及時間規律性的編碼方案，以編碼前后描述長度的變化為衡量標準來評估序列模式質量，并從數據中迭代挖掘出可有效代表序列的模式。實驗結果表明，DTS可以有效發現高質量且低冗余的模式結果集。下一步將對算法搜索策略進行改進，以有效減少計算開銷，提高算法效率。