基于Kendall tau距離的在線服務信譽度量方法

鄭蘇蘇 付曉東,2 岳 昆 劉 驪 劉利軍 馮 勇

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

隨著互聯網的發(fā)展和普及，傳統(tǒng)商業(yè)環(huán)境向開放、共享、多元的面向在線服務方式轉化.在線服務在電子商務、企業(yè)經營、管理等領域發(fā)揮越來越重要的作用.同時，隨著互聯網上可供用戶選擇的在線服務越來越多，用戶也需要花費更多的時間和精力來尋找自己需要的服務[1-2]：首先，龐大的在線服務數量使得用戶不可能與每個在線服務具有交互的經驗，用戶不可能獲得每個在線服務的完整信息；其次，由于網絡環(huán)境下允許匿名交互而彼此之間又不直接接觸，某些用戶或在線服務提供者可能提供不真實的服務信息[3-4].因此，用戶通常需要借助以第三方觀點為基礎形成的在線服務信譽為輔助進行服務選擇.

信譽是服務若干信用行為累積的結果，對于在線服務選擇起著重要的作用[5].一種客觀的在線服務信譽度量方法可有效地輔助用戶進行在線服務的優(yōu)劣選擇決策.現有的在線服務信譽度量方法均假設所有用戶根據相同的標準來評價服務，而未考慮到用戶因主觀偏好導致的評價準則不一致的問題[6].然而，受到自身習慣、生活經驗和消費歷史的影響，用戶對在線服務評價的標準不可能完全相同.比如，有些用戶傾向于給服務較高的評分，有些用戶傾向于給服務較低的評分，導致即使本質表現相同的服務也會得到不同的評分[7].因此，不同用戶對同一服務的評分不可比較，不考慮用戶評分可比較性得到的服務信譽也不具備公正的可比較性.此外，一些用戶和在線服務提供者為了獲取不當利益，通過對某些服務提高評分或降低評分來達到操縱服務信譽的目的[8].利用這種信譽進行服務選擇會對用戶產生誤導，使用戶難以獲取真正需要的服務.

為解決上述問題，本文提出了一種基于Kendall tau距離[9]的在線服務信譽度量方法，方法不需要假定用戶具有相同的評價準則，考慮了用戶對不同服務之間的關系，將與用戶-服務評分矩陣Kendall tau距離最小的信譽向量作為最終的服務信譽，有效地避免了在線服務信譽不可比較的問題.

1 相關工作

近年來，國內外學者圍繞更加精確、理性的在線服務信譽度量展開了一系列研究，目前的在線信譽度量方法主要有[1,10]：平均法模型、累加法模型、基于貝葉斯網絡的信譽模型、離散的信譽模型、基于模糊邏輯的信譽模型、基于鏈狀的信譽模型和基于證據理論的信譽模型等.文獻[11]指出服務信譽度量可以分為2類：1)通過用戶評分計算服務信譽；2)通過綜合多種服務質量因素計算服務信譽，如響應時間、可用性和吞吐量等.

通過用戶評分計算服務信譽的方法在目前的電子商務平臺應用廣泛[1].eBay網站采用求和法(SUM)，將所有用戶對服務的評分進行求和得到服務信譽，用戶根據服務信譽對在線服務做出選擇.Amazon網站則使用平均法(AVG)，通過計算所有用戶對服務評分的平均值得到其服務信譽.文獻[12]提出了一種基于低階矩陣分解的信譽估計方法，通過用戶對項目的評分計算項目的信譽;文獻[3]提出了一種計算評估者信譽的方法，根據評估者的評分歷史和其他評估者對該評估者的評分自動計算評估者的聲譽，并結合這些聲譽來生成關于評分對象的增值信息;文獻[13]提出了一種基于上下文的Web服務信譽測量方法，根據用戶的上下文對評分進行分類，然后根據用戶評分差異獲得用戶的內部評分，最后采用基于用戶的協同過濾衡量每個Web服務的聲譽.

通過用戶評分計算服務信譽只考慮用戶對服務的主觀感受并未考慮到影響服務信譽的其他因素[14]，比如服務質量(quality of service, QoS)、用戶歷史行為、社交網絡關系等.文獻[15]提出一種基于服務質量相似度的Web服務信譽度量模型，通過比較服務質量公告值和實際值的相似性來進行Web服務信譽評估.文獻[16]提出一種用QoS感知Web服務選擇中信譽度評估的方法，通過反饋核查、校正和檢測這3個信譽度評估模塊對服務的信譽度進行評估.文獻[17]提出了一種基于云的評價方法，通過評估服務消費者的歷史行為，并考慮評分相似度以生成評分質量云，進而利用云模型的參數進行服務信譽評估.文獻[18]提出了一種信譽管理系統(tǒng)，基于N元語法學習方法對社交媒體數據進行分析，以測量給定公司的聲譽.文獻[19]提出隱馬爾可夫模型(hidden Markov model, HMM)來預測服務提供商的聲譽，當客戶的反饋不容易獲得時，可以通過HMM綜合一整套質量參數獲得Web服務的聲譽.

上述研究在進行服務信譽度量時都假設所有用戶的偏好相同，并且他們能按照一致的評價準則對在線服務進行客觀的評價[1].然而，在開放的在線網絡環(huán)境中，用戶對在線服務的偏好不可能完全一致，甚至可能出現矛盾和沖突.因此，上述研究提出的信譽度量方法忽視了用戶評價準則不一致的問題，難以客觀地反映在線服務的真實信譽.考慮到以上研究中存在的不足，本文充分考慮了用戶的主觀偏好不一致性，在不假設用戶評價準則相同的情況下，提出一種基于Kendall tau距離的在線服務信譽度量方法.方法不考慮用戶評分強度，而是將用戶對不同服務的評分轉化為用戶對不同服務之間的偏好關系，將這些偏好關系進行集結，最終形成服務信譽.通過考慮用戶對不同服務評分的關系，使得到的在線服務信譽具備可比較性.最后，本文通過理論分析與實驗驗證了方法的合理性和有效性.

2 問題描述

2.1 問題定義

為解決用戶對服務評價準則不一致導致的服務信譽不具備可比較性的問題，本文首先對在線服務信譽度量問題進行定義.

定義1. 集合U={u1,u2,…,ux}為所有用戶的集合，集合S={s1,s2,…,sy}為所有在線服務的集合，集合C={c1,c2,…,ch}為用戶對在線服務的評分等級.其中，x為用戶的個數，y為在線服務的個數，用戶對在線服務的評分等級共有h種.

定義2. 評分向量ri=(ri 1,ri 2,…,ri p,…,riy)表示用戶ui對所有服務的評分信息，ri p表示用戶ui對服務sp的評分并體現用戶ui對服務sp的滿意程度.ri p越大則表示ui對sp越滿意.ri p>ri q表示用戶ui認為服務sp優(yōu)于sq；ri p

定義3. 所有用戶對服務的評分信息用矩陣R=(ri p)x×y表示，評分向量ri(i=1,2,…,x)的集合用G表示，即G={r1,r2,…,rx}.

定義4. 服務集合S={s1,s2,…,sy}的信譽用信譽向量rz=(rz1,rz2,…,rzy)表示，rz1,rz2,…,rzy分別表示服務s1,s2,…,sy的信譽值，且rz1,rz2,…,rzy屬于集合C.

2.2 舉例說明

例1. 假設有3個用戶(u1,u2,u3)共同對4個在線服務(s1,s2,s3,s4)進行評分,用戶-服務評分矩陣R=(ri p)3×4如表1所示.其中評分ri p表示用戶對在線服務的滿意程度，采用電子商務評價機制中常用的5個評分等級，1～5分別表示很不滿意、不滿意、一般、滿意和很滿意.ri p=0表示該用戶未與該服務產生交互或未對服務進行評分.

Table1 Ratings Matrix of User-Service表1 用戶-服務評分矩陣表

由表1可見，對于同一服務s4，用戶u1對服務s4給出5分的評分，用戶u2對服務s4給出3分的評分，并不能說明服務s4為用戶u1提供的服務優(yōu)于為用戶u2提供的服務.由于不同用戶對在線服務的偏好不同，面對表現相同的在線服務，不同用戶也可能給出不同的評分.而對于同一服務s2，用戶u1和用戶u2都給出1分的評分，并不能說明服務s2對用戶u1和用戶u2的表現相同.因此即使服務表現不同，不同用戶也可能給出相同的評分.

傳統(tǒng)的服務信譽度量方法沒有考慮到由于偏好不同導致用戶評價準則不一致的問題.比如，平均法假定不同用戶對在線服務的評價準則相同，通過計算所有用戶對服務評分的平均值得到其服務信譽，得到的信譽向量為ra=(1.5,1.3,3.7,3.7).從信譽向量ra中可以看出平均法計算得到的服務s1優(yōu)于服務s2，在基于信譽進行服務選擇時，用戶應該選擇服務s1.然而在真實的在線網絡環(huán)境中，不同用戶對服務的偏好是不同的，即使服務s1,s2的表現相同，它們得到的評分依然可能不同，進一步導致最終得到的信譽不一樣，也就是說服務s1,s2的信譽事實上不具有可比較性.其次，從信譽向量ra中可以看出服務s3,s4的信譽相同，而表1中所有用戶對服務s3,s4的評分均不相同，因此根據平均法計算得到的信譽不具備可比較性，不能體現出用戶的偏好.此外，如果將用戶u1對服務s2的評分提高至5分，根據平均法得到的服務s2的信譽將提高至1.6分，并且對其他服務的信譽沒有影響，使得服務s2的信譽大大提升，抗操縱性較弱.因此，本文提出一種基于Kendall tau距離的在線服務信譽度量方法，避免了用戶評分準則不一致導致的在線服務信譽不可比較的問題，同時提高了信譽度量方法的抗操縱性.

3 基于Kendall tau距離的在線服務信譽度量

由于用戶評價準則不一致，不同用戶的評分不具備可比較性，從而根據不同用戶的評分計算得到的服務信譽也不具備可比較性.而對于同一理性用戶，其對不同服務的評分是可以比較的.例1中用戶u1對服務s3給出2分的評分，對服務s4給出5分的評分，可以推斷用戶u1認為服務s4優(yōu)于服務s3，因此，通過考慮同一用戶對不同服務評分之間的關系可以建立可比較的信譽度量方法.

基于以上分析，本文針對用戶評價準則不一致導致的在線服務信譽不可比較的問題，提出一種基于Kendall tau距離的在線服務信譽度量方法.Kendall tau距離通過計算2個排列之間的逆序數來衡量2個排列π和σ之間的差異程度[20]，計算方法為

K(π，σ)=|(i,j):iπ[j])∨
(π[i]>π[j]∧σ[i]<π[j])|,

(1)

其中，π[i]和σ[i]分別表示元素i在排列π和σ中的排名.從式(1)可以看出，排列π和σ之間的Kendall tau距離為元素i和元素j在2個排列中的排列順序不一致的數量.

我們將Kendall tau距離重新定義以測量2個服務評分向量之間用戶對成對服務偏好不一致性的數量，距離越小，2個服務評分向量越一致[21-22].本文通過Kendall tau距離比較同一用戶對不同服務的評分，將與用戶-服務評分矩陣距離最小的信譽向量作為與所有用戶偏好最一致的服務信譽.由于同一用戶的評分是可以比較的，因而可以有效地避免用戶評價準則不一致導致的在線服務信譽不可比較的問題.同時，通過考慮用戶對不同服務評分的關系，提高了信譽度量方法的抗操縱性.此外，本文采用模擬退火算法(simulated annealing, SA)尋找最優(yōu)信譽向量，有效地避免了陷入局部最優(yōu)的缺點，保證了信譽度量方法的效率.

3.1 基于Kendall tau的評分向量距離度量

定義5. 距離指標K(ri,rj)用來表示2個服務評分向量ri=(ri1,…ri p,…,ri y),rj=(rj1,…rj q,…,rj y)之間的Kendall tau距離.

我們用K(ri,rj)表示ri,rj之間的偏好一致性：K(ri,rj)越小，表示ri,rj之間的偏好一致性越大；K(ri,rj)越大，表示ri,rj之間的偏好一致性越?。籏(ri,rj)=0表示ri,rj之間的偏好完全一致.

計算K(ri,rj)首先要計算對于每2個服務ri,rj之間的距離，對于2個不同的服務sp,sq∈S(p≠q)，它們在2個服務評分向量ri,rj之間的距離表示為

(2)

例1中r11=r12并且r21>r22，此時Ks1,s2(r1,r2)=1，表示從評分向量r1,r2可以看到，用戶u1,u2對服務s1,s2具有不同的偏好.另一方面，由于r11

對服務集合S={s1,s2,…,sy}，計算2個服務評分向量ri,rj之間的距離可通過計算針對ri,rj的距離之和得到.即：

(3)

例1中2個評分向量r1,r2之間的距離K(r1,r2)=Κs1,s2(r1,r2)+Ks1,s3(r1,r2)+Ks1,s4(r1,r2)+Ks2,s3(r1,r2)+Ks2,s4(r1,r2)+Ks3,s4(r1,r2)=2，表示評分向量r1,r2之間用戶對2對不同服務的偏好不一致.其中Ks1,s2(r1,r2)=1，表示用戶u1和u2對服務s1和s2具有不同的偏好.r13r24，此時Ks1,s4(r1,r2)=1，表示評分向量r1,r2體現出用戶u1,u2對服務s3,s4具有不同的偏好.

3.2 基于Kendall tau距離的信譽度量

Kendall tau距離是衡量評分向量之間的成對分歧數量的指標，距離越小，2個評分向量越一致.本文服務信譽度量方法的核心是找到一個與所有用戶偏好最一致的信譽向量，即與用戶-服務評分矩陣R之間距離最小的信譽向量.因此我們首先根據距離指標K(ri,rj)的定義計算信譽向量rz和用戶-服務評分矩陣R之間的距離.

定義6. 距離指標K(rz,R)用來表示信譽向量rz=(rz1,rz2,…,rzy)和用戶-服務評分矩陣R之間的Kendall tau距離.

K(rz,R)表示信譽向量rz和用戶-服務評分矩陣R之間的偏好一致性：K(rz,R)越小，表示rz,R之間的偏好一致性越大；K(rz,R)越大，表示rz,R之間的偏好一致性越?。籏(rz,R)=0表示rz,R之間的偏好完全一致.

對于y個在線服務、h個評分等級，有hy種可能的信譽向量，如果一一計算每個可能的信譽向量與用戶-服務評分矩陣R中每個評分向量的距離之和，計算量龐大且運行時間長，因此本方法預先統(tǒng)計用戶-服務評分矩陣R中ri p>ri q，ri p=ri q，ri pri q，用Vp p表示ri p=ri q，用Vq p表示ri pri q，ri p=ri q，ri p

計算K(rz,R)首先要計算對于每2個服務rz,R之間的距離，對于2個不同的服務sp,sq∈S(p≠q)，它們在信譽向量rz與用戶-服務評分矩陣R之間的距離為

(4)

對服務集合S={s1,s2,…,sy}，rz與用戶-服務評分矩陣R之間的距離通過計算rz,R之間距離的和得到.即：

(5)

計算例1中對服務集合S={s1,s2,s3,s4}信譽向量ra與用戶-服務評分矩陣R之間的距離.首先統(tǒng)計|Vp q|，|Vp p|，|Vq p|的數量；然后根據式(4)計算得出對于每2個服務在ra,R之間的距離；最后求和得到K(ra,R)=4，表示ra,R之間對成對服務偏好不一致的數量為4.

基于以上分析，確定信譽度量最優(yōu)化目標函數為

(6)

3.3 基于模擬退火算法尋找最優(yōu)信譽向量

尋找最優(yōu)信譽向量是一個NP難問題[21]，解空間規(guī)模隨在線服務數量y的增大呈指數增加,利用傳統(tǒng)的窮盡搜索方法尋找最優(yōu)向量需要計算每一種可能的信譽向量與用戶-服務評分矩陣之間的距離，并將距離最小的信譽向量作為服務信譽，計算量龐大且對存儲空間需求很大.文獻[21]提出用遺傳算法(genetic algorithm， GA)解決此類優(yōu)化問題.然而由于遺傳算法的局限性，容易產生“過早收斂”的問題，即很快收斂到局部最優(yōu)解，而不是全局最優(yōu)解[23].模擬退火算法是一種隨機搜索方法，在尋優(yōu)過程中具有概率突跳性，除了可以接受優(yōu)化解外，還可用Metropolis準則有限度地接受較差解，并且接受較差解的概率慢慢趨向于0.由于在整個解空間內取值的隨機性，可以改善陷入局部最優(yōu)解的缺陷，使算法盡可能地收斂于全局最優(yōu)解，已經被證明可以在多項式時間內解決復雜的組合優(yōu)化問題[24-25].因此本文將采用模擬退火方法作為尋優(yōu)算法，尋找最優(yōu)信譽向量.步驟為

① http://www.grouplens.org/node/73

步驟1. 設定模擬退火算法的參數，包括初始溫度t0、終止溫度te、退溫系數α、Markov鏈長L.令終止條件為：溫度t下連續(xù)m次迭代過程中的新解都未被接受或者溫度降為終止溫度，滿足其中任一條件則計算終止.

步驟2. 設定初始解r0，從解空間M中隨機選取1個可能解作為初始解r0，r0=(r01,r02,…,r0y)，計算r0的目標函數值K(r0,R).

步驟3. 隨機改變初始解r0中的部分元素值(如改變r02和r04的值)，產生1個位于解空間M的新解rn，rn=(rn1,rn2,…rny)，計算rn的目標函數值K(rn,R).

步驟4. 計算rn的目標函數K(rn,R)與r0的目標函數K(r0,R)之間的差值Δk，Δk=K(rn,R)-K(r0,R).

步驟5. 新解的接受概率為

(7)

其中，t為當前溫度，降溫后的溫度T=αt.新解的接受遵循Metropolis準則：當Δk<0時，接受rn作為當前最優(yōu)解；當Δk>0時，給出一個(0,1)區(qū)間上的隨機數β，在新解的接受概率P>β時，接受rn作為當前最優(yōu)解，否則不接受rn，此時初始解r0實現了一次迭代.在當前溫度下共進行L次迭代，若迭代過程中接受了新的解，則不滿足終止條件，根據T=αt降低溫度.

步驟6.令當前溫度t=T，重復步驟3～5，直到滿足終止條件，此時停止計算，求得的當前解r*為最優(yōu)解.

步驟7.將得到的最優(yōu)解r*作為用戶-服務評分矩陣R的服務信譽.

由于退火參數對求解優(yōu)化問題有很大影響，因此我們設置合理的退火參數，根據不同的服務和用戶規(guī)模設置算法終止條件.終止條件之一為溫度t下連續(xù)m迭代過程中的新解都未被接受.在用戶和服務規(guī)模較小時，由于運行速度快，可以設置較大的m值以保證得到最優(yōu)信譽向量；隨著用戶和服務規(guī)模越來越大，可能產生的新解rn越來越多，此時m值可以適當減小，以提高算法的尋優(yōu)效率.

為了盡可能地獲得最優(yōu)解，我們在算法中加入補充搜索環(huán)節(jié)，在得到最優(yōu)解r*后，可以將r*作為初始解r0進行新一輪的尋優(yōu)過程，得到與用戶-服務評分矩陣距離更小的最優(yōu)信譽向量.

將以上步驟應用到3.2節(jié)例1中，得到最優(yōu)信譽向量為r*=(1,1,5,4)，r*與用戶-服務評分矩陣R之間的Kendall tau距離為K(r*,R)=2.而用平均法得到的信譽向量ra=(1.5,1.3,3.7,3.7)，與用戶-服務評分矩陣R之間的Kendall tau距離為K(ra,R)=4.由此可見，本文方法得到的信譽向量與平均法相比，與用戶-服務評分矩陣間的距離更小，從而與所有用戶具有更大的偏好一致性.此外，如果將用戶u1對服務s2的評分提高至5分，根據本方法得到的最優(yōu)信譽向量為r*=(2,3,5,4)，對服務s2操縱不僅提高了s2的信譽，服務s1的信譽也會提升，因此本方法具有更強的抗操縱性.

4 實驗結果及分析

根據第3節(jié)提到的基于Kendall tau距離的在線服務信譽度量方法，設計實現了在線服務信譽度量方法，用于在線服務信譽度量，并對評價數據進行驗證.實驗環(huán)境為PC機，Windows 8系統(tǒng)、Core i5處理器、8 GB內存.

為驗證本文信譽度量方法的有效性和效率，我們采用MovieLens①數據集，包含1 682部電影、943個用戶以及100 000條左右的評分(1～5)，每個用戶至少對20部電影進行過評分.由于用戶對電影的評分稀疏，為確保信譽度量的高效性，如果每對服務中至少有一個服務未被評分，實驗中將忽略這對服務的比較.由于平均法易于理解并且被廣泛應用于計算服務信譽[1]，因此我們將平均法作為本文的主要對比方法.文獻[21]提出用遺傳算法解決信譽計算中的組合優(yōu)化問題，并通過理論及實驗證明了其合理性.遺傳算法也是一種有效的近似優(yōu)化算法，為了測試本文模擬退火算法的性能，實驗對比了遺傳算法和本文算法的優(yōu)化效果和運行效率.其中，用r*表示用本文方法求得的信譽向量，用ra表示用平均法求得的信譽向量，用rg表示用遺傳算法求得的信譽向量.

在實驗中，我們需要設置合理的模擬退火參數：初始溫度、終止溫度、退溫系數和Markov鏈長.如果這些參數設置得太小，不能進行高質量的尋優(yōu)計算，很難得到最優(yōu)信譽向量；如果設置得太大，則運行時間過長，迭代運算速度慢，浪費大量不必要的計算資源.為了提高算法得到最優(yōu)信譽向量的可靠性，實驗過程中將初始溫度和終止溫度設置為常用的參數[26]，t0=100,te=1，并且設置退溫系數α=0.9，Markov鏈長L=10.

4.1 有效性實驗

Fig. 1 Consistency verification圖1 一致性驗證

根據式(4)，信譽向量與用戶-服務評分矩陣R的Kendall tau距離越小，表示該信譽向量與所有用戶的分歧越小，與所有用戶的偏好越一致，因此將與用戶-服務評分矩陣R的Kendall tau距離最小的信譽向量作為服務信譽是合理的.因此，我們用Kendall tau距離驗證方法的有效性.實驗模擬了200～800個用戶和10～50個在線服務，在不同用戶數量x和不同服務數量y下，記錄依據本文方法得到的最優(yōu)信譽向量r*與用戶-服務評分矩陣R間的Kendall tau距離K(r*,R)、平均法得到的信譽向量ra與用戶-服務評分矩陣R的Kendall tau距離K(ra,R)，以及依據文獻[21]中的遺傳算法得到的最優(yōu)信譽向量rg與用戶-服務評分矩陣R的Kendall tau距離K(rg,R)，如圖1所示.

由圖1可見，隨著用戶數量和服務數量的增加，K(r*,R)，K(ra,R)，K(rg,R)都會增加.說明不可能得到與所有用戶偏好完全一致的信譽向量，并且服務和用戶規(guī)模越大，信譽向量與所有用戶的偏好不一致性越大.這符合社會選擇理論中的阿羅定理，當眾多的社會成員具有不同的偏好時，不可能存在令所有人都滿意的結果[27].

此外，算法比較記錄了不同樣本規(guī)模下K(r*,R),K(ra,R) 的差值以及K(r*,R),K(rg,R)的差值，K(r*,R)-K(ra,R)如圖2(a)所示，K(r*,R)-K(rg,R)如圖2(b)所示：

Fig. 2 Consistency comparison of reputation measurement methods圖2 信譽度量方法一致性比較

由圖2(a)可見，在同樣的服務數量和用戶規(guī)模下，K(r*,R)-K(ra,R)始終小于0，K(r*,R)始終小于K(ra,R)，并且隨著服務數量和用戶規(guī)模的增大，K(ra,R),K(r*,R)的差值越來越大.說明根據本方法得到的信譽向量與用戶-服務評分矩陣R之間的Kendall tau距離更小，在服務和用戶規(guī)模一定時，采用本方法計算服務信譽比平均法更為合理，得到的信譽更符合用戶的偏好.

由圖2(b)可見，在用戶數量為200、服務數量為10時，K(r*,R)-K(ra,R)=0.說明在用戶服務規(guī)模較小時，模擬退火和遺傳算法都能找到最優(yōu)信譽向量.然而隨著服務數量和用戶規(guī)模的增大，K(rg,R)與K(r*,R)的差值越來越大，模擬退火算法總能找到比遺傳算法更好的解，得到的信譽向量與R之間的Kendall tau距離更小，與所有用戶的偏好更為一致.

Fig. 3 Verification of majority rule圖3 多數準則驗證

4.2 多數準則

服務信譽應滿足大多數人的偏好，因此我們利用經濟學理論中的多數準則驗證方法有效性.這里的多數準則指的是如果存在認為服務si優(yōu)于服務sj的用戶多于認為服務sj優(yōu)于服務si的用戶，那么根據多數準則，由服務信譽度量方法得到的服務信譽應體現si優(yōu)于sj.我們使用m(ri,R)表示信譽向量中不符合多數準則的數量，即ri p|Vq p|.實驗比較記錄了本文方法、平均法和遺傳算法得到的信譽向量中不符合多數準則的數量m(r*,R)，m(ra,R)，m(rg,R)，如圖3所示.

由圖3可見，無論是本文方法還是平均法得到的信譽向量中，ri p|Vq p|的情況都會出現，同時m(r*,R),m(ra,R)都會隨著服務數量的增加而不斷增大，但是并不會因為用戶數量的增加而明顯增大，因為用戶數量的增加不只可能將|Vp q|>|Vq p|改變?yōu)閨Vp q|<|Vq p|，也可能將|Vp q|<|Vq p|改變?yōu)閨Vp q|>|Vq p|.

此外，我們還記錄了不同樣本規(guī)模下m(r*,R),m(ra,R) 的差值以及m(r*,R),m(rg,R)的差值，m(r*,R)-m(ra,R)如圖4(a)所示，m(r*,R)-m(rg,R)如圖4(b)所示:

Fig. 4 Comparison of majority rule of reputation measurement methods圖4 信譽度量方法多數準則比較

由圖4(a)可見，在不同用戶數量和服務數量的情況下,m(r*,R)-m(ra,R)始終小于0，即m(r*,R)始終小于m(ra,R).說明本文方法得到的信譽向量中ri p>ri q并且用戶-服務評分矩陣R中|Vp q|>|Vq p|的情況更少，比平均法更符合多數準則.

由圖4(b)可見，在用戶數量為200、服務數量為10時，m(r*,R)=0且m(rg,R)=0.說明在用戶服務規(guī)模較小時，模擬退火和遺傳算法得到的結果都能滿足多數準則；而當用戶和服務規(guī)模變大時，m(r*,R)在絕大多數情況下小于m(rg,R).模擬退火算法和遺傳算法的尋優(yōu)過程都具有隨機性，然而本文使用模擬退火算法得到的信譽向量比遺傳算法得到的信譽向量更符合多數準則.

4.3 抗操縱性

為了驗證該方法的操縱復雜性，隨機選擇3個在線服務，用戶數量為800，并對其中某一服務增加高評分評價，若根據該方法得到的服務信譽排名無明顯提升，則該方法具有較強的抗操縱性.假設有3個服務s1,s2,s3，有20%,40%,60%,80%,100%的用戶對評分進行操縱，這些用戶對服務s1的評分提高至5分，觀察3個服務信譽的變化.本文方法的信譽如圖5(a)所示，平均法的信譽如圖5(b)所示:

Fig. 5 Verification of manipulation resistance performance圖5 抗操縱性能驗證

根據圖5(a)所示，隨著操縱評分數量的增加，根據本文方法得到的服務s1的信譽值先提高再降低然后不變，并且當服務s1的信譽改變時，服務s2,s3的信譽也會隨之改變.而根據圖5(b)所示，根據平均值方法得到的服務s1的信譽值明顯提升，但并不會改變服務s2,s3的信譽，從而實現了對服務s1的操縱.因此本方法更具抗操縱性.

4.4 性能測試

為驗證該方法的效率，實驗模擬了200～800個用戶和10～50個在線服務，在不同樣本規(guī)模下算法記錄了系統(tǒng)每次進行服務信譽度量的運行時間，如圖6所示.同時，比較了在800個用戶和10～50個在線服務規(guī)模下模擬退火算法、平均法、遺傳算法和整數規(guī)劃算法(mixed integer programming， MIP)的運行時間，如圖7所示.整數規(guī)劃算法計算所有可能的信譽向量的目標函數值，并將目標函數值最小的信譽向量作為最優(yōu)信譽向量輸出.

Fig. 6 Runtime of different sample sizes圖6 不同樣本規(guī)模下的運行時間

根據圖6所示，隨著服務數量的增加，運行時間不斷增加，即算法的效率逐漸降低.但是相同服務數量下，運行時間并不隨著用戶數量的增多而變長，這是因為，在服務數量一定時,只需預先計算|Vp q|,|Vp p|,|Vq p|的數量，之后再用式(3)計算信譽向量與用戶-服務評分矩陣之間的距離，運行時間與用戶數量無關.因此，在服務數量一定時，本文方法可以有效地提升信譽度量的效率.

Fig. 7 Runtime of SA, MIP, AVG, and GA圖7 SA，MIP，AVG，GA方法的運行時間

根據圖7所示，當服務數量較少時，模擬退火算法、平均法、遺傳算法和整數規(guī)劃算法的運行時間并無太大差別.但當服務數量超過9時，整數規(guī)劃算法的運行時間隨著服務數量的增加呈指數增長，遠遠超過模擬退火算法的運行時間.在用戶數量小于11時，本文的模擬退火算法獲得的服務信譽與整數規(guī)劃算法相比并無差別，對于大規(guī)模的用戶和服務而言，模擬退火算法比整數規(guī)劃算法效率更高.此外，模擬退火算法與遺傳算法的運行時間并無明顯差距，但模擬退火算法得到的信譽向量優(yōu)于遺傳算法得到的信譽向量.可見模擬退火算法在保證得到最優(yōu)解的同時，克服了尋優(yōu)速度慢的缺點.并且，與平均法相比，雖然本文方法的運行時間較長，但對信譽度量方法進行操縱比平均法消耗時長多，抗操縱性更強.

5 結 語

本文提出一種基于Kendall tau距離的在線服務信譽度量方法，以解決由于用戶評價準則不一致導致的在線服務信譽不可比較的問題.方法采用Kendall tau距離指標來衡量2個評分向量的差異，然后將信譽度量轉化為最優(yōu)化問題，再采用模擬退火算法尋找最優(yōu)信譽向量作為服務信譽，為在線服務的信譽度量提供了一種新的思路.理論分析及實驗驗證表明了該方法的有效性、抗操縱性以及高效性.本方法在信譽度量時只考慮了用戶對在線服務的評分值，未能全面考慮影響信譽的多種因素.因此下一步的工作將結合影響服務信譽的其他因素，研究更加精確的在線服務信譽度量方法.