包志強 宋靜霞

關(guān)鍵詞： 關(guān)聯(lián)規(guī)則; 數(shù)據(jù)填充; 協(xié)同過濾; 推薦算法; 評分矩陣; 數(shù)據(jù)稀疏; 對比實驗

中圖分類號： 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 ?引 ?言

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

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

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

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

1 ?傳統(tǒng)基于項目的協(xié)同過濾算法

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

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

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

3.3 ?實驗結(jié)果及分析

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

由表2和圖1可以得到，在本文數(shù)據(jù)集下，傳統(tǒng)算法中IBCF算法優(yōu)于UBCF算法，所以本文實驗選擇關(guān)聯(lián)規(guī)則與IBCF相結(jié)合。

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

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

4 ?結(jié) ?論

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

參考文獻

[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] 蔡強，韓東梅，李海生，等.基于標簽和協(xié)同過濾的個性化資源推薦[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] 劉勝宗，廖志芳，吳言鳳，等.一種融合用戶評分可信度和相似度的協(xié)同過濾算法[J].小型微型計算機系統(tǒng)，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] 俞琰，邱廣華. 融合社會網(wǎng)絡(luò)的協(xié)同過濾推薦算法研究[J].現(xiàn)代圖書情報技術(shù)，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.