利用屬性條件偏好推理的在線服務(wù)群體選擇

梁菁霞,付曉東,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ù)提供者以互聯(lián)網(wǎng)為載體,向用戶提供的服務(wù)稱為在線服務(wù)[1].隨著信息技術(shù)和通信技術(shù)的發(fā)展,用戶之間的交流越來(lái)越方便.服務(wù)提供商面向的用戶從個(gè)體轉(zhuǎn)向群體的情況越來(lái)越多,在線服務(wù)群體選擇就是為用戶群體選擇其感興趣的在線服務(wù).主要應(yīng)用在團(tuán)建活動(dòng)、拼團(tuán)活動(dòng)等多人活動(dòng)情境下.例如拼多多的拼團(tuán)活動(dòng)(1)https://www.pinduoduo.com,飛豬的酒店團(tuán)購(gòu)活動(dòng)(2)https://tuan.fliggy.com,攜程的私家團(tuán)游(3)https://vacations.ctrip.com/privategroup,美團(tuán)的多人休閑娛樂(lè)活動(dòng)(4)https://cq.meituan.com/xiuxianyule/c21193/等等.為群體選擇服務(wù)時(shí),考慮群體中個(gè)體用戶的偏好,用聚合策略將用戶的偏好聚合,得到群體的在線服務(wù)選擇結(jié)果.面對(duì)大量在線服務(wù),在線服務(wù)群體選擇方法能夠有效地為群體選擇在線服務(wù),為用戶節(jié)省時(shí)間和精力.

在線服務(wù)群體選擇方法根據(jù)聚合策略將個(gè)體用戶對(duì)服務(wù)的偏好進(jìn)行聚合,得到群體對(duì)服務(wù)的選擇結(jié)果.在線服務(wù)群體選擇分兩步:首先,對(duì)個(gè)體用戶的偏好建模,獲取個(gè)體用戶對(duì)服務(wù)的偏好;然后聚合個(gè)體用戶的服務(wù)偏好,得到群體的服務(wù)選擇結(jié)果.個(gè)體用戶的偏好建模、推理是在線服務(wù)群體選擇中的一個(gè)基礎(chǔ)工作[2].在服務(wù)選擇的場(chǎng)景中,用戶不僅考慮對(duì)服務(wù)的偏好,通常還會(huì)考慮對(duì)服務(wù)的多個(gè)屬性的偏好.用戶更喜歡用定性的方式而不是定量的方式來(lái)表達(dá)自己的偏好.例如,當(dāng)用戶在團(tuán)購(gòu)平臺(tái)訂購(gòu)酒店時(shí),會(huì)考慮酒店的位置、裝修風(fēng)格和是否提供餐飲等屬性的偏好.用戶通常用“在酒店位置臨近購(gòu)物中心時(shí),相比于提供餐飲的酒店更喜歡不提供餐飲的酒店”來(lái)描述偏好.考慮服務(wù)的所有屬性的偏好,其結(jié)構(gòu)比較復(fù)雜.給定服務(wù)屬性的有限值域上的笛卡爾積稱為服務(wù)在屬性值上的組合結(jié)構(gòu)[3],也稱服務(wù)的屬性值組合空間.若酒店3個(gè)屬性的取值都有3個(gè),那么組成的備選服務(wù)屬性值組合方案有33=27種.在有條件偏好的屬性組合結(jié)構(gòu)背景下,導(dǎo)致經(jīng)典決策理論中的效用函數(shù)難以對(duì)所有的服務(wù)屬性進(jìn)行建模[4],也無(wú)法根據(jù)已有的屬性偏好對(duì)未體驗(yàn)服務(wù)偏好進(jìn)行推理.序數(shù)偏好是根據(jù)用戶對(duì)服務(wù)各全面綜合考慮,給候選服務(wù)排序的偏好表示方式.序數(shù)偏好對(duì)用戶的要求非常高,并且面對(duì)未體驗(yàn)服務(wù)無(wú)法直接進(jìn)行排序,需要借助其他方式來(lái)預(yù)測(cè)用戶對(duì)其偏好.采用協(xié)同過(guò)濾等方法對(duì)未體驗(yàn)服務(wù)進(jìn)行偏好預(yù)測(cè),預(yù)測(cè)結(jié)果與用戶真實(shí)偏好會(huì)產(chǎn)生偏差,在聚合過(guò)程中影響群體對(duì)服務(wù)的偏好.現(xiàn)有在線服務(wù)群體選擇模型中,沒(méi)有根據(jù)屬性條件偏好對(duì)服務(wù)偏好進(jìn)行推理的方法.此外,聚合策略需考慮個(gè)體用戶的偏好建模方式,以及平衡群體中個(gè)體用戶的偏好以達(dá)成群體共識(shí).

考慮上述問(wèn)題,提出了一種利用屬性條件偏好推理的在線服務(wù)群體選擇方法.方法使用條件偏好網(wǎng)絡(luò)[5](Conditional Preference networks,CP-nets)的頂點(diǎn)表示服務(wù)屬性數(shù)據(jù),根據(jù)用戶對(duì)屬性的偏好和條件依賴關(guān)系構(gòu)建條件偏好表(CPT),有效解決服務(wù)屬性值有組合結(jié)構(gòu)情況下,用戶表示偏好困難,以及無(wú)法根據(jù)屬性偏好對(duì)服務(wù)偏好進(jìn)行偏好推理的問(wèn)題;在此基礎(chǔ)上使用社會(huì)選擇函數(shù)Ranked Pairs[6]對(duì)個(gè)體用戶的選擇結(jié)果進(jìn)行聚合,形成群體的在線服務(wù)選擇結(jié)果.

2 相關(guān)工作

近年來(lái),國(guó)內(nèi)外學(xué)者圍繞服務(wù)選擇展開(kāi)了一系列的研究,現(xiàn)服務(wù)選擇方法已經(jīng)較為成熟.目前的在線服務(wù)選擇方法主要有:基于用戶偏好的服務(wù)選擇[7]、基于聚類的服務(wù)選擇[8]、多標(biāo)準(zhǔn)決策服務(wù)選擇[9]、多目標(biāo)進(jìn)化算法服務(wù)選擇[10]等.與基于個(gè)體用戶的服務(wù)選擇方法相比,基于群體的服務(wù)選擇方法研究較少,但基于群體的在線服務(wù)在生活中越來(lái)越多,逐漸受到了服務(wù)選擇研究人員的關(guān)注.在線服務(wù)群體選擇方法主要有:基于服務(wù)信譽(yù)的方法、基于協(xié)同過(guò)濾的方法和其他方法.

信譽(yù)是服務(wù)若干信用行為累積的結(jié)果[11].基于服務(wù)信譽(yù)的方法是計(jì)算群體對(duì)服務(wù)的信譽(yù)度來(lái)進(jìn)行服務(wù)選擇.鄭蘇蘇等人[11]提出了一種基于Kendall tua距離的在線服務(wù)信譽(yù)度量方法,根據(jù)用戶對(duì)服務(wù)的評(píng)分信息,計(jì)算群體的在線服務(wù)信譽(yù)度,從而進(jìn)行在線服務(wù)的群體選擇.VectorTrust[12]是一種基于信任向量的信任管理方案,它利用Bellman-Ford 的算法進(jìn)行快速輕量級(jí)的信任評(píng)分聚合,具有本地化和分布式并發(fā)通信功能.

基于協(xié)同過(guò)濾的方法是尋找相似用戶或相似群體,使用相似用戶的偏好或相似群體的偏好來(lái)進(jìn)行服務(wù)選擇.Lee等人[13]根據(jù)成員組織的群相似性指標(biāo)的組合,選擇與新群體相似群體的協(xié)同過(guò)濾群體推薦方法.Bok等人[14]提出一種使用個(gè)體用戶信息和社交網(wǎng)絡(luò)協(xié)同過(guò)濾的群體服務(wù)推薦方法,利用與群體用戶相似的其他用戶的信息來(lái)為群體推薦服務(wù).

此外,曾蘇夢(mèng)等人[15]根據(jù)個(gè)體用戶對(duì)服務(wù)的優(yōu)先級(jí)計(jì)算群體對(duì)服務(wù)的滿意度,根據(jù)服務(wù)滿意度進(jìn)行服務(wù)選擇.Xie等人[16]利用豐富的異構(gòu)信息,提出了一種在異構(gòu)信息網(wǎng)絡(luò)中基于混搭群體偏好的服務(wù)推薦方法.考慮用戶群體之間的準(zhǔn)確性和公平性,Xiao等人[17]將概率模型與聯(lián)盟博弈策略相結(jié)合提出一種新的服務(wù)群體推薦方法.Zhou等人[18]提出了一種專注于網(wǎng)絡(luò)社會(huì)計(jì)算的模型,該模型將大規(guī)模群體決策集成到網(wǎng)絡(luò)支持的在線服務(wù)社會(huì)推薦中.

上述在線服務(wù)群體選擇研究使用評(píng)分信息和序數(shù)偏好來(lái)表示用戶對(duì)服務(wù)的偏好,以及提取用戶間的關(guān)系.評(píng)分信息和序數(shù)偏好都無(wú)法表示用戶對(duì)服務(wù)各個(gè)屬性的偏好,無(wú)法對(duì)未體驗(yàn)服務(wù)的偏好進(jìn)行推理.借助協(xié)同過(guò)濾等方法得到的預(yù)測(cè)偏好與真實(shí)偏好有誤差,預(yù)測(cè)偏好會(huì)影響群體對(duì)服務(wù)的偏好,從而影響群體的服務(wù)選擇結(jié)果.考慮以上研究中存在的不足,本文充分考慮用戶屬性的條件偏好,提出一種利用服務(wù)屬性條件偏好推理的在線服務(wù)選擇方法.

本文的主要工作如下:1)使用CP-nets來(lái)對(duì)具有組合結(jié)構(gòu)的服務(wù)屬性進(jìn)行偏好表示;2)通過(guò)CP-nets的語(yǔ)義和性質(zhì)推導(dǎo)出用戶對(duì)服務(wù)的偏好;3)使用社會(huì)選擇函數(shù)Ranked Pairs將個(gè)體用戶的服務(wù)選擇結(jié)果聚合,最終形成群體的服務(wù)選擇結(jié)果.此外,通過(guò)理論分析和實(shí)驗(yàn)驗(yàn)證了該方法的合理性和有效性.

3 問(wèn)題描述

3.1 問(wèn)題定義

用戶對(duì)服務(wù)的各個(gè)屬性有相應(yīng)的偏好,根據(jù)用戶對(duì)服務(wù)屬性的條件偏好推導(dǎo)出用戶對(duì)服務(wù)的偏好,即得到個(gè)體用戶的服務(wù)選擇結(jié)果.在線服務(wù)群體選擇聚合策略將個(gè)體用戶的選擇結(jié)果聚合,得到在線服務(wù)的排序列表,作為群體的選擇結(jié)果.以下對(duì)在線服務(wù)群體選擇問(wèn)題進(jìn)行相關(guān)定義.

定義1.用戶的集合為U={ui|i=1,2,…,n},在線服務(wù)的集合為S={sa|a=1,2,…,m}.其中,n表示群體中用戶的數(shù)量,m表示在線服務(wù)的數(shù)量.

服務(wù)sa包含所有服務(wù)屬性,集合S中的服務(wù)sa在集合Ω中有唯一的服務(wù)屬性值組合ot與之對(duì)應(yīng).

定義5.Pi=oσ(1)?ioσ(2)?i…?ioσ(t)表示用戶ui對(duì)集合Ω中所有服務(wù)屬性值組合的偏好.其中,oσ(1)?ioσ(2)表示用戶ui認(rèn)為服務(wù)屬性值組合oσ(1)優(yōu)于oσ(2),σ(t)表示屬性值組合的序號(hào).

定義6.根據(jù)Pi對(duì)集合S中的服務(wù)排序,得到用戶ui的在線服務(wù)選擇結(jié)果,將其記為L(zhǎng)i=sσ(1)?isσ(2)?i…?isσ(1).其中,sσ(1)?isσ(2)表示用戶ui認(rèn)為服務(wù)sσ(1)優(yōu)于sσ(2),l=1,2,…,m,σ(l)表示服務(wù)的序號(hào).群體的在線服務(wù)選擇結(jié)果記為L(zhǎng)G.

根據(jù)上述定義,本文將為集合U中的所有用戶組成的群體從集合S中選擇適合群體的服務(wù)排序作為群體的服務(wù)選擇結(jié)果.首先根據(jù)用戶ui對(duì)屬性Xj的偏好,對(duì)其進(jìn)行推理得到用戶ui對(duì)服務(wù)屬性值組合的偏好Pi,從而得到用戶ui對(duì)服務(wù)的偏好Li.然后通過(guò)聚合策略Ranked Pairs將用戶對(duì)服務(wù)的偏好Li聚合得到群體的服務(wù)選擇結(jié)果LG.

3.2 問(wèn)題示例

表1 用戶對(duì)酒店屬性的偏好Table 1 Users′ preference about hotel attributes

表2 酒店-屬性值組合Table 2 Combination of hotels-attribute values

如表2所示,酒店有3種屬性,每種屬性擁有相對(duì)應(yīng)的屬性值.酒店與其屬性值組合相對(duì)應(yīng).以表2中的屬性值組合為基礎(chǔ),根據(jù)用戶對(duì)屬性值組合偏好關(guān)系Pi對(duì)表2中的酒店進(jìn)行排序,得到用戶的酒店選擇結(jié)果Li.聚合3位用戶的Li可獲得由三個(gè)用戶組成的群體的酒店選擇結(jié)果 .

用戶在對(duì)服務(wù)進(jìn)行選擇時(shí),會(huì)根據(jù)自身的需求對(duì)服務(wù)的屬性有不同的要求和偏好.上例中用戶對(duì)酒店的首要需求是位置要靠近購(gòu)物中心.那么用戶面對(duì)兩家其他條件相同而位置不同的酒店時(shí),用戶優(yōu)先選擇位置更符合他們期望的一家酒店.若用戶對(duì)酒店位置的要求不嚴(yán)格,那么他們對(duì)是否提供餐飲、裝修風(fēng)格也有不同的偏好.根據(jù)用戶對(duì)屬性的偏好來(lái)進(jìn)行服務(wù)選擇,更契合用戶的偏好.

現(xiàn)有服務(wù)群體選擇方法中對(duì)用戶的偏好表示和建模的方式主要有數(shù)值評(píng)分、序數(shù)偏好和效用函數(shù).以上方法中效用函數(shù)對(duì)具有組合結(jié)構(gòu)的服務(wù)屬性偏好表示困難,其他方法沒(méi)有考慮到服務(wù)屬性的偏好.此外,若用戶未體驗(yàn)過(guò)部分服務(wù),無(wú)法直接對(duì)未體驗(yàn)服務(wù)進(jìn)行評(píng)價(jià),現(xiàn)有方法也不能對(duì)其未體驗(yàn)服務(wù)的偏好進(jìn)行推理.為了解決以上問(wèn)題,需要考慮服務(wù)本身屬性的偏好外,還需要結(jié)合屬性的偏好來(lái)對(duì)服務(wù)的偏好進(jìn)行推理.本文提出的利用屬性條件偏好推理的在線服務(wù)群體選擇方法,不僅能夠準(zhǔn)確表示用戶對(duì)服務(wù)屬性的偏好,還可以根據(jù)屬性偏好對(duì)服務(wù)的偏好進(jìn)行推理,使得群體選擇結(jié)果更符合大多數(shù)用戶的偏好.

4 利用偏好推理的在線服務(wù)群體選擇

基于以上分析,使用CP-nets表示個(gè)體用戶對(duì)服務(wù)屬性的偏好,根據(jù)CP-nets的語(yǔ)義和特征對(duì)服務(wù)屬性值組合的偏好進(jìn)行推理,得到用戶對(duì)服務(wù)屬性值組合的偏好關(guān)系,以此構(gòu)建CP-nets的導(dǎo)出圖結(jié)構(gòu),根據(jù)導(dǎo)出圖的拓?fù)渑判驅(qū)Ψ?wù)進(jìn)行排序,得到個(gè)體用戶的在線服務(wù)選擇結(jié)果.然后,使用社會(huì)選擇函數(shù)Ranked Pairs聚合個(gè)體用戶的服務(wù)偏好,得到群體的選擇結(jié)果.

4.1 用戶偏好表示

用戶對(duì)于自己的偏好表達(dá)更擅長(zhǎng)于用定性而不是定量的方式.例如,用戶在選擇酒店時(shí),某用戶表示:“若在其他條件相同的情況下,相比于臨近旅游景區(qū)的酒店,我更喜歡臨近購(gòu)物中心的酒店.”某女士在預(yù)訂機(jī)票時(shí)表示:“在非工作日,相比于東航更喜歡南航.”在進(jìn)行服務(wù)選擇時(shí),用戶更擅長(zhǎng)于表示服務(wù)屬性的偏好.在數(shù)量龐大的在線服務(wù)背景下,為了能夠簡(jiǎn)潔地表示服務(wù)屬性的偏好,本文使用CP-nets[5]來(lái)表示用戶的偏好.

CP-nets以一種自然、清晰方式來(lái)表示條件偏好.從結(jié)構(gòu)上看CP-nets是一個(gè)有向圖,使用圖結(jié)構(gòu)來(lái)表示用戶偏好具有很強(qiáng)的邏輯性和緊湊性.在有向圖中,頂點(diǎn)表示服務(wù)的屬性,有向邊表示屬性之間的依賴關(guān)系,每個(gè)頂點(diǎn)所對(duì)應(yīng)的條件偏好表表示用戶對(duì)每個(gè)屬性在不同取值下的偏好.CP-nets也是通過(guò)稀疏的屬性依賴關(guān)系來(lái)表達(dá)屬性值組合之間的占優(yōu)關(guān)系[19].CP-nets的相關(guān)定義如下所示.

定義7(CP-nets[20,21]). CP-nets是一個(gè)三元組(Φ,CE,CPT),結(jié)構(gòu)上是一個(gè)有向圖,將條件偏好網(wǎng)絡(luò)記為Ni(i=1,2,…,n).其中:

1)Φ表示CP-nets的頂點(diǎn)集,也是在線服務(wù)的屬性集.Dom(Xj)表示服務(wù)屬性Xj上的有限值域.

2)CE={|Xj′,Xj∈Φ}是有向邊集,若∈CE,表示屬性Xj′和Xj之間有依賴關(guān)系,也稱Xj′是Xj的一個(gè)父親,記為Pare(Xj)=Xj′;

3)頂點(diǎn)Xj對(duì)應(yīng)一個(gè)條件偏好表,用CPT(Xj)表示.若Pare(Xj)=Xj′,則CPT(Xj)的含義為屬性Xj的父屬性Xj′在不同取值下,用戶對(duì)CPT(Xj)中屬性值的偏好排序.

例2. 根據(jù)定義7和表1中用戶的偏好,對(duì)用戶構(gòu)建CP-nets,如圖1所示.

圖1 用戶u1的CP-netN1Fig.1 CP-net N1 of user u1

4.2 個(gè)體用戶在線服務(wù)選擇

CP-nets作為表示在線服務(wù)屬性條件偏好的工具,需要對(duì)其進(jìn)行推理,得到用戶對(duì)服務(wù)屬性值組合的偏好關(guān)系.然后根據(jù)用戶對(duì)服務(wù)屬性值組合的偏好,得到用戶對(duì)服務(wù)的偏好關(guān)系.在此之前需要了解屬性值組合之間存在的關(guān)系,相關(guān)定義如下.

定義9(導(dǎo)出圖[23]). 設(shè)N為CP-net,則有向圖N′=(Ω,IE)稱作N的導(dǎo)出圖,其中Ω是屬性值組合空間,IE是誘導(dǎo)的邊集合,也稱作翻轉(zhuǎn)關(guān)系集合.

圖2 N1的偏好導(dǎo)出圖Fig.2 Induced preference diagram of N1

算法1建立了一個(gè)迭代方案,每經(jīng)過(guò)一次迭代,就根據(jù)用戶ui對(duì)屬性的條件偏好構(gòu)建CP-netsNi,并根據(jù)Ni對(duì)服務(wù)偏好進(jìn)行推理,得到用戶對(duì)屬性值組合的偏好關(guān)系Pi,以此得到用戶的在線服務(wù)選擇結(jié)果Li.進(jìn)行n次迭代,每次迭代結(jié)束返回用戶的在線服務(wù)選擇結(jié)果Li.

算法1.個(gè)體用戶在線服務(wù)選擇

輸入:用戶的條件偏好cpi

輸出:用戶的在線服務(wù)選擇結(jié)果Li

1.CPT=[],Ω=[],IE=[]

2. FORi=1 tonDO:

3. CPT.append(cpi)

4. FORj=1 topDO:

5. 計(jì)算所有翻轉(zhuǎn)關(guān)系

6. Ω.append(o1)

7.IE.append((o1,o2))/IE.append((o2,o1))//將翻轉(zhuǎn)關(guān)系添加到邊集中

8. END FOR

9.N′i.append(Ω)

10.N′i.append(IE)

11.Pi=對(duì)N′i進(jìn)行拓?fù)渑判?/p>

12.Li=根據(jù)Pi對(duì)S排序

13. RETURNLi

14. END FOR

算法1描述個(gè)體用戶服務(wù)選擇的全過(guò)程,首先根據(jù)用戶的條件偏好構(gòu)CP-nets,構(gòu)建條件偏好網(wǎng)絡(luò)的時(shí)間復(fù)雜度為O(n·p).其次,進(jìn)行偏好推理,通過(guò)翻轉(zhuǎn)關(guān)系并構(gòu)建偏好導(dǎo)出圖的時(shí)間復(fù)雜度為O(npq·qp+2).最后,對(duì)導(dǎo)出圖進(jìn)行拓?fù)渑判?其時(shí)間復(fù)雜度為O(nmqp).綜上,算法1的時(shí)間復(fù)雜度為O(npq·qp+2+nmqp),對(duì)其影響最大的是服務(wù)屬性數(shù)量以及服務(wù)屬性值的數(shù)量.

4.3 個(gè)體用戶選擇結(jié)果聚合

根據(jù)個(gè)體用戶對(duì)服務(wù)的偏好關(guān)系,需要使用聚合策略將所有個(gè)體用戶的偏好聚合,得到群體對(duì)服務(wù)的選擇結(jié)果.社會(huì)選擇函數(shù)Ranked Pairs[6]是社會(huì)選擇理論中的經(jīng)典方法,滿足社會(huì)選擇性質(zhì)較多,且出現(xiàn)平局概率低.因此,使用Ranked Pairs來(lái)聚合用戶的服務(wù)選擇結(jié)果.聚合過(guò)程分為4個(gè)步驟:

步驟1.根據(jù)Li進(jìn)行成對(duì)比較.建立用戶-服務(wù)偏好關(guān)系矩陣PRi=[prab]m×m(i=1,2,…,n;a,b= 1,2,…,m;a≠b),計(jì)算方法為:

(1)

式(1)中,若服務(wù)sa和sb在服務(wù)選擇列表Li中的偏好關(guān)系為sa?sb,則prab=1.同理,若sa～sb,prab=0;sasb,prab=-1.

步驟2.計(jì)算群體對(duì)服務(wù)的偏好關(guān)系.構(gòu)建群體服務(wù)-服務(wù)比較矩陣CM=[cmab]m×m(a,b=1,2,…,m;a≠b)表示群體的服務(wù)偏好關(guān)系,為計(jì)算方法為:

(2)

(3)

式(2)中統(tǒng)計(jì)所有個(gè)體用戶中服務(wù)對(duì)(sa,sb)兩兩比較時(shí)的優(yōu)先服務(wù),若認(rèn)為服務(wù)sa優(yōu)于服務(wù)sb的用戶數(shù)量多于認(rèn)為服務(wù)sb優(yōu)于服務(wù)sa的用戶數(shù)量,那么服務(wù)sa為優(yōu)先服務(wù),同理,若兩者數(shù)量相同,那么兩個(gè)服務(wù)沒(méi)有優(yōu)先級(jí),若前者數(shù)量少于后者,那么服務(wù)sb為優(yōu)先服務(wù).式(3)中,當(dāng)sa在群體中為優(yōu)先服務(wù)時(shí),統(tǒng)計(jì)服務(wù)sa的排名比服務(wù)sb的排名靠前的用戶數(shù)量作為cmab的值,統(tǒng)計(jì)服務(wù)sa排名比服務(wù)sb的排名靠后的用戶數(shù)量取負(fù)數(shù)作為cmba的值.當(dāng)sb為優(yōu)先服務(wù)時(shí),計(jì)算cmba的值和cmab的值.當(dāng)服務(wù)對(duì)(sa,sb)中沒(méi)有優(yōu)先服務(wù),則忽略.

步驟3.根據(jù)CM計(jì)算服務(wù)對(duì)的排序.將服務(wù)對(duì)排序列表記為ST,計(jì)算方法為:

(4)

式(4)中,c=1,2,…,m;a≠b≠c.在矩陣CM中比較cmab和cmac的大小,如果cmab>cmac,表示在服務(wù)對(duì)排序列表中服務(wù)對(duì)(sa,sb)排在(sa,sc)前面;如果cmab

(5)

當(dāng)|cmba|<|cmca|時(shí),服務(wù)對(duì)(sa,sb)排在(sa,sc)前面;當(dāng)|cmba|=|cmca|時(shí),服務(wù)對(duì)(sa,sb)和(sa,sc)不分先后順序;當(dāng)|cmba|>|cmca|時(shí),服務(wù)對(duì)(sa,sb)排在(sa,sc)后面.

步驟4.根據(jù)服務(wù)對(duì)排序列表ST構(gòu)建以服務(wù)為頂點(diǎn),以服務(wù)對(duì)為邊的有向圖.對(duì)有向圖進(jìn)行拓?fù)渑判?得到群體對(duì)服務(wù)的排序列表LG,將其作為群體的在線服務(wù)選擇結(jié)果.

5 實(shí)驗(yàn)與分析

根據(jù)本文提出的利用服務(wù)屬性條件偏好推理的群體選擇方法,設(shè)計(jì)了實(shí)驗(yàn)方案并進(jìn)行實(shí)驗(yàn)分析.所有實(shí)驗(yàn)都在Intel Core i7 CPU,64位Windows 10 操作系統(tǒng),PyCharm 2019.2.3,Python 3.6.5環(huán)境下進(jìn)行.

由于基于奇異值分解(SVD)的方法是推薦方法中的經(jīng)典方法[24],并且現(xiàn)有方法大多都用協(xié)同過(guò)濾的手段來(lái)解決服務(wù)未評(píng)價(jià)問(wèn)題,因此本文將SVD作為個(gè)體用戶選擇結(jié)果的對(duì)比方法.文獻(xiàn)[25]中提出了Average、Least Misery、Most Pleasure等幾種常見(jiàn)的聚合策略.由于以上方法是聚合策略的經(jīng)典方法,為了測(cè)試本方法的聚合效果,實(shí)驗(yàn)與上面幾種聚合策略進(jìn)行比較.本文從3個(gè)方面設(shè)計(jì)實(shí)驗(yàn):首先,本方法與對(duì)比方法的聚合效果進(jìn)行比較;其次,實(shí)驗(yàn)驗(yàn)證社會(huì)選擇理論相關(guān)性質(zhì);最后,對(duì)性能的影響因素分析.本文所有的準(zhǔn)確性及有效性數(shù)值結(jié)果實(shí)驗(yàn)都進(jìn)行10次重復(fù)實(shí)驗(yàn),并取平均值作為實(shí)驗(yàn)的最終結(jié)果.

5.1 數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集來(lái)源于Rafael等人提供的餐廳&消費(fèi)者數(shù)據(jù)集[26],該數(shù)據(jù)集是一個(gè)對(duì)餐廳評(píng)分的數(shù)據(jù)集,用戶對(duì)餐廳的服務(wù)、環(huán)境以及食物口味等進(jìn)行綜合打分,不同的評(píng)分分值表達(dá)了用戶對(duì)餐廳的不同喜好程度.餐廳部分的數(shù)據(jù)集包含每個(gè)餐廳所擁有的性質(zhì),比如價(jià)格,位置等.餐廳&消費(fèi)者數(shù)據(jù)集包含177個(gè)用戶對(duì)130個(gè)餐廳的1161條評(píng)分?jǐn)?shù)據(jù).在進(jìn)行實(shí)驗(yàn)之前,先對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理,刪除缺失價(jià)格,位置等信息的餐廳數(shù)據(jù),進(jìn)行實(shí)驗(yàn)的數(shù)據(jù)集包含133個(gè)用戶對(duì)113個(gè)餐廳的1059條評(píng)分?jǐn)?shù)據(jù).

根據(jù)餐廳&消費(fèi)者數(shù)據(jù)集的餐廳部分?jǐn)?shù)據(jù),提取出餐廳的7個(gè)重要屬性,例如價(jià)格,氛圍,位置以及是否可以抽煙等.其中,屬性值的數(shù)量為2到3.例如,價(jià)格分為“高”、“中”、“低”3個(gè)屬性值.113家餐廳分別以0,1,…,112進(jìn)行編號(hào).隨機(jī)選擇數(shù)據(jù)集的20%的數(shù)據(jù)作為測(cè)試集,剩下的80%作為訓(xùn)練集.

5.2 聚合效果

5.2.1 評(píng)價(jià)指標(biāo)

根據(jù)方法介紹,首先對(duì)用戶的偏好進(jìn)行學(xué)習(xí)和推理,得到用戶對(duì)服務(wù)的選擇結(jié)果;然后對(duì)個(gè)體用戶的服務(wù)選擇結(jié)果進(jìn)行聚合,得到群體選擇結(jié)果.實(shí)驗(yàn)分為2步:首先,從數(shù)據(jù)集中構(gòu)建每個(gè)用戶的CP-nets,并對(duì)其進(jìn)行推理,得到用戶對(duì)在線服務(wù)的選擇結(jié)果;然后,選擇數(shù)據(jù)集中的用戶組成群體,根據(jù)每個(gè)用戶的服務(wù)偏好對(duì)該群體進(jìn)行服務(wù)選擇.

本文使用準(zhǔn)確率來(lái)評(píng)估個(gè)體用戶的選擇結(jié)果算法的效果.準(zhǔn)確率表示服務(wù)選擇結(jié)果排序中正確的樣本數(shù)占總樣本數(shù)的比例,Precison值越大表示個(gè)體用戶選擇結(jié)果越準(zhǔn)確:

(6)

式(6)中,R(ui)表示測(cè)試集中用戶ui的總樣本偏好數(shù)量,T(ui)表示用戶ui通過(guò)CP-nets推理后得到的服務(wù)偏好.

本文使用nDCG(Normalized Discounted Cumulative Gain)[25]對(duì)用戶服務(wù)偏好聚合策略進(jìn)行評(píng)估,用戶u關(guān)于a(a=1,2,…,m)個(gè)在線服務(wù)選擇結(jié)果的DCG和nDCG定義為:

(7)

(8)

5.2.2 準(zhǔn)確率

為了實(shí)驗(yàn)的可行性和準(zhǔn)確性,需在數(shù)據(jù)集上構(gòu)建用戶的CP-nets.并對(duì)用戶的服務(wù)偏好進(jìn)行推理,得到用戶對(duì)服務(wù)的選擇結(jié)果.為了驗(yàn)證構(gòu)建CP-nets得到用戶對(duì)服務(wù)偏好的準(zhǔn)確率,從數(shù)據(jù)集中分別選擇80%和20%數(shù)據(jù)作為訓(xùn)練集和測(cè)試集,與SVD方法預(yù)測(cè)用戶服務(wù)偏好的準(zhǔn)確率進(jìn)行比較.改變用戶數(shù)量記錄準(zhǔn)確率,實(shí)驗(yàn)結(jié)果如圖3所示.

圖3 用戶對(duì)服務(wù)偏好的準(zhǔn)確率Fig.3 Accuracy of user preference for services

從圖3中可以看出構(gòu)建CP-nets得到的用戶對(duì)服務(wù)偏好的準(zhǔn)確率在0.57到0.7之間,隨著用戶數(shù)量的增加,準(zhǔn)確率趨于平穩(wěn).兩種方法都隨著用戶數(shù)量的增加呈上升趨勢(shì),隨著用戶數(shù)量的改變,構(gòu)建CP-nets得到的用戶對(duì)服務(wù)偏好的準(zhǔn)確率比SVD方法預(yù)測(cè)用戶對(duì)服務(wù)的偏好準(zhǔn)確率都要高.此外,本方法相比于SVD方法更穩(wěn)定.

5.2.3 聚合效果

在得到用戶對(duì)服務(wù)偏好的基礎(chǔ)上,比較了本方法與Average、Least Misery和Most Pleasure的聚合效果.實(shí)驗(yàn)得到群體中每個(gè)用戶關(guān)于群體選擇結(jié)果的nDCG,將所有用戶nDCG的平均值作為用戶所在群體的群體選擇結(jié)果有效性評(píng)估指標(biāo).通過(guò)改變用戶數(shù)量,記錄不同方法的nDCG值,觀察nDCG的變化趨勢(shì),實(shí)驗(yàn)結(jié)果如圖4所示.

圖4 聚合效果Fig.4 Aggregation effectiveness

圖4顯示了上述聚合策略在不同用戶數(shù)量組成的群體上的聚合效果.本方法的nDCG在0.875到0.9之間,其他方法的nDCG值在0.731到0.86之間.可以看出本方法的聚合策略要優(yōu)于其他聚合策略,并且本方法的聚合效果不會(huì)隨著群體中用戶數(shù)量的增加而產(chǎn)生劇烈變化,其效果較穩(wěn)定.

Average方法將每個(gè)用戶在服務(wù)評(píng)價(jià)過(guò)程中的作用視為相同,不能公平對(duì)待群體用戶.Least Misery聚合策略的特點(diǎn)是小部分不喜歡某些服務(wù)的用戶群決定了群體的選擇,Most Pleasure方法是小部分特別喜歡某些服務(wù)的用戶決定了群體的選擇,兩者都是由小部分用戶來(lái)決定群體的選擇,這使得用戶能夠輕易進(jìn)行惡意操縱行為.由于以上聚合策略的特性,使得以上聚合策略的聚合效果存在一定的劣勢(shì).本方法不僅能夠滿足大多數(shù)人的偏好,通過(guò)偏好推理提高了學(xué)習(xí)用戶偏好的準(zhǔn)確率,此外,本方法在一定程度上能避免個(gè)別用戶的惡意操縱行為.因此,本方法的聚合效果要比其他方法更好.

5.3 方法性質(zhì)

5.3.1 孔多賽性

孔多賽性反映了大多數(shù)用戶的最優(yōu)結(jié)果是群體的最優(yōu)結(jié)果.如果存在服務(wù)sa與其他任意服務(wù)sb成對(duì)比較時(shí),都有一半以上的用戶認(rèn)為服務(wù)sa優(yōu)于服務(wù)sb,那么sa為孔多賽候選服務(wù)[6].從個(gè)體用戶的服務(wù)選擇結(jié)果中統(tǒng)計(jì)可知有28名用戶認(rèn)為服務(wù)29優(yōu)于任意其他服務(wù),服務(wù)29為孔多賽候選服務(wù).為了驗(yàn)證本方法的孔多賽性,從28名用戶中選擇n名用戶,從剩下的85名用戶中選擇n′名用戶組成群體進(jìn)行6輪實(shí)驗(yàn),其中n>n′.記錄不同方法得到的群體選擇結(jié)果的最優(yōu)服務(wù),如圖5所示.

從圖5可以看出,本方法在不同用戶數(shù)量下的群體選擇結(jié)果中的最優(yōu)服務(wù)都是服務(wù)29,與候選服務(wù)一致,滿足孔多賽性;Least Misery方法在不同用戶數(shù)量下的群體選擇結(jié)果中最優(yōu)服務(wù)都是服務(wù)109,但與候選服務(wù)不一致,不滿足孔多賽性;Average方法和Most Pleasure方法在不同用戶數(shù)量下的群體選擇結(jié)果中最優(yōu)服務(wù)與候選服務(wù)不一致,因此,都不滿足孔多賽性.

圖5 孔多賽性驗(yàn)證Fig.5 Verification of condorcet

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

在線服務(wù)群體選擇應(yīng)滿足大多數(shù)人的偏好,因此使用社會(huì)選擇理論中的多數(shù)準(zhǔn)則驗(yàn)證方法的有效性.多數(shù)準(zhǔn)則是指如果認(rèn)為服務(wù)sa優(yōu)于服務(wù)sb的用戶數(shù)量大于認(rèn)為服務(wù)sb優(yōu)于服務(wù)sa的用戶數(shù)量,那么在群體選擇結(jié)果中,服務(wù)sa優(yōu)于服務(wù)sb.改變用戶數(shù)量,在不同用戶群體上測(cè)試在進(jìn)行服務(wù)的成對(duì)比較時(shí),記錄本方法與比較方法滿足多數(shù)準(zhǔn)則的服務(wù)比較對(duì)的比例,如圖6所示.

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

在圖6中可以看出,本方法在不同用戶數(shù)量下滿足多數(shù)準(zhǔn)則的比例在0.86～0.98之間,都高于比較方法.比較方法都是基于評(píng)分的聚合策略,由于用戶對(duì)服務(wù)表示同一喜愛(ài)程度的評(píng)分存在差異,因此會(huì)削弱或增高部分用戶對(duì)服務(wù)的偏好,導(dǎo)致群體不能最大可能滿足大多數(shù)人的偏好.本方法從用戶對(duì)屬性的偏好出發(fā),對(duì)用戶服務(wù)偏好進(jìn)行推理,避免了評(píng)分不一致的問(wèn)題.本方法多數(shù)準(zhǔn)則比例無(wú)法達(dá)到百分百的原因是Ranked Pairs有孔多賽悖論[27]的存在.但本方法在不同用戶數(shù)量下滿足多數(shù)準(zhǔn)則的比例都要比其他方法高.

5.3.3 抗操縱性

圖7中的曲線14、19、…、100表示服務(wù)序號(hào),如服務(wù)4隨著不誠(chéng)實(shí)用戶的變化時(shí),服務(wù)4的排名沒(méi)有發(fā)生改變.從圖7可以看出,當(dāng)不誠(chéng)實(shí)用戶數(shù)量增時(shí),排名靠前和靠后的服務(wù)的排名都未改變排名,說(shuō)明排名靠前和靠后的服務(wù)具有很強(qiáng)的抗操縱性.排名在中間的服務(wù)抗操縱性較弱.這是因?yàn)槭艿紺P-nets屬性依賴性的影響,改變部分屬性值的偏好,個(gè)體用戶的服務(wù)選擇結(jié)果排名在中間的服務(wù)更容易受到影響.綜上分析,本方法得到的群體選擇結(jié)果中,排名在中間的服務(wù)抗操縱性較弱,排名靠前和靠后的服務(wù)具有較強(qiáng)的抗操縱性.

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

5.4 性能測(cè)試

在餐廳&消費(fèi)者數(shù)據(jù)集中,用戶CP-nets的屬性和屬性值不變,依次選取20%,40%,60%,80%,100%的用戶組成群體進(jìn)行實(shí)驗(yàn).記錄本方法和其他3種比較方法在不同用戶數(shù)量組成的群體中得到群體選擇結(jié)果的運(yùn)行時(shí)間,實(shí)驗(yàn)結(jié)果如圖8所示.

圖8 運(yùn)行時(shí)間Fig.8 Runtime

從圖8可以看出,在5個(gè)群體中,群體選擇方法的運(yùn)行時(shí)間隨著群體中用戶數(shù)量的增加都會(huì)隨之增加.與其他方法相比,本方法由于考慮了服務(wù)屬性以及屬性值的數(shù)量和偏好,并根據(jù)用戶對(duì)屬性的偏好對(duì)服務(wù)偏好進(jìn)行了推理,因此本方法的運(yùn)行時(shí)間要更長(zhǎng),但對(duì)方法的實(shí)用性沒(méi)有本質(zhì)的影響.

6 總 結(jié)

本文針對(duì)用戶對(duì)在線服務(wù)屬性偏好建模困難,且現(xiàn)有方法無(wú)法對(duì)未評(píng)價(jià)服務(wù)進(jìn)行偏好推理的問(wèn)題提出了一種利用服務(wù)屬性條件偏好推理的在線服務(wù)群體選擇方法.方法根據(jù)CP-nets的語(yǔ)義對(duì)用戶的條件偏好進(jìn)行建模,并使用CP-nets的性質(zhì)對(duì)用戶服務(wù)偏好進(jìn)行推理,從而得到用戶對(duì)服務(wù)的偏好關(guān)系;最后,受到社會(huì)選擇理論啟發(fā),使用社會(huì)選擇函數(shù)Ranked Pairs將用戶的服務(wù)選擇結(jié)果聚合形成群體的在線服務(wù)選擇結(jié)果.

實(shí)驗(yàn)結(jié)果表明,本方法相比于對(duì)比方法總體呈優(yōu),能夠根據(jù)推理得到的個(gè)體用戶偏好做出較優(yōu)的在線服務(wù)群體選擇.此外,實(shí)驗(yàn)驗(yàn)證該方法滿足孔多賽性、多數(shù)準(zhǔn)則、單調(diào)性和抗操縱性等性質(zhì).未來(lái)工作中,將探索降低推理用戶偏好過(guò)程的時(shí)間問(wèn)題,在此基礎(chǔ)上結(jié)合其他聚合策略迅速獲取群體的選擇結(jié)果.同時(shí),還需在此基礎(chǔ)上探索該方法中用戶服務(wù)屬性偏好的變化與社會(huì)選擇性質(zhì)中變化趨勢(shì)的關(guān)聯(lián)性.