基於l*算法的業務流程增量挖掘方法
2023-05-20 01:52:56 1
基於l*算法的業務流程增量挖掘方法
【專利摘要】一種基於L*算法的業務流程增量挖掘方法，屬於業務流程挖掘領域。其目的是通過智能挖掘技術來實現增量日誌的挖掘，避免日誌增加後需要重新挖掘的情況。首先從業務活動軌跡中提取頻數較大的日誌序列，然後進行預處理；根據L*算法的查詢思想分析相鄰兩個活動間的序關係，建立行為輪廓，依據直接依賴關係構建初始模型；然後比較模型的適合度和適當度，驗證增量日誌序列的相鄰活動的序關係與初始模型的行為輪廓的一致性，判斷是否對初始模型作出調整，利用行為輪廓一致性度選擇較優的模型；直到所有增量日誌序列驗證完畢，得到最優業務流程模型。該挖掘方法不僅能夠避免增量日誌的重複操作，而且使得流程的行為符合行為一致性。
【專利說明】基於L*算法的業務流程增量挖掘方法【技術領域】
[0001]本發明涉及基於增量日誌的業務流程挖掘方法，它避免了以往挖掘方法對於新增加的日誌需要重新挖掘的不足，有效適用於從不斷增加的日誌序列中逐步確定一個滿足有效行為、經濟實用的流程模型，屬於業務流程挖掘領域。
【背景技術】
[0002]目前，很多大型企業的管理應用軟體，如企業資源計劃、工作流管理系統都會自動生成日誌，這些日誌是對實際操作流程的記錄。業務流程挖掘就是利用這些日誌數據，進行分析、重組，重現業務流程的真實過程，且較之與原始模型行為更有效，以達到提高運行效率的目的。
[0003]到目前為止，國內外已成功研究出了大量的過程挖掘算法，在一定程度上，它們代表了幾個不同的研究方向，如基於活動間的依賴圖的挖掘算法，該算法假設日誌中的活動是分離的，這樣便使得活動的發生有了前後順序，進而得到活動間的依賴關係；再如面向塊結構模型的挖掘算法，該算法把活動間的關係用四種塊結構(順序結構、並行結構、選擇結構和循環結構)來表示；再如基於Petri網模型的挖掘算法，該算法的代表算法是α算法等等。本發明則是另尋他法，受到L*算法中的查詢思想的啟發從而提出了基於L*算法的業務流程優化挖掘方法。
[0004]L*算法最早是由Angluin因為學習確定性的有限自動機(DFA)提供的，後經過Rivest和Schapire改進。L*算法本質是在字母表Σ上研究一種未知語言U，而字母表Σ是由能夠接受U的最小的DFA產生的。L*算法是一種查詢學習方法，主要包括兩種查詢:一是會員身份查詢，即對於字符串σ e Σ%是否有σ eu?二是等價查詢，即對於一個DFAC，是否有L(C) =U?為了學習這種未知語言U，L*會反饋答案「Yes/No」給這兩種查詢。如果反饋給等價查詢的是「No」，L*期待一個反例字符串σ使得σ e U-L(C)或者σ e L(C)-U，對於第一種情況σ應該添加`到L (C)，第二種情況應將σ從L(C)中移除。本發明借鑑L*算法中的查詢思想，將其運用到日誌序列中相鄰活動的行為輪廓關係的確定方法中。
【發明內容】
[0005]本發明為了豐富現有的挖掘方法，提出了一種基於L*算法的業務流程增量挖掘方法，採用L*算法查詢的基本思想，將日誌序列相繼活動間的關係與行為輪廓的兩種序關係(因為這裡考察的是日誌序列裡的兩個相繼活動，故不考慮排他序關係)進行查詢，建立行為輪廓，從而建立業務流程模型，然後優化選擇得到最優模型。另外，在日誌序列的提取問題上，為了避免同時操作大量日誌序列而產生的冗餘、錯誤等問題，本發明採用增量日誌的方法。
[0006]在挖掘過程中，首先，從程序運行產生的軌跡中提取頻數較大的日誌序列，將提取的日誌序列進行合併，避免出現重複操作，再將合併後的日誌序列按照頻數大小順序排列，即優先考慮頻數大的序列，以保證這些序列能被模型接受。其次，定義一個日誌弱序關係集合Σ =.(χ卜>，,_y卜xjf jcj，其中x, y是日誌序列中兩個相繼的活動，>代表它們之間
的弱序關係，定義序關係集合"={(-V卜.V, V Ψ A-H-V卜V, V卜x)j，集合U中依次是行為輪廓關
系中的嚴格序關係和交叉序關係；觀察日誌序列中每相鄰兩個活動，經過查詢確定是何種序關係。例如，一組日誌W= {AB⑶E，ABDCE，ADBCE}，在W中，字母表集合由所有的序關係組成，即
W -Σ ^ {Ay B, B> C,C y D,D y E,B y D,D y C,C > L 4 ^ D,D y B,B A,D )f- A,C ψ B,五★ C,五> D},根據U集合的定義，我們可知= p yB,B^ A),{A卜D,D ^ A),(β y C, C ? B\(CC).{DyE.E^ D\{ByD,Dy B\(C yD,Dy C)},故 /丨:W.Σ 丨 | 丨我
們可找到屬於嚴格序關係的有，(A, B), (A, D), (B，C)，(C, E)和(D，E)，屬於交叉序關係的有(B, D), (C, D),據此，構建Petri網模型作為初始模型。然後驗證增量日誌序列相鄰活動的序關係與初始模型的行為輪廓關係是否一致，若是，則繼續驗證剩餘增量日誌序列，若否，則做出調整再進行模型與模型間的一致性分析，然後繼續驗證。直到所有增量日誌驗證完畢，得到最優模型。
[0007]本發明的優點是採用了 L*算法中查詢的基本思想，且在查詢過程中加入了行為輪廓的概念，利用增量日誌來減少操作過程中可能會出現的問題(如堵塞、冗餘等)，在優化過程中沿用了行為輪廓一致性及模型間的行為輪廓一致性分析，這樣得出的模型比之原始模型更加合理得當。
【專利附圖】
【附圖說明】
[0008]圖1是本發明實施方式的結構示意圖。
[0009]圖2是本發明日誌序列處理的結構示意圖。
[0010]圖3是本發明基於L*算法的模型優化結構示意圖。
【具體實施方式】
[0011]以下結合附圖所述實施例對本發明作進一步的說明。
[0012]圖1為本發明的整個流程系統的主要部分的示意圖。如圖所示，整個系統是以提取日誌為開始，經過預處理，然後進行業務流程的挖掘。它主要包括三部分分別是日誌序列的處理、初始模型的建立和基於L*算法的業務流程優化挖掘算法。
[0013]圖2是本發明日誌序列處理的結構示意圖。如圖所示，首先，從程序運行產生的軌跡中提取頻數較大的日誌序列，將提取出的日誌序列進行預處理使之滿足兩個條件:一是沒有相同的日誌序列，可避免重複操作；二是日誌序列應按照頻數大小順序排列，以方便優先考慮頻數大的序列，以保證這些序列能被模型接受。
[0014]圖3是本發明基於L*算法的模型挖掘結構示意圖。如圖所示，從處理過的日誌序列開始，構建日誌序列相鄰活動間的弱序關係集合，根據行為輪廓序關係的定義，得出日誌序列相鄰活動的序關係集合，進而得到它們的行為輪廓，構建初始模型；然後不斷地從程序中提取增量日誌，驗證增量日誌序列的相鄰活動的序關係與初始模型的行為輪廓的一致性，作出判斷:是否需要調整初始模型，若是，則調整模型，進行模型與模型間的一致性分析，擇優，繼續驗證；若否，繼續驗證剩餘增量日誌序列。直到所有增量日誌序列驗證完畢，得到最優模型。附:
[0015]行為輪廓一致性度:設S1 = (P1, T1; F1, M1)和 S2 = (P2, T2; F2, M2)是兩個 Petri 網系統，他們關於~匹配，
【權利要求】
1.基於L*算法的業務流程增量挖掘方法，該方法由日誌序列的提取和處理及增量日誌的運用、初始模型的建立和基於L*算法業務流程的優化挖掘方法三部分組成，其特徵在於，提取和處理實現對日誌序列的規範化要求，即滿足能夠從日誌序列進行挖掘的條件；增量日誌的運用可有效地減少因同時操作大量日誌序列而產生的錯誤，提高運行效率；基於L*算法的業務流程的挖掘方法實現對處理過的日誌序列構造日誌弱序關係集合和日誌序列序關係集合，從而確定日誌序列中相繼活動的行為輪廓關係，依此構建流程模型，並依據增量日誌進行優化。
2.根據權利要求1所述的業務流程挖掘方法，其特徵在於:在分析日誌序列的活動時，採用L*算法中查詢的思想以及行為輪廓的概念，根據L*算法的查詢思想構建了各個相鄰活動間的行為輪廓關係。
3.根據權利要求1所述的業務流程挖掘方法，其特徵在於:在整個挖掘過程中，不再將所有的日誌序列全部同時提取出來，而是先提取一部分，其餘的以增量日誌的形式提取出來，用於挖掘算法的逐步優化過程中。
4.根據權利要求1所述的業務流程挖掘方法，其特徵在於:在優化挖掘過程中，不僅利用了日誌序列相鄰活動的序關係與模型的行為輪廓關係的一致性驗證，而且還利用了模型與模型的一致性分析，在評價模型與模型的一致性時，採用評價標準是行為輪廓一致性度。
【文檔編號】G06F11/34GK103778051SQ201410010776
【公開日】2014年5月7日 申請日期:2014年1月9日 優先權日:2014年1月9日
【發明者】方賢文, 吳俊枝, 劉璐, 殷志祥, 方新建 申請人:安徽理工大學