融合用戶自然最近鄰的協同過濾推薦算法

王　穎，王　欣，唐萬梅

WANG Ying,WANG Xin,TANG Wanmei

重慶師范大學 計算機與信息科學學院，重慶 401331

College of Computer and Information Science,Chongqing Normal University,Chongqing 401331,China

1　引言

互聯網技術、設備和網絡資源的逐步發展和日趨豐富使人們的日常生活與Internet的關系愈來愈密不可分。CNNIC報告顯示，我國網民數量截至2016年6月已達7.10億[1]。網絡信息過載和信息迷航等問題成為眾網民獲取想要信息以及得到個性化推薦的需求無法滿足的主要原因，這種情況下，推薦系統通過分析用戶行為，向不同用戶提供更準確的個性化推薦越來越迫切。

推薦系統作為一種基于用戶網絡行為信息向用戶提供與其行為相關信息的信息預測與交付系統[2-5]，目前已被廣泛應用于電影、音樂、閱讀、電商、廣告、社交網絡、新聞媒體、基于地理位置的推薦、個性化郵件等多個領域[6]。作為推薦系統最普遍采用的算法，基于用戶近鄰的協同過濾推薦的基本原理是通過尋找與目標用戶興趣相似的用戶集合即近鄰用戶，向目標用戶推薦近鄰用戶喜歡且目標用戶未評分過的物品。如，某推薦系統中存在任意用戶A及與其興趣相似的鄰居用戶B、C、D，假設B、C、D用戶看過電影《阿甘正傳》且對該電影評分較高，而A用戶未看過《阿甘正傳》，則推薦系統根據A和B、C、D的鄰居關系，向A推薦《阿甘正傳》這部電影。任何推薦都應該伴隨合理的推薦解釋，即為何這樣推薦[7-8]，而基于用戶近鄰推薦，具有較強解釋性。此外，基于用戶近鄰的推薦具有實現相對簡單，可解釋性強，高效、穩定等顯著的優越性[9]。目前常用的近鄰方法有：KNN、K-means、K-d Trees、LSH等。

傳統的KNN使用預先固定的K值，沒有充分利用數據集的重要信息，如訓練集中每個樣例的維數大小[10]。進行推薦時，固定的K值會使目標用戶偏向訓練集中擁有較多評分的用戶，結果造成傾向于向目標用戶推薦擁有較多評分的鄰居喜歡的項目。選取不同K值會造成推薦結果具有不確定性，且得到最優K值通常需要迭代方法，計算量較大，通常采用off-line的方式進行。而K-d Tree面臨的維數災難降低了算法的有效性。相關學者紛紛提出對基于K近鄰推薦算法的改進方法，如羅辛等[11]提出一種通過相似度支持度優化K近鄰模型的方法，選擇合理規模的K近鄰，保持推薦精度前提下降低計算的復雜度。考慮到用戶近鄰的分布不均勻和對分類貢獻的不同以及避免僅由評分決定K近鄰帶來的片面性，尹航等[12]提出了用各個樣本與其所屬類別的類別關聯度來區分對待待預測用戶的K個最近鄰居，達到提高推薦精度的目的。黃創光等[13]提出了一種不確定近鄰的協同過濾推薦算法（Uncertain Neighbors Collaborative Filtering，UNCF），根據用戶及產品的相似性自適應地獲取目標用戶近鄰作為推薦群，在推薦群基礎上得到目標用戶的信任子群，再使用一種不確定近鄰因子度量推薦結果。更多文獻是從相似度的角度進行優化，利用用戶的多種信息如評分值和共同評分項目的個數等進行改進，并一定程度上提高了推薦準確度[14-15]。以上方法雖然一定程度上提高了推薦效果，但存在以下不足：（1）都是通過分析目標用戶尋找近鄰，而忽略了鄰居用戶的分析，形成一種不對稱的鄰居關系。（2）沒有充分利用隱藏鄰居用戶的信息。（3）都是在選擇近鄰前通過聚類或設置相似度閾值u、v篩選鄰居，或者選出K近鄰后通過貢獻度、相似度、類別關聯度等改進鄰居關系，算法涉及近鄰數K、相似度閾值u和v、聚類的類別關聯度等多個參數，參數設置不同對推薦結果有影響。

自然最近鄰概念于2011年首先由Zou等[16]提出，這是一種去參數的、對稱的鄰居關系，考慮到了空間分布疏密程度對近鄰個數和鄰居對稱關系的影響，簡單且容易實現，目前已經被改進和應用到多方面[17-19]，尤其在聚類、分類和離群點檢測等方面表現頗佳。本文在此基礎上，提出一種融合用戶自然最近鄰的協同過濾算法（Collaborative Filtering recommendation integrating user-centric Natural Nearest Neighbor，CF3N）。本文算法試圖在K近鄰的基礎上，去參數K，自適應地獲取目標用戶的自然近鄰集合。在評分預測時充分考慮到鄰居用戶對評分預測的貢獻，將目標用戶關于目標項目的活躍鄰居集合與自然最近鄰用戶集合融合后形成推薦鄰居集合，并根據推薦鄰居集合預測評分，計算RMSE和MAE值得到評分預測的準確度。通過在MovieLens數據集上進行仿真實驗，驗證本文算法在復雜程度和推薦準確度方面較傳統基于K近鄰的協同過濾推薦算法具有一定的優越性。

2　傳統的基于近鄰的協同過濾算法

傳統的基于近鄰的協同過濾算法分為基于用戶近鄰的協同過濾推薦和基于項目近鄰的協同過濾推薦兩個方面。目前，大多數推薦系統使用的是基于項目近鄰的推薦算法，如Netflix、Amazon等網站，因為該方法更注重用戶的歷史興趣且推薦系統中用戶總數往往大于項目總數，從存儲角度來看更有優勢，但對于個性化不太明顯且項目更新較快或數量龐大的領域則不太適合。傳統的基于用戶近鄰的協同過濾具有更長的發展歷史，第一個郵件過濾系統Tapestry、Digg網站的個性化閱讀、GroupLens的個性化新聞推薦都是使用的該方法，因為新聞、文章、圖書更新速度快且數量遠超用戶數，人們對于“新”的需求超過了對“個性化”的需求，此時該方法在存儲代價、推薦速度、實現的難易程度等方面具有更強的優勢。此外，實際應用中基于用戶近鄰的協同過濾方法相比基于項目近鄰的協同過濾在推薦結果的召回率、覆蓋率、新穎度等方面表現更優[6]。雖然該方法在解決用戶冷啟動問題時表現不佳，但仍然具有獨特的優勢和較強的應用價值。

傳統的基于用戶近鄰的推薦算法主要工作包含：（1）建立用戶-項目評分矩陣；（2）計算用戶之間關于評分的相似度；（3）建立用戶-用戶相似度矩陣；（4）尋找與目標用戶最相似的鄰居對目標用戶進行評分預測；（5）計算評分預測的準確度。具體步驟如下。

2.1　建立用戶-項目評分矩陣

假設推薦系統中存在m個用戶，n個項目，用戶集合表示為U={user1,user2,…,userm}，項目集合表示為I={item1,item2,…,itemn}，評分矩陣表示為 R=[r1,1,r1,2,…,r1,n;r2,1,r2,2,…,r2,n;…,rm,1,rm,2,…,rm,n]，其中 R 矩陣中評分值范圍在1～5之間（0表示無評分），建立如下用戶-項目（User-Item）評分矩陣（如表1）。

表1　用戶-項目評分矩陣

2.2　根據評分值計算用戶之間相似度

傳統的基于用戶近鄰推薦算法采用的相似度計算方法主要有以下幾種：

（1）Cosine相似度

余弦相似度（公式（1））表示目標用戶u及其鄰居用戶v的評分向量之間的夾角余弦值，余弦相似度的范圍值在[－1，1]區間，1表示兩個用戶完全相似，0表示兩用戶相互獨立，－1則表示兩用戶完全不相似。

（2）Pearson相似度

Pearson相似度（公式（2））取值在[－1，1]之間，負數表示兩用戶負相關，正數表示兩用戶正相關，0表示兩用戶不相關。其中，Iuv表示目標用戶u和鄰居用戶v共同評分過的項目集合，rui表示用戶u對項目i的評分，表示用戶u對所有評分過的項目的評分均值。

（3）Jaccard相似度

Jaccard相似度（公式（3））表示集合 Γ(u)和 Γ(v)中相同元素個數除以Γ(u)和Γ(v)并集中的元素個數，其范圍在[0，1]之間。Jaccard相似度適合兩極評價，如音樂評價中判斷用戶是否收藏了歌曲，用戶u和v收藏的歌曲的交集除以并集，得到的Jaccard相似值可以反映兩用戶的相似度。而不適合多級評價，如1～5分5個等級的評價方式。

2.3　尋找目標用戶u的K近鄰集合

假設推薦系統中用戶的興趣是相對穩定的，且興趣越相似的用戶越傾向于喜歡相同的項目。把用戶集合U中的用戶按照與目標用戶的相似度由大到小即Sim值降序排序，Sim值越大表示該用戶與目標用戶興趣越相似，則該用戶越有可能與目標用戶喜歡相同的項目。找出Sim值最大的前K個用戶，即與目標用戶最相似的或最近的K個鄰居，這K個用戶組成目標用戶u的K近鄰集合Neighbor(u)。其中，目標用戶的鄰居個數K值大小是由算法設計者自主選取，不同的K值對推薦結果準確性有影響。

2.4　對目標用戶u進行評分預測

根據目標用戶的鄰居即集合Neighbor(u)中用戶的評分值和相似度，預測目標用戶u對目標項目i的評分，評分預測公式（公式（4））如下：

2.5　推薦結果準確性評測

目前，推薦算法的評測指標主要從用戶、物品、時間三個維度進行，包括用戶滿意度、預測準確度、覆蓋率、多樣性、新穎性、驚喜度、信任度、實時性、健壯性、商業目標是否達成等多個指標[6]，然而預測準確度依然是協同過濾最重要的指標[9]。預測準確性又包含評分預測準確性方面的平均絕對誤差（MAE）和均方根誤差（RMSE）兩個指標。

3　融合用戶自然最近鄰的協同過濾推薦

傳統的基于用戶K近鄰的協同過濾推薦算法通過計算用戶相似度再按照相似度值由大到小把鄰居排序后，直接選取與目標用戶距離最近的K個用戶作為目標用戶的鄰居集合，沒有考慮到鄰居的對稱性且K值的選取方法不同對評分預測結果的準確性影響較大。常用方法是選擇特定步長，計算不同K值下的用戶評分預測結果及其準確性，直到推薦準確率達到設定的閾值為止。而這種方法無疑計算量較大，實現起來相對復雜，且準確率不高。

本文著眼于用戶近鄰集合的選擇，充分考慮到傳統基于用戶K近鄰的協同過濾推薦算法以上所述不足之處，提出了一種融合用戶自然最近鄰的協同過濾推薦算法。在確定推薦鄰居集合時，首先找到目標用戶u的自然最近鄰居集合（定義1）NaturalNearestNeighbor(u)和目標用戶u關于項目i的活躍用戶集合（定義2）ActiveNeighbor(u,i)，將二者融合后的結果作為待預測用戶u關于項目i的推薦鄰居集合RecommendNeighbor(u,i)，根據推薦鄰居集合預測目標用戶u的評分r?(ui)。本文推薦算法流程如圖1所示。

圖1　CF3N算法流程圖

3.1　前提工作

CF3N是一種新的改進的基于用戶近鄰的推薦算法，該算法中用戶近鄰個數不需要提前設置好，而是在算法過程中自適應生成。可以將任意用戶u看作空間里的一個點，推薦系統中存在的大量用戶U構成一個點空間，空間中兩個用戶距離越近則相似度Sim值越大，稱這兩個用戶的興趣偏好越相似。不難理解，空間分布密集區域的用戶群具有更多的自然最近鄰居，分布稀疏區域的用戶具有較少的自然最近鄰居。

假設有給定的用戶集合U={user1,user2,…,userm}，用戶u，v∈U ，項目集合I={item1,item2,…,itemn}，項目 i∈I。用戶的評分矩陣表示為 ScoreMatrix（m×n）=

u和v的相似度，Simu,v的值越大則表明用戶u和v對項目（如電影）的品味越相近。按照相似度值由大到小排序后，得到鄰居矩陣 NeighborMatrix（m×(m-1)）=

3.2　獲取推薦鄰居集合RecommendNeighbor(u,i)

在向目標用戶u推薦時選擇的鄰居個數隨用戶分布疏密程度有所不同，即NaturalNearestNeighboradpt_r(u)集合的大小與u所處空間用戶疏密程度呈正相關。因為現實中的推薦系統數據稀疏度往往會高達90%以上，在預測目標用戶u對目標項目i的評分時，其自然最近鄰NaturalNearestNeighboradpt_r(u)中的鄰居用戶并非全部都是活躍用戶，非活躍用戶在評分預測中所起作用不大，此時采用融入活躍用戶集合的方法，把NaturalNearestNeighboradpt_r(u)和 ActiveNeighbor(u,i)融合后的結果作為評分預測時使用的鄰居集合Recommend-Neighbor(u,i)，具體步驟如下。

3.2.1獲取正最近鄰用戶集合NearestNeighborr(u)

對于推薦系統中的用戶空間U，依次尋找所有用戶的第一正最近鄰、第二正最近鄰……直到U中的每個用戶都出現在其他用戶的正最近鄰集合里時，共進行了r次查詢，即每個用戶的第r正最近鄰居。此時，得到的用戶u的r近鄰集合則為用戶u的正最近鄰集合。尋找正最近鄰算法如下（CodeⅠ）：

可知，r∈[1,m-1]，當存在一個用戶離群比較遠時，即該用戶是其他每一個用戶的最遠鄰居時，最壞情況下需要查詢m-1次后才滿足終止條件“每個用戶都是其他用戶的正最近鄰”，會造成算法的搜索長度大大增加，這種情況下可以設置一個閾值?∈(0,1)，當r＞?·m時即停止搜索。

3.2.2獲取逆最近鄰用戶集合ReverseNearestNeighboradpt_r(u)

CF3N協同過濾推薦算法選擇用戶近鄰時，考慮到的鄰居關系是一種對稱關系的鄰居，如目標用戶u有r個正最近鄰，若反過來用戶u出現在其r個鄰居的正最近鄰集合中至少一次，則才能構成對稱的鄰居關系。尋找目標用戶u的逆最近鄰用戶算法如下（CodeⅡ）：

3.2.3獲取自然最近鄰用戶的集合NaturalNearest-Neighboradpt_r(u)

定義1（用戶u的自然最近鄰居集合）已知目標用戶u的正最近鄰用戶集NearestNeighborr(u)，以及用戶u的逆最近鄰用戶集ReverseNearestNeighboradpt_r(u)，若存在任意用戶v，滿足v∈NearestNeighborr(u)?Reverse-NearestNeighboradpt_r(u)，稱用戶v為用戶u的自然最近鄰[17]。

確定用戶的正最近鄰用戶集NearestNeighborr(u)和逆最近鄰用戶集ReverseNearestNeighboradpt_r(u)后，可通過計算兩個集合的交集得到用戶的自然最近鄰居集合NaturalNearestNeighboradpt_r(u)。自然最近鄰居集合避免了傳統基于K近鄰算法只考慮鄰居用戶興趣而忽略了分析目標用戶興趣的缺點。鄰居用戶的興趣和目標用戶u相近，同時目標用戶u的興趣與其鄰居用戶興趣相似時，得到的才是全面的、對稱鄰居關系的用戶集合。用戶u的自然最近鄰居集合（定義1），操作過程如下（CodeⅢ）：

3.2.4獲取用戶u關于項目i的活躍鄰居用戶集合ActiveNeighbor(u，i)

定義2（用戶u關于項目i的活躍鄰居用戶集）已知目標用戶u的鄰居集合NeighborMatrix(u)，任意用戶m∈NeighborMatrix(u)，如果rm,i≠0，則稱用戶m為用戶u關于項目i的活躍鄰居用戶。滿足rm,i≠0的用戶集合則為用戶u關于項目i的活躍鄰居用戶集合，即ActiveNeighbor(u,i)。

目標用戶u的自然最近鄰用戶集NaturalNearest-Neighboradpt_r(u)中可能存在未對項目i評分的鄰居用戶，根據評分預測公式（5）可知，在預測用戶u對項目i的評分時只有對項目i評分過的鄰居才是真正貢獻最大的用戶，把那些對目標項目i評分值為非0的用戶稱作目標用戶u關于項目i的活躍用戶集合ActiveNeighbor(u,i)，獲取活躍鄰居用戶集的方法如下（CodeⅣ）：

3.2.5獲取推薦集合RecommendNeighbor(u,i)

傳統的基于K近鄰的協同過濾算法直接選取與目標用戶相似度最高的前K個用戶作為鄰居用戶進行評分預測，容易忽略掉真正對評分預測有意義的用戶。本文算法既考慮到自然最近鄰用戶NaturalNearest-Neighboradpt_r(u)對目標用戶的貢獻，也融合了活躍用戶ActiveNeighbor(u,i)對目標項目的貢獻，單獨考慮任何一方的集合，都會降低推薦效果造成推薦結果準確度不高的結果。最簡約易實現的方法是把自然最近鄰用戶集合與活躍用戶集合的并集作為目標用戶u的推薦用戶集合RecommendNeighbor(u,i)，即：

3.3　預測評分P?(u,i)及其準確性

評分預測的準確性與推薦結果的準確性息息相關，選擇不同的鄰居用戶會影響評分預測的結果。獲得目標項目u對項目i的推薦鄰居集合RecommendNeighbor(u,i)后，按照公式（5）預測目標用戶的評分：

其中，pi向量存放測試集中用戶對項目的實際評分，qi存放本文算法預測出的測試集中用戶對項目的評分。

4　實驗結果分析

4.1　實驗數據集

本文仿真實驗使用的數據集是明尼蘇達大學Group-Lens小組從movielens.umn.edu網站收集的MovieLens 100k Dataset（表2）。MovieLens數據集包含943個用戶，1 682部電影，以及用戶對電影逾100 000條范圍在1～5分之間的整數評分（評分值為0則表示用戶未對該電影評分），且每個用戶至少對20部以上的電影進行了評分。通過表2對MovieLens數據集中用戶數、電影數、評分數、評分范圍以及稀疏度的分析可以看出，真實的數據集具有極高的稀疏度。為避免評分填充對鄰居選擇的影響，應在確定目標用戶的推薦鄰居集合后對各用戶缺失項使用評分均值填充。

表2　MovieLens實驗數據集稀疏度

本文算法實驗從ml-100k數據集中將隨機選出的每個用戶對10部電影的實際評分作為ua.test測試集，ml-100k剩余部分作為ua.base訓練集，且兩部分相互獨立。此外，實驗還分別在不同用戶規模上驗證了本文算法在MovieLens數據集上的表現。實驗平臺為Matlab 2010b版本。

4.2　實驗結果分析

首先，本文仿真實驗對比了CF-KNN算法和CF3N算法在MovieLens數據集上的RMSE和MAE值，實驗結果如圖2所示。

圖2　MovieLens上CF-KNN與CF3N算法對比

從圖2看出，CF-KNN算法隨K值增大，RMSE和MAE值逐漸變小，最后趨于一個常數RMSECF-KNNmin=1.072 9，MAECF-KNNmin=0.788 1。本文算法CF3N，目標用戶的鄰居個數是算法自適應生成的，通過該算法計算測試集RMSE=1.031 8和MAE=0.748 3。對比發現，CF3N算法在RMSE和MAE兩個指標上均優于CF-KNN算法。

其次，本文選擇INS-CF[20]算法作為對照，該算法綜合考慮用戶評分數量和評分質量兩方面，提出一種用戶有影響力近鄰的選擇方法，是一種改進的基于用戶近鄰的推薦方法。本文實驗對比了INS-CF算法、CF3N算法在MovieLens數據集上的MAE值，實驗結果（如圖3）顯示，在100～800個鄰居規模上，本文算法的MAE值始終小于INS-CF算法的MAE值。

圖3　MovieLens上INS-CF與CF3N算法對比

此外，實驗還在MovieLens數據集不同用戶規模上進行了對比實驗。比較CF3N、CF-KNN算法在100～500個用戶上的RMSE和MAE值（如圖4所示），得出本文算法在推薦準確性上優于CF-KNN算法的結論。

圖4　MovieLens不同用戶規模上CF-KNN與CF3N對比

5　結束語

本文算法改進了基于K近鄰協同過濾算法直接選取K個鄰居進行評分預測和推薦時，存在K值對評分預測準確率有影響，算法本身推薦準確率不高，且獲取準確率最高的推薦結果實現過程復雜等不足之處。分析傳統基于K近鄰的協同過濾算法在鄰居選擇方法存在的不足，提出一種融合用戶自然最近鄰居的協同過濾推薦算法（CF3N），自適應選取目標用戶的自然最近鄰用戶集合，再融合目標用戶的自然最近鄰居集與活動近鄰用戶集，使用融合后得到的鄰居集合預測目標用戶評分，并在MovieLens數據集上進行對比實驗。既避免了選擇合適K值較難的問題，也更大程度上提升了推薦結果的準確性和有效性。雖然該推薦算法對解決用戶冷啟動問題不具備實用性，這也是下一步研究待解決的問題，但實驗表明本文算法在鄰居選擇和推薦結果準確性方面具有一定優越性。

參考文獻:

[1]中國互聯網絡中心（CNNIC）.第38次中國互聯網絡發展狀況統計報告[R].2016.

[2]Wang Hongbing，Shao Shizhi，Zhou Xuan，et al.Preference recommendation for personalized search[J].Knowledge-Based Systems，2016，100：124-136.

[3]Hu Xiao，Zeng An，Shang Mingsheng.Recommendation in evolving online networks[J].The European Physical Journal B，2016，89（2）：1-7.

[4]Bennett P N，Kelly D，White R W，et al.Overview of the special issue on contextual search and recommendation[J].ACMTransactionsonInformationSystems，2015，33（1）：1-7.

[5]Rahul K，Prakash V O.A collaborative recommender system enhanced with particle swarm optimization technique[J].Multimedia Tools Applications，2016，75（15）：9225-9239.

[6]項亮.推薦系統實踐[M].北京：人民郵電出版社，2012：61-62，23-34.

[7]Herlocker J L，Konstan J A，Riedl J.Explaining collaborative filtering recommendations[C]//Proceedings of ACM Conference on Computer Supported Cooperative Work，2000：241-250.

[8]Hu Yifan，Koren Y，Volinsky I C.Collaborative filtering for implicit feedback datasets[C]//Proceedings of the 2008 Eighth IEEE International Conference on Data Mining，2008：263-272.

[9]Destosiers C，Karypis G.A comprehensive survey of neighborhood-based recommendation methods[M]//Recommender Systems Handbook.Boston，MA：Springer，2011：107-144.

[10]Li Baoli，Lu Qin，Yu Shiwen.An adaptivek-nearest neighbor text categorization strategy[J].ACM Transactions on Asian Language Information Processing，2004，3（4）：215-226.

[11]羅辛，歐陽元新，熊璋，等.通過相似度支持度優化基于K近鄰的協同過濾算法[J].計算機學報，2010，33（8）：1437-1445.

[12]尹航，常桂然，王興偉.采用聚類算法優化的K近鄰協同過濾算法[J].小型微型計算機系統，2013，34（4）：806-809.

[13]黃創光，印鑒，汪靜，等.不確定近鄰的協同過濾推薦算法[J].計算機學報，2010，33（8）：1369-1377.

[14]Polatidis N，Georgiadis C K.A dynamic multi-level collaborative filtering method for improved recommendations[J].Computer Standards&Interfaces，2017，51：14-21.

[15]Wang Shuhui，Huang Qingming，Jiang Shuqiang，et al.Nearest-neighbor method using multiple neighborhood similarities for social media data mining[J].Neurocomputing，2012，95：105-116.

[16]Zou Xianlin，Zhu Qingsheng.Abnormal structure in regular data revealed by isomap with natural nearest neighbor[C]//Communications in Computer and Information Science.Berlin：Springer-Verlag，2011：538-544.

[17]Zhu Qingsheng，Huang Jinlong，Feng Ji，et al.A clustering algorithm based on natural nearest neighbor[J].Journal of Computational Information Systems，2014，10（13）：5473-5480.

[18]Zhang Shu，Mouhoub M，Sadaoui S.3N-Q：Natural nearest neighbor with quality[J].Computer and Information Science，2014，7（1）：94-102.

[19]Zhu Qingsheng，Zhang Ying，Liu Huijun.Classification algorithm based on natural nearest neighbor[J].Journal of Information and Computational Science，2015，12（2）：573-580.

[20]楊恒宇，李慧宗，林耀進，等.協同過濾中有影響力近鄰的選擇[J].北京郵電大學學報，2016，39（1）：29-34.