段廷銀, 趙東明

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

基于流形近鄰的協(xié)同過濾算法*

段廷銀, 趙東明

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

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

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

0 引言

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

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

1 相關(guān)工作

1.1 符號(hào)約定

本文約定：

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

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

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

1.2 最小最大距離

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

(1)

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

(2)

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

2.1 最小最大距離空間

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

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

證明:

(1)由式(2)得:

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

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

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

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

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

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

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

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

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

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

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

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

(5)構(gòu)造出(4)中無向有權(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%的測試集。

為了評(píng)估MNCF，本文采用了平均絕對(duì)值誤差(MAE)[15]。

(3)

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

也許是動(dòng)作太快，等這一切結(jié)束時(shí)，周教授幾個(gè)還張著大嘴愣怔著。只有可蔓不驚不慌，正像一個(gè)長官似地在那教訓(xùn)一個(gè)長著娃娃臉的八路軍?？陕闹尥薇拿弊诱f，是不是新兵蛋子嘛，怎么連駁殼槍都不會(huì)打嘛，要平端著打知道不？

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 權(quán)重與加權(quán)方案對(duì)應(yīng)關(guān)系

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

從圖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é)同過濾框架的比較

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

表2 不同框架性能對(duì)比

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

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

圖2 ECF和MNCF預(yù)測效果對(duì)比

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

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

圖3 不同鄰居數(shù)對(duì)預(yù)測性能的影響

對(duì)于MNCF，讓鄰居數(shù)從100變化到900，加權(quán)方案取01VD得到的結(jié)果如圖3所示。

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

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

從圖4中可以看出，當(dāng)流形近鄰數(shù)在訓(xùn)練集用戶總數(shù)一半附近時(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 最佳流形近鄰數(shù)目附近的MAE

4 結(jié)束語

本文介紹了最小最大距離在電影評(píng)分預(yù)測中的應(yīng)用。實(shí)驗(yàn)結(jié)果表明,本文提出的基于流形近鄰的協(xié)同過濾算法與目前的協(xié)同過濾算法相比性能有一定程度的提高。在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ù)以千萬計(jì)的用戶，在傳統(tǒng)的單機(jī)系統(tǒng)上快速求解出最小最大距離顯得不可行。然而，隨著大數(shù)據(jù)時(shí)代的到來，基于MapReduce的Hadoop與Spark，旨在分布式處理實(shí)時(shí)數(shù)據(jù)的Storm，以及分布式大規(guī)模圖像處理系統(tǒng)Pregel等大數(shù)據(jù)平臺(tái)也得以飛速發(fā)展。接下來的工作是針對(duì)本文中的算法在Pregel和Spark GraphX等大數(shù)據(jù)平臺(tái)上進(jìn)行集群算法的研究與實(shí)現(xiàn)。

[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] 董立巖，劉晉禹，蔡觀洋，等.基于抽樣近鄰的協(xié)同過濾算法[J].吉林大學(xué)學(xué)報(bào)(理學(xué)版)，2014,52(4):799-782.

[7] 趙琴琴，盧凱，王斌.SPCF:一種基于內(nèi)存的傳播式協(xié)同過濾算法[J].計(jì)算機(jī)學(xué)報(bào)，2013,36(3)：671-676.

[8] 叢曉琪，楊懷珍，劉枚蓮.基于時(shí)間加權(quán)的協(xié)同過濾算法[J].計(jì)算機(jī)應(yīng)用與軟件，2009,26(8):120-121.

[9] 吳成超，王衛(wèi)平.考慮用戶興趣變化的概率隱語義協(xié)同推薦算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2014，23(5):162-166.

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

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

[12] 萬年紅. 基于云模型的協(xié)同過濾推薦算法[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用, 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] 熊忠陽，劉芹，張玉芳，等.基于項(xiàng)目分類的協(xié)同過濾改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用與研究，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

國家自然科學(xué)基金(61572444)

TP391.3

A

1674- 7720(2016)03- 0078- 03

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

2015-09-15)

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