融合帕累托占優的用戶協同過濾方法

劉艷，范永全

（西華大學計算機與軟件工程學院，成都610065）

融合帕累托占優的用戶協同過濾方法

劉艷，范永全

（西華大學計算機與軟件工程學院，成都610065）

針對冷啟動條件下傳統基于用戶的協同過濾方法不能獲取充分代表目標用戶的鄰居用戶，采用帕累托占優理論預過濾掉那些低相似度的用戶。由鄰近度、影響力、流行度結合的PIP相似度計算方法結合共同評分占比的影響因素改進相似度計算方法。實驗采用Movielens100KB數據集，MAE作為評測指標，結果證明，融合帕累托占優和改進相似度的協同過濾算法MAE值對比只做過濾和只改進相似度有所改進。

協同過濾；帕累托占優；相似度計算；共同評分占比

教育部春暉計劃（No.Z2011088）、四川省教育廳重點項目（11ZB002）、四川省高校重點實驗室基金（No.SZJJ2012-027、No.SZJJ2014-033）、西華大學重點科研基金項目（No.Z1412620）

0　引言

在網絡數據爆炸的時代，推薦技術讓用戶更快地找到想要的數據，讓用戶發現自己潛在的興趣和需求，這對于電子商務和社會網絡的應用都是至關重要的。在眾多的推薦算法中，協同過濾推薦算法因其方法模型簡單，數據依賴性低，數據采集方便，推薦效果較優成為主流的推薦算法。

協同過濾推薦的主要思想就是根據已有的一群用戶的行為數據預測當前用戶對沒有見過的項目的喜好程度。協同過濾推薦可以分為基于內存的和基于模型的協同過濾推薦[1]。因為原始的評分數據保存在內存中，直接生成推薦結果，所以稱為基于內存的推薦。而基于模型的推薦會先通過機器學習等方法學習用戶行為數據建立用戶的偏好模型，運行算法時再將模型調入內存。基于模型的推薦方法使用的模型有貝葉斯模型、聚類模型、矩陣因子分解模型等。

基于內存的協同過濾推薦算法又分為基于用戶和基于項目的協同過濾。基于用戶的協同過濾推薦思想是計算用戶間的相似度，找到與目標用戶相似度高的鄰居用戶，將鄰居用戶感興趣的項目推薦給目標用戶。基于項目的協同推薦思想是計算項目之間的相似度，推薦與目標用戶感興趣的項目相似度高的項目。

基于用戶的協同過濾算法是一種早期的算法，最初介紹該算法是在GroupLens系統[2]用于推薦網絡新聞。用戶評分數據的稀疏性制約著推薦的質量，針對這一問題，文獻[3]中定義了用戶群體的概念并根據群體影響提出相應的兩條準則，這樣不僅考慮了用戶個體之間的相似性，也考慮了用戶所處群體之間的相似性。用戶評分項目數極少的用戶稱為冷用戶，也稱為冷啟動問題。計算相似度時，傳統的相似度計算方法如皮爾遜相關系數、余弦、均方差不能獲得足夠的有效相似用戶。文獻[4]提出了一種啟發式的相似度測量模型，模型由三個部分組成，有效解決冷啟動問題。文獻[5]提出在根據計算得出的相似度找K個近鄰之前采用帕累托占優理論預先過濾一些具有較小代表性的用戶，保留最有代表性的那些用戶。

本文采用文獻[5]提出的帕累托占優理論預過濾用戶得到候選用戶，然后采用文獻[4]提出的啟發式相似度測量模型加入共同評分占比的影響因素改進相似度測量方法，計算其他用戶與目標用戶的相似度，找到前K個相似度高的鄰居用戶。根據鄰居用戶做評分預測，計算MAE值。實驗證明，本文的方法對比只改進相似度計算方法和只做預過濾處理的方法MAE值都有所提高，方法是可行的。

1　相關工作

帕累托占優理論是用于解決多目標最優化問題[6]，從除開目標用戶的所有其他用戶中尋找能準確代表目標用戶的用戶作為候選鄰居用戶。若x'∈D，且在D中不存在比x'更優越的解x，則稱x'為多目標最優問題的Pareto最優解，也稱有效解。D就是除了目標用戶以外的其他用戶，x'就是與目標用戶相關的鄰居用戶。一般來說，多目標優化問題不存在唯一的最優解，所有可能的解的集合都稱為Pareto解集，也稱非劣解集。

在推薦系統領域，用戶對項目的興趣度的測量包括準確度、新穎性、多樣性，推薦系統推薦的項目通常都只選取一種測量條件，同時滿足這三個條件可能會導致目標沖突的問題，文獻[7]提出帕累托效率的概念用于解決這個沖突問題。根據用戶回答系統提出的問題這樣的簡短對話所得出的答案做出推薦，稱為對話推薦系統。文獻[8]采用帕累托占優理論用于選擇向用戶提供的問題。對話推薦系統是基于內容的推薦算法的實例，在面向用戶的電子商務中應用廣泛。而在本文中我們將帕累托占優理論融合到協同過濾算法中。

我們定義m個用戶對n個項目進行評分，用戶集合為U，項目集合為I，評分值集合V，用戶u的評分項目集合為Ru，項目i的評分項目集合為Ti。

U={u∈N|1≤u≤m}

I={i∈N|1≤i≤n}

V={v∈N│min≤v≤max}∪{∞}

其中max和min表示評分的最大值和最小值，∞表示沒有評分。

Ru={i∈I，v∈V|ru，i=（i，v）}

Ti={u∈U，v∈V|ti，u=（u，v）}

常用的相似度計算方法有：皮爾遜相關系數（Pearson Correlation Coefficient）（1）、余弦（Cosine）（2）、均方差（Mean Squared Difference）（3）。

sim（x，y）PCC=

其中，Ix，y表示用戶x與用戶y共同評分的項目集合，|Ix，y|表示共同評分項的數目，rx，i和ry，i，表示用戶x和用戶y對項目i的評分，rx和ry表示用戶x和用戶y的平均評分。

2　融合帕累托占優和改進相似度的協同過濾

2.1選取候選鄰居

定義Iu={i∈I，v∈V，v≠∞|ru，i=（i，v）}為目標用戶u已評分項目集合。

定義d（rx，i，ry，i）為用戶x和用戶y對項目i的絕對差異。

當滿足表達式（5）時，我們稱用戶x比用戶y關于用戶u占優，用戶y被用戶x關于用戶u占優:

從概念上說，代表目標用戶的被占優用戶相比于占優用戶沒有展現更大的相似性，他們展現了較低的相似性。因此我們就將被占優用戶舍棄。

我們定義目標用戶u的候選鄰居集合Cu，正式地，稱為代表目標用戶的非被占優（non-dominated）用戶集。定義Du為被至少一個用戶關于目標用戶u占優的被占優用戶集合。Cu滿足表達式（6）：

Cu∈U，u?U，Cu=U-（Du∪{u}），?y∈Du，?x∈Cu|x> yu（6）

2.2計算相似度

文獻[4]提出的新的相似度測量由鄰近度（Proximi-ty）、影響力（Impact）、流行度（Popularity）三個部分組成。

用戶x和用戶y之間的相似度為sim（x，y）PIP，計算如表達式（7）：

定義：

布爾值函數：

距離：

Distance（rx，i，ry，i）=

鄰近度：

Proximity（rx，i，ry，i）=

影響力：

表示項目i對所有用戶的平均評分

流行度：

共同評分項的占比是一個重要的因素，因此我們引入Jaccard系數，如表達式（16）：

因此改進后的相似度計算方法如表達式（17）：

2.3評分預測

從目標用戶u的候選鄰居集合Cu中選取k個近鄰，得到K近鄰集合Ku滿足表達式（18），

令Gu，i={l∈Ku|rl，i≠∞}為Ku中對項目i進行了評分的用戶集合。

預測目標用戶u對項目i的評分如表達式（19）：

3　實驗結果

實驗數據采用Movielens 100KB數據集，包含943名用戶對1682部電影超過10萬條評分。令Au={i∈I|ru，i≠∞∧pu，i≠∞}為用戶u預測的項目的集合。

采用MAE作為準確性度量標準，則用戶u的MAE計算公式如表達式（20）：

算法的MAE值計算如表達式（21）：

實驗結果如圖1所示：

圖1　不同方法在不同k值下的MAE值

從圖中可以看出本文采用的預過濾處理結合改進的相似度計算方法的MAE值相比其他方法是最小的，改進的相似度的方法相比傳統的PCC、MSD、COS方法都較小。傳統的方法之間MAE值差別不大。隨著鄰居數k的變化，MAE值不斷減小，但從120以后，變化趨于平緩，比較穩定了。因此本文的方法和傳統的協同過濾方法相比較，推薦質量有所提高。

4　結語

傳統的基于用戶的協同過濾方法在選取目標用戶的鄰居用戶時不夠代表性，因此本文采用帕累托占優理論預先過濾掉那些低相似度的用戶。由鄰近度、影響力、流行度結合的PIP相似度計算方法結合共同評分占比的影響因素改進相似度計算方法。預過濾處理結合改進的相似度計算方法提高了推薦質量。采用預過濾處理，增加了運行時間，接下來將會對如何提高算法的運行時間進行研究。

[1]Su X，Khoshgoftaar TM.A Survey of Collaborative Filtering Techniques[J].Advances in Artificial Intelligence，2009，2009:4

[2]Resnick P，Iacovou N，Suchak M，et al.GroupLens:an Open Architecture for Collaborative Filtering of Netnews[C].Proceedings of the 1994 ACM Conference on Computer Supported Cooperative Work.ACM，1994:175~186

[3]林耀進，胡學鋼，李慧宗.基于用戶群體影響的協同過濾推薦算法.情報學報，2013，32（3）:299~305

[4]Ahn H J.A New Similarity Measure for Collaborative Filtering to Alleviate the New U ser C old-S tarting P roblem[J].Information Sciences，2008，178（1）:37~51

[5]Ortega F，Sánchez J，Bobadilla J，etal.Improving C ollaborative F iltering-B ased R ecommender S ystems R esults U sing Pareto D ominance[J].Information Sciences，2013，239（4）:50~61

[6]Zitzler E，Laumanns M，Thiele L.SPEA2:Improving the Strength Pareto Evolutionary Algorithm[J].Tik Swiss Federal Institute of Technology，2001

[7]Ribeiro M T，Ziviani N，Moura E SD，et al.Multiobjective Pareto-Efficient Approaches for Recommender Systems[J].ACM Transactions on Intelligent Systems and Technology（TIST），2014，5（4）:53

[8]TrabelsiW，Wilson N，Bridge DG，etal.Comparing Approaches to Preference Dominance for Conversational Recommenders[C]，in: 22th IEEE International Conferences on Toolswith Artificial Intelligence（ICTAI’10），2010:113~120

Collaborative Filtering;Pareto Dominance;Similarity Measure;Proportion of Common Ratings

User-Based Collaborative Filtering Using Pareto Dom inance

LIU Yan，FAN Yong-quan

（School of Computer and Software Engineering，Xihua University，Chengdu 610065）

The traditional collaborative filteringmethods can not select the representative users as neighbors insufficiently of active user in the condition of cold starting.Uses Pareto dominance to perform a pre-filtering process eliminating low similarity with the active user.Improves sim ilarity measure by considering the influence of proportion of common ratings,combined with the PIP similarity measure which composed of proximity,impact,and popularity.Uses MovieLens-100K as the data sets,MAE asmetrics.The experimental results show that themethod combining with the pre-filtering processing and improved similarity measure is improved in the value of MAE compared to only using pre-filtering or improved similaritymeasure.

1007-1423（2015）16-0011-04

10.3969/j.issn.1007-1423.2015.16.003

劉艷（1990-），女，四川廣安人，研究生研究生，研究方向為信息檢索、推薦系統

收謝日期：2015-04-142015-06-03