趙恩毅 王瑞剛

（西安郵電大學(xué)物聯(lián)網(wǎng)與兩化融合研究院 西安 710061）

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，它為人們提供越來越多的信息和服務(wù)的同時，也使得人們從信息缺乏的時代逐步踏進(jìn)信息過載的時代。智能推薦系統(tǒng)的到來，使用戶能夠更加便捷地在網(wǎng)絡(luò)中獲取到自己所感興趣的話題。推薦系統(tǒng)通過對無用信息進(jìn)行篩選過濾來為用戶推送有用信息，從而提升了用戶獲取信息的效率［1］。其中推薦算法則是推薦系統(tǒng)中的關(guān)鍵所在，它能夠決定一個推薦系統(tǒng)性能的優(yōu)劣，而協(xié)同過濾推薦是推薦算法中性能效果比較好的策略之一［2］。

然而大數(shù)據(jù)時代的到來讓海量數(shù)據(jù)的存儲與計算效率面臨巨大挑戰(zhàn)。傳統(tǒng)單機(jī)上的協(xié)同過濾在運(yùn)算效率和計算復(fù)雜度上都不能滿足超大量信息處理的需要。因此分布式推薦成為推薦算法研究中一個新的研究方向［3］，本文將設(shè)計一種基于Hadoop 平臺的分布式聚類協(xié)同過濾推薦算法。首先對K-means 聚類算法進(jìn)行改進(jìn)，然后在MapReduce 計算框架下對其實(shí)現(xiàn)分布式聚類［4］。改進(jìn)聚類算法利用最大-最小值思想得出聚類中心，能夠有效降低算法并行計算時的迭代次數(shù)。同時在MapReduce 框架下將Map 端所產(chǎn)生的同簇數(shù)據(jù)傳輸?shù)紺ombiner 類中，避免了Reduce 端所接收數(shù)據(jù)量過大而影響傳輸效率。然后在傳統(tǒng)協(xié)同過濾算法的基礎(chǔ)上，通過大數(shù)據(jù)平臺實(shí)現(xiàn)一種基于改進(jìn)K-means聚類的協(xié)同過濾推薦算法，進(jìn)而改善了推薦系統(tǒng)在大數(shù)據(jù)環(huán)境中存在的稀疏性和可擴(kuò)展性問題，同時算法的運(yùn)行速率以及推薦精度也得以提升。

2 分布式聚類協(xié)同過濾推薦算法

針對傳統(tǒng)協(xié)同過濾推薦算法在數(shù)據(jù)稀疏性和準(zhǔn)確度等方面存有缺陷，提出在利用Hadoop 分布式計算平臺所具備的計算大規(guī)模數(shù)據(jù)等優(yōu)勢的同時，通過聚類模型來構(gòu)建高精度的推薦算法［5］。其中Hadoop 是開源的分布式計算框架，它有分布式文件系統(tǒng)HDFS 和支持一個MapReduce 范式的實(shí)現(xiàn)。該分布式聚類協(xié)同過濾推薦算法不但使推薦精度提升，并且在數(shù)據(jù)的稀疏性和可擴(kuò)展性方面也得以解決［6］。針對分布式環(huán)境下的高維復(fù)雜數(shù)據(jù)，首先對其做降維處理，數(shù)據(jù)預(yù)處理之后經(jīng)過改進(jìn)的K-means 聚類模型計算出恰當(dāng)?shù)木垲惔?，最后在Hadoop 分布式計算框架下通過協(xié)同過濾結(jié)合聚類的方法構(gòu)成推薦列表［7］。圖1為推薦算法流程。

圖1 基于大數(shù)據(jù)平臺下分布式聚類協(xié)同過濾推薦算法流程

2.1 對數(shù)據(jù)做預(yù)處理

復(fù)雜的初始數(shù)據(jù)只有經(jīng)過預(yù)處理之后，在后期運(yùn)用中才能夠被高效利用［8］。在這里可以將數(shù)據(jù)定義作屬性集合，其中屬性則是特征信息。通常在推薦系統(tǒng)中的數(shù)據(jù)較為復(fù)雜，不但存有高維空間特征，并且在空間中表現(xiàn)較為稀疏［9］。通過對數(shù)據(jù)降維，可以高效地將復(fù)雜高維空間轉(zhuǎn)為簡單低維空間［10］。其中，在奇異值分解方法中，集合中的任何特征信息的概念強(qiáng)度都通過計算得來。另外，針對協(xié)同過濾推薦算法，矩陣分解技術(shù)能夠有效解決其數(shù)據(jù)稀疏性以及可擴(kuò)展性問題［11］。本文在Hadoop分布式計算框架下采用交替最小二乘迭代（ALS）矩陣分解技術(shù)對初始矩陣做處理，其中 ||u × ||τ user-item 評價打分矩陣R（秩為n）可以粗略定義為矩陣=PQT。

最小誤差等同于對R 值做奇異值分解處理：

其中U 表示 ||u ×n 矩陣，V 表示 ||τ ×n 矩陣，∑是n×n 對角化矩陣。下面提取前k 個最大奇異值所對應(yīng)的向量矩陣，Uk，Vk，能夠得出用戶-矩陣和物品-矩陣可定義為

該模型相應(yīng)的評分預(yù)測rui可定義為

當(dāng)學(xué)習(xí)P 和Q 時，可利用已知評分：

其中λ 被定義為控制正則化參數(shù)。

2.2 改進(jìn)聚類算法MapReduce并行化實(shí)現(xiàn)

K-means算法在傳統(tǒng)聚類方法中相對簡單高效，但傳統(tǒng)K-means 算法的聚類結(jié)果卻不夠穩(wěn)定［12］。原因是傳統(tǒng)K-means 算法在初始聚類中心點(diǎn)和K值的選取上通常是根據(jù)用戶自身經(jīng)驗(yàn)來設(shè)定，在這個過程中往往需要用戶重復(fù)試驗(yàn)來提升設(shè)定值的準(zhǔn)確度［13］。那么在沒有用戶的經(jīng)驗(yàn)情況下，如何通過準(zhǔn)確計算來確定K-means 算法的初始聚類中心和K值，本文對傳統(tǒng)K-means聚類算法做出改進(jìn)。

對于如何來高效設(shè)定初始聚類中心點(diǎn)，可以在Hadoop 分布式計算框架下采用最大值-最小值方法來計算獲?。?4］。用該方法不但可以降低計算過程中迭代次數(shù)，并且能夠避免聚類中心在選取時發(fā)生點(diǎn)與點(diǎn)過于鄰近的情況。該方法利用歐式距離來確保聚類中心點(diǎn)之間的距離值足夠大。假定對象集合為{ x1，x2，???，xm} ，算法的實(shí)現(xiàn)步驟如下：

1）假設(shè)θ( 0 ＜θ ＜1) ，選取距離原點(diǎn)最遠(yuǎn)的點(diǎn)x1和距離原點(diǎn)最近的點(diǎn)x2作為初始聚類中心點(diǎn)c1和c2，記x1，x2兩點(diǎn)之間的距離為D。

2）計算出剩余點(diǎn)與c1，c2點(diǎn)的距離，找出與c1點(diǎn)和c2點(diǎn)距離值最小的點(diǎn)d1和d2得出max( d1，d2)，其中max( d1，d2)＞θ·D，再將相應(yīng)數(shù)據(jù)點(diǎn)設(shè)為第3個聚類中心點(diǎn)c3。

3）假若c3存在，那么繼續(xù)計算剩余點(diǎn)各自與c1，c2，c3點(diǎn)的距離得出max( d1，d2，d3) 并確定第4 個聚類中心點(diǎn)。 依次類推，當(dāng)剩余點(diǎn)與max( d1，d2???dn)的距離不大于θ·D 時，終止選取聚類中心點(diǎn)的計算。

該改進(jìn)的K-means 算法避免了所選取的聚類中心點(diǎn)間距離相鄰近的情況，也降低了運(yùn)算迭代次數(shù)。同時，本文結(jié)合MapReduce分布式計算模型的特性，將Map端所產(chǎn)生的同一簇數(shù)據(jù)利用Combiner類對其做歸并處理，這樣能夠使得從Map 端到Reduce端傳輸過程中的數(shù)據(jù)量減少，從而縮減傳輸開銷。具體步驟如下：

假設(shè)對象集合X={x1，x2，???，xn}，聚類簇數(shù)k個，聚類中心點(diǎn)為{C1，C2，???，Ck} 。

輸入：對象集合X，初始中心點(diǎn)x1，x2

輸出：k個聚類中心點(diǎn)

步驟1.計算初始聚類中心

1）Map 端讀取本地數(shù)據(jù)，計算每個點(diǎn)與初始中心點(diǎn)的距離。

2）將該距離記作Value值傳送到Reduce函數(shù)。

3）Reduce端計算出與初始中心點(diǎn)距離最近的點(diǎn)。

4）將MapReduce 計算結(jié)果中距離值最大的點(diǎn)添入中心點(diǎn)文件。

5）將所有中心點(diǎn)寫進(jìn)cluster 中并將其加到分布式緩存里，以便為下一次迭代傳輸信息。具體流程如圖2所示。

圖2 聚類中心點(diǎn)計算流程

步驟2.聚類算法的MapReduce實(shí)現(xiàn)

1）Map 端讀取分布式緩存中上一輪迭代而來的簇中心點(diǎn)。

2）Map 函數(shù)計算中心點(diǎn)到每個點(diǎn)的距離并得出最近的簇中心點(diǎn)，然后將其作為key 值，對應(yīng)點(diǎn)的數(shù)據(jù)內(nèi)容作為value值。

3）Combiner 類歸并Map 端同一簇的＜key，value＞。

4）Reduce 端對Combiner 類所輸出內(nèi)容做合并計算。

5）當(dāng)中心點(diǎn)變化值小于給定值時結(jié)束本流程，否則跳向第1）步。

2.3 聚類中的相似度/距離度量方法

聚類算法往往會根據(jù)距離度量的方法來計算對象之間的相似度，對象通常會被分入相同簇或者不同簇中。不同簇對象之間的距離較遠(yuǎn)而相似度低，同一簇對象之間的距離較進(jìn)而相似度高［15］。距離度量方法作為衡量對象間相似度的指標(biāo)，當(dāng)采用不同的計算方法將會產(chǎn)生不同的效果。所以會將不同的度量方法進(jìn)行比較，從而選取出一種準(zhǔn)確度較高的方法。其中較常見的是歐幾里得距離：

除了距離，用來計算兩向量之間夾角的余弦相似度能夠準(zhǔn)確衡量兩個樣本之間的差異，夾角范圍為［-1，1］，余弦相似度如下：

另外皮爾遜相關(guān)性系數(shù)也是較常用的一種度量方法［16］。Pearson 相關(guān)系數(shù)重點(diǎn)用來確定兩向量是否在同一條直線上，它類似于余弦相似度是用來計算兩向量之間的夾角。當(dāng)Pearson 相關(guān)系數(shù)值越大，說明兩對象之間的相關(guān)性越強(qiáng)。而當(dāng)Pearson相關(guān)系數(shù)值趨近0 時，說明兩對象之間的相關(guān)性越弱。我們通?？梢詤⒖急? 數(shù)據(jù)來判斷兩個向量的相關(guān)強(qiáng)度。

表1 相關(guān)系數(shù)值域等級

Pearson相關(guān)系數(shù)：

其中Pearson 相關(guān)系數(shù)值介于-1 到1 之間，它能夠衡量兩個數(shù)列之間的線性相關(guān)程度。

2.4 基于改進(jìn)聚類的協(xié)同過濾推薦算法

協(xié)同過濾算法當(dāng)前在推薦系統(tǒng)研究領(lǐng)域被廣泛應(yīng)用，它不同于傳統(tǒng)搜索引擎需要用戶提供關(guān)鍵字等信息內(nèi)容，而是通過用戶的日志行為來挖掘出用戶喜好［17］。協(xié)同過濾通常使用近鄰方法為用戶尋找相似偏好用戶的信息，從而針對性比較強(qiáng)。協(xié)同過濾推薦算法不同于基于內(nèi)容的推薦算法，它是根據(jù)鄰近用戶物品評價或者打分結(jié)果來判斷目標(biāo)用戶的偏好，在這個過程中協(xié)同過濾推薦算法并不需要獲取用戶和物品的特征內(nèi)容。另外，協(xié)同過濾推薦通?？梢苑譃閮纱箢?，一種是基于用戶的協(xié)同過濾，另一種是基于物品的協(xié)同過濾?？偠灾?，協(xié)同過濾關(guān)鍵之處是挖掘出用戶的偏好，通過廣大用戶給各個物品做出的評價以及打分結(jié)果向相關(guān)用戶進(jìn)行合理的推薦。本文將在協(xié)同過濾推薦算法的基礎(chǔ)上結(jié)合改進(jìn)聚類算法來構(gòu)建推薦列表。其中，基于改進(jìn)聚類的協(xié)同過濾算法具體描述如下。

輸入：目標(biāo)物品的評分測試集R1、聚類數(shù)據(jù)集合R2、聚類中心和初始點(diǎn)集合R3、給定相似性閾值C。

輸出：最終推薦列表

1）對評分測試集中的目標(biāo)值與集合中各聚類中心點(diǎn)做相似度計算處理并統(tǒng)計；

2）將上述統(tǒng)計值與所給定的相似性閾值進(jìn)行詳細(xì)對比，選取不小于閾值的統(tǒng)計值所對應(yīng)項(xiàng)目列表，并將其添加到候選項(xiàng)目集中；

3）對候選集進(jìn)行基于項(xiàng)目的分布式協(xié)同過濾來生成用戶向量、項(xiàng)目共現(xiàn)向量以及項(xiàng)目組織完成的預(yù)測向量等等，實(shí)現(xiàn)對向量的預(yù)測，最終完成對目標(biāo)項(xiàng)目的相關(guān)推薦。

3 實(shí)驗(yàn)結(jié)果與分析

通過上述研究，選取1 臺機(jī)器作為Master，4 臺機(jī)器作為Slave去負(fù)責(zé)相關(guān)運(yùn)算任務(wù)。在數(shù)據(jù)集的選取上，這里在MovieLens 官方網(wǎng)站www.Crouplens.org 下載電影數(shù)據(jù)中的100KB，1MB 和10MB三種對應(yīng)數(shù)據(jù)，接下來選用該三類不同大小的電影數(shù)據(jù)來進(jìn)行實(shí)驗(yàn)，實(shí)現(xiàn)本文中不同算法在各個性能上的比較。

為了檢驗(yàn)在分布式大數(shù)據(jù)環(huán)境下該算法的相關(guān)性能，本文根據(jù)加速比S=T1/Tn來做相關(guān)處理和驗(yàn)證，通過Hadoop 的分布式平臺環(huán)境的可擴(kuò)展性能，可使該三種數(shù)據(jù)規(guī)模不同的電影數(shù)據(jù)在算法上的執(zhí)行效率大大提升。其中對該加速比的定義如下：

其中T1表示的是每個節(jié)點(diǎn)所執(zhí)行的時間，Tn則表示的是n 個節(jié)點(diǎn)同時工作的時候程序所執(zhí)行的總時長。在實(shí)驗(yàn)過程中，根據(jù)計算節(jié)點(diǎn)的數(shù)量我們依次對集群中的節(jié)點(diǎn)進(jìn)行啟動，總共5 個計算節(jié)點(diǎn)。接著分別將我們所選取的三類不同規(guī)模的數(shù)據(jù)集在所搭建好的集群上進(jìn)行處理。最后得出實(shí)際執(zhí)行的時間T1～T5，根據(jù)上述步驟所繪制出來的加速比曲線如圖3所示。

圖3 加速比曲線

圖3 縱軸表示執(zhí)行算法所得出的加速比S 值，橫軸表示運(yùn)算過程中計算節(jié)點(diǎn)的數(shù)量從1 臺遞增到5 臺。由圖3 所示曲線我們可以得出，隨著集群中計算節(jié)點(diǎn)數(shù)量從1臺機(jī)器逐漸增加到5臺機(jī)器過程中，執(zhí)行以上三種不同數(shù)據(jù)規(guī)模的電影數(shù)據(jù)所繪制出的曲線加速比值也在大幅單調(diào)增長。通過觀察圖3 中三條曲線走勢，顯然可得出隨著計算節(jié)點(diǎn)數(shù)量的逐漸增多，10MB 的大數(shù)據(jù)量電影數(shù)據(jù)所執(zhí)行效率增長較快，而100KB的小數(shù)據(jù)量電影數(shù)據(jù)所執(zhí)行效率增長較為緩慢。另外，當(dāng)計算節(jié)點(diǎn)的數(shù)目越來越多的時候，折線圖中的曲線加速比值增大的速率會由非線性增長變?yōu)榫€性增長。所以基于Hadoop 平臺下的分布式聚類協(xié)同過濾算法在數(shù)據(jù)規(guī)模龐大的環(huán)境下所執(zhí)行出來的推薦效率相對較高，同時也可以得出該算法在大數(shù)據(jù)環(huán)境下具有比較好的可擴(kuò)展性。

在協(xié)同過濾推薦中同樣也涉及到了相似度計算的問題，可將余弦相似度、皮爾遜相關(guān)性系數(shù)以及修正余弦相似度三種度量方法應(yīng)用到Hadoop 大數(shù)據(jù)平臺上進(jìn)行實(shí)驗(yàn)，計算比較絕對平均誤差MAE 值，根據(jù)結(jié)果選擇最佳相似性度量方法應(yīng)用到本文提出的協(xié)同過濾推薦算法中，便于查找目標(biāo)用戶的最近鄰居。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 相似度計算方法比較

由圖4 可得出，在相同實(shí)驗(yàn)條件下，三種方法都隨著鄰域數(shù)的增多而降低直到趨于穩(wěn)定，皮爾遜相關(guān)性系數(shù)的值在三種方法當(dāng)中較小，那么采用皮爾遜相關(guān)性系數(shù)來計算用戶簇中項(xiàng)目之間的相似性會提高推薦精度。

另外，對測評算法性能方面，可采用平均絕對誤差（MAE）來測評推薦質(zhì)量，公式如下：

由式（9）可推，當(dāng)計算出來的平均絕對誤差值越小，就表明算法的推薦精度或者質(zhì)量越高，反之，當(dāng)計算結(jié)果越大，那么算法的推薦準(zhǔn)確度就會下降。我們從100 KB 的電影數(shù)據(jù)集中選取不同數(shù)量規(guī)模的用戶數(shù)進(jìn)行試驗(yàn)，用戶數(shù)量逐次增加，分別選擇50、100、200、500、800 五組數(shù)據(jù)。并且每組數(shù)據(jù)按照8∶2的比例，隨機(jī)抽選劃分訓(xùn)練集R1和測試集R2。通過這五組實(shí)驗(yàn)數(shù)據(jù)計算MAE 值，對不同的推薦算法進(jìn)行試驗(yàn)比較。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 各個數(shù)據(jù)量的算法效果比較

圖5 中橫軸指的是試驗(yàn)數(shù)據(jù)所劃分得到的組數(shù)，縱軸是我們計算出來的平均絕對誤差值的大小。由圖5 曲線走勢我們可以得出，基于聚類的協(xié)同過濾算法MAE 值較小，該算法在性能上明顯要比其它兩種方法效果好。另外，當(dāng)電影實(shí)驗(yàn)數(shù)據(jù)量越大，MAE值也會隨之變小，推薦質(zhì)量不斷提高，從而可以總結(jié)出在較大數(shù)據(jù)量的條件下推薦準(zhǔn)確度更高。同時在實(shí)驗(yàn)數(shù)據(jù)上，第一組數(shù)據(jù)最為稀疏，到第五組數(shù)據(jù)相對密集，從圖5 中結(jié)果我們能夠總結(jié)出本文算法在對數(shù)據(jù)稀疏性問題上明顯比其他兩種算法效果好，它在克服數(shù)據(jù)稀疏性方面取得了較好效果。

4 結(jié)語

本文是在Hadoop 平臺下結(jié)合改進(jìn)聚類算法提升了傳統(tǒng)協(xié)同過濾推薦方法的性能。通過最大值-最小值算法對K-means 做出改進(jìn)，實(shí)現(xiàn)了對改進(jìn)K-means 算法的MapReduce 并行化設(shè)計，并在Hadoop平臺下對聚類協(xié)同過濾算法實(shí)現(xiàn)分布式處理，這種利用MapReduce 計算框架所實(shí)現(xiàn)的改進(jìn)推薦算法大大提高了算法的推薦質(zhì)量和運(yùn)算效率。同時本文也探討了并行化協(xié)同推薦算法的評估指標(biāo)，驗(yàn)證了基于Hadoop 平臺的分布式聚類協(xié)同過濾推薦算法能夠有效地解決數(shù)據(jù)的稀疏性和算法的可擴(kuò)展性問題。然而在推薦質(zhì)量上仍有很多有待完善的地方，同時以后的工作重點(diǎn)可以在算法的推薦性能上再進(jìn)一步對其優(yōu)化。