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

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

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

中圖分類號：TP301.6；TP391? ? 文獻(xiàn)標(biāo)識碼：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)已廣泛用于線音樂流媒體服務(wù)（例如Spotify、網(wǎng)易云音樂、QQ音樂、Apple Music）。推薦系統(tǒng)是簡化用戶決策的工具，通過挖掘用戶行為數(shù)據(jù)以幫助用戶瀏覽大量音樂[1]。隨著越來越多信息的出現(xiàn)，數(shù)據(jù)稀疏性問題或新記錄不足帶來的冷啟動挑戰(zhàn)越來越嚴(yán)重。如果用戶歷史行為記錄不足，或者歌曲缺少訪問記錄，推薦結(jié)果將不準(zhǔn)確，甚至影響推薦其他歌曲的機(jī)會，從而產(chǎn)生負(fù)面反饋，這稱為冷啟動問題。

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

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

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

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

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

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

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

（1）

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

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

（2）

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

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

（3）

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

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

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

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

1.3? 個性化推薦

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

整個推薦過程，首先根據(jù)Pearson相關(guān)系數(shù)，將二分網(wǎng)絡(luò)投影到用戶與歌曲的單模網(wǎng)絡(luò)中。利用投影Louvain算法對兩個單模網(wǎng)絡(luò)進(jìn)行社區(qū)檢測。其次，在新紀(jì)錄到來后對社區(qū)進(jìn)行更新，在這個過程中僅有一小部分用戶和歌曲項目改變了社區(qū)。最后，將偏好信息嵌入到ALS算法中來更新社區(qū)集群因子，避免對整個模型重新訓(xùn)練。在算法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é)作關(guān)系改進(jìn)的在雙向網(wǎng)絡(luò)中聚類的方法Bipartite-cluster[12]和進(jìn)行了比較，驗證了該算法的有效性。實驗使用三個現(xiàn)實世界的大規(guī)模數(shù)據(jù)集評估所有的模型，第一個是Million Song，第二個數(shù)據(jù)集是Yahoo Music，除此之外還使用了電影評分?jǐn)?shù)據(jù)集MovieLens數(shù)據(jù)集，采用均值絕對誤差（MAE）和準(zhǔn)確度（Precision）用于衡量預(yù)測等級與真實等級的接近程度。為了消除隨機(jī)性的影響，所有實驗均在相同的條件下進(jìn)行，實驗重復(fù)10次取平均值。

2.1? 評價指標(biāo)

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

（4）

（5）

其中，

2.2? 實驗結(jié)果

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

從表1中可以看出，在3個相關(guān)數(shù)據(jù)集中計算用戶預(yù)測評價與真實評價的數(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性能更強(qiáng)。

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

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

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

3? 結(jié)? 論

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

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

參考文獻(xiàn)：

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

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

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

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

[5] 張川.基于內(nèi)容和用戶行為的個性化微博推薦算法研究與實現(xiàn) [D].北京：北京郵電大學(xué)，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].青島大學(xué)學(xué)報：自然科學(xué)版，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] 陳東明，嚴(yán)燕斌，黃新宇，等.基于二分網(wǎng)絡(luò)社團(tuán)劃分的推薦算法 [J].東北大學(xué)學(xué)報：自然科學(xué)版，2018，39（8）：1103-1107.

[10] 夏瑋，楊鶴標(biāo).改進(jìn)的Louvain算法及其在推薦領(lǐng)域的研究 [J].信息技術(shù)，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].金華：浙江師范大學(xué)，2018.

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

收稿日期：2022-08-09