基于weighted slope one用戶聚類的林產品推薦算法

鄭　丹，王名揚，陳廣勝

(東北林業大學 信息與計算機工程學院，哈爾濱 150040)

?

基于weighted slope one用戶聚類的林產品推薦算法

鄭丹，王名揚*，陳廣勝

(東北林業大學 信息與計算機工程學院，哈爾濱 150040)

隨著電商平臺用戶、林產品數量規模不斷擴大，協同過濾推薦時構建的用戶-林產品評分矩陣變得高維稀疏，導致推薦算法精度和可擴展度下降。基于此本文提出一種weighted slope one用戶聚類推薦算法，將其應用在林業產品個性化推薦服務中。首先，通過weighted slope one算法的思想填充高維稀疏的用戶-林產品評分矩陣；其次，使用K-means聚類算法對用戶進行聚類，產生相似用戶集合，縮小推薦過程中鄰居用戶的搜索范圍；最后，在大數據Mahout平臺進行實際推薦，為林產品貿易平臺個性化推薦服務的大規模實現奠定基礎。經仿真實驗表明，文中提出的算法能夠全面提升推薦的精度和可擴展性。

林產品推薦；weighted slope one；K-means；協同過濾

0　引　言

近年來，科學技術的發展使林產品不斷被精深加工，加之其所具有綠色、環保、天然的優勢，林產品不斷成為健康產品的主流選擇。電子商務平臺的不斷發展帶動了林產品的推廣和銷售，但用戶和林產品的不斷增多出現了嚴重的信息負載，個性化推薦服務應運而生。通過個性化推薦服務省去了用戶搜索、篩選林產品的時間成本，直接為用戶推薦其可能感興趣的林產品，不但能提升用戶在電商平臺的購物體驗，同時還能夠為商家帶來銷售收入。

國家林業局于2011年提出《林業發展“十二五”規劃》中指出，要加快推進林業產品信息化，實現林業產品貿易化發展[1]。因此實現林產品智能推薦是推進我國林業信息化、實現《林業發展“十二五”規劃》的重要環節。完善林業產品平臺的產品推薦個性化服務技術是建設人性化、智能化林產品商務網站的關鍵技術與必然趨勢[2]。

協同過濾算法是目前應用最為廣泛的推薦算法，最早是由GlodBreg等人在90年代開發推薦系統Tapestry時提出來的，并在后來被廣泛的研究和應用[3]。隨著電商平臺上用戶、林產品規模的不斷擴大，構建出的用戶-林產品評分矩陣將具有高維稀疏性，其中大部分元素都是0元素，這對于計算用戶、產品之間相似性生成最近鄰居，提升算法推薦精度、可擴展性都是非常緊迫的挑戰。

為解決這一困境，近年來學者們提出了很多組合算法來提升推薦算法的推薦效果。通過降低用戶-產品評分矩陣的規模來實現提升推薦精度與可擴展性。Zhan Li等提出了通過取用戶的hyper-plane相似性和傳統的余弦相似性的折衷來解決數據的稀疏性問題，仿真實驗表明，該方法確實可以在一定程度上緩解數據的稀疏性問題[4]。Pirasteh P等人認為即使是相似性相同的兩個人也不應該推薦給他們完全相同的一個產品，他們將加權策略考慮進了相似性的度量中，實驗表明，的確能提升推薦算法的推薦精度，但是對于可擴展性的提升并不大[5]。陳洪濤等提出了一種新的基于社交關系的相似度傳播式協同過濾推薦算法，通過量化用戶社交關系計算用戶之間的相似性，然后基于社交網絡的相似度傳播模型來給出推薦列表[6]。王茜等通過引入社交網絡中的信任機制，從個體的社交圈中的主觀信任和全局聲譽角度出發建模，將直接、間接信任度聚合在一起構成用戶信任關系，解決冷啟動問題和用戶-評分矩陣稀疏性問題[7]。

在對學者們的研究現狀進行了充分調研的前提下，文中提出一種基于weighted slope one的用戶聚類推薦算法，以有效應對用戶-產品評分矩陣的高維稀疏性帶來的推薦效率低的問題，并將其應用在電子商務平臺上的林產品個性化推薦服務上。

1　數據源

以京東商城的產品分類中的食品、酒類、生鮮、特產為一級目錄，以地方特產、茗茶、生鮮食品作為二級目錄，收集二級目錄下的堅干果、可食用菌類、茗茶等類目林產品為代表作為本文的林產品數據集，通過八爪魚采集器收集產品的評論頁面中的評價詳情、評價時間、評價星級、林產品名稱、用戶名稱、用戶等級，用戶所在地點，采集的部分數據情況如圖1所示，共采集到72358條用戶-林產品評價信息。

圖1　爬取的林產品數據信息Fig.1 Forestry products data information

將重復的林產品進行合并，并且認為同一用戶對同一種商品的評價中時間最早的評價星級為有效評論。對數據經過清洗后共有2555條有效評論，在這些評論中包含了1899個用戶和60種林產品。在此基礎上，構建用戶-林產品評分矩陣，矩陣大小為1899×60，其中每列表示一種林產品，每行代表一個用戶，每個元素代表用戶對于林產品的評分情況。由于每個用戶能夠評論的林產品是有限的，所以呈現出的用戶-林產品評分矩陣具有高維稀疏性，直接在此矩陣上無論是進行用戶聚類推薦還是協同過濾推薦都存在用戶之間關聯性太低的問題，因此不易尋找最近鄰居給出推薦結果[8-9]。

2　基于weighted slope one用戶聚類協同過濾推薦算法

傳統的協同過濾推薦算法遇到了性能的瓶頸，算法的推薦精度和可擴展性都在下降。在對學者們提出的算法進行了深入的分析研究之后，提出了一種基于weighted slope one用戶聚類推薦算法，該算法首先構建用戶-產品的評分矩陣，將weighted slope one方法實現產品推薦思想的應用于稀疏矩陣的0元素填充，然后使用K-means算法實現相似用戶聚集，產生推薦列表，如圖2所示。

圖2　基于 weighted slope one算法填充后的用戶-林產品評分矩陣(部分)Fig.2 User-forestry products matrix based on weighted slope one(part)

2.1weighted slope one算法

slope one算法是Daniel Lemire教授于2005年提出的一個基于用戶打分的推薦算法，該算法通過以f(x)=x+b作為預測器，通過線性回歸來預測目標用戶對于未評分項目的打分情況，其中b是用戶對兩個項目的評分的平均偏差[10-11]。weighted slope one是slope one算法的一個遞進形式，它將用戶共同評分的差異度以及不同項目被用戶同時評論的次數也考慮進了打分預測中。因此weighted slope one算法所預測的評分更接近于真實的用戶評分。但是，文獻[12]研究表明slope one在用戶-項目評分矩陣比較稀疏時，其推薦的效果并不好。因此，文中并不直接利用weighted slope one算法進行目標用戶對項目的打分預測，而是通過使用該算法的思想將其應用于初始的用戶-林產品稀疏矩陣填充上。先降低初始用戶-林產品評分矩陣的稀疏程度，確保后續進行用戶聚類以及推薦的結果更優。

將weighted slope one算法應用于初始用戶-林產品評分矩陣填充(以目標用戶u的0元素填充為例)的具體過程為：首先，尋找目標用戶u與用戶v評分的林產品交集Iuv=Iu∩Iv，計算目標用戶u的未評分項目j對于項目i的偏移量devji，見公式(1)。然后計算目標用戶對于項目j的評分值，見公式(2)。這是經典的slope one算法預測目標用戶對項目打分的方式。但顯然的，用戶v與目標用戶u之間評分林產品的交集越多說明用戶與目標用戶更為相似，對其的預測評分的影響也就越深刻。因此，weighted slope one算法修正用戶u對項目最終的預測評分，見公式(3)。

(1)

(2)

(3)

式中：uj、ui表示用戶u對于項目i、j的評分值；card(i∩j)表示項目i、j同時被評分過的用戶數目；R(u)表示目標用戶u已經給出評分的項目集合；D(j)表示與目標項目j計算得到的平均偏移量devji的集合。

通過weighted slope one算法對高維稀疏矩陣進行填充后，用戶-林產品的評分矩陣如圖2所示，顯然有效降低了數據的稀疏程度。再通過K-means算法對用戶進行聚類，縮小鄰居用戶的搜索范圍，在提升推薦算法可擴展性的同時，為快速給出推薦結果奠定基礎。

2.2K-means算法

K-means聚類算法思想簡單，又容易實現對數據的大規模聚類，因此是使用的最為廣泛的聚類算法之一。 其基本思想為：首先從N個數據對象中隨機選擇k個對象作為初始聚類中心；對于剩下的其他對象，則根據它們與這些聚類中心的相似度(距離)，分別將其分配給與其最相似的聚類；然后再計算每個聚類新的聚類中心(該聚類中所有對象的均值)；不斷重復這一過程直到準則函數收斂為止[13-14]。K-均值算法采用誤差平方和函數作為準則函數，定義為：

(4)

式中：k表示聚類的數目；Cj(j=1，2，…，k)為j個簇；x為簇Cj中任意數據對象；mj為簇Cj中數據對象的均值；E是數據樣本與簇中心間距離的平方和，E值越小，聚類結果的質量就越高。因此，該算法設法找到使聚類準則函數E的值達到最小的聚類結果。

文中使用K-means算法對填充過的用戶-林產品評分矩陣進行聚類，用戶之間距離的度量使用余弦相似性進行度量，見公式(5)。產生相似用戶的候選集合，減少后續推薦的相似用戶搜索的時間、空間復雜度。

(5)

2.3協同過濾推薦

傳統的協同過濾算法可以分為基于用戶的協同過濾推薦和基于項目的協同過濾推薦，基于用戶的協同過濾算法實現推薦時基于如下事實：如果用戶對一些項目的評分比較相似就認為他們在其他項目的評分上具有相似關系[15]。算法首先遍歷用戶集合中的所有用戶，計算目標用戶與所有用戶的相似性，找出前N個最相似的用戶作為目標用戶的最近鄰居，見公式(5)；其次，對于目標用戶未評分的項目，搜索鄰居用戶集合對于目標用戶未評分項目的評分，并結合其與目標用戶的相似度計算目標用戶對于未評分項目的預測評分，見公式(6)。最后，針對預測評分的值給出目標用戶的推薦列表。

(6)

式中：sim(u,l)表示鄰居用戶l與目標用戶u的相似性，Rl,j表示鄰居用戶l對項目j的評分，項目j是目標用戶的未評分項目。Nu是目標用戶的鄰居用戶集合。

2.4基于weighted slope one用戶聚類推薦算法

設U={u1,u2,…,um}為收集的用戶集合，U′={C1,C2,…,Ck}表示生成的用戶簇類，k表示具體的用戶簇類個數，Ck表示第k個簇類，算法的具體描述如下：

輸入：用戶-評分矩陣D，聚類個數k，最近鄰居大小N，推薦列表的個數M。

輸出：目標用戶的推薦列表以及對應的評分。

step1：根據weighted slope one算法的思想對初始用戶-林產品評分矩陣D中的0元素進行填充，生成填充矩陣Dζ。

Step2：利用K-means算法對Dζ進行聚類分析，生成k個聚類輸出，各聚類的中心為ci，i=1，2，……，k。

Step3：通過公式(5)計算目標用戶與聚類中心ci的相似度，將目標用戶分配到距離最小的聚類Ci(i=1，2，……，k)中去。

Step4：在目標用戶所屬的簇類中，根據公式(5)計算目標用戶與其他用戶的相似性，搜索出相似性最大的前N個用戶作為目標用戶的最近鄰居集合，記為Nu。

Step5：利用公式(6)計算各個項目的預測評分，列出M個預測評分最大的項目推薦給目標用戶。

3　仿真實驗與結果分析

以收集到的京東商城的用戶、林產品評分數據為實驗數據，評分值是按照用戶在評價產品時給的評分星級，用戶標亮5顆星就認為用戶對該林產品的評分為5，未評分的用0來表示，評分越高，說明用戶對于該林產品的偏好性越強。

3.1實驗環境

文中通過JAVA語言來進行數據的清洗、去重復等工作，從而獲取初始的用戶、林產品評分信息。構造用戶-林產品評分矩陣、基于weighted slope one算法對用戶-林產品評分矩陣中的0元素進行填充、實現用戶聚類均是以Matlab語言完成，最后在Apache Mahout上構建推薦平臺完成推薦過程，為后續的林產品大規模推薦實現奠定基礎。

3.2推薦框架(Apache Mahout)

Apache Mahout是Apache Softwear Foundation(ASF)開發的一個基于大數據的開源項目，該項目中開發了很多機器學習的算法的接口，可以供開發人員、學者直接進行調用測試，算法涵蓋了聚類、分類、推薦等。

文中的推薦算法均在Apache Mahout上直接實現。在Taste組件中包含了可以進行編程擴展的接口，包括SO算法、基于內容的協同過濾推薦算法、基于項目的協同過濾推薦算法等，同時還提供了擴展接口，工程開發人員可以根據需要實現自己提出的推薦算法。Taste組件的工作原理如圖3所示：

圖3　Apache Mahout Taste推薦組件執行過程Fig.3 Apache Mahout taste components for execution

底層是數據存儲層，用于存儲用戶的偏好信息，在推薦系統層，用戶的偏好信息被建模成Users’ Preferences(接口)，一個preference就是一個三元組，其構成為<用戶ID，物品ID，評價詳情>。推薦引擎將Users’ Preferences提交給Recommender模塊，推薦引擎通過DataModel對用戶評價信息進行壓縮表示，DataModel是用戶評價信息的接口，它的具體實現支持從任意類型的數據源抽取用戶評價信息，它支持文件讀取和數據庫的讀取。Apache Mahout在進行協同過濾時，首先通過用戶的歷史行為構建DataModel，在Recommmender模塊中根據用戶的偏好計算用戶之間的相似性，產生最近鄰居，然后產生推薦策略給上層的應用層。

3.3評測指標

協同過濾推薦算法最終的目標要給出推薦產品列表以及產品的具體評分，因此涉及到兩個指標，即topM個項目的推薦性能以及評分預測的偏差。評分預測的度量多是通過MAE(平均絕對誤差)來進行度量，見公式(7)，而topM推薦的預測準確率一般通過準確率和召回率來進行度量[16]，見公式(8)和公式(9)。

(7)

(8)

(9)

式中：R(u)是給目標用戶的推薦列表；而T(u)則是目標用戶實際的行為列表。很明顯的，precision表示了推薦的準確性程度，而recall則反映了推薦列表中所推薦的產品被用戶響應的程度。從公式(8)和公式(9)來看，準確率和召回率都應該是越高越好。當準確率為NAN說明根據現有的用戶數據無法給出推薦產品列表，典型的就是常見的冷啟動問題。召回率為NAN說明用戶對于推薦的響應列表也為空，可以理解為不活躍用戶。

3.4實驗結果分析

為了驗證改進算法的有效性，使其能夠大范圍的應用在林業產品貿易平臺的使用上，以收集到的數據為測試數據，分別將文中提出的算法與傳統的協同過濾算法、基于K-means用戶聚類的算法的MAE、precision、recall進行對比，隨機地取用戶聚類個數為10，選取top 5個林產品作為產品列表推薦給用戶。 實驗結果見表1。

根據表1可知，利用文中提出的算法對用戶-林產品評分矩陣首先進行填充可以有效避免數據稀疏性的問題，在與基于K-means用戶聚類推薦算法的比較中可以看到，除去cluster4，cluster6之外，基于K-means用戶聚類推薦的算法都出現了NAN的情況，說明文中提出算法的無論是在預測評分還是topM推薦上其整體效果都優于基于K-means用戶聚類推薦，可見數據稀疏性對于推薦系統推薦結果的影響。同時，觀察到cluster4、cluster9的文中提出的算法所得到的precision、recall相對比較低。通過分析聚類結果發現，首先，cluster4、cluster9簇類內用戶數量較少，小用戶集合中進行推薦的能力有限；其次，簇類內用戶的評分行為較集中，即用戶購買評分的項目基本相同。由于用戶數量和小差異的集中的購買評分現象，造成了cluster4、cluster9的precision和recall都比較低。去除cluster4、cluster9這兩個聚類的precision和recall值發現，文中算法的平均precision、平均recall可以達到84.73%、87.28%。雖然與傳統的協同過濾算法相比較在precision上文中的算法還略低一點，但是其在recall、MAE上面的表現卻是完全優于傳統的協同過濾推薦算法。recall比傳統的算法提升了近60%多，MAE下降的幅度也比較大。

表1　各算法的precision、recall、MAE值比較

除此之外，由于文中提出的算法通過K-means聚類算法獲取了相似用戶的簇類，當需要對某個目標用戶進行推薦時，首先判斷該目標用戶所屬的簇類，在目標用戶所屬的簇類內實現推薦而非以往在所有用戶集中實現推薦過程。由于相似用戶簇類的用戶數量遠遠小于所有用戶集合，因此將目標用戶最近鄰居的搜索空間將大大降低，從而有效提升了算法的可擴展性。

4　結束語

電子商務的不斷發展會帶動林產品貿易平臺的完善和發展，完善林產品個性化推薦服務是推進我國林業信息化的重要途徑。文中以林產品為主題，收集關于用戶、林產品、評論等重要信息，通過對數據進行去重、整理生成用戶-林產品評分矩陣，引入weighted slope one算法進行推薦的思想，填充稀疏矩陣矩陣進行K-means聚類產生相似用戶集合，在低維的相似用戶空間中實現林產品的推薦。經仿真實驗表明，文中提出的方法能夠很好地提升林產品推薦的效率。

[1]國家林業局.《林業發展“十二五”規劃》[Z].2011.

[2]王梓.林產品貿易信息用戶興趣模型及個性化搜索[D].北京：北京林業大學，2013.

[3]Goldberg D，Nichols D，Oki B M，et al.Using collaborative filtering to weave an information tapestry[J].Communications of the ACM，1992，35(12)：61-70.

[4]Li Z，Peng J Y，Geng G H，et al.Video recommendation based on multi-modal information and multiple kernel[J].Multimedia Tools & Applications，2015，74(13)：4599-4616.

[5]Pirasteh P，Hwang D，Jung J E.Weighted similarity schemes for high scalability in user-based collaborative filtering[J].Mobile Networks & Applications，2015，20(4)：1-11.

[6]陳洪濤，肖如良，鄧新國.一種新的基于社交關系的相似度傳播式推薦算法[J].小型微型計算機系統，2015，36(5)：1073-1077.

[7]王茜，王錦華.結合信任機制和用戶偏好的協同過濾推薦算法[J].計算機工程與應用，2015，51(10)：261-265.

[8]李華，張宇，孫俊華.基于用戶模糊聚類的協同過濾推薦研究[J].計算機科學，2012，39(12)：83-86.

[9]賀桂和.基于用戶偏好挖掘的電子商務協同過濾推薦算法研究[J].情報科學，2013，31(12)：38-42.

[10]李朝陽.基于Slope One算法的協作過濾個性化推薦系統設計與實現[D].武漢：華中科技大學，2010.

[11]王毅.基于Hadoop的Slope One及其改進算法實現[D].成都：西南交通大學，2011.

[12]董麗，邢春曉，王克宏.基于不同數據集的協作過濾算法評測[J].清華大學學報：自然科學版，2009，49(4)：590-594.

[13]熊忠陽，陳若田，張玉芳.一種有效的K-means聚類中心初始化方法[J].計算機應用研究，2011，28(11)：4188-4190.

[14]王千，王成，馮振元，葉金鳳.K-means聚類算法研究綜述[J].電子設計工程，2012，20(7)：21-24.

[15]李濤，王建東，葉飛躍，等.一種基于用戶聚類的協同過濾推薦算法[J].系統工程與電子技術，2007(7)：1178-1182.

[16]項亮.推薦系統實戰[M].北京：人民郵電出版社，2014.

Research on Users’ Clustering of Forest Products RecommendationAlgorithm Based on Weighted Slope One

Zheng Dan，Wang Mingyang*，Chen Guangsheng

(College of Information and Computer Engineering，Northeast Forestry University，Harbin 150040)

With the rapid popularization of the Internet，number of users and products for E-commerce platform is getting huge.Traditional collaborative filtering algorithm encounters data sparseness problem，which cause the accuracy，scalability of recommendation algorithm a sharply drop.In this paper，a users’ clustering recommendation algorithm based on weighted slope one was proposed with aiming at the research of the recommendation for forest products.Firstly，the zero items in user-item matrix items were filled by weighted slope one algorithm.This operation can effectively reduce the data sparseness.Secondly，users could be clustered by K-means algorithm.Finally，the corresponding forestry products were recommended to the target users according to their nearest neighbors which were found by the users’ collaborative filtering recommendation algorithm on Mahout platform.Experiments showed that the improved algorithm can significantly reduce the data sparseness and improve the accuracy and scalability of recommendation.

forest products recommendation；weighted slope one；K-means；collaborative filtering

2016-02-29

中央高校基本科研業務費專項資金項目(2572014DB05)；中國博士后科學基金面上基金(2012M520711)；國家自然科學基金(No.71473034)

鄭丹，碩士研究生。研究方向：數據挖掘。

王名揚，博士，副教授。研究方向：數據挖掘、社交網絡挖掘。E-mail：wangmingyang@nefu.edu.cn

鄭丹，王名揚，陳廣勝.基于weighted slope one用戶聚類的林產品推薦算法[J].森林工程，2016，32(5)：65-70.

S 759.1

A

1001-005X(2016)05-0065-06