基于標(biāo)簽和共評比例改進(jìn)的推薦算法*

林鵬飛 王 遜 黃樹成

（江蘇科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院 鎮(zhèn)江 212003）

1 引言

推薦算法是推薦系統(tǒng)中的重要組成部分。推薦算法主要分為基于內(nèi)容的推薦［1］、基于協(xié)同過濾的推薦［2］以及基于混合推薦［3～5］三大類。協(xié)同過濾算法在科學(xué)研究和現(xiàn)實商業(yè)系統(tǒng)中均取得了大量的成績和使用。然而協(xié)同過濾算法存在評價數(shù)據(jù)不足、推薦精度低等問題［6］。

上述協(xié)同過濾算法存在的問題，大批科研工作者和工程師提出了許多治理方案。例如，曹占偉等［7］提出了一種基于LDA 主題模型的矩陣分解推薦算法，該算法在相似度計算中引入了KL散度，提高了相似度度量［8］精度，減少了推薦誤差。陳潔敏等［9］提出經(jīng)過用戶興趣構(gòu)建的標(biāo)簽集合來發(fā)掘用戶的興趣分布，進(jìn)而計算用戶的相似度。Sun B等［10］提出了一個概率模型來尋找用戶標(biāo)注的標(biāo)簽和位置的偏好關(guān)鍵字之間的映射，并使用輔助上下文數(shù)據(jù)信息來解決數(shù)據(jù)稀疏性的問題。上述的方法提高了計算的精確性，但仍存在不足之處。只考慮了用戶評分和用戶標(biāo)注信息，忽略了項目本身存在的類別信息與用戶之間潛在的關(guān)聯(lián)關(guān)系。Aliannejadi M 等［11］提出了一個概率模型來尋找用戶標(biāo)注的標(biāo)簽和位置的偏好關(guān)鍵字之間的映射，并使用輔助上下文數(shù)據(jù)信息來解決數(shù)據(jù)稀疏性的問題。Sun J 等［12］提出了一種新的多方面用戶興趣模型，引入產(chǎn)品的總體用戶滿意度，通過從多個方面的評論計算用戶興趣級別來構(gòu)建用戶興趣概要。建立了領(lǐng)域情感詞典，克服了正負(fù)詞在數(shù)量上的差距，用于情感極性分析。并設(shè)計了用戶情感傾向性和傾向性的情感分析模型，提高了推薦精度和推薦質(zhì)量。以上方法卻沒有考慮用戶興趣的公平性與用戶共評比例的關(guān)聯(lián)。

因此，基于以上兩個因素，本文提出基于標(biāo)簽和共評比例改進(jìn)的推薦算法。通過分析用戶評分矩陣的高度稀疏性，利用標(biāo)簽進(jìn)行彌補(bǔ)稀疏的措施，標(biāo)簽信息一定程度上代表著用戶的偏好，具有優(yōu)良的可解釋性。配合兩用戶評分項目的數(shù)量和共同評分的項目比例因素，使得用戶相似性的計算更符合實際。

2 傳統(tǒng)的相似度計算方法

2.1 余弦相似度

余弦相似度［13］最初用于二維空間中兩個向量的夾角值計算，例如向量=(a，b)和向量=(c，d)，向量表示當(dāng)前坐標(biāo)（a，b）與原點坐標(biāo)（0，0）形成的直線關(guān)系，同理，向量表示當(dāng)前坐標(biāo)（c，d）與原點坐標(biāo)（0，0）形成的直線關(guān)系。則余弦相似度計算的就是向量與這兩條直線的夾角值，表示當(dāng)前它根據(jù)二維向量之間的角度來度量它們之間的相似性。兩條直線的角度值越小則兩個向量越相似，反之則差異越大。余弦相似度的公式如式（1）所示：

其中，余弦相似性度量值的范圍在［-1，1］之間，-1則表示向量完全不相似，1 則表示向量完全相似，0表示向量正交或向量不相關(guān)，而中間值則表示兩向量的相似度級別。向量和通常是文檔的詞頻向量。余弦相似度常用于正值空間，因此范圍常在［0，1］之間。

余弦相似度通過向量空間中兩個向量夾角的余弦值來度量兩個個體之間的差異，因此，該方法注意的是兩個向量在方向上的差異，而不是距離或者長度上的差異。兩個向量越相似，角度越小，余弦值越大。但是僅考慮角度大小會有一定的局限性，只能分辨?zhèn)€體在角向量維度的差異，無法從數(shù)值上進(jìn)行測度。

2.2 皮爾遜相關(guān)系數(shù)

在統(tǒng)計學(xué)中，Pearson 相關(guān)系數(shù)（Pcc）［14］是衡量兩組數(shù)據(jù)之間線性相關(guān)性的指標(biāo)，該相關(guān)系數(shù)表示為兩個變量之間協(xié)方差與其標(biāo)準(zhǔn)差的乘積之比。因此，本質(zhì)上是對協(xié)方差進(jìn)行了歸一化的計算，使得結(jié)果的值域始終保持在［-1，1］，相關(guān)系數(shù)取值在-1和1之間。與協(xié)方差本身一樣，該度量只能反映變量的線性相關(guān)性，而忽略了許多其他類型的關(guān)系或相關(guān)性。

協(xié)方差：設(shè)置兩個隨機(jī)變量X和Y，協(xié)方差用于衡量這兩個變量的總體誤差，表示的是兩個變量總體誤差的期望。計算方式如式（2）所示：

標(biāo)準(zhǔn)差：標(biāo)準(zhǔn)差是一組數(shù)值自平均值分散開來的程度的一種測量觀念。一個較大的標(biāo)準(zhǔn)差，代表大部分的數(shù)值和其平均值之間差異較大；一個較小的標(biāo)準(zhǔn)差，代表這些數(shù)值較接近平均值。計算方法如式（3）所示：

根據(jù)式（2）和式（3），皮爾遜相關(guān)系數(shù)公式如式（4）所示：

也可表示為式（5）：

其中，皮爾森相關(guān)系數(shù)的變化范圍為［-1，1］。系數(shù)的值為1意味著x和y可以很好地由直線方程式來描述，所有的數(shù)據(jù)點都很好地落在一條直線上，且y隨著x的增加而增加。系數(shù)的值為-1 意味著所有的數(shù)據(jù)點都落在直線上，且y隨著x的增加而減少。系數(shù)的值為0 意味著兩個變數(shù)之間沒有線性關(guān)系。

2.3 Jaccard系數(shù)

Jaccard 系數(shù)主要應(yīng)用場景為數(shù)據(jù)聚類、比較文本的相似度，用于文本的查重與去重，計算對象間的距離。Jaccard 系數(shù)考慮了共項的問題。這種方法的原則是具有共同評分的項目的用戶可能有相似的興趣愛好。Jaccard 系數(shù)能夠量度有限樣本集合的相似度，其定義為兩個集合交集大小與并集大小之間的比例，如式（6）所示：

其中，如果A與B的集和完全重合，則定義Sim(A，B)J=1，于是有0 ＜Sim(A，B)J＜1。Jaccard系數(shù)值越大，樣本相似度越高，反之則越低。

3 基于標(biāo)簽偏好的相似度改進(jìn)算法

3.1 全局興趣模型

通常，在傳統(tǒng)的協(xié)同過濾算法中，評分值通常表示用戶對某項產(chǎn)品的偏好程度。而在本節(jié)中，所提出的方法利用項目類別來表達(dá)這種偏好。此處將描述構(gòu)建全局興趣模型的三個主要步驟。例如，使用ML 數(shù)據(jù)集來解釋這些步驟。ML 數(shù)據(jù)集有18種類別的電影，如動作、犯罪、喜劇、紀(jì)錄片等。每一部電影至少可以屬于一種或多種類別。用戶對電影的所有評分都被用來建立用戶的全局偏好。該過程用三個子過程表達(dá)，如下所示。

用戶-項目評分矩陣：我們定義U表示數(shù)據(jù)集中n個用戶的集合，I表示為數(shù)據(jù)集中m個項目的集合，并且在區(qū)間［Min，…，Max］評分維度內(nèi)，用戶對項目進(jìn)行評分。在該矩陣中，這些行表示同一個用戶對不同項目的評分信息。同樣，這些列表示不同用戶對同一個項目的評分信息。因此，矩陣中行列單元格的唯一交集，將由表示用戶u對項目i的評分的值來進(jìn)行填充，其中沒有評分的單元格的值，將用符號*來表示，如表1所示。

表1 用戶-評分矩陣

用戶-標(biāo)簽頻次矩陣：讓我們進(jìn)行以下假設(shè)。在電子商務(wù)中，用戶根據(jù)顏色、款式、品牌等類型購買商品。因此，我們可以說，他們的偏好可能取決于這種行為（他們購買的類型）。類似地，ML 數(shù)據(jù)集電影項目被劃分為有限個類別。因此，喜歡看紀(jì)錄片的用戶會比其他人更喜歡看這種類型的電影。為了解釋這一步驟，我們假設(shè)是表示電影j的類別信息的向量，向量具體表示為是該數(shù)據(jù)集中電影類型的總數(shù)。其中，如果項目j屬于對應(yīng)g類別，那么的值為1 否則為0。該矩陣的值將表示為ti，g，具體表示為用戶i評分過的屬于類別g的電影數(shù)量。ti，g值的計算表達(dá)式為此處，Ii是用戶i選擇的電影集。表示屬于類別g的電影j的貢獻(xiàn)值，如表2所示。

表2 用戶-標(biāo)簽頻次矩陣

歸一化矩陣：對用戶-標(biāo)簽頻次類型矩陣進(jìn)行歸一化，將評分計數(shù)值轉(zhuǎn)換為0 與1 之間的比值。為了在比較過程中保持標(biāo)準(zhǔn)化，將進(jìn)行標(biāo)準(zhǔn)化處理。在相似度計算過程中，將使用歸一化的值來表示用戶的全局偏好。例如向量表示用戶i的類別信息，其中=(ti，1，ti.2，…，ti，g，…，ti，k-1，ti，k)。如表3 所示。因此，在向量空間模型中，用戶對每個類別的偏好通過用戶標(biāo)簽頻次歸一化矩陣表示。其中歸一化值wi，g表示用戶i對類別g的偏愛值，可以使用表示，其中k是數(shù)據(jù)集中項目類別的數(shù)量。接下來，采用歸一化矩陣作為主要輸入來定義所改進(jìn)的相似度計算方法。

表3 歸一化矩陣

相似度度量需要計算一對用戶之間的相關(guān)性。在本節(jié)中，皮爾遜相關(guān)系數(shù)和余弦相似度的計算將分別根據(jù)歸一化矩陣數(shù)據(jù)，采用公平因子和共同評分的項目比例兩個因素的調(diào)整方式。

3.2 公平因子

在本研究中，公平性因子可以定義為目標(biāo)用戶評分的項目數(shù)量與兩個用戶所取項目數(shù)量的比例。首先，將公平因子應(yīng)用到提出的相似度度量公式上，使其更加準(zhǔn)確。一對評分相近的用戶之間的相關(guān)性應(yīng)該比其他用戶更強(qiáng)。例如，用戶u是目標(biāo)用戶，則|Iu|就是用戶u總的評分項目數(shù)量。與此同時，v是被比較用戶，則|Iv|是用戶v總的評分項目數(shù)量。因此，每個用戶的公平因子（Ff）可定義為如式（7）所示：

其中，F(xiàn)f(u，v)為用戶u相對于用戶v的公平權(quán)重，并且Ff(u，v)為用戶v相對于用戶u的公平權(quán)重。

3.3 Sigmoid函數(shù)

在計算用戶之間的相似性時，還應(yīng)考慮具有共同評分的項目比例對相似度計算的影響。一般來說，兩個用戶評分項目集合中，兩集合的交集的項目數(shù)量占兩用戶所有項目并集數(shù)量上的比例越大，這兩個用戶在某種程度上就越相似。此外，如果Sim(u，v)=Sim(u，l)相似度的值相同的情況下，可以通過其他方式再次確定相似度。例如，用戶u與用戶v之間共同評分的項目數(shù)多于用戶u和用戶l。 那么很顯然即使Sim(u，v)=Sim(u，l) ，那Sim(u，v)的效用也要比Sim(u，l)的效用要更強(qiáng)。

為了解決這種問題，在此處將使用Sigmoid 函數(shù)［15］來降低相似度的權(quán)重，如式（8）所示。當(dāng)我們計算兩個用戶之間的相似度時，兩個用戶的評分之間的差異越小，用戶之間的相似度就越高。選擇Sigmoid 函數(shù)具有以下優(yōu)點：1）相似度可以限制在［0，1］的范圍內(nèi)，這便于與其他算法或自身進(jìn)行比較。2）Sigmoid 函數(shù)可以擴(kuò)大函數(shù)差的大小，擴(kuò)大相似值，也可以抑制負(fù)面因素。

分母θ用來限制共同評分項的最小長度。如果公共項目集的大小等于或者大于閾值θ，那么Sigmoid 權(quán)重將大于0.9。例如，如果θ的值為1 并且共同評分項目數(shù)量為0，此時Sigmoid函數(shù)值則為0.5。但是，如果共同評分的項目數(shù)量為3，那么Sigmoid 函數(shù)值將會大于0.95。Sigmoid 函數(shù)公式（Sf）可按照以下方式計算：

其中Sf(u，v)=Sf(v，u)并且|Iu，v|表示用戶u和用戶v的共同項目評分?jǐn)?shù)量。

表4 給出了各種初始測試分母值的描述及其對Sigmoid值的相應(yīng)影響。

表4 Sigmoid參數(shù)影響表

3.4 改進(jìn)的相似度計算方法

如上節(jié)所述，為了解決數(shù)據(jù)稀疏導(dǎo)致的推薦精度較低的問題［16～18］，基于歸一化矩陣呈現(xiàn)的全局偏好并采用上述的兩種因素進(jìn)行改進(jìn)，則用戶之間的相似性可以分別定義為改進(jìn)的基于皮爾森的相似度計算方法（IPcc）和改進(jìn)的基于余弦相似度（ICos）的計算方法。改進(jìn)公式如式（9）與式（10）所示：

在制定相似性度量公式之后，將計算數(shù)據(jù)集中用戶之間的相似度，以確定目標(biāo)用戶的最相似的用戶集合。與目標(biāo)用戶具有較高相似度的用戶將被定義為鄰居。調(diào)整后的加權(quán)方法用于計算用戶對每個鄰居項目的預(yù)測分?jǐn)?shù)。式（11）將用于計算預(yù)測評分。

其中，Pu，i表示用戶u對項目i的預(yù)測評分，N為用戶u的近鄰集。

4 實驗設(shè)計與分析

4.1 實驗數(shù)據(jù)集

協(xié)同過濾算法向用戶提供一個推薦列表，其中有n個未評級的項目。為了評估本節(jié)模型的有效性，我們使用MovieLens 數(shù)據(jù)集進(jìn)行驗證。我們選擇ML-100k 數(shù)據(jù)集，它由943 個用戶對1682 部電影的10 萬條評級記錄組成。在數(shù)據(jù)集中，每個用戶至少被評級20 部電影，評級范圍是1～5，每個用戶可以將電影評級為1、2、3、4、5。用戶對電影的評價越高，用戶對電影就越感興趣。數(shù)據(jù)集的稀疏度可計算為1-100000/（943*1682）=0.936953。采用5-交叉驗證方法［19］，將數(shù)據(jù)集分割為五個等比例子集。分別前四份子集為訓(xùn)練數(shù)據(jù)集，最后的一份子集作為測試數(shù)據(jù)集。不斷調(diào)整訓(xùn)練集和測試集的比例，計算結(jié)果取平均值作為最終實驗結(jié)果。

4.2 實驗評價標(biāo)準(zhǔn)

預(yù)測準(zhǔn)確率是目前推薦系統(tǒng)研究中討論最多的屬性。在實驗過程中，我們選擇了四個評價指標(biāo)來評價推薦質(zhì)量，分別是MAE、Recall、Precision、F1-measure［20］。我們希望預(yù)測用戶對目標(biāo)項目的評分，因此采用了度量評分預(yù)測的準(zhǔn)確性。MAE是評級預(yù)測中最常用的評估指標(biāo)。較小的值意味著預(yù)測分?jǐn)?shù)更準(zhǔn)確。通過計算預(yù)測額定值與實際額定值之間的差值獲得。式（12）如下所示：

其中N表示項目的數(shù)量，rm，i表示預(yù)測的評分值，表示用戶m在項目i上的實際評分值。

為了更好地評估算法的準(zhǔn)確性，我們使用了召回率和準(zhǔn)確度評估指標(biāo)。我們?yōu)橛脩舳x預(yù)測的推薦項目，并在測試集中投票給實際的推薦列表。召回率和準(zhǔn)確度公式如下：

準(zhǔn)確度和召回率是相互影響的。理想情況下，兩者都可以達(dá)到最佳值，但一般來說，準(zhǔn)確度較高，召回率較低，準(zhǔn)確度較低，召回率較高。F1-Measure 是準(zhǔn)確度和召回率的加權(quán)調(diào)和平均值，因此選擇F1-Measure 作為評價指標(biāo)，可以更直接地比較推薦的準(zhǔn)確度。F1-Measure 越大，則推薦精度越高，定義如下：

4.3 實驗結(jié)果分析

4.3.1θ的選擇

由于一對用戶之間的相似度在計算時包含兩用戶之間共同評分項目的比例，因此，需要增加或減少兩用戶之間相似度權(quán)重的共同評分項的量級的影響。Sigmoid 函數(shù)的使用取決于分母θ的值。為此，進(jìn)行了多次實驗，以確定合適的分母值θ，以提高相似度測度，并得到可接受的結(jié)果。

表4 描述了各種初始測試分母值及其對Sigmoid 函數(shù)的影響。圖1 表示使用MovieLens 100K的MAE 率。近鄰數(shù)量有30、50、70、100 和150 個。當(dāng)鄰域數(shù)增加時，可以觀察到MAE 值略有改善。同樣，當(dāng)分母增加時，MAE 值增加。綜上所述，當(dāng)所有分母值中鄰域的大小為150時，MAE值是可接受的。此外，當(dāng)分母等于13時，MAE率最低。當(dāng)分母θ為9時，MAE率接近最佳值。

圖1 ICos算法關(guān)于θ 的MAE

4.3.2 改進(jìn)的算法比較

皮爾遜相關(guān)系數(shù)（Pcc）、余弦相似度（Cos）、Jaccard 系數(shù)作為最常見的用于傳統(tǒng)協(xié)同過濾算法中的相似度計算方法。IPcc 和ICos 分別表示本文提出的基于皮爾遜相關(guān)系數(shù)和余弦相似度的改進(jìn)計算方法。

圖2 顯示了本文所提出的改進(jìn)方法與Pcc、Cos和Jaccard系數(shù)相比下MAE的比較結(jié)果。最近鄰居的大小以橫軸表示，大小各不相同，從大到小分別為30、50、70、100、150，縱軸表示MAE 的值。當(dāng)鄰居數(shù)量增加時，MAE 大小會隨之降低。如圖所示，所提出的方法相較于其他方法具有明顯的減小MAE 的作用，它們的MAE 值最低。表示提出的方法符合實際情況，也明顯表現(xiàn)出IPcc和ICos方法提高了計算的精確率。

圖2 MAE與鄰居數(shù)量的關(guān)系

圖3 顯示了本文所提出的改進(jìn)方法與Pcc、Cos、Jaccard 系數(shù)相比下召回率的比較結(jié)果。總的來說，對于所有的相似度計算方法，當(dāng)項目推薦數(shù)為50 時，推薦率逐漸上升，達(dá)到最高?？梢钥闯觯琁Pcc 和ICos 的召回率在所有算推薦中排最高。綜上所述，召回率隨著推薦條目數(shù)量的增加而提高。

圖3 Recall與鄰居數(shù)量的關(guān)系

圖4 顯示了本文所提出的改進(jìn)方法與Pcc、Cos、Jaccard 系數(shù)相比下精確率的比較結(jié)果。由圖可知，所有計算方法的準(zhǔn)確率都從推薦數(shù)為10 的初始點開始下降，在推薦數(shù)為50 時達(dá)到最低。從圖中可以看出，所提出的方法的準(zhǔn)確率是相比于其他方法仍然是效果最好的。

圖4 Precision與鄰居數(shù)量的關(guān)系

圖5 顯示了本文所提出的改進(jìn)方法與Pcc、Cos、Jaccard 系數(shù)相比下F1 的比較結(jié)果。從圖中可以觀察到，對于所有的相似度計算方法，當(dāng)推薦項目的大小為10～30 之間時，從初始點開始，所有方法的F1 值都有顯著上升。然而，在此之后，在接下來的兩個推薦長度內(nèi)，該指數(shù)略有上升。因此，與Pcc、Cos 和Jaccard 系數(shù)相比，IPcc 和ICos 改進(jìn)計算方法的F1值總體最好。

圖5 F1與鄰居數(shù)量的關(guān)系

5 結(jié)語

在協(xié)同過濾算法中，定位最相似的鄰居是提高準(zhǔn)確率的關(guān)鍵步驟。因此，關(guān)鍵的一步是如何構(gòu)造一個合適的相似性度量方法。然而，大多數(shù)的相似性度量方法仍然面臨數(shù)據(jù)稀疏性的負(fù)面影響進(jìn)而導(dǎo)致計算值誤差較大的問題。本文對現(xiàn)有的幾種相似性度量方法進(jìn)行了改進(jìn)，提出了一種利用用戶全局偏好的相似性度量方法來解決這一問題。然后，偏好值被用作所提出的相似性度量方法的輸入數(shù)據(jù)。因此，即使一對用戶沒有共同的項目，也會計算它們之間的相關(guān)性。此外，在提出的方法中，采用公平因子和共同評價項比例兩個因素，對提高推薦的準(zhǔn)確性有積極的影響。實驗結(jié)果表明，該方法解決了數(shù)據(jù)稀疏性問題，提高了精度。與傳統(tǒng)協(xié)同過濾相似性度量方法相比，本文的改進(jìn)方法使用通用評價指標(biāo)（MAE、Recall、Precision和F1）并提高了準(zhǔn)確率。然而算法未考慮偏好在時間維度的特性，這是以后改進(jìn)的關(guān)鍵點之一。