基于加權聚類的動態協同過濾推薦算法

趙洋+劉方愛

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

關鍵詞：協同過濾；加權聚類方法；數據稀疏性；動態情景；推薦效率

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

推薦系統[1]收集用戶的歷史數據和其他相關信息，利用數據挖掘方法和各種數學模型進行分析計算，準確預測用戶的興趣愛好，主動向用戶推薦可能感興趣的內容。

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

我們在SK-means聚類方法[6]的基礎上引入權重的概念，并由此推導出了一種動態情景下的協同過濾推薦算法，不僅弱化了算法中數據稀疏性帶來的影響，還有效的解決了數據頻繁變化帶來的一系列問題。

1 基于加權聚類的動態推薦算法

我們提出的基于加權聚類的動態協同過濾推薦算法可以分為三個主要步驟：訓練、預測和增量訓練。

1.1 訓練步驟

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

（1）

更新后用于加權的SK-means聚類方法的質心計算公式如下：

（2）

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

（3）

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

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

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

（4）

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

1.2 算法描述

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

輸出：聚類K的質心，分解矩陣

（1）聚類中心初始化：令，隨機產生球面聚類質心；

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

（3）通過競爭學習計算使目標函數最接近用戶的球面質心：

；

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

1.3 預測步驟

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

（5）

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

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

1.4 增量訓練步驟

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

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

·更新的范數：

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

·更新活動用戶的權重：

·更新的分配：

·根據公式（3）更新相應的質心，滿足條件

，

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

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

·根據公式（3）計算新用戶的權重；

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

·更新對應的質心：

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

2 實驗設置

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

3 實驗結果和分析

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

3.1 靜態情景

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

從圖2和圖3中我們發現，在ML-1M數據集上，我們給出的WCM-DCF算法得出的計算結果遠遠優于所有其他增量方法，提供了高質量的推薦建議。我們還發現COCLUST算法給出的推薦結果質量最低。

3.2 動態情景

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

4 結語

針對動態情景下協同過濾算法存在的數據稀疏性問題和數據頻繁變化帶來的一系列影響，本文提出了一種基于加權聚類的動態情景協同過濾推薦算法。實驗對比表明，WCM-DCF算法相比于現有的推薦算法具有更好的有效性，同時需要更少的計算時間。

參考文獻

[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