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

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

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

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

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

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

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

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

0 引言

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

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

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

1 相關(guān)研究

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

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

2 問題描述

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

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

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

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

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

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

3)公平性(中性)。若每個(gè)用戶對(duì)兩個(gè)服務(wù)作相反評(píng)價(jià)時(shí),群體最優(yōu)服務(wù)排序的結(jié)果也要作相反選擇；公平性是對(duì)在線服務(wù)的公平性，它防止用戶偏袒某一在線服務(wù)，因?yàn)樗ＷC在每個(gè)用戶都對(duì)兩個(gè)在線服務(wù)作相反選擇時(shí)，那排序結(jié)果應(yīng)作相反的選擇，亦即社會(huì)選擇機(jī)制應(yīng)同樣對(duì)待所有在線服務(wù)。

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

(2)

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

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

(3)

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

3.1 基于Kemeny社會(huì)選擇函數(shù)的在線服務(wù)評(píng)價(jià)

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

3.1.1 Kemeny函數(shù)

(4)

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

(5)

即對(duì)任意P均滿足：

fk(P)≤fk(P*)

(6)

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

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

(7)

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

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

(8)

約束于:

(9)

3.2 方法過程描述

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

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

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

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

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

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

4 評(píng)價(jià)模型理論分析

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

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

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

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

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

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

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

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

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

5.1 有效性實(shí)驗(yàn)

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

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

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

5.2 一致性實(shí)驗(yàn)

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

圖1 不同方法的一致性對(duì)比

5.3 公平性實(shí)驗(yàn)

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

5.4 抗操縱性和抵制推薦攻擊實(shí)驗(yàn)

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

表2 初始評(píng)價(jià)與相反評(píng)價(jià)的Kemeny值對(duì)比

圖2 不同方法的抗操縱性對(duì)比

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

圖3 抵制惡意攻擊問題

6 結(jié)語

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

References)

[1] 王玉祥,喬秀全,李曉峰,等.上下文感知的移動(dòng)社交網(wǎng)絡(luò)服務(wù)選擇機(jī)制研究[J].計(jì)算機(jī)學(xué)報(bào),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].計(jì)算機(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)境下基于可信評(píng)價(jià)的云服務(wù)選擇[J].計(jì)算機(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ù)測方法的移動(dòng)用戶偏好預(yù)測方法[J].電子與信息學(xué)報(bào),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真實(shí)性與工作流模型的Web服務(wù)選擇[J].北京航空航天大學(xué)學(xué)報(bào),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] 粟超.基于排序集成的自動(dòng)術(shù)語識(shí)別方法[J].計(jì)算機(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社會(huì)選擇函數(shù)的0- 1規(guī)劃算法[J].遵義師范學(xué)院學(xué)報(bào),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é)報(bào)，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é)基金資助項(xiàng)目(61462056, 71161015, 81560296);云南省應(yīng)用基礎(chǔ)研究計(jì)劃項(xiàng)目(2014FA028, 2014FB133)。

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

1001- 9081(2017)07- 1983- 06

10.11772/j.issn.1001- 9081.2017.07.1983