一種針對(duì)群體的列表融合推薦算法

馬遠(yuǎn)坤，崔永鋒，趙中原

(周口師范學(xué)院，河南 周口 466001)

1 簡介

近年來，推薦系統(tǒng)逐漸成為人們在海量數(shù)據(jù)中發(fā)現(xiàn)有價(jià)值信息的重要工具[1-2].在目前的研究中，大部分的推薦算法是針對(duì)單獨(dú)用戶設(shè)計(jì)的，實(shí)際中還有很多應(yīng)用是針對(duì)多人進(jìn)行推薦[3]，例如，針對(duì)多人的電視節(jié)目推薦[2]或者旅游地點(diǎn)推薦.在這些情景下，根據(jù)適合單獨(dú)用戶的推薦算法無法給多人產(chǎn)生滿意的推薦結(jié)果，因?yàn)橐粋€(gè)用戶滿意的推薦結(jié)果對(duì)其他人來說很可能不是太好的選擇.因此，如何選擇推薦內(nèi)容使群組內(nèi)每個(gè)組員都滿意或者接受是面向群組的推薦算法需要解決的主要難題.正是由于這個(gè)難題，目前群組推薦算法的用戶滿意度比較差，因此，研究滿足群組中每個(gè)組員興趣的推薦算法是很有必要的.

2 相關(guān)工作

當(dāng)前群組推薦算法可以歸為兩類[3-4]：基于群組興趣模型的推薦算法和基于列表融合的推薦算法.筆者提出的算法屬于后者，因此，本節(jié)僅分析和比較現(xiàn)有的基于列表融合的推薦算法.目前使用最多的基于列表融合的推薦算法主要有Average Aggregation算法和Borda算法.

Masthoff在對(duì)電視節(jié)目的群組推薦中提出了使用Average Aggregation策略和Least Misery策略來對(duì)群組內(nèi)每個(gè)用戶的推薦列表進(jìn)行融合.Average Aggregation策略將組員對(duì)某個(gè)項(xiàng)目的平均評(píng)分作為群組對(duì)該項(xiàng)目的組評(píng)分，然后將組評(píng)分較高的項(xiàng)目作為群組的推薦內(nèi)容；Least Misery策略將群組內(nèi)所有組員對(duì)某個(gè)項(xiàng)目評(píng)分的最低分作為群組對(duì)該項(xiàng)目的組評(píng)分，然后將組評(píng)分較高的項(xiàng)目作為群組的推薦內(nèi)容.這兩種算法充分考慮了組員的評(píng)分因素，在推薦時(shí)平衡了組員之間的興趣差異.Coppersmith等人研究了Borda算法，該算法使用項(xiàng)目在組內(nèi)每個(gè)組員推薦列表中的平均排名來決定其組評(píng)分的大小，平均排名越高，組評(píng)分就越高.

Linas和Tadas等人[4]對(duì)比了Average Aggregation,Borda和Least Misery[3-4]等一些常見的算法，發(fā)現(xiàn)在不同的群組規(guī)模或群組內(nèi)部相似度的情況下，沒有一種算法效果是最優(yōu)的.此外，群組推薦的效果并不一定隨著組規(guī)模的增加而降低，在某些情況下，組推薦的效果超過了給獨(dú)立用戶推薦的效果.

根據(jù)上面算法介紹可以得出結(jié)論：Average Aggregation算法和Least Misery算法忽略了項(xiàng)目在組員推薦列表中的排名因素；Borda算法忽略了每個(gè)組員給項(xiàng)目的評(píng)分因素.因此，這些算法不可避免地存在著推薦精度上的丟失.

3 HAaB融合算法

為了克服Average Aggregation算法和Borda算法的局限性，筆者提出了HAaB融合算法(Hybrid of Average Aggregation and Borda)，該算法對(duì)Average Aggregation算法和Borda算法進(jìn)行了融合，兼顧了組員推薦列表中項(xiàng)目排名和項(xiàng)目評(píng)分兩種因素.HAaB融合算法的實(shí)現(xiàn)步驟如下.

3.1 生成每個(gè)組員的推薦列表

首先使用針對(duì)獨(dú)立用戶的推薦算法給群組中每個(gè)組員生成推薦列表.本步驟中的推薦算法可以使用任意一種推薦算法.目前流行的推薦算法有很多，比如說：基于內(nèi)容的推薦算法、協(xié)同過濾推薦算法、基于奇異值分解(SVD)的推薦算法等.對(duì)單個(gè)組員的推薦精度越高，最終對(duì)群組推薦的精度也就越高.因此在選擇對(duì)單個(gè)組員的推薦算法之前，筆者對(duì)基于項(xiàng)目的協(xié)同過濾算法、基于用戶的協(xié)同過濾算法、基于內(nèi)容的推薦算法、K最近鄰分類算法、Slope One、SVD推薦算法等幾種最流行的推薦算法進(jìn)行了比較，得出結(jié)論為：SVD推薦算法和Slope One算法的推薦結(jié)果最為精確；但是在算法資源占用方面，Slope One算法消耗內(nèi)存太大.基于該結(jié)論，筆者選擇SVD推薦算法[5]來為每個(gè)組員生成推薦列表.

3.2 組員推薦列表融合

算法對(duì)每個(gè)項(xiàng)目計(jì)算群組中每個(gè)組員對(duì)其的預(yù)測評(píng)分之和作為列表融合策略的一個(gè)影響因素；同時(shí)也計(jì)算每個(gè)項(xiàng)目在群組中每個(gè)組員推薦列表中的排名之和作為另一個(gè)影響因素.由于項(xiàng)目評(píng)分和項(xiàng)目排名對(duì)結(jié)果的影響程度可能不同，因此加入一個(gè)參數(shù)來調(diào)整項(xiàng)目評(píng)分和項(xiàng)目排名對(duì)結(jié)果的影響權(quán)重，以使結(jié)果達(dá)到最優(yōu).如下公式定義了項(xiàng)目組評(píng)分的計(jì)算方法：

(1)

其中，Scoreg(i)代表群組g對(duì)項(xiàng)目i的評(píng)分，rui代表用戶u對(duì)項(xiàng)目i的評(píng)分，pui代表項(xiàng)目i在用戶u的推薦列表中的排名，λ是平衡參數(shù)，用來調(diào)整項(xiàng)目排名和項(xiàng)目評(píng)分對(duì)結(jié)果的影響權(quán)重.

公式(1)把組員推薦列表中項(xiàng)目的評(píng)分和排名兩個(gè)因素進(jìn)行融合得到群組對(duì)項(xiàng)目的評(píng)分.該融合策略中對(duì)結(jié)果起關(guān)鍵作用的是λ的值，對(duì)于不同內(nèi)部相似度的組或者不同規(guī)模的組來說，最優(yōu)的λ值往往不同.由于沒有一個(gè)λ值使推薦結(jié)果在任何情況下都是最優(yōu)的，所以需要通過實(shí)驗(yàn)獲得在每種情況(主要考慮組內(nèi)相似度和組規(guī)模兩個(gè)因素)下λ的最優(yōu)值，然后在每種情況下使用在該情況下最優(yōu)的λ值來進(jìn)行推薦，筆者稱這個(gè)改進(jìn)后的算法為HAaB算法.

4 實(shí)驗(yàn)與分析

為了驗(yàn)證HAaB算法的性能，筆者設(shè)計(jì)了兩套實(shí)驗(yàn).第一套實(shí)驗(yàn)主要分析不同λ值對(duì)結(jié)果的影響；第二套實(shí)驗(yàn)主要對(duì)比HAaB算法和當(dāng)前典型算法的效果，驗(yàn)證HAaB算法的有效性.下面詳細(xì)介紹實(shí)驗(yàn)的設(shè)置和結(jié)果.

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 實(shí)驗(yàn)數(shù)據(jù)

本實(shí)驗(yàn)中使用的數(shù)據(jù)集是MovieLens-1m數(shù)據(jù)集，其中有大約3 900個(gè)電影、6 040個(gè)用戶的1 000 209條評(píng)分記錄.實(shí)驗(yàn)按照電影把數(shù)據(jù)集隨機(jī)分成訓(xùn)練集和測試集，其中訓(xùn)練集包含80%的電影，測試集包含20%的電影.用這種方法得到10組數(shù)據(jù)，然后分別對(duì)這10組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，最后結(jié)果取每組實(shí)驗(yàn)結(jié)果的平均值.

4.1.2 生成群組

由于MovieLens數(shù)據(jù)集中沒有現(xiàn)成的群組數(shù)據(jù)，所以需要手動(dòng)對(duì)用戶進(jìn)行分組.分組的時(shí)候主要考慮兩個(gè)因素：組內(nèi)相似度和組的規(guī)模.根據(jù)組內(nèi)相似度，將組分為高相似度組、低相似度組和隨機(jī)組，因此需要設(shè)定高相似度組和低相似度組滿足的條件.這里使用Pearman相關(guān)公式[6]分析了數(shù)據(jù)集中用戶之間的相似度，結(jié)果如圖1所示.從圖1可以看出，相似度大于0.3的大約占所有數(shù)據(jù)的1/3，相似度小于0.06的大約也占所有數(shù)據(jù)的1/3左右.

圖1 MovieLens組員相似度圖

根據(jù)上述結(jié)果，本實(shí)驗(yàn)定義組內(nèi)每兩個(gè)組員之間的相似度均大于0.3的組為高相似度組，組內(nèi)每兩個(gè)組員之間的相似度均小于0.06的組為低相似度組，隨機(jī)組則不做任何限制.

實(shí)驗(yàn)考慮組的規(guī)模人數(shù)分別為2，3，4，5，6，7，8，考慮組內(nèi)相似度分別為高相似度組、低相似度組和隨機(jī)組.其中，高相似度組、低相似度組和隨機(jī)組分別生成 1 050個(gè)，每種規(guī)模的組有150個(gè)，一共生成3 150個(gè)組.

4.1.3 參數(shù)設(shè)置

正如算法第一步中提到的，組推薦算法需要首先生成群組中每個(gè)組員的推薦列表.因此，實(shí)驗(yàn)中首先使用SVD[5]算法給組員生成推薦列表.SVD算法的參數(shù)根據(jù)之前研究者的經(jīng)驗(yàn)來設(shè)置，因此這里將SVD算法中的特征值數(shù)目設(shè)置為50.通過SVD算法給數(shù)據(jù)集中每個(gè)用戶預(yù)測出對(duì)測試集中所有電影的評(píng)分；實(shí)驗(yàn)中設(shè)置組推薦列表的長度跟測試集中電影的數(shù)目相同.

4.1.4 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)中使用一種信息檢索中評(píng)估網(wǎng)頁排序的方法Discounted cumulative gain(nDCG)[7]來評(píng)估用戶對(duì)有序推薦列表的滿意度.對(duì)于nDCG評(píng)估方法來說，用戶評(píng)分越高的項(xiàng)目排名越靠前，其nDCG的值就越高，因此可以有效地評(píng)估用戶對(duì)有序推薦列表的滿意度.

4.2 實(shí)驗(yàn)結(jié)果與分析

4.2.1 不同λ值對(duì)實(shí)驗(yàn)結(jié)果的影響結(jié)果與分析

為了分析不同的λ值對(duì)推薦效果的影響，筆者對(duì)λ分別取100，200，300，400，500，600，700，800，900，1 000，結(jié)果如圖2、圖3和圖4所示.圖中縱坐標(biāo)代表nDCG的值，橫坐標(biāo)代表內(nèi)部相似度和規(guī)模不同的組.其中l(wèi)md100表示λ值為100時(shí)的算法，其他的與此類似.high_2代表組規(guī)模人數(shù)為2時(shí)的高相似度組的情況；同理，low_3代表組規(guī)模人數(shù)為3的低相似度組的情況，random_8代表組規(guī)模人數(shù)為8的隨機(jī)相似度組的情況，其他情況類似.

圖2 不同值的結(jié)果對(duì)比圖(高相似度組)

圖3 不同值的結(jié)果對(duì)比圖(低相似度組)

從圖2、圖3和圖4中可以看出： 對(duì)于高相似度組來說，組規(guī)模為2時(shí)，λ取100時(shí)算法取得效果最好；對(duì)于規(guī)模為3，5，8的組，λ取400時(shí)效果最好；其他情況下，λ取500效果比較好.對(duì)于低相似度組來說，組規(guī)模為2，3，4的時(shí)候，λ取500或600左右效果最好；當(dāng)組規(guī)模大于4的時(shí)候，λ取1 000的效果很明顯是最優(yōu)的.對(duì)于隨機(jī)組，也有與之前類似的結(jié)果.此外，可以發(fā)現(xiàn)λ取100的時(shí)候?qū)M規(guī)模為2的高相似度組的推薦效果最好，但是對(duì)于別的情況卻表現(xiàn)不佳；λ取1 000在高相似度和隨機(jī)組表現(xiàn)都一般，在低相似度組表現(xiàn)很好.因此可以看出，很難找出一個(gè)λ的值在任何情況下表現(xiàn)都很優(yōu)異.

圖4 不同值的結(jié)果對(duì)比圖(隨機(jī)相似度組)

此外還可以得到如下結(jié)果：對(duì)于低相似度組和隨即組來說，推薦結(jié)果的效果隨著組規(guī)模的增加而降低；然而對(duì)于高相似度組，組規(guī)模為8的時(shí)候效果甚至要好于比他更小規(guī)模的組.這說明組推薦的效果不一定隨著組規(guī)模的增加而降低.

通過上述實(shí)驗(yàn)計(jì)算得到了每種情況下的λ最優(yōu)值，如表1所示.如果針對(duì)高相似度的3人群組進(jìn)行推薦，根據(jù)表1就可以將λ設(shè)置為400以得到最優(yōu)的結(jié)果.

表1 各種情況下λ最優(yōu)數(shù)值

4.2.2 HAaB算法與典型算法的對(duì)比與分析

通過表1中總結(jié)的數(shù)據(jù)，可以實(shí)現(xiàn)使用HAaB算法對(duì)組進(jìn)行推薦.下面對(duì)HAaB算法與之前介紹的幾種典型算法做一下對(duì)比，結(jié)果如圖5、圖6和圖7所示.圖中Random指隨機(jī)推薦方法，Borda代表Borda計(jì)數(shù)算法，LM代表Least Misery算法，AA代表Average Aggregation算法.

圖5、圖6和圖7中結(jié)果表明，HAaB方法無論針對(duì)高相似度組、低相似度組還是隨機(jī)組的推薦效果都是最優(yōu)的.在高相似度組的對(duì)比中，HAaB算法的推薦精度比Average Aggregation算法平均高大概3個(gè)百分點(diǎn)，比其他三種方法平均高出至少10個(gè)百分點(diǎn).在低相似度組的對(duì)比中，HAaB算法的推薦精度比Average Aggregation平均高出5個(gè)百分點(diǎn)左右，比Borda計(jì)數(shù)算法高了將近10個(gè)百分點(diǎn)，比Least Misery高出了30個(gè)百分點(diǎn).此外，Average Aggregation算法的推薦效果一般要優(yōu)于Borda計(jì)數(shù)、Least Misery等算法； Least Misery算法僅僅在高相似度組中效果比Borda好，其他情況下都不如Borda算法，這說明獨(dú)立的算法不一定在每種情況下效果都最好，混合算法可以彌補(bǔ)獨(dú)立算法的缺陷.最后，隨機(jī)算法的效果是最差的，證明了所有的算法都是有效的.

圖5 HAaB算法與其他算法結(jié)果對(duì)比圖(高相似度組)

圖6 HAaB算法與其他算法結(jié)果對(duì)比圖(低相似度組)

圖7 HAaB算法與其他算法結(jié)果對(duì)比圖(隨機(jī)相似度組)

此外，對(duì)于高相似度組來說，HAaB算法和Average Aggregation算法在組規(guī)模大于3的時(shí)候推薦精度基本處于穩(wěn)定狀態(tài)；在其他的所有情況下，大部分算法的效果都會(huì)隨著組規(guī)模的增大而降低.對(duì)于大部分算法來說，高相似度組的推薦效果是最好的，其次是隨機(jī)組，而低相似度組的推薦效果是最差的.這說明組內(nèi)相似度越高，組推薦算法的推薦效果就越好.

5 小結(jié)

筆者分析了當(dāng)前典型的基于列表融合的組推薦算法的缺陷，并提出了HAaB算法融合了Average Aggregation算法和Borda算法的思想，同時(shí)考慮了組員推薦列表中項(xiàng)目評(píng)分和項(xiàng)目排名兩個(gè)因素，摒棄了這兩種算法的缺陷.通過實(shí)驗(yàn)發(fā)現(xiàn)，HAaB算法比Average Aggregation算法和Borda等算法效果要好很多；此外，組內(nèi)相似度越高，組推薦的效果就越好.一般情況下，組推薦的效果還隨著組規(guī)模的增加而降低，但是在少數(shù)情況下也有例外.

HAaB算法的關(guān)鍵是在每種情況下使用最優(yōu)的λ值來進(jìn)行推薦，因此未來的工作比較重要的一點(diǎn)就是解決如何設(shè)計(jì)算法自適應(yīng)得到每種情況下的最優(yōu)λ值.此外，組員推薦列表的融合策略可以做進(jìn)一步的優(yōu)化，可以將融合策略考慮的因素更加細(xì)化.同時(shí)，將來也可以在多個(gè)數(shù)據(jù)集上對(duì)HAaB算法做進(jìn)一步的優(yōu)化和驗(yàn)證.