基于社區(qū)結(jié)構(gòu)的推薦系統(tǒng)中冷啟動(dòng)問(wèn)題研究

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

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

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

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

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

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

1? 基于社區(qū)檢測(cè)的冷啟動(dòng)算法

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

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

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

同理，也可計(jì)算歌曲之間相似度矩陣Wi。如式（1）所示，其中? 和? 表示用戶(hù)u1和u2評(píng)價(jià)集合， 表示用戶(hù)u1對(duì)歌曲i的評(píng)分， 表示用戶(hù)u1對(duì)所有歌曲評(píng)分平均值。

（1）

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

通常對(duì)于二分投影網(wǎng)絡(luò)大多方法采用在兩個(gè)單模網(wǎng)絡(luò)上直接使用Louvain算法，本文利用先前工作[9，10]中進(jìn)行剪枝操作以減少算法耗費(fèi)的時(shí)間，同時(shí)針對(duì)二分投影網(wǎng)絡(luò)模塊度進(jìn)行相關(guān)改進(jìn)。進(jìn)行社區(qū)劃分時(shí)通過(guò)將二分網(wǎng)絡(luò)節(jié)點(diǎn)之間建立二分鄰接矩陣，重新連接單模用戶(hù)網(wǎng)絡(luò)與項(xiàng)目網(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)重。

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

（3）

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

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

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

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

1.3? 個(gè)性化推薦

為了實(shí)現(xiàn)冷啟動(dòng)音樂(lè)推薦，首先定義用戶(hù)偏好，本文根據(jù)用戶(hù)對(duì)音樂(lè)的偏好，而不是使用顯式評(píng)分信息來(lái)尋找相似的用戶(hù)和音樂(lè)。

整個(gè)推薦過(guò)程，首先根據(jù)Pearson相關(guān)系數(shù)，將二分網(wǎng)絡(luò)投影到用戶(hù)與歌曲的單模網(wǎng)絡(luò)中。利用投影Louvain算法對(duì)兩個(gè)單模網(wǎng)絡(luò)進(jìn)行社區(qū)檢測(cè)。其次，在新紀(jì)錄到來(lái)后對(duì)社區(qū)進(jìn)行更新，在這個(gè)過(guò)程中僅有一小部分用戶(hù)和歌曲項(xiàng)目改變了社區(qū)。最后，將偏好信息嵌入到ALS算法中來(lái)更新社區(qū)集群因子，避免對(duì)整個(gè)模型重新訓(xùn)練。在算法1中介紹了更新過(guò)程：

算法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? 實(shí)驗(yàn)和討論

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

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

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

（4）

（5）

其中，

2.2? 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

3? 結(jié)? 論

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

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

參考文獻(xiàn)：

[1] 于鵬華.數(shù)據(jù)數(shù)量與質(zhì)量敏感的推薦系統(tǒng)若干問(wèn)題研究 [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é)同過(guò)濾推薦算法研究 [D].重慶：重慶郵電大學(xué)，2019.

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

[5] 張川.基于內(nèi)容和用戶(hù)行為的個(gè)性化微博推薦算法研究與實(shí)現(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] 周超，孫英華，熊化峰，等.基于用戶(hù)和項(xiàng)目雙向聚類(lèi)的協(xié)同過(guò)濾推薦算法 [J].青島大學(xué)學(xué)報(bào)：自然科學(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é)報(bào)：自然科學(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é)同過(guò)濾群組推薦算法研究 [D].金華：浙江師范大學(xué)，2018.

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

收稿日期：2022-08-09