程 芳 沈紅巖 趙 艷

(河北農(nóng)業(yè)大學(xué)信息科學(xué)與技術(shù)學(xué)院，河北 保定 071000)

?

·技術(shù)視角·

一種有效緩解數(shù)據(jù)稀疏問題的協(xié)同過濾推薦算法

程 芳 沈紅巖 趙 艷

(河北農(nóng)業(yè)大學(xué)信息科學(xué)與技術(shù)學(xué)院，河北 保定 071000)

傳統(tǒng)協(xié)同過濾推薦算法依據(jù)共同評分項(xiàng)目計(jì)算用戶相似度，進(jìn)而產(chǎn)生推薦項(xiàng)目。然而，隨著用戶和商品數(shù)量的不斷增加，用戶共同評分的項(xiàng)目會越來越少，甚至沒有，因此傳統(tǒng)協(xié)同過濾推薦算法對用戶之間相似度的衡量將會越來越不準(zhǔn)確，從而影響推薦系統(tǒng)的性能。針對這一問題，本文對用戶相似度的計(jì)算方法進(jìn)行了改進(jìn)，提出直接相似度和間接相似度的概念，同時(shí)引入關(guān)鍵人物權(quán)重，進(jìn)一步提高推薦系統(tǒng)的準(zhǔn)確性。

電子商務(wù)；推薦系統(tǒng)；協(xié)同過濾；直接相似度；間接相似度；關(guān)鍵人物

隨著電子商務(wù)的迅速發(fā)展，電子商務(wù)網(wǎng)站平臺的商品越來越多，同時(shí)相當(dāng)多的用戶面臨著海量的商品往往不知如何下手，必須花費(fèi)大量的時(shí)間和精力來尋找所需的信息，因此智能推薦系統(tǒng)在電子商務(wù)網(wǎng)站中尤為重要。協(xié)同過濾推薦是目前最好的一種推薦技術(shù)[1]，其根據(jù)用戶的評分?jǐn)?shù)據(jù)進(jìn)行項(xiàng)目推薦。傳統(tǒng)的協(xié)同過濾推薦技術(shù)雖然一段時(shí)間內(nèi)發(fā)揮了很大的作用，然而隨著電子商務(wù)網(wǎng)站規(guī)模的不斷擴(kuò)大，協(xié)同過濾推薦技術(shù)面臨著眾所周知的嚴(yán)重問題[2]：(1)“稀疏性”問題：用戶-項(xiàng)目評價(jià)矩陣非常稀疏；(2)“冷啟動(dòng)”問題：一個(gè)新的商品出現(xiàn)時(shí)，用戶對其評分會特別少，甚至沒有，那么這個(gè)商品就不容易被推薦出去。另外，一個(gè)新用戶加入時(shí)，由于沒有對任何項(xiàng)目進(jìn)行過評價(jià)，系統(tǒng)就無法對其進(jìn)行推薦。(3)“可擴(kuò)展性”問題：面對用戶和商品數(shù)量的日益增多，系統(tǒng)的性能會越來越低。

為了解決數(shù)據(jù)稀疏而導(dǎo)致的推薦結(jié)果不準(zhǔn)確問題，許多學(xué)者提出了各自不同的方法。目前常用的方法有以下幾種：(1)數(shù)據(jù)填充：在計(jì)算用戶相似性之前，首先對原始的用戶-項(xiàng)目評分矩陣進(jìn)行填充，從而降低其稀疏性，提高推薦準(zhǔn)確度。郝立燕等[3]根據(jù)原始矩陣中評分?jǐn)?shù)據(jù)的特征，采用SOFT-IMPUTE算法對評分矩陣進(jìn)行填充，然后利用填充后的矩陣計(jì)算用戶相似性，進(jìn)而做出推薦預(yù)測。張玉芳等[4]采用分兩步對原始評分矩陣進(jìn)行填充的方法。首先在利用傳統(tǒng)協(xié)同過濾推薦算法尋找目標(biāo)用戶鄰居集時(shí)，只考慮相似度比較高的用戶作為目標(biāo)用戶鄰居，進(jìn)而對評分矩陣進(jìn)行第一次填充，然后將第一步填充后的矩陣作為新的用戶-項(xiàng)目矩陣，在此基礎(chǔ)上進(jìn)行第二次填充，此方法可以很好的解決數(shù)據(jù)稀疏問題。黃永鋒等[5]在原始評分矩陣基礎(chǔ)上，首先根據(jù)用戶訪問過的項(xiàng)目的特征及訪問頻率對用戶訪問過但沒有給出評價(jià)的項(xiàng)目進(jìn)行填充，從而降低原始評分矩陣的稀疏度，提高推薦準(zhǔn)確性。(2)聚類技術(shù)：在計(jì)算用戶相似性之前，首先對用戶或項(xiàng)目進(jìn)行聚類，從而降低預(yù)測計(jì)算量，提高推薦質(zhì)量。黃國言等[6]及崔春生等[7]提出對用戶進(jìn)行聚類的方法，前者根據(jù)用戶對項(xiàng)目評分的相似性對用戶進(jìn)行聚類，后者根據(jù)用戶的興趣度對用戶進(jìn)行聚類，進(jìn)而分別在各聚類內(nèi)部計(jì)算用戶相似性，產(chǎn)生推薦項(xiàng)目。吳潮等[8]提出對用戶和項(xiàng)目兩個(gè)方面分別聚類并互相結(jié)合的方法，在已有聚類中尋找用戶最近鄰居集，實(shí)現(xiàn)對用戶的推薦。(3)矩陣分解：對原始評分矩陣進(jìn)行分解，從而降低評分矩陣維數(shù)，提高推薦精確度。李改等[9]分析了傳統(tǒng)的矩陣分解模型(SVD)的弊端，并對其進(jìn)行了改進(jìn)，提出了帶正則化的基于迭代最小二乘法的矩陣分解方法，此方法提高了傳統(tǒng)推薦算法的抗稀疏性。楊陽等[10]提出增量奇異值矩陣分解的方法，對評分矩陣進(jìn)行梯度分解，從而有效的解決矩陣稀疏的問題。

以上幾種方法均在一定程度上緩解了評分矩陣的稀疏性問題，并取得了一定的成果，但在計(jì)算用戶形似度進(jìn)而尋找最近鄰居集時(shí)，仍局限于用戶共同評分項(xiàng)目，而大多數(shù)用戶共同評分項(xiàng)目極少，此時(shí)用戶相似度的計(jì)算只受幾個(gè)項(xiàng)目評分的影響，計(jì)算結(jié)果很容易出現(xiàn)偏差。尤其當(dāng)用戶興趣愛好一致但不存在共同評分項(xiàng)目時(shí)，系統(tǒng)則無法計(jì)算其相似性。針對這一問題，本文對傳統(tǒng)協(xié)同過濾推薦技術(shù)中計(jì)算用戶相似度及產(chǎn)生推薦項(xiàng)目的方法進(jìn)行改進(jìn)，使用戶相似度的計(jì)算不再僅僅依據(jù)用戶共同評分項(xiàng)目，同時(shí)兼顧用戶未評分項(xiàng)目，并引入關(guān)鍵人物權(quán)重，進(jìn)而進(jìn)一步提高推薦質(zhì)量。

1 傳統(tǒng)協(xié)同過濾推薦算法

協(xié)同過濾推薦算法的主要思想是，利用現(xiàn)有用戶群過去的評價(jià)數(shù)據(jù)來預(yù)測當(dāng)前用戶的購買意向[3]。這種方法的潛在假設(shè)是，如果某些用戶對一些項(xiàng)目的評價(jià)相似，那么他們對其他項(xiàng)目的評分也是相似的。通過相似性計(jì)算發(fā)現(xiàn)和當(dāng)前用戶相似的N個(gè)近鄰，根據(jù)興趣相似的用戶群的評價(jià)，計(jì)算產(chǎn)生對某些項(xiàng)目的預(yù)測評分，最后根據(jù)預(yù)測值將排名最前的k個(gè)項(xiàng)目推薦給當(dāng)前用戶。算法一般分為3步：建立用戶-物品評分矩陣，計(jì)算用戶相似度并尋找近鄰集，產(chǎn)生推薦項(xiàng)目[11]。

1.1 建立用戶-物品評分矩陣

推薦系統(tǒng)經(jīng)常利用用戶對已購買物品的評分作為推薦系統(tǒng)的數(shù)據(jù)源，一般定義用戶集U={U1，U2，…，Um}，物品集定義為I={I1，I2，…，In}，通常用戶-物品評分矩陣用矩陣Rm×n來表示，其中的每一項(xiàng)Rij表示第i個(gè)顧客對第j個(gè)商品項(xiàng)的評價(jià)值[12]，通過獲得的評價(jià)值來反映顧客的購買興趣。通常以1～5表示用戶對物品的偏好程度，沒有評分的項(xiàng)目用0代替。

1.2 計(jì)算用戶相似度并尋找近鄰集

在這一步先計(jì)算用戶之間的相似度，然后根據(jù)相似度尋找到用戶的最近鄰居集。在協(xié)同過濾推薦系統(tǒng)中，確定相似用戶集，一般采用的方法是Pearson相關(guān)系數(shù)[3]。給定評分矩陣R，用戶a和用戶b的相似度sim(a，b)可以用公式(1)來表示。

(1)

1.3 產(chǎn)生推薦項(xiàng)目

對于用戶a未作評價(jià)的項(xiàng)目，可以通過用戶a的最近鄰居集N的評分來預(yù)測，具體方法如下：

(2)

最終推薦項(xiàng)目的獲取可以通過選擇預(yù)測分?jǐn)?shù)最高的N個(gè)項(xiàng)目作為推薦結(jié)果。

2 本文算法

在大型電子商務(wù)網(wǎng)站中，用戶評分的項(xiàng)目極為稀疏，一般不足1%，傳統(tǒng)的協(xié)同過濾推薦算法無疑會導(dǎo)致算法準(zhǔn)確率下降，使得系統(tǒng)難以找到真正的相似用戶。為了彌補(bǔ)傳統(tǒng)相似度計(jì)算方法的缺陷，本文提出了一種改進(jìn)的協(xié)同過濾推薦算法。

2.1 用戶相似度計(jì)算方法的改進(jìn)

本文用戶相似度的計(jì)算方法與傳統(tǒng)的推薦系統(tǒng)不同之處在于，在計(jì)算用戶a與用戶b的相似度時(shí)，不僅僅根據(jù)兩個(gè)用戶共同評價(jià)過的項(xiàng)目集合進(jìn)行計(jì)算，同時(shí)考慮用戶a評價(jià)過，而用戶b未評價(jià)過的項(xiàng)目集合。即計(jì)算用戶a與用戶b的相似度Sab時(shí)，需綜合考慮直接相似度和間接相似度兩個(gè)因素，計(jì)算公式如下：

Sab=α*Ri+(1-α)*Rj

(3)

其中，Ri表示用戶a與用戶b的直接相似度，Rj表示用戶a與用戶b的間接相似度，α為小于1的權(quán)重系數(shù)。下面分別給出Ri和Rj的計(jì)算公式。

2.1.1 計(jì)算直接相似度

在用戶-物品評分矩陣中，如果用戶a與用戶b共同評價(jià)過同一個(gè)項(xiàng)目，則認(rèn)為用戶a與用戶b進(jìn)行了一次交易，那么用戶a與用戶b之間的相似度可以直接利用Pearson系數(shù)計(jì)算方法，公式如下：

(4)

2.1.2 計(jì)算間接相似度

在用戶-物品評分矩陣中，定義用戶a評價(jià)過的項(xiàng)目集為Ia，用戶b評價(jià)過的項(xiàng)目集為Ib，用戶a評價(jià)過但用戶b沒有評價(jià)的項(xiàng)目集合Id=Ia-(Ia∩Ib)。這里首先采用傳統(tǒng)的協(xié)同過濾推薦技術(shù)尋找用戶b的最近鄰居集，進(jìn)而得到用戶b對項(xiàng)目集Id的預(yù)測評價(jià)值，進(jìn)而在項(xiàng)目集Id上，通過用戶a的評價(jià)值與用戶b的預(yù)測評價(jià)值得到的相似度即為用戶a與用戶b的間接相似度。因此，計(jì)算用戶a與用戶b的間接相似度公式如下：

(5)

其中，ra，p是用戶a對項(xiàng)目p的評價(jià)值，rb，p是用戶b對項(xiàng)目p的預(yù)測評價(jià)值。

2.2 關(guān)鍵人物的引入

在所有的用戶中，總會有一些關(guān)鍵人物的存在。在推薦系統(tǒng)中，關(guān)鍵人物即為對推薦有特別幫助的用戶。關(guān)鍵人物具有如下特征，如內(nèi)行：定義為寫了很多評論的用戶；頻繁評分者：評價(jià)了很多的物品；連接者：信任很多人，也被很多人信任。在推薦系統(tǒng)中引入關(guān)鍵人物能夠提高最終結(jié)果的準(zhǔn)確度。

由于關(guān)鍵人物的評價(jià)對提高推薦系統(tǒng)的準(zhǔn)確度起著重要的作用，因此，本文提高了關(guān)鍵人物的信任值權(quán)重，以此提高推薦系統(tǒng)準(zhǔn)確度。在用戶-物品評價(jià)矩陣中，如果用戶a的近鄰集N中包含用戶b，即Ub∈N，且用戶b為關(guān)鍵人物。那么，引入關(guān)鍵人物權(quán)重后，計(jì)算用戶a與用戶b的相似度Sab的公式可以修改如下：

Sab=β*(α*Ri+(1-α)*Rj)

(6)

其中，β為大于1的權(quán)重系數(shù)。

2.3 產(chǎn)生推薦項(xiàng)目

改進(jìn)用戶相似度計(jì)算及引入關(guān)鍵人物后，產(chǎn)生推薦項(xiàng)目可以由公式(2)修改如下：

(7)

最終推薦項(xiàng)目的獲取可以通過選擇預(yù)測分?jǐn)?shù)最高的N個(gè)項(xiàng)目作為推薦結(jié)果。

3 推薦方法測試

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境使用的服務(wù)器為IBM System x3850 X6，CPU為2枚Xeon E7-4820，最高主頻為2.5G，內(nèi)存是4*16GB DDR3，共計(jì)64GB，操作系統(tǒng)采用Microsoft Windows Server 2012，推薦算法采用JAVA語言編寫。

3.2 實(shí)驗(yàn)集

本文采用了MovieLens提供的數(shù)據(jù)集(http:∥www.grouplens.org)作為測試數(shù)據(jù)，MovieLens數(shù)據(jù)集包含了1997年9月至1998年5月的943個(gè)用戶對1 682部電影的100 000條評價(jià)記錄，每個(gè)用戶評價(jià)了至少20部電影，評分范圍1～5。針對這一數(shù)據(jù)集，出現(xiàn)了很多劃分訓(xùn)練集和測試集的方法，本文采用的是站點(diǎn)提供的一種方法，將測試數(shù)據(jù)分為了訓(xùn)練集(占80%)和測試集(占20%)，因此可以計(jì)算得出稀疏度為：(943*1682-100000)/(943*1682)=93.695%。

3.3 評價(jià)標(biāo)準(zhǔn)

評價(jià)推薦系統(tǒng)推薦質(zhì)量的標(biāo)準(zhǔn)主要有統(tǒng)計(jì)精度度量方法和決策支持精度度量方法[13]。本文采用統(tǒng)計(jì)精度度量方法中廣泛使用的平均絕對偏差(Mean Absolute Error，MAE)作為度量標(biāo)準(zhǔn)，即通過計(jì)算預(yù)測的用戶評分與實(shí)際用戶評分之間的偏差來衡量預(yù)測的準(zhǔn)確性。MAE的計(jì)算公式如下[14]：

(8)

其中，N表示預(yù)測分?jǐn)?shù)的數(shù)量，pi代表項(xiàng)目i的預(yù)測評分，而qi代表項(xiàng)目i的實(shí)際評分。MAE值越小，準(zhǔn)確度越高。

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

為驗(yàn)證本文推薦算法的有效性，在實(shí)驗(yàn)過程中，分別采用兩種推薦算法，即本文所改進(jìn)的協(xié)同過濾推薦算法和傳統(tǒng)協(xié)同過濾推薦算法，并對兩種情況下的推薦結(jié)果進(jìn)行對比分析。推薦算法中目標(biāo)用戶的最近鄰居數(shù)以4為間隔從4個(gè)增加到32個(gè)。經(jīng)過實(shí)驗(yàn)驗(yàn)證，取得最優(yōu)的權(quán)值參數(shù)α值為0.8，β值為1.3，觀察不同條件下的推薦效果。實(shí)驗(yàn)結(jié)果如表1。

表1 兩種推薦算法的MAE值比較

傳統(tǒng)的協(xié)同過濾推薦算法與本文改進(jìn)的協(xié)同過濾推薦算法的推薦試驗(yàn)MAE值比較結(jié)果直觀表示如圖1所示。

圖1 兩種推薦技術(shù)的MAE值比較

由以上實(shí)驗(yàn)結(jié)果可以看出，本文所改進(jìn)的推薦算法，對推薦結(jié)果有明顯的改善。隨著目標(biāo)用戶最近鄰居數(shù)目的增加，雖然兩種推薦算法的MAE值都呈下降趨勢，但當(dāng)鄰居數(shù)較多時(shí)，本文推薦算法的優(yōu)勢越來越明顯，推薦結(jié)果更加準(zhǔn)確。由此可見，本文所提出的協(xié)同過濾推薦算法可以增強(qiáng)推薦系統(tǒng)的抗稀疏性，提高推薦系統(tǒng)的推薦質(zhì)量。

4 結(jié) 論

隨著電子商務(wù)網(wǎng)站的迅速發(fā)展壯大，智能推薦系統(tǒng)在電子商務(wù)網(wǎng)站中發(fā)揮著越來越重要的作用，而推薦算法決定了推薦系統(tǒng)的性能。計(jì)算用戶相似度是協(xié)同過濾推薦算法中最為關(guān)鍵的一步，本文在計(jì)算用戶相似度時(shí)充分考慮直接相似度、間接相似度以及關(guān)鍵人物權(quán)重三個(gè)方面因素，實(shí)驗(yàn)結(jié)果證明，本文所改進(jìn)的計(jì)算用戶相似度的方法比傳統(tǒng)的計(jì)算方法更合理更準(zhǔn)確。尤其對于評分項(xiàng)目極少的用戶，可以根據(jù)間接相似度尋找其近鄰集，進(jìn)而產(chǎn)生推薦項(xiàng)目。因此本推薦算法不僅可以很好的解決評分矩陣數(shù)據(jù)稀疏問題，同時(shí)還可以在一定程度上緩解系統(tǒng)冷啟動(dòng)問題。

[1]許海玲，吳瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J]．軟件學(xué)報(bào)，2009，20(2):350-362.

[2]夏建勛，吳非，謝長生．應(yīng)用數(shù)據(jù)填充緩解稀疏問題實(shí)現(xiàn)個(gè)性化推薦[J]．計(jì)算機(jī)工程與科學(xué)，2013，35(5):15-19.

[3]郝立燕，王靖．基于填充和相似性信任因子的協(xié)同過濾推薦算法[J]．計(jì)算機(jī)應(yīng)用，2013，33(3):834-837.

[4]張玉芳，代金龍，熊忠陽.分步填充緩解數(shù)據(jù)稀疏性的協(xié)同過濾算法[J]．計(jì)算機(jī)應(yīng)用研究，2013，30(9):2602-2605.

[5]黃永鋒，覃羅春．一種有效緩解協(xié)同過濾推薦評價(jià)數(shù)據(jù)稀疏問題的算法[J]．東華大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，39(1):83-87.

[6]黃國言，李有超，高建培，等.基于項(xiàng)目屬性的用戶聚類協(xié)同過濾推薦算法[J]．計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(5):1038-1041.

[7]崔春生，吳祈宗，王瑩.用于推薦系統(tǒng)聚類分析的用戶興趣度研究[J]．計(jì)算機(jī)工程與應(yīng)用，2011，47(7):226-228.

[8]吳潮，王永吉，王哲，等.兩階段聯(lián)合聚類協(xié)同過濾算法[J]．軟件學(xué)報(bào)，2010，21(5):1042-1054.

[9]李改，李磊.基于矩陣分解的協(xié)同過濾算法[J]．計(jì)算機(jī)工程與應(yīng)用，2011，47(30):4-7.

[10]楊陽，向陽，熊磊.基于矩陣分解與用戶近鄰模型的協(xié)同過濾推薦算法[J]．計(jì)算機(jī)應(yīng)用，2012，32(2):395-398.

[11]曾慶輝，邱玉輝．一種基于協(xié)作過濾的電子圖書推薦系統(tǒng)[J]．計(jì)算機(jī)科學(xué)，2005，32(6):147-150.

[12]劉東輝，彭德巍，張暉．一種基于時(shí)間加權(quán)和用戶特征的協(xié)同過濾算法[J]．武漢理工大學(xué)學(xué)報(bào)，2012，34(5):144-148.

[13]劉慶鵬，陳明銳．優(yōu)化稀疏數(shù)據(jù)集提高協(xié)同過濾推薦系統(tǒng)質(zhì)量的方法[J]．計(jì)算機(jī)應(yīng)用，2012，32(4):1082-1085.

[14]郭均鵬，王啟鵬，寧靜，等.基于符號數(shù)據(jù)與非負(fù)矩陣分解法的混合推薦算法[J]．系統(tǒng)管理學(xué)報(bào)，2015，24(3):372-378.

(本文責(zé)任編輯：孫國雷)

Collaborative Filtering Recommendation Algorithm for Alleviating Data Sparsity

Cheng Fang Shen Hongyan Zhao Yan

(College of Information Science and Technology，Agricultural University of Hebei，Baoding 071000，China)

In traditional collaborative filtering recommendation Algorithm,similarity of users is often calculated based on common ratings,and then the recommended items are produced.However,with the increasing number of users and products,the common rated items will be less and less,and even no.So the measure of the similarity of users will be more and more inaccurate,and thus it will affect the performance of the recommendation system.In order to solve this problem,the method of calculating the similarity of users is improved,and the concepts of direct similarity and indirect similarity are put forward.At the same time,in order to further improve the accuracy of the recommendation system,the key figure is introduced into the system.

e-commerce;recommending system;collaborative filtering;direct similarity;indirect similarity;key figures

2015-12-27

保定市科學(xué)技術(shù)研究與發(fā)展指導(dǎo)計(jì)劃項(xiàng)目“基于協(xié)同過濾的農(nóng)業(yè)信息推薦系統(tǒng)的研究與開發(fā)”(項(xiàng)目編號：14ZN019)、“農(nóng)網(wǎng)中工控網(wǎng)絡(luò)信息安全攻擊監(jiān)測方法的研究”(項(xiàng)目編號：14ZS005)；河北農(nóng)業(yè)大學(xué)?；稹盎谥悄苁謾C(jī)的三農(nóng)科技信息服務(wù)體系的關(guān)鍵技術(shù)研究”(項(xiàng)目編號：LG201308)。

程 芳(1980-)，女，講師，碩士，研究方向：數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用。

10．3969/j．issn．1008-0821．2016．03．013

TP301

A

1008-0821(2016)03-0076-04