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

劉鑫 李家樂 趙敏

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

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

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

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

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

協(xié)同過濾推薦（collaborative filtering recommendation）是應(yīng)用最廣泛的一種推薦技術(shù)之一。它假設(shè)的前提是：若要向一個(gè)用戶推薦商品，首先找到與本用戶興趣愛好相似的其它用戶群，然后將相似用戶感興趣的商品推薦給本用戶。如圖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é)同過濾，另一類是基于模型。具體推薦過程分為三個(gè)階段：用戶興趣表示、相似用戶產(chǎn)生、商品推薦。

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

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

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

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

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

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

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

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

圖3：算法流程圖

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

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

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

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

第四步：更新所有的商品Si社區(qū)，并將劃分到一個(gè)社區(qū)的商品進(jìn)行重新編號作為一個(gè)新的商品節(jié)點(diǎn)，生成新的二部圖，兩次的二部圖進(jìn)行比較，如果新的二部圖的社區(qū)拓?fù)浣Y(jié)構(gòu)與之前有變化，重復(fù)執(zhí)行第二步，直到兩次的拓?fù)浣Y(jié)構(gòu)沒有變化時(shí)執(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ī)定任意兩個(gè)用戶（商品）節(jié)點(diǎn)之間的邊的條數(shù)越多就表示這兩個(gè)用戶（商品）節(jié)點(diǎn)之間的聯(lián)系越緊密，同時(shí)若任意兩個(gè)用戶（商品）都 與一個(gè)公共節(jié)點(diǎn)相連，那么這兩個(gè)節(jié)點(diǎn)也一定存在某種程度的聯(lián)系，建立用戶-商品二部圖拓?fù)浣Y(jié)構(gòu)如圖2。

3.2 相似性計(jì)算

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

第二步：求取最近鄰。

3.3 推薦階段

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

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

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

4 結(jié)束語

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