袁云靜，王 菁，韓燕波，栗倩文，陳高建，焦博揚(yáng)

(北方工業(yè)大學(xué) 大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100144)

0 引言

隨著服務(wù)計(jì)算、云計(jì)算、物聯(lián)網(wǎng)、大數(shù)據(jù)等高新技術(shù)的快速發(fā)展與成熟，各個(gè)服務(wù)行業(yè)與領(lǐng)域涌現(xiàn)出大規(guī)模智能服務(wù)，人們的生活越來(lái)越依賴(lài)于互聯(lián)網(wǎng)提供的服務(wù)[1-2]，而服務(wù)系統(tǒng)中的細(xì)粒度原子服務(wù)難以滿(mǎn)足日益復(fù)雜的用戶(hù)需求。因此，服務(wù)組合受到科研人員的持續(xù)關(guān)注。在求解科研協(xié)作、遠(yuǎn)程醫(yī)療、城市應(yīng)急等應(yīng)用領(lǐng)域問(wèn)題過(guò)程中，服務(wù)組合邏輯往往難以預(yù)先定義完備，需要在用戶(hù)參與過(guò)程中不斷調(diào)整，支持邊執(zhí)行邊構(gòu)造的探索式服務(wù)組合[3]應(yīng)運(yùn)而生。在探索式服務(wù)組合過(guò)程中產(chǎn)生了大量的服務(wù)組合流程，充分利用這些歷史數(shù)據(jù)可以增強(qiáng)服務(wù)組合流程的可重用性，提高服務(wù)組合效率。

通過(guò)分析總結(jié)探索式服務(wù)組合形成的服務(wù)組合流程，發(fā)現(xiàn)用戶(hù)選擇服務(wù)具有一定共性，某些服務(wù)經(jīng)常共同出現(xiàn)在一個(gè)服務(wù)組合流程軌跡中，這些固定搭配的服務(wù)往往以子片段的形式出現(xiàn)，表現(xiàn)出粒度大、復(fù)用性高等特征，文獻(xiàn)[4]將這種被高頻使用的服務(wù)搭配稱(chēng)為服務(wù)模式。由于探索式服務(wù)組合流程的執(zhí)行軌跡分為兩種，其對(duì)應(yīng)的服務(wù)模式也分為成功服務(wù)模式和失敗服務(wù)模式兩種，將這兩種服務(wù)模式應(yīng)用于探索式服務(wù)組合，一方面可以提高用戶(hù)構(gòu)造服務(wù)組合流程的效率，另一方面可以充分利用領(lǐng)域先驗(yàn)知識(shí)，提高服務(wù)組合流程的可重用性。而當(dāng)前工作大多只關(guān)注成功服務(wù)模式的挖掘，尚未有對(duì)失敗服務(wù)模式挖掘的研究，相應(yīng)歷史數(shù)據(jù)的價(jià)值沒(méi)有得到充分發(fā)揮。如果將成功服務(wù)模式的挖掘方法直接運(yùn)用于失敗服務(wù)模式的挖掘，會(huì)造成不必要的時(shí)間與資源浪費(fèi)，原因是在流程軌跡中，只有一部分流程片段最終導(dǎo)致執(zhí)行失敗，而非整個(gè)軌跡都是失敗的，因此將挖掘聚焦于失敗部分可提高挖掘效率。

針對(duì)上述問(wèn)題，本文提出探索式服務(wù)組合流程實(shí)例建模及服務(wù)模式建模方法，設(shè)計(jì)了一種擴(kuò)展gSpan算法的增量式失敗服務(wù)模式挖掘算法(Incremental Failure Service Pattern Mining Algorithm, IFSPMA)，通過(guò)所提模型與算法，可增量式地挖掘出服務(wù)組合流程執(zhí)行失敗軌跡中的失敗服務(wù)模式，實(shí)驗(yàn)表明，相比原始算法，IFSPMA明顯提高了挖掘效率。

1 相關(guān)工作

1.1 基于日志的服務(wù)模式挖掘

基于日志的服務(wù)模式挖掘算法主要有4種：

(1)α及其擴(kuò)展算法[5]該算法掃描日志中的所有實(shí)例，抽象活動(dòng)之間的基本關(guān)系，根據(jù)基本關(guān)系的類(lèi)型直接構(gòu)造流程的控制流結(jié)構(gòu)，其雖然能夠處理各種控制流結(jié)構(gòu)，但是無(wú)法處理日志中的噪聲。

(2)啟發(fā)式算法[6]該算法主要考慮流程實(shí)例在日志中出現(xiàn)的頻率，其雖然既可以挖掘流程的主要行為，也可以處理日志噪聲，但是忽略了流程細(xì)節(jié)，而且無(wú)法處理日志多樣性并進(jìn)行質(zhì)量監(jiān)控。

(3)遺傳算法[7]該算法是一種模擬生物進(jìn)化過(guò)程的搜索技術(shù)，能夠同時(shí)處理各種控制流結(jié)構(gòu)和日志噪聲，但可能得不到最優(yōu)的流程模型。

(4)基于日志分類(lèi)的算法 該算法對(duì)日志中的執(zhí)行實(shí)例進(jìn)行聚類(lèi)[8]，將日志劃分為多個(gè)子日志，借助已有挖掘算法對(duì)子日志進(jìn)行挖掘，該算法能夠很好地處理日志的多樣性，但是依賴(lài)現(xiàn)有具體挖掘算法。

1.2 基于流程的服務(wù)模式挖掘

基于流程的服務(wù)模式挖掘可抽象為頻繁子圖挖掘，其解決方式主要采用Apriori算法和FP-growth算法兩種算法思想。

應(yīng)用Apriori思想的挖掘算法有基于Apriori的圖挖掘(Apriori-based Graph Mining, AGM)算法[9]和基于該算法的改進(jìn)算法，AGM算法思路簡(jiǎn)單，以遞歸統(tǒng)計(jì)為基礎(chǔ)，可挖掘出所有頻繁子圖，但對(duì)大型數(shù)據(jù)庫(kù)的執(zhí)行效率較低。其改進(jìn)算法有頻繁子圖(Frequent Subgraph, FSG)算法[10]和基于Apriori的連通圖挖掘(Apriori-based connected Graph Mining, AcGM)算法[11]，這兩種算法的執(zhí)行效率較AGM算法均有提高。文獻(xiàn)[12]采用Apriori算法思想設(shè)計(jì)了一種輔助服務(wù)組合發(fā)現(xiàn)的挖掘算法。

FP-growth算法[13-14]將數(shù)據(jù)壓縮到頻繁模式樹(shù)中，存儲(chǔ)項(xiàng)的關(guān)聯(lián)關(guān)系，然后對(duì)模式樹(shù)產(chǎn)生頻繁集，其因?yàn)闊o(wú)需產(chǎn)生候選頻繁集，所以執(zhí)行效率高于Apriori算法?；谶@一算法思想的頻繁子圖挖掘算法包括gSpan算法[15]、快速頻繁子圖挖掘(Fast Frequent Subgraph Mining, FFSM)算法[16]等，其中g(shù)Span算法的最右路徑擴(kuò)展與頻繁剪枝策略，大幅降低了算法運(yùn)行時(shí)間；FFSM算法在計(jì)算支持度時(shí)，只對(duì)embedding set進(jìn)行掃描，提高了計(jì)算速度與效率，但其無(wú)法支持有向圖的挖掘。LIU等[17]借助FP-growth算法思想從歷史服務(wù)組合挖掘服務(wù)模式來(lái)研究服務(wù)選擇算法優(yōu)化。

以上服務(wù)模式挖掘的相關(guān)工作均是針對(duì)構(gòu)建成功的服務(wù)組合流程的挖掘方法，尚未考慮文獻(xiàn)[18]探索式服務(wù)組合中帶有調(diào)試點(diǎn)的失敗流程軌跡，且其挖掘往往針對(duì)整個(gè)服務(wù)組合流程，易對(duì)時(shí)間與資源產(chǎn)生不必要的浪費(fèi)。因此，本文綜合考慮當(dāng)前服務(wù)模式挖掘的特點(diǎn)及其存在的問(wèn)題，采用基于流程的服務(wù)模式挖掘算法，鑒于這類(lèi)可選算法的挖掘效率及可實(shí)現(xiàn)性，最終選擇基于gSpan算法進(jìn)行改進(jìn)，以支持對(duì)包含調(diào)試點(diǎn)的失敗服務(wù)模式的挖掘。

1.3 增量式更新

增量式更新的相關(guān)工作主要有增量式關(guān)聯(lián)規(guī)則挖掘、增量式頻繁子圖挖掘。FENG等[19]針對(duì)原始數(shù)據(jù)庫(kù)不變、最小支持度和置信度改變時(shí)，如何生成新的關(guān)聯(lián)規(guī)則，提出增量式更新算法(Incremental Updating Algorithm, IUA)和并行增量式更新算法(Parallel Incremental Updating Algorithm, PIUA)；CHEUNG等[20]針對(duì)最小支持度和置信度不變、數(shù)據(jù)庫(kù)發(fā)生改變時(shí)，如何生成新數(shù)據(jù)庫(kù)的關(guān)聯(lián)規(guī)則，提出快速更新(Fast Update, FUP)算法；XU等[21]研究在原始數(shù)據(jù)與最小支持度、置信度同時(shí)發(fā)生變化時(shí)關(guān)聯(lián)規(guī)則的更新問(wèn)題；CHAE等[22]對(duì)頻繁子圖挖掘算法gSpan進(jìn)行了增量式挖掘，將增量式gSpan應(yīng)用于動(dòng)態(tài)圖包分類(lèi)，并隨時(shí)間推移逐步更新top-m最具辨別力的特征。雖然當(dāng)前增量式更新已有較多研究，但是尚未發(fā)現(xiàn)在服務(wù)領(lǐng)域的應(yīng)用。本文結(jié)合所使用的失敗服務(wù)模式挖掘算法，在文獻(xiàn)[22]增量式gSpan研究的基礎(chǔ)上進(jìn)行改進(jìn)，使其適應(yīng)服務(wù)模式挖掘的應(yīng)用環(huán)境。

2 服務(wù)模式模型

本章主要對(duì)探索式服務(wù)組合實(shí)例及服務(wù)模式進(jìn)行形式化建模。

2.1 探索式服務(wù)組合實(shí)例模型

探索式服務(wù)組合可支持業(yè)務(wù)用戶(hù)對(duì)不完備的服務(wù)組合流程進(jìn)行邊執(zhí)行邊構(gòu)造，在構(gòu)造執(zhí)行過(guò)程中遇到執(zhí)行結(jié)果不正確或中間產(chǎn)生數(shù)據(jù)不滿(mǎn)意的情況時(shí)，可在相應(yīng)節(jié)點(diǎn)處添加調(diào)試點(diǎn)，派生新的軌跡，然后繼續(xù)構(gòu)造，直到探索出一條可完成目標(biāo)任務(wù)的成功路徑。探索式服務(wù)組合實(shí)例模型如圖1所示。

定義1探索式服務(wù)組合實(shí)例。探索式服務(wù)組合實(shí)例表示為一個(gè)三元組Instance=instanceID,name,trackSet，描述通過(guò)服務(wù)組合流程實(shí)例實(shí)現(xiàn)某些目標(biāo)的探索性過(guò)程。其中，instanceID為探索式服務(wù)組合實(shí)例的唯一標(biāo)識(shí)符；name為探索式服務(wù)組合實(shí)例的名稱(chēng)；trackSet為實(shí)例中包含的軌跡集合。

定義2軌跡。軌跡表示為T(mén)rack=trackProfile,instanceID,status,activities,transitions,directDeriv,dataPocket,exploredState，其中：trackProfile為軌跡基本信息，包括trackID,name,createTime等；instanceID為軌跡所屬實(shí)例；status為軌跡的執(zhí)行狀態(tài)，status∈{init,running,suspend,complete,terminated}；activities為軌跡中包含的活動(dòng)；transitions為軌跡中所包含活動(dòng)間的變遷關(guān)系；directDeriv在派生關(guān)系中定位原始軌跡，directDeriv=originalTrack,probePoint，originalTrack標(biāo)記當(dāng)前派生軌跡的父軌跡，probePoint標(biāo)記派生時(shí)原始軌跡中的調(diào)試點(diǎn)(添加調(diào)試點(diǎn)操作參見(jiàn)定義5，派生關(guān)系參見(jiàn)定義6)；dataPocket為軌跡執(zhí)行產(chǎn)生的數(shù)據(jù)信息；exploredState為探索完成后的軌跡狀態(tài)，exploredState∈{success,failure}。

定義3活動(dòng)?；顒?dòng)表示為Activity=activityID,activityName,Input,Output,QoS,type,status，其中：activityID為活動(dòng)的唯一標(biāo)識(shí)；activityName為活動(dòng)名稱(chēng)；Input為輸入?yún)?shù)集合；Output為輸出參數(shù)集合；QoS為活動(dòng)質(zhì)量；type為活動(dòng)類(lèi)型，type∈{service,start,end,orSplit,orJoin,andSplit,andJoin}；status為活動(dòng)執(zhí)行狀態(tài)，status∈{init,running,suspend,executed}。

定義4變遷關(guān)系。變遷關(guān)系表示為T(mén)ransition=tranID,fromAct,toAct,dataMappingSet，其中：tranID為變遷關(guān)系的唯一標(biāo)識(shí)；fromAct為變遷關(guān)系源活動(dòng)；toAct為變遷關(guān)系目標(biāo)活動(dòng)；dataMappingSet為源活動(dòng)和目標(biāo)活動(dòng)之間的數(shù)據(jù)映射關(guān)系集合，每個(gè)數(shù)據(jù)映射可表示為dataMapping=SourcePara,TargetPara,mappingExpression，SourcePara為源節(jié)點(diǎn)的輸入和輸出參數(shù)的集合，TargetPara為目標(biāo)節(jié)點(diǎn)的輸入?yún)?shù)的集合，mappingExpression為SourcePara和TargetPara之間的參數(shù)映射關(guān)系表達(dá)式。

定義5添加調(diào)試點(diǎn)操作。添加調(diào)試點(diǎn)操作記為addProbePoint(pt,a),其中pt為軌跡，a為活動(dòng)，只有pt的狀態(tài)不是terminated且a的狀態(tài)為executed，才允許添加調(diào)試點(diǎn)。該操作會(huì)生成新的軌跡pt′，其變遷關(guān)系的dataMappingSet及調(diào)試點(diǎn)a的前繼活動(dòng)均從原始軌跡克隆且保持不變，調(diào)試點(diǎn)a及其后繼活動(dòng)克隆后重置初始化。

定義6派生關(guān)系。派生關(guān)系是一個(gè)二元單向關(guān)系dr(tr1,tr2)，其中tr1為原始軌跡，tr2為派生軌跡。如果兩個(gè)流程片斷分別表示流程軌跡tr1和tr2中從開(kāi)始節(jié)點(diǎn)的可達(dá)流程片斷，滿(mǎn)足：①流程片斷中活動(dòng)的名稱(chēng)、輸入輸出參數(shù)，以及參數(shù)值、類(lèi)型等完全相同，且狀態(tài)均為executed；②流程片斷中變遷關(guān)系的源活動(dòng)、目標(biāo)活動(dòng)及活動(dòng)之間的數(shù)據(jù)映射關(guān)系完全相同。則稱(chēng)這兩個(gè)可達(dá)流程片斷相同。如果兩個(gè)軌跡共享相同的可達(dá)流程片段，則其為派生關(guān)系，其中createTime較小的軌跡為原始軌跡，另一個(gè)為派生軌跡。

軌跡間的派生關(guān)系如圖2所示，包括3條軌跡tr1～tr3和12個(gè)服務(wù)節(jié)點(diǎn)S1～S12，其中：tr1為原始軌跡，S2為原始軌跡中的調(diào)試點(diǎn)，從該點(diǎn)派生出軌跡tr2，片斷S1為原始軌跡tr1和tr2的相同可達(dá)流程片斷；以tr2為原始軌跡，S7為調(diào)試點(diǎn)，派生出軌跡tr3，片斷S1→S5→S6為其相同的可達(dá)流程片斷。

2.2 服務(wù)模式模型

探索式服務(wù)組合實(shí)例執(zhí)行完成后，可確定成功流程軌跡與失敗流程軌跡，對(duì)這兩種軌跡進(jìn)行挖掘可得兩種不同的服務(wù)模式。

定義7服務(wù)模式。服務(wù)模式表示為SP={spID，activities,transitions,type}，其中：spID為服務(wù)模式唯一標(biāo)識(shí)；activities為服務(wù)模式包含的活動(dòng)；transitions為活動(dòng)間存在的變遷關(guān)系；type為服務(wù)模式的類(lèi)型，type∈{success，failure}。

3 增量式失敗服務(wù)模式挖掘算法

為了從服務(wù)組合流程的失敗流程軌跡中挖掘出失敗服務(wù)模式，并適應(yīng)服務(wù)組合流程數(shù)量不斷增加的探索式服務(wù)組合環(huán)境，本文提出IFSPMA，該算法將挖掘范圍限定在調(diào)試點(diǎn)附近，對(duì)執(zhí)行失敗的軌跡進(jìn)行挖掘。首先將輸入的失敗流程軌跡集T抽象為圖集P，將軌跡上調(diào)試點(diǎn)前面的頂點(diǎn)標(biāo)記為成功點(diǎn)，調(diào)試點(diǎn)后面的頂點(diǎn)標(biāo)記為失敗點(diǎn)(算法1第1行)；然后基于頻繁度對(duì)P中的頂點(diǎn)與邊排序，刪除非頻繁頂點(diǎn)與邊(算法1第2～3行)，將剩余頻繁邊以深度優(yōu)先搜索(Depth First Search, DFS)的字典序排序(算法第5行)；最后，為挖掘得到失敗服務(wù)模式，要求頻繁子圖中必須包含至少一個(gè)調(diào)試點(diǎn)或失敗點(diǎn)，因此僅針對(duì)圖3中的3種頻繁邊進(jìn)行Subgraph_Mining最右路徑擴(kuò)展挖掘(算法第8行)，將擴(kuò)展后形成的DFS編碼樹(shù)作為中間結(jié)果保存，用于后續(xù)增量式挖掘。完成一條邊的擴(kuò)展挖掘后，從原圖刪去挖掘過(guò)的這條邊(算法第12行)，繼續(xù)擴(kuò)展挖掘下一個(gè)滿(mǎn)足條件的頻繁邊的子圖，重復(fù)該過(guò)程，直到遍歷完所有滿(mǎn)足條件的頻繁邊。該過(guò)程實(shí)例如圖4所示。

IFSPMA的增量式挖掘部分介紹如下：如果當(dāng)前服務(wù)庫(kù)中不存在服務(wù)模式，如圖5所示的t=0時(shí)刻算法過(guò)程，將DFS編碼樹(shù)中支持度大于minSup的節(jié)點(diǎn)作為頻繁子圖輸出，并經(jīng)篩選得到失敗服務(wù)模式存入服務(wù)庫(kù)；如果當(dāng)前服務(wù)庫(kù)中已有服務(wù)模式(算法1第15行)，則合并當(dāng)前時(shí)刻(假設(shè)為t+1時(shí)刻)增量DFS編碼樹(shù)與t時(shí)刻DFS編碼樹(shù)，將同時(shí)存在于兩棵樹(shù)中的節(jié)點(diǎn)支持度相加作為t+1時(shí)刻該節(jié)點(diǎn)的支持度，將僅存在于t+1時(shí)刻增量DFS編碼樹(shù)與僅存在于t時(shí)刻DFS編碼樹(shù)中的節(jié)點(diǎn)直接拷貝到t+1時(shí)刻DFS編碼樹(shù)中(算法1第16～21行)；最后，根據(jù)minSup對(duì)DFS編碼樹(shù)進(jìn)行剪枝得到所有頻繁子圖(算法1第22～24行)，篩選后得到失敗服務(wù)模式。

該失敗服務(wù)模式增量式挖掘原理圖如圖5所示。

算法1IFSPMA。

輸入:軌跡集T、t時(shí)刻的DFS編碼樹(shù)t_dct、最小支持度minSup。

輸出:失敗服務(wù)模式集合FS。

1: 將T抽象為圖集P并標(biāo)記成功點(diǎn)與失敗點(diǎn);

2: 通過(guò)頻繁度對(duì)P中的頂點(diǎn)與邊進(jìn)行排序;

3: 移除非頻繁頂點(diǎn)與邊;

4:FS1←P中的頻繁1子圖;

5: 以DFS字典序?yàn)镕S1排序;

6:FS←FS1;

7: for FS1中的每條邊e do

8: if e.from和e.to均為失敗點(diǎn)

or e.from為調(diào)試點(diǎn)，且e.to為失敗點(diǎn)

or e.to為調(diào)試點(diǎn):

9: incremental_dct←incremental_dct∪{e};

10: 初始化s為e, 設(shè)置s.P為包含e的圖集;

11: FS←Subgraph-Mining(P,FS,s,minSup);

12: P←P-e;

13: if |P|

14: break;

15:if t_dct不為空:

16: for increment_dct中的每一個(gè)DFS編碼c do

17: if c在t_dct中:

18: 重新計(jì)算c.support，并將更新后的c寫(xiě)入t1_dct中;

19: else:

20: 直接將c寫(xiě)入t1_dct中;

21: 將t_dct中剩余的DFS編碼寫(xiě)入t1_dct中;

22: for t1_dct中的每一個(gè)DFS編碼c do

23: if c.support >=minSup:

24: FS←FS∪{c};

25:FS←FS中的頻繁閉子圖;

26: return FS

子過(guò)程調(diào)用1子圖挖掘。

輸入: 圖集P、頻繁子圖集合Q、頻繁片段s、最小支持度minSup。

輸出:頻繁子圖集合Q。

1: if s≠min(s):

2: returnQ;

3: if t_dct不為空:

4: Q←Q∪{s};

5: 遍歷P中包含s的每個(gè)圖，并擴(kuò)展得到包含s的子圖;

6: for擴(kuò)展得到的每個(gè)子圖c do

7: incremental_dct←incremental_dct∪{c};

8: if support(c)≥minSup:

9: s←c;

10: Q←Subgraph-Mining(Ps,Q,s);

4 實(shí)驗(yàn)

4.1 數(shù)據(jù)集與環(huán)境

本節(jié)采用仿真實(shí)驗(yàn)評(píng)估IFSPMA的性能和有效性。為提高實(shí)驗(yàn)的可信度，本文采用myexperiment(www.myexperiment.org)研究社區(qū)爬取的1 405個(gè)流程作為實(shí)驗(yàn)數(shù)據(jù)集，其為該社區(qū)訪問(wèn)量和下載量最高的xml與t2flow格式的數(shù)據(jù)集。該社區(qū)是供全球生物計(jì)算研究者發(fā)布并共享生物計(jì)算流程及實(shí)驗(yàn)計(jì)劃等信息的一個(gè)協(xié)作環(huán)境，學(xué)者們可以在社區(qū)中發(fā)布其流程和實(shí)驗(yàn)，與小組分享，也可以找到其他人的流程，從而減少實(shí)驗(yàn)時(shí)間，避免流程再造。

為滿(mǎn)足算法需要，本文將收集到的生物流程文件進(jìn)行解析，將服務(wù)抽象為頂點(diǎn)，服務(wù)名稱(chēng)設(shè)為頂點(diǎn)標(biāo)簽，服務(wù)之間的關(guān)聯(lián)關(guān)系抽象為邊，為獲得更多的頻繁服務(wù)模式，將統(tǒng)計(jì)出的最頻繁的16個(gè)活動(dòng)節(jié)點(diǎn)設(shè)為調(diào)試點(diǎn)。由于從網(wǎng)站上爬取的流程均可成功執(zhí)行，本文通過(guò)程序模擬構(gòu)造失敗流程軌跡，共構(gòu)造10 490個(gè)流程軌跡，用于IFSPMA實(shí)驗(yàn)驗(yàn)證。

仿真程序用Anaconda 3.6和Pycharm開(kāi)發(fā)，運(yùn)行在一臺(tái)CPU為AMD Ryzen 7 2.90 GHz、內(nèi)存為16 G的Windows操作系統(tǒng)PC機(jī)上。

4.2 實(shí)驗(yàn)驗(yàn)證

實(shí)驗(yàn)主要觀察在挖掘準(zhǔn)確度相同時(shí)，IFSPMA相比未使用增量式更新的失敗服務(wù)模式挖掘算法(Failure Service Pattern Mining Algorithm，F(xiàn)SPMA)及未將挖掘聚焦于調(diào)試點(diǎn)附近的gSpan算法挖掘效率的提升情況，3種算法的對(duì)比說(shuō)明如表1所示。實(shí)驗(yàn)主要分析在挖掘準(zhǔn)確度相同時(shí)，不同的最小支持度、軌跡數(shù)量、挖掘結(jié)果個(gè)數(shù)對(duì)算法運(yùn)行時(shí)間的影響。

表1 算法對(duì)比說(shuō)明

算法參數(shù)主要為最小支持度和軌跡數(shù)量，如圖6所示，在軌跡數(shù)量固定為10 000的條件下，調(diào)整最小支持度，針對(duì)FSPMA與gSpan算法，在挖掘結(jié)果完全相同時(shí)，前者的運(yùn)行時(shí)間明顯低于后者，當(dāng)minSup=10時(shí)，F(xiàn)SPMA與gSpan算法的挖掘效率均處于較優(yōu)狀態(tài)。

選取minSup=10，分析不同軌跡數(shù)量下的運(yùn)行時(shí)間，如圖7所示。當(dāng)軌跡數(shù)以1 000為單位增長(zhǎng)，挖掘準(zhǔn)確度基本相同時(shí)(誤差極小可忽略)，IFSPMA的運(yùn)行時(shí)間明顯低于FSPMA和gSpan算法。

挖掘到的服務(wù)模式個(gè)數(shù)也可能會(huì)影響IFSPMA的運(yùn)行時(shí)間，當(dāng)minSup=10時(shí)，不同算法挖掘相同服務(wù)模式個(gè)數(shù)所用的運(yùn)行時(shí)間如圖8所示?？梢?jiàn)，隨著挖掘到的服務(wù)模式個(gè)數(shù)的增長(zhǎng)，IFSPMA的運(yùn)行時(shí)間比gSpan算法明顯降低，比FSPMA算法有所降低。

綜上所述，IFSPMA可有效將挖掘聚焦于生成失敗服務(wù)模式，避免gSpan算法面向整個(gè)服務(wù)組合流程的挖掘方式，而且算法可適應(yīng)不斷增量的探索式服務(wù)組合環(huán)境。在不同的最小支持度和軌跡數(shù)量下，IFSPMA的挖掘效率較其他兩種算法均有提升，其中在當(dāng)前數(shù)據(jù)集下，minSup=10時(shí)，IFSPMA的效率比gSpan算法提高得最多；隨著軌跡數(shù)量的增加，IFSPMA效率相比FSPMA提高的百分比穩(wěn)定在40%左右，相比gSpan提高的百分比穩(wěn)定在67%左右。

5 結(jié)束語(yǔ)

本文重點(diǎn)討論了從執(zhí)行失敗的服務(wù)組合流程軌跡中增量式挖掘失敗服務(wù)模式的相關(guān)研究。針對(duì)探索式服務(wù)組合的特點(diǎn)，為加快用戶(hù)探索式構(gòu)建服務(wù)組合流程的速度與準(zhǔn)確度，同時(shí)充分利用歷史服務(wù)組合流程數(shù)據(jù)，提出一種擴(kuò)展gSpan算法的改進(jìn)算法——IFSPMA，用于挖掘探索式服務(wù)組合流程中調(diào)試點(diǎn)附近失敗流程軌跡的服務(wù)模式，在此基礎(chǔ)上研究增量式挖掘，動(dòng)態(tài)更新服務(wù)庫(kù)中的服務(wù)模式。另外，根據(jù)問(wèn)題及算法特點(diǎn)，定義了探索式服務(wù)組合實(shí)例模型與失敗服務(wù)模式模型，作為IFSPMA的基礎(chǔ)。通過(guò)用模擬數(shù)據(jù)集對(duì)算法進(jìn)行實(shí)驗(yàn)評(píng)估，將IFSPMA與非增量的FSPMA算法和未聚焦于調(diào)試點(diǎn)的gSpan算法進(jìn)行對(duì)比，驗(yàn)證了本文方法的有效性和實(shí)用性。

未來(lái)將研究歷史服務(wù)模式的失效問(wèn)題，淘汰過(guò)時(shí)的服務(wù)模式，并結(jié)合服務(wù)模式的更新迭代分析歷史庫(kù)中的服務(wù)模式，觀察其演化趨勢(shì)。