融合隱語(yǔ)義模型和K-meansplus聚類模型的推薦算法?

喬平安 曹 宇 任澤乾

1 引言

隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的逐步發(fā)展，信息的爆炸式增長(zhǎng)帶來(lái)了信息過(guò)載的問(wèn)題［1］，使得人們無(wú)法快速地獲取有效的信息，個(gè)性化推薦［2］的出現(xiàn)解決信息過(guò)載問(wèn)題，幫助用戶快速有效地獲取有效的信息，因此得到越來(lái)越多研究者的關(guān)注。

協(xié)同過(guò)濾推薦［3］是最受歡迎并廣泛研究和大量應(yīng)用的推薦技術(shù)。協(xié)同過(guò)濾推薦算法基本思想是，如果用戶之間有相同或是類似的興趣愛(ài)好，那么他們對(duì)其它物品選擇上有相同或是相似的表現(xiàn)。目前，協(xié)同過(guò)濾推薦模型很多，本文主要使用了隱語(yǔ)義模型和聚類模型。

隱語(yǔ)義模型［4］的基本思想是通過(guò)隱含特征聯(lián)系用戶與物品，把高維向量空間模型中的信息射到低維的潛在語(yǔ)義空間中，降維處理使得物品與用戶之間的潛在關(guān)系用隱含特征聯(lián)系［5］。

聚類模型［6］的基本思想對(duì)根據(jù)用戶的相似度［7］，將用戶聚在相對(duì)同源的類中，在每個(gè)簇內(nèi)使用最近鄰技術(shù)進(jìn)行推薦。

本文將隱語(yǔ)義模型和聚類模型結(jié)合，提出了一種融合隱語(yǔ)義模型和K-meansplus聚類模型的推薦算法。該算法既克服了數(shù)據(jù)稀疏性問(wèn)題［8］，同時(shí)也保留了聚類算法可擴(kuò)展［9］的優(yōu)點(diǎn)。

2 融合隱語(yǔ)義模型和K-meansplus模型的推薦算法

2.1 隱語(yǔ)義模型

隱語(yǔ)義模型可以看作是對(duì)SVD模型的改進(jìn)。因?yàn)镾VD模型填充稀疏矩陣需要大量的存儲(chǔ)空間，并且計(jì)算復(fù)雜度很高，所以很難得以應(yīng)用。為了解決SVD的缺點(diǎn)，Simon Funk在Netflix Prize提出了隱語(yǔ)義模型［10］。該模型的核心思想是通過(guò)隱含特征聯(lián)系用戶興趣與項(xiàng)目。該算法通過(guò)矩陣分解［11］將評(píng)分矩陣分解成為兩個(gè)低維矩陣，一個(gè)是用戶隱含特征矩陣，一個(gè)是項(xiàng)目隱含特征矩陣。再將低維的隱含矩陣相乘表示預(yù)測(cè)評(píng)分。假設(shè)用戶u對(duì)項(xiàng)目i的評(píng)分為r?ui，可以得到計(jì)算公式：

可以直接通過(guò)訓(xùn)練集中的觀察值利用最小化RMSE來(lái)學(xué)習(xí) puf和qif。

C(p ,q)被稱為損失函數(shù)，用于估計(jì)參數(shù)。λ(‖ pu‖2+‖qi‖2)是防止過(guò)擬合而加入的正則項(xiàng)。

可以使用隨即梯度下降法［12］來(lái)優(yōu)化上述的損失函數(shù)。通過(guò)對(duì)參數(shù)的求偏導(dǎo)來(lái)找到最快下降方向，可以得到：

然后根據(jù)隨機(jī)剃度下降法，沿著最速下降方向向前推進(jìn)，可以得到如下遞推公式：

其中α是學(xué)習(xí)速率，它的取值需要通過(guò)反復(fù)實(shí)驗(yàn)獲得。迭代的終止條件是損失函數(shù)到達(dá)最小值。由于在用梯度下降方法對(duì)單個(gè)特征向量元素求偏導(dǎo)時(shí)，和其余特征向量相關(guān)的項(xiàng)均為0，因此回避了一般SVD算法中需要迭代或插值求解矩陣中未知元素的問(wèn)題。另外也可以看出，每次迭代使用一個(gè)評(píng)分?jǐn)?shù)據(jù)，整個(gè)訓(xùn)練過(guò)程只需要存儲(chǔ)特征向量的內(nèi)存空間，因此特別適合于有非常大數(shù)據(jù)集的情況。

2.2 基于K-meansplus協(xié)同過(guò)濾推薦算法

基于K-meansplus協(xié)同過(guò)濾推薦算法是在基于K-means協(xié)同過(guò)濾推薦算法上對(duì)初始中心點(diǎn)的選擇進(jìn)行了優(yōu)化?；贙-meansplus協(xié)同過(guò)濾推薦算法基本思想：首先是將原本評(píng)分、偏好、興趣特征相似的對(duì)象通過(guò)聚類算法將其聚到同一簇中，然后就可以只在與目標(biāo)用戶相似度極髙的簇中通過(guò)計(jì)算來(lái)查找興趣最相似的鄰居。

K-meansplus聚類算法步驟

輸入：u為用戶訓(xùn)練數(shù)據(jù)集；k為總共聚類的數(shù)目。

輸出：k個(gè)聚類中心，

1）定義所需的聚類數(shù)量k；

2）從訓(xùn)練集u中均勻隨機(jī)選擇初始聚類中心c1；

3）repeat；

4）選擇下一個(gè)初始聚類中心點(diǎn) ci，其中ci=u'∈u可能性：

5）直到k個(gè)聚類中心找到。

基于K-meansplus聚類的協(xié)同過(guò)濾算法避免了傳統(tǒng)的基于內(nèi)存的系統(tǒng)過(guò)濾算法的缺點(diǎn)。具體來(lái)說(shuō)，傳統(tǒng)的基于內(nèi)存的協(xié)同過(guò)濾算法搜索最近鄰時(shí)，要在整個(gè)用戶或是項(xiàng)目對(duì)象中搜索，這就產(chǎn)生很大計(jì)算量造成計(jì)算效率低下。通過(guò)K-meansplus聚類技術(shù)就可以很好的規(guī)避這個(gè)缺陷，搜索最近的鄰居的范圍目標(biāo)對(duì)象可以被限制在一些集群相似度最高的目標(biāo)中，計(jì)算量得到了減少，實(shí)時(shí)響應(yīng)能力相應(yīng)的提高，同時(shí)具有更好的可擴(kuò)展性。但是基于K-meansplus聚類的協(xié)同過(guò)濾算法和傳統(tǒng)的基于內(nèi)存的協(xié)同過(guò)濾算法一樣無(wú)法解決數(shù)據(jù)稀疏性的問(wèn)題，當(dāng)數(shù)據(jù)十分稀疏時(shí)候，推薦的準(zhǔn)確度也無(wú)法得到保證?；趦?nèi)存的協(xié)同過(guò)濾算法分為基于用戶的協(xié)同過(guò)濾和基于項(xiàng)目的協(xié)同過(guò)濾，這里主要討論基于用戶的協(xié)同過(guò)濾。

2.3 融合隱語(yǔ)義模型和K-meansplus聚類模型的推薦算法

融合推薦算法的思路有很多種，在本文中則是采用層級(jí)疊加兩種協(xié)同過(guò)濾推薦算法的方法設(shè)計(jì)了一種混合推薦算法，先使用其中一種推薦算法評(píng)估出用戶對(duì)一些未評(píng)分項(xiàng)目的預(yù)測(cè)評(píng)分，將評(píng)分值填充進(jìn)用戶-項(xiàng)目評(píng)分矩陣中，然后在解決了數(shù)據(jù)稀疏性的問(wèn)題之后，再采用另一種傳統(tǒng)的協(xié)同過(guò)濾推薦算法在此填充過(guò)后的矩陣的基礎(chǔ)上得到更好的推薦結(jié)果。

融合隱語(yǔ)義模型和K-meansplus聚類模型的推薦算法步驟：

Step1：利用隱語(yǔ)義模型對(duì)數(shù)據(jù)缺失的矩陣填充得到無(wú)缺失的用戶-項(xiàng)目矩陣R；

Step2：將評(píng)分矩陣R利用K-meansplus對(duì)用戶進(jìn)行聚類，將用戶聚集到不同的k個(gè)簇中，距離函數(shù)使用皮爾遜相似性；

Step3：對(duì)于當(dāng)前活動(dòng)用戶a，計(jì)算它與c個(gè)類中心的距離，并將c指定為距離中心最近的簇中；

Step4：在已經(jīng)聚類的簇中，計(jì)算用戶相似度sim(Ua,Ui)，選N個(gè)最相似用戶作為最近鄰居；

Step5：根據(jù)最近鄰用戶集的評(píng)分?jǐn)?shù)據(jù)，加權(quán)預(yù)測(cè)當(dāng)前用戶a的未評(píng)分項(xiàng)目評(píng)分；

Step6：選出前N個(gè)預(yù)測(cè)評(píng)分輸出。

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

3.1 數(shù)據(jù)集

本文實(shí)驗(yàn)采用美國(guó)明尼蘇達(dá)大學(xué)GroupLens研究小組提供的MovieLens數(shù)據(jù)集。本文采用100K的評(píng)分?jǐn)?shù)據(jù)集，該數(shù)據(jù)集包含了943個(gè)用戶對(duì)1682部電影的100000條評(píng)分記錄。所有的評(píng)分值都是1～5中的整數(shù)值，其中分?jǐn)?shù)越高代表用戶相對(duì)應(yīng)的電影評(píng)價(jià)越高。這個(gè)評(píng)分矩陣的稀疏度為93.7%。實(shí)驗(yàn)中，我們將整個(gè)數(shù)據(jù)集隨機(jī)分為訓(xùn)練集和測(cè)試集兩部分，所占比分別為80%和20%。

3.2 評(píng)測(cè)標(biāo)準(zhǔn)

本文采用平均絕對(duì)誤差（MAE）和準(zhǔn)確率（Precision）作為評(píng)價(jià)標(biāo)準(zhǔn)［13～14］。平均絕對(duì)誤差（MAE）已廣泛應(yīng)用于許多研究項(xiàng)目中作為評(píng)測(cè)指標(biāo)。MAE是計(jì)算由推薦系統(tǒng)預(yù)測(cè)獲得的評(píng)分和用戶真實(shí)的評(píng)分之間的平均絕對(duì)誤差，公式如下：

|T|是由測(cè)試集提供的評(píng)分總數(shù)量，rui是用戶u對(duì)物品i的實(shí)際評(píng)分，r?ui是推薦算法給出的預(yù)測(cè)評(píng)分值。推薦系統(tǒng)想要通過(guò)最小化對(duì)項(xiàng)目的真實(shí)與預(yù)測(cè)評(píng)分值來(lái)降低MAE。

準(zhǔn)確率公式如下：

R(u)表示根據(jù)用戶在訓(xùn)練集上的興趣行為表現(xiàn)給用戶推薦產(chǎn)生的推薦列表，T(u)表示根據(jù)用戶在測(cè)試集上的興趣行為產(chǎn)生的列表。

3.3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文提出的融合算法在評(píng)分預(yù)測(cè)中的性能，本文與隱語(yǔ)義模型和K-meansplus進(jìn)行對(duì)比 。 隱 語(yǔ) 義 模 型 中 α=0.007，F(xiàn)=40，λ=0.025。K-meansplus聚類模型中聚類個(gè)數(shù)選擇15。

圖2 不同算法Precision對(duì)比

由圖1可以看出，本文提出的算法在MAE性能上要優(yōu)于K-meansplus。當(dāng)最近鄰個(gè)數(shù)20時(shí)候算法性能與LFM近似相等，隨著最近鄰個(gè)數(shù)增加算法性能優(yōu)于LFM。由圖2可以看出，本文提出的算法在Precision性能上優(yōu)于K-meansplus。當(dāng)最近鄰個(gè)數(shù)超過(guò)26時(shí)，算法的性能優(yōu)于LFM。

4 結(jié)語(yǔ)

推薦系統(tǒng)發(fā)展至今，每種推薦算法都有一定的局限性。數(shù)據(jù)的稀疏性、冷啟動(dòng)、可擴(kuò)展等問(wèn)題一直是推薦算法待解決的問(wèn)題。為了解決以上問(wèn)題，各種混合推薦技術(shù)層出不窮。本文提出了基于隱語(yǔ)義模型和K-meansplus聚類的層級(jí)推薦算法。我們先使用矩陣分解技術(shù)，對(duì)原始矩陣進(jìn)行數(shù)據(jù)填充，提高數(shù)據(jù)密度，得到一個(gè)無(wú)缺失值的矩陣。然后使用K-meansplus聚類算法對(duì)用戶進(jìn)行聚類，完成對(duì)評(píng)分預(yù)測(cè)。通過(guò)對(duì)比實(shí)驗(yàn)證明本文提出的混合推薦算法具有更好的預(yù)測(cè)準(zhǔn)確度。

［1］Bawden D，Robinson L.The dark side of information：over-load，anxiety and other paradoxes and pathologies［J］.Journal of Information Science，2009，35（2）：180-191.

［2］Zhang Y，Jiao J.An associative classification-based recommendation system for personalization in B2C e-commerce applications［J］.Expert Systems with Applications An International Journal，2007，33（2）：357-367.

［3］Song H，Lu P，Zhao K.Improving item-based collaborative filtering recommendation system with tag［C］//International Conference on Artificial Intelligence，Management Science and Electronic Commerce. IEEE， 2011：2142-2145.

［4］Hoff P D.Multiplicative latent factor models for description and prediction of social networks［J］.Computational and Mathe-matical Organization Theory，2009，15（4）：261-272.

［5］Dumais ST.Latent semantic analysis［J］.Annual Review of Information Science and Technology，2004，38（1）：188-230.

［6］Kim D，Kim K S，Park K H，et al.A music recommendation system with a dynamic k-means clustering algorithm［C］//International Conference on Machine Learning and Applications.IEEEComputer Society，2007：399-403.

［7］Zhang D，Xu C.A collaborative filtering recommendation system by unifying user similarity and item similarity［C］//International Conference on Web-Age Information Management.Springer-Verlag，2011：175-184.

［8］曹一鳴.協(xié)同過(guò)濾推薦瓶頸問(wèn)題綜述［J］.軟件，2012，33（12）：315-321.

CAOYiming.Collaborative Filtering Recommendation Bottlenecks Review［J］.SoftWare，2012，33（12）：315-321.

［9］王國(guó)霞，劉賀平.個(gè)性化推薦系統(tǒng)綜述［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（7）：66-76.

WANG Guoxia，LIU Heping.Survey of Personalized Recommendation System［J］.Computer Engineering and Application，2012，48（7）：66-76.

［10］Piatetsky G.Interview with Simon Funk［J］.Acm Sigkdd Explorations Newsletter，2007，9（1）：38-40.

［11］Koren Y，Bell R，Volinsky C.Matrix factorization techniques for recommender systems［J］.IEEE，Computer Journal，2009，42（8）：30-37.

［12］Koren Y.Factor in the neighbors：Scalable and accurate collaborative filtering［J］.ACM Transactions on Knowledge Discovery from Data（TKDD），2010，4（1）：1-11.

［13］劉建國(guó)，周濤，郭強(qiáng)，等.個(gè)性化推薦系統(tǒng)評(píng)價(jià)方法綜述［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2009，6（3）：1-10.

LIU Jianguo，ZHOU Tao，GUO Qiang.Overview of the Evaluated Algorithms for the Personal Recommendation Systems［J］.Complex Systems and Complexity Science，2009，6（3）：1-10.

［14］朱郁筱，呂琳媛.推薦系統(tǒng)評(píng)價(jià)指標(biāo)綜述［J］.電子科技大學(xué)學(xué)報(bào)，2012，41（2）：163-175.

ZHU Yuxiao，Lü Linyuan.Evaluation Metrics for Recommender Systems［J］.Journal of University of Electronic Science and Technology of China，2012，41（2）：163-175.