長尾群組推薦的免疫多目標優化實現

韓亞敏， 柴爭義,2,， 李亞倫， 朱思峰

(1. 天津工業大學 計算機科學與軟件學院，天津 300387； 2. 諾丁漢大學(英國) 計算機學院，諾丁漢 NG8 1BB; 3. 周口師范學院 數學與統計學院，河南 周口 466001)

推薦系統作為解決信息過載的有效方式，在電子購物、新聞閱讀、互聯網廣告等眾多領域得到了廣泛應用[1]．傳統推薦算法針對單個用戶的設計，無法滿足現實中的某些需要，比如聚餐、看電影、旅行等一系列行為通常是以群組的形式發生的，群組推薦將推薦對象由單一用戶擴展到多個用戶，需要滿足多個用戶的偏好并對其進行融合．眾多學者對其關鍵問題進行研究．文獻[2]研究了認知與社交模型下的群組推薦; 文獻[3]基于投票聚合策略與元學習技術，探索群組協作搜索、選擇、評價、推薦的方法; 文獻[4]利用社區網絡結構發現群組，提出一種基于社交網絡社區的組推薦框架; 文獻[5]采用矩陣分解技術對小、中、大型3種群組進行推薦; 文獻[6]對組推薦的研究現狀進行了總結和展望．

總之，已有的群組推薦主要集中在如何滿足用戶偏好，提高推薦的準確度，對推薦的多樣性和新穎性方面關注較少[6]．眾多研究表明，長尾物品同樣重要，有利于提高推薦結果的多樣性和新穎性[7-8]．因此，筆者將長尾物品引入群組推薦，考慮準確度和“長尾”的矛盾性，將其建模為多目標問題，采用免疫優化進行求解．算法旨在滿足群組對推薦列表滿意度的基礎上，提高推薦物品的長尾覆蓋率，發揮長尾效益．實驗結果表明了算法的有效性．

1 推薦問題建模

1.1 推薦的長尾問題

傳統的推薦算法為滿足用戶的偏好，主要考慮提高推薦的準確度，傾向于推薦一些流行的物品[6]．而事實上假使沒有推薦系統，用戶也很容易通過其他途徑獲取這些流行度較高的物品，系統價值意義不大．因此，很多研究者致力于長尾，也就是不流行物品的推薦[7-8]．很顯然，如果僅推薦不流行的物品，將導致準確度很低，對推薦系統來說，同樣是沒有意義的．一個好的推薦系統應該權衡兩者，得到一個較好的均衡解．

另一方面，很多互聯網數據研究表明，用戶行為符合長尾分布[8]．用戶經常購買或訪問的物品主要集中在長尾的頭部，即比較流行的物品．而長尾理論表明，尾部物品的總體效益同樣不容小覷．對用戶來說，不流行而恰好所需的物品，無疑可以提高用戶的驚喜度，讓用戶獲得更加多樣與新穎的選擇，增加用戶與推薦系統的粘合度;而對物品提供商來說，長尾推薦可以提高潛在的收益，對推薦系統的實際應用存在非常重要的價值．因此，在群組推薦中，考慮長尾物品有著理論和實際意義．

1.2 多目標長尾群組推薦建模

推薦問題通常被描述為一個定義在用戶空間和物品空間上的效用函數．推薦系統的目的就是把特定的物品推薦給用戶，使效用函數最大化[9]．

定義函數F(G，i)表示群組G對物品i的效用函數，top-N群組推薦問題為:給定群組G，找到效用函數最大的物品集合R，并滿足約束條件R=N．其中N為最終推薦列表的長度．表示如下:

(1)

傳統群組推薦主要滿足群組中用戶的偏好，提高推薦結果的準確度．考慮到推薦的長尾問題，筆者將其建模成多目標問題，一方面保證群組推薦的準確性；另一方面降低推薦結果的流行度，挖掘長尾物品．

設用戶u和物品i的相似度記為S(u，i)，則群組中用戶對推薦結果的滿意度定義為

(2)

函數f1計算了群組對推薦列表的平均相似度以衡量推薦的滿意度．相似度越高，代表物品越符合用戶的偏好．其中，采用余弦相似度計算，公式如下:

(3)

由于長尾物品很少被評分，而流行的物品會受到廣泛評價．通常的作法是基于評分數量來判定流行度．但是依靠評分數量對很多評分相同的物品并不合適．最恰當的辦法是利用物品評分的均值與方差[10]．設物品i的流行度定義為

mi=1μi(σi+1)2,(4)

其中，μi和σi分別代表物品i的評分均值和方差．物品越流行，m值越小．整個推薦列表中物品的流行度為

(5)

為了挖掘更多的長尾物品，函數f2越大越好．同時，為了提高組用戶的滿意度，也要求函數f1越大越好．顯然，這兩個目標是相互制約的，推薦流行度高的物品可以提高推薦的準確性和用戶滿意度，但會降低整個推薦列表的物品流行度，反之亦然．因此，這是一個典型的多目標優化問題．所以，長尾群組推薦的多目標問題可設置為

maxf1(R)，f2(R) ．(6)

2 長尾群組推薦的免疫多目標優化實現

2.1 算法描述

圖1 長尾群組推薦算法流程

2.2 群組數據預處理

群組推薦的數據來源一般包括組成員行為歷史、瀏覽記錄、用戶-項目評分等[6，11]．文中將用戶集、物品集、用戶-項目評分矩陣作為群組數據來源．表示如下:

(1)U={u1，u2，…，um}，m個用戶的集合;

(2)I={i1，i2，…，in}，n個物品的集合;

(3)D={du，i|u∈U，i∈I}，用戶對物品的評分數據．

在D中，du，i=0，表示用戶u尚未對物品i進行打分．實際中，評分矩陣相當稀疏．矩陣分解的推薦方法能夠有效緩解評分數據稀疏問題[12]．文中選用的是矩陣分解的一個代表，即奇異值分解，其可以表示為

D=XΣYT=XΣ1/2(YΣ1/2)T,(7)

其中，X，Y是正交矩陣，Σ是對角矩陣．在很多情況下，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上了．故通常用前k個奇異值來近似描述矩陣．SVD如下所示:

(8)

由此得到用戶特征矩陣M和物品特征矩陣N，即

其中，k是特征空間的維度．矩陣M和N的每一行分別代表對應用戶和物品的特征向量．

2.3 群組發現與偏好融合

文中根據用戶的偏好動態發現群組．算法隨機產生一組用戶作為待推薦群組，計算用戶之間的相似度;根據用戶之間的相似度關系，發現該組用戶的代表群組．具體的群組發現過程如算法1所描述．其中，δ為相似度的門限值．

算法1 群組發現．

輸入: 隨機輸入k個用戶的集合U

輸出:G群組

1. for useri，jfromU&&j≠ido

2.SU[i][j]←cos(U[i]，U[j]);

3. end for

4.G←U;

5. for userifromUdo

6. if ?jfromU&&j≠i，SU[i][j]<δthen

7. G←G-i;

8 end if

9. end for

10. returnG．

群組發現后，重要的一步就是如何對不同用戶的偏好進行融合．融合策略有公平策略、均值策略、痛苦避免策略、最小痛苦策略、最開心策略等不同方法[6]．文中采用最常用的均值策略進行偏好融合．首先通過用戶和物品的特征相似性計算評估該用戶對物品的喜愛程度，獲取用戶的物品偏好序列．取每個用戶最喜愛的前r個物品，組成臨時物品集．根據不同物品出現的頻率對物品集劃分階級，依次加入候選集，直到候選集達到r個; 最后加入的階級根據均值融合策略作截斷處理．具體如算法2所示．

算法2 群組偏好融合．

輸入: 群組G，用戶特征矩陣M，物品特征矩陣N，候選集大小r

輸出: 群組推薦的候選集RC

1.IS←?;

2. for userifromGdo

3. for itemjfromIdo

4.SI[i][j]←S(M[i]，N[j]);

5. end for

6.Z←Sort(SI[i]，descend);

7.IS←IS∪Z[1:r];

8. end for

9.k←1，RC←?;

10. whileIS≠?

11.F{k}←findCommon(IS); /*返回IS的最頻繁子集，并從IS中移除該子集*/

12.RC←RC∪F{k};

13. ifRC>rthen

14.RC←RC-F{i}; break;

15. end if

16.k++;

17. end while

18.IC←sort(F{k}，descend);

19.i←1;

20. whileRC

21.RC←RC∪IC[i];

22.i++;

23. end while

24. returnRC．

2.4 多目標免疫優化推薦

免疫智能作為一種仿生學算法，在解決多目標優化問題上取得了很好的效果[13-14]．文中對上面生成的組推薦列表，考慮物品的長尾效應，進一步使用免疫算法進行優化，得到用戶滿意度和物品流行度均衡的推薦結果．

2.4.1 編 碼

抗體代表群組推薦中的候選解．每一個候選解都是候選集RC的子集．不同于文獻[15]，筆者采用實數編碼，更易于理解和執行后面的免疫操作．每一個抗體以向量的形式表示一個推薦列表，表示為

X={x1，x2，…，xL} ,(11)

其中，L為推薦列表的長度，滿足X=L．每一個xi是RC中的一個元素，并且元素各不相同，保證同一物品在同一推薦列表中不能被推薦2次．迭代中的一組推薦列表形成抗體種群．

2.4.2 親和力度量

親和力是抗體的適應性度量，文中長尾群組推薦的多目標是max{f1(R)，f2(R)}，所以親和力的度量就是計算max{f1(R)，f2(R)}．

2.4.3 交 叉

傳統的單點交叉會造成X中的元素重復．對此，文中作了如下變化，如圖2所示．x1，x2在6th處單點交叉產生y1，y2．造成y1中3th和9th元素相同，y2中5th和7th元素相同．然后，隨機從候選集中選擇其他元素進行替換，保證候選解中元素彼此不同．

圖2 交叉算子圖3 變異算子

2.4.4 變 異

變異算子采用單點變異，從候選集中挑選一個不屬于X的元素隨機替換xi，形成新的X．如圖3所示，概率選擇3th元素進行單點變異．

綜上，多目標免疫優化具體步驟如下:

(1) 初始化生成NM個抗體，即種群P0，設t=0．

(2) 計算種群Pt的抗體親和力．根據帕累托占優，找出其中的占優抗體，記作占優種群Dt．如果Dt≤NM，則Dt+1=Dt；否則，按擁擠距離排序，前NM個抗體組成Dt+1．具體擁擠距離計算詳見文獻[13]．

(3) 如果t≥Gmax，算法結束，輸出Dt+1；否則，t=t+1，執行步驟4．

(4) 如果Dt≤NA，則活動種群At+1=Dt；否則，按擁擠距離排序，前NA個抗體組成At．

(5) 按比例克隆At，組成大小為NC的克隆種群Ct．

3 實驗評估

3.1 數據集與參數設置

群組推薦要求測試數據集包含群組信息，目前在組推薦領域還沒有標準的測試集[6]．組推薦通常利用傳統數據集構建群組或隨機生成群組進行實驗評價．文中利用經典數據集MovieLens對隨機群組作實驗．數據集MovieLens是來自 6 040 個用戶對 3 952 部電影的 1 000 209 條評分，且所有的評分都是[1，5]之間的整數．實驗中，將數據集分成2份，80%作為訓練集，20%作為測試集．參數設置及其含義如表1所示．

表1 參數設置

3.2 評價指標

3.2.1 準 確 度

準確度是推薦系統的一個重要指標[16]，用來衡量推薦列表中與目標用戶相關的物品占比．可表示為

P(R)=R∩TR,(12)

其中，R是系統的推薦列表，T是測試數據集中與用戶相關的物品集合．如果用戶對某個物品的評分大于等于3，則認為該物品與此用戶相關．以群組內用戶準確度的均值作為群組的準確度．P(R)值越大，則代表推薦結果的準確度越高．

3.2.2 多 樣 性

多樣性衡量推薦列表中物品之間的差異性[17]．文中使用Jaccard相似系數計算兩個項目之間的類型相似度，然后通過計算整個推薦列表之間的相似度來評價推薦結果的多樣性．假設A和B代表兩個物品，則Jaccard相似系數可以如下表示．值越大，相似度越高．

J(A，B)=A∩BA∪B．(13)

則推薦列表R的多樣性可以表示為

(14)

其中，J(Ri，Rj)代表物品Ri和Rj之間的類型相似度．

3.2.3 新 穎 性

新穎性是對推薦列表不流行程度的一個評價指標，衡量系統挖掘長尾物品的能力[8，16]．其公式為

(15)

其中，pi代表推薦列表中第i個物品的度，是對該物品有評分行為的用戶個數．新穎性的值越低，越傾向于推薦不流行的物品，即推薦的物品越處于長尾曲線的尾部．

圖4 群組[151，198，2 276，4 921，5 515]的帕累托前沿

3.3 實驗結果

文中隨機產生大小為2、5、10、20、40的群組，對其進行實驗．如圖4所示為群組[151，198，2 276，4 921，5 515] 迭代得到的帕累托前沿．橫縱坐標分別為衡量組內用戶對推薦物品的滿意度和推薦列表中物品的流行度．圖中的每個點代表一個推薦列表，實驗參數NM設置為20，即得到20個推薦列表．從圖4可以看出，在一次的迭代過程中，算法產生不同滿意度與流行度權重的多個推薦結果．其中，a點(0.129，926.75)，x值最小，y值最大，表示點a滿意度最低，但物品更處于長尾的尾部; 反之，b點(0.234，101.88)，x值最大，y值最小，表示點b滿意度最高，但物品更偏向于長尾頭部．

算法對2、5、10、20、40等不同組大小的群組推薦結果以準確度、多樣性和新穎性進行評價．在一次迭代中，算法為群組產生多個推薦列表，其中，表2以群組[151，198，2 276，4 921，5 515] 的一組推薦列表為例，展示了各成員與群組整體的準確度、多樣性、新穎性情況．對于群組中少數用戶如 5 515 準確度為0，但大多數用戶準確度為 0.2～ 0.3，群組整體的準確度達到0.2．多樣性值為0.104，代表物品之間的不相似性高達0.896左右，推薦列表的多樣性較好．另外列表的新穎性為241.34，意味著推薦物品在數據集 6 040 個用戶基數下平均只有4%的用戶對其進行過評價，驗證了算法對長尾物品的挖掘能力．

表2 群組準確度、多樣性與新穎性情況

圖5 不同群組大小的指標對比

文中對考慮長尾物品和不考慮長尾物品的情況作了對比，實驗結果如圖5所示．結果表明，算法在群組大小為2、5、10、40時，準確度高于非長尾群組推薦，證明長尾群組推薦有效保持了推薦準確度．其中，群組大小為2時，準確度最高；隨著成員的增多，準確度有所下降．這是因為成員越多，不同的偏好越難滿足，因此，在理論上是合理的．從圖5(b)和圖5(c)可以看出，算法在組大小為2時，多樣性和新穎性優勢不明顯，但群組大小為5、10、20、40時，多樣性與新穎性優于非長尾群組推薦，驗證了算法的有效性．

由于群組推薦中，動態生成的群組，成員是動態的，因此，無法與其他算法進行有效比較．與已有的組推薦研究類似，文中僅驗證了算法的可行性，相關研究還需進一步探討．

4 結 束 語

筆者將考慮長尾效應的群組推薦建模成一個多目標問題，并利用免疫優化算法進行求解，旨在同時優化推薦結果的準確性與推薦物品的流行度．實驗結果表明，算法在滿足群組滿意度的情況下，能提高物品的多樣性和新穎性，增加其長尾覆蓋率．但是算法在群組較大時，準確度還不是太好，有待以后繼續研究．

[1] LACERDA A. Multi-objective Ranked Bandits for Recommender Systems[J]. Neurocomputing, 2017, 246: 12-24.

[2] QUIJANO-SANCHEZ L, DIAZ-AGUDO B, RECIO-GARCIA J A. Development of a Group Recommender Application in a Social Network[J]. Knowledge-Based Systems, 2014, 71: 72-85.

[3] ZAPATA A, MENENDEZ V H, PRIETO M E, et al. Evaluation and Selection of Group Recommendation Strategies for Collaborative Searching of Learning Objects[J]. International Journal of Human-Computer Studies, 2015, 76: 22-39.

[4] 劉宇, 吳斌, 曾雪琳, 等. 一種基于社交網絡社區的組推薦框架[J]. 電子與信息學報, 2016, 38(9): 2150-2157.

LIU Yu, WU Bin, ZENG Xuelin, et al. A Group Recommendation Framework Based on Social Network Community[J]. Journal of Electronics & Information Technology, 2016, 38(9): 2150-2157.

[5] ORTEGA F, HERNANDO A, BOBADILLA J, et al. RecommendingItems to Group of Users Using Matrix Factorization Based Collaborative Filtering[J]. Information Sciences, 2016, 345: 313-324.

[6] 張玉潔, 杜雨露, 孟祥武. 組推薦系統及其應用研究[J]. 計算機學報, 2016, 39(4): 745-764.

ZHANG Yujie, DU Yulu, MENG Xiangwu. Reserch on Group Recommender Systerms and Their Applications[J]. Chinese Journal of Computers, 2016, 39(4): 745-764.

[7] VALCARCE D, PARAPAR J, BARREIRO A. Item-basedRelevance Modelling of Recommendations for Getting Rid of Long Tail Products[J]. Knowledge-Based Systems, 2016, 103: 41-51.

[8] WANG S F, GONG M G, LI H L, et al. Multi-objective Optimization for Long Tail Recommendation[J]. Knowledge-Based Systems, 2016, 104: 145-155.

[9] QUIJANO-SANCHEZ L, SAUER C, RECIO-GARCIA J A, et al. MakeIt Personal: a Social Explanation System Applied to Group Recommendations[J]. Expert Systems with Applications, 2017, 76: 36-48.

[10] PARK Y J. The Adaptive Clustering Method for the Long Tail Problem of Recommender Systems[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(8): 1904-1915.

[11] FENG S S, CAO J. Improving Group Recommendations via Detecting Comprehensive Correlative Information[J]. Multimedia Tools and Applications, 2017, 76(1): 1355-1377.

[12] FANG Y N, GUO Y F. A Context-aware Matrix Factorization Recommender Algorithm[C]//Proceedings of the 2013 IEEE International Conference on Software Engineering and Service Science. Washington: IEEE Computer Society, 2013: 914-918.

[13] 雷雨, 焦李成, 公茂果, 等. 求解多目標考試時間表問題的NNIA改進算法[J]. 西安電子科技大學學報, 2016, 43(2): 157-161.

LEI Yu, JIAO Licheng, GONG Maoguo, et al. Enhanced NNIA forMulti-objective Examination Timetabling Problems[J]. Journal of Xidian University, 2016, 43(2): 157-161.

[14] CHAI Z Y, YAN X Y, LI Y L, et al. Throughput Optimization in Cognitive Wireless Network Based on Clone Selection Algorithm[J]. Computer and Electronic Engineering, 2016, 52: 328-336.

[15] GENG B R, LI L L, JIAO L C, et al. NNIA-RS: a Multi-objective Optimization Based Recommender System[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 424: 383-397.

[16] ZUO Y, GONG M G, ZENG J L, et al. Personalized Recommendation Based on Evolutionary Multi-objective Optimization[J]. IEEE Computational Intelligence Magazine, 2015, 10(1): 52-62.

[17] KUNAVER M, POZRL T. Diversity in Recommender Systems—a Survey[J]. Knowledge-Based Systems, 2017, 123: 154-162.