劉艷，范永全

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

融合帕累托占優(yōu)的用戶協(xié)同過濾方法

劉艷，范永全

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

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

協(xié)同過濾；帕累托占優(yōu)；相似度計算；共同評分占比

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

0　引言

在網(wǎng)絡(luò)數(shù)據(jù)爆炸的時代，推薦技術(shù)讓用戶更快地找到想要的數(shù)據(jù)，讓用戶發(fā)現(xiàn)自己潛在的興趣和需求，這對于電子商務(wù)和社會網(wǎng)絡(luò)的應(yīng)用都是至關(guān)重要的。在眾多的推薦算法中，協(xié)同過濾推薦算法因其方法模型簡單，數(shù)據(jù)依賴性低，數(shù)據(jù)采集方便，推薦效果較優(yōu)成為主流的推薦算法。

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

基于內(nèi)存的協(xié)同過濾推薦算法又分為基于用戶和基于項目的協(xié)同過濾?；谟脩舻膮f(xié)同過濾推薦思想是計算用戶間的相似度，找到與目標用戶相似度高的鄰居用戶，將鄰居用戶感興趣的項目推薦給目標用戶?；陧椖康膮f(xié)同推薦思想是計算項目之間的相似度，推薦與目標用戶感興趣的項目相似度高的項目。

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

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

1　相關(guān)工作

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

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

我們定義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）}

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

sim（x，y）PCC=

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

2　融合帕累托占優(yōu)和改進相似度的協(xié)同過濾

2.1選取候選鄰居

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

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

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

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

我們定義目標用戶u的候選鄰居集合Cu，正式地，稱為代表目標用戶的非被占優(yōu)（non-dominated）用戶集。定義Du為被至少一個用戶關(guān)于目標用戶u占優(yōu)的被占優(yō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）：

定義：

布爾值函數(shù)：

距離：

Distance（rx，i，ry，i）=

鄰近度：

Proximity（rx，i，ry，i）=

影響力：

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

流行度：

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

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

2.3評分預(yù)測

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

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

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

3　實驗結(jié)果

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

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

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

實驗結(jié)果如圖1所示：

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

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

4　結(jié)語

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

[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]林耀進，胡學(xué)鋼，李慧宗.基于用戶群體影響的協(xié)同過濾推薦算法.情報學(xué)報，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，F(xiàn)AN 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-），女，四川廣安人，研究生研究生，研究方向為信息檢索、推薦系統(tǒng)

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