基于關聯規則的協同過濾改進算法

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

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

從網易云音樂的歌單、亞馬遜的商品到抖音的短視頻，推薦系統已經改變了用戶的瀏覽習慣。推薦系統由于具有幫用戶做出合適選擇的能力在網絡技術發展的時代下越來越有意義。

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

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

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

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

1 基于用戶的協同過濾

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

1.1 相似度計算

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

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

(1)

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

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

(2)

(3)

(4)

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

1.2 鄰居集的選擇

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

1.3 預測評分

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

(5)

1.4 傳統基于協同過濾算法不足分析

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

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

2 基于關聯規則的協同過濾改進算法

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

2.1 關聯規則概述

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

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

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

(6)

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

(7)

定義4 頻繁項：經常出現在一塊的物品的集合。也就是關聯規則的支持度不低于最小支持度的前后項組成的項集稱為頻繁項，否則為非頻繁項。

定義5 強關聯規則：支持度不小于最小支持度且置信度不小于最小置信度的規則。

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

關聯規則挖掘所需的數據為事務型數據，一條事務型記錄代表一次交易(購買)，所以需將數據轉化為事務型數據。

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

1) 掃描全部數據集，產生候選1-項集C1；

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

3) 對k>1，重復執行步驟4)、5)、6)；

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

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

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

7) 根據最小置信度，由頻繁項集過濾掉低于最小置信度的規則產生強關聯規則。

2.2 基于關聯規則的評分預測

協同過濾算法中計算相似度的方法是Pearson相關系數度量方法，依據的是用戶對項目的顯式評分，而在數據稀疏性的情況下，評分數很少會導致相似度計算不準確影響推薦精度。因此，對于由于共同評分數目稀少而不能用傳統協同過濾算法準確推薦的則用關聯規則進行推薦，緩解數據稀疏造成的負面影響。

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

(8)

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

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

(9)

本文結合項目間的關聯關系，利用數據挖掘中的關聯規則技術緩解數據稀疏性對推薦質量的影響。基于關聯規則計算用戶對項目預測評分的公式為

(10)

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

2.3 基于關聯規則的改進推薦算法

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

(11)

3 實驗分析

首先介紹實驗環境和所選用的數據集，然后介紹實驗內容，最后根據選用的數據集將本文算法與傳統算法相比較得出實驗結果。

3.1 實驗環境和實驗數據集

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

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

3.2 評價指標

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

(12)

(13)

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

3.3 實驗內容與實驗結果

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

3.3.1選擇關聯規則最優支持度、置信度的實驗

在進行關聯規則實驗前，要對數據進行處理。由于關聯規則挖掘輸入的是事務型數據，因此要將數據集的數據處理成事務型數據，再進行實驗。將評分不小于3的視為購買，加入事務項，否則視為不購買。

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

圖1 最小支持度在不同置信度下與規則數目的關系

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

圖3 最小置信度為0.5，最小支持度與MAE、RMSE的關系

由圖2可知：在最小支持度設置為0.15，最小置信度在0.5時MAE、RSME最小，算法獲得最優推薦質量，最佳最小置信度為0.5。由圖3可知：在最佳最小置信度下，最小支持度為0.2時，MAE、RSME最小，算法獲得最優推薦質量。因此，當最小支持度為0.2，最小置信度為0.5時，關聯規則推薦算法取得最優推薦質量。

3.3.2 本文算法有效性實驗

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

由圖4、5可以發現：本文提出的算法的MAE、RMSE平均都比傳統協同過濾算法小，即本文算法推薦的準確度更高。可以得出，關聯規則技術的引入可以提高推薦準確性，一定程度緩解數據稀疏性問題。當近鄰數目為90時，基于關聯規則的協同過濾推薦算法推薦質量最優。

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

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

4 結束語

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