付曉東,彭 俊,岳 昆,劉 驪+,劉利軍,馮 勇

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

0 引言

以互聯(lián)網(wǎng)作為載體，由服務(wù)提供者向用戶所提供的服務(wù)，被稱為在線服務(wù)[1]。隨著互聯(lián)網(wǎng)技術(shù)的蓬勃發(fā)展，在線服務(wù)在Web服務(wù)、電子商務(wù)、搜索引擎等眾多領(lǐng)域得到了廣泛應(yīng)用[2]。相應(yīng)地，互聯(lián)網(wǎng)出現(xiàn)了眾多功能相同的候選在線服務(wù)[3]，用戶想從中選擇出滿足自身需求的服務(wù)，勢(shì)必會(huì)花費(fèi)大量的時(shí)間與精力[4]。首先，用戶不可能與所有候選的在線服務(wù)進(jìn)行交互，使其難以獲取所有候選服務(wù)的相關(guān)信息；其次，由于服務(wù)與服務(wù)之間的競(jìng)爭(zhēng)激烈，不排除服務(wù)提供者為了提升其服務(wù)的競(jìng)爭(zhēng)力發(fā)布虛假服務(wù)信息的可能。因此，用戶通常需要借助以第三方用戶觀點(diǎn)(即其他用戶對(duì)服務(wù)的數(shù)值型評(píng)分、文本評(píng)論、序數(shù)偏好等偏好信息)為基礎(chǔ)的在線服務(wù)評(píng)價(jià)方法對(duì)服務(wù)進(jìn)行評(píng)價(jià)。此類方法將所有已知的第三方用戶觀點(diǎn)作為輸入，并使用相應(yīng)的評(píng)價(jià)算法對(duì)候選服務(wù)進(jìn)行有效的排序，用于輔助用戶進(jìn)行服務(wù)選擇。

以數(shù)值型評(píng)分為基礎(chǔ)的評(píng)價(jià)方法[5-6]和以文本評(píng)論為基礎(chǔ)的評(píng)價(jià)方法[7-8]，均假設(shè)所有用戶具有相同的評(píng)價(jià)準(zhǔn)則，忽視了用戶對(duì)服務(wù)的評(píng)分事實(shí)上不可比較的問題，使得評(píng)價(jià)結(jié)果可能具有誤導(dǎo)性和不可靠性[9]。因此，出現(xiàn)了以序數(shù)偏好為基礎(chǔ)的評(píng)價(jià)方法[10]，此類方法結(jié)合了社會(huì)選擇理論[11]，將在線服務(wù)評(píng)價(jià)問題定義為一個(gè)群決策問題，其核心目的是將用戶的序數(shù)偏好聚合為群體偏好，以輔助用戶進(jìn)行服務(wù)選擇。由于此類方法在進(jìn)行偏好聚合時(shí)，是使用序數(shù)偏好作為用戶的服務(wù)評(píng)價(jià)數(shù)據(jù)，而不是數(shù)值型評(píng)分形式的基數(shù)偏好，從而解決了因用戶的評(píng)價(jià)準(zhǔn)則不一致而導(dǎo)致評(píng)價(jià)結(jié)果存在誤導(dǎo)和不可靠的問題。

由于候選服務(wù)的數(shù)量集巨大，使得不完整偏好成為了極其常見的現(xiàn)象。首先，用戶不可能對(duì)所有候選服務(wù)進(jìn)行交互獲得交互體驗(yàn)，從而用戶所能提供的偏好難以覆蓋所有候選服務(wù)；其次，用戶大多并非決策領(lǐng)域?qū)＜?，即使其與所有候選服務(wù)均有過交互體驗(yàn)，但是仍然很難提供對(duì)所有候選服務(wù)的完整偏好；再次，用戶可能會(huì)出于對(duì)自身隱私的考慮，不愿意提供其全部的已知偏好；最后，要求用戶提供其關(guān)于所有候選服務(wù)的完整偏好，會(huì)造成大量且不必要的計(jì)算和認(rèn)知負(fù)擔(dān)[12]。

偏好聚合是社會(huì)選擇理論的基本問題之一[13]，但阿羅不可能定理[14]證明了不可能存在完美的偏好聚合方法。盡管如此，依然可通過運(yùn)用各種距離作為度量指標(biāo)，尋找與所有個(gè)體偏好距離最小的群體偏好，用于解決偏好聚合問題[15]。在該場(chǎng)景中，若候選服務(wù)數(shù)量為m，則潛在群體偏好的原始解空間規(guī)模為m!。當(dāng)用戶偏好為完整偏好時(shí)，可通過借助群體偏好應(yīng)滿足的某些基礎(chǔ)公理(例如多數(shù)準(zhǔn)則、孔多塞性等)有效地縮小解空間規(guī)模[16];當(dāng)用戶偏好不完整時(shí)，將導(dǎo)致潛在群體偏好的數(shù)量劇增，并會(huì)降低最終聚合結(jié)果的質(zhì)量[17]。以聚合序數(shù)偏好作為基礎(chǔ)解決方案的現(xiàn)有在線服務(wù)評(píng)價(jià)方法在處理不完整偏好時(shí)，通常是僅基于已知偏好進(jìn)行偏好聚合，并未考慮未知偏好對(duì)群體決策的潛在影響，使得已知偏好的代表性成為了影響評(píng)價(jià)結(jié)果質(zhì)量的重要因素；或是限制用戶偏好的表達(dá)形式從而降低了評(píng)價(jià)方法的普適性；或是使用協(xié)同過濾工具對(duì)未知偏好預(yù)先進(jìn)行填充。然而在實(shí)際應(yīng)用中，其可能會(huì)出現(xiàn)冷啟動(dòng)、時(shí)間復(fù)雜度受限于用戶或服務(wù)規(guī)模的問題，且存在降低評(píng)價(jià)結(jié)果質(zhì)量的風(fēng)險(xiǎn)。

為解決上述不完整偏好解決方案的潛在問題，本文提出一種面向不完整序數(shù)偏好的在線服務(wù)評(píng)價(jià)方法，首先通過定義面向不完整序數(shù)偏好的Kendall tau勝者距離(KWD)，實(shí)現(xiàn)了在不完整序數(shù)偏好場(chǎng)景下的在線服務(wù)評(píng)價(jià)，同時(shí)避免了現(xiàn)有方法對(duì)用戶偏好表達(dá)形式的限制；然后開發(fā)了關(guān)于群體偏好的質(zhì)量評(píng)估算法，以及由Kendall tau勝者距離驅(qū)動(dòng)的偏好抽取策略，用于在需要時(shí)評(píng)估和快速優(yōu)化服務(wù)評(píng)價(jià)結(jié)果的質(zhì)量。通過理論分析，并在真實(shí)數(shù)據(jù)集、人工合成數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，驗(yàn)證了所提方法的有效性與合理性。

1 相關(guān)工作

近年來，以不同類型的在線服務(wù)評(píng)價(jià)數(shù)據(jù)為基礎(chǔ)，國內(nèi)外學(xué)者分別展開了一系列的服務(wù)評(píng)價(jià)研究。根據(jù)不同的服務(wù)評(píng)價(jià)數(shù)據(jù)類型，可將服務(wù)評(píng)價(jià)方法分為3類[18]：①以數(shù)值型評(píng)分為基礎(chǔ)；②以文本評(píng)論為基礎(chǔ)；③以序數(shù)偏好為基礎(chǔ)。

累加法、平均值法兩種基于數(shù)值型評(píng)分的服務(wù)評(píng)價(jià)方法，因其計(jì)算效率高、原理容易被用戶理解，在電子商務(wù)領(lǐng)域中得到了廣泛的應(yīng)用[5]。文獻(xiàn)[6]提出一種Beta信譽(yù)系統(tǒng)，其將用戶的數(shù)值型評(píng)分與統(tǒng)計(jì)學(xué)中的β概率密度函數(shù)相結(jié)合，用于計(jì)算候選服務(wù)的評(píng)級(jí)。這類在線服務(wù)評(píng)價(jià)方法假定用戶能夠在相同的評(píng)價(jià)準(zhǔn)則下對(duì)候選服務(wù)進(jìn)行評(píng)分，忽視了因用戶的評(píng)價(jià)準(zhǔn)則不一致所造成的不同用戶對(duì)同一服務(wù)的評(píng)分不可比較的情況，以至于評(píng)價(jià)結(jié)果可能具有誤導(dǎo)性和不可靠性[9]。

由于文本評(píng)論相比于數(shù)值型評(píng)分所蘊(yùn)涵的信息更豐富，使得在使用相同數(shù)量的評(píng)論數(shù)據(jù)時(shí)，其能提供一個(gè)相對(duì)更為準(zhǔn)確的評(píng)價(jià)結(jié)果。因此，文獻(xiàn)[7]提出了HFT(hidden factors as topics)模型，通過綜合考慮文本評(píng)論數(shù)據(jù)與數(shù)值型評(píng)分?jǐn)?shù)據(jù)，最終可更準(zhǔn)確地對(duì)缺失的服務(wù)評(píng)分進(jìn)行預(yù)測(cè)，為個(gè)性化的在線服務(wù)推薦提供了解決方案。文獻(xiàn)[8]提出一種通過分析每個(gè)服務(wù)的已知文本評(píng)論，識(shí)別出其所擁有的特性并給出相對(duì)應(yīng)的評(píng)分，當(dāng)用戶選擇某個(gè)特性時(shí)，將該特性的評(píng)分作為評(píng)價(jià)指標(biāo)對(duì)候選服務(wù)進(jìn)行排序的評(píng)價(jià)方法。然而，該類方法仍然是建立在假設(shè)所有用戶具有相同的評(píng)價(jià)準(zhǔn)則的前提下[18]。

為了解決用戶評(píng)價(jià)準(zhǔn)則不一致的問題，文獻(xiàn)[10]提出將數(shù)值型評(píng)分轉(zhuǎn)換為成對(duì)的序數(shù)偏好，利用Kendall tau距離度量?jī)蓚€(gè)偏好之間的距離，使用遺傳算法尋找與已知偏好距離最小的最優(yōu)信譽(yù)向量;文獻(xiàn)[19]提出一種基于Kendall tau距離的在線服務(wù)信譽(yù)度量方法，其構(gòu)建了用戶—服務(wù)評(píng)分矩陣，通過使用模擬退火法，尋找與用戶—服務(wù)評(píng)分矩陣的Kendall tau距離最小的服務(wù)信譽(yù)向量;文獻(xiàn)[20]提出一種基于支配關(guān)系的信譽(yù)計(jì)算模型，其通過多數(shù)準(zhǔn)則確定候選服務(wù)對(duì)的支配關(guān)系，用于構(gòu)造一個(gè)以候選服務(wù)為節(jié)點(diǎn)的有向無環(huán)圖，并在圖中尋找一條包含所有候選服務(wù)的路徑，將其作為最終的服務(wù)排名;文獻(xiàn)[18]使用協(xié)同過濾工具預(yù)先對(duì)未知的用戶評(píng)分進(jìn)行填充，構(gòu)造完整的用戶—服務(wù)評(píng)分矩陣，然后將評(píng)分矩陣轉(zhuǎn)換成偏好關(guān)系，最終使用排序?qū)?ranked pair)社會(huì)選擇函數(shù)聚合用戶偏好獲得服務(wù)評(píng)價(jià)結(jié)果。

由于候選服務(wù)數(shù)量眾多、用戶認(rèn)知能力以及隱私因素等問題的存在，使得不完整偏好在現(xiàn)實(shí)的在線服務(wù)評(píng)價(jià)中極其常見，而在線服務(wù)評(píng)價(jià)方法則是以所有已知的用戶偏好作為輸入，計(jì)算服務(wù)評(píng)價(jià)結(jié)果。因此，在線服務(wù)評(píng)價(jià)方法應(yīng)當(dāng)具備在不完整偏好場(chǎng)景下(尤其是用戶偏好非常稀疏時(shí))進(jìn)行在線服務(wù)評(píng)價(jià)的能力。然而，現(xiàn)有研究在不完整偏好場(chǎng)景下進(jìn)行在線服務(wù)評(píng)價(jià)時(shí)存在以下問題：

(1)一部分方法僅基于已知偏好進(jìn)行偏好聚合，忽視了未知偏好對(duì)群體決策的潛在影響，如通過特定的策略構(gòu)建及求解以服務(wù)為節(jié)點(diǎn)的有向無環(huán)圖的評(píng)價(jià)方法，當(dāng)已知偏好過于稀疏時(shí)，可能會(huì)導(dǎo)致無法構(gòu)建包含所有節(jié)點(diǎn)的有向無環(huán)圖，或者構(gòu)建的有向無環(huán)圖缺乏代表性。另一部分評(píng)價(jià)方法則是對(duì)用戶偏好的表達(dá)形式進(jìn)行限制，如要求用戶必須給出關(guān)于所有候選服務(wù)的Top-K偏好，給用戶附加了多余的認(rèn)知與計(jì)算負(fù)擔(dān)，并使得此類方法在用戶所表達(dá)的不完整偏好不滿足前提條件時(shí)會(huì)出現(xiàn)無法計(jì)算的情況，降低了評(píng)價(jià)方法的普適性。

(2)基于協(xié)同過濾工具的評(píng)價(jià)方法使得協(xié)同過濾的性能成為了影響評(píng)價(jià)結(jié)果質(zhì)量的重要因素。因?yàn)閰f(xié)同過濾首先要求已知偏好具有一定的完整度，否則會(huì)出現(xiàn)冷啟動(dòng)等問題，嚴(yán)重影響預(yù)測(cè)結(jié)果的準(zhǔn)確性；其次，用戶或服務(wù)規(guī)模的增加將提高預(yù)測(cè)算法的時(shí)間復(fù)雜度，給評(píng)價(jià)方法附加了多余的限制；最后，無論何種評(píng)價(jià)方法的評(píng)價(jià)結(jié)果本就具有一定的誤差，若再使用協(xié)同過濾預(yù)測(cè)未知偏好，相當(dāng)于引入了二次誤差，存在降低評(píng)價(jià)結(jié)果質(zhì)量的風(fēng)險(xiǎn)。

綜上所述，已有研究尚存在僅考慮已知偏好、限制用戶偏好的表達(dá)形式、使用協(xié)同過濾工具預(yù)先填充未知偏好，以及假設(shè)用戶具有相同的評(píng)價(jià)準(zhǔn)則而導(dǎo)致評(píng)價(jià)結(jié)果具有誤導(dǎo)性的問題，有必要研究性能更穩(wěn)定、高效的服務(wù)評(píng)價(jià)方法。

2 問題定義

為方便描述不完整序數(shù)偏好場(chǎng)景下的在線服務(wù)評(píng)價(jià)問題，首先對(duì)相關(guān)概念定義如下：

定義1集合S={s1,s2,…,sm}為所有候選在線服務(wù)的集合，集合U={u1,u2,…,un}為所有用戶的集合。其中：m為候選在線服務(wù)的數(shù)量，n為用戶的數(shù)量。

定義2γh是從集合S中選出m個(gè)候選服務(wù)構(gòu)成的一個(gè)由優(yōu)至劣的排列；集合Γs={γh|h∈{1,2,…,m!}}是由所有可能的排列γh所構(gòu)成的集合，即關(guān)于集合S的全排列序數(shù)偏好的集合，|Γs|=m!。例如，當(dāng)m=3時(shí)，Γs={(s1,s2,s3),(s1,s3,s2),(s2,s1,s3),(s2,s3,s1),(s3,s1,s2),(s3,s2,s1)}，|Γs|=6。

定義3P={p1,p2,…,pn}為n個(gè)用戶的已知序數(shù)偏好集。其中px是由|px|個(gè)成對(duì)偏好關(guān)系構(gòu)成的關(guān)于用戶ux的已知序數(shù)偏好，px?{(si,sj)|i,j∈{1,2,…,m},i≠j},且0≤|px|≤m(m-1)/2；若存在(si,sj)∈px則表示用戶ux認(rèn)為si優(yōu)于sj,記為si?xsj，且(sj,si)?px。

當(dāng)|px|=m×(m-1)/2時(shí)，表示用戶ux的已知序數(shù)偏好px為完整序數(shù)偏好；當(dāng)1≤|px|

定義4V={v1,v2,…,vn}為n個(gè)用戶關(guān)于m個(gè)候選服務(wù)的完整序數(shù)偏好集，其中vx為用戶ux的完整序數(shù)偏好，vx∈Γs；vx(si)表示si在用戶ux偏好中的位置，若用戶ux認(rèn)為si?xsj，則vx(si)

定義5C(px)是由以px作為基礎(chǔ)，拓展出的所有可能的vx所構(gòu)成的關(guān)于用戶ux的潛在完整序數(shù)偏好集合；C(P)=C(p1)×C(p2)×…×C(pn)是由以P作為基礎(chǔ)，拓展出的所有可能的V所構(gòu)成的關(guān)于所有用戶的潛在完整序數(shù)偏好集的集合。

例如，當(dāng)m=3,n=2且p1={(s3,s1)},p2{(s2,s1),(s1,s3),(s2,s3)}時(shí)，則C(p1)={(s2,s3,s1),(s3,s2,s1),(s3,s1,s2)}，C(p2)={(s2,s1,s3)}；C(P)={{(s2,s3,s1),(s2,s1,s3)},{(s3,s2,s1),(s2,s1,s3)}，{(s3,s1,s2),(s2,s1,s3)}}且有|C(P)|=|C(p1)|×|C(p2)|=3，即若以當(dāng)前的P作為基礎(chǔ)，則可拓展出3種不同的V。

定義6KR=(ki|i∈{1,2,…,m})為以P作為基礎(chǔ)評(píng)價(jià)數(shù)據(jù)所計(jì)算出的關(guān)于候選服務(wù)集合S中的所有候選服務(wù)的群體偏好，即服務(wù)評(píng)價(jià)結(jié)果。其中ki為候選服務(wù)si的有效評(píng)價(jià)值，若ki

本文所提方法能夠直接以不完整序數(shù)偏好作為輸入進(jìn)行在線服務(wù)評(píng)價(jià)，且不限制用戶偏好的表達(dá)形式，同時(shí)也不需要協(xié)同過濾工具對(duì)用戶偏好進(jìn)行預(yù)先填充。本文還設(shè)計(jì)了用于評(píng)估群體偏好(KR)質(zhì)量的評(píng)估算法，當(dāng)用戶需要且KR質(zhì)量未達(dá)要求時(shí)，可通過應(yīng)用偏好抽取策略向用戶進(jìn)行少量但關(guān)鍵的偏好查詢，適當(dāng)?shù)刎S富已知序數(shù)偏好集P，從而快速優(yōu)化KR的質(zhì)量。

3 基于Kendall tau距離的在線服務(wù)評(píng)價(jià)

在線服務(wù)的實(shí)際應(yīng)用場(chǎng)景中，龐大的候選服務(wù)數(shù)量使得不完整偏好已經(jīng)成為了極其常見的現(xiàn)象。不同于現(xiàn)有的在線服務(wù)評(píng)價(jià)方法處理不完整偏好的解決方案，本文受到Kendall tau距離原始定義的啟發(fā)，對(duì)其進(jìn)行了拓展。首先，定義了完整序數(shù)偏好場(chǎng)景下的KWD，將其用于量化每個(gè)候選服務(wù)的質(zhì)量；然后，將KWD拓展至不完整序數(shù)偏好的場(chǎng)景，并設(shè)計(jì)了相應(yīng)的服務(wù)排序算法，用于計(jì)算服務(wù)評(píng)價(jià)結(jié)果KR，解決了現(xiàn)有評(píng)價(jià)方法在不完整序數(shù)偏好場(chǎng)景下進(jìn)行服務(wù)評(píng)價(jià)的局限性；另外，由于在以P作為基礎(chǔ)評(píng)價(jià)數(shù)據(jù)計(jì)算KR時(shí)，每個(gè)候選服務(wù)si均存在大量不同的可能有效評(píng)價(jià)值ki，且其規(guī)模通常均為階乘級(jí)別，本文通過分析序數(shù)偏好的結(jié)構(gòu)特點(diǎn)以及KWD的計(jì)算特點(diǎn)，開發(fā)了可快速計(jì)算有效評(píng)價(jià)值ki的算法，最終實(shí)現(xiàn)了能夠直接以不完整序數(shù)偏好作為輸入，并快速計(jì)算出相應(yīng)的服務(wù)評(píng)價(jià)結(jié)果KR的在線服務(wù)評(píng)價(jià)方法。

3.1 面向完整序數(shù)偏好的KWD

以各種距離作為度量指標(biāo)，尋找與所有個(gè)體偏好距離最小的群體偏好是解決偏好聚合問題的常見且被廣泛應(yīng)用的方案[15]。其中，以Kendall tau距離為基礎(chǔ)的Kemeny方法[21]是解決偏好聚合問題的經(jīng)典方法。然而，求解Kemeny排序是一個(gè)NP難問題，由于原始的Kendall tau距離僅能被用于衡量2個(gè)完整序數(shù)偏好之間的差異程度，即計(jì)算它們之間的逆序數(shù)作為距離值[22]，從而造成了Kemeny方法要求個(gè)體偏好必須為完整序數(shù)偏好。

本文以Kendall tau距離的核心思想，即利用逆序數(shù)計(jì)算差異為基礎(chǔ)，定義了KWD來衡量每個(gè)候選服務(wù)成為群體偏好中的勝者的距離，而不是像原始的Kendall tau距離一樣去衡量?jī)蓚€(gè)完整序數(shù)偏好之間的差異程度，為后續(xù)將KWD拓展至不完整序數(shù)偏好的場(chǎng)景提供了條件。

首先，通過假定si為群體偏好中的最優(yōu)候選服務(wù)(勝者)，表示其在群體偏好中一定優(yōu)于其他的所有候選服務(wù)。因此，可通過統(tǒng)計(jì)當(dāng)前假定勝者si與其他所有候選服務(wù)在用戶偏好vx中的逆序關(guān)系對(duì)的數(shù)量，即vx中優(yōu)于si的候選服務(wù)數(shù)量，將其作為用戶ux關(guān)于si的Kendall tau勝者距離，即uKWD(si,vx)。隨后將每個(gè)用戶關(guān)于si的Kendall tau勝者距離進(jìn)行求和，并將結(jié)果作為所有用戶關(guān)于si的Kendall tau勝者距離，即

(1)

(2)

式(1)中的1(…)為計(jì)數(shù)器，當(dāng)vx中存在sj?xsi偏好關(guān)系時(shí)返回1，否則返回0。

例如，當(dāng)m=4且用戶ui的v1=(s1,s2,s3,s4)時(shí)，若計(jì)算uKWD(s3,v1)：首先需假定s3為群體偏好中的勝者，則可推導(dǎo)出在群體偏好中存在如下包含s3的偏好關(guān)系對(duì){(s3?s1),(s3?s2),(s3?s4)}；其次根據(jù)v1可推導(dǎo)出如下包含s3的偏好關(guān)系對(duì){(s1?s3),(s2?s3),(s3?s4)}；最后統(tǒng)計(jì)上述2個(gè)偏好關(guān)系對(duì)集合中不一致的偏好關(guān)系對(duì)的數(shù)量，即逆序關(guān)系對(duì)的數(shù)量，其結(jié)果即為uKWD(s3,v1)，因此有uKWD(s3,v1)=2。最終僅需將所有用戶的uKWD(s3,vx)進(jìn)行求和，其結(jié)果即為KWD(s3,V)。

當(dāng)以完整序數(shù)偏好集V為基礎(chǔ)評(píng)價(jià)數(shù)據(jù)求解群體偏好時(shí)，僅需將每個(gè)候選服務(wù)的KWD值作為基準(zhǔn)，并將所有候選服務(wù)按照由小至大的規(guī)則排列，即可形成關(guān)于所有候選服務(wù)的群體偏好，不存在計(jì)算困難的問題。

3.2 面向不完整序數(shù)偏好的KWD以及在線服務(wù)排序

為了使KWD能夠基于不完整序數(shù)偏好的場(chǎng)景進(jìn)行在線服務(wù)評(píng)價(jià)，以及為后續(xù)的質(zhì)量評(píng)估算法與偏好抽取策略提供條件，需分別求解每個(gè)候選服務(wù)在P作為基礎(chǔ)評(píng)價(jià)數(shù)據(jù)時(shí)的最大與最小KWD，記為MaxK(si,P)與MinK(si,P)：

(3)

(4)

式(3)中的MaxK(si,P)表示候選服務(wù)si在P中的最大KWD；式(4)中的MinK(si,P)表示候選服務(wù)si在P中的最小KWD。

由于KWD是基于距離的概念對(duì)每個(gè)候選服務(wù)的質(zhì)量進(jìn)行量化，KWD值越大，則表示該候選服務(wù)的質(zhì)量越差，即成為勝者的可能性越小;反之亦然。

在不完整序數(shù)偏好的場(chǎng)景中，評(píng)價(jià)一個(gè)候選服務(wù)的優(yōu)劣，存在大量的不確定因素，為了確保評(píng)價(jià)結(jié)果的穩(wěn)定與準(zhǔn)確，應(yīng)使用其最低質(zhì)量作為評(píng)價(jià)指標(biāo)，而不是最高質(zhì)量。因此，本文將每個(gè)候選服務(wù)的最大KWD作為該候選服務(wù)的有效評(píng)價(jià)值，即ki=MaxK(si,P)，并將該值作為排序因子，對(duì)所有候選服務(wù)按由小至大的規(guī)則排列，形成關(guān)于所有候選服務(wù)的群體偏好KR，即為在線服務(wù)排序結(jié)果。

3.3 最大與最小KWD計(jì)算

以P作為基礎(chǔ)評(píng)價(jià)數(shù)據(jù)計(jì)算每個(gè)候選服務(wù)的最大或最小KWD時(shí)，均需從規(guī)模為|C(P)|=|C(p1)|×|C(p2)|×…×|C(pn)|的解空間中分別尋找到可令每個(gè)候選服務(wù)的KWD最大或最小化的V∈C(P)，然而C(P)的規(guī)模由P的稀疏程度決定，P越稀疏,C(P)的規(guī)模越大,且常為階乘級(jí)別。若使用窮舉法求解，將導(dǎo)致最大與最小KWD計(jì)算時(shí)間復(fù)雜度非常高。

因此，本文通過分析序數(shù)偏好的結(jié)構(gòu)特點(diǎn)以及KWD的計(jì)算特點(diǎn)，設(shè)計(jì)了可快速計(jì)算每個(gè)候選服務(wù)si的最大與最小KWD的算法，構(gòu)造了用戶的已知序數(shù)偏好px基于si的拓?fù)浣Y(jié)構(gòu)，如圖1所示。

由圖1可見，px被劃分為3個(gè)集合且|W|+|L|+|UK|=m-1：集合W={sj|(sj,si)∈px,sj∈S/si}，即集合W中所有候選服務(wù)均優(yōu)于si；集合L={sj|(si,sj)∈px,sj∈S/si}，即集合L中的所有候選服務(wù)均劣于si；集合UK={sj|(sj,si)?px∧(si,sj)?px,sj∈S/si}，即集合UK中所有候選服務(wù)與si的優(yōu)劣關(guān)系未知。

計(jì)算每個(gè)候選服務(wù)的最大或最小KWD時(shí)，首先需要分別計(jì)算每個(gè)用戶關(guān)于該服務(wù)的最大或最小uKWD，然后僅需將所有用戶關(guān)于該服務(wù)的最大或最小uKWD進(jìn)行求和，即為該候選服務(wù)的最大或最小KWD：

(5)

(6)

式(5)為用戶ux關(guān)于候選服務(wù)si的最大uKWD的計(jì)算公式；式(6)為用戶ux關(guān)于候選服務(wù)si的最小uKWD的計(jì)算公式。

在計(jì)算最大和最小uKWD的過程中，由于uKWD的計(jì)算特點(diǎn)，無需關(guān)注集合W、L、UK中候選服務(wù)的具體偏好關(guān)系，僅需計(jì)算集合W與UK中的候選服務(wù)數(shù)量即可。

基于P計(jì)算任意一個(gè)候選服務(wù)si的最大與最小KWD時(shí)，首先需要以每個(gè)用戶的px為基礎(chǔ)，將集合S/si中的所有候選服務(wù)與si逐一進(jìn)行比較，并將它們分類至集合W或L或UK中，從而計(jì)算出當(dāng)前用戶ux關(guān)于候選服務(wù)si的最大與最小uKWD，其時(shí)間復(fù)雜度為O(m)；然后，將所有用戶關(guān)于候選服務(wù)si的最大與最小uKWD進(jìn)行求和，獲得候選服務(wù)si的最大與最小KWD，其時(shí)間復(fù)雜度為O(nm)。

基于P計(jì)算群體偏好KR時(shí)，需要分別計(jì)算每個(gè)候選服的有效評(píng)價(jià)值(最大KWD),并以此為基礎(chǔ)求解KR，其時(shí)間復(fù)雜度為O(nm2+nlogn)。

4 質(zhì)量評(píng)估算法與偏好抽取策略

群體偏好KR是以當(dāng)前的P作為基礎(chǔ)評(píng)價(jià)數(shù)據(jù)，并執(zhí)行第3章提出的基于KWD在線服務(wù)評(píng)價(jià)方法所計(jì)算出的服務(wù)評(píng)價(jià)結(jié)果，但是針對(duì)一些對(duì)在線服務(wù)評(píng)價(jià)結(jié)果精度要求較高的場(chǎng)景，本文設(shè)計(jì)了用于評(píng)估KR質(zhì)量的質(zhì)量評(píng)估算法，以及由KWD驅(qū)動(dòng)的偏好抽取策。當(dāng)條件允許且用戶需要時(shí)，可通過質(zhì)量評(píng)估算法對(duì)KR的質(zhì)量進(jìn)行評(píng)估，若未能達(dá)標(biāo)，則表示當(dāng)前KR的質(zhì)量存在進(jìn)一步優(yōu)化的空間。因此可通過向部分參與評(píng)價(jià)的用戶執(zhí)行偏好抽取策略，即通過偏好查詢的方式向用戶獲取少量但關(guān)鍵的偏好信息用于快速優(yōu)化服務(wù)評(píng)價(jià)結(jié)果KR的質(zhì)量。

4.1 群體偏好KR的質(zhì)量評(píng)估算法

以P作為基礎(chǔ)評(píng)價(jià)數(shù)據(jù)計(jì)算出相應(yīng)的KR后，可使用質(zhì)量評(píng)估算法評(píng)估當(dāng)前KR的質(zhì)量是否達(dá)標(biāo)。當(dāng)質(zhì)量未達(dá)標(biāo)時(shí)，則可通過執(zhí)行偏好抽取策略，提高KR的質(zhì)量；當(dāng)質(zhì)量達(dá)標(biāo)時(shí)，則應(yīng)終止偏好抽取策略即時(shí)輸出KR，且此時(shí)的KR已為近似最優(yōu)解。

定義7初始Kendall tau勝者候選服務(wù)集合KWS={s1,s2,…,sm}，預(yù)設(shè)質(zhì)量等級(jí)參數(shù)(QCP)，且1≤|KWS|≤m，1≤QCP≤m-1。

其中，集合KWS內(nèi)的候選服務(wù)為KR中的Top-|KWS|候選服務(wù)(前|KWS|名候選服務(wù))，且集合KWS中候選服務(wù)的MaxK(si,P)均小于集合S/KWS內(nèi)所有候選服務(wù)的MinK(si,P)，即在最終的KR中，集合KWS內(nèi)的候選服務(wù)一定優(yōu)于集合S/KWS內(nèi)的所有候選服務(wù)。

通過每個(gè)候選服務(wù)當(dāng)前的MaxK(si,P)和MinK(si,P)維護(hù)KWS集合，并使用|KWS|的值表示當(dāng)前KR的質(zhì)量等級(jí)，用于判斷KR的質(zhì)量是否達(dá)標(biāo)，以及決策是否需要執(zhí)行偏好抽取策略。當(dāng)|KWS|>QCP時(shí)，則當(dāng)前KR的質(zhì)量未達(dá)標(biāo)，需繼續(xù)執(zhí)行偏好抽取策略；當(dāng)|KWS|≤QCP時(shí)，則當(dāng)前KR的質(zhì)量已達(dá)標(biāo)，可終止偏好抽取策略即時(shí)輸出KR。QCP設(shè)置得越小，則最終KR的質(zhì)量等級(jí)越高，反之亦然。

根據(jù)QCP以及每個(gè)候選服務(wù)當(dāng)前的MaxK(si,P)和MinK(si,P)維護(hù)KWS并評(píng)估KR質(zhì)量的具體過程，如算法1所示。

算法1群體偏好KR的質(zhì)量評(píng)估算法。

輸入：當(dāng)前的P、KWS集合，QCP;

輸出：False或Ture，F(xiàn)alse表示當(dāng)前KR的質(zhì)量未達(dá)標(biāo)，Ture表示當(dāng)前KR的質(zhì)量已達(dá)標(biāo)。

// ks1、ks2僅為程序中的普通變量

1. 找出KWS中MaxK(si,P)最小的候選服務(wù)，并記為ks1

2. for ks2∈KWS:ks1≠ ks2do

3. if MaxK(ks1,P)

4. KWS.remove(ks2)；//從集合KWS中刪除ks2

5. end if

6. end for

7. if|KWS|≤QCP then

8. return Ture //當(dāng)前KR質(zhì)量已達(dá)標(biāo)

9. else return False //當(dāng)前KR質(zhì)量未達(dá)標(biāo)

10. end if

質(zhì)量評(píng)估算法通過求解每個(gè)候選服務(wù)當(dāng)前的MaxK(si,P)和MinK(si,P)以維護(hù)KWS集合。然而由于MaxK(si,P)的取值范圍為0≤MaxK(si,P)≤n×(m-1)，P越稀疏時(shí)，MaxK(si,P)的初始值將越接近n×(m-1)，而MinK(si,P)越接近0，從而導(dǎo)致需要獲取大量的用戶偏好數(shù)據(jù)，才能使KR的質(zhì)量達(dá)標(biāo)。然而，本文目標(biāo)是希望使用盡可能少的用戶偏好數(shù)據(jù)即能計(jì)算出高質(zhì)量的KR，以及可以根據(jù)不同的需求靈活地控制所使用的用戶偏好數(shù)據(jù)量。因此，定義了MaxK(si,P,IUK)*，通過使用實(shí)時(shí)更新的全局參數(shù)IUK對(duì)MaxK(si,P,IUK)*的初始取值上限進(jìn)行了限定，并在質(zhì)量評(píng)估算法中使用MaxK(si,P,IUK)*代替MaxK(si,P)，縮小了求解質(zhì)量達(dá)標(biāo)的KR的原始解空間規(guī)模，算法僅需基于縮小后的解空間計(jì)算局部最優(yōu)解即可。

MaxK(si,P,IUK)*=MaxK(si,P)×IUK。

(7)

式中IUK是一個(gè)實(shí)時(shí)更新且用于控制在計(jì)算局部最優(yōu)解時(shí)的解空間規(guī)模的全局參數(shù)，對(duì)于所有候選服務(wù)均存在統(tǒng)一且實(shí)時(shí)更新的IUK，0

因此可知，若基于式(3)求解質(zhì)量達(dá)標(biāo)的KR，則其原始解空間的規(guī)模應(yīng)為m×(n×(m-1))，而若在算法1中使用式(7)代替式(3)，即通過設(shè)置全局參數(shù)IUK進(jìn)行局部求解，則可將原始解空間規(guī)模縮小為m×(n×(m-1)×IUK)。

同時(shí)，為了保證算法的準(zhǔn)確率與效率，需根據(jù)不同的IUK設(shè)置不同的QCP：即IUK越小，所使用的用戶偏好數(shù)據(jù)也越少，應(yīng)提高質(zhì)量等級(jí)以保證最終KR的質(zhì)量；而IUK越大，則所使用的用戶偏好數(shù)據(jù)也越多，應(yīng)適當(dāng)?shù)亟档唾|(zhì)量等級(jí)以提高算法的計(jì)算效率。因此，需將QCP按照QCP=(m-1)×IUK的規(guī)則設(shè)置預(yù)設(shè)值。

另外，當(dāng)出現(xiàn)任意一個(gè)候選服務(wù)si滿足如下關(guān)系式，即gi>n×(m-1)×IUK時(shí)，其中g(shù)i=MinK(si,P)+(n×(m-1)-MaxK(si,P))，則表示當(dāng)前的解空間過小，不足以計(jì)算出質(zhì)量達(dá)標(biāo)的KR，需通過提高IUK擴(kuò)大解空間規(guī)模。因此，需按照IUK=gi/(n×(m-1))的規(guī)則實(shí)時(shí)地更新IUK，從而更新所有候選服務(wù)的MaxK(si,P,IUK)*。

在實(shí)際應(yīng)用中，可根據(jù)不同的需求設(shè)置不同的IUK初始值，其值的大小決定了在計(jì)算局部最優(yōu)解時(shí)所需搜索的解空間規(guī)模，即可通過IUK靈活地控制使用的用戶偏好數(shù)據(jù)量：IUK越小，解空間規(guī)模越小，即允許忽略越多的用戶偏好數(shù)據(jù)，使得求解質(zhì)量達(dá)標(biāo)的KR所需的用戶偏好數(shù)據(jù)也越少；而IUK越大，解空間規(guī)模就越大，所需的用戶偏好數(shù)據(jù)也越多。

4.2 KWD驅(qū)動(dòng)的偏好抽取策略

偏好抽取策略通過分析已知的偏好信息和所使用的評(píng)價(jià)方法的特點(diǎn)，向用戶生成有效的偏好查詢，適當(dāng)?shù)靥岣卟煌暾玫耐暾潭?，輔助評(píng)價(jià)方法基于優(yōu)化后的不完整偏好計(jì)算出準(zhǔn)確的勝者或群體偏好。

然而，對(duì)于Borda計(jì)數(shù)、Copeland等可用于服務(wù)評(píng)價(jià)的社會(huì)選擇機(jī)制，計(jì)算哪些用戶偏好需要被抽取，即向用戶生成哪些偏好查詢才能有助于社會(huì)選擇機(jī)制計(jì)算出準(zhǔn)確的勝者是一個(gè)NP難問題[12]。盡管如此，卻并不代表偏好抽取不具有實(shí)際應(yīng)用的意義,可通過將計(jì)算高概率的勝者作為應(yīng)用偏好抽取的目的，而不是計(jì)算準(zhǔn)確的勝者[12]。

為了讓偏好抽取策略的應(yīng)用具有實(shí)際可行性，首先需要設(shè)計(jì)與所使用的評(píng)價(jià)方法相符且有效的質(zhì)量評(píng)價(jià)指標(biāo)(針對(duì)每個(gè)候選服務(wù))；其次以該質(zhì)量評(píng)價(jià)指標(biāo)作為目標(biāo)函數(shù)，通過分析已知偏好信息，向用戶生成有效的偏好查詢，優(yōu)化該目標(biāo)函數(shù)值, 從而盡快計(jì)算出近似最優(yōu)解；最后設(shè)置合適的基準(zhǔn)評(píng)估當(dāng)前勝者或群體偏好的質(zhì)量，用于判斷是否終止偏好抽取策略(即最終勝者或群體偏好是否達(dá)到近似最優(yōu)解)。

本文提出了由KWD驅(qū)動(dòng)的偏好抽取策略，使用每個(gè)候選服務(wù)的最大與最小KWD作為該候選服務(wù)的質(zhì)量評(píng)價(jià)指標(biāo)。通過實(shí)時(shí)地分析當(dāng)前的P以及每個(gè)用戶的px，分別針對(duì)每個(gè)用戶生成一個(gè)高效且穩(wěn)定的成對(duì)比較查詢，用于快速縮小該用戶關(guān)于目標(biāo)候選服務(wù)的最大uKWD或提高最小uKWD。使用4.1節(jié)中的質(zhì)量評(píng)估算法1，評(píng)估當(dāng)前群體偏好KR的質(zhì)量是否達(dá)標(biāo)。若算法1的返回值為False，則表示KR的質(zhì)量未達(dá)標(biāo)，需重復(fù)執(zhí)行上述偏好抽取策略；若返回值為Ture，則表示KR的質(zhì)量已達(dá)標(biāo)，無需繼續(xù)執(zhí)行偏好抽取策略。

如何生成有效的偏好查詢是偏好抽取策略的核心問題，本文使用成對(duì)比較作為偏好查詢的類型，其由兩個(gè)候選服務(wù)構(gòu)成(st?xsh)，其中st為目標(biāo)候選服務(wù)，sh為最大效用候選服務(wù)。

因此，首先定義了uUKN(si,px)，表示在不完整序數(shù)偏好px中與候選服務(wù)si優(yōu)劣關(guān)系未知的候選服務(wù)的數(shù)量(user Unknow Number, uUKN)；然后定義了UKN(si,P)，表示通過將每個(gè)用戶的uUKN(si,px)進(jìn)行求和計(jì)算在當(dāng)前P中候選服務(wù)si的未知量(Unknow Number, UKN)；最后以當(dāng)前的P作為基礎(chǔ)評(píng)價(jià)數(shù)據(jù)，選擇集合S中UKN最大的候選服務(wù)，并將其作為目標(biāo)候選服務(wù)st：

uUKN(si,px)=|UK|，

(8)

(9)

(10)

在確定了st后，還需以px和st為基礎(chǔ)，構(gòu)建當(dāng)前待查詢用戶ux的集合UK，并在UK中尋找可令用戶ux關(guān)于st的最大或最小uKWD大幅度縮小或提高且穩(wěn)定的最大效用候選服務(wù)sh。

因此，首先定義了Anc(si,px)表示在集合UK中優(yōu)于si的已知候選服務(wù)數(shù)量，即si的前驅(qū)(Ancestors)數(shù)量，以及Des(si,px)表示在集合UK中劣于si的已知候選服務(wù)數(shù)量，即si的后繼(Descendants)數(shù)量；然后定義了PotS(px)，其是由集合UK中前驅(qū)與后繼的數(shù)量相同或僅相差±1的中位候選服務(wù)構(gòu)成的集合；最后在集合PotS(px)中選擇Anc(si,px)最大的候選服務(wù)，并將其作為最大效用候選服務(wù)sh：

(11)

(12)

PotS(px)={si|-1≤Anc(si,px)-

Des(si,px)≤1,si∈UK},

(13)

(14)

其中，式(11)和式(12)中的1(…)為計(jì)數(shù)器，當(dāng)括號(hào)中的關(guān)系式為真時(shí)返回1，否則返回0。

例如，若當(dāng)前px的集合UK={s1,s2,s3,s4,s5,s6,s7}，且由px可推導(dǎo)出序數(shù)偏好s2?xs3?xs4，s1?xs3?xs4，s5?XS6?xs7，則集合PotS(px)={s3,s6}，sh=s3。

另外，集合PotS(px)中的候選服務(wù)均為中位候選服務(wù)，即前驅(qū)與后繼的數(shù)量相同或僅相差±1的候選服務(wù)，因此保證了對(duì)于生成的偏好查詢st?xsh，無論用戶的回答是肯定或否定，均能有效地縮小或提高最大或最小uKWD，達(dá)到快速且穩(wěn)定地提高KR質(zhì)量的目標(biāo)。

將質(zhì)量評(píng)估算法1與由KWD驅(qū)動(dòng)的偏好抽取策略相結(jié)合，計(jì)算最終服務(wù)評(píng)價(jià)結(jié)果KR的具體過程如算法2所示。

算法2最終服務(wù)評(píng)價(jià)結(jié)果KR的算法。

輸入：初始的P、KWS、全局參數(shù)IUK;

輸出：最終的群體偏好KR，即最終服務(wù)評(píng)價(jià)結(jié)果。

1. while算法1==False do //調(diào)用算法1，并根據(jù)返回值判斷當(dāng)前KR的質(zhì)量是否達(dá)標(biāo)

2. for x=1 to n do //遍歷用戶集合U中的所有用戶

3. 基于式(10)與式(14)分別計(jì)算用戶ux的st與sh

4. 向用戶進(jìn)行偏好查詢，并更新px

5. end for

6. end while

7. returnKR//輸出最終的群體偏好KR

5 實(shí)驗(yàn)

根據(jù)第3章提出的基于KWD的在線服務(wù)評(píng)價(jià)方法以及第4章提出的質(zhì)量評(píng)估算法與偏好抽取策略，設(shè)計(jì)實(shí)現(xiàn)了面向不完整序數(shù)偏好的在線服務(wù)評(píng)價(jià)方法并進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)環(huán)境為PC機(jī)、Windows 10系統(tǒng)、Core i5處理器、8 GB內(nèi)存。另外，為保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，所有實(shí)驗(yàn)均被重復(fù)運(yùn)行30次，并取每個(gè)指標(biāo)的平均值作為實(shí)驗(yàn)結(jié)果。

為驗(yàn)證本文方法的有效性和效率，實(shí)驗(yàn)分別采用AGH、Dublin、Sushi真實(shí)數(shù)據(jù)集以及Mallows[23]人工合成數(shù)據(jù)集。其中：AGH數(shù)據(jù)集由146條關(guān)于9門課程的完整序數(shù)偏好組成。Dublin數(shù)據(jù)集由3 800條關(guān)于9位候選人的完整序數(shù)偏好組成。Sushi數(shù)據(jù)集由5 000條關(guān)于10種壽司的完整序數(shù)偏好組成。Mallows是一個(gè)在序數(shù)偏好研究中被廣泛應(yīng)用及認(rèn)可的偏好模型[24]，其可通過設(shè)置不同的參數(shù)σ與φ，隨機(jī)生成屬于各類不同分布情況下的序數(shù)偏好數(shù)據(jù)集，其中σ為一個(gè)由m個(gè)候選服務(wù)構(gòu)成的完整序數(shù)偏好；φ∈(0,1]為離散參數(shù)，其控制了隨機(jī)生成的用戶序數(shù)偏好與σ的離散程度，當(dāng)φ→0時(shí)，所生成的用戶序數(shù)偏好均完全一致，當(dāng)φ=1時(shí)，所生成的用戶序數(shù)偏好則為一個(gè)均勻分布。通過設(shè)置不同的φ、用戶數(shù)量n、服務(wù)數(shù)量m得到的Mallows人工合成數(shù)據(jù)集，用于驗(yàn)證本文方法的普適性、有效性以及效率。

首先，本文分別以上述完整數(shù)據(jù)集為基礎(chǔ)隨機(jī)生成了相對(duì)應(yīng)的且偏好完整度為5%、10%、15%、20%、25%的不完整數(shù)據(jù)集，并以此作為評(píng)價(jià)方法的初始輸入P；然后，分別設(shè)計(jì)了2個(gè)在線服務(wù)評(píng)價(jià)方案(記為方案F1、方案F2)用于進(jìn)行實(shí)驗(yàn)：其中方案F1直接將當(dāng)前已知的不完整數(shù)據(jù)集P作為輸入，然后僅使用本文第3章所提出的基于KWD的在線服務(wù)評(píng)價(jià)方法計(jì)算在線服務(wù)評(píng)價(jià)結(jié)果KR；方案F2則是在方案F1的基礎(chǔ)上配合執(zhí)行在第4章提出的質(zhì)量評(píng)估算法與偏好抽取策略(即執(zhí)行算法2)，希望通過進(jìn)行少量但關(guān)鍵的偏好查詢實(shí)現(xiàn)對(duì)服務(wù)評(píng)價(jià)結(jié)果KR質(zhì)量的快速優(yōu)化。在利用方案F2進(jìn)行實(shí)驗(yàn)時(shí)：會(huì)將完整數(shù)據(jù)集視為待查詢數(shù)據(jù)集，即將每條序數(shù)偏好模擬為一個(gè)用戶，用于回答偏好抽取策略所生成的偏好查詢；同時(shí)還會(huì)按照如下規(guī)則設(shè)置全局參數(shù)IUK的初始值，例如，若不完整數(shù)據(jù)集初始的完整度為5%，則將全局參數(shù)IUK設(shè)置為0.1、若初始偏好完整度為10%，則將全局參數(shù)IUK設(shè)置為0.15。

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

基于Kemeny社會(huì)選擇機(jī)制計(jì)算的Kemeny排序是真相排序的最大似然估計(jì)，其不僅在群體決策中得到廣泛應(yīng)用[25]，還被用于服務(wù)評(píng)價(jià)并取得良好效果[10,19]。因此，實(shí)驗(yàn)將Kemeny方法作為實(shí)驗(yàn)比較的基準(zhǔn)方法，將本文方法所計(jì)算的KR與Kemeny排序相對(duì)比，計(jì)算它們之間的相似度，用于驗(yàn)證本文方法的有效性。

實(shí)驗(yàn)首先使用Kemeny方法基于每個(gè)數(shù)據(jù)集的完整序數(shù)偏好計(jì)算相應(yīng)的Kemeny排序，并將其作為精確最優(yōu)解(Exact Optimal Solution, EOS)；然后分別應(yīng)用方案F1與方案F2計(jì)算服務(wù)評(píng)價(jià)結(jié)果KR；最后使用Kendall tau距離度量KR與EOS之間的相似度，記為S(KR,EOS)。S(KR,EOS)越大，KR與EOS越相似，即KR與EOS之間的Kendall tau距離越小，反之亦然。

實(shí)驗(yàn)首先基于AGH、Dublin、Sushi數(shù)據(jù)集分別執(zhí)行了方案F1和F2，并記錄了在初始偏好完整度為5%、10%、15%、20%、25%時(shí)的S(KR,EOS)，如圖2a所示；然后采用5個(gè)離散參數(shù)φ值，在包含10個(gè)候選服務(wù)、100個(gè)用戶的Mallows數(shù)據(jù)集分別執(zhí)行方案F1和F2，并記錄在初始偏好完整度為5%、10%、15%、20%、25%時(shí)的S(KR,EOS)，如圖2b所示。

由圖2可見，不論是在AGH、Dublin、Sushi數(shù)據(jù)集，還是5個(gè)Mallows數(shù)據(jù)集中，方案F1僅依據(jù)初始的不完整數(shù)據(jù)集就能夠直接計(jì)算出較高的S(KR,EOS)的服務(wù)評(píng)價(jià)結(jié)果，并且在應(yīng)用方案F2后可以發(fā)現(xiàn)最終的S(KR,EOS)也會(huì)較方案F1有所提高。另外，由圖2b可見，除了數(shù)據(jù)集的初始偏好完整度會(huì)影響S(KR,EOS)的高低之外，數(shù)據(jù)集的離散參數(shù)φ也是影響S(KR,EOS)的主要因素，隨著離散參數(shù)φ增大至接近1時(shí)(即用戶偏好趨于均勻分布)，若單純應(yīng)用方案F1,可能導(dǎo)致S(KR,EOS)出現(xiàn)下降，但可通過應(yīng)用方案F2在一定程度上緩解該問題。另外，根據(jù)文獻(xiàn)[12]和文獻(xiàn)[24]的結(jié)論可知，在現(xiàn)實(shí)中用戶偏好的離散參數(shù)φ并不會(huì)趨于1(即用戶偏好不會(huì)符合均勻分布)，通常為φ≤0.7，從而也進(jìn)一步說明了本文方法的有效性。

同時(shí)，還生成了25個(gè)關(guān)于不同用戶數(shù)量n和不同服務(wù)數(shù)量m，初始偏好完整度為5%，參數(shù)φ為0.7的Mallows數(shù)據(jù)集，用于驗(yàn)證本文方法在不同樣本規(guī)模下的有效性，如圖3所示。

由圖3可見，不論是方案F1還是F2，均會(huì)隨著用戶數(shù)量n的增加使得S(KR,EOS)增加；而隨著服務(wù)數(shù)量m的增加，S(KR,EOS)并不會(huì)發(fā)生明顯的下降。考慮到在線服務(wù)場(chǎng)景中的用戶數(shù)量和服務(wù)數(shù)量通常較大且會(huì)動(dòng)態(tài)地發(fā)生變化，S(KR,EOS)只會(huì)因用戶數(shù)量的增加而增加，并不會(huì)因服務(wù)數(shù)量的變化而導(dǎo)致S(KR,EOS)明顯下降，該結(jié)果進(jìn)一步驗(yàn)證了本文方法對(duì)在線服務(wù)評(píng)價(jià)的有效性。

此外，為了分析本文方法在用戶偏好差異較大時(shí)的有效性，基于原始的Kendall tau距離定義了DIFF(vx,vy)=KT(vx,vy)/(m×(m-1)/2)，用于計(jì)算兩個(gè)用戶偏好之間的差異程度。其中，KT(vx,vy)為vx與vy之間的逆序數(shù)，即vx與vy的真實(shí)Kendall tau距離；(m×(m-1)/2)為vx與vy的逆序數(shù)取值上限，即vx與vy的理論最大Kendall tau距離。由此可見，DIFF(vx,vy)越大，vx與vy之間的差異也越大，反之亦然。

因此，實(shí)驗(yàn)以5個(gè)采用不同參數(shù)φ且包含10個(gè)候選服務(wù)、5 000個(gè)用戶的Mallows數(shù)據(jù)集為基礎(chǔ)。通過對(duì)每個(gè)數(shù)據(jù)集均進(jìn)行5 000次的隨機(jī)抽樣，每次隨機(jī)選取2個(gè)用戶，并計(jì)算出相應(yīng)的DIFF(vx,vy)，用于反映該數(shù)據(jù)集中的用戶偏好之間的差異程度，如圖4所示。

由圖4可見，在Mallows數(shù)據(jù)集中，隨著參數(shù)φ的增加，用戶偏好之間的差異程度也會(huì)逐步擴(kuò)大。由圖2b可知，S(KR,EOS)雖然會(huì)因參數(shù)φ的增加而發(fā)生下降，在參數(shù)φ=0.9時(shí)，即使僅執(zhí)行方案F1，S(KR,EOS)仍能夠保持在80%以上，并且當(dāng)執(zhí)行方案F2時(shí)，S(KR,EOS)能夠被提高至85%左右。另外，根據(jù)圖3的結(jié)果可知，在使用方案F1進(jìn)行服務(wù)評(píng)價(jià)時(shí)，隨著用戶數(shù)量的增加，S(KR,EOS)也會(huì)隨之增加且提升明顯，考慮到真實(shí)的互聯(lián)網(wǎng)應(yīng)用場(chǎng)景中的用戶數(shù)量總是較多且增長(zhǎng)較快，說明本文方法即使在用戶偏好差異較大時(shí)除了可以通過執(zhí)行方案F2提高評(píng)價(jià)結(jié)果質(zhì)量，還能依靠用戶數(shù)量的增加來緩解因用戶偏好趨于均勻分布而造成的評(píng)價(jià)結(jié)果質(zhì)量下降的問題。

5.2 偏好完整度實(shí)驗(yàn)

為驗(yàn)證本文方法在處理不完整序數(shù)偏好時(shí)的性能，實(shí)驗(yàn)首先基于AGH、Dublin、Sushi數(shù)據(jù)集執(zhí)行方案F2，并記錄了在初始偏好完整度為5%、10%、15%、20%、25%時(shí)計(jì)算最終服務(wù)評(píng)價(jià)結(jié)果KR所使用的偏好完整度，如圖5a所示；然后采用5個(gè)φ值，在包含10個(gè)候選服務(wù)、100個(gè)用戶的Mallows數(shù)據(jù)集執(zhí)行方案F2，并記錄了在初始偏好完整度為5%、10%、15%、20%、25%時(shí)計(jì)算最終服務(wù)評(píng)價(jià)結(jié)果KR所使用的偏好完整度，如圖5b所示。

由圖5可見，不論是在AGH、Dublin、Sushi數(shù)據(jù)集，還是5個(gè)Mallows數(shù)據(jù)集，PI(n,m,P)均會(huì)與初始全局參數(shù)IUK保持較小的差距。在大多數(shù)情況下PI(n,m,P)會(huì)小于IUK的初始值，僅在少數(shù)情況PI(n,m,P)會(huì)大于IUK的初始值，這是因?yàn)镮UK是一個(gè)能夠?qū)崟r(shí)自動(dòng)更新的全局參數(shù)，如果出現(xiàn)因IUK的初始值設(shè)置過小而導(dǎo)致解空間過小，無法計(jì)算出質(zhì)量達(dá)標(biāo)的KR時(shí)，IUK會(huì)通過自動(dòng)更新并擴(kuò)大解空間以完成求解。另外，由5.1節(jié)中的實(shí)驗(yàn)結(jié)果可知，按照預(yù)設(shè)規(guī)則設(shè)置IUK就已經(jīng)能夠?qū)崿F(xiàn)高質(zhì)量的求解，僅在少數(shù)的情況下，例如當(dāng)用戶偏好趨于均勻分布且用戶數(shù)量也較少時(shí)才可能需要考慮通過提高IUK來提升最終服務(wù)評(píng)價(jià)結(jié)果KR的高質(zhì)量。

5.3 性能測(cè)試

為驗(yàn)證本文方法的效率，實(shí)驗(yàn)首先基于AGH、Dublin、Sushi數(shù)據(jù)集分別執(zhí)行方案F1和F2，并記錄了初始偏好完整度為5%、10%、15%、20%、25%時(shí)計(jì)算最終服務(wù)評(píng)價(jià)結(jié)果KR的運(yùn)行時(shí)間，如圖6a所示；然后采用5個(gè)φ值，在包含10個(gè)候選服務(wù)、100個(gè)用戶的Mallows數(shù)據(jù)集分別執(zhí)行方案F1和F2，并記錄初始偏好完整度為5%、10%、15%、20%、25%時(shí)計(jì)算最終服務(wù)評(píng)價(jià)結(jié)果KR的運(yùn)行時(shí)間，如圖6b所示。

由圖6可見，不論是在AGH、Dublin、Sushi數(shù)據(jù)集，還是5個(gè)Mallows數(shù)據(jù)集中，方案F1和F2均能保持較高的運(yùn)行效率，雖然運(yùn)行時(shí)間會(huì)隨著數(shù)據(jù)集的初始偏好完整度或者離散參數(shù)φ的提高而增加，但是并不會(huì)導(dǎo)致運(yùn)行時(shí)間劇增。

此外，本文還生成了25個(gè)關(guān)于不同用戶數(shù)量n和不同服務(wù)數(shù)量m，初始偏好完整度為5%，參數(shù)φ為0.7的Mallows數(shù)據(jù)集，用于驗(yàn)證本文方法在不同樣本規(guī)模下的效率，如圖7所示。

由圖7可見，隨著用戶數(shù)量和服務(wù)數(shù)量的增加，方案F1和F2的運(yùn)行時(shí)間均隨之增加，但是在大多數(shù)情況下它們均能保持線性增長(zhǎng)?？紤]在線服務(wù)評(píng)價(jià)場(chǎng)景中用戶數(shù)量和服務(wù)數(shù)量通常較大，該結(jié)果進(jìn)一步驗(yàn)證了本文方法對(duì)在線服務(wù)評(píng)價(jià)的計(jì)算有效性。

6 結(jié)束語

本文提出一種面向不完整序數(shù)偏好的在線服務(wù)評(píng)價(jià)方法，以解決不完整序數(shù)偏好場(chǎng)景下的在線服務(wù)評(píng)價(jià)問題。方法通過定義KWD來量化每個(gè)候選服務(wù)的質(zhì)量，并設(shè)計(jì)了基于KWD的近似算法用于計(jì)算服務(wù)評(píng)價(jià)結(jié)果KR，從而實(shí)現(xiàn)了在不完整序數(shù)偏好場(chǎng)景下的在線服務(wù)評(píng)價(jià)。同時(shí)還設(shè)計(jì)了質(zhì)量評(píng)估算法與偏好抽取策略，用于在需要時(shí)評(píng)估和快速優(yōu)化服務(wù)評(píng)價(jià)結(jié)果KR的質(zhì)量，為不完整序數(shù)偏好場(chǎng)景下的在線服務(wù)評(píng)價(jià)提供了一種新的思路。理論分析及實(shí)驗(yàn)驗(yàn)證表明了該方法的有效性與合理性。但是，本方法在進(jìn)行在線服務(wù)評(píng)價(jià)時(shí)并未考慮用戶偏好可能會(huì)出現(xiàn)平局的情況，即用戶可能會(huì)認(rèn)為2個(gè)或多個(gè)候選服務(wù)之間無優(yōu)劣差異。因此，下一步的工作將結(jié)合平局的情況，研究更加通用的在線服務(wù)評(píng)價(jià)方法。