張開生， 宋文偉， 李慧貞

(陜西科技大學(xué) 電氣與信息工程學(xué)院， 陜西 西安 710021)

自互聯(lián)網(wǎng)發(fā)展開始，網(wǎng)絡(luò)數(shù)據(jù)呈現(xiàn)出爆炸式的增長趨勢，用戶往往需要消耗大量的精力和時間來篩選自己真正想要的并且有價值的信息。目前，協(xié)同過濾算法是使用最廣泛和最成功的推薦策略，但協(xié)同過濾推薦算法仍然存在稀疏性、可伸縮性、冷啟動等問題。為此，許多學(xué)者提出了各種方法來提高推薦算法的性能。涂丹丹等[1]為解決數(shù)據(jù)稀疏性問題提出了基于聯(lián)合概率矩陣分解的因子模型AdRec，該模型結(jié)合了網(wǎng)頁、廣告和用戶三維數(shù)據(jù)生成推薦結(jié)果?？仔佬赖萚2]提出一種基于標(biāo)簽權(quán)重評分的推薦系統(tǒng)模型，旨在使用標(biāo)簽權(quán)重評分來獲取用戶最準(zhǔn)確的評價和需求，從而生成對用戶的推薦。肖文強(qiáng)等[3]為解決冷啟動問題引入用戶通用評分權(quán)重和熱門項目權(quán)重可提高推薦算法的準(zhǔn)確性。黃震華等[4]引入排序?qū)W習(xí)，以此整合海量用戶、物品特征，建立最貼合用戶偏好需求的用戶模型。為解決伸縮性問題，孫天昊等[5]提出在分布式平臺下，引入并改進(jìn)聚類協(xié)同過濾推薦算法?；诖?，本文對基于模糊聚類的并行推薦算法進(jìn)行了研究,采用PCA(Principal Component Analysis)降維，保留最能代表用戶特征的數(shù)據(jù)，結(jié)合模糊聚類特點，改善傳統(tǒng)協(xié)同過濾中因數(shù)據(jù)稀疏導(dǎo)致的最近鄰劃分不準(zhǔn)確問題，從而提高推薦質(zhì)量。

1 傳統(tǒng)的協(xié)同過濾推薦算法

協(xié)同過濾的主要思想是，在海量數(shù)據(jù)集中探索與用戶品味最相似的K個用戶組成鄰居，并根據(jù)這K個用戶對當(dāng)前用戶未評級項目的打分，預(yù)測當(dāng)前用戶對其未評級項目的評分，最后選擇前n個用于推薦。算法主要由以下3個步驟組成。

1.1 建立用戶評分關(guān)系矩陣

在對用戶的行為數(shù)據(jù)進(jìn)行預(yù)處理之后，用Rm×n表示用戶對推薦對象的評級信息，即用戶評分矩陣：

(1)

其中Rij表示用戶i對對象j的評估。得分可以是一系列值，例如0～5，不同的值表示用戶喜好推薦對象的程度。也可以是0或1，代表用戶喜歡或用戶不喜歡。

1.2 相似度計算

在推薦系統(tǒng)中，對象相似度[6-7]的計算方法是提高推薦準(zhǔn)確性的關(guān)鍵之一?？墒褂媚秤脩魧λ许椖康钠米鳛橄蛄縼碛嬎阌脩糁g的相似性，或?qū)⑺杏脩魧δ稠椖康钠糜米飨蛄縼碛嬎沩椖恐g的相似性。在不同的推薦場景中，所選擇的相似度的計算方法也不同。本文中，Pearson相關(guān)系數(shù)用于計算相似性。Pearson相關(guān)系數(shù)通常用于計算兩個距離變量之間關(guān)系的接近程度，其值在[-1，+1]之間，計算公式如下:

(2)

圖1 傳統(tǒng)協(xié)同過濾 推薦算法流程

1.3 產(chǎn)生推薦

對計算出的相似度排序，選取用戶的前N個最近鄰居，可以對該用戶未評分的項目進(jìn)行預(yù)測，預(yù)測方法如下:

(3)

2 基于模糊聚類的并行推薦算法研究

雖然傳統(tǒng)的協(xié)同過濾推薦算法被廣泛使用，但在實際應(yīng)用中經(jīng)常存在一些挑戰(zhàn)和不足。由于傳統(tǒng)的協(xié)同過濾算法相似度計算，需要遍歷整個用戶物品矩陣，隨用戶量和物品量的增長，計算量持續(xù)增加，響應(yīng)推薦請求的系統(tǒng)效率降低，存儲器開銷也隨之增加。使用明尼蘇達(dá)大學(xué)項目研究組Grouplens發(fā)布的MovieLens數(shù)據(jù)集，當(dāng)鄰居N數(shù)量為10且推薦數(shù)量為30時，統(tǒng)計傳統(tǒng)協(xié)同過濾推薦算法的平均推薦耗時，其中抽樣等級S1(2555-250)表示從2555個用戶中抽取250個用戶，抽樣等級S2(1915-190)表示從1915個用戶中抽取190個用戶，如表1所示。

表1 傳統(tǒng)的協(xié)同過濾推薦耗時

可知，在整體數(shù)據(jù)集用戶數(shù)量只有3883，電影數(shù)量只有6040部的情況下，傳統(tǒng)協(xié)同過濾推薦算法的運行時間至少大于1 min。在實際應(yīng)用中，面對數(shù)以萬計的用戶及推薦對象，單憑這樣的推薦速度會嚴(yán)重影響用戶體驗。為此，本文研究了一種基于模糊聚類的并行推薦算法。針對數(shù)據(jù)維度高、計算量大的問題，原始數(shù)據(jù)由PCA技術(shù)和FCM(Fuzzy C-means)聚類預(yù)處理,降低數(shù)據(jù)維度、減少計算次數(shù)。后利用得到的聚類簇集合建立最近鄰集合，生成基本預(yù)測評分并作出推薦。以上操作均在Hadoop集群上運用MapReduce[8]計算框架完成。算法流程如圖2所示。

圖2 并行推薦算法流程

2.1 PCA降維

在實際使用時，推薦系統(tǒng)中的用戶數(shù)量和推薦對象的數(shù)量非常大，并且生成的用戶項目矩陣維度非常高。迫切需要引入降維方法進(jìn)行優(yōu)化，PCA正是一種在盡可能減少信息損失的情況下降低數(shù)據(jù)維度的方法，通過正交變化，可以用少量新變量來解釋原始數(shù)據(jù)的大部分信息[9]。通常，提取原始數(shù)據(jù)中95%的信息就可以實現(xiàn)良好的降維效果。算法描述如下：

Ⅰ 輸入m×n的初始數(shù)據(jù)矩陣X和設(shè)定的主成分?jǐn)?shù)量k；

Ⅱ 計算初始數(shù)據(jù)矩陣X的協(xié)方差矩陣Cn×n；

Ⅲ 對協(xié)方差矩陣Cn×n作奇異值分解，計算協(xié)方差矩陣Cn×n的特征值和特征向量e1、e2、…、en，返回由特征向量組成的n×n降維矩陣U，其中矩陣U上每列數(shù)據(jù)都是一個特征向量；

Ⅳ 取出降維后矩陣U的前k列數(shù)據(jù)，得到n×k的投影矩陣P；

Ⅴ 最后原矩陣X乘以投影矩陣P，得到目標(biāo)矩陣。

2.2 模糊C均值聚類

模糊C均值聚類(FCM)算法是對早期硬C均值聚類(HCM)算法的一種改進(jìn)，其主要思想是通過隸屬度來表達(dá)各數(shù)據(jù)點隸屬某聚類的程度。FCM的主要改進(jìn)在于摒棄了暴力的0、1取值，F(xiàn)CM用模糊劃分，隸屬度采用[0,1]取值區(qū)間來確定[10]。算法描述如下：給定數(shù)據(jù)集X={x1,x2,…,xn}包括n個樣本，數(shù)據(jù)集可以劃分為c(1≤c≤n)類，那么，F(xiàn)CM的目標(biāo)函數(shù)可定義為：

(4)

其中U表示隸屬度矩陣,uij∈[0,1],ci表示組i的聚類中心,dij=‖Hi-Xj‖表示數(shù)據(jù)點j與各聚類中心之間的歐式距離,m∈[1,+∞)是一個加權(quán)指數(shù)。使(4)式逼近最小值的必要條件為

(5)

(6)

算法主要步驟如下:

步驟1:用隨機(jī)生成的[0,1]區(qū)間內(nèi)的數(shù)來初始化隸屬度矩陣;

步驟2:用式(5)對各聚類中心進(jìn)行初始化;

步驟3:通過式(4)得到目標(biāo)函數(shù)，多次迭代，若目標(biāo)函數(shù)的變化量小于ε(ε表示非常小的數(shù))，算法停止;

步驟4:用式(6)更新隸屬度矩陣，回到步驟2執(zhí)行。

3 基于模糊聚類的并行推薦算法的流程

3.1 建立用戶模糊簇關(guān)系矩陣

通過對原始數(shù)據(jù)進(jìn)行模糊聚類，得到相應(yīng)的模糊簇，用式(7)計算項目對各模糊簇的隸屬度：

(7)

其中xi、mj分別代表各項目和各簇中心的屬性特征向量，‖xi-mj‖表示項目i與各簇中心的歐氏距離，c表示簇數(shù)量。

通過原始數(shù)據(jù)中用戶評分和各項目對簇的隸屬度，用式(8)計算用戶u對各個簇j的偏好值，從而建立用戶-模糊簇關(guān)系矩陣：

(8)

式中Su,j表示用戶u對簇j的偏好值，Ru,i表示用戶u對歸屬于簇j的項目i的偏好值，Iu表示u個用戶建立的用戶評分集合。對用戶-模糊簇關(guān)系矩陣進(jìn)行PCA降維計算，舍棄掉特征值較小或為0的特征向量，計算每一維數(shù)據(jù)的投影，該投影矩陣即為該樣本集合的主成分。

3.2 構(gòu)建最近鄰集合

獲取降維后的用戶模糊簇關(guān)系矩陣，用式(2)計算用戶間相似度值，生成用戶的最近鄰集合。

3.3 得出推薦結(jié)果

從最近鄰集合中獲取與當(dāng)前用戶具有最高相似度的m個鄰居。根據(jù)式(3)預(yù)測鄰居購買但未被目標(biāo)用戶購買的項目分?jǐn)?shù)，并選擇Top-N進(jìn)行推薦。

4 實驗仿真與分析

4.1 實驗環(huán)境

根據(jù)以上研究，使用5臺PC機(jī)搭建Hadoop平臺，包括1個Master節(jié)點和4個Slave節(jié)點，運行環(huán)境為Ubuntu14.04，Hadoop版本為2.6.0，集群配置[11]如表2所示。

表2 Hadoop集群配置信息

4.2 數(shù)據(jù)集合

實驗主要采用明尼蘇達(dá)大學(xué)GroupsLens小組發(fā)布的Movielens數(shù)據(jù)集，從http://grouplens.org/datasets/movielens/站點下載大小分別100 KB、1 MB、10 MB的數(shù)據(jù)集進(jìn)行實驗。各數(shù)據(jù)集內(nèi)容如下：(1)100 KB：共有943位用戶評分了1628部電影，共計90 582個記錄；(2)1 MB：共有6040位用戶評分3900部電影，總計1 000 209個記錄；(3)10 MB：共有71 567位用戶對10 681部電影評分，總計10 000 054個記錄。分?jǐn)?shù)從1～5，值越高，用戶對電影的喜愛程度越高。

4.3 度量標(biāo)準(zhǔn)

推薦系統(tǒng)的評估標(biāo)準(zhǔn)可以反映推薦系統(tǒng)預(yù)測用戶行為的能力，本文主要測量平均絕對誤差(MAE)和加速比。平均絕對誤差方法是推薦精度的常用度量方法。加速比是在單處理器系統(tǒng)和并行處理器系統(tǒng)中運行相同任務(wù)所花費的時間的比率，通常用于衡量并行系統(tǒng)或程序并行化的性能和效果[12]。

設(shè)pi是系統(tǒng)對項目i的預(yù)測得分，ri是用戶項目的實際得分，N是預(yù)測項目數(shù),MAE可定義為

(9)

設(shè)Tp表示存在p個處理器時并行算法的執(zhí)行時間，T1表示順序執(zhí)行算法的執(zhí)行時間,加速比可定義為

(10)

4.4 實驗過程及分析

(1)MAE比較

如表3所示，取100 KB數(shù)據(jù)集作為實驗數(shù)據(jù)，選取用戶數(shù)量分別為25、100、200、400、800的集合作

表3 實驗數(shù)據(jù)

為本實驗的5組實驗數(shù)據(jù)。隨機(jī)選擇組中80%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，并將20%的數(shù)據(jù)用作每組實驗數(shù)據(jù)中的測試數(shù)據(jù)。

圖3將本文研究的基于模糊聚類的并行推薦算法，同傳統(tǒng)協(xié)同過濾和基于PCA降維的協(xié)同過濾做性能上的對比分析。從圖中可以看出，本文算法具有較小的MAE并且MAE值隨著實驗數(shù)據(jù)量的增加而減小，這意味著推薦精度的不斷提高。PCA降維將最能反映用戶興趣的特征保留下來，剔除了噪聲數(shù)據(jù)，改善了數(shù)據(jù)稀疏性,降低了計算復(fù)雜度，故傳統(tǒng)CF算法的MAE值明顯較大。

(2)加速比分析

本實驗通過逐個增加DataNode節(jié)點個數(shù)改變Hadoop集群的處理能力，比較得出在不同規(guī)模的Hadoop集群下執(zhí)行算法對算法執(zhí)行效率的影響。分別在1—4臺計算節(jié)點上對MovieLens在100 KB、1 MB、10 MB三個不同數(shù)據(jù)集進(jìn)行加速比計算，繪制加速比曲線圖如圖4所示。

圖3 MAE對比圖 圖4 加速比曲線圖

從圖4看出，隨節(jié)點個數(shù)遞增，處于3種不同數(shù)據(jù)集下的算法加速比也遞增。若數(shù)據(jù)集保持不變，加速比隨節(jié)點數(shù)量的增加而增大。若數(shù)據(jù)集改變時，數(shù)據(jù)集越大，加速比隨節(jié)點數(shù)量增大的幅度越大。當(dāng)節(jié)點數(shù)量小于3時，節(jié)點不僅需要處理計算任務(wù)，還需要調(diào)度資源，故加速比變化率較小。但是，當(dāng)集群中的DataNode節(jié)點數(shù)大于3時，加速比線性增加。因此，本文算法可以提高推薦效率，并在并行化環(huán)境中具有可擴(kuò)展性。