摘  要： 協(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í)在一定程度上提高了算法精度。

　　關(guān)鍵詞： 推薦系統(tǒng),；隱語義模型,；聚類算法；協(xié)同過濾

0 引言

　　隨著互聯(lián)網(wǎng)的蓬勃發(fā)展,，用戶數(shù)量和信息量都呈指數(shù)型增長(zhǎng),。不同的用戶都有其個(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ù)型增長(zhǎng),，這樣傳統(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è)簡(jiǎn)單的方法補(bǔ)全稀疏矩陣,，使矩陣R變成一個(gè)稠密矩陣,。這種需求在推薦系統(tǒng)面對(duì)大數(shù)據(jù)量的情況時(shí)需要很大的存儲(chǔ)空間。同時(shí)SVD矩陣分解的算法復(fù)雜性特別高,，在高維稠密數(shù)據(jù)中進(jìn)行矩陣分解特別慢,。LFM正是為解決這兩個(gè)問題而提出的,。

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

　　其中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ù)：

　　然后,，根據(jù)隨機(jī)梯度下降算法，得到迭代計(jì)算公式：

　　當(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）、（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}；

　?。?）將S個(gè)聚類集合初始化為空,，C={c1，c2…cs},；

　?。?）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聚類中心不變

　?。?）返回,。

　　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ì)算如下：

　　sim（i,，j）表示項(xiàng)目i和j之間的相似度，Ri和Rj表示對(duì)項(xiàng)目i和j的平均評(píng)分,。

　　算法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)分,。

　　方法：

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

　　（2）for item cc in CC

　?。?）if sim（cc,，i）>Y

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

　?。?）end for

　?。?）for item i in SC

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

　?。?）end for

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

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

　?。?1）返回。

　　利用算法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所示,，融合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í)由于利用了隱語義模型,，推薦的過程中加入了商品類別信息,，從而在一定程度上提高了算法的精度。

參考文獻(xiàn)

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

　　[3] SARWAR B,， KARYPIS G， KONSTAN J,， et al. Item-based 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 8th International Conference on Intelligent User Interfaces,， New York,， 2003： 263-266.