一種基于隨機(jī)游走的歌曲推薦算法

吳雪君，米紅娟，李 欣

(蘭州財經(jīng)大學(xué) 信息工程學(xué)院，甘肅 蘭州 730020)

0 引言

互聯(lián)網(wǎng)的快速發(fā)展使得用戶在面對呈指數(shù)級增長的信息量時很難挖掘出有用的資源。推薦算法的出現(xiàn)在一定程度上為用戶緩解了這個難題。推薦算法主要通過歷史數(shù)據(jù)中用戶對項目的行為操作，利用相應(yīng)算法計算相似度，為用戶推薦他可能感興趣的項目?，F(xiàn)在已經(jīng)有許多實際的應(yīng)用，如Netflix的電影推薦，亞馬遜網(wǎng)站的圖書、CD推薦等。

常見的主流音樂推薦算法可以分為三種：基于內(nèi)容的推薦算法、協(xié)同過濾推薦算法、混合推薦算法。基于內(nèi)容的推薦算法[1]易于實現(xiàn)，它只需要用戶個人的歷史數(shù)據(jù)，分析用戶曾經(jīng)喜歡過的歌曲的屬性信息，計算所用歌曲間的相似度，為用戶推薦相似的未收聽過的歌曲。但是推薦結(jié)果缺乏多樣性，且特征提取的方法受到技術(shù)的限制。協(xié)同過濾推薦算法[2-3]是根據(jù)歷史數(shù)據(jù)中用戶對歌曲的評分(評分?jǐn)?shù)據(jù)可以是用戶對項目的各種操作)，計算相似度，發(fā)現(xiàn)偏好相同的用戶，根據(jù)相似用戶的偏好預(yù)測目標(biāo)用戶對其他歌曲的喜好程度，不足之處是存在冷啟動問題和數(shù)據(jù)稀疏性問題?；旌贤扑]算法將上述兩種算法互補(bǔ)組合進(jìn)行推薦，比如Stanford大學(xué)推出的Fab系統(tǒng)，將兩種算法結(jié)合為用戶提供個性化推薦[4]。

有學(xué)者也提出了新的推薦算法，例如基于圖結(jié)構(gòu)進(jìn)行推薦。傳統(tǒng)的隨機(jī)游走(Random Walk，RW)[5]是一種理想的數(shù)學(xué)模型，它從所處的節(jié)點出發(fā)，以相同的幾率游走到其某一個鄰居節(jié)點，可以將它假設(shè)成馬爾科夫鏈。隨著研究的發(fā)展，隨機(jī)游走模型也被應(yīng)用在推薦系統(tǒng)中，實現(xiàn)對用戶的個性化推薦。YILDIRIM H等人[6]提出了一種基于隨機(jī)游走模型的面向項目的協(xié)同過濾推薦算法，使用項目間的余弦相似度和修正的余弦相似度來初始化狀態(tài)轉(zhuǎn)移概率，該模型能在稀疏數(shù)據(jù)下增強(qiáng)相似性矩陣。ZHANG L等人[7]提出了一種基于分類隨機(jī)游走的推薦算法，引入了分類等級分?jǐn)?shù)，針對用戶對不同類別的偏好進(jìn)行推薦。對于冷啟動問題，SHANG S等人[8]利用社交信息來解決缺少用戶評分信息時的冷啟動問題，通過構(gòu)建用戶-項目有向圖，結(jié)合項目內(nèi)容和社交信息為用戶進(jìn)行推薦。

近年來，場論在其他學(xué)科中的應(yīng)用越來越廣泛，已有學(xué)者提出經(jīng)濟(jì)場、物流場等概念與理論。費孝通[9]提出“場”是一個研究多學(xué)科的綜合平臺，可以給其他學(xué)科的研究提供新的理論依據(jù)與研究視角。湯銀英[10]在物流場的基礎(chǔ)上，建立了物流場理論體系，研究了物流場的各種特性，構(gòu)造了發(fā)展動力場模型，為物流企業(yè)的發(fā)展提供策略。

本文提出一種基于隨機(jī)游走的音樂推薦算法，首先根據(jù)歌曲的基本信息和用戶的收聽數(shù)據(jù)，計算歌曲間的綜合相似度，降低評分矩陣的稀疏性，構(gòu)建歌曲相關(guān)圖，再結(jié)合物理場論中的場力公式，將歌曲看作相互作用的節(jié)點，結(jié)合音樂的重要度，確定隨機(jī)游走模型中的轉(zhuǎn)移概率矩陣，降低隨機(jī)游走的時間復(fù)雜度，提高歌曲推薦的準(zhǔn)確性。

1 推薦算法相關(guān)理論

1.1 隨機(jī)游走模型

隨機(jī)游走由一系列隨機(jī)的軌跡組成，在推薦系統(tǒng)中，對于m個用戶和n個項目，模型中用戶游走到當(dāng)前節(jié)點的概率由前一步P(Xu,d+1=j|Xu,d=i)決定，Xu,d=i表示用戶u隨機(jī)游走d步后在項目i處的隨機(jī)變量[6]。

Pij=P(Xu,d+1=j|Xu,d=i)

(1)

其中，Pij∈P，P為m×n的轉(zhuǎn)移概率矩陣。

(2)

定義用戶u在節(jié)點j的總概率如式(3)所示。

(3)

1.2 場論模型

場是物質(zhì)存在的基本形式，相互作用存在于場之間，如溫度場、電場、磁場等。在場中，某物質(zhì)對其他物質(zhì)產(chǎn)生的影響可以用作用力表示。在萬有引力場中，任意兩質(zhì)點間的引力由式(4)計算。

(4)

場力的統(tǒng)一公式如式(5)所示。

(5)

其中，K是常數(shù)，M表示物質(zhì)的特性(包括式(4)中的M1與M2，式(5)中的Ma與Mb)，比如質(zhì)量、重要性等，r是兩種物質(zhì)之間的“距離”。

2 基于隨機(jī)游走的歌曲推薦算法

2.1 構(gòu)造歌曲相關(guān)圖

2.1.1 歌曲評分相似度

設(shè)用戶集U={u1,u2,...,ua，...,um}，歌曲集I={i1,i2,...,ij,...,in}，根據(jù)數(shù)據(jù)集中用戶的行為操作，構(gòu)造二部圖G=，如圖1所示，其中V由用戶頂點集U和歌曲頂點集I組成，E表示用戶頂點和歌曲頂點之間相連的邊。如果用戶ua收聽過歌曲ij，那么就在ua和ij之間建立一條邊。

圖1 二部圖示例

基于協(xié)同過濾的歌曲推薦算法通過分析歷史數(shù)據(jù)集中用戶對歌曲的評分來獲得項目或用戶間的關(guān)系。對于m個用戶和n個項目，用戶對項目進(jìn)行自己的操作，比如購買、分享、刪除等，這些行為操作表示了用戶對項目一定的喜惡程度，是一種隱式評分。在如式(6)所示的用戶-項目評分矩陣R中，raj表示第a個用戶對第j個項目的評分值。傳統(tǒng)的協(xié)同過濾推薦算法通過評分矩陣計算相似度，得到具有相似偏好的用戶或項目進(jìn)行推薦。本文使用的數(shù)據(jù)集中用戶的歷史操作是以收聽歌曲的次數(shù)計數(shù)，所以以用戶收聽某首歌曲的次數(shù)來作為用戶對項目的評分。

(6)

歌曲ix和歌曲iy的評分相似度計算的基本思想是，找出既收聽過歌曲ix，也收聽過歌曲iy的所有用戶Uix，iy，然后計算相似度Simix,iy。計算歌曲相似度的方法有很多，如皮爾遜相關(guān)系數(shù)、余弦相似度、修正的余弦相似度[11]等。

經(jīng)過對現(xiàn)有語料的分析，用戶收聽某首歌曲的次數(shù)變化范圍在1～7 939之間，用戶一般不會再次收聽不喜歡的歌曲，但是會不斷循環(huán)收聽喜歡的歌曲。根據(jù)數(shù)據(jù)集中用戶收聽歌曲的歷史行為，生成User-Item矩陣。為消除用戶收聽歌曲存在的次數(shù)差異，通過式(7)對數(shù)據(jù)做最大值最小值歸一化。

(7)

其中，Max(Rua)表示第a行元素中的最大值，即用戶ua收聽單首歌曲的最大次數(shù)，Rua,ix表示用戶Ua收聽歌曲ix的次數(shù)。

本文選取改進(jìn)的余弦相似度方法計算歌曲評分相似度，如式(8)所示。

Sim1(ix,iy)=

(8)

2.1.2 歌曲基本信息相似度

根據(jù)數(shù)據(jù)集中音樂的固有信息，例如曲風(fēng)、演唱者、發(fā)行年份等，計算歌曲基本信息相似度。

①曲風(fēng)屬性可以作為標(biāo)簽屬性，其取值為搖滾、金屬、說唱等，屬性間的相似度用式(9)計算。

(9)

其中，S1(ix,iy)表示歌曲ix與iy之間的曲風(fēng)相似度，K表示兩首歌曲共有的標(biāo)簽數(shù)，N表示該屬性所有的標(biāo)簽數(shù)。

②發(fā)行年份屬性，對年份進(jìn)行分段處理，比如10年作一次劃分，年份從1922年～2011年，則1922年記為1，1931年記為2，2011年記為10，劃分后用式(10)計算兩首歌曲之間的發(fā)行年份相似度。

S2(ix,iy)=e-|Tix-Tiy|

(10)

其中，S2(ix,iy)表示歌曲ix與iy的發(fā)行年份相似度，Tix、Tiy分別表示歌曲ix和iy的發(fā)行年份所處的分段值。

③演唱者屬性，將演唱者屬性看作二元屬性，即兩首歌曲的演唱者相同記為1，不同記為0，用Sim3(ix,iy)表示歌曲ix和iy的演唱者相似度。

歌曲ix和iy的基本信息相似度通過Sg(ix,iy)(g=1,2,3)的加權(quán)求和得到，如式(11)所示。

(11)

其中，w1表示曲風(fēng)屬性占的權(quán)重，w2表示發(fā)行年份屬性占的權(quán)重，w3表示演唱者屬性占的權(quán)重。

2.1.3 歌曲相關(guān)圖

由歌曲評分相似度Sim1(ix,iy)和歌曲基本信息相似度Sim2(ix,iy)加權(quán)求和計算歌曲綜合相似度Sim(ix,iy)，如式(12)所示。

Sim(ix,iy)=αSim1(ix,iy)+βSim2(ix,iy)

(12)

其中，參數(shù)α、β分別表示歌曲評分相似度和歌曲基本信息相似度所占的權(quán)重。

2.2 改進(jìn)的隨機(jī)游走推薦模型

傳統(tǒng)的隨機(jī)游走算法在時間復(fù)雜度上有明顯的缺點，因為在為每個用戶進(jìn)行推薦時，都需要在整個用戶-項目二部圖上進(jìn)行迭代，直到每個項目被選擇的概率值收斂，這一過程的時間復(fù)雜度非常高。改進(jìn)后的隨機(jī)游走算法通過構(gòu)建轉(zhuǎn)移概率矩陣，大大降低了算法的時間復(fù)雜度。

由歌曲綜合相似度，得出對應(yīng)的相似度矩陣M1。運用式(5)，計算作用力矩陣Mforce。其中距離r用歌曲節(jié)點間的綜合相似度Sim(ix,iy)來計算，如式(13)所示。兩首歌曲越相似，Sim(ix,iy)越大，r就越小，表示歌曲間的“距離”越近。

(13)

式(5)中的物質(zhì)特性M采用歌曲的重要性，即歌曲的度來衡量，歌曲的度為用戶-歌曲二部圖中歌曲頂點連接的路徑數(shù)，也就是收聽過這首歌曲的用戶數(shù)，根據(jù)用戶-歌曲二部圖得到每首歌曲的度outix。由于每一項都有常系數(shù)K，通常K取1，得到歌曲間的場力如式(14)所示。

(14)

綜上，得到作用力矩陣Mforce，其中Mforce(ix,iy)=Fix→iy，Mforce(ix,ix)=0。

對Mforce進(jìn)行歸一化計算，得到轉(zhuǎn)移概率矩陣Mtran，其中Mtran(ix,iy)如式(15)所示。

(15)

通過Mtran計算出各節(jié)點對應(yīng)歌曲的最終推薦值N，如式(16)所示，將推薦值N按從小到大排序，得到推薦結(jié)果。

由N=(1-λ)N0+λNMtran得[12]：

N=(1-λ)(1-λMtran)-1N0

(16)

其中，N是所有節(jié)點的推薦值向量;N0是一個n×1的列向量，表示目標(biāo)用戶的收聽記錄，N0(ix)=1，表示該歌曲被目標(biāo)用戶收聽過；N0(ix)=0，表示該歌曲未被目標(biāo)用戶收聽過，參數(shù)λ表示權(quán)重。

3 推薦算法實驗及結(jié)果分析

3.1 數(shù)據(jù)集

公開數(shù)據(jù)集Million Song Dataset(MSD)包含了一百萬首歌曲的特征分析和元數(shù)據(jù)。其他幾個互聯(lián)網(wǎng)音樂社區(qū)貢獻(xiàn)了相關(guān)互補(bǔ)數(shù)據(jù)集，例如The musiXmatch Dataset提供了歌曲的歌詞數(shù)據(jù)。The Last.fm Dataset提供了歌曲信息、藝術(shù)家信息等。Kaggle曾經(jīng)舉辦過The Million Song Dataset Challenge，利用了一百萬用戶的播放記錄數(shù)據(jù)。

本文使用到的數(shù)據(jù)是MSD的子集The Echo Nest提供的可以與MSD關(guān)聯(lián)的user-song-play count數(shù)據(jù)集。數(shù)據(jù)集有元數(shù)據(jù)和評分?jǐn)?shù)據(jù)，其中元數(shù)據(jù)包括歌曲的曲風(fēng)、演唱者、發(fā)行年份，評分?jǐn)?shù)據(jù)是用戶收聽歌曲的次數(shù)。

3.2 實驗與結(jié)果分析

實驗中訓(xùn)練集為100萬用戶的收聽歌曲的記錄，Kaggle比賽提供了額外的11萬用戶對38萬多首歌曲的收聽記錄，驗證集為其中1萬用戶的收聽記錄，測試集為剩余10萬用戶的收聽記錄，測試集中一半的收聽數(shù)據(jù)可見。

根據(jù)歌曲元數(shù)據(jù)計算歌曲基本信息相似度時，對于歌曲的基本信息，曲風(fēng)、年代、演唱者三者之間存在一定的聯(lián)系，例如某一演唱者屬于某一年代，他的歌曲一般在這一年代較流行，也具有該年代的主流曲風(fēng)。本文實驗中曲風(fēng)、年代、演唱者所占自的權(quán)重均為1/3。

經(jīng)過實驗證明，計算歌曲綜合相似度時，歌曲評分相似度Sim1(ix,iy)和歌曲基本信息相似度Sim2(ix,iy)的權(quán)重為α=0.4，β=0.6時實驗效果最佳。計算歌曲最終的推薦值N時，參數(shù)λ取經(jīng)驗值0.85。

本文采用Kaggle比賽中使用的平均精度均值(Mean Average Precision,MAP)作為評價指標(biāo)，評價歌曲推薦方法的準(zhǔn)確性，其公式如下：

(17)

其中：MAP@500表示給第a個用戶推薦Top500的音樂的平均準(zhǔn)確率，U表示所有的用戶數(shù)量。

Kaggle比賽第一名Aiolli使用基于內(nèi)存的協(xié)同過濾進(jìn)行推薦，以該實驗的結(jié)果作為參照進(jìn)行對比，結(jié)果如表1所示。

表1 算法運行時間比較

從表1可見，改進(jìn)的隨機(jī)游走歌曲推薦算法提高了推薦的準(zhǔn)確性，利用歌曲綜合相似度建立歌曲相似度矩陣，降低了相似度矩陣的稀疏度，再由歌曲的重要性結(jié)合場力公式，構(gòu)造轉(zhuǎn)移概率矩陣，基于隨機(jī)游走進(jìn)行推薦，相比于協(xié)同過濾算法，該算法具有更好的推薦準(zhǔn)確性。

4 結(jié)論

本文提出了一種基于隨機(jī)游走的歌曲推薦算法，引入物理學(xué)中的場論理論，解決了隨機(jī)游走算法同等對待節(jié)點的不足，通過計算歌曲綜合相似度，降低了相似度矩陣的稀疏度，將歌曲的重要性和場力公式結(jié)合，構(gòu)造轉(zhuǎn)移概率矩陣，進(jìn)行基于隨機(jī)游走的推薦。實驗證明，該方法比一些傳統(tǒng)的協(xié)同過濾方法具有更好的推薦準(zhǔn)確性。但本文僅利用了歌曲的基本信息和評分?jǐn)?shù)據(jù)，沒有充分利用歌曲的其他重要特征，后期將繼續(xù)研究如何融合歌曲的更多特征，比如音頻特征、歌詞特征等，以提高算法的推薦準(zhǔn)確性。