一種基于頻繁項(xiàng)集挖掘的推薦算法

帖軍，呂琴艷，孫翀，王江晴，尹帆

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

隨著互聯(lián)網(wǎng)和信息技術(shù)的迅猛發(fā)展，網(wǎng)絡(luò)上的信息數(shù)據(jù)量呈指數(shù)增長(zhǎng)，人們逐漸陷入 “信息過(guò)載”時(shí)代.在這個(gè)時(shí)代，消費(fèi)者很難從眾多商品中找到自己感興趣的商品，同時(shí)生產(chǎn)者也很難讓自己的商品在眾多用戶的關(guān)注中脫穎而出.推薦系統(tǒng)[1-3]則成為解決該問(wèn)題的重要手段.它可以根據(jù)用戶的喜好篩去不相關(guān)的項(xiàng)目，并推薦用戶可能喜歡的項(xiàng)目.

在推薦系統(tǒng)中，關(guān)聯(lián)規(guī)則挖掘[4]和協(xié)同過(guò)濾[5,6]是最常用和最重要的兩種技術(shù).挖掘關(guān)聯(lián)規(guī)則的目的是在大型事務(wù)數(shù)據(jù)庫(kù)中搜索項(xiàng)目集合之間的內(nèi)在聯(lián)系.協(xié)同過(guò)濾可以分為基于用戶的推薦(User-based Recommendation)、基于物品的推薦(Item-based Recommendation)、基于模型的推薦(Model-based Recommendation)等子類.基于用戶的協(xié)同過(guò)濾算法，其基本思想是先找到和目標(biāo)用戶有相似興趣的用戶，然后把這些用戶感興趣而目標(biāo)用戶沒(méi)有接觸過(guò)的物品推薦給目標(biāo)用戶；基于項(xiàng)目的協(xié)同過(guò)濾推薦算法，是給用戶推薦那些與他們之前喜歡的物品相似的物品，主要通過(guò)分析用戶的行為記錄計(jì)算物品之間的相似度；基于模型的協(xié)同過(guò)濾推薦則是先使用歷史數(shù)據(jù)訓(xùn)練得到一個(gè)模型，再用此模型進(jìn)行預(yù)測(cè).

雖然協(xié)同過(guò)濾算法取得了巨大的成功，但始終存在數(shù)據(jù)稀疏性問(wèn)題.電子商務(wù)網(wǎng)站中用戶和項(xiàng)目的數(shù)目非常龐大，而多數(shù)用戶只會(huì)對(duì)少量的項(xiàng)目進(jìn)行評(píng)分，導(dǎo)致用戶之間評(píng)分的重疊部分很小，難以計(jì)算兩個(gè)用戶之間的相似程度.而相似性計(jì)算是基于協(xié)同過(guò)濾的推薦系統(tǒng)中一個(gè)非常重要的步驟.因此數(shù)據(jù)稀疏性大大降低了協(xié)同過(guò)濾的預(yù)測(cè)準(zhǔn)確性.

基于上述分析，本文將頻繁項(xiàng)集挖掘與協(xié)同過(guò)濾相結(jié)合，提出一種新的相似性度量方法，提高相似度計(jì)算的準(zhǔn)確率，從而提升協(xié)同過(guò)濾算法的推薦質(zhì)量.

1 相關(guān)工作

數(shù)據(jù)稀疏性[7,8]和冷啟動(dòng)一直是影響推薦系統(tǒng)的推薦性能的重要因素，針對(duì)這些問(wèn)題，一些研究人員提出將數(shù)據(jù)挖掘算法與協(xié)同過(guò)濾相結(jié)合，對(duì)用戶-項(xiàng)目評(píng)分矩陣的缺失值進(jìn)行預(yù)測(cè)并填充.缺失值填補(bǔ)法是根據(jù)已有的用戶評(píng)分?jǐn)?shù)據(jù)，以某種計(jì)算方法對(duì)用戶未評(píng)分的數(shù)據(jù)進(jìn)行估計(jì)并填充，可以顯式地解決數(shù)據(jù)稀疏問(wèn)題.

Shambour等人[9]提出將來(lái)自用戶社交信任網(wǎng)絡(luò)的附加信息和項(xiàng)目的語(yǔ)義領(lǐng)域知識(shí)結(jié)合起來(lái)，以提高推薦的準(zhǔn)確性和覆蓋范圍.Fan[10]等人提出一種基于預(yù)測(cè)值填充的UBCF推薦算法，該算法在計(jì)算用戶相似度之前，通過(guò)整合基于內(nèi)容的推薦算法和用戶活動(dòng)水平來(lái)預(yù)測(cè)用戶項(xiàng)目矩陣中的缺失值，一定程度緩解了數(shù)據(jù)稀疏性對(duì)推薦精度的影響.Zhou等人[11]提出了一種基于SVD(奇異值分解，Singular Value Decomposition)推薦系統(tǒng)的增量式方法，每次迭代計(jì)算原始矩陣的奇異值分解，以解決稀疏性問(wèn)題和用戶興趣的動(dòng)態(tài)性.張玉芳等人[12]提出一種結(jié)合條件概率和傳統(tǒng)協(xié)同過(guò)濾算法的非固定K近鄰算法.該算法在分步填充評(píng)分矩陣思想的基礎(chǔ)上，第一步只接受相似度和共同評(píng)分項(xiàng)目數(shù)量達(dá)到閾值的鄰居用戶作為目標(biāo)用戶鄰居，然后計(jì)算并填充未評(píng)分項(xiàng)目；第二步使用第一步填充后的矩陣計(jì)算剩余未評(píng)分項(xiàng)目的評(píng)分.Chujai等人[13]同時(shí)使用用戶信息和電影信息挖掘頻繁項(xiàng)集，填補(bǔ)缺失數(shù)據(jù).Insuwan等人[14]提出 SVDUPMedianCF 算法，該算法利用改進(jìn)的K-means 算法進(jìn)行聚類，得到聚類的中心來(lái)填補(bǔ)缺失值.劉枚蓮等人[15]提出基于雙向關(guān)聯(lián)規(guī)則項(xiàng)目評(píng)分預(yù)測(cè)的推薦算法，利用雙向關(guān)聯(lián)規(guī)則挖掘事務(wù)數(shù)據(jù)庫(kù)中相互關(guān)聯(lián)的項(xiàng)目，找到目標(biāo)項(xiàng)目的關(guān)聯(lián)集，利用已評(píng)分項(xiàng)目初步預(yù)測(cè)用戶對(duì)目標(biāo)項(xiàng)目的偏好程度，從而進(jìn)行推薦.

缺失值填補(bǔ)法可以直觀、顯著地改善數(shù)據(jù)稀疏問(wèn)題，但其本身是對(duì)評(píng)分缺失值的一種預(yù)測(cè)，并不能真正代表用戶偏好，而預(yù)測(cè)的評(píng)分對(duì)推薦結(jié)果有較大的影響，可能導(dǎo)致最終的推薦結(jié)果不準(zhǔn)確.當(dāng)數(shù)據(jù)十分稀疏時(shí)，使用傳統(tǒng)的相似度計(jì)算方法往往不能得到很好的推薦效果.因此，本文提出一種結(jié)合頻繁項(xiàng)集與協(xié)同過(guò)濾的相似度改進(jìn)算法，算法考慮項(xiàng)目之間相互關(guān)聯(lián)的特性，對(duì)項(xiàng)目進(jìn)行頻繁項(xiàng)集挖掘，設(shè)計(jì)一種新的相似性計(jì)算方法，對(duì)傳統(tǒng)相似性計(jì)算方法進(jìn)行改進(jìn)，從而尋找項(xiàng)目的最近鄰居并進(jìn)行推薦.

2 算法設(shè)計(jì)

2.1 問(wèn)題描述

協(xié)同過(guò)濾的相似度[16,17]計(jì)算只考慮用戶對(duì)項(xiàng)目的評(píng)分?jǐn)?shù)據(jù)(評(píng)分?jǐn)?shù)據(jù)具有很大的稀疏性)，忽略了項(xiàng)目在空間上存在的相互關(guān)聯(lián)性.而且，如果有惡意的評(píng)分，通過(guò)某種手段對(duì)某一特定的項(xiàng)目評(píng)分，并且評(píng)分很高，這無(wú)疑會(huì)帶來(lái)噪聲樣本.這些問(wèn)題都會(huì)導(dǎo)致推薦誤差大，推薦結(jié)果不準(zhǔn)確.如果引入事務(wù)數(shù)據(jù)庫(kù)和頻繁項(xiàng)，則可以認(rèn)為頻繁項(xiàng)是比較正常和可靠的事務(wù)數(shù)據(jù)，也可以認(rèn)為頻繁被用戶購(gòu)買的商品理論上具有較高的相似性.本文利用Apriori算法挖掘事務(wù)數(shù)據(jù)庫(kù)中的頻繁項(xiàng)集，根據(jù)頻繁項(xiàng)集設(shè)計(jì)新的相似性度量函數(shù)，再與用戶對(duì)項(xiàng)目的評(píng)分相似性進(jìn)行加權(quán)綜合，從而尋找項(xiàng)目的最近鄰居并進(jìn)行推薦.

協(xié)同過(guò)濾推薦算法是以用戶-項(xiàng)目評(píng)分?jǐn)?shù)據(jù)作為基礎(chǔ)進(jìn)行推薦的，假設(shè)U={u1,u2,…，um}和I={i1,i2,…，in}分別是用戶和項(xiàng)目的集合，用戶對(duì)項(xiàng)目的評(píng)分矩陣為X∈Rm×n，即矩陣X有m行n列，第i行第j列的元素Xi,j表示第i個(gè)用戶對(duì)第j個(gè)項(xiàng)目的評(píng)分.

通過(guò)用戶-項(xiàng)目評(píng)分?jǐn)?shù)據(jù)X可以形成事務(wù)數(shù)據(jù)庫(kù)矩陣D∈Rm×n，D中的每一項(xiàng)Di,j(i=1,2,…，m;j=1,2,…，n)表示第i個(gè)用戶是否對(duì)第j個(gè)項(xiàng)目進(jìn)行評(píng)分.具體計(jì)算方式如公式(1)：

(1)

2.2 BFIM算法

本文的BFIM算法針對(duì)基于項(xiàng)目的協(xié)同過(guò)濾算法，在計(jì)算項(xiàng)目相似度時(shí)完全依賴用戶評(píng)分?jǐn)?shù)據(jù)，忽略了項(xiàng)目在空間上的相互關(guān)聯(lián)性問(wèn)題，重新定義了項(xiàng)目相似度計(jì)算方法.算法提出對(duì)項(xiàng)目進(jìn)行頻繁項(xiàng)集挖掘，根據(jù)頻繁項(xiàng)集設(shè)計(jì)一種相似性度量方法，融入到傳統(tǒng)相似度計(jì)算方法中，然后利用該相似度更好地預(yù)測(cè)用戶對(duì)項(xiàng)目的評(píng)分.

2.2.1 頻繁項(xiàng)集矩陣的構(gòu)建

本文采用Apriori算法進(jìn)行頻繁項(xiàng)集挖掘，根據(jù)最小支持度minSup得出全部的頻繁項(xiàng)集.現(xiàn)假設(shè)對(duì)事務(wù)數(shù)據(jù)庫(kù)挖掘出的頻繁項(xiàng)集總條數(shù)為k，構(gòu)建頻繁項(xiàng)集矩陣F∈Rk×n，具體計(jì)算方法如下：

(2)

矩陣F的可能取值如表1所示.

表1 頻繁項(xiàng)集矩陣示例Tab.1 An example of frequent itemsets matrix

由表1可知，F(xiàn)矩陣中{I1,I2,…，In}表示n個(gè)項(xiàng)目，{1,2,…,k}表示第k個(gè)頻繁項(xiàng)集，F(xiàn)2,2=1表示第2條頻繁項(xiàng)集包含項(xiàng)目I2，F(xiàn)2,1=0表示第2條頻繁項(xiàng)集不包含項(xiàng)目I1.

2.2.2 相似度計(jì)算

(3)

(4)

(5)

其中?表示權(quán)重，為可調(diào)的參數(shù).該綜合相似度計(jì)算方法不僅考慮用戶項(xiàng)目評(píng)分矩陣，同時(shí)還考慮了項(xiàng)目間的內(nèi)在聯(lián)系，二者以一定權(quán)重結(jié)合在一起，可以更準(zhǔn)確地尋找項(xiàng)目的最近鄰居.

2.2.3 尋找最近鄰居

假設(shè)目標(biāo)項(xiàng)目為Ia，根據(jù)相似性矩陣S篩選出所有項(xiàng)目與Ia的相似性值，并對(duì)其進(jìn)行降序排列，選擇相似性最高的K個(gè)項(xiàng)目作為目標(biāo)項(xiàng)目Ia的最近鄰居集合，設(shè)為Na={N1,N2,…,NK}，用戶u對(duì)項(xiàng)目Ia的預(yù)測(cè)評(píng)分是Pu,Ia，計(jì)算方法如下：

(6)

BFIM算法以偽代碼形式描述如下：

BFIM算法輸入評(píng)分矩陣X∈Rm×n,目標(biāo)用戶u,可調(diào)參數(shù)?,最近鄰居數(shù)目K,推薦結(jié)果個(gè)數(shù)N(N<=K )輸出N個(gè)推薦項(xiàng)目1對(duì)矩陣X篩選目標(biāo)用戶u未評(píng)分的項(xiàng)目集合Is={Is1, Is2,…, Ish};2利用Apriori算法挖掘頻繁項(xiàng)集,構(gòu)建頻繁項(xiàng)集矩陣F∈Rk×n3根據(jù)矩陣F和公式(3)計(jì)算基于頻繁項(xiàng)集的項(xiàng)目相似度矩陣S(1);4采用公式(4)計(jì)算基于用戶評(píng)分?jǐn)?shù)據(jù)的項(xiàng)目相似度矩陣S(2);5利用?和公式(5)計(jì)算項(xiàng)目間的綜合相似性,得到相似性矩陣S;6for i=1,2,3,…,h do7對(duì)矩陣S篩選Isi與其他項(xiàng)目的相似度矩陣;8根據(jù)其相似度值取Top-K個(gè)項(xiàng)目作為Isi的最近鄰居Na;9根據(jù)公式(6)計(jì)算用戶u對(duì)Isi的預(yù)測(cè)評(píng)分;10end for11對(duì)步驟6～10的結(jié)果進(jìn)行降序排列,選擇Top-N個(gè)項(xiàng)目作為用戶u的推薦結(jié)果

本文算法實(shí)現(xiàn)中需要構(gòu)建項(xiàng)目-項(xiàng)目相似度矩陣,其所需要的時(shí)間復(fù)雜度為O(n2) ，在對(duì)h個(gè)未評(píng)分項(xiàng)目中每一個(gè)項(xiàng)目進(jìn)行預(yù)測(cè)時(shí)，需尋找K個(gè)最近鄰居，因此本算法的時(shí)間復(fù)雜度為O(n2+h·K).

由算法偽代碼可知，本文提出的BFIM算法在項(xiàng)目相似度計(jì)算中考慮了項(xiàng)目?jī)?nèi)在的關(guān)聯(lián)性，對(duì)相似度計(jì)算方法進(jìn)行了改進(jìn)，下面將通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證算法的相關(guān)性能.

3 實(shí)驗(yàn)與分析

3.1 數(shù)據(jù)集

本文的實(shí)驗(yàn)采用目前衡量推薦系統(tǒng)推薦質(zhì)量的最常用的MovieLens數(shù)據(jù)集(https://grouplens.org/datasets/movielens/)，該數(shù)據(jù)集是由美國(guó)Minnesota大學(xué)GroupLens研究小組公布的，它包含了943名用戶對(duì)1682部電影的評(píng)分，共105條評(píng)分記錄.為了進(jìn)行實(shí)驗(yàn)比較，將數(shù)據(jù)集進(jìn)行十折交叉驗(yàn)證，進(jìn)行10次實(shí)驗(yàn)，每次實(shí)驗(yàn)將數(shù)據(jù)集的90%作為訓(xùn)練集，10%作為測(cè)試集.

3.2 評(píng)價(jià)指標(biāo)

推薦算法的推薦效果評(píng)價(jià)標(biāo)準(zhǔn)有準(zhǔn)確度、覆蓋度、多樣性等，其中準(zhǔn)確度是推薦系統(tǒng)的推薦質(zhì)量評(píng)估中最常用的指標(biāo)，本文以平均絕對(duì)差MAE為判斷算法推薦質(zhì)量的標(biāo)準(zhǔn)，其計(jì)算方法如公式(7)、(8)所示.

(7)

其中，MAEu是用戶u對(duì)Nu個(gè)項(xiàng)目預(yù)測(cè)評(píng)分的平均絕對(duì)偏差,Pu,i表示用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分，qu,i表示用戶u對(duì)項(xiàng)目i的實(shí)際評(píng)分，Nu是測(cè)試集所提供的用戶u的評(píng)分項(xiàng)目數(shù)量.

(8)

其中M是全體用戶總數(shù)，MAE則是測(cè)試集全體用戶的平均絕對(duì)偏差.可看出，MAE的值越小，則預(yù)測(cè)越精確，算法推薦的準(zhǔn)確性越高.

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

實(shí)驗(yàn)分為兩部分，第一部分是對(duì)影響頻繁項(xiàng)集挖掘質(zhì)量的最小支持度閾值minSup和綜合相似度的加權(quán)因子?進(jìn)行選取和比較，找到使算法推薦結(jié)果最優(yōu)的minSup和?.在第一部分實(shí)驗(yàn)取得最優(yōu)的基礎(chǔ)上，第二部分實(shí)驗(yàn)是對(duì)其他推薦算法與本文的BFIM算法在不同的最近鄰取值下的性能進(jìn)行比較，從而說(shuō)明BFIM算法的有效性.

3.3.1minSup與?選取

首先確定最小支持度minSup的大小.將?設(shè)為0.2，minSup在0.1～0.4之間，以0.05遞增，隨著minSup的增加，觀察算法的MAE值的變化.實(shí)驗(yàn)結(jié)果如圖1所示.

圖1 最小支持度對(duì)推薦精度的影響Fig.1 Effect of minimum support on the accuracy of the recommendation

由圖1可知，將加權(quán)因子?設(shè)為0.2時(shí)，minSup取0.2時(shí)，MAE最小，當(dāng)0.2

下一步確定加權(quán)因子?的大小.使minSup=0.2，改變加權(quán)因子?的大小，?∈[0,1]，每次遞增0.2.實(shí)驗(yàn)結(jié)果如圖2所示，?=0.4時(shí)MAE值最小，因此minSup=0.2，?=0.4，BFIM算法取得最優(yōu)推薦質(zhì)量.

圖2 加權(quán)因子對(duì)推薦精度的影響Fig.2 Effect of weighting factors on the accuracy of the recommendation

3.3.2 算法比較

為驗(yàn)證本文提出的BFIM算法的性能，將基于項(xiàng)目的協(xié)同過(guò)濾推薦(IBCF算法)，基于項(xiàng)目評(píng)分預(yù)測(cè)的推薦(IRBCF算法)與本文的BFIM算法進(jìn)行比較，均采用十折交叉驗(yàn)證法進(jìn)行實(shí)驗(yàn)，每次隨機(jī)將數(shù)據(jù)集劃分為10份，選9份為訓(xùn)練集，1份為測(cè)試集，然后得到10次實(shí)驗(yàn)的驗(yàn)證結(jié)果.如圖3所示，BFIM算法的MAE值與其他算法相比大部分都較小，即本文的BFIM算法推薦效果更好.

圖3 實(shí)驗(yàn)次數(shù)對(duì)推薦精度的影響Fig.3 Effect of the number of experiments on the accuracy of the recommendation

圖4展示了最近鄰數(shù)目與MAE值的關(guān)系，最近鄰數(shù)目在5～40之間，隨著最近鄰數(shù)目的增加，3種推薦算法的MAE值均不同程度地降低，推薦質(zhì)量不斷提高，當(dāng)最近鄰數(shù)目一定時(shí)，BFIM算法的MAE值明顯小于傳統(tǒng)推薦算法，表明文中提出的BFIM算法優(yōu)于傳統(tǒng)的推薦算法.

圖4 3種算法MAE對(duì)比圖Fig.4 Comparison of three algorithms on MAE

4 結(jié)語(yǔ)

協(xié)同過(guò)濾是如今應(yīng)用成功的推薦算法之一，然而該算法過(guò)度依賴評(píng)分?jǐn)?shù)據(jù)，忽略了項(xiàng)目間關(guān)聯(lián)的特性.在數(shù)據(jù)極端稀疏的情況下，傳統(tǒng)基于項(xiàng)目的協(xié)同過(guò)濾算法不能準(zhǔn)確找到目標(biāo)項(xiàng)目的最近鄰居，導(dǎo)致推薦不準(zhǔn)確.對(duì)此，文中提出的結(jié)合頻繁項(xiàng)集與項(xiàng)目相似度的協(xié)同過(guò)濾推薦算法，通過(guò)Apriori算法找到事務(wù)數(shù)據(jù)庫(kù)頻繁被購(gòu)買的項(xiàng)目，計(jì)算基于頻繁項(xiàng)集的項(xiàng)目相似度，再與Pearson相關(guān)系數(shù)加權(quán)計(jì)算項(xiàng)目的綜合相似度，該算法不僅考慮了事務(wù)數(shù)據(jù)的頻繁項(xiàng)集，還考慮了用戶評(píng)分?jǐn)?shù)據(jù)，減小了相似度計(jì)算值與實(shí)際值的偏差，從而提高了推薦算法的質(zhì)量.