段廷銀, 趙東明

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

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

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

0引言

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

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

1相關(guān)工作

　　1.1符號(hào)約定

　　本文約定：

　　ri表示某一用戶對(duì)項(xiàng)目i的評(píng)分,；

　　i表示某一用戶對(duì)項(xiàng)目i評(píng)分的預(yù)測(cè)；

　　wi表示用戶i對(duì)用戶a評(píng)分預(yù)測(cè)時(shí)的權(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é)點(diǎn)之間的歐氏距離,。當(dāng)兩個(gè)用戶在同一個(gè)流形上時(shí)，其最小最大距離較?。?3］,。因此，它更好地反應(yīng)了用戶之間的近鄰關(guān)系,。

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

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

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

　　2.1最小最大距離空間

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

　　引理1最小最大距離可以確定一個(gè)距離空間,。

　　證明:

　　(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時(shí),，ρ(i,j)=0。

　?。?) 由于最小生成樹(shù)是一個(gè)無(wú)向圖,，所以有：

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

　　（3）對(duì)任意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情形類似,。否則,，因?yàn)樽钚∩蓸?shù)連通，Pij上必然存在一點(diǎn)k′使得k′∈Pik并且k′∈Pkj,。

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

　　證畢,。

　　2.2流形K近鄰

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

　　2.3視覺(jué)距離

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

　　2.4MNCF

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

　　輸入：用戶的評(píng)分記錄,。

　　輸出: 用戶對(duì)項(xiàng)目評(píng)分的預(yù)測(cè)。

　?。?)計(jì)算每個(gè)用戶已經(jīng)評(píng)論過(guò)項(xiàng)目的評(píng)分均值,。

　　（2）把（1）中計(jì)算得到的平均分作為該用戶對(duì)未評(píng)分項(xiàng)目的評(píng)分,。

　?。?）計(jì)算每個(gè)用戶之間的歐氏距離。

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

　　（5）構(gòu)造出（4）中無(wú)向有權(quán)圖的最小生成樹(shù),。

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

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

　　（8）利用k個(gè)流形近鄰對(duì)某一項(xiàng)目的評(píng)分的加權(quán)平均值作為用戶α對(duì)未評(píng)分項(xiàng)目的評(píng)分,。

3實(shí)驗(yàn)

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

　　為了評(píng)估MNCF,，本文采用了平均絕對(duì)值誤差（MAE）［15］,。

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

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

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

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

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

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

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

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

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

　　3.3不同流形鄰居數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響

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

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

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

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

4結(jié)束語(yǔ)

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

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

　?。?］ 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.

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