曹珂崯 張?zhí)焓? 孫娟 彭二帥

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

關鍵詞：社區(qū)檢測；冷啟動；二分投影網(wǎng)絡；推薦系統(tǒng)

中圖分類號：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? 引? 言

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

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

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

1? 基于社區(qū)檢測的冷啟動算法

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

1.1? 二分網(wǎng)絡社區(qū)檢測

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

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

（1）

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

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

（2）

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

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

（3）

1.2? 二分投影網(wǎng)絡更新

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

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

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

1.3? 個性化推薦

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

整個推薦過程，首先根據(jù)Pearson相關系數(shù)，將二分網(wǎng)絡投影到用戶與歌曲的單模網(wǎng)絡中。利用投影Louvain算法對兩個單模網(wǎng)絡進行社區(qū)檢測。其次，在新紀錄到來后對社區(qū)進行更新，在這個過程中僅有一小部分用戶和歌曲項目改變了社區(qū)。最后，將偏好信息嵌入到ALS算法中來更新社區(qū)集群因子，避免對整個模型重新訓練。在算法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? 實驗和討論

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

2.1? 評價指標

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

（4）

（5）

其中，

2.2? 實驗結果

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

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

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

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

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

3? 結? 論

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

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

參考文獻：

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

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

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

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

[5] 張川.基于內容和用戶行為的個性化微博推薦算法研究與實現(xiàn) [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] 周超，孫英華，熊化峰，等.基于用戶和項目雙向聚類的協(xié)同過濾推薦算法 [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] 陳東明，嚴燕斌，黃新宇，等.基于二分網(wǎng)絡社團劃分的推薦算法 [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++的協(xié)同過濾群組推薦算法研究 [D].金華：浙江師范大學，2018.

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

收稿日期：2022-08-09