林文祥,劉德生
(航天工程大學(xué) 復(fù)雜電子系統(tǒng)仿真重點(diǎn)實(shí)驗(yàn)室,北京 101400)
流程挖掘是一門新興的交叉學(xué)科,起源于軟件工程領(lǐng)域.起初,軟件設(shè)計(jì)者只能根據(jù)業(yè)務(wù)設(shè)計(jì)師和業(yè)務(wù)管理者的相關(guān)介紹對(duì)工作流程進(jìn)行建模,容易導(dǎo)致流程模型具有主觀性和片面性,無(wú)法客觀反映客戶對(duì)軟件的真實(shí)需求;此外,由于業(yè)務(wù)實(shí)際運(yùn)轉(zhuǎn)過(guò)程中的不確定性,容易導(dǎo)致真實(shí)的業(yè)務(wù)流程與事先建好的流程模型存在差異,難以借助模型分析和優(yōu)化真實(shí)的業(yè)務(wù)流程.流程挖掘技術(shù)應(yīng)運(yùn)而生,被認(rèn)為是解決這一問(wèn)題的可行方案,即使用系統(tǒng)的實(shí)際運(yùn)行事件日志數(shù)據(jù),通過(guò)流程發(fā)現(xiàn)、驗(yàn)證等方法,構(gòu)建真實(shí)的業(yè)務(wù)流程模型,用于指導(dǎo)真實(shí)業(yè)務(wù)流程的分析和優(yōu)化[1].
流程挖掘的概念自1998年首次被提出以來(lái),相關(guān)技術(shù)發(fā)展迅速,其算法研究更是熱點(diǎn)之一.在20 余年的時(shí)間里,流程挖掘的新算法和改進(jìn)算法層出不窮.本文對(duì)流程挖掘算法進(jìn)行統(tǒng)計(jì)學(xué)分析,探討了算法研究的總體情況和發(fā)展趨勢(shì);基于算法特性將流程挖掘算法分為傳統(tǒng)算法和基于計(jì)算智能和機(jī)器學(xué)習(xí)技術(shù)的算法,對(duì)其中主要算法進(jìn)行簡(jiǎn)要介紹和對(duì)比分析,并提出下一步改進(jìn)措施.
選取Web of Science (WoS)核心合集作為分析流程挖掘總體現(xiàn)狀的數(shù)據(jù)來(lái)源,設(shè)置檢索的時(shí)間跨度為1998-2020年,設(shè)置檢索條件式為“Topic=‘process mining’”and “Topic=‘Algorithm’”,共檢索出文獻(xiàn)7 085 篇.
圖1是將檢索的7 085 篇有關(guān)流程挖掘算法的文獻(xiàn)按照發(fā)文年份進(jìn)行統(tǒng)計(jì)分析,由圖可知,在流程挖掘發(fā)展之初,大約2010年之前,有關(guān)算法文章的研究和發(fā)表呈現(xiàn)平穩(wěn)姿態(tài),數(shù)目位于100-200 之間,表明這一時(shí)間是流程挖掘領(lǐng)域的奠基階段,研究發(fā)現(xiàn)許多經(jīng)典算法誕生于此時(shí)間段內(nèi);在2010年之后,每年算法的發(fā)文數(shù)量呈現(xiàn)指數(shù)型增長(zhǎng),在最近兩年,年增長(zhǎng)數(shù)目均在200 以上,表明了當(dāng)前流程挖掘算法研究正處于爆發(fā)期.
圖1 1998-2020年外文文獻(xiàn)年度趨勢(shì)
運(yùn)用CiteSpace[2]對(duì)WoS 數(shù)據(jù)源的文獻(xiàn)資料進(jìn)行分析.上述7 085 篇文獻(xiàn)經(jīng)去重得到6 863 篇獨(dú)立文獻(xiàn),分析得到突現(xiàn)關(guān)鍵詞116 個(gè),其中與算法相關(guān)的關(guān)鍵詞58 個(gè).算法突現(xiàn)詞從一定層面上可以反映在某段時(shí)間內(nèi)的研究熱點(diǎn),甚至可以表明某一算法提出的時(shí)間,比如evolutionary algorithm,其突現(xiàn)時(shí)間是2007-2010年,這也是遺傳挖掘提出并引發(fā)相關(guān)熱點(diǎn)的時(shí)候,再比如與模糊挖掘相關(guān)的關(guān)鍵詞Fuzzy 突現(xiàn)時(shí)間為2008-2010年,這也與模糊挖掘算法提出時(shí)間接近.此外突現(xiàn)詞數(shù)量眾多反映出流程挖掘相關(guān)研究自1998年發(fā)展至今,算法提出和改進(jìn)的相關(guān)研究非常多,尤其是2010年以來(lái)表現(xiàn)得更加活躍;突現(xiàn)強(qiáng)度前30的關(guān)鍵詞如表1所示,其中排名靠前的關(guān)鍵詞均與人工智能等前沿領(lǐng)域相關(guān),相關(guān)算法在2019年左右開(kāi)始突現(xiàn),表明與deep learning、machine learning、artificial intelligence 等領(lǐng)域的結(jié)合已成為近兩年來(lái)流程挖掘算法研究的熱點(diǎn).
表1 1998-2020年排名前30 算法突現(xiàn)詞
目前算法的分類方式主要有以下4 種:(1) 根據(jù)流程挖掘結(jié)果輸出的模型表示方式對(duì)算法進(jìn)行分類;(2) 基于應(yīng)用領(lǐng)域?qū)λ惴ㄟM(jìn)行分類;(3) 基于算法特性進(jìn)行分類;(4) 按照時(shí)間順序介紹算法.由于第3 種分類方式具有交叉性小、算法特點(diǎn)明顯等優(yōu)勢(shì),所以本文采取基于算法特性的分類方式,將流程挖掘領(lǐng)域算法分為兩大類,分別是傳統(tǒng)算法和基于計(jì)算智能和機(jī)器學(xué)習(xí)技術(shù)的算法,并對(duì)其中骨干算法進(jìn)行簡(jiǎn)短介紹.
流程挖掘傳統(tǒng)算法的主要特點(diǎn)是具有嚴(yán)密的邏輯推理和因果關(guān)系,提出時(shí)間較早且發(fā)展較為成熟,主要包括直接算法、啟發(fā)式算法和基于概率統(tǒng)計(jì)的算法.
直接算法的基本思想是直接對(duì)事件日志進(jìn)行全盤掃描,從中找出具有特定規(guī)律的模式.α算法和相關(guān)改進(jìn)算法是此類方法的典型代表[3-7].
以α算法[3]為例.α算法首先基于日志定義了4 種活動(dòng)間的次序關(guān)系(以同一日志W(wǎng)中的活動(dòng)a和b為例),分別是伴隨關(guān)系a>W(wǎng)b、因果關(guān)系a→Wb、并行關(guān)系a||Wb和無(wú)關(guān)關(guān)系a#Wb;接著根據(jù)4 種次序關(guān)系進(jìn)一步構(gòu)造5 種控制流結(jié)構(gòu),分別是順序模式、選擇分叉模式、選擇合并模式、并行分叉模式和并行合并模式.
圖2即為5 種控制流結(jié)構(gòu)Petri 網(wǎng)的表現(xiàn)形式,其中,圖2(a)是順序結(jié)構(gòu),要求滿足的次序關(guān)系是a→Wb;圖2(b)是選擇分叉結(jié)構(gòu),要求滿足的次序關(guān)系是a→Wb,a→Wc并且b#Wc;圖2(c)是選擇合并結(jié)構(gòu),要求滿足的次序關(guān)系是a→Wc,b→Wc,并且a#Wb;圖2(d)是并行分叉結(jié)構(gòu),要求滿足的次序關(guān)系是a→Wb,a→Wc,并且b||Wc;圖2(e)是并行合并結(jié)構(gòu),要求滿足的次序關(guān)系是a→Wc,b→Wc并且a||Wb.α算法分類得到事件日志中各活動(dòng)間關(guān)系,在5 種控制流結(jié)構(gòu)的基礎(chǔ)上,輸出完整的以工作流網(wǎng)為表示形式的流程模型.
圖2 α 算法中的典型控制流結(jié)構(gòu)
α算法的提出促進(jìn)了流程挖掘的快速發(fā)展,目前仍是流程挖掘領(lǐng)域的主流算法之一.但是,因?yàn)樵撍惴ú荒芴幚韼в蟹亲杂蛇x擇結(jié)構(gòu)、短循環(huán)結(jié)構(gòu)、重復(fù)任務(wù)和不可見(jiàn)任務(wù)等復(fù)雜結(jié)構(gòu)的流程模型,很多學(xué)者基于α算法做了深入研究并提出改進(jìn)措施.其中,α+算法[4]可用于處理流程模型中具有長(zhǎng)度為1 或2的短循環(huán)結(jié)構(gòu);α++算法[5]則能發(fā)現(xiàn)依賴關(guān)系大于1的隱式依賴關(guān)系;α#算法[6]針對(duì)的是隱式變遷問(wèn)題;α*算法[7]則是可以處理重復(fù)活動(dòng).到目前未止還沒(méi)有一種可以綜合上述所有優(yōu)點(diǎn)的成熟的算法,文獻(xiàn)[8]在此方面做了有益的探索和嘗試,使α算法初步具備同時(shí)處理多種復(fù)雜結(jié)構(gòu)的能力.
α算法的應(yīng)用需要一個(gè)重要前提,即日志完備且沒(méi)有噪聲.噪聲指的是記錄錯(cuò)誤的日志數(shù)據(jù)或者流程執(zhí)行出現(xiàn)異常所記錄的數(shù)據(jù),這在流程實(shí)際運(yùn)行的時(shí)候必然會(huì)出現(xiàn).為解決流程挖掘中的日志噪聲問(wèn)題,研究人員提出了啟發(fā)式算法[9,10].
噪聲日志是指出現(xiàn)頻次明顯低于其他行為的特定行為[11],這是基于流程運(yùn)行的穩(wěn)定性的一種假設(shè),即噪聲日志在正確日志中所占比例很小.啟發(fā)式算法的基本思想是基于此基本假設(shè),在挖掘事件日志時(shí),考慮流程實(shí)例出現(xiàn)的頻率,從概率統(tǒng)計(jì)的角度識(shí)別噪聲,通過(guò)設(shè)定閾值,將低頻實(shí)例作為噪聲過(guò)濾掉.文獻(xiàn)[9]首次提出了啟發(fā)式挖掘算法,其基本思想是在挖掘事件日志時(shí),使用頻率來(lái)刻畫(huà)一對(duì)活動(dòng)之間因果關(guān)系的強(qiáng)度,并以依賴度度量,通過(guò)事件日志中不同活動(dòng)之間的連接數(shù)計(jì)算得到依賴度,依賴度低于某個(gè)閾值的日志即視為噪聲,將之過(guò)濾后輸出相應(yīng)的控制流結(jié)構(gòu)形成流程模型.文獻(xiàn)[10]對(duì)啟發(fā)式挖掘步驟進(jìn)行了詳細(xì)介紹,可總結(jié)如下.
1) 挖掘依賴圖.其中包括計(jì)算活動(dòng)間依賴度,形成活動(dòng)依賴表,再設(shè)定閾值構(gòu)造活動(dòng)間依賴圖.圖3(a)是一個(gè)構(gòu)造的依賴圖的例子[12],其中活動(dòng)用字母代替,活動(dòng)間關(guān)系用有向弧表示,并在相應(yīng)有向弧標(biāo)明活動(dòng)間的依賴關(guān)系,此環(huán)節(jié)中低頻噪聲已通過(guò)閾值被過(guò)濾.
圖3 C-net 構(gòu)造過(guò)程
2) 在依賴圖基礎(chǔ)上確定并行和選擇分支,通過(guò)定義并行選擇結(jié)構(gòu)判斷的計(jì)算公式a?Wb∧c=和設(shè)定閾值,當(dāng)計(jì)算值小于某一閾值時(shí)被當(dāng)作選擇結(jié)構(gòu)處理,大于某一閾值時(shí)則被當(dāng)作并行結(jié)構(gòu)處理.圖3(b)是構(gòu)建成功的一個(gè)C-net 例子,在依賴圖的基礎(chǔ)上對(duì)選擇或并行關(guān)系進(jìn)行了標(biāo)識(shí)[12].
啟發(fā)式算法在應(yīng)對(duì)噪聲問(wèn)題上走出了創(chuàng)新的一步,但基于頻率閾值的對(duì)低頻事件一刀切也會(huì)導(dǎo)致錯(cuò)誤刪除有效的低頻行為,已有學(xué)者考慮這個(gè)問(wèn)題后提出了一些解決方法.就目前而言,在針對(duì)噪聲處理問(wèn)題上啟發(fā)式思想仍是主流,并未出現(xiàn)更多可供選擇的噪聲處理方法.
此類算法是概率統(tǒng)計(jì)相關(guān)算法在流程挖掘中的應(yīng)用,具有明顯的或潛在的概率模型,揭示了特定數(shù)據(jù)點(diǎn)之間的相關(guān)性概率,與流程挖掘需要得到活動(dòng)連接概率、現(xiàn)象發(fā)生頻率等契合度高,因此在流程挖掘領(lǐng)域發(fā)揮重要作用.常見(jiàn)于流程挖掘領(lǐng)域的概率統(tǒng)計(jì)算法有:馬爾可夫(Markov)模型[13],隨機(jī)活動(dòng)圖(SAG)算法[14],增量分析[15],Apriori 算法[16,17],隨機(jī)Petri 網(wǎng)等.
馬爾可夫模型[13]是一個(gè)具有無(wú)后效性的隨機(jī)過(guò)程,表示系統(tǒng)從一個(gè)狀態(tài)n轉(zhuǎn)移到另一種狀態(tài)n+1 只取決于系統(tǒng)在n時(shí)刻的狀態(tài),即未來(lái)狀態(tài)的選擇僅與系統(tǒng)當(dāng)前狀態(tài)相關(guān),而與之前的狀態(tài)無(wú)關(guān),并將系統(tǒng)從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的概率稱之為狀態(tài)轉(zhuǎn)移概率.業(yè)務(wù)流程也可看作一個(gè)隨機(jī)過(guò)程,它描述了系統(tǒng)從一個(gè)任務(wù)狀態(tài)到另一個(gè)任務(wù)狀態(tài).由于流程的任務(wù)在時(shí)間t具有任務(wù)狀態(tài),因此業(yè)務(wù)流程被視為具有有限狀態(tài)的馬爾可夫鏈,文獻(xiàn)[13]設(shè)計(jì)了一種基于馬爾可夫轉(zhuǎn)移矩陣的自動(dòng)業(yè)務(wù)流程建模方法,可推導(dǎo)任務(wù)間所有可能的邏輯關(guān)系且不受日志質(zhì)量影響.
隨機(jī)活動(dòng)圖(SAG)[14]是有著明確定義的元組,包括節(jié)點(diǎn)、邊、活動(dòng)、活動(dòng)分配函數(shù)、轉(zhuǎn)移概率、開(kāi)始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn),由于隨機(jī)活動(dòng)圖和工作流模型的基本元素都是活動(dòng),可用隨機(jī)活動(dòng)圖的構(gòu)建方式發(fā)現(xiàn)日志中活動(dòng)關(guān)系.文獻(xiàn)[14]通過(guò)對(duì)SAG 活動(dòng)節(jié)點(diǎn)和工作流實(shí)例的節(jié)點(diǎn)進(jìn)行映射,并要求SAG 活動(dòng)尊重實(shí)例活動(dòng)之間的時(shí)間依賴性,用隨機(jī)活動(dòng)圖作為工作流模型的中間表現(xiàn)形式,再進(jìn)行工作流模型轉(zhuǎn)換.
與α算法和啟發(fā)式算法專注于流程發(fā)現(xiàn)不同,概率統(tǒng)計(jì)算法可用在流程挖掘的優(yōu)化方面,如利用Apriori算法進(jìn)行關(guān)聯(lián)規(guī)則挖掘[18],從而找出高效的工作組合;再比如利用Markov 模型的兩個(gè)活動(dòng)先后發(fā)生概率得到流程執(zhí)行的路由概率,從而檢測(cè)流程是否異常[19].概率統(tǒng)計(jì)方法識(shí)別流程模型中的缺陷和問(wèn)題應(yīng)用較為廣泛.
此類流程算法主要來(lái)自于數(shù)據(jù)挖掘相關(guān)技術(shù)在流程挖掘領(lǐng)域的應(yīng)用,相比于傳統(tǒng)流程挖掘算法,此類技術(shù)的整體成熟性還不夠,大部分還未能達(dá)到很好的挖掘效果,但興盛的計(jì)算智能和機(jī)器學(xué)習(xí)浪潮未必不能給流程挖掘領(lǐng)域帶來(lái)不一樣的前進(jìn)方向.
智能優(yōu)化算法在流程挖掘領(lǐng)域具有天然的優(yōu)勢(shì),一是可以處理大多數(shù)的控制流結(jié)構(gòu),并且挖掘結(jié)果具有很高準(zhǔn)確率;二是算法魯棒性好,可以很好地處理噪聲;三是基于局部次序關(guān)系的全局搜索,有利于得到全局優(yōu)化的結(jié)果;四是適應(yīng)度函數(shù)的自由設(shè)置,便于得到更符合用戶傾向的流程模型.常見(jiàn)的在流程挖掘中使用的搜索算法有:遺傳算法[20]、模擬退火算法[21]、禁忌搜索算法[22]、和粒子群[23]等.
智能優(yōu)化算法的基本框架[22]如圖4所示.
圖4 智能優(yōu)化算法基本框架
(1)智能優(yōu)化算法的初始化.算法初始化要考慮兩個(gè)方面因素:一是算法本身原理,如遺傳算法需要生成初始種群,而模擬退火算法和禁忌搜索算法僅需生成一個(gè)初始個(gè)體;二是要考慮流程挖掘的特點(diǎn),主要就是如何表示各流程個(gè)體以適應(yīng)于智能優(yōu)化技術(shù),可采用因果矩陣或Petri 網(wǎng)等表現(xiàn)形式.
(2)計(jì)算流程模型的適應(yīng)度.適應(yīng)度是判斷算法停止的主要依據(jù),流程模型的適應(yīng)度主要參考4 個(gè)評(píng)價(jià)指標(biāo):擬合度、泛化度、精確度和簡(jiǎn)單度,四者相互制約,從中尋求平衡是難點(diǎn).
(3)智能優(yōu)化算法停止的條件.算法停止條件可自行定義,常用的有:一是適應(yīng)度函數(shù)若干輪計(jì)算后達(dá)到預(yù)設(shè)數(shù)值,二是算法的循環(huán)次數(shù)達(dá)到設(shè)定的上限,三是適應(yīng)度函數(shù)的值經(jīng)歷若干次計(jì)算未發(fā)生變化或變化量小于設(shè)定閾值等.
(4)智能優(yōu)化算法的尋優(yōu)操作.該步驟是智能優(yōu)化算法在流程挖掘領(lǐng)域應(yīng)用的核心步驟,目的是通過(guò)尋優(yōu)操作提升個(gè)體或群體的適應(yīng)度.不同算法尋優(yōu)方式不同,需要把流程挖掘任務(wù)中的概念根據(jù)算法進(jìn)行抽象,對(duì)算法進(jìn)行適應(yīng)性修改.例如基于遺傳算法的流程挖掘算法,在抽象個(gè)體表示為因果矩陣后,需要對(duì)針對(duì)基因的交叉、變異和選擇等策略修改針對(duì)因果矩陣的操作,這些操作是否合理和有效將成為優(yōu)化算法輸出結(jié)果優(yōu)劣的主要影響因素.
智能優(yōu)化算法隨著計(jì)算效率的提高而越來(lái)越受追捧,這也反映了智能優(yōu)化算法的不足,即算法執(zhí)行時(shí)間過(guò)長(zhǎng),執(zhí)行效率不高,利用智能優(yōu)化算法對(duì)業(yè)務(wù)流程進(jìn)行離線分析尚還可以,但流程挖掘的發(fā)展趨勢(shì)是支持在線運(yùn)行,目前從效率來(lái)看仍有較大差距.
傳統(tǒng)流程挖掘技術(shù)有很多顯現(xiàn)或者隱含的假設(shè),使其在結(jié)構(gòu)化流程上表現(xiàn)良好,但應(yīng)用于結(jié)構(gòu)化程度低的流程,無(wú)法提供具有洞察力的模型.這不是說(shuō)傳統(tǒng)技術(shù)挖掘的模型不正確,而是挖掘的模型顯示了所有細(xì)節(jié),沒(méi)有從事件日志本身提供任何有意義的抽象,因此對(duì)于流程分析師來(lái)說(shuō)是無(wú)用的.模糊挖掘技術(shù)[24]就是針對(duì)此類現(xiàn)象,實(shí)現(xiàn)了流程模型的挖掘和自適應(yīng)簡(jiǎn)化,其基本步驟如下:
(1)首先創(chuàng)建初始模型
將日志中的所有事件類型都被轉(zhuǎn)換為活動(dòng)節(jié)點(diǎn),其重要性由一元重要性來(lái)表示.對(duì)于事件類之間的優(yōu)先關(guān)系,采用相應(yīng)的有向邊進(jìn)行連接.這條邊由二元重要性和相關(guān)性來(lái)描述.
(2)將下列3 種轉(zhuǎn)換方法應(yīng)用于流程模型,依次簡(jiǎn)化流程模型的特定方面.
1) 二元關(guān)系中的沖突解決
若活動(dòng)A發(fā)生后執(zhí)行B,定義A對(duì)于B的相對(duì)重要性為rel(A,B),同理B對(duì)于A的相對(duì)重要性為rel(B,A),根據(jù)相對(duì)重要性處理3 種沖突情況.
一是兩個(gè)沖突關(guān)系rel(A,B)和rel(B,A)的相對(duì)重要性均超過(guò)先前設(shè)定的保留閾值,則A→B和B→A都將被保留;二是至少一個(gè)沖突關(guān)系的相對(duì)重要性低于該閾值,計(jì)算確定兩個(gè)關(guān)系的相對(duì)重要性之間的偏移量.如果偏移值超過(guò)先前設(shè)定的比率閾值,則移除不重要的邊;三是至少一個(gè)關(guān)系的相對(duì)重要性低于保留閾值,并且它們的偏移小于比率閾值,則兩個(gè)邊都從過(guò)程模型中移除.
2) 邊的過(guò)濾
如圖5所示,首先定義可配置的效用比ur,即帶有權(quán)重的考慮兩活動(dòng)之間的二元重要性和二元相關(guān)性,計(jì)算得到有效選取值 Util.后進(jìn)行歸一化得到Normal Util.,再與設(shè)定參數(shù)刪除值Co相比較,刪除小于閾值的邊.
圖5 過(guò)濾節(jié)點(diǎn)A 輸入邊的過(guò)程
3) 節(jié)點(diǎn)聚合和抽象
借鑒數(shù)據(jù)挖掘中的模糊聚類方法,模糊挖掘提出了結(jié)點(diǎn)聚集的方法,對(duì)于流程模型中重要性較低但是相關(guān)性卻很高的多個(gè)結(jié)點(diǎn)采用聚集的方式,同時(shí)基于結(jié)點(diǎn)參數(shù)刪除值的大小移除孤立且重要性低的結(jié)點(diǎn)[25].
模糊挖掘技術(shù)對(duì)于解決傳統(tǒng)流程挖掘技術(shù)挖掘的“意大利面式”的流程模型具有顯著的作用,在發(fā)現(xiàn)開(kāi)發(fā)人員編碼過(guò)程[26]和查找惡意軟件[27]等方面發(fā)揮了作用.模糊挖掘算法針對(duì)不同的事件日志可通過(guò)配置合理參數(shù)得到有效的流程模型,從適用范圍來(lái)講較大.但優(yōu)點(diǎn)也是缺點(diǎn),針對(duì)不同的應(yīng)用場(chǎng)景,如何找到正確的參數(shù)是一件耗時(shí)耗力的事.模糊挖掘的發(fā)展需要得到高適應(yīng)性的默認(rèn)參數(shù)設(shè)置或易操作的合理參數(shù)尋找方式,提高算法在實(shí)際應(yīng)用中的可使用性.
事件日志中包含著大量的事件屬性信息,如時(shí)間戳、執(zhí)行者和一些附加數(shù)據(jù)等,目前的流程挖掘算法更多的是利用前兩個(gè)屬性來(lái)構(gòu)造反映因果相關(guān)性的流程模型,即基于控制流視角的流程發(fā)現(xiàn),而對(duì)日志中其他數(shù)據(jù)利用較少,無(wú)法解釋活動(dòng)為何被選擇執(zhí)行.機(jī)器學(xué)習(xí)算法[28]已經(jīng)成為從大量數(shù)據(jù)中提取知識(shí)的廣泛采用的手段,文獻(xiàn)[29]最早提出了決策挖掘的概念,通過(guò)決策樹(shù)分析技術(shù)分析日志中的各種數(shù)據(jù)信息如何影響具體的流程實(shí)例進(jìn)行決策,即得到?jīng)Q策規(guī)則,關(guān)注流程挖掘的案例視角.
決策挖掘也稱之為決策點(diǎn)分析,旨在挖掘與業(yè)務(wù)流程路由相關(guān)的數(shù)據(jù)信息.現(xiàn)有的決策挖掘算法可分為3 個(gè)步驟.
(1)使用已有控制流挖掘算法挖掘出業(yè)務(wù)流程的控制流模型.
(2)識(shí)別過(guò)程模型中的決策點(diǎn).
以Petri 網(wǎng)為例,若Petri 網(wǎng)中某一庫(kù)所對(duì)應(yīng)了多個(gè)輸出弧,則可被判定為決策點(diǎn).
(3)使用決策樹(shù)分析過(guò)程模型中的決策點(diǎn).
在對(duì)過(guò)程模型中的決策點(diǎn)進(jìn)行識(shí)別之后,需要判定過(guò)程實(shí)例的數(shù)據(jù)屬性是否對(duì)實(shí)例的決策產(chǎn)生影響,即決策規(guī)則挖掘,其思想就是將每一個(gè)決策點(diǎn)轉(zhuǎn)換為一個(gè)分類問(wèn)題,具體類別則是作出的不同決策[30].
如圖6,決策樹(shù)會(huì)構(gòu)建出一個(gè)樹(shù)狀模型.模型存在一個(gè)根節(jié)點(diǎn)、多個(gè)決策結(jié)點(diǎn)和多個(gè)葉子結(jié)點(diǎn).其中根結(jié)點(diǎn)對(duì)應(yīng)了樣本的全部數(shù)據(jù)集,而根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑則對(duì)應(yīng)一個(gè)決策序列.葉結(jié)點(diǎn)則對(duì)應(yīng)的是決策樹(shù)最后的判斷結(jié)果,決策結(jié)點(diǎn)設(shè)置數(shù)據(jù)屬性,把每個(gè)結(jié)點(diǎn)包含的樣本數(shù)據(jù)集合根據(jù)屬性測(cè)試條件分別劃分到其子節(jié)點(diǎn)中.
圖6 決策樹(shù)模型
決策樹(shù)挖掘提出來(lái)之后,很多學(xué)者針對(duì)其進(jìn)行了深入的研究和改進(jìn).文獻(xiàn)[31]針對(duì)流程日志與流程模型不一致會(huì)影響挖掘結(jié)果的問(wèn)題,提出了增加一致性檢驗(yàn)步驟;文獻(xiàn)[32]則是提出在決策點(diǎn)挖掘時(shí)同時(shí)考慮外部數(shù)據(jù)信息和內(nèi)部各決策點(diǎn)的結(jié)構(gòu)關(guān)系,提升了決策點(diǎn)決策規(guī)則挖掘的全面性和準(zhǔn)確性.決策挖掘主要針對(duì)案例視角,運(yùn)用機(jī)器學(xué)習(xí)相關(guān)技術(shù)填補(bǔ)了空白,但在實(shí)際應(yīng)用中還面臨許多難題,包括工作流日志數(shù)量好壞直接影響決策挖掘結(jié)果、非Petri 網(wǎng)模型的決策點(diǎn)挖掘等問(wèn)題,還需要更進(jìn)一步的研究探索.
前述各類流程挖掘算法的優(yōu)缺點(diǎn)如表2所示.
表2 流程挖掘算法特點(diǎn)
直接算法以α算法及其系列算法[3-7]代表,在流程挖掘發(fā)展初期誕生,發(fā)展成熟,根據(jù)活動(dòng)間依賴關(guān)系發(fā)現(xiàn)流程模型,原理清晰,計(jì)算簡(jiǎn)單,但不能處理許多復(fù)雜結(jié)構(gòu)和噪聲,后期雖有學(xué)者針對(duì)性改進(jìn),但至今仍沒(méi)有能夠處理所有復(fù)雜結(jié)構(gòu)的完善算法;啟發(fā)式算法[9,10]解決了噪聲處理問(wèn)題,基于活動(dòng)間發(fā)生頻率來(lái)去除噪聲,缺點(diǎn)是易誤刪低頻有效行為,導(dǎo)致挖掘模型不能反映實(shí)際情況;基于概率統(tǒng)計(jì)的算法[13-17]在處理特定問(wèn)題時(shí)效果顯著,可用于流程優(yōu)化或者改進(jìn)算法,缺點(diǎn)是適用范圍不大,依附性強(qiáng);基于智能優(yōu)化的流程挖掘算法[20-23]可以處理大多數(shù)的控制流結(jié)構(gòu)和噪聲,有利于得到全局的優(yōu)化結(jié)果,通過(guò)設(shè)置適應(yīng)度函數(shù)便于得到傾向性模型,不足在于算法效率太低,容易產(chǎn)生死鎖等問(wèn)題,可在質(zhì)量和效率兩方面進(jìn)行改進(jìn);模糊挖掘[24]可用于處理現(xiàn)實(shí)生活中“意大利面式”的流程模型,但需要獲得合適參數(shù)來(lái)進(jìn)行過(guò)濾,可使用性較差;決策挖掘[29]關(guān)注案例視角,發(fā)現(xiàn)流程走向的原因,便于研究人員分析,但是易受事件日志影響.
流程挖掘算法各類算法都有其優(yōu)越性,可解決特定領(lǐng)域的特定問(wèn)題,但各算法也存在著明顯短板,改進(jìn)難度大.從整體上看,流程挖掘算法發(fā)展呈現(xiàn)煙囪式,目前并無(wú)一個(gè)算法可以解決絕大多數(shù)問(wèn)題,探索之路任重而道遠(yuǎn).
流程挖掘是對(duì)客觀世界中的業(yè)務(wù)流程、工作流程、信息流程進(jìn)行發(fā)現(xiàn)、驗(yàn)證和優(yōu)化的有效手段,目前已經(jīng)成為系統(tǒng)工程和數(shù)據(jù)應(yīng)用工程的研究熱點(diǎn).流程挖掘算法是流程挖掘的核心,直接影響流程挖掘效率和挖掘結(jié)果質(zhì)量.現(xiàn)有的流程挖掘算法中,以直接算法、啟發(fā)式算法和概率統(tǒng)計(jì)算法等為代表的傳統(tǒng)算法具有執(zhí)行效率高的優(yōu)點(diǎn),但對(duì)日志噪聲、復(fù)雜結(jié)構(gòu)、有效低頻行為等問(wèn)題的處理上難以兼顧,通常需要組合運(yùn)用以達(dá)到理想效果;以智能優(yōu)化、模糊挖掘和決策挖掘等算法為代表的新型算法在處理上述問(wèn)題方面具有獨(dú)到的優(yōu)勢(shì),且更容易獲得全局優(yōu)化結(jié)果,但執(zhí)行效率會(huì)隨著挖掘算法的復(fù)雜程度而降低,在應(yīng)用時(shí)需要在挖掘效率和挖掘質(zhì)量上綜合考慮.隨著計(jì)算機(jī)算力的不斷提升,挖掘算法復(fù)雜度對(duì)執(zhí)行效率的制約將逐漸降低,基于計(jì)算智能和機(jī)器學(xué)習(xí)的挖掘算法將以其高質(zhì)量的挖掘效果成為今后流程挖掘算法的主要發(fā)展趨勢(shì).