基于組合優(yōu)化理論的協(xié)同過(guò)濾推薦算法

楊麗麗+袁浩浩

摘 要： 針對(duì)傳統(tǒng)推薦系統(tǒng)中的協(xié)同過(guò)濾推薦算法無(wú)法解決數(shù)據(jù)間的高度稀疏問(wèn)題，采用余弦相似性度量運(yùn)算的物品相似性誤差較高，導(dǎo)致系統(tǒng)推薦質(zhì)量降低，提出基于局部組合優(yōu)化的協(xié)同過(guò)濾推薦算法，其改進(jìn)了物品間相似性的運(yùn)算，為了解決數(shù)據(jù)稀疏性問(wèn)題，選擇目標(biāo)的近鄰對(duì)象時(shí)利用局部?jī)?yōu)化方法選擇推薦群，降低了預(yù)測(cè)的誤差，確保誤差值收斂到某固定值，并采用基于內(nèi)容的方法調(diào)整協(xié)同過(guò)濾預(yù)測(cè)存在的異常預(yù)測(cè)結(jié)果。實(shí)驗(yàn)結(jié)果表明，所提算法抑制了數(shù)據(jù)稀疏性的不利影響，提高了協(xié)同過(guò)濾預(yù)測(cè)評(píng)分的準(zhǔn)確度。

關(guān)鍵詞： 局部； 組合優(yōu)化理論； 協(xié)同過(guò)濾； 推薦算法； 稀疏問(wèn)題； 評(píng)分精度

中圖分類(lèi)號(hào)： TN911.1?34； TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）01?0139?04

Abstract： The collaborative filtering recommended algorithm in the traditional recommended system can′t solve the high sparsity among data. The cosine similarity measurement used to calculate the similarity of objects has big error， which may cause the low recommendation quality of the system. Therefore， a collaborative filtering algorithm based on local combinatorial optimization is proposed to improve the calculation of similarity among items. In order to reduce the data sparsity， the local combinatorial optimization method is adopted to select the recommended group for the object near the selected objective to reduce the prediction error and guarantee the error converging to a fixed value. The content?based method is used to adjust the abnormal prediction results of collaborative filtering prediction. The experimental results show that the algorithm can suppress the adverse effects of data sparsity， and improve the scoring accuracy of collaborative filtering prediction.

Keywords： local； combinatorial optimization theory； collaborative filtering； recommended algorithm； sparse problem； scoring accuracy

0 引 言

隨著互聯(lián)網(wǎng)、信息技術(shù)的快速發(fā)展，信息呈現(xiàn)爆炸式增長(zhǎng)，用戶(hù)從海量信息中快速、準(zhǔn)確檢索到有價(jià)值資源的難度逐漸增加。因此，個(gè)性化推薦系統(tǒng)的發(fā)展逐漸引起人們的關(guān)注[1]。

個(gè)性化推薦系統(tǒng)中應(yīng)用性最高的推薦技術(shù)是協(xié)同過(guò)濾推薦算法，其基于用戶(hù)以往的行為偏好，獲取用戶(hù)間的相似度，將同目標(biāo)用戶(hù)興趣最相似的用戶(hù)作為臨近鄰居集，分析鄰居用戶(hù)的行為偏好，獲取預(yù)測(cè)目標(biāo)用戶(hù)對(duì)物品的偏好情況。傳統(tǒng)推薦算法無(wú)法解決數(shù)據(jù)間的高度稀疏問(wèn)題，采用余弦相似性度量運(yùn)算的物品相似性誤差較高，導(dǎo)致預(yù)測(cè)的誤差大幅度增加。

為了解決該問(wèn)題，本文提出基于局部組合優(yōu)化的協(xié)同過(guò)濾推薦算法，以提高協(xié)同過(guò)濾預(yù)測(cè)評(píng)分的準(zhǔn)確度。

1 基于組合優(yōu)化的協(xié)同過(guò)濾推薦算法

1.1 問(wèn)題的提出

數(shù)據(jù)稀疏性問(wèn)題廣泛存在于個(gè)性化推薦系統(tǒng)中，電子商務(wù)網(wǎng)站中包含了海量的用戶(hù)和商品，用戶(hù)無(wú)法對(duì)全部的物品實(shí)施準(zhǔn)確評(píng)價(jià)。若采用傳統(tǒng)協(xié)同過(guò)濾算法，通過(guò)相似性度量獲取物品間的相似性[2]，能夠完成用戶(hù)對(duì)物品偏好度的評(píng)分，但是該種算法會(huì)受到高度稀疏數(shù)據(jù)集的干擾，使得推薦質(zhì)量大大降低。針對(duì)傳統(tǒng)算法無(wú)法處理數(shù)據(jù)稀疏性問(wèn)題，可采用改進(jìn)相似度運(yùn)算方法對(duì)其實(shí)施改進(jìn)。相似性的兩個(gè)改進(jìn)方法，公式如下：

[sim（i，j）=min（Ui?Uj，γ）γ×cos（i，j）] （1）

[sim（i，j）=max（Ui?Uj，γ）γ×cos（i，j）] （2）

式中：[γ]參數(shù)用于描述調(diào)節(jié)參數(shù)，基于實(shí)際數(shù)據(jù)集明確該參數(shù)的取值范圍；[cos（i，j）]是余弦相似性，對(duì)向量而言，式（1），式（2）中主要為物品間關(guān)系，可轉(zhuǎn)化為向量表示。

采用式（1）和式（2）描述的兩種改進(jìn)相似性運(yùn)算方法可提高評(píng)分預(yù)測(cè)的準(zhǔn)確度，然而在數(shù)據(jù)高度稀疏時(shí)，這兩種改進(jìn)算法的優(yōu)化效果不明顯。因此，面向上述分析問(wèn)題，本文基于局部組合優(yōu)化的協(xié)同過(guò)濾推薦算法，先對(duì)項(xiàng)目間的相似性運(yùn)算實(shí)施優(yōu)化，再采用局部?jī)?yōu)化方法選擇對(duì)象當(dāng)成推薦群，并通過(guò)基于內(nèi)容的方法調(diào)整協(xié)同過(guò)濾預(yù)測(cè)評(píng)分包含的部分異常[3]，提升推薦系統(tǒng)的質(zhì)量。

1.2 優(yōu)化物品間相似性運(yùn)算公式

如果數(shù)據(jù)存在高度稀疏性特征，在傳統(tǒng)協(xié)同過(guò)濾算法對(duì)物品相似性實(shí)施運(yùn)算的過(guò)程中，兩個(gè)物品被同時(shí)評(píng)分的用戶(hù)數(shù)量大大降低，使得物品相似性運(yùn)算存在顯著的隨機(jī)特征。為了減少該種隨機(jī)特征產(chǎn)生的干擾，本文采用物品的評(píng)分相似性同物品的特征屬性相似性的線性加權(quán)方法運(yùn)算物品間的相似性，如式（3）所示：endprint

[sim′（i，j）=θsim（i，j）+（1-θ）simT（i，j）] （3）

式中：[θ]是常量；[simT（i，j）]用于描述物品的特征屬性相似性。

1.3 局部?jī)?yōu)化選擇近鄰對(duì)象

傳統(tǒng)協(xié)同過(guò)濾過(guò)程是在全部推薦物品群內(nèi)，采用[k]個(gè)相似性最高的物品，若采用的相鄰個(gè)數(shù)[k]過(guò)高，則會(huì)使得推薦結(jié)果精度降低，無(wú)法提高推薦系統(tǒng)的質(zhì)量。本文提出的基于局部?jī)?yōu)化選擇的組合推薦算法，設(shè)置最小閾值[δ，]通過(guò)局部?jī)?yōu)化方法選擇預(yù)測(cè)目標(biāo)[4]，確保近鄰集中物品數(shù)量最小化。采取的局部?jī)?yōu)化運(yùn)算公式如下：

[sgi，j*sim′（i，j）>δ] （4）

式中：[δ]是常量，設(shè)置的相似度閾值如果過(guò)高，會(huì)使得覆蓋率過(guò)低；[sgij]描述重要性權(quán)重因子，其靠近存在更多一致評(píng)分物品的對(duì)等者。真實(shí)狀態(tài)中出現(xiàn)兩個(gè)用戶(hù)評(píng)分混合的現(xiàn)象較少，為了解決相似性度量存在的隨機(jī)特征的不利影響，用[I=Ii?Ij]描述物品[Ii]以及[Ij]被共同評(píng)分的用戶(hù)集，用[λ]描述閾值，采用式（5）對(duì)比分析閾值同項(xiàng)目[Ii]以及[Ij]被共同評(píng)分的用戶(hù)數(shù)[ni，j]：

[sgi，j=ni，jλ，ni，j<λ1，其他] （5）

式中：[ni，j=I]，因?yàn)楫?dāng)共同評(píng)分物品數(shù)量高于50時(shí)，預(yù)測(cè)的誤差向平穩(wěn)趨勢(shì)靠近。

該方法通過(guò)局部的相似性使得總體預(yù)測(cè)誤差MAE大大降低，并且確保預(yù)測(cè)誤差收斂于某固定值。

1.4 基于內(nèi)容調(diào)整異常預(yù)測(cè)評(píng)分

系統(tǒng)過(guò)濾預(yù)測(cè)評(píng)分時(shí)，如果數(shù)據(jù)呈現(xiàn)高度稀疏狀態(tài)，則將導(dǎo)致用戶(hù)對(duì)項(xiàng)目的評(píng)分?jǐn)?shù)大大降低，出現(xiàn)預(yù)測(cè)評(píng)分異常，導(dǎo)致系統(tǒng)預(yù)測(cè)誤差的大幅度上升[5]。因此，本文通過(guò)基于內(nèi)容的方法對(duì)異常預(yù)測(cè)評(píng)分進(jìn)行調(diào)整，詳細(xì)的過(guò)程如下：

1） 基于內(nèi)容的預(yù)測(cè)過(guò)程

基于內(nèi)容的預(yù)測(cè)方法采用式（6）獲取項(xiàng)目[i]對(duì)于物品特征[t]的權(quán)重：

[wi，t=1，項(xiàng)目i有屬性特征t0，項(xiàng)目i沒(méi)有屬性特征t] （6）

采用式（7），用0～1的值描述用戶(hù)對(duì)于項(xiàng)目的某種物品特征的興趣度：

[wu，t=r（t）tar（u）tb*11+ct] （7）

式中：[r（t）]是用戶(hù)[u]對(duì)具有特征[t]的全部項(xiàng)目總的評(píng)分；[r（u）]是用戶(hù)[u]全部評(píng)分的總和；[ta]表示用戶(hù)[u]對(duì)存在特征[t]的項(xiàng)目進(jìn)行評(píng)價(jià)的數(shù)量；[tb]表示用戶(hù)[u]評(píng)價(jià)的全部項(xiàng)目數(shù)；[wu，t]表示用戶(hù)[u]對(duì)物品特征[t]的感興趣度；約束因子[11+ct]用于降低熱門(mén)項(xiàng)目特征的權(quán)重[6]，[ct]用于描述特征[t]在全部特征中所占的權(quán)重。

式（6）能得到各項(xiàng)目的特征權(quán)重向量[V，]式（7）能夠運(yùn)算各用戶(hù)的歷史興趣特征權(quán)重，得到用戶(hù)特征權(quán)重向量[U。]則依據(jù)內(nèi)容的評(píng)分預(yù)測(cè)表達(dá)式為：

[R′i，j=hj*5*sim（ui，vj）] （8）

式中：[sim（ui，vj）]是采用余弦相似性公式運(yùn)算得到的；[hj]表示當(dāng)前項(xiàng)目[j]被評(píng)分的用戶(hù)數(shù)的權(quán)重。根據(jù)式（9）計(jì)算[hj，]從而得到基于內(nèi)容預(yù)測(cè)的準(zhǔn)確度。

[hj=njη，nj>η1，其他] （9）

式中：[η]是常量；[nj]用于描述項(xiàng)目[j]被評(píng)分的用戶(hù)數(shù)量。

2） 調(diào)整評(píng)分預(yù)測(cè)方法

協(xié)同過(guò)濾算法自身存在的缺陷，會(huì)使得用戶(hù)對(duì)項(xiàng)目的評(píng)分?jǐn)?shù)量較少，預(yù)測(cè)的分?jǐn)?shù)會(huì)大大減小，容易產(chǎn)生異常的預(yù)測(cè)評(píng)分現(xiàn)象[7]。面對(duì)該現(xiàn)象，本文提出新的評(píng)分預(yù)測(cè)表達(dá)式：

[Ru，t=σ*R′u，n+（1-σ）Ru，n，Ru，n<βRt+n∈S（Jj）sim（t，n）*（Ru，n-Rn）n∈S（Jj）sim（t，n），others] （10）

分析上述描述的協(xié)同過(guò)濾預(yù)測(cè)評(píng)分過(guò)程可得，協(xié)同過(guò)濾預(yù)測(cè)獲取的異常結(jié)果為[Ru，n<β，][Ru，n]為特征值，通過(guò)基于內(nèi)容的預(yù)測(cè)[R′u，n]對(duì)該異常結(jié)果實(shí)施調(diào)整，其中[β]是常量。

3） 拉普拉斯平滑方法

概率統(tǒng)計(jì)過(guò)程中的拉普拉斯平滑也就是加平滑，用于處理數(shù)學(xué)系數(shù)在統(tǒng)計(jì)領(lǐng)域中的零概率問(wèn)題。數(shù)據(jù)集中包括小規(guī)模的項(xiàng)目特征，基于項(xiàng)目特征矩陣進(jìn)行特征的余弦相似性運(yùn)算時(shí)，會(huì)產(chǎn)生大量的零值關(guān)系，此時(shí)基于相似性屬性，能夠看出兩種項(xiàng)目間相互獨(dú)立。但是實(shí)際預(yù)測(cè)過(guò)程中，無(wú)法獲取兩個(gè)項(xiàng)目間的不確定關(guān)系[8]。因此，采用拉普拉斯平滑方法進(jìn)行改進(jìn)，項(xiàng)目特征屬性運(yùn)算相似性表達(dá)式為：

[simt（i，j）=ti?tj+1ti?tj+k] （11）

式中：[ti，][tj]是用于描述項(xiàng)目[i，j]的特征向量；[k]是相關(guān)聯(lián)項(xiàng)目的數(shù)量，本文設(shè)置其值是10。

基于式（11）可以看出，在拉普拉斯方法運(yùn)算原始項(xiàng)目屬性矩陣過(guò)程中，無(wú)需進(jìn)行繁瑣的操作，就能夠高效率地運(yùn)算出項(xiàng)目間的相似性，具有較高的運(yùn)算效率。

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

2.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)分析的數(shù)據(jù)集是MovieLens，將該數(shù)據(jù)集中的832個(gè)用戶(hù)對(duì)1 489部電影的8 000條評(píng)分記錄作為實(shí)驗(yàn)數(shù)據(jù)集。同時(shí)將實(shí)驗(yàn)數(shù)據(jù)集中的75%當(dāng)成訓(xùn)練集，其余的25%當(dāng)成測(cè)試集。實(shí)驗(yàn)數(shù)據(jù)集內(nèi)存在16種全部電影的特征輸入，如愛(ài)情、劇情、恐怖等。通過(guò)預(yù)測(cè)評(píng)分和用戶(hù)實(shí)際評(píng)分間的偏差，也就是通過(guò)平均絕對(duì)誤差MAE（Mean Absolute Error）對(duì)本文算法預(yù)測(cè)評(píng)分的準(zhǔn)確度進(jìn)行檢測(cè)。

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

2.2.1 參數(shù)[β]的最優(yōu)取值

過(guò)高稀疏性的數(shù)據(jù)會(huì)導(dǎo)致訓(xùn)練集內(nèi)用戶(hù)評(píng)分的項(xiàng)目記錄過(guò)低，存在共同評(píng)分項(xiàng)目的用戶(hù)數(shù)十分少，用戶(hù)間的相似度很小，使得協(xié)同過(guò)濾預(yù)測(cè)分?jǐn)?shù)中存在異常評(píng)分。本文算法采用基于內(nèi)容的方法對(duì)異常評(píng)分進(jìn)行調(diào)整，實(shí)驗(yàn)設(shè)置本文算法的預(yù)測(cè)評(píng)分score<[β]時(shí)產(chǎn)生異常評(píng)分。在數(shù)據(jù)集MovieLens中，1～5分用于描述不同用戶(hù)可選擇的評(píng)分區(qū)域，1用于描述很差，5用于描述很好。用戶(hù)采用差異分?jǐn)?shù)描述自身對(duì)已看電影的偏好程度。實(shí)驗(yàn)設(shè)置[β]取[0.0，0.20，0.40，0.60，0.80，0.85，0.90，1.10，1.30，1.50]，設(shè)置鄰居個(gè)數(shù)為[N=20，]實(shí)驗(yàn)結(jié)果用圖1描述。endprint

分析圖1可得，如果[β]值是0.9，則當(dāng)預(yù)測(cè)評(píng)分低于0.9時(shí)，采用基于內(nèi)容的推薦法調(diào)整異常預(yù)測(cè)評(píng)分，本文算法可有效減少預(yù)測(cè)的誤差。

2.2.2 異常預(yù)測(cè)評(píng)分結(jié)果的數(shù)目

實(shí)驗(yàn)采用本文算法預(yù)測(cè)不同的測(cè)試數(shù)據(jù)集的評(píng)分score，其中，[k]為預(yù)測(cè)用戶(hù)相關(guān)系數(shù)，異常預(yù)測(cè)評(píng)分結(jié)果（score<0.9與score≤0）的數(shù)量，用表1和圖2描述。

圖2 5個(gè)MovieLens 100K的數(shù)據(jù)集內(nèi)異常的預(yù)測(cè)評(píng)分結(jié)果個(gè)數(shù)

Fig. 2 Number of abnormal prediction scores of 100K

5 MovieLens datasets

分析表1和圖2能夠得出，本文算法預(yù)測(cè)評(píng)分低于0.9的異常結(jié)果在總體檢測(cè)過(guò)程中存在的平均次數(shù)是97.2次，預(yù)測(cè)評(píng)分不高于0的異常結(jié)果的平均出現(xiàn)次數(shù)是61.6次。說(shuō)明本文算法可有效預(yù)測(cè)出異常評(píng)分結(jié)果，為后續(xù)的預(yù)測(cè)評(píng)分優(yōu)化提供有利基礎(chǔ)，提升總體協(xié)同過(guò)濾推薦的準(zhǔn)確度。

2.2.3 不同算法的MAE值對(duì)比

實(shí)驗(yàn)對(duì)比分析本文算法、線性組合LCCF算法和填充偽評(píng)分CBCF算法的MAE值[9]，結(jié)果用表2和圖3描述。分析表2和圖3可得，當(dāng)[N]值低于10時(shí)，各種算法的預(yù)測(cè)質(zhì)量將大大降低；而當(dāng)[N]值高于10時(shí)，各算法的預(yù)測(cè)質(zhì)量逐步提升。但是本文算法的MAE值低于其他兩種算法，可有效增強(qiáng)預(yù)測(cè)的精度，降低數(shù)據(jù)稀疏性產(chǎn)生的不利干擾，并且隨著[N]值的不斷提升，本文算法的預(yù)測(cè)準(zhǔn)確度趨于穩(wěn)定。

3 結(jié) 論

本文針對(duì)傳統(tǒng)協(xié)同過(guò)濾推薦算法無(wú)法解決數(shù)據(jù)間的高度稀疏問(wèn)題，存在預(yù)測(cè)評(píng)分精度低的問(wèn)題，提出基于局部組合優(yōu)化的協(xié)同過(guò)濾推薦算法，實(shí)現(xiàn)協(xié)同過(guò)濾預(yù)測(cè)評(píng)分精度的提高。

參考文獻(xiàn)

[1] 田保軍，胡培培，杜曉娟，等.Hadoop下基于聚類(lèi)協(xié)同過(guò)濾推薦算法優(yōu)化的研究[J].計(jì)算機(jī)工程與科學(xué)，2016，38（8）：1615?1624.

TIAN Baojun， HU Peipei， DU Xiaojuan， et al. Optimization of the collaborative filtering recommendation algorithm based on clustering under Hadoop [J]. Computer engineering and science， 2016， 38（8）： 1615?1624.

[2] 張學(xué)錢(qián)，林世平，郭昆.協(xié)同過(guò)濾推薦算法對(duì)比分析與優(yōu)化應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2015，24（5）：100?105.

ZHANG Xueqian， LIN Shiping， GUO Kun. Collaborative filte?ring recommendation algorithm analysis and optimization applications [J]. Computer systems & applications， 2015， 24（5）： 100?105.

[3] 祝曉斌，蔡強(qiáng)，白璐，等.一種基于標(biāo)簽和協(xié)同過(guò)濾的并行推薦算法[J].高技術(shù)通訊，2015，25（3）：307?312.

ZHU Xiaobin， CAI Qiang， BAI Lu， et al. A parallel recommendation algorithm based on tagging and collaborative filte?ring [J]. Chinese high technology letters， 2015， 25（3）： 307?312.

[4] 劉濤.基于二叉樹(shù)偏碼匿名亂序的云平臺(tái)協(xié)同計(jì)算研究[J].科技通報(bào)，2016，32（7）：167?171.

LIU Tao. Cloud platform collaborative computing research based on binary tree partial code anonymous out?of?order [J]. Bulletin of science and technology， 2016， 32（7）： 167?171.

[5] 王興茂，張興明，鄔江興.基于一跳信任模型的協(xié)同過(guò)濾推薦算法[J].通信學(xué)報(bào)，2015（6）：193?200.

WANG Xingmao， ZHANG Xingming， WU Jiangxing. Collabo?rative filtering recommendation algorithm based on one?jump trust model [J]. Journal on communications， 2015（6）： 193?200.

[6] 馬胡雙，石永革，高勝保.基于特征增益與多級(jí)優(yōu)化的協(xié)同過(guò)濾個(gè)性化推薦算法[J].科學(xué)技術(shù)與工程，2016，16（21）：272?277.

MA Hushuang， SHI Yongge， GAO Shengbao. A recommendation algorithm based on collaborative filtering by feature augmentation and cascade tactics [J]. Science technology and engineering， 2016， 16（21）： 272?277.

[7] 周?chē)?guó)強(qiáng)，金禮仁，張文聰，等.基于用戶(hù)影響力和個(gè)性的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)應(yīng)用，2016，36（z1）：63?66.

ZHOU Guoqiang， JIN Liren， ZHANG Wencong， et al. Colla?borative filtering recommendation algorithm based on user inf?luence [J]. Journal of computer applications， 2016， 36（z1）： 63?66.

[8] WANG Jianian， XIAN Xiaobing. Multi?node cooperative transmission of data collection protocols for wireless sensor networks [J]. Computer simulation， 2014， 31（9）： 339?342.

[9] 趙偉，李俊鋒，韓英，等.Hadoop云平臺(tái)下的基于用戶(hù)協(xié)同過(guò)濾算法研究[J].計(jì)算機(jī)測(cè)量與控制，2015，23（6）：2082?2085.

ZHAO Wei， LI Junfeng， HAN Ying， et al. Research on user?based collaborative filtering algorithm on Hadoop platform [J]. Computer measurement & control， 2015， 23（6）： 2082?2085.