段廷銀, 趙東明

鄭州大學 信息工程學院， 河南 鄭州 450001

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

　　關鍵詞： 流形近鄰；距離空間；協同過濾；視覺距離；最小最大距離；推薦系統

0引言

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

　　在實際應用中，傳統的基于用戶的協同過濾技術存在兩個問題：第一，大量項目評分的缺失；第二，利用歐氏距離可發現與用戶的興趣相近的近鄰，但是歐氏距離并不能很好地反應用戶之間的近鄰關系。對于第一個問題，一般設置缺失值為0。然而，用戶對某一項目進行評分時心理有一個標準，根據大數定理，平均分最能代表該標準。因此，采用平均值替換缺失值更合適。本文提出了一種新穎的基于最小最大距離的方法來發現用戶近鄰，稱其為流形近鄰。然后基于KNN的思想，利用近鄰對某一項目評分的加權平均值來預測用戶對某一項目的評分。對于利用近鄰不能預測的項目評分，使用用戶對其他項目的均值作為對該項目評分的預測。基于以上方法本文建立一個基于用戶的協同過濾框架，稱之為基于流形近鄰的協同過濾算法（MNCF）。

1相關工作

　　1.1符號約定

　　本文約定：

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

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

　　wi表示用戶i對用戶a評分預測時的權重；

　　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是路徑上相鄰節點之間的歐氏距離。當兩個用戶在同一個流形上時，其最小最大距離較小［13］。因此，它更好地反應了用戶之間的近鄰關系。

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

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

2流形近鄰協同過濾

　　2.1最小最大距離空間

　　距離空間是一種拓撲空間，其上的拓撲由指定的一個距離決定。

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

　　證明:

　　(1)由式（2）得:

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

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

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

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

　　（3）對任意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視覺距離

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

　　2.4MNCF

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

　　輸入：用戶的評分記錄。

　　輸出: 用戶對項目評分的預測。

　　（1)計算每個用戶已經評論過項目的評分均值。

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

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

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

　　（5）構造出（4）中無向有權圖的最小生成樹。

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

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

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

3實驗

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

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

　　MAE的值越小，說明準確率越高。

　　3.1不同加權方案對MNCF的影響

　　用戶i對用戶a評分權重為wi時對應的加權方案如表1所示。不同加權方案對MNCF的影響如圖1。

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

　　3.2不同協同過濾框架的比較

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

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

　　為了比較基于歐氏距離的協同過濾算法和基于最小最大距離的協同過濾算法，此處變化鄰居數，加權方案取01VD，記使用歐氏距離的協同過濾方案為ECF，得到的實驗結果如圖2所示。　

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

　　3.3不同流形鄰居數對實驗結果的影響

　　圖3不同鄰居數對預測性能的影響對于MNCF，讓鄰居數從100變化到900，加權方案取01VD得到的結果如圖3所示。

　　從圖3中可以看出，當流形近鄰數在訓練集用戶總數一半附近時，預測效果較好。

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

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

4結束語

　　本文介紹了最小最大距離在電影評分預測中的應用。實驗結果表明,本文提出的基于流形近鄰的協同過濾算法與目前的協同過濾算法相比性能有一定程度的提高。在Movie lens數據集上為達到最佳性能，MNCF所需的流形鄰居數目較多，主要原因應該是本文中的最小最大距離還是基于歐氏距離的。從實驗結果可以看出，使用最小最大距離優于歐氏距離。本文的方法還可以被應用到社區發現、傳感器網絡、圖像分割等領域。

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

　　參考文獻

　　［1］ 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.

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