基于流形近鄰的協同過濾算法*

段廷銀, 趙東明

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

基于流形近鄰的協同過濾算法*

段廷銀, 趙東明

(鄭州大學 信息工程學院， 河南 鄭州 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的評分；

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

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

1.2 最小最大距離

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

(1)

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

(2)

2 流形近鄰協同過濾

2.1 最小最大距離空間

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

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

證明:

(1)由式(2)得:

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

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

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

(3)對任意i，k和j，如果k∈Pij，則：

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

=ρ(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.4 MNCF

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

輸入：用戶的評分記錄。

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

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

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

(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]。

(3)

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

也許是動作太快，等這一切結束時，周教授幾個還張著大嘴愣怔著。只有可蔓不驚不慌，正像一個長官似地在那教訓一個長著娃娃臉的八路軍。可蔓拍著娃娃兵的帽子說，是不是新兵蛋子嘛，怎么連駁殼槍都不會打嘛，要平端著打知道不？

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

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

表1 權重與加權方案對應關系

圖1 不同加權方案對MNCF的影響

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

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

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

表2 不同框架性能對比

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

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

圖2 ECF和MNCF預測效果對比

從圖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 最佳流形近鄰數目附近的MAE

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.

[4] Luo Si,Rong Jin. Flexible mixture model for collaborative filtering[C]. Proc. of the 20th Int’l Conf. on Machine Learning,2003: 704-711.

[5] PORTEOUS I, BART E, WELLING M. Multi-HDP: a non parametric Bayesian model for tensor factorization[C]. Proc. of the 23rd National Conf. on Artificial Intelligence, 2008:1487-1490.

[6] 董立巖，劉晉禹，蔡觀洋，等.基于抽樣近鄰的協同過濾算法[J].吉林大學學報(理學版)，2014,52(4):799-782.

[7] 趙琴琴，盧凱，王斌.SPCF:一種基于內存的傳播式協同過濾算法[J].計算機學報，2013,36(3)：671-676.

[8] 叢曉琪，楊懷珍，劉枚蓮.基于時間加權的協同過濾算法[J].計算機應用與軟件，2009,26(8):120-121.

[9] 吳成超，王衛平.考慮用戶興趣變化的概率隱語義協同推薦算法[J].計算機系統應用，2014，23(5):162-166.

[10] 劉海鷗，房俊峰.面向云計算的大數據協同過濾并行推薦方法[J].電子商務，2014(3):58-68.

[11] 李改，潘嶸，李章鳳，等.基于大數據集的協同過濾算法的并行化研究[J].計算機工程與設計，2012，33(6)：2437-2441.

[12] 萬年紅. 基于云模型的協同過濾推薦算法[J]. 計算機系統應用, 2015(5)：140-146.

[13] KIM K H, CHOI S.Neighbor search with global geometry: a minimax message passing algorithm[C]. Proceedings of the 24th International Conference on Machine Learning,2007 :401-408.

[14] CARROLL J D. “Minimax length links” of a dissimilarity matrix and minimum spanning trees[J]. Psychometrika, 1995, 60(3): 371-374.

[15] SARWAR B, KARYPIS G, KONSTAN J, et al. Item-based collaborative filtering recommendation algorithms[C].Proceedings of the 10th International Conference on World Wide Web. ACM, 2001: 285-295.

[16] 熊忠陽，劉芹，張玉芳，等.基于項目分類的協同過濾改進算法[J].計算機應用與研究，2012，29(2):493-496.

Collaborative filtering based on manifold neighbors

Duan Tingyin， Zhao Dongming

(School of Information Engineering, Zhengzhou University, Zhengzhou 450001, China)

The collaborative filtering technology predicts an active user’s rating to an item based on his historical interests. Traditional user-based collaborative filtering takes the Euclidean distances as input to find the neighbors of an active user. However, the Euclidean distance cannot reflect the relationships well. A novel method which takes min-max distance based on the Euclidean distances to find an active user’s neighbors is introduced and called manifold neighbors. According to the results of experiments, MNCF can outperform state-of-the-art collaborative filtering algorithms to some extent.

manifold neighbor; metric space; collaborative filtering; vision distance; min-max distance; recommendation system

國家自然科學基金(61572444)

TP391.3

A

1674- 7720(2016)03- 0078- 03

段廷銀, 趙東明. 基于流形近鄰的協同過濾算法[J].微型機與應用，2016,35(3)：78- 80，91.

2015-09-15)

段廷銀(1987-)，通信作者，男，碩士研究生，主要研究方向：數據挖掘。E-mail：clickyeah@yeah.net。