劉艷麗，付曉東，2，岳 昆，劉 驪，馮 勇，劉利軍

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

1 引 言

在線服務(wù)是指運(yùn)用互聯(lián)網(wǎng)技術(shù)向用戶提供線上服務(wù)的方式.隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展和普及，越來越多的設(shè)備被接入到互聯(lián)網(wǎng)中，使在線服務(wù)規(guī)模顯著增長(zhǎng).在線服務(wù)已廣泛應(yīng)用于Web服務(wù)、電子商務(wù)、移動(dòng)多媒體、電子學(xué)習(xí)等領(lǐng)域[1].然而在面對(duì)許多功能相似或相同的在線服務(wù)時(shí)，用戶不僅要考慮功能需求，還要考慮非功能需求，即服務(wù)質(zhì)量(Quality of Service，QoS)[2].此外，由于互聯(lián)網(wǎng)具有開放性和虛擬性，導(dǎo)致服務(wù)提供者可能發(fā)布不真實(shí)、不客觀的服務(wù)信息[3].信譽(yù)作為衡量服務(wù)QoS的重要指標(biāo)，反映的是用戶對(duì)服務(wù)總體的信任程度[4].因此，研究準(zhǔn)確、客觀的在線服務(wù)信譽(yù)度量方法不僅能有效地幫助用戶選擇在線服務(wù)也能促使服務(wù)提供者改善其服務(wù)質(zhì)量.

用戶與在線服務(wù)進(jìn)行交易后，會(huì)根據(jù)個(gè)人體驗(yàn)對(duì)在線服務(wù)進(jìn)行反饋評(píng)分，信譽(yù)系統(tǒng)將用戶反饋評(píng)分以特定的方式集結(jié)起來形成信譽(yù)[5].用戶對(duì)服務(wù)的評(píng)分可看成是用戶對(duì)服務(wù)的分類.例如，用戶對(duì)服務(wù){(diào)s1,s2,s3,s4,s5,s6,s7}的評(píng)分為(1，3，3，1，2，4，2)，體現(xiàn)出用戶將服務(wù)分為4類，分別為{s1,s4}、{s2,s3}、{s5,s7}以及{s6}.因此基于評(píng)分的服務(wù)信譽(yù)度量本質(zhì)上是集結(jié)各用戶對(duì)服務(wù)的分類信息獲得用戶群體對(duì)服務(wù)分類結(jié)果的過程.由于用戶具有不同的行為習(xí)慣和偏好，其對(duì)服務(wù)的分類具有明顯的個(gè)性化特征.因此，提高用戶對(duì)服務(wù)分類與最終獲得的信譽(yù)之間的一致性是確保信譽(yù)度量質(zhì)量的重要因素.一致性反映的是用戶群體對(duì)評(píng)價(jià)結(jié)果達(dá)成一致的程度，是測(cè)量群體評(píng)價(jià)意見一致性程度的重要參數(shù)[6].現(xiàn)有累加法、均值法等已被廣泛應(yīng)用的信譽(yù)度量方法均未考慮到用戶對(duì)服務(wù)分類與信譽(yù)之間的一致性關(guān)系.

隨著互聯(lián)網(wǎng)上在線服務(wù)數(shù)量的不斷增長(zhǎng)及類型的多樣化，如何集結(jié)用戶對(duì)服務(wù)的分類合理有效地進(jìn)行在線服務(wù)信譽(yù)度量成為亟待解決的重要問題.針對(duì)上述問題，本文提出一種基于一致性聚類[7]的在線服務(wù)信譽(yù)度量方法.該方法將用戶對(duì)服務(wù)的評(píng)分視為用戶對(duì)服務(wù)的分類，通過聚合所有用戶對(duì)服務(wù)的分類形成一個(gè)最終的服務(wù)聚類，使得到的最終信譽(yù)度量結(jié)果與用戶對(duì)服務(wù)分類之間的一致性最大且聚類效果較好.首先，考慮到在計(jì)算服務(wù)分類中的簇間和簇內(nèi)相似性時(shí)需要消耗大量的空間，方法使用二進(jìn)制組成的位向量來存儲(chǔ)在線服務(wù)分類中的每個(gè)簇，降低存儲(chǔ)空間的消耗；其次，方法是在服務(wù)集群的分類級(jí)別上運(yùn)行的，具有很高的可擴(kuò)展性；最后，對(duì)在線服務(wù)的分類進(jìn)行聚合的過程中，不需要輸入任何參數(shù)，自動(dòng)計(jì)算最終聚類中的聚類數(shù)量.有效地提高了在線服務(wù)信譽(yù)的合理性和有效性.

2 相關(guān)工作

信譽(yù)作為評(píng)價(jià)服務(wù)的重要QoS之一，對(duì)服務(wù)選擇的決策起著重要作用.近年來，為了研究更加準(zhǔn)確、理性的在線信譽(yù)度量，國內(nèi)外學(xué)者開展了一系列的工作.目前的在線服務(wù)信譽(yù)度量方式主要分為基于用戶反饋評(píng)分和綜合多種因素對(duì)服務(wù)信譽(yù)的影響[8].

常見的基于用戶反饋評(píng)分的在線信譽(yù)度量方式有累加法模型、平均法模型、模糊模型、Beta信譽(yù)模型等[9]，上述方法均以用戶反饋評(píng)分為基礎(chǔ)來計(jì)算服務(wù)信譽(yù)，其計(jì)算原理簡(jiǎn)單，可以快速得到信譽(yù)值.例如，eBay使用累加法將用戶對(duì)在線服務(wù)做出的反饋評(píng)分進(jìn)行累加得出服務(wù)信譽(yù)值，Amazon使用平均法，以服務(wù)獲得的所有反饋評(píng)分為基礎(chǔ)求取平均值計(jì)算服務(wù)信譽(yù).文獻(xiàn)[10]提出了一種基于模糊的大數(shù)據(jù)處理框架來評(píng)估云服務(wù)的信任級(jí)別，在用戶反饋的基礎(chǔ)上評(píng)估服務(wù)的信任級(jí)別；文獻(xiàn)[11]提出了一種Beta信譽(yù)模型，該模型在統(tǒng)計(jì)學(xué)理論的基礎(chǔ)上結(jié)合β概率密度函數(shù)和用戶反饋的評(píng)分計(jì)算在線服務(wù)信譽(yù)；文獻(xiàn)[12]提出了一種考慮用戶隱私代價(jià)的服務(wù)選擇模型，其運(yùn)用模糊邏輯與服務(wù)信譽(yù)、用戶隱私相結(jié)合來計(jì)算用戶的隱私代價(jià)，從而實(shí)現(xiàn)對(duì)候選服務(wù)的排序.

基于用戶反饋評(píng)分的信譽(yù)度量方法未考慮服務(wù)質(zhì)量、社交網(wǎng)絡(luò)關(guān)系等其他因素對(duì)服務(wù)信譽(yù)的影響[13].為此，文獻(xiàn)[14]基于QoS相似度計(jì)算服務(wù)信譽(yù)，并由低到高對(duì)其進(jìn)行排序，從而實(shí)現(xiàn)對(duì)Web服務(wù)的信譽(yù)評(píng)估；文獻(xiàn)[15]基于用戶屬性的細(xì)度化提出了一種信譽(yù)度量方法，在不考慮用戶身份的前提下，用戶可以通過評(píng)價(jià)其他用戶的屬性來提高評(píng)價(jià)的信任度；文獻(xiàn)[16]提出了一種新的信譽(yù)度量機(jī)制，它將用戶的序數(shù)偏好聚合到信譽(yù)中.首先根據(jù)序數(shù)偏好定義服務(wù)之間的優(yōu)勢(shì)關(guān)系；然后基于服務(wù)對(duì)的優(yōu)勢(shì)關(guān)系構(gòu)造一個(gè)有向無環(huán)圖；最后從圖中找出服務(wù)的排序.

上述研究雖然從多個(gè)方面對(duì)在線服務(wù)進(jìn)行了信譽(yù)度量，但未考慮到將用戶對(duì)服務(wù)的評(píng)分視為用戶對(duì)服務(wù)的分類時(shí)用戶對(duì)服務(wù)分類與信譽(yù)之間的一致性關(guān)系，導(dǎo)致在對(duì)分類進(jìn)行聚合時(shí)會(huì)出現(xiàn)具有不同類別的聚類結(jié)果，聚類效果較差，不符合大部分用戶的偏好，降低了服務(wù)信譽(yù)的穩(wěn)定性和準(zhǔn)確性.另外，如果用戶對(duì)服務(wù)的反饋評(píng)分被操縱，則根據(jù)用戶反饋評(píng)分得到的在線服務(wù)信譽(yù)度量結(jié)果也能被輕易改變.考慮到以上研究中存在的不足，本文提出一種基于一致性聚類的在線服務(wù)信譽(yù)度量方法.該方法是將所有用戶對(duì)服務(wù)的分類結(jié)果進(jìn)行聚類得到服務(wù)信譽(yù)的一個(gè)過程，在該過程中充分考慮了用戶對(duì)服務(wù)的分類與信譽(yù)之間的一致性關(guān)系，使最終聚類的每個(gè)簇中的服務(wù)最大程度的相似，而不同簇中的服務(wù)相似性最小，從而使在線服務(wù)的真實(shí)性能得到客觀地反映.最后，通過實(shí)驗(yàn)驗(yàn)證了本文方法的有效性和客觀性.

3 問題描述

本文主要研究如何把所有用戶對(duì)服務(wù)的分類進(jìn)行聚合，最終形成一個(gè)服務(wù)聚類，并且使最終聚類獲得的服務(wù)信譽(yù)與所有用戶對(duì)服務(wù)分類之間的一致性達(dá)到最大，實(shí)現(xiàn)基于一致性聚類的在線服務(wù)信譽(yù)度量.

3.1 問題定義

為了研究所有用戶對(duì)服務(wù)的分類結(jié)果與信譽(yù)之間的一致性關(guān)系問題，本文給出以下相關(guān)定義：

定義1.U={ui|i=1,2，…,m}為用戶的有限集，S={sj|j=1,2，…,n}為在線服務(wù)的有限集.其中，m表示用戶個(gè)數(shù)，n表示在線服務(wù)個(gè)數(shù).

定義2.R=[rix]m×n為用戶-服務(wù)評(píng)分矩陣，rix表示第i個(gè)用戶對(duì)第x個(gè)在線服務(wù)的評(píng)分.當(dāng)rix=riy時(shí)，表示用戶ui把服務(wù)sx和sy歸為同一類；當(dāng)rix=N/A時(shí)，表示用戶ui未對(duì)服務(wù)sx進(jìn)行評(píng)分，即用戶ui未對(duì)服務(wù)sx進(jìn)行分類，即用戶對(duì)服務(wù)的分類可以是不完整的.

定義3.矩陣R中的每行表示用戶ui對(duì)在線服務(wù)集S的分類，用向量ri=(ri1,ri2,…,rin)表示.集合cip={sx∈S|rix=p}表示用戶ui把在線服務(wù)集S中的服務(wù)sx放在等級(jí)為p的簇中.集合Ci={ci1,ci2,…,cih}為用戶ui把在線服務(wù)集S分為h個(gè)等級(jí)簇的集合.集合C={Ci|,i=1,2,…,m}為所有用戶U對(duì)服務(wù)集S分類中的簇集合.

定義4.將所有用戶對(duì)服務(wù)的分類進(jìn)行聚合，得到一個(gè)最終聚類.最終聚類中的每個(gè)簇用集合c*q={sy∈S|q=N}，其中q是經(jīng)過多數(shù)投票后服務(wù)sy所在的簇標(biāo)簽，為自然數(shù).最終聚類用集合π*表示，即π*={c*1,c*2,…,c*g}且1≤g≤h.

定義5.由用戶對(duì)服務(wù)的分類得到的最終聚類用π*表示，π*中服務(wù)集S的信譽(yù)評(píng)級(jí)用向量rz=(rz1,rz2,…,rzn)表示，rz1,rz2,…,rzn分別表示服務(wù)s1,s2,…,sn的信譽(yù)級(jí)別，且rz1,rz2,…,rzn可由聚類中服務(wù)的評(píng)分計(jì)算獲得.

定義6.在線服務(wù)分類中的簇間相似性ECS表示在一對(duì)服務(wù)簇之間服務(wù)對(duì)象的相似程度[17].其定義如下：

(1)

式(1)中，sim(sx,sy)是在線服務(wù)sx和sy在給定所有用戶對(duì)服務(wù)分類C中被分配給相同簇的次數(shù).ECS值越小，表明服務(wù)簇cip和cjk之間的相似性越小，分離性越大.

定義7.在線服務(wù)分類中的簇內(nèi)相似性ICS表示在服務(wù)簇cip內(nèi)服務(wù)對(duì)象的相似程度[17].其定義如下：

(2)

3.2 舉例說明

例1.假設(shè)有4個(gè)用戶U={ui|i=1,2，…,4}共同對(duì)6個(gè)在線服務(wù)S={sj|j=1，2，…，6}進(jìn)行評(píng)分，評(píng)分矩陣R=[rix]4×6，如表1所示.其中表中的評(píng)分表示了用戶對(duì)服務(wù)的滿意程度，我們采用電子商務(wù)評(píng)價(jià)機(jī)制中常用的1-5的評(píng)分等級(jí)來表示很不滿意、不滿意、一般、滿意、很滿意.rix=N/A表示用戶與服務(wù)未進(jìn)行交互.

表1 用戶-服務(wù)評(píng)分矩陣表

Table 1 Ratings matrix of user-service

Rs1s2s3s4s5s6u1112233u2332211u3111222u411N/AN/AN/A2

在本文中，將用戶對(duì)服務(wù)的評(píng)分視為用戶對(duì)服務(wù)的分類，即針對(duì)同一在線服務(wù)集，用戶將評(píng)分相同的在線服務(wù)歸為同一類，由此得出所有用戶對(duì)在線服務(wù)的分類.由表1可見，對(duì)于6個(gè)在線服務(wù)，用戶u1將服務(wù)s1～s6分成3類，即s1和s2、s3和s4、s5和s6.以此類推，u2把服務(wù)分成3類，u3把服務(wù)分成2類.由于用戶不一定對(duì)所有服務(wù)進(jìn)行評(píng)分，所以用戶u4只對(duì)服務(wù)s1，s2，s6進(jìn)行了評(píng)分，把服務(wù)分成2類.上述分類可用圖1表示.

圖1 多個(gè)用戶對(duì)在線服務(wù)的分類

傳統(tǒng)的在線服務(wù)信譽(yù)度量未考慮到用戶對(duì)服務(wù)分類與信譽(yù)之間存在的一致性關(guān)系問題.例如，通過均值法計(jì)算用戶對(duì)服務(wù)評(píng)分的平均值得到的信譽(yù)向量為ravg=(1.5，1.5，1.67，2，2，2).從ravg中可看出服務(wù)s1～s6被分成3類，且認(rèn)為s4，s5，s6屬于同一類.然而表1中所有用戶對(duì)服務(wù)s4，s5，s6的評(píng)分不相同，認(rèn)為s4與s5，s6不在同一類別中.使用均值法會(huì)使原本不在同一類別的服務(wù)被分到相同類別中，導(dǎo)致最終得到的信譽(yù)與所有用戶對(duì)服務(wù)分類之間的不一致性較大，缺乏合理性.此外，如果將用戶u1對(duì)服務(wù)s6的評(píng)分降低至1分，則發(fā)現(xiàn)通過均值法計(jì)算服務(wù)s6的信譽(yù)降低至1.5分，且其他服務(wù)的信譽(yù)未發(fā)生改變，這大大降低了服務(wù)s6的信譽(yù)等級(jí)，使其具有較差的抗操縱性.因此，本文提出了一種基于一致性聚類的在線服務(wù)信譽(yù)度量方法，有效地避免了因未考慮用戶對(duì)服務(wù)分類與信譽(yù)之間的一致性關(guān)系導(dǎo)致的在線服務(wù)信譽(yù)等級(jí)劃分不合理的問題，同時(shí)還提高了方法的抗操縱性.

4 基于一致性聚類的服務(wù)信譽(yù)度量

由于目前的在線服務(wù)信譽(yù)度量方法均未考慮到信譽(yù)結(jié)果與用戶對(duì)服務(wù)分類之間的一致性關(guān)系，導(dǎo)致通過用戶-服務(wù)評(píng)分計(jì)算得到的服務(wù)信譽(yù)準(zhǔn)確性較低.因此，本文提出了一種基于一致性聚類的在線服務(wù)信譽(yù)度量方法.方法將用戶對(duì)服務(wù)的評(píng)分視為用戶對(duì)服務(wù)的分類，根據(jù)在線服務(wù)中的簇內(nèi)和簇間相似性建立基于相似性的最小成本生成樹(Similarity-based Minimum-cost Spanning Tree，SMST)[18]，從具有最小權(quán)重值的邊開始，對(duì)SMST進(jìn)行切割產(chǎn)生多種可能的聚類.然后通過一致性質(zhì)量函數(shù)[19]來搜索所有可能的聚類以找到具有更好整體質(zhì)量的最終聚類π*，使最終聚類π*擁有緊湊性最強(qiáng)和分離性最大的簇.

定義8.一致性質(zhì)量函數(shù).本文中用一致性質(zhì)量函數(shù)φ來評(píng)價(jià)聚類πi的好與壞.定義如下：

(3)

(4)

其中，listmax是得到的一列值中的最大值，listmin是得到的一列值中的最小值.運(yùn)用公式(4)，通過變換在[0，1]范圍內(nèi)所有用戶對(duì)服務(wù)分類中的ICS和ECS值，減少了在計(jì)算簇內(nèi)和簇間相似性的過程中大值和小值對(duì)計(jì)算結(jié)果的不利影響.

獲得的最終聚類π*的一致性質(zhì)量函數(shù)φ必須滿足：

(5)

從式(5)可以看出聚類π*擁有最好的整體質(zhì)量，使最終聚類π*中的簇內(nèi)相似性最大，簇間相似性最小.其服務(wù)信譽(yù)度量結(jié)果相對(duì)于所有用戶對(duì)服務(wù)分類的結(jié)果來說盡可能多地一致.

4.1 基于位向量的在線服務(wù)簇表示

本文采用的一致性聚類方法在聚合所有用戶對(duì)服務(wù)的分類形成一個(gè)最終聚類的過程中，考慮到隨著互聯(lián)網(wǎng)的快速發(fā)展，在線服務(wù)數(shù)量不斷增加，將導(dǎo)致在計(jì)算所有用戶對(duì)服務(wù)分類之間的簇內(nèi)和簇間相似性時(shí)需要占用很大的存儲(chǔ)空間.因此，為了節(jié)省空間用由二進(jìn)制組成的的位向量來存儲(chǔ)在線服務(wù)中的每個(gè)簇[17].其中，每個(gè)簇中服務(wù)的存在由1表示，服務(wù)的缺失由0表示.每個(gè)用戶對(duì)在線服務(wù)的分類表示與在線服務(wù)集|S|的大小一樣長(zhǎng).

為了應(yīng)對(duì)具有不同數(shù)量的在線服務(wù)分類，我們利用投票機(jī)制來組合分類結(jié)果，從而引出服務(wù)之間相似性的新度量[20].考慮到不同服務(wù)很可能共同存在于不同服務(wù)分類中的同一簇中，因此將同一簇中服務(wù)對(duì)的同時(shí)出現(xiàn)作為其關(guān)聯(lián)的投票.在獲得用戶對(duì)服務(wù)分類的基礎(chǔ)上，通過統(tǒng)計(jì)不同服務(wù)在所有用戶對(duì)服務(wù)分類中被分配給相同簇中的次數(shù)得出共同關(guān)聯(lián)矩陣(Co-association Matrix，SM)，并基于SM計(jì)算所有用戶對(duì)服務(wù)分類中的簇間和簇內(nèi)相似性.

定義9.共同關(guān)聯(lián)矩陣為SM=[smxy]n×n，smxy表示服務(wù)sx和sy被分配給相同簇的次數(shù).則：

smxy=votesxy/m

(6)

式(6)中，m為用戶數(shù)量，votesxy是服務(wù)對(duì)(sx，sy)被分配給所有用戶對(duì)服務(wù)分類中的相同簇的次數(shù)，即sx∈S，sy∈S.然后將分類中服務(wù)對(duì)同時(shí)出現(xiàn)在相同簇中的次數(shù)映射到|S|×|S|的共同關(guān)聯(lián)矩陣中.最后根據(jù)得到的SM進(jìn)一步計(jì)算在線服務(wù)中的簇間相似性和簇內(nèi)相似性.

4.2 簇間和簇內(nèi)相似性計(jì)算

在對(duì)獲得的所有用戶對(duì)在線服務(wù)分類進(jìn)行聚合時(shí)，考慮到不同服務(wù)在分類中的相似程度不同，可以運(yùn)用兩個(gè)非常著名的無監(jiān)督客觀測(cè)量指標(biāo)：簇間相似性和簇內(nèi)相似性來實(shí)現(xiàn)對(duì)分類中的在線服務(wù)進(jìn)行簇間和簇內(nèi)相似性計(jì)算.在根據(jù)公式(1)和公式(2)進(jìn)行相似性計(jì)算時(shí)，需要知道服務(wù)sx和sy同時(shí)出現(xiàn)在相同簇中的次數(shù)sim(sx，sy).由于本文中是運(yùn)用SM來統(tǒng)計(jì)分類中服務(wù)sx和sy同時(shí)出現(xiàn)在相同簇中的次數(shù)，因此sim(sx，sy)=smxy.則在線服務(wù)分類中的簇間相似性計(jì)算如下：

(7)

在線服務(wù)分類中的簇內(nèi)相似性計(jì)算如下：

(8)

根據(jù)例1中給出的在線服務(wù)分類，分別運(yùn)用公式(7)和公式(8)計(jì)算分類中的ECS和ICS.由于ECS的計(jì)算是利用服務(wù)對(duì)象級(jí)別的信息來提供非常準(zhǔn)確的分類級(jí)別信息，所以此時(shí)得到的ECS值非常有效.

由于本文中的信譽(yù)度量是將所有用戶對(duì)服務(wù)的分類進(jìn)行聚合得到一個(gè)聚類的過程，所以可以將在線服務(wù)分類中的ECS和ICS擴(kuò)展為聚類πi的簇間相似性和簇內(nèi)相似性.

定義10.聚類πi的簇間相似性定義如下：

(9)

定義11.聚類πi的簇內(nèi)相似性定義如下：

(10)

式(10)中，ICSC(πi)值越大，表示πi的簇越緊湊.

4.3 基于用戶對(duì)服務(wù)分類與信譽(yù)之間的一致性尋找最終聚類

為了使用戶對(duì)服務(wù)分類結(jié)果與信譽(yù)之間的一致性達(dá)到最大，我們需要尋找具有緊湊且分離良好的簇的最終聚類.本文方法在不輸入任何參數(shù)的情況下，以最小生成樹的形式組織所有用戶對(duì)服務(wù)的分類來處理分類聚合問題，因?yàn)樗粌H可以保留原始的所有用戶對(duì)服務(wù)的分類信息，而且是稀疏圖，處理復(fù)雜度低.對(duì)于獲得的SMST，它有d-1條邊和最多d個(gè)不同的簇，其中d是輸入的所有用戶對(duì)服務(wù)分類中的總簇?cái)?shù).然后從SMST中具有權(quán)重值最小的邊開始對(duì)其進(jìn)行切割產(chǎn)生多種可能的聚類[21].為了從多個(gè)可能的聚類中獲得擁有簇內(nèi)相似性最大和簇間相似性最小的最終聚類π*，則必須找到一個(gè)一致性質(zhì)量函數(shù)φ(πi)，使其滿足公式(5)，用于確定具有更好整體質(zhì)量的最終聚類π*.本文方法雖然不能保證產(chǎn)生的最終聚類是全局最優(yōu)的，但通過實(shí)驗(yàn)結(jié)果表明采用本文中的算法產(chǎn)生的最終聚類較好.

本文方法中的最小成本生成樹是由無向加權(quán)圖G獲得的.首先，根據(jù)SM獲得服務(wù)分類中的簇間和簇內(nèi)相似性；其次，用無向加權(quán)圖G表示輸入的所有用戶對(duì)服務(wù)分類之間的關(guān)系.在圖G中，每個(gè)頂點(diǎn)V代表所有用戶對(duì)服務(wù)分類中的一個(gè)簇，每條邊E代表分類中簇之間的關(guān)系，每條邊上的權(quán)重W代表所有用戶對(duì)服務(wù)分類中相應(yīng)簇之間的ECS值.其定義如下：

定義12.G=(E，V，W)為無向加權(quán)圖.其中E={(cip，cjk)|(cip，cjk)∈C}為圖G中無向邊集合，V={cip|cip∈Ci}為圖G的頂點(diǎn)集合，W={ECS(cip，cjk)|(cip，cjk)∈C}為V的權(quán)重集合.

然后在圖G上運(yùn)行普里姆(Prim)算法[22]，考慮到邊緣頂點(diǎn)之間的差異性和邊緣權(quán)重值W具有反比關(guān)系，因此在圖G上運(yùn)行普里姆(Prim)算法時(shí)，以圖中的某一頂點(diǎn)為起點(diǎn)，逐步尋找與之相連的各頂點(diǎn)之間擁有高相似度即最大權(quán)重值W的邊，通過使用高相似度值表示低差異性成本來構(gòu)建SMST.最后，基于SMST來尋找最終聚類.本文的一致性聚類算法如算法1.

算法1.一致性聚類算法

輸入：輸入所有用戶對(duì)在線服務(wù)的分類U

輸出：最終聚類π*

1.G：=(E，V，W); //初始化加權(quán)圖

2.V：= ?; //頂點(diǎn)集

3.E：= ?; //邊緣集

4.W：= ?，W?E→; //邊緣權(quán)重函數(shù)

5.FOR ALLCi∈CDO

6.FOR ALLcip∈CiDO

7.V=V∪cip;

8.FOR ALLcip∈VDO

9. FOR ALLcjk∈V，i≠j，p≠kDO

10.E：=E∪(cip，cjk);

11.W：=W∪(E，ECS(cip，cjk));//邊緣頂點(diǎn)之間的差異性和W值具有反比關(guān)系

12.SMST:=Prim′s_Algorithm(G);

13.π*:=find_final_clustering(SMST);

14.RETURNπ*;

本文采用的一致性聚類算法的核心是尋找最終聚類的過程.對(duì)于獲得的SMST，從SMST上具有權(quán)重值最小的邊開始對(duì)其進(jìn)行切割并產(chǎn)生元聚類，每個(gè)元聚類都是樹的連通分量.為了在切割SMST產(chǎn)生的多個(gè)聚類中找到最終聚類π*，下面給出了尋找最終聚類過程的算法，如算法2.

算法2.尋找最終聚類

輸入：基于相似度的最小成本生成樹(SMST)

輸出：簇號(hào)h

1.初始化空列表：ics，ecs，nics，necs，φ，π;

2.h：= 0; //存儲(chǔ)邊緣的編號(hào)

3.REPEAT

4.h:=h+1;

5. 從SMST中刪除最小加權(quán)邊

6.πMC是SMST的元聚類，每一個(gè)連接組件都是元聚類;

7.πh:=majority_voting(πMC);//多數(shù)投票

8.icsh:=ICSC(πh);

9.ecsh:=ECSC(πh);

10.UNTILSMST中有一些邊;

11.nics:=normalize(ics);

12.necs:=normalize(ecs);

13.FORi= 1 tohDO

14.φi:=icsi-ecsi;

15.max_index:=maxi(φ);

16.RETURNπmax_index;

由算法2可知，在SMST中每切割一次SMST，相連接的服務(wù)簇之間會(huì)變得彼此更相似，使該聚類中的服務(wù)在所有用戶對(duì)服務(wù)分類中共同存在同一類中多次.然后，在聚類上執(zhí)行多數(shù)投票表決[23]，統(tǒng)計(jì)服務(wù)出現(xiàn)在每個(gè)類別中的次數(shù)，每個(gè)在線服務(wù)僅分配給最常存在的一個(gè)類別，以產(chǎn)生非重疊的最終聚類，提高了聚類的服務(wù)信譽(yù)級(jí)別劃分的合理性.最后，對(duì)每次切割產(chǎn)生的聚類運(yùn)用公式(3)計(jì)算其一致性質(zhì)量函數(shù)φ(πi)，再根據(jù)公式(5)來尋找具有緊湊且良好分離的簇的最終聚類π*.

從具有權(quán)重值最小的邊開始對(duì)SMST進(jìn)行切割，每切割一次產(chǎn)生的聚類運(yùn)用公式(3)對(duì)其進(jìn)行一致性質(zhì)量函數(shù)計(jì)算.在進(jìn)行ICSC(πi)和ECSC(πi)計(jì)算時(shí)，為了減少在計(jì)算過程中產(chǎn)生的大值和小值對(duì)聚類結(jié)果準(zhǔn)確度的影響，我們運(yùn)用公式(4)對(duì)其進(jìn)行歸一化處理.具體過程如算法3.

算法3.歸一化處理

輸入：值列表list

輸出：規(guī)范化列表normalized_list

1.max:=max(list);

2.min:=min(list);

3.normalized_list:=initialize empty list;//初始化空列表

4.FORi:=start_of(list)toend_of(list)DO

6.RETURNnormalized_list;

本文采用的一致性聚類算法在通過切割SMST尋找最終聚類的過程中需要運(yùn)行h次.然后在每次計(jì)算一致性聚類函數(shù)尋找最終聚類的時(shí)間復(fù)雜度為O(|πi||C|+|πi|2|C|).因此，在運(yùn)用一致性聚類算法聚合所有用戶對(duì)服務(wù)的分類得到最終聚類的總體時(shí)間復(fù)雜度為O(h(|πi||C|+|πi|2|C|)).其中|πi|表示聚類πi中簇的個(gè)數(shù)，|C|表示所有用戶U對(duì)服務(wù)集S分類的總簇?cái)?shù)，且在大多數(shù)情況下|πi|2?|S|，|C|?|S|.

4.4 基于最終聚類的信譽(yù)度量

根據(jù)用戶對(duì)服務(wù)的分類與信譽(yù)之間的一致性關(guān)系獲得最終聚類π*，然后對(duì)π*進(jìn)行信譽(yù)計(jì)算，進(jìn)而得到服務(wù)集S的信譽(yù)等級(jí)rz=(rz1，rz2，…，rzn).

首先，根據(jù)最終聚類π*計(jì)算聚類中每個(gè)簇c*q內(nèi)所有用戶對(duì)服務(wù)sx評(píng)分的平均值avgx，avgx=(r1x+r2x+…+rmx)/m，接著將其簇內(nèi)所有服務(wù)的平均值進(jìn)行累加再求取平均值作為該簇的信譽(yù)值l*q，l*q=(avg1+avg2+…+avgn)/n.然后求出其余每個(gè)簇的信譽(yù)值，并對(duì)聚類π*中所有簇的信譽(yù)值L*=(l*1，l*2，…，l*g)進(jìn)行比較大小，把信譽(yù)值最小的簇的簇號(hào)賦值為1，即該簇的信譽(yù)等級(jí)為1.以此類推，聚類中的每個(gè)簇都被賦予相應(yīng)的信譽(yù)等級(jí).最后，輸出最終聚類中每個(gè)在線服務(wù)的信譽(yù)等級(jí)rz=(rz1，rz2，…，rzn).

圖2 在線服務(wù)的最終聚類

例1中，通過計(jì)算得到的最終聚類為π*={c*1，c*2，c*3}，如圖2所示.π*中在線服務(wù)s1，s2，s3，s4，s5，s6的信譽(yù)等級(jí)為rz=(1，1，2，2，3，3).因此最終聚類π*的信譽(yù)結(jié)果最大程度上符合所有用戶對(duì)服務(wù)的分類C的結(jié)果，使最終聚類的服務(wù)信譽(yù)與所有用戶對(duì)服務(wù)分類之間的一致性最大.

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

針對(duì)以上提出的基于一致性聚類的在線服務(wù)信譽(yù)度量方法，本部分設(shè)計(jì)實(shí)現(xiàn)了該信譽(yù)度量方法并展示了實(shí)驗(yàn)結(jié)果，以測(cè)試該方法的有效性和效率.

1https：//grouplens.org/datasets/movielens/

5.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

本文方法的開發(fā)語言為Java，它提供了對(duì)位向量的內(nèi)置支持以及對(duì)位向量的操作.實(shí)驗(yàn)采用Java語言的JDK 1.8軟件開發(fā)工具包實(shí)現(xiàn)，在一臺(tái)配置為Intel Core i5 3.3GHz CPU、8GB RAM的PC機(jī)上運(yùn)行，操作系統(tǒng)為 Windows 10 專業(yè)版.

由于本文方法是基于用戶-服務(wù)評(píng)分值，所以為了更加真實(shí)地反應(yīng)實(shí)驗(yàn)結(jié)果，本文實(shí)驗(yàn)采用的數(shù)據(jù)集為MovieLens1數(shù)據(jù)集，目前MovieLens數(shù)據(jù)集被廣泛應(yīng)用于與服務(wù)相關(guān)的研究領(lǐng)域.該數(shù)據(jù)集包含電影1682部，943名用戶以及10萬條左右的用戶對(duì)服務(wù)的真實(shí)評(píng)分(1～5)，每個(gè)用戶參與的電影評(píng)分不得少于20部.考慮到用戶不可能參與所有電影的評(píng)分，為確保信譽(yù)等級(jí)劃分的合理性，如果用戶對(duì)服務(wù)的分類少于兩類，實(shí)驗(yàn)時(shí)不將這個(gè)用戶對(duì)服務(wù)的分類加入到聚類中.本文將現(xiàn)在比較流行的3種在線服務(wù)信譽(yù)度量方法：平均(Average)法、累加(Sum)法以及Beta信譽(yù)系統(tǒng)方法[11]作為主要對(duì)比方法.實(shí)驗(yàn)驗(yàn)證了信譽(yù)度量結(jié)果的合理性和有效性.

5.2 評(píng)價(jià)標(biāo)準(zhǔn)

本文將基于一致性聚類的在線服務(wù)信譽(yù)度量問題視為基于用戶對(duì)不同服務(wù)信譽(yù)類別的服務(wù)分類的聚類問題，可通過聚類有效性度量來進(jìn)行最終聚類的質(zhì)量評(píng)估.由于將每個(gè)用戶對(duì)服務(wù)集S的評(píng)分視為服務(wù)具有的真實(shí)類標(biāo)簽，因此使用最常用的監(jiān)督評(píng)估方法之一：調(diào)整后的蘭德指數(shù)(Adjusted Rand Index，ARI)[24]即蘭德指數(shù)(Rand Index，RI)的改進(jìn)版本來進(jìn)行聚類質(zhì)量評(píng)估.本文使用ARI來測(cè)量由聚合服務(wù)分類得到的最終聚類的信譽(yù)結(jié)果與所有用戶對(duì)服務(wù)分類之間的匹配程度，ARI值越大，表明它們之間的匹配程度越大，即聚類結(jié)果與用戶對(duì)服務(wù)的分類結(jié)果越吻合，聚類效果越好.因此將具有最大ARI值對(duì)應(yīng)的最終聚類的信譽(yù)向量作為服務(wù)信譽(yù)是合理的.所以，我們用ARI的大小來驗(yàn)證方法的有效性.具體定義如下：

(11)

ARIi取值范圍為[-1，1]，值越大意味著聚類結(jié)果與用戶對(duì)服務(wù)的分類結(jié)果越匹配，聚類效果越好.當(dāng)ARIi最大取值為1時(shí)，表示用戶ui對(duì)服務(wù)集S的分類Ci與經(jīng)過聚合分類得到的最終聚類π*之間完全匹配，聚類效果最好；當(dāng)ARIi為-1時(shí)，表示用戶ui對(duì)服務(wù)集S的分類Ci與最終聚類π*之間完全獨(dú)立，聚類效果最差.

本文中聚合服務(wù)分類得到的最終聚類π*與所有用戶U對(duì)服務(wù)集S的分類C之間的匹配程度用ARI*表示，則：

ARI*=ARI1+ARI2+…+ARIm

(12)

此時(shí)，ARI*取值范圍為[-m，m].同樣，ARI*值越大意味著最終聚類的信譽(yù)度量結(jié)果與所有用戶對(duì)服務(wù)的分類結(jié)果越吻合，聚類效果越佳.

表2 ARI列聯(lián)表

Table 2 Abbreviations for ARI

ClassClusterc?1c?2…c?QSumsci1n11n12…n1Qn1·ci2n21n22…n2Qn2·????ciPnP1nP2…nPQnP·Sumsn·1n·2n·Qn··=n

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

觀察公式(12)可知，所有用戶對(duì)服務(wù)分類與最終聚類的信譽(yù)之間的ARI值越大，表示最終聚類的信譽(yù)與所有用戶對(duì)服務(wù)的分類結(jié)果匹配度越大，聚類效果越好，得到的信譽(yù)度量結(jié)果越合理.實(shí)驗(yàn)?zāi)M了在不同用戶數(shù)量m(100≤m≤500)和不同服務(wù)數(shù)量n(10≤n≤50)下，記錄本文方法得到的最終聚類的信譽(yù)向量rz、平均法的信譽(yù)向量ravg、累加法的信譽(yù)向量rsum、Beta法的信譽(yù)向量rbeta與所有用戶對(duì)服務(wù)分類之間的ARI，分別用ARI*，ARIavg，ARIsum，ARIbeta表示，如圖3所示.

圖3 一致性驗(yàn)證

由圖3(a)可見，隨著用戶數(shù)量和服務(wù)數(shù)量的增加，ARI*越來越大.說明服務(wù)和用戶數(shù)量越大，通過本文方法聚合分類得到的聚類結(jié)果與用戶對(duì)服務(wù)分類之間的匹配程度越高，使得到的最終聚類的信譽(yù)向量rz與所有用戶對(duì)服務(wù)分類之間的一致性越大.

由圖3(b)、圖3(c)和圖3(d)可見，ARIavg、ARIsum和ARIbeta并不都隨著用戶數(shù)量和服務(wù)數(shù)量的增加而增加.說明通過平均法、累加法和Beta法得到的信譽(yù)度量結(jié)果與所有用戶對(duì)服務(wù)分類之間的匹配度較低，使信譽(yù)向量ravg，rsum和rbeta與所有用戶對(duì)服務(wù)分類之間的不一致性較大.

此外，算法比較記錄了在不同服務(wù)數(shù)量和用戶樣本規(guī)模下ARI*，ARIavg的差值、ARI*，ARIsum的差值以及ARI*，ARIbeta的差值，ARI*-ARIavg如圖4(a)所示，ARI*-ARIsum如圖4(b)所示，ARI*-ARIbeta的如圖4(c)所示.

圖4 信譽(yù)度量方法一致性比較

由圖4(a)、圖4(b)和圖4(c)可見，在同樣的服務(wù)數(shù)量和用戶規(guī)模下，ARI*-ARIavg、ARI*-ARIsum和ARI*-ARIbeta的值始終大于0，即ARI*始終大于ARIavg、ARIsum和ARIbeta.雖然隨著服務(wù)數(shù)量和用戶規(guī)模的增大，ARI*與ARIavg、ARIsum、ARIbeta之間的差值在不斷縮小，但始終位于0之上.說明本方法與其他三種方法相比得到最終聚類的信譽(yù)向量與所有用戶對(duì)服務(wù)分類之間的ARI*最大，由此獲得的信譽(yù)度量結(jié)果與所有用戶對(duì)服務(wù)分類之間的一致性最大，得到的服務(wù)信譽(yù)較為合理.

5.4 操縱復(fù)雜性驗(yàn)證

對(duì)于隨機(jī)選取的某服務(wù)，通過對(duì)其增加高評(píng)分或低評(píng)分的用戶數(shù)量來進(jìn)行服務(wù)評(píng)分操縱，若根據(jù)本文方法得到的服務(wù)信譽(yù)級(jí)別無明顯變化，則通過該方法得到的信譽(yù)結(jié)果抗操縱性較強(qiáng).為此，隨機(jī)選取兩個(gè)在線服務(wù)s1和s2，用戶數(shù)量為500.我們選取不同比例的用戶對(duì)服務(wù)進(jìn)行評(píng)分操縱，分別為20%，40%，60%，80%，100%.通過分別提高s1的評(píng)分至5分和降低s2的評(píng)分至1分來觀察這兩個(gè)服務(wù)的信譽(yù)級(jí)別變化.Sum法、Average法、Beta法、本文方法分別計(jì)算在增加不同操縱用戶比例時(shí)在線服務(wù)s1和s2的信譽(yù)級(jí)別，結(jié)果分別如圖5(a)和圖5(b)所示.

圖5 抗操縱性能驗(yàn)證

根據(jù)圖5(a)所示，隨著操縱用戶比例的增加，Average法、Sum法和Beta法中服務(wù)s1的信譽(yù)級(jí)別在不斷地提高，而根據(jù)本文方法得到的服務(wù)s1的信譽(yù)級(jí)別一直保持不變，只有當(dāng)操縱用戶比例達(dá)到100%時(shí)，服務(wù)s1的信譽(yù)級(jí)別才提高.說明要對(duì)本方法中服務(wù)s1的信譽(yù)級(jí)別進(jìn)行操縱需要消耗大量成本.

根據(jù)圖5(b)所示，隨著操縱評(píng)分?jǐn)?shù)量的增加，Average法、Sum法和Beta法中服務(wù)s2的信譽(yù)級(jí)別在不斷地降低，而根據(jù)本文方法得到的服務(wù)s2的信譽(yù)級(jí)別在操縱用戶比例達(dá)到60%之前一直保持不變；然后當(dāng)操縱用戶比例達(dá)到80%時(shí)，服務(wù)s2的信譽(yù)級(jí)別降低；最后隨著操縱用戶比例的增加直到100%時(shí)，服務(wù)s2的信譽(yù)級(jí)別穩(wěn)定不變.由此可以看出，本文方法得到的信譽(yù)度量結(jié)果具有更好的抗操縱性.

5.5 性能驗(yàn)證

為了測(cè)試方法的運(yùn)行效率，實(shí)驗(yàn)?zāi)M了m(100≤m≤500)個(gè)用戶和n(10≤n≤50)個(gè)在線服務(wù)分別在不同用戶數(shù)量和服務(wù)樣本規(guī)模下進(jìn)行信譽(yù)度量的實(shí)驗(yàn)，并且記錄了每次實(shí)驗(yàn)的運(yùn)行時(shí)間，如圖6所示.此外，還比較了本方法、Average法、Sum法、Beta法在用戶數(shù)量為500和服務(wù)數(shù)量為10～50的規(guī)模下的運(yùn)行時(shí)間，如表3所示.

圖6 不同用戶數(shù)量和服務(wù)規(guī)模下的運(yùn)行時(shí)間

觀察圖6可知，方法的運(yùn)行時(shí)間會(huì)隨著用戶數(shù)量的增加而不斷增加，原因是在服務(wù)數(shù)量一定時(shí)，計(jì)算用戶對(duì)服務(wù)分類中的ECS和ICS的次數(shù)會(huì)隨用戶數(shù)量的增加而增加，導(dǎo)致根據(jù)公式(3)和公式(4)計(jì)算得到最終聚類的信譽(yù)度量結(jié)果的運(yùn)行時(shí)間增加.但是在用戶數(shù)量一定時(shí)，運(yùn)行時(shí)間并不隨服務(wù)數(shù)量的增加而增加，是因?yàn)樵谟?jì)算簇間和簇內(nèi)相似性時(shí)，運(yùn)行時(shí)間只與每對(duì)服務(wù)出現(xiàn)在相同簇中的次數(shù)有關(guān)，與服務(wù)數(shù)量無關(guān).所以本文方法可通過控制用戶數(shù)量來有效地提升信譽(yù)度量的效率.

表3 不同服務(wù)數(shù)量在不同方法下的運(yùn)行時(shí)間(單位：秒)

Table 3 Runtime of different services in different methods(unit：seconds)

1020304050本文方法30294288813571156Average0.1720.2840.3280.5150.547Sum0.1560.2180.2800.4370.468Beta0.2170.3310.4480.5460.609

從表3可知，相對(duì)Average法、Sum法和Beta法的運(yùn)行時(shí)間而言，本文方法雖然運(yùn)行時(shí)間較長(zhǎng)，但通過操縱該方法獲得在線服務(wù)信譽(yù)度量結(jié)果所需的時(shí)間要比其他3種方法更長(zhǎng).因此，對(duì)本文方法獲得的信譽(yù)度量結(jié)果進(jìn)行操縱的難度要遠(yuǎn)高于其他三種方法.

6 結(jié) 論

本文提出一種基于一致性聚類的在線服務(wù)信譽(yù)度量方法，以解決由于未考慮到用戶對(duì)服務(wù)的分類結(jié)果與信譽(yù)之間的一致性關(guān)系導(dǎo)致的最終聚類的服務(wù)信譽(yù)級(jí)別劃分不合理的問題.方法在切割基于相似性的最小成本生成樹時(shí)，會(huì)產(chǎn)生多種可能的聚類.然后用一致性質(zhì)量函數(shù)來尋找具有更好整體質(zhì)量的最終聚類，使其簇內(nèi)的相似性最大，簇間的差異性最大，聚類效果較好.最后基于得到的最終聚類計(jì)算其服務(wù)信譽(yù)，使用戶對(duì)服務(wù)分類與信譽(yù)結(jié)果之間的一致性達(dá)到最大，提供了一種研究在線服務(wù)信譽(yù)度量方法的新思路.同時(shí)，實(shí)驗(yàn)也驗(yàn)證了本文方法在進(jìn)行服務(wù)分類聚合時(shí)具有較高的的有效性.

本文方法在進(jìn)行聚類過程中只考慮了用戶對(duì)在線服務(wù)的評(píng)分，未綜合考慮其他因素在聚類過程中對(duì)在線服務(wù)信譽(yù)的影響.因此，下一步將從該方面研究一種使信譽(yù)等級(jí)劃分更準(zhǔn)確的在線服務(wù)信譽(yù)度量方法.