一種改進的協同過濾推薦算法

朱小強，張琳

（上海海事大學信息工程學院，上海　201306）

一種改進的協同過濾推薦算法

朱小強，張琳

（上海海事大學信息工程學院，上海201306）

0　引言

在如今這個大數據及電商的時代，個性化推薦系統［1～2］應運而生。在電子商務網站中，使用個性化推薦系統的目的是向擁有不同興趣的一類客戶提供符合其需求的商品。目前主要的推薦技術［3］有3種：基于用戶的過濾推薦技術［4］，基于內容的過濾推薦技術和基于規則的過濾推薦技術。

在推薦技術的實際應用過程中，面臨著剛開始時沒有用戶對商品給出評價，即冷開始；用戶對商品的評價數目過少以及商品數目的不斷增加，也就是數據稀疏性以及擴展性等問題，使得推薦的精確度大打折扣。

針對上述不足之處，本文提出了一種基于Mean-Shift聚類的用戶協同過濾算法。該算法先利用Mean-Shift聚類算法對所有用戶進行聚類，然后將目標用戶所屬的類作為基于用戶的協同過濾算法的輸入得到最終的結果。

1　基于用戶的協同過濾算法

在個性化推薦中，基于用戶的協同過濾算法是應用最為廣泛的推薦算法。其基本原理是基于鄰居用戶的興趣愛好預測目標用戶的興趣偏好。算法先使用統計技術尋找與目標用戶有相同喜好的N個用戶作為用戶的最近鄰居集，然后根據目標用戶的這N個鄰居的偏好產生向目標用戶的推薦。取其中排在最前面的K個資源作為用戶的推薦集［5］。具體的流程如圖1所示：

圖1　基于用戶的協同過濾算法的主要步驟

用戶的偏好信息決定著系統推薦的效果，所以收集方法很重要。用戶提供個人偏好信息的方式有很多，例如游覽網頁的時長，點擊的相關物品以及用戶注冊時提供的一些個人信息等。根據不同用戶的行為，可以得到用戶偏好的二維評分矩陣，列表示物品，橫表示用戶，數值是用戶對物品的評分，一般是［0，4］之間的數值 （0表示非常不滿意，1表示基本滿意，2表示滿意，3表示很滿意，4表示非常滿意），如表1所示：

表1　用戶對項目的評分表

根據已有的用戶對項目的評分表計算出相似用戶或項目，再依據計算得到的相似用戶或者項目進行推薦。首先需要做的是選用合適的方法計算相似度。

在協同過濾算法中，計算相似度的方法主要有：Pearson相關相似性、余弦相似性和修正的余弦相似性這3種，為了準確性和方便，本文采用了Pearson相關相似性。由此可得兩個用戶之間的相似度Sim（i，j）為［6］：

其中Ric，Rjc分別為用戶ui，uj對項目c的評分，分別表示用戶ui，uj已評分項目的平均分，Iij為用戶ui，uj共同評分的項目。

得到用戶之間的相似度之后，接下來要做的就是根據相似度找到目標用戶的最近鄰居集，可選用如下兩類方法計算用戶的最近鄰居集：

（1）固定數量的鄰居：選取離目標用戶距離最近的K個用戶作為目標用戶的最近鄰居集。

（2）相似度門檻的鄰居：提前設定一個閾值t，選取離目標用戶的距離小于或等于閾值t的所有用戶作為目標用戶的最近鄰居集。

假設集合Nu為目標用戶u的最近鄰居集合，則可以預測用戶u對項目j的評分

Pu，j為［7］：

2　改進的算法

由于采用傳統協同過濾推薦算法的推薦系統具有數據稀疏性，推薦的精確度，算法的伸縮性等問題，本文提出了一種改進的新型推薦模型。其中，采用奇異值分解的方法來降低評分矩陣的稀疏性；運用項目語義相似度來提高推薦的精確度；采取基于項目聚類的方法來改善算法的伸縮性。

改進的算法的設計流程圖如圖2所示：

圖2　改進的算法流程圖

聚類中，常用的是K-means聚類算法。其優點是可以離線預處理數據，能夠很好地響應實時性；可以通過縮小最近鄰居查找空間范圍的方法來提高搜索效率。但也有許多不足之處，其中最重要的就是聚類的數目K不是算法自動生成的，而是人為的隨機選取的，不同的K值會產生不同數目的聚類中心，這樣得到的聚類個數也就不同。顯而易見，采用這種聚類方法得到的結果帶有一定的隨機性，從而聚類的準確性也會不盡如人意。

綜上所述，本文采用的聚類算法為MeanShift聚類算法。MeanShift算法的特性之一是不需要提供一個明確的聚類數目，其二是該算法還能根據數據的特征發現任意形狀的聚類簇 （這點和 Canopy算法不同，Canopy算法發現的是圓形簇）。該算法首先為每個數據創建一個固定半徑的窗口，循環遍歷每個窗口，通過一個本地的密度函數計算一個均值漂移向量 （這個向量是指最大增長速度的方向）。然后每個窗口根據計算出來的均值漂移向量移動到一個新的位置，并且又開始新的循環。循環退出的條件是當通過本地密度函數計算出來的向量變得很小的時候，滿足一個閾值就退出。

改進算法使用距離閾值T1作為每個窗口的固定半徑，使用距離閾值T2來決定兩個canopy什么時候合并為一個 （即當兩個canopy的距離小于T2時就把它們合并）。每個canopy包含一個或者多個被限制在某個范圍的點。下面是MeanShift聚類的過程［8］：

算法在初始時為每個輸入樣本數據點創建一個canopy。

針對每一個canopy，把輸入與當前canopy的距離小于閾值T1的歸為當前canopy）

（比如，一共有三條記錄，如果它們彼此的距離都小于T1，那么以第一條記錄為canopy的點有兩個，分別為記錄2和記錄3；以第二條記錄為canopy的點有兩個，分別為記錄1和記錄3；以第三條記錄為canopy的點有兩個，分別為記錄1和記錄2）。每一個canopy計算它的均值漂移向量，計算方法：使用每個canopy包含的點的全部維度相加除以包含點的數目就得到了一個新的canopy中心向量，即均值漂移向量。這個中心向量的權重通過它包含的點的數目來表示。

針對步驟2中新的canopy計算它們之間的距離，當距離小于閾值T2時就把它們歸為一個canopy，同時相應的屬性也疊加。

算法結束的條件：當每一個canopy的前后兩次的差值都滿足小于一個給定的閾值delta時，該算法結束。

算法結束后，剩下的canopy的數目就是聚類的數目。

準確性是傳統協同過濾的一大不足，因為物品或用戶之間的相似度只通過用戶評分矩陣計算獲得是一個不明智的做法，它沒有考慮項目之間的語義關系。例如手機和充電器這兩個物品除了表面計算得到的相似度外它們還有內在的聯系。所以本文最終的相似度是把采用傳統方法計算得到的相似度和采用基于領域本體［8］的方法計算得到的相似度按一定比例進行組合得到的，以此來提高項目或用戶的相似度，使得到的項目或用戶的最近鄰更加準確，從而提高推薦的準確度。

（1）基于領域本體的項目相似度計算：

什么是領域本體，它是一種對學科概念的闡述。其定義如下：（其結構為樹的模型）

①對于一個給定的分類本體樹r，定義它的根節點為R，則R的高度或者深度可表示為Dep（R）=1；

②概念D為上述所建樹中的任一非根節點，它的父節點可用parent（D）來表示，則概念D的高度或者深度為從概念D到根節點R的路徑長度，記為Dep（D），則由樹的概念可知其高度或深度為：Dep（D）=Dep（parent（D））+1；

I為概念C的實例，則I的深度Dep（I）為Dep（I）=Dep（C）+1。任意2個概念m，n的最小共同祖先LCA（Least Common Ancestor）為m，n祖先中深度最大的共同祖先，記為LCA（m，n），可以表示為：

說明如下：Ii，Ij分別為概念m，n的實例。由此可得Ii，Ij之間相似度為：

由上述相似度公式可知，相似度Sim（m，n）的值在0到1之間，且LCA（m，n）越大，概念m，n的相似度Sim（m，n）就越大，當Sim（m，n）=1時，表示這兩個概念相同。

最終的相似度組合公式為：

其中，α為在0到1之間可調節的值。當α=1時就是傳統的協同過濾方法，反之當α=0時其相似度就是完全采用基于領域本體的方法計算得到的。

協同過濾的另一個問題就是評分矩陣的稀疏性問題，相對于系統中的龐大物品數量，用戶對物品的評價可謂冰山一角，這也是評分矩陣稀疏性問題的由來。

奇異值分解（SVD）的簡單介紹：它是用來簡化矩陣維數的一種常用方法，它將一個m×n的矩陣A分解為3個矩陣。A=N×S×VT，其中N是一個m×m的正交矩陣，V是一個n×n的正交矩陣，S是一個m×n的對角矩陣，對角線上的元素由上往下一次遞減，并且對角線上的元素都是大于0的，非對角線上的元素全為0，對角線上的元素從小到大排列，稱為奇異值，奇異值分解可以產生與原始矩陣秩相等的并且與原始矩陣最近似的矩陣。

預測采用奇異值分解的評分公式為：

3　實驗結果及分析

本文的數據集為Movielens的數據集，從用戶數據庫中選擇包含1200個用戶和4000部電影的共199050條評分的實驗數據集。將實驗數據集分為測試集［9］和訓練集，通常比例為1：4，這樣可以使建立模型在大量的訓練集中得到完善，使得最后的實驗結果更具有說服力。

本文采用的電影數據集的稀疏等級為：1-199050/ （1200×4000）=0.9585。

將本文提出的改進算法與基于K-means聚類的傳統的用戶的過濾推薦算法在其他外在條件相同的情況下進行測試比較。

本文采用平均絕對偏差的方法來作為推薦系統推薦質量的評價標準，將實際的用戶評分與預測的用戶評分進行比較，從而得到預測預測的評分與實際評分的偏差，偏差值越小，那么推薦的準確度就越高［10］。

其中，qi為測試集中用戶原始的評分；pi是預測的評分；number是評分項目數目。

圖3　實驗結果折點圖

從圖3可看到，改進的推薦算法在精度方面明顯高于傳統的推薦算法。同時，隨著折線圖的升降可以看出推薦的準確度受最大鄰居數目的影響，所以在選擇鄰居的數目時要慎重。

4　結語

本文提出了基于MeanShift聚類的協同過濾算法，降低了用戶空間的維數。在評分數據極其稀疏條件下，能夠較精確的給出評分預測，是一種更合理的用于推薦的選擇。

［1］張樹良，冷伏海.Web環境下個性化信息的獲取和個性化服務的實現［J］.中國圖書館學報，2007，33（170）：77～81

［2］王翠萍，楊冬梅.知識門戶的個性化服務現狀及優化研究［J］.中國圖書館學報，2009，35（183）：117～122

［3］Resnick，Varian.Recommender Systems［J］.Communications of the ACM，1997，40（3）：56～58

［4］傅鶴崗，彭晉.基于模范用戶的改進協同過濾算法［J］.計算機工程，2011，37（3）：71～74

［5］周強.基于用戶的協同過濾推薦算法研究［J］.南昌高專學報，2006（3）：88～89

［6］王茜，王均波.一種改進的協同過濾推薦算法［J］.計算機科學，2010，37（6）：226～228

［7］程巖，肖小云，吳潔倩.基于聚類分析的電子商務推薦系統［J］.計算機工程與應用，2005（24）：175～177

［8］MeanShift，Mode Seeking，and Clustering（1995）

［9］彭玉，程小平，徐藝萍.一種改進的Item-based協同過濾推薦算法［J］.西南大學學報，2007，29（5）：146～149

［10］顏豐，張琳.一種混合模式的協同過濾算法［J］.現代計算機，2014.

Recommendation System；Collaborative Filtering Algorithm；Clustering；Singular Value Decomposition

Collaborative Filtering Algorithm Based on MeanShift Clustering

ZHU Xiao-qiang，ZHANG Lin
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

1007-1423（2015）17-0031-05

10.3969/j.issn.1007-1423.2015.17.007

朱小強（1989-），男，江蘇泰州人，碩士研究生，研究方向：個性化推薦系統、自然語言處理、模式識別

2015-04-24

2015-05-26

在這個電商及大數據的時代，個性化推薦系統應運而生。由于傳統的協同過濾算法存在新使用者、新項目、擴展性以及稀疏性等問題，提出一種基于MeanShift算法的項目或用戶聚類，奇異值分解和項目語義相似度的推薦模型，有針對性的對傳統的協同過濾推薦系統的不足之處進行改進。實驗結果表明，與傳統的推薦算法相比，改進算法具有更高的準確性。

推薦系統；協同過濾；MeanShift聚類；矩陣稀疏

張琳（1973-），女，河南信陽人，博士，副教授，研究方向為港航信息化技術、智能信息處理、信息檢索、本體與知識工程等

In this era of electricity and big data，the personalized recommendation is mainly used in e-commerce sites.To solve the traditional collaborative filtering algorithm existing the new user，new project，scalability and sparsity problems，proposes a collaborative filtering algorithm based on MeanShift clustering，Semantic similarity between items and Singular Value Decomposition.To deal with the disadvantages that the traditional collaborative filtering recommendation system facing.The experimental results show that，compared with the traditional recommendation algorithm，the improved algorithm has higher accuracy.