工作流日志中的工作流模式圖挖掘技術研究

摘要：工作流挖掘技術能夠從系統的執行日志中構建出過程，大部分過程挖掘方法都使用了一種圖形化的方式來表示模型，也就是控制流圖。討論了工作流模式圖挖掘，它實際上是工作流挖掘的一種擴展；對其中所涉及的問題進行了剖析，并介紹了一種模式圖挖掘算法。

關鍵詞：工作流；工作流日志；過程挖掘；模式圖挖掘

中圖分類號：TP311文獻標志碼：A

文章編號：1001－3695(2008)01－0105－03

工作流是一類能夠完全或部分自動執行的經營過程，根據一系列過程規則、文檔、信息或任務能夠在不同的執行者之間傳遞、執行。在過去的十年里，工作流技術在工作流管理系統、企業資源管理（ERP）系統、供應鏈管理（SCM）系統、客戶資源管理（CRM）系統等軟件中得到了廣泛應用。它也一直是企業界與學術界關注的熱點領域[1，2]。

工作流日志包含了實際的工作流過程執行信息，它通常保存在系統的日志文件中。為了支持工作流的設計，更好地理解現有系統的實際過程，數據挖掘與機器學習技術被應用到了工作流領域來解決這一問題。它的基本思想是從工作流日志中提取出過程的工作流模型，該技術被稱為工作流挖掘或過程挖掘[3~5]。大部分過程挖掘方法使用了一種圖形化的方式來表示模型，即控制流圖。它用有向圖來描述過程，圖的頂點表示活動，邊表示兩個活動間的先后關系。這種關系實際上體現了活動間的同步、并發等關系，也可稱之為過程中活動間的局部約束關系。雖然這些方法能直觀地描述出過程中基本活動間的先后關系，但是它們不能發現活動的執行模式，即活動的一些執行結構，或者說過程中多個活動間隱含的約束關系。這在實際應用中是大量存在的。針對這個問題，本文介紹并剖析了一種基于聚類技術的工作流模式圖挖掘技術。它擴展了現有的工作流過程挖掘方法，主要特點在于對工作流日志進行了聚類分析。通過數據聚類，具有一些相同執行結構與行為的工作流日志記錄聚集到同一個簇中，可以用工作流模式圖來描述這種結構；然后應用層次聚類思想，逐步細化工作流模式圖，最終能夠較為準確地挖掘出隱含在過程中的多個活動間的約束關系。

1問題定義

為了便于介紹，先簡要描述要解決的主要問題。相關的一些符號定義如下：

a）P表示一個過程。

b）L(P)是P的工作流日志。為了便于問題的討論，假定L(P)是一個活動串的集合，它以活動串（如a1…an。其中ai均表示P中的活動）的方式記錄了P的執行信息。

c）WS(P)表示對應于P的實際工作流模式圖。它是一個三元組CF(P)，CL(P)， CG(P)。其中：CF(P)是P的控制流圖；CL(P)是P的活動局部約束關系集； CG(P)是P的多個活動間的約束關系。

d)WS(P)表示經過模式圖挖掘得出的P的工作流模式圖。它是工作流模式圖的一個集合{WSi|WSi=CFi，CLi，，1≤i≤m}，即隱含在過程中的多個活動間的約束關系用工作流模式圖WSi來表示。

e）soundness(WS(P)，L(P))表示WS(P)的錯誤率。在已知WS(P)的情況下，能夠推導出P的可能執行信息（假設共有A條記錄），但它們不一定與L(P)一致（即L(P)中并不存在這樣的記錄。假設這樣的記錄條數為B），那么soundness(WS(P)，L(P))=B/A。

f）completeness(WS(P)，L(P))表示WS(P)的完整率。相似地，L(P)中的每一條記錄也不一定與由WS(P)推導出P的可能執行信息一致（即L(P)的記錄并未在其中出現。假設這樣的記錄數為C）。設L(P)中的記錄總數為D，則completeness(WS(P)，L(P))=(D-C)/D。

g）|WS(P)|表示集合WS(P)中的元素個數。

h）σ，即如果completeness(WS(P) ，L(P))≥σ，稱WS(P)關于 L(P)是σ完整的。

i）m表示一個自然數。

顯然，WS(P)必然是正確地隱含在L(P)中的工作流模式圖。進行模式圖挖掘的目標就是使WS(P)與WS(P)盡可能地接近。另外，如果|WS(P)|等于L(P)中的記錄條數，即L(P)中的每一條記錄均用一個模式圖來描述，那么挖掘就失去了意義，應該對它作一個限制，m表示了這種限制。

因此，工作流模式圖挖掘要解決的問題是在L(P)，σ，m已知的情況下，找出合適的WS(P)，使WS(P)關于L(P)是σ完整的，|WS(P)|≤m，soundness(WS(P)，L(P))盡可能地小。

2模式圖挖掘技術分析

2．1基本思想和主要步驟

模式圖挖掘的基本思想是將對工作流日志進行聚類分析，提取出隱含的工作流模式圖，逐步對模式圖細化，最后得出最合適的模式圖集合。它的主要步驟可以分為三個階段。

1）控制流圖挖掘

與工作流日志的過程挖掘方法類似，首先應該處理活動間的關系，但處理要求并不一樣。從工作流日志中推導出活動間的依賴關系時，要考慮L(P)與σ這兩個參數的約束。與此相關的一些符號定義如下：

3結束語

作為支持企業經營過程重組(BPR)、經營過程自動化(BPA)的一種手段，工作流技術的研究應用日益受到了學術界與企業界的重視。工作流模式圖挖掘技術是對現有工作流過程挖掘技術的一種擴展，能夠進一步發現工作流日志中隱含的活動執行模式。但是，工作流模式圖挖掘是一項非常復雜的任務。本文所分析的算法沒有考慮到如何處理實際工作流日志中存在的噪聲數據。另外，如何改進聚類算法，降低聚類的時間復雜性與空間復雜性，使之更適用于工作流模式圖發現；如何結合文獻[7，8]，發現用戶在使用工作流系統時的一些行為習慣以優化工作流系統的任務配置等問題也都值得進一步的研究討論。

參考文獻：

［1］范玉順. 工作流管理技術基礎[M]. 北京：清華大學出版社，2001.

［2］羅海濱，范玉順，吳澄.工作流技術綜述[J].軟件學報，2000，11(7):899－907.

［3］AALST W M P van der，DONGEN B F van，HERBST J，et al.Workflow mining:a survey of issues and approaches[J].Data and Know ledge Engineering，2003，47(3):237－267.

［4］JOACHIM H，DIMITRIS K.Workflow mining with InWoLve[J].Computers in Industry，2004，53(3):245－264.

［5］AGRAWAL R，GUNOPULOS D，LEYMANN F.Mining process mo dels from workflow logs[C]//Proc of the 6th International Conference on Extending Database Technology.1998:469－483.

［6］嚴蔚敏，吳偉民.數據結構：C語言版[M].北京：清華大學出版社，1997.

［7］GRECO G，GUZZO A，MANCO G，et al.Mining and reasoning on workflows[J].IEEE Trans on Knowledge and Data Engineering，2005，17(4):519－534.

［8］AALST W M P van der，HOFSTEDE A H Mter，KIEPUSZEWSKI B，et al.Workflow patterns[J].Distributed and Parallel Databases，2003，14(3):5－51.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”