基于改進(jìn)型啟發(fā)式相似度模型的協(xié)同過濾推薦方法

張南　林曉勇　史晟輝

摘要：為提高協(xié)同過濾推薦方法的準(zhǔn)確性和有效性，提出一種基于改進(jìn)型啟發(fā)式相似度模型的協(xié)同過濾推薦方法PSJ。該方法考慮了用戶評分差值、用戶全局評分偏好和用戶共同評分物品數(shù)三個因素。PSJ方法的Proximity因子使用指數(shù)函數(shù)反映用戶評分差值對用戶相似度的影響，這樣也可避免零除問題；將NHSM（new heuristic similarity model）方法中的Significance因子和URP因子合并成PSJ方法的Significance因子，這使得PSJ方法的計算復(fù)雜度低于NHSM方法；而且為了提高在數(shù)據(jù)稀疏情況下的推薦效果，PSJ方法同時考慮了用戶間的評分差值和用戶全局評分兩個因素。實驗采用Top-k推薦中的查準(zhǔn)率和查全率作為衡量標(biāo)準(zhǔn)。實驗結(jié)果表明，當(dāng)推薦物品數(shù)大于20時，與NHSM、杰卡爾德算法、自適應(yīng)余弦相似度（ACOS）算法、杰卡爾德均方差（JMSD）算法和皮爾遜相關(guān)系數(shù)算法（SPCC）相比，PSJ方法的查準(zhǔn)率與查全率均有提升。

關(guān)鍵詞：協(xié)同過濾推薦方法；啟發(fā)式相似度模型；用戶相似度；推薦效果；數(shù)據(jù)稀疏

中圖分類號：TP181

文獻(xiàn)標(biāo)志碼：A

0引言

互聯(lián)網(wǎng)的信息量正變得越來越大，然而大量的線上信息也帶來一些不便。例如，某個消費者希望在網(wǎng)上買一部智能手機，在做出決定之前他將非常困惑，因為他將瀏覽和比較大量的互聯(lián)網(wǎng)上提供的智能手機信息。推薦系統(tǒng)就是為了解決這種問題而被發(fā)明的，它會自動為用戶提供購買物品的建議。準(zhǔn)確的推薦可以幫助用戶快速找到他感興趣的物品并且避免用戶瀏覽大量的相關(guān)商品。推薦系統(tǒng)同時對經(jīng)銷商來說也是一個很好的助手，它可以向訪問經(jīng)銷商網(wǎng)站的瀏覽者推薦網(wǎng)站內(nèi)的商品，通過這樣的方式經(jīng)銷商有可能將這些瀏覽者變成長期客戶。

協(xié)同過濾方法[1]首先被發(fā)明用于郵件過濾，現(xiàn)在它已經(jīng)非常廣泛地用于推薦系統(tǒng)。它依據(jù)激活用戶的相似度或者被激活用戶評過分的物品的相似度提供推薦結(jié)果。協(xié)同過濾技術(shù)可以被分成兩類：基于內(nèi)存的方法和基于模型的方法[2]?；趦?nèi)存的方法首先利用用戶評分?jǐn)?shù)據(jù)計算用戶之間的相似度，然后將相似度值超過某個閾值的用戶作為目標(biāo)用戶的鄰居，最后根據(jù)這些鄰居產(chǎn)生推薦結(jié)果?；谀Ｐ偷姆椒ǖ墓ぷ鞣绞酵耆煌?。它首先建立一個模型用于描述用戶的行為，并用這個模型來預(yù)測用戶對物品的評分。協(xié)同過濾方法的關(guān)鍵是計算用戶之間的相似度，因此相似度計算的準(zhǔn)確性將影響推薦的準(zhǔn)確性。現(xiàn)在有許多相似度算法，例如：杰卡爾德相似度（Jaccard similarity， Jaccard）算法[3]、余弦相似度（COSine similarity， COS）算法[4]、皮爾遜相關(guān)系數(shù)（Pearson Correlation Coefficient， PCC）算法[5]。除了協(xié)同過濾方法之外，還有許多方法被用于推薦系統(tǒng)，例如：語義推薦、社交推薦、基于內(nèi)容的技術(shù)。

Jaccard方法[2]和均方差相似度算法（Mean Squared Difference， MSD）[9]也是很常用的計算相似度的方法，其中：Jaccard方法只考慮到了用戶共同評分物品的數(shù)量，沒有考慮用戶評分的數(shù)值；而MSD方法只考慮到了用戶評分的數(shù)值，但沒有考慮到用戶共同評分的物品數(shù)量。有研究人員認(rèn)為可以將兩種方法的優(yōu)缺點相互彌補，為此提出了杰卡爾德均方差（Jaccard Mean Squared Difference， JMSD）相似度算法[10]。這三種相似度計算方法的計算公式分別如下：

以上九種算法可以分為三類：第一類只考慮了用戶之間對同一個物品的評分而沒有考慮共同評分物品的數(shù)量，包括COS、ACOS、PCC、CPCC和MSD方法。這類算法的缺點是會出現(xiàn)用戶之間相似值偏高或偏低的現(xiàn)象。第二類只考慮了用戶之間共同評分物品數(shù)而沒有考慮用戶之間對同一個物品的評分，Jaccard方法屬于這一類算法；這類算法在數(shù)據(jù)不是很稀疏時會表現(xiàn)出大量用戶之間相似度值相等的情況，這樣就難以發(fā)現(xiàn)用戶組之間的差異。第三類是混合型算法，這類算法至少考慮了兩點與用戶間相似度計算相關(guān)的因素，如SPCC、JMSD和NHSM方法。這些與相似度計算相關(guān)的因素都在前兩類算法的設(shè)計思想中有體現(xiàn)，例如ACOS方法考慮了用戶評分均值對相似度的影響，MSD方法考慮了用戶評分差值對相似度的影響，Jaccard方法考慮了共同評分物品數(shù)目對相似度計算的影響。這類算法與前兩類算法相比在計算用戶之間的相似度值時更加準(zhǔn)確。另外根據(jù)文獻(xiàn)[11]中的實驗結(jié)果顯示，NHSM方法在數(shù)據(jù)稀疏的情況下能取得更好的推薦效果。

2本文算法

NHSM方法的五個因素中，有些因素還需要額外的計算，這使得NHSM方法十分復(fù)雜，而各個計算環(huán)節(jié)都會帶來誤差，多個計算誤差相互疊加會增大偏離實際值的可能性，因此該方法的推薦效果在某些情況下不是很理想。本文將提出簡化的NHSM方法。

2.1設(shè)計思想

首先介紹一下實際應(yīng)用場景中的狀況。在現(xiàn)實場景中，系統(tǒng)中用戶只給系統(tǒng)中少部分物品評分，這樣用戶物品評分矩陣是非常稀疏的，所以應(yīng)該將數(shù)據(jù)稀疏性問題引入到考慮范圍中。下面是本文方法的考慮因素：

1）考慮用戶評分的不同非常重要。在文獻(xiàn)[12]的實驗部分可以發(fā)現(xiàn)，大部分相似度計算方法考慮到了用戶評分的不同。綜合第1章介紹的九種方法可以發(fā)現(xiàn)，有三種方式可以引入用戶評分的不同，一種是類似余弦相似度方法的那種乘積形式的計算公式，一種是MSD方法中的差值平方的方式，還有一種是NHSM方法中的指數(shù)函數(shù)的形式。在實際情況中，用戶間評分差值和相似度是成反比的關(guān)系，即相似度越高評分差值越小。因此可以直接采用指數(shù)函數(shù)倒數(shù)的形式，這樣處理沒有NHSM方法那么復(fù)雜，同時還可以避免乘積形式中零除現(xiàn)象的出現(xiàn)。

2）用戶共同評分物品所占的比例不能被忽略。一些研究者認(rèn)為應(yīng)該考慮共同評分物品所占的比例對相似度計算的影響，在前面的介紹中可以發(fā)現(xiàn)，SPCC[8]、JMSD[10]和NHSM方法[11]都引入了用戶共同評分物品所占的比例，它們的實驗結(jié)果顯示這三種方法都提升了推薦效果。

3）應(yīng)該考慮到用戶評分的局部上下文和用戶評分全局偏好。在 NHSM方法[11]的設(shè)計思想中提到了這一條設(shè)計思想，而且它的實驗結(jié)果顯示，當(dāng)數(shù)據(jù)集稀疏度越高時，NHSM方法相比那些只考慮了用戶評分的局部上下文的方法推薦效果要好。

4）應(yīng)該使用用戶全局評分均值區(qū)分用戶對商品是喜歡還是討厭。在 ACOS方法[6]的設(shè)計思想中提到了用戶評分偏好對相似度計算的影響。通過觀察不同網(wǎng)站的評分頁面可以發(fā)現(xiàn)，大多數(shù)頁面中沒有明顯地提醒用戶評分域的中間值是一個區(qū)分喜歡和討厭的中間值，因此用戶會根據(jù)自己的偏好進(jìn)行評分。根據(jù)上述情況可以將NHSM方法中的Significance因子和URP因子合并。

5）NHSM方法[11]中Singularity因子可能不如作者認(rèn)為的那么有效?？梢约僭O(shè)這樣的情景，當(dāng)評分域為1～5，只有5個評分域且只有5個不同的評分時，假設(shè)用戶1給物品1評分1，用戶2給物品1評分5，用戶3給物品1評分3，用戶4給物品1評分3，可以發(fā)現(xiàn)用戶1與用戶2的Singularity值和用戶3與用戶4的Singularity值相同。這顯然給相似度計算帶來了誤導(dǎo)。因為大多數(shù)評分?jǐn)?shù)據(jù)集的評分粒度不夠大，使用該因子不一定能使用戶組之間區(qū)分度增大，反而增加了計算復(fù)雜度和計算誤差。

綜合所述，本文將NHSM方法中的五個因子簡化為三個因子，并用一個更簡化的方程來重新定義Proximity因子，同時將Significance因子和URP因子結(jié)合在一起重新定義了新的Significance因子，而且在將Singularity因子移除的同時保留原來的Jaccard′因子。

由于在PSJ方法的Significance因子已經(jīng)考慮了用戶全局評分喜好，所以PSJ方法中的Significance因子是將NHSM方法中的Significance因子和URP因子合并。

為了考慮共同評分物品的所占比例，PSJ方法仍然使用NHSM算法中的Jaccard′方法，通過實際的實驗對比可知，它融合到PSJ方法中產(chǎn)生的推薦效果比原始的Jaccard方法融入到PSJ方法產(chǎn)生的推薦效果更好，它的計算方式定義如下：

圖1表示各個相似度算法的相似度計算結(jié)果。由于這些矩陣是對稱的，這里只列舉出了矩陣的上半部分，行從左到右表示用戶1～6，列從上到下表示用戶1～6。

1）可以在圖1（a）中發(fā)現(xiàn)用戶1與用戶2的相似度高于用戶1與用戶3之間的相似度。用戶2的評分向量為（4，1，—，5，—，4，1），并且用戶3的評分向量為（5，—，1，—， 5，5，1）。通過觀察可以發(fā)現(xiàn)用戶3有兩個評分分值和用戶1相同，而用戶2只有一個評分和用戶1相同，這兩個用戶的其他的評分大致與用戶1相同。因此用戶1與用戶3的相似度應(yīng)該高于用戶1與用戶2。這個錯誤也發(fā)生在ACOS方法中，PSJ方法糾正了這個相似度計算錯誤。

2）仔細(xì)觀察用戶1與用戶3的評分向量，在圖1（c）中可以發(fā)現(xiàn)，用戶1與用戶3的相似度達(dá)到了0.997，用戶1與用戶3之間只有兩個相同評分物品，這個值跟實際情況相比偏高，這個問題也發(fā)生在CPCC、SPCC和MSD方法中。在PSJ方法中的計算結(jié)果是0.646，該結(jié)果足夠用于描述用戶1與用戶3的相似度。

3）在圖1（f）中可以發(fā)現(xiàn)，用戶2和用戶5的相似度與用戶2和用戶6的相似度相等。實際上，在表1中用戶2與用戶5對共同評分物品的評分差值還是比較大的，用戶2與用戶6的相似度應(yīng)該高于用戶2與用戶5之間的相似度。在PSJ方法中用戶2與用戶5中的相似度是0.037，并且用戶2與用戶6的相似度為0.117，與實際情況相符。

4）在圖1（c）中有許多相似度值為NaN，其產(chǎn)生是因為零除問題。這樣的問題也發(fā)生在CPCC、SPCC、MSD和JMSD方法中。將JMSD和MSD方法比較可以發(fā)現(xiàn)，JMSD方法中NaN值的數(shù)量相對少一些。PSJ方法的計算結(jié)果中沒有NaN值，這體現(xiàn)了PSJ方法使用指數(shù)函數(shù)的倒數(shù)的優(yōu)勢。

5）在圖1（f）中許多的相似度值為0.4和0.5。當(dāng)仔細(xì)觀察表1中各個用戶的評分向量后可以發(fā)現(xiàn)，這些用戶之間是彼此不同的，這些用戶之間的相似度值也應(yīng)該是不同的，這樣才能更好地區(qū)分他們。在PSJ方法的計算結(jié)果中這個問題得到了解決。

6）在圖1（g）中許多用戶的相似度值偏低，有些相似度值過于接近0。同時NHSM方法中用戶和用戶自己的相似度還是不同，即不等于1，這個問題也發(fā)生在SPCC方法中。在PSJ方法中這個問題得到了解決。

3實驗與分析

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

在實驗中使用了最新的MovieLens數(shù)據(jù)集，該數(shù)據(jù)集被叫作ml-latest-small。它包括706個用戶，8570部電影和100023個評分，每個用戶至少給20部電影評過分。它與其他MovieLens數(shù)據(jù)集的不同之處是：它的評分粒度更細(xì)一些，其評分域是0.5～5.0，有10個不同的評分值。它的用戶物品評分矩陣的密度是1.7%。

本文選取了該數(shù)據(jù)集中的所有用戶和前5000部電影，每個用戶至少給15部電影評過分，用于實驗的用戶物品評分矩陣密度仍然是1.7%。在實驗過程中，數(shù)據(jù)集被分成兩部分，80%的數(shù)據(jù)用于訓(xùn)練，剩下20%的數(shù)據(jù)用于測試。按照這樣的數(shù)據(jù)處理方式在實驗過程中一共進(jìn)行了五次交叉驗證，每次交叉驗證的訓(xùn)練集和測試集都不相同。

3.2相似度計算對推薦的影響

實驗設(shè)計：首先使用數(shù)據(jù)集里的數(shù)據(jù)建立一個用戶物品矩陣；然后，用相似度計算方法計算用戶之間的相似度，并建立用戶相似度矩陣；接著，建立推薦列表。建立推薦列表的操作又分成兩步：1）通過用戶相似度矩陣找出與用戶最相似度值排在前k的用戶，用鏈表將他們從高到低記錄下來；2）根據(jù)相似度值最高的用戶給出的評分排列這前k位用戶關(guān)注過的而目標(biāo)用戶從未關(guān)注過的物品，最終選取排在前n的物品推薦給目標(biāo)用戶。

對比方法分別是ACOS方法、SPCC方法、Jaccard方法、JMSD方法和NHSM方法。因為推薦的物品數(shù)量和最近鄰居的數(shù)量將影響到推薦效果，所以本文將實驗情景分成兩種狀況：第一種狀況是當(dāng)鄰近用戶數(shù)是定值而推薦物品數(shù)是變量，第二種情況是推薦物品數(shù)是定值而鄰近用戶數(shù)是變量。最終的每條實驗數(shù)據(jù)都由五次交叉實驗的結(jié)果求平均值得出。

在上述實驗中每個算法都要進(jìn)行35次用戶用戶相似度矩陣計算，在本章的3.2.4節(jié)中將通過用戶用戶相似度矩陣計算的平均時間說明PSJ方法的優(yōu)越性。

3.2.1衡量尺度

在商業(yè)化推薦系統(tǒng)中，總是推薦給用戶一個他或她可能喜歡的k件物品的列表，這種方式被稱為Top-k推薦。本文對比實驗也使用Top-k推薦，因此使用查全率和查準(zhǔn)率[14-16]來衡量實驗結(jié)果。

3.2.2推薦物品數(shù)

本節(jié)實驗將鄰近用戶數(shù)設(shè)為定值20，推薦物品數(shù)從10到70變化。

圖2展現(xiàn)的是當(dāng)Top-k中k變化時不同方法查準(zhǔn)率的變化。與NHSM、ACOS和SPCC方法相比，PSJ方法的查準(zhǔn)率提升比較明顯；當(dāng)k=10時，Jaccard和JMSD方法的查準(zhǔn)率與PSJ方法很接近；當(dāng)k>20時，NHSM方法獲得了比SPCC、JMSD和ACOS方法更好的查準(zhǔn)率，而PSJ方法能獲得最好的查準(zhǔn)率。

圖3展現(xiàn)的是當(dāng)Top-k中k變化時不同方法查全率的變化。與ACOS和SPCC方法相比，PSJ方法的查全率提升明顯；當(dāng)k=10時，Jaccard、JMSD和NHSM方法的查全率與PSJ方法很接近；當(dāng)k>20時，NHSM方法獲得了比SPCC、JMSD和ACOS方法更好的查全率，而PSJ方法獲得了最好的查全率。

圖2和圖3的實驗結(jié)果表明，PSJ方法考慮的各種因素對提升推薦效果是有效的。

3.2.3最近鄰居數(shù)量

本節(jié)實驗將推薦物品數(shù)量設(shè)為定值50，最近鄰居數(shù)從10到70變化。

圖4展現(xiàn)的是當(dāng)最近鄰居數(shù)變化時不同方法查準(zhǔn)率的變化。在整個實驗過程中，PSJ方法能獲得最高的查準(zhǔn)率，與其他五種協(xié)同過濾方法相比，PSJ方法的查準(zhǔn)率提升較為明顯。當(dāng)最近鄰居數(shù)大于20時，除了ACOS方法外，其他方法的查準(zhǔn)率都比較穩(wěn)定；當(dāng)最近鄰居數(shù)在10～20時，ACOS方法的查準(zhǔn)率下降很快，這是用戶相似度計算偏差太大造成的。

圖5展現(xiàn)的是當(dāng)最近鄰居數(shù)變化時不同方法查全率的變化。與查準(zhǔn)率實驗結(jié)果一樣，PSJ方法能獲得最高的查全率，與其他五種協(xié)同過濾方法相比，PSJ方法的查全率提升較為明顯。

圖4和圖5的實驗結(jié)果表明，PSJ方法在實驗情景下與其他方法相比，其推薦效果也有明顯提升。

3.2.4不同算法的計算時間

本節(jié)通過用戶用戶相似度矩陣的計算時間來對比PSJ算法與其他五種相似度算法。表2展示的是各個算法計算了35次用戶用戶相似度矩陣的平均計算時間。從表2的數(shù)據(jù)中可以發(fā)現(xiàn)，PSJ方法與NHSM方法相比計算時間縮短了9.85%，但與其他四種相似度算法的計算時間仍有差距，繼續(xù)降低PSJ算法的復(fù)雜度仍然很有必要。

綜合以上兩組實驗的實驗結(jié)果，從兩個不同情景說明了PSJ方法的有效性，其查準(zhǔn)率與查全率與對比的五種協(xié)同過濾方法相比有不同幅度的提升；同時在實驗中還對比了PSJ方法與其他五種方法計算用戶用戶相似度矩陣的平均計算時間，這些實驗結(jié)果說明了PSJ仍然需要降低復(fù)雜度。

4結(jié)語

本文介紹了協(xié)同過濾推薦方法中使用的相似度計算方法，并在綜合了這些相似度計算方法的優(yōu)點之后，提出了PSJ方法的設(shè)計思路，并給出了PSJ方法的計算公式。PSJ方法是基于NHSM方法的改進(jìn)方法，并且在設(shè)計時考慮到了數(shù)據(jù)稀疏狀況對產(chǎn)生推薦結(jié)果的影響。它簡化了NHSM方法的Proximity因子的計算，將NHSM方法的Significance因子和URP因子合并組成了自己的Significance因子。通過這兩步簡化，使得PSJ方法的計算復(fù)雜度相較于NHSM方法明顯降低。在PSJ方法的討論中，通過一個用戶物品評分矩陣的例子驗證了PSJ方法在相似度計算方面的準(zhǔn)確性。在MovieLens的ml-latest-small數(shù)據(jù)集上對比實驗結(jié)果驗證了PSJ方法的有效性，結(jié)果表明，與對比的協(xié)同過濾方法相比，PSJ方法可以有效提升推薦效果，同時在一定程度上克服了數(shù)據(jù)稀疏情況對推薦效果的影響。然而，在更為稀疏的數(shù)據(jù)集上推薦效果如何，以及如何改進(jìn)是下一步需要深入研究的內(nèi)容。

參考文獻(xiàn)：

[1]YANG X， GUO Y， LIU Y， et al. A survey of collaborative filtering based social recommender systems [J]. Computer Communications， 2014， 41： 1-10.

[2]CACHEDA F， CARNEIRO V， FERNNDEZ D， et al. Comparison of collaborative filtering algorithms： limitations of current techniques and proposals for scalable， high-performance recommender systems [J]. ACM Transactions on the Web， 2011， 5（1）： Article No. 2.

[3]KOUTRIKA G， BERCOVITZ B， GARCIA-MOLINA H. FlexRecs： expressing and combining flexible recommendations [C]// SIGMOD 09： Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2009： 745-758.

[4]ADOMAVICIUS G， TUZHILIN A. Toward the next generation of recommender systems： a survey of the state-of-the-art and possible extensions [J]. IEEE Transactions on Knowledge and Data Engineering， 2005， 17（6）： 734-749.

[5]RESNICK P， IACOVOU N， SUCHAK M， et al. GroupLens： an open architecture for collaborative filtering of netnews [C]// CSCW 94： Proceedings of the ACM Conference on Computer Supported Cooperative Work. New York： ACM， 1994： 175-186.

[6]AHN H J. A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem [J]. Information Sciences， 2008， 178（1）： 37-51.

[7]PATRA B K， LAUNONEN R， OLLIKAINEN V， et al. A new similarity measure using Bhattacharyya coefficient for collaborative filtering in sparse data [J]. Knowledge-Based Systems， 2015， 82： 163-177.

[8]JAMALI M， ESTER M. TrustWalker： a random walk model for combining trust-based and item-based recommendation [C]// KDD 09： Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 397-406.

[9]BOBADILLA J， HERNANDO A， ORTEGA F， et al. Collaborative filtering based on significances [J]. Information Sciences， 2012， 185（1）： 1-17.

[10]BOBADILLA J， SERRADILLA F， BERNAL J. A new collaborative filtering metric that improves the behavior of recommender systems [J]. Knowledge-Based Systems， 2010， 23（6）： 520-528.

[11]LIU H， HU Z， MIAN A， et al. A new user similarity model to improve the accuracy of collaborative filtering [J]. Knowledge-Based Systems， 2014， 56： 156-166.

[12]BOBADILLA J， ORTEGA F， HERNANDO A， et al. A collaborative filtering approach to mitigate the new user cold start problem [J]. Knowledge-Based Systems， 2011， 26： 225-238.

[13]ANAND D， BHARADWAJ K K. Utilizing various sparsity measures for enhancing accuracy of collaborative recommender systems based on local and global similarities [J]. Expert Systems with Applications， 2011， 38（5）： 5101-5109.

[14]CREMONESI P， KOREN Y， TURRIN R. Performance of recommender algorithms on top-n recommendation tasks [C]// RecSys 10： Proceedings of the fourth ACM conference on Recommender Systems. New York： ACM， 2010： 39-46.

[15]FOUSS F， PIROTTE A， RENDERS J-M， et al. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation [J]. IEEE Transactions on Knowledge and Data Engineering， 2007， 19（3）： 355-369.

[16]YU S J. The dynamic competitive recommendation algorithm in social network services [J]. Information Sciences： an International Journal， 2012， 187： 1-14.