基于差異化資源分配的二部圖推薦算法

張功國，江 洋，成振華，劉 穎

(1.重慶郵電大學通信與信息工程學院，重慶400065;2.重慶市質量和標準化研究院，重慶400023;3.重慶信科設計有限公司，重慶401121)

1 引言

隨著大數據時代的到來，信息過載問題變得越來越嚴重，推薦系統是用于解決信息過載的有效途徑，它用來給用戶推薦可能感興趣的事務[1]。推薦算法是推薦系統的核心，它用于處理輸入信息并將其形成推薦信息。近年來，基于二部圖的推薦算法受到了很多研究者的關注，該算法借鑒了物理學上熱傳導和物質擴散的思想[2]。周濤等人最早提出了一種基于二部圖的物質擴散推薦算法[3]，該算法傾向于給用戶推薦流行項目；文獻[4]在此基礎上對項目的初始資源進行修正，引入一個參數β，通過把項目初始資源k(o)調整為k(o)β，抑制了流行項目的影響，從而提高了算法推薦的多樣性；Becatti等人在文獻[5]中按照一定的重啟動條件設定，在二部圖網絡結構中加入隨機的游走過程，由此來尋找最佳的待推薦節點；He[6]等人考慮到項目對于用戶的吸引作用，提出在二部圖推薦系統中加入反饋調節，在多個數據集中實現了推薦新穎度的提高。

本文結合已有研究提出了一種基于差異化資源分配的二部圖推薦算法。分別對項目初始資源和資源分配系數進行了差異化設置，通過實驗驗證了該算法相比其它類似的算法在推薦精度和多樣性上都有所提升。

2 傳統二部圖推薦算法

將推薦系統建模成二部圖，其中節點的兩個集合分別代表用戶集U和項目集O，當用戶選擇了項目則將它們相連，即兩者形成連邊[7]。一個由n個用戶U={u1，u2…un}和m個項目O={o1，o2，…，om}構成的二部圖可以用鄰接矩陣A={aαi}n，m表示，如果用戶uα選擇了項目oi則aαi=1，未選擇則aαi=0。二部圖推薦算法認為，用戶選擇過的項目有向其推薦其它項目的能力，這樣的能力可以在二部圖中進行傳遞，從而產生推薦。

傳統二部圖推薦算法具體步驟如下：

1)項目初始資源配置

設用戶uα為目標用戶，則各項目初始資源值的表達式如式(1)所示

f(oi)=aαi

(1)

如果用戶uα選擇了項目oi則aαi=1，即該項目的初始資源為1，未選擇則aαi=0。

2)項目將資源傳遞給用戶

在傳統二部圖推薦算法中，第一次資源流轉采用均勻分配的方式由項目流向用戶，項目oi的初始資源f(oi)≥0，則經過第一次資源流轉，任意用戶uβ獲得的資源如式(2)所示

(2)

其中，aβi為鄰接矩陣A={aαi}n，m中的對應元素，k(oi)為項目oi的度即該項目被多少用戶選擇過。

3)用戶將資源再次傳遞給項目

用戶將第一階段獲得的資源傳遞給相對應的項目，也采用均勻分配原則。在該過程中任意項目oj所獲得的資源如式(3)所示

(3)

其中，k(uβ)為用戶uβ的度，即該用戶選擇過多少項目。

4)生成推薦列表

將目標用戶未選擇過的項目按照f(oj)的大小進行排序，將所獲資源最多的前L項推薦給用戶，L為推薦列表長度。

如圖1所示，(a)表示該二部圖由四個用戶和三個項目組成，x，y，z分別表示三個項目的初始資源，(b)表示經第一步資源流轉后每個用戶所獲得的相應資源值，(c)表示經兩步資源流轉以后每個項目最終所獲得的資源。則三個項目的最終資源x′、y′、z′如式(4)所示

(4)

圖1 基于二部圖的資源分配推薦算法資源流轉圖

3 基于差異化資源分配的二部圖推薦算法

傳統二部圖推薦算法在進行初始資源設置時往往僅依靠項目是否被目標用戶選擇而進行0/1設置，這樣會丟失系統里面的很多有用信息；另外在進行資源流轉時也僅僅依靠項目度和用戶度來平均分配，這樣會導致推薦有失準確性。針對以上問題，提出一種基于差異化資源分配的二部圖推薦算法，新算法具體如下：

步驟一：初始資源差異化設置

在現實生活中可能存在著惡意評分等特殊因素，在這種情況下評分不能代表用戶的真實偏好[8]。利用規范化對評分進行處理，消除評分不利影響。評分規范化的預處理方法如式(5)所示

(5)

其中，rαi為用戶uα對項目oi的初始評分，Pi為項目oi得到的平均評分值，Qα為用戶uα對所有項目評分的均值，預處理以后更能體現用戶的真實喜好。若Pi>Qα則代表項目oi受用戶的喜愛，因此對評分進行增強修正，反之對評分進行削弱修正。

為了減小由于用戶評分尺度不同而帶來的計算誤差，進一步優化評分數據，采用最大最小值法[9]進行修正，如式(6)所示

(6)

其中，rmax、rmin分別表示用戶uα在系統中給出的最大和最小評分值，為了預防分母為0，設定極小值p為0.001，同時為了實驗方便，設定極小值q為0.01。

傳統的大多數推薦算法都沒有考慮到“興趣偏移”問題，即用戶的興趣會隨著時間的變化而改變，項目的流行度也會隨時代而變。時間因素在推薦系統中也是一個重要信息，對用戶的喜好有著很大的影響。本文基于德國心理學家艾賓浩斯所提出的記憶遺忘曲線[10]，將時間衰減函數定義為式(7)所示(時間計量單位為天)

(7)

其中，fα，i(t)表示當時間為t時，用戶uα對項目oi“興趣偏移”的衰減率，tα表示用戶uα在系統中初次評分的時間，tα，i表示用戶uα對項目oi進行評分操作的時間。fα，i(t)的取值范圍在e-1到1之間，符合衰減率的要求。

經過評分規范化、最大最小值修正以及時間衰減函數的量化，最終實現了項目初始資源的差異化設置，如式(8)所示

(8)

步驟二：第一階段資源分配

在基于二部圖的推薦算法中，項目將資源根據用戶項目相互之間的選擇關系平均分配給相應的用戶，考慮到以下兩點：①如果兩個用戶共同選擇的項目數比較多，那么他們的興趣相似性可能比較高；②如果兩個用戶對項目的評分大小比較接近，代表其偏好更加的相近。基于此，本文利用修正后的用戶評分相似性函數對第一階段資源分配系數進行差異化設置，使得與目標用戶興趣相似的用戶能夠得到更多的資源。

兩個用戶共同選擇的項目比例如式(9)所示

(9)

其中，Iα和Iβ分別表示用戶uα和uβ所選擇的項目的集合，兩個用戶共同選擇的項目比例越大，他們的興趣就可能越相近。

交互用戶指的是有公共選擇的用戶，他們的交互關系指的是對于項目的喜愛程度是否一致。本文通過積極評分還是消極評分判定用戶交互成功還是失敗。如果用戶對項目評分小于他給出的評分均值，說明它為消極評分；反之則為積極評分。倘若用戶uα和uβ對相同項目oi給出的都是積極或消極評分，說明交互用戶間持有相同觀點，他們交互是成功的；反之交互是失敗的。交互關系判定方法如式(10)所示

(10)

計算兩個用戶評分相似性，需要收集雙方交互間歷史總記錄。假設s和f分別代表交互用戶彼此間成功和失敗次數。即每次交互用戶間項目交互成功，那么s+1(i∈Is)，否則f+1(i∈If)。

結合項目比例系數、交互關系以及評分偏差，最終得到用戶評分相似性函數，如式(11)所示

(11)

其中，Is表示兩用戶交互成功的項目集合，If表示交互失敗的項目集合。

利用新構建的用戶評分相似性函數得到第一階段的資源分配系數，如式(12)所示

(12)

Hα，βi表示用戶uβ與目標用戶uα的相似度占所有選擇了項目oi的用戶與目標用戶uα的相似度之和的比例，取值在0到1之間，Hα，βi越大表示在所有已經選擇項目oi的用戶群體中，用戶uα與uβ比其他用戶更為相似，則項目oi上的初始資源就會較多的傳遞到用戶uβ。

假設選定用戶uα為目標用戶并為其推薦，則在第一階段資源流轉以后傳遞到任意用戶uβ的資源量如式(13)所示

(13)

步驟三：第二階段資源分配

在第二階段資源分配中，推薦者是與目標用戶有共同選擇的用戶，這些用戶更傾向于推薦自己喜愛的項目。因此在第二階段資源分配中也加入了用戶的顯性偏好，把資源分配系數定義成用戶對項目的評分比例zβ，j，如式(14)所示

(14)

其中，Max(β)是用戶uβ在系統中給出的最大評分，zβ，j越大則認為用戶更加愿意推薦該項目給其他用戶。由此所有作為鄰居用戶的推薦者推薦的項目都是各自認為最好的，并且避免了用戶的評分尺度不一的問題。則在第二階段資源流轉后傳遞到任意項目oj的資源如式(15)所示

(15)

其中，k(uβ)為用戶uβ的度，f(uβ)由步驟二所得。

步驟四：推薦：

將目標用戶未選擇過的項目按照f(oj)的大小進行排序，將所獲資源最多的前L項推薦給用戶，L為推薦列表長度。

4 實驗分析

4.1 實驗數據

在選擇數據集時本文選用了推薦系統中最經典的MovieLens數據集和Netflix數據集。前者由943個用戶和1682部電影組成，用戶使用整數1-5對電影進行評分，評分越大表示用戶喜愛程度越強。后者曾用于全球推薦系統競賽，原始的Netflix數據集非常大，本文從中截取了一個由 10000個用戶和6000個電影組成的數據子集，該數據集相對MovieLens數據集的選擇關系要復雜很多。在實驗中，將數據集隨機分成兩部分：80%作為訓練集，用于建立推薦模型，其余20%作為測試集，用于驗證模型性能。為了確保結果更加準確，實驗均采用五折交叉法驗證測試。

4.2 評價指標

準確率是指推薦算法的結果中用戶實際選擇的項目占推薦結果的項目總數的比例，定義如式(16)所示

(16)

其中，hits是為目標用戶準確推薦的項目的數量，recset是推薦列表的長度。準確率越大，說明該推薦結果越能反映出用戶的喜好。

召回率指的是推薦結果中實際的項目命中數占在理論上最大的可能命中數的比例，定義如式(17)所示

(17)

其中，hits是為目標用戶準確推薦的項目的數量，testset是理論上最大的可能命中數。召回率越大，說明推薦結果對用戶的喜好的覆蓋率高，即推薦系統能夠更大程度的滿足用戶的需求。

通常情況下Pr ecision和Re call都是越高越好，然而事實上兩者在某些情況下是相互矛盾的。F1是Pr ecision和Re call的加權調和平均，能夠有效的在準確率和召回率之間取得平衡。其定義如式(18)所示

(18)

F1的值越高，說明推薦算法的綜合準確性越好。

本文使用漢明距離(Hamming distance，HD)來評估推薦算法的多樣性，它描述了用戶間推薦列表之間的差異性。如式(19)所示

(19)

其實，m表示用戶數，L表示推薦列表的長度，Q=|βi∩βj|表示兩用戶的推薦列表中的相同項目的數量，HD越大表明推薦結果越多樣化。

4.3 實驗結果與分析

將本文所提出的基于差異化資源分配的二部圖推薦算法(BGRA)與基于熱傳導的二部圖推薦算法(HC)、基于物質擴散的二部圖推薦算法(MD)、基于物質擴散與熱傳導的混合推薦算法(HPH)以及文獻[11]提出的基于二部圖網絡的非均勻資源分配推薦算法(NURA)進行對比實驗。

首先比較各個算法的推薦集質量，評價指標包括準確率Pr ecision、召回率Re call和F1系數。

圖2 Precision值對比結果

如圖2所示，在兩個數據集中當推薦列表長度較小時，BGRA算法的準確率和HPH(α=0.5)、NURA表現差不多，隨著推薦列表長度的增加，BGRA的準確率明顯要高于其它幾種算法，證明BGRA有著較好的準確率。只考慮推薦多樣性的HC算法明顯要比其中幾種算法的推薦準確率低。

圖3 Recall值對比結果

如圖3所示，隨著推薦列表長度的增加幾種算法的召回率都有所上升，這是因為隨著推薦列表的增加，算法能夠預測到的用戶喜愛的電影數量變多，相應的未能命中的數量就少了。在MovieLens數據集中，BGRA、HPH、NURA三種算法的召回率表現相似。但在相對復雜的Netflix數據集中，BGRA算法在召回率的總體表現要優于其它幾種算法。

圖4 F1值對比結果

如圖4所示，各個算法的F1系數變化曲線轉折點均在推薦列表長度為20的時候。只注重推薦多樣性的HC算法依然是幾種算法中F1系數表現最差的。在MovieLens數據集中，BGRA算法在F1系數方面并不太理想，但在Netflix數據集中優于其它四種算法。

其次在推薦多樣性比較中，如圖5所示。HC算法的推薦多樣性要比MD、HPH算法好很多，在Netflix數據集中本文提出的BGRA算法要好于其它幾種算法，這主要是因為在資源流轉過程中加入了分配系數的差異化設置，使得算法推薦出來的電影更具多樣化。

圖5 HD值對比結果

5 結束語

本文提出了一種基于差異化資源分配的二部圖推薦算法。首先利用評分規范化、最大最小值法以及時間遺忘曲線對項目的初始資源進行了差異化設置。然后分別利用用戶評分相似性函數和用戶偏好函數對兩個階段的分配系數進行了差異化設置，使資源流轉變得更加合理。最后通過實驗證明在較復雜的數據集中算法的準確率和多樣性都有很大的提升。但是隨著數據量的增加，推薦需要的開銷變大，因此下一步研究的重點是如果改善推薦的可擴展性。