段廷銀, 趙東明

鄭州大學(xué) 信息工程學(xué)院， 河南 鄭州 450001

　　摘要：協(xié)同過濾技術(shù)基于用戶的評分歷史預(yù)測用戶對某一項目的評分。基于用戶的協(xié)同過濾技術(shù)可以利用傳統(tǒng)的歐氏距離發(fā)現(xiàn)與用戶的興趣相近的近鄰。針對歐氏距離并不能很好地反應(yīng)用戶之間的近鄰關(guān)系的問題，一種新穎的基于歐氏距離的最小最大距離的方法被提出，用來發(fā)現(xiàn)用戶近鄰，稱之為流形近鄰。實驗結(jié)果表明，基于流形近鄰的協(xié)同過濾框架（Collaborative Filtering based on Manifold Neighbors, MNCF）與目前的協(xié)同過濾算法相比，性能有一定的提高。

　　關(guān)鍵詞： 流形近鄰；距離空間；協(xié)同過濾；視覺距離；最小最大距離；推薦系統(tǒng)

0引言

　　協(xié)同過濾是Web 3.0時代一個新穎的技術(shù)，被廣泛應(yīng)用于各類電子商務(wù)網(wǎng)站。通常協(xié)同過濾算法分為兩大類：基于內(nèi)存的協(xié)同過濾算法和基于模型的協(xié)同過濾算法［1］?；趦?nèi)存的算法［2］首先找到k個近鄰，然后根據(jù)近鄰進(jìn)行推薦。基于模型的算法［35］通過學(xué)習(xí)用戶的歷史興趣建立用戶的偏好模型?；趦?nèi)存的算法又可分為基于用戶和基于項目的兩大類。當(dāng)前對協(xié)同過濾算法的研究主要針對數(shù)據(jù)稀疏性［67］和用戶興趣隨時間漂移問題［89］等進(jìn)行。隨著云計算的發(fā)展，一些基于云計算的分布式協(xié)同過濾算法也被提出［1012］。

　　在實際應(yīng)用中，傳統(tǒng)的基于用戶的協(xié)同過濾技術(shù)存在兩個問題：第一，大量項目評分的缺失；第二，利用歐氏距離可發(fā)現(xiàn)與用戶的興趣相近的近鄰，但是歐氏距離并不能很好地反應(yīng)用戶之間的近鄰關(guān)系。對于第一個問題，一般設(shè)置缺失值為0。然而，用戶對某一項目進(jìn)行評分時心理有一個標(biāo)準(zhǔn)，根據(jù)大數(shù)定理，平均分最能代表該標(biāo)準(zhǔn)。因此，采用平均值替換缺失值更合適。本文提出了一種新穎的基于最小最大距離的方法來發(fā)現(xiàn)用戶近鄰，稱其為流形近鄰。然后基于KNN的思想，利用近鄰對某一項目評分的加權(quán)平均值來預(yù)測用戶對某一項目的評分。對于利用近鄰不能預(yù)測的項目評分，使用用戶對其他項目的均值作為對該項目評分的預(yù)測?；谝陨戏椒ū疚慕⒁粋€基于用戶的協(xié)同過濾框架，稱之為基于流形近鄰的協(xié)同過濾算法（MNCF）。

1相關(guān)工作

　　1.1符號約定

　　本文約定：

　　ri表示某一用戶對項目i的評分；

　　i表示某一用戶對項目i評分的預(yù)測；

　　wi表示用戶i對用戶a評分預(yù)測時的權(quán)重；

　　dmin_max(i,a)表示用戶i和用戶a的最小最大距離。

　　1.2最小最大距離

　　用戶i和j之間的最小最大距離定義為：

　　dmin_max(i,j)=minkdkpij=minpkijmax(xp,xp+1)pkijdp,p+1（1）

　　其中,pkij是用戶i和用戶j之間的第k條路徑，dp,p+1是路徑上相鄰節(jié)點之間的歐氏距離。當(dāng)兩個用戶在同一個流形上時，其最小最大距離較?。?3］。因此，它更好地反應(yīng)了用戶之間的近鄰關(guān)系。

　　求解最小最大距離時，如果采用深度優(yōu)先搜索或者廣度優(yōu)先搜索，時間復(fù)雜度是指數(shù)級的。當(dāng)用戶比較多時，直接求解最小最大距離變得不可行。然而，最小生成樹（MST）恰是最小最大生成樹［14］。求解最小生成樹的時間復(fù)雜度為O(n2)。在最小生成樹上，最小最大距離由式（2）計算。

　　ρ(i,j)=dmin_max(i,j)=max(xp,xp+1)pijdp,p+1（2）

2流形近鄰協(xié)同過濾

　　2.1最小最大距離空間

　　距離空間是一種拓?fù)淇臻g，其上的拓?fù)溆芍付ǖ囊粋€距離決定。

　　引理1最小最大距離可以確定一個距離空間。

　　證明:

　　(1)由式（2）得:

　　ρ(i,j)=dmin_max(i,j)=max(xp,xp+1)pijdp,p+1≥max(xp,xp+1)pij0=0

　　當(dāng)且僅當(dāng)i=j時，ρ(i,j)=0。

　　（2) 由于最小生成樹是一個無向圖，所以有：

　　ρ(i,j)=ρ(j,i)

　?。?）對任意i，k和j，如果k∈Pij，則：

　　ρ(i,j)=dmin_max(i,j)

　　=max(max(xp,xp+1)pikdp,p+1,max(xp,xp+1)pkjdp,p+1)

　　≤max(xp,xp+1)pikdp,p+1+max(xp,xp+1)pkjdp,p+1

　　=ρ(i,k)+ρ(k,j)

　　如果k∈Pi,*或者k∈Pj,*,與k∈Pi,j情形類似。否則，因為最小生成樹連通，Pij上必然存在一點k′使得k′∈Pik并且k′∈Pkj。

　　ρ(i,j)≤ρ(i,k′)+ρ(k′,j)≤ρ(i,k)+ρ(k,j)

　　證畢。

　　2.2流形K近鄰

　　定義與用戶a流形距離最近的k個用戶為用戶a的k個近鄰。

　　2.3視覺距離

　　基于人的視覺感知，敏感度大致上與輸入信號的強度成對數(shù)關(guān)系，在考慮加權(quán)方案時，本文引入對用戶間的最小最大距離進(jìn)行對數(shù)變換的加權(quán)方案01VD。

　　2.4MNCF

　　流形近鄰協(xié)同過濾框架MNCF算法描述如下：

　　輸入：用戶的評分記錄。

　　輸出: 用戶對項目評分的預(yù)測。

　?。?)計算每個用戶已經(jīng)評論過項目的評分均值。

　?。?）把（1）中計算得到的平均分作為該用戶對未評分項目的評分。

　?。?）計算每個用戶之間的歐氏距離。

　　（4）以用戶為點集，以（3）中得到的用戶之間的歐氏距離為邊的權(quán)值構(gòu)造一個無向有權(quán)圖。

　?。?）構(gòu)造出（4）中無向有權(quán)圖的最小生成樹。

　?。?）利用（5）中的最小生成樹根據(jù)式（2）計算用戶間的最小最大距離。

　?。?）根據(jù)（6）中得到的最小最大距離求出每個用戶的k個鄰居。

　　（8）利用k個流形近鄰對某一項目的評分的加權(quán)平均值作為用戶α對未評分項目的評分。

3實驗

　　選取Movie Lens數(shù)據(jù)集對本文提到的方法進(jìn)行試驗。Movie Lens 數(shù)據(jù)集包含100 000個評分（1~5分），它們是由943個用戶對1 682個電影給出的評分。把數(shù)據(jù)集分割為兩個不相交的子集，也即是80%的訓(xùn)練集和20%的測試集。

　　為了評估MNCF，本文采用了平均絕對值誤差（MAE）［15］。

　　MAE的值越小，說明準(zhǔn)確率越高。

　　3.1不同加權(quán)方案對MNCF的影響

　　用戶i對用戶a評分權(quán)重為wi時對應(yīng)的加權(quán)方案如表1所示。不同加權(quán)方案對MNCF的影響如圖1。

　　從圖1中可以看出,當(dāng)流形近鄰數(shù)目較少時，加權(quán)方案EXND、01VD、01ED和SMN的結(jié)果相近。然而，隨著流形近鄰數(shù)目的增加，MAE的性能開始變差但趨于穩(wěn)定。而01VD、01ED、SMN的性能在流形近鄰數(shù)目足夠大時才開始發(fā)生顯著差異，并且01ED的性能表現(xiàn)最好。

　　3.2不同協(xié)同過濾框架的比較

　　在加權(quán)方案都取01VD的情況下，首先將MNCF與只使用用戶已給出評分的平均值進(jìn)行預(yù)測的算法（MCF）進(jìn)行對比；然后與采用最小最大距離加上一定權(quán)重的歐氏距離的算法（EMNCF）進(jìn)行對比。實驗結(jié)果如表2所示。 

　　其中，EMNCF和MNCF的流形鄰居數(shù)取500，EMNCF是在最小最大距離上加上0.01倍的歐氏距離。從表2中可以看出MNCF明顯優(yōu)于MCF，與EMNCF性能相當(dāng)。

　　為了比較基于歐氏距離的協(xié)同過濾算法和基于最小最大距離的協(xié)同過濾算法，此處變化鄰居數(shù)，加權(quán)方案取01VD，記使用歐氏距離的協(xié)同過濾方案為ECF，得到的實驗結(jié)果如圖2所示?！?/p>

　　從圖2可以看出，使用流形近鄰的協(xié)同過濾算法優(yōu)于使用歐氏距離的協(xié)同過濾算法。

　　3.3不同流形鄰居數(shù)對實驗結(jié)果的影響

　　圖3不同鄰居數(shù)對預(yù)測性能的影響對于MNCF，讓鄰居數(shù)從100變化到900，加權(quán)方案取01VD得到的結(jié)果如圖3所示。

　　從圖3中可以看出，當(dāng)流形近鄰數(shù)在訓(xùn)練集用戶總數(shù)一半附近時，預(yù)測效果較好。

　　3.4與最新基于用戶的協(xié)同過濾算法對比

　　從圖4中可以看出，當(dāng)流形近鄰數(shù)在訓(xùn)練集用戶總數(shù)一半附近時，預(yù)測結(jié)果的MAE控制在［0.77,0.78］之間（加權(quán)方案取01VD，流形近鄰數(shù)目從400到600，依次增1）。與文獻(xiàn)［8］、文獻(xiàn)［16］(［0.80,0.82］)中的協(xié)同過濾算法相比，有一定提高。

4結(jié)束語

　　本文介紹了最小最大距離在電影評分預(yù)測中的應(yīng)用。實驗結(jié)果表明,本文提出的基于流形近鄰的協(xié)同過濾算法與目前的協(xié)同過濾算法相比性能有一定程度的提高。在Movie lens數(shù)據(jù)集上為達(dá)到最佳性能，MNCF所需的流形鄰居數(shù)目較多，主要原因應(yīng)該是本文中的最小最大距離還是基于歐氏距離的。從實驗結(jié)果可以看出，使用最小最大距離優(yōu)于歐氏距離。本文的方法還可以被應(yīng)用到社區(qū)發(fā)現(xiàn)、傳感器網(wǎng)絡(luò)、圖像分割等領(lǐng)域。

　　在實際應(yīng)用中，往往會有數(shù)以千萬計的用戶，在傳統(tǒng)的單機系統(tǒng)上快速求解出最小最大距離顯得不可行。然而，隨著大數(shù)據(jù)時代的到來，基于MapReduce的Hadoop與Spark，旨在分布式處理實時數(shù)據(jù)的Storm，以及分布式大規(guī)模圖像處理系統(tǒng)Pregel等大數(shù)據(jù)平臺也得以飛速發(fā)展。接下來的工作是針對本文中的算法在Pregel和Spark GraphX等大數(shù)據(jù)平臺上進(jìn)行集群算法的研究與實現(xiàn)。

　　參考文獻(xiàn)

　?。?］ BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithms for collaborative filtering［C］.Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers Inc., 1998: 4352.

　　［2］ RESNICK P, IACOVOU N, Suchak M,et al. Grouplens: an open architecture for collaborative filtering of netnews［C］.Proc. of the ACM Conf. on Computer Supported Cooperative Work, 1994: 175186.

　?。?］ HOFMANN T. Probabilistic latent semantic analysis［C］.Proc of the 15th Conf. on Uncertainty in Artificial Intelligence, 1999:289296.