一種基于蟻群算法的用戶(hù)瀏覽路徑推薦方法

劉晉佩，曾建平

（廈門(mén)大學(xué)信息科學(xué)與技術(shù)學(xué)院，福建 廈門(mén)361005）

隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)的迅速發(fā)展，互聯(lián)網(wǎng)的信息量呈爆炸式增長(zhǎng)，信息過(guò)載成為互聯(lián)網(wǎng)發(fā)展所面臨的主要挑戰(zhàn).尤其在電子商務(wù)領(lǐng)域，信息過(guò)載問(wèn)題更加突出，推薦系統(tǒng)正是解決該問(wèn)題的有效手段之一.在電子商務(wù)推薦系統(tǒng)中［1］，協(xié)同過(guò)濾算法是應(yīng)用最為廣泛的方法，它具有推薦效果好，實(shí)現(xiàn)和維護(hù)代價(jià)低等優(yōu)點(diǎn)，成為最成功的個(gè)性化推薦技術(shù)之一.Xerox PARC研究中心提供的Tapestry［2］被認(rèn)為是第1個(gè)協(xié)同過(guò)濾推薦系統(tǒng)，該系統(tǒng)用于過(guò)濾E－mail信息和Usent文章.由于協(xié)同過(guò)濾技術(shù)是基于用戶(hù)對(duì)項(xiàng)目的評(píng)分?jǐn)?shù)據(jù)，隨著電子商務(wù)系統(tǒng)中用戶(hù)和項(xiàng)目的快速增長(zhǎng)，數(shù)據(jù)稀疏程度不斷擴(kuò)大，從而造成整個(gè)推薦系統(tǒng)的準(zhǔn)確度不斷降低.此外，推薦系統(tǒng)中新用戶(hù)和新商品的加入還會(huì)造成系統(tǒng)無(wú)法完成推薦的冷啟動(dòng)問(wèn)題.為了解決上述問(wèn)題，需要探索新的推薦算法.

1 預(yù)備知識(shí)

Dorigo等［3］在1991年提出了蟻群算法，此后在他的其他著作中詳細(xì)地闡述了該算法的基本原理和數(shù)學(xué)模型.蟻群算法是種群進(jìn)化算法中的一種，具有良好的協(xié)作和搜索能力.同時(shí)還是一種本質(zhì)并行的算法，能夠迅速發(fā)現(xiàn)最優(yōu)解.因此，蟻群算法非常適合應(yīng)用于推薦系統(tǒng)中解決由數(shù)據(jù)集稀疏帶來(lái)的問(wèn)題.

根據(jù)蟻群算法［4］，一個(gè)完整的推薦系統(tǒng)可以看作是由螞蟻所代表的用戶(hù)以及螞蟻所要尋找的“食物”所代表的商品項(xiàng)目構(gòu)成，因此，有如下假設(shè)：

1）將用戶(hù)看作是推薦系統(tǒng)中的螞蟻，螞蟻之間通過(guò)信息素進(jìn)行交流；

2）將推薦系統(tǒng)中的目標(biāo)商品項(xiàng)目看作螞蟻要尋找的“食物”；

3）螞蟻和食物之間存在很多非目標(biāo)商品項(xiàng)目，將他們視為螞蟻覓食路徑上的節(jié)點(diǎn)，用戶(hù)瀏覽這些商品項(xiàng)目就等同于螞蟻訪(fǎng)問(wèn)這些節(jié)點(diǎn)，并留下信息素.這里信息素為用戶(hù)對(duì)商品項(xiàng)目的評(píng)分.

設(shè)推薦系統(tǒng)中用戶(hù)的總數(shù)為M，商品項(xiàng)目總數(shù)為N，記用戶(hù)i對(duì)商品項(xiàng)目j的原始評(píng)分為a′ij，實(shí)時(shí)評(píng)分為a″ij，最終評(píng)分為aij.

用戶(hù)間相似度的計(jì)算通常是利用用戶(hù)對(duì)商品的評(píng)分信息來(lái)計(jì)算得到的［5］，其中Pearson相似性和余弦相似性是最常用的方法，由于Pearson相似性考慮了不同用戶(hù)的評(píng)分喜好，因此可以提高尋找鄰居用戶(hù)的準(zhǔn)確度，本文計(jì)算用戶(hù)間的相似度所采用的便是Pearson相似性算法.定義用戶(hù)i1和i2共同打過(guò)分的商品項(xiàng)目集合為Si1i2，則用戶(hù)i1和i2之間的相似度sim（i1，i2）定義為：

目標(biāo)用戶(hù)u的最近鄰居集合用Su表示［6］，在Su中的用戶(hù)是按與目標(biāo)用戶(hù)的相似度從高到低排列的，則目標(biāo)用戶(hù)u對(duì)未評(píng)分項(xiàng)目j的預(yù)測(cè)評(píng)分Puj為：

綜上，用戶(hù)i對(duì)項(xiàng)目j的最終評(píng)分［7］可表示為：

2 基于蟻群算法的推薦系統(tǒng)

2.1 轉(zhuǎn)移概率函數(shù)的建立

用戶(hù)在瀏覽商品時(shí)會(huì)根據(jù)瀏覽路徑上信息素的強(qiáng)弱來(lái)決定下一個(gè)將要瀏覽的商品，這里用禁忌表集合tabu來(lái)記錄用戶(hù)瀏覽過(guò)的商品項(xiàng)目，集合D＝｛1，2，…，N｝為推薦系統(tǒng)中項(xiàng)目的集合，用戶(hù)從項(xiàng)目j1轉(zhuǎn)移到項(xiàng)目j2的轉(zhuǎn)移概率為：

其中，allowed＝D－tabu表示用戶(hù)下一步可選擇的商品集，ηj1j2為能見(jiàn)度，它表示用戶(hù)從項(xiàng)目j1轉(zhuǎn)移到項(xiàng)目j2的期望程度，可根據(jù)某種啟發(fā)式函數(shù)來(lái)確定，具體形式將在下文中給出.參數(shù)α和β分別表示信息素強(qiáng)度和能見(jiàn)度在轉(zhuǎn)移概率中的相對(duì)重要性.α越大，表示用戶(hù)更傾向于選擇最近鄰居集中用戶(hù)選擇過(guò)的商品.β越大，表示用戶(hù)更傾向于選擇與當(dāng)前瀏覽項(xiàng)目相似的商品.

2.2 啟發(fā)式函數(shù)的設(shè)計(jì)

啟發(fā)式函數(shù)的設(shè)計(jì)來(lái)源于兩部分，一部分來(lái)自于不同用戶(hù)對(duì)同一項(xiàng)目的評(píng)分，為保持項(xiàng)目的原始屬性，用項(xiàng)目j的原始評(píng)分向量Cj＝（a′1j，a′2j，…，a′Mj）來(lái)表示項(xiàng)目的評(píng)價(jià)屬性值，項(xiàng)目j1和j2的相似性由余弦相似性公式來(lái)表示：

余弦值越大說(shuō)明Ij1和Ij2越相似.

啟發(fā)式函數(shù)的另一部分來(lái)自項(xiàng)目本身的屬性值.設(shè)I為m個(gè)具有l(wèi)維屬性的項(xiàng)目數(shù)據(jù)集合I＝｛Ii｜Ii，i＝1，2，…，m｝，其中Iij指項(xiàng)目i的第j個(gè)屬性值，則項(xiàng)目j1和j2間的相似度由歐氏距離公式來(lái)表示：

Ij1和Ij2的歐氏距離越小說(shuō)明Ij1和Ij2越相似.

綜上，啟發(fā)式函數(shù)ηj1j2就可以表示為：

ηj1j2值越大，表明用戶(hù)從項(xiàng)目j1轉(zhuǎn)移到項(xiàng)目j2的期望程度越大，反之越小.

2.3 項(xiàng)目評(píng)分更新規(guī)則

螞蟻在它行走的過(guò)程中會(huì)在其運(yùn)動(dòng)軌跡上留下信息素，信息素的強(qiáng)弱會(huì)影響到其他螞蟻的行為，如果某條運(yùn)動(dòng)軌跡上的信息素越強(qiáng)，那么其他螞蟻選擇該軌跡的概率也就越大，當(dāng)有螞蟻從這條軌跡上經(jīng)過(guò)時(shí)還會(huì)繼續(xù)增加該軌跡上信息素的強(qiáng)度，當(dāng)然，如果隨后該軌跡上沒(méi)有螞蟻經(jīng)過(guò)，信息素的強(qiáng)度就會(huì)逐漸減弱.這里信息素的更新實(shí)質(zhì)上就是項(xiàng)目評(píng)分的更新，推薦系統(tǒng)每做一次推薦或遍歷完所有的項(xiàng)目都會(huì)依據(jù)用戶(hù)的反應(yīng)，更新項(xiàng)目的評(píng)分，更新規(guī)則如下所示：

其中，ρ（0≤ρ＜1）表示信息素?fù)]發(fā)因子，1－ρ為信息素殘留因子，ξ為本次遍歷過(guò)程中的信息素增量.

信息素殘留因子表示不同螞蟻間相互影響的關(guān)系［8］：當(dāng)信息素殘留因子過(guò)大時(shí)，之前搜索過(guò)的路徑被再次搜索的可能性會(huì)增大，降低了算法的隨機(jī)性和全局搜索能力；雖然通過(guò)減小信息素殘留因子可以提高算法的隨機(jī)性和全局搜索能力，但又會(huì)降低算法的收斂速度.ξ的初值為0，如果用戶(hù)瀏覽并購(gòu)買(mǎi)推薦項(xiàng)目時(shí)，會(huì)使項(xiàng)目評(píng)分增加，即ξ＞0；如果用戶(hù)未瀏覽或?yàn)g覽后未購(gòu)買(mǎi)推薦項(xiàng)目時(shí)，ξ＝0.

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

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

實(shí)驗(yàn)采用由美國(guó)Minnesota大學(xué)的GroupLens研究小組創(chuàng)建并維護(hù)的MovieLens數(shù)據(jù)集，該數(shù)據(jù)集由943名用戶(hù)對(duì)1 682部電影的100 000條評(píng)分記錄所組成，其中，任一用戶(hù)都至少對(duì)20部電影打過(guò)評(píng)分，評(píng)分范圍是1～5，5表示“非常喜歡”，1表示“不喜歡”.評(píng)分的稀疏等級(jí)為ψ＝1－100 000／（943×1 682）＝0.93 695，可見(jiàn)，該數(shù)據(jù)集的評(píng)分矩陣是非常稀疏的.實(shí)驗(yàn)隨機(jī)地把數(shù)據(jù)按8∶2的比例分為訓(xùn)練集和測(cè)試集，訓(xùn)練集用來(lái)產(chǎn)生實(shí)驗(yàn)結(jié)果，測(cè)試集用來(lái)測(cè)試實(shí)驗(yàn)結(jié)果的性能.

3.2 推薦質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn)

這里采用分類(lèi)準(zhǔn)確度作為評(píng)價(jià)該算法優(yōu)劣的標(biāo)準(zhǔn)［9］，分類(lèi)準(zhǔn)確度表示的是推薦系統(tǒng)能否正確預(yù)測(cè)用戶(hù)是否喜歡某個(gè)商品的能力.網(wǎng)站在提供推薦服務(wù)時(shí)，一般給用戶(hù)一個(gè)個(gè)性化推薦列表，長(zhǎng)度為L(zhǎng).根據(jù)預(yù)測(cè)評(píng)分對(duì)訓(xùn)練集上的商品進(jìn)行排序，記R（u）為用戶(hù)u在訓(xùn)練集上的最可能喜歡商品列表，T（u）為用戶(hù)u在測(cè)試集上的最喜歡商品列表，Tu為用戶(hù)u在測(cè)試集上喜歡的商品數(shù)目，Npt為用戶(hù)u在R（u）和T（u）上共有的商品數(shù)目.那么對(duì)用戶(hù)u，其推薦結(jié)果的準(zhǔn)確率Pu（L）（precision）和召回率Ru（L）（recall）分別表示為：

這里，Pu（L）表示系統(tǒng)所推薦的L個(gè)商品中用戶(hù)真正喜歡的商品所占的比例，Ru（L）表示一個(gè)用戶(hù)真正喜歡的商品能被推薦出來(lái)的概率.

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

實(shí)驗(yàn)使用5對(duì)數(shù)據(jù)集進(jìn)行測(cè)試，取5次實(shí)驗(yàn)的平均值作為實(shí)驗(yàn)的結(jié)果.實(shí)驗(yàn)中當(dāng)取ρ＝0.3，ξ＝1.5，α＝1.8，β＝1.3時(shí)，取得較好的結(jié)果.為了驗(yàn)證本文提出的算法的有效性［10］，以ItemRank和 Maximum－frequency（MaxF）推薦算法作為對(duì)照，推薦長(zhǎng)度從10增加到60，間隔為10，然后與本文提出的算法作比較，實(shí)驗(yàn)結(jié)果如表1所示.

將表1中的數(shù)據(jù)轉(zhuǎn)換成圖的形式，實(shí)驗(yàn)結(jié)果如圖1所示.

由于MaxF算法只是將推薦系統(tǒng)內(nèi)的項(xiàng)按被用戶(hù)所瀏覽的次數(shù)進(jìn)行簡(jiǎn)單的降序排序，將用戶(hù)沒(méi)有看過(guò)且排序靠前的項(xiàng)推薦給用戶(hù)，沒(méi)有考慮項(xiàng)目的評(píng)價(jià)屬性和項(xiàng)目自身的屬性，而ItemRank算法在將用戶(hù)－項(xiàng)目評(píng)分二部圖轉(zhuǎn)換為相關(guān)圖時(shí)會(huì)導(dǎo)致用戶(hù)評(píng)分信息的丟失.本文提出的算法在運(yùn)用蟻群算法強(qiáng)大的協(xié)作和搜索能力時(shí)，啟發(fā)式函數(shù)的設(shè)計(jì)考慮了項(xiàng)目的評(píng)價(jià)屬性和項(xiàng)目自身的屬性，提高了尋找相似項(xiàng)目的準(zhǔn)確度，同時(shí)保留了協(xié)同過(guò)濾算法來(lái)尋找目標(biāo)用戶(hù)的最近鄰居集.從圖1中可以看出，隨著推薦長(zhǎng)度的增加，3種算法的準(zhǔn)確率均降低，召回率增加，但本文提出的算法不論準(zhǔn)確率還是召回率都比MaxF和ItemRank算法有了明顯提高，在推薦長(zhǎng)度為40時(shí)本文提出的算法的準(zhǔn)確率和召回率分別為27.14%和31.82%，比MaxF算法分別高出了10.82%和10.62%，比Item－Rank算法分別高出了9.91%和9.23%，證明了算法的有效性.

4 結(jié) 論

本文提出一種基于蟻群算法的電子商務(wù)推薦系統(tǒng).該方法可有效地減少由數(shù)據(jù)集稀疏帶來(lái)的問(wèn)題，提高推薦系統(tǒng)的推薦質(zhì)量，且通過(guò)設(shè)置相關(guān)參數(shù)解決新用戶(hù)的冷啟動(dòng)問(wèn)題.然而，蟻群算法中各參數(shù)的取值尚無(wú)嚴(yán)格的理論依據(jù)，至今還沒(méi)有確定參數(shù)取值的一般方法，需要依靠大量的重復(fù)性實(shí)驗(yàn)尋找較優(yōu)的結(jié)果.此外，由于推薦系統(tǒng)中的用戶(hù)－評(píng)分矩陣是一個(gè)高維度的龐大矩陣［11］，且數(shù)據(jù)稀疏度極高，目前只能通過(guò)掃描評(píng)分矩陣來(lái)進(jìn)行查詢(xún)，并且蟻群算法的引入也提高了掃面時(shí)間的復(fù)雜度.因此，未來(lái)可以通過(guò)建立多維的動(dòng)態(tài)索引結(jié)構(gòu)，從而提高推薦系統(tǒng)的實(shí)時(shí)性.

表1 不同推薦長(zhǎng)度下各算法的準(zhǔn)確率和召回率Tab.1 Precision and recall under the different length of recommended list

圖1 3種算法在MovieLense數(shù)據(jù)集上的準(zhǔn)確率（a）和召回率（b）Fig.1 Three algorithms performances of the MovieLens data set：（a）precision，（b）recall.

［1］Sarwar B，Karypis G，Konstan J，et al.Item－based collaborative filtering recommendation algorithms［C］∥Proceedings of the 10th International Conference on World Wide Web.New York，USA：ACM，2001：285－295.

［2］Deshpande M，Karypis G.Item－based top－N recommendation algorithms［J］.ACM Transactions on Information Systems（TOIS），2004，2（1）：143－177.

［3］Dorigo M，Maniezzo V，Colorni A.Ant system：optimization by a colony of cooperating agents［J］.Systems Man and Cybernetics，Part B：Cybernetics，1996，26（1）：29－41.

［4］王晗，夏自謙.基于蟻群算法和瀏覽路徑的推薦算法研究［J］.中國(guó)科技信息，2009，33（7）：103－104.

［5］吳月萍，王娜，馬良.基于蟻群算法的協(xié)同過(guò)濾推薦系統(tǒng)的研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2010，21（10）：73－76.

［6］鄧愛(ài)林，朱揚(yáng)勇，施伯樂(lè).基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過(guò)濾推薦算法［J］.軟件學(xué)報(bào)，2003，14（9）：1621－1628.

［7］周玉妮.基于蟻群算法的移動(dòng)商務(wù)個(gè)性化推薦體系研究［D］.南京：南京郵電大學(xué)，2012.

［8］詹士昌，徐婕，吳俊.蟻群算法中有關(guān)參數(shù)的最優(yōu)選擇［J］.科技通報(bào)，2003，19（5）：381－386.

［9］朱郁筱，呂琳媛.推薦系統(tǒng)評(píng)價(jià)指標(biāo)綜述［J］.電子科技大學(xué)學(xué)報(bào)，2012，41（2）：163－175.

［10］Zhang Y，Wu J，Zhuang Y.Random walk models for top－N recommendation task［J］.Journal of Zhejiang University Science A，2009，10（7）：927－936.

［11］陳健，印鑒.基于影響集的協(xié)作過(guò)濾推薦算法［J］.軟件學(xué)報(bào)，2007，18（7）：1685－1694.