基于組合優化理論的協同過濾推薦算法

楊麗麗+袁浩浩

摘 要： 針對傳統推薦系統中的協同過濾推薦算法無法解決數據間的高度稀疏問題，采用余弦相似性度量運算的物品相似性誤差較高，導致系統推薦質量降低，提出基于局部組合優化的協同過濾推薦算法，其改進了物品間相似性的運算，為了解決數據稀疏性問題，選擇目標的近鄰對象時利用局部優化方法選擇推薦群，降低了預測的誤差，確保誤差值收斂到某固定值，并采用基于內容的方法調整協同過濾預測存在的異常預測結果。實驗結果表明，所提算法抑制了數據稀疏性的不利影響，提高了協同過濾預測評分的準確度。

關鍵詞： 局部； 組合優化理論； 協同過濾； 推薦算法； 稀疏問題； 評分精度

中圖分類號： TN911.1?34； TP391 文獻標識碼： A 文章編號： 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 引 言

隨著互聯網、信息技術的快速發展，信息呈現爆炸式增長，用戶從海量信息中快速、準確檢索到有價值資源的難度逐漸增加。因此，個性化推薦系統的發展逐漸引起人們的關注[1]。

個性化推薦系統中應用性最高的推薦技術是協同過濾推薦算法，其基于用戶以往的行為偏好，獲取用戶間的相似度，將同目標用戶興趣最相似的用戶作為臨近鄰居集，分析鄰居用戶的行為偏好，獲取預測目標用戶對物品的偏好情況。傳統推薦算法無法解決數據間的高度稀疏問題，采用余弦相似性度量運算的物品相似性誤差較高，導致預測的誤差大幅度增加。

為了解決該問題，本文提出基于局部組合優化的協同過濾推薦算法，以提高協同過濾預測評分的準確度。

1 基于組合優化的協同過濾推薦算法

1.1 問題的提出

數據稀疏性問題廣泛存在于個性化推薦系統中，電子商務網站中包含了海量的用戶和商品，用戶無法對全部的物品實施準確評價。若采用傳統協同過濾算法，通過相似性度量獲取物品間的相似性[2]，能夠完成用戶對物品偏好度的評分，但是該種算法會受到高度稀疏數據集的干擾，使得推薦質量大大降低。針對傳統算法無法處理數據稀疏性問題，可采用改進相似度運算方法對其實施改進。相似性的兩個改進方法，公式如下：

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

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

式中：[γ]參數用于描述調節參數，基于實際數據集明確該參數的取值范圍；[cos（i，j）]是余弦相似性，對向量而言，式（1），式（2）中主要為物品間關系，可轉化為向量表示。

采用式（1）和式（2）描述的兩種改進相似性運算方法可提高評分預測的準確度，然而在數據高度稀疏時，這兩種改進算法的優化效果不明顯。因此，面向上述分析問題，本文基于局部組合優化的協同過濾推薦算法，先對項目間的相似性運算實施優化，再采用局部優化方法選擇對象當成推薦群，并通過基于內容的方法調整協同過濾預測評分包含的部分異常[3]，提升推薦系統的質量。

1.2 優化物品間相似性運算公式

如果數據存在高度稀疏性特征，在傳統協同過濾算法對物品相似性實施運算的過程中，兩個物品被同時評分的用戶數量大大降低，使得物品相似性運算存在顯著的隨機特征。為了減少該種隨機特征產生的干擾，本文采用物品的評分相似性同物品的特征屬性相似性的線性加權方法運算物品間的相似性，如式（3）所示：endprint

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

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

1.3 局部優化選擇近鄰對象

傳統協同過濾過程是在全部推薦物品群內，采用[k]個相似性最高的物品，若采用的相鄰個數[k]過高，則會使得推薦結果精度降低，無法提高推薦系統的質量。本文提出的基于局部優化選擇的組合推薦算法，設置最小閾值[δ，]通過局部優化方法選擇預測目標[4]，確保近鄰集中物品數量最小化。采取的局部優化運算公式如下：

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

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

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

式中：[ni，j=I]，因為當共同評分物品數量高于50時，預測的誤差向平穩趨勢靠近。

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

1.4 基于內容調整異常預測評分

系統過濾預測評分時，如果數據呈現高度稀疏狀態，則將導致用戶對項目的評分數大大降低，出現預測評分異常，導致系統預測誤差的大幅度上升[5]。因此，本文通過基于內容的方法對異常預測評分進行調整，詳細的過程如下：

1） 基于內容的預測過程

基于內容的預測方法采用式（6）獲取項目[i]對于物品特征[t]的權重：

[wi，t=1，項目i有屬性特征t0，項目i沒有屬性特征t] （6）

采用式（7），用0～1的值描述用戶對于項目的某種物品特征的興趣度：

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

式中：[r（t）]是用戶[u]對具有特征[t]的全部項目總的評分；[r（u）]是用戶[u]全部評分的總和；[ta]表示用戶[u]對存在特征[t]的項目進行評價的數量；[tb]表示用戶[u]評價的全部項目數；[wu，t]表示用戶[u]對物品特征[t]的感興趣度；約束因子[11+ct]用于降低熱門項目特征的權重[6]，[ct]用于描述特征[t]在全部特征中所占的權重。

式（6）能得到各項目的特征權重向量[V，]式（7）能夠運算各用戶的歷史興趣特征權重，得到用戶特征權重向量[U。]則依據內容的評分預測表達式為：

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

式中：[sim（ui，vj）]是采用余弦相似性公式運算得到的；[hj]表示當前項目[j]被評分的用戶數的權重。根據式（9）計算[hj，]從而得到基于內容預測的準確度。

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

式中：[η]是常量；[nj]用于描述項目[j]被評分的用戶數量。

2） 調整評分預測方法

協同過濾算法自身存在的缺陷，會使得用戶對項目的評分數量較少，預測的分數會大大減小，容易產生異常的預測評分現象[7]。面對該現象，本文提出新的評分預測表達式：

[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）

分析上述描述的協同過濾預測評分過程可得，協同過濾預測獲取的異常結果為[Ru，n<β，][Ru，n]為特征值，通過基于內容的預測[R′u，n]對該異常結果實施調整，其中[β]是常量。

3） 拉普拉斯平滑方法

概率統計過程中的拉普拉斯平滑也就是加平滑，用于處理數學系數在統計領域中的零概率問題。數據集中包括小規模的項目特征，基于項目特征矩陣進行特征的余弦相似性運算時，會產生大量的零值關系，此時基于相似性屬性，能夠看出兩種項目間相互獨立。但是實際預測過程中，無法獲取兩個項目間的不確定關系[8]。因此，采用拉普拉斯平滑方法進行改進，項目特征屬性運算相似性表達式為：

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

式中：[ti，][tj]是用于描述項目[i，j]的特征向量；[k]是相關聯項目的數量，本文設置其值是10。

基于式（11）可以看出，在拉普拉斯方法運算原始項目屬性矩陣過程中，無需進行繁瑣的操作，就能夠高效率地運算出項目間的相似性，具有較高的運算效率。

2 實驗結果與分析

2.1 實驗數據

本文實驗分析的數據集是MovieLens，將該數據集中的832個用戶對1 489部電影的8 000條評分記錄作為實驗數據集。同時將實驗數據集中的75%當成訓練集，其余的25%當成測試集。實驗數據集內存在16種全部電影的特征輸入，如愛情、劇情、恐怖等。通過預測評分和用戶實際評分間的偏差，也就是通過平均絕對誤差MAE（Mean Absolute Error）對本文算法預測評分的準確度進行檢測。

2.2 實驗結果分析

2.2.1 參數[β]的最優取值

過高稀疏性的數據會導致訓練集內用戶評分的項目記錄過低，存在共同評分項目的用戶數十分少，用戶間的相似度很小，使得協同過濾預測分數中存在異常評分。本文算法采用基于內容的方法對異常評分進行調整，實驗設置本文算法的預測評分score<[β]時產生異常評分。在數據集MovieLens中，1～5分用于描述不同用戶可選擇的評分區域，1用于描述很差，5用于描述很好。用戶采用差異分數描述自身對已看電影的偏好程度。實驗設置[β]取[0.0，0.20，0.40，0.60，0.80，0.85，0.90，1.10，1.30，1.50]，設置鄰居個數為[N=20，]實驗結果用圖1描述。endprint

分析圖1可得，如果[β]值是0.9，則當預測評分低于0.9時，采用基于內容的推薦法調整異常預測評分，本文算法可有效減少預測的誤差。

2.2.2 異常預測評分結果的數目

實驗采用本文算法預測不同的測試數據集的評分score，其中，[k]為預測用戶相關系數，異常預測評分結果（score<0.9與score≤0）的數量，用表1和圖2描述。

圖2 5個MovieLens 100K的數據集內異常的預測評分結果個數

Fig. 2 Number of abnormal prediction scores of 100K

5 MovieLens datasets

分析表1和圖2能夠得出，本文算法預測評分低于0.9的異常結果在總體檢測過程中存在的平均次數是97.2次，預測評分不高于0的異常結果的平均出現次數是61.6次。說明本文算法可有效預測出異常評分結果，為后續的預測評分優化提供有利基礎，提升總體協同過濾推薦的準確度。

2.2.3 不同算法的MAE值對比

實驗對比分析本文算法、線性組合LCCF算法和填充偽評分CBCF算法的MAE值[9]，結果用表2和圖3描述。分析表2和圖3可得，當[N]值低于10時，各種算法的預測質量將大大降低；而當[N]值高于10時，各算法的預測質量逐步提升。但是本文算法的MAE值低于其他兩種算法，可有效增強預測的精度，降低數據稀疏性產生的不利干擾，并且隨著[N]值的不斷提升，本文算法的預測準確度趨于穩定。

3 結 論

本文針對傳統協同過濾推薦算法無法解決數據間的高度稀疏問題，存在預測評分精度低的問題，提出基于局部組合優化的協同過濾推薦算法，實現協同過濾預測評分精度的提高。

參考文獻

[1] 田保軍，胡培培，杜曉娟，等.Hadoop下基于聚類協同過濾推薦算法優化的研究[J].計算機工程與科學，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] 張學錢，林世平，郭昆.協同過濾推薦算法對比分析與優化應用[J].計算機系統應用，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] 祝曉斌，蔡強，白璐，等.一種基于標簽和協同過濾的并行推薦算法[J].高技術通訊，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] 劉濤.基于二叉樹偏碼匿名亂序的云平臺協同計算研究[J].科技通報，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] 王興茂，張興明，鄔江興.基于一跳信任模型的協同過濾推薦算法[J].通信學報，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].科學技術與工程，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] 周國強，金禮仁，張文聰，等.基于用戶影響力和個性的協同過濾推薦算法[J].計算機應用，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云平臺下的基于用戶協同過濾算法研究[J].計算機測量與控制，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.