融合用戶自然最近鄰的協(xié)同過(guò)濾推薦算法

王　穎，王　欣，唐萬(wàn)梅

WANG Ying,WANG Xin,TANG Wanmei

重慶師范大學(xué) 計(jì)算機(jī)與信息科學(xué)學(xué)院，重慶 401331

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

1　引言

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

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

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

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

2　傳統(tǒng)的基于近鄰的協(xié)同過(guò)濾算法

傳統(tǒng)的基于近鄰的協(xié)同過(guò)濾算法分為基于用戶近鄰的協(xié)同過(guò)濾推薦和基于項(xiàng)目近鄰的協(xié)同過(guò)濾推薦兩個(gè)方面。目前，大多數(shù)推薦系統(tǒng)使用的是基于項(xiàng)目近鄰的推薦算法，如Netflix、Amazon等網(wǎng)站，因?yàn)樵摲椒ǜ⒅赜脩舻臍v史興趣且推薦系統(tǒng)中用戶總數(shù)往往大于項(xiàng)目總數(shù)，從存儲(chǔ)角度來(lái)看更有優(yōu)勢(shì)，但對(duì)于個(gè)性化不太明顯且項(xiàng)目更新較快或數(shù)量龐大的領(lǐng)域則不太適合。傳統(tǒng)的基于用戶近鄰的協(xié)同過(guò)濾具有更長(zhǎng)的發(fā)展歷史，第一個(gè)郵件過(guò)濾系統(tǒng)Tapestry、Digg網(wǎng)站的個(gè)性化閱讀、GroupLens的個(gè)性化新聞推薦都是使用的該方法，因?yàn)樾侣?、文章、圖書(shū)更新速度快且數(shù)量遠(yuǎn)超用戶數(shù)，人們對(duì)于“新”的需求超過(guò)了對(duì)“個(gè)性化”的需求，此時(shí)該方法在存儲(chǔ)代價(jià)、推薦速度、實(shí)現(xiàn)的難易程度等方面具有更強(qiáng)的優(yōu)勢(shì)。此外，實(shí)際應(yīng)用中基于用戶近鄰的協(xié)同過(guò)濾方法相比基于項(xiàng)目近鄰的協(xié)同過(guò)濾在推薦結(jié)果的召回率、覆蓋率、新穎度等方面表現(xiàn)更優(yōu)[6]。雖然該方法在解決用戶冷啟動(dòng)問(wèn)題時(shí)表現(xiàn)不佳，但仍然具有獨(dú)特的優(yōu)勢(shì)和較強(qiáng)的應(yīng)用價(jià)值。

傳統(tǒng)的基于用戶近鄰的推薦算法主要工作包含：（1）建立用戶-項(xiàng)目評(píng)分矩陣；（2）計(jì)算用戶之間關(guān)于評(píng)分的相似度；（3）建立用戶-用戶相似度矩陣；（4）尋找與目標(biāo)用戶最相似的鄰居對(duì)目標(biāo)用戶進(jìn)行評(píng)分預(yù)測(cè)；（5）計(jì)算評(píng)分預(yù)測(cè)的準(zhǔn)確度。具體步驟如下。

2.1　建立用戶-項(xiàng)目評(píng)分矩陣

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

表1　用戶-項(xiàng)目評(píng)分矩陣

2.2　根據(jù)評(píng)分值計(jì)算用戶之間相似度

傳統(tǒng)的基于用戶近鄰?fù)扑]算法采用的相似度計(jì)算方法主要有以下幾種：

（1）Cosine相似度

余弦相似度（公式（1））表示目標(biāo)用戶u及其鄰居用戶v的評(píng)分向量之間的夾角余弦值，余弦相似度的范圍值在[－1，1]區(qū)間，1表示兩個(gè)用戶完全相似，0表示兩用戶相互獨(dú)立，－1則表示兩用戶完全不相似。

（2）Pearson相似度

Pearson相似度（公式（2））取值在[－1，1]之間，負(fù)數(shù)表示兩用戶負(fù)相關(guān)，正數(shù)表示兩用戶正相關(guān)，0表示兩用戶不相關(guān)。其中，Iuv表示目標(biāo)用戶u和鄰居用戶v共同評(píng)分過(guò)的項(xiàng)目集合，rui表示用戶u對(duì)項(xiàng)目i的評(píng)分，表示用戶u對(duì)所有評(píng)分過(guò)的項(xiàng)目的評(píng)分均值。

（3）Jaccard相似度

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

2.3　尋找目標(biāo)用戶u的K近鄰集合

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

2.4　對(duì)目標(biāo)用戶u進(jìn)行評(píng)分預(yù)測(cè)

根據(jù)目標(biāo)用戶的鄰居即集合Neighbor(u)中用戶的評(píng)分值和相似度，預(yù)測(cè)目標(biāo)用戶u對(duì)目標(biāo)項(xiàng)目i的評(píng)分，評(píng)分預(yù)測(cè)公式（公式（4））如下：

2.5　推薦結(jié)果準(zhǔn)確性評(píng)測(cè)

目前，推薦算法的評(píng)測(cè)指標(biāo)主要從用戶、物品、時(shí)間三個(gè)維度進(jìn)行，包括用戶滿意度、預(yù)測(cè)準(zhǔn)確度、覆蓋率、多樣性、新穎性、驚喜度、信任度、實(shí)時(shí)性、健壯性、商業(yè)目標(biāo)是否達(dá)成等多個(gè)指標(biāo)[6]，然而預(yù)測(cè)準(zhǔn)確度依然是協(xié)同過(guò)濾最重要的指標(biāo)[9]。預(yù)測(cè)準(zhǔn)確性又包含評(píng)分預(yù)測(cè)準(zhǔn)確性方面的平均絕對(duì)誤差（MAE）和均方根誤差（RMSE）兩個(gè)指標(biāo)。

3　融合用戶自然最近鄰的協(xié)同過(guò)濾推薦

傳統(tǒng)的基于用戶K近鄰的協(xié)同過(guò)濾推薦算法通過(guò)計(jì)算用戶相似度再按照相似度值由大到小把鄰居排序后，直接選取與目標(biāo)用戶距離最近的K個(gè)用戶作為目標(biāo)用戶的鄰居集合，沒(méi)有考慮到鄰居的對(duì)稱性且K值的選取方法不同對(duì)評(píng)分預(yù)測(cè)結(jié)果的準(zhǔn)確性影響較大。常用方法是選擇特定步長(zhǎng)，計(jì)算不同K值下的用戶評(píng)分預(yù)測(cè)結(jié)果及其準(zhǔn)確性，直到推薦準(zhǔn)確率達(dá)到設(shè)定的閾值為止。而這種方法無(wú)疑計(jì)算量較大，實(shí)現(xiàn)起來(lái)相對(duì)復(fù)雜，且準(zhǔn)確率不高。

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

圖1　CF3N算法流程圖

3.1　前提工作

CF3N是一種新的改進(jìn)的基于用戶近鄰的推薦算法，該算法中用戶近鄰個(gè)數(shù)不需要提前設(shè)置好，而是在算法過(guò)程中自適應(yīng)生成?？梢詫⑷我庥脩魎看作空間里的一個(gè)點(diǎn)，推薦系統(tǒng)中存在的大量用戶U構(gòu)成一個(gè)點(diǎn)空間，空間中兩個(gè)用戶距離越近則相似度Sim值越大，稱這兩個(gè)用戶的興趣偏好越相似。不難理解，空間分布密集區(qū)域的用戶群具有更多的自然最近鄰居，分布稀疏區(qū)域的用戶具有較少的自然最近鄰居。

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

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

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

在向目標(biāo)用戶u推薦時(shí)選擇的鄰居個(gè)數(shù)隨用戶分布疏密程度有所不同，即NaturalNearestNeighboradpt_r(u)集合的大小與u所處空間用戶疏密程度呈正相關(guān)。因?yàn)楝F(xiàn)實(shí)中的推薦系統(tǒng)數(shù)據(jù)稀疏度往往會(huì)高達(dá)90%以上，在預(yù)測(cè)目標(biāo)用戶u對(duì)目標(biāo)項(xiàng)目i的評(píng)分時(shí)，其自然最近鄰NaturalNearestNeighboradpt_r(u)中的鄰居用戶并非全部都是活躍用戶，非活躍用戶在評(píng)分預(yù)測(cè)中所起作用不大，此時(shí)采用融入活躍用戶集合的方法，把NaturalNearestNeighboradpt_r(u)和 ActiveNeighbor(u,i)融合后的結(jié)果作為評(píng)分預(yù)測(cè)時(shí)使用的鄰居集合Recommend-Neighbor(u,i)，具體步驟如下。

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

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

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

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

CF3N協(xié)同過(guò)濾推薦算法選擇用戶近鄰時(shí)，考慮到的鄰居關(guān)系是一種對(duì)稱關(guān)系的鄰居，如目標(biāo)用戶u有r個(gè)正最近鄰，若反過(guò)來(lái)用戶u出現(xiàn)在其r個(gè)鄰居的正最近鄰集合中至少一次，則才能構(gòu)成對(duì)稱的鄰居關(guān)系。尋找目標(biāo)用戶u的逆最近鄰用戶算法如下（CodeⅡ）：

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

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

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

3.2.4獲取用戶u關(guān)于項(xiàng)目i的活躍鄰居用戶集合ActiveNeighbor(u，i)

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

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

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

傳統(tǒng)的基于K近鄰的協(xié)同過(guò)濾算法直接選取與目標(biāo)用戶相似度最高的前K個(gè)用戶作為鄰居用戶進(jìn)行評(píng)分預(yù)測(cè)，容易忽略掉真正對(duì)評(píng)分預(yù)測(cè)有意義的用戶。本文算法既考慮到自然最近鄰用戶NaturalNearest-Neighboradpt_r(u)對(duì)目標(biāo)用戶的貢獻(xiàn)，也融合了活躍用戶ActiveNeighbor(u,i)對(duì)目標(biāo)項(xiàng)目的貢獻(xiàn)，單獨(dú)考慮任何一方的集合，都會(huì)降低推薦效果造成推薦結(jié)果準(zhǔn)確度不高的結(jié)果。最簡(jiǎn)約易實(shí)現(xiàn)的方法是把自然最近鄰用戶集合與活躍用戶集合的并集作為目標(biāo)用戶u的推薦用戶集合RecommendNeighbor(u,i)，即：

3.3　預(yù)測(cè)評(píng)分P?(u,i)及其準(zhǔn)確性

評(píng)分預(yù)測(cè)的準(zhǔn)確性與推薦結(jié)果的準(zhǔn)確性息息相關(guān)，選擇不同的鄰居用戶會(huì)影響評(píng)分預(yù)測(cè)的結(jié)果。獲得目標(biāo)項(xiàng)目u對(duì)項(xiàng)目i的推薦鄰居集合RecommendNeighbor(u,i)后，按照公式（5）預(yù)測(cè)目標(biāo)用戶的評(píng)分：

其中，pi向量存放測(cè)試集中用戶對(duì)項(xiàng)目的實(shí)際評(píng)分，qi存放本文算法預(yù)測(cè)出的測(cè)試集中用戶對(duì)項(xiàng)目的評(píng)分。

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

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

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

表2　MovieLens實(shí)驗(yàn)數(shù)據(jù)集稀疏度

本文算法實(shí)驗(yàn)從ml-100k數(shù)據(jù)集中將隨機(jī)選出的每個(gè)用戶對(duì)10部電影的實(shí)際評(píng)分作為ua.test測(cè)試集，ml-100k剩余部分作為ua.base訓(xùn)練集，且兩部分相互獨(dú)立。此外，實(shí)驗(yàn)還分別在不同用戶規(guī)模上驗(yàn)證了本文算法在MovieLens數(shù)據(jù)集上的表現(xiàn)。實(shí)驗(yàn)平臺(tái)為Matlab 2010b版本。

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

首先，本文仿真實(shí)驗(yàn)對(duì)比了CF-KNN算法和CF3N算法在MovieLens數(shù)據(jù)集上的RMSE和MAE值，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2　MovieLens上CF-KNN與CF3N算法對(duì)比

從圖2看出，CF-KNN算法隨K值增大，RMSE和MAE值逐漸變小，最后趨于一個(gè)常數(shù)RMSECF-KNNmin=1.072 9，MAECF-KNNmin=0.788 1。本文算法CF3N，目標(biāo)用戶的鄰居個(gè)數(shù)是算法自適應(yīng)生成的，通過(guò)該算法計(jì)算測(cè)試集RMSE=1.031 8和MAE=0.748 3。對(duì)比發(fā)現(xiàn)，CF3N算法在RMSE和MAE兩個(gè)指標(biāo)上均優(yōu)于CF-KNN算法。

其次，本文選擇INS-CF[20]算法作為對(duì)照，該算法綜合考慮用戶評(píng)分?jǐn)?shù)量和評(píng)分質(zhì)量?jī)煞矫?，提出一種用戶有影響力近鄰的選擇方法，是一種改進(jìn)的基于用戶近鄰的推薦方法。本文實(shí)驗(yàn)對(duì)比了INS-CF算法、CF3N算法在MovieLens數(shù)據(jù)集上的MAE值，實(shí)驗(yàn)結(jié)果（如圖3）顯示，在100～800個(gè)鄰居規(guī)模上，本文算法的MAE值始終小于INS-CF算法的MAE值。

圖3　MovieLens上INS-CF與CF3N算法對(duì)比

此外，實(shí)驗(yàn)還在MovieLens數(shù)據(jù)集不同用戶規(guī)模上進(jìn)行了對(duì)比實(shí)驗(yàn)。比較CF3N、CF-KNN算法在100～500個(gè)用戶上的RMSE和MAE值（如圖4所示），得出本文算法在推薦準(zhǔn)確性上優(yōu)于CF-KNN算法的結(jié)論。

圖4　MovieLens不同用戶規(guī)模上CF-KNN與CF3N對(duì)比

5　結(jié)束語(yǔ)

本文算法改進(jìn)了基于K近鄰協(xié)同過(guò)濾算法直接選取K個(gè)鄰居進(jìn)行評(píng)分預(yù)測(cè)和推薦時(shí)，存在K值對(duì)評(píng)分預(yù)測(cè)準(zhǔn)確率有影響，算法本身推薦準(zhǔn)確率不高，且獲取準(zhǔn)確率最高的推薦結(jié)果實(shí)現(xiàn)過(guò)程復(fù)雜等不足之處。分析傳統(tǒng)基于K近鄰的協(xié)同過(guò)濾算法在鄰居選擇方法存在的不足，提出一種融合用戶自然最近鄰居的協(xié)同過(guò)濾推薦算法（CF3N），自適應(yīng)選取目標(biāo)用戶的自然最近鄰用戶集合，再融合目標(biāo)用戶的自然最近鄰居集與活動(dòng)近鄰用戶集，使用融合后得到的鄰居集合預(yù)測(cè)目標(biāo)用戶評(píng)分，并在MovieLens數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)。既避免了選擇合適K值較難的問(wèn)題，也更大程度上提升了推薦結(jié)果的準(zhǔn)確性和有效性。雖然該推薦算法對(duì)解決用戶冷啟動(dòng)問(wèn)題不具備實(shí)用性，這也是下一步研究待解決的問(wèn)題，但實(shí)驗(yàn)表明本文算法在鄰居選擇和推薦結(jié)果準(zhǔn)確性方面具有一定優(yōu)越性。

參考文獻(xiàn):

[1]中國(guó)互聯(lián)網(wǎng)絡(luò)中心（CNNIC）.第38次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[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]項(xiàng)亮.推薦系統(tǒng)實(shí)踐[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]羅辛，歐陽(yáng)元新，熊璋，等.通過(guò)相似度支持度優(yōu)化基于K近鄰的協(xié)同過(guò)濾算法[J].計(jì)算機(jī)學(xué)報(bào)，2010，33（8）：1437-1445.

[12]尹航，常桂然，王興偉.采用聚類算法優(yōu)化的K近鄰協(xié)同過(guò)濾算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2013，34（4）：806-809.

[13]黃創(chuàng)光，印鑒，汪靜，等.不確定近鄰的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)學(xué)報(bào)，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，F(xiàn)eng 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ìn)，等.協(xié)同過(guò)濾中有影響力近鄰的選擇[J].北京郵電大學(xué)學(xué)報(bào)，2016，39（1）：29-34.