融合隱語義模型的聚類協(xié)同過濾

邊文龍，黃曉霞

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

融合隱語義模型的聚類協(xié)同過濾

邊文龍，黃曉霞

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

協(xié)同過濾算法是推薦系統(tǒng)中應(yīng)用最廣泛的算法，隨著用戶數(shù)量和物品數(shù)量的不斷增加，傳統(tǒng)的協(xié)同過濾算法不能滿足推薦系統(tǒng)的實(shí)時(shí)需求。本文提出了一種融合隱語義模型的聚類協(xié)同過濾算法。首先利用隱語義模型分解評(píng)分矩陣，然后在分解后的矩陣上利用傳統(tǒng)的聚類算法聚合相同類別的物品，最后在相同類別的物品之間進(jìn)行基于項(xiàng)目的協(xié)同過濾推薦。實(shí)驗(yàn)結(jié)果表明，該算法有效減少了推薦時(shí)間，同時(shí)在一定程度上提高了算法精度。

推薦系統(tǒng)；隱語義模型；聚類算法；協(xié)同過濾

0　引言

隨著互聯(lián)網(wǎng)的蓬勃發(fā)展，用戶數(shù)量和信息量都呈指數(shù)型增長。不同的用戶都有其個(gè)性化的需求，如何快速地在這些復(fù)雜環(huán)境中找出那些滿足用戶興趣的信息，成為亟需要解決的問題。而推薦系統(tǒng)的功能就是針對(duì)不同的用戶根據(jù)其背景和喜好主動(dòng)推薦信息來滿足用戶的潛在興趣［1］。

協(xié)同過濾技術(shù)是現(xiàn)在推薦系統(tǒng)中應(yīng)用最廣的算法［2］，它的主要思想是根據(jù)用戶對(duì)相似項(xiàng)目的評(píng)分來預(yù)測(cè)對(duì)目標(biāo)項(xiàng)目的評(píng)分［3-4］。基于這種假設(shè)，大部分用戶對(duì)兩個(gè)商品i和j的評(píng)分都很相似，那么就可以考慮將其中一個(gè)商品推薦給只對(duì)另一個(gè)商品有評(píng)分的用戶?；陧?xiàng)目的協(xié)同過濾找到目標(biāo)項(xiàng)目的若干近鄰，產(chǎn)生推薦列表。傳統(tǒng)的協(xié)同過濾算法是利用用戶的歷史行為，來預(yù)測(cè)用戶對(duì)目標(biāo)用戶的評(píng)分。需要在整個(gè)用戶空間上去尋找最近鄰居。隨著電子商務(wù)的不斷發(fā)展，用戶數(shù)量和物品的數(shù)量都呈指數(shù)型增長，這樣傳統(tǒng)的算法就不能夠滿足推薦的實(shí)時(shí)需求。同時(shí)，傳統(tǒng)的協(xié)同過濾算法只是考慮了用戶的歷史行為，而沒有考慮物品之間的關(guān)系。針對(duì)這些問題，本文提出了一種融合隱語義模型的聚類協(xié)同過濾算法，區(qū)別于傳統(tǒng)的基于項(xiàng)目聚類的協(xié)同過濾［5］，本文算法沒有直接在用戶評(píng)分矩陣上進(jìn)行聚類，而是先將評(píng)分矩陣進(jìn)行分解，將得到的矩陣再進(jìn)行聚類，這樣聚類的維度降低，同時(shí)還考慮了物品類別信息，提高了推薦系統(tǒng)實(shí)時(shí)響應(yīng)速度。

1　相關(guān)研究

隱語義模型（LFM）是由 Simon Funk在 Netflix Prize后公布的一個(gè)算法［6］。該算法的理論基礎(chǔ)是運(yùn)用SVD矩陣分解，把用戶評(píng)分矩陣R分解為兩個(gè)低維矩陣，然后用這兩個(gè)低維矩陣去估計(jì)目標(biāo)用戶對(duì)項(xiàng)目的評(píng)分。

傳統(tǒng)的SVD分解需要一個(gè)簡單的方法補(bǔ)全稀疏矩陣，使矩陣R變成一個(gè)稠密矩陣。這種需求在推薦系統(tǒng)面對(duì)大數(shù)據(jù)量的情況時(shí)需要很大的存儲(chǔ)空間。同時(shí)SVD矩陣分解的算法復(fù)雜性特別高，在高維稠密數(shù)據(jù)中進(jìn)行矩陣分解特別慢。LFM正是為解決這兩個(gè)問題而提出的。

LFM將評(píng)分矩陣R分解為兩個(gè)低維矩陣相乘：

R?=PT×Q

其中P∈Rf×m，Q∈Rf×n，而且f＜＜m，從而達(dá)到降維的目的。

可以直接通過訓(xùn)練集的觀察值，利用最小化RMSE來學(xué)習(xí)P、Q。損失函數(shù)定義為：

其中λ‖Pi‖2+λ‖Qj‖2是用來防止過擬合的正規(guī)化項(xiàng)。

最小化上面的損失函數(shù)可以采用隨機(jī)梯度下降算法，通過求參數(shù)的偏導(dǎo)數(shù)來找出最快下降方向，然后迭代地不斷去優(yōu)化參數(shù)。

首先求出參數(shù)的偏導(dǎo)數(shù)：

當(dāng)損失函數(shù)達(dá)到最小值時(shí)，迭代結(jié)束，得到矩陣P和Q，分別為用戶對(duì)隱藏類別的興趣權(quán)重和項(xiàng)目屬于不同隱藏類別的權(quán)重。

2　融合隱語義模型的聚類協(xié)同過濾

基于項(xiàng)目聚類的協(xié)同過濾算法能夠有效地降低計(jì)算維度，減少運(yùn)算時(shí)間。然而這種算法也存在不足之處。在大型的電子商務(wù)系統(tǒng)中，項(xiàng)目的數(shù)量很大，例如淘寶上的商品數(shù)量多達(dá)8億之多。同時(shí)用戶的評(píng)分項(xiàng)目又很少，一般不會(huì)達(dá)到1％，所以實(shí)際上數(shù)據(jù)是很稀疏的。直接對(duì)這些稀疏的數(shù)據(jù)進(jìn)行聚類，效果不是很理想，維度過大。因此提出了融合隱語義模型的聚類算法。

2.1項(xiàng)目聚類

傳統(tǒng)的協(xié)同過濾算法沒有考慮物品本身的類別信息，如電影的分類、電商物品的類別等。因此可以利用物品的類別，把相同類別的物品聚類到一塊來推薦給喜歡這類物品的用戶。但是，實(shí)際的推薦系統(tǒng)中物品的數(shù)量很大，很難人為地去給物品進(jìn)行分類，同時(shí)有些物品的屬性特殊，無法歸屬于特定的類別。

利用LFM可以把用戶的評(píng)分矩陣R分解為兩個(gè)矩陣：一個(gè)是用戶對(duì)不同類別物品的喜愛權(quán)重矩陣P，另一個(gè)是不同物品屬于不同類別的權(quán)重Q。然后可以在矩陣Q上進(jìn)行傳統(tǒng)的聚類算法［7-8］，把矩陣Q分解為K個(gè)簇｛C1C2…Ck｝，每一個(gè)簇就代表一種物品的類別，這樣就自動(dòng)生成了原來很難定義的類別。

算法1：融合隱語義模型的聚類算法

輸入：用戶-項(xiàng)目評(píng)分矩陣R，聚類個(gè)數(shù)S

輸出：S個(gè)聚類簇

方法：

（1）利用公式（1）、（2）、（3）對(duì)評(píng)分矩陣R進(jìn)行矩陣分解，得到用戶矩陣P和項(xiàng)目矩陣Q：

（2）設(shè)矩陣Q中項(xiàng)目集合為I=｛i1，i2…in｝；

（3）在項(xiàng)目矩陣中任意選擇S個(gè)項(xiàng)目，作為初始聚類的中心CC=｛cc1，cc2…ccs｝；

（4）將S個(gè)聚類集合初始化為空，C=｛c1，c2…cs｝；

（5）repeat

for each item i in I

for each item c in CC

計(jì)算i和c的相似性

end for

計(jì)算i最近的聚類中心，把i加到最近的聚類集合中

end for

for each item cc in CC

計(jì)算新的聚類中心

end for

until聚類中心不變

（6）返回。

2.2產(chǎn)生推薦

為了得到目標(biāo)用戶的若干鄰居，需要度量不同用戶的相似性，從而找出與目標(biāo)用戶最相似的鄰居集合。相似性度量的方法主要有兩種：

（1）余弦相似性：采用標(biāo)準(zhǔn)的向量余弦夾角計(jì)算，用戶Ui和Uj的相似度Sim（Ui，Uj）的計(jì)算方法如下：

（2）改進(jìn)的余弦相似性：為了減少不同用戶評(píng)分尺度上的差異，改進(jìn)的余弦相似性用減去平均分后的分?jǐn)?shù)計(jì)算相似性：

在進(jìn)行協(xié)同過濾的最近鄰查詢時(shí)，目標(biāo)用戶的最近鄰居大部分分布在與目標(biāo)項(xiàng)目相似性最高的若干個(gè)簇里，因此不需要在整個(gè)項(xiàng)目空間上尋找最近鄰。算法的復(fù)雜度降低。

假設(shè)目標(biāo)項(xiàng)目I的最近鄰居集合用Ci=｛Ci1，Ci2…Cik｝表示，采用余弦相似度計(jì)算相似性，則用戶U對(duì)項(xiàng)目I的預(yù)測(cè)評(píng)分計(jì)算如下：

算法2：利用聚類結(jié)果產(chǎn)生推薦

輸入：用戶-項(xiàng)目評(píng)分矩陣R，項(xiàng)目聚類C，聚類中心CC，鄰居個(gè)數(shù)K，相似度閾值Y。

輸出：目標(biāo)用戶U對(duì)目標(biāo)項(xiàng)目I的評(píng)分。

方法：

（1）初始化與目標(biāo)項(xiàng)目I相似的集合SC為空

（2）for item cc in CC

（3）if sim（cc，i）〉Y

（4）cc所在的簇加入集合SC

（5）end for

（6）for item i in SC

（7）計(jì)算sim（i，I）

（8）end for

（9）選出相似度最高的k個(gè)鄰居。

（10）利用公式6，計(jì)算用戶U對(duì)目標(biāo)I的評(píng)分。

（11）返回。

利用算法2可以得到用戶對(duì)項(xiàng)目的預(yù)測(cè)評(píng)分，從中選出評(píng)分最高的K個(gè)項(xiàng)目推薦給用戶。

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

3.1數(shù)據(jù)集及度量標(biāo)準(zhǔn)

實(shí)驗(yàn)采用MovieLens站點(diǎn)（http://movielens.umn.edu）提供的數(shù)據(jù)集［9］。該站點(diǎn)是一個(gè)基于Web的研究性推薦系統(tǒng)，用于接受用戶對(duì)電影的評(píng)分并且提供相應(yīng)的推薦列表，該數(shù)據(jù)集包含943個(gè)用戶對(duì)1 682部電影的100 000個(gè)評(píng)分，評(píng)分的范圍為1～5，而且每個(gè)用戶至少有20個(gè)評(píng)分。整個(gè)實(shí)驗(yàn)根據(jù)需要進(jìn)一步劃分?jǐn)?shù)據(jù)集，其中的80％作為訓(xùn)練集，20％作為測(cè)試集。

實(shí)驗(yàn)采用絕對(duì)偏差MAE作為度量標(biāo)準(zhǔn)，通過計(jì)算預(yù)測(cè)評(píng)分與實(shí)際評(píng)分之間的差別來度量算法的準(zhǔn)確性，MAE越小，算法的準(zhǔn)確性越高。設(shè)通過算法預(yù)測(cè)的評(píng)分為，…｝，用戶實(shí)際的評(píng)分為｛P1，P2…Pk｝，則MAE的定義為：

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

本文提出的算法并不保證能夠找到目標(biāo)項(xiàng)目的所有最近鄰，因?yàn)榫垲愋纬傻拇刂行目赡苓h(yuǎn)離目標(biāo)項(xiàng)目。下面把所提出改進(jìn)算法與基于項(xiàng)目的協(xié)同過濾進(jìn)行比較，使用MAE和運(yùn)行時(shí)間作為度量標(biāo)準(zhǔn)。

固定鄰居個(gè)數(shù)k=20，可以得到不同聚類個(gè)數(shù)對(duì)MAE的影響，如圖1所示。

如圖1所示，當(dāng)k=15時(shí)，本文提出的算法的MAE達(dá)到最小值，比基于項(xiàng)目的協(xié)同過濾還要小，但隨著聚類個(gè)數(shù)的增加，MAE開始變大。

固定聚類個(gè)數(shù)c=10，可以得到不同鄰居個(gè)數(shù)對(duì)算法MAE的影響，如圖2所示。

如圖2所示，算法在不同鄰居個(gè)數(shù)上的MAE與Item-Base保持基本相同，在某些鄰居點(diǎn)上算法的MAE更小。

固定鄰居個(gè)數(shù)k=20，可以得到不同聚類個(gè)數(shù)產(chǎn)生推薦的時(shí)間，如圖3所示。

圖3　聚類個(gè)數(shù)對(duì)運(yùn)行時(shí)間的影響

如圖3所示，融合LFM的聚類協(xié)同過濾算法的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)小于傳統(tǒng)的協(xié)同過濾算法，能夠更好地滿足推薦的實(shí)時(shí)要求。

4　結(jié)論

針對(duì)傳統(tǒng)的基于項(xiàng)目的協(xié)同過濾算法在面對(duì)大數(shù)據(jù)量的情況下表現(xiàn)出的性能不佳，以及基于項(xiàng)目聚類算法不能很好地應(yīng)對(duì)稀疏數(shù)據(jù)、沒有考慮物品類別等問題，本文提出了一種融合隱語義模型的聚類協(xié)同過濾算法。算法首先對(duì)用戶的評(píng)分?jǐn)?shù)據(jù)進(jìn)行矩陣分解，得到物品的類別信息；然后在分解后的矩陣上進(jìn)行傳統(tǒng)的聚類算法。實(shí)驗(yàn)表明，本文提出的算法可以有效提高推薦系統(tǒng)的響應(yīng)速度。同時(shí)由于利用了隱語義模型，推薦的過程中加入了商品類別信息，從而在一定程度上提高了算法的精度。

［1］SCHAFER J B，KONGSTAN J A，RIED J.E-commerce recommendation applications［J］.Data Mining and Knowledge Discovery，2001，5（1/2）：115-153.

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

［3］SARWAR B，KARYPIS G，KONSTAN J，et al.Itembased collaborative filtering recommendation algorithms［C］.In Proceedings of the Tenth International World Wide Web Conference，2001：285-295.

［4］DESHPANDE M，KARYPIS G.Item-based top-N recommendation algorithms［J］.ACM Transactions on Information Systems，2004，22（1）：143-177.

［5］鄧愛林，左子葉，朱楊勇.基于項(xiàng)目聚類的協(xié)同過濾推薦算法［J］.小型微型計(jì)算機(jī)，2004，25（9）：1665-1670.

［6］DUMAIS S T.Latent semantic analysis［J］.Annual Review of Information Science and Technology，2004，38（1）：188-230.

［7］DEMPSTER A，LAIRD N，RUBIN D.Maximum likelihood from incomplete data via the EM algorithm［J］.Journal of the Royal Statistical Society，1977，38（1）：1-38.

［8］THIESSON B，MEEK C，CHICKERING D，et al.Learning mixture of DAG models［C］.Proceeding of the Fourteenth Conference on Uncertainty in Articial Intelligence，1998：504-513.

［9］MILLER B N，ALBERT I，LAM S K，et al.Movie lens unplugged：experiences with an occasionally connected recommender system ［C］.Proceedings of the 8thInternational Conference on Intelligent User Interfaces，New York，2003：263-266.

Collaborative filtering combine with latent factor model and cluster

Bian Wenlong，Huang Xiaoxia

（Information Engineering College，Shanghai Maritime University，Shanghai 201306，China）

Collaborative filtering has widely been used in recommend system.With the increase of users and items，the traditional algorithm can not satisfy the real-time demand of recommend system.This paper proposes a collaborative filtering algorithm that combine with latent factor model and cluster.The first step is decomposition of matrix with LFM.Then polymerize the same category of items by using traditional cluster algorithm.Finally use the item based collaborative filtering in the cluster.The result shows that the algorithm reduces the calculation time and improves the accuracy of the algorithm in a certain extent.

recommend system；latent factor model；cluster algorithm；collaborative filtering

TP391

A

1674-7720（2015）15-0026-03

邊文龍，黃曉霞.融合隱語義模型的聚類協(xié)同過濾［J］.微型機(jī)與應(yīng)用，2015，34（15）：26-28，32.

2015-04-05）

邊文龍（1992-），通信作者，男，碩士研究生，主要研究方向：數(shù)據(jù)挖掘。E-mail：lwwenlong@126.com。

黃曉霞（1968-），女，博士研究生，副教授，主要研究方向：港航與物流信息管理、智能信息處理。