方晨，張恒巍，張銘，王晉東

?

基于信任擴(kuò)展和列表級(jí)排序?qū)W習(xí)的服務(wù)推薦方法

方晨1,2，張恒巍1,2，張銘1,2，王晉東1,2

（1. 信息工程大學(xué)三院，河南 鄭州 450001；2. 數(shù)字工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450001）

針對(duì)傳統(tǒng)基于信任網(wǎng)絡(luò)的服務(wù)推薦算法中信任關(guān)系稀疏以及通過QoS預(yù)測(cè)值排序得到的服務(wù)推薦列表不一定最符合用戶偏好等問題，提出基于信任擴(kuò)展和列表級(jí)排序?qū)W習(xí)的服務(wù)推薦方法（TELSR）。在分析服務(wù)排序位置信息的重要性后給出概率型用戶相似度計(jì)算方法，進(jìn)一步提高相似度計(jì)算的準(zhǔn)確性；利用信任擴(kuò)展模型解決用戶信任關(guān)系稀疏性問題，并結(jié)合用戶相似度給出可信鄰居集合構(gòu)建方法；基于可信鄰居集合，利用列表級(jí)排序?qū)W習(xí)方法訓(xùn)練出最優(yōu)排序模型。仿真實(shí)驗(yàn)表明，與已有算法相比，TELSR在具有較高推薦精度的同時(shí)，還可有效抵抗惡意用戶的攻擊。

服務(wù)推薦；排序?qū)W習(xí)；概率型用戶相似度；信任關(guān)系

1 引言

隨著互聯(lián)網(wǎng)的普及和云計(jì)算技術(shù)的迅猛發(fā)展，網(wǎng)絡(luò)上提供的Web服務(wù)呈指數(shù)級(jí)增長(zhǎng)。用戶迫切地需要一種有效的服務(wù)推薦方法來(lái)解決其面臨的選擇困境。因此，服務(wù)推薦技術(shù)在服務(wù)計(jì)算領(lǐng)域獲得了廣泛的關(guān)注。Web服務(wù)的服務(wù)質(zhì)量（QoS, quality of service）包括服務(wù)失效率、響應(yīng)時(shí)間、成本、吞吐量等[1]，是用戶進(jìn)行服務(wù)選取時(shí)需要考慮的重要屬性之一。而由于Web服務(wù)廣泛地分布在網(wǎng)絡(luò)中，一些QoS屬性如響應(yīng)時(shí)間、吞吐量等經(jīng)常受到網(wǎng)絡(luò)環(huán)境動(dòng)態(tài)變化的影響，具有很大的不確定性，這就造成了服務(wù)推薦可靠性差的問題。

為解決此問題，研究者們考慮將協(xié)同過濾算法應(yīng)用到服務(wù)推薦過程中，通過預(yù)測(cè)QoS值并以此對(duì)服務(wù)進(jìn)行排序來(lái)實(shí)現(xiàn)推薦[2]。為了提高QoS預(yù)測(cè)的準(zhǔn)確性，研究者們對(duì)傳統(tǒng)協(xié)同過濾算法做出了一系列改進(jìn)，包括引入用戶的信任網(wǎng)絡(luò)[3]、服務(wù)調(diào)用模式[4]、服務(wù)的上下文信息[5]等。主要存在的問題為1) 沒有有效利用服務(wù)的排序位置信息；2) 引入的信任網(wǎng)絡(luò)中用戶直接信任關(guān)系稀疏，難以提供足夠的輔助信息。

近幾年來(lái)，有研究者考慮將排序?qū)W習(xí)技術(shù)引入推薦算法中來(lái)，通過直接優(yōu)化最終的排序列表來(lái)提高推薦系統(tǒng)的準(zhǔn)確性[6]。作為一種強(qiáng)監(jiān)督性機(jī)器學(xué)習(xí)算法，排序?qū)W習(xí)能夠整合大量復(fù)雜特征并自動(dòng)學(xué)習(xí)最優(yōu)參數(shù)，降低了考慮單個(gè)因素進(jìn)行排序的風(fēng)險(xiǎn)，且能夠通過多種方法來(lái)規(guī)避過擬合問題，獲得了學(xué)術(shù)界越來(lái)越多的關(guān)注[7]。然而，目前很少有研究將傳統(tǒng)協(xié)同過濾算法與排序?qū)W習(xí)技術(shù)結(jié)合起來(lái)，并應(yīng)用到服務(wù)推薦領(lǐng)域。

針對(duì)上述問題，本文提出基于信任擴(kuò)展和列表級(jí)排序?qū)W習(xí)的服務(wù)推薦方法（TELSR, trust expansion and listwise learning-to-rank based service recommendation method）。該方法首先在分析服務(wù)排序位置信息重要性的基礎(chǔ)上，給出概率型用戶相似度計(jì)算方法（PUSC, probabilistic user similarity computation method），提高相似度計(jì)算準(zhǔn)確性；然后，提出信任擴(kuò)展模型充分挖掘用戶信任網(wǎng)絡(luò)信息，并結(jié)合用戶相似度構(gòu)建可信鄰居集合；最后，利用可信鄰居集合改進(jìn)列表級(jí)排序?qū)W習(xí)算法，通過訓(xùn)練得到最符合用戶偏好的服務(wù)推薦列表。本文的主要貢獻(xiàn)有以下3點(diǎn)。

1) 給出概率型用戶相似度計(jì)算方法，有效利用了服務(wù)的排序位置信息，提高了相似度計(jì)算準(zhǔn)確性。

2) 提出信任擴(kuò)展模型，充分挖掘了用戶信任關(guān)系，構(gòu)建出可信鄰居集合，能夠抵抗惡意用戶的攻擊。

3) 改進(jìn)列表級(jí)排序?qū)W習(xí)算法，可輸出最符合用戶興趣偏好的服務(wù)推薦列表。

2 相關(guān)工作

協(xié)同過濾最早是由Goldberg等[8]在1992年提出的，后來(lái)被廣泛應(yīng)用于電子商務(wù)領(lǐng)域，并且取得了極大的成功。其核心思想是：在用戶群中尋找與目標(biāo)用戶評(píng)分行為相似的鄰居用戶，然后基于這些鄰居用戶對(duì)服務(wù)的評(píng)分向目標(biāo)用戶做出推薦[9]。目前，已有很多學(xué)者將協(xié)同過濾算法應(yīng)用到服務(wù)推薦過程中，并對(duì)其做出了一系列的改進(jìn)。王海艷等[10]引入服務(wù)的推薦個(gè)性屬性特征來(lái)改進(jìn)傳統(tǒng)的相似度計(jì)算式，并結(jié)合用戶之間的信任關(guān)系對(duì)服務(wù)的評(píng)分值進(jìn)行預(yù)測(cè)，進(jìn)而對(duì)用戶做出推薦。Liu等[11]利用服務(wù)的流行度特征改進(jìn)相似度計(jì)算，并根據(jù)用戶和服務(wù)的地理位置來(lái)縮小相似用戶的尋找范圍，相比傳統(tǒng)推薦算法更加高效；Hu等[12]在尋找相似鄰居時(shí)融入了服務(wù)調(diào)用的時(shí)間信息，并通過線性加權(quán)的方式綜合了基于相似用戶和相似服務(wù)的QoS預(yù)測(cè)結(jié)果。文獻(xiàn)[10~12]均是通過改進(jìn)相似度計(jì)算來(lái)提高算法準(zhǔn)確性，屬于基于近鄰的協(xié)同過濾算法。此外，還有部分研究者利用數(shù)學(xué)模型來(lái)預(yù)測(cè)服務(wù)的QoS，并取得了較好的成果。Wei等[13]利用矩陣分解模型將高維的用戶—服務(wù)矩陣分解為低維的用戶矩陣和服務(wù)矩陣，并將位置屬性融入矩陣分解的正則項(xiàng)中，有效提高了QoS預(yù)測(cè)精度；胡堰等[14]借助隱含類別表示用戶指標(biāo)偏好、用戶及服務(wù)情境三者之間的依賴關(guān)系，并建立隱語(yǔ)義概率模型用于預(yù)測(cè)用戶在特定服務(wù)情境下的個(gè)性化指標(biāo)偏好，然后計(jì)算出每個(gè)候選服務(wù)的效用值進(jìn)行推薦；Wang等[15]考慮到了QoS值在不同時(shí)間段的動(dòng)態(tài)變化特性，對(duì)QoS預(yù)測(cè)值的殘差進(jìn)行零均值拉普拉斯先驗(yàn)分布假設(shè)，將QoS預(yù)測(cè)問題轉(zhuǎn)化為L(zhǎng)asso回歸問題進(jìn)行求解。文獻(xiàn)[13~15]有效利用了數(shù)學(xué)模型的精確性，屬于基于模型的協(xié)同過濾算法?？梢?，上述工作的研究重點(diǎn)均集中在提高QoS值預(yù)測(cè)的準(zhǔn)確性方面，而近年來(lái)有研究者發(fā)現(xiàn)QoS值預(yù)測(cè)的準(zhǔn)確性并不能確保服務(wù)推薦的準(zhǔn)確性，引言已給出相關(guān)示例。

排序?qū)W習(xí)作為一種強(qiáng)監(jiān)督性機(jī)器學(xué)習(xí)算法，能夠直接針對(duì)最終的推薦列表進(jìn)行優(yōu)化，這一特性可以避免根據(jù)QoS值排序來(lái)間接得到推薦列表帶來(lái)的缺陷。根據(jù)優(yōu)化目標(biāo)的不同，排序?qū)W習(xí)主要分為3類：點(diǎn)級(jí)（pointwise）、對(duì)級(jí)（pairwise）、列表級(jí)（listwise）[7]。點(diǎn)級(jí)排序的處理對(duì)象是單獨(dú)的一個(gè)項(xiàng)目，通過預(yù)測(cè)評(píng)分實(shí)現(xiàn)推薦，其相當(dāng)于傳統(tǒng)的預(yù)測(cè)QoS值的服務(wù)推薦方法；對(duì)級(jí)排序是根據(jù)評(píng)分來(lái)定義項(xiàng)目對(duì)之間的偏序關(guān)系，最終通過整合所有項(xiàng)目對(duì)的偏序關(guān)系得到整個(gè)排序列表，而其時(shí)間復(fù)雜度高，且在整合推薦列表時(shí)會(huì)損失一定的準(zhǔn)確性；列表級(jí)排序的處理對(duì)象是所有的項(xiàng)目，直接對(duì)整個(gè)排序列表進(jìn)行優(yōu)化，在運(yùn)行效率和推薦準(zhǔn)確性方面具有更明顯的優(yōu)勢(shì)，因此，成為被研究最多的方法。

Huang等[6]利用基于排列概率的相似度來(lái)尋找更準(zhǔn)確的鄰居用戶，然后通過最小化目標(biāo)用戶和鄰居用戶在未評(píng)分項(xiàng)目集合上的交叉熵?fù)p失函數(shù)，來(lái)得到最優(yōu)的排序列表。Weimer等[16]提出了一種最大化邊界矩陣因式分解算法CoFiRank，通過直接優(yōu)化排序評(píng)價(jià)標(biāo)準(zhǔn)NDCG來(lái)進(jìn)行推薦。Shi等[17]提出一種基于上下文感知的推薦方法，利用張量分解優(yōu)化MAP評(píng)測(cè)準(zhǔn)則，是首個(gè)能夠挖掘用戶隱式反饋和上下文信息，并將列表級(jí)排序?qū)W習(xí)和協(xié)同過濾算法相結(jié)合的方法。但是列表級(jí)排序?qū)W習(xí)算法依然面臨著用戶惡意評(píng)分、數(shù)據(jù)稀疏性等傳統(tǒng)難題，且目前還缺乏將該算法改進(jìn)并應(yīng)用到服務(wù)推薦領(lǐng)域的研究。

3 基于信任擴(kuò)展和列表級(jí)排序?qū)W習(xí)的服務(wù)推存方法

本節(jié)給出基于信任擴(kuò)展和列表級(jí)排序?qū)W習(xí)的服務(wù)推薦方法，該方法首先將用戶表示為已調(diào)用服務(wù)集合的概率分布，基于Kullback-Leibler（KL）距離進(jìn)行概率型用戶相似度的計(jì)算，以此提高用戶相似度計(jì)算的準(zhǔn)確性；然后，利用信任擴(kuò)展模型充分挖掘用戶信任網(wǎng)絡(luò)中的信任關(guān)系，并結(jié)合用戶相似度構(gòu)建為目標(biāo)用戶構(gòu)建可信鄰居集合，以此抵抗某些惡意用戶的攻擊；最后，利用可信鄰居集合改進(jìn)列表級(jí)排序?qū)W習(xí)算法，訓(xùn)練出最優(yōu)的服務(wù)排序列表推薦給用戶。其中，概率型用戶相似度計(jì)算方法、可信鄰居集合構(gòu)建算法（TNSC, trusted neighbor set construction algorithm）以及列表級(jí)排序?qū)W習(xí)預(yù)測(cè)算法（PABL, prediction algorithm based on listwise learning-to-rank）為TELSR的核心，下面重點(diǎn)對(duì)它們進(jìn)行介紹。

3.1 概率型用戶相似度計(jì)算方法

協(xié)同過濾算法的核心步驟是尋找相似用戶，可采用的方法主要有Pearson相關(guān)系數(shù)、余弦相似性、修正的余弦相似性等[10]。目前大多數(shù)服務(wù)推薦算法都是基于Pearson相關(guān)系數(shù)改進(jìn)得來(lái)的，其基本定義如下。

用戶調(diào)用服務(wù)示例如圖1所示，假設(shè)用戶A、B、C共同調(diào)用過的服務(wù)集合為I={a,b,c,d}，這4個(gè)服務(wù)的QoS（如可用性，用百分制表示）分別為A=(0, 20%, 80%, 100%), B=(10%, 0, 80%, 100%), C=(0, 22%, 100%, 89%)，采用Pearson相關(guān)系數(shù)計(jì)算得，即用戶B、用戶C和用戶A是同等相似的。從圖1可以看出，如果根據(jù)服務(wù)可用性大小對(duì)服務(wù)進(jìn)行排序，用戶B對(duì)于服務(wù)a、b的排序與用戶A是相反的，而用戶C對(duì)于服務(wù)c、d的排序與用戶A是相反的。此時(shí)，若利用用戶B做推薦，則其向用戶A推薦的最好服務(wù)是d，正好符合用戶A的需求；若利用用戶C做推薦，則其向用戶A推薦的最好服務(wù)是c，違背用戶A的需求。相比之下，用戶B的推薦結(jié)果更加可信，所以理論上用戶B與用戶A的相似度應(yīng)該更大。原因在于，在實(shí)際推薦系統(tǒng)中，用戶主要關(guān)注排在推薦列表中前面質(zhì)量較優(yōu)的服務(wù)，對(duì)于排在后面質(zhì)量較差（如可用性低于50%）的服務(wù)給予的關(guān)注較少。因此，服務(wù)的排序位置是除了QoS數(shù)據(jù)之外另一個(gè)能夠反映用戶興趣偏好的重要信息。

基于此，本文充分挖掘服務(wù)的排序位置信息，借鑒Mollica等[18]提出的Plackett-Luce模型，將每個(gè)用戶表示為已調(diào)用服務(wù)集合排列的概率分布，然后進(jìn)行用戶相似度的計(jì)算，從而找到更加準(zhǔn)確的相似用戶。為方便下文討論，定義如下。

定義7 概率型用戶相似度。用戶和之間的概率型相似度可定義為

算法1 概率型用戶相似度計(jì)算

begin

6) end for

end

3.2 可信鄰居集合構(gòu)建算法

利用PUSC可計(jì)算其他用戶與目標(biāo)用戶的相似度，然后選取出相似度較大的用戶作為鄰居進(jìn)行推薦。但是當(dāng)推薦系統(tǒng)中存在惡意用戶對(duì)服務(wù)QoS值進(jìn)行虛假評(píng)價(jià)時(shí)，此時(shí)，若把這類用戶當(dāng)作鄰居，會(huì)極大影響推薦的精度?；诖?，本文利用用戶間的信任關(guān)系建立可信鄰居集合來(lái)進(jìn)行推薦，從而避免惡意用戶的攻擊。為了解決傳統(tǒng)基于信任的服務(wù)推薦算法中信任關(guān)系稀疏性問題，本文提出信任擴(kuò)展模型，同時(shí)考慮直接信任關(guān)系和間接信任關(guān)系。

由式(8)可知，用戶和之間的直接信任度與有效推薦行為次數(shù)成正比，因此，其可以甄別某些用戶反常的惡意評(píng)價(jià)行為。然而，在實(shí)際推薦系統(tǒng)中，用戶之間的相互交互記錄往往較少，導(dǎo)致直接信任關(guān)系稀疏性問題。為此，本文利用信任關(guān)系的傳遞特性來(lái)擴(kuò)大用戶的信任范圍，并給出如下定義。

間接信任傳遞關(guān)系如圖2所示。由圖2可知，用戶和均與用戶和之間存在直接信任關(guān)系，根據(jù)信任關(guān)系的傳遞性，可以通過用戶和建立起用戶和之間的間接信任關(guān)系。

圖2 間接信任傳遞關(guān)系

定義11 間接信任度。若用戶的直接信任集合為，利用中所有與用戶有直接信任關(guān)系的用戶來(lái)進(jìn)行信任傳遞，則用戶和之間的間接信任度為

定義12 綜合信任度。通過綜合直接信任度和間接信任度，得到用戶之間的綜合信任度為

定義13 可信相似度。綜合考慮用戶和之間的概率相似度和綜合信任度，得到用戶和的可信相似度為

基于可信相似度的定義，本文提出可信鄰居構(gòu)建算法，如算法2所示。

算法2 可信鄰居構(gòu)建

輸入 目標(biāo)用戶，其他用戶集合，參數(shù)

輸出 目標(biāo)用戶的可信鄰居集合N

begin

7) end for

8)N←按照可信相似度由大到小對(duì)用戶進(jìn)行排序，選取前個(gè)用戶作為目標(biāo)用戶的可信鄰居集合

end

3.3 列表級(jí)排序?qū)W習(xí)預(yù)測(cè)算法

為了利用可信鄰居集合來(lái)提高服務(wù)推薦的準(zhǔn)確性，本文首先利用矩陣分解模型來(lái)預(yù)測(cè)服務(wù)的QoS值，然后利用列表級(jí)排序?qū)W習(xí)算法訓(xùn)練出最優(yōu)的服務(wù)排序模型。為了方便描述，定義參數(shù)如下。

1) 參數(shù)定義

：用戶服務(wù)評(píng)分矩陣，其中，m為用戶的個(gè)數(shù)，n為服務(wù)的個(gè)數(shù)。

：維的服務(wù)隱含特征矩陣。

：隱含特征數(shù)。

：矩陣V的第k列向量，代表服務(wù)的隱含特征向量。

2) 矩陣分解模型

矩陣分解模型是在協(xié)同過濾推薦算法中應(yīng)用最為廣泛的模型之一。其主要思想是將用戶服務(wù)評(píng)分矩陣近似分解為低維的用戶隱含特征矩陣和服務(wù)隱含特征矩陣，計(jì)算式為

算法通過最小化預(yù)測(cè)評(píng)分矩陣和原評(píng)分矩陣的誤差來(lái)實(shí)現(xiàn)QoS值的精確預(yù)測(cè)[21]。在現(xiàn)實(shí)生活中，人們對(duì)于一個(gè)服務(wù)的評(píng)價(jià)往往會(huì)受到所信任好友的影響。因此，為了提高服務(wù)推薦的準(zhǔn)確性，本文在預(yù)測(cè)QoS值時(shí)加入可信鄰居用戶的影響，將式(13)改進(jìn)為

3) 列表級(jí)排序?qū)W習(xí)模型

列表級(jí)排序?qū)W習(xí)直接針對(duì)最終的排序列表進(jìn)行優(yōu)化，可以避免僅僅根據(jù)QoS值排序帶來(lái)的不準(zhǔn)確性。其核心思想是：將預(yù)測(cè)排序列表和正確排序列表之間的交叉熵作為損失函數(shù)，通過訓(xùn)練過程最小化其交叉熵，從而使最終得到的預(yù)測(cè)排序模型最接近正確排序模型[7]。本文基于top-1概率，將交叉熵?fù)p失函數(shù)定義如下。

定義14 top-1概率。服務(wù)在用戶的推薦列表中排在第一位置的概率，定義為

基于交叉熵?fù)p失函數(shù)的定義，給出列表級(jí)排序?qū)W習(xí)預(yù)測(cè)算法，具體如算法3所示。

算法3 列表級(jí)排序?qū)W習(xí)預(yù)測(cè)

輸出 每一個(gè)用戶的最佳服務(wù)推薦列表

begin

1) 根據(jù)訓(xùn)練數(shù)據(jù)集，利用式(15)計(jì)算得到正確排序列表的概率分布

2) 利用式(14)算出初始所有服務(wù)的QoS預(yù)測(cè)值

3) 利用式(15)算出初始預(yù)測(cè)排序列表的概率分布

4) 利用式(16)計(jì)算初始交叉熵?fù)p失函數(shù)

6) 更新用戶隱含特征矩陣和服務(wù)隱含特征矩陣

7) 記錄上次交叉熵?fù)p失函數(shù)

8) 利用式(14)算出新的所有服務(wù)的QoS預(yù)測(cè)值

9) 利用式(15)算出新的預(yù)測(cè)排序列表的概率分布

13) end for

15) 將所有服務(wù)按照top-1概率由大到小進(jìn)行排序，得到最佳服務(wù)排序列表，推薦給用戶

16) end for

end

3.4 TELSR描述

經(jīng)過上述分析，TELSR的具體過程如下。

1) 運(yùn)用PUSC計(jì)算每一個(gè)用戶與其他用戶的概率型相似度。

2) 運(yùn)用TNSC為每一個(gè)用戶建立可信鄰居集合。

3) 根據(jù)訓(xùn)練數(shù)據(jù)集得到用戶服務(wù)評(píng)分矩陣，初始化用戶隱含特征矩陣和服務(wù)隱含特征矩陣。

4) 運(yùn)用PABL得到每一個(gè)用戶的最佳服務(wù)推薦列表。

TELSR首先通過Plackett-Luce模型將用戶表示為已調(diào)用服務(wù)集合的概率分布，并利用PUSC計(jì)算用戶的概率型相似度，其優(yōu)點(diǎn)在于利用了服務(wù)的排序位置信息，使相似度計(jì)算更加準(zhǔn)確；為了消除推薦系統(tǒng)中惡意用戶隨意打分的影響，利用TNSC為用戶建立可信鄰居集合，其優(yōu)點(diǎn)在于充分挖掘用戶間的直接信任關(guān)系和間接信任關(guān)系，緩解了用戶信任網(wǎng)絡(luò)稀疏性問題；最終利用可信鄰居集合改進(jìn)QoS預(yù)測(cè)值的準(zhǔn)確性，并利用列表級(jí)排序?qū)W習(xí)的強(qiáng)大數(shù)據(jù)處理能力，訓(xùn)練出最優(yōu)的排序模型，為用戶提供最符合其偏好的服務(wù)推薦列表。

3.5 算法時(shí)間復(fù)雜度

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)置

本實(shí)驗(yàn)使用由Zheng等[22]收集并公共發(fā)布的WS-DREAM數(shù)據(jù)集，它是由分布在全球20多個(gè)國(guó)家的150個(gè)電腦節(jié)點(diǎn)收集的QoS信息，構(gòu)成了約150萬(wàn)條QoS調(diào)用記錄，其內(nèi)容主要包括Web服務(wù)的往返響應(yīng)時(shí)間RTT、數(shù)據(jù)塊大小、響應(yīng)結(jié)果等屬性，表1展示了該數(shù)據(jù)集的部分服務(wù)實(shí)例信息。

本文選用往返響應(yīng)時(shí)間RTT作為評(píng)價(jià)QoS的標(biāo)準(zhǔn)，當(dāng)用戶調(diào)用某服務(wù)超過100次時(shí)，計(jì)算出RTT的均值，最終得到一個(gè)150×100的用戶服務(wù)矩陣。為了研究算法的推薦準(zhǔn)確性，本文從原始的用戶服務(wù)矩陣中隨機(jī)地剔除部分QoS值，形成了5個(gè)不同的稀疏矩陣，其密度分別為0.04、0.08、0.12、0.16、0.20。之所以選擇小密度矩陣，是因?yàn)樵诤Ａ康腤eb服務(wù)環(huán)境中，用戶只調(diào)用過很少的服務(wù)，因此，其真實(shí)的用戶服務(wù)矩陣就是很稀疏的。

本文使用5重交叉驗(yàn)證作為實(shí)驗(yàn)方法，將稀疏矩陣隨機(jī)分為5份，每次選擇其中的4份即矩陣的80%作為訓(xùn)練集，選擇余下的1份即矩陣的20%作為測(cè)試集。每次實(shí)驗(yàn)重復(fù)5次，取平均值得到最終的評(píng)估結(jié)果。由于本文認(rèn)為用戶更在意最終獲得的服務(wù)推薦列表中服務(wù)排序的準(zhǔn)確性，因此，采用NDCG（normalized discounted cumulative gain）作為衡量算法推薦性能的標(biāo)準(zhǔn)。NDCG值越大，表示算法的推薦性能越好[7]。

4.2 參數(shù)對(duì)算法性能的影響

表1 部分?jǐn)?shù)據(jù)集信息

圖3 參數(shù)對(duì)于推薦性能的影響

圖4 參數(shù)對(duì)于推薦性能的影響

圖5 隱含特征數(shù)d對(duì)于推薦性能的影響

4.3 算法運(yùn)行時(shí)間的比較

表2 k取值的影響

由表2可以看出，隨著的取值不斷增大，算法的推薦性能提高非常小，但是算法的運(yùn)行時(shí)間卻大幅增加。當(dāng)=3時(shí)，算法的推薦性能@10比=1時(shí)提高了2.9%，但是運(yùn)行時(shí)間增加了341%。而=1時(shí)，算法就可以在較短的運(yùn)行時(shí)間內(nèi)實(shí)現(xiàn)較好的推薦性能。因此，本文實(shí)驗(yàn)中均設(shè)置=1。

為了衡量算法的運(yùn)行時(shí)間性能，將TELSR與以下4種經(jīng)典的推薦算法做比較。

1) CF-DNC[23]

該算法首先利用“興趣相似用戶集選取算法”動(dòng)態(tài)選取目標(biāo)用戶的相似鄰居，然后提出“用戶信任計(jì)算模型”，篩選出目標(biāo)用戶的可信鄰居用戶集，最后提出了一種新的協(xié)同過濾算法，綜合利用可信鄰居的評(píng)分信息，對(duì)服務(wù)的評(píng)分值進(jìn)行預(yù)測(cè)。

2) TACF[12]

該算法有效融合了服務(wù)調(diào)用時(shí)間信息，提出“時(shí)間感知的相似度算法”，尋找更加準(zhǔn)確的相似用戶和相似服務(wù)，然后設(shè)計(jì)“個(gè)性化隨機(jī)游走算法”來(lái)克服數(shù)據(jù)的稀疏性，最后利用混合協(xié)同過濾算法預(yù)測(cè)服務(wù)的QoS值。

3) listPMF[24]

該算法改進(jìn)了概率矩陣分解模型，根據(jù)用戶評(píng)分得到用戶的偏好序列，并通過最大化預(yù)測(cè)的偏好序列和已知的偏好序列的后驗(yàn)概率來(lái)實(shí)現(xiàn)項(xiàng)目的推薦，屬于基于列表級(jí)排序的協(xié)同過濾算法。

4) listCF[6]

該算法通過計(jì)算用戶共同打分項(xiàng)目集合的Jansen-Shannon散度，來(lái)度量用戶的相似度，并通過最小化目標(biāo)用戶和鄰居用戶的加權(quán)交叉熵?fù)p失函數(shù)來(lái)做預(yù)測(cè)，屬于基于列表級(jí)排序的協(xié)同過濾算法。

圖6 不同算法運(yùn)行時(shí)間的比較

由圖6可以看出，隨著矩陣密度的增加，本文提出的TELSR的運(yùn)行時(shí)間比listPMF短，但是比CF-DNC、TACF和listCF稍長(zhǎng)，具體原因如下。

1) listPMF基于用戶和項(xiàng)目的隱含特征矩陣來(lái)預(yù)測(cè)用戶的偏好序列。當(dāng)矩陣密度增加時(shí)，需要預(yù)測(cè)的用戶偏好序列數(shù)量增多，且隨著隱含特征矩陣的不斷更新，算法計(jì)算量成倍增長(zhǎng)，導(dǎo)致listPMF的運(yùn)行時(shí)間大幅度增加，甚至超過了TELSR。

2) CF-DNC和TACF均是在傳統(tǒng)的Pearson相關(guān)系數(shù)的基礎(chǔ)上改進(jìn)的相似度計(jì)算方法，可以直接利用數(shù)據(jù)集中的QoS值。而TELSR采用PUSC，首先需要根據(jù)已有的QoS數(shù)據(jù)計(jì)算出用戶調(diào)用服務(wù)的概率分布，才能進(jìn)行下一步的相似度計(jì)算。

3）listCF選取出鄰居用戶之后，直接利用列表級(jí)排序算法進(jìn)行QoS值預(yù)測(cè)。而TELSR還增加了用戶信任度的計(jì)算，并結(jié)合用戶相似度提出了可信鄰居構(gòu)建算法TNSC。

由于TELSR屬于混合型算法，內(nèi)容同時(shí)涉及用戶相似度、信任度和QoS預(yù)測(cè)，因此，其計(jì)算量更大，但根據(jù)第3.5節(jié)和圖6可知，隨著矩陣密度的增加，其運(yùn)行時(shí)間仍保持了線性增長(zhǎng)的趨勢(shì)，說(shuō)明TELSR算法是可以應(yīng)用在大型Web服務(wù)數(shù)據(jù)集上的。

4.4 推薦準(zhǔn)確性的比較

2) 在5種算法中，listCF和TELSR表現(xiàn)最為優(yōu)異，它們均屬于listwise CF，但是TELSR在listCF的相似度的基礎(chǔ)上加入了信任度的計(jì)算，因此其推薦性能相對(duì)于listCF有所提升，且提升幅度隨著矩陣密度的增加而增加。因?yàn)殡S著矩陣中已知QoS值的服務(wù)的增多，TELSR能夠在用戶之間發(fā)現(xiàn)更多的有效推薦行為，從而使其信任度計(jì)算更加準(zhǔn)確，進(jìn)一步提升了算法的推薦性能。

表3 推薦準(zhǔn)確性比較

4.5 抵抗惡意用戶能力的比較

圖7 抵抗惡意用戶能力比較

由圖7可知，隨著惡意用戶比例的增加，TACF和listCF的推薦性能下降很快，因?yàn)樗鼈儧]有建立任何防御機(jī)制，一旦系統(tǒng)中的相似用戶演變?yōu)閻阂庥脩?，算法的?zhǔn)確性會(huì)受到很大的影響；而CF-DNC考慮到了用戶的信任關(guān)系，具備一定的抗攻擊能力，但是其在計(jì)算相似度時(shí)沒有考慮服務(wù)的排序位置信息，所以導(dǎo)致推薦精度不夠高；TELSR利用概率分布模型計(jì)算用戶相似度，并結(jié)合用戶的信任關(guān)系進(jìn)行服務(wù)推薦，在具備較高推薦精度的同時(shí)，還能夠較好地抵抗惡意用戶的攻擊。

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

本文針對(duì)傳統(tǒng)服務(wù)推薦算法中僅依據(jù)QoS預(yù)測(cè)值排序帶來(lái)的不準(zhǔn)確性以及用戶信任關(guān)系稀疏性問題，提出基于信任擴(kuò)展和列表級(jí)排序?qū)W習(xí)的服務(wù)推薦方法。該方法首先在分析服務(wù)排序位置信息重要性的基礎(chǔ)上，給出概率型用戶相似度計(jì)算方法，提高了用戶相似度計(jì)算的準(zhǔn)確性；然后，利用信任擴(kuò)展模型充分挖掘用戶之間的信任關(guān)系，并給出可信鄰居構(gòu)建算法，以抵抗某些惡意用戶的攻擊；最后，利用可信鄰居集合改進(jìn)矩陣分解模型，并給出列表級(jí)排序?qū)W習(xí)預(yù)測(cè)算法，為用戶訓(xùn)練出最優(yōu)的服務(wù)排序模型。實(shí)驗(yàn)證明，TELSR具有較高的推薦精度，并且可以應(yīng)用到大型的Web服務(wù)數(shù)據(jù)集上。下一步工作將優(yōu)化用戶信任模型，并考慮QoS值的時(shí)間效應(yīng)，進(jìn)一步增強(qiáng)推薦模型在動(dòng)態(tài)環(huán)境中的適用性。

[1] 李玲, 劉敏, 成國(guó)慶. 一種基于FAHP的多維QoS的局部最優(yōu)服務(wù)選擇模型[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(10): 1997-2010.

LI L, LIU M, CHENG G Q. A local optimal model of service selection of multi-QoS based on FAHP[J]. Chinese Journal of Computers, 2015, 38(10): 1997-2010.

[2] MA Y, WANG S G, YANG F C, et al. Predicting QoS values via multi-dimensional QoS data for Web service recommendations[C]//IEEE Conference on Web Services. 2015: 249-256.

[3] LIU Z, MA J, JIANG Z, et al. IRLT: integrating reputation and local trust for trustworthy service recommendation in service-oriented social networks[J]. Plos One, 2016, 11(3):e0151438.

[4] 張莉, 張斌, 黃利萍, 等. 基于服務(wù)調(diào)用特征模式的個(gè)性化Web服務(wù)QoS預(yù)測(cè)方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(5):1066-1075.

ZHANG L, ZHANG B, HUANG L P, et al. A personalized Web service quality prediction approach based on invoked feature model[J]. Journal of Computer Research and Development, 2013, 50(5): 1066-1075.

[5] QI L, DOU W, ZHOU Y, et al. A context-aware service evaluation approach over big data for cloud applications[J]. IEEE Transactions on Cloud Computing, 2015, PP (99): 1.

[6] HUANG S S, WANG S Q, LIU T Y, et al. Listwise collaborative filtering[C]//The 38th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). 2015: 343-352.

[7] 黃震華, 張佳雯, 田春岐. 基于排序?qū)W習(xí)的推薦算法研究綜述[J]. 軟件學(xué)報(bào), 2016, 27(3): 691-713.

HUANG Z H, ZHANG J W, TIAN C Q. Survey on learning-to-rank based recommendation algorithms[J]. Journal of Software, 2016, 27(3): 691-713.

[8] GOLDBERG D. Using collaborative filtering to weave an information tapestry[J]. Communications of the ACM, 1992, 35(12): 61-70.

[9] PARK C, KIM D, OH J, et al. TRecSo: enhancing top-recommendation with social information[C]//International Conference Companion on World Wide Web, International World Wide Web Conferences Steering Committee. 2016: 89-90.

[10] 王海艷, 楊文彬, 王隨昌. 基于可信聯(lián)盟的服務(wù)推薦方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(2): 301-311.

WANG H Y, YANG W B, WANG S C. A service recommendation method based on trustworthy community[J]. Chinese Journal of Computers, 2014, 37(2): 301-311.

[11] LIU J, TANG M, ZHENG Z, et al. Location-aware and personalized collaborative filtering for Web service recommendation[J]. IEEE Transactions on Services Computing, 2015, 9 (5): 686-699.

[12] HU Y, PENG Q, HU X. A time-aware and data sparsity tolerant approach for Web service recommendation[C]//IEEE International Conference on Web Services. 2014: 33-40.

[13] WEI L, YIN J, DENG S, et al. Collaborative Web service QoS prediction with location-based regularization[C]//IEEE International Conference on Web Services. 2012: 464-471.

[14] 胡堰, 彭啟民, 胡曉惠. 一種基于隱語(yǔ)義概率模型的個(gè)性化Web服務(wù)推薦方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(8): 1781-1793.

HU Y, PENG Q M, HU X H. A personalized Web service recommendation method based on latent semantic probabilistic model[J]. Journal of Computer Research and Development, 2014, 51(8): 1781-1793.

[15] WANG X Y, ZHU J K, ZHENG Z B, et al. A spatial-temporal QoS prediction approach for time-aware Web service recommendation[J]. ACM Transactions on the Web, 2016, 10(1): 1-25.

[16] WEIMER M, KARATZOGLOU A, LE Q V, et al. Cofirank maximum margin matrix factorization for collaborative ranking[C]//The 21th Int’l Conference on Neural Information Processing Systems. 2007: 1-8.

[17] SHI Y, KARATZOGLOU A, BALTRUNAS L, et al. TFMAP: optimizing MAP for top-context-aware recommendation[C]//ACM Special Interest Group on Information Retrieval. 2012: 155-164.

[18] MOLLICA C, TARDELLA L. Bayesian mixture of Plackett-Luce models for partially ranked data[J]. Statistics, 2015, 2(4): 208-222.

[19] CAO Z, QIN T, LIU T Y, et al. Learning to rank: from pairwise approach to listwise approach[C]//The 2007 ACM conference on Machine learning. 2007: 129-136.

[20] FANG W, ZHANG C, SHI Z, et al. BTRES: beta-based trust and reputation evaluation system for wireless sensor networks[J]. Journal of Network & Computer Applications, 2015(59): 88-94.

[21] 郭弘毅, 劉功申, 蘇波, 等. 融合社區(qū)結(jié)構(gòu)和興趣聚類的協(xié)同過濾推薦算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(8): 1664-1672.

GUO H Y, LIU G S, SU B, et al. Collaborative filtering recommendation algorithm combining community structure and interest clusters[J]. Journal of Computer Research and Development, 2016, 53(8): 1664-1672.

[22] ZHENG Z B, ZHANG Y L, LYU M R. Distributed QoS evaluation for real-world Web services[C]//The 8th International Conference on Web Services. 2010: 83-90.

[23] 賈冬艷, 張付志. 基于雙重鄰居選取策略的協(xié)同過濾推薦算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(5): 1076-1084.

JIA D Y, ZHANG F Z. A collaborative filtering recommendation algorithm based on double neighbor choosing strategy[J]. Journal of Computer Research and Development, 2013, 50(5): 1076-1084.

[24] LIU J, WU C, XIONG Y, et al. List-wise probabilistic matrix factorization for recommendation[J]. Information Sciences, 2014(278): 434-447.

Trust expansion and listwise learning-to-rank based service recommendation method

FANG Chen1,2, ZHANG Hengwei1,2, ZHANG Ming1,2, WANG Jindong1,2

1. The Third College, Information Engineering University, Zhengzhou 450001, China 2. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China

In view of the problem of trust relationship in traditional trust-based service recommendation algorithm, and the inaccuracy of service recommendation list obtained by sorting the predicted QoS, a trust expansion and listwise learning-to-rank based service recommendation method (TELSR) was proposed. The probabilistic user similarity computation method was proposed after analyzing the importance of service sorting information, in order to further improve the accuracy of similarity computation. The trust expansion model was presented to solve the sparseness of trust relationship, and then the trusted neighbor set construction algorithm was proposed by combining with the user similarity. Based on the trusted neighbor set, the listwise learning-to-rank algorithm was proposed to train an optimal ranking model. Simulation experiments show that TELSR not only has high recommendation accuracy, but also can resist attacks from malicious users.

service recommendation, learning-to-rank, probabilistic user similarity, trust relationship

TP393

A

10.11959/j.issn.1000-436x.2018007

方晨（1993-），男，安徽宿松人，信息工程大學(xué)碩士生，主要研究方向?yàn)榉?wù)推薦、數(shù)據(jù)挖掘等。

張恒?。?978-），男，河南洛陽(yáng)人，博士，信息工程大學(xué)副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)安全與攻防對(duì)抗、信息安全風(fēng)險(xiǎn)評(píng)估。

張銘（1993-），男，河南安陽(yáng)人，信息工程大學(xué)碩士生，主要研究方向?yàn)樵瀑Y源調(diào)度。

王晉東（1966-），男，山西洪洞人，信息工程大學(xué)教授，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全、云資源管理。

2017-04-05；

2017-12-26

張恒巍，13083710760@163.com

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61303074, No.61309013）；河南省科技攻關(guān)計(jì)劃基金資助項(xiàng)目（No.12210231003）

: The National Natural Science Foundation of China (No.61303074, No.61309013), Henan Science and Technology Research Project (No.12210231003)