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

(1.南京郵電大學 現(xiàn)代郵政學院，江蘇 南京 210003；2.南京郵電大學 通信與信息工程學院，江蘇 南京 210003；3.南京郵電大學 物聯(lián)網(wǎng)學院，江蘇 南京 210003)

0 引 言

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

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

1 研究現(xiàn)狀

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

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

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

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

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

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

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

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

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

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

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

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

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

2 算法理論基礎(chǔ)

2.1 基于用戶的協(xié)同過濾推薦算法

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

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

表1 用戶項目評分表

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

(1)

2.2 模糊C均值聚類算法

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

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

(2)

其中，m是加權(quán)指數(shù)，也可以稱為平滑系數(shù)，一般取值為2。

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

1≤i≤n,1≤j≤c

(3)

(4)

3 GAFCM-CF算法

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

圖1 改進FCM的協(xié)同過濾流程

3.1 數(shù)據(jù)預處理

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

3.2 構(gòu)建用戶特征偏好矩陣

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

圖2 用戶偏好特征矩陣構(gòu)建過程

圖2中，矩陣UIn×m為用戶項目評分矩陣，矩陣IFm×k為項目特征隸屬矩陣，矩陣UFPn×k為用戶特征偏好矩陣?？梢酝ㄟ^用戶項目評分矩陣和項目特征隸屬矩陣聚合來構(gòu)建用戶特征偏好矩陣。項目特征隸屬矩陣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)

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

3.3 歸一化處理

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

(7)

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

3.4 GAFCM聚類

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

GAFCM聚類的具體步驟如下：

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

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

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

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

(8)

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

步驟6：若t=tmax，遺傳算法結(jié)束，輸出最終的數(shù)據(jù)，并轉(zhuǎn)入步驟7；否則，令t=t+1，并返回步驟4。

步驟7：根據(jù)全局最優(yōu)解模糊劃分整個數(shù)據(jù)集，輸出聚類中心矩陣，實現(xiàn)用戶聚類劃分。

3.5 用戶相似度計算

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

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

(9)

其中，λ是權(quán)重因子，取值范圍為(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 數(shù)據(jù)集描述

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

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

4.2 實驗設(shè)置及評價指標

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

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

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

(12)

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

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

(13)

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

(14)

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

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

4.3 實驗結(jié)果與分析

首先，對GAFCM-CF算法性能隨權(quán)重因子λ的變化情況進行了分析。該組實驗將相似用戶數(shù)量k值設(shè)置為20，如圖3所示，在相似用戶數(shù)量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隨相似用戶數(shù)量k的變化情況。該組實驗權(quán)重因子λ取值均設(shè)置為0.4。

由圖5可以看出，GAFCM-CF算法、PDSFCM算法和User-CF算法的MAE均隨著相似用戶數(shù)量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均隨著相似用戶數(shù)量k的增大而增大。在k值相同的情況下，GAFCM-CF算法的預測準確率和召回率都比User-CF算法和PDSFCM算法的預測準確率和召回率要高，表明GAFCM-CF算法比User-CF算法和PDSFCM算法具有更好的推薦效果。

圖6 Precision對比分析

圖7 Recall對比分析

5 結(jié)束語

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