結合用戶社區和評分矩陣聯合社區的推薦算法研究

文 凱,朱傳亮,何少元

1(重慶郵電大學 通信與信息工程學院,重慶 400065) 2(重慶郵電大學 通信新技術應用研究中心,重慶 400065) 3(重慶信科設計有限公司,重慶 401121)E-mail:cquptzcl@yeah.net

1 引 言

隨著Web2.0的發展,用戶間的社交網絡扮演著越來越重要的地位,用戶之間可以建立不同程度的信任關系,用戶的購買行為也不僅僅是依靠用戶自身的興趣愛好了,更多地會考慮到用戶所信任的其他用戶的意見,社交網絡分析表明,用戶和所信任的朋友在很大程度上有著相似的偏好,因此一些基于社交網絡的算法被提出[1,2],用來改善推薦精度,其中傳統的基于社交網絡的推薦算法采取一種信任評估的模型,考慮用戶間的直接信任關系.文獻[3]介紹了一種SocialMF算法,該算法是在社交推薦中比較常用的算法,將信任傳播機制融合進概率矩陣分解框架中;文獻[4]提出將用戶信任和張量分解技術結合起來.文獻[5]提出了一種基于用戶信任的矩陣分解技術Trust SVD,在SVD++算法的基礎上進一步結合顯示及隱式用戶信任對推薦的影響.

隨著社交網絡的不斷發展,社交網絡越來越龐大,社交數據越來越稀疏,導致了推薦結果準確度的下降.同時,隨著數據量的越來越大,傳統的推薦算法在可擴展性上已經不足以支撐現有的數據量,因此一些基于社區的算法被提出用來改善推薦的可擴展性[6,7].有的挖掘用戶社區,有的挖掘項目社區,比如文獻[8]首先利用基于密度的聚類算法將物品進行聚類,然后在物品聚類簇中利用加權Slope one算法進行評分預測;文獻[9]提出一種基于用戶屬性的聚類算法,定義了用戶之間的偏好距離,根據偏好距離進行聚類;文獻[10]提出一種結合SVD的推薦方法,推薦時在目標用戶的社區內利用隨機游走算法為用戶做出推薦;文獻[11]提出一種融合拓撲勢的層次化聚類算法,綜合考慮網絡拓撲結構和社交網絡屬性信息,利用協同過濾預測評分.

同時也有一些學者提出同時將用戶和物品進行聚類,這樣的聚類方式稱為聯合聚類(co-clustering),文獻[12]通過聯合聚類將用戶和項目同時劃分到社區中,用戶或項目只屬于一個社區;文獻[13]提出了一種混合推薦算法,將用戶和物品同時進行聚類并學習用戶和物品的屬性,去解決冷啟動問題;文獻[14]提出一種多類聯合聚類,通過迭代方式獲取用戶和產品的聯合聚類結果,然后通過統一的框架利用傳統的協同過濾算法進行推薦.

然而以上提出的這些聚類方法雖然提高了推薦的效率,但都只考慮了單一社區結構,所以推薦精度不高.針對上述問題,本文綜合考慮用戶社區結構和聯合社區結構,首先基于社交信息和評分信息提出了一種新的用戶間相似度度量方法,利用該度量方法對用戶進行聚類從而發現用戶社區;之后從用戶和物品兩個維度進行聯合聚類,得到一個用戶-物品的聯合社區.最后結合這兩個社區結構,將用戶社區結構融入到面向聯合社區的矩陣分解模型中從而進行推薦.

2 結合用戶社區結構和評分聯合社區的推薦模型

2.1 符號表示與框架描述

設U={u1,u2,…um}和V={v1,v2,…vn}分別表示用戶和物品的集合,其中m和n分別表示用戶和物品的數量,設R∈Rm×n表示用戶-項目評分矩陣,設T∈Rm×m表示用戶之間的社交關系矩陣,在矩陣T中,當T(a,b)=1時表示用戶ua信任用戶ub.

圖1是本文聯合推薦模型的一個整體的框架圖,從圖中可以看到,整個框架的輸入為用戶-項目評分數據和用戶社交網絡數據,整個過程可以分為以下4步:

圖1 矩陣分解推薦模型圖Fig.1 Matrix decomposition recommendation model

Step 1.分別利用用戶的評分數據和社交網絡數據挖掘出用戶間的評分相似性和用戶間的信任關系;

Step 2.融合用戶間的評分相似性和信任關系,得到一種新的用戶間相似度,基于這種新的用戶間關系度量方法進行聚類得到用戶社區結構.

Step 3.利用用戶的評分模式從用戶和物品兩個方面對評分矩陣進行聯合聚類,將原來稀疏的評分矩陣劃分為一個個子矩陣.

Step 4.將用戶社區結構融入到面向聯合社區的矩陣分解模型中進行推薦.

2.2 用戶社區挖掘

由于傳統的用戶聚類算法只是利用用戶間的評分相似性進行聚類,而評分矩陣是十分稀疏的,得到的聚類效果往往不好.因此本文通過融合用戶社交信息和評分信息定義一種新的相似性度量方法,然后基于這種新的混合度量方法對用戶進行聚類.

2.2.1 獲取用戶間的信任關系

在社交網絡中,人與人之間存在著一種相互信任的關系,通常系統無法直接給出十分精確的數值用來反映兩個用戶之間的信任程度,系統給出的往往是二元的,同時由于信任網絡是十分稀疏的,所以需要對信任網絡進行擴展.本文定義用戶間的信任關系值度量公式如下:

(1)

式中,t(u,v)∈(0,1],d(u,v)是用戶u和用戶v之間的最短距離,可以寬度優先搜索算法進行搜索,兩個用戶之間的距離越短則說明兩個用戶之間的信任值越大.根據小世界理論,每個用戶和陌生人之間間隔不能超過六個人,因此我們限制兩個用戶之間的最遠距離為6,即d(u,v)≤6.

2.2.2 獲取用戶的評分相似性

傳統的相似度計算方法是根據不同用戶對項目評分的差別來進行計算的,但是在實際的評分中有些用戶對項目的評分普遍都很高,而有的評分普遍都很低,這種單一的評分偏好會影響傳統相似度計算方法的準確性,為了減輕這種影響,文獻[15]提出一種基于用戶評分偏好的相似度計算方法,其計算公式如下:

(2)

2.2.3 融合信任關系和相似性

把用戶間的信任關系和評分相似性融合在一起,揚長避短,得到一種新的計算用戶間相似度的方法.下面用線性關系來融合這兩種關系,如式(3)所示:

(3)

式中,Trust(u,v)表示通過公式(1)計算的用戶之間的信任關系,SimRat(u,v)表示通過公式(2)計算的用戶間的相似關系.

2.2.4 利用K-means進行用戶社區挖掘

社區挖掘就是將相似的用戶或項目劃分到相同的社區結構中.在進行用戶社區挖掘時選擇經典的K-means聚類算法,但考慮到經典的K-means聚類算法對初始點的選擇比較敏感,如果初始的聚類中心選擇不恰當對最后的聚類結果將產生很大影響.因此考慮對初始點的選擇進行改進,社會心理學的研究表明,人們在選擇推薦的產品的時候往往更加重視專家的意見,由于專家用戶對推薦的影響,因此本文考慮將專家用戶作為K-means算法的初始聚類中心,結合用戶的社交關系和評分信息從可信度,權威性以及評分多樣性三個指標出發,對用戶成為專家的可能性進行評估.

定義1.可信度.可信度反映的是用戶被其他用戶信任的程度,可以通過在信任網絡中用戶的入度來衡量.

(4)

式(4)中,du表示在信任網絡中信任用戶u的用戶數,dmax表示信任網絡中入度的最大值.

定義2.權威性.權威性表示用戶在整個系統中的活躍度,可以利用用戶的評分數量Nu來衡量,用戶的評分數量越多,說明用戶越活躍.

(5)

定義3.評分多樣性.評分多樣性表示用戶對物品進行評分時所表現出來的評分差異性,如果一個用戶對所有物品的評分都相同,這樣就不能反映出用戶對物品的喜好程度,因此專家對不同物品的評分一定要呈現出一定的差異,因此使用評分的方差vu來衡量用戶評分多樣性.

(6)

由于k-means算法需要初始的聚類中心,因此根據用戶的專家值進行排序,取專家值最大的k個用戶作為初始的聚類中心,記作U={expert(u1),expert(u1),…，expert(uk)},那么整個用戶聚類的算法步驟描述如下:

輸入:用戶項目-評分矩陣R,信任矩陣T,聚類簇個數K

輸出:K個用戶聚類簇

步驟1.將集合U中的K個用戶作為初始聚類中心,聚類中心集合記為Center={ce1,ce2,…,cek} 并初始化k個聚類簇,記作C={C1,C2,…,Ck};

步驟2.對用戶集合中的每個用戶,利用公式(3)計算其與所有聚類中心的混合相似度,找到其中相似度最大的用戶Max(Sim(u,cei)),將用戶u加入聚類中心cei所在的聚類簇Ci;

步驟3.更新所有的聚類中心,計算每個聚類簇中用戶混合相似度均值最大的用戶作為新的聚類中心;

步驟5.直到L的值收斂即聚類中心不發生變化時整個迭代就停止,否則返回步驟2繼續執行.

經過以上的迭代過程,可以得到K個用戶聚類簇,其

中,K值是未知的,過大或過小都將對后面的推薦產生很大的影響,因此本文在后面的實驗中來獲取其最優值.

2.3 評分矩陣聯合社區挖掘

由于在大規模的稀疏評分矩陣中,聯合聚類(co-clustering)不僅能有效地降低矩陣的稀疏度,同時可以降低計算的復雜度[14].因此在本小節中,我們利用用戶的歷史評分信息同時對用戶和項目進行聚類,采用這樣的方式進行聚類有利于發現矩陣中隱藏的聚類結構.經過聯合聚類后,一個較大規模的評分矩陣可以轉化為W個規模較小且內部相對稠密的子矩陣,每個子矩陣的內部評分都有較高的相似度,從而可以進行有效的降維,在后面的計算中可以有更小的計算復雜度.

基于評分模式的聚類方法[16]是一種軟聯合聚類算法,用戶和項目可以歸屬多個不同的類.它首先掃描已有的用戶-項目評分矩陣,將用戶、項目和評分按照概率分別劃分類別,整合這三個概率得到用戶-項目評分屬于每個類別的概率.迭代的時候要重新計算用戶、項目、評分屬于某個子矩陣的概率直到收斂.每個聚類簇內部的用戶、項目以及評分會重新組成矩陣.計算評分屬于某個類別的計算公式如下所示:

p(k|ui,vj,r=

(7)

式(7)中,對每個概率加上α,β,γ是為了防止分母為0,在實驗中均設置為0.00000001,p(k|ui),p(k|vj),p(r|k)分別表示用戶和項目屬于該類別的概率以及評分出現在該類別中的概率,其計算公式分別如下:

(8)

(9)

(10)

式中,V(ui)表示用戶ui評價過的物品集合,U(vj)表示對商品vj有過評價的用戶集合,r′表示評分矩陣中的不同評分(從1～5,間隔為0.5的數).運行時首先隨機初始化每個評分屬于某個類別的概率,再不斷進行迭代直至收斂,得到最后的結果.整個算法的詳細描述如下:

輸入:用戶-項目評分矩陣R,類別個數W,概率閾值δ

輸出:每個類別所含的用戶、項目的集合

步驟1.開始時隨機初始化每個評分屬于某個類別的概率p(k|ui,vj,r),滿足∑k′∈Kp(k′|ui,vj,r)=1.

步驟2.對評分矩陣中的每一個用戶和項目,分別根據公式(8)和公式(9)分別計算該用戶屬于各個類別的概率以及該項目屬于某個類別的概率.

步驟3.根據公式(10)計算某個類別中存在某個評分的概率.

步驟4.根據公式(7)重新計算p(k|ui,vj,r),并選取所屬概率大于δ的類別作為該評分的類別.

步驟5.跳轉到步驟2,直到概率值收斂,否則結束程序.

在實驗中為了簡化起見,本文規定用戶所屬類別的概率閾值δ=0.5,整個過程迭代完成后,原本稀疏的矩陣轉變成W個內部相對稠密的子矩陣,其中W值的大小將對整體的推薦產生影響,其最優值可以通過實驗獲取.聯合聚類示意圖如圖2所示.

2.4 結合社區結構和聯合聚類的矩陣分解推薦

2.4.1 基本的矩陣分解模型

矩陣分解是在推薦系統中運用最為廣泛的方法之一,本文以矩陣分解作為基本的模型.在2.3節中得到了聚類后的子矩陣,子矩陣相比原始矩陣而言,矩陣規模小,稀疏性低,因此本文在含有目標用戶的子矩陣中進行推薦.設Rw∈RMw×Nw表示評分子矩陣,w∈{1,2,…w},Mw和Nw分別表示評分子矩陣內的用戶個數和項目個數,設Uw和Vw分別表示評分子矩陣的用戶隱特征向量和項目隱特征向量,在子矩陣內采用矩陣分解技術,和傳統矩陣分解技術類似,其誤差計算公式如下:

(11)

圖2 評分矩陣聯合聚類Fig.2 Score matrix co-clustering

2.4.2 融合社區結構和評分聯合社區的矩陣分解

在現實生活中,我們做的很多決定往往會受到好友的影響,在2.2節中獲取了用戶社區結構,將相互影響的用戶聚集在一起,用戶與同一社區中用戶的偏好相似性要高于不在同一個社區中的用戶,根據目標用戶所在的子矩陣和用戶社區,就可以構造如下的正則項公式,其表達式如下:

(12)

因此,融合矩陣分解的框架可以得到一種結合用戶社區和評分矩陣聯合社區的矩陣分解模型,其目標函數如下所示:

(13)

(14)

(15)

2.4.3 評分預測

當模型訓練完成后,每個子矩陣的隱特征向量Uw和Vw可以求得,對于一個給定的用戶-項目對(ui,vj),用戶對未評分物品的評分預測如公式(16)所示:

(16)

3 實驗與分析

在本小節中,我們將在Epinions數據集上進行算法驗證和對比,為了簡單起見,在后文中用UCCC(user community and co-clustering)來表示本文所提的算法.

3.1 實驗數據和評價標準

Epinions是一個消費者評價網站,用戶可以通過評分對項目進行評價,數據集中包含用戶的評分信息以及用戶間的社交信息,其中含有40163個用戶對139738個商品的664823條評分記錄,除了評分信息以外,還含有487182條用戶間的信任關系.

從以上數據集中隨機選擇80%的用戶-商品評分數據作為訓練集,剩下的20%作為測試集,本文采用五折交叉驗證的方法,即重復五次這一過程,取五次實驗結果的平均值作為本實驗的結果,本文采用平均絕對誤差(mean absolute error,MAE)和均方根誤差(root mean square error,RMSE)作為本次實驗的評估標準.

(17)

(18)

3.2 對比算法介紹

為了檢驗本文的算法與其他推薦算法的區別,我們選擇了5種其他算法作為對比.

1)BaseMF:文獻[17]提出的結合矩陣分解的基本推薦模型,沒有融合其他信息.

2)SoReg:文獻[2]在矩陣分解的模型中加入了社交關作為正則化項,使得用戶的偏好與其好友偏好的均值相似,但是沒有考慮任何社區信息.

3)MFCC:文獻[16]提出的基于聯合聚類的矩陣分解算法,在PMF算法的基礎上,將評分矩陣劃分為子矩陣并行的進行評分預測.

4)UCCC-U:利用本文中的社區挖掘算法,只利用了用戶的社區結構,然后執行矩陣分解算法,沒有考慮聯合社區結構.

5)UCCC-UI:利用本文中的聯合社區挖掘算法,利用子矩陣進行矩陣分解的推薦.

3.3 實驗結果及分析

3.3.1 實驗參數分析

1)用戶社區數目K的確定

首先,針對用戶社區的挖掘過程中,要確定用戶的聚類數目K,本實驗在取不同K值的情況下,觀察MAE值的變化情況,得到最合適的用戶社區數目.同時,為了驗證本文提出的利用專家用戶作為初始聚類中心的K-means算法的有效性,同時選擇了原始的K-means算法作為對比.對于原始K-means算法而言,由于其初始中心不一樣,因此對原始的K-means算法取5次結果的平均值.本次實驗的其他參數設置如下:聯合社區個數W=20,社區正則化參數α=0.01,矩陣分解正則化參數λ=0.01,矩陣分解的特征向量維度設置為10,實驗中K的取值從2開始,間隔為2,實驗結果如圖3所示.

從圖3可以看出,開始時隨著聚類簇數目的增加,MAE值呈減小的趨勢,在聚類數等于12的時候平均絕對誤差達到最小,之后又快速增加.分析其原因可能是:如果用戶社區的數量過少,導致用戶過度集中,可能有不同偏好的用戶也會在一個社區中,導致社區內的平均偏好不準確,影響推薦效果;如果用戶社區過多,則會使用戶十分分散,不能充分利用相似用戶之間的關系,也會導致社區內平均偏好不準確.所以在下面的實驗中選擇用戶社區結構數目為12.同時可以看到采用改進初始聚類中心的K-means算法相比原始的K-means算法效果有明顯的改善,也驗證了本文所用聚類算法的有效性.

圖3 不同K值下的MAE變化情況Fig.3 Changes of MAE under different K value

圖4 不同聯合聚類簇下的RMSE和MAE值變化Fig.4 Changes of RMSE and MAE under different K value

圖5 不同α值情況下RMSE和MAE值變化Fig.5 Change of RMSE and MAE under different α value

2)聯合聚類簇數目W的確定

為了找到最優的聯合社區情況,本文分別在不同聯合社區數目W的情況下(W=10,20,30,40,50,60)計算其RMSE和MAE值,其中用戶社區數取12,其他實驗參數同 1)中一樣,實驗結果如圖4所示.

從圖4中可以看出RMSE與MAE的值剛開始時隨著聯合聚類簇的數目增加而減小,達到最小值后又開始增加.分析其可能原因是:如果聯合社區的數量過少,對于每一個子矩陣而言,其稀疏性仍然很大,因此在推薦時也依然受數據稀疏性的影響很大;如果聯合社區數量過多,那么整個評分矩陣顯得十分分散,在進行矩陣分解推薦時可以利用的評分數據就十分少,這樣同樣影響著推薦的精度.因此評分矩陣的聯合聚類簇的數目為40的時候可以得到最好的效果.

3)正則化參數α的確定

正則化參數α表示的是用戶的社區結構在矩陣分解模型中參與的比重,當α=0時模型相當于基本的矩陣分解模型,本文將α取值分別為{0.0001,0.001,0.01,0.1,1,10}進行實驗,其他實驗參數設置如下:用戶社區數目K=12,評分聯合社區數W=40,λ=0.01,記錄MAE值和RMSE隨著不同的α值得變化情況,實驗結果如圖5所示.

從圖5中可以看到,RMSE和MAE的值先減小后增大,當α=0.01時RMSE和MAE的值達到最小值,分析其可能原因是當α的取值過小時,算法引入的信息對結果影響不大,最后效果不明顯;當α取值過大時,引入的信息權重過大造成過擬合的現象,因此效果也不明顯.

3.3.2 不同推薦算法整體用戶上的效果對比

通過之前實驗的分析,可知當用戶社區數目K=12,聯合社區數目W=40,正則化參數α=0.01時,本文提出的UCCC模型能獲得最佳的推薦結果.為了更加進一步驗證本文所提算法的有效性,將本文的算法與3.2節中提到的算法進行了對比實驗,用戶和項目的特征向量維度均設為10,在SoReg中將社交正則化系數α設置為0.01,MFCC中正則化參數λ設置為10,實驗結果如表1所示.

從表1中可以看出,本文提出的結合用戶社區和評分聯合社區的協同過濾算法和其他算法相比,推薦精度更高,分析其可能的原因是,BaseMF算法沒有考慮評分信息以外的信息,所以其推薦效果最差;SoReg考慮到了用戶間的社交關系信息,推薦精度有一定的提升,但社交關系是十分稀疏的;UCCC-U考慮了用戶的社區結構作為正則項,相對于SoReg來說對用戶進行了聚類操作,更加有效利用了用戶的社交關系信息,因此效果有所提升;MFCC算法和UCCC-UI算法利用了評分矩陣的聯合社區結構,效果相比傳統的BaseMF算法有所提升.本文提出的UCCC算法一方面使用用戶的社區結構,一定程度上緩解用戶間的社交稀疏問題;另一方面,針對評分矩陣進行了聯合聚類操作,緩解了評分矩陣稀疏的問題,因此整體推薦效果可以得到提升.

表1 不同推薦方法在整體情況下的對比Table 1 Comparison of different methods on all users

3.3.3 不同推薦算法在時間性能上的對比

本章所提的基于用戶社區和評分聯合社區的推薦算法可以被應用到大規模的數據集中,圖6描述的是BaseMF算法、MFCC算法、UCCC算法以及其變體算法在進行評分預測時的運行時間對比.

圖6 不同算法的運行時間對比圖Fig.6 Comparison of runtime with different algorithms

從圖6中可以看出,UCCC-U算法的運行時間最長,這是因為單獨地以正則化地方式引入用戶的社區結構并不能降低數據的規模,雖然在推薦誤差上有所下降,但耗時較長;MFCC、UCCC-UI算法因為進行了聯合聚類,所以模型的訓練時間顯著降低,這也證明了聯合聚類確實可以提高運行的效率;同時可以看到UCCC算法相對MFCC和UCCC-U的計算時間是有所增加的,這是由于其在進行矩陣分解時需要搜尋鄰居用戶的偏好,但從表1可以知道其推薦誤差較小,因此其綜合性能較優.總體來說本文提出的算法可以在保證一定推薦精度的同時,提高推薦的效率.

4 結 語

本文在傳統的基于社區結構的推薦算法的基礎上,融合用戶的社區結構和評分矩陣聯合社區結構,通過利用聚類算法來挖掘用戶社區,通過概率的方法來挖掘評分矩陣聯合社區,然后在面向聯合社區的矩陣中結合用戶社區進行矩陣分解.在當前研究中,我們考慮的都是靜態興趣偏好與社交關系,但是隨著時間的推移,用戶的興趣和社交關系都是不斷在變化的,因此考慮在動態場景下的協同過濾推薦算法是未來研究的重要工作之一.