鄧璐娟,董東曉,陳欣欣
(鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院,河南 鄭州 450002)
過程挖掘技術(shù)的研究與應(yīng)用
鄧璐娟,董東曉,陳欣欣
(鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院,河南 鄭州 450002)
由于業(yè)務(wù)流程日益復(fù)雜多變,并且流程模型設(shè)計(jì)者對(duì)于業(yè)務(wù)流程的理解主觀性較強(qiáng),大多數(shù)通過人工建立的過程模型都與現(xiàn)實(shí)情況存在較大偏差,使用過程挖掘技術(shù)能夠很好地解決這一問題。針對(duì)典型的工作流系統(tǒng)中索賠事件流程的日志,對(duì)其建模流程進(jìn)行分析,使用過程挖掘工具ProM進(jìn)行挖掘得到對(duì)應(yīng)的過程模型。實(shí)驗(yàn)結(jié)果表明,通過過程挖掘技術(shù)所得到的過程模型與實(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
企業(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ù)運(yùn)作流程結(jié)合非常緊密。面對(duì)復(fù)雜的、快速多變的業(yè)務(wù)流程,工作流建模技術(shù)遇到了問題,例如,由于流程設(shè)計(jì)者對(duì)于業(yè)務(wù)流程的理解不到位,使得設(shè)計(jì)出的工作流模型與實(shí)際的業(yè)務(wù)流程存在偏差。此外,系統(tǒng)中記錄了數(shù)量眾多的事件,從這些寶貴的事件數(shù)據(jù)中提取有價(jià)值的信息也比較困難。過程挖掘技術(shù)的出現(xiàn)能很好地解決這些問題,使用過程挖掘技術(shù)進(jìn)行企業(yè)流程建模不需要依賴業(yè)務(wù)流程領(lǐng)域的專家知識(shí),只需要提供記錄這些流程的數(shù)據(jù)就能夠根據(jù)這些流程數(shù)據(jù)自動(dòng)生成對(duì)應(yīng)的過程模型,并且這種過程模型的生成方法是領(lǐng)域獨(dú)立的[1]。
通過對(duì)事件日志中的數(shù)據(jù)進(jìn)行分析提取得到過程相關(guān)的信息,從而自動(dòng)地發(fā)現(xiàn)過程模型的技術(shù)就是過程挖掘。過程挖掘涉及機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、過程建模與分析等多個(gè)領(lǐng)域的知識(shí)[1]。過程挖掘技術(shù)通過對(duì)事件日志的處理和分析發(fā)掘日志中所包含的業(yè)務(wù)過程模型,過程挖掘建立了兩種連接,一是實(shí)際過程與其數(shù)據(jù)的連接;二是實(shí)際過程與過程模型的連接。這種自動(dòng)生成過程模型的技術(shù)不僅能夠最大限度地減少建模過程中人為因素的干擾,使得過程模型與實(shí)際過程更加吻合,而且還提高了建模效率。
事件日志是進(jìn)行過程挖掘的基礎(chǔ),一份高質(zhì)量的事件日志能為過程挖掘的實(shí)施提供很多便利。如圖1所示,事件日志主要用于三種類型的過程挖掘場(chǎng)景:第一種應(yīng)用是發(fā)現(xiàn),即使用不包括任何先驗(yàn)信息的事件日志生成過程模型;第二種應(yīng)用是合規(guī)性檢查,即使用一個(gè)已知的過程模型與它產(chǎn)生的事件日志相比較,驗(yàn)證過程模型是否與日志中的實(shí)際情況相吻合;第三種應(yīng)用是改進(jìn),其理念是利用實(shí)際過程產(chǎn)生的事件日志來擴(kuò)展或改進(jìn)一個(gè)已經(jīng)存在的過程。
圖1 三種主要的過程挖掘場(chǎng)景
表1中顯示了處理索賠申請(qǐng)過程所對(duì)應(yīng)的一個(gè)可能日志的一部分,每一行代表一個(gè)事件,事件按照不同的案例進(jìn)行分組。在具體的挖掘過程中只用到了事件日志中的部分信息,過程挖掘的最低要求是每個(gè)事件都能對(duì)應(yīng)一個(gè)案例和一個(gè)活動(dòng),并且一個(gè)案例中的事件是有序的。因此,表中的“案例ID”和“活動(dòng)”這兩個(gè)列代表了過程挖掘?qū)τ谑录罩镜淖畹鸵蟆?/p>
表1 索賠申請(qǐng)事件部分日志
在真實(shí)的工作流系統(tǒng)中,事件日志以挖掘可擴(kuò)展標(biāo)記語言(Mining eXtensible Markup Language,MXML)文件的形式保存過程挖掘工具ProM對(duì)其操作,MXML也是當(dāng)前存儲(chǔ)和交換事件日志的事實(shí)上的標(biāo)準(zhǔn)。采用IEEE Task Force on Process Mining小組定義的XES(eXtensible Event Stream)格式,則描述的事件流程的日志如下所示。
……
……
……
對(duì)這個(gè)事件,采用α算法進(jìn)行挖掘。L表示基于某個(gè)活動(dòng)集合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)在日志中的活動(dòng)(TL),這些活動(dòng)對(duì)應(yīng)著最終生成的工作流網(wǎng)中的變遷。第二步要找出開始活動(dòng)的集合TI,即在軌跡中出現(xiàn)在第一個(gè)位置的所有活動(dòng)的集合。第三步要找出結(jié)束活動(dòng)的集合TO,即在軌跡中出現(xiàn)在最后一個(gè)位置的所有活動(dòng)的集合。第四步要確定工作流網(wǎng)中的庫所以及它們之間的連接關(guān)系XL。A中任何一個(gè)元素不能緊跟同集合內(nèi)的其他元素,即對(duì)于所有的a1,a2∈A都有a1#La2,對(duì)于集合B中的元素也是同樣的要求,B中的元素都可以緊跟A中任意元素后邊,反之不然,即對(duì)于所有的(a,b)∈A×B,有a→Lb。所有滿足要求的A,B對(duì)構(gòu)成的結(jié)合就是XL。第五步是要精簡(jiǎn)庫所。如果把XL中的每個(gè)元素都作為一個(gè)庫所,庫所規(guī)模就很大,因此對(duì)庫所進(jìn)行精簡(jiǎn),只保留“最大的”(A,B),即(A′,B′)記為YL。第四步和第五步是α算法的核心。第六步是要得到庫所PL。每一個(gè)元素(A,B)∈YL都對(duì)應(yīng)著一個(gè)庫所P(A,B),這個(gè)庫所連接了A和B中的變遷,此外,PL還包含一個(gè)唯一的源庫所iL和一個(gè)唯一的匯結(jié)庫所oL。第七步是要生成工作流網(wǎng)中的弧。TI中的所有變遷都以iL作為輸入庫所,TO中的所有變遷都以oL作為輸出庫所。所有P(A,B)都以A作為輸入節(jié)點(diǎn),以B作為輸出節(jié)點(diǎn)。最終得到一個(gè)Petri網(wǎng)α(L)=(PL,TL,FL)如圖2所示。
圖2 α算法挖掘結(jié)果
從4個(gè)維度來衡量挖掘算法的質(zhì)量,即擬合度(fitness)、精確度(precision)、泛化度(generalization)和簡(jiǎn)潔度(simplicity)。擬合度是指得到的過程模型應(yīng)該允許事件日志所反映的行為發(fā)生,一個(gè)擬合度良好的模型能夠重演日志中大部分軌跡;精確度是指得到的過程模型不應(yīng)該允許與事件日志中所反映的行為完全無關(guān)的行為出現(xiàn);泛化度是指得到的過程模型應(yīng)該泛化事件日志中的行為例子;簡(jiǎn)潔度是指得到的過程模型應(yīng)該越簡(jiǎn)單越好。這4個(gè)質(zhì)量標(biāo)準(zhǔn)是相互競(jìng)爭(zhēng)的,因此在這4個(gè)標(biāo)準(zhǔn)間取得平衡是一項(xiàng)挑戰(zhàn)。α算法雖然不能很好地滿足這4個(gè)質(zhì)量標(biāo)準(zhǔn),但是α算法是更高級(jí)的挖掘方法的基礎(chǔ)。
1995年COOK J E等人第一次提出了過程挖掘的概念,并且提出了RNet、KTail和Markov三種過程挖掘算法[2-3],挖掘出的過程模型用有限狀態(tài)機(jī)表示;德國(guó)的HERBST J等人[4]提出了三個(gè)能夠處理重復(fù)任務(wù)的算法,分別為:MergeSeq、SplitSeq以及SplitPar。荷蘭Eindhoven大學(xué)教授AALST W V D的團(tuán)隊(duì)和國(guó)際其他機(jī)構(gòu)及院校合作,取得了一系列的成果[5-8],在挖掘算法方面,提出了α算法、啟發(fā)式挖掘算法以及區(qū)域挖掘算法等優(yōu)秀算法;于2004年研發(fā)出開源過程挖掘工具ProM,發(fā)展到今天ProM已經(jīng)集成了幾百個(gè)過程挖掘與分析插件,成為過程挖掘的事實(shí)標(biāo)準(zhǔn)。AALST W V D為過程挖掘的研究奠定了理論和實(shí)踐基礎(chǔ),極大地推動(dòng)了過程挖掘技術(shù)的發(fā)展。
國(guó)內(nèi)過程挖掘的研究起步較晚,但也取得了一些顯著的成果。清華大學(xué)范玉順教授是國(guó)內(nèi)過程建模領(lǐng)域較早的研究者,針對(duì)目前工作流管理系統(tǒng)在描述能力和柔性上存在的嚴(yán)重不足,通過擴(kuò)展傳統(tǒng)活動(dòng)網(wǎng)絡(luò)模型,提出了一種基于協(xié)調(diào)理論和反饋機(jī)制的新的過程建模方法[9-10]。清華大學(xué)王建民教授在文獻(xiàn)[11-13]中指出過程挖掘的研究迅速發(fā)展,各種挖掘算法不斷出現(xiàn),但是過程挖掘數(shù)據(jù)集和過程挖掘算法評(píng)判卻沒有統(tǒng)一標(biāo)準(zhǔn)。為此,王建民教授提出了一種針對(duì)不同應(yīng)用需求選擇過程挖掘算法的框架。針對(duì)α算法的不足,清華大學(xué)的聞立杰進(jìn)行了擴(kuò)展和改進(jìn)[14-15],提出的α++算法、α#算法以及β算法,突破了非自由選擇結(jié)構(gòu)、不可見任務(wù)這兩大開放性過程挖掘的問題。文獻(xiàn)[16-18]中針對(duì)現(xiàn)有成批處理工作流調(diào)度方法的不足,利用微粒群算法的智能優(yōu)化原理,提出一種動(dòng)態(tài)分組調(diào)度優(yōu)化模型;為了解決了現(xiàn)有工作流挖掘方法無法挖掘出工作流實(shí)例方面模型的問題,通過分析描述了業(yè)務(wù)過程實(shí)際執(zhí)行情況的事件日志中活動(dòng)輸入輸出等數(shù)據(jù)的特點(diǎn),提出了一種基于工作流網(wǎng)的工作流實(shí)例方面模型挖掘方法。
過程挖掘作為一個(gè)新興技術(shù)領(lǐng)域在當(dāng)前的研究中存在下面一些困難與挑戰(zhàn):
(1)對(duì)于復(fù)雜結(jié)構(gòu)和特殊結(jié)構(gòu)的挖掘。雖然啟發(fā)式挖掘算法能夠處理不完備的日志和日志中的噪音,但對(duì)于日志中存在的重復(fù)或孤立的活動(dòng)以及特殊循環(huán)結(jié)構(gòu)還不能很好地處理。文獻(xiàn)[19-20]中基于啟發(fā)式算法做了一些改進(jìn),使之對(duì)特殊復(fù)雜結(jié)構(gòu)的挖掘能力有一定的提升。
(2)對(duì)于挖掘結(jié)果的驗(yàn)證困難。通過挖掘算法得到的結(jié)果要進(jìn)行交叉驗(yàn)證,交叉驗(yàn)證的問題之一就是缺少反例,也就是說日志只提供了可能發(fā)生的行為,但卻沒有提供不可能發(fā)生的行為。文獻(xiàn)[21-22]提供一種可能的解決方案,即插入人工生成的反面事件。
(3)在線過程挖掘(比如提供預(yù)測(cè)和推薦)。隨著云計(jì)算和大數(shù)據(jù)技術(shù)的發(fā)展以及計(jì)算能力的提升,人們對(duì)于數(shù)據(jù)實(shí)時(shí)性的要求越來越高,所以在線過程挖掘?qū)?huì)是過程挖掘的一個(gè)重要發(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é)報(bào), 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] 文一憑. 工作流實(shí)例方面的調(diào)度與挖掘方法研究[D]. 長(zhǎng)沙:中南大學(xué), 2013.
[17] 陳志剛, 文一憑, 康國(guó)勝. 成批處理工作流動(dòng)態(tài)分組調(diào)度優(yōu)化方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2012, 18(8):1693-1699.
[18] 文一憑, 劉潔. 工作流模型挖掘算法及其應(yīng)用研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2008, 18(7):93-95.
[19] 魯法明, 曾慶田, 段華,等. 一種并行化的啟發(fā)式流程挖掘算法[J]. 軟件學(xué)報(bào), 2015, 26(3):533-549.
[20] 朱銳, 李彤, 莫啟,等. 啟發(fā)式并行化單觸發(fā)序列挖掘算法[J]. 計(jì)算機(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] 石杰. 云計(jì)算環(huán)境下的數(shù)據(jù)挖掘應(yīng)用[J]. 微型機(jī)與應(yīng)用, 2015, 34(5):13-15.
2017 TI杯全國(guó)大學(xué)生物聯(lián)網(wǎng)設(shè)計(jì)競(jìng)賽完美收官
2017年9月15日,無錫訊——由教育部高等學(xué)校計(jì)算機(jī)類專業(yè)教學(xué)指導(dǎo)委員會(huì)主辦,全球領(lǐng)先模擬和嵌入式處理半導(dǎo)體廠商德州儀器(TI)(NASDAQ: TXN)協(xié)辦的“2017 TI杯全國(guó)大學(xué)生物聯(lián)網(wǎng)設(shè)計(jì)競(jìng)賽”(以下簡(jiǎn)稱“競(jìng)賽”)決賽日前于無錫完美收官。
TI杯全國(guó)大學(xué)生物聯(lián)網(wǎng)設(shè)計(jì)競(jìng)賽迄今已成功舉辦四屆,旨在以學(xué)科競(jìng)賽推動(dòng)專業(yè)建設(shè),以物聯(lián)網(wǎng)行業(yè)項(xiàng)目和創(chuàng)新產(chǎn)品激發(fā)高校學(xué)生的創(chuàng)造力和創(chuàng)業(yè)活力,推動(dòng)創(chuàng)新創(chuàng)業(yè)教育的持續(xù)開展。
本次競(jìng)賽共吸引了來自國(guó)內(nèi)500余所高校的1 500多支代表隊(duì)、1 700余名指導(dǎo)教師和6 500余名學(xué)生的積極報(bào)名參賽。經(jīng)過線上預(yù)賽和華東、華中及西南、東北、華北和西北的全國(guó)5個(gè)分賽區(qū)的激烈角逐,共有120支團(tuán)隊(duì)入圍全國(guó)總決賽。最終,來自哈爾濱工業(yè)大學(xué)的Hit Elites團(tuán)隊(duì)?wèi){借“Mr. Piano-遠(yuǎn)程鍵盤樂器教學(xué)系統(tǒng)”項(xiàng)目脫穎而出,斬獲本屆TI杯特等獎(jiǎng)。
此外,本屆大賽增設(shè)了線上投票環(huán)節(jié),經(jīng)過緊張激烈的6小時(shí)投票與互動(dòng),來自深圳大學(xué)-小白智能團(tuán)隊(duì)的“基于CC3200和DLP技術(shù)的智能魚缸”、南京工業(yè)大學(xué)-InnoDrive團(tuán)隊(duì)的“汽車輔助駕駛系統(tǒng)”以及北京理工大學(xué)-503團(tuán)隊(duì)的“基于CC3200的聲音定位智能嬰兒車”三個(gè)設(shè)計(jì)作品榮獲本屆TI杯最佳人氣獎(jiǎng)。
萬物相連已不是夢(mèng)想,隨著科技腳步日新月異,物聯(lián)網(wǎng)正以成倍的速度發(fā)展中。作為最早進(jìn)軍物聯(lián)網(wǎng)市場(chǎng)的全球性半導(dǎo)體設(shè)計(jì)制造公司之一, TI已成為可為物聯(lián)網(wǎng)應(yīng)用提供廣泛模塊芯片的供應(yīng)商——從節(jié)點(diǎn)到網(wǎng)關(guān)再到云端,TI提供眾多的產(chǎn)品及解決方案,包括微控制器、處理器、有線/無線連接、傳感器、信號(hào)鏈和電源管理解決方案等。
TI一直積極參與到物聯(lián)網(wǎng)工程專業(yè)的學(xué)科建設(shè)中。目前,TI已經(jīng)在600多所大學(xué)中建立了超過3 000個(gè)數(shù)字信號(hào)處理、模擬及微控制器實(shí)驗(yàn)室,每年有超過30萬名學(xué)生通過TI的實(shí)驗(yàn)室和各類活動(dòng)進(jìn)行實(shí)踐。在本次物聯(lián)網(wǎng)設(shè)計(jì)競(jìng)賽中,TI向各參賽隊(duì)提供了7種物聯(lián)網(wǎng)設(shè)計(jì)套件,包括TI CC3200 LaunchPad開發(fā)板、CC2650 LaunchPad開發(fā)板和CC2650STK套件等。同時(shí),TI還提供了TI Design參考設(shè)計(jì)、無線技術(shù)選型指南、傳感器方案、MCU選擇參考、電池管理設(shè)計(jì)參考等豐富的資源,參賽隊(duì)伍在作品中可使用TI的設(shè)計(jì)套件,完成創(chuàng)意滿分的物聯(lián)網(wǎng)設(shè)計(jì)。
在TI的全球戰(zhàn)略中,大學(xué)計(jì)劃是極為重要的組成部分。今年是TI大學(xué)計(jì)劃進(jìn)入中國(guó)的第21年,TI仍將不遺余力地在全球范圍內(nèi)推行大學(xué)計(jì)劃,通過這個(gè)孕育科學(xué)技術(shù)人才的搖籃,與自身技術(shù)創(chuàng)新發(fā)展相結(jié)合,培養(yǎng)更多掌握世界先進(jìn)技術(shù)的高級(jí)專業(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].微型機(jī)與應(yīng)用,2017,36(18):11-14,17.
2017-02-26)
鄧璐娟(1964-),女,博士,教授,主要研究方向:軟件工程、工作流建模。
董東曉(1991-),男,碩士,主要研究方向:軟件工程、工作流建模。
陳欣欣(1993-),女,碩士,主要研究方向:軟件工程。