基于社區結構的推薦系統中冷啟動問題研究

曹珂崯 張天舒 孫娟 彭二帥

摘? 要：由于推薦系統中數據稀疏性和冷啟動問題日益嚴重，傳統的算法無法有效地解決這些問題，現有的改進算法由于穩定性差，仍然需要預先確定具體的參數。文章提出了一種基于社區結構的冷啟動算法以改善推薦系統中的冷啟動問題，通過計算用戶和項目節點的相似度投影二分網絡，利用改進的Louvain算法對投影單模式網絡進行社區檢測，使新記錄更新到社區，然后進行對用戶社區組推薦。與其他冷啟動算法相比，該算法在推薦準確率和運行效率有明顯提升。

關鍵詞：社區檢測；冷啟動；二分投影網絡；推薦系統

中圖分類號：TP301.6；TP391? ? 文獻標識碼：A? ? 文章編號：2096-4706（2023）01-0030-04

Research on Cold Start Problem in Recommendation System Based on Community Structure

CAO Keyin， ZHANG Tianshu， SUN Juan， PENG Ershuai

（Department of Computer and Communication， Jiangsu Vocational College of Electronics and Information， Huaian? 223001， China）

Abstract： Due to the increasingly serious problems of data sparsity and cold start in recommendation systems， traditional algorithms cannot effectively solve these problems， and the existing improved algorithms still need to pre-determine specific parameters due to their poor stability. In this paper， a cold-start algorithm based on community structure is proposed to improve the cold-start problem in recommendation systems. By calculating the similarity bipartite projection network between users and project nodes， the improved Louvain algorithm is used to detect the community for the projected single-mode network. It updates the new record to the community and then makes recommendations to the user community groups. Compared with other cold-start algorithms， the algorithm has a significant improvement in recommendation accuracy and operating efficiency.

Keywords： community detection; cold start; bipartite projection network; recommendation system

0? 引? 言

推薦系統已廣泛用于線音樂流媒體服務（例如Spotify、網易云音樂、QQ音樂、Apple Music）。推薦系統是簡化用戶決策的工具，通過挖掘用戶行為數據以幫助用戶瀏覽大量音樂[1]。隨著越來越多信息的出現，數據稀疏性問題或新記錄不足帶來的冷啟動挑戰越來越嚴重。如果用戶歷史行為記錄不足，或者歌曲缺少訪問記錄，推薦結果將不準確，甚至影響推薦其他歌曲的機會，從而產生負面反饋，這稱為冷啟動問題。

針對推薦系統中的冷啟動問題，研究人員進行了相關的研究。Funk將SVD應用到推薦系統中，將用戶與項目都投影到矩陣中，顯式地表示用戶對物品興趣數據[2]。一些研究發現，來自社區的用戶資料可以提高推薦系統的效率[3-5]。Shi提出了一種基于局部代表的矩陣分解方法，可以使用決策樹創建相同興趣的用戶組，通過兩輪劃分為用戶劃定用戶組從而實現組推薦[6]。周超提出了一種分別從用戶和項目兩個方向通過計算Pearson-Jaccard相關系數進行聚類[7]，從兩個方向降低了數據稀疏性的影響。

通過對上述算法總結，結合現實生活中用戶具有社區結構，本文提出了基于社區結構的冷啟動推薦算法。該算法通過將用戶與歌曲行為信息視為二分網絡，計算余弦相似系數投影到兩個單模網絡，利用Louvain算法獲得相似用戶和歌曲的社區分組，并且能夠根據新到達的數據逐步更新新記錄的社區，從而對于整個社區組進行推薦，緩解了推薦系統中的冷啟動問題。

1? 基于社區檢測的冷啟動算法

在本節中，首先對二分網絡進行投影操作，根據用戶對音樂的行為對用戶/音樂社區進行劃分，音樂偏好相似的用戶被劃分到同一個社區。然后，將新紀錄合并到已有社區，原有的用戶或項目可能因為新紀錄到來，偏好發生改變而更新社區。最后，對于用戶社區組生成音樂推薦的結果。算法框架如圖1所示。

1.1? 二分網絡社區檢測

為了初始化推薦系統二分圖的社區，首先對用戶和歌曲進行單模投影，以減少劃分社區所耗費的時間。使用余弦相似公式，以計算用戶偏好相似矩陣，并設置最小相似度閾值，以突出相似度。

同理，也可計算歌曲之間相似度矩陣Wi。如式（1）所示，其中? 和? 表示用戶u1和u2評價集合， 表示用戶u1對歌曲i的評分， 表示用戶u1對所有歌曲評分平均值。

（1）

其次，對單模投影網絡進行社區劃分。在網絡中，更大的模塊度意味著社區結構較強，用戶興趣更相似。Louvain算法[8]是一種基于模塊度的圖聚合類快速社區檢測算法，算法將孤立的用戶或歌曲節點一個個地加入獲得最大的社區中，直至模塊度不再增加。

通常對于二分投影網絡大多方法采用在兩個單模網絡上直接使用Louvain算法，本文利用先前工作[9，10]中進行剪枝操作以減少算法耗費的時間，同時針對二分投影網絡模塊度進行相關改進。進行社區劃分時通過將二分網絡節點之間建立二分鄰接矩陣，重新連接單模用戶網絡與項目網絡，以此保留原始二分網絡中的一些社區結構，將原公式修改如式（2）所示：

（2）

其中，QP表示二分投影網絡模塊度， 社區c內部鄰接矩陣， 這里Bi，j表示二分鄰接矩陣，。令? 表示社區c內部邊的權重， 表示社區c內和連接社區c的所有邊的權重。

由于投影時單模網絡的節點之間的連接是由原始圖中的共享鄰居引起的，在投影為單模網絡之后，一些結構會丟失。通過改寫二分投影網絡的模塊度計算方式，計算模塊度時重新連接原始的二分圖，因此包含原始二分網絡中的一些信息。將節點n加入社區c中獲得的投影模塊度增量ΔQP如式（3）所示：

（3）

1.2? 二分投影網絡更新

當新紀錄進入推薦系統時，首先重新計算投影相似性網絡中相關用戶的相似度，根據相似性矩陣更新用戶相似網絡[9]。接下來，對于新增記錄可以分為兩種類型：

（1）新記錄節點已經存在于某個社區中。更新過程中將其視為老用戶，在這種情況下根據先前的工作在計算模塊度時刪除某些邊緣節點，削減社區劃分時的運算時間，使用投影Louvain算法實現局部模塊度最大，為用戶找到最合適的社區，如果用戶的社區發生變化，則代表用戶對音樂偏好的遷移[10]。

（2）新記錄節點沒有社區信息。分別計算新紀錄用戶節點鄰居節點社區邊的權重，選取鄰居社區中權重最大的社區將新節點更新到社區，以節省算法運算時間。計算新節點加入社區的ΔQP，如果ΔQP小于閾值，則對整個用戶相似網絡使用投影Louvain算法，重新劃分網絡中的社區。

1.3? 個性化推薦

為了實現冷啟動音樂推薦，首先定義用戶偏好，本文根據用戶對音樂的偏好，而不是使用顯式評分信息來尋找相似的用戶和音樂。

整個推薦過程，首先根據Pearson相關系數，將二分網絡投影到用戶與歌曲的單模網絡中。利用投影Louvain算法對兩個單模網絡進行社區檢測。其次，在新紀錄到來后對社區進行更新，在這個過程中僅有一小部分用戶和歌曲項目改變了社區。最后，將偏好信息嵌入到ALS算法中來更新社區集群因子，避免對整個模型重新訓練。在算法1中介紹了更新過程：

算法1.Community cold-start

輸入： Newrecord

輸出： Music recommendation results

1. Cu： User communities; Cu： Musiccommunities

2. p，q is potential factor and s，g is community factor

3.Function Update New Record

4.? ?Using Projection Louvain Algorithm Update Cu and Ci

5.? ?Initialize l=1，diff =999

6.? ?while diff＞l do

7.? ? for u in Cu do

8.? ? ? ? ?Calculate

9.? ? ?end for

10.? ? for i in Ci do

11. Calculate

12.end for

13.? ? ?diff =

14.l=l+1

15.end while

16. results=ALS（p，q，s，g，Cu，Ci）

17. Return results

18.end Function

2? 實驗和討論

在本節中，將通過一系列實驗來演示算法的性能。將基于社區檢測的冷啟動算法（Community cold-start）與傳統的SVD組推薦算法[11]以及一種考慮用戶和項目之間的協作關系改進的在雙向網絡中聚類的方法Bipartite-cluster[12]和進行了比較，驗證了該算法的有效性。實驗使用三個現實世界的大規模數據集評估所有的模型，第一個是Million Song，第二個數據集是Yahoo Music，除此之外還使用了電影評分數據集MovieLens數據集，采用均值絕對誤差（MAE）和準確度（Precision）用于衡量預測等級與真實等級的接近程度。為了消除隨機性的影響，所有實驗均在相同的條件下進行，實驗重復10次取平均值。

2.1? 評價指標

音樂推薦系統的主要目的是預測用戶的基本興趣和偏好，并向用戶推薦合適的項目，以便從數量越來越多的音樂中找到喜歡的歌曲。有很多指標可以衡量推薦系統的各個方面。這里使用兩種流行的度量標準，均值絕對誤差（MAE）和準確度（Precision）用于衡量預測等級與真實等級的接近程度。對MAE和Precision定義如式（4）和式（5）所示：

（4）

（5）

其中，

2.2? 實驗結果

在3個真實用戶評價數據集中分別計算MAE。對于投影網絡中較小的群組，將它們分組為一個特殊的社區。數據前80%用于訓練，后20%用于驗證推薦準確性。通過對不同數據集的MAE計算，得到如表1所示的結果。

從表1中可以看出，在3個相關數據集中計算用戶預測評價與真實評價的數據，在評價數據較多的較密集的MovieLens和Million Song數據集Community cold-start算法較好，Bipartite-cluster算法次之，SVD算法最差。在評價數目較少的和Yahoo Music數據集中Community cold-start和Bipartite-cluster算法性能差別不大，但是都要比SVD性能更強。

為了驗證推薦歌曲的性能，本文還在Yahoo Music數據集對準確度（Precision）和運行時間進行測試，在測試集中隨機選擇5名用戶，分別進行Top5、Top10、Top15、Top20推薦，對每組準確度求平均后獲得推薦準確度，預測評分誤差小于0.5時按照預測與實際評分相等處理。圖2顯示了三種算法在不同推薦項目數的準確度，推薦歌曲的數目設置為[5，10，15，20]。

當設置推薦音樂個數為5時，Community cold-start算法推薦準確度為44%比其他兩種算法分別高2%和4%左右，隨著推薦歌曲的數目逐漸增多，三種算法推薦歌曲的準確度都在下降，但是基于社區的冷啟動算法趨于穩定保持了較高的準確度。

在圖3中第一批數據到達音樂推薦系統時，由于要對二分網絡進行相似度計算及投影操作，因此基于社區檢測的冷啟動算法消耗時間比其他兩種算法耗時長。隨著新紀錄越來越多，基于社區檢測的冷啟動算法只需要更新社區中的小部分，Bipartite-cluster算法需要重新對用戶和歌曲項目進行聚類，SVD算法每次都需要進行大規模矩陣運算，因此SVD算法消耗的時間成倍增加，在整個過程基于社區檢測的冷啟動算法消耗時間較少。根據以上內容可以得出以下結論：對于評價數據密集的數據集三種算法的MAE得分相似，對于數據稀疏和遇到新用戶/項目時基于社區檢測的冷啟動算法具有比其他方法更高的準確性，并且運行時間較短。

3? 結? 論

本文針對音樂推薦系統中的冷啟動問題提出了討論與分析，提出了一種基于社區結構的改善音樂推薦系統中的冷啟動方法，首先將輸入用戶與音樂二分網絡進行投影，降低后續復雜度，然后使用改進的投影Louvain算法得到用戶和項目兩個單模網絡社區劃分結果。新紀錄到來時通過更新一部分網絡來完成對新紀錄的推薦，通過3個真實的用戶評價數據集驗證了方法的有效性。

本文雖在一定程度緩解新記錄遇到的冷啟動問題，但是實際生活中用戶可能對不同流派音樂的感興趣，而本文僅將用戶劃分到單一社區，未來將探索重疊社區劃分算法解決冷啟動相關問題，滿足用戶同時喜歡不同分類音樂的需求。同時本文面對大規模數據進行推薦時耗時較長，需要使用并行計算對推薦過程進行加速。下一步將把以上兩點作為研究方向。

參考文獻：

[1] 于鵬華.數據數量與質量敏感的推薦系統若干問題研究 [D].杭州：浙江大學，2016.

[2] FUNK S. Netflix update：try this at home [EB/OL].（2006-12-11）.http：//sifter.org/simon/journal/20061211.html.

[3] 朱傳亮.基于社交關系和社區結構的協同過濾推薦算法研究 [D].重慶：重慶郵電大學，2019.

[4] 張凱涵，梁吉業，趙興旺，等.一種基于社區專家信息的協同過濾推薦算法 [J].計算機研究與發展，2018，55（5）：968-976.

[5] 張川.基于內容和用戶行為的個性化微博推薦算法研究與實現 [D].北京：北京郵電大學，2018.

[6] SHI L ，ZHAO W X ，SHEN Y D. Local Representative-Based Matrix Factorization for Cold-Start Recommendation [J].Acm Transactions on Information Systems，2017，36（2）：1-28.

[7] 周超，孫英華，熊化峰，等.基于用戶和項目雙向聚類的協同過濾推薦算法 [J].青島大學學報：自然科學版，2018，31（1）：55-60.

[8] BLONDEL V D，GUILLAUME J，LAMBIOTTE R，et al.Fast unfolding of communities in large networks [J].Journal of Statistical Mechanics：Theory and Experiment，2008（10）：1-12.

[9] 陳東明，嚴燕斌，黃新宇，等.基于二分網絡社團劃分的推薦算法 [J].東北大學學報：自然科學版，2018，39（8）：1103-1107.

[10] 夏瑋，楊鶴標.改進的Louvain算法及其在推薦領域的研究 [J].信息技術，2017（11）：125-128.

[11] BI X，QU A，WANG J，et al. A Group-Specific Recommender System [J].Journal of the American Statal Association，2017，112（519）：1344-1353.

[12] 王金.基于SVD++的協同過濾群組推薦算法研究 [D].金華：浙江師范大學，2018.

作者簡介：曹珂崯（1994—），男，漢族，山東鄄城人，助教，碩士，研究方向：網絡安全、人工智能。

收稿日期：2022-08-09