和鳳珍，石進平

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

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

1 引言

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

針對多樣性推薦問題，已有一些相關(guān)研究成果[4,10,13]。利用這些方法獲得的推薦結(jié)果不能在多樣性與相關(guān)性之間取得較好的折中。這是因為它們受到均勻擬陣約束（uniform matroid constraints），即假設(shè)推薦項目集中的各個推薦項對于所有用戶具有相同的重要性，如文獻[4,10]。文獻[13]考慮到每個推薦項具有不同的重要性，但尚未考慮用戶的偏好，會導(dǎo)致推薦結(jié)果中相同類別中的推薦項具有較高的冗余度。受此啟發(fā)，本文提出了一種非均勻劃分擬陣約束下的基于用戶偏好的多樣性推薦模型（preferencebased diversified recommendation model，PDM）。該模型在推薦過程中同時考慮了多樣性和相關(guān)性兩個因素，在保證推薦結(jié)果相關(guān)性的前提下，通過在每個類別上施加非均勻劃分擬陣約束，有效提升推薦結(jié)果的多樣性，力爭在相關(guān)性和多樣性之間取得有效折中。

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

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

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

本文工作的主要貢獻如下：

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 基于非均勻劃分擬陣約束的多樣性模型

3.1 問題定義

擬陣M是一個二元組(I,R)，其中I是一個有限集，R是I的子集簇，R被稱為獨立集，它滿足下列性質(zhì)：

（1）? 是獨立集。

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

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

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

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

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

3.2 整體框架流程

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

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

3.3 非均勻劃分擬陣約束下的多樣性模型

假設(shè)1用戶對推薦項目的評分越高，該推薦項與用戶的興趣愛好越相關(guān)。

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

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

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

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

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

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

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

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

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

因此，非均勻劃分擬陣約束下基于PDM的多樣性最大化問題可以定義為：

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

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

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

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

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

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

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

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

4 非均勻劃分擬陣約束下的多樣性推薦算法

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

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

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

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

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

4.2 PDM貪心算法

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

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

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

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

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

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

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

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

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

算法2PDM貪心算法

5 實驗與結(jié)果

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

5.1 基線算法

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

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

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

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

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

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

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

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

5.3 多樣性與準確度度量

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

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

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

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

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

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

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

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

5.4 實驗結(jié)果

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

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

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

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

Fig.5 Relationship between precision and diversity圖5 多樣性與準確率之間的關(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 準確率隨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 準確率隨top-k的變化情況(Book-Crossing)

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

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 準確率隨top-k的變化情況(Remaining Book-Crossing)

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

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

Table 5 Category cluster recall表5 類別簇上的召回率

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

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

6 結(jié)束語

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