基于Slater社會選擇理論的在線服務評價方法

朱明強,付曉東,1b,2,劉 驪,馮 勇,劉利軍

(1.昆明理工大學 a.信息工程與自動化學院; b.航空學院,昆明 650500;2.云南省計算機技術應用重點實驗室,昆明 650500)

0 概述

在線服務是指利用互聯網技術向用戶提供線上服務的方式。隨著現代互聯網技術的飛速發展,在線服務已經在電子商務、在線娛樂等領域得到廣泛應用。然而,互聯網的發展使得在線服務的種類和數量迅速增加,同時不同用戶對在線服務質量的要求也不盡相同,尤其是當用戶面對較多功能相似或者相同的在線服務時,難以做出正確的服務優劣決策[1]。用戶在選擇滿足自身偏好的在線服務時,由于服務的種類和數量非常多,因此不可能選用所有的服務,也不可能對所有的在線服務進行評價,從而導致評分數據的不完整性。此外,用戶根據自己的評價標準對服務進行評價,往往存在一些主觀因素,有的傾向給予高分評價,有的傾向給予低分評價,使得評價數據可信度降低。同時,某些服務提供者為了提高服務的影響力,可能向用戶提供不真實的信息,也可能出現互刷服務好評的情況。上述存在的問題使得用戶難以從大量服務中方便快捷地選擇適合的在線服務。因此,需要一種客觀的在線服務評價方法,通過該方法得到的在線服務評價結果,必須能夠保證對在線服務評價的真實性和可靠性。

在用戶使用在線服務的過程中,由于不同的用戶具有不同的消費心理、消費背景等,致使其偏好以及評價準則不一致,對同一個服務的評價可能出現矛盾和沖突[2-3]。由于不同用戶對服務進行評價時具有不一致的評價準則,即使對于同一服務的滿意度一致,對該服務進行評分時,評分值也可能不盡相同,從而導致無法對服務進行公正的優劣比較;另一方面,某些服務提供者為了提高自身的信譽,向用戶提供不真實的服務信息,更有甚者雇傭“用戶”對其所出售的在線服務給予較高的評分,從而達到操縱服務信譽的目的[4],給用戶決策帶來誤導,使其不能準確選擇適合自身偏好的在線服務。

本文提出一種基于Slater社會選擇理論的在線服務評價方法，利用Slater方法將不同用戶對服務的評分轉化為偏好矩陣，并形成以服務為節點、以優先關系為有向邊的有向圖，最終得到在線服務排序，解決用戶對服務評分不可比較的問題。

1 相關研究

1.1 基于評分的在線服務評價

文獻[5]指出,實際應用中研究者多數是通過平均值法與累加法計算獲取最終的評價值。均值法將用戶對服務的所有評分進行求和,然后除以該服務被評分的總次數,從而得到服務的平均評分,對該平均評分進行排序,并將其作為用戶對在線服務的評價優劣排序依據。累加法將用戶對服務的反饋評分進行分類并統計:當用戶評分為4、5時,表示好評總分加1分;當用戶評分為3時,表示中評得0分;當用戶評分為1、2,表示差評總分減1分,然后對總分進行累加并排序,其排序結果表示服務的優劣排序,并將其作為用戶對在線服務的評價優劣排序依據。然而,無論是累加法還是均值法,均未考慮到用戶的主觀偏好和評價準則不一致的問題,導致其評價結果不能很好地體現用戶的偏好需求。文獻[6]提出一種基于用戶對已購服務評論信息的服務評價方法,先根據評論信息對在線服務的特有屬性進行識別并加以鑒定,再根據每個服務的特有屬性對服務進行評分,并據此對在線服務進行排序。文獻[7]基于累加法提出一種改進方法,即加權累加法,通過該方法計算的結果更準確。文獻[8]提出了一種基于Copeland社會選擇函數的在線服務評價方法,該方法基于用戶對服務的評分,通過比較計算得出的服務評價值大小對在線服務進行排序。

1.2 基于服務屬性的在線服務評價

在基于服務屬性的在線服務評價研究中:文獻[9]綜合每個用戶的偏好和不同網站對服務各方面信息的描述對服務進行評價;文獻[10]基于服務的屬性對在線服務進行評價,包括銷量、評價、服務描述信息等屬性;文獻[11-12]將服務的價格、用戶對服務的評分、服務的銷量以及服務的質量等綜合后對在線服務進行綜合排序;文獻[13]提出一種基于改進熵權的評價方法,該方法將多維度屬性以主觀、客觀權重相結合,最終得到評價結果;文獻[14]提出一種基于服務特征的排序技術,先將用戶分為熟客和非熟客兩組,通過用戶的評論信息根據排序列表賦予不同的權重,通過計算得出加權評分表,并根據加權評分表對其進行排序,從而幫助用戶制定購買意向。

1.3 基于文本的在線服務評價

研究者對服務進行相應的評價并與其他用戶相互分享經驗,根據用戶的評論信息和業務策略對服務進行選擇,但并沒有考慮用戶之間的偏好具有相似性以及用戶對服務評價的真實性。文獻[12]通過預測每個用戶對服務評論的強度,將其聚合后作為評估服務排名的標準。該方法的優點在于用戶可以在不搜索所有評論的情況下快速找到想要獲得的評論,但只是針對較少用戶的評論,并不適合大規模用戶對服務的評論。文獻[15]提出一個基于客戶反饋計算準確評級的框架,將用戶的評論作為輸入條件,通過信息檢索刪除所有常用的詞,對評論中剩余的詞進行標注以及關鍵詞提取,通過概率計算對服務進行排名。

1.4 基于推薦系統的在線服務評價

推薦系統是一種個性化的推薦方法。文獻[16]提出一種局部最優服務選擇模型。該模型選擇服務中單個最優的服務并將其組合,然而這種服務組合的結果可能只是局部最優,并不一定是全局最優。文獻[17]提出一種服務推薦方法,首先對用戶已有評價信息進行分析,挖掘出不可靠的惡意評價信息,然后通過計算用戶的可信度刪除惡意評價用戶。該方法的不足之處在于需要在篩除惡意用戶之后,所推薦的服務才會更好地符合用戶的偏好需求,而由于在線服務的數量巨大,不可能篩除所有惡意用戶的評價信息。

1.5 基于信譽系統的在線服務評價

信譽系統是一種群體的推薦方法。文獻[18]指出現有信譽系統基本上都是以用戶的評價標準相同為前提,然而,現實中不同用戶的評價標準是不可能完全一致的,甚至對同一服務的評價也可能不同。文獻[19]提出一種基于聚類的信譽系統,根據評分的系數將用戶分為誠實與不誠實,并通過計算得到信譽值,其不足之處在于計算方法比較復雜,不易理解。上述研究多數未考慮不同的用戶具有不同的偏好以及不同的評價準則,導致用戶對服務之間的評分不可比較。針對該問題,本文選擇使用基于社會選擇理論[20]的思想加以解決,集結所有用戶對不同評價對象的評價關系形成群決策結果。本文提出一種基于Slater社會選擇理論的在線服務評價方法,在無需假設不同用戶偏好不一致和評價準則不一致的情況下,將用戶對服務的評分轉化為以服務為節點、以優先關系為有向邊的有向圖,最終得出在線服務的排序,實現在用戶偏好不一致和評價準則不一致情況下的服務排序。

2 基于Slater方法的在線服務評價

2.1 問題定義

本文對在線服務評價相關問題定義如下:

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

定義2用戶-服務評分矩陣R=[ri,j]m×n,其中,ri,j表示用戶ui對服務sj的評分。ri,j取值為1～5,表示用戶對服務的喜好程度,1表示非常不喜歡,2表示不喜歡,3表示一般,4表示喜歡,5表示非常喜歡。若ri,j==0,則表示用戶ui沒有對服務sj進行評分。

定義3ui表示第i個用戶,其對在線服務之間評價的偏好關系分為以下情況:若ri,j>ri,k,則sj?sk,其中sj?sk表示用戶ui認為服務sj優于服務sk,符號“?”表示優于;若ri,j=ri,k,則sj～sk,其中sj～sk表示用戶ui認為服務sj和服務sk不分優劣;若ri,j

本文對在線服務評價的總體思想是:在用戶偏好以及評價準則不一致的情況下,根據用戶對在線服務的評分,首先對稀疏的用戶-服務矩陣進行填充,然后構建以服務為節點、以優先關系為有向邊的有向圖,最后通過Slater方法[21]得到在線服務評價結果。

2.2 偏好關系獲取

為對在線服務進行評價,需要獲取每個用戶對在線服務的評分。由于在線服務的種類和數量非常多,用戶不可能選用所有的服務,也不可能對所有的在線服務進行評價,從而導致評分數據的不完整性,造成用戶-服務評分矩陣較為稀疏[22]。由于本文是基于用戶對服務的兩兩比較,因此需要對稀疏的用戶-服務矩陣進行填充。目前協同過濾[23]是一種常用的推薦方法,該方法通過尋找與自己偏好最相似的用戶進行推薦,本文采用協同過濾算法對不完整的用戶-服務評分矩陣進行填充。

定義4基于填充完整的用戶-服務矩陣R,統計用戶ui∈U(i=1,2,…,m)對在線服務sp,sq∈S(p,q=1,2,…,n,p≠q)的偏好關系,構建每一個用戶的偏好關系矩陣,用ZHi=[zhpq(i)]n×n(p,q=1,2,…,n,p≠q)表示,zhpq(i)取值如式(1)所示。

(1)

其中:1表示用戶ui認為服務sp優于sq服務;0表示用戶ui認為服務sp和服務sq具有同等效用;-1表示用戶ui認為服務sq優于服務sp。

根據每個用戶的偏好矩陣ZHi統計出m個用戶中zhpq(i)=1和zhqp(i)=-1的用戶數進行比較,如式(2)所示。

(2)

2.3 在線服務群體評價排序

為更明確地闡述本文提出的利用Slater社會選擇理論對在線服務進行評價,給出相關定義如下:

定義5根據用戶-服務矩陣得到服務-服務矩陣TU=[tupq]n×n(p,q=1,2,…,n,p≠q),任取2個服務對sp1,q1,sp2,q2∈sp,q,并且tup1,q1>0,tup2,q2>0。然后根據tup1,q1、tup2,q2進行排序,并建立服務優先對Lpq,如式(3)所示。

(3)

其中:tup1,q1-tup2,q2>0,表示在服務優先對Lpq中服務對sp1,q1排在服務對sp2,q2之前;tup1,q1-tup2,q2=0,表示在服務優先對Lpq中服務對sp1,q1和服務對sp2,q2不分前后;tup1,q1-tup2,q2<0,表示在服務優先對Lpq中服務對sp2,q2排在服務對sp1,q1之前。

定義6(有向圖)G=為有向圖,其中:V表示以服務為節點的集合,V={s1,s2,…,sn};E表示以(sp,sq)為有向邊的集合,E=(sp,sq)(p,q=1,2,…,n,p≠q)。

根據得到的服務優先對Lpq,將Lpq中的優先關系視為有向圖中邊的指向關系,如Lpq:(sp,sq)表示在有向圖中有從sp指向sq的有向邊。遍歷服務優先對Lpq,得到Lpq中所有的節點和有向邊,將Lpq中的每條有向邊以及節點依次添加到圖中,最終構造以服務為節點、以優先關系為有向邊的有向圖。

定義7(相似集) 在有向圖G=中,若有子集Sim?C(其中集合C指的是有向圖中所有節點的集合)由相似的節點集合組成,如果存在節點s1,s2∈Sim,對于任何節點有c∈C-Sim,有s1→c(表示節點s1到節點c存在有向邊),當且僅當s2→c,則集合Sim是一個相似集。2個相似候選集的交集仍然是相似候選集。

定義8(前集) 在有向圖G=中,對于任意節點f∈F都存在f→s的有向邊,其中對于任意的s∈Sim,集合F中的任意節點到相似集Sim中的每一個節點都存在有向邊,記集合F為前集。

定義9(后集) 在有向圖G=中,對于任意節點l∈L,都存在s→L的有向邊,其中對于任意的s∈Sim,相似集Sim中的任意一個節點到集合L中的每一個節點都存在有向邊,記集合L為后集。

2.4 具體示例

例1假設有5個用戶對5個在線服務進行評分,如表1所示,其中,小數為利用協同過濾算法填充后的評分值,根據定義1～定義6構造的有向圖如圖1所示。

表1 用戶對在線服務的評分

圖1 有向圖G

在有向圖G中,s1到s2、s3、s5存在邊:s1→s2,s1→s3,s1→s5,s2、s3、s5到s4存在邊:s2→s4,s3→s4,s4→s5。根據定義7,可以得出{s2,s3,s4}是相似集,即Sim={s2,s3,s4}。又因為在有向圖中存在邊s3→s2,s3→s4,s2→s4,所以s3?s2?s4。

根據定義8中前集的定義,從圖1中可以得到s1→s2,s1→s3,s1→s5,s2,s3,s5到s4的邊分別s2→s4,s3→s4,s4→s5,由此可以得出{s1}是前集,即前集F={s1}。

根據定義9中后集的定義,從圖1中可以得到相似集中的s2、s3、s5到s4存在邊:s2→s4,s3→s4,s4→s5,可以得出{s5}是后集,即后集L={s5}。

遍歷有向圖G,根據相似集、前集、后集的定義,分別找到相似集、前集、后集,并根據3個集合之間以及內部節點有向邊的指向關系,判斷有向圖中所有節點的指向關系,從而得出所有節點的排序,節點的排序也即是服務的排序,將節點的排序轉化為服務的排序,最終得出在線服務的排序。因此,在圖1中最終排序結果為:s1?s3?s2?s4?s5,轉化為服務的評價結果:s1?s3?s2?s4?s5,因此,最優服務為s1,最劣服務為s5。

定義10在線服務偏好序列O=(sk|k=1,2,…,m),其中,sk表示第k個在線服務在所有用戶偏好序列中的排序,則第k個服務的評價值為Wk=n-k+1,其中n表示在線服務的總數量。

服務的評價值越大,表示該服務在整體排序中名次越靠前。O=(s1,s4,s2,s3)表示服務的排序為s1?s4?s2?s3,其中,s1為最優服務,s3為最劣服務,服務s1的評價值W1=4-1+1=4。

3 在線服務評價理論分析

3.1 孔多塞性

如果存在服務sp,有一半以上的用戶認為服務sp優于其他服務,則服務sp是孔多塞候選服務。

3.2 單調性

對于任意不同的服務sp和sq,有sp?sq。如果某個用戶對服務sp給予較高評分而對服務sq的評分不變,則服務sp在總體服務排序中其排名應提高或者不變;如果某個用戶對服務sp評分保持不變且對服務sq給予較低評分,則服務sq的總體排名不應該降低,并且最終結果仍為sp?sq。

3.3 反對稱性

對于服務sp和sq,如果每個用戶都認為服務sp優于sq服務,則最終排序結果為sp?sq。當每個用戶都作出相反偏好選擇時,也即是每個用戶都認為服務sq優于sp服務時,則最終服務排序結果為sq?sp。

證明:若每個用戶對服務sp、sq的偏好由sp優于sq變為sq優于sp,則有tupq

3.4 抗操縱性

對于任意服務sp的評分提高或者降低時,最終的服務排序結果保持不變。

4 實驗結果與分析

本文采用具有真實評分數據的電影數據集MovieLens進行實驗。該數據集包含943名用戶以及1 682部電影,共有10萬條左右用戶對電影的評分。實驗環境為:64位Windows7操作系統,Intel Core i5 CPU,8 GB內存,開發語言是Matlab 2016a。

為驗證本文方法所得在線服務評價結果的可靠性,以3種在線服務評價方法,即累加(Sum)法[5]、均值(Average)法[5]和Copeland法[8]作為主要對比方法,對孔多塞性、單調性、反對稱性、抗操縱性、多數準則沖突以及時間性能進行驗證,實驗中將本文方法稱為Slater法。

4.1 孔多塞性實驗

如果Slater法得到的最優服務與孔多塞候選服務一致,則表明該方法滿足孔多塞性。本文實驗中選取943名用戶對52個服務的評分作為基礎。根據所有用戶對服務的評分,可得服務8(即s8)有一半以上的用戶認為其優于其他任意一個服務,因此,s8為孔多塞服務。Slater法、Average法、Sum法、Copeland法得到的評價結果如圖2～圖5所示。通過對比可知,Average法和Sum法得到的最優服務均是s18,因此,Average法和Sum法不滿足孔多塞性,而Copeland法和Slater法得到的最優服務均是s8,滿足孔多塞性。

圖2 Slater法評價結果

圖3 Average法評價結果

圖4 Sum法評價結果

圖5 Copeland法評價結果

4.2 單調性實驗

為驗證Slater法的單調性,任選一個在線服務,分別提高、降低用戶對其評分值,判斷該服務在總體排序中的位置是否有所變化,如果提高評分值該服務的排序位置提高或者不變,而且降低評分值該服務的排序位置降低或者不變,則Slater法得到的評價結果符合單調性。本文實驗隨機選擇2個在線服務,并且選取100個～900個用戶分別增加和減少對上述2個服務的評分,實驗結果如圖6和圖7所示。

圖6 提高評分的評價結果

圖7 降低評分的評價結果

由圖6可以看出,當提高用戶對在線服務的評分時,Slater法得到的該服務的評價值增大,表明該服務在總體服務排序中排名提高。由圖7可以看出,當降低用戶對在線服務的評分時,Slater法得到的該服務的評價值減小,表明該服務在總體服務排序中排名逐漸靠后。由此表明,Slater法得到的評價結果滿足單調性。

4.3 反對稱性實驗

為驗證Slater法得到的評價結果滿足反對稱性,任取某個用戶對2個在線服務的評分給予相反選擇,若通過Slater法得到的評價結果排序也相反,則該方法滿足反對稱性。本文實驗將用戶對服務的評分全部取反,并分別用Slater法得出評分取反前與評分取反后的評價值,如圖8所示?？梢钥闯?當用戶對服務的評分取反后,Slater法得到的評價結果也作相反選擇,且取反前與取反后的評價值關于評價值26對稱。由此表明,Slater法得到的評價結果滿足反對稱性。

圖8 反對稱性驗證結果

4.4 抗操縱性實驗

為驗證Slater法的抗操縱性,隨機選取某個在線服務:1)增加對該服務給予較高評分的不誠實用戶;2)增加對該服務給予較低評分的不誠實用戶,如果得到的最終排序結果與增加不誠實用戶前的排序結果一致,則Slater法得到的評價結果具有抗操縱性。4種方法得到的評價值如圖9和圖10所示。可以看出,Slater法得到的評價值并沒有隨著不誠實用戶數的增加而變大,也沒有隨著用戶對服務評分的降低而變小,即服務排名基本不受影響,相比之下,Average法、Sum法、Copeland法得到的評價值則變化較大,即該服務排名受到較大的影響。由此表明,Slater法得到的在線服務評價結果具有較強的抗操縱性,不會因為部分不法用戶對服務的評分而影響最終的服務評價結果。

圖9 將用戶評分提升至4分的評價結果

圖10 將用戶評分降低至2分的評價結果

4.5 多數準則沖突實驗

多數準則是指對于任意2個不同的在線服務sp、sq,如果認為服務sp優于服務sq的用戶數量多于認為服務sq優于sp服務的用戶數量,則sp?sq。那么根據多數準則沖突,把認為服務sq優于服務sp的用戶數量稱為多數準則沖突數量。本文保持服務的數量固定不變,采用5組不同用戶數量的數據集進行實驗,統計出Slater法、Sum法、Average法、Copeland法各自滿足多數準則沖突的比例,如圖11所示。可以看出,Slater法滿足多數準則沖突的比例遠低于Average法、Sum法和Copeland法,即表明該方法得到的評價結果更好地滿足多數準則,能夠符合較多用戶的偏好需求。

圖11 多數準則沖突實驗結果

4.6 運行時間

設定服務的數量固定,依次增加用戶的數量,比較Slater法、Sum法、Average法、Copeland法每次排序后的系統運行時間,如圖12所示。可以看出,隨著用戶數量的增加,系統計算用戶評價的次數增加,導致運行時間逐漸增加。然而Slater法運行時間并沒有隨著用戶數量成倍增加,因此該方法效率較高。此外還可以看出,相比于Sum法、Average法、Copeland法,雖然Slater法運行時間較長,但是對其進行操縱比Sum法、Average法、Copeland法需要更長的時間,因此,Slater法得到的評價結果其抗操縱難度比Sum法、Average法、Copeland法更高。

圖12 運行時間比較

5 結束語

本文基于社會選擇理論的基本思想,利用Slater法對在線服務進行評價,解決因用戶偏好和評價準則不一致導致的在線服務評分不可比較的問題。該方法將不可比較的評分轉化為用戶對不同服務的個人偏好矩陣,利用Slater法得到在線服務的評價結果。理論分析和實驗比較結果表明,本文方法得到的在線服務評價結果滿足孔多塞性、單調性、反對稱性和抗操縱性,驗證了其對在線服務評價的有效性。由于Slater問題是NP-hard問題,隨著在線服務數量的增加,Slater法計算在線服務評價的難度將有所增加,因此下一步將對本文方法進行優化,提高算法效率并降低系統消耗。