基于FCM用戶聚類的協同過濾推薦算法

趙學健，張雨豪，陳 昊，劉 旭，李朋起

(1.南京郵電大學 現代郵政學院，江蘇 南京 210003；2.南京郵電大學 通信與信息工程學院，江蘇 南京 210003；3.南京郵電大學 物聯網學院，江蘇 南京 210003)

0 引 言

信息技術和互聯網技術的迅猛發展，使得數據量呈指數性爆炸，人民逐漸從信息匱乏的時代走入了信息過載的時代[1]。無論是信息生產者還是銷售者都遇到了很大的挑戰，對于消費者而言，海量的數據篩選，獲取有效信息越來越困難；生產者為了滿足客戶需求，生產有價值的信息，變得越來越困難。推薦算法是一種有效的信息處理工具，通過用戶的歷史行為信息，將用戶和商品聯系起來，解決信息過載的問題。目前，推薦算法已經成功應用到電子商務、在線音視頻網站以及社交網絡平臺等各個領域。亞馬遜的前首席科學家Andreas Weigend提及亞馬遜有20%～30%的銷售來自于推薦系統[2]。

推薦算法是推薦過程的重要組成部分，為推薦系統的核心內容。目前有許多種推薦算法，常見的推薦算法有基于人口學的推薦算法、基于內容的推薦算法、基于關聯規則推薦算法、協同過濾推薦算法、混合推薦算法。而協同過濾推薦算法是目前發展最為成熟、應用最為廣泛的個性化推薦技術之一。協同過濾算法可以分為基于內存(memory-based)的和基于模型(model-based)的兩類[3]。其中基于內存的協同過濾推薦算法又可以分為基于用戶的協同過濾算法和基于項目的協同過濾算法。

1 研究現狀

隨著電子商務深入人心，用戶和項目的數量急劇增加，這使得協同過濾推薦算法計算量巨大，時間復雜度和空間復雜度都極大。另一方面，單個用戶所關注的項目通常都很少，這又導致用戶的評分矩陣極其稀疏，使得推薦系統的精度大大降低。近年來，研究者開始借助聚類方法來解決協同過濾推薦過程中的數據稀疏性和推薦精度降低的問題。

文獻[4]提出了一個新的基于Web的推薦系統，該系統基于用戶在Web頁面上瀏覽的順序信息，采用模糊C均值聚類算法為目標用戶確定相似用戶，并評估每個網頁的權重，來預測推薦用戶的下一次訪問網頁，極大提高了現有推薦系統的精度。

文獻[5]提出一種用于醫學圖像模糊聚類與直覺模糊推薦結合的混合推薦模型-HIFCF(hybrid intuitionistic fuzzy collaborative filtering)。該模型比傳統的模糊集合或單純的推薦系統具有更好的預測精度。

文獻[6]提出一種新的社交推薦模型，該模型首先將描述多個領域用戶偏好的用戶偏好矩陣形式化，然后利用偏距離策略模糊C-均值聚類算法-PDSFCM (partial distance strategy fuzzy c-means)得到用戶聚類分組，然后設計了一個基于聚類的社交正則化項，將聚類關系與傳統的矩陣分解模型進行融合，用以進一步提高推薦算法的精度。

文獻[7]提出一種新的基于聚類的協同過濾方法-CBCF(clustering-based collaborative filtering)，該方法基于用戶評分數據建立激勵/懲罰用戶模型，對用戶進行聚類，在不需要更多先驗信息的情況下，提高了推薦的準確性。

文獻[8]將單領域基于聚類的矩陣分解方法擴展應用到多領域推薦，所提出的推薦方法可以更有效地利用來自輔助域的數據來獲得更好的推薦效果，特別是對于冷啟動用戶。

文獻[9]在2010年通過提出一種基于用戶偏好模糊聚類的協同過濾推薦，用以解決推薦過程中的數據稀疏性和伸縮性。該方法將用戶項評分矩陣轉換為用戶類矩陣，因此大大提高了矩陣中數據的密度。然后，使用模糊C均值算法將用戶模糊地分為不同的組。采用模糊C均值聚類可以讓每個用戶屬于不同的組，可以更為有效地捕獲用戶的各種偏好。

文獻[10]在2015年提出了一種結合FCM和Slope One算法[11]的協同過濾推薦方法，該方法針對推薦算法的數據稀疏性問題，首先使用基于FCM聚類的Slope One算法來預測未評分的數據，然后通過基于用戶的協同過濾推薦算法來實現推薦。

文獻[12]為了提高推薦質量，將信任關系融合到推薦系統中，采用模糊C聚類算法，對信任關系進行聚類。利用信任類預測用戶間的隱式信任，最后將信任關系與用戶-項目關系線性融合進行推薦。實驗表明該算法能夠大幅度地改進推薦質量，提升算法的時間效率。

文獻[13]為了克服評級數據的稀疏性問題，提出了一種新穎的稀疏性消除方法，該方法結合了評級和電影題材特征，應用模糊C均值聚類技術對電影進行聚類。該方案結合了評分和電影的題材來預測未評分數據，有效提升了推薦質量。

文獻[14]提出了一種基于對用戶真實性信息應用模糊C均值聚類的協作過濾模型。該文獻提出一種新的度量用戶相似度的方式，該公式結合了用戶的使用組合系數對模糊真實性信息進行評級，在數據稀疏和冷啟動條件下，推薦效果更佳。

文獻[15]針對推薦算法的數據稀疏性和冷啟動問題，將聚類算法和關聯規則生成算法相結合，首先根據用戶相似度對評分矩陣進行聚類，然后將聚類數據轉換成布爾數據，并生成高效的關聯規則，最后進行基于規則的推薦。實驗表明，該方法不僅降低了推薦系統的稀疏度，而且提高了推薦系統的精度。

通過上述分析，可以看出當前借助聚類方法的協同過濾推薦通常只考慮了用戶的顯性特征進行聚類，沒有考慮到項目的隱性特征；另一方面，當前采用模糊C均值聚類方法對用戶進行聚類時，該算法容易收斂于局部極小值點，有時難以取得目標函數的全局最小值。因此，該文提出一種基于FCM用戶聚類的協同過濾推薦算法GAFCM-CF(genetic algorithm based fuzzy c-means collaborative filtering)。該算法首先結合用戶評分和項目特征構建用戶特征偏好矩陣，然后采用模糊C均值聚類算法對用戶進行聚類。此外，該算法為了防止模糊C均值聚類算法收斂于局部極小值，影響推薦質量，采用遺傳算法對模糊C均值聚類算法進行了改進，以防止模糊C均值聚類算法出現局部最優解。實驗結果表明，所提出的基于改進FCM的協同過濾推薦算法GAFCM-CF相比于傳統的基于用戶的協同過濾推薦算法具有更好的推薦質量。

2 算法理論基礎

2.1 基于用戶的協同過濾推薦算法

基于用戶的協同過濾算法是推薦系統中比較古老的推薦算法，這個算法的誕生標志著推薦算法的誕生。該算法利用目標用戶的歷史行為信息，挖掘與目標用戶具有高相似度的近鄰用戶集合，然后根據用戶對此項目的評分來預測目標用戶對該商品的相應的評分，之后再從預測的評分中選擇靠前的Top-K個項目推薦給用戶。

基于用戶的協同過濾算法中，用戶-項目評分矩陣Rm×n是算法的基礎，如表1所示。該矩陣中，每行對應一個用戶，每列對應一個項目，每個矩陣元素ri,j表示用戶i對項目j的評分，當用戶沒有對項目進行評分時，ri,j為0或者NULL。

表1 用戶項目評分表

在基于用戶的協同過濾推薦算法中，可以選擇皮爾遜相關系數、余弦相似度等不同的相似度計算方法。皮爾遜相關系數計算方法如公式(1)所示：

(1)

2.2 模糊C均值聚類算法

模糊C均值聚類算法(fuzzy c-means，FCM)是在硬C均值聚類算法模型基礎上融合了模糊理論的精髓進一步推理得到的。硬C均值聚類算法要求每個用戶只能明確屬于某一個類之中，然而模糊C聚類可以提供更加靈活的聚類結果，它可以將每一個目標對象劃分到多個類中。

假設數據集X={x1,x2,…,xn}?Rd×n，其中n為數據集的個數，d為數據集的維度。模糊C均值聚類算法將數據集劃分成k個子集，則對應生成模糊劃分矩陣U，cj(j=1,2,…,k)為每個聚類的中心，可記錄為C，μi,j是第i個樣本對應第j類的隸屬度函數，則基于隸屬度函數的聚類損失函數如公式(2)所示：

(2)

其中，m是加權指數，也可以稱為平滑系數，一般取值為2。

模糊C均值聚類算法首先計算各個用戶和聚類中心之間的距離，然后計算出用戶對各聚類中心的隸屬度矩陣，通過比較用戶在各個聚類中心隸屬度的大小，將用戶分配到隸屬度最大的用戶簇中，使得在同一個用戶簇之中用戶與用戶的相似度最高，降低不同用戶簇中用戶之間的相似度。使得聚類函數最小的必要條件為cj和μi,j分別滿足公式(3)和公式(4)：

1≤i≤n,1≤j≤c

(3)

(4)

3 GAFCM-CF算法

該文提出的GAFCM-CF算法包括數據預處理，用戶特征偏好矩陣構建，矩陣歸一化處理，GAFCM聚類，用戶相似度計算，目標項目評估及推薦六個步驟，如圖1所示。算法的核心是用戶特征偏好特征矩陣的構建和融合遺傳算法對模糊C均值聚類算法進行改進，實現對用戶的聚類分析，防止模糊C均值聚類算法出現局部最優解。

圖1 改進FCM的協同過濾流程

3.1 數據預處理

數據預處理主要負責從原始數據中提取用戶特征和項目特征數據并進行數據清洗操作，獲得特定格式的數據集，并構建項目特征隸屬矩陣和用戶項目評分矩陣。

3.2 構建用戶特征偏好矩陣

時間復雜度、空間復雜度高以及評分矩陣稀疏問題是協同過濾算法目前所面臨的主要問題。為了解決用戶評分矩陣的稀疏性問題，GAFCM-CF算法通過利用用戶項目評分矩陣和項目特征隸屬矩陣來構建用戶特征偏好矩陣，構建方法如圖2所示。

圖2 用戶偏好特征矩陣構建過程

圖2中，矩陣UIn×m為用戶項目評分矩陣，矩陣IFm×k為項目特征隸屬矩陣，矩陣UFPn×k為用戶特征偏好矩陣。可以通過用戶項目評分矩陣和項目特征隸屬矩陣聚合來構建用戶特征偏好矩陣。項目特征隸屬矩陣IFm×k中的元素取值為0或1，滿足公式(5):

(5)

用戶u對項目的評分向量為ru=(ru,1,ru,2,…,ru,m)，項目i對應特征的隸屬向量為fi=(f1,i,f2,i,…,fm,i)，Rui計算過程如式(6)所示：

(6)

該方法中用戶項目評分矩陣通常都是稀疏矩陣，這是由于用戶數量和項目數量極多，而單個用戶關聯的項目數量極少。項目特征隸屬矩陣中k的取值通常遠小于用戶評分矩陣中項目的數量m，因此通過該方法獲得的用戶對項目特征的偏好矩陣相對于用戶項目評分矩陣維度得到了極大降低，有利于降低推薦算法的時間和空間復雜度。

3.3 歸一化處理

對UFP矩陣進行min-max歸一化處理，將矩陣各元素數值映射到區間[0，1]，映射公式如下所示：

(7)

其中，xi,j為矩陣第i行第j列對應的元素值，在UFP矩陣中表示用戶i對項目特征j的偏愛程度，xmin為所有用戶對項目特征偏愛程度中的最小值，xmax為所有用戶對項目特征偏愛程度的最大值。

3.4 GAFCM聚類

GAFCM-CF算法為了達到快速收斂并避免局部最優，將遺傳算法與FCM的算法融合，通過FCM算法使數據快速高效地趨于各自的極值點，又可以通過遺傳算法擺脫數據在收斂過程中可能陷入的局部最小值的問題[16]。

GAFCM聚類的具體步驟如下：

步驟1：對原始數據進行預處理，構建用戶偏好特征矩陣UFP并對其進行歸一化處理。

步驟2：參數初始化，初始化GAFCM算法的相關參數，包括種群大小M，交叉概率Pc，變異概率Pm，最大迭代次數tmax，聚類簇數c，隸屬度因子m，收斂精度ε。

步驟3：編碼及種群初始化，根據公式進行編碼，并隨機產生一個種群X，X中有n個研究對象作為初始個體，即X=[x1,x2,…,xn]。

步驟4：計算個體適應度：

(8)

步驟5：對當前種群執行選擇、交叉和變異操作，產生新一代個體。

步驟6：若t=tmax，遺傳算法結束，輸出最終的數據，并轉入步驟7；否則，令t=t+1，并返回步驟4。

步驟7：根據全局最優解模糊劃分整個數據集，輸出聚類中心矩陣，實現用戶聚類劃分。

3.5 用戶相似度計算

為計算用戶的相似度，GAFCM-CF算法通過綜合利用用戶特征偏好矩陣以及用戶項目評分矩陣來實現，既包含原始用戶項目評分矩陣的顯性信息，又考慮到用戶對項目特征偏好的隱性信息，如公式(9)所示：

Sim(u,v)=λSim1(u,v)+(1-λ)Sim2(u,v)

(9)

其中，λ是權重因子，取值范圍為(0,1)；Sim(u,v)表示用戶u和用戶v的綜合相似度；Sim1(u,v)表示通過公式(1)計算得到的相似度，是使用原始用戶項目評分矩陣得到的；Sim2(u,v)表示使用用戶對項目特征偏好矩陣得到的相似度，可以通過公式(10)獲得：

Sim(u,v)2=

(10)

3.6 目標項目評估

用戶u對項目i的評分計算公式為：

(11)

4 實驗分析

4.1 數據集描述

該文采用MovieLens 100k數據集驗證算法的性能。該數據集包括1 682部電影中的943位用戶的100 000個評分，數據集稀疏度為93.7%(用戶未評分數量占用戶最大評分數量的比例)。用戶對電影的評分區間為1～5分，每個用戶至少評分20部電影，用戶對某電影的評分值越高表明用戶對該電影喜愛程度越大。

該文將原始數據集隨機劃分為5部分，使用5折交叉驗證方式，每次將其中4部分用于訓練，剩下的1部分用于測試，將5次實驗的平均值作為實驗結果。

4.2 實驗設置及評價指標

該文主要通過平均絕對誤差(mean absolute error，MAE)、準確率(Precision)和召回率(Recall)三個指標對算法的性能進行分析。

MAE是衡量預測評分的準確性的重要指標，通過比較預測評分和真實評分之間的平均絕對誤差計算得出。MAE值越小，則表示預測評分與真實評分越接近，算法精度也就越高。Precision表示正樣本在預測為正的樣本中所占的比例，即用戶發生行為項目占推薦項目的比例。Recall表示預測為正樣本占正樣本的比例，即推薦項目占用戶產生行為項目的比例。顯然，Precision和Recall越大，說明算法的推薦精度越高。

MAE可以通過公式(12)進行計算：

(12)

其中，pu,i表示用戶u對項目i的預測評分，ru,i表示用戶u對項目i的真實評分,n表示用戶u所評分的項目的數量。

Precision可以通過公式(13)進行計算：

(13)

Recall可以通過公式(14)進行計算：

(14)

上述公式(13)和公式(14)中，U表示所有項目的集合，R(u)表示給用戶u推薦的項目集合，T(u)表示用戶u發生行為的項目的集合。

實驗相關參數設置如下：模糊聚類分類數c=8，隸屬度因子m=2，迭代次數t=50，交叉概率Pc=0.6，變異概率Pm=0.1，收斂精度ε=0.000 1。

4.3 實驗結果與分析

首先，對GAFCM-CF算法性能隨權重因子λ的變化情況進行了分析。該組實驗將相似用戶數量k值設置為20，如圖3所示，在相似用戶數量k=15時，隨著λ取值逐漸增大，準確率和召回率變化趨勢均為先增大后減小，并且在λ=0.4時，準確率和召回率達到峰值，分別為0.251和0.129。由圖4可以看出，隨著λ取值逐漸增大，平均絕對誤差MAE變化趨勢為先減小后增大，并且在λ=0.4時，平均絕對誤差取得最小值0.466。

圖3 λ取值對Precision和Recall的影響分析

圖4 λ取值對MAE的影響分析

其次，將GAFCM-CF算法與文獻[6]提出的PDSFCM算法、User-CF算法的進行性能對比，分析了三種算法的MAE、Precision和Recall隨相似用戶數量k的變化情況。該組實驗權重因子λ取值均設置為0.4。

由圖5可以看出，GAFCM-CF算法、PDSFCM算法和User-CF算法的MAE均隨著相似用戶數量k的增大而減小。在k值相同的情況下，GAFCM-CF算法的MAE均比PDSFCM算法與User-CF算法的MAE要小，表明GAFCM-CF算法比User-CF算法和PDSFCM算法具有更好的精度。

圖5 MAE對比分析

由圖6和圖7可以看出，GAFCM-CF算法、PDSFCM算法及User-CF算法的Precision和Recall均隨著相似用戶數量k的增大而增大。在k值相同的情況下，GAFCM-CF算法的預測準確率和召回率都比User-CF算法和PDSFCM算法的預測準確率和召回率要高，表明GAFCM-CF算法比User-CF算法和PDSFCM算法具有更好的推薦效果。

圖6 Precision對比分析

圖7 Recall對比分析

5 結束語

針對傳統協同過濾推薦算法中存在的數據稀疏性及推薦準確率低的問題，提出了一種基于改進FCM的協同過濾推薦算法GAFCM-CF。實驗結果表明，相比于傳統的基于用戶的協同過濾推薦算法，該算法具有更高的推薦質量以及推薦準確率。未來工作中，將考慮進一步挖掘用戶隱藏信息，進一步提升推薦算法的準確率；另一方面，將對算法的復雜度和其他方面的推薦性能，比如推薦物品的覆蓋率、流行度、驚喜度等進行更全面的評估。