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

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

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

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

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

1 相關(guān)工作

近年來(lái)，國(guó)內(nèi)外學(xué)者圍繞更加精確、理性的在線服務(wù)信譽(yù)度量展開(kāi)了一系列研究，目前的在線信譽(yù)度量方法主要有[1,10]：平均法模型、累加法模型、基于貝葉斯網(wǎng)絡(luò)的信譽(yù)模型、離散的信譽(yù)模型、基于模糊邏輯的信譽(yù)模型、基于鏈狀的信譽(yù)模型和基于證據(jù)理論的信譽(yù)模型等.文獻(xiàn)[11]指出服務(wù)信譽(yù)度量可以分為2類：1)通過(guò)用戶評(píng)分計(jì)算服務(wù)信譽(yù)；2)通過(guò)綜合多種服務(wù)質(zhì)量因素計(jì)算服務(wù)信譽(yù)，如響應(yīng)時(shí)間、可用性和吞吐量等.

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

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

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

2 問(wèn)題描述

2.1 問(wèn)題定義

為解決用戶對(duì)服務(wù)評(píng)價(jià)準(zhǔn)則不一致導(dǎo)致的服務(wù)信譽(yù)不具備可比較性的問(wèn)題，本文首先對(duì)在線服務(wù)信譽(yù)度量問(wèn)題進(jìn)行定義.

定義1. 集合U={u1,u2,…,ux}為所有用戶的集合，集合S={s1,s2,…,sy}為所有在線服務(wù)的集合，集合C={c1,c2,…,ch}為用戶對(duì)在線服務(wù)的評(píng)分等級(jí).其中，x為用戶的個(gè)數(shù)，y為在線服務(wù)的個(gè)數(shù)，用戶對(duì)在線服務(wù)的評(píng)分等級(jí)共有h種.

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

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

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

2.2 舉例說(shuō)明

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

Table1 Ratings Matrix of User-Service表1 用戶-服務(wù)評(píng)分矩陣表

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

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

3 基于Kendall tau距離的在線服務(wù)信譽(yù)度量

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

基于以上分析，本文針對(duì)用戶評(píng)價(jià)準(zhǔn)則不一致導(dǎo)致的在線服務(wù)信譽(yù)不可比較的問(wèn)題，提出一種基于Kendall tau距離的在線服務(wù)信譽(yù)度量方法.Kendall tau距離通過(guò)計(jì)算2個(gè)排列之間的逆序數(shù)來(lái)衡量2個(gè)排列π和σ之間的差異程度[20]，計(jì)算方法為

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

(1)

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

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

3.1 基于Kendall tau的評(píng)分向量距離度量

定義5. 距離指標(biāo)K(ri,rj)用來(lái)表示2個(gè)服務(wù)評(píng)分向量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之間的偏好完全一致.

計(jì)算K(ri,rj)首先要計(jì)算對(duì)于每2個(gè)服務(wù)ri,rj之間的距離，對(duì)于2個(gè)不同的服務(wù)sp,sq∈S(p≠q)，它們?cè)?個(gè)服務(wù)評(píng)分向量ri,rj之間的距離表示為

(2)

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

對(duì)服務(wù)集合S={s1,s2,…,sy}，計(jì)算2個(gè)服務(wù)評(píng)分向量ri,rj之間的距離可通過(guò)計(jì)算針對(duì)ri,rj的距離之和得到.即：

(3)

例1中2個(gè)評(píng)分向量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，表示評(píng)分向量r1,r2之間用戶對(duì)2對(duì)不同服務(wù)的偏好不一致.其中Ks1,s2(r1,r2)=1，表示用戶u1和u2對(duì)服務(wù)s1和s2具有不同的偏好.r13r24，此時(shí)Ks1,s4(r1,r2)=1，表示評(píng)分向量r1,r2體現(xiàn)出用戶u1,u2對(duì)服務(wù)s3,s4具有不同的偏好.

3.2 基于Kendall tau距離的信譽(yù)度量

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

定義6. 距離指標(biāo)K(rz,R)用來(lái)表示信譽(yù)向量rz=(rz1,rz2,…,rzy)和用戶-服務(wù)評(píng)分矩陣R之間的Kendall tau距離.

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

對(duì)于y個(gè)在線服務(wù)、h個(gè)評(píng)分等級(jí)，有hy種可能的信譽(yù)向量，如果一一計(jì)算每個(gè)可能的信譽(yù)向量與用戶-服務(wù)評(píng)分矩陣R中每個(gè)評(píng)分向量的距離之和，計(jì)算量龐大且運(yùn)行時(shí)間長(zhǎng)，因此本方法預(yù)先統(tǒng)計(jì)用戶-服務(wù)評(pí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

計(jì)算K(rz,R)首先要計(jì)算對(duì)于每2個(gè)服務(wù)rz,R之間的距離，對(duì)于2個(gè)不同的服務(wù)sp,sq∈S(p≠q)，它們?cè)谛抛u(yù)向量rz與用戶-服務(wù)評(píng)分矩陣R之間的距離為

(4)

對(duì)服務(wù)集合S={s1,s2,…,sy}，rz與用戶-服務(wù)評(píng)分矩陣R之間的距離通過(guò)計(jì)算rz,R之間距離的和得到.即：

(5)

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

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

(6)

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

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

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

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

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

步驟3. 隨機(jī)改變初始解r0中的部分元素值(如改變r(jià)02和r04的值)，產(chǎn)生1個(gè)位于解空間M的新解rn，rn=(rn1,rn2,…rny)，計(jì)算rn的目標(biāo)函數(shù)值K(rn,R).

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

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

(7)

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

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

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

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

為了盡可能地獲得最優(yōu)解，我們?cè)谒惴ㄖ屑尤胙a(bǔ)充搜索環(huán)節(jié)，在得到最優(yōu)解r*后，可以將r*作為初始解r0進(jìn)行新一輪的尋優(yōu)過(guò)程，得到與用戶-服務(wù)評(píng)分矩陣距離更小的最優(yōu)信譽(yù)向量.

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

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

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

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

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

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

Fig. 1 Consistency verification圖1 一致性驗(yàn)證

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

由圖1可見(jiàn)，隨著用戶數(shù)量和服務(wù)數(shù)量的增加，K(r*,R)，K(ra,R)，K(rg,R)都會(huì)增加.說(shuō)明不可能得到與所有用戶偏好完全一致的信譽(yù)向量，并且服務(wù)和用戶規(guī)模越大，信譽(yù)向量與所有用戶的偏好不一致性越大.這符合社會(huì)選擇理論中的阿羅定理，當(dāng)眾多的社會(huì)成員具有不同的偏好時(shí)，不可能存在令所有人都滿意的結(jié)果[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 信譽(yù)度量方法一致性比較

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

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

Fig. 3 Verification of majority rule圖3 多數(shù)準(zhǔn)則驗(yàn)證

4.2 多數(shù)準(zhǔn)則

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

由圖3可見(jiàn)，無(wú)論是本文方法還是平均法得到的信譽(yù)向量中，ri p|Vq p|的情況都會(huì)出現(xiàn)，同時(shí)m(r*,R),m(ra,R)都會(huì)隨著服務(wù)數(shù)量的增加而不斷增大，但是并不會(huì)因?yàn)橛脩魯?shù)量的增加而明顯增大，因?yàn)橛脩魯?shù)量的增加不只可能將|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 信譽(yù)度量方法多數(shù)準(zhǔn)則比較

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

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

4.3 抗操縱性

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

Fig. 5 Verification of manipulation resistance performance圖5 抗操縱性能驗(yàn)證

根據(jù)圖5(a)所示，隨著操縱評(píng)分?jǐn)?shù)量的增加，根據(jù)本文方法得到的服務(wù)s1的信譽(yù)值先提高再降低然后不變，并且當(dāng)服務(wù)s1的信譽(yù)改變時(shí)，服務(wù)s2,s3的信譽(yù)也會(huì)隨之改變.而根據(jù)圖5(b)所示，根據(jù)平均值方法得到的服務(wù)s1的信譽(yù)值明顯提升，但并不會(huì)改變服務(wù)s2,s3的信譽(yù)，從而實(shí)現(xiàn)了對(duì)服務(wù)s1的操縱.因此本方法更具抗操縱性.

4.4 性能測(cè)試

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

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

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

Fig. 7 Runtime of SA, MIP, AVG, and GA圖7 SA，MIP，AVG，GA方法的運(yùn)行時(shí)間

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

5 結(jié) 語(yǔ)

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