基于模糊聚類的多視圖協同過濾推薦算法

黃巧文,周寬久,費 錚,崔云鵬

(1.北京商業機械研究所 信息化研究部,北京 100070;2.大連理工大學 軟件學院,遼寧 大連 116081)

0 引 言

隨著移動互聯網的發展及大數據時代的到來,信息呈現出爆炸式增長。面對信息的泛濫和超載,人們往往會無所適從,在信息面前會面臨各種選擇問題,如信息的獲取方式、信息的真偽鑒別等。于是,為了幫助用戶獲取其感興趣且有價值的信息,推薦系統應運而生?，F如今,推薦技術已經成功在電子商務、社交網絡等領域中得到了廣泛應用,它旨在根據用戶在系統中的自然行為和歷史數據,挖掘用戶的興趣點,從而向用戶推薦其感興趣的項目,如資訊、商品和廣告等。

推薦算法是推薦系統中的核心部分,常用的推薦算法包括基于內容的推薦算法[1]、基于知識的推薦算法[2]和基于協同過濾的推薦算法[3]等。其中,基于協同過濾的推薦算法因其簡單、高效的特點而被廣泛應用。在實際應用中,協同過濾算法根據其作用的對象又可分為基于用戶的協同過濾(UBCF)和基于項目的協同過濾(IBCF)。以IBCF算法為例,其核心思想是先通過用戶的歷史行為信息構建用戶—項目的評分矩陣,然后挖掘相似性較大的項目,并得出目標用戶對項目的預測評分,最后將預測評分進行排序,形成TOP-N推薦結果。

聚類[4]作為一種無監督機器學習方法,在推薦領域常被用于挖掘用戶或項目的相似性,以提升推薦效率。由此,針對協同過濾算法的不足,大量的學者提出了一系列的改進措施。李華等[5]提出了基于模糊聚類的協同過濾推薦算法,該算法將模糊聚類算法作用于項目評分矩陣,一定程度上提高了推薦的實時性和準確性。肖文強等[6]提出了基于譜聚類的用戶協同過濾推薦算法(Collaborative Filtering Recommendation Algorithm based on User Spectral Clustering,SC-CF+),該算法利用譜聚類將用戶進行聚類,降低了用戶空間的維度,同時在相似性度量中引入了項目的時間和流行度等因素提高了推薦結果的召回率?？紤]到矩陣分解的有效性,Ifada等[7]基于非負矩陣分解(NMF)、奇異值分解(SVD)、主成分分析(PCA)三種矩陣分解方法和K-means、模糊C均值聚類兩種聚類方法的6種組合研究了不同矩陣分解方法在基于聚類的協同過濾推薦算法中的差異性。為了降低數據稀疏性的影響,蘇慶等[8]著重優化了項目的相似度計算方式,通過引入時間差因子和冷門、熱門項目權重以改進修正的余弦相似度,并結合模糊C均值聚類算法提出了基于改進模糊劃分的協同過濾推薦算法(Collaborative Filtering Recommendation Algorithm Based on Improved Fuzzy Partition Clustering,GIFP-CCF+)。為了解決推薦系統數據稀疏及冷啟動問題,王巖等[9]基于蜂群算法降低了K-means++算法聚類中心的敏感度,從而緩解了數據稀疏問題,提高了推薦質量;賈俊杰等[10]通過融合用戶間的顯、隱式信任值將信任機制引入到模糊C均值聚類算法中,提出了基于用戶模糊聚類的綜合信任推薦算法。劉軍等[11]在解決冷啟動問題的基礎上,提出一種增強評分矩陣的協同過濾推薦算法,該算法綜合考慮用戶購買意愿力、用戶興趣便宜因素以及時間因素等為用戶提供精準推薦。上述算法均為單一聚類算法在推薦系統上的優化,為了進一步增強聚類算法在推薦系統中的性能,Zarzour等[12]又基于集成聚類技術,將多種聚類算法集成到推薦系統中,集合期望最大化和超圖劃分算法提高了預測精度。最近,王英博等[13]提出了基于子空間聚類的協同過濾推薦算法(Subspace Clustering based User Collaborative Filtering Recommendation Algorithm,SCUCF),該算法通過利用子空間聚類來構建用戶鄰居樹,結合改進的相似性度量方法提高了尋找相似用戶的準確性?？傊?大部分的改進算法都致力于改進相似性度量方式、改進鄰域劃分以及降低數據稀疏性帶來的影響等措施來提高算法的性能,而忽略了推薦系統中用戶行為的復雜性和多樣性。

基于“村鎮社區新型商貿連鎖綜合服務平臺研究及示范”的國家重點研發計劃,針對課題中新零售精準會員推薦系統中具有多源異構特點的用戶行為,提出基于模糊聚類的多視圖協同過濾推薦算法。首先,為挖掘用戶的關鍵行為信息,將用戶在系統中的多種行為數據整合為多視圖數據[14],并基于此提出基于多視圖融合的項目相似性度量方法和用戶偏好預測方法。然后,為了在優化項目鄰域劃分的同時自動學習用戶的多種行為偏好之間的差異性,結合最大熵方法[15]提出基于質心約束的多視圖熵加權模糊聚類算法(Centroid Constraints Based Multi-View Entropy Weighted Fuzzy Clustering,C_MVEWFC)。此外,考慮到C_MVEWFC算法的非線性表達能力較弱的問題,基于核映射技術提出基于質心約束的多視圖加權核模糊聚類算法(Centroid Constraints Based Multi-View Entropy Weighted Kernel Fuzzy Clustering,C_MVWKFC)。最后,結合上述改進的項目相似性度量方法和用戶偏好預測方法,基于C_MVEWFC算法和C_MVWKFC算法提出對應的協同過濾推薦算法MVFC-CF和MVKFC-CF,算法的執行流程如圖1所示。為公平比較算法的推薦效果,在公開數據集上與較為先進的基于聚類的協同過濾推薦算法進行實驗驗證。

圖1 MVFC-CF算法和MVKFC-CF算法的執行流程

1 相關理論

1.1 協同過濾推薦算法

假定J個用戶、K個項目的評分矩陣定義為R=[rjk]J·K,rjk表示第j個用戶對第k個項目的評分,則列向量r.k表示項目k的受歡迎程度。因此,項目之間的相似性就是評分矩陣R中列向量之間的相關性。通常來講,可以通過余弦相似度、Pearson相關系數、Jaccard系數等來刻畫該相關性,式(1)為余弦相似度的計算公式。

(1)

由式(1)可得項目k與其余所有項目之間的相似性。

在進行項目的評分預測時,傳統方法首先在項目空間中計算并搜尋項目的鄰域,然后結合項目之間的相似度和用戶—項目評分矩陣可得如下的評分預測[16]:

(2)

從式(1)可看出,傳統協同過濾算法在計算項目的相似性時是在全局范圍內進行搜索的,這在大規模推薦系統顯然不適用。而聚類算法的引入,縮小了近鄰項目的搜索范圍,使得協同過濾算法在尋找近鄰項目時只需聚焦于同一類簇下,這給傳統的協同過濾算法創造了新的發展空間。

1.2 模糊劃分聚類算法

Fuzzy C-Means(FCM)聚類算法[17]是最為經典的模糊聚類算法,它旨在通過劃分的方式將數據分割成類間相似度較小、類內相似度較大的類簇。給定待聚類的M×N維數據X={x1,x2,…,xm}M×N,FCM的目標函數如下:

(3)

其中,U=[umk]M×K為模糊劃分矩陣,umk表示第m個樣本屬于第k個類的程度;ck則表示第k個類的聚類中心向量;α為大于1的模糊因子。

顯然,傳統的FCM算法原理較為簡單,難以處理復雜多變的數據。近年來,隨著信息技術的發展,數據往往呈現出多源異構的特點。為了提高對此類數據的聚類精確度,大量的多視圖聚類算法[18-19]層出不窮,同時這些算法被廣泛應用在數據挖掘等領域。然而,推薦系統中的多視圖聚類算法為了簡便大多數是先在單視圖聚類的基礎上進行拆分,再尋求融合之法;沒有考慮到多個視圖之間既存在關聯性也存在差異性,忽略了多個視圖對于最終推薦結果的差異化貢獻。

1.3 多視圖行為的項目相似性度量與偏好預測

該部分基于推薦系統中復雜多樣的用戶行為數據,結合行為之間的差異性,提出新的偏好預測方法和項目相似性度量方法。

1.3.1 項目相似性度量

用戶在項目上的不同行為可看作是不同的視圖(角度)上對項目的偏好,張量Z={X1,X2,…,Xv}囊括了用戶的V種行為數據,對于其中一個視圖來講Xv=[xni]N×I代表用戶的行為矩陣,例如評分、點擊歷史、購買歷史等;xni∈[0,1]表示用戶n對項目i的局部偏好。因此,用戶對項目的全局偏好程度Q=[qni]N×I定義為:

(4)

式中,ωvni表示在第v個視圖中用戶n和項目i之間的行為權重;xvni表示在第v個視圖中用戶n對項目i的行為偏好。本方法在用戶對項目的偏好程度的評估上融合了用戶對項目的多種行為信息,而這多種行為信息的重要程度則由Ω(Ω=[ωvni]V×N×I)決定,因而這種評估方式更具客觀性和準確性。

在項目相似性的計算上,考慮到不同用戶對不同項目偏好的標準和程度上的差異,結合修正的余弦相似度和式(4),引入新的融合多種行為信息的項目相似性度量方法,如式(5)所示。

(5)

sij=gij×oij,oij∈[0,1]

(6)

其中,oij在計算時已經過歸一化處理。

1.3.2 用戶偏好預測

結合式(5)、式(6),項目的偏好預測公式如式(7)所示:

(7)

2 多視圖協同過濾推薦算法

為了提高推薦結果的準確性,本節首先提出C_MVEWFC算法,該算法能夠實現上述行為權重的自動優化以及多視圖的協同過濾;然后,在此基礎上引入核函數,進一步提出C_MVWKFC算法以提高算法對非線性數據的聚類性能。

2.1 基于質心約束的多視圖熵加權模糊聚類算法

給定項目行為的多視圖數據集Z={X1,X2,…,Xv},C_MVEWFC算法的任務是融合V個視圖將數據劃分為K個類簇,該算法的目標函數如式(8)所示。

F(M,C,Ω)=

(8)

式中,M=[μik]I×K為隸屬度矩陣,即模糊劃分矩陣;μik表示第i個樣本(項目)屬于第k個類的程度;C=[cvkn]V×K×N為三維的聚類中心矩陣,cvkn代表第v個視圖中第k個聚類中心的第n個屬性(該文指用戶偏好);Ω=[ωvin]V×I×N為三維的權重矩陣,ωvin為第v個視圖中第n個用戶對第i個項目的偏好權重;α為模糊因子,β和γ是兩個正標量。

在目標函數F中,第一項是對FCM算法的改進,主要用于融合多個視圖的數據來學習全局隸屬度矩陣M,從而進行數據劃分;第二項為聚類中心(質心)的正則化項,通過最大化類間聚類中心的距離來進一步優化類簇的劃分;第三項為權重的正則化熵項,用于最優化權重ωvin的分布;β和γ則分別控制著后兩項的重要程度。因此,算法的目標是通過最小化目標函數(8)得到多視圖數據的最優劃分,該文采用Picard迭代法[20],通過迭代求解M、C、Ω逐步將式(8)進行最小化。

首先,固定C和Ω求解M。使用拉格朗日乘數法將帶有約束的F(M)最小化問題轉化為如式(9)所示的無約束最小化問題。

(9)

(10)

(11)

結合式(10)和式(11)即可得到全局模糊隸屬度的更新公式,如式(12)所示。

(12)

其次,固定M和Ω求解C。此時,目標函數的最小化問題轉化為式(13)的最小化問題。

(13)

這里令dL(C)/dcvkn=0,可得:

(14)

通過求解式(14)可得到各視圖聚類中心的迭代公式,如式(15)所示。

(15)

最后,固定M和C求解Ω。同樣地,借助于拉格朗日乘數法,將帶有約束的F(Ω)的最小化問題轉化為式(16)所示的無約束最小化問題。

(16)

γlogωvin+γ+θin=0

(17)

(18)

求解式(17)和式(18)得到權重的迭代公式,如式(19)所示。

(19)

結合以上公式,C_MVEWFC算法的執行流程如算法1所示。

算法1:C_MVEWFC算法

輸入:多視圖數據Z,項目個數I,視圖個數V,類簇個數K,迭代收斂閾值ε,最大迭代次數tmax,以及參數α,β,γ

輸出:隸屬度矩陣M=[μik]I×K

1.初始化每個視圖隨機生成K個聚類中心cvkn,設定行為權重ωvin為1/V,設置迭代計數器t=1;

2.fort

3.通過式(12)更新隸屬度矩陣M;

4.通過式(15)更新聚類中心矩陣C;

5.通過式(19)更新權重矩陣Ω;

6.利用式(8)計算目標函數F的值;

7.if|F(t)-F(t-1)|<εthen//目標函數收斂

8.break;

9.end if

10.t++;

11.end for

2.2 基于質心約束的多視圖加權核模糊聚類算法

為了提高C_MVEWFC算法對非線性多視圖數據的劃分精度,借鑒核聚類算法[21]的思想并結合高斯核函數進一步提出基于核函數的C_MVWKFC算法,該算法的目標函數如式(20)所示。

Fψ(M,C,Ω)=

(20)

其中,ω(x)表示將x從低維的特征空間映射到高維的核空間,而核空間中向量的內積則可由核函數ψ(a,b)=φ(a)Tφ(b)得出,該文采用的高斯核函數如式(21)所示。

(21)

式中,a和b代表參與運算的變量。根據高斯核函數的運算規則,式(20)可以進一步改寫為:

Fψ(M,C,Ω)=

(22)

與C_MVEWFC算法一樣,C_MVWKFC算法的目標是通過最小化目標函數來得到最優的劃分矩陣M。在目標函數的求解上同樣采用Picard迭代法,式(23)、式(24)及式(25)分別為得出的隸屬度更新公式、聚類中心更新公式和權重更新公式。

(23)

cvkn=

(24)

(25)

結合以上公式,C_MVWKFC算法的執行流程如算法2所示。

算法2:C_MVWKFC算法

輸入:多視圖數據Z,項目個數I,視圖個數V,類簇個數K,迭代收斂閾值ε,最大迭代次數tmax,核參數σ,以及參數α,β,γ

輸出:隸屬度矩陣M=[μik]I×K

1.初始化每個視圖隨機生成K個聚類中心cvkn,設定行為權重ωvin為1/V,設置迭代計數器t=1;

2.fort

3.通過式(23)更新隸屬度矩陣M;

4.通過式(24)更新聚類中心矩陣C;

5.通過式(25)更新權重矩陣Ω;

6.利用式(22)計算目標函數Fψ的值;

8.break;

9.end if

10.t++;

11.end for

2.3 計算復雜度分析

對于C_MVEWFC算法,假設待聚類的用戶行為數據包含V種行為、N個用戶、I個項目以及K個類別,則該算法在一個迭代周期內計算隸屬度的時間復雜度為O(VIK2N),計算聚類中心的時間復雜度為O(VIK2N),計算權重的時間復雜度為O(V2IKN)。因此,C_MVEWFC算法執行一次的時間復雜度為O(tV2IK2N),其中t為算法的迭代次數;同樣地,C_MVWKFC算法的時間復雜度亦為O(tV2IK2N)。在實際的應用中,用戶的數量N和項目的數量I要遠大于行為的種類V和項目的類別K,故可認為文中的兩個聚類算法的時間復雜度接近于O(IN)。此外,根據式(4)和式(6)可知,偏好矩陣和相似度矩陣的計算復雜度分別為O(VIN)和O(I2)。

3 實驗分析與討論

3.1 實驗數據與目的

如表1所示,采用兩種公開數據來驗證算法的效果,其中一個是阿里巴巴的淘寶用戶行為數據集UserBehavior[22],該數據集記錄了一段時間內部分用戶對商品的消費行為,包括點擊、購買、收藏、加購物車等。在實驗數據的構造上,將用戶的上述4種行為數據看作為4種不同的視圖,先從原始數據中抽取了500名用戶在行為密度較高的7 800個商品上的行為數據作為實驗數據集,然后從項目的維度將以上數據集劃分成兩部分,即訓練集和測試集,分別占整個實驗數據集的80%和20%。

表1 實驗數據構成

由該數據的構造可知,點擊行為表達出了用戶對項目的第一印象,也是用戶對項目偏好與否的第一行為反饋。故在該數據集上的實驗目的就是通過學習訓練集中用戶與項目之間的不同行為來預測測試集中用戶對項目的點擊行為。

參與實驗的另一個數據集是MovieLens-1M[23],該數據集是由GroupLens團隊從MovieLens網站(https://movielens.org)上收集的,包含了2000年加入MovieLens的6 040人對約3 900部電影的100萬條匿名評分。該數據集在實驗中用于驗證引入核函數的MVKFC-CF算法相較于MVFC-CF算法的非線性數據處理能力。為了保證該數據集在算法上的可用性,這里首先分別將用戶對電影的評分、電影上映時間與評分時間差作為兩個不同的視圖,兩個視圖均能從不同的角度反映出用戶對電影的喜好程度;其次利用Sigmoid激活函數將評分與時間差的真實值均分別進行非線性變換,以得出非線性的多視圖數據集。在訓練集和測試集的劃分比例上,與UserBehavior數據集保持一致。

3.2 評價指標與參數設定

為了更加合理、公平地評估文中算法的性能,選用平均絕對誤差MAE[24]和推薦結果TOP命中率THR[25]作為算法性能的評價指標,并同基于改進的kmeans聚類的協同過濾推薦算法Kmeans-CF[16]、基于模糊C均值聚類的協同過濾推薦算法FCM-CF[8]、SC-CF+[6]、GIFP-CCF+[8]、SCUCF[13]等進行比較。MAE和THR的公式分別定義如下:

(26)

(27)

算法涉及到的超參有模糊因子α,核參數σ,正則化參數β和γ,實驗中采用網格搜索法來尋找參數的最優值,表2列出了這些參數的搜索范圍。

表2 算法參數的尋優范圍

3.3 實驗結果與分析

3.3.1 UserBehavior數據的實驗結果

首先,針對參與對比實驗的所有算法利用訓練數據集尋找最佳聚類參數,并通過比較MAE和THR值的變化情況來確定最終的參數取值,如文中α的取值為2.0,β的取值為10-5,γ的取值為10-4,σ的取值為22。然后,為了實驗的公平性,在測試集上驗證各算法的實際推薦效果和泛化性能,這里每種算法的評價指標均取在測試集上執行100遍的均值。表3列出了上述5種算法和文中算法在UserBehavior數據集上的MAE值和THR值,以及兩指標的標準差。從表中可知,相較于其他算法Kmeans-CF和FCM-CF的推薦效果最差。一方面這是因為傳統的聚類算法難以處理多視圖數據,導致在尋找鄰域項目時準確度不高;另一方面,傳統協同過濾算法在用戶的偏好預測上只能參考用戶的單一行為,難以挖掘到多種行為之間的聯系。

表3 算法效果對比

雖然SC-CF+、GIFP-CCF+、SCUCF等三個算法都從項目相似性度量、項目鄰域劃分等不同的角度進行了改進,但仍然忽略了推薦系統中多種行為的關聯性和差異性,故而在面對多視圖數據時推薦效果差強人意。而引入多視圖概念的MVFC-CF算法通過自動加權的方式自動地學習用戶的關鍵行為,同時采用多視圖聚類的方式優化了項目鄰域的劃分,進而與SCUCF算法相比在MAE上從0.622 9降低到0.603 4,在THR上從0.128 2提升到0.143 6。此外,由于核函數的引入,MVKFC-CF算法的精度得到進一步提升,相比于MVFC-CF算法在MAE指標上相對降低了3.1%,在THR指標上相對提升了5.92%。

聚類數K與數據集本身強相關,該參數是決定最終類簇緊密程度的重要影響因素,而在與聚類結合的協同過濾算法中,該參數的取值會直接影響到最終的推薦效果。為了確定文中數據集最優的聚類數目,這里用K={5,10,15,20,25,30} 6個不同大小的聚類數來測試聚類數K對算法的影響。實驗中,固定各算法的最優聚類參數不變,將聚類數目由最初5個逐漸增加至30個,觀察各算法的評價指標的變化情況。圖2(a)(b)分別展示了以上7種算法在測試集上不同K值下的MAE和THR的變化趨勢。由圖2可知,隨著聚類數量的逐漸增加,所有算法的預測精度都呈現出越來越好的趨勢。這是因為聚類數越大最終得到的項目鄰域就越細化,那么找到相近鄰居的概率就越高,因此推薦結果就越精準。從圖中可進一步觀察到,對于本數據集而言,當聚類數達到25至30時大部分算法均趨于穩定,因此在測試中文中算法的K值設定為25。從算法的表現上來看,MVKFC-CF相比較新的SCUCF算法在MAE上從0.622 9降低到0.584 7,在THR上從0.128 2提升到0.152 1。整體來看,MVFC-CF算法和MVKFC-CF算法相較于其他算法在不同的K值下均表現出了更好的性能,這再次驗證了文中算法的有效性。

圖2 算法在UserBehavior數據集上不同K值下MAE和THR的變化曲線

3.3.2 MovieLens-1M數據的實驗結果

MVKFC-CF算法通過引入核映射技術以提高MVFC-CF算法的非線性數據處理能力,從而提高協同過濾的準確性。為了驗證MVKFC-CF算法的推薦效果,實驗中首先設定K={5,10,15,20,25,30},σ=22,然后對比在不同聚類數下的MVFC-CF算法和MVKFC-CF算法對該數據集的處理能力,實驗結果如圖3所示。

圖3 MVFC-CF和MVKFC-CF在MovieLens-1M數據集上的MAE和THR

由圖3可知,當聚類數目較小時兩算法的差距并不大,而隨著聚類數目的增大,MVKFC-CF算法的優勢就愈加明顯,當聚類數為15時,文中算法在MovieLens-1M數據集上的推薦效果達到最佳,此時MVKFC-CF算法與MVKFC-CF算法的MAE指標絕對差距為0.06,THR的絕對差距為1.6百分點。實驗的評價指標表明,MVKFC-CF算法對于非線性數據的處理能力更強,推薦結果更加精準。

4 結束語

提出了兩種基于多視圖聚類的協同過濾推薦算法,不僅考慮到了多種行為之間的潛在聯系,還考慮到了數據的非線性特點。在多視圖行為的構造上,利用推薦系統中用戶對項目的多樣性行為構建多視圖行為矩陣,同時引入多視圖融合的權重系數來平衡多種行為之間的差異性和關聯性。在相似性評估上,結合用戶與項目之間的同現矩陣,提出新的相似性度量方法和偏好預測方法。

在項目鄰域劃分的優化上,基于多視圖模糊聚類的思想,提出了MVFC-CF算法,利用最大熵方法來自動調節行為權重的分布。進一步地,在MVFC-CF算法的基礎上引入核函數,提出MVKFC-CF算法以增強算法對非線性數據的處理能力。實驗表明,該算法在推薦結果的準確性上相較于其他基于聚類的較為先進的協同過濾算法均有不同程度的提高。即便如此,算法仍有不足之處,下一步將通過引入上下文信息和彌補缺失行為的角度,進一步提高算法的推薦效果。