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

張開生， 宋文偉， 李慧貞

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

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

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

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

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

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

(1)

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

1.2 相似度計(jì)算

在推薦系統(tǒng)中，對(duì)象相似度[6-7]的計(jì)算方法是提高推薦準(zhǔn)確性的關(guān)鍵之一?？墒褂媚秤脩魧?duì)所有項(xiàng)目的偏好作為向量來計(jì)算用戶之間的相似性，或?qū)⑺杏脩魧?duì)某項(xiàng)目的偏好用作向量來計(jì)算項(xiàng)目之間的相似性。在不同的推薦場(chǎng)景中，所選擇的相似度的計(jì)算方法也不同。本文中，Pearson相關(guān)系數(shù)用于計(jì)算相似性。Pearson相關(guān)系數(shù)通常用于計(jì)算兩個(gè)距離變量之間關(guān)系的接近程度，其值在[-1，+1]之間，計(jì)算公式如下:

(2)

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

1.3 產(chǎn)生推薦

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

(3)

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

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

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

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

圖2 并行推薦算法流程

2.1 PCA降維

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

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

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

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

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

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

2.2 模糊C均值聚類

模糊C均值聚類(FCM)算法是對(duì)早期硬C均值聚類(HCM)算法的一種改進(jìn)，其主要思想是通過隸屬度來表達(dá)各數(shù)據(jù)點(diǎn)隸屬某聚類的程度。FCM的主要改進(jìn)在于摒棄了暴力的0、1取值，F(xiàn)CM用模糊劃分，隸屬度采用[0,1]取值區(qū)間來確定[10]。算法描述如下：給定數(shù)據(jù)集X={x1,x2,…,xn}包括n個(gè)樣本，數(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ù)點(diǎn)j與各聚類中心之間的歐式距離,m∈[1,+∞)是一個(gè)加權(quán)指數(shù)。使(4)式逼近最小值的必要條件為

(5)

(6)

算法主要步驟如下:

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

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

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

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

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

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

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

(7)

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

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

(8)

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

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

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

3.3 得出推薦結(jié)果

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

4 實(shí)驗(yàn)仿真與分析

4.1 實(shí)驗(yàn)環(huán)境

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

表2 Hadoop集群配置信息

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

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

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

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

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

(9)

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

(10)

4.4 實(shí)驗(yàn)過程及分析

(1)MAE比較

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

表3 實(shí)驗(yàn)數(shù)據(jù)

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

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

(2)加速比分析

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

圖3 MAE對(duì)比圖 圖4 加速比曲線圖

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