結合信任關系的用戶聚類協同過濾推薦算法①

孟 晗,高 岑,王 嵩,張琳琳,劉 念

1(中國科學院大學 計算機控制與工程學院,北京 100049)

2(中國科學院 沈陽計算技術研究所,沈陽 110168)

引言

在大數據時代,互聯網給用戶帶來了大量信息,但隨著網絡的不斷發展和信息的迅速增長,用戶在浩瀚數據中想要找到所需信息將會愈發困難,出現了信息超載問題.目前,解決信息超載一個非常高效的方法就是推薦系統.推薦系統簡單來說就是一種信息過濾系統,用于預測用戶對物品的喜愛程度.在推薦系統中,協同過濾(Collaborative Filtering)技術是推薦系統中應用最早和最為成功的技術之一,其核心是用戶的評分數據,與被推薦的內容無關,即:在閱讀歷史中對新聞評分相似的用戶在將來也會相似,從而把推薦轉換為評分預測問題[1].同時,由于協同過濾具備發現用戶隱藏興趣的能力,并且可以有效的使用其他相似用戶的反饋信息,加快個性化學習速度,因此逐漸成為最受歡迎的推薦算法.

雖然協同過濾推薦技術有著廣泛的應用,但是也存在很多問題,比如冷啟動、數據稀疏等,因此研究人員不斷的對其進行創新和改善.Lokhande 等[2]提出一種附加的層次聚類技術,并且將主成分分析用于數據降維,提高了傳統CFRA 輸出的準確性.Bobadilla等[3]研究了神經網絡學習算法在冷啟動問題中的應用.Zhou 等[4]提出了功能矩陣分解模型(functional matrix factorization),利用決策樹和矩陣分解的結合,在冷啟動過程中為用戶選擇合適的物品進行打分,從而盡可能準確地理解用戶的偏好.

上述研究都是依托于已有的評分數據進行分析,但依托的這些數據并沒有考慮用戶間的信任關系,而一個良好的信任關系模型能夠有助于尋找相似度更高的近鄰用戶,從而得到更準確的推薦結果.基于此,Yang 等[5]采用矩陣分解將用戶映射到低維特征空間的信任關系,更準確的反映了用戶之間的相互影響.Xue 等[6]提出將用戶間的信任關系依據方差大小進行量化形成調節因子的思想,算法將調節因子納入用戶相似性計算,形成相似性用戶聚類簇,但是上述算法沒有在真實應用場景中實驗,并且忽略了用戶隱式信任關系導致實驗結果不完整.Du 等[7]創新了社會學領域的信任關系計算,用其代替傳統的相似度計算方法,將信任度集成到最近鄰居選擇中.信任網絡是通過擴展不同的路徑長度來構建的,用戶之間的信任值可以通過信任傳輸規則來獲得.

綜上所述,很多研究學者為了解決協同過濾存在的問題,都會考慮降維、矩陣分解、神經網絡等方法.而本文從描述用戶關系入手,結合用戶屬性和信任傳遞設計了一種改進的信任機制,然后融合到相似度算法中,使其能夠更好的反映用戶之間的關系,最后結合聚類算法,提高了推薦的精確度,同時解決了協同過濾的冷啟動以及數據稀疏問題.

1 協同過濾推薦算法

協同過濾是目前應用最廣泛的推薦算法,其基于系統中其他用戶的評分或行為進行預測和推薦.這種方法認為,如果兩個用戶對某些項目有著相同的評價,那么他們可能會對其他項目也達成一致意見.

基本的協同過濾算法通常經過以下幾個步驟:

步驟1.收集數據并建立用戶評分矩陣.矩陣中行代表用戶,列代表項目,元素值為具體的評分值,一般在0～5 之間,評分越大喜愛程度越高.

步驟2.計算每個用戶與其他用戶的相似度.皮爾遜相關系數是目前最常見的計算方式,其公式如下:

式中,a,b代表兩個用戶,Ra,i表示用戶a對項目i的評分,Ia,b表示用戶a,b共同評分的項目,,分別表示用戶a和b所有評分的平均值.

步驟3.尋找目標用戶最近鄰.依據相似度選取與目標用戶最相似的鄰居集合作為目標用戶的最近鄰.

步驟4.生成推薦結果.根據確定好的鄰居集合,通過式(2)計算出預測值,最后依據預測評分的排序進行推薦,得到最終的結果.

由上述算法可以看出,在整個計算過程中,最為核心的是相似度的計算以及最近鄰的選取,但是相似度計算公式中沒有考慮用戶間的隱性關系,也沒有考慮一個用戶本身的可信任度問題,更可預見的是,在推薦系統初始化時,由于數據稀疏還會產生冷啟動問題.同時,最近鄰的選取上也過于簡單化,容易出現推薦結果不準確的情況.基于以上對傳統協同過濾算法的分析,本文將結合信任機制對相似度計算進行改進,并且結合聚類算法對最近鄰的選取合理優化.

2 信任關系

在推薦系統中,信任關系指的是目標用戶對其他用戶評分可靠性的一種主觀認可程度,認可程度越高則信任關系越密切.一般來說,信任關系可以分為直接信任與間接信任.

2.1 直接信任

2.1.1 傳統的信任關系模型

已有的描述信任關系[8]是由初始信任度與交互權重相乘得到的,如式(3)所示.其中Init(a,b)為初始信任度,由式(4)表示,t表示用戶a和用戶b達到信任的最小交互次數,參考文獻[8]的實驗結果可設置t為80.Ia∩Ib表示兩個用戶的交互次數.Cs表示成功交互次數,所謂成功交互指兩個用戶在交互項目的評分差值小于2.Ca指的是交互總數.

2.1.2 改進的信任關系模型

改進1.傳統的信任模型雖然可以成功表示兩個用戶的信任關系,但是忽略了惡意用戶或者傾向于給高低分的用戶,如果一個用戶比較嚴格,評價分數普遍過高或者過低,則認為其不是一般性用戶,此用戶在信任機制中的權重則應該減少.因此這里我們引入一個用戶本身可信任度,公式如下:

其中,C(Rb=1,2)代表用戶b評價分數為1和2的總次數,C(Rb=4,5)代表用戶b評價分數為4和5的總次數.此式可以衡量出低分和高分之間的比例,若兩者相差較大證明該用戶趨向于高分或者低分,從而可信任度下降.將其融合到信任模型中得到式(6):

式(6)在原有的信任機制中引入用戶本身可信任度,經過計算之后,如果打分比較正常的用戶,其信任度變化不大,而惡意用戶或者比較嚴格的用戶其信任度會有所下降,通過這種改進有效地區分了兩種用戶對相似度計算的影響.

改進2.增加兩個用戶的本身屬性到可信度中.一般而言,人們更傾向于相信與自己特征類似的群體.這里我們采取3 個用戶屬性融合到信任模型中,分別是用戶年齡、性別和職業,這里參考文獻[9]及其實驗結果,S(a,b),A(a,b),O(a,b)分別代表性別、年齡和職業的相似性,公式分別如下:

得到用戶之間的屬性相似性[9]如式(10)所示:

組合到信任模型最終得到直接信任公式為:

2.2 間接信任

由于評分矩陣一般都是稀疏矩陣,所以直接信任數據過于稀少,因此需要引入間接信任,即用戶間無直接信任關系,但存在至少一條可達路徑,從而建立的信任關系.間接信任用ITrust(a,b)來表示.根據六度分割理論可知信任傳遞最大路徑長度為6,依據文獻[10]的研究設置信任傳遞最大路徑長度d值為3.

假設用戶a和b之間存在至少一條路徑,則路徑集合表示為Paths(a,b)={p1(a,b),p2(a,b),···,pn(a,b)}每條路徑可表示為pi(a,b)=(ai,ci1,ci2,···,bi).每條路徑權重αi隨路徑長度呈遞減趨勢,計算方式如式(12)所示,其中dpi(a,b)表示第i條路徑的長度:

則每條路徑的信任度可表示為:

由此得到間接信任模型如式(14)所示,其中n表示用戶a和用戶b可以可達路徑總數,最終得到的用戶a和b的間接信任度通過取平均值的方式計算得出.

2.3 融合信任模型

融合信任模型指的是由直接信任和間接信任采用加權因子融合而成,用來綜合考慮用戶間信任關系的一種評估方式,其中的加權因子 λ取值在0?1 之間,用來衡量兩個信任度的權重,其計算公式如式(15)所示:

最后通過計算參數值,得到最終的信任模型Trust(a,b)如式(16)所示:

3 相似度算法改進

3.1 融合熱點的皮爾遜相關系數

由第1 節介紹可知目前大多是用皮爾遜相關系數進行相似度的計算.但是該計算方式忽略了熱點新聞的影響程度,一條新聞越受歡迎,多個用戶共同點擊的概率就會越大,對相似度影響的權重就會越低,基于此,提出一種融合熱點的皮爾遜相關系數HS-P 如式所示:

其中,Ia,b代表用戶a和b共同評價過的項目集合Ra,i代表用戶a對項目i的評價值,為用戶a的評價平均值,Ci為用戶a和b共同評價的某個項目i的被評價次數,為所有項目被評價次數的平均值.從上述,公式可以看出一個項目被評價的次數越多,則其在相似度計算中所占權重越低.

3.2 最終的用戶相似度公式

結合第2 節的用戶信任關系以及上述的HS-P 公式,得到最終改進的衡量用戶間相似度公式為:

4 算法過程描述

4.1 用戶聚類迭代算法

依據之前對相似度算法的改進,可以將其用到聚類算法之中,通過不斷迭代的方式調整用戶聚類簇,讓其達到穩定,這種方式可以更加準確的尋找到目標用戶的最近鄰.具體的算法步驟如算法1 所示.

4.2 推薦算法整體流程

本文的算法整體流程如圖1所示.當用戶聚類算法迭代完成,也就是用戶聚類集合趨于穩定之后,再尋找最近鄰的可靠性就會大大增加.假設查找目標用戶a的k個鄰居,首先計算用戶a與所有聚類中心的相似度,然后優先選取相似度最高的聚類,計算a與該聚類中各個用戶的相似度,選取前k個即為最近鄰,記為UKN(a),則用戶a對項目i的預測評分為:

圖1 算法整體流程圖

最終通過預評分公式預測出目標用戶a對項目的評分值,選取評分值最高的前N個項目作為推薦結果.

算法1.用戶聚類迭代算法輸入:用戶集合U,評分矩陣Rm×n輸出:調整后的用戶聚類(1)首先用K-mean 聚類算法對初始的用戶集合進行聚類,得到初始用戶聚類和初始用戶聚類中心為(2)//迭代得到最佳用戶聚類集合repeat for each user Ui∈U UC={UC1,UC2,···,UCk} C={C1,C2,···,Ck}for each user cluster Cj∈C計算Ui與聚類中心Cj的相似度USim(Ui,Cj)end for US im(Ui,Ct)=max{sim(Ui,C1),···,sim(Ui,Ck)}Ui 所屬聚類UCs=UCs-Ui UCt=UCt+Ui end for for each UCi∈UC更新聚類中心Ci until 聚類簇中元素不再變化或者達到設定迭代次數

5 實驗

5.1 實驗數據

本次實驗選擇了明尼蘇達大學GroupLens 項目組收集的MovieLens 數據集,該數據包含了943 位用戶對1682 部電影的十萬條打分記錄,打分標準從1 到5,經過計算得到稀疏度達到了93.7%.另外,該數據集還包含了用戶的特征屬性信息,滿足本文對信任關系的改進要求.實驗時隨機選取數據集中的80%作為訓練集,20%作為測試集.

5.2 實驗評分標準

實驗標準采取均絕對誤差MAE(Mean Absolute Error)進行評估,該值是用來衡量預測值與真實值之間的誤差,值越小,誤差就越小,推薦的準確率也就更高.其計算公式為:

其中,n表示預測的項目個數,Pi表示預測的評分值,Ri表示真實的評分值.

5.3 實驗結果與分析

實驗1.在聚類算法中,首先需要確定好聚類的數值大小.這里采取傳統的用戶聚類協同過濾算法進行實驗,其中迭代時計算用戶間相似度采用原始的皮爾遜相關系數.聚類數值從10 增加到50,查看對應的MAE值大小,實驗結果如圖2所示.

圖2 不同聚類次數對應的MAE 值

從圖2可以看出MAE值的變化隨著聚類數值的增大而縮小,當K達到50 時MAE有最低值,這里考慮到算法效率問題,選取聚類數為50 進行后續實驗.

實驗2.對于用戶聚類迭代算法,不容易判斷何時聚類簇穩定,因此需要考慮迭代次數對MAE的影響.實驗中設定相似度權重因子μ=0.5,鄰居個數設置N=10,調整聚類迭代次數從1 到10,觀察不同迭代次數對MAE的影響如圖3所示.

從圖中可看出當迭代次數從7 開始MAE值保持穩定,此時可以設定聚類簇達到穩定狀態.因此后續實驗中,設定迭代次數為7 次.

圖3 不同迭代次數對應的MAE 值

實驗3.該實驗的目的是確定式(15)中權重因子μ的取值,實驗中確設定迭代次數為7 次,鄰居個數取值為10,圖4比較了當μ 取值在0–1 之間時MAE的相應值.

圖4 不同權重因子對應的MAE 值

從圖4中可以看出,μ的值不宜過大或者過小,當μ=0.6 時,即信任關系占據權重0.6,HS-P 相似度算法占據權重0.4 時,MAE有最低值,此時推薦結果最準確.

實驗4.為了驗證本文提出的結合信任關系的用戶聚類協同過濾推薦算法(K-TUBCF),實驗選取了幾個傳統算法[10]比較它們的MAE值,算法包括傳統的基于用戶的協同過濾算法(UBCF),基于K-means 聚類的協同過濾推薦算法(K-UBCF),融入傳統信任關系的協同過濾算法 (TUBCF),融入用戶喜好度到信任關系中的協同過濾算法(WTUBCF),最終結合文獻[8,10]的數據得出實驗對比結果如圖5所示.

從圖5中可以看出,這幾種算法隨著鄰居個數的增加MAE值逐漸下降,并且在鄰居個數達到30 時趨于穩定,說明鄰居個數N=30 時會取得最好的推薦結果.

另外,本文提出的算法在MAE值上明顯低于之前的各類算法,說明本文這種基于改進信任關系的用戶聚類算法可以有效的提高算法準確度,產生更準確的推薦結果.

圖5 不同算法之間的比較

6 結論

本文提出的結合信任關系的用戶聚類協同過濾推薦算法,在直接信任與間接信任兩個層面上都做了一定改進,并且有效的結合用戶的屬性特征.另外,對于傳統的皮爾遜相似度忽略熱點新聞的缺點進行了補充,最后采用迭代的聚類算法求出最近鄰從而得到更為準確的推薦結果.實驗也證明所提出的優化算法比之前的算法誤差值更小.但是文章沒有考慮到時間對推薦的影響,下一步將結合時間因子對推薦算法進行更詳細的研究,使其更加滿足實際情況.