結合關聯規則填充的協同過濾改進算法

包志強 宋靜霞

關鍵詞： 關聯規則; 數據填充; 協同過濾; 推薦算法; 評分矩陣; 數據稀疏; 對比實驗

中圖分類號： TN911.1?34; TP301.6 ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）03?0078?04

Abstract： Since the traditional collaborative filtering algorithm for personalized recommendation has the problems of sparse scoring matrix of user and item， low recommendation accuracy and cold start， an improved collaborative filtering recommendation algorithm based on association rules filling is proposed. The result obtained by association rules is added into this algorithm before the first step of the collaborative filtering algorithm to predict some items without score value. The obtained data is filled into original user?item scoring matrix to reduce the sparseness of the scoring matrix， which can provide the similarity calculation for more data. And on this basis， the traditional collaborative filtering algorithm based on item is combined to make recommendation to users. The experiment contrast is carried out with MovieLens dataset. The results show that， in comparison with the traditional algorithm， the proposed algorithm can improve the accuracy and effectiveness of the recommendation system.

Keywords： association rule; data filling; collaborative filtering; recommendation algorithm; scoring matrix; data sparseness; contrast experiment

0 ?引 ?言

當今是數據化的時代，每天被海量信息充斥，為便于人們從中快速準確地找到自己所需要的，個性化推薦應運而生，而協同過濾算法是其中最重要和運用最廣泛的一種技術方法。它最開始是對郵件進行過濾[1]，隨后運用在新聞推薦[2]中，現在擴展到物聯網、在線視頻等其他領域。傳統的協同過濾算法大致可以分為基于用戶的協同過濾[3]（user_based CF）和基于項目的協同過濾[4]（item_based CF）兩類。第一種方法先利用數據集中的相關數據求出不同用戶間的相似性，選擇和所求的用戶相似度比較高的那幾個用戶組成該用戶的近鄰用戶集合，然后再根據這些近鄰用戶對某些項目的評分值利用相關公式預測目標用戶的評分值;而第二種方法則是根據相同用戶之前已經評分過的不同項目計算不同項目之間的相似程度，去掉計算近鄰用戶，后續步驟和第一種類似。

但該算法有幾個非常明顯的缺陷，例如：冷啟動、推薦準確度低、可擴展性差以及數據稀疏等。為了進一步得到更精確的推薦結果，學者們基于現有技術和知識水平提出了很多新的方法和觀點對傳統算法進行改進。文獻[2]研究項目相似度的不同計算方法，并將結果與K?最近鄰算法進行比較。文獻[5]利用主成分分析法將高維的評分矩陣降為較低維。文獻[6]實現了一種基于可信任傳達的推薦辦法，這是在認為用戶間的信任關系具有傳播性的基礎上得到的。文獻[7]添加用戶標簽作為一個用戶興趣特征的相似度權重進行計算，提高了精度。文獻[8]通過打分精度和數量確定可信度得分，將用戶信任等級與相似度計算相結合，從而提高算法的準確性。文獻[9]建議通過社交網絡首先對用戶之間的信任度進行運算，然后通過用戶的興趣找到其最近鄰居，最后再融合用戶數據，從而提高推薦精度。總體而言，已有的大多數研究方法都是從提高相似度計算效率的角度來提高最終的推薦效果。

事實上，除了計算相似度的方法，數據本身的情況也會很大程度影響最終的推薦效果。在實際應用中，用戶數和項目數都是動態的，在不斷增多，隨之帶來的結果就是用戶?項目的評分矩陣漸漸變成了高維。而實際利用率通常在1%以下[10]，只是數據中很小的一部分，也就是說，此時的評分矩陣有用數據很少，大部分都是無意義的數據。如果系統通過某種方式填充了一些新數據加入到原來較稀疏的評分矩陣中，就降低了這個評分數據的稀疏性，問題就可能得到解決。

本文提出一種結合關聯規則的協同過濾改進算法（Association Rules Data Filling Item_Based Collaborative Filtering，ARDF?IBCF），該算法首先通過關聯規則得到二階頻繁項集的置信度，然后把置信度作為一個權值因子，按照用戶之前評分過的項目值預測出一些還沒有評分項目的評分值填充到用戶?項目矩陣中，接下來再按照傳統基于項目的協同過濾算法一步步施行，最終得到所需要的用戶推薦目錄，從而達到目的。

1 ?傳統基于項目的協同過濾算法

傳統基于項目的協同過濾算法就是將與用戶以前購買過的相類似的物品推薦給他們。第一步先計算項目間相似度，再根據項目間相似程度和用戶之前購買過的歷史記錄產生對用戶進行推薦的清單表。因此，在經常使用的傳統IBCF算法中，第一步是基礎。

通常使用以下三種相似性計算方法進行計算： 基于余弦的相似度計算、基于修正余弦相似度計算以及基于Pearson相關系數法相似度計算方法。其中基于Pearson相關系數法的相似度計算經過試驗比照證實在這三種方法中誤差最小，成效極明顯[11]。

假設有關于[m]個用戶和[n]個項目的一個數據集，可以通過一個[m×n]的大矩陣[R]表示數據集中用戶和項目的評分信息，如表1所示。表中第[i]行第[j]列元素[Rij]表示用戶[i]對項目[j]的實際評分值。

3.3 ?實驗結果及分析

關聯規則的支持度閾值一般設為5%～10%，置信度閾值一般設為70%～90%。本文實驗選擇置信度閾值[C=0.7]，當支持度閾值[S=0.15]時，得到181條規則，可以填充2 589項數據;當支持度閾值[S=0.1]時，得到577條規則，可以填充4 833項數據。通過比較傳統的UBCF，IBCF算法和本文實驗的改進算法的預測結果和測試集中給出的實際數據，分別計算RMSE和MAE值，得到的結果如表2～表4，圖1～圖3所示。

由表2和圖1可以得到，在本文數據集下，傳統算法中IBCF算法優于UBCF算法，所以本文實驗選擇關聯規則與IBCF相結合。

由表3和圖2可以得出，本文實驗ARDF?IBCF算法的RMSE和MAE值均小于IBCF算法，表示改進的算法確實提高了推薦效率的準確性。

由表4和圖3可以看出，在改進算法中填充數據較多的ARDF?IBCF（577）算法的RMSE和MAE值更小，推薦質量更優。

4 ?結 ?論

傳統協同過濾算法因為數據稀疏導致推薦質量效果差，本文提出一種基于關聯規則數據填充的改進算法。通過各個實驗對比顯示，先利用關聯規則預測出一些還未評分過的項目值填充至稀疏矩陣中，再運用傳統基于項目的協同過濾進行推薦，確實提高了推薦的準確性。因此本文提出的改進算法的推薦質量優于傳統的協同過濾算法，并具有一定的實際意義。

參考文獻

[1] HERLOKCER J L， KONSTAN J A， BORHCESR A， et al. An algorithmic framework for performing collaborative filtering [C]// Proceedings of 1999 ACM SIGIR Conference on Research and Development in Information Retrieval. Berkeley： ACM Press， 1999： 230?237

[2] SARWAR B， KARYPIS G， KONSTAN J， et al. Item?based collaborative filtering recommendation algorithms [C]// Procee?dings of the 10th International World Wide Web Conference. Hong Kong， China： ACM， 2001： 285?295.

[3] GOLDBERG D， NICHOLS D， OKI B M， et al. Using collabo?rative filtering to weave an information tapestry [J]. Communications of the ACM， 1992， 35（12）： 61?70.

[4] RESNICK P， LACOVOU N， SUCHAK M， et al. GroupLens： an open architecture for collaborative filtering of netnews [C]// Proceedings of 1994 ACM Conference on Computer Supported Cooperative Work. Chapel Hill： ACM， 1994： 175?186.

[5] KIM D， YUM B L. Collaborative filtering based on iterative principal component analysis [J]. International journal of expert systems with applications， 2005， 28（4）： 823?830.

[6] JAMALI M， ESTER M. A matrix factorization technique with trust propagation for recommendation in social networks [C]// Proceedings of the 4th ACM Conference on Recommender Systems. Barceloa， Spain： ACM， 2010： 135?142.

[7] 蔡強，韓東梅，李海生，等.基于標簽和協同過濾的個性化資源推薦[J].計算機科學，2014，41（1）：69?71.

CAI Q， HAN D M， LI H S， et al. Personalized resource re?commendation based on tags and collaborative filtering [J]. Computer science， 2014， 41（1）： 69?71.

[8] 劉勝宗，廖志芳，吳言鳳，等.一種融合用戶評分可信度和相似度的協同過濾算法[J].小型微型計算機系統，2014，35（5）：973?977.

LIU S Z， LIAO Z F， WU Y F， et al. A collaborative filtering algorithm combined with user rating credibility and similarity [J]. Journal of Chinese computer systems， 2014， 35（5）： 973?977.

[9] 俞琰，邱廣華. 融合社會網絡的協同過濾推薦算法研究[J].現代圖書情報技術，2012，28（6）：54?59.

YU Y， QIU G H. Research on collaborative filtering recommendation algorithm by fusing social network [J]. New technology of library and information service， 2012， 28（6）： 54?59.

[I0] SARWAR B M. Sparsity， scalability and distribution in recommender systems [D]. Minneapolis， USA： University of Minnesota， 2001.

[11] HERLOCKER L J， KONSTAN A J， RIEDL T J. Empirical analysis of design choices in neighborhood?based collaborative filtering algorithms [J]. Information retrieval， 2002， 5（4）： 287?310.