何登平，張為易，黃 浩

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

1 引言

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

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

針對上述問題，本文對聚類模型和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提取用戶特征，然后用多源信息聚類得到用戶類別，最后通過線性加權(quán)的方式綜合2種算法的預(yù)測結(jié)果，進而為用戶生成Top-N推薦。本文貢獻如下：

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

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

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

2 多源聚類算法

2.1 改進的相似度計算公式

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

計算用戶屬性相似度是最小生成樹模型的基礎(chǔ)，也是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個抽象的概念，在不同的應(yīng)用場景，其定義的標準也不盡相同。在推薦系統(tǒng)中，如果2個用戶對同一個項目都進行了評分，表示兩者具有一定的信任度，如式(2)所示：

(2)

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

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

(3)

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

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

(4)

2.2 MST-K-means聚類算法

因為在K-means中最初的聚類簇中心是隨機選定的，導(dǎo)致聚類的效果不理想。為了提高聚類的質(zhì)量，本文提出了MST-K-means算法：其核心思想是以用戶之間的相似度關(guān)系構(gòu)建1個無向圖，通過最小生成樹算法找出K個互不連通的子圖；然后用K個子圖的均值作為K-means算法的聚類中心，避免了隨機聚類導(dǎo)致算法的效率降低。最小生成樹聚類算法的核心是用戶之間相似度計算的方式，本文通過式(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)計算)作為邊的權(quán)重，構(gòu)成邊集合E;Vnew={x}，其中x為集合V中的任1節(jié)點(起始點)，Enew={}。

重復(fù)下列操作，直到Vnew=V：

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

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

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

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

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

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

3 IRC-RBM推薦模型

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

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

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

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

(5)

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

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

(6)

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

(7)

傳統(tǒng)的對比散度算法存在迭代次數(shù)過多和容易產(chǎn)生局部最優(yōu)解的問題，本文提出了增加沖量因子的方法來解決上述問題。即在進行權(quán)值更新時，加入上1次更新的權(quán)重，可以使權(quán)重更新方法更趨近模型迭代的方向，減少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)

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

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

4.1 MST-K-means聚類算法評分預(yù)測

設(shè)目標用戶為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的評分可表示為：

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

4.2 IRC-RBM模型評分預(yù)測

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

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

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

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

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

4.3 混合推薦

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

(10)

其中,λ是加權(quán)參數(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個部分，前者為訓(xùn)練集，作為數(shù)據(jù)輸入，設(shè)計推薦模型；后者為測試集，對推薦模型進行性能評估。

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

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

(11)

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

5.2.1 確定隱藏層單元

本實驗將建立IRC-RBM模型對測試集進行預(yù)測，以探究IRC-RBM中隱藏層單元對評分預(yù)測的影響，從而確定最佳隱藏層單元的數(shù)量。根據(jù)多次實驗結(jié)果，在IRC-RBM模型中，隱藏層單元數(shù)量為100時，效果最好。實驗結(jié)果如圖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。實驗結(jié)果如圖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ù)量過少，會導(dǎo)致用戶過度集中，影響推薦效果；如果用戶聚類數(shù)量過多，會使用戶十分分散，不能充分利用相似用戶之間的關(guān)系，也會導(dǎo)致推薦精度下降。所以，在下面的實驗中選擇用戶聚類個數(shù)為100。

5.2.3 相關(guān)算法對比實驗

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

Figure 4 MAE comparison of related algorithms圖4 相關(guān)算法MAE對比

從圖4可以看出，MST-K-means算法相比傳統(tǒng)K-means算法在推薦精度上有明顯的提高?；旌贤扑]算法的推薦精度遠高于單一推薦算法的，說明將2種算法相結(jié)合的混合推薦算法，可以互相彌補各自的不足；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)，說明本文提出的新相似度計算方式和在模型訓(xùn)練中加入沖量因子，大大緩解了數(shù)據(jù)稀疏性的問題，提高了推薦精度。

5.3 算法結(jié)果分析

為了進一步驗證算法的有效性，將本文算法與最新提出的2種混合推薦算法進行對比。2種對比算法分別是文獻[16]中提出的基于C均值聚類和受限玻爾茲曼機的混合推薦算法(CFC-RBM)和文獻[17]中提出的基于用戶聚類和支持向量機的混合推薦算法(IC-SVD)。實驗結(jié)果如圖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通過與多源信息聚類算法進行加權(quán)，緩解了這種過擬合現(xiàn)象?？梢钥闯?，本文所提的IRC-RBM-MST推薦精度最高，CFC-RBM其次，IC-SVD最低。通過以上分析可知，本文提出的IRC-RBM-MST算法具有推薦精度高和抗過擬合等優(yōu)點。

6 結(jié)束語

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