G-S模型下的協同過濾算法

顧 凱,劉建明

G-S模型下的協同過濾算法

顧 凱1,劉建明2

(1.桂林電子科技大學電子工程與自動化學院,廣西桂林 541004; 2.桂林電子科技大學計算機科學與工程學院,廣西桂林 541004)

針對協同過濾算法忽視供應商偏好、存在稀疏矩陣導致準確率低的現象,提出一種改進的協同過濾算法。利用改進的相似度計算方法填充評分矩陣,計算目標用戶的評分,將目標用戶評分作為G-S算法的輸入項,得到消費者、供應商的匹配結果。仿真結果表明,算法具有較高的滿意度和準確率。

協同過濾算法;滿意值;Pareto最優;信息熵

推薦系統已廣泛應用在電子商務系統中,它能為消費者找到較為準確的購買目標,大大提升了供應商的銷售額[1]。旅游網站Priceline消費者主動出價的模式考慮到了雙方的利益。

協同過濾算法是應用最為廣泛的推薦算法。為了解決該算法中出現的稀疏矩陣,有學者提出利用評分均值填充的算法,還有學者提出一種基于項目評分的填充算法[2]。

隨著消費者、供應商的快速增加,而用戶-項目評分矩陣的數據嚴重稀疏,傳統的填充方法計算得到的預測評分不準確,出現推薦準確率低的問題[3],同時傳統推薦算法還存在忽視供應商需求的問題。鑒于傳統的填充方法得到的預測評分不夠準確,提出一種綜合填充算法,該算法考慮了共同評分數量、評分背景兩者對相似度的影響。為解決忽視供應商利益的問題,引入Pareto最優的概念,在電子商務平臺上, Pareto最優狀態要求同時考慮消費者和供應商的滿意值。G-S算法能求Pareto最優解,其最早出現在Shapley的基礎理論研究[4-5],后來Roth將其應用于市場實踐[6-7]。G-S算法是針對雙方數量相同的情況,因此提出一種改進的G-S算法來解決電子商務中消費者的數量要遠大于供應商的問題。

1 G-S模型

G-S算法應用在雙邊匹配市場中,照顧到參與雙方的利益,在理論和實踐中被驗證具有穩定性。

G-S的流程用如下語言表示:

while 消費者集合B中存在消費者b_i

在b_i還未發申請的供應商中選擇滿意值bigf最高的一個供應商s_j發出意向

if s_j未收到項目申請or意向個數小于庫存then

b_i與s_j結合組成(b_i,s_j)

else//s_j已經與b_k組成組合(b_k,s_j)

if g(s_j,b_k)＞g(s_j,b_i)//s_j更喜歡b_k

then

b_i進去下一輪循環

else b_i與s_j組成組合(b_i,s_j)

b_k變成被拒絕者,進入下一輪循環

//供應商s_j更喜歡消費者b_i

end if

end if

end while

最終返回的配對集合矩陣S是一個穩定的匹配,此算法的關鍵是要得出消費者的偏好,將協同過濾算法產生的推薦作為G-S算法的輸入內容。

2 推薦算法的實現

2.1 傳統相似度

求用戶對項目的評分,關鍵是求相似度。從相似度角度看,流行的推薦算法包括基于內容推薦算法和基于協同過濾的推薦算法。內容推薦的特點是匹配準確、推薦更多新項目,但存在覆蓋率低、項目特征提取困難等問題。協同過濾包括基于用戶的協同過濾和基于項目的協同過濾。結合用戶購買行為的特點,采用基于項目的協同過濾進行預填充,采用基于用戶的協同過濾計算目標用戶得分。項目之間的相似度采用修正的余弦相似度計算效果較好[8],計算公式為:

其中:i、j分別為不同的項目;ˉru為在評分矩陣中用戶的平均評分;rui、ruj分別為同一用戶u對不同項目i、j的評分。

用戶對項目的評分公式為:其中:S(i,k)為與項目i最相似的k個項目集合;N (u)為有過評分的項目集合或對有過評分的用戶集合。

2.2 傳統方法存在的問題

表1為用戶對項目的評分矩陣。從表1可見,用戶U2缺少對項目I1的評分,但由項目I1、I3之間相似的特性可知,U2對項目I1的評分為3。因此,可先根據項目相似度進行填充。

表1 評分矩陣Tab.1 The matrix of rate value

因為存在稀疏矩陣,導致相似度計算不準確,為此,人們進行了大量的研究,常用的方法是對評分矩陣進行預填充,設定一個固定的缺省值,取用戶或項目的平均分,文獻[9-10]提出了一種信任度傳播的評分填充算法,文獻[2]提出了基于項目評分預測的協同過濾推薦算法,文獻[11]提出了基于概率知識的評分填充算法。這些方法均未考慮項目屬性出現的情境,比如在價格高的項目中,高價格就沒有什么代表性,計算的相似度自然不準確;如果周圍的項目都是一種品牌,出現了其他品牌就非常容易區分,計算的相似度自然對類的區分很有貢獻,文獻[12]提出一種基于用戶評分差異的協同過濾算法。

2.3 改進的基于項目相似度填充

1948年,香農提出了“信息熵”的概念,用數學語言闡明了概率與信息冗余度的關系。這里用信息熵表示信息的穩定性,若信息分布越均勻,則信息熵越大,若屬性越集中,則信息熵越小。

在相似度的基礎上,加入信息熵的概念,相似度的計算結果會更加準確。假設項目的一個屬性f有多個種類,多種取值屬性值vfm構成屬性集合V(f) ={vf1,vf2,…,vfm}。對于離散的項目屬性容易處理,而對于連續型的屬性,要為每一區間的屬性規定相應的名稱。以項目的價格為例,把價格區間劃分為奢侈、昂貴、經濟、便宜4類,相應的取值為:

其中:n(vfm)為屬性fm出現的次數;n為項目的數量。項目價格的信息熵為:

其中p(fi)為fi出現的概率。信息熵越大,表示價格4種屬性分布越平均,項目價格屬性便于區分,否則,價格屬性沒有區分的必要。改進后的相似度為:

其中:p為項目數量;s1(Ii,Ij)∈[0,1];

S(Ii,Ij,f)表示項目Ii和Ij屬性值是否相同,若相同為1,否則為0;t(Ii,f)和t(Ij,f)表示項目Ii和Ij,的屬性f值,s1越大,項目的此屬性越有區分力,說明在此情境下此屬性越能代表2種項目的相似度。

項目相似度還應考慮擁有相同屬性的用戶數量。表1中項目I1和I3共同評分的用戶數量更多,它們可能擁有更高的相似度,而根據傳統的相似度求解方法,I2、I4的相似度則更高,稀疏矩陣導致忽視共同評分數量的現象更加明顯,因此求相似度應該考慮共同評分的用戶數量。受Jaccard系數啟發,加權共同評分數量的相似度:

式(7)中分子表示兩項目有共同評分的用戶數量,分母表示用戶總數。s2在[0,1]內越大,表示共同評分的數量越大,即2個消費者的相似度越高。

對s1、基于相同項目評分數量的s2及基于項目評分的修正的余弦相似度進行加權,得到最后的相似度公式為:

其中,α和β為調節系數,可調節修正的余弦相似度、s1系數和基于共同評分數量的相關系數三者的比重, α∈[0,1]。

根據最終的相似度系數s4對未評分的項目進行填充,

2.4 基于用戶鄰域相似度的評分預測

人的行為受社會化的影響[13],在評分填充后計算用戶相似度,根據式(2)計算目標用戶對項目的預測評分rui,再根據評分高低產生推薦。

3 在改進的G-S框架下雙邊算法的實現

3.1 雙邊算法的實現步驟

傳統推薦算法忽略供應商的偏好,受雙邊算法的啟發,利用改進的G-S算法解決此問題。假設有m個消費者、n個供應商,項目有f個屬性。推薦算法在G-S框架下實現的具體步驟為:

1)改進的協同過濾算法得到的推薦作為G-S算法中消費者的偏好。

2)消費者給出相關偏好rb,并根據項目屬性ps計算適合值bijgf,加入消費者對屬性的權限值wif,得出滿意值bijg,系統按滿意值高低依次向供應商發出意向。

3)根據供應商要求rs和消費者屬性pb計算Sji,加入購買數量計算總滿意度Gji。供應商對有意向的買家進行排序得到矩陣O。若賣家有庫存,則預留消費者;若無庫存,則拒絕排序最靠后的買方,被拒絕的買方向下一個志愿發出意向。

4)依次類推,直至向所有的買方都發出意向,一輪匹配結束。

5)下一輪循環開始,直至完成所有匹配或達到規定的循環次數。

3.2 消費者滿意值

軟約束條件指的是在一定的范圍內都可以接受的條件,通過計算滿意值和滿意度判定偏好程度。而軟約束有越大越好型和越少越好型,比如項目的配置和價格。消費者對項目屬性可分以下幾種:

1)越大越好型。消費者選擇項目時希望項目的配置、質量越高越好。引入適合值函數bijgf表示消費者i對于供應商j的項目g的屬性f的滿意度,用-1表示供應商的項目屬性pjgf小于消費者對該項目屬性的最低要求rif,min,1表示供應商的項目屬性pjgf大于等于消費者的最高要求rigf,適合值為:

2)越少越好型。消費者對于項目的價格越低越好,用-1表示供應商的項目屬性高于消費者對于該項目屬性的上限rigf,max,1表示供應商的項目的屬性值小于消費者的下限要求,適合值為:

消費者根據自己的滿意值,由大到小依次向心儀的供應商發出購買意向,滿意值計算式為:

3.3 供應商滿意值

供應商同樣對消費者有偏好,他們往往關心消費者的信用,引入適合值Sjigf表示供應商對消費者的偏好,用1表示消費者的信用度pigf大于供應商的最好心理值rigf,-1表示消費者的信用度小于供應商的最差心理值rjgf,min,供應商滿意值為:

3.4 滿意度

匹配過程會出現一個供應商對應多個消費者,購買數量作為一個權值參與計算總滿意值Gji,并按Gji大小對消費者進行排序。供應商把對自己有意向的消費者按照偏好矩陣O進行排序,供應商庫存充足,則接受所有消費者;一旦出現需求大于庫存m的情況,供應商就要剔除排序靠后的消費者,被剔除的消費者進入下一輪循環。滿意度計算式為:

其中:

4 仿真實驗與分析

4.1 實驗評價標準

采用平均絕對誤差EMA作為評價推薦算法預處理階段的指標,

定義參與率為最終匹配方案與推薦系統列表之間對應的比值:

其中:cb為消費者參與度;cs為供應商參與度;na為G-S算法匹配成功的項目數量;ns為預推薦給消費者的項目數量;nb為消費者總數。

4.2 仿真數據

采用MovieLens數據集,其包含用戶對自己看過的電影進行評分,分值為1~5。采用小規模庫,有943個用戶對1682部電影作的10 000次評分。為了驗證推薦算法的準確性,實驗分別在10、20、30、40四種鄰居規模上進行,將傳統的協同過濾推薦算法、基于項目評分相似度填充的算法與改進的算法進行對比。首先對數據進行隨機采集,平均分成8份,選取其中的7份作為訓練集,1份作為測試集,循環3次,取平均值作為結果。采用α、β均為0.1的情況下對算法進行試驗。

為驗證算法能同時提高消費者和供應商的滿意度,設定消費者的偏好內容是項目價格,供應商更在意消費者的信用度,通過將各自的要求與對方的屬性比較,便可計算出偏好程度。匹配方案加入先前得出的偏好程度,便可計算出最終的滿意值。根據改進的G-S算法的要求,假設有9個消費者和3個供應商。表2為供應商對消費者信用的要求和項目屬性,表3為消費者對項目的要求和自身信用指數。

表2 供應商對信用的要求和項目價格屬性Tab.2 The credit requirement of suppliers and commodity price

表3 消費者對項目的要求和自身信用指數Tab.3 The commodity requirement of consumers and credit value

計算得到的消費者對供應商滿意值如表4所示,供應商對消費者滿意值如表5所示。

表4 消費者對供應商的滿意值Tab.4 The consumers satisfaction for supplies

4.3 仿真結果

4.3.1 預處理階段推薦算法準確性比較

在不同的鄰居規模下,改進算法與經典協同過濾算法(CCF)和基于項目評分相似度填充的協同過濾(CFBRF)的EMA如圖1所示。

圖1 3種算法EMA對比Fig.1 EMAof three algorithms

4.3.2 匹配質量比較

觀察用戶滿意度指標,在同樣的參與者、偏好相同的情況下,在第1輪匹配中匹配次數從1到9逐漸增加時,供應商和消費者的滿意值如圖2所示。從圖2可看出,隨著匹配次數的增加,消費者的滿意值在增加。改進的算法相較于傳統的協同過濾算法,供應商的滿意值也在增加,因為算法滿足消費者優先選擇的情況下,由供應商按照其偏好對消費者進行篩選,最終得到匹配方案是雙向選擇的結果。總體來看,滿意度呈上升趨勢,保持雙方較高的滿意值,能滿足雙方的需求。

圖2 供應商和消費者的滿意值Fig.2 The satisfaction of supplies and consumers

比較匹配次數從1到9逐漸增加的情況下,供應商和消費者的參與度如圖3所示。從圖3可看出,隨著匹配次數的增加,雙方參與度都不斷上升。

圖3 供應商和消費者的參與度Fig.3 The participation of supplies and consumers

為驗證算法的有效性,算法在第1輪到第5輪的供應商與消費者的參與度如圖4所示。從圖4可看出,在第2輪匹配中,消費者和供應商的參與度達到最高,匹配次數繼續增加,在供應商參與度幾乎不變的情況下,消費者的參與度會下降。由此可見,選擇合適的匹配次數很重要,一味增加匹配次數不但增加內存和時間的開銷,而且推薦的效果也會下降。

圖4 第1~5輪供應商與消費者的參與度Fig.4 The participation of supplies and consumers from first to fifth matching

5 結束語

針對傳統的協同過濾算法存在稀疏矩陣及忽視供應商偏好的問題,提出一種G-S框架下的推薦算法。利用改進的基于項目相似度對矩陣進行填充,能夠緩解稀疏矩陣造成的問題,提高推薦準確性;G-S算法能夠充分考慮到供應商和消費者雙方的偏好,增加算法的穩定性。仿真結果表明,改進的算法從算法的準確性和滿意值上,都能提高用戶體驗,有利于吸引參與者加入到電子交易平臺。但是,推薦準確度還存在很大的提升空間,將社交網絡的概念引入也是一個重要的方向。

[1] 楊博,趙鵬飛.推薦算法綜述[J].山西大學學報:自然科學版,2011,34(3):337-350.

[2] 鄧愛林,朱揚勇,施伯樂.基于項目評分預測的協同過濾推薦算法[J].軟件學報,2003,14(9):1621-1628.

[3] 彭石.基于用戶興趣和項目特征的協同過濾推薦算法研究[D].長沙:中南大學,2012:14-18.

[4] Gale D,Shapley L S.College admissions and the stability of marriage[J].The American Mathematical Monthly, 1962,69(1):9-15.

[5] Shapley L S.On market games[J].Journal of Economic Theory,1969,1:9-25.

[6] Roth A E.Incentive compatibility in a market with indivisible goods[C]//Economics Letters,1982:127-132.

[7] Roth A E,Sonmez T,Utuuver M.Pairwise kidney exchange[J].Journal of Economics Theory,2005,125: 127-132.

[8] 龔亮.推薦系統實踐[M].北京:人民郵電出版社,2012: 59-61.

[9] 曾賽.基于社交網絡信任模型的項目推薦系統[D].廣州:華南理工大學,2012:33-39.

[10] 周靜.基于信任的協同過濾推薦算法研究[D].秦皇島:燕山大學,2013:27-32.

[11] 周軍鋒,湯顯,郭景峰.一種優化的協同過濾推薦算[J].計算機研究與發展,2004,40(10):1843-1847.

[12] 曹建新,楊寧,夏培勇.一種基于改進信息熵的協同過濾算法[J].微計算機信息,2012,40(10):181-183.

[13] 蘇彥秋.SNS中意見領袖對消費者購買意向的影響研究[D].大連:東北財經大學,2013:18-19.

編輯:翁史振

A collaborative filtering algorithm on G-S model

Gu Kai1,Liu Jianming2
(1.School of Electronic Engineering and Automation,Guilin University of Electronic Technology,Guilin 541004,China; 2.School of Computer Science and Engineering,Guilin University of Electronic Technology,Guilin 541004,China)

The absence of supplies’interest and the execution efficiency of recommendation technology based on collaborative filtering algorithm is relatively low with the data sparsity,so a modified collaborative filtering algorithm is proposed.Firstly,it prefills the rating matrix by the approved algorithm and makes sure of the users’rates.Then the improved G-S algorithm for consumers and sellers provides appropriate match on both sides according to the recommended goods based on the collaborative filtering algorithm.The experimental results show that the algorithm has high execution and satisfaction.

collaborative filtering algorithm;satisfaction;Pareto principle;information entropy

TP391

A

1673-808X(2015)05-0395-06

2015-03-09

國家自然科學基金(61262074)

劉建明(1975-),男,廣西桂林人,教授,博士,研究方向為計算機及通信網絡組網工程。E-mail:jmliu_gl@sina.com引文格式:顧凱,劉建明.G-S模型下的協同過濾算法[J].桂林電子科技大學學報,2015,35(5):395-400.