和鳳珍，石進(jìn)平

1.云南大學(xué)旅游文化學(xué)院 信息學(xué)院，云南 麗江 674100

2.云南省農(nóng)村信用社 科技結(jié)算中心，昆明 650228

1 引言

作為一種從大量冗余信息中挖掘用戶(hù)感興趣的內(nèi)容并推送給用戶(hù)的有效手段，推薦系統(tǒng)（recommender system）已經(jīng)成功應(yīng)用到移動(dòng)APP應(yīng)用[1]、學(xué)術(shù)文獻(xiàn)[2]、電子商務(wù)[3]、音樂(lè)[4]、電影[5-7]、Web社區(qū)發(fā)現(xiàn)[8]、信息檢索[9-10]等廣泛領(lǐng)域中。已有的推薦算法側(cè)重提高推薦結(jié)果的相關(guān)性和準(zhǔn)確度，如文獻(xiàn)[4,6-7]，但是缺乏多樣性（diversity）。文獻(xiàn)[11]研究表明：具有多樣性的推薦結(jié)果有助于提高用戶(hù)的整體滿(mǎn)意度。由此可見(jiàn)，相關(guān)性不是衡量推薦質(zhì)量的唯一標(biāo)準(zhǔn)，多樣性對(duì)于提升推薦服務(wù)質(zhì)量也具有重要作用。在實(shí)際推薦系統(tǒng)應(yīng)用環(huán)境中，由于用戶(hù)的偏好很難被準(zhǔn)確描述和獲取，往往具有不確定性、模糊性以及多義性。因此，如何基于已有的用戶(hù)偏好信息，向用戶(hù)推薦與其興趣相關(guān)同時(shí)又具有非冗余、多樣化的推薦結(jié)果，這成為當(dāng)前推薦系統(tǒng)研究面臨的主要挑戰(zhàn)[12]。

針對(duì)多樣性推薦問(wèn)題，已有一些相關(guān)研究成果[4,10,13]。利用這些方法獲得的推薦結(jié)果不能在多樣性與相關(guān)性之間取得較好的折中。這是因?yàn)樗鼈兪艿骄鶆驍M陣約束（uniform matroid constraints），即假設(shè)推薦項(xiàng)目集中的各個(gè)推薦項(xiàng)對(duì)于所有用戶(hù)具有相同的重要性，如文獻(xiàn)[4,10]。文獻(xiàn)[13]考慮到每個(gè)推薦項(xiàng)具有不同的重要性，但尚未考慮用戶(hù)的偏好，會(huì)導(dǎo)致推薦結(jié)果中相同類(lèi)別中的推薦項(xiàng)具有較高的冗余度。受此啟發(fā)，本文提出了一種非均勻劃分?jǐn)M陣約束下的基于用戶(hù)偏好的多樣性推薦模型（preferencebased diversified recommendation model，PDM）。該模型在推薦過(guò)程中同時(shí)考慮了多樣性和相關(guān)性?xún)蓚€(gè)因素，在保證推薦結(jié)果相關(guān)性的前提下，通過(guò)在每個(gè)類(lèi)別上施加非均勻劃分?jǐn)M陣約束，有效提升推薦結(jié)果的多樣性，力爭(zhēng)在相關(guān)性和多樣性之間取得有效折中。

圖1展示了PDM的基本思想及與其他主流方法的不同。不同的字母代表不同類(lèi)別，假設(shè)它們都與查詢(xún)內(nèi)容相關(guān)，但彼此之間具有差異性。假設(shè)大寫(xiě)字母和小寫(xiě)字母屬于同一類(lèi)別，但與查詢(xún)內(nèi)容的相關(guān)度不一樣：大寫(xiě)字母的相關(guān)度大于小寫(xiě)字母。假設(shè)虛線(xiàn)框內(nèi)的字母與查詢(xún)內(nèi)容的相關(guān)度大于其他類(lèi)別。

在均勻擬陣約束（即基約束）下的推薦結(jié)果記作R，均勻擬陣假設(shè)各個(gè)推薦項(xiàng)對(duì)于所有用戶(hù)具有相同的重要性，因此與用戶(hù)興趣相關(guān)度較高的推薦項(xiàng)被重復(fù)選擇作為推薦結(jié)果，從而導(dǎo)致均勻擬陣約束下的推薦結(jié)果R僅來(lái)自少數(shù)幾個(gè)與用戶(hù)興趣相關(guān)度較高的類(lèi)別中，即C、B、O，而不能覆蓋整個(gè)物品類(lèi)別。非均勻擬陣約束下的Max-sum[13]方法，其認(rèn)為每個(gè)推薦項(xiàng)的重要程度不同。然后，從與用戶(hù)興趣相關(guān)的每個(gè)類(lèi)別中取相同數(shù)目的推薦項(xiàng)構(gòu)成top-k推薦列表，使得Max-sum模型的效用函數(shù)最大化，如圖1中R′所示，從每個(gè)相關(guān)的類(lèi)別中取2個(gè)推薦項(xiàng)構(gòu)成top-10推薦列表，因此，R′中的類(lèi)別覆蓋范圍比R更廣泛，多樣性較好。在非均勻劃分?jǐn)M陣約束（即不僅考慮了每個(gè)推薦項(xiàng)具有不同的重要性，而且還考慮到不同用戶(hù)對(duì)每個(gè)類(lèi)別的偏好程度不同以及用戶(hù)對(duì)相同類(lèi)別中推薦項(xiàng)之間差異化的偏好程度也不同）下，選擇使得PDM模型的效用函數(shù)最大化的推薦列表記作R*，如圖1中R*所示，R*與R′都覆蓋了所有的類(lèi)別，根據(jù)前面的分析，在R中用戶(hù)對(duì)類(lèi)別C、B、O感興趣的程度大于類(lèi)別D、P，在覆蓋廣泛類(lèi)別的同時(shí)也應(yīng)當(dāng)體現(xiàn)出用戶(hù)的偏好，但是R′中每個(gè)類(lèi)別中推薦項(xiàng)的數(shù)目均相同，而R*中不僅來(lái)自類(lèi)別C、B、O、D、P的數(shù)目不完全相同，分別為3、2、2、2、1，而且R*中有來(lái)自同一類(lèi)別C的“C,c,C”三個(gè)彼此差異化較大的推薦項(xiàng)，而R′中來(lái)自類(lèi)別C的兩個(gè)推薦項(xiàng)“C,C”彼此相同，沒(méi)有差異化。R*比R′的差異化更大，多樣性更豐富。這是由于在PDM模型中同時(shí)考慮了用戶(hù)不同的偏好：用戶(hù)不僅偏好能夠覆蓋廣泛類(lèi)別的推薦結(jié)果，而且也偏好相同類(lèi)別中差異性較大的推薦結(jié)果。如圖1左邊的方框所示：均勻擬陣約束下所有推薦項(xiàng)屬于同一類(lèi)別且重要程度相同；非均勻擬陣約束下僅考慮到推薦項(xiàng)的重要程度，而未考慮類(lèi)別之間的重要程度；而非均勻劃分?jǐn)M陣約束將推薦項(xiàng)劃分為不同的類(lèi)別（如圖1中虛線(xiàn)框所示，未標(biāo)出所有的虛線(xiàn)框），每個(gè)類(lèi)別中推薦項(xiàng)的重要程度不同，而且不同類(lèi)別的重要程度也不同。

Fig.1 Basic idea of PDM and its differences from other mainstream methods圖1 PDM的基本思想及與其他主流方法的不同

本文工作的主要貢獻(xiàn)如下：

（1）為有效折中推薦結(jié)果的相關(guān)性和多樣性，提出了一種非均勻劃分?jǐn)M陣約束條件下基于用戶(hù)偏好的多樣性推薦模型。該模型以一個(gè)具有子模性的目標(biāo)函數(shù)來(lái)度量top-k推薦結(jié)果的推薦質(zhì)量，在推薦過(guò)程同時(shí)融合了用戶(hù)偏好的多樣性和相關(guān)性。

（2）證明了使多樣性效用函數(shù)最大化問(wèn)題是一個(gè)NP-hard，并進(jìn)一步提出一個(gè)高效率的近似優(yōu)化算法——PDM多樣性算法，進(jìn)一步提出高效的貪心算法求解子模函數(shù)，能夠獲得(1-1/e)的近似保證。

（3）提出一種新穎的多樣性度量方法DisCover-Div，此多樣性度量方法融合了推薦列表的不相似度和類(lèi)別覆蓋程度，更加全面、多方位地度量推薦結(jié)果的多樣性。

（4）在真實(shí)的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，與多種算法在多樣性和準(zhǔn)確率（相關(guān)性）兩方面進(jìn)行分析比較，實(shí)驗(yàn)證明所提方法不僅能夠在多樣性和準(zhǔn)確率之間取得較好的折中，而且具有高效性。

2 相關(guān)工作

目前，針對(duì)推薦系統(tǒng)中的多樣性研究存在的問(wèn)題，需要進(jìn)行以下三方面研究[12]：（1）在多樣性度量方式上，主要關(guān)注如何評(píng)價(jià)整體用戶(hù)對(duì)多樣性結(jié)果的滿(mǎn)意度；（2）在相關(guān)性方面，主要研究如何在多樣性和相關(guān)性之間找到一個(gè)良好的平衡點(diǎn)，而不是以犧牲準(zhǔn)確度為代價(jià)換取多樣性的提升；（3）在算法方面，主要研究推薦過(guò)程中高效率、新穎的多樣性推薦算法。

近年來(lái)，許多研究者針對(duì)推薦系統(tǒng)中推薦結(jié)果多樣性的度量方法、多樣性最大化以及多樣性推薦算法等問(wèn)題積極開(kāi)展研究，并取得了一系列成果，極大地促進(jìn)了推薦系統(tǒng)多樣化問(wèn)題的研究[1-5,14-17]。然而，多樣性與相關(guān)性之間是一種對(duì)立關(guān)系：隨著多樣性的提高，相關(guān)性將降低[14]。在不以犧牲相關(guān)性為代價(jià)的前提下，使得多樣性最大化[13,18-21]等問(wèn)題引起學(xué)者的關(guān)注，取得了一些初步的研究成果。

例如：文獻(xiàn)[2]將多樣性應(yīng)用到學(xué)術(shù)領(lǐng)域，利用MutualRank對(duì)學(xué)術(shù)網(wǎng)絡(luò)中的論文及作者的權(quán)威度進(jìn)行建模，提出了一種面向權(quán)威度（相關(guān)性）和多樣性的兩階段排序模型PDRank，給出一個(gè)融合相關(guān)性和多樣性?xún)蓚€(gè)因素的線(xiàn)性目標(biāo)函數(shù)。文獻(xiàn)[3]展現(xiàn)了推薦列表多樣性的重要性，提出了DivRec多樣性推薦框架，通過(guò)設(shè)置相關(guān)性閾值調(diào)節(jié)推薦列表的多樣性，該方法過(guò)濾了與用戶(hù)相關(guān)度不高的物品，只考慮了用戶(hù)感興趣物品范圍內(nèi)的多樣性。Lee等[4]介紹了基于圖（graph）的個(gè)性化多樣性推薦方法，提出了一種基于熵模型的GraphRec算法。Adomavicius等[15]基于商品流行程度提出一種整體多樣性重排序方法，但是過(guò)于流行的商品會(huì)在許多用戶(hù)的推薦結(jié)果中出現(xiàn)，從而降低了推薦結(jié)果的整體多樣性。Bradley等[21]首先將多樣性作為衡量指標(biāo)引入到推薦系統(tǒng)中，并提出了整合多樣性和準(zhǔn)確度的線(xiàn)性模型，給出了一種求解該模型的貪心選擇算法BGS（bounded greedy selection）。Hurley等[11]基于文獻(xiàn)[21]進(jìn)一步擴(kuò)展，將多樣性問(wèn)題建模為一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題，同樣采用目標(biāo)函數(shù)優(yōu)化的方式獲得與文獻(xiàn)[21]相似的多樣性，但時(shí)間復(fù)雜度更高。然而，這些多樣性模型僅考慮使推薦列表中物品之間的相異性最大化，并沒(méi)有考慮使推薦結(jié)果覆蓋廣泛的類(lèi)別，因此推薦結(jié)果僅來(lái)自與用戶(hù)興趣愛(ài)好相關(guān)度較高的少數(shù)幾個(gè)類(lèi)別。

雖然一些文獻(xiàn)考慮了類(lèi)別多樣性，例如，文獻(xiàn)[1]提出了將用戶(hù)的主題模型和移動(dòng)應(yīng)用APP的主題模型與協(xié)同過(guò)濾相結(jié)合的LDA_MF模型，并提出了結(jié)合主題模型LDA（latent Dirichlet allocation）和矩陣分解MF（matrix factorization）的LDA_MF算法，最后為了整合其他算法的優(yōu)點(diǎn)，提出了通過(guò)邏輯回歸將LDA_MF算法與其他協(xié)同過(guò)濾算法相融合的混合算法Hybrid_Rec，提高推薦結(jié)果的多樣性。Aytekin等[5]提出一種基于聚類(lèi)的多樣性推薦模型ClusDiv。文獻(xiàn)[8]基于網(wǎng)絡(luò)設(shè)計(jì)中用戶(hù)之間的關(guān)系網(wǎng)絡(luò)和社區(qū)主題，提出一種新穎性社區(qū)推薦方法NovelRec，這種新穎性推薦本質(zhì)上也是一種多樣性，旨在向用戶(hù)推薦其潛在感興趣但又尚未觸及的新社區(qū)。該方法雖然能夠獲得相對(duì)較好的新穎性推薦結(jié)果，但同時(shí)也犧牲了推薦結(jié)果的準(zhǔn)確度。Ziegler等[14]首先提出話(huà)題多樣性（topic diversification），并給出了在ILS模型下，使得推薦結(jié)果能夠覆蓋更多話(huà)題類(lèi)別的重排序方法。但是，文獻(xiàn)[1,5,8,14]依舊假設(shè)項(xiàng)目集合中所有項(xiàng)目的重要程度都是相同的，即受到均勻擬陣約束，因此，這些方法不能夠在多樣性和相關(guān)性之間取得較好的折中。

實(shí)際上，每個(gè)推薦項(xiàng)的重要程度是不相同的，不同用戶(hù)對(duì)推薦項(xiàng)類(lèi)別的偏好程度以及相同類(lèi)別下推薦項(xiàng)之間的偏好程度也不一樣，而且這些情況往往是同時(shí)存在的，針對(duì)這種情況下的多樣性研究較少。Wu等[13]考慮了每張圖像具有不同的重要性，通過(guò)引入困難系數(shù)自動(dòng)調(diào)節(jié)每張圖像的不同權(quán)重，提出了Max-sum模型，證明了Max-sum目標(biāo)函數(shù)滿(mǎn)足子模性，并在非均勻擬陣約束下提出一種高效率的近似優(yōu)化算法，避免更多的圖像來(lái)自相同類(lèi)別。雖然Max-sum模型能夠覆蓋廣泛的類(lèi)別，但是Maxsum模型在每個(gè)類(lèi)別劃分上均取相同數(shù)目的圖像構(gòu)成top-k推薦列表，即Max-sum模型沒(méi)有考慮不同用戶(hù)對(duì)圖像類(lèi)別的偏好程度；其次，Max-sum模型沒(méi)有考慮相同類(lèi)別內(nèi)圖像之間的差異化，即Max-sum模型會(huì)導(dǎo)致推薦結(jié)果中相同類(lèi)別下圖像的冗余度較高。因此，Max-sum模型降低了推薦結(jié)果的多樣性。

3 基于非均勻劃分?jǐn)M陣約束的多樣性模型

3.1 問(wèn)題定義

擬陣M是一個(gè)二元組(I,R)，其中I是一個(gè)有限集，R是I的子集簇，R被稱(chēng)為獨(dú)立集，它滿(mǎn)足下列性質(zhì)：

（1）? 是獨(dú)立集。

（2）遺傳性：任意的A′?A?I，如果A∈R，那么A′∈R。

（3）交換性：如果A∈R，B∈R且|A|＞|B|，那么?e∈AB使得{e}?B∈R。

針對(duì)劃分?jǐn)M陣（partition matroid），有限集I被劃分成m類(lèi)，類(lèi)別集合L={L1,L2,…,Lm}，獨(dú)立集R滿(mǎn)足為第i個(gè)類(lèi)別劃分上的閾值（threshold），該閾值表示推薦結(jié)果中至多有Ti個(gè)物品來(lái)自類(lèi)別Li。均勻擬陣是劃分?jǐn)M陣的一種特例，即當(dāng)m=1時(shí)，劃分?jǐn)M陣則變?yōu)榫鶆驍M陣（uniform matroid）。

把top-k多樣性推薦問(wèn)題轉(zhuǎn)化為一個(gè)劃分?jǐn)M陣上的優(yōu)化問(wèn)題，利用聚類(lèi)算法將推薦項(xiàng)聚類(lèi)到多個(gè)類(lèi)別（劃分）中，用戶(hù)通過(guò)界面輸入一個(gè)閾值，該閾值表示結(jié)果集中同一類(lèi)別內(nèi)用戶(hù)最多允許出現(xiàn)的數(shù)目，對(duì)初始的相關(guān)性結(jié)果大于閾值的類(lèi)別進(jìn)行調(diào)整，分配到其他類(lèi)別上從而使得最終結(jié)果能夠盡可能覆蓋整個(gè)類(lèi)別，并且使得相關(guān)性大的類(lèi)別出現(xiàn)的數(shù)目多，相關(guān)性小的類(lèi)別出現(xiàn)的數(shù)目少。這里考慮到用戶(hù)興趣愛(ài)好的變化性，假設(shè)所有類(lèi)別都是用戶(hù)感興趣的。

具體地，令推薦項(xiàng)目集為I，I={i1,i2,…,im}，其中I被劃分成m類(lèi)。L={L1,L2,…,Lm}為類(lèi)別集合，例如L2={i2,i5,i8,i10}。用戶(hù)集合為U，U={u1,u2,…,un}。對(duì)于任意用戶(hù)u，u∈U，top-k個(gè)性化多樣性推薦的任務(wù)是從各個(gè)類(lèi)別中選擇滿(mǎn)足約束條件的k個(gè)元素集合Ru,Ru?I，使得目標(biāo)函數(shù)的效益utility(Ru)最大化。

3.2 整體框架流程

如圖2所示，PDM框架分為在線(xiàn)和離線(xiàn)兩個(gè)階段。其中評(píng)分預(yù)測(cè)和聚類(lèi)過(guò)程運(yùn)算量較大且能夠動(dòng)態(tài)計(jì)算更新，因此可以在離線(xiàn)階段進(jìn)行線(xiàn)下計(jì)算，而在線(xiàn)階段直接使用離線(xiàn)結(jié)果進(jìn)行計(jì)算，從而縮短響應(yīng)時(shí)間，可有效提高用戶(hù)體驗(yàn)。評(píng)分預(yù)測(cè)過(guò)程中，采用基于模型分解的ALS[6]（alternating least squares）協(xié)同過(guò)濾算法完成預(yù)測(cè)。并根據(jù)用戶(hù)評(píng)分?jǐn)?shù)據(jù)利用k-means聚類(lèi)算法將推薦項(xiàng)聚類(lèi)。在線(xiàn)階段中，首先根據(jù)評(píng)分預(yù)測(cè)結(jié)果進(jìn)行相關(guān)性推薦，并利用用戶(hù)輸入的閾值對(duì)初始推薦結(jié)果進(jìn)行類(lèi)別權(quán)重，調(diào)整后的結(jié)果作為非均勻劃分?jǐn)M陣約束施加到PDM推薦模型上，推薦模型將在推薦過(guò)程中對(duì)用戶(hù)偏好、相關(guān)性和多樣性進(jìn)行計(jì)算，最后將生成的top-k多樣性結(jié)果集合返回給推薦用戶(hù)。

Fig.2 Flowchart of PDM framework圖2 PDM框架流程圖

3.3 非均勻劃分?jǐn)M陣約束下的多樣性模型

假設(shè)1用戶(hù)對(duì)推薦項(xiàng)目的評(píng)分越高，該推薦項(xiàng)與用戶(hù)的興趣愛(ài)好越相關(guān)。

基于這個(gè)假設(shè)，為方便表達(dá)，首先描述相關(guān)定義：

定義1（相關(guān)性）用戶(hù)u(u∈U)對(duì)推薦項(xiàng)i(i∈I)的評(píng)分記為Scoreu(i)，推薦項(xiàng)i與用戶(hù)u的相關(guān)性形式化描述如下：

定義2（集合相似度）集合S的相似度為集合S中兩兩推薦項(xiàng)目之間的平均相似度,形式化定義如下：

其中，S∈I，n=|S|，sim(i,j)為推薦項(xiàng)i,j∈I之間的相似度，相似度可以采用余弦相似度等度量方法。

定義3（類(lèi)別內(nèi)部偏好程度）用戶(hù)u∈U按照PDM模型進(jìn)行推薦，推薦結(jié)果集記作Ru，推薦項(xiàng)i∈I的類(lèi)別記為L(zhǎng)i；Ru中與推薦項(xiàng)i類(lèi)別相同的推薦項(xiàng)構(gòu)成的集合記為，用戶(hù)u對(duì)類(lèi)別Li的內(nèi)部偏好（inner preference，IP）記為)，形式化定義如下：

定義4（整體類(lèi)別偏好程度）用戶(hù)u∈U按照PDM模型進(jìn)行推薦，推薦結(jié)果集記作Ru，用戶(hù)u對(duì)類(lèi)別Ru的整體類(lèi)別偏好（aggregate preference，AP）記為AP(Ru)，形式化定義如下：

其中，懲罰因子wi控制著與推薦項(xiàng)i屬于同一類(lèi)別的推薦項(xiàng)加入到R中的困難程度，wi越大，對(duì)推薦項(xiàng)i的懲罰力度越大，推薦項(xiàng)i加入到推薦列表的困難程度也越大。wi被定義為[13]：

在等式（5）中，Zi表示R中已經(jīng)包含與推薦項(xiàng)i來(lái)自于同一個(gè)類(lèi)別的推薦項(xiàng)數(shù)量。

由于用戶(hù)同時(shí)具有不同的偏好，用融合上述兩種偏好的乘積作為用戶(hù)u∈U推薦列表Ru∈I的多樣化效用，記為：

因此，非均勻劃分?jǐn)M陣約束下基于PDM的多樣性最大化問(wèn)題可以定義為：

定義5（多樣性最大化）按照PDM進(jìn)行多樣性推薦，給定任意用戶(hù)u∈U，求解用戶(hù)u多樣性效用最大化的結(jié)果集Ru?I，使得：

在等式（7）中，實(shí)施劃分?jǐn)M陣約束的目的是使推薦列表Ru能夠盡可能地覆蓋到所有與用戶(hù)興趣愛(ài)好相關(guān)的類(lèi)別中。本文僅使用了數(shù)據(jù)中的顯示評(píng)分信息，沒(méi)有使用隱示信息，如時(shí)間、標(biāo)題等；根據(jù)模型，式（7）中僅對(duì)不同類(lèi)別出現(xiàn)在結(jié)果集中的數(shù)目以及k值進(jìn)行約束，依據(jù)模型和數(shù)據(jù)集的不同可以對(duì)推薦項(xiàng)的多個(gè)屬性進(jìn)行約束。Ru來(lái)自于劃分中，滿(mǎn)足，kt為類(lèi)別權(quán)重調(diào)整后各個(gè)類(lèi)別的上限值，值得注意kt的值不完全相同，即k1:k2:…:km≠ 1。

定理1PDM模型的多樣性最大化問(wèn)題是一個(gè)關(guān)于k的NP-hard問(wèn)題。

證明在PDM模型中，當(dāng)用戶(hù)u∈U對(duì)類(lèi)別內(nèi)部的偏好程度均相同時(shí)，即，i∈I，PDM 模型則退化為Max-sum模型，因此，Max-sum模型是PDM模型的一種特例。文獻(xiàn)[13]證明了Max-sum模型下的多樣性最大化問(wèn)題是一個(gè)關(guān)于k的NP-hard問(wèn)題，因此等式（7）描述的PDM模型下的多樣性最大化也是一個(gè)關(guān)于k的NP-hard問(wèn)題。 □

定理2在PDM模型下，任意推薦用戶(hù)u∈U的推薦結(jié)果列表Ru∈I的多樣性效用函數(shù)utility(Ru)是一個(gè)非負(fù)、單調(diào)、子模函數(shù)。

證明任意推薦用戶(hù)u∈U在PDM模型的推薦過(guò)程中，若每次均在整個(gè)推薦項(xiàng)集合中進(jìn)行篩選，那么，推薦過(guò)程將按照Max-sum模型進(jìn)行，最終得到utility(Ru)。由于Wu等[13]已經(jīng)證明了Max-sum模型的效用函數(shù)具有子模性，因此，在PDM模型下，任意推薦用戶(hù)u的推薦結(jié)果列表Ru?I的多樣性效用函數(shù)utility(Ru)也具有子模性。 □

定理3若函數(shù)f是一個(gè)單調(diào)、非遞減的子模函數(shù)，貪心（greedy）算法獲得k個(gè)元素的集合SG滿(mǎn)足[22]：

由定義1及定理2結(jié)論可知，求解Ru可歸結(jié)為一個(gè)子模函數(shù)優(yōu)化問(wèn)題。于是，給定任意推薦用戶(hù)u∈U，在非均勻擬陣約束條件下，以u(píng)tility(Ru)作為子模目標(biāo)函數(shù)，由定理3和子模函數(shù)優(yōu)化理論[22]可知，使用貪心選擇法可得到(1-1/e)的近似保證。

4 非均勻劃分?jǐn)M陣約束下的多樣性推薦算法

4.1 初始類(lèi)別權(quán)重調(diào)整算法

設(shè)不同用戶(hù)對(duì)各個(gè)推薦項(xiàng)類(lèi)別具有不同的初始權(quán)重，這些初始權(quán)重是根據(jù)初始推薦結(jié)果計(jì)算得到的。具體方法為：取前k個(gè)評(píng)分最高的推薦項(xiàng)作為用戶(hù)u∈U的初始推薦結(jié)果Ru，統(tǒng)計(jì)每個(gè)用戶(hù)的推薦列表Ru中各個(gè)類(lèi)別上的推薦項(xiàng)數(shù)量，并將其作為初始權(quán)重。例如，R1中有7個(gè)推薦項(xiàng)來(lái)自類(lèi)別L2時(shí)，則L2W1=7。

如果按照初始類(lèi)別權(quán)重進(jìn)行分配，由于存在部分類(lèi)別的權(quán)重很大，而其他類(lèi)別的很小的現(xiàn)象，而且，權(quán)重很大的類(lèi)別可能是用戶(hù)很感興趣的類(lèi)別，而權(quán)重較低的類(lèi)別可能是用戶(hù)尚未了解、未觸及的推薦項(xiàng)，從而導(dǎo)致top-k推薦列表僅來(lái)自有數(shù)幾個(gè)與用戶(hù)興趣愛(ài)好高度相關(guān)的類(lèi)別而不能完整反映整個(gè)推薦項(xiàng)的輪廓結(jié)構(gòu)，產(chǎn)品曝光率低。為了更好地提高推薦結(jié)果的多樣性，在所有類(lèi)別上施加了非均勻劃分?jǐn)M陣約束，對(duì)初始類(lèi)別權(quán)重大于給定閾值的推薦項(xiàng)所屬的類(lèi)別按照算法1進(jìn)行類(lèi)別權(quán)重調(diào)整。

算法1初始類(lèi)別權(quán)重調(diào)整算法

算法1主要涉及3個(gè)參數(shù)：（1）初始推薦結(jié)果InitResult；（2）聚類(lèi)結(jié)果L；（3）閾值threshold。算法首先統(tǒng)計(jì)用戶(hù)初始推薦結(jié)果中各個(gè)類(lèi)別的權(quán)重，即各個(gè)類(lèi)別在初始推薦結(jié)果中出現(xiàn)的數(shù)量（第1行），對(duì)類(lèi)別權(quán)重大于給定閾值的類(lèi)別Lm進(jìn)行如下調(diào)整（第2～9行）：隨機(jī)選擇權(quán)重類(lèi)別最小的類(lèi)別（第4行），將其權(quán)重類(lèi)別加1（第5行），同時(shí)將類(lèi)別Lm的權(quán)重減1。如此反復(fù)調(diào)整，直到初始推薦結(jié)果的類(lèi)別權(quán)重均小于或等于給定閾值為止，值得注意的是：如果給定的閾值較大，初始推薦結(jié)果的類(lèi)別權(quán)重均小于該閾值，則最終推薦結(jié)果與初始推薦結(jié)果完全相同；相反,如果給定的閾值較小,則每個(gè)類(lèi)別上都要進(jìn)行相應(yīng)的調(diào)整。

4.2 PDM貪心算法

首先通過(guò)一個(gè)例子解釋PDM算法的邏輯計(jì)算。無(wú)向帶權(quán)圖G一共有8個(gè)頂點(diǎn),分別是每個(gè)頂點(diǎn)都有各自的屬性，如，表示頂點(diǎn)v2，來(lái)自于類(lèi)別1。無(wú)向圖G的鄰接矩陣（上三角矩陣）如表1所示，權(quán)重表示頂點(diǎn)之間的相似度，而相關(guān)度可以利用等式（1）計(jì)算得到，無(wú)向圖G中頂點(diǎn)之間的相關(guān)度如表2所示。

Table 1 Adjacency matrix of graph G表1 圖G的鄰接矩陣

利用貪心算法求解滿(mǎn)足PDM多樣性的前6個(gè)檢索結(jié)果，輸入查詢(xún)?yōu)轫旤c(diǎn)，設(shè)用戶(hù)輸入的閾值為2，對(duì)初始的相關(guān)性檢索結(jié)果進(jìn)行類(lèi)別權(quán)重調(diào)整后的權(quán)重如表3所示：允許類(lèi)別1中的頂點(diǎn)在結(jié)果集合中出現(xiàn)2次；允許類(lèi)別3中的頂點(diǎn)在結(jié)果集合中出現(xiàn)1次。

Table 2 Relevance of vertex in graph G表2 圖G中頂點(diǎn)之間的相關(guān)度

Table 3 Adjusted category weights表3 調(diào)整后的類(lèi)別權(quán)重

在類(lèi)別2內(nèi)的頂點(diǎn)分別與R中的頂點(diǎn)計(jì)算PDM效益。對(duì)于頂點(diǎn)：PDM值為(1-((exp(-(2-0)/2)))×((0.8+0.9+0.7)/3/(3-1)))×1×0.13=0.110 9。對(duì)于頂點(diǎn)：PDM值為(1-((exp(-(2-0)/2)))×((0.8+0.8+0.9)/3/(3-1)))×1×0.11=0.093 1。由于，故先將加入R中，

采用同樣的方式計(jì)算后的最終推薦結(jié)果為R=

通過(guò)上面具體的邏輯計(jì)算，可以得出算法2的關(guān)鍵步驟。算法2涉及到用戶(hù)u∈U對(duì)所有推薦項(xiàng)的評(píng)分和類(lèi)別權(quán)重LmWu兩個(gè)參數(shù)。算法首先進(jìn)行初始化工作（第1～3行），接著算法先更新wi、Zi（第4行），對(duì)調(diào)整后的每個(gè)類(lèi)別（第6行），在類(lèi)別簇內(nèi)計(jì)算PDM值，將使PDM最大的推薦項(xiàng)加入R中，同時(shí)更新變量（第7～15行）。

PDM貪心算法包括在線(xiàn)階段初始類(lèi)別權(quán)重調(diào)整和生成檢索結(jié)果兩個(gè)步驟。算法1中主要涉及類(lèi)別權(quán)重調(diào)整，最壞情況下top-k來(lái)自于同一類(lèi)別，因此，算法1的時(shí)間復(fù)雜度為O(k)；將推薦項(xiàng)集合I={i1，i2，…，in}的大小記作n，算法2的關(guān)鍵迭代步驟為第5～7行，最壞情況下L的長(zhǎng)度為k，|Ri|的長(zhǎng)度為1，因此時(shí)間復(fù)雜度為O(kn)，由于算法2是在類(lèi)別簇內(nèi)局部貪心，而不是每次都在所有推薦項(xiàng)中進(jìn)行全局貪心，因此空間復(fù)雜度為O(n)。從算法角度看，施加非均勻劃分?jǐn)M陣約束后，算法的時(shí)間復(fù)雜度從O(k2n)降為O(kn)，空間復(fù)雜度也從O(kn)下降為O(n)。

算法2PDM貪心算法

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

實(shí)驗(yàn)執(zhí)行環(huán)境為Intel Core i7處理器，8Cores，每個(gè)Core的主頻為3.4 GHz，Windows 10 64 bit操作系統(tǒng)，12 GB內(nèi)存。實(shí)驗(yàn)程序基于Pandas模塊，采用Python2.7版程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)。

5.1 基線(xiàn)算法

為了比較最終的多樣性推薦效果，實(shí)現(xiàn)了下面四種算法：

（1）PDM：本文第4章中提出一種非均勻劃分?jǐn)M陣約束下基于偏好的多樣性近似優(yōu)化算法。

（2）Max-sum：文獻(xiàn)[13]提出一種多樣性圖像檢索近似優(yōu)化算法。

（3）PDRank：文獻(xiàn)[2]基于異質(zhì)學(xué)術(shù)網(wǎng)絡(luò)提出一種融合作者、論文權(quán)威度和多樣性的推薦方法。

（4）GraphRec：文獻(xiàn)[4]基于社交網(wǎng)絡(luò)提出一種面向“兩階段”重排序的多樣性圖排序算法。

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

從用戶(hù)數(shù)目、推薦項(xiàng)數(shù)目、評(píng)分?jǐn)?shù)目、評(píng)分范圍和稀疏度五方面描述數(shù)據(jù)集MovieLens(http：//grouplens.org/datasets/movielens/)與 Book-Crossing(http：//www2.informatik.unifreiburg.de/～cziegler/BX/)。 由 于內(nèi)存限制，對(duì)Book-Crossing數(shù)據(jù)集進(jìn)行縮減，篩選這些用戶(hù)和推薦項(xiàng)：對(duì)20個(gè)及以上的推薦項(xiàng)進(jìn)行打分的用戶(hù)和被10個(gè)及以上用戶(hù)打過(guò)分的推薦項(xiàng)。經(jīng)過(guò)篩選后剩下的數(shù)據(jù)集記作Remaining Book-Crossing，縮減后的Book-Crossing數(shù)據(jù)信息如表4所示，沒(méi)有使用數(shù)據(jù)集中提供的隱式信息。

Table 4 Detail information of dataset表4 數(shù)據(jù)集詳細(xì)信息統(tǒng)計(jì)

5.3 多樣性與準(zhǔn)確度度量

在推薦系統(tǒng)中，針對(duì)不同角度的多樣性存在不同的度量方式。文獻(xiàn)[12]列舉出不同的多樣性度量方法，其中，Hurley等[11]、Aytekin等[5]和Bradley等[21]描述了一種能有效度量特定用戶(hù)推薦列表多樣性的方法。該方法計(jì)算用戶(hù)推薦列表中兩兩推薦項(xiàng)相異度的平均值，定義如下：

設(shè)I={i1，i2，…，in}為所有推薦項(xiàng)的集合，U={u1，u2，…，un}是全部用戶(hù)的集合，那么用戶(hù)u(u∈U)的推薦列表Ru?I的多樣性Div為：

其中，sim(i，j)是推薦項(xiàng)i，j∈I的相似度，N為推薦列表的長(zhǎng)度。

盡管等式（8）是一種合理的多樣性度量方法，但是僅僅考慮推薦列表的不相似度不能更完整地反映推薦結(jié)果的多樣性。比如，尚未考慮推薦結(jié)果的類(lèi)別覆蓋度。Vargas等[19]利用概率方式從類(lèi)型覆蓋度和類(lèi)型非冗余度兩方面衡量推薦列表的多樣性，其被定義為：

這是一種新穎的度量方法，但只結(jié)合類(lèi)型這一單一因素[12]。受此啟發(fā)，提出一種新穎的多樣性度量方法DisCoverDiv，形式化表示為等式（10）：

其中，Dis(Ru)為推薦結(jié)果Ru中兩兩推薦項(xiàng)之間的不相似度，可以通過(guò)等式（8）獲得，Cover(Ru)是推薦結(jié)果Ru所覆蓋的類(lèi)別數(shù)目|C(Ru)|占推薦列表長(zhǎng)度|Ru|的比例，其被描述成等式（11）：

準(zhǔn)確率（Precision）作為衡量結(jié)果準(zhǔn)確度的標(biāo)準(zhǔn)在推薦系統(tǒng)[8]等領(lǐng)域有著廣泛的應(yīng)用，利用準(zhǔn)確率評(píng)價(jià)top-k推薦列表的準(zhǔn)確度，其定義如下：

其中，Ru為用戶(hù)u∈U的推薦結(jié)果列表，T?I為用戶(hù)u評(píng)過(guò)5或10分的商品集合。在準(zhǔn)確度度量中，假設(shè)用戶(hù)對(duì)推薦項(xiàng)的評(píng)分越高，該推薦項(xiàng)與用戶(hù)興趣的相關(guān)度也越高?；诖耍瑑H選擇用戶(hù)評(píng)過(guò)滿(mǎn)分5分（MovieLens數(shù)據(jù)集）或10分（Book-Crossing數(shù)據(jù)集）的推薦項(xiàng)進(jìn)行測(cè)試。正如文獻(xiàn)[5]中提到，這種做法往往會(huì)比真實(shí)的準(zhǔn)確度低。

5.4 實(shí)驗(yàn)結(jié)果

將PDM貪心算法分別應(yīng)用到MovieLens、Book-Crossing兩個(gè)真實(shí)的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。首先，觀(guān)察了多樣性和準(zhǔn)確率隨著閾值變化的影響。實(shí)驗(yàn)中推薦列表長(zhǎng)度k=20，聚類(lèi)數(shù)目m=20，隨機(jī)采樣500個(gè)用戶(hù)進(jìn)行多次重復(fù)實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖3、圖4所示。在不同數(shù)據(jù)集上，當(dāng)每個(gè)類(lèi)別上給定的上限閾值較大時(shí)，初始推薦結(jié)果中的類(lèi)別權(quán)重均小于給定的閾值，因此不再需要調(diào)整，最后的推薦結(jié)果與初始推薦結(jié)果一致，圖像基本保持不變，多樣性較低，但此時(shí)的準(zhǔn)確度較高；隨著閾值不斷降低，初始推薦結(jié)果中的類(lèi)別權(quán)重開(kāi)始重新調(diào)整分配，將大于閾值的部分分配到權(quán)重最小的類(lèi)別上，最終推薦結(jié)果的多樣性逐漸增大，與此同時(shí)，準(zhǔn)確度也隨之降低。如圖5所示，這也客觀(guān)地反映了多樣性與準(zhǔn)確度之間的對(duì)立關(guān)系：準(zhǔn)確率伴隨多樣性的提高而降低。

其次，還與三種基準(zhǔn)算法Max-sum、PDRank、GraphRec進(jìn)行比較。本次實(shí)驗(yàn)，觀(guān)察不同方法下多樣性和準(zhǔn)確度隨推薦列表長(zhǎng)度top-k的變化情況。同樣地，隨機(jī)采樣500個(gè)用戶(hù)進(jìn)行多次重復(fù)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖6～圖9所示：從圖中可以看出，隨著top-k逐漸增大，四種方法的多樣性和準(zhǔn)確度都逐漸降低。

Fig.3 Change of diversity with different thresholds圖3 多樣性隨閾值的變化情況

Fig.4 Change of precision with different thresholds圖4 準(zhǔn)確率隨閾值的變化情況

Fig.5 Relationship between precision and diversity圖5 多樣性與準(zhǔn)確率之間的關(guān)系

Fig.6 Change of diversity with top-k(MovieLens)圖6 多樣性隨top-k的變化情況（MovieLens）

Fig.7 Change of precision with top-k(MovieLens)圖7 準(zhǔn)確率隨top-k的變化情況（MovieLens）

Fig.8 Change of diversity with top-k(Book-Crossing)圖8 多樣性隨top-k的變化情況（Book-Crossing）

Fig.9 Change of precision with top-k(Book-Crossing)圖9 準(zhǔn)確率隨top-k的變化情況(Book-Crossing)

此外，針對(duì)那些對(duì)推薦項(xiàng)打分較少的用戶(hù)，以及被較少用戶(hù)打了分的數(shù)據(jù)進(jìn)行相同的實(shí)驗(yàn)，結(jié)果如圖10、圖11所示，實(shí)驗(yàn)表明所提出的方法在該數(shù)據(jù)集上仍然能夠獲得較好的折中效果；對(duì)比圖9、圖11，Remaining Book-Crossing數(shù)據(jù)集上的準(zhǔn)確度相對(duì)較低，主要原因在于較高的稀疏率（99.97%）導(dǎo)致預(yù)測(cè)評(píng)分階段的誤差率升高。

Fig.10 Change of diversity with top-k(Remaining Book-Crossing)圖10 多樣性隨top-k的變化情況（Remaining Book-Crossing）

Fig.11 Change of precision with top-k(Remaining Book-Crossing)圖11 準(zhǔn)確率隨top-k的變化情況(Remaining Book-Crossing)

由于在PDM、Max-sum方法上均施加了劃分?jǐn)M陣約束，它們的多樣性效果優(yōu)于其他兩種方法。然而，PDM方法不僅考慮了用戶(hù)對(duì)不同類(lèi)別的偏好程度，而且還考慮了不同用戶(hù)對(duì)推薦列表中相同類(lèi)別內(nèi)部多樣性的偏好程度，因此本文提出的PDM方法在多樣性和準(zhǔn)確度兩方面均優(yōu)于其他三種方法，并且能夠獲得更好的折中效果。

再次，報(bào)告了四種不同方法生成推薦列表中類(lèi)別的召回率。如表5所示：根據(jù)前面的分析，由于在PDM、Max-sum方法上施加了非均勻擬陣約束，因此它們?cè)陬?lèi)別簇上的召回率是相同的，且能夠覆蓋更為廣泛的類(lèi)別。而PDRank、GraphRec兩種方法由于受到均勻擬陣約束，推薦結(jié)果僅來(lái)自于查詢(xún)用戶(hù)興趣相關(guān)的少數(shù)幾個(gè)類(lèi)別中，因此這兩種方法推薦結(jié)果的類(lèi)別召回率相對(duì)較低。

Table 5 Category cluster recall表5 類(lèi)別簇上的召回率

最后，還進(jìn)行了一些重復(fù)實(shí)驗(yàn)來(lái)比較四種不同多樣性推薦算法生成多樣性推薦結(jié)果所需的時(shí)間。如表6所示：記錄了為一個(gè)用戶(hù)生成不同長(zhǎng)度的多樣性推薦結(jié)果所需的平均時(shí)間，PDM、Max-sum、PDRank三種算法在推薦過(guò)程中都同步考慮了推薦結(jié)果的多樣性和相關(guān)性，生成最終結(jié)果相對(duì)耗時(shí)，而GraphRec算法則分為兩個(gè)階段進(jìn)行，第一階段進(jìn)行相關(guān)性排序，第二階段在相關(guān)性排序結(jié)果的基礎(chǔ)上進(jìn)行多樣性排序。最后選擇排名靠前的k個(gè)結(jié)果作為最終推薦結(jié)果，該算法主要為內(nèi)排序操作，速度較快。不同于Max-sum算法，PDM算法通過(guò)在類(lèi)別簇內(nèi)局部貪心選擇該類(lèi)別中滿(mǎn)足PDM模型的結(jié)果，而不是在每次貪心選擇均要遍歷整個(gè)推薦項(xiàng)集合，因此PDM算法比Max-sum算法耗時(shí)更短。

Table 6 Time to generate diversified recommendation result for a user表6 為一個(gè)用戶(hù)生成多樣性推薦結(jié)果所需的時(shí)間

6 結(jié)束語(yǔ)

本文主要研究了個(gè)性化推薦中的多樣性推薦問(wèn)題，針對(duì)現(xiàn)有多樣性方法的不足，提出非均勻劃分?jǐn)M陣約束下的多樣性最大化問(wèn)題，并將多樣性最大化問(wèn)題建模為非均勻劃分?jǐn)M陣約束下的子模函數(shù)優(yōu)化問(wèn)題，提出了一種基于用戶(hù)偏好的多樣性推薦算法PDM。算法的多樣性不僅考慮用戶(hù)偏好能夠覆蓋廣泛的類(lèi)別，而且也考慮相同類(lèi)別中偏好冗余程度小、差異性較大的推薦，最后設(shè)計(jì)了貪心算法求解該問(wèn)題。不同數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果證明了提出方法的可行性，能夠在多樣性和準(zhǔn)確度上取得良好的折中效果。在進(jìn)一步工作中，將結(jié)合推薦項(xiàng)的顯式評(píng)分和隱式內(nèi)容采用機(jī)器學(xué)習(xí)方式深入挖掘基于大數(shù)據(jù)背景下的有效信息和高效率的多樣性推薦方法，比如，如何更加智能地設(shè)置閾值等。