一種改進(jìn)用戶相似度的協(xié)同過濾推薦算法

魏 浩，劉小豫，張 偉

（咸陽師范學(xué)院計(jì)算機(jī)學(xué)院，陜西 咸陽 712000）

隨著互聯(lián)網(wǎng)的高速發(fā)展，社會(huì)進(jìn)入了一個(gè)“信息爆炸”時(shí)代。尤其伴隨著電子商務(wù)的快速成長和網(wǎng)絡(luò)購物的迅速普及，如何使用戶在數(shù)量龐大的商品中快速、高效地找到感興趣的商品，是電子商務(wù)網(wǎng)站面臨的一個(gè)重大挑戰(zhàn)。雖然用戶能夠通過電子商務(wù)網(wǎng)站的搜索功能獲得商品信息，但要求用戶使用關(guān)鍵字確切描述自己的需求，在不能準(zhǔn)確描述所想購買商品的情況下，搜索功能無法發(fā)揮應(yīng)有的作用。推薦系統(tǒng)不需要用戶主動(dòng)參與，就能根據(jù)用戶以往的商品購買記錄，推薦滿足用戶興趣的商品。推薦系統(tǒng)不但增強(qiáng)了用戶購物體驗(yàn)，而且通過發(fā)現(xiàn)潛在購買者，有針對(duì)性地推薦商品，使銷售利潤最大化，達(dá)到了雙贏的效果。

目前，應(yīng)用最廣泛的是基于內(nèi)容的推薦算法和協(xié)同過濾（Collaborative Filtering，CF）算法[1-3]，協(xié)同過濾算法使用用戶與商品的歷史交互數(shù)據(jù)，并通過分析其他人的興趣偏好，建立當(dāng)前用戶偏好模型，即體現(xiàn)了“協(xié)同”，該算法假設(shè)存在一組興趣偏好相似的用戶群。相比較基于內(nèi)容的推薦算法，協(xié)同過濾算法對(duì)音頻、圖像等難以提取特征的非結(jié)構(gòu)化對(duì)象有較好的推薦效果[4-5]。

1 基于用戶的協(xié)調(diào)過濾算法

協(xié)同過濾推薦算法主要包括基于用戶（Userbased CF，UCF）和基于項(xiàng)目（Item-based CF，ICF）兩種協(xié)同過濾算法[6]?；谟脩舻膮f(xié)同過濾推薦算法包括以下3個(gè)階段：

1）相似度計(jì)算：相似度計(jì)算的方法主要有Person相關(guān)系數(shù)、Jaccard相關(guān)系數(shù)以及余弦相似度[7]。計(jì)算余弦相似度時(shí)，需計(jì)算用戶評(píng)分向量之間的余弦夾角，即為兩向量的點(diǎn)積與其模的乘積之商，用來衡量兩個(gè)用戶之間的相似度，設(shè)兩個(gè)用戶u和v的評(píng)分向量分別為和，則兩個(gè)用戶之間的相似度如式（1）所示：

2）用戶最近鄰搜尋：通常用戶最近鄰搜尋的辦法有兩種，基于閾值設(shè)定和基于K最近鄰搜尋。對(duì)于第一種方法，若相似度高于閾值即可進(jìn)入最近鄰集合，反之則剔除。而第二種方法中，根據(jù)相似度將目標(biāo)用戶的近鄰用戶進(jìn)行排序后，選取前K個(gè)用戶進(jìn)入最近鄰集合。兩種方法都會(huì)面對(duì)如何設(shè)計(jì)閾值和選取K值的問題，K值過大會(huì)導(dǎo)致在最近鄰集合中引入不相似或干擾用戶，從而影響最終的推薦效果；K值過小則可能導(dǎo)致最近鄰集合信息不全，同樣不利于推薦效果。

3）預(yù)測(cè)評(píng)分并生成top-N推薦：完成最近鄰搜尋后能夠獲得目標(biāo)用戶的近鄰集，可用式（2）預(yù)測(cè)未評(píng)分項(xiàng)目的評(píng)分，將項(xiàng)目按照預(yù)測(cè)評(píng)分降序進(jìn)行排序，把前N個(gè)項(xiàng)目推薦給目標(biāo)用戶。

式中，用戶u的最近鄰集合為C，用戶u與鄰近用戶v之間的相似度為wuv，鄰近用戶v對(duì)項(xiàng)目j的評(píng)分為Rv,j，Pu,j為目標(biāo)用戶u對(duì)未評(píng)分項(xiàng)目j的預(yù)測(cè)評(píng)分。

2 推薦算法的評(píng)價(jià)標(biāo)準(zhǔn)

推薦算法的準(zhǔn)確度是衡量推薦算法優(yōu)劣的關(guān)鍵，推薦算法評(píng)價(jià)指標(biāo)包括對(duì)預(yù)測(cè)評(píng)分準(zhǔn)確度和top-N推薦準(zhǔn)確度兩類評(píng)價(jià)指標(biāo)，對(duì)top-N推薦準(zhǔn)確度的評(píng)價(jià)指標(biāo)主要有召回率（Recall）和準(zhǔn)確率（Precision），對(duì)預(yù)測(cè)評(píng)分準(zhǔn)確度的評(píng)價(jià)指標(biāo)通常包括平均絕對(duì)誤差（Mean Absolute Error，MAE）和均方根誤差（Root Mean Square Error，RMSE）[8-9]。

平均絕對(duì)誤差與均方根誤差利用預(yù)測(cè)評(píng)分與真實(shí)評(píng)分間的誤差大小來衡量系統(tǒng)的預(yù)測(cè)精度。MAE和RMSE值越小說明推薦質(zhì)量越高，預(yù)測(cè)的評(píng)分與實(shí)際評(píng)分誤差越小。MAE及RMSE的計(jì)算公式為：

其中，{p1,p2,…,pn}為預(yù)測(cè)的用戶評(píng)分集合，{q1,q2,…,qn}為實(shí)際的用戶評(píng)分集合，n為用戶評(píng)價(jià)的項(xiàng)目數(shù)量。

準(zhǔn)確率（Precision）表示推薦列表中推薦的準(zhǔn)確項(xiàng)目所占的比例，如式（5）所示：

召回率（Recall）是用戶推薦準(zhǔn)確的項(xiàng)目在測(cè)試集中所占的比值，如式（6）所示：

其中，test為測(cè)試集，top-N為預(yù)測(cè)評(píng)分的前N個(gè)項(xiàng)目，|L|表示設(shè)定的推薦列表長度。

3 數(shù)據(jù)稀疏性問題

協(xié)同過濾算法具有用戶群體社會(huì)化的特點(diǎn)，且高度自動(dòng)化、新興趣發(fā)現(xiàn)等優(yōu)勢(shì)，能夠推薦非結(jié)構(gòu)化對(duì)象，因此在推薦系統(tǒng)中被廣泛使用，但其存在稀疏性、冷啟動(dòng)和擴(kuò)展性等問題[10-12]。

在電子商務(wù)系統(tǒng)中，由于用戶和商品數(shù)量的急劇增加，加之用戶缺乏對(duì)商品評(píng)分的主動(dòng)性，使得用戶評(píng)分的商品數(shù)量只占很少的一部分，用戶與商品評(píng)分矩陣（表）非常稀疏，用戶-商品矩陣的高度稀疏將造成相似計(jì)算出現(xiàn)很大誤差，進(jìn)而影響推薦系統(tǒng)的推薦質(zhì)量和推薦性能。數(shù)據(jù)的稀疏性用稀疏度（Sparsity）表示，稀疏度是指評(píng)分矩陣中空值的數(shù)目與矩陣元素總數(shù)的比值，如式（7）所示：

其中，|R|表示評(píng)分?jǐn)?shù)，|I|表示項(xiàng)目數(shù)或商品數(shù)，|U|表示評(píng)分者數(shù)，Sparsity是所得的稀疏度[13]。

解決數(shù)據(jù)稀疏性問題的主要方法有降維技術(shù)、評(píng)分矩陣預(yù)填充、多種特征融合、數(shù)據(jù)聚類、以及相似度改進(jìn)算法[14]。相似度計(jì)算作為協(xié)同過濾算法的重要部分，但由于評(píng)分矩陣的稀疏性，使兩個(gè)用戶之間的共同評(píng)分項(xiàng)數(shù)量很小，因此，傳統(tǒng)計(jì)算相似度的方法會(huì)出現(xiàn)很大誤差。文獻(xiàn)[15]針對(duì)社交網(wǎng)絡(luò)，提出了屬性相似度及其構(gòu)成與計(jì)算方法，有效地提高了推薦準(zhǔn)確率。文獻(xiàn)[16]在數(shù)據(jù)高度稀疏的情況，建立了梯形模糊的評(píng)分模型，并使用該模型計(jì)算用戶之間的相似度。文獻(xiàn)[17]針對(duì)評(píng)分矩陣的稀疏性，提出了一種加權(quán)相似度算法，以減小評(píng)分矩陣稀疏性導(dǎo)致的相似度誤差。

4 改進(jìn)用戶相似度的推薦算法

在大多數(shù)推薦系統(tǒng)中，用戶評(píng)過分的項(xiàng)目很少，計(jì)算用戶之間的相似性會(huì)產(chǎn)生很大的誤差，使得生成的用戶近鄰集合與實(shí)際的近鄰集合有較大差異。同理，基于項(xiàng)目的協(xié)同過濾算法項(xiàng)目之間的共同評(píng)價(jià)也很少，使得計(jì)算的項(xiàng)目間的相似度誤差較大，得到的項(xiàng)目近鄰集合也有偏差[18-19]。文中提出了一種改進(jìn)用戶相似度的協(xié)同過濾推薦算法（Improved user similarity User-based CF，IUCF），該算法基于項(xiàng)目特征的稀疏數(shù)據(jù)預(yù)處理方法，結(jié)合用戶的已評(píng)分信息及項(xiàng)目的特征，生成用戶與項(xiàng)目特征興趣矩陣，使用用戶與項(xiàng)目特征興趣矩陣計(jì)算用戶的相似度，提升用戶相似度的準(zhǔn)確率，最終提高推薦的精度和準(zhǔn)確度。

在一個(gè)推薦系統(tǒng)中，一般包含的項(xiàng)目數(shù)量十分巨大，而項(xiàng)目特征的個(gè)數(shù)要遠(yuǎn)遠(yuǎn)小于項(xiàng)目數(shù)，例如Movielens-100k數(shù)據(jù)集，電影的數(shù)目有1 682部，而電影的類型只有19種，一部電影可以屬于一個(gè)或多個(gè)不同的類型。由用戶與項(xiàng)目評(píng)分矩陣（表）生成的用戶與項(xiàng)目特征興趣矩陣，將大幅降低數(shù)據(jù)稀疏度，例如，在Movielens-100k數(shù)據(jù)集中，觀眾與電影評(píng)分矩陣（用戶與項(xiàng)目評(píng)分矩陣）的數(shù)據(jù)稀疏度為0.937，生成的觀眾與電影類型興趣矩陣（用戶與項(xiàng)目特征興趣矩陣）的數(shù)據(jù)稀疏度為0.205。由于觀眾與電影類型興趣矩陣數(shù)據(jù)密度的提高，觀眾之間共同評(píng)分項(xiàng)數(shù)量增多，因此，使用觀眾與電影類型興趣矩陣計(jì)算得到的觀眾相似度更加準(zhǔn)確，更能反映觀眾對(duì)不同類型電影的偏好。

假設(shè)在一個(gè)包括N個(gè)用戶和M個(gè)項(xiàng)目的推薦系統(tǒng)中，R為用戶與項(xiàng)目評(píng)分矩陣，記作[Ru,i]N×M，其中，Ru,i表示用戶u對(duì)項(xiàng)目i的評(píng)分。以Movielens-100k數(shù)據(jù)集為例，算法步驟描述如下：

1）數(shù)據(jù)讀入和預(yù)處理：讀入觀眾對(duì)電影的評(píng)分集合，把觀眾對(duì)電影的評(píng)分集合分成訓(xùn)練集train和測(cè)試集test兩部分，使用訓(xùn)練集部分生成觀眾與電影評(píng)分矩陣R=[Ru,i]N×M，讀入電影的類型描述集合，生成電影與電影類型矩陣（項(xiàng)目與項(xiàng)目特征矩陣）V=[Vi,f]M×Q。

2）由觀眾與電影評(píng)分矩陣R生成觀眾與電影興趣矩陣R′：對(duì)于觀眾與電影評(píng)分矩陣R中的每個(gè)評(píng)分項(xiàng)Ru,i，當(dāng)評(píng)分項(xiàng)Ru,i≧1時(shí)，設(shè)定Ru,i=1，生成的觀眾與電影興趣矩陣為。

3）由觀眾與電影興趣矩陣R′和電影與電影類型矩陣V生成觀眾與電影類型興趣矩陣（用戶與項(xiàng)目特征興趣矩陣）T：觀眾與電影興趣矩陣和電影與電影類型矩陣相乘得到中間結(jié)果矩陣，然后求出T′每行的和，計(jì)算得到矩陣T的每個(gè)元素，生成觀眾與電影類型興趣矩陣T。

4）使用觀眾與電影類型興趣矩陣T生成觀眾間相似性矩陣S=[Su,v]N×N：選擇余弦相似度，計(jì)算每一個(gè)觀眾和其他觀眾的相似性，組成觀眾相似性矩陣S，通過式（1）計(jì)算可得到觀眾相似性矩陣S的元素Su,v，和是觀眾u和v在矩陣T中的觀眾與電影類型興趣向量。

5）搜索最近鄰：在不同數(shù)目的K最近鄰情況下，對(duì)測(cè)試集中的每個(gè)觀眾，在觀眾相似性矩陣S中搜索與該觀眾相似度最大的前K個(gè)觀眾組成最近鄰集合。

6）預(yù)測(cè)測(cè)試集中的觀眾對(duì)電影的評(píng)分：根據(jù)式（2）預(yù)測(cè)用戶對(duì)1 682部電影的評(píng)分，例如測(cè)試集中的觀眾u，對(duì)電影的實(shí)際評(píng)分集合為{q1,q2,…,qn}，對(duì)應(yīng)電影的預(yù)測(cè)評(píng)分集合為{p1,p2,…,pn}{p1,p2,…,pn}，根據(jù)式（3）計(jì)算MAE。

7）計(jì)算推薦準(zhǔn)確率和召回率：依據(jù)給定top-N的N值生成推薦給觀眾的電影集合top-N，test為測(cè)試集，按照式（5）計(jì)算推薦準(zhǔn)確率，按照式（6）計(jì)算推薦召回率。

5 實(shí)驗(yàn)描述及結(jié)果分析

實(shí)驗(yàn)使用的編程語言是python3.7，開發(fā)工具為Jupyter notebook，實(shí)驗(yàn)程序還使用了兩個(gè)擴(kuò)展程序庫NumPy和Pandas。NumPy是一個(gè)基礎(chǔ)性的python科學(xué)計(jì)算庫，提供高維度數(shù)組與矩陣的計(jì)算能力，并提供大量方便用戶調(diào)用的函數(shù)庫[20]。Pandas是一個(gè)數(shù)據(jù)分析包，通過提供的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)以及快速、靈活的操作，成為了python環(huán)境下高效而強(qiáng)大的數(shù)據(jù)分析工具[21]。

實(shí)驗(yàn)所使用的數(shù)據(jù)集是Movielens-100k，由943名線上電影觀眾針對(duì)1 682部電影共10萬條評(píng)分記錄組成。該數(shù)據(jù)集包含電影的類型描述、觀眾信息和觀眾對(duì)電影的評(píng)分等3個(gè)數(shù)據(jù)集文件，電影類型有19種，觀眾對(duì)電影的評(píng)分是1～5的整數(shù)，每部電影至少被評(píng)價(jià)1次，每個(gè)觀眾至少給二十部電影評(píng)過分。原始數(shù)據(jù)隨機(jī)分成5份，每次將其中4份數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，另一份作為測(cè)試數(shù)據(jù)，運(yùn)行5次，并將5次實(shí)驗(yàn)結(jié)果的平均值作為最終的評(píng)測(cè)值。

實(shí)驗(yàn)選擇了4個(gè)推薦算法評(píng)價(jià)指標(biāo)包括推薦精度(MAE)、準(zhǔn)確率（Precision）、召回率（Recall）以及預(yù)測(cè)耗時(shí)，使用這4個(gè)評(píng)價(jià)指標(biāo)將IUCF算法與UCF進(jìn)行比較。預(yù)測(cè)耗時(shí)是在同樣的條件下比較兩種推薦算法，計(jì)算推薦結(jié)果耗費(fèi)的時(shí)間。該算法最主要的參數(shù)是用戶最近鄰的K值，選擇用戶不同的近鄰數(shù)目對(duì)算法的結(jié)果有重要影響。

1）用戶最近鄰K值的取值范圍為10～300，且為10的整數(shù)倍，UCF算法和IUCF算法的MAE值隨K值的變化趨勢(shì)如圖1所示。當(dāng)K小于140時(shí)，IUCF算法的MAE值小于UCF算法，K值越小，兩種算法的MAE差值越大；隨著K值的增大，當(dāng)K大于140時(shí)，兩種算法的MAE趨于相等。說明相比傳統(tǒng)的UCF算法，其在用戶最近鄰K值越小時(shí)，預(yù)測(cè)的評(píng)分與觀眾實(shí)際評(píng)分更接近，推薦精度更高；當(dāng)K大于140時(shí)，兩種算法預(yù)測(cè)的評(píng)分基本相同，推薦精度也大致相等。

圖1 算法MAE比較

2）K的取值方法與上面相同，取值范圍為10～300，且為10的整數(shù)倍，兩種算法預(yù)測(cè)耗時(shí)隨K值的變化如圖2所示。當(dāng)K小于140時(shí)，IUCF算法的預(yù)測(cè)耗時(shí)小于UCF算法，當(dāng)K大于140時(shí)，兩種算法的預(yù)測(cè)耗時(shí)基本相等，并且隨著K值的增大，兩種算法預(yù)測(cè)耗時(shí)都趨于相同的值。從圖2可知，當(dāng)K小于140時(shí)，IUCF算法比UCF算法效率更高，當(dāng)K大于140時(shí)，兩種算法效率基本相同。

3）兼顧評(píng)分預(yù)測(cè)的準(zhǔn)確率和算法執(zhí)行效率，最近鄰數(shù)目K值取為140，top-N推薦的N取值范圍為10～500、且為10的整數(shù)倍，兩種算法的準(zhǔn)確率隨N值的變化如圖3所示。兩種算法準(zhǔn)確率曲線的基本趨勢(shì)是隨著N值的增加，準(zhǔn)確率提高，當(dāng)N等于360時(shí)，UCF算法的準(zhǔn)確率最高；當(dāng)N等于380時(shí)，IUCF算法的準(zhǔn)確率最高。IUCF算法的準(zhǔn)確率曲線始終位于UCF算法的準(zhǔn)確率曲線上方，IUCF算法相比UCF算法準(zhǔn)確率平均提高了0.45%，說明IUCF算法的準(zhǔn)確率總體優(yōu)于UCF算法。

圖3 算法準(zhǔn)確率比較

4）同樣取K為140，兩種算法的召回率隨top-N推薦的N值變化如圖4所示。N值由10至500，且為10的整數(shù)倍，兩種算法的召回率都隨N值增大而提高，但I(xiàn)UCF算法召回率曲線始終位于UCF算法召回率上方，IUCF算法相比UCF算法召回率平均提高了5.2%，說明IUCF算法的召回率整體優(yōu)于UCF算法。

圖4 算法召回率比較

6 結(jié)論

文中使用Movielens-100k數(shù)據(jù)集，選擇了4個(gè)推薦算法評(píng)價(jià)指標(biāo)，對(duì)比改進(jìn)的用戶相似度協(xié)同過濾推薦算法（IUCF）和傳統(tǒng)的基于用戶的協(xié)同過濾算法（UCF）。在用戶最近鄰數(shù)目K小于140時(shí)，改進(jìn)的用戶相似度協(xié)同過濾推薦算法推薦精度高，預(yù)測(cè)評(píng)分準(zhǔn)確，推薦消耗的時(shí)間少，推薦效率高，而當(dāng)用戶最近鄰數(shù)K大于140時(shí)，兩種算法的推薦精度和推薦消耗時(shí)間趨于相等。在用戶最近鄰數(shù)K=140并且top-N推薦的N取值范圍為10～500的條件下，IUCF算法的準(zhǔn)確率及召回率從總體上看高于UCF算法。