基于多源信息聚類和IRC-RBM的混合推薦算法*

何登平，張為易，黃 浩

(1.重慶郵電大學通信與信息工程學院，重慶 400065; 2.重慶郵電大學通信新技術應用研究中心，重慶400065;3.重慶信科設計有限公司，重慶 401121)

1 引言

隨著移動通信技術的飛速發(fā)展，數(shù)據(jù)規(guī)模呈指數(shù)級增長，用戶往往難以從海量數(shù)據(jù)中定位到自己滿意的信息[1]。如何解決“信息過載”問題[2]，為用戶提供滿意的信息，已經(jīng)成為了互聯(lián)網(wǎng)公司亟待攻克的難題。推薦系統(tǒng)是建立在對大規(guī)模數(shù)據(jù)挖掘的基礎上的一種智能預測系統(tǒng)，能大大緩解上述問題[3]。推薦系統(tǒng)以其簡單、魯棒性強的特點成為人們輔助決策不可或缺的工具[4]，其中最重要的推薦技術之一就是協(xié)同過濾[5]。協(xié)同過濾是目前最流行的推薦算法，但也面臨著一些挑戰(zhàn)，其中一個重要的挑戰(zhàn)是處理高度稀疏的數(shù)據(jù)集。

為了解決上述問題，學者們提出了許多方法緩解數(shù)據(jù)稀疏性。例如文獻[6,7]提出了用矩陣降維和奇異值分解來緩解數(shù)據(jù)稀疏性問題，但是存在數(shù)據(jù)量過大導致模型推薦效率降低的問題。文獻[8]提出了一種基于受限玻爾茲曼機RBM(Restricted Boltzmann Machine)的協(xié)同過濾推薦算法[8],對高維度稀疏的評分矩陣建模，通過模型自動降維處理緩解數(shù)據(jù)稀疏性問題，實驗結果表明該算法的推薦精度遠高于奇異值分解算法的，但存在模型訓練時間過長的問題。文獻[9]提出一種對比散度的訓練方法[9]，緩解了RBM模型訓練時間過長的問題。但是，RBM模型也存在沒有考慮到用戶差異的問題。此外，一些學者通過將外部信息導入到協(xié)同過濾模型中來提高推薦精度。例如，文獻[10]利用用戶的職業(yè)信息和文獻[11]利用用戶之間的相似度。近些年，混合推薦算法綜合2種或2種以上的算法的優(yōu)點，實現(xiàn)了技術互補[12]，漸漸成為了學者們研究的熱點之一。學者Schafer等在文獻[13]中列出了一些常用的組合思路，如加權、變換、混合、折疊等，隨機組合不同的推薦算法。

針對上述問題，本文對聚類模型和RBM模型進行改進融合，提出了一種基于項目實值受限玻爾茲曼機和多源信息最小生成樹K-means聚類的混合推薦算法IRC-RBM-MST(a hybrid recommendation algorithm based on Items of Real-valued Conditional Restricted Boltzmann Machine and Multi-source minimum Spanning Tree K-means information clustering)，主要思想是利用基于項目實值受限玻爾茲曼機的協(xié)同過濾模型IRC-RBM提取用戶特征，然后用多源信息聚類得到用戶類別，最后通過線性加權的方式綜合2種算法的預測結果，進而為用戶生成Top-N推薦。本文貢獻如下：

(1)改進了傳統(tǒng)的K-means算法，提出了一種結合多源信息最小生成樹K-means聚類算法MST-K-means(Multi-source minimum Spanning Tree K-means)。首先改進了傳統(tǒng)的用戶相似度計算公式，通過加入用戶的信任度和項目的時間權重來重新定義用戶的相似度。然后通過用戶之間的相似度關系重構出1個無向圖，通過最小生成樹算法，生成初始聚類簇，克服了K-means隨機選取初始簇類中心問題。

(2)改進了RBM模型，提出了IRC-RBM。本文改進了RBM的可見層單元，讓可見層單元可以用實值表示，降低了模型的復雜度。同時，提出了一種加入沖量因子的對比散度算法，使模型迭代的速度更快，增強模型抗過擬合效果。

(3)將IRC-RBM和MST-K-means通過線性加權的方式融合，通過對真實數(shù)據(jù)集進行離線實驗，驗證了IRC-RBM-MST混合算法的有效性。

2 多源聚類算法

2.1 改進的相似度計算公式

因為K-means算法只利用稀疏的評分矩陣計算相似度，得到的聚類效果往往不理想。因此，本文通過融合用戶之間信任關系和項目的時間權重定義了一種新的相似性度量方法，然后基于這種新的混合度量方法對用戶進行聚類。

計算用戶屬性相似度是最小生成樹模型的基礎，也是K-means算法的第1步。用戶屬性相似度反映的是2個用戶屬性之間的距離，值越大則2個用戶屬性距離越遠，反之則2個用戶屬性距離越近。經(jīng)典的聚類算法通常使用歐氏距離來考慮用戶之間的相似性，如式(1)所示：

(1)

其中，du,e表示用戶u和用戶e的歐氏距離，ru,i表示用戶u對項目i的評分，re,i表示用戶e對項目i的評分,Iu,e表示用戶u和用戶e共同評分過的項目集合。

信任度是1個抽象的概念，在不同的應用場景，其定義的標準也不盡相同。在推薦系統(tǒng)中，如果2個用戶對同一個項目都進行了評分，表示兩者具有一定的信任度，如式(2)所示：

(2)

其中，I(u)和I(e)分別表示用戶u和用戶e所有評過分的項目集合；Tu,e表示兩者信任度，數(shù)值越大說明兩者興趣越相似，信任度也越高。

除此之外還要考慮用戶興趣的變化，用戶的興趣隨時間的推移可能會出現(xiàn)偏移，當為用戶做推薦時要考慮用戶當前最感興趣的物品。項目的時間權重如式(3)所示：

(3)

其中，tu,i表示用戶u對項目i的評分的時間戳。

本文綜合考慮了用戶之間的信任度和項目的時間權重，經(jīng)過改進后的用戶相似度計算公式如式(4)所示：

(4)

2.2 MST-K-means聚類算法

因為在K-means中最初的聚類簇中心是隨機選定的，導致聚類的效果不理想。為了提高聚類的質量，本文提出了MST-K-means算法：其核心思想是以用戶之間的相似度關系構建1個無向圖，通過最小生成樹算法找出K個互不連通的子圖；然后用K個子圖的均值作為K-means算法的聚類中心，避免了隨機聚類導致算法的效率降低。最小生成樹聚類算法的核心是用戶之間相似度計算的方式，本文通過式(4)計算的相似度更能描述用戶之間的相似性。通過實驗驗證，改進相似度后的MST-K-means算法的效果明顯優(yōu)于K-means算法的。MST-K-means算法如算法1所示。

算法1MST-K-means

輸入：原始數(shù)據(jù)集，聚類個數(shù)K。

輸出：K個聚類簇。

步驟1計算用戶的初始聚類中心。

初始化：以用戶作為節(jié)點的集合V,以用戶之間的相似度(根據(jù)式(4)計算)作為邊的權重，構成邊集合E;Vnew={x}，其中x為集合V中的任1節(jié)點(起始點)，Enew={}。

重復下列操作，直到Vnew=V：

(1)在集合E中選取權值最小的邊〈u,e〉，其中u∈Vnew，e?Vnew，并且e∈V；

(2)將V加入集合Vnew，將邊〈u,e〉加入集合Enew。

使用集合Vnew和Enew來描述所得到的最小生成樹。刪除最小生成樹中權值最大的K-1條邊，得到K個互不連通的子圖。

在數(shù)據(jù)集中用K個子圖的均值作為K-means算法的聚類中心，構造初始的聚類簇。

步驟2(1)根據(jù)式(4)計算用戶與每個聚類中心的距離；

(2)將每個用戶都劃分到距離最近的聚類簇中；

3 IRC-RBM推薦模型

RBM是具有2層結構的隨機生成模型，可見層表示數(shù)據(jù)，隱藏層提取特征。文獻[14]把實值條件引入了RBM模型，簡化了傳統(tǒng)RBM模型。文獻[15]證明了在大數(shù)據(jù)集上，基于項目的RBM模型推薦效果遠遠優(yōu)于基于用戶的RBM模型的。

本文通過借鑒文獻[14,15]的思想，提出了IRC-RBM模型,其結構如圖1所示。IRC-RBM的結構類似于二部圖，其中v是可見層，表示用戶對項目的評分(如果用戶沒有對該項目評分，就用0表示)；ai表示可見層單元的偏置；h表示隱藏層，用來提取項目之間的隱藏特征；bj表示隱藏層單元偏置；Wij表示可見層與隱藏層的連接權重。

Figure 1 IRC-RBM model圖1 IRC-RBM模型

因為可見層用實值表示評分數(shù)據(jù)，所以在傳統(tǒng)的RBM能量模型基礎上，增加了可見層實值的能量函數(shù)，此時IRC-RBM的能量計算如式(5)所示:

(5)

其中，θ={W,a,b}指RBM模型的參數(shù)集合，可見層神經(jīng)元數(shù)量用n表示，隱藏層神經(jīng)元數(shù)量為m。v為可見層，vi為可見層單元。

因為IRC-RBM模型具有層內無連接和層間全連接的特殊結構，使其隱單元的激活概率相互獨立。當把評分數(shù)據(jù)輸入模型以后，可以根據(jù)能量公式計算隱藏層單元的激活概率，如式(6)所示：

(6)

給定隱藏層單元的狀態(tài)時，第i個可見層單元的值為：

(7)

傳統(tǒng)的對比散度算法存在迭代次數(shù)過多和容易產(chǎn)生局部最優(yōu)解的問題，本文提出了增加沖量因子的方法來解決上述問題。即在進行權值更新時，加入上1次更新的權重，可以使權重更新方法更趨近模型迭代的方向，減少RBM迭代次數(shù)和提高模型抗過擬合的能力。參數(shù)更新如式(8)所示：

ΔWij=ε(〈vihj〉data-〈vihj〉model)+βΔWij(n-1),

Δai=ε(〈vi〉data-〈vi〉model)+βΔai(n-1),

Δbi=ε(〈hj〉data-〈hj〉model)+βΔbj(n-1)

(8)

其中，ε表示學習率;β是沖量項;〈vihj〉data表示可見層已知時隱藏層的期望;〈vihj〉model表示重構后模型的期望。

4 混合推薦系統(tǒng)

4.1 MST-K-means聚類算法評分預測

設目標用戶為u，評分項目集合為Nu，F(xiàn)u為u未評過分的項目集合。對項目i(i∈Nu)來說，首先找到該項目所屬類簇Ci，用戶u對類簇中已評分項目的集合記為Ia={i1,i2,…,ip}，則計算用戶u對目標項目i的評分公式如式(9)所示：

(9)

其中，dij為目標項目i與項目j的相似度，ru,j為用戶u對項目j的評分。

經(jīng)過上述處理，用戶-項目評分數(shù)據(jù)庫中的大多數(shù)項目都有1個評分值，即用戶u對任一項目i的評分可表示為：

本文采用的多源信息融合聚類評分預測算法具體步驟如下所示：(1)根據(jù)項目的多源信息，用改進后的相似度公式計算項目屬性的相似度；(2)對項目用MST-K-means算法進行聚類,生成K個用戶聚類簇;(3)對于用戶評分缺失的項目，計算相同用戶簇類其他被該用戶評分的項目的評分平均值，以此來表示缺失項目的評分。

4.2 IRC-RBM模型評分預測

IRC-RBM模型評分預測的過程如下所示：

(1)輸入用戶u和項目i；

(2)將用戶u的所有評分作為RBM的Softmax單元的輸入；

(3)根據(jù)式(6)計算所有隱藏層單元的激活概率；

(4)根據(jù)式(7)為項目i計算每1個評分k(k=1,…,K)所對應的激活概率；

4.3 混合推薦

設R1∈Rm×n為MST-K-means聚類算法評分預測后的評分矩陣,R2∈Rm×n為IRC-RBM模型得到的評分預測矩陣，則經(jīng)過線性組合之后的評分預測矩陣C,如式(10)所示：

(10)

其中,λ是加權參數(shù)，0≤λ≤1。λ的取值根據(jù)實驗經(jīng)驗和交叉驗證的方法獲得。

5 實驗分析

5.1 數(shù)據(jù)集及評價指標

本文在評估推薦算法性能指標時所采用的數(shù)據(jù)集是目前眾多研究者所使用的MovieLens數(shù)據(jù)集。數(shù)據(jù)集包括：用戶ID、項目ID、評級信息、時間戳(來自Unix秒制時間)，如表1所示。該數(shù)據(jù)集包含943位會員用戶對推薦系統(tǒng)中1 682部影片的評級，并且每個會員用戶至少評價了20部電影，共約有100 000條電影的評級信息，評級的數(shù)值為1～5的整數(shù)。將數(shù)據(jù)集中的評分矩陣按4∶1分為2個部分，前者為訓練集，作為數(shù)據(jù)輸入，設計推薦模型；后者為測試集，對推薦模型進行性能評估。

Table 1 MovieLens dataset表1 MovieLens數(shù)據(jù)集

為了衡量本文算法的效果，本次實驗采用平均絕對誤差MAE(Mean Absolute Error)作為評價標準，其計算方法如式(11)所示，評價指標MAE的值越小，表示預測值的誤差越小。

(11)

5.2 不同參數(shù)對推薦準確度的影響

5.2.1 確定隱藏層單元

本實驗將建立IRC-RBM模型對測試集進行預測，以探究IRC-RBM中隱藏層單元對評分預測的影響，從而確定最佳隱藏層單元的數(shù)量。根據(jù)多次實驗結果，在IRC-RBM模型中，隱藏層單元數(shù)量為100時，效果最好。實驗結果如圖2所示。

Figure 2 Influence of implicit layer unit on the IRC-RBM model圖2 隱藏層單元的數(shù)量對IRC-RBM模型的影響

從圖2中可知，隨著隱藏層單元數(shù)目的增加，IRC-RBM模型的MAE值呈現(xiàn)出先降后增的趨勢，在隱藏層單元數(shù)量取值100時，取得最優(yōu)推薦效果。在隱藏層單元數(shù)量大于100時，推薦效果下降，這是因為作為特征提取單元的隱藏層單元數(shù)量過大而產(chǎn)生了過擬合現(xiàn)象。故本文實驗IRC-RBM 模型中的隱藏層單元個數(shù)將固定為100。

5.2.2 確定用戶簇數(shù)K

首先，在用戶聚類過程中要確定用戶聚類數(shù)目K。本實驗在取不同K值的情況下，觀察MAE值的變化，得到最適合的聚類數(shù)目K。實驗結果如圖3所示。

Figure 3 Influence of user clustering number on IRC-RBM-MST model圖3 用戶聚類數(shù)對IRC-RBM-MST模型的影響

從圖3可以看出，起始階段隨著K值的增加，MAE值呈現(xiàn)減小的趨勢，在K值等于100時MAE達到最小，之后又快速增加。其可能原因為，如果用戶聚類數(shù)量過少，會導致用戶過度集中，影響推薦效果；如果用戶聚類數(shù)量過多，會使用戶十分分散，不能充分利用相似用戶之間的關系，也會導致推薦精度下降。所以，在下面的實驗中選擇用戶聚類個數(shù)為100。

5.2.3 相關算法對比實驗

本實驗的實驗參數(shù)設置：迭代次數(shù)為100、用戶聚類個數(shù)為100。將本文所提出的IRC-RBM-MST混合推薦算法與其它融合算法進行對比實驗。實驗結果如圖4所示。

Figure 4 MAE comparison of related algorithms圖4 相關算法MAE對比

從圖4可以看出，MST-K-means算法相比傳統(tǒng)K-means算法在推薦精度上有明顯的提高?；旌贤扑]算法的推薦精度遠高于單一推薦算法的，說明將2種算法相結合的混合推薦算法，可以互相彌補各自的不足；IRC-RBM-MST混合推薦算法也遠遠優(yōu)于傳統(tǒng)K-means和RBM混合推薦算法K-means-RBM(a hybrid recommendation algorithm based on K-means clustering and Restricted Boltzmann Machine)，說明本文提出的新相似度計算方式和在模型訓練中加入沖量因子，大大緩解了數(shù)據(jù)稀疏性的問題，提高了推薦精度。

5.3 算法結果分析

為了進一步驗證算法的有效性，將本文算法與最新提出的2種混合推薦算法進行對比。2種對比算法分別是文獻[16]中提出的基于C均值聚類和受限玻爾茲曼機的混合推薦算法(CFC-RBM)和文獻[17]中提出的基于用戶聚類和支持向量機的混合推薦算法(IC-SVD)。實驗結果如圖5所示。

Figure 5 MAE comparison among IRC-RBM-MST, CFC-RBM and IC-SVD圖5 與CFC-RBM和IC-SVD的MAE對比

從圖5中可以看出，隨著迭代次數(shù)增加，3種算法都出現(xiàn)了過擬合的現(xiàn)象。其中CFC-RBM算法過擬合程度最嚴重，IRC-RBM-MST其次，IC-SVD基本保持平穩(wěn)，波動較小。這是因為RBM模型隨著迭代次數(shù)增加會出現(xiàn)過擬合的現(xiàn)象，我們可以通過融合其他模型來緩解RBM模型的過擬合。相比于文獻[15]的CFC-RBM，本文所提的IRC-RBM-MST通過與多源信息聚類算法進行加權，緩解了這種過擬合現(xiàn)象?？梢钥闯?，本文所提的IRC-RBM-MST推薦精度最高，CFC-RBM其次，IC-SVD最低。通過以上分析可知，本文提出的IRC-RBM-MST算法具有推薦精度高和抗過擬合等優(yōu)點。

6 結束語

本文提出了一種混合推薦算法，將聚類和受限玻爾茲曼機2種模型結合在一起，通過加入用戶的信任度和項目的時間權重解決了無法量化用戶相似度計算的問題；通過最小生成樹解決隨機選取聚類中心導致聚類效果不理想的問題。另外，也通過基于用戶實值的受限玻爾茲曼機模型，簡化了傳統(tǒng)的受限玻爾茲曼機模型，提升了模型推薦效果。最后，基于聚類的推薦算法隨著用戶增加，推薦精度不斷下降，而受限玻爾茲曼機隨著用戶增加，往往不能考慮用戶個性化的特點，本文通過線性加權的方式，使2種模型進行互補。通過實驗表明，本文所提的混合推薦算法具有較高的精度和抗過擬合能力。但是，本文算法還是不能解決冷啟動問題，如何解決新用戶的推薦問題，將是下一步工作的要點。另外，下一步工作中將會繼續(xù)調整平衡因子、K近鄰的取值等參數(shù)來優(yōu)化算法。相比于傳統(tǒng)的機器學習算法，本文算法因使用到RBM深度學習模型，單機運行效率比較低。為了提高效率，將在接下來的實驗中將嘗試利用Hadoop、Spark等分布式平臺。