結(jié)合關(guān)聯(lián)規(guī)則填充的協(xié)同過濾改進(jìn)算法

包志強(qiáng) 宋靜霞

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

中圖分類號(hào)： TN911.1?34; TP301.6 ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ?文章編號(hào)： 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 ?引 ?言

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

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

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

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

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

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

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

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

3.3 ?實(shí)驗(yàn)結(jié)果及分析

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

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

由表3和圖2可以得出，本文實(shí)驗(yàn)ARDF?IBCF算法的RMSE和MAE值均小于IBCF算法，表示改進(jìn)的算法確實(shí)提高了推薦效率的準(zhǔn)確性。

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

4 ?結(jié) ?論

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

參考文獻(xiàn)

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