張書涵 費超群 黃錫昆* 李陽陽

(*中國科學院計算技術(shù)研究所智能信息處理重點實驗室 北京100190)

(**中國科學院數(shù)學與系統(tǒng)科學研究院管理、決策與信息系統(tǒng)重點實驗室 北京100190)

(***中國科學院大學 北京100049)

0 引言

工作流網(wǎng)頻繁子網(wǎng)挖掘是指以工作流網(wǎng)為輸入,分析工作流網(wǎng)中頻繁出現(xiàn)的子結(jié)構(gòu)(子模式),發(fā)現(xiàn)數(shù)據(jù)的內(nèi)在規(guī)律,使其能夠為工業(yè)上了解、優(yōu)化、應用數(shù)據(jù)提供重要信息的一類問題[1]。隨著網(wǎng)絡技術(shù)飛速發(fā)展,工作流網(wǎng)已經(jīng)成為刻畫業(yè)務執(zhí)行邏輯的主要形式[2],被廣泛用于網(wǎng)絡交易系統(tǒng)、業(yè)務流程管理等應用場景的建模和分析中[3]。

當前工作流網(wǎng)頻繁子網(wǎng)挖掘研究在新型應用場景下面臨著諸多挑戰(zhàn)。例如,在業(yè)務流程管理領(lǐng)域,存在大量重復出現(xiàn)、高度可重用的子流程[4],尤其是近年來,在跨組織工作流網(wǎng)挖掘的場景下存在許多子網(wǎng)變體[5]。變體的存在使得工作流網(wǎng)頻繁子網(wǎng)變得多種多樣、紛繁復雜,缺乏通用性。

按照輸入數(shù)據(jù)類型進行劃分,工作流網(wǎng)頻繁子網(wǎng)挖掘相關(guān)研究分為兩大主流方向。其一,從一維的日志進程序列中實施進程挖掘,構(gòu)造出工作流網(wǎng)及其子網(wǎng)[6-7]。如何更高效地從日志中抽取、發(fā)現(xiàn)工作流網(wǎng)及其子網(wǎng),是當前研究的熱點問題[8-13]。另外,從二維的工作流網(wǎng)中挖掘其頻繁的子網(wǎng)結(jié)構(gòu)[1,14]。相關(guān)工作大多采用頻繁模式挖掘(frequent pattern mining,FPM)相關(guān)方法進行求解。由于工作流網(wǎng)中大量存在的選擇、循環(huán)、并發(fā)等復雜模式及其特殊的語義約束,在工作流網(wǎng)上進行頻繁子網(wǎng)挖掘比傳統(tǒng)的FPM 問題更加復雜[15]。

本文基于頻繁模式挖掘的相關(guān)方法,總結(jié)了目前工作流網(wǎng)頻繁子網(wǎng)挖掘所取得的研究成果。詳細分析了將傳統(tǒng)FPM 用于工作流網(wǎng)頻繁子網(wǎng)挖掘存在的問題及挑戰(zhàn),分析了基于工作流網(wǎng)進行頻繁子網(wǎng)挖掘與基于一般圖進行頻繁子圖挖掘的本質(zhì)區(qū)別。本文的主要貢獻包括以下幾個方面。

(1) 針對輸入是一維日志序列的情形,研究方法分為基于過程式模式檢測、基于日志轉(zhuǎn)換和基于聲明式規(guī)則檢測3 類方法,本文給出了各代表性方法,總結(jié)了優(yōu)缺點。

(2) 針對輸入輸出均是二維工作流網(wǎng)的情形,研究方法分為基于工作流網(wǎng)轉(zhuǎn)換、基于序列與網(wǎng)混合式兩類方法,本文給出了各代表性方法,總結(jié)了優(yōu)缺點。

(3) 從理論上分析了傳統(tǒng)頻繁模式挖掘方法在工作流網(wǎng)頻繁子網(wǎng)挖掘問題中的不適用情況及其根本原因,總結(jié)了工作流網(wǎng)頻繁子網(wǎng)挖掘與頻繁子圖挖掘的本質(zhì)區(qū)別。

本文剩余部分組織結(jié)構(gòu)如下。第1 節(jié)簡要介紹相關(guān)的頻繁模式挖掘方法;第2 節(jié)給出工作流網(wǎng)頻繁子網(wǎng)挖掘相關(guān)研究的兩大主流方向,包括基于一維日志進程構(gòu)造工作流網(wǎng)及其子網(wǎng)的研究方法和基于工作流網(wǎng)的頻繁子網(wǎng)挖掘研究方法;第3 節(jié)分析將傳統(tǒng)FPM 用于工作流網(wǎng)頻繁子網(wǎng)挖掘存在的問題及挑戰(zhàn);第4 節(jié)列舉分析了工作流網(wǎng)頻繁子網(wǎng)挖掘中的幾種典型應用;第5 節(jié)總結(jié)了工作流網(wǎng)頻繁子網(wǎng)挖掘技術(shù)的發(fā)展趨勢及存在的挑戰(zhàn)。

1 頻繁模式挖掘

為了具體闡述工作流網(wǎng)頻繁子網(wǎng)挖掘相關(guān)研究方向的分類,本節(jié)針對其使用的傳統(tǒng)頻繁模式挖掘方法進行梳理,詳見圖1。頻繁模式挖掘是數(shù)據(jù)挖掘中重要的研究問題,從最初的分析顧客購買記錄到近幾年用于進程挖掘,FPM 一直有著十分廣泛的應用[8,10,16-19]。依據(jù)不同的數(shù)據(jù)類型,相關(guān)方法分為頻繁項挖掘、序列模式挖掘和頻繁子圖挖掘。

圖1 工作流網(wǎng)頻繁子網(wǎng)挖掘研究方向分類

1.1 頻繁項挖掘

頻繁項挖掘(frequent itemset mining,FIM)問題提出之初旨在分析購物車中經(jīng)常被一起購買的物品,得到顧客的購買習慣,為商店提供決策服務[20]。FIM 問題的首個解決算法是Apriori 算法[21],其核心在于向下反單調(diào)性的保障,即如果一個項集不頻繁,那么它的超集必定不頻繁;反之,如果一個項集是頻繁的,那么它的子集必定是頻繁的。該性質(zhì)可用偏序?表示,即給定任意模式p1及p2,如果p1?p2且p2為頻繁的,則p1也是頻繁的。向下反單調(diào)性是指導FPM 及工作流網(wǎng)頻繁子網(wǎng)挖掘的關(guān)鍵理論支撐。利用該性質(zhì),可以大大減小搜索空間。作為FPM 最經(jīng)典的算法框架,Apriori 具有良好的可擴展性。近年來,高性能計算、硬件加速等新技術(shù)被融合至Apriori算法。目前,已有數(shù)百個后續(xù)改進工作[22-28]。

1.2 序列模式挖掘

序列數(shù)據(jù)庫由有序元素或事件組成,典型的序列數(shù)據(jù)包括顧客購物序列、DNA 序列、時間序列等[16,29-36]。隨著數(shù)據(jù)類型的多樣化,序列模式挖掘(sequential pattern mining,SPM)算法處理的對象也越來越復雜。首個處理SPM 問題的算法為廣義序列模式(generalized sequential pattern,GSP)挖掘算法[16]。GSP 遵循逐層遍歷的方式,但候選集的生成十分耗時。參考FP-Growth 算法[37]提出的模式增長計算方式,Jian 等人[38]提出了PrefixSpan 算法,以深度優(yōu)先遍歷的方法計算候選子序列的支持度。此外,PrefixSpan 利用向下反單調(diào)性提出了一種有效的剪枝策略,減小搜索空間。隨著序列數(shù)據(jù)維度及類型的復雜化,許多約束被融合到SPM 問題的解決算法中。例如,Pex-Spam 算法使用的時間間隔約束[39],MaxSP 算法使用的長度約束[40]等。

1.3 頻繁子圖挖掘

作為數(shù)據(jù)結(jié)構(gòu)中最為復雜的一種,圖結(jié)構(gòu)廣泛應用于生物數(shù)據(jù)分析、社交網(wǎng)絡分析等實際問題的數(shù)據(jù)建模中[41-45]。Cook 和Holder[46]提出頻繁子圖挖掘(frequent subgraph mining,FSM)問題,旨在從給定的圖集中抽取出頻次大于一定閾值的子圖。

首個解決FSM 問題的算法是基于Apriori 的圖挖掘(Apriori-based graph mining,AGM)算法[47],采取逐層兩兩連接的方式。如圖2(a)所示,大小為k的所有頻繁子圖連接生成大小為(k +1) 的候選子圖,利用向下反單調(diào)性刪除候選子圖中的非頻繁子圖。AGM 類方法代表性的工作包括AGM/AcGM 算法[47]、FSG 算法[48]、Path-Join 算法[49]等,但不足之處是生成大量的候選集,需要耗費大量的內(nèi)存。

基于以上不足,基于模式擴充的方法特點是在k級頻繁子圖p的基礎(chǔ)上,每次擴展一條邊,生成p的超圖模式,然后計算支持度得到(k +1) 級頻繁子圖。從每個(k +1) 級頻繁子圖開始繼續(xù)擴展,直到無法再擴展為止。此方法是一種全內(nèi)存的計算,工作機制如圖2(b)所示,代表工作包括gSpan算法[44]、GASTON 算法[50]、SPIN 算法[51]等。

圖2 頻繁子圖挖掘兩種主要方法

2 工作流網(wǎng)頻繁子網(wǎng)挖掘

按照輸入數(shù)據(jù)類型進行劃分,工作流網(wǎng)頻繁子網(wǎng)挖掘相關(guān)研究分為兩大主流方向。其一,從一維的日志進程序列中實施進程挖掘,構(gòu)造出工作流網(wǎng)及其子網(wǎng)[6,7]。另外,從二維的工作流網(wǎng)中挖掘其頻繁的子網(wǎng)結(jié)構(gòu)[1,14]。

2.1 基于一維日志進程構(gòu)造工作流網(wǎng)及其子網(wǎng)

進程挖掘在文獻[52]中被提出,IBM 艾曼登研究中心將進程發(fā)現(xiàn)思想引入業(yè)務過程管理中[53]。進程挖掘旨在以大規(guī)模日志為原始輸入,從中抽取系統(tǒng)運行過程,通常以工作流網(wǎng)的形式呈現(xiàn)。隨著業(yè)務流程管理系統(tǒng)的興起,日志信息日益豐富,進程挖掘方法的重要性逐步提升[6,7,54-56]。當前,進程挖掘任務分為3 種類型,即進程發(fā)現(xiàn)、一致性檢測和模型增強,如圖1 所示。而每種任務要解決的核心問題是確保模型能夠“重演”。進程發(fā)現(xiàn)問題主要采用基于規(guī)則匹配的方法[55]進行求解。一致性檢測問題主要采用分解日志的方法進行對齊計算[57]。模型增強問題關(guān)注日志中時間、資源等組織信息的提取。

由于進程挖掘和序列模式挖掘具備問題的相似性,已有許多SPM 方法被用于進程挖掘中[8-11,58-62]。

目前,日志中包含的關(guān)系可分為兩類:

(1)控制流依賴關(guān)系,即日志中包含的所有活動都遵循一定的次序,例如直接依賴、選擇、并發(fā)關(guān)系。

(2)聲明式約束,即日志中的活動可用時態(tài)邏輯描述,如發(fā)生的情況最終一定會發(fā)生。

根據(jù)日志關(guān)系類型劃分,基于進程挖掘構(gòu)造工作流網(wǎng)及其子網(wǎng)的研究方法可分為基于過程式模型檢測、基于日志轉(zhuǎn)換和基于聲明式檢測的方法。

2.1.1 基于過程式模型檢測的方法

定義1 過程式模型檢測問題[55]

給定一組活動集合A,由一系列活動組成的非空序列稱為工作流執(zhí)行軌跡σ∈A*,軌跡的多重集合表示為日志L∈B(A*),其中B(A*) 表示A*的冪集。過程式模型是指事件次序與日志中的活動次序保持一致,如順序模式、并行分支模式、同步模式等。過程式模型檢測問題是指將日志轉(zhuǎn)化為端到端過程模式的過程。

表1列舉了過程式模型檢測任務清單,各任務均是以序列模式挖掘方法為解決方案。其中,最具代表性的任務為頻繁子片段(episode)挖掘問題。

表1 過程式模型檢測問題任務清單

定義2 片段,子片段[9]

片段為事件的偏序集合,表示為三元組α=＜V,≤,g ＞,其中V為一組事件的集合,≤為定義在V上的偏序關(guān)系集合,g:V→A為事件和活動之間的對應函數(shù)。存在另一個片段β=＜V′,≤′,g′ ＞是α的子片段,記作β?α,當且僅當存在內(nèi)射函數(shù)f:V′→V,使得以下2 個條件同時滿足:

(1) ?v∈V′:g′(v)=g(f(v)),即β中的所有節(jié)點都出現(xiàn)在α中;

(2) ?v,w∈V′∧v≤′w:f(v) ≤f(w),即β中的所有邊都出現(xiàn)在α中。

片段使用有向無環(huán)圖(directed acyclic graph,DAG)進行表示,DAG 中的節(jié)點代表事件(出現(xiàn)在日志的活動集合中),DAG 中的邊代表事件之間存在偏序關(guān)系。如圖3 所示為3 個片段,其中E1表示事件A(D)與事件B(E)并發(fā)執(zhí)行,事件C 只能在事件A 和B 發(fā)生之后執(zhí)行;E2表示事件A 執(zhí)行后有事件B 和事件C 兩種選擇,而事件B 執(zhí)行后D 才能執(zhí)行,或者事件C 執(zhí)行后D 才能執(zhí)行;E3表示,事件A和B 并發(fā)執(zhí)行,其中A 和B 之間沒有連邊。

圖3 片段示例

定義3 頻繁子片段挖掘問題[9]

片段α=＜V,≤,g ＞在工作流執(zhí)行軌跡σ=＜a1,a2,…,an ＞中出現(xiàn),記作α?σ,當且僅當存在一個內(nèi)射函數(shù)h:V→{1,…,n},使得以下2 個條件同時滿足:

(1) ?v∈V:g(v)=ah(v)∈σ成立,即片段中的事件與日志中的活動一致;

(2) ?v,w∈V∧v≤w:h(v)≤h(w),即片段中事件之間的偏序關(guān)系與日志中活動間的次序一致。

片段α在日志L∈B(A*)中出現(xiàn)的頻率定義為

表示片段中的偏序關(guān)系在日志中出現(xiàn)的次數(shù)。片段發(fā)現(xiàn)問題旨在從事件日志中找到所有滿足freq(α) 大于等于給定閾值的片段。

2.1.2 基于日志轉(zhuǎn)換的方法

求解過程式模型檢測問題,通常采用基于轉(zhuǎn)換的方法,即將頻繁日志轉(zhuǎn)換為圖/樹模式。(1)工作流圖是最早提出的頻繁日志的轉(zhuǎn)換對象[53],它的特點是不能識別工作流中的AND/OR 匯集結(jié)構(gòu)和分支結(jié)構(gòu)。因此,工作流圖只能用來表示不包含OR結(jié)構(gòu)的工作流網(wǎng)。(2)有向無環(huán)圖(directed acyclic graphs,DAG)是最常用的轉(zhuǎn)換表示[9]。然而目前,DAG 只能表示頻繁日志中的順序和并發(fā)模式,對于日志中出現(xiàn)的選擇、循環(huán)等復雜結(jié)構(gòu)仍不能檢測。(3)實例圖常用于聚類,實施步驟為首先將每條頻繁日志轉(zhuǎn)換為實例圖,然后運行圖聚類算法[59]。與DAG 類似,實例圖也僅能表示頻繁日志中的順序和并發(fā)模式。(4)過程樹是一種直觀的樹型結(jié)構(gòu),樹中的葉子節(jié)點代表日志中的活動,分支節(jié)點代表活動之間的關(guān)系[70]。使用過程樹構(gòu)造Petri 網(wǎng)的步驟是,首先從頻繁日志中提取過程樹,然后根據(jù)6 種預設(shè)規(guī)則,將過程樹轉(zhuǎn)換為可靠的(也稱為良構(gòu)的)端到端過程模型。與前幾種表示不同,基于過程樹的方法不僅支持基本的控制流模式,還可表示復雜的選擇、循環(huán)等結(jié)構(gòu)。

2.1.3 基于聲明式規(guī)則檢測的方法

近年來,由進程挖掘中的進程發(fā)現(xiàn)任務衍生出了另一項具有挑戰(zhàn)性的任務——聲明式規(guī)則發(fā)現(xiàn)(declarative rule discovery)[71],是指從日志中提取一系列符合時態(tài)邏輯規(guī)則的任務,又稱約束發(fā)現(xiàn)。已往的進程挖掘中的進程發(fā)現(xiàn)任務,只能得到結(jié)構(gòu)化(structured)的工作流網(wǎng),而聲明式規(guī)則是一種弱結(jié)構(gòu)化(less-structured)的表示形式,是對進程挖掘任務的補充。

定義4 聲明式規(guī)則發(fā)現(xiàn)[72]

給定活動集合A={a1,a2,…,am} 和一條日志L={t1,t2,…,tn},其中tq(1 ≤q≤n) 表示一條取值于A的有限活動記錄。聲明式規(guī)則挖掘旨在從日志中抽取滿足時態(tài)邏輯關(guān)系的一系列約束。其中,約束由以下3 部分組成。

(1)取值于A的活動。

(2)活動之間的布爾型連接關(guān)系,包括非(?)、與(∧)、或(∨)、蘊含(?)、等價(?)。

(3)基于有限序列的線性時態(tài)邏輯(linear temporal logic on finite traces,LTLf)算子,包括必然算子(□)、可能算子(◇)、直到算子(∪)、下一時刻算子(○)。

例1給定活動集合A={S,A} 和日志t=其中1,2,… 代表活動在日志中的下標。日志t中包含一條聲明式規(guī)則RESPONSE(S,A),其含義為□(S?◇(A)),S發(fā)生時都有A跟隨發(fā)生。

日志t中規(guī)則RESPONSE(S,A) 的實例為{S1A1},{S2A1},{S3A1},{S4A2},{S5A3},{S6A3}。

在聲明式規(guī)則發(fā)現(xiàn)任務中,仍然是以日志作為主要輸入數(shù)據(jù)類型。但不同的是,關(guān)注日志的視角和粒度與傳統(tǒng)進程挖掘不同。日志中記錄著大量已經(jīng)發(fā)生的活動(也稱事件、案例、任務)以及活動間的邏輯依賴關(guān)系。這些依賴關(guān)系是聯(lián)系日志與進程模型、日志與Declare 規(guī)則之間的重要紐帶[73]。作為常用的數(shù)據(jù)預處理方法,FIM 方法首先針對日志中大量的活動進行初步過濾,然后提取活動之間的依賴關(guān)系。FIM 問題與聲明式挖掘問題的數(shù)據(jù)類型有著密不可分的聯(lián)系,如表2 所示。表3 列舉了聲明式規(guī)則檢測問題任務清單。

表2 頻繁項挖掘與聲明式規(guī)則挖掘?qū)Ρ?/p>

表3 聲明式規(guī)則檢測問題任務清單

2.2 基于二維工作流網(wǎng)挖掘頻繁子網(wǎng)

定義5 頻繁工作流網(wǎng)子網(wǎng)挖掘

給定工作流網(wǎng)集W={w1,w2,…,wT},子網(wǎng)x的支持度定義為包含它的工作流網(wǎng)占比

頻繁工作流子網(wǎng)挖掘旨在從工作流網(wǎng)集中挖掘得到子網(wǎng)/片段,以供工作流網(wǎng)重用、設(shè)計。工作流網(wǎng)頻繁子網(wǎng)挖掘的相關(guān)研究重點關(guān)注以下兩方面問題。

(1)工作流網(wǎng)標簽一致性。工作流網(wǎng)的標簽往往使用WordNet 進行統(tǒng)一規(guī)范,標簽有固定的語法形式,即動詞+賓語,例如檢查訂單、創(chuàng)建賬戶等。

(2)工作流網(wǎng)適合的圖形表示方法為基于轉(zhuǎn)換的方法。本文主要關(guān)注此類問題。

2.2.1 基于工作流網(wǎng)轉(zhuǎn)換的方法

目前已有的工作流網(wǎng)頻繁子網(wǎng)挖掘通常采用兩步走的解決方案。

第一步,對工作流網(wǎng)進行轉(zhuǎn)換。例如,(1)僅將工作流網(wǎng)中的事件轉(zhuǎn)換為圖節(jié)點,將條件以及輸入輸出弧作為圖的邊,多用于轉(zhuǎn)換一種特殊類型的工作流網(wǎng)—標識圖。(2)僅將工作流網(wǎng)中的條件轉(zhuǎn)換為圖節(jié)點,將事件、輸入輸出弧作為圖的邊[75],多用于另一類工作流網(wǎng)—狀態(tài)機。(3)將工作流網(wǎng)中的兩類節(jié)點(事件、條件)轉(zhuǎn)換為圖的一種節(jié)點,將輸入輸出弧作為圖的邊[76]。

第二步,基于轉(zhuǎn)換的圖直接運行頻繁子圖挖掘、圖聚類等算法。首個工作流網(wǎng)挖掘方法是w-find 算法[77]。該算法的輸入是工作流轉(zhuǎn)換而成的控制流圖(control flow graph,CFG),算法的目標是挖掘出CFG 中所有滿足閉合約束的子圖。然而,CFG 只包含一類節(jié)點,代表日志中的活動,邊代表活動之間的數(shù)據(jù)流。可以發(fā)現(xiàn),w-find 算法利用頻繁子圖挖掘技術(shù)得到頻繁的活動,是對進程挖掘任務的驗證和擴充。文獻[78]提出BPMClustering 算法,利用圖聚類方法基于多個工作流網(wǎng)進行聚類計算,計算多個工作流網(wǎng)之間的相似度。然而,該方法不能挖掘常見的選擇和并發(fā)結(jié)構(gòu)。文獻[79]提出IGP 算法,該算法將每條日志都轉(zhuǎn)換為一個實例圖(instance graph),然后在大規(guī)模的實例圖之間實施頻繁子圖挖掘,但挖掘出的實例圖僅能還原順序和并發(fā)結(jié)構(gòu),一些復雜模式無法挖掘。類似w-find 算法,IGP 算法的目標也是對于進程挖掘任務進行部分驗證。文獻[1]基于w-find 算法提出從進程模型中挖掘頻繁模式的問題,將頻繁子圖挖掘的方法應用于工作流網(wǎng)模式抽取中,并開發(fā)出工具WoMine 對工作流網(wǎng)的拓撲結(jié)構(gòu)進行挖掘。然而算法得到的子結(jié)構(gòu)不再是工作流網(wǎng)。常見的基于圖集合的頻繁子圖挖掘算法在工作流網(wǎng)挖掘中的應用如表4 所示。

表4 基于圖集合的頻繁子圖挖掘算法在工作流網(wǎng)挖掘中的應用

2.2.2 序列與網(wǎng)混合式方法

混合的方法是指從一維日志序列中構(gòu)造二維的工作流網(wǎng),然后再將工作流網(wǎng)與日志序列進行比對計算。代表性的混合方法是一致性檢測算法[80]。一致性檢測利用對齊映射等方式解決模型重演問題,但是大多數(shù)一致性檢測技術(shù)僅提供基本統(tǒng)計信息,例如不一致的偏差數(shù)量。關(guān)于序列與網(wǎng)混合的方法研究仍是少數(shù),表5 中列舉了幾種代表性的序列與網(wǎng)混合方法。

表5 序列與網(wǎng)混合式方法所適用的具體任務清單

業(yè)務流程的執(zhí)行順序決定了業(yè)務的正確性和完整性。檢測此工作流網(wǎng)與日志序列之間的一致性程度,關(guān)乎業(yè)務流程的正常運行。但如果單獨的檢測每個流程的偏差,十分耗時耗力。利用頻繁子網(wǎng)的方式將工作流網(wǎng)中重復執(zhí)行的片段進行提取,利用分治的策略將日志進行分解,是一種常用的技術(shù)手段[82]。

例如,銀行的匯款流程預定義了檢測步驟:開始匯款處理、讀取系統(tǒng)配置文件、核查收款人的銀行信息等,完整的流程在每次匯款時都會重復發(fā)生。

實際上,在上述重復執(zhí)行的匯款進程中通常存在一種異常模式,即具有高級權(quán)限的VIP 客戶可以跳過冗長的預配置檢測階段。然而這種異常模型并非每次都出現(xiàn)在日志序列中,這就需要使用頻繁模式挖掘的手段對工作流網(wǎng)的子結(jié)構(gòu)進行混合分析。

3 FPM 用于工作流網(wǎng)頻繁子網(wǎng)挖掘的問題及缺陷分析

3.1 基于SPM 構(gòu)造工作流網(wǎng)的問題

在進程挖掘研究中,關(guān)注更多的是如何從日志中抽取滿足偏序關(guān)系、控制流依賴關(guān)系的工作流網(wǎng)。Leemans 和Aalst[9]提出EpisodeDiscovery 算法,利用序列挖掘算法PrefixSpan 分析日志序列。但要求所采用的日志必須具備時間、資源等具有偏序關(guān)系的數(shù)據(jù)。EpisodeDiscovery 算法的目的是從日志中抽取出工作流網(wǎng)的順序結(jié)構(gòu),體現(xiàn)出與日志中一致的偏序關(guān)系。Tax 等人[58]提出LocalProcessModel 算法,旨在從一維的日志序列中構(gòu)造出工作流網(wǎng)的順序結(jié)構(gòu)、并發(fā)結(jié)構(gòu)、選擇結(jié)構(gòu)等復雜的結(jié)構(gòu)。該算法的目的與前面的方法均有所不同,算法并不要求得到完整的工作流網(wǎng),只需要得到局部結(jié)構(gòu)作為重要的模式。

盡管當前序列模式挖掘、進程挖掘問題已被廣泛研究,但將序列模式挖掘方法用在進程挖掘,解決工作流網(wǎng)及其子網(wǎng)的構(gòu)造仍存在以下問題。

(1)構(gòu)造的工作流網(wǎng)結(jié)構(gòu)復雜。由于進程挖掘的諸多方法基于規(guī)則匹配,存在封閉世界的假設(shè),使得構(gòu)造出的許多工作流網(wǎng)存在過擬合的現(xiàn)象,存在許多結(jié)構(gòu)復雜、重復、冗長的工作流網(wǎng)模型。在大數(shù)據(jù)的場景下,文獻[84]中提出利用分治策略將日志和模型進行分解,從而降低進程挖掘構(gòu)造工作流網(wǎng)的復雜度,但挖掘到的工作流網(wǎng)仍然十分復雜,許多研究者稱之為“意大利面”式。

(2)聲明式規(guī)則發(fā)現(xiàn)低效。由于聲明式規(guī)則使用基于有限序列的線性時態(tài)邏輯LTLf的操作算子進行表示,當規(guī)則數(shù)量龐大時,算法處理十分耗時。但聲明式規(guī)則的優(yōu)點是比較靈活,適合于不同層面的日志解析,不再局限于以結(jié)構(gòu)為導向。

(3)可解釋性差。許多挖掘出的頻繁子結(jié)構(gòu)/子模式的意義難以解釋,因為缺乏領(lǐng)域知識的支撐,通常被認作無意義。例如,在生物信息學中,挖掘出的頻繁模式是否有意義需要由領(lǐng)域?qū)＜覜Q定。

3.2 基于FSM 進行工作流網(wǎng)挖掘的問題

工作流網(wǎng)是一種具有單一入口、單一出口,并且執(zhí)行流程受結(jié)構(gòu)化約束的Petri 網(wǎng),是刻畫業(yè)務執(zhí)行邏輯的主要形式。Petri 網(wǎng)中的元素“條件”、“事件”、“流關(guān)系”與工作流網(wǎng)中的“案例”、“任務”、“過程”一一對應。

定義6 工作流網(wǎng)[55]

令N=(C,E;F) 一個Petri 網(wǎng),N是工作流網(wǎng),若

(1) ?e∈E:·e≠? ∧e·≠?;

(2) ?i∈C:|{i|·i=?}|=1,其中i稱為N的源條件;

(3) ?o∈C:|{o| o·=?}|=1,其中o稱為N的匯結(jié)條件;

(4) ?x∈C∪E都位于從i到o一條正向路徑或反向路徑上。

由于頻繁子圖挖掘算法在一般圖上的成功應用,許多研究者致力于將FSM 技術(shù)推廣到其他領(lǐng)域。在工作流網(wǎng)上的應用需要將工作流網(wǎng)進行轉(zhuǎn)換。然而大多數(shù)情況下,這種轉(zhuǎn)換無法還原,不滿足雙射關(guān)系,會丟失重要信息。因此,傳統(tǒng)的頻繁子圖挖掘方法無法直接用于工作流網(wǎng)挖掘。其本質(zhì)原因如下。

(1)復雜、異構(gòu)拓撲結(jié)構(gòu)。從定義6 中不難看出,工作流網(wǎng)具有兩類節(jié)點集和一類邊集,而一般圖通常由一類節(jié)點集和一類邊集組成。通常情況下,工作流網(wǎng)的第一類節(jié)點叫做事件(表示動作)節(jié)點,第二類節(jié)點叫做條件(表示狀態(tài))節(jié)點。

(2)非獨立帶約束連接類型。遵循Petri 網(wǎng)的結(jié)構(gòu)性質(zhì),在工作流網(wǎng)中,弧(連接)是不能獨立的,必需依附在它兩端的條件/事件節(jié)點,且同一類型的節(jié)點之間不能有弧。這也使得工作流網(wǎng)的結(jié)構(gòu)約束性更強,是工作流網(wǎng)處理中高復雜度的主要來源。

(3)完備性語義。一般圖結(jié)構(gòu)可無語義約束(或可賦予任意語義)。Petri 教授本人曾指出,Petri網(wǎng)具有內(nèi)置完備性語義。一個Petri 網(wǎng)中的流關(guān)系通常是“前提條件事件后提條件”。此內(nèi)置語義為Petri 網(wǎng)中不可分割的單元。然而轉(zhuǎn)換為一般圖后丟失了完備性語義。工作流網(wǎng)是Petri 網(wǎng)的一種特殊子類,因此,工作流子網(wǎng)應是一種不可分割的執(zhí)行單元[15]。

(4)執(zhí)行約束。定義6 的2、3 條件規(guī)定了工作流網(wǎng)具有唯一的入口和出口,即工作流網(wǎng)具有執(zhí)行約束[5],此約束是工作流網(wǎng)滿足可靠性、無死鎖的重要理論依據(jù)。

目前,工作流網(wǎng)挖掘工作得到的子網(wǎng)都不再是工作流網(wǎng),因為轉(zhuǎn)換破壞了工作流網(wǎng)的語義特性。從理論角度分析,目前缺乏關(guān)于工作流子網(wǎng)的統(tǒng)一定義,通常將其與一般圖等同處理。進一步講,缺乏工作流子網(wǎng)同構(gòu)的嚴格定義。這些都是工作流頻繁子網(wǎng)挖掘工作中有待探索的問題。

4 工作流網(wǎng)頻繁子網(wǎng)挖掘典型應用

4.1 異常檢測

對于構(gòu)建工作流網(wǎng)及挖掘工作流網(wǎng)結(jié)構(gòu)這兩類主要任務而言,異常模式的存在都為問題求解增加了難度。許多異常體現(xiàn)出統(tǒng)計意義上的特征,例如出現(xiàn)的較少(低于頻繁閾值),即可被判定為異常。已有很多研究成果利用FPM 方法對異常進行檢測、過濾處理[85-87]?；陉P(guān)系對日志過濾、基于統(tǒng)計概率對日志過濾,都在一定程度上提升了日志質(zhì)量,使得構(gòu)造的工作流網(wǎng)質(zhì)量有所保障。

4.2 跨組織變體分析

在業(yè)務流程管理(business process management,BPM)領(lǐng)域,廣泛存在子結(jié)構(gòu)重復出現(xiàn)的現(xiàn)象。它們具有高度重用的特點。跨組織變體問題是指針對同一個流程,在不同組織、不同地域之間會存在著共性和差異性,這些差異性被稱為變體[6]。變體中的共性信息體現(xiàn)了不同變體之間的關(guān)聯(lián),得到共性信息可以促進不同組織之間的信息共享、甚至是平臺共用。例如,對于醫(yī)生診斷流程,不同醫(yī)院和不同醫(yī)生檢查在診斷步驟上會存在一些差別,但不同的醫(yī)院、不同醫(yī)生之間往往遵循一個公共的模式[88]。得到這種公共模式可以為許多醫(yī)院提供病例模版和診斷指導。

4.3 模型重用

對于大多數(shù)制造企業(yè)來說,設(shè)計新的業(yè)務流程(如零件裝配流水線)耗費巨大,需要多部門協(xié)調(diào)、整合歷史資源。文獻[89]針對不同組織環(huán)境、不同部門之間相同/相似的子結(jié)構(gòu)/子模式進行相似度計算,同時也表明了已有Petri 網(wǎng)模式的重用對于企業(yè)的流程設(shè)計而言意義重大。生物信息學領(lǐng)域提出工作流數(shù)據(jù)集myExperiment[90]、Taverna[91]及其配套的開發(fā)軟件,旨在檢索、共享、重用工作流。利用頻繁模式挖掘(FPM)方法提取頻繁的子結(jié)構(gòu)是常用的研究方法。

4.4 其他應用

除上述應用外,頻繁模式挖掘技術(shù)也在不斷進步,提出了更能夠體現(xiàn)模式意義的算法[67,92-94]。頻繁模式挖掘技術(shù)在不同領(lǐng)域中也發(fā)揮著重要作用,例如醫(yī)療輔助保健系統(tǒng)、決策系統(tǒng)以及e-learning 電子學習系統(tǒng)。在這些系統(tǒng)中,軟件執(zhí)行過程通常存在重復、循環(huán)[95-96]。在e-learning 系統(tǒng)中,通過學生與課堂之間的互動分析頻繁的行為模式[1]。另一方面,老師可以根據(jù)挖掘的頻繁模式改進課程設(shè)計。

5 總結(jié)與展望

本文首先依據(jù)3 種數(shù)據(jù)類型,對于工作流網(wǎng)頻繁子網(wǎng)挖掘的研究方法進行分類,其次,針對2 種主流研究方向,即從一維日志進程中構(gòu)造工作流網(wǎng)及其子網(wǎng)和從二維工作流網(wǎng)中挖掘其頻繁子網(wǎng)結(jié)構(gòu),分別給出具體的問題描述、任務列表及相關(guān)數(shù)據(jù)表示。本研究可得到如下結(jié)論。

(1)在以進程挖掘技術(shù)作為手段,構(gòu)建工作流網(wǎng)的任務中,諸多SPM 算法被應用,聚焦于工作流網(wǎng)在控制流層面(簡單的拓撲結(jié)構(gòu))的構(gòu)造。然而針對復雜拓撲結(jié)構(gòu),如選擇、循環(huán)等結(jié)構(gòu)以及不可見的隱含信息,當前SPM 算法仍然不能平衡準確度和泛化程度,并且容易過擬合。

(2)在進程挖掘技術(shù)的演進發(fā)展中,構(gòu)建聲明式的規(guī)則為一項比較新穎的任務。FIM 算法被用于日志預處理階段,其關(guān)鍵在于保持日志活動序。然而,目前只有少量FIM 算法被用于此任務中。

(3)對于具有二維異構(gòu)拓撲結(jié)構(gòu)的工作流網(wǎng)挖掘分析問題,解決方法更為復雜。當前,經(jīng)典的FSM 算法,如gSpan 算法、SUBDUE 算法被廣泛用于挖掘工作流網(wǎng)子網(wǎng)問題中。然而,由于缺乏針對工作流網(wǎng)的理論問題探究,例如,對于工作流網(wǎng)結(jié)構(gòu)的特殊性、工作流網(wǎng)表示方法的正確性等的考察,適合于工作流網(wǎng)的頻繁子網(wǎng)算法還有待嚴格的理論驗證。

伴隨著網(wǎng)絡技術(shù)的飛速發(fā)展,網(wǎng)絡交易系統(tǒng)、業(yè)務流程管理系統(tǒng)等應用場景產(chǎn)生了海量大規(guī)模工作流網(wǎng)。復雜異構(gòu)的網(wǎng)絡結(jié)構(gòu)、豐富的語義,為FPM在工作流網(wǎng)中的應用帶來了新的挑戰(zhàn)。將工作流網(wǎng)頻繁子網(wǎng)挖掘研究推廣至一般Petri 網(wǎng)更具難度。因為一般Petri 網(wǎng)類型眾多,性質(zhì)更復雜。文獻[15]提出完備子網(wǎng)的概念和適用于一般Petri 網(wǎng)的壓縮數(shù)據(jù)表示方法,是對一般類型Petri 網(wǎng)的頻繁子網(wǎng)挖掘研究的嘗試。但是文獻[15,97]中的一般Petri 網(wǎng)頻繁子網(wǎng)挖掘技術(shù)仍不能用于工作流網(wǎng),這是因為缺乏保特殊語義的劃分工作流子網(wǎng)的方法。因此,以下幾點是工作流網(wǎng)頻繁子網(wǎng)挖掘研究可能的發(fā)展趨勢:

(1)針對海量數(shù)據(jù)特征,設(shè)計一種包容異構(gòu)性、完備性語義的工作流網(wǎng)子網(wǎng)劃分方法,以及滿足完備性語義的新的表示形式,并設(shè)計更高效的工作流網(wǎng)挖掘算法,將頻繁模式挖掘理論推廣至工作流網(wǎng)及其廣義領(lǐng)域。

(2)一直以來,在Petri 網(wǎng)(包含工作流網(wǎng))研究領(lǐng)域中,帶token(托肯,也被稱為令牌)的動態(tài)信息一直是工作流網(wǎng)性能分析的瓶頸[98]。特別是,托肯體現(xiàn)全局范圍內(nèi)資源的流動,而子網(wǎng)技術(shù)是局部層面的研究。文獻[98]考慮動態(tài)性質(zhì)的同時探討了網(wǎng)絡交易系統(tǒng)漏洞檢測問題的解決思路。如何設(shè)計子網(wǎng)挖掘算法,保持整個工作流網(wǎng)的性質(zhì),并在電信詐騙檢測、用戶行為分析等更具挑戰(zhàn)性的場景中發(fā)揮作用,是未來工作的重點。

(3)工作流網(wǎng)是一種特殊類型的Petri 網(wǎng),而Petri 網(wǎng)區(qū)別于其他建模工具的根本性優(yōu)勢在于其能夠描述真并發(fā)、具有嚴格的執(zhí)行語義。除了本文聚焦的拓撲層面的完備性語義,Petri 網(wǎng)通用網(wǎng)論(包括多種Petri 網(wǎng)的共有特性挖掘,如并發(fā)特性、同步特性、沖突特性)還有待進一步研究。