《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 融合隱語(yǔ)義模型的聚類(lèi)協(xié)同過(guò)濾
融合隱語(yǔ)義模型的聚類(lèi)協(xié)同過(guò)濾
2015年微型機(jī)與應(yīng)用第15期
邊文龍,,黃曉霞
(上海海事大學(xué) 信息工程學(xué)院,上海 201306)
摘要: 協(xié)同過(guò)濾算法是推薦系統(tǒng)中應(yīng)用最廣泛的算法,,隨著用戶(hù)數(shù)量和物品數(shù)量的不斷增加,傳統(tǒng)的協(xié)同過(guò)濾算法不能滿(mǎn)足推薦系統(tǒng)的實(shí)時(shí)需求,。本文提出了一種融合隱語(yǔ)義模型的聚類(lèi)協(xié)同過(guò)濾算法。首先利用隱語(yǔ)義模型分解評(píng)分矩陣,,然后在分解后的矩陣上利用傳統(tǒng)的聚類(lèi)算法聚合相同類(lèi)別的物品,,最后在相同類(lèi)別的物品之間進(jìn)行基于項(xiàng)目的協(xié)同過(guò)濾推薦。實(shí)驗(yàn)結(jié)果表明,,該算法有效減少了推薦時(shí)間,,同時(shí)在一定程度上提高了算法精度。
Abstract:
Key words :

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

  關(guān)鍵詞: 推薦系統(tǒng);隱語(yǔ)義模型,;聚類(lèi)算法,;協(xié)同過(guò)濾

0 引言

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

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

1 相關(guān)研究

  隱語(yǔ)義模型(LFM)是由Simon Funk在Netflix Prize后公布的一個(gè)算法[6],。該算法的理論基礎(chǔ)是運(yùn)用SVD矩陣分解,把用戶(hù)評(píng)分矩陣R分解為兩個(gè)低維矩陣,,然后用這兩個(gè)低維矩陣去估計(jì)目標(biāo)用戶(hù)對(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è)問(wèn)題而提出的,。

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

 SHCSM6UM69R3ND`N[{5ENCQ.png

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

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

  1.png

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

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

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

 2.png

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

  3.png

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

2 融合隱語(yǔ)義模型的聚類(lèi)協(xié)同過(guò)濾

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

  2.1 項(xiàng)目聚類(lèi)

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

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

  算法1:融合隱語(yǔ)義模型的聚類(lèi)算法

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

  輸出:S個(gè)聚類(lèi)簇

  方法:

 ?。?)利用公式(1),、(2)、(3)對(duì)評(píng)分矩陣R進(jìn)行矩陣分解,,得到用戶(hù)矩陣P和項(xiàng)目矩陣Q:

 ?。?)設(shè)矩陣Q中項(xiàng)目集合為I={i1,i2…in},;

 ?。?)在項(xiàng)目矩陣中任意選擇S個(gè)項(xiàng)目,作為初始聚類(lèi)的中心CC={cc1,,cc2…ccs},;

  (4)將S個(gè)聚類(lèi)集合初始化為空,,C={c1,,c2…cs};

 ?。?)repeat

  for each item i in I

  for each item c in CC

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

  end for

  計(jì)算i最近的聚類(lèi)中心,,把i加到最近的聚類(lèi)

  集合中

  end for

  for each item cc in CC

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

  end for

  until聚類(lèi)中心不變

  (6)返回,。

  2.2 產(chǎn)生推薦

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

 ?。?)余弦相似性:采用標(biāo)準(zhǔn)的向量余弦?jiàn)A角計(jì)算,用戶(hù)Ui和Uj的相似度Sim(Ui,,Uj)的計(jì)算方法如下:

  4.png

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

  5.png

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

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

  6.png

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

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

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

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

  方法:

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

 ?。?)for item cc in CC

  (3)if sim(cc,,i)>Y

 ?。?)cc所在的簇加入集合SC

  (5)end for

 ?。?)for item i in SC

 ?。?)計(jì)算sim(i,I)

 ?。?)end for

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

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

 ?。?1)返回,。

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

  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),用于接受用戶(hù)對(duì)電影的評(píng)分并且提供相應(yīng)的推薦列表,,該數(shù)據(jù)集包含943個(gè)用戶(hù)對(duì)1 682部電影的100 000個(gè)評(píng)分,,評(píng)分的范圍為1~5,而且每個(gè)用戶(hù)至少有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),通過(guò)計(jì)算預(yù)測(cè)評(píng)分與實(shí)際評(píng)分之間的差別來(lái)度量算法的準(zhǔn)確性,,MAE越小,,算法的準(zhǔn)確性越高。設(shè)通過(guò)算法預(yù)測(cè)的評(píng)分為YT]}OD%I1VX]K4C]D7~~LIR.jpg,,用戶(hù)實(shí)際的評(píng)分為{P1,,P2…Pk},則MAE的定義為:

  YJE)ZC%XL8690AFD8UJC2T8.png

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

  本文提出的算法并不保證能夠找到目標(biāo)項(xiàng)目的所有最近鄰,,因?yàn)榫垲?lèi)形成的簇中心可能遠(yuǎn)離目標(biāo)項(xiàng)目,。下面把所提出改進(jìn)算法與基于項(xiàng)目的協(xié)同過(guò)濾進(jìn)行比較,,使用MAE和運(yùn)行時(shí)間作為度量標(biāo)準(zhǔn)。

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

001.jpg

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

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

002.jpg

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

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

003.jpg

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

4 結(jié)論

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

參考文獻(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] 鄧愛(ài)林,,左子葉,朱楊勇.基于項(xiàng)目聚類(lèi)的協(xié)同過(guò)濾推薦算法[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.


此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載,。