宋月亭，吳 晟

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

1 引言

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

在個性化推薦系統(tǒng)中，提出了大量的推薦算法，其中，協(xié)同過濾CF(Collaborative Filtering)算法是目前最成功、應用最廣泛的個性化推薦技術(shù)之一[2]。協(xié)同過濾算法假設(shè)擁有相似興趣的用戶可能會喜歡相似的項目或者用戶可能對相似的項目表現(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é)同過濾算法利用用戶-項目評分矩陣，獲得用戶或物品間的相似關(guān)系，然后用這個相似關(guān)系產(chǎn)生預測評分進行個性化推薦，因而，基于記憶的協(xié)同過濾算法又可分為基于用戶的協(xié)同過濾UBCF(User-Based Collaborative Filtering)算法和基于項目的協(xié)同過濾IBCF(Item-Based Collaborative Filtering)[4]算法。基于模型的協(xié)同過濾推薦算法是在離線情況下對目標用戶進行建模，然后在線上使用構(gòu)建好的模型對用戶進行推薦，進而達到快速推薦的效果。基于用戶的協(xié)同過濾算法的基本原理是：根據(jù)所有用戶偏好信息(評分)，尋找與當前活動用戶興趣相似的鄰居用戶，然后基于鄰居用戶的偏好記錄，為當前活動用戶進行個性化推薦[5]?；陧椖康膮f(xié)同過濾推薦算法的基本原理是：根據(jù)所有用戶對項目的偏好信息(評分)，得到項目之間的相似性，然后根據(jù)活動用戶的歷史偏好信息，將類似的項目推薦給用戶[6]。

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

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

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

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

2.1 用戶-項目評分矩陣

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

(1)

2.2 用戶間相似度計算

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

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

simcosine(i,j)=

(2)

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

simpearson(i,j)=

(3)

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

2.3 最近鄰居搜索

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

2.4 評分預測

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

(4)

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

3.1 相似度優(yōu)化

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

(5)

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

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

(6)

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

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

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

sim′cosine(i,j)=

(7)

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

sim′pearson(i,j)=

(8)

3.2 流形學習聚類算法

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

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

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

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

(9)

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

L=D-W

(10)

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

令：

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

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

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

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

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

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

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

步驟6選取集合S中對目標用戶i評分最高的前X個項目作為推薦集合。

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

4 實驗結(jié)果及分析

4.1 實驗數(shù)據(jù)及評價指標

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

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

(11)

(12)

(13)

4.2 實驗結(jié)果及分析

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

實驗1在Epinions數(shù)據(jù)集上，K∈[0,200]時傳統(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均有降低，準確率得到了提高。與此同時，優(yōu)化相似度的MLCF+算法比不優(yōu)化相似度的MLCF算法的MAE和RMSE更低，準確率最高。

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對比

實驗2在MovieLens數(shù)據(jù)集上，K∈[0,200]時傳統(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ù)集上，實驗結(jié)果呈現(xiàn)的整體趨勢與Epinions數(shù)據(jù)集上的一致，隨著K值的增大，3種算法的MAE值和RMSE值同樣呈先快速下降后逐漸平穩(wěn)的趨勢。相較Epinions數(shù)據(jù)集上的實驗結(jié)果，各算法在MovieLens數(shù)據(jù)集上穩(wěn)定性稍有不足，但總體準確率均有提高，MAE和RMSE值更小。與此同時，優(yōu)化相似度的MLCF+算法對比不優(yōu)化相似度的MLCF算法和傳統(tǒng)CF算法，擁有更低的MAE和RMSE值，準確率更高。

實驗3在用戶聚類過程中設(shè)定將用戶分割為2～6個類，進而在每個類中對項目進行推薦，計算平均召回率。在MovieLens數(shù)據(jù)集上，針對傳統(tǒng)CF算法在不同K值下推薦結(jié)果的召回率結(jié)果如表1所示。由表1中可看出，當K=130時，傳統(tǒng)CF算法召回率最高，因此對于MLCF算法和MLCF+算法也取K=130，即表示在推薦過程中項目最近相似項目集合數(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)化和流形學習的協(xié)同過濾算法(MLCF+)在推薦準確率上相較傳統(tǒng)方法和單一改進方法得到了一定的提升。同時可以看出，當?shù)螖?shù)為15時，MLCF算法和MLCF+算法的召回率基本達到最大值。用戶聚類數(shù)為2時，2種算法的召回率最大，推薦準確率最高，且當聚類數(shù)小于4時，2種算法的召回率均基本都大于傳統(tǒng)協(xié)同過濾算法的。

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

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