鄧璐娟，董東曉，陳欣欣

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

過程挖掘技術(shù)的研究與應(yīng)用

鄧璐娟，董東曉，陳欣欣

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

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

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

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 引言

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

1 過程挖掘技術(shù)的應(yīng)用

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

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

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

表1中顯示了處理索賠申請過程所對應(yīng)的一個可能日志的一部分，每一行代表一個事件，事件按照不同的案例進行分組。在具體的挖掘過程中只用到了事件日志中的部分信息，過程挖掘的最低要求是每個事件都能對應(yīng)一個案例和一個活動，并且一個案例中的事件是有序的。因此，表中的“案例ID”和“活動”這兩個列代表了過程挖掘?qū)τ谑录罩镜淖畹鸵蟆?/p>

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

在真實的工作流系統(tǒng)中，事件日志以挖掘可擴展標記語言(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)

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

圖2 α算法挖掘結(jié)果

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

2 過程挖掘技術(shù)的現(xiàn)狀

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

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

3 過程挖掘技術(shù)的瓶頸與發(fā)展方向

過程挖掘作為一個新興技術(shù)領(lǐng)域在當前的研究中存在下面一些困難與挑戰(zhàn)：

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

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

(3)在線過程挖掘(比如提供預(yù)測和推薦)。隨著云計算和大數(shù)據(jù)技術(shù)的發(fā)展以及計算能力的提升，人們對于數(shù)據(jù)實時性的要求越來越高，所以在線過程挖掘?qū)沁^程挖掘的一個重要發(fā)展方向。

[1] AALST W V D. 過程挖掘[M]. 王建民，聞立杰，等，譯.北京：清華大學(xué)出版社, 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] 范玉順. 工作流管理技術(shù)基礎(chǔ)[M]. 北京：清華大學(xué)出版社, 2001.

[10] 羅海濱, 范玉順,吳澄. 工作流技術(shù)綜述[J]. 軟件學(xué)報, 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] 聞立杰. 基于工作流網(wǎng)的過程挖掘算法研究[D]. 北京：清華大學(xué), 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] 文一憑. 工作流實例方面的調(diào)度與挖掘方法研究[D]. 長沙：中南大學(xué), 2013.

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

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

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

[20] 朱銳, 李彤, 莫啟,等. 啟發(fā)式并行化單觸發(fā)序列挖掘算法[J]. 計算機集成制造系統(tǒng), 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] 石杰. 云計算環(huán)境下的數(shù)據(jù)挖掘應(yīng)用[J]. 微型機與應(yīng)用, 2015, 34(5):13-15.

2017 TI杯全國大學(xué)生物聯(lián)網(wǎng)設(shè)計競賽完美收官

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

TI杯全國大學(xué)生物聯(lián)網(wǎng)設(shè)計競賽迄今已成功舉辦四屆，旨在以學(xué)科競賽推動專業(yè)建設(shè)，以物聯(lián)網(wǎng)行業(yè)項目和創(chuàng)新產(chǎn)品激發(fā)高校學(xué)生的創(chuàng)造力和創(chuàng)業(yè)活力，推動創(chuàng)新創(chuàng)業(yè)教育的持續(xù)開展。

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

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

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

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

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

(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

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

2017-02-26)

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

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

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