基于相似度優(yōu)化和流形學(xué)習(xí)的協(xié)同過濾算法改進(jìn)研究*

宋月亭，吳 晟

(昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院,云南 昆明 650500)

1 引言

互聯(lián)網(wǎng)技術(shù)極速發(fā)展的當(dāng)下，各類網(wǎng)絡(luò)應(yīng)用中的用戶量不斷增加，互聯(lián)網(wǎng)中的信息也呈現(xiàn)出指數(shù)爆炸型增長的趨勢。海量資訊致使用戶難以快速有效地檢索到所需資源，因此如何有效地篩選和過濾信息成為當(dāng)今互聯(lián)網(wǎng)研究領(lǐng)域的重要問題。個(gè)性化推薦系統(tǒng)是現(xiàn)行信息過濾應(yīng)用最為廣泛的一種重要手段，它已經(jīng)成為當(dāng)前解決“信息過載”問題的重要手段，被廣大電子商務(wù)系統(tǒng)和個(gè)性化網(wǎng)站所采用[1]。

在個(gè)性化推薦系統(tǒng)中，提出了大量的推薦算法，其中，協(xié)同過濾CF(Collaborative Filtering)算法是目前最成功、應(yīng)用最廣泛的個(gè)性化推薦技術(shù)之一[2]。協(xié)同過濾算法假設(shè)擁有相似興趣的用戶可能會(huì)喜歡相似的項(xiàng)目或者用戶可能對相似的項(xiàng)目表現(xiàn)出相似的偏好程度[3]。因此，協(xié)同過濾算法依據(jù)用戶相關(guān)評分記錄，推薦質(zhì)量較高，而且還可以發(fā)現(xiàn)用戶本身沒有發(fā)現(xiàn)的潛在興趣。

協(xié)同過濾推薦算法包括：基于記憶的協(xié)同過濾算法Me-BCF(Memory-Based Collaborative Filtering)和基于模型的協(xié)同過濾算法Mo-BCF(Model-Based Collaborative Filtering)?；谟洃浀膮f(xié)同過濾算法利用用戶-項(xiàng)目評分矩陣，獲得用戶或物品間的相似關(guān)系，然后用這個(gè)相似關(guān)系產(chǎn)生預(yù)測評分進(jìn)行個(gè)性化推薦，因而，基于記憶的協(xié)同過濾算法又可分為基于用戶的協(xié)同過濾UBCF(User-Based Collaborative Filtering)算法和基于項(xiàng)目的協(xié)同過濾IBCF(Item-Based Collaborative Filtering)[4]算法?；谀Ｐ偷膮f(xié)同過濾推薦算法是在離線情況下對目標(biāo)用戶進(jìn)行建模，然后在線上使用構(gòu)建好的模型對用戶進(jìn)行推薦，進(jìn)而達(dá)到快速推薦的效果?；谟脩舻膮f(xié)同過濾算法的基本原理是：根據(jù)所有用戶偏好信息(評分)，尋找與當(dāng)前活動(dòng)用戶興趣相似的鄰居用戶，然后基于鄰居用戶的偏好記錄，為當(dāng)前活動(dòng)用戶進(jìn)行個(gè)性化推薦[5]。基于項(xiàng)目的協(xié)同過濾推薦算法的基本原理是：根據(jù)所有用戶對項(xiàng)目的偏好信息(評分)，得到項(xiàng)目之間的相似性，然后根據(jù)活動(dòng)用戶的歷史偏好信息，將類似的項(xiàng)目推薦給用戶[6]。

不難看出，基于用戶的協(xié)同過濾算法和基于項(xiàng)目的協(xié)同過濾算法本質(zhì)都是基于鄰域的推薦方法，在整個(gè)用戶或者項(xiàng)目空間上對目標(biāo)項(xiàng)進(jìn)行最優(yōu)鄰域搜索，將最近鄰居集合進(jìn)行加權(quán)處理，進(jìn)而產(chǎn)生推薦集。其核心步驟采用的方法主要為通過余弦相似度(Cosine Similarity)或Pearson相關(guān)系數(shù)法(Pearson Correlation Coefficient)得到用戶間的相似度之后，運(yùn)用K最近鄰方法KNN(K Nearest Neighbors)為活動(dòng)用戶尋找偏好相似的近鄰，最后運(yùn)用Top-N推薦列表根據(jù)相似近鄰的評分信息為活動(dòng)用戶產(chǎn)生推薦。

協(xié)同過濾算法雖然被廣泛使用，但依舊存在一些問題：(1)數(shù)據(jù)稀疏性問題。每個(gè)用戶擁有的評價(jià)數(shù)據(jù)只占大量數(shù)據(jù)中的一小部分，致使求解相似度時(shí)共同評分過少，用戶項(xiàng)目評分矩陣形成高維稀疏矩陣，導(dǎo)致求得的相似度存在噪聲。(2)可擴(kuò)展性問題。推薦系統(tǒng)通常需要面對數(shù)以百萬計(jì)的用戶和項(xiàng)目，計(jì)算量的上升導(dǎo)致實(shí)時(shí)性和推薦質(zhì)量的下降，為此通常采用聚類、降維的方法解決[7]。通常采用K-means聚類，該算法不用考慮用戶間的相似度是多少，只選擇與目標(biāo)用戶相似度最大的用戶作為相似近鄰，但其聚類結(jié)果收斂于局部最優(yōu)解，優(yōu)化過程與初始的聚類中心有關(guān)，選取不同的聚類中心會(huì)有不同的解，初始聚類中心數(shù)據(jù)的不同選擇，可能導(dǎo)致最終推薦準(zhǔn)確率不佳。

基于以上問題，本文提出一種基于相似度優(yōu)化和流形學(xué)習(xí)的協(xié)同過濾算法，通過改進(jìn)相似度計(jì)算，再運(yùn)用流形學(xué)習(xí)的方法根據(jù)相似度對用戶求解最近鄰，最后求得推薦結(jié)果?？紤]數(shù)據(jù)稀疏性，將評價(jià)存在的內(nèi)在信息也充分使用的同時(shí)，提高推薦準(zhǔn)確率。

2 傳統(tǒng)協(xié)同過濾算法

2.1 用戶-項(xiàng)目評分矩陣

定義用戶集合U={1,2，…，m}，其中|U|=m，定義項(xiàng)目集合I={1，2，…，n}，其中|I|=n，定義用戶對項(xiàng)目評分矩陣R=[ri,j]m×n,如式(1)所示。

(1)

2.2 用戶間相似度計(jì)算

根據(jù)用戶間共同評分項(xiàng)目的評分?jǐn)?shù)據(jù)，利用相似度計(jì)算公式，求出用戶i和用戶j間的相似度sim(i,j)。常見的相似度計(jì)算公式如下所示：

(1)修正的余弦相似度如式(2)所示。

simcosine(i,j)=

(2)

(2)Person相關(guān)系數(shù)相似度如式(3)所示。

simpearson(i,j)=

(3)

其相似度取值為[-1,1]，值越大，則表示用戶間相似程度越高。

2.3 最近鄰居搜索

根據(jù)目標(biāo)用戶與所有其他用戶的相似度，通過K-means聚類，選取與目標(biāo)用戶最接近的前k個(gè)用戶作為其最近鄰居。

2.4 評分預(yù)測

令目標(biāo)用戶的最近鄰集合為N(u)，則利用N(u)中的用戶對用戶u的未評分項(xiàng)目進(jìn)行評分。計(jì)算公式如式(4)所示。

(4)

3 基于相似度優(yōu)化和流形學(xué)習(xí)的改進(jìn)協(xié)同過濾算法

3.1 相似度優(yōu)化

在傳統(tǒng)的協(xié)同過濾算法相似度計(jì)算中，存在著一些問題。假設(shè)2個(gè)用戶間共同評分項(xiàng)目很多，且2個(gè)用戶對這些共同項(xiàng)目的評分均不高，則間接表明2個(gè)用戶并不傾向于這些項(xiàng)目。假設(shè)2個(gè)用戶間共同評分項(xiàng)目不多，但是對于這少量的共同評分項(xiàng)均有較高的評分，則間接表明2個(gè)用戶更傾向于這些項(xiàng)目。故可以看出，用戶對共同評分項(xiàng)的評分比重對相似度計(jì)算精度有一定的影響，因此本文引入一種共同評分項(xiàng)評分所占比重的加權(quán)因子優(yōu)化相似度計(jì)算，該加權(quán)因子表述如式(5)所示。

(5)

式(5)中的加權(quán)因子盡管考慮了2個(gè)用戶共同評分項(xiàng)分?jǐn)?shù)所占比重，但當(dāng)某個(gè)用戶的評分項(xiàng)目很少時(shí)，該用戶與某個(gè)評分很多的用戶產(chǎn)生的共同評分項(xiàng)目很多，且項(xiàng)目評分相近或相同時(shí)，傳統(tǒng)的相似度計(jì)算方法會(huì)產(chǎn)生高相似度的結(jié)果，但2個(gè)用戶在非共同評分項(xiàng)目上的評分可能存在較大的差異。因此，考慮到共同評分項(xiàng)目個(gè)數(shù)在2個(gè)用戶總評分項(xiàng)目集合中所占的比例，進(jìn)一步改進(jìn)加權(quán)因子，如式(6)所示。

w(i,j)=w1(i,j)·w2(i,j)=

(6)

其中，Tij={(ts|ts∈T∧ri,s≠0∧rj,s≠0},為2個(gè)用戶共同評分項(xiàng)目集合，Ti和Tj分別為各用戶的評分項(xiàng)目集合，Ti={ts|ts∈T∧ri,s≠0}，Tj={ts|ts∈T∧rj,s≠0}。

綜上，通過加權(quán)因子對傳統(tǒng)的相似度計(jì)算方法進(jìn)行優(yōu)化，最終得到如下所示的相似度計(jì)算方法：

(1)基于修正余弦相似度優(yōu)化方法。

sim′cosine(i,j)=

(7)

(2)基于Pearson相似度優(yōu)化方法。

sim′pearson(i,j)=

(8)

3.2 流形學(xué)習(xí)聚類算法

流形學(xué)習(xí)是解決高維大數(shù)據(jù)問題的方法，對于數(shù)據(jù)稀疏且高維的協(xié)同過濾推薦系統(tǒng)，流形聚類可通過降維發(fā)現(xiàn)數(shù)據(jù)內(nèi)在聯(lián)系，減少傳統(tǒng)聚類存在的局部最優(yōu)解問題[8]。其中較為典型的是譜聚類算法，譜聚類以圖論為基礎(chǔ)，將一個(gè)樣本作為定點(diǎn)，樣本間相似度作為帶權(quán)邊，尋找組成邊權(quán)重較低且組內(nèi)邊權(quán)重較高的圖[9,10]。該流形聚類算法以樣本間相似度為核心，相較傳統(tǒng)K-means聚類方法，將聚類問題轉(zhuǎn)換為圖分割問題，不受形狀限制，可求得全局最優(yōu)解。本文采用流形聚類改進(jìn)協(xié)同過濾推薦算法中傳統(tǒng)的基于距離的K-means聚類，可在搜索最近鄰居的過程中，通過降維降低計(jì)算成本的同時(shí)獲得全局最優(yōu)解，提高推薦準(zhǔn)確率。步驟如下所示：

(1)輸入一個(gè)M×N的矩陣W，即W中共包含N個(gè)數(shù)據(jù)點(diǎn)。

(2)構(gòu)建W的相似度矩陣D∈RN×N，其中，Dij=Dji(i,j=1,…,N)。以所有頂點(diǎn)度為對角元素構(gòu)成的矩陣D的具體構(gòu)建方法如式(9)所示。

D=diag(D11,D12,…,DNN)

(9)

(3)計(jì)算拉普拉斯矩陣L，如式(10)所示。

L=D-W

(10)

(4)對L進(jìn)行歸一化處理，得到歸一化矩陣E。其中

令：

(5)計(jì)算矩陣L的歸一化矩陣E的Y個(gè)最大特征值及其對應(yīng)的特征向量，形成一個(gè)N×Y的特征矩陣，記為Q。

(6)將特征矩陣Q的每一行看成k維空間中的一個(gè)向量，使用K-means對其進(jìn)行聚類。

3.3 基于相似度優(yōu)化和流形學(xué)習(xí)的協(xié)同過濾算法

針對傳統(tǒng)協(xié)同過濾算法中存在的不足，通過對相似度和搜索最近鄰居進(jìn)行優(yōu)化改進(jìn)，本文提出一種基于相似度優(yōu)化和流形學(xué)習(xí)的協(xié)同過濾算法MLCF+(Collaborative Filtering algorithm based on Manifold Learning and similarity optimization)。其基本思想為：基于用戶間共同評分項(xiàng)目通過加權(quán)因子獲得更為精確的用戶相似矩陣，利用流形學(xué)習(xí)中的譜聚類算法將與目標(biāo)用戶相似度最大的最近鄰居聚為一類，在最近鄰域中對目標(biāo)用戶進(jìn)行TOP-N推薦。該算法旨在通過加權(quán)相似度計(jì)算影響因子對相似度計(jì)算進(jìn)行優(yōu)化，同時(shí)通過流形學(xué)習(xí)中的譜聚類算法，緩解傳統(tǒng)協(xié)同過濾算法中運(yùn)用的K-means等聚類算法初始聚類中心選擇對最后推薦準(zhǔn)確率的影響，使聚類收斂于全局最優(yōu)，通過對分類結(jié)果精度的提高進(jìn)而提高推薦準(zhǔn)確率。MLCF+算法流程如圖1所示，具體步驟如下所示：

步驟1對用戶評分矩陣R=[ri,j]m×n，根據(jù)加權(quán)相似度優(yōu)化計(jì)算公式計(jì)算各用戶間的相似度，本文選用優(yōu)化后的Pearson相似度計(jì)算方法，得到用戶間的相似矩陣A∈Rm×m，其中Ai,j=sim(i,j)。

步驟2將每個(gè)用戶對應(yīng)到譜圖中的一個(gè)頂點(diǎn)，利用譜聚類，通過構(gòu)建拉普拉斯矩陣、求取特征向量進(jìn)而重組矩陣進(jìn)行聚類，將所有用戶分成k類，分別記為U1,U2,…,Uk，其中，Ui∩Uj=?，1≤i,j≤k,U1∪U2∪…∪Uk=U。

步驟3設(shè)目標(biāo)用戶i∈Uj，該集合內(nèi)用戶和評分項(xiàng)目間的信息矩陣記作Hi∈Rni×m，目標(biāo)用戶i已評分項(xiàng)目集合為G，未評分項(xiàng)目集合為S，其中，ni為Uj集合中用戶個(gè)數(shù)。計(jì)算矩陣Hi中各項(xiàng)目間相似度，得到項(xiàng)目間相似度矩陣V∈Rn×n。

步驟6選取集合S中對目標(biāo)用戶i評分最高的前X個(gè)項(xiàng)目作為推薦集合。

Figure 1 Flow chart of MLCF+ algorithm圖1 MLCF+算法流程圖

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

4.1 實(shí)驗(yàn)數(shù)據(jù)及評價(jià)指標(biāo)

本文選用Epinions數(shù)據(jù)集和MovieLens數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其中，Epinions數(shù)據(jù)集包含49 290個(gè)用戶對139 738個(gè)項(xiàng)目的共664 824條評分?jǐn)?shù)據(jù)，評分為1～5分，數(shù)據(jù)稀疏度為99.99%。MovieLens數(shù)據(jù)集包含943個(gè)用戶對1 682個(gè)項(xiàng)目的共100 000條評分?jǐn)?shù)據(jù)，評分為1～5分，數(shù)據(jù)稀疏度為93.7%。實(shí)驗(yàn)中，隨機(jī)取80%的數(shù)據(jù)作為訓(xùn)練集，20%的數(shù)據(jù)為測試集。

利用平均絕對誤差MAE(Mean Absolute Error)、均方根誤差RMSE(Root Mean Squared Error)和召回率Recall作為實(shí)驗(yàn)結(jié)果評價(jià)指標(biāo)。MAE和RMSE的值越小，召回率越大，則推薦準(zhǔn)確率越高。計(jì)算公式分別如式(11)～式(13)所示。

(11)

(12)

(13)

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

取0～200內(nèi)10個(gè)不同的K值來測試基于相似度優(yōu)化和流形學(xué)習(xí)的協(xié)同過濾算法MLCF+、傳統(tǒng)協(xié)同過濾算法CF和不優(yōu)化相似度的流形學(xué)習(xí)協(xié)同過濾算法MLCF(Collaborative Filtering algorithm based on Manifold Learning)。采用5折交叉驗(yàn)證法進(jìn)行驗(yàn)證，重復(fù)實(shí)驗(yàn)5次取平均值作為最終結(jié)果。

實(shí)驗(yàn)1在Epinions數(shù)據(jù)集上，K∈[0,200]時(shí)傳統(tǒng)CF算法、MLCF算法和MLCF+算法的平均絕對誤差MAE和均方根誤差RMSE對比如圖2和圖3所示。從圖2和圖3可以看出，在Epinions數(shù)據(jù)集上，隨著K值的增大，3種算法的MAE值和RMSE值均呈先快速下降后逐漸平穩(wěn)的趨勢。其中，MLCF算法相對傳統(tǒng)CF算法，MAE和RMSE均有降低，準(zhǔn)確率得到了提高。與此同時(shí)，優(yōu)化相似度的MLCF+算法比不優(yōu)化相似度的MLCF算法的MAE和RMSE更低，準(zhǔn)確率最高。

Figure 2 MAE comparison of different algorithms on Epinions dataset圖2 在Epinions數(shù)據(jù)集上不同算法的MAE對比

Figure 3 RMSE comparison of different algorithms on Epinions dataset圖3 在Epinions數(shù)據(jù)集上不同算法的RMSE對比

實(shí)驗(yàn)2在MovieLens數(shù)據(jù)集上，K∈[0,200]時(shí)傳統(tǒng)CF算法、MLCF算法和MLCF+算法的平均絕對誤差MAE和均方根誤差RMSE對比如圖4和圖5所示。

Figure 4 MAE comparison of different algorithms on MovieLens dataset圖4 在MovieLens數(shù)據(jù)集上不同算法的MAE對比

Figure 5 RMSE comparison of different algorithms on MovieLens dataset圖5 在MovieLens數(shù)據(jù)集上不同算法的RMSE對比

從圖4和圖5可以看出，在MovieLens數(shù)據(jù)集上，實(shí)驗(yàn)結(jié)果呈現(xiàn)的整體趨勢與Epinions數(shù)據(jù)集上的一致，隨著K值的增大，3種算法的MAE值和RMSE值同樣呈先快速下降后逐漸平穩(wěn)的趨勢。相較Epinions數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，各算法在MovieLens數(shù)據(jù)集上穩(wěn)定性稍有不足，但總體準(zhǔn)確率均有提高，MAE和RMSE值更小。與此同時(shí)，優(yōu)化相似度的MLCF+算法對比不優(yōu)化相似度的MLCF算法和傳統(tǒng)CF算法，擁有更低的MAE和RMSE值，準(zhǔn)確率更高。

實(shí)驗(yàn)3在用戶聚類過程中設(shè)定將用戶分割為2～6個(gè)類，進(jìn)而在每個(gè)類中對項(xiàng)目進(jìn)行推薦，計(jì)算平均召回率。在MovieLens數(shù)據(jù)集上，針對傳統(tǒng)CF算法在不同K值下推薦結(jié)果的召回率結(jié)果如表1所示。由表1中可看出，當(dāng)K=130時(shí)，傳統(tǒng)CF算法召回率最高，因此對于MLCF算法和MLCF+算法也取K=130，即表示在推薦過程中項(xiàng)目最近相似項(xiàng)目集合數(shù)為130。表2和表3所示分別為MLCF算法和MLCF+算法在不同聚類數(shù)下推薦結(jié)果的召回率。

結(jié)果表明，與傳統(tǒng)協(xié)同過濾推薦算法(CF)相比，MLCF算法和MLCF+算法的召回率都有明顯提高，另外，在相同聚類數(shù)和迭代次數(shù)下，相似度優(yōu)化的MLCF+算法比不優(yōu)化相似度的MLCF算

Table 1 Recall of traditional CF algorithm under different K values表1 傳統(tǒng)CF算法在不同K值下的召回率

法推薦結(jié)果的召回率高。說明本文提出的基于相似度優(yōu)化和流形學(xué)習(xí)的協(xié)同過濾算法(MLCF+)在推薦準(zhǔn)確率上相較傳統(tǒng)方法和單一改進(jìn)方法得到了一定的提升。同時(shí)可以看出，當(dāng)?shù)螖?shù)為15時(shí)，MLCF算法和MLCF+算法的召回率基本達(dá)到最大值。用戶聚類數(shù)為2時(shí)，2種算法的召回率最大，推薦準(zhǔn)確率最高，且當(dāng)聚類數(shù)小于4時(shí)，2種算法的召回率均基本都大于傳統(tǒng)協(xié)同過濾算法的。

綜合上述實(shí)驗(yàn)，表明本文提出的MLCF算法可以更為精準(zhǔn)地通過聚類找到與目標(biāo)用戶具有相似愛好的用戶，進(jìn)而獲得更高準(zhǔn)確率的推薦。結(jié)合相似度優(yōu)化的MLCF+算法，擁有優(yōu)于其他算法的召回率，緩解了數(shù)據(jù)稀疏性的問題，從而進(jìn)一步提高了協(xié)同過濾推薦算法的準(zhǔn)確率。

Table 2 Recall of MLCF algorithm without optimized similarity under different clustering numbers表2 不優(yōu)化相似度的MLCF算法在不同聚類數(shù)下的召回率

Table 3 Recall of MLCF+ algorithm with optimized similarity under different clustering numbers表3 優(yōu)化相似度的MLCF+算法在不同聚類數(shù)下的召回率

5 結(jié)束語

傳統(tǒng)的協(xié)同過濾算法存在數(shù)據(jù)稀疏性和可擴(kuò)展性的問題，面對高維稀疏數(shù)據(jù)，如何降維后精準(zhǔn)發(fā)現(xiàn)相似項(xiàng)進(jìn)而進(jìn)行推薦，是該算法改進(jìn)的關(guān)鍵。本文提出了一種基于相似度優(yōu)化和流形學(xué)習(xí)的協(xié)同過濾算法，通過考慮加權(quán)因子優(yōu)化傳統(tǒng)相似度計(jì)算，提高相似度計(jì)算準(zhǔn)確率，同時(shí)利用流形學(xué)習(xí)中的譜聚類對矩陣進(jìn)行用戶聚類搜索最近鄰居，降低用戶維度的同時(shí)，使用戶聚類結(jié)果收斂于全局最優(yōu)，進(jìn)而提高協(xié)同過濾算法推薦準(zhǔn)確率。實(shí)驗(yàn)結(jié)果表明，基于相似度優(yōu)化和流形學(xué)習(xí)的協(xié)同過濾算法相較傳統(tǒng)算法，推薦準(zhǔn)確率得到了改善。下一步將結(jié)合冷啟動(dòng)問題進(jìn)一步改善協(xié)同過濾算法性能。