王 笑，徐漢川，王忠杰，涂志瑩，徐曉飛

(哈爾濱工業(yè)大學 計算學部，黑龍江 哈爾濱 150001)

0 引言

隨著大數(shù)據(jù)、云計算、物聯(lián)網(wǎng)等理論和技術的快速發(fā)展，Internet上可用的軟件服務越來越多，現(xiàn)實中的各類物理資源及人工服務也通過虛擬化和物聯(lián)網(wǎng)技術被接入Internet,并與線上的軟件服務建立協(xié)同和集成，這兩個趨勢使互聯(lián)網(wǎng)上的可用服務數(shù)量急劇增加。與此同時，客戶需求也越來越傾向于大粒度和個性化，涉及到的應用業(yè)務與數(shù)據(jù)體現(xiàn)出很強的復雜性、關聯(lián)性與跨界性，單一的服務往往難以滿足此類需求，通常需要多項服務的集成。這種跨越大量領域、服務、業(yè)務流程和規(guī)則的服務生態(tài)系統(tǒng)構成了服務互聯(lián)網(wǎng)或大服務[1-2]，其中用戶對服務的需求海量且個性化，服務資源數(shù)量眾多且跨領域，需要在海量需求和服務間進行服務匹配，通過聚合不同領域的服務，產(chǎn)生復合服務解決方案，以滿足用戶需求。例如，養(yǎng)老服務中，某老人患有糖尿病，不愿接受到養(yǎng)老院養(yǎng)老，而子女白天上班，無法照顧老人。通過構建服務解決方案，可以將護工預約、護工日常護理、健康商城、老人健康檔案、慢病管理、醫(yī)院就醫(yī)等跨領域和組織的服務整合在一起提供給老人，滿足老人的居家養(yǎng)老需求。因此，如何高效構建用戶滿意的服務方案是服務互聯(lián)網(wǎng)中服務設計和優(yōu)化的核心問題。

服務方案構建的核心問題是在可用服務與用戶需求間建立匹配關系，即服務供需雙邊匹配。研究人員已對服務供需匹配問題進行了大量研究，傳統(tǒng)服務組合[3]和服務選擇[4]技術將每個用戶需求視為獨立的個體，以某個或某些目標最優(yōu)化為目標，在滿足約束的前提下，根據(jù)現(xiàn)有可用服務構造出用戶滿意的優(yōu)化服務解決方案。典型方法包括精確算法[5-6]、演化算法[7-11]、基于深度學習的算法[12-13]以及將服務組合問題轉(zhuǎn)化為經(jīng)典規(guī)劃問題[14-15]與基于圖的方法[16-17]。CHATTOPADHYAY[18]對服務組合問題提出一種近似機制來獲得接近于最優(yōu)解的時間。RODRIGUEZ-MIER等[6]提出一種使用精確算法的方法，該方法使用一種混合的局部—全局策略來優(yōu)化QoS感知服務組合問題。HAYTAMY等[10]提出一個基于深度學習的服務組合框架，該框架融合了長短期記憶人工神經(jīng)網(wǎng)絡(Long Short-Term Memory, LSTM) 和粒子群優(yōu)化算法。ZHOU等[8]在云制造領域中提出了解決多目標服務組合問題的自適應多種群差分人工蜂群算法。但是，在服務互聯(lián)網(wǎng)場景下，用戶需求和服務資源數(shù)量龐大，算法搜索空間巨大，現(xiàn)有的服務組合和服務選擇技術難以高效快速地得到滿足大規(guī)模個性化用戶需求的服務方案。經(jīng)過大量的實踐觀察和分析，發(fā)現(xiàn)服務與服務間、需求與需求間均存在相似性和關聯(lián)性，某些領域服務也會頻繁地在一起關聯(lián)使用，如淘寶購物服務中，用戶只能選擇支付寶服務，而在京東購物服務中，只能選擇微信或者京東錢包服務。這類相似性與關聯(lián)性是領域服務先驗知識的一種體現(xiàn)，如果能夠挖掘出蘊含其中的關聯(lián)關系，將歷史上成功的可復用服務解決方案(服務模式)和用戶經(jīng)常提出的關聯(lián)需求(需求模式)用于服務方案的構建和用戶需求聲明中，則可以將服務匹配的粒度從小粒度的原子服務和需求提升為大粒度的構建模塊，有效縮減搜索空間，提升用戶滿意度。如果可刻畫服務模式與需求模式間的關聯(lián)關系，則可以進一步提高服務匹配的效率，實現(xiàn)服務方案的快速高效構建。

在現(xiàn)有研究中，通過數(shù)據(jù)挖掘技術從歷史中挖掘模式已經(jīng)成為服務組合中一種主導的方法[19-20]。PERRYEA等[21]在基于社區(qū)的服務組合方法中，利用歷史上的復合解決方案盡可能地滿足新的需求。LIU等[22]使用FP-growth算法從歷史服務解決方案中挖掘服務模式。XU等[23]提出“需求—工程”(RE2SEP)兩段式服務開發(fā)范型，對服務模式進行了定義，并提出了將需求模式與服務模式通過情境信息進行匹配。雖然當前已經(jīng)有不少對服務模式的研究，但是對需求模式的研究還不足，只是根據(jù)用戶提出的需求使用服務模式進行服務組合或者服務選擇。同時，對于服務模式使用情境的研究較少，只是單純使用歷史出現(xiàn)的全部或部分服務流程進行復用。

另外，為了更好地理解用戶需求，需要提供一種表達能力強且易于用戶之間建模的需求模型。面向目標的建模技術常用于需求建模當中，ASADI等[24]提出一種基于描述邏輯的方法，在一個共同的知識庫中表達模型之間的關系。ROLLAND等[25]和YU[26]將目標模型應用與需求工程的系統(tǒng)分析和設計以及信息和軟件系統(tǒng)開發(fā)中。HORKOFF等[27]通過與功能和非功能目標的聯(lián)系來分析和證明模型的正確性。但是，這些方法沒有以服務開發(fā)為中心，而且必須對指定的目標模型進行人工分析，才能得到相應的候選服務[28]。同時，這些模型大多太過復雜，對于沒有建模經(jīng)驗的終端用戶，使用這些模型提出需求十分困難。

基于以上分析和思考，本文提出一種基于供需雙邊模式的服務方案高效匹配方法，其核心思想是挖掘領域先驗知識中服務間、需求間以及服務與需求間的關聯(lián)特征，利用模塊化的思想提升服務匹配中供需雙邊構建單元的粒度，從而提高服務匹配效率和用戶滿意度。本文首先建立了基于雙邊模式的服務匹配問題模型;之后針對用戶需求端，提出了基于意圖樹的需求和需求模式模型;針對服務提供端，提出了服務模式模型及挖掘策略;進而根據(jù)歷史服務方案中的用戶情境信息等內(nèi)容構建了多維雙邊模式關聯(lián)矩陣，并提出了關聯(lián)矩陣的適應性更新策略;最后，針對3種典型的服務場景，設計了不同類型的算法，驗證本文所提基于雙邊模式的匹配方法相較于傳統(tǒng)方法的有效性。

1 基于供需雙邊模式的服務匹配問題模型與方法框架

1.1 基于供需雙邊模式的服務匹配問題模型

本文采用的優(yōu)化策略是利用供需雙邊模式(服務模式與需求模式)及其關聯(lián)矩陣來縮小搜索空間，提高匹配效率，實現(xiàn)服務方案的高效快速構建。由于最小化問題和最大化問題可以等價轉(zhuǎn)化，服務互聯(lián)網(wǎng)中基于供需雙邊模式的服務匹配問題模型可定義如下：

minF(x)=(Gu(x),Gs(x),Gp(x))T。

(1)

s.t.

hi(x)≤0,i=1,2,…,uh;

(2)

cpj(x)>0,j=1,2,…,|SSP|;

(3)

sspk?sspl,k,l∈SSP。

(4)

其中決策變量x為服務方案，x=SSP,SEQ。其中：SSP為服務方案構造單元集合，由|SP|個服務模式sp和|S|個原子服務s構成，即ssp∈{sp1,sp2,…,sp|SP|,s1,s2…,s|s|}，|SSP|=|SP|+|S|;SEQ為服務方案中構造單元間執(zhí)行順序集合，SEQ={seqij|sspi需要在sspj之前執(zhí)行,sspi,sspj∈SSP}。式(1)為優(yōu)化目標函數(shù)向量，根據(jù)目標訴求方可分為用戶目標Gu(x)，服務提供商目標Gs(x)以及第三方平臺目標Gp(x)，根據(jù)優(yōu)化目標數(shù)量可以分為單目標、多目標以及超多目標(目標數(shù)量超過4個)優(yōu)化問題。每個目標的計算方式由目標本身和方案流程決定，服務系統(tǒng)的優(yōu)化目標通常包括時間、成本、資源利用率、可靠性、資源均衡利用等。式(2)為用戶需求中提出的約束，hi(x)≤0表示用戶提出的第i個約束，uh為約束數(shù)量，不等式中大于和小于可以相互轉(zhuǎn)化，以小于等于代指所有類型約束。式(3)為服務能力約束，cpj(x)為服務方案x中服務模式spj或原子服務sj當前服務能力值，所用服務的服務能力需要大于0。式(4)為順序約束，約束了服務流程中服務的先后順序，sspk?sspl表示服務模式spk或原子服務sk需要在服務模式spl或原子服務sl之前執(zhí)行。

1.2 問題求解框架

針對服務供需匹配問題，提出如圖1所示的求解框架。具體求解環(huán)節(jié)如下：

(1)在用戶需求端，維護歷史需求庫，并從中挖掘得到需求模式庫。

(2)在服務提供端，維護可用原子服務集，并從歷史服務方案中挖掘得到服務模式庫。

(3)構建雙邊模式關聯(lián)矩陣，利用服務日志中的歷史匹配記錄，得到需求模式與服務模式間的匹配關系。

(4)構建服務解決方案，針對特定需求，建立需求模型，對用戶需求進行匹配，得到一組能夠最優(yōu)匹配所提需求的需求模式。進一步通過關聯(lián)矩陣找到每個需求模式對應的一組服務模式，針對用戶提出的優(yōu)化目標，適應性地選擇優(yōu)化算法得到匹配的服務模式，最終構造一個滿足用戶需求的優(yōu)化服務方案。

其中：環(huán)節(jié)(1)～(3)為服務方案構造所需基礎數(shù)據(jù)準備階段，需要維護歷史需求庫、需求模式庫、原子服務庫、服務模式庫和雙邊模式關聯(lián)矩陣;環(huán)節(jié)(4)為針對特定需求構建服務方案環(huán)節(jié)。

2 供需雙邊模式與關聯(lián)矩陣

2.1 基于意圖樹的需求模型與需求模式

2.1.1 基于意圖樹的需求模型

在常用需求建模方法中，面向目標的建模技術因其具有形式直觀、易于理解、表達能力強、不需過多專業(yè)知識等優(yōu)點，被廣泛應用于需求工程中的需求建模[24,27]?；谀繕私５姆椒ɡ砟睿疚奶岢鲆环N基于意圖樹的需求模型iTree，

iTree=G,E

其中意圖樹iTree由意圖節(jié)點集合G={G1,G2,…,Gn}與意圖關聯(lián)關系集E構成。一個意圖樹節(jié)點Gi包括意圖、約束和優(yōu)化目標，Gi=intension,{constaint},{OptObjective}。意圖樹節(jié)點間的關聯(lián)關系有分解與依賴兩種。需求模型可以由用戶直接手工建立，也可以通過其他需求獲取的方式建立，如通過與用戶對話等方式。

如圖2所示為iTree模型中的元素及其關系，詳細介紹如下：

(1)User表示用戶。

(2)Role表示角色。一個用戶可以被分配不同的角色。

(3)Intension表示意圖。用戶通過意圖來描述自己的功能性需求。

(4)Decomposition表示分解。上層意圖可以分解為若干下層意圖。該關系有“與”和“或”兩種?！芭c”關系表示當下層意圖均被滿足時，上層意圖同時被滿足;“或”關系表示當任意一個下級意圖能被滿足時，上層意圖即可被滿足。

(5)Dependency表示依賴。同級意圖之間某意圖的實現(xiàn)依賴于另一意圖。

(6)Constraint表示約束。用戶通過約束來描述自己的非功能性需求。約束使用鍵值對定義：Cons=Conskey,Constype,Consvalue，分別表達約束名、約束數(shù)據(jù)類型和約束值。

(7)OptObjective表示優(yōu)化目標。用戶使用優(yōu)化目標表達自己的偏好，如解質(zhì)量優(yōu)先或求解速度優(yōu)先，此指標在服務方案構建時予以考慮。

圖3給出了一個居家老人日常生活需求的iTree模型實例。老人通過意圖樹表達自己的日常生活需求：老人需要找一名保姆、找一名家庭醫(yī)生并進行慢病管理、辦理健康檔案與居民健康一卡通、使用健康商城服務購買醫(yī)療用品。意圖樹中描述了老人對意圖的偏好和非功能性需求，如：老人對服務的偏好是最少花費；在家庭醫(yī)生服務意圖中，老人對非功能性需求進行了指定：花費在0～3 000元間，并進一步表達了自己的需求：需要與醫(yī)生交流、進行健康管理以及醫(yī)生隨訪服務。

2.1.2 基于意圖樹的需求模式

在大量的用戶需求中，某些需求中包含的意圖間存在較強的關聯(lián)性，這些關聯(lián)意圖集往往會在多個需求中被重復提出，這些頻繁出現(xiàn)的關聯(lián)意圖集體現(xiàn)了領域用戶需求的先驗知識，本文對其進行挖掘并刻畫為需求模式(RP)。需求模式是對用戶需求的模塊化描述，在用戶需求聲明過程中，利用需求模式，通過需求補全、推薦、重構等操作，可將碎片化和不精確的原始需求，快速完整地轉(zhuǎn)換為合理優(yōu)化的需求。進一步，將需求模式同服務模式關聯(lián)，形成供需雙邊模式關聯(lián)矩陣，增大匹配粒度，提高匹配效率，高效構建服務方案。

基于意圖樹的需求模式是由多棵子意圖樹組成的森林，RP=info,{iTreei}。其中：info表示需求模式的基本信息，如需求模式描述和使用頻率等;{iTreei}為意圖樹集合。在圖3所示的例子中，存在兩個需求模式，一個是“家庭醫(yī)生服務”，另一個是“慢病管理服務”，其中家庭醫(yī)生服務需求模式包含了醫(yī)生交流服務、健康管理服務、隨訪服務3個頻繁出現(xiàn)的子意圖以及指定家庭醫(yī)生服務的約束為花費在0～3 000元間。

需求模式的構建可以采用人工定義和自動挖掘兩種手段。自動挖掘包括兩個階段：

第一階段：頻繁意圖樹結構挖掘。該過程以挖掘頻繁樹結構為目標，考慮意圖與結構，不考慮約束。使用gSpan算法挖掘頻繁結構。

第二階段：需求模式挖掘。從需求全集中提取包含頻繁結構的子意圖樹，根據(jù)約束進行聚類，最后得到具有相同結構及意圖，但約束不同的需求模式。

由于篇幅限制，本文只簡要介紹需求模式挖掘算法思路，詳細算法以及如何利用需求模式進行需求的自動補全、推薦、重構等內(nèi)容將在后續(xù)論文進行描述。

2.2 面向關聯(lián)知識復用的服務模式

在服務互聯(lián)網(wǎng)環(huán)境下，服務之間存在著相似性和關聯(lián)性，即某些服務之間經(jīng)常會關聯(lián)在一起搭配使用，如第1章所述的京東商城和天貓商城的例子。本文對歷史服務方案和領域知識中，經(jīng)常被高頻使用的服務流程和服務搭配進行分析和挖掘，形成服務模式(SP)[29]。服務模式定義如下：

SP=SPinfo,SPfr,SPprocess,SPinstance。

其中：SPinfo表示服務模式的基本信息，如名稱、所屬領域等；SPfr描述了服務模式完成的功能；SPprocess描述服務流程，實現(xiàn)時可采用業(yè)務流程建模與標注(Business Process Modeling Notation, BPMN)格式描述和存儲；SPinstance是服務模式的實例集，SPinstance=S,SPQoS，其中：S為該服務模式實例綁定的服務集合，服務可以使用傳統(tǒng)的網(wǎng)絡服務的本體語言(Ontology Web Language for Services, OWL-S)或Web服務描述語言(Web Services Description Language, WSDL)等服務模型進行建模，SPQoS為服務模式實例的質(zhì)量指標信息。

如圖4所示為服務模式中的元素及其關系。

與利用原子服務構建服務方案相比，服務模式挖掘了歷史服務方案中成功的案例并將其重用，減少搜索空間，提高構建效率；此外，由于服務模式體現(xiàn)了領域先驗的服務使用知識，可以預先準備建立關聯(lián)，降低關聯(lián)成本；且服務模式是經(jīng)過實踐驗證的成功案例，可獲得更好的用戶滿意度。

在之前的研究中，已提出采用頻繁模式增長(Frequent Pattern growth, FP-growth)算法從服務系統(tǒng)的歷史日志中挖掘服務模式[22]。該算法包括兩個步驟：利用緊湊的數(shù)據(jù)結構FP-Tree，對日志進行壓縮，避免多次的數(shù)據(jù)庫掃描；使用FP-growth算法挖掘出頻繁的服務模式。

如圖5所示的服務模式為一個“慢病管理”服務模式的流程示例，內(nèi)含5個服務：慢病篩查服務、簽約服務、醫(yī)生咨詢服務、健康評估服務和應用健康卡服務。

2.3 供需雙邊模式關聯(lián)矩陣

2.3.1 關聯(lián)矩陣定義

通過2.1節(jié)和2.2節(jié)介紹的需求模式和服務模式，可以通過固化需求間和服務間的關聯(lián)關系，形成需求模式和服務模式，通過提升需求與服務的構建單元粒度，縮小搜索空間?？蛇M一步利用歷史服務方案中供需雙邊模式間的成功匹配先驗知識，構建雙邊模式間的多維概率關聯(lián)矩陣，支持服務方案構建中的快速搜索。該關聯(lián)矩陣由R,S,RP,SP,Context五個維度構成，其中：R為需求集合，S為服務集合，RP為需求模式集合，SP為服務模式集合，Context為情境信息集合。如圖6所示為供需雙邊模式關聯(lián)矩陣的示意圖，圖中：x軸為需求模式，y軸為服務模式，z軸為情境信息。

五個維度間存在多種關聯(lián)關系，需求模式與服務模式分別蘊含了需求間的關聯(lián)和服務間的關聯(lián)，本節(jié)重點闡述需求模式與服務模式在不同情境下的關聯(lián)關系，關聯(lián)關系的強弱通過匹配度pij∈[0,1)進行度量。

假設共有n個需求模式與m個服務模式，關聯(lián)矩陣定義如下。

(1)當情境ctk相同時，設需求模式rpi可以匹配mi個服務模式，aij為需求模式rpi與服務模式spj的匹配度。若二者不能匹配，則匹配度aij=0。由于每個需求模式只對應少量服務模式，mi通常遠小于m，故需求模式與服務模式之間關系可以表達為稀疏矩陣：

(5)

(2)當同一需求模式rpi所處的用戶情境不同時，其對應的服務模式也不同。設有c個情境信息，設bk,j為情境ctk時，需求模式rpi與服務模式spj的匹配度，若二者不能匹配，則匹配度bk,j=0。為簡單起見，本文設每個情境信息對應的候選服務模式都有m0個，則相應匹配關系可表達為稀疏矩陣：

(6)

2.3.2 用戶情境信息

在不同情境下，同一需求模式能夠匹配的服務模式可能不同。因此，在服務方案構建過程中，需要依據(jù)服務情境信息的不同，采用不同的策略和優(yōu)化方法，因此在關聯(lián)矩陣構建時，要考慮情境維度的信息。

本文所考慮的情境信息包括兩類：

(1)用戶情境，即用戶年齡、性別等自然信息以及用戶的職業(yè)、人際關系等群體信息。

(2)環(huán)境情境，即時間、地點等用戶提出需求時所處的環(huán)境。

采用鍵值對形式對情境進行建模，對于連續(xù)型情境，使用標準化歐氏距離度量兩個情境的相似程度,對于離散型情境，按照one-hot編碼規(guī)則轉(zhuǎn)換為連續(xù)型情境。由于抽象后的情境維度可能過高，本文使用主成分分析法(Principal Component Analysis, PCA)[31]進行降維。

2.3.3 雙邊模式匹配度計算

雙邊模式匹配度是需求模式在某情境下匹配服務模式的匹配概率。匹配度的計算需要考慮歷史、當前和未來3部分服務數(shù)據(jù)。因為歷史中使用次數(shù)較高的服務模式當前可能不會出現(xiàn)，且新需求模式，服務模式對存在冷啟動問題，服務模式的約束值也可能會發(fā)生變化，所以歷史和當前部分數(shù)據(jù)的匹配度計算需考慮包括時間衰減、約束滿足度和匹配次數(shù)3個參數(shù)。

(1)時間衰減Ti,表示第i次匹配的時間衰減程度,

Ti=1-e-(t0-ti)。

(7)

式中t0表示當前時間，ti表示第i次匹配時間點。

(2)約束滿足度Ci,表示第i次匹配時需求模式約束滿足程度，

(8)

式中：n為約束數(shù)量，cj為第j個約束的服務模式滿足度。對于枚舉值，滿足約束為1，不滿足為0；對于范圍值的情況，服務模式滿足度定義如下：

(9)

式中：wmin與wmax指需求模式中約束的最小值與最大值，w為約束的實際值。

(3)匹配次數(shù)記為N。

綜合3個參數(shù)，包含歷史和當前部分信息的匹配度

(10)

未來部分的匹配度pf需要結合特定領域?qū)ξ磥硇枨笈c服務的使用情況進行預測，有針對性地調(diào)整匹配度。

需求模式中每個子需求的預測值為pf,ri，則需求模式的預測值

其中：n為子需求的個數(shù);ai為子需求i的權值，本文認為需求模式中約束多的子需求為更重要的部分，在匹配度計算中權值越大，因此ai為子需求i約束的數(shù)量。同理，服務模式的預測值pf,s即為每個服務預測值的平均值。在實際應用中，可根據(jù)使用具體情境，采用對應的預測模型，獲得需求和服務的變化趨勢，設計預測值pf,ri的計算方法。綜上，包含歷史、當前和未來3個部分信息的匹配度

(11)

其中，由于歷史和當前部分可以同時考慮，統(tǒng)一用k1表示歷史和當前部分的權重;k2表示將來部分的權重，k2的大小與需求和服務預測的置信度有關，預測的置信度越低，k2越小。

將p歸一化即為最后得到的匹配度。

關聯(lián)矩陣在使用時，首先通過用戶情境信息找到Ak，再根據(jù)需求模式找到與其對應的服務模式集，經(jīng)過優(yōu)化得到最終的服務方案。如圖3的需求模型，用戶提出居家老人的日常生活意圖樹，假設其情境信息的一部分為60歲，哈爾濱，則根據(jù)其情境信息，就只會找到適合60歲且地點在哈爾濱的家庭醫(yī)生和慢病管理的服務模式。

2.4 供需雙邊模式關聯(lián)矩陣的構建與更新方法

2.4.1 供需雙邊模式關聯(lián)矩陣的構建算法

算法1雙邊模式關聯(lián)矩陣構建算法。

輸入:服務方案集合solution;

輸出:關聯(lián)矩陣A。

1 begin

2 用戶情境集合X=?;匹配時間點集合D=?;關聯(lián)矩陣A=?

3 foreach服務方案si∈solution do

4 foreach (rpj,spk)∈sido

/* X[(rpj,spk)]與D[(rpj,spk)]初始為空列表*/

5 X[(rpj,spk)]←X[(rpj,spk)]+ci//ci為si中用戶情境

6 D[(rpj,spk)]←D[(rpj,spk)]+ti//ti為si中匹配時間點

7 end

8 end

9 foreach (rpj,spk)∈X do

10 Cij←X[(rpj,spk)]

11 Tij←D[(rpj,spk)]

12 使用PCA算法對Cij降維

13 使用Birch算法對Cij聚類

14 計算匹配度，并將聚類結果與匹配度加入A中

15 end

16 返回A

17 end

2.4.2 供需雙邊模式關聯(lián)矩陣的更新策略

由實驗可知，當服務日志中總方案數(shù)量很多時，更新時間會達到1個小時甚至更多，關聯(lián)矩陣更新代價巨大。因此，需要根據(jù)總服務方案數(shù)量動態(tài)調(diào)整更新頻率，在更新效率與更新效果間進行均衡。本節(jié)根據(jù)關聯(lián)矩陣的特點針對性地提出了關聯(lián)矩陣的適應性更新策略，關聯(lián)矩陣在滿足一定條件時進行更新，以實時調(diào)整關聯(lián)矩陣的內(nèi)容。

(1)新增策略 該策略包含兩部分：

2)增加新的需求模式，服務模式。此時,在服務日志中找到新增模式的匹配情況，并更新關聯(lián)矩陣。

(3)服務質(zhì)量變化策略 服務質(zhì)量發(fā)生變化會導致匹配度中約束滿足度發(fā)生變化，這時也需要對關聯(lián)矩陣中的匹配度進行更新。

在關聯(lián)矩陣使用時，需定期判斷是否滿足上述策略。如滿足策略1或策略2，使用算法2對關聯(lián)矩陣進行更新；如滿足策略3，對使用該服務的需求模式，服務模式對的匹配度進行更新。當需求模式，服務模式對在某情境下的匹配度降低到某一閾值時，在匹配中不予考慮，視為該對失效，但在關聯(lián)矩陣中保留數(shù)據(jù)，隨關聯(lián)矩陣進行更新。

雙邊模式關聯(lián)矩陣的更新算法如算法2所示，從歷史記錄中取出需要更新的需求模式，服務模式對，讀取其PCA模型與Birch模型，將新的匹配記錄加入模型中并計算匹配度。

算法2雙邊模式關聯(lián)矩陣更新算法。

輸出:更新后的關聯(lián)矩陣A。

1 begin

2 用戶情境X′=?;匹配時間點D′=?

3 foreach服務方案si∈solution do

4 foreach(rpj,spk)∈sido

/* X′[(rpj,spk)]與D′[(rpj,spk)]初始為空列表*/

5 if(rpj,spk)∈rpsp and匹配時間點大于上次更新時間do

6 X′[(rpj,spk)]←X′[(rpj,spk)]+ci//ci為si中用戶情境

7 D′[(rpj,spk)]←D′[(rpj,spk)]+ti//ti為si中匹配時間點

8 end

9 end

10 foreach (rpj,spk)∈X′ do

13 if (rpi,spj)?X do

16 end else

17 Cij←X[(rpj,spk)]

20 計算匹配度，并將聚類結果與匹配度加入A中

21 end

22 返回A

23 end

3 基于供需雙邊模式的服務方案構建算法

服務方案構建算法的目標是獲得優(yōu)化的服務執(zhí)行方案Solution，

Solution=Info,SSP,Process,Q。

其中：Info為基本信息；SSP為方案中使用的服務模式SP與原子服務集合S；Process為服務流程；Q為質(zhì)量指標。如圖1所示，構建算法流程分為需求匹配、服務模式與原子服務選擇、生成服務流程3個步驟。

3.1 需求匹配方法

需求匹配的目標是利用歷史需求信息，使用需求模式去覆蓋意圖樹的過程。其結果包含可被需求模式匹配的意圖集(體現(xiàn)為對應的需求模式集)和不能被匹配的意圖集兩部分。

匹配算法采用基于優(yōu)先規(guī)則的迭代方式，逐步使用需求模式覆蓋意圖樹中未被覆蓋的意圖，即使需求模式中包含的意圖和需求樹中待匹配意圖完全相同，且需求模式中的約束包含待匹配意圖的約束。

需求匹配優(yōu)先規(guī)則的順序如下：

(1)優(yōu)先考慮覆蓋率更高的匹配方案；

(2)優(yōu)先考慮使用更少需求模式的匹配方案；

(3)優(yōu)先考慮需求模式平均使用頻率更高的匹配方案。

限于篇幅，匹配算法流程不再贅述。

3.2 構建服務方案

在得到需求模式集和單獨的意圖集之后，該環(huán)節(jié)基于雙邊模式關聯(lián)矩陣和服務的描述信息，利用算法得到優(yōu)化后的服務方案。

構建步驟分為以下兩個部分：

(1)對需求進行需求匹配。根據(jù)需求匹配的結果和匹配情境，從關聯(lián)矩陣中找到與各需求模式對應的匹配度較高的服務模式集，并在服務庫中找到與各單獨意圖對應服務功能的服務集。如果某需求模式找不到對應的服務模式，則對該需求模式利用更小粒度的需求模式進行需求匹配，并重復以上步驟。

(2) 在上述集合當中選擇合適的服務模式和服務，并構建服務流程。利用匹配算法，最終得到滿足約束且優(yōu)化目標最優(yōu)的服務方案。

由于在不同實際應用場景中，服務數(shù)量和需求數(shù)量規(guī)模不同，追求的質(zhì)量與效率的偏好不同，因此，本文提出3類算法，并將雙邊模式以及關聯(lián)矩陣融入其中：精確算法(Bilateral Pattern Precise Algorithm, BP-PA)，適用于數(shù)據(jù)規(guī)模較小且用戶需要最優(yōu)解的場景；貪心算法(Bilateral Pattern Approximation Algorithm, BP-AA)，適用于數(shù)據(jù)規(guī)模適中且用戶對算法效率要求較高的場景；人工蜂群算法(Bilateral Pattern Artificial Bee Colony Algorithm, BP-ABC)，適用于數(shù)據(jù)規(guī)模較大且用戶需要質(zhì)量較好解的場景。

BP-PA算法通過遍歷每個服務方案來獲得最優(yōu)解，在實際應用中通常使用各種不同的剪枝算法來提高運行速度，如：若當前遍歷的部分服務方案已經(jīng)劣于當前最優(yōu)方案，不再繼續(xù)對該部分服務方案的后續(xù)服務進行遍歷等。

BP-ABC算法(算法5)使用的可行性準則定義如下：如果解x1和解x2滿足以下3點之一，則稱解x1支配解x2：①解x1滿足約束而解x2不滿足約束；②解x1和解x2均不滿足約束，但x1總約束滿足度較大；③解x1和解x2均滿足約束，但解x1帕累托支配解x2。

算法3精確算法(BP-PA)。

輸入:用戶意圖樹iTree，需求模式集RP，服務模式集SP和原子服務集S，關聯(lián)矩陣A，用戶需求情境ctk;

輸出:最優(yōu)服務方案x*。

1 begin

2 x*←?

3 調(diào)用需求匹配算子reqMatch，利用RP覆蓋iTree，獲得需求匹配結果：需求模式集RP′，未能匹配的意圖集R′(見3.1節(jié))。

4 從A中根據(jù)ctk找到子矩陣Ak并根據(jù)RP′中各rpi找到對應的服務模式集SPi，在S中找到R′中意圖rj與服務功能對應的服務集Sj。

5 對SPi中服務模式以及Sj中原子服務按照優(yōu)化目標排序

6 foreach服務模式spim∈SPi與原子服務sjn∈Sjdo

7 調(diào)用服務流程構建算子constructingProcess獲得服務方案x

8 if x滿足約束且優(yōu)化目標優(yōu)于x*

9 x*←x

10 end else continue

11 end

12 返回x*

13 end

算法4貪心算法(BP-AA)。

輸入:用戶意圖樹iTree，需求模式集RP，服務模式集SP和原子服務集S，關聯(lián)矩陣A，用戶需求情境ctk;

輸出:最優(yōu)服務方案x*。

1 begin

2 x*←?; success←0; i←0;初始化循環(huán)次數(shù)N

3 調(diào)用需求匹配算子reqMatch，利用RP覆蓋iTree，獲得需求匹配結果：需求模式集RP′，未能匹配的意圖集R′(見3.1節(jié))。

4 從A中根據(jù)ck找到子矩陣Ak并根據(jù)RP′各rpi找到對應的服務模式集SPi，在S中找到R′中意圖rj與服務功能對應的服務集Sj。

5 對SPi中服務模式以及Sj中原子服務按照優(yōu)化目標排序

6 while success=0 and i

7 根據(jù)貪心準則選擇服務模式進行替換

8 調(diào)用服務流程算子buildingProcess獲得服務方案x*

9 i←i+1

10 if x*滿足約束

11 success←1

12 end else continue

13 end

14 返回x*

15 end

算法5人工蜂群算法(BP-ABC)。

輸入:用戶意圖樹iTree，需求模式集RP，服務模式集SP和原子服務集S，關聯(lián)矩陣A，用戶需求情境ctk;

輸出:最優(yōu)服務方案x*。

1 begin

2 x*←?;j←0;初始化循環(huán)次數(shù)MCN;偵察蜂參數(shù)limit;食物源個數(shù)SN；跟隨蜂個數(shù)d

3 調(diào)用需求匹配算子reqMatch，利用RP覆蓋iTree，獲得需求匹配結果：需求模式集RP′，未能匹配的意圖集R′(見3.1節(jié))。

4 從A中根據(jù)ck找到子矩陣Ak并根據(jù)RP′各rpi找到對應的服務模式集SPi，在S中找到R′中意圖rj與服務功能對應的服務集Sj。

5 根據(jù)SPi與Sj隨機生成SN個服務方案xi

6 foreach j

7 foreach xido

8 隨機選擇xi中1維用其他服務模式替換。

11 counti←0

12 end else counti←counti+1

13 隨機選擇d個服務方案，使用NSGA Ⅱ多目標優(yōu)化法優(yōu)化

14 foreach xido

15 if counti>limit do

16 隨機生成服務方案xi

17 end else continue

18 end

19 記錄當前最優(yōu)的服務方案x*;j←j+1

20 end

21 返回x*

22 end

3.3 生成服務流程

本節(jié)介紹將選擇后的服務模式和原子服務構造成一個流程的方法。在服務方案歷史執(zhí)行流程中對每個服務模式和服務加上時間戳，用來記錄服務與服務模式間的執(zhí)行順序。順序執(zhí)行的服務/服務模式，時間戳依次加1，并行執(zhí)行的，時間戳相同。

若將P中的服務模式和服務表示為圖中的點，大于1的值表示為圖中的邊，可以將P表示成一張有向圖。因為P中服務模式間的偏序關系可能存在環(huán)，所以使用貪心算法去掉環(huán)，使用的貪心策略為：去掉Σpij最大的spi的入邊。去環(huán)后的P即為一個合理的服務流程。服務流程構建算子constructingProcess如算法6所示。

算法6服務流程構建算子constructingProcess。

輸入:服務模式集SP，服務集S，順序比矩陣P;

輸出:服務流程s*。

1 begin

2 t←0;SP′←SP+S;ti←0為各服務模式/服務的時間戳

3 while SP′≠? do

4 foreach spi∈SP′ and spj∈SP′ do

5 si←0

6 if pij<1 do

7 si←si+1

8 end

9 end

10 將si最小的spi放入集合SP″中，s←minsi

11 if s=0 do

12 foreach spi∈SP″ do

13 ti←t

14 SP′←SP′SP″

15 end else

16 foreach spi∈SP″ and spj∈SP′ do

17 spm←Σpij最大的服務模式

18 if pmj<1 do

19 pmj←1; pjm←1

20 end

21 SP′←SP′{spm}

22 end

23 t←t+1

24 end

25 返回依據(jù)時間戳升序原則生成的服務流程s*

26 end

4 實驗與分析

本章將對所設計的基于雙邊模式的3個服務方案構建算法進行實驗分析，并與對應不采用模式的傳統(tǒng)算法進行比較。此外，對所提雙邊模式關聯(lián)矩陣的更新策略進行實驗，分析其有效性。

4.1 實驗環(huán)境

本文選擇公開服務數(shù)據(jù)集CrossWOZ[32]作為實驗數(shù)據(jù)集，CrossWOZ是一個大規(guī)模的中文跨領域數(shù)據(jù)集。它包含5個領域的6 012個需求對話及相關服務資源，服務資源包括：酒店、餐廳、景點、地鐵和出租車5大類。下面是數(shù)據(jù)集提供的一條需求對話示例。

CrossWOZ

usr:你好，可以幫我推薦一個評分是4.5分以上的景點嗎？

Hello, could you recommend an attraction with a rating of 4.5 or higher?

sys:天安門城樓，簋街小吃和北京歡樂谷都是很不錯的地方呢。

Tiananmen, Gui Street, andBeiJjing Happy Velleyare very nice places.

usr:我喜歡北京歡樂谷,你知道這個景點周邊的酒店都是什么嗎?

I likeBeijing Happy Valley. What hotels are around this attrraction?

sys:那可多了，有A酒店，B酒店，C酒店。

There are many, such as hotel A, hotel B, and hotel C.

usr:太好了，我正打算在景點附近找個酒店住宿呢，知道哪家評分是4分以上，提供叫醒服務的不？

Great! I am planning to find a hotel to stay near the attraction. Which one has a rating of 4 or higher and offers wake-up call service？

針對本文所提方法的特點，對數(shù)據(jù)作以下處理，以形成服務、服務模式、需求、需求模式和雙邊模式關聯(lián)矩陣等實驗數(shù)據(jù)：

(1)將數(shù)據(jù)集中的對話轉(zhuǎn)化為意圖樹作為需求數(shù)據(jù)，共6 012棵意圖樹；數(shù)據(jù)集中服務資源作為可用服務，為增加可用服務規(guī)模，以驗證算法的求解效率，增加華為應用商店中評分較高的地圖與天氣預報服務，共2 569個服務。

(2)隨機選取1 000棵意圖樹作為訓練集，挖掘得到需求模式集；從訓練集中生成對應服務方案集，從中挖掘得到服務模式集。

(3)對所選的1 000棵意圖樹形成的訓練集進行需求模式與需求的匹配，根據(jù)匹配結果中包含的需求模式在服務方案中對應的服務模式，構造雙邊模式關聯(lián)矩陣。

4.2 基于雙邊模式的服務方案構建算法的實驗與分析

對BP-PA、BP-AA、BP-ABC三個本文所提出的基于雙邊模式的服務方案構造算法，以及S-PA、S-AA、S-ABC三個對應的不使用雙邊模式的算法進行對比。將CrossWOZ數(shù)據(jù)集中除1 000條訓練集之外的其余5 012條數(shù)據(jù)作為驗證集，從可用服務數(shù)量、需求復雜度(所含意圖的數(shù)量)、雙邊模式關聯(lián)矩陣在匹配中可用程度(通過需求模式對需求的覆蓋程度來度量)3方面輸入數(shù)據(jù)的變化進行實驗分析，用算法執(zhí)行時間和解質(zhì)量兩個指標進行對比。其中解質(zhì)量指標采用當前對比算法所得解同最優(yōu)解的比值(解質(zhì)量比)度量，如式(12)所示：

(12)

為公平對比，進行解質(zhì)量比對比時，BP-PA和S-PA算法所生成服務方案的解質(zhì)量比是在執(zhí)行時間8 s下獲得；BP-ABC和S-ABC算法所生成服務方案的解質(zhì)量比是在執(zhí)行時間0.5 s下獲得；BP-AA和S-AA算法的解質(zhì)量比的獲得沒有時間限制。

進行執(zhí)行時間對比時，BP-PA和S-PA算法的執(zhí)行時間是在所生成服務方案的解質(zhì)量比為0.95的前提下獲得；BP-ABC和S-ABC算法的執(zhí)行時間是在所生成服務方案的解質(zhì)量比為0.98的前提下獲得；BP-AA和S-AA算法的執(zhí)行時間沒有解質(zhì)量比限制。

針對S-ABC和BP-ABC算法，運行10次，取平均值。

(1)不同可用服務數(shù)量下實驗結果

本節(jié)在可用服務數(shù)量為100～2 500時對6個算法進行對比，以驗證各算法在不同可用服務數(shù)據(jù)規(guī)模下的求解速度和求解質(zhì)量，結果如圖7與圖8所示。由于執(zhí)行時間數(shù)據(jù)差異較大，為了能夠清晰地加以區(qū)分，將2個精確算法的執(zhí)行時間單獨列出。

由圖7與圖8可見，無論是解質(zhì)量還是算法效率，使用雙邊模式下均優(yōu)于不使用雙邊模式，且服務數(shù)量越多，數(shù)據(jù)規(guī)模越大，使用雙邊模式的表現(xiàn)越好。由于數(shù)據(jù)的關系，在服務數(shù)量為1 800時，不使用雙邊模式的精確算法的解質(zhì)量比發(fā)生突變，這是因為在該范圍內(nèi)出現(xiàn)了一個質(zhì)量較好的服務，但是由于執(zhí)行時間被限制在8 s，導致精確算法并沒有搜索到該服務就已經(jīng)停止。由于其他算法能搜索到該服務，故此點為異常點。

(2)不同意圖樹節(jié)點數(shù)量下實驗結果

本節(jié)在意圖樹節(jié)點數(shù)量為2～7時對6種算法進行實驗，以驗證各算法在不同需求復雜程度下的求解速度和求解質(zhì)量，結果如圖9與圖10所示。

從圖9和圖10可見，無論是解質(zhì)量還是算法效率，使用雙邊模式的算法均優(yōu)于不使用雙邊模式，且意圖樹節(jié)點數(shù)量越多，需求越復雜，使用雙邊模式的表現(xiàn)越好。觀察不使用雙邊模式的人工蜂群算法在解質(zhì)量比的表現(xiàn)，可以發(fā)現(xiàn)在意圖樹節(jié)點數(shù)量在7時發(fā)生突變，原因是運行時間0.5 s不足以讓算法收斂，得到滿意的解。

(3)不同需求模式覆蓋比例下實驗結果

本節(jié)在需求模式覆蓋比例不同時對6種算法進行實驗，以驗證各算法在關聯(lián)矩陣的可用程度不同時的求解速度和求解質(zhì)量。如實驗(2)所示，由于意圖樹規(guī)模對實驗結果有較大影響，選擇使用節(jié)點數(shù)量為5的意圖樹作為實驗集，結果如圖11與圖12所示。

如圖11與圖12所示，在解質(zhì)量方面，使用雙邊模式的算法要優(yōu)于不使用雙邊模式的算法，且需求模式覆蓋比例越高，使用雙邊模式的算法解質(zhì)量比越好。在算法效率方面，當需求模式覆蓋比例為0(關聯(lián)矩陣不發(fā)揮作用)時，使用雙邊模式的算法退化為不使用雙邊模式的算法，由于使用雙邊模式的算法需要進行需求匹配，算法執(zhí)行時間要多于不使用雙邊模式的算法，隨著需求模式覆蓋比例的增加，使用雙邊模式的算法在匹配效率方面逐漸優(yōu)于不使用雙邊模式的算法。

(4)3種求解策略對比

本實驗中BP-PA和BP-ABC算法的執(zhí)行時間是在所生成服務方案的解質(zhì)量比為0.97的前提下獲得的，實驗結果如圖13所示。當服務規(guī)模較小(100～200)，在獲得近似解質(zhì)量比的情況下，3個算法的時間差距不大(0.1～0.25 s)，因此選擇BP-PA算法以得到最優(yōu)的解質(zhì)量比；在服務規(guī)模中等(300～1 500)時，BP-PA算法執(zhí)行時間較長(0.5～1.25 s)，而BP-ABC算法求解時間較BP-AA算法長，因此選擇BP-AA算法平衡算法速度與解質(zhì)量；在服務規(guī)模較大(1 600～2 500)時，BP-ABC和BP-AA的求解速度相互起伏，無法通過平均時間判定算法優(yōu)劣，因此本文對服務數(shù)量在1 600～2 500，BP-ABC和BP-AA兩個算法的箱形圖(如圖14)進行分析。

對兩組數(shù)據(jù)進行t檢驗，結果如表1所示。

表1 服務數(shù)量在1 600～2 500時BP-ABC和BP-AA算法的執(zhí)行時間t檢驗

由于樣本數(shù)量大，本文選擇顯著度水平α=0.025，當p<α時，拒絕零假設，即有顯著差異。當服務數(shù)量為2 300時，兩組數(shù)據(jù)均值有顯著差異，這時BP-ABC的均值為0.245，BP-AA的均值為0.303，前者的平均執(zhí)行時間要少于后者。對于其他服務數(shù)量，均值無顯著差異，而BP-ABC的矩形箱明顯偏下，大部分需求的執(zhí)行時間優(yōu)于BP-AA，因此優(yōu)先選擇BP-ABC提升求解速度。

4.3 關聯(lián)矩陣更新策略實驗與分析

首先對使用關聯(lián)矩陣更新策略的必要性進行驗證。實驗內(nèi)容為當總服務方案數(shù)量在0～200 000時更新關聯(lián)矩陣并記錄執(zhí)行時間，結果如圖15所示。

由實驗可知，更新時間與總方案數(shù)量基本呈線性關系，當日志中的方案數(shù)量為25 000時，更新時間為125 s，但當方案數(shù)量很大時(超過175 000)，日志中方案不斷累積，更新時間會達到1 000 s甚至更多，關聯(lián)矩陣更新代價巨大。由此可見，有必要對關聯(lián)矩陣采用動態(tài)更新頻率和策略。

下面對關聯(lián)矩陣更新策略的有效性進行驗證。由于數(shù)據(jù)集中沒有時間信息，本文通過百度指數(shù)網(wǎng)站收集2019年各景區(qū)逐日網(wǎng)絡關注度數(shù)據(jù)來模擬一年中各景區(qū)每日的訪問量，模擬每日各需求出現(xiàn)的數(shù)量。首先使用精確算法生成最優(yōu)解并挖掘服務模式，再根據(jù)精確解中的每個景區(qū)，得到對應需求每日被提出的次數(shù)。因為數(shù)據(jù)中沒有服務QoS變化的信息，所以本文不對策略3進行實驗驗證。本文假設每次更新的總方案數(shù)量相同。如2.4.2節(jié)所述，當某需求模式，服務模式對在某情境下的匹配度降低到一定程度時，在匹配中不予考慮，且4.2節(jié)已經(jīng)通過實驗證明使用雙邊模式生成服務方案在效率和匹配質(zhì)量上要優(yōu)于不使用雙邊模式，所以本節(jié)以匹配成功率和更新的次數(shù)來度量更新策略的效果，匹配成功率越高，更新次數(shù)越少，策略越優(yōu)。

(1)策略1：新增策略

本節(jié)對策略1的參數(shù)a進行分析，結果如表2所示?？梢园l(fā)現(xiàn)，隨著參數(shù)a的降低，匹配成功率增大，更新次數(shù)增多，但是當a過小時，更新次數(shù)迅速增加但匹配成功率變化不大，策略效果達到瓶頸。綜合考慮，本文選擇a=0.1作為策略1的參數(shù)。

表2 策略1參數(shù)設置

(2)策略2：突變策略

對策略2的參數(shù)b進行分析，結果如表3所示?？梢园l(fā)現(xiàn)，隨著b的增大，匹配成功率增大，更新次數(shù)增多。與參數(shù)a相似，當b過大時，更新次數(shù)迅速增加但是匹配成功率變化不大。綜合考慮，本文選擇b=0.8作為策略2的參數(shù)。

表3 策略2參數(shù)設置

(3)同時考慮兩種更新策略

如表4的4～6行所示，同時使用兩種策略比僅使用一種策略的匹配成功率高，且更新次數(shù)相近，說明同時使用兩種策略要優(yōu)于單獨使用一種策略。觀察表的前3行與后3行，可以發(fā)現(xiàn)定期更新策略要劣于使用本文提出的關聯(lián)矩陣更新策略。因此，本文提出的關聯(lián)矩陣更新策略在匹配成功率與更新次數(shù)上表現(xiàn)較優(yōu)，在關聯(lián)矩陣使用過程中有較好的效果。

表4 關聯(lián)矩陣更新策略實驗驗證

5 結束語

針對服務互聯(lián)網(wǎng)中的服務供需匹配這類復雜優(yōu)化問題，本文基于模塊化的思想提出了基于供需雙邊模式的服務匹配問題模型。當服務日志中已經(jīng)存在了一定的歷史服務方案，利用領域先驗知識挖掘需求模式與服務模式，增加匹配粒度，提高重用效率。設計多維關聯(lián)矩陣建立需求模式和服務模式的關系，提出自適應關聯(lián)矩陣更新策略動態(tài)調(diào)整更新頻率，進一步提高匹配效率。針對3種不同場景設計3種算法構建服務方案，通過對各算法的求解質(zhì)量與執(zhí)行時間的對比，證明所提的使用雙邊模式的算法(以S-ABC算法與BP-ABC為例)在時間上提高了41.2%，在質(zhì)量上提高了1.12%。通過對關聯(lián)矩陣更新策略的匹配成功率與更新次數(shù)的對比，證明本文提出的關聯(lián)矩陣自適應更新策略(與每14天更新作比較)在匹配成功率上提高了7.9%。

在未來工作中，將進一步研究關聯(lián)矩陣的多維數(shù)學模型建模，優(yōu)化存儲和查詢的數(shù)據(jù)結構，索引技術等內(nèi)容，提升檢索效率，降低存儲空間，解決矩陣稀疏性等問題。同時，考慮將方法擴展至分布式環(huán)境中，需求與需求模式、服務與服務模式以及關聯(lián)矩陣將如何存儲，節(jié)點間應以何種策略協(xié)作以完成全局目標構建優(yōu)化的服務解決方案將是今后的研究重點。