基于Slater社會(huì)選擇理論的在線服務(wù)評(píng)價(jià)方法

朱明強(qiáng),付曉東,1b,2,劉 驪,馮 勇,劉利軍

(1.昆明理工大學(xué) a.信息工程與自動(dòng)化學(xué)院; b.航空學(xué)院,昆明 650500;2.云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室,昆明 650500)

0 概述

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

在用戶使用在線服務(wù)的過(guò)程中,由于不同的用戶具有不同的消費(fèi)心理、消費(fèi)背景等,致使其偏好以及評(píng)價(jià)準(zhǔn)則不一致,對(duì)同一個(gè)服務(wù)的評(píng)價(jià)可能出現(xiàn)矛盾和沖突[2-3]。由于不同用戶對(duì)服務(wù)進(jìn)行評(píng)價(jià)時(shí)具有不一致的評(píng)價(jià)準(zhǔn)則,即使對(duì)于同一服務(wù)的滿意度一致,對(duì)該服務(wù)進(jìn)行評(píng)分時(shí),評(píng)分值也可能不盡相同,從而導(dǎo)致無(wú)法對(duì)服務(wù)進(jìn)行公正的優(yōu)劣比較;另一方面,某些服務(wù)提供者為了提高自身的信譽(yù),向用戶提供不真實(shí)的服務(wù)信息,更有甚者雇傭“用戶”對(duì)其所出售的在線服務(wù)給予較高的評(píng)分,從而達(dá)到操縱服務(wù)信譽(yù)的目的[4],給用戶決策帶來(lái)誤導(dǎo),使其不能準(zhǔn)確選擇適合自身偏好的在線服務(wù)。

本文提出一種基于Slater社會(huì)選擇理論的在線服務(wù)評(píng)價(jià)方法，利用Slater方法將不同用戶對(duì)服務(wù)的評(píng)分轉(zhuǎn)化為偏好矩陣，并形成以服務(wù)為節(jié)點(diǎn)、以優(yōu)先關(guān)系為有向邊的有向圖，最終得到在線服務(wù)排序，解決用戶對(duì)服務(wù)評(píng)分不可比較的問(wèn)題。

1 相關(guān)研究

1.1 基于評(píng)分的在線服務(wù)評(píng)價(jià)

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

1.2 基于服務(wù)屬性的在線服務(wù)評(píng)價(jià)

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

1.3 基于文本的在線服務(wù)評(píng)價(jià)

研究者對(duì)服務(wù)進(jìn)行相應(yīng)的評(píng)價(jià)并與其他用戶相互分享經(jīng)驗(yàn),根據(jù)用戶的評(píng)論信息和業(yè)務(wù)策略對(duì)服務(wù)進(jìn)行選擇,但并沒(méi)有考慮用戶之間的偏好具有相似性以及用戶對(duì)服務(wù)評(píng)價(jià)的真實(shí)性。文獻(xiàn)[12]通過(guò)預(yù)測(cè)每個(gè)用戶對(duì)服務(wù)評(píng)論的強(qiáng)度,將其聚合后作為評(píng)估服務(wù)排名的標(biāo)準(zhǔn)。該方法的優(yōu)點(diǎn)在于用戶可以在不搜索所有評(píng)論的情況下快速找到想要獲得的評(píng)論,但只是針對(duì)較少用戶的評(píng)論,并不適合大規(guī)模用戶對(duì)服務(wù)的評(píng)論。文獻(xiàn)[15]提出一個(gè)基于客戶反饋計(jì)算準(zhǔn)確評(píng)級(jí)的框架,將用戶的評(píng)論作為輸入條件,通過(guò)信息檢索刪除所有常用的詞,對(duì)評(píng)論中剩余的詞進(jìn)行標(biāo)注以及關(guān)鍵詞提取,通過(guò)概率計(jì)算對(duì)服務(wù)進(jìn)行排名。

1.4 基于推薦系統(tǒng)的在線服務(wù)評(píng)價(jià)

推薦系統(tǒng)是一種個(gè)性化的推薦方法。文獻(xiàn)[16]提出一種局部最優(yōu)服務(wù)選擇模型。該模型選擇服務(wù)中單個(gè)最優(yōu)的服務(wù)并將其組合,然而這種服務(wù)組合的結(jié)果可能只是局部最優(yōu),并不一定是全局最優(yōu)。文獻(xiàn)[17]提出一種服務(wù)推薦方法,首先對(duì)用戶已有評(píng)價(jià)信息進(jìn)行分析,挖掘出不可靠的惡意評(píng)價(jià)信息,然后通過(guò)計(jì)算用戶的可信度刪除惡意評(píng)價(jià)用戶。該方法的不足之處在于需要在篩除惡意用戶之后,所推薦的服務(wù)才會(huì)更好地符合用戶的偏好需求,而由于在線服務(wù)的數(shù)量巨大,不可能篩除所有惡意用戶的評(píng)價(jià)信息。

1.5 基于信譽(yù)系統(tǒng)的在線服務(wù)評(píng)價(jià)

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

2 基于Slater方法的在線服務(wù)評(píng)價(jià)

2.1 問(wèn)題定義

本文對(duì)在線服務(wù)評(píng)價(jià)相關(guān)問(wèn)題定義如下:

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

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

定義3ui表示第i個(gè)用戶,其對(duì)在線服務(wù)之間評(píng)價(jià)的偏好關(guān)系分為以下情況:若ri,j>ri,k,則sj?sk,其中sj?sk表示用戶ui認(rèn)為服務(wù)sj優(yōu)于服務(wù)sk,符號(hào)“?”表示優(yōu)于;若ri,j=ri,k,則sj～sk,其中sj～sk表示用戶ui認(rèn)為服務(wù)sj和服務(wù)sk不分優(yōu)劣;若ri,j

本文對(duì)在線服務(wù)評(píng)價(jià)的總體思想是:在用戶偏好以及評(píng)價(jià)準(zhǔn)則不一致的情況下,根據(jù)用戶對(duì)在線服務(wù)的評(píng)分,首先對(duì)稀疏的用戶-服務(wù)矩陣進(jìn)行填充,然后構(gòu)建以服務(wù)為節(jié)點(diǎn)、以優(yōu)先關(guān)系為有向邊的有向圖,最后通過(guò)Slater方法[21]得到在線服務(wù)評(píng)價(jià)結(jié)果。

2.2 偏好關(guān)系獲取

為對(duì)在線服務(wù)進(jìn)行評(píng)價(jià),需要獲取每個(gè)用戶對(duì)在線服務(wù)的評(píng)分。由于在線服務(wù)的種類和數(shù)量非常多,用戶不可能選用所有的服務(wù),也不可能對(duì)所有的在線服務(wù)進(jìn)行評(píng)價(jià),從而導(dǎo)致評(píng)分?jǐn)?shù)據(jù)的不完整性,造成用戶-服務(wù)評(píng)分矩陣較為稀疏[22]。由于本文是基于用戶對(duì)服務(wù)的兩兩比較,因此需要對(duì)稀疏的用戶-服務(wù)矩陣進(jìn)行填充。目前協(xié)同過(guò)濾[23]是一種常用的推薦方法,該方法通過(guò)尋找與自己偏好最相似的用戶進(jìn)行推薦,本文采用協(xié)同過(guò)濾算法對(duì)不完整的用戶-服務(wù)評(píng)分矩陣進(jìn)行填充。

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

(1)

其中:1表示用戶ui認(rèn)為服務(wù)sp優(yōu)于sq服務(wù);0表示用戶ui認(rèn)為服務(wù)sp和服務(wù)sq具有同等效用;-1表示用戶ui認(rèn)為服務(wù)sq優(yōu)于服務(wù)sp。

根據(jù)每個(gè)用戶的偏好矩陣ZHi統(tǒng)計(jì)出m個(gè)用戶中zhpq(i)=1和zhqp(i)=-1的用戶數(shù)進(jìn)行比較,如式(2)所示。

(2)

2.3 在線服務(wù)群體評(píng)價(jià)排序

為更明確地闡述本文提出的利用Slater社會(huì)選擇理論對(duì)在線服務(wù)進(jìn)行評(píng)價(jià),給出相關(guān)定義如下:

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

(3)

其中:tup1,q1-tup2,q2>0,表示在服務(wù)優(yōu)先對(duì)Lpq中服務(wù)對(duì)sp1,q1排在服務(wù)對(duì)sp2,q2之前;tup1,q1-tup2,q2=0,表示在服務(wù)優(yōu)先對(duì)Lpq中服務(wù)對(duì)sp1,q1和服務(wù)對(duì)sp2,q2不分前后;tup1,q1-tup2,q2<0,表示在服務(wù)優(yōu)先對(duì)Lpq中服務(wù)對(duì)sp2,q2排在服務(wù)對(duì)sp1,q1之前。

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

根據(jù)得到的服務(wù)優(yōu)先對(duì)Lpq,將Lpq中的優(yōu)先關(guān)系視為有向圖中邊的指向關(guān)系,如Lpq:(sp,sq)表示在有向圖中有從sp指向sq的有向邊。遍歷服務(wù)優(yōu)先對(duì)Lpq,得到Lpq中所有的節(jié)點(diǎn)和有向邊,將Lpq中的每條有向邊以及節(jié)點(diǎn)依次添加到圖中,最終構(gòu)造以服務(wù)為節(jié)點(diǎn)、以優(yōu)先關(guān)系為有向邊的有向圖。

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

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

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

2.4 具體示例

例1假設(shè)有5個(gè)用戶對(duì)5個(gè)在線服務(wù)進(jìn)行評(píng)分,如表1所示,其中,小數(shù)為利用協(xié)同過(guò)濾算法填充后的評(píng)分值,根據(jù)定義1～定義6構(gòu)造的有向圖如圖1所示。

表1 用戶對(duì)在線服務(wù)的評(píng)分

圖1 有向圖G

在有向圖G中,s1到s2、s3、s5存在邊:s1→s2,s1→s3,s1→s5,s2、s3、s5到s4存在邊:s2→s4,s3→s4,s4→s5。根據(jù)定義7,可以得出{s2,s3,s4}是相似集,即Sim={s2,s3,s4}。又因?yàn)樵谟邢驁D中存在邊s3→s2,s3→s4,s2→s4,所以s3?s2?s4。

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

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

遍歷有向圖G,根據(jù)相似集、前集、后集的定義,分別找到相似集、前集、后集,并根據(jù)3個(gè)集合之間以及內(nèi)部節(jié)點(diǎn)有向邊的指向關(guān)系,判斷有向圖中所有節(jié)點(diǎn)的指向關(guān)系,從而得出所有節(jié)點(diǎn)的排序,節(jié)點(diǎn)的排序也即是服務(wù)的排序,將節(jié)點(diǎn)的排序轉(zhuǎn)化為服務(wù)的排序,最終得出在線服務(wù)的排序。因此,在圖1中最終排序結(jié)果為:s1?s3?s2?s4?s5,轉(zhuǎn)化為服務(wù)的評(píng)價(jià)結(jié)果:s1?s3?s2?s4?s5,因此,最優(yōu)服務(wù)為s1,最劣服務(wù)為s5。

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

服務(wù)的評(píng)價(jià)值越大,表示該服務(wù)在整體排序中名次越靠前。O=(s1,s4,s2,s3)表示服務(wù)的排序?yàn)閟1?s4?s2?s3,其中,s1為最優(yōu)服務(wù),s3為最劣服務(wù),服務(wù)s1的評(píng)價(jià)值W1=4-1+1=4。

3 在線服務(wù)評(píng)價(jià)理論分析

3.1 孔多塞性

如果存在服務(wù)sp,有一半以上的用戶認(rèn)為服務(wù)sp優(yōu)于其他服務(wù),則服務(wù)sp是孔多塞候選服務(wù)。

3.2 單調(diào)性

對(duì)于任意不同的服務(wù)sp和sq,有sp?sq。如果某個(gè)用戶對(duì)服務(wù)sp給予較高評(píng)分而對(duì)服務(wù)sq的評(píng)分不變,則服務(wù)sp在總體服務(wù)排序中其排名應(yīng)提高或者不變;如果某個(gè)用戶對(duì)服務(wù)sp評(píng)分保持不變且對(duì)服務(wù)sq給予較低評(píng)分,則服務(wù)sq的總體排名不應(yīng)該降低,并且最終結(jié)果仍為sp?sq。

3.3 反對(duì)稱性

對(duì)于服務(wù)sp和sq,如果每個(gè)用戶都認(rèn)為服務(wù)sp優(yōu)于sq服務(wù),則最終排序結(jié)果為sp?sq。當(dāng)每個(gè)用戶都作出相反偏好選擇時(shí),也即是每個(gè)用戶都認(rèn)為服務(wù)sq優(yōu)于sp服務(wù)時(shí),則最終服務(wù)排序結(jié)果為sq?sp。

證明:若每個(gè)用戶對(duì)服務(wù)sp、sq的偏好由sp優(yōu)于sq變?yōu)閟q優(yōu)于sp,則有tupq

3.4 抗操縱性

對(duì)于任意服務(wù)sp的評(píng)分提高或者降低時(shí),最終的服務(wù)排序結(jié)果保持不變。

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

本文采用具有真實(shí)評(píng)分?jǐn)?shù)據(jù)的電影數(shù)據(jù)集MovieLens進(jìn)行實(shí)驗(yàn)。該數(shù)據(jù)集包含943名用戶以及1 682部電影,共有10萬(wàn)條左右用戶對(duì)電影的評(píng)分。實(shí)驗(yàn)環(huán)境為:64位Windows7操作系統(tǒng),Intel Core i5 CPU,8 GB內(nèi)存,開(kāi)發(fā)語(yǔ)言是Matlab 2016a。

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

4.1 孔多塞性實(shí)驗(yàn)

如果Slater法得到的最優(yōu)服務(wù)與孔多塞候選服務(wù)一致,則表明該方法滿足孔多塞性。本文實(shí)驗(yàn)中選取943名用戶對(duì)52個(gè)服務(wù)的評(píng)分作為基礎(chǔ)。根據(jù)所有用戶對(duì)服務(wù)的評(píng)分,可得服務(wù)8(即s8)有一半以上的用戶認(rèn)為其優(yōu)于其他任意一個(gè)服務(wù),因此,s8為孔多塞服務(wù)。Slater法、Average法、Sum法、Copeland法得到的評(píng)價(jià)結(jié)果如圖2～圖5所示。通過(guò)對(duì)比可知,Average法和Sum法得到的最優(yōu)服務(wù)均是s18,因此,Average法和Sum法不滿足孔多塞性,而Copeland法和Slater法得到的最優(yōu)服務(wù)均是s8,滿足孔多塞性。

圖2 Slater法評(píng)價(jià)結(jié)果

圖3 Average法評(píng)價(jià)結(jié)果

圖4 Sum法評(píng)價(jià)結(jié)果

圖5 Copeland法評(píng)價(jià)結(jié)果

4.2 單調(diào)性實(shí)驗(yàn)

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

圖6 提高評(píng)分的評(píng)價(jià)結(jié)果

圖7 降低評(píng)分的評(píng)價(jià)結(jié)果

由圖6可以看出,當(dāng)提高用戶對(duì)在線服務(wù)的評(píng)分時(shí),Slater法得到的該服務(wù)的評(píng)價(jià)值增大,表明該服務(wù)在總體服務(wù)排序中排名提高。由圖7可以看出,當(dāng)降低用戶對(duì)在線服務(wù)的評(píng)分時(shí),Slater法得到的該服務(wù)的評(píng)價(jià)值減小,表明該服務(wù)在總體服務(wù)排序中排名逐漸靠后。由此表明,Slater法得到的評(píng)價(jià)結(jié)果滿足單調(diào)性。

4.3 反對(duì)稱性實(shí)驗(yàn)

為驗(yàn)證Slater法得到的評(píng)價(jià)結(jié)果滿足反對(duì)稱性,任取某個(gè)用戶對(duì)2個(gè)在線服務(wù)的評(píng)分給予相反選擇,若通過(guò)Slater法得到的評(píng)價(jià)結(jié)果排序也相反,則該方法滿足反對(duì)稱性。本文實(shí)驗(yàn)將用戶對(duì)服務(wù)的評(píng)分全部取反,并分別用Slater法得出評(píng)分取反前與評(píng)分取反后的評(píng)價(jià)值,如圖8所示。可以看出,當(dāng)用戶對(duì)服務(wù)的評(píng)分取反后,Slater法得到的評(píng)價(jià)結(jié)果也作相反選擇,且取反前與取反后的評(píng)價(jià)值關(guān)于評(píng)價(jià)值26對(duì)稱。由此表明,Slater法得到的評(píng)價(jià)結(jié)果滿足反對(duì)稱性。

圖8 反對(duì)稱性驗(yàn)證結(jié)果

4.4 抗操縱性實(shí)驗(yàn)

為驗(yàn)證Slater法的抗操縱性,隨機(jī)選取某個(gè)在線服務(wù):1)增加對(duì)該服務(wù)給予較高評(píng)分的不誠(chéng)實(shí)用戶;2)增加對(duì)該服務(wù)給予較低評(píng)分的不誠(chéng)實(shí)用戶,如果得到的最終排序結(jié)果與增加不誠(chéng)實(shí)用戶前的排序結(jié)果一致,則Slater法得到的評(píng)價(jià)結(jié)果具有抗操縱性。4種方法得到的評(píng)價(jià)值如圖9和圖10所示。可以看出,Slater法得到的評(píng)價(jià)值并沒(méi)有隨著不誠(chéng)實(shí)用戶數(shù)的增加而變大,也沒(méi)有隨著用戶對(duì)服務(wù)評(píng)分的降低而變小,即服務(wù)排名基本不受影響,相比之下,Average法、Sum法、Copeland法得到的評(píng)價(jià)值則變化較大,即該服務(wù)排名受到較大的影響。由此表明,Slater法得到的在線服務(wù)評(píng)價(jià)結(jié)果具有較強(qiáng)的抗操縱性,不會(huì)因?yàn)椴糠植环ㄓ脩魧?duì)服務(wù)的評(píng)分而影響最終的服務(wù)評(píng)價(jià)結(jié)果。

圖9 將用戶評(píng)分提升至4分的評(píng)價(jià)結(jié)果

圖10 將用戶評(píng)分降低至2分的評(píng)價(jià)結(jié)果

4.5 多數(shù)準(zhǔn)則沖突實(shí)驗(yàn)

多數(shù)準(zhǔn)則是指對(duì)于任意2個(gè)不同的在線服務(wù)sp、sq,如果認(rèn)為服務(wù)sp優(yōu)于服務(wù)sq的用戶數(shù)量多于認(rèn)為服務(wù)sq優(yōu)于sp服務(wù)的用戶數(shù)量,則sp?sq。那么根據(jù)多數(shù)準(zhǔn)則沖突,把認(rèn)為服務(wù)sq優(yōu)于服務(wù)sp的用戶數(shù)量稱為多數(shù)準(zhǔn)則沖突數(shù)量。本文保持服務(wù)的數(shù)量固定不變,采用5組不同用戶數(shù)量的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),統(tǒng)計(jì)出Slater法、Sum法、Average法、Copeland法各自滿足多數(shù)準(zhǔn)則沖突的比例,如圖11所示。可以看出,Slater法滿足多數(shù)準(zhǔn)則沖突的比例遠(yuǎn)低于Average法、Sum法和Copeland法,即表明該方法得到的評(píng)價(jià)結(jié)果更好地滿足多數(shù)準(zhǔn)則,能夠符合較多用戶的偏好需求。

圖11 多數(shù)準(zhǔn)則沖突實(shí)驗(yàn)結(jié)果

4.6 運(yùn)行時(shí)間

設(shè)定服務(wù)的數(shù)量固定,依次增加用戶的數(shù)量,比較Slater法、Sum法、Average法、Copeland法每次排序后的系統(tǒng)運(yùn)行時(shí)間,如圖12所示。可以看出,隨著用戶數(shù)量的增加,系統(tǒng)計(jì)算用戶評(píng)價(jià)的次數(shù)增加,導(dǎo)致運(yùn)行時(shí)間逐漸增加。然而Slater法運(yùn)行時(shí)間并沒(méi)有隨著用戶數(shù)量成倍增加,因此該方法效率較高。此外還可以看出,相比于Sum法、Average法、Copeland法,雖然Slater法運(yùn)行時(shí)間較長(zhǎng),但是對(duì)其進(jìn)行操縱比Sum法、Average法、Copeland法需要更長(zhǎng)的時(shí)間,因此,Slater法得到的評(píng)價(jià)結(jié)果其抗操縱難度比Sum法、Average法、Copeland法更高。

圖12 運(yùn)行時(shí)間比較

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

本文基于社會(huì)選擇理論的基本思想,利用Slater法對(duì)在線服務(wù)進(jìn)行評(píng)價(jià),解決因用戶偏好和評(píng)價(jià)準(zhǔn)則不一致導(dǎo)致的在線服務(wù)評(píng)分不可比較的問(wèn)題。該方法將不可比較的評(píng)分轉(zhuǎn)化為用戶對(duì)不同服務(wù)的個(gè)人偏好矩陣,利用Slater法得到在線服務(wù)的評(píng)價(jià)結(jié)果。理論分析和實(shí)驗(yàn)比較結(jié)果表明,本文方法得到的在線服務(wù)評(píng)價(jià)結(jié)果滿足孔多塞性、單調(diào)性、反對(duì)稱性和抗操縱性,驗(yàn)證了其對(duì)在線服務(wù)評(píng)價(jià)的有效性。由于Slater問(wèn)題是NP-hard問(wèn)題,隨著在線服務(wù)數(shù)量的增加,Slater法計(jì)算在線服務(wù)評(píng)價(jià)的難度將有所增加,因此下一步將對(duì)本文方法進(jìn)行優(yōu)化,提高算法效率并降低系統(tǒng)消耗。