基于用戶(hù)多興趣的服務(wù)流程推薦方法

陳 明，高鐵梁，張志鋒，季肖輝，唐啟光

(1.鄭州輕工業(yè)大學(xué) 軟件學(xué)院，河南 鄭州 450001；2.新鄉(xiāng)學(xué)院 商學(xué)院，河南 新鄉(xiāng) 453000；3.中原油田 采油氣工程服務(wù)中心，河南 濮陽(yáng) 457001)

0 引言

隨著服務(wù)計(jì)算和移動(dòng)互聯(lián)網(wǎng)的發(fā)展，越來(lái)越多的服務(wù)逐漸開(kāi)放自己的接口，使得用戶(hù)創(chuàng)建對(duì)象也延伸到了服務(wù)領(lǐng)域，開(kāi)啟了一個(gè)新的用戶(hù)創(chuàng)建服務(wù)(User Generated Service，UGS)[1]趨勢(shì)。

在輕量級(jí)服務(wù)組合平臺(tái)上[2]，普通用戶(hù)可以通過(guò)組合單一的簡(jiǎn)單服務(wù)，創(chuàng)建出滿(mǎn)足個(gè)人需求的服務(wù)流程。例如用戶(hù)可以在Zapier平臺(tái)上組合Evernote、Todoist和Twitter去創(chuàng)建一個(gè)自動(dòng)化影評(píng)的服務(wù)流程，當(dāng)用戶(hù)在Evernote中寫(xiě)完影評(píng)，并在Todoist中標(biāo)記為完成后，Twitter就會(huì)創(chuàng)建消息發(fā)布這篇影評(píng)。然而，由于服務(wù)組合的復(fù)雜性和用戶(hù)的編程思維缺失，使得普通用戶(hù)在選擇服務(wù)時(shí)依然需要決策輔助。這些決策主要體現(xiàn)在兩個(gè)方面：

(1)在用戶(hù)組建服務(wù)流程時(shí)，因?yàn)橛脩?hù)領(lǐng)域知識(shí)和接口知識(shí)匱乏，加上用戶(hù)興趣的不確定性，使得用戶(hù)在組建業(yè)務(wù)流程時(shí)出現(xiàn)組件選擇困難的問(wèn)題。傳統(tǒng)鏈接算法在給用戶(hù)推薦服務(wù)鏈接時(shí)，往往只關(guān)注當(dāng)下用戶(hù)的選擇，忽視了用戶(hù)之前的服務(wù)選擇和當(dāng)下服務(wù)的鏈接性(即忽視了用戶(hù)的上下文調(diào)用順序和服務(wù)流程的多類(lèi)屬性)，從而在用戶(hù)連續(xù)調(diào)用服務(wù)時(shí)不能準(zhǔn)確推薦出用戶(hù)所需服務(wù)組件。例如當(dāng)用戶(hù)點(diǎn)擊服務(wù)Flickr的時(shí)候，系統(tǒng)若能考慮之前用戶(hù)點(diǎn)擊的Facebook服務(wù)，則可以推薦出能和Facebook—>Flickr服務(wù)序列相鏈接的其他服務(wù)(如Google Maps)，而不是單純只能推薦Flickr的鏈接服務(wù)。

(2)在用戶(hù)創(chuàng)建服務(wù)流程結(jié)束后，因?yàn)橛脩?hù)興趣的多樣性，單一的服務(wù)流程往往無(wú)法滿(mǎn)足用戶(hù)需求，需要推薦用戶(hù)有潛在興趣的其他業(yè)務(wù)流程。例如當(dāng)用戶(hù)調(diào)用服務(wù)流程結(jié)束后，可以通過(guò)用戶(hù)當(dāng)下行為，利用模型挖掘該服務(wù)流程所屬興趣，當(dāng)系統(tǒng)得到該服務(wù)流程的興趣后，就可以將其他滿(mǎn)足用戶(hù)興趣的相似服務(wù)流程推薦給用戶(hù)，最后由用戶(hù)根據(jù)自己的需要?jiǎng)?chuàng)建下一業(yè)務(wù)流程。

綜上所述，為了更好地輔助用戶(hù)決策，本文提出一種基于用戶(hù)多興趣的服務(wù)流程推薦方法，該方法通過(guò)對(duì)上下文順序的感知和語(yǔ)義分析可以緩解服務(wù)組合中遇到的用戶(hù)興趣問(wèn)題，不僅可以幫助用戶(hù)在組建服務(wù)時(shí)避免出現(xiàn)服務(wù)不匹配的問(wèn)題，還可以根據(jù)潛在興趣為用戶(hù)推薦更多相關(guān)的服務(wù)流程，以滿(mǎn)足用戶(hù)的個(gè)性化需求。通過(guò)仿真實(shí)驗(yàn)表明，所提方法能夠快速、準(zhǔn)確地為用戶(hù)推薦相關(guān)服務(wù)組件和業(yè)務(wù)流程鏈。

1 相關(guān)研究

目前，學(xué)術(shù)界針對(duì)輕量級(jí)服務(wù)組合的研究主要集中在如何給用戶(hù)推薦服務(wù)組件和流程上。GREENSHPAN等[3]在IBM Mashup Center的基礎(chǔ)上提出了autocompletion機(jī)制，通過(guò)定義組合模型來(lái)評(píng)估用戶(hù)當(dāng)前的組合狀態(tài)，從而在IBM Mashup Center的數(shù)據(jù)庫(kù)中找到與當(dāng)前狀態(tài)最匹配的設(shè)計(jì)方案。文獻(xiàn)[4]通過(guò)分析Mashup、應(yīng)用程序接口(Application Programming Interface,API)和Tag之間的關(guān)系，設(shè)計(jì)了一個(gè)Mashup-API-Tag網(wǎng)絡(luò)模型，在模型中以杰卡德系數(shù)為基礎(chǔ),分別從API和Tag的角度去計(jì)算業(yè)務(wù)流程的相似度從而進(jìn)行推薦。文獻(xiàn)[5]從語(yǔ)義網(wǎng)的角度考慮輕量級(jí)服務(wù)組合中的推薦問(wèn)題，通過(guò)用戶(hù)歷史訪(fǎng)問(wèn)記錄建立語(yǔ)義樹(shù)，并計(jì)算樹(shù)節(jié)點(diǎn)的距離，基于節(jié)點(diǎn)的距離近似度進(jìn)行服務(wù)推薦。文獻(xiàn)[6]使用復(fù)雜網(wǎng)絡(luò)的觀(guān)點(diǎn)分析了輕量級(jí)服務(wù)組合，通過(guò)分析API和服務(wù)組合的調(diào)用關(guān)系組建了Mashup-API網(wǎng)絡(luò)。文獻(xiàn)[7]提出了voronoi Navigation的推薦機(jī)制，該機(jī)制通過(guò)分析用戶(hù)的蹤跡來(lái)理解用戶(hù)的意圖，利用voronoi圖以及非對(duì)稱(chēng)度量空間的相關(guān)技術(shù)快速地找到最接近用戶(hù)意圖的k個(gè)數(shù)據(jù)源，然后通過(guò)層次分析對(duì)這k個(gè)數(shù)據(jù)源進(jìn)行評(píng)估和排序，最終將最準(zhǔn)確的k個(gè)數(shù)據(jù)源有序的推薦給用戶(hù)。文獻(xiàn)[8]提出一種新的基于迭代式自主構(gòu)造的Mashup服務(wù)組合的運(yùn)行模式，主要思想是對(duì)大量離散、孤立的歷史執(zhí)行軌跡進(jìn)行挖掘處理，建立上下文相關(guān)和偏好相關(guān)的用戶(hù)行為選擇概率模型，為構(gòu)造優(yōu)化的個(gè)性化Mashup組合方案提供支持。文獻(xiàn)[9]提出一種融合自組織映射(Self Organization Map，SOM)功能聚類(lèi)與深度因子分解機(jī)(Deep Factorization Machine，DeepFM)質(zhì)量預(yù)測(cè)的API服務(wù)推薦方法，用于創(chuàng)建高質(zhì)量的Mashup應(yīng)用。文獻(xiàn)[10]提出一種基于文本擴(kuò)展和深度模型的服務(wù)推薦方法，該方法首先提出用新的概率主題模型去擴(kuò)展句子級(jí)的服務(wù)描述，然后提出一個(gè)長(zhǎng)短期內(nèi)存模型并結(jié)合兩種注意機(jī)制(功能注意機(jī)制和上下文注意機(jī)制)推薦服務(wù)。文獻(xiàn)[11]針對(duì)移動(dòng)邊緣計(jì)算，提出一種延遲感知的微服務(wù)Mashup方法。文獻(xiàn)[12]提出一種可用于Mashup開(kāi)發(fā)的Web API推薦方法。該方法首先通過(guò)使用Mashup服務(wù)之間的關(guān)系來(lái)確定兩級(jí)主題模型，以挖掘潛在的有用新穎主題，提高服務(wù)聚類(lèi)的準(zhǔn)確性，接著基于Mashup的聚類(lèi)結(jié)果，采用協(xié)同過(guò)濾算法來(lái)推薦Web API(該算法利用從Mashups集群與相應(yīng)Web API之間的歷史調(diào)用推斷出Web API之間的隱式協(xié)同調(diào)用關(guān)系，從而為每個(gè)Mashups集群推薦不同的Web API)。

上述研究主要集中在用戶(hù)-服務(wù)流程的二元關(guān)系中進(jìn)行相似度計(jì)算，沒(méi)有上升到語(yǔ)義層面，因此本文考慮采用概率潛在語(yǔ)義分析(Probabilistic Latent Semantic Analysis，PLSA)算法，將其上升為用戶(hù)-興趣-服務(wù)流程三層模型，將興趣相似的服務(wù)流程聚類(lèi)在一起，從而更好地推薦服務(wù)流程。

2 算法描述

基于用戶(hù)多興趣的服務(wù)流程推薦可以分為3個(gè)階段：①數(shù)據(jù)處理，將抓取的服務(wù)訪(fǎng)問(wèn)信息轉(zhuǎn)換為用戶(hù)-服務(wù)矩陣以供后續(xù)處理；②初始興趣引導(dǎo)，已知前面i-1個(gè)已選擇的服務(wù)組件，根據(jù)N元模型(N-gram)計(jì)算第i個(gè)不同服務(wù)組件出現(xiàn)的概率，根據(jù)概率選取推薦服務(wù)，根據(jù)推薦服務(wù)創(chuàng)建業(yè)務(wù)流程；③用戶(hù)興趣抽取，在用戶(hù)完成服務(wù)流程創(chuàng)建后，通過(guò)概率潛在語(yǔ)義分析訓(xùn)練出用戶(hù)的興趣-服務(wù)流程分布，為用戶(hù)推薦出符合當(dāng)下興趣的其他服務(wù)流程。

2.1 數(shù)據(jù)處理

將抓取的服務(wù)訪(fǎng)問(wèn)信息根據(jù)訪(fǎng)問(wèn)時(shí)間的先后順序轉(zhuǎn)換為用戶(hù)-服務(wù)矩陣，即user1:(sc1,sc2,…,scn)形式，其中(sc1,sc2,…,scn)是用戶(hù)user1選擇的服務(wù)流程，服務(wù)組件sc1,sc2,…，scn按用戶(hù)user1訪(fǎng)問(wèn)時(shí)間的先后順序排序，前后服務(wù)之間具有直接鏈接關(guān)系，服務(wù)組件之間的鏈接關(guān)系可以用來(lái)訓(xùn)練N-gram模型，不同的服務(wù)流程可以用來(lái)聚類(lèi)用戶(hù)興趣。然后將用戶(hù)-服務(wù)矩陣中那些不活躍用戶(hù)的數(shù)據(jù)清洗掉，將活躍用戶(hù)數(shù)據(jù)放入文本中作為實(shí)驗(yàn)數(shù)據(jù)集。

2.2 初始興趣引導(dǎo)

N元模型(N-gram)[13]是基于概率的判別模型，該模型認(rèn)為第i個(gè)詞的出現(xiàn)只與前面i-1個(gè)詞相關(guān)，而與其他任何詞都不相關(guān)?；谠摷僭O(shè)，可以認(rèn)為在服務(wù)流程中，第i個(gè)服務(wù)出現(xiàn)的概率僅與前面i-1個(gè)已選擇的服務(wù)有關(guān)，而與其他任何服務(wù)無(wú)關(guān)，因此當(dāng)用戶(hù)點(diǎn)擊服務(wù)組件后，通過(guò)N元模型計(jì)算其后的預(yù)測(cè)服務(wù)，并將預(yù)測(cè)服務(wù)推薦給用戶(hù)，即將不同的候選服務(wù)帶入概率公式p(sci|sc1…sci-1)，將大于閾值T的服務(wù)作為候選推薦給用戶(hù)。這里sci表示第i個(gè)服務(wù)組件，sc1…sci-1表示sc1到sci-1的服務(wù)組件序列，p(sci|sc1…sci-1)表示當(dāng)服務(wù)序列sc1…sci-1出現(xiàn)后，該序列能和sci鏈接的概率。

在實(shí)際求解時(shí)，p(sci|sc1…sci-1)的參數(shù)空間過(guò)大，計(jì)算非常耗時(shí)，為解決該問(wèn)題，引入Markov假設(shè)：一個(gè)服務(wù)的出現(xiàn)僅與它之前的若干個(gè)服務(wù)有關(guān)。因此可由p(sci|sc1…sci-1)推出式(1)成立：

p(sci|sc1…sci-1)≈p(sci|sci-N+1…sci-1)。

(1)

然后利用極大似然估計(jì)求解p(sci|sci-N+1…sci-1)，有式(2)成立：

(2)

式中：C(sci-N+1…sci-1sci)代表服務(wù)序列sci-N+1…sci-1sci在已知數(shù)據(jù)集中出現(xiàn)的次數(shù)。

2.3 用戶(hù)興趣抽取

PLSA是一種柔性聚類(lèi)的生成模型方法[14]。在本文中，PLSA的最大目的是計(jì)算出興趣-服務(wù)流程的概率分布來(lái)實(shí)現(xiàn)聚類(lèi)，這樣當(dāng)用戶(hù)根據(jù)推薦的服務(wù)創(chuàng)建業(yè)務(wù)流程后或直接調(diào)用服務(wù)流程時(shí)，根據(jù)其所屬不同興趣的概率來(lái)挑選與其相似的服務(wù)流程推薦給用戶(hù)。PLSA的概率圖模型如圖1所示。

圖中U表示用戶(hù)，Z表示興趣類(lèi)別，SP表示觀(guān)察到的服務(wù)流程，p(ui)表示用戶(hù)ui在數(shù)據(jù)集中出現(xiàn)的概率，p(zk|ui)表示用戶(hù)ui屬于興趣類(lèi)別zk的概率，用戶(hù)興趣不唯一，p(spj|zk)表示當(dāng)興趣zk確定時(shí)，服務(wù)流程spj屬于此興趣類(lèi)別zk的概率。作為生成模型，要計(jì)算p(spj|zk)，需要得到p(spj|zk)的聯(lián)合分布，由于zk是隱變量，該聯(lián)合分布無(wú)法直接求得。故可根據(jù)觀(guān)測(cè)到的數(shù)據(jù)對(duì)(ui,spj)，先計(jì)算(ui,spj)的聯(lián)合分布，如式(3)所示：

(3)

根據(jù)最大似然估計(jì)求PLSA模型的參數(shù)p(spj|zk)，其似然函數(shù)L如式(4)所示：

(4)

其中n(ui,spj)表示用戶(hù)ui選取服務(wù)組合spj的次數(shù)。為防止連乘造成數(shù)據(jù)溢出，對(duì)似然函數(shù)進(jìn)行對(duì)數(shù)處理，得到式(5)：

(6)

根據(jù)式(6)，此時(shí)可以不用計(jì)算極大似然函數(shù)本身的值，而是使用期望最大化(Expectation-Maximum，EM)算法極大化該函數(shù)的下界。EM算法分為E和M兩個(gè)步驟，通過(guò)不斷循環(huán)E和M兩個(gè)步驟去逼近似然函數(shù)下界的最大值，當(dāng)EM算法收斂后，此時(shí)的參數(shù)值接近真實(shí)數(shù)據(jù)集的參數(shù)值。EM算法如下：

(1)E步驟主要計(jì)算Q(zk)，即隱變量的后驗(yàn)概率p(zk|ui,spj)，可以先隨機(jī)初始化參數(shù)p(zk|ui)和p(spj|zk)的值，然后根據(jù)初始化的結(jié)果求解隱變量在當(dāng)前參數(shù)條件下的后驗(yàn)概率。有式(7)成立：

(7)

(2)M步驟的任務(wù)是期望最大化，主要是根據(jù)E步得到的隱變量的后驗(yàn)概率對(duì)含有參數(shù)的對(duì)數(shù)似然函數(shù)進(jìn)行極值求解，得到p(zk|ui)和p(spj|zk)的新參數(shù)值，然后帶入E步進(jìn)行循環(huán)。為了簡(jiǎn)化式子，將p(zk|ui)和p(spj|zk)簡(jiǎn)寫(xiě)為Z。M步驟如式(3)～式(8)所示：

(8)

式(8)是一個(gè)帶約束條件的多元函數(shù)求極值問(wèn)題，利用拉格朗日乘子法可以將一個(gè)約束求極值問(wèn)題轉(zhuǎn)化為一個(gè)對(duì)偶的無(wú)約束極值求解問(wèn)題，創(chuàng)建拉格朗日函數(shù)Lg如式(9)所示：

(9)

這是一個(gè)關(guān)于p(zk|ui)和p(spj|zk)的函數(shù)。對(duì)參數(shù)p(zk|ui)求偏導(dǎo)并令偏導(dǎo)數(shù)為0，可以得到式(10)：

(10)

(11)

同理，Lg對(duì)p(spj|zk)求偏導(dǎo)并令偏導(dǎo)數(shù)為0，可得到式(12)：

(12)

得到新的p(spj|zk)和p(zk|ui)值后，再將參數(shù)帶入到E步驟，進(jìn)一步得出新的p(zk|ui,spj)，接著再進(jìn)入M步驟，再次得到更新后的p(spj|zk)和p(zk|ui)值，直到最大似然值的變化達(dá)到閾值，這表示最后得到的參數(shù)值可以描述數(shù)據(jù)集。然后根據(jù)p(spj|zk)可以判斷出戶(hù)調(diào)用的服務(wù)流程spj屬于各個(gè)興趣的概率，從而給用戶(hù)推薦出符合用戶(hù)興趣的服務(wù)流程。

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

3.1 數(shù)據(jù)集

本文采用ProgrammableWeb網(wǎng)站的用戶(hù)服務(wù)調(diào)用記錄、服務(wù)組合數(shù)據(jù)集和服務(wù)組件數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其中服務(wù)組合數(shù)據(jù)集包括13 082個(gè)服務(wù)流程，服務(wù)組件數(shù)據(jù)集包括10 648個(gè)服務(wù)，用戶(hù)服務(wù)調(diào)用記錄包括20 035個(gè)用戶(hù)的調(diào)用記錄。

3.2 基于N-gram模型的服務(wù)鏈接推薦算法評(píng)估

3.2.1N-gram模型中N值估計(jì)

N-gram模型認(rèn)為一個(gè)服務(wù)的出現(xiàn)依賴(lài)于其前面N個(gè)其他服務(wù)。為選取合適的N值，本文對(duì)不同N值下服務(wù)推薦的精確性進(jìn)行對(duì)比，這里只考慮N=2和N=3的情況，因?yàn)殡S著N的增大，依賴(lài)的服務(wù)也就越多，雖然推薦的精確性增高，但是需要計(jì)算的參數(shù)卻呈指數(shù)級(jí)增長(zhǎng)，現(xiàn)實(shí)中一般只考慮N=2和N=3兩種情況。

可以看出，隨著Top-P的增大，precision(sc)中分子為1的概率逐漸增大，因此2-gram和3-gram的服務(wù)推薦精確性也在逐漸提高，但是這種提高在到達(dá)某個(gè)點(diǎn)時(shí)將終止并進(jìn)入平滑期，如3-gram在Top-P=6時(shí)，因?yàn)殚撝档南拗?，?shí)際推薦的服務(wù)組件將不再隨著Top-P的增大而改變，其推薦精度將逐漸穩(wěn)定。

3.2.2 算法對(duì)比

3-gram和超鏈接引導(dǎo)主題搜索 (Hyperlink-Induced Topic Search, HITS) 算法的對(duì)比如圖3所示，HITS算法將服務(wù)節(jié)點(diǎn)的調(diào)入和調(diào)出分別定義為權(quán)威值和樞紐值，然后通過(guò)不停鏈接迭代尋找高質(zhì)量的節(jié)點(diǎn)，可以用來(lái)發(fā)現(xiàn)服務(wù)和服務(wù)之間的鏈接關(guān)系。從圖中可以看出3-gram算法的服務(wù)推薦精度高于HITS算法，特別是隨著Top-P的增大，3-gram的推薦精度逐漸穩(wěn)定，但是HITS算法經(jīng)過(guò)多次迭代會(huì)產(chǎn)生鏈接漂移的現(xiàn)象，其服務(wù)推薦精度反而降低。

3.3 基于PLSA模型的服務(wù)流程推薦算法評(píng)估

3.3.1 興趣個(gè)數(shù)估計(jì)

為實(shí)現(xiàn)方案的最優(yōu)性能，本文利用困惑度(perplexity)確定PLSA模型的興趣聚類(lèi)個(gè)數(shù)，困惑度可以看作是后驗(yàn)概率取-log值，其后驗(yàn)概率越大，perplexity越小，說(shuō)明這個(gè)參數(shù)越能代表這個(gè)數(shù)據(jù)的真實(shí)性：

(13)

如圖4所示，隨著聚類(lèi)個(gè)數(shù)變化，perplexity值也在不斷變化中，當(dāng)聚類(lèi)個(gè)數(shù)為160時(shí)，perplexity值最小，perplexity=198.6，代表160個(gè)流程聚類(lèi)最符合這個(gè)數(shù)據(jù)集。

3.3.2 算法對(duì)比

從圖5可以看出，隨著服務(wù)流程訓(xùn)練數(shù)據(jù)密度的增大，PLSA算法和LSA算法的推薦精度將隨之增大，同時(shí)PLSA算法的增大幅度高于LSA算法。如在訓(xùn)練數(shù)據(jù)密度30%時(shí)，PLSA算法的推薦精度為0.068，LSA算法的推薦精度為0.065。在訓(xùn)練數(shù)據(jù)密度為90%時(shí)，PLSA算法的推薦精度為0.172，LSA算法的推薦精度為0.120。增大幅度不同是因?yàn)長(zhǎng)SA是根據(jù)奇異值矩陣分解來(lái)進(jìn)行聚類(lèi)的，興趣因子中有負(fù)值，聚類(lèi)效果低于PLSA算法。

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

為了解決服務(wù)推薦過(guò)程中，用戶(hù)興趣的不確定性問(wèn)題和多樣性問(wèn)題，提出一種基于用戶(hù)多興趣的服務(wù)流程推薦方法。該方法采用N元模型算法為用戶(hù)推薦和調(diào)用相匹配的服務(wù)，緩解了用戶(hù)在組建服務(wù)時(shí)出現(xiàn)服務(wù)不匹配的問(wèn)題；采用概率潛在語(yǔ)義分析算法為用戶(hù)提供滿(mǎn)足用戶(hù)興趣的服務(wù)組合，不僅縮減了用戶(hù)創(chuàng)建服務(wù)所需開(kāi)銷(xiāo)，還能讓模板庫(kù)中的組合得到復(fù)用，對(duì)輕量級(jí)服務(wù)組合的發(fā)展具有重要推動(dòng)作用。

未來(lái)作者將進(jìn)一步從用戶(hù)行為模式、服務(wù)質(zhì)量、時(shí)延與成本、資源分配策略等角度出發(fā)，考慮構(gòu)建一種更高效的服務(wù)組合推薦算法，為Mashup設(shè)計(jì)與實(shí)現(xiàn)提供參考。