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

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

(1.重慶郵電大學(xué)通信與信息工程學(xué)院，重慶400065;2.重慶市質(zhì)量和標(biāo)準(zhǔn)化研究院，重慶400023;3.重慶信科設(shè)計有限公司，重慶401121)

1 引言

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

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

2 傳統(tǒng)二部圖推薦算法

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

傳統(tǒng)二部圖推薦算法具體步驟如下：

1)項目初始資源配置

設(shè)用戶uα為目標(biāo)用戶，則各項目初始資源值的表達(dá)式如式(1)所示

f(oi)=aαi

(1)

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

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

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

(2)

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

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

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

(3)

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

4)生成推薦列表

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

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

(4)

圖1 基于二部圖的資源分配推薦算法資源流轉(zhuǎn)圖

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

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

步驟一：初始資源差異化設(shè)置

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

(5)

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

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

(6)

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

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

(7)

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

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

(8)

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

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

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

(9)

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

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

(10)

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

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

(11)

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

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

(12)

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

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

(13)

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

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

(14)

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

(15)

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

步驟四：推薦：

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

4 實驗分析

4.1 實驗數(shù)據(jù)

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

4.2 評價指標(biāo)

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

(16)

其中，hits是為目標(biāo)用戶準(zhǔn)確推薦的項目的數(shù)量，recset是推薦列表的長度。準(zhǔn)確率越大，說明該推薦結(jié)果越能反映出用戶的喜好。

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

(17)

其中，hits是為目標(biāo)用戶準(zhǔn)確推薦的項目的數(shù)量，testset是理論上最大的可能命中數(shù)。召回率越大，說明推薦結(jié)果對用戶的喜好的覆蓋率高，即推薦系統(tǒng)能夠更大程度的滿足用戶的需求。

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

(18)

F1的值越高，說明推薦算法的綜合準(zhǔn)確性越好。

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

(19)

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

4.3 實驗結(jié)果與分析

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

首先比較各個算法的推薦集質(zhì)量，評價指標(biāo)包括準(zhǔn)確率Pr ecision、召回率Re call和F1系數(shù)。

圖2 Precision值對比結(jié)果

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

圖3 Recall值對比結(jié)果

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

圖4 F1值對比結(jié)果

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

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

圖5 HD值對比結(jié)果

5 結(jié)束語

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