張繼康,付曉東,2,岳 昆,劉 驪,劉利軍(昆明理工大學(xué)信息工程與自動化學(xué)院云南省計算機技術(shù)應(yīng)用重點實驗室,昆明650500)
2(昆明理工大學(xué)航空學(xué)院,昆明650500)
3(云南大學(xué)信息學(xué)院,昆明650091)
E-mail:xiaodong_fu@hotmail.com
在線服務(wù)是指利用互聯(lián)網(wǎng)技術(shù),向用戶提供線上服務(wù)的方式.現(xiàn)如今互聯(lián)網(wǎng)上存在大量功能相似或者相同的在線服務(wù)[1].用戶在挑選服務(wù)時如何在大量的在線服務(wù)中快速準確選擇到需要的服務(wù)是一個越來越嚴重的問題.另外,不法商家為了提高自己服務(wù)被選擇的幾率,會惡意修改用戶給與的在線服務(wù)的評價,導(dǎo)致評價結(jié)果無法正確反應(yīng)在線服務(wù)的性能,誘導(dǎo)用戶做出錯誤選擇[2].以上行為導(dǎo)致用戶對互聯(lián)網(wǎng)中的在線服務(wù)無法進行有效的篩選.因此,通過給服務(wù)排名的方式向用戶提供在線服務(wù)成為了如今在線服務(wù)評價的主要手段[3].服務(wù)排名是把在線服務(wù)各項性能量化,最后整體得到在線服務(wù)評價結(jié)果的方法.用戶在面對眾多在線服務(wù)時,會根據(jù)排序名次挑選滿足需求的服務(wù).所以使用在線服務(wù)評價方法可以幫助用戶在互聯(lián)網(wǎng)中快速準確的找到滿足需求的在線服務(wù).
累加法、平均值法、構(gòu)圖法等方法是目前工業(yè)界和學(xué)術(shù)界常用的在線服務(wù)評價方法[4].這些方法為了方便計算,通常對在線服務(wù)進行評價時都假設(shè)用戶具有相同的評價準則[5].然而受用戶主觀心理因素和消費偏好的影響,用戶群體很難具有相似的評價準則,所以用戶服務(wù)評分無法客觀的的反應(yīng)服務(wù)質(zhì)量[6,7].這種情況下,即使性能相同的服務(wù)也可能會得到不同的評分.因此現(xiàn)有方法得到的評價結(jié)果會對用戶選擇起到誘導(dǎo)作用,做出不正確的選擇.此外,互聯(lián)網(wǎng)中還存在惡意修改或大批量增加在線服務(wù)的評分數(shù)據(jù),來提高在線服務(wù)排序名次的行為,導(dǎo)致用戶根據(jù)排序名次進行服務(wù)選擇時會產(chǎn)生有利于自己的結(jié)果[8].
為解決上述問題,本文提出了一種利用Plackett-Luce模型[9,1https://www.amazon.cn/0]的在線服務(wù)評價方法,方法基于用戶評價準則不一致的情況,根據(jù)用戶對不同的在線服務(wù)的評分獲取用戶對服務(wù)可比較的偏好關(guān)系[11],根據(jù)在線服務(wù)間可比較的偏好關(guān)系進而得到在線服務(wù)評價結(jié)果.
近年來,根據(jù)用戶評價信息判斷服務(wù)之間優(yōu)劣關(guān)系的研究工作已經(jīng)成為熱點.文獻[12]的研究提出基于服務(wù)屬性的在線服務(wù)評價方法,例如價格、銷量、信譽、評分等等.文獻[13https://www.ebay.cn/-15]指出可以基于在線服務(wù)特征對在線服務(wù)進行評價,從大量評論信息中使用自然語言處理技術(shù)抽取服務(wù)描述信息對服務(wù)進行評價,得到最終評價結(jié)果.文獻[16]指出目前工業(yè)界大部分是通過累加法與平均值法計算獲取最終的評價值.平均值法是將所有用戶對某個在線服務(wù)的評分進行累加得到一個總的服務(wù)評分,然后除以用戶數(shù)量,將所得到的結(jié)果作為該服務(wù)的評價結(jié)果,目前Amazon1https://www.amazon.cn/和天貓2https://www.tmall.com/是使用平均值法作為網(wǎng)站內(nèi)部的評價方法.累加法將用戶對服務(wù)的評分進行分類并統(tǒng)計:當用戶評分為4、5時,表示好評,即總分+1分;當用戶評分為3時,表示中評,即得0分;當用戶評分為1、2,表示為差評,即總分-1分.然后對總分進行累加,將所得到的結(jié)果作為該服務(wù)的評價結(jié)果,目前eBay3https://www.ebay.cn/和淘寶4https://www.taobao.com/是使用累加法作為網(wǎng)站內(nèi)部的評價方法.但是每位用戶對在線服務(wù)的評價準則和偏好只需要滿足自己的需求,很難在用戶群體中出現(xiàn)一致的偏好.因此,以上研究提出的在線服務(wù)評價方法涉及到用戶反饋信息實質(zhì)是不可比較的,通過這些方法得到的在線服務(wù)評價結(jié)果很難反應(yīng)在線服務(wù)的真是性能.
文獻[17]的研究是根據(jù)用戶的多維度屬性評價對服務(wù)的信任進行綜合評價,進而得到個性化的評價結(jié)果.文獻[18]提出了一種改進熵權(quán)的在線服務(wù)評價方法,對于多維度屬性以主客觀權(quán)重相結(jié)合的方法得到最終的評價結(jié)果.上述研究雖然都考慮到用戶對在線服務(wù)評價準則不同的問題,但是還是根據(jù)用戶服務(wù)評分直接計算得到最終評價結(jié)果,沒有解決評分不可比較問題.文獻[19]考慮從用戶服務(wù)偏好入手解決該問題,構(gòu)建加權(quán)有向圖并計算最強路徑得到最終的評價結(jié)果.文獻[20]的研究基于偏好不一致的思路,以社會選擇函數(shù)[21]為基礎(chǔ)提出基于Copeland社會選擇理論的在線服務(wù)評價方法,構(gòu)建有向無環(huán)偏好圖獲取在線服務(wù)評價結(jié)果.上述研究雖然考慮到了用戶偏好不一致的問題,但是提出的解決辦法運行時間較長,整體效率較低.
考慮到以上研究中存在的不足,在用戶評價準則不一致情況下,本文在不假設(shè)用戶偏好一致的情況下,首先以用戶對服務(wù)的評分為基礎(chǔ),將用戶對不同在線服務(wù)的評分轉(zhuǎn)換成用戶服務(wù)可比較的偏好關(guān)系,通過可比較的偏好關(guān)系獲取每個服務(wù)的占優(yōu)次數(shù);其次利用Plackett-Luce模型,將占優(yōu)次數(shù)轉(zhuǎn)換為概率;最后通過概率求解得出在線服務(wù)評價結(jié)果.
定義1.定義 U={u1,u2,…,um}為用戶集合,定義 S={s1,s2,…,sn}為在線服務(wù)集合.其中,m 表示用戶人數(shù),n表示在線服務(wù)數(shù)量.
定義 2.定義 R=[rij]m×n(i=1,2,…,m;j=1,2,3,…,n)為用戶-服務(wù)評分矩陣;其中,rij表示第i位用戶ui對第j個在線服務(wù)sj的評分,若存在rij=0,則表示用戶ui未對在線服務(wù)sj進行評分.
定義3.在線服務(wù)評價結(jié)果 P={p1,p2,…,pn},其中 pn表示第n個服務(wù)的評價值.若px>py,則表示服務(wù)sx優(yōu)于服務(wù)sy.
顯然,一種有效的在線服務(wù)評價方法應(yīng)當滿足以下準則:
1)反轉(zhuǎn)對稱性:對不同在線服務(wù) sx、sy(1≤x,y≤n且 x≠y),若所有用戶都認為服務(wù)sx比服務(wù)sy好,則最終結(jié)果為 sxsy.若每位用戶改變想法,即每位用戶都認為服務(wù)sy比服務(wù)sx好,則最終結(jié)果為 sxsy.
2)單調(diào)性:若有服務(wù)排序sxsy,則提高用戶對服務(wù)sx的評分,則結(jié)果仍是sxsy;
3)非獨裁性:若用戶群體中只有一個用戶認為sx比服務(wù)sy好,而其他所有用戶認為sy比服務(wù)sx好,則最終結(jié)果結(jié)果不可能是sxsy;
4)抗操縱性:若存在服務(wù)排序sxsy,那么增加給予服務(wù)sy高評分的用戶,則結(jié)果仍是sxsy;
例1.假設(shè)有3個用戶共同對4個在線服務(wù)進行評分,評分矩陣如表1所示.
表1 用戶-服務(wù)評分表Table 1 User-service score sheet
根據(jù)表1的數(shù)據(jù),利用eBay網(wǎng)站使用的累加法(Sum)和Amazon網(wǎng)站使用的平均值法(Avg)的得到評價值如表2所示.
由表1可見,每位用戶給出的評價值是個人效用,無法和其他用戶的評價比較.無法說明服務(wù)s1給用戶u3的表現(xiàn)比服務(wù)s3給用戶u1的表現(xiàn)更好.所以用戶服務(wù)評分無法去直接計算,且運用服務(wù)評分直接計算得到的在線服務(wù)評價結(jié)果無法反映在線服務(wù)的真是性能.
此外,如果將用戶u1對服務(wù)s2的評分提高至5分,這個操作會提升服務(wù)s2的評價值.但對其他服務(wù)的評價結(jié)果沒有影響,這將導(dǎo)致服務(wù)s2的評價結(jié)果大大提升,所以上述方法抗操縱性較弱.因此,本文提出一種利用Plackett-Luce模型的在線服務(wù)評價方法,從服務(wù)偏好和服務(wù)占優(yōu)次數(shù)的角度解決了在線服務(wù)評分不可比較的問題,同時提高了評價方法的抗操縱性.
表2 評價值表Table 2 Evaluation value table
Plackett-Luce模型是一個排序概率模型,描述模型內(nèi)部參數(shù)排序的概率[22,23].對內(nèi)部參數(shù)進行排序時,Plackett-Luce模型把排序過程分成許多個階段且每個階段互不影響,并在每個階段選出一個最優(yōu)服務(wù).在當前階段中,計算所有服務(wù)排序名次為第一的概率,把排序概率值最高的服務(wù)作為當前階段的最優(yōu)服務(wù),重復(fù)這個過程直到所有階段結(jié)束,得到服務(wù)的排序結(jié)果.
基于以上分析,本文將每位用戶對不同服務(wù)的評分計算獲取該用戶對所有服務(wù)的偏好關(guān)系,然后通過偏好關(guān)系,得到每個服務(wù)的占優(yōu)次數(shù).通過占優(yōu)次數(shù)解決了用戶評分準則不一致導(dǎo)致的不同用戶對同一服務(wù)的評分不可比較的問題.最后根據(jù)Plackett-Luce模型對數(shù)似然函數(shù)的迭代函數(shù)從概率的角度推斷得到每個服務(wù)在整體服務(wù)中排序的概率,把排序權(quán)重轉(zhuǎn)化的概率后作為評價結(jié)果向用戶展示.
定義 4.用戶-服務(wù)偏好關(guān)系矩陣 Pre=[preij]m×n(i=1,2,3,…,m;j=1,2,3,…,n).其中,preij表示第 i位用戶 ui對第j個在線服務(wù)sj的偏好值.其中preij的計算公式如下所示:
對于同一用戶,服務(wù)評分是可以比較的.所以計算用戶-服務(wù)評分得到每位用戶關(guān)于每個服務(wù)的偏好值pre,填入偏好矩陣Pre.在相同的情況下pre值大的服務(wù)被用戶選擇的概率更大.
算法1.根據(jù)用戶服務(wù)評分矩陣R得到用戶服務(wù)偏好矩陣Pre.
輸入:用戶服務(wù)評分矩陣R
輸出:用戶服務(wù)偏好矩陣Pre
算法1根據(jù)用戶服務(wù)評分矩陣R得到用戶服務(wù)偏好矩陣Pre,根據(jù)矩陣Pre中每位用戶對每個服務(wù)的偏好關(guān)系確定服務(wù)的占優(yōu)次數(shù).
定義5.ui是一個用戶,其評價的在線服務(wù)之間的偏好關(guān)系:若 preix>preiy,則偏好關(guān)系為 sxsy;若 preix=preiy,則偏好關(guān)系為 sx~sy;若 preix<preiy,則偏好關(guān)系為 sxsy.其中sxsy表示用戶ui認為服務(wù)sx優(yōu)于服務(wù)sy;sx~sy表示用戶ui認為服務(wù)sx和服務(wù)sy無差別;sxsy表示用戶ui認為服務(wù)sy優(yōu)于服務(wù)sx.
定義 6.服務(wù)占優(yōu)次數(shù)矩陣 T=[tij]m×n(i=1,2,3,…,m;j=1,2,3,…,n),其中 tij表示服務(wù) sj在用戶 ui偏好下的占優(yōu)次數(shù).
根據(jù)定義6,若在用戶ui偏好下將服務(wù)sx和服務(wù)sy進行比較,那么服務(wù)sx的占優(yōu)次數(shù)tix計算方式如下所示:
服務(wù)占優(yōu)次數(shù)矩陣T是將m個用戶評價的n個在線服務(wù)根據(jù)偏好值pre進行統(tǒng)計,若pre值大則記為占優(yōu)1次.在每位用戶的偏好下,每個服務(wù)都要和其他所有服務(wù)進行偏好值比較,統(tǒng)計每個服務(wù)的占優(yōu)次數(shù).
算法2.根據(jù)用戶服務(wù)偏好矩陣Pre得到服務(wù)占優(yōu)次數(shù)矩陣T.
輸入:用戶服務(wù)偏好矩陣Pre
輸出:服務(wù)占優(yōu)次數(shù)矩陣T
算法2根據(jù)用戶偏好矩陣Pre構(gòu)建服務(wù)占優(yōu)次數(shù)矩陣T.在得到矩陣T后根據(jù)矩陣中每位用戶偏好下每個服務(wù)的占優(yōu)次數(shù)tij得到每個服務(wù)在所有用戶偏好下總的占優(yōu)次數(shù).
定義7.用W表示服務(wù)在所有用戶偏好下總的占優(yōu)次數(shù),W={W1,W2,W3,…,Wn}.其中 W 計算公式如下所示:
累加每個服務(wù)在所有用戶偏好下的占優(yōu)次數(shù)t,得到每個服務(wù)在所有用戶偏好下總的占優(yōu)次數(shù)W.根據(jù)得到的服務(wù)總的占優(yōu)次數(shù)W,從概率的角度推斷求解每個在線服務(wù)的評價結(jié)果.
通過Plackett-Luce模型的對數(shù)似然函數(shù)(γ)構(gòu)建關(guān)于權(quán)重值的迭代函數(shù)Q(γ),找到使對數(shù)似然函數(shù)(γ)取得最大值時的權(quán)重值γ的值.把權(quán)重值轉(zhuǎn)化的概率,通過服務(wù)概率值大小對在線服務(wù)進行排序.
由于對數(shù)似然函數(shù)(γ)無法直接求解得到最大值,所以需要通過迭代的方式求解使得對數(shù)似然函數(shù)(γ)取得最大值的γ的值.
定義8.迭代函數(shù)Q(γx)如下所示:
Nxy表示服務(wù)sx和服務(wù)sy的總占優(yōu)次數(shù)之和.
|≤ε,則認為當前得到的結(jié)果 接近最優(yōu)的權(quán)重
x
定義10.服務(wù)的排序權(quán)重值 γ ={γ1,γ2,γ3,…,γn},在Plackett-Luce模型中,服務(wù)sx的排序概率求解如下所示:
在用戶群體中,若服務(wù)sx與服務(wù)sy比較時有超過一半的用戶認為服務(wù)sx比服務(wù)sy好,則sx稱為孔多塞候選服務(wù).
證明:有超過一半的用戶認為sx優(yōu)于sy,則Wx大于Wy,即服務(wù)sx的初始權(quán)重值比服務(wù)sy的初始權(quán)重值大,所以服務(wù)sx的評價結(jié)果不會比sy差.因此本方法滿足孔多塞性.
孔多塞性表明最終排序結(jié)果滿足用戶群體中多數(shù)人的偏好.評價結(jié)果中孔多塞候選服務(wù)越多,那么評價結(jié)果就越滿足多數(shù)人的偏好.
將兩個在線服務(wù)sxsy進行比較,若用戶群體中僅有一位用戶認為服務(wù)sx優(yōu)于sy,其余所有用戶都認為服務(wù)sy比服務(wù)sx好,那么最終排序結(jié)果服務(wù)sx的排序名次不會比服務(wù)sy高.
證明:僅有一位用戶ui認為服務(wù)sx比服務(wù)sy好,即僅有一次preixpreiy,所以在線服務(wù)sy的占優(yōu)次數(shù)只有1次,在有n個用戶的情況下,服務(wù)sx的初始權(quán)重值是1/2n.而服務(wù)sy的初始權(quán)重值是2n-1/2n,所以在排序結(jié)果中服務(wù)sx的排序結(jié)果應(yīng)該比服務(wù)sy低.
非獨裁性表明有效的在線服務(wù)評價方法不會因為特定用戶評價偏好影響最終的評價結(jié)果.
存在任意的在線服務(wù)sx、sy并且排序結(jié)果為sxsy.若部分用戶將給予服務(wù)sx較服務(wù)評分提高,對服務(wù)sy評分保持不變,那么服務(wù)sx的排序結(jié)果不應(yīng)該變得比服務(wù)sy低,并且排序結(jié)果仍是sxsy.
證明:若果用戶持續(xù)給予服務(wù)sx高評分而保持服務(wù)sy評分不變,那么服務(wù)sx的占優(yōu)次數(shù)Wx只會增加而不會降低,所以服務(wù)sx的初始權(quán)重值會增加,迭代的結(jié)果就不會比增加前的結(jié)果差.若用戶持續(xù)給予服務(wù)sy低評分,那么服務(wù)sy的占優(yōu)次數(shù)Wy只會降低不會增加,所以服務(wù)sy的初始迭代權(quán)重只會降低不會增加,那么迭代結(jié)果就不會比之間的結(jié)果好,并且排序結(jié)果應(yīng)該是sxsy.
單調(diào)性表明在線服務(wù)的評分發(fā)生變化時,該服務(wù)的排序結(jié)果也應(yīng)該發(fā)生變化.若評分變高,那么排序結(jié)果應(yīng)該提升;若評分降低,那么排序結(jié)果應(yīng)該降低.
對兩個在線服務(wù)sx、sy,若所有用戶都認為服務(wù)sx比服務(wù)sy好,那么排序結(jié)果應(yīng)該為sxsy.若每位用戶都改變想法,即每位用戶都認為服務(wù)sx比服務(wù)sy差,那么最后的結(jié)果應(yīng)該為 sxsy.
證明:若所有用戶對在線服務(wù)sx、sy偏好由 sxsy變?yōu)閟xsy,那么服務(wù)sx,sy之間的占優(yōu)次數(shù)也就會發(fā)生反轉(zhuǎn),從而導(dǎo)致服務(wù)總的占優(yōu)次數(shù)也會發(fā)生反轉(zhuǎn),即通過占優(yōu)次數(shù)計算的排序結(jié)果由sxsy變?yōu)閟xsy.
反轉(zhuǎn)對稱性表示在線服務(wù)評價方法不會偏袒任何一個在線服務(wù),是公平性的體現(xiàn).
根據(jù)文中提到的利用Plackett-Luce模型的在線服務(wù)評價方法,設(shè)計了在以下實驗環(huán)境中進行驗證該方法的合理性和有效性:PC機,Windows 10系統(tǒng)、Core i3處理器、8GB內(nèi)存.我們采用了由GroupLens研究組發(fā)布的公共數(shù)據(jù)集MovieLens[25],其中該數(shù)據(jù)集包含1682部電影,943個用戶,以及100,000條左右的評分(1-5).
因為Avg和Sum方法是目前工業(yè)界和學(xué)術(shù)界應(yīng)用十分廣泛的在線服務(wù)評價方法,所以本文選擇這兩種方法進行對比.而Copeland方法是基于用戶服務(wù)評分矩陣,通過評分獲取用戶服務(wù)偏好關(guān)系,通過偏好關(guān)系獲取最終的評價結(jié)果.因為本文方法也是從偏好角度入手,所以選擇社會選擇函數(shù)Copeland方法作為本文中的對比方法.
本實驗中隨機選取20個服務(wù),將800為用戶對所有在線服務(wù)評價全都取反(即1分變?yōu)?分,2分變?yōu)?分,3分不變),然后分別計算取反前在線服務(wù)權(quán)重值與取反后的在線服務(wù)權(quán)重值,權(quán)重值數(shù)據(jù)如圖1所示.
圖1 反轉(zhuǎn)對稱性驗證Fig.1 Reverse symmetry verification
由圖1可見,本文方法在取反前排序權(quán)重值大的,取反后排序權(quán)重值變小,取反前排序權(quán)重值小的,取反后排序權(quán)重值變大,最終結(jié)果排序結(jié)果也反轉(zhuǎn)了.所以在取反后本文方法得到的評價名次會變成相反的,因此本文方法滿足反轉(zhuǎn)對稱性.
實驗比較記錄了本方法、Sum方法、Avg方法和Copeland方法得到的多數(shù)準則沖突的數(shù)量,實驗結(jié)果如圖2所示.
圖2 多數(shù)準則沖突Fig.2 Most criteria conflict
由圖2可見,由于孔多塞悖論[26]的存在,結(jié)果不可能達到100%.但是本文方法在不同數(shù)量在線服務(wù)中多數(shù)準則沖突的數(shù)量是最少的,遠低于Sum方法、Avg方法與Copeland方法中的多數(shù)準則沖突數(shù)量.
為模擬單調(diào)性實驗,分別選擇50個~500個用戶針對一個在線服務(wù)的評分進行修改,觀察修改后評價值變化情況.實驗結(jié)果圖3(a)、圖3(b)所示.
圖3 單調(diào)性驗證Fig.3 Monotonic verification
由圖3可知,改變在線服務(wù)的評分時,在線服務(wù)評價值也會相應(yīng)的發(fā)生變化.本文方法在評分降低時,最終排序結(jié)果也呈現(xiàn)降低趨勢;在評分變高時,排序結(jié)果也是呈現(xiàn)上升趨勢.因此本文方法滿足單調(diào)性.
隨機選取某在線服務(wù),通過增加高評分或低評分的數(shù)量來模擬操縱該服務(wù)評分,若果評價結(jié)果中,增加高或低評分數(shù)量對排序名次影響較小,則該方法得到的評價結(jié)果具有較好的抗操縱性.因此選擇用戶數(shù)量為300,對在線服務(wù)sx增加高評分或降低評分.分別對 10,20,30,40,50,60,70 位用戶的評分進行修改.改變這些用戶對在線服務(wù)的評分后排序名次如圖4(a)、圖4(b)所示.
圖4 抗操縱性驗證Fig.4 Anti-manipulation verification
根據(jù)圖4(a)所示,隨著高評分數(shù)量的增加,四種方法得到的評價結(jié)果都是呈現(xiàn)上升趨勢,但是本文方法得到的排序名次改變幅度比其他三種方法得到的結(jié)果小;反之從圖4(b)可知其他三種方法對于降低評分的影響也比本方法高.因此本方法更具抗操縱性.
為驗證本方法的效率,實驗選擇100~900個用戶和20~100個在線服務(wù)的環(huán)境進行模擬,記錄了系統(tǒng)在不同用戶數(shù)量和服務(wù)數(shù)量下的運行時間(單位:s),運行結(jié)果如圖5所示.
圖5 不同樣本規(guī)模下的運行時間Fig.5 Run time at different sample sizes
如圖5所示,在固定用戶數(shù)量下,運行時間雖然隨服務(wù)數(shù)量的增加而增加,但是時間增長并不是呈指數(shù)級;在固定服務(wù)數(shù)量下,隨著用戶數(shù)量的增加,運行時間增長也不是呈指數(shù)級增長,因此本方法具有較高的效率.
本文提出一種利用Plackett-Luce模型的在線服務(wù)評價方法,解決由于用戶評價準則不一致導(dǎo)致的在線服務(wù)評分不可比較的問題.方法通過Plackett-Luce模型把不可比較的評分轉(zhuǎn)化為可比較的用戶偏好,然后再把用戶偏好轉(zhuǎn)化為在線服務(wù)排序概率,通過概率對在線服務(wù)進行總體評價.理論分析及實驗驗證表明了該方法的有效性以及抗操縱性.但是本方法對在線服務(wù)評價時僅從單一的評分角度衡量在線服務(wù)的性能,不能充分合理地表現(xiàn)在線服務(wù)的真是性能.因此下一步的工作將從多屬性綜合考慮在線服務(wù)性能,力求讓在線服務(wù)評價結(jié)果更加準確.