趙洋+劉方愛

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

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

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

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

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

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

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

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

1.1 訓(xùn)練步驟

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

（1）

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

（2）

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

（3）

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

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

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

（4）

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

1.2 算法描述

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

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

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

（2）對于每一個對象，分別計算它們的聚類中心表達式

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

；

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

1.3 預(yù)測步驟

我們根據(jù)聚類結(jié)果預(yù)測未知評分。因為在矩陣中有很多未知評分，所以即使實現(xiàn)最好的聚類結(jié)果也難以做出最準(zhǔn)確的預(yù)測。為了克服這方面的困難，我們采用對已知評分進行加權(quán)平均的方式來估計未知評分，方法如下：

（5）

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

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

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

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

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

·更新的范數(shù)：

·對于每個聚類，更新和之間的余弦相似性：

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

·更新的分配：

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

，

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

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

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

·將新用戶分配到第個聚類中；

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

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

2 實驗設(shè)置

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

3 實驗結(jié)果和分析

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

3.1 靜態(tài)情景

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

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

3.2 動態(tài)情景

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

4 結(jié)語

針對動態(tài)情景下協(xié)同過濾算法存在的數(shù)據(jù)稀疏性問題和數(shù)據(jù)頻繁變化帶來的一系列影響，本文提出了一種基于加權(quán)聚類的動態(tài)情景協(xié)同過濾推薦算法。實驗對比表明，WCM-DCF算法相比于現(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