段廷銀, 趙東明

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

　　摘要：協(xié)同過(guò)濾技術(shù)基于用戶的評(píng)分歷史預(yù)測(cè)用戶對(duì)某一項(xiàng)目的評(píng)分。基于用戶的協(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ò)濾；視覺距離；最小最大距離；推薦系統(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)行推薦?；谀Ｐ偷乃惴ǎ?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í)，其最小最大距離較小［13］。因此，它更好地反應(yīng)了用戶之間的近鄰關(guān)系。

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

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

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

　?。?）對(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)樽钚∩蓸溥B通，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視覺距離

　　基于人的視覺感知，敏感度大致上與輸入信號(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è)。

　　（1)計(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)圖。

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

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

　　（7）根據(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的性能開始變差但趨于穩(wěn)定。而01VD、01ED、SMN的性能在流形近鄰數(shù)目足夠大時(shí)才開始發(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.

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