一種改進(jìn)的協(xié)同過濾推薦算法

朱小強(qiáng)，張琳

（上海海事大學(xué)信息工程學(xué)院，上?！?01306）

一種改進(jìn)的協(xié)同過濾推薦算法

朱小強(qiáng)，張琳

（上海海事大學(xué)信息工程學(xué)院，上海201306）

0　引言

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

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

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

1　基于用戶的協(xié)同過濾算法

在個(gè)性化推薦中，基于用戶的協(xié)同過濾算法是應(yīng)用最為廣泛的推薦算法。其基本原理是基于鄰居用戶的興趣愛好預(yù)測(cè)目標(biāo)用戶的興趣偏好。算法先使用統(tǒng)計(jì)技術(shù)尋找與目標(biāo)用戶有相同喜好的N個(gè)用戶作為用戶的最近鄰居集，然后根據(jù)目標(biāo)用戶的這N個(gè)鄰居的偏好產(chǎn)生向目標(biāo)用戶的推薦。取其中排在最前面的K個(gè)資源作為用戶的推薦集［5］。具體的流程如圖1所示：

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

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

表1　用戶對(duì)項(xiàng)目的評(píng)分表

根據(jù)已有的用戶對(duì)項(xiàng)目的評(píng)分表計(jì)算出相似用戶或項(xiàng)目，再依據(jù)計(jì)算得到的相似用戶或者項(xiàng)目進(jìn)行推薦。首先需要做的是選用合適的方法計(jì)算相似度。

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

其中Ric，Rjc分別為用戶ui，uj對(duì)項(xiàng)目c的評(píng)分，分別表示用戶ui，uj已評(píng)分項(xiàng)目的平均分，Iij為用戶ui，uj共同評(píng)分的項(xiàng)目。

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

（1）固定數(shù)量的鄰居：選取離目標(biāo)用戶距離最近的K個(gè)用戶作為目標(biāo)用戶的最近鄰居集。

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

假設(shè)集合Nu為目標(biāo)用戶u的最近鄰居集合，則可以預(yù)測(cè)用戶u對(duì)項(xiàng)目j的評(píng)分

Pu，j為［7］：

2　改進(jìn)的算法

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

改進(jìn)的算法的設(shè)計(jì)流程圖如圖2所示：

圖2　改進(jìn)的算法流程圖

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

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

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

算法在初始時(shí)為每個(gè)輸入樣本數(shù)據(jù)點(diǎn)創(chuàng)建一個(gè)canopy。

針對(duì)每一個(gè)canopy，把輸入與當(dāng)前canopy的距離小于閾值T1的歸為當(dāng)前canopy）

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

針對(duì)步驟2中新的canopy計(jì)算它們之間的距離，當(dāng)距離小于閾值T2時(shí)就把它們歸為一個(gè)canopy，同時(shí)相應(yīng)的屬性也疊加。

算法結(jié)束的條件：當(dāng)每一個(gè)canopy的前后兩次的差值都滿足小于一個(gè)給定的閾值delta時(shí)，該算法結(jié)束。

算法結(jié)束后，剩下的canopy的數(shù)目就是聚類的數(shù)目。

準(zhǔn)確性是傳統(tǒng)協(xié)同過濾的一大不足，因?yàn)槲锲坊蛴脩糁g的相似度只通過用戶評(píng)分矩陣計(jì)算獲得是一個(gè)不明智的做法，它沒有考慮項(xiàng)目之間的語義關(guān)系。例如手機(jī)和充電器這兩個(gè)物品除了表面計(jì)算得到的相似度外它們還有內(nèi)在的聯(lián)系。所以本文最終的相似度是把采用傳統(tǒng)方法計(jì)算得到的相似度和采用基于領(lǐng)域本體［8］的方法計(jì)算得到的相似度按一定比例進(jìn)行組合得到的，以此來提高項(xiàng)目或用戶的相似度，使得到的項(xiàng)目或用戶的最近鄰更加準(zhǔn)確，從而提高推薦的準(zhǔn)確度。

（1）基于領(lǐng)域本體的項(xiàng)目相似度計(jì)算：

什么是領(lǐng)域本體，它是一種對(duì)學(xué)科概念的闡述。其定義如下：（其結(jié)構(gòu)為樹的模型）

①對(duì)于一個(gè)給定的分類本體樹r，定義它的根節(jié)點(diǎn)為R，則R的高度或者深度可表示為Dep（R）=1；

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

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

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

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

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

其中，α為在0到1之間可調(diào)節(jié)的值。當(dāng)α=1時(shí)就是傳統(tǒng)的協(xié)同過濾方法，反之當(dāng)α=0時(shí)其相似度就是完全采用基于領(lǐng)域本體的方法計(jì)算得到的。

協(xié)同過濾的另一個(gè)問題就是評(píng)分矩陣的稀疏性問題，相對(duì)于系統(tǒng)中的龐大物品數(shù)量，用戶對(duì)物品的評(píng)價(jià)可謂冰山一角，這也是評(píng)分矩陣稀疏性問題的由來。

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

預(yù)測(cè)采用奇異值分解的評(píng)分公式為：

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

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

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

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

本文采用平均絕對(duì)偏差的方法來作為推薦系統(tǒng)推薦質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn)，將實(shí)際的用戶評(píng)分與預(yù)測(cè)的用戶評(píng)分進(jìn)行比較，從而得到預(yù)測(cè)預(yù)測(cè)的評(píng)分與實(shí)際評(píng)分的偏差，偏差值越小，那么推薦的準(zhǔn)確度就越高［10］。

其中，qi為測(cè)試集中用戶原始的評(píng)分；pi是預(yù)測(cè)的評(píng)分；number是評(píng)分項(xiàng)目數(shù)目。

圖3　實(shí)驗(yàn)結(jié)果折點(diǎn)圖

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

4　結(jié)語

本文提出了基于MeanShift聚類的協(xié)同過濾算法，降低了用戶空間的維數(shù)。在評(píng)分?jǐn)?shù)據(jù)極其稀疏條件下，能夠較精確的給出評(píng)分預(yù)測(cè)，是一種更合理的用于推薦的選擇。

［1］張樹良，冷伏海.Web環(huán)境下個(gè)性化信息的獲取和個(gè)性化服務(wù)的實(shí)現(xiàn)［J］.中國圖書館學(xué)報(bào)，2007，33（170）：77～81

［2］王翠萍，楊冬梅.知識(shí)門戶的個(gè)性化服務(wù)現(xiàn)狀及優(yōu)化研究［J］.中國圖書館學(xué)報(bào)，2009，35（183）：117～122

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

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

［5］周強(qiáng).基于用戶的協(xié)同過濾推薦算法研究［J］.南昌高專學(xué)報(bào)，2006（3）：88～89

［6］王茜，王均波.一種改進(jìn)的協(xié)同過濾推薦算法［J］.計(jì)算機(jī)科學(xué)，2010，37（6）：226～228

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

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

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

［10］顏豐，張琳.一種混合模式的協(xié)同過濾算法［J］.現(xiàn)代計(jì)算機(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

朱小強(qiáng)（1989-），男，江蘇泰州人，碩士研究生，研究方向：個(gè)性化推薦系統(tǒng)、自然語言處理、模式識(shí)別

2015-04-24

2015-05-26

在這個(gè)電商及大數(shù)據(jù)的時(shí)代，個(gè)性化推薦系統(tǒng)應(yīng)運(yùn)而生。由于傳統(tǒng)的協(xié)同過濾算法存在新使用者、新項(xiàng)目、擴(kuò)展性以及稀疏性等問題，提出一種基于MeanShift算法的項(xiàng)目或用戶聚類，奇異值分解和項(xiàng)目語義相似度的推薦模型，有針對(duì)性的對(duì)傳統(tǒng)的協(xié)同過濾推薦系統(tǒng)的不足之處進(jìn)行改進(jìn)。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的推薦算法相比，改進(jìn)算法具有更高的準(zhǔn)確性。

推薦系統(tǒng)；協(xié)同過濾；MeanShift聚類；矩陣稀疏

張琳（1973-），女，河南信陽人，博士，副教授，研究方向?yàn)楦酆叫畔⒒夹g(shù)、智能信息處理、信息檢索、本體與知識(shí)工程等

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.