利用Plackett-Luce模型的在線服務評價方法

張繼康，付曉東，2，岳 昆，劉 驪，劉利軍(昆明理工大學信息工程與自動化學院云南省計算機技術應用重點實驗室，昆明650500)

2(昆明理工大學航空學院，昆明650500)

3(云南大學信息學院，昆明650091)

E-mail:xiaodong_fu@hotmail.com

1 引言

在線服務是指利用互聯網技術，向用戶提供線上服務的方式.現如今互聯網上存在大量功能相似或者相同的在線服務［1］.用戶在挑選服務時如何在大量的在線服務中快速準確選擇到需要的服務是一個越來越嚴重的問題.另外，不法商家為了提高自己服務被選擇的幾率，會惡意修改用戶給與的在線服務的評價，導致評價結果無法正確反應在線服務的性能，誘導用戶做出錯誤選擇［2］.以上行為導致用戶對互聯網中的在線服務無法進行有效的篩選.因此，通過給服務排名的方式向用戶提供在線服務成為了如今在線服務評價的主要手段［3］.服務排名是把在線服務各項性能量化，最后整體得到在線服務評價結果的方法.用戶在面對眾多在線服務時，會根據排序名次挑選滿足需求的服務.所以使用在線服務評價方法可以幫助用戶在互聯網中快速準確的找到滿足需求的在線服務.

累加法、平均值法、構圖法等方法是目前工業界和學術界常用的在線服務評價方法［4］.這些方法為了方便計算，通常對在線服務進行評價時都假設用戶具有相同的評價準則［5］.然而受用戶主觀心理因素和消費偏好的影響，用戶群體很難具有相似的評價準則，所以用戶服務評分無法客觀的的反應服務質量［6，7］.這種情況下，即使性能相同的服務也可能會得到不同的評分.因此現有方法得到的評價結果會對用戶選擇起到誘導作用，做出不正確的選擇.此外，互聯網中還存在惡意修改或大批量增加在線服務的評分數據，來提高在線服務排序名次的行為，導致用戶根據排序名次進行服務選擇時會產生有利于自己的結果［8］.

為解決上述問題，本文提出了一種利用Plackett-Luce模型［9，1https://www.amazon.cn/0］的在線服務評價方法，方法基于用戶評價準則不一致的情況，根據用戶對不同的在線服務的評分獲取用戶對服務可比較的偏好關系［11］，根據在線服務間可比較的偏好關系進而得到在線服務評價結果.

2 相關工作

近年來，根據用戶評價信息判斷服務之間優劣關系的研究工作已經成為熱點.文獻［12］的研究提出基于服務屬性的在線服務評價方法，例如價格、銷量、信譽、評分等等.文獻［13https://www.ebay.cn/-15］指出可以基于在線服務特征對在線服務進行評價，從大量評論信息中使用自然語言處理技術抽取服務描述信息對服務進行評價，得到最終評價結果.文獻［16］指出目前工業界大部分是通過累加法與平均值法計算獲取最終的評價值.平均值法是將所有用戶對某個在線服務的評分進行累加得到一個總的服務評分，然后除以用戶數量，將所得到的結果作為該服務的評價結果，目前Amazon1https://www.amazon.cn/和天貓2https://www.tmall.com/是使用平均值法作為網站內部的評價方法.累加法將用戶對服務的評分進行分類并統計:當用戶評分為4、5時，表示好評，即總分+1分;當用戶評分為3時，表示中評，即得0分;當用戶評分為1、2，表示為差評，即總分-1分.然后對總分進行累加，將所得到的結果作為該服務的評價結果，目前eBay3https://www.ebay.cn/和淘寶4https://www.taobao.com/是使用累加法作為網站內部的評價方法.但是每位用戶對在線服務的評價準則和偏好只需要滿足自己的需求，很難在用戶群體中出現一致的偏好.因此，以上研究提出的在線服務評價方法涉及到用戶反饋信息實質是不可比較的，通過這些方法得到的在線服務評價結果很難反應在線服務的真是性能.

文獻［17］的研究是根據用戶的多維度屬性評價對服務的信任進行綜合評價，進而得到個性化的評價結果.文獻［18］提出了一種改進熵權的在線服務評價方法，對于多維度屬性以主客觀權重相結合的方法得到最終的評價結果.上述研究雖然都考慮到用戶對在線服務評價準則不同的問題，但是還是根據用戶服務評分直接計算得到最終評價結果，沒有解決評分不可比較問題.文獻［19］考慮從用戶服務偏好入手解決該問題，構建加權有向圖并計算最強路徑得到最終的評價結果.文獻［20］的研究基于偏好不一致的思路，以社會選擇函數［21］為基礎提出基于Copeland社會選擇理論的在線服務評價方法，構建有向無環偏好圖獲取在線服務評價結果.上述研究雖然考慮到了用戶偏好不一致的問題，但是提出的解決辦法運行時間較長，整體效率較低.

考慮到以上研究中存在的不足，在用戶評價準則不一致情況下，本文在不假設用戶偏好一致的情況下，首先以用戶對服務的評分為基礎，將用戶對不同在線服務的評分轉換成用戶服務可比較的偏好關系，通過可比較的偏好關系獲取每個服務的占優次數;其次利用Plackett-Luce模型，將占優次數轉換為概率;最后通過概率求解得出在線服務評價結果.

3 存在問題

3.1 問題定義

定義1.定義 U={u1，u2，…，um}為用戶集合，定義 S={s1，s2，…，sn}為在線服務集合.其中，m 表示用戶人數，n表示在線服務數量.

定義 2.定義 R=［rij］m×n(i=1，2，…，m;j=1，2，3，…，n)為用戶-服務評分矩陣;其中，rij表示第i位用戶ui對第j個在線服務sj的評分，若存在rij=0，則表示用戶ui未對在線服務sj進行評分.

定義3.在線服務評價結果 P={p1，p2，…，pn}，其中 pn表示第n個服務的評價值.若px＞py，則表示服務sx優于服務sy.

顯然，一種有效的在線服務評價方法應當滿足以下準則:

1)反轉對稱性:對不同在線服務 sx、sy(1≤x，y≤n且 x≠y)，若所有用戶都認為服務sx比服務sy好，則最終結果為 sxsy.若每位用戶改變想法，即每位用戶都認為服務sy比服務sx好，則最終結果為 sxsy.

2)單調性:若有服務排序sxsy，則提高用戶對服務sx的評分，則結果仍是sxsy;

3)非獨裁性:若用戶群體中只有一個用戶認為sx比服務sy好，而其他所有用戶認為sy比服務sx好，則最終結果結果不可能是sxsy;

4)抗操縱性:若存在服務排序sxsy，那么增加給予服務sy高評分的用戶，則結果仍是sxsy;

3.2 舉例說明

例1.假設有3個用戶共同對4個在線服務進行評分，評分矩陣如表1所示.

表1 用戶-服務評分表Table 1 User-service score sheet

根據表1的數據，利用eBay網站使用的累加法(Sum)和Amazon網站使用的平均值法(Avg)的得到評價值如表2所示.

由表1可見，每位用戶給出的評價值是個人效用，無法和其他用戶的評價比較.無法說明服務s1給用戶u3的表現比服務s3給用戶u1的表現更好.所以用戶服務評分無法去直接計算，且運用服務評分直接計算得到的在線服務評價結果無法反映在線服務的真是性能.

此外，如果將用戶u1對服務s2的評分提高至5分，這個操作會提升服務s2的評價值.但對其他服務的評價結果沒有影響，這將導致服務s2的評價結果大大提升，所以上述方法抗操縱性較弱.因此，本文提出一種利用Plackett-Luce模型的在線服務評價方法，從服務偏好和服務占優次數的角度解決了在線服務評分不可比較的問題，同時提高了評價方法的抗操縱性.

表2 評價值表Table 2 Evaluation value table

4 利用Plackett-Luce模型的在線服務評價

Plackett-Luce模型是一個排序概率模型，描述模型內部參數排序的概率［22，23］.對內部參數進行排序時，Plackett-Luce模型把排序過程分成許多個階段且每個階段互不影響，并在每個階段選出一個最優服務.在當前階段中，計算所有服務排序名次為第一的概率，把排序概率值最高的服務作為當前階段的最優服務，重復這個過程直到所有階段結束，得到服務的排序結果.

基于以上分析，本文將每位用戶對不同服務的評分計算獲取該用戶對所有服務的偏好關系，然后通過偏好關系，得到每個服務的占優次數.通過占優次數解決了用戶評分準則不一致導致的不同用戶對同一服務的評分不可比較的問題.最后根據Plackett-Luce模型對數似然函數的迭代函數從概率的角度推斷得到每個服務在整體服務中排序的概率，把排序權重轉化的概率后作為評價結果向用戶展示.

4.1 服務偏好獲取

定義 4.用戶-服務偏好關系矩陣 Pre=［preij］m×n(i=1，2，3，…，m;j=1，2，3，…，n).其中，preij表示第 i位用戶 ui對第j個在線服務sj的偏好值.其中preij的計算公式如下所示:

對于同一用戶，服務評分是可以比較的.所以計算用戶-服務評分得到每位用戶關于每個服務的偏好值pre，填入偏好矩陣Pre.在相同的情況下pre值大的服務被用戶選擇的概率更大.

算法1.根據用戶服務評分矩陣R得到用戶服務偏好矩陣Pre.

輸入:用戶服務評分矩陣R

輸出:用戶服務偏好矩陣Pre

算法1根據用戶服務評分矩陣R得到用戶服務偏好矩陣Pre，根據矩陣Pre中每位用戶對每個服務的偏好關系確定服務的占優次數.

定義5.ui是一個用戶，其評價的在線服務之間的偏好關系:若 preix＞preiy，則偏好關系為 sxsy;若 preix=preiy，則偏好關系為 sx～sy;若 preix＜preiy，則偏好關系為 sxsy.其中sxsy表示用戶ui認為服務sx優于服務sy;sx～sy表示用戶ui認為服務sx和服務sy無差別;sxsy表示用戶ui認為服務sy優于服務sx.

定義 6.服務占優次數矩陣 T=［tij］m×n(i=1，2，3，…，m;j=1，2，3，…，n)，其中 tij表示服務 sj在用戶 ui偏好下的占優次數.

根據定義6，若在用戶ui偏好下將服務sx和服務sy進行比較，那么服務sx的占優次數tix計算方式如下所示:

服務占優次數矩陣T是將m個用戶評價的n個在線服務根據偏好值pre進行統計，若pre值大則記為占優1次.在每位用戶的偏好下，每個服務都要和其他所有服務進行偏好值比較，統計每個服務的占優次數.

算法2.根據用戶服務偏好矩陣Pre得到服務占優次數矩陣T.

輸入:用戶服務偏好矩陣Pre

輸出:服務占優次數矩陣T

算法2根據用戶偏好矩陣Pre構建服務占優次數矩陣T.在得到矩陣T后根據矩陣中每位用戶偏好下每個服務的占優次數tij得到每個服務在所有用戶偏好下總的占優次數.

定義7.用W表示服務在所有用戶偏好下總的占優次數，W={W1，W2，W3，…，Wn}.其中 W 計算公式如下所示:

累加每個服務在所有用戶偏好下的占優次數t，得到每個服務在所有用戶偏好下總的占優次數W.根據得到的服務總的占優次數W，從概率的角度推斷求解每個在線服務的評價結果.

4.2 服務排序獲取

通過Plackett-Luce模型的對數似然函數(γ)構建關于權重值的迭代函數Q(γ)，找到使對數似然函數(γ)取得最大值時的權重值γ的值.把權重值轉化的概率，通過服務概率值大小對在線服務進行排序.

由于對數似然函數(γ)無法直接求解得到最大值，所以需要通過迭代的方式求解使得對數似然函數(γ)取得最大值的γ的值.

定義8.迭代函數Q(γx)如下所示:

Nxy表示服務sx和服務sy的總占優次數之和.

|≤ε，則認為當前得到的結果 接近最優的權重

x

定義10.服務的排序權重值 γ ={γ1，γ2，γ3，…，γn}，在Plackett-Luce模型中，服務sx的排序概率求解如下所示:

5 理論分析

5.1 孔多塞性［24］

在用戶群體中，若服務sx與服務sy比較時有超過一半的用戶認為服務sx比服務sy好，則sx稱為孔多塞候選服務.

證明:有超過一半的用戶認為sx優于sy，則Wx大于Wy，即服務sx的初始權重值比服務sy的初始權重值大，所以服務sx的評價結果不會比sy差.因此本方法滿足孔多塞性.

孔多塞性表明最終排序結果滿足用戶群體中多數人的偏好.評價結果中孔多塞候選服務越多，那么評價結果就越滿足多數人的偏好.

5.2 非獨裁性［24］

將兩個在線服務sxsy進行比較，若用戶群體中僅有一位用戶認為服務sx優于sy，其余所有用戶都認為服務sy比服務sx好，那么最終排序結果服務sx的排序名次不會比服務sy高.

證明:僅有一位用戶ui認為服務sx比服務sy好，即僅有一次preixpreiy，所以在線服務sy的占優次數只有1次，在有n個用戶的情況下，服務sx的初始權重值是1/2n.而服務sy的初始權重值是2n－1/2n，所以在排序結果中服務sx的排序結果應該比服務sy低.

非獨裁性表明有效的在線服務評價方法不會因為特定用戶評價偏好影響最終的評價結果.

5.3 單調性［24］

存在任意的在線服務sx、sy并且排序結果為sxsy.若部分用戶將給予服務sx較服務評分提高，對服務sy評分保持不變，那么服務sx的排序結果不應該變得比服務sy低，并且排序結果仍是sxsy.

證明:若果用戶持續給予服務sx高評分而保持服務sy評分不變，那么服務sx的占優次數Wx只會增加而不會降低，所以服務sx的初始權重值會增加，迭代的結果就不會比增加前的結果差.若用戶持續給予服務sy低評分，那么服務sy的占優次數Wy只會降低不會增加，所以服務sy的初始迭代權重只會降低不會增加，那么迭代結果就不會比之間的結果好，并且排序結果應該是sxsy.

單調性表明在線服務的評分發生變化時，該服務的排序結果也應該發生變化.若評分變高，那么排序結果應該提升;若評分降低，那么排序結果應該降低.

5.4 反轉對稱性［24］

對兩個在線服務sx、sy，若所有用戶都認為服務sx比服務sy好，那么排序結果應該為sxsy.若每位用戶都改變想法，即每位用戶都認為服務sx比服務sy差，那么最后的結果應該為 sxsy.

證明:若所有用戶對在線服務sx、sy偏好由 sxsy變為sxsy，那么服務sx，sy之間的占優次數也就會發生反轉，從而導致服務總的占優次數也會發生反轉，即通過占優次數計算的排序結果由sxsy變為sxsy.

反轉對稱性表示在線服務評價方法不會偏袒任何一個在線服務，是公平性的體現.

6 實驗結果及分析

根據文中提到的利用Plackett-Luce模型的在線服務評價方法，設計了在以下實驗環境中進行驗證該方法的合理性和有效性:PC機，Windows 10系統、Core i3處理器、8GB內存.我們采用了由GroupLens研究組發布的公共數據集MovieLens［25］，其中該數據集包含1682部電影，943個用戶，以及100，000條左右的評分(1-5).

因為Avg和Sum方法是目前工業界和學術界應用十分廣泛的在線服務評價方法，所以本文選擇這兩種方法進行對比.而Copeland方法是基于用戶服務評分矩陣，通過評分獲取用戶服務偏好關系，通過偏好關系獲取最終的評價結果.因為本文方法也是從偏好角度入手，所以選擇社會選擇函數Copeland方法作為本文中的對比方法.

6.1 反轉對稱性實驗

本實驗中隨機選取20個服務，將800為用戶對所有在線服務評價全都取反(即1分變為5分，2分變為4分，3分不變)，然后分別計算取反前在線服務權重值與取反后的在線服務權重值，權重值數據如圖1所示.

圖1 反轉對稱性驗證Fig.1 Reverse symmetry verification

由圖1可見，本文方法在取反前排序權重值大的，取反后排序權重值變小，取反前排序權重值小的，取反后排序權重值變大，最終結果排序結果也反轉了.所以在取反后本文方法得到的評價名次會變成相反的，因此本文方法滿足反轉對稱性.

6.2 多數準則沖突實驗

實驗比較記錄了本方法、Sum方法、Avg方法和Copeland方法得到的多數準則沖突的數量，實驗結果如圖2所示.

圖2 多數準則沖突Fig.2 Most criteria conflict

由圖2可見，由于孔多塞悖論［26］的存在，結果不可能達到100%.但是本文方法在不同數量在線服務中多數準則沖突的數量是最少的，遠低于Sum方法、Avg方法與Copeland方法中的多數準則沖突數量.

6.3 單調性實驗

為模擬單調性實驗，分別選擇50個～500個用戶針對一個在線服務的評分進行修改，觀察修改后評價值變化情況.實驗結果圖3(a)、圖3(b)所示.

圖3 單調性驗證Fig.3 Monotonic verification

由圖3可知，改變在線服務的評分時，在線服務評價值也會相應的發生變化.本文方法在評分降低時，最終排序結果也呈現降低趨勢;在評分變高時，排序結果也是呈現上升趨勢.因此本文方法滿足單調性.

6.4 抗操縱性實驗

隨機選取某在線服務，通過增加高評分或低評分的數量來模擬操縱該服務評分，若果評價結果中，增加高或低評分數量對排序名次影響較小，則該方法得到的評價結果具有較好的抗操縱性.因此選擇用戶數量為300，對在線服務sx增加高評分或降低評分.分別對 10，20，30，40，50，60，70 位用戶的評分進行修改.改變這些用戶對在線服務的評分后排序名次如圖4(a)、圖4(b)所示.

圖4 抗操縱性驗證Fig.4 Anti-manipulation verification

根據圖4(a)所示，隨著高評分數量的增加，四種方法得到的評價結果都是呈現上升趨勢，但是本文方法得到的排序名次改變幅度比其他三種方法得到的結果小;反之從圖4(b)可知其他三種方法對于降低評分的影響也比本方法高.因此本方法更具抗操縱性.

6.5 性能實驗

為驗證本方法的效率，實驗選擇100～900個用戶和20～100個在線服務的環境進行模擬，記錄了系統在不同用戶數量和服務數量下的運行時間(單位:s)，運行結果如圖5所示.

圖5 不同樣本規模下的運行時間Fig.5 Run time at different sample sizes

如圖5所示，在固定用戶數量下，運行時間雖然隨服務數量的增加而增加，但是時間增長并不是呈指數級;在固定服務數量下，隨著用戶數量的增加，運行時間增長也不是呈指數級增長，因此本方法具有較高的效率.

7 結語

本文提出一種利用Plackett-Luce模型的在線服務評價方法，解決由于用戶評價準則不一致導致的在線服務評分不可比較的問題.方法通過Plackett-Luce模型把不可比較的評分轉化為可比較的用戶偏好，然后再把用戶偏好轉化為在線服務排序概率，通過概率對在線服務進行總體評價.理論分析及實驗驗證表明了該方法的有效性以及抗操縱性.但是本方法對在線服務評價時僅從單一的評分角度衡量在線服務的性能，不能充分合理地表現在線服務的真是性能.因此下一步的工作將從多屬性綜合考慮在線服務性能，力求讓在線服務評價結果更加準確.