過程挖掘技術的研究與應用

鄧璐娟，董東曉，陳欣欣

(鄭州輕工業學院 計算機與通信工程學院，河南 鄭州 450002)

過程挖掘技術的研究與應用

鄧璐娟，董東曉，陳欣欣

(鄭州輕工業學院 計算機與通信工程學院，河南 鄭州 450002)

由于業務流程日益復雜多變，并且流程模型設計者對于業務流程的理解主觀性較強，大多數通過人工建立的過程模型都與現實情況存在較大偏差，使用過程挖掘技術能夠很好地解決這一問題。針對典型的工作流系統中索賠事件流程的日志，對其建模流程進行分析，使用過程挖掘工具ProM進行挖掘得到對應的過程模型。實驗結果表明，通過過程挖掘技術所得到的過程模型與實際的業務流程相符，與人工流程建模相比，提高了效率，降低了成本。

過程挖掘；事件日志；挖掘算法

Abstract: Because the business process is increasingly complicated, and the process model for business process designer’s understand has strong subjectivity, most process models established artificially have a big deviation with reality. Using process mining technology can solve this problem well. In view of the log of the claim event process in the typical workflow system, the modeling process is analyzed, and the corresponding process model is obtained by using the process data mining tool ProM. The experimental results show that the process model is consistent with the actual business process, and the process model is very efficient and can reduce the cost.

Key words:process mining; event log; mining algorithm

0 引言

企業資源規劃系統(ERP)、供應鏈管理系統(SCM)、客戶關系管理系統(CRM)和工作流管理系統(WFM)等在企業中得到了廣泛的應用。這些信息系統和它們所支持的業務運作流程結合非常緊密。面對復雜的、快速多變的業務流程，工作流建模技術遇到了問題，例如，由于流程設計者對于業務流程的理解不到位，使得設計出的工作流模型與實際的業務流程存在偏差。此外，系統中記錄了數量眾多的事件，從這些寶貴的事件數據中提取有價值的信息也比較困難。過程挖掘技術的出現能很好地解決這些問題，使用過程挖掘技術進行企業流程建模不需要依賴業務流程領域的專家知識，只需要提供記錄這些流程的數據就能夠根據這些流程數據自動生成對應的過程模型，并且這種過程模型的生成方法是領域獨立的[1]。

1 過程挖掘技術的應用

通過對事件日志中的數據進行分析提取得到過程相關的信息，從而自動地發現過程模型的技術就是過程挖掘。過程挖掘涉及機器學習、數據挖掘、過程建模與分析等多個領域的知識[1]。過程挖掘技術通過對事件日志的處理和分析發掘日志中所包含的業務過程模型，過程挖掘建立了兩種連接，一是實際過程與其數據的連接；二是實際過程與過程模型的連接。這種自動生成過程模型的技術不僅能夠最大限度地減少建模過程中人為因素的干擾，使得過程模型與實際過程更加吻合，而且還提高了建模效率。

事件日志是進行過程挖掘的基礎，一份高質量的事件日志能為過程挖掘的實施提供很多便利。如圖1所示，事件日志主要用于三種類型的過程挖掘場景:第一種應用是發現，即使用不包括任何先驗信息的事件日志生成過程模型；第二種應用是合規性檢查，即使用一個已知的過程模型與它產生的事件日志相比較，驗證過程模型是否與日志中的實際情況相吻合；第三種應用是改進，其理念是利用實際過程產生的事件日志來擴展或改進一個已經存在的過程。

圖1 三種主要的過程挖掘場景

表1中顯示了處理索賠申請過程所對應的一個可能日志的一部分，每一行代表一個事件，事件按照不同的案例進行分組。在具體的挖掘過程中只用到了事件日志中的部分信息，過程挖掘的最低要求是每個事件都能對應一個案例和一個活動，并且一個案例中的事件是有序的。因此，表中的“案例ID”和“活動”這兩個列代表了過程挖掘對于事件日志的最低要求。

表1 索賠申請事件部分日志

在真實的工作流系統中，事件日志以挖掘可擴展標記語言(Mining eXtensible Markup Language,MXML)文件的形式保存過程挖掘工具ProM對其操作，MXML也是當前存儲和交換事件日志的事實上的標準。采用IEEE Task Force on Process Mining小組定義的XES(eXtensible Event Stream)格式，則描述的事件流程的日志如下所示。

……

……

……

對這個事件，采用α算法進行挖掘。L表示基于某個活動集合T的事件日志，T?A，則α(L)可以如下定義：

(1)TL={t∈T?σ∈Lt∈σ}

(2)TI={t∈T?σ∈Lt=first(σ)}

(3)TO={t∈T?σ∈Lt=last(σ)}

(4)XL={(A,B)A?TL∧A≠?∧B?TL∧B≠?∧?a?A?b?Ba→Lb∧?a1,a2?Aa1#La2∧?b1,b2?Bb1#Lb2}

(5)YL={(A,B)∈XL?(A′,B′)∈XLA?A′∩B?B′?(A,B)=(A′,B′)}

(6)PL={P(A,B)(A,B)∈YL}∪{iL,oL}

(7)FL={(a,p(A,B))(A,B)∈YL∧a∈A}∪{(p(A,B),b)(A,B)∈YL∧b∈B}∪{(iL,t)t∈TI}∪{(t,oL)t∈To}

(8)α(L)=(PL,TL,FL)

第一步，檢查出現在日志中的活動(TL)，這些活動對應著最終生成的工作流網中的變遷。第二步要找出開始活動的集合TI，即在軌跡中出現在第一個位置的所有活動的集合。第三步要找出結束活動的集合TO，即在軌跡中出現在最后一個位置的所有活動的集合。第四步要確定工作流網中的庫所以及它們之間的連接關系XL。A中任何一個元素不能緊跟同集合內的其他元素，即對于所有的a1,a2∈A都有a1#La2，對于集合B中的元素也是同樣的要求，B中的元素都可以緊跟A中任意元素后邊，反之不然，即對于所有的(a,b)∈A×B，有a→Lb。所有滿足要求的A，B對構成的結合就是XL。第五步是要精簡庫所。如果把XL中的每個元素都作為一個庫所，庫所規模就很大，因此對庫所進行精簡，只保留“最大的”(A,B)，即(A′,B′)記為YL。第四步和第五步是α算法的核心。第六步是要得到庫所PL。每一個元素(A,B)∈YL都對應著一個庫所P(A,B)，這個庫所連接了A和B中的變遷，此外，PL還包含一個唯一的源庫所iL和一個唯一的匯結庫所oL。第七步是要生成工作流網中的弧。TI中的所有變遷都以iL作為輸入庫所，TO中的所有變遷都以oL作為輸出庫所。所有P(A,B)都以A作為輸入節點，以B作為輸出節點。最終得到一個Petri網α(L)=(PL,TL,FL)如圖2所示。

圖2 α算法挖掘結果

從4個維度來衡量挖掘算法的質量，即擬合度(fitness)、精確度(precision)、泛化度(generalization)和簡潔度(simplicity)。擬合度是指得到的過程模型應該允許事件日志所反映的行為發生，一個擬合度良好的模型能夠重演日志中大部分軌跡；精確度是指得到的過程模型不應該允許與事件日志中所反映的行為完全無關的行為出現；泛化度是指得到的過程模型應該泛化事件日志中的行為例子；簡潔度是指得到的過程模型應該越簡單越好。這4個質量標準是相互競爭的，因此在這4個標準間取得平衡是一項挑戰。α算法雖然不能很好地滿足這4個質量標準，但是α算法是更高級的挖掘方法的基礎。

2 過程挖掘技術的現狀

1995年COOK J E等人第一次提出了過程挖掘的概念,并且提出了RNet、KTail和Markov三種過程挖掘算法[2-3]，挖掘出的過程模型用有限狀態機表示；德國的HERBST J等人[4]提出了三個能夠處理重復任務的算法，分別為：MergeSeq、SplitSeq以及SplitPar。荷蘭Eindhoven大學教授AALST W V D的團隊和國際其他機構及院校合作，取得了一系列的成果[5-8]，在挖掘算法方面，提出了α算法、啟發式挖掘算法以及區域挖掘算法等優秀算法；于2004年研發出開源過程挖掘工具ProM，發展到今天ProM已經集成了幾百個過程挖掘與分析插件，成為過程挖掘的事實標準。AALST W V D為過程挖掘的研究奠定了理論和實踐基礎，極大地推動了過程挖掘技術的發展。

國內過程挖掘的研究起步較晚，但也取得了一些顯著的成果。清華大學范玉順教授是國內過程建模領域較早的研究者，針對目前工作流管理系統在描述能力和柔性上存在的嚴重不足，通過擴展傳統活動網絡模型，提出了一種基于協調理論和反饋機制的新的過程建模方法[9-10]。清華大學王建民教授在文獻[11-13]中指出過程挖掘的研究迅速發展，各種挖掘算法不斷出現，但是過程挖掘數據集和過程挖掘算法評判卻沒有統一標準。為此，王建民教授提出了一種針對不同應用需求選擇過程挖掘算法的框架。針對α算法的不足，清華大學的聞立杰進行了擴展和改進[14-15]，提出的α++算法、α#算法以及β算法，突破了非自由選擇結構、不可見任務這兩大開放性過程挖掘的問題。文獻[16-18]中針對現有成批處理工作流調度方法的不足，利用微粒群算法的智能優化原理，提出一種動態分組調度優化模型；為了解決了現有工作流挖掘方法無法挖掘出工作流實例方面模型的問題，通過分析描述了業務過程實際執行情況的事件日志中活動輸入輸出等數據的特點，提出了一種基于工作流網的工作流實例方面模型挖掘方法。

3 過程挖掘技術的瓶頸與發展方向

過程挖掘作為一個新興技術領域在當前的研究中存在下面一些困難與挑戰：

(1)對于復雜結構和特殊結構的挖掘。雖然啟發式挖掘算法能夠處理不完備的日志和日志中的噪音，但對于日志中存在的重復或孤立的活動以及特殊循環結構還不能很好地處理。文獻[19-20]中基于啟發式算法做了一些改進，使之對特殊復雜結構的挖掘能力有一定的提升。

(2)對于挖掘結果的驗證困難。通過挖掘算法得到的結果要進行交叉驗證，交叉驗證的問題之一就是缺少反例，也就是說日志只提供了可能發生的行為，但卻沒有提供不可能發生的行為。文獻[21-22]提供一種可能的解決方案，即插入人工生成的反面事件。

(3)在線過程挖掘(比如提供預測和推薦)。隨著云計算和大數據技術的發展以及計算能力的提升，人們對于數據實時性的要求越來越高，所以在線過程挖掘將會是過程挖掘的一個重要發展方向。

[1] AALST W V D. 過程挖掘[M]. 王建民，聞立杰，等，譯.北京：清華大學出版社, 2014.

[2] COOK J E, WOLF A L. Automating process discovery through event-data analysis[C]. International Conference on Software Engineering. IEEE, 1995:73-73.

[3] COOK J E. Software process validation: quantitatively measuring the correspondence of a process to a model[J]. Acm Transactions on Software Engineering & Methodology, 1999, 8(2):147-176.

[4] HERBST J, KARAGIANNIS D. Integrating machine learning and workflow management to support acquisition and adaptation of workflow models[J]. Intelligent Systems in Accounting Finance & Management, 1998, 9(2):745-752.

[5] AALST W V D, ADRIANSYAH A, MEDEIROS A K A D, et al. Process mining manifesto[J]. Lecture Notes in Business Information Processing, 2011, 99:169-194.

[6] AALST W M P V D, REIJERS H A, WEIJTERS A J M M, et al. Business process mining: an industrial application[J]. Information Systems, 2007, 32(5):713-732.

[7] AALST W V D. Process mining: discovery, conformance and enhancement of business processes[M]. Springer Publishing Company, Incorporated, 2011: 1018-1019.

[8] AALST W M P V D, SCHONENBERG M H, SONG M. Time prediction based on process mining[J]. Information Systems, 2011, 36(2): 450-475.

[9] 范玉順. 工作流管理技術基礎[M]. 北京：清華大學出版社, 2001.

[10] 羅海濱, 范玉順,吳澄. 工作流技術綜述[J]. 軟件學報, 2000, 11(7): 899-907.

[11] Wang Jianmin, WONG R K, Ding Jianwei, et al. Efficient selection of process mining algorithms[J]. IEEE Transactions on Services Computing, 2013, 6(4):484-496.

[12] Wang Jianmin, Jin Tao, WONG R K, et al. Querying business process model repositories: a survey of current approaches and issues[J]. World Wide Web-internet & Web Information Systems, 2014, 17(3):427-454.

[13] Wang Jianmin, Song Shaoxu, Zhu Xiaochen, et al. Efficient recovery of missing events[J]. Proceedings of the VIDB Endowment, 2013, 6(10): 841-852.

[14] 聞立杰. 基于工作流網的過程挖掘算法研究[D]. 北京：清華大學, 2007.

[15] Wen Lijie, AALST W M, Wang Jianmin, et al. Mining process models with non-free-choice constructs[J]. Data Mining & Knowledge Discovery, 2007, 15(2):145-180.

[16] 文一憑. 工作流實例方面的調度與挖掘方法研究[D]. 長沙：中南大學, 2013.

[17] 陳志剛, 文一憑, 康國勝. 成批處理工作流動態分組調度優化方法[J]. 計算機集成制造系統, 2012, 18(8):1693-1699.

[18] 文一憑, 劉潔. 工作流模型挖掘算法及其應用研究[J]. 計算機技術與發展, 2008, 18(7):93-95.

[19] 魯法明, 曾慶田, 段華,等. 一種并行化的啟發式流程挖掘算法[J]. 軟件學報, 2015, 26(3):533-549.

[20] 朱銳, 李彤, 莫啟,等. 啟發式并行化單觸發序列挖掘算法[J]. 計算機集成制造系統, 2016, 22(2):330-342.

[21] GOEDERTIER S, MARTENS D, BAESENS B, et al. Process mining as first-order classification learning onlogs with negative events[C]. Business Process Management Workshops, BPM 2007 International Workshops, BPI, BPD, CBP, ProHealth, RefMod, semantics4ws, Brisbane, Australia, September 24, 2007, Revised Selected Papers， 2007:42-53.

[22] GOEDERTIER S, MARTENS D, VANTHIENEN J, et al. Robust process discovery with artificial negative events[J]. Journal of Machine Learning Research, 2009, 10(9):1305-1340.

[23] 石杰. 云計算環境下的數據挖掘應用[J]. 微型機與應用, 2015, 34(5):13-15.

2017 TI杯全國大學生物聯網設計競賽完美收官

2017年9月15日，無錫訊——由教育部高等學校計算機類專業教學指導委員會主辦，全球領先模擬和嵌入式處理半導體廠商德州儀器(TI)(NASDAQ: TXN)協辦的“2017 TI杯全國大學生物聯網設計競賽”(以下簡稱“競賽”)決賽日前于無錫完美收官。

TI杯全國大學生物聯網設計競賽迄今已成功舉辦四屆，旨在以學科競賽推動專業建設，以物聯網行業項目和創新產品激發高校學生的創造力和創業活力，推動創新創業教育的持續開展。

本次競賽共吸引了來自國內500余所高校的1 500多支代表隊、1 700余名指導教師和6 500余名學生的積極報名參賽。經過線上預賽和華東、華中及西南、東北、華北和西北的全國5個分賽區的激烈角逐，共有120支團隊入圍全國總決賽。最終，來自哈爾濱工業大學的Hit Elites團隊憑借“Mr. Piano-遠程鍵盤樂器教學系統”項目脫穎而出，斬獲本屆TI杯特等獎。

此外，本屆大賽增設了線上投票環節，經過緊張激烈的6小時投票與互動，來自深圳大學-小白智能團隊的“基于CC3200和DLP技術的智能魚缸”、南京工業大學-InnoDrive團隊的“汽車輔助駕駛系統”以及北京理工大學-503團隊的“基于CC3200的聲音定位智能嬰兒車”三個設計作品榮獲本屆TI杯最佳人氣獎。

萬物相連已不是夢想，隨著科技腳步日新月異，物聯網正以成倍的速度發展中。作為最早進軍物聯網市場的全球性半導體設計制造公司之一， TI已成為可為物聯網應用提供廣泛模塊芯片的供應商——從節點到網關再到云端，TI提供眾多的產品及解決方案，包括微控制器、處理器、有線/無線連接、傳感器、信號鏈和電源管理解決方案等。

TI一直積極參與到物聯網工程專業的學科建設中。目前，TI已經在600多所大學中建立了超過3 000個數字信號處理、模擬及微控制器實驗室，每年有超過30萬名學生通過TI的實驗室和各類活動進行實踐。在本次物聯網設計競賽中，TI向各參賽隊提供了7種物聯網設計套件，包括TI CC3200 LaunchPad開發板、CC2650 LaunchPad開發板和CC2650STK套件等。同時，TI還提供了TI Design參考設計、無線技術選型指南、傳感器方案、MCU選擇參考、電池管理設計參考等豐富的資源，參賽隊伍在作品中可使用TI的設計套件，完成創意滿分的物聯網設計。

在TI的全球戰略中，大學計劃是極為重要的組成部分。今年是TI大學計劃進入中國的第21年，TI仍將不遺余力地在全球范圍內推行大學計劃，通過這個孕育科學技術人才的搖籃，與自身技術創新發展相結合，培養更多掌握世界先進技術的高級專業人才。

(TI供稿)

Research and application of process mining technology

Deng Lujuan, Dong Dongxiao, Chen Xinxin

(College of Computer and Communication Engineering,Zhengzhou University of Light Industry, Zhengzhou 450002, China)

TP311

A

10.19358/j.issn.1674- 7720.2017.18.004

鄧璐娟，董東曉，陳欣欣.過程挖掘技術的研究與應用[J].微型機與應用，2017,36(18)：11-14，17.

2017-02-26)

鄧璐娟(1964-)，女，博士，教授，主要研究方向：軟件工程、工作流建模。

董東曉(1991-)，男，碩士，主要研究方向：軟件工程、工作流建模。

陳欣欣(1993-)，女，碩士，主要研究方向：軟件工程。