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

和鳳珍，石進平

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

2.云南省農村信用社 科技結算中心，昆明 650228

1 引言

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

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

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

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

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

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

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

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

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

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

2 相關工作

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

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

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

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

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

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

3.1 問題定義

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

（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），該閾值表示推薦結果中至多有Ti個物品來自類別Li。均勻擬陣是劃分擬陣的一種特例，即當m=1時，劃分擬陣則變為均勻擬陣（uniform matroid）。

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

具體地，令推薦項目集為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個性化多樣性推薦的任務是從各個類別中選擇滿足約束條件的k個元素集合Ru,Ru?I，使得目標函數的效益utility(Ru)最大化。

3.2 整體框架流程

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

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

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

假設1用戶對推薦項目的評分越高，該推薦項與用戶的興趣愛好越相關。

基于這個假設，為方便表達，首先描述相關定義：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 初始類別權重調整算法

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

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

算法1初始類別權重調整算法

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

4.2 PDM貪心算法

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

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

利用貪心算法求解滿足PDM多樣性的前6個檢索結果，輸入查詢為頂點，設用戶輸入的閾值為2，對初始的相關性檢索結果進行類別權重調整后的權重如表3所示：允許類別1中的頂點在結果集合中出現2次；允許類別3中的頂點在結果集合中出現1次。

Table 2 Relevance of vertex in graph G表2 圖G中頂點之間的相關度

Table 3 Adjusted category weights表3 調整后的類別權重

在類別2內的頂點分別與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中，

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

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

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

算法2PDM貪心算法

5 實驗與結果

實驗執行環境為Intel Core i7處理器，8Cores，每個Core的主頻為3.4 GHz，Windows 10 64 bit操作系統，12 GB內存。實驗程序基于Pandas模塊，采用Python2.7版程序設計語言實現。

5.1 基線算法

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

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

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

（3）PDRank：文獻[2]基于異質學術網絡提出一種融合作者、論文權威度和多樣性的推薦方法。

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

5.2 數據集

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

Table 4 Detail information of dataset表4 數據集詳細信息統計

5.3 多樣性與準確度度量

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

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

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

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

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

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

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

其中，Ru為用戶u∈U的推薦結果列表，T?I為用戶u評過5或10分的商品集合。在準確度度量中，假設用戶對推薦項的評分越高，該推薦項與用戶興趣的相關度也越高。基于此，僅選擇用戶評過滿分5分（MovieLens數據集）或10分（Book-Crossing數據集）的推薦項進行測試。正如文獻[5]中提到，這種做法往往會比真實的準確度低。

5.4 實驗結果

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

其次，還與三種基準算法Max-sum、PDRank、GraphRec進行比較。本次實驗，觀察不同方法下多樣性和準確度隨推薦列表長度top-k的變化情況。同樣地，隨機采樣500個用戶進行多次重復實驗，實驗結果如圖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 多樣性與準確率之間的關系

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)

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

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

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

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

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

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

6 結束語

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