基于用戶偏好和動態興趣的多樣性推薦方法

鄧明通，劉學軍，李 斌

(南京工業大學 計算機科學與技術學院，南京 211816)

1 引 言

近年來，推薦系統已經成為電子商務網站或資料庫網站中幫助其推廣業務以及幫助用戶尋找項目的必備工具.作為一個有效的解決信息過載問題的工具，推薦系統能夠從巨大的項目池中給用戶推薦符合其偏好的項目集合.

目前已有的推薦系統多注重準確性，如何提高多樣性越來越成為推薦任務中的關鍵問題[1].例如，當用戶在電影資料庫網站IMDB1中搜索電影《致命彎道》后，所有關于《致命彎道》系列的電影都會被推薦，如圖1所示.從準確性的角度，推薦列表是令人滿意的，因為目標用戶喜歡《致命彎道》.然而，由于推薦結果缺乏多樣性，不利于拓寬用戶的視野，從而讓用戶感到厭煩.事實上，拓寬用戶的視野已經成為推薦系統的重要特性之一[1].一個能夠開拓用戶視野的系統可以獲得一個雙贏的結果：用戶可以找到更多的有趣的項目，網站經營者可以增加他們的銷售額，提高用戶滿意度.冷啟動問題同樣

圖1 IMDB網站中關于《致命彎道》的推薦列表Fig.1 A recommended list of "wrong turn" on the IMDB website

也是目前大多數推薦系統所面臨的缺陷[2].本文對用戶歷史反饋信息通過聚類分析得出用戶的多樣傾向度，然后引入時間衰減函數，動態調整用戶的歷史評分數據，最后將矩陣分解和項目疲勞函數相結合，并加入多樣傾向度調節兩者所占比重.當新用戶加入系統時，通過網格索引為其產生最信任鄰居，新用戶缺失的反饋信息由最信任鄰居代替，從而有效緩解了用戶冷啟動問題，并能在保證準確率的前提下提高推薦結果的多樣性.

本文文章結構如下：第2節簡要介紹相關工作以及目前的研究現狀，第3節具體介紹產生最信任鄰居的過程并構造項目疲勞函數，第4節介紹基于用戶偏好和動態興趣的多樣性推薦方法，第5節介紹驗證本文所提出算法的相關實驗，第6節對本文進行簡短總結以及指出未來的工作方向.

2 相關工作

推薦系統的主要目標是向用戶推薦一組滿足其要求的個性化列表，根據用戶的歷史行為數據做出推薦.對項目的評分數量少于五個的用戶通常被視為冷啟動用戶[3]，傳統的推薦算法在解決數據稀疏性和冷啟動問題時效果難以令人滿意.文獻[4]將用戶進行聚類分組，通過PageRank算法識別每個簇中的專家，對于冷啟動用戶，將其未評分的項目分配到每個簇中，由簇內專家確定預測評分.文獻[5]通過定義多個指標，例如評分相似度，信任度等為冷啟動用戶計算其信任用戶集，進而采用傳統的協同過濾推薦算法為其產生推薦.文獻[6]通過朋友關系或人口相似性等特征計算新用戶與已有用戶的偏好得分，通過對用戶聚類，計算每個簇中用戶與新用戶的偏好得分，將得分最高的簇作為推薦的依據.上述的推薦方法雖然一定程度上緩解了用戶冷啟動問題，但是忽略了推薦的多樣性.

目前對于多樣性的研究主要分為兩個方面：總體多樣性(aggregate diversity)和個體多樣性(individual diversity).文獻[7]為了提高推薦的個體多樣性，提出了使用張量分解揭示包括社區、用戶和社會標簽的多模式數據中潛在主題的框架.文獻[8]提出了一種面向多樣性的熱傳導算法，與面向準確度的能量擴散方法結合，調節精確度與多樣性的平衡.文獻[9]結合了傳統協同過濾和概率主題建模的優點，它為用戶和項目提供了可解釋的潛在結構，該方法雖然可以在一定程度上提高推薦的總體多樣性，但是推薦結果還是會偏向于熱門項目.上述學者對于多樣性的研究都集中在項目集合上，而沒有考慮到用戶自身對于多樣性的偏好程度，且當用戶冷啟動時，推薦結果很難達到預期的效果.

本文提出了基于用戶偏好和動態興趣的多樣性推薦方法，主要致力于向目標用戶推薦符合其多樣性偏好程度的個性化列表.本文的主要工作如下：

1)對新用戶通過網格索引為其產生最信任鄰居，同時為了增加冷門項目被推薦的權重，構造了受長尾分布約束的項目疲勞函數.

2)通過對用戶歷史反饋信息分析用戶對于多樣性的偏好程度，提出了多樣傾向度的概念，并通過聚類分析計算出用戶的多樣傾向度.

3)通過使用時間衰減函數對用戶歷史評分數據調整后，提出了將矩陣分解與項目疲勞函數相結合的DRMUD算法，并加入多樣傾向度調節項目疲勞函數所占權重.

4)在真實數據集上對本文提出的方法進行了實驗，結果證實DRMUD能夠獲得較好的結果.

3 最信任鄰居和項目疲勞函數

3.1 為冷啟動用戶產生最信任鄰居

在實際的電子商務網站或資料庫網站中，有的用戶積極主動，愿意對相關項目進行評分，而部分用戶相對消極被動，不愿意對項目進行評分.Hernando A等人的研究[10]表明評分越多的用戶，其對推薦系統的意義越大，有效利用評分多的用戶可以提高推薦系統的準確性，若用戶對項目的評分越接近所有用戶對項目的平均評分，則該用戶的評分準確度就越高[11].對于用戶u評分的準確度，本文通過公式(1)衡量：

(1)

因為評分數越少同時準確度越低的用戶分布在坐標的左下角，所以左下角對應著信任度較低的用戶索引；評分數越多同時準確度越高的用戶分布在坐標的右上角，所以右上角部分對應著信任度較高的用戶索引.冷啟動用戶的最信任鄰居的選取可以通過網格索引的方式解決，具體訪問方式如下：

圖2 用戶的分布模型圖Fig.2 Distribution model of the user圖3 用戶的查詢方式Fig.3 User's query method

因為C5,5中存儲著信任度最高的用戶，因而優先訪問最右上角的C5,5，計算C5,5中各用戶的屬性向量與目標用戶屬性向量的相似度S，如果相似度S大于0，則將其加入候選鄰居列表，之后的訪問次序是{C5,4→C4,5→C5,3→C4,4…}.最終選取候選鄰居列表中與目標用戶屬性相似度最大的鄰居作為最信任鄰居，算法具體過程如下：

算法1：為目標用戶u產生最信任鄰居T(u)

輸入：候選鄰居數n

輸出：目標用戶u的最信任鄰居T(u)

1) 將候選鄰居列表C(u)初始化為空；

2) 將隊列H初始化為空；

3) 令C為最右上角的格子，將其加入到隊列H中；

4) REPEAT：H不為空且C(u)中的鄰居數

5) 彈出H中的第一個元素Ci，j；

6) FOR EACH 用戶t INCi，j

7) IF(相似度S(t，u)>0) THEN

8) 將用戶t加入到C(u)中；

9) END FOR

10) IF(Ci，j-1不在H中)將其加入隊列H；

11)IF(Ci-1，j不在H中)將其加入隊列H；

12) C(u)中與用戶屬性相似度最大值max_sim=0；

13) FOR EACH 鄰居m IN C(u)

14) IF(相似度S(m，u)>max_sim)

15) max_sim=相似度S(m，u)；

16) END FOR

17) T(u)= C(u)中max_sim對應的鄰居用戶；

18) RETURN T(u)

對于候選鄰居數目n，通常設定為數據集中鄰居數量占總體用戶數量的15%[13].

3.2 受長尾分布約束的項目疲勞函數

定義1.長尾分布[15].令S(x)為任意一個分布的累積分布函數，互補函數為Sc(x)=1-S(x).如果滿足對任意γ>0，當t→∞時，有eγtSc(x)→∞，則稱S(x)對應的分布為長尾分布.

為了滿足定義1中描述的長尾分布的條件，文獻[15]提出了由n個底為e的指數函數線性組合描述長尾分布函數：

(2)

數據集中項目的被評價次數符合長尾分布，將數據點記為(xi，yi)(i=1，…，h)，其中，xi為項目被評分次數的排名，yi為項目被評分的次數，h為項目總數，F(x)表示P(x)與數據(xi，yi)的平方差：

(3)

其中，ωi>0為點的權系數，可通過求n階非線性方程組得到使F(x)最小的參數pj，λj>0(j=1，…，n)，進而求得滿足長尾分布描述的P(x).文獻[15]進一步通過對韋伯分布的擬合效果分析得出當n=2時，對長尾分布的描述效果最優，也即P(x)=p1e-λ1x+p2e-λ2x+C.

由于項目被評價的次數呈長尾分布，為了增加對冷門項目的推薦，提高推薦的多樣性，通過構造與評價次數負相關的項目疲勞函數來提高冷門項目的推薦權重，令函數g(x)=1/(1+e-x)將長尾分布的函數值P(x)映射到[0，1]之間，則項目疲勞函數η(x)可表示如下：

(4)

4 基于用戶偏好和動態興趣的多樣性推薦方法

4.1 用戶的多樣傾向度

定義2.多樣傾向度.設項目集合中所有項目經過聚類后的類簇數為K，用戶反饋信息中項目的子類數目為L，則用戶的多樣傾向度為ω=L/K.

通過對用戶歷史反饋信息研究發現，大部分用戶的歷史反饋信息中都存在很多不同種類的項目，項目的種類數越多則說明用戶越偏好于多樣性.本文通過K均值聚類算法對項目聚類，K均值聚類算法是一種基于形心的技術，需要計算不同類型的項目相似度.對于項目特征，本文利用項目的屬性信息，令項目a和b在k維屬性特征空間上的特征值分別為fa={a1，a2，…，ak}，fb={b1，b2，…，bk}，則項目a和b的相似性計算如公式(5)所示：

(5)

其中，sima，b∈[0，1].K均值聚類的過程可描述如下：

1)任意選擇K個對象作為K個初始的簇中心，根據與簇中心的相似度，每個對象被分配到最相似的一個簇.

2)更新簇中心.根據簇中當前對象，重新計算每個簇的均值，使用新的簇中心，把對象重新分配到離簇中心最相似的簇中.

3)重復步驟2，迭代地將對象重新分配到各個簇，改進劃分的過程直至對象的重新分配不再發生，聚類過程返回結果簇.

他的筆下，有一個瑰奇的門派——逍遙派。這個門派的掌門人，除了武功奇高之外，還要面如冠玉，姿容英偉。也許是一種巧合，放眼中國籃壇，擔得起“逍遙王”這個外號的，也只有山東籃壇的代表人物鞏曉彬了。

使用K均值聚類算法得到所有項目的K個類簇后(離群點除外)，將用戶的歷史反饋記錄中的項目逐一與聚類完成后的K個簇進行比對后可以得到L個子類(L<=K)，L即為用戶歷史反饋記錄中項目的子類數量，則用戶的多樣傾向度通過定義2即可求得.

4.2 多樣性推薦方法

用戶的興趣會隨著時間的推移而發生變化，越近的評分越能表示用戶當前的興趣，為了保證推薦的準確率，讓用戶的評分值更符合用戶的動態興趣，受Liu M等人的研究[12]啟發，本文引入了艾賓浩斯遺忘曲線模擬用戶反饋信息重要性的衰減過程，艾賓浩斯遺忘曲線中的遺忘因子decay(t)表示如下：

(6)

其中，δ是遺忘系數，δ∈[0，1]，其值越大，衰減過程越快.t0，tm，t分別代表數據集中的最早時間，最遲時間和當前項目評分時間.令r(u，i，t)為用戶u在t時刻對項目i的評分，則引入了艾賓浩斯遺忘曲線后新的評分可表示如下：

r′(u，i，t)=r(u，i，t)*decay(t)

(7)

當新用戶加入系統中時，由于其還沒有或只有很少的歷史評分數據，此時可以用其最信任鄰居的評分代替，從而緩解了用戶冷啟動問題.

本文首先采用時間衰減函數調整用戶對項目的評分值；進而使用矩陣分解計算得出用戶對項目的初始偏好得分，同時加入項目疲勞函數調整偏好得分，增加推薦結果的多樣性，矩陣分解的目標函數如下：

(8)

其中，U為用戶隱含特征矩陣，V為項目隱含特征矩陣，對于每一個用戶i和項目j的對(i，j)，rij表示用戶i對項目j的評分.rij∈R，R為評分矩陣.λu和λv是正則項系數，通過使用交替最小二乘法求解可以得到ui和vj相應的更新公式：

ui=(VVT+λE)-1VRi

(9)

vj=(UUT+λE)-1URj

(10)

(11)

對電子商務網站的銷售記錄研究發現，項目的銷量呈長尾分布，項目的被評價次數也同樣呈長尾分布[14]，當用戶被多次推薦相同的項目會產生項目疲勞[16].為了進一步增加冷門項目被推薦的概率，需要提高對冷門項目的推薦權重，因此將公式(11)改寫為：

(12)

其中，η(x)為項目疲勞函數；ω為多樣傾向度，用來調節項目疲勞函數所占比重，當新用戶加入到系統中時，其多樣傾向度可以用其最信任鄰居的多樣傾向度代替；系數μ用來調節η(x)的值域范圍，其值為評分范圍的最大值.

將對應的偏好得分降序排序，選取top-n作為最終推薦的候選.

算法2.多樣性推薦算法DRMUD

輸入：用戶評分數據集D，待推薦項目集合Item

輸出：每個用戶的top-n推薦列表

Begin

1)IF(用戶u 為新用戶)通過網格索引計算出其最信任鄰居，u缺失的評分數據和多樣傾向度由其最信任鄰居的相關數據代替；

2)通過時間衰減函數decay(t)調整用戶對項目的評分數值；

3)對調整后的評分數據進行矩陣分解并使用交替最小二乘法求解U*和V*；

6)由定義2計算用戶的多樣傾向度ω；

End

5 實驗及結果分析

5.1 實驗數據集

本文實驗數據采用了Movie Lens數據集，該數據集由美國明尼蘇達州立大學Group Lens研究小組提供，包括6040個用戶對3952部電影的約100萬條電影評分信息，每個用戶至少評價了20部電影，且評分范圍為1～5，“1”表示“poor”(不喜歡)，“5”表示“perfect”(非常喜歡).本文從中選取了943個用戶對1682部電影的大約100000次評分數據作為實驗數據集，稀疏度為93.7%.

實驗中，在非冷啟動場景下，我們從數據集中隨機抽取80%作為訓練集，其余的20%作為測試集.在冷啟動場景下，由于新用戶加入到系統中時還沒有評分數據，而此數據集中不存在新用戶，因此本實驗從數據集中隨機抽取了100至300名用戶作為新用戶，其評分數據作為測試集，其余用戶的評分數據作為訓練集.

5.2 評價標準

5.2.1 推薦準確性評測指標

本實驗采用平均絕對偏差MAE(Mean Absolute Error)作為度量準確性的標準，它是一種統計精度度量方法，同時也是最常用的一種推薦質量度量方法.其通過計算預測評分與實際評分之間的偏差來衡量預測的準確性.MAE的值越小，表明推薦質量越高.

假設預測的用戶評分集合為{p1，p2，…，pN}，對應的實際用戶評分集合為{q1，q2，…，qN}，N表示預測的次數，則MAE的計算公式如下：

(13)

5.2.2 推薦多樣性評測指標

高準確性一直是目前大多數推薦系統的衡量標準，但是系統要以“用戶的長期維系”為目標，因此提高推薦結果的多樣性非常重要.對推薦結果的多樣性評測主要包括兩個方面：總體多樣性和個體多樣性.

對于總體多樣性，本實驗采用信息熵[18]評測.信息熵是信息理論中用于度量信息量的一個概念，如果系統越是有序，那么信息熵越低，反之越高.我們認為如果推薦結果中所有的項目都能夠出現，并且出現的次數相差不大，那么系統具有很好的挖掘長尾項目的能力，將不同推薦列表中項目的出現次數稱為該項目在推薦結果中的流行度，信息熵的計算公式如下：

(14)

其中，p(i)等于項目i的流行度除以所有項目流行度之和，信息熵越大，表明算法挖掘長尾項目的能力越好.

對于個體多樣性，我們計算每個用戶u的推薦結果R(u)中兩兩項目的不相似程度D(R(u))，進而求得所有用戶的推薦列表不相似程度的均值D：

(15)

(16)

5.3 實驗過程

5.3.1 類簇個數的取值

在K均值聚類算法中，不同的K值對聚類效果有著重要的影響，本實驗采用輪廓系數[17]來確定類簇的個數，項目o的輪廓系數s(o)為：

(17)

(18)

表1 不同的類簇個數對聚類效果的影響Table 1 Effect of different clusters on the clustering effect

從表1中可以看出，類簇數為14時的平均輪廓系數最大，其值為0.5558，所以本實驗中類簇數為14時聚類效果最好，在接下來的實驗中，將類簇數設置為14進行實驗.

表2 不同的ω值所占的百分比Table 2 Percentage of different ω

5.3.2 多樣傾向度ω的分布特點

在DRMUD算法中，多樣傾向度ω起到了很重要的作用，用來平衡準確性和多樣性的比重，ω越大表明算法受項目疲勞函數的影響力越大.由5.3.1節可知，K=14時聚類效果最好，本實驗分別計算了數據集在K=14時30次聚類完成后各用戶評分過的電影類別數，并計算了用戶30次多樣傾向度ω的平均值，得到用戶的多樣傾向度ω的分布情況，結果如表2所示.

從表2中我們可以看出，大部分的用戶的多樣傾向度ω的值集中在[0.2，0.3)和[0.3，0.4)區間內，這說明了大部分用戶對于推薦系統的多樣性有一定的要求，如果我們只以傳統的基于準確性為標準的算法進行推薦是不能夠滿足要求的.

5.3.3 遺忘系數δ的調整

在DRMUD算法中，遺忘系數δ起到了很重要的作用，它可以控制用戶興趣的衰減速度，δ越大用戶的興趣衰減越快.為了計算遺忘系數δ對于推薦結果的影響，本文分別對于不同δ取值在非冷啟動場景下的Top-10、Top-20推薦結果進行了對比，評價標準為MAE，結果如圖4所示.

從圖4中我們可以發現，遺忘系數δ的取值對實驗結果有較為顯著的影響，隨著δ的增加，MAE逐漸降低，算法準確度不斷提高；但當δ的值增大到閾值時(本文中是0.2)，算法準確度開始下降，因而本文將δ設置為0.2.推薦的準確性隨著δ的取值不斷變化，也充分說明了用戶的興趣是動態變化的，證明了本文算法的有效性.

5.3.4 多樣性和準確性的對比實驗

為了展示本文提出的DRMUD算法的有效性和高效性，在非用戶冷啟動場景下，本文同以下兩種方法進行了比較：

1)傳統MF：該方法通過對用戶的瀏覽行為進行矩陣分解來計算用戶對于項目的偏好.

2)CTR[9]：該方法為用戶和項目提供了可解釋的潛在結構，增加了推薦的多樣性.

由于Movie Lens數據集中用戶對電影的評分范圍為1-5，因此設置公式(12)中的參數μ=5.實驗中我們分別比較了本文提出的DRMUD算法同其它算法在準確性，個體多樣性以及總體多樣性指標上的不同表現.在非用戶冷啟動場景下的實驗結果如圖5-圖7所示.

圖4 不同遺忘系數的取值對準確性的影響Fig.4 Different forgetting coefficients on the accuracy of the impact

圖5 不同算法的準確性對比Fig.5 Comparison of the accuracy of different algorithms

圖6 不同算法的總體多樣性對比Fig.6 Comparison of the aggregate diversity of different algorithms

圖7 不同算法的個體多樣性對比Fig.7 Comparison of individual diversity of different algorithms

從圖5中可以看出，由于DRMUD算法加入了項目疲勞函數，增加了推薦的多樣性，其準確性與CTR模型相比略顯不足，但是由于DRMUD算法在利用了用戶的評分信息的同時考慮了時間因素，而傳統的MF模型和CTR模型都沒有考慮時間因素，當推薦的項目逐漸增多的時候，DRMUD算法的準確性不斷提高，與CTR模型的差距不斷縮小，且優于傳統MF模型，因此，DRMUD算法的準確性還是在可以接受的范圍之內.

從圖6和圖7中可以看出，由于本文提出的DRMUD算法加入了項目疲勞函數，增加了冷門項目的推薦權重，綜合三種不同的推薦算法，包括總體多樣性和個體多樣性兩個方面，DRMUD算法均能夠取得較好的效果.在總體多樣性方面，DRMUD能夠在全局上推薦更多不同種類的項目，有利于保證推薦系統的長期性能；在個體多樣性方面，DRMUD能夠為單個用戶提供盡可能豐富的推薦列表，有利于拓寬用戶的視野，提高用戶的滿意度.因此，本文提出的DRMUD算法能夠有效向目標用戶推薦符合其多樣性偏好程度的項目集合.

在用戶冷啟動場景下，本文同以下兩種方法進行比較：

1)ECWT[4]：對于冷啟動用戶，將其未評分的項目分配到每個簇中，由簇內專家確定預測評分.

2)PSCU[6]：通過對用戶聚類，計算每個簇中用戶與新用戶的偏好得分，將得分最高的簇作為推薦的依據.

實驗分別從數據集中抽取了100，200，300名用戶作為冷啟動用戶，驗證其在Top-10、Top-20推薦結果下的準確性，總體多樣性和個體多樣性的表現情況，如表3、表4所示.

表3 冷啟動場景下Top-10推薦效果比較Table 3 Top-10 recommendations for cold start scenarios

從表3和表4可以看出：1)本文采用的基于網格索引的方法由于綜合考慮了用戶的評分數量，評分準確度和用戶屬性相似度，同時本文還考慮了時間衰減因素，其準確性明顯高

表4 冷啟動場景下Top-20推薦效果比較Table 4 Top-20 recommendations for cold start scenarios

于其它兩種方法.這說明僅考慮用戶的評分信息將用戶或項目聚類的方法不能很好的模擬新用戶的偏好.2)本文提出的DRMUD方法由于加入了項目疲勞函數，調整了對于冷門項目的推薦權重，其總體多樣性和個體多樣性相對于其他兩種方法都更優異，進而論證了這一方法的正確性.

6 總 結

針對如何向目標用戶推薦符合其多樣性偏好程度的項目集合，本文提出了基于用戶偏好和動態興趣的多樣性推薦算法DRMUD，通過K均值聚類算法對項目進行聚類，分析用戶的多樣性偏好程度，得出用戶的多樣傾向度；通過使用時間衰減函數調整用戶對項目的評分值；將矩陣分解與項目疲勞函數相結合，同時加入多樣傾向度調節項目疲勞函數所占權重，增加了冷門項目被推薦的概率.當新用戶加入時，其評分數據和多樣傾向度可以由其最信任鄰居的相關數據代替.在真實數據集上的實驗表明，DRMUD算法能夠有效緩解用戶冷啟動問題，并能得到準確率較好且多樣性豐富的推薦列表.

在推薦過程中，用戶的歷史記錄信息是推薦算法預測的主要依據，這就帶來了安全隱私問題.有的用戶害怕自己的信息被泄露，或者有些惡意用戶故意利用虛假信息欺騙推薦系統，影響了用戶對系統的信任度，這就需要設計專門的算法保護隱私問題，這將是我們下一步的研究方向.