劉鑫 李家樂 趙敏

（吉林建筑科技學(xué)院 吉林省長春市 130114）

隨著互聯(lián)網(wǎng)信息的爆炸式增長，人們在享受豐富的數(shù)據(jù)帶來更多方便的同時也要忍受尋找自己真正需要的信息的時間越來越長所帶來的困擾。推薦系統(tǒng)為解決這一問題應(yīng)運而生，推薦系統(tǒng)是針對不同用戶的興趣、愛好為其進(jìn)行個性化推薦商品的服務(wù)，個性化推薦技術(shù)在一定程度上可以節(jié)省用戶搜索信息的時間，提高信息獲取效率，目前在個性化推薦算法及相關(guān)技術(shù)和應(yīng)用領(lǐng)域方面，已經(jīng)成為國內(nèi)外大批學(xué)者研究的熱點問題。其中主要研究的推薦算法有協(xié)同過濾算法、基于知識的推薦以及混合推薦算法等，而協(xié)同過濾一直是研究最多的技術(shù)之一，它通過維護用戶-商品評分矩陣，通過相似度計算公式，建立鄰居用戶集，產(chǎn)生推薦列表。

本文結(jié)合傳統(tǒng)的協(xié)同過濾推薦算法在打分稀疏，推薦正確率較低等問題，結(jié)合二部圖函數(shù)設(shè)計改進(jìn)的協(xié)同過濾推薦算法，給出了基于用戶和基于商品的混合列表推薦方式。使用戶更快、更方便地獲取到自己所想要的資源。

1 現(xiàn)有的協(xié)同過濾算法及算法存在的問題

1.1 協(xié)同過濾算法的問題描述

協(xié)同過濾推薦（collaborative filtering recommendation）是應(yīng)用最廣泛的一種推薦技術(shù)之一。它假設(shè)的前提是：若要向一個用戶推薦商品，首先找到與本用戶興趣愛好相似的其它用戶群，然后將相似用戶感興趣的商品推薦給本用戶。如圖1所示，user-B選擇了item-a、item-b和item-d,而user-C選擇了item-b和item-d,認(rèn)為user-B和user-C是相似用戶，因此將user-B選擇的item-a推薦給user-C。通常協(xié)同過濾算法分兩類：一類是基于記憶，基于記憶的又分為基于用戶的協(xié)同過濾和基于物品的協(xié)同過濾，另一類是基于模型。具體推薦過程分為三個階段：用戶興趣表示、相似用戶產(chǎn)生、商品推薦。

1.2 協(xié)同過濾算法分析

1.2.1 協(xié)同過濾算法的優(yōu)點

協(xié)同過濾推薦是基于相似用戶的興趣選擇進(jìn)行推薦，因此最大的優(yōu)點是對于推薦商品的資源類型不限，不需要對商品進(jìn)行內(nèi)容信息提取，而只需要用戶對選擇的商品進(jìn)行簡單的評分，通過采集評分矩陣，通過相似度計算，得到相似用戶的鄰居集合，從而根據(jù)鄰居集中用戶選擇的物品預(yù)測目標(biāo)用戶感興趣的物品，向用戶推薦，推薦的商品可以是視頻、美食或其他日用品等。

圖1：基于用戶的協(xié)同過濾

圖2：用戶-商品關(guān)系拓?fù)浣Y(jié)構(gòu)圖

1.2.2 協(xié)同過濾算法的缺點

通過分析傳統(tǒng)的協(xié)同過濾技術(shù)，一方面由于協(xié)同過濾推薦算法需要用戶的評分進(jìn)行推薦，對于新用戶和新商品產(chǎn)生時，由于沒有用戶-商品的評分?jǐn)?shù)據(jù)，導(dǎo)致出現(xiàn)冷啟動或數(shù)據(jù)稀疏問題，無法進(jìn)行推薦；另一方面隨著用戶及商品的數(shù)量增加、商品的類型更加多樣化、使得用戶-商品之間的關(guān)系更加復(fù)雜，通過計算相似度構(gòu)建用戶鄰居集合的效率會越來越低，因此傳統(tǒng)的協(xié)同過濾算法就存在數(shù)據(jù)稀疏、可擴展性和冷啟動等幾個問題的制約，影響最終商品的推薦結(jié)果和推薦效率。

2 改進(jìn)的協(xié)同過濾算法

圖3：算法流程圖

傳統(tǒng)的協(xié)同過濾推薦算法在尋找相似用戶時由于只是參考了鄰居集合中相似用戶進(jìn)行評分的商品，而當(dāng)相似用戶進(jìn)行評分的商品數(shù)量太少，獲得的評分矩陣稀疏時，最終產(chǎn)生的推薦列表可靠性較低，因此本文對二部圖模塊函數(shù)的理論進(jìn)行研究，在協(xié)同過濾算法中引入二部圖模塊函數(shù)（Bipartite Modularity）對用戶和商品進(jìn)行相似性劃分，擴大了用戶間相似性計算的范圍，提高了相似性的可靠性和準(zhǔn)確度，以商品社區(qū)劃分為例，具體步驟如下：

第一步：為每個商品初始化不同的社區(qū)，初始時商品數(shù)與社區(qū)數(shù)相同；

第二步：對于任意一個商品Si,首先將其添加到其他不同商品Sj所在的社區(qū)，計算社區(qū)變化后的每一個函數(shù)值，比較Si加入不同Sj所在的社區(qū)產(chǎn)生的函數(shù)值，找到函數(shù)值是正數(shù)且最大時對應(yīng)的鄰居商品Sj，則將Si劃分到Sj所在的商品社區(qū)；如果所得函數(shù)值都不為正值時，Si將繼續(xù)留在初始社區(qū)；

第三步：對所有的商品節(jié)點Si，重復(fù)上述操作；

第四步：更新所有的商品Si社區(qū)，并將劃分到一個社區(qū)的商品進(jìn)行重新編號作為一個新的商品節(jié)點，生成新的二部圖，兩次的二部圖進(jìn)行比較，如果新的二部圖的社區(qū)拓?fù)浣Y(jié)構(gòu)與之前有變化，重復(fù)執(zhí)行第二步，直到兩次的拓?fù)浣Y(jié)構(gòu)沒有變化時執(zhí)行第五步；

第五步：輸出最終的商品社區(qū)劃分。

3 改進(jìn)的協(xié)同過濾算法應(yīng)用于商品推薦中

3.1 問題表述

將用戶-商品評分的二元關(guān)系矩陣表示成二部圖，描述為G（Vu,Vs,E）表示。其中用戶總和表示為：Vu={u1,u2,u3,…,um}；商品總和表示為：Vs={s1,s2,s3,…,sn}；用戶-商品關(guān)系矩陣表示為：A={aij},其中，當(dāng) aij=1表示ui用戶選擇了sj商品。即規(guī)定任意兩個用戶（商品）節(jié)點之間的邊的條數(shù)越多就表示這兩個用戶（商品）節(jié)點之間的聯(lián)系越緊密，同時若任意兩個用戶（商品）都 與一個公共節(jié)點相連，那么這兩個節(jié)點也一定存在某種程度的聯(lián)系，建立用戶-商品二部圖拓?fù)浣Y(jié)構(gòu)如圖2。

3.2 相似性計算

第一步：初始化社區(qū)。

第二步：求取最近鄰。

3.3 推薦階段

針對進(jìn)行推薦商品的用戶，推薦列表的生成方式有三種：第一種推薦列表由被分配到相同的社區(qū)的商品構(gòu)建，第二種推薦列表由鄰居用戶社區(qū)的用戶構(gòu)建，第三種推薦列表是前兩種混合方式生成的。

為了描述生成的預(yù)測評分過程，設(shè)置四個概念：

其中，R（ui）表示同用戶ui在相同社區(qū)的其他用戶的集合，R（sm）表示同商品sm在相同社區(qū)的其他商品的集合，L（ui）是被用戶ui選擇的商品集合，L（sm）是選擇了相同商品sm的用戶集合。

為了得到推薦列表，對基于鄰居用戶社區(qū)進(jìn)行推薦，用戶ui對商品sm進(jìn)行預(yù)測得到評分值表示為：

基于商品社區(qū)進(jìn)行推薦，用戶ui對商品sm進(jìn)行預(yù)測得到評分值表示為：

集合中商品的排序按照推薦列表預(yù)測得到的評分值進(jìn)行從高到低排序，取最高值進(jìn)行推薦。

3.4 推薦算法建模

圖3是基于改進(jìn)的協(xié)同過濾推薦算法應(yīng)用于商品推薦的算法流程圖，可以將推薦算法建模過程分成兩個部分：用戶-商品關(guān)系建模和推薦實現(xiàn)建模，在用戶-商品關(guān)系建模過程中，首先采集用戶-商品的評分?jǐn)?shù)據(jù)，分別構(gòu)建用戶和商品的二部圖拓?fù)浣Y(jié)構(gòu)，建立用戶-商品分類模型，然后搭建用戶-商品二部圖模型；在推薦系統(tǒng)建模過程中，首先根據(jù)二部圖模塊函數(shù)計算用戶和商品間的相似值，構(gòu)建用戶-商品相似矩陣，應(yīng)用改進(jìn)的協(xié)同過濾推薦算法生成推薦列表，將預(yù)測得到的商品評分值進(jìn)行從高到低排序，并對鄰居用戶推薦商品評分最高的商品，完成商品個性化推薦。

4 結(jié)束語

本文分析了傳統(tǒng)的協(xié)同過濾算法，克服其在評分稀疏、正確率低的問題，在問題表述階段、相似性計算階段和推薦階段，綜合了利用二部圖模塊函數(shù)優(yōu)化的方法構(gòu)建用戶-商品分類模型，搭建用戶-商品二部圖模型，通過計算用戶和商品的相似性，設(shè)計得到改進(jìn)的協(xié)同過濾算法。在實驗階段，將改進(jìn)的協(xié)同過濾算法選取MovieLens作為基礎(chǔ)數(shù)據(jù)集，進(jìn)行基于社區(qū)劃分的推薦算法與傳統(tǒng)協(xié)同過濾推薦算法在正確率及穩(wěn)定性方面的比較，分別在十組數(shù)據(jù)上運行基于商品社區(qū)和用戶社區(qū)及混合推薦算法，取平均值，整體上看，改進(jìn)的協(xié)同過濾算法正確率高，且可以在多次迭代后快速達(dá)到穩(wěn)定。