基于SGA-RBF的協(xié)同過濾算法研究

王玉珍 ，許艷茹 ，常 丹

（蘭州財(cái)經(jīng)大學(xué)a.絲綢之路經(jīng)濟(jì)研究院；b.信息工程學(xué)院，蘭州 730020）

0 引言

隨著科學(xué)技術(shù)的發(fā)展，大量的信息出現(xiàn)在人們的生活中，歌曲、電影、新聞以及商品等是大多數(shù)人關(guān)注較多的信息。因此，為了滿足用戶迫切想獲取有用信息這一需求，推薦技術(shù)的使用已經(jīng)成為一種常態(tài)。而推薦技術(shù)的核心是推薦算法，目前，就應(yīng)用領(lǐng)域來說，像貝葉斯方法[1]、神經(jīng)網(wǎng)絡(luò)方法[2]、聚類方法[3]等基于模型的協(xié)同過濾算法[4]的應(yīng)用最為廣泛。近年來，人們對(duì)該領(lǐng)域的研究越來越深入，研究成果也越來越多。主要的研究成果如下：王曉耘等[5]提出一種基于粗糙用戶聚類的協(xié)同過濾推薦模型，采用粗糙K-means算法對(duì)用戶聚類，形成用戶的初始近鄰集，然后從目標(biāo)用戶的初始近鄰集中搜索其最近鄰，根據(jù)搜索結(jié)果預(yù)測(cè)項(xiàng)目評(píng)分并進(jìn)行推薦；Baltrunas等[6]將項(xiàng)目依據(jù)上下文分裂成兩個(gè)，然后按照特定的上下文關(guān)系來預(yù)測(cè)用戶評(píng)分并進(jìn)行推薦；冷亞軍等[7]在對(duì)用戶聚類的基礎(chǔ)上，根據(jù)用戶偏好建立偏好矩陣，進(jìn)行預(yù)測(cè)評(píng)分并推薦；張星等[8]為每個(gè)用戶根據(jù)其興趣愛好的差異性，創(chuàng)建了個(gè)性化的項(xiàng)目相似度的計(jì)算過程，因該過程與用戶的興趣愛好結(jié)合緊密，從而有效提高了推薦的精度；葉蘭平等[9]利用RBF神經(jīng)網(wǎng)絡(luò)能夠有效進(jìn)行非線性逼近這一特點(diǎn)，利用用戶的相似度，進(jìn)行評(píng)分預(yù)測(cè)；薛福亮[10]將Vague集融入電子商務(wù)推薦中，并且使用SOM算法改進(jìn)RBF神經(jīng)網(wǎng)絡(luò)，降低了預(yù)測(cè)誤差；Jia等[11]將偏最小二乘法和遺傳算法引入RBF神經(jīng)網(wǎng)絡(luò)中，取得了更好的效果。可見，雖然目前對(duì)基于模型的協(xié)同過濾方法已有一定的研究，但是在推薦領(lǐng)域采用RBF神經(jīng)網(wǎng)絡(luò)的研究成果還較少。因此，本文在優(yōu)化RBF神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)上，提出了一種SGA-RBF神經(jīng)網(wǎng)絡(luò)模型，并將SGA-RBF神經(jīng)網(wǎng)絡(luò)與協(xié)同過濾算法結(jié)合，預(yù)測(cè)了未評(píng)分項(xiàng)目的分?jǐn)?shù)，從而提高了預(yù)測(cè)的準(zhǔn)確性。

1 推薦技術(shù)

1.1 協(xié)同過濾算法

協(xié)同過濾算法作為使用最廣泛的推薦算法，其過程如下：

1.1.1 評(píng)分信息的預(yù)處理

Items代表項(xiàng)目，Users代表用戶，Suj表示用戶Usersu對(duì)項(xiàng)目Itemsj的評(píng)分（如表1所示）。

表1 用戶-項(xiàng)目評(píng)分矩陣R

1.1.2 最近鄰居集的建立

該步驟的任務(wù)是根據(jù)項(xiàng)目之間的相似度建立最近鄰集。通常，相似度可采用以下方法計(jì)算：

（1）余弦相似度

余弦相似度是根據(jù)向量空間中的兩個(gè)向量夾角的余弦值來度量的，見式（1）所示：

（2）修正的余弦相似度

為了彌補(bǔ)余弦相似度只在方向上區(qū)分差異的不足，修正的余弦相似度的計(jì)算方法應(yīng)運(yùn)而生。見式（2）所示：

（3）Pearson相關(guān)系數(shù)

該方法是根據(jù)項(xiàng)目之間的相關(guān)關(guān)系來度量相似度，見式（3）所示：

其中，Aui和Auj分別表示用戶對(duì)項(xiàng)目i和項(xiàng)目j的評(píng)分分別表示所有用戶對(duì)項(xiàng)目i、項(xiàng)目j評(píng)分的均值。

根據(jù)相似度的計(jì)算結(jié)果，將相似度較大的n個(gè)項(xiàng)目用來構(gòu)成最近鄰集。

1.1.3 進(jìn)行預(yù)測(cè)評(píng)分并推薦

由以上兩步獲取每個(gè)項(xiàng)目的最近鄰居集，根據(jù)最近鄰居集中的評(píng)分?jǐn)?shù)據(jù)預(yù)測(cè)用戶對(duì)某個(gè)項(xiàng)目的評(píng)分。見式（4）所示：

根據(jù)評(píng)分預(yù)測(cè)的結(jié)果，將分?jǐn)?shù)排名靠前M個(gè)項(xiàng)目推薦給目標(biāo)用戶。

1.2 RBF神經(jīng)網(wǎng)絡(luò)

徑向基函數(shù)（Radial Basis Function，RBF）神經(jīng)網(wǎng)絡(luò)[12]是20世紀(jì)80年代末，由J.Moody和C.Darken提出的，該神經(jīng)網(wǎng)絡(luò)是具有單隱層的三層前饋網(wǎng)絡(luò)，能有效進(jìn)行非線性逼近，被廣泛應(yīng)用于各領(lǐng)域。

（1）RBF網(wǎng)絡(luò)結(jié)構(gòu)

RBF網(wǎng)絡(luò)是一種三層前向網(wǎng)絡(luò)，其網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。在圖1中，xn代表輸入值，hn代表隱藏層的輸出值，wn代表隱藏層與輸出層的連接權(quán)值，Ym代表輸出層的輸出值。

圖1 RBF神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

（2）RBF網(wǎng)絡(luò)的逼近

采用RBF網(wǎng)絡(luò)逼近一對(duì)象的結(jié)構(gòu)如圖2所示。

圖2 RBF神經(jīng)網(wǎng)絡(luò)逼近

其中，gi為節(jié)點(diǎn)j的基寬參數(shù)，且為大于零的數(shù)。網(wǎng)絡(luò)的權(quán)向量為：

RBF網(wǎng)絡(luò)的輸出為：

RBF網(wǎng)絡(luò)逼近的性能指標(biāo)函數(shù)為：

根據(jù)梯度下降法，輸出權(quán)、節(jié)點(diǎn)基寬參數(shù)及節(jié)點(diǎn)中心矢量的迭代算法如下：

式（10）至式（14）中，η為學(xué)習(xí)速率，α為動(dòng)量因子，η∈[0，1]，α∈[0，1]。將對(duì)象輸出對(duì)輸入的敏感度稱為Jacobian信息，其值由RBF神經(jīng)網(wǎng)絡(luò)辨識(shí)而得[13]。

辨識(shí)算法如下：取RBF網(wǎng)絡(luò)的第一個(gè)輸入為z(k)，即x1=z(k)，即：

本文使用的RBF網(wǎng)絡(luò)中，網(wǎng)絡(luò)隱藏層神經(jīng)元個(gè)數(shù)為4，網(wǎng)絡(luò)結(jié)構(gòu)2-4-1。

1.3 遺傳算法

遺傳算法[14]是模仿生物生存的機(jī)理而形成的，Goldberg總結(jié)了一種最基本的遺傳算法——簡(jiǎn)單遺傳算法（Simple Genetic Algorithms，簡(jiǎn)稱SGA）。SGA包含了編碼、初始種群的生成、種群中個(gè)體適應(yīng)度的檢測(cè)評(píng)估、選擇、交叉、變異5個(gè)基本步驟。

（1）問題編碼和適應(yīng)度

SGA通常作用于確定長(zhǎng)度的二進(jìn)制串上，即I={0 ，1}l。比如，分量可以表示為串長(zhǎng)為lx的二進(jìn)制代碼，即譯碼函數(shù)為，式中，為參數(shù)xl的二進(jìn)制表達(dá)，本文采用二進(jìn)制編碼。適應(yīng)度函數(shù)Φ(x)通常選為確保適應(yīng)值為正值，并且最好個(gè)體的適應(yīng)值最大的函數(shù)[13]。

（2）選擇

選擇（Selection）即從群體中按個(gè)體的適應(yīng)度函數(shù)值選擇出較適應(yīng)環(huán)境的個(gè)體。

（3）交叉

SGA中，交叉（Crossover）的目的是把兩個(gè)不同個(gè)體上的有用段組合在一起，從而實(shí)現(xiàn)進(jìn)化。Holland的一點(diǎn)交換算子作用機(jī)理如下：設(shè)兩個(gè)父輩個(gè)體分別為隨機(jī)選擇交換點(diǎn)d=random(1，2，…，l-1)，產(chǎn)生的兩個(gè)子代個(gè)體分別為

（4）變異

在SGA中，通常變異（Mutation）被認(rèn)為是為確保每一代個(gè)體的多樣性而設(shè)置的輔助算子。Pm的值一般為0.001到0.1之間。個(gè)體，其中：

式中，?i∈(1，…，l)；θi為0與1之間的隨機(jī)數(shù)。Pm的取值一般很小，否則SGA退化為簡(jiǎn)單的隨機(jī)搜索。

在實(shí)際應(yīng)用中，SGA的串長(zhǎng)(1)、群體大小(n)、交叉概率(Pc)、變異概率(Pm)等參數(shù)的取值對(duì)其性能影響很大。通常情況下，各參數(shù)的取值如表2所示。

表2 SGA的各參數(shù)取值表

由于這些參數(shù)的選擇難度大，近年來更多學(xué)者已經(jīng)認(rèn)識(shí)到研究這些參數(shù)隨遺傳進(jìn)程而自適應(yīng)變化問題的重要性。

2 基于SGA-RBF的協(xié)同過濾算法

RBF神經(jīng)網(wǎng)絡(luò)的參數(shù)初始值的選擇存在隨機(jī)性，容易給模型造成誤差。遺傳算法具有全局優(yōu)化的優(yōu)點(diǎn)，能夠使RBF神經(jīng)網(wǎng)絡(luò)的初值權(quán)值得到優(yōu)化，提高RBF神經(jīng)網(wǎng)絡(luò)模型的準(zhǔn)確率。

2.1SGA優(yōu)化RBF神經(jīng)網(wǎng)絡(luò)

由于RBF神經(jīng)網(wǎng)絡(luò)的初始參數(shù)很難確定，用簡(jiǎn)單遺傳算法可以優(yōu)化其網(wǎng)絡(luò)參數(shù)，使逼近更加準(zhǔn)確，具體的算法步驟如圖3所示。

圖3 SGA優(yōu)化RBF神經(jīng)網(wǎng)絡(luò)算法流程

2.2 推薦算法設(shè)計(jì)

本文用遺傳算法優(yōu)化RBF神經(jīng)網(wǎng)絡(luò)的初始權(quán)值，提出了SGA-RBF神經(jīng)網(wǎng)絡(luò)模型，然后在項(xiàng)目相似度的基礎(chǔ)上，將SGA-RBF神經(jīng)網(wǎng)絡(luò)與協(xié)同過濾算法結(jié)合。本文以電影推薦為例來說明該算法，具體的算法步驟如下：

（1）構(gòu)建“Users-Items”矩陣

本文所構(gòu)建的“Users-Items”矩陣如表3所示。

表3 “Users-Items”評(píng)分矩陣

矩陣中的行向量代表m個(gè)用戶，列項(xiàng)代表n部電影，矩陣值代表每個(gè)用戶對(duì)每部電影的具體評(píng)分。

（2）建立項(xiàng)目的近鄰集

首先采用Pearson相關(guān)系數(shù)法計(jì)算出項(xiàng)目相似度，然后按照每個(gè)項(xiàng)目相似度由高到低進(jìn)行排序，選出其中的前n個(gè)構(gòu)成近鄰集。

（3）構(gòu)建SGA-RBF神經(jīng)網(wǎng)絡(luò)模型并預(yù)測(cè)評(píng)分

獲得近鄰集之后，則可用目標(biāo)項(xiàng)目i與其近鄰集的評(píng)分來訓(xùn)練與仿真網(wǎng)絡(luò)。具體步驟如下[13]：

步驟1：生成集合S1和S2。其中S1是項(xiàng)目i與近鄰集中的項(xiàng)目的共同評(píng)分用戶集合，S2是對(duì)近鄰項(xiàng)目評(píng)分而未對(duì)項(xiàng)目i評(píng)分的用戶的評(píng)分?jǐn)?shù)據(jù)集合；

步驟2：用遺傳算法優(yōu)化RBF神經(jīng)網(wǎng)絡(luò)的初始權(quán)值；

步驟3：設(shè)置神經(jīng)網(wǎng)絡(luò)的訓(xùn)練樣本輸入為S1中項(xiàng)目j的評(píng)分?jǐn)?shù)據(jù)，訓(xùn)練樣本輸出為S1中用戶對(duì)目標(biāo)項(xiàng)目i的評(píng)分?jǐn)?shù)據(jù)；

步驟4：將S2中對(duì)j評(píng)分的數(shù)據(jù)輸入訓(xùn)練好的網(wǎng)絡(luò)中，輸出值則為S2中的用戶對(duì)目標(biāo)項(xiàng)目i的預(yù)測(cè)評(píng)分值；

步驟5：如果j是S1中的最后一個(gè)項(xiàng)目，則繼續(xù)步驟6，否則，返回步驟3；

步驟6：根據(jù)計(jì)算結(jié)果求出目標(biāo)項(xiàng)目求平均值。

（4）推薦

根據(jù)評(píng)分預(yù)測(cè)的結(jié)果，從中選出評(píng)分較高的M個(gè)項(xiàng)目，作為目標(biāo)項(xiàng)目推薦給用戶。

3 模型評(píng)價(jià)

本文使用公開的數(shù)據(jù)集movielens來檢驗(yàn)算法的有效性。數(shù)據(jù)集共10000條數(shù)據(jù)，包括1682部電影和943個(gè)用戶，按時(shí)間排序后，取出每個(gè)用戶最后的10條數(shù)據(jù)為測(cè)試集，其余數(shù)據(jù)為訓(xùn)練集，供實(shí)驗(yàn)使用。

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

本文的實(shí)驗(yàn)中，用平均絕對(duì)誤差（MAE）來評(píng)估實(shí)驗(yàn)結(jié)果。其公式如式（17）所示：

其中mi表示預(yù)測(cè)評(píng)分，ki表示用戶對(duì)項(xiàng)目的實(shí)際評(píng)分。

3.2 實(shí)驗(yàn)結(jié)果及分析

本文共進(jìn)行了兩個(gè)實(shí)驗(yàn)，分別比較了不同近鄰數(shù)對(duì)應(yīng)的MAE值與不同稀疏度對(duì)應(yīng)的MAE值。

（1）不同近鄰數(shù)對(duì)應(yīng)的MAE值

用movielens數(shù)據(jù)集來測(cè)試當(dāng)近鄰數(shù)N變化時(shí)，采用SGA優(yōu)化前后的基于RBF神經(jīng)網(wǎng)絡(luò)的協(xié)同過濾算法MAE的變化情況，其結(jié)果如圖4所示。

圖4 不同近鄰數(shù)下的MAE變化

圖4顯示了當(dāng)近鄰數(shù)N分別取5、10、15、20、25、30時(shí)，基于RBF的協(xié)同過濾算法和基于SGA-RBF的協(xié)同過濾算法的MAE值的變化。由圖可知，改進(jìn)算法的MAE值明顯低于基于RBF的協(xié)同過濾算法的MAE值。可見，經(jīng)過SGA優(yōu)化的RBF神經(jīng)網(wǎng)絡(luò)的性能優(yōu)于未優(yōu)化的RBF神經(jīng)網(wǎng)絡(luò)。

（2）不同稀疏度對(duì)應(yīng)的MAE值

本文將movielens數(shù)據(jù)集按稀疏度劃分了五類，即0～0.05、0.05～0.1、0.1～0.15、0.15～0.2、0.2以上，比較每個(gè)稀疏度區(qū)間內(nèi)改進(jìn)算法與原RBF協(xié)同過濾算法之間的差異。

圖5 不同稀疏度區(qū)間內(nèi)的MAE變化

由圖5可以看出，對(duì)于每個(gè)稀疏度區(qū)間，本文所提出的算法均優(yōu)于基于RBF的協(xié)同過濾算法，而且對(duì)于稀疏度越小的區(qū)間，優(yōu)化的效果越明顯。

4 結(jié)束語

本文首先用遺傳算法優(yōu)化RBF神經(jīng)網(wǎng)絡(luò)的初始權(quán)值，提出了SGA-RBF神經(jīng)網(wǎng)絡(luò)模型，然后在項(xiàng)目相似度的基礎(chǔ)上，將SGA-RBF神經(jīng)網(wǎng)絡(luò)與協(xié)同過濾算法結(jié)合，預(yù)測(cè)了未評(píng)分項(xiàng)目的分?jǐn)?shù)，最后將預(yù)測(cè)評(píng)分和實(shí)際評(píng)分進(jìn)行比較，并計(jì)算了平均相對(duì)誤差。實(shí)驗(yàn)結(jié)果顯示，用遺傳算法改進(jìn)RBF神經(jīng)網(wǎng)絡(luò)的初始權(quán)值能有效的提高RBF神經(jīng)網(wǎng)絡(luò)的性能，減小平均絕對(duì)誤差，提高預(yù)測(cè)準(zhǔn)確率。