趙文濤，田歡歡，馮婷婷，崔自恒

河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南焦作454000

大數(shù)據(jù)時(shí)代的到來(lái)，數(shù)據(jù)規(guī)模明顯擴(kuò)大，導(dǎo)致用戶尋找的有效信息和冗余信息的矛盾尖銳，信息過(guò)載[1]問(wèn)題日益嚴(yán)重。推薦系統(tǒng)[2]是一種信息過(guò)濾技術(shù)，幫助用戶快速準(zhǔn)確地獲取感興趣的內(nèi)容，提供個(gè)性化推薦?；卩徲虻膮f(xié)同過(guò)濾[3-4]是一種應(yīng)用廣泛的推薦算法，其中用戶（項(xiàng)目）相似度的確定是協(xié)同過(guò)濾算法的核心步驟[5]，它不僅決定近鄰的選擇，而且對(duì)預(yù)測(cè)和推薦結(jié)果有決定性影響。

傳統(tǒng)相似度主要分為數(shù)值型相似度、結(jié)構(gòu)型相似度和混合型相似度。數(shù)值型相似度如余弦相似度（cosine similarity，COS）[6]、皮爾遜相關(guān)系數(shù)（Pearson correlation coefficient，PCC）[7]和平均絕對(duì)誤差（mean absolute difference，MSD）[8]等，僅考慮共同評(píng)分項(xiàng)目中評(píng)分?jǐn)?shù)值差異，在稀疏數(shù)據(jù)下相似度計(jì)算較不準(zhǔn)確。結(jié)構(gòu)型相似度不同于數(shù)值型相似度，如杰卡德系數(shù)（Jaccard）[9]只考慮共同評(píng)分項(xiàng)目數(shù)量占比。混合型相似度綜合考慮用戶評(píng)分的數(shù)值和結(jié)構(gòu)信息，如JMSD[10]是Jaccard 和MSD 的組合，SPCC[11]結(jié)合Sigmoid 函數(shù)與PCC，具有更好的推薦質(zhì)量。但這些方法都依賴共同評(píng)分項(xiàng)目，隨著用戶和項(xiàng)目數(shù)量的增加，數(shù)據(jù)集越來(lái)越稀疏，導(dǎo)致推薦準(zhǔn)確性降低。許多研究人員致力于從提升預(yù)測(cè)準(zhǔn)確度和推薦質(zhì)量方面，提出不同的改進(jìn)算法來(lái)緩解數(shù)據(jù)稀疏[12-13]和冷啟動(dòng)[14-15]問(wèn)題。其中，新非線性啟發(fā)式相似度（new heuristic similarity model，NHSM）[16]綜合考慮用戶評(píng)分的局部上下文信息和評(píng)分偏好。最近提出基于評(píng)分概率分布的相似度，包括BCF（Bhattacharyya coefficient）[17]和KLCF[18]等，計(jì)算相似度時(shí)使用評(píng)分矩陣中所有的評(píng)分?jǐn)?shù)據(jù)。這些改進(jìn)方法可在一定程度上緩解數(shù)據(jù)稀疏和冷啟動(dòng)問(wèn)題，提高推薦準(zhǔn)確性，但時(shí)間復(fù)雜度和計(jì)算成本較高。

基于以上分析，本文提出一種融合相似度和預(yù)篩選模式的協(xié)同過(guò)濾算法，更好地平衡推薦準(zhǔn)確性和時(shí)間效率的關(guān)系。首先提出一種基于用戶的相似度，其中定義相對(duì)評(píng)分差異，并列舉相似度應(yīng)滿足的定性條件，結(jié)合放大部分相似度值的需求，得到基于exp(-x)函數(shù)的相似度公式，同時(shí)考慮基于信息熵改進(jìn)的評(píng)分偏好和用戶的全局評(píng)分?jǐn)?shù)量信息作為權(quán)重因子以區(qū)分用戶間差異，提高稀疏數(shù)據(jù)中相似度計(jì)算的可靠性。其次根據(jù)相似度和評(píng)分預(yù)測(cè)公式中的隱式約束，提出預(yù)篩選模式。在不影響推薦結(jié)果的前提下，過(guò)濾掉不參與計(jì)算的用戶及相應(yīng)的評(píng)分?jǐn)?shù)據(jù)，進(jìn)一步提高計(jì)算效率。最終融合相似度和預(yù)篩選模式的協(xié)同過(guò)濾算法，在保持較低時(shí)間成本的同時(shí)，也具有良好的預(yù)測(cè)和推薦質(zhì)量。

1 相關(guān)工作

1.1 準(zhǔn)確性和效率的權(quán)衡

推薦系統(tǒng)的目的是幫助用戶以較低的搜索成本[19-20]和更高的推薦準(zhǔn)確性[21-23]來(lái)獲取感興趣的產(chǎn)品或服務(wù)，從而提高用戶體驗(yàn)。隨著信息資源爆炸式增長(zhǎng)，推薦系統(tǒng)面臨著數(shù)據(jù)稀疏、準(zhǔn)確性與效率的權(quán)衡等重大挑戰(zhàn)。

就準(zhǔn)確性而言，目前提出的推薦算法[16-18,24-25]主要通過(guò)設(shè)計(jì)復(fù)雜的相似度來(lái)提高推薦準(zhǔn)確性，但往往忽略時(shí)間效率。Liu 等人[16]引入非線性啟發(fā)式相似度NHSM，由接近度、重要性和奇異性（proximity-significance-singularity，PSS）組成，同時(shí)考慮共同評(píng)分項(xiàng)目的比例（Jaccard）以及用戶評(píng)分偏好的影響。Patra 等人[17]提出基于巴氏系數(shù)的線性相似度BCF，同時(shí)考慮共同評(píng)分項(xiàng)目占比（Jaccard）。Wang 等人[18]提出非線性KLCF，利用擴(kuò)展的NHSM 模型并結(jié)合KL 散度，綜合計(jì)算用戶相似度。受注意力機(jī)制的啟發(fā)，F(xiàn)u等人[24]提出一種項(xiàng)目相似度，自適應(yīng)地捕捉近鄰間的關(guān)系來(lái)進(jìn)行評(píng)分預(yù)測(cè)，能獲得較好的推薦結(jié)果。Polatidis等人[25]提出一種動(dòng)態(tài)的多層次協(xié)同過(guò)濾算法，以提高推薦準(zhǔn)確性。

就效率而言，最近提出的算法[26-30]致力于在保持一定推薦準(zhǔn)確性的同時(shí)降低計(jì)算成本。Bag 等人[26]提出相關(guān)杰卡德系數(shù)（related Jaccard，RJaccard）和相關(guān)JMSD（related JMSD，RJMSD）對(duì)相關(guān)鄰域進(jìn)行分類，在較短的時(shí)間內(nèi)生成推薦。Zhang 等人[27]結(jié)合蜂群聚類，提出一種新的協(xié)同過(guò)濾算法，只需計(jì)算類內(nèi)用戶間的相似度，降低近鄰搜索范圍。Liu 等人[28]提出一種新的潛因子模型（latent collaborative relations，LCR），在保持推薦準(zhǔn)確性的同時(shí)，為目標(biāo)用戶提供快速的推薦。Chae 等人[29]為基于鄰域的相似度分別設(shè)計(jì)了新的數(shù)據(jù)結(jié)構(gòu)，有效地識(shí)別近鄰，提高時(shí)間效率。Wang 等人[30]提出一種相似度框架，綜合考慮數(shù)值和結(jié)構(gòu)型相似度，更高效地產(chǎn)生推薦。

根據(jù)以上分析，通過(guò)設(shè)計(jì)更為復(fù)雜的相似度可在一定程度上改進(jìn)預(yù)測(cè)和推薦質(zhì)量，但計(jì)算復(fù)雜度較高，導(dǎo)致時(shí)間效率顯著降低。為了更好地權(quán)衡準(zhǔn)確度和時(shí)間效率的關(guān)系，迫切需要一種簡(jiǎn)單高效的方法，在保持較低時(shí)間成本的同時(shí)，也具有良好的預(yù)測(cè)和推薦質(zhì)量。

1.2 評(píng)分預(yù)測(cè)公式

協(xié)同過(guò)濾算法中，除相似度的確定之外，評(píng)分預(yù)測(cè)公式也影響最終預(yù)測(cè)和推薦結(jié)果。通常使用的是基于加權(quán)平均的評(píng)分預(yù)測(cè)公式[31]，如式（1）所示。

其中，用戶u的評(píng)分均值為，N(·)為目標(biāo)用戶u的鄰居集，近鄰對(duì)物品i的評(píng)分為rv,i，sim(u,v)為用戶間相似度。這里假設(shè)：如果目標(biāo)用戶u對(duì)未評(píng)分物品i無(wú)法計(jì)算或預(yù)測(cè)時(shí)，將直接忽略Pu,i。

2 本文提出的方法

為在較低的時(shí)間成本內(nèi)提供良好的推薦，首先提出一種簡(jiǎn)單高效的相似度，以緩解稀疏數(shù)據(jù)下相似度計(jì)算的準(zhǔn)確性問(wèn)題。然后根據(jù)相似度和評(píng)分預(yù)測(cè)公式中的隱式約束，提出預(yù)篩選模式，進(jìn)一步提高時(shí)間效率。

2.1 相似度模型

提出的相似度（score enhanced similarity，SES）表達(dá)式共由三部分組成：第一部分是基于相對(duì)評(píng)分差異優(yōu)化的相似度，第二部分為基于信息熵改進(jìn)的用戶評(píng)分偏好，第三部分考慮用戶的全局評(píng)分?jǐn)?shù)量信息。擬議的用戶相似度最終公式如式（2）所示。

2.1.1 基于相對(duì)評(píng)分差異優(yōu)化的相似度

直接使用相對(duì)評(píng)分差異的原始定義衡量相似度顯然不夠準(zhǔn)確，通?？杉尤胍恍┫嗨贫葢?yīng)滿足的定性條件將其達(dá)到優(yōu)化，即通過(guò)對(duì)表示函數(shù)f(raduvi)的raduvi值進(jìn)行變換，可得到調(diào)整的相似度值。這種變換首先需滿足以下條件：（1）f(·)的定義域?yàn)閇0,1]；（2）f(·)是相似度函數(shù)，值域也為[0,1]；（3）f(·)嚴(yán)格連續(xù)且單調(diào)遞減。

除以上相似度應(yīng)滿足的基本條件外，函數(shù)f(·)的選擇還應(yīng)當(dāng)以放大部分相似度值為主要依據(jù)。具體表現(xiàn)為：當(dāng)raduvi的值很小甚至趨近于0 時(shí)，用戶間的相似度很高并且趨近于1，函數(shù)的變化率應(yīng)越來(lái)越快；當(dāng)raduvi變大甚至趨近于1 時(shí)，用戶間的相似度很低并且趨近于0，函數(shù)的變化率應(yīng)越來(lái)越慢。即需滿足raduvi趨于0 時(shí)，f(·)的變化率比raduvi趨于1 時(shí)更重要，這種變化趨勢(shì)能更好地區(qū)分相似度高的用戶間差異，所選的最近鄰參與評(píng)分預(yù)測(cè)時(shí)結(jié)果也更有區(qū)分度。綜合以上分析，函數(shù)exp(-x)不僅滿足所有要求的定性條件，而且是形式簡(jiǎn)單的非線性函數(shù)，具有成為相似度的天然優(yōu)勢(shì)。最終基于exp(-x)函數(shù)衡量相對(duì)評(píng)分差異的相似度，公式如式（3）所示。

其中，max(ru,i,rv,i)是指ru,i與rv,i中的最大值，Iu表示用戶u的評(píng)分項(xiàng)目集。

2.1.2 基于信息熵改進(jìn)的用戶評(píng)分偏好

對(duì)于同樣喜愛(ài)的物品，不同的用戶會(huì)根據(jù)自己的評(píng)分偏好給出不同的評(píng)分值，這將降低推薦準(zhǔn)確性。受NHSM 中用戶評(píng)分偏好的啟發(fā)，提出基于信息熵改進(jìn)的評(píng)分偏好公式，以衡量和區(qū)分用戶評(píng)分偏好對(duì)推薦結(jié)果的影響。

信息熵可以衡量用戶的評(píng)分分布以及信息量情況，信息熵越大表示用戶的評(píng)分分布較均勻且包含的信息量較大，信息熵越小表示用戶的評(píng)分分布較集中且包含的信息量較小。信息熵的分布范圍能夠有效體現(xiàn)不同用戶的區(qū)分度，且根據(jù)信息熵的性質(zhì)，熵值較小的用戶表明其行為可信度較低，因此選取信息熵的倒數(shù)來(lái)調(diào)整用戶差異度，具體表現(xiàn)為：放大熵值較小的用戶差異度，縮小熵值較大的用戶差異度，使得引入信息熵的方式更具合理性。最終綜合用戶均值差和信息熵的倒數(shù)差，提出基于信息熵改進(jìn)的評(píng)分偏好公式，如式（4）所示，更好地衡量用戶的評(píng)分偏好，有效地刻畫用戶間的差異性，從而提高用戶間相似度計(jì)算的準(zhǔn)確性。

其中，Eu、Ev分別代表用戶u和v的信息熵，Eu的計(jì)算公式如式（5）所示，其中當(dāng)前評(píng)分值k在用戶u的評(píng)分向量中所占比例為p(k)，X表示評(píng)分值k的取值范圍。

2.1.3 用戶全局評(píng)分的數(shù)量信息

傳統(tǒng)相似度僅考慮共同評(píng)分項(xiàng)目的信息來(lái)識(shí)別最近鄰，然后通過(guò)最近鄰對(duì)同一物品的評(píng)分情況進(jìn)行預(yù)測(cè)，但有時(shí)這個(gè)過(guò)程并不適合預(yù)測(cè)未評(píng)分物品的評(píng)分值。假設(shè)兩個(gè)用戶非常相似，但只對(duì)共同評(píng)分項(xiàng)目有評(píng)分，這種情況下相似的用戶對(duì)各自的評(píng)分預(yù)測(cè)沒(méi)有貢獻(xiàn)。因此非共同評(píng)分項(xiàng)目的信息對(duì)產(chǎn)生評(píng)分預(yù)測(cè)有重要影響。

針對(duì)這一問(wèn)題提出基于用戶全局評(píng)分?jǐn)?shù)量信息的相似度，主要由目標(biāo)用戶的共同評(píng)分項(xiàng)目相對(duì)于其所有評(píng)分項(xiàng)目的比例構(gòu)成。不僅強(qiáng)調(diào)共同評(píng)分項(xiàng)目的重要性，而且考慮單個(gè)用戶的所有評(píng)分項(xiàng)目信息。由于用戶間的評(píng)分?jǐn)?shù)量大多數(shù)情況下不相同（即Iu≠Iv），則考慮全局評(píng)分?jǐn)?shù)量信息的用戶間相似度一般不對(duì)稱（即sim(u,v)≠sim(v,u)），說(shuō)明用戶間影響力不是同等重要的，更加符合用戶間實(shí)際的影響力情況。同時(shí)由于用戶評(píng)分?jǐn)?shù)據(jù)是離散的，用戶間的關(guān)系一般不是線性的，選用非線性Sigmoid 函數(shù)更好地衡量用戶間的關(guān)系，同時(shí)懲罰低相似度，獎(jiǎng)勵(lì)高相似度。最終基于用戶全局評(píng)分?jǐn)?shù)量信息的相似度公式如式（6）所示，不僅反映用戶自身的全局偏好，而且有助于在預(yù)測(cè)模型中選擇合適的最近鄰進(jìn)而提高評(píng)分預(yù)測(cè)的準(zhǔn)確性。

2.2 預(yù)篩選模式

基于鄰域的協(xié)同過(guò)濾算法最主要的性能瓶頸是查找鄰居集的過(guò)程十分耗時(shí)。如果該性能問(wèn)題可以得到緩解，會(huì)比常規(guī)模式下有更高的計(jì)算效率。受上述相似度模型和評(píng)分預(yù)測(cè)公式中隱式約束的啟發(fā)，提出預(yù)篩選模式。目的是在不影響預(yù)測(cè)和推薦結(jié)果的前提下，有效檢索出對(duì)預(yù)測(cè)評(píng)分值有貢獻(xiàn)的用戶，同時(shí)過(guò)濾掉其余不參與計(jì)算的用戶及對(duì)應(yīng)的評(píng)分?jǐn)?shù)據(jù)。

基于相似度模型和評(píng)分預(yù)測(cè)公式的固有特性，提出以下篩選條件：（1）對(duì)任意兩個(gè)用戶u和v，如果Iu?Iv=?（即兩個(gè)用戶間沒(méi)有共同評(píng)分項(xiàng)目），則相似度為0。（2）對(duì)于目標(biāo)用戶u和目標(biāo)項(xiàng)目i，若rv,i不存在（即鄰居用戶未對(duì)目標(biāo)項(xiàng)目有評(píng)分行為），則評(píng)分預(yù)測(cè)不可計(jì)算。

根據(jù)篩選條件（1），可以安全地忽略掉那些對(duì)目標(biāo)用戶已評(píng)分物品沒(méi)有評(píng)分行為的用戶。根據(jù)篩選條件（2），可以忽略掉那些對(duì)目標(biāo)物品沒(méi)有評(píng)分行為的用戶。這兩類用戶都可通過(guò)訪問(wèn)預(yù)構(gòu)建的項(xiàng)目-用戶表輕松獲得，因此只有同時(shí)滿足與目標(biāo)用戶有共同評(píng)分，且對(duì)目標(biāo)物品有評(píng)分行為的用戶才能進(jìn)入備選鄰居集（將滿足上述篩選條件的兩類用戶集合取交集，即可獲得目標(biāo)用戶的備選鄰居集）。因此目標(biāo)用戶只需與備選鄰居集中的用戶計(jì)算相似度，在不影響預(yù)測(cè)準(zhǔn)確度和推薦質(zhì)量的情況下，縮小鄰居的查詢范圍，從而實(shí)現(xiàn)高效的推薦。

2.3 討論

2.3.1 討論相似度模型

根據(jù)提出的相似度模型（SES），為得到用戶u和v的相似度，需根據(jù)公式依次計(jì)算sim(u,v)RAD、sim(u,v)ENT和sim(u,v)GRN。根據(jù)表1 中示例數(shù)據(jù)計(jì)算用戶相似度，結(jié)果如表2 所示。

表1 用戶-物品評(píng)分矩陣實(shí)例Table 1 Example of user-item rating matrix

表2 用戶相似度計(jì)算結(jié)果Table 2 Values of user similarity

可以看出：（1）無(wú)極端相似度值的產(chǎn)生。由于相對(duì)評(píng)分差異本身的取值較廣泛，且通過(guò)加入較合適的函數(shù)進(jìn)一步優(yōu)化計(jì)算的結(jié)果值，不僅能夠避免極端相似度值的產(chǎn)生，而且使用戶間相似度值分布在較合理的范圍內(nèi)。（2）相似度值分布均勻。用戶的評(píng)分均值和信息熵大多不同，使得用戶間相似度值具有可比性。同時(shí)評(píng)分偏好的計(jì)算返回值較小，可減弱用戶評(píng)分偏好對(duì)相似度的影響。（3）相似度值是非對(duì)稱的。用戶間的相似度基本是不一致的，更加符合用戶間相似度的實(shí)際情況。因此示例中得出的相似度結(jié)果驗(yàn)證了提出的相似度模型具有的計(jì)算優(yōu)勢(shì)。

2.3.2 算法分析

最終融合相似度和預(yù)篩選模式的協(xié)同過(guò)濾算法（combined score enhanced similarity，CSES）的具體實(shí)現(xiàn)過(guò)程如算法1 所示。

算法1融合相似度和預(yù)篩選模式的協(xié)同過(guò)濾算法

假定數(shù)據(jù)集中用戶和物品的數(shù)量分別是|U|和|I|，每個(gè)用戶平均評(píng)價(jià)的物品數(shù)量為m，與目標(biāo)用戶存在共同評(píng)分項(xiàng)目的平均用戶數(shù)量為|V|，兩個(gè)用戶間平均共同評(píng)分項(xiàng)目數(shù)量為n。

傳統(tǒng)相似度（PCC、COS 等）需計(jì)算目標(biāo)用戶與原始鄰居集中用戶間的相似度，時(shí)間復(fù)雜度為O(|U|·|V|·n)。改進(jìn)算法BCF 和KLCF 的時(shí)間復(fù)雜度主要分為兩部分，首先計(jì)算任意兩個(gè)物品間的相似度，復(fù)雜度為O(|I|·|I|)，然后計(jì)算用戶相似度，任何兩個(gè)用戶間的相似度計(jì)算是基于笛卡爾積操作，復(fù)雜度為O(|U|·|U|·m·m)，因此總時(shí)間復(fù)雜度為O(|U|·|U|·m·m+|I|·|I|)。改進(jìn)算法RJMSD 計(jì)算相似度時(shí)考慮用戶的所有評(píng)價(jià)向量，時(shí)間復(fù)雜度為O(|U|·|U|·m)。本文提出的協(xié)同過(guò)濾算法（CSES）只需計(jì)算目標(biāo)用戶與備選鄰居集中用戶間的相似度。假設(shè)備選鄰居集中的平均用戶數(shù)量為|S|（|S|遠(yuǎn)小于|V|和|U|），目標(biāo)用戶與備選鄰居集中用戶間的平均共同評(píng)分物品數(shù)量為k，時(shí)間復(fù)雜度為O(|U|·|S|·k)。根據(jù)以上分析，CSES的時(shí)間復(fù)雜度最低，且隨著數(shù)據(jù)規(guī)模的增加，CSES的時(shí)間復(fù)雜度有更突出的優(yōu)勢(shì)。

3 實(shí)驗(yàn)

為驗(yàn)證本文提出的協(xié)同過(guò)濾算法的有效性，選擇4種經(jīng)典的算法（SPCC[11]、COS[6]、Jaccard[9]、JMSD[10]）以及4種不同的改進(jìn)算法（NHSM[16]、BCF[17]、KLCF[18]、RJMSD[26]）作為對(duì)比實(shí)驗(yàn)。所有的實(shí)驗(yàn)均在開發(fā)平臺(tái)AI Studio 上運(yùn)行，其中處理器為4 核，主存為32 GB，開發(fā)語(yǔ)言為Python3.7，框架版本為PaddlePaddle 2.0.2。為減少實(shí)驗(yàn)環(huán)境的影響，采用5 次實(shí)驗(yàn)的平均值作為統(tǒng)計(jì)的結(jié)果。

3.1 數(shù)據(jù)集

實(shí)驗(yàn)選擇常用的三個(gè)公開數(shù)據(jù)集，其中兩個(gè)來(lái)自MovieLens，分別是ML-100K 和ML-Latest-Small，另一個(gè)是Yahoo Music。表3 總結(jié)了各數(shù)據(jù)集在用戶、物品、評(píng)分和稀疏度[32]方面的屬性。為評(píng)估算法的性能，遵循經(jīng)典的推薦系統(tǒng)測(cè)試方法[33]，在數(shù)據(jù)集中隨機(jī)選取每個(gè)用戶80%的評(píng)分?jǐn)?shù)據(jù)作為訓(xùn)練集，其余作為測(cè)試集。

表3 數(shù)據(jù)集屬性Table 3 Properties of datasets

3.2 評(píng)測(cè)指標(biāo)

使用預(yù)測(cè)準(zhǔn)確性和推薦準(zhǔn)確性衡量推薦算法的質(zhì)量，使用覆蓋率評(píng)價(jià)推薦算法挖掘長(zhǎng)尾的能力。

預(yù)測(cè)準(zhǔn)確性的常用指標(biāo)是平均絕對(duì)誤差（mean absolute error，MAE）和均方根誤差（root mean squared error，RMSE），用于評(píng)估測(cè)試集中實(shí)際評(píng)分值和預(yù)測(cè)評(píng)分值的差異，誤差越低表示預(yù)測(cè)準(zhǔn)確性越好。MAE 和RMSE 的公式如式（7）、式（8）所示。

其中，ru,i、pu,i分別為目標(biāo)用戶對(duì)目標(biāo)物品的實(shí)際評(píng)分和預(yù)測(cè)評(píng)分，n表示算法執(zhí)行預(yù)測(cè)的次數(shù)。

推薦準(zhǔn)確性包括三個(gè)重要的指標(biāo)，精確率（Precision）、召回率（Recall）和綜合評(píng)價(jià)指標(biāo)（F1-value），如式（9）～式（11）所示。其中F1-value 同時(shí)考慮精確率和召回率，F(xiàn)1-value越高，表示推薦的質(zhì)量越好。

其中，Ipr和Iar分別是預(yù)測(cè)推薦列表和測(cè)試集中實(shí)際推薦列表，n(·)表示返回集合中元素的個(gè)數(shù)。采取的推薦規(guī)則是：出現(xiàn)在推薦列表中物品的評(píng)分必須大于該目標(biāo)用戶的平均評(píng)分。

覆蓋率（Coverage）定義為推薦系統(tǒng)能夠推薦出的物品占總物品的比例。覆蓋率越高說(shuō)明推薦算法發(fā)掘長(zhǎng)尾的能力越好，如式（12）所示，其中Iut是測(cè)試集中實(shí)際的評(píng)分列表。

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

3.3.1 預(yù)篩選模式的有效性分析

通過(guò)理論上對(duì)相似度模型和評(píng)分預(yù)測(cè)公式的分析，提出預(yù)篩選模式。首先在三個(gè)數(shù)據(jù)集上分別進(jìn)行實(shí)驗(yàn)，對(duì)比原始鄰居集和使用預(yù)篩選模式后得到的備選鄰居集中的平均用戶數(shù)量，預(yù)篩選的效果如圖1所示。

圖1 原始鄰居集和備選鄰居集的平均用戶數(shù)量對(duì)比Fig.1 Average number of users in original neighbor set versus alternative neighbor set

在ML-100K 數(shù)據(jù)集中，原始鄰居集的平均用戶數(shù)量為943，而備選鄰居集的平均用戶數(shù)量約為668，使用預(yù)篩選模式后，共過(guò)濾29.16%的用戶和相應(yīng)的評(píng)分?jǐn)?shù)據(jù)。同樣，在ML-Latest-Small 數(shù)據(jù)集中，原始鄰居集的平均用戶數(shù)量為610，備選鄰居集的平均用戶數(shù)量約為351，過(guò)濾了42.46%的用戶和相應(yīng)評(píng)分?jǐn)?shù)據(jù)。在Yahoo Music 數(shù)據(jù)集中，原始鄰居集的平均用戶數(shù)量為15 400，備選鄰居集的平均用戶數(shù)量約為2 635，共過(guò)濾82.89%的用戶和相應(yīng)評(píng)分?jǐn)?shù)據(jù)。從各數(shù)據(jù)集過(guò)濾的用戶和評(píng)分?jǐn)?shù)據(jù)的百分比可以看出，預(yù)篩選模式能減少大量的用戶相似度計(jì)算，并且在稀疏數(shù)據(jù)集中的效果更加突出。

為進(jìn)一步細(xì)化分析預(yù)篩選模式對(duì)時(shí)間效率的影響，在三個(gè)數(shù)據(jù)集上，分別統(tǒng)計(jì)提出的相似度模型（SES）在常規(guī)模式和預(yù)篩選模式下完成單次推薦所需的平均時(shí)間，主要分為查找鄰居集和完成評(píng)分預(yù)測(cè)的時(shí)間。其中近鄰個(gè)數(shù)根據(jù)文獻(xiàn)[30]設(shè)為80，結(jié)果如表4 和表5 所示。

根據(jù)表4 和表5 中各部分的時(shí)間對(duì)比，首先在查找近鄰的步驟中，預(yù)篩選模式相比常規(guī)模式在三個(gè)數(shù)據(jù)集上分別提升36.88%、22.84%和71.55%的時(shí)間效率。其次在產(chǎn)生預(yù)測(cè)的步驟中，執(zhí)行時(shí)間無(wú)明顯差別。最后在三個(gè)數(shù)據(jù)集上，預(yù)篩選模式的總運(yùn)行時(shí)間相比常規(guī)模式分別下降35.42%、20.29%和71.18%。以上分析證明了預(yù)篩選模式的有效性，特別在規(guī)模較大的數(shù)據(jù)集中，預(yù)篩選模式的優(yōu)勢(shì)更加突出。因此引入預(yù)篩選模式后，SES 的時(shí)間效率得到進(jìn)一步提升。

表4 常規(guī)模式下單次推薦所需時(shí)間Table 4 Running time for single recommendation in common mode 單位：s

表5 預(yù)篩選模式下單次推薦所需時(shí)間Table 5 Running time for single recommendation in pre-filtering mode 單位：s

3.3.2 整體預(yù)測(cè)和推薦效果比較

在三個(gè)數(shù)據(jù)集上分別進(jìn)行實(shí)驗(yàn)，主要討論不同近鄰數(shù)量下融合預(yù)篩選模式后的協(xié)同過(guò)濾算法（CSES）與其余對(duì)比算法的預(yù)測(cè)和推薦結(jié)果。其中近鄰數(shù)量從10 到100 變化，步長(zhǎng)為10。

（1）在ML-100K 數(shù)據(jù)集上的結(jié)果分析

在ML-100K 數(shù)據(jù)集上，各算法的預(yù)測(cè)準(zhǔn)確度如圖2 所示。圖2 表明，隨著近鄰個(gè)數(shù)的增加，所有方法的預(yù)測(cè)誤差（MAE 和RMSE）值都逐漸下降。其中SPCC、BCF、KLCF 的預(yù)測(cè)誤差值較高，且波動(dòng)范圍較大。COS、JMSD、RJMSD 的預(yù)測(cè)準(zhǔn)確度有明顯改善，且變化趨勢(shì)較為接近。不同近鄰數(shù)量下，CSES具有最好的預(yù)測(cè)準(zhǔn)確度，相比最接近的NHSM 平均降低1%～2%的預(yù)測(cè)誤差，特別在近鄰個(gè)數(shù)較少時(shí)，優(yōu)勢(shì)更加明顯。主要原因可能為：基于exp(-x)函數(shù)衡量相對(duì)評(píng)分差異的相似度能更敏感地捕捉評(píng)分差異的變化，同時(shí)綜合信息熵改進(jìn)的評(píng)分偏好和用戶的全局評(píng)分?jǐn)?shù)量信息，使相似度計(jì)算更加可靠。

圖2 ML-100K 數(shù)據(jù)集上不同鄰居數(shù)量的MAE 和RMSEFig.2 MAE and RMSE with different neighbor sizes on ML-100K dataset

在ML-100K 數(shù)據(jù)集上，各算法的推薦質(zhì)量如圖3所示。所有方法的F1 值都隨近鄰數(shù)量的增加而逐漸變大。其中最近提出的算法BCF、NHSM、KLCF 相比傳統(tǒng)算法在推薦質(zhì)量方面有明顯的改善。當(dāng)近鄰個(gè)數(shù)為10 時(shí)，CSES 的F1 值略低于BCF，但隨著近鄰數(shù)量的增加，CSES 的F1 值最高且有相對(duì)穩(wěn)定的表現(xiàn)，當(dāng)近鄰數(shù)量為100 時(shí)，CSES 的F1 值達(dá)到最大值，約為0.696。因此在ML-100K 數(shù)據(jù)集上，CSES 相比其他算法有更好的推薦質(zhì)量。

圖3 ML-100K 數(shù)據(jù)集上不同鄰居數(shù)量的F1-valueFig.3 F1-value with different neighbor sizes on ML-100K dataset

在ML-100K 數(shù)據(jù)集上，各算法的覆蓋率如圖4所示。在不同鄰居數(shù)量下，CSES 的覆蓋率略低于BCF，保持最接近的趨勢(shì)且相對(duì)穩(wěn)定。相比其余算法，CSES 和BCF 均有更好的覆蓋率。BCF 的覆蓋率較高，原因可能為：能夠計(jì)算任意兩個(gè)用戶間的相似度，得到的預(yù)測(cè)推薦列表中有效評(píng)分?jǐn)?shù)量更多，因此覆蓋率會(huì)略有優(yōu)勢(shì)。

圖4 ML-100K 數(shù)據(jù)集上不同鄰居數(shù)量的CoverageFig.4 Coverage with different neighbor sizes on ML-100K dataset

（2）在ML-Latest-Small數(shù)據(jù)集上的結(jié)果分析

同樣地，在ML-Latest-Small 數(shù)據(jù)集上執(zhí)行所有算法，預(yù)測(cè)準(zhǔn)確度如圖5 所示。在不同近鄰數(shù)量下，CSES 都有最好的預(yù)測(cè)準(zhǔn)確率和較小的波動(dòng)范圍，相比最接近的NHSM 和RJMSD 大約提升1%～3%。所有算法在ML-Latest-Small 數(shù)據(jù)集上的誤差范圍均比在ML-100K 上有所降低，主要因?yàn)椋涸谠u(píng)分?jǐn)?shù)量相差不大的情況下，ML-Latest-Small 數(shù)據(jù)集上的用戶數(shù)量相對(duì)較少，則單個(gè)用戶對(duì)應(yīng)的評(píng)分?jǐn)?shù)據(jù)更多，基于用戶的相似度計(jì)算就更加準(zhǔn)確。

圖5 ML-Latest-Small數(shù)據(jù)集上不同鄰居數(shù)量的MAE 和RMSEFig.5 MAE and RMSE with different neighbor sizes on ML-Latest-Small dataset

在ML-Latest-Small 數(shù)據(jù)集上執(zhí)行所有算法，推薦質(zhì)量如圖6 所示。不同近鄰數(shù)量下，CSES 都有最高的F1 值。相比表現(xiàn)較好的BCF、KLCF、NHSM，平均提升1%～3%。隨著近鄰數(shù)量的增加，BCF、KLCF、NHSM 的F1 值無(wú)顯著差異。

圖6 ML-Latest-Small數(shù)據(jù)集上不同鄰居數(shù)量的F1-valueFig.6 F1-value with different neighbor sizes on ML-Latest-Small dataset

在ML-Latest-Small 數(shù)據(jù)集上，各算法的覆蓋率如圖7 所示。不同近鄰數(shù)量下相比其余算法，BCF、KLCF 和CSES 的RMSE覆蓋率較高，且分布區(qū)間為[0.580,0.603]。隨著近鄰數(shù)量的增加，三者M(jìn)AE的差距越來(lái)越小。

圖7 ML-Latest-Small數(shù)據(jù)集上不同鄰居數(shù)量的CoverageFig.7 Coverage with different neighbor sizes on ML-Latest-Small dataset

（3）在Yahoo Music數(shù)據(jù)集上的結(jié)果分析

在Yahoo Music 數(shù)據(jù)集上執(zhí)行所有算法，預(yù)測(cè)準(zhǔn)確度如圖8 所示。在不同近鄰數(shù)量下CSES 的預(yù)測(cè)誤差值最低，相比表現(xiàn)較接近的NHSM 和RJMSD 降低大約1%～4%，相比其余算法則有更明顯的優(yōu)勢(shì)。在Yahoo Music 數(shù)據(jù)集上，所有算法的預(yù)測(cè)誤差值都普遍較高，主要原因是：數(shù)據(jù)規(guī)模明顯變大且用戶數(shù)量也明顯變多，單個(gè)用戶對(duì)應(yīng)的評(píng)分?jǐn)?shù)據(jù)較少，因此預(yù)測(cè)誤差值較高。

圖8 Yahoo Music數(shù)據(jù)集上不同鄰居數(shù)量的MAE 和RMSEFig.8 MAE and RMSE with different neighbor sizes on Yahoo Music dataset

在Yahoo Music 數(shù)據(jù)集上各算法的推薦質(zhì)量如圖9 所示。不同鄰居數(shù)量下，CSES 比其余方法有更好的推薦質(zhì)量，特別在鄰居數(shù)量較少時(shí)，這種優(yōu)勢(shì)更加明顯。其中，NHSM、RJMSD、BCF 和SPCC 的推薦質(zhì)量相比其余傳統(tǒng)方法也有較大提升。

圖9 Yahoo Music數(shù)據(jù)集上不同鄰居數(shù)量的F1-valueFig.9 F1-value with different neighbor sizes on Yahoo Music dataset

在Yahoo Music 數(shù)據(jù)集上，各算法的覆蓋率如圖10 所示。當(dāng)近鄰個(gè)數(shù)小于30 時(shí)，BCF 的Coverage 值最高，與最接近的CSES 相比有2%～3%的優(yōu)勢(shì)；當(dāng)近鄰個(gè)數(shù)大于30 時(shí)，CSES 的coverage 值最高，相比最接近的RJMSD 提升1%～4%。

圖10 Yahoo Music數(shù)據(jù)集上不同鄰居數(shù)量的CoverageFig.10 Coverage with different neighbor sizes on Yahoo Music dataset

3.3.3 時(shí)間效率比較

在三個(gè)數(shù)據(jù)集上，分別統(tǒng)計(jì)各評(píng)測(cè)指標(biāo)中表現(xiàn)較好的5種算法（CSES、RJMSD、NHSM、BCF和KLCF）的總運(yùn)行時(shí)間，具體結(jié)果如表6 所示。

表6 在三個(gè)數(shù)據(jù)集上的總運(yùn)行時(shí)間對(duì)比Table 6 Running time comparison on three datasets 單位：s

從表6 中可以看出，在ML-100K 數(shù)據(jù)集上，CSES和RJMSD 的總運(yùn)行時(shí)間無(wú)明顯差別，相比NHSM 分別有大約57.14%和58.93%的降低。同樣地，在MLLatest-Small 數(shù)據(jù)集上，CSES 和RJMSD 的總運(yùn)行時(shí)間一致，相比NHSM 大約降低48.48%。在Yahoo Music 數(shù)據(jù)集上，CSES 的總運(yùn)行時(shí)間最短，相比RJMSD 和NHSM 大約降低71.55%和80.42%。然而在三個(gè)數(shù)據(jù)集上，BCF 和KLCF 的總運(yùn)行時(shí)間較長(zhǎng)，與CSES、RJMSD 和NHSM 相比有明顯的差距。綜合以上分析，CSES 的時(shí)間效率較高，特別在稀疏數(shù)據(jù)集下優(yōu)勢(shì)更加突出。

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

本文提出將相似度和預(yù)篩選模式融合的協(xié)同過(guò)濾算法，以更好地平衡準(zhǔn)確性和時(shí)間效率的關(guān)系。該算法首先定義相對(duì)評(píng)分差異，并根據(jù)相似度函數(shù)應(yīng)滿足的條件得到基于相對(duì)評(píng)分差異優(yōu)化的相似度，能更敏感地捕捉用戶間評(píng)分變化。同時(shí)將基于信息熵改進(jìn)的評(píng)分偏好和基于用戶全局評(píng)分的數(shù)量信息作為權(quán)重因子，更易區(qū)分用戶間相似度。提出的相似度模型具有簡(jiǎn)單高效的特性，并緩解了稀疏數(shù)據(jù)下推薦準(zhǔn)確性問(wèn)題。其次通過(guò)分析相似度和評(píng)分預(yù)測(cè)公式的隱式約束，進(jìn)一步提出預(yù)篩選模式。在不影響預(yù)測(cè)和推薦結(jié)果的前提下，減少大量無(wú)效的相似度計(jì)算，極大地改善了算法運(yùn)行效率。最終提出的協(xié)同過(guò)濾算法融合相似度和預(yù)篩選模式，在三個(gè)不同稀疏度的數(shù)據(jù)集上實(shí)驗(yàn)，結(jié)果表明：相比已有算法，所提出的算法在保持相對(duì)穩(wěn)定和較高推薦準(zhǔn)確性的同時(shí)，進(jìn)一步提高了系統(tǒng)運(yùn)行效率。

本研究?jī)H關(guān)注評(píng)分矩陣中評(píng)分?jǐn)?shù)據(jù)，未來(lái)的工作將分析評(píng)分表以外的物品標(biāo)簽、用戶評(píng)論等信息，進(jìn)一步提升推薦性能。