基于加權(quán)聚類的動(dòng)態(tài)協(xié)同過(guò)濾推薦算法

趙洋+劉方愛(ài)

摘要：針對(duì)傳統(tǒng)協(xié)同過(guò)濾推薦算法存在數(shù)據(jù)稀疏性及動(dòng)態(tài)情景下推薦效率急劇下降的問(wèn)題，提出了一種基于加權(quán)聚類的動(dòng)態(tài)情景協(xié)同過(guò)濾推薦算法。該方法對(duì)提供較多評(píng)分的用戶給予更多的重視，在運(yùn)用SK-means聚類方法的基礎(chǔ)上引入用戶權(quán)重的概念，有效的解決了數(shù)據(jù)稀疏性的問(wèn)題，在此基礎(chǔ)上考慮增量更新的情況以便處理推薦過(guò)程中數(shù)據(jù)的頻繁變化帶來(lái)的影響，優(yōu)化了對(duì)目標(biāo)用戶的偏好預(yù)測(cè)和個(gè)性化推薦建議。實(shí)驗(yàn)結(jié)果表明，相比于IUCF、IICF、和COCLUST算法，該算法在有效緩解用戶評(píng)分?jǐn)?shù)據(jù)稀疏性的同時(shí)，還以非常低的計(jì)算成本提供了高質(zhì)量的推薦建議。

關(guān)鍵詞：協(xié)同過(guò)濾；加權(quán)聚類方法；數(shù)據(jù)稀疏性；動(dòng)態(tài)情景；推薦效率

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2017）05-0142-03

推薦系統(tǒng)[1]收集用戶的歷史數(shù)據(jù)和其他相關(guān)信息，利用數(shù)據(jù)挖掘方法和各種數(shù)學(xué)模型進(jìn)行分析計(jì)算，準(zhǔn)確預(yù)測(cè)用戶的興趣愛(ài)好，主動(dòng)向用戶推薦可能感興趣的內(nèi)容。

傳統(tǒng)的協(xié)同過(guò)濾算法在靜態(tài)情境下可以實(shí)現(xiàn)良好的預(yù)測(cè)精度，但隨著用戶數(shù)目和項(xiàng)目數(shù)量的持續(xù)增加以及評(píng)分的不斷更新，協(xié)同過(guò)濾算法的數(shù)據(jù)稀疏性問(wèn)題以及推薦效率急劇下降的問(wèn)題越來(lái)越突出，這直接導(dǎo)致了推薦系統(tǒng)的推薦質(zhì)量迅速下降。針對(duì)這一問(wèn)題，相關(guān)研究引入了不同的算法[3]。例如，X.Yang等人[4]通過(guò)計(jì)算和分析不同情況下項(xiàng)目間的相似性，使用動(dòng)態(tài)增量更新和本地鏈路預(yù)測(cè)的方式，提出一種以可擴(kuò)展項(xiàng)目為基礎(chǔ)的協(xié)同過(guò)濾算法。該算法提出一種基于項(xiàng)目相似度圖的傳遞結(jié)構(gòu)，使用本地鏈路預(yù)測(cè)方法來(lái)尋找隱性候選項(xiàng)目，以減輕預(yù)測(cè)和建議的過(guò)程中數(shù)據(jù)稀疏帶來(lái)的負(fù)面影響，從而提高了傳統(tǒng)協(xié)同過(guò)濾算法的性能和推薦效率。大多數(shù)推薦算法都不能處理動(dòng)態(tài)情景，例如基于奇異值分解的協(xié)同過(guò)濾算法[5]不能處理出現(xiàn)新評(píng)分以及更新現(xiàn)有評(píng)分的情況。而基于內(nèi)存的協(xié)同過(guò)濾算法普遍存在數(shù)據(jù)稀疏性以及推薦效率低的問(wèn)題。

我們?cè)赟K-means聚類方法[6]的基礎(chǔ)上引入權(quán)重的概念，并由此推導(dǎo)出了一種動(dòng)態(tài)情景下的協(xié)同過(guò)濾推薦算法，不僅弱化了算法中數(shù)據(jù)稀疏性帶來(lái)的影響，還有效的解決了數(shù)據(jù)頻繁變化帶來(lái)的一系列問(wèn)題。

1 基于加權(quán)聚類的動(dòng)態(tài)推薦算法

我們提出的基于加權(quán)聚類的動(dòng)態(tài)協(xié)同過(guò)濾推薦算法可以分為三個(gè)主要步驟：訓(xùn)練、預(yù)測(cè)和增量訓(xùn)練。

1.1 訓(xùn)練步驟

首先將用戶劃分為k個(gè)聚類。為了解決這個(gè)問(wèn)題，我們將一種適用于協(xié)同過(guò)濾推薦系統(tǒng)的SK-means聚類方法引入到WCM-DCF算法中。因此，所得到的集群將受到最有用的用戶的高度影響。我們令表示第個(gè)用戶的權(quán)重，SK-means聚類方法的加權(quán)目標(biāo)函數(shù)可以表示為：

（1）

更新后用于加權(quán)的SK-means聚類方法的質(zhì)心計(jì)算公式如下：

（2）

我們給出用戶權(quán)重的直觀計(jì)算公式。令為一個(gè)二進(jìn)制矩陣。第行對(duì)應(yīng)的向量指示已經(jīng)被第個(gè)用戶評(píng)分的項(xiàng)目。由此我們將第個(gè)用戶的權(quán)重定義為與其可用評(píng)分的數(shù)量成比例，公式如下：

（3）

其中是所有值均為1的適當(dāng)維度的向量，表示用戶提供的項(xiàng)目評(píng)分的標(biāo)準(zhǔn)差。僅從已經(jīng)評(píng)價(jià)了許多項(xiàng)目的用戶集合中選擇初始質(zhì)心也不是最優(yōu)解決方案，因?yàn)椴粫?huì)檢測(cè)到所有結(jié)構(gòu)特征。為了避免這個(gè)問(wèn)題，我們通過(guò)以下步驟進(jìn)行聚類初始化：

（1）將用戶隨機(jī)分區(qū)生成為k個(gè)聚類，由表示，其中表示第i個(gè)用戶所屬的聚類。

（2）令表示第k個(gè)質(zhì)心的第j個(gè)分量，估計(jì)初始質(zhì)心公式如下：

（4）

根據(jù)公式（4），通過(guò)獲取相應(yīng)聚類內(nèi)第個(gè)項(xiàng)目的評(píng)分總和來(lái)估計(jì)初始質(zhì)心的分量。因此很少被評(píng)價(jià)的項(xiàng)目將會(huì)被自動(dòng)弱化。2.2的算法更詳細(xì)的描述了我們的訓(xùn)練步驟。

1.2 算法描述

輸入：目標(biāo)用戶，大小為的用戶-項(xiàng)目評(píng)分矩陣，聚類數(shù)量k，批處理迭代次數(shù)B

輸出：聚類K的質(zhì)心，分解矩陣

（1）聚類中心初始化：令，隨機(jī)產(chǎn)生球面聚類質(zhì)心；

（2）對(duì)于每一個(gè)對(duì)象，分別計(jì)算它們的聚類中心表達(dá)式

（3）通過(guò)競(jìng)爭(zhēng)學(xué)習(xí)計(jì)算使目標(biāo)函數(shù)最接近用戶的球面質(zhì)心：

；

（4）令，b從1循環(huán)到B，i從1循環(huán)到n，迭代以上步驟。

1.3 預(yù)測(cè)步驟

我們根據(jù)聚類結(jié)果預(yù)測(cè)未知評(píng)分。因?yàn)樵诰仃囍杏泻芏辔粗u(píng)分，所以即使實(shí)現(xiàn)最好的聚類結(jié)果也難以做出最準(zhǔn)確的預(yù)測(cè)。為了克服這方面的困難，我們采用對(duì)已知評(píng)分進(jìn)行加權(quán)平均的方式來(lái)估計(jì)未知評(píng)分，方法如下：

（5）

公式（5）的核心思想是根據(jù)每個(gè)用戶與其對(duì)應(yīng)的質(zhì)心之間的相似性利用權(quán)重對(duì)用戶做出的可用評(píng)分進(jìn)行加權(quán)，以便對(duì)最接近質(zhì)心的用戶給予更高的權(quán)重。

我們提出的預(yù)測(cè)公式（5）的另一個(gè)優(yōu)點(diǎn)在于它給出的預(yù)測(cè)信息只取決于聚類結(jié)果，這就意味著它可以離線執(zhí)行并將結(jié)果存儲(chǔ)在大小為的矩陣中，大大縮短預(yù)測(cè)時(shí)間。

1.4 增量訓(xùn)練步驟

我們考慮增量更新的情況以便處理協(xié)同過(guò)濾過(guò)程中數(shù)據(jù)的頻繁變化。首先區(qū)分四種主要情況：（1）提交新評(píng)分；（2）更新現(xiàn)有評(píng)分；（3）新用戶的出現(xiàn)；（4）新項(xiàng)目的出現(xiàn)。下面我們給出每種情況的更新公式。

提交新評(píng)分及更新現(xiàn)有評(píng)分情況：為項(xiàng)目提交新評(píng)分的活躍用戶用表示。下面的等式給出了在這種情況下執(zhí)行動(dòng)態(tài)更新的情況：

·更新的范數(shù)：

·對(duì)于每個(gè)聚類，更新和之間的余弦相似性：

·更新活動(dòng)用戶的權(quán)重：

·更新的分配：

·根據(jù)公式（3）更新相應(yīng)的質(zhì)心，滿足條件

，

符號(hào)表示提交新的評(píng)分后的用戶，和分別表示項(xiàng)目之前的評(píng)分和的平均評(píng)分。由于質(zhì)心在訓(xùn)練結(jié)束時(shí)相對(duì)穩(wěn)定，所以隨著后續(xù)增量的不斷更新，重新分配時(shí)不需要根據(jù)每個(gè)新評(píng)分加入后重新執(zhí)行。endprint

出現(xiàn)新用戶：在這種情況下只需將新用戶實(shí)時(shí)合并到模型中。令表示新用戶，模型的動(dòng)態(tài)增量步驟如下：

·根據(jù)公式（3）計(jì)算新用戶的權(quán)重；

·將新用戶分配到第個(gè)聚類中；

·更新對(duì)應(yīng)的質(zhì)心：

出現(xiàn)新項(xiàng)目：新項(xiàng)目出現(xiàn)時(shí)沒(méi)有評(píng)分，因此模型中沒(méi)有需要更改的內(nèi)容。當(dāng)新項(xiàng)目開始接收新的評(píng)分時(shí)，只需針對(duì)新項(xiàng)目進(jìn)行處理，減少處理新出現(xiàn)評(píng)分的過(guò)程。

2 實(shí)驗(yàn)設(shè)置

在模擬實(shí)驗(yàn)中，通過(guò)對(duì)比不同算法的接受者行為特征（Receiver Operating Characteristic ， ROC）曲線、準(zhǔn)確率（Precision）和召回率（Recall）來(lái)驗(yàn)證該算法的性能。實(shí)驗(yàn)數(shù)據(jù)集選用著名電影評(píng)分?jǐn)?shù)據(jù)集，該數(shù)據(jù)及包含6040個(gè)用戶對(duì)3952部電影做出的100萬(wàn)條評(píng)分記錄。實(shí)驗(yàn)對(duì)比對(duì)象有基于用戶的增量協(xié)同過(guò)濾（incremental user-based CF，IUCF）算法、基于項(xiàng)目的增量協(xié)同過(guò)濾（incremental item-based CF，IICF）算法、基于協(xié)同聚類的增量協(xié)同過(guò)濾（incremental CF based on co-clustering，COCLUST）算法。

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

我們采用以下策略評(píng)價(jià)推薦系統(tǒng)的質(zhì)量。（1）我們從數(shù)據(jù)集中隨機(jī)生成10個(gè)訓(xùn)練-測(cè)試（80-20%）集合。（2）在測(cè)試集中，推薦系統(tǒng)獲取每個(gè)用戶給出的個(gè)評(píng)分，其他評(píng)分被保留用于預(yù)測(cè)評(píng)價(jià)。在推薦過(guò)程中，我們?cè)陟o態(tài)情況下設(shè)置=10，動(dòng)態(tài)情境下設(shè)置=5。（3）在開始比較之前，我們使用ML-1M數(shù)據(jù)集上的不同參數(shù)對(duì)每個(gè)推薦系統(tǒng)進(jìn)行多次實(shí)驗(yàn)，并保留對(duì)應(yīng)最佳性能的參數(shù)。圖1給出了WCM-DCF算法在ML-1M數(shù)據(jù)集上隨著聚類數(shù)目的增多的變化情況。（4）在10個(gè)訓(xùn)練測(cè)試集中根據(jù)ROC曲線、等指標(biāo)參數(shù)對(duì)每個(gè)推薦系統(tǒng)進(jìn)行綜合評(píng)價(jià)。

3.1 靜態(tài)情景

圖2和圖3給出了在ML-1M數(shù)據(jù)集上不同協(xié)同過(guò)濾算法的ROC曲線和參數(shù)比較。圖2通過(guò)改變前N個(gè)推薦列表的大小并且用每個(gè)協(xié)同過(guò)濾算法的假正類率（false positive rate， FPR）與真正類率（true positive rate ，TPR）的線性關(guān)系來(lái)構(gòu)建ROC曲線。圖3中，我們假定最長(zhǎng)的列表包含40個(gè)元素，每種方法的參數(shù)在不同的列表上各有不同。

從圖2和圖3中我們發(fā)現(xiàn)，在ML-1M數(shù)據(jù)集上，我們給出的WCM-DCF算法得出的計(jì)算結(jié)果遠(yuǎn)遠(yuǎn)優(yōu)于所有其他增量方法，提供了高質(zhì)量的推薦建議。我們還發(fā)現(xiàn)COCLUST算法給出的推薦結(jié)果質(zhì)量最低。

3.2 動(dòng)態(tài)情景

在動(dòng)態(tài)情景下，每種推薦方法的訓(xùn)練步驟之后遞增的并入動(dòng)態(tài)情景。從圖5及圖6中我們觀察到，在動(dòng)態(tài)情況下，WCM-DCF算法優(yōu)于所有其他增量方法。我們還觀察到COCLUST在動(dòng)態(tài)情況下繼續(xù)提供較差的性能，因?yàn)樗鼉H使用部分更新來(lái)處理推薦過(guò)程中數(shù)據(jù)的變化，因此新信息不能以動(dòng)態(tài)方式并入模型中。

4 結(jié)語(yǔ)

針對(duì)動(dòng)態(tài)情景下協(xié)同過(guò)濾算法存在的數(shù)據(jù)稀疏性問(wèn)題和數(shù)據(jù)頻繁變化帶來(lái)的一系列影響，本文提出了一種基于加權(quán)聚類的動(dòng)態(tài)情景協(xié)同過(guò)濾推薦算法。實(shí)驗(yàn)對(duì)比表明，WCM-DCF算法相比于現(xiàn)有的推薦算法具有更好的有效性，同時(shí)需要更少的計(jì)算時(shí)間。

參考文獻(xiàn)

[1]HERLOCKER J L， KONSTAN J A， Terveen L G， et al. Evaluating collaborative filtering recommender systems [J]. ACM Transactions on Information Systems （TOIS）， 2004， 22（1）： 5-53.

[2]B. Sarwar， G. Karypis， J. Konstan， J. Riedl， et al. Incremental singular value decomposition algorithms for highly scalable recommender systems， In： Fifth International Conference on Computer and Information Science， 2002， pp. 27-28.

[3]X. Yang， Z. Zhang， K. Wang， Scalable collaborative filtering using incremental update and local link prediction， In： Proceedings of the 21st ACM International Conference on Information and Knowledge Management， ACM， 2012， pp. 2371-2374.

[4]B. Sarwar， G. Karypis， J. Konstan， J. Riedl， Incremental singular value decomposition algorithms for highly scalable recommender systems， In： Fifth International Conference on Computer and Information Science， 2002， pp. 27-28.

[5]I.S. Dhillon， D.S. Modha， Concept decompositions for large sparse text data using clustering， Mach. Learn. 42 （1-2） （2001） 143-175.

[6]Hornik K， Feinerer I， Kober M， et al. Spherical k-Means Clustering[J]. Journal of Statistical Software， 2016， 50（10）：1-22.endprint