李 威，付曉東,2，劉 驪，劉利軍

(1.昆明理工大學(xué) 信息工程與自動化學(xué)院，昆明 650500； 2.昆明理工大學(xué) 航空學(xué)院，昆明 650500) (*通信作者電子郵箱xiaodong_fu@hotmail.com)

基于社會選擇理論的在線服務(wù)評價

李 威1，付曉東1,2*，劉 驪1，劉利軍1

(1.昆明理工大學(xué) 信息工程與自動化學(xué)院，昆明 650500； 2.昆明理工大學(xué) 航空學(xué)院，昆明 650500) (*通信作者電子郵箱xiaodong_fu@hotmail.com)

用戶評價標(biāo)準(zhǔn)不一致和偏好不一致導(dǎo)致網(wǎng)絡(luò)空間中的在線服務(wù)之間不具備公正的可比較性，從而用戶難以選擇到滿意的在線服務(wù)，因此，提出了基于社會選擇理論計算在線服務(wù)優(yōu)劣的排序方法。首先，根據(jù)用戶給出的用戶-服務(wù)評價矩陣構(gòu)建群體偏好矩陣；然后，基于群體偏好矩陣和Kemeny社會選擇函數(shù)構(gòu)建0- 1整數(shù)規(guī)劃模型；最后，通過求解該模型可得到服務(wù)的最優(yōu)排序結(jié)果。該方法聚合個體偏好為群體偏好，決策符合群體大多數(shù)人的偏好且與個體偏好保持最大的一致性。通過理論分析和實驗驗證了該方法的合理性和有效性。實驗結(jié)果表明，該方法能有效地解決在線服務(wù)之間的不可比較性問題，實現(xiàn)在線服務(wù)的優(yōu)劣排序，并可以有效抵制推薦攻擊，具有較強的抗操縱性。

在線服務(wù)；社會選擇理論；Kemeny函數(shù)；服務(wù)排序；群體決策

0 引言

隨著在線服務(wù)的爆炸性增長，用戶面臨著如何在大量的在線服務(wù)中選擇偏愛的、優(yōu)質(zhì)的在線服務(wù)的問題。然而不同用戶對服務(wù)質(zhì)量的要求各有不同，面對大量功能相同或相近的在線服務(wù)[1]，單個用戶不可能與每一個服務(wù)都產(chǎn)生交互，更不可能對每一個服務(wù)都給予評價，越來越多的用戶訪問在線服務(wù)的所形成的經(jīng)驗表明，一個優(yōu)質(zhì)的在線服務(wù)要盡可能地滿足絕大多數(shù)人的偏好，因此，優(yōu)質(zhì)的在線服務(wù)成為用戶服務(wù)選擇的自然需求。

在線服務(wù)的評價，是用戶自身與該在線服務(wù)交互過程中所產(chǎn)生的一種主觀感受[2]，但是，用戶的主觀感受很難被客觀地描述和獲取，且對選擇同一服務(wù)的不同用戶而言，由于用戶自身的背景、心理和偏好等因素的不同，使得用戶之間的評價標(biāo)準(zhǔn)不一致[1-2]，即使服務(wù)之間具有同樣的服務(wù)質(zhì)量表現(xiàn)，它們得到的評價也不盡然相同。用戶的評價正是用戶對于在線服務(wù)是否滿足用戶偏好的主觀感受表現(xiàn)，因此，評價值的高低可以較好地反映用戶使用在線服務(wù)的主觀感受。文獻[3]的研究中指出在線服務(wù)提供者選擇必須考慮用戶觀點，由于不同用戶之間的評價尺度不一致，即使在線服務(wù)使不同用戶均感到滿意，它們得到的評價也會不一致，進一步導(dǎo)致在線服務(wù)之間不具備公正的可比較性；另外，還有一些不法的用戶和在線服務(wù)提供商為了提高或降低某些在線服務(wù)的影響力，采取欺騙手法惡意捏造用戶評分?jǐn)?shù)據(jù)而達到操縱服務(wù)信用的目的[4]，扭曲在線服務(wù)的可信度，致使用戶利用這種可信度進行服務(wù)選擇時會產(chǎn)生不客觀的結(jié)果，從而使用戶面臨不能選擇到合適服務(wù)的風(fēng)險。

針對用戶評價標(biāo)準(zhǔn)不一致和偏好不一致導(dǎo)致網(wǎng)絡(luò)空間中的在線服務(wù)之間不具備公正的可比較性問題。本文基于社會選擇理論的基本思想，提出一種決策分析方法，該方法使個體偏好和群體決策達到最大一致。該方法不對任何用戶的評價標(biāo)準(zhǔn)作任何假定，在充分考慮用戶主觀偏好選擇和不同評價標(biāo)準(zhǔn)的條件下，通過集結(jié)個人偏好形成群決策，設(shè)計了從大量用戶的偏好序中產(chǎn)生一個最優(yōu)的在線服務(wù)優(yōu)劣排序方法，最后通過理論分析和實驗驗證了該方法的有效性和合理性。

1 相關(guān)研究

近年來，大量的研究工作已經(jīng)或正在圍繞利用用戶的評價信息判斷服務(wù)質(zhì)量優(yōu)劣的問題展開。目前在線電子商務(wù)評價方法主要有累加法、平均法、概率法、模糊法、流程法等[5]。文獻[1]的研究指出目前的服務(wù)評分值的預(yù)測方法主要采用簡單平均值、加權(quán)平均值、中心加權(quán)平均值3種統(tǒng)計的方法，但不同用戶的評價值之間不可簡單累加和求平均；文獻[6]提出了一種基于可信評價的制造云服務(wù)選擇方法，采用加權(quán)平均的方法計算制造云服務(wù)的整體可信度，能有效地識別云制造環(huán)境下的制造云服務(wù)實體，但加權(quán)平均的方法下的評價值不具備可比較性；文獻[7]利用Beta信譽系統(tǒng)的信譽計算方法作為評價服務(wù)水平協(xié)議可信度的評價標(biāo)準(zhǔn)，雖在用戶偏好不確定的條件下提高了云服務(wù)組合的兼容性精確度，但不能滿多數(shù)人的偏好。推薦系統(tǒng)與信譽系統(tǒng)領(lǐng)域，文獻[8]的研究指出現(xiàn)有的推薦系統(tǒng)假定不同用戶間主觀性的不一致導(dǎo)致評價不一致，現(xiàn)有信譽系統(tǒng)都假定所有用戶具有一致的評價標(biāo)準(zhǔn)，然而用戶對在線服務(wù)的偏好和評價不可能完全一致，甚至可能出現(xiàn)矛盾和沖突。對群決策而言，文獻[9]的研究中分析了3種最常用的群組決策策略：Average Satisfaction、Minimum Misery、Maximum Satisfaction，但這三種策略均是同等地看待用戶的評價；文獻[10]的研究中指出Average Satisfaction可能導(dǎo)致更多的推薦偏見，Minimum Misery可能忽視大多數(shù)人的偏好；MusicFX[11]是一個健身房背景音樂群組推薦系統(tǒng)，采用的是Maximum Satisfaction群組決策策略，它試圖最大化群組成員的滿意度，其關(guān)鍵的前提條件用戶必須事先對所有音樂網(wǎng)站都給予評價，但對于大規(guī)模的音樂網(wǎng)站來說顯得效率及其低下；文獻[12]指出目前所有的推薦系統(tǒng)都面臨著一些共性的重難點問題：評價數(shù)據(jù)稀疏[13]和推薦系統(tǒng)的安全性即推薦攻擊等問題，然而，這些問題都嚴(yán)重影響著推薦排序的優(yōu)劣結(jié)果，不能給予用戶更好的決策選擇。文獻[14]通過分析移動用戶行為，提出一種基于信任度和鏈接預(yù)測的移動用戶偏好預(yù)測方法，在一定程度上解決了稀疏性問題，但采用的是平均評分值，未考慮用戶評價不一致性；文獻[15]的研究提出社會選擇理論與云計算相結(jié)合的方法應(yīng)用于在線營銷研究，與傳統(tǒng)的方式相比，充分考慮了用戶不一致的觀點，幫助市場管理者作出高效而實際的決策；文獻[16]指出用戶使用在線服務(wù)后進行的主觀評價,易受自身因素影響,不同用戶對同一在線服務(wù)作出的評價可能存在較大差異，因此當(dāng)用戶根據(jù)前人經(jīng)驗評價進行服務(wù)選擇時,必須考慮用戶主觀因素對于評價值的影響。

上述研究很少考慮用戶主觀因素不一致導(dǎo)致的問題，大多數(shù)研究都是假定用戶的評價標(biāo)準(zhǔn)和評價尺度一致的情況下基于用戶對服務(wù)的評價來評估在線服務(wù)優(yōu)劣，均是同等地看待每個用戶的評價?？紤]到現(xiàn)有研究中存在的不足，本文基于社會選擇理論思想對在線服務(wù)進行群體評價，提出了利用Kemeny函數(shù)[17]來計算在線服務(wù)的優(yōu)劣排序的方法。Kemeny函數(shù)是社會選擇理論中唯一的同時滿足中性、一致性及孔多賽性的社會選擇函數(shù)[18]。在不需要假定用戶評價標(biāo)準(zhǔn)和評價尺度一致的情況下，通過集結(jié)個人用戶的歷史評價結(jié)果形成聚合排序，對在線服務(wù)服務(wù)群體評價形成群決策，解決用戶在偏好不一致及評價標(biāo)準(zhǔn)不一致情況下的服務(wù)優(yōu)劣選擇問題，一定程度上避免了用戶評分?jǐn)?shù)據(jù)極端稀疏的負面影響，又達到有效地抵制推薦攻擊的目的。

2 問題描述

為了更好地闡述開放網(wǎng)絡(luò)環(huán)境下的用戶偏好不一致和評價準(zhǔn)則不一致的在線服務(wù)評價問題，本文首先給出相關(guān)定義如下。

定義1 集合U={ui|i=1,2,…,m}為所有用戶集合；集合S={sj|j=1,2,…,n}為用戶與所有在線服務(wù)產(chǎn)生交互的服務(wù)集合。

定義2 所有用戶對其評價的服務(wù)形成的矩陣為用戶-服務(wù)評分矩陣R=[rij]m*n；其中rij表示第i個用戶對第j個服務(wù)的評價值且rij=[0,5]，若rij=0則表明第i個用戶對第j個服務(wù)未評價。

綜合比較了現(xiàn)有的在線服務(wù)評價方法后，針對用戶主觀評價標(biāo)準(zhǔn)不一致的研究表明一種公正且有效的在線服務(wù)優(yōu)劣評價方法應(yīng)當(dāng)滿足以下特性：

1)一致性。若結(jié)果的最優(yōu)服務(wù)排序中服務(wù)sx優(yōu)于sy，那么大多數(shù)用戶均認為服務(wù)sx優(yōu)于sy(或sx至少不劣于sy)。

2)孔多賽性。當(dāng)大多數(shù)用戶認為服務(wù)sx優(yōu)于其他服務(wù)(該在線服務(wù)在逐對比較時優(yōu)于其他所有服務(wù))，那么sx優(yōu)于其他的在線服務(wù)。

3)公平性(中性)。若每個用戶對兩個服務(wù)作相反評價時,群體最優(yōu)服務(wù)排序的結(jié)果也要作相反選擇；公平性是對在線服務(wù)的公平性，它防止用戶偏袒某一在線服務(wù)，因為它保證在每個用戶都對兩個在線服務(wù)作相反選擇時，那排序結(jié)果應(yīng)作相反的選擇，亦即社會選擇機制應(yīng)同樣對待所有在線服務(wù)。

4)多數(shù)準(zhǔn)則性。若認為服務(wù)sx優(yōu)于服務(wù)sy的人數(shù)多于認為服務(wù)sy優(yōu)于服務(wù)sx的人數(shù)，那么最優(yōu)服務(wù)排序結(jié)果中服務(wù)sx必須優(yōu)于服務(wù)sy。

5)防操縱性。若操縱某些服務(wù)的評價時，即提高或者降低某些服務(wù)的評分時，那么最終的服務(wù)排序結(jié)果也應(yīng)保持不變。

3 基于社會選擇理論的在線服務(wù)評價方法

用戶對在線服務(wù)的評分是用戶的主觀感受，故不同用戶對同一在線服務(wù)評價標(biāo)準(zhǔn)存在較大差異，所以對于不同用戶對同一在線服務(wù)的評價信息是不能用同等看待的。為此常用評價中的累加求和法(Sum)、求平均法(Average)和Beta信譽系統(tǒng)的信譽計算方法[19]得出的評價結(jié)果具有誤導(dǎo)性，而且若用戶評價值一旦被攻擊，那么累加和法、平均法和Beta信譽計算法得出的評價結(jié)果會極易被改變，因此，提出一種基于社會選擇理論[20]對在線服務(wù)進行群體評價的方法，將同一用戶對不同在線的評價轉(zhuǎn)換成用戶對在線服務(wù)的偏好關(guān)系，然后集結(jié)所有用戶的偏好，形成群體評價。

定義3ui是一個用戶，其評價的在線服務(wù)之間的偏好關(guān)系：若rij>rik，則sj?isk；若rij=rik，則sj～isk；若rij

定義4 用戶的評價偏好排序Oi，其中，Oi={sk|k=1,2,…,t},1≤t≤n,1≤i≤m，Oi表示第i個用戶ui依據(jù)用戶偏好規(guī)則建立的在線服務(wù)偏好排序序列，如Oj={s2,s4,s1,s3,s5,…}表示用戶uj認為s2?s4?s1?s3?s5?…。

定義5 用戶偏好矩陣C=[cij]n*n，其中：

(1)

其中：I(si?sj)為指示函數(shù)，即當(dāng)si?sj時，I=1；否則I=0。

在這里，用戶偏好矩陣C是將m個用戶所評價的n個在線服務(wù)，根據(jù)用戶評價偏好排序Oi對在線服務(wù)進行兩兩成對比較，統(tǒng)計m個用戶中認為si?sj的次數(shù)；很顯然，矩陣C的第i行表示在線服務(wù)i優(yōu)于其他服務(wù)的次數(shù)，矩陣C的第j列表示在線服務(wù)j劣于其他服務(wù)的次數(shù)。

將每個在線服務(wù)與所有其他服務(wù)兩兩成對比較，只要一個服務(wù)在大多數(shù)用戶投票上的得分高于另一個候選服務(wù)，那么它便擊敗了那個候選服務(wù)。擊敗所有其他服務(wù)的便是孔多塞贏家。這方法稱為孔多賽標(biāo)準(zhǔn)[21]。

由于用戶自身的評價標(biāo)準(zhǔn)是一致的，所以用戶自身評價各服務(wù)之間的評價值是具備可比較性的，不需要同等地看待不同用戶的評價標(biāo)準(zhǔn)，不需假定用戶之間具有一致性的標(biāo)準(zhǔn)，因此，有效地避免不同用戶之間的評價標(biāo)準(zhǔn)與評價尺度不一致所產(chǎn)生評價值的比較；這就解決了由于用戶評分準(zhǔn)則不一致而導(dǎo)致的不同用戶對同一在線服務(wù)的評分不可較的問題。

定義6 用戶偏好比例矩陣E=[eij]n*n，其中：

E=[eij]n*n=(C-CT)/m

(2)

其中：eij表示群體m個用戶中認為服務(wù)si優(yōu)于服務(wù)sj的人數(shù)比例與群體用戶中認為服務(wù)si劣于sj服務(wù)的人數(shù)比例之差；矩陣E反映了群體用戶對各在線服務(wù)總的偏好。

定義7 社會選擇的排序矩陣為P=[pjk]n*n，其中：

(3)

顯然，對于n個在線服務(wù)而言，僅考慮嚴(yán)格的優(yōu)于關(guān)系，n個在線服務(wù)的排序種類也達到n!個，根據(jù)排序關(guān)系(3)它的每一種優(yōu)劣排序都對應(yīng)相應(yīng)的排序矩陣P。

3.1 基于Kemeny社會選擇函數(shù)的在線服務(wù)評價

基于Kemeny社會選擇函數(shù)[22]的在線服務(wù)評價的思想是將所有用戶的個體偏好集結(jié)成群體偏好，以得出在線服務(wù)的一個群排序。對n個在線服務(wù)而言，需要先逐一地計算n!個社會選擇排序矩陣，然后再計算出每一個排列矩陣的Kemeny數(shù)值，并將最大的函數(shù)值所對應(yīng)的排列作為最符合群體偏好的排列。

3.1.1 Kemeny函數(shù)

(4)

式(4)來衡量排列矩陣P與用戶的群體偏好的一致性或相似性；這個模型依據(jù)是當(dāng)P中的元素pij的符號盡可能多地與E中對應(yīng)的元素eij的符號一致時，P所對應(yīng)的最優(yōu)排列將能更好地反映出群體的偏好；Kemeny函數(shù)是要找符合孔多塞標(biāo)準(zhǔn)的P，使得〈E·P〉取最大值的P*：

(5)

即對任意P均滿足：

fk(P)≤fk(P*)

(6)

3.1.2 Kemeny函數(shù)0- 1整數(shù)規(guī)劃

利用Kemeny函數(shù)進行群決策的最大困難是它較大的計算量，文獻[23]指出Kemeny函數(shù)計算是個NP-hard問題。由于其計算的復(fù)雜性，本文采用0- 1整數(shù)規(guī)劃模型來求解Kemeny函數(shù)的最佳在線服務(wù)評價排序矩陣P*；根據(jù)社會選擇排序矩陣P中的排序關(guān)系式(3)，只需考慮排序矩陣P中右上角矩陣元素，即可求出所有的排序關(guān)系；又由于用戶比例矩陣E為對角線為0的反對稱矩陣，故：

(7)

因此，對文獻[24]提出的整數(shù)規(guī)劃目標(biāo)函數(shù)進行如下改進，Kemeny函數(shù)的0- 1整數(shù)規(guī)劃模型如下：

目標(biāo)函數(shù)：

(8)

約束于:

(9)

3.2 方法過程描述

根據(jù)以上分析,本節(jié)設(shè)計了基于Kemeny函數(shù)的在線服務(wù)優(yōu)劣排序方法;集結(jié)用戶偏好排序，產(chǎn)生一個整體的在線服務(wù)優(yōu)劣排序,用戶可以選擇最令人滿意的在線服務(wù)。同時文獻[17-19]表明Kemeny函數(shù)是滿足中性、一致性及孔多賽性的社會選擇函數(shù)。綜上所述，設(shè)計求解不一致用戶偏好序信息的最佳在線服務(wù)評價排序的計算方法如下。

步驟1 集結(jié)所有用戶U評價的在線服務(wù)S，根據(jù)用戶偏好評價值建立用戶-服務(wù)評分矩陣R=[rij]m*n。

步驟2 根據(jù)用戶-服務(wù)評分矩陣R建立用戶的在線服務(wù)評價偏好排序Oi。

步驟3 集結(jié)所有用戶的服務(wù)評價偏好排序Oi計算用戶偏好矩陣C=[cij]n*n。

步驟4 依據(jù)用戶偏好矩陣C計算用戶偏好比例矩陣E=[eij]n*n，構(gòu)建Kemeny函數(shù)的0- 1整數(shù)規(guī)劃模型。

步驟6 依據(jù)最優(yōu)解矩陣P*和式(3)中的對應(yīng)關(guān)系，便可計算出最優(yōu)的服務(wù)優(yōu)劣排序或選擇最優(yōu)的在線服務(wù)。

4 評價模型理論分析

為了通過理論驗證基于Kemeny函數(shù)的在線服務(wù)優(yōu)劣排序方法的合理性和有效性，下面對Kemeny函數(shù)的孔多塞性、公平性、一致性和操縱復(fù)雜性進行證明。

定理1 孔多賽性。若?服務(wù)si，使得大多數(shù)的用戶均評價服務(wù)si優(yōu)于其他所有在線服務(wù)sj(?j=1,2,…,n,j≠i)有cki≥ckj(k=1,2,…,m)，則在線服務(wù)si是孔多賽贏者。

定理2 公平性。對任意服務(wù)si和sj，若每個用戶均認為si?ksj時，那么結(jié)果的整體排序中必有si?sj；若每個用戶取相反評價siksj時，那么結(jié)果的整體排序中必有sisj，則群體評價Kemeny函數(shù)對候選服務(wù)具有公平性。

證明 若對每個用戶的偏好序Ok(k=1,2,…,m)均滿足si?sj，必有cij≥cji，則有eij≥eji，又由于上文3.1.1節(jié)中的模型依據(jù)可知最終的排序結(jié)果pij與eij保持一致，則結(jié)果的整體排序中必有si?sj；相反可證若對每個用戶的偏好序Ok均滿足sisj時，則結(jié)果的整體排序中必有sisj，所以該函數(shù)滿足一致性，故fk(-P)=-fk(P)。

定理3 一致性。對大多數(shù)服務(wù)si和sj，若最終的排序結(jié)果中?si?sj，那么大多數(shù)用戶應(yīng)均認為si?sj，排序結(jié)果應(yīng)與大多數(shù)用戶保持一致，則該函數(shù)滿足一致性。

定理4 防操縱性。對?si服務(wù)而言，若增加對在線服務(wù)si給予低評分或者高評分的惡意欺詐用戶數(shù)，最終的評價結(jié)果應(yīng)不變。

證明 對于si，假設(shè)最終的評價結(jié)果中?si?sj，增加些許惡意欺詐用戶數(shù)的高評分(或低評分)評價偏好，則根據(jù)本文的在線服務(wù)排序方法并未改變cij，所以cij值不變，那么eij值不變，評價結(jié)果仍然是si?sj；故防操縱性強。

5 實驗結(jié)果與分析

根據(jù)本文提出的基于Kemeny函數(shù)的在線服務(wù)評價方法，設(shè)計實現(xiàn)了在線服務(wù)評價方法，用于評價在線服務(wù)優(yōu)劣，并對評價數(shù)據(jù)進行驗證，驗證評價方法的有效性及合理性。由于該方法基于用戶的評分記錄，因此必須建立用戶評分?jǐn)?shù)據(jù)集,為使實驗更為真實，參照MovieLens公開的數(shù)據(jù)集。在實驗中，本文模擬了943個在線服務(wù)使用者和10～100個在線服務(wù)，以數(shù)據(jù)集里的評分模擬為電子商務(wù)中用戶對服務(wù)表現(xiàn)的滿意程度，采用電子商務(wù)評價機制中常用的5個等級，1～5級分別表示很不滿意、不滿意、一般、滿意和很滿意，數(shù)據(jù)集中的0值表示用戶與該在線服務(wù)沒有產(chǎn)生交互或沒有評價。為了進一步驗證在線商品評價模型的高效性，本文使用現(xiàn)在兩種比較流行的在線服務(wù)評價方法:累加和(Sum)方法、平均(Average)方法、Beta信譽系統(tǒng)的信譽計算方法[25]作為本文的主要對比方法。

5.1 有效性實驗

該實驗用于驗證本文方法的有效性。實驗?zāi)M了943個服務(wù)用戶和10～100個在線服務(wù)，為驗證該方法的有效性，對不同服務(wù)樣本數(shù)量情況下算法記錄了依據(jù)本方法得到的最優(yōu)在線服務(wù)排序矩陣P*時的Kemeny函數(shù)值，如表1所示。

表1 服務(wù)最優(yōu)排序時的最大Kemeny值

由表1可見，固定用戶數(shù)量，隨著在線服務(wù)數(shù)量的增加，最優(yōu)服務(wù)排序的Kemeny函數(shù)值越來越大，說明用戶偏好比例矩陣E中的元素與服務(wù)排序矩陣P*中的元素保持符號一致越來越多，也表明保持一致性的人數(shù)也越來越多。

5.2 一致性實驗

該實驗用于驗證本文方法的一致性。若本文方法得到的整體排序結(jié)果與大多數(shù)用戶對服務(wù)評價的排序趨勢大致相同，則該方法具有一致性。為了驗證該方法的一致性，本文選擇Sum方法、Average方法、Beta方法以及本文方法，取這4種方法每次排序后的最優(yōu)的兩個在線服務(wù)，比較其一致性的人數(shù)，結(jié)果如圖1所示。由圖1可以看出，很明顯在大多數(shù)情況下本文方法的排序結(jié)果比Sum方法、Average方法、Beta方法的排序結(jié)果保持一致性的人數(shù)多，因此，本文提出的基于Kemeny函數(shù)的在線服務(wù)優(yōu)劣排序滿足一致性，更能與群體的偏好保持最大的一致。

圖1 不同方法的一致性對比

5.3 公平性實驗

該實驗用于驗證本文方法的公平性。若每個用戶對兩個候選方案作相反選擇時,群體的選擇結(jié)果也要作相反選擇，即fk(-P)=-fk(P)。為了驗證本方法的公平性，再利用Kemeny函數(shù)模型重新計算；例如一般情況下根據(jù)本文方法得到的最優(yōu)服務(wù)排序為s3?s5?s2?s4?s1；當(dāng)用戶取對服務(wù)的相反評價之后，再根據(jù)本文方法計算的最優(yōu)服務(wù)排序為服務(wù)的群體排序為s3s5s2s4s1。本次實驗?zāi)M了943個在線服務(wù)使用者和10～100個在線服務(wù)，初始評價與取相反評價后，比較其最優(yōu)在線服務(wù)排序的Kemeny值，如表2所示，實驗表明如果用戶作相反選擇，那么群體排序結(jié)果也會相反，因此該方法對服務(wù)評價是公平的。

5.4 抗操縱性和抵制推薦攻擊實驗

為了驗證該方法的抗操縱性，隨機選擇一個在線服務(wù)增加10～100個欺詐用戶，將該在線服務(wù)的評價值同時提高到5分或者同時降低到1分來產(chǎn)生惡意攻擊數(shù)據(jù)。與Sum方法、Average方法、Beta方法相比，本實驗中對于這4種方法都選取原最終排序為第20的在線服務(wù)，如圖2(a)和2(b)所示，本文方法結(jié)果幾乎不變，而Sum方法、Average方法隨著不誠實用戶數(shù)量的增多，使該在線服務(wù)的排序大量提前或推后了，Beta方法雖然開始變化不明顯，但是隨著不誠實用戶人數(shù)大量增加，服務(wù)排序名次也退后了，因此本方法具有防操縱性。

表2 初始評價與相反評價的Kemeny值對比

圖2 不同方法的抗操縱性對比

一些不法的用戶為了提高或降低某些對象的推薦概率，惡意捏造用戶評分?jǐn)?shù)據(jù)而達到目的，這也是推薦系統(tǒng)存在的一個安全問題，被稱為推薦攻擊[26]。本實驗隨機選擇943個用戶中的20%的用戶，再將其評價的在線服務(wù)的評價值同時提高到5分或者同時降低到1分來惡意攻擊數(shù)據(jù)，結(jié)果如圖3(a)和圖3(b)所示。由圖3可知，隨著服務(wù)數(shù)量的增加,未惡意攻擊評價數(shù)據(jù)與惡意攻擊評價數(shù)據(jù)后，圖中的未惡意攻擊數(shù)據(jù)與惡意攻擊數(shù)據(jù)后的點未發(fā)生非常明顯的變化，幾乎達到一致，本文方法產(chǎn)生的在線服務(wù)最佳排序幾乎未被影響；由此可見，Kemeny函數(shù)得到的最優(yōu)服務(wù)排序結(jié)果保持了多數(shù)用戶的偏好選擇，因此，本文方法能有效地抵制推薦攻擊，具有較強的抗操縱性。

圖3 抵制惡意攻擊問題

6 結(jié)語

本文提出了基于社會選擇理論的在線服務(wù)評價方法，緩解了由用戶偏好不一致和評價標(biāo)準(zhǔn)不一致，導(dǎo)致的用戶對在線服務(wù)不具備公正的可比較性問題。本文方法根據(jù)用戶已評價的在線服務(wù)，通過Kemeny函數(shù)集結(jié)用戶評價排序求出滿足群體偏好一致性的最優(yōu)在線服務(wù)優(yōu)劣排序,不需要假定用戶之間具有的評價標(biāo)準(zhǔn)和評價尺度一致性，保證了服務(wù)之間比較的公正性，并通過理論分析與實驗驗證了該方法的有效性、公平性、抗操縱性，能有效地抵制推薦攻擊，新加入用戶可直接選擇最優(yōu)在線服務(wù)。由于在實際應(yīng)用中，不斷有新用戶和新在線服務(wù)加入網(wǎng)絡(luò)空間，從而得到新的評價，因此群體最優(yōu)評價排序也需要實時更新，下一步的工作中將研究滿足用戶和服務(wù)動態(tài)增長的在線服務(wù)群體評價方法；并且隨著在線服務(wù)數(shù)量的大量增加，Kemeny函數(shù)的計算難度越來越大，下一步的工作也將研究如何優(yōu)化算法性能。

References)

[1] 王玉祥,喬秀全,李曉峰,等.上下文感知的移動社交網(wǎng)絡(luò)服務(wù)選擇機制研究[J].計算機學(xué)報,2010,33(11):2126-2135.(WANG Y X, QIAO X Q, LI X F, et al. Research on context-awareness mobile SNS service selection mechanism [J]. Chinese Journal of Computers, 2010, 33(11): 2126-2135.)

[2] WANG H, TANG Y, YIN G, et al. Trustworthiness of Internet-based software [J]. Science in China Series F: Information Sciences, 2006, 49(6): 759-773.

[3] SREENATH R M, SINGH M P. Agent-based service selection [J]. Web Semantics: Science, Services and Agents on the World Wide Web, 2004, 1(3): 261-279.

[4] 余力,董斯維,郭斌.電子商務(wù)推薦攻擊研究[J].計算機科學(xué),2007,34(5):134-138.(YU L, DONG S W, GUO B. Research on attack on personalized recommendations in e-commerce [J]. Computer Science, 2007, 34(5): 134-138.)

[5] YAO Y, RUOHOMAA S, XU F. Addressing common vulnerabilities of reputation systems for electronic commerce [J]. Journal of Theoretical and Applied Electronic Commerce Research, 2012, 7(1): 1-20.

[6] 魏樂,趙秋云,舒紅平.云制造環(huán)境下基于可信評價的云服務(wù)選擇[J].計算機應(yīng)用,2013,33(1):23-27.(WEI L, ZHAO Q Y, SHU H P. Cloud service selection based on trust evaluation for cloud manufacturing environment [J]. Journal of Computer Applications, 2013, 33(1): 23-27.)

[7] DASTJERDI A V, BUYYA R. Compatibility-aware cloud service composition under fuzzy preferences of users [J]. IEEE Transactions on Cloud Computing, 2014, 2(1): 1-13.

[8] J?SANG A, GUO G, PINI M S, et al. Combining recommender and reputation systems to produce better online advice [C]// Proceedings of the 2013 International Conference on Modeling Decisions for Artificial Intelligence. Berlin: Springer, 2013: 126-138.

[9] GARTRELL M, XING X, LYU Q, et al. Enhancing group recommendation by incorporating social relationship interactions [C]// Proceedings of the 16th ACM International Conference on Supporting Group Work. New York: ACM, 2010: 97-106.

[10] KIM J K, KIM H K, OH H Y, et al. A group recommendation system for online communities [J]. International Journal of Information Management, 2010, 30(3): 212-219.

[11] MCCARTHY J F, ANAGNOST T D. MusicFX: an arbiter of group preferences for computer supported collaborative workouts [C]// Proceedings of the 1998 ACM Conference on Computer Supported Cooperative Work. New York: ACM, 1998: 363-372.

[12] Lü L, MEDO M, YEUNG C H, et al. Recommender systems [J]. Physics Reports, 2012, 519(1): 1-49.

[13] ZHOU X, LIN D, ISHIDA T. Evaluating reputation of Web services under rating scarcity [C]// SCC 2016: Proceedings of the 2016 IEEE International Conference on Services Computing. Piscataway, NJ: IEEE, 2016: 211-218.

[14] 耿華,孟祥武,史艷翠.一種基于信任度和鏈接預(yù)測方法的移動用戶偏好預(yù)測方法[J].電子與信息學(xué)報,2013,35(12):2972-2977.(GENG H, MENG X W, SHI Y C. A mobile user preference prediction method based on trust and link prediction [J]. Journal of Electronics and Information Technology, 2013, 35(12): 2972-2977.)

[15] LI L I, NIU B, TANG X. Online marketing research based on social choice theory and cloud computing [C]// UCC 2015: Proceedings of the 2015 IEEE/ACM 8th International Conference on Utility and Cloud Computing. Piscataway, NJ: IEEE, 2015: 391-396.

[16] 袁玉倩,胡曉惠.基于QoS真實性與工作流模型的Web服務(wù)選擇[J].北京航空航天大學(xué)學(xué)報,2011,37(4):390-394.(YUAN Y Q, HU X H. Web service selection approach based on the authenticity of QoS data and workflow mode [J]. Journal of Beijing University of Aeronautics and Astronautics, 2011, 37(4): 390-394.)

[17] BETZLER N, FELLOWS M R, GUO J, et al. Fixed-parameter algorithms for Kemeny rankings [J]. Theoretical Computer Science, 2009, 410(45): 4554-4570.

[18] BALTRUNAS L, MAKCINSKAS T, RICCI F. Group recommendations with rank aggregation and collaborative filtering [C]// Proceedings of the Fourth ACM Conference on Recommender Systems. New York: ACM, 2010: 119-126.

[19] BIDGOLY A J, LADANI B T. Quantitative verification of beta reputation system using PRISM probabilistic model checker [C]// ISCISC 2013: Proceedings of the 2013 10th International ISC Conference on Information Security and Cryptology. Piscataway, NJ: IEEE, 2013: 1-6.

[20] NEATH A A, CAVANAUGH J E, WEYHAUPT A G. Model evaluation, discrepancy function estimation, and social choice theory [J]. Computational Statistics, 2015, 30(1): 231-249.

[21] 粟超.基于排序集成的自動術(shù)語識別方法[J].計算機應(yīng)用與軟件，2012，29(1):196-198.(SU C. Rank aggregation-based automatic term recognition [J]. Computer Applications and Software, 2012, 29(1): 196-198.)

[22] KEMENY J G. Mathematics without numbers [J]. Daedalus, 1959, 88(4): 577-591.

[23] ALI A, MEILA M. Experiments with Kemeny ranking: what works when?[J]. Mathematical Social Sciences, 2012, 64(1): 28-40.

[24] 吳祥標(biāo).Kemeny社會選擇函數(shù)的0- 1規(guī)劃算法[J].遵義師范學(xué)院學(xué)報,2014,16(1):81-83.(WU X B. 0- 1 programming algorithm of Kemeny social choice function [J]. Journal of Zunyi Normal College, 2014, 16(1): 81-83.)

[25] 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, 2016, 59:88-94.

[26] 許海玲，吳瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學(xué)報，2009，20(2):350-362.(XU H L, WU X, LI X D, et al. Comparison study of Internet recommendation system [J]. Journal of Software, 2009, 20(2): 350-362.)

This work is partially supported by the National Natural Science Foundation of China (61462056, 71161015, 81560296), the Applied Fundamental Research Project of Yunnan Province (2014FA028, 2014FB133).

LIWei, born in 1990, M. S. candidate. His research interests include service computing, intelligent decision.

FUXiaodong, born in 1975, Ph. D., professor. His research interests include service computing, decision theory and method, software engineering.

LIULi, born in 1979, Ph. D., associate professor. Her research interests include service computing, smart home.

LIULijun, born in 1978, M. S., lecturer. His research interests include service computing, medical information system.

Onlineserviceevaluationbasedonsocialchoicetheory

LI Wei1, FU Xiaodong1,2*, LIU Li1, LIU Lijun1

(1.FacultyofInformationEngineeringandAutomation,KunmingUniversityofScienceandTechnology,KunmingYunnan650500,China;2.AviationCollege,KunmingUniversityofScienceandTechnology,KunmingYunnan650500,China)

The inconformity of user evaluation standard and preference results in unfair comparability between online services in cyberspace, thereby the users are hardly to choose satisfactory online services. The ranking method to calculate the online service quality based on social choice theory was proposed. First, group preference matrix was built according to the user-service evaluation matrix given by users; second, 0- 1 integer programming model was built based on group preference matrix and Kemeny social choice function; at last, the optimal service ranking results could be obtained by solving this model. The individual preferences were aggregated to group preference in the proposed method; the decision was consistent with the majority preference of the group and maximum consistency with the individual preference. The proposed method’s rationality and effectiveness were verified by theoretical analysis and experiment results. The experimental results show that the proposed method can solve the incomparability between online services, realize the online service quality ranking, effectively resisted the recommendation attacks. So it has strong anti-manipulation.

online service; social choice theory; Kemeny function; service ranking; group decision

TP301.6; TP18

:A

2016- 12- 16;

:2016- 03- 05。

國家自然科學(xué)基金資助項目(61462056, 71161015, 81560296);云南省應(yīng)用基礎(chǔ)研究計劃項目(2014FA028, 2014FB133)。

李威(1990—)，男，湖北荊州人，碩士研究生，主要研究方向：服務(wù)計算、智能決策； 付曉東(1975—)，男，云南鎮(zhèn)雄人，教授，博士，CCF高級會員，主要研究方向：服務(wù)計算、決策理論與方法、軟件工程； 劉驪(1979—)，女，重慶人，副教授，博士，主要研究方向：服務(wù)計算、智能家居； 劉利軍(1978—)，男，河南輝縣人，講師，碩士，主要研究方向：服務(wù)計算、醫(yī)療信息系統(tǒng)。

1001- 9081(2017)07- 1983- 06

10.11772/j.issn.1001- 9081.2017.07.1983