趙海燕,李欣歌,陳慶奎,曹 健
1(上海市現(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,光學(xué)儀器與系統(tǒng)教育部工程研究中心,上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)2(上海交通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系,上海 200030)
業(yè)務(wù)過(guò)程管理[1]自上世紀(jì)90年代提出便得到了廣泛的關(guān)注,其旨在將企業(yè)工作流程標(biāo)準(zhǔn)化、高效化.業(yè)務(wù)過(guò)程管理的提出促使業(yè)務(wù)過(guò)程管理系統(tǒng)的誕生,當(dāng)前不論是企業(yè)內(nèi)部統(tǒng)一的業(yè)務(wù)過(guò)程管理系統(tǒng)還是涉及多系統(tǒng)、多部門(mén)、多企業(yè)的業(yè)務(wù)過(guò)程感知系統(tǒng)都產(chǎn)生并記錄了大量的流程執(zhí)行信息,這些信息被稱(chēng)為事件日志保存在文件或數(shù)據(jù)庫(kù)中用于過(guò)程挖掘和分析[2].例如,文獻(xiàn)[3]提出從事件序列中發(fā)現(xiàn)一般階段的過(guò)程模型算法,而文獻(xiàn)[4]提出的算法可在日志不完備的情況下挖掘過(guò)程模型.然后由挖掘出的過(guò)程模型對(duì)企業(yè)或組織的業(yè)務(wù)流程進(jìn)行分析以及改進(jìn).
現(xiàn)實(shí)世界的數(shù)據(jù)一般都是存在錯(cuò)誤、不完整的和不一致的,數(shù)據(jù)預(yù)處理技術(shù)可以改進(jìn)數(shù)據(jù)的質(zhì)量,從而有助于提高其后的挖掘過(guò)程的準(zhǔn)確率和效率[5].正如過(guò)程挖掘的經(jīng)驗(yàn)所示,大多數(shù)真實(shí)的事件日志與普通數(shù)據(jù)一樣存在各種類(lèi)型的質(zhì)量問(wèn)題,例如:事件數(shù)據(jù)可能是不完整的、有噪音的.未能解決事件日志的數(shù)據(jù)質(zhì)量問(wèn)題可能會(huì)損害分析結(jié)果的有效性.文獻(xiàn)[6]中提出了當(dāng)前過(guò)程挖掘面臨的一些重大挑戰(zhàn),其中第一個(gè)挑戰(zhàn)就是發(fā)現(xiàn)、合并和清洗事件日志數(shù)據(jù).
事件日志的質(zhì)量對(duì)于任何流程分析項(xiàng)目的成功都起著決定性的作用,因此在過(guò)程挖掘前對(duì)事件日志進(jìn)行預(yù)處理是至關(guān)重要的.目前,數(shù)據(jù)挖掘領(lǐng)域內(nèi)存在的數(shù)據(jù)預(yù)處理技術(shù)如:數(shù)據(jù)的規(guī)范化、集成、清理方法可以解決一般數(shù)據(jù)的質(zhì)量問(wèn)題.對(duì)于過(guò)程管理系統(tǒng)的事件日志來(lái)說(shuō),由于事件之間存在依賴(lài)傳遞關(guān)系和時(shí)間序列關(guān)系,而普通數(shù)據(jù)往往不存在強(qiáng)烈的依賴(lài)關(guān)系和時(shí)間關(guān)系,因此需要采用特殊的處理方法對(duì)事件日志進(jìn)行預(yù)處理.本文對(duì)近年來(lái)事件日志預(yù)處理的技術(shù)發(fā)展?fàn)顩r進(jìn)行總結(jié),并對(duì)未來(lái)的研究方向進(jìn)行展望.
日志是記錄系統(tǒng)運(yùn)行過(guò)程中各種重要信息的文件,在日志中可以快速定位系統(tǒng)運(yùn)行中所出現(xiàn)的問(wèn)題.
表1 事件日志示例片段Table 1 A sample fragment of event log
事件日志(Event Log)不同于普通的日志信息,它由過(guò)程實(shí)例(Case)組成,每個(gè)過(guò)程實(shí)例通常由可以唯一表示自身的實(shí)例標(biāo)識(shí)符所區(qū)分.過(guò)程實(shí)例由一個(gè)或多個(gè)事件(Event)組成,其中每個(gè)事件又由事件標(biāo)識(shí)符和各種屬性組成,例如:事件發(fā)生時(shí)的時(shí)間戳、事件的發(fā)起人等.過(guò)程實(shí)例中的事件構(gòu)成了執(zhí)行序列,也可稱(chēng)作執(zhí)行軌跡(Trace).表1中給出了事件日志的示例片段,其中每行代表一個(gè)事件.
事件日志數(shù)據(jù)通常有不同類(lèi)型的質(zhì)量問(wèn)題.文獻(xiàn)[7]給出了事件日志中可能出現(xiàn)的4類(lèi)過(guò)程特征問(wèn)題和27類(lèi)事件日志質(zhì)量問(wèn)題.文獻(xiàn)[8]中提出了幾種事件日志質(zhì)量問(wèn)題并給出了每個(gè)問(wèn)題幾種可行的解決方案.文獻(xiàn)[9]描述了一組從過(guò)程挖掘分析經(jīng)驗(yàn)中提煉出來(lái)的數(shù)據(jù)質(zhì)量問(wèn)題.
我們把事件日志中存在的問(wèn)題總結(jié)如下:
1)規(guī)范性問(wèn)題:目前事件日志是由各個(gè)系統(tǒng)按照各自的格式進(jìn)行保存,有的采用了文件格式,有的采用了數(shù)據(jù)庫(kù)格式.針對(duì)每一個(gè)事件的具體表達(dá),事件名、屬性表示、時(shí)間表示都存在不統(tǒng)一、不規(guī)范的問(wèn)題,這就使得挖掘和分析工具難以統(tǒng)一處理.
2)完整性問(wèn)題:該質(zhì)量問(wèn)題體現(xiàn)在兩方面,一方面真實(shí)的業(yè)務(wù)流程通常由多個(gè)信息系統(tǒng)所支持,從某一系統(tǒng)提取出來(lái)的事件日志并不反映完整的業(yè)務(wù)執(zhí)行過(guò)程.另一方面,由于人為或系統(tǒng)導(dǎo)致的各種錄入和傳輸問(wèn)題以及資源限制等原因,事件日志數(shù)據(jù)往往會(huì)在事件或事件屬性上出現(xiàn)缺失值,從而影響事件日志數(shù)據(jù)的完整性.
3)一致性問(wèn)題:為挖掘完整的業(yè)務(wù)流程,通常會(huì)將存儲(chǔ)在不同系統(tǒng)上的日志進(jìn)行合并操作.但由于不同系統(tǒng)記錄數(shù)據(jù)的方式不同,這會(huì)導(dǎo)致合并后的數(shù)據(jù)在格式、命名等方面出現(xiàn)不一致情況.
4)準(zhǔn)確性問(wèn)題:由于數(shù)據(jù)輸入或系統(tǒng)故障問(wèn)題,事件日志記錄的執(zhí)行序列中可能包含重復(fù)事件、錯(cuò)位事件、異常事件等情況.這使得事件日志無(wú)法準(zhǔn)確地表示在特定時(shí)期內(nèi)組織中執(zhí)行的業(yè)務(wù)流程的行為.
5)表示合理性問(wèn)題:許多事件日志在存儲(chǔ)時(shí)并沒(méi)有考慮對(duì)過(guò)程挖掘和分析的支持,因此經(jīng)常需要進(jìn)行各種處理才能更好地支持過(guò)程挖掘和分析.
事件日志的預(yù)處理技術(shù)就是為了提高日志數(shù)據(jù)的質(zhì)量而提出的.
由于各企業(yè)、組織使用的系統(tǒng)不盡相同,事件日志數(shù)據(jù)的存儲(chǔ)方式也各有差異,常見(jiàn)的存儲(chǔ)方式有:csv文件、數(shù)據(jù)庫(kù)表等形式.過(guò)程挖掘和分析工具都是針對(duì)特定格式的數(shù)據(jù)展開(kāi)的.因此,將原始日志格式轉(zhuǎn)換為特定格式是重要的一步.
ProM作為一種廣泛使用的過(guò)程挖掘工具,格式轉(zhuǎn)換是一項(xiàng)重復(fù)且耗時(shí)的任務(wù),需要一個(gè)通用的軟件框架來(lái)實(shí)現(xiàn).由此,ProMImport框架[10]應(yīng)運(yùn)而生,它使得各種轉(zhuǎn)換工具能夠方便地開(kāi)發(fā)出來(lái).
在ProM的早期版本中以MXML格式的事件日志作為輸入.MXML的主要問(wèn)題之一是以MXML格式存儲(chǔ)的事件日志中的附加屬性都被視為帶關(guān)鍵字的字符串且沒(méi)有實(shí)際含義.但是,事件的屬性值往往具有重要含義.為解決MXML格式遇到的問(wèn)題,一種新的日志格式—可擴(kuò)展事件流格式(XES格式)[11]被提了出來(lái)并成為IEEE的標(biāo)準(zhǔn)[12].為此,ProM中也提供了一個(gè)插件—XESame,它可以從數(shù)據(jù)源提取事件日志并將其轉(zhuǎn)化為XES[注]http://www.win.tue.nl/ieeetfpm.表2給出了XES格式的基礎(chǔ)結(jié)構(gòu)標(biāo)簽.
表2 XES基礎(chǔ)結(jié)構(gòu)標(biāo)簽Table 2 XES infrastructure label
雖然XES已經(jīng)成為了事件日志格式的國(guó)際標(biāo)準(zhǔn),但在實(shí)際中采用得依然并不廣泛.同時(shí),XES在表達(dá)結(jié)合了物聯(lián)網(wǎng)等技術(shù)的新型業(yè)務(wù)流程中產(chǎn)生的日志數(shù)據(jù)方面還存在一定的不足.
企業(yè)、組織內(nèi)部或是跨企業(yè)、跨組織,其業(yè)務(wù)流程執(zhí)行通常在不同的系統(tǒng)上完成[13-19],因此記錄執(zhí)行流程的事件日志也存儲(chǔ)在不同的源上.為了準(zhǔn)確挖掘和分析企業(yè)執(zhí)行流程,通常需要將在不同源上的事件日志進(jìn)行合并處理,從而揭示完整的端到端的執(zhí)行流程.
日志中包含的過(guò)程實(shí)例之間的關(guān)系類(lèi)似于數(shù)據(jù)庫(kù)中實(shí)體的關(guān)系,分別為:一對(duì)一、一對(duì)多、多對(duì)一以及多對(duì)多.隨著日志之間關(guān)系的復(fù)雜度增加,對(duì)日志合并過(guò)程的要求也越來(lái)越高.好的日志合并應(yīng)當(dāng)盡可能將兩個(gè)日志之間屬于同一過(guò)程實(shí)例的執(zhí)行序列合并在一起.而日志可在3個(gè)級(jí)別上進(jìn)行合并,分別為:原始數(shù)據(jù)、結(jié)構(gòu)化數(shù)據(jù)和模型級(jí)別[13].圖1總結(jié)了不同層級(jí)上日志合并的一些方法.
下文將針對(duì)不同級(jí)別的日志合并進(jìn)行介紹.
4.2.1 原始數(shù)據(jù)合并
原始數(shù)據(jù)是指事件日志以其本身的格式存在于數(shù)據(jù)庫(kù)或文件中,未進(jìn)行上文中所提出的格式轉(zhuǎn)換處理.目前對(duì)原始事件日志數(shù)據(jù)進(jìn)行合并的研究并不是很多.
文獻(xiàn)[21]研究了如何使用RFID技術(shù)來(lái)合并供應(yīng)鏈合作伙伴的數(shù)據(jù),重點(diǎn)是符合EPCglobal標(biāo)準(zhǔn)的數(shù)據(jù),這使得通過(guò)將數(shù)據(jù)映射到公共標(biāo)準(zhǔn)來(lái)合并合作伙伴的數(shù)據(jù)成為可能.另外,可以采用ETL技術(shù)從系統(tǒng)中獲取信息,然后將其轉(zhuǎn)換為新系統(tǒng)需要的格式,這樣,來(lái)自不同系統(tǒng)的數(shù)據(jù)可以合并到新系統(tǒng)中.然而這些方法不支持合并屬性不同但歸屬于同一執(zhí)行流程的數(shù)據(jù).在這種情況下,僅僅將兩個(gè)事件日志的數(shù)據(jù)合并放在一個(gè)聚合事件日志中是不夠的,還需要確定哪些過(guò)程實(shí)例需要單獨(dú)合并在一起.
當(dāng)原始數(shù)據(jù)保存在數(shù)據(jù)庫(kù)中,可以通過(guò)外鍵關(guān)聯(lián)不同數(shù)據(jù)庫(kù)表中的事件,采用映射規(guī)則使相互關(guān)聯(lián)的事件構(gòu)成過(guò)程實(shí)例.例如,文獻(xiàn)[14]中提出的方法就是通過(guò)事件相關(guān)標(biāo)識(shí)符識(shí)別屬于同一過(guò)程實(shí)例的數(shù)據(jù).但由于人工事件未被記錄,構(gòu)成的過(guò)程實(shí)例可能不具備完整性.文獻(xiàn)[20]的方法通過(guò)一個(gè)通用的數(shù)據(jù)模型和中間件收集和關(guān)聯(lián)所需的事件信息,這些信息中包括了業(yè)務(wù)過(guò)程的上下文和依賴(lài)關(guān)系.
隨著物聯(lián)網(wǎng)的廣泛應(yīng)用,融合物聯(lián)網(wǎng)的業(yè)務(wù)過(guò)程也得到了越來(lái)越多的部署.在這個(gè)背景下,原始數(shù)據(jù)的格式越來(lái)越多樣化,對(duì)這些傳感數(shù)據(jù)、實(shí)時(shí)數(shù)據(jù)等形式的原始數(shù)據(jù)的合并目前還缺乏研究.
4.2.2 結(jié)構(gòu)化數(shù)據(jù)合并
結(jié)構(gòu)化數(shù)據(jù)是指事件日志以結(jié)構(gòu)化的方式進(jìn)行保存,例如MXML格式、XES格式.在結(jié)構(gòu)化層級(jí)對(duì)日志進(jìn)行合并是最合適的級(jí)別[13]:一方面,對(duì)原始數(shù)據(jù)進(jìn)行合并需要掌握數(shù)據(jù)的含義和數(shù)據(jù)之間的關(guān)系知識(shí),這是一項(xiàng)重大的挑戰(zhàn);另一方面,在模型級(jí)別進(jìn)行合并無(wú)法重新選擇合適的過(guò)程挖掘技術(shù),而在結(jié)構(gòu)化層級(jí)進(jìn)行合并的結(jié)果仍然是一個(gè)事件日志,所有的過(guò)程挖掘和分析技術(shù)仍然可以運(yùn)用于該事件日志.
對(duì)于日志合并問(wèn)題,最優(yōu)的結(jié)果是將屬于同一過(guò)程實(shí)例的子日志合并起來(lái),因此這是一個(gè)在子日志上的組合優(yōu)化問(wèn)題.由于問(wèn)題規(guī)模龐大,許多算法采用智能優(yōu)化算法來(lái)解決該問(wèn)題.例如,文獻(xiàn)[17,19,22]中就分別采用了人工免疫算法、增強(qiáng)的人工免疫算法和遺傳算法解決日志合并問(wèn)題:首先將兩個(gè)日志中的每條軌跡進(jìn)行鏈接構(gòu)成總的鏈接集,其次,對(duì)于人工免疫算法,基于每組鏈接的匹配度函數(shù)得分進(jìn)行排序并從中選擇得分較高的前p%的鏈接構(gòu)成初始群體.該初始群體將經(jīng)歷超變異和受體編輯步驟,從而對(duì)群體中的鏈接集進(jìn)行不斷的優(yōu)化直到算法滿(mǎn)足某種停止?fàn)顟B(tài),若在優(yōu)化過(guò)程中總體最佳鏈接沒(méi)有得到改善,算法將提前停止.對(duì)于遺傳算法,從總的鏈接集開(kāi)始,在每一步中通過(guò)改變鏈接進(jìn)行隨機(jī)突變,然后根據(jù)匹配度得分選擇保留當(dāng)前鏈接或更新鏈接直到滿(mǎn)足算法停止條件.由于算法步驟的簡(jiǎn)化,這種技術(shù)不再是真正的遺傳算法,而稱(chēng)之為遺傳算法啟發(fā)的日志合并技術(shù).采用人工免疫算法和遺傳算法進(jìn)行日志合并容易陷入局部最優(yōu)的陷阱,每一代群體中保持鏈接的多樣性是避免過(guò)早收斂或持續(xù)退化的關(guān)鍵.因此文獻(xiàn)[18,19]中提出在人工免疫算法中加入模擬退火算法,從而不僅保留比上一代匹配度度更高的鏈接,而且在一定概率下接受一些劣解來(lái)產(chǎn)生新的種群.另一方面,還增加了一個(gè)免疫記憶庫(kù)來(lái)保存每一代中匹配度最高的鏈接.在構(gòu)建新一代群體時(shí),選擇免疫記憶庫(kù)中的鏈接來(lái)加強(qiáng)鏈接的多樣性.
上述日志合并方法要么假設(shè)兩個(gè)日志之間共享相同的實(shí)例標(biāo)識(shí)符,要么假設(shè)一個(gè)日志的實(shí)例標(biāo)識(shí)符作為屬性存于另一個(gè)日志中,并且過(guò)程之間是簡(jiǎn)單的一對(duì)一或一對(duì)多的關(guān)系.而在實(shí)際生活中過(guò)程實(shí)例之間可能具有復(fù)雜的多對(duì)一和多對(duì)多關(guān)系.若兩個(gè)日志中每個(gè)過(guò)程實(shí)例均使用不同的實(shí)例標(biāo)識(shí)符,在該情況下,某一日志的實(shí)例不一定直接對(duì)應(yīng)于其它日志中的實(shí)例,合并這些實(shí)例的日志成為一項(xiàng)更具有挑戰(zhàn)性的任務(wù).為克服日志之間實(shí)例標(biāo)識(shí)符的差異性,文獻(xiàn)[15,16]中提出基于屬性值相似和適當(dāng)?shù)臅r(shí)間關(guān)系進(jìn)行日志合并,這種方法不限定日志之間的關(guān)系,從而可以合并具有復(fù)雜關(guān)系的日志.其中適當(dāng)?shù)臅r(shí)間關(guān)系[23]是指主流程的執(zhí)行可以觸發(fā)子流程,在時(shí)間線(xiàn)上兩個(gè)流程必有重疊的時(shí)間點(diǎn),而屬性值相似則使用詞頻-逆文檔(TF-IDF)技術(shù)[24].合并方法首先為主流程的每個(gè)實(shí)例生成一個(gè)新的實(shí)例標(biāo)識(shí)符,其次為滿(mǎn)足時(shí)間關(guān)系的實(shí)例組合計(jì)算屬性值相似性分?jǐn)?shù),然后對(duì)于主流程的每個(gè)實(shí)例選擇匹配分?jǐn)?shù)最大的子流程實(shí)例進(jìn)行合并并保存在新的日志文件中.
基于屬性值相似或適當(dāng)?shù)臅r(shí)間關(guān)系進(jìn)行日志合并在一定程度上會(huì)存在誤差,即日志之間的鏈接并非是正確的或本應(yīng)屬于同一過(guò)程實(shí)例的子日志未進(jìn)行合并.文獻(xiàn)[13]提出了一種基于規(guī)則的方法用于一次合并兩個(gè)事件日志,合并規(guī)則規(guī)定了兩個(gè)事件日志中的軌跡或軌跡中事件的屬性之間需要滿(mǎn)足什么條件才能被認(rèn)為屬于同一過(guò)程實(shí)例.該方法直接基于給定規(guī)則進(jìn)行日志合并,其合并結(jié)果一定滿(mǎn)足合并規(guī)則.文章還通過(guò)向用戶(hù)獲取合并規(guī)則擴(kuò)展了該算法,以支持不具備相關(guān)領(lǐng)域知識(shí)的用戶(hù)對(duì)日志進(jìn)行合并.然而在真實(shí)的事件日志中,數(shù)據(jù)錯(cuò)誤的發(fā)生率很高,由此導(dǎo)致事件的連接以及日志的合并是不正確的.文獻(xiàn)[25]中提出的基于規(guī)則的合并方法可以處理有錯(cuò)誤的事件日志,與基于標(biāo)準(zhǔn)規(guī)則的算法相比,該方法具有更強(qiáng)的抗錯(cuò)能力.
4.2.3 模型級(jí)別合并
模型級(jí)別是指運(yùn)用過(guò)程挖掘技術(shù)從事件日志得出過(guò)程模型,其形式有petri網(wǎng)、BPMN圖等形式.當(dāng)企業(yè)或組織的業(yè)務(wù)流程進(jìn)行調(diào)整或整合時(shí),從原始數(shù)據(jù)或結(jié)構(gòu)化級(jí)別進(jìn)行日志合并是一項(xiàng)繁雜的工作,因此可從模型級(jí)別識(shí)別并無(wú)縫集成重疊的流程部分.
模型級(jí)別合并[26]是將一個(gè)過(guò)程模型合并到另一個(gè)過(guò)程模型中.合并分為無(wú)損合并和有損合并,有損合并不能保證合并后所有任務(wù)都保留,但有損合并不一定就是有問(wèn)題的,它將兩個(gè)任務(wù)合并成一個(gè)任務(wù)來(lái)改進(jìn)了流程并刪除了冗余任務(wù).而無(wú)損合并是將過(guò)程模型中的所有任務(wù)都保留,但有時(shí)會(huì)產(chǎn)生冗余任務(wù)使得合并后的過(guò)程模型更為復(fù)雜.
文獻(xiàn)[27]提出使用模型元素之間的對(duì)應(yīng)關(guān)系和單入口單出口片段(SESE片段)技術(shù)來(lái)檢測(cè)兩個(gè)過(guò)程模型之間的差異[28],并基于建模者的偏好以迭代的方式解決過(guò)程模型之間的差異并在必要情況下重新合并過(guò)程模型.與之相反,文獻(xiàn)[29]提出的方法是尋找待合并模型之間相匹配的節(jié)點(diǎn),使用基于字符串編輯距離[30]和基于Wordnet相似度包[31]來(lái)計(jì)算每對(duì)節(jié)點(diǎn)間的相似性分?jǐn)?shù).在具有最高相似性分?jǐn)?shù)的節(jié)點(diǎn)進(jìn)行合并,并在結(jié)果圖中移除其中一個(gè)流程圖的開(kāi)始或結(jié)束節(jié)點(diǎn)而保留另一個(gè)流程圖的開(kāi)始或結(jié)束節(jié)點(diǎn)形成完整模型.
過(guò)程模型有不同的定義形式,文獻(xiàn)[32]提出的方法是基于事件驅(qū)動(dòng)過(guò)程鏈(EPC)[33]對(duì)模型進(jìn)行合并.將事件驅(qū)動(dòng)過(guò)程鏈中的事件以函數(shù)圖的形式表示,通過(guò)合并函數(shù)集、弧集并根據(jù)兩個(gè)函數(shù)圖中的值計(jì)算弧的拆分和連接類(lèi)型,從而實(shí)現(xiàn)兩個(gè)函數(shù)圖的合并,最后將得到的結(jié)果函數(shù)圖轉(zhuǎn)換回EPC格式.該方法不局限于EPC類(lèi)型的過(guò)程模型,對(duì)于其它的業(yè)務(wù)流程建模語(yǔ)言同樣適用.
模型級(jí)別的合并要求事先從事件日志中挖掘出過(guò)程模型,這一定程度限制了該方法的應(yīng)用.
原始數(shù)據(jù)合并、結(jié)構(gòu)化數(shù)據(jù)合并和模型級(jí)別合并適合于不同的場(chǎng)景.對(duì)數(shù)據(jù)質(zhì)量的要求也有所不同.顯然模型級(jí)別合并是建立在已經(jīng)挖掘出或者定義了模型的基礎(chǔ)上,要求最高,而原始數(shù)據(jù)合并對(duì)數(shù)據(jù)要求最低,難度也最大.
由于系統(tǒng)故障或人為原因,事件日志可能缺少某些數(shù)據(jù)[34-38],例如事件的丟失或事件屬性的丟失等.不完整的事件日志給過(guò)程挖掘和過(guò)程分析帶來(lái)了困難[34],例如,現(xiàn)有的過(guò)程挖掘技術(shù)在日志缺失的情況下得到的過(guò)程模型在一定程度上將偏離實(shí)際的業(yè)務(wù)流程.在數(shù)據(jù)挖掘領(lǐng)域,有許多方法可以修復(fù)丟失的數(shù)據(jù),如回歸、離群點(diǎn)檢測(cè)等[5].然而,由于業(yè)務(wù)執(zhí)行過(guò)程的復(fù)雜性以及事件之間存在的并發(fā)性、循環(huán)性和因果關(guān)系等,上述方法不能直接用于修復(fù)過(guò)程挖掘中不完整事件日志中的缺失數(shù)據(jù).
下文將介紹不同類(lèi)型的數(shù)據(jù)缺失及其解決方案.
4.3.1 事件缺失
事件缺失是指在執(zhí)行序列中該發(fā)生的事件并未發(fā)生或發(fā)生的事件未被記錄在事件日志中,對(duì)缺失事件進(jìn)行恢復(fù)有助于挖掘完整的業(yè)務(wù)流程,從而改進(jìn)業(yè)務(wù)流程[35-39].
事件修復(fù)與業(yè)務(wù)流程的一致性檢查有關(guān).一致性檢查用于確定執(zhí)行序列在多大程度上符合預(yù)定義的過(guò)程.與一致性檢查不同,事件修復(fù)側(cè)重于如何使用過(guò)程規(guī)范來(lái)修復(fù)不完整的序列.對(duì)齊方法是一種一致性檢查技術(shù),這種方法旨在將日志中的事件按順序與過(guò)程中的事件對(duì)齊.文獻(xiàn)[40]就提出了一種基于Petri網(wǎng)的事件日志與過(guò)程模型之間的快速對(duì)齊方法.對(duì)齊方法也可以運(yùn)用到事件修復(fù),即將缺失事件的軌跡與某一對(duì)照軌跡對(duì)齊并利用對(duì)照軌跡修復(fù)缺失事件.目前有兩種方法選擇對(duì)照軌跡,一種以過(guò)程模型中某條具體的執(zhí)行路徑作為對(duì)照軌跡[34,35,38,39,42],另一種將日志進(jìn)行預(yù)處理后分為完整的和不完整的序列,將完整的執(zhí)行序列作為對(duì)照軌跡[36,37,41].
文獻(xiàn)[42]中的方法基于BPMN圖進(jìn)行缺失事件的恢復(fù),該方法從過(guò)程模型中自動(dòng)推導(dǎo)出一組邏輯規(guī)則,對(duì)于每一個(gè)執(zhí)行序列運(yùn)用邏輯規(guī)則檢查其與模型的一致性,對(duì)于不完整的執(zhí)行序列推理可能的丟失事件.相比之下,文獻(xiàn)[38,39]提出了增強(qiáng)的對(duì)齊方法,即通過(guò)結(jié)合隨機(jī) Petri 網(wǎng)、對(duì)齊技術(shù)和貝葉斯網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)恢復(fù).它使用路徑概率來(lái)確定最可能丟失的事件,并利用貝葉斯網(wǎng)絡(luò)來(lái)計(jì)算每個(gè)插入事件最可能的時(shí)間戳.但是這種方法是低效的,因?yàn)樗枰杜e和搜索模型中所有可能的完整執(zhí)行序列.為解決效率問(wèn)題,文獻(xiàn)[34]提出了一個(gè)分支框架,將Petri網(wǎng)過(guò)程模型拆分為多個(gè)分支,其中每個(gè)分支表示一個(gè)沒(méi)有任何選擇路由的Petri網(wǎng),然后利用索引和修剪技術(shù)來(lái)減少搜索空間.盡管分支方法比窮舉搜索更有效,但仍有很大的改進(jìn)空間.文獻(xiàn)[35]提出了一種更有效的最小恢復(fù)方法,該文認(rèn)為一個(gè)過(guò)程模型可能由幾個(gè)獨(dú)立的子過(guò)程組成,不完整序列的最小恢復(fù)只需要在其中一個(gè)子過(guò)程中進(jìn)行,考慮到這一點(diǎn),文中提出了采用啟發(fā)式方法識(shí)別能夠產(chǎn)生最小恢復(fù)的子進(jìn)程,這樣搜索空間將明顯減少.
選擇過(guò)程模型作為修復(fù)的基礎(chǔ)的假設(shè)是過(guò)程模型是完整和正確的.然而,原始事件日志本身可能就包含缺失值,利用原始事件日志得出的過(guò)程模型不一定就是“完美”的模型,以“不完美”的模型去檢測(cè)執(zhí)行序列是否含有缺失值可能會(huì)有誤差.
若未定義過(guò)程模型,也可對(duì)不完整序列進(jìn)行修復(fù).文獻(xiàn)[37]采用軌跡配置文件表示完整事件日志中的執(zhí)行序列,其中軌跡配置文件是指用索引表示執(zhí)行序列中事件的發(fā)生順序并記錄某事件的出現(xiàn)次數(shù).然而,該文件沒(méi)有進(jìn)一步分析事件之間的循環(huán)和因果關(guān)系.因此在文獻(xiàn)[36]中使用事件傳遞關(guān)系矩陣來(lái)表示完整事件日志中的執(zhí)行序列,其中每一行對(duì)應(yīng)于一個(gè)軌跡的傳遞關(guān)系向量,如果軌跡中存在對(duì)應(yīng)的傳遞關(guān)系就將其值設(shè)置為 1,否則設(shè)置為 0.使用這兩種方法對(duì)完整的執(zhí)行序列重新表示后可以采用歐氏距離和自組織映射算法相結(jié)合的方式對(duì)其進(jìn)行聚類(lèi),然后將不完整序列與其最相似的聚類(lèi)進(jìn)行對(duì)齊匹配,最后根據(jù)聚類(lèi)中事件之間的關(guān)系修復(fù)不完整序列中缺失的事件.不同于上述方法中對(duì)軌跡進(jìn)行聚類(lèi)得到軌跡簇,文獻(xiàn)[41]中的方法將軌跡進(jìn)行分段使得每段中不包含重復(fù)的事件,然后對(duì)于分段進(jìn)行聚類(lèi)得到分段簇,對(duì)于不完整序列的修復(fù),一般只考慮對(duì)照軌跡簇的一個(gè)片段,即在對(duì)應(yīng)的分段簇中進(jìn)行軌跡重放確定并修復(fù)缺失事件.該方法不僅可以修復(fù)缺失事件,而且對(duì)冗余事件和錯(cuò)位事件的處理也有幫助.
利用完整的執(zhí)行序列修復(fù)缺失事件有3點(diǎn)局限:1)區(qū)分日志中的執(zhí)行序列是否完整需要領(lǐng)域?qū)<乙约跋闰?yàn)知識(shí)的幫助;2)在實(shí)際生活中企業(yè)、組織的業(yè)務(wù)流程是不斷變化的,某一項(xiàng)業(yè)務(wù)的流程可能會(huì)被簡(jiǎn)化.簡(jiǎn)化后的流程相對(duì)于簡(jiǎn)化前的流程可能是不完整的,但實(shí)際上兩者都是完整的執(zhí)行序列;3)對(duì)于業(yè)務(wù)流程眾多的企業(yè)或組織,對(duì)海量的事件日志去判斷每一條執(zhí)行序列是否完整需要耗費(fèi)很長(zhǎng)的時(shí)間.
在研究中,目前對(duì)于缺失事件恢復(fù)的解決方案都是在真實(shí)或合成日志上隨機(jī)刪除一定比例的事件進(jìn)行實(shí)驗(yàn),這些事件作為缺失事件是人們所知道的.而在實(shí)際日志中算法僅依靠程序設(shè)定判斷軌跡是否是完整的并對(duì)不完整序列進(jìn)行修復(fù),這樣的判斷以及修復(fù)可能存在誤差,尋找缺失原因才是修復(fù)缺失事件的根本.
4.3.2 事件屬性缺失
事件屬性包括事件的發(fā)生時(shí)間、事件的發(fā)起人、相關(guān)變量的取值等等.缺少屬性值可能無(wú)法對(duì)事件日志進(jìn)行分析,例如:若事件的發(fā)起人缺失則無(wú)法確定哪個(gè)用戶(hù)對(duì)該事件負(fù)責(zé);若事件的開(kāi)始時(shí)間或結(jié)束時(shí)間缺失則無(wú)法判斷事件的持續(xù)時(shí)間是否符合要求等.修復(fù)缺失的屬性值會(huì)提高基于事件日志的過(guò)程分析的質(zhì)量.
因?yàn)槭录傩钥赡芎卸喾N類(lèi)型的數(shù)據(jù),例如:數(shù)值型、文本型等,所以對(duì)于缺失的屬性值要明確其類(lèi)型,選用恰當(dāng)?shù)姆椒▽?duì)其進(jìn)行恢復(fù).
事件日志通常由實(shí)例標(biāo)識(shí)符來(lái)確定執(zhí)行序列,若實(shí)例標(biāo)識(shí)符缺失則對(duì)于過(guò)程挖掘是一項(xiàng)艱巨的挑戰(zhàn).在未標(biāo)記的事件日志中尋找實(shí)例標(biāo)識(shí)符這一問(wèn)題雖然可以用貪婪法解決,但其結(jié)果通常不是最優(yōu)的.文獻(xiàn)[43]提出了序列劃分方法來(lái)生成一組分區(qū),然后找到可以覆蓋執(zhí)行序列的最小分區(qū),通過(guò)最小分區(qū)可以得出事件日志是如何從過(guò)程實(shí)例的執(zhí)行中生成的,從而恢復(fù)沒(méi)有實(shí)例標(biāo)識(shí)符的執(zhí)行序列.由于該方法將流程的并發(fā)執(zhí)行部分表示為不同的分區(qū),所以其主要限制是無(wú)法處理并發(fā)事件和循環(huán)事件.文獻(xiàn)[44]提出的方法根據(jù)事件的時(shí)間戳構(gòu)建實(shí)例決策樹(shù)來(lái)推導(dǎo)實(shí)例標(biāo)識(shí)符,去除了并發(fā)事件的限制,但依然無(wú)法處理循環(huán)事件.
對(duì)于數(shù)值型數(shù)據(jù)最簡(jiǎn)單的方法是回歸.文獻(xiàn)[45]以交通領(lǐng)域作為研究對(duì)象,應(yīng)用了線(xiàn)性回歸、嶺回歸和Lasso回歸解決事件日志中的時(shí)間戳缺失問(wèn)題.但事件日志中有些屬性值并不遵循已知的特定分布,所以傳統(tǒng)的數(shù)據(jù)插補(bǔ)方法對(duì)事件日志的修復(fù)不是很有效.文獻(xiàn)[46]中提出采用機(jī)器學(xué)習(xí)技術(shù)來(lái)學(xué)習(xí)事件日志中數(shù)據(jù)潛在分布的模型,從該模型中估算出缺失值.
采用傳統(tǒng)方法或機(jī)器學(xué)習(xí)技術(shù)對(duì)缺失數(shù)據(jù)進(jìn)行填充有其不同的優(yōu)缺點(diǎn),對(duì)于事件屬性的缺失需要考慮數(shù)據(jù)本身的特點(diǎn)以及針對(duì)數(shù)據(jù)做出的假設(shè)從而選用合適的預(yù)測(cè)方法.同事件缺失一樣,找到事件屬性缺失的原因才是修復(fù)缺失屬性的根本.
事件丟失與事件屬性缺失處理相比較,顯然事件丟失的難度更大.目前針對(duì)這兩方面的問(wèn)題采用的技術(shù)從本質(zhì)上是類(lèi)似的,都需要借助于先驗(yàn)知識(shí)或者從認(rèn)為是完整的日志上獲得的知識(shí).借助于先驗(yàn)知識(shí)需要專(zhuān)家的介入,利用完整的日志獲得的知識(shí)進(jìn)行處理時(shí),在缺失現(xiàn)象比較普遍的情況下,這些方法將面臨性能下降的風(fēng)險(xiǎn).兩者的結(jié)合是一條可行的途徑.
由于數(shù)據(jù)輸入問(wèn)題、系統(tǒng)故障問(wèn)題或其他技術(shù)限制造成事件日志中存在噪音.噪音的存在會(huì)導(dǎo)致過(guò)程模型中包含不常見(jiàn)的執(zhí)行路徑,從而降低過(guò)程模型和過(guò)程分析的整體準(zhǔn)確性.
噪音處理的簡(jiǎn)單方法是直接將包含異常行為的軌跡進(jìn)行刪除[46,47],然而對(duì)于企業(yè)或組織來(lái)說(shuō)所有的流程實(shí)例都具有價(jià)值,這種“暴力”的刪除方法可能會(huì)獲得不完整的過(guò)程模型從而無(wú)法準(zhǔn)確分析及改進(jìn)流程.
文獻(xiàn)[49]中提出使用信息論方法進(jìn)行噪音處理,對(duì)于事件日志中不同類(lèi)型的噪音問(wèn)題可以選用不同的信息論方法進(jìn)行噪音過(guò)濾.
目前針對(duì)日志噪音的處理大多采用了基于概率的方法.文獻(xiàn)[48]中根據(jù)子序列的出現(xiàn)頻率判斷執(zhí)行序列是否異常,如果它是異常軌跡則將整條軌跡刪除,而這樣的噪音處理方式可能會(huì)導(dǎo)致更多的異常行為出現(xiàn).文獻(xiàn)[50]中選用更高頻率出現(xiàn)的子序列替代異常子序列,從而減少更多異常行為的出現(xiàn).文獻(xiàn)[51,52]提出基于整個(gè)事件日志和給定的閾值構(gòu)造一個(gè)無(wú)異常自動(dòng)機(jī)(AFA),將所有低于閾值的狀態(tài)轉(zhuǎn)換刪除并在該自動(dòng)機(jī)上重放事件日志,隨后所有不符合 AFA 的事件將被刪除,從而能夠在細(xì)粒度級(jí)別檢測(cè)不常見(jiàn)的事件行為.然而該技術(shù)并不能檢測(cè)所有類(lèi)型的異常值,例如,符合AFA的執(zhí)行序列并沒(méi)有正確的終止,這仍然會(huì)導(dǎo)致不可行的過(guò)程挖掘結(jié)果.
基于概率的方法進(jìn)行噪音刪除有潛在的風(fēng)險(xiǎn).罕見(jiàn)行為是指發(fā)生次數(shù)不多,但其組成的執(zhí)行序列是可正常出現(xiàn)的行為.例如,在銀行貸款中若貸款數(shù)額巨大則需要進(jìn)行額外的檢查.因罕見(jiàn)行為是低概率發(fā)生的事件,基于概率的方法可能會(huì)將罕見(jiàn)行為刪除掉.但罕見(jiàn)行為對(duì)企業(yè)或組織來(lái)說(shuō)也是有價(jià)值的實(shí)例,對(duì)其直接刪除可能會(huì)產(chǎn)生危害.
除了基于概率的方法對(duì)事件日志進(jìn)行過(guò)濾,文獻(xiàn)[53]提出基于規(guī)則的方法進(jìn)行日志過(guò)濾.主要思想是將事件日志的子集標(biāo)記為無(wú)噪聲或有噪聲,然后被標(biāo)記的子日志可使用PRISM算法[54]構(gòu)建基于規(guī)則的分類(lèi)器,通過(guò)該分類(lèi)器對(duì)整個(gè)事件日志進(jìn)行過(guò)濾.然而,在真實(shí)的事件日志中,提供一組覆蓋所有可能異常值的訓(xùn)練軌跡是不切實(shí)際的.
上文中的噪聲過(guò)濾技術(shù)不能直接應(yīng)用于在線(xiàn)環(huán)境.因此,在文獻(xiàn)[55,56]中采用事件窗口維護(hù)一組最近接收的事件,當(dāng)新事件到達(dá)后轉(zhuǎn)發(fā)給過(guò)濾器評(píng)估相應(yīng)實(shí)例的狀態(tài),并根據(jù)該狀態(tài)的傳出弧概率分布來(lái)判斷新事件是否可能是異常的,從而決定是發(fā)送到輸出流或者是丟棄該事件.
以上噪音的處理都發(fā)生在事件級(jí)別,而有時(shí)屬性值的不正確也會(huì)對(duì)業(yè)務(wù)流程的整體有一定的影響.文獻(xiàn)[57]提供了一種自動(dòng)糾正事件日志中時(shí)間戳錯(cuò)誤的方法.該方法使用日志中正確排序的執(zhí)行序列,為受時(shí)間戳錯(cuò)誤問(wèn)題影響的序列估計(jì)事件之間最可能的順序,并估計(jì)每個(gè)事件的持續(xù)時(shí)間為已重新排序的事件分配時(shí)間戳.文獻(xiàn)[58]提出使用結(jié)構(gòu)完整的過(guò)程模型來(lái)修復(fù)日志中的事件名稱(chēng)與模型中事件名稱(chēng)不一致的問(wèn)題.
總體而言,目前對(duì)日志噪音的處理主要還是進(jìn)行噪音數(shù)據(jù)的刪除,這種做法雖然比較簡(jiǎn)單,但是將導(dǎo)致數(shù)據(jù)的損失.對(duì)噪音的修復(fù)難度較大,它需要基于一些先驗(yàn)的知識(shí),因此,所適用的范圍相對(duì)有限.一個(gè)可行的方向是去挖掘噪聲產(chǎn)生的原因,通過(guò)對(duì)噪聲源的建模,可以為噪聲修復(fù)提供技術(shù)途徑.
現(xiàn)實(shí)生活中許多業(yè)務(wù)過(guò)程具有復(fù)雜性,其產(chǎn)生的事件軌跡也非常復(fù)雜.依據(jù)這些事件軌跡去生成一個(gè)統(tǒng)一的模型將非常復(fù)雜[59,60],也不利于進(jìn)行后續(xù)的針對(duì)性分析.解決這一問(wèn)題的方法是采用聚類(lèi)方法將相似的過(guò)程實(shí)例進(jìn)行聚類(lèi),從而可以針對(duì)每一個(gè)聚類(lèi)都構(gòu)建相對(duì)應(yīng)的模型.文獻(xiàn)[61]提出對(duì)于大型日志而言,采用任何過(guò)程挖掘算法,其挖掘效率及模型質(zhì)量均不高.因此文中提出將軌跡聚類(lèi)與遺傳挖掘算法結(jié)合的方法,提高挖掘效率以及過(guò)程模型的質(zhì)量.
文獻(xiàn)[62]中提到了兩種不同的軌跡聚類(lèi)技術(shù),一種是基于距離的聚類(lèi)技術(shù),另一種是結(jié)合了模型驅(qū)動(dòng)方法的技術(shù).
目前對(duì)事件日志進(jìn)行聚類(lèi)的大多數(shù)方法都基于軌跡之間的相似性,而衡量相似性的指標(biāo)就是軌跡之間的“距離”,“距離”越小則相似性越高.目前有多種距離度量方法來(lái)計(jì)算軌跡間的相對(duì)距離,例如:歐式距離、漢明距離、雅克卡距離等.文獻(xiàn)[63]從理論的角度確定了衡量軌跡相似性的8個(gè)度量指標(biāo),并給出了8個(gè)度量指標(biāo)的相似度定義.
文獻(xiàn)[64,65]中提出的方法對(duì)軌跡中的子序列進(jìn)行聚類(lèi).文獻(xiàn)[64]的方法將日志分割得到日志段,基于統(tǒng)計(jì)推斷分析測(cè)量事件日志不同段之間的距離并計(jì)算在特定位置所觀察事件的概率分布,然后計(jì)算段之間的相似性并應(yīng)用聚類(lèi)算法對(duì)其進(jìn)行聚類(lèi).文獻(xiàn)[65]使用Smith-Waterman-Gotoh算法對(duì)序列進(jìn)行局部比對(duì)[66]來(lái)計(jì)算軌跡間距離并應(yīng)用多維縮放構(gòu)建特征空間,然后應(yīng)用k-means方法進(jìn)行聚類(lèi).
除了對(duì)軌跡內(nèi)子序列進(jìn)行聚類(lèi)外,更多的方法還是對(duì)整條軌跡進(jìn)行聚類(lèi).文獻(xiàn)[67]中將軌跡轉(zhuǎn)換為向量空間模型并使用標(biāo)準(zhǔn)距離度量方法計(jì)算軌跡間的相似性.但該方法沒(méi)有捕捉動(dòng)態(tài)的執(zhí)行過(guò)程且丟失了事件之間的發(fā)生順序,由此計(jì)算得到的軌跡之間相似性的誤差很大.因此文獻(xiàn)[68]在向量空間模型的基礎(chǔ)上提出了上下文感知特征集,即若兩個(gè)或多個(gè)過(guò)程實(shí)例之間共享高相似性區(qū)域可被認(rèn)為這些流程是相似的,從而使用這些高相似性區(qū)域作為特征對(duì)軌跡進(jìn)行聚類(lèi).除此之外,文獻(xiàn)[69]也提出了一種在通用編輯距離的基礎(chǔ)上添加上下文感知來(lái)計(jì)算編輯操作的成本,再根據(jù)編輯操作的成本進(jìn)行相似性度量.考慮上下文的技術(shù)比不考慮上下文的技術(shù)性能更好,但復(fù)雜性也隨之提高.以上方法只考慮了事件以及事件之間的傳遞關(guān)系,計(jì)算軌跡間的相似性指標(biāo)有些單一.文獻(xiàn)[59]中提出基于配置文件對(duì)軌跡進(jìn)行聚類(lèi),其中每個(gè)配置文件從一個(gè)特定的角度測(cè)量每個(gè)實(shí)例,從而可以從多個(gè)角度衡量軌跡間的相似性.
文獻(xiàn)[70]提出了一個(gè)分層的軌跡聚類(lèi)框架.該框架使用事件的屬性作為聚類(lèi)指標(biāo),并使用分區(qū)函數(shù)將有相同屬性值的實(shí)例組合在一起,由此產(chǎn)生幾個(gè)子日志構(gòu)成原始事件日志的初始分區(qū),然后使用距離函數(shù)計(jì)算初始分區(qū)間的距離從而構(gòu)建聚類(lèi)的層次結(jié)構(gòu).與在整個(gè)事件數(shù)據(jù)上發(fā)現(xiàn)的模型相比,由層次結(jié)構(gòu)的不同集群描述的模型具有更好的質(zhì)量.
文獻(xiàn)[62]指出當(dāng)前的軌跡聚類(lèi)主要存在兩方面的問(wèn)題:1)以何種驅(qū)動(dòng)方式對(duì)日志進(jìn)行聚類(lèi),若采用軌跡之間的距離對(duì)日志進(jìn)行聚類(lèi)可能會(huì)存在誤差;2)用戶(hù)希望能站在專(zhuān)業(yè)領(lǐng)域的角度理解集群之間的區(qū)別特征,這有賴(lài)于當(dāng)前過(guò)程環(huán)境的業(yè)務(wù)特征.因此,文中介紹了SECPI算法,該算法旨在找到業(yè)務(wù)流特征的最小集合,通過(guò)該最小集合決定某一過(guò)程實(shí)例是否保留在某一集群中.此外,該方法允許在相應(yīng)的過(guò)程模型中進(jìn)行可視化,以便用戶(hù)可以觀察什么特征使得過(guò)程實(shí)例屬于某個(gè)集群.
以上方法均在軌跡級(jí)別對(duì)事件日志進(jìn)行聚類(lèi),而有些日志中缺乏事件軌跡的信息,因此文獻(xiàn)[71]的方法使用全局事件類(lèi)相關(guān)函數(shù)計(jì)算日志中事件類(lèi)之間的相關(guān)度,其次通過(guò)該相關(guān)度推斷出事件類(lèi)的層次結(jié)構(gòu)并使用凝聚層次聚類(lèi)(AHC)算法將最相關(guān)的事件類(lèi)連續(xù)的組合成更高級(jí)別的實(shí)體—事件簇,最后在這個(gè)事件類(lèi)的層次結(jié)構(gòu)中選擇任意的抽象級(jí)別進(jìn)行軌跡分段.
另外一種常用的聚類(lèi)方法是基于模型而不關(guān)注單條軌跡.文獻(xiàn)[60,72]的方法將每個(gè)集群的模型用馬爾可夫鏈表示,通過(guò)期望最大化算法計(jì)算某條軌跡由某個(gè)集群中的馬爾可夫鏈產(chǎn)生的概率,從而將一條軌跡分配給某一集群.文獻(xiàn)[73]提出使用過(guò)程發(fā)現(xiàn)算法構(gòu)建總的過(guò)程模型,其次迭代的使用K-means聚類(lèi)方法將日志劃分成簇,直到為每個(gè)簇發(fā)現(xiàn)一個(gè)易于理解的模型.文獻(xiàn)[74]的方法與文獻(xiàn)[73]的方法相反,其基于適合度向已經(jīng)選擇的軌跡集合中添加一個(gè)新的軌跡構(gòu)成新的過(guò)程模型,若該模型依然足夠精確,則所選的軌跡添加到當(dāng)前集合,最后每個(gè)集合即是一個(gè)聚類(lèi).該方法將軌跡進(jìn)行聚類(lèi)不是因?yàn)檐壽E之間表現(xiàn)出相似的行為,而是因?yàn)樗鼈兌歼m合于特定的過(guò)程模型.在聚類(lèi)的同時(shí)對(duì)模型進(jìn)行評(píng)估會(huì)得到更為滿(mǎn)意的聚類(lèi)結(jié)果和易于理解的過(guò)程模型.
在所有日志上進(jìn)行聚類(lèi)可以保證全局優(yōu)化,但是需要消耗大量計(jì)算時(shí)間,實(shí)時(shí)性無(wú)法保證.通過(guò)分層聚類(lèi)或者增量式聚類(lèi)可以減少計(jì)算量,但是無(wú)法保證全局優(yōu)化.因此,如何找到有效的方法能夠?qū)崿F(xiàn)全局優(yōu)化,又保證計(jì)算速度還是一個(gè)挑戰(zhàn)性問(wèn)題.
本文中闡述的技術(shù)覆蓋了日志預(yù)處理技術(shù)的各個(gè)方面.其中,日志標(biāo)準(zhǔn)化是前提,日志合并是基礎(chǔ),缺失值和噪音處理用以提高日志的質(zhì)量,而軌跡聚類(lèi)是面向特定任務(wù)進(jìn)行的準(zhǔn)備工作.在有些場(chǎng)景中,這些技術(shù)都需要采用,而有些場(chǎng)景中日志合并可能并不需要采用.
雖然在事件日志預(yù)處理方面的研究已經(jīng)取得了一定的成果,隨著業(yè)務(wù)過(guò)程的應(yīng)用的廣泛化以及和最新技術(shù)的結(jié)合,對(duì)事件日志預(yù)處理帶來(lái)了許多新的挑戰(zhàn),也使我們需要關(guān)注一些未來(lái)的研究方向.
5.1.1 事件日志預(yù)處理效率的挑戰(zhàn)
許多企業(yè)的業(yè)務(wù)過(guò)程的數(shù)量越來(lái)越多,這使得事件日志一直在快速產(chǎn)生.而過(guò)程挖掘和過(guò)程分析的實(shí)時(shí)性要求又要求事件日志的處理也需要實(shí)時(shí)完成.目前,許多日志預(yù)處理技術(shù)需要在整個(gè)事件日志上來(lái)進(jìn)行,效率上難以滿(mǎn)足要求.在海量的、不斷增長(zhǎng)的事件日志上如何高效地進(jìn)行預(yù)處理,以滿(mǎn)足實(shí)時(shí)性的要求,這是事件日志預(yù)處理的重要挑戰(zhàn).
5.1.2 事件日志的異構(gòu)性
隨著物聯(lián)網(wǎng)與業(yè)務(wù)過(guò)程的結(jié)合,事件日志不僅來(lái)自于軟件系統(tǒng),也來(lái)自于傳感器、物理設(shè)備.同時(shí),業(yè)務(wù)過(guò)程中也可以將圖像、視頻、聲音等多媒體數(shù)據(jù)作為事件的屬性.這就將使事件日志的形態(tài)更為復(fù)雜.目前,許多事件日志預(yù)處理都是針對(duì)結(jié)構(gòu)化的事件日志展開(kāi)的,無(wú)法處理非結(jié)構(gòu)化的數(shù)據(jù).
5.1.3 分布式事件日志預(yù)處理
許多業(yè)務(wù)過(guò)程涉及到多個(gè)企業(yè),這就意味著事件日志分散在不同的企業(yè)中.數(shù)據(jù)作為一種重要的資產(chǎn)越來(lái)越被各個(gè)企業(yè)所重視,因此各個(gè)企業(yè)并不愿共享這些事件日志.然而,對(duì)業(yè)務(wù)過(guò)程進(jìn)行挖掘和分析又具有很大的價(jià)值,如何在這種情況下對(duì)這些分布的數(shù)據(jù)進(jìn)行預(yù)處理是一個(gè)具有很大挑戰(zhàn)性的問(wèn)題.
5.1.4 事件日志預(yù)處理對(duì)先驗(yàn)假設(shè)的依賴(lài)
對(duì)事件日志進(jìn)行預(yù)處理時(shí)常常會(huì)假設(shè)事件日志滿(mǎn)足一些條件,例如:在進(jìn)行日志合并時(shí)會(huì)假設(shè)兩個(gè)事件日志的格式是統(tǒng)一的、對(duì)事件日志進(jìn)行聚類(lèi)假設(shè)日志中的每個(gè)事件都具有時(shí)間戳且事件按照發(fā)生順序進(jìn)行排列.對(duì)日志進(jìn)行預(yù)處理的一些方法是在理想情況下或是在合成日志上進(jìn)行實(shí)驗(yàn),但是真實(shí)的事件日志通常是復(fù)雜的.所以在真實(shí)日志上應(yīng)用預(yù)處理技術(shù)可能未必得到滿(mǎn)意的結(jié)果.
5.1.5 事件日志預(yù)處理中對(duì)閾值取值的依賴(lài)
在諸多對(duì)日志進(jìn)行預(yù)處理的方法中均涉及到閾值,例如在日志噪音處理中認(rèn)為某一事件的出現(xiàn)頻率低于給定的閾值就會(huì)被認(rèn)為是異常行為、在軌跡聚類(lèi)中若兩條軌跡的相似性高于給定的閾值就會(huì)被認(rèn)為是相似的軌跡等.閾值是人為給定的,合適的閾值會(huì)提高預(yù)處理結(jié)果的準(zhǔn)確性,但不合適的閾值會(huì)降低預(yù)處理結(jié)果的準(zhǔn)確性甚至得到錯(cuò)誤的結(jié)果.
5.2.1 高效的事件日志預(yù)處理方法
目前,現(xiàn)有的事件日志預(yù)處理技術(shù)都是對(duì)過(guò)去的日志進(jìn)行預(yù)處理,而在實(shí)際生活中,日志不斷產(chǎn)生且隨時(shí)會(huì)產(chǎn)生規(guī)律的變化,對(duì)日志進(jìn)行即時(shí)的處理是未來(lái)的一個(gè)研究方向.從流數(shù)據(jù)的角度看,事件日志也可以看成是一種流數(shù)據(jù),因此可以運(yùn)用流數(shù)據(jù)中的處理手段來(lái)進(jìn)行事件日志預(yù)處理.另一方面,可以研究增量化的模型,例如貝葉斯模型,以適應(yīng)數(shù)據(jù)不斷到來(lái)的特點(diǎn).近年來(lái),將深度學(xué)習(xí)方法應(yīng)用事件日志處理也已經(jīng)出現(xiàn)了一些方法,它們可以將軌跡映射為一個(gè)向量,而映射為向量后再進(jìn)行各種預(yù)處理將更為高效.因此,將事件日志運(yùn)用深度學(xué)習(xí)進(jìn)行嵌入表示是一個(gè)值得探討的方向.
5.2.2 非結(jié)構(gòu)化事件日志處理
業(yè)務(wù)過(guò)程的事件日志信息可能是非結(jié)構(gòu)化形式,如掃描的文檔或電子郵件.將非結(jié)構(gòu)化數(shù)據(jù)與業(yè)務(wù)流程及其活動(dòng)相關(guān)聯(lián)將是大勢(shì)所趨,而當(dāng)前所存在的日志預(yù)處理技術(shù)大多都是針對(duì)結(jié)構(gòu)化的事件日志,文獻(xiàn)[20]針對(duì)非結(jié)構(gòu)化日志提出了如何識(shí)別端到端的系統(tǒng)流程,但對(duì)非結(jié)構(gòu)化日志的其它數(shù)據(jù)質(zhì)量問(wèn)題的研究卻沒(méi)有涉及.對(duì)非結(jié)構(gòu)化的事件日志處理是一個(gè)重要的研究方向.
5.2.3 隱私保護(hù)的事件日志預(yù)處理
針對(duì)分布式業(yè)務(wù)過(guò)程中各個(gè)企業(yè)隱私保護(hù)的需求,需要研究如何結(jié)合過(guò)程挖掘和過(guò)程分析算法進(jìn)行事件日志的預(yù)處理.文獻(xiàn)[75]歸納和整理了最新的隱私保護(hù)算法,將隱私保護(hù)算法和日志預(yù)處理方法結(jié)合成為未來(lái)的研究方向.
5.2.4 事件日志預(yù)處理的集成框架
現(xiàn)有的事件日志預(yù)處理技術(shù)都針對(duì)某一特定的問(wèn)題,而對(duì)實(shí)際事件日志進(jìn)行過(guò)程挖掘和分析時(shí)面對(duì)的質(zhì)量問(wèn)題不可能是單一的,這就需要對(duì)原始事件日志進(jìn)行多方面處理得到“完美”的事件日志.因?yàn)椴煌罩绢A(yù)處理問(wèn)題有多種解決方案,所以若需對(duì)某一實(shí)際日志進(jìn)行多方面處理時(shí),怎么組合問(wèn)題的解決方案會(huì)產(chǎn)生最優(yōu)的結(jié)果是未來(lái)的一個(gè)研究方向.
5.2.5 事件日志預(yù)處理結(jié)果的可視化
目前許多事件日志預(yù)處理技術(shù)得到的結(jié)果都以特定的指標(biāo)來(lái)衡量,而一些結(jié)果可能需要專(zhuān)門(mén)的可視化,這樣用戶(hù)才能更為直接的觀察到對(duì)事件日志進(jìn)行處理的結(jié)果,從而基于用戶(hù)的反饋對(duì)技術(shù)進(jìn)行改進(jìn)以提高預(yù)處理結(jié)果的準(zhǔn)確性.
對(duì)事件日志進(jìn)行過(guò)程挖掘和分析對(duì)于企業(yè)、組織改進(jìn)工作流程以及提高工作效率有重要的幫助,但事件日志的質(zhì)量嚴(yán)重影響著過(guò)程挖掘和分析的結(jié)果,因此在進(jìn)行過(guò)程挖掘和分析前必須對(duì)事件日志數(shù)據(jù)進(jìn)行預(yù)處理以提高數(shù)據(jù)質(zhì)量從而提高挖掘結(jié)果的準(zhǔn)確性.本文首先介紹事件日志的相關(guān)概念,然后總結(jié)了事件日志中存在的若干質(zhì)量問(wèn)題.文中從五個(gè)角度出發(fā)總結(jié)目前對(duì)如何提高事件日志數(shù)據(jù)的質(zhì)量所進(jìn)行的研究,分別為:日志格式標(biāo)準(zhǔn)化、日志的合并、日志缺失值的處理、日志的噪音處理以及日志的軌跡聚類(lèi).最后就日志預(yù)處理研究中所面臨的挑戰(zhàn)和未來(lái)的研究方向進(jìn)行了展望.