基于關(guān)聯(lián)規(guī)則的協(xié)同過濾改進算法

張小川，周澤紅，向 南，桑瑞婷

(1.重慶理工大學(xué) 計算機科學(xué)與工程學(xué)院， 重慶 400054；2.重慶理工大學(xué) 兩江國際學(xué)院， 重慶 401135)

從網(wǎng)易云音樂的歌單、亞馬遜的商品到抖音的短視頻，推薦系統(tǒng)已經(jīng)改變了用戶的瀏覽習(xí)慣。推薦系統(tǒng)由于具有幫用戶做出合適選擇的能力在網(wǎng)絡(luò)技術(shù)發(fā)展的時代下越來越有意義。

目前，推薦系統(tǒng)中主流的推薦算法有基于內(nèi)容的推薦、矩陣分解推薦、基于知識的推薦、協(xié)同過濾推薦、混合推薦等算法，其中協(xié)同過濾算法是基于用戶對商品的評分或其他行為(如購買)來為用戶提供個性化的推薦，不需要了解用戶或商品的大量信息，不必進行內(nèi)容分析，可較好地實現(xiàn)跨類別項目的推薦[1-2]。該算法根據(jù)目標用戶的近鄰用戶(具有相似興趣的用戶)對物品的用戶偏好預(yù)測(推測)目標用戶對物品的偏好從而進行推薦。因此，協(xié)同過濾算法被廣泛應(yīng)用于推薦系統(tǒng)中。協(xié)同過濾算法有CF based user (基于用戶的協(xié)同過濾)和CF based item(基于項目于的協(xié)同過濾) 兩種。由于本文所研究的算法場景是項目增長量大于用戶增長量的電影等場景，計算項目相似度比用戶相似度復(fù)雜，故本文選擇在基于用戶的協(xié)同過濾算法基礎(chǔ)上進行研究。

在日常生活中，朋友經(jīng)常一起購物，是因為朋友對商品有相似的喜好。協(xié)同過濾也是在這類場景下產(chǎn)生的一種算法。它可以根據(jù)目標用戶的朋友(近鄰)購買的商品，對目標用戶實現(xiàn)較為準確的推薦。協(xié)同過濾算法主要根據(jù)歷史評分數(shù)據(jù)進行推薦，而隨著用戶和項目的急速增長，用戶只能對有限的項目進行評分，項目也只能得到有限用戶的評分，評分數(shù)據(jù)變得越來越稀疏[3]，嚴重影響了推薦算法的準確性。在數(shù)據(jù)稀疏的情形下真正具有相似興趣的用戶也不能被有效提取出來。

針對上述問題，專家學(xué)者提出了一系列的解決辦法。李文海等[4]提出了用默認值填充缺失數(shù)據(jù)的矩陣填充技術(shù)。韓亞楠等[5]提出采用用戶平均評分填充評分矩陣缺失值。李遠博等[6]提出用PCA對評分矩陣降維，保留信息量最大的幾個特征，在保證不影響結(jié)果的提前下緩解數(shù)據(jù)稀疏性帶來的影響。鄧愛林等[7]通過基于項目的協(xié)同過濾算法對用戶未評分項目進行評分預(yù)測，將評分預(yù)測值填充到評分稀疏矩陣中。陳宗言等[8]通過引入項目的特征，計算項目間特征的相似度，預(yù)測用戶對未評分項目的評分，填充稀疏矩陣。Elahi M等[9]提出了主動學(xué)習(xí)，有選擇地選擇要呈現(xiàn)給用戶的項目以獲得其評分并最終提高推薦準確性。Najafabadi M K等[10]引入用戶與項目的隱式交互記錄，計算基于特征的項目相似度實現(xiàn)推薦。王潘潘等[11]提出了一種改進的加權(quán) Slope one 協(xié)同過濾推薦算法，計算相似度選擇最近鄰，用Slope one算法預(yù)測值填充用戶未評分項。Kim K等[12]通過社交網(wǎng)絡(luò)分析(SNA)和聚類技術(shù)來提高準確性。Tong C等[13]結(jié)合時間對用戶和項目的影響，提出了TimeTrustSVD，一種集成時間信息、信任關(guān)系和評價得分的協(xié)同過濾模型。肖文強等[14]引入用戶共同評分權(quán)重、物品時間差因素以及流行物品權(quán)重，將興趣相似的用戶聚成一類，在類內(nèi)應(yīng)用推薦算法分別為用戶進行推薦。孟桓羽等[15]通過建立基于圖的評分數(shù)據(jù)模型，將傳統(tǒng)的協(xié)同過濾算法與圖計算及改進的KNN算法相結(jié)合來提高推薦準確度。張海霞等[16]引入加權(quán)異構(gòu)信息來緩解數(shù)據(jù)稀疏性造成的推薦不準確問題。

上述學(xué)者提出的方法都可以在一定程度上緩解數(shù)據(jù)稀疏性問題，但都沒有考慮到項目間存在的相關(guān)性，或者僅考慮到兩個項目之間的關(guān)聯(lián)關(guān)系[17]。為了緩解稀疏性問題，本文提出了基于關(guān)聯(lián)規(guī)則的協(xié)同過濾改進算法。即設(shè)置相似度閾值，選定目標用戶的k個近鄰用戶，若選擇的k個近鄰與目標用戶的相似度不小于閾值，則按協(xié)同過濾算法推薦，否則應(yīng)用關(guān)聯(lián)規(guī)則技術(shù)進行推薦。協(xié)同過濾算法按照傳統(tǒng)的基于用戶的協(xié)同過濾算法進行推薦，而用關(guān)聯(lián)規(guī)則技術(shù)進行推薦則先應(yīng)用Apriori算法，挖掘出強關(guān)聯(lián)規(guī)則，從而發(fā)現(xiàn)項目間的關(guān)聯(lián)關(guān)系，以支持度和置信度的乘積作為推薦度進行推薦。

1 基于用戶的協(xié)同過濾

基于用戶的協(xié)同過濾算法的推薦思想是：如果某些用戶評分高的項目重合度高，那么這些用戶是興趣度相似的用戶，對其他項目的評分也相似。該算法首先建立用戶項目評分矩陣，然后根據(jù)目標用戶與其他用戶的共同評分項計算出目標用戶與其他用戶之間的相似度，用相似度選取目標用戶的近鄰，目標用戶對未評分項目的評分依據(jù)近鄰用戶對該項目的評分進行預(yù)測，最后選取評分高的項目進行推薦。

1.1 相似度計算

評估相似度的方法有多種，如余弦相似度及調(diào)整的余弦相似度、皮爾遜相關(guān)系數(shù)(Pearson相關(guān)系數(shù))、Jaccard相似系數(shù)、Tanimoto系數(shù)(廣義Jaccard相似系數(shù))、對數(shù)似然相似度等。其中常用的3種相似度度量方法是：余弦相似度，修正的余弦相似度，Pearson相關(guān)系數(shù)。

要對目標用戶進行推薦首先要建立用戶評分矩陣，假設(shè)數(shù)據(jù)中有m個用戶n個項目，數(shù)據(jù)轉(zhuǎn)化的m行n列的評分矩陣見式(1)。其中：i行j列的元素Rij代表的是用戶i對項目j的評分；?代表的未評分或缺失值。

(1)

用戶i和j相似度的計算方法是：首先得到用戶i和用戶j共同評分的所有項目，然后通過相似度計算方法計算用戶i和j的相似度，記為sim(i,j)。

余弦相似度：用兩個向量的余弦值作為衡量相似度的標準，兩個向量夾角越小，相似度越強。設(shè)Iij是用戶i和j共同評分的項目集合，Ric是用戶i對項目c的評分，Rjc是用戶j對項目c的評分，則

(2)

(3)

(4)

考慮到用戶之間評分尺度不同這個重要因素，選擇修正余弦相似度和Pearson相似度。經(jīng)實驗證明：Pearson相似度效果最好，本文選擇Pearson相似度計算方法。

1.2 鄰居集的選擇

根據(jù)上述選出的相似度計算方法計算目標用戶與其他用戶的相似度，將相似度降序排序，選擇前k個作為該目標用戶的鄰居集。

1.3 預(yù)測評分

選擇好目標用戶i的最近鄰居集合為NBSi，根據(jù)鄰居集中鄰居對目標用戶未評分項目的評分預(yù)測目標用戶的評分。目標用戶i對未評分項目c的預(yù)測評分計算公式為

(5)

1.4 傳統(tǒng)基于協(xié)同過濾算法不足分析

由于互聯(lián)網(wǎng)推動的電子商務(wù)的發(fā)展，用戶數(shù)目和項目數(shù)目呈指數(shù)級增長，而一個用戶對項目的購買能力有限，只會購買龐大項目中的少數(shù)項目而且用戶不一定對購買過的項目都進行評分，因而造成用戶評分數(shù)據(jù)極度稀疏，某一個用戶的評分項目不及總項目的1%。相似度計算依靠的是用戶間的共同評分，數(shù)據(jù)稀疏情況下，相似度計算方法不能準確計算用戶間的相似度，從而無法選擇和目標用戶興趣品味相似的鄰居集，導(dǎo)致目標用戶對未評分項目評分預(yù)測不準確，影響推薦質(zhì)量。

為了降低數(shù)據(jù)稀疏性造成的推薦效果不佳的影響，本文在計算相似度時先統(tǒng)計用戶與鄰居的共同評分項目數(shù)，設(shè)置計算相似度的最小共同項目數(shù)，當(dāng)共同評分的項目數(shù)小于設(shè)置值時則將相似度設(shè)置為0。然后設(shè)置相似度閾值，若選擇的鄰居集中的用戶與目標用戶的相似度都不小于閾值，則按協(xié)同過濾算法推薦，否則應(yīng)用關(guān)聯(lián)規(guī)則技術(shù)進行推薦。

2 基于關(guān)聯(lián)規(guī)則的協(xié)同過濾改進算法

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘技術(shù)中挖掘項目相關(guān)性的一類規(guī)則，最早由Agrawal等于1993年提出[18]，能夠揭示項集之間的關(guān)聯(lián)。關(guān)聯(lián)規(guī)則技術(shù)最初應(yīng)用在零售業(yè)中，把具有相關(guān)性的商品進行打包銷售。基于關(guān)聯(lián)規(guī)則的推薦算法利用關(guān)聯(lián)規(guī)則挖掘出項目間的相關(guān)性，將用戶未購買但與已購買項目相關(guān)性大的項目推薦給用戶。其中Apriori算法[19]是最經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法。

2.1 關(guān)聯(lián)規(guī)則概述

關(guān)聯(lián)規(guī)則挖掘已經(jīng)被廣泛采用來提升推薦質(zhì)量，挖掘用戶的興趣度模式。關(guān)聯(lián)規(guī)則形如X={x1,x2,…,xm}?Y={y1,y2,…,yn}，意味著用戶購買了X則很大程度上可能會購買Y。其中，X和Y分別稱為關(guān)聯(lián)規(guī)則的前項和后項。常用的關(guān)聯(lián)規(guī)則挖掘算法有Apriori算法和FP-Growth算法兩種。本文選擇最為經(jīng)典的Apriori算法。以下是關(guān)聯(lián)規(guī)則相關(guān)概念。

定義1 項集： 項集是項的集合。一條購買記錄中每一個item為一個項，包含k個項的項集稱為k項集。

定義2 支持度(support)：假設(shè)規(guī)則X?Y，支持度表示X作為前項Y作為后項在所有事務(wù)中同時出現(xiàn)的概率。最小支持度是X、Y同時出現(xiàn)的最小概率，是評估支持度的一個閾值。

(6)

定義3 置信度(confidence)：假設(shè)規(guī)則X?Y，置信度表示在購買X的情況下購買Y的概率。最小置信度是評估置信度可靠性的一個閾值，表示關(guān)聯(lián)規(guī)則的最低可靠性。

(7)

定義4 頻繁項：經(jīng)常出現(xiàn)在一塊的物品的集合。也就是關(guān)聯(lián)規(guī)則的支持度不低于最小支持度的前后項組成的項集稱為頻繁項，否則為非頻繁項。

定義5 強關(guān)聯(lián)規(guī)則：支持度不小于最小支持度且置信度不小于最小置信度的規(guī)則。

Apriori算法主要包含兩個步驟：首先找出事務(wù)數(shù)據(jù)庫中所有不小于用戶指定的最小支持度的數(shù)據(jù)項集(頻繁項集)；然后利用頻繁項集結(jié)合最小置信度生成強關(guān)聯(lián)規(guī)則。此算法基于性質(zhì)：若一個項集是非頻繁項集，則它的所有超集也是非頻繁項集。該算法有兩個關(guān)鍵步驟分別為連接步和剪枝步。

關(guān)聯(lián)規(guī)則挖掘所需的數(shù)據(jù)為事務(wù)型數(shù)據(jù)，一條事務(wù)型記錄代表一次交易(購買)，所以需將數(shù)據(jù)轉(zhuǎn)化為事務(wù)型數(shù)據(jù)。

采用Apriori算法進行數(shù)據(jù)挖掘，其輸入為：處理成事務(wù)型的數(shù)據(jù)集，最小支持度minSupport,最小置信度minConfidence；其輸出為：強關(guān)聯(lián)規(guī)則。具體步驟如下：

1) 掃描全部數(shù)據(jù)集，產(chǎn)生候選1-項集C1；

2) 根據(jù)最小支持度，由候選1-項集C1產(chǎn)生頻繁1-項集L1；

3) 對k>1，重復(fù)執(zhí)行步驟4)、5)、6)；

4)由Lk執(zhí)行連接和剪枝操作，產(chǎn)生候選(k+1)-項集C(k+1)；

5) 根據(jù)最小支持度，由候選(k+1)-項集C(k+1)，產(chǎn)生頻繁(k+1)-項集L(k+1)；

6) 若L不空，則k=k+1，轉(zhuǎn)步驟4)；否則，轉(zhuǎn)步驟7)；

7) 根據(jù)最小置信度，由頻繁項集過濾掉低于最小置信度的規(guī)則產(chǎn)生強關(guān)聯(lián)規(guī)則。

2.2 基于關(guān)聯(lián)規(guī)則的評分預(yù)測

協(xié)同過濾算法中計算相似度的方法是Pearson相關(guān)系數(shù)度量方法，依據(jù)的是用戶對項目的顯式評分，而在數(shù)據(jù)稀疏性的情況下，評分數(shù)很少會導(dǎo)致相似度計算不準確影響推薦精度。因此，對于由于共同評分數(shù)目稀少而不能用傳統(tǒng)協(xié)同過濾算法準確推薦的則用關(guān)聯(lián)規(guī)則進行推薦，緩解數(shù)據(jù)稀疏造成的負面影響。

由上述Apriori算法得出的強關(guān)聯(lián)規(guī)則組成集合Rrules，本文對Rrules里的關(guān)聯(lián)規(guī)則進行拆分，拆分為關(guān)聯(lián)規(guī)則后表示為只有一個項目的形式，即將關(guān)聯(lián)規(guī)則拆分成多對一或一對一的形式，拆分形式如下：

(8)

令S為規(guī)則的支持度，C為規(guī)則的置信度，recom為規(guī)則的推薦度，可得：

recom(X?Y)=S(X?Y)·C(X?Y)

(9)

本文結(jié)合項目間的關(guān)聯(lián)關(guān)系，利用數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則技術(shù)緩解數(shù)據(jù)稀疏性對推薦質(zhì)量的影響。基于關(guān)聯(lián)規(guī)則計算用戶對項目預(yù)測評分的公式為

(10)

MAI的形成：首先，找出后項為目標項目的關(guān)聯(lián)規(guī)則；其次，將找到的關(guān)聯(lián)規(guī)則按推薦度值降序進行排列；最后，設(shè)置推薦度閾值，提取不小于推薦度閾值的關(guān)聯(lián)規(guī)則，這些關(guān)聯(lián)規(guī)則的前項組成MAI。

2.3 基于關(guān)聯(lián)規(guī)則的改進推薦算法

設(shè)置用戶間的相似度閾值為α，利用Pearson相關(guān)性度量方法計算目標用戶i和其他用戶間的相似度，然后對相似度進行降序排序，選擇前k個用戶作為目標用戶的最近鄰，m為第k個用戶，則用戶i對項目c的預(yù)測評分值計算公式如下：

(11)

3 實驗分析

首先介紹實驗環(huán)境和所選用的數(shù)據(jù)集，然后介紹實驗內(nèi)容，最后根據(jù)選用的數(shù)據(jù)集將本文算法與傳統(tǒng)算法相比較得出實驗結(jié)果。

3.1 實驗環(huán)境和實驗數(shù)據(jù)集

實驗環(huán)境如下：筆記本，CPU為 @1.60 GHz 1.80 GHz，內(nèi)存8 GB，編程環(huán)境Anaconda-Spyder(python 3.6)。

實驗數(shù)據(jù)集：美國明尼蘇達大學(xué)GroupLens小組給出的100k的movieLens 數(shù)據(jù)集。采用該數(shù)據(jù)集中的u.data，包含完整的用戶數(shù)據(jù)集，有943個用戶對1 682個項目的100 000個評分。每位用戶至少有20個評分數(shù)據(jù)。用戶和項目從1開始連續(xù)編號，數(shù)據(jù)是隨機排列的。這個列表是以用戶id|項目id|時間戳分割的一個列表。評分集合為{1，2，3，4，5}，評分越大證明用戶對所評電影越滿意。實驗中將數(shù)據(jù)隨機分成10份，一份作為測試集，其余作為訓(xùn)練集。

3.2 評價指標

評估推薦系統(tǒng)性能的指標有很多，如平均絕對誤差、均方根誤差、召回率、準確率、覆蓋率、多樣性、流行度、F1指標和AUC等。本文采用平均絕對誤差MAE(mean absolute error)和均方根誤差RMSE(root mean squared error)來評估推薦系統(tǒng)的性能。MAE、RMSE主要計算預(yù)測評分值與用戶真正評分值之間的誤差程度，MAE、RMSE值越小，推薦系統(tǒng)的推薦性能就越好。

(12)

(13)

其中：u為用戶；i為項目；T為測試集；rui為用戶u對用戶i的真實評分；為用戶u對用戶i的預(yù)測評分。

3.3 實驗內(nèi)容與實驗結(jié)果

本文將實驗分為兩部分,首先是對影響關(guān)聯(lián)規(guī)則質(zhì)量的指標最小支度、最小置信度進行比較，選擇最佳值作為接下來實驗的基礎(chǔ)；然后將本文提出的算法與傳統(tǒng)算法相比較，證明本文算法的有效性。

3.3.1選擇關(guān)聯(lián)規(guī)則最優(yōu)支持度、置信度的實驗

在進行關(guān)聯(lián)規(guī)則實驗前，要對數(shù)據(jù)進行處理。由于關(guān)聯(lián)規(guī)則挖掘輸入的是事務(wù)型數(shù)據(jù)，因此要將數(shù)據(jù)集的數(shù)據(jù)處理成事務(wù)型數(shù)據(jù)，再進行實驗。將評分不小于3的視為購買，加入事務(wù)項，否則視為不購買。

在關(guān)聯(lián)規(guī)則挖掘算法中，最小支持度和最小置信度是影響關(guān)聯(lián)規(guī)則的兩個主要因素。為了獲取關(guān)聯(lián)規(guī)則的最優(yōu)最小支持度、置信度，設(shè)計如下實驗：通過設(shè)置一系列關(guān)聯(lián)規(guī)則推薦算法的最小支持度和最小置信度，觀察關(guān)聯(lián)規(guī)則數(shù)目隨最小支持度和最小置信度的變化規(guī)律。實驗結(jié)果如圖1所示。考慮到數(shù)據(jù)量較大，設(shè)置的支持度范圍為15%～40%。實驗首先將最小支持度設(shè)為15%，觀察最小置信度在20%～70%的MAE和RMSE的變化，找出最佳最小置信度。然后，設(shè)置最小置信度為找出的最佳最小置信度，觀察最小支持度在15%～40%的MAE和RMSE的變化，找出最佳最小支持度。實驗結(jié)果如圖2、3所示。

圖1 最小支持度在不同置信度下與規(guī)則數(shù)目的關(guān)系

由圖1可以看出：在最小置信度一定的情況下，關(guān)聯(lián)規(guī)則推薦算法的規(guī)則數(shù)隨著最小支持度的增加不斷下降直至規(guī)則數(shù)為0，而在最小支持度一定的情況下，置信度越大，規(guī)則數(shù)目越少。由此可知，最小支持度、置信度太小，規(guī)則數(shù)太多，關(guān)聯(lián)規(guī)則質(zhì)量比較低；最小支持度、置信度太大，則會把有效規(guī)則過濾掉。因而，在合適的最小支持度、置信度時關(guān)聯(lián)規(guī)則質(zhì)量較高。

圖3 最小置信度為0.5，最小支持度與MAE、RMSE的關(guān)系

由圖2可知：在最小支持度設(shè)置為0.15，最小置信度在0.5時MAE、RSME最小，算法獲得最優(yōu)推薦質(zhì)量，最佳最小置信度為0.5。由圖3可知：在最佳最小置信度下，最小支持度為0.2時，MAE、RSME最小，算法獲得最優(yōu)推薦質(zhì)量。因此，當(dāng)最小支持度為0.2，最小置信度為0.5時，關(guān)聯(lián)規(guī)則推薦算法取得最優(yōu)推薦質(zhì)量。

3.3.2 本文算法有效性實驗

為了驗證本文提出的基于關(guān)聯(lián)規(guī)則的協(xié)同過濾改進算法的有效性，在上述最佳最小支持度、置信度條件下，將基于關(guān)聯(lián)規(guī)則的協(xié)同過濾算法(ARCF)與傳統(tǒng)基于用戶的協(xié)同過濾算法(UCF)、基于用戶平均值填充的協(xié)同過濾算法(UACF)進行對比實驗。在測試數(shù)據(jù)集上，這些算法在不同最近鄰上的性能表現(xiàn)見圖4、5。

由圖4、5可以發(fā)現(xiàn)：本文提出的算法的MAE、RMSE平均都比傳統(tǒng)協(xié)同過濾算法小，即本文算法推薦的準確度更高。可以得出，關(guān)聯(lián)規(guī)則技術(shù)的引入可以提高推薦準確性，一定程度緩解數(shù)據(jù)稀疏性問題。當(dāng)近鄰數(shù)目為90時，基于關(guān)聯(lián)規(guī)則的協(xié)同過濾推薦算法推薦質(zhì)量最優(yōu)。

圖4 三種算法在不同鄰居數(shù)目下MAE的比較

圖5 三種算法在不同鄰居數(shù)目下RMSE的比較

4 結(jié)束語

協(xié)同過濾算法由于其簡單、可實現(xiàn)跨項目推薦等優(yōu)點成為目前在推薦系統(tǒng)中應(yīng)用最廣泛、最成功的推薦算法，但是該算法的實現(xiàn)依賴用戶項目的顯式評分數(shù)據(jù)。當(dāng)今互聯(lián)網(wǎng)行業(yè)蓬勃發(fā)展，各種線上網(wǎng)站發(fā)展迅速，用戶量和數(shù)據(jù)量急速上升，由于用戶購買能力有限造成的評分數(shù)據(jù)稀疏性越來越嚴重，因而協(xié)同過濾算法推薦效果不佳。針對數(shù)據(jù)稀疏性問題，本文考慮到項目間存在的關(guān)聯(lián)關(guān)系，提出了基于關(guān)聯(lián)規(guī)則的協(xié)同過濾改進算法。設(shè)置相似度閾值，若選擇的鄰居集中的近鄰用戶與目標用戶的相似度都不小于閾值，按協(xié)同過濾算法推薦，否則應(yīng)用關(guān)聯(lián)規(guī)則技術(shù)進行推薦。經(jīng)過實驗證明：基于關(guān)聯(lián)規(guī)則的協(xié)同過濾改進算法在一定程度上緩解了數(shù)據(jù)稀疏性，提高了推薦精度。在基于關(guān)聯(lián)規(guī)則的推薦算法中,如果數(shù)據(jù)中具有關(guān)聯(lián)關(guān)系的項目較少，提取出來的強關(guān)聯(lián)規(guī)則就較少，關(guān)聯(lián)規(guī)則起不到應(yīng)有的推薦作用。解決此問題是下一步的研究工作。